Методики получения разрешенных кодограмм циклического кода

Основные свойства циклического кода. Способы его задания.

Учебные вопросы занятия.

Лекция 9 Основы построения циклических кодов

ЛЕКЦИЯ

Защиты информации

Коды Хэмминга.

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

2 ^k £ 2 ⁿ / (n+1)

Код строится таким образом, чтобы в результате r проверок получилось r разрядное число указывающее номер искаженного разряда. Для этого проверочные символы должны находиться на позициях степени два. Результат первой проверки дает младшую цифру разряда синдрома. Если результат проверки даст единицу, то один из символов проверочной группы искажен. Таким образом первой проверке должны быть подвержены символы с номерами: 1, 3, 5, 7, 9, ... Результат второй проверки дает цифру второго разряда синдрома следовательно проверкой должны быть охвачены числа: 2,3,6,7,10,... и т.д.

S1 = A1+A3+A5+A7+A9

S2 =A2+A3+A6+A7

S3 = A4+A5+A6+A7

S4 = A8+A9+A10+A11+...

Проверочная матрица должна иметь n столбцов и r строк. Каждый столбец должен составлять двоичную комбинацию указывающую номер соответствующей позиции в коде.

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

* * * *

A9A8A7A6A5A4A3A2A1

S1 = A1+A3+A5+A7+A9

S2 =A2+A3+A6+A7

S3 = A4+A5+A6+A7

S4 = A8+A9

Пусть задана кодовая комбинация L(19) = 10011

1 * 0 0 1 * 1 * *

A9A8A7A6A5A4A3A2A1

A1 = A1+A3+A5+A7+A9 = 1

A2 =A2+A3+A6+A7 = 1

A4 = A4+A5+A6+A7 = 1

A8 = A8+A9 = 1

B(19) = 110011111

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

B*(19) = 110001111

S1 = 1

S2 = 0

S3 = 1

S4 = 0

0101 -соответствует А5.

Код Хэминга с d(min) = 4 получается из матрицы для кода с d(min) = 3 путем добавления проверочного символа, представляющего собой суммирование по модулю два всех комбинаций.

S5 = A9+A8+A7+A6+A5+A4+A3+A2+A1

по учебной дисциплине "Теория информации "

для студентов специальности 075500 (090105) – Комплексное обеспечение информационной безопасности автоматизированных систем

Ставрополь 2009 г.

Цель занятия: Изучить основные свойства циклических кодов, а также способы их задания. Ознакомиться с матричным представлением циклических кодов. Изучить методику обнаружения и исправления ошибок в циклических кодах.

1. Основные свойства циклического кода и способы его задания - 30 мин.

2. Матричное представление циклических кодов - 25 мин.

3. Методика обнаружения и исправления ошибок в циклическом коде - 25 мин.

Название кодов произошло от их свойств, заключающихся в том, что кодовая комбинация

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

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

_{6 5 4 3 2 1 0}

В = 1101011 Þх⁶+х⁵+х³+х+1

Использование полиминомиальной формы позволяет свести действия над комбинациями к действиям с полиномами.

Операции над полиномами:

1.Сложение

₊ х⁵+х⁴+х²+х

х³+х²+х+1

х⁵+х⁴+х³+1

2. Вычитание совершается аналогично.

3. Умножение полиномов производится по mod(хⁿ+1), т.е. за результат берется остаток от деления результата обычного умножения полиномов на двучлен хⁿ+1

Пример: произвести умножение числа х⁵+х⁴+х²+х на полином х²+1. Причем в канале связи используется шестиразрядный код - n = 6.

х⁵+х⁴+х²+х

х²+1

х⁷+х⁶+х⁴+х³

х⁵+х⁴+х²+х¹

х⁷+х⁶+х³+х²+х| х⁶+1

х⁷+х х+1

х⁶+х⁵+х³+х²

х⁶+1

х⁵+х³+х²+1 -результат.

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

Циклический код может быть получен путем умножения k -значного кода на порождающий полином со степенью р = n - k.

Методика выбора порождающего полинома:

Порождающий полином выбирается из таблицы неприводимых полиномов, он должен удовлетворять требованиям:

1. Степень порождающего полинома определяется количеством проверочных символов.

2. Вес полинома должен быть не менее d(min).

3. P(x) = x³+x+1

r = 3 w = 3

x⁷+1| p(x)

g(x) - проверочный полином (без остатка).

Х⁷+1 | x³+x+1

X⁷+x⁵+x⁴ x⁴+x²+x+1

X⁵+x⁴+1

X⁵+x³+x²

X⁴+x³+x²+1

X⁴+x²+x

X³+x+1

X³+x+1

1. Разрешенная кодограмма образуется путем умножения исходной комбинации k - 1 степени на порождающий полином.

(-) информационные символы перемешаны с проверочными

L(11) = 1011 = x³+x+1

B(11) = |L(11)*p(x)| ⁺_mod(xⁿ₊₁₎ = x³+x+1

x³+x+1

x⁶+x⁴+x³

x⁴+x²+x

x³+x+1

x⁶+x²+1

B(11) = 1000101 -неразделенная к.к.

2. К.к. простого k - значного кода умножается на одночлен степени n-k

L(x)*x^{(n-k) =r}. После этого полученное произведение делится на порождающий многочлен, т.е L(x)*x^{(n-k) =r} ₌ остаток, который дописывается к исходной к.к.

Р(х)

L(13) = 1101 =x³+x²+1

(x³+x²+1)*x³ = x⁶+x⁵+x³ |x³+x+1

x⁶+x⁴+x³ x³+x²+x+1

x⁵+x⁴

x⁵+x³+x²

x⁴+x³+x²

x⁴+x²+x

x³+x

x³+x+1

B(13) = 1101001