Обнаружение и исправление ошибок в коде Хэмминга

Построение кода Хэмминга

Пример: Построить макет кода Хемминга и определить значения корректирующих разрядов для кодовой комбинации k=4, X=0101.

Решение:

Согласно таблице минимальное число контрольных символов r=3, при этом n = 7. Контрольный коэффициенты будут расположены на позициях 1, 2, 4. Составим макет корректирующего кода и запишем его во вторую колонку таблицы. Пользуясь таблицей для номеров проверочных коэффициентов, определим значения коэффициентов К1 К2 и К3.

Первая проверка: сумма П1+П3+П5+П7 должна быть четной, а сумма К1+0+1+1 будет четной при К =0.

Вторая проверка: сумма П2+П3+П6+П7 должна быть четной, а сумма К2+0+0+1 будет четной при К2=1.

Третья проверка: сумма П4+П5+П6+П7 должна быть четной, а сумма К3+1+0+1 будет четной при К3=0.

Окончательное значение искомой комбинации корректирующего кода записываем в третью колонку таблицы макета кода.

Пример . Предположим, в канале связи под действием помех произошло искажение и вместо 0100101 было принято 01001(1)1.

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

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

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

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

Код, исправляющий одиночную и обнаруживающий двойную ошибки

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

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