季鵬輝，孟 丁，任勇峰*

(1.中北大學(xué)儀器科學(xué)與動(dòng)態(tài)測試教育部重點(diǎn)實(shí)驗(yàn)室;電子測試技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，太原030051;2.北京第二炮兵駐699廠軍事代表室，北京100076)

循環(huán)冗余校驗(yàn)(CRC)是一種實(shí)現(xiàn)簡單、校驗(yàn)?zāi)芰軓?qiáng)、在串行通信中廣泛采用的校驗(yàn)方式［1］，可提高數(shù)據(jù)傳輸?shù)目煽啃院蜏?zhǔn)確性。由于FPGA速度快、效率高、靈活穩(wěn)定、集成度高的特點(diǎn)，因此，F(xiàn)PGA廣泛應(yīng)用于串行通信，來提高串行通信的速度和效率［2］。對于常規(guī)的CRC查表法校驗(yàn)而言，通常需要事先生成校驗(yàn)表，然后才能對其進(jìn)行查詢，使查表法的實(shí)現(xiàn)復(fù)雜、繁瑣且不易操作。為了增加CRC查表法校驗(yàn)的可行性和簡潔性，本文介紹了基于FPGA IP核實(shí)現(xiàn)CRC校驗(yàn)的查表法設(shè)計(jì)和實(shí)現(xiàn)方法。

1 CRC校驗(yàn)基本原理

CRC校驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進(jìn)制序列，以一定規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的監(jiān)督碼r位，并附在信息后，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)，共(k+r)位，最后發(fā)送出去［3］。將待校驗(yàn)數(shù)據(jù)表示為一個(gè)n階的多項(xiàng)式P(x)，G(x)為 CRC多項(xiàng)式(對于 CRC-16而言，G(x)=x16+x15+x2+1)，則P(x)=Q(x)×G(x)+R(x)，式中R(x)和Q(x)分別是P(x)除以CRC多項(xiàng)式G(x)的余數(shù)和商，這個(gè)R(x)就是目標(biāo)CRC校驗(yàn)值。根據(jù)CRC校驗(yàn)基本原理，CRC校驗(yàn)可由逐位運(yùn)算或者查表法實(shí)現(xiàn)。

(1)逐位運(yùn)算法

根據(jù)CRC校驗(yàn)基本原理可知，CRC校驗(yàn)實(shí)際上是一個(gè)循環(huán)移位的模2運(yùn)算，對于CRC-16，通過設(shè)置一個(gè)17 bit的寄存器，反復(fù)移位和進(jìn)行CRC除法，寄存器中最終值去掉最高位就是所求CRC校驗(yàn)值。逐位運(yùn)算法在數(shù)據(jù)每移入一位時(shí)，就需重新對每一位進(jìn)行再次計(jì)算。因此，移位操作的次數(shù)等于總的數(shù)據(jù)位數(shù)減去16［4］。這種算法簡單，容易實(shí)現(xiàn)，但它一次只能處理1 bit數(shù)據(jù)，效率太低。如果發(fā)送的數(shù)據(jù)塊比較長，這種算法就不太合適了。

(2)查表法

為提高逐位運(yùn)算法的效率，查表法的CRC-16校驗(yàn)每次可以處理一個(gè)字節(jié)(8 bit)，根據(jù)異或運(yùn)算的交換律(A XOR B)XOR C=A XOR(B XOR C)，數(shù)據(jù)可以先與剛從寄存器移出的字節(jié)相異或，通過高8 bit的反復(fù)移位和CRC除法，得到CRC余式表的索引值，根據(jù)索引值進(jìn)行查表，再用表值異或寄存器，這樣得到的即為CRC校驗(yàn)碼，但其缺點(diǎn)是需要占用大量的邏輯資源。

2 方案設(shè)計(jì)

某總線控制系統(tǒng)中，為了提高數(shù)據(jù)傳輸?shù)臏?zhǔn)確性和可靠性，數(shù)據(jù)的接收和裝載都須使用CRC校驗(yàn)，通過接收的數(shù)據(jù)幀CRC校驗(yàn)碼和查表法產(chǎn)生的CRC校驗(yàn)碼一致性來判斷數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，數(shù)據(jù)幀由數(shù)據(jù)區(qū)，CRC校驗(yàn)碼，數(shù)據(jù)區(qū)長度組成。

某總線控制系統(tǒng)為高速數(shù)字電路，當(dāng)數(shù)據(jù)區(qū)數(shù)據(jù)較多時(shí)，使用逐位運(yùn)算法勢必會帶來速度和功耗的問題，從而造成信號傳遞過程中延遲。為解決這些問題，本設(shè)計(jì)采用了查表法，由于查表法基于字節(jié)(8 byte)操作，避免了耗時(shí)的位運(yùn)算，故運(yùn)算量少，速度快的優(yōu)點(diǎn)，大大優(yōu)化了系統(tǒng)的設(shè)計(jì)。查表法一般可由軟件或者硬件實(shí)現(xiàn)，本設(shè)計(jì)采用了硬件實(shí)現(xiàn)查表法的CRC校驗(yàn)，其原理圖框圖如圖1所示。

進(jìn)行查表法校驗(yàn)時(shí)，應(yīng)事先計(jì)算所有CRC校驗(yàn)碼，并將其制作為一表格，將所有的信息組對應(yīng)的校驗(yàn)元按次序排序起來［5］，考慮到計(jì)算CRC校驗(yàn)碼和制作表格的復(fù)雜性，本設(shè)計(jì)中采用了FPGA的IP核建立RAM來存放CRC的校驗(yàn)碼，從而無需事先生成校驗(yàn)表，使得程序代碼少，修改靈活，這樣只要識別讀入的余式表索引，就能用一條指令找到對應(yīng)的校驗(yàn)碼。

圖1 CRC校驗(yàn)硬件實(shí)現(xiàn)原理圖框圖

為此，根據(jù)查表法原理，通過如下的步驟實(shí)現(xiàn)查表法的16 bit CRC校驗(yàn)。

(1)初始化寄存器;

(2)寄存器高八位與待傳輸?shù)男畔⒆止?jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向余式表的索引;

(3)寄存器左移八位;

(4)余式表索引表值與寄存器做異或運(yùn)算;

(5)如果數(shù)據(jù)未接收完，則重復(fù)(2)(3)(4)步，否則執(zhí)行第(6)步;

(6)寄存器的內(nèi)容即為CRC碼。

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

根據(jù)某總線控制系統(tǒng)要求，系統(tǒng)在接收到RS-422轉(zhuǎn)義數(shù)據(jù)后，在FPGA中被解碼為原始數(shù)據(jù)，CRC校驗(yàn)正確后數(shù)據(jù)被再轉(zhuǎn)義回傳給計(jì)算機(jī)。為此，F(xiàn)PGA內(nèi)部邏輯可劃分為:

(1)422接收模塊:主要用于數(shù)據(jù)幀的接收，并將接收的數(shù)據(jù)幀存入下一級FIFO中;

(2)CRC控制模塊:主要用于CRC校驗(yàn)的實(shí)現(xiàn)，將FIFO中數(shù)據(jù)讀出，通過對存有CRC校驗(yàn)碼余式表的查詢，進(jìn)行16 bit CRC的校驗(yàn)。

如圖2 Xilinx原理圖所示，re422為422接收模塊，ctr_crc為CRC控制模塊，RAM4K為存儲16 bit CRC校驗(yàn)表全部校驗(yàn)碼的RAM。

圖2 FPGA實(shí)現(xiàn)16 bit CRC校驗(yàn)查表法設(shè)計(jì)原理圖

為了構(gòu)造16 bit CRC校驗(yàn)余式表，本設(shè)計(jì)通過Xilinx中CORE Generator生成IP核和設(shè)置IP核的參數(shù)來建立Block RAM，即圖2中RAM4K模塊。通過Uedit創(chuàng)建*.coe文件，將16 bit CRC校驗(yàn)余式表中所有CRC碼寫入*.coe文件，并將其導(dǎo)入RAM中，實(shí)現(xiàn)16 bit CRC校驗(yàn)余式表的建立，以此代替相關(guān)程序直接生成查表法所需的CRC校驗(yàn)碼，使本設(shè)計(jì)代碼減少，修改靈活，并且避免了重復(fù)設(shè)計(jì)，提高了工作效率。其中，RAM的地址為CRC索引值。圖3即為RAM中的部分CRC余式表值。

圖3 RAM中的CRC余式表值

16 bit CRC校驗(yàn)查表法校驗(yàn)流程如圖4所示。

圖4 16 bit CRC校驗(yàn)查表法校驗(yàn)流程圖

判斷串行通信是否正確，通過對數(shù)據(jù)區(qū)中的數(shù)據(jù)進(jìn)行CRC查表法校驗(yàn)得到的校驗(yàn)碼與直接從數(shù)據(jù)幀中讀出的CRC碼進(jìn)行對比，相等即數(shù)據(jù)通信正確，否則就錯(cuò)誤。

RS-422接收模塊將接收的數(shù)據(jù)幀存入FIFO，CRC控制模塊從FIFO中讀出數(shù)據(jù)，從FIFO中讀出一個(gè)數(shù)據(jù)時(shí)，初始化CRC寄存器(CRC初始值為0xFFFF)，CRC寄存器高8位與數(shù)據(jù)位異或，其值即為余式表索引值也就是RAM地址，CRC寄存器左移8位，與RAM中讀出的余式表值異或，存入到CRC寄存器中。重復(fù)以上操作，直到讀完FIFO中所有數(shù)據(jù)，此時(shí)，CRC寄存器中值即為數(shù)據(jù)幀的CRC校驗(yàn)碼。若和讀出的CRC校驗(yàn)碼相等，則校驗(yàn)正確;反之，則繼續(xù)等待正確的數(shù)據(jù)幀到來。

本設(shè)計(jì)采用 Xilinx公司 Spartan-3AN系列XC3S200AN FPGA芯片作為主控制器，使用18.432 M晶振，通過VHDL語言對FPGA編程，為靈活、高效的實(shí)現(xiàn)CRC校驗(yàn)的查表法設(shè)計(jì)，采用了狀態(tài)機(jī)，對于高速數(shù)字電路來說，狀態(tài)機(jī)是一種重要的時(shí)序邏輯電路，用其來描述數(shù)字電路的控制單元和運(yùn)算單元。本論文分別給出了查表法和通過逐位運(yùn)算法實(shí)現(xiàn)CRC-16校驗(yàn)的部分VHDL程序代碼［6-7］，如表1所示。

表1 實(shí)現(xiàn)CRC-16校驗(yàn)部分VHDL程序代碼

else rd_en＜ =＇0＇;addrd＜=addrd+1;w_state＜=wr0;end if;……end case;逐位運(yùn)算法實(shí)現(xiàn)CRC-16的部分程序case w_state is……when wr0=＞rd_en＜ =＇1＇;w_state＜=wr1;when wr1=＞datard＜=cdin;--讀FIFO中數(shù)據(jù)cnt＜=cnt+1;w_state＜=wr2;when wr2=＞crc_reg＜=datard＆ "00000000";w_state＜=wr3;when wr3=＞crc_reg＜=crc_reg(15 downto 0)＆ ＇0＇;--寄存器左移1位cnt1＜=cnt1+1;w_state＜=wr4;when wr4=＞crc_reg＜=crc_reg xor X"8005";--寄存器與CRC多項(xiàng)式異或w_state＜=wr5;when wr5=＞if cnt＜lenth then if cnt1=8 then rd_en＜ =＇0＇;addrd＜=addrd+1;cnt1＜=(other=＞＇0＇);w_state＜=wr0;else w_state＜=wr3;end if;else w_state＜=wr6;end if;……end case;

通過表1可知，對一個(gè)字節(jié)的數(shù)據(jù)進(jìn)行CRC-16校驗(yàn)，查表法需要7個(gè)時(shí)鐘周期，而逐位運(yùn)算則需要40個(gè)時(shí)鐘周期(5×8 bit)，本設(shè)計(jì)采用了18.432 M的外接晶振，數(shù)據(jù)塊長度為134個(gè)字節(jié)，則這兩種方法所需的時(shí)間如表2所示，查表法運(yùn)算量少，速度快的優(yōu)點(diǎn)很明顯的體現(xiàn)出來。

表2 CRC-16校驗(yàn)所需時(shí)鐘和時(shí)間

4 實(shí)驗(yàn)驗(yàn)證

本設(shè)計(jì)使用Xilinx ISE 10.1進(jìn)行編譯和綜合。為了驗(yàn)證本設(shè)計(jì)的正確性，采用了ChipScope Pro Analyzer虛擬邏輯分析儀，對其進(jìn)行在線邏輯分析，通過設(shè)定觸發(fā)條件將信號實(shí)時(shí)的保存于Block RAM中，然后通過JTAG接口傳送到計(jì)算機(jī)，最后在用戶計(jì)算機(jī)屏幕上顯示出波形［8］。如圖5、圖6中16 bit CRC校驗(yàn)查表法設(shè)計(jì)邏輯分析圖所示。

圖5 16 bit CRC校驗(yàn)查表法設(shè)計(jì)邏輯分析圖(1)

圖6 16 bit CRC校驗(yàn)查表法設(shè)計(jì)邏輯分析圖(2)

其中，lenth為數(shù)據(jù)區(qū)長度，crc為數(shù)據(jù)幀CRC校驗(yàn)碼，crc_reg為CRC寄存器，rd_en為讀FIFO使能信號，addrd為讀FIFO的地址，datard為從FIFO中讀出的數(shù)據(jù)。由圖4流程圖和圖5可知，先讀數(shù)據(jù)幀CRC校驗(yàn)碼和長度，當(dāng)rd_en上升沿到來時(shí)，F(xiàn)IFO中讀出的數(shù)據(jù)datard為0xFFD1和0x0086(低字節(jié)先發(fā)送，高字節(jié)后發(fā)送)，即 crc為0xFFD1，lenth為0x0086(十進(jìn)制為134)，此時(shí)開始讀數(shù)據(jù)區(qū)數(shù)據(jù)，CRC寄存器初值為0xFFFF，初始化后變?yōu)?x0000，如圖5所示。

在從FIFO中讀出最后一個(gè)數(shù)據(jù)0x5A之前，CRC寄存器crc_reg為0xA4F1，左移一個(gè)字節(jié)crc_reg變?yōu)?xF100，其高8 bit 0xA4與0x5A異或，得到余式表索引值254，其余式表值為0x0ED1(如圖3所示)，則 CRC=余式表值 XOR crc_reg=0x0ED1 XOR 0xF100=0xFFD1，很顯然，crc和crc_reg相等，如圖6所示。證明了通信過程中的CRC校驗(yàn)的正確性，同時(shí)也驗(yàn)證了本設(shè)計(jì)的正確性和可行性。

5 結(jié)束語

采用查表法實(shí)現(xiàn)CRC校驗(yàn)，使實(shí)際中的應(yīng)用變的簡單易行。FPGA的使用讓設(shè)計(jì)變的簡單，尤其是IP核的使用，用RAM構(gòu)造的16 bit CRC校驗(yàn)余式表使源程序更加簡潔明了。ChipScope Pro Analyzer的使用縮短了設(shè)計(jì)時(shí)間，也方便了本論文設(shè)計(jì)的驗(yàn)證。在某總線控制器實(shí)際應(yīng)用中，也證明了本設(shè)計(jì)的可行性，并表現(xiàn)出良好的性能。

［1］孫志雄，謝海霞.基于FPGA的CRC編解碼器實(shí)現(xiàn)［J］.電子器件，2012，35(6):657-660.

［2］葉懋，劉宇紅，劉橋.CRC碼的FPGA實(shí)現(xiàn)［J］.重慶工學(xué)院學(xué)報(bào)，2007，21(3):85-87.

［3］劉新寧，王超，胡晨，等.一種快速CRC算法的硬件實(shí)現(xiàn)方法［J］.電子器件，2003，26(1):88-91.

［4］莫元?jiǎng)牛S水永.并行CRC在FPGA上實(shí)現(xiàn)［J］.電子設(shè)計(jì)工程，2011，19(15):133-135.

［5］劉會杰，張乃通.基于查表法的快速CRC算法設(shè)計(jì)［J］.通信技術(shù)，2002，124(4):8-10.

［6］常天海，胡鑒.基于FPGA的CRC并行算法研究與實(shí)現(xiàn)［J］.微處理器，2010，4(2):45-48.

［7］任勇峰，莊新敏.VHDL與硬件實(shí)現(xiàn)速成［M］.北京:國防工業(yè)出版社，2005.

［8］王杰，王誠，謝龍漢.Xilinx FPGA/CPLD設(shè)計(jì)手冊［M］.北京:人民郵電出版社，2011.