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

  Содержание



 

3.2. Коды Хэмминга

Двоичный код Хемминга удобнее всего задавать при помощи проверочной матрицы. Рассмотрим матрицу H из нулей и единиц, содержащую m, m>1, строк и 2m - 1 столбцов, причем столбцами матрицы являются все ненулевые двоичные наборы длины m. Любые два столбца этой матрицы различны, т. е. сумма любых двух столбцов из этой матрицы (по модулю 2) не равна 0. Следовательно, любая пара столбцов матрицы H является линейно независимой, и согласно теореме 2.3, нулевое пространство этой матрицы имеет расстояние не меньше 3, и является кодом, исправляющим все одиночные ошибки. Длина кодовых векторов равна 2m - 1, число проверочных символов равно m, и, следовательно, число информационных символов равно 2m - 1 - m.

Поскольку все 2m - 1 векторов, задающих одиночные ошибки, принадлежат различным смежным классам, то этими смежными классами и кодовым пространством исчерпываются все 2m смежных классов. Поэтому образующими смежных классов для этого кода являются нулевой вектор и все векторы одиночных ошибок, причем других векторов среди образующих нет. Можно построить код Хемминга любой длины n, если выбрать матрицу H для наименьшего значения m, удовлетворяющего условию 2m - 1 ≥ n, а затем просто отбросить все лишние столбцы, оставив n столбцов. Независимо от того, какие именно столбцы отбрасываются, минимальный вес кода будет все равно равен 3. Итак, для любого n существует код Хемминга, исправляющий все одиночные ошибки.

Предположим, что передавался кодовый вектор v, в котором при передаче произошла одна ошибка. Тогда будет получен вектор v + e, где e - вектор, содержащий 1 в том разряде, в котором произошла ошибка, и 0 во всех остальных разрядах. Синдром принятого вектора равен

(v + e)HT =  vHT+ eHT  = eHT,

так как v -кодовый вектор и поэтому vHT = 0. Так как вектор e содержит единственную единицу в разряде, в котором произошла ошибка, то синдром eHT равен той строке матрицы HT, которая соответствует ошибочному разряду. Таким образом, сравнивая синдром с матрицей HT, можно найти положение ошибки и исправить ее, просто заменив принятый символ в соответствующем разряде на его инверсию. Если в качестве i-го столбца матрицы H использовать двоичное представление числа i, то синдром будет равен двоичному представлению номера разряда, в котором произошла ошибка.

Выберем в качестве проверочной матрицы (7, 3)-кода Хэмминга следующую матрицу:

.

Процедура кодирования будет проще, если в качестве проверочных символов выбрать первый, второй и четвертый символы, так как каждый из этих символов входит только в одно из проверочных соотношений задаваемых матрицей H. Соответственно символы третий, пятый, шестой и седьмой являются информационными. Чтобы закодировать информационные символы 1100, нужно определить проверочные символы в слове p1p21p4100. Символ p1 должен быть выбран так, чтобы удовлетворялось проверочное соотношение, задаваемое последней строкой матрицы H, т. е. чтобы p1 + 1 + 1 + 0 = 0. Следовательно, p1 = 0.

Аналогично p2 и p4 входят в проверочные соотношения, задаваемые второй и первой строками проверочной матрицы, т. е. p2 + 1 + 1 + 1 = 0 и p4 + 1 + 0 + 0 = 0. Таким образом, p2 = 1 и p4 = 1, и информационному слову 1100 соответствует кодовый вектор 0111100. Предположим, что при передаче в пятом символе кодового слова произошла ошибка, т. е. вместо кодового слова 0111100 принято слово u = 0111000. Синдром uHT принятого слова равен 101, что является двоичным позиционным кодом числа номера разряда 5, в котором произошла ошибка. Заменив в принятом слове значение 0 в 5-м разряде на его инверсию 1, получим переданное кодовое слово 0111100.