Параметры распространённых CRC и кодов Хэмминга
Справочная таблица параметров алгоритмов CRC в модели Rocksoft (Width, Poly, Init, RefIn, RefOut, XorOut) с контрольными значениями от строки «123456789», рассчитанными по алгоритму: CRC-5/USB, CRC-7/MMC, CRC-8, CRC-8/MAXIM, CRC-16/MODBUS, CRC-16/CCITT-FALSE, CRC-16/XMODEM, CRC-32, CRC-32C. Запись полиномов, какие ошибки обнаруживает CRC, параметры кодов Хэмминга и расширенных кодов SECDED.
Циклический избыточный код (CRC) — остаток от деления сообщения, записанного как двоичный многочлен, на порождающий многочлен (полином) степени w. Кроме полинома, конкретный вариант CRC задаётся ещё пятью параметрами (модель Rocksoft, по которой описаны почти все CRC):
- Width — разрядность CRC (степень полинома);
- Poly — полином без старшего бита, в «прямой» записи;
- Init — начальное значение регистра;
- RefIn / RefOut — переворачивать ли биты каждого входного байта и итогового значения (младший бит первым);
- XorOut — значение, с которым складывается результат по модулю 2;
- Check — CRC от ASCII-строки «123456789», по которому проверяют правильность реализации.
Распространённые варианты CRC
Контрольные значения в таблице вычислены по алгоритму с указанными параметрами (во всех вариантах RefIn = RefOut). Проверить свои данные можно в калькуляторе CRC, в котором есть все эти варианты.
| Вариант | Бит | Полином | Init | Отражение | XorOut | CRC от «123456789» | Где применяется |
|---|---|---|---|---|---|---|---|
| CRC-5/USB | 5 | 0x05 | 0x1F | да | 0x1F | 0x19 | пакеты-маркеры USB |
| CRC-7/MMC | 7 | 0x09 | 0x00 | нет | 0x00 | 0x75 | команды SD- и MMC-карт |
| CRC-8 (SMBus) | 8 | 0x07 | 0x00 | нет | 0x00 | 0xF4 | SMBus, ATM HEC |
| CRC-8/MAXIM | 8 | 0x31 | 0x00 | да | 0x00 | 0xA1 | датчики Dallas 1-Wire (DS18B20) |
| CRC-16/ARC | 16 | 0x8005 | 0x0000 | да | 0x0000 | 0xBB3D | архиваторы ARC, LHA |
| CRC-16/MODBUS | 16 | 0x8005 | 0xFFFF | да | 0x0000 | 0x4B37 | протокол Modbus RTU |
| CRC-16/CCITT-FALSE | 16 | 0x1021 | 0xFFFF | нет | 0x0000 | 0x29B1 | многие встраиваемые протоколы |
| CRC-16/XMODEM | 16 | 0x1021 | 0x0000 | нет | 0x0000 | 0x31C3 | протоколы XMODEM, ZMODEM |
| CRC-16/KERMIT | 16 | 0x1021 | 0x0000 | да | 0x0000 | 0x2189 | протокол Kermit, Bluetooth |
| CRC-16/X-25 | 16 | 0x1021 | 0xFFFF | да | 0xFFFF | 0x906E | HDLC, X.25, IrDA |
| CRC-32 | 32 | 0x04C11DB7 | 0xFFFFFFFF | да | 0xFFFFFFFF | 0xCBF43926 | ZIP, gzip, PNG, Ethernet |
| CRC-32C | 32 | 0x1EDC6F41 | 0xFFFFFFFF | да | 0xFFFFFFFF | 0xE3069283 | iSCSI, SCTP, Btrfs, ext4 |
| CRC-32/BZIP2 | 32 | 0x04C11DB7 | 0xFFFFFFFF | нет | 0xFFFFFFFF | 0xFC891918 | архиватор bzip2 |
| CRC-32/MPEG-2 | 32 | 0x04C11DB7 | 0xFFFFFFFF | нет | 0x00000000 | 0x0376E6E7 | цифровое телевидение MPEG-2 TS |
Как записывают полиномы
Один и тот же полином встречается в разных записях. Например, CRC-16-CCITT x¹⁶ + x¹² + x⁵ + 1:
| Запись | Значение | Как получить |
|---|---|---|
| Прямая (normal) | 0x1021 | биты степеней 15…0, старший x¹⁶ опущен |
| Обратная (reversed) | 0x8408 | те же биты в обратном порядке — для реализаций «младшим битом вперёд» |
| Купмана (Koopman) | 0x8810 | биты степеней 16…1, младший член +1 опущен |
| Полная | 0x11021 | все 17 коэффициентов |
Для CRC-32 прямая запись 0x04C11DB7, обратная — 0xEDB88320 (именно эта константа встречается в большинстве табличных реализаций ZIP и Ethernet).
Какие ошибки обнаруживает CRC
- все одиночные ошибки — если в полиноме больше одного ненулевого члена;
- все ошибки в нечётном числе бит — если полином делится на (x + 1), как у CRC-16-CCITT и CRC-16/ARC;
- все пакеты ошибок (подряд идущие искажённые биты) длиной до w включительно;
- длинные пакеты — с вероятностью пропуска около 2−w (для CRC-32 — одна на 4 миллиарда).
CRC защищает только от случайных искажений. Злоумышленник может подобрать изменения так, что CRC не изменится, поэтому для защиты от подделки нужны криптографические хеши и коды аутентификации (HMAC).
Коды Хэмминга
Код Хэмминга с r проверочными битами имеет длину n = 2r − 1 и исправляет любую одиночную ошибку. Добавив общий бит чётности, получают расширенный код (SECDED): он исправляет одну ошибку и обнаруживает две. Такие коды используются в памяти ECC.
| Проверочных бит r | Длина кода n = 2r − 1 | Информационных бит k | Обозначение | Скорость k/n | Расширенный код (SECDED) |
|---|---|---|---|---|---|
| 2 | 3 | 1 | Хэмминг (3, 1) | 0,333 | (4, 1) |
| 3 | 7 | 4 | Хэмминг (7, 4) | 0,571 | (8, 4) |
| 4 | 15 | 11 | Хэмминг (15, 11) | 0,733 | (16, 11) |
| 5 | 31 | 26 | Хэмминг (31, 26) | 0,839 | (32, 26) |
| 6 | 63 | 57 | Хэмминг (63, 57) | 0,905 | (64, 57) |
| 7 | 127 | 120 | Хэмминг (127, 120) | 0,945 | (128, 120) |
| 8 | 255 | 247 | Хэмминг (255, 247) | 0,969 | (256, 247) |
Например, в серверной памяти ECC на каждые 64 бита данных добавляется 8 проверочных: укороченный код SECDED (72, 64). Закодировать и декодировать сообщение с внесением ошибки можно в калькуляторе кода Хэмминга, а число различающихся бит между двумя словами — в калькуляторе расстояния Хэмминга.
Комментарии и вопросы