- отсчеты спектральной плотности через интервал частоты
- число отсчетов.
Из (1) следует, что для определения одного спектрального коэффициента требуется умножений, вычислений экспонент и сложений, а на все коэффициентов требуется 2 умножений, сложений и вычислений экспонент. Алгоритм быстрого преобразования Фурье позволяет уменьшить число таких операций до
При = 210 = 1024 машинное время уменьшается в 100 раз.
Пусть = 2p (p - целое число). Разобьем последовательность (1) на сумму двух последовательностей, составленных из четных и нечетных номеров.
(2)
Однако вычисления по (2) можно ограничить номером , т. к. функции и являются периодическими с периодом из-за большего (в два раза) интервала отсчетов между ними. Итак, при будем иметь:
т.к.
Аналогично
. (3)
Теперь снова разобьем суммы и с четными и нечетными новыми номерами слагаемых:
;
= 0, 1, ..., 2P-2-1.
Далее суммы снова можно разбить. Получим:
= 0, 1, ..., 2P-3-1; для номеров +2P-3знаки перед экспонентами заменяют на минус.
остальным членам соответствуют следующие отсчеты sk:
k=0,1,...2P-3-1.
Таким образом, мы имеем все время удваивающееся число сумм X,Y для одного , однако число членов в этих суммах все время в два раза уменьшается и, кроме того, в два раза уменьшается число номеров , так что общее число сумм остается тем же, но уменьшается число членов в каждой сумме.
Продолжая такое разбиение l раз, будем иметь:
;
(4)
.
где (5)
l = 1, 2, ..., p; i = 1, 2, ..., 2l-2 в (4) и i = 1, 2, ..., 2l-1 в (5).
n = 0, 1, ..., 2P-l-1. При l = p получим = 0, k = 0.
i = 1, 2, ..., 2P-1.
Итак, можно предложить следующий алгоритм быстрого преобразования Фурье.
Задано = 2P отсчетов сигнала , i = 0, 1, 2, ..., -1, l = p, = 0