10.4. Кодирование по Хэммингу

В ряде случаев для контроля функционирования схем реализации ПФ используют прямое сравнение, т.е. сравнивают реакции на схемах. Кроме того, применяются: прямое дублирование со сравнением результатов, троирование.

В своё время широко применялся контроль по модулю, эффективный при арифметических операциях. Используются классы эквивалентностей чисел по модулю.

|1|₅=|6|₅=|11|₅ – сравнимы по модулю.

Контроль по нечётности – это контроль по модулю 2.

Коды Хэмминга – это кодирование с использованием нескольких групп контроля по модулю 2.

Помехоустойчивое кодирование по Хэммингу – обеспечивает обнаружение и исправление ошибок при передаче информации (контроль передачи информации).

В кодовом слове всего m разрядов, где m=n+k, n – количество информационных разрядов, k – количество контрольных разрядов.

Используется контроль по нечетности, причем формируется несколько групп контроля по нечетности.

Пример. Передается четырехразрядная информация:

Количество контрольных разрядов должно быть таковым, чтобы можно было закодировать как информационные разряды, так и сами контрольные.

В нашем случае: n=4, k=3. Разместим передаваемую информацию в секторах диаграммы Эйлера для трех взаимно пересекающихся множеств А, В, С (рис. 86).

A: k₁=1

B: k₂=1

C: k₃=0

Рис. 86. Диаграмма Эйлера для кодирования по Хэммингу

четырехразрядной информации

Пусть произошла ошибка в разряде х₂ (рис. 87).

Рис. 87. Ошибка в разряде х₂

Искажение (ошибка) привела к изменению информации и нарушению нечетности в двух контрольных группах А и С. Именно это и укажет на номер искаженного разряда. Каждый сектор («кусочек») диаграммы Эйлера определяет один из разрядов n или k.

Для определения числа контрольного разряда необходимо использовать соотношение m2^k–1, или n+k2^k–1.

Далее строится матрица Хэмминга.

1 0 1 0 1 0 1

1 1 0 0 1 1 0

1 1 1 1 0 0 0

x₄ x₃ x₂ k₃ x₁ k₂ k₁

Если дано число информационных разрядов n, то необходимо определить число контрольных разрядов. Выбираются двоичные эквиваленты номеров всех m разрядов (справа налево, младшие разряды вверху). Столбцы с одной единицей отводятся под контрольные разряды. Выделяются три группы контрольных разрядов k₁, k₂, k₃.

В передатчике формируются контрольные разряды по нечётности k₁,k₂,k₃ путём суммирования по модулю 2 соответствующих разрядов.

Записываются уравнения Хэмминга:

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

Синдром ошибки – вектор .

Если искажение не произошло, то синдром нулевой. Если не нулевой он укажет на место ошибки. Если (101), то ошибка в 5-ом столбце, разряд х₂, поскольку этот разряд входит в две группы контроля по нечетности – первую и вторую – это области А и С диаграммы Эйлера (рис. 87).

Иногда реальную информацию передают в другом порядке: отдельно информационные, отдельно контрольные разряды. Представим информацию в матричном виде. Матрица Хэмминга обозначается Н. Информационную подматрицу обозначим Р, а контрольную – I:

Если – входной вектор,– полное кодовое слово, тогда кодирование заключается в следующих матричных операциях:

, где – конкатенация (сцепление) информации в определенном порядке следования разрядов.

На вектор воздействуют ошибки. Используем вектор ошибок:

,

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

.

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