Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 64
Текст из файла (страница 64)
Однвч из путей решения этой задачи, конечно, являетсп решение гсходного матричного уравнения относительно вектора ! я даль пейшото вычисления многачлена й (х) Другой метод основан на асяользовании алгоритма Евклида для чногочлеяов. Для того, чтобм увилеть, хак можно решать шо уравнение шггасятельно ) (х) и й (х), вернемся к доказательству алгоритма Я' "~1 ! так что Г Б юная Р . 11.9 Р 398 Гз.11 Б рн н анрюш» плтн*ш Евклида. Иа етого доказательства легко увидеть, что !(') (к) = А)~э' (х) ! (х) (шод з (х)), что прн ! (х) =- а (х) и з (х) = кэ' являтся одной из форм решае- мого нами уравнения Выписанное уравнение справедливо прн всех г, Чтобы решить задачу, надо найти шкас г, при каторол( дед А(;) (х) < и в бей !(') (х) < и — !.
Если тзкое г уи(естаут, то многочлеим А;г (т) и 1' (х) должны равняться искомым ино) () гочлеиам ( (х) и у (х) Выберел( значение г, нри котором удовлетво. ряются неравенства дед !(" †"(х) ) и н деу!о)(х).< и — 1. Так как дей !(е) (х) = 2л и с растем г степень мчогочленов !(н (х) строго убываег, то это определяет г однозначно. При таком апре. делении г требование дей !")(х) < л — ! удоваегварено С ро. стом г степень мвогочлена А))'(х) растет, и нада только показать, что дей А;, (х) .. и, Для того, пабы это доказать, восполь.)уемся , () натряией. обратной к ивгрнпе Ан' (х).
Сначала напомним, что 1)в М,хы, оьш н р . Бвз лн (-.,~ в Отсюда ясно, что дед А)г'(х) > дейА)(г) (г) Напомним также, чта бей з(') (х) > дей гн) (т). Из этих неравенств и матрвчного уравнения з(х)) Г А,')'(х) — А)))(х)~ ~з(')(х)~ ~ ~=-! ' ~=( 'Ч-- !(- Аэ('( ) А)('( ) "( ) следует, то дей ( (х) =- дей А'))' (х) -' деу эн) (х), н так как Ш') (х) = П' — ') (х), то это преобразуется к соотношению дед А!('э) (х) = деда(х) — дей1(' а(х) *..2л — н =.
и, где неравенство вы~екает из определения парачетрз г. Гйм получиви почти полное доказательство слельюшей теоремм. Теорема 11.Б.1. При заданньы У') (х) =- хг" и б') (х) — а (х) пусть А(ь) (х) Продолжая рекурсию до тех иор. нока дей (н' (4 < л — 1, рг им гггдуюн(ую сипиему реяуррентных ур вне шй: ГО 1 Г' ~:Н' -' .Е':-"й и положим у (х) = Ь '!(') (к) и ) (х) —.. Ь (А';,) (х), где Ь вЂ”. =. А';,' (О) При условии, юно Ь отлично от нуля, эти.нногонхенм удоеяетворяюп( ур гиеною у (х) — ( (х) а (х) ('шод хг"). нриим дед) (э) < и, деду (х) < и — ! иД вЂ”.
! Доюэзатеюстго. Деление на Ь обеспечивает равенство Д = 1. Справедливость остальных утверждений была установлена рааее. () ь 1 ь,) ' ° Задачи 400 Гл. 11. Пишрье ишоа рипш л иевив снеге Таким образом, мы получили лругой способ решения той же самой теплиневой системы уравнений )в случае, когда эта система обратима), которую ыы уже реньалн раньше, используя алгорнгм Берлекэипа — 41)ессн; блок.скеча этого метола показана на рнс. 11.9 Если теплнпева система не обратима, то описааное применение алгоритма Евклида также приводит к иногочлену А))ь )х) наименыпей степени, который удовлетворяет определяющему аго равенству, но в этом случае Ь = О и поэтому миогочлен ) )х) не определен. Если Ь = О, го описанный алгоритм приводит к реше.
пию системы выр л 11.7. Сфор у р уш шв шэирожь алгоригш )Гура ш Замечания —,а', ь"'.пн."а'.-* 11977). лоэ Глава 12 БЫСТРЫЕ АЛГОРИТМЫ ПОИСКА ПО РЕШЕТКЕ И ПО ДЕРЕВУ ЛЭ1 Пшш р «и Око*У -02= Машина с конечным числом состояний, производящая в каждый момент времени один или более элементов некоторого полн Р, генерирует шклеловательность элементов этого полн. Множество исех возможных таких последовательностей на выходе машины с конечным числам состояний описываются графам определеннога вида, который называется решеткой или, в случае очень большого числа состояний, деревом Имеется много приложений, в которых по речультатач наблюдений в шуме одной иэ таких последователь. настей требуется опеаить либо, саму эту последоиательноси, либо историю малнииы с конечным числом состояний Это задача поиска по решетке или по дереву заката пути, который лучше всего отвечает данной последовательности.
Такое направление в абра. ботке даскрстных сигпалоа сплыло отличается ат других направлений, и алгарнтмм, рассматриваемые в настоящей главе, сильно отличаются ат уже изученных нами адгаритмов. Алгоритмы ваиска па решетке и по дереву находят приложения а таких областях, как декодирование свертачных кодов, дечадуля. ция сигналов при наличии межсимвольной интерференции, демо. дуляпяя сигнала по частичному отклику или фазана-раэнастно. модуларованных сигналов, распознавание речи и текстовых симвалов. 12,1.
Поиск па решетке п па дереву Решетки и деревьл, ио которым реализуется нанси, возникают каи описания машин с конечным ч лам астояний. Машина с ионечным числом состояний вадается множеством состояний, ° которых она может изхадитьсп, множествам переходов между этими состоянияин и выходными символами, соответствующими каждому такому переходу. Простейший способ построения машины с конечным числам состоиннй с помеченными переходами состоит в использовании регистра сдвига так, «ак показано иа примере на рис 12.1. Состояния машины в этом примере описываются двумя содержащимися в пчейках регистра сдвига битами, всего ичеетсн четыре так определяемых состояния.
В каждый момент времени ва вход поступают два бита, так чта из «аждога состояния возможны четыре перехода В данном частном примере из каждого состояния возможен прямой переход в любое другое состояние. Изображенная на рис. !2 ! схема имеет трн выходных бита; каждый переход порождает трехбитовую последовательность. На рис. 12.2 показан другой пример, а катарам уже нельзя из произвольного состоянии перейти в любое другое состояние. Для достижения некоторых состояний требуется совершить два иере. хода.
Схема иа рис. 12.2 имеет двухбиювый выход. Диагра лма переходов ддя малдины с конечным числом состоя. ний гаказанз на рнс 12 3. Переходы помечены векторами длины два. В каждый момент времени чашнна дедает переход ыежлу са. стояниями вдоль нута я метит путь переходов. Приведенная на рис 12.3 диаграмма соответстнует схеме на ряс. 12.2. Как правила, анд графа, который называется решгпжой, можно ислюльзовать для описзння выходных последовательностей произ.
вольной машаны с конечным числом состанний. Типичная решетка, иэ каждой вершины которой выходят два ребра, показана на рис, !2.4. Вершины любого сталбна решетки обозначают состояния, в которьп пожег находиться машина Каждый последовательный столбец соответствует последовательным моментам времени и со. держит одно и то же множество состояний Ребра, связывающие вершинм двух столбцов. представляют собой все возможные пе. реходы в течение данного временного интервала, именуемого кад.
рол. В общелл случае решетка представляет собой палубсскоиечный вправо прячоугольный граф, число вершин в каждом столбае которого конечно. Расположение ребер, связывающих вершины ланного столбца с вершинами следующего справа столбца, алка и то же для каждого столбца. Диаграмма начипаетсв в верхней левал вершние, так кзк движение осуществляется только вправо, то недостижимые левые узлы на диаграмме не указмааются. Д.тиной кодового ограничения решетки называется число битов, необходимых для определения состояаия на решетке Длина кодового ограничении решетки, показанной на рис. 12.4, равна двум.
4ОЗ По квсв . 'сар у о 404 Гл. 12. в тр ор м ас а р чо х реву ( .. Рч . 12.3. Дзаграма Р . 124. Пр т* р и т Каждый кадр машины с конечным чяслом состояний приводит к изненению состояния. На решетке зго изменение показано реб. ром, вхадншнм в следующую вершину.
Каткдое ребра на рнс 12.5 помечено. В общем случае ребро маркируется некаторыч фиксированным числом и, элементов осаовного пояя Р. Прн переходе ог кадрв к кадру множество меток на ребре можег быль как фак. снраванным, так и переменным, рйашниа с конечным числом со. стояний может двигаться по решетке слева направо но многим путям решетки. Идя по каждому из этих путей, она вычисляет некоторую последовательность элементов поля Р, которая и яв. ляется ее выходной последовательностью Пусть с — (со ! =.
О, , ) обозначает последовательность сим. волов источника над полем Р,генерируемых машиной с конечным числом состояний, и пусть ч =-,'о„ ! = О, ) обозначает последонательность символов данных нал Р. Во многих прихшжевиях о, = с, — ео где е, — составляющая ошибки. 0 такой ситуации говорят, что последовательность на выходе источника набшодается в аддитнвном шуме Задача поиска по решетке соспонт э вычислении такого пути на решетке, для которого последовательность с согласуется с задав.
ной последовательностью т данных ваилучшнч образом. Для измерения меры согласованности необходима ввести функцию расстоянн». Риссшоялое иа множестве 5 определяется как вецгествениая функции б (и, й) на паре элементов вз 5, удоцчегворяююая условиям 1, 4( (а, б) .. О а б (и, а) = О, 2 Д(а, й) = Д()1, и). Ясли эта функлия удовлетворяет также устовню Рчс. 12.2. М р«р* аш р з. 3. 1 (а, ))) ( б (о, у) -)- б'(у, ))) для всех у из 5, то она нвзыаашся мегприкой. Евклидова рассшояяие, определяемое на и-меркам векторном пространстве формулой д (ч, и) = 24 (о, — ш,)', 4-4 является вляется метрикой.
Каждый состоящий из 1 иадров путь на реп е еляет вектор длины йм над полем Е. Если из кажло й вершины решетки выкодит д путей, то на длине пу " р мы гюлу чаем д таки к векторов планы (п, Задача поиска по решетке состоит в выделении того из этих векторов, котор ый ближе всего в данном расстоянии подходит к дашюму вектору ч длины 1л,. Нзнболсе простой для понимания метод поиска по решетке со- стоит в вычислении всех расстояний данного вектора ч от д' по. следоватсльиостей, производимых данной реше~кой, я нахажде. нии в полученном списке наименьшего расстояния Зто можно проделать,мысл " сино накладыная заданн>ю последовательность ч на каждый из во з возможных путей на решетке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
