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

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

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

Математика [ править ]

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

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

Вот полином исходного сообщения и полином генератора степеней . Биты являются исходным сообщением с добавленными нулями в конце. Контрольная сумма CRC формируется из коэффициентов полинома остатка , степень которого строго меньше, чем . Фактор-полином не представляет интереса. Используя операцию по модулю , можно сказать, что${\ Displaystyle М (х)}$${\ Displaystyle G (х)}$${\ displaystyle n}$${\ Displaystyle М (х) \ CDOT х ^ {п}}$${\ displaystyle n}$${\ Displaystyle R (х)}$${\ displaystyle n}$${\ Displaystyle Q (х)}$

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

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

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

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

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

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

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

${\ displaystyle (x ^ {3} + x) + (x + 1) = x ^ {3} + 2x + 1 \ Equiv x ^ {3} +1 {\ pmod {2}}.}$

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

${\ displaystyle 2x = x + x = x \ times (1 + 1) \ Equiv x \ times 0 = 0 {\ pmod {2}}.}$

Сложение полиномов по модулю 2 аналогично побитовой операции XOR . Поскольку XOR является обратным самому себе, полиномиальное вычитание по модулю 2 совпадает с побитовым XOR.

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

${\ displaystyle (x ^ {2} + x) (x + 1) = x ^ {3} + 2x ^ {2} + x \ Equiv x ^ {3} + x {\ pmod {2}}.}$

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

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

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

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

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

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

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

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

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

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

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

Причина использования этого метода заключается в том, что немодифицированный CRC не различает два сообщения, которые отличаются только количеством начальных нулей, поскольку начальные нули не влияют на значение . Когда эта инверсия выполняется, CRC действительно различает такие сообщения.${\displaystyle M(x)}$

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

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

Таким образом, CRC может быть проверена либо очевидным методом вычисления CRC для сообщения, его инвертирования и сравнения с CRC в потоке сообщений, либо путем вычисления CRC для всего кодового слова и сравнения его с ожидаемым фиксированным значением , называется проверочным полиномом, остатком или магическим числом . Это может быть вычислено как , или , что эквивалентно, вычисляя немодифицированного CRC сообщени , состо щей из них, .${\displaystyle C(x)}$${\displaystyle C(x)=\left(\sum _{i=n}^{2n-1}x^{i}\right)\,{\bmod {\,}}G(x)}$${\displaystyle n}$${\displaystyle 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 коэффициент 1 [0 0 0 1 | 0 0 0 0 | 0 0 1 0 | 0 0 0 1] Нормальный  [1 | 0 | 2 | 1] Нормальные полубайты 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 Реверс [8 | 4 | 0 | 8] Полубайты реверса 0x840816 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] Взаимный  [0 | 8 | 1 | 1] Полубайты взаимности 0x0811 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Обратный обратный16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Купман[1 0 0 0 | 1 0 0 0 | 0 0 0 1 | 0 0 0 0] 1 [8 | 8 | 1 | 0] Полубайты 0x8810

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

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

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

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

Взаимные полиномы [ править ]

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

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

Уровень обнаружения ошибок [ править ]

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

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

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

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

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

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

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

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

Битовые фильтры [ править ]

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

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

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

• Редукция Барретта
• Код исправления ошибок
• Список алгоритмов контрольной суммы
• Паритет (телекоммуникации)
• Полиномиальные представления циклических проверок избыточности

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

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