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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:37, 7 мая 2016.

Описание

TemplateDifinitionIcon.svg Определение «

Определение - Алгоритм Витерби

»

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

Суть алгоритма

  1. Фиксируются , ,.
  2. - кодовое ограничение - максимальное число блоков, которое одновременно хранится в декодере.
  3. Блок из символов преобразуем в блок из символов.
  4. Если -кодовое ограничение, то алгоритм имеет право исправить подряд идущих символов (ограничивается объемом памяти декодера и скоростью приема).

Процесс декодирования

TemplateExampleIcon.svg Пример Пример:

Допустим послали сообщение: 111 010 110 011 111 101 011, а получили: 110 110 111 011 101 101 001


Рис. 1.

1 случай

В первом символе 2 варианта 0 или 1 (в начальном состоянии ). Так как больше единиц в первом полученном символе, то у нас была 1, следовательно, ошибка и исправляем на 111.

Во втором символе пришло 110, и наиболее вероятный символ по минимальному расстоянию Хемминга - это 010.

В третьем символе пришло 111 и более правдоподобное 111.

Особенность

Если мы потеряем символ (то есть ошибемся), то и далее мы будем совершать ошибки.

Этот способ хорош, когда декодируем сначала.

2 случай

Строятся слова (строим всевозможные пути) для нескольких символов, то есть для 111 011 101 101 001 и вычисляем расстояние по Хеммингу. Затем выбираем где значение расстояния минимально. Но для этого нужно зафиксировать нижнюю границу. Глубина нижней границы для каждого кода своя. Верхняя граница - для нее нет оценки и она подбирается эмпирическим путем.

Чем больше будем в глубь продвигаться, тем больше потребуется вычислительных ресурсов.

Достоинство алгоритма

Алгоритм можно воспроизводить в реальном времени. Т.е. алгоритм можно легко и наглядно показать студентам во время пары.

См. также

Алгоритм Витерби на Википедии