張惠崢

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

0 引言

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

1 CRC算法

CRC是一種系統(tǒng)縮短循環(huán)碼，它是利用除法及余數(shù)的原理來做錯(cuò)誤檢測的。利用CRC進(jìn)行檢錯(cuò)的過程可簡單描述為:在發(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)式”，CRC校驗(yàn)采用的就是多項(xiàng)式編碼方法，發(fā)送方和接收方用同一個(gè)生成多項(xiàng)式g（x），并且g（x）的首位和最后一位的系數(shù)必須為1。CRC校驗(yàn)可以100%地檢測出所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤和長度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯(cuò)誤。所以CRC的生成多項(xiàng)式的階數(shù)越高，那么誤判的概率就越小。

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

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

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

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

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

2 高速ATM中并行CRC設(shè)計(jì)實(shí)現(xiàn)

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

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

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

2.1 ATM信頭并行CRC編碼

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

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

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

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

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

在進(jìn)行FPGA設(shè)計(jì)時(shí)，將并行CRC編碼計(jì)算做成一個(gè)單獨(dú)的函數(shù)，這樣發(fā)送端和接收端進(jìn)行CRC計(jì)算時(shí)都可以調(diào)用。

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

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

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

圖2 信頭差錯(cuò)控制工作模式

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

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

表1 糾錯(cuò)模塊的端口說明

糾錯(cuò)模塊VHDL語言的主要實(shí)現(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校驗(yàn)碼的計(jì)算搜尋正確的HEC，也就是判斷信頭中前4個(gè)字節(jié)與后1個(gè)字節(jié)是否長期符合CRC-8的關(guān)系，就可實(shí)現(xiàn)連續(xù)信元流的定界。另外，為防止因誤碼破壞CRC-8關(guān)系而誤判為信元失界，對于偶爾的HEC不一致，不作失界處理。

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

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

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

4 結(jié)束語

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

[1]李永忠.通用并行CRC計(jì)算原理及其硬件實(shí)現(xiàn)方法[J].西北民族學(xué)院學(xué)報(bào):自然科學(xué)版，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.