Циклическая проверка избыточности

Проверка циклическим избыточным кодом ( CRC ) является код ошибки обнаружения обычно используются в цифровых сетей и запоминающих устройств для обнаружения случайного изменения исходных данных. К блокам данных, поступающим в эти системы, прикрепляется короткое контрольное значение , основанное на остатке от полиномиального деления их содержимого. При извлечении расчет повторяется, и, если контрольные значения не совпадают, можно предпринять корректирующие действия против повреждения данных. CRC могут использоваться для исправления ошибок (см. Битовые фильтры ). ^[1]

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

Введение [ править ]

CRC основаны на теории циклических кодов с исправлением ошибок . Использование систематических циклических кодов, которые кодируют сообщения путем добавления контрольного значения фиксированной длины, с целью обнаружения ошибок в сетях связи, было впервые предложено У. Уэсли Петерсоном в 1961 году. ^[2] Циклические коды не только просты в использовании. реализуются, но имеют то преимущество, что они особенно хорошо подходят для обнаружения пакетных ошибок : непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, поскольку пакетные ошибки являются обычными ошибками передачи во многих каналах связи , включая магнитные и оптические устройства хранения. Обычно n-битовая CRC, применяемая к блоку данных произвольной длины, обнаружит любой одиночный пакет ошибок длиной не более n бит, а доля всех более длинных пакетов ошибок, которые он обнаружит, будет (1-2 ^{- n} ) .

Спецификация кода CRC требует определения так называемого порождающего полинома . Этот многочлен становится делителем в полиномиальном делении в столбик , при котором сообщение рассматривается как делимое, в котором частное отбрасывается, а остаток становится результатом. Важное предостережение заключается в том, что коэффициенты полинома вычисляются в соответствии с арифметикой конечного поля , поэтому операцию сложения всегда можно выполнять поразрядно-параллельно (нет переноса между цифрами).

На практике все обычно используемые CRC используют поле Галуа из двух элементов, GF (2) . Эти два элемента обычно называются 0 и 1, что соответствует компьютерной архитектуре.

CRC называется n- битным CRC, если его контрольное значение имеет длину n бит. Для заданного n возможно несколько CRC, каждый с различным полиномом. Такой многочлен имеет наивысшую степень n , что означает, что он имеет n + 1 член. Другими словами, многочлен имеет длину n + 1 ; для его кодирования требуется n + 1 бит. Обратите внимание, что в большинстве спецификаций полиномов либо отбрасываются MSB, либо LSB , поскольку они всегда равны 1. CRC и связанный с ним многочлен обычно имеют имя в форме CRC- n -XXX, как в таблице ниже.

Простейшая система обнаружения ошибок, бит четности , на самом деле представляет собой 1-битную CRC: она использует полином генератора  x + 1 (два члена) и имеет имя CRC-1.

Заявление [ править ]

Устройство с поддержкой CRC вычисляет короткую двоичную последовательность фиксированной длины, известную как контрольное значение или CRC , для каждого блока данных, который должен быть отправлен или сохранен, и добавляет его к данным, образуя кодовое слово .

Когда кодовое слово принимается или считывается, устройство либо сравнивает свое контрольное значение с одним, только что вычисленным из блока данных, либо, что эквивалентно, выполняет CRC для всего кодового слова и сравнивает полученное контрольное значение с ожидаемой константой остатка .

Если значения CRC не совпадают, то блок содержит ошибку данных.

Устройство может предпринять корректирующие действия, например перечитать блок или запросить его повторную отправку. В противном случае предполагается, что данные не содержат ошибок (хотя с некоторой небольшой вероятностью они могут содержать необнаруженные ошибки; это заложено в самой природе проверки ошибок). ^[3]

Целостность данных [ править ]

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

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

Во-вторых, в отличие от криптографических хэш-функций, CRC - это легко обратимая функция, что делает ее непригодной для использования в цифровых подписях. ^[4]

В-третьих, CRC - это линейная функция со свойством, которое ^[5]

${\ displaystyle \ operatorname {crc} (x \ oplus y \ oplus z) = \ operatorname {crc} (x) \ oplus \ operatorname {crc} (y) \ oplus \ operatorname {crc} (z);}$

в результате, даже если CRC шифруются с помощью потокового шифра , который использует XOR в качестве операции комбинирования (или режима из блочного шифра , который эффективно превращает его в потоковом шифр, такие как OFB или CFB), оба сообщений и связанный с ним CRC можно манипулировать без знания ключа шифрования; это был один из хорошо известных недостатков конструкции протокола Wired Equivalent Privacy (WEP). ^[6]

Вычисление [ править ]

Чтобы вычислить n- битный двоичный CRC, выровняйте биты, представляющие ввод, в строку и поместите ( n + 1 ) -битовый шаблон, представляющий делитель CRC (называемый « полиномом ») под левым концом строки. .

В этом примере мы закодируем 14 бит сообщения с помощью 3-битной CRC с полиномом x ³ + x + 1 . Многочлен записывается в двоичном формате как коэффициенты; многочлен 3-й степени имеет 4 коэффициента ( 1 x ³ + 0 x ² + 1 x + 1 ). В этом случае коэффициенты равны 1, 0, 1 и 1. Результат вычисления составляет 3 бита.

Начните с сообщения, которое нужно закодировать:

11010011101100

Сначала он дополняется нулями, соответствующими длине битов n CRC. Это сделано для того, чтобы полученное кодовое слово было в систематической форме. Вот первый расчет для вычисления 3-битной CRC:

11010011101100 000 <--- ввод справа, дополненный 3 битами1011 <--- делитель (4 бита) = x³ + x + 1------------------01100011101100 000 <--- результат

Алгоритм воздействует на биты непосредственно над делителем на каждом шаге. Результатом этой итерации является побитовое исключающее ИЛИ полиномиального делителя с битами над ним. Биты не выше делителя просто копируются прямо ниже для этого шага. Затем делитель сдвигается вправо, чтобы выровняться с наивысшим оставшимся 1 битом во входных данных, и процесс повторяется до тех пор, пока делитель не достигнет правого конца входной строки. Вот весь расчет:

11010011101100 000 <--- ввод справа, дополненный 3 битами1011 <--- делитель01100011101100 000 <--- результат (обратите внимание, что первые четыре бита - это XOR с делителем ниже, остальные биты не меняются) 1011 <--- делитель ...00111011101100 000 101100010111101100 000 101100000001101100 000 <--- обратите внимание, что делитель перемещается, чтобы выровняться со следующей 1 в дивиденде (поскольку частное для этого шага было равно нулю) 1011 (другими словами, он не обязательно перемещается на один бит за итерацию)00000000110100 000 101100000000011000 000 101100000000001110 000 101100000000000101 000 101 1-----------------00000000000000 100 <--- остаток (3 бита). Алгоритм деления на этом останавливается, так как дивиденд равен нулю.

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

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

11010011101100 100 <--- ввод с контрольным значением1011 <--- делитель01100011101100 100 <--- результат 1011 <--- делитель ...00111011101100 100......00000000001110 100 101100000000000101 100 101 1------------------00000000000000 000 <--- остаток

В следующем коде Python описана функция, которая будет возвращать начальный остаток CRC для выбранного ввода и полинома с 1 или 0 в качестве начального заполнения. Обратите внимание, что этот код работает со строковыми входами, а не с необработанными числами:

def  crc_remainder ( input_bitstring ,  polynomial_bitstring ,  initial_filler ):  "" "Вычислить остаток CRC строки битов с использованием выбранного полинома.  initial_filler должен быть '1' или '0'.  " ""  polynomial_bitstring  =  polynomial_bitstring . lstrip ( '0' )  len_input  =  len ( input_bitstring )  initial_padding  =  ( len ( polynomial_bitstring )  -  1 )  *  начальный_филлер input_padded_array  =  список ( input_bitstring  +  initial_padding ),  а  «1»  в  input_padded_array [: len_input ]:  cur_shift  =  input_padded_array . index ( '1' )  для  i  в  диапазоне ( len ( polynomial_bitstring )):  input_padded_array [ cur_shift  +  i ] \ =  str ( int ( polynomial_bitstring [я ]  ! =  input_padded_array [ cur_shift  +  i ]))  return  '' . присоединиться ( input_padded_array ) [ len_input :]def  crc_check ( input_bitstring ,  polynomial_bitstring ,  check_value ):  "" "Вычислить проверку CRC строки битов, используя выбранный полином." ""  polynomial_bitstring  =  polynomial_bitstring . lstrip ( '0' )  len_input  =  len ( input_bitstring )  initial_padding  =  check_value  input_padded_array  =  list ( input_bitstring  +  initial_padding ),  а  '1'  в  input_padded_array [:len_input ]:  cur_shift  =  input_padded_array . index ( '1' )  для  i  в  диапазоне ( len ( polynomial_bitstring )):  input_padded_array [ cur_shift  +  i ] \ =  str ( int ( polynomial_bitstring [ i ]  ! =  input_padded_array [ cur_shift  +  i ]))  return  ( '1'  не  в  '' .присоединиться ( input_padded_array ) [ len_input :])

>>> crc_remainder ( '11010011101100' ,  '1011' ,  '0' ) '100' >>> crc_check ( '11010011101100' ,  '1011' ,  '100' ) Истина

Алгоритм CRC-32 [ править ]

Это практический алгоритм для варианта CRC CRC-32. ^[7] CRCTable является мемоизация из расчета , что необходимо будет повторяться для каждого байта сообщения ( Вычисление проверки циклический избыточного кода § многоразрядных вычислений ).

Функция CRC32  Вход: данные: байты  // Массив байтов  Выход: crc32: UInt32  // 32-битное беззнаковое значение CRC-32 
// Инициализация CRC-32 начальным значением
crc32 ← 0xFFFFFFFF
 для каждого байта в данных do nLookupIndex ← (crc32 xor byte) и 0xFF; crc32 ← (crc32 shr 8) xor CRCTable [nLookupIndex] // CRCTable - это массив из 256 32-битных констант 
// Завершить значение CRC-32, инвертируя все битыcrc32 ← crc32 xor 0xFFFFFFFFвернуть crc32

Математика [ править ]

Математический анализ этого процесса, подобного делению, показывает, как выбрать делитель, который гарантирует хорошие свойства обнаружения ошибок. В этом анализе цифры битовых цепочек берутся в качестве коэффициентов многочлена от некоторой переменной x - коэффициентов, которые являются элементами конечного поля GF (2) , вместо более привычных чисел. Набор двоичных многочленов представляет собой математическое кольцо .

Создание многочленов [ править ]

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

Наиболее важным атрибутом полинома является его длина (наибольшая степень (показатель) +1 любого члена в полиноме) из-за его прямого влияния на длину вычисляемого контрольного значения.

Наиболее часто используемые полиномиальные длины:

• 9 бит (CRC-8)
• 17 бит (CRC-16)
• 33 бита (CRC-32)
• 65 бит (CRC-64)

CRC называется n- битной CRC, если ее контрольное значение равно n- битам. Для заданного n возможно несколько CRC, каждый с различным полиномом. Такой многочлен имеет наивысшую степень n , а значит, n + 1 член (длина многочлена n + 1 ). Остаток имеет длину n . CRC имеет имя в форме CRC- n -XXX.

Дизайн полинома CRC зависит от максимальной общей длины блока, который должен быть защищен (данные + биты CRC), желаемых функций защиты от ошибок и типа ресурсов для реализации CRC, а также желаемой производительности. Распространенное заблуждение состоит в том, что «лучшие» полиномы CRC получаются либо из неприводимых полиномов, либо из неприводимых полиномов, умноженных на множитель  1 + x , что добавляет к коду способность обнаруживать все ошибки, влияющие на нечетное количество бит. ^[8] В действительности, все факторы, описанные выше, должны входить в выбор полинома и могут привести к приводимому полиному. Однако выбор приводимого полинома приведет к определенной доле пропущенных ошибок из-за того, что фактор-кольцо имеетделители нуля .

Преимущество выбора примитивного полинома в качестве генератора для кода CRC заключается в том, что результирующий код имеет максимальную общую длину блока в том смысле, что все однобитовые ошибки в пределах этой длины блока имеют разные остатки (также называемые синдромами ), и, следовательно, поскольку остаток является линейной функцией блока, код может обнаруживать все 2-битные ошибки в пределах этой длины блока. Если - это степень полинома примитивного генератора, то максимальная общая длина блока равна , и связанный с ним код способен обнаруживать любые однобитовые или двухбитовые ошибки. ^[9] Мы можем исправить эту ситуацию. Если мы используем порождающий полином , где - примитивный полином степени${\ displaystyle r}$${\ displaystyle 2 ^ {r} -1}$${\ Displaystyle г (х) = р (1 + х)}$${\ displaystyle p}$${\ displaystyle r-1}$, то максимальная общая длина блока равна , и код может обнаруживать одиночные, двойные, тройные и любое нечетное количество ошибок.${\ displaystyle 2 ^ {r-1} -1}$

Затем может быть выбран полином, который допускает другие факторизации, чтобы сбалансировать максимальную общую длину блока с желаемой мощностью обнаружения ошибок. Эти коды БЧХ являются мощным классом таких многочленов. Они включают два приведенных выше примера. Независимо от свойств сводимости порождающего полинома степени  r , если он включает член «+1», код сможет обнаруживать шаблоны ошибок, которые ограничены окном из r смежных битов. Эти шаблоны называются «пакетами ошибок».${\ displaystyle g (x)}$

Спецификация [ править ]

Концепция CRC как кода обнаружения ошибок усложняется, когда разработчик или комитет по стандартам используют его для разработки практической системы. Вот некоторые из сложностей:

• Иногда реализация добавляет фиксированный битовый шаблон к проверяемому битовому потоку. Это полезно, когда ошибки синхронизации могут вставлять 0-биты перед сообщением, изменение, которое в противном случае оставило бы значение проверки неизменным.
• Обычно, но не всегда, реализация добавляет n 0-битов ( n - размер CRC) к потоку битов, который нужно проверить до того, как произойдет полиномиальное деление. Такое добавление явно продемонстрировано в статье « Вычисление CRC» . Это удобно тем, что остаток от исходного потока битов с добавленным контрольным значением равен нулю, поэтому CRC можно проверить, просто выполнив полиномиальное деление полученного потока битов и сравнив остаток с нулем. Благодаря ассоциативным и коммутативным свойствам операции «исключающее ИЛИ» практические реализации, управляемые таблицами, могут получить результат, численно эквивалентный добавлению нулей без явного добавления нулей, с помощью эквивалента,^[8] более быстрый алгоритм, объединяющий поток битов сообщения с потоком, смещенным из регистра CRC.
• Иногда реализация с использованием операции исключающего ИЛИ включает фиксированный битовый шаблон в остаток полиномиального деления.
• Порядок битов: в некоторых схемах младший бит каждого байта рассматривается как «первый», что во время полиномиального деления означает «крайний левый», что противоречит нашему обычному пониманию «младшего разряда». Это соглашение имеет смысл, когда передача через последовательный порт проверяется аппаратно с помощью CRC, потому что некоторые широко распространенные соглашения о передаче через последовательный порт сначала передают байты младшего разряда.
• Порядок байтов : при использовании многобайтовых CRC может возникнуть путаница в отношении того, является ли байт, переданный первым (или сохраненный в байте с наименьшим адресом памяти), младшим (LSB) или старшим (MSB) байтом. Например, некоторые 16-битные схемы CRC меняют местами байты контрольного значения.
• Пропуски бит высокого порядка дивизора полинома: Поскольку бит высокого порядка всегда равен 1, и так как п -разрядных CRC должно быть определено ап ( п + 1 ) -битных делителем , который перетекает п -разрядного регистре , некоторые авторы считают, что нет необходимости упоминать старший бит делителя.
• Пропуск младшего бита полинома делителя: поскольку младший бит всегда равен 1, такие авторы, как Филип Купман, представляют полиномы с неповрежденным старшим битом, но без младшего бита ( член или 1) . Это соглашение кодирует многочлен вместе со степенью в одно целое число.${\ displaystyle x ^ {0}}$

Эти сложности означают, что существует три распространенных способа выражения многочлена как целого числа: первые два, которые являются зеркальными изображениями в двоичном формате, представляют собой константы, обнаруженные в коде; третий - номер, найденный в бумагах Купмана. В каждом случае один член опускается. Таким образом, многочлен можно записать как:${\ displaystyle x ^ {4} + x + 1}$

• 0x3 = 0b0011, представляющий (MSB-первый код)${\ displaystyle x ^ {4} + (0x ^ {3} + 0x ^ {2} + 1x ^ {1} + 1x ^ {0})}$
• 0xC = 0b1100, представляющий (LSB-первый код)${\ displaystyle (1x ^ {0} + 1x ^ {1} + 0x ^ {2} + 0x ^ {3}) + x ^ {4}}$
• 0x9 = 0b1001, представляющий (нотация Купмана)${\ displaystyle (1x ^ {4} + 0x ^ {3} + 0x ^ {2} + 1x ^ {1}) + x ^ {0}}$

В таблице ниже они показаны как:

Обфускация [ править ]

CRC в проприетарных протоколах могут быть запутаны с помощью нетривиального начального значения и окончательного XOR, но эти методы не добавляют криптографической стойкости алгоритму и могут быть реконструированы с использованием простых методов. ^[10]

Стандарты и обычное использование [ править ]

В технические стандарты включены многочисленные разновидности циклических проверок с избыточностью . Ни в коем случае не один алгоритм или по одной каждой степени подходит для всех целей; Купман и Чакраварти рекомендуют выбирать полином в соответствии с требованиями приложения и ожидаемым распределением длин сообщений. ^[11] Количество используемых различных CRC сбивает разработчиков с толку, и авторы стремились исправить эту ситуацию. ^[8] Сообщается о трех полиномах для CRC-12, ^{[11] о} двадцати двух конфликтующих определениях CRC-16 и семи из CRC-32. ^[12]

Обычно применяемые полиномы не самые эффективные из возможных. С 1993 года Купман, Кастаньоли и другие исследовали пространство многочленов размером от 3 до 64 бит, ^{[11] [13] [14] [15],} находя примеры, которые имеют гораздо лучшую производительность (с точки зрения расстояния Хэмминга для данного размер сообщения), чем полиномы более ранних протоколов, и опубликовать лучшие из них с целью повышения способности обнаружения ошибок будущих стандартов. ^[14] В частности, iSCSI и SCTP переняли один из результатов этого исследования - полином CRC-32C (Кастаньоли).

Дизайн 32-битного многочлена CRC-32-IEEE, наиболее часто используемого органами стандартизации, стал результатом совместных усилий Римской лаборатории и Подразделения электронных систем ВВС Джозефом Хаммондом, Джеймсом Брауном и Шиан-Шианг Лю. из Технологического института Джорджии и Кеннет Брейер из Mitre Corporation . Самые ранние известные появления 32-битного полинома были в их публикациях 1975 года: Технический отчет 2956 Брайера для Mitre, опубликованный в январе и выпущенный для публичного распространения через DTIC в августе ^[16] , и отчет Хаммонда, Брауна и Лю для Римского Лаборатория, вышла в мае. ^[17]Оба отчета содержали материалы другой команды. В декабре 1975 года Брайер и Хаммонд представили свою работу в докладе на Национальной телекоммуникационной конференции IEEE: полином IEEE CRC-32 является порождающим полиномом кода Хэмминга и был выбран из-за его способности обнаруживать ошибки. ^[18] Даже в этом случае полином CRC-32C Кастаньоли, используемый в iSCSI или SCTP, соответствует своей производительности для сообщений от 58 бит до 131 кбит и превосходит его в нескольких диапазонах размеров, включая два наиболее распространенных размера Интернет-пакетов. ^[14] Стандарт ITU-T G.hn также использует CRC-32C для обнаружения ошибок в полезной нагрузке (хотя он использует CRC-16-CCITT для заголовков PHY ).

Вычисление CRC32C реализовано аппаратно как операция ( CRC32) набора инструкций SSE4.2 , впервые представленного в микроархитектуре процессоров Intel Nehalem . Операции CRC32C также определены в AArch64 .

Полиномиальные представления циклических проверок избыточности [ править ]

В таблице ниже перечислены только многочлены различных используемых алгоритмов. Варианты конкретного протокола могут налагать преинверсию, пост-инверсию и обратный порядок битов, как описано выше. Например, CRC32, используемый в Gzip и Bzip2, использует один и тот же многочлен, но Gzip использует обратный порядок битов, а Bzip2 - нет. ^[12] Обратите внимание, что четные полиномы в GF (2) со степенью больше 1 никогда не являются примитивными. Полином четности, помеченный как примитивный в этой таблице, представляет собой примитивный полином, умноженный на . Обратите внимание, что старший бит полинома всегда равен 1 и не отображается в шестнадцатеричном представлении.${\ Displaystyle \ влево (х + 1 \ вправо)}$

Имя	Использует	Полиномиальные представления				Четность [19]	Примитивный [20]	Максимальные биты полезной нагрузки по расстоянию Хэмминга [21] [14] [20]
		Нормальный	Обратный	Взаимный	Обратный взаимный			≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2 [22]
CRC-1	большая часть оборудования; также известный как бит четности	0x1	0x1	0x1	0x1	четное
		${\ displaystyle x + 1}$
CRC-3- GSM	мобильные сети [23]	0x3	0x6	0x5	0x5	странный	да [24]	-	-	-	-	-	-	-	-	-	-	-	-	-	4	∞
		${\ displaystyle x ^ {3} + x + 1}$
CRC-4-ITU	ITU-T G.704 , стр. 12	0x3	0xC	0x9	0x9	странный
		${\ displaystyle x ^ {4} + x + 1}$
CRC-5-EPC	RFID поколения 2 [25]	0x09	0x12	0x05	0x14	странный
		${\ displaystyle x ^ {5} + x ^ {3} +1}$
CRC-5-ITU	ITU-T G.704 , стр. 9	0x15	0x15	0x0B	0x1A	четное
		${\ displaystyle x ^ {5} + x ^ {4} + x ^ {2} +1}$
CRC-5-USB	Пакеты токенов USB	0x05	0x14	0x09	0x12	странный
		${\ displaystyle x ^ {5} + x ^ {2} +1}$
CRC-6- CDMA2000 -A	мобильные сети [26]	0x27	0x39	0x33	0x33	странный
CRC-6- CDMA2000 -B	мобильные сети [26]	0x07	0x38	0x31	0x23	четное
CRC-6-DARC	Радиоканал данных [27]	0x19	0x26	0x0D	0x2C	четное
CRC-6- GSM	мобильные сети [23]	0x2F	0x3D	0x3B	0x37	четное	да [28]	-	-	-	-	-	-	-	-	-	-	1	1	25	25	∞
		${\ displaystyle x ^ {6} + x ^ {5} + x ^ {3} + x ^ {2} + x + 1}$
CRC-6-ITU	ITU-T G.704 , стр. 3	0x03	0x30	0x21	0x21	странный
		${\displaystyle x^{6}+x+1}$
CRC-7	телекоммуникационные системы, ITU-T G.707 , ITU-T G.832 , MMC , SD	0x09	0x48	0x11	0x44	странный
		${\displaystyle x^{7}+x^{3}+1}$
CRC-7-MVB	Сеть связи поездов , IEC 60870-5 [29]	0x65	0x53	0x27	0x72	странный
CRC-8	DVB-S2 [30]	0xD5	0xAB	0x57	0xEA [11]	четное	нет [31]	-	-	-	-	-	-	-	-	-	-	2	2	85	85	∞
		${\displaystyle x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1}$
CRC-8- АВТОСАР	автомобильная интеграция, [32] OpenSafety [33]	0x2F	0xF4	0xE9	0x97 [11]	четное	да [31]	-	-	-	-	-	-	-	-	-	-	3	3	119	119	∞
		${\displaystyle x^{8}+x^{5}+x^{3}+x^{2}+x+1}$
CRC-8- Bluetooth	беспроводная связь [34]	0xA7	0xE5	0xCB	0xD3	четное
		${\displaystyle x^{8}+x^{7}+x^{5}+x^{2}+x+1}$
CRC-8- CCITT	МСЭ-Т I.432.1 (02/99) ; ATM HEC , ISDN HEC и разграничение ячеек, SMBus PEC	0x07	0xE0	0xC1	0x83	четное
		${\displaystyle x^{8}+x^{2}+x+1}$
CRC-8- Даллас / Максим	Шина 1-Wire [35]	0x31	0x8C	0x19	0x98	четное
		${\displaystyle x^{8}+x^{5}+x^{4}+1}$
CRC-8-DARC	Радиоканал данных [27]	0x39	0x9C	0x39	0x9C	странный
		${\displaystyle x^{8}+x^{5}+x^{4}+x^{3}+1}$
CRC-8- GSM -B	мобильные сети [23]	0x49	0x92	0x25	0xA4	четное
		${\displaystyle x^{8}+x^{6}+x^{3}+1}$
CRC-8- SAE J1850	AES3 ; OBD	0x1D	0xB8	0x71	0x8E	странный
		${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$
CRC-8- WCDMA	мобильные сети [26] [36]	0x9B	0xD9	0xB3	0xCD [11]	четное
		${\displaystyle x^{8}+x^{7}+x^{4}+x^{3}+x+1}$
CRC-10	Банкомат; ITU-T I.610	0x233	0x331	0x263	0x319	четное
		${\displaystyle x^{10}+x^{9}+x^{5}+x^{4}+x+1}$
CRC-10- CDMA2000	мобильные сети [26]	0x3D9	0x26F	0x0DF	0x3EC	четное
CRC-10- GSM	мобильные сети [23]	0x175	0x2BA	0x175	0x2BA	странный
CRC-11	FlexRay [37]	0x385	0x50E	0x21D	0x5C2	четное
		${\displaystyle x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1}$
CRC-12	телекоммуникационные системы [38] [39]	0x80F	0xF01	0xE03	0xC07 [11]	четное
		${\displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-12- CDMA2000	мобильные сети [26]	0xF13	0xC8F	0x91F	0xF89	четное
CRC-12- GSM	мобильные сети [23]	0xD31	0x8CB	0x197	0xE98	странный
CRC-13-BBC	Сигнал времени, радиотелевизор [40] [41]	0x1CF5	0x15E7	0x0BCF	0x1E7A	четное
		${\displaystyle x^{13}+x^{12}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1}$
CRC-14-DARC	Радиоканал данных [27]	0x0805	0x2804	0x1009	0x2402	четное
CRC-14- GSM	мобильные сети [23]	0x202D	0x2D01	0x1A03	0x3016	четное
CRC-15- CAN		0xC599 [42] [43]	0x4CD1	0x19A3	0x62CC	четное
		${\displaystyle x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1}$
CRC-15- MPT1327	[44]	0x6815	0x540B	0x2817	0x740A	странный
CRC-16-Chakravarty	Оптимально для полезной нагрузки ≤64 бит [29]	0x2F15	0xA8F4	0x51E9	0x978A	странный
CRC-16- ARINC	Приложения ACARS [45]	0xA02B	0xD405	0xA80B	0xD015	странный
CRC-16-CCITT	X.25 , V.41 , HDLC FCS , XMODEM , Bluetooth , PACTOR , SD , DigRF , многие другие; известный как CRC-CCITT	0x1021	0x8408	0x811	0x8810 [11]	четное
		${\displaystyle x^{16}+x^{12}+x^{5}+1}$
CRC-16- CDMA2000	мобильные сети [26]	0xC867	0xE613	0xCC27	0xE433	странный
CRC-16- DECT	беспроводные телефоны [46]	0x0589	0x91A0	0x2341	0x82C4	четное
		${\displaystyle x^{16}+x^{10}+x^{8}+x^{7}+x^{3}+1}$
CRC-16- T10 - DIF	SCSI DIF	0x8BB7 [47]	0xEDD1	0xDBA3	0xC5DB	странный
		${\displaystyle x^{16}+x^{15}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$
CRC-16- DNP	DNP, IEC 870 , M-Bus	0x3D65	0xA6BC	0x4D79	0x9EB2	четное
		${\displaystyle x^{16}+x^{13}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{2}+1}$
CRC-16- IBM	Bisync , Modbus , USB , ANSI X3.28 , SIA DC-07, многие другие; также известен как CRC-16 и CRC-16-ANSI	0x8005	0xA001	0x4003	0xC002	четное
		${\displaystyle x^{16}+x^{15}+x^{2}+1}$
CRC-16- OpenSafety -A	полевая шина безопасности [33]	0x5935	0xAC9A	0x5935	0xAC9A [11]	странный
CRC-16- OpenSafety -B	полевая шина безопасности [33]	0x755B	0xDAAE	0xB55D	0xBAAD [11]	странный
CRC-16- Profibus	сети fieldbus [48]	0x1DCF	0xF3B8	0xE771	0x8EE7	странный
Флетчер-16	Используется в контрольных суммах Adler-32 A & B	Часто путают с CRC, но на самом деле это контрольная сумма; см . контрольную сумму Флетчера
CRC-17-CAN	CAN FD [49]	0x1685B	0x1B42D	0x1685B	0x1B42D	четное
CRC-21-CAN	CAN FD [49]	0x102899	0x132281	0x064503	0x18144C	четное
CRC-24	FlexRay [37]	0x5D6DCB	0xD3B6BA	0xA76D75	0xAEB6E5	четное
		${\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}$
CRC-24- Основание-64	OpenPGP , RTCM 104v3	0x864CFB	0xDF3261	0xBE64C3	0xC3267D	четное
		${\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}$
CRC-24- WCDMA	Используется в ОСРВ ОС-9 . Остаток = 0x800FE3. [50]	0x800063	0xC60001	0x8C0003	0xC00031	четное	да [51]	-	-	-	-	-	-	-	-	-	-	4	4	8388583	8388583	∞
		${\displaystyle x^{24}+x^{23}+x^{6}+x^{5}+x+1}$
CRC-30	CDMA	0x2030B9C7	0x38E74301	0x31CE8603	0x30185CE3	четное
		${\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}$
CRC-32	ISO 3309 ( HDLC ), ANSI X3.66 ( ADCCP ), FIPS PUB 71, FED-STD-1003, ITU-T V.42 , ISO / IEC / IEEE 802-3 ( Ethernet ), SATA , MPEG-2 , PKZIP , Gzip , Bzip2 , POSIX cksum , [52] PNG , [53] ZMODEM , многие другие	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB [14]	странный	да	-	10	-	-	12	21 год	34	57	91	171	268	2974	91607	4294967263	∞
		${\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}$
CRC-32C (Кастаньоли)	iSCSI , SCTP , полезная нагрузка G.hn , SSE4.2 , Btrfs , ext4 , Ceph	0x1EDC6F41	0x82F63B78	0x05EC76F1	0x8F6E37A0 [14]	четное	да	6	-	8	-	20	-	47	-	177	-	5243	-	2147483615	-	∞
		${\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}$
CRC-32K (Купман {1,3,28})	Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами	0x741B8CD7	0xEB31D82E	0xD663B05D	0xBA0DC66B [14]	четное	нет	2	-	4	-	16	-	18	-	152	-	16360	-	114663	-	∞
		${\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}$
CRC-32K 2 (Купман {1,1,30})	Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами	0x32583499	0x992C1A4C	0x32583499	0x992C1A4C [14]	четное	нет	-	-	3	-	16	-	26	-	134	-	32738	-	65506	-	∞
CRC-32Q	авиация; AIXM [54]	0x814141AB	0xD5828281	0xAB050503	0xC0A0A0D5	четное
		${\displaystyle x^{32}+x^{31}+x^{24}+x^{22}+x^{16}+x^{14}+x^{8}+x^{7}+x^{5}+x^{3}+x+1}$
Адлер-32		Часто путают с CRC, но на самом деле это контрольная сумма; см. Адлер-32
CRC-40- GSM	Канал управления GSM [55] [56] [57]	0x0004820009	0x9000412000	0x2000824001	0x8002410004	четное
		${\displaystyle x^{40}+x^{26}+x^{23}+x^{17}+x^{3}+1=(x^{23}+1)(x^{17}+x^{3}+1)}$
CRC-64- ECMA	ECMA-182 с. 51, XZ Utils	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0x92D8AF2BAF0E1E85	0xA17870F5D4F51B49	четное
		${\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}$
CRC-64-ISO	ISO 3309 ( HDLC ), Swiss-Prot / TrEMBL ; считается слабым для хеширования [58]	0x000000000000001B	0xD800000000000000	0xB000000000000001	0x800000000000000D	странный
		${\displaystyle x^{64}+x^{4}+x^{3}+x+1}$

Реализации [ править ]

• Реализация CRC32 в Gnuradio ;
• Код класса C для вычисления контрольной суммы CRC с множеством различных CRC на выбор

Каталоги CRC [ править ]

• Каталог параметризованных алгоритмов CRC
• CRC Полиномиальный зоопарк

См. Также [ править ]

• Математика циклических проверок избыточности
• Вычисление циклических проверок избыточности
• Список хеш-функций
• Список алгоритмов контрольной суммы
• Информационная безопасность
• Простая проверка файла
• LRC

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.

Внешние ссылки [ править ]

• ISO / IEC 13239: 2002: Информационные технологии. Телекоммуникации и обмен информацией между системами. Процедуры управления каналом передачи данных высокого уровня (HDLC).
• CRC32-Castagnoli Linux библиотека