在Virtex-5 FPGA中使用CRC硬模塊
數(shù)據(jù)損壞是與數(shù)據(jù)傳輸和存儲(chǔ)有關(guān)的首要問題。只要是在通道上傳輸數(shù)據(jù),就總會(huì)有出現(xiàn)某些錯(cuò)誤的有限概率。
本文引用地址:http://butianyuan.cn/article/80754.htm關(guān)鍵是接收模塊要能區(qū)分無錯(cuò)消息和有錯(cuò)消息。檢錯(cuò)有多種方法,其中大多數(shù)都是專門為此目的引入冗余位。數(shù)據(jù)通信中常用的檢錯(cuò)方法包括奇偶碼、漢明碼和循環(huán)冗余校驗(yàn)(CRC),其中CRC使用最廣泛。
CRC根據(jù)一個(gè)給定的數(shù)據(jù)位組算出,然后在傳輸或存儲(chǔ)之前附加到數(shù)據(jù)幀尾部。接收或檢索到幀后,對(duì)其內(nèi)容重新計(jì)算CRC,以此來驗(yàn)證其有效性,確保數(shù)據(jù)無誤。
本文簡(jiǎn)述CRC計(jì)算所依據(jù)的原理,并且探討用線性反饋移位寄存器實(shí)現(xiàn)其硬件的方法。然后,我們把注意力轉(zhuǎn)向Xilinx?VirtexTM-5 LXT/SXT 器件中存在的 CRC 硬模塊。
原理
加法和減法運(yùn)算是用模2算法執(zhí)行;也就是說,這兩種運(yùn)算與“異或”(XOR)運(yùn)算相同。除了沒有進(jìn)位,多項(xiàng)式算法中的兩數(shù)相加與普通二進(jìn)制算法中的多數(shù)相加相同。
例如:二進(jìn)制消息流11001011表達(dá)為x7+x6+x3+x+1。傳輸點(diǎn)與接收點(diǎn)約定一個(gè)固定多項(xiàng)式,稱為生成器多項(xiàng)式;這是CRC計(jì)算的關(guān)鍵參數(shù)。
將數(shù)據(jù)解釋為一個(gè)多項(xiàng)式的系數(shù),用一個(gè)給定的生成器多項(xiàng)式除這些系數(shù)。除得的余數(shù)就是CRC。假設(shè)有一個(gè)m位消息序列和一個(gè)r階生成器多項(xiàng)式,發(fā)射器創(chuàng)建一個(gè)n位 (n=m+r)序列,稱為幀校驗(yàn)序列 (FCS),使這個(gè)(m+r)位合成幀可以被一個(gè)預(yù)先確定的序列整除。
發(fā)射器將r個(gè)0位附加到m位的消息,并且用生成器多項(xiàng)式除所得 m+r-1階多項(xiàng)式。這樣可得到一個(gè)階數(shù)等于或小于(r-1)的余數(shù)多項(xiàng)式。該余數(shù)多項(xiàng)式有r個(gè)系數(shù),這些系數(shù)形成校驗(yàn)和。將商丟棄。傳輸?shù)臄?shù)據(jù)是原m位消息后附r位校驗(yàn)和。
在接收器上,可以按以下兩種標(biāo)準(zhǔn)方法之一評(píng)估所接收數(shù)據(jù)的有效性:
對(duì)收到的前m個(gè)位再次計(jì)算校驗(yàn)和,然后與收到的校驗(yàn)和(收到的后r個(gè)位)進(jìn)行比較。
對(duì)收到的全部(m+r)個(gè)位計(jì)算校驗(yàn)和,然后與一個(gè)0余數(shù)進(jìn)行比較。
為了說明第二種方法如何得出 0余數(shù),我們做如下約定:
M=消息的多項(xiàng)表達(dá)式
R=發(fā)射器上所算得余數(shù)的多項(xiàng)表達(dá)式
G=生成器多項(xiàng)式
Q=用G除M得到的商
傳輸?shù)臄?shù)據(jù)對(duì)應(yīng)于多項(xiàng)式 Mxr–R。變量xr表示消息為容納校驗(yàn)和而產(chǎn)生的一個(gè)r位移位。
我們知道:Mxr=QG+R
在發(fā)射器上將校驗(yàn)和R附加到消息中相當(dāng)于從消息中減去余數(shù)。于是,傳輸?shù)臄?shù)據(jù)變?yōu)镸xr-R=QG,這顯然是G的倍數(shù)。這就是我們?cè)诘诙N情況下得到0余數(shù)的過程。
不過,這一過程對(duì)所傳輸數(shù)據(jù)中首0位和尾0位的個(gè)數(shù)不敏感。換句話說,無論消息插入還是刪除尾0位,余數(shù)都保持為0,從而使錯(cuò)誤漏檢,這表明不會(huì)復(fù)原成同樣的位序列。下面介紹一種克服這一缺點(diǎn)的變通辦法。
剩余法
實(shí)際上,校驗(yàn)和經(jīng)過反演后才附加到消息中。這就使接收器上算出的余數(shù)(超過m+r位)不為0。在這類情況下,接收器上得到的余數(shù)是一個(gè)固定值,稱為多項(xiàng)式的剩余值。
做一點(diǎn)演算有助于更清楚地說明這一概念。
假定%符號(hào)在下列表達(dá)式中表示模運(yùn)算。
對(duì)于未經(jīng)反演附加校驗(yàn)和的情況:
(Mxr–R)xr%G=0
在這種情況下,接收器會(huì)執(zhí)行與發(fā)射器一樣的移位運(yùn)算。
現(xiàn)在,考慮校驗(yàn)和在發(fā)射器上經(jīng)反演后附加到消息流的情況: (Mxr–Rc)xr% G
其中,Rc表示經(jīng)過反演的校驗(yàn)和。
還可以將其寫成:(Mxr– R +(xr-1+...+x+ 1)) xr% G
一個(gè)位的反碼與其對(duì)1異或運(yùn)算的結(jié)果相同。這里的+號(hào)表示模2算法中的加法(另請(qǐng)注意,在模2算法中,加法和減法運(yùn)算相同)。
在這種情況下,余數(shù)與以下表達(dá)式相同:(xr-1+...+x+1) xr% G
對(duì)于給定的生成器多項(xiàng)式來說,此表達(dá)式的計(jì)算結(jié)果將是一個(gè)常數(shù)。
最常用的CRC 32生成器多項(xiàng)式是G(x) = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
該式在十六進(jìn)制中是04C11DB7。
與CRC-32對(duì)應(yīng)的常數(shù)剩余值在十六進(jìn)制中是C704DD7B。對(duì)于給定的生成器多項(xiàng)式G來說,無論在輸入端提供何種數(shù)據(jù)樣式,剩余值仍為常數(shù)。
硬件實(shí)現(xiàn)
CRC校驗(yàn)和的計(jì)算是多項(xiàng)式除法過程。在硬件中實(shí)現(xiàn)該過程需要使用一個(gè)移位寄存器(亦稱CRC寄存器)。該移位寄存器的長(zhǎng)度與生成器多項(xiàng)式的階數(shù)相同。
CRC 計(jì)算過程如下:
1.初始化CRC寄存器。
2.持續(xù)獲取消息位,直到獲得所有消息位。如果CRC寄存器中的高階位是1,則向左移一位,并且將其結(jié)果與G進(jìn)行異或運(yùn)算。否則,僅向左移一位。
對(duì)給定消息完成所有這些步驟后,CRC寄存器中剩 下的就是余數(shù)。
可以用一種稱為線性反饋移位寄存器(LFSR)的電路執(zhí)行這些步驟。圖1所示為用CRC32多項(xiàng)式計(jì)算 CRC 的 LFSR 實(shí)現(xiàn)方法。請(qǐng)注意,異或門的布局取決于生成器多項(xiàng)式中項(xiàng)值為 1 的對(duì)應(yīng)項(xiàng)的系數(shù)。圖中的編號(hào)方框各代表一個(gè)存儲(chǔ)元件(觸發(fā)器)。
CRC模塊
CRC 的硬件實(shí)現(xiàn)使用一個(gè)簡(jiǎn)單的 LFSR。這種電路雖然實(shí)現(xiàn)起來簡(jiǎn)單,但對(duì)于一個(gè)n位數(shù)據(jù)流來說,要占用n個(gè)時(shí)鐘周期來計(jì)算CRC值。在必須以較高速度處理數(shù)據(jù)幀的高速數(shù)據(jù)網(wǎng)絡(luò)應(yīng)用中,這樣的延遲是無法忍受的。這類高速網(wǎng)絡(luò)應(yīng)用迫切需要對(duì)并行數(shù)據(jù)流實(shí)現(xiàn)CRC生成和校驗(yàn)。
Virtex-5 LXT/SXT器件中實(shí)現(xiàn)的CRC模塊可幫助設(shè)計(jì)人員加速校驗(yàn)和計(jì)算。
Virtex-5 LXT/SXT器件中的 CRC硬模塊基于CRC32多項(xiàng)式。Virtex-5 FPGA含有CRC32和 CRC64 兩種硬模塊,能以一個(gè)時(shí)鐘周期的延遲為4位和8位數(shù)據(jù)輸出生成CRC。其界面簡(jiǎn)單易用。硬模塊對(duì)給定的消息流起著CRC計(jì)算器的作用,同時(shí)提供一些針對(duì) CRC的參數(shù)作為輸入。CRC的比較功能已經(jīng)超出硬模塊的范圍,應(yīng)集成到FPGA架構(gòu)中。
FPGA 中的每個(gè)CRC硬模塊異步計(jì)算一個(gè)32位校驗(yàn)和。
圖2是說明硬模塊架構(gòu)的模塊級(jí)圖。CRC硬模塊提供一個(gè)位反演和字節(jié)反轉(zhuǎn)的輸出。
圖3所示為CRC硬模塊的應(yīng)用概況。在發(fā)射器上,CRC經(jīng)計(jì)算后附加到給定數(shù)據(jù)包的尾部。在接收器上,對(duì)連帶發(fā)射器所附加的CRC一起接收到的整個(gè)數(shù)據(jù)包重新計(jì)算CRC。
所收數(shù)據(jù)包的有效性用剩余法來確定。對(duì)于本例中的CRC32多項(xiàng)式來說,剩余值的計(jì)算結(jié)果將是十六進(jìn)制的1CDF4421,這其實(shí)就是 C704DDB7的位反演和字節(jié)反轉(zhuǎn)值。字節(jié)反轉(zhuǎn)和位反演的概念如圖4所示。
圖5所示為正常CRC運(yùn)算的波形
我們還提供一個(gè)LogICORETM CRC 向?qū)?,其中?Virtex-5 器件中的CRC硬模塊提供一個(gè)LocalLink封裝。其內(nèi)核還提供了一個(gè)說明如何使用 CRC 硬模塊的設(shè)計(jì)實(shí)例。此外,內(nèi)核提供了各種選項(xiàng),如流水線處理、補(bǔ)數(shù)計(jì)算和轉(zhuǎn)置。
結(jié)論
Xilinx FPGA中的CRC模塊使設(shè)計(jì)人員能夠輕松地將檢錯(cuò)機(jī)制加入到各種設(shè)計(jì)中??梢杂肅ORE GeneratorTM軟件中提供的CRC Wizard IP加入符合不同協(xié)議(如 Aurora 和 PCI Express)的檢錯(cuò)功能。
評(píng)論