Алгоритмы поиска по решетке

Характеристики сверточных кодов, как и любых других кодов, улучшаются по мере увеличения их размера, в данном случае - кодовой длины блока n. При этом, однако, декодер Витерби становится нереализуемо сложным. Так, при n = 10

он должен помнить уже не менее 210 = 1024 выживших путей.

Для уменьшения сложности декодера максимального правдоподобия при больших n была разработана стратегия, игнорирующая маловероятные пути поиска по решетке, как только они становятся маловероятными. Однако решение о том, чтобы окончательно отбросить данный путь, не принимается. Время от времени декодер возвращается назад и продолжает оставленный путь.

Подобные стратегии поиска наиболее вероятного пути по решетке известны под общим названием последовательного декодирования.

В отличие от оптимальной процедуры Витерби последовательный декодер, просмотрев первый кадр, переходит в очередной узел решетки с наименьшей на данный момент расходимостью. Из этого узла он анализирует следующий кадр, выбирая ребро, ближайшее к данному кадру, и переходит в следующий узел и так далее.

При отсутствии ошибок эта процедура работает очень хорошо, однако при возникновении ошибок на каком-либо шаге декодер может случайно выбрать неправильную ветвь. Если он продолжит следовать по неправильному пути, то очень скоро обнаружит, что происходит слишком много ошибок, и расходимость пути начнет быстро нарастать. Но это будут ошибки декодера, а не канала. Поэтому декодер возвращается на несколько кадров назад и начинает исследовать другие пути, пока не найдет наиболее правдоподобный. Затем он будет следовать вдоль этого нового пути.

Наиболее простым последовательным алгоритмом декодирования является алгоритм Фано. Для его реализации необходимо знать среднюю вероятность появления ошибок в канале связи Pош.

Пока декодер следует по правильному пути, вероятное число ошибок в первых l кадрах (это будет мерой расходимости пути за l кадров) примерно равно

dl = Pош × n0 × l . (2.11)

Если же ошибок становится намного больше, то декодер принимает решение, что он на ложном пути, и возвращается на несколько кадров назад.

Процедура декодирования последовательности r = (01000000..., содержащей ошибку во втором символе, показана на рис. 2.9.

Пусть U = (00000000000000000… и принята последовательность r = (0100000000000…, то есть возникла ошибка во второй позиции кода. Проследим путь декодера Фано по решетке рис. 2.9.

Рис. 2.9

Видно, что если на первом шаге выбран верный путь, то расходимость не увеличивается и декодирование выполняется без ошибки. Однако на первом шаге мог быть выбран и неправильный путь (вниз), имеющий такую же метрику. При этом расходимость начинает быстро нарастать, что свидетельствует о неправильном выборе пути. Необходимо вернуться, но на сколько шагов? Предположим, что возвращение произошло в точку А и из нее осуществляется поиск по неисследованному пути. Очень быстро, однако, декодер убедится в неправильности выбора и снова должен вернуться. Но теперь уже не имеет смысла возвращаться в точку А, нужно сделать по крайней мере еще один шаг назад и снова пойти по неисследованному пути. В данном случае это будет правильный путь.

Декодер Фано гораздо проще в реализации, нежели декодер Витерби, и почти не уступает ему в вероятности ошибочного декодирования. Но он обладает и серьезным недостатком. Если вероятность ошибок в канале велика, то возрастает и вероятность принятия неправильных решений при переходе из одного узла решетки в другой, а следовательно, возрастает число возвратов к предыдущим узлам, что требует затрат времени. Входная последовательность при этом во избежание потери данных должна сохраняться в специальном накапливающем регистре. В конечном итоге могут произойти переполнение этого регистра и отказ декодера.

Содержание раздела