Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 34
Текст из файла (страница 34)
пнальаа для даинога поля Галуа, лучше алгоритма, перенесенаого из другого гюля. Для построения такога алгоритма можно поль. зозаться разработанными в гл. 3 методамн; конечно, прн этом требуется, чтобы разложение ш(х) = шгзг(х) ...ш(ьг(х) было разложенкем в гом воле, в котором вычисляется свертка. В большей части данной главы мы будем интересоваться па. лямн, характернстнка р которых великз. Так кан для таких палей Е будет намного меньше р, та все алгорптмы свертки для паля ришанальных чнсел могут быть перенесены в Ер (р) н будут выглядеть точна так же. В оставшейся часта этого раздета мы аайчемся противоположным случаем — случаем палей малой характерясгикн, нли, еще конкретнее, случаем полей характеристикн два Поля Галуа характеристики два игрзкп важную роль в несколькнх приложениях.
Начнем с построенпя алгоритма 3-точечной циклической сверткн для палей характеристнкн два. В псле бесноаечной характеристики этот алгорятм записывается уравнеанем з '~тцг г 'га 3 (з] — гг: еа з-~ (з,), Нн одна нз знаменателей не кратен двум. Следовательно, алгоритм мажет быть перенесен а поля характеристики 2. Арнфметикай целых чисел в полях характеристики даа является арнфметина па лгодулю деа, так что все целые числа равны нулю нла едвнице.
Сошвегстаенна новый алгоритм записывается в виде Последний алгоритм строится методами главы 3 и задается равен- ствам о а о о « а 1о о а о г ос~!а' а з,! х„) оо)л о о 1 а а о о с а о о о о а~а а г а ~ е о а о а о з ! д а й о о з Такого сорта улучшения чожно найтв и в полях бодьюей характеристики. Например. н поле бд (1Ц разложение на простые множнтечи гаго же нногочлеяа х' — 1 имеет вид х — 1 —.
(х — Ц (х' -1- бха -! 4х — Ц (ха — 4хл — 8х — Ц, Следовательно, в полях характеристика одиннадцать алгоритм вычисления 7.точечной циклической свертки содержит 11 умно. жений. Таким алгоритмом является аааа -л В а.цоригм входит только 11 умножений обюего вида, но умножений на малые гриксаароваагные константы (ю2, ~3, Ю4, а=б) оа содержит достаточна много, Каждое нз такик уыиожений можно замеивть несколькими сложеанями, но тогда мы получим бояьюое числа сложений. Возможноств улучшения этого алгорятмн и являются открытой задачей Ее регнение зависит от стоимости сложений и умножений В достатояяо больших расширениях поля ОР (11") умножения обходятся с)щественно дороже сложений, так что такой алгоритм мажет оказатьсд вполне пригоднын В простом поле Сг (1Ц, по-видимому, замена умножений сложениями не дает преямущестн.
С другои стороны, алгоритм 2-точечной свертки содержит эле менты с четным знааюнвтелем п, следовательно, не може~ быть перенесен в поля характеристики два, таь как знаменатели обратятся в нута Лучачаай алгоритм 2-точечной циклической свертки в полах характеристика два задзетси равенством и содержи тря уююжгнпя Прнчиаш нсобход ~алости трех уланоженнй кроеюя а то», что нзд полем СР (2) мвогачлен хл — 1 не разлагается в произведение двух взаиално простых чвожитетей, так как в полях хврюггеристпки два — 1 = 1, в, следоиательно, л' -и 1 = (х 4- Ц'. следонателыю, и коншруьцию затора тма в иачестве молуля входит многочлеа ха 4 1 степени двз Таная саатуаашаа, чогда число умножений в коне~ноя поле больше числа умноисепнй в рашюяальном поле,,егтречаюся дхя циклических сверток многих длин.
Эта происходит патону, по несколько прэ гых делителей мпогачлеиа х" — 1 аказываипся равнымн. С другой сторояы,некюорме циклические свертки в полях конечной характеристики требуаот меньше умноженвй, чем свертки тех же длин в рзцвональнои поле Это происходит посолу, что круговые многочлгны в кпаечных полях могут распадаться в произведение простых множителей Наприааер, над полем рациоиальнык чисел разложение иа неприводнмые множители многочлена х' — 1 имеет внд х' — 1 — — (х — Ц (х' -1 х' -1- х' -1 х' 4 х* -1 к Ц а над полем характеристики двв это разложение можно продол жить х' — 1 — (х — П(х"', х а- Ц(ха -ха-! Ц.
Следовательно, согласна «ыпиеаняой в равд. 3 8 сбацай граяице, опгииальный (относительно числа у гноакеввй) алгоритм 7-точечной циклическоя евер,ьл н д полем ра гкональв х чисел дш жен содержать 12 умножений, а оптаааальвый злгораюм 7-точечной циклической свертки вад полем «арактернстикн два должеисолержать 11 умножений Длн гюрвого случая известев хороший с практической очки зрения алгорктм, содержашиаа !б уиножевиа, а длн второго — хороший алгоритм С 13 умножениями. о ~ а аз а ~ оа о ~ оо а~о о о ел~аз а во ~ о о|о оо ~ а а о 3 ~ е о о о ° а а а о е а о о аз о а во ь.ь.
К с я сз рт а сурр тнл птзя 6.5. Комплексная свертка в суррогвтиых полях В последних двух разделах мы виделя, как свертку в вещественном поле нежно вложить в поле Галуа, где ее удобнее вычислять. Теперь мы займемся этой же задачей для свертки камялекснмх гисел. В зависимости от наличия н поле ОЕ (р) элемента у — 1 здесь ииеются два различных случая, которые приводят к совершенно разным лействням.Мы рассмотрим толька два класса простых чисел! простые числа Мерсенва и простые числа Ферма. В случае простых чисел Мерсеина поле ОЕ (р) ие содержит элемента ус †в случае простых чисел Ферма элемент !т †! принадлежит полю ОЕ (р). Мы будем рассматривать лишь эти двз класса простых чисел, но к любому другому простому числу ыожно применить одни из этих методов.
Мы начнем с простых чисел Мерсенна, р .=- 2" — 1, где т— нечетное простое число. Эта палс не содержит элеиента у — 1. Расширим лоле ОР (2" — Ц да поля ОЕ 62" — Ц') полабна тому, как пале вещественных чисел и расширяется до поля комплексных чисел С. Тогда иреабразовавие Фурье я поле ОЕ ((див — Ц') можно исполюовать для вычисления свертки в поле комплексных чисел. В пале вещественных чисел мнагочлеи х' + 1 нс илгеет корней. Обозначлгм через 7' некоторый попый элемент к присоединим его к полю вндествеивых чисел, образуя множестно С = !а -1- ЬД, где а и Ь вЂ” вещественные числа, а сдожение и умножение за. даются правилами [а -1- б/) + (с .1- дД = (а + с) + (Ь + д) Д (а -1- Ь!) (с -1- д!) = (ас — Ьд) + (ад -1- Ьс) ). Летно проверить, что это множества образует пале.
Аналогично, в поле Галуа ОЕ (2 — Ц многачлен х' -'- ! не имен корней. Расширим это поле. присоединив к нему некоторый ' обозначаемый через /элемент и сформировав множество ОГ 62"— — Ц') = [а -(- Ь!), где а и Ь вЂ” произвольные элементы поля ОЕ (2и — Ц. Сложение и умножение оипть зададим правилаыи (а -1- ЬД -1- (с -1- д)) = (о -1- с) -1- (б + д) Д (а -(- Ь!) (с -1- д/) = (ас — Ьд) -1- (од -1- Ьс) ), где аперапии справа являются операниями в исхаднои поле ОЕ (2 — Ц, Легко проверить, что такое определение эадаег поле, содержащее (2 — Ц' злементов. Подытожим сказанное в виде двух хеорем.
Теорема 5.5.1. Еслгг 2 — 1 — ирттог число Мгрсгииа, то поле ОГ (2 — 1) ие содержит сргди своих юементсг каадр ного хорал иэ — 11 следтательна, многочггн л" .1- 1 не имгон а этом пола корНей. Доказательства отложим да каипа раздела, Теорема 5.5.2. Относительно оиргделеиных выше оиерадий сложения и умножсии» множество ОЕ((2 — Цл) обритдгт аот.
Доказательство. Утверждение вьпенает всиосредственно из того, что многочлен к' щ 1 прост. С) Теперь рассмотрим преобразование Фурье и пале ОЕ ((2"— — Ц'). Длина преобразования равна (25 — Ц' — 1 иля делит это числа. Так как имеет место разложение (2" — Цз — 1 .= -- 2 т'(2 ' — Ц, то возможной длиной преобразования Фурье в поле ОЕ ((2" — 1)') является 2 ", и тогда зто преобразоэание можно вычислять с помощью ВПФ-алгоритна Кули †Тыч по основанию два.
Другие возможнме длины преобразовзнн Фурье видаются делителями числа 2" †' — 1. Выберелг, например, т = 17. Тогда (2м — Ц' — 1 = 2ы х к 3 5 17 257. В иа~естве дляпы преобразования лгожно взять любую степень лвойкн вплоть до 2'", а больпгие длины палуча. ютсл присоединением ональных делителей. П!сть л делит 2ы и пусть -г ул=-згм аг г — 3 й=б, ..., и — 1, где м — элемент паля ОЕ ((2ы — Ц*) порядка и.
(В табл, б,! приведены найденные ва ЭВМ соответствующее элене|ген го.) Так как и равна некоторой стеасни двух,то для вычисления преобразования Фурье можно воспальзоватьсяВПФ-алгорнтмон Кули— Тьюкн по аснаваниго два. Возможности выбора длины преобразования Фурье в псле ОГ 62ы — Ц') существенно гавре, челе в поле ОЕ (2о — Ц; в частности, эта относится к длинам, равным степени двойки. Поэтому дла вычисления гтиклической свертки а ОЕ (2м — Ц можно перейтн в ноле Ггр ((2о — ц"'~, расслитривэя исходгг!чо свертку «ак свертку седых чисел поля ОЕ ((2лт — Ц). В случае, когда р является просты» числом Ферма, у' — 1 являнся элементом простого пала, н настроение расширения ОЕ !р') с операцией умножения, аналогичной умножена ю в поле кочплексяых чисел, невозможно.
Действительно, для р = 2 -'. 1, где т раино степени двух, возведением в квадрат легка убедиться, что «.о. Кг т «яеетш Гор х г«атяя !' — 1 = 2 м (2 ' — !). Для вычисления свертки я(х) = =- й (х) д (х), где й (х) =- й„ (х) + )йг (х) н д (х) == дя (х) + )дг (х), приходятся вычяслять четыре свертки кя (х) дя (х), йя (х) дг (х), йг (х) дя (х) н йг (х) д, (х) н пользоваться равенствами (х) = й (х)дя(х) — й, (х)дг(х), з, (х) = йв (х) дг (х) + й, (х) д„(х).
Лучшая пропепура, содержащая вдвое меньше умножений, оспа. вана на определения в кольце ОГ (р) (х)1(х" — 1) многочленов а(х) = — (йя(х) — 2 Сзй,(х))(дя(к) — 2 гздг(х)) Ь (х) — —. — (йя (х) + 2 пйг (х)) (дв(х) + 2 Г'б, (х)), для вычислевян которых надо сделать только две свертки. Все вычисления проводятся в кольпе ОР (р) П)((х — 1), н сяер ка з (х) вычнсляется по правилу яя ' = (а (х) + Ь (х)), з,(х) = 2"г'(а(к) — Ь (хД. Для завершения раздела нам осталось провести доказательства теоремы 6.5.1. Оно достаточно длинно в опираетсв на лопатке квадратичного вычета. Те элементы простого ноля ОР (р), для которых в этом поле сущестеузы квадратные кориа, называются кеодроти яьыш аматами (поскольку по модулю р оня равны квзд.
рата» своих квадратных корней). Если р нечетко, то ровно поло. вняв элементов поля ОР (р) и«Реют квадратные корня. Чтобы зто поьазать, заметны сначала, по каждая четная степень пргг«ггыяв. ного элемента и имеет кпадратный корень. Округой стороны, каждьгй элемент, равный квадратному корню, может быть записан в виде а* для некоторого г, так что ега квздрат равен а!'г'и, где двойные скобки в показателе степени использованы для обозначевня того, что вычнсления проводятся по модулю р — 1, тан как мультнпликатнвная группа паля является пнкляческой порядка р — 1 Но число р — ! четно, н, следовательно, Я2!)) также ятно, Таким образом, только четные степени элемента а могут иметь квадратный корень. Теормяа 6.5.3. Для ягмтяых р е лоле ОР (р) элемент г является коодротичвы.я яы«етом «погда и только тогда, юнади -Пгз— Локозяте яство. Предположим, что ггл — г«ггчь 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
