Просмотр кода страницы Циклический избыточный код

{{О|коде|методе мозгового штурма|CRC-карта}}
'''Цикли́ческий избы́точный код''' ({{lang-en|Cyclic redundancy check{{нет в источнике|14|02|2021}}, CRC<ref name="koop04"/>}}) — вид [[Корректирующий код|корректирующего кода]], получаемый алгоритмом нахождения [[контрольная сумма|контрольной суммы]] и предназначенный для проверки целостности данных<ref>{{Cite web |url=http://www.intuit.ru/department/network/wifi/1/wifi_1.html |title=Интернет-университет информационных технологий. Лекция: Организация беспроводных сетей |access-date=2011-07-30 |archive-date=2011-11-12 |archive-url=https://web.archive.org/web/20111112174328/http://www.intuit.ru/department/network/wifi/1/wifi_1.html |url-status=live }}</ref>. CRC является практическим приложением [[помехоустойчивое кодирование|помехоустойчивого кодирования]], основанным на определённых математических свойствах [[циклический код|циклического кода]].

== Введение ==
{{main|Циклический код}}
Понятие [[Циклический код|циклические коды]] — достаточно широкое<ref>{{Cite web |url=http://www.intuit.ru/department/network/baslocnet/10/baslocnet_10.html |title=Интернет-университет информационных технологий Лекция: Алгоритмы сети Ethernet/Fast Ethernet |access-date=2011-07-30 |archive-date=2010-01-28 |archive-url=https://web.archive.org/web/20100128223355/http://www.intuit.ru/department/network/baslocnet/10/baslocnet_10.html |url-status=live }}</ref>. В англоязычной литературе CRC понимается двояко в зависимости от контекста: ''Cyclic Redundancy Code'' или ''Cyclic Redundancy Check''<ref>{{Cite web |url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4317846 |title=Walma, M.; Pipelined Cyclic Redundancy Check (CRC) Calculation |access-date=2011-07-30 |archive-date=2011-11-05 |archive-url=https://web.archive.org/web/20111105085601/http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4317846 |url-status=live }}</ref>. Под первым понятием подразумевают математический феномен циклических кодов, под вторым — конкретное применение этого феномена как [[хеш-функция|хеш-функции]].

Циклические коды не только просты в реализации, но и обладают тем преимуществом, что подходят для обнаружения пакетных ошибок: непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, потому что пакетные ошибки являются распространёнными ошибками передачи во многих каналах связи, включая магнитные и оптические устройства. Обычно n‑разрядный CRC, применяемый к блоку данных произвольной длины, и при расположении контрольной суммы непосредственно вслед за данными, обнаруживает любой одиночный пакет ошибок длиной не более n бит, а доля всех более длинных пакетов ошибок, которые он обнаружит, равна (1 − 2<sup>−n</sup>).
{{дополнить раздел|дата=2012-12-11}}

=== Помехоустойчивое кодирование ===
{{main|Обнаружение и исправление ошибок}}
Первые попытки создания кодов с избыточной информацией начались задолго до появления современных компьютеров. К примеру, ещё в [[1960-е годы|1960-х годах]] Ридом и Соломоном была разработана эффективная методика кодирования — [[Код Рида-Соломона]]. Использование её в те времена не представлялось возможным, так как произвести операцию [[декодирование|декодирования]] за [[Сложность вычислений|разумное время]] первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа [[Берлекэмп, Элвин|Берлекэмпа]], опубликованная в [[1968 год]]у. [[Алгоритм Берлекэмпа — Мэсси|Эта методика]], на практическое применение которой указал через год [[Мэсси, Джеймс|Мэсси]], и по сей день используется в цифровых устройствах, обеспечивающих приём [[Код Рида — Соломона|RS-кодированных]] данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего [[байт|октеты]]).

Но далеко не всегда от кода требуется [[коррекция ошибок]]. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли '' какие-нибудь '' сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.

Хотя код CRC используют обычно только для обнаружения ошибок, его математические свойства дают возможность найти и исправить одиночную ошибку в блоке бит, если каждому биту защищаемого блока (включая проверочные биты) соответствует свой уникальный остаток от деления на порождающий многочлен. Например, если порождающий многочлен неприводим, и длина блока не превышает порядок порождённой циклической группы.

=== Контрольная сумма ===
{{main|Контрольная сумма}}
В общем виде контрольная сумма представляет собой некоторое значение, вычисленное по определённой схеме на основе кодируемого сообщения. Проверочная информация при ''систематическом кодировании'' приписывается к передаваемым данным. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.

При передаче [[пакет (сетевые технологии)|пакетов]] по сетевому каналу могут возникнуть искажения исходной информации вследствие разных внешних воздействий: электрических наводок, плохих погодных условий и многих других. Сущность методики в том, что при хороших характеристиках контрольной суммы в подавляющем числе случаев ошибка в сообщении приведёт к изменению его контрольной суммы. Если исходная и вычисленная суммы не равны между собой, принимается решение о недостоверности принятых данных, и можно запросить повторную передачу пакета.

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

Каждой конечной последовательности [[бит]]ов <math>a_0, a_1, \dots, a_{N-1}</math> [[биекция|взаимно однозначно]] сопоставляется двоичный полином <math>\textstyle\sum_{n=0}^{N-1} a_n x^n</math>, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

: <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>

Количество различных многочленов степени, меньшей <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>:

: <math>R(x) = P(x)\cdot x^N\, \bmod\, G(x)</math>

: где <math>R(x)</math> — многочлен, представляющий значение CRC;
: <math>P(x)</math> — многочлен, коэффициенты которого представляют входные данные;
: <math>G(x)</math> — порождающий многочлен;
: <math> N </math> — степень порождающего многочлена.

Умножение <math>x^N</math> осуществляется приписыванием <math>N</math> нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

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

Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число [[коллизия хеш-функции|коллизий]], простота вычисления), некоторые из которых перечислены ниже.

== Вычисление CRC ==
{{Викиучебник|Программные реализации вычисления CRC|Программные реализации вычисления CRC}}

=== Параметры алгоритма ===
Одним из основных параметров CRC является порождающий полином.

С порождающим полиномом связан другой параметр — его [[степень многочлена|степень]], которая определяет количество [[бит]]ов, используемых для вычисления значения CRC. На практике наиболее распространены 8-, 16- и 32-битовые слова, что является следствием особенностей [[микроархитектура|архитектуры]] современной вычислительной техники.

Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие [[Порядок байтов|обратный порядок]] обработки битов.

=== Описание процедуры ===
Из файла берётся первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции [[исключающее или|XOR]] с порождающим полиномом. Соответственно, если старший бит в слове «0», то после [[битовый сдвиг|сдвига]] операция XOR не выполняется. После сдвига теряется старший бит, а на место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла в слове остаётся остаток, который и является контрольной суммой.

== Популярные и стандартизованные полиномы ==
В то время как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу<ref name="koop04">{{cite web
 |author      = Philip Koopman, Tridib Chakravarty.
 |title       = Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks
 |date        = 2004
 |url         = http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
 |access-date  = ???
 |archive-url  = https://www.webcitation.org/618ad4oyk?url=http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
 |archive-date = 2011-08-22
 |url-status    = live
}}</ref><ref>{{cite web
 |url         = http://homepages.tesco.net/rainstorm/crc-catalogue.htm
 |title       = Catalogue of parameterised CRC algorithms
 |access-date  = ???
 |author      = Greg Cook.
 |date        = 2009-04-29
 |archive-url  = https://www.webcitation.org/618adVYf6?url=http://homepages.tesco.net/rainstorm/crc-catalogue.htm
 |archive-date = 2011-08-22
 |url-status    = live
}}</ref>.

Этот парадокс касается и выбора многочлена-генератора: зачастую [[стандартизация|стандартизованные]] полиномы не являются самыми эффективными в плане [[непрерывное равномерное распределение|статистических]] свойств соответствующего им ''check redundancy code''.

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16<ref name="koop04"/> 24 и 32 бит<ref>{{статья
| автор=G. Castagnoli, S. Braeuer, M. Herrman.
| год = июнь 1993
| заглавие = Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits
| издание =  IEEE Transactions on Communications
| том = 41 | номер = 6| doi = 10.1109/26.231911 | страницы = 883
}}</ref><ref name="koop02">{{статья
| автор = P. Koopman.
| год = июнь 2002
| заглавие = 32-Bit Cyclic Redundancy Codes for Internet Applications
| издание = The International Conference on Dependable Systems and Networks
| ссылка = http://citeseer.ist.psu.edu/koopman02bit.html
| страницы = 459
| doi = 10.1109/DSN.2002.1028931
| archive-date = 2008-03-29
| archive-url = https://web.archive.org/web/20080329071307/http://citeseer.ist.psu.edu/koopman02bit.html
}}</ref> и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле [[Расстояние Хемминга|кодового расстояния]]<ref name="koop02"/>. Один из результатов этого исследования уже нашёл своё применение в протоколе [[iSCSI]].

Самый популярный и рекомендуемый [[IEEE]] полином для CRC-32 используется в [[Ethernet]], [[FDDI]]; также этот многочлен является генератором [[Код Хемминга|кода Хемминга]]<ref>{{cite conference
 | first = K
 | last = Brayer
 | coauthors = Hammond, J L Jr.
 | year = 1975
 | month = December
 | title = Evaluation of error detection polynomial performance on the AUTOVON channel
 | conference = National Telecommunications Conference, New Orleans, La
 | book-title = Conference Record
 | volume = 1
 | publisher = Institute of Electrical and Electronics Engineers
 | location = New York
 | pages = 8—21 to 8-25
}}</ref>. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше, поэтому в наши дни он тоже пользуется популярностью<ref name="koop02"/>. К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

Ниже в таблице перечислены наиболее распространённые многочлены — генераторы CRC. На практике вычисление CRC может включать пре- и постинверсию, а также обратный порядок обработки битов. В [[авторское право|проприетарных реализациях]] CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.

{|class="wikitable"
! Название || Полином || Представления:<ref>В представлениях опущен старший бит.</ref> нормальное / реверсированное / реверсированное от обратного
|-
|CRC-1 || <math>x + 1</math> (используется в аппаратном контроле ошибок; также известен как ''[[бит чётности]]'') || 0x1 / 0x1 / 0x1
|-
|CRC-4-ITU || <math>x^4 + x + 1</math> ([[Сектор стандартизации электросвязи МСЭ|ITU]] G.704<ref>[http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704] {{Wayback|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en |date=20121009112319 }}, p. 12</ref>) || 0x3 / 0xC / 0x9
|-
|CRC-5-EPC || <math>x^5 + x^3 + 1</math> ([[Radio-frequency identification|Gen 2 RFID]]<ref>{{статья|заглавие=Class-1 Generation-2 UHF RFID Protocol version 1.2.0|издатель=EPCglobal|ссылка=http://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2_1_0_9-standard-20050126.pdf|год=23 октября 2008|страницы=35|страниц=108|издание=|archive-url=https://web.archive.org/web/20081120022612/http://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2_1_0_9-standard-20050126.pdf|archive-date=2008-11-20}}</ref>) || 0x09 / 0x12 / 0x14
|-
|CRC-5-ITU || <math>x^5 + x^4 + x^2 + 1</math> ([[Сектор стандартизации электросвязи МСЭ|ITU]] G.704<ref>[http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704] {{Wayback|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en |date=20121009112319 }}, p. 9</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>[http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704] {{Wayback|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en |date=20121009112319 }}, p. 3</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)<!-- Заголовок добавлен ботом --> |access-date=2009-10-16 |archive-date=2012-10-07 |archive-url=https://web.archive.org/web/20121007221444/http://www.itu.int/rec/T-REC-G.707/en |url-status=live }}</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<!-- Заголовок добавлен ботом --> |access-date=2009-10-16 |archive-date=2012-10-12 |archive-url=https://web.archive.org/web/20121012124944/http://www.itu.int/rec/T-REC-G.832/en |url-status=live }}</ref>, [[MultiMediaCard|MMC]], [[Secure Digital|SD]]) || 0x09 / 0x48 / 0x44
|-
|CRC-8-[[CCITT]] || <math>x^8 + x^2 + x + 1</math> ([[Asynchronous Transfer Mode|ATM]] [[Header Error Correction|HEC]]), [[ISDN]] [[HEC|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 Semiconductor|Dallas]]/[[Maxim Integrated Products|Maxim]] || <math>x^8 + x^5 + x^4 + 1</math> ([[1-Wire]] [[Bus (computing)|bus]]) || 0x31 / 0x8C / 0x98
|-
|CRC-8-DVB-S2 || <math>x^8 + x^7 + x^6 + x^4 + x^2 + 1</math> ([[ETSI]] EN 302 307<ref>{{Cite web |url=http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_40/en_302307v010201o.pdf |title=EN 302 307. Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2) |access-date=2011-09-19 |archive-date=2012-07-04 |archive-url=https://web.archive.org/web/20120704012936/http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_40/en_302307v010201o.pdf |url-status=live }}</ref>, 5.1.4) || 0xD5 / 0xAB / 0xEA<ref name="koop04"/>
|-
|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 name="flexray-spec">{{статья|заглавие=FlexRay Protocol Specification version 2.1 Revision A|издатель=Flexray Consortium|год=22 декабря 2005|страницы=93|страниц=245}}</ref>) || 0x385 / 0x50E / 0x5C2
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math> (системы телекоммуникации<ref>{{статья
  | автор=A. Perez, Wismer, Becker.
  | заглавие =  Byte-Wise CRC Calculations
  | издание = IEEE Micro
  | том = 3
  | номер = 3
  | страницы = 40—50
  | год = 1983
  | doi = 10.1109/MM.1983.291120
}}</ref><ref>{{статья
  |автор=T. V. Ramabadran, S. S. Gaitonde.
  | заглавие = A tutorial on CRC computations
  | издание = IEEE Micro
  | том = 8
  | номер = 4
  | год = 1988
  | страницы = 62—75
  | doi = 10.1109/40.7773
}}</ref>)
 || 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> ([[Binary Synchronous Communications|Bisync]], [[Modbus]], [[USB]], [[ANSI]] X3.28<ref>{{Cite web |url=http://www.incits.org/press/1997/pr97020.htm |title=Архивированная копия |access-date=2009-10-16 |archive-url=https://web.archive.org/web/20091001172850/http://www.incits.org/press/1997/pr97020.htm |archive-date=2009-10-01 |url-status=dead }}</ref>, многие другие; также известен как ''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<ref name="koop04"/>
|-
|CRC-16-[[International Committee for Information Technology Standards|T10]]-[[Data Integrity Field|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<ref>{{cite web|author=Pat Thaler.|title=16-bit CRC polynomial selection|publisher=INCITS T10|date=2003-08-28|url=http://www.t10.org/ftp/t10/document.03/03-290r0.pdf|access-date=???|archive-url=https://www.webcitation.org/618advs5T?url=http://www.t10.org/ftp/t10/document.03/03-290r0.pdf|archive-date=2011-08-22|url-status=live}}</ref> / 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-16-Fletcher || Не CRC; см. [[Fletcher's checksum]] || Используется в [[Adler-32]] A & B CRC
|-
|CRC-24 || <math>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</math> ([[FlexRay]]<ref name="flexray-spec"/>) || 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 + x^5 + x^4 + x^3 + x + 1 </math> ([[Pretty Good Privacy#OpenPGP|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} + x^{6} + x^{2} + x + 1 </math> ([[CDMA]]) || 0x2030B9C7 / 0x38E74301 / 0x30185CE3
|-
|CRC-32-Adler || Не CRC; см. [[Adler-32]] || См. [[Adler-32]]
|-
|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 + x^5 + x^4 + x^2 + x + 1</math> ([[V.42]], [[MPEG-2]], [[Portable Network Graphics|PNG]]<ref>{{cite web
 |url         = http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html
 |title       = PNG (Portable Network Graphics) Specification, Version 1.2
 |access-date  = ???
 |author      = Thomas Boutell, Glenn Randers-Pehrson и др.
 |date        = 1998-07-14
 |archive-url  = https://www.webcitation.org/618aeMw33?url=http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html
 |archive-date = 2011-08-22
 |url-status    = live
}}</ref>, [[POSIX]] [[cksum]])
|| 0x04C11DB7 / 0xEDB88320 / 0x82608EDB<ref name="koop02"/> <!-- little- and big-endian rows are merged, as with CRC-16-CCITT -->
|-
|CRC-32C (Castagnoli) || <math>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</math> ([[iSCSI]], [[G.hn]] payload) || 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0<ref name="koop02"/>
|-
|CRC-32K (Koopman) || <math>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</math> || 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B<ref name="koop02"/>
|-
|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> (aviation; [[AIXM]]<ref>{{cite web|title=AIXM Primer version 4.5|url=http://www.eurocontrol.int/aim/gallery/content/public/aicm_aixm_4_5/aixm_primer/AIXM_Primer_4.5.pdf|publisher=European Organisation for the Safety of Air Navigation|date=2006-03-20|access-date=???|archive-url=https://www.webcitation.org/618aeucX4?url=http://www.eurocontrol.int/aim/gallery/content/public/aicm_aixm_4_5/aixm_primer/AIXM_Primer_4.5.pdf|archive-date=2011-08-22|url-status=live}}</ref>) || 0x814141AB / 0xD5828281 / 0xC0A0A0D5
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math> ([[High-Level Data Link Control|HDLC — 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} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} +</math> <math>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</math><ref>[http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] {{Wayback|url=http://www.ecma-international.org/publications/standards/Ecma-182.htm |date=20200731173949 }} p. 51</ref> || 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49
|}

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время{{когда}} вытеснены [[криптографическая хеш-функция|криптографическими хеш-функциями]].

== Спецификации алгоритмов CRC ==
Одной из самых известных является методика Ross N. Williams<ref>{{cite web
 |url         = http://www.ross.net/crc/crcpaper.html
 |title       = CRC Rocksoft
 |author      = Ross N. Williams.
 |date        = 1993
 |archive-url  = https://web.archive.org/web/20110903033652/http://www.ross.net/crc/crcpaper.html
 |archive-date = 2011-09-03
 |access-date  = 2012-04-17
 |url-status    = dead
}}</ref>. В ней используются следующие параметры:

* Название алгоритма (''name'');

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

* Сам производящий полином (''poly''). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен <math> x^8+x^4+1 </math> в данной [[нотация|нотации]] будет записан числом <math> 00010001_2 </math>. Для удобства полученное двоичное представление записывают в [[шестнадцатеричная система счисления|шестнадцатеричной]] форме. Для нашего случая оно будет равно <math>11_h</math> или 0x11;

* Стартовые данные (''init''), то есть значения регистров на момент начала вычислений;

* Флаг (''RefIn''), указывающий на начало и направление вычислений, для обнаружения пакетов ошибок должно соответствовать {{iw|Порядок битов|порядку передачи в канале|en|Bit numbering}}. Существует два варианта: False — начиная со старшего значащего бита (MSB-first) или True — с младшего (LSB-first);

* Флаг (''RefOut''), определяющий, инвертируется ли порядок битов регистра при входе на элемент [[XOR]];

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

* Значение CRC (''check'') для строки «123456789» .

; Примеры<ref>{{cite web
 | url         = http://reveng.sourceforge.net/crc-catalogue/
 | title         = Catalogue of parametrised CRC algorithms
 | author         = Greg Cook
 | date         = 2016-01-18
 | access-date         = 2016-02-01
 | archive-date         = 2016-01-09
 | archive-url         = https://web.archive.org/web/20160109162313/http://reveng.sourceforge.net/crc-catalogue/
 | url-status         = live
 }}</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 || 0x0589 || 0x0 || false || false || 0x1 || 0x7E
|-
|CRC-16/DECT-X || 16 || 0x0589 || 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 || 0x04C11DB7 || 0x7FFFFFFF || false || false || 0x7FFFFFFF || 0xCE9E46C
|-
|CRC-32/[[zlib]] || 32 || 0x04C11DB7 || 0xFFFFFFFF || true || true || 0xFFFFFFFF || 0xCBF43926
|-
|CRC-32/BZIP2 || 32 || 0x04C11DB7 || 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 || 0x04C11DB7 || 0xFFFFFFFF || false || false || 0x0 || 0x376E6E7
|-
|CRC-32/POSIX || 32 || 0x04C11DB7 || 0x0 || false || false || 0xFFFFFFFF || 0x765E7680
|-
|CRC-32Q || 32 || 0x814141AB || 0x0 || false || false || 0x0 || 0x3010BF7F
|-
|CRC-32/JAMCRC || 32 || 0x04C11DB7 || 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
|}

== Примечания ==
{{примечания|2}}

== Литература ==
* {{книга
|заглавие = Алгоритмические трюки для программистов
|часть = Глава 5. Подсчет битов
|оригинал = Hacker’s Delight
|автор = Генри С. Уоррен, мл.
|isbn = 0-201-91465-4
|страниц = 288
|год = 2007
|место = М. |издательство = [[Вильямс (издательство)|Вильямс]]
}}

== Ссылки ==
{{Викиучебник|Программные реализации вычисления CRC}}

* [https://web.archive.org/web/20130407000813/http://rsdn.ru/article/files/classes/SelfCheck/crcguide.pdf Элементарное руководство по CRC алгоритмам обнаружения ошибок]
* [https://web.archive.org/web/20120227054137/http://www.rsdn.ru/article/files/classes/SelfCheck/crcrevrs.pdf CRC, и как его восстановить]
* [http://www.easics.be/webtools/crctool Генератор CRC-функций] на языках [[VHDL]] и [[Verilog]]
* Ross N. Williams/Anarchriz. [https://web.archive.org/web/20051229000614/http://www.wasm.ru/docs/5/crc.zip Всё о CRC32] // Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок
* Ross N. Williams. [https://web.archive.org/web/20090528113024/http://www.ross.net/crc/download/crc_v3.txt A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS]{{ref|en}}

; CRC Калькуляторы

* [https://github.com/KoynovStas/QCRC_Calc CRC-калькулятор, написан на Qt]
* [http://dencode.com/hash/crc32 On-line CRC32-калькулятор, для строк (можно менять кодировку и формат EndLine)]
* [http://www.zorc.breitbandkatze.de/crc.html On-line CRC-калькулятор]
* [https://crccalc.com/ On-line CRC-калькулятор crccalc.com]
* [http://www.lammertbies.nl/comm/info/crc-calculation.html On-line CRC calculation and free library]


{{Хеш-алгоритмы}}

[[Категория:Обнаружение и устранение ошибок]]