Систематический код, предложенный в 1949 г. американским учёным Ричардом Хэммингом, обладает способностью не только обнаруживать, но и исправлять одиночные ошибки.
Рассмотрим принцип построения кода Хэмминга с минимальным кодовым расстоянием d= 3, т.е. способностью обнаруживать место появления любой однократной ошибки. Построение кода состоит в разбиении разрядов слова на взаимно пересекающиеся подмножества, причём каждому подмножеству ставится в соответствие один контрольный разряд проверки на чётность. Количество контрольных разрядов кода Хэмминга определяется из следующего соотношения:
2k-1 ³ m+k > 2k-1.
Контрольные разряды перемежаются с информационными и располагаются в позициях с номерами Nk=2i (i = 0, 1, 2, ...), т.е. в позициях с номерами 1, 2, 4, 8, 16 и т.д.
Формирование подмножеств производится на основе анализа номера разряда при записи его в двоичной системе счисления. Все разряды кодового слова, имеющие единицу в первом (младшем) разряде своего номера, включаются в первое подмножество, во втором - во второе и т.д. Затем подсчитывается количество единиц в разрядах, относящихся к каждому подмножеству, и в соответствующий контрольный разряд записывается единица, если это количество нечётно, и ноль - если чётно.
В табл.16.2 иллюстрируется разбиение разрядов на указанные выше подмножества для 15-разрядного кодового слова, состоящего из 11 информационных разрядов и 4 контрольных.
Таблица 16.2
Номер разрядов
кодового слова
Подмножество
десятичный
двоичный
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Пример кодирования 11-разрядного информационного слова А = 10111010111 представлен на рис.16.5.
Рис.16.5. Кодирование информационного слова по Хэммингу
При декодировании (процесс обнаружения ошибки) вычисляется синдром ошибки S = sk sk-1 ... s2 s1 , по которому можно судить о наличии ошибки и её месте. Число разрядов в синдроме ошибки равно числу контрольных разрядов кода Хэмминга для данного слова. В рассматриваемом случае будем иметь четырёхразрядный синдром ошибки S = s4 s3 s2 s1 . Для вычисления разрядов синдрома ошибки si нужно сложить по модулю 2 разряды, относящиеся к i-му подмножеству, включая i-й контрольный разряд кода Хэмминга. Если все разряды синдрома ошибки равны нулю S = 0 0 0 0, то это свидетельствует о том, что в закодированном слове ошибки отсутствуют. Если синдром не равен нулю, значит в слове имеется ошибка, а значение синдрома указывает на ошибочный разряд.
Например, ошибка произошла в пятом справа разряде закодированного слова, причём первым считается крайний правый разряд. Это приведёт к нарушению чётности единиц в первом и третьем подмножествах. Следовательно, разряды синдрома ошибки будут равны: s4 = 0, s3 = 1, s2 = 0, s1 = 1. Синдром ошибки S = 0101 указывает на пятый разряд. Для исправления ошибки достаточно проинвертировать значение указанного разряда.
Однако если в закодированном слове будет присутствовать ошибка кратности 2 или более, синдром ошибки укажет на разряд, не содержащий ошибки.
Легко построить модифицированный код Хэмминга с минимальным кодовым расстоянием d = 4 для определения места одиночной и факта двойной ошибки. Для этого нужно ввести в разрядную сетку ещё один дополнительный разряд для проверки на чётность общего количества единиц в закодированном слове.
Если произойдёт одиночная ошибка, то её выявит проверка на чётность всего слова, а место ошибки определится синдромом ошибки. При искажении содержимого двух разрядов общая проверка на чётность ошибку не зафиксирует, но синдром ошибки будет отличен от нуля. Это указывает на то, что ошибка есть, хотя определить её место становится уже невозможным. Ошибки кратности 3, 5, 7, ... будут восприниматься как одиночная ошибка. Однако ввиду того, что код Хэмминга используется в основном для контроля полупроводниковых ЗУ, в которых наиболее вероятными являются одиночные ошибки (с увеличением кратности ошибки на единицу вероятность её появления уменьшается примерно на порядок), данный недостаток кода можно считать несущественным.
В табл.16.3 показаны варианты решений, принимаемых при декодировании модифицированного кода Хэмминга.
Таблица 16.3
Общая
чётность
Синдром
ошибки
Решение
= 0
= 0
Ошибки нет
= 0
¹ 0
Неисправимая ошибка кратности 2, 4, 6, 8, ...
¹ 0
= 0
Неисправимая пакетная ошибка кратности 2i-1, где i = 2, 3, 4, ... , располагающаяся в 2i-1 младших разрядах закодированного слова
¹ 0
¹ 0
Ошибка кратности 1, 3, 5, 7, ... . Поскольку вероятность появления тройной ошибки в 100 раз меньше, чем вероятность появления однобитовой ошибки, решаем, что произошла одиночная ошибка
По методу Хэмминга могут быть построены коды различной длины. При этом, чем больше длина кода, тем меньше относительная избыточность. Например, для контроля числа, имеющего 56 двоичных разрядов, потребуется только шесть контрольных разрядов кода Хэмминга. Коды Хэмминга используют в основном для контроля полупроводниковых ЗУ и контроля передачи информации по каналам связи. При контроле ЗУ их надёжность увеличивается в 60 - 85 раз [5, 23].
Кроме этого код Хэмминга может быть использован для контроля выполнения арифметических и логических операций [17].
