張惠崢

（中國電子科技集團公司第五十四研究所，河北石家莊050081）

0 引言

循環(huán)冗余碼CRC算法是測控及通信領域中應用廣泛的一種算法，ITU-T建議對異步轉移模式ATM信元信頭采用CRC算法進行誤碼檢測和校正，在同步數(shù)字系列SDH傳輸幀中ATM信元的定界也是通過CRC校驗碼的計算獲得的。CRC校驗碼的計算一般可分為軟件和硬件實現(xiàn)2種方法，由于軟件代碼的順序執(zhí)行的特點，在對速度要求甚高的場合很難滿足要求;硬件實現(xiàn)一般采用線性反饋移位寄存器組LSFR方法完成，這種方法簡單，但每次只能處理一位二進制數(shù)據(jù)，這種串行的硬件實現(xiàn)方法也很難滿足速度較高的場合。筆者在設計高速ATM接口CRC電路的實踐過程中，在查閱大量資料的基礎上總結出了一種易于采用FPGA實現(xiàn)的并行CRC算法進行信頭誤碼檢測和校正以及信元定界的設計。

1 CRC算法

CRC是一種系統(tǒng)縮短循環(huán)碼，它是利用除法及余數(shù)的原理來做錯誤檢測的。利用CRC進行檢錯的過程可簡單描述為:在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督碼（CRC碼），附在原始信息后邊，構成一個新的二進制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”，CRC校驗采用的就是多項式編碼方法，發(fā)送方和接收方用同一個生成多項式g（x），并且g（x）的首位和最后一位的系數(shù)必須為1。CRC校驗可以100%地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。

CRC校驗碼的編碼方法是用待發(fā)送的二進制數(shù)據(jù)t（x）除以生成多項式g（x），將最后的余數(shù)作為CRC校驗碼。其實現(xiàn)步驟如下:

①設待發(fā)送的數(shù)據(jù)塊是m位的二進制多項式t（x），生成多項式為r階的g（x）。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應的二進制多項式為xrt（x）;

②用生成多項式g（x）去除xrt（x），求得余數(shù)為階數(shù)為r-1的二進制多項式y(tǒng)（x）。此二進制多項式y(tǒng)（x）就是t（x）經(jīng)過生成多項式g（x）編碼的CRC校驗碼;

③用xrt（x）以模2的方式減去y（x），得到二進制多項式xrt′（x）。xrt′（x）就是包含了CRC校驗碼的待發(fā)送字符串。

從CRC的編碼規(guī)則可以看出，CRC編碼實際上是將待發(fā)送的m位二進制多項式t（x）轉換成了可以被g（x）除盡的m+r位二進制多項式xrt′（x），所以解碼時可以用接收到的數(shù)據(jù)去除g（x），如果余數(shù)為零，則表示傳輸過程沒有錯誤;如果余數(shù)不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時xrt′（x）可以看做是由t（x）和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。

2 高速ATM中并行CRC設計實現(xiàn)

采用CRC串行算法一個時鐘周期內(nèi)只能處理一位數(shù)據(jù)，在某些高速場合只能靠提高時鐘頻率來達到所需的速度要求，這增加了開發(fā)的難度和成本。在基于SDH的ATM網(wǎng)絡接口中，數(shù)據(jù)傳輸速率是155Mbit/s或更高的速率等級，采用串行方式設計出的電路在高速不能穩(wěn)定工作，同時高的數(shù)據(jù)傳輸速率對FPGA芯片等級也提出了很高的要求。為解決此問題，在進行FPGA設計時，串行傳輸階段采用并行的CRC算法來降低設計中對芯片處理速度的要求。目前已采用的CRC并行算法是查表法和基于查表法而導出的一些方法，這些方法均需要存儲長度較大的CRC余數(shù)表，隨著并行度的增加，余數(shù)表的長度按指數(shù)增加，其實現(xiàn)性亦隨之大大降低，因此需要提出新的并行CRC算法，用于實現(xiàn)高速鏈路上CRC的產(chǎn)生和校正電路。

采用并行處理方法的目的都是要提高處理的速度，以達到更高的數(shù)據(jù)處理能力。筆者為了從CRC的基本算法中得到并行處理的算法，采用了基于矩陣運算、按位依次展開、Z變換等數(shù)學知識進行遞推，直接推導出數(shù)據(jù)的邏輯關系公式。在并行處理時，每次處理的位數(shù)可以是固定的。

CRC校驗電路設計分為CRC編碼、檢測和校正2大部分，編碼用于對輸入數(shù)據(jù)計算CRC校驗碼，檢測和校正用于驗證接收到的數(shù)據(jù)是否正確，并對檢測到的單bit錯誤進行糾正，其實編碼和檢測這2個過程一樣的，不同的是檢測時需要判斷得到CRC校驗碼是否為0，如果是0則表示數(shù)據(jù)正確，如果不為0則表示數(shù)據(jù)有錯。糾正模塊對有錯的bit進行糾錯，糾正不過來的扔掉。下面分別對CRC并行編碼、檢測和校正電路的FPGA實現(xiàn)進行詳細介紹。

2.1 ATM信頭并行CRC編碼

每個ATM信元的信頭均含有VPI/VCI控制選路及其他重要的信息，網(wǎng)絡據(jù)此選擇路由，并決定目的地址，為此需要對信頭進行有效的保護。ITU-T建議采用CRC-8實現(xiàn)對ATM信元信頭信息的保護，進行信頭誤碼差錯控制（HEC），該算法可以檢測到多個bit錯誤并能糾正單個bit錯誤。發(fā)送端對信頭進行CRC編碼，接收端對收到的數(shù)據(jù)進行誤碼檢測與校正。

如圖1所示，ATM信元由53個8bit字節(jié)組成，其中前5個字節(jié)構成信頭，后48字節(jié)構成信元凈荷，被保護的信息是信頭前4個字節(jié)，位長為k=32，監(jiān)督位（即HEC字段）為第5個字節(jié)，位長為r=8，循環(huán)碼組長度n=k+r=40，所用生成多項式為:G（x）=x8+x2+x+1。在發(fā)送端對信頭的前4個字節(jié)實施CRC算法生成HEC字段。

在并行方法中，一系列的移位運算合并起來在1個時鐘周期內(nèi)完成。對于一個含有qbit的信息，如果信息的kbit來到后k次移位運算綜合起來在1個時鐘周期內(nèi)完成，那么僅需要[q/k]個時鐘周期即可計算出余數(shù)。并行CRC算法一次讀入多位數(shù)據(jù)，通過當前余數(shù)與讀入數(shù)據(jù)的運算，得出新的余數(shù)。顯然，一個時鐘周期處理n位數(shù)據(jù)的并行算法在計算結果上與串行算法處理n個時鐘周期所得的余數(shù)應該相同。基于這一點，利用高等數(shù)學知識采用遞推的方法推導出CRC校驗碼與輸入數(shù)據(jù)和生成多項式的邏輯關系，然后直接運算得出CRC校驗碼，算法中CRC碼的計算和校驗完全由一系列的組合邏輯實現(xiàn)，十分有利于轉化為硬件電路。

圖1 ATM信元的53字節(jié)

這里著眼于介紹CRC的并行算法與FPGA實現(xiàn)，原理和推導過程不再詳述，下面直接給出XOR電路的結果。這里的D（*）代表*位數(shù)據(jù)，Z（*）代表上一次計算的*位CRC值。

在進行FPGA設計時，將并行CRC編碼計算做成一個單獨的函數(shù)，這樣發(fā)送端和接收端進行CRC計算時都可以調用。

2.2 ATM信頭并行CRC檢測與校正

在接收端對信頭的5個字節(jié)實施循環(huán)冗余校驗來判斷信頭的正確性，檢測方法與發(fā)送端的編碼算法相似，通過把信頭前4個字節(jié)的CRC計算結果與HEC字段進行異或，如果為0就表示接收到的碼字可能是一個合法的信頭，否則表示該信元信頭有誤。

ITU-T I.432.1建議的信頭差錯控制工作的2種模式如圖2所示。平時，接收端工作于單bit“糾錯模式”，如果檢測到單個bit錯誤，接收器糾正這個錯誤并轉到“檢錯模式”;如果檢測到多bit錯誤，它不可能糾正，只好丟棄這個信元，并轉到“檢錯模式”。在檢錯模式下，所有檢測到錯誤的信元都被丟棄，接收器工作模式不變;只有收到不含差錯的信頭時，接收器才回到“糾錯模式”。當檢測出誤碼后，只有當接收器處于糾錯模式時，而且能夠成功地糾正單bit誤碼，并重新組成正確的信頭，才能得到正確的有效信元。當接收器工作于檢錯模式時，或糾錯不成功，或糾錯后的信頭不容許時，信元都要被丟棄。如果發(fā)現(xiàn)信頭有誤碼而不能糾正時，寧可丟掉信元而避免將錯誤的信元送到網(wǎng)絡節(jié)點。

圖2 信頭差錯控制工作模式

實現(xiàn)ATM信元信頭的單bit糾錯功能，常用的方法是查表法，但需要在查找表中存儲40個可能的錯誤伴隨式模式，占用芯片的資源較多，而且會對電路的復雜程度和最大工作速度產(chǎn)生較大影響，因此查表法并不是實現(xiàn)糾錯功能的理想解決方案。利用A.Maniatopoulos提出的一種通過迭代計算導出的“與平面”邏輯來實現(xiàn)高速ATM信元信頭糾錯是一種簡潔易實現(xiàn)的方法。利用“與平面”邏輯確定錯誤圖樣后再與原始數(shù)據(jù)相異或就實現(xiàn)了信頭的單bit糾錯功能。

介于目前大部分文獻資料對CRC的糾錯功能電路實現(xiàn)介紹的比較少，這里把糾錯模塊進行詳細說明，表1是設計的糾錯模塊的端口說明。

表1 糾錯模塊的端口說明

糾錯模塊VHDL語言的主要實現(xiàn)代碼如下:

correc-data＜=data xor error;

error（0）:=（not d（7））and d（6）and d（5）and（not d（4））and（not d（3））and（not d（2））and d（1）and（not d（0））;

error（1）:=d（7）and d（6）and（not d（5））and（not d（4））and（not d（3））and d（2）and（not d（1））and（not d（0））;

error（2）:=d（7）and（not d（6））and（not d（5））and（not d（4））and d（3）and d（2）and d（1）and d（0）;

error（3）:=（not d（7））and（not d（6））and（not d（5））and d（4）and d（3）and（not d（2））and（not d（1））and d（0）;

error（4）:=（not d（7））and（not d（6））and d（5）and d（4）and（not d（3））and（not d（2））and d（1）and（not d（0））;

error（5）:=（not d（7））and d（6）and d（5）and（not d（4））and（not d（3））and d（2）and（not d（1））and（not d（0））;

error（6）:=d（7）and d（6）and（not d（5））and（not d（4））and d（3）and（not d（2））and（not d（1））and（not d（0））;

error（7）:=d（7）and（not d（6））and（not d（5））and d（4）and（not d（3））and d（2）and d（1）and d（0）;

3 ATM信元定界

信元定界是接收方為了確定信元的起始邊界位置，以便于信元后續(xù)處理的正確性。通過對CRC校驗碼的計算搜尋正確的HEC，也就是判斷信頭中前4個字節(jié)與后1個字節(jié)是否長期符合CRC-8的關系，就可實現(xiàn)連續(xù)信元流的定界。另外，為防止因誤碼破壞CRC-8關系而誤判為信元失界，對于偶爾的HEC不一致，不作失界處理。

因SDH幀中提供同步信號，如圖3所示，接收端一開始對收到的數(shù)據(jù)逐字節(jié)進行符合CRC編碼規(guī)則的檢測，搜尋正確的HEC，工作在搜索狀態(tài);一旦找到正確的HEC，立即轉到預同步狀態(tài)，逐信元地核對HEC，只有連續(xù)收到δ個含有正確HEC的信元時，才算真正找到了信元邊界，進入了信元同步狀態(tài)，否則仍要回到搜索態(tài)。在同步狀態(tài)下，接收端仍需逐信元進行HEC檢測，一旦發(fā)現(xiàn)α個連續(xù)的含有不正確HEC的信元時，就認為丟失了信元邊界，重新回到搜索狀態(tài)。

δ值決定了抗拒信元偽定界的能力，δ值越大，識別偽定界的能力越強，但δ值太大時意味著真正定界后仍沒判為定界，易受誤碼影響使捕捉時間也越長，為此應合理選擇δ值。α值決定了信元偽失界的能力，α值越大，抗誤碼影響的能力越強，但真正失界時所需進入搜索狀態(tài)的時間也越長，因而α值也應合理選擇。ITU-T I.432建議中規(guī)定δ=6，α=7。

圖3 信元定界狀態(tài)圖

4 結束語

利用上述方法進行了高速ATM信元信頭差錯控制與信元定界的電路設計，用VHDL語言編寫了可綜合邏輯代碼，最后在XILINX公司的器件Spartan3系列的XC3S4000上進行設計電路的實現(xiàn)，編譯結果顯示CRC編碼生成、檢測與糾錯3個模塊僅占用了126個邏輯單元。設計的電路正確運行的最高時鐘頻率為155MHz，數(shù)據(jù)吞吐量超過1.2Gbit/s。工程應用結果表明，這種設計方式較以往的實現(xiàn)方式具有邏輯直接、精簡、速度更快，占用資源更少的優(yōu)點，可以很方便地在FPGA中實現(xiàn)并穩(wěn)定可靠，對于類似的并行處理電路也具有很好的借鑒意義。

[1]李永忠.通用并行CRC計算原理及其硬件實現(xiàn)方法[J].西北民族學院學報:自然科學版，2002，23（1）:33-37.

[2]MANIATOPULOS A.Single-bit error-correction circuit for ATM interface[J].IEE Electronics Letters，1995（31）:617-618.

[3]ITU-T I.432.B-ISDN USER-NETWORK INTERFACE PHYSICAL LAYER SPECIFICATION:GENERAL CHARACTERISTICS[S].1999.

[4]楊衛(wèi)平.ATM接口中信元定界方法分析[J].現(xiàn)代有線傳輸，1997，25（4）:51-56.