郭寶增，吳鵬飛

(河北大學(xué) 電子信息工程學(xué)院，河北 保定 071002)

CRC的全稱是循環(huán)冗余校驗(yàn)(cyclic redundancy check)，是一種非常著名的檢錯(cuò)手段，在通信和數(shù)據(jù)存儲(chǔ)領(lǐng)域得到廣泛應(yīng)用.其特點(diǎn)是檢錯(cuò)能力極強(qiáng),開銷小,易于編碼器及檢測電路實(shí)現(xiàn).從檢錯(cuò)能力來看，其不能發(fā)現(xiàn)的錯(cuò)誤的幾率在0.004 7%以下.著名的通訊協(xié)議X.25的FCS(幀檢錯(cuò)序列)采用的是CRC-CCITT；ARJ，LH等壓縮工具軟件采用的是CRC32；磁盤驅(qū)動(dòng)器的讀寫采用了CRC16；通用的圖像存儲(chǔ)格式GIF，TIFF等都使用CRC作為檢錯(cuò)手段[1].

1 CRC32算法研究

1.1 LSFR串行編碼算法

CRC32屬于線性分組碼的分支，同時(shí)還具有循環(huán)特性，符合一般循環(huán)碼的編碼方法[2]，其過程可以采用LSFR實(shí)現(xiàn)編碼電路，這種電路主要由移位寄存器和異或門組成[3-4].對于CRC32校驗(yàn)碼，生成多項(xiàng)式為

g(x) =x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1.

(1)

以8 bit的數(shù)據(jù)輸入為例，其硬件實(shí)現(xiàn)框圖如圖1所示.

圖1 LSFR串行編碼電路Fig.1 LSFR serial encoder circuit

圖1中，32位移位寄存器用于存儲(chǔ)CRC32校驗(yàn)碼，稱其為CRC寄存器.編碼前將寄存器各位置1，每個(gè)時(shí)鐘周期1 bit數(shù)據(jù)輸入，通過移位和異或運(yùn)算，CRC寄存器中的數(shù)據(jù)進(jìn)行隨之更新，8個(gè)時(shí)鐘周期后，數(shù)據(jù)輸入完畢，此時(shí)CRC寄存器的值即為CRC32的碼序列，該算法原理簡單，便于硬件實(shí)現(xiàn)，但效率不高，主要應(yīng)用于串行通信.

1.2 并行CRC32算法

從本質(zhì)上說，LSFR算法是一種串行算法，針對LSFR電路效率低的問題，本文從LSFR電路的結(jié)構(gòu)入手，通過相應(yīng)的邏輯運(yùn)算推導(dǎo)出高效并行的CRC32編碼算法.

(2)

(3)

(4)

(5)

(6)

將(3)，(4)，(5)，(6)式代入(2)式，可以求得

(7)

即移位寄存器R0經(jīng)過8個(gè)時(shí)鐘后的狀態(tài)值可以表示為移位寄存器R30，R24的初始值與輸入數(shù)據(jù)D7，D1的異或運(yùn)算，這樣就可以將LSFR中8 bit的串行輸入數(shù)據(jù)轉(zhuǎn)換為等效的并行輸入，將其記做CRC0.按照上述的推導(dǎo)原則，可以求得其他31個(gè)寄存器經(jīng)過8個(gè)時(shí)鐘后的狀態(tài)值.

8 bit并行輸入，經(jīng)過并行運(yùn)算單元運(yùn)算之后，將運(yùn)算結(jié)果存儲(chǔ)到移位寄存器R0-R31，移位寄存中的值有2個(gè)用途：當(dāng)前時(shí)鐘周期下，直接以運(yùn)算結(jié)果的形式作為輸出；下一時(shí)鐘周期作為保護(hù)數(shù)據(jù)反饋到并行運(yùn)算單元，共同作用到下一時(shí)鐘周期.

2 并行CRC32算法的FPGA驗(yàn)證

在算法研究的基礎(chǔ)上，鑒于ASIC(application specific integrated circuit)流片成本高，風(fēng)險(xiǎn)大，因此大規(guī)模量產(chǎn)之前需要事先對芯片的設(shè)計(jì)進(jìn)行FPGA驗(yàn)證.通過驗(yàn)證，一方面可以確保系統(tǒng)邏輯功能的正確；另一方面可以說明系統(tǒng)的時(shí)序基本可以滿足設(shè)計(jì)要求[3].

依據(jù)推導(dǎo)出的邏輯關(guān)系，編寫并行CRC32算法的verilog代碼[5]

module crc(

input[7:0] data_in,

input crc_en,

output [31:0] crc_out,

input rst,

input clk);

reg[31:0] lfsr_q,lfsr_c;

assign crc_out = lfsr_q;

always @(*) begin

lfsr_c[0] = lfsr_q[30] ^ data_in[7] ^ lfsr_q[24] ^ data_in[1];

?

lfsr_c[31] = lfsr_q[23] ^ lfsr_q[29] ^ data_in[2];

end

always @(posedge clk, posedge rst) begin

if(rst) begin

lfsr_q <= {32{1’b1}};

end

else begin

lfsr_q <= crc_en ? lfsr_c : lfsr_q;

end

end

endmodule

生成的并行CRC32編碼模塊如圖2所示.

圖2中data_in為8位數(shù)據(jù)輸入端；crc_en為使能端，只有當(dāng)crc_en為高電平時(shí)，編碼器才進(jìn)行編碼工作；rst為復(fù)位信號(hào)(高電平有效)，當(dāng)電平為高時(shí)，進(jìn)行初始化；clk為時(shí)鐘信號(hào)；crc_out為32位CRC編碼輸出端.

通過編寫testbench，利用Modelsim軟件對生成的編碼模塊進(jìn)行功能仿真，其仿真結(jié)果如圖3所示.

圖3 并行CRC32編碼電路功能仿真結(jié)果Fig.3 Function simulation result of Parallel CRC32 encoder circuit

仿真輸入數(shù)據(jù)為8’h12，8’h34，8’h56，8’h78，8’h9a，8’hcf；得到的CRC32校驗(yàn)碼為16’h5c86227b，16’h669666e7，16’ha36a7c64，16’he68f6fad，16’h0a1e9dc3，16’hb5ecce06，通過觀察仿真結(jié)果，其編碼結(jié)果與理論計(jì)算的結(jié)果一致.

將編譯后的工程文件下載到DE2-70開發(fā)板，通過實(shí)驗(yàn)檢測，可以得到一致的輸出結(jié)果，至此芯片代碼的FPGA驗(yàn)證工作結(jié)束.

3 并行CRC32編碼芯片的實(shí)現(xiàn)

FPGA的使用費(fèi)用太高，資源利用率較低；在功耗、設(shè)計(jì)密度以及產(chǎn)品的運(yùn)算速度方面相對ASIC來說存在相當(dāng)程度的劣勢，因此，為了實(shí)現(xiàn)產(chǎn)品的大規(guī)模生產(chǎn)，必須進(jìn)行系統(tǒng)邏輯的版圖GDS II設(shè)計(jì).設(shè)計(jì)過程采用中芯國際180 nm的數(shù)字工藝庫，主要使用Synopsys公司的Design Compiler邏輯綜合軟件，和Cadence公司的Soc Encounter自動(dòng)布局、布線軟件實(shí)現(xiàn)版圖的GDS II文件設(shè)計(jì).

3.1 編碼電路的邏輯綜合

使用Design Compiler軟件，對編碼電路的verilog代碼進(jìn)行邏輯綜合，其主要工作包括：一方面將硬件語言描述的行為級電路、RTL級電路轉(zhuǎn)換到基于工藝庫的門級網(wǎng)表[6]；另一方面要根據(jù)綜合產(chǎn)生的時(shí)序報(bào)告，對綜合過程中的各項(xiàng)參數(shù)進(jìn)行修改，以保證時(shí)間余量(slack)為給定時(shí)鐘的30%以上，這是由于綜合過程中設(shè)置的連線負(fù)載只是工藝庫提供的延時(shí)參數(shù)，并不是實(shí)際延時(shí)，必須以足夠的slack為后續(xù)的實(shí)際布局、布線提供充足的延時(shí)空間，圖4為綜合后的時(shí)序報(bào)告.

圖4 邏輯綜合時(shí)序報(bào)告Fig.4 Logic synthesis timing report

從圖中可以看出給定的時(shí)鐘clk為10 ns，而綜合后的slack為6.18 ns，超過要求的最少時(shí)間余量3 ns，說明綜合過程可以提供充足的時(shí)間余量用于布局、布線.

將滿足上述要求綜合后的verilog文件(門級網(wǎng)表文件)和sdf文件(時(shí)序約束文件)進(jìn)行導(dǎo)出，采用Formality形式驗(yàn)證工具對綜合后的網(wǎng)表進(jìn)行邏能的驗(yàn)證，形式驗(yàn)證相對于時(shí)序仿真的優(yōu)勢在于，能夠以較短的時(shí)間消耗比較綜合前、后電路邏輯功能是否一致.

3.2 編碼電路的布局、布線

使用Soc Encounter軟件，導(dǎo)入邏輯綜合后的verilog文件和sdf文件，完成版圖GDS II的設(shè)計(jì)，設(shè)計(jì)過程需要針對版圖的面積、時(shí)序進(jìn)行分析，采取面積約束、優(yōu)化布局布線、時(shí)鐘數(shù)綜合等方法達(dá)到合理的版圖設(shè)計(jì)，隨后完成版圖的LVS比較和DRC規(guī)則檢查，得到的版圖文件如圖5所示.

圖5 并行CRC32編碼芯片版圖Fig.5 Parallel CRC32 encoder chip layout

3.3 編碼電路的時(shí)序仿真

上面提到過對于驗(yàn)證電路功能是否與原始代碼一致可以采用形式驗(yàn)證工具Formality.而本設(shè)計(jì)是優(yōu)化的并行電路結(jié)構(gòu)，其結(jié)構(gòu)簡單，使用的邏輯單元較小，時(shí)序仿真的耗時(shí)可以接受，因此可以采用Modelsim對編碼電路進(jìn)行時(shí)序仿真加以驗(yàn)證，時(shí)序仿真的結(jié)果如圖6所示.

圖6 并行CRC32編碼芯片時(shí)序仿真結(jié)果Fig.6 Timing simulation result of Parallel CRC32 encoder chip

通過比較功能仿真和時(shí)序仿真結(jié)果，可以證明所設(shè)計(jì)芯片完全能夠?qū)崿F(xiàn)CRC32的并行編碼功能.

4 結(jié)語

在研究CRC算法及編碼原理的基礎(chǔ)上，從代碼編寫到GDS II版圖生成，完成了數(shù)字集成電路前端到后端的整個(gè)設(shè)計(jì)流程；所實(shí)現(xiàn)的編碼芯片能夠以高效的速率完成編碼工作.此外，本文介紹的芯片設(shè)計(jì)方法對了解和掌握數(shù)字芯片設(shè)計(jì)思想起到一定的指導(dǎo)作用.

參 考 文 獻(xiàn):

[1] 張樹剛,張遂南,黃士坦.CRC校驗(yàn)碼并行計(jì)算的FPGA實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(2):56-62.

ZHANG Shugang,ZHANG Suinan,HUANG Shitan.CRC Parallel Computation Implementation on FPGA[J].Computer Technology and Development,2007,17(2)：56-62.

[2] 樊昌信,張甫翊,徐炳祥,等.通信原理[M].北京:國防工業(yè)出版社,2001.

[3] SHIEH M D,SHEU M H,CHEN C H,et al.A systematic approach for parallel CRC computations [J].Journal of Information Science and Engineering,2001,17:445-461.

[4] RAMABADRAN T V,GAITONDE S S.A tutorial on CRC computations[J].IEEE Micro,1988(8):62-75.

[5] 夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程[M].北京:北京航空航天大學(xué)出版社,2003.

[6] 韓雁,洪慧,馬紹宇,等.集成電路設(shè)計(jì)制造中EDA工具實(shí)用教程[M].杭州:浙江大學(xué)出版社,2007.