大位寬情況下的回滾式循環(huán)冗余校驗算法

羅 宇 郭家松

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

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

1 概述

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

隨著數(shù)據(jù)通信帶寬的不斷提升，受器件工作頻率的限制，器件內(nèi)部的數(shù)據(jù)位寬也越來越寬，以以太網(wǎng)硬件為例，早期千兆以太網(wǎng)的時候，理論帶寬只有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，才可以達到百G以太網(wǎng)的理論帶寬。

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

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

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

但是在大位寬并行輸入的情況下，又引入了一個問題：那就是報文尾計算的問題。

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

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

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

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

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

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

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

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

2 CRC回滾計算的思路

因為傳統(tǒng)實現(xiàn)方案的缺陷，可以以一種新的算法來代替原有的算法。

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

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

則可以表示為運算式

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

式(1)簡化寫做

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

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

式(3)可簡化寫做

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

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

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

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

2.2 二進制運算的矩陣求逆

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

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

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

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

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

為了避免繁瑣枯燥而易錯的手工矩陣運算，在這里，我們采用的開源的數(shù)學工具Maxima進行矩陣運算。

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

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

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

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

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

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

用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算法的硬件實現(xiàn)

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

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

圖3 1 bit運算矩陣

圖4 8 bit運算矩陣

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

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

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

圖5 8 bit逆運算矩陣

圖6 硬件實現(xiàn)

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

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

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

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

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

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

5 實驗數(shù)據(jù)

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

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

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

實驗環(huán)境如表1所列。

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

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

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

6 結(jié)論

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

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

表1 實驗環(huán)境

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