Полином для CRC32 является:
0x 04 С1 1D B7
х + X + X + X + х + x + x + x + x + х + х + х + х + 1
, который работает, чтобы быть в двоичном виде:
Вы можете считать 1 и 0, но вы увидите, что они совпадают с многочленом, где 1 является бит 0 (или первый бит) и x является бит 1 (или второй бит).
Почему этот многочлен? Потому что должен быть стандартный заданный полином, и стандарт был установлен IEEE 802.3. Также чрезвычайно сложно найти многочлен, который эффективно обнаруживает различные битовые ошибки.
Вы можете думать о CRC-32 как о серии «Двоичная арифметика без несушек» или в основном «XOR и операции сдвига». Это технически называется полиномиальной арифметикой.
Чтобы лучше понять это, думает, это умножение:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
Если предположить й основание 2, то мы получим:
x^7 + x^3 + x^2 + x^1 + x^0
Почему? Поскольку 3x^3 является 11x^11 (но нам нужно только 1 или 0 до цифры), поэтому перенесет:
=1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111 + 1x^11 + 1x^10 + 1x^1 + x^0
Но математики изменили правила так, что модуль 2. Таким образом, в основном любой двоичный полином по модулю 2 это просто дополнение без переноса или XOR.Таким образом, наше исходное уравнение выглядит следующим образом:
=(1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0) MOD 2
=(1x^110 + 1x^101 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)
Я знаю, что это прыжок веры, но это за пределами моей способности как линии-программист. Если вы являетесь основателем CS-студент или инженером, я бросаю вызов сломать это. Этот анализ будет полезен всем.
Так отработать полный пример:
Original message : 1101011011
Polynomial of (W)idth 4 : 10011
Message after appending W zeros : 11010110110000
Теперь разобьет дополненное сообщение в Poly с использованием CRC арифметики. Это же разделение, как и раньше:
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!
Разделение дает фактор, который мы выбрасываем, а остаток, который вычисленная контрольная сумма. Это завершает расчет. Обычно контрольная сумма добавляется к сообщению и передается результат. В этом случае передача будет: 11010110111110.
Используйте только 32-битное число в качестве делителя и использовать весь поток в качестве дивидендов. Выбросьте фактор и сохраните остаток. Отложите остаток в конце вашего сообщения, и у вас есть CRC32.
Средняя оценка парень:
QUOTIENT
----------
DIVISOR) DIVIDEND
= REMAINDER
- Возьмите первые 32 бита.
- сдвига битов
- Если 32 бит меньше, чем DIVISOR, перейти к шагу 2.
- исключающее 32 битов с помощью DIVISOR. Перейдите к шагу 2.
(Обратите внимание, что поток должен быть разделен на 32 бита или должен быть дополнен. поток, деление прекращается.)
Ваш код для генерации таблицы CRC32 выглядит правильно. Ваш lsbit-first (* reverseed *) CRC32-многочлен '0xEDB88320' также может быть записан в msbit-first (* normal *) как' 0x04C11DB7'. Были ли значения таблиц, найденные вами в другом месте, с использованием одного и того же полинома CRC? – jschmier