1.3.5. Алгоритмы БПФ для произвольного составного N

Алгоритм с множителями поворота.

Пусть где — любые положительные целые. В этом случае вычисление -точечного ДПФ можно свести к определению -точечных и -точечных ДПФ и умножениям на множители поворота Для этого в (1.19) необходимо сделать следующую подстановку:

где

Тогда (1.19) преобразуется к виду

Пример 1.8. Пусть Согласно (1.28) положим Тогда

Соответствующий направленный граф изображен на рис. 1.9.

Рис. 1.9

Алгоритмы БПФ с произвольным основанием.

Используя алгоритм с множителями поворота, можно получить алгоритмы БПФ с основаниями, отличными от 2. На практике наибольшее применение нашли алгоритмы с основаниями 4, 8 и 16, позволяющие значительно сократить число требуемых операций по сравнению с алгоритмами с основанием 2. В табл. 1.3 приведены выражения для

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

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

Пример Построить алгоритм -точечного ДПФ с основанием 4. Положим где Согласно (1.28) и

Построим алгоритм вычисления базового 4-точечного ДПФ

Положим

Подставляя (1.32) в (1.31), получаем

Направленный граф, соответствующий (1.33), изображен на рис. 1.10. Направ ленный граф 16-точечного ДПФ изображен на рис. 1.11.

Алгоритм взаимно-простых делителей.

Пусть где — взаимно-простые, т. е. а однозначное отображение между числами и парами определяется соотношениями:

Рис. 1.10

Пусть последовательность получается из последовательности перестановкой

а последовательность получается из последовательности ДПФ перестановкой

Числа определяются согласно китайской теореме об остатках .12] из уравнений:

Рис. 1.11

Запись означает; «наибольший общий делитель чисел

Запись означает «остаток от деления числа на число например

Тогда справедливо выражение

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

Пример 1.10. Рассмотрим случай Пусть Сеглаено (1.34) положим:

Из найдем: Получим элементы вектора из перестановкой (1.35)

и элементы выходного вектора из перестановкой (1.36)

Согласно (1.39)

Соответствующий направленный граф изображен на рис. 1.12.

Рис. 1.12

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