Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 62
Текст из файла (страница 62)
11.3. Блок-схема основана из теореме , но П.йл, но величины Ь„Ь и Ь, в итерапнях заменены нарналнзова аннымн величинами с„с н Х в соответствии с равенствами 1,,„! о о Баатветствениа рекурсия описывается уравненняь и На рис. !1 3 использована эта форыа уравнений. звт зю г,ын Э лцээ*нэ пэз нс о ч™ п х,... Ря Ы .4, А тэрэгр я э Ф " Р П ря фиксированном 1 это уравнение является уравнением автор грессионного фильтра, который может быть реализован в вй линейного регистра сдвнга с обратной связью, в отво а отводак ноторо стоят умножнтелн на компоненты вектора !.
С этой точкн зрения задача решення Ланнпй теплипевой гнете уразаеняй становится задачей построения показанного аа ряс. !! анн авторегресснонного фильтра, ва выходе которого форьгируе з д ая псслеловательность снмволов. Если теплнцева ьируется з матра валет бр ти а, то существует точно один автарегресснонный ф .
уд воряющяй данной системе уравнений Если матрица не ильтр рагима, то такнх решений может существовать много нля ае сущц ствовать яи одного Однако, алгоритм Берлекэмна †Мес всег в качестве решения лает «ратчайшкй авторегресснонный ф уд воряюшнй данным уравнениям Отволы этого фильтр описываются вектором 1, содержащим не более о ненулеаык ка понент, еслн исходная теплипева система имеет по меньшей мен одна решение, н большее, чем п, чнсло ненулевых компонент )1. г ) я, если исходная теплнцева система не имеет решений. Любая процедура построения авторегрсссноннага фнльтр является также методом решеннп рассматриваемого матрично уравнення с заданным вектором ! Мы сейчас опишем такую праэ педуру построення регистров сдвнга.
В прогшдуре не предпол гаегся наличие каких бы то нн было спецнальных свойств послед ' вательностя аь пп ..., аэ,, Пронзвольпый линейный реги сдвига с обратной связью можно задать многочлевом ((х) аб ат ных связей, х а рат ((х)=Дх", /...х"-'ш - — Дх+1, больше с и длиной Ь регнстра сдвига. Длина регистра сленга мо б степенн многочлена ((х), так как самые правые ячейк и жег регистра могут не включаться в обратную связь.
Для нестроения регистра сленга надо определять две величин длину Ь регнстра к многочлен ((х) обратных связей степевц бей 1(х) Ш Ь. Обозначнм зту пару через (Д ((х)). Нада майей, е.астр сдвпгз га с обратной связью, который прн соответствующих р '' „. ыльных у . в ело яях порождает заданную последоватшшность а„, и является прн этом кратчайшим. р с матряваемая процедура построения являетсн рекурсвнасс воэ. Для ка Д, ждого г, начиная с г = 1, мы будем строить реги р ; га, порождающий последовательность ом, ..
о„регистр сдвига чаннчальной ллинм, порождающий посчедователь б эн чнм через (Ь,. (го (х)). Этот регистр не обязательно дол. коль. жсь опред еляться однозначно; возможно существованне нес г. о шага ьвт таких регистров с одной н той же длиной. К началу г.го амеется спнсок регистров сдвига (1„Пгг(х)), (1ь )гэ1(х)), ..., (1., м )о '1(х)), Алюрктм Берлекэнпа — Месса вычисляет новый кратчайший ре. гястр (1.„, ( м (х)), генернруюшяй паслеловательность аь ., а, Длэ этого используется гамый последкий из вычисленных регнст.
роа, в котором па мере надобности ьюдифнпнруютсн длпна н весовые чножителп в отводах. Ня г.ч шаге вычпслветсп следующий элемент на выходе (г — 1) го регистра сдвига: ь,, .1 — !1 д„'11' ' и, 1. Так как Ь,, может быть больше степени многачлена )г — и (х), то некоторые члены суммы могут быть Равными нулю. Эту сумму следоьало бы записать с пределачн суммирования от 1 да Д ' †'11 ) М , однако, выбрали менее громоздкое обозначение. П сгь Ь, обозначает разность между требуемым элементом на выходе о, я истинным элементом, полученны на д усть ч выхо е самого по ле го егнст а ствига; с дне р р ( — н Ь,.=а,— й,=.а,— ~(1' О,, то Эьвнвалентно, 1, 1= ° рсдн Ь„= О, та полагаем (Ь,, (1'1 (х)) = (Ь,л, (о "(х)) ве)нпаем этны г.ю нтераввю В пршнвном случае измеяим весовые мвонштслн в цспн обратной сэнли регистра сдвига по правнлу.
Пы(х) =. (и и (х) г дх'Д -" (х), где А — элемент поля, 1 — целое число и,' — г'1 — д и -П Гхз — одиН ИЗ цлогочленов обратной связи, встречавшейся ранее в списке ре. гястроэ сдвига. 13' Заа Г. 11 В р* д рм пана« Используя этот новый мнагочлен, определиы г=а г-ь Теперь все тото!о для определения величин и, ! и А Выб рем т меньше г и такое, что Л ть О; выберем также ! =- г— н А = — Л ' Л,. Тогда Л так что новый регистр сдвига будет генерировать последовател ность пь ..., а,, и,. У нас остался произвол в выборе и, лл которого Л„ чц О.
Выбрав в качестве и номер ближайшей итера ции, для которой выповнялось условие Е > ! , получим паждай итераиии регистр сдвига ыинимальной длины, однако т кое усавершенствовангге требует дополнительных рассужден и будет описано позже. Практическая внтерпретация гога, что было изложено до н стоящего момента, представлена на рнс. 11.5. Два регистра сдвига. отвечающие итерапиям с номерами гл на, показаны аа фрагменте(г рисунка. В качестве аг-й итерации выбарается та, при которой р гистр сдвига (! , Д вЂ” и (х)) ве способен генерировать коми менту а, и минимальная длина регистра сдвига, генерируюшег требуемую комвоневту при т.й итерации, больше ! , Буде также считать, что регистр сдвига (5, г !и — и (х)) не способен ге нернровать компоненту и„ так «ак в противном случае мы не доц жны ничего с ним делать.
На фрагменте (Б) рнс. 11.5 регистр сдвига ((, Д вЂ” и (х) превращен во вспомогательный регистр путем увеличения его дли ны, позиционирования п такого изченейня его выхода, мотор позволяет скомвенсировать неспособность регистра (5, г Д'-и (х) генерировать компоненту а,. Отметнм, что вспомогательный ре; гистр имею дополнительный атвоп с весовым множителем едн. ница, соответствующны коэффициенту )е" г( На протяжении пер вых г — ! итераций в остальных отводах цепи обратной связ формируется отрицательное значение соответствующей этому да, полннтельному отводу велкчииы, н поэтому на выходе вспаиога- тельного регистра формируется последовательность пулей.
Прн' г.й итерации зти величины взаимно не уничтожаются, и выход вспомогательного регистра оказываетсп ненулевым. Коэффициент А выбирается таким образам. чтобы его лобавление п г-му выход- ному сигналу обратной связи главного регистра сдвига арина. дило бы к получению нужной компоненты а, На фрагменте (ГБ) рис. 11.5 показано, как два регистра сдвига; изображенные на фрагменте (й), сливаются в один регистр, что в силу цринципа суперпознции не меняет общего наведения схемы, м. *„.
м КЛ, Вго дает регистр (1-» )о> (х)). Инагца иногда !., > Е, з В последнем случае прн проведении да,ы альнейших итерапий м заменяется наг мой 11.3.2, которая Т иое описание процедуры дается теоремой , к р очи 1'гперждает, что эта процедура приводит к наименьше, у р «у и егис и зю г».
н Б р иеюэ рез» лиа и ш сдвига с требуемым свойством. Прежде, чем док взывать эту тсо. релгу, получим гранину для длины регистра сдвига. Теорема 11.3.1. Пусвю(Е,, гл' и (х)) — псгигтр сдгига сли- яейяоа об а пи р аа сгчзью .ниии алл оа д.шяы, ге»лерг руюигий по- сггдогатггьпшгггь а,... а,, а (Е„)а~ (х)) — регистр сдвиги с ли. »гйяай сбратяоа сююью .яияилальяоа длины, ггясрирую си оеатгльлсстл а,, а, л, а„и (а~ (х) сь Д' 'л (х) Тогда Е, > шах По и г — Е„,!.
Доказательство. Неравенства, которое требуется доказать, разбивается на деа неравенства (.,> Е,, !.,> — Е,, Первое нерэвенггво очевидно, пасковьку е л с. н регистр гдаи а с линейной обратной связ~ю генерирует веко ор т рую исследователь. ность, то он генерирует н любую меньшую последоветел»ность, являющуюся началом исходной Если Е,, > г, то втор г, то второе неравен- ство также становится очевидным. Поэтому д „, < г н второе неравенстпо не выполняетгя, и попытаемся . прийти к противоречию. Иэ предположения следмет, что Е„ < — — Для сокращения ~аписи введем вреиенные обо.
значения: с (х) — )и и (х), Ь (х) =- !го (х), (. = (,, в Е ' = (., В н . ня приап»тают вяд: В новых обозначениях исходные оредооложен <гиг) Е 1.' ч- 1 что < ) Е "Е' 1 Крометого.нзусловийтеоремыследует, г. " чь — Е г,а, „ а =-- шсо, „ с. ЕЬ»аг», ! — Е »=1 Теперь установим противоречие. С одной стороны, с а, =- — Е Ь»а,-» = люг Ь» У с,а,,, »=г п обега где справедливость разложения а, » следует из нр( егает аелые значения от г — ! до — Е Е соде л т из того, что г — й —, содержащиеся среди чисел !.
- 1, йг — 1, в силу предположения г> Š—. Е' !. с 1 а„т — 'Е', с,а, г = Ч' с, дг Ь»а.. ., зв! !ГЗ Ялюр БЭ. и — М Е„> (.„г где справедливость разложения аги следует из того, что г — л пробегает садержащиеси среди чисел Е' ю 1, ..., г — 1 целые зйачения от г — ! до г — !., а это, в свою очередь, следует из аредположения г)ж Е З- Е' 1- ! Изменение порядка суммирова. нвя в правой части последнего равенстпа приводит к выражению дли а„ полученному в правой части предыдущего равенства Та- ним образом, получаем доказывалагдее теорему противоречие и, чь Если удастся построить регистр сдвига с длиной, удовлетворя- ющей соотношению нз теоремы Н,З.! с заменой знака иесгрогога неравенства знаком равенства, то тем самым будет построен ре.
гистр сдвига минимальной длины. Доказательство теоремы 11.3.2 предъявлнег конструкцию такого регистра сдвига. Теорема 11.3.2. Предположим, тпа (Еи (пйх)), 1 —. !... г, шлштся посла)смательпштью ршистрш гдгига минимальной длш м с линейной обратной сэазью, таких, что (Е,ыцг) (х)) ггигри. руст псслсдояатгльяосп ь а„, а, Есяа (м> (х) лж (о-П (х), та Е, =- шах(Е,, г †. 1., Д любой регистр сдяша, гшерирующиа ап ..., а. и и гю гиа длили, я шэпадаюи!ую с геличияой праеод чаапи последнего раггясялги, г. .жется регистром сдвига минимальной длины.
Дсхлзалыльстаа Согласно теореме 11 3.1 Е, не может быть меныие величины в прэвой части последнего равенства, Если удастся построить какой-либо регистр сдвига, который генерирует требуемую последовательность н длина которого совпадает с ука. эанной величиной, то ои будет регистром сдвига минимальной дла- ны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
