Русская Википедия:Списочное декодирование

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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