Кодирование с исправлением ошибок в системах цифровой связи

Пример 2. Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.
Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.
1. По заданной длине информационного слова (k = 8), используя соотношения вычислим основные параметры кода n и m.


m = [log2 {(k+1)+ [log2(k+1)]}]= [log2 {(9+1)+ [log2(9+1)]}]=4,

при этом n = k+m = 12, т. е. получили (12, 8) - код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.
Для рассматриваемой задачи (при n = 12) номера контрольных позиций равны 1, 4, 8.
При этом кодовая комбинация имеет вид:
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12
к1 к2 1 к3 1 0 1 к4 1 0 1 1
3. Определяем значения контрольных разрядов (0 или 1) путем многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контрольный и определенные проверочные биты.
Номера информационных бит, включаемых в каждую проверку, определяется по двоичному коду натуральных n-чисел разрядностью - m.
0001 b1 Количество разрядов m - определяет количество проверок
0010 b2
0011 b3 1) к1 b3  b5 b7 b9 а11 = к111111 =>
0100 b4 четная при к1=1
0101 b5 2) к2 b3 b6 b7 b10 b11= к210101 =>
0110 b6 четная при к2=1
0111 b7 3) к3 b5 b6 b7 b12 = к31011=>
1000 b8 четная при к3=1
1001 b9 4) к4 b9 b10 b11 b12 = к11011 =>
1010 b10 четная при к4=1
1011 b11
1100 b12
Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 1 0 1 1 1 0 1 1
Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1
Для обнаружения и исправления ошибки составим аналогичные проверки на четность контрольных сумм, результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции.
1) к1 b3 b5 b7 b9 b11 = 110111 =1
2) к2 b3 b6 b7 b10 b11 = 110101 =0
3) к3 b5 b6 b7 b12 = 10011 =1
4) к4 b9 b10 b11 b12 = 11011 =0
Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.

Вывод
В каждую проверку включается один контрольный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение -0, в противном случае - 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n –чисел разрядностью – m (табл. 1, для m = 4) или при помощи проверочной матрицы H(mn), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2k –1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид:

Для обнаружения и исправления ошибки составляются аналогичные проверки на четность контрольных сумм, результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции, который определяется по двоичной записи числа, либо по проверочной матрице.

Литература

1. 
   Вернер М. Основы кодирования. — М.: Техносфера, 2004.
   
2. 
   Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.
   
3. 
   Кнут Дональд, Грэхем Роналд, Паташник Орен Конкретная математика. Основание информатики — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703.
   
4. 
   Лидовский В.И. Теория информации. - М., «Высшая школа», 2002. – 120с.
   
5. 
   Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: Высшая школа, 2001 г. – 383с.