Чтобы построить двумерный БПФ-алгоритм по основанию 4 положим п = 4 и л = л/4. Это разобьет исходную двумерную таблицу на 16 подтаблиц. Вычисления можно записать в виде следующего матричного уравнения:

I Е

Е Е

(1 П I 1 м.,. ,. -J Е Е

* е е у -1 -J е е

е Е ч-.,. .

* I -* .=

е Е . .>..,. ....о. ./. Е Е

-о ,-0

1111 1-J 1 J 1-1 1-1

1 J -I -J

Здесь (16х 16)-матрица, на которую выполняется умножение, представлена в виде кронекеровского произведения двух (4x4)-матриц с элементами ±1 и ±/. 15/16 из стоящих в правой части равенства членов умножаются на степени элемента а>. Небольшая часть из них представляет собой тривиальные умножения, но, чтобы структура оставалась простой и удабной для расчетов, мы их выбрасывать не будем. Тогда число умножений описывается рекуррентным соотношением

М{п X п) = тм (- X г) + 4г

решением которого является

M(n X n) = -n(\ogn-C),

где константа С имеет такой же смысл, как и для алгоритма по основанию 2. Если выбрать внутреннюю свертку так, что М (4 X 4)=0,

Л1(л X n) = -i-n (logn-2),

и мы видим, что в добавление к хорошей структурированности алгоритм по основанию 4 эффективен в смысле числа необходимых умножений.

Для того, чтобы воспользоваться двумерным разбиением по основанию 4, локальная память должна быть столь большой, чтобы можно было одновременно записать четыре строки матрицы входных данных. В общей сложности таблица входных данных будет

переноситься log, п раз, так что всего потребуется -j-n logs л

переносов строк из глобальной памяти в локальную и наоборот.

8.2. Гнездовые алгоритмы преобразования

Теперь мы рассмотрим другой метод, известный под названием гнездового, в котором многомерные БПФ-алгоритмы строятся сочетанием одномерных БПФ-алгоритмов, как в БПФ-алгоритме Винограда. Напомним, что следствием возможности изменения порядка суммирования

Lr=o

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

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

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

М (п X л ) = п М (л) + пМ (л ),

А (л X л ) = пА (л) + пА (л ).

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

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

Пусть W и W обозначают соответственно матрицы преобразования Фурье длин л и л , так что V = Wv, V = Wv и

Vk = е р ;, VI- = Ё тч.

Двумерное (п X л)-преобразование Фурье двумерного сигнала о,-. 1- получается применением матрицы W к каждому столбцу (столбец содержит л компонент) и последующим применением матрицы W к каждой строке. Это двумерное вычисление можно преобразовать в одномерное так, как показано на рис. 8.2.

Выпишем двумерные таблицы v и V в виде одномерных таблиц, считывая их в стеки по столбцам, и сохраним за ними те же обоз-

1 -и--1

Рис. 8.2. Отображение двумерной таблицы в одномерную.

начения, так что входной и выходной одномерные векторы содержат лл компонент и имеют вид

где V[. и Vi- обозначают соответственно столбцы исходных двумерных таблиц:

Если под V и V понимать так построенные одномерные лл-точечные векторы, то двумерное преобразование Фурье записывается

В виде кронекеровского произведения. Сначала запишем вычисления в виде

<1

WOO. 0 W 0 0 0 w

где W - определенная выше {n X п)-матрица, О - нулевая (я X п)-матрица и I - единичная (я х л)-матрица. В этом произведении матриц легко узнать кронекеровское произведение матриц, так что в сокращенной записи имеем

V = Wv,

где W = W X-W представляет собой (яя X яя)-матрицу.

В БПФ-алгоритмах Винограда длин п и п соответственно матрицы W и W разлагаются в виде W = С ВА и W = С В А, где А, А , С и С представляют собой матрицы, состоящие только из нулей и единиц, а матрицы В и В являются диагональными. Все умножения в алгоритмах Винограда исчерпываются умножениями на матрицы В и В соответственно. Пусть W = W X W; применяя дважды теорему 2.5.5., получаем

W = (СВА ) X (СВА) = (С X С) (В X В) (А х А) = = СВА,

где кронекеровское произведение С = С X С и А = А X А приводит опять к матрицам, состоящим только из нулей и единиц, а кронекеровское произведение В = В X В представляет собой диагональную матрицу. Таким образом, мы построили алгоритм двумерного яя -гочечного преобразования Фурье в той же форме, что и БПФ-алгоритм Винограда. Это и дает способ построения двумерных БПФ-алгоритмов из одномерных алгоритмов.

Хороший способ организации вычисления двумерного преобразования Фурье диктуется формулой

V = (C X С) (В X В) (А X A)v,

и иллюстрируется рис. 8.3. Здесь предполагается, что данные записаны в виде двумерной таблицы. Для умножения на (А х X А) сначала каждый столбец входной двумерной таблицы умножается на матрицу А, а затем каждая строка полученной матрицы умножается на А . Первая из этих операций не содержит умножений и преобразует входную (я х я )-таблицу в таблицу раз-

я Умножение

я Умножение

временной области

М{п-)

М[п)

Хранимая таблица констант

я Умножение

Умножение

М(п )

N ПономпОнент -Jnoe умножение

М(п-)

Рис. 8.3. Гнездовой метод вычисления двумерного преобразования Фурье.

мера (М (я) X я )); вторая операция также содержит только сложения и преобразует данные в таблицу размера (М (л) х М(п )). Далее происходит умножение каждого столбца на матрицу В и затем умножение каждой строки на матрицу В . Эта процедура содержит 2М (я) М (л ) умножений. Другой способ реализации этого шага вычислений состоит в предварительном вычислении и запоминании [М (я) X М (я ))-матрицы В = В X В. Тогда на этом шаге потребуется только М (я) М (л ) умножений, но память для констант вычисления растет. Наконец, вычисленная на втором шаге (Л1 (л) X М (я ))-матрица преобразуется в (л X я )-матрицу умножением сначала каждого столбца на С, а затем каждой строки на С. Последний шаг содержит только сложения. Полное число умножений в алгоритме равно М (л X я ) = Ж(п)М (я ).

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