一種基于矩陣的并行CRC校驗算法

趙坤鵬，吳龍勝，馬徐瀚，陳慶宇

（西安微電子技術研究所 陜西 西安710054）

一種基于矩陣的并行CRC校驗算法

趙坤鵬，吳龍勝，馬徐瀚，陳慶宇

（西安微電子技術研究所 陜西 西安710054）

針對高速網絡通信中高位寬并行數據的實時校驗需求，提出了一種可單周期實現的、面向128位并行數據的循環冗余校驗算法（Cyclic Redundancy Check，CRC）。該算法首先根據CRC串行編碼原理得到8位并行數據的CRC校驗矩陣，之后對矩陣進行迭代簡化，得到32位并行數據的參數矩陣，此參數矩陣作為該CRC算法的核心實現了對數據進行預處理。最后對該算法進行了硬件實現，仿真及綜合結果表明，該算法可在單周期內完成對128位并行數據的CRC編碼和解碼校驗，時鐘頻率提高1.8倍，而硬件開銷僅增加5.15%。

128位并行數據；單周期；CRC算法；硬件實現；頻率提高

為了保證通信系統中數據傳輸的可靠性，基于編解碼的數據校驗技術廣泛應用，同時日漸提高的網絡通信速率，迫切需要支持寬位并行數據的實時校驗電路。

循環冗余校驗碼CRC作為編碼校驗中重要的編碼方式，由于其易于硬件實現，具有良好的檢錯性能，在網絡數據傳輸中得到廣泛應用。CRC編碼實現方式多樣，有串行編碼方式、查表法和公式法（也稱推導法）。其中，串行編碼只能處理串行數據，無法實現寬位并行數據校驗[1]。查表法需要存儲模塊來存儲表項，硬件消耗大，難以實現高位寬并行數據校驗[2]。公式法在以太網和PCIe等高速并行通信中應用廣泛，但其迭代推導方式對于高位寬數據（大于16）較為復雜。針對上述實現方法中存在的問題，文獻[5]提出了基于級聯結構的CRC校驗方法，該方法電路結構清晰，可以實現對并行64位數據的校驗，但隨著并行數據位寬的提高，相應的鏈路延時會線性增長，無法實現高位寬（如128位）的實時校驗。文獻[6]提出了一種多通道并行CRC計算方法，其算法復雜，相應實現方式復雜，需要高性能處理器，硬件消耗較大，不適合應用于實際的專用集成電路中。文中提出了一種面向128位并行數據的CRC校驗算法，該算法采用校驗矩陣對128位數據進行了預處理，大大提高了寬位并行數據的校驗效率。

文中首先介紹了當前CRC編碼的研究現狀，然后提出了一種針對寬位并行數據的CRC校驗算法，該算法可以實現128位數據的單周期校驗，并在此基礎上對本文算法進行了硬件實現；之后，對硬件電路的功能和開銷進行了仿真驗證、綜合分析；最后，對文中進行了總結。

1 CRC并行數據校驗算法

傳統的CRC-32校驗是通過線性反饋移位寄存器（LFSR，Linear Feedback Shift Register）來實現的，如圖1所示。

圖1 LFSR結構框圖

由此可知當前CRC值與當前數據輸入和前一級CRC值的關系為

由式（1）的迭代關系可以遞次推導出8位并行數據輸入的當前CRC值與當前數據輸入和8位數據輸入之前的CRC值之間的關系，得到當前CRC值中每一位的值為：

將式（2）中的異或由數學中的加號替代，則式（2）可表示為如下形式

由式（3）可以得到輸入兩次8位數據，即輸入16位并行數據后的當前CRC值C2，如式（4），其中D2為第2次輸入的8位數據。

同理，繼續迭代兩次后得到輸入4次8位數據，即輸入32位并行數據后的CRC值

式（5）中的C0為前一級的CRC值，D1、D2、D3、D4分別為第一、二、三、四次輸入的8位數據，為輸入32位并行數據后的CRC值，C2C32×32*C2C32×32*

C2C32×32*C2C32×32為C0的參數矩陣，D2C8×32*C2C32×32* C2C32×32*C2C32×32為 D1的參數矩陣，D2C8×32*C2C32×32* C2C32×32為D2的參數矩陣，D2C8×32*C2C32×32為D3的參數矩陣，D2C8×32為D4的參數矩陣。

令C0的參數矩陣為，D1的參數矩陣為，D2的參數矩陣為，D3的參數矩陣為，D4的參數矩陣為，則

得到當前CRC值與前一級CRC值和當前32位并行數據的關系:

式（8）中D32=[D1，D2，D3，D4]，將式（8）按照式（3）、式（4）、式（5）的方法進行4次迭代計算，得到CRC值與前一級CRC值和當前128位并行數據的關系式為式（9）。

其中，C128為128位并行數據輸入后的CRC值，為C0的參數矩陣，D128為128位并行輸入數據為128位并行數據的參數矩陣。

2 算法的硬件實現

文中根據第二節的推導公式，基于式（9）提出了一種可以對數據進行預處理的CRC編解碼電路[18]。

由式（9）可知，在進行并行128位數據CRC校驗時，可以對數據直接進行處理，同時，根據矩陣C2C12832×32對前一級CRC值進行處理，提高了編碼效率，大大減少了鏈路延遲。

如圖2所示，文中提出了一種面向128位并行數據的CRC編解碼電路。圖中的前一級CRC編碼模塊是以矩陣 D2C128128×32為基本原理轉化生成的電路，可以對上一級的CRC值進行編碼處理。數據預處理編碼模塊是以矩陣D2C128128×32為基本原理轉化生成的電路模塊，對128位并行數據進行預處理編碼，并通過邏輯優化實現鏈路延遲的減少。異或模塊對來自前一級CRC編碼模塊和數據預處理編碼模塊的數據進行按位異或處理。最終CRC值由反相器輸出，校驗結果與魔數進行比較，由比較器輸出結果。

圖2 128位并行數據的CRC編解碼電路

3 實驗驗證及分析

為驗證文中提出的電路結構的有效性和合理性，使用Modelsim搭建驗證環境進行仿真、使用synplify綜合工具對電路進行綜合。為了進行對比，采用了基于synopsys公司的8位并行數據校驗電路對同一組數據進行校驗，以對比校驗編碼的正確性。

仿真結果如圖3、圖4所示。其中圖3為采用文中提出的編碼校驗電路的功能時序圖；圖4為基于synopsys公司的8位并行數據校驗電路的功能時序圖，其輸入與圖3的輸入相同，分為26個時鐘周期，每個時鐘并行輸入8位數據。如圖3、圖4所示，兩種電路所的到的結果一致。

圖3 128位并行數據的CRC電路功能時序圖

圖4 synopsys公司8位并行數據的CRC電路功能時序圖

選用Xilinx公司Virtex 5系列的X65VLX330T芯片對本文設計的并行128數據的CRC-32校驗電路進行邏輯綜合，為了進行比較，針對文獻[5]中所提出的基于級聯結構的電路進行了布局布線，綜合結果見表1。

表1 128位并行數據CRC-32編解碼電路綜合結果

從表1中可以看出，對于128并行數據的CRC-32編碼，文中所述的方法相對于級聯結構，由于對組合邏輯鏈路進行了算法上的優化和結構上的改進，縮短了最長延遲路徑，從而在面積僅增加5.15%的情況下，將工作的時鐘頻率提高了1.8倍[19]。

4 結束語

隨著網絡通信速率的日漸提高，迫切需要支持寬位并行數據的實時校驗電路，文中提出了一種可單周期實現的、面向128位并行數據的循環冗余校驗算法。該算法通過對邏輯電路進行優化處理，提高了工作時鐘頻率，可以實現對128位并行數據的CRC快速編碼和解碼校驗。并且，文中在迭代過程中所涉及到的參數矩陣，在工程應用中均有重要實用價值，可以應用于以太網、PCIe等高速通信網絡。

[1]劉新寧.一種快速CRC算法的硬件實現方法[J].電子器件，2003，26（1）:88-91.

[2]Amila，Akagic， Hideharu，et al.A Study of Adaptable Co-processors for Cyclic Redundancy Check on an FPGA[D].Japan:Hiyoshi，2012.

[3]王月琴，楊恒新.CRC碼串并結合算法的研究與實現[J].計算機技術與發展，2014，24（6）:103-106.

[4]Kiyana，Bahadori.Multiclass classification of error correcting output[J].Australian Journal of Basic and Applied Sciences，2015，5（9）:538-543.

[5]袁征，冶曉隆，郭超.基于FPGA的10G以太網并行CRC設計 [J].計算機工程與設計，2014，35（5）: 1510-1515.

[6]徐展琦，裴昌幸，董淮南.一種通用多通道并行CRC計算及其實現[J].南京郵電大學學報，2008，28（2）:53-57.

[7]Li C C，Lei Z.CRC codes for short control frames in IEEE 802.11ah[C]//Vehicular Technology Conference（VTC Fall），2014 IEEE 80th.IEEE，2014: 1-5.

[8]Lou C Y.An analytical packet error rate prediction for punctured convolutional codes and an application to CRC code design[J].Dissertations&Theses-Gradworks，2015.

[9]Bartholomew E O，Oscar E A.Error detection in a multi-user request system using enhanced CRC algorithm[J].International Journal of Information Technology&Computer Science，2014，6（9）:14-23.

[10]Deng H，Wang C.Verifi cation of CRC error detecting capability based on monte-carlo simulation[J].Railway Signalling&Communication Engineering，2014.

[11]劉巖俊，閆海霞．HDLC通訊協議中CRC的應用[J]．電子測量技術，2010（3）：21-23．

[12]彭偉．嵌入式系統CRC循環冗余校驗算法設計研究[J]．南京信息工程大學學報：自然科學版，2012（3）：258-265．

[13]呂曉敏．嵌套循環冗余碼（CRC）的優化與檢驗[D]．杭州：浙江大學，2012．

[14]莫元勁．并行CRC在FPGA上的實現[J]．電子設計工程，2011（15）：133-135．

[15]杜瑞，張偉功，鄧哲，等．新型總線中并行CRC算法的設計與實現[J]．計算機工程與設計，2013（1）：131-135．

[16]肖飛，余子寒，隋天宇，等．LTE中CRC算法的研究與實現[J]．電子測量技術，2014（7）：36-39．

[17]Wu F，Jia S，Meng Q，et al.Improved CRC calculation strategies for 64-bit serial rapidIO[J]. Ieice Transactions on Electronics，2013，E96.C（10）:1330-1338.

[18]朱黨杰，孫江輝，蔣學東.RS級聯CRC編碼在遙測系統中的應用[J].電子科技，2013（7）：40-42.

[19]郝永健,張團善,周文勝,等.動態紗線張力傳感器彈簧片的有限元模態分析[J].西安工程大學學報，2015（3）：358-361.

Parallel CRC verification algorithm based on matrix

ZHAO Kun-peng，WU Long-sheng，MA Xu-han，CHEN Qing-yu
（Xi'an Microelectronics Technology Institute，Xi'an 710054，China）

To target the real-time verification requirement of the parallel data in the high speed network communication，the CRC（Cyclic Redundancy Check）algorithm which can implement check of 128-bit parallel data in a single cycle is presented in this paper.Firstly，the CRC check matrix for 8-bit parallel data is extrapolated base on the principle of CRC serial encoding.Then，that check matrix is iteratively simplified to calculate the parameter matrix of 32-bit parallel data.The parameter matrix is regarded as the most significant part in the proposed algorithm and is used to pre-process data.Finally，the algorithm is implemented by hardware.The results of simulation and synthesis show that the encoding and decoding check of 128-bit parallel data can be finished in a single cycle based on the proposed algorithm and the clock frequency increases by 1.8 times with the hardware overheads only increasing 5.15%.

128-bit parallel data；single cycle；CRC algorithm；hardware implementation；frequency increase

TN492

：A

：1674－6236（2017）03-0085-04

2016-01-21稿件編號：201601193

趙坤鵬 （1989—），男，河北石家莊人，碩士研究生。研究方向：以太網ASIC設計。