Циклічний надлишковий код

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Циклі́чний надлишко́вий код (англ. Cyclic redundancy check, CRC[1]) — алгоритм обчислення контрольної суми, призначений для перевірки цілісності даних. CRC є практичним додатком завадостійкого кодування, заснованому на певних математичних властивостях циклічного коду.

Введення[ред.ред. код]

Поняття циклічні коди достатньо широке. У англомовній літературі CRC розшифровується двояко в залежності від контексту: Cyclic Redundancy Code або Cyclic Redundancy Check. Під першою розшифровкою розуміють математичний феномен циклічних кодів, під другою — конкретне застосування цього феномену як геш-функції.

Завадостійке кодування[ред.ред. код]

Перші спроби створення кодів з надлишковою інформацією почалися задовго до появи сучасних ПК. До прикладу, ще в шістдесятих роках минулого століття Рідом і Соломоном була розроблена ефективна методика кодування — код Ріда-Соломона. Використання її у ті часи не представлялося можливим, так як провести операцію декодування за розумний час першими алгоритмами не вдавалося. Крапку в цьому питанні поставила фундаментальна робота Берлекампа, опублікована в 1968 році. Ця методика, на практичне застосування якої вказав через рік Мессі, і донині використовується в цифрових пристроях, що забезпечують приймання RS-кодованих даних. Більш того: дана система дозволяє не тільки визначати позиції, але й виправляти невірні кодові символи (найчастіше октети).

Але далеко не скрізь від коду потрібна корекція помилок. Сучасні канали зв'язку мають прийнятні характеристики, і часто достатньо лише перевірити, чи успішно пройшла передача або виникли будь-які складності; структура ж помилок і конкретні позиції невірних символів абсолютно не цікавлять сторону, яка приймає дані. І в цих умовах дуже вдалим рішенням виявилися алгоритми, що використовують контрольні суми. CRC як найкраще підходить для подібних задач: невисокі витрати ресурсів, простота реалізації і вже сформований математичний апарат з теорії лінійних циклічних кодів забезпечили їй величезну популярність.

Контрольна сума[ред.ред. код]

У найзагальнішому своєму вигляді контрольна сума являє собою деяке значення, побудоване за певною схемою на основі кодованого повідомлення. Перевірочна інформація при систематичному кодуванні дописується, найчастіше, на кінець повідомлення — після корисних даних. З приймального боку абонент знає алгоритм обчислення контрольної суми: відповідно, програма має можливість перевірити коректність прийнятих даних.

При передачі пакетів по реальному каналу, зрозуміло, можуть виникнути спотворення вихідної інформації внаслідок різних зовнішніх впливів: електричних наведень, поганих погодних умов і багатьох інших. Сутність методики в тому, що при хороших характеристиках хеш-функції[2]в переважній кількості випадків помилка в повідомленні призведе до зміни обчисленого на прийомі значення CRC. Якщо вихідна і обчислена суми не рівні між собою, ухвалюється рішення про недостовірність отриманих даних, і можна запитати повторну передачу пакета.

Математичний опис[ред.ред. код]

Алгоритм CRC базується на властивості ділення з остачею двійкових многочленів, тобто многочленів над скінченним полем . Значення CRC є по суті остачею від ділення многочлена, відповідного вхідним даним, на деякий фіксований породжувальний многочлен.

Кожній послідовності бітів взаємно однозначно зіставляється двійковий многочлен , послідовність коефіцієнтів якого являє собою початкову послідовність. Наприклад, послідовність бітів 1011010 відповідає многочлену:

Кількість різних многочленів степені меншої  дорівнює , що збігається з числом всіх двійкових послідовностей довжини . Значення контрольної суми в алгоритмі з породжуючим многочленом  степені  задається як бітова послідовність довжини , яка представляє многочлен , отриманий в остачі при діленні многочлена , який представляє вхідний потік біт, на многочлен :

де

 — многочлен, який представляє значення CRC;
— многочлен, коефіцієнти якого представляють вхідні дані;
 — породжувальний многочлен;
 — степінь породжувального многочлена.

Множення здійснюється приписуванням нульових бітів до вхідної послідовності, що покращує якість гешування для коротких вхідних послідовностей.

При діленні з остачею початкового многочлена на породжуючий многочлен  степені  можна отримати  різних остач від ділення.  найчастіше є незвідним многочленом. Зазвичай його підбирають відповідно до вимог до геш-функції у контексті кожного конкретного застосування. Проте, існує багато стандартизованих породжувальних многочленів, що володіють добрими математичними та кореляційними властивостями (мінімальне число колізій, простота обчислення), деякі з котрих приведені нижче.

Обчислення CRC[ред.ред. код]

Параметри алгоритму[ред.ред. код]

Одним з основних параметрів CRC є породжувальний многочлен.

З породжувальним многочленом пов'язаний інший параметр — його степінь, який визначає кількість бітів, застосованих для обчислення значення CRC. На практиці найбільш поширені 8-, 16- та 32-бітові слова, що є наслідком особливостей архітектури сучасної обчислювальної техніки.

Ще одним параметром є початкове (стартове) значення слова. Вказані параметри повністю визначають «традиційний» алгоритм обчислення CRC. Існують також модифікації алгоритму, наприклад, які використовують зворотний порядок обробки бітів.

Опис процедури[ред.ред. код]

З файлу береться перше слово — це може бути бітовий (CRC-1), байтовий (CRC-8) або будь-який інший елемент. Якщо старший біт у слові «1», то слово зсувається вліво на один розряд з подальшим виконанням операції XOR з породжувальним многочленом. Відповідно, якщо старший біт у слові «0», то після зсуву операція XOR не виконується. Після зсуву втрачається старий старший біт, а молодший біт звільняється — його значення встановлюється рівним нулю. На місце молодшого біту завантажується черговий біт із файлу, й операція повторюється до тих пір, поки не завантажиться останній біт файлу. Після проходження всього файлу, в слові залишається остача, яка і є контрольною сумою.

Популярні й стандартизовані многочлени[ред.ред. код]

В той час, як циклічні надлишкові коди є частиною стандартів, у цього терміну не існує загальноприйнятого визначення — трактування різних авторів нерідко суперечать один одному.

Цей парадокс стосується й вибору многочлена-генератора: найчастіше стандартизовані многочлени не є найбільш ефективними в плані статичних властивостей відповідного їм check redundancy code.

При цьому багато широко використовуваних многочленів не є найефективнішими із всіх можливих. У 1993—2004 роках група вчених займалася дослідженням породжувальних многочленів розрядності до 16, 24 та 36 біт й знайшла многочлени, які дають кращу, ніж стандартизовані многочлени, продуктивність у сенсі кодової відстані. Один із результатів цього дослідження вже знайшов своє застосування в протоколі iSCSI.

Найпопулярніший та рекомендований IEEE многочлен для CRC-32 використовується в Ethernet, FDDI; також цей многочлен є генератором коду Геммінга. Використання іншого многочлену — CRC-32C — дозволяє досягти такої ж продуктивності при довжині вихідного повідомлення від 58 біт до 131 кбіт, а в деяких діапазонах довжини вхідного повідомлення може бути навіть більше — цьому в наш час він також користується популярністю. Наприклад, стандарт ITU-T G.hn[3] використовує CRC-32C з ціллю виявлення помилок в корисному навантаженні.

Нижче в таблиці приведені найбільш розповсюджені многочлени — генератори CRC. На практиці обчислення CRC може включати пре- та пост-інверсію, а також зворотний порядок обробки бітів. У власницьких реалізаціях CRC для ускладнення аналізу коду використовують ненульові початкові значення регістрів.

Назва Многочлен Використання Представлення
Нормальне Реверсоване Реверсоване

від зворотнього

CRC-1 використовується в апаратному контролі помилок;

також відомий як біт парності

0x1 0x1 0x1
CRC-4-ITU ITU G.704

[4]

0x3 0xC 0x9
CRC-5-EPC Gen 2 RFID[5] 0x09 0x12 0x14
CRC-5-ITU ITU G.704[6] 0x15 0x15 0x1A
CRC-5-USB USB token packets 0x05 0x14 0x12
CRC-6-ITU ITU G.704[7] 0x03 0x30 0x21
CRC-7 системи телекомунікації, ITU-T G.707[8]ITU-T G.832[9]MMCSD 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[10] 0xD5 0xAB 0xEA
CRC-8-SAE J1850 0x1D 0xB8 0x8E
CRC-10 0x233 0x331 0x319
CRC-11 FlexRay[11] 0x385 0x50E 0x5C2
CRC-12 системи телекомунікації 0x80F 0xF01 0xC07
CRC-15-CAN 0x4599 0x4CD1 0x62CC
CRC-16-IBM Bisync, ModbusUSBANSI X3.28[20], багато інших;

також відомий як CRC-16 та CRC-16-ANSI

0x8005 0xA001 0xC002
CRC-16-CCITT X.25HDLC, XMODEM, BluetoothSD та інші 0x1021 0x8408 0x8810
CRC-16-T10-DIF SCSI DIF 0x8BB7 0xEDD1 0xC5DB
CRC-16-DNP DNP, IEC 870M-Bus 0x3D65 0xA6BC 0x9EB2
CRC-24 FlexRay 0x5D6DCB 0xD3B6BA 0xAEB6E5
CRC-24-Radix-64

OpenPGP 0x864CFB 0xDF3261 0xC3267D
CRC-30

CDMA 0x2030B9C7 0x38E74301 0x30185CE3
CRC-32-IEEE 802.3

V.42, MPEG-2PNGPOSIX cksum 0x04C11DB7 0xEDB88320 0x82608EDB
CRC-32C (Castagnoli)

iSCSI, G.hn payload 0x1EDC6F41 0x82F63B78 0x8F6E37A0
CRC-32K (Koopman)

0x741B8CD7 0xEB31D82E 0xBA0DC66B
CRC-32Q авіація; AIXM 0x814141AB 0xD5828281 0xC0A0A0D5
CRC-64-ISO HDLC — ISO 3309 0x000000000000001B 0xD800000000000000 0x800000000000000D
CRC-64-ECMA

0x42F0E1EBA9EA3693 0xC96C5795D7870F42 0xA17870F5D4F51B49

Наявні стандарти CRC-128 (IEEE) та CRC-256 (IEEE) в теперішній час витіснені.

Специфікації алгоритмів CRC[ред.ред. код]

Однією з найвідоміших є методика Ross N. Williams[12]. У ній використовуються наступні параметри:

  • Назва алгоритму (name);
  • Ступінь породжує контрольну суму многочлена (width);
  • Сам виготовляючий поліном (poly). Для того, щоб записати його у вигляді значення, його спочатку записують як бітову послідовність, при цьому старший біт опускається - він завжди дорівнює 1. Наприклад, многочлен в даній нотації буде записаний числом. Для зручності отримане двійкове подання записують в шістнадцятковій формі. Для нашого випадку воно буде дорівнює або 0x11;
  • Стартові дані (init), тобто значення регістрів на момент початку обчислень;
  • Прапор (RefIn), який вказує на початок і напрямок обчислень. Існує два варіанти: False - починаючи зі старшого значущого біта (MSB-first),[13] або True - з молодшого (LSB-first);[14]
  • Прапор (RefOut), що визначає, інвертується чи порядок бітів регістра при вході на елемент XOR;
  • Число (XorOut), з яким складається по модулю 2 отриманий результат;
  • Значення CRC (check) для рядка «123456789».

Приклади[15][ред.ред. код]

Name Width Poly Init RefIn RefOut XorOut Check
CRC-3/ROHC 3 0x3 0x7 true true 0x0 0x6
CRC-4/ITU 4 0x3 0x0 true true 0x0 0x7
CRC-5/EPC 5 0x9 0x9 false false 0x0 0x0
CRC-5/ITU 5 0x15 0x0 true true 0x0 0x7
CRC-5/USB 5 0x5 0x1F true true 0x1F 0x19
CRC-6/CDMA2000-A 6 0x27 0x3F false false 0x0 0xD
CRC-6/CDMA2000-B 6 0x7 0x3F false false 0x0 0x3B
CRC-6/DARC 6 0x19 0x0 true true 0x0 0x26
CRC-6/ITU 6 0x3 0x0 true true 0x0 0x6
CRC-7 7 0x9 0x0 false false 0x0 0x75
CRC-7/ROHC 7 0x4F 0x7F true true 0x0 0x53
CRC-8 8 0x7 0x0 false false 0x0 0xF4
CRC-8/CDMA2000 8 0x9B 0xFF false false 0x0 0xDA
CRC-8/DARC 8 0x39 0x0 true true 0x0 0x15
CRC-8/DVB-S2 8 0xD5 0x0 false false 0x0 0xBC
CRC-8/EBU 8 0x1D 0xFF true true 0x0 0x97
CRC-8/I-CODE 8 0x1D 0xFD false false 0x0 0x7E
CRC-8/ITU 8 0x7 0x0 false false 0x55 0xA1
CRC-8/MAXIM 8 0x31 0x0 true true 0x0 0xA1
CRC-8/ROHC 8 0x7 0xFF true true 0x0 0xD0
CRC-8/WCDMA 8 0x9B 0x0 true true 0x0 0x25
CRC-10 10 0x233 0x0 false false 0x0 0x199
CRC-10/CDMA2000 10 0x3D9 0x3FF false false 0x0 0x233
CRC-11 11 0x385 0x1A false false 0x0 0x5A3
CRC-12/3GPP 12 0x80F 0x0 false true 0x0 0xDAF
CRC-12/CDMA2000 12 0xF13 0xFFF false false 0x0 0xD4D
CRC-12/DECT 12 0x80F 0x0 false false 0x0 0xF5B
CRC-13/BBC 13 0x1CF5 0x0 false false 0x0 0x4FA
CRC-14/DARC 14 0x805 0x0 true true 0x0 0x82D
CRC-15 15 0x4599 0x0 false false 0x0 0x59E
CRC-15/MPT1327 15 0x6815 0x0 false false 0x1 0x2566
CRC-16/ARC 16 0x8005 0x0 true true 0x0 0xBB3D
CRC-16/AUG-CCITT 16 0x1021 0x1D0F false false 0x0 0xE5CC
CRC-16/BUYPASS 16 0x8005 0x0 false false 0x0 0xFEE8
CRC-16/CCITT-FALSE 16 0x1021 0xFFFF false false 0x0 0x29B1
CRC-16/CDMA2000 16 0xC867 0xFFFF false false 0x0 0x4C06
CRC-16/DDS-110 16 0x8005 0x800D false false 0x0 0x9ECF
CRC-16/DECT-R 16 0x589 0x0 false false 0x1 0x7E
CRC-16/DECT-X 16 0x589 0x0 false false 0x0 0x7F
CRC-16/DNP 16 0x3D65 0x0 true true 0xFFFF 0xEA82
CRC-16/EN-13757 16 0x3D65 0x0 false false 0xFFFF 0xC2B7
CRC-16/GENIBUS 16 0x1021 0xFFFF false false 0xFFFF 0xD64E
CRC-16/MAXIM 16 0x8005 0x0 true true 0xFFFF 0x44C2
CRC-16/MCRF4XX 16 0x1021 0xFFFF true true 0x0 0x6F91
CRC-16/RIELLO 16 0x1021 0xB2AA true true 0x0 0x63D0
CRC-16/T10-DIF 16 0x8BB7 0x0 false false 0x0 0xD0DB
CRC-16/TELEDISK 16 0xA097 0x0 false false 0x0 0xFB3
CRC-16/TMS37157 16 0x1021 0x89EC true true 0x0 0x26B1
CRC-16/USB 16 0x8005 0xFFFF true true 0xFFFF 0xB4C8
CRC-A 16 0x1021 0xC6C6 true true 0x0 0xBF05
CRC-16/KERMIT 16 0x1021 0x0 true true 0x0 0x2189
CRC-16/MODBUS 16 0x8005 0xFFFF true true 0x0 0x4B37
CRC-16/X-25 16 0x1021 0xFFFF true true 0xFFFF 0x906E
CRC-16/XMODEM 16 0x1021 0x0 false false 0x0 0x31C3
CRC-24 24 0x864CFB 0xB704CE false false 0x0 0x21CF02
CRC-24/FLEXRAY-A 24 0x5D6DCB 0xFEDCBA false false 0x0 0x7979BD
CRC-24/FLEXRAY-B 24 0x5D6DCB 0xABCDEF false false 0x0 0x1F23B8
CRC-31/PHILIPS 31 0x4C11DB7 0x7FFFFFFF false false 0x7FFFFFFF 0xCE9E46C
CRC-32/zlib 32 0x4C11DB7 0xFFFFFFFF true true 0xFFFFFFFF 0xCBF43926
CRC-32/BZIP2 32 0x4C11DB7 0xFFFFFFFF false false 0xFFFFFFFF 0xFC891918
CRC-32C 32 0x1EDC6F41 0xFFFFFFFF true true 0xFFFFFFFF 0xE3069283
CRC-32D 32 0xA833982B 0xFFFFFFFF true true 0xFFFFFFFF 0x87315576
CRC-32/MPEG-2 32 0x4C11DB7 0xFFFFFFFF false false 0x0 0x376E6E7
CRC-32/POSIX 32 0x4C11DB7 0x0 false false 0xFFFFFFFF 0x765E7680
CRC-32Q 32 0x814141AB 0x0 false false 0x0 0x3010BF7F
CRC-32/JAMCRC 32 0x4C11DB7 0xFFFFFFFF true true 0x0 0x340BC6D9
CRC-32/XFER 32 0xAF 0x0 false false 0x0 0xBD0BE338
CRC-40/GSM 40 0x4820009 0x0 false false 0xFFFFFFFFFF 0xD4164FC646
CRC-64 64 0x42F0E1EBA9EA3693 0x0 false false 0x0 0x6C40DF5F0B497347
CRC-64/WE 64 0x42F0E1EBA9EA3693 0xFFFFFFFFFFFFFFFF false false 0xFFFFFFFFFFFFFFFF 0x62EC59E3F1A4F00A
CRC-64/XZ 64 0x42F0E1EBA9EA3693 0xFFFFFFFFFFFFFFFF true true 0xFFFFFFFFFFFFFFFF 0x995DC9BBDF1939FA

Примітки[ред.ред. код]

Див. також[ред.ред. код]

Посилання[ред.ред. код]