Циклический избыточный код

Цикли́ческий избы́точный код (англ. Cyclic redundancy check^{[нет в источнике]}, CRC^[1]) — вид корректирующего кода, получаемый алгоритмом нахождения контрольной суммы и предназначенный для проверки целостности данных^[2]. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.

Введение

Понятие циклические коды — достаточно широкое^[3]. В англоязычной литературе CRC понимается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check^[4]. Под первым понятием подразумевают математический феномен циклических кодов, под вторым — конкретное применение этого феномена как хеш-функции.

Циклические коды не только просты в реализации, но и обладают тем преимуществом, что подходят для обнаружения пакетных ошибок: непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, потому что пакетные ошибки являются распространёнными ошибками передачи во многих каналах связи, включая магнитные и оптические устройства. Обычно n‑разрядный CRC, применяемый к блоку данных произвольной длины, и при расположении контрольной суммы непосредственно вслед за данными, обнаруживает любой одиночный пакет ошибок длиной не более n бит, а доля всех более длинных пакетов ошибок, которые он обнаружит, равна (1 − 2⁻ⁿ).

Этот раздел нужно дополнить.

Пожалуйста, улучшите и дополните раздел. (11 декабря 2012)

Математическое описание

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем ${\displaystyle GF(2)}$. Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен^[англ.].

Каждой конечной последовательности битов ${\displaystyle a_{0},a_{1},\dots ,a_{N-1}}$ взаимно однозначно сопоставляется двоичный полином ${\displaystyle \textstyle \sum _{n=0}^{N-1}a_{n}x^{n}}$, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

${\displaystyle 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}.}$

Количество различных многочленов степени, меньшей ${\displaystyle N}$, равно ${\displaystyle 2^{N}}$, что совпадает с числом всех двоичных последовательностей длины ${\displaystyle N}$.

Значение контрольной суммы в алгоритме с порождающим многочленом ${\displaystyle G(x)}$ степени ${\displaystyle N}$ определяется как битовая последовательность длины ${\displaystyle N}$, представляющая многочлен ${\displaystyle R(x)}$, получившийся в остатке при делении многочлена ${\displaystyle P(x)}$, представляющего входной поток бит, на многочлен ${\displaystyle G(x)}$:

${\displaystyle R(x)=P(x)\cdot x^{N}\,{\bmod {\,}}G(x)}$

где ${\displaystyle R(x)}$ — многочлен, представляющий значение CRC;

${\displaystyle P(x)}$ — многочлен, коэффициенты которого представляют входные данные;

${\displaystyle G(x)}$ — порождающий многочлен;

${\displaystyle N}$ — степень порождающего многочлена.

Умножение ${\displaystyle x^{N}}$ осуществляется приписыванием ${\displaystyle N}$ нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

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

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

Вычисление CRC

	Имеется викиучебник по теме «Реализации алгоритмов/Циклический избыточный код»

Популярные и стандартизованные полиномы

В то время как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу^[1][5].

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

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16^[1] 24 и 32 бит^[6][7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния^[7]. Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга^[8]. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше, поэтому в наши дни он тоже пользуется популярностью^[7]. К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

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

Название	Полином	Представления:[9] нормальное / реверсированное / реверсированное от обратного
CRC-1	${\displaystyle x+1}$ (используется в аппаратном контроле ошибок; также известен как бит чётности)	0x1 / 0x1 / 0x1
CRC-4-ITU	${\displaystyle x^{4}+x+1}$ (ITU G.704[10])	0x3 / 0xC / 0x9
CRC-5-EPC	${\displaystyle x^{5}+x^{3}+1}$ (Gen 2 RFID[11])	0x09 / 0x12 / 0x14
CRC-5-ITU	${\displaystyle x^{5}+x^{4}+x^{2}+1}$ (ITU G.704[12])	0x15 / 0x15 / 0x1A
CRC-5-USB	${\displaystyle x^{5}+x^{2}+1}$ (USB token packets)	0x05 / 0x14 / 0x12
CRC-6-ITU	${\displaystyle x^{6}+x+1}$ (ITU G.704[13])	0x03 / 0x30 / 0x21
CRC-7	${\displaystyle x^{7}+x^{3}+1}$ (системы телекоммуникации, ITU-T G.707[14], ITU-T G.832[15], MMC, SD)	0x09 / 0x48 / 0x44
CRC-8-CCITT	${\displaystyle x^{8}+x^{2}+x+1}$ (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim	${\displaystyle x^{8}+x^{5}+x^{4}+1}$ (1-Wire bus)	0x31 / 0x8C / 0x98
CRC-8-DVB-S2	${\displaystyle x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1}$ (ETSI EN 302 307[16], 5.1.4)	0xD5 / 0xAB / 0xEA[1]
CRC-8-SAE J1850	${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$	0x1D / 0xB8 / 0x8E
CRC-10	${\displaystyle x^{10}+x^{9}+x^{5}+x^{4}+x+1}$	0x233 / 0x331 / 0x319
CRC-11	${\displaystyle x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1}$ (FlexRay[17])	0x385 / 0x50E / 0x5C2
CRC-12	${\displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$ (системы телекоммуникации[18][19])	0x80F / 0xF01 / 0xC07
CRC-15-CAN	${\displaystyle x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1}$	0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM	${\displaystyle x^{16}+x^{15}+x^{2}+1}$ (Bisync, Modbus, USB, ANSI X3.28[20], многие другие; также известен как CRC-16 и CRC-16-ANSI)	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	${\displaystyle x^{16}+x^{12}+x^{5}+1}$ (X.25, HDLC, XMODEM, Bluetooth, SD и др.)	0x1021 / 0x8408 / 0x8810[1]
CRC-16-T10-DIF	${\displaystyle x^{16}+x^{15}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$ (SCSI DIF)	0x8BB7[21] / 0xEDD1 / 0xC5DB
CRC-16-DNP	${\displaystyle x^{16}+x^{13}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{2}+1}$ (DNP, IEC 870, M-Bus)	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher	Не CRC; см. Fletcher's checksum	Используется в Adler-32 A & B CRC
CRC-24	${\displaystyle 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}$ (FlexRay[17])	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64	${\displaystyle 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}$ (OpenPGP)	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	${\displaystyle 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}$ (CDMA)	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler	Не CRC; см. Adler-32	См. Adler-32
CRC-32-IEEE 802.3	${\displaystyle 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}$ (V.42, MPEG-2, PNG[22], POSIX cksum)	0x04C11DB7 / 0xEDB88320 / 0x82608EDB[7]
CRC-32C (Castagnoli)	${\displaystyle 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}$ (iSCSI, G.hn payload)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0[7]
CRC-32K (Koopman)	${\displaystyle 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}$	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B[7]
CRC-32Q	${\displaystyle x^{32}+x^{31}+x^{24}+x^{22}+x^{16}+x^{14}+x^{8}+x^{7}+x^{5}+x^{3}+x+1}$ (aviation; AIXM[23])	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	${\displaystyle x^{64}+x^{4}+x^{3}+x+1}$ (HDLC — ISO 3309)	0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA	${\displaystyle 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}+}$ ${\displaystyle 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}$[24]	0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

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

Спецификации алгоритмов CRC

Одной из самых известных является методика Ross N. Williams^[25]. В ней используются следующие параметры:

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

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

• Сам производящий полином (poly). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен ${\displaystyle x^{8}+x^{4}+1}$ в данной нотации будет записан числом ${\displaystyle 00010001_{2}}$. Для удобства полученное двоичное представление записывают в шестнадцатеричной форме. Для нашего случая оно будет равно ${\displaystyle 11_{h}}$ или 0x11;

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

• Флаг (RefIn), указывающий на начало и направление вычислений, для обнаружения пакетов ошибок должно соответствовать порядку передачи в канале^[англ.]. Существует два варианта: False — начиная со старшего значащего бита (MSB-first) или True — с младшего (LSB-first);

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

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

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

Примеры^[26]

Примечания

Литература

• Генри С. Уоррен, мл. Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4.

Ссылки

	Имеется викиучебник по теме «Реализации алгоритмов/Циклический избыточный код»

• Элементарное руководство по CRC алгоритмам обнаружения ошибок
• CRC, и как его восстановить
• Генератор CRC-функций на языках VHDL и Verilog
• Ross N. Williams/Anarchriz. Всё о CRC32 // Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок
• Ross N. Williams. A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS (англ.)

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

• CRC-калькулятор, написан на Qt
• On-line CRC32-калькулятор, для строк (можно менять кодировку и формат EndLine)
• On-line CRC-калькулятор
• On-line CRC-калькулятор crccalc.com
• On-line CRC calculation and free library