7. АЛГОРИТМЫ БПФ РАЗМЕРНОСТИ N=2^n

В данной главе отдельно рассматриваются методы построения и характеристики алгоритмов БПФ для случая Необходимость отдельного рассмотрения алгоритмов БПФ данного класса обусловлена их большим разнообразием. Это связано с весьма большой популярностью алгоритмов в практике спектрального анализа и цифровой фильтрации сигналов.

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

7.1. Алгоритмы БПФ по основаниям 2, 4, 8 и 16

Структуры алгоритмов БПФ по основанию 2 непосредственно следуют из выражений при подстановке Наиболее подробная классификация различных вариантов таких алгоритмов приведена в обзоре

Рассмотрим некоторые примеры построения структур алгоритмов БПФ по основанию 2 для случая

1. БПФ с замещением, прямым входом и двоично-инверсным выходом (прореживанием по частоте). рис. 7.1

где

2. БПФ с замещением, двоично-инверсным входом и прямым выходом (прореживание по времени), рис. 7.2

3. БПФ с постоянной структурой и прореживанием по частоте, рис. 7.3

Рис. 7.1. Алгоритм БПФ по основанию 2 с замещением и прореживанием по частоте

Рис. 7.2. Алгоритм БПФ по основанию 2 с замещением и прореживанием по времени

Вычислительная эффективность приведенных алгоритмов одинакова. Конкретные оценки числа нетривиальных арифметических операций равны (табл. 7.1)

Рассмотрим теперь алгоритмы БПФ по основанию 4. Пусть тогда при четном и при и нечетном Обозначим через ближайшее меньшее целое к т.е. Тогда

Таблица 7.1 (см. скан)

Рис. 7.3. Алгоритм БПФ по основанию 2 с постоянной структурой и прореживанием по частоте

Рис. 7.4. Алгоритм БПФ по основанию 4 с замещением и прореживанием по частоте Отсюда алгоритм БПФ для данного случая согласно (6.1) имеет вид

где

Рис. 7.5. Алгоритм БПФ по осночанию 4 с постоянной структурой и прореживанием по частоте

На рис. 7.4 показан граф алгоритма (7.1) при . В этом случае

Приведем выражение алгоритма БПФ по основанию 4 с постоянной структурой. Это возможно только в случае, когда постоянная структура вычислений не сохраняется)

На рис. 7.5 построен граф алгоритма БПФ (7.2) при . В этом случае

где

Оценки числа нетривиальных арифметических операций для алгоритмов БПФ данного класса приведены табл. 7.1. Из таблщы следует, что алгоритмы БПФ по основанию числу арифметических операций примерно на экономичнее, чем алгоритмы БПФ по сснованиы 2.

Алгоритмы БПФ по основанию 8 или 16 используются для дальнейшего повышения вычислительной эффективности [2]. Для таких алгоритмов наиболее оптимальным будет представление модулей или в канонической форме (4.13) [3]. Например, для

Число арифметических операций алгоритмов БПФ по основаниям 8 и 16 приведено в табл. 7.1.