Полином для CRC32:
x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1
Или в шестнадцатеричном и двоичном виде:
0x 01 04 C1 1DB7
1 0000 0100 1100 0001 0001 1101 1011 0111
Самый высокий член (x 32 ) обычно не записывается явно, поэтому он может быть представлен в шестнадцатеричном виде простокак
0x 04 C1 1D B7
Не стесняйтесь считать 1 и 0, но вы обнаружите, что они совпадают с полиномом, где 1бит 0 (или первый бит) и x - это бит 1 (или второй бит).
Почему этот многочлен?Потому что должен быть стандарт, заданный полином, и стандарт был установлен IEEE 802.3.Кроме того, чрезвычайно трудно найти полином, который эффективно обнаруживает различные битовые ошибки.
Вы можете думать о CRC-32 как о серии "двоичной арифметики без переносов" или в основном "операциях XOR и shift",Технически это называется полиномиальной арифметикой.
Чтобы лучше понять это, подумайте об этом умножении:
(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
Если мы предположим, что x является основанием 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 бита.
- Shiftбиты
- Если 32 бита меньше, чем DIVISOR, перейдите к шагу 2.
- XOR 32 бита от DIVISOR.Перейдите к шагу 2.
(Обратите внимание, что поток должен делиться на 32 бита, или он должен быть дополнен. Например, 8-битный поток ANSI должен быть дополнен. Также наконец потока, разделение остановлено.)