Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 33
Текст из файла (страница 33)
Е. Н л л урра ю к»юлх дш л эпю- лл Х -ию л" зз-» л«э и эл — л ли -тлю „л и 8.3. Числовые преабразовииця Мерсеина Полями Галуа, в которых уыноженне вмглядит наиболее естественным образам, являются паля аида 6Р (2 — 1), «аторме являются на самом деле полем тально для простых ш, так как ри . е.2. 0 рг ур !924.
з лег впа-шг р * ор (2г'-!. !), 6Р (2м ф 1) является примитивным, ио, вазлгожно, такой амбар ие является лучшим. Мы хотим м выбрать так, чтобы выполнялось равенства ю' = 2; следовательно, и нада выбрать так, 'пабы п*м' = 2. БПФ-алгоритм Кули †Тыч приводит преобразование к виду г —.а г"=э Для каждого значения г' внутренняя сумма является 32-точечным преобразованием Фурье, и длз каждого Д" внешняя сумма является 92-точечным преобразованием Фурье. Каждое 32-точечное преобразование Фурье в свою очередь может быть разбита по БПФ-алгорнтму Кули †Тыч по основанию два и вычислено с помощью только циклических сдвигов и сложений Умножения на мсю предсгавлюот собой нетривиальные умножения, на таких умножений имеется всего 1024, и все ани являются целочисленными.
На самом деле при г' нля Д', равном нулю, эти умноже. ния тривиальны, и остается только 93! нетривиальных умвоже. ний. Струнтура этого БПФ-алгоритэга показана ва рнс. б 2 В общем случае преобразование Фурье в поле 6Р (2ю -1- 1) может бмть вычислено с помощью примерна и (Г(ойю и) — !) умнажа ний в аале 6Р (2м -1- 1), (1(2) л 1ой, л сложений в этом пале и (1)2) л1ой, и циклических сдвигов. Арифметикой поля 6Р (2ю ф 1) являются обычные целогисленные сложение и умножение с последугощим приведением ре.
зультага по модулю 2» -!. 1. Но так как 2»:: — 1, то 2ю ' = = — 2', так что баты порядка больше чем 1б переводятся в младшие разряды и вычитаются. сачи ш — число составное, то 2" — 1 делится на 2' — 1. Простые числа вила 2" — 1 называются простыми числами Мерсениа. Наименьшие значения ш, для которых числа 2 — 1 является простым, равны 3, 8, 7, 13, 17, 19 н 31; соответствующие им простые числа Мерсенна равны 7, 31, !27, 8191, 131 071, 524 287 и 2 147483847. Арифметика поля 6Р (2 — 1) очень хороню согласуется а представлением целых чисел в виде т-битовых чисел, так как в этом поле 2 = 1. Следовательца, арифыегиной паля является обычная целочисленная арифметика, в которой биты переполнения переносятся слагаемыми в соответствующие низшие разряды. Это и есть арифметика 1-дополиений ').
Поле 6Р (2" — 1) существует для всех простых чисев 2 — 1. В поле Галуа 6Р (9) преобразоваяие Фурье существует для всех длин л, которые делят число 9 — !. Следовательно, в простои поле 6Р (2 — 1) преобразование Фурье существует для всех длин л, которые делят число 2 — 2. Эти преобразования иногда называют числеэмми лрзобреэоеаиияии Мерслзиа. Так «ак числа (2 — 1) — ! не р вна сгеис и двух, т нолевые преобразования Мерсенна иелшя вычислять с помощью БПФ-алгоритма Кули — Тычки по основанию два.
Этим они существенно атчичаюгся от числовых преобразований Ферма, для которых БПФ.алгоритм Кули — Тычки оказался вполне подходящим. Для вычисления числового преобразования Мерсеина можно воспользоваться любым БПФ-алгоритмом по смешанному основанию. Например, поле 6Р (йы — 1) можно рассматривать как пале, элеиенты которого заданы в виде 13-битовых представлений целых чисел. Свертка двух векторов, компоненты которых заданы !2-битовыми числаыи, может быть вычислена в этом ноле, если только не происходит переполнемня выходных козффициегпов свертки.
Таким образом, линейная свертка з(х) =-. 8 (х) б (х), где коэффициентами ынагошенов 8 (х) и б (х) служат 12-битовые положительные делые числа (по эквивалентно 13-битовому представлению целых чисел в обратном коде), мажет бить выражена в виде з (х) 9 (х) б (х) (шоб 2ы — 1), е ли известно, что коэффициенты многочлена з (х) меньше чем 2 — 1. Для длин и, которые делят числа 2'л — 2, в поле 6Р (2» — 1) существует преобразование Фурье. В данном случае выбор воз- пю зл. ь. нячи а низ э ГГЭ зз В.З Чз и прзсзр зоз нзя М Э а можной длины и преобразования дается разложением 2ы — 2 =- = 2 5-7 9.13.
В начестве ядра преобразования Фурье можно выбрать элемент — 2, так как 2ы — ! = 0 (шоб 2м — 1), и, следовательно, порядок -2 равен 26. Таким образом,преобразование Фурье записывается в ниде Уь = 2) ( — 2)" аь й = О, ..., 25. з з В этом преобразовании Фурье все умяожения исчерпываются умножениями на степени двух, и, следовательно, вычнсленас можно реализовать одними циклическими сдвигами, без умножений. С другой стороны, делителя числа 26 не очень приюдны в качестве длин Б)ТФ-алгоритмов! на этой конкретней длине трудна придумать что-то лучшес, чеы вычислить преобразование Фурье как она записано аосредсгвоы 25з циклических сдвигон и 26 25 сложений.
Для ыютраения преобразований на других длинах приходятся допустить наличие умножений. Алгоритм нз большой длине, скажем 70, строится из алгоритмов малых длин, в данном случае 2, 5 и 7, подобно тому, как рассматриваемый в гл. 8 БПФ-алгоритм Винограда большой длины яля поля комплексных чисел строится из БПФ-алгоритмов Винограда малых длин. Этн алгоритмы зюлностью аналогичны, за исключением того, шо по-разному определяются констагпы умножения, связанные с различным оиределеннеи ядра м.
В качестве примера построим 5.точечный БПФ-алгоритм Винограда з пале СР (2ы — 1). Непосрелсгвенной проверкой можно установить, что 3 является примитивным элементом поля СР (2н — !); следовательно, порядок элемента Зз'г '" (что равно 4 794) равен 5. Далее, порядок злемстта 1904 также равен 5, так как 1904 =. (4794)'. Тогда 5-точечное преобразование Фурье в поле СГ (2ы — 1) имеет вид: Уь = 1 (1904)мзь й =-О, ..., 4. г-с Сначала воспользуемся алгоритмом Рейдера для аамены этого вычисления свертков.
Так как алгоритм Рейдера оперирует только с ипдексачи коынонент данных, то эта коззструкция пал. пастью повторяет конструкцию для полн комплекснмх чисел. Этим задача сводится к вычислению циклической свертки з(х) =: =- д (х) б (х) (шоб хз — 1), в которой мнагочлен Рейдера ранен 3(х) =- (н — Цха+ (ы — 1) «» -1- (ыз !) х+ (м 1) = и =- 3001х' — 151!х' + 4793х .1- 1903 б (х) = о,х' + а,х" + с,х -1- ео а(х) (У Уз)» ! ()з )з)з + -1- (1' — Уз) х -1- (У, — У,).
Теперь воспользуемся быстрым алгаритмон вмчисления 4-точечной циклической свертки. Так нак разложение многачлепа — ! в поле СР (2м — !) дается равенствам х' — 1 = (ив — !) (х + 1)(х' + 1), то этот алгоритм цикличссной свертки имеет тат же самый вид, что и для полей конплексных и вежытвенаых чисел. Это позвалнет васпальзаватьс» выписанным на рнс. 4.13 алгоритмам, интерпретируя арифметические операции как операция в поле СР (2м — !). Итак, ~ю!! !с, ~ - ~ ~ ь зты! зззз! о) (з о з з! 'РгзВ и 5-точечный БПФ-алгоритм Винограда и иоле СР (йж — 1) записывается в виде Г~ .:1 В качестве второго примера рассмотрим поле СР (2ы — 1), элементм кагорога записаны как 17-битовые представления целых шсел в обратном коде. Линейная свертка послеаовательнастей 16-битовых целых чисел мажет быть вычислена как свертка и пале СР(2м — 1): здесь не происходит перепа.тнеиия выходных компонент свертки.
Для вычисления свертки можно воспользо. ваться БПФ-алгоритмамв н ноле СР (2м — 1) и тес)темой о свертке. Длины нреобразованин Фурье в пале СР (2' — 1) исчерпываются делителями числа 2ы — 2, которые полностью определи|атея разложением 2м — 2 = 2 3 5.17.257. Можно выбрать, например, я = 5!О, и строять 5!О-точечпое БПФ-преобразование ие 2-точечнань З-точечного, 5-точечнога и 17-точечного БПФ- алгоритмов. Модули для 2.точечного, 3-тозе«наго и 5-тачечнога преобразований очень просты и даются малюзз БПФ-алгоритьшчя Винограда.
Хотя эти малые ачгаритмы рассматриваются нзд полем СР (2ы — 1), записываются они точно так жс, как н н случае паля номплексяых чисел. 17-точечное преобразование тоже представляет собой простой модуль, но строится он другим соособом. А именно, элемент 2 тур поля БГ (2'à — !) имеет порядок 17, так «ак 2»'= 1. Следова. тельно, 17-точечное преобразование в этом поле задается равен ствамя м Уь=Е2цаг, й=й, ..., 15, г=е п может быть вычислено а помощью одних циклическнх сдвнгов я сложений. Умноження пе нужны.
Если необходимо вычислить свертку, длнна которой больше 510, то надо использовать также мпожатель 267. 257-точечное преобразование Фурье о помощью алгоритма Рейдера сводятся к 256-точечной циклической свертне, которая затем вычисляется с помощью БПФ-алгоритма Кули †Тью по основанию два н алгоритма свертки. 6.4. Алгоритмы свертки п конечных полях В полях Галуа вместо того, пабы пользоватьс преобразова.
пнем Фурье и теоремой о свертке, можно строить прямые методы вычисления свертки. Для построения алгоритмов свертки применпмы все опксавпые в гл. 3 методы. Другой путь построения прямых алгоритмов свертка состоит в мадкфккацни уже построенных алгоритмов свертки для поля вещественных чисел. Д.чя преобразовзння алгоритма свертки, построенного для паля вещественных чисел, в алгоритм свертки н пале Галуа СЕ (О) характериегкнн р наянем а алгоритма свертки, записанного в виде з = С((А2) (Вб)], где А, В я С вЂ” матрацы с рационзльнымп элеыентамя.
Умножим обе части равенства на наяменьшее целое число Е, такое, чтобы лнкзяднровать все знаменатели ва всех компонентах; магда равенство переппшется в виде Еа = С' ((А'й) (В'3)], где Š— целое число я А', В', С' — целачясленнме матрицы. Это равенство можно рассматрпвать как алгорптм зыяяслевия целочнсленвой свертки; следовательно, его можно рассматривать и «ак уравнение па модулю р: Ез = С'](А'й) (В'6)] (глоб р). Есле 1. нн О (пюб р), та, разделив обе части равенства на Е па модулю р, получаем алгоритм сверткн в СР (р), н, боаее того, алгоритм в любам расширении поля СГ (р). р и жрпззкашж* з Если Е сравнимо с нулем по модулю р, то алгорнтм свергни для поля вещественных чисел не переносятся в поле Галуа, н нада строить такой алгоритм прямо з самом вале Галуа. Эта залача возникает даже тогда, когда Е не равна нулю по модулю р, так как может оказаться, что алгоритм сверткн, построенный сце.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
