循环冗余校验码（CRC）的编译码仿真实现.doc

*实践教学* 兰州理工大学计算机与通信学院2014年秋季学期计算机通信课程设计 题 目：循环冗余校验码（CRC）的编译码仿真实现 专业班级： 通信工程（1）班 姓 名： 学 号： 指导教师： 成 绩： 摘 要CRC即循环冗余校验码（Cyclic Redundancy Check）是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查（CRC）是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。本次课程设计研究了纠错码及循环冗余校验码的原理， 以及利用MATLAB对其进行了编码和译码仿真，实现了CRC循环冗余校验码的编码及校验，在接收端收到通过校验的码，从而确定传输过程是否出错，得到的结论和理论上是一致的。关键词：循环冗余校验码；检错码； matlab软件目录前言1第1章 循环冗余校验码（CRC）的基本原理21.1 循环冗余校验码的基本介绍21.2 循环冗余校验码的几个基本概念21.3 循环冗余校验码的基本原理3第2章 MATLAB软件基本介绍52.1 MATLAB的介绍52.2 MATLAB的组成部分52.3 MATLAB的语言特点52.4 MATLAB的优势6第3章 循环冗余校验码（CRC）的详细设计73.1 CRC循环冗余校验码的编码模块73.2 CRC循环冗余校验码的译码模块73.3 CRC循环冗余校验码的性能分析83.4 CRC循环冗余校验码的生成器和校验器83.5 CRC循环冗余校验码的程序流程图93.6 运行结果及其分析10总结12参考文献13附录14致谢160前言 数据通信中的编码可以分为两大类，分别是信源编码和信道编码。在实际应用中，为了提高数据通信的可靠性而采取的编码称为信道编码，也称做抗干扰编码。一般来讲，数据通信要求传输过程中的误码率应该足够低，这样才能真正符合实际应用的具体要求，为了降低数据通信线路传输的误码率，通常有改善数据通信线路传输质量和差错检测控制两种方法。 实现差错检测控制的方法很多，CRC校验码是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。CRC校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来“确认信息”的困惑，所以对通信的可靠性检查就需要“校验”，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。循环冗余码校验英文名称为Cyclical Redundancy Check，简称CRC。CRC校验码码的作用是：发送方发送的数据发送给了接收方，但是由于在传输过程中信号干扰，可能出现错误的码，造成的结果就是接收方不清楚收到的数据是否就是发送方要发的数据，所以就有了CRC校验码。保证了发送跟接受的数据是否一样，要纠错的话，还需对软件进行设计，毕竟传输的是2进制，如果知道了哪一位出错了，可以把那一位取反，需要对软件进行优化。CRC也是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。它是利用除法及余数的原理来作错误侦测的。实际应用时，发送装置计算出CRC值并随数据一同发送给接收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个CRC值不同，则说明数据通讯出现错误。 本次课程设计主要设计（16，12）校验码的编码与解码，本次课程设计是介绍如何通过matlab软件，采用原理图输入法，分别完成相应的编码和解码；最后，检查编码解码过程是否发生错误，通过课程设计验证CRC校验码的编码译码过程。第1章 循环冗余校验码（CRC）的基本原理1.1 循环冗余校验码的基本介绍 CRC码是由两部分组成的，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码（CRC 码）r 位，并附在信息后边，构成一个新的二进制码序列数共 (k+r) 位，最后发送出去。在接收端，则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。 16 位的CRC 码产生的规则是先将要发送的二进制序列数左移16 位后，再除以一个多项式，最后所得到的余数既是CRC 码。求CRC 码所采用模2 加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。接收方将接收到的二进制序列数（包括信息码和CRC 码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误。1.2 循环冗余校验码的几个基本概念 1.2.1 多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。多项式包括生成多项式G(x)和信息多项式f(x)。如生成多项式为，可转换为二进制数码11011。而发送信息位 1111，可转换为数据多项式为。1.2.2 生成多项式 生成多项式是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。应满足以下条件： a、生成多项式的最高位和最低位必须为1； b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0； c、不同位发生错误时，应该使余数不同； d、对余数继续做模2除，应使余数循环。1.2.3 模2除（按位除） 第一步，要在数据位（被除数）后边补 0 ，0 的个数比除数（生成多项式）少一位；第二步，做除法，从被除数的头五位减去五位的除数。除数的每一位都与被除数的对应位在不涉及上一位的情况下独立进行减法（实际进行的是模 2 加）。在本此课程设计中，除数11101 与被除数的前五位10111进行的是模 2 加，得到1010 （余数 1 前面的 0 被省略）。在被除数中下一个没有使用过的比特接着被抄录下来，使得余数的位数和除数的位数相同。如果位数不够，在商位补0（这与一般除法相同），因此，下一步就是 11110 11001 ，结果是 111 ，依次类推。在二进制除法中，除数总是以 1 开头的，然后从上一次的被除数 / 余数中与除数位数相同的部分中减去除数，并且只能从最左位是 1 的被除数 / 余数中减去除数。每当被除数 / 余数的最左位是 0 时，就在该步骤中把 0 丢弃，再把被除数中的下一个未使用比特抄录下来填充余数，同时对应的商数位补一个零，并按上述方法进行二进制除法运算，一直重复这个过程直到被除数中所有比特都被使用过。1.3 循环冗余校验码的基本原理1.3.1循环冗余校验码的编码规则CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是： 1移位将原信息码序列(kbit)左移r位(k+r=n) 2相除运用一个生成多项式G(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。 非常简单，要说明的是：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是： 0+0=1+1=0,1+0=0+1=1 即异则真，非异则假。由此得到定理：a+b+b=a 也就是模2减和模2加真值表完全相同。 有了加减法就可以用来定义模2除法，于是就可以用生成多项式G(x)生成CRC校验码。1.3.2 CRC码生成和校验1.CRC码生成第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数。由此除法产生的余数就是循环冗余码校验码第三步：用从第二步得到的r个比特的CRC码替换数据单元末尾附加的r个0。如果余数位数小于r，最左的缺省位数为0。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以r个0作为CRC码替换余数所在的位置。产生的比特模式正好能被除数整除。2.CRC码校验到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。3应用举例发送端:例如：已知：信息码：1 1 0 1 0 0 1 1 0 1信息多项式：，生成码：1 1 0 0 1 0生成多项式：。解： 1）* 的积是对应的码字是1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 02) 积G(X)(按模二算法) 由计算结果知冗余码是1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0,CRC码（码字）就是1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0接收端：例如：已知：接受码字：1 0 1 0 0 1 1多项式：生成码：1011 生成多项式：(r=3) 求：码字的正确性。若正确，则指出冗余码和信息码。解：1) 用CRC 码（码字）除以生成码，余数为0 ，所以CRC 码（码字）正确。2) 因r=3，所以冗余码是：011，信息码是:1010。 第2章 MATLAB软件基本介绍2.1 MATLAB的介绍在当今30多个数学类科技应用软件中，就软件数学处理的原始内核而言，可分为两大类。一类是数值计算型软件，如 MATLAB、Xmath、Gauss等，这类软件长于数值计算，对处理大批数据效率高；另一类是数学分析型软件，如Mathematica、Maple等，这类软件以符号计算见长，能给出解析解和任意精度解，其缺点是处理大量数据时效率较低。MathWorks公司顺应多功能需求之潮流，在其卓越数值计算和图示能力的基础上，又率先在专业水平上开拓了其符号计算、文字处理、可视化建模和实时控制能力，开发了适合多学科、多部门要求的新一代科技应用软件MATLAB。经过多年的国际竞争，MATLAB 已经占据了数值型软件市场的主导地位。在MATLAB进入市场前，国际上的许多应用软件包都是直接以FORTRAN和C语言等编程语言开发的。这种软件的缺点是使用面窄、接口简陋、程序结构不开放以及没有标准的基库，很难适应各学科的最新发展，因而很难推广。MATLAB的出现，为各国科学家开发学科软件提供了新的基础。在MATLAB问世不久的20世纪80年代中期，原先控制领域里的一些软件包纷纷被淘汰或在MATLAB上重建。2.2 MATLAB的组成部分（1）开发环境(development Environment)：一组图形化用户接口工具和组件的集成：MATLAB桌面、命令窗口、命令历史窗口、编辑调试窗口及帮助信息、工作空间、文件和搜索路径等浏览器;（2）MATLAB数学函数库：(Math Function Library)基本函数：求和、正弦、余弦和复数运算等；特殊函数：矩阵求逆、矩阵特征值、贝塞尔函数和快速付里叶变换等;（3）MATLAB 语言：(MATLAB Language)一种高级编程语言，包括控制流的描述、函数、数据结构、输入输出及面对对象编程；（4）句柄图形：(Handle Graphics) 可以对各种图形对象进行更为细腻的修饰和控制，建立完整的图形界面的应用程序;（5）应用程序接口：(Applied Function Interface) MATLAB的应用程序接口允许用户使用C或FORTRAN语言编写程序与MATLAB连接。2.3 MATLAB的语言特点语言简洁紧凑，使用方便灵活，库函数极其丰富。MATLAB程序书写形式自由，利用其丰富的库函数避开繁杂的子程序编程任务，压缩了一切不必要的编程工作。由于库函数都由本领域的专家编写，用户不必担心函数的可靠性。可以说， MATLAB甚至具有一定的智能水平，比如上面的解方程，MATLAB会根据矩阵的特性选择方程的求解方法，所以用户根本不用怀疑MATLAB的准确性。运算符丰富。由于MATLAB是用C语言编写的，MATLAB提供了和C语言几乎一样多的运算符，灵活使用MATLAB的运算符将使程序变得极为简短，具体运算符见附表。MATLAB既具有结构化的控制语句（如for循环、while循环、break语句和if语句），又有面向对象编程的特性。语法限制不严格，程序设计自由度大。例如，在MATLAB里，用户无需对矩阵预定义就可使用。程序的可移植性很好，基本上不做修改就可以在各种型号的计算机和操作系统上运行。MATLAB的图形功能强大。在FORTRAN和C语言里，绘图都很不容易，但在MATLAB里，数据的可视化非常简单。MATLAB还具有较强的编辑图形界面的能力。MATLAB的缺点是，它和其他高级程序相比，程序的执行速度较慢。由于MATLAB的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。功能强劲的工具箱是MATLAB的另一重大特色。MATLAB包含两个部分：核心部分和各种可选的工具箱。核心部分中有数百个核心内部函数。其工具箱又可分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能、图示建模仿真功能、文字处理功能以及与硬件实时交互功能。功能性工具箱能用于多种学科。而学科性工具箱是专业性比较强的，如control、toolbox、signal processing toolbox、communication toolbox等。这些工具箱都是由该领域内的学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高、精、尖的研究。2.4 MATLAB的优势（1）友好的工作平台和编程环境（2）简单易用的程序语言（3）强大的科学计算机数据处理能力（4）出色的图形处理功能（5）应用广泛的模块集合工具箱（6）实用的程序接口和发布平台（7）应用软件开发（包括用户界面） 第3章 循环冗余校验码（CRC）的详细设计3.1 CRC循环冗余校验码的编码模块循环冗余校验码CRC它是利用除法及余数的原理来作错误侦测（Error Detecting）的。实际应用时，发送装置计算出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的同步传输中本设计中CRC校验码的n=16,k=12，则K位要发送的信息位可对应于一个(k-1)次多项式f(X),r位冗余位则对应于一个(r-1)次多项式R(X)，由r位冗余位组成的n=k+r位码字则对应于一个(n-1)次多项式T(X)=G(x)*f(X)+R(X)。其编码过程为：（1）移位将原信息码（kbit）左移r位（k+r=n)（2）相除运用一个生成多项式G(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。3.2 CRC循环冗余校验码的译码模块译码是该编码能否得到实际应用的关键所在。译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。根据不同的纠错或检错目的，循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。 用于纠错目的的循环码的译码算法比较复杂，而用于检错目的循环码，一般使用ARQ通信方式。检测过程也是将接受到的码组进行除法运算，如果除尽，则说明传输无误；如果未除尽，则表明传输出现差错，要求发送端重发。用于这种目的的循环码经常被称为循环冗余校验码，即CRC校验码。CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。在通过MODEM传输文件的协议如ZMODEM、XMODEM协议中均用到了CRC校验技术。在磁盘、光盘介质存储技术中也使用该方法。 在译码过程中到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。3.3 CRC循环冗余校验码的性能分析一般情况下，r位生成多项式产生的CRC码可检测出所有的单个错误和随机两位错误、奇数个错和长度小于等于k位的突发错误。例如，对于r=16的情况，就能检测出所有突发长度小于等于16的突发错以及99997%的突发长度为17的突发错和99998%的突发长度大于17的突发错。所以CRC码的检错能力还是很强的。这里，突发错误是指几乎是连续发生的一串错，突发长度就是指从出错的第一位到出错的最后一位的长度(但是，中间并不一定每一位都错)。 3.4 CRC循环冗余校验码的生成器和校验器CRC循环冗余校验码的生成器和校验器如图1所示： r bit r+1 bit 余数 r bit CRC校验码 数据 00.0 G(X)数据数据 0接收，非0拒绝 数据 余数 G(X) 发送方 接收方 图1 CRC循环冗余校验码的生成器和校验器3.5 CRC循环冗余校验码的程序流程图CRC循环冗余校验码的程序流程图如图2所示：余数是否为零 输出接收端的码 结束输出erro=1开始初始化，随机产生信息码并输出 添加冗余比特位 循环计算长除 是否除完 合成编码序列输出 用合成码长除生成多项式 是否除完 NY NY NY 图2 CRC循环冗余校验码的程序流程图3.6 运行结果及其分析3.6.1 MATLAB的运行结果正确译码时MATLAB的运行结果如图3所示：图3 MATLAB的运行结果译码发生错误时MATLAB的运行结果如图4所示：图4 MATLAB的运行结果3.6.2 结果分析CRC校验的基本思想是利用线性编码理论，在发送端根据要传送一个n比特的帧或报文，发送器生成一个r比特的序列，称为帧检验序列（FCS）。这样形成的帧将由（n+r）比特组成。这个帧刚好能被某个预先规定的数整除。接收器用相同的数去除外来的帧，结果无余数，则认为无差错。 循环冗余校验与奇偶校验不同，后者是一个字符校验一次，而前者是一个数据块校验一次。在同步通信中，几乎都使用这种校验方法。 二进制多项式的加减运算为模2加减运算，即两个码多项式相加时，对应系数进行模2加减。所谓模2加减就是各位做不带进位、借位的按位加减。这种加减运算实际上是逻辑上的异或运算，即加法和减法等价。信息多项式和余数多项式可以合并成一个新的多项式（称为循环码的码多项式），则该多项式是生成多项式的整数倍，即能被生成多项式整除。根据这一原理，在发送端用信息码多项式除以生成多项式所得的余数多项式就是所要加的监督位。将循环码的码多项式除以生成多项式，若能除尽，说明传输正确，否则说明出错。CRC校验的关键是如何求出余数，此余数即为校验码（CRC校验码）。以前用数字电路来实现，而现在可以用计算机来完成。为了传输的正确性，在接收端要有一个CRC检验器。它的功能和发生器一样，当收到CRC冗余校验码后，做同样的模2除法（注意，这里采用的生成多项式一定要与发送端相同）。如果余数是0，则说明传输正确；否则，传输错误，应重传。本次课设通过对（16，12）循环码的编译码的设计与仿真得出仿真过程得到的结论与理论是一致的。总结CRC是现代通信领域的重要技术之一。掌握CRC的算法与实现方法，在通信系统的设计、通信协议的分析以及软件保护等诸多方面，能发挥很大的作用。在此次课设中，我学习了matlab仿真软件的运用，我们通过动手实践操作，进一步学习和掌握了有关CRC原理的知识，加深了对纠错技术的认识。在设计时我们根据课题要求，复习了相关知识，还查阅了相当多的资料，这也在一定程度上拓宽了我们的视野，丰富了我们的知识。做设计的过程中，我有许多不懂得地方，在老师的指导下我一步步的解决问题完成论文，在完成过程中老师指导我去怎么选择资料，如何去利用网络资源，在这个学习的过程中，我了解到MATLAB的实用价值，更深的理解循环冗余校验码的原理。这次课程设计，使我坚定了我在以后的学习中要认真学好基础知识，不能只做表面工作。读书不仅是要读书还要读活书，把学到的知识灵活地运用到实践中去，达到学有所用的地步。通过这段时间的亲身经历，我感觉自己学到了：收集、整理资料、共同协作、分析及处理问题等许多方面的知识。这次课程设计还让我们知道了，我们平时所学的知识如果不加以实践的话等于纸上谈兵。课程设计主要是我们理论知识的延伸，它的目的主要是要在设计中发现问题，锻炼我们的创新能力,并且自己要能找到解决问题的方案，形成一种独立的意识。我们还能从设计中检验我们所学的理论知识到底有多少，巩固我们已经学会的，不断学习我们所遗漏的新知识，把这门课学的扎实。当然在做课程设计的过程中总会出现各种问题，在这种情况下我们都会努力寻求最佳路径解决问题，无形间提高了我们的动手，动脑能力，并且同学之间还能相互探讨问题，研究解决方案，增进大家的团队意识。总的来说，这次创新课程设计让我们收获颇多，不仅让我们更深一步理解书本的知识，提高我们分析问题和解决问题的能力，而且让我们体会到团队的重要性。 参考文献【1】孙丽华著. 信息论与纠错编码M. 电子工业出版社，2005【2】潘新民著. 计算机通信技术M. 电子工业出版社，2003【3】张应中，张德明等编著. 数据通信工程. 人民邮电出版社，1996【4】杜煜，姚鸿等编. 计算机网络基础. 电子工业出版社，2002【5】王福昌，熊兆飞，黄本雄等编著. 通信原理. 清华大学出版社，2006【6】王兴亮著. 数字通信原理与技术（第二版）. 西安电子科技大学出版社，2000【7】 沈越泓，高媛媛，魏以民等编著.通信原理. 机械工业出版社，2004 【8】黎洪松，张卫刚等编著. 数字通信原理. 西安电子科技大学出版社，2005【9】Peter M.Grant.Digital Communications(Second Edition).China Machine Press【10】H.S.Black.Modulation Theory.1993,Chap.4附录clear;clc;close all;uncode_sequence=randint(1,12)sequence_length = length(uncode_sequence); % 得到原始信号长度crc_ccitt = 1 1 1 0 1; % 常用的CRC生成多项式add_bit = zeros(1,4); % 添加冗余比特位crc_coded_sequence = uncode_sequence zeros(1,4); % 初始化输出检错码序列uncode_sequence = uncode_sequence add_bit;remainder_bits = uncode_sequence; % 初始化余数数组for k = 1:sequence_length % 开始循环计算长除得到最终余数 add_zeros = zeros(1,sequence_length-k); % 加入冗余位参与模2运算 register_bits = crc_ccitt add_zeros; % 构造除数数组 if remainder_bits(1) = 0 % 被除数第一位为0则将除数所有位置0 register_bits = zeros(1,length(register_bits); endremainder_bits = bitxor(register_bits,remainder_bits); % 将除数与被除数进行异或操作register_bits = crc_ccitt; % 将寄存器恢复为除数数组remainder_bits(1) = ; % 去除模2后得到的被除数的第1位 endadd_len = length(crc_coded_sequence) - length(remainder_bits); % 生成余数序列的冗余位以叠加到编码序列remainder_bits = zeros(1,add_len),remainder_bits; % 余数序列添加冗余crc_coded_sequence = crc_coded_sequence + remainder_bits % 合成编码序列sequence_length = length(crc_coded_sequence); % 得到冗余编码的长度original_sequence = crc_coded_sequence; % 初始化输出序列 c