CRC算法的MATLAB仿真

精选优质文档-倾情为你奉上通信系统综合设计与实践 题目CRC算法的MATLAB仿真 院（系）名称信息工程学院 专业名称通信工程 姓名学号 指导教师 2012年 5 月 22 日CRC算法的MATLAB仿真设计摘 要数据通信技术是计算机网络技术发展的基础，已经为成现代生活中必不可少的一部分。但通过通信信道传输的数据往往会有差错的产生，而且差错的产生是不可避免的，我们的任务是分析循环码算法的实现原理及研究检查是否出现差错及如何纠正差错。循环冗余码（CRC）是目前应用最广的检错纠错编码方法之一。本文论述了CRC的算法原理及其在数据通信中的作用，并提出了用MATLAB程序语言实现CRC校验的程序设计。关键词：循环码 CRC-16 查表法纠错目录1. CRC算法的基本工作原理循环冗余码CRC检验技术广泛应用与测控及通信领域，其基本原理是：利用线性编码理论，在发送端根据要传送的K位二进制码序列，以一定的规则产生一个校验用的监督码（即CRC码）r位，并附在信息位后边，构成一个新的二进制码序列数共（k+r）位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。2. CRC算法仿真的意义在有噪声的信道中传输信息会产生差错，为了减少差错需要在传输的信息序列中引入冗余码来增加通信系统的可靠性。为了减少接收错误码元的数量，需要在发送码元序列中加入监督码元。这样做的结果是发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大。但在通信系统中，可靠性与有效性是对矛盾，要求有效性提高，必然使每个码元所占的时间缩短，从而受干扰和产生错误的可能性增大，可靠性降低；要提高信息的可靠性，又使信息速率变慢有效性降低。因此，合理的解决有效性与可靠性这对矛盾，是正确设计一个通信系统的关键问题之一，为保证传输过程的可靠性，就需要对通信过程进行差错控制。循环冗余校验码CRC（cyclic redundancy check）是一种高效率且可靠的方法，由线性分组码分支而来的，是一种通过多项式除法检测错误的方法，一方面它有很强的检测能力，而是它的编码器电路及错误检测器电路都很容易实现，它的优点使它在通信系统中得到了广泛的应用。3. 仿真过程在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（n,k）。对于一个给定的（n,k）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G（x）可以生成K位信息的校验码，而G（x）叫做这个CRC码的生成多项式。设信息多项式为C（x），将C（x）左移R位，则可表示成C（x）×2n；这样C（x）的右边就会空出R位，这就是校验码的位置。通过C（x）×2n除以生成多项式G（x）得到的余数就是校验码。判断余数是否为零。4. 纠错方法循环冗余校验(CRC)是一种重要的线性分组码，不但具有极强的检测能力，而且编解码器采用硬件实现比较简单，特别适合于检测错误，同时还能纠正单比特错误。利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位校验码，附在原始信息后边，构成一个共k+r位的新的二进制码序列数，然后发送出去；在接收端，根据信息码和校验码之间所遵循的规则进行检验，以确定传送中是否出错。在差错控制理论中，这个规则被称为生成多项式。根据r的阶数，可以构造CRC4，CRC16，以及CRC32等不同的生成多项式。通过CRC校验码对整个帧结构进行保护是对随机和突发错误进行检测的最好方法。 目前在传输系统中使用最广泛的数据报文封装结构为通用帧结构(GFP)。GFP在接收定帧时不采用特殊字节进行帧对齐，而是通过对GFP核心帧头的长度域PLI进行CRC16计算，从而判断下一GFP帧的开始来达到定帧的目的。在发送的时候，这个长度域加上其CRC16校验和构成了GFP的核心帧头。除了核心帧头以外，GFP的静荷类型帧头同样也是收到CRC16的保护。在GFP中，无论是核心帧头中的长度域还是静荷类型帧头中的类型域对于GFP来说都是非常重要的信息，因此在标准中都对其定义了单比特误码的纠错要求。具有同样检错和纠错要求的标准还有RFC2823。令T(x)=an-1xn-1+an-2xn-2+a2x2+a1x1+a0为发送的信息序列，这里采用数组T=an-1,an-1,a2,a1,a0来表示，其中ai=0 or 1,0in-1。同时令接收信息序列表示为T'(x)=bn-1xn-1+bn-2xn-2+b1x1+b0，这里仍然采用数组来表示，其中bi=0 or 1,0in-1。这样定义误差序列E=T'-T=en,en-1,e1,e0。误差序列第i位取值为当ei=0时，表示i位无错；当ei=1时，表示i位出错。接收端校验码计算值可以通过下式得到：其中，H为生成多项式构成的生成矩阵。从高等代数基本理论可以知道，生成矩阵一定是线性无关的，因此T*HT=0，接收端校验码计算值只与误差序列和生成多项式有关，与被保护的信息序列本身无关。换句话说，生成多项式和误码决定了接收端的校验值计算结果。同样，假设Ttr=an-1,an-2,a2,a1,a0为需要传递的信息序列，CRCtr为该信息序列的CRC16校验码，那么发送序列为(Ttr<<16)&(CRCtr)；同理，接收端的接收序列为(Trx<<16)&(CRCrx)，其中Trx=a'n-1,a'n-2,a'2,a'1,a'0为接收的信息序列，CRCrx为接收的CRC16校验码。同时，接收端会对整个接收的数据帧进行校验，如果传输过程中没有任何错误发生，接收端计算得到的CRCcal应该等于CRCrx；如果出现传输错误时(有可能是信息序列出现误码，也有可能是发送的CRC本身出现传输误码)，CRCcal将不等于CRCrx。正如前面描述，CRC16是可以实现单比特误码纠错的一种线性分组编码，因此无论该单比特错误是出现在信息域，还是在作为冗余信息的CRC16校验码中，接收端都可以实现无误接收。只是当单比特误码出现在信息域时，接收端必须要将其校正过来，而如果该单比特误码出现在CRC16校验码中，则没有必要将其校正过来。根据前面给出的结论，接收端计算得到的校验码CRCcal仅仅与传输错误序列和生成多项式相关。观察CRC16并行计算公式，如果输入数据中Di出现单比特错误的话，其对应的CRC中对应的比特位将出现错误。例如，数据比特D1将影响校验码中的1、6、13位，这意味着D1如果出现错误，那么校验码的第1、6、13位的结果将反相。既然无错情况下计算得到的CRCcal等于CRCrx，那么下一个CRC计算值将等于0。如果出错的话，那么得到的CRC计算值将等于0X2042。可以证明，每一个数据比特单比特误码出现的CRC计算值都是唯一的，因此我们将数据单比特误码时的CRCcalCRCrc总结为下表同样，除了数据比特可能出现误码以外，接收的CRC校验码也可能出现误码。当接收的CRC校验码出现某位误码时，显然最终得到的CRC计算值在该比特位置上将反相，因此，当接收的CRC校验码出现单比特误码时，其CRCcalCRCrc如下表所示。因此，对CRC16单比特误码纠错就变成了通过CRC计算值找到相应的单比特出错序号。此外，还可以同时区别错误来源，如果是数据单比特出错，则需要完成单比特纠错；如果是校验码出错，则无需对校验码进行单比特纠错。5. 仿真方法CRC校验码生成：初始化msg和CRC-16的值对序列msg左移补零对多项式的除，返回余数对除法的余数做模二运算，得到CRC校验码在原序列后面加上CRC校验码CRC校验：对给定信息码与多项式做除，返回余数对余数做模二运算判断余数与表中的数值是否相等返回结果代码如下：function crc( msg )if nargin = 0msg = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 ; end msg1 = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 ;generator = 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1; c = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; multip = conv(c,msg);divid, remainder=deconv(multip,generator); remainder=mod(remainder(end-15:end),2);code=msg,remainder;deCRC16(code,generator); function deCRC16(code,generator) divid, remainder=deconv(code,generator); remainder=mod(remainder(end-15:end),2);% data = 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1; if isequal(remainder,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0); msgbox('CRC',num2str(code(1:16),'校验正确！'); elsemsgbox('CRC校验错误:',num2str(remainder),'');% switch num2str(remainder)% case num2str(data)% code(1)=code(1);% msgbox('CRC',num2str(code(end-15:end),'第1位错误');% case isequal(remainder,0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0)% code(2)=code(2);% msgbox('CRC',num2str(code(end-15:end),'第2位错误');% case isequal(remainder,0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0)% code(3)=code(3);% msgbox('CRC',num2str(code(end-15:end),'第3位错误');% case isequal(remainder,1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0)% code(4)=code(4);% msgbox('CRC',num2str(code(end-15:end),'第4位错误');% case isequal(remainder,0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1)% code(5)=code(5);% msgbox('CRC',num2str(code(end-15:end),'第5位错误');% case isequal(remainder,0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0)% code(6)=code(6);% msgbox('CRC',num2str(code(end-15:end),'第6位错误');% case isequal(remainder,0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0)% code(7)=code(7);% msgbox('CRC',num2str(code(end-15:end),'第7位错误');% case isequal(remainder,1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0)% code(8)=code(8);% msgbox('CRC',num2str(code(end-15:end),'第8位错误');% case isequal(remainder,0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1)% code(9)=code(9);% msgbox('CRC',num2str(code(end-15:end),'第9位错误');% case isequal(remainder,0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0)% code(10)=code(10);% msgbox('CRC',num2str(code(end-15:end),'第10位错误');% case isequal(remainder,1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0)% code(11)=code(11);% msgbox('CRC',num2str(code(end-15:end),'第11位错误');% case isequal(remainder,1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1)% code(12)=code(12);% msgbox('CRC',num2str(code(end-15:end),'第12位错误');% case isequal(remainder,0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1)% code(13)=code(13);% msgbox('CRC',num2str(code(end-15:end),'第13位错误');% case isequal(remainder,0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0)% code(14)=code(14);% msgbox('CRC',num2str(code(end-15:end),'第14位错误');% case isequal(remainder,0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 0)% code(15)=code(15);% msgbox('CRC',num2str(code(end-15:end),'第15位错误');% case isequal(remainder,0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0)% code(16)=code(16);% msgbox('CRC',num2str(code(end-15:end),'第16位错误');% otherwise% msgbox('CRC校验位错误:',num2str(remainder),'');% end end% if isequal(remainder,0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1);% msgbox('CRC',num2str(code(end-15:end),'第1位错误');% else% msgbox('未知错误，请重传');% end 6. 仿真结果的预计接收端收到了CRC码后用生成多项式G（x）去做模二运算，若得到余数为0，则码字无误。如果有一位出错，则余数不为0。且余数与出错位的对应关系至于码制及生成多项式有关，而与信息位无关。7. 仿真结果的意义对于接收到的信息码中，如果有一位比特发生错误，则G（x）只要有两项，就可以检测出任何单位比特的错误；如果有长度kr=G(x)次方的次数的错误，选择G（x），使x不是G（x）的一个因子，既然kr ，G（x）不可能是一个更低次方的多项式的因子。那么长度为k的突发错误都可以检测出来；如果有长度kr=G(x)的次方的错误，考虑k-1=r，那么损坏的比特位组合就有2r-1种，若假设所有组合以相同几率出现，那么组合与G（x）项精确匹配的几率为1/2r-1,，也就是说错误漏检率为1-2r-1。总之CRC是一种很强的纠错方式，CRC-32多项式能以（232-1）/232的概率检测所有长度小于等于33的突发错误，这个准确率可以说是几乎不发生错误，又由于其实现简单，所以在实际中得到了广泛的应用专心-专注-专业