Стандартизованные полиномы

Описание процедуры алгоритма вычисления CRC.

Вычисление CRC. Параметры алгоритма.

Одним из основных параметров CRC является порождающий полином.

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

техники.

Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие обратный порядок обработки битов.

Из файла берётся первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу.

Этот парадокс касается и выбора многочлена – генератора: При этом многие широко используемые стандартизованные полиномы не являются наиболее эффективными из всех возможных.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI, а также этот многочлен является генератором кода Хемминга. Использование другого полинома CRC-32C позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью.

К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке. В таблице 2 перечислены наиболее часто используемые полиномы — генераторы CRC. На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В некоторых реализациях CRC с целью усложнения анализа кода используют некоторые ненулевые начальные значения регистров.

Таблица 2. Стандартизованные полиномы.

Название	Полином	Представления: нормальное / реверсированное / реверсированное от обратного
CRC-1	(используется в аппаратном контроле ошибок; также известен как бит чётности)	0x1 / 0x1 / 0x1
CRC-4-ITU	(ITU G.704)	0x3 / 0xC / 0x9
CRC-5-EPC	(Gen 2 RFID)	0x09 / 0x12 / 0x14
CRC-5-ITU	(ITU G.704)	0x15 / 0x15 / 0x1A
CRC-5-USB	(USB token packets)	0x05 / 0x14 / 0x12
CRC-6-ITU	(ITU G.704)	0x03 / 0x30 / 0x21
CRC-7	(системы телекоммуникации, ITU-T G.707, ITU-T G.832, MMC, SD)	0x09 / 0x48 / 0x44
CRC-8-CCITT	(ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim	(1-Wire bus)	0x31 / 0x8C / 0x98
CRC-8	(ETSI EN 302 307, 5.1.4)	0xD5 / 0xAB / 0xEA^[1]
CRC-8-SAE J1850		0x1D / 0xB8 / 0x8E
CRC-10		0x233 / 0x331 / 0x319
CRC-11	(FlexRay)	0x385 / 0x50E / 0x5C2
CRC-12	(системы телекоммуникации)	0x80F / 0xF01 / 0xC07
CRC-15-CAN		0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM	(Bisync, Modbus, USB, ANSI X3.28^[20], многие другие; также известен как CRC-16 и CRC-16-ANSI)	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	(X.25, HDLC, XMODEM, Bluetooth, SD и др.)	0x1021 / 0x8408 / 0x8810^[1]
CRC-16-T10-DIF	(SCSI DIF)	0x8BB7 / 0xEDD1 / 0xC5DB
CRC-16-DNP	(DNP, IEC 870, M-Bus)	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher	Не CRC; см. Fletcher’s checksum	Используется в Adler-32 A & B CRC
CRC-24	(FlexRay)	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64	(OpenPGP)	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	(CDMA)	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler	Не CRC; Adler-32	Adler-32
CRC-32-IEEE 802.3	(V.42, MPEG-2, PNG^[22], POSIX cksum)	0x04C11DB7 / 0xEDB88320 / 0x82608EDB
CRC-32C (Castagnoli)	(iSCSI, G.hn payload)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0
CRC-32K (Koopman)		0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B
CRC-32Q	(aviation; AIXM)	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	(HDLC — ISO 3309)	0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA		0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

Дата добавления: 2015-08-31