Алгоритм фильтрации, пример на основе БПФ (стр. 5 из 6)

Подставляя n и k в выражение для 16-точечного ДПФ, получаем

X(k₄k₃k₂k₁)=

(n₄n_Зn₂n₁)

Теперь распишем алгоритм по ступеням:

т = 0 - инверсия входной последовательности:

Х₀(n₁ 2³+n₂ 2²+n₃ 2+n₄)=x(n₄ 2³+n_3'2²+n₂2+n₁);

т= l - преобразование «бабочка» последовательности Х₀:

т = 2 - преобразование «бабочка» последовательности X₁:

m=3 - преобразование «бабочка» последовательности Х₂:

m=4 - преобразование «бабочка» последовательности Х_З:

Искомая выходная последовательность

Рисунок 7

Направленный граф полученного в примере 16-точечного БПФ с указанием источников элементарных ошибок округления произведений и масштабирования, а также путей их распространения изображен на рис.7. Ошибки округления появляются в местах умножения комплексных чисел на нетривиальные поворачивающие множители.

Ошибки масштабирования появляются на обоих входах каждой операции «бабочка» из-за сдвига входных чисел на один разряд вправо (деление на два).

Элементарные ошибки округления и масштабирования, возникающие на различных ступенях алгоритма, приводят к тому, что отсчеты ДПФ X(k) на выходе вычисляются неточно.

Обозначим ошибку вычисления k-ro отсчета ДПФ через e(k)=X'(k) -X(k), где Х'(k)-вычисленное значение отсчета.

Анализ траекторий распространения элементарных ошибок, возникающих на различных ступенях алгоритма, позволяет сделать следующие выводы:

1. Элементарная ошибка с дисперсией

, возникающая на т-й ступени алгоритма. вызывает ошибку с дисперсией в 2^v-m выходных точках БПФ.

2. Дисперсия ошибки каждого выходного отсчета алгоритма, обусловленной округлением произведений, равна сумме ошибок, 2^v-m из которых вызывается ошибками т-й ступени.

Перейдем к анализу арифметических ошибок. В силу того, что математическое ожидание всех элементарных ошибок равно нулю, математическое ожидание результирующей ошибки E(e(k))=0 для всех k. Тогда СКЗ ошибок ДПФ будет определяться только дисперсией элементарных ошибок.

Дисперсия ошибок округления произведения двух комплексных чисел на т-й ступени равна 4

. Множитель появляется из-за масштабирования на т предыдущих ступенях путем деления пополам.

Вычислим СКЗ ошибок e(k), k=0,...,N-1. Из анализа алгоритма БПФ (8.3) и соответствующего направленного графа следует, что нетривиальные умножения, связанные с вычислением отсчета Х (k), появляются, начиная со ступени

(8.5)

где.

Это объясняется тем, что первое появление

единицы в двоичном представлении

, , соответствует умножению на коэффициент -1 на ступени т, тогда на следующей т+ l-й ступени наличие коэффициента = 1 приведет к умножению на j, а уже на т+2 и далее ступенях все умножения будут нетривиальными. Это хорошо проследить, анализируя выражение (8.3), описывающее т-ю ступень алгоритма. Можно показать путем вычислений s (k), что для определения отсчетов с номерами k=0, N/4; N/2; 3N/4 не требуется выполнение нетривиальных умножений, все умножения здесь на ; . Ошибка округления этих отсчетов равна нулю. А для вычисления СКЗ ошибок округления отсчетов с другими k воспользуемся вторым выводом. В результате получим

(8.6)

Пример 7. Рассмотрим вычисление ошибок округления отсчетов 16-точечного БПФ. Для этого выпишем для каждого номера отсчета его двоичное представление

. Затем пользуясь выражением (8.6), вычисляем ошибки округления. Результаты расчетов приводятся в табл.1. Заметим, что отсчеты с номерами k=4, 8, 12 вычисляются точно так, как s(k)>4, где 4-максимальное число возможных ступеней алгоритма, т. е. в формировании отсчетов с номерами 0, 4, 8, 12 участвуют умножения только на тривиальные множители (см. также граф на рис.5).

Вычислим СКЗ ошибки, усредненное по всем k. На первых двух ступенях алгоритма (т=1,2) все умножения являются точными, так как множители тривиальны

; на выходах т-й ступени (т = 3,…, у) появляется N произведений в блоках, причем четыре произведения в каждом блоке являются точными в результате умножения также на тривиальные множители.

Таблица 1

Тогда, пользуясь выводом 1, получаем

(8.7)

В случае 16-точечного БПФ

Определим СКЗ выходной ошибки алгоритма, обусловленной масштабированием промежуточных результатов. Ошибка масштабирования комплексного числа на m-й ступени алгоритма имеет нулевое среднее и дисперсию

. Множитель появляется из-за масштабирования на m предыдущих ступенях.

В соответствии с выводом 2 СКЗ индивидуальной ошибки равно

(8.8)

в случае 16-точечного БПФ

Усредненное по всем выходам k СК3 также равно

(8.9)

Среднеквадратическое значение суммарной ошибки, обусловленной округлением и масштабированием, вычисляется как сумма отдельных СК3:

(8.10)

СК3 суммарной ошибки, усредненное по всем выходам алгоритма, равно

(8.11)

В случае 1б-точечного БПФ

Результаты вычисления СК3 суммарных ошибок также приведены в табл.1. Точность алгоритма принято оценивать по отношению «СК3 ошибки / СК3 выходного сигнала». В данном случае оно составляет

____«СКЗ ошибки»______ =

(8.12)

«СКЗ выходного сигнала»

В случае 1б-точечного БПФ

___«СК3 ошибки»_______ =

«СК3 выходного сигнала»

Как видно из полученных выражений, точность алгоритма зависит от двух параметров: длины преобразования N и разрядности представления чисел b_1.Если известны требования по точности вычисления и размер преобразования, разрядность процессора БПФ можно определить из следующего выражения, полученного логарифмированием выражения (8.12):

(8.13)

Теперь перейдем к анализу ошибок БПФ, вызванных неточным представлением значений поворачивающих множителей

Пусть

-точные значения коэффициентов Фурье, а '(k) - неточные, полученные при условии представления коэффициентов конечным числом разрядов