где Vl = Vi к vl = - соответственно переставленные

компоненты последовательностей входных и выходных данных. Теперь мы получили уравнение для вычисления циклической свертки последовательностей [v]] и {(o ). Таким образом, переставляя инде1сы входных и выходных данных, мы записали преобразование Фурье в виде свертки. Однако для того вида, в котором эти формулы выписаны, необходимое число операций для вычисления свертки опять имеет порядок л. В следующем разделе мы скомбинируем алгоритм Рейдера для простой длины с алгоритмом Винограда для свертки и получим малый БПФ-алгоритм Винограда.

Построим, используя алгоритм Рейдера, двоичное пятиточечное преобразование Фурье, для которого

= Б шЧ. А = о.....4,

где ш = Сначала перепишем преобразование в виде

V. = i; Щ,

v = o + i: t.i = Vo + i:(o -i)ii. * = i.....

(=1 (=1

И будем заниматься только членами 2 ( - ) i- Элемент 2

в поле GF (5) является примитивным, и, следовательно, в этом поле выполняются равенства

2 = 1, 2> = 2, 2 = 4, 2 = 3,

2 = 1, 2- = 3, 2-2 = 4, 2- = 2.

Таким образом,

V;-V,= ; (0,24 !) ;.

в этой сумме легко узнается 4-точечная циклическая свертка. Выделим постоянные члены и определим фильтр Рейдера, задавая его многочленом g (х) над полем комплексных чисел, где

g (х) = (<о= - 1) X + ((О* -1)х + (О) - 1) X -Ь (<о - 1)

(с коэффициентами gj = ш - 1). Вход и выход фильтра описываются многочленами, коэффициенты которых равны перестав-

ленным компонентам векторов v и V. Итоговая форма 5-точечного алгоритма Рейдера задается уравнениями;

d (jc) = VX + ViX -f V3X + Dl,

s {x) = (V3 -Vo)x> + (V4 - Vo) + (V,-Vo)x + (V,- V )

s{x) = g{x)d(x) (mod-I),

Многочлен g (л:) фиксирован. Многочлен d (x) образуется перестановкой коэффициентов многочлена t) (д;). Многочлен V {х) получается обратной перестановкой коэффициентов многочлена s(x). Схематически этот алгоритм представлен на рис. 4.13.

Поучительно переписать алгоритм Рейдера в матричной формулировке. Для 5-точечного преобразования Фурье такая формулировка имеет вид

У, - у,

У-. - у.

у> - у в

у, - У

ш - I м= - 1 - 1 .= - I и - 1 и - 1

и - I - I

- 1 - 1

- 1 и - 1

Правило перестановки алгоритма Рейдера приводит это равенство к эквивалентному равенству

У, - П

У, - и.

у. - У<

У> - (

и - 1 и> - 1 и - 1 ш - 1

и - 1 ш - 1 и - 1 и - 1

- 1 - 1 w - 1 w - 1

- 1 w - I - 1 ш - 1

в котором легко распознать матричную форму записи циклической свертки

\у, - П

у г - Ус

У, - Ус

у, - у.

Sl 2 1

о 1 2

it Sl о s>

) 2 Sl о

Вход (ио, wi, ui, fj, u)

Перестановка компонент Входа

й{Х] = - VtX - + ViX + tf,

Выход (И,. И И,. Г.. V.)

Рис. 4.13. Алгоритм Рейдера вычисления 5-точечкого преобразования Фурье.

go = 01 - 1, 1 = - 1,

(о* - I, = -

где - 1.

Идея алгоритма Рейдера переносится на случай, когда длина п преобразования равна степени нечетного простого числа. В этом случае, подобно тому, как нулевые компоненты временного и частотного векторов обрабатывались отдельно, еще некоторое количество компонент временного и частотного векторов должны обрабатываться отдельно. Это объясняется тем, что в кольце Z/(p ) не существует элемента порядка р - 1. Теорема 5.1.8 (которая будет доказана в гл. 5) гарантирует, однако, что для простого нечетного р в этом кольце имеется элемент порядка р - (р - 1), и мы этим воспользуемся.

При вычислении

р -1

А = 0, ...,/) - 1,

воспользуемся структурой кольца zKp ) для того, чтобы переупорядочить компоненты векторов. Эта структура описывается теоремой 5.1.8. Еслн q равно степени простого нечетного числа, то zl(p ) содержит циклическую-подгруппу порядка р - (р - 1). Из (р ! X р-матрицы W = lmJ просто выбросим все вызывающие трудности строки и столбцы так, чтобы к оставшейся матрице размерности р - (р - 1) была применима идея Рейдера. Выброшенные строки и столбцы будем обрабатывать отдельно. Как мы увидим в следующем разделе, обработку даже этих вызывающих трудности столбцов и строк можно организовать как вычисление еще меньших циклических сверток.

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

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

Это объясняется тем, что множество индексов, взаимно простых 0 2 - множество нечетных индексов - не образует циклической группы по умножению. Как доказывается в теореме 5.1.8, это множество образует группу, изоморфную группе Zi X Zm~2 Идея организации процедуры вычислений состоит в следующем. Из (г X 2 )-матрицы W = [ш ] выбрасываются все строки и столбцы с четными индексами, так что остается матрица размерности 2 -1. Все оставшиеся индексы являются нечетными и по

умножению образуют группу, изоморфную группе 22 X Z2m-2-

Этот изоморфизм используется для того, чтобы определить такую

перестановку строк и столбцов матрицы, которая переводит ее в матрицу вида

где Wi и представляют собой (2 -2х2 -2)-матрицы, каждая из которых задает структуру циклической свертки.

Точнее, пусть я = 3 и 0=2 - 1. Тогда по модулю 2 имеем о = 1. На самом деле группа нечетных целых чисел относительно умножения по модулю 2 порождается элементами п на: каждый элемент группы может быть однозначно представлен

. в виде <1л , где / = О, 1 и Г - 0.....2 -. Следовательно,

м = О) яояг- и подходящей перестановкой строк и столбцов матрица W приводится к виду

где и г соответственно индексы строк и столбцов в каждой из подматриц. Каждая из четырех подматриц задает циклическую свертку длины 2 -.

После выполнения перестановки рассматриваемое вычисление приводится к виду матричной 2-точечной циклической свертки

ОДИН из способов вычисления которой дается формулой

4-(Wi-Wa)

1 1 1 -1

Этим задача сводится к вычислению двух комплексных циклических сверток длины 2 -; мы увидим, что вычисления можно организовать несколько лучше.

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

Кй = S м*и А = 0.....15,

где ш = I. Рассмотрим матрицу, образуемую в результате выбрасывания всех четных индексов в рассматриваемом диапазоне значений i и к. Получим

Чтобы найти нужную перестановку, выпишем индексы в виде чисел 15-З для Г= О, 1 и Г= О, 1, 2, 3. Степени тройки по модулю 16 имеют вид

3° =1, 3 = 3, 3 = 9, 3 = И,

3 = I, 3- = 11, 3- = 9, 3 = 3,

и соответственно

15-3° = 15, 15-3 = 13, 15-3 = 7, 15-3 = 5,

15-3 = 15, 15-3- = 5, 15-3,- = 7, 15-3- = 13.

Выполним перестановку входных индексов, записывая их в порядке 15--3- (mod 16), и перестановку выходных индексов, записывая их в порядке 15-3 (mod 16). Тогда

VI <1 CI и

К U

и; ш ui ш u) i ui ui ui u \

Чтобы показать четыре образовавшиеся при этом циклические свертки, матрица разбита на блоки. Если преобразование Фурье вычисляется в поле комплексных чисел, то блоки связаны соот-