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

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

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

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

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