Циклическая проверка избыточности - Cyclic redundancy check
Проверка циклическим избыточным кодом ( CRC ) является код ошибки обнаружения обычно используются в цифровых сетей и запоминающих устройств для обнаружения случайного изменения исходных данных. К блокам данных, поступающим в эти системы, прикрепляется короткое контрольное значение , основанное на остатке от полиномиального деления их содержимого. При извлечении расчет повторяется, и, если контрольные значения не совпадают, можно предпринять корректирующие действия против повреждения данных. CRC могут использоваться для исправления ошибок (см. Битовые фильтры ).
CRC называются так потому, что значение проверки (проверки данных) является избыточным (оно расширяет сообщение без добавления информации ), а алгоритм основан на циклических кодах . CRC популярны, потому что их легко реализовать в двоичном оборудовании , легко анализировать математически и особенно хорошо при обнаружении общих ошибок, вызванных шумом в каналах передачи. Поскольку значение проверки имеет фиксированную длину, функция, которая его генерирует, иногда используется как хеш-функция .
Вступление
CRC основаны на теории циклических кодов с исправлением ошибок . Использование систематических циклических кодов, которые кодируют сообщения путем добавления контрольного значения фиксированной длины, с целью обнаружения ошибок в сетях связи, было впервые предложено У. Уэсли Петерсоном в 1961 году. Циклические коды не только просты в реализации, но и имеют преимущество в том, что он особенно хорошо подходит для обнаружения пакетов ошибок : непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, поскольку пакетные ошибки являются распространенными ошибками передачи во многих каналах связи , включая магнитные и оптические запоминающие устройства. Обычно 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: она использует полином генератора n + 1 (два члена) и имеет имя CRC-1.
заявка
Устройство с поддержкой CRC вычисляет короткую двоичную последовательность фиксированной длины, известную как контрольное значение или CRC , для каждого блока данных, который должен быть отправлен или сохранен, и добавляет его к данным, образуя кодовое слово .
Когда кодовое слово принимается или считывается, устройство либо сравнивает свое контрольное значение с одним, только что вычисленным из блока данных, либо, что эквивалентно, выполняет CRC для всего кодового слова и сравнивает полученное контрольное значение с ожидаемой константой остатка .
Если значения CRC не совпадают, то блок содержит ошибку данных.
Устройство может предпринять корректирующие действия, например перечитать блок или запросить его повторную отправку. В противном случае предполагается, что данные не содержат ошибок (хотя с некоторой небольшой вероятностью они могут содержать необнаруженные ошибки; это заложено в самой природе проверки ошибок).
Целостность данных
CRC специально разработаны для защиты от распространенных типов ошибок в каналах связи, где они могут обеспечить быструю и разумную гарантию целостности доставленных сообщений. Однако они не подходят для защиты от преднамеренного изменения данных.
Во-первых, поскольку аутентификации нет, злоумышленник может отредактировать сообщение и пересчитать CRC без обнаружения подстановки. При хранении вместе с данными CRC и криптографические хеш-функции сами по себе не защищают от преднамеренного изменения данных. Любое приложение, которое требует защиты от таких атак, должно использовать криптографические механизмы аутентификации, такие как коды аутентификации сообщений или цифровые подписи (которые обычно основаны на криптографических хэш- функциях).
Во-вторых, в отличие от криптографических хеш-функций, CRC - это легко обратимая функция, что делает ее непригодной для использования в цифровых подписях.
В-третьих, CRC удовлетворяет соотношению, аналогичному соотношению линейной функции (или, точнее, аффинной функции ):
где зависит от длины и . Это также можно сформулировать следующим образом, где , и иметь одинаковую длину
в результате, даже если CRC шифруются с помощью потокового шифра , который использует XOR в качестве операции комбинирования (или режима из блочного шифра , который эффективно превращает его в потоковом шифр, такие как OFB или CFB), оба сообщений и связанный с ним CRC можно манипулировать без знания ключа шифрования; это был один из хорошо известных недостатков конструкции протокола Wired Equivalent Privacy (WEP).
Вычисление
Чтобы вычислить n- битный двоичный CRC, выровняйте биты, представляющие ввод, в строку и поместите ( n + 1 ) -битовый шаблон, представляющий делитель CRC (называемый « полиномом »), под левым концом строки.
В этом примере мы закодируем 14 бит сообщения с помощью 3-битной CRC с полиномом x 3 + x + 1 . Многочлен записывается в двоичном формате как коэффициенты; многочлен 3-й степени имеет 4 коэффициента ( 1 x 3 + 0 x 2 + 1 x + 1 ). В этом случае коэффициенты равны 1, 0, 1 и 1. Результат вычисления составляет 3 бита, поэтому он называется 3-битным CRC. Однако вам нужно 4 бита, чтобы явно указать полином.
Начните с сообщения, которое нужно закодировать:
11010011101100
Сначала он дополняется нулями, соответствующими длине бит n CRC. Это сделано для того, чтобы результирующее кодовое слово было в систематической форме. Вот первый расчет для вычисления 3-битной CRC:
11010011101100 000 <--- input right padded by 3 bits 1011 <--- divisor (4 bits) = x³ + x + 1 ------------------ 01100011101100 000 <--- result
Алгоритм воздействует на биты непосредственно над делителем на каждом шаге. Результатом этой итерации является побитовое исключающее ИЛИ полиномиального делителя с битами над ним. Биты не выше делителя просто копируются прямо ниже для этого шага. Затем делитель сдвигается вправо, чтобы выровняться с наивысшим оставшимся 1 битом на входе, и процесс повторяется до тех пор, пока делитель не достигнет правого конца входной строки. Вот весь расчет:
11010011101100 000 <--- input right padded by 3 bits 1011 <--- divisor 01100011101100 000 <--- result (note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged) 1011 <--- divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero) 1011 (in other words, it doesn't necessarily move one bit per iteration) 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <--- remainder (3 bits). Division algorithm stops here as dividend is equal to zero.
Поскольку крайний левый бит делителя обнуляет каждый входной бит, которого он касается, когда этот процесс завершается, единственными битами во входной строке, которые могут быть отличными от нуля, являются n битов в правом конце строки. Эти n битов являются остатком от шага деления, а также будут значением функции CRC (если выбранная спецификация CRC не требует некоторой постобработки).
Достоверность полученного сообщения можно легко проверить, снова выполнив вышеуказанный расчет, на этот раз с добавленным контрольным значением вместо нулей. Остаток должен быть равен нулю, если нет обнаруживаемых ошибок.
11010011101100 100 <--- input with check value 1011 <--- divisor 01100011101100 100 <--- result 1011 <--- divisor ... 00111011101100 100 ...... 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 00000000000000 000 <--- remainder
Следующий код Python описывает функцию, которая будет возвращать начальный остаток CRC для выбранного ввода и полинома с 1 или 0 в качестве начального заполнения. Обратите внимание, что этот код работает со строковыми входами, а не с необработанными числами:
def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):
"""Calculate the CRC remainder of a string of bits using a chosen polynomial.
initial_filler should be '1' or '0'.
"""
polynomial_bitstring = polynomial_bitstring.lstrip('0')
len_input = len(input_bitstring)
initial_padding = (len(polynomial_bitstring) - 1) * initial_filler
input_padded_array = list(input_bitstring + initial_padding)
while '1' in input_padded_array[:len_input]:
cur_shift = input_padded_array.index('1')
for i in range(len(polynomial_bitstring)):
input_padded_array[cur_shift + i] \
= str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
return ''.join(input_padded_array)[len_input:]
def crc_check(input_bitstring, polynomial_bitstring, check_value):
"""Calculate the CRC check of a string of bits using a chosen polynomial."""
polynomial_bitstring = polynomial_bitstring.lstrip('0')
len_input = len(input_bitstring)
initial_padding = check_value
input_padded_array = list(input_bitstring + initial_padding)
while '1' in input_padded_array[:len_input]:
cur_shift = input_padded_array.index('1')
for i in range(len(polynomial_bitstring)):
input_padded_array[cur_shift + i] \
= str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
return ('1' not in ''.join(input_padded_array)[len_input:])
>>> crc_remainder('11010011101100', '1011', '0')
'100'
>>> crc_check('11010011101100', '1011', '100')
True
CRC-32 алгоритм
Это практический алгоритм для варианта CRC CRC-32. CRCTable является мемоизация из расчета , что необходимо будет повторяться для каждого байта сообщения ( Вычисление проверки циклический избыточного кода § многоразрядных вычислений ).
Function CRC32 Input: data: Bytes // Array of bytes Output: crc32: UInt32 // 32-bit unsigned CRC-32 value
// Initialize CRC-32 to starting value crc32 ← 0xFFFFFFFF
for each byte in data do nLookupIndex ← (crc32 xor byte) and 0xFF; crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTable is an array of 256 32-bit constants
// Finalize the CRC-32 value by inverting all the bits crc32 ← crc32 xor 0xFFFFFFFF return crc32
На языке C алгоритм выглядит так:
#include <inttypes.h> // uint32_t, uint8_t
uint32_t CRC32(const uint8_t data[], size_t data_length) {
uint32_t crc32 = 0xFFFFFFFFu;
for (size_t i = 0; i < data_length; i++) {
const uint32_t lookupIndex = (crc32 ^ data[i]) & 0xff;
crc32 = (crc32 >> 8) ^ CRCTable[lookupIndex]; // CRCTable is an array of 256 32-bit constants
}
// Finalize the CRC-32 value by inverting all the bits
crc32 ^= 0xFFFFFFFFu;
return crc32;
}
Математика
Математический анализ этого процесса, похожего на деление, показывает, как выбрать делитель, который гарантирует хорошие свойства обнаружения ошибок. В этом анализе цифры битовых строк берутся в качестве коэффициентов многочлена от некоторой переменной x - коэффициентов, которые являются элементами конечного поля GF (2) (целые числа по модулю 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 , что добавляет к коду способность обнаруживать все ошибки, влияющие на нечетное количество битов. В действительности все описанные выше факторы должны входить в выбор полинома и могут привести к приводимому полиному. Однако выбор приводимого многочлена приведет к определенной доле пропущенных ошибок из-за того, что фактор-кольцо имеет делители нуля .
Преимущество выбора примитивного полинома в качестве генератора для кода CRC состоит в том, что результирующий код имеет максимальную общую длину блока в том смысле, что все однобитовые ошибки в пределах этой длины блока имеют разные остатки (также называемые синдромами ) и, следовательно, поскольку остаток является линейной функцией блока, код может обнаруживать все 2-битные ошибки в пределах этой длины блока. Если - степень полинома примитивного генератора, то максимальная общая длина блока равна , и соответствующий код способен обнаруживать любые однобитовые или двухбитовые ошибки. Мы можем исправить эту ситуацию. Если мы используем порождающий полином , где - примитивный полином степени , то максимальная общая длина блока равна , и код способен обнаруживать одиночные, двойные, тройные и любое нечетное количество ошибок.
Затем может быть выбран полином, который допускает другие факторизации, чтобы сбалансировать максимальную общую длину блока с желаемой мощностью обнаружения ошибок. Эти коды БЧХ являются мощным классом таких многочленов. Они включают два приведенных выше примера. Независимо от свойств сводимости порождающего полинома степени r , если он включает член «+1», код сможет обнаруживать шаблоны ошибок, которые ограничены окном из r смежных битов. Эти шаблоны называются «пакетами ошибок».
Технические характеристики
Концепция CRC как кода для обнаружения ошибок усложняется, когда разработчик или комитет по стандартам используют его для разработки практической системы. Вот некоторые из сложностей:
- Иногда реализация добавляет фиксированный битовый шаблон к проверяемому битовому потоку. Это полезно, когда ошибки синхронизации могут вставлять 0-биты перед сообщением, изменение, которое в противном случае оставило бы значение проверки неизменным.
- Обычно, но не всегда, реализация добавляет n 0-битов ( n - размер CRC) к потоку битов, который необходимо проверить до того, как произойдет полиномиальное деление. Такое добавление явно продемонстрировано в статье « Вычисление CRC» . Это удобно тем, что остаток от исходного потока битов с добавленным контрольным значением равен нулю, поэтому CRC можно проверить, просто выполнив полиномиальное деление полученного потока битов и сравнив остаток с нулем. Благодаря ассоциативным и коммутативным свойствам операции исключающее ИЛИ, практические реализации, управляемые таблицами, могут получить результат, численно эквивалентный добавлению нулей без явного добавления нулей, с помощью эквивалентного, более быстрого алгоритма, который объединяет поток битов сообщения с потоком сдвинут из регистра CRC.
- Иногда реализация " исключающее ИЛИ" включает фиксированный битовый шаблон в оставшуюся часть полиномиального деления.
- Порядок битов: в некоторых схемах младший бит каждого байта рассматривается как «первый», что затем во время полиномиального деления означает «крайний левый», что противоречит нашему обычному пониманию «младшего разряда». Это соглашение имеет смысл, когда передача через последовательный порт проверяется аппаратно с помощью CRC, потому что некоторые широко распространенные соглашения о передаче через последовательный порт сначала передают байты младшего разряда.
- Порядок байтов : при использовании многобайтовых CRC может возникнуть путаница в отношении того, является ли байт, переданный первым (или сохраненный в байте с наименьшим адресом памяти), младшим (LSB) или старшим (MSB) байтом. Например, некоторые 16-битные схемы CRC меняют местами байты контрольного значения.
- Пропуски бит высокого порядка дивизора полинома: Поскольку бит высокого порядка всегда равен 1, и так как п -разрядных CRC должно быть определено ап ( п + 1 ) -битных делителем , который перетекает п -разрядного регистре , некоторые авторы считают, что нет необходимости упоминать старший бит делителя.
- Отсутствие младшего бита полинома делителя: поскольку младший бит всегда равен 1, такие авторы, как Филип Купман, представляют полиномы с неповрежденным старшим битом, но без младшего бита ( член или 1). . Это соглашение кодирует многочлен вместе со степенью в одно целое число.
Эти сложности означают, что существует три распространенных способа выражения многочлена как целого числа: первые два, зеркальные изображения в двоичном формате, представляют собой константы, обнаруженные в коде; третий - номер, найденный в бумагах Купмана. В каждом случае один член опускается. Таким образом, многочлен можно записать как:
- 0x3 = 0b0011, представляющий (MSB-первый код)
- 0xC = 0b1100, представляющий (LSB-первый код)
- 0x9 = 0b1001, представляющий (обозначение Купмана)
В таблице ниже они показаны как:
Имя | Обычный | Обратный | Обратный взаимный |
---|---|---|---|
CRC-4 | 0x3 | 0xC | 0x9 |
Обфускация
ЗКИ в собственных протоколах могут быть затемненными с помощью нетривиального начального значения и окончательного XOR, но эти методы не добавляют криптостойкости к алгоритму и могут быть обратной инженерией , используя простые методы.
Стандарты и общее использование
В технические стандарты включены многочисленные разновидности циклических проверок с избыточностью . Ни в коем случае не один алгоритм или по одной каждой степени подходит для всех целей; Купман и Чакраварти рекомендуют выбирать полином в соответствии с требованиями приложения и ожидаемым распределением длин сообщений. Количество используемых различных CRC сбивает разработчиков с толку, и авторы стремились исправить эту ситуацию. Сообщается о трех полиномах для CRC-12, о двадцати двух конфликтующих определениях CRC-16 и о семи для CRC-32.
Обычно применяемые полиномы не самые эффективные из возможных. С 1993 года Купман, Кастаньоли и другие исследовали пространство многочленов размером от 3 до 64 бит, найдя примеры, которые имеют гораздо лучшую производительность (с точки зрения расстояния Хэмминга для данного размера сообщения), чем многочлены более ранних протоколов, и опубликовали лучшие из них с целью улучшения способности обнаружения ошибок будущих стандартов. В частности, iSCSI и SCTP приняли один из результатов этого исследования - полином CRC-32C (Кастаньоли).
Дизайн 32-битного многочлена CRC-32-IEEE, наиболее часто используемого органами стандартизации, был результатом совместных усилий Римской лаборатории и Подразделения электронных систем ВВС Джозефом Хаммондом, Джеймсом Брауном и Шиан-Шианг Лю. из Технологического института Джорджии и Кеннет Брейер из Mitre Corporation . Самые ранние известные появления 32-битного полинома были в их публикациях 1975 года: Технический отчет 2956 Брайера для Mitre, опубликованный в январе и выпущенный для публичного распространения через DTIC в августе, и отчет Хаммонда, Брауна и Лю для Римской лаборатории, опубликованный в мае. Оба отчета содержали материалы другой команды. В декабре 1975 года Брайер и Хаммонд представили свою работу в докладе на Национальной конференции по телекоммуникациям IEEE: полином IEEE CRC-32 является порождающим полиномом кода Хэмминга и был выбран из-за его способности обнаруживать ошибки. Даже в этом случае полином CRC-32C Кастаньоли, используемый в iSCSI или SCTP, соответствует своей производительности для сообщений от 58 бит до 131 кбит и превосходит его в нескольких диапазонах размеров, включая два наиболее распространенных размера Интернет-пакетов. Стандарт ITU-T G.hn также использует CRC-32C для обнаружения ошибок в полезной нагрузке (хотя он использует CRC-16-CCITT для заголовков PHY ).
Вычисление CRC-32C реализовано аппаратно как операция ( CRC32
) набора инструкций SSE4.2 , впервые представленного в микроархитектуре процессоров Intel Nehalem . Архитектура ARM AArch64 также обеспечивает аппаратное ускорение для операций CRC-32 и CRC-32C.
Полиномиальные представления циклических проверок избыточности
В таблице ниже перечислены только полиномы различных используемых алгоритмов. Варианты конкретного протокола могут налагать преинверсию, постинверсию и обратный порядок битов, как описано выше. Например, CRC32, используемый в Gzip и Bzip2, использует один и тот же многочлен, но Gzip использует обратный порядок битов, а Bzip2 - нет. Обратите внимание, что полиномы четности в GF (2) со степенью больше 1 никогда не являются примитивными. Полином четности, помеченный как примитивный в этой таблице, представляет собой примитивный полином, умноженный на . Самый старший бит полинома всегда равен 1 и не отображается в шестнадцатеричном представлении.
Имя | Использует | Полиномиальные представления | Паритет | Примитивный | Максимальные биты полезной нагрузки по расстоянию Хэмминга | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Обычный | Обратный | Взаимный | Обратный взаимный | ≥ 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | ||||
CRC-1 | большая часть оборудования; также известный как бит четности | 0x1 | 0x1 | 0x1 | 0x1 | даже | ||||||||||||||||
CRC-3- GSM | мобильные сети | 0x3 | 0x6 | 0x5 | 0x5 | странный | да | - | - | - | - | - | - | - | - | - | - | - | - | - | 4 | ∞ |
CRC-4-ITU | ITU-T G.704 , стр. 12 | 0x3 | 0xC | 0x9 | 0x9 | странный | ||||||||||||||||
CRC-5-EPC | RFID поколения 2 | 0x09 | 0x12 | 0x05 | 0x14 | странный | ||||||||||||||||
CRC-5-ITU | ITU-T G.704 , стр. 9 | 0x15 | 0x15 | 0x0B | 0x1A | даже | ||||||||||||||||
CRC-5-USB | Пакеты USB- токенов | 0x05 | 0x14 | 0x09 | 0x12 | странный | ||||||||||||||||
CRC-6- CDMA2000 -A | мобильные сети | 0x27 | 0x39 | 0x33 | 0x33 | странный | ||||||||||||||||
CRC-6- CDMA2000 -B | мобильные сети | 0x07 | 0x38 | 0x31 | 0x23 | даже | ||||||||||||||||
CRC-6-DARC | Радиоканал данных | 0x19 | 0x26 | 0x0D | 0x2C | даже | ||||||||||||||||
CRC-6- GSM | мобильные сети | 0x2F | 0x3D | 0x3B | 0x37 | даже | да | - | - | - | - | - | - | - | - | - | - | 1 | 1 | 25 | 25 | ∞ |
CRC-6-ITU | ITU-T G.704 , стр. 3 | 0x03 | 0x30 | 0x21 | 0x21 | странный | ||||||||||||||||
CRC-7 | телекоммуникационные системы, ITU-T G.707 , ITU-T G.832 , MMC , SD | 0x09 | 0x48 | 0x11 | 0x44 | странный | ||||||||||||||||
CRC-7-MVB | Сеть связи поездов , IEC 60870-5 | 0x65 | 0x53 | 0x27 | 0x72 | странный | ||||||||||||||||
CRC-8 | DVB-S2 | 0xD5 | 0xAB | 0x57 | 0xEA | даже | нет | - | - | - | - | - | - | - | - | - | - | 2 | 2 | 85 | 85 | ∞ |
CRC-8- АВТОСАР | автомобильная интеграция, OpenSafety | 0x2F | 0xF4 | 0xE9 | 0x97 | даже | да | - | - | - | - | - | - | - | - | - | - | 3 | 3 | 119 | 119 | ∞ |
CRC-8- Bluetooth | беспроводная связь | 0xA7 | 0xE5 | 0xCB | 0xD3 | даже | ||||||||||||||||
CRC-8- CCITT | МСЭ-Т I.432.1 (02/99) ; ATM HEC , ISDN HEC и разграничение ячеек, SMBus PEC | 0x07 | 0xE0 | 0xC1 | 0x83 | даже | ||||||||||||||||
CRC-8- Даллас / Максим | Шина 1-Wire | 0x31 | 0x8C | 0x19 | 0x98 | даже | ||||||||||||||||
CRC-8-DARC | Радиоканал данных | 0x39 | 0x9C | 0x39 | 0x9C | странный | ||||||||||||||||
CRC-8- GSM -B | мобильные сети | 0x49 | 0x92 | 0x25 | 0xA4 | даже | ||||||||||||||||
CRC-8- SAE J1850 | AES3 ; OBD | 0x1D | 0xB8 | 0x71 | 0x8E | странный | ||||||||||||||||
CRC-8- WCDMA | мобильные сети | 0x9B | 0xD9 | 0xB3 | 0xCD | даже | ||||||||||||||||
CRC-10 | Банкомат; ITU-T I.610 | 0x233 | 0x331 | 0x263 | 0x319 | даже | ||||||||||||||||
CRC-10- CDMA2000 | мобильные сети | 0x3D9 | 0x26F | 0x0DF | 0x3EC | даже | ||||||||||||||||
CRC-10- GSM | мобильные сети | 0x175 | 0x2BA | 0x175 | 0x2BA | странный | ||||||||||||||||
CRC-11 | FlexRay | 0x385 | 0x50E | 0x21D | 0x5C2 | даже | ||||||||||||||||
CRC-12 | телекоммуникационные системы | 0x80F | 0xF01 | 0xE03 | 0xC07 | даже | ||||||||||||||||
CRC-12- CDMA2000 | мобильные сети | 0xF13 | 0xC8F | 0x91F | 0xF89 | даже | ||||||||||||||||
CRC-12- GSM | мобильные сети | 0xD31 | 0x8CB | 0x197 | 0xE98 | странный | ||||||||||||||||
CRC-13-BBC | Сигнал времени, Радиотелевизионный переключатель | 0x1CF5 | 0x15E7 | 0x0BCF | 0x1E7A | даже | ||||||||||||||||
CRC-14-DARC | Радиоканал данных | 0x0805 | 0x2804 | 0x1009 | 0x2402 | даже | ||||||||||||||||
CRC-14- GSM | мобильные сети | 0x202D | 0x2D01 | 0x1A03 | 0x3016 | даже | ||||||||||||||||
CRC-15- CAN | 0xC599 | 0x4CD1 | 0x19A3 | 0x62CC | даже | |||||||||||||||||
CRC-15- MPT1327 | 0x6815 | 0x540B | 0x2817 | 0x740A | странный | |||||||||||||||||
CRC-16-Chakravarty | Оптимально для полезной нагрузки ≤64 бит | 0x2F15 | 0xA8F4 | 0x51E9 | 0x978A | странный | ||||||||||||||||
CRC-16- ARINC | Приложения ACARS | 0xA02B | 0xD405 | 0xA80B | 0xD015 | странный | ||||||||||||||||
CRC-16-CCITT | X.25 , V.41 , HDLC FCS , XMODEM , Bluetooth , PACTOR , SD , DigRF , многие другие; известный как CRC-CCITT | 0x1021 | 0x8408 | 0x811 | 0x8810 | даже | ||||||||||||||||
CRC-16- CDMA2000 | мобильные сети | 0xC867 | 0xE613 | 0xCC27 | 0xE433 | странный | ||||||||||||||||
CRC-16- DECT | беспроводные телефоны | 0x0589 | 0x91A0 | 0x2341 | 0x82C4 | даже | ||||||||||||||||
CRC-16- T10 - DIF | SCSI DIF | 0x8BB7 | 0xEDD1 | 0xDBA3 | 0xC5DB | странный | ||||||||||||||||
CRC-16- DNP | DNP, IEC 870 , M-Bus | 0x3D65 | 0xA6BC | 0x4D79 | 0x9EB2 | даже | ||||||||||||||||
CRC-16- IBM | Bisync , Modbus , USB , ANSI X3.28 , SIA DC-07, многие другие; также известен как CRC-16 и CRC-16-ANSI | 0x8005 | 0xA001 | 0x4003 | 0xC002 | даже | ||||||||||||||||
CRC-16- OpenSafety -A | полевая шина безопасности | 0x5935 | 0xAC9A | 0x5935 | 0xAC9A | странный | ||||||||||||||||
CRC-16- OpenSafety -B | полевая шина безопасности | 0x755B | 0xDAAE | 0xB55D | 0xBAAD | странный | ||||||||||||||||
CRC-16- Profibus | сети fieldbus | 0x1DCF | 0xF3B8 | 0xE771 | 0x8EE7 | странный | ||||||||||||||||
Флетчер-16 | Используется в контрольных суммах Adler-32 A & B | Часто путают с CRC, но на самом деле это контрольная сумма; см . контрольную сумму Флетчера | ||||||||||||||||||||
CRC-17-CAN | CAN FD | 0x1685B | 0x1B42D | 0x1685B | 0x1B42D | даже | ||||||||||||||||
CRC-21-CAN | CAN FD | 0x102899 | 0x132281 | 0x064503 | 0x18144C | даже | ||||||||||||||||
CRC-24 | FlexRay | 0x5D6DCB | 0xD3B6BA | 0xA76D75 | 0xAEB6E5 | даже | ||||||||||||||||
CRC-24- Основание-64 | OpenPGP , RTCM 104v3 | 0x864CFB | 0xDF3261 | 0xBE64C3 | 0xC3267D | даже | ||||||||||||||||
CRC-24- WCDMA | Используется в ОСРВ OS-9 . Остаток = 0x800FE3. | 0x800063 | 0xC60001 | 0x8C0003 | 0xC00031 | даже | да | - | - | - | - | - | - | - | - | - | - | 4 | 4 | 8388583 | 8388583 | ∞ |
CRC-30 | CDMA | 0x2030B9C7 | 0x38E74301 | 0x31CE8603 | 0x30185CE3 | даже | ||||||||||||||||
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 , PNG , ZMODEM , многие другие | 0x04C11DB7 | 0xEDB88320 | 0xDB710641 | 0x82608EDB | странный | да | - | 10 | - | - | 12 | 21 год | 34 | 57 | 91 | 171 | 268 | 2974 | 91607 | 4294967263 | ∞ |
CRC-32C (Кастаньоли) | iSCSI , SCTP , полезная нагрузка G.hn , SSE4.2 , Btrfs , ext4 , Ceph | 0x1EDC6F41 | 0x82F63B78 | 0x05EC76F1 | 0x8F6E37A0 | даже | да | 6 | - | 8 | - | 20 | - | 47 | - | 177 | - | 5243 | - | 2147483615 | - | ∞ |
CRC-32K (Купман {1,3,28}) | Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами | 0x741B8CD7 | 0xEB31D82E | 0xD663B05D | 0xBA0DC66B | даже | нет | 2 | - | 4 | - | 16 | - | 18 | - | 152 | - | 16360 | - | 114663 | - | ∞ |
CRC-32K 2 (Купман {1,1,30}) | Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами | 0x32583499 | 0x992C1A4C | 0x32583499 | 0x992C1A4C | даже | нет | - | - | 3 | - | 16 | - | 26 год | - | 134 | - | 32738 | - | 65506 | - | ∞ |
CRC-32Q | авиация; AIXM | 0x814141AB | 0xD5828281 | 0xAB050503 | 0xC0A0A0D5 | даже | ||||||||||||||||
Адлер-32 | Часто путают с CRC, но на самом деле это контрольная сумма; см. Адлер-32 | |||||||||||||||||||||
CRC-40- GSM | Канал управления GSM | 0x0004820009 | 0x9000412000 | 0x2000824001 | 0x8002410004 | даже | ||||||||||||||||
CRC-64- ECMA | ECMA-182 стр. 51, XZ Utils | 0x42F0E1EBA9EA3693 | 0xC96C5795D7870F42 | 0x92D8AF2BAF0E1E85 | 0xA17870F5D4F51B49 | даже | ||||||||||||||||
CRC-64-ISO | ISO 3309 ( HDLC ), Swiss-Prot / TrEMBL ; считается слабым для хеширования | 0x000000000000001B | 0xD800000000000000 | 0xB000000000000001 | 0x800000000000000D | странный | ||||||||||||||||
Реализации
- Реализация CRC32 в GNU Radio до версии 3.6.1 (примерно 2012 г.)
- Код класса C для вычисления контрольной суммы CRC с множеством различных CRC на выбор
Каталоги CRC
Смотрите также
- Математика циклических проверок избыточности
- Вычисление циклических проверок избыточности
- Список хеш-функций
- Список алгоритмов контрольной суммы
- Информационная безопасность
- Простая проверка файла
- LRC
использованная литература
дальнейшее чтение
- Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc. 978-0-321-84268-8.
внешние ссылки
- Митра, Джубин; Наяк, Тапан (январь 2017 г.). «Реконфигурируемая архитектура CRC 32 VLSI (FPGA) с очень высокой пропускной способностью и малой задержкой». Интеграция, Журнал СБИС . 56 : 1–14. DOI : 10.1016 / j.vlsi.2016.09.005 .
- Циклические проверки избыточности , MathPages, обзор обнаружения ошибок различных полиномов
- Уильямс, Росс (1993). «Безболезненное руководство по алгоритмам обнаружения ошибок CRC» . Архивировано из оригинального 3 -го сентября 2011 года . Проверено 15 августа 2011 года .
- Блэк, Ричард (1994). «Быстрый CRC32 в программном обеспечении» . Синяя книга . Группа системных исследований, Компьютерная лаборатория, Кембриджский университет. Алгоритм 4 использовался в Linux и Bzip2.
- Kounavis, M .; Берри, Ф. (2005). «Системный подход к созданию высокопроизводительных программных генераторов CRC» (PDF) . Intel., Алгоритмы нарезки на 4 и на 8 единиц
- Ковальк, В. (август 2006 г.). «CRC Cyclic Redundancy Check, анализ и исправление ошибок» (PDF) . Университет Ольденбурга. - Битовые фильтры
- Уоррен, Генри С., младший «Циклическая проверка избыточности» (PDF) . Хакерское наслаждение . Архивировано 3 мая 2015 года из оригинального (PDF) . - теория, практика, оборудование и программное обеспечение с упором на CRC-32.
- Обратное проектирование алгоритма CRC
- Повар, Грег. «Каталог параметризованных алгоритмов CRC» . CRC RevEng .
- Купман, Фил. «Блог: Контрольная сумма и CRC Central» .- включает ссылки на PDF-файлы, содержащие 16- и 32-битные CRC- расстояния Хэмминга
- Купман, Филипп; Дрисколл, Кевин; Холл, Брендан (март 2015 г.). «Циклический код избыточности и алгоритмы контрольной суммы для обеспечения критической целостности данных» (PDF) . Федеральная авиационная администрация. DOT / FAA / TC-14/49.