Проверка циклическим избыточностью

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

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

Введение

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

Спецификация кода 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 не совпадают, то блок содержит ошибку данных.

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

Целостность данных

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

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

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

В-третьих, CRC удовлетворяет соотношению, аналогичному соотношению линейной функции (или, точнее, аффинной функции ):

$\operatorname {CRC} (x\oplus y)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus c$

где $c$ зависит от длины $x$ и $y$. Это также можно сформулировать следующим образом, где $x$, $y$ и $z$ иметь одинаковую длину

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

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

Вычисление

Основная статья: Вычисление проверок циклическим избыточным кодом

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

В этом примере мы закодируем 14 бит сообщения с помощью 3-битного CRC с полиномом x ³ + х + 1 . Полином записывается в двоичном виде в виде коэффициентов; полином 3-й степени имеет 4 коэффициента ( 1 x ³ + 0 х ² + 1 х + 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

Математика

Основная статья: Математика циклических избыточных проверок

Математический анализ этого процесса, похожего на деление, показывает, как выбрать делитель, который гарантирует хорошие свойства обнаружения ошибок. В этом анализе цифры битовых строк принимаются как коэффициенты многочлена от некоторой переменной 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 заключается в том, что результирующий код имеет максимальную общую длину блока в том смысле, что все 1-битные ошибки в пределах этой длины блока имеют разные остатки (также называемые синдромами ), и, следовательно, поскольку остаток является линейной функцией блока, код может обнаружить все 2-битные ошибки в пределах этой длины блока. Если $r$ — степень полинома примитивного генератора, то максимальная общая длина блока равна $2^{r}-1$, а связанный с ним код способен обнаруживать любые однобитные или двухбитовые ошибки. Мы можем улучшить эту ситуацию. Если мы используем генераторный полином $g(x)=p(x)(1+x)$, где $p$ является примитивным полиномом степени $r-1$, то максимальная общая длина блока равна $2^{r-1}-1$, и код способен обнаруживать одиночные, двойные, тройные и любое нечетное количество ошибок.

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

Спецификация

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

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

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

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

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

Примеры представлений CRC

Имя	Нормальный	Перевернутый	Обратная обратная связь
КПР-4	0x3	0xC	0x9

Обфускация

CRC в частных протоколах можно запутать с помощью нетривиального начального значения и конечного 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 для обнаружения ошибок в полезной нагрузке (хотя для заголовков PHY он использует CRC-16-CCITT ).

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

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

В таблице ниже перечислены только полиномы различных используемых алгоритмов. Вариации конкретного протокола могут налагать прединверсию, постинверсию и обратный порядок битов, как описано выше. Например, CRC32, используемый в Gzip и Bzip2, использует один и тот же полином, но Gzip использует обратный порядок битов, а Bzip2 — нет. Обратите внимание, что даже полиномы четности в GF(2) со степенью больше 1 никогда не являются примитивными. Даже полином четности, помеченный как примитивный в этой таблице, представляет собой примитивный полином, умноженный на $\left(x+1\right)$. Самый старший бит многочлена всегда равен 1 и не отображается в шестнадцатеричных представлениях.

Имя	Использование	Полиномиальные представления				Паритет	Примитивный	Максимальное количество бит полезной нагрузки по расстоянию Хэмминга
		Нормальный	Перевернутый	Взаимный	Обратная обратная связь			≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2
КПР-1	большая часть аппаратного обеспечения; также известный как бит четности	0x1	0x1	0x1	0x1	даже
		$x+1$
CRC-3- GSM	мобильные сети	0x3	0x6	0x5	0x5	странный	да	–	–	–	–	–	–	–	–	–	–	–	–	–	4	∞
		$x^{3}+x+1$
CRC-4-МСЭ	МСЭ-Т G.704 , стр. 12	0x3	0xC	0x9	0x9	странный
		$x^{4}+x+1$
CRC-5-EPC	RFID 2-го поколения	0x09	0x12	0x05	0x14	странный
		$x^{5}+x^{3}+1$
CRC-5-МСЭ	ИТ-Т G.704 , с. 9	0x15	0x15	0x0B	0x1A	даже
		$x^{5}+x^{4}+x^{2}+1$
CRC-5-USB	USB- Пакеты токенов	0x05	0x14	0x09	0x12	странный
		$x^{5}+x^{2}+1$
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	∞
		$x^{6}+x^{5}+x^{3}+x^{2}+x+1$
CRC-6-МСЭ	МСЭ-Т G.704 , стр. 3.	0x03	0x30	0x21	0x21	странный
		$x^{6}+x+1$
КПР-7	телекоммуникационные системы, ITU-T G.707 , ITU-T G.832 , MMC , SD	0x09	0x48	0x11	0x44	странный
		$x^{7}+x^{3}+1$
КПР-7-МВБ	Сеть связи поездов , IEC 60870-5	0x65	0x53	0x27	0x72	странный
КПР-8	ДВБ-С2	0xD5	0xAB	0x57	0xEA	даже	нет	–	–	–	–	–	–	–	–	–	–	2	2	85	85	∞
		$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$
CRC-8- АВТОСАР	автомобильная интеграция, Открытая безопасность	0x2F	0xF4	0xE9	0x97	даже	да	–	–	–	–	–	–	–	–	–	–	3	3	119	119	∞
		$x^{8}+x^{5}+x^{3}+x^{2}+x+1$
CRC-8- Bluetooth	беспроводная связь	0xA7	0xE5	0xCB	0xD3	даже
		$x^{8}+x^{7}+x^{5}+x^{2}+x+1$
CRC-8- МККТТ	МСЭ-Т I.432.1 (02/99) ; ATM HEC , ISDN HEC и разграничение ячеек, SMBus PEC	0x07	0xE0	0xC1	0x83	даже
		$x^{8}+x^{2}+x+1$
CRC-8- Даллас / Максим	1-проводная шина	0x31	0x8C	0x19	0x98	даже
		$x^{8}+x^{5}+x^{4}+1$
CRC-8-DARC	Радиоканал данных	0x39	0x9C	0x39	0x9C	странный
		$x^{8}+x^{5}+x^{4}+x^{3}+1$
CRC-8- GSM -B	мобильные сети	0x49	0x92	0x25	0xA4	даже
		$x^{8}+x^{6}+x^{3}+1$
CRC-8- SAE J1850	АЕС3 ; ОБД	0x1D	0xB8	0x71	0x8E	странный
		$x^{8}+x^{4}+x^{3}+x^{2}+1$
CRC-8- WCDMA	мобильные сети	0x9B	0xD9	0xB3	0xCD	даже
		$x^{8}+x^{7}+x^{4}+x^{3}+x+1$
КПР-10	банкоматы; ИТ-Т I.610	0x233	0x331	0x263	0x319	даже
		$x^{10}+x^{9}+x^{5}+x^{4}+x+1$
CRC-10- CDMA2000	мобильные сети	0x3D9	0x26F	0x0DF	0x3EC	даже
CRC-10- GSM	мобильные сети	0x175	0x2BA	0x175	0x2BA	странный
КПР-11	ФлексРэй	0x385	0x50E	0x21D	0x5C2	даже
		$x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1$
КПР-12	телекоммуникационные системы	0x80F	0xF01	0xE03	0xC07	даже
		$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-12- CDMA2000	мобильные сети	0xF13	0xC8F	0x91F	0xF89	даже
CRC-12- GSM	мобильные сети	0xD31	0x8CB	0x197	0xE98	странный
CRC-13-ББК	Сигнал времени, Радиотелепереключатель	0x1CF5	0x15E7	0x0BCF	0x1E7A	даже
		$x^{13}+x^{12}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1$
CRC-14-DARC	Радиоканал данных	0x0805	0x2804	0x1009	0x2402	даже
CRC-14- GSM	мобильные сети	0x202D	0x2D01	0x1A03	0x3016	даже
CRC-15- МОЖЕТ		0xC599	0x4CD1	0x19A3	0x62CC	даже
		$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1$
CRC-15- MPT1327		0x6815	0x540B	0x2817	0x740A	странный
CRC-16-Чакраварти	Оптимально для полезных данных размером менее 64 бит.	0x2F15	0xA8F4	0x51E9	0x978A	странный
CRC-16- АРИНЦ	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	даже
		$x^{16}+x^{12}+x^{5}+1$
CRC-16- CDMA2000	мобильные сети	0xC867	0xE613	0xCC27	0xE433	странный
CRC-16- DECT	беспроводные телефоны	0x0589	0x91A0	0x2341	0x82C4	даже
		$x^{16}+x^{10}+x^{8}+x^{7}+x^{3}+1$
CRC-16- T10 - ДИФ	SCSI- ДИФ	0x8BB7	0xEDD1	0xDBA3	0xC5DB	странный
		$x^{16}+x^{15}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$
CRC-16- ДНП	ДНП, МЭК 870 , М-шина	0x3D65	0xA6BC	0x4D79	0x9EB2	даже
		$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	даже
		$x^{16}+x^{15}+x^{2}+1$
CRC-16- OpenSafety -A	полевая шина безопасности	0x5935	0xAC9A	0x5935	0xAC9A	странный
CRC-16- OpenSafety -B	полевая шина безопасности	0x755B	0xDAAE	0xB55D	0xBAAD	странный
CRC-16- Профибус	сети полевых шин	0x1DCF	0xF3B8	0xE771	0x8EE7	странный
Флетчер-16	Используется в контрольных суммах Adler-32 A и B.	Часто путают с CRC, но на самом деле это контрольная сумма; увидеть контрольную сумму Флетчера
CRC-17-КАН	CAN ФД	0x1685B	0x1B42D	0x1685B	0x1B42D	даже
CRC-21-КАН	CAN ФД	0x102899	0x132281	0x064503	0x18144C	даже
КПР-24	ФлексРэй	0x5D6DCB	0xD3B6BA	0xA76D75	0xAEB6E5	даже
		$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	даже
		$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	Используется в ОСРВ OS-9 . Остаток = 0x800FE3.	0x800063	0xC60001	0x8C0003	0xC00031	даже	да	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	∞
		$x^{24}+x^{23}+x^{6}+x^{5}+x+1$
КПР-30	CDMA	0x2030B9C7	0x38E74301	0x31CE8603	0x30185CE3	даже
		$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$
КПР-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 csum , PNG , ЗМОДЕМ и многие другие.	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB	странный	да	–	10	–	–	12	21	34	57	91	171	268	2974	91607	4294967263	∞
		$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	даже	да	6	–	8	–	20	–	47	–	177	–	5243	–	2147483615	–	∞
		$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$
КПР-32К (Купман {1,3,28})	Отличная длина кадра Ethernet, низкая производительность при работе с длинными файлами	0x741B8CD7	0xEB31D82E	0xD663B05D	0xBA0DC66B	даже	нет	2	–	4	–	16	–	18	–	152	–	16360	–	114663	–	∞
		$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$
КПР-32К 2 (Купман {1,1,30})	Отличная длина кадра Ethernet, низкая производительность при работе с длинными файлами	0x32583499	0x992C1A4C	0x32583499	0x992C1A4C	даже	нет	–	–	3	–	16	–	26	–	134	–	32738	–	65506	–	∞
CRC-32Q	авиация; AIXM	0x814141AB	0xD5828281	0xAB050503	0xC0A0A0D5	даже
		$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-канал управления	0x0004820009	0x9000412000	0x2000824001	0x8002410004	даже
		$x^{40}+x^{26}+x^{23}+x^{17}+x^{3}+1=(x^{23}+1)(x^{17}+x^{3}+1)$
CRC-64- ECMA	ЭКМА-182 с. 51, XZ Утилиты	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0x92D8AF2BAF0E1E85	0xA17870F5D4F51B49	даже
		$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}+$ $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 ; считается слабым для хеширования	0x000000000000001B	0xD800000000000000	0xB000000000000001	0x800000000000000D	странный
		$x^{64}+x^{4}+x^{3}+x+1$

Реализации

• Реализация CRC32 в GNU Radio до версии 3.6.1 (около 2012 г.)
• Код класса C для расчета контрольной суммы CRC с множеством различных CRC на выбор

CRC-каталоги

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

См. также

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

Дальнейшее чтение

• Уоррен младший, Генри С. (2013). «14. Проверка циклическим избыточностью» . Хакерское наслаждение (2-е изд.). Эддисон Уэсли . стр. 319–330. ISBN  978-0-321-84268-8 .
• Купман, Филип (2024). Понимание контрольных сумм и циклических избыточных проверок . ASIN   B0CVXWDZ99 .

Внешние ссылки

• Митра, Джубин; Наяк, Тапан (январь 2017 г.). «Реконфигурируемая архитектура VLSI (FPGA) с очень высокой пропускной способностью и малой задержкой CRC 32». Интеграция, Журнал СБИС . 56 : 1–14. дои : 10.1016/j.vlsi.2016.09.005 .
• Циклические проверки избыточности , MathPages, обзор обнаружения ошибок различных полиномов
• Уильямс, Росс (1993). «Безболезненное руководство по алгоритмам обнаружения ошибок CRC» . Архивировано из оригинала 3 сентября 2011 года . Проверено 15 августа 2011 г.
• Блэк, Ричард (1994). «Быстрая CRC32 в программном обеспечении» . Синяя книга . Группа системных исследований, Компьютерная лаборатория, Кембриджский университет. Алгоритм 4 использовался в Linux и Bzip2.
• Кунавис, М.; Берри, Ф. (2005). «Систематический подход к созданию высокопроизводительных программных генераторов CRC» (PDF) . Интел. Архивировано (PDF) из оригинала 16 декабря 2006 г. Проверено 4 февраля 2007 г. , Алгоритмы среза на 4 и 8
• Ковальк, В. (август 2006 г.). «Проверка циклическим избыточным кодом CRC, анализ и исправление ошибок» (PDF) . Университет Ольденбурга. Архивировано (PDF) из оригинала 11 июня 2007 года . Проверено 1 сентября 2006 г. — Битфильтры
• Уоррен, Генри С. младший «Проверка циклическим избыточностью» (PDF) . Хакерское удовольствие . Архивировано из оригинала (PDF) 3 мая 2015 г. — теория, практика, аппаратное и программное обеспечение с упором на CRC-32.
• Реверс-инжиниринг алгоритма CRC. Архивировано 7 августа 2011 г. на Wayback Machine.
• Кук, Грег. «Каталог параметризованных алгоритмов CRC» . CRC RevEng . Архивировано из оригинала 1 августа 2020 года . Проверено 18 сентября 2020 г.
• Купман, Фил. «Блог: Контрольная сумма и CRC Central» . - включает ссылки на PDF-файлы с 16- и 32-битными расстояниями Хэмминга CRC.
  • - (апрель 2023 г.). «Почему жизненно важные сети имеют тенденцию обеспечивать HD=6» .
• Купман, Филип; Дрисколл, Кевин; Холл, Брендан (март 2015 г.). «Код циклической избыточности и алгоритмы контрольной суммы для обеспечения целостности критически важных данных» (PDF) . Федеральное управление гражданской авиации. DOT/FAA/TC-14/49. Архивировано (PDF) из оригинала 18 мая 2015 года . Проверено 9 мая 2015 г.
• Купман, Филип (январь 2023 г.). Механика вычислений циклической избыточности - через YouTube.

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