Коды с обнаружением и исправлением ошибок. Код хемминга

Код Хемминга относится к блоковым кодам. Наиболее простой код, исправляющий ошибки кратности t=1, имеет кодовое расстояние d=3.

Принцип построения:

1) На передающей стороне к k информационным символам добавляется r проверочных символов. Значения проверочных символов (0 или 1) определяются путем проверок на четность. В проверку на четность включают определенные элементы кодовых комбинаций, образующие проверочную группу. Сформированный n-разрядный код, состоящий из k информационных и r проверочных элементов, передается в линию связи.

2) На приемной стороне в тех же проверочных группах производится r проверок на четность.

3) Проверочные группы строятся таким образом, чтобы записи результатов каждой проверки в двоичной форме давало бы r-разрядное двоичное число , указывающее номер разряда (в исчислении с основанием 10) искаженного элемента. Это выражение называют синдромом ошибки.

Для того чтобы обнаружить и исправить все ошибки кратности 1, число проверочных символов выбирается из соотношения . Добавление слагаемого +1 соответствует случаю отсутствия ошибок.

Число элементов помехоустойчивой кодовой комбинации определяется из решения уравнения относительно n:

. (4.6)

Изначально известно число k. Определив n из уравнения (4.6), получим число проверочных разрядов r в новых кодовых комбинациях (таблица 4.1).

Таблица 4.1 – Соотношение числа информационных и проверочных разрядов

k	2	3	4	5	6	7	8	9	10	11	12
n	5	6	7	9	10	11	12	13	14	15	17
r	3	3	3	4	4	4	4	4	4	4	5

Выбор значений и позиций проверочных элементов

Если ошибок нет, то синдром ошибки имеет значение 00…00.

При наличии ошибки двоичный код синдрома ошибки должен указать номер разряда кодовой комбинации (в исчислении с основанием 10), в котором произошло искажение элемента.

Единица в первом разряде синдрома ошибки появляется при искажении любого нечетного разряда кодовой комбинации.

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

(4.7)

То есть в первую проверку должны входить все элементы кодовой комбинации, в первом (младшем) разряде содержится 1. Если , то один из элементов искажен.

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

(4.8)

Если S₂=1, то один из элементов искажен:

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

(4.9)

Четвертая проверочная группа содержит элементы, принимающие значение 1 в четвертом разряде новой кодовой комбинации:

(4.10)

Проверочные элементы каждой кодовой комбинации должны входить только в одну проверку. Таким образом, проверочными должны быть символы, расположенные в 1-м, 2-м, 4-м, 8-м и т. д. (16-м, 32-м,…) разрядах полученной кодовой комбинации.

Обозначим проверочные символы как . Тогда

; ; ; . (4.11)

Пример:

1 0 0 0 0 1 1 – исходная кодовая комбинация (младший разряд слева), k=7.

k₁k₂k₃k₄k₅k₆k₇

По таблице 4.1 найдем число проверочных символов r=4. Помехоустойчивая кодовая комбинация должна содержать n=k+r =11 элементов (разрядов)

k₁ k₂ k₃ k₄ k₅ k₆ k₇

а₁ а₂ а₃ а₄ а₅ а₆ а₇ а₈ а₉ а₁₀ а₁₁ (а₁ – младший разряд).

b₁ b₂ b₃ b₄

Выполнив проверку на четность по описанным выше правилам, определим значения проверочных элементов:

;

;

;

.

Получится новая кодовая комбинация 01100000011, содержащая информационные биты и проверочные биты.

Пусть принят код 01101000011, то есть произошла ошибка в 5-м разряде.

Проверочные группы на приемной стороне:

;

;

;

;

Таким образом, синдром ошибки

, то есть, выявлена ошибка в бите .

Для ее исправления надо выполнить операцию суммирования а₅ с 1 по модулю 2: а₅= а₅1.