摘 要： 介紹循環(huán)冗余校驗(yàn)CRC在TMS320C64x+系列DSP上的軟件實(shí)現(xiàn)。 給出了該實(shí)現(xiàn)方法的理論推導(dǎo)過程并提供了相應(yīng)的軟件實(shí)現(xiàn)代碼。

　　1 CRC常規(guī)實(shí)現(xiàn)方法

　　CRC即循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check）：是數(shù)據(jù)通信領(lǐng)域中常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。

　　GCRC16（X）=X16+X12+X5+1

　　CRC通常由硬件實(shí)現(xiàn)，圖1說明由硬件移位寄存器實(shí)現(xiàn)的3GPP CRC16。

　　圖1中，表示異或（XOR）運(yùn)算， 異或運(yùn)算在移位寄存器中的位置與生成多項(xiàng)式相對(duì)應(yīng)。CRC運(yùn)算前，移位寄存器清零，隨后數(shù)據(jù)位被移入寄存器，寄存器的值即為CRC碼。

　　發(fā)送端將CRC碼附在原始數(shù)據(jù)后發(fā)送；接收端用同樣的方法為接收到的原始數(shù)據(jù)生成CRC碼，并且與接收到的CRC碼比較。如果不一致，則說明接收到的數(shù)據(jù)出錯(cuò)。

　　CRC校驗(yàn)也可由軟件實(shí)現(xiàn)，它比硬件實(shí)現(xiàn)靈活，但不如硬件實(shí)現(xiàn)效率高。假設(shè)變量crc代表移位寄存器的值，CRC16 軟件實(shí)現(xiàn)的偽代碼為：

　　while（data_len--）

　　{

　　crc=（crc《1）

　　if （（（input bit）（bit shifted out））==1）

　　crc=crc0x1021           //0x1021 represents X12+X5+1

　　else if （（（input bit）（bit shifted out））==0）

　　crc=crc0//this can be removed since it is meaningless

　　}

　　以上軟件實(shí)現(xiàn)效率不高，主要是因?yàn)閿?shù)據(jù)被逐個(gè)位處理，每次循環(huán)只能處理一位。一種常見的改進(jìn)的軟件實(shí)現(xiàn)方法可以每次循環(huán)處理一個(gè)字節(jié)，但它需要一個(gè)查找表。在查找表中保存所有的8位數(shù)據(jù)的CRC運(yùn)算結(jié)果，因?yàn)?位數(shù)據(jù)有256個(gè)，所以查找表的長(zhǎng)度為256。下面是生成查找表的偽代碼：利用CRC進(jìn)行檢錯(cuò)的過程可簡(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)式”。

　　for（i=0；i<256；i++）

　　crc_lut[i]=crc_value_for_one_byte（i）；//generate CRC for one byte

　　用查找表方法實(shí)現(xiàn)的CRC16的代碼如下：

　　Uint16 crc16_lut（Uint8*data_prt，Int32 data_len，Uint16*crc_lut）

　　{

　　Uint8 crc_shift_out；

　　Uint16 crc=0；

　　while（data_len--）

　　{

　　crc_shift_out=（Uint8） （crc》8）；//higher 8 bit of previous crc are shifted out

　　crc=（crc《8）^crc_lut[crc_shift_out^（*data_prt++）]；

　　}

　　return（crc）；

　　}

　　這個(gè)處理過程可被理解為：

　　（1）計(jì)算移位寄存器在8個(gè)時(shí)鐘周期中的輸入：（crc_shift_out^*data_prt++）；

　?。?）查找這個(gè)輸入字節(jié)對(duì)應(yīng)的CRC碼：crc_lut[crc_shift_out^*data_prt++]；

　?。?）把新輸入數(shù)據(jù)的CRC碼加到原有的CRC值上：（crc《8）^crc_lut[crc_shift_out^*data_prt++]。

　　在TMS320C64x DSP上，如果用這種方法實(shí)現(xiàn)CRC校驗(yàn)，每次循環(huán)大概需9個(gè)DSP時(shí)鐘周期。而在TMS320C64x+DSP上新增了與CRC運(yùn)算相關(guān)的Galois域乘法運(yùn)算指令，使得每次循環(huán)僅需約1個(gè)DSP時(shí)鐘周期。

　　2 C64x+DSP的Galois域乘法指令

　　C64x+DSP系列是TI的高性能DSP系列，它有8個(gè)并行的運(yùn)算單元，速度高達(dá)到1GHz。C64x+ DSP 提供了新的與CRC運(yùn)算相關(guān)的Galois域乘法指令和寄存器，可在兩個(gè)乘法單元M1、M2中并行執(zhí)行。

　　C64x+DSP是一種獨(dú)特的微處理器，是以數(shù)字信號(hào)來處理大量信息的器件。其工作原理是接收模擬信號(hào)，轉(zhuǎn)換為0或1的數(shù)字信號(hào)。再對(duì)數(shù)字信號(hào)進(jìn)行修改、刪除、強(qiáng)化，并在其他系統(tǒng)芯片中把數(shù)字?jǐn)?shù)據(jù)解譯回模擬數(shù)據(jù)或?qū)嶋H環(huán)境格式。它不僅具有可編程性，而且其實(shí)時(shí)運(yùn)行速度可達(dá)每秒數(shù)以千萬條復(fù)雜指令程序，遠(yuǎn)遠(yuǎn)超過通用微處理器，是數(shù)字化電子世界中日益重要的電腦芯片。它的強(qiáng)大數(shù)據(jù)處理能力和高運(yùn)行速度，是值得稱道的兩大特色。

　?。?）GMPY：Galois域（32bit）（9bit），寄存器GPLYA存放用于M1運(yùn)算單元的多項(xiàng)式，寄存器GPLYB存放用于M2運(yùn)算單元的多項(xiàng)式；

　?。?）XORMPY：多項(xiàng)式為0的Galois域（32bit）（9bit）；

　?。?）GMPY4：同時(shí)執(zhí)行4個(gè)Galois域（8bit）（8bit），M1和M2運(yùn)算單元共用存放多項(xiàng)式的GFPGFR寄存器。

　　注：表示Galois域乘法。

　　M1和M2可以并行執(zhí)行，所以，C64x+每個(gè)時(shí)鐘周期可執(zhí)行2個(gè)（32bit）（9bit）的GMPY或XORGMPY指令，或執(zhí)行8個(gè)（8bit）（8bit）的GMPY指令。

　　下面是C64x+GMPY指令的等效C代碼：

　　//32bits src1 multiply 9bit src2 with 32bit polynomial

　　uint GMPY（uint src1，uint src2，uint polynomial）

　　{

　　uint pp；

　　uint mask，tpp；

　　uint i；

　　pp=0；

　　mask=0x00000100；//multiply by computing partial products.

　　for （i=0；i<8；i++）{

　　if （src2 & mask） pp^=src1；

　　mask》=1；

　　tpp=pp《1；

　　if（pp & 0x80000000） pp=polynomial^tpp；

　　else pp=tpp；

　　}

　　if （src2 & 0x1） pp^=src1；

　　return（pp）；//leave it asserted left.

　　}

　　請(qǐng)注意，這里的GMPY指令所用的多項(xiàng)式是GF（232）原多項(xiàng)式的低32位。例如：

　　G（X）CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

　　用二進(jìn)制數(shù)表示為：1 0000 0100 1100 0001 0001 1101 1011 0111=0x1 04c1 1db7，則GMPY多項(xiàng)式寄存器的值應(yīng)該是0x04c11db7，沒有必要包含位，因?yàn)樗冀K為1。GMPY所用的多項(xiàng)式必須是GF（232）域多項(xiàng)式，對(duì)于非GF域的多項(xiàng)式，必須被左移得到32階的多項(xiàng)式，并左移操作數(shù)src1，使它也是32階，然后用GMPY指令運(yùn)算，結(jié)果需右移同樣的位數(shù)，從而得到終結(jié)果。

　　例如：Galois域G（X）=X8+X6+X5+X3+1（01101001）上的二進(jìn)制數(shù)（01000001）（100）可以用以下方法計(jì)算：

　　GMPY（（01000001）《24，（100），（01101001）《24）》24

　　3 CRC在C64x+DSP上的高效實(shí)現(xiàn)

　　比較CRC的軟件實(shí)現(xiàn)代碼和GMPY指令的等效C語言代碼可以看出，一個(gè)字節(jié)的CRC碼可以用GMPY指令計(jì)算為GMPY（polynomial, data_byte, polynomial）。

　　用GMPY實(shí)現(xiàn)的CRC代碼為：

　　Uint32 crc_gmpy（Uint8*data_ptr，Int32 data_len_of_byte，Uint32 polynomial）

　　//data_ptr is data pointer，data_len_of_byte is the data length in bytes

　　{

　　Int32 i；

　　Uint32 crc32=0；

　　GPLYA=polynomial；

　　GPLYB=polynomial；

　　for（i=0；i      {

　　crc32=_gmpy（crc32，0x100）^_gmpy（polynomial，（*data_ptr++））；

　　}

　　return（crc32）；

　　}

　　以上代碼中的“_gmpy”代表GMPY指令，用戶按C語言函數(shù)調(diào)用的方式使用它，但DSP編譯器會(huì)把它編譯成一條GMPY指令，而不是一個(gè)函數(shù)調(diào)用。所有的C6000系列DSP指令都可以在C語音中按這種方式使用。

　　以上代碼在C64x+上執(zhí)行，每次循環(huán)需要大約6個(gè)時(shí)鐘周期，它比查找表方法效率高，而且不需要查找表，這對(duì)于存儲(chǔ)器受限的應(yīng)用來說非常合適。上該方法使用的查找表可以由以下代碼生成：

　　crc_lut[0]=polynomial；

　　for（k=1；k         crc_lut[k]=_gmpy（crc_lut[k-1]，0x100））；//polynomialx8

　　這種CRC的計(jì)算方法可用以下偽代碼表示：

　　Index=length_of_byte-1；

　　for（k=0；k         crc=crc^_gmpy（crc_lut[Index--]，data_byte[k]））；

　　為了更充分地利用C64x+ DSP并行流水式處理的能力，并減少查找表的長(zhǎng)度，可以進(jìn)一步對(duì)以上計(jì)算進(jìn)行優(yōu)化，每次循環(huán)處理32bit。相應(yīng)的查找表長(zhǎng)度減少為原來的1/4。查找表的生成代碼如下：

　　crc_lut[0]=polynomial；

　　for（k=1；k        crc_lut[k]=_gmpy（_gmpy（_gmpy（_gmpy（crc_lut[k-1]，0x100），0x100），0x100），0x100）；//polynomialx32

　　該方法的CRC計(jì)算可用以下偽代碼表示：

　　Index=length_of_word-1；

　　for（j=0；j    {

　　LutXn=crc_lut[Index--]；

　　crc0=crc0^_gmpy（LutXn，data_byte[4*j]）；

　　crc1=crc1^_gmpy（LutXn，data_byte[4*j+1]）；

　　crc2=crc2^_gmpy（LutXn，data_byte[4*j+2]）；

　　crc3=crc3^_gmpy（LutXn，data_byte[4*j+3]）；

　　}

　　//crc0x24

　　crc0=_gmpy（crc0，0x100）；

　　crc0=_gmpy（crc0，0x100）；

　　crc0=_gmpy（crc0，0x100）；

　　//crc1x16

　　crc1= _gmpy（crc1, 0x100）；

　　crc1= _gmpy（crc1, 0x100）；

　　//crc2x8

　　crc2=_gmpy（crc2，0x100）；

　　crc=crc0^crc1^crc2^crc3；

　　上述基于GMPY和查找表的CRC優(yōu)化實(shí)現(xiàn)，每次循環(huán)約需4個(gè)時(shí)鐘周期，而循環(huán)處理4字節(jié)，所以每個(gè)字節(jié)的處理僅需約一個(gè)時(shí)鐘周期。

　　CRC是常用的檢錯(cuò)機(jī)制，表1總結(jié)了幾種CRC的軟件實(shí)現(xiàn)方法在C64x+DSP上執(zhí)行的效率。

　　通過表1可以看出，在C64x+DSP上利用Galois域乘法指令極大地提高了CRC運(yùn)算的效率。