CRC-16

CRC-16 — это циклический избыточный код (Cyclic Redundancy Check) с длиной контрольной суммы 16 бит, используемый для обнаружения случайных ошибок в цифровых данных. Относится к классу несекретных хеш-функций, применяемых в протоколах передачи данных, системах хранения информации и цифровых интерфейсах. Основное назначение CRC-16 — выявление одиночных и множественных битовых ошибок, вызванных помехами в канале связи или дефектами носителя.

Принцип работы

Алгоритм CRC-16 основан на делении двоичного представления данных на фиксированный полином (генераторный многочлен) по модулю 2 в поле Галуа GF(2). В отличие от арифметического деления, операция выполняется без переносов: сложение и вычитание заменяются операцией «исключающее ИЛИ» (XOR). Результатом деления является остаток длиной 16 бит, который и представляет собой контрольную сумму.

Процесс вычисления включает следующие этапы:

1. Исходное сообщение дополняется 16 нулевыми битами (для размещения остатка).
2. Выполняется последовательное деление сообщения на выбранный полином с использованием сдвигового регистра.
3. После обработки всех битов сообщения регистр содержит остаток — значение CRC-16.
4. Полученный остаток может быть инвертирован или дополнен в зависимости от конкретной реализации.

При проверке целостности данных получатель выполняет аналогичное деление принятого сообщения вместе с контрольной суммой. Если остаток равен нулю (или заданному фиксированному значению, например 0x0F47 для CRC-16-IBM), данные считаются неповреждёнными.

Полиномы и разновидности

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

Полиномы выбираются так, чтобы обеспечить максимальную обнаруживающую способность для типичных длин сообщений. Например, CRC-16-CCITT обнаруживает все одиночные и двойные ошибки, все ошибки нечётной кратности, все пакетные ошибки длиной до 16 бит и 99,997% пакетных ошибок большей длины.

Характеристики

Обнаруживающая способность

CRC-16 гарантированно обнаруживает:

• Все одиночные битовые ошибки.
• Все двойные битовые ошибки (при условии, что полином является примитивным).
• Все ошибки нечётной кратности (если полином содержит множитель x+1).
• Все пакетные ошибки длиной не более 16 бит.
• 99,998% (для CRC-16-CCITT) пакетных ошибок длиной более 16 бит.

Скорость вычисления

Аппаратная реализация CRC-16 на сдвиговых регистрах с обратной связью (LFSR) выполняется за 16 тактов на каждый байт данных при битовой обработке. Программные реализации с табличным методом (таблица на 256 значений) обрабатывают байт за 1-2 такта процессора, что делает CRC-16 одним из самых быстрых методов контроля целостности.

Ограничения

CRC-16 является несекретным алгоритмом и не предназначен для защиты от преднамеренных модификаций данных. Он не обладает криптографической стойкостью: зная полином, злоумышленник может подделать контрольную сумму. Для задач аутентификации и защиты от подделки применяются криптографические хеш-функции (SHA-2, SHA-3) или коды аутентичности сообщений (HMAC).

Применение

Промышленные сети и протоколы

CRC-16-IBM используется в протоколе Modbus RTU для контроля целостности кадров данных. В протоколе DNP3 применяется CRC-16-DNP. В стандарте CAN (Controller Area Network) используется CRC-15, но в некоторых расширениях — CRC-16.

Компьютерные интерфейсы

USB-пакеты содержат CRC-16 для поля данных (CRC-16-USB) и CRC-5 для поля токена. В интерфейсе SCSI используется CRC-16 для проверки данных на шине.

Хранение данных

CRC-16 применяется в файловых системах (например, в ZFS для проверки целостности блоков), в форматах архивов (ZIP, RAR — для проверки отдельных файлов) и в системах коррекции ошибок на жёстких дисках.

Телекоммуникации

В протоколах X.25 и HDLC кадры содержат CRC-16-CCITT. В стандарте Bluetooth пакеты базовой полосы используют CRC-16 для проверки заголовка и полезной нагрузки.

Встраиваемые системы

Микроконтроллеры и ПЛИС часто реализуют CRC-16 аппаратно для проверки данных в энергонезависимой памяти (EEPROM, Flash) и при обмене по последовательным интерфейсам (SPI, I²C).

Реализация

Программная (табличный метод)

Наиболее эффективный программный способ — предварительное вычисление таблицы из 256 значений CRC для всех возможных байтов. Каждый байт данных обрабатывается как индекс в таблице, что позволяет вычислить CRC за 16 операций XOR на байт.

``c uint16_t crc16_ibm(uint8_t data, size_t len) { uint16_t crc = 0x0000; while (len--) { crc ^= data++ << 8; for (int i = 0; i < 8; i++) { if (crc & 0x8000) crc = (crc << 1) ^ 0x8005; else crc <<= 1; } } return crc; } ``

Аппаратная

В ПЛИС и специализированных микросхемах CRC-16 реализуется на сдвиговом регистре с обратной связью. Каждый полином соответствует определённой схеме подключения XOR-элементов между разрядами регистра.

История

Циклические коды были разработаны в 1961 году Уэсли Питерсоном (Wesley Peterson) как класс линейных кодов, исправляющих ошибки. Первые практические реализации CRC появились в 1970-х годах в протоколах передачи данных. CRC-16-CCITT был стандартизирован ITU-T (тогда CCITT) в рекомендации V.41 (1972 год). CRC-16-IBM стал широко применяться в устройствах IBM (флоппи-диски, протоколы BSC) с середины 1970-х годов. К началу 1980-х CRC-16 стал обязательным компонентом большинства промышленных протоколов и интерфейсов хранения данных.

Сравнение с другими контрольными суммами

CRC-16 занимает промежуточное положение между быстрыми, но менее надёжными методами (CRC-8, Adler-32) и более мощными, но медленными (CRC-32, SHA-256). Для приложений с ограниченными ресурсами (микроконтроллеры, низкоскоростные линии связи) CRC-16 остаётся оптимальным выбором.

Источники

1. Peterson, W. W., & Brown, D. T. (1961). Cyclic Codes for Error Detection. Proceedings of the IRE, 49(1), 228-235.
2. ITU-T Recommendation V.41 (1972). Code-Independent Error Control System.
3. Williams, R. (1993). A Painless Guide to CRC Error Detection Algorithms. Rocksoft Pty Ltd.
4. Modbus Application Protocol Specification V1.1b3 (2012). Modbus Organization.
5. USB 2.0 Specification (2000). USB Implementers Forum.
6. Koopman, P. (2002). 32-Bit Cyclic Redundancy Codes for Internet Applications. Proceedings of the International Conference on Dependable Systems and Networks.