Посмотрев на эту матрицу, можно убедиться, что строки и столбцы с номерами О, 3 и 6 являются для нас новыми, так как содержат повторяющиеся элементы. Переставим строки и столбцы матрицы так, чтобы эти строки и столбцы оказались в новой матрице первыми, остальные строки расположились в порядке степеней двойки по модулю 9, т. е. в порядке 1, 2, 4, 8, 7, 5, а столбцы - в порядке степеней 2 по модулю 9, т. е. в порядке 1, 5, 7, 8, 4, 2. Тогда вычисление преобразуется к виду

Пунктирные разбиения, сделанные в матрице, показывают сформировавшиеся циклические свертки: одну 6-точечную циклическую свертку и шесть 2-точечных циклических сверток. Те 2-точечные свертки, которые расположены во второй и третьей строках матрицы, содержат повторяющиеся вычисления, что позволяет переписать входящие в эти две строки вычисления в виде

и, + От Us + и.

. Так как п = -1, то отсюда сразу вытекают первые два утверждения теоремы.

Для доказательства утверждения (iii) рассмотрим многочлен

g (х) = g (х) (mod х - 1) --= Е (0 х* (mod х - 1).

Коэффициент gi, равен сумме тех коэффициентов многочлена g (х), индекс к которых кратен числу Ь/р. Таких членов имеется р

штук., и

Таким образом, подходящим способом выполненные перестановки и разбиения входных данных и матрицы преобразования позволили представить рассматриваемое преобразование Фурье в виде одной 6-точечной циклической свертки и двух 2-точечных циклических сверток. Можно было бы ожидать, что так организованное вычисление потребует 12 комплексных умножений. ДЭднако, как показывает. следующая теорема, происходят две вещи:

1. Все умножения являются чисто вещественными или чисто мнимыми, так что 12 комплексных умножений превращаются в 12 вещественных умножений.

2. Число необходимых умножений уменьшается до 10, так как два коэффициента оказываются равными нулю.

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

Теорема 4.6.2. Пусть т > 1 целое, а р - простое нечетное число. Пусть b = [р - 1) р ~. Пусть g (х) - обобщенный мно-ь-\

гонлен Рейдера, g(x) = 2 u) x , где а-корень из единицы стекло

пени и я - целое число порядка b относительно умножения по модулю р . Тогда:

(1) Коз1рфициенты многочлена g (х) (mod х - 1) являются вещественными числами;

(ii) Коэффициенты многочлена g (х) (mod х + 1) являются мнимыми числами.

(iii) Коэффициенты многочлена g (х) (mod х - 1) равны нулю.

Доказательство. Доказательство первых двух утверждений теоремы аналогично доказательству теоремы 4.6.1. Так как порядок числа л равен Ь, а b четно, то = 1 и п = -1. Тогда коэффициенты многочлена g (х) (mod х ± 1) равны gi, = ш Ч=

преобразованию Фурье, так что некоторые из поправочцЬ1х членов могут быть выражены в виде свертки малой длины.

Построение 9-точечного БПФ-алгоритма Винограда проводится следующим образом. Выпишем матричное уравнение

В общем случае коэффициент gr дается равенством

gr = Ii м + , Г = О.....(Ь/р) - 1.

Требуется доказать, что gr равен нулю для всех таких г. Перепишем выражение для g, в виде

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

т. е. для go = S ю , где а = к представляет собой элемент порядка р. Последнее равенство можно переписать в виде

о = tos{o>T.

где га является корнем степени р из единицы. Следовательно, git = О, и доказательство теоремы закончено. □

Таким образом, мы умеем строить БПФ-алгоритм Винограда малых длин, равных степени нечетного простого числа. Матрица преобразования Фурье размера р X р разбивается на - p )-тoчeчнyю циклическую свертку и р + 1 (р - 1)-точечных циклических сверток. Согласно теореме 4.6.2, все эти свертки вычисляются с помощью алгоритма Винограда для цикли-ческих сверток, содержащего только чисто вещественные и чисто мнимые умножения.

Длина преобразования равна степени двойки. Преобразование Фурье, длина которого равна степени двойки, приходится рассматривать отдельно, так как целые числа, не превосходящие 2 , взаимно простые с 2, не образуют относительно операции умножения по модулю 2 циклической группы (за исключением случаев m = 1 и m = 2). Это множество чисел образует группу, изоморфную группе Z2 X Zgm-2. По этой причине конструкция БПФ-алгоритма Винограда длины 2 ,содержит на один шаг больше. Прежде всего, отберем 2 * строк и столбцов матрицы с нечетными индексами, подобно тому как это было сделано в разд. 4.5. Это подмножество элементов матрицы будет переупорядочено теперь не в одну, а в четыре циклические свертки.

Строки и столбцы с четными индексами можно представить в виде преобразования Фурье длины 2 ~ несколькими способами.. Эта часть вычислений представляет собой 2 ~-точечное преобразование Фурье.

ft =0.....n/2 - 1.

Это 2 ~-точечное преобразование Фурье может быть вычислено уже известным алгоритмом. Компоненты с нечетными значениями индекса к можно записать в виде

п!2-\ nJ2-l

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

V2k-+1.= (0> 2/- - е> 02Г+п ) О) + .

/=0 л/2-1

Е гс-цш /-=0

{2C-I-1) (2i--l)

, ft ==0, ... , n/2 - 1,

где первая сумма подлежит вычислению только для первых п/4 значений индекса ft, ft = О, /4 - 1, так как потом эти значения суммы повторяются. Если входная последовательность данных является вещественной, то эта часть вычислений состоит из (п/2) - 6 вещественных умножений и (/г/4)-точечного преобразования Фурье, а если входная последовательность данных является комплексной, то к (/г/4)-точечному преобразованию Фурье добавляется (3/4) п - 8 вещественных умножений.

Вторая сумма в уравнениях для V2k-+i может быть вычислена рассмотренным в предыдущем .разделе обобщенным алгоритмом Рейдера. Он сводится к вычислению двух циклических сверток длины 2 -2. Следующая теорема показывает, что если эти циклические свертки вычисляются на основании китайской теоремы об остатках, то часть умножений является умножением на нуль и может быть выброшена.

Теорема 4.6.3. Пусть т > 2 есть целое число и g (х, у) - обобщенный двумерный многочлен Рейдера вида

g{x, 1/)= S Е

/=0 Г-0

где ш является корнем степени 2 из единицы. Тогда

Разбиение в некотором смысле аналогично одному шагу алгоритма Кули-Тьюки по основанию 2. Предположим, что мы уже умеем строить г--точечное быстрое преобразование Фурье.

Для заданного Vt = S А = 0, ...,п- 1, компоненты

с четными значениями индекса к можно записать в виде

/./2-1

1 1 1 ш

1 ы I

1 и U

- Уд)

ы\иг - Ue)

Вторую часть сначала выпишем в следующем виде:

W w

Теперь преобразуем эти равенства несколько иначе, чем в общем случае, а именно, воспользуемся условием м* = - 1 и перепишем уравнения в виде

ш -ш ш -ы -ш о) -ш ill о) -to w -ы

Тогда

Циклическую свертку можно вычислить по правилу

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

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

Задачи

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

4.2. Пусть задано устройство вычисления л-точечного преобразовання Фурье; описать, как это устройство можно использовать для вычисления п-точечного обратного преобразования Фурье.

4.3. Приведите блок-схему устройства вычисления 5-точечного преобразования Фурье, основанного на чирн-алгоритме Блюстейна.

4.4. а. Доказать, что 2 является примитивным элементом поля GF (11).

б. Используя алгоритм Рейдера, записать 11-точечное преобразование

Фурье над полем комплексных чисел

S

(В t-i в виде свертки

(i) Коэффициенты многочлена g (х, у) (mod у - 1) являются вещественными числами.

(ii) Коэффициенты Многочлена g {х, у) (mod -j- 1) являются мнимыми числами,

(iii) Коэффициенты многочлена g (х, у) (mod х - 1) равны нулю.

Доказательство аналогично доказательству теоремы 4.6.2. □

Согласно первой части теоремы циклическая свертка по модулю х * - 1 представляет собой две вещественные циклические свертки (точнее, одну чисто мнимую и одну чисто вещественную). Вторая часть теоремы утверждает, что вычисление циклической свертки сводится только к вычислениям, связанным с модулем - 1 так как остальные вычеты обращаются в нуль. В силу неприводимости многочлена х + 1 на эти вычисления требуется 2 (п/8) - вещественных умножений.

Теперь мы получили разбиение преобразовання Фурье на следующие фрагменты: (1) 2 --точечное преобразование Фурье; (2) г--точечное преобразование Фурье, которому предшествует 2 - - 1 комплексных умножений; (3) два произведения многочленов по модулю неприводимого многочлена х + 1:

8-точечное преобразование Фурье разбивается на две части, 4-точечное преобразование Фурье