Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.
Задача:
Представим кодовую комбинацию с числом разрядов n=15.
Тогда схема формирования КР(бит) в коде Хэмминга имеет вид: АВ0С111D0100101
| 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 | |||||||||||||||
| Контрольные разряды | Номера разрядов | ||||||||||||||
| A | x | x | x | x | x | X | x | X | |||||||
| B | x | x | x | x | X | X | x | X | |||||||
| C | x | x | x | x | x | x | x | X | |||||||
| D | x | x | X | X | x | x | x | X |
КР А контролирует по чётности все нечётные разряды кода. В КР А записывается такая цифра, чтобы количество “1” в нечётных разрядах было нечётным. Таким образом, КР А контролирует по чётности все разряды в номерах которых есть “1” в первом разряде (в двоичном представлении).
КР В контролирует по чётности разряды в номерах которых есть “1” во втором разряде.
|
|
КР С контролирует по чётности разряды в номерах которых есть “1” в третьем разряде.
КР Д контролирует по чётности разряды в номерах которых есть “1” в четвёртом разряде.
Контрольные разряды могут быть размещены среди информационных различными способами. Наиболее удобно их размещать на 1,2,4,… 
позициях, так как в этом случае каждый КР принадлежит только одной, соответствующей ему группе разрядов.
Пример 1.
Записать слово х=01110100101 в коде Хэмминга.
Сформируем КР для слова х. Длина слова k=11, l=4, n=15 следовательно, код Хэмминга должен иметь вид:
АВ0С111D0100101
Для определения значений А, В, С, D решим уравнения:
А+0+1+1+0+0+1+1=1 (mod 2)=1 А=1
В+0+1+1+1+0+0+1=1 (mod 2)=1 В=1
С+1+1+1+0+1+0+1=1 (mod 2)=0 С=0
D+0+1+0+0+1+0+1=1 (mod 2)=0 D=0
Таким образом, слово х в коде Хэмминга примет вид: 11 0 0 111 0 0100101.
Пример 2. найти ошибку в слове х=110011100101101. для этого сформируем суммы по mod 2 разрядов, контролируемых разрядами А, В, С,D.
A=1+0+1+1+0+0+1+1 (mod 2)=1 
B=1+0+1+1+1+0+0+1 (mod 2)=1 
C=0+1+1+1+1+1+0+1 (mod 2)=0 
D=0+0+1+0+1+1+0+1 (mod 2)=0 
Следовательно, ошибка в разряде с номером 1100. Если ошибки нет, то проверка по всем КР даёт номер разряда 0000, которой нет.
Пример 3. Сформируем 
при наличии ошибок во 2-м и 5-м разрядах слова х=1110001, то есть принято слово x`=1010101.
A=1+1+1+1 (mod 2)=0 
B=0+1+0+1 (mod 2)=0 
C=0+1+0+1 (mod 2)=0 
Таким образом, при двукратной ошибке декодирование даёт номер разряда 111, что неверно.
Незначительное увеличение избыточности кода путём введения дополнительного КР1, осуществляющего проверку на чётность всего кода, позволяет обнаружить все двукратные ошибки. Располагает КР1 на месте “0”–го разряда кода. Признаком наличия двукратной ошибки является равенство нулю функции x` при проверке всех разрядов кода на нечётность и равенство “1” хотя бы одной функции 
.
|
|
Пример 4. Найдём КР1 для слова х=1110001.
A=1+1+0+1=1
B=1+1+0+1=1
C=0+0+0+1=1
I+1+0+0+1 (mod 2)=1 I=1
Таким образом, слово примет вид 11110001.
Пусть принято слово x`=11010101 ошибки во 2-м и 5-м разрядам. Сформируем функции 
.
A=1+1+1+1 (mod 2)=0
B=0+1+0+1 (mod 2)=0
C=0+1+0+1 (mod 2)=0
I=1+1+0+1+0+1+0+1=1 x`=0
Таким образом, в коде присутствуют 2 ошибки.
Общий недостаток избыточных кодов – они не приспособлены для выполнения арифметической операции.
Задача. Закодировать данное слово кодом Хэмминга 1001 0001 1101 1110 0000 000
РЕШЕНИЕ. Для кодирования данного сообщения длиной m = 23 потребуется k = 5 дополнительных разряда, т.е. на выходе получим сообщение длиной n = 28 (количество дополнительных разрядов подбирали из соотношения 2k ≥ n+1, n – число полученных разрядов, k – число дополнительных разрядов). 
Пусть закодированное сообщение имеет вид
b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1,
причем разряды b1, b2, b4, b8, b16 будут контрольными, а остальные информационными.
Помещаем в информационные разряды разряды исходного числа по порядку, т.е.
b3 =1, b5 = 0, b6 = 0, b7=1, b9=0, b10 =0, b11=0, b12=1, b13= 1, b14=1, b15=0, b17=1, b18=1, b19=1, b20=1, b21=0, b22=0, b23=0, b24=0, b25=0, b26=0, b27=0, b28=0.
Теперь найдем значения контрольных разрядов. Введем для удобства следующие множества:
V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27… - все числа у которых первый разряд равен 1
V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27… - все числа, у которых второй разряд равен 1
V3 = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28… - все числа, у которых третий разряд равен 1
|
|
V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28… - все числа, у которых четвертый разряд равен 1,
V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 … - все числа, у которых пятый разряд равен 1.
Далее под + будем понимать сложение по модулю 2.
Тогда b1 = b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27 = 1 (все разр. из V1, кроме первого)
b2 = b3+b6+b7+b10+b11+b14+ b15+ b18+ b19+ b22+ b23+ b26+ b27 = 1 (все разряды из V2, кроме перв.)
b4 = b5+b6+b7 +b12+b13+ b14+ b15+ b20 +b21+b22+b23+b28 = 1 (все разряды из V3, кроме первого)
b8 = b9+b10+b11+b12+b13+b14+b15+b24+b25+b26+b27+b28 = 1 (все разряды из V4, кроме первого),
b16 = b17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27+b28 = 0 (все разряды из V5, кроме первого).
Таким образом, получили код 1111 0011 0001 1100 1111 0000 0000.
Задача. Пользуясь кодом Хэмминга найти ошибку в сообщении
1111 1011 0010 1100 1101 1100 110.
РЕШЕНИЕ. Сообщение состоит из 27 символов, из них 22 информационные, а 5 – контрольные. Это разряды b1 = 1, b2 = 1, b4 = 1, b8 = 1, b16=0.
Вычислим число J для обнаружения ошибки:
Введем для удобства следующие множества:
V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27… - все числа у которых первый разряд равен 1
V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27… - все числа, у которых второй разряд равен 1
V3 = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23 … - все числа, у которых третий разряд равен 1
V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27 … - все числа, у которых четвертый разряд равен 1,
V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 … - все числа, у которых пятый разряд равен 1.
Разряды числа J определяются следующим образом:
j1 = b1 + b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27 = 1
j2 = b2+ b3+b6+b7+b10+b11+b14+ b15+ b18+ b19+ b22+ b23+ b26+ b27= 0
j3 = b4+ b5+b6+b7 +b12+b13+ b14+ b15+ b20 +b21+b22+b23 = 0
j4 = b9+b10+b11+b12+b13+b14+b15+b24+b25+b26+b27 = 0,
j5 = b16+ b17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27 = 1
то есть число J=100012 = 1710.
Таким образом, ошибка произошла в семнадцатом разряде переданного числа, следует 1 заменить на 0. Получим 1111 1011 0010 1100 0 101 1100 110
Теперь удалим контрольные разряды. Получим 1101 0010 1100 1011 1001 10 - переданное число.