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

Разработку этих принципов впервые начал Хэмминг, который предложил код с автоматическим исправлением единичной (!) ошибки в кодовой комбинации.

Формула его работы:

n = n ₀+ k,

где k – проверочные элементы;

n ₀ – информационные элементы.

Причём, автоматическое определение местоположения ошибочного элемента обеспечивается в результате проведения “ k ” проверок на чётность (т.е. число проверок на чётность равно числу проверочных элементов!).

Рассмотрим подробнее код Хэмминга.

Хемминг ввёл понятие “расстояние d ” – это параметр, определяющий различие между кодовыми комбинациями. Например, для двоичного кода расстояние – это число символов, на которые одна кодовая комбинация отличается от другой.

Избыточность кода (обеспечивающая коррекцию кода) количественно определяется выражением:

R = (n - n ₀) / n ₀.

n ₀ – количество информационных элементов достаточных для образования нужного числа комбинаций кода.

Хэмминг показал, что не только обнаружить, но и скорректировать ошибку можно, если увеличить расстояние d до величины:

d_min =1 + Δ + S,

где Δ – кратность (количество) обнаруживаемой ошибки;

S – кратность (количество) исправленной ошибки.

Здесь Δ >= S.

Так, если рассматривать однократные ошибки (Δ=1, S =1), то расстояние d=1+1+1=3 обеспечивает обнаружение и исправление однократной ошибки (либо только обнаружение двукратной ошибки!).

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

Коррекция осуществляется автоматическим устройством, выдающим правильную при приеме как неискаженной комбинации, так и искаженной в одном символе.