羅 宇 郭家松

①(北京交通大學(xué)經(jīng)濟(jì)管理學(xué)院 北京 100044)

②(北京交通大學(xué)離退休干部處 北京 100044)

1 概述

循環(huán)冗余校驗(yàn)( Cyclic Redundancy Check,CRC)易于實(shí)現(xiàn)，且具有較優(yōu)的誤碼檢錯(cuò)能力和抗干擾性能被廣泛應(yīng)用于高速網(wǎng)絡(luò)的差錯(cuò)控制中[1]，以太網(wǎng)，ATM, PCIe, PON和OTN等數(shù)據(jù)通信協(xié)議中都使用了CRC算法。CRC還可以和其它編碼技術(shù)結(jié)合，例如LDPC碼與Polar碼，形成新的編碼技術(shù)[2]。CRC校驗(yàn)需要對(duì)每個(gè)報(bào)文的全部內(nèi)容進(jìn)行數(shù)據(jù)校驗(yàn)，運(yùn)算頻繁，為了不影響吞吐量和轉(zhuǎn)發(fā)速度，一般都是采用硬件算法實(shí)現(xiàn)[3]。通常采用異或門邏輯算法[4]，或者查表算法[5]。

隨著數(shù)據(jù)通信帶寬的不斷提升，受器件工作頻率的限制，器件內(nèi)部的數(shù)據(jù)位寬也越來越寬，以以太網(wǎng)硬件為例，早期千兆以太網(wǎng)的時(shí)候，理論帶寬只有1000 Mbps，如果主頻是125 MHz的話，數(shù)據(jù)位寬只要8 bit就夠了(1000/125=8)。而現(xiàn)在100 Gbit以太網(wǎng)已經(jīng)普及，在這種情況下，即使工作頻率提升到400 MHz，數(shù)據(jù)位寬也需要增加到256 bit，才可以達(dá)到百G以太網(wǎng)的理論帶寬。

CRC算法也從串行實(shí)現(xiàn)變成了并行實(shí)現(xiàn)，CRC校驗(yàn)算法可以通過遞推的方法從串行形式推導(dǎo)出并行形式[6]。

查表法CRC雖然可以比較簡單地提高運(yùn)算性能[7]，但是需要占用存儲(chǔ)單元，占用空間隨著位寬加大指數(shù)上升，因此需要用邏輯門算法。

隨著輸入位寬的不斷提升，CRC并行運(yùn)算的要求也越來越高。對(duì)于并行邏輯門CRC的算法，在文獻(xiàn)[8,9]中，給出了多種實(shí)現(xiàn)方案。并行數(shù)據(jù)位寬加大的情況下，也帶來了邏輯門級(jí)數(shù)增多，延時(shí)加大，限制工作頻率的問題，不過可以通過加流水線(pipeline)優(yōu)化的方式[10]或分段運(yùn)算-拼接[11]來解決。

但是在大位寬并行輸入的情況下，又引入了一個(gè)問題：那就是報(bào)文尾計(jì)算的問題。

問題的引出是這樣的：數(shù)據(jù)報(bào)文的長度都是整數(shù)字節(jié)的，但是報(bào)文長度的總字節(jié)數(shù)是不固定的。在8 bit數(shù)據(jù)位寬時(shí)，因?yàn)閳?bào)文長度是整數(shù)字節(jié)，所以每次CRC計(jì)算的輸入數(shù)據(jù)長度是固定的8 bit；但是在更大位寬情況下，報(bào)文的最后一拍有效數(shù)據(jù)位數(shù)是不定的，存在末尾的某些字節(jié)無效的情況，這也就導(dǎo)致做CRC運(yùn)算時(shí)最后一拍的輸入數(shù)據(jù)位寬是不定的。

以32 bit(4 Byte)的位寬為例，如圖1所示，一個(gè)長度為18 Byte的報(bào)文，需要傳輸5個(gè)時(shí)鐘周期。前4個(gè)周期里，每周期有4 Byte有效數(shù)據(jù)，最后一周期，只有2 Byte有效數(shù)據(jù)。

圖1 報(bào)文尾有無效字節(jié)

CRC算法需要對(duì)整個(gè)報(bào)文做校驗(yàn)，所以前4個(gè)周期里，每個(gè)周期計(jì)算4 Byte，最后一周期，只計(jì)算2 Byte，而末尾的2 Byte無效字節(jié)是不被計(jì)算的。因此最后一周期，CRC算法模塊輸入數(shù)據(jù)位數(shù)和前4周期是不一樣的。隨著報(bào)文長度的變化，最后一周期的輸入位寬有4種可能(1～3 Byte)。

文獻(xiàn)[12]提供了一種可變數(shù)據(jù)位寬的CRC運(yùn)算方法，可以靈活的處理不同輸入數(shù)據(jù)位寬的CRC運(yùn)算。但是此種變位寬CRC運(yùn)算是串行的，一個(gè)時(shí)鐘周期只能處理1 bit，而我們要求的處理速度是在一個(gè)時(shí)鐘周期內(nèi)處理完數(shù)據(jù)位寬的所有bit。此算法性能遠(yuǎn)遠(yuǎn)不能滿足要求。

為應(yīng)對(duì)上述情況，在常規(guī)的設(shè)計(jì)實(shí)現(xiàn)中，需要放置多個(gè)不同CRC算法模塊，對(duì)應(yīng)不同字節(jié)的輸入位寬，然后根據(jù)最后一周期的實(shí)際有效數(shù)據(jù)個(gè)數(shù)，選擇相應(yīng)模塊的輸出作為最終的CRC校驗(yàn)值[13,14]。很多設(shè)計(jì)都采用了這種方法來解決尾部數(shù)據(jù)變長的問題，例如文獻(xiàn)[13]和文獻(xiàn)[14]，其CRC部分實(shí)現(xiàn)如圖2，圖中的數(shù)據(jù)位寬是64 bit(8 Byte)，是個(gè)標(biāo)準(zhǔn)的常規(guī)設(shè)計(jì)。

這樣的傳統(tǒng)實(shí)現(xiàn)方式消耗資源較多，在位寬不很大的情況下(如4 Byte, 8 Byte)還可以接受，但是在更大數(shù)據(jù)位寬情況下，如32 Byte及以上，會(huì)消耗大量的邏輯資源，處理帶寬越高，數(shù)據(jù)位寬也就越寬，這樣的資源消耗也就越嚴(yán)重。

文獻(xiàn)[15,16]中提供了一種級(jí)聯(lián)結(jié)構(gòu)的實(shí)現(xiàn)方式，可以在10 Gbit以太網(wǎng)情況下比較經(jīng)濟(jì)地完成CRC校驗(yàn)功能，但是在更大位寬的100 Gbit以太網(wǎng)中，依然存在級(jí)聯(lián)級(jí)數(shù)多，時(shí)延不均衡的問題。

2 CRC回滾計(jì)算的思路

因?yàn)閭鹘y(tǒng)實(shí)現(xiàn)方案的缺陷，可以以一種新的算法來代替原有的算法。

2.1 數(shù)據(jù)回滾

CRC運(yùn)算是通過輸入數(shù)據(jù)和上一次的CRC結(jié)果數(shù)據(jù)做異或運(yùn)算得到的，是一種線性運(yùn)算，可以用矩陣的方式來表示[11]，例如一個(gè)輸入數(shù)據(jù)位寬為8 bit(1 Byte)的CRC32運(yùn)算模塊，輸入變量有2個(gè)：8 bit輸入數(shù)據(jù)D, 32 bit的上一次運(yùn)算值CRC32-1；輸出變量有1個(gè)：32 bit輸出值CRC32，這些變量都以向量的方式表示：CRC32=[c31c30··· c1c0],D =[d7d6··· d1d0],CRC32-1=[cl31cl30···cl1cl0] 。

則可以表示為運(yùn)算式

圖2 傳統(tǒng)實(shí)現(xiàn)

式(1)簡化寫做

A是一個(gè)40行32列的矩陣，是CRC算法的生成矩陣，是一個(gè)常數(shù)矩陣。

對(duì)于一個(gè)M Byte輸入數(shù)據(jù)位寬的CRC運(yùn)算模塊，在最后一周期的CRC運(yùn)算中，如果M Byte中的最后n Byte是無效數(shù)據(jù)，而我們依然把所有數(shù)據(jù)都輸入給CRC算法模塊，那么計(jì)算的結(jié)果肯定是錯(cuò)的。這個(gè)錯(cuò)誤的CRC32值(記作CRC32E)，是正確的CRC32值(記作CRC32C)在多計(jì)算了末尾的n個(gè)無效數(shù)據(jù)字節(jié)后得到的。如果通過某種運(yùn)算，把這n個(gè)無效數(shù)據(jù)字節(jié)逆運(yùn)算回去，就能得到正確的CRC32C值。因?yàn)镃RC運(yùn)算是矩陣運(yùn)算，我們首先想到的逆運(yùn)算方法就是逆矩陣。但是式(2)中的運(yùn)算矩陣A不是方陣，不存在逆矩陣。不過如果在計(jì)算CRC32E時(shí)，令末尾的無效數(shù)據(jù)字節(jié)D為全0(這在設(shè)計(jì)中很容易實(shí)現(xiàn))：D=[0 0 ··· 0 0]。將其代入式(1)后，式(1)可以變?yōu)?/p>

式(3)可簡化寫做

式(4)中A1是一個(gè)32行32列的方陣，可能存在逆矩陣。

此時(shí)，對(duì)于上述包含n個(gè)末尾無效字節(jié)(已令其為全0)數(shù)據(jù)的CRC運(yùn)算，可以表示為

式(5)中，矩陣A1的數(shù)量為n個(gè)。

這樣的話，就可以通過逆矩陣反運(yùn)算得到正確的CRC32C：CRC32E·A1-1·A1-1· ··· ·A1-1=(CRC32C·A1·A1 · ··· · A1)·A1-1·A1-1· ··· ·A1-1=CRC32C

2.2 二進(jìn)制運(yùn)算的矩陣求逆

CRC算法中，采用的都是二進(jìn)制的布爾運(yùn)算，算法中都是線性運(yùn)算，即只涉及到加法和乘法，但布爾運(yùn)算和普通的數(shù)學(xué)運(yùn)算有一些不同：

數(shù)據(jù)：只有0和1兩個(gè)值；

加法：0+0=0, 0+1=1, 1+0=1, 1+1=0；

乘法：0×0=0, 0×1=0, 1×0=0, 1×1=1。

可以看出，只有布爾運(yùn)算的加法和普通的數(shù)學(xué)運(yùn)算不同，只要做一些小調(diào)整，就可以使用常規(guī)的方法完成布爾矩陣的運(yùn)算。算得的結(jié)果中，只需要把結(jié)果進(jìn)行二值化處理，即：奇數(shù)都變成1，偶數(shù)都變成0就行了。

為了避免繁瑣枯燥而易錯(cuò)的手工矩陣運(yùn)算，在這里，我們采用的開源的數(shù)學(xué)工具M(jìn)axima進(jìn)行矩陣運(yùn)算。

要計(jì)算8 bit的全0數(shù)據(jù)輸入的運(yùn)算矩陣A1，首先構(gòu)造1 bit的0數(shù)據(jù)輸入運(yùn)算矩陣Ab：CRC32=CRC32-1·AbCRC32的生成多項(xiàng)式為：G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1[10]；可以寫成0x104C11DB7。把0x104C11DB7轉(zhuǎn)換成二進(jìn)制構(gòu)成矩陣的第1行；然后把元素(2, 1), (3, 2), (4, 3), (5, 6), ··· , (32,31)置為1，形成一條斜線；其它元素為全0[17]。得到矩陣Ab，如圖3所示。

1 bit的運(yùn)算矩陣Ab乘8次方即得到8 bit的運(yùn)算矩陣A1。通過Maxima工具，對(duì)矩陣Ab點(diǎn)乘8次后(矩陣乘8次方在Maxima中的運(yùn)算符為^^8)，再經(jīng)過二值化處理，得到圖4的運(yùn)算矩陣：A1=Ab^^8。

最后，對(duì)A1矩陣求逆(矩陣求逆在Maxima中的運(yùn)算符為^^-1)，再經(jīng)過二值化處理后，得到圖5的逆運(yùn)算矩陣：A1-1=A1^^-1。

至此，我們得到了8 bit的全0數(shù)據(jù)輸入時(shí)的反運(yùn)算矩陣。

然后根據(jù)反運(yùn)算矩陣來實(shí)現(xiàn)回滾模塊：

對(duì)回滾模塊輸出值CRC_rb(“rb”為rollback的簡寫)的每個(gè)bit，只要看矩陣A1-1對(duì)應(yīng)的列(最左列對(duì)應(yīng)bit31，最右列對(duì)應(yīng)bit0)里哪些行不為0，將回滾模塊輸入CRC的對(duì)應(yīng)bit(最上行對(duì)應(yīng)bit31，最下行對(duì)應(yīng)bit0)加到異或運(yùn)算中即可。

用Verilog HDL代碼表示為crc_rb[31]= crc[7]^ crc[6] ^ crc[4] ^ crc[2] ^ crc[0];crc_rb[30]=crc[6] ^ crc[5] ^ crc[3] ^ crc[1]; ···crc_rb[0] =crc[8] ^ crc[7] ^ crc[5] ^ crc[3] ^ crc[1]。

3 CRC算法的硬件實(shí)現(xiàn)

有了回滾運(yùn)算邏輯模塊，CRC運(yùn)算硬件實(shí)現(xiàn)就比較簡單了，邏輯框圖如圖6。

把末尾的無效輸入字節(jié)都強(qiáng)制設(shè)置成0，這在設(shè)計(jì)上很容易實(shí)現(xiàn)。一般采用與門掩碼處理的邏輯結(jié)構(gòu)。

圖3 1 bit運(yùn)算矩陣

圖4 8 bit運(yùn)算矩陣

如果最后一個(gè)周期里，只有末尾1個(gè)字節(jié)是無效的，就把這個(gè)無效字節(jié)設(shè)置成0，然后依然按照完整的全位寬計(jì)算CRC，此時(shí)得到的結(jié)果就是CRC32E，即正確的結(jié)果CRC32C再多計(jì)算了一個(gè)全0的數(shù)據(jù)字節(jié)。

然后用這個(gè)CRC結(jié)果通過1 Byte回滾運(yùn)算模塊，進(jìn)行回滾運(yùn)算，最終得到的就是正確的CRC計(jì)算值。

如果末尾存在n個(gè)字節(jié)的無效數(shù)據(jù)，則需要重復(fù)回滾運(yùn)算n次。在硬件實(shí)現(xiàn)上為了避免多次迭代操作影響處理速度，一般都會(huì)例化多個(gè)不同的回滾運(yùn)算模塊，每個(gè)回滾運(yùn)算模塊對(duì)應(yīng)不同的回滾字節(jié)數(shù)。通過后再用選擇器選擇對(duì)應(yīng)的回滾運(yùn)算模塊輸出。

圖5 8 bit逆運(yùn)算矩陣

圖6 硬件實(shí)現(xiàn)

這些不同回滾字節(jié)的回滾模塊，其對(duì)應(yīng)的矩陣也是不同的，可以用1 Byte反運(yùn)算矩陣A1-1通過乘方的方式簡單的算出來。

4 回滾算法的優(yōu)勢

以一個(gè)200 MHz主頻，512 bit(64 Byte)的100 Gbit以太網(wǎng)設(shè)計(jì)為例，在傳統(tǒng)設(shè)計(jì)實(shí)現(xiàn)中，其CRC運(yùn)算需要使用64個(gè)不同輸入位寬的模塊，如圖7所示。

對(duì)于一個(gè)64 Byte位寬輸入的CRC運(yùn)算模塊；其輸入數(shù)據(jù)為64 Byte的數(shù)據(jù)加上32 bit的上一次CRC結(jié)果，總共是544 bit輸入，32 bit輸出，運(yùn)算邏輯是一個(gè)544×32的矩陣線性運(yùn)算；一個(gè)63 Byte的運(yùn)算模塊的輸入為536 bit，輸出為32 bit，運(yùn)算邏輯是一個(gè)536×32的矩陣線性運(yùn)算；以此類推，最簡單的1 Byte運(yùn)算模塊輸入為40 bit，輸出為32 bit，運(yùn)算邏輯是一個(gè)40×32的矩陣線性運(yùn)算。

回滾算法的CRC運(yùn)算的構(gòu)成如圖8所示。

回滾式CRC算法里也包括了64個(gè)運(yùn)算模塊，包括1個(gè)64 Byte輸入的CRC運(yùn)算模塊和63個(gè)回滾運(yùn)算模塊。其中64 Byte輸入的CRC運(yùn)算模塊和常規(guī)CRC算法中的對(duì)應(yīng)子模塊相同，但回滾運(yùn)算模塊的就簡單多了，每個(gè)回滾運(yùn)算模塊都是32 bit輸入32 bit輸出，運(yùn)算邏輯為32×32的矩陣線性運(yùn)算；和常規(guī)算法相比，比其中最簡單的40×32的矩陣線性運(yùn)算還簡單。因此總體實(shí)現(xiàn)就更是簡單得多。

5 實(shí)驗(yàn)數(shù)據(jù)

圖7 傳統(tǒng)實(shí)現(xiàn)方式

圖8 回滾實(shí)現(xiàn)方式

以上一節(jié)的512 bit數(shù)據(jù)位寬輸入，主頻200 MHz的CRC32運(yùn)算模塊為實(shí)驗(yàn)對(duì)象，用完全相同的硬件/軟件開發(fā)平臺(tái)，在完全相同的FPGA器件上，實(shí)驗(yàn)傳統(tǒng)算法和回滾算法兩種不同的實(shí)現(xiàn)方式。

實(shí)驗(yàn)環(huán)境如表1所列。

對(duì)比兩種算法下，資源占用情況和軟件運(yùn)行時(shí)間。得到的結(jié)果如下：

邏輯資源占用量，在Altera工具中以ALM(Adaptive Logic Module)數(shù)量為計(jì)量；邏輯綜合耗時(shí)和布線耗時(shí)以秒為單位，兩種算法的對(duì)比數(shù)據(jù)如表2所示。

可以看出，邏輯資源占用方面，回滾算法比傳統(tǒng)算法節(jié)約了85%的ALM占用數(shù)量；在綜合耗時(shí)和布局布線耗時(shí)方面，回滾算法比傳統(tǒng)算法節(jié)約了60%～70%的時(shí)間，優(yōu)勢非常顯著。

6 結(jié)論

針對(duì)傳統(tǒng)的變位寬CRC算法中存在的不足，本文打破常規(guī)，從逆向思維的角度出發(fā)，通過逆運(yùn)算的方式，從可控的錯(cuò)誤數(shù)據(jù)中逆推出正確的數(shù)據(jù)。并利用矩陣運(yùn)算的數(shù)學(xué)工具推導(dǎo)和實(shí)現(xiàn)了算法。

逆運(yùn)算的CRC算法，也就是本文中說的回滾運(yùn)算，在大數(shù)據(jù)位寬輸入情況下，可以解決傳統(tǒng)算法的臃腫低效問題。回滾算法在FPGA上通過了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)不僅證明了回滾算法完全可行，而且可以顯著地節(jié)約資源，降低復(fù)雜度。在512 bit位寬的情況下，回滾算法和傳統(tǒng)算法相比，可以節(jié)約85%左右的ALM邏輯資源；節(jié)約70%的綜合時(shí)間；節(jié)約60%的布局布線時(shí)間。體現(xiàn)出了巨大的優(yōu)勢。

表1 實(shí)驗(yàn)環(huán)境

表2 傳統(tǒng)算法與回滾算法對(duì)比