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

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

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

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

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

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

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

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

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

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

При передачі пакетів по реальному каналу, зрозуміло, можуть виникнути спотворення вихідної інформації внаслідок різних зовнішніх впливів: електричних наводок, поганих погодних умов і багатьох інших. Сутність методики в тому, що при хороших характеристиках хеш-функції в переважній кількості випадків помилка в повідомленні призведе до зміни обчисленого на прийомі значення 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 використовує CRC-32C з ціллю виявлення помилок в корисному навантаженні.

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

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

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

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

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

0x1 0x1 0x1
CRC-4-ITU ITU G.704 0x3 0xC 0x9
CRC-5-EPC Gen 2 RFID 0x09 0x12 0x14
CRC-5-ITU ITU G.704 0x15 0x15 0x1A
CRC-5-USB USB token packets 0x05 0x14 0x12
CRC-6-ITU ITU G.704 0x03 0x30 0x21
CRC-7 системи телекомунікації, ITU-T G.707, ITU-T G.832, 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 0xD5 0xAB 0xEA
CRC-8-SAE J1850 0x1D 0xB8 0x8E
CRC-10 0x233 0x331 0x319
CRC-11 FlexRay 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 870, M-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) в теперішній час витіснені.

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

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