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

Рассмотрим дискретное прямое преобразование Фурье.

, (1)

= 0, 1,..., -1; k = 0, 1,..., -1; j -мнимая единица.

- отсчеты сигнала через интервал времени

- отсчеты спектральной плотности через интервал частоты

- число отсчетов.

Из (1) следует, что для определения одного спектрального коэффициента требуется умножений, вычислений экспонент и сложений, а на все коэффициентов требуется ² умножений, сложений и вычислений экспонент. Алгоритм быстрого преобразования Фурье позволяет уменьшить число таких операций до

При = 2¹⁰ = 1024 машинное время уменьшается в 100 раз.

Пусть = 2^p (p - целое число). Разобьем последовательность (1) на сумму двух последовательностей, составленных из четных и нечетных номеров.

(2)

Однако вычисления по (2) можно ограничить номером , т. к. функции и являются периодическими с периодом из-за большего (в два раза) интервала отсчетов между ними. Итак, при будем иметь:

т.к.

Аналогично

. (3)

Теперь снова разобьем суммы и с четными и нечетными новыми номерами слагаемых:

;

= 0, 1,..., 2^P-2-1.

Далее суммы снова можно разбить. Получим:

= 0, 1,..., 2^P-3-1; для номеров +2^P-3 знаки перед экспонентами заменяют на минус.

остальным членам соответствуют следующие отсчеты s_k:

k=0,1,...2^P-3-1.

Таким образом, мы имеем все время удваивающееся число сумм X,Y для одного, однако число членов в этих суммах все время в два раза уменьшается и, кроме того, в два раза уменьшается число номеров, так что общее число сумм остается тем же, но уменьшается число членов в каждой сумме.

Продолжая такое разбиение l раз, будем иметь:

;

(4)

.

где (5)

l = 1, 2,..., p; i = 1, 2,..., 2^l-2 в (4) и i = 1, 2,..., 2^l-1 в (5).

n = 0, 1,..., 2^P-l-1. При l = p получим = 0, k = 0.

i = 1, 2,..., 2^P-1.

Итак, можно предложить следующий алгоритм быстрого преобразования Фурье.

Задано = 2^P отсчетов сигнала , i = 0, 1, 2,..., -1, l = p, = 0

for i = 1 to N/2 , end.

* for n = 0 to n = 2^P-l-1.

for i = 1 to i = 2^l-2.

end, end.

l=l-1, if l>1 go to *, else for n=0 to .

, end.