12.14. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

Суть этого алгоритма заключается в многократном членении заданной последовательности временных отсчетов на более короткие последовательности. Поясним достигаемый при этом выигрыш на примере одного первого разбиения.

Пусть задана последовательность отсчетов , причем число N является степенью двойки, т. е. , где — целое число. Разобьем эту последовательность на две подпоследовательности, как показано на рис. 12.36. Для первой из них, составленной из четно пронумерованных отсчетов (рис. 12.36, б), выражение, аналогичное (12.14), должно быть записано в форме

(12.76)

Здесь и в дальнейшем используется обозначение . Для второй (нечетной) подпоследовательности, составленной из отсчетов (рис. 12.36, б), ДПФ можно записать в форме

(12.77)

Рис. 12.36. Разбиение последовательности , на две последовательности: четных и нечетных отсчетов

Рис. 12.37. Спектры ДПФ последовательностей четных отсчетов (а), нечетных отсчетов (б) и исходной последовательности (в)

С учетом равенств

(12.78)

правые части выражений (12.76), (12.77) можно привести к виду

В этих, выражениях представляют собой ДПФ соответственно четной и нечетной подпоследовательностей.

Заменой на учитывается, что шаг дискретизации в вдвое больше, чем в исходной последовательности

Фазовый множитель перед второй суммой учитывает задержку последовательности на один интервал относительно последовательности (см. рис. 12.36).

На рис. 12.37, а и б представлен примерный вид спектров . В соответствии с числом временных отсчетов число спектральных коэффициентов также равно . Штриховыми линиями на рисунках показано периодическое продолжение спектра на участок .

Результирующее ДПФ исходной последовательности можно выразить через .

В диапазоне имеет место очевидное соотношение

В диапазоне можно, основываясь на периодичности (с периодом ), исходить из равенств

(12.79)

Кроме того, необходимо учитывать перемену знака перед фазовым множителем при :

поскольку .

В результате приходим к следующему выражению для ДПФ всей последовательности:

Спектр содержит N спектральных отсчетов на интервале одного периода (на оси ), как это представлено на рис. 12.37, в.

Заметим, что совпадают с соответствующими значениями .

Выяснив структуру спектров , подсчитаем число операций умножения, требующихся для получения N спектральных коэффициентов при использовании алгоритма (12.80). Для вычисления функций требуется умножений отсчетов на комплексные коэффициенты Кроме того, требуется N умножений на коэффициент . Всего требуется умножений, т. е. почти вдвое меньше, чем при использовании алгоритма (12.73).

Разбиением каждой подпоследовательности можно осуществить дальнейшее уменьшение объема вычислений. Разбиение следует продолжать вплоть до получения простейших, двухэлементных последовательностей. Определив ДПФ указанных простейших пар отсчетов, можно найти ДПФ четырехэлементных, восьмиэлементных и т. д. последовательностей. При объединении ДПФ двух подпоследовательностей можно руководствоваться алгоритмом (12.80), подставляя в него соответствующие значения

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

При обозначениях (12.80) базовая операция принимает вид, показанный на рис. 12.38, б. Основанный на этой базовой операции сигнальный граф объединения двух ДПФ представлен на рис. 12.38, в.

Проиллюстрируем описанный способ построения полного графа БПФ от двухточечных до точечных ДПФ на примере N = 8.

После первого разбиения последовательности получаются две четырехэлементные последовательности показанные в левой рис. 12.39. В первой из них четными считаются , а нечетными Поэтому последовательность распадается на две пары: .

Аналогично последовательность распадается на две пары: .

Рис. 12.38. Базовые операции, используемые в алгоритме БПФ

Рис. 12.39. Сигнальный граф БПФ при N=8

Определим ДПФ двухэлементных последовательностей. Для пары ,

откуда

Как видим, для вычисления и не требуется умножений. Нужно лишь образовать сумму и разность , т. е. и .

На рис. 12.39 для операции сложение-вычитание использована символика, совпадающая с операцией «бабочка» при верхний вывод соответствует сумме, а нижний — разности.

Аналогичным образом на рис. 12.39 обозначены ДПФ остальных пар: .

Следующий шаг объединение ДПФ . Число спектральных коэффициентов в суммарном ДПФ равно .

По аналогии с (12.80) можем написать

Учитывая, что переписываем последнее выражение в форме

Итак,

Аналогичные выражения нетрудно составить для ДПФ объединяющего ДПФ см. Базовые операции для одинаковы (см. рис. 12.39).

Для определения ДПФ всей последовательности из восьми отсчетов нужно воспользоваться выражением (12.80) и графом, представленным на рис. 12.38, в при .

Базовые операций, соответствующие приведенным соотношениям, показаны в правой части графа на рис. 12.39.

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

Итак, при использовании алгоритма БПФ для вычисления ДПФ N-точечной последовательности требуется примерно N log2N операций умножения.

Ранее было показано, что при прямом вычислении ДПФ по выражению (12.73) требуется умножений. Следовательно, алгоритм БПФ уменьшает число операций в . При . Столь большое сокращение числа операций резко уменьшает объем аппаратуры и повышает быстродействие цифровых устройств. Из рассмотрения графа следует, что экономия достигается благодаря объединению всех слагаемых, подлежащих умножению на однаковые множители.

К обоснованию алгоритма БПФ можно также прийти, используя метод факторизации матрицы, описывающей дискретное преобразование (12.73) 121).

Для большей наглядности все предыдущее рассмотрение проводилось в предположении действительного (вещественного) сигнала. Однако результаты можно распространить и на комплексный сигнал.

На с. 390 приведена программа вычисления прямого и обратного преобразований Фурье как для действительного, так и комплексного сигнала с базой до 512.

Существует большое разнообразие вариантов построения схем БПФ.