CRC FAQ. Что, зачем и как

1. Глава 1. Что такое CRC и зачем он нужен
2. Глава 2. Базовая теория, необходимая для вычисления CRC
3. Глава 3. Модификация алгоритма для практического применения
4. Глава 4. Резюме

Глава 1. Что такое CRC и зачем он нужен

CRC (cyclic redundancy code) — циклический избыточный код, иногда называемый также контрольным кодом. По своей сути — это просто вычисленное на основе исходного передаваемого сообщения число (или можно сказать код), которое передаётся вместе с самим сообщением (дописывается в конец информационной части) и служит для контроля его безошибочной передачи.

Число это вычисляется по определённым правилам и всегда имеет строго определённое заранее количество разрядов. Очень удобно заранее знать, сколько разрядов занимает контрольное число, потому что иначе станет заранее неизвестной длина сообщения целиком, вместе с CRC, даже при условии, что мы точно знаем длину информационной части. Кроме того, это позволяет заранее выделить для вычисления CRC регистр нужного размера.

Никакой дополнительной информационной нагрузки это число не несёт, поэтому с точки зрения передачи полезной информации оно избыточно. Однако, как я уже сказал, его наличие позволяет диагностировать некоторое количество ошибок, если такие возникают при передаче.

Глава 2. Базовая теория, необходимая для вычисления CRC

По большому счёту, вся теория нахождения CRC базируется на двух вещах.

Первое. Любое сообщение можно представить в виде одного большого двоичного числа и считать что значения разрядов этого числа кодируют коэффициенты некоторого полинома.

Например, возьмём сообщение «15». В шестнадцатиричном виде оно кодируется так: 0x31,0x35. Если перевести эту запись в двоичную форму и записать всё в одну строку, то получим: 00110001 00110101. Если считать, что каждый разряд полученного числа — это коэффициент полинома, то этот полином будет иметь вид:
0*x¹⁵+0*x¹⁴+1*x¹³+1*x¹²+0*x¹¹+0*x¹⁰+0*x⁹+ 1*x⁸+0*x⁷+0*x⁶+1*x⁵+1*x⁴+0*x³+1*x²+ 0*x¹+1*x⁰
Кратко его можно записать так: x¹³+x¹²+x⁸+x⁵+x⁴+x²+1

По большому счёту, мы можем оставить и двоичную запись (чаще всего так и делают, иксы писать неудобно), но будем помнить, что теперь это не просто число, а вектор, составленный из коэффициентов полинома (можно даже продолжать называть такие вектора полиномами). Причём нулевые коэффициенты при старших степенях можно опустить (в дальнейшем вы увидите, что нулевые коэффициенты при старших степенях ни на что не влияют) и написать его в виде 11000100110101.

Второе. Количество разрядов любого двоичного сообщения — это вполне конкретные, конечные числа. Соответственно, множества всех возможных N-разрядных сообщений (где N-любое целое положительное число), составленных по описанному выше способу, — это конечные множества. При использовании особой алгебры такие конечные множества можно считать конечными полями, являющимися расширением простого конечного поля GF(2). Соответственно, любые полиномы, коэффициенты которых составлены из значений разрядов двоичных чисел, можно рассматривать как многочлены над конечным полем.

Подробно многочлены над конечными полями изучаются в отдельном разделе математики, в который мы не будем сильно углубляться в рамках этой статьи. Если кто-то хочет узнать больше — вектор поисков для самостоятельного изучения, я считаю, вполне определён. Нам же интересно, что это за особая алгебра и как это связано с вычислением CRC.

Так вот, отличия этой алгебры от обычной заключаются в следующем:
— операции сложения и вычитания в ней тождественны и выполняются как сложение по модулю 2 (XOR),
— вместо понятий «меньше»/»больше» используются понятия «старше»/»младше». Старшим считается многочлен с большей степенью (наибольшая степень, у которой коэффициент при x равен единице). Например x³+1 старше, чем x²+x, потому что 3>2.

Нахождение CRC заключается в делении с остатком информационного полинома (тот который составлен из информационного сообщения) на некоторый специальный полином. Делим мы как обычно — столбиком, но вместо операции «вычитания» используем «сложение по модулю 2» и продолжаем деление до тех пор, пока оставшийся в делимом полином не окажется младше полинома делителя. Полученный остаток — это и есть CRC.

Для примера разделим рассмотренный выше полином, составленный из сообщения «15», на полином x⁴+x+1, для чего сначала запишем последний полином со всеми коэффициентами в явном виде (1*x⁴+0*x³+0*x²+1*x¹+1*x⁰), а потом запишем эти коэффициенты в виде вектора (10011). Деление будет выглядеть так, как на рисунке справа.

Нули в самом начале делимого, как я и обещал, нам не пригодились, точно также, как они не пригодились бы нам и при обычном делении.

Идём далее. Что это за специальный полином, на который мы делим наше представленное в виде полинома сообщение?

А это как раз один из основных параметров CRC-алгоритма, называемый также порождающим многочленом или порождающим полиномом. В качестве порождающего многочлена обычно берут какой-либо неприводимый многочлен.

Деление с остатком на полином степени N позволяет получить 2^N различных остатков от деления, причем все эти остатки можно описать N-1 разрядными векторами.

Описанные выше действия — это то, что мы по сути всегда делаем при нахождении CRC. Такое описание алгоритма удобно теоретикам и неудобно инженерам. Поэтому теперь перейдём к частностям, которые приближают нас к практической действительности.

Глава 3. Модификация алгоритма для практического применения.

Посмотрим ещё раз внимательно на наш пример деления столбиком и обратим внимание вот на что — при вычислениях мы фактически всегда оперируем только пятью битами, а могли бы оперировать и четырьмя, поскольку во всех операциях XOR у нас самый старший бит равен единице и он всегда сокращается. То есть, если считать, что вычисления происходят в каком-то выделенном четырёхбитном регистре, то всё деление будет выглядеть так, как будто мы просто на каждом шаге сдвигаем биты в регистре влево, загружая новое значение младшего бита, а старший бит просто выкидываем, если он равен нулю, или, если он равен единице, выполняем XOR регистра и младших четырёх битов порождающего полинома.

То есть теперь можно описать наш алгоритм так: побитно загружаем наше информационное сообщение в регистр нужного размера (на единицу меньше степени порождающего полинома), каждый раз сдвигая регистр влево и помещая новый бит в младший разряд. При этом, если вытесняемый из регистра старший бит равен единице, то выполняем XOR регистра со всеми битами порождающего полинома, кроме старшего. Значение регистра после обработки всего сообщения — это и есть CRC.

На картинке слева тот же самый пример, который мы рассматривали выше, но оформленный в соответствии с новым (инженерным) описанием алгоритма вычисления CRC (хотя по сути, это то же самое деление, что и выше).

Одно отличие в нашем инженерном алгоритме от рассматриваемого выше деления столбиком всё же есть. Отличие это заключается в начальном значении регистра. Мы инициализировали регистр нулями. В итоге наше сообщение стало несколько длиннее первоначального. Как мы знаем, нули в начале сообщения не влияют на результат вычислений, их там можно хоть сколько написать. Но ведь можно инициализировать регистр и не нулями.

Что изменится? Да особенно ничего, просто мы тогда будем искать CRC для несколько модифицированного исходного сообщения (с приписанными в начале битами). Если тот, кто будет определять правильность передачи сообщения, знает об этом и знает какое значение для инициализации регистра нужно выбирать, то он сможет правильно посчитать CRC. Надо сказать, что на практике чаще всего используется инициализация всего регистра нулями или инициализация всего регистра единицами.

Ещё одна особенность практической реализации основана на таком свойстве деления с остатком: если C — это остаток от деления A на B, то остаток от деления (A-C) на B будет равен нулю, а остаток от деления (A-C+D) на B будет равен D (если D < B). Это свойство прекрасно работает как с обычной алгеброй, так и с модифицированной, поэтому на практике, при вычислении CRC, на стороне передатчика дописывают дополнительные биты к исходному сообщению не только спереди, но и сзади, однако приёмнику эти дописанные сзади биты не передают, а вместо них передают вычисленный CRC.

Что нам это даёт? Это упрощает реализацию вычисления CRC на стороне приёмника. Например, если сообщение, для которого мы ищем CRC, оканчивается нулями, то сообщение без этих нулей, но с записанным вместо них CRC можно считать разностью исходного сообщения и вычисленного остатка. Значит если посчитать CRC для этой разности — он будет равен нулю.

То есть, если передатчик, при вычислении CRC, сзади к сообщению дописал нули, а приёмнику передал сообщение с записанным вместо нулей CRC, то приёмник, вместо того, чтобы сначала вычислять CRC для сообщения без контрольного кода, потом принимать CRC в отдельную ячейку памяти, а потом сравнивать вычисленный CRC с принятым, может просто вычислить CRC для всего входящего потока бит (вместе с передаваемым в конце сообщения CRC) и сравнить результат с нулём, сэкономив таким образом пару регистров.

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

Не знаю, понятно я объяснил или нет, если нет — смотрим на картинку справа (там всё, о чём говорилось выше, показано на нашем любимом примере).

Глава 4. Резюме

Подведём краткий итог. Вычисление CRC заключается в нахождении остатка от деления полинома, составленного по определённым правилам на основе исходного сообщения, на порождающий полином. Полиномы при этом записываются просто битовыми последовательностями коэффициентов. Полученный остаток, разрядность которого всегда на единицу меньше степени порождающего полинома — это и есть CRC.

Для полного описания алгоритма недостаточно просто указать разрядность контрольного кода (например CRC8 или CRC16), для этого необходимо, во-первых, задать параметры формирования на основе исходного сообщения битовой последовательности, для которой вычисляется CRC, и, во-вторых, описать используемый для вычисления CRC порождающий полином. Ну или хотя бы дополнительно сослаться на название интерфейса, в котором этот алгоритм используется, чтобы полное описание можно было посмотреть в соответствующей спецификации (например, CRC8-1Wire, CRC8-SAE J1850, CRC16-USB, CRC16-Bluetooth и так далее).

Порождающий полином может быть приведён в явном виде (с иксами), в виде двоичного числа (коэффициенты полинома) или в виде соответствующего шестнадцатиричного числа. Кроме того, поскольку коэффициенты при старшей и младшей степенях порождающего полинома всегда равны 1, то один из этих коэффициентов могут опускать. Например, полином, рассматриваемый нами в примерах, может быть записан следующими способами:

• в виде полинома: x⁴+x+1
• в виде двоичного (шестнадцатиричного) числа (коэффициенты полинома): 10011 ( 0x0B )
• в виде двоичного (шестнадцатиричного) числа без старшего бита (самый распространённый вариант): 0011 ( 0x03 )
• в виде двоичного (шестнадцатиричного) числа без младшего бита 1001 ( 0x09 )

Параметры, определяющие формирование битовой последовательности должны описывать:

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

Наличие последнего параметра связано с тем, что сообщения как правило передаются побайтно и при этом возможны два варианта передачи: старшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в нормальном порядке) или младшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в обратном порядке). Причём, иногда переворачивают не только биты в байтах, но и, например, байты в словах. Кстати говоря, во всех примерах, которые приводятся в этой статье, рассматривался только нормальный порядок бит (старшим битом вперёд).

Кроме того, иногда полученный в результате деления остаток дополнительно инвертируют и в качестве CRC используют не сам остаток, а это инвертированное значение.

Помимо описанного в этой статье прямого способа вычисления, существует, так называемый, табличный или быстрый способ расчёта CRC, но об этом как-нибудь в другой раз. А на сегодня, пожалуй, всё.

P.S. Пример вычисления CRC-8 для 1-Wire можно посмотреть, скажем, в программе для программирования микросхем памяти DS2430, исходники которой можно найти в этой статье.