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

  Содержание



 

5.2. Алгоритм Витерби

Шаг 1. Рассматривается подпоследовательность r из ne знаков принятой последовательности. Для каждого набора из информационных последовательностей, последние (me-1) символов совпадают, выбирается кодовое слово, ближайшее к r. Соответствующий путь называется выжившим, т.е. после первого шага остаются выживших путей.

Пример. Рассмотрим сверточный код, дерево которого приведено на рисунке 10. Предположим, что передавалась последовательность 00 00 00 ..., а принята последовательность 11 00 00 .... Пусть me = 3. Рассмотрим информационные последовательности 000 и 100. Соответствующие кодовые последовательности суть 00 00 00 и 11 10 11. Для последовательности 00 00 00 расстояние до принятой последовательности равно 2, а для кодовой последовательности 11 10 11 - равно 3. поэтому выжившим считается путь, соответствующий 00 00 00. Аналогично определяются еще три выживших пути 11 10 00, 11 01 10 и 11 01 01 .

Рисунок 10. Дерево декодирования

Шаг 2. Следующий шаг выполняется в цикле, пока число циклов не превысит (m - me); в этом случае осуществляется переход на Шаг 3. В t-м цикле все выжившие пути удлиняются на одну ветвь и вычисляются расстояния между подпоследовательностью r длины no·(me+t) принятой последовательности, однако, по-прежнему сравниваются кодовые слова, для которых совпадают последние (me - 1) информационных символов, и среди таких слов определяется выживший путь.

Пример. На втором этапе выжившие пути 00 00 00 и 11 01 01 удлиняются на одну ветвь, что соответствует кодовым словам 00 00 00 00 и 00 00 00 11, и 11 01 01 11 и 11 01 01 00. Пути, помеченные словами 00 00 00 00 и 11 01 01 11, имеют два одинаковых последних информационных символа 0 0. Расстояние принятого слова 11 00 00 00 до 00 00 00 00 меньше, чем до 11 01 01 11; поэтому выжившим является путь, соответствующий 00 00 00 00.

Шаг 3. После (me - m +1)-го этапа рассматриваются пути длины m и до предела используются возможности памяти декодера. Теперь, если все выживших путей имеют одинаковые информационные символы в первом блоке длины n0, то первый блок декодируется в эти информационные символы. Если же согласованы не все выжившие пути, то декодер каким-то образом, например, голосованием по большинству выживших путей, определяет эти символы. Декодирование первого блока можно проделать и раньше, если на каком-то из этапов все выжившие пути будут иметь одинаковые информационные символы в первом блоке.

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