一种快速CRC算法的硬件实现方法

1、由于数据在传输和存储时可能会由于干扰等原因发生变化,所以一般会采用数据校验来确保数据的完整性。CRC(循环冗余码)算法是把原始数据输入到一个校验公式中,生成一定长度的校验码,然后把校验码添加到原始数据的后面,组成新的数据,对于串行输入输出的系统,需要循环计算校验码,直到数据全部计算结束 校验码的作用是保证数据的可靠性,它本身并不是系统要求1传输的数据,所以对于系统来说是冗余的。计算CRC、组成新数据的过程是编码,用相同的方法把数据译码,就可以发现数据是否变化。CRC算法可以用软件实现,也可以用硬件实现,但软件计算的速度受限于系统CPU的速度,使用硬件方式来实现可以提高计算速度,从而提升系统的通

2、信效率。最普通的CRC硬件实现方法是串行计算方法,使用一位数据输入,n位长度的原始数据连续计算n次后得出校验码,串行计算的电路结构简单,容易实现,可以工作在较高的时钟频率下。但随着通信速度的不断提高,高的数据传输带宽要求CRC的计算速度越来越快,串行计算的方法已经不适应要求,所以越来越多的使用并行计算方法 。本文先讲述串行计算的实现方法,再在2此基础上作一些改进,产生并行计算的电路结构。1CRC算法在模运算中,模2 2乘法运算2除法只在除数为1 2多项式表示,多项式的系数就是序列的值。如101011可以表示为1x5,二进制序列最左边的二进制位表示次数最高的多项式系数 。(x)就是CRC校验码,

3、多项式最高次数为k-1。编码之后的数据为F(x)=xM(x)+R(x),因为模2k加减法运算的结果相同,所以F(x)=xM(x)-R(x)=Q(x)G(x),在译码的时候,对F(x)作模运算,k结果应该为0。如果结果不为0,说明数据在编码后已经发生了变化。常用的CRC校验公式 :2串行实现串行计算时,每次输入一位数据,输入数据和上一次异或运算的结果组成新数据,循环进行异串行实现的电路结构如图1所示 。5g的取值范围是0或1,取0时,表示断路,不需要异或运算,取1时,表示通路,需要异或运算,其中ig和g都为1。对于k位的CRC校验,需要k个寄存器,当有新的数据输入后,异或运算立刻得出0k新的CR

4、C,寄存器在时钟沿移位,等待新的输入数据,反复循环,就可以计算出CRC的值。串行的方法虽然可以计算各种CRC,但是一个时钟周期只能计算一位数据,效率比较低,只适用于低速的串行输入输出系统,而当数据传输的速度很高,或者是多位数据并行传输时,需要引入并行计算的实现方法,并行的实现方法可以在一个时钟内对多位数据进行编码,从而提高了CRC的计算速度。3并行实现并行CRC计算,可以在串行计算的基础上改进电路结构来实现。在串行实现中一个时钟周期处理一位数据,如果能够把串行实现中多个时钟周期处理的数据集中到一个时钟周期内处理,就达到并行处理的目的了。先分析一下串行实现中每一位CRC校验码的生成过程,CRC的

5、模2多项式为4CRC的长度为k,R是在计算j位原始数据后CRC的值所对应的模2多项式,r 表示第i位的值,jr是R 第i-1位寄存后的值,g是校验公式对应的数据位(g、g为1),d是输入的第j位原i-1、j-1始数据。j-1i0kj所以有这个函数关系式表示R 只和R 有关,所以在电路实现时只计算R ,而不用计算2j+12j-12j2j+12j-1R R 。从R 到R 计算两位数据的输入,在串行实现中移位寄存两次,需要两2j2j+12j-12j+1个时钟周期,现在一个周期就可以完成,说明串行实现可以转化为两位的并行实现。图2和图3比较了串行实现和并行实现结构上的区别。具体到CRC每一位的值,在串

6、行实现中有上面的公式将串行的电路结构转换成了两位输入的并行电路结构,根据相应的校验公式,可理的位数为w,只需用相同的方法将r 推算到r 一级就可以了。i、ji、j-w对于算法CRC-16,如果计算的数据长度是100个字节,时钟频率为1MHz,串行计算的时间为800s,而16位并行输入的计算时间为50s。并行实现的计算速度是串行实现的w倍(w是并行数据输入的宽度),所以当并行输入的数据宽度比较大时,速度上的差异是非常明显的。并行计算的缺点是使用了多级组合逻辑的反馈,将产生较大的门延迟,特别是在计算时钟的频率很高时,时钟周期非常小,对时延的要求比较高,比如实现32位并行输入的CRC-32,会产生31次异或操作,电路的门延时可能会很大,而超出系统的时延限度,这取决于组合电路的具体结构。组合逻辑在综合的时候,将产生图4的电路结构 。5图4所示结构的组合逻辑的延时是各个异或门的累加,异或次数多了以后,延时是很大的,所Z=(AB)(CD)(EF),电路的功能不变,但综合出的电路结构如图5的延时分散到多个并行的分支上,将门延时从5级降低到3级。对于w位数据的异或操作,图4的结构将产生w级门延时,图5的结构将产生logw(表示取小数部分不等于0就加1)级12门延时,优化后的结构的延时以指数级减少。4结束语CRC现了CRC的并行计算。并行实现方式适