大位寬情況下的回滾式循環冗余校驗算法

羅 宇 郭家松

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

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

1 概述

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

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

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

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

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

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

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

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

圖1 報文尾有無效字節

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

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

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

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

文獻[15,16]中提供了一種級聯結構的實現方式，可以在10 Gbit以太網情況下比較經濟地完成CRC校驗功能，但是在更大位寬的100 Gbit以太網中，依然存在級聯級數多，時延不均衡的問題。

2 CRC回滾計算的思路

因為傳統實現方案的缺陷，可以以一種新的算法來代替原有的算法。

2.1 數據回滾

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

則可以表示為運算式

圖2 傳統實現

式(1)簡化寫做

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

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

式(3)可簡化寫做

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

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

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

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

2.2 二進制運算的矩陣求逆

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

數據：只有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。

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

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

要計算8 bit的全0數據輸入的運算矩陣A1，首先構造1 bit的0數據輸入運算矩陣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轉換成二進制構成矩陣的第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)，再經過二值化處理，得到圖4的運算矩陣：A1=Ab^^8。

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

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

然后根據反運算矩陣來實現回滾模塊：

對回滾模塊輸出值CRC_rb(“rb”為rollback的簡寫)的每個bit，只要看矩陣A1-1對應的列(最左列對應bit31，最右列對應bit0)里哪些行不為0，將回滾模塊輸入CRC的對應bit(最上行對應bit31，最下行對應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算法的硬件實現

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

把末尾的無效輸入字節都強制設置成0，這在設計上很容易實現。一般采用與門掩碼處理的邏輯結構。

圖3 1 bit運算矩陣

圖4 8 bit運算矩陣

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

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

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

圖5 8 bit逆運算矩陣

圖6 硬件實現

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

4 回滾算法的優勢

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

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

回滾算法的CRC運算的構成如圖8所示。

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

5 實驗數據

圖7 傳統實現方式

圖8 回滾實現方式

以上一節的512 bit數據位寬輸入，主頻200 MHz的CRC32運算模塊為實驗對象，用完全相同的硬件/軟件開發平臺，在完全相同的FPGA器件上，實驗傳統算法和回滾算法兩種不同的實現方式。

實驗環境如表1所列。

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

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

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

6 結論

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

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

表1 實驗環境

表2 傳統算法與回滾算法對比