Основы теории передачи информации


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


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

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

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

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

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

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

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

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

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




Начало  Назад  Вперед