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;