Выбор и обоснование информационных характеристик канала связи (стр. 10 из 16)
Декодирование групповых кодов осуществляется с помощью контрольной или проверочной матрицы. Структурно она представляет собой совокупность транспонированной проверочной части генераторной матрицы, дополненной единичной матрицей с левой диагональю.
Для декодирования блочного кода в режиме обнаружения и исправления ошибок необходимо построить контрольную матрицу Н.
Н =
(7.6)H =
Пусть подается первая часть блочного кода (1 строка матрицы М) с запланированной ошибкой:
В =
R =
(7.7)где R – проверочный вектор или синдром
В – передаваемое сообщение – блок как совокупность m-шифрованных и
к – контрольных разрядов
Н – контрольная матрица
R = (2 3 2 2)
R = (0 1 0 0)
Вектор R является девятым столбцом в контрольной матрице Н. Он однозначно указывает на место ошибки переданной кодовой комбинации. Следовательно:
е = (0 0 0 0 0 0 0 0 1 0 0)
Для исправления ошибки:
е (7.8) 
Таким образом, при кодировании сообщения групповым кодом была проверена эффективность данного метода. Алгоритм построен таким образом, чтобы была возможность обнаруживать и исправлять ошибки в переданном сообщении. Это достигается с помощью добавления избыточности в виде контрольных разрядов в каждый блок сообщения.
Необходимо построить циклический код, способный обнаруживать и исправлять одну ошибку при передаче сообщения М = (АКСЕНЕНКО_И), закодированного с помощью метода Хаффмана.
Циклический код – это блочный код, который структурно состоит из информационной части m и проверочной части n.
В отличие от блочного кода циклический код формируется путем смещения разрядов справа налево в каждом цикле. Такой циклический сдвиг обеспечивает поиск и обнаружение ошибок краткости r также, как и в блочном коде.
8.1. Представление сообщения, закодированного методом Хаффмана, в блочной форме
Необходимо передать сообщение М = (АКСЕНЕНКО_И), закодированное методом Хаффмана:
1000010101100110100010111001101110111110001001
В пункте 7 принято, что сообщение, закодированное методом Хаффмана, в блочном виде выглядит следующим образом:
A =
Было также определено:
r = 1
S = 1
d = 3
k = 4
8.2. Построение образующей (генераторной) матрицы
8.2.1. Выбор образующего полинома и определение контрольных разрядов
В основе теории циклических кодов лежит алгоритм поиска контрольных или проверочных групп путем использования простых полиномов. По аналогии с простыми числами простые полиномы – это полиномы, которые не могут быть представлены произведением других полиномов или, иными словами, могут делиться только на себя и на единицу. В общем случае простой полином имеет вид:
(8.1)В качестве коэффициента
используются бинарные числа 0 и 1.Полиномы, с помощью которых осуществляется поиск контрольных разрядов, последующее нахождение и исправление ошибок, получили название образующие полиномы. При использовании образующих полиномов разработаны два способа формирования циклических кодов.
Первый способ базируется на использовании генераторной матрицы.
(8.2)Количество элементов проверяющей части матрицы обосновывается также, как и для групповых кодов, а сами контрольные группы определяются как остатки от деления единицы с неограниченным числом нулей на образующий полином.
Необходимо определить контрольные группы для циклического кода, способного обнаруживать и исправлять одну ошибку. Для этого понадобится образующий полином, который можно выбрать по таблице минимальных неприводимых в поле Галуа многочленов:
Таблица 8.1
| № | 1 | 2 | 3 | 4 |
| 1 | 1 | 111 | 1011 1101 | 10011 11111 111 11001 |
| 2 | ||||
| 3 | ||||
| 4 |
Так как количество разрядов в контрольной группе k = 4, выберем многочлен из четвертого столбца:
P(x) = 11001
P(x) = a1x4+a2x3+a3x0
P(x) = x4+x3+1
Процедура деления осуществляется до тех пор, пока кодовые группы не начнут повторяться.
1 0 0 0 0 0 0 0 0 0 0 |1 1 0 0 11 1 0 0 1 1 1 1 1 0 1 0
1 0 0 1 0
1 1 0 0 1
1 0 1 1 0
1 1 0 0 1
1 1 1 1 0
1 1 0 0 1
0 1 1 1 0
0 0 0 0 0
1 1 1 0 0
1 1 0 0 1
0 1 0 1 0
0 0 0 0 0
1 0 1 0 …
8.2.2. Построение генераторной матрицы
Генераторная матрица по формуле 8.2 состоит из единичной матрицы с правой диагональю и проверочной матрицы, состоящей из полученных остатков.
V =
Сообщение М кодируется блоками путем сложения по модулю 2 соответствующих строк генераторной матрицы.
1 строка: {1 0 0 0 0 1 0}
2 строка: {1 0 1 1 0 0 1}
3 строка: {1 0 1 0 0 0 1}
4 строка: {0 1 1 1 0 0 1}
5 строка: {1 0 1 1 1 0 1}
6 строка: {1 1 1 1 0 0 0}
7 строка: {1 0 0 1 1 1 1}
Таким образом, формируется закодированная матрица, состоящая из результатов сложения по модулю 2:
M = 
Контрольные группы могут быть найдены без генераторной матрицы путем деления информационной группы или блока на образующий полином.
Необходимо выписать информационную часть кода, добавить количество нулей, равное числу контрольных разрядов, и поделить на полином.
1 строка: 1 0 0 0 0 1 0 0 0 0 0 |1 1 0 0 11 1 0 0 1 1 1 1 0 0 1 0
1 0 0 1 1
1 1 0 0 1
1 0 1 0 0
1 1 0 0 1
1 1 0 1 0
1 1 0 0 1
0 0 1 1 0
0 0 0 0 0
0 1 1 0 0
0 0 0 0 0
1 1 0 0 0
1 1 0 0 1
0 0 0 1
2 строка: