基于FPGA的CRC查表法設計及優化

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

（1.中北大學電子測試技術國家重點實驗室，太原030051；2.中北大學儀器科學與動態測試教育部重點實驗室，太原030051）

0 引 言

在數據存儲和數據通信網絡等領域中，由于傳輸的不確定性及干擾等情況，使得通信出現異常，因此在串行通信中添加校驗是必不可少的［1］。而FPGA來做數字信號處理是完全的硬件化、并行化編程操作，具有靈活調節的優點［2］，故廣泛應用于串行通信中。在通信中，常規的CRC校驗是按比特計算的，雖然此方法能更清楚體現CRC算法的本質，但當發送的數據量很大時，因其一次只能處理一位數據，效率太低，且占用的邏輯資源較大，而查表法能夠按字節處理數據，避免了耗時的位運算［3］，提高了數據的運算量和運算速率，大大優化了系統的設計。

1 CRC校驗原理

循環冗余校驗碼（CRC）是一種系統的縮短循環碼，是由線性分組碼的分支而來，它只能檢查數據的錯誤，而不能糾正傳輸錯誤。在代數編碼理論中，將一個碼序列表示為一個多項式，碼序列中各碼元當作多項式的系數，而CRC碼的結構［4］如圖1所示。

圖1 CRC校驗碼結構Fig.1 CRC check code structure

其中m（x）為（k-1）次信息多項式，它的 k個系數對應 k位信息，r（x）為（n-k-1）次多項式，其 n-k個系數對應n-k個校驗位。整個n位幀為一個信息碼字，習慣上僅把n-k部分稱為CRC碼。

對于系統，其發送端發送信息為：

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

式中Q（x）為商式。此時，接收碼應能被生成多項式整除。反之，如果不能整除，則傳輸中出現誤碼。根據此原理，以CRC生成多項式的階數為16位為例，詳細按字節計算CRC代數過程。

16位CRC碼產生的規則是：先將要發送的二進制序列左移16位（乘以216）后，再除以一個多項式，最后得到的余數即是CRC碼［5］，如式（3）所示。

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

對一個二進制序列按字節表示為：

式（4）中Bn（x）為一個字節。按照CRC碼產生規則求此二進制序列的CRC碼，如式（5）所示。

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

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

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

2 硬件電路設計

為提高RS-485數據傳輸的準確性和可靠性，數據的發送端和接收端都采用CRC校驗，通過比較接收數據幀的CRC校驗碼和查表法產生的CRC碼是否一致來判斷數據傳輸的準確性，其實硬件實現原理框圖如圖2所示。

圖2 CRC硬件實現原理圖框圖Fig.2 CRC hardware implementation schematic diagram

根據CRC校驗原理，可通過以下步驟實現查表法的設計：

（1）初始化寄存器；

（2）寄存器左移1字節，尾字節補值為0；

（3）用移出的字節查余式表值；

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

（5）信息字節未結束，則重復執行（2）、（3）、（4）步驟，否則執行步驟（6）；

（6）寄存器值即為 CRC校驗值［7］。

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

圖3 余式表實現CRC流程圖Fig.3 Remainder table implementation flow chart of CRC

由圖3可看到，讀出的FIFO數據中必須在其尾部補加w/8（w為CRC位寬度）個字節，添加的w/8個字節必須向其他字節一樣從右邊移入寄存器，但其對寄存器并沒有任何影響，這是因為任何值與0異或都不會改變目標值，這樣，w/8個0字節的唯一作用是驅動數據字節的循環，使得所有應處理的數據全部通過寄存器。這對于一個很在意運行時間的環境可能是一個小問題，如果這段數據還要被別的代碼使用，可能存在一定的隱患。為避免在附加尾比特的信息后添加0的w/8個字節，將其優化設計，使查表法更加簡潔方便，易于操作，如圖4所示。

圖4 改進的余式表實現CRC流程圖Fig.4 Improved type table implementation flow chart of CRC

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

圖5 反射余式表實現CRC流程圖Fig.5 Flow chart of reflection complementary table to achieve CRC

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

3 內部邏輯設計

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

圖6 發送端FPGA原理圖Fig.6 Principle diagram of the sender FPGA

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

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

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

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

表1 實現CRC-16 CCITT校驗部分VHDL程序Tab.1 Implementation of CRC-16 CCITT check part VHDL program

通過上表可知，對一個字節的數據進行CRC-16 CCITT校驗時，改進后的余式表法或反射余式表法需要9個時鐘周期，約為0.22μs，經比較，約為逐位運算一字節所需時間的1/5。因為其不附加多余2個字節值，在處理一字節數據時比沒有改進前少用18個時鐘周期，可見改進后的查表法運算量少，速度快。

4 仿真及實踐驗證

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

圖9 CRC-16 CCITT校驗查表法實現仿真Fig.9 CRC-16 CCITT check look-up table method to realize the simulation

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

圖10 CRC-16 CCITT校驗查表法實現實際接收Fig.10 CRC-16 CCITT check look-up table method to realize the actual received

從圖中可知，幀結構中出現幀計數不連續的情況，丟失幀計數為00 00 01 F6的一包幀，其實際原因是發送時將此幀的CRC校驗設置錯誤，然后傳輸出去；當接收端校驗CRC時出錯，故將其刪除并通過上位機報出幀計數出錯位置。

5 結束語

本文基于CRC以字節校驗的原理，詳細介紹了CRC查表法校驗的硬件實現原理。在串行通信中，經過實際驗證，加入CRC校驗碼，在數據存儲之前進行判斷數據傳輸的正確性，大幅度降低了數據的誤碼率，避免錯誤數據大量占用存儲資源，保證了通信的有效性和準確性。