1 1 1

0000000 0" 0 110 0 0 0 1 0 10 10 0 10 10 0 110 0 0 10 10 0 10 0

Рис. 11.6. Малый пятиточечный алгоритм Винограда вычисления БПФ,

Здесь многочлен g (х) фиксирован, многочлен а (х) получается из многочлена v (х) перестановкой коэффициентов с отбрасыванием, а многочлен V (х) получается из многочлена b (х) без отбрасывания коэффициента.

Малый пятиточечный алгоритм Винограда вычисления БПФ получится, если для вычисления произведения g (х) а (х) воспользоваться алгоритмом Винограда вычисления короткой свертки. Обращаясь к таблице на рис. 11.2, находим алгоритм Винограда вычисления четырехточечной циклической свертки, содержащий девять умножений. Воспользуемся этим алгоритмом для построения алгоритма преобразования Фурье. Соединим операции переиндексации алгоритма Рейдера с матричными операциями алгоритма свертки, выполняя соответствующие перестановки строк и столбцов. Далее, так как коэффициенты многочлена g (х) являются фиксированными константами поля GF то произведение g на соответствующую матрицу можно вычислить заранее. Внеся все эти изменения в алгоритм четырехточечной свертки и присоединяя к нему компоненты Vq и v, получаем малый пятиточечный алгоритм Винограда БПФ. На рис. 11.6 приведена запись этого алгоритма в матричном виде:

V = BDAv.

Отметим, что матрица А предварительных сложений и матрица В последующих сложений не являются квадратными. Пятиточечный входной вектор перед выполнением покомпонентного умножения вытягивается в десятиточечный, задаваемый матрицей D. Первая строка матричного равенства связана с вычислением компоненты Vq и не содержит умножений. Остальные девять строк определяются алгоритмом четырехточечной циклической свертки. Одна из констант, на которую происходит умножение, равна еди-

1) Заметим, что для построения 5-точечного ДПФ с девятью умножениями достаточно воспользоваться только тем, что ядро а ДПФ длины 5 удовлетворяет тождеству 1 -j- сс -j- сс -j- сс + а* = 0. Это позволяет организовать вычисление величины vj = 2j?=o-4 полях характеристики 2 (последнее, впрочем, несущественно) следующим образом:

Vo = V(,+ Vj + Vz+ Vs + Vi,

= (fo + fi) + (f 1 + f4) аЯ + (t<2 -f v) -f {v -f v) a,

Vi = (fo + -4) + (Pi + v) a + (v + a? + {v + v) a?,

Vs = iPu + 2) + (Pi + a? + (t)2 + t;) a -f (Wg -f 4) cc*,

V, = t,o+ Vo+ У1+ У2+ 13-

Ha самом же деле использование алгоритма Рейдера сведения ДПФ простой длины к циклической свертке позволяет построить алгоритм 5-точечного БПФ, содержащий всего пять умножений. А именно для произвольных многочленов а (х) = flfl + aix -f ах -f- адл" и b {х) = f bx -f bx -f bifl алгоритм 4-точечной циклической свертки с {х) = Сд -f сх -f сх -f сх = а (х) b (х) (mod (х* - 1)) перепишем в виде

Со = (a, + ai) (60 + 2) + и йг +

+ {ao + a){bi + b.)+aibi,

Со f С2 = (bo + 62) и а; + (х + з) 2] г-

1=-0 1=0

Со + Cl + Сг = {bo Н- 62) (Оо + + il 2j +

+ iai + a){b2 + bs)+a, 6;.

Co + Cl -]- -b Сз -

/ 3 \ / 3 \

\t=0

\t=0 /

в рассматриваемом случае 6 (л:) = сс-f ссл:-f а*л;-f ccV, и, следовательно,

в силу тождества для ядра, 6 = 1, так что по существу эти умножения от-

сутствуют, и приходится выполнять только пять умнолсений. - Прим. перев.

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

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

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

В общем случае БПФ-алгоритм Винограда строится для длины п, равной произведению простых чисел или степеней простых чисел. Рассмотрим случай двух множителей, когда п = пп". Воспользуемся алгоритмом Гуда-Томаса для преобразования п-точечного преобразования Фурье в двумерное [п X п")-точеч-ное преобразование Фурье. Отдельные компоненты этого двумерного преобразования Фурье могут быть вычислены с помощью соответственно «-точечного и п"-точечного алгоритмов Винограда. Сначала выполняется п-точечное преобразование Фурье каждой строки, а затем п"-точечное преобразование Фурье каждого столбца.

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

Определение 11.5.1. Пусть А = (ац) и В = (Ьц) - матрицы соответственно размеров / X /С и J X L. Тогда кронекеровским произведением матриц А и В, обозначаемым А X В, называется матрица, содержащая строк и КБ столбцов, у которой на пересечении строки с номером (г - !)/-(-/ и столбца с номером {k - 1) L + / стоит элемент

Чтобы проще понять структуру кронекеровского произведения матриц, следует представить матрицу А X В в виде (/ X К)-таблицы, состоящей из (/ X L)-блoкoв, (i, к)-я из которых равен aftB. Непосредственно из определения вытекает, что кронекеровское произведение матриц некоммутативно, но ассоциативно:

А X В В X А, (А X В) X С = А (В X С).

Элементы матриц А X В и В X А одни и те же, но упорядочены по-разному. Очевидно также, что кронекеровское произведение дистрибутивно относительно обычного сложения матриц.