1.3.4. Алгоритмы БПФ с основанием 2

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

Алгоритмы с основанием 2 используются при — целое. Основная идея, лежащая в их основе, заключается в сведении вычисления исходного -точечного ДПФ к вычислению нескольких точечных ДПФ, причем Алгоритмы, при реализации которых требуется перестановка отсчетов входной последовательности (см. пример 1.6), называются алгоритмами с прореживанием по времени. Алгоритмы, при реализации которых требуется перестановка отсчетов выходной последовательности см. пример 1.7), называются алгоритмами с прореживанием по частоте. По эффективности эти две разновидности алгоритмов эквивалентны и позволяют уменьшить число требуемых арифметических операций примерно в раз по сравнению с прямым методом вычисления ДПФ.

Алгоритм с прореживанием по времени. Если последовательности длиной разделить на две -точечные последовательности, состоящие из с четными и нечетными номерами соответственно, то выражение для ДПФ (1.19) можно записать в виде

Какдая из сумм в (1.24) является -точечным ДПФ, которое аналогичным образом можно представить через -точечные, а -точечные через -точбчиые и т. д., пока не останутся только -точечные. Таких ступеней пре» образования всего На производится пре образование множества комплексных чисел в множество комплексных чисел в соответствии с базовой операцией «бабочка», описываемой выражениями:

где зависят от номера ступени от и могут быть определены из выражений, аналогичных (1.24).

Входная последовательность нулевой ступени получается перестановкой последовательности в соответствии с двоичной инверсией и ров, т. е. число с номером в двоичном представлении запоминается на месте

Направленный граф, реализующий «бабочку», изображен на рис. 1.5. Здесь сигналы ветвей, входящих в узел, суммируются; сигнал ветви умножается на коэффициент, записанный рядом с ветвью. Если коэффициент не указан, то он полагается равным 1.

Рис. 1.5

Пример 1.6. Рассмотрим случай Так как то . Для получения входного массива произведем двоично-инверсную перестановку элементов последовательности

Направленный граф с использованием «бабочки» и выражения (1.24) изображен на рис. 1.6.

Алгоритм с прореживанием по частоте. Исходная последовательность разбивается на две подпоследовательности где и отдельно вычисляются четные и нечетные отсчеты ДПФ:

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

Рис. 1.6

На ступени производится преобразование множества комплексных чисел в множество комплексных чисел в соответствии с базовой операцией «бабочка», описываемой выражениями:

где для каждой ступени определяются из выражений, аналогичных . Направленный граф операции

«бабочка» изображен на рис. 1.7.

Рис. 1.7.

В рассматриваемом алгоритме, в отличие от алгоритма с прореживанием по времени, в двоично-инверсионном порядке располагается не входная, а выходная последовательность

Рис. 1.8

Пример 1.7. Рассмотрим случай Направленный граф -точечного, ДПФ с использованием операции «бабочка» и выражения (1.26) изображен рис. 1.8.

Алгоритмы с прореживанием по времени и по частоте являются дуальными: каждый из них может быть получен из другого путем взаимной замены входа и выхода и обращения направления всех стрелок в направленном графе (см. рис. 1.6 и 1.8).

ФОРТРАН — программа, реализующая алгоритм БПФ с основанием 2 при прореживании по времени, приведена в [1.6]. В пакете прикладных программ ЕС ЭВМ имеется подпрограмма которая также реализует алгоритм БПФ.