Для комплексных входных дан

: все цифры удваиваются

Рис. 8.18. Характеристики БПФ-алгоритмов Нуссбаумера-Квенделла.

Размер массива пХпХп

Нетривиальн умножений точку на вых1

Сложений на точку на выходе

Рис, 8.19. Характеристики трехмерных БПФ-алгоритмов Нуссбаумера-Квенделла.

сложения перед всеми умножениями и все умножения перед всеми постсложениями. Такой гнездовой метод построения алгоритма вычисления {пп х пп )-преобразования Фурье содержит М {пп X пп ) = М {п X п) М {п X п )

умножений. Число тривиальных умножений описывается равенством такого же типа; число сложений в алгоритме равно А {пп X пп ) = {nYA {п X п ) + М (я х я ) А (я X я).

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

10 Блейхут р.

опять переворачиваем всю постановку задачи и используем полиномиальное преобразование для вычисления преобразования Фурье, хотя и не того самого, которое первоначально привело нас к определению полиномиального преобразования.

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

Алгоритм Нуссбаумера - Квенделла является алгоритмом вычисления многомерного преобразования Фурье в случае, когда число точек во всех измерениях равно одному и тому же числу п, которое либо просто, либо равно степени простого числа. Конструкции различны для трех случаев: п - простое число; п равно степени нечетного простого числа; п равно степени двойки, п = = 2 . Гнездовой метод позволяет из этих алгоритмов строить большие многомерные преобразования точно таким же образом, как это делается в случае одномерного преобразования Фурье. Например, для построения (бЗхбЗ)-преобразования Фурье сначала оно отображается в четырехмерное ((7x9) X (7х9))-преоб-разование, которое затем рассматривается как ((7x7) X (9x9))-преобразование, для вычисления которого используется гнездовой метод сочетания (7х7)-алгоритма с (9х9)-алгоритмом. Это приводит к 49-кратному применению двумерного (9х9)-преобразова-ния Фурье к 49 подтаблицам данных, за которым следует 81-кратное применение двумерного (7х7)-преобразования Фурье к 81 подтаблицам данных. Все алгоритмы могут быть приведены в стандартную форму в виде матрицы предсложений при условии, что каждая из (7 X 7)-подтаблиц сформирована как 49-компонентный вектор и каждая из (9х9)-подтаблиц сформирована как 81-компо-нентный вектор. (Все описанные манипуляции с входной (63x63)-таблицей относятся только к индексам. Они не содержат арифметических вычислений и не требуют никакой физической перестановки данных.) Далее, так же как и для одномерного случая, можно использовать теорему о кронекеровском произведении матриц для приведения вычислений к стандартному виду, выделяя все пред-

Размер массива

Веществен женнй

Нетривиальных умножений на точку на выходе

Сложений на точку на выходе

128 278 584

1 112

2 014 2 648 6 824 9 336

17 816 37 400 84 728 290 144 436 760

1 160 600

2 074 712

1 152

2 889 7 499

13 356 30 240 29 592 102 460 123 784 276 696 658 584 I 344 456 5 765 760 8 1 76 792 24 738 840 40 133 656 298 481 560

Для комплексвь)% давят ,св цифры удааиваюгея

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

Изучаемые в настоящем разделе алгоритмы строятся сведением двумерного {р X р)-прео6разования Фурье к вычислению {р + 1) одномерных р-точечных преобразований Фурье для случая, когда число р простое. Для иллюстрации структуры, с которой мы будем работать, рассмотрим пример двумерного (ЗхЗ)-преобразования Фурье. Если записать входную и выходную (ЗхЗ)-таблииы по столбцам в виде векторов с 9 компонентами, то рассматриваемое (3 X 3)-прео6раование запишется в виде

I 1 1

1 и: U

где разделение на подматрицы сделано для того, чтобы выявить структуру кронекеровского произведения. Кратко это равенство записывается в виде V = Wv, где v и V обозначают выписанные выше входной и выходной векторы соответственно, а элементы матрицы W равны степеням элемента т. Нашей целью является по-

где незаполненным блокам соответствуют нулевые (ЗхЗ)-матрицы.

Разложение W = СВА замечательно похоже на запись малого БПФ-алгоритма Винограда. Сейчас, однако, мы находимся на совершенно ином уровне: стоящая в центре разложения блочно-диагональная матрица представляет собой пакет одномерных преобразований Фурье, а не пакет умножений. Коль скоро такое разложение уже получено, двумерное (ЗхЗ)-преобразование Фурье вычисляется последовательным выполнением предсложений, задаваемых матрицей А, четырехкратным обращением к 3-точечному одномерному БПФ и выполнением постсложений, задаваемых матрицей С. Как мы увидим позже, для некоторых одномерных преобразований Фурье надо вычислять не все члены; эта обсуждаемая дальше процедура названа выколотыми БПФ-алгоритмами и позволяет еще немного уменьшить вычислительную нагрузку.

Одномерное преобразование Фурье можно трактовать как процесс вычисления значений многочлена v (х) в точках со:

= и (ш*), = О, л - 1,

;i-1

v{x)Yi ViX,

Эта же трактовка применима и к двумерному преобразованию Фурье, причем более плодотворным оказалось использование такого описания только вдоль одного из измерений двумерного преобразования. Запишем (п Х п)-таблицу в виде вектора длины п, компонентами которого являются многочлены

Vi {Х) = £ Ус. i-X, Г = О, .... Л - 1.

строение разложения W = СВА, где А и С представляют собой соответственно матрицы предсложений и постсложений, а матрица В задает набор одномерных преобразований Фурье. В данном примере матрица В имеет вид

1 I I

Определим одномерное преобразование Фурье вектора многочленов равенствами

Vr (х) == Ё W-Or (х), Г = О.....п-1.

Тогда двумерное преобразование Фурье запишется в виде

fe =0, п-1, Vr. г = IV*. (X)) = V*. (<. ), , Q.....

В этом определении оси двумерного преобразования Фурье неравноправны и играют разную роль.

Теперь у нас уже все готово для того, чтобы, используя некоторую разумную технику перестановок, начать переход от преобразования Фурье к полиномиальному преобразованию. Пусть г обозначает некоторое положительное целое число, взаимно простое с п. Пусть k - {{kr))n для некоторого k из множества 0, п- \\. Это задает неявный способ перебора всех значений индекса k , так как в силу взаимной простоты гид, когда k пробегает все значения от О до п - 1, число k также пробегает все значения отО до л - I. Тогда, так как порядок элемента (о равен п, fk (kr дда предыдущие равенства можно для любого г, взаимно простого с п, переписать в виде

k =0, .... n- 1, V*., (,., = , *. I V t, (X)], n-1.

Если k само взаимно просто с n, то можно положить г равным к и тогда второе равенство принимает вид

к = 0.....л- 1.

V -, (, ), = lVutk- (х)1, д J

Каждая компонента выходной таблицы, первый индекс которой взаимно прост с л, может быть записана таким образом.

Завершив на этом вводную часть, переходим к построению полиномиального преобразования. Следующая теорема представляет собой скачок прямо к окончательному результату. Читая эту теорему, необходимо иметь в виду, что все те к, которые относятся к одному и тому же круговому многочлену, требуют одних и тех же вычислений, что один и тот же индекс к используется и в качестве выходного индекса, и для формирования перестановки, и что деление на к определено, так как и п взаимно просты.

Теорема 8.7.1. Пусть к - фиксированное целое число, взаимно простое с п. Пусть Q (х) обозначает круговой многочлен, корнем

которого является элемент ш*. Тогда вычисление компонент l/f. f для к - О, п - 1 может быть реализовано в виде следуюш,их трех шагов: (I) вычислить полиномиальное преобразование

Vi (х) = Е V,. (X) х (mod Q (х)), к = 0.....п-1;

/--о

(2) вычислить п преобразований Фурье

-г к-: ПОД(к\ л)=1, П.,. = Да>У .....

(3) сделать перестановку

к: НОЩк, n)=i, V*..*. = У*.,г = 0, л-1. Доказательство. Рассмотрим равенства

V - (X) = S r i.x). Vf. (( = lV M-i) (x)l.

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

V .*,) М - Е г {x) (шой q (x)),

V.., (, . = R.k iv K. (X)) = 1о*у;., . .

Но теперь, согласно второму равенству, элемент ш* сравним с х. Поэтому замена oj* на х в первом равенстве не приведет к изменению окончательного результата. Это позволяет еще раз переписать исходные равенства в виде

Ушк-,) (X) = Е (X) X-* (mod Q (х)), V.., ,( . = [Vш (х)1 = Е <йТг. ,( .

Теперь для завершения доказательства теоремы остается уточ-нить обозначения и переписать равенства в окончательном виде. □ Эту теорему надо применить к трем различным случаям, соответствующим равенству числа точек по каждой размерности двумерного преобразования простому числу, степени нечетного про-