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

Код обнаружения ошибок для обнаружения изменений данных

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

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

Введение

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

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

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

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

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

Приложение

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычисление

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

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

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

11010011101100

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

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

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

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

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

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

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

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

def  crc_remainder ( input_bitstring ,  polynomial_bitstring ,  initial_filler ): """Вычисляет остаток CRC строки битов с использованием выбранного полинома.  initial_filler должен быть равен '1' или '0'.  """ polynomial_bitstring = polynomial_bitstring . lstrip ( '0' ) len_input = len ( input_bitstring ) initial_padding = ( len ( polynomial_bitstring ) - 1 ) * initial_filler input_padded_array = list ( input_bitstring + initial_padding ) while '1' in input_padded_array [: len_input ]: cur_shift = input_padded_array . индекс ( '1' ) для i в диапазоне ( 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 ): """Вычислить проверку CRC строки битов с использованием выбранного полинома.""" 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 . индекс ( '1' ) для i в диапазоне ( 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' ) Истина

Математика

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

Проектирование полиномов

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

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

Наиболее часто используемые длины полиномов составляют 9 бит (CRC-8), 17 бит (CRC-16), 33 бита (CRC-32) и 65 бит (CRC-64). ^[5]

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

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

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

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

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

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

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

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

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

В таблице ниже они показаны следующим образом:

Запутывание

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

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

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

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

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

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

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

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

Реализации

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

CRC-каталоги

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

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

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

Ссылки

1. Pundir, Meena; Sandhu, Jasminder Kaur (2021). «Систематический обзор качества обслуживания в беспроводных сенсорных сетях с использованием машинного обучения: последние тенденции и будущее видение». Журнал сетевых и компьютерных приложений . 188 : 103084. doi : 10.1016/j.jnca.2021.103084. Механизм циклического избыточного кода (CRC) используется для защиты данных и обеспечения защиты целостности от битов ошибок при передаче данных от отправителя к получателю.
2. Шиллер, Франк; Маттес, Тина (2007). «Анализ CRC-полиномов для критически важной для безопасности связи с помощью детерминированных и стохастических автоматов». Обнаружение неисправностей, надзор и безопасность технических процессов 2006. Elsevier. стр. 944–949. doi :10.1016/b978-008044485-7/50159-7. ISBN 978-0-08-044485-7Циклический избыточный код (CRC) — эффективный метод обеспечения низкой вероятности необнаруженных ошибок при передаче данных с использованием контрольной суммы, получаемой в результате деления полиномов.
3. "Алгоритм для исправления ошибок при проверке циклическим избыточным кодом". drdobbs.com . Архивировано из оригинала 20 июля 2017 г. Получено 28 июня 2017 г.
4. Петерсон, WW; Браун, DT (январь 1961). «Циклические коды для обнаружения ошибок». Труды IRE . 49 (1): 228–235. doi :10.1109/JRPROC.1961.287814. S2CID  51666741.
5. Ergen, Mustafa (21 января 2008 г.). "2.3.3 Кодирование обнаружения ошибок". Mobile Broadband . Springer . стр. 29–30. doi :10.1007/978-0-387-68192-4_2. ISBN 978-0-387-68192-4.
6. Риттер, Терри (февраль 1986). «Великая тайна CRC». Журнал доктора Добба . 11 (2): 26–34, 76–83. Архивировано из оригинала 16 апреля 2009 года . Получено 21 мая 2009 года .
7. Stigge, Martin; Plötz, Henryk; Müller, Wolf; Redlich, Jens-Peter (май 2006 г.). "Reversing CRC – Theory and Practice" (PDF) . Университет имени Гумбольдта в Берлине. стр. 17. SAR-PR-2006-05. Архивировано из оригинала (PDF) 19 июля 2011 г. Получено 4 февраля 2011 г. Представленные методы предлагают очень простой и эффективный способ изменения ваших данных таким образом, чтобы они вычислялись до CRC, который вы хотите или, по крайней мере, знаете заранее.
8. "algorithm design – Why is said to be linear?". Cryptography Stack Exchange . Получено 5 мая 2019 г. .
9. Cam-Winget, Nancy; Housley, Russ; Wagner, David; Walker, Jesse (май 2003 г.). "Security Flaws in 802.11 Data Link Protocols" (PDF) . Communications of the ACM . 46 (5): 35–39. CiteSeerX 10.1.1.14.8775 . doi :10.1145/769800.769823. S2CID  3132937. Архивировано (PDF) из оригинала 26 мая 2013 г. . Получено 1 ноября 2017 г. . 
10. Williams, Ross N. (24 сентября 1996 г.). "A Painless Guide to CRC Error Detection Algorithms V3.0". Архивировано из оригинала 2 апреля 2018 г. Получено 23 мая 2019 г.
11. Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 22.4 Циклическая избыточность и другие контрольные суммы". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 13 июля 2024 . Получено 20 августа 2024 .
12. Ewing, Gregory C. (март 2010 г.). "Reverse-Engineering a CRC Algorithm". Крайстчерч: Университет Кентербери. Архивировано из оригинала 7 августа 2011 г. Получено 26 июля 2011 г.
13. Купман, Филипп; Чакраварти, Тридиб (июнь 2004 г.). "Выбор полинома циклического избыточного кода (CRC) для встраиваемых сетей". Международная конференция по надежным системам и сетям, 2004 г. (PDF) . стр. 145–154. CiteSeerX 10.1.1.648.9080 . doi :10.1109/DSN.2004.1311885. ISBN  978-0-7695-2052-0. S2CID  793862. Архивировано (PDF) из оригинала 11 сентября 2011 г. Получено 14 января 2011 г.
14. Cook, Greg (15 августа 2020 г.). "Каталог параметризованных алгоритмов CRC". Архивировано из оригинала 1 августа 2020 г. Получено 18 сентября 2020 г.
15. Кастаньоли, Г.; Бройер, С.; Херрманн, М. (июнь 1993 г.). «Оптимизация циклических кодов избыточности с 24 и 32 битами четности». IEEE Transactions on Communications . 41 (6): 883–892. doi :10.1109/26.231911.
16. Купман, Филип (июль 2002 г.). "32-битные циклические избыточные коды для интернет-приложений". Труды Международной конференции по надежным системам и сетям (PDF) . стр. 459–468. CiteSeerX 10.1.1.11.8323 . doi :10.1109/DSN.2002.1028931. ISBN  978-0-7695-1597-7. S2CID  14775606. Архивировано (PDF) из оригинала 16 сентября 2012 г. . Получено 14 января 2011 г. .
17. Купман, Филип (21 января 2016 г.). «Лучшие полиномы CRC». Университет Карнеги-Меллона. Архивировано из оригинала 20 января 2016 г. Получено 26 января 2016 г.
18. Брейер, Кеннет (август 1975 г.). Оценка полиномов 32-й степени при обнаружении ошибок на моделях ошибок SATIN IV Autovon (отчет). Национальная техническая информационная служба . ADA014825. Архивировано из оригинала 31 декабря 2021 г. Получено 31 декабря 2021 г.
19. Хаммонд, Джозеф Л. младший; Браун, Джеймс Э.; Лю, Шьян-Шианг (1975). «Разработка модели ошибок передачи и модели контроля ошибок». Технический отчет NASA Sti/Recon № 76 ( опубликован в мае 1975 г.): 15344. Бибкод : 1975STIN...7615344H. ADA013939. Архивировано из оригинала 31 декабря 2021 г. Получено 31 декабря 2021 г.
20. Брейер, Кеннет; Хаммонд, Джозеф Л. младший (декабрь 1975 г.). Оценка производительности полинома обнаружения ошибок на канале AUTOVON. NTC 75: Национальная конференция по телекоммуникациям, 1–3 декабря 1975 г., Новый Орлеан, Луизиана. Том 1. Институт инженеров по электротехнике и электронике. стр. 8–21–5. Bibcode : 1975ntc.....1....8B. OCLC  32688603. 75 CH 1015-7 CSCB.
21. CRC с четной четностью обнаруживают любое нечетное количество битовых ошибок за счет более низкого расстояния Хэмминга для длинных полезных нагрузок. Обратите внимание, что четность вычисляется по всему генераторному полиному, включая подразумеваемую 1 в начале или конце. Например, полное представление CRC-1 — 0x3, которое имеет два бита 1. Таким образом, его четность четная.
22. "32 Bit CRC Zoo". users.ece.cmu.edu . Архивировано из оригинала 19 марта 2018 г. Получено 5 ноября 2017 г.
23. Полезная нагрузка означает длину без учета поля CRC. Расстояние Хэмминга d означает, что d  − 1 ошибок бита может быть обнаружено и ⌊( d  − 1)/2⌋ ошибок бита может быть исправлено
24. всегда достигается для произвольно длинных сообщений
25. ETSI TS 100 909 (PDF) . V8.9.0. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Январь 2005 г. Архивировано (PDF) из оригинала 17 апреля 2018 г. Получено 21 октября 2016 г.
26. "3 Bit CRC Zoo". users.ece.cmu.edu . Архивировано из оригинала 7 апреля 2018 года . Получено 19 января 2018 года .
27. Протокол UHF RFID Class-1 Generation-2 (PDF) . 1.2.0. EPCglobal . 23 октября 2008 г. стр. 35. Архивировано (PDF) из оригинала 19 марта 2012 г. Получено 4 июля 2012 г.(Таблица 6.12)
28. Физический уровень стандарта для систем с расширенным спектром cdma2000 (PDF) . Редакция D версии 2.0. 3rd Generation Partnership Project 2. Октябрь 2005 г. стр. 2–89–2–92. Архивировано из оригинала (PDF) 16 ноября 2013 г. Получено 14 октября 2013 г.
29. "11. Стратегия исправления ошибок". ETSI EN 300 751 (PDF) . V1.2.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Январь 2003 г. С. 67–8. Архивировано (PDF) из оригинала 28 декабря 2015 г. Получено 26 января 2016 г.
30. "6 Bit CRC Zoo". users.ece.cmu.edu . Архивировано из оригинала 7 апреля 2018 года . Получено 19 января 2018 года .
31. Chakravarty, Tridib (декабрь 2001 г.). Performance of Cyclic Redundancy Codes for Embedded Networks (PDF) (диссертация). Philip Koopman, научный руководитель. Carnegie Mellon University. стр. 5, 18. Архивировано (PDF) из оригинала 1 января 2014 г. Получено 8 июля 2013 г.
32. "5.1.4 CRC-8 encoder (for packetized streams only)". EN 302 307 (PDF) . V1.3.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Март 2013 г. стр. 17. Архивировано (PDF) из оригинала 30 августа 2017 г. Получено 29 июля 2016 г.
33. "8 Bit CRC Zoo". users.ece.cmu.edu . Архивировано из оригинала 7 апреля 2018 года . Получено 19 января 2018 года .
34. "7.2.1.2 8-битное вычисление полинома 0x2F CRC". Спецификация процедур CRC (PDF) . 4.2.2. Мюнхен: AUTOSAR. 22 июля 2015 г. стр. 24. Архивировано из оригинала (PDF) 24 июля 2016 г. Получено 24 июля 2016 г.
35. "5.1.1.8 Поле проверки циклическим избыточным кодом (CRC-8 / CRC-16)". Спецификация профиля безопасности openSAFETY: Рабочий проект предложения EPSG 304. 1.4.0. Берлин: Группа стандартизации Ethernet POWERLINK. 13 марта 2013 г. стр. 42. Архивировано из оригинала 12 августа 2017 г. Получено 22 июля 2016 г.
36. "B.7.1.1 Генерация HEC". Спецификация системы Bluetooth. Том 2. Bluetooth SIG. 2 декабря 2014 г. стр. 144–5. Архивировано из оригинала 26 марта 2015 г. Получено 20 октября 2014 г.
37. Уитфилд, Гарри (24 апреля 2001 г.). "XFCN для вычислений циклического избыточного кода". Архивировано из оригинала 25 мая 2005 г.
38. Ричардсон, Эндрю (17 марта 2005 г.). Справочник WCDMA. Cambridge University Press. стр. 223. ISBN 978-0-521-82815-4.
39. Спецификация протокола FlexRay . 3.0.1. Консорциум Flexray. Октябрь 2010 г. стр. 114.(4.2.8 CRC заголовка (11 бит))
40. Перес, А. (1983). «Побайтовые вычисления CRC». IEEE Micro . 3 (3): 40–50. doi :10.1109/MM.1983.291120. S2CID  206471618.
41. Рамабадран, ТВ; Гаитонде, СС (1988). «Учебник по вычислениям CRC». IEEE Micro . 8 (4): 62–75. doi :10.1109/40.7773. S2CID  10216862.
42. "Декодирование данных длинноволнового радио с использованием HC11 и MC3371" (PDF) . Freescale Semiconductor. 2004. AN1597/D. Архивировано из оригинала (PDF) 24 сентября 2015 г.
43. Ely, SR; Wright, DT (март 1982 г.). LF Radio-Data: спецификация экспериментальных передач BBC 1982 г. (PDF) . Исследовательский отдел, Инженерное подразделение, Британская вещательная корпорация. стр. 9. Архивировано (PDF) из оригинала 12 октября 2013 г. . Получено 11 октября 2013 г.
44. Cyclic Redundancy Check (CRC): PSoC Creator™ Component Datasheet. Cypress Semiconductor. 20 февраля 2013 г. стр. 4. Архивировано из оригинала 2 февраля 2016 г. Получено 26 января 2016 г.
45. "Cyclic redundancy check (CRC) in CAN frames". CAN in Automation . Архивировано из оригинала 1 февраля 2016 года . Получено 26 января 2016 года .
46. "3.2.3 Кодирование и проверка ошибок". Стандарт сигнализации для транкинговых частных наземных мобильных радиосистем (MPT 1327) (PDF) (3-е изд.). Ofcom . Июнь 1997 г. стр. 3. Архивировано (PDF) из оригинала 14 июля 2012 г. Получено 16 июля 2012 г.
47. Рехманн, Альберт; Местре, Хосе Д. (февраль 1995 г.). "Air Ground Data Link VHF Airline Communications and Reporting System (ACARS) Preliminary Test Report" (PDF) . Технический центр Федерального управления гражданской авиации. стр. 5. Архивировано из оригинала (PDF) 2 августа 2012 г. . Получено 7 июля 2012 г. .
48. "6.2.5 Контроль ошибок". ETSI EN 300 175-3 (PDF) . V2.5.1. София Антиполис, Франция: Европейский институт телекоммуникационных стандартов. Август 2013 г. С. 99, 101. Архивировано (PDF) из оригинала 1 июля 2015 г. Получено 26 января 2016 г.
49. Thaler, Pat (28 августа 2003 г.). "16-битный выбор полинома CRC" (PDF) . INCITS T10. Архивировано (PDF) из оригинала 28 июля 2011 г. . Получено 11 августа 2009 г. .
50. "8.8.4 Контрольный октет (FCS)". PROFIBUS Specification Normative Parts (PDF) . 1.0. Том 9. Profibus International. Март 1998 г. стр. 906. Архивировано из оригинала (PDF) 16 ноября 2008 г. Получено 9 июля 2016 г.
51. CAN with Flexible Data-Rate Specification (PDF) . 1.0. Robert Bosch GmbH. 17 апреля 2012 г. стр. 13. Архивировано из оригинала (PDF) 22 августа 2013 г.(3.2.1 ФРЕЙМ ДАННЫХ)
52. "Руководство системного программиста операционной системы OS-9". roug.org . Архивировано из оригинала 17 июля 2018 г. . Получено 17 июля 2018 г. .
53. Купман, Филип П. (20 мая 2018 г.). "24 Bit CRC Zoo". users.ece.cmu.edu . Архивировано из оригинала 7 апреля 2018 г. . Получено 19 января 2018 г. .
54. "cksum". pubs.opengroup.org . Архивировано из оригинала 18 июля 2018 г. Получено 27 июня 2017 г.
55. Бутелл, Томас; Рандерс-Пехрсон, Гленн; и др. (14 июля 1998 г.). «Спецификация PNG (переносимая сетевая графика), версия 1.2». Libpng.org. Архивировано из оригинала 3 сентября 2011 г. Получено 3 февраля 2011 г.
56. AIXM Primer (PDF) . 4.5. Европейская организация по безопасности воздушной навигации . 20 марта 2006 г. Архивировано (PDF) из оригинала 20 ноября 2018 г. Получено 3 февраля 2019 г. .
57. ETSI TS 100 909 Архивировано 17 апреля 2018 г. в Wayback Machine версии 8.9.0 (январь 2005 г.), раздел 4.1.2 a
58. Gammel, Berndt M. (31 октября 2005 г.). Документация Matpack: Crypto – Codes. Matpack.de. Архивировано из оригинала 25 августа 2013 г. Получено 21 апреля 2013 г.(Примечание: MpCRC.html включен в исходный код сжатого программного обеспечения Matpack в /html/LibDoc/Crypto)
59. Geremia, Patrick (апрель 1999 г.). "Вычисление циклического избыточного кода: реализация с использованием TMS320C54x" (PDF) . Texas Instruments. стр. 5. Архивировано (PDF) из оригинала 14 июня 2012 г. Получено 4 июля 2012 г.
60. Джонс, Дэвид Т. "Улучшенная 64-битная циклическая проверка избыточности для последовательностей белков" (PDF) . Университетский колледж Лондона. Архивировано (PDF) из оригинала 7 июня 2011 г. . Получено 15 декабря 2009 г. .

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

• Уоррен-младший, Генри С. (2013). "14. Циклическая проверка избыточности". Hacker's Delight (2-е изд.). Addison Wesley . стр. 319–330. ISBN 978-0-321-84268-8.
• Купман, Филип (2024). Понимание контрольных сумм и циклических проверок избыточности . ASIN  B0CVXWDZ99.

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

• Митра, Джубин; Наяк, Тапан (январь 2017 г.). «Реконфигурируемая архитектура проектирования сверхвысокой пропускной способности и низкой задержки VLSI (FPGA) CRC 32». Интеграция, VLSI Journal . 56 : 1–14. doi :10.1016/j.vlsi.2016.09.005.
• Циклические проверки избыточности, MathPages, обзор обнаружения ошибок различных полиномов
• Уильямс, Росс (1993). "Безболезненное руководство по алгоритмам обнаружения ошибок CRC". Архивировано из оригинала 3 сентября 2011 г. Получено 15 августа 2011 г.
• Блэк, Ричард (1994). «Быстрый CRC32 в программном обеспечении». Синяя книга . Группа системных исследований, компьютерная лаборатория, Кембриджский университет.Алгоритм 4 использовался в Linux и Bzip2.
• Кунавис, М.; Берри, Ф. (2005). "Систематический подход к построению высокопроизводительных программных генераторов CRC" (PDF) . Intel. Архивировано (PDF) из оригинала 16 декабря 2006 г. . Получено 4 февраля 2007 г. ., Алгоритмы нарезки по 4 и по 8
• Kowalk, W. (август 2006 г.). "CRC Cyclic Redundancy Check Analysing and Correcting Errors" (PDF) . Universität Oldenburg. Архивировано (PDF) из оригинала 11 июня 2007 г. . Получено 1 сентября 2006 г. .— Битовые фильтры
• Уоррен, Генри С. младший. "Cyclic Redundancy Check" (PDF) . Hacker's Delight . Архивировано из оригинала (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