还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
CRC循环冗余校验原理及FPGA实现姚树渝|创建时间2013年06月19日14:07|浏览220|评论0标签管理
13.1 基本CRC循环冗余校验原理介绍循环冗余码校验英文名称为CyclicalRedundancyCheck,简称CRC 它是利用除法及余数的原理来作错误侦测(ErrorDetecting)的实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置,接收装置对收到的数据重新计算CRC并与收到的CRC相比较,若两个CRC值不同,则说明数据通讯出现错误 根据应用环境与习惯的不同,CRC又可分为以下几种标准
①CRC-12码;
②CRC-16码;
③CRC-CCITT码;
④CRC-132码 CRC-12码通常用来传送6-bit字符串 CRC-16及CRC-CCITT码则用是来传送8-bit字符,其中CRC-16为美国采用,而CRC-CCITT为欧洲国家所采用 CRC-132码大都被采用在一种称为Point-to-Point的同步传输中
1.CRC特点CRC是种常用的检测错误的循环码,它能够榆测出如下错误
(1)突发长度小于r的突发错误
(2)大部分突发长度等于r十l的错误,其中不可检测的这类错误只占2-(r-1)
(3)大部分突发K度大于r+1的错堤,其中不可检测的这类错误只占2-r
(4)所有奇数个错误 CRC检错能力极强,开销小,易于用编码器及检测电路实现从其检错能力来看,它所不能发现的错误的几率仅为
0.0047%以下从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式因而,在数据存储和数据通讯领域,CRC无处不在著名的通讯协议X.25的FCS帧检错序列采用的是CRC-CCITT,WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC132,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段
2.CRC生成原理 CRC循环码即在m位信息码后再拼接r位的校验码,整个编码长度为n位,因此这种编码又叫n,k码对于一个给定的n,k码,可以证明存在一个最高次幂为n-k=r的多项式gx根据gx可以生成后位信息的校验码,而gx叫做这个CRc码的生成多项式校验码的具体生成过程为 假设发送信息用数据多项式mx表示,将mx左移n一k位,则可表示成,nz×2n-k这样mx的右边就会空出n一k位,即校验码的位置通过mx×2n-k除以生成多项式gx得到的商Qx和余数rx,其中余数rx就是校验码即 在发送端发送数据时余数加到信息码之后一同发出,将一组信息码和余数组成的数据块称为一个码元,设为Tx,则有 在接收端任一组多项式Tx都应被生成多项式gx整除,如果传输中未发生错误,则接收码元与发送码元相同,故接收的码元必定能被gx整除;若码元在传输中发生错误,则接收的码元可能除不尽而有余数,因此我们就以余数是否为零来判断接收码元中有无错误可能有错误的码元正好也被gx整除,这是CRC校验无力消除的,但通过选择多项式gx和增加冗余位数,使余数rx多项式的位数增多,来降低发生这种错误的概率
3.生成多项式的选择 生成多项式gx是构成CRC校验码的关键它的选取并不是任何一个多项式都可以作为生成多项式的,从检错与纠错的要求出发,生成多项式应能满足下列要求1任何一位发生错误都应使余数不为0;2不同位发生错误应当使余数不同;13应满足余数循环规律 CRC有多种国际标准,各种标准如下 CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于愚是为gz的阶数的突发错误所以CRc的生成多项式的阶数越高,误判的概率就越小
13.2CRC循环冗余码FPGA设计思想
1.编码电路的设计思想 编码电路的功能是己知信息数据位和生成多项式,要得到对应的CRC码字CRC码是系统码,对一个合法的CRC码字前面部分是原始信息位,后面部分为校验位部分因此,若能求解出校验位,把它与原始数据组合即可得到CRC码现已知mx,Gx,要求Rx,用X*mx除以Gx,它的余式即为XRx用二进制数表示,即将原始信息位后添r个0后的数据除以生成多项式对应的二进制数,所得余数即是校验位
2.解码电路的设计思想 一个合法的CRC码的多项式,它应该能被Gx整除据此,现对一个位长为n的数据段可能不是一合法CRC码,其多项式除以Gx,若其余数为零,说明该码字是合法的,取出其前面部分即为发端发送的有效数据,即完成解码;若余数不为0,则该码字出错,接收方可以告知发方重发,或进行纠错后再解码实际上,对任意的CRC码都能纠正一个错误
3.软件及硬件实现方法一般有以下几种软件实现方法逐位运算法则是用简单的软件编程来实现CRC编码,完成这种编码的原理同使用线性反馈移位寄存器的硬件方法雷同假定监督位已储存在称之为CRC的寄存器中,则逐位运算法则的实现步骤可归纳如下
①给CRC寄存器赋值为0
②如果CRC寄存器中最左边的1位是”l”,则移人下一个消息位,并且用码的生成多项式对CRC寄存器进行模2相加;否则,只移人下一个消息位
③重复第2步,直到一帧消息码的所有位都被移人为止标准查找表运算法对所有增加了a位组合的CRC编码进行预处理,然后在查找表中找出对应的值作为CRC编码的监督位假设监督位已储存在称之为CRC的寄存器中,则标准查找表运算法则的软件实现步骤归纳如下
①给CRC寄存器赋值为0,即设置rn--k一1,....,ro位为0
②用右移了n—k—a位的CRC寄存器的内容对a个输入位进行模2相加,即用rn-k-
1....ro进行模2相加
③在查找表中找出相应的值,并且用左移了a位的CRC寄存器的内容对其进行模2相加,即用rn-k-
1....ro进行模2相加,然后代替原CRC寄存器的内容
④重复第二和第三步,直到所有的信息位都移人为止一般有以下几种硬件实现方法1采用LSFR(线性反馈移位寄存器组)来完成,这种方法简单,但每次只能处理一位二进制数据,也很难以满足速度较高的场合2CRC校验码的并行算法有查表法及基于查表法而导出的一些方法,但这些方法均需要存储长度较大的CRC余数表,并且随着并行位数的增加,余数表的长度按指数增加,其现实性亦随之大大降低.13根据线性时不变系统的特性推出了用于计算CRC校验码计算的转换矩阵,但变换矩阵的推导方法过于烦琐4按字节运算方法,它直接推导出CRC校验码与输入数据和生成多项式的逻辑关系,然后直接运算得出CRC校验码,这种方法直接、简洁
13.3CRC循环冗余码FPGA实现 CRC—16校验码,采用的生成多项式为gx=x16+x15+x2+l,依据上述的推导公式的结论设计出逻辑电路见下图,在图中有16级移位寄存器和13个异或门,实现CRC码的计算初始化时每一位寄存器都清零,然后每输入一位数据,16位移位寄存器按照异或逻辑由低到高进行移动1位,直到一组校验数据结束,此时,16位移位寄存器的内容就是该组数据的CRC-16的校验位 这里采用按字节运算方法,它直接推导出CRC校验码与输入数据和生成多项式的逻辑关系,然后直接运算得出CRC校验码添加testbench 进行功能测试 从仿真结果可知,当输入为1001100110011001时,通过CRC校验得到的校验位如上图所示由于串行CRC运算,当前的CRC余数值只与当前信息码的最前一位的输入值和前一状态的CRC余数值有关,所以,当输入到最后一位信息位时,此时的校验位即为最终的校验位这里输入的信息为周期信号,所以当第16位到达后,从图中可以看到校验位为0101010101011100,这与通过计算所得的结果一致,验证是正确的 通过综合后的RTL图以及内部详细的电路结构如上图在板上调试时,需要添加一个信号产生模块source以下是对Source添加testbench后的功能仿真波形 即输入信号设为1011001111001101 这里需要对时钟进行设置,这里用的是13E的实验板,所以CLK设为C9,见上图加核后,综合后RTL图如下所示 这里由于要观察编解码后的波形,所以要添加一个ILA核,那么就要添加两个ICON核对ILA核以及VIO核进行控制通过下载到实验板上,chipscope在线调试结果如下VIO捕捉到的波形如上,当复位信号为0时,产生输入信号,同时,CRC校验位也相应发生变化 以上是Ila核捕捉的CRC校验位的校验位板上调试代码modulecrc_mainclksig_s1crc_regcrc_s ;inputclk;output[15:0]sig_s1;output[15:0]crc_reg;output[0:0]crc_s;wirereset;wire[15:0]sig_s1;wire[15:0]sig_jie;wire[35:0]control0control1;wire[32:0]data;wire[0:0]async_out;wire[32:0]async_in;sources
1.clkclk.resetreset.sig_ssig_s1;crcv
1.clkclk.resetreset.xsig_s
1.crc_regcrc_reg.crc_scrc_s;iconicon.CONTROL0control0 .CONTROL1control1 ; assigndata[15:0]=sig_s1[15:0];assigndata[31:16]=crc_reg[15:0]; assigndata[32:32]=crc_s[0:0]; ilamy_ila .CLKclk .CONTROLcontrol0 .TRIG0reset .DATAdata ; assignreset=async_out
[0];assignasync_in[15:0]=sig_s1[15:0];assignasync_in[31:16]=crc_reg[15:0];assignasync_in[32:32]=crc_s[0:0]; viomy_vio .CONTROLcontrol1 .ASYNC_OUTasync_out .ASYNC_INasync_in;endmoduleCrc编码代码modulecrc clkresetxcrc_regcrc_s;inputclk; inputreset; inputx; //串行输入数据output[15:0]crc_reg;//CRC编码输出outputcrc_s; //CRC同步信号,标志着一帧编码的结束reg[15:0]crc_reg;regcrc_s;reg[3:0]cnt;wire[15:0]crc_enc;always@posedgeclkbegin if!resetbegin crc_reg=0; cnt=0; end elsebegin crc_reg=crc_enc; cnt=cnt+1; ifcnt==0 crc_s=0; else crc_s=1; endendassigncrc_enc
[0]=crc_reg
[15]^x;assigncrc_enc
[1]=crc_reg
[0];assigncrc_enc
[2]=crc_reg
[1]^crc_reg
[15]^x;assigncrc_enc[14:3]=crc_reg[13:2];assigncrc_enc
[15]=crc_reg
[14]^crc_reg
[15]^x;endmodule输入的数据产生代码modulesource clkresetsig_s;inputclkreset;outputsig_s;regsig_s;reg[1:0]count;reg[3:0]addr;parameterCOUNT=3d2;always@posedgeclkbeginifreset begin addr=3d0; count=3d0; endelse begin count=count+1; ifcount==COUNT begin addr=addr+1; end elseaddr=addr; end endalways@posedgeclkbegincaseaddr[3:0] 4b0000:sig_s=1; 4b0001:sig_s=0; 4b0010:sig_s=1; 4b0011:sig_s=1; 4b0100:sig_s=0; 4b0101:sig_s=0; 4b0110:sig_s=1; 4b0111:sig_s=1; 4b1000:sig_s=1; 4b1001:sig_s=1; 4b1010:sig_s=0; 4b1011:sig_s=0; 4b1100:sig_s=1; 4b1101:sig_s=1; 4b1110:sig_s=0; 4b1111:sig_s=1; endcaseendendmodule
13.4 小结 这种基本的串行运算电路仅用了移位寄存器和异或门,占用的资源很少,实现原理比较简单,不论其输人数据是8bit、16bit,还是32bit,其算法程序均不需要修改但是,该算法输出CRC校验结果需要较长时间的延迟,需要将信息码单比特输入,经过移位方能输出编码结果;而并行算法输出CRC校验结果虽然算法复杂,但是需要的时间很短,信息码一次并行输入,经过必要的处理时间即可输出编码结果,大大缩短了处理时间,具有很大的优越性 实际上,串行算法运算速度的提高完全依靠于时钟的速度,相应地也增加了实现的难度,所以在现实中通常采用通过改进,采用并行处理方法按字节并行计算的思路是模拟串行计算电路的计算过程,从而推导出每次并行处理一个字节后的CRC校验码与当前输入字节和CRC寄存器前一状态的关系。