Почему CRC 32 Generator не делится на 11?

Question

Генератор CRC 32 - это 33-битный номер бина:

100000100110000010001110110110111

Согласно PDF-странице 18,

Нечетное количество битовых ошибок может быть обнаружено, если C(x) содержит коэффициент (x + 1)

CRC 32 должен удовлетворять свойству возможности обнаруживать любое нечетное количество битовых ошибок. Однако генератор CRC 32 (то есть C(x)) не делится на 11. Другими словами, полином CRC-32:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

не содержит фактор (x + 1),

Итак, как можно удовлетворить собственность?

Примечание: вам может быть полезно иметь онлайн арифметический калькулятор по модулю-2.

Answer 1

Не все полиномы CRC делятся на x+1. Существует компромисс между обнаружением однобитовых ошибок и двухбитовых ошибок. Это зависит от того, от какого источника шума вы пытаетесь защитить. Как вы заметили, обычно используемый Ethernet/gzip/etc. многочлен не делится на х + 1.

Полином CRC-32C (Кастаньоли) делится на x+1. Как это бывает, в целом он сильнее и является CRC-выбором для новых приложений. (На самом деле это произошло не просто - это было результатом исчерпывающего поиска.) Это также CRC, что Intel crc32 инструкция вычисляет.