г. Записать произведение кватернионов s = gd в виде произведения (4Х4)-матрицы на вектор, содержащий 4 компоненты. Дать алгоритм, содержащий девять умножений.

7.8. Определить число умножений и число сложений в алгоритме Агарвала - Кули для вычисления 45-точечной циклической свертки. Какое улучшение дает переход к алгоритму разложения)

7.9. а. Найти характеристики гнездового алгоритма вычисления циклической (15Х 15)-свертки, сочетающего алгоритм циклической {ЗХЗ)-свертки с алгоритмом циклической (5Х5)-свертки. Сравнить эти характеристики с характеристиками гнездового алгоритма, сочетающего алгоритм 15-точечной одномерной циклической свертки с ним самим.

б. Повторить вычисления для двумерной циклической (21Х2[)-свертки.

7.10. Для вычисления циклической (пХп)-свертки комплексных векторов можно попросту воспользоваться алгоритмом вычисления циклической (лХп)-свертки вещественных векторов, заменив все вещественные умножения и сложения на комплексные умножения и сложения. На сколько можно улучшить алгоритм вычисления циклической (5Х 5)-свертки комплексных векторов? Насколько лучше циклическая {4Х4)-свертка комплексных векторов?

Замечания

На простейшем уровне конструкций двумерное преобразование Фурье состоит из двух независимых преобразований Фурье, применяемых отдельно вдоль каждой из осей; аналогичное утверждение относится к двумерной свертке. Следовательно, быстрые алгоритмы вычисления одномерной свертки в равной мере применимы и для вычисления двумерной свертки. Являющиеся по существу двумерными алгоритмы возникли позже. Пионером в этой области явился Нусс-баумер [11 (1977), введя свои полиномиальные преобразования. Они были сначала определены эвристически по аналогии с преобразованиями Фурье, поскольку эти преобразования и представляли интерес. Только позже стало понятно, что полиномиальные преобразования представляют нечто большее, чем просто аналогию преобразованиям Фурье. Их интерпретация в виде преобразования Фурье в полиномиальном представлении расширений полей была дана Блейхутом [2] (1983). Аналогичные идеи былн высказаны Бетом, Фуми и Мах-вельдом [3] (1982). Другое полиномиальное преобразование, с более ясной структурой, но с большей сложностью вычислений, введено АрамбеполоЙ и Рай-нером [4] (1979).

Использование индексации типа Гуда - Томаса для вычисления одномерных сверток принадлежит Агарвалу и Кули [5] (1977). Они преобразовали одномерную светку в многомерную и для вычисления последней применили гнездовой алгоритм, сочетающий одномерные алгоритмы, - процедура, описанная нами в терминах кронекеровского произведения. Их гнездовой метод совпадает с предложенным Виноградом [8] (1978) для вычисления многомерных преобразований Фурье.

Идея использования для уменьшения числа сложений при вычислении многомерной свертки китайской теоремы об остатках для многочленов принадлежит Нуссбэумеру [6] (1978). Использовать в качестве модулей многочлены с коэффициентами в полиномиальных расширениях полей было предложено Питасом и Стринэисом [7] (1982). Многие нз приведенных в главе таблиц основаны на работе Нуссбаумера.

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

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

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

8.1. Алгоритмы Кули-Тьюки по малому основанию

Для вычисления двумерного преобразования Фурье можно использовать БПФ-алгоритм Кули-Тьюки, применяя его сначала к каждой строке, а потом к каждому столбцу. Это обосновывается простой расстановкой сМок в уравнениях, определяющих двумерное преобразование Фурье. Обозначим через v двумерную таблицу с элементами v с, / = О, .... п - 1, / = О, п - 1, из поля F. Двумерное преобразование Фурье таблицы v

БЫСТРЫЕ АЛГОРИТМЫ МНОГОМЕРНЫХ ПРЕОБРАЗОВАНИЙ

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

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

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

Для того, чтобы избежать операции транспонирования, посмотрим более внимательно на используемые в алгоритме Кули- Тьюки правила разбиения и применим их к построению много-

Одномерная

По основанию два

Двумерная

одномерная

По основанию четыре Двумерная

Рис. 8.1. Некоторые схемы прореживания.

мерных алгоритмов БПФ. В многомерных алгоритмах будем делать разбиения не по строкам и столбцам, а прямо разбивая двумерную таблицу. Различие этих способов разбиения показано на рис, 8.1. В частности, двумерное разбиение по основанию 2 разбивает (яхп)-таблицу на четыре ((п/2)X( /2))-таблицы, а двумерное разбиение по основанию 4 разбивает (пХ л)-таблицу на шест-надцать ((л/4) X (п/4))-таблиц. Последнее разбиение, в частности, привлекательно не только тем, что преобразует данные к малым объемам, но также и тем, что позволяет уменьшить число необходимых умножений и сложений.

Рассмотрим задачу вычисления двумерного (пхп)-точечного преобразования Фурье

П = е ЕлЧ,;.

=0 /=0

определяется как двумерная таблица V с элементами из поля F, вычисляемыми по формулам

А =0.....л - 1,

(=0 (=0 = и, ..., л - 1,

где ш - первообразный корень степени п из единицы в поле F, а ц - первообразный корень степени п из единицы в поле F; при п = я обычно полагают m = р. Ясно, что

где л - л л . Отметим, что мы специально убрали штрихованные обозначения индексов, чтобы воспользоваться разбиением Кули- 1ькжи. Теперь л и л- размеры прямоугольной таблицы. Тьюки 5 ° 4.1 формулу разбиения Кули-

n-l * Г Л -1

(=0

Применим эту формулу к двумерному преобразованию дважды - один раз к строчным индексам, а другой раз к столбцовым индексам, Югда, меняя порядок суммирования, можно записать

1-=0 /--о

Теперь мы получили запись преобразования в виде двумерного (Л Хл )-точечного преобразования для каждых Г и /, за которым следует покомпонентное умножение, а за ним (лх л)-точечное двумерное преобразование Фурье для каждых К и Г

Для построения двумерного алгоритма БПФ с разбиением по времени по основанию 2 выберем л = 2 и л = л/2. Тогда урав нения в матричном виде для * = О, л/2 - 1 и / = О л/2 - 1 даются равенством

п/2-I п/2-I л/2-I л/2-] Л/2-] п/2-I

,2 Г А 2/7,

2+1, 2/

2i, 2/+I

(=0 /=(

Этот БПФ-алгоритм разбивает таблицу входных данных на четыре llur. n четностью или нечетностью обоих ин-

дексов. Выходная таблица также разбивается на четыре таблицы oxnl ДРУ У правилу, определяемому принадлежностьк l?rZ. rJl Р Р * -новине. Вычисления

теперь свелись к четырем двумерным ((п/2) х (л/2))-точечным поеоб-разованиям Фурье и (3/4) п умножениям на степени элемента! Мы здесь не учитываем (1/4) п тривиальных умножений, которые

формируются в один блок и легко из алгоритма выбрасываются. Оставшаяся часть тривиальных умножений мала и входит в полное число (3/4) умножений. Пусть п равно степени двойки и М {пхп) обозначает число умножений в поле F, необходимых для вычисления двумерного (пХ/г)-точечного преобрйзования Фурье описанным алгоритмом. Тогда мы получаем следующую рекурсию:

м{пхп) = ш (- x-f)--л

Решение этого рекуррентного уравнения дается равенством

М {п X п) ~ л (log., п -С),

где константа С определяется числом умножений в самом внутреннем шаге. В частности, можно отталкиваться от (2 X 2)-преобразования Фурье, не содержащего умножений, так что Af (2x2) = О, или от (4x4)-преобразования Фурье, также не содержащего умножений, так что Л4 (4X4) = 0. Тогда

М{п X n) = n\ogn~ ])

М (п X п) = п (log., л - 2).

Возможно и дальнейшее уменьшение 4HCvTa умножений, но структура алгоритма при этом усложняется.

Полученные формулы интересно сравнить с числом М {пхп) = logs п умножений в поле F, необходимым в двумерном алгоритме, основанном на использовании БПФ-алгоритма Кули-Тьюки по основанию 2 по столбцам и по строкам.

Некоторое уменьшение числа необходимых умножений является приятным свойством рассмотренного двумерного алгоритма. Но намного более важной является используемая в нем форма записи входных данных, так как она уменьшает необходимое число обменов данными между глобальной и локальной памятью процессора. Входная таблица считывается в локальную память по две строки одновременно. Объем локальной памяти должен быть достаточен для запоминания двух строк. Вдоль каждой пары строк вычисляются все двумерные (2х2)-преобразования-Этот процесс для данной таблицы повторяется logs п раз. В каждой итерации процесс спаривания двух строк управляется алгоритмы адресного тасования Кули-Тьюки; формирование (2x2)-таблиц в пределах двух спаренных строк также управляется алгоритмом адресного тасования Кули-Тьюки. Так как входная таблица содержит п строк, и так как она трансформируется всего logg п раз, то в общей сложности мы получаем п logs переносов строк из глобальной памяти в локальную и такое же число обратных переносов.