3.3 Код Хемминга.

Предназначенный для обнаружения и исправления однократной ошибки. При построении кода каждый из k проверочных символов определяется как результат суммирования по модулю 2 определенного сочетания инфор­мационных символов. В результате этого сумма проверяемых инфор­мационных и контрольного символа всегда является четной. Количество контрольных символов определяется по формуле: , где – количество символов в кодовой комбинации. Контрольные символы располагаются на местах определенных по степеням двойки (1, 2, 4, 8, 16…)

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

При проверке на четность мы используем номер позиции соответствующие единице находящейся в том разряде, какую проверку мы делаем, то есть если 1проверка, то смотрим единицы по первому разряду, и т.д.

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

Была принята комбинация 1110111.

П роведём первую проверку на парность:

Сумма парная. В младший разряд

номера позиции ошибки записываем 0.

Вторая проверка:

С умма парная. Во второй разряд номера

позиции ошибки записываем 0.

Третья проверка на парность:

С умма непарная. В третий разряд номера записываем 1.

Номер позиции, где была ошибка – 100. Этот двоичный код соответствует числу 4. Это значит, что четвёртый символ в принятой комбинации надо заменить на противоположный. Получим комбинацию – 1111111.

Информационные символы находятся на позициях 3, 5, 6, 7 , то есть передавался двоичный код 1111, которому соответствует число 15.

4.1 Построение неразделимого циклического кода

Циклический код предназначен для того, чтобы обнаруживать ошибки и в некоторых случаях исправлять их (определить место ошибки и корректировать ее). Циклические коды характеризуются тем, что при циклической перестановке всех символов кодовой комбинации этого кода возникает другая кодовая комбинация этого же кода, то есть если комбинация есть комбинацией циклического кода, то – тоже комбинация этого кода. (n – длина кодовой комбинации). Определение ошибки с помощью циклического кода обеспечивается тем, что в качестве разрешенных комбинаций избираются такие, которые делятся без остатка на некоторый заранее выбранный полином . Если принятая комбинация содержит искажения символов, то деление на полином осуществляется с остатком. При этом формируется сигнал, который свидетельствует об ошибке. Полином называется образующим.

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

Пример:

A(x)=1101

G(x)=1011

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

A(x)=x³+x²+1

G(x)= x³+x+1

A(x)*G(x)= x⁶+x⁵+x⁴+x³+x²+x+1

Полученный циклический код: 1111111