Введение
CRC (Cyclic Redundancy Check, циклический избыточный код) – широко применяемый алгоритм обнаружения ошибок при передаче данных по каналам связи или при хранении на носителях. Алгоритм генерирует короткую контрольную сумму фиксированной длины из блока данных; получатель выполняет ту же операцию и сравнивает результат – несовпадение означает повреждение данных.
CRC не исправляет ошибки (для этого существуют коды с исправлением ошибок – ECC, Reed-Solomon), а лишь обнаруживает их с высокой надёжностью. Алгоритм основан на математике полиномов над полем GF(2) – вычислениях по модулю 2.
История и контекст
CRC изобрёл W. Wesley Peterson в 1961 году, опубликовав работу «Cyclic Codes for Error Detection». В ней он предложил использовать полиномиальное деление над полем GF(2) для генерации контрольного кода. С 1970-х годов CRC стал стандартом де-факто для обнаружения ошибок в коммуникационных системах.
CRC-32 (32-битная версия) был включён в стандарт IEEE 802.3 для Ethernet в 1980 году и стал одним из наиболее распространённых CRC-полиномов. Сегодня различные варианты CRC встроены практически в каждый цифровой интерфейс: USB, SATA, Bluetooth, ZIP, PNG.
Как это работает
Алгоритм CRC состоит из нескольких шагов:
- Выбор полинома-делителя: стандартный полином фиксированной длины (например, CRC-32: 0x04C11DB7). Длина CRC = степень полинома (32 бита для CRC-32).
- Дополнение сообщения: к данным добавляются n нулей (n = длина CRC в битах).
- Полиномиальное деление по модулю 2 (XOR): сообщение делится на полином-делитель с использованием операции XOR (без переноса).
- Остаток = CRC: остаток от деления добавляется к передаваемым данным.
- Проверка на приёме: получатель делит принятые данные (включая CRC) на тот же полином – если остаток равен нулю, ошибок нет.
Аппаратная реализация CRC через регистры сдвига с обратной связью (LFSR) работает за один такт на бит, что делает алгоритм исключительно быстрым.
Где применяется
- Сетевые протоколы: Ethernet (IEEE 802.3) использует CRC-32 в поле FCS (Frame Check Sequence) каждого кадра.
- Файловые форматы: ZIP, PNG, GZIP хранят CRC для проверки целостности файлов.
- Последовательные интерфейсы: USB, HDLC, CAN-bus используют CRC для защиты передачи данных.
- Хранение данных: файловые системы (ext4, NTFS, ZFS) применяют CRC для обнаружения повреждений на носителе.
- Телекоммуникации: GSM, DVB, ATM используют различные полиномы CRC.
Преимущества и ограничения
Преимущества: высокая надёжность обнаружения ошибок (CRC-32 обнаруживает все одиночные, двойные и все ошибки нечётной кратности); исключительно эффективная аппаратная реализация; стандартизированность.
Ограничения: CRC обнаруживает, но не исправляет ошибки; уязвим к намеренным манипуляциям данными (не является криптографической функцией); длина контрольной суммы ограничивает обнаруживаемые ошибки.
Связь с другими понятиями
CRC относится к классу хешей/контрольных сумм, но не является криптографическим хешем (MD5, SHA-256 обеспечивают защиту от намеренных модификаций). Аналоги для других целей: Checksum (простая сумма байтов), Parity bit (бит чётности). В сетевом стеке CRC работает на канальном уровне (L2), тогда как IP-checksum – на сетевом (L3). Для исправления ошибок (а не только обнаружения) применяются коды Хэмминга, Reed-Solomon и Turbo-коды.
