數據傳輸系統中ＣＲＣ校驗的ＤＳＰ算法實現
2008-04-12 00:00:00華濤吳進
現代電子技術 2008年7期
摘 要：循環冗余校驗碼是一種重要的循環碼，編碼和解碼方法簡單，容易實現，檢錯能力強，誤判概率幾乎為零，是一種效率極高的差錯控制方法，可以滿足通信系統可靠傳送信息的要求，在測控及數據通信中得到了非常廣泛的應用。詳細介紹了循環冗余校驗的編解碼原理，分析了用DSP實現CRC的合理性，最后給出了根據校驗原理實現的設計思想及流程圖，具有一定的實用價值。
關鍵詞：數據傳輸系統；循環冗余校驗；數字信號處理器；算法分析
中圖分類號：TN911.72文獻標識碼：B
文章編號：1004-373X(2008)07-083-03
DSP Implementation of CRC Algorithm in Data Communication System
HUA Tao1，WU Jin2
(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
通信的目的是將信息及時可靠地傳給對方，因此要求一個通信系統傳送信息必須可靠快速。由于傳輸距離、現場狀況、干擾等諸多因素的影響，設備之間的通信數據常會發生一些無法預測的錯誤。為了降低錯誤所帶來的影響，一般在通信時采用數據校驗的辦法［1］，而循環冗余碼校驗是常用的重要校驗方法之一。CRC校驗的檢錯能力強，在通信領域廣泛地用于實現差錯控制。數字信號處理器(DSP)是實施高速實時信號處理的專用處理器，目前DSP已成為通信、計算機、消費類電子產品等領域的基礎器件，被譽為信息社會革命的旗手。CRC的高效檢錯能力、DSP的實時處理能力，可以滿足通信系統傳送信息的兩大基本要求：可靠、快速。應用DSP系統來實現CRC，完成數據傳輸過程中的檢錯處理，便于集成，使用方便。使用DSP匯編語言，編解碼效率高，速度快，實時性好，占用系統資源少。因此CRC校驗被廣泛使用在各種數據校驗應用中。
1 循環冗余校驗碼
循環冗余校驗碼(Cyclic Redundancy Check Code，CRC)由線性分組碼的分支而來，是一種檢錯能力很強的循環碼。循環冗余校驗對傳送數據作錯誤偵測(Error Detecting)是利用除法及余數的原理。編碼和解碼方法簡單，容易實現，檢錯能力強，誤判概率幾乎為零，而且這種方法取得校驗碼的方式具有很強的信息覆蓋能力，是一種效率極高的錯誤校驗法。這種高效的差錯控制方法，在測控及數據通信中得到了廣泛的應用［2］。
1.1 CRC的編碼原理
CRC校驗采用多項式編碼方法，被處理的數據塊可以看作是一個n階的二進制多項式，即an-1 xn-1 + an-2 xx-2 +…+ a1 x + a0 。如一個8位二進制數10110101可以表示為：1x7+0x6+1x5+1x4+0x3+1x2+0x+1=x7+x5+x4+x2+1。多項式乘除法運算過程與普通代數多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進、借位，和邏輯異或運算一致。
CRC碼的編碼方法是用待發送的二進制數據t(x)除以生成多項式g(x)，g(x)的首位和最后一位的系數必須均為1，兩者相除之后將最后的余數作為CRC校驗碼。其實現步驟如下：
(1) 設待發送的數據塊是m位的二進制多項式t(x)，生成多項式為g(x)，階數為r。在數據塊的末尾添加r個0，數據塊的長度增加到m+r位，對應的二進制多項式為xrt(x)。
(2) 用生成多項式g(x)去除xrt(x)，求得余數為二進制多項式y(x)，階數為r-1。這個二進制多項式y(x)就是t(x)經過生成多項式g(x)編碼的CRC校驗碼。
(3) 用xrt(x)以模2的方式減去y(x)，得到二進制多項式xrt′(x)。xrt′(x)就是包含了CRC校驗碼的待發送字符串。
1.2 CRC的解碼原理
CRC校驗原理實際上就是在一個p位二進制數據序列之后附加一個r位二進制檢驗碼(序列)，從而構成一個總長為n＝p＋r位的二進制序列，例如，p位二進制數據序列D＝［dp-1 dp-2 …d1 d0］，r位二進制檢驗碼R＝［rr-1 rr-2…r1 r0］，所得到的這個n位二進制序列就是M＝［dp-1dp-2 …d1d0 rr-1 rr-2…r1 r0］；附加在p位二進制數據序列之后的這個r位二進制檢驗碼與數據序列的內容之間存在著某種特定的關系。如果因干擾等原因使數據序列中的某一位或某些位發生錯誤，這種特定關系就會被破壞。因此，通過檢查這一關系，就可以實現對數據正確性的檢驗。
校驗碼R是通過對數據序列D進行二進制除法取余式運算得到的，他被一個稱為生成多項式的(r＋1)位二進制序列G＝［gr gr-1…g1 g0］來除，用多項式可以表示為:
[SX(]xrD(x)[]G(x)[SX)]=Q(x)+[SX(]R(x)[]G(x)[SX)]
其中，xrD(x)表示將數據序列D左移r位(即在D的末尾再增加r個0位)，Q(x)代表這一除法所得的商，R(x)就是所需的余式。這一運算關系還可以用下式表達:
R(x)=Re［xrD(x)G(x)］
其中，Re［ ］表示對括號內的式子進行取余式運算。
由CRC碼的編碼過程可知，接收方接收的n位二進制序列M(x)可以看作是D(x)和CRC校驗碼的組合，去掉M(x)序列的后r位就是發送的原始數據。所以CRC的解碼過程則是對接收的前p位二進制數據進行如編碼一樣的CRC校驗，發送方和接收方用同一個生成多項式G(x)，將校驗得到的r位CRC校驗碼與接收的M(x)序列的后r位CRC校驗碼相比較，以兩個校驗碼是否相同為據，判斷數據幀是否出錯。兩者相同，則表示數據幀傳輸正確；反之，則表示數據傳輸中出現錯誤。
CRC編碼實際上是將待發送的p位二進制多項式D(x)轉換成了可以被G(x)除盡的p＋r位二進制多項式M(x)。所以CRC的解碼過程也可以通過對M序列直接進行除法取余式運算，即:
M(x)G(x)=Q(x)+R(x)G(x)
所得到的余式R(x)若為零則表示數據傳輸正確，否則認為在傳輸過程中發生錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。
1.3 CRC的算法分析
以上介紹了CRC校驗碼的編碼和解碼原理，很明顯，CRC校驗過程就是進行除法取余式運算，實際上是一個循環移位的模2邏輯異或運算。這也就是CRC算法要解決的問題。
算法的依據和多項式的除法性質有關［3］。如果一個m位的多項式t(x)除以一個r階的生成多項式g(x)，t(x)=am－1xm－1+am－2xm－2+…+a2x2+a1x1+a0，將每一位akxk(0≤k＜m)提出來，在后面補足r個0后，單獨去除生成多項式g(x)，得到余式位yk(x)，則將ym－1(x)⊕ym－2(x)⊕…⊕y0(x)后得到的就是t(x)由生成多項式g(x)得到的余式。
上述算法是依據CRC校驗碼的產生原理來實現的，即計算法。這種方法代碼簡單，容易實現，所占用的內存也比較少，而且修改靈活，可移植性好，對任意長度的生成多項式都適用。但是這種以bit為單位對數據進行校驗的算法對于發送的數據不長的情況比較適合。如果發送的數據塊很長時，逐個bit進行校驗，就會占用很多的處理器處理時間，大大降低校驗的效率，尤其在高速通訊的場合，這是不允許的，這時可采用一次處理4位、8位、16位等方法，即是常用的按半字節、按字節查表法［4］。
查表法的優缺點與計算法剛好相反，運算速度快，不過這種方法要事先計算出一個參數表，需要占用相當大的內存空間，這就是查表法的缺點。本文不詳述這種方法。計算法和查表法各有優缺點，實際應用時，根據應用場合對速度和內存的不同要求，選擇最合適的校驗方法。
2 CRC的DSP實現
2.1 用DSP實現CRC的設計思想
不同CRC碼的生成多項式各不相同，CRC碼的比特數也不同，且在有的通信協議中要求將余數寄存器先初始化為全0，另外的則須初始化為全1。因此，在程序設計時必須充分利用CRC碼的共性及所用DSP指令具有代碼簡潔、容易實現、運算速度快等特點。
CRC的編解碼用到模2的多項式除法，而多項式除法可以采用帶反饋的移位寄存器來實現，因此，用DSP來實現CRC編解碼的關鍵是通過DSP來模擬一個移位寄存器(也就是模擬手寫多項式除法)。考慮到TMS320C54x系列DSP的累加器A和B均為40位，因此，可以用一個40位累加器A作為移位寄存器，若CRC碼不夠40位(設為k位)，則僅用到A的最高k位，無用位就用0填充［5］。
在CRC的編碼和解碼中均涉及到碼的移位和異或操作，這可以通過C54x系列的SFTA(算術移位)和XOR(異或)兩條指令來實現。C54x系列還提供了特殊指令bitt和xc。bitt指令利用寄存器T，取出一個16位數據中的第(15－T)位，并送入TC(TC是特殊寄存器中的一位)。xc指令是條件執行語句，此指令先判斷所列條件是否滿足，再決定是否執行其后的2條單周期指令或1條雙周期指令。其實現步驟如下：
(1) 先將CRC移位寄存器(即余數寄存器)A的每一位有效位均初始化為全0或全1(與協議有關)，而無用位清0；
(2) 將CRC移位寄存器中的值左移一位，判斷移出的第一位與輸入序列的最高位異或之后是否為1；
(3) 若是1，則將A與生成多項式進行異或再跳到步驟(2)處理下一位;否則，直接跳到步驟(2)繼續處理下一位。
在手寫多項式除法的過程中可以發現，生成多項式即除式一共為k＋1位，而余數寄存器A里僅有k位有效位，這可以視為余數寄存器的k＋1位永遠為0，因此，在實際的異或運算時，生成多項式的最高位即k＋1位不必參與運算。
重復(2)、(3)兩步，直到輸入信息位全部處理完為止，則A的最高k位為進行多項式除法后所得的余數，若余數寄存器先初始化為全0，則此時A的最高k位就是CRC校驗碼，若余數寄存器先初始化為全1，則須將A取反后最高k位才是CRC碼。
解碼時，則是接收方對接收的原始數據進行同樣的CRC校驗，將得到的CRC碼與發送方發送過來的CRC碼比較來判斷數據傳輸是否出錯。
2.2 CRC流程圖
為了實現上節講述的設計思想，可以在程序中用指針AR2指向輸入信息，用AR3指向輸入信息字的某一位，用AR4表示夠一個字的個數，AR5表示不夠一個字的比特數，即：若參加計算的信息比特數為164，則AR4＝10，AR5＝4。該方法運用比較靈活，用他能夠實現任意信息長度的40位以內任意CRC碼的編解碼。
但在實際的通信應用中，一般以字為單位傳輸數據。為了依次取出一個字中的bit15，bit14，…，bit0等16位信息位，在程序中可用一個全局變量bitpos，共占16個字，并將這16個地址的內容依次賦值為0，1，2，…，15，而在程序
中這些值不能被改變。為了實現循環長度為16的循環尋址，bitpos的地址必須為32字的整數倍。CRC編解碼的流程圖如圖1所示。
圖1 CRC編解碼流程圖
3 結 語
本文詳細介紹了循環冗余校驗碼的編解碼原理，通過反復測試，證明了上述CRC碼的編碼和解碼的設計思想是正確的，能正確實現CRC-4，CRC-8，CRC-12，CRC-16，CCITT，CRC-32等的CRC碼的編碼和解碼。用DSP匯編語言編寫程序，具有代碼簡潔，編解碼效率高，運算速度快，實時性好，占用系統資源少等優點［6］。該設計思想也適用于任意40位以內的CRC編碼和解碼，在其他DSP上也可以很方便地實現，具有一定的實用價值。
參 考 文 獻
［1］樊昌信.通信原理［M］.北京：國防工業出版社，2001.
［2］申敏，鄧矣兵，鄭建宏，等.DSP原理及其在移動通信中的應用［M］.北京：人民郵電出版社，2001.
［3］周霖.DSP系統設計與實現［M］.北京：國防工業出版社，2004.
［4］鄒彥.DSP原理及應用［M］.北京：電子工業出版社，2005.
［5］朱銘鋯，趙勇，甘泉，等.DSP應用系統設計［M］.北京：電子工業出版社，2002.
［6］鄭紅.TMS320C54xDSP應用系統設計［M］.北京：北京航空航天大學出版社，2002.
［7］姚七棟，張春玉.CRC校驗及其軟件實現［J］.現代電子技術，2006，29(13):67-68，71.
作者簡介 華 濤 男，1976年出生，江西臨川人，工學碩士，工程師。主要從事自動檢測與控制技術方向的研究。吳 進 女，1975年出生，江蘇常州人，工學碩士，講師。主要從事數字信號處理方向的研究。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
