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

Проверить, верно, ли передана комбинация, и при необходимость исправить ошибку.

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

Всего символов в коде n= n_и + n_к

Для вычисления основных параметров кода задается количество символов. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочим, а какие контрольными. Номера контрольных символов удобно выбирать по закону 2ⁱ , где i=0,1,2. Номера контрольных символов: 1,2,4,8,16 и т.д. Затем определяют значения контрольных коэффициентов: сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна – значение контрольного коэффициента 0, в противном случае –1.

а8 a7 a6 a5 a4 a3 a2 a1

1 0 0 1 1 0 1 0

После получения очередного кодового слова на приемном конце необходимо вычислить значения разрядов синдрома кода (7, 4) и организовать проверку на четность полученного кодового слова (обозначим это значение через V):

(27)

Обозначив синдром кода через С, а результат общей проверки на четность - через , и пренебрегая возможностью возникновения ошибок кратности 3 и выше, запишем алгоритм декодирования:

– при С=0 и V=0 ошибок нет;

– при С=0 и V=1 ошибка в восьмом разряде;

– при С 0 и V=0 двойная ошибка (коррекция блокируется, необходимо послать запрос повторной передачи);

– при С 0 и V=1 одиночная ошибка, осуществляется ее исправление.

Вычислим значение синдрома С и выполним общую проверку на четность (вычислим значение V) первого кодового слова Cod 1.

Cod 1=01101111.

С1= а1+а3+а5+а7 = 1+1+0+1 = 1;

С2 = а2+а3+а6+а7= 1+1+1+1 =0;

С3= а4+а5+а6+а7 = 1+0+1+1 = 1.

V = а1+а2+а3+а4+а5+а6+а7+а8 = 1+1+1+1+0+1+1+0 = 0.

С=(с3+с2+с1) = 101, V = 0. Следовательно, произошла двойная ошибка(коррекция блокируется, необходимо послать запрос повторной передачи).

Cod 2 = 00110100.

С1= а1+а3+а5+а7 = 0+1+1+0 = 0;

С2 = а2+а3+а6+а7= 0+1+1+0 = 0;

С3= а4+а5+а6+а7 = 0+1+1+0 = 0.

V = а1+а2+а3+а4+а5+а6+а7+а8 = 0+0+1+1+0+1+0+0 = 1.

С=(с3+с2+с1) = 0, V = 1. Произошла ошибка в восьмом разряде. На передающем конце было отправлено кодовое слово:

Cod 2
Вектор ошибки а8
Верная комбинация

Cod 3=01100010.

С1= а1+а3+а5+а7 = 0+0+0+1 = 1;

С2 = а2+а3+а6+а7=1+0+1+1 = 1;

С3= а4+а5+а6+а7 =0+0+1+1 = 0.

V = а1+а2+а3+а4+а5+а6+а7+а8 = 0+1+0+0+0+1+1+0 = 1.

С=(с3+с2+с1) = 011, V = 1. Следовательно, произошла одиночная ошибка, осуществляется ее исправление.

Верная комбинация: 01100110

Cod 4 = 10011001.

С1= а1+а3+а5+а7 =1+0+1+0 = 0;

С2 = а2+а3+а6+а7=0+0+0+0 = 0;

С3= а4+а5+а6+а7 =1+1+0+0 = 0.

V = а1+а2+а3+а4+а5+а6+а7+а8 =1+0+0+1+1+0+0+1 = 0.

С=(с3+с2+с1) = 0, V = 0. Ошибок нет.

Вывод:

При передаче первого кодового слова Cod 1=01101111 произошла двойная ошибка в связи, с чем необходимо послать запрос на повторную передачу этого кодового слова.

При передаче второго кодового слова Cod 2=00110100 произошла ошибка в восьмом разряде.

При передаче третьего кодового слова Cod 3=01100010 произошла одиночная ошибка, осуществилось ее исправление.

При передаче четвертого кодового слова Cod 4 = 10101101 ошибок не было.

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

Литература.

1 . Дмитриев В.И. Прикладная теория информации .- М.: Высшая школа , 1989 .

2 . Касати Т. и др. Теория кодирования.- М.: Мир, 1978.

3 . Кузин Л.Т. Основы кибернетики .Т.1. Математические основы кибернетики .- М.: Энергия, 1973.

4 . Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования .-

Киев: Вища школа, 1977 .

5 . Фано Р. Передача информации. Статистическая теория связи .- М.: Мир, 1965 .

6 . Хемминг Р.В. Теория кодирования и теория информации .- М.: Радио и связь, 1983 .

7 . Цымбал В.П. Задачник по теории информации и кодированию .- Киев : Вища школа, 1976 .

8 . Теория информации и кодирование .- Киев: Вища школа,1977 .

9 . Шеннон К. Работы по теории информации и кибернетике .- М: Иностранная литература, 1963 .