Кодирование с использованием циклических кодов

И математического аппарата умножения и деления полиномов.

Сигнатурный анализ

Циклический код.

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

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

G(x³)=x³+x+1.

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

Идея построения циклического кода основана на понятии неприводимого многочлена, который делится только на себя и на единицу:

G(x²)=x²+x+1;

G(x)=x+1;

G(x¹⁶)=x¹⁶+x⁹+x⁷+x⁴+1.

По существу, используется так называемое поле Галуа – алгебра с двумя операциями: умножением и сложением по модулю 2 (GF(2)).

Умножение полиномов.

Некоторый полином x³+1 можно записать в развёрнутой форме:

Здесь коэффициенты принимают значения из бинарного множества.

Умножение производится по правилам обычной алгебры, например:

(х³+1)х=х⁴+х, т.е. получили:

Это сдвиг на один разряд вправо.

С учетом использования операции сложения по модулю 2, одинаковые разряды при сложении уничтожаются.

Рассмотрим пример умножения информационного полинома А=х³+1 на порождающий (образующий) полином G=х³+х+1.

Аналитически процесс умножения можно представить так:

Процесс умножения в развернутом виде показан в табл. 66.

                                                                                           Таблица 66

Умножение A на образующий полином G

	х6	х5	х4	х3	х2	х	1
А×1				х3			1
А×x			х4			х
А×x3	х6			х3
А×G	х6		х4			х	1

 

Проведем умножение в двоичном коде:

х⁶_пр х⁵_пр х⁴_пр х³_пр х²_пр х_пр 1_пр – порядок следования разрядов произведения (пр).

Получим уравнения для произведения многочленов, при условии, что множитель G «жестко задан», а полином А – любой, – степени три:

А_мн=х³_мн х²_мн х_мн 1_мн – это переменные множимого (мн)-полинома

третьей степени.

G= 1 0 1 1 – множитель (образующий полином).

Процесс умножения в развернутом виде показан в табл. 67.

                                                                                           Таблица 67

Å	0 х3мн	0 х2мн	х3мн 0 хмн	х3мн х2мн 0 1мн	х2мн хмн 0	хмн 1мн	1мн
	х3мн	х2мн	х3мн Å хмн	х3мн Åх2мн Å1мн	х3мн Å хмн	хмн Å1мн	1мн

Умножение A на образующий полином G

           х⁶_пр х⁵_пр        х⁴_пр                       х³_пр                       х²_пр            х_пр      1_пр

Т.е. уравнения, описывающие значения разрядов произведения, в зависимости от значения разрядов множимого при условии «жестко заданного» множителя имеют вид:

Эти уравнения позволяют определить вид соответствующего устройства – умножителя полиномов, основанного на D-триггерах и элементах сложения по модулю 2.

Деление полиномов.

По аналогии с умножением вводится операция деления полиномов.

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

Например:

Здесь используется суммирование по модулю 2, поэтому х⁶+х⁶=0, аналогично х⁴+х⁴=0, х³+х³=0, х+х=0, 1+1=0.

Деление полиномов можно выполнять последовательными вычитаниями по модулю 2.

Можно показать, что если А – делимое (дл), G – делитель, то разряды частного (чст) определяются так:

1_чст=х³_длÅх⁵_длÅх⁶_дл

х_чст=х⁴_длÅх⁶_дл

х²_чст=х⁵_дл

х³_чст=х⁶_дл

Остаток:

1_ост=1_длÅх³_длÅх⁵_длÅх⁶_дл

х_ост=х_длÅх³_длÅх⁴_длÅх⁵_дл

х²_ост=х²_длÅх⁴_длÅх⁵_длÅх⁶_дл

Нулевой остаток указывает на отсутствие ошибки. Такие уравнения позволяют построить схемы – делители на образующий полином.