Код Хемминга

Содержание.

1. Значение кода Хемминга.

2. Код Хемминга.

3. Принцип построения кодов Хемминга.

4. Применение.

5.Литература.

1. Значение кода Хемминга

Код Хэмминга – систематический код, то есть состоящий из информационных и корректирующих символов, расположенных по строго определенной системе, имеющих одинаковую длину и всегда занимающих строго определенные места в кодовых комбинациях.

Предложенные Хэммингом регулярные методы построения кодов, корректирующих ошибки, имеют фундаментальное значение. Они демонстрируют инженерам практическую возможность достижения пределов, на которую указывали законы теории информации. Эти коды нашли практическое применение при создании компьютерных систем. Работа Хэмминга привела к решению проблемы более плотной упаковки для конечных полей. Он ввел в научный обиход важнейшие понятия теории кодирования – расстояние Хэмминга между кодовыми комбинациями в векторном пространстве, определяемом для двоичных кодов как количество позиций этих комбинаций с различными символами, и границы Хэмминга для исправляющей способности блочных корректирующих кодов. Граница Хэмминга для двоичных кодов рассчитывается по следующей формуле:

В этом выражении число ошибок e может быть исправлено корректирующим блочным кодом длиной N, имеющим М кодовых комбинаций (C^j_N – биномиальный коэффициент).

Работа Хэмминга сыграла ключевую роль в последующем развитии теории кодирования и стимулировала обширные исследования, выполненные в последующие годы.

Коды Хэмминга позволяют не только обнаружить наличие ошибки, но и место ее нахождения и, следовательно, дают возможность ее исправить.

2. Коды Хемминга.

Коды Хемминга являются самоконтролирующимися кодами, т.е кодами, позволяющими автоматически обнаруживать наиболее вероятные ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.

При этом, разумеется, мы не получаем никаких указаний о том, в каком именно разряде произошла ошибка, и, следовательно, не имеем возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырёх или вообще в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно.Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенству или , где m - количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице № 1

Диапазон m	kmin
1	2
2-4	3
5-11	4
12-26	5
27-57	6

Имея m+k разрядов, самокорректирующийся код можно построить следующим образом.

Присвоим каждому из разрядов свой номер - от 1 до m+k; запишем эти номера в двоичной системе счисления. Поскольку 2^k > m + k ,каждый номер можно представить, очевидно, k-разрядным двоичным числом.

Предположим далее, что все m+k разрядов кода разбиты на контрольные группы, которые частично перекрываются, причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определённым контрольным группам. Например: разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера 5₁₀ = …000101₂ - 1-й и 3-й разряды содержат единицы.

Среди m+k разрядов кода при этом имеется k разрядов, каждый из которых принадлежит только к одной контрольной группе:

Разряд № 1: 1₁₀ = …000001₂ принадлежит только к 1-й контрольной группе.

Разряд № 2: 2₁₀ = …000010₂ принадлежит только к 2-й контрольной группе.

Разряд № 4: 4₁₀ = …000100₂ принадлежит только к 3-й контрольной группе.

…

Разряд № 2^k−1 принадлежит только к k-й контрольной группе.

Эти k разрядов мы и будем считать контрольными. Остальные m разрядов, каждый из которых принадлежит, по меньшей мере, к двум контрольным группам, будут информационными разрядами.

В каждой из k контрольных групп будем иметь по одному контрольному разряду. В каждый из контрольных разрядов поместим такую цифру (0 или 1), чтобы общее количество единиц в его контрольной группе было четным.

Например, довольно распространен код Хеминга с m=7 и k=4.

Пусть исходное слово (кодовое слово без контрольных разрядов) - 0110101₂.

Обозначим P_i - контрольный разряд №i; а D_i - информационный разряд №i, где i = 1,2,3,

4…

1	2	3	4	5	6	7	8	9	10	11
№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011
Распределение контрольных и информационных разрядов	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). Первая группа контролирует разряды № 3,5,7,9,11 исходного кода, вторая — 3,6,7,10,11 (№ группы = № контрольного разряда). Очевидно, что они частично перекрываются.

Рис.№1 Первая группа контролирует разряды № 3,7,5 исходного кода, вторая — 3,7,6… Очевидно что они частично перекрываются

Предположим теперь, для примера, что при передаче данного кодового слова 10001100101 произошла ошибка в 11–м разряде, так, что было принято новое кодовое слово 10001100100. Произведя в принятом коде проверку четности внутри контрольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й,2-й и 4-й контрольных группах, и четно в 3-й контрольной группе. Это указывает, во-первых, на наличие ошибки, во-вторых, означает, что номер ошибочно принятого разряда в двоичном представлении содержит единицы на первом, втором и четвёртом местах и нуль - на третьем месте, т.к ошибка только одна, и 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

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

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

Например (Рис №2), когда ошибки одновременно прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают подмены.

Рис.№2 Когда ошибки прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают ошибки

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

Например, предположим теперь, что при передаче данного кодового слова 10001100101 произошли ошибки в 3-м и 6-м разрядах, так, что принято кодовое слово 10101000101.

№ разряда:	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

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

Вывод: ошибка произошла в 5-м разряде Истинное кодовое слово : 1 0 0 0 1 1 0 0 1 0 1 Ошибочное кодовое слово : 1 0 1 0 1 0 0 0 1 0 1 Исправленное кодовое слово : 1 0 1 0 0 0 0 0 1 0 1 Результат получается ещё более отдаленным от правильного, чем принятый код. Исправление кода по общему правилу не только не улучшило, но даже ухудшило бы дело.

Можно построить и такой код, который обнаруживал бы двойные ошибки и исправлял одиночные. Для этого к самокорректирующемуся коду, рассчитанному на исправление одиночных ошибок, нужно приписать ещё один контрольный разряд (разряд двойного контроля). Полное количество разрядов кода при этом будет 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

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

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

3. Принцип построения кодов Хемминга.

Построение кодов Хемминга базируется на принципе проверки начетность веса W (числа единичных символов) в информационной груп-пе кодового блока. Поясним идею проверки на четность на примере простейшего кор-ректирующего кода, который так и называется кодом с проверкой начетность или кодом с проверкой по паритету (равенству). В таком коде к кодовым комбинациям безызбыточного первичногодвоичного k-разрядного кода добавляется один дополнительный разряд(символ проверки на четность, называемый проверочным, или конт-рольным). Если число символов 1 исходной кодовой комбинации чет-ное, то в дополнительном разряде формируют контрольный символ 0, аесли число символов 1 нечетное, то в дополнительном разряде форми-руют символ 1. В результате общее число символов 1 в любой переда-ваемой кодовой комбинации всегда будет четным. Таким образом, правило формирования проверочного символа сво-дится к следующему: r1 = i1 ⊕ i2 ⊕ ... ⊕ ik ,где i – соответствующий информационный символ (0 или 1); k – общееих число а под операцией "⊕" здесь и далее понимается сложение поmod 2. Очевидно, что добавление дополнительного разряда увеличива-ет общее число возможных комбинаций вдвое по сравнению с числомкомбинаций исходного первичного кода, а условие четности разделяетвсе комбинации на разрешенные и неразрешенные. Код с проверкой начетность позволяет обнаруживать одиночную ошибку при приеме кодо-вой комбинации, так как такая ошибка нарушает условие четности, пе-реводя разрешенную комбинацию в запрещенную. Критерием правильности принятой комбинации является равенствонулю результата S суммирования по mod 2 всех n символов кода, вклю-чая проверочный символ r1. При наличии одиночной ошибки S прини-мает значение 1: S = r1 ⊕ i1 ⊕ i2 ⊕ ... ⊕ ik =  0 – ошибки нет, = 1 – однократная ошибка. n Этот код является (k +1, k)-кодом, или (n, n–1)-кодом. Минимальноерасстояние кода равно двум (dmin = 2), и, следовательно, никакие ошиб-ки не могут быть исправлены. Простой код с проверкой на четностьможет использоваться только для обнаружения (но не исправления) од-нократных ошибок. Увеличивая число дополнительных проверочных разрядов и форми-руя по определенным правилам проверочные символы r, равные 0 или1, можно усилить корректирующие свойства кода так, чтобы он позво-лял не только обнаруживать, но и исправлять ошибки. На этом и осно-вано построение кодов Хемминга. Коды Хемминга позволяют исправлять одиночную ошибку, с помощьюнепосредственного описания. Для каждого числа проверочных символовr = 3, 4, 5… существует классический код Хемминга с маркировкой (n, k) = (2r–1, 2r–1 – r) , (3.20)т. е. (7,4), (15,11), (31,26) … При других значениях числа информационных символов k полу-чаются так называемые усеченные (укороченные) коды Хемминга.Так, для Международного телеграфного кода МТК-2 , имеющего5 информационных символов, потребуется использование коррек-тирующего кода (9,5), являющегося усеченным от классического кодаХемминга (15,11), так как число символов в этом коде уменьшается(укорачивается) на 6.

4.Применение.

Код Хэмминга используется в некоторых прикладных программах в области хранения данных, особенно в RAID 2; кроме того, метод Хемминга давно применяется в памяти типа ECC и позволяет "на лету" исправлять однократные и обнаруживать двукратные ошибки.

Литература:

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

3. Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с.