32位并行数据的CRC_16编码器的FPGA实现.pdf

第28卷第2期 河池学院学报 Vol . 28 No. 2 2008年4月 JOURNAL OF HECH IUN I VERSITY Apr . 2008 32位并行数据的CRC - 16编码器的FPGA实现 谭华 1 ,韦林 1 ,田宜君 2 (1. 桂林电子科技大学 计算机与控制学院,广西 桂林 541004; 2.华南理工大学 数学科学学院,广东 广州 510641) 摘 要 在数据通信中,提高数据在通信中的可靠性,以及快速的数据处理能力一直是人们所追求的,循环 冗余校验CRC就是一种广泛采用的差错控制方法,也是一种最常用的信道编码方法。在介绍CRC码原理之后,以 经典的LFSR电路为基础,推导出产生32位并行数据的CRC - 16编码表达式,用EDA工具设计出CRC - 16编码 模块,并对其进行综合仿真,验证其可行性。 关键词 循环冗余校验;差错控制;编码器;并行算法;VHDL 中图分类号 TN919. 3 文献标识码 A 文章编号 1672 - 9021(2008) 02 - 0074 - 06 作者简介 谭华(1983 - ) ,男,湖北潜江人,桂林电子科技大学计算机与控制学院硕士研究生,主要研究方 向为嵌入式系统设计技术。 0 引言 在数字数据通信中,可能会因为各种原因导致数据在传输或接收时发生错误,为了保证数据传输的可靠 性和数据校验的高效性,循环冗余校验CRC(Cyclic Redundancy Code)原理就是一种被广泛采用的差错控制 方法和数据编码方法。它具有编码和解码方法简单,检错和纠错能力强等特点,能有效的对数据进行编码, 并可以显著地提高系统的检错能力 1 ,从而能够有效的保证数据传输的可靠性和正确性,因此,在数据通信 和计算机通信中有着广泛的应用。 随着通信技术、 计算机技术和控制技术 (3C 技术)的快速发展,在工业控制领域或小型移动终端设备对 数据传输的速率提出了更高的要求。多位数据的并行处理成为了人们关注的焦点,如何对多位并行数据进 行快速编码及校验成为了数据处理中的研究热点。例如,在高速的千兆以太网传输系统中往往是以32位数 据传输。如果采用一般的串行CRC编码处理方式,在处理速度方面必定会大打折扣,若要满足快速的处理 能力,就必须提高系统时钟频率,这样就增加了系统的功耗,也增加了系统的硬件实现难度。针对以上问题, 本文以具有更强差错校验能力的CRC - 16校验码为例,用FPGA实现了32位并行数据的CRC - 16编码。 这一实现使得系统能够在较低时钟频率下,对32位并行数据进行快速编码和差错控制,保证了多位数据的 快速处理和传输的可靠性。 1 CRC码原理 1. 1 CRC的分类 目前CRC的使用分为标准和非标准两种,非标准为用户自定义CRC的生成多项式,而标准是已被国际 标准化组织规定的标准生成多项式。 1. 1. 1 标准的CRC 在通信协议中常见并被广泛使用的,主要有以下几种(见表 1) 。 1. 1. 2 非标准的CRC 非标准的CRC一般是为了某种用途而采用的不同于标准的生成多项式,而实际的操作原理是相同的。 主要是用于需要CRC但需要低成本的应用,或者为了减轻计算机的处理负担,又能保证数据可靠性的折中 办法。此外,部分的加密算法也用CRC来生成。 47 表1 常用的几种CRC 名称多项式简记应用 CRC - 4x4+x+10x13ITU G . 704 CRC - 16x16+x15+x2+10x18005I BM SDLC CRC - CCITTx16+x12+x5+10x11021ISO HDLC, ITU X. 25. CRC - 32 x32+x26+x23+x22+x16+x12+x10+ x8+x7+x5+x4+x2+1 0x104C11DB7 ZIP, RAR, IEEE802 LAN /FDD I, PPP - FCS 1. 2 CRC编码原理 CRC编码是根据CRC校验原理得出的一种编码方法, CRC校验 2 的基本思想是 :利用线形编码理论, 在发送方根据要传送的k位二进制序列,以一定的规则产生r位校验用的监督码(即CRC码 ) , 并附在信息 后边,构成一个新的二进制代码序列共n=k+r位,最后发送出去。在接收方,则根据信息码和CRC码之间 所遵循的规则进行校验,以确定传送中是否出错。同样, CRC编码也是采用这种线形编码理论进行编码的。 编码和解码双方都使用同一个生成多项式G(x)(例如: CRC - CCITT, CRC - 16等)。 对一个数据进行编码,简单的说,就是原始数据通过某种算法,得到一个新的数据。而这个新的数据与 原始数据有着固有的内在联系。通过把原数据和新数据组合在一起形成新的数据,因此这个数据具有自我 校验的能力。我们把原来的数据表示为P (x) ,它是一个n阶的多项式。表示为: P (x)=an- 1x n- 1 +an- 2x n- 2 +a1x+a0 式中ai为0或1, x为伪变量,并用x i 指明各位间的排列位置。因此,一个8位二进制数10100101可以表示为: P (x) =1x 7 +0x 6 +1x 5 +0x 4 +0x 3 +1x 2 +0x 1 +1x 0 在对这个数据进行编码时,我们设CRC生成多项式为r阶的G ( x) ,并在带编码的二进制多项式 P ( x) 末尾 添加r个0,这样对应的二进制多项式为x r P (x)。再用生成多项式 G(x)去除xrP (x) ,求得余数为 r- 1阶的 二进制多项式 R (x) 。 R (x) 即为所求的CRC校验码多项式。最后用x r P (x) 以模2的方式减去R (x) ,则对 应的二进制序列就是包含了CRC校验码的待发送字符串,也就是编码后的数据。用如下表达式可以表示以 上描述: x r P (x) G(x) =Q (x)+ R (x) G(x) x r P (x)-R (X) =G (x)Q (x)=T (x) 其中Q (x)是商多项式, R (x)是余数多项式, T (x)是编码后的数据。 在对数据进行解码时,应采用同样的CRC生成多项式G(x) ,用接收到的数据去除G (x) ,如果余数为零 则传输正确,否则在传输过程中肯定存在错误。同时T (x)可以看作是由P (x)和CRC校验码的组合,所以 译码时将接收到的二进制数据去掉尾部的r位,得到的就是原始数据。 2 CRC - 16编码的并行算法分析 2. 1 CRC - 16的串行算法原理 经典的CRC校验码生成电路采用线性反馈移位寄存器LFSR来实现 3 ,也就是通用的CRC串行算法的 实现电路,如图1所示。 图1 线性反馈移位寄存器LFSR 其中g ( i) ( i=0,1, r- 1)的通断由生成多项式的对应的系数是0还是1决定, g ( i)=1表示通路, g ( i) =0与表示断路。 对于CRC - 16,其生成多项式为: G(x) =x 16 +x 15 +x 2 +1。所以对应的系数016为:10100000000000011, 57 由此可以将CRC - 16串行编码电路简化为图2。 图2 CRC - 16串行编码电路 在用CRC - 16串行编码电路对输入数据进行编码时,它的输入数据是串行输入的。其算法是按位逐个 输入的,因此数据的传输率较低,它的运算速度的提高完全依赖于系统的时钟频率的提高,要实现对数据的 快速处理,就会增加系统硬件实现的难度。不能满足现在的低功耗下的数据快速传输。为此,如果能将数据 的处理方式改为并行处理,这样就可以在一个较低的时钟频率下快速的处理多位数据。 2. 2 CRC - 16编码的并行算法分析 我们从图1可以看出,各移位寄存器当前的存数即为CRC余数值,当进行串行CRC运算时,当前的 CRC余数值只与当前信息码的最前一位的输入值和前一状态的CRC余数值有关。由此可以推断,在进行 32比特的并行CRC运算时, 32比特信息码一次输入并行运算电路所产生的CRC值应该和32比特信息码 依次输入串行运算电路所产生的CRC值完全相同。正是基于这一思想,我们可以将串行算法改为并行算 法,并得以实现。 这里根据图2所示的CRC - 16串行编码电路,推算出了能实现32位并行接口数据流进行CRC - 16编 码的表达式。并给出了如下32位并行数据的CRC - 16编码电路结构图 4。 图3 32位并行数据的CRC - 16编码电路结构图 在图4中, R0R15作为存贮余数的寄存器。输入数据为32位并行数据D (31 DOWNTO 0)。并行数 据首先通过一个CRC - 16并行运算电路和余数寄存器中的数据进行运算,得出的结果依然保存在余数寄存 器中。每个时钟周期完成32位数据CRC - 16运算并将结果输出到CRC(15 DOWTO 0) ,在下一个时钟对后 继的并行数据继续进行运算。 推导如下:设余数寄存器中的数据为R15R0,然后假设输入并行数据为D (31)D (0)。数据的校验 从D (0) (最低)数据位开始。这里根据图2所示的CRC - 16串行编码电路可知,D (0)这个数据位和余数多 项式的最高位的异或结果为: R0 =D (0) R15;那么在做完第1位数据的CRC运算后,所得到的余数多项式可 以使用布尔表达式表示为: R0 =D (0) R15; R1 =R0; R2 =D (0) R15 R1; R3 =R2; ; R15 =D (0) R15 R14。 我们将这个结果重新置入余数寄存器,然后对输入数据的第2, 3,位依次类推做迭代运算。最后得 到一次完成32位数据的CRC“ 模2” 运算的余数项的表达式为: R0 =D (31) D (30) D (27) D (26) D (25) D (24) D (23) D (22) D (21) D (20) D (19) D (18) D (17) D (16) D (15) D (13) D (12) D (11) D (10) D (9) D (8) D (7) D (6) D (5) D (4) D (3) D (2) D (1) D (0) R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R14 R15; R1 =D (31) D (28) D (27) D (26) D (25) D (24) D (23) D (22) D (21) D (20) D (19) D (18) D (17) D (16) D (14) D (13) D (12) D (11) D (10) D (9) D (8) D (7) D (6) D (5) D (4) D (3) D (2) 67 D (1) R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R15; R2 =D (31) D (30) D (29) D (28) D (16) D (14) D (1) D (0) R0 R12 R13 R14 R15; R3 =D (31) D (30) D (29) D (17) D (15) D (2) D (1) R1 R13 R14 R15; R4 =D (31) D (30) D (18) D (16) D (3) D (2) R0 R2 R14 R15; R5 =D (31) D (19) D (17) D (4) D (3) R1 R3 R15; R6 =D (20) D (18) D (5) D (4) R2 R4; R7 =D (21) D (19) D (6) D (5) R3 R5; R8 =D (22) D (20) D (7) D (6) R4 R6; R9 =D (23) D (21) D (8) D (7) R5 R7; R10 =D (24) D (22) D (9) D (8) R6 R8; R11 =D (25) D (23) D (10) D (9) R7 R9; R12 =D (26) D (24) D (11) D (10) R8 R10; R13 =D (27) D (25) D (12) D (11) R9 R11; R14 =D (28) D (26) D (13) D (12) R10 R12; R15 =D (31) D (30) D (29) D (26) D (25) D (24) D (23) D (22) D (21) D (20) D (19) D (18) D (17) D (16) D (15) D (14) D (12) D (11) D (10) D (9) D (8) D (7) D (6) D (5) D (4) D (3) D (2) D (1) D (0) R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R13 R14 R15; 用上述这个表达式,我们可以在一个周期时间里并行地完成32位数据的CRC - 16校验码的产生和校 验,从而满足了低功耗下的多位数据的快速处理。 3 32位并行数据CRC - 16校验码的FPGA实现 一般的CRC校验码生成器具有编码和解码两种功能,编码用于对输入数据计算CRC校验码,解码用于 验证接收到的数据是否正确,其实这两个过程对于CRC校验生成器是一样的。不同之处在于解码完成后需 要判断得到的CRC校验码是否为0,如果是0则表示数据正确,如果不为0则表示数据有错。 基于以上并行算法分析。我们在这里给出了用VHDL 5实现的 32位并行数据的CRC - 16编码的生 成,见表2。 图4 CRC - 16编码模块 表2 32位CRC - 16编码器的端口说明 clkinput系统时钟 crc_rsetinputCRC生成器复位 sdatainput输入数据 crc_outoutput输出CRC校验码 其中VHDL代码如下: L I BRARY IEEE; USE IEEE. STD_LOGI C_1164. ALL; ENTITY CRC16 IS PORT ( sdata: I N STD_LOGIC_VECTOR (31 DOWNTO 0) ; clk: I N STD_LOGI C; crc_rset: I N STD_LOGIC; crc_out:OUT STD_LOGIC_VECTOR (15 DOWNTO 0) ) ; END CRC16; ARCH ITECTURE th OF CRC16 IS SIGNAL D: STD_LOGIC_VECTOR (31 DOWNTO 0) ; SIGNAL R, crc_temp: STD_LOGI C_VECTOR (15 DOWNTO 0) ; BEGI N D 0 ) ; ELSIF rising_edge(clk) THEN crc_temp (0) =D (31) XOR D (30) XOR D (27) XOR D (26) XOR D (25) XOR D (24) XOR D (23) XOR D (22) XOR D (21) XOR D (20) XOR D (19) XOR D (18) XOR D (17) XOR D (16) XOR D (15) XOR D (13) XOR D (12) XOR D (11) XOR D (10) XOR D (9) XOR D (8) XOR D (7) XOR D (6) XOR D (5) XOR D (4) XOR D (3) XOR D (2) XOR D (1) XOR D (0) XOR R (0) XOR R (1) XOR R (2) XOR R (3) XOR R (4) XOR R (5) XOR R (6) XOR R (7) XOR R (8) XOR R (9) XOR R (10) XOR R (11) XOR R (14) XOR R (15) ; crc_temp (1) =D (31) XOR D (28) XOR D (27) XOR D (26) XOR D (25) XOR D (24) XOR D (23) XOR D (22) XOR D (21) XOR D (20) XOR D (19) XOR D (18) XOR D (17) XOR D (16) XOR D (14) XOR D (13) XOR D (12) XOR D (11) XOR D (10) XOR D (9) XOR D (8) XOR D (7) XOR D (6) XOR D (5) XOR D (4) XOR D (3) XOR D (2) XOR D (1) XOR R (0) XOR R (1) XOR R (2) XOR R (3) XOR R (4) XOR R (5) XOR R (6) XOR R (7) XOR R (8) XOR R (9) XOR R (10) XOR R (11) XOR R (12) XOR R (15) ; crc_temp (2) =D (31) XOR D (30) XOR D (29) XOR D (28) XOR D (16) XOR D (14) XOR D (1) XOR D (0) XOR R (0) XOR R (12) XOR R (13) XOR R (14) XOR R (15) ; crc_temp (3) =D (31) XOR D (30) XOR D (29) XOR D (17) XOR D (15) XOR D (2) XOR D (1) XOR R (1) XOR R (13) XOR R (14) XOR R (15) ; crc_temp (4) =D (31) XOR D (30) XOR D (18) XOR D (16) XOR D (3) XOR D (2) XOR R (0) XOR R (2) XOR R (14) XOR R (15) ; crc_temp (5) =D (31) XOR D (19) XOR D (17) XOR D (4) XOR D (3) XOR R (1) XOR R (3) XOR R (15) ; crc_temp (6) =D (20) XOR D (18) XOR D (5) XOR D (4) XOR R (2) XOR R (4) ; crc_temp (7) =D (21) XOR D (19) XOR D (6) XOR D (5) XOR R (3) XOR R (5) ; crc_temp (8) =D (22) XOR D (20) XOR D (7) XOR D (6) XOR R (4) XOR R (6) ; crc_temp (9) =D (23) XOR D (21) XOR D (8) XOR D (7) XOR R (5) XOR R (7) ; crc_temp (10) =D (24) XOR D (22) XOR D (9) XOR D (8) XOR R (6) XOR R (8) ; crc_temp (11) =D (25) XOR D (23) XOR D (10) XOR D (9) XOR R (7) XOR R (9) ; crc_temp (12) =D (26) XOR D (24) XOR D (11) XOR D (10) XOR R (8) XOR R (10) ; crc_temp (13) =D (27) XOR D (25) XOR D (12) XOR D (11) XOR R (9) XOR R (11) ; crc_temp (14) =D (28) XOR D (26) XOR D (13) XOR D (12) XOR R (10) XOR R (12) ; crc_temp (15) =D (31) XOR D (30) XOR D (29) XOR D (26) XOR D (25) XOR D (24) XOR D (23) XOR D (22) XOR D (21) XOR D (20) XOR D (19) XOR D (18) XOR D (17) XOR D (16) XOR D (15) XOR D (14) XOR D (12) XOR D (11) XOR D (10) XOR D (9) XOR D (8) XOR D (7) XOR D (6) XOR D (5) XOR D (4) XOR D (3) XOR D (2) XOR D (1) XOR D (0) XOR R (0) XOR R (1) XOR R (2) XOR R (3) XOR R (4) XOR R (5) XOR R (6) XOR R (7) XOR R (8) XOR R (9) XOR R (10) XOR R (13) XOR R (14) XOR R (15) ; END IF; END PROCESS; crc_out = crc_temp; END th; 本仿真采用的是Altera公司的Quartus II 5. 0开发工具,仿真用的有效数据是32位十六进制数 “D8C345A8”,生成的校验码是十六进制数“72EE” 。工作的频率是20 MHz。 87 图5 仿真结果图 4 总结 本文在对串行CRC算法原理分析的基础上,推导出了32位并行数据的CRC - 16编码的生成表达式, 并以此通过Altera公司的EDA工具设计出了其编码模块,并进行了仿真测试与验证,验证的结果与理论值 相符合。结果表明,通过本系统能够很好的满足低功耗下的32位并行数据的快速编码与校验。从而提高了 系统中数据的快速传输。 参考文献: 1 TanenbaumAS .计算机网络M .北京:清华大学出版社, 1998. 137 - 142. 2 王新梅,肖国镇.纠错码原理与方法M .西安:西安电子科技大学出版社, 2001. 3 RamabadranTV, GaitondeSS . ATutorialonCRCComputa - tionsJ . MicroIEEE, 1988, 8 (4) : 62 - 75. 4 程军,陈贵灿,姜飞. USB数据传输中CRC校验码的并行算法实现J .微电子学与计算机, 2003, (3) : 77 - 80. 5 潘松. EDA技术实用教程M .北京:科学出版社, 2002. An Achievement on FPGA of CRC - 16 Encoder with 32 Bits ParallelData TAN Hua 1 , W EIL in 1 ,TIAN Y i2jun 2 ( 1. School of Computer and Control, Guilin University of Electronic Technology, Guilin, Guangxi, 541004; 2. School ofMathematical Sciences, South China University of Technology, Guangzhou, Guangdong 510641, China) Abstract What people have been pursuing, in data communication, is its data reliability as well as the highly efficient data processing capability . CRC(Cyclic Redundancy Check) is a method commonly used for error control and channel coding .Introducing the theory of CRC and basing on classic LFSR circuit, the paper inferred the CRC - 16 encoding formulation with 32 bits parallel data, designed the CRC - 16 encoderwith EDA, and fur2 thermore implemented a comprehensive sti mulation which confirmed the feasibility . Key words CRC; error control; encoder; parallel algorithm; VHDL 收稿日期 2008 - 02 - 09 责任编辑 刘景平 97