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

  Содержание



 

2. Декодирование древовидных кодов на основе таблицы декодирования

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

2.1. Принцип максимального правдоподобия

Декодирование древовидных кодов, так же как и в случае блоковых кодов, заключается в выборе "наилучшей гипотезы" относительного того, какая именно кодовая последовательность в результате искажения шумом в канале могла привести к полученной последовательности. При декодировании древовидных кодов мы также используем метод максимального правдоподобия (МП), т.е. предполагаем, что вероятность появления одной ошибки при передаче информации намного меньше, чем вероятность возникновения двух ошибок, вероятность появления двух ошибок намного меньше, чем вероятность возникновения трех ошибок, и т.п. Иными словами, принятое слово должно быть декодировано в ближайшее к нему кодовое слово и соответственно, необходимо определить, что считать кодовым словом в древовидном коде. Поскольку любая аппаратура может обрабатывать в каждый момент только конечное число двоичных символов, то мы предполагаем, что одновременно декодером может обрабатываться только фиксированное число m подпоследовательностей длины n0 принятой последовательности. Величина mn0 называется длиной кодового ограничения (ДКО) и обозначается через n. Подпоследовательности длины n и будут рассматриваться как кодовые слова. Однако в отличие от блоковых кодов множество кодовых слов в вершинах дерева, представляющего древовидный код, различно. Например, на рисунке 1 для случая n = 4 (m = 2) множество {1110, 1101, 0011, 0000} будет множеством кодовых слов во всех вершинах с нечетными номерами, в частности, в корневой вершине 1 дерева. Во всех вершинах с четными номерами, в частности, в вершине 2, множество кодовых слов есть множество {1010, 1001, 0111, 0100}.