Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика





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

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

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

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

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

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