胡坤焌 黃元峰

摘要：為解決大規(guī)模數(shù)據(jù)傳輸中CRC校驗(yàn)的實(shí)時(shí)處理問題，文章提出了一種可同時(shí)處理256位數(shù)據(jù)的并行算法。文章首先通過遞推法推導(dǎo)出4位數(shù)據(jù)并行運(yùn)算CRC（Cyclical Redundancy Check）關(guān)系式，并將表達(dá)式系數(shù)提出轉(zhuǎn)化為矩陣，在此基礎(chǔ)上對(duì)矩陣反復(fù)迭代，求得256位數(shù)據(jù)并行計(jì)算矩陣。該并行算法推導(dǎo)過程直觀易懂，算法實(shí)現(xiàn)簡(jiǎn)單。文章最后采用硬件描述語言對(duì)算法進(jìn)行描述，并搭建了驗(yàn)證環(huán)境。仿真驗(yàn)證結(jié)果表明了該方案的可行性，達(dá)到了設(shè)計(jì)指標(biāo)要求，在時(shí)鐘頻率為400MHz的條件下可滿足100G以太網(wǎng)中CRC校驗(yàn)需求。

關(guān)鍵詞：高速以太網(wǎng);256位并行數(shù)據(jù);CRC編碼; 矩陣并行算法;CRC校驗(yàn)

中圖分類號(hào)：TP319.56 ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）13-0037-03

1 引言

隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的存儲(chǔ)和傳輸速度大大提高[1]。由于信息傳輸過程中的干擾，信號(hào)的失真依然難以避免，而通過增加冗余碼的方式來對(duì)傳輸數(shù)據(jù)進(jìn)行檢錯(cuò)和糾錯(cuò)，可大大提高數(shù)字通信的可靠性。在多種檢錯(cuò)碼中，由于CRC編碼和解碼方法簡(jiǎn)單、檢錯(cuò)能力強(qiáng)等特點(diǎn)，在數(shù)字通信中得到廣泛應(yīng)用[2]。如今，網(wǎng)絡(luò)安全已經(jīng)是熱門的探討話題[3]，CRC校驗(yàn)也同樣在網(wǎng)絡(luò)安全領(lǐng)域中廣泛應(yīng)用。在IEEE 2010年發(fā)布的802.3ba標(biāo)準(zhǔn)中，MAC（Media Access Control）層仍沿用之前的規(guī)定，而100Gb/s的數(shù)據(jù)傳輸速率使得以往CRC計(jì)算方法不再適用，需要采用更高位寬的并行數(shù)據(jù)來滿足現(xiàn)代數(shù)字通信對(duì)于高吞吐量需求。

CRC編碼實(shí)現(xiàn)方式多種多樣[4]。傳統(tǒng)串行編碼利用LFSR（Linear Feedback Shift Register）進(jìn)行級(jí)聯(lián)，其結(jié)構(gòu)簡(jiǎn)單且容易實(shí)現(xiàn)，但缺點(diǎn)是處理效率低下且無法應(yīng)用到對(duì)速度要求較高的場(chǎng)合，因此在高速通信領(lǐng)域中越來越多地使用并行計(jì)算的方法。文獻(xiàn)[5]中提到的查表法運(yùn)算較快，但需要存儲(chǔ)模塊來預(yù)先存儲(chǔ)表中項(xiàng)目。當(dāng)并行計(jì)算位數(shù)每增加一位，所需存儲(chǔ)的表項(xiàng)就會(huì)呈現(xiàn)指數(shù)級(jí)增長(zhǎng)，由于占用資源多，所以難以應(yīng)用在高位寬數(shù)據(jù)場(chǎng)合。文獻(xiàn)[6]提出了一種用級(jí)聯(lián)結(jié)構(gòu)實(shí)現(xiàn)對(duì)64位數(shù)據(jù)的并行運(yùn)算，但當(dāng)進(jìn)一步提高并行數(shù)據(jù)位寬時(shí)，級(jí)聯(lián)結(jié)構(gòu)就會(huì)增多，256位并行計(jì)算時(shí)需要32個(gè)模塊，延時(shí)大大增加。文獻(xiàn)[7]提出了一種128位并行數(shù)據(jù)的CRC算法，但由于時(shí)鐘頻率的限制，滿足不了100Gb/s的吞吐量的需求。

本文提出了一種可實(shí)現(xiàn)256位并行數(shù)據(jù)的CRC編碼方案，并對(duì)此方案進(jìn)行了硬件實(shí)現(xiàn)。通過對(duì)仿真結(jié)果進(jìn)行分析，驗(yàn)證了其準(zhǔn)確性并具有一定的實(shí)用價(jià)值，在時(shí)鐘頻率為400MHz的情況下，其能夠滿足吞吐量為100Gb/s的需求。

2 CRC校驗(yàn)原理

設(shè)通信中待檢測(cè)的信息碼為n位，將此信息碼用多項(xiàng)式M表示：

[M=mn-1Xn-1+mn-2Xn-2+…+m1X+m0 ] ? ? ?（1）

為了計(jì)算該數(shù)據(jù)的CRC，還需要一個(gè)稱為生成多項(xiàng)式的多項(xiàng)式g（x），其最高次冪為k。待編碼的信息序列與多項(xiàng)式g（x）進(jìn)行模二運(yùn)算，則會(huì)對(duì)應(yīng)生成一個(gè)k-1位的冗余碼。CRC檢驗(yàn)的一般計(jì)算流程如下：

1）將式（1）中的多項(xiàng)式M乘以[Xk]，即信息序列左移k位得到式（2）：

[XkM=mn-1Xk+n-1+mn-2Xk+n-2+L+m1Xk+1+m0Xk] ? ? （2）

2）將得出來的結(jié)果式（2）除以生成多項(xiàng)式g（x），得到式（3）及相應(yīng)的余數(shù)多項(xiàng)式r（x）：

[XkMg（x）=q（x）+rxgx ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）]

其中r（x）為：

[rx=rk-1xk-1+rk-2xk-2+…+r1x+r0 ? ? ? ? ? ? （4）]

3）將式（2）（4）帶入式（3）中，則得到附有CRC碼的數(shù)據(jù)序列式（5）：

[qxgx=XkM+rx=mn-1Xk+n-1+…+m1Xk+1+…+r1x+r0 ]

（5）

4）在接收端接收到帶CRC碼的數(shù)據(jù)序列后，使用相同的多項(xiàng)式進(jìn)行模二運(yùn)算。若余數(shù)為0，則表明數(shù)據(jù)在傳輸中沒有錯(cuò)誤。反之，則說明傳輸發(fā)生錯(cuò)誤。

通過線性反饋寄存器級(jí)聯(lián)實(shí)現(xiàn)的CRC串行計(jì)算電路[8]主要由移位寄存器和異或門組成，具體硬件結(jié)構(gòu)如圖1所示[9]。每個(gè)時(shí)鐘周期僅能輸入1比特?cái)?shù)據(jù)，并進(jìn)行相應(yīng)移位和異或運(yùn)算后得到計(jì)算結(jié)果。對(duì)于n位的數(shù)據(jù)來說，則需要n個(gè)周期完成CRC值計(jì)算。由于串行計(jì)算效率低下，一般只被用于低速通信的場(chǎng)合中[10]。

設(shè)[cj+1i+1]為第j+1次輸入數(shù)據(jù)的情況下第i+1位CRC的值，[cji]為第j次輸入數(shù)據(jù)的情況下第i位CRC的值，[dj+1]為第j+1位的數(shù)據(jù)輸入，[cj31]為第j位數(shù)據(jù)輸入后的第31位CRC值。由此則可以得到當(dāng)前此位數(shù)據(jù)的CRC值與前一位數(shù)據(jù)及其CRC碼之間的關(guān)系，即式（6）：

[cj+1i+1=cji⊕gi+1dj+1⊕cj31 ? ? ? ? ? ? ? ? ? ? ? ? ?（6）]

3矩陣并行算法

依據(jù)以太網(wǎng)的國(guó)際標(biāo)準(zhǔn)IEEE 802.3[11]，數(shù)據(jù)幀中使用的CRC校驗(yàn)?zāi)Ｐ蜑镃RC-32[12]，其對(duì)應(yīng)的生成多項(xiàng)式g（x）為[13]：

[gx=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1]

對(duì)式（6）進(jìn)行4次遞歸運(yùn)算，可得到處理4位數(shù)據(jù)后的CRC碼與初始CRC碼和數(shù)據(jù)之間的關(guān)系式，推導(dǎo)出的CRC-32關(guān)系式如下：

[c431=c270c430=c260L ? ? ? ? ?L c45=c310⊕c290⊕c280⊕c280⊕c00⊕d3⊕d1⊕d0L ? ? ? ? ?Lc41=c290⊕c280⊕d1⊕d0c40=c280⊕d0]

當(dāng)前CRC值中的每一位的值都可表達(dá)為式（7）：

[c1i=xi31c031⊕L⊕xi0c00⊕yi3d13⊕L⊕yi0d10 ? ? ? ? ? ? ? ? ? （7）]

其中i為自然數(shù)，i=0，1，...，31。x和y分別為初始CRC碼及輸入的4位數(shù)據(jù)的系數(shù)。

將式（7）表達(dá)式中的系數(shù)x、y提出，可得到一個(gè)36*32的矩陣，如矩陣（1）。

將矩陣（1）進(jìn)行轉(zhuǎn)置，拆分成兩塊。其中前32行為系數(shù)x組成的32*32 CRC系數(shù)矩陣[14]，如矩陣（2）。

后四行為系數(shù)y組成的4*32輸入數(shù)據(jù)參數(shù)矩陣：

[00100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111]

設(shè)：

[C1=C131，C130…C1i…C10]

[C0=C131，C130…C1i…C10]

根據(jù)式（2）并將式中的加號(hào)替換為異或，可以得到第一次4位數(shù)據(jù)輸入結(jié)果，計(jì)算公式如式（8）：

[C1=C0*C32*32+D1*D4*32] ? ? ? ? ? ? ? ? ? ? ? [8]

將式（8）進(jìn)行一次迭代，可以得到第二次4位數(shù)據(jù)輸入計(jì)算結(jié)果式（9）：

[C2=C1*C32*32+D2*D4*32=C0*C32*32+D1*D4*32*C32*32+D2*D4*32] ? ? ? ? ? ? [9]

同理，將式（9）再進(jìn)行迭代，經(jīng)過6次迭代后可得到256位數(shù)據(jù)并行的矩陣表達(dá)式，即式（10）：

[C256=C0*C25632*32+D256*D256256*32 ? ? ? ? ? ? ? ? ? ? ? 10]

式（10）中[C256]為256位并行數(shù)據(jù)輸入后的CRC值，[D256]為256位并行輸入數(shù)據(jù)，[D256256*32]和[C25632*32]為256位數(shù)據(jù)并行時(shí)的參數(shù)矩陣。注意：當(dāng)用MATLAB計(jì)算矩陣時(shí)要將矩陣進(jìn)行奇數(shù)變1，偶數(shù)變0的處理[15-16]。

256位并行數(shù)據(jù)的計(jì)算流程如圖2所示。

4邏輯設(shè)計(jì)

本文以100G以太網(wǎng)中采用的CRC-32計(jì)算為例，該以太網(wǎng)每周期可處理數(shù)據(jù)位寬為256bit，時(shí)鐘頻率可達(dá)400MHz，其邏輯設(shè)計(jì)結(jié)構(gòu)如圖3所示。

在一個(gè)時(shí)鐘周期內(nèi)，輸入256bit待處理數(shù)據(jù)。根據(jù)信號(hào)szin、sop對(duì)數(shù)據(jù)進(jìn)行前補(bǔ)零、字節(jié)高低位翻轉(zhuǎn)等預(yù)處理操作。將處理結(jié)束的數(shù)據(jù)送入計(jì)算模塊，得到第一步計(jì)算數(shù)據(jù)crc_s1，并將crc_s1作為下一輸入的參數(shù)值進(jìn)行迭代。當(dāng)eop信號(hào)有效時(shí)表示輸入計(jì)算結(jié)束，對(duì)此時(shí)得到的crc_s1進(jìn)行翻轉(zhuǎn)，取反操作即得到輸入CRC碼。

5仿真驗(yàn)證

為了驗(yàn)證矩陣計(jì)算的正確性，使用傳統(tǒng)串行計(jì)算和矩陣計(jì)算的方法對(duì)相同的輸入值進(jìn)行編碼，在Modalism SE-64搭建的平臺(tái)上進(jìn)行仿真驗(yàn)證，再將兩者的仿真結(jié)果進(jìn)行對(duì)比。由仿真波形可以看出，當(dāng)輸入值為63時(shí)，利用矩陣計(jì)算的CRC值為32xec7dd02d，而使用傳統(tǒng)串行計(jì)算最后的結(jié)果值也為32xec7dd02d。另外選取不同輸入值進(jìn)行校驗(yàn)，皆可得到相同的結(jié)果，說明矩陣計(jì)算的方法是正確的。

說明：圖4中clk為時(shí)鐘信號(hào)，din為當(dāng)前的輸入值，crc為計(jì)算結(jié)果。由于使用矩陣法可一次處理256位數(shù)據(jù)，所以可單周期完成運(yùn)算。圖5中data為總輸入值，din為當(dāng)前輸入值，一個(gè)時(shí)鐘周期輸入1比特的0或1。

注意：在本次使用矩陣法和串行方式對(duì)輸入值進(jìn)行計(jì)算時(shí)均沒有加入數(shù)據(jù)預(yù)處理和結(jié)果處理部分，僅為驗(yàn)證相同輸入情況下矩陣計(jì)算的正確性。

6結(jié)論

本文介紹了CRC并行和串行兩種實(shí)現(xiàn)方式，并分析了如今主流高位寬并行算法的特點(diǎn)，然后基于4位并行數(shù)據(jù)的矩陣算法，通過反復(fù)迭代得到可應(yīng)用于高位寬輸入的計(jì)算矩陣。利用本文的思想和方法可以方便地得出不同的并行度下的CRC計(jì)算矩陣，并應(yīng)用到不同場(chǎng)合的數(shù)據(jù)校驗(yàn)中。本文以256位數(shù)據(jù)并行為例，用硬件描述語言對(duì)算法進(jìn)行硬件實(shí)現(xiàn)并搭建驗(yàn)證環(huán)境。仿真驗(yàn)證結(jié)果表明，在時(shí)鐘頻率為400MHz情況下，數(shù)據(jù)吞吐量可達(dá)到100Gb/s，本文的思想和方法能夠滿足100G以太網(wǎng)中高速網(wǎng)絡(luò)通信中進(jìn)行CRC計(jì)算校驗(yàn)的要求。

參考文獻(xiàn)：

[1] 夏忠海，任勇峰，賈興中，等.基于FPGA的CRC查表法設(shè)計(jì)及優(yōu)化[J].電測(cè)與儀表，2017，54（3）：54-59，88.

[2] 楊衛(wèi)平.CRC計(jì)算實(shí)現(xiàn)方法[J].電子技術(shù)與軟件工程，2018（9）：158-159.

[3] 黃麗麗.大數(shù)據(jù)背景下的計(jì)算機(jī)網(wǎng)絡(luò)安全探討[J].電腦知識(shí)與技術(shù)，2021，17（23）：38-39.

[4] 姚威.循環(huán)冗余校驗(yàn)碼并行算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)與數(shù)字工程，2006，34（9）：112-114.

[5] 周凱，田楓，李愛國(guó).基于查表法CRC檢錯(cuò)碼改進(jìn)算法的研究與實(shí)現(xiàn)[J].微型電腦應(yīng)用，2017，33（8）：12-14.

[6] 王濤，屈代明，江濤.降低SCL譯碼錯(cuò)誤的級(jí)聯(lián)極化碼[J].中興通訊技術(shù)，2019，25（1）：5-11.

[7] 趙坤鵬，吳龍勝，馬徐瀚，等.一種基于矩陣的并行CRC校驗(yàn)算法[J].電子設(shè)計(jì)工程，2017，25（3）：85-88.

[8] 李永基，魏文軍.基于LFSR的CRC校驗(yàn)碼在FPGA上的實(shí)現(xiàn)[J].蘭州交通大學(xué)學(xué)報(bào)，2015，34（6）：91-94.

[9] Sprachmann M.Automatic generation of parallel CRC circuits[J].IEEE Design & Test ofComputers，2001，18（3）：108-114.

[10] 朱正鵬，朱旭鋒，李賓，等.一種位寬可變的CRC校驗(yàn)算法及硬件實(shí)現(xiàn)[J].航天控制，2019，37（2）：42-48.

[11] Cheng C，Parhi K K.High-speed parallel CRC implementation based on unfolding，pipelining，and retiming[J].IEEE Transactionson Circuits and Systems II：Express Briefs，2006，53（10）：1017-1021.

[12] 張穎，郭志君.10G以太網(wǎng)高速CRC的FPGA實(shí)現(xiàn)與優(yōu)化[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2018（12）：58-60.

[13] Ahmad A，Hayat L.Selection of polynomials for cyclic redundancy check for the use of high speed embedded： an algorithmic procedure[J].WSEAS Transactions on Computers，2011，10（1）：16-20.

[14] 陳基昕，王忠，趙錦宇.基于CAN總線的改進(jìn)CRC校驗(yàn)算法設(shè)計(jì)[J].工業(yè)控制計(jì)算機(jī)，2018，31（5）：37-38.

[15] 時(shí)亞麗.基于FPGA的CRC32校驗(yàn)查找表算法的設(shè)計(jì)[J].山東工業(yè)技術(shù)，2016（10）：215.

[16] 王爽.CAN總線控制器CRC校驗(yàn)碼的設(shè)計(jì)原理及實(shí)現(xiàn)[J].微處理機(jī)，2019，40（3）：25-28.

【通聯(lián)編輯：代影】