Значения некоторых известных полиномов, используемых на практике.

При вычитании соотношение разрядов не важно, главное — это одинаковая размерность и единичные старшие биты. В этом случае считается, что вычитаемое меньше уменьшаемого. Это и есть проявление слабого понятия размерности.

Рис. 9. Схема вычисления CRC-деления

Рис. 8. Схема вычисления двоичного деления (с циклическим переносом)

CRC-деление (рис. 9).

 

Снос двоичных разрядов при CRC делении из делимого продолжается до тех пор, пока размерности промежуточного битового значения и делителя не сравняются, а их старшие разряды не станут равными 1.После этого над двоичными разрядами выполняется побитовое CRC-вычитание.

Частное для процесса вычисления CRC-кода не имеет никакого значения.

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

В терминах полиномиальной арифметики исходное двоичное число называется полиномом данных (сообщения) и обозначается как D(x).

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

· порождающий полином G(x) — предварительно особым образом выбранный полином, на который делится исходный полином сообщения;

· полином-частное Q(x) — полином, получившийся в качестве частного от деления полиномов D(x)/G(x);

· полином-остаток R(x) — полином, получившийся в качестве остатка от деления полиномов D(x)/G(x). Полином-остаток R(x) называется CRC (Cyclic Redundancy Code).

Между перечисленными полиномами существуют следующие отношения:

D(x)=Q(x)*G(x)+R(x), Q(x)=(D(x)-R(x))/G(x).

D(x)=Q(x)*G(x)+R(x);

 

Выбор делителя G(x)

При выборе делителя G(x) должны учитываться следующие свойства:

· Число разрядов (количество членов) в полиноме-остатке R(x) непосредственно определяется длиной самого порождающего полинома G(x). Выбор G(x) длиной n гарантирует, что полином-остаток от деления R(x) будет иметь разрядность не более, чем n-1.

· Способность порождающего полинома G(x) к выявлению ошибок, специфичных для передачи данных по каналами связи. Это такие ошибки, как ошибки в одном, двух, нечетном количестве битов, а также ошибки блока битов.

Для большинства алгоритмов вычисления CRC значение порождающего полинома известно и утверждено соответствующими стандартами. Определять новое значение порождающего полинома G(x) нет необходимости.

· x¹⁶+х¹²+х⁵+х⁰ (1 0001 0000 0010 0001b) — полином 1021h, используемый в протоколе XMODEM и производных от него протоколах передачи данных. Он стандартизован в спецификации V.41 МККТТ «Кодонезависимая система контроля ошибок».

· х¹⁶+х¹⁵+х²+х⁰ (1 1000 0000 0000 0101b)— полином 8005h, используемый в протоколе двоичной синхронной передачи фирмы IBM. Он также стандартизован. Этот полином широко известен как полином, используемый в алгоритме вычисления CRC — CRC16.

· x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁹+x⁷+x⁵+x⁴+x²+x¹+x⁰

(1 0000 0100 1100 0001 0001 1110 1011 0111b) – полином 04C1 1EB7h, используемый в алгоритме вычисления CRC — CRC32 и также стандартизованный в стандарте V.42 МККТТ. Этот полином, в частности, используется в технологии локальных вычислительных сетей Ethernet.

· x³²+x³¹+x³⁰+x²⁹+x²⁷+x²⁶+x²⁴+x²³+x²¹+x²⁰+х¹⁹+х¹⁵+х⁹+х⁸+х⁵. (1 1110 1101 1011 1000 1000 0011 0010 0000b=EDB8 8320) Данный полином используют различные архиваторы.

 

Степень полинома – номер позиции его старшего единичного бита (считая с нуля). Например, для полинома 1011 степень равна 3.