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

  Содержание



 

5.4. Комментарии к алгоритму Витерби

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

Вообще говоря, в утверждается, что для кодов со скоростью 0.5 ограничение длины при декодировании, превышающее выбранное значение ne в 3-4 раза, достаточно дя исправления всех комбинаций ошибок с весами, меньшими, чем d/2, где d - расстояние кода, однако, мы не нашли доказательства этого факта ни в одном из источников.

В качестве заключения заметим, что при декодировании по методу Витерби, так как рассматриваются кодовые слова из различных множеств, то минимально требуемое расстояние для заданной корректирующей способности будет меньшим, чем при декодировании блоковых кодов. Например, для сверточного кода из предыдущего примера (рис. 7б), для которого k0 = 1, n0 = 2, для исправления двух ошибок требуется минимальное расстояние между кодовыми словами из различных множеств равное 5, которое достигается при m = 6. Соответственно если декодирование проводить при помощи таблицы декодирования, то необходимо хранить 26=64 кодовых слов. При использовании алгоритма Витерби можно положить mе = 3, и соответственно на каждом шаге производить действий (в данном случае 8 действий). На каждом шаге будет храниться только путей, т.е. в данном случае 4 пути.

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

Пример: Рассмотрим код на рисунке 7б. При n = 12 (m = 6) данный код исправляет все комбинации из 2 или менее ошибок. Используем декодер Витерби, положив me = 2 (ne = 4). Пусть было передано слово 00 00 00 00 00 00, и ошибки произошли в первых двух разрядах, т.е. будет принято слово 11 00 00 00 00 00. Если при кодировании используется таблица декодирования, то все ближайшие кодовые слова начинаются с 00. При использовании декодера Витерби при ne = 4 мы видим, что выжившим путям соответствуют слова 1110 и 1101, т.е. возможность правильно декодировать первый информационный символ 0 потеряна. Однако уже при me = 3 (ne = 6) возможность правильного декодирования остается, и корректирующая способность кода сохраняется.