Циклі́чний надлишко́вий код (англ. 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, 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 | 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, 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 | 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. У ній використовуються наступні параметри:
- Назва алгоритму (name);
- Ступінь породжує контрольну суму многочлена (width);
- Сам виготовляючий поліном (poly). Для того, щоб записати його у вигляді значення, його спочатку записують як бітову послідовність, при цьому старший біт опускається — він завжди дорівнює 1. Наприклад, многочлен в даній нотації буде записаний числом. Для зручності отримане двійкове подання записують в шістнадцятковій формі. Для нашого випадку воно буде дорівнює або 0x11;
- Стартові дані (init), тобто значення регістрів на момент початку обчислень;
- Прапор (RefIn), який вказує на початок і напрямок обчислень. Існує два варіанти: False — починаючи зі старшого значущого біта (MSB-first), або True — з молодшого (LSB-first);
- Прапор (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 |
Примітки
- What is cyclic redundancy checking? - Definition from WhatIs.com. SearchNetworking (амер.).
- Лекція 17 - Криптографічні ХЕШ-функції | Кафедра безпеки інформації та телекомунікацій. bit.nmu.org.ua.
- ITU-T (англ.). 2010.
- tsbmail. G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels P.7. www.itu.int.
- GEN 2 RFID. с. 35.
- tsbmail. G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels P.9. www.itu.int.
- tsbmail. G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels p.3. www.itu.int.
- tsbmail. G.707 : Network node interface for the synchronous digital hierarchy (SDH) P. 7. www.itu.int.
- tsbmail. G.832 : Transport of SDH elements on PDH networks - Frame and multiplexing structures. www.itu.int.
- Final draft ETSI EN 302 307 V1.2.1 (EN) . ETSI. 2009.
- FlexRay Automotive Communication Bus Overview - National Instruments. www.ni.com.
- . http://embedded.ifmo.ru. Архів оригіналу за 20 листопада 2016.
- ShiftOut Программирование Ардуино. arduino.ua.
- Catalogue of parametrised CRC algorithms. reveng.sourceforge.net.
Див. також
Посилання
![]() | Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет