CRC-арифметика
Между перечисленными полиномами существуют следующие отношения:
D(x)=Q(x)xG(x)+R(x), Q(x)=(D(x)-R(x))/G(x).
Эти соотношения приводят к следующим основополагающим для дальнейшего рассмотрения тезисам:
- операция деления двух двоичных полиномов D(x)/G(x), где G(x)*0, дает в качестве результата полином-частное Q(x) и полином-остаток R(x), удовлетворяющие условиям: D(x)=Q(x)xG(x)+R(x);
- остаток от деления двух полиномов R(x) является двоичным числом, которое после вычитания из D(x) дает в результате еще один полином, делящийся без остатка на G(x);
- получающееся в результате этого деления частное Q(x) отбрасывается за ненадобностью, а полином-остаток R(x) называют CRC (Cyclic Redundancy Code).
Из приведенного выше описания общей схемы вычисления CRC возникает ряд вопросов: что представляет собой этот магический делитель G(x), каков его размер? Выбор порождающего полинома G(x) – достаточно сложная задача. Перечислим некоторые важные свойства, которые должны учитываться при этом.
- Число разрядов (количество членов) в полиноме-остатке R(x) непосредственно определяется длиной самого порождающего полинома G(x). Выбор G(x) длиной п гарантирует, что полином-остаток от деления R(x) будет иметь разрядность не более, чем п-1. Это следует из общего свойства операции деления, которое предполагает, что остаток от деления должен быть меньше делителя.
- Порождающий полином G(x) должен быть полиномиально простым. Это означает его неделимость нацело на полиномы со значением в диапазоне от 2 до самого себя.
- Способность порождающего полинома G(x) к выявлению ошибок, специфичных для передачи данных по каналами связи. Это такие ошибки, как ошибки в одном, двух, нечетном количестве битов, а также ошибки блока битов. Выше мы отмечали, что более простые методы обнаружения ошибок передачи не способны обнаружить с достаточной степенью вероятности большинство таких типов ошибок.
Для большинства алгоритмов вычисления CRC значение порождающего полинома известно заранее и, более того, утверждено соответствующими стандартами. Поэтому программисту без особой надобности не стоит терять времени и сил на изобретение нового значения порождающего полинома G(x). Приведем значения некоторых широко известных полиномов, используемых на практике.
- х'6+х12+х5+х° – полином 1021h, используемый в протоколе XMODEM и производных от него протоколах передачи данных. Он стандартизован в спецификации V.41 МККТТ "Кодонезависимая система контроля ошибок".
- х16+х|5+х2+х° – полином 8005h, используемый в протоколе двоичной синхронной передачи фирмы IBM. Он также стандартизован в приложении А "Процедура коррекции ошибок для оконечного оборудования линии с использованием асинхронно-синхронного преобразования" к стандарту V.42 МККТТ. Этот же полином широко известен как полином, используемый в алгоритме вычисления CRC – CRC16.
- x32+x26+x23+x22+x16+x12+x"+xlo+xs+x7+x5+x4+x2+x1+x0 – полином 04clldb7h, используемый в алгоритме вычисления CRC – CRC32 и также стандартизованный в стандарте V.42 МККТТ. Этот полином, в частности, используется в технологии локальных вычислительных сетей Ethernet. Необходимо отметить, что вычисление по алгоритму CRC32 зачастую проводят и с другим полиномом: 0edb88320h;
- x32+x31+x30+x29+x27+x26+x24+x23+x21+x20+ +х19+х15+х9+х8+х5. Последний полином используют различные архиваторы. Необходимо заметить, что полином 0edb88320h – это просто зеркальное отражение полинома 04clldb7h.
В заключение отметим, почему выгодно увеличивать число разрядов CRC. Выше уже было отмечено, что алгоритм вычисления CRC по сути своей является одним из возможных (и неплохих) алгоритмов хэширования. Разрядность порождающего полинома G(x) 16 бит обеспечивает до 65 535 значений хэш-функции. Увеличение разрядности полинома G(x) до 32 битов приводит к расширению набора значений хэш-функции уже до 4 294 967 295.
С полиномом связано еще одно понятие – степени полинома, которое по определению является номером позиции его старшего единичного бита (считая с нуля). Например, для полинома 1011 из приведенного выше примера (см. рис. 9.4) степень равна 3.
В качестве выводов отметим, что CRC-арифметика отличается от двоичной отсутствием переносов/заемов, а CRC-вычитание и сложение выполняются по тем же правилам, что и команда ассемблера XOR, что и обусловливает ее важную роль при вычислении значений CRC.