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

Коды Хемминга относятся к линейным, групповым, систематическим кодам с и

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

Правило нахождения проверочных разрядов является основной задачей построения корректирующих кодов. Рассмотрим этот процесс для кода Хемминга. Сначала познакомимся с понятием синдром кода.

Обнаружение и исправление ошибок избыточными кодами сводится к определению и последующему анализу синдрома.

Под синдромом понимают совокупность элементов, сформированных суммированием по модулю 2 принятых проверочных элементов и вычисленных проверочных элементов и вычисленных проверочных элементов по принятым информационным элементам с использованием одного и того же правила на передаче и приеме.

Если синдром нулевой, то ошибок в принятой КК нет. либо они не обнаружены. Наличие единиц в синдроме указывает на ошибку в принятой КК. Код Хемминга с может исправить одну ошибку, поэтому синдром должен указать номер позиции в КК, где произошла ошибка. Этого достаточно для исправления ошибки в двоичных кодах.

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

Рассмотрим пример построения кода с К=5, способным исправлять 1 кратную ошибку.

Пример: Дано К=5; .

1. Определяем при , с .

2. Определяем необходимое число проверочных разрядов, поскольку , то

Это неравенство решается методом подбора:

----- - не выполняется.

----- - выполняется.

Таким образом, и код имеет вид (9.5).

Обозначим КК в виде:

(1)

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

	Двоичная запись этого номера
С4	С3	С2	С1

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

Аналогично, в алгоритм второй проверки включили те элементы, двоичные коды номеров которых содержат во 2-ом разряде единицу.

Аналогично для 3-ей и 4-ой проверок.

Обозначим результат каждой проверки как П1.Если П1=1. то это означает, что один из элементов КК, охватываемых первой проверкой, искажен. Наличие 1 в младшем разряде синдрома С1 указывает, что искомой искаженный элемент является нечетным, т.к. единицу в первом разряде имеют все нечетные числа. Следовательно, они и должны охватываться первой проверкой:

; = ; (4.26)

Результат второй проверки П2 определяет второй разряд синдрома, т.е.

(4.27)

Далее:

(4.28)

(4.29)

Теперь определим, какие позиции в КК занимают проверочные разряды, а какие информационные. Признаком проверочного элемента является то, что он входит только в один алгоритм проверки. При этом необходимо учесть. что в каждую проверку проверочный элемент должен входить только один раз.

Анализируя уравнения проверок видим, что элемент , входит только в первую проверку;

элемент входит только во вторую проверку;

элемент входит только в третью проверку;

элемент входит только в четвертую проверку.

Поэтому уравнения проверок можно переписать в виде:

(4.30)

В дискретный канал передается следующая КК:

на приеме производится аналогичные проверки (4.31)

;

;

;

; (4.31)

Крышечки у символов означают оценки единичных элементов в месте приема. По виду синдрома определяют номер разряда, где произошла ошибка.

В классическом коде Хемминга проверочные элементы располагаются на позициях, где i- номер проверочного разряда. При такой структуре КК усложняется аппаратура кодера и декодера. Поэтому на практике пользуются модифицированным кодом Хемминга, в котором изменяют, порядок передачи элементов КК в канал. Сначала передают информационные элементы, а затем проверочные.

Классический код Хемминга

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

Модифицированный код

Проверка:

вместо

вместо

вместо

вместо

а на передаче проверки запишутся в виде:

Модифицированный код: Классический код: