Циклі́чний надлишко́вий код (, 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використовується в апаратному контролі помилок; також відомий як біт парності0x10x10x1CRC-4-ITUITU G.7040x30xC0x9CRC-5-EPCGen 2 RFID0x090x120x14CRC-5-ITUITU G.7040x150x150x1ACRC-5-USBUSB token packets0x050x140x12CRC-6-ITUITU G.7040x030x300x21CRC-7системи телекомунікації, ITU-T G.707, ITU-T G.832, MMC, SD0x090x480x44CRC-8-CCITTATM HEC, ISDN Header Error Control  and Cell Delineation ITU-T I.432.1 (02/99)0x070xE00x83CRC-8-Dallas/Maxim1-Wire bus0x310x8C0x98CRC-8ETSI EN 302 307, 5.1.40xD50xAB0xEACRC-8-SAE J18500x1D0xB80x8ECRC-100x2330x3310x319CRC-11FlexRay0x3850x50E0x5C2CRC-12системи телекомунікації0x80F0xF010xC07CRC-15-CAN0x45990x4CD10x62CCCRC-16-IBMBisync, Modbus, USB, ANSI X3.28, багато інших; також відомий як CRC-16 та CRC-16-ANSI0x80050xA0010xC002CRC-16-CCITTX.25, HDLC, XMODEM, Bluetooth, SD та інші0x10210x84080x8810CRC-16-T10-DIFSCSI DIF0x8BB70xEDD10xC5DBCRC-16-DNPDNP, IEC 870, M-Bus0x3D650xA6BC0x9EB2CRC-24FlexRay0x5D6DCB0xD3B6BA0xAEB6E5CRC-24-Radix-64OpenPGP0x864CFB0xDF32610xC3267DCRC-30CDMA0x2030B9C70x38E743010x30185CE3CRC-32-IEEE 802.3V.42, MPEG-2, PNG, POSIX cksum0x04C11DB70xEDB883200x82608EDBCRC-32C (Castagnoli)iSCSI, G.hn payload0x1EDC6F410x82F63B780x8F6E37A0CRC-32K (Koopman)0x741B8CD70xEB31D82E0xBA0DC66BCRC-32Qавіація; AIXM0x814141AB0xD58282810xC0A0A0D5CRC-64-ISOHDLC — ISO 33090x000000000000001B0xD8000000000000000x800000000000000DCRC-64-ECMA0x42F0E1EBA9EA36930xC96C5795D7870F420xA17870F5D4F51B49 Наявні стандарти 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».

Приклади