Циклі́чний надлишко́вий код (англ. Cyclic redundancy check, CRC[1]) — алгоритм обчислення контрольної суми, призначений для перевірки цілісності даних. CRC є практичним додатком завадостійкого кодування, заснованому на певних математичних властивостях циклічного коду.
Введення
Поняття циклічні коди достатньо широке. У англомовній літературі CRC розшифровується двояко в залежності від контексту: Cyclic Redundancy Code або Cyclic Redundancy Check. Під першою розшифровкою розуміють математичний феномен циклічних кодів, під другою — конкретне застосування цього феномену як геш-функції.
Завадостійке кодування
Перші спроби створення кодів з надлишковою інформацією почалися задовго до появи сучасних ПК. До прикладу, ще в шістдесятих роках минулого століття Рідом і Соломоном була розроблена ефективна методика кодування — код Ріда-Соломона. Використання її у ті часи не представлялося можливим, так як провести операцію декодування за розумний час першими алгоритмами не вдавалося. Крапку в цьому питанні поставила фундаментальна робота Берлекампа, опублікована в 1968 році. Ця методика, на практичне застосування якої вказав через рік Мессі, і донині використовується в цифрових пристроях, що забезпечують приймання RS-кодованих даних. Більш того: дана система дозволяє не тільки визначати позиції, але й виправляти невірні кодові символи (найчастіше октети).
Але далеко не скрізь від коду потрібна корекція помилок. Сучасні канали зв'язку мають прийнятні характеристики, і часто достатньо лише перевірити, чи успішно пройшла передача або виникли будь-які складності; структура ж помилок і конкретні позиції невірних символів абсолютно не цікавлять сторону, яка приймає дані. І в цих умовах дуже вдалим рішенням виявилися алгоритми, що використовують контрольні суми. CRC як найкраще підходить для подібних задач: невисокі витрати ресурсів, простота реалізації і вже сформований математичний апарат з теорії лінійних циклічних кодів забезпечили їй величезну популярність.
Контрольна сума
У найзагальнішому своєму вигляді контрольна сума являє собою деяке значення, побудоване за певною схемою на основі кодованого повідомлення. Перевірочна інформація при систематичному кодуванні дописується, найчастіше, на кінець повідомлення — після корисних даних. З приймального боку абонент знає алгоритм обчислення контрольної суми: відповідно, програма має можливість перевірити коректність прийнятих даних.
При передачі пакетів по реальному каналу, зрозуміло, можуть виникнути спотворення вихідної інформації внаслідок різних зовнішніх впливів: електричних наведень, поганих погодних умов і багатьох інших. Сутність методики в тому, що при хороших характеристиках хеш-функції[2]в переважній кількості випадків помилка в повідомленні призведе до зміни обчисленого на прийомі значення CRC. Якщо вихідна і обчислена суми не рівні між собою, ухвалюється рішення про недостовірність отриманих даних, і можна запитати повторну передачу пакета.
Математичний опис
Алгоритм CRC базується на властивості ділення з остачею двійкових многочленів, тобто многочленів над скінченним полем
. Значення CRC є по суті остачею від ділення многочлена, відповідного вхідним даним, на деякий фіксований породжувальний многочлен.
Кожній послідовності бітів
взаємно однозначно зіставляється двійковий многочлен
, послідовність коефіцієнтів якого являє собою початкову послідовність. Наприклад, послідовність бітів 1011010 відповідає многочлену:
![{\displaystyle P(x)=1\cdot x^{6}+0\cdot x^{5}+1\cdot x^{4}+1\cdot x^{3}+0\cdot x^{2}+1\cdot x^{1}+0\cdot x^{0}=x^{6}+x^{4}+x^{3}+x^{1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75ced698ec6589f5573cd4586ae77204e365aa9a)
Кількість різних многочленів степені меншої
дорівнює
, що збігається з числом всіх двійкових послідовностей довжини
.
Значення контрольної суми в алгоритмі з породжуючим многочленом
степені
задається як бітова послідовність довжини
, яка представляє многочлен
, отриманий в остачі при діленні многочлена
, який представляє вхідний потік біт, на многочлен
:
![{\displaystyle R(x)=P(x)\cdot x^{N}{\bmod {\ }}G(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5135780b9a302056aa70caf255285c6dd79e1ccf)
де
— многочлен, який представляє значення 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], 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[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, 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
|
CRC-16-T10-DIF
|
|
SCSI DIF
|
0x8BB7
|
0xEDD1
|
0xC5DB
|
CRC-16-DNP
|
|
DNP, IEC 870, M-Bus
|
0x3D65
|
0xA6BC
|
0x9EB2
|
CRC-24
|
![{\displaystyle x^{24}+x^{22}+x^{20}+x^{19}+x^{18}+x^{16}+x^{14}+x^{13}+x^{11}+x^{10}+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39b7c8ba40b9c9d4b4edf7dc956ef71d7fb5acc5)
|
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-2, PNG, POSIX 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]. У ній використовуються наступні параметри:
- Ступінь породжує контрольну суму многочлена (width);
- Сам виготовляючий поліном (poly). Для того, щоб записати його у вигляді значення, його спочатку записують як бітову послідовність, при цьому старший біт опускається — він завжди дорівнює 1. Наприклад, многочлен в даній нотації буде записаний числом. Для зручності отримане двійкове подання записують в шістнадцятковій формі. Для нашого випадку воно буде дорівнює або 0x11;
- Стартові дані (init), тобто значення регістрів на момент початку обчислень;
- Прапор (RefOut), що визначає, інвертується чи порядок бітів регістра при вході на елемент XOR;
- Число (XorOut), з яким складається по модулю 2 отриманий результат;
- Значення CRC (check) для рядка «123456789».
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
|
Примітки
Див. також
Посилання