КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Стандартизованные полиномы
|
|
|
|
Описание процедуры алгоритма вычисления 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; Просмотров: 975; Нарушение авторских прав?; Мы поможем в написании вашей работы!