基于FPGA的CRC32校驗(yàn)查找表算法的設(shè)計(jì)

時亞麗（中國電子科技集團(tuán)公司第三十八研究所，合肥　230088）

基于FPGA的CRC32校驗(yàn)查找表算法的設(shè)計(jì)

時亞麗
（中國電子科技集團(tuán)公司第三十八研究所，合肥230088）

循環(huán)冗余碼校驗(yàn)CRC廣泛應(yīng)用于數(shù)字通信和數(shù)據(jù)存儲的數(shù)據(jù)檢錯。CRC校驗(yàn)分為串行方式校驗(yàn)、并行方式校驗(yàn)。串行方式校驗(yàn)采用串行移位寄存器，每1個clk計(jì)算1bit，處理速度慢。并行方式采用查找表算法，處理速度快。本文介紹了CRC32校驗(yàn)算法的FPGA實(shí)現(xiàn)方法，并通過Modelsim仿真，驗(yàn)證了算法的可行性和正確性。

循環(huán)冗余校驗(yàn)碼；CRC32；FPGA

0　引言

循環(huán)冗余校驗(yàn)碼CRC是一種實(shí)現(xiàn)簡單、校驗(yàn)?zāi)芰?qiáng)、在串行通信領(lǐng)域廣泛采用的校驗(yàn)編碼［1］。CRC校驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端，對要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個校驗(yàn)用的監(jiān)督碼（即CRC碼）r位，附在信息后邊，構(gòu)成了一個新的二進(jìn)制碼序列數(shù)共（k+r）位，然后發(fā)送出去［2］。在接收端，則根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行校驗(yàn)，以確定傳送中是否出錯。

1　CRC32生成查找表和CRC32數(shù)據(jù)校驗(yàn)

CRC32校驗(yàn)查找表算法采用正規(guī)查詢表查詢，該查詢表是將“直接查詢表”的索引值和表值直接鏡像，正規(guī)查找表多項(xiàng)式POLY是0x04C11DB7。生成查找表的流程是首先對索引值0到0xFF數(shù)值鏡像。以索引值1為例，鏡像值為0x80，已對該8bit鏡像值0x80左移24位變成32位CRC32值。對該值一次左移1位，移出的值若為1，則對移后的CRC32值與POLY進(jìn)行異或操作得到新的CRC32值，否則不做運(yùn)算。進(jìn)行8次左移運(yùn)算，最后的CRC32值在做鏡像后的值即為索引值1的CRC32查找表值，按照該算法進(jìn)行256次操作，可得到256 個CRC32查找表值。

得到查找表后，則對數(shù)據(jù)進(jìn)行CRC校驗(yàn)，其校驗(yàn)步驟是將待校驗(yàn)數(shù)據(jù)與32位寄存器的低8位做XOR運(yùn)算得到一個指向查詢表的索引值，將所將索引所指的表值與寄存器的高24位做XOR運(yùn)算，得到的值更新到32位寄存器中，同時該值也為校驗(yàn)過的值，如數(shù)據(jù)沒有全部處理完，則跳到開始進(jìn)行運(yùn)算。

2　FPGA硬件實(shí)現(xiàn)

FPGA實(shí)現(xiàn)CRC32校驗(yàn)時，一種方法是校驗(yàn)之前將CRC32生成的查找表值直接存入ROM中，按照索引值去取表內(nèi)值。第二種方法是在校驗(yàn)前根據(jù)算法生成CRC32的查找表值，依次存入RAM中，生成查找表之后再按照索引值去取表內(nèi)值。本文是按照第二種方式進(jìn)行校驗(yàn)。這種方式的優(yōu)點(diǎn)是靈活、易于操作。FPGA實(shí)現(xiàn)的流程圖如圖1所示，待校驗(yàn)數(shù)據(jù)Din與CRC32低8位異或的值產(chǎn)生查找表的索引值，由于查找表是RAM存儲器，為了數(shù)據(jù)輸出穩(wěn)定，輸出寄存一拍，從RAM出來的值會有兩拍延遲。Din數(shù)據(jù)寄存一拍，CRC32數(shù)據(jù)輸出寄存一拍，共有4拍數(shù)據(jù)延遲，所以CRC32會比串行校驗(yàn)提高8倍時鐘周期。

圖1　FPGA實(shí)現(xiàn)CRC32校驗(yàn)的流程圖

生成查找表值代碼段如下，其中tab_cnt_next一個周期的高電平將tab_cnt_refl ect鏡像值更新到crc32_table，ulPolynomial是校驗(yàn)多項(xiàng)式值32'h04C11DB7，循環(huán)256次，并將256個crc32_table值鏡像之后存入RAM中。

if（tab_cnt_next==1'b1）

crc32_table <=｛tab_cnt_refl ect，24'h0｝；

else if（crc32_table［31］==1'b1）

crc32_table <=｛crc32_table［30：0］，1'b0｝^ulPolynomial；

else crc32_table <=｛crc32_table［30：0］，1'b0｝；

對Din數(shù)據(jù)進(jìn)行校驗(yàn)的主要代碼如下，dat_valid是一個周期的高電平，crc_value初始值為0，tab_index是RAM的讀地址，兩拍后從RAM讀的值rd_ram_data和crc_value高24位異或更新到新的crc_ value值。

if（dat_valid==1'b1）

tab_index <=crc_value［7：0］^din；

else if（dat_valid_2d==1'b1）

crc_value <=rd_ram_data ^crc_value［31：8］；

3　CRC32的仿真驗(yàn)證

CRC32生成查找表要循環(huán)256次完成查找表所有值的遍歷，其用Modelsim仿真如圖2所示，crc32_table的鏡像值crc32_table_ refl ect即為查找表的值，圖2中顯示的32’h0、32’h 77073096、32’hEE0E612C、32’h 990951BA即為CRC32正規(guī)查詢表值0到3的值。選取待校驗(yàn)值0xAA，0x44，0x13其CRC32校驗(yàn)值crc_value如圖3所示，最后一個值0xc4441369即為校驗(yàn)值，經(jīng)驗(yàn)證正確。

圖2　CRC32生成查找表的Modelsim仿真圖

圖3　CRC32校驗(yàn)的Modelsim仿真圖

4　結(jié)束語

本文介紹了CRC32校驗(yàn)算法的FPGA實(shí)現(xiàn)方法，詳細(xì)介紹了CRC32查找表的生成、CRC32的數(shù)據(jù)校驗(yàn)，并列出了FPGA實(shí)現(xiàn)的verilog代碼和仿真時序圖。經(jīng)過驗(yàn)證可以證明此方法的可行性，并提高了CRC32校驗(yàn)的速率。

［1］葉懋，劉宇紅，劉橋.CRC碼的FPGA實(shí)現(xiàn)［J］.重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版），2007（03）.

［2］莫元勁，黃水永.并行CRC在FPGA上的實(shí)現(xiàn)［J］.電子設(shè)計(jì)工程，2011（15）.

10.16640/j.cnki.37-1222/t.2016.10.188

時亞麗（1988-），女，安徽合肥人，碩士，助理工程師。