摘 要：循環(huán)冗余校驗(yàn)碼是一種重要的循環(huán)碼，編碼和解碼方法簡(jiǎn)單，容易實(shí)現(xiàn)，檢錯(cuò)能力強(qiáng)，誤判概率幾乎為零，是一種效率極高的差錯(cuò)控制方法，可以滿足通信系統(tǒng)可靠傳送信息的要求，在測(cè)控及數(shù)據(jù)通信中得到了非常廣泛的應(yīng)用。詳細(xì)介紹了循環(huán)冗余校驗(yàn)的編解碼原理，分析了用DSP實(shí)現(xiàn)CRC的合理性，最后給出了根據(jù)校驗(yàn)原理實(shí)現(xiàn)的設(shè)計(jì)思想及流程圖，具有一定的實(shí)用價(jià)值。



關(guān)鍵詞：數(shù)據(jù)傳輸系統(tǒng)；循環(huán)冗余校驗(yàn)；數(shù)字信號(hào)處理器；算法分析

中圖分類號(hào)：TN911.72文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004-373X(2008)07-083-03

DSP Implementation of CRC Algorithm in Data Communication System



HUA Tao1，WU Jin2

(1.System House，Siemens Signal Company Ltd.，Xi′an，710016，China;2.Xi′an University of Posts and Telecommunications，Xi′an，710061，China)



Abstract：Cyclic redundancy check code is a very important cyclic code，the coding and decoding methods are simple，easy to realize.It is strong to detect error，the probability of misjudging is nearly zero.It is a method with extremely high efficiency in controlling errors，which can fulfill the requirement of reliable information transmission in communication systems.It has got very extensive application in observing and controlling and data communication.This paper introduces the encoding and decoding principle of CRC in detail，analyzes the feasibility of CRC by DSP，and gives out the design proposal and flow chart according to the principle，which is very useful in applications.



Keywords：data communication system;cyclic redundancy check;digital signal processor;algorithm analysis

通信的目的是將信息及時(shí)可靠地傳給對(duì)方，因此要求一個(gè)通信系統(tǒng)傳送信息必須可靠快速。由于傳輸距離、現(xiàn)場(chǎng)狀況、干擾等諸多因素的影響，設(shè)備之間的通信數(shù)據(jù)常會(huì)發(fā)生一些無法預(yù)測(cè)的錯(cuò)誤。為了降低錯(cuò)誤所帶來的影響，一般在通信時(shí)采用數(shù)據(jù)校驗(yàn)的辦法［1］，而循環(huán)冗余碼校驗(yàn)是常用的重要校驗(yàn)方法之一。CRC校驗(yàn)的檢錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。數(shù)字信號(hào)處理器(DSP)是實(shí)施高速實(shí)時(shí)信號(hào)處理的專用處理器，目前DSP已成為通信、計(jì)算機(jī)、消費(fèi)類電子產(chǎn)品等領(lǐng)域的基礎(chǔ)器件，被譽(yù)為信息社會(huì)革命的旗手。CRC的高效檢錯(cuò)能力、DSP的實(shí)時(shí)處理能力，可以滿足通信系統(tǒng)傳送信息的兩大基本要求：可靠、快速。應(yīng)用DSP系統(tǒng)來實(shí)現(xiàn)CRC，完成數(shù)據(jù)傳輸過程中的檢錯(cuò)處理，便于集成，使用方便。使用DSP匯編語言，編解碼效率高，速度快，實(shí)時(shí)性好，占用系統(tǒng)資源少。因此CRC校驗(yàn)被廣泛使用在各種數(shù)據(jù)校驗(yàn)應(yīng)用中。

1 循環(huán)冗余校驗(yàn)碼

循環(huán)冗余校驗(yàn)碼(Cyclic Redundancy Check Code，CRC)由線性分組碼的分支而來，是一種檢錯(cuò)能力很強(qiáng)的循環(huán)碼。循環(huán)冗余校驗(yàn)對(duì)傳送數(shù)據(jù)作錯(cuò)誤偵測(cè)(Error Detecting)是利用除法及余數(shù)的原理。編碼和解碼方法簡(jiǎn)單，容易實(shí)現(xiàn)，檢錯(cuò)能力強(qiáng)，誤判概率幾乎為零，而且這種方法取得校驗(yàn)碼的方式具有很強(qiáng)的信息覆蓋能力，是一種效率極高的錯(cuò)誤校驗(yàn)法。這種高效的差錯(cuò)控制方法，在測(cè)控及數(shù)據(jù)通信中得到了廣泛的應(yīng)用［2］。

1.1 CRC的編碼原理

CRC校驗(yàn)采用多項(xiàng)式編碼方法，被處理的數(shù)據(jù)塊可以看作是一個(gè)n階的二進(jìn)制多項(xiàng)式，即an-1 xn-1 + an-2 xx-2 +…+ a1 x + a0 。如一個(gè)8位二進(jìn)制數(shù)10110101可以表示為：1x7+0x6+1x5+1x4+0x3+1x2+0x+1=x7+x5+x4+x2+1。多項(xiàng)式乘除法運(yùn)算過程與普通代數(shù)多項(xiàng)式的乘除法相同。多項(xiàng)式的加減法運(yùn)算以2為模，加減時(shí)不進(jìn)、借位，和邏輯異或運(yùn)算一致。

CRC碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)t(x)除以生成多項(xiàng)式g(x)，g(x)的首位和最后一位的系數(shù)必須均為1，兩者相除之后將最后的余數(shù)作為CRC校驗(yàn)碼。其實(shí)現(xiàn)步驟如下：

(1) 設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項(xiàng)式t(x)，生成多項(xiàng)式為g(x)，階數(shù)為r。在數(shù)據(jù)塊的末尾添加r個(gè)0，數(shù)據(jù)塊的長(zhǎng)度增加到m+r位，對(duì)應(yīng)的二進(jìn)制多項(xiàng)式為xrt(x)。

(2) 用生成多項(xiàng)式g(x)去除xrt(x)，求得余數(shù)為二進(jìn)制多項(xiàng)式y(tǒng)(x)，階數(shù)為r-1。這個(gè)二進(jìn)制多項(xiàng)式y(tǒng)(x)就是t(x)經(jīng)過生成多項(xiàng)式g(x)編碼的CRC校驗(yàn)碼。

(3) 用xrt(x)以模2的方式減去y(x)，得到二進(jìn)制多項(xiàng)式xrt′(x)。xrt′(x)就是包含了CRC校驗(yàn)碼的待發(fā)送字符串。

1.2 CRC的解碼原理

CRC校驗(yàn)原理實(shí)際上就是在一個(gè)p位二進(jìn)制數(shù)據(jù)序列之后附加一個(gè)r位二進(jìn)制檢驗(yàn)碼(序列)，從而構(gòu)成一個(gè)總長(zhǎng)為n＝p＋r位的二進(jìn)制序列，例如，p位二進(jìn)制數(shù)據(jù)序列D＝［dp-1 dp-2 …d1 d0］，r位二進(jìn)制檢驗(yàn)碼R＝［rr-1 rr-2…r1 r0］，所得到的這個(gè)n位二進(jìn)制序列就是M＝［dp-1dp-2 …d1d0 rr-1 rr-2…r1 r0］；附加在p位二進(jìn)制數(shù)據(jù)序列之后的這個(gè)r位二進(jìn)制檢驗(yàn)碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯(cuò)誤，這種特定關(guān)系就會(huì)被破壞。因此，通過檢查這一關(guān)系，就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)正確性的檢驗(yàn)。

校驗(yàn)碼R是通過對(duì)數(shù)據(jù)序列D進(jìn)行二進(jìn)制除法取余式運(yùn)算得到的，他被一個(gè)稱為生成多項(xiàng)式的(r＋1)位二進(jìn)制序列G＝［gr gr-1…g1 g0］來除，用多項(xiàng)式可以表示為:



[SX(]xrD(x)[]G(x)[SX)]=Q(x)+[SX(]R(x)[]G(x)[SX)]



其中，xrD(x)表示將數(shù)據(jù)序列D左移r位(即在D的末尾再增加r個(gè)0位)，Q(x)代表這一除法所得的商，R(x)就是所需的余式。這一運(yùn)算關(guān)系還可以用下式表達(dá):



R(x)=Re［xrD(x)G(x)］



其中，Re［ ］表示對(duì)括號(hào)內(nèi)的式子進(jìn)行取余式運(yùn)算。

由CRC碼的編碼過程可知，接收方接收的n位二進(jìn)制序列M(x)可以看作是D(x)和CRC校驗(yàn)碼的組合，去掉M(x)序列的后r位就是發(fā)送的原始數(shù)據(jù)。所以CRC的解碼過程則是對(duì)接收的前p位二進(jìn)制數(shù)據(jù)進(jìn)行如編碼一樣的CRC校驗(yàn)，發(fā)送方和接收方用同一個(gè)生成多項(xiàng)式G(x)，將校驗(yàn)得到的r位CRC校驗(yàn)碼與接收的M(x)序列的后r位CRC校驗(yàn)碼相比較，以兩個(gè)校驗(yàn)碼是否相同為據(jù)，判斷數(shù)據(jù)幀是否出錯(cuò)。兩者相同，則表示數(shù)據(jù)幀傳輸正確；反之，則表示數(shù)據(jù)傳輸中出現(xiàn)錯(cuò)誤。

CRC編碼實(shí)際上是將待發(fā)送的p位二進(jìn)制多項(xiàng)式D(x)轉(zhuǎn)換成了可以被G(x)除盡的p＋r位二進(jìn)制多項(xiàng)式M(x)。所以CRC的解碼過程也可以通過對(duì)M序列直接進(jìn)行除法取余式運(yùn)算，即:



M(x)G(x)=Q(x)+R(x)G(x)



所得到的余式R(x)若為零則表示數(shù)據(jù)傳輸正確，否則認(rèn)為在傳輸過程中發(fā)生錯(cuò)誤。許多CRC的硬件解碼電路就是按這種方式進(jìn)行檢錯(cuò)的。

1.3 CRC的算法分析

以上介紹了CRC校驗(yàn)碼的編碼和解碼原理，很明顯，CRC校驗(yàn)過程就是進(jìn)行除法取余式運(yùn)算，實(shí)際上是一個(gè)循環(huán)移位的模2邏輯異或運(yùn)算。這也就是CRC算法要解決的問題。

算法的依據(jù)和多項(xiàng)式的除法性質(zhì)有關(guān)^［3］。如果一個(gè)m位的多項(xiàng)式t(x)除以一個(gè)r階的生成多項(xiàng)式g(x)，t(x)=am－1xm－1+am－2xm－2+…+a2x2+a1x1+a0，將每一位akxk(0≤k＜m)提出來，在后面補(bǔ)足r個(gè)0后，單獨(dú)去除生成多項(xiàng)式g(x)，得到余式位yk(x)，則將ym－1(x)⊕ym－2(x)⊕…⊕y0(x)后得到的就是t(x)由生成多項(xiàng)式g(x)得到的余式。

上述算法是依據(jù)CRC校驗(yàn)碼的產(chǎn)生原理來實(shí)現(xiàn)的，即計(jì)算法。這種方法代碼簡(jiǎn)單，容易實(shí)現(xiàn)，所占用的內(nèi)存也比較少，而且修改靈活，可移植性好，對(duì)任意長(zhǎng)度的生成多項(xiàng)式都適用。但是這種以bit為單位對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)的算法對(duì)于發(fā)送的數(shù)據(jù)不長(zhǎng)的情況比較適合。如果發(fā)送的數(shù)據(jù)塊很長(zhǎng)時(shí)，逐個(gè)bit進(jìn)行校驗(yàn)，就會(huì)占用很多的處理器處理時(shí)間，大大降低校驗(yàn)的效率，尤其在高速通訊的場(chǎng)合，這是不允許的，這時(shí)可采用一次處理4位、8位、16位等方法，即是常用的按半字節(jié)、按字節(jié)查表法［4］。

查表法的優(yōu)缺點(diǎn)與計(jì)算法剛好相反，運(yùn)算速度快，不過這種方法要事先計(jì)算出一個(gè)參數(shù)表，需要占用相當(dāng)大的內(nèi)存空間，這就是查表法的缺點(diǎn)。本文不詳述這種方法。計(jì)算法和查表法各有優(yōu)缺點(diǎn)，實(shí)際應(yīng)用時(shí)，根據(jù)應(yīng)用場(chǎng)合對(duì)速度和內(nèi)存的不同要求，選擇最合適的校驗(yàn)方法。

2 CRC的DSP實(shí)現(xiàn)

2.1 用DSP實(shí)現(xiàn)CRC的設(shè)計(jì)思想

不同CRC碼的生成多項(xiàng)式各不相同，CRC碼的比特?cái)?shù)也不同，且在有的通信協(xié)議中要求將余數(shù)寄存器先初始化為全0，另外的則須初始化為全1。因此，在程序設(shè)計(jì)時(shí)必須充分利用CRC碼的共性及所用DSP指令具有代碼簡(jiǎn)潔、容易實(shí)現(xiàn)、運(yùn)算速度快等特點(diǎn)。

CRC的編解碼用到模2的多項(xiàng)式除法，而多項(xiàng)式除法可以采用帶反饋的移位寄存器來實(shí)現(xiàn)，因此，用DSP來實(shí)現(xiàn)CRC編解碼的關(guān)鍵是通過DSP來模擬一個(gè)移位寄存器(也就是模擬手寫多項(xiàng)式除法)?？紤]到TMS320C54x系列DSP的累加器A和B均為40位，因此，可以用一個(gè)40位累加器A作為移位寄存器，若CRC碼不夠40位(設(shè)為k位)，則僅用到A的最高k位，無用位就用0填充［5］。

在CRC的編碼和解碼中均涉及到碼的移位和異或操作，這可以通過C54x系列的SFTA(算術(shù)移位)和XOR(異或)兩條指令來實(shí)現(xiàn)。C54x系列還提供了特殊指令bitt和xc。bitt指令利用寄存器T，取出一個(gè)16位數(shù)據(jù)中的第(15－T)位，并送入TC(TC是特殊寄存器中的一位)。xc指令是條件執(zhí)行語句，此指令先判斷所列條件是否滿足，再?zèng)Q定是否執(zhí)行其后的2條單周期指令或1條雙周期指令。其實(shí)現(xiàn)步驟如下：

(1) 先將CRC移位寄存器(即余數(shù)寄存器)A的每一位有效位均初始化為全0或全1(與協(xié)議有關(guān))，而無用位清0；

(2) 將CRC移位寄存器中的值左移一位，判斷移出的第一位與輸入序列的最高位異或之后是否為1；

(3) 若是1，則將A與生成多項(xiàng)式進(jìn)行異或再跳到步驟(2)處理下一位;否則，直接跳到步驟(2)繼續(xù)處理下一位。

在手寫多項(xiàng)式除法的過程中可以發(fā)現(xiàn)，生成多項(xiàng)式即除式一共為k＋1位，而余數(shù)寄存器A里僅有k位有效位，這可以視為余數(shù)寄存器的k＋1位永遠(yuǎn)為0，因此，在實(shí)際的異或運(yùn)算時(shí)，生成多項(xiàng)式的最高位即k＋1位不必參與運(yùn)算。

重復(fù)(2)、(3)兩步，直到輸入信息位全部處理完為止，則A的最高k位為進(jìn)行多項(xiàng)式除法后所得的余數(shù)，若余數(shù)寄存器先初始化為全0，則此時(shí)A的最高k位就是CRC校驗(yàn)碼，若余數(shù)寄存器先初始化為全1，則須將A取反后最高k位才是CRC碼。

解碼時(shí)，則是接收方對(duì)接收的原始數(shù)據(jù)進(jìn)行同樣的CRC校驗(yàn)，將得到的CRC碼與發(fā)送方發(fā)送過來的CRC碼比較來判斷數(shù)據(jù)傳輸是否出錯(cuò)。

2.2 CRC流程圖

為了實(shí)現(xiàn)上節(jié)講述的設(shè)計(jì)思想，可以在程序中用指針AR2指向輸入信息，用AR3指向輸入信息字的某一位，用AR4表示夠一個(gè)字的個(gè)數(shù)，AR5表示不夠一個(gè)字的比特?cái)?shù)，即：若參加計(jì)算的信息比特?cái)?shù)為164，則AR4＝10，AR5＝4。該方法運(yùn)用比較靈活，用他能夠?qū)崿F(xiàn)任意信息長(zhǎng)度的40位以內(nèi)任意CRC碼的編解碼。

但在實(shí)際的通信應(yīng)用中，一般以字為單位傳輸數(shù)據(jù)。為了依次取出一個(gè)字中的bit15，bit14，…，bit0等16位信息位，在程序中可用一個(gè)全局變量bitpos，共占16個(gè)字，并將這16個(gè)地址的內(nèi)容依次賦值為0，1，2，…，15，而在程序

中這些值不能被改變。為了實(shí)現(xiàn)循環(huán)長(zhǎng)度為16的循環(huán)尋址，bitpos的地址必須為32字的整數(shù)倍。CRC編解碼的流程圖如圖1所示。

圖1 CRC編解碼流程圖

3 結(jié) 語

本文詳細(xì)介紹了循環(huán)冗余校驗(yàn)碼的編解碼原理，通過反復(fù)測(cè)試，證明了上述CRC碼的編碼和解碼的設(shè)計(jì)思想是正確的，能正確實(shí)現(xiàn)CRC-4，CRC-8，CRC-12，CRC-16，CCITT，CRC-32等的CRC碼的編碼和解碼。用DSP匯編語言編寫程序，具有代碼簡(jiǎn)潔，編解碼效率高，運(yùn)算速度快，實(shí)時(shí)性好，占用系統(tǒng)資源少等優(yōu)點(diǎn)［6］。該設(shè)計(jì)思想也適用于任意40位以內(nèi)的CRC編碼和解碼，在其他DSP上也可以很方便地實(shí)現(xiàn)，具有一定的實(shí)用價(jià)值。

參 考 文 獻(xiàn)

［1］樊昌信.通信原理［M］.北京：國(guó)防工業(yè)出版社，2001.

［2］申敏，鄧矣兵，鄭建宏，等.DSP原理及其在移動(dòng)通信中的應(yīng)用［M］.北京：人民郵電出版社，2001.

［3］周霖.DSP系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［M］.北京：國(guó)防工業(yè)出版社，2004.

［4］鄒彥.DSP原理及應(yīng)用［M］.北京：電子工業(yè)出版社，2005.

［5］朱銘鋯，趙勇，甘泉，等.DSP應(yīng)用系統(tǒng)設(shè)計(jì)［M］.北京：電子工業(yè)出版社，2002.

［6］鄭紅.TMS320C54xDSP應(yīng)用系統(tǒng)設(shè)計(jì)［M］.北京：北京航空航天大學(xué)出版社，2002.

［7］姚七棟，張春玉.CRC校驗(yàn)及其軟件實(shí)現(xiàn)［J］.現(xiàn)代電子技術(shù)，2006，29(13):67-68，71.



作者簡(jiǎn)介 華 濤 男，1976年出生，江西臨川人，工學(xué)碩士，工程師。主要從事自動(dòng)檢測(cè)與控制技術(shù)方向的研究。吳 進(jìn) 女，1975年出生，江蘇常州人，工學(xué)碩士，講師。主要從事數(shù)字信號(hào)處理方向的研究。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。