Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 65
Текст из файла (страница 65)
Сложность этой про. авдуры растет зкспоненциально па 1, так что при ольших она практически неприемлема. Обычно 1 сталь велико, что его можно полагать бесконечным. Практически алгоритм не может рассматривать всю входную последовательность нелаком при б 1. Он начинает с самого начаяа и, двигаясь вдоль по- олшпнх щения. Ззфекпгв- следовательности, принимает окончательные реш ный поиск по решетке можаа осуществлять по алгоритму Ви- терби, который булез описан в следующем разделе ых случаях число гостояний машины с конечным чис. В некоторы . у ам кад е регпетки лом состояний велико. Тогда число узлов в каждом кадре р также велико, иногда настолько, па его можно гюлагать неагра.
ничеяным В этом случае исходная часть решет ' р ки тоже астет неограниченно, и в графе мы пренебрегаем тем, что аа самон деле при возврате машины с конечным числом састо явнй в некоторое састоянве в конечном итоге пути рекомбинирую т Ведь в каж- лый момент времени прикодится рассматривать лишь малые ф агменты решетки. Хорошим иэображением того, что проксходит, фрагме ~2 3 Алг рит Вз е!юа является зреасшаленаоо на рнс.
!2 б дереза Число узле«дерева растет неограниченно. Тан жс как иа решетке, 1 кадров маркироваияого дерева определяют ц) векторов Задача понска по дереву сосгоат в нахождении тот из этих векторов, который олнже все~о к заданному вектору т „;"ппыт Ь!ы моьчеч численно наложить данную последователю ю ть яа каждый из возможных и!~ей дерева .глиной в 1 кадров з о~ рс!!сзлю наилучшее совпадение Опять сложность эгай про. и туры ра тет зкспншен ~«алэна па!, так что чрактическ«оиа не. пригчлг з Э)«ре«тзв«ые процеауры поиска па дереку даются по,ле,ювз елг.ныьш алгоритмачи, рассматрнваеиымв в следуюцшт ~ зрэграфгх. !2.2.
Алгоритм Вмтсрбн Причина оптимзлч«ости днизыического про~рами«рванина ут. зарычат ц ч~ о если в не«тором смысле оптимальный путь от точки Д х точке С пр ж шит через точку В, то о~резок путя из ~очки В в точку С совпадает с оптимальным путем из точки В в точку С, Это' иринино прнменнч к задаче отыскани» чучнтего пуз« по решемге Огнонаннаи нз эгон принципе итеративная процедура по. строения цере ~еннгэго гножесгва претендентов на лучный путь по решетке пззестна по,! названнеч алгоритма Внтерби Алгоритм В«герб« для решетки с д ребрами в каждой вершине и длано! кодового огран.*гмвия т операрует З' нретеидентаии, так что его сложность пропорциональна дц Практически алга.
риги пригоден только при малых т Если длина «одоного ограничен«я равна !и и из кзжюй верпшны решетки выходят два ребра, то жтгорятч Вцтерби оперируе~ !02З претензентачя Практически это дот~усыьзо Но при дляпе кодового ограничения 20 число пре. тсндентои уже балыке миллиона, так что алгоритм практически иепрвечле) Двигаясь вдоль решетки, алгоритм Внтерби итеративно обре.
батывает кадр за кадром Находясь иа некотором кадре в момент 1, алгоритм не знает, капая из вершин является ближайшей, и даже ие пытается вычислить эту вершину. Вместо этого алгоритм опре. делает лучший нз путей от начальной першины до каждой из вершин 1 го кадра. Он вычисляет расстояния между данной последовательностью и всеми претендентами для «аждой вершины 1-го кадра. Для наждого нз путей-претендентов зто расстояние называется его расходнмостью. Если все пути. претенденты проходят в первом кадре через одну и ту же вершину, алгорити находит первый кадр ближайшего пути, но не принимает пря этом никакого решения относительно 1.го кадра.
Далее алгоритм вычисляет пути-претенденты в каждую новую вершину Д -1- 1) го кадра. Но чтобы попасть в любую новую вер. шину (1 -1- !).го кадра, путь должен пройти через одну из старых вершин 1.го кадра. Таким образом, пути.претечденты в новые вершины можно почучить продолжением старых претендентов, кото. рые допускают занос продолжение Ближайший путь вычисляется прибавлением приращений расходимастн каждого пути к расхо.
димости лучшего пути в старую вершину. В каждую новую вершин> ведут 0" путей, н путь к новой вершние с минимальным приращением является ближайшим. Этот процесс повторяется для каждой нз новых вершин. В «онце вы шсленнй, связаинмх с новым кадром, алгоритм вычисляет ближайший путь в каждую «з вершин этого кадра 1 -1- !. Если опять все эти путя проходят через одну и ту же вершину второго кадра, то алгоритм Витерб» успешно выг числяет второй кадр.
Этот провесс повторяется во всех успешных «адрах. Если в некоторый момент возникает несналько ближайших путей в данную вершину, то алгоритм должен разрешить этот конфликт, используя некоторое правила Альтернатива состоит в сохра. ненни всех решений, так что, например, находятся два пути в дан. ную вершиму Ддя лучшего понимания это~о момента следует обратиться к расс аатриваемому ниже примеру.
Для реализации алгоритма Вигерби надо выбрать окно ши. рины Ь, которое, «ак правило, в несколько рзз превышает ширину кодового ограничения т я диктуется воз ожностями исполь зуемого иочпьютера. В моме~тт и алгоритм просматривает все выжившие пути. Если в первом кадре оии совпадают, то этот кадр выбирается в качестве первого кадра правильного пути; его можно передать пользователю. Далее алгоритм шбрасывает первое ребро и переходит к вычислению следующей итерации, беря для этого новмй падр.
Если опять все выжившие пути проходят через одну и ту же першину наиболее старого надра, та этот кадр принимается. Этот процесс повторяется бесконечно, вычисляя кадр за кадром Если Ь выбрана достаточно большим, то в данном кадре почти всегда можно принять однозначное решение.
Редко, но ветре. зоэ — чаются ситуации, когда ори- нять однозначнов решение — — — — и отбросить кадр не удается 2 У несколько ближайших цутей, либо потому, что ширина окна й слишком мала лля принятия решения. Тогда используется некоторое правило разрешения рзт Ва ра . этой неопределенности Такое событие случается пренебрежимо редко.
Вместе с ростом числа кадров растет расходимость каждого пути Чтобы избежать переполнения памяти, приходится время от времени редугшровагь рашодкность, Простое правило такой редукция дается вычптэннем нанчсныпсй расходнмости из нсех расходи юстей. Это нс влияет н» выбор эшнньгально!г расходи- мости. Полезно представлять себе декодер Ввтербн кзк окно, через которое можно наблюдать часть решетки Это нллюстрнруетси рис. 12.?. На рисунке можно видеть только часть решетки конечной длины, на которой отмечены выжившие пути а их расходи- мости. С течением времена решетка скользит влево. При появлении справа новых вершин некоторые пути продолжаются в них, а другие ночева от; самый старый столбец выходит ив-под наблюдения налево Со временен левый столбец вершин нсчеэзет, а лишь для ошюй из его вершин будет существовать проходящий через вее путь На рас !2.8 приведен првмер. Для простоты и метки на решетке, а последовагелэнаст» данаых в примере выбраны двоичными Еакладово расстояние заменяется просто числом позиций, а котором различаются две последовательности.
Выберем ширину окна Ь равной 15. Предпачожим, что заданная последовательность равна г †. 101000001000000000000000 и требуется найти путь на решетке, ближайший к заданной после. довательностн Днаграмзга согтоявнй лекадера показана на рис. 12 В. На третьей нтерагснн алгоритм находит ближайший дуть к каждой вершияе третьего кадра. Затем, продолжая пути, ведущие к вер. шинат: 1г — П.го кадра, в сохраняя ближайший путь к каждой веразпге г-го кадра, алгоритм на г.в итерации находят ближайшие аута в вершнвы г.го кадра.
Иногда может возникнуть неопре- де гз Р» . 1з.а. ПР Р элгю В Ра деленнасть. В данном примере имеются две неопределенности в пятой втерацвн. Алгорнтм может разрешить неопределенность случайным обра. зом или сохранить оба пути. относительно которых существует неопределенность. В данном примере неопределенность сохраняется до тех цор, пока не находятся лучший путь или сомнительяый участок не выводится за пределы буфера Если имеется толька один путь, проходящий через вершину наибовее старого кадра, то принимается однозначное решение 4И 4!О Г . !Х.
Бнмр азг рашн пояса Э аз у В этом примере ближайшей к данной последовательности будет либо нулевая послеловательность, либо последовательность с началом !110001011000.. Истинная реализация рассматриваемого алгоритма ыожет сильно отли ~аться от приведенного на рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
