CRC16算法学习笔记_crc16多项式简化

一.CRC原理
CRC(Cyclic Redundancy Check）即循环冗余校检码，和奇偶校检码一样，是用来检验数据传输的错误的，其原理用到的是多项式除法。
首先一串比特流，可以表示为一个F2域上的多项式，比如10110110 可以表示为g(x) = x^7 + x^5 +x^4 + x^2 + x^1 ,我们所要做的是找到一个不可约多项式，比如h(x) = x^8+x^6+x^4+x^3+x^2+x,然后将g(x)乘以x^8，即比特流左移8位，然后将其除以h(x)， 所得到的余数即为我们要的CRC码。
上面的例子是CRC-8的算法，相应的，CRC16将比特流左移16位，h(x)是一个次数为16的不可约多项式。
那么接下来讨论一下，如何生成CRC16码。

二.CRC的三种算法
1.比特型算法
由F2域上的多项式除法可知，两式相除，其实就是做异或运算。

可以观察到当首位为1的时候就进行异或运算，为0就将比特流左移一位，
直到比特流最后一位也参与到运算。
图引自百度文库：
http://wenku.baidu.com/link?url=W3vwtcrzv5f0G5hCke028G5FVZSCia1kyhmHFKArbKPWi5uFZLZFCJYqOF0qbvnQ-ws3uvATXpPKy9FyJaB21kBzsX5rBY7cfuhyVYo9ujG

算法如下：
1.扩大数据流（左移16位）
2.创建一个16位的寄存器，初始值为数据流前16位
3.
while(比特流最后一位未读入寄存器)
{
if(首位为0)
{
左移一位，低位从比特流中下一位读取
}
else
{
和h(x)进行异或运算
}
}
这样最后16位寄存器中的数据就是求得的16位CRC码。
需要注意的是，h(x)只要是传输方和接收方都约定好的16次不可约多项式都可以，标准CRC16用的多项式是x^16 + x^15 + x^2 + 1，即0x8005。

2.字节型算法
一位博主原理总结得十分详细，下面连接供大家参考:
http://www.cnblogs.com/Msisiterc/archive/2011/12/20/2294910.html

下面贴出字节型算法中的查表法C#的代码

        ///CRC16表
        static ushort[] CRC16Table = 
        {
            0x0, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,  
           0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,  
           0x1231, 0x210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7
1
2
3
4
5
6