Перегляд вихідного коду сторінки Циклічний надлишковий код

'''Циклі́чний надлишко́вий код''' ({{lang-en|Cyclic redundancy check}}, CRC<ref>{{Cite news|url=http://searchnetworking.techtarget.com/definition/cyclic-redundancy-checking|title=What is cyclic redundancy checking? - Definition from WhatIs.com|last=|first=|date=|language=en-US|work=SearchNetworking|accessdate=}}</ref>)&nbsp;— алгоритм обчислення [[Контрольна сума|контрольної суми]], призначений для [[Виявлення і виправлення помилок|перевірки цілісності даних]]. CRC є практичним додатком завадостійкого [[кодування]], заснованому на певних математичних властивостях [[Циклічний код|циклічного коду]].

== Введення ==
Поняття [[Циклічний код|циклічні коди]] достатньо широке. У англомовній літературі CRC розшифровується двояко в залежності від контексту: ''Cyclic Redundancy Code''&nbsp;або ''Cyclic Redundancy Check.'' Під першою розшифровкою розуміють математичний феномен циклічних кодів, під другою&nbsp;— конкретне застосування цього феномену як [[Геш-функція|геш-функції]].

== Завадостійке кодування ==

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

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

== Контрольна сума ==

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

При передачі пакетів по реальному каналу, зрозуміло, можуть виникнути спотворення вихідної інформації внаслідок різних зовнішніх впливів: електричних наведень, поганих погодних умов і багатьох інших. Сутність методики в тому, що при хороших характеристиках хеш-функції<ref>{{Cite web|url=http://bit.nmu.org.ua/ua/student/metod/cryptology/lecture17.php|title=Лекція 17 - Криптографічні ХЕШ-функції  {{!}} Кафедра безпеки інформації та телекомунікацій|last=|first=|date=|website=bit.nmu.org.ua|publisher=|language=|accessdate=}}</ref>в переважній кількості випадків помилка в повідомленні призведе до зміни обчисленого на прийомі значення CRC. Якщо вихідна і обчислена суми не рівні між собою, ухвалюється рішення про недостовірність отриманих даних, і можна запитати повторну передачу пакета.

== Математичний опис ==
Алгоритм CRC базується на властивості [[ділення з остачею]] двійкових [[Многочлен|многочленів]], тобто многочленів над [[Скінченне поле|скінченним полем]] <math>GF(2)</math>. Значення CRC є по суті остачею від ділення многочлена, відповідного вхідним даним, на деякий фіксований породжувальний многочлен.

Кожній послідовності бітів <math>a_0, a_1, ..., a_{N-1}</math> взаємно однозначно зіставляється двійковий многочлен <math>\textstyle \sum_{n=0}^{N-1} \displaystyle a_nx^n</math>, послідовність коефіцієнтів якого являє собою початкову послідовність. Наприклад, послідовність бітів 1011010 відповідає многочлену:<blockquote><math>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.</math></blockquote>Кількість різних многочленів степені меншої <math>N</math> дорівнює <math>2^N</math>, що збігається з числом всіх двійкових послідовностей довжини <math>N</math>.

Значення контрольної суми в алгоритмі з породжуючим многочленом <math>G(x)</math> степені <math>N</math> задається як бітова послідовність довжини <math>N</math>, яка представляє многочлен <math>R(x)</math>, отриманий в остачі при діленні многочлена <math>P(x)</math>, який представляє вхідний потік біт, на многочлен <math>G(x)</math>:<blockquote><math>R(x) = P(x)\cdot x^N\bmod\ G(x) </math></blockquote>де
: <math>R(x)</math>&nbsp;— многочлен, який представляє значення CRC;
: <math>P(x)</math>— многочлен, коефіцієнти якого представляють вхідні дані;
: <math>G(x)</math>&nbsp;— породжувальний многочлен;
: <math>N</math>&nbsp;— степінь породжувального многочлена.
Множення <math>x^N</math> здійснюється приписуванням нульових бітів до вхідної послідовності, що покращує якість гешування для коротких вхідних послідовностей.

При діленні з остачею початкового многочлена на породжуючий многочлен <math>G(x)</math> степені <math>N</math> можна отримати <math>2^N</math> різних остач від ділення. <math>G(x)</math> найчастіше є [[Незвідний многочлен|незвідним многочленом]]. Зазвичай його підбирають відповідно до вимог до геш-функції у контексті кожного конкретного застосування. Проте, існує багато стандартизованих породжувальних многочленів, що володіють добрими математичними та кореляційними властивостями (мінімальне число [[Колізія хеш-функції|колізій]], простота обчислення), деякі з котрих приведені нижче.

== Обчислення CRC ==

=== Параметри алгоритму ===
Одним з основних параметрів CRC є породжувальний многочлен.

З породжувальним многочленом пов'язаний інший параметр&nbsp;— його [[Степінь многочлена|степінь]], який визначає кількість бітів, застосованих для обчислення значення CRC. На практиці найбільш поширені 8-, 16- та 32-бітові слова, що є наслідком особливостей архітектури сучасної обчислювальної техніки.

Ще одним параметром є початкове (стартове) значення слова. Вказані параметри повністю визначають «традиційний» алгоритм обчислення CRC. Існують також модифікації алгоритму, наприклад, які використовують [[Порядок байтів|зворотний порядок]] обробки бітів.

=== Опис процедури ===
З файлу береться перше слово&nbsp;— це може бути бітовий (CRC-1), байтовий (CRC-8) або будь-який інший елемент. Якщо старший біт у слові «1», то слово зсувається вліво на один розряд з подальшим виконанням операції [[XOR]] з породжувальним многочленом. Відповідно, якщо старший біт у слові «0», то після [[Бітовий зсув|зсуву]] операція XOR не виконується. Після зсуву втрачається старий старший біт, а молодший біт звільняється&nbsp;— його значення встановлюється рівним нулю. На місце молодшого біту завантажується черговий біт із файлу, й операція повторюється до тих пір, поки не завантажиться останній біт файлу. Після проходження всього файлу, в слові залишається остача, яка і є контрольною сумою.

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

Цей парадокс стосується й вибору многочлена-генератора: найчастіше [[Стандартизація|стандартизовані]] многочлени не є найбільш ефективними в плані [[Неперервний рівномірний розподіл|статичних]] властивостей відповідного їм ''check redundancy code''.

При цьому багато широко використовуваних многочленів не є найефективнішими із всіх можливих. У 1993—2004 роках група вчених займалася дослідженням породжувальних многочленів розрядності до 16, 24 та 36 біт й знайшла многочлени, які дають кращу, ніж стандартизовані многочлени, продуктивність у сенсі [[Відстань Геммінга|кодової відстані]]. Один із результатів цього дослідження вже знайшов своє застосування в протоколі [[iSCSI]].

Найпопулярніший та рекомендований [[IEEE]] многочлен для CRC-32 використовується в [[Ethernet]], [[FDDI]]; також цей многочлен є генератором [[Коди Гемінга|коду Геммінга]]. Використання іншого многочлену&nbsp;— CRC-32C&nbsp;— дозволяє досягти такої ж продуктивності при довжині вихідного повідомлення від 58 біт до 131 кбіт, а в деяких діапазонах довжини вхідного повідомлення може бути навіть більше&nbsp;— тому в наш час він також має популярність. Наприклад, [https://www.itu.int/dms_pub/itu-t/opb/tut/T-TUT-HOME-2010-PDF-E.pdf стандарт ITU-T G.hn]<ref>{{Cite book|title=ITU-T|last=|first=|year=2010|publisher=|location=|pages=|language=en|isbn=}}</ref> використовує CRC-32C з ціллю виявлення помилок в [[Корисне навантаження|корисному навантаженні]].

Нижче в таблиці приведені найбільш розповсюджені многочлени&nbsp;— генератори CRC. На практиці обчислення CRC може включати пре- та пост-інверсію, а також зворотний порядок обробки бітів. У власницьких реалізаціях CRC для ускладнення аналізу коду використовують ненульові початкові значення регістрів.
{| class="wikitable"
! rowspan="2" |Назва
! rowspan="2" |Многочлен
! rowspan="2" |Використання
! colspan="3" |'''Представлення'''
|-
!Нормальне
!Реверсоване
!Реверсоване
від зворотнього
|-
|CRC-1
|<math>x + 1</math>
|використовується в апаратному контролі помилок;
також відомий як [[біт парності]]
|0x1
|0x1
|0x1
|-
|CRC-4-ITU
|<math>x^4 + x + 1</math>
|[[ITU]] G.704
<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en|title=G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels   P.7|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>
|0x3
|0xC
|0x9
|-
|CRC-5-EPC
|<math>x^5 + x^3 + 1</math>
|Gen 2 RFID<ref>{{Cite book|title=GEN 2 RFID|last=|first=|year=|publisher=|location=|pages=35|language=|isbn=}}</ref>
|0x09
|0x12
|0x14
|-
|CRC-5-ITU
|<math>x^5 + x^4 + x^2 + 1</math>
|[[ITU]] G.704<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en|title=G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels P.9|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>
|0x15
|0x15
|0x1A
|-
|CRC-5-USB
|<math>x^5 + x^2 + 1</math>
|[[USB]] token packets
|0x05
|0x14
|0x12
|-
|CRC-6-ITU
|<math>x^6 + x + 1</math>
|[[ITU]] G.704<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en|title=G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels p.3|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>
|0x03
|0x30
|0x21
|-
|CRC-7
|<math>x^7 + x^3 + 1</math>
|системи телекомунікації, [[ITU]]-T G.707<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.707/en|title=G.707 : Network node interface for the synchronous digital hierarchy (SDH) P. 7|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>, [[ITU]]-T G.832<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.832/en|title=G.832 : Transport of SDH elements on PDH networks - Frame and multiplexing structures|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>, [[MultiMediaCard|MMC]], [[Secure Digital|SD]]
|0x09
|0x48
|0x44
|-
|CRC-8-[[CCITT]]
|<math>x^8 + x^2 + x  +1</math>
|ATM HEC, [[ISDN]] Header Error Control 
and Cell Delineation ITU-T [http://www.itu.int/rec/T-REC-I.432.1-199902-I/en I.432.1 (02/99)]
|0x07
|0xE0
|0x83
|-
|CRC-8-Dallas/Maxim
|<math>x^8 + x^5 + x^4 + 1</math>
|1-Wire bus
|0x31
|0x8C
|0x98
|-
|CRC-8
|<math>x^8 + x^7 + x^6 + x^4 + x^2 + 1</math>
|[[ETSI]] EN 302 307, 5.1.4<ref>{{Cite book|title=Final draft ETSI EN 302 307 V1.2.1|last=|first=|year=2009|publisher=ETSI|location=|pages=|language=EN|isbn=}}</ref>
|0xD5
|0xAB
|0xEA
|-
|CRC-8-SAE J1850
|<math>x^8 + x^4 + x^3 + x^2 + 1</math>
|
|0x1D
|0xB8
|0x8E
|-
|CRC-10
|<math>x^{10} + x^9 + x^5 + x^4 + x + 1</math>
|
|0x233
|0x331
|0x319
|-
|CRC-11
|<math>x^{11} + x^9 + x^8 + x^7 + x^2 + 1</math>
|FlexRay<ref>{{Cite web|url=http://www.ni.com/white-paper/3352/en/|title=FlexRay Automotive Communication Bus Overview - National Instruments|last=|first=|date=|website=www.ni.com|publisher=|language=|accessdate=}}</ref>
|0x385
|0x50E
|0x5C2
|-
|CRC-12
|<math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math>
|системи телекомунікації
|0x80F
|0xF01
|0xC07
|-
|CRC-15-[[Controller Area Network|CAN]]
|<math>x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1</math>
|
|0x4599
|0x4CD1
|0x62CC
|-
|CRC-16-[[IBM]]
|<math>x^{16} + x^{15} + x^2 + 1</math>
|Bisync, [[Modbus]], [[USB]], [[ANSI]] X3.28<sup>[20]</sup>, багато інших;
також відомий як ''CRC-16'' та ''CRC-16-ANSI''
|0x8005
|0xA001
|0xC002
|-
|CRC-16-CCITT
|<math>x^{16} + x^{12} + x^5 + 1</math>
|[[X.25]], [[HDLC]], XMODEM, [[Bluetooth]], [[Secure Digital|SD]] та інші
|0x1021
|0x8408
|0x8810
|-
|CRC-16-T10-DIF
|<math>x^{16} + x^{15} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math>
|[[SCSI]] DIF
|0x8BB7
|0xEDD1
|0xC5DB
|-
|CRC-16-[[DNP3|DNP]]
|<math>x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1</math>
|DNP, [[IEC 60870-5|IEC 870]], [[Meter-Bus|M-Bus]]
|0x3D65
|0xA6BC
|0x9EB2
|-
|CRC-24
|<math>x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{11} + x^{10} +</math><math>x^8 + x^7 + x^6 + x^3 + x + 1</math>
|FlexRay
|0x5D6DCB
|0xD3B6BA
|0xAEB6E5
|-
|CRC-24-Radix-64
|<math>x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + </math>

<math>x^5 + x^4 + x^3 + x + 1 </math>
|[[Pretty Good Privacy|OpenPGP]]
|0x864CFB
|0xDF3261
|0xC3267D
|-
|CRC-30
|<math>x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^8 + x^7 + </math>

<math>x^6 + x^2 + x + 1 </math>
|[[CDMA]]
|0x2030B9C7
|0x38E74301
|0x30185CE3
|-
|CRC-32-[[IEEE 802.3]]
|<math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + </math>

<math>x^5 + x^4 + x^2 + x + 1 </math>
|V.42, [[MPEG-2]], [[Portable Network Graphics|PNG]], [[POSIX]] cksum
|0x04C11DB7
|0xEDB88320
|0x82608EDB
|-
|CRC-32C (Castagnoli)
|<math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + </math>

<math>x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1 </math>
|[[iSCSI]], G.hn payload
|0x1EDC6F41
|0x82F63B78
|0x8F6E37A0
|-
|CRC-32K (Koopman)
|<math>x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + </math>

<math>x^{11} + x^{10} + x^7 + x^6 + x^4 + x^2 + x + 1 </math>
|
|0x741B8CD7
|0xEB31D82E
|0xBA0DC66B
|-
|CRC-32Q
|<math>x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^8 + x^7 + x^5 + x^3 + x + 1 </math>
|авіація; AIXM
|0x814141AB
|0xD5828281
|0xC0A0A0D5
|-
|CRC-64-ISO
|<math>x^{64} + x^4 + x^3 + x + 1 </math>
|HDLC&nbsp;— ISO 3309
|0x000000000000001B
|0xD800000000000000
|0x800000000000000D
|-
|CRC-64-[[Ecma International|ECMA]]
|<math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + </math>

<math>x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + </math>

<math>x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1 </math>
|
|0x42F0E1EBA9EA3693
|0xC96C5795D7870F42
|0xA17870F5D4F51B49
|}
Наявні стандарти CRC-128 (IEEE) та CRC-256 (IEEE) в теперішній час витіснені [[Криптографічна геш-функція|криптографічними геш-функціями]].

== Специфікації алгоритмів CRC ==
Однією з найвідоміших є [http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc/crc.htm методика Ross N. Williams]<ref>{{Cite web|url=http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc/crc.htm|title=CRC-алгоритмы обнаружения ошибок.|last=|first=|date=|website=embedded.ifmo.ru|publisher=|language=|accessdate=|archive-date=2016-11-20|archive-url=https://web.archive.org/web/20161120022651/http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc/crc.htm}}</ref>. У ній використовуються наступні параметри:
* Назва алгоритму (name);

* Ступінь породжує контрольну суму многочлена (width);

* Сам виготовляючий поліном (poly). Для того, щоб записати його у вигляді значення, його спочатку записують як бітову послідовність, при цьому старший біт опускається&nbsp;— він завжди дорівнює 1. Наприклад, многочлен в даній нотації буде записаний числом. Для зручності отримане двійкове подання записують в шістнадцятковій формі. Для нашого випадку воно буде дорівнює або 0x11;

* Стартові дані (init), тобто значення регістрів на момент початку обчислень;

* Прапор (RefIn), який вказує на початок і напрямок обчислень. Існує два варіанти: False&nbsp;— починаючи зі старшого значущого [http://arduino.ua/ru/prog/ShiftOut біта (MSB-first),]<ref name=":0">{{Cite web|url=http://arduino.ua/ru/prog/ShiftOut|title=ShiftOut Программирование Ардуино|last=|first=|date=|website=arduino.ua|publisher=|language=|accessdate=}}</ref> або True&nbsp;— з молодшого [http://arduino.ua/ru/prog/ShiftOut (LSB-first);]<ref name=":0"/>

* Прапор (RefOut), що визначає, інвертується чи порядок бітів регістра при вході на елемент XOR;

* Число (XorOut), з яким складається по [[Модуль над кільцем|модулю 2]] отриманий результат;

* Значення CRC (check) для рядка «123456789».

==== Приклади<ref>{{Cite web|url=http://reveng.sourceforge.net/crc-catalogue/|title=Catalogue of parametrised CRC algorithms|last=|first=|date=|website=reveng.sourceforge.net|publisher=|language=|accessdate=}}</ref> ====
{| class="wikitable"
!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
|}

== Примітки ==
{{reflist}}

== Див. також ==
* [[Хешування]]

== Посилання ==
* [https://web.archive.org/web/20170531035748/http://posibnyky.vntu.edu.ua/e_s/index.htm Електронні системи: навчальний посібник / Й.&nbsp;Й.&nbsp;Білинський, К.&nbsp;В.&nbsp;Огороднік, М.&nbsp;Й.&nbsp;Юкиш.&nbsp;— Вінниця: ВНТУ, 2011.&nbsp;— 208 с.]

{{Геш-функції та коди аутентифікації повідомлення}}
{{програмування-доробити}}

[[Категорія:Телекомунікації]]
[[Категорія:Хешування]]