千兆以太網中CRC-32的并行實現

田野，佟皓萌

（1.天津理工大學 中環信息學院，天津 300380；2.浙江工業大學 浙江 杭州 310014）

千兆以太網中CRC-32的并行實現

田野1，佟皓萌2

（1.天津理工大學 中環信息學院，天津 300380；2.浙江工業大學 浙江 杭州 310014）

為了保證數據通信的可靠性，要使用一定的檢錯和糾錯方式。循環冗余校驗碼（CRC）作為一種分組碼，具有一定的檢錯功能。以太網傳輸幀中使用的是CRC-32校驗碼作為以太幀的最后4個字節，同以太幀一起傳輸。CRC的實現方式分為串行方式和并行方式，由于并行方式一個時鐘周期內可以處理8個bit，與千兆以太網的GMII接口協議相符合，故千兆以太網的CRC校驗碼的生成和校驗中常使用并行算法實現。本文研究了CRC校驗碼的串行實現算法和并行實現算法，并且用modelsim進行了二者的仿真，比較二者結果的一致性和實現效率，說明了CRC-32校驗碼的并行實現算法更適合使用于千兆以太網中。

循環冗余校驗（CRC）；千兆以太網；并行實現；CRC-32

在數據通信中，為保證傳輸過程中的正確性，需要對通信過程進行差錯控制。而差錯控制最常用的方法是對傳輸的信息序列進行差錯控制編碼，包括各種形式的檢錯碼和糾錯碼。其中按照對信息序列的處理方法不同，檢錯糾錯碼可以分為分組碼和卷積碼兩種。分組碼是指將信息序列分割為k位成一組以后獨立編解碼，分組間無關。卷積碼也是講信息序列分組，不同的是編解碼運算不僅和本組信息有關，而且還與前面若干組有關。按照碼元與原始信息位之間的關系，檢錯糾錯碼又可以分為線性碼與非線性碼。線性碼的所有碼元均是原始信息元的組合，非線性碼的碼元并不都是信息元的線性組合，可能還與前面已編碼的碼元有關[1]。

循環冗余校驗CRC（Cyclic Redundancy Check）碼是由線性分組碼的分支而來，簡稱為循環冗余碼，主要應用是二元碼字[2]。編碼簡單并且誤判概率很低，所以在通信系統中得到了廣泛的應用。循環冗余校驗碼是屬于分組碼中的一類很重要的線性碼，它不僅在理論上有著很好的代數結構，而且它的編碼和譯碼可以通過線性移位寄存器很容易地實現[3]?；谶@個優點，CRC碼在計算機及網絡通信方面得到了廣泛的應用。例如，以太網MAC幀中采用的檢錯算法就是CRC校驗碼。文中研究了CRC校驗碼的串行實現算法和并行實現算法，并且用modelsim進行了二者的仿真，比較二者結果的一致性和實現效率，說明了CRC-32校驗碼的并行實現算法更適合使用于千兆以太網中。

1 以太網的介紹

以太網的國際標準為 IEEE 802.3，以太網最初是由DEC、INTEL和XEROX3家公司共同研制出來的計算機局域網，又簡稱DIX網，后來發展成以太網[4]。其發展經歷了3個階段，即以太網、快速以太網和千兆以太網。如今，人們研究最多的是最新的100 G甚至400 G以太網。以太網MAC幀中采用的檢錯算法就是CRC校驗碼[5]。IEEE802.3規范為實現MAC定義了一套基本的幀數據格式，如圖1所示。

圖1 幀數據格式

各個字段的含義及規定如下[4]：

Preamble（PRE）：報頭。字段中1和 0交替使用，接收方通過該字段知道導入幀，并且該字段提供了同步接收物理層幀接收和導入數據流的方法。

Start-of-frame delimiter（SDF）：幀起始分隔符。字段中1和 0交替使用，結尾是兩個連續的 1，表示下一位是目的地址的第一個自己的第一位。

Destination Address（DA）：目標地址。表示幀準備發往目的MAC地址，共6個字節，可以是單址、多址或全地址，用于識別需要接受幀的目的地。

Source Address（SA）：源地址。用于識別發送幀的源MAC地址，即發送端的網卡地址。

Length/Type：長度/類型。表示包含在幀數據字段中的LLC PDU數據長度，也可以表示幀的類型，該字段用于表示數據字段中包含的高層協議，也就是說，該字段告訴接收設備如何解釋數據字段。

Data：數據。即要傳送的LLC數據，MAC的數據域，是一組 n（46<=n<=1500）字節的任意值序列，如果填入該字段的信息少于46字節，該字段的其余部分也必須進行填充。

Frame check sequence（FCS）：是 32位冗余檢驗碼（CRC）。檢驗除前導、SFD和FCS以外的內容。當發送站發出幀時，一邊發送，一邊逐位進行CRC檢驗。最后形成一個32位CRC檢驗和填在幀尾FCS位置中一起在媒體上傳輸。接收站接收后，從DA開始同樣邊接收邊逐位進行CRC檢驗。最后接收站形成的檢驗和若與幀的檢驗和相同，則表示媒體上傳輸幀未被破壞。反之，接收站認為幀被破壞，則會通過一定的機制要求發送站重發該幀。

IEEE 802.3規范提出媒體無關接口 （Media Independent Interface，MII）來實現，MAC層和不同的物理層（PHY）之間的邏輯連接，如圖2所示。

圖2 MAC層和不同物理層間的邏輯連接

MAC層可以通過媒體無關接口連接不同的物理層[6]。根據對以太網通信速率的要求選擇合適物理接口。針對不同的物理層，媒體無關接口可以以不同的方式實現到 MAC的邏輯連接。例如在10 Mbit/s以太網通信中，媒體無關接口使用4位來串行發送/接收數據流；在100 Mbit/s以太網通信中，媒體無關接口使用4位來串行發送/接收數據流；在 1 000 Mbit/s以太網通信中，媒體無關接口稱作千兆媒體無關接口（GMII），使用8位來串行發送/接收數據流。

2 CRC校驗碼的實現算法理論

CRC碼由一個生成多項式 （最高次冪為k）產生，k次冪的生成多項式可產生k-1位的冗余碼。設TCC數字系統中待校驗的信息碼有n位，M（x）=（mn-1，mn-2，...，m1，m0），將信息碼用多項式M（x）表示:

若生成多項式g（x）的最高次冪為k，則先在式 （1）的兩端乘以Xk，變成:

XkM（x）模2除以g（x），得余數多項式為R（x），即:

余數多項式R（x）可表示為:

將式（2）和式（4）代入式（3），得:

式（5）對應的碼組為n+k位，即:

所得到rk-1，rk-2，…，r1，r0即為校驗位.在接收端，將接收到的n+k位碼 （即M′）除以相同的生成多項式g（x），若產生余數為零或者為一恒定值，就認為接收到的信息正確無誤；否則就認為在傳輸過程中發生了誤碼。

下面介紹CRC的串行移位寄存器的實現，CRC的串行數據輸入計算可以用一個線性反饋移位寄存器 （LFSR）來實現。以CRC-16為例子闡述，其生成多項式為:g（x）=x16+x12+ x5+1，電路結構如圖3所示。

圖3 CRC-16的電路結構圖

當每一個時鐘來臨時輸入1bit數據，經過相應的異或和移位運算，此位數據輸入完畢，再延遲16個時鐘周期，即可得到CRC校驗碼。CRC串行電路優點是電路簡單，但是每一個時鐘脈沖只完成一個比特的計算，這樣就大大的影響了數據的傳輸速率。

串行實現方法電路結構簡單，但是一個時鐘周期只能計算1位數據，效率低下，因此需要引入并行的計算方法，以提高CRC的計算速度。當進行串行運算時，當前的CRC余數值只與信息碼的當前一位的輸入值和前一狀態的余數值有關。若進行并行運算，如8位并行運算，即8位信息碼同時輸入并行運算電路所產生的CRC余數與串行運算時連續8位信息碼相繼輸入串行運算電路所產生的CRC余數相同，則稱這兩種電路是等效的。由此產生出CRC并行計算方法。其運算過程如下：設為移位寄存器狀態值，mi為輸入信息碼序列，i=1，2…為輸入信息碼序號，j=0，1…k-1，為移位寄存器編碼，則：

下面以8位并行輸入為例，推導8位并行計算的CRC-16（其中生成多項式為g（x）=X16+X15+X2+1，即K=16）的邏輯關系式。利用式（7），可遞推出，…，:

則可得表1。

表1 八位并行計算的CRC-16邏輯關系式

上述方法的推導過程雖然是針對8位并行CRC-16運算為例進行的，但這種方法具有通用性，即用這種方法可推導各種CRC生成多項式的各種并行度的并行計算邏輯關系式。

3 CRC-32校驗碼串行實現和并行實現仿真對比

以太網中使用的CRC為CRC-32，其生成多項式為：

G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

下面使用modelsim的仿真圖來比較串行CRC-32和并行CRC-32的一致性。對于串行算法，仿真時，假設輸入一個32位的串行數據為0xaaaaaaaa，功能仿真圖如圖4所示。

圖4 串行實現功能仿真

展開局部如圖5所示。

圖5 串行實現局部仿真

當32位串行數據完全輸入后，此時的CRC[31:0]寄存器中的值就是CRC校驗碼，為100001011111100010010110010100 10。

對于并行算法，數據輸入為8位的并行輸入d[7:0]，在每個clk下并行的輸入8位數，這個是符合千兆以太網GMII時序的。仿真時用到數據與之前串行CRC仿真一致，也是輸入32位數據0xaaaaaaaa，但是這時不是串行的輸入這32位數，而是并行的輸入這32位數，需要4個clk的時間。當最后一個8位數輸入后，在輸出crc_reg[31:0]上便是CRC-32的輸出。并行實現功能仿真如圖6所示。

展開局部看到，得到的CRC-32為100010111111000100 1011001010010，和串行算法得到的結果是一致的，但是只使用了4個時鐘周期，提高了效率，符合以太網GMII接口時序。如圖7所示。

圖6 并行實現功能仿真

圖7 并行實現局部仿真

4 結論

串行實現方法電路結構簡單，但是一個時鐘周期只能計算一位數據，效率低下。而并行算法參照仿真結果來看，得到的結果一致，可是時間卻提高了8倍，這便是并行算法的優勢所在。而并行算法的最重要的優勢是它的輸入符合以太網GMII總線要求，為每個時鐘周期輸入8bit，所以并行算法才可以真正用到以太網的應用中。

[1]曹雪虹，張宗橙.信息論與編碼[M].北京：清華大學出版社，2009.

[2]廖海紅，吳文禮.通信系統中的CRC算法的研究和工程實現[M].北京：北京郵電大學，2009.

[3]朱榮華.一種CRC并行計算原理及實現方法[J].電子學報，2009，1（4）:204-206.

[4]胡昊，李毅超，張運林.用FPGA實現以太網控制器[M].成都：成都電子科技大學，2010.

[5]程鵬，張剛.基于FPGA的10M/100M以太網控制器的設計[M].太原：太原理工大學，2012.

[6]聶真理，李秀琴，李嘯.計算機網絡基礎教程[M].北京：北京工業大學出版社，2009.

Parallel implementation of CRC-32 in Gigabit Ethernet

TIAN Ye1，TONG Hao-meng2
（1.Zhonghuan Information College，Tianjin University of Technology，Tianjin 300380，China；2.Zhejiang University of Technology，Hangzhou 310014，China）

In order to ensure the reliability of data communication，the certain error detection and error correction mode must be used.Cyclic redundancy check code（CRC）as a kind of block code，has a certain function of error detection.The CRC-32 check code is used in the last 4 bytes of frame along with the Ethernet frame transmission.CRC realization methods are classified into serial and parallel，due to the parallel mode can handle 8 bits in a clock cycle，and it is in line with Gigabit Ethernet GMII interface protocol，so the generation and validation of Gigabit Ethernet CRC check code often use parallel algorithm.This paper studied CRC serial algorithm and parallel algorithm，and conducted simulation of the two using Modelsim.The consistency and efficiency of the two are compared，and the parallel implementation of the CRC-32 check code is more suitable for Gigabit Ethernet.

cyclic redundancy check code；gigabit ethernet；parallel implementation；CRC-32

TN911

A

1674－6236（2016）15-0112-03

2015-07-24 稿件編號：201507161

田 野（1984—），女，天津人，碩士，講師。研究方向：單片機、信息論與編碼。