Коды Хемминга (dmin=3, dmin=4,) - коды, в которых проверочные разряды формируются линейным преобразованием информационных разрядов. Пусть имеется разрешенная КК a1 ... ak b1 ... br. Проверочные элементы - есть результат линейного преобразования информационных:
bi=ai1a1+ai2a2+...+ainak
где aij - числа равные 0 или 1.
Обнаружение и исправление ошибок кодами Хемминга сводится к последовательному анализу «синдрома». Под синдромом понимают совокупность элементов, сформированная в результате суммирования по модулю 2 принятых проверочных элементов и вычисленных проверочных элементов по тому же правилу, которое применяется для их определения на передающей стороне
- принятые проверочные элементы
- вычисленные проверочные элементы
-------------
с1 с2 ... сr - синдром (вектор ошибки)
В случае, если ошибок в канале связи не произошло, все разряды синдрома будут представлены нулями, т.е. с1 с2 ... сr Þ 0 0 ... 0, в противном случае вес синдрома не равен 0. Так как dmin=3, код может исправить одну ошибку.
Пусть (n,k)=(9,5), r=4 и синдром имеет вид 1000. В поясняющей таблице 3.1 показано, что если синдром показывает числа 1,2,4,8, это означает, что ошибки произошли в проверочных элементах. Появление других чисел - ошибки в информационных элементах.
Таблица 1
|
|
с1 |
с2 |
с3 |
с4 |
|
|
1 |
0 |
0 |
0 |
1 |
b4 |
|
2 |
0 |
0 |
1 |
0 |
b3 |
|
3 |
0 |
0 |
1 |
1 |
a1 |
|
4 |
0 |
1 |
0 |
0 |
b2 |
|
5 |
0 |
1 |
0 |
1 |
a2 |
|
6 |
0 |
1 |
1 |
0 |
a3 |
|
7 |
0 |
1 |
1 |
1 |
a4 |
|
8 |
1 |
0 |
0 |
0 |
b1 |
|
9 |
1 |
0 |
0 |
1 |
a5 |
Запишем правило формирования проверочных символов, где aij - характеризует столбцы, а aj - строки:
b1 = a11 a1 + a12 a2 + a13 a3 + a14 a4 + a15 a5 = a5;
b2 = a21 a1 + a22 a2 + a23 a3 + a24 a4 + a25 a5=a2 + a3 + a4;
b3 = a1 + a3 + a4;
b4 = a1 + a2 + a4 + a5.
Пример. Пусть принята кодовая комбинация 11001 1111(в третьем разряде произошла ошибка). Тогда b1=1, b2 =0, b3 =0, b4 =1. В результате сравнения имеем:
--------------
0 1 1 0 - число 6, Þ в шестой строке - a3 произошла ошибка.