Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 53
Текст из файла (страница 53)
та» его в переопределенном остатке йщ (х) Пусть очи (х) = й (х) (шай .г' -1- 1), й'и (х) = (х 1- 1) д (х) (шой х' -1- х -1- 1), Рг' (к) = (х — 1) ! (х) (шой х' — х -1- 1), йгп (х) — х й (к) (шой х' -1- 1) Тогда вычеты йг'г(х) переопределятся па правилам йгп (х) = 22, — й„ йгг! (к) = й -1- йз — й, йгзг(х)= — й рй гй й '! (х) =- й,х' 4- й,х Ш йи для вычисления каждого из сстатиав вгп (к), згг' (х) и Фн (х) потребуется два умножемия, а остаток д'г (к) надо вычислять как линейную свертку с последующим приведением по модулю х' -1- 1. Эта линейная свертка представляет собой прохождение 4.то геч.
ного вептора через симметрический фильтр с тремя отводами. й.чгоритм такой фильтранин с шестью умножениями мы уже построили. Используя построенные фрагменты, можно формировать ал. горитмы линейной свертки для симметрического фильтра с пятью отводами. Предположим, что требуется построить алгоритм вычисления последовательностя на выходе такого фильтра, если на его вход подается 6-точечная последовательность. Тогда выберем ш (х) = х (х — 1) (х -1- 1) (к — гю) (к' -1- 1) (х' †.с -1- 1] к х (х' -1- к -1- !). Каждый из первых четырех многочленов приводит в алгоритме к одному умножению, а каждый из остальных трех — г двум умножениям.
Окончательный алгоритм будет содержать десять умножений (1.67 умножений нз один отсчет на выходе). Предположим, что требуется пропустить через этот же фильтр 14-точечную последоватетьносгь. Тогда к исготьзовавшемуся ранее кнагочлеиу ш (х) добавим еще одни множитель, хе ф , хг Эш добавит в алгоритм еще шесть умножений. Окончательный алгоритм будет содержа~а 16 умножений (1.14 умвожений на один отсчет на выхозе). В общем случае необходимы симметрические фильтры с числом отводов, большим пяти.
Следующая теорема говорит о том, как надо выбирать модули для того, чтобы строить алгоритмы для больших симметрических фильтров из малых симметрических фильтров. Теорема 6.4.!. Пдсп ь чгшнов число 1 лв мвныив южною п и пугть г (х) обозначает запашок ош деления симметрического ггвсгочзгнп й (х) опвлвни ! яа спммвтричггкий много«вгн пг (х) гмгввви и над ошсвпым полем б. Тогда г (х) можно эапнспшь в виде г (к) = ( (к) г' (х) (шой ш (х)), гдг р (х) првдсшпвгквт собой симметркмскмй мкшочвгк сшвпвпп л- 2 и ((х) — -нексшормг1 мншочвгн нпд основным повем и (нв зависящий, свпуовппмвьно, ош коэрфичигншоо мяогоыша й (к)). Докпзашгвьсгпвс.
Без потери общности можно полагать, что иногочлен ш (х) приведен. Так как т (к) является симметричесним 11 з .еш э. ЗЗЗ Гл В архитектура фильтров пр Юраз г Ю сг с» ' тоню ив а гыос га с 4 многочленом степени и, то т (х) .— х"т (х ') Если л = Г, т' положим т' (х) =- т (х), в противном случае, пусть т' (х) = т (х) ( х'-"т (х) Этот многачлен является симметрическим степени г, так как «'(т (х — '\-~-х-гь"т (х ')) = х' "т(х) 1- т (х). Определим многочлен у' (х) равенством ху' (х) = у (х) — у,т' (х). Многочлен ху' (х) при делении иа т (х) дает тот же остаток, ч и многочлев у (х), но многочлен у' (х) является симметрически и его степень равна четному числу.
которое по меньшей мере н два меньше степени иногочлена у(х) Если степень мнагочлен* у'(х) не меньше , то этот процесс можно повторять го тех пор нека ве волучим мнагочлен г'(х) степени и — 2. Тогда оста ат деления мнагочлсна хгт †' †'гпгг'(с) на т (х) ранен остатку деления у (х) на т (х) Для завершения доказательства положи ) (х) = Л.м, (х — +» '1. О Теперь мы перейпем к алгоритмам для кососимыетрачески фильтров. С этой задачей мы справимся значительна скор указав, квк алгоритмы длв симметрических фвльтров ножи превратить в алгоритмы для иососимметрических филыров. Теорема 9.4.2.
Луста кососиммстри«гскиб фильтр содсржд Е отгадает тогда, если Е чгтио, гпо глза задана филотронии можг быте, решена по алгоритму для симмгтришского фильтра с Е— отгодами, о если Е нечетко, то злга задача может быть ргигг по алгоритму дш симмгтричгсюго фильтра с Š— 2 оюоодами.
Доказатггостао Предположим, что многочлеа у (х) аписы вает «ососнмметрический фильтр с четным числои Е отвода Тогда у (1) = О, так как ус = — уь,, для 1 —. О... (1.12) — ! Следовательно, (х — 1) делят мнагочлен у (х). Определим филь у' (х) = у (х)Г(х — !). Ясно, что многачлен й' (х) задает симметрический фильтр с Е— отводами. Симметричность фальтрв вытекает иэ тога, что равенст у (х) = — х" — 'у (х-') влечет за собой равенство (х — Пу'(х) = — хс-'( — — 1) у' ( — ), или равенство у'(х) = х"-'у'( -'). Таким образом, фильтр, описываеиый мнагочленом у (к) эквивалентен фильтру с многочленом у'(х), эа которым следу !от каторочу предшествует) фильтр с двумя отводами, опксываеый чногочленом (т-- 1) Теперь предположим, что многочлен у (х) задает касосимме.
тояческий филыр с нечетным числом Е отвалов. Тагла 1 н — 1 являются корнями многочлена у (х), так как центральный коэф. фгциент равен нулю и у ( П = г' Т', у, — 9...) ~ ( у', у, + Е...) =-. О. Следовательно, макно оаределить симметричный филыр с Š— 2 огвадасв, задавая его многочленоч у' (х) --. у (х)((хз — 1). Таким образом, филыр. аяисываемый мнагачленоя у (х), эквввыентен фильтру, эадаваечажт миогочлено» у' (х), катароьгу пведгг~ествует (или за катары» следует) фильтр с многогленоч с" — 1 О Фильтры, задаваемые многочленами х — 1 илк х' — 1, приводят к некоторым дополнительным сложениям на входе или вм заде.
Следавательяо, изменяя соответствующим образом матрицу пргдстожеянй или матрицу пастсюжеиий. мы преобразуем алга. (исти для симметрического фильтра в алгоритм для иососимме. грнческога фильтра. Как всегда. если этот адгоритм используется в четаде перекрытия с суммированием, то ега следует брать в форьсе алгоритма для линейной свертки. Напротив, если в кон. струкции используется метод перекрытия с накоплением, то следует воспольааваться даваемыч теоремой 9 2 1 принципом твгнсфармаций для преобразования алгоритма в аагарши сек. шюяаай фитьтрацин Как оказалась, тот же метод, который позволяет свести за. дачу для кососичметри юскнк филыров к задаче для симметрических фильтров, позволяет ори нечетном воле 1.
отводов свести задачу для симметрического фильтра с Š— 1 атводачи к задаче дяя симметрического фильтра с Е отис~да гн. Теорема 9А.О. Если Е иаиогяо, то алгоритм дгв симметрического фи ютоа с Е-~-1 отгадали пшуи гогов из алгоритма дгя с мистри«еского фичыра с Е отгодани бгз допогнитггьтих уиножгиии. Доказатгхьапао. Пусть (1. 1) точечный фвлыр задается симметрическим мвогачленом у (х) нечетной степени Е. Тогда у ( — 1) =. О, так что (х -г !) делит мяогачлену (Н Следовательно. у бф = (х -~- 1)у' (х), где й' (х) — саччетричгский много шеи сте. пенн Š— 1 Таким образом, фильтр, задаваечый чногочленои у !т) может быть реализован в виде каскада фильтров, задавае. мых сгногочленаыи х -1- 1 и у' (х), без дополнительных умножений 11* (г, м з.
е о! 'у,! о кг,о о1 о г, г. г, о )уя о! Зев Гл Э. Архитектуре фнз ро паеоау зоы ка 9.5. Фильтры прореживанмн и итерполяцмм Фильшром лрареживанпл назынаетса КИО.филыр, катар вычисляет только каждый г-й выходной отсчет; часта г равна или 3 Все прочие выкадиые отсчеты нежелательны и и давляютсн, даже если они вычнслнются. Можно надеяться существование более простых алгоритмов, не вычисляющих н нужные выкадпые тачки. Филыпр инлмряоляции действует пр тивопаложным образом.
отсчепз на выходе такога фильтра фо мируются с большей скоростью, чем иа входе. Прореживзющи и интерпалирующий фильтры иногда называются фи,гьшро с подавлением и филыпром с восстановлением соотвсгственно. Конструкпии црареживающего и интерпалкрующего КИ фиаьтров аналогнчкм общим конструкциям КИО-филыров. О пако, их специфические особенности можно использовать дл построения более эффективных алгоритмов. В первачу слуг более эффеитивные алгоритмы можно строить из-за выбрасыва ных выходнмх тачек, а во втором — из-за выбрасываемых вхо ных точек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
