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

Question

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

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

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

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

Answer 1

1. Добавим n нули, когда вычисления n -битовый CRC, потому что, при добавлении ЦИК к сообщению и отправке целого (обычная практика в телекомов):
   • Это позволяет получающей чтобы обрабатывать биты CRC так же, как и остальную часть сообщения, что приводит к известному остатку для любой безошибочной передачи. Это особенно полезно, когда в конце сообщения указано что-то, что следует за CRC (обычная практика); на стороне приема он сохраняет бит-бит n, а на стороне передачи он практически не добавляет сложности (дополнительные условия x(n) сводятся к тому, что бит ИД заставляет биты сообщения равными нулю во время передачи CRC, а дополнительные этапы восстановления n выполняются как CRC передается).
     Математически отправленный CRC - это (M(x) * x^n) mod P(x) = R(x) (возможно, в пределах некоторой константы или, возможно, с некоторыми заданными битами, добавленными в начале M(x), что соответствует инициализации регистра CRC), а CRC, вычисленный на принимающей стороне, конкатенация M(x) и R(x), то есть
     (M(x) * x^n + R(x)) mod P(x), которая равна нулю (или указанной постоянной).
   • Это гарантирует, что всплеск ошибок, влияющих как на конец сообщения, так и на непрерывный CRC, будет иметь полный уровень защиты, предоставляемый выбором полинома. В частности, если мы вычислили C(x) как M(x) mod P(x), перевернув последний бит M(x), и последний бит C(x) исчезнет, ​​когда большинство полиномов, используемых при обнаружении ошибок, гарантируют, что любая двубитная ошибка обнаружена до некоторого большого размера сообщения.
2. Общепринятой практикой является наличие полиномов CRC, используемых для обнаружения ошибок, делящихся на x+1, поскольку оно обеспечивает обнаружение любой ошибки, влияющей на нечетное число бит. Однако эта практика не является универсальной и иногда предотвращает выбор лучшего полинома для некоторых полезных определений лучше, включая максимизацию длины сообщения, так что ошибки m всегда обнаруживаются (при отсутствии потерь синхронизации) для некоторых комбинаций m и n. В частности, если мы хотим иметь возможность обнаруживать любую 2-битную ошибку для самого длинного сообщения (которое будет содержать два бита, включая n -битный CRC), нам нужно, чтобы полином был примитивным, таким образом, неприводимым, таким образом (для n> 1) не делится на x+1.
3. Универсальной практикой является использование полиномов CRC для обнаружения ошибок, не делящихся на x, поскольку в противном случае последний бит генерируемого CRC был бы постоянным и не помог бы обнаружить ошибки в остальной части сообщения + CRC.