Алгоритм контрольного суммирования CRC

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

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

В зависимости от вида порождающего многочлена и его длины, изменяется вероятность совпадения контрольных сумм для различных исходных данных и время контрольного суммирования. Наиболее популярными являются алгоритмы CRC, работающие с порождающими многочленами: восьмой (CRC-8), шестнадцатой (CRC - 16) и тридцать второй (CRC – 32) степени.

Выбор длины порождающего многочлена, кратной байту, позволяет ускорить работу программы по контрольному суммированию, обеспечивая достаточную надежность полученного результата. Например, контрольное суммирование CRC-32 в пределе позволяет получить надежность порядка: 2³² = 4.294.967.296. Что в принципе позволяет, практически со 100% вероятностью, обнаруживать сбои при хранении и передаче данных.

Существует достаточно большое разнообразие порождающих многочленов для алгоритмов контрольного суммирования CRC – 8, 16 и 32, подобранных на основе теории кодирования и многочисленных исследований. Ниже приведены некоторые из них:

CRC-8: x⁸ + x⁷ + x⁶ + x⁴ + x² + 1 -иИспользуется формой Dallas Semiconductor в устройствах низкоскоростной связи.

CRC-16: x¹⁶ + x¹⁵ + x² + 1 - используется в таких интерфейсах, как USB, ModBus и других линиях связи.

CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 - используется при кодировании видео и аудио сигналов с использованием стандарта MPEG-2, при кодировании растровых изображений в формате PNG и во многих других случаях.

В вычислительной технике оперировать с полиномами N–степени - неудобно и ресурсоемко. Поэтому полиномы заменяют бинарными последовательностями и вычисляют контрольную сумму, оперируя уже не с полиномами, а с бинарными данными.

Действительно, любому полиному можно однозначно сопоставить бинарную последовательность. Если полином в общем виде записывается, как А₁*Хⁿ + A₂*X^n-1 +…+ A_n-1*X + A_n, где коэффициенты А₁ ... А_n принимают значения единицы или нуля, то достаточно записать последовательность из коэффициентов A₁ ... A_n, чтобы однозначно задать полином. Например, полином Х⁴ + X² + 1 однозначно соответствует бинарной последовательности 10101, так как 1*Х⁴ + 0*Х³ + 1*Х² + 0*Х + 1= Х⁴ + X² + 1.

Так как деление можно заменить повторением операций вычитания, рассмотрим, как осуществляется вычитание в полиномиальной арифметике по модулю 2.

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

Таким образом, вычитание полиномов сводится к операции «исключающего или» с элементами полинома, имеющими одну и ту же степень, а, следовательно, мы можем заменить вычитание полиномов на операцию «исключающие или», с сопоставленными им бинарными последовательностями. Рассмотрим это утверждение на примере вычитания из полинома Х⁴ + X²+1 полинома Х³ + X² (операцию "исключающее или" обзначим значком ‘^’, как это принято в языке Си ):

Используя описанную выше возможность замены полинома на бинарную последовательность, рассмотрим алгоритм подсчета контрольной суммы CRC8:

Исходный массив данных: 1001 0110 0100 1011.

Порождающий многочлен: 1101 0101.

Аналогичным способом подсчитываются контрольные суммы CRC-16, CRC-32, CRC-64 и т.д. Как видите, алгоритмы очень просты и легко реализуются на любой ЭВМ.

Особенно важно здесь, что работаем мы не со всеми данными, а только с небольшой последовательностью битов (для CRC-8 – с 8-ю битами, для CRC-16 – с 16-ю битами), затем, сдвигаясь на один бит, опять работаем с небольшой последовательностью битов такой же длины. Это позволяет нам легко обрабатывать огромные массивы данных, не загружая их полностью в память и не расходауя понапрасну вычислительные ресурсы.

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