基于FPGA的16 bit CRC校驗查表法設計

季鵬輝，孟 丁，任勇峰*

(1.中北大學儀器科學與動態測試教育部重點實驗室;電子測試技術國家重點實驗室，太原030051;2.北京第二炮兵駐699廠軍事代表室，北京100076)

循環冗余校驗(CRC)是一種實現簡單、校驗能力很強、在串行通信中廣泛采用的校驗方式［1］，可提高數據傳輸的可靠性和準確性。由于FPGA速度快、效率高、靈活穩定、集成度高的特點，因此，FPGA廣泛應用于串行通信，來提高串行通信的速度和效率［2］。對于常規的CRC查表法校驗而言，通常需要事先生成校驗表，然后才能對其進行查詢，使查表法的實現復雜、繁瑣且不易操作。為了增加CRC查表法校驗的可行性和簡潔性，本文介紹了基于FPGA IP核實現CRC校驗的查表法設計和實現方法。

1 CRC校驗基本原理

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

(1)逐位運算法

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

(2)查表法

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

2 方案設計

某總線控制系統中，為了提高數據傳輸的準確性和可靠性，數據的接收和裝載都須使用CRC校驗，通過接收的數據幀CRC校驗碼和查表法產生的CRC校驗碼一致性來判斷數據傳輸的準確性，數據幀由數據區，CRC校驗碼，數據區長度組成。

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

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

圖1 CRC校驗硬件實現原理圖框圖

為此，根據查表法原理，通過如下的步驟實現查表法的16 bit CRC校驗。

(1)初始化寄存器;

(2)寄存器高八位與待傳輸的信息字節進行異或運算，得出一個指向余式表的索引;

(3)寄存器左移八位;

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

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

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

3 內部邏輯設計

根據某總線控制系統要求，系統在接收到RS-422轉義數據后，在FPGA中被解碼為原始數據，CRC校驗正確后數據被再轉義回傳給計算機。為此，FPGA內部邏輯可劃分為:

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

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

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

圖2 FPGA實現16 bit CRC校驗查表法設計原理圖

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

圖3 RAM中的CRC余式表值

16 bit CRC校驗查表法校驗流程如圖4所示。

圖4 16 bit CRC校驗查表法校驗流程圖

判斷串行通信是否正確，通過對數據區中的數據進行CRC查表法校驗得到的校驗碼與直接從數據幀中讀出的CRC碼進行對比，相等即數據通信正確，否則就錯誤。

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

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

表1 實現CRC-16校驗部分VHDL程序代碼

else rd_en＜ =＇0＇;addrd＜=addrd+1;w_state＜=wr0;end if;……end case;逐位運算法實現CRC-16的部分程序case w_state is……when wr0=＞rd_en＜ =＇1＇;w_state＜=wr1;when wr1=＞datard＜=cdin;--讀FIFO中數據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多項式異或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可知，對一個字節的數據進行CRC-16校驗，查表法需要7個時鐘周期，而逐位運算則需要40個時鐘周期(5×8 bit)，本設計采用了18.432 M的外接晶振，數據塊長度為134個字節，則這兩種方法所需的時間如表2所示，查表法運算量少，速度快的優點很明顯的體現出來。

表2 CRC-16校驗所需時鐘和時間

4 實驗驗證

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

圖5 16 bit CRC校驗查表法設計邏輯分析圖(1)

圖6 16 bit CRC校驗查表法設計邏輯分析圖(2)

其中，lenth為數據區長度，crc為數據幀CRC校驗碼，crc_reg為CRC寄存器，rd_en為讀FIFO使能信號，addrd為讀FIFO的地址，datard為從FIFO中讀出的數據。由圖4流程圖和圖5可知，先讀數據幀CRC校驗碼和長度，當rd_en上升沿到來時，FIFO中讀出的數據datard為0xFFD1和0x0086(低字節先發送，高字節后發送)，即 crc為0xFFD1，lenth為0x0086(十進制為134)，此時開始讀數據區數據，CRC寄存器初值為0xFFFF，初始化后變為0x0000，如圖5所示。

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

5 結束語

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

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

［2］葉懋，劉宇紅，劉橋.CRC碼的FPGA實現［J］.重慶工學院學報，2007，21(3):85-87.

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

［4］莫元勁，黃水永.并行CRC在FPGA上實現［J］.電子設計工程，2011，19(15):133-135.

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

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

［7］任勇峰，莊新敏.VHDL與硬件實現速成［M］.北京:國防工業出版社，2005.

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