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

ТОИ  2011-2012 уч. год

 

Практическое занятие №6

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

1. Обнаружение одиночной ошибки (1).

 

 Наиболее известные из самоконтролирующихся и самокорректирующихся кодов – коды Хемминга. Построены они применительно к двоичной системе счисления.

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

Коды Хемминга имеют большую относительную избыточность, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при d = 3), либо для исправления одиночных и обнаружения без исправления двойных ошибок (d = 4). В таком коде n-значное число имеет m информационных и k контрольных разрядов. Каждый из контрольных разрядов является знаком четности для определенной группы информационных знаков слова. При декодировании производится k групповых проверок на четность. В результате каждой проверки в соответствующий разряд регистра ошибки записывается 0, если проверка была успешной, или 1, если была обнаружена нечетность.

Группы для проверки образуются таким образом, что в регистре ошибки после окончания проверки получается K-разрядное двоичное число, показывающее номер позиции ошибочного двоичного разряда. Изменение этого разряда – исправление ошибки.

Первоначально эти коды предложены Хеммингом в таком виде, при котором контрольные знаки занимают особые позиции: позиция i-го знака имеет номер 2i–1. При этом каждый контрольный знак входит лишь в одну проверку на четность.

Рассмотрим код Хемминга, предназначенный для исправления одиночных ошибок, т. е. код с минимальным кодовым расстоянием d = 3.

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

k ³ log2(n + 1).

(1)

Отсюда

m £ n – log2(n + 1).

(2)

Значения m и k для некоторых коротких кодов, вычисленные по формулам (1) и (2) даны в табл. 7.1.

Таблица 1. Значения m и n

n	3	4	5	6	7	8	9	10	11	12
m	1	1	2	3	4	4	5	6	7	8
k	2	3	3	3	3	4	4	4	4	4

 

 

Чтобы число в регистре ошибок (РОШ) указывало номер позиции ошибочного разряда, группы для проверки выбираются по правилу:

I гр.:		все нечетные позиции, включая и позиции контрольного разряда, т. е. позиции, в первом младшем разряде которых стоит 1.
II гр.:		все позиции, номера которых в двоичном представлении имеют 1 во втором разряде справа (например, 2, 3, 6, 7, 10) и т. д.
III гр.	:	разряды, имеющие "1" в третьем разряде справа, и т. д.

Примечание: каждый контрольный знак входит только в одну проверяемую группу. 

 

Пример 1. Пусть k = 5 (табл. 7.2).

Таблица 2. Формирование контрольных групп

Номер проверки	Позиция контрольного знака	Проверяемые позиции
1	1	1, 3, 5, 7, 9, 11, 13, ...
2	2	2, 3, 6, 7, 10, 11, ...
3	4	4, 5, 6, 7, 12, 13, ...
4	8	8, 9, 10, 11, 12, 13, ...
5	16	16, 17, 18, 19, 20, 21

 

 

Пример 2. Рассмотрим семизначный код Хемминга, служащий для изображения чисел от 0 до 9 (табл. 7.3).

Таблица 7.3. Семизначный код Хемминга 

 

Десятичное	Простой двоичный				Код Хемминга
число	код							к		к	к
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	0	1	1	1
2	0	0	1	0	0	0	1	1	0	0	1
3	0	0	1	1	0	0	1	1	1	1	0
4	0	1	0	0	0	1	0	1	0	1	0
5	0	1	0	1	0	1	0	1	1	0	1
6	0	1	1	0	0	1	1	0	0	1	1
7	0	1	1	1	0	1	1	0	1	0	0
8	1	0	0	0	1	0	0	1	0	1	1
9	1	0	0	1	1	0	0	1	1	0	0

 

 

Пусть передан код числа 6 в виде "0 1 1 0 0 1 1", а приняли в виде "0 1 0 0 0 1 1". Проверочные группы:

I проверка :	разряды 1, 3, 5, 7 – дает 1 в младший разряд РОШ.
II проверка :	разряды 2, 3, 6, 7 – дает 0 во второй разряд РОШ.
III проверка:	разряды 4, 5, 6, 7 – дает 1 в третий разряд РОШ.

Содержимое РОШ "101", значит ошибка в пятой позиции.

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

Вывод. Рост кодового расстояния позволяет увеличить корректирующую способность кода. В то время как d = 2 у кода с проверкой на четность позволяет обнаруживать одиночную ошибку, код Хемминга с d = 3 исправляет ее.  

Задание 1.

1. Передан код числа 5 в виде "0 1 0 1 1 0 1", а приняли в виде "0 1 0 1 0 0 1". Обнаружить позицию ошибки.

Для обнаружения ошибки производят проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 0+0+0+1 нечетна. В младший разряд номера ошибочной позиции запишем 1.

Вторая проверка: сумма П2+П3+П6+П7 = 1+0+0+1 четна. Во второй разряд номера ошибочной позиции запишем 0

Третья проверка: сумма П4+П5+П6+П7 = 1+1+0+1 нечетна. В третий разряд номера ошибочной позиции запишем 1.

Номер ошибочной позиции 101= 5. Следовательно, символ пятой позиции следует изменить на обратный, и получим правильную кодовую комбинацию.

 

2. Передан код числа 8 в виде "1 0 0 1 0 1 1", а приняли в виде "1 0 1 1 0 1 1". Обнаружить позицию ошибки.

Для обнаружения ошибки производят проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 1+0+0+1 четна. В младший разряд номера ошибочной позиции запишем 0.

Вторая проверка: сумма П2+П3+П6+П7 = 0+1+1+1 нечетна. Во второй разряд номера ошибочной позиции запишем 1.

Третья проверка: сумма П4+П5+П6+П7 = 1+0+1+1 нечетна. В третий разряд номера ошибочной позиции запишем 1.

Номер ошибочной позиции 011= 3. Следовательно, символ третей позиции следует изменить на обратный, и получим правильную кодовую комбинацию.

 

2. Обнаружение одиночной ошибки (2).

В коде Хемминга вводится понятие кодового расстояния d (расстояния между двумя кодами), равного числу разрядов с неодинаковыми значениями. Возможности исправления ошибок связаны с минимальным кодовым расстоянием dmin. Исправляются ошибки кратности r = ent (dmin-1)/2 и обнаруживаются ошибки кратности dmin-1 (здесь ent означает "целая часть"). Так, при контроле на нечетность dmin = 2 и обнаруживаются одиночные ошибки. В коде Хемминга dmin = 3. Дополнительно к информационным разрядам вводится L = log2K избыточных контролирующих разрядов, где K - число информационных разрядов, L округляется до ближайшего большего целого значения. L-разрядный контролирующий код есть инвертированный результат поразрядного сложения (т.е. сложения по модулю 2) номеров тех информационных разрядов, значения которых равны 1.

П р и м е р 1. Пусть имеем основной код 100110, т.е. К = 6. Следовательно, L = 3 и дополнительный код равен

010 # 011 # 110 = 111,

где # - символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь вместе с основным кодом будет передан и дополнительный. На приемном конце вновь рассчитывается дополнительный код и сравнивается с переданным. Фиксируется код сравнения (поразрядная операция отрицания равнозначности), и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, то рассчитанный в приемнике дополнительный код равен инверсии от 010 # 110 = 100, т.е. 011, что означает ошибку в 3-м разряде.

П р и м е р 2. Основной код 1100000, дополнительный код 110 (результат инверсии кода 110 # 111 = 001). Пусть принятый код 1101000, его дополнительный код 010, код сравнения 100, т.е. ошибка в четвертом разряде.

Задание 2.

1. Основной код 100110,  принятый код 100100.  Подсчитать дополнительный код. Обнаружить позицию ошибки.

Основной код 100110, т.е. К = 6. Следовательно, L = 3 и дополнительный код равен 010 # 011 # 110 = 111.

Принятый код 100100,  т.е. К = 6. Следовательно, L = 3 и дополнительный код равен 010

Код сравнения 101, т.е. ошибка в 5 разряде.

2. Основной код 0101100,  принятый код 0111100.  Подсчитать дополнительный код. Обнаружить позицию ошибки.

 Основной  код 0101100, дополнительный код 111. Пусть принятый код 0111100, его дополнительный код 100, код сравнения 011, т.е. ошибка в третьем разряде.

 

Самостоятельно:

1. Передан код числа 7 в виде "0 1 1 0 1 0 0", а приняли в виде "1 1 1 0 1 0 0". Обнаружить позицию ошибки.

Для обнаружения ошибки производят проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 0+1+1+0 четна. В младший разряд номера ошибочной позиции запишем 0.

Вторая проверка: сумма П2+П3+П6+П7 = 1+1+0+0 четна. Во второй разряд номера ошибочной позиции запишем 0.

Третья проверка: сумма П4+П5+П6+П7 = 0+1+0+0 нечетна. В третий разряд номера ошибочной позиции запишем 1.

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

 

2. Основной код 0101100, принятый код 0101101.  Подсчитать дополнительный код. Обнаружить позицию ошибки.

Основной код 0101100, дополнительный код 1111. Пусть принятый код 0101101, его дополнительный код 1000, код сравнения 0111, т.е. ошибка в седьмом разряде.

Задание 3 (самостоятельно).

Познакомиться с программой  Code (Папка «Учебник по помехоустойчивому кодированию» на сервере).