Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 41
Текст из файла (страница 41)
7.6, Свертка в паднномнцльных расширениях полей Еслн ч — вектор с рацвональнммн компонентами, та «омно. кенты — 1 1'„= д,' еаоь А=О,, л — 1, г — з его преобразован«я Фурье принадлежат палго С(е), в более общем случае, еслн «омпаненты т принадлежат (7 (е), то кампо. ненты его преобраэованнп Фурье также па«надлежат () (е). Пусть степень кругового я«опт«лена, караем которого является е, равна и. Тогда «аждый элачент в С (е) заннсывается 247 в виде многочлена над С степенн, меньшей и. В полнномнальной записи преобразован«с Фурье имеет внд -! У„= Х'„хгзаг (шоб р(х)), 2=-0,..., л--1. 7=-4 Эта формула вычнсляется проще, так как умноженне на х сво. днтся к операциям над нндексамн, а прнведенне по мопулю р(х) содерхснт не более и сложений.
А(ажно воспользоваться любым БПф.алгорнтмам, например БПф.алгорнтмом Кули †Тью, но все умнаженяя представляют собой умноження нз х, н, следова. тельно, требунл для своега выпотнення не более и вегцественных сложений й ае содержат вещественных умноженнй Аналогично, каждое слажен«с является сложевнем многочленав н выполняется с и неществсннымн сложеннямн. Прнменнтельно ко вкоду с рацнональнымн компонентами пре абрэзованне Фурье можно рассматрнвать как отображен«с век. торов нз мнагочленов первой степе«« в векторы нз много«пенса степенн и — 1 В более общем сл) гас, преобразован«с Фурье в такой трактовке отображает векторы, кампонентамн «отарых служат многочлены степени и — 1, в векторы нз многочленав степени и — 1.
Справедливость теоремы о свертке не зависит ог того, как именно представлены числа в данной арнфметнчес«ай системе. Слга применима в равной степенн как н векторам, компоненты которых зал«саны в полнномнальной форме, так н к векторам, компоненты которых записаны а обычном виде Следовательно, для вычисления цнклнческай свертки послсдовате.тьностей с рзцнональнымн «омпанентамн, з, = ~ Фн †зн ыожно ваять преабразазанае фурье векторов й н д е поле С , вычнслнть в частот. ной областн покомпонюгтное про«заеден«с 54 = 6404 н взять обратное преобразование Фурье. В пол«нам«аль«ой записи поля С оба преобразован«я Фурье пря этом не содержат умно.
жевнй. Покомпонентнас спектра.чьное провзведенне, однако, те. перь валяется провзведеннем многочленав по модулю р(х), н, следовательно, требует большого чнсла вещественных умноженвй Сложность вычислений переместилась с одного этапа ва другой Усложнение вычнслення спектрального про«введен«я сводят на нет зынгрмш, полученный в преобразованиях Фурье. Позже мы увнднм, что прн вычнсленнн двумерной нннлнчвской сверткн все же можно получать вы«треш ат полнномнального предста« лепна. Напр«мер.
пусть л =- 64; круговой мнагочлен равен р (х) =. : — — ле -1- !. Элементы поля ( (ьй представляют собой много«лены сгепенн 31 н заданлся списком нэ 32 рацнональных чнсел. Каждое Хчэ Гл. т. Б с р е щшр и з мшпи Э р произеедеаие 5э =- Оз()ь является произведением многочленоэ по модулго х" 1- 1 Этот многочлен «еприаод«м. так что для каж. дога такого про из аеас «на необходимо по меньшей мере 2 32 -- 1 эещестзенное умножение. На сэмом деле число умножений сущестиенно больше 63; практически используемый 32.точечный алг ритм, приведенный на рнс, 7.7, содержит 147 умножений, Таким образом, каждая из 64 коыпоиент преобразаэания Фурье требует 147 аещсстаснных умножений Эта существенно больше, чем число вещественных умножений, необходимых при не«аль.
зоэанни абщепринятога для этага с.чучая ВПФ-алгоритма. Нз самом деле эелнчины бз не нэляюгся пронзаольными, а должны удовлетворять некоторым ограничениям, связанным с тем, чта обратное преобразозанне Фурье должно иметь рацио. нальные компоненты, 64 компоненты з, обратного преобразоэания Фурье представляют собой 64 многочлена, каждый нз кото. рых задается 32 ра|1«опальными числами. На самом деле 3! из этих чисел разны нулю, та« «ак каждый нз мкагочленаэ нэляется многочленом нулеэай степени Это позволяет аыписать ограниче. иия, которым дплжны удовлетворять вели гинм 5ю и окажется, что 64 из 147 этих величин нет надобности эы гнслять Детальное иыписыэание этой пропедуры, адаако, приэодит к алгоритму, очень похожему на алгоритм, осноианнмй аа китайской теореме об остатках, который праще аыписап непосредственна. Поэтому мы ие будет прадочжать рассмотрение втой процедуры В полиномиальиом расширении поля, б , можно определить и более корщкие преобразаэаиия Фурье, Предположим, чта число и является составным: и =- л'»'.
Тогда ядточечное преобра. занан«с Фурье определяется раненстиом У, = Е (х" У' ~., й = О,..., я' — 1, г=э где арифметина шдается «ак полиномиальная «рнфметика по. ли С„' . ядро преабразоэання теперь вместо х равно х" . При га. ком определении преобразования Фурье, так же как и ранее, существует и обратное к нему преобразаиание и спразедлиза теорема о сэерткс.
7.7. Пали«амиальиое преобразование Нуссбаумера Преобразоэаяня, построенные «ак преобразозання Фурье а па. лннониалыгых расширеяиях полей, заслужнааюг самостоятель. ного исследоэаияя. Мы определили их для поля рациональных чисел, так что нмффициенты всех многочленаэ радианальны. Так как построенное преобраэоэание обратимо, то ано задает некоторое мнажестэа таждестэ длк многочленоэ с рациональными «оэффициеитами. Тождества остаются спразедлиныма, даже если з качестве наэффнциеитоэ многочленап допустить эещесгэеншзе (или «омплексные) числа В данном разделе мы эноаь обращаемся к изучению полина миэльнога преобразоэания, но на сей раз мы будем его рассматриаать не кап преабразоаанне Фурье, а кэк самостоятельное преаб.
разоэание. В кольце много«ленси по модулю р (х) полиномнальнае преаб разоэзние определяется равенством Уэ (х) = д„' в (х)м а, (х), й =- О,..., и — 1, г=э где в (к) представляет собой элемент поряд«а л и умножение, «онечно, яиляетс» «альцеиым умножением мнагочленаэ по мо. пулю р (х). Наше рассмотрение будет ограничена случаем, когда в (х) =- к и нногочлен р (х] делит х" — 1.
Как предсгаэляется, никакие другие случаи ие именя ка«ого.либо реального прантического интереса. Определение 7.7.1. Пусть р (х) — некоторый многочлен сте. пепи ш и пусть миогочлены а,(х), г †. О, ..., л — 1, над полем Р имеют степени не более гп — 1 и представляют собой компоненты подиномиального нектара.Поли«о««аль«ил пресбразсеаяием этого вектора назыааетсн вектор с кампоаентамн Уь(х) = ~, 'х'за, (х) (жабр(х)), й=б, ., л — !. Е Иолиномиальнае преобразоээние легко вычислить, так как оно не содержит умножений элементов пальца общего инда. Умноже.
ння на х'з тривиальны, и, если многочлен р (х) выбран тэк, что эсе ега коэффициенты разны О, 1 илн — 1, то приведение по мо. дулю р (х) также иыпалняется одними сложениями. Ценность палииочиальнага преобразозаиия обуслаэлнеается двумя теоремами: теоремой а сущестэоэанип обратного пргобразоэаяия и теоремой о свертке. Оба зти утверждения, конечно, сразу эыте«ают из яозможнасти интерпретапни полнноыиааьного преобразоэаина как преобразаэания Фурье. подобно тому, как эта делалась а предыдущем разделе. Тем не менее поучительна пать более прямое доказательства.
Пусть и обозначает наименьшее целое числа, для ксторага Р (х) делит х" — !. В даказательстае следующей теоремы используется тот факт, что если многочлен и(х) делит х" — 1, та 2Я = 1 (пюй р (х)1. 2за Г .7. Бы Оы»лг Оь. ы ни ога ереы ер для произвол» »аго многачлена ( (х) выпалняетсл равенство )7 »,! !) (х)) = )7. ! ! ()7„, ! (( (х))) Начнем с простейшего случая, когда число л просто. Теорема 7.7.2.
!»редпояожим, ало мнагочлел р (к) нид паяем Р степени т делит многа»ни к" — 1, причем числа а яеяягтся ьростим. Тогда лошномиагьный вектор ч (к) длины н, кампонен. тами которого яьгяются много тены слылени т — 1, и его пали. номиальнае лрсобразоеа ие У (х) сешаны соотношениями - ! У»(х) = ~~ хыо,(х) (люб р (х)), 2=0,... л — 1, »-ь о,(х) = — ~хм-и'»У»(к) (шаб (р(х)), »=О,..., и — 1. » —.ь Доказатггьстьо. Исключая тривиальный случай, можно полагать, гтп степень многочлена р (х) равна по меньшей мере двум. Вычисли» правую часть второго равенства: — ! — ! Г" — ' — Ух!" Я»ыу»(х) = — Ъ хю — "'" ~ ~~~х'ьа, (х)~ (жабр(х1) = .ш л ! »=ь »=ь »-ь " †' à — ! =- — ~ ~ о, (х) ~ к!'ч т — н») (той р (х)). »=»».— ь Вычислим внутреннюю сумму.
Ес.чи ! Равна 1, то так как р (к) делит х" — 1, имеем: -! — ! — ~ к! "т '»ь = — р, кт' = — у, 1 (тод х" — !) = — ° .йи — ° 2 11ри 1, ие равном 1, воспользуемся тождеством, справедливым в «альдо: — ! (1 .-»') с» х'» = 1 — хРБ »=ь Так как г †. ! 1- л( — ! ие кратно л, та 1 — к' чи О (той х" — 1), в то вреия, «ак 1 — х" — О (таб х" — — 1). Так как р (к) лепит х' — 1, то отсюда вытекает, что шю к'» =.
О (шоб р (х)). Итак. мы доказали, что кч 1, если 1=! (пшд р(х)), — г х!'ьш — '!» —.— (О, ели !чи! (жабр(х)). Слеловательно, — к!" — н ыу» (к) = о! (х) (тоб р (х)), что и завершает доказательство. Д Так кьк » = 1, то обратное лолннамиальнае преобразование может быть записаао в более простом виде а, (х) = — — ь к — ы!'ь ОО (шо»1 р (х)), »=ь котя формальна к-т не является многочленом. Точно так же, как умножение на х выполняется с поможью переиндексапии коэффициентов н ыриведения х" по модулю р(х), умноженве ча," ' также иожно выполнить с помотью переиндексаиии казф финиентсв и приведения па »юдуью р(х), причем для исключе.
ньа к ' надо воспользоваться тем, что р х" ф р„,х -' + ф р (х) , р, = О, так что = Рь (Р " + Р -!х -' -Г Р!). Следовательно, обратное полнномнальное преобразование вычис. ляется столь же просто, сколь н прямое паливамнальное преоб- разование. Теорема 7.7.2 (теареиа а свертке). Если е юыьйе многочлекое ло модулю р (х) ть»лар .инагачлгное с кеннонен»лами з, (х), ! = = О, ..., л — 1, связи с век»лорами многочяеное, имеюи(ими ком. поненти й, (х) и д! (х),' 1 = О, ..., л — 1, соатно гноем нак- »ической сгертки многотгноз з, (х) = ~» й,,(х)д»(к) (шод р (х)), то лоликомиальный спектр Яь(х) сгяэи со с ектрами Й» (к] и Р» (х) покомлонентным произосдгннем многочяенов 5» (х) = О» (к) Р» (х) (шод р (х)), й:.= О,..., л — !.
252 Г 7. Б р»з» Г» и э изет Э Э ч Докам»тельстэо. Используя обратное полиномнальнае преоб. раэозаняе, имеем з, (х) —.- ~~~~~ дсы (х) д» (х) = — ~~» ~ хг"-'»»' — а»б» (х) д, (х) = »=» .а»=» — г — г' хм —" мб» (х) ~ «г»д»(х), »-э где х"» следует положить равным епннице, нагому что, как и ранее, все вычисления проиэвалятся по модуаю х' — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
