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

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

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

Математика

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

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

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

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

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

На практике вычисления 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}}.}$

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

${\ 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 (х ^ {3} + х ^ {2} + х) = (х ^ {2} +1) (х + 1) -1 \ эквив (х ^ {2} +1) (х + 1 ) +1 {\ pmod {2}}.}$

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

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

Варианты

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

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

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

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

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

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

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

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

Эти инверсии чрезвычайно распространены, но выполняются не повсеместно, даже в случае полиномов 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] Полубайты реверса 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] Взаимный [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 степени ${\ displaystyle n}$имеют два общих шестнадцатеричных представления. В обоих случаях коэффициент${\ Displaystyle х ^ {п}}$ опускается и понимается как 1.

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

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

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

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

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

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

Уровень обнаружения ошибок

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

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

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

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

${\ Displaystyle М (х) \ CDOT х ^ {п} = Q (х) \ CDOT х \ CDOT K '(х) + х \ CDOT R (х)}$

${\ Displaystyle М (х) \ CDOT х ^ {п} = Q (х) \ CDOT К (х) + х \ CDOT R (х)}$

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

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

Битовые фильтры

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

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

См. Также

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

Ссылки

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