Списочное декодирование

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Математическая формулировка[править | править вики-текст]

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

Вход: Полученное кодовое слово , максимальное количество ошибок

Выход: Список всех кодовых слов чье расстояние Хэмминга с не превышает .