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


Декодирование сверточных кодов Алгоритм Витерби - часть 2


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

Рассмотрим работу декодера Витерби на простом примере. Полагаем, что кодирование производится с использованием сверточного (6,3)-кода (схема кодера приведена на  рис. 2.5, решетчатая диаграмма, соответствующая этому кодеру, – на рис. 2.7).

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

Предположим,   что    передана    кодовая    последовательность        U = = ( 0000000…), а принятая последовательность имеет вид r = (10001000 00...), то есть в первом и в третьем кадрах кодового слова возникли ошибки. Как мы уже убедились, процедура и результат декодирования не зависят от передаваемого кодового слова и определяются только ошибкой, содержащейся в принятой последовательности. Поэтому проще всего считать, что передана нулевая последовательность, то есть  U = (0000000…).

Приняв первую пару символов (10), определим меру расходимости для первого сечения решетки (см. рис. 2.7), приняв следующую пару символов  (00),  — для второго сечения и т.д. При этом из входящих в каждый узел путей оставляем путь с меньшей расходимостью, поскольку путь с большей на данный момент расходимостью уже не сможет стать в дальнейшем короче.

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


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