Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 66
Текст из файла (страница 66)
12 8 символического описания. Например, выживающие пути на решетке можно задавать в виде таблицы 15-битовых чисел. При кажлой итерации нексчорые из этих 15-бнтовых чисел сдвигаются влево, выталкивая наиболее левый бвт и добавлян справа новый бит. Друтие из 15-битовых чисел этого списка не видоизменяются, а выбрасываются из списка.
12.3. Стек-алгоритм Для больших решеток алгоритм Витербя быстро становится непрактичным; при длине кодового ограничения 1О алгоритм требует запоминания 1024 путей-претендентов. Для того чтобы ослабить влияние больших длзн кодового ограничения, была разрабатана сгрзтегия, игнорнруюптая маловероятные пути па решетке, кан только онн становятся маловероятными. Стратегвя, поиска на решетне только наиболее вероятных путей изнестн» под общим названием последавашльных алгоритмов. Как пра. вило, в последовательных алгоритмах не принимается оконча.
тельных решений о непрерывном отбрасывании путей, Время от времени последовательный алгоритм принимает решение вернуться обращено и продолжить оставаениый ранее путь. Последо. вательнме алгоритмы в равной мере пригодны и для пояска по дереву, и для поиска по решетке Представим себе решетку с большой длиной кодового ограничения, скажем, равного 40. Для принятия первого решения в та.. кой решетке надо обработать несколько сотен кадров.
Каждый падр содержит и вовсе огромное число вершин, а именно 2ы, илн, примерно, 10ы вершин. Последовательный алгоритм должен найти наиболее близкий к заданной последовательности путь на этой решетке; он должен сделать это, па крайней мере, с очень высокой вероятностью, хата время от времени ему дозволено отказаться от декодирования. Этот отказ связан не с недостаточностью данных, а с неполнотой алгоритма В алгоритме Витербн, мы ме встречались с огпибками подобного сорта. Последовательный алгоритм просматривает только первы падр, принимает решение и переходит в вершину решетки первог уровня.
Затем он повторяет эту пронедуру. На каждом уровне, находясь только в одной вергнине, он просматривает следующна кадр, выбира» ребро, ближайшее н принятому кадру, и персх дит в вершину следующего уровня, прокладывая таким образо путь на дереве. Если заданная последовательность точно созна. дает с некоторым путем на дереве, то эта процедура рабо.гает зо. роше.
Однако прн валины г ~асов~ здеш н пг, тедоват л ый ритм выбирает иногда неправнлюп:й птть Гела злгорш ~ про. допжает следоват а л жиоьт пут, он в~ез пиз обнару от что в ьажлом кадре расхадимость слншко г велика н, по-вндгДтк тИ, он на неправильнот пую Погледовзт ль пай алгорнг ~ вер назад на неснолько кадров нач~гт исследовагь альтернат в ые ° учи до тек пор, пока не найдешься нрав,гоподсбный путь Затес он будет дшц ать я вд л этого ал гернаю нного г.утг Н ваге будут кратко описаны правила, которымн он руковозст ° сися при этом поиске. Характеристккгз алгорн~ ° з эавг с»т от шнрниь 5 аьна Есла алгоритм из~пел пу.п„ проходящай через Ь кадров дерева. он пргннчает окончательное рептен ~е оп оснгелюи а юга арого кадра, выводит этот кадр в вдвнгаез в окно навыа кадр Числа вычислений, необходинш поспею вательнгчу алто.
ритму длн продвижения по дереву пя о:ну вернзину вг. у б» задается случайной величиной Эта веггачннг с»ужнт о г озной характеристикой аоследовз~ельиого а.иори та Она продетая. лает собой основной параметр, определяющни слояангсзь ал;э ритча, необходныую зля обеспечения заданного уровня его за. раитеригтик Если помехи малы, то алгорнлн может двигаться по правильному ~утгь используя для ородвнження вглуб по дереву на окну вершниу только по одному жзчислевшо в каждо ~ кадре. Но если имеются сбгвающве помехи, т алгоргм» мажет пойти по тгеяравильг~оьгу пути, что привод задержке и боль. шону числу вычислений, предшествующих вьщаду на прзвнль.
ный путь Переменность числа вычислев .й влечет за собой необхозщмость большого объема памяти для входных данных Любтон буфер нонечного объема, езави хо о ег аелвчины, прн испол . эовании в последовательном алгорит ее енулевую вероят. ность переиолнення. Такая поведение алгоритма следует рассматривать кан одну ич его характерностях Переполнение буфер.
ной памнтн лвляется существенным фактароы любого алгоритма, который осуществляет по меньшей мере одно вычисление з каждой посещаеыой шршние н который послсдоватсщно просчатрввает ребра так, что заз з аааые на более глубоких ребрах дерева данаые не используются. Второе условие оказывается критическим н приводит к о болт и вед ю алгоритчз Испольауеные последовательные алгорггтьгы разбнвзютсч ~гз два класса стек.алгоритм, рассматриваемый в нзстоящстг разделе н алгоритьг Фано, который будет рассмотрен в следтющем разделе Структура их совершенна различна.
Используелгые в этвх двтт подходах метркки являются предметом несрерывяых обсуждений Необходииое число вычислений в стнюалгоритме меньше, ы2 гз ~хв решгрш р «хизу 423 чем в алгоритме Фане Стек алгоритьг запоминает уже вы численный набор путей Эт контрас~пруст с паведенве алгоритма Фано, который, найля свой путь в некотору вершину, может вернуться ва какое-та расстояние обратно только для того, чтобы понт рить во всех деталях путь в т же вершину. Стек-алгоритм предпочитает запоминать проделанную работу, а не повторять ее С другой стороны, дл ' стек.алгорнтма требуется существенно больший объем памяти и большая вычисллтельная работа на каждой итера. цяи. Стек-алгоритм легок для поаямания; его упрашснная блок-схема приведева нв рис 12 9.
Алгоритм организуется вокруг стека уже вычисленных на прелыдущнх итерациях путеи различной длины. Каждый вход в стек представляет собой путь, опии сываеьшй тремя величиначиг длиной путя; последаватедьностью переменной длины, со. держащей определившие данию ный путь переходы между со- Л и З „„„„„- „„,, „ стояниями; н расходимосгью данного пути В начальны Р с. 22.2. угрми е сте ° е - моишш стек содержит только трнвиальньш путь нулевой ритм. длины. Расхадимость пути определяется «ак расс~ояние между сегментом пути н вачальнын сегментом данных той же самой длины.
Используемые в последоватечьных алгоритмах расстояния измеряются многими разными спасобачя. Во многих важных задачах последовательность ленных представляет собой последовательность запвсанпых на ребрах символов, искаженных аддитнвным шумом. В зтам случае мера расстояния известна как мешрики Фоно, которая сейчас будет определена. Расходимость пут» определяется ьзк чагарифмнческая функ шгг~ правдоподобия этого путя и вычисляется следугошим обра. зом Первые Аг -1- 1 кадров заданвого слова ыожно записать з виде = (со, ио*, иь ..., и,"д ..., ил; ..., ии').
Первые пг -- 1, кшграв символпв вдоль произвольного пути можно записать в наде Яы хатим отыскать шрезок пути на дереве, ко~орый ьгаиснмнзнрует Рг (сыо ) чш'), Пас чедовательныв алгоритм выбирает начальный отрезок пути по дереву, ие заглядывая а глубь дерева По правилу Байеса, р,(Ии!) с!лен Рг (ч'ш (с< ') можно разбить на два множителя г зг ь Рг(ч'ч'(с' ') = ~ П П Рг(с((сгг)~ ~ П П Рг(иг)1 г=зг-~ г-. ы г=~ Первмй член равен произведению уславнык вероятностей для ш г 1 кадров истинного путя; второй множитель равен ировзведению безусловных вероятностей по тем кадрам, где путь не определен.
Это разложение являетсп следствием определенна последовательного алгарвтма. Алгоритм более общего вида не обязательно допускает такое разбиеиве. Теперь будеы максимизировать вдоль путей величину П П»,(и((с() г — ! —.г Так «ак все пути предполагаются равнавсроятнымн, та член Рг (с' ~) является константой. Иго можно отбросить, и это не влияет на выбор иаксимума Используемая в рассматриваемом последовательном алгоритме метрика, именуемая метрикой Фано, задается логарифмической функцией г р("м! гш)р(| г) ' р(сиы)=-)ай,~ р,(И ~ф)сй (и() Гг)1 3!з д,эз Фэио 4Ы Г.
!З б Эи юг в яэр х я Здесь с-я скобка представляет собоб вклад метрики Фано на г.м калре (о( () я я(с) Для каждого рассматриваемого пути е с-и кадре требуется вычислить только зтог член. Метрика р (соо) позучаегся прибавлеииеч нового приращения к метрике Фана пути, которыя ~вписан на предыдущей втерев!ни в вершине с~сна. 12.4. Алгоритм Фано В алгоритме Фано требуется знать среднюю расходнчость аа «адр правильной последовательности д тщн хотя бы верхнюю границу для б.
Это ерелпохагаст наличие неко~эрой меры ста. тистической регулярности расхадичостн, так что средняя расхо-, дилюсть может быть нгпользована как типичнэв. Пока алгоритм Фано следует по правнльному пути, можно ожядять, что в пределах первых ! кадров раскоди юсгь равна примерно Ыд Алгоритм допускает несколько ббльшую величину расходимостя, но е.лн оиз намного больше, то алгоритм сделает вывод, что ан ва неправильном пути Выбереи (быть иожст, моделироваанелг) некоторый параметр б', больший, чеч Д, и определим перекошенное расстовние формулой ') С (!) = б'! — б (Л, где д (!) равна расходимости текущего путе-претендента на дереве.
Ддя правильного пути 0 (О приблизительна равна бс, а с(!) положительно и возрастает. Алгоритм следует по пути на дереве до тех пор, пока с(!) возрастает, Ясли вдруг с(!) станет уменьшаться, алгоритм заключает, что в некоторой вершине он выбрал ошнбочное ребра и возвращается па дереву обратно, иро. неряя другие пути. Он мажет найти лучший путь н слелавать по нему или может возвратиться к той же самой вершине, но уже более уверенно прололжать путь через нее.
Для того чтобы решить, когда ! (!) начинает уменьшаться, в алгоритме Фана используется нереьгенный порог Т, который всегда нратен приращению А порога Пока алгоритм движется вперед, порог, оставаясь ие большим с(!) и кратныы приращению Ь, принимает максиьгально возможное при этих ограничениях значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
