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

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

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

Пусть $\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$.