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

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

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

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

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

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

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

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

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

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

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

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

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

Кожній послідовності бітів a_0, a_1, ..., a_{N-1} взаємно однозначно зіставляється двійковий многочлен \textstyle \sum_{n=0}^{N-1} \displaystyle a_nx^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\bmod\ 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 використовує CRC-32C з ціллю виявлення помилок в корисному навантаженні.

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

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

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

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

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

0x1 0x1 0x1
CRC-4-ITU x^4 + x + 1 ITU G.704 0x3 0xC 0x9
CRC-5-EPC x^5 + x^3 + 1 Gen 2 RFID 0x09 0x12 0x14
CRC-5-ITU x^5 + x^4 + x^2 + 1 ITU G.704 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 0x03 0x30 0x21
CRC-7 x^7 + x^3 + 1 системи телекомунікації, ITU-T G.707, ITU-T G.832, MMCSD 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 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 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, ModbusUSBANSI X3.28[20], багато інших;

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

0x8005 0xA001 0xC002
CRC-16-CCITT x^{16} + x^{12} + x^5 + 1 X.25HDLC, XMODEM, BluetoothSD та інші 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-2PNGPOSIX 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) в теперішній час витіснені.

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

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