夏忠海，任勇峰，2，賈興中，2，郭佳欣

（1.中北大學(xué)電子測(cè)試技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，太原030051；2.中北大學(xué)儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，太原030051）

0 引 言

在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通信網(wǎng)絡(luò)等領(lǐng)域中，由于傳輸?shù)牟淮_定性及干擾等情況，使得通信出現(xiàn)異常，因此在串行通信中添加校驗(yàn)是必不可少的［1］。而FPGA來做數(shù)字信號(hào)處理是完全的硬件化、并行化編程操作，具有靈活調(diào)節(jié)的優(yōu)點(diǎn)［2］，故廣泛應(yīng)用于串行通信中。在通信中，常規(guī)的CRC校驗(yàn)是按比特計(jì)算的，雖然此方法能更清楚體現(xiàn)CRC算法的本質(zhì)，但當(dāng)發(fā)送的數(shù)據(jù)量很大時(shí)，因其一次只能處理一位數(shù)據(jù)，效率太低，且占用的邏輯資源較大，而查表法能夠按字節(jié)處理數(shù)據(jù)，避免了耗時(shí)的位運(yùn)算［3］，提高了數(shù)據(jù)的運(yùn)算量和運(yùn)算速率，大大優(yōu)化了系統(tǒng)的設(shè)計(jì)。

1 CRC校驗(yàn)原理

循環(huán)冗余校驗(yàn)碼（CRC）是一種系統(tǒng)的縮短循環(huán)碼，是由線性分組碼的分支而來，它只能檢查數(shù)據(jù)的錯(cuò)誤，而不能糾正傳輸錯(cuò)誤。在代數(shù)編碼理論中，將一個(gè)碼序列表示為一個(gè)多項(xiàng)式，碼序列中各碼元當(dāng)作多項(xiàng)式的系數(shù)，而CRC碼的結(jié)構(gòu)［4］如圖1所示。

圖1 CRC校驗(yàn)碼結(jié)構(gòu)Fig.1 CRC check code structure

其中m（x）為（k-1）次信息多項(xiàng)式，它的 k個(gè)系數(shù)對(duì)應(yīng) k位信息，r（x）為（n-k-1）次多項(xiàng)式，其 n-k個(gè)系數(shù)對(duì)應(yīng)n-k個(gè)校驗(yàn)位。整個(gè)n位幀為一個(gè)信息碼字，習(xí)慣上僅把n-k部分稱為CRC碼。

對(duì)于系統(tǒng)，其發(fā)送端發(fā)送信息為：

式中 r（x）等于 xn-km（x）除以生成多項(xiàng)式 G（x）的余式。若接收端接收碼R（x）等于發(fā)送碼C（x），即：

式中Q（x）為商式。此時(shí)，接收碼應(yīng)能被生成多項(xiàng)式整除。反之，如果不能整除，則傳輸中出現(xiàn)誤碼。根據(jù)此原理，以CRC生成多項(xiàng)式的階數(shù)為16位為例，詳細(xì)按字節(jié)計(jì)算CRC代數(shù)過程。

16位CRC碼產(chǎn)生的規(guī)則是：先將要發(fā)送的二進(jìn)制序列左移16位（乘以216）后，再除以一個(gè)多項(xiàng)式，最后得到的余數(shù)即是CRC碼［5］，如式（3）所示。

式中 B（x）表示n位二進(jìn)制序列。

對(duì)一個(gè)二進(jìn)制序列按字節(jié)表示為：

式（4）中Bn（x）為一個(gè)字節(jié)。按照CRC碼產(chǎn)生規(guī)則求此二進(jìn)制序列的CRC碼，如式（5）所示。

將式（6）帶入式（5），得：

其中 rnH8（x）28是 rn（x）的高 8位，rnL8（x）是 rn（x）的低8位。將式（8）帶入式（7），整理得：

根據(jù)CRC定義，顯然16位二進(jìn)制余數(shù)r0（x）即為CRC碼。式（10）是編程計(jì)算CRC的關(guān)鍵，它說明本字節(jié)后的CRC等于上一字節(jié)余式CRC的低8位左移8位后，再加上上一字節(jié)右移8位和本字節(jié)之和后求得的CRC碼［6］。如果把8位二進(jìn)制序列數(shù)的CRC碼全部計(jì)算出來，放在一個(gè)表里，采用查表法，可大大提高計(jì)算速度。

2 硬件電路設(shè)計(jì)

為提高RS-485數(shù)據(jù)傳輸?shù)臏?zhǔn)確性和可靠性，數(shù)據(jù)的發(fā)送端和接收端都采用CRC校驗(yàn)，通過比較接收數(shù)據(jù)幀的CRC校驗(yàn)碼和查表法產(chǎn)生的CRC碼是否一致來判斷數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，其實(shí)硬件實(shí)現(xiàn)原理框圖如圖2所示。

圖2 CRC硬件實(shí)現(xiàn)原理圖框圖Fig.2 CRC hardware implementation schematic diagram

根據(jù)CRC校驗(yàn)原理，可通過以下步驟實(shí)現(xiàn)查表法的設(shè)計(jì)：

（1）初始化寄存器；

（2）寄存器左移1字節(jié)，尾字節(jié)補(bǔ)值為0；

（3）用移出的字節(jié)查余式表值；

（4）寄存器值與余式表值作異或運(yùn)算，即寄存器值等于寄存器值異或余式表值；

（5）信息字節(jié)未結(jié)束，則重復(fù)執(zhí)行（2）、（3）、（4）步驟，否則執(zhí)行步驟（6）；

（6）寄存器值即為 CRC校驗(yàn)值［7］。

進(jìn)行查表法校驗(yàn)時(shí)，應(yīng)事先計(jì)算所有校驗(yàn)碼，并將其制作為一表格，將所有的信息組對(duì)應(yīng)的校驗(yàn)元按次序排序起來，本設(shè)計(jì)中采用了FPGA生成的單端RAM來存放CRC校驗(yàn)碼。具體以CRC-16CCITT校驗(yàn)為例，實(shí)現(xiàn)流程圖如圖3所示。

圖3 余式表實(shí)現(xiàn)CRC流程圖Fig.3 Remainder table implementation flow chart of CRC

由圖3可看到，讀出的FIFO數(shù)據(jù)中必須在其尾部補(bǔ)加w/8（w為CRC位寬度）個(gè)字節(jié)，添加的w/8個(gè)字節(jié)必須向其他字節(jié)一樣從右邊移入寄存器，但其對(duì)寄存器并沒有任何影響，這是因?yàn)槿魏沃蹬c0異或都不會(huì)改變目標(biāo)值，這樣，w/8個(gè)0字節(jié)的唯一作用是驅(qū)動(dòng)數(shù)據(jù)字節(jié)的循環(huán)，使得所有應(yīng)處理的數(shù)據(jù)全部通過寄存器。這對(duì)于一個(gè)很在意運(yùn)行時(shí)間的環(huán)境可能是一個(gè)小問題，如果這段數(shù)據(jù)還要被別的代碼使用，可能存在一定的隱患。為避免在附加尾比特的信息后添加0的w/8個(gè)字節(jié)，將其優(yōu)化設(shè)計(jì)，使查表法更加簡潔方便，易于操作，如圖4所示。

圖4 改進(jìn)的余式表實(shí)現(xiàn)CRC流程圖Fig.4 Improved type table implementation flow chart of CRC

上述算法已經(jīng)很優(yōu)化了，但使用異步收發(fā)控制器時(shí)，習(xí)慣在每字節(jié)最高位先發(fā)最低位（bit 0）后發(fā)最高位（bit 7），但發(fā)送的字節(jié)順序是不變的［8］。在進(jìn)行CRC校驗(yàn)就要將字節(jié)數(shù)據(jù)反相，這樣校驗(yàn)顯然加大了計(jì)算量和邏輯資源，但采用余式表反射算法來計(jì)算，則可以減少運(yùn)算量，提高運(yùn)算速度，反射算法如圖5所示。

圖5 反射余式表實(shí)現(xiàn)CRC流程圖Fig.5 Flow chart of reflection complementary table to achieve CRC

反射即一個(gè)值（或寄存器值），如果它的所有比特均以其中心交換位置，則交換后得到的值稱為反射值，比如，0111-0101-1010-1101的反射值為1011-0101-1010-1110。圖5中，寄存器的初始化值是反射值，因?yàn)槠渌鼦l目值已被反射了，這樣在執(zhí)行到最后，寄存器保存的值為CRC的反射值。

3 內(nèi)部邏輯設(shè)計(jì)

基于改進(jìn)的余式表和反射余式表實(shí)現(xiàn)CRC校驗(yàn)，通信時(shí)在發(fā)送端加上CRC校驗(yàn)碼后按規(guī)定的幀格式組幀［9］，而接收模塊將接收的數(shù)據(jù)幀緩存于FIFO中，CRC控制模塊從FIFO中讀出數(shù)據(jù)幀，并取數(shù)據(jù)的高8位與寄存器（初始化為0x0000）的高字節(jié)（或低字節(jié)）相異或，用異或值去查余式表索引值，并將索引值與寄存器值相異或，再將其異或值存于寄存器中。重復(fù)以上操作，直到一幀數(shù)據(jù)全部結(jié)束后比較發(fā)送的CRC值與計(jì)算的CRC值是否相等，若相等，則存儲(chǔ)于FLASH中；不相等，則將此幀數(shù)據(jù)刪除，上位機(jī)顯示報(bào)表提示出錯(cuò)幀的幀計(jì)數(shù)的位置，直到發(fā)送的所有數(shù)據(jù)都存儲(chǔ)完后結(jié)束。數(shù)據(jù)發(fā)送端和接收端的部分設(shè)計(jì)原理圖如圖6和圖7所示。

圖6 發(fā)送端FPGA原理圖Fig.6 Principle diagram of the sender FPGA

圖7 接收端FPGA部分原理圖Fig.7 Principle diagram of the receiver part FPGA

發(fā)送端中signal模塊主要用于數(shù)據(jù)幀的發(fā)送，包括一路LVDS數(shù)據(jù)、一路同步RS-422數(shù)據(jù)和一路異步RS-485數(shù)據(jù)；接收端recv_data用于接收數(shù)據(jù)幀，其中LVDS數(shù)據(jù)直接緩沖于FIFO中，而RS-422和RS-485數(shù)據(jù)經(jīng)過pack打包模塊將正確的數(shù)據(jù)打包緩沖于FIFO中進(jìn)行下一級(jí)相應(yīng)的操作；而CRC_RAM則是通過Xilinx FPGA中的COREGENETATOR生成單口RAM來構(gòu)造余式表，將余式表值導(dǎo)入其中，如圖8所示為部分CRC-16余式表值，其中圖8（b）為反射余式表值。

本設(shè)計(jì)采用某公司Spartan-3系列XC3S400 FPGA作為主控制器，使用 36.864 MHz晶振，通過VHDL語言，為高效簡潔實(shí)現(xiàn)CRC查表表法的設(shè)計(jì)，采用狀態(tài)機(jī)分別對(duì)改進(jìn)前后的余式表進(jìn)行編程，其部分源程序代碼［10］，如表1所示。

圖8 RAM中的CRC余式表值Fig.8 CRC residual table value in RAM

表1 實(shí)現(xiàn)CRC-16 CCITT校驗(yàn)部分VHDL程序Tab.1 Implementation of CRC-16 CCITT check part VHDL program

通過上表可知，對(duì)一個(gè)字節(jié)的數(shù)據(jù)進(jìn)行CRC-16 CCITT校驗(yàn)時(shí)，改進(jìn)后的余式表法或反射余式表法需要9個(gè)時(shí)鐘周期，約為0.22μs，經(jīng)比較，約為逐位運(yùn)算一字節(jié)所需時(shí)間的1/5。因?yàn)槠洳桓郊佣嘤?個(gè)字節(jié)值，在處理一字節(jié)數(shù)據(jù)時(shí)比沒有改進(jìn)前少用18個(gè)時(shí)鐘周期，可見改進(jìn)后的查表法運(yùn)算量少，速度快。

4 仿真及實(shí)踐驗(yàn)證

利用Xilinx ISE 13.1對(duì)計(jì)算CRC-16CCITT校驗(yàn)碼模塊進(jìn)行仿真，用 VHDL語言建立 VHDL Test Bench文件對(duì)代碼進(jìn)行測(cè)試，測(cè)試文件輸入十六進(jìn)制數(shù)00到1F的反射值，其仿真結(jié)果如圖9所示。

圖9 CRC-16 CCITT校驗(yàn)查表法實(shí)現(xiàn)仿真Fig.9 CRC-16 CCITT check look-up table method to realize the simulation

圖9中f_din［7：0］為輸入原始數(shù)據(jù)，doutb2［7：0］為從FIFO讀出來的輸入數(shù)據(jù)，為十六進(jìn)制的00到1F的反射值，即輸入低位在前，高位在后。crc_reg［15：0］存儲(chǔ)CRC校驗(yàn)值，當(dāng)輸入最后一個(gè)數(shù)1F（反射值為F8）之前，crc_reg為0x8480，其低字節(jié)與f_din數(shù)據(jù)F8異或得0x78，即為查找表的地址ram_addr，其內(nèi)容值為FFCF；此時(shí)crc_reg右移一字節(jié)為0x0084，與FFCF異或得FF4B，其反射值即為D2FF，顯然與CRC值相等，從而證明了數(shù)據(jù)傳輸?shù)恼_性。實(shí)際應(yīng)用中，為驗(yàn)證其正確性，在發(fā)送端發(fā)送的數(shù)據(jù)中添加CRC錯(cuò)誤的幀，采集接收數(shù)據(jù)，并經(jīng)過上位機(jī)軟件分析處理，得到的部分?jǐn)?shù)據(jù)如圖10所示。

圖10 CRC-16 CCITT校驗(yàn)查表法實(shí)現(xiàn)實(shí)際接收Fig.10 CRC-16 CCITT check look-up table method to realize the actual received

從圖中可知，幀結(jié)構(gòu)中出現(xiàn)幀計(jì)數(shù)不連續(xù)的情況，丟失幀計(jì)數(shù)為00 00 01 F6的一包幀，其實(shí)際原因是發(fā)送時(shí)將此幀的CRC校驗(yàn)設(shè)置錯(cuò)誤，然后傳輸出去；當(dāng)接收端校驗(yàn)CRC時(shí)出錯(cuò)，故將其刪除并通過上位機(jī)報(bào)出幀計(jì)數(shù)出錯(cuò)位置。

5 結(jié)束語

本文基于CRC以字節(jié)校驗(yàn)的原理，詳細(xì)介紹了CRC查表法校驗(yàn)的硬件實(shí)現(xiàn)原理。在串行通信中，經(jīng)過實(shí)際驗(yàn)證，加入CRC校驗(yàn)碼，在數(shù)據(jù)存儲(chǔ)之前進(jìn)行判斷數(shù)據(jù)傳輸?shù)恼_性，大幅度降低了數(shù)據(jù)的誤碼率，避免錯(cuò)誤數(shù)據(jù)大量占用存儲(chǔ)資源，保證了通信的有效性和準(zhǔn)確性。