CRC循环冗余校验

1、13 CRC循环冗余校验原理及FPGA实现13.1基本CRC循环冗余校验原理介绍循环冗余码校验英文名称为 Cyclical Redundancy Check ，简称 CRC。 它是利用除法及余数的原理来作错误侦测（ Error Detecting ）的。实 际应用时，发送装置计算出CRC值并随数据一同发送给接收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个 CRC值不同，则说明数据通讯出现错误。根据应用环境与习惯的不同，CRC又可分为以下几种标准： CRC-12码； CRC-16码； CRC-CCITT 码； CRC-132码。CRC-12码通常用来传送 6-bit字符

2、串。CRC-16及 CRC-CCITT码则用是来传送8-bit 字符，其中 CRC-16为美国 采用，而CRC-CCITT为欧洲国家所采用。CRC-132码大都被采用在一种称为Poi nt-to-Poi nt的同步传输中。1. CRC 特点CRC是种常用的检测错误的循环码，它能够榆测出如下错误：（ 1）突发长度小于 r 的突发错误。（2） 大部分突发长度等于 r 十 l 的错误，其中不可检测的这类错误只占2-（r-1）。（3） 大部分突发 K 度大于 r+1 的错堤，其中不可检测的这类错误只占2-r。 （ 4）所有奇数个错误。CRC 检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能

3、 力来看，它所不能发现的错误的几率仅为 0.0047%以下。从性能上和开销上考虑， 均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域， CRC无处不在：著名的通讯协议X.25的FCS（帧检错序列）采用的是CRC-CCITT， Win RAR、NERO、ARJ、LHA等压缩工具软件采用的是 CRC132,磁盘驱动器 的读写采用了 CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错 手段。2. CRC生成原理CRC循环码即在m位信息码后再拼接 r位的校验码，整个编码长度为n位，因此这种编码又叫 （n ， k） 码。对于一个给定的 （n ， k） 码，可以证明存

4、 在一个最高次幂为 n-k=r 的多项式 g（x） 。根据 g（x） 可以生成后位信息的校验码，而g(x)叫做这个CRc码的生成多项式。校验码的具体生成过程为:假设发送信息用数据多项式m(x)表示，将m(x)左移n k位，则可表示成，n(z) x 2n-k。这样m(x)的右边就会空出n k位，即校验码的位置。通过m(x) x 2n-k ,除以生成多项式 g(x)得到的商Q(x和余数r(x)，其中余数 r(x)就是校验码。即：X 2E"r在发送端发送数据时余数加到信息码之后一同发出，将一组信息码和 余数组成的数据块称为一个码元，设为T(x)，则有在接收端任一组多项式T(x)都应被生成多

5、项式 g(x)整除，如果传输中未发生错误，则接收码元与发送码元相同，故接收的码元必定能被g(x)整除；若码元在传输中发生错误，则接收的码元可能除不尽而有余数，因此 我们就以余数是否为零来判断接收码元中有无错误。可能有错误的码元正 好也被g(x)整除，这是CRC校验无力消除的，但通过选择多项式g(x)和增加冗余位数，使余数 r(x)多项式的位数增多，来降低发生这种错误的概率。3. 生成多项式的选择生成多项式g(x)是构成CRC校验码的关键。它的选取并不是任何一个多 项式都可以作为生成多项式的，从检错与纠错的要求出发，生成多项式应 能满足下列要求：(1) 任何一位发生错误都应使余数不为0 ；(2)

6、 不同位发生错误应当使余数不同；(13)应满足余数循环规律。CRC有多种国际标准，各种标准如下：名称生成多项式愉记式亠应用举例CRC-16工饷+工站+宀180)5IHMSDLCCR(.riTTLr16 + jr12 + + 11021ISO HDIX ITl： X.25,V.34/V.41/V.42+忑加4-新+ '* + J2 + J- + 1(MC1UB7RARF IEEE B02 l-AN/FDDb【EEE 1394CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于愚(是为g(z)的阶数)的突发错误。所以 CRc的生成多项式的阶数越高，误判的概率 就越小。13.2 C

7、RC循环冗余码FPGA设计思想1. 编码电路的设计思想编码电路的功能是己知信息数据位和生成多项式，要得到对应的CRC码字。CRC码是系统码，对一个合法的CRC码字前面部分是原始信息位，后面部分为校 验位部分。因此，若能求解出校验位，把它与原始数据组合即可得到CR(码。现已知m(x)，G(x)，要求R(x)，用X*m(x)除以G(x)，它的余式即为X'R(x)。用 二进制数表示， 即将原始信息位后添 r 个 0 后的数据除以生成多项式对应的二进 制数，所得余数即是校验位。2. 解码电路的设计思想一个合法的CRC码的多项式，它应该能被 G(x)整除。据此，现对一个位长为 n的数据段(可能不

8、是一合法CR(码)，其多项式除以G(x)，若其余数为零，说明 该码字是合法的， 取出其前面部分即为发端发送的有效数据， 即完成解码； 若余 数不为 0，则该码字出错，接收方可以告知发方重发，或进行纠错后再解码。实 际上，对任意的CRC码都能纠正一个错误。3. 软件及硬件实现方法 一般有以下几种软件实现方法 ：逐位运算法：则是用简单的软件编程来实现CRC编码，完成这种编码的原理同使用线性反馈移位寄存器的硬件方法雷同。假定监督位已储存在称之 为CRC的寄存器中，贝燧位运算法则的实现步骤可归纳如下： 给CRC寄存器赋值为0 如果CRC寄存器中最左边的1位是” I”，则移人下一个消息位，并且用 码的生

9、成多项式对 CRC寄存器进行模2相加；否则，只移人下一个消息位 重复第 2 步，直到一帧消息码的所有位都被移人为止。标准查找表运算法：对所有增加了 a位组合的CRC编码进行预处理，然后 在查找表中找出对应的值作为CRC编码的监督位。假设监督位已储存在称之为CRC的寄存器中，贝U标准查找表运算法则的软件实现步骤归纳如下： 给CRC寄存器赋值为 0,即设置(r n-k 一 1，.，ro)位为0。 用右移了 (n k a)位的CRC寄存器的内容对 a个输入位进行模 2相加，即用 (r n-k-1,ro) 进行模 2相加。 在查找表中找出相应的值，并且用左移了a位的CRC寄存器的内容对其进行模2相加，

10、即用(r n-k-1,.,ro)进行模2相加，然后代替原 CRC寄存器的内容。 重复第二和第三步，直到所有的信息位都移人为止。 一般有以下几种硬件实现方法：(1)采用LSFR(线性反馈移位寄存器组)来完成，这种方法简单，但每次只能处理一位二进制数据，也很难以满足速度较高的场合。(2)CRC校验码的并行算法有查表法及基于查表法而导出的一些方法，但这些方法均需要存储长度较大的CRC余数表，并且随着并行位数的增加，余数表的长度按指数增加，其现实性亦随之大大降低(13)根据线性时不变系统的特性推出了用于计算CRC校验码,计算的转换矩阵，但变换矩阵的推导方法过于烦琐。(4) 按字节运算方法，它直接推导出

11、CR(校验码与输入数据和生成多项式的逻辑关系，然后直接运算得出CR(校验码，这种方法直接、简洁。13.3 CRC循环冗余码FPGA实现CRC 16校验码，采用的生成多项式为 g(x)=x16+x15+x2+l ，依据上述的 推导公式的结论设计出逻辑电路(见下图)，在图中有16级移位寄存器和13个异或门，实现 CRC码的计算。初始化时每一位寄存器都清零，然后每输 入一位数据，16位移位寄存器按照异或逻辑由低到高进行移动1位，直到一组校验数据结束，此时，16位移位寄存器的内容就是该组数据的CRC-16的校验位。J AVdk/H cnc.reg/ 15| "网/ 111 / rio)191

12、 pi71KI PI 丿W "Bl 丿2 丿ni这里采用按字节运算方法，它直接推导出CRC校验码与输入数据和生成多项式的逻辑关系，然后直接运算得出CRC校验码。添加test bench进行功能测试。010ioDoogo(Mooiioii stisuoSlO讯swSlO別Stf)SlOSIOstisuoSL1sti51:1WeO从仿真结果可知，当输入为100110011001100时，通过CRC校验得到的校验位如上图所示。由于串行CRC运算，当前的 CRC余数值只与当前信息码的最前一位的输 入值和前一状态的 CRC余数值有关，所以，当输入到最后一位信息位时， 此时的校验位即为最终的校验

13、位。这里输入的信息为周期信号，所以当第 16位到达后，从图中可以看到校验位为0101010101011100，这与通过计算所得的结果一致，验证是正确的。通过综合后的RTL图以及内部详细的电路结构如上图。在板上调试时，需要添加一个信号产生模块source,以下是对Source添加testbench后的功能仿真波形：Currnl SimulatiQn Time: 1000 msOus1 1 1100 nsI I I I I20CI Ii ns11IJ300 nsI I I I I400 ns500 ns600 ns1 1 1 1 1 1 1 1 1 1 1 1 1 1 17G0 ns I I I

14、I I8Mi I InsI I900 nslO&O r>51 1 1 1 1 1 1 1工!訥 空0D 4PERIOD31:0/32'hfl0000G14也! DLrn_C¥CUE05D P<OFFSETT31:OJ3_.匚32*h)iiOOOOOiA学1 C*1nrr丽mumr曲uuu曲Luu门WrwuwMreset0即输入信号设为1011001111001101File Edit View IOBi Ar essTindow HelpD U B这里需要对时钟进行设置，这里用的是13E的实验板，所以CLK设为C9,见上图 加核后，综合后RTL图如下所示。

15、这里由于要观察编解码后的波形，所以要添加一个ILA核，那么就要添加两个ICON核对ILA核以及VIO核进行控制。通过下载到实验板上，chipscope在线调试结果如下VIO捕捉到的波形如上，当复位信号为0时，产生输入信号，同时，CRC校验位也 相应发生变化。阖 WrtwftH rn- DFV：n(KC3S5DDE) UNIT:O胸IL All 01 A)痊盪恣安恣逐蕊克疣疾理址总恣盪龜盪叢蕊瑕总恣金 才|3BusJSignaiX0Q40BO120200)740羽 fl32Q36040D440W1.II."Ii.I iII . . . . ii IIDftCaP01：tL7i1nuiT

16、ijnimoiimuuimmBiiiniuiniiMnmiuMwiiiDat-aPDEtL8J11muiimmiiraimiiinuwmLiioinmnnmDataPoi:t 1QQuiummmu nijiiwniiiijiOTiiiL'Jiimi.iiii iuiuiMnniiiuM】muwm【DataPoEt2011iLniwmnnmmwMimiimmuiiRjniimraimmra.DataPDrt2111uuiununm ilwm 町 uni lutinniiii tuoniuiiiLUUFiBn00nuiunmraumMiiiimiuiiMnLimmminmmnmiiJ00D

17、tttaPott2411LioMimmmmiiMrrLLiLmnunwmnm!DataPDEt2500m ffi ni iimiiMiuiiiiiiiirjrjimimMiiiimnL lounuuininwiimnniuunii以上是Ila核捕捉的CRC校验位的校验位。板上调试代码：module crc_ma in(clk,sig_s1,crc_reg,crc_s)；in put clk;output15:0sig_s1;output15:0 crc_reg;output0:0 crc_s;wire reset;wire 15:0 sig_s1;wire 15:0 sig _jie;wire

18、35:0co ntrol0,co ntrol1;wire32:0 data;wire0:0as yn c_out;wire32:0as ync_in;source s1(.clk(clk),.reset(reset),sig_s(sig_s1);crc v1(.clk(clk),.reset(reset), .x(sig_s1),.crc_reg(crc_reg),.crc_s(crc_s);icon ico n(.CONTROL0(co ntrol0).CONTROL1(control1);assign data15:0=sig_s115:0;assign data31:16=crc_reg

19、15:0;assign data32:32=crc_s0:0;ila my_ila(.CLK(clk), .CONTROL(control0), .TRIG0(reset), .DATA(data);assign reset=async_out0;assign async_in15:0=sig_s115:0; assign async_in31:16=crc_reg15:0;assign async_in32:32=crc_s0:0;vio my_vio(.CONTROL(control1), .ASYNC_OUT(async_out), .ASYNC_IN(async_in);endmodu

20、leCrc 编码代码：module crc(clk, reset, x, crc_reg, crc_s);input clk;input reset;input x;/串行输入数据帧编码的结束output 15:0 crc_reg; /CRC 编码输出 output crc_s; /CRC 同步信号，标志着 reg 15:0 crc_reg;reg crc_s;reg 3:0 cnt;wire 15:0 crc_enc;always (posedge clk) beginif(!reset) begincrc_reg <= 0;cnt <= 0;endelse begincrc_r

21、eg <= crc_enc;cnt <= cnt +1; if(cnt = 0) crc_s <= 0;elsecrc_s <= 1;endendassig n crc_e ncO = crc_reg15Fx;assign crc_enc1 = crc_reg0;assig n crc_e nc2 = crc_reg1Acrc_reg15Ax;assign crc_enc14:3 = crc_reg13:2;assign crc_enc15 = crc_reg14Acrc_reg15Ax;endmodule 输入的数据产生代码： module source(clk,re

22、set,sig_s );input clk,reset;output sig_s;reg sig_s;reg1:O count;reg3:O addr;parameter COUNT=3'd2;always (posedge clk)beginif (reset)beginaddr<=3'dO; count<=3'dO;endelsebegincount<=count+1; if(count=COUNT) begin addr<=addr+1; endelse addr<=addr;endendalways(posedge clk)begincase(addr3:O)4'bOOOO:sig_s<=1;4'bOO