Код Хемминга

Код Хемминга исправляет однократные ошибки. Опознаватель кода Хемминга строится так, чтобы полученный при проверках результат r ₁, r ₂, …, r_{n - k} прямо указывал бы номер искаженного разряда. Для этого проверочные символы должны находиться на номерах позиций, которые выражаются степенью двойки (2⁰, 2¹, 2², …, 2^r-1). Таким образом, если нумеровать позиции слева направо, то контрольные символы должны находиться на первой, второй, четвертой и т. д. позициях.

Результат первой проверки дает цифру младшего разряда синдрома в двоичной записи. Если младший разряд r ₁ опознавателя содержит 1 (т.е. результат первой проверки равен 1), то искажение должно быть в одной из нечетных позиций кодовой комбинации. Следовательно, первое уравнение проверки должно содержать символы с нечетными номерами а ₁, а ₃, а ₅, а ₇ и т.д. (таблица 2).

Таблица 2

Символы разрядов опознавателя

Аналогично, во второе уравнение проверки должны входить символы, содержащие в двоичной записи номера единицы во втором разряде: а ₂, а ₃, а ₆, а ₇ и т.д. При третьей проверке должны проверяться символы а ₄, а ₅, а ₆, а ₇ и т.д.

r 1 =a 1 a 3 a 5 a 7 a 9 ...= 0 r 2 =a 2 a 3 a 6 a 7 + a 10 ... =0 r 3 =a 4 a 5 a 6 a 7 a 12 ... =0 r 4 =a 8 a 9 a 10 a 11 a 12 ... =0

Тогда номер позиции ошибочного символа:

a _ош.= r ₄× 2³+ r ₃× 2²+ r ₂× 2¹+ r ₁× 2⁰

С целью упрощения операций кодирования и декодирования проверочные символы размещаются так, чтобы каждый из них включался бы в минимальное число проверок. Удобно размещать контрольные символы на позициях, номера которых встречаются только в одной из проверок: 1, 2, 4, 8, ….

Следовательно, в кодовой комбинации символы а ₁, а ₂, а ₄, а ₈, … должны быть проверочными, а символы а ₃, а ₅, а ₆, а ₇, …- информационными.

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

Представим в качестве примера простую двоичную комбинацию 10011 кодом Хемминга (k =5, t =1). Из соотношения следует, что n = 9. Кодовая комбинация принимает вид а ₁ а ₂1 а ₄001 а ₈1.

Используя уравнение проверок вычислим значения проверочных символов

a ₁= a ₃ a ₅ a ₇ a ₉ =1,

a ₂= a ₃ a ₆ a ₇=0,

a ₄= a ₅ a ₆ a ₇=1,

a ₈= a ₉ a ₁₀=1.

Следовательно, будет передана комбинация 101100111(а ₁ – а ₉).

Если при передаче информации произошла одиночная ошибка и была принята, например, комбинация 101101111, то декодирование дает следующий результат:

r ₁= a ₁ a ₃ a ₅ a ₇ a ₉ =0,

r ₂= a ₂ a ₃ a ₆ a ₇ =1,

r ₃= a ₄ a ₅ a ₆ a ₇ =1,

r ₄= a ₈ a ₉ a ₁₀ =0.

Тогда a _ош.= r ₄× 2³+ r ₃× 22+ r ₂× 21+ r ₁× 20 =1× 2²+1× 2¹ = 6, т.е. искажен элемент с порядковым номером 6, его надо изменить на противоположный, т.е. на 0.

Лекция 19. Кодирование информации циклическими кодами

План:

1. Циклические коды

2. Полиноминальное представление циклических кодов

3. Порождающий многочлен циклического кода

4. Разделимые и неразделимые циклические коды

5. Матричное представление циклических кодов

6. Выбор образующего полинома

19.1.Циклические коды. Основные свойства и способы построения.

Циклические коды получили широкое применение благодаря их эффективности при обнаружении и исправлении ошибок. Схемы кодирующих и декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе обычных регистров сдвига. Название кода произошло от свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов исходной комбинации, принадлежащей и этому же коду. Например, если комбинация a₀ a₁ a₂ ….a_n-1 является разрешенной комбинацией циклического кода, то комбинация a_n-1 a₀ a₁ a₂ ….a_n-2 тоже принадлежит этому коду.