CRC32校验是如何计算的？ [英] How is a CRC32 checksum calculated?
问题描述
也许我只是没有看到它，但是CRC32似乎不是必要的复杂，或不够随时随地解释，我可以在网上找到。
我理解它的要点是，它是从消息值的非承载基于arithmitic分工，由多项式除以剩余部分，但它的实际执行逃脱我。
我读过无痛指南CRC错误检测算法，我必须说这是没有痛苦。它越过理论的比较好，但笔者从来没有得到一个简单的这是它。他不说什么的参数为标准CRC32算法，但他忽略了实际制定出明确如何得到它。
这让我当他说，这是它，然后添加上的方式，它可以逆转或开始与不同的初始条件哦，并没有给出一个明确的答案部分是什么计算所有给予他刚加入的变化CRC32校验的最终途径。
总之，除此之外，有没有它是如何计算出一个简单的解释？
我试图在C code是如何形成的表，它包含如下：
为（i = 0; I＆LT; 256;我++）
{
TEMP = I;
为（J = 0; J＆下; 8; J ++）
{
如果（温度＆放大器; 1）
{
温度＆GT;＆GT; = 1;
临时^ = 0xEDB88320;
}
其他
{
温度＆GT;＆GT; = 1;
}
}
testcrc [I] =温度;
}
不过，这似乎生成我已经在互联网上其他地方找到值不一致的值。我可以用我找到了价值，但我想了解他们是如何来到他们。
在清理这些难以置信的混乱数量将是非常美联社preciated任何帮助。
有关CRC32多项式是：
0x04C11DB7
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
能够统计出是二进制：
100110000010001110110110111
随意数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 ^ 11倍11（但我们只1或0 pre位需要），所以我们扛过：
= 1X ^ 110 + 1×101 ^ + 1X ^ 100 + 11X ^ 11 + 1×10 ^ + 1X ^ 1 + X ^ 0
= 1X ^ 110 + 1×101 ^ + 1X ^ 100 + 1×^ 100 + 1×11 ^ + 1X ^ 10 + 1×^ 1 + X ^ 0
= 1X ^ 110 + 1×101 ^ + 1X ^ 101 + 1×11 ^ + 1X ^ 10 + 1×^ 1 + X ^ 0
= 1X ^ 110 + 1×110 ^ + 1X ^ 11 + 1×10 ^ + 1X ^ 1 + X ^ 0
= 1X ^ 111 + 1×11 ^ + 1X ^ 10 + 1×^ 1 + X ^ 0但数学家改变了规则，使其mod2.所以基本上任何二进制多项式模2只是除了没有进位或异或。因此，我们的原方程如下：
=（1X ^ 110 + 1×101 ^ + 1X ^ 100 + 11X ^ 11 + 1×10 ^ + 1X ^ 1 + X ^ 0）MOD 2
=（1×110 ^ + 1X ^ 101 + 1×^ 100 + 1×11 ^ + 1X ^ 10 + 1×^ 1 + X ^ 0）
= X ^ 6 + X ^ 5 + X ^ 4 + 3 * X ^ 3 + X ^ 2 + X ^ 1 + X ^ 0（或者说原来我们有号码）我知道这是一个信仰的飞跃，但是这超出了我的能力，作为一个行程序员。如果你是一个铁杆CS-学生或工程师，我挑战打破这种下来。每个人都将受益于这种分析。
所以要制定出一个完整的例子：
原始消息：1101011011
保利：10011
附加W¯¯零后留言：11010110110000现在，我们只需使用CRC聚划分扩充消息
算术。这是相同的分区如前： 1100001010 =智商（无人问津的商数）
_______________
10011）11010110110000 =扩充消息（1101011011 + 0000）
= 10011保利,,。,, ....
----- ,,。,, ....
10011。,, ....
10011。,, ....
-----。,, ....
00001。,, ....
00000。,, ....
----- ,, ....
00010 ,, ....
00000 ,, ....
----- ,, ....
00101，...
00000，...
----- ....
01011 ....
00000 ....
-----....
10110 ...
10011 ...
-----...
01010 ..
00000 ..
----- ..
10100。
10011。
-----。
01110
00000
-----
1110 =余数=校验!!!!该部门产生的商，这是我们扔掉，和余数，
这是计算的校验和。这结束的计算。
一般，校验然后将其附加到消息，并将结果
传输。在这种情况下，传输将是：11010110111110。仅使用一个32位的数字作为除数，并使用你的整个流作为你的股息。扔掉商，并保持剩余部分。钉在你的消息结束剩下的，你有一个CRC32。
普通人回顾：
QUOTIENT
----------
DIVISOR）股息
=余
- 取前32位。
- 移位位
- 如果32位小于除数转到步骤2。
- XOR被DIVISOR 32位。转到第2步。
（注意，该流具有由32位是可分的或应当paddded，例如，一个8位的ANSI流必须被填充。此外，在流的末尾，这个划分停止。）
Maybe I'm just not seeing it, but CRC32 seems either needlessly complicated, or insufficiently explained anywhere I could find on the web.
I understand the gist of it is that it is the remainder from a non-carry based arithmitic division of the message value, divided by the polynomial, but the actual implementation of it escapes me.
I've read A Painless Guide To CRC Error Detection Algorithms, and I must say it was not painless. It goes over the theory rather well, but the author never gets to a simple "This is it." He does say what the parameters are for the standard CRC32 algorithm is, but he neglects to actually lay out clearly how you get to it.
The part that gets me is when he says "this is it" and then adds on, "oh by the way, it can be reversed or started with different initial conditions," and doesn't give a clear answer of what the final way of calculating a CRC32 checksum given all of the changes he just added.
Anyway, besides that, is there a simple explanation of how it is calculated?
I attempted to code in C how the table is formed, and it is included below:
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; }But this seems to generate values inconsistent with values I have found elsewhere on the Internet. I could use the values I found, but I wanted to understand how they arrived at them.
Any help in clearing up these incredibly confusing numbers would be very appreciated.
解决方案The polynomial for CRC32 is:
0x04C11DB7
x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Which works out to be in binary:
100110000010001110110110111
Feel free to count the 1s and 0s, but you'll find they match up with the polynomial where 1 is bit 0 (or the first bit) and x is bit 1 (or the second bit).
Why this polynomial? Because there needs to be a standard given polynomial and the standard was set by IEEE 802.3. Also it is extremely difficult to find a polynomial that works effectively.
You can think of the CRC-32 as a series of "Binary Arithmetic with No Carries" or basically XOR and shift operations. This is technically called Polynomial Arithmetic.
To better understand, think of this situation:
(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^0If we assume x is base 2 then we get:
x^7 + x^3 + x^2 + x^1 + x^0Why? Because 3x^3 is 11x^11 (but we need only 1 or 0 pre digit) so we carry over:
=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^0But mathematicians changed the rules so that it is mod 2. So basically any binary polynomial mod 2 is just addition without carry or XORs. So our original equation looks like:
=( 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)I know this is a leap of faith but this is beyond my capability as a line-programmer. If you are a hard-core CS-student or engineer I challenge to break this down. Everyone will benefit from this analysis.
So to work out a full example:
Original message : 1101011011 Poly : 10011 Message after appending W zeros : 11010110110000 Now we simply divide the augmented message by the poly using CRC arithmetic. This is the same division as before: 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!!!! The division yields a quotient, which we throw away, and a remainder, which is the calculated checksum. This ends the calculation. Usually, the checksum is then appended to the message and the result transmitted. In this case the transmission would be: 11010110111110.Only use a 32-bit number as your divisor and use your entire stream as your dividend. Throw out the quotient and keep the remainder. Tack the remainder on the end of your message and you have a CRC32.
Average guy review:
QUOTIENT ---------- DIVISOR ) DIVIDEND = REMAINDER
- Take the first 32 bits.
- Shift bits
- If 32 bits are less than DIVISOR, goto step 2.
- XOR 32 bits by DIVISOR. Goto step 2.
(Note that the stream has to be dividable by 32 bits or it should be paddded. For example, an 8-bit ANSI stream would have to be padded. Also at the end of the stream, the division is halted.)
这篇关于CRC32校验是如何计算的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
