Степень простого числа

рЗ-точечное преобразо- р + р

вание по модулю (Р* - - 1)

р-точечное преобразование по модулю

р-точечное преобразование по модулю (к~\)Кх~Х)

ваний

преобразо-длины р

2р* + р* - Ьр + + р=+ 6

р + 1 преобразований* длины р

Степень 2 -точечное преобразо-двойки 2 * вание по модулю

(3/2) 2 преобразо. ваний** длины 2

iZm + 5) 2

2 -точечное преобра- Одно двумерное зованне по модулю преобразование раз-

2т.~\

мера 2 - хг -

Из которых р выколоты. * Из которых все выколоты.

Рис. 8.2i. Подпрограммы, используемые в БПФ-алгоритмах Нуссбаумера- Квенделла.

стого числа и степени двух. Рассмотрим последовательно все три случая; результаты анализа подытожены на рис. 8.21.

Число г точек в каждом измерении просто. При простом числе точек теоремой можно воспользоваться для того, чтобы свести вычисление двумерного (р X р)-преобразования Фурье к р + I различным одномерным преобразованиям Фурье. В более общем случае метод позволяет свести Л-мерное, р-точечное по каждому измерению преобразование Фурье к (р* - 1)/(р - 1) различным одномерным р-точечиым преобразованиям Фурье. Это можно сравнить с прямым методом вычисления Л?-мерного р-точечного по каждому измерению преобразования Фурье, содержащим Np - различных одномерных р-точечных преобразований Фурье.

Для простых р нмеет место разложение

х - 1 = (х - 1) (х -! + х - -I- ...-(- X 4- 1).

Полииомиальнае преобразование

£-0

р преобразований Фурье

, р-г ,

к., . £ .....Р-

Переиндексация

Выход

Рис 8 22 Перестановочный алгоритм Нуссбаумера-Квенделла.

вхоа

Выколотое преобразование Фурье где и = I, п - р

Нормальное БПФ Винограда

Выколотое БПФ Винограда

Рис. 8.23. Характеристики некоторых выколотых БПФ-алгорктмов.

поненты Vk, к с k , равным нулю. Но они получаются сразу как результат еще одного преобразования Фурье: р-\ р-1 V(,-.o= Е <й Е Ог,<-. fe = 0.....р-1.

Таким образом, всего получаем р + 1 одномерных преобразований Фурье длины На рис. 8.22 приведена блок-схема алгоритма для простого р. На последнем шаге осуществляется обратная перестановка компонент, для чего используется обращение к по модулю р.

Есть еще одно упрощение. У большинства преобразований Фурье некоторые коэффициенты отсутствуют, так что соответствующие преобразования можно упростить с помощью выкалывания - выбрасывая те входные компоненты, которые заведомо равны нулю, и те выходные компоненты, вычислять которые нет надобности. Как видно из блок-схемы на рис. 8.22, в основном шаге алгоритма, связанном с вычислением р-точечных преобразований Фурье векторов длины р - 1, коэффициент старшего порядка всегда равен нулю и нужны только р - 1 выходных компонент, а младший коэффициент можно отбросить. Такие выколотые БПФ-алгоритмы и их вычислительные характеристики представлены на рис. 8.23.

R качестве примера БПФ-алгоритма Нуссбаумера-Квенделла остроГпр меГ зхЗ)-БПФ-алг;ритма. Первый фрагмент вы-писывается проще всего:

л 1 1

0,1 + 1.1

10.! + 1,!

+ 2,0 + 21

Теперь заметим, что круговой многочлен равен Q (х) = х -f- х -(-Ч- 1 = (х= - 1)/(х - I) и

о (х) = Чг.оХ + i.oX -)- 0,0, (х) = j,iX= + a iX + u ,i, г (x) = и2,гХ + Ui.jX -I- 0 ,j. Вычисление полиномиального преобразования по модулю х -f--Ь X -Н 1 приводит к многочленам первой степени. Хотя приведение по модулю Q (х) можно и отложить, мы сразу заменим исходные многочлены их вычетами по модулю Q (х):

о (х) = (fi,o - Иг,о) X -f (i> , - ц ),

l (Х) = ( 1,1 - X + (y ,i - 4j,i),

Dj (x) = (Уг - X -f (i; ,j - yj.j). Полиномиальное преобразование равно

Ги;.(х)1

l-i(x)

1 ,u.*i]

лI li М

(mod

Это равенство можно переписать в виде

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

= 1 1

нужны ТОЛЬКО выколотые преобразования Фурье

при А - о, 1,2. Соединяя их вместе, получаем

Теперь надо выполнить обратную перестановку

компонент:

Наконец, собирая вместе все фрагменты, получаем окончательную форму алгоритма, показанную на рис. 8.24.

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

х - 1 = (х -~ 1) (X - + х - -1- ... -t- X + 1) (х с-ч +

4- х (0-=) + ... + х + 1) = (3, (X) (X) Qp. (X) на круговые многочлены. Индексы к разбиваются на три подмножества, соответствующие трем множествам сопряженных элементов, на которые корни из единицы, ш*, разделяются круговыми многочленами. Воспользуемся теоремой 8.7.1 для обработки компонент, индексы которых входят в множество сопряженных эле-

ментов, соответствующее многочлену Qp (х). Это потребует выполнения одного полиномиального пре: образования р членов по модулю Qp. (х) и р выколотых р-то-чечных преобразований Фурье.

Для завершения этого фрагмента вычислений надо найти компоненты Vf, s- с индексами к , кратными р. Эти компоненты задаются равенствами

Ir.ip°£ш- сг,с,

* = о.....- 1,

/ = 0, .... р- 1.

Внутреннюю сумму можно трансформировать в р-точечное преобразование Фурье. Обозначим через у = ш корень степени р из единицы; пусть

Ol-,r= S С(-,.+(р,

( = 0 р- 1,

г = 0.....Р-1,

и пусть Vf.i = Vf,ip. Тогда р-1 р-1

t=i r=0

fe = 0, .... 1, / =0, ;j- Ь

Теперь поменяем порядок суммирования и опять применим теорему 8.7.1. Для этого нам потребуется еще одно полиномиальное преобразование р членов по модулю Qpi {х) и еще р выколотых р-точечных преобразований Фурье. Остающееся при этом

- с о о о о с -S о о о о - о I

3 о о о о о о I