可變生成多項(xiàng)式與輸入位寬的并行CRC

張 強(qiáng)

(思科系統(tǒng)(中國)研發(fā)有限公司,上海200233)

可變生成多項(xiàng)式與輸入位寬的并行CRC

張 強(qiáng)

(思科系統(tǒng)(中國)研發(fā)有限公司,上海200233)

介紹了兩種LFSR類型的CRC且比較了它們的特性,然后以II型LFSR為基礎(chǔ),分兩步先后推導(dǎo)出任意m比特的直接并行計(jì)算以及如何進(jìn)行連續(xù)m比特的計(jì)算,即得到可變生成多項(xiàng)式與輸入位寬的并行CRC算法,最后舉例給出基于CCITT-16協(xié)議的4比特輸入位寬的VHDL程序?qū)崿F(xiàn)代碼并給出仿真驗(yàn)證結(jié)果。由此對(duì)于給定的生成多項(xiàng)式與輸入位寬,通過提出的算法用C語言或者硬件電路描述語言可以實(shí)現(xiàn)快速簡單的并行CRC計(jì)算。

循環(huán)冗余校驗(yàn) 線性反饋移位寄存器 并行算法

0 引 言

CRC全稱為Cyclic Redundancy Check,中文名稱為循環(huán)冗余校驗(yàn),由W.Wesley Peterson于1961年發(fā)明,編碼和解碼方法簡單,檢錯(cuò)能力強(qiáng),在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制,例如發(fā)送端根據(jù)傳送的m位二進(jìn)制碼序列,用一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼(CRC碼),附在原始信息后面,構(gòu)成一個(gè)新的二進(jìn)制碼序列共m+r位,然后發(fā)送出去。接收端根據(jù)信息碼和CRC碼之間所遵循的生成規(guī)則進(jìn)行校驗(yàn),以確定傳送中是否出錯(cuò)[1]。這個(gè)規(guī)則,在差錯(cuò)控制理論中稱為生成多項(xiàng)式。

隨著高帶寬數(shù)據(jù)處理與數(shù)據(jù)傳輸?shù)陌l(fā)展,串行CRC早已不能滿足現(xiàn)代通信系統(tǒng)的需求,因此高階次生成多項(xiàng)式與高輸入位寬的并行CRC被廣泛使用,目前主要有查表法[2]和并行矩陣法[3]。查表法雖可實(shí)現(xiàn)快速CRC計(jì)算,但需消耗硬件電路中寶貴的存儲(chǔ)資源,甚至是不能實(shí)現(xiàn)的,例如對(duì)輸入位寬為32比特的數(shù)據(jù)做CRC-32的并行查表計(jì)算,需要消耗的存儲(chǔ)資源為232×32比特,即16G字節(jié)的存儲(chǔ)空間。而并行矩陣法可以用簡單的異或邏輯快速實(shí)現(xiàn)并行CRC,但目前流行的算法中多以2的冪次輸入位寬進(jìn)行推導(dǎo),比如8、16和32,且多項(xiàng)式冪次也為偶數(shù)。文中將對(duì)任意多項(xiàng)式階次與任意輸入位寬的并行矩陣法進(jìn)行推導(dǎo)。

1 串行算法

1.1 多項(xiàng)式除法

對(duì)于信息串“11100110”,設(shè)信息多項(xiàng)式為M(x)=x7+x6+x5+x2+x1。若生成多項(xiàng)式G(x)=x3+ x1+1,則M(x)×x3除以G(x)的余數(shù)項(xiàng)R(x)={M(x)×x3}mod{G(x)}=x2,即CRC碼為“100”。對(duì)于多項(xiàng)式除法的邏輯實(shí)現(xiàn),需要將多項(xiàng)式除法和電路模型對(duì)應(yīng)以方便實(shí)現(xiàn)CRC計(jì)算。線性反饋移位寄存器(LFSR)是很好的電路模型[4]。

1.2 LFSRI型

LFSR由r個(gè)D觸發(fā)器和異或門以及一個(gè)反饋電路組成,其中r為生成多項(xiàng)式的最高階次。如圖1所示,I型中系數(shù)Gi(i=0,1,…,r-1)決定Yr-1是否作為反饋參與寄存器Yi-1和輸入串行比特D的異或運(yùn)算。

圖1 I型線性反饋移位寄存器Fig.1 LFSR I

1.3 LFSR II型

由系數(shù)Gi決定輸入D與Yr-1的異或結(jié)果是否作為反饋參與寄存器Yi-1的異或運(yùn)算。

圖2 II型線性反饋移位寄存器Fig.2 LFSRII

1.4 類型比較

I型與II型對(duì)比如表1所示。

表1 I型與II型對(duì)比Table 1 Comparison of between type I and II

2 并行CRC算法

2.1 m個(gè)比特的并行計(jì)算

設(shè)m位比特串B={Dm-1,Dm-2,…,D1,D0},生成多項(xiàng)式系數(shù)G={Gr-1,Gr-2,…,G1,G0},則余數(shù)項(xiàng)R(x)={B×xr}mod{G(x)}={(Dm-1×xm-1+Dm-2×xm-2+,…,D1×x1+D0)×xr}mod{G(x)}。令Ri={Di×xi× xr}mod{G(x)}且0≤i≤m-1,即Ri等于比特串{Di,左移r位后除以G的余數(shù)項(xiàng),則總的余數(shù)項(xiàng)為,由II型LFSR可知Ri需i+1次的移位運(yùn)算,令j為移位運(yùn)算的次序且1≤j≤i+1,則Ri,j,r為Ri經(jīng)過j次移位后第r位比特的結(jié)果,通過II型的電路計(jì)算可得:

由Ri,1和Ri,j可知,Di首先進(jìn)入II型電路,后續(xù)對(duì)進(jìn)入‘0’的運(yùn)算,都是將Yr-1中的結(jié)果不斷的對(duì)電路做式(2)中的線性反饋異或運(yùn)算[5]。因Ri,1中的每一比特均有Di乘數(shù)因子,所以最終的Ri,i+1中的每一比特必有Di因子和一個(gè)由多項(xiàng)式系數(shù)經(jīng)過運(yùn)算得出的系數(shù)因子Hi,r,則Ri表示為:

考察式(3),若Di=0,則Ri=0,若Di=1,則

由式(1)知,Di=1時(shí),Ri,1={Gr-1,Gr-2,…,G1,G0}；因系數(shù)Gi為常數(shù),所以將Ri,1代入式(2),通過循環(huán)迭代,得到Ri,i+1,即Ri。從式(4)可見,Hi,r已求出,則Ri最終由變量Di確定。

將式(2)迭代中的每個(gè)結(jié)果保存,得到m個(gè)Hi={Hi,r-1,Hi,r-2,…,Hi,1,Hi,0}；則

由式(5)可知,H矩陣為已知,將任意m位比特串B={Dm-1,Dm-2,…,D1,D0}輸入,通過矩陣運(yùn)算可立即得到CRC結(jié)果R。

2.2 連續(xù)m個(gè)比特的并行計(jì)算

對(duì)于連續(xù)的并行輸入,需對(duì)連續(xù)的前后兩次m比特并行計(jì)算進(jìn)行分析,才能達(dá)到連續(xù)處理并行數(shù)據(jù)的目的。

設(shè)B[n]為并行數(shù)據(jù)中的第n個(gè)m位比特串,生成多項(xiàng)式G的次數(shù)為r,設(shè)Br[n]為B[n]除以G的余數(shù),即Br[n]=(B[n]×xr)mod(G)。

則n個(gè)m位比特除以G的余數(shù)為:

算法為:

a)用2.1節(jié)的算法快速計(jì)算得出B[n-1]的余數(shù)Br[n-1]。

b)將Br[n-1]與B[n-2]異或。

c)異或后的結(jié)果重復(fù)a)中的快速計(jì)算。

2)若r＜m,則

算法為:

a)用2.1節(jié)的算法快速計(jì)算得出B[n-1]的余數(shù)Br[n-1]。

b)將Br[n-1]左移m-r位且右邊補(bǔ)‘0’后與B [n-2]異或。

c)異或后的結(jié)果重復(fù)作a)中的快速計(jì)算。

3)若r＞m,則

令Brm[n]為Br[n]的高m位,Br-m[n]為Br[n]的低r-m位,即

令B′r[n-2]為Brm[n-1]+B[n-2]除以G的余數(shù),類似B[n-1]項(xiàng)的計(jì)算,得

可見R中的最高階次為(n-3)m,與計(jì)算B[n-1]項(xiàng)后相比階次降低了1。

a)用2.1節(jié)的算法快速計(jì)算得出B[n-1]的余數(shù)Br[n-1]。

b)Brm[n-1]與B[n-2]異或后重復(fù)做a)中的計(jì)算得B′r[n-2]。

c)B′r[n-2]與{Br-m[n-1],異或得B″r[n-2]。

d)對(duì)B″r[n-2]和B[n-3]重復(fù)做b)中的計(jì)算。

3 VHDL設(shè)計(jì)舉例

對(duì)CCITT-16標(biāo)準(zhǔn),其生成多項(xiàng)式G(x)=x16+ x12+x5+1,輸入位寬4 bit,VHDL實(shí)現(xiàn)代碼為:

4 仿真驗(yàn)證

將十進(jìn)制數(shù)據(jù)串“0123456789”轉(zhuǎn)換成十六進(jìn)制的ASCII碼值,即“0x30313233343536373839”,然后每個(gè)時(shí)鐘周期將上述結(jié)果中的數(shù)據(jù)以4 bit為單位從左端依次賦值給變量D,令Y初值為0。如圖3所示,仿真最終的結(jié)果為0x9C58。

圖3 CCITT-16協(xié)議的4 bit輸入位寬CRC仿真Fig.3 CRC simulation for 4 bit data with CCITT-16

5 結(jié) 語

文中給出可變生成多項(xiàng)式與輸入位寬的并行CRC算法,只需將生成多項(xiàng)式系數(shù)G代入公式即可得系數(shù)矩陣H,每組輸入比特向量與矩陣相乘可得CRC計(jì)算結(jié)果；對(duì)連續(xù)的并行計(jì)算,須根據(jù)2.2節(jié)中的三種情況進(jìn)行判斷,把前次的結(jié)果與下次的輸入比特關(guān)聯(lián)運(yùn)算,所得結(jié)果才能作為下一次CRC運(yùn)算的輸入。由此實(shí)現(xiàn)連續(xù)并行計(jì)算的一種通用算法。可見,與通常的并行CRC算法相比,文中不對(duì)多項(xiàng)式階次與輸入位寬做約束,只需將使用的多項(xiàng)式階次與輸入位寬作為參數(shù),即可運(yùn)用文中的算法快速得到并行CRC的邏輯運(yùn)算電路。

[1] 劉偉,王俊芳,王立瑩,等.千兆以太網(wǎng)MAC中CRC算法的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),2012,45(07):32-34,37.

LIU Wei,WANG Jun-fang,WANG Li-ying,et al.CRC Algorithm Design and Develop ment in Gigabit Ethernet-MAC[J].Communications Technology,2012,45(07):32 -34,37.

[2] 李劍鋒.新的高性能CRC查表算法[J].計(jì)算機(jī)應(yīng)用, 2011(06):181-182,121.

LI Jian-feng.New Table Look-up Algorithm for High-Performance CRC[J].Computer Application,2011(06): 181-182,121.

[3] CAMPOBELLO G,PATANE G,RUSSO M.Parallel CRC Realization[J].IEEE Transaction on Computers,2003, 52(10):1312-1319.

[4] 王新梅,肖國鎮(zhèn).糾錯(cuò)碼-原理與方法[M].西安:西安電子科技大學(xué)出版社,2001.

WANG Xin-mei,XIAO Guo-zhen.Correcting Code-Theory and Method[M].Xi′an:Xi′an University of E-lectronic Science and Technology Press,2001.

[5] PEREZ A.Byte-Wise CRC Calculation[J].IEEE Micro, 1983,N(06):40-50.

ZHANG Qiang(1978-),male,M.Sci., senior hardware engineer,majoring in FPGA algorithm research and development in communication system.

Parallel CRC Algorithm with Variable Generator and Data Width

ZHANG Qiang
(Cisco Systems China R&D Center,Shanghai 200233,China)

The paper describes two methods of LFSR and compares their features.Then based on type II of LFSR,it derives in two steps the calculation of‘m’bits parallel data in one clock cycle and the execution of continuous parallel calculation.So the whole algorithm for variable generator and data width can be realized.Finally,an example based on CCITT-16 and 4 bit data width is provided by using VHDL,and the simulation result also given.Therefore for certain generator and data width,parallel CRC could be completed quickly and easily by C or hardware description language.

CRC；LFSR；parallel algorithm

TN918

A

1002-0802(2014)03-0335-04

10.3969/j.issn.1002-0802.2014.03.020

張 強(qiáng)(1978—),男,碩士,高級(jí)硬件工程師,主要研究方向?yàn)橥ㄐ畔到y(tǒng)中FPGA實(shí)現(xiàn)算法的研究與開發(fā)。