2015-01-30
544
В области спектрального (или гармонического) анализа используются прямое и обратное дискретное преобразование Фурье, а также вариант его рационального вычисления – быстрое преобразование Фурье:
где 
. Трудоемкость вычисления составляет порядка N 2 комплексных умножений и столько же комплексных сложений.
Выполним некоторые преобразования:
= 
Таким образом, вычисление N -точечного преобразования можно произвести путем вычисления двух N /2-точечных: B (k), k =0,2,4,6,…, N -1 и C (k), k =1,3,5,…, N -1.
Учитывая, что преобразование Фурье длиной N /2 элементов периодично с периодом N /2 точек, т.е. B (n) = B (n + N /2) и С (n) = С (n + N /2), получаем
, поскольку 
.
Таким образом
Трудоемкость вычислений преобразования теперь составит порядка 
комплексных умножений и в 2 раза больше комплексных сложений. Вычисление коэффициентов Wn осуществляется либо с использованием подпрограмм вычисления синуса и косинуса, либо табличным способом (чаще всего), либо каким-нибудь другим способом.
Аналогично, два N /2-точечных преобразования можно свести к четырем N /4-точечным и так далее. При этом сокращение объема вычислений составит (при N равном степени числа 2):
|
|
|
.
Порядок адресации элементов при выполнении, например, четырех 2-х точечных преобразования (при N =8) будет такой:
Представим адреса элементов в двоичном коде и переставим биты в обратном (реверсном) порядке:
| Прямой: | ||||||||
| Реверсный: | ||||||||
| Значение: |
Как видно из этого примера для эффективной реализации преобразования Фурье необходима аппаратная поддержка бит-реверсного режима адресации данных и возможности выполнения дуального сложения/вычитания..
