也许我只是没有看到它,但CRC32似乎不必要地复杂化,或者在我能在网上找到的任何地方都没有充分解释.
我理解它是消息值的非基于进位的算术除法的余数除以(生成器)多项式,但它的实际实现逃脱了我.
我读过CRC无错误检测算法的指南,我必须说它不是无痛的.它完全超越了理论,但作者从未得到过简单的"就是这样".他确实说过标准CRC32算法的参数是什么,但是他忽略了如何清楚地列出它.
得到我的部分就是当他说"这就是它"然后补充说,"顺便说一句,它可以逆转或以不同的初始条件开始",并没有给出最终方式的明确答案在给出他刚刚添加的所有更改的情况下计算CRC32校验和.
我试图在C中编写表格的形式:
for (i = 0; i < 256; i++)
{
temp = i;
for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}
但这似乎产生的价值与我在互联网上其他地方找到的价值观不一致.我可以使用我在网上找到的值,但我想了解它们是如何创建的.
任何帮助清除这些令人难以置信的令人困惑的数字将非常感激.
小智 96
CRC32的多项式是:
0x 04 C1 1D B7
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
这是二进制的:
1001100 0001 0001 1101 1011 0111
您可以随意计算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
如果我们假设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
但是数学家改变了规则,因此它是mod 2.所以基本上任何二元多项式mod 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
现在我们使用CRC算法将增强的消息除以Poly.这是与以前相同的部门:
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位分割,或者它应该被填充.例如,必须填充8位ANSI流.同样在流的末尾,分割被暂停.)
vaf*_*lec 11
我发布了一个关于 CRC-32 哈希的教程，在这里： CRC-32 哈希教程 - AutoHotkey 社区
在这个例子中，我演示了如何计算 'ANSI'（每个字符 1 个字节）字符串 'abc' 的 CRC-32 哈希：
calculate the CRC-32 hash for the 'ANSI' string 'abc':
inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7
start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)
reverse the bits in each byte:
10000110 01000110 11000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)
01111001101110010011100111111111000000000000000000000000
next we will perform 'CRC division':
a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'
note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit
'CRC division':
'divide' by the polynomial 0x104C11DB7:
01111001101110010011100111111111000000000000000000000000
100000100110000010001110110110111
---------------------------------
111000100010010111111010010010110
100000100110000010001110110110111
---------------------------------
110000001000101011101001001000010
100000100110000010001110110110111
---------------------------------
100001011101010011001111111101010
100000100110000010001110110110111
---------------------------------
111101101000100000100101110100000
100000100110000010001110110110111
---------------------------------
111010011101000101010110000101110
100000100110000010001110110110111
---------------------------------
110101110110001110110001100110010
100000100110000010001110110110111
---------------------------------
101010100000011001111110100001010
100000100110000010001110110110111
---------------------------------
101000011001101111000001011110100
100000100110000010001110110110111
---------------------------------
100011111110110100111110100001100
100000100110000010001110110110111
---------------------------------
110110001101101100000101110110000
100000100110000010001110110110111
---------------------------------
101101010111011100010110000001110
100000100110000010001110110110111
---------------------------------
110111000101111001100011011100100
100000100110000010001110110110111
---------------------------------
10111100011111011101101101010011
we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53
note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bit
XOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2
thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2
CRC非常简单; 您将多项式表示为位和数据,并将多项式除以数据(或者将数据表示为多项式并执行相同的操作).余数在0和多项式之间是CRC.您的代码有点难以理解,部分原因是它不完整:未声明temp和testcrc,因此不清楚索引的内容以及通过算法运行的数据量.
理解CRC的方法是尝试使用短多项式(16位左右)计算一些数据,这可能是短多项式--4位.如果你以这种方式练习,你会真正理解你如何编写它.
如果你经常这样做,CRC在软件中的计算速度很慢.硬件计算效率更高,只需几个门.
小智 7
对于IEEE802.3，CRC-32。将整个消息视为串行位流，在消息末尾附加32个零。接下来，您必须反转消息的每个字节的位，并对前32位进行1的补码。现在除以CRC-32多项式0x104C11DB7。最后，您必须对该除法的32位余数进行1的补码位反转，将余数的4个字节中的每个字节反转。这将成为附加在消息末尾的32位CRC。
此奇怪过程的原因是，第一个以太网实现会一次将消息串行化一个字节，然后首先传输每个字节的最低有效位。然后，串行比特流经过串行CRC-32移位寄存器计算，该过程得到了简单的补充，并在消息完成后通过导线发送出去。对消息的前32位进行补充的原因是，即使消息为全零，您也不会获得全零的CRC。
除了维基百科循环冗余检查和CRC文章的计算之外,我还发现了一篇题为" 逆转CRC - 理论与实践*"的论文作为一个很好的参考.
计算CRC的方法主要有三种:代数方法,面向位的方法和表驱动方法.在逆转CRC - 理论与实践*中,这三种算法/方法中的每一种都在理论中通过附录中的C编程语言中的CRC32的实现来解释.
*PDF链接
反转CRC - 理论与实践.
HU柏林公开报道
SAR-PR-
2006-05
2006年5月
作者:
Martin Stigge,HenrykPlötz,WolfMüller,Jens-Peter Redlich