Проверка циклическим избыточным кодом ( CRC ) — это код обнаружения ошибок, обычно используемый в цифровых сетях и устройствах хранения для обнаружения случайных изменений цифровых данных. К блокам данных, поступающим в эти системы, прикрепляется короткое контрольное значение , основанное на остатке полиномиального деления их содержимого. При извлечении вычисление повторяется, и, если контрольные значения не совпадают, могут быть предприняты корректирующие действия против повреждения данных. CRC можно использовать для исправления ошибок (см. битовые фильтры ). [1]
CRC называются так потому, что значение проверки (проверки данных) является избыточным (оно расширяет сообщение без добавления информации ) и алгоритм основан на циклических кодах . CRC популярны, потому что их легко реализовать в двоичном аппаратном обеспечении , легко анализировать математически и особенно хорошо обнаруживать распространенные ошибки, вызванные шумом в каналах передачи. Поскольку контрольное значение имеет фиксированную длину, функция , которая его генерирует, иногда используется как хеш-функция .
CRC основаны на теории циклических кодов с исправлением ошибок . Использование систематических циклических кодов, которые кодируют сообщения путем добавления контрольного значения фиксированной длины, с целью обнаружения ошибок в сетях связи было впервые предложено У. Уэсли Петерсоном в 1961 г. [2]Циклические коды не только просты в реализованы, но имеют то преимущество, что они особенно хорошо подходят для обнаружения пакетных ошибок : непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, поскольку пакетные ошибки являются распространенными ошибками передачи во многих каналах связи , включая магнитные и оптические запоминающие устройства. Обычно н-битовая CRC, примененная к блоку данных произвольной длины, обнаружит любой одиночный пакет ошибок не длиннее n бит, а доля всех более длинных пакетов ошибок, которые он обнаружит, приблизительно равна (1 − 2 − n ) .
Спецификация кода CRC требует определения так называемого порождающего полинома . Этот полином становится делителем в полиномиальном длинном делении , в котором сообщение принимается как делимое , частное отбрасывается , а остаток становится результатом. Важным предостережением является то, что полиномиальные коэффициенты вычисляются в соответствии с арифметикой конечного поля , поэтому операцию сложения всегда можно выполнить побитово-параллельно (перенос между цифрами отсутствует).
На практике все обычно используемые CRC используют конечное поле из двух элементов, GF(2) . Эти два элемента обычно называются 0 и 1, что удобно соответствует компьютерной архитектуре.
CRC называется n -битным CRC, если его контрольное значение имеет длину n бит. Для данного n возможны несколько CRC, каждая с другим полиномом. Такой многочлен имеет наивысшую степень n , что означает, что он имеет n + 1 членов. Другими словами, полином имеет длину n + 1 ; для его кодирования требуется n + 1 бит. Обратите внимание, что в большинстве полиномиальных спецификаций либо MSB , либо LSB отбрасываются , поскольку они всегда равны 1. CRC и связанный с ним полином обычно имеют имя в форме CRC- n -XXX, как в таблице ниже.