СЕВЕРО-КАВКАЗСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра
Защиты информации
ЛЕКЦИЯ
по учебной дисциплине "Теория информации "
для студентов специальности 075500 (090105) – Комплексное обеспечение информационной безопасности автоматизированных систем
Лекция 9 Основы построения циклических кодов
Ставрополь 2009 г.
Цель занятия: Изучить основные свойства циклических кодов, а также способы их задания. Ознакомиться с матричным представлением циклических кодов. Изучить методику обнаружения и исправления ошибок в циклических кодах.
Учебные вопросы занятия.
Основные свойства циклического кода и способы его задания - 30 мин.
Матричное представление циклических кодов - 25 мин.
Методика обнаружения и исправления ошибок в циклическом коде - 25 мин.
Основные свойства циклического кода. Способы его задания.
Название кодов произошло от их свойств, заключающихся в том, что кодовая комбинация
может быть получена путем циклической перестановки символов. Циклический сдвиг осуществляется справа налево, причем крайне левый переходит в крайне правую позицию.
Циклические коды удобно рассматриввать не только в виде двоичного кода, но и в полиномиальной форме. В соответствии с этим двоичная комбинация записывается в виде степенного ряда аргумента х, а ее символы являются коэффициентами полинома.
6 5 4 3 2 1 0
В = 1101011 х6+х5+х3+х+1
Использование полиминомиальной формы позволяет свести действия над комбинациями к действиям с полиномами.
Операции над полиномами:
1.Сложение
+ х5+х4+х2+х
х3+х2+х+1
х5+х4+х3+1
2. Вычитание совершается аналогично.
3. Умножение полиномов производится по mod(хn+1), т.е. за результат берется остаток от деления результата обычного умножения полиномов на двучлен хn+1
Пример: произвести умножение числа х5+х4+х2+х на полином х2+1. Причем в канале связи используется шестиразрядный код - n = 6.
х5+х4+х2+х
х2+1
х7+х6+х4+х3
х5+х4+х2+х1
х7+х6+х3+х2+х| х6+1
х7+х х+1
х6+х5+х3+х2
х6+1
х5+х3+х2+1 -результат.
Циклические коды задаются порождающими полиномами. Роль образующего полинома выполняют неприводимые многочлены (делятся на себя и на единицу). Его невозможно представить в виде произведения других полиномов. Если принять условие, что порождающий полином Р(х) является делителем двучлена хn+1, то принадлежность кодовой комбинации к разрешенным определяется безостаточным делением этой к.к. на порождающий (образующий) многочлен.
Циклический код может быть получен путем умножения k -значного кода на порождающий полином со степенью р = n - k.
Методика выбора порождающего полинома:
Порождающий полином выбирается из таблицы неприводимых полиномов, он должен удовлетворять требованиям:
Степень порождающего полинома определяется количеством проверочных символов.
Вес полинома должен быть не менее d(min).
P(x) = x3+x+1
= 3 w = 3
x7+1| p(x)
g(x) - проверочный полином (без остатка).
Х7+1 | x3+x+1
X7+x5+x4 x4+x2+x+1
X5+x4+1
X5+x3+x2
X4+x3+x2+1
X4+x2+x
X3+x+1
X3+x+1
0
Методики получения разрешенных кодограмм циклического кода
Разрешенная кодограмма образуется путем умножения исходной комбинации k - 1 степени на порождающий полином.
(-) информационные символы перемешаны с проверочными
L(11) = 1011 = x3+x+1
B(11) = |L(11)*p(x)| +mod(xn+1) = x3+x+1
x3+x+1
x6+x4+x3
x4+x2+x
x3+x+1
x6+x2+1
B(11) = 1000101 -неразделенная к.к.
К.к. простого k - значного кода умножается на одночлен степени n-k
L(x)*x(n-k) =. После этого полученное произведение делится на порождающий многочлен, т.е L(x)*x(n-k) = = остаток, который дописывается к исходной к.к.
Р(х)
L(13) = 1101 =x3+x2+1
(x3+x2+1)*x3 = x6+x5+x3 |x3+x+1
x6+x4+x3 x3+x2+x+1
x5+x4
x5+x3+x2
x4+x3+x2
x4+x2+x
x3+x
x3+x+1
1
B(13) = 1101001
2. Матричное представление циклического кода
Как и всякий линейный код ц.к. может быть построен на основе порождающей и проверочных матриц. Для формирования строк порождающей матрицы по второму способу построения ц.к. берется комбинация простого к - разрядного кода, содержащего только одну единицу. Затем они умножаются на одночлен
хn-k и делятся на порождающий полином; полученные остатки дописываются в n-k последние строки проверочной матрицы.
Пример: построить порождающую матрицу для ц.к. (7,4) в качестве порождающего многочлена выбрать х3+х2+1.
-
P(7,4)=
1
0
0
0
1
0
1
0
1
0
0
1
1
1
0
0
1
0
0
1
1
0
0
0
1
1
1
0
Для получения первой строки дополнительной матрицы необходимо первую строку информационной матрицы умножить на х3, а затем разделить на порождающий полином.
0001*х3 = х3 | x3+x2+1
x3+x2+1 1
x2+1 =101
0010*x3 = x4 | x3+x2+1
x4+x3+x x+1
x3+x
x3+x2+1
x2+x+1 = 111
0100*x3 = x5 | x3+x2+1
x5+x4+x2 x2+x+1
x4+x2
x4+x3+x
x3+x2+x
x3+x2+1
x+1 = 011
1000* x3 = x6 | x3+x2+1
x6+x5+x3 x3+x2+x
x5+x3
x5+x4+x2
x4+x3+x2
x4+x3+x
x2+x = 110
Чтобы получить проверочную матрицу необходимо определить проверочный полином.
x7+1 | x3+x2+1
x7+x6+x4 x4+x3+x2+1 = g(x) = 11101
x6+x4+1
x6+x5+x3
x5+x4+x3+1
x5+x4+x2
x3+x2+1
x3+x2+1
0
| 0 0 1 1 1 0 1 |
h(p) = | 0 1 1 1 0 1 0 |
| 1 1 1 0 1 0 0 |