Код Хемминга (стр. 2 из 3)

Можно построить и такой код, который обнаруживал бы двойные ошибки и исправлял одиночные. Для этого к самокорректирующемуся коду, рассчитанному на исправление одиночных ошибок, нужно приписать ещё один контрольный разряд (разряд двойного контроля). Полное количество разрядов кода при этом будет m+k+1. Цифра в разряде двойного контроля устанавливается такой, чтобы общее количество единиц во всех m + k + 1 разрядах кода было четным. Этот разряд не включается в общую нумерацию и не входит ни в одну контрольную группу.

Например, код Хеминга с m=7 и k=4 Пусть информационное кодовое слово - 0110101

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	Second Parity
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Информационное кодовое слово:	0	1	1	0	1	0	1
p1	1	0	1	0	1	1
p2	0	0	1	0	0	1
p3	0	1	1	0
p4	0	1	0	1
Кодовое слово с контрольными разрядами:	1	0	0	0	1	1	0	0	1	0	1	1

При этом могут быть следующие случаи.

1. В принятом коде в целом и по всем контрольным группам количество единиц четно. Если тройные ошибки и ошибки в большем количестве разрядов исключаются, то первый случай соответствует безошибочному приему кода. Например

2.

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	Контроль по четности в группе	Контрольный бит	Контроль по четности в целом	Контрольный бит в целом
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Переданное кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
Принятое кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
p1	1	0	1	0	1	1	Pass	0
p2	0	0	1	0	0	1	Pass	0
p3	0	1	1	0	Pass	0
p4	0	1	0	1	Pass	0	1	Pass

p4	p3	p2	p1
В двоичном представлении	0	0	0	0
В десятичном представлении	Σ = 0

2. В принятом коде в целом количество единиц нечетно, но во всех контрольных группах количество единиц четно. Второй случай - ошибки только в разряде двойного контроля. Например

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	Контроль по четности в группе	Контрольный бит	Контроль по четности в целом	Контрольный бит в целом
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Переданное кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
Принятое кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
p1	1	0	1	0	1	1	Pass	0
p2	0	0	1	0	0	1	Pass	0
p3	0	1	1	0	Pass	0
p4	0	1	0	1	Pass	0	0	Fail

p4	p3	p2	p1
В двоичном представлении	0	0	0	0
В десятичном представлении	Σ = 0

3. В принятом коде в целом и в некоторых из контрольных групп количество единиц нечетно. Третий случай — одиночной ошибки в каком-либо из остальных разрядов (можно исправить в соответствии с приведенными выше правилами)

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	Контроль по четности в группе	Контрольный бит	Контроль по четности в целом	Контрольный бит в целом
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Переданное кодовое слово :	1	0	0	0	1	1	0	0	1	0	1
Принятое кодовое слово:	1	0	0	0	1	1	0	0	1	0	0
p1	1	0	1	0	1	0	Fail	1
p2	0	0	1	0	0	0	Fail	1
p3	0	1	1	0	Pass	0
p4	0	1	0	0	Fail	1	1	Fail

p4	p3	p2	p1
В двоичном представлении	1	0	1	1
В десятичном представлении	8	2	1	Σ = 11

Из таблицы следует, что ошибка произошла в 11-м разряде и что её можно исправить.

4. В принятом коде в целом количество единиц четно, но в некоторых контрольных группах имеется нечетное количество единиц - двойная ошибка

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	Контроль по четности в группе	Контрольный бит	Контроль по четности в целом	Контрольный бит в целом
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Переданное кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
Принятое кодовое слово:	1	0	1	0	1	0	0	0	1	0	1
p1	1	1	1	0	1	1	Fail	1
p2	0	1	0	0	0	1	Pass	0
p3	0	1	0	0	Fail	1
p4	0	1	0	1	Pass	0	1	Pass

p4	p3	p2	p1
В двоичном представлении	0	1	0	1
В десятичном представлении	4	1	Σ = 5

Раз получившаяся сумма не равна нулю, а контрольный бит указывает на ошибку передачи, то обнаруживаем двойную ошибку. Исправление двойных ошибок здесь, конечно, невозможно.