Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

2.2. Принципы декодирования древовидных кодов

В случае древовидных кодов декодер на каждом шаге декодирует только первые n0 символов (в информационное слово длины k0), но при этом учитываются и последующие (m-1)×n0 символов, которые находятся в декодере. Предполагается также, что декодер не может возвращаться назад: после того как декодированные n0 символов покинут декодер, они безвозвратно теряются. Таким образом, с одной стороны декодер, в отличие от блоковых кодов, как бы «подсматривает» вперед на (m-1)×n0 символов, что естественно дает возможность исправить больше ошибок при декодировании текущих n0 символов. С другой стороны, если первые n0 символов декодированы неправильно, то декодер после их декодирования окажется в «неправильной» вершине дерева, и ошибка начнет влиять на декодирование последующих символов.

Так же, как и при кодировании, при декодировании древовидного кода на каждом шаге декодируется один информационный символ, т.е. обрабатывается одна ветвь дерева, или набор длины n0. В определенный момент времени декодер находится в некоторой вершине дерева. На основании n символов, которые содержатся в декодере, декодер должен принять решение относительного того, какая из  ветвей, исходящих из данной вершины, является правильной. В случае древовидного кода, так же как и в случае блокового кода, декодер должен найти ближайшее кодовое слово длины n для слова, находящегося в декодере; первые n0 символов найденного кодового слова декодируются в соответствующее информационное слово длины k0. После этого декодированные n0 символов покидают декодер, и декодер принимает следующий блок из n0 символов кодовой последовательности.