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

Отметим, что четыре верхние строки комплексно сопряжены с четырьмя нижними строками; выполнять надо только вычисления, связанные с первыми четырьмя строками. Следовательно, дальнейшие вычисления можно организовать в виде пары циклических сверток

= (o) x + + =х -f 0)) {vnx + щх + v,x -f щ) + -f- (ш- х= -f m-V + (o-x + 0)-) (v + v,x -b У13Х -f

(modx*- 1).

Для комплексного поля можно использовать и альтернативный способ, основанный на выписанной выше 2-точечной циклической свертке блоков:

1 I

1 -1

где при 9 = 2л./1б

3(W, + w,) =

cose COS COS 9e COS lie

COS 119 COS fl COS 3e COS 9в

cos9d COS 119 COS 9 cos 39

COS 39 cos 99 cos 119 cos 9

у sin 9 у sin 39 у sin 99 у sin 119

у sin 119 у sin 9 у sin 39 у sin 99

у sin 99 у sin 119 у sin 9 у sin 39

у sin 39 у sin 99 у sin 119 у sin 9

Заметим, что теперь мы получили две циклические свертки, одна из которых чисто вещественная, а другая - чисто мнимая. Для случая вещественного входного вектора необходимо вычислить только две вещественные свертки,

s (х) = kos Звх- + cos Эбх -Ь cos 118х -Ь cos ЭЫ (х)

(mod X* - 1)

,! (х) = [sin ЗЭх -f sin 9вх + sin llOx -f sin 6] d (x)

(mod X* - 1).

Используя Китайскую теорему об остатках для разложения х - 1 = (х - 1) (х + 1), видим, что некоторые вычисления излишни, так как

cos Звх + cos ЭЭх -f cos 119х + cos е = О (mod х= - 1)

sin Звх= + sin Эвх -f sin пех + sin 9 = О (mod х - 1).

Следовательно, умножения, связанные с модулем х - 1, не нужны. Вычеты по модулю х + 1 требуют трех умножений каждый. Следовательно, для вычисления двух циклических сверток необходимо в общем только шесть умножений. Исходное 16-точечное преобразование требует, таким образом, всего 10 нетривиальных умножений.

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

Этот БПФ-алгоритм Винограда предназначен для эффективного вычисления дискретного преобразования Фурье малой длины. В основу алгоритма заложены две идеи: рассмотренный в предыдущем разделе алгоритм Рейдера для простых длин и рассмотренный в разд. 3.4 алгоритм Винограда для свертки. Рассмотрению подлежат три случая: (1) длина равна простому числу; (2) длина равна степени простого нечетного числа и (3) длина равна степени двойки. Наиболее популярными длинами являются 2, 3, 4, 5, 7, 8, 9 и 16. Характеристики БПФ-алгоритма Винограда для этих длин приведены на рис. 4.14. (Сами алгоритмы выписаны в приложении В.) Число умножений на этом рисунке упоминается дважды: один раз приведено число умножений без учета тривиальных умножений, а другой раз - полное число умножений, включающее умножения на (±1) и (±/). Если БПФ-алгоритм малой длины используется в качестве блока для гнездового алгоритма, который будет изложен в гл. 8, то умножения на (± 1) и (±/) в малом алгоритме приводят к нетривиальным умно-

Рис. 4.14. Характеристики БПФ-алгоритмов Винограда малой длины.

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

В характеристики алгоритмов, приведенные на рис. 4.14, включены также некоторые тривиальные сложения. Сюда относятся чисто вещественные и чисто мнимые сложения, которые согласно принятым определениям не являются сложениями. Но при подсчетах сложности мы не будем различать тривиальные и нетривиальные сложения. Если заменить вещественный вектор комплексным, то все сложения становятся нетривиальными комплексными сложениями.

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

Рассмотрим 5-точечный двоичный БПФ-алгоритм Винограда, вычисляющий

: S ai4. А =

0.....4,

где (О = е- . Сначала воспользуемся описанным в разд. 4.5 алгоритмом Рейдера, переводящим рассматриваемое преобразование Фурье в циклическую свертку

S W = g W d W (mod x - 1), где многочлен Рейдера

g (х) = (ш - 1) X -f ((В -1)х + (а 1) X + (м I)

имеет фиксированные коэффициенты. Вход я выход фильтра описываются соответственно многочленами d (х) = v,3 + ViX + V3X + Ox,

s (X) = (К, -V,)x + (V. - Ко) x + {Уг -V,)x + (V,- V,). Коэффициенты многочлена d (x) получаются перестановкой коэффициентов входного многочлена и (х); коэффициенты многочлена V (х) на выходе алгоритма (с точностью до слагаемого V ) получаются обратной перестановкой коэффициентов многочлена s (х) на выходе фильтра.

5-точе}ный БПФ-алгоритм Винограда получается, если произведение g (х1 d (х) вычислять с помощью алгоритма Винограда для малой свертки. Воспользуемся приведенным на рис. 3.14 и содержащим пять умножений алгоритмом 4-точечной циклической Свертки. Его можно приспособить для вычисления преобразования Фурье, введя в матрицу свертки операции перестановок путем соответствующей перестановки ее строк и столбцов. Так как коэффициенты многочлена g{x) фиксированы, то вычисление произведения вектора g на его матрицу также можно выполнить заранее. Если в алгоритме 4-точечной свертки произвести все эти изменения и внести в него члены и и У , то и получится 5-точечный БПФ-алгоритм Винограда, стандартная матричная форма которого показана на рис. 4.15. Эта стандартная форма окажется очень полезной при построении в гл. 8 гнездовых методов. Заметим, что в алгоритме иа рис. 4.15 матрицы предсложений и постсложений не являются квадратными. 5-точечный входной вектор дополняется до 6-точечного вектора, к компонентам которого применяется умножение. Верхние две строки связующей матрицы не содержат умножений, так как связывают а и V . Другие пять строк соответствуют алгоритму вычисления 4-точечной циклической свертки. Одна из констант умножения оказалась равной единице, так что на самом деле алгоритм содержит только пять нетривиальных умножений и одно тривиальное.

На рис. 4.15 видна также и другая важная деталь алгоритма. Хотя нет никаких причин ожидать этого, все диагональные эле-менты оказались чисто вещественными или чисто мнимыми ).

) При желании множитель / можно перенести из диагональной матрицы в матрицу постсложений. Тогда элементы диагональной матрицы окажутся чисто вещественными.

V = Wv = СВА*

0 о о о б] fSi

1 1 I 0-1 1-1 1 1 о 1-1-1-1 о 11-10

11111

0 1111

0 1-1-1 1

0 1-1 1-1

0 10 0-1

0 0-1 1 о

i (COS 9 + cos 29) - 1 I (cos 9 - cos 29) J sin 9

7{-sin в + sin 29) j {sin 9 + sin 29)

Рис. 4.15. 5-точечный БПФ-алгоритм Винограда.

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

1 = {х(р-

. 1)((>.-1)/2 1).

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

Теорема 4.6.1. Пусть g(x)-многочлен Рейдера; тогда для каждого нечетного р коэффициенты многочлена g (х) (mod хС- - - 1) являются вещественными, а коэффициенты многочлена g (х) (mod х(р-0/2 -f- 1) являются мнимыми.

Доказательств. Так как элемент я примитивен, то л - = 1 и я -)/ = -1. Так как

г(х)=Е(и-- 1)х ,

то коэффициенты многочлена g (х) (mod х-/ ± 1) даются равенствами

g, = (o,- 1):р( + (->/2 ,).

Утверждение теоремы вытекает теперь из того, что яр-ч/ = = -1- □

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

Случаи р = 2 и нечетного простого р решаются двумя различными методами. Сначала рассмотрим случай нечетного простого р.

Длина преобразования равна степени простого нечетного числа. Конструкция несколько усложняется. Сначала для выделения циклической группы порядка р- (р - 1) из множества {I, 2, р- 1} всех индексов удаляются целые числа, кратные р. Эта циклическая группа приводит к свертке длины р (р - 1), которая образует ядро алгоритма вычисления преобразования Фурье. Как и прежде, она вычисляется быстрым алгоритмом свертки. Компоненты свертки нужно переставить по правилу, обратному перестановке входных компонент свертки, и подправить членами, учитывающими выброшенные р~ строк и столбцов. Как мы увидим, эти поправочные члены можно вычислить алгоритмами еще меньших сверток, так как они пред-ставимы в виде алгоритмов преобразования Фурье малой длины.

Например, при = 9 = 3 удаление номеров О, 3 и 6 из множества всех индексов приводит к подмножеству {I, 2, 4, 5, 7, 8}, образующему относительно умножения по модулю 9 циклическую группу, изоморфную аддитивной группе Zj целых чисел {О, 1, 2, 3, 4, 5} относительно сложения по модулю 6. Мультипликативная группа порождается степенями 2 по модулю 9, так как эти степени равны соответственно (1, 2, 4, 8, 7, 5. Таким образом, 9-точечное преобразование Фурье содержит шесть строк, которые можно изолировать, переставить и вычислить в виде свертки. Нетрудно предвидеть, что остальные строки и столбцы (с индексами, равными О, 3 и 6) имеют структуру, близкую к 3-точечному

6 Блейхут Р.