Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 36
Текст из файла (страница 36)
Запишем элементы й, и б! поля СР (й) над простым полем СЕ(р) в виде мвогочлено» й, = ш йггз и бг = ~ ~бггз, ч !=в ! где й = Е", а й,! и яц обозначают неотрицательные целые числа, не превосходящие р — 1. Тогда линениая свертка векторов й и б равна — ! з! =- Е яьб! а = а-з †! †! †! 2,' 2,' йзк(гг з! ! а +и (пюб р)(шоб р (х)), з=е ! .е! -о 3 ычз 217 Каждый элемент такой двумерной таблицы «редставляет собой число между О и р — 1. Тогда ! — ! з! =- 2з зн з (шобр) (!ной р(л)).
Вычисления вычетов делаются иа последне м этапе вычислений, причем сначала вмчисляются вычеты целых чис чисел по модулю р, ! — ! а затем вычеты многочленав з о6 = ~~ з г, '', = ~~ зц з по молулю много- члена р (х). Сложностью вычисления вычетов можно б ирене речь сра нению со сложностью вычисления двумс ной с у. р у р ку можно вычислять в любом подходюцем сурроу ср о свертки. гатаом поле, например в пале вещественных или поле компл плекс- ага Вмесго паля комплексных чисел можно использовз р тное поле любое подходнщее конечное по. е, ть как сурполе, даже с харак- тсрнстиной, отличной от характеристики ис исходного поля.
На- пример, лл» свертки послсдовател ностей над СР (2), длина л которых меньше, чем половина простого числа Ферма 2 -1. 1 ббб37), можно использовать поле СР (2 -1- 1). Длн этого доста- точно проинтерпретировать последовательность нал СЕ (2) как ° оследовательвость целых чисел, которые прниима н, р е н . Длина линейаой свертки таких целочисленных слс послеловатсльностей, хотя н больше л, ио не преаос 2, «одвт, к, о вычислить кзк цик- : дователыго, эту линейную свертку можно шзч ланскую свертку в поле СЕ(2 -1- 1) с последующиы приведе- нием целых чисел по модулю 2. мо н Для вычисления пиклнческой свергни в н СЕ(2 -1- 1) ж о воспользоваться любым ло устнчым б оле ак как в поле СР (2" -1- 1) «ущжтвуст преобразование урье длины а, разной любому делителю числа 2 , т возможных схем в , то опной иэ вавка Фу ье и те ем вычислений валяется использование преабр „р оремы о свертке. Преобразование Фурье при р разо- этом можно нычнслять по БПФ.алгоритму К вЂ” Т ули — 'ьюки, содер.
у (л ) оа, в умножений и стольк же сложений в поле Р ! -1- 1). Далее, тан как элементы поля СЕ (2 "; 1) оп ° Р72 -'-1 скаюг запксь в виде(т -1- попу. вость такого алто итм с д (т -1- 1).разрядных двоичных чисел, то слаж. р а снертки сравнима со сложностью в поле комплексных чисел. где р — характеристика поля, а р (х) — простой маагочлеи стэ пени т. Определим двумерную целочмслеиную свертку равенство -! -! 1=-О, ..., л — 1, зп. = 2, 2, йыыи-ю ! - '» ' — О, ..., 2 — 1.
з-а ! -е Задачи з.!. Ба ч пя 212 ЗИ Гл. б Вмч « в суррщ",и мх пщгял б. П р г чюкке с» н, р люущщ р пх умющвпи» и ыа. 6.2.. Пр р, ч есг др р бры Фур а пые ОЕ(2' .(- 3) ы» а «: дыйпи я 1 б з « «ап пч мн сдввгама. дв йки В.з. и рад к ы х в кщ и 2166) р чсюр . В ать (4х4) ма. р» 4- юпп прюбрыюэх Фур м у браг!юг пр гбр зова ия. Фуры сбрыо . К кне свой«в ыщгся св ркммиу По ему3 ВА. а. Ч»у ра пор до л га 2 про Ферма ОЕ (17)з 6.
О З.гач чанй ВПФ- щар Ку — Т щю л ющгвзл щ лва д . БЕ(17) С с а у во ылйюлр эо авырлпау . О 4. ючгый БПФ- люрпгн Куп — Т по о:юнакам ды, . В ОГ(17) нм "г р* н )72= П Явля щя лн П прщгм сом гюлю О г 16- й БПФ-элгоригм Ку и— 66 пу ь о= (2а-1. Ч (2 -!. 1).
ч у р п р д в л мюга 2 в юли!в Ъ (4У б. В и ыгь б. о и й БПФ. л р В грыа пале ОЕ(31). . В юле ОГ (31) ы ммп -1 юдра в го н р я. Чему ра ел ор д злы!мха 1-)а) в ра ш р» БЕ (31') ищя1 г. Ч у рван! пппб л щ я лапу л д а прпмравсааннв Фурье ' л. О ъ струн уру З.гачюксго БпФ ла Ое (31') 6.7. Пюаз, и!рядок эл н нщ 1-1- ) л «омплекснмх чнсы Пер. ын Ое 62м — 1)') рамн 136 Бг зпыв., ла юм пюе сук ствуы пр бр «и Фуры дл нп Ыв Опию ь ру уру б щрого лг рыка В.В, П р б- щюл й БПФ- юргин В Фраде лля юл» ОЕ (41).
(Е о- В.э. В л ОГ ((2'7--1) ) сумм у 17- рюбрвэоиан Фуры ю рюбр эованиа Фур е в ле ко . ек мх часы. Вм бюк. 6. Сх Л К рыущеязщ МХу ЮМ Ийящщжв»й, 1б.м » е приор юваиы Фур в в ы ком симл часы м с по' . К «овм до.м и бмг раю дющь в пр юдура скр лля г ю б ОЕ 62' г — Б*)7 В.36. В П рыр е Фура *. О сщь, и х эг пр брйзованнэ щк г бмг м помощ б. С л кп у а ий в й о «.уррю гн м в л* р бу я пр В.33.. ПОНЫагЬ, ЧГО О О ЛМ вЂ” 1 НМ В В Лз ОЕ (2зе Ф 1) 32 раап ар я.
Замечание П б а ) Глава 7 БЫСТРЫЕ АЛГОРИТМЫ И МНОГОМЕРНЫЕ СВЕРТКИ Подобно тому, как определяется одноиернзя свертка, можно определить многомерную свертку. Для многомерных таблиц данных можно пать полезные во мвогнх отношеняях определевия динейвой и цякличесхой сверток для любого представлнюьцего иншрег поля вычислений Иногоыерные таблицы данных и много. мерные свертка создаются нсхусственным образом как часть алгорптььов обработь.н одномерных векторов данных, Иьогочер.
ные таблицы данных вьзнпкакт также естественным образоль во миоыьх зада ах пвфро ой обрэбо кн с г а. в, в и н задачах обработки нзобралсею й. например фотография, поаьчеяиых со спутиаьов, и медицинских взооражеипй, в ток шоле рентгеаограим, в задачах сейсмографии и электронной микро. скопин. Глава начинается с гнездового метода построения быстрых алгоритмов вычисления многомерамх сверток нз быстрых алгоритзьов для одномерных сверток Затем рассматривается способ построения бмстрых алгоритмов вычисления одномерноэ свертки путем вреыеаного отображеаня в многомерную свертку, — про.
цедура, извесюшя под названием а»горятм Агарвала- Кул« вы чнсления свертки Алгоритм Агарыла — Кулп для одномерной циклической свертки представляет собой мошиос дополаенне к раавигым в гл. 3 методам. которые становятся чрезмерно громоздкими для ллииных сверток Он позволяет строить алгоритмы для дль нных сверток из коротких сверток Накоьец, последняя половияа главы содержит методы, развитые сььепььально для вы.
числения двумерных «верюьь 7.1. Г эзо Ра и сэ Г Заданную (йь' к у )-таблицу б - )б., гь ь' =б,..., Аь' — !; ь" =б, ..., Аь" — 1) назовем таблицей данных, а (ь'кй')-таблицу ; =О,..., С 1; Г=О,.... А — И назовем таблицей фильтра, и вычислим ((ь' —, йь' — ))х(ь" -ьф Ю вЂ” 1))-таблицу сигнала ь'=б... ь'т-йь' — 2, ) !'=б, ..., ь" юйь' — 2 задавая правила вычнслонии ее элементов равенствами — — ь" =-О ..
й'-~.дь'--2 Это определение можно непосредственно перенести и на свертки большей размерности. Однако мы ограничим рассмотрение в ос. во иом дву рпымн ь) свертками, так как е иден легко обоб. щаются на случай произвольной размерности. Двумерная свертка может быть выписана в терминах много. членов; полииомиальные обозначения можно вводить как но любому нз измерений, так и по обоим измерениям одновременно. Таким образом, таблицу б можно записать нли как вектор много. членов, л" — ь бь (у) = ~ бг, ту', м.=о или как миогочлен от двух переменных и' — ьэ"-ь б(х, у) = ~ ~ бг ь.у'х'. с*=о и — с Аналогичные обозначения можно ввести для д н э: с -ь.н.— у (у) = д' уьчь.у', з (у) = Х я,.у', о г" о 7.1. Гиездовыс алгоритмы свертки Двумерная свертка представляет собой операцию, задаваемую на сыре лвумерных табляц Ее можно предсьаплять себе как опе.
рацию фильтрации, в которой одна двумерная таблнпа предсьав. ляет собой двумервый фильтр, через коьорый пропускается нто. рая дв)мерная таблица и на выходе которого форчэруегся выхол. ной двуььерььый сигнал Такого сорьа ооерацин возаикакп в эата. чах обработки изображений. х — ь ь.=ь у(х, у) = г=а ь=э с ч.и — г ыьэ" .г '(" у) = хчз дюь э,,узх'. ь'-о ь"-з 1 ы и 222 Гл. 7 Быстры злюр тмн н и агом рннз аяр ан Двумерная свертка в этих обозначениях может быть записана или «ак одномерная свертка многочленов, л. †з (у) - Е уг*- (у) йь (у) илн как произведение многочлемов от двух переменщах, э (х, у) = у (х, у) б (л, у).
Двумерная циклическая свертка также мажет быть выпнсана в терминах многочленов, а именно, 5 (х, у) = у (х, у) б (х, у) (гпоб х" — 1) (гпоб у" — 1), где я' ве обязатечьно равна яС Для двумерной циклический свертка выполняется теорема о свертке Если О и С обозначают двумерные преобразонани» Фурье таблиц д и й соответственно и 3„ ь- — бью ОРьс м, то 3 является двумерным преобразо. ваиием Фурье таблицы з.
Следовательно, для вычисления дву. мерной цнклнческои свертки можно пользовать*п двумерным ВПФ.алгоритмом. Уамяо, конечно, ппльзовзться и прнмыми ме- тодамн вычисления двумерных сверток. Имеется много способон прямого вычнсленвя двумервой ли- нейной нли пин.чическай свертки. Простейший путь состоит в том, чтобы попытаться вычислять ее как последовательность адномер. ных гверток сначала по стропам, а затем по столбцам Заьгетим, однако, что в формуле и' — 1 ! э" — г зг,г.=- ~ ~ ~уг ь,г «.уььь.~ ь'=.з ь"-з выделенная в квадратные скобни линейная свертка по й" лолжиа быть вычислена для всех У и йц Понять двумерную свертку легче, если выписать ее в виде свертки мяогочленов, я — г з (У)= йшйн,(У)бм(У) г =-О,..., У У з =а Из этой формулы ясно видна реализация двумерной сверткя как УУ' произведений многочленое, каждое из которых, в счею очередь, нвляется сверткой, требующей С"У" умножений Всего, таким образом, получаем УМУ'У' умножений, что, конечво, недопустимо для болыннк задач, так по нужны быстрые алто.
ритмы. Хотя рассмотренные в гл. 3 алгоритмы свертки строились над попами, оии нв саном деле выполнимы и в некоторых колыжх, в частнсюти, в нольцемногочленав. Следовательно, свертка много- г.г. г юз злг р нми членов может быть вычислена любым вз этих быстрых алгоритмов. Сложение в этих алгоритмах становится сложением мвогочленов, а умножение — умножением ыяогочленов. Эти последние умно. щения, в свою очередь, являются свертками и могут быть вычислены с помощью быстрык алгоритыав свертки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
