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

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

Математическая формулировка

Пусть $𝒞$ — $(n,k,d{)}_q$-код, исправляющий ошибки, то есть, $𝒞$ — код длины $n$, размерности $k$ и с минимальным расстоянием $d$ над полем размерности $q$. Тогда задача списочного декодирования определяется следующим образом:

Вход: Полученное кодовое слово $x\in {\mathrm{\Sigma }}^n$, максимальное количество ошибок $e$

Выход: Список всех кодовых слов $x_1,x_2,\dots ,x_m\in 𝒞$ чье расстояние Хэмминга с $x$ не превышает $e$.