CRC16

CRC16 — это циклический избыточный код (CRC) длиной 16 бит, представляющий собой контрольную сумму, используемую для обнаружения случайных ошибок в цифровых данных. CRC16 относится к классу хеш-функций, не являющихся криптографическими, и вычисляется путём деления двоичного представления данных на фиксированный полином (генератор) по модулю 2 в поле Галуа GF(2). Результатом вычисления является 16-битное значение (от 0 до 65535), которое добавляется к блоку данных для последующей верификации целостности.

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

Алгоритм вычисления

CRC16 основан на двоичном делении без переносов. Входные данные рассматриваются как длинное двоичное число, которое делится на заданный полином (например, 0x8005 для CRC-16-IBM). Процесс включает следующие шаги:

1. Инициализация регистра CRC начальным значением (часто 0x0000 или 0xFFFF).
2. Для каждого байта данных выполняется операция XOR с текущим значением регистра.
3. Регистр сдвигается вправо на один бит, и если выдвинутый бит равен 1, выполняется XOR с полиномом.
4. После обработки всех байтов к результату может применяться постобработка (XOR с финальным значением, отражение битов).

Реализация может быть аппаратной (на сдвиговых регистрах с обратной связью) или программной (с использованием таблиц поиска для ускорения).

Полиномы

Разные стандарты CRC16 используют различные полиномы, что определяет совместимость и эффективность обнаружения ошибок. Основные варианты:

• CRC-16-IBM (CRC-16/ARC): полином 0x8005, начальное значение 0x0000, финальный XOR 0x0000. Применяется в протоколах Modbus, USB, Bluetooth.
• CRC-16-CCITT (CRC-16/XMODEM): полином 0x1021, начальное значение 0x0000, финальный XOR 0x0000. Используется в телекоммуникациях, XMODEM, PPP.
• CRC-16-DNP (DNP3): полином 0x3D65, начальное значение 0x0000, финальный XOR 0xFFFF. Применяется в системах промышленной автоматизации.
• CRC-16-USB: полином 0x8005, начальное значение 0xFFFF, финальный XOR 0xFFFF. Используется в протоколах USB.

История

Концепция циклических избыточных кодов была разработана в 1961 году американским математиком Уэсли Питерсоном в статье «Cyclic Codes for Error Detection». В 1970-х годах CRC16 стал широко применяться в телекоммуникационных протоколах и системах хранения данных. В 1980-х годах стандарт CRC-16-CCITT был принят Международным союзом электросвязи для передачи данных в сетях X.25. С развитием микроконтроллеров и встраиваемых систем CRC16 стал стандартным методом проверки целостности в протоколах Modbus, CAN и других.

Применение

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

CRC16 является основным методом контроля ошибок в протоколах промышленной автоматизации:

• Modbus RTU: 16-битная контрольная сумма вычисляется для каждого кадра, начиная с адреса устройства. Полином — CRC-16-IBM.
• CAN bus: в стандарте CAN 2.0B используется 15-битный CRC, но в некоторых расширениях (CAN FD) применяется 17-битный или 21-битный CRC. Однако для низкоуровневых протоколов часто применяется CRC16.
• DNP3: протокол телемеханики использует CRC-16-DNP для каждого блока данных.

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

• PPP (Point-to-Point Protocol): использует CRC-16-CCITT для проверки кадров.
• Bluetooth: в пакетах базовой скорости применяется 16-битный CRC для проверки заголовка и данных.
• USB: в пакетах данных используется CRC-16-USB для защиты полезной нагрузки.

Накопители и память

• Флеш-память NAND: некоторые контроллеры используют CRC16 для обнаружения ошибок в страницах данных.
• Дискеты: в старых форматах (например, MFM) применялся CRC16 для секторов.
• CD/DVD: в стандартах компакт-дисков используется CRC16 для подканалов.

Криптография и безопасность

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

Характеристики и ограничения

Обнаружение ошибок

CRC16 гарантированно обнаруживает:

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

Ограничения

• Не обнаруживает ошибки, кратные полиному (например, если данные изменены таким образом, что остаток от деления совпадает).
• Не защищает от преднамеренных модификаций — CRC16 легко подделать, зная алгоритм и полином.
• Не подходит для криптографических целей (например, проверки паролей или цифровых подписей).

Реализация

Программная реализация (на C)

``c uint16_t crc16_ibm(uint8_t *data, size_t len) { uint16_t crc = 0x0000; for (size_t i = 0; i < len; i++) { crc ^= data[i]; for (int j = 0; j < 8; j++) { if (crc & 0x0001) { crc = (crc >> 1) ^ 0x8005; } else { crc >>= 1; } } } return crc; } ``

Табличная реализация

Для ускорения вычислений используется таблица из 256 значений, предварительно рассчитанных для каждого байта. Это позволяет обрабатывать байт за одну операцию XOR и один сдвиг.

Аппаратная реализация

В микроконтроллерах и FPGA CRC16 реализуется с помощью сдвигового регистра с обратной связью (LFSR). Например, в контроллерах CAN используется аппаратный модуль CRC, вычисляющий 15-битный код за один такт.

Сравнение с другими CRC

CRC16 занимает промежуточное положение между CRC8 и CRC32, обеспечивая достаточную надёжность для большинства приложений при низких вычислительных затратах.

Интересные факты

• В протоколе Modbus RTU CRC16 вычисляется для всего кадра, включая адрес, функцию и данные, но исключая стоп-биты.
• В стандарте CRC-16-CCITT начальное значение 0xFFFF используется для обнаружения ведущих нулей в данных.
• CRC16 применяется в некоторых алгоритмах сжатия данных (например, в формате PNG для проверки чанков).
• В криптографии CRC16 иногда используется как часть генераторов псевдослучайных чисел, но это не рекомендуется из-за предсказуемости.

Источники

1. Peterson, W. W., Brown, D. T. (1961). «Cyclic Codes for Error Detection». Proceedings of the IRE.
2. International Telecommunication Union (1988). «Recommendation X.25: Interface between Data Terminal Equipment (DTE) and Data Circuit-terminating Equipment (DCE) for terminals operating in the packet mode and connected to public data networks by dedicated circuit».
3. Modbus Organization (2006). «Modbus Application Protocol Specification V1.1b».
4. USB Implementers Forum (2000). «Universal Serial Bus Specification Revision 2.0».
5. Tanenbaum, A. S., Wetherall, D. J. (2011). «Computer Networks» (5th ed.). Pearson.
6. Press, W. H., Teukolsky, S. A., Vetterling, W. T., Flannery, B. P. (2007). «Numerical Recipes: The Art of Scientific Computing» (3rd ed.). Cambridge University Press.