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

  Содержание



 

5. Декодирование сверточных кодов по методу Витерби

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


5.1. Метод Витерби

Как обсуждалось выше, если число кодовых слов в сверточном коде достаточно мало, то при декодировании можно использовать таблицу декодирования. При этом последовательно порождаются все 2k кодовых слов, каждое из которых сравниваются с принятым словом. Блок с номером 0 принятого слова декодируется в блок с номером 0 ближайшего кодового слова. Поскольку для декодирования n0 символов требуется 2k действий, эта систематическая поисковая процедура декодирования по максимуму правдоподобия может быть применена лишь к коротким кодам и кодам с низкими скоростями.

Несколько более длинные коды можно декодировать с использованием метода Витерби. Рассмотрим сверточный код со скоростью k0/n0 и основной блоковой длинной n0. Пусть ограничение длины при декодировании обозначено через n = m·no, и пусть k = m·ko - количество информационных символов на длине кодового ограничения, m - задержка декодирования. При декодировании по таблице принятое слово длины n необходимо сравнить с каждым из кодовых слов, чтобы определить кодовое слово, которое находится от него на наименьшем расстоянии. При декодировании по методу Витерби выбирается некоторое число me, me < m, которое обычно на 1 меньше числа разрядов в регистре сдвига соответствующего кодера. Мы далее полагаем ne = me·no и ke = me·ko. Обычно задержка декодирования m в несколько раз больше, чем число me, и соответственно n в несколько раз больше, чем ne.

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