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

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

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

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

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

Выход: Список всех кодовых слов $x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}$ чье расстояние Хэмминга с $x$ не превышает $e$.