Расчет циклических проверок избыточности

Вычисление циклической проверки избыточности выводится из математики полиномиального деления по модулю два . На практике это напоминает длинное деление строки двоичного сообщения с фиксированным числом добавленных нулей строкой «генераторного полинома», за исключением того, что операции исключающего или заменяют вычитания. Деление этого типа эффективно реализуется в оборудовании с помощью модифицированного регистра сдвига ^[1] и в программном обеспечении с помощью ряда эквивалентных алгоритмов , начиная с простого кода, близкого к математике, и становясь быстрее (и, возможно, более запутанным ^[2] ) посредством побайтового параллелизма и компромиссов между пространством и временем .

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

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

Различные стандарты CRC расширяют алгоритм полиномиального деления, указывая начальное значение регистра сдвига, конечный шаг Exclusive-OR и, что наиболее важно, порядок битов ( endianness ). В результате код, наблюдаемый на практике, отклоняется от «чистого» деления, ^[2] и регистр может сдвигаться влево или вправо.

Пример

В качестве примера реализации полиномиального деления на оборудовании предположим, что мы пытаемся вычислить 8-битный CRC 8-битного сообщения, состоящего из символа ASCII "W", который является двоичным 01010111 ₂ , десятичным 87 ₁₀ или шестнадцатеричным 57 ₁₆ . Для иллюстрации мы будем использовать полином CRC-8-ATM ( HEC ) . Записывая первый переданный бит (коэффициент наивысшей степени ) слева, это соответствует 9-битной строке "100000111". $x^{8}+x^{2}+x+1$ $x$

Значение байта 57 ₁₆ может передаваться в двух разных порядках, в зависимости от используемого соглашения о порядке битов. Каждый из них генерирует другой полином сообщения . Msbit-first, это = 01010111, в то время как lsbit-first, это = 11101010. Затем их можно умножить на , чтобы получить два 16-битных полинома сообщения . $M(x)$ $x^{6}+x^{4}+x^{2}+x+1$ $x^{7}+x^{6}+x^{5}+x^{3}+x$ $x^{8}$ $x^{8}M(x)$

Вычисление остатка затем состоит из вычитания кратных полинома генератора . Это похоже на десятичное деление в столбик, но даже проще, потому что единственными возможными кратными на каждом шаге являются 0 и 1, а вычитания заимствуют «из бесконечности» вместо уменьшения верхних цифр. Поскольку нас не волнует частное, нет необходимости его записывать. $G(x)$

Обратите внимание, что после каждого вычитания биты делятся на три группы: в начале группа, состоящая из одних нулей; в конце группа, которая не изменилась по сравнению с исходной; и синяя затененная группа в середине, которая является «интересной». «Интересная» группа имеет длину 8 бит, что соответствует степени многочлена. На каждом шаге соответствующее кратное многочлена вычитается, чтобы сделать нулевую группу на один бит длиннее, а неизмененная группа становится на один бит короче, пока не останется только последний остаток.

В примере msbit-first остаток полинома равен . Преобразование в шестнадцатеричное число с использованием соглашения, что наивысшая степень x является msbit; это A2 ₁₆ . В примере lsbit-first остаток равен . Преобразование в шестнадцатеричное число с использованием соглашения, что наивысшая степень x является lsbit; это 19 ₁₆ . $x^{7}+x^{5}+x$ $x^{7}+x^{4}+x^{3}$

Выполнение

Выписывать полное сообщение на каждом шаге, как это сделано в примере выше, очень утомительно. Эффективные реализации используют -битный регистр сдвига для хранения только интересных битов. Умножение полинома на эквивалентно сдвигу регистра на одну позицию, поскольку коэффициенты не меняют своего значения, а только перемещаются к следующему члену полинома. $n$ $x$

Вот первый черновик псевдокода для вычисления n -битного CRC. Он использует выдуманный составной тип данных для полиномов, где x— не целочисленная переменная, а конструктор, генерирующий объект Polynomial , который можно складывать, умножать и возводить в степень. К двум полиномам — это сложить их по модулю два; то есть, выполнить исключающее ИЛИ коэффициентов каждого совпадающего члена из обоих полиномов.xor

функция crc( битовый массив bitString[1..len], int len) { remainderPolynomial := polynomialForm (bitString[1..n]) // Первые n бит сообщения  // Популярный вариант дополняет remainderPolynomial здесь; см. § Предустановка на −1 ниже  для i от 1 до len { remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x ⁰ // Определить bitString[k]=0 для k>len  , если коэффициент x ⁿ в remainderPolynomial = 1 { остатокПолином := остатокПолином xor генераторПолином } } // Популярный вариант дополняет remainderPolynomial здесь; см. § Post-invert ниже  return remainderPolynomial}

Фрагмент кода 1: Простое полиномиальное деление

Обратите внимание, что в этом примере кода нет необходимости указывать соглашение о порядке битов, поскольку байты не используются; входные данные bitStringуже представлены в виде битового массива, а remainderPolynomialманипулируются с помощью полиномиальных операций; умножение на может быть левым или правым сдвигом, а прибавление выполняется к коэффициенту, который может быть правым или левым концом регистра. $x$ bitString[i+n] $x^{0}$

У этого кода есть два недостатка. Во-первых, он фактически требует n +1-битный регистр для хранения remainderPolynomial, чтобы можно было проверить коэффициент. Что еще более важно, он требует дополнения n нулевыми битами. $x^{n}$ bitString

Первую задачу можно решить, проверив коэффициент перед тем, как его умножить на . $x^{n-1}$ remainderPolynomial $x$

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

Поскольку операция XOR, используемая для вычитания полинома генератора из сообщения, является коммутативной и ассоциативной , не имеет значения, в каком порядке различные входы объединяются в remainderPolynomial. И, в частности, заданный бит bitStringне нужно добавлять к , remainderPolynomialпока он не будет проверен, чтобы определить, следует ли его добавлять xorк generatorPolynomial.

Это также устраняет необходимость предварительной загрузки remainderPolynomialпервых n бит сообщения:

функция crc( битовый массив bitString[1..len], int len) { остатокПолином := 0 // Популярный вариант дополняет remainderPolynomial здесь; см. § Предустановка на −1 ниже  для i от 1 до len { remainderPolynomial := remainderPolynomial xor (bitstring[i] * x ⁿ⁻¹ ) если (коэффициент x ⁿ⁻¹ remainderPolynomial) = 1 { остатокПолином := (остатокПолином * x ) генератор xorПолином } еще { остатокПолинома := (остатокПолинома * x ) } } // Популярный вариант дополняет remainderPolynomial здесь; см. § Post-invert ниже  return remainderPolynomial}

Фрагмент кода 2: Полиномиальное деление с отложенным сообщением XORing

Это стандартная реализация CRC-кода по битам за раз, и она заслуживает изучения; как только вы поймете, почему она вычисляет точно такой же результат, как и первая версия, остальные оптимизации будут довольно простыми. Если remainderPolynomialимеет длину всего n бит, то коэффициенты ее и просто отбрасываются. По этой причине вы обычно будете видеть полиномы CRC, записанные в двоичном виде с опущенным старшим коэффициентом. $x^{n}$ generatorPolynomial

В программном обеспечении удобно отметить, что хотя можно отложить выполнение xorкаждого бита до самого последнего момента, это также возможно сделать раньше. Обычно удобно выполнять по xorодному байту за раз, даже в реализации «побитно за раз». Здесь мы берем входные данные в 8-битных байтах:

функция crc( массив байтов string[1..len], int len) { остатокПолином := 0 // Популярный вариант дополняет remainderPolynomial здесь; см. § Предустановка на −1 ниже  для i от 1 до len { remainderPolynomial := remainderPolynomial xor  polynomialForm (string[i]) * x ⁿ⁻⁸ для j от 1 до 8 { // Предполагая 8 бит на байт  , если коэффициент x ⁿ⁻¹ remainderPolynomial = 1 { остатокПолином := (остатокПолином * x ) генератор xorПолином } еще { остатокПолинома := (остатокПолинома * x ) } } } // Популярный вариант дополняет remainderPolynomial здесь; см. § Post-invert ниже  return remainderPolynomial}

Фрагмент кода 3: Полиномиальное деление с побайтовым сообщением XORing

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

Порядок битов (порядок байтов)

При реализации в аппаратном обеспечении последовательной передачи битов полином генератора однозначно описывает назначение битов; первый переданный бит всегда является коэффициентом наивысшей степени , а последние переданные биты являются остатком CRC , начиная с коэффициента и заканчивая коэффициентом , также известным как коэффициент 1. $x$ $n$ $R(x)$ $x^{n-1}$ $x^{0}$

Однако, когда биты обрабатываются побайтно , например, при использовании параллельной передачи , кадрирования байтов, как в кодировке 8B/10B или асинхронной последовательной связи в стиле RS-232 , или при реализации CRC в программном обеспечении , необходимо указать порядок битов (порядок байтов) данных; какой бит в каждом байте считается «первым» и будет коэффициентом высшей степени . $x$

Если данные предназначены для последовательной связи , лучше всего использовать порядок битов, в котором данные в конечном итоге будут отправлены. Это связано с тем, что способность CRC обнаруживать пакетные ошибки основана на близости в полиноме сообщения ; если соседние члены полинома не передаются последовательно, физический пакет ошибок одной длины может рассматриваться как более длинный пакет из-за перестановки битов. $M(x)$

Например, стандарты IEEE 802 ( ethernet ) и RS-232 ( последовательный порт ) определяют передачу с первым младшим битом (little-endian), поэтому программная реализация CRC для защиты данных, передаваемых по такому каналу, должна сопоставлять младшие биты в каждом байте с коэффициентами высших степеней . С другой стороны, дискеты и большинство жестких дисков записывают первым старший бит каждого байта. $x$

Lsbit-first CRC немного проще реализовать в программном обеспечении, поэтому встречается несколько чаще, но многие программисты считают, что порядок битов msbit-first проще для понимания. Так, например, расширение XMODEM -CRC, раннее использование CRC в программном обеспечении, использует msbit-first CRC.

До сих пор псевдокод избегал указания порядка битов в байтах, описывая сдвиги в псевдокоде как умножения на и записывая явные преобразования из двоичной в полиномиальную форму. На практике CRC хранится в стандартном двоичном регистре с использованием определенного соглашения о порядке битов. В форме msbit-first наиболее значимые двоичные биты будут отправлены первыми и, таким образом, будут содержать коэффициенты полинома более высокого порядка, в то время как в форме lsbit-first наименее значимые двоичные биты содержат коэффициенты более высокого порядка. Вышеприведенный псевдокод может быть записан в обеих формах. Для конкретности, это использует 16-битный полином CRC-16- CCITT : $x$ $x^{16}+x^{12}+x^{5}+1$

// Самый старший бит первый (big-endian) // (x ¹⁶ )+x ¹² +x ⁵ +1 = (1) 0001 0000 0010 0001 = 0x1021 function crc( byte array string[1..len], int len) { rem := 0 // Популярный вариант дополняет rem здесь  для i от 1 до len { rem := rem xor (string[i] leftShift (n-8)) // n = 16 в этом примере  для j от 1 до 8 { // Предполагая 8 бит на байт  , если rem и 0x8000 { // Тест коэффициента x ¹⁵ rem := (rem leftShift 1) xor 0x1021 } еще { rem := rem leftShift 1 } rem := rem и 0xffff // Обрезаем остаток до 16 бит } } // Популярный вариант дополняет rem здесь  return rem}

Фрагмент кода 4: Деление на основе регистра сдвига, старший значащий бит первый

// Сначала младший бит (прямой порядок байтов) // 1+x ⁵ +x ¹² +(x ¹⁶ ) = 1000 0100 0000 1000 (1) = 0x8408 function crc( byte array string[1..len], int len) { рем := 0 // Популярный вариант дополняет rem здесь  для i от 1 до len { rem := rem xor string[i] for j from 1 to 8 { // Предполагая 8 бит на байт  if rem и 0x0001 { // Тестовый коэффициент x ¹⁵ rem := (rem rightShift 1) xor 0x8408 } еще { rem := rem вправоShift 1 } } } // Популярный вариант дополняет rem здесь  return rem}

Фрагмент кода 5: Деление на основе регистра сдвига, сначала младший бит

Обратите внимание, что форма lsbit-first позволяет избежать необходимости сдвига string[i]перед xor. В любом случае обязательно передавайте байты CRC в порядке, соответствующем выбранному вами соглашению о порядке битов.

Многобитные вычисления

Алгоритм Сарвата (единая таблица поиска)

Другая распространенная оптимизация использует таблицу поиска, индексированную коэффициентами наивысшего порядка remдля обработки более одного бита дивиденда за итерацию. ^[3] Чаще всего используется таблица поиска с 256 записями, заменяющая тело внешнего цикла (по i) на:

// Msbit-первыйrem = (rem leftShift 8) xor big_endian_table[string[i] xor ((крайние левые 8 бит rem) rightShift (n-8))]// Lsbit-первыйrem = (rem rightShift 8) xor little_endian_table[string[i] xor (крайние правые 8 бит rem)]

Фрагмент кода 6: Ядра табличного деления

Один из наиболее часто встречающихся алгоритмов CRC известен как CRC-32 , используемый (среди прочих) Ethernet , FDDI , ZIP и другими форматами архивов , а также форматом изображений PNG . Его полином может быть записан msbit-first как 0x04C11DB7 или lsbit-first как 0xEDB88320. Веб-страница W3C по PNG включает приложение с короткой и простой табличной реализацией на языке C CRC-32. ^[4] Вы заметите, что код соответствует псевдокоду lsbit-first byte-at-a-time, представленному здесь, и таблица генерируется с использованием кода bit-at-a-time.

Использование таблицы с 256 записями обычно наиболее удобно, но можно использовать и другие размеры. В небольших микроконтроллерах использование таблицы с 16 записями для обработки четырех бит за раз дает полезное улучшение скорости, сохраняя при этом небольшую таблицу. На компьютерах с достаточным объемом памяти,Таблица из 65 536 записей может использоваться для обработки 16 бит одновременно.

Генерация таблиц

Программное обеспечение для генерации таблиц настолько мало и быстро, что обычно быстрее вычислять их при запуске программы, чем загружать предварительно вычисленные таблицы из хранилища. Одним из популярных методов является использование бит-за-за-каждый код 256 раз для генерации CRC 256 возможных 8-битных байтов. Однако это можно значительно оптимизировать, воспользовавшись тем свойством, что . Только записи таблицы, соответствующие степеням двойки, необходимо вычислять напрямую.table[i xor j] == table[i] xor table[j]

В следующем примере кода crcсодержится значение table[i]:

big_endian_table[0] := 0crc := 0x8000 // Предположим, что полином 16-битныйя := 1сделать { если crc и 0x8000 { crc := (crc leftShift 1) xor 0x1021 // Полином CRC } else { crc := crc левый сдвиг 1 } // crc — это значение big_endian_table[i] ; пусть j выполняет итерацию по уже инициализированным записям  для j от 0 до i−1 { big_endian_table[i + j] := crc xor big_endian_table[j]; } i := i сдвиг влево 1} пока я < 256

Фрагмент кода 7: Побайтовая генерация таблицы CRC, первым идет старший значащий бит

little_endian_table[0] := 0крк := 1;я := 128сделать { если crc и 1 { crc := (crc rightShift 1) xor 0x8408 // Полином CRC } else { crc := crc вправоShift 1 } // crc — это значение little_endian_table[i] ; пусть j выполняет итерацию по уже инициализированным записям  для j от 0 до 255 по 2 × i { little_endian_table[i + j] := crc xor little_endian_table[j]; } i := i сдвиг вправо 1} пока я > 0

Фрагмент кода 8: Побайтовая генерация таблицы CRC, сначала младший бит

В этих примерах кода индекс таблицы i + jэквивалентен ; вы можете использовать любую удобную для вас форму.i xor j

Алгоритм CRC-32

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

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

На языке C алгоритм выглядит так:

#include <inttypes.h> // uint32_t, uint8_t uint32_t CRC32 ( const uint8_t data [], size_t data_length ) { uint32_t crc32 = 0xFFFFFFFFu ; for ( size_t i = 0 ; i < data_length ; i ++ ) { const uint32_t lookupIndex = ( crc32 ^ data [ i ]) & 0xff ; crc32 = ( crc32 >> 8 ) ^ CRCTable [ lookupIndex ]; // CRCTable — это массив из 256 32-битных констант } // Завершим значение CRC-32, инвертировав все биты crc32 ^= 0xFFFFFFFFu ; return crc32 ; }

Байт-срез с использованием нескольких таблиц

Существует алгоритм slice-by -n (обычно slice-by-8 для CRC32), который обычно удваивает или утраивает производительность по сравнению с алгоритмом Sarwate. Вместо того, чтобы считывать 8 бит за раз, алгоритм считывает 8 n бит за раз. Это максимизирует производительность на суперскалярных процессорах. ^[6]^[7]^[8]^[9]

Неясно, кто на самом деле изобрел алгоритм. ^[10]

Чтобы понять преимущества, начнем со случая slice-by-2. Мы хотим вычислить CRC 2 байта (16 бит) за раз, но стандартный табличный подход потребовал бы неудобно большой таблицы из 65536 записей. Как упоминалось в § Генерация таблиц, таблицы CRC обладают тем свойством, что . Мы можем использовать это тождество для замены большой таблицы двумя таблицами по 256 записей: .table[i xor j] = table[i] xor table[j]table[i + 256×j] = table_low[i] xor table_high[j]

Итак, большая таблица не хранится явно, но каждая итерация вычисляет значение CRC, которое там будет, объединяя значения в двух меньших таблицах. То есть, 16-битный индекс «разрезается» на два 8-битных индекса. На первый взгляд, это кажется бессмысленным; зачем делать два поиска в отдельных таблицах, когда стандартный алгоритм «байт за раз» делал бы два поиска в одной и той же таблице?

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

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

Очевидно, что эту технологию можно распространить на столько фрагментов, сколько необходимо процессору.

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

Результирующий внутренний цикл slice-by -n состоит из:

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

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

Это происходит потому, что часть результатов первого шага больше не зависит от какой-либо предыдущей итерации. При выполнении операции XOR над 32-битным CRC с 64 битами сообщения половина результата представляет собой просто копию сообщения. Если кодирование выполнено аккуратно (чтобы избежать создания ложной зависимости данных ), половина загрузок таблицы срезов может начаться до завершения предыдущей итерации цикла. Результатом является достаточная работа для поддержания постоянной занятости подсистемы памяти процессора , что обеспечивает максимальную производительность. Как уже упоминалось, на микропроцессорах после 2000 года для достижения этого уровня обычно достаточно slice-by-8.

Нет особой необходимости в том, чтобы срезы были шириной 8 бит. Например, было бы вполне возможно вычислить CRC 64 бита за раз, используя алгоритм slice-by-9, используя 9 таблиц поиска по 128 записей для обработки 63 бит, а 64-й бит обрабатывался бы алгоритмом bit-at-a-time (который фактически является 1-битной таблицей поиска по 2 записи). Это почти вдвое уменьшило бы размер таблицы (переходя с 8×256 = 2048 записей до 9×128 = 1152) за счет одной дополнительной загрузки, зависящей от данных, на итерацию.

Параллельные вычисления без таблицы

Параллельное обновление для байта или слова за раз также может быть сделано явно, без таблицы. ^[11] Обычно это используется в высокоскоростных аппаратных реализациях. Для каждого бита уравнение решается после того, как 8 бит были сдвинуты. В следующих таблицах перечислены уравнения для некоторых часто используемых полиномов, используя следующие символы:

Двухэтапное вычисление

Поскольку полином CRC-32 имеет большое количество членов, при вычислении остатка по байтам каждый бит зависит от 8 битов предыдущей итерации. В байт-параллельных аппаратных реализациях это требует либо 8-входовых, либо каскадных вентилей XOR, что увеличивает задержку распространения .

Чтобы максимизировать скорость вычислений, промежуточный остаток может быть вычислен путем первого вычисления CRC сообщения по модулю x ¹²³ + x ¹¹¹ + x ⁹² + x ⁸⁴ + x ⁶⁴ + x ⁴⁶ + x ²³ + 1. Это тщательно подобранное кратное полинома CRC-32, так что члены (отводы обратной связи) находятся на расстоянии не менее 8 позиций друг от друга. Таким образом, 123-битный регистр сдвига может быть продвинут на 8 бит за итерацию, используя только двухвходовые вентили XOR, что является максимально возможной скоростью. Наконец, промежуточный остаток может быть уменьшен по модулю стандартного полинома во втором регистре сдвига, чтобы получить остаток CRC-32. ^[12]

Если разрешены 3- или 4-входовые элементы XOR, можно использовать более короткие промежуточные полиномы степени 71 или 53 соответственно.

Блочные вычисления

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

Однопроходная проверка

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

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

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

Варианты CRC

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

Предустановлено значение −1

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

Но если передаваемое сообщение заботится о ведущих нулевых битах, неспособность базового алгоритма CRC обнаружить такое изменение нежелательна. Если возможно, что ошибка передачи может добавить такие биты, простым решением будет начать с remустановки регистра сдвига на некоторое ненулевое значение; для удобства обычно используется значение «все единицы». Это математически эквивалентно дополнению (двоичное НЕ) первых n бит сообщения, где n — количество бит в регистре CRC.

Это никак не влияет на генерацию и проверку CRC, пока и генератор, и проверяющий используют одно и то же начальное значение. Подойдет любое ненулевое начальное значение, и несколько стандартов указывают необычные значения, ^[15] но значение из всех единиц (−1 в двоичном дополнительном коде) является наиболее распространенным. Обратите внимание, что однопроходная генерация/проверка CRC все равно даст результат ноль, когда сообщение верно, независимо от предустановленного значения.

Пост-инверт

Такая же ошибка может возникнуть в конце сообщения, хотя и с более ограниченным набором сообщений. Добавление 0 бит к сообщению эквивалентно умножению его полинома на x , и если он ранее был кратен полиному CRC, то результатом этого умножения также будет x. Это эквивалентно тому факту, что поскольку 726 кратно 11, то и 7260 тоже кратно 11.

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

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

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

Общая категория

Код исправления ошибок
Список хэш-функций
Четность эквивалентна 1-битному CRC с полиномом $x +1$ .

Контрольные суммы без CRC

Ссылки

^ Дуброва, Елена; Мансури, Шохре Шариф (май 2012 г.). «Подход на основе BDD к построению LFSRS для параллельного кодирования CRC». 2012 IEEE 42nd International Symposium on Multiple-Valued Logic . стр. 128–133. doi :10.1109/ISMVL.2012.20. ISBN 978-0-7695-4673-5. S2CID 27306826.
^ ab Williams, Ross N. (1996-09-24). "A Painless Guide to CRC Error Detection Algorithms V3.00". Архивировано из оригинала 2006-09-27 . Получено 2016-02-16 .
^ Sarwate, Dilip V. (август 1998 г.). «Вычисление циклических проверок избыточности с помощью табличного поиска». Communications of the ACM . 31 (8): 1008–1013. doi : 10.1145/63030.63037 . S2CID 5363350.
^ "Спецификация Portable Network Graphics (PNG) (второе издание): Приложение D, Пример реализации циклического избыточного кода". W3C . 2003-11-10 . Получено 2016-02-16 .
^ "[MS-ABS]: 32-битный алгоритм CRC". msdn.microsoft.com . Архивировано из оригинала 7 ноября 2017 г. . Получено 4 ноября 2017 г. .
^ Кунавис, ME; Берри, FL (2005). «Систематический подход к созданию высокопроизводительных программных генераторов CRC». 10-й симпозиум IEEE по компьютерам и коммуникациям (ISCC'05) (PDF) . стр. 855–862. doi :10.1109/ISCC.2005.18. ISBN 0-7695-2373-0. S2CID 10308354.
^ Берри, Фрэнк Л.; Кунавис, Майкл Э. (ноябрь 2008 г.). «Новые алгоритмы на основе поиска в таблицах для высокопроизводительной генерации CRC». IEEE Transactions on Computers . 57 (11): 1550–1560. doi :10.1109/TC.2008.85. S2CID 206624854.
^ Генерация высокооктанового CRC с помощью алгоритма Intel Slicing-by-8 (PDF) (Технический отчет). Intel . Архивировано из оригинала (PDF) 2012-07-22.
^ "Краткое руководство по вычислению CRC". Архив ядра Linux .
^ Менон-Сен, Абхиджит (2017-01-20). «Кто изобрел алгоритм нарезки по N CRC32?».
^ Джон Буллер (1996-03-15). "Re: 8051 и CRC-CCITT". Группа новостей : comp.arch.embedded. Usenet: [email protected] . Получено 2016-02-16 .
^ Glaise, René J. (1997-01-20). "Двухшаговое вычисление циклического избыточного кода CRC-32 для сетей ATM". IBM Journal of Research and Development . 41 (6). Armonk, NY : IBM : 705. doi :10.1147/rd.416.0705. Архивировано из оригинала 2009-01-30 . Получено 2016-02-16 .
^ Дас, Ариндам (2022). «Блочное вычисление циклического избыточного кода с использованием факторизованных матриц Теплица вместо таблицы поиска». IEEE Transactions on Computers . 72 (4): 1110–1121. doi :10.1109/TC.2022.3189574. ISSN 0018-9340. S2CID 250472783.
^ Кадатч, Эндрю; Дженкинс, Боб (3 сентября 2010 г.). Все, что мы знаем о CRC, но боимся забыть (PDF) (Технический отчет). стр. 4. Тот факт, что CRC сообщения, за которым следует его CRC, является постоянной величиной, которая не зависит от сообщения... хорошо известен и широко используется в телекоммуникационной отрасли в течение длительного времени.{{cite tech report}}: CS1 maint: year (link) Хороший источник для еще большего
^ Например, лист данных низкочастотного RFID TMS37157 - Пассивное низкочастотное интерфейсное устройство с EEPROM и интерфейсом транспондера 134,2 кГц (PDF) , Texas Instruments , ноябрь 2009 г., стр. 39 , получено 16 февраля 2016 г. Генератор CRC инициализируется значением 0x3791, как показано на рисунке 50.

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

Джон Пол Адамовский. «64-битный циклический избыточный код – длинное деление XOR для побайтового поиска в таблице».

Эндрю Кадарч, Боб Дженкинс. "Эффективная (~1 цикл ЦП на байт) реализация CRC". GitHub .