Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 35
Текст из файла (страница 35)
То~да у г яе может суюествовать в данном палс, так кая в прохнвном случае зю !а. ь н з сурртьтгнх пелла должно бы было выполняться равенство (у г)г ' = 1, которое не выполняется. Предположим, чта г" 'н'= 1, и пусть а — примитивный эле. мент поля 6У (р). Очевидно, что все четные степени элеиеата а явлюстсз квадраткчными вычетами, а все нечетные степени элы мента а квадратичными вычетами ае явлнююя. Нала толька по. казать, 'по г равно !сгной степени элемента а. Допустим противное: г =.анч Ч тогда, так как порядок э.чемента п равен р — 1, имеем г ' — !и ) =а и' =..а и — и ! н.г! ы — гт !!а — и ! и~ гг — пн Таким образом, из равенства г!' — 'гн= 1 вытекает, что г равно четной степени злемекга а н, следовательно, является кв;щратнчным вычетам.
С Теперь у нас уже все готово для доказательства теоремы 6.5.1. Теорема 6.5.!. Этмент — 1 лола 6Р (2 — 1), где 2 — !в просты чита гцерсенна, не инеет г зтам лот кгадрат ога корня. С едогапгельна, мнагылен кг.(- 1 нг имеет г глюм лом «арлей. Лаказательслыа. Предположим, что — 1 имеет квалратный корень, равный г.
Тогда г' = — 1 и, согласно теореме 6.5 3, ггг — 'га =. Ц -66 =-!.Таккакр.— 2 — 1, то г =1 илн г г '=1. -! Но г' = — 1 и т — 1 четно. Следовательно, г = 1 и г ' — — 1. Но тогда г' ве равна — 1 Полученное противоречие показывает, что в данном пале ие существует ивадратнаго корня из — !. Е! 6.6. Преобразования н числовом кольце Если пале Р содержит элемент порядка и, то в этом поле существует прсобразоранне Фурье длины л Если преобразование Фурье суп!ествует, то аио обладает всеми элементарными свойствами такого преобразования. Часто возможно также определить преобразование в кольце, но при этом снтуация не является столь простой.
В настоящем разделе рассматриваются преабразованни в кольце 7)(д) целмх чисел па модулю д, Есл~ д — простое число, то хбд) является полем, и, как мы уже видюн, в нем существует преабраэованве Фурье со всеми ега основными свойствами. Поэтому надо рассмотреть толька случай составного числа д.
Кзи мы увидим, даже для составных д можно дать осмысленное определенне преобразования Фурье. Однако структура этих преобразований представляет собой точную копию преобразований Фурье для простых делителей числа д, так что переход к составному д прибаеляаг мала возьгожностей. рмарю зь з чнел е,ц з!! Мы хатим определить а целочисленном пальце преобразование — ! Уь = Е итог, й=й..., л — 1, г-.ь веитора з над кольцом 7Дд) так, чтобы существовало обратное преобразование -а о,=л д,и Уь, г=й,...,н — 1, !=а и была справедлива теорема о свертке. Для тога, чтобы такое определение преобразованы» Фурье было возможным, необходима выполнение двух условий: (1) должен существовать элемент и поридка и; (2) элемент л в кольце 2!(д) должен быть обратимым.
Нужна, конечно, еще н обратимость элемента и, но из условия н" =- ! автоматически следует, чта н ' = н' '. Итан, нада опрелелить те зна гения и, для которых существует элемент и порядка л. Начнем с простейп го случая д, равного ст ° пени простою нечетного числа р, д == р Копыта 7ДР ) не образует поля, так как его умножением является умножение по модулю р . Согласно теареие 5.1.8, в этом кольце имеются элементы порядка (р — 1) р -', н согласно теореме 5.1.5 (теореме ЭйлеРа), по)гидон каждого взаимно простого р элемента делит (р — 1) р . О!гласно этому условию, для каждого делителе л числа (р — 1) р †' можно выбрать элемент н порядка л. Однако теорема 5.2.2 утверждает, что число л абрам!ма тогда и только тогда, когда л н р" взаимно просты. Следовательно, и не может лепиться на р.
Таким образам,в иачесгве и можно выбрать тальио элеыенты, порядок которых л делит р — 1. Следующая теореыа показываю, что длн каждого такого л существую сгютветсгвующее преобразование Фурье. Однако длины такого преобразования нг(р ) в точности совпадают с теми длинами, «оторме допустимы для преобразования Фурье в пале 67 (р).
Изменения'касаются только разрядности используемых чн ел, «оторва увеличивается примерно с !ой, р до т 1ой, р. Но обычно разрядность является боль достаточна большой и для преобразований в поле 6р (р), чта егце ольше уменьшает преимущества перехода к 2 Лр"). Ситуация для произвольного д аналогична и опксывытся следующей тоеремой. Теорема 6.6.1. Обратимое преобразование Фуры дмгнм и над кольцом 2)(д) сущестгует тогди а талью тогда, когд! и делит Р— 1 для гсгя простыл делынелей р числа д. сл ча, Лагазалгельсаъю.
Сначала мы приведем доказательспю для учая, когда д равмо степени простого числа. Затем используем китайскую теорему об остатках, чтобы связать этот случай со случаем произвольного числа Ф Проще всего доказывается обратная часть теоремы. Длина и преобразования обратима, тольио если н и 4 шанино просты, так как .-'= 14- ЕФ и, следовательаа, любой делитель чисел и и у должен быть и делителем единицы, так что он должен равняться единице.
Далее, тжтрема 5.1.5 утверждает, что если порядок и элемента ю вза. имно прост с 4, та он делит Р (Р) = (р — 1) р — '. Следовательно, преобразование Фурье в кольце 2)(р ) существует только на длннак л, которые делят р — 1. Теперь докажем прямое утверждение теоремы.
Полагать р равным 2 смысла нет, так как тогда л равно 1 и утверждение тривиально. Следонзгсльао, р — нечетное простое число н согласна теореме 5 1.8 существует элемент ч порядка (р — 1) р '. Для зг -< любого делителя Ь числа р — 1 полежим ю = н; тогда порядок элемента равен (р — 1)(Ь Таки обр ом, дл любого делитеяя Ь чис.ча р — 1 имеется элемент м этого порядка, н остается доказать существование обратного преобразования ФуРье Для этого запишем — г ~ю™У —.. ~~ м ' ~~~ м щ ь-ь а=о г -о 2!3 отображения кольца х(!ц) н прямое проичвглеяие к((Р, ,) х х гг(р,') х...
х 27(р,') Условия существовании преобразовавггя Фурье в польце 87(4) сняззны с условиями существования преобразований Фурье в иажлом иэ дг(э г г), так что услание делимости р, — 1 на л даллгко выполнятьсз для всех !.П По-видимому, описываемое теоремой 6.6 1 преобразование Ф!Рье в целочнглеяном кольце 7ДФ при сообразном 4 может име~ь весьма аграничшпгые приложения Тем не менее окн могут в не. которых спеггпальг~ых случаях оказщься весьма подходяп!ами. Рассмотриьг, например, разложение 2 + 1 = (257) (427825536!) = р р В кольце 37(2ы т- 1) существует преобразование Фурье длины 256, так как 256 делит и р, — 1 и р, — ! Это преобрвзоваиае при разрядно тн чясел в 41 бнт обесп чивает точность вы шслепий ч 40 бит Кольцо допускает БПФ алгоритм Куля †Тью но о новзнню лва дрнф е ка ерепол ения леш чч ть ае с равонством йм = .
-1. Элемент 2 неяшя н этом случае всподьзозть а качестве ядра преобразования, тзя как парякок 2 равен 80, а порядок ядра должон быть равен 256. Следавзтельно, уиножени» не могут быть реализованы в виде циклических сдвигов. а явлю. ютгя умножением 40-батовых чисел общего вида Таким образом, такая конструкция приводит к процедуре 256.точечной цикзиче. ской свертки, содержащей примерно 266 .!. 256.1ой, 256 умножений общего типа для 40-разрндных двоичных чисел с тачношью а 40 битовык разрядах По сравнению с комплехгным БПФ-ал. горнтнам для 40-разрядных двоичных шсел эта процедура являетси а более точной и содержит меньшее число умножеаий Если Р = г, то сумма по й равна л. Для г чь !' имеем -и -п)ь !— ь-з Так как оба индекса! и Г меньше и и !' — г ть О (шоб к), то вы- ' ражение справа равно нулю.
Таким образом, — ~~~ и м1'ь =- — ~~„ог(лби ) = ог, что н требовалось доказать. Теперь предположим, что д .=- р~'рз' ... р, С Воспользуемся «итзйсиой теоремой об осткгках н алгоритмом Гуда †Тома для 6.7. Числовые преобразования Шевиллн Ческе Шениллз (как правило, простые, но ие всегда) в нестрогсн определении задаются как числа 4, ддя которых в кольце г'(В существует преобрааование Фурье по одному основанию тл„больших длно преобразования Числа Шеаялла связаны только .торашнмн г~реабразоваггггямгг Фурье и не имеют спец.гальнаго гсогзет~ ио-числового значевия Таблнца этих чисел пастроеа. имч с помощью ЗВЬВ приведена иа рнс. 6 3.
Если элемент ю кольца 284) имеет порядок, равный степени много простого ча ла, то преобразованяе Фурье У, — '. 2; мною й — О,, л — 1. г=з 6.7. Ч сл вис сР обРвзсвзв Ш илвз 215 в этом кольне удобно вычислять с помашью БПФ-алгоритма Ку. ля †Тыч по одному основанию. В приведеаной на рис. БВ таблияе для каждого 0 указан порядок, апределвющай длину преобразования л, равную степени малого простота чиода. 8 14 02 М 21 1О 2'1 зи ю зя зю из Яз си 1019 за 174 '1 * юз О5 ги г 1*1 за 81 21 16 124 зю 37, 121 16 2 1 121 11 12 41 1Ю о, з. 14 Я1 бю Зз 11 З 41 3 41 21 29 зз зва пс и 4144 Ри .
8.5. Тьблииз злозрзписв Шавилва дзя ср сбрвюьав 3 .1 1Ю1 11 и".1 зм гм ' 3127 3 5 из 4 01 4И9 ая 14 ю ю. Юз ю Ю9 за оз О 9 21 ио ио ЗО 11 2 и зз юс 11Ю юс Юз 2юз згз 14Ю зззз выз 13751 ЫЮ7 15 ЗЯ заюз 16073 зы 93 зыы Юзбг Ю169 15 1749 1Ы33 25601 28751 г881з 50871 32Ю7 32251 згзю ЗЫО1 32537 юзш 3 1609 ззыз 39361 40961 52439 63Ы3 Ызсз 65001 И353 64511 65089 ЫЮ1 65171 65269 65281 65Ы9 ю.ю 1З 0 13 7 13 3 13 9 ыс ЮО 14 О юо 14 0 юс Ю.2 ыб 14.3 ыз 14Л юо ю.а 1З,О 15.0 здо мо 15.0 15 0 15,3 15.3 15.7 15.9 15.9 15.9 16 0 юо 16.0 16 О 16.0 16 0 16.0 16.0 1ЬО 8262 Ы73О 1аюб 15ИЛ 1ИЮО 16072 16 Ю2 16ЧЮ 16362 163% Ю496 18432 25ЯЮ 28 Ю гав ю зса70 зготь 32250 32256 ЗЫОО 32536 32562 Зизю 48 3юбб 409Ю 52488 взнес 62500 250 64 3 Я ь4Ю г 65088 65100 65170 65268 96 бззы 65 520 243 625 2401 1024 1гв, ыз ю М 25 83 16 Ызз 20М 1024 525 2401 143 729 123 512 25 49 ыз З2 16 зииэ 3392 аю Либ 15625 125 729 Ю24 61 25 343 49 32 вз 36 З1Е Г .
В В !в!леан! зсурр гю «есз * Для вычислений в кольце 2)(д) необходима знать вычеты по модулю Ф которые в общем случае вычисляются не столь просто, как в случае простых чксел Ферма ичи Мерсенна. Это является одним из основных педостагков чнсловык преобразований Шевилла; возможным выхопом является предварительное вычисление и табулирование вычетов по модулю простых чесел. 8.8.
Алгоритм Препараты — Сернейта Так же нак вычисления н поле «омплексных чисел вкладываются в пела Галуа, вычисление в полях Галуа можно вложить в поле комплексных чисел. Для вычисления свертки в СЕ (й) можно носпользаваться комнлексноэначным БПФ-алгоритмом. Предположим, что в поле СЕ (д), где д равно степени простого числа р, требуется вычислить произведение з(х) = й (х) Д (х). Представим элементы поля СЕ (й) в виде многочленов; тогда провзведенне элсмсптоо поля в СЕ (Ч) и жиа интерпретировать как свертку мвогочленов по модулю непрнводимога многочлена р (х), Вычисление всех вычетов по модулю етого неприволимого мнагочлена можно отложить до тех пор, пока не будут вычислены все свертки. Исходная свертка при этом превращается в двуыерную свертку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
