WikiSort.ru - Не сортированное

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

Введение

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

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

Алгоритм 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

Имеется викиучебник по теме
«Программные реализации вычисления CRC»

Параметры алгоритма

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

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

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

Описание процедуры

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

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

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу.^[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	${\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 calculation and free library