Известно, что количество операций умножения в дискретном преобразовании Фурье определяется как
Пусть количество отсчетов цифрового сигнала x(n) будет равно N. Тогда дискретное преобразование Фурье временной последовательности x(n) будет записываться следующим образом:
Для сокращения записи при преобразовании формул произведем замену переменной. Комплексную частоту e−jω заменим переменной W:
Теперь формула дискретного преобразования Фурье будет выглядеть следующим образом:
Запишем последовательность четных отсчетов сигнала x(n) в следующем виде:
Точно таким же образом запишем нечетные отсчеты входного сигнала:
Теперь выразим дискретное преобразование Фурье через дискретные преобразования Фурье четных и нечетных последовательностей входных отсчетов сигнала:
Раскроем скобки в степени коэффициента W:
В результате математических преобразований мы выяснили, что два ДПФ четных и нечетных временных отсчетов входного сигнала можно объединить в дискретное преобразование Фурье полной длины, если просуммировать частотные отсчеты четной последовательности с произведением частотных отсчетов нечетной последовательности входных сигналов на комплексную экспоненту WN. Количество операций умножения при этом значительно уменьшается по сравнению с прямым вычислением дискретного преобразования Фурье. Теперь обратим внимание, что отсчеты комплексной экспоненты WN симметричны относительно N/2. График комплексной экспоненты WN приведен на рисунке 1.
Рисунок 1. Графики реальной и мнимой составляющих комплексной экспоненты WN
По формуле Эйлера реальная составляющая комплексной экспоненты представляет собой cos(x), а мнимая составляющая — sin(x). На графике sin(x)
показан красным цветом, а cos(x) — синим, количество точек равно 10000. Из графика четко видно, что
Рисунок 2. Граф вычисления быстрого преобразования Фурье
Если количество отсчетов (точек) в исходных ДПФ будет снова четным числом, то их, в свою очередь, можно будет разбить на четные и нечетные последовательности временных отсчетов. Это снова позволит сократить количество операций комплексного умножения. Граф быстрого преобразования Фурье при этом примет вид, изображенный на рисунке 3.
Рисунок 3. Улучшенный граф вычисления быстрого преобразования Фурье
Для окончательного алгоритма 8-ми точечного быстрого преобразования Фурье с прореживанием по времени граф будет выглядеть, как это показано на рисунке 4.
Рисунок 4. Окончательный граф вычисления быстрого преобразования Фурье
Теперь оценим выигрыш полученного алгоритма быстрого преобразования Фурье с прореживанием по времени. Наибольший выигрыш получается для длины временной
последовательности
В качестве примера рассмотрим быстрое преобразование Фурье (БПФ) последовательности из 1024 отсчетов. Для прямого вычисления ДПФ нам бы потребовалось
N2 операций умножения. Это приблизитеьно 1 млн. операций. При быстром преобразовании Фурье нам потребуется
Теперь обратим внимание, что последовательность отсчетов сигнала на входе алгоритма быстрого преобразования Фурье не соответствует естественному течению времени. Ее следует переупорядочить. Для того, чтобы определить как следует переставить отсчеты воспользуемся двоичным представлением номера входного отсчета При перестановке младшие и старшие биты номера отсчета меняются местами. В качестве примера рассмотрим перестановку входных отсчетов 8-ми точечного БПФ. Соответствие входных номеров отсчетов сигнала и номеров на входе алгоритма БПФ приведено в таблице 1.
| Номер | Двоичное представление | Двоично-инверсная перестановка | Десятичное представление |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 100 | 4 |
| 2 | 010 | 010 | 2 |
| 3 | 011 | 110 | 6 |
| 4 | 100 | 001 | 1 |
| 5 | 101 | 101 | 5 |
| 6 | 110 | 011 | 3 |
| 7 | 111 | 111 | 7 |
Следует отметить, что в настоящее время быстрое преобразование Фурье обычно выполняется в сигнальных процессорах, а в них предусмотрен особый вид адресации — двоично-инверсный адрес. При этом старшие и младшие биты адреса меняются местами аппаратно, а реальная перестановка не производится. Это позволяет значительно сокращать время вычисления спектра входного сигнала. Не меньший выигрыш в быстродействии получается за счет применения умножителей-накопителей (MAC), а в современных сигнальных процессорах таких как SM320VC5510A фирмы Texas Instruments их применяется две штуки. Есть модели сигнальных процессоров, в которых применяется и большее количество MAC.
