-- TOC --
记得好几次都想彻底搞清楚如何计算CRC，以及CRC背后的原理，但总是被那些让人迷惑的专业术语劝退了......
CRC：Cyclic Redundancy Codes
作用：用户传输过程的差错监测，比如Ethernet就采用CRC。
生成多项式：就这个东西最吓人...
CRC的计算过程类似除法，而这个除数（divisor），就是所谓的生成多项式，generator polynomial。比如，如果除数是10011，等价于一个多项式：
\(x^4+x^1+x^0\)
多项式的宽度W：即多项式最高位的次数。比如上面的10011，宽为4。
刚才说类似除法，除法计算过程中的减法，被XOR替代了。具体计算时，先在原始信息后面补W个0。
下面是一个完整的CRC计算过程：
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,.,,....
-----,.,,....
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.
接收端收到信息后，用相同的生成多项式，即所谓的除数，进行相同的计算，结果为0,即表示校验OK。
以上就是CRC纯计算部分。
设计生成多项式是个技术活，它会显著影响差错检查的效果。不懂，也不要自己搞，各种标准都已经将这部分定义清楚：
Some popular polys are:
16 bits: (16,12,5,0) [X25 standard]
(16,15,2,0) ["CRC-16"]
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
显然CRC的计算需要速度，直接先出上述计算过程的代码，速度是不能满足要求的。因此，现在主流计算方法是Table-Drive，细节暂略。
参考：http://www.ross.net/crc/download/crc_v3.txt
本文链接：https://cs.pynote.net/ag/202303051/
-- EOF --
-- MORE --