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

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

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

CRC был изобретен В. Уэсли Петерсон в 1961 г .; 32-битная функция CRC, используемая в Ethernet и многих других стандартах, является результатом работы нескольких исследователей и была опубликована в 1975 году.

Вступление

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

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

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

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

Вычисление

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

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

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

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

11010011101100

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

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

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

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

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

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

11010011101100 100 <--- ввод с контрольным значением 1011 <--- делитель 01100011101100 100 <--- результат 1011 <--- делитель ... 00111011101100 100 ...... 00000000001110 100 101100000000000101 100101 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 = initial_filler * (len(polynomial_bitstring) - 1)    input_padded_array = список(input_bitstring + initial_padding)    пока '1' в input_padded_array[:len_input]:        cur_shift = input_padded_array.индекс('1')        за я в классифицировать(len(polynomial_bitstring)):            input_padded_array[cur_shift + я] = ул.(int(polynomial_bitstring[я] != input_padded_array[cur_shift + я]))    возвращаться ''.присоединиться(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 = список(input_bitstring + initial_padding)    пока '1' в input_padded_array[:len_input]:        cur_shift = input_padded_array.индекс('1')        за я в классифицировать(len(polynomial_bitstring)):            input_padded_array[cur_shift + я] = ул.(int(polynomial_bitstring[я] != input_padded_array[cur_shift + я]))    возвращаться ('1' нет в ''.присоединиться(input_padded_array)[len_input:])
>>> crc_check('11010011101100','1011','100')Истинный>>> crc_remainder('11010011101100','1011','0')'100'

CRC-32 алгоритм

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

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

Математика

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

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

Разработка многочленов

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

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

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

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

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

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

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

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

Технические характеристики

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

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

Эти сложности означают, что есть три общих способа выразить многочлен как целое число: первые два, которые являются зеркальными изображениями в двоичном формате, представляют собой константы, найденные в коде; третий - номер, найденный в бумагах Купмана. В каждом случае один член опускается. Итак, многочлен можно записать как:

  • 0x3 = 0b0011, представляющий (MSB-первый код)
  • 0xC = 0b1100, представляющий (LSB-первый код)
  • 0x9 = 0b1001, представляющий (Обозначения Купмана)

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

Примеры представлений CRC
ИмяНормальныйОбратныйОбратный взаимный
CRC-40x30xC0x9

Запутывание

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 никогда не бывают примитивными. Полином четности, помеченный как примитивный в этой таблице, представляет собой примитивный полином, умноженный на .

ИмяИспользуетПолиномиальные представленияПаритет[19]Примитивный[20]Максимальные биты полезной нагрузки на Расстояние Хэмминга[21][14][20]
НормальныйОбратныйВзаимныйОбратный взаимный≥ 1615141312111098765432[22]
CRC-1большая часть оборудования; также известный как бит четности0x10x10x10x1четное
CRC-3-GSMмобильные сети[23]0x30x60x50x5странныйда [24]–––––––––––––4∞
CRC-4-ITUITU-T G.704, п. 120x30xC0x90x9странный
CRC-5-EPCRFID поколения 2[25]0x090x120x050x14странный
CRC-5-ITUITU-T G.704, п. 90x150x150x0B0x1Aчетное
CRC-5-USBUSB токен-пакеты0x050x140x090x12странный
CRC-6-CDMA2000 -Амобильные сети[26]0x270x390x330x33странный
CRC-6-CDMA2000 -Bмобильные сети[26]0x070x380x310x23четное
CRC-6-DARCРадиоканал данных[27]0x190x260x0D0x2Cчетное
CRC-6-GSMмобильные сети[23]0x2F0x3D0x3B0x37четноеда [28]––––––––––112525∞
CRC-6-ITUITU-T G.704, п. 30x030x300x210x21странный
CRC-7телекоммуникационные системы, ITU-T G.707, ITU-T G.832, MMC, SD0x090x480x110x44странный
CRC-7-MVBСеть связи поездов, IEC 60870-5[29]0x650x530x270x72странный
CRC-8DVB-S2[30]0xD50xAB0x570xEA[11]четноенет [31]––––––––––228585∞
CRC-8-АВТОСАРавтомобильная интеграция,[32] OpenSafety[33]0x2F0xF40xE90x97[11]четноеда [31]––––––––––33119119∞
CRC-8-Bluetoothбеспроводная связь[34]0xA70xE50xCB0xD3четное
CRC-8-CCITTITU-T I.432.1 (02/99); Банкомат HEC, ISDN HEC и разграничение клеток, SMBus PEC0x070xE00xC10x83четное
CRC-8-Даллас /Максим1-Wire автобус[35]0x310x8C0x190x98четное
CRC-8-DARCРадиоканал данных[27]0x390x9C0x390x9Cстранный
CRC-8-GSM -Bмобильные сети[23]0x490x920x250xA4четное
CRC-8-SAE J1850AES3; OBD0x1D0xB80x710x8Eстранный
CRC-8-WCDMAмобильные сети[26][36]0x9B0xD90xB30xCD[11]четное
CRC-10Банкомат; ITU-T I.6100x2330x3310x2630x319четное
CRC-10-CDMA2000мобильные сети[26]0x3D90x26F0x0DF0x3ECчетное
CRC-10-GSMмобильные сети[23]0x1750x2BA0x1750x2BAстранный
CRC-11FlexRay[37]0x3850x50E0x21D0x5C2четное
CRC-12телекоммуникационные системы[38][39]0x80F0xF010xE030xC07[11]четное
CRC-12-CDMA2000мобильные сети[26]0xF130xC8F0x91F0xF89четное
CRC-12-GSMмобильные сети[23]0xD310x8CB0x1970xE98странный
CRC-13-BBCСигнал времени, Радиотелевизор[40][41]0x1CF50x15E70x0BCF0x1E7Aчетное
CRC-14-DARCРадиоканал данных[27]0x08050x28040x10090x2402четное
CRC-14-GSMмобильные сети[23]0x202D0x2D010x1A030x3016четное
CRC-15-МОЖЕТ0xC599[42][43]0x4CD10x19A30x62CCчетное
CRC-15-MPT1327[44]0x68150x540B0x28170x740Aстранный
CRC-16-ChakravartyОптимально для полезной нагрузки ≤64 бит[29]0x2F150xA8F40x51E90x978Aстранный
CRC-16-ARINCACARS Приложения[45]0xA02B0xD4050xA80B0xD015странный
CRC-16-CCITTX.25, V.41, HDLC FCS, XMODEM, Bluetooth, PACTOR, SD, DigRF, многие другие; известный как CRC-CCITT0x10210x84080x8110x8810[11]четное
CRC-16-CDMA2000мобильные сети[26]0xC8670xE6130xCC270xE433странный
CRC-16-DECTбеспроводные телефоны[46]0x05890x91A00x23410x82C4четное
CRC-16-T10 -DIFSCSI DIF0x8BB7[47]0xEDD10xDBA30xC5DBстранный
CRC-16-DNPDNP, IEC 870, M-автобус0x3D650xA6BC0x4D790x9EB2четное
CRC-16-IBMBisync, Modbus, USB, ANSI X3.28, SIA DC-07, многие другие; также известный как CRC-16 и CRC-16-ANSI0x80050xA0010x40030xC002четное
CRC-16-OpenSafety -Аполевая шина безопасности[33]0x59350xAC9A0x59350xAC9A[11]странный
CRC-16-OpenSafety -Bполевая шина безопасности[33]0x755B0xDAAE0xB55D0xBAAD[11]странный
CRC-16-Profibusсети fieldbus[48]0x1DCF0xF3B80xE7710x8EE7странный
Флетчер-16Используется в Адлер-32 Контрольные суммы A и BЧасто путают с CRC, но на самом деле это контрольная сумма; видеть Контрольная сумма Флетчера
CRC-17-CANCAN FD[49]0x1685B0x1B42D0x1685B0x1B42Dчетное
CRC-21-CANCAN FD[49]0x1028990x1322810x0645030x18144Cчетное
CRC-24FlexRay[37]0x5D6DCB0xD3B6BA0xA76D750xAEB6E5четное
CRC-24-Радикс-64OpenPGP, RTCM 104v30x864CFB0xDF32610xBE64C30xC3267Dчетное
CRC-24-WCDMAИспользуется в ОС-9 ОСРВ. Остаток = 0x800FE3.[50]0x8000630xC600010x8C00030xC00031четноеда[51]––––––––––4483885838388583∞
CRC-30CDMA0x2030B9C70x38E743010x31CE86030x30185CE3четное
CRC-32ISO 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, многие другие0x04C11DB70xEDB883200xDB7106410x82608EDB[14]странныйда–10––12213457911712682974916074294967263∞
CRC-32C (Кастаньоли)iSCSI, SCTP, G.hn полезная нагрузка SSE4.2, Btrfs, ext4, Ceph0x1EDC6F410x82F63B780x05EC76F10x8F6E37A0[14]четноеда6–8–20–47–177–5243–2147483615–∞
CRC-32K (Купман {1,3,28})Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами0x741B8CD70xEB31D82E0xD663B05D0xBA0DC66B[14]четноенет2–4–16–18–152–16360–114663–∞
CRC-32K2 (Купман {1,1,30})Отлично при длине кадра Ethernet, низкая производительность при работе с длинными файлами0x325834990x992C1A4C0x325834990x992C1A4C[14]четноенет––3–16–26–134–32738–65506–∞
CRC-32Qавиация; AIXM[54]0x814141AB0xD58282810xAB0505030xC0A0A0D5четное
Адлер-32Часто путают с CRC, но на самом деле это контрольная сумма; видеть Адлер-32
CRC-40-GSMКанал управления GSM[55][56][57]0x00048200090x90004120000x20008240010x8002410004четное
CRC-64-ECMAECMA-182 п. 51, XZ Utils0x42F0E1EBA9EA36930xC96C5795D7870F420x92D8AF2BAF0E1E850xA17870F5D4F51B49четное
CRC-64-ISOISO 3309 (HDLC ), Swiss-Prot /TrEMBL; считается слабым для хеширования[58]0x000000000000001B0xD8000000000000000xB0000000000000010x800000000000000Dстранный

Реализации

Каталоги CRC

Смотрите также

Рекомендации

  1. ^ «Алгоритм исправления ошибок циклических проверок избыточности». drdobbs.com. Архивировано из оригинал 20 июля 2017 г.. Получено 28 июн 2017.
  2. ^ Peterson, W. W .; Браун, Д. Т. (январь 1961 г.). «Циклические коды для обнаружения ошибок». Труды IRE. 49 (1): 228–235. Дои:10.1109 / JRPROC.1961.287814. S2CID  51666741.
  3. ^ Риттер, Терри (февраль 1986). "Великая тайна КПР". Журнал доктора Добба. 11 (2): 26–34, 76–83. Получено 21 мая 2009.
  4. ^ Стигге, Мартин; Плётц, Хенрик; Мюллер, Вольф; Редлих, Йенс-Петер (май 2006 г.). «Обращение CRC вспять - теория и практика» (PDF). Берлин: Университет Гумбольдта в Берлине: 17. Архивировано из оригинал (PDF) 19 июля 2011 г.. Получено 4 февраля 2011. Представленные методы предлагают очень простой и эффективный способ изменить ваши данные, чтобы они вычисляли CRC, который вы хотите или, по крайней мере, знаете заранее. Цитировать журнал требует | журнал = (помощь)
  5. ^ «Дизайн алгоритма - Почему CRC называется линейным?». Обмен криптографическим стеком. Получено 5 мая 2019.
  6. ^ Кам-Вингет, Нэнси; Хаусли, Расс; Вагнер, Давид; Уокер, Джесси (май 2003 г.). «Недостатки безопасности в протоколах передачи данных 802.11» (PDF). Коммуникации ACM. 46 (5): 35–39. CiteSeerX  10.1.1.14.8775. Дои:10.1145/769800.769823. S2CID  3132937.
  7. ^ «[MS-ABS]: 32-битный алгоритм CRC». msdn.microsoft.com.
  8. ^ а б c Уильямс, Росс Н. (24 сентября 1996 г.). "Безболезненное руководство по алгоритмам обнаружения ошибок CRC V3.0". Архивировано из оригинал 2 апреля 2018 г.. Получено 23 мая 2019.
  9. ^ Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 22.4 Циклическое резервирование и другие контрольные суммы». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
  10. ^ Юинг, Грегори С. (март 2010 г.). "Обратное проектирование алгоритма CRC". Крайстчерч: Кентерберийский университет. Получено 26 июля 2011.
  11. ^ а б c d е ж грамм час я j Купман, Филипп; Чакраварти, Тридиб (июнь 2004 г.). Выбор полинома циклического избыточного кода (CRC) для встроенных сетей (PDF). Международная конференция по надежным системам и сетям. С. 145–154. CiteSeerX  10.1.1.648.9080. Дои:10.1109 / DSN.2004.1311885. ISBN  978-0-7695-2052-0. S2CID  793862. Получено 14 января 2011.
  12. ^ а б Кук, Грег (15 августа 2020 г.). «Каталог параметризованных алгоритмов CRC». Получено 18 сентября 2020.
  13. ^ Castagnoli, G .; Bräuer, S .; Херрманн, М. (июнь 1993 г.). «Оптимизация циклических кодов проверки избыточности с 24 и 32 битами четности». Транзакции IEEE по коммуникациям. 41 (6): 883–892. Дои:10.1109/26.231911.
  14. ^ а б c d е ж грамм час Купман, Филипп (июль 2002 г.). «32-битные циклические коды избыточности для Интернет-приложений». Труды Международной конференции по надежным системам и сетям (PDF). Международная конференция по надежным системам и сетям. С. 459–468. CiteSeerX  10.1.1.11.8323. Дои:10.1109 / DSN.2002.1028931. ISBN  978-0-7695-1597-7. S2CID  14775606. Получено 14 января 2011.
  15. ^ Купман, Филипп (21 января 2016 г.). «Лучшие полиномы CRC». Питтсбург: Университет Карнеги-Меллона. Получено 26 января 2016.
  16. ^ Брейер, Кеннет (август 1975). «Оценка полиномов 32 градусов при обнаружении ошибок на шаблонах ошибок SATIN IV Autovon». Национальная служба технической информации: 74. Получено 3 февраля 2011. Цитировать журнал требует | журнал = (помощь)[постоянная мертвая ссылка ]
  17. ^ Хаммонд, Джозеф Л., младший; Браун, Джеймс Э .; Лю, Шянь-Шианг (1975). «Разработка модели ошибок передачи и модели контроля ошибок» (PDF). Технический отчет NASA Sti / Recon N (опубликовано в мае 1975 г.). 76: 74. Bibcode:1975STIN ... 7615344H. Получено 7 июля 2012.
  18. ^ Брейер, Кеннет; Хаммонд, Джозеф Л. младший (декабрь 1975 г.). «Оценка работы полинома обнаружения ошибок на канале АВТОВОН». Запись конференции. Национальная конференция по телекоммуникациям IEEE, Новый Орлеан, штат Луизиана. 1. Нью-Йорк: Институт инженеров по электротехнике и электронике. С. 8–21–8–25. Bibcode:1975нтк ..... 1 .... 8Б.
  19. ^ CRC с четностью обнаруживают любое нечетное количество битовых ошибок за счет меньшего расстояния Хэмминга для длинных полезных данных. Обратите внимание, что четность вычисляется по всему полиному генератора, включая подразумеваемую 1 в начале или в конце. Например, полное представление CRC-1 - 0x3, которое имеет два бита 1. Таким образом, его соотношение четное.
  20. ^ а б "32-битный зоопарк CRC". users.ece.cmu.edu.
  21. ^ Полезная нагрузка означает длину без учета поля CRC. Расстояние Хэмминга d Значит это d - могут быть обнаружены 1 битовые ошибки и ⌊ (d - 1) / 2⌋ битовые ошибки могут быть исправлены
  22. ^ всегда достигается для произвольно длинных сообщений
  23. ^ а б c d е ж ETSI TS 100 909 (PDF). V8.9.0. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Январь 2005 г.. Получено 21 октября 2016.
  24. ^ "3-битный зоопарк CRC". users.ece.cmu.edu.
  25. ^ Протокол УВЧ RFID поколения 2 класса 1 (PDF). 1.2.0. EPCglobal. 23 октября 2008 г. с. 35 год. Получено 4 июля 2012. (Таблица 6.12)
  26. ^ а б c d е ж Стандарт физического уровня для систем с расширенным спектром cdma2000 (PDF). Редакция D версии 2.0. Проект партнерства третьего поколения 2. Октябрь 2005 г., стр. 2–89–2–92. Архивировано из оригинал (PDF) 16 ноября 2013 г.. Получено 14 октября 2013.
  27. ^ а б c «11. Стратегия исправления ошибок». ETSI EN 300 751 (PDF). V1.2.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Январь 2003. С. 67–8.. Получено 26 января 2016.
  28. ^ "6-битный зоопарк CRC". users.ece.cmu.edu.
  29. ^ а б Чакраварти, Тридиб (декабрь 2001 г.). Производительность кодов циклического резервирования для встроенных сетей (PDF) (Тезис). Филип Купман, советник. Питтсбург: Университет Карнеги-Меллона. стр.5, 18. Получено 8 июля 2013.
  30. ^ «5.1.4 Кодер CRC-8 (только для пакетированных потоков)». EN 302 307 (PDF). V1.3.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Март 2013. с. 17. Получено 29 июля 2016.
  31. ^ а б "8-битный зоопарк CRC". users.ece.cmu.edu.
  32. ^ «7.2.1.2 Вычисление 8-битного полинома 0x2F CRC». Спецификация процедур CRC (PDF). 4.2.2. Мюнхен: АВТОСАР. 22 июля 2015. с. 24. Архивировано из оригинал (PDF) 24 июля 2016 г.. Получено 24 июля 2016.
  33. ^ а б c «5.1.1.8 Поле циклического контроля избыточности (CRC-8 / CRC-16)». Спецификация профиля безопасности openSAFETY: рабочее предложение 304 EPSG. 1.4.0. Берлин: Группа стандартизации Ethernet POWERLINK. 13 марта 2013. с. 42. Архивировано с оригинал 12 августа 2017 г.. Получено 22 июля 2016.
  34. ^ «B.7.1.1 Генерация HEC». Спецификация системы Bluetooth. 2. Bluetooth SIG. 2 декабря 2014. С. 144–5.. Получено 20 октября 2014.
  35. ^ Гарри Уитфилд (24 апреля 2001 г.). "XFCN для расчетов циклической проверки избыточности". Архивировано из оригинал 25 мая 2005 г.
  36. ^ Ричардсон, Эндрю (17 марта 2005 г.). Справочник WCDMA. Кембридж, Великобритания: Издательство Кембриджского университета. п. 223. ISBN  978-0-521-82815-4.
  37. ^ а б Спецификация протокола FlexRay. 3.0.1. Консорциум Flexray. Октябрь 2010. с. 114. (4.2.8 CRC заголовка (11 бит))
  38. ^ Перес, А. (1983). «Побайтовые вычисления CRC». IEEE Micro. 3 (3): 40–50. Дои:10.1109 / MM.1983.291120. S2CID  206471618.
  39. ^ Ramabadran, T.V .; Гайтонде, С.С. (1988). «Учебник по вычислениям CRC». IEEE Micro. 8 (4): 62–75. Дои:10.1109/40.7773. S2CID  10216862.
  40. ^ http://www.freescale.com/files/microcontrollers/doc/app_note/AN1597.pdf
  41. ^ Ely, S.R .; Райт, Д.Т. (март 1982 г.). L.F. Radio-Data: спецификация экспериментальных передач BBC 1982 г. (PDF). Исследовательский отдел инженерного отдела Британской радиовещательной корпорации. п. 9. Получено 11 октября 2013.
  42. ^ Cyclic Redundancy Check (CRC): Техническое описание компонентов PSoC Creator ™. Cypress Semiconductor. 20 февраля 2013. с. 4. Получено 26 января 2016.
  43. ^ «Циклический контроль избыточности (CRC) в кадрах CAN». CAN в автоматизации. Получено 26 января 2016.
  44. ^ «3.2.3 Кодирование и проверка ошибок». Стандарт сигнализации для транкинговых частных наземных мобильных радиосистем (MPT 1327) (PDF) (3-е изд.). Ofcom. Июнь 1997. с. 3. Получено 16 июля 2012.
  45. ^ Реманн, Альберт; Местре, Хосе Д. (февраль 1995 г.). "Предварительный отчет об испытаниях системы авиационной связи и передачи данных по воздуху и земле (ACARS)" (PDF). Технический центр Федерального авиационного управления: 5. Получено 7 июля 2012. Цитировать журнал требует | журнал = (помощь)
  46. ^ «6.2.5 Контроль ошибок». ETSI EN 300 175-3 (PDF). V2.5.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Август 2013. С. 99, 101.. Получено 26 января 2016.
  47. ^ Талер, Пат (28 августа 2003 г.). «Выбор 16-битного полинома CRC» (PDF). INCITS T10. Получено 11 августа 2009. Цитировать журнал требует | журнал = (помощь)
  48. ^ «8.8.4 Проверить октет (FCS)». Нормативные части спецификации PROFIBUS (PDF). 1.0. 9. Profibus International. Март 1998. с. 906. Архивировано с оригинал (PDF) 16 ноября 2008 г.. Получено 9 июля 2016.
  49. ^ а б CAN с гибкой спецификацией скорости передачи данных (PDF). 1.0. Роберт Бош ГмбХ. 17 апреля 2012. с. 13. Архивировано из оригинал (PDF) 22 августа 2013 г. (3.2.1 КАДР ДАННЫХ)
  50. ^ "Руководство программиста операционной системы OS-9". www.roug.org.
  51. ^ Филип П. Купман (20 мая 2018 г.). "24-битный зоопарк CRC". users.ece.cmu.edu.
  52. ^ "cksum". pubs.opengroup.org.
  53. ^ Бутелл, Томас; Рандерс-Персон, Гленн; и другие. (14 июля 1998 г.). "Спецификация PNG (переносимая сетевая графика), версия 1.2". Libpng.org. Получено 3 февраля 2011.
  54. ^ Праймер AIXM (PDF). 4.5. Европейская организация по безопасности аэронавигации. 20 марта 2006 г.. Получено 3 февраля 2019.
  55. ^ ETSI TS 100 909 версия 8.9.0 (январь 2005 г.), раздел 4.1.2 a
  56. ^ Гаммель, Берндт М. (31 октября 2005 г.). Документация Matpack: Крипто - Коды. Matpack.de. Получено 21 апреля 2013. (Примечание: MpCRC.html включен в исходный код сжатого программного обеспечения Matpack, в / html / LibDoc / Crypto)
  57. ^ Геремия, Патрик (апрель 1999). «Вычисление с циклическим контролем избыточности: реализация с использованием TMS320C54x» (PDF) (SPRA530). Техасских инструментов: 5. Получено 4 июля 2012. Цитировать журнал требует | журнал = (помощь)
  58. ^ Джонс, Дэвид Т. «Улучшенная 64-битная циклическая проверка с избыточностью для белковых последовательностей» (PDF). Университетский колледж Лондона. Получено 15 декабря 2009. Цитировать журнал требует | журнал = (помощь)

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

внешняя ссылка