田野，佟皓萌

（1.天津理工大學(xué) 中環(huán)信息學(xué)院，天津 300380；2.浙江工業(yè)大學(xué) 浙江 杭州 310014）

千兆以太網(wǎng)中CRC-32的并行實(shí)現(xiàn)

田野1，佟皓萌2

（1.天津理工大學(xué) 中環(huán)信息學(xué)院，天津 300380；2.浙江工業(yè)大學(xué) 浙江 杭州 310014）

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

循環(huán)冗余校驗(yàn)（CRC）；千兆以太網(wǎng)；并行實(shí)現(xiàn)；CRC-32

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

循環(huán)冗余校驗(yàn)CRC（Cyclic Redundancy Check）碼是由線性分組碼的分支而來，簡(jiǎn)稱為循環(huán)冗余碼，主要應(yīng)用是二元碼字[2]。編碼簡(jiǎn)單并且誤判概率很低，所以在通信系統(tǒng)中得到了廣泛的應(yīng)用。循環(huán)冗余校驗(yàn)碼是屬于分組碼中的一類很重要的線性碼，它不僅在理論上有著很好的代數(shù)結(jié)構(gòu)，而且它的編碼和譯碼可以通過線性移位寄存器很容易地實(shí)現(xiàn)[3]。基于這個(gè)優(yōu)點(diǎn)，CRC碼在計(jì)算機(jī)及網(wǎng)絡(luò)通信方面得到了廣泛的應(yīng)用。例如，以太網(wǎng)MAC幀中采用的檢錯(cuò)算法就是CRC校驗(yàn)碼。文中研究了CRC校驗(yàn)碼的串行實(shí)現(xiàn)算法和并行實(shí)現(xiàn)算法，并且用modelsim進(jìn)行了二者的仿真，比較二者結(jié)果的一致性和實(shí)現(xiàn)效率，說明了CRC-32校驗(yàn)碼的并行實(shí)現(xiàn)算法更適合使用于千兆以太網(wǎng)中。

1 以太網(wǎng)的介紹

以太網(wǎng)的國(guó)際標(biāo)準(zhǔn)為 IEEE 802.3，以太網(wǎng)最初是由DEC、INTEL和XEROX3家公司共同研制出來的計(jì)算機(jī)局域網(wǎng)，又簡(jiǎn)稱DIX網(wǎng)，后來發(fā)展成以太網(wǎng)[4]。其發(fā)展經(jīng)歷了3個(gè)階段，即以太網(wǎng)、快速以太網(wǎng)和千兆以太網(wǎng)。如今，人們研究最多的是最新的100 G甚至400 G以太網(wǎng)。以太網(wǎng)MAC幀中采用的檢錯(cuò)算法就是CRC校驗(yàn)碼[5]。IEEE802.3規(guī)范為實(shí)現(xiàn)MAC定義了一套基本的幀數(shù)據(jù)格式，如圖1所示。

圖1 幀數(shù)據(jù)格式

各個(gè)字段的含義及規(guī)定如下[4]：

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

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

Destination Address（DA）：目標(biāo)地址。表示幀準(zhǔn)備發(fā)往目的MAC地址，共6個(gè)字節(jié)，可以是單址、多址或全地址，用于識(shí)別需要接受幀的目的地。

Source Address（SA）：源地址。用于識(shí)別發(fā)送幀的源MAC地址，即發(fā)送端的網(wǎng)卡地址。

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

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

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

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

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

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

2 CRC校驗(yàn)碼的實(shí)現(xiàn)算法理論

CRC碼由一個(gè)生成多項(xiàng)式 （最高次冪為k）產(chǎn)生，k次冪的生成多項(xiàng)式可產(chǎn)生k-1位的冗余碼。設(shè)TCC數(shù)字系統(tǒng)中待校驗(yàn)的信息碼有n位，M（x）=（mn-1，mn-2，...，m1，m0），將信息碼用多項(xiàng)式M（x）表示:

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

XkM（x）模2除以g（x），得余數(shù)多項(xiàng)式為R（x），即:

余數(shù)多項(xiàng)式R（x）可表示為:

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

式（5）對(duì)應(yīng)的碼組為n+k位，即:

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

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

圖3 CRC-16的電路結(jié)構(gòu)圖

當(dāng)每一個(gè)時(shí)鐘來臨時(shí)輸入1bit數(shù)據(jù)，經(jīng)過相應(yīng)的異或和移位運(yùn)算，此位數(shù)據(jù)輸入完畢，再延遲16個(gè)時(shí)鐘周期，即可得到CRC校驗(yàn)碼。CRC串行電路優(yōu)點(diǎn)是電路簡(jiǎn)單，但是每一個(gè)時(shí)鐘脈沖只完成一個(gè)比特的計(jì)算，這樣就大大的影響了數(shù)據(jù)的傳輸速率。

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

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

則可得表1。

表1 八位并行計(jì)算的CRC-16邏輯關(guān)系式

上述方法的推導(dǎo)過程雖然是針對(duì)8位并行CRC-16運(yùn)算為例進(jìn)行的，但這種方法具有通用性，即用這種方法可推導(dǎo)各種CRC生成多項(xiàng)式的各種并行度的并行計(jì)算邏輯關(guān)系式。

3 CRC-32校驗(yàn)碼串行實(shí)現(xiàn)和并行實(shí)現(xiàn)仿真對(duì)比

以太網(wǎng)中使用的CRC為CRC-32，其生成多項(xiàng)式為：

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

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

圖4 串行實(shí)現(xiàn)功能仿真

展開局部如圖5所示。

圖5 串行實(shí)現(xiàn)局部仿真

當(dāng)32位串行數(shù)據(jù)完全輸入后，此時(shí)的CRC[31:0]寄存器中的值就是CRC校驗(yàn)碼，為100001011111100010010110010100 10。

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

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

圖6 并行實(shí)現(xiàn)功能仿真

圖7 并行實(shí)現(xiàn)局部仿真

4 結(jié)論

串行實(shí)現(xiàn)方法電路結(jié)構(gòu)簡(jiǎn)單，但是一個(gè)時(shí)鐘周期只能計(jì)算一位數(shù)據(jù)，效率低下。而并行算法參照仿真結(jié)果來看，得到的結(jié)果一致，可是時(shí)間卻提高了8倍，這便是并行算法的優(yōu)勢(shì)所在。而并行算法的最重要的優(yōu)勢(shì)是它的輸入符合以太網(wǎng)GMII總線要求，為每個(gè)時(shí)鐘周期輸入8bit，所以并行算法才可以真正用到以太網(wǎng)的應(yīng)用中。

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

[2]廖海紅，吳文禮.通信系統(tǒng)中的CRC算法的研究和工程實(shí)現(xiàn)[M].北京：北京郵電大學(xué)，2009.

[3]朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法[J].電子學(xué)報(bào)，2009，1（4）:204-206.

[4]胡昊，李毅超，張運(yùn)林.用FPGA實(shí)現(xiàn)以太網(wǎng)控制器[M].成都：成都電子科技大學(xué)，2010.

[5]程鵬，張剛.基于FPGA的10M/100M以太網(wǎng)控制器的設(shè)計(jì)[M].太原：太原理工大學(xué)，2012.

[6]聶真理，李秀琴，李嘯.計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)教程[M].北京：北京工業(yè)大學(xué)出版社，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 稿件編號(hào)：201507161

田 野（1984—），女，天津人，碩士，講師。研究方向：?jiǎn)纹瑱C(jī)、信息論與編碼。