CRC(查表法)-表的由来

CRC(查表)-表的由来bylenglx([e-mail],[e-mail])2006/07/251)硬件电路组成a)x^16+x^12+x^5+1┌───────────┬─────────────────┬─────────────┐↑┌─┬─┬─┬─┐↓┌─┬─┬─┬─┬─┬─┬─┐↓┌─┬─┬─┬─┬─┐│◎←│15│14│13│12│←◎←│11│10│09│08│07│06│05│←◎←│04│03│02│01│00│←┘↑└─┴─┴─┴─┘└─┴─┴─┴─┴─┴─┴─┘└─┴─┴─┴─┴─┘inb)x^8+x^2+x+1┌───────────────┬─────┬─────┐↑┌─┬─┬─┬─┬─┬─┐↓┌─┐↓┌─┐│◎←│07│06│05│04│03│02│←◎←│01│←◎←│00│←┘↑└─┴─┴─┴─┴─┴─┘└─┘└─┘in2)简单算法模型(按bit计算)照以上的硬件电路来看,其工作原理就是:如果原来CRC的最高位异或输入是1的话,那么絇OST并且异或生成多项式(图a为0x1021,图b为0x7).如果原来CRC的最高位异或输入是高位异或输入是0的话,那么结果就是CRC左移一位.那么可以得到以下的程序(以图a例)U16crc_cal(bit*in,U32cnt){U16crc=0;while(cnt--){booltmp=(crc15)^*in;crc=1;if(tmp)crc^=0x1021;in++;}returncrc;}3)查表(按字节计算)很显然,按比特计算的方法,其效率是低下的.下面介绍查表方法(按字节计算).要知道为什么可以用查表的方法,需要一些预备知识.以图b为例,假设当前的CRC值是10111001,现在要输入4比特数据1101,其生成多项式是:00000111CRC=10111001,in=1101,G(X)=00000111计算方法1计算方法2step:10111001011010011:01110010110100102:1110010010100100^00000111^000001111----------------------------11100011101000113:1100011001000110^00000111^000001112-----------------------------11000001010000014:1000001010000010计算方法1是硬件电路的完全模拟算法step1:将crc左移一位,因为crc的最高位是1,输入也是1,所以不做处理.step2:将crc左移一位,因为crc的最高位是0,输入是1,所以还需要异或G(X).....step4:将crc左移一位,因为crc的最高位是0,输入也是0,所以不做处理.得到最终的结果crc=10000010实际上,在crc左移以后,是否还要异或生成多项式的条件是:crc的最高位和输入位异或后的值.那么是否可以预先将CRC(h)的值与要输入的4比特数据异或,作为是否判断条件呢.答案是肯定的.CRC=10111001,in=1101,CRC(h)^in=0110其计算过程见计算方法2step1:将CRC左移一位,因为CRC的最高位是0,所以不做处理.step2:将CRC左移一位,因为CRC的最高位是1,所以还需要异或G(X).....step4:将CRC左移一位,因为CRC的最高位是0,所以不做处理.得到最终的结果CRC=10000010虽然,上面的结果是一样的,可有证据证明无论什么情况下,结果都是对的?静下来想想,你就是知道这2个方法确实能得出相同的结果.当4比特的输入完成之后,整个CRC值左移了4位,原来的CRC(h)只是作为判断异或生成多项式的条件存在过.最终的CRC值完全是G(X)和CRC(l)不停地(异或/移位)的结果.虽然,在CRC计算的过程中,CRC不停的在变化着,但:1.如果在方法1中,由于CRC的最高位和输入异或后的结果等于0,那么CRC只是左移一位.显然2个方法是一样的.2.如果在方法1中,由于CRC的最高位和输入异或后的结果等于1,那么CRC左移一位后,还需要异或G(X).异或G(X)的过程中,可能使CRC的后续某位产生变化(也可能不变化,视生成多项式的值而定).a.如果没发生变化,那当这位最后移到最高位,作为判断条件的时候,仍然是以前的这个值和输入位的异或.显然2个计算方法是一样的.b.如果变化过,那当这位最后移到最高位,作为判断条件的时候,是变化过后的值和输入位的异或.但如果方法1能引起后续某位的变化,方法2同样也会引起同一位的变化.这样当这位最后移到最高位,作为判断条件的时候,2种方法的判断条件仍然是一致的.*关于这部分,我描述得不怎么清楚,那是因为我小时候地语文基础没打好,:).如果你有更好地描述,请告诉我.好了,预备知识完毕,现在开始探讨那个查找表是怎么来的.请看方法2,最终的CRC的结果是:(CRC(l)4)^1^2计算方法2CRC=10111001,in=1101,G(X)=00000111|-----------------------CRC(h)^in=1011^1101=0110|||------------------CRC(l)--------011010011101001010100100^000001111--------------1010001101000110^000001112-------------0100000110000010由于异或的可结合律,其结果等同于:(CRC(l)4)^(1^2)这说明,(1)^2)可以预先制作成表格,采用查表的方法计算CRC,表的索引是CRC(h)^in.其结果是:(CRC(l)4)^table[CRC(h)^in].因为是4比特,表的大小是16.表的内容可以根据G(X),预先计算.这里举例用的4比特,基于字节的方法可以用同样的方法.那么现在开始编程了.U16crc_tab[256]={...};U16crc_cal(U8*ptr,U32cnt){U16crc=0;U8da;while(cnt--){da=crc8;//CRC(h)crc=8;crc^=crc_tab[da^*ptr++];}returncrc;}既然你已经知道了查表的原理,那么编一个计算表值的程序不成问题了.#defineGX0x1021voidCCrcDlg::OnButton1(){WORDtable[256];for(inti=0;i256;i++){WORDcrc=i8;for(intn=0;n8;n++){booltmp=crc&(115)?true:false;crc=1;if(tmp)crc^=GX;}table=crc;}}那么你得到了这么个表:U16table[256]={0X0000,0X1021,0X2042,0X3063,0X4084,0X50A5,0X60C6,0X70E7,0X8108,0X9129,0XA14A,0XB16B,0XC18C,0XD1AD,0XE1CE,0XF1EF,0X1231,0X0210,0X3273,0X2252,0X52B5,0X4294,0X72F7,0X62D6,0X9339,0X8318,0XB37B,0XA35A,0XD3BD,0XC39C,0XF3FF,0XE3DE,0X2462,0X3443,0X0420,0X1401,0X64E6,0X74C7,0X44A4,0X5485,0XA56A,0XB54B,0X8528,0X9509,0XE5EE,0XF5CF,0XC5AC,0XD58D,0X3653,0X2672,0X1611,0X0630,0X76D7,0X66F6,0X5695,0X46B4,0XB75B,0XA77A,0X9719,0X8738,0XF7DF,0XE7FE,0XD79D,0XC7BC,0X48C4,0X58E5,0X6886,0X78A7,0X0840,0X1861,0X2802,0X3823,0XC9CC,0XD9ED,0XE98E,0XF9AF,0X8948,0X9969,0XA90A,0XB92B,0X5AF5,0X4AD4,0X7AB7,0X6A96,0X1A71,0X0A50,0X3A33,0X2A12,0XDBFD,0XCBDC,0XFBBF,0XEB9E,0X9B79,0X8B58,0XBB3B,0XAB1A,0X6CA6,0X7C87,0X4CE4,0X5CC5,0X2C22,0X3C03,0X0C60,0X1C41,0XEDAE,0XFD8F,0XCDEC,0XDDCD,0XAD2A,0XBD0B,0X8D68,0X9D49,0X7E97,0X6EB6,0X5ED5,0X4EF4,0X3E13,0X2E32,0X1E51,0X0E70,0XFF9F,0XEFBE,0XDFDD,0XCFFC,0XBF1B,0XAF3A,0X9F59,0X8F78,0X9188,0X81A9,0XB1CA,0XA1EB,0XD10C,0XC12D,0XF14E,0XE16F,0X1080,0X00A1,0X30C2,0X20E3,0X5004,0X4025,0X7046,0X6067,0X83B9,0X9398,0XA3FB,0XB3DA,0XC33D,0XD31C,0XE37F,0XF35E,0X02B1,0X1290,0X22F3,0X32D2,0X4235,0X5214,0X6277,0X7256,0XB5EA,0XA5CB,0X95A8,0X8589,0XF56E,0XE54F,0XD52C,0XC50D,0X34E2,0X24C3,0X14A0,0X0481,0X7466,0X6447,0X5424,0X4405,0XA7DB,0XB7FA,0X8799,0X97B8,0XE75F,0XF77E,0XC71D,0XD73C,0X26D3,0X36F2,0X0691,0X16B0,0X6657,0X7676,0X4615,0X5634,0XD94C,0XC96D,0XF90E,0XE92F,0X99C8,0X89E9,0XB98A,0XA9AB,0X5844,0X4865,0X7806,0X6827,0X18C0,0X08E1,0X3882,0X28A3,0XCB7D,0XDB5C,0XEB3F,0XFB1E,0X8BF9,0X9BD8,0XABBB,0XBB9A,0X4A75,0X5A54,0X6A37,0X7A16,0X0AF1,0X1AD0,0X2AB3,0X3A92,0XFD2E,0XED0F,0XDD6C,0XCD4D,0XBDAA,0XAD8B,0X9DE8,0X8DC9,0X7C26,0X6C07,0X5C64,0X4C45,0X3CA2,0X2C83,0X1CE0,0X0CC1,0XEF1F,0XFF3E,0XCF5D,0XDF7C,0XAF9B,0XBFBA,0X8FD9,0X9FF8,0X6E17,0X7E36,0X4E55,0X5E74,0X2E93,0X3EB2,0X0ED1,0X1EF0};----------------------------------END------------------------------------