Исправление ошибок

15 1 1 1 1 1 1 1

2 0 1 0 1 0 1 0

1 1 1 0 1 0 0 1

0 0 0 0 0 0 0 0

Mod2)

Mod2)

1 1 1

1 1 0

1 0 1

0 1 1

0 1 0

H= 1 0 0

В качестве строк матрицы возьмем порядковые двоичные числа номеров строк.

Представим кодовую комбинацию V кода Хэмминга в общем виде:

V= а1 а2 а3 а4 а5 а6 а7_,

где а_i – двоичные разряды двоичного кода, принимающие значения 0 или 1.

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

В общем случае номера позиций контрольных разрядов можно вычислить из выражения 2ⁱ , где i = 0, 1, 2, 3, 4 и т. д.

Следовательно, информационные разряды в кодовой комбинации а3, а5, а6, а7_. Информационные позиции всегда определены, т.к. они заполняются передаваемой информацией.

Контрольные позиции вычисляются по правилам кодирования. Представим кодовую комбинацию V в другом виде:

V= x1 x2 a3 x4 a5 a6 a7,

где символом x отмечены контрольные позиции, а символом a – информационные.

Для нахождения контрольных позиций кода необходимо решить систему уравнений, которая получается после умножения кодовой комбинации Vна проверочную матрицу Hкода Хэмминга. При умножении применяются специальные правила поразрядного умножения и суммирования по модулю 2:

Правила умножения

1*1=1

1*0=0

0*1=0

0*0=0

Правила суммирования

1+1=0

1+0=1

0+0=0

В качестве результата суммирования берем остаток от деления суммы единиц на модуль 2.

По алгоритму кодирования Хэмминга результат умножения комбинации V на любой столбец матрицы должен быть равен нулю.

Умножим комбинацию V на матрицу H

001

V*H=( x1 x2 a3 x4 a5 a6 a7) * 100 = 0

В результате получим три равенства:

x1*0 + x2*0 + a3*0 + x4*1 + a5*1 + a6*1 + a7*1 = 0

x1*0 + x2*1 + a3*1 + x4*0 + a5*0 + a6*1 + a7*1=0

x1*1 + x2*0 + a3*1 + x4*0 + a5*1 + a6*0 + a7*1=0

Учитывая, что умножение на 0 дает нулевой результат, получим три уравнения для вычисления контрольных разрядов кода.

x4=a5 + a6 + a7,

x2=a3 + a6 + a7,

x1=a3 + a5 + a7.

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

Рассмотрим пример вычисления контрольных разрядов кодовой комбинации.

Пусть в комбинации V известны информационные разряды:

a3=1, a5=0, a6=1, a7=0

Тогда начальное состояние комбинации:

V=x1 x2 1 x4 0 1 0,

где разряды x1,x2,x4- не определены.

Подставим в полученные выше уравнения известные информационные разряды и вычислим контрольные :

X4=0+1+0=1

X2=1+1+0=0

X1=1+0+0=1

В результате процедуры кодирования получим одну комбинацию кода Хэмминга:

V=1 0 1 1 0 1 0

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

……………

…………….

…………….

В каждой комбинации информация занимает 4 разряда.

Комбинации используются для передачи информации по каналу связи, в котором возможно искажение кода (ошибки передачи).

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

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

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

Составим таблицу соответствия между ошибками и синдромами.

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

Пример.

0 1 0 1 0 1 0Кодовая комбинация 2

+