程桂花， 陳付龍， 齊學梅， 左開中

（1.安徽師范大學數(shù)學計算機科學學院，安徽蕪湖 241002；2.安徽師范大學網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心，安徽蕪湖 241002）

字節(jié)信息流并行CRC－32校驗碼電路設(shè)計與實現(xiàn)

程桂花1， 陳付龍1， 齊學梅1， 左開中2

（1.安徽師范大學數(shù)學計算機科學學院，安徽蕪湖 241002；2.安徽師范大學網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心，安徽蕪湖 241002）

CRC是一種能發(fā)現(xiàn)并糾正信息在存儲和傳輸過程中連續(xù)出現(xiàn)的多位錯誤的校驗編碼.分析CRC碼的校驗原理及特點，推導相鄰字節(jié)間的CRC－32校驗碼的計算方法，利用組合邏輯并行快速計算當前字節(jié)的32位CRC校驗碼，使用Verilog HDL設(shè)計編碼電路，通過FPGA實現(xiàn)CRC－32編碼及檢錯功能.電路不僅可以計算任意長度的字節(jié)信息流的CRC－32校驗碼，還可嵌入到通信傳輸系統(tǒng)中快速并行實現(xiàn)CRC－32的編碼及檢錯運算，保證信息正確可靠地傳輸.

CRC－32；循環(huán)校驗碼；并行CRC－32算法；字節(jié)信息流

引 言

CRC［1］（Cyclic Redundancy Check，循環(huán)冗余碼校驗）是一種能發(fā)現(xiàn)并糾正信息在存儲和傳輸過程中連續(xù)出現(xiàn)的多位錯誤的校驗編碼.CRC碼因?qū)崿F(xiàn)簡單、檢錯能力強而在通信傳輸中得到廣泛應(yīng)用［2，3］，如USB協(xié)議、IEEE 802.3標準、IEEE 802.11標準、RFID協(xié)議等都采用了CRC作為正確性校驗的方法［4］，避免由于信道傳輸特性不理想及其他噪聲的影響而引起的信息位出錯，保證信息正確可靠地傳輸.

CRC碼的計算大都使用硬件電路直接進行［5－10］，目前硬件實現(xiàn)CRC碼計算的方法主要有串行和并行兩種.文獻［6］提出的串行CRC算法，簡單易于實現(xiàn)，但每次只能處理一位的二進制，難以滿足高速應(yīng)用場合；文獻［3－5，8－10］通過分析串行的CRC算法提出的并行CRC算法，核心思想是同時計算8位二進制（字節(jié)）的CRC校驗碼，相對于串行算法效率大大提高.

采用文獻［3－5，9－10］提出的并行CRC算法可得到16位的余數(shù)校驗碼，屬于并行CRC－16算法；利用文獻［8］提出的并行CRC算法可得到32位的余數(shù)校驗碼，屬于并行CRC－32算法，雖然檢錯能力高于并行CRC－16算法，但只討論了單個字節(jié)的并行CRC－32算法；文獻［3］提出的CRC－16算法，雖采用查表（余數(shù)表）法實行并行算法，余數(shù)表需占用存儲空間且影響計算速度，但討論了相鄰字節(jié)間的CRC－16碼的計算方法，綜合兩種算法的優(yōu)點，文中提出基于“字節(jié)信息流并行CRC－32”算法.文中分析CRC碼的校驗原理，并行CRC－32的計算規(guī)則，推導相鄰字節(jié)間的CRC－32校驗碼的計算方法，利用組合邏輯并行快速計算當前字節(jié)的32位CRC校驗碼，設(shè)計基于字節(jié)信息流的并行、高效、快速計算任意長度字節(jié)信息的CRC－32校驗碼運算電路，在Quartus II開發(fā)軟件中仿真，通過FPGA實現(xiàn).

1　CRC算法

CRC碼的計算使用二進制多項式模運算，系數(shù)運算以2為模［11－12］，運算時不考慮進位和借位，模2加減其實質(zhì)是按位執(zhí)行異或運算，模2乘除采用模2加減計算部分積和部分余數(shù).一個二進制位串可以表示為二進制多項式，如二進制串“100011011”的多項式表示為x8＋x4＋x3＋x＋1；反之亦然.

1.1CRC碼的編碼與校驗原理

設(shè)n位信息串mn－1mn－2…m1m0用信息多項式M（x）表示為：

首先，將信息多項式M（x）左移k位，即M（x）xk表示為：

其次，選擇一個k＋1位的生成多項式Gk＋1（x）對M（x）xk作模2除，得到k位的余數(shù)多項式R（x）作為校驗碼，附加到信息位串之后，形成CRC碼字多項式MC（x），表示如下：

從式（1）－（4）計算得到式（5）的過程稱為CRC編碼，多項式MC（x）對應(yīng)的二進制位串稱為CRC碼字，由發(fā)送方向外發(fā)送.

接收方將收到CRC碼字后用相同的生成多項式作模2除，得余數(shù)多項式R′（x），若收到的CRC碼字正確，R′（x）的計算過程表示如下：

若R′（x）為全“0”時，說明接收方收到的CRC碼字是正確的；否則，收到的CRC碼字有錯，根據(jù)余數(shù)的值可推知出錯的二進制位，可以實現(xiàn)糾錯功能，或要求發(fā)送方重新發(fā)送CRC碼字，直到正確為止.

在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常n非常大，由數(shù)千個二進制位構(gòu)成一個信息幀，為檢測信息傳輸正確與否，通常選用的CRC－32的生成多項式［8］如式（7）所示.

1.2字節(jié)信息流的CRC－32算法

假設(shè)：

·生成多項式G33（x）＝x32＋x26＋…＋x2＋x＋I （104C11DB7H）；

·Mi（x）表示第i個字節(jié)；

·字節(jié)信息流Mn－1（x）Mn－2（x）…Mi（x）…M1（x）M0（x）可表示為：

即字節(jié)數(shù)據(jù)流左移32位，再模2除生成多項式G33（x）：

首先，假設(shè)

其次，分析｛Mn－1（x）＊256（n－1）＋Mn－2（x）＊256（n－2）｝＊2564mod G33（x）的余數(shù)R（n－2）（x），分析過程如式（11）

式（11）表明，當前字節(jié)Mn－2（x）的32位CRC校驗碼的計算方法是

第一步，計算上一字節(jié)的CRC校驗碼的最高8位與當前字節(jié)異或后的CRC校驗碼；

第二步，上一字節(jié)的CRC校驗碼左移8位；

第三步，第一、第二步的計算結(jié)果異或得到當前字節(jié)的CRC校驗碼R（n－2）（x）.

重復第一至第三步依次逐個字節(jié)計算CRC校驗碼，直到M0（x）計算得到R0（x）為整個字節(jié)信息流的32位CRC校驗碼.

如，字節(jié)信息流M1（x）M0（x）＝DD9DH，則32位CRC校驗碼R（x）計算過程如下：

采用式（11）不僅可以計算任意長度字節(jié)信息流的32位CRC校驗碼，而且將基于二進制位的32位CRC校驗碼的計算轉(zhuǎn)換為基于字節(jié)的CRC碼的計算，加速CRC碼的運算.

1.3單字節(jié)32位CRC校驗碼并行算法

表1　8位并行CRC－32計算邏輯表達式（“＋”表示異或）

由式（8）可知，字節(jié)信息流的CRC校驗碼運算的本質(zhì)是一個遞推過程［2］，其核心是計算單個字節(jié)的CRC校驗碼，依據(jù)式（1）－（4）采用模2除及代入運算規(guī)則可推導出一種求單字節(jié)的高速并行CRC算法，可利用組合邏輯電路計算一個字節(jié)的32位CRC校驗碼.單個字節(jié)的8位信息多項式系數(shù)m7m6m5m4m3m2m1m0與32位的CRC校驗碼余數(shù)多項式系數(shù)r31r30r29r28r27r26…r3r2r1r0邏輯關(guān)系如表1所示.

2　CRC－32編碼電路設(shè)計與實現(xiàn)

2.1電路設(shè)計

CRC碼的計算使用二進制多項式模運算，運算時不考慮進位和借位，模2加減其實質(zhì)是按位執(zhí)行異或運算，模2乘除采用模2加減計算部分積和部分余數(shù).基于式（11）的字節(jié)信息流CRC碼運算電路結(jié)構(gòu)如圖1所示：電路在時鐘信號的作用下，按如下步驟進行工作：

第一步，當reset信號有效（“0→1→0”），余數(shù)寄存器r始化為全“0”；

第二步，在時鐘信號的上升沿（“↑”），余數(shù)寄存器r高八位與當前輸入的字節(jié)m異或后存入字節(jié)寄存器mx；

第三步，組合邏輯電路按照表1所示的邏輯表達式，并行計算得到字節(jié)的32位CRC校驗碼rx；

圖1　字節(jié)信息流8位并行CRC－32電路結(jié)構(gòu)

第四步，rx的值與余數(shù)寄存器的現(xiàn)態(tài)左移八位后執(zhí)行異或運算，異或結(jié)果在時鐘下降沿（“↓”）的作用下存入余數(shù)寄存器.這樣，在一個時鐘周期內(nèi)可以完成一個字節(jié)的CRC碼的計算.

第五步，重復第二－第四步，直到完成所有字節(jié)的計算，同時輸入信號finish有效（“1→0→1”）表明字節(jié)信息流發(fā)送結(jié)束，利用finish信號的下降沿（“↓”）將余數(shù)寄存器r的值存入輸出寄存器rout中并向外發(fā)送，該值即為輸入的字節(jié)信息流的32位CRC校驗碼.

電路由reset信號啟動，finish信號結(jié)束，使得電路可以計算任意長度的字節(jié)信息流的CRC－32校驗碼；時鐘信號的上升、下降沿的分別驅(qū)動兩個寄存器工作，使得電路在每個時鐘內(nèi)完成一個字節(jié)的CRC－32校驗碼的計算.

2.2邏輯實現(xiàn)

應(yīng)用Verilog HDL語言設(shè)計基于字節(jié)信息流的8位的高速、低功耗的并行CRC－32運算電路，選擇EP2C5Q208CN芯片，在Quartus II開發(fā)工具中配置、綜合和優(yōu)化后通過Quartus II中的Programmer工具下載到芯片中，可以快速穩(wěn)定地實現(xiàn)CRC－32校驗碼的運算操作且占用面積小，達到預(yù)期設(shè)計目標.

EP2CQ208CN是Altera公司推出的CycloneⅡ系列的FPGA，具有低成本、低功耗和高性價比的特點，芯片內(nèi)包含豐富的邏輯單元、可編程寄存器和存儲單元，可以進行大量的邏輯運算，支持寄存器反饋操作，在數(shù)據(jù)傳輸、無線局域網(wǎng)、無線感知網(wǎng)、智能卡系統(tǒng)、汽車等領(lǐng)域得到廣泛應(yīng)用，在相關(guān)應(yīng)用領(lǐng)域可提供快速、低功耗解決方案.

2.3仿真波形

文中設(shè)計基于字節(jié)信息流的高速、低功耗的8位并行CRC－32校驗碼運算電路的Verilog HDL模型，在Altera公司的Quartus II軟件中進行編譯和仿真，用Visual FoxPro語言進行軟件驗證，所有運算結(jié)果完全正確.圖2是不同長度的字節(jié)信息流的CRC校驗碼的仿真波形.

圖2中t1時間段：輸入信息流m由DDH、9DH、CCH、9DH四個字節(jié)組成，每個時鐘周期計算一個字節(jié)的32位的CRC校驗碼，所以時間段t1由4個時鐘周期T1、T2、T3、T4組成.各個時鐘周期電路完成的功能如下：

T1：字節(jié)信息流的起始信號reset在T1時鐘周期的前半周期有效（高有效），完成寄存器的初始化操作；T1時鐘周期的上升沿處字節(jié)寄存器mx接收輸入端數(shù)據(jù)DDH（當前輸入字節(jié)DDH與余數(shù)寄存器r的現(xiàn)態(tài)的高8位00H異或結(jié)果），組合邏輯電路的輸出rx為2056CD3AH（DDH的32位CRC校驗碼）；T1時鐘周期的下升沿處余數(shù)寄存器r接收輸入端數(shù)據(jù)2056CD3AH（rx的值與r現(xiàn)態(tài)左移8位后的值全“0”異或結(jié)果），至此電路完成字節(jié)數(shù)據(jù)流“DDH”的32位CRC校驗碼的計算.

圖2　字節(jié)信息流8位并行CRC－32仿真波形

T2：T2時鐘周期的上升沿處字節(jié)寄存器mx接收輸入端數(shù)據(jù)BDH（當前輸入字節(jié)9DH與余數(shù)寄存器r的現(xiàn)態(tài)的高8位20H異或結(jié)果），組合邏輯電路的輸出rx為8CF30BADH（BDH的32位CRC校驗碼）；T2時鐘周期的下升沿處余數(shù)寄存器r接收輸入端數(shù)據(jù)DA3E31ADH（rx的值與r現(xiàn)態(tài)左移8位后的值“56CD3A00H”異或結(jié)果），至此電路完成字節(jié)數(shù)據(jù)流“DD9DH”的32位CRC校驗碼的計算.

T3：T3時鐘周期的上升沿處字節(jié)寄存器mx接收輸入端數(shù)據(jù)16H（當前輸入字節(jié)CCH與余數(shù)寄存器r的現(xiàn)態(tài)的高8位DAH異或結(jié)果），組合邏輯電路的輸出rx為569796C2H（16H的32位CRC校驗碼）；T3時鐘周期的下升沿處余數(shù)寄存器r接收輸入端數(shù)據(jù)68A63BC2H（rx的值與r現(xiàn)態(tài)左移8位后的值“3E31AD 00H”異或結(jié)果），至此電路完成字節(jié)數(shù)據(jù)流“DD9DCCH”的32位CRC校驗碼的計算.

T4：T4時鐘周期的上升沿處字節(jié)寄存器mx接收輸入端數(shù)據(jù)F5H（當前輸入字節(jié)9DH與余數(shù)寄存器r的現(xiàn)態(tài)的高8位68H異或結(jié)果），組合邏輯電路的輸出rx為9E7D9662H（F5H的32位CRC校驗碼）；T4時鐘周期的下升沿處余數(shù)寄存器r接收輸入端數(shù)據(jù)38465462H（rx的值與r現(xiàn)態(tài)左移8位后的值“A63BC2 00H”異或結(jié)果），至此電路完成字節(jié)數(shù)據(jù)流“DD9DCC9DH”的32位CRC校驗碼的計算.

輸入信號finish收到負脈沖，表明一個字節(jié)信息流輸入結(jié)束，字節(jié)信息流“DD9DCC9DH”的32位校驗碼（38465462H）在此負脈沖的下降沿處存入寄存器rout并附加到數(shù)據(jù)流之后向外發(fā)送，同時電路在reset信號的作用下，又可開始下一個字節(jié)信息流的32位CRC校驗碼的計算，如圖2中t2、t3時間段所示信息.

由圖2可知，一個字節(jié)信息流的CRC－32校驗碼的運算由reset信號（“0→1→0”）啟動、finish信號（“1→0→1”）結(jié)束，這樣安排主要有兩個目的：一是，電路可以完成任意長度字節(jié)信息流的8位并行CRC－32檢驗碼的計算，如t1、t2時間段的信息流的長度為4個字節(jié)，t3時間段的信息流的長度為6個字節(jié)；二是，當電路應(yīng)用于串行數(shù)據(jù)傳輸系統(tǒng)中，可以由信息幀的起始序列組合產(chǎn)生reset信號、信息幀的結(jié)束序列組合產(chǎn)生finish信號，這樣圖2所示的電路可以非常方便地嵌入到通信系統(tǒng)中，在發(fā)送方可以方便快速產(chǎn)生CRC－32校驗碼，在接收方只需將finish信號推遲四個時鐘周期即可實現(xiàn)信息幀的檢錯功能.

4　結(jié)束語

CRC是一種能發(fā)現(xiàn)并糾正信息在存儲和傳輸過程中連續(xù)出現(xiàn)的多位錯誤的校驗編碼.文中分析CRC碼的校驗原理及特點，推導相鄰字節(jié)間的CRC－32校驗碼的計算方法，利用組合邏輯直接快速計算當前字節(jié)的32位CRC校驗碼，使用Verilog HDL建立基于字節(jié)信息流的8位并行、高效、快速計算任意長度字節(jié)的32位CRC校驗碼的運算電路模型，通過Quartus II開發(fā)軟件編譯和仿真，下載到FPGA芯片中快速穩(wěn)定實現(xiàn)CRC－32校驗碼的計算及檢錯功能.

電路由輸入信號啟動和停止，不僅可以使字節(jié)信息流的長度不限，還可容易地嵌入到通信傳輸系統(tǒng)中，在發(fā)送方快速計算CRC－32校驗碼，在接收方可實現(xiàn)信息幀的檢錯功能，避免由于信道傳輸特性不理想及其他噪聲的影響而引起的信息位出錯，保證信息正確可靠地傳輸.

［1］ 張平安.16位循環(huán)冗余校驗碼（CRC）的原理和性能分析［J］.山西科技，2005，5：123－125.

［2］ 梁海華，盤麗娜.快速CPC逆序校驗方法［J］.計算機應(yīng)用，2013，37（7）：1833－1835，1836.

［3］ 許培培，賈鉑奇，余金培，劉會杰，龔文斌.一種通用并行CRC計算原理及其實現(xiàn)［J］.微計算機信息，2010.26（9－3）：110－111.

［4］ 蔣安平.循環(huán)冗余校驗碼（CRC）的硬件并行實現(xiàn)［J］.微電子學與計算機，2007，24（2）：107－109.

［5］ 張樹剛，張遂南，黃士坦.CRC校驗碼并行計算的FPGA實現(xiàn)［J］.計算機技術(shù)與發(fā)展，2007，17（2）：56－58.

［6］ RAMABADRAN TV，GAITONDE S S.ATutorial on CRC Computations［J］.Micro IEEE，1988，8（4）：62－75.

［7］ 廖堅，于海勛.USB中的CRC校驗原理及其Verilog HDL語言實現(xiàn)［J］.計算機工程與設(shè)計，2005，26（11）：3127－3129.

［8］ 李宥謀.以太網(wǎng)中8位并行CRC－32軟核設(shè)計［J］.西安郵學院學報，2006.11（5）：32－35.

［9］ 梁海華，盤麗娜，李克清.CRC生成與同構(gòu)逆序校驗方法［J］.微電子學與計算機，2014，9：167－169，172.

［10］ 張小紅，盧娟.超高頻RFID系統(tǒng)的CRC分組ALOHA算法優(yōu)化［J］.計算機應(yīng)用，2014，34（9）：2742－2746.

［11］ 藺冰.關(guān)于同余式2n≡4（modn）［J］.安徽師范大學學報：自然科學版，2010，33（5）：425－427.

［12］ 程桂花，齊學梅，羅永龍.AES算法中模逆運算電路設(shè)計與實現(xiàn)［J］.小型微型計算機系統(tǒng)，2011，32（6）：1240－1244.

Design and Implementation of Parallel CRC－32Checking Circuits for Byte Streams

CHENG Gui－h(huán)ua1， CHEN Fu－long1， QI Xue－mei1， ZUO Kai－zhong2
（1.School of Mathematics and Computer Science，Anhui Normal University，Wuhu 241003，China；2.Engineering Technology Research Center of Network and Information Security，Anhui Normal University，Wuhu 241003，China）

CRC is a check coding method to detect and correct continuous multiple error bits in the process of storage and transmission.In this paper，the principles and characteristics of CRC－32are analyzed，the algorithms of CRC－32between adjacent bytes are derived，the CRC－32code of the current byte is fast calculated by combinational logic circuits in parallel，and this CRC－32coding and error detection circuit coded in Verilog HDL is implemented in FPGA.In this circuit，the CRC－32check code for byte stream with an arbitrary length is calculated，and it also can be embedded in communication transmission systems for error detection and correction to ensure that the information is transmitted accurately and reliably.

CRC－32；cyclic redundancy check code；parallel CRC－32algorithm；byte stream

309.2

A

1001－2443（2016）03－0214－06

10.14182／J.cnki.1001－2443.2016.03.002

2015－12－20

國家自然科學基金（61370050，61572036）；安徽省高校省級自然科學研究項目（KJ2014A084）；安徽省高校省級自然科學研究項目（自籌KJ2012Z119）；蕪湖市科技計劃重點項目（2014cxy04）.

程桂花（1966－），女，安徽池州人，講師，主要研究方向為計算機系統(tǒng)結(jié)構(gòu)及信息安全.

引用格式：程桂花，陳付龍，齊學梅，等.字節(jié)信息流并行CRC－32校驗碼電路設(shè)計與實現(xiàn)［J］.安徽師范大學報：自然科學版，2016，39（3）：214－219.