Математика циклических проверок избыточности - Mathematics of cyclic redundancy checks

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

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

Математика

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

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

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

{displaystyle R (x) = M (x) cdot x ^ {n}, {mod {,}} G (x).}

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

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

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

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

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

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

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

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

{displaystyle 2x = x + x = x imes (1 + 1) Equiv x imes 0 = 0 {pmod {2}}.}

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

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

{displaystyle (x ^ {2} + x) (x + 1) = x ^ {3} + 2x ^ {2} + xequiv 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) -1equiv (x ^ {2} +1) (x + 1) +1 {pmod {2}}.}

Деление дает частное от Икс² + 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 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.

Регистр сдвига может быть инициализирован единицами вместо нулей. Это эквивалентно инвертированию первого ${displaystyle n}$ биты сообщения перед подачей их в алгоритм. Уравнение CRC становится ${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} ight), {mod {,}} G (x)}$ .

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

{displaystyle M (x)}

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

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

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

Таким образом, CRC можно проверить либо очевидным методом вычисления CRC в сообщении, его инвертирования и сравнения с CRC в потоке сообщений, либо путем вычисления CRC для всего кодового слова и сравнения его с ожидаемым фиксированным значением. ${displaystyle C (x)}$ , называемый контрольным полиномом, вычетом или магическое число. Это можно вычислить как ${displaystyle C (x) = left (сумма _ {i = n} ^ {2n-1} x ^ {i} ight), {mod {,}} G (x)}$ или, что то же самое, вычислением немодифицированного CRC сообщения, состоящего из ${displaystyle n}$ те, ${displaystyle M (x) = сумма _ {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 степени ${displaystyle n}$ имеют два общих шестнадцатеричных представления. В обоих случаях коэффициент ${displaystyle x ^ {n}}$ опускается и понимается как 1.

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

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

Чтобы еще больше запутать ситуацию, статья П. Купмана и Т. Чакраварти ^[1]^[2] преобразует полиномы генератора CRC в шестнадцатеричные числа еще одним способом: msbit-first, но включая ${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, является то, что они имеют точно такую же способность обнаруживать ошибки, что и многочлены, которым они являются обратными. Обратная величина полинома порождает то же кодовые слова, только бит обратный - то есть, если все, кроме первого ${displaystyle n}$ биты кодового слова под исходным многочленом берутся, меняются местами и используются в качестве нового сообщения, CRC этого сообщения под обратным многочленом равняется обратному первому ${displaystyle n}$ биты исходного кодового слова. Но обратный многочлен не совпадает с исходным многочленом, и CRC, сгенерированные с его помощью, не такие же (даже по модулю обращения битов), как те, которые сгенерированы исходным многочленом.

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

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

Поскольку CRC основан на делении, ни один полином не может обнаружить ошибки, состоящие из строки нулей, добавленных к данным, или отсутствующих начальных нулей. Однако см. Вариации.
Все одиночные битовые ошибки будут обнаружены любым полиномом, содержащим как минимум два члена с ненулевыми коэффициентами. Полином ошибки равен ${displaystyle x ^ {k}}$ , и ${displaystyle x ^ {k}}$ делится только на многочлены ${displaystyle x ^ {i}}$ где ${displaystyle ileq k}$ .
Все две битовые ошибки, разделенные расстоянием меньше, чем порядок из примитивный полином, который является множителем порождающего полинома будет обнаружен. Полином ошибки в двухбитном случае равен ${displaystyle E (x) = x ^ {i} + x ^ {k} = x ^ {k} cdot (x ^ {i-k} +1) ,; i> k}$ . Как отмечалось выше, ${displaystyle x ^ {k}}$ член не будет делиться на полином CRC, который оставляет ${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}}$ срок.

(Кстати, никогда не стоит использовать полином с нулевым ${displaystyle x ^ {0}}$ срок. Напомним, что CRC - это остаток полиномиального времени сообщения. ${displaystyle x ^ {n}}$ делится на полином CRC. Полином с нулем ${displaystyle x ^ {0}}$ термин всегда имеет ${displaystyle x}$ как фактор. Так что если ${displaystyle K (x)}$ является исходным полиномом CRC и ${displaystyle K (x) = xcdot 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 xcdot K '(x) + xcdot R (x)}

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

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

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

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

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

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

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

использованная литература

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

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

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

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

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

[1]

[2]