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

Методы обнаружения и исправления ошибок в коммуникациях

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

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

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

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

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

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

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

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

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

Программные реализации иногда разделяют сообщение на части и сравнивают полученное значение со значением, восстановленным из полученного сообщения, но аппаратные реализации неизменно обнаруживают, что описанное выше полное разделение является более простым. ${\displaystyle R(x)}$

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

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}}.}$

Мы также можем разделить многочлены mod 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}}.}$

Деление дает частное с остатком −1, которое, поскольку оно нечетное, имеет последний бит 1. ${\displaystyle x^{2}+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 с делением полной ширины Последнее не даст остаток 0, ни , но Это не делает проверку CRC более сложной, вам просто нужно знать ожидаемый шаблон. ${\displaystyle S(x)}$ ${\displaystyle (x^{n}+1)/(x+1)}$ ${\displaystyle x^{6}+x^{4}+x^{2}+1.}$ ${\displaystyle R(x)=M(x)\cdot x^{n}{\bmod {G}}(x)+S(x)}$ ${\displaystyle W(x)\cdot x^{n}{\bmod {G}}(x).}$ ${\displaystyle S(x)}$ ${\displaystyle S(x)\cdot x^{n}{\bmod {G}}(x).}$
• Длинное деление может начинаться с ненулевого остатка. Остаток обычно вычисляется с использованием -битного регистра сдвига, содержащего текущий остаток, в то время как биты сообщения добавляются, и выполняется сокращение по модулю. Обычное деление инициализирует регистр сдвига нулем, но вместо этого он может быть инициализирован ненулевым значением. (Опять же, наиболее распространены все единицы, но можно использовать любой шаблон.) Это эквивалентно добавлению (XOR) шаблона инициализации с первыми битами сообщения перед их подачей в алгоритм. Уравнение CRC становится , где - длина сообщения в битах. Изменение, которое это накладывает на, является функцией порождающего полинома и длины сообщения, . ${\displaystyle n}$ ${\displaystyle G(x)}$ ${\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 \sum _{i=m}^{m+n-1}x^{i}\,{\bmod {\,}}G(x)}$

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

Аналогично, использование ненулевого остатка обнаруживает конечные нулевые биты, добавленные к сообщению. Если сообщение, защищенное CRC, имеет добавленный нулевой бит, полученный полином будет Если первый делится на порождающий полином, то и второй делится. Использование ненулевого остатка , добавление нулевого бита приведет к другому остатку , и, следовательно, будет обнаружен дополнительный бит. ${\displaystyle W(x)}$ ${\displaystyle W(x)\cdot x.}$ ${\displaystyle S(x)}$ ${\displaystyle S(x)\cdot x{\bmod {G}}(x)}$

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

Эти инверсии чрезвычайно распространены, но не выполняются повсеместно, даже в случае полиномов CRC-32 или CRC-16-CCITT. Они почти всегда включаются при отправке сообщений переменной длины, но часто опускаются при отправке сообщений фиксированной длины, поскольку проблема добавления нулевых битов возникает реже.

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

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

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

Эту битовую строку затем можно преобразовать в двоичное число, используя одно из двух соглашений:

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

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

Например, полином CCITT степени 16 в описанных формах (биты внутри квадратных скобок включены в представление слова; биты снаружи подразумеваются как 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-first, но включая коэффициент и опуская коэффициент. Это представление «Купмана» имеет то преимущество, что степень может быть определена из шестнадцатеричной формы, а коэффициенты легко считываются в порядке слева направо. Однако оно больше нигде не используется и не рекомендуется из-за риска путаницы. ${\displaystyle x^{n}}$ ${\displaystyle x^{0}}$

Взаимные многочлены

Обратный многочлен создается путем присвоения сквозных коэффициентов одного многочлена сквозным коэффициентам нового многочлена. То есть, обратная величина степени многочлена равна . ${\displaystyle x^{n}}$ ${\displaystyle x^{0}}$ ${\displaystyle x^{0}}$ ${\displaystyle x^{n}}$ ${\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). Поскольку все нечетные ошибки оставляют нечетный остаток, все четные — четный остаток, можно различать ошибки в одном бите и ошибки в двух битах. Однако, как и другие методы SECDED , CRC не всегда могут различать ошибки в одном бите и ошибки в трех битах. Когда в блоке возникает 3 или более ошибок бита, исправление ошибок бита CRC само по себе будет ошибочным и приведет к большему количеству ошибок.

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

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

Ссылки

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

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

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