Рис. 8.12. Характеристики некоторых алгоритмов разложения Нуссбаумера- Квенделла.

6 X 1

6x6 Циклическая свертка

Рис. 8.13. Разбиение (7Х 7)-преобразования Фурье.

Характеристики некоторых построенных таким способом двумерных алгоритмов выписаны на рис. 8.12. Если сравнить эти характеристики с приведенными на рис. 8.18 характеристиками, то можно увидеть, что для [р X /?)-точечных БПФ-алгоритмов данный способ проигрывает приведенному на рис. 8.18.

В качестве примера рассмотрим двумерное (7x7)-точечное преобразование Фурье. Как показано на рис. 8.13, оно распадается в вычисление двух 6-точечных циклических сверток и одной двумерной (6X6)-точечной циклической свертки. Для вычисления каждой 6-точечной циклической свертки необходимо восемь вещественных умножений. Алгоритм вычисления двумерной (6x6)-свертки можно строить гнездовым методом, сочетая алгоритм циклической (2х2)-свертки с алгоритмом циклической (3x3)-свертки, данным на рис. 7.9. Для такого вычисления необходимо 52 умножения, так что в общей сложности получаем 68 умножений. Еще одно, тривиальное, умножение (на 1) нужно для того, чтобы представить в том же виде вычисление компоненты У , ; это существенно при использовании данного (7х7)-БПФ-алгоритма в качестве составляющей в гнездовом методе построения больших БПФ-алгоритмов. .

Подсчет числа сложений несколько более громоздок, и результат зависит от того, насколько удачно организованы уравнения. Сначала рассмотрим уравнения в том виде, как они были выписаны выше. Тогда вычисления состоят из некоторых предсложений, предшествующих обращению к двум 6-точечным циклическим сверткам и одной (бхб)-точечной двумерной циклической свертке, и

следующих за этим постсложений. Некоторые предсложения и постсложения входят также и в алгоритмы сверток. Полное число сложений тогда вычисляется так;

Предсложения 84

Две 6-точечные циклические свертки 68

Циклическая (6 X 6)-свертка 424

Постсложения 84

Однако мы знаем, что если собрать вместе все предсложения, включая и те, которые входят в алгоритмы сверток, то возможно уменьшение числа сложений. Аналогичного уменьшения числа сложений можно добиться, собирая вместе все постсложения. Мы не можем сделать это в достаточно общем виде, поскольку нет никакой общей теории минимизации числа сложений и, что еще важнее, поскольку это не позволяет построить алгоритм, хорошо распадающийся на мелкие подпрограммы так, как рассматриваемый алгоритм. Тем не менее кое-что можно сделать. 6-точечные циклические свертки можно скомбинировать с некоторыми предсложе-ниями и постсложениями так, чтобы сформировать 7-точечные преобразования Фурье. Это не меняет числа необходимых умножений. Вычисления в так организованном алгоритме будут состоять из некоторых предсложений, одного 7-точечного преобразования Фурье, одной 6-точечной циклической свертки, одной двумерной (бхб)-свертки и некоторых постсложений. Полное число сложений уменьшается следующим образом:

Предсложения 78

7-точечное БПФ 36

6-точечная циклическая свертка 34

Циклическая (6Х 6)-свертка 424

Постсложения 78

650

Эго, конечно, небольшое улучшение.

В качестве второго примера рассмотрим двумерное (5x13)-преобразование Фурье. Как показано на рис. 8.14, разобьем его на 4-точечную циклическую свертку, 12-точечную циклическую свертку и двумерную циклическую (4Х 12)-свертку. Для вычисления двумерной циклической (4Х 12)-свертки преобразуем ее в трехмерную циклическую (4 X 4 X 3)-свертку и воспользуемся гнездовым алгоритмом, сочетающим алгоритм циклической (4x4)-свертки с алгоритмом 3-точечной циклической свертки; этот алгоритм содержит 88 вещественных умножений и 608 вещественных сложений. Присоединяя 4-точечную циклическую свертку и 12-точечную циклическую свертку (20 вещественных умножений и 100 вещественных сложений) и учитывая одно связанное с компонен-

4~ точечная циклическая -свертка

12-точечная циклическая свертка

Циклическая (4 к 12)~ свертка

-12-

Рис. 8.14. Разбиение (5Х13)-преобразования Фурье.

гой Vo, тривиальное умножение, получаем(5х 13)-БПФ-алгоритм, содержащий 114 вещественных умножений и 939 вещественных сложений.

(5х 13)-БПФ-алгоритм с несколько лучшими характеристиками получается, если подпрограмму 13-точечного БПФ с 20 нетривиальными вещественными умножениями и 94 вещественными сложениями использовать вместо 12-точечной циклической свертки; тогда число вещественных умножений равно 114, а число необходимых вещественных сложений равно 917.

Описанный метод пригоден и в том случае, когда числа точек по осям равны степеням простых чисел. Разбиения множеств индексов на подмножества даются теперь более сложными правилами. Например, рассмотрим задачу вычисления двумерного (7X9)-преобразования Фурье. Так как число 9 не является простым, то для построения алгоритма нужен более общий, чем рассмотренный выше, метод. Напомним, что обобщая в гл. 4 алгоритм Рейдера на случай вычисления 9-точечной свертки, мы выбросили все не взаимно простые с 9 индексы и свели задачу к вычислению 6-точечной циклической свертки и двух 2-точечных циклических сверток. Поступая так же и

5x2 i дважды]

Рис. 8.15. Разбиение (7X9)-преобразования Фурье.

теперь, мы получаем двумерную циклическую (бхб)-сверт-ку и две двумерные циклические (2х6)-свертки. Таким образом, как показано на рис. 8.15, двумерный (7x9)-БПФ-алгоритм строится из двумерной циклической (6x6)-свертки, двух двумерных циклических (6х2)-сверток, 9-точечного БПФ-алгоритма и 6-точечной циклической свертки. В общей сложности такой алгоритм требует 52 -Ь 2 х X 16 + 10 + 8 = 102 умноже-

Рис. 8.16. Разбиение двумерной (бхб)-свертки.

ний, но это число можно уменьшить, если более тщательно структурировать алгоритм. Мы не учли того факта, что 6-точечная свертка, получающаяся при преобразовании 9-точечного преобразования Фурье по алгоритму Рейдера, приводит к нескольким умножениям на нуль. Эти умножения, описываемые теоремой 4.6.2, можно не учитывать.

(бхб)-свертка возникает из двумерного аналога обобщенного алгоритма Рейдера. Для двумерного (7х9)-преобразования Фурье многочлен Рейдера от двух переменных равен

g{x, i/)=fi:(o> - 1)х] f Е (р - 1)/ 1/-0 J Lt-0

где О) - первообразный корень степени шесть из единицы, а р - первообразный корень степени девять из единицы.

Для построения алгоритма циклической (6 X 6)-свертки запишем

5 1 = + л: + 1) (х - 1) (х -Ь 1) (х - X -Ь 1), / - 1 = (у + + 1) (У - 1) (i/ + 1) ( - !/ + I), и вычислим вычеты многочлена g (х, у) по модулям, равным этим делителям. Как показано на рис. 8.16, эти вычисления можно разбить на 16 фрагментов. Согласно теореме 4.6.2, фрагменты, связанные с модулями (у - 1) и ((/ -Ь 1), приводят к равным нулю вычетам, и, следовательно, могут быть выброшены. В квадратах на рнс. 8.16 указаны числа умножений, необходимых при вычислении каждого фрагмента, причем в скобках приведено число умножений, необходимое в случае, когда вычет не равен нулю. Отсюда видно, что для вычисления циклической (бхб)-свертки требуется только 36 умножений, так что полное число умножений в алгоритме (7х9)-точечного БПФ равно 86.

Рис. 8.17. Характеристики улучшенного быстрого алгоритма преобразования Фурье.

алгоритма Винограда, а на самом деле даже хуже, так как содержит больше сложений.

Теперь рассмотрим 63-точечное преобразование Фурье. Большой БПФ-алгоритм Винограда содержит в этом случае 98 нетривиальных вещественных умножений и 704 вещественных сложений. Рассмотрим улучшенный БПФ-алгоритм, начинающийся сведением 63-точечного преобразования Фурье к двумерному (7х9)-преобра-зованию Фурье, для вычисления которого используется показанная на рис. 8.15 структура. Такой алгоритм содержит 85 нетривиальных вещественных умножений и 712 вещественных сложений.

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

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

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

8.6. Улучшенный алгоритм Винограда быстрого преобразования Фурье

Коль скоро задача вычисления одномерного преобразования Фурье с помощью алгоритма Гуда-Томаса сведена к задаче вычисления многомерного преобразования Фурье, то дальше можно ее решать сведением к многомерной свертке. Такой путь вычисления одномерного преобразования Фурье очень похож на большой БПФ-алгоритм Винограда, но с одним отличием. Напомним, что большой БПФ-алгоритм Винограда комбинирует два или больше малых БПФ-алгоритмов, но не меняет их структуру. Однако каждый из малых алгоритмов строится на основании быстрого алгоритма свертки, так что можно ожидать, что в большой задаче содержится многомерная свертка. Большой БПФ-алгоритм Винограда не пытается извлечь из многомерной свертки никакой пользы и он в конечном счете вычисляет ее, сочетая гнездовым способом два одномерных алгоритма. Если многомерная свертка достаточно велика, то характеристики можно улучшить, применяя для вычисления этой свертки более сильные алгоритмы. Характеристики ля-точечного улучшенного БПФ-алгоритма Винограда лучше, чем характеристики большого п(г -точечного БПФ-алгоритма Ви-кограда, если <р ( ) и (р ( ) имеют обший делитель, равный по меньшей мере четырем. Характеристики для некоторых таких алгоритмов приведены на рис. 8.17.

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

Рассмотрим сначала 15-точечное преобразование Фурье. Его можно трансформировать в двумерное (Зх 5)-точечное преобразование Фурье. Используя далее алгоритм Рейдера вдоль каждой оси, выделим двумерную циклическую (2х4)-свертку, записываемую в виде

S {х, у] = g {х, у) d {х, у] (modx-1) (глоА f - \).

Эта свертка так коротка, что наилучшим способом ее вычисления является гнездовое сочетание одномерных алгоритмов свертки. Для = 15 улучшенный БПФ-алгоритм не лучше большого БПФ-