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

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

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

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

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

Выводы

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

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