CRC деление.
Лекция №13. Прямой алгоритм вычисления CRC. Встроенный ассемблер.
Две операции CRC-арифметики (сложение и вычитание) идентичны и по принципу формирования результата они аналогичны команде ассемблера XOR.
Далее
1*x7+1*x6+1*x5+0*х4+0*x3+0*x2+1*x1+1*х = x7+x6+x5+x1+х°.
Над полиномами можно выполнять арифметические операции: сложение, умножение и вычитание.
Например, для умножения 7h (0111b) на 5h (0101b) выполняются действия:
(х2 + х1 + х°)*(х2 + х°) = (х4 + х3 + х2 + х2 + х1 + х°) =
=х4 + х3 + 2*х2 + х1 + х° = х4 + х3 + х3 + х1 + х° =
= х4 + 2*х3 + х1 + х°=х4+ х4 + х1 + х°=2*х4 + х1 + х°= х5 + х1 + х°
Переносы можно выполнять в случае, когда известно основание системы счисления. То есть до тех пор, пока мы не знаем х, мы не можем производить и переносы.
Операции сложения и вычитания в полиномиальной арифметике абсолютно идентичны и вместо них можно оставить одну.
1) Сложение по правилам полиномиальной арифметики по модулю 2 (CRC-арифметика), будет выполнено так (нет переносов):
+ | |
Правила сложения:
0+0 = 0;
0+1 = 1;
1+0 = 1;
1+1 = 0.
2) Операция вычитания:
- | |
Правила выполнения вычитания в арифметике с отсутствием переносов:
0-0=0;
0-1=1;
1-0=1;
1-1=0.
Умножение в арифметике с отсутствием переносов также выполняется с учетом особенностей CRC-сложения:
x | ------- | ||
--------------- | |||
При этом, в самом умножении особенностей нет, а вот сложение промежуточных результатов производится по правилам CRC-сложения.
Так как CRC-код – это по сути остаток от деления исходной последовательности на некоторое двоичное число.
При делении необходимо ввести в рассмотрение понятие «слабое понятие размерности»: число X больше или равно числу Y, если оба числа имеют одинаковую размерность и позиции их старших битов единичны, то есть соотношение остальных битов X и Y для операции сравнения не имеет значения.
Рассмотрим обычное деление (по правилам двоичной арифметики с циклическим переносом) рис. 8;