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

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

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

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

Различные стандарты CRC расширяют алгоритм полиномиального деления, определяя начальное значение регистра сдвига, заключительный шаг исключающего ИЛИ и, что наиболее важно, порядок следования битов ( порядок следования байтов ). В результате код, наблюдаемый на практике, сбивает с толку от "чистого" деления ^[2], и регистр может сдвигаться влево или вправо.

Пример [ править ]

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

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

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

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

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

Реализация [ править ]

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

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

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

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

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

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

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

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

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

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

function crc ( битовый массив bitString [1..len], int len) { остатокПолином: = 0 // Популярный вариант дополняет здесь ОстаточноеПолиномиальное; см. § Preset to −1 ниже  для i от 1 до len { ОстающийсяПолином: = ОстаточныйПолиномиальный xor (битовая строка [i] * x n − 1 ) if (коэффициент x n − 1 остатка Полинома) = 1 { остатокПолином: = (остатокПолином * x ) xor generatorПолином } else { ОстаточныйПолином: = (ОстаточныйПолином * x ) } } // Популярный вариант дополняет здесь ОстаточноеПолиномиальное; см. § Пост-инверсия ниже  return Остаток Полиномиальный}

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

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

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

функция crc ( строка байтового массива [1..len], int len) { остатокПолином: = 0 // Популярный вариант дополняет здесь ОстаточноеПолиномиальное; см. § Preset to −1 ниже  для i от 1 до len { остатокПолином: = остатокПолиномиальный xor  polynomialForm (строка [i]) * x n − 8  для j от 1 до 8 { // Предполагается, что 8 бит на байт,  если коэффициент x n − 1 остаткаPolynomial = 1 { остатокПолином: = (остатокПолином * x ) xor generatorПолином } else { ОстаточныйПолином: = (ОстаточныйПолином * x ) } } } // Популярный вариант дополняет здесь ОстаточноеПолиномиальное; см. § Пост-инверсия ниже  return Остаток Полиномиальный}

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

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

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

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

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

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

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

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

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

// Первый старший бит (с прямым порядком байтов) // x ^ 16 + x ^ 12 + x ^ 5 + 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 { // если крайний левый (самый левый значимый) бит установлен rem: = (rem leftShift 1) xor 0x1021 } else { rem: = rem leftShift 1 } rem: = rem и 0xffff // Обрезать остаток до 16 бит } } // Популярный вариант дополняет rem здесь  return rem}

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

// Сначала младший бит (прямой порядок байтов) // x ^ 16 + x ^ 12 + x ^ 5 + 1 = 1000 0100 0000 1000 (1) = 0x8408 function crc ( byte array string [1..len], int len) { rem: = 0 // Популярный вариант дополняет здесь rem  для i от 1 до len { rem: = rem xor string [i] for j от 1 до 8 { // Предполагается, что 8 бит на байт,  если rem и 0x0001 { // если установлен самый правый (самый старший) бит rem: = (rem rightShift 1) xor 0x8408 } else { rem: = rem rightShift 1 } } } // Популярный вариант дополняет rem здесь  return rem}

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

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

Многобитовые вычисления [ править ]

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

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

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

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

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

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

Создание таблиц [ править ]

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

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

big_endian_table [0]: = 0crc: = 0x8000 // Предполагая 16-битный полиномя: = 1do { if crc and 0x8000 { crc: = (crc leftShift 1) xor 0x1021 // Полином CRC } else { crc: = crc leftShift 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, сначала MSB

little_endian_table [0]: = 0crc: = 1;я: = 128do { if crc and 1 { crc: = (crc rightShift 1) xor 0x8408 // Полином CRC } else { crc: = crc rightShift 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

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

Существует алгоритм «срез на N» (обычно «срез на 8» для CRC32; N ≤ 64), который обычно удваивает или утраивает производительность по сравнению с алгоритмом Сарвате. Вместо того, чтобы читать 8 бит за раз, алгоритм читает 8N бит за раз. Это максимизирует производительность суперскалярных процессоров. ^{[5] [6] [7] [8]}

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

Параллельное вычисление без таблицы [ править ]

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

r 0 ←г 1 ←г 2 ←r 3 ←r 4 ←r 5 ←r 6 ←r 7 ←

0e 0 + e 4 + e 7
e 1 + e 5
e 2 + e 6
e 3 + e 7   + e 0 + e 4 + e 7
e 4 + e 1 + e 5
e 5 + e 2 + e 6
e 6 + e 3 + e 7           

e 0 + e 4 + e 1 + e 0 + e 5 + e 2 + e 1
e 1 + e 5 + e 2 + e 1 + e 6 + e 3 + e 2 + e 0
e 2 + e 6 + e 3 + e 2 + e 0 + e 7 + e 4 + e 3 + e 1
e 3 + e 0 + e 7 + e                 4 + e 3 + e 1
e 4 + e 1 + e 0
e 5 + e 2 + e 1
e 6 + e 3 + e 2 + e 0
e 7 + e 4 + e 3 + e 1

 uint8_t  c ,  d ,  e ,  f ,  r ;  …  E  =  c  ^  d ;  е  =  е  ^  ( е  >>  4 )  ^  ( е  >>  7 );  r  =  ( f  <<  1 )  ^  ( f  <<  4 );

 uint8_t  c ,  d ,  e ,  f ,  r ;  …  E  =  c  ^  d ;  е  =  е  ^  ( е  <<  3 )  ^  ( е  <<  4 )  ^  ( е  <<  6 );  г  =  е  ^  ( е  >>  4 )  ^  ( е  >>  5 );

r 0 ←г 1 ←г 2 ←r 3 ←r 4 ←r 5 ←r 6 ←r 7 ←r 8 ←r 9 ←r 10 ←r 11 ←r 12 ←r 13 ←r 14 ←r 15 ←

s 4 + s 0
s 5 + s 1
s 6 + s 2
s 7 + s 3   s 4   s 5 + s 4 + s 0   s 6 + s 5 + s 1   s 7 + s 6 + s 2
c 0   + s 7 + s 3
c 1 + s 4
c 2 + s 5
c 3 + s 6
c 4               + s 7 + s 4 + s 0
c 5 + s 5 + s 1
c 6 + s 6 + s 2
c 7 + s 7 + s 3                 

c 8 + e 4 + e 0
c 9 + e 5 + e 1
c 10 + e 6 + e 2
c 11 + e 0 + e 7 + e 3
c 12 + e 1
c 13 + e 2
c 14 + e 3
с 15 + e 4 + e 0 e 0 + e 5 + e 1 e 1 + e 6 + e                         2   e 2 + e 7 + e 3   e 3   e 4 + e 0   e 5 + e 1   e 6 + e 2   e 7 + e 3

     s p s 0 + s p s 1 + s 0 s 2 + s 1 s 3 + s 2 s 4 + s 3 s 5 + s 4 s 6 + s 5
c 0 + s 7 + s 6
c 1 + s 7
в 2
в 3
в 4
в 5
в 6
в 7 + с п                                 

c 8 + e p
c 9
c 10
c 11
c 12
c 13
c 14 + e 0
c 15 + e 1 + e 0 e 2 + e 1 e 3 + e 2 e 4 + e 3 e 5 + e 4 e 6 + e 5 e 7 + e 6 e p + e 7 e p                     

 uint8_t  d ,  s ,  t ;  uint16_t  c ,  r ;  …  S  =  d  ^  ( c  >>  8 );  t  =  s  ^  ( s  >>  4 );  r  =  ( c  <<  8 )  ^  t  ^  ( t  <<  5 )  ^  ( t  <<  12 );

 uint8_t  d ,  e ,  f ;  uint16_t  c ,  r ;  …  E  =  c  ^  d ;  е  =  е  ^  ( е  <<  4 );  r  =  ( c  >>  8 )  ^  ( f  <<  8 )  ^  ( f  <<  3 )  ^  ( f  >>  4 );

 uint8_t  d ,  s ,  p ;  uint16_t  c ,  r ,  t ;  …  S  =  d  ^  ( c  >>  8 );  p  =  s  ^  ( s  >>  4 );  р  =  р  ^  ( р  >>  2 );  р  =  р  ^  ( р  >>  1 );  р  =  р  &  1 ;  t  = p  |  ( s  <<  1 );  r  =  ( c  <<  8 )  ^  ( t  <<  15 )  ^  t  ^  ( t  <<  1 );

 uint8_t  d ,  e ,  p ;  uint16_t  c ,  r ,  f ;  …  E  =  c  ^  d ;  р  =  е  ^  ( е  >>  4 );  р  =  р  ^  ( р  >>  2 );  р  =  р  ^  ( р  >>  1 );  р  =  р  &  1 ;  f  =  e  |  ( p <<  8 );  r  =  ( c  >>  8 )  ^  ( f  <<  6 )  ^  ( f  <<  7 )  ^  ( f  >>  8 );

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

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

Чтобы максимизировать скорость вычислений, можно вычислить промежуточный остаток , пропустив сообщение через 123-битный регистр сдвига. Полином является тщательно подобранным кратным стандартному многочлену, так что члены (отводы обратной связи) широко разнесены, и ни один бит остатка не подвергается операции XOR более одного раза за байтовую итерацию. Таким образом, необходимы только двухвходовые вентили XOR, самые быстрые из возможных. Наконец, промежуточный остаток делится на стандартный полином во втором регистре сдвига, чтобы получить остаток CRC-32. ^[11]

Однопроходная проверка [ править ]

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

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

Варианты CRC [ править ]

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

Предустановлено на -1 [ править ]

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

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

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

Пост-инвертирование [ править ]

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

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

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

См. Также [ править ]

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

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

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

• Адлер-32
• Контрольная сумма Флетчера

Ссылки [ править ]

Внешние ссылки [ править ]

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

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