Быстрое преобразование Фурье (бпф)

Быстрое преобразование Фурье (FFT) является не более, чем алгоритмом для ускоренного вычисления ДПФ путем сокращения требуемого числа операций умножения и сложения. Данное преобразование было предложено в 1960-ых годах. Алгоритм быстрого преобразования Фурье значительно сокращает количество арифметических операций и объем памяти, необходимой для вычисления ДПФ. ДПФ может быть сильно упрощено, если использовать свойства симметрии и периодичности коэффициентов поворота.

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

Таблица 1.1

Эффективность бпф

N	Умножений при ДПФ	Умножений при БПФ	Эффективность БПФ
256	65 536	1 024	64 : 1
512	262 144	2 304	114 : 1
1 024	1 048 576	5 120	205 : 1
2 048	4 194 304	11 264	372 : 1
4 096	16 777 216	24 576	683 : 1

Если необходимо рассчитать только несколько точек спектра, ДПФ может быть более эффективным. Вычисление одного выходного отсчета спектра с использованием ДПФ требует только N умножений с комплексными числами.

Мы будем предполагать далее, что N=2ⁿ. При этом общность не теряется, так как N выбирается достаточно большим для того, чтобы удовлетворять теореме дискретизации Котельникова, т.е.

N  2BT,

где B – полоса частот сигнала x(t); T – его длительность.

Теорема Котельникова-Найквиста-Шеннона: если сигнал таков, что его спектр ограничен частотой F, по после дискретизации сигнала с частотой не менее 2F можно восстановить непрерывный сигнал по полученному цифровому сигналу абсолютно точно. Для этого нужно проинтерполировать цифровой сигнал «между отсчетами» специального вида функциями.

Рассмотрим случай вещественно-значной последовательности {X(m)} при N=8. Из свойства комплексной сопряженности ДПФ следует, что

; .

Тогда

; ;

W=e^-i2/8=e^-i/4;

. (1.17)

Используя свойство N-периодичности экспонент, для N=8 матрица будет иметь вид

.

Из свойства симметрии экспоненциальных функций следует, что

W_k+N/2=-W_k, где .

То есть W₄=-W₀;

W₅=-W₁;

W₆=-W₂;

W₇=-W₃.

Тогда матрица F будет иметь вид

.

Используя двоичную инверсию (перестановку) строк,

(0,1,2,3,4,5,6,7) (0,4,2,6,1,5,3,7) будем иметь

=

= . (1.18)

В свою очередь, матрицы A₁¹ и B₁¹ можно представить в виде, где верхний индекс представляет собой номер шага процедуры БПФ

(1.19)

Подставляя выражения для A₁¹ и B₁¹ в (1.18) получим

;

;

;

. (1.20)

Наконец, на последнем шаге получим

(1.21)

Описанный алгоритм удобно представить графически (рис. 1.6).

Рис. 1.6. Граф-схема быстрой процедуры вычисления коэффициентов преобразования Фурье

Для определения степеней W на одном шаге необходимо выразить последовательность l=0, 1, 2, …, N/2-1 в виде (n-1) – разрядных двоичных последовательностей. В результате для N=16, к примеру, получим множество

S₁=(000,001,010,011,100,101,110,111).

Для получения S₂ необходимо выполнить двоичную инверсию каждой (n-1)-разрядной последовательности множества S₁, т.е.

S₂=(000,100,010,110,001,101,011,111),

и записать двоичную последовательность в виде десятичных чисел

S₃=(0,4,2,6,1,5,3,7),

и таким образом имеем W₀, W₄, W₂, W₆, W₁, W₅, W₃, W₇. (табл. 1.2).

Итерация r для БПФ состоит из 2^r-1 групп, где (N=2ⁿ). Для N=16, .

Таблица 1.2