32位CRC校验码课程设计

1、32位CRC校验码课程设计摘要：通过对CRC校验码原理的分析,研究了一种并行32位CRC算法。该算法 采用递推的方法,直接得出计算多位数据后的CRC余数与计算前余数之间的逻辑 关系。相对于一般的按位串行计算或者查表并行计算的方法来说,该方法运算速 度快且不需要额外的空间存储余数表，十分有利于硬件实现。概述：在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然 使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产 生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息 地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个 通信系统地关键

2、问题之一。为保证传输过程的正确性，需要对通信过程进行差错 控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC） 和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输 过程误码率较高时，采用FEC容易出现“乱纠”现象HEC方式则式ARQ和FEC的结 合。在许多数字通信中，广泛采用AR Q方式，此时的差错控制只需要检错功能。 实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码 校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校 验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到 的校验码和

3、接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都 有各自的缺点，误判的概率比较高。循环冗余校验CRCCCyclic Redundancy Check） 是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低， 在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。一、CRC原理分析计算机系统中的数据，在进行读、写或者传输时可能产生错误，为了减少和避 免错误的产生，一方面可以通过对特定电路的精心设计，提高电路的稳定性和可 靠性;另一方面则是对数据采用某种编码，通过少量的附加电路，使之能发现某些 错误,甚至能确定出错位置，进而实现自动改错的功能。CR

4、C（循环冗余码）就是一 种常用的错误检测码，它可以发现并纠正数据存储或传输过程中连续出现的多位 错误，因此在介质存储和网络通信方面得到了广泛的应用。随着技术的发展，数据 存储和传输速度大大提高,在一些高速的场合如usb2.0或者快速以太网中，传统 的串行CRC算法已不能满足速度上的要求，而必须采用速度更快的并行算法。CRC校验的基本思路是利用线性码原理，对需要进行传输的原始k位二进制 数据按照一定的规则处理，产生一个r位的校验码并附加在原始数据后面,形成 一个k + r位的二进制数据,最后一起发送出去。首先,可将待编码的k位数据表示成多项式M（X） = * 1 Xi + 樵 2Xk-2 +.

5、+ CXi +. + C1 X + C0其中为C 0或者1。对于r位CRC来说，校验码产生的过程为：i将M (X)左移r位，然后除以一个称为生成多项式的G (X),所得余数就是CRC校 验码。这里，生成多项式G(X)是一个r+1位的多项式。用公式表示如下：M (X ) xr / /G (X)其中Q(X)为商，在3RC的计算过程中不需要关注，R(x)为余数，就是需要的CRC 码。CRC的计算使用的是模2运算，即不带进位和借位的按位加减，这在逻辑上等 同于异或运算。串行32位的CRC算法设Cj x3i + Cj x30 + Cjx + Cj = x32(d xk-i + d xk-2 + d )m

6、od G(x)313010k-1k - 20为计算前的CRC多项式，为生成多项式G(x)的第i位系数。则新读入一位数据d后，x 32( d xk-1 + d xk-2 + . + d xi + d x + d )mod G (x)=x 33( d xk-1 + d xk-2 + d xi + d )mod G (x) + x32d mod G (x)=(Cj + gCj)x31 + (Cj + g Cj)x30 + (Cj + gCj)x + TOC o 1-5 h z 301 312930 3101 31g Cj + g dx31 + g dx30 + g dx + g d = g (Cj

7、+ d) 0 31313010031+矿Cj + g (Cj + d)xi i-1i 31i=1若记Cj+1 x31 + Cj+1 x30 + + Cj+1 + Cj+1 = x32 (d xk-1 + d xk - 2 + +d xi + d x + d )mod G(x)为计算一位数据d后的CRC码多项式，则可得：Cj+1 = Cj + g (Cj + d ) i e 1,31 ii-1i 310式(1)给出了读入一位数据后新的CRC码Cj+1与原来的Cj之间的逻辑关系。 ii采用这种算法，当原始数据依次输入完毕后，32位寄存器内的值就是最后的CRC码。这种算法无需在原始数据后添加32位0

8、进行计算。二、并行32位CRC算法串行算法一个时钟周期内只能处理一位数据，在某些高速场合只能靠提高时 钟频率来达到所需的速度要求，这增加了开发的难度和成本，因此提出7CRC的 并行算法。并行CRC算法一次读入多位数据，通过当前余数与读入数据的运算， 得出新的余数。显然，一个时钟周期处理n位数据的并行算法在计算结果上与串 行算法处理n个时钟周期所得的余数应该相同。基于这一点，采用递推的方法可 由串行算法导出并行算法计算前后余数之间的逻辑关系。下面以4位CRC - 32并 行算法为例，说明推导的过程。CRC-32的生成多项式G(x)为：X32 + X26 + X23 + % 22 + %16 +

9、X12 + %11 + X10 + X 8 + X 7 + X 5 + X 4 + X 2 + X + 1转换成二进制序列就是100000100110000010001110110110111为了便于表达，记为： TOC o 1-5 h z g g g g g3231210(2) 其中，gj对应于生成多项式的系数，取0或者1。定义为计算了第位数据后所得CRC值的第i位，d，d，d，d，d，d，d， 7654321d为读入的数据顺序，最初时的CRC值为：C0，C0，Co，C0，C0，C0。 0313029210基本思想就是连续套用式(1)给出的串行公式8次，以期得到处理8位数据后C8i与C0和d

10、，d，d，d，d，d，d，d之间的逻辑关系。推导过程如下： i76543210C8= C7+ d= C6 + g(C6+ d ) + d031030313110=C1 + g (C1 + d ) + d 25263160=C0 + C0 + d + dC8 = C7 + g (C7 + d ) = C7 + C0 + C0 + d + d 1013100243060=C0 + C0 + d + d + C0 + C0 + d + d253171243060C8 = C; + g2(q + d0)=C0 + C0 + C0 + C0 + C0 + d + d + d + d + d2425263

11、03176210C3 = C; + g3(C；+ d0)C o + C o + C o + C o + d + d + d + d TOC o 1-5 h z 252627317321C8 C; + gC + d)C0 +C0 + C0 + C0 + C0 + d + d + d + d + d242627283064320C8C7 +g (C7+d)Co +g (Co +d)+g (C2 +d)+g (C3 +d)+g (C4 +d)=C0 +C0 +C0 +C0 +C0 +d +d +d +d272829317543C8 =C +g (C +d)1516 310=C0 + g C +d)+

12、g (C3 +d)+g (C2 +d)+g (G +d)16 31012 31411 31510 316=C +C0 +C +C +d +d +d242829540C8 =C + g (C +d)1617 310=C0 + g (C6 +d)+g (C2 +d)+g (C1 +d)+g (C0 +d)16 31112 31511 31610 317=C +C +C +C +d +d +d9252930651C8 = C + g (C7 + d ) 292829310=Co + g(C4+ d) + g(Ci+ d ) + g (C。+ d)263132331622317=C0 + C0 + C

13、0 + C0 + d + d + d273031763C8 = C7 + g (C7 + d ) 302930310=C0 + g (C3 + d ) + g (C0 + d )2631423317C0 + C0 + C0 + d + d283174C8 C7 + g (C7 + d ) 313031310C0 + g(C2 + d )26315C 0 + C 0 + d317以上推导结果表明，计算8位数据后的CRC值可由当前CRC值与输入数据的异或组 合来表示，这为并行CRC的实现提供了理论基础。三、并行CRC-32算法的一些改进及模块的设计思路当接收端收到包含CRC校验的数据包时,用与发送

14、端同样的生成多项式再次 计算CRC值，如果数据在传输过程中没有发生错误，则计算的结果应该为0。这在 通常情况下是正确的。现在考虑两种特殊的情况，一种是当数据包的开头有多余0 出现（或者以连续0开头的数据丢失了开头的几位0），另一种是数据包的结尾有 多余的0出现（或者以连续0结尾的数据丢失了结尾的几位0）。在这两种情况下, 当接收端计算CRC的值为0时,不能确定没有错误发生,这是因为如果一个数据串的CRC计算结果为0，那么在串头或者串尾 增加或减少几位0 ,计算的结果仍然是0 ,然而数据已经被改变了。针对这两种情 况,CRC算法作了相应的改动。对于解决串开头0的问题，可以把32位CRC寄存器的值

15、预设为全1 ,相当于 把原始数据的高32位取反来计算CRC。这样处理后，如果由于传输错误在数据开 头出现0的增加或减少，经过取反后的数据就会与原来的不同，故而达到了错误 检测的目的。由于在数值上这样等于给被除数加上了个常量F，而在CRC的生成 和校验阶段都做这样的处理，所以在算法上对最终的校验结果没有影响。解决串 结尾0的问题稍微麻烦点，具体做法是生成CRC码时将正常计算得出的结果按位 取反，作为最终的CRC码附加在数据后。校验时在接收到的数据包(包括原始数据 和校验码)之后添加32个0，计算除以生成多项式的余数。这时，当数据传输没 有发生错误时,CRC校验的结果不再为0，而是一个常数，通常被

16、称为魔数(magic number)。同样，当出现数据结尾有0的增减错误时，计算所得的余数会发生变化。 所有校验结果不等于这个常数的数据包就被认为是出现了错误。下面给出32位CRC校验中这个常量的计算方法：设M为原始数据串,G为生成多项式,R为取反前的余数，所用的加法均为模2 加法可知(Mx32 + R)mod G = 0现在将日取反，计为REMx2+R)moG=x32Mx2+(R+x3i+x30+. +x+1)mGd =X3#MX2+R)+X31+X30+ +x+1mod=x32(Mx2+R)+X52(x3i+x30+- +x+1)mOd由式(3)可知:x32 (Mx 32 + R) mod

17、 G = 0所以x 32 (Mx32 + R)mod G = x32( x3i + x 30 + x + 1)mod G对于32位CRC校验的生成多项式来说，这个结果为0 x704DD70。其代码是这样写的if(i=(INPUT_BYTE-4) Begincrcout=crcout32hFFFFFFFF;crcout= crcout0, crcout1, crcout2, crcout3,crcout4, crcout5, crcout6, crcout7,crcout8, crcout9, crcout10, crcout11,crcout12, crcout13, crcout14, cr

18、cout15,crcout16, crcout17, crcout18, crcout19,crcout20, crcout21, crcout22, crcout23,crcout24, crcout25, crcout26, crcout27, crcout28, crcout29, crcout30, crcout31;end对于CRC-32的校验码来说，比较重要的一部分是怎样控制接收数据，并当符合条 件时计算CRC，与送过来的校验码进行比较，正确的就输出结果为1，错误的就输 出结果为0。代码如下：if(i(INPUT_BYTE-4)/控制输入送过来的crc结果，这个是拿比较用的begi

19、ncrcout=nextCRC32_D8(d,crcout);endelse if(i(INPUT_BYTE)/控制输入要计算crc的字数begintempcrc=tempcrc23:0,d;endif(tempcrc=crcout)/比较crc结果是否正确beginresult=1;endelsebeginresult=0;endend其中 INPUT-BYTE=64。四、CRC-32校验码生成和校验码模块的设计生成模块的功能示意图如图1所示图1 CRC生成示意图同CRC生成模块，将32位寄存器初始化为全1 ,然后把接收到的数据每时钟周期 输入4位,与当前寄存器中的数据运算，结果存入32位寄存器作为新的值，当所 有数据输入完毕后,与0 xC704DD78比较，得出校验结果。电路仿真Current Simulaticn Time: 1QQ5QQ nsns1 1 1 12 ns1 1 1 1 Illi4代1 1 1 1 1 1 1 1EC VI I I I I I I I