И математического аппарата умножения и деления полиномов.
Сигнатурный анализ
Циклический код.
Циклический код обязан своим названием особенности: если некоторая кодовая комбинация принадлежит множеству разрешённых комбинаций, то и комбинация, полученная циклической перестановкой разрядов тоже принадлежит множеству разрешённых комбинаций.
Существует соответствующий математический аппарат умножения и деления полиномов, основным понятием которого является полином, например, третьей степени:
G(x3)=x3+x+1.
Циклические коды позволяют обнаружить не только одиночные, но и групповые ошибки. Такие коды используются при тестировании цифровой аппаратуры, чтобы обнаружить отказы в схемах и при криптографической защите информации.
Идея построения циклического кода основана на понятии неприводимого многочлена, который делится только на себя и на единицу:
G(x2)=x2+x+1;
G(x)=x+1;
G(x16)=x16+x9+x7+x4+1.
По существу, используется так называемое поле Галуа – алгебра с двумя операциями: умножением и сложением по модулю 2 (GF(2)).
Умножение полиномов.
Некоторый полином x3+1 можно записать в развёрнутой форме:
Здесь коэффициенты принимают значения из бинарного множества.
Умножение производится по правилам обычной алгебры, например:
(х3+1)х=х4+х, т.е. получили:
Это сдвиг на один разряд вправо.
С учетом использования операции сложения по модулю 2, одинаковые разряды при сложении уничтожаются.
Рассмотрим пример умножения информационного полинома А=х3+1 на порождающий (образующий) полином G=х3+х+1.
Аналитически процесс умножения можно представить так:
Процесс умножения в развернутом виде показан в табл. 66.
Таблица 66
Умножение A на образующий полином G
| х6 | х5 | х4 | х3 | х2 | х | 1 | |
| А×1 | х3 | 1 | |||||
| А×x | х4 | х | |||||
| А×x3 | х6 | х3 | |||||
| А×G | х6 | х4 | х | 1 |
Проведем умножение в двоичном коде:
х6пр х5пр х4пр х3пр х2пр хпр 1пр – порядок следования разрядов произведения (пр).
Получим уравнения для произведения многочленов, при условии, что множитель G «жестко задан», а полином А – любой, – степени три:
Амн=х3мн х2мн хмн 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
х6пр х5пр х4пр х3пр х2пр хпр 1пр
Т.е. уравнения, описывающие значения разрядов произведения, в зависимости от значения разрядов множимого при условии «жестко заданного» множителя имеют вид:
Эти уравнения позволяют определить вид соответствующего устройства – умножителя полиномов, основанного на D-триггерах и элементах сложения по модулю 2.
Деление полиномов.
По аналогии с умножением вводится операция деления полиномов.
При делении необходима операция вычитания по модулю 2, однако результат этой операции совпадает с результатом суммы по модулю 2.
Например:
Здесь используется суммирование по модулю 2, поэтому х6+х6=0, аналогично х4+х4=0, х3+х3=0, х+х=0, 1+1=0.
Деление полиномов можно выполнять последовательными вычитаниями по модулю 2.
Можно показать, что если А – делимое (дл), G – делитель, то разряды частного (чст) определяются так:
1чст=х3длÅх5длÅх6дл
хчст=х4длÅх6дл
х2чст=х5дл
х3чст=х6дл
Остаток:
1ост=1длÅх3длÅх5длÅх6дл
хост=хдлÅх3длÅх4длÅх5дл
х2ост=х2длÅх4длÅх5длÅх6дл
Нулевой остаток указывает на отсутствие ошибки. Такие уравнения позволяют построить схемы – делители на образующий полином.
