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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Математическая формулировка[править | править исходный текст]

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