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

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

Введення

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

Завадостійке кодування

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

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

Контрольна сума

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

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

Математичний опис

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

Кожній послідовності бітів

a_{0}, a_{1}, . . ., a_{N - 1}

взаємно однозначно зіставляється двійковий многочлен

\sum_{n = 0}^{N - 1} a_{n} x^{n}

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

$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} .$

Кількість різних многочленів степені меншої

N

дорівнює

2^{N}

, що збігається з числом всіх двійкових послідовностей довжини

N

. Значення контрольної суми в алгоритмі з породжуючим многочленом

G (x)

степені

N

задається як бітова послідовність довжини

N

, яка представляє многочлен

R (x)

, отриманий в остачі при діленні многочлена

P (x)

, який представляє вхідний потік біт, на многочлен

G (x)

:

$R (x) = P (x) \cdot x^{N} mod G (x)$

де

R (x)

— многочлен, який представляє значення CRC;

P (x)

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

G (x)

— породжувальний многочлен;

N

— степінь породжувального многочлена.

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

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

Обчислення 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	$x + 1$	використовується в апаратному контролі помилок; також відомий як біт парності	0x1	0x1	0x1
CRC-4-ITU	$x^{4} + x + 1$	ITU G.704 ^[4]	0x3	0xC	0x9
CRC-5-EPC	$x^{5} + x^{3} + 1$	Gen 2 RFID^[5]	0x09	0x12	0x14
CRC-5-ITU	$x^{5} + x^{4} + x^{2} + 1$	ITU G.704^[6]	0x15	0x15	0x1A
CRC-5-USB	$x^{5} + x^{2} + 1$	USB token packets	0x05	0x14	0x12
CRC-6-ITU	$x^{6} + x + 1$	ITU G.704^[7]	0x03	0x30	0x21
CRC-7	$x^{7} + x^{3} + 1$	системи телекомунікації, ITU-T G.707^[8], ITU-T G.832^[9], MMC, SD	0x09	0x48	0x44
CRC-8-CCITT	$x^{8} + x^{2} + x + 1$	ATM HEC, ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07	0xE0	0x83
CRC-8-Dallas/Maxim	$x^{8} + x^{5} + x^{4} + 1$	1-Wire bus	0x31	0x8C	0x98
CRC-8	$x^{8} + x^{7} + x^{6} + x^{4} + x^{2} + 1$	ETSI EN 302 307, 5.1.4^[10]	0xD5	0xAB	0xEA
CRC-8-SAE J1850	$x^{8} + x^{4} + x^{3} + x^{2} + 1$		0x1D	0xB8	0x8E
CRC-10	$x^{10} + x^{9} + x^{5} + x^{4} + x + 1$		0x233	0x331	0x319
CRC-11	$x^{11} + x^{9} + x^{8} + x^{7} + x^{2} + 1$	FlexRay^[11]	0x385	0x50E	0x5C2
CRC-12	$x^{12} + x^{11} + x^{3} + x^{2} + x + 1$	системи телекомунікації	0x80F	0xF01	0xC07
CRC-15-CAN	$x^{15} + x^{14} + x^{10} + x^{8} + x^{7} + x^{4} + x^{3} + 1$		0x4599	0x4CD1	0x62CC
CRC-16-IBM	$x^{16} + x^{15} + x^{2} + 1$	Bisync, Modbus, USB, ANSI X3.28^[20], багато інших; також відомий як CRC-16 та CRC-16-ANSI	0x8005	0xA001	0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^{5} + 1$	X.25, HDLC, XMODEM, Bluetooth, SD та інші	0x1021	0x8408	0x8810
CRC-16-T10-DIF	$x^{16} + x^{15} + x^{11} + x^{9} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1$	SCSI DIF	0x8BB7	0xEDD1	0xC5DB
CRC-16-DNP	$x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^{8} + x^{6} + x^{5} + x^{2} + 1$	DNP, IEC 870, M-Bus	0x3D65	0xA6BC	0x9EB2
CRC-24	$x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{11} + x^{10} +$ $x^{8} + x^{7} + x^{6} + x^{3} + x + 1$	FlexRay	0x5D6DCB	0xD3B6BA	0xAEB6E5
CRC-24-Radix-64	$x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^{7} + x^{6} +$ $x^{5} + x^{4} + x^{3} + x + 1$	OpenPGP	0x864CFB	0xDF3261	0xC3267D
CRC-30	$x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} +$ $x^{6} + x^{2} + x + 1$	CDMA	0x2030B9C7	0x38E74301	0x30185CE3
CRC-32-IEEE 802.3	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7} +$ $x^{5} + x^{4} + x^{2} + x + 1$	V.42, MPEG-2, PNG, POSIX cksum	0x04C11DB7	0xEDB88320	0x82608EDB
CRC-32C (Castagnoli)	$x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} +$ $x^{14} + x^{13} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + 1$	iSCSI, G.hn payload	0x1EDC6F41	0x82F63B78	0x8F6E37A0
CRC-32K (Koopman)	$x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} +$ $x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1$		0x741B8CD7	0xEB31D82E	0xBA0DC66B
CRC-32Q	$x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^{5} + x^{3} + x + 1$	авіація; AIXM	0x814141AB	0xD5828281	0xC0A0A0D5
CRC-64-ISO	$x^{64} + x^{4} + x^{3} + x + 1$	HDLC — ISO 3309	0x000000000000001B	0xD800000000000000	0x800000000000000D
CRC-64-ECMA	$x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} +$ $x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} +$ $x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^{9} + x^{7} + x^{4} + x + 1$		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);^[13]

Прапор (RefOut), що визначає, інвертується чи порядок бітів регістра при вході на елемент XOR;

Число (XorOut), з яким складається по модулю 2 отриманий результат;

Значення CRC (check) для рядка «123456789».

Приклади^[14]

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

Примітки

Шаблон:Reflist

Див. також

Хешування

Посилання

Електронні системи: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. — Вінниця: ВНТУ, 2011. — 208 с.

Шаблон:Геш-функції та коди аутентифікації повідомлення Шаблон:Програмування-доробити

[1] Шаблон:Cite news

[2] Шаблон:Cite web

[3] Шаблон:Cite book

[4] Шаблон:Cite web

[5] Шаблон:Cite book

[6] Шаблон:Cite web

[7] Шаблон:Cite web

[8] Шаблон:Cite web

[9] Шаблон:Cite web

[10] Шаблон:Cite book

[11] Шаблон:Cite web

[12] Шаблон:Cite web

[:0-13] 13,0 ^13,1 Шаблон:Cite web

[14] Шаблон:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

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

Зміст

Введення

Завадостійке кодування

Контрольна сума

Математичний опис

Обчислення CRC

Параметри алгоритму

Опис процедури

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

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

Приклади^[14]

Примітки

Див. також

Посилання

Навігаційне меню

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

Введення

Завадостійке кодування

Контрольна сума

Математичний опис

Обчислення CRC

Параметри алгоритму

Опис процедури

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

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

Приклади[14]

Примітки

Див. також

Посилання

Навігаційне меню

Пошук

Приклади^[14]