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

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

Любую строку битов можно интерпретировать как коэффициенты полинома сообщения такого типа, и чтобы найти CRC, мы умножаем полином сообщения на $x^{n}$ а затем находим остаток при делении на степень - $n$ полином генератора . Коэффициентами полинома остатка являются биты CRC.

Формулировка

В общем, вычисление CRC соответствует евклидову делению полиномов по GF(2) :

M(x)\cdot x^{n}=Q(x)\cdot G(x)+R(x).

Здесь $M(x)$ является исходным полиномом сообщения и $G(x)$ это степень- $n$ генераторный полином. Части $M(x)\cdot x^{n}$ оригинальное сообщение с $n$ в конце добавлены нули. «Контрольная сумма» CRC формируется из коэффициентов полинома остатка. $R(x)$ степень которого строго меньше $n$ . Факторный полином $Q(x)$ не представляет интереса. Используя операцию по модулю , можно сказать, что

R(x)=M(x)\cdot x^{n}\,{\bmod {\,}}G(x).

При сообщении отправитель прикрепляет $n$ биты R после битов исходного сообщения M, что, как можно показать, эквивалентно отправке $M(x)\cdot x^{n}-R(x)$ ( кодовое слово .) Получатель, зная $G(x)$ и поэтому $n$ , отделяет M от R и повторяет расчет, проверяя, что полученное и вычисленное R равны. Если да, то получатель предполагает, что биты полученного сообщения верны.

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

CRC — это контрольная сумма в строгом математическом смысле, поскольку ее можно выразить как взвешенную по модулю 2 сумму побитовых синдромов , но это слово обычно зарезервировано для сумм, вычисленных с использованием больших модулей, таких как 10, 256, или 65535.

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

Полиномиальная арифметика по модулю 2

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

(x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1{\pmod {2}}.

Обратите внимание, что $2x$ эквивалентно нулю в приведенном выше уравнении, поскольку сложение коэффициентов выполняется по модулю 2:

2x=x+x=x\times (1+1)\equiv x\times 0=0{\pmod {2}}.

Полиномиальное сложение по модулю 2 аналогично побитовому исключающему ИЛИ . Поскольку исключающее ИЛИ является обратным самому себе, полиноминальное вычитание по модулю 2 аналогично побитовому исключающему ИЛИ.

Умножение аналогично ( произведение без переноса ):

(x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x{\pmod {2}}.

Мы также можем разделить многочлены по модулю 2 и найти частное и остаток. Например, предположим, что мы делим $x^{3}+x^{2}+x$ к $x+1$ . Мы бы нашли это

{\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}.

Другими словами,

(x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1\equiv (x^{2}+1)(x+1)+1{\pmod {2}}.

Деление дает частное от x ² + 1 с остатком -1, который, поскольку он нечетный, имеет последний бит 1.

В приведенных выше уравнениях $x^{3}+x^{2}+x$ представляет исходные биты сообщения 111, $x+1$ – образующий полином, а остаток $1$ (эквивалентно, $x^{0}$ ) — это CRC. Степень полинома генератора равна 1, поэтому мы сначала умножили сообщение на $x^{1}$ получить $x^{3}+x^{2}+x$ .

Вариации

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

Для проверки CRC вместо вычисления CRC сообщения и сравнения его с CRC можно выполнить вычисление CRC для всего кодового слова. Если результат (называемый остатком) равен нулю, проверка проходит. Это работает, потому что кодовое слово $M(x)\cdot x^{n}-R(x)=Q(x)\cdot G(x)$ , которое всегда делится на $G(x)$ .

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

Регистр сдвига может быть инициализирован единицами вместо нулей. Это эквивалентно инвертированию первого $n$ биты сообщения перед подачей их в алгоритм. Уравнение CRC становится $M(x)\cdot x^{n}+\sum _{i=m}^{m+n-1}x^{i}=Q(x)\cdot G(x)+R(x)$ , где $m>\deg(M(x))$ длина сообщения в битах. Изменение, которое это накладывает на $R(x)$ является функцией производящего полинома и длины сообщения, $\left(\sum _{i=m}^{m+n-1}x^{i}\right)\,{\bmod {\,}}G(x)$ .

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

M(x)

. Когда эта инверсия выполнена, CRC различает такие сообщения.

CRC может быть инвертирован перед добавлением в поток сообщений. Хотя немодифицированный CRC различает сообщения $M(x)$ с различным количеством конечных нулей он не обнаруживает конечные нули, добавленные после самого остатка CRC. Это связано с тем, что все допустимые кодовые слова кратны $G(x)$ , так $x$ раз это кодовое слово также кратно. (На самом деле именно поэтому работает первый вариант, описанный выше.)

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

Таким образом, CRC можно проверить либо очевидным методом вычисления CRC в сообщении, его инвертирования и сравнения с CRC в потоке сообщений, либо путем вычисления CRC для всего кодового слова и сравнения его с ожидаемым фиксированным значением. $C(x)$ , называемый проверочным полиномом, остатком или магическим числом . Это может быть вычислено как $C(x)=\left(\sum _{i=n}^{2n-1}x^{i}\right)\,{\bmod {\,}}G(x)$ или, что то же самое, путем вычисления немодифицированного CRC сообщения, состоящего из $n$ те, $M(x)=\sum _{i=0}^{n-1}x^{i}$ .

Эти инверсии чрезвычайно распространены, но не выполняются повсеместно, даже в случае полиномов CRC-32 или CRC-16-CCITT.

Обратные представления и обратные полиномы

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

Пример 16-битного полинома CCITT в описанных формах (биты внутри квадратных скобок включены в словесное представление; биты снаружи подразумеваются 1 бит; вертикальные полосы обозначают границы полубайта ):

16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0   coefficient
 1 [0  0  0  1 |0  0  0  0 |0  0  1  0 |0  0  0  1]  Normal                        
   [     1     |     0     |     2     |     1    ]  Nibbles of Normal                 0x1021

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[1  0  0  0 |0  1  0  0 |0  0  0  0 |1  0  0  0] 1   Reverse                       
[     8     |     4     |     0     |     8    ]     Nibbles of Reverse                0x8408

16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
 1 [0  0  0  0 |1  0  0  0 |0  0  0  1 |0  0  0  1]  Reciprocal                    
   [     0     |     8     |     1     |     1    ]  Nibbles of Reciprocal             0x0811

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16   Reverse reciprocal
16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0   Koopman
[1  0  0  0 |1  0  0  0 |0  0  0  1 |0  0  0  0] 1    
[     8     |     8     |     1     |     0    ]     Nibbles                           0x8810

Все известные полиномы генератора CRC степени $n$ имеют два общих шестнадцатеричных представления. В обоих случаях коэффициент $x^{n}$ опускается и понимается как 1.

Представление msbit-first представляет собой шестнадцатеричное число с $n$ бит, младший бит из которых всегда равен 1. Самый старший бит представляет коэффициент $x^{n-1}$ и младший бит представляет собой коэффициент $x^{0}$ .
Представление lsbit-first представляет собой шестнадцатеричное число с $n$ бит, старший бит из которых всегда равен 1. Самый старший бит представляет коэффициент $x^{0}$ и младший бит представляет собой коэффициент $x^{n-1}$ .

Форма msbit-first часто упоминается в литературе как нормальное представление, а форма lsbit-first называется обратным представлением. При реализации CRC важно использовать правильную форму. Если коэффициент $x^{n-1}$ бывает нулевым, формы можно отличить с первого взгляда, увидев, на каком конце установлен бит.

Чтобы еще больше запутать дело, статья П. Купмана и Т. Чакраварти ^[1]^[2] преобразует полиномы генератора CRC в шестнадцатеричные числа еще одним способом: сначала msbit, но включая $x^{n}$ коэффициент и опуская $x^{0}$ коэффициент. Преимущество этого представления «Купмана» состоит в том, что степень можно определить по шестнадцатеричной форме, а коэффициенты легко считывать в порядке слева направо. Однако он больше нигде не используется и не рекомендуется из-за риска путаницы.

Взаимные полиномы

создается Обратный полином путем присвоения $x^{i}$ через $x^{0}$ коэффициенты одного полинома к $x^{0}$ через $x^{i}$ коэффициенты нового полинома. То есть обратная степень $n$ полиномиальный $G(x)$ является $x^{n}G(x^{-1})$ .

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

Сила обнаружения ошибок

Способность CRC обнаруживать ошибки зависит от степени его ключевого полинома и от конкретного используемого ключевого полинома. «Полином ошибки» $E(x)$ представляет собой симметричную разность кодового слова полученного сообщения и правильного кодового слова сообщения. Ошибка останется незамеченной алгоритмом CRC тогда и только тогда, когда полином ошибки делится на полином CRC.

Поскольку CRC основан на делении, ни один полином не может обнаружить ошибки, состоящие из строки нулей, добавленных к данным, или из пропущенных начальных нулей. Однако см. Вариации .
Все однобитовые ошибки будут обнаружены с помощью любого полинома, содержащего как минимум два члена с ненулевыми коэффициентами. Полином ошибки $x^{k}$ , и $x^{k}$ делится только на многочлены $x^{i}$ где $i\leq k$ .
все две битовые ошибки, разделенные расстоянием меньшим, чем порядок примитивного полинома, который является коэффициентом полинома генератора Будут обнаружены . Полином ошибки в двухбитном случае равен $E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k$ . Как отмечалось выше, $x^{k}$ член не будет делиться на полином CRC, что оставляет $x^{i-k}+1$ срок. По определению, наименьшее значение ${i-k}$ такой, что многочлен делит $x^{i-k}+1$ полинома — порядок или показатель . Полиномы наибольшего порядка называются примитивными многочленами , а многочлены степени $n$ с двоичными коэффициентами имеют порядок $2^{n}-1$ .
Все ошибки в нечетном числе битов будут обнаруживаться полиномом, кратным $x+1$ . Это эквивалентно полиному, имеющему четное количество членов с ненулевыми коэффициентами. Эта емкость предполагает, что полином генератора является произведением $x+1$ и примитивный полином степени $n-i$ поскольку все примитивные полиномы, кроме $x+1$ иметь нечетное количество ненулевых коэффициентов.
Все пакетные ошибки длины $n$ будет обнаружен любым полиномом степени $n$ или больше, который имеет ненулевое значение $x^{0}$ срок.

(Кстати, нет смысла использовать многочлен с нулевым значением. $x^{0}$ срок. Напомним, что CRC — это остаток полиномиального времени сообщения. $x^{n}$ разделенное на полином CRC. Полином с нулем $x^{0}$ термин всегда имеет $x$ как фактор. Итак, если $K(x)$ является исходным полиномом CRC и $K(x)=x\cdot K'(x)$ , затем

M(x)\cdot x^{n-1}=Q(x)\cdot K'(x)+R(x)

M(x)\cdot x^{n}=Q(x)\cdot x\cdot K'(x)+x\cdot R(x)

M(x)\cdot x^{n}=Q(x)\cdot K(x)+x\cdot R(x)

То есть CRC любого сообщения с $K(x)$ полином такой же, как у того же сообщения с $K'(x)$ многочлен с добавленным нулем. Это просто пустая трата времени.)

Сочетание этих факторов означает, что хорошие полиномы CRC часто представляют собой примитивные полиномы (которые лучше всего обнаруживают 2-битные ошибки) или примитивные полиномы степени $n-1$ , умноженный на $x+1$ (который обнаруживает все нечетные числа битовых ошибок и имеет вдвое меньшую способность обнаружения двухбитных ошибок, чем примитивный полином степени $n$ ). ^[1]

Битфильтры

Техника анализа с использованием битфильтров ^[1] позволяет очень эффективно определять свойства данного порождающего полинома. Результаты следующие:

Все пакетные ошибки (кроме одной) длиной не длиннее полинома генератора могут быть обнаружены любым полиномом генератора. $1+\cdots +X^{n}$ . Сюда входят 1-битные ошибки (пакет длиной 1). Максимальная длина $n+1$ , когда $n$ — степень порождающего полинома (который сам имеет длину $n+1$ ). Исключением из этого результата является битовая комбинация, такая же, как и в полиноме генератора.
Все нечетные битовые ошибки обнаруживаются с помощью генераторных полиномов с четным числом членов.
2-битные ошибки на (кратном) расстоянии самого длинного битового фильтра четности до полинома генератора не обнаруживаются; все остальные обнаруживаются. Для степеней до 32 существует оптимальный порождающий полином этой степени и четного числа членов; в этом случае период, упомянутый выше, составляет $2^{n-1}-1$ . Для $n=16$ это означает, что блоки длиной 32 767 бит не содержат необнаруженных 2-битных ошибок. Для нечетного числа членов в полиноме генератора может быть период $2^{n}-1$ ; однако эти полиномы-генераторы (с нечетным числом членов) не обнаруживают все нечетное количество ошибок, поэтому их следует избегать. Список соответствующих генераторов с четным количеством термов можно найти по ссылке, указанной в начале этого раздела.
Все однобитовые ошибки в течение упомянутого выше периода битового фильтра (для четных членов полинома генератора) могут быть однозначно идентифицированы по их остатку. Таким образом, метод CRC можно использовать и для исправления однобитовых ошибок (в этих пределах, например, 32 767 бит с оптимальными полиномами генератора 16-й степени). Поскольку все нечетные ошибки оставляют нечетный остаток, можно различать все четные и четные ошибки, 1-битные ошибки и 2-битные ошибки. Однако, как и другие методы SECDED , CRC не всегда может отличить 1-битные ошибки от 3-битных ошибок. Когда в блоке возникают 3 или более битовых ошибки, коррекция битовых ошибок CRC сама по себе будет ошибочной и приведет к увеличению количества ошибок.

См. также

Ссылки

^ Jump up to: ^а ^б ^с Купман, Филип (июль 2002 г.). «32-битные циклические избыточные коды для интернет-приложений». Материалы Международной конференции по надежным системам и сетям (PDF) . стр. 459–468. CiteSeerX 10.1.1.11.8323 . дои : 10.1109/DSN.2002.1028931 . ISBN 978-0-7695-1597-7 . S2CID 14775606 . Проверено 14 января 2011 г. - проверка результатов Кастаньоли перебором и некоторыми новыми хорошими полиномами.
^ Купман, Филип; Чакраварти, Тридиб (июнь 2004 г.). «Выбор полинома циклического избыточного кода (CRC) для встроенных сетей». Международная конференция по надежным системам и сетям, 2004 г. (PDF) . стр. 145–154. CiteSeerX 10.1.1.648.9080 . дои : 10.1109/DSN.2004.1311885 . ISBN 978-0-7695-2052-0 . S2CID 793862 . Проверено 14 января 2011 г. – анализ коротких полиномов CRC для встроенных приложений

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

Купман, Фил. «Блог: Контрольная сумма и CRC Central» . — перечисляет полиномы CRC, дающие наилучшие расстояния Хэмминга .

[koop02-1] Jump up to: ^а ^б ^с Купман, Филип (июль 2002 г.). «32-битные циклические избыточные коды для интернет-приложений». Материалы Международной конференции по надежным системам и сетям (PDF) . стр. 459–468. CiteSeerX 10.1.1.11.8323 . дои : 10.1109/DSN.2002.1028931 . ISBN 978-0-7695-1597-7 . S2CID 14775606 . Проверено 14 января 2011 г. - проверка результатов Кастаньоли перебором и некоторыми новыми хорошими полиномами.

[koop04-2] Купман, Филип; Чакраварти, Тридиб (июнь 2004 г.). «Выбор полинома циклического избыточного кода (CRC) для встроенных сетей». Международная конференция по надежным системам и сетям, 2004 г. (PDF) . стр. 145–154. CiteSeerX 10.1.1.648.9080 . дои : 10.1109/DSN.2004.1311885 . ISBN 978-0-7695-2052-0 . S2CID 793862 . Проверено 14 января 2011 г. – анализ коротких полиномов CRC для встроенных приложений

[1]

[2]