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

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

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

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

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

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

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

Кожній послідовності бітів ${\displaystyle a_{0},a_{1},...,a_{N-1}}$ взаємно однозначно зіставляється двійковий многочлен ${\displaystyle \textstyle \sum _{n=0}^{N-1}\displaystyle a_{n}x^{n}}$, послідовність коефіцієнтів якого являє собою початкову послідовність. Наприклад, послідовність бітів 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}.}$

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

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

де

${\displaystyle R(x)}$ — многочлен, який представляє значення CRC;

${\displaystyle P(x)}$— многочлен, коефіцієнти якого представляють вхідні дані;

${\displaystyle G(x)}$ — породжувальний многочлен;

${\displaystyle N}$ — степінь породжувального многочлена.

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

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

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

Цей парадокс стосується й вибору многочлена-генератора: найчастіше стандартизовані многочлени не є найбільш ефективними в плані статичних властивостей відповідного їм 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	${\displaystyle x+1}$	використовується в апаратному контролі помилок; також відомий як біт парності	0x1	0x1	0x1
CRC-4-ITU	${\displaystyle x^{4}+x+1}$	ITU G.704 [4]	0x3	0xC	0x9
CRC-5-EPC	${\displaystyle x^{5}+x^{3}+1}$	Gen 2 RFID[5]	0x09	0x12	0x14
CRC-5-ITU	${\displaystyle x^{5}+x^{4}+x^{2}+1}$	ITU G.704[6]	0x15	0x15	0x1A
CRC-5-USB	${\displaystyle x^{5}+x^{2}+1}$	USB token packets	0x05	0x14	0x12
CRC-6-ITU	${\displaystyle x^{6}+x+1}$	ITU G.704[7]	0x03	0x30	0x21
CRC-7	${\displaystyle x^{7}+x^{3}+1}$	системи телекомунікації, ITU-T G.707[8], ITU-T G.832[9], MMC, SD	0x09	0x48	0x44
CRC-8-CCITT	${\displaystyle 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	${\displaystyle x^{8}+x^{5}+x^{4}+1}$	1-Wire bus	0x31	0x8C	0x98
CRC-8	${\displaystyle 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	${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$		0x1D	0xB8	0x8E
CRC-10	${\displaystyle x^{10}+x^{9}+x^{5}+x^{4}+x+1}$		0x233	0x331	0x319
CRC-11	${\displaystyle x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1}$	FlexRay[11]	0x385	0x50E	0x5C2
CRC-12	${\displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$	системи телекомунікації	0x80F	0xF01	0xC07
CRC-15-CAN	${\displaystyle x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1}$		0x4599	0x4CD1	0x62CC
CRC-16-IBM	${\displaystyle 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	${\displaystyle x^{16}+x^{12}+x^{5}+1}$	X.25, HDLC, XMODEM, Bluetooth, SD та інші	0x1021	0x8408	0x8810
CRC-16-T10-DIF	${\displaystyle 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	${\displaystyle 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	${\displaystyle x^{24}+x^{22}+x^{20}+x^{19}+x^{18}+x^{16}+x^{14}+x^{13}+x^{11}+x^{10}+}$${\displaystyle x^{8}+x^{7}+x^{6}+x^{3}+x+1}$	FlexRay	0x5D6DCB	0xD3B6BA	0xAEB6E5
CRC-24-Radix-64	${\displaystyle x^{24}+x^{23}+x^{18}+x^{17}+x^{14}+x^{11}+x^{10}+x^{7}+x^{6}+}$ ${\displaystyle x^{5}+x^{4}+x^{3}+x+1}$	OpenPGP	0x864CFB	0xDF3261	0xC3267D
CRC-30	${\displaystyle x^{30}+x^{29}+x^{21}+x^{20}+x^{15}+x^{13}+x^{12}+x^{11}+x^{8}+x^{7}+}$ ${\displaystyle x^{6}+x^{2}+x+1}$	CDMA	0x2030B9C7	0x38E74301	0x30185CE3
CRC-32-IEEE 802.3	${\displaystyle x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+}$ ${\displaystyle x^{5}+x^{4}+x^{2}+x+1}$	V.42, MPEG-2, PNG, POSIX cksum	0x04C11DB7	0xEDB88320	0x82608EDB
CRC-32C (Castagnoli)	${\displaystyle x^{32}+x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+}$ ${\displaystyle 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)	${\displaystyle x^{32}+x^{30}+x^{29}+x^{28}+x^{26}+x^{20}+x^{19}+x^{17}+x^{16}+x^{15}+}$ ${\displaystyle x^{11}+x^{10}+x^{7}+x^{6}+x^{4}+x^{2}+x+1}$		0x741B8CD7	0xEB31D82E	0xBA0DC66B
CRC-32Q	${\displaystyle 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	${\displaystyle x^{64}+x^{4}+x^{3}+x+1}$	HDLC — ISO 3309	0x000000000000001B	0xD800000000000000	0x800000000000000D
CRC-64-ECMA	${\displaystyle x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+}$ ${\displaystyle x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+x^{32}+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+}$ ${\displaystyle 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) в теперішній час витіснені криптографічними геш-функціями.

Однією з найвідоміших є методика 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».

• Хешування

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