7.1 Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота

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

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

Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на основе которых впоследствии возникло множество различных эффективных модификаций. Это: 1) обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота; 2) алгоритм простых множителей Гуда-Винограда; 3) алгоритм Винограда.

Для простоты изложения везде будем полагать N=N₁N₂, где N - длина преобразования. Очевидно, приводимые ниже положения легко могут быть перенесены на более общий случай, когда

Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота. Итак, пусть N=N₁N₂, гдеN₁ и N₂ - положительные целые. Покажем, что в этом случае вычисление исходного N-точечного ДПФ можно свести к вычислению N₁ N₂-точечных и N₂ N₁-точечных ДПФ и N умножениям на множители поворота . Для этого в выражения для ДПФ (1.1)

(7.1)

где , необходимо сделать подстановку:

k=k₁ +k₂N_2, k₁=0, …., N₂-1; k₂=0, …., N₁-1; (7.2)

n=n₁ +n₂N_2, n₁=0, …., N₂-1; n₂=0, …., N₂-1. (7.3)

Рисунок 6 - Сигнальный граф алгоритма

Тогда ДПФ (7.1) преобразуется к виду

(7.4)

Таким образом, полученный алгоритм включает в себя две основные ступени: на первой ступени переставленные в соответствии с (7.3) входные выборки подвергаются N₂-точечному преобразованию Фурье. На второй ступени производится вычисление N₁-точечных ДПФ. Между первой и второй ступенями осуществляется операция поворота путем умножения на поворачивающие множители . Полученная последовательность на выходе ДПФ должна быть переставлена в соответствии с (7.2).

Пример 4. Пусть N=6, N₁=3, N₂=2. Положим k=k₁+k₂*2; n=n₁+ +n₂*3; n₁k₂=0,1,2; n₂k₁=0, 1.

Тогда

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

Рассмотренный подход может быть положен в основу синтеза алгоритмов БПФ Кули-Тьюки с произвольным постоянным основанием. Наибольшую популярность получили алгоритмы с основаниями 4 и 8, позволяющие повысить эффективность вычисления ДПФ по сравнению с классическими алгоритмами по основанию 2. Отметим, что алгоритмы с основанием 2 также могут быть получены с использованием рассмотренного подхода. Таким образом, рассмотренный метод синтеза является общим и позволяет синтезировать различные модификации алгоритма Кули - Тьюки с произвольными постоянным и смешанным основаниями.