4.1.3.Основание алгоритма бпф

В названиях алгоритмов БПФ можно встретить слово «RADIX» («основание» - в математическом смысле). Следующее после него число обозначает число фрагментов, на которое разбивается сигнал на каждом этапе прореживания (а также минимальный размер «кусочков» входного вектора, который достигается в результате его последовательных разбиений).

В алгоритмах «RADIX-2» размер анализируемой последовательности должен быть равен степени двойки, а ее половинное деление производится вплоть до получения двухэлементных последовательностей. Вычисление их ДПФ не требует операций умножения – два спектральных отсчета представляют собой сумму и разность отсчетов временных:

(0) = x(0) + x(1),

(1) = x(0) - x(1).

В алгоритмах «RADIX-4» количество отсчетов сигнала должно быть равно степени четверки, при каждом прореживании сигнал делится на четыре фрагмента, а последней стадией деления являются четырехэлементные последовательности. При вычислении их ДПФ умножение производится только на ±j, а такое умножение сводится к взаимной перестановке вещественной и мнимой частей комплексного числа с изменением знака у одной из них:

(0) = x(0) + x(1) + x(2) + x(3),

(1) = x(0) - jx(1) - x(2) + jx(3),

(2) = x(0) - x(1) + x(2) - x(3),

(3) = x(0) + jx(1) - x(2) –j x(3).

Выше показано, что использование основание 4 позволяет ощутимо уменьшить число выполняемых умножений.

ПРИЛОЖЕНИЕ 4.2

Пример выполнения домашнего задания.

Рассчитать ДПФ функции x(n) с использованием алгоритма БПФ для последовательности: {1,1,1,1} при N=4;