国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

摘要: 本文首先討論了CRC的代數(shù)學(xué)算法，然后以常見(jiàn)的CRC-ITU為例，通過(guò)硬件電路的實(shí)現(xiàn)，引出了比特型算法，最后重點(diǎn)介紹了字節(jié)型快速查表算法，給出了相應(yīng)的C語(yǔ)言實(shí)現(xiàn)。

關(guān)鍵詞: CRC, FCS, 生成多項(xiàng)式, 檢錯(cuò)重傳

引言

CRC的全稱為Cyclic Redundancy Check，中文名稱為循環(huán)冗余校驗(yàn)。它是一類重要的線性分組碼，編碼和解碼方法簡(jiǎn)單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。實(shí)際上，除數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個(gè)ZIP文件時(shí)，偶爾會(huì)碰到“Bad CRC”錯(cuò)誤，由此它在數(shù)據(jù)存儲(chǔ)方面的應(yīng)用可略見(jiàn)一斑。

差錯(cuò)控制理論是在代數(shù)理論基礎(chǔ)上建立起來(lái)的。這里我們著眼于介紹CRC的算法與實(shí)現(xiàn)，對(duì)原理只能捎帶說(shuō)明一下。若需要進(jìn)一步了解線性碼、分組碼、循環(huán)碼、糾錯(cuò)編碼等方面的原理，可以閱讀有關(guān)資料。

利用CRC進(jìn)行檢錯(cuò)的過(guò)程可簡(jiǎn)單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。這個(gè)規(guī)則，在差錯(cuò)控制理論中稱為“生成多項(xiàng)式”。

1 代數(shù)學(xué)的一般性算法

在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如 1100101 表示為
1·x⁶+1·x⁵+0·x⁴+0·x³+1·x²+0·x+1，即 x⁶+x⁵+x²+1。

設(shè)編碼前的原始信息多項(xiàng)式為P(x)，P(x)的最高冪次加1等于k；生成多項(xiàng)式為G(x)，G(x)的最高冪次等于r；CRC多項(xiàng)式為R(x)；編碼后的帶CRC的信息多項(xiàng)式為T(x)。

發(fā)送方編碼方法：將P(x)乘以xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移r位)，再除以G(x)，所得余式即為R(x)。用公式表示為
T(x)=x^rP(x)+R(x)

接收方解碼方法：將T(x)除以G(x)，如果余數(shù)為0，則說(shuō)明傳輸中無(wú)錯(cuò)誤發(fā)生，否則說(shuō)明傳輸有誤。

舉例來(lái)說(shuō)，設(shè)信息碼為1100，生成多項(xiàng)式為1011，即P(x)=x³+x²，G(x)=x³+x+1，計(jì)算CRC的過(guò)程為

      xrP(x)     x3(x3+x2)     x6+x5                    x-------- = ---------- = -------- = (x3+x2+x) + --------G(x)       x3+x+1      x3+x+1                 x3+x+1

即 R(x)=x。注意到G(x)最高冪次r=3，得出CRC為010。

如果用豎式除法，計(jì)算過(guò)程為

               1110-------1011 /1100000     (1100左移3位)1011----11101011-----10101011-----00100000----010

因此，T(x)=(x⁶+x⁵)+(x)=x⁶+x⁵+x, 即 1100000+010=1100010

如果傳輸無(wú)誤，

       T(x)     x6+x5+x------ = --------- = x3+x2+x,G(x)     x3+x+1

無(wú)余式。回頭看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個(gè)1時(shí)，就能除盡。

上述推算過(guò)程，有助于我們理解CRC的概念。但直接編程來(lái)實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會(huì)直接這樣去計(jì)算和驗(yàn)證CRC。

下表中列出了一些見(jiàn)于標(biāo)準(zhǔn)的CRC資料：

    *  生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如04C11DB7實(shí)際上是104C11DB7。** 前稱CRC-CCITT。ITU的前身是CCITT。

2 硬件電路的實(shí)現(xiàn)方法

多項(xiàng)式除法，可用除法電路來(lái)實(shí)現(xiàn)。除法電路的主體由一組移位寄存器和模2加法器(異或單元)組成。以CRC-ITU為例，它由16級(jí)移位寄存器和3個(gè)加法器組成，見(jiàn)下圖(編碼/解碼共用)。編碼、解碼前將各寄存器初始化為"1"，信息位隨著時(shí)鐘移入。當(dāng)信息位全部輸入后，從寄存器組輸出CRC結(jié)果。

3 比特型算法

上面的CRC-ITU除法電路，完全可以用軟件來(lái)模擬。定義一個(gè)寄存器組，初始化為全"1"。依照電路圖，每輸入一個(gè)信息位，相當(dāng)于一個(gè)時(shí)鐘脈沖到來(lái)，從高到低依次移位。移位前信息位與bit0相加產(chǎn)生臨時(shí)位，其中bit15移入臨時(shí)位，bit10、bit3還要加上臨時(shí)位。當(dāng)全部信息位輸入完成后，從寄存器組取出它們的值，這就是CRC碼。

typedef unsigned char bit;typedef unsigned char byte;typedef unsigned short u16;typedef union {u16 val;struct {u16 bit0 : 1;u16 bit1 : 1;u16 bit2 : 1;u16 bit3 : 1;u16 bit4 : 1;u16 bit5 : 1;u16 bit6 : 1;u16 bit7 : 1;u16 bit8 : 1;u16 bit9 : 1;u16 bit10 : 1;u16 bit11 : 1;u16 bit12 : 1;u16 bit13 : 1;u16 bit14 : 1;u16 bit15 : 1;} bits;} CRCREGS;// 寄存器組CRCREGS regs;// 初始化CRC寄存器組：移位寄存器置為全"1"void crcInitRegisters(){regs.val = 0xffff;}// CRC輸入一個(gè)bitvoid crcInputBit(bit in){bit a;a = regs.bits.bit0 ^ in;regs.bits.bit0 = regs.bits.bit1;regs.bits.bit1 = regs.bits.bit2;regs.bits.bit2 = regs.bits.bit3;regs.bits.bit3 = regs.bits.bit4 ^ a;regs.bits.bit4 = regs.bits.bit5;regs.bits.bit5 = regs.bits.bit6;regs.bits.bit6 = regs.bits.bit7;regs.bits.bit7 = regs.bits.bit8;regs.bits.bit8 = regs.bits.bit9;regs.bits.bit9 = regs.bits.bit10;regs.bits.bit10 = regs.bits.bit11 ^ a;regs.bits.bit11 = regs.bits.bit12;regs.bits.bit12 = regs.bits.bit13;regs.bits.bit13 = regs.bits.bit14;regs.bits.bit14 = regs.bits.bit15;regs.bits.bit15 = a;}// 輸出CRC碼(寄存器組的值)u16 crcGetRegisters(){return regs.val;}crcInputBit中一步一步的移位/異或操作，可以進(jìn)行簡(jiǎn)化：void crcInputBit(bit in){bit a;a = regs.bits.bit0 ^ in;regs.val >>= 1;if(a) regs.val ^= 0x8408;}

細(xì)心的話，可以發(fā)現(xiàn)0x8408和0x1021(CRC-ITU的簡(jiǎn)記式)之間的關(guān)系。由于我們是從低到高輸出比特流的，將0x1021左右反轉(zhuǎn)就得到0x8408。將生成多項(xiàng)式寫成 G(x)=1+x⁵+x¹²+x¹⁶，是不是更好看一點(diǎn)？

下面是一個(gè)典型的PPP幀。最后兩個(gè)字節(jié)稱為FCS(Frame Check Sequence)，是前面11個(gè)字節(jié)的CRC。

FF 03 C0 21 04 03 00 07 0D 03 06 D0 3A

我們來(lái)計(jì)算這個(gè)PPP幀的CRC，并驗(yàn)證它。

    byte ppp[13] = {0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00, 0x00};int i,j;u16 result;/////////// 以下計(jì)算FCS// 初始化crcInitRegisters();// 逐位輸入，每個(gè)字節(jié)低位在先，不包括兩個(gè)FCS字節(jié)for(i = 0; i < 11; i++){for(j = 0; j < 8; j++){crcInputBit((ppp[i] >> j) & 1);}}// 得到CRC：將寄存器組的值求反result = ~crcGetRegisters();// 填寫FCS，先低后高ppp[11] = result & 0xff;ppp[12] = (result >> 8) & 0xff;/////////// 以下驗(yàn)證FCS// 初始化crcInitRegisters();// 逐位輸入，每個(gè)字節(jié)低位在先，包括兩個(gè)FCS字節(jié)for(i = 0; i < 13; i++){for(j = 0; j < 8; j++){crcInputBit((ppp[i] >> j) & 1);}}// 得到驗(yàn)證結(jié)果result = crcGetRegisters();

可以看到，計(jì)算出的CRC等于0x3AD0，與原來(lái)的FCS相同。驗(yàn)證結(jié)果等于0。初始化為全"1"，以及將寄存器組的值求反得到CRC，都是CRC-ITU的要求。事實(shí)上，不管初始化為全"1"還是全"0"，計(jì)算CRC取反還是不取反，得到的驗(yàn)證結(jié)果都是0。

4 字節(jié)型算法

比特型算法逐位進(jìn)行運(yùn)算，效率比較低，不適用于高速通信的場(chǎng)合。數(shù)字通信系統(tǒng)(各種通信標(biāo)準(zhǔn))一般是對(duì)一幀數(shù)據(jù)進(jìn)行CRC校驗(yàn)，而字節(jié)是幀的基本單位。最常用的是一種按字節(jié)查表的快速算法。該算法基于這樣一個(gè)事實(shí)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位，加上上一字節(jié)CRC右移8位和本字節(jié)之和后所求得的CRC碼。如果我們把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來(lái)，放在一個(gè)表里 ，編碼時(shí)只要從表中查找對(duì)應(yīng)的值進(jìn)行處理即可。

CRC-ITU的計(jì)算算法如下：a.寄存器組初始化為全"1"(0xFFFF)。b.寄存器組向右移動(dòng)一個(gè)字節(jié)。c.剛移出的那個(gè)字節(jié)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。d.索引所指的表值與寄存器組做異或運(yùn)算。f.數(shù)據(jù)指針加1，如果數(shù)據(jù)沒(méi)有全部處理完，則重復(fù)步驟b。g.寄存器組取反，得到CRC，附加在數(shù)據(jù)之后。CRC-ITU的驗(yàn)證算法如下：a.寄存器組初始化為全"1"(0xFFFF)。b.寄存器組向右移動(dòng)一個(gè)字節(jié)。c.剛移出的那個(gè)字節(jié)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。d.索引所指的表值與寄存器組做異或運(yùn)算。e.數(shù)據(jù)指針加1，如果數(shù)據(jù)沒(méi)有全部處理完，則重復(fù)步驟b (數(shù)據(jù)包括CRC的兩個(gè)字節(jié))。f.寄存器組的值是否等于“Magic Value”(0xF0B8)，若相等則通過(guò)，否則失敗。

下面是通用的CRC-ITU查找表以及計(jì)算和驗(yàn)證CRC的C語(yǔ)言程序：

// CRC-ITU查找表const u16 crctab16[] ={0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78,};// 計(jì)算給定長(zhǎng)度數(shù)據(jù)的16位CRC。u16 GetCrc16(const byte* pData, int nLength){u16 fcs = 0xffff;    // 初始化while(nLength>0){fcs = (fcs >> 8) ^ crctab16[(fcs ^ *pData) & 0xff];nLength--;pData++;}return ~fcs;    // 取反}// 檢查給定長(zhǎng)度數(shù)據(jù)的16位CRC是否正確。bool IsCrc16Good(const byte* pData, int nLength){u16 fcs = 0xffff;    // 初始化while(nLength>0){fcs = (fcs >> 8) ^ crctab16[(fcs ^ *pData) & 0xff];nLength--;pData++;}return (fcs == 0xf0b8);  // 0xf0b8是CRC-ITU的"Magic Value"}

使用字節(jié)型算法，前面出現(xiàn)的PPP幀F(xiàn)CS計(jì)算和驗(yàn)證過(guò)程，可用下面的程序片斷實(shí)現(xiàn)：

    byte ppp[13] = {0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00, 0x00};u16 result;// 計(jì)算CRCresult = GetCrc16(ppp, 11);// 填寫FCS，先低后高ppp[11] = result & 0xff;ppp[12] = (result >> 8) & 0xff;// 驗(yàn)證FCSif(IsCrc16Good(ppp, 13)){... ...}

該例中數(shù)據(jù)長(zhǎng)度為11，說(shuō)明CRC計(jì)算并不要求數(shù)據(jù)2字節(jié)或4字節(jié)對(duì)齊。

至于查找表的生成算法，以及CRC-32等其它CRC的算法，可參考RFC 1661, RFC 3309等文檔。需要注意的是，雖然CRC算法的本質(zhì)是一樣的，但不同的協(xié)議、標(biāo)準(zhǔn)所規(guī)定的初始化、移位次序、驗(yàn)證方法等可能有所差別。

結(jié)語(yǔ)

CRC是現(xiàn)代通信領(lǐng)域的重要技術(shù)之一。掌握CRC的算法與實(shí)現(xiàn)方法，在通信系統(tǒng)的設(shè)計(jì)、通信協(xié)議的分析以及軟件保護(hù)等諸多方面，能發(fā)揮很大的作用。如在作者曾經(jīng)設(shè)計(jì)的一個(gè)多串口數(shù)據(jù)傳輸系統(tǒng)中，每串口速率為460kbps，不加校驗(yàn)時(shí)誤碼率大于10^-6，加上簡(jiǎn)單的奇偶校驗(yàn)后性能改善不很明顯，利用CRC進(jìn)行檢錯(cuò)重傳，誤碼率降低至10^-15以下，滿足了實(shí)際應(yīng)用的要求。

參考文獻(xiàn)

1. Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, 1994
2. J. Stone, "Stream Control Transmission Protocol (SCTP) Checksum Change", RFC 3309, 2002
3. J. Satran, "Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC)/Checksum Considerations", RFC 3385, 2002
4. International Standardization,"High-level data link control (HDLC) procedures", ISO/IEC 3309, 1992
5. ITU-T V.41, "Code-independent error-control system", 1989
6. 郭梯云等,《數(shù)據(jù)傳輸(修訂本)》, 人民郵電出版社, 1998

[相關(guān)資源]
◆ RFC/STD文檔：Internet FAQ Archives
◆ ITU官方網(wǎng)站：http://www.itu.int/home/index.html
◆ bhw98的專欄：http://www.csdn.net/develop/author/netauthor/bhw98/