Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

2.2. Исправление ошибок

Рассмотрим стандартное расположение для (n,k) - кода V, Любые два вектора из одного смежного класса имеют одинаковый синдром. Следовательно, нам достаточно свести в таблицу синдромы и образующие смежных классов. Тогда алгоритм декодирования включает следующие шаги.

1. По принятому вектору u вычисляем синдром s = uHT вектора u.

2. В таблице образующих смежных классов находим образующий g с синдромом s. Этот образующий является вектором ошибки для принятого вектора. Таким образом, мы исправим ошибку, сложив принятый вектор u с образующим g смежного класса, и получим кодовое слово v = u + g.

Для приведенного выше примера, проверочной матрицей будет матрица

.

С оответственно, таблица образующих смежных классов и соответствующих синдромов имеет следующий вид.
Образующие
смежных классов
             Синдромы
 


Предположим, что был принят вектор u = 10010. Тогда s = uHT = = 101. Образующий смежного класса, который имеет синдром 101, равен 01000. Следовательно, с наибольшей вероятностью было передано кодовое слово 11010, равное 10010 Å 01000.

Заметим, что число смежных классов (и соответственно число образующих смежных классов) равно индексу кода V (подгруппы V) во множестве всех двоичных векторов длины n. Так как мощность (n, k)-кода равна 2k (теорема 1.2), то число образующих смежных классов равно 2n-k, где (n - k) - число проверочных символов. Так как число проверочных символов обычно много меньше, чем n и k, то в ряде случаев таблица образующих может храниться в явном виде. Тем не менее, продолжаются поиски кодов, в которых нет необходимости хранить в явном виде эту таблицу.