1024

32 -точецный 5ПФ-алгоритм Кули-Тьюки без умножений

32-mouewHbiu

БПФ-алгоритм Кут-Тьюки без умножений

Рис. 6.2. Структура 1024-точечного БПФ-алгоритма в поле QF (21+ I).

GF (2- + I) является примитивным, но, возможно, такой выбор не является лучшим. Мы хотим со выбрать так, чтобы выполнялось равенство (о = 2; следовательно, я надо выбрать так, чтобы jj3048 2. БПФ-алгоритм Кули-Тьюки приводит преобразование к виду

31 г

2 2-

Для каждого значения i внутренняя сумма является 32-точечным преобразованием Фурье, и для каждого к внешняя сумма является 32-точечным преобразованием Фурье. Каждое 32-точечное преобразование Фурье в свою очередь может быть разбито по БПФ-алгоритму Кули-Тьюки по основанию два и вычислено с помощью только циклических сдвигов и сложений. Умножения на со * представляют собой нетривиальные умножения, но таких умножений имеется всего 1024, и все они являются целочисленными. На самом деле при i или к , равном нулю, эти умножения тривиальны, и остается только 931 нетривиальных умножений. Структура этого БПФ-алгоритма показана на рис. 6.2. В общем случае преобразование Фурье в поле GF (2 4- 1) может быть вычислено с помощью примерно п (flogsi 1 - 1) умножений в поле GF (2 + 1), (1/2) п log п сложений в этом поле и (1/2) л logs л циклических сдвигов.

Арифметикой поля GF (2 + 1) являются обычные целочисленные сложение и умножение с последующим приведением результата по модулю 2 + 1. Но так как 2* = -1, то 2+ = - -2, так что биты порядка больше чем 16 переводятся в младшие разряды и вычитаются.

6.3. Числовые преобразования Мерсенна

Полями Галуа, в которых умножение выглядит наиболее естественным образом, являются поля вида GF {2 - 1), которые являются на самом деле полем только для простых т, так как

если т - число составное, то 2°* - 1 делится на 2- 1. Простые числа вида 2 - 1 называются простыми числами Мерсенна. Наименьшие значения т, для которых число 2 - 1 является простым, равны 3, 5, 7, 13, 17, 19 и 31; соответствующие им простые числа Мерсенна равны 7, 31, 127, 8191, 131 071, 524 287 и 2 147 483 647.

Арифметика поля GF (2 * - 1) очень хорошо согласуется с представлением целых чисел в виде т-битовых чисел, так как в этом поле 2 = 1. Следовательно, арифметикой поля является обычная целочисленная арифметика, вкоторой биты переполнения переносятся слагаемыми в соответствующие низшие разряды. Это и есть арифметика 1-дополнений).

Поле Gf (2°* - 1) существует для всех простых чисел 2 - 1. В поле Галуа GF (q) преобразование Фурье существует для всех длин л, которые делят чрсло q - 1. Следовательно, в простом поле GF {2 - 1) преобразование Фурье существует для всех длин л, которые делят число 2 - 2. Эти преобразования иногда называют числовыми преобразованиями Мерсенна.

Так как число (2 - 1) - 1 не равно степени двух, то числовые преобразования Мерсенна нельзя вычислять с помощью БПФ-алгоритма Кули-Тьюки по основанию два. Этим они существенно отличаются от числовых преобразований Ферма, для которых БПФ-алгоритм Кули-Тьюки оказался вполне подходящим. Для вычисления числового преобразования Мерсенна можно воспользоваться любым БПФ-алгоритмом по смешанному основанию.

Например, поле GF (2 - 1) можно рассматривать как поле, элементы которого заданы в виде 13-битовых представлений целых чисел. Свертка двух векторов, компоненты которых заданы 12-бнтовыми числами, может быть вычислена в этом поле, если только не происходит переполнения выходных коэффициентов свертки. Таким образом, линейная свертка s (х) = g (х) d (х), где коэффициентами многочленов g (д;) и d (х) служат 12-битовые положительные целые числа (что эквивалентно 13-битовому представлению целых чисел в обратном коде), может быть выражена в виде

s(x) = g {х) d {X) (mod 2 - 1),

если известно, что коэффициенты многочлена s ix) меньше чем 2 - 1.

Для длин л, которые делят число 2 - 2, в поле GF (2 - 1) существует преобразование Фурье. В данном случае выбор воз-

Напомним, что речь идет о двоичном представлении целых чисел в обратном коде, в котором взятое с обратным знаком число записывается в виде дополнения его двоичной записи. Например, при m = 3 и р = 7 число 2 записывается в виде 010, а число - 2 = 5 в виде 101. - Прим. перев.

можной ДЛИНЫ п Преобразования дается разложением 2 - 2 = = 2-57-9-13. В качестве ядра преобразования Фурье можно выбрать элемент -2, так как 2 - 1 = 0 (mod 2 - 1), и, следовательно, порядок -2 равен 26. Таким образом,преобразование Фурье записывается в виде

= I (-2) V,. ft = О, ..., 25.

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

Для построения преобразований на других длинах приходится допустить наличие умножений. Алгоритм на большой длине, скажем 70, строится из алгоритмов малых длин, в данном случае 2, 5 и 7, подобно тому, как рассматриваемый в гл. 8 БПФ-алгоритм Винограда большой длины для поля комплексных чисел строится из БПФ-алгоритмов Винограда малых длин. Эти алгоритмы полностью аналогичны, за исключением того, что по-разному определяняся константы умножения, связанные с различным определением ядра т.

В качестве примера построим 5-точечный БПФ-алгоритм Винограда в поле GF (2 - 1). Непосредственной проверкой можно установить, что 3 является примитивным элементом поля GF (2 - 1); следовательно, порядок элемента 32T.9-13 .р равно 4 794) равен 5. Далее, порядок элемента 1904 также равен 5, так как 1904 = (4794). Тогда 5-точечное преобразование Фурье в поле GF (2 - 1) имеет вид:

V, = S [imfvi, t-o

ft = 0,

Сначала воспользуемся алгоритмом Рейдера для замены этого вычисления сверткой. Так как алгоритм Рейдера оперирует только с индексами компонент данных, то эта конструкция полностью повторяет конструкцию для поля комплексных чисел. Эти.м задача сводится к вычислению циклической свертки s {х) = = g (х) d (х) (mod X* - 1), в которой многочлен Рейдера равен

g (Х) = (0) - 1) Х + (о* - 1) + (0)2 1) + (ш 1) =

и = 3001х - 1511х= + 4793х + 1903

d (х) = Чгх + Ч4Х -f Vsx + щ,

s(x) = (Vs-v )x=-(v.-v )x + - {V, -Vo)x + (Vl - Vo). Теперь воспользуемся быстрым алгоритмом вычисления 4-точечной циклической свертки. Так как разложение многочлена - \ в поле GF (2 - 1) дается равенством х - 1 = (х - - 1) (х + 1) (х + 1), то этот алгоритм циклической свертки имеет тот же самый вид, что и для полей комплексных и вещественных чисел. Это позволяет воспользоваться выписанным на рис. 4.13 алгоритмом, интерпретируя арифметические операции как операции в поле GF (2 - 1). Итак,

С С,

и 5-точечный БПФ-алгоритм Винограда в поле GF (2 - 1) записывается в виде

В качестве второго примера рассмотрим поле GF (2 - 1), элементы которого записаны как 17-битовые представления це. лых чисел в обратном коде. Линейная свертка последовательностей 16-битовых целых чисел может быть вычислена как свертка в поле GF (2 - 1): здесь не происходит переполнения выходных компонент свертки. Для вычисления свертки можно воспользоваться БПФ-алгоритмами в поле GF (2 - 1) и теоремой о свертке.

Длины преобразования Фурье в поле GF (2 - 1) исчерпываются делителями числа 2 - 2, которые полностью определяются разложением 2 - 2 = 2-3-5-17-257. Можно выбрать, например, п. = 510, и строить 510-точечное БПФ-преобразование из 2-точечного, 3-точечного, 5-точечного и 17-точечного БПФ-алгоритмов. Модули для 2-точечного, 3-точечного и 5-точечного преобразований очень просты и даются малыми БПФ-алгоритмами Винограда. Хотя эти малые алгоритмы рассматриваются над полем GF (2 - 1), записываются они точно так же, как и в случае поля комплексных чисел.

17-точечное преобразование тоже представляет собой простой модуль, во строится он другим способом. А именно, элемент 2

ПОЛЯ Of (2 - 1) имеет порядок 17, так как 2 = 1. Следовательно, 17-точечное преобразование в этом поле задается равенствами

Vt. = i;2 u ft = О, .... 16,

и может быть вычислено с помощью одних циклических сдвигов и сложений. Умножения не нужны.

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

6.4. Алгоритмы свертки в конечных полях

В полях Галуа вместо того, чтобы пользоваться преобразованием Фурье и теоремой о свертке, можно строить прямые методы вычисления свертки. Для построения алгоритмов свертки применимы все описанные в гл. 3 методы. Другой путь построения прямых алгоритмов свертки состоит в модификации уже построенных алгоритмов свертки для поля вещественных чисел.

Для преобразования алгоритма свертки, построенного для поля вещественных чисел, в алгоритм свертки в поле Галуа GF (q) характеристики р начнем о алгоритма свертки, записанного в виде

s = C[(Ag)-(Bd)],

где А, В и С - матрицы о рациональными элементами. Умножим обе части равенства на наименьшее целое число L, такое, чтобы ликвидировать все знаменатели во всех компонентах; тогда равенство перепишется в виде

Ls = C[(Ag)-(Bd)l,

где L - целое число и А, В, С - целочисленные матрицы. Это равенство можно рассматривать как алгоритм вычисления целочисленной свертки; следовательно, его можно рассматривать и как уравнение по модулю р:

Ls = C[(Ag).(Bd)] (modp).

Если L ф О (mod р), то, разделив обе части равенства на L по модулю р, получаем алгоритм свертки в GF {р), и, более того, алгоритм в любом расширении поля GF (р).

Если L сравнимо с нулем по модулю р, то алгоритм свертки для поля вещественных чисел не переносится в поле Галуа, и надо строить такой алгоритм прямо в самом поле Галуа. Эта задача возникает даже тогда, когда L не равно нулю по модулю р, так как может оказаться, что алгоритм свертки, построенный специально для данного поля Галуа, лучше алгоритма, перенесенного из другого поля. Для построения такого алгоритма можно пользоваться разработанными в гл. 3 методами; конечно, при этом требуется, чтобы разложение

т(л:) = т< ()-т >()

было разложением в том поле, в котором вычисляется свертка.

В большей части данной главы мы будем интересоваться полями, характеристика р которых велика. Так как для таких полей L будет намного меньше р, то все алгоритмы свертки для поля рациональных чисел могут быть перенесены в GF (р) и будут выглядеть точно так же. В оставшейся части этого раздела мы займемся противоположным случаем - случаем полей малой характеристики, или, еще конкретнее, случаем полей характеристики два. Поля Галуа характеристики два играют важную роль в нескольких приложениях.

Начнем с построения алгоритма 3-точечной циклической свертки для полей характеристики два. В поле бесконечной характеристики этот алгоритм записывается уравнением

t(,s. + S, t g.)

( а - Я) (8 - S,}

Uso + g, -

I 1 1

1 О- 1 О 1-1 1-2

Ни один из знаменателей не кратен двум. Следовательно, алгоритм может быть перенесен в поля характеристики 2. Арифметикой целых чисел в полях характеристики два является арифметика по модулю два, так что все целые числа равны нулю или единице Соответственно новый алгоритм записывается в виде

110 1 1110 10 11

(Sl + S,]

I 0 1

0 1 1

1 1 0