字节信息流并行CRC－32校验码电路设计与实现

程桂花， 陈付龙， 齐学梅， 左开中

（1.安徽师范大学数学计算机科学学院，安徽芜湖 241002；2.安徽师范大学网络与信息安全工程技术研究中心，安徽芜湖 241002）

字节信息流并行CRC－32校验码电路设计与实现

程桂花1， 陈付龙1， 齐学梅1， 左开中2

（1.安徽师范大学数学计算机科学学院，安徽芜湖 241002；2.安徽师范大学网络与信息安全工程技术研究中心，安徽芜湖 241002）

CRC是一种能发现并纠正信息在存储和传输过程中连续出现的多位错误的校验编码.分析CRC码的校验原理及特点，推导相邻字节间的CRC－32校验码的计算方法，利用组合逻辑并行快速计算当前字节的32位CRC校验码，使用Verilog HDL设计编码电路，通过FPGA实现CRC－32编码及检错功能.电路不仅可以计算任意长度的字节信息流的CRC－32校验码，还可嵌入到通信传输系统中快速并行实现CRC－32的编码及检错运算，保证信息正确可靠地传输.

CRC－32；循环校验码；并行CRC－32算法；字节信息流

引 言

CRC［1］（Cyclic Redundancy Check，循环冗余码校验）是一种能发现并纠正信息在存储和传输过程中连续出现的多位错误的校验编码.CRC码因实现简单、检错能力强而在通信传输中得到广泛应用［2，3］，如USB协议、IEEE 802.3标准、IEEE 802.11标准、RFID协议等都采用了CRC作为正确性校验的方法［4］，避免由于信道传输特性不理想及其他噪声的影响而引起的信息位出错，保证信息正确可靠地传输.

CRC码的计算大都使用硬件电路直接进行［5－10］，目前硬件实现CRC码计算的方法主要有串行和并行两种.文献［6］提出的串行CRC算法，简单易于实现，但每次只能处理一位的二进制，难以满足高速应用场合；文献［3－5，8－10］通过分析串行的CRC算法提出的并行CRC算法，核心思想是同时计算8位二进制（字节）的CRC校验码，相对于串行算法效率大大提高.

采用文献［3－5，9－10］提出的并行CRC算法可得到16位的余数校验码，属于并行CRC－16算法；利用文献［8］提出的并行CRC算法可得到32位的余数校验码，属于并行CRC－32算法，虽然检错能力高于并行CRC－16算法，但只讨论了单个字节的并行CRC－32算法；文献［3］提出的CRC－16算法，虽采用查表（余数表）法实行并行算法，余数表需占用存储空间且影响计算速度，但讨论了相邻字节间的CRC－16码的计算方法，综合两种算法的优点，文中提出基于“字节信息流并行CRC－32”算法.文中分析CRC码的校验原理，并行CRC－32的计算规则，推导相邻字节间的CRC－32校验码的计算方法，利用组合逻辑并行快速计算当前字节的32位CRC校验码，设计基于字节信息流的并行、高效、快速计算任意长度字节信息的CRC－32校验码运算电路，在Quartus II开发软件中仿真，通过FPGA实现.

1　CRC算法

CRC码的计算使用二进制多项式模运算，系数运算以2为模［11－12］，运算时不考虑进位和借位，模2加减其实质是按位执行异或运算，模2乘除采用模2加减计算部分积和部分余数.一个二进制位串可以表示为二进制多项式，如二进制串“100011011”的多项式表示为x8＋x4＋x3＋x＋1；反之亦然.

1.1CRC码的编码与校验原理

设n位信息串mn－1mn－2…m1m0用信息多项式M（x）表示为：

首先，将信息多项式M（x）左移k位，即M（x）xk表示为：

其次，选择一个k＋1位的生成多项式Gk＋1（x）对M（x）xk作模2除，得到k位的余数多项式R（x）作为校验码，附加到信息位串之后，形成CRC码字多项式MC（x），表示如下：

从式（1）－（4）计算得到式（5）的过程称为CRC编码，多项式MC（x）对应的二进制位串称为CRC码字，由发送方向外发送.

接收方将收到CRC码字后用相同的生成多项式作模2除，得余数多项式R′（x），若收到的CRC码字正确，R′（x）的计算过程表示如下：

若R′（x）为全“0”时，说明接收方收到的CRC码字是正确的；否则，收到的CRC码字有错，根据余数的值可推知出错的二进制位，可以实现纠错功能，或要求发送方重新发送CRC码字，直到正确为止.

在数据通信与网络中，通常n非常大，由数千个二进制位构成一个信息帧，为检测信息传输正确与否，通常选用的CRC－32的生成多项式［8］如式（7）所示.

1.2字节信息流的CRC－32算法

假设：

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

·Mi（x）表示第i个字节；

·字节信息流Mn－1（x）Mn－2（x）…Mi（x）…M1（x）M0（x）可表示为：

即字节数据流左移32位，再模2除生成多项式G33（x）：

首先，假设

其次，分析｛Mn－1（x）＊256（n－1）＋Mn－2（x）＊256（n－2）｝＊2564mod G33（x）的余数R（n－2）（x），分析过程如式（11）

式（11）表明，当前字节Mn－2（x）的32位CRC校验码的计算方法是

第一步，计算上一字节的CRC校验码的最高8位与当前字节异或后的CRC校验码；

第二步，上一字节的CRC校验码左移8位；

第三步，第一、第二步的计算结果异或得到当前字节的CRC校验码R（n－2）（x）.

重复第一至第三步依次逐个字节计算CRC校验码，直到M0（x）计算得到R0（x）为整个字节信息流的32位CRC校验码.

如，字节信息流M1（x）M0（x）＝DD9DH，则32位CRC校验码R（x）计算过程如下：

采用式（11）不仅可以计算任意长度字节信息流的32位CRC校验码，而且将基于二进制位的32位CRC校验码的计算转换为基于字节的CRC码的计算，加速CRC码的运算.

1.3单字节32位CRC校验码并行算法

表1　8位并行CRC－32计算逻辑表达式（“＋”表示异或）

由式（8）可知，字节信息流的CRC校验码运算的本质是一个递推过程［2］，其核心是计算单个字节的CRC校验码，依据式（1）－（4）采用模2除及代入运算规则可推导出一种求单字节的高速并行CRC算法，可利用组合逻辑电路计算一个字节的32位CRC校验码.单个字节的8位信息多项式系数m7m6m5m4m3m2m1m0与32位的CRC校验码余数多项式系数r31r30r29r28r27r26…r3r2r1r0逻辑关系如表1所示.

2　CRC－32编码电路设计与实现

2.1电路设计

CRC码的计算使用二进制多项式模运算，运算时不考虑进位和借位，模2加减其实质是按位执行异或运算，模2乘除采用模2加减计算部分积和部分余数.基于式（11）的字节信息流CRC码运算电路结构如图1所示：电路在时钟信号的作用下，按如下步骤进行工作：

第一步，当reset信号有效（“0→1→0”），余数寄存器r始化为全“0”；

第二步，在时钟信号的上升沿（“↑”），余数寄存器r高八位与当前输入的字节m异或后存入字节寄存器mx；

第三步，组合逻辑电路按照表1所示的逻辑表达式，并行计算得到字节的32位CRC校验码rx；

图1　字节信息流8位并行CRC－32电路结构

第四步，rx的值与余数寄存器的现态左移八位后执行异或运算，异或结果在时钟下降沿（“↓”）的作用下存入余数寄存器.这样，在一个时钟周期内可以完成一个字节的CRC码的计算.

第五步，重复第二－第四步，直到完成所有字节的计算，同时输入信号finish有效（“1→0→1”）表明字节信息流发送结束，利用finish信号的下降沿（“↓”）将余数寄存器r的值存入输出寄存器rout中并向外发送，该值即为输入的字节信息流的32位CRC校验码.

电路由reset信号启动，finish信号结束，使得电路可以计算任意长度的字节信息流的CRC－32校验码；时钟信号的上升、下降沿的分别驱动两个寄存器工作，使得电路在每个时钟内完成一个字节的CRC－32校验码的计算.

2.2逻辑实现

应用Verilog HDL语言设计基于字节信息流的8位的高速、低功耗的并行CRC－32运算电路，选择EP2C5Q208CN芯片，在Quartus II开发工具中配置、综合和优化后通过Quartus II中的Programmer工具下载到芯片中，可以快速稳定地实现CRC－32校验码的运算操作且占用面积小，达到预期设计目标.

EP2CQ208CN是Altera公司推出的CycloneⅡ系列的FPGA，具有低成本、低功耗和高性价比的特点，芯片内包含丰富的逻辑单元、可编程寄存器和存储单元，可以进行大量的逻辑运算，支持寄存器反馈操作，在数据传输、无线局域网、无线感知网、智能卡系统、汽车等领域得到广泛应用，在相关应用领域可提供快速、低功耗解决方案.

2.3仿真波形

文中设计基于字节信息流的高速、低功耗的8位并行CRC－32校验码运算电路的Verilog HDL模型，在Altera公司的Quartus II软件中进行编译和仿真，用Visual FoxPro语言进行软件验证，所有运算结果完全正确.图2是不同长度的字节信息流的CRC校验码的仿真波形.

图2中t1时间段：输入信息流m由DDH、9DH、CCH、9DH四个字节组成，每个时钟周期计算一个字节的32位的CRC校验码，所以时间段t1由4个时钟周期T1、T2、T3、T4组成.各个时钟周期电路完成的功能如下：

T1：字节信息流的起始信号reset在T1时钟周期的前半周期有效（高有效），完成寄存器的初始化操作；T1时钟周期的上升沿处字节寄存器mx接收输入端数据DDH（当前输入字节DDH与余数寄存器r的现态的高8位00H异或结果），组合逻辑电路的输出rx为2056CD3AH（DDH的32位CRC校验码）；T1时钟周期的下升沿处余数寄存器r接收输入端数据2056CD3AH（rx的值与r现态左移8位后的值全“0”异或结果），至此电路完成字节数据流“DDH”的32位CRC校验码的计算.

图2　字节信息流8位并行CRC－32仿真波形

T2：T2时钟周期的上升沿处字节寄存器mx接收输入端数据BDH（当前输入字节9DH与余数寄存器r的现态的高8位20H异或结果），组合逻辑电路的输出rx为8CF30BADH（BDH的32位CRC校验码）；T2时钟周期的下升沿处余数寄存器r接收输入端数据DA3E31ADH（rx的值与r现态左移8位后的值“56CD3A00H”异或结果），至此电路完成字节数据流“DD9DH”的32位CRC校验码的计算.

T3：T3时钟周期的上升沿处字节寄存器mx接收输入端数据16H（当前输入字节CCH与余数寄存器r的现态的高8位DAH异或结果），组合逻辑电路的输出rx为569796C2H（16H的32位CRC校验码）；T3时钟周期的下升沿处余数寄存器r接收输入端数据68A63BC2H（rx的值与r现态左移8位后的值“3E31AD 00H”异或结果），至此电路完成字节数据流“DD9DCCH”的32位CRC校验码的计算.

T4：T4时钟周期的上升沿处字节寄存器mx接收输入端数据F5H（当前输入字节9DH与余数寄存器r的现态的高8位68H异或结果），组合逻辑电路的输出rx为9E7D9662H（F5H的32位CRC校验码）；T4时钟周期的下升沿处余数寄存器r接收输入端数据38465462H（rx的值与r现态左移8位后的值“A63BC2 00H”异或结果），至此电路完成字节数据流“DD9DCC9DH”的32位CRC校验码的计算.

输入信号finish收到负脉冲，表明一个字节信息流输入结束，字节信息流“DD9DCC9DH”的32位校验码（38465462H）在此负脉冲的下降沿处存入寄存器rout并附加到数据流之后向外发送，同时电路在reset信号的作用下，又可开始下一个字节信息流的32位CRC校验码的计算，如图2中t2、t3时间段所示信息.

由图2可知，一个字节信息流的CRC－32校验码的运算由reset信号（“0→1→0”）启动、finish信号（“1→0→1”）结束，这样安排主要有两个目的：一是，电路可以完成任意长度字节信息流的8位并行CRC－32检验码的计算，如t1、t2时间段的信息流的长度为4个字节，t3时间段的信息流的长度为6个字节；二是，当电路应用于串行数据传输系统中，可以由信息帧的起始序列组合产生reset信号、信息帧的结束序列组合产生finish信号，这样图2所示的电路可以非常方便地嵌入到通信系统中，在发送方可以方便快速产生CRC－32校验码，在接收方只需将finish信号推迟四个时钟周期即可实现信息帧的检错功能.

4　结束语

CRC是一种能发现并纠正信息在存储和传输过程中连续出现的多位错误的校验编码.文中分析CRC码的校验原理及特点，推导相邻字节间的CRC－32校验码的计算方法，利用组合逻辑直接快速计算当前字节的32位CRC校验码，使用Verilog HDL建立基于字节信息流的8位并行、高效、快速计算任意长度字节的32位CRC校验码的运算电路模型，通过Quartus II开发软件编译和仿真，下载到FPGA芯片中快速稳定实现CRC－32校验码的计算及检错功能.

电路由输入信号启动和停止，不仅可以使字节信息流的长度不限，还可容易地嵌入到通信传输系统中，在发送方快速计算CRC－32校验码，在接收方可实现信息帧的检错功能，避免由于信道传输特性不理想及其他噪声的影响而引起的信息位出错，保证信息正确可靠地传输.

［1］ 张平安.16位循环冗余校验码（CRC）的原理和性能分析［J］.山西科技，2005，5：123－125.

［2］ 梁海华，盘丽娜.快速CPC逆序校验方法［J］.计算机应用，2013，37（7）：1833－1835，1836.

［3］ 许培培，贾铂奇，余金培，刘会杰，龚文斌.一种通用并行CRC计算原理及其实现［J］.微计算机信息，2010.26（9－3）：110－111.

［4］ 蒋安平.循环冗余校验码（CRC）的硬件并行实现［J］.微电子学与计算机，2007，24（2）：107－109.

［5］ 张树刚，张遂南，黄士坦.CRC校验码并行计算的FPGA实现［J］.计算机技术与发展，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语言实现［J］.计算机工程与设计，2005，26（11）：3127－3129.

［8］ 李宥谋.以太网中8位并行CRC－32软核设计［J］.西安邮学院学报，2006.11（5）：32－35.

［9］ 梁海华，盘丽娜，李克清.CRC生成与同构逆序校验方法［J］.微电子学与计算机，2014，9：167－169，172.

［10］ 张小红，卢娟.超高频RFID系统的CRC分组ALOHA算法优化［J］.计算机应用，2014，34（9）：2742－2746.

［11］ 蔺冰.关于同余式2n≡4（modn）［J］.安徽师范大学学报：自然科学版，2010，33（5）：425－427.

［12］ 程桂花，齐学梅，罗永龙.AES算法中模逆运算电路设计与实现［J］.小型微型计算机系统，2011，32（6）：1240－1244.

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

CHENG Gui－hua1， 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－），女，安徽池州人，讲师，主要研究方向为计算机系统结构及信息安全.

引用格式：程桂花，陈付龙，齐学梅，等.字节信息流并行CRC－32校验码电路设计与实现［J］.安徽师范大学报：自然科学版，2016，39（3）：214－219.