Несколько вопросов об основах CRC

Я инженер-электронщик и не считаю важным рассматривать CRC с чисто математической точки зрения. Однако у меня есть следующие вопросы:

  1. Почему мы добавляем n нулей к сообщению, когда вычисляем CRC, если n — это степень полинома генератора? Я видел это в длинном делении по модулю 2, а также в аппаратной реализации CRC.

  2. Почему мы хотим, чтобы образующий многочлен делился на (x+1)?

  3. Почему мы хотим, чтобы образующий многочлен не делился на x?


checksum crc polynomials modulo
person quantum231    schedule 17.06.2016    source источник

Ответы (1)


arrow_upward
8
arrow_downward

  1. We add n zeros when computing an n-bit CRC because, when appending the CRC to the message and sending the whole (a usual practice in telecoms):
    • That allows the receiving side to process the bits of the CRC just as the rest of the message is, leading to a known remainder for any error-free transmission. This is especially useful when the end of the message is indicated by something that follows the CRC (a common practice); on the receiving side it saves an n bit buffer, and on the transmit side it adds virtually no complexity (the extra terms of x(n) reduce to an AND gate forcing message bits to zero during CRC transmission, and the n extra reduction steps are performed as the CRC is transmitted).
      Mathematically, the CRC sent is (M(x) * x^n) mod P(x) = R(x) (perhaps, within some constant, or/and perhaps with some prescribed bits added at beginning of M(x), corresponding to an initialization of the CRC register), and the CRC computed on the receiving side is over the concatenation of M(x) and R(x), that is
      (M(x) * x^n + R(x)) mod P(x), which is zero (or said constant).
    • Это гарантирует, что пакет ошибок, влияющий как на конец сообщения, так и на непрерывный CRC, получит преимущество от полного уровня защиты, обеспечиваемого выбором полинома. В частности, если бы мы вычислили C(x) как M(x) mod P(x), перестановка последнего бита M(x) и последнего бита C(x) осталась бы незамеченной, тогда как большинство полиномов, используемых при обнаружении ошибок, гарантируют, что любая двухбитовая ошибка будет обнаружена вплоть до некоторого большого размера сообщения.
  2. Общепринятой практикой является использование полиномов CRC для обнаружения ошибок, кратных x+1, поскольку это гарантирует обнаружение любой ошибки, влияющей на нечетное число битов. Однако эта практика не универсальна, и иногда она может помешать выбору лучшего полинома для некоторых полезных определений лучшего, включая максимизацию длины сообщения, чтобы всегда обнаруживались ошибки m (при условии отсутствия потери синхронизации), для некоторых комбинаций m и n. В частности, если мы хотим обнаружить любую 2-битную ошибку для самого длинного сообщения (которое будет состоять из 2n-1 бит, включая n-бит CRC), нам нужно, чтобы полином был примитивный, таким образом неприводимый, таким образом (для n> 1) не делится на x+1.
  3. Универсальной практикой является использование полиномов CRC для обнаружения ошибок, не кратных x, потому что в противном случае последний сгенерированный бит CRC был бы постоянным и не помог бы в обнаружении ошибок в остальной части сообщения + CRC.
person fgrieu    schedule 17.06.2016
comment
Очень хороший ответ. +1. Я бы только добавил, что добавление n нулей является частью определения CRC, но почти никогда не является частью реализации. CRC в программном или аппаратном обеспечении может быть и почти всегда реализован, чтобы избежать этих дополнительных n шагов. Для 3 я бы сказал, что это действительно универсальный. Это не CRC, если многочлен не имеет члена 1. - person Mark Adler; 18.06.2016
comment
@Mark Adler: включил ваши комментарии. Я думаю, вы Марк Адлер из Adler-32 славы, спасибо за это! - person fgrieu; 18.06.2016
comment
хммм, мне нужно больше подумать над ответом 2. Кстати, в 2 что вы имеете в виду, что полином не может быть неприводимым. Зачем нам неприводимый многочлен? - person quantum231; 18.06.2016
comment
@ quantum231: исправил мой аргумент о 2, который был неверным в его обосновании, поскольку когда-то использовал неприводимые полиномы. Теперь я привожу по крайней мере одну вескую причину: полином может быть примитивным, чтобы максимизировать длину сообщения, для которого обнаруживаются все 2-битные ошибки. - person fgrieu; 19.06.2016