32位CRC校验码课程设计.doc

32位CRC校验码课程设计摘要：通过对CRC校验码原理的分析,研究了一种并行32位CRC算法。该算法采用递推的方法,直接得出计算多位数据后的CRC余数与计算前余数之间的逻辑关系。相对于一般的按位串行计算或者查表并行计算的方法来说,该方法运算速度快且不需要额外的空间存储余数表,十分有利于硬件实现。概述：在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。循环冗余校验 CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC 校验的原理及其算法实现。一、CRC原理分析计算机系统中的数据,在进行读、写或者传输时可能产生错误,为了减少和避免错误的产生,一方面可以通过对特定电路的精心设计,提高电路的稳定性和可靠性;另一方面则是对数据采用某种编码,通过少量的附加电路,使之能发现某些错误,甚至能确定出错位置,进而实现自动改错的功能。CRC(循环冗余码)就是一种常用的错误检测码,它可以发现并纠正数据存储或传输过程中连续出现的多位错误,因此在介质存储和网络通信方面得到了广泛的应用。随着技术的发展,数据存储和传输速度大大提高,在一些高速的场合如usb2.0或者快速以太网中,传统的串行CRC 算法已不能满足速度上的要求,而必须采用速度更快的并行算法。CRC 校验的基本思路是利用线性码原理,对需要进行传输的原始k 位二进制数据按照一定的规则处理,产生一个r 位的校验码并附加在原始数据后面,形成一个 k + r 位的二进制数据,最后一起发送出去。首先,可将待编码的k 位数据表示成多项式其中为0或者1。对于r位CRC来说，校验码产生的过程为：将M（X）左移r位，然后除以一个称为生成多项式的G（X），所得余数就是CRC校验码。这里，生成多项式G（X）是一个r+1位的多项式。用公式表示如下：其中Q（X）为商，在CRC的计算过程中不需要关注，R(x)为余数，就是需要的CRC码。CRC的计算使用的是模2运算，即不带进位和借位的按位加减，这在逻辑上等同于异或运算。串行32位的CRC算法设为计算前的CRC多项式，为生成多项式G(x)的第i位系数。则新读入一位数据后，若记为计算一位数据后的CRC码多项式，则可得：式（1）给出了读入一位数据后新的CRC码与原来的之间的逻辑关系。采用这种算法，当原始数据依次输入完毕后，32位寄存器内的值就是最后的CRC码。这种算法无需在原始数据后添加32位0进行计算。二、并行32位CRC算法串行算法一个时钟周期内只能处理一位数据,在某些高速场合只能靠提高时钟频率来达到所需的速度要求,这增加了开发的难度和成本,因此提出了CRC 的并行算法。并行CRC 算法一次读入多位数据,通过当前余数与读入数据的运算,得出新的余数。显然,一个时钟周期处理n 位数据的并行算法在计算结果上与串行算法处理n 个时钟周期所得的余数应该相同。基于这一点,采用递推的方法可由串行算法导出并行算法计算前后余数之间的逻辑关系。下面以4 位CRC - 32 并行算法为例,说明推导的过程。CRC-32的生成多项式G(x)为：转换成二进制序列就是100000100110000010001110110110111为了便于表达，记为： （2）其中，对应于生成多项式的系数，取0或者1。定义为计算了第j位数据后所得CRC值的第i位，为读入的数据顺序，最初时的CRC值为：，。基本思想就是连续套用式（1）给出的串行公式8次，以期得到处理8位数据后与和，之间的逻辑关系。推导过程如下：以上推导结果表明，计算8位数据后的CRC值可由当前CRC值与输入数据的异或组合来表示，这为并行CRC的实现提供了理论基础。三、并行CRC-32算法的一些改进及模块的设计思路当接收端收到包含CRC 校验的数据包时,用与发送端同样的生成多项式再次计算CRC 值,如果数据在传输过程中没有发生错误,则计算的结果应该为0。这在通常情况下是正确的。现在考虑两种特殊的情况,一种是当数据包的开头有多余0 出现(或者以连续0 开头的数据丢失了开头的几位0) ,另一种是数据包的结尾有多余的0 出现(或者以连续0 结尾的数据丢失了结尾的几位0) 。在这两种情况下,当接收端计算CRC 的值为0 时,不能确定没有错误发生,这是因为如果一个数据串的CRC 计算结果为0 ,那么在串头或者串尾增加或减少几位0 ,计算的结果仍然是0 ,然而数据已经被改变了。针对这两种情况,CRC 算法作了相应的改动。对于解决串开头0 的问题,可以把32 位CRC 寄存器的值预设为全1 ,相当于把原始数据的高32 位取反来计算CRC。这样处理后,如果由于传输错误在数据开头出现0 的增加或减少,经过取反后的数据就会与原来的不同,故而达到了错误检测的目的。由于在数值上这样等于给被除数加上了个常量F ,而在CRC 的生成和校验阶段都做这样的处理,所以在算法上对最终的校验结果没有影响。解决串结尾0 的问题稍微麻烦点,具体做法是生成CRC 码时将正常计算得出的结果按位取反,作为最终的CRC 码附加在数据后。校验时在接收到的数据包(包括原始数据和校验码) 之后添加32 个0 ,计算除以生成多项式的余数。这时,当数据传输没有发生错误时,CRC 校验的结果不再为0 ,而是一个常数,通常被称为魔数(magic number) 。同样,当出现数据结尾有0 的增减错误时,计算所得的余数会发生变化。所有校验结果不等于这个常数的数据包就被认为是出现了错误。下面给出32 位CRC校验中这个常量的计算方法:设M为原始数据串,G为生成多项式,R 为取反前的余数，所用的加法均为模2加法可知现在将R取反，计为由式（3）可知：所以 对于32位CRC校验的生成多项式来说，这个结果为0x704DD70。其代码是这样写的if(i=(INPUT_BYTE-4) Begincrcout=crcout32hFFFFFFFF;crcout= crcout0, crcout1, crcout2, crcout3,crcout4, crcout5, crcout6, crcout7,crcout8, crcout9, crcout10, crcout11,crcout12, crcout13, crcout14, crcout15,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结果，这个是拿比较用的begincrcout=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 ,然后把接收到的数