Введение в архитектуру компьютеров

         

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


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

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

Коды Хемминга имеют бóльшую относительную избыточность, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при 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) даны в табл. 11.1.

Таблица 11.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 (табл. 11.2).

Таблица 11.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 (табл. 11.3).


Содержание раздела