*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2014年秋季学期
《计算机通信》课程设计
题目：循环冗余校验码（CRC）的编译码仿真实现专业班级：通信工程（1）班
姓名：
学号：
指导教师：
成绩：
摘要
CRC即循环冗余校验码（Cyclic Redundancy Check）是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查（CRC）是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。
本次课程设计研究了纠错码及循环冗余校验码的原理，以及利用MATLAB对其进行了编码和译码仿真，实现了CRC循环冗余校验码的编码及校验，在接收端收到通过校验的码，从而确定传输过程是否出错，得到的结论和理论上是一致的。
关键词：循环冗余校验码；检错码；matlab软件
前言 (1)
第1章循环冗余校验码（CRC）的基本原理 (2)
1.1 循环冗余校验码的基本介绍 (2)
1.2 循环冗余校验码的几个基本概念 (2)
1.3 循环冗余校验码的基本原理 (3)
第2章 MATLAB软件基本介绍 (5)
2.1 MATLAB的介绍 (5)
2.2 MATLAB的组成部分 (5)
2.3 MATLAB的语言特点 (5)
2.4 MATLAB的优势 (6)
第3章循环冗余校验码（CRC）的详细设计 (7)
3.1 CRC循环冗余校验码的编码模块 (7)
3.2 CRC循环冗余校验码的译码模块 (7)
3.3 CRC循环冗余校验码的性能分析 (8)
3.4 CRC循环冗余校验码的生成器和校验器 (8)
3.5 CRC循环冗余校验码的程序流程图 (8)
3.6 运行结果及其分析 (10)
总结 (12)
参考文献 (13)
附录 (13)
致谢 (16)
数据通信中的编码可以分为两大类，分别是信源编码和信道编码。在实际应用中，为了提高数据通信的可靠性而采取的编码称为信道编码，也称做抗干扰编码。一般来讲，数据通信要求传输过程中的误码率应该足够低，这样才能真正符合实际应用的具体要求，为了降低数据通信线路传输的误码率，通常有改善数据通信线路传输质量和差错检测控制两种方法。
实现差错检测控制的方法很多，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)。如生成多项式为1)(34+++=x x x x G ，可转换为二进制数码11011。而发送信息位 1111，可转换为数据多项式为1)(23+++=x x x x f 。
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)(23689+++++=x x x x x x f ，生成码：1 1 0 0 1 0生成多项式：1)(45+++=x x x x G 。
解： 1）)1(23689+++++x x x x x *3x 的积是369182427x x x x x x +++++对应的码字是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 0
2) 积／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多项式：1)(46+++=x x x x T 生成码：1011 生成多项式：1)(3++=x x x G (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的突发错以及99．997%的突发长度为17的突发错和99．998%的突发长度大于17的突发错。所以CRC 码的检错能力还是很强的。这里，突发错误是指几乎是连续发生的一串错，突发长度就是指从出错的第一位到出错的最后一位的长度(但是，中间并不一定每一位都错)。
3.4 CRC 循环冗余校验码的生成器和校验器
CRC 循环冗余校验码的生成器和校验器如图1所示：
图1 CRC 循环冗余校验码的生成器和校验器 3.5 CRC 循环冗余校验码的程序流程图
r bit r+1 bit 余数 r bit
CRC 校验码
数据 00...0 G(X) 数据 数据 0接收，非0拒绝 数据 余数 G(X) 发送方
接收方
CRC 循环冗余校验码的程序流程图如图2所示：
N
Y
N
Y N
Y
图2 CRC 循环冗余校验码的程序流程图 余数是否为零 输出接收端的码 结束
输出erro=1
开始 初始化，随机产生信息码并输出 添加冗余比特位 循环计算长除 是否除完 合成编码序列输出 用合成码长除生成多项式
是否除完
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));
end
remainder_bits = bitxor(register_bits,remainder_bits);
% 将除数与被除数进行异或操作
register_bits = crc_ccitt; % 将寄存器恢复为除数数组remainder_bits(1) = []; % 去除模2后得到的被除数的第1位end
add_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; % 初始化输出序列crc_ccitt = [1 1 1 0 1]; % 常用的CRC生成多项式
remainder_bits = crc_coded_sequence; % 初始化余数数组
cycle_length = sequence_length-length(crc_ccitt)+1;
% 计算长除法的循环周期
for k = 1:cycle_length % 开始循环计算长除得到最终余数add_zeros = zeros(1,cycle_length-k);
% 加入冗余位参与模2运算
register_bits = [crc_ccitt add_zeros]; % 构造除数数组
if remainder_bits(1) == 0
% 被除数第一位为0则将除数所有位置0 register_bits = zeros(1,length(register_bits));
end
remainder_bits = bitxor(register_bits,remainder_bits);
% 将除数与被除数进行异或操作
register_bits = crc_ccitt; % 将寄存器恢复为除数数组
remainder_bits(1) = []; % 去除模2后得到的被除数的第1位end
if sum(remainder_bits) == 0 % 传输码元中没有发生奇数个错误original_sequence = crc_coded_sequence(1:cycle_length)
else
err = 1 % 码元传输发生错误end
致谢
我们通信工程专业是个实践性很强的专业，而我们在校大部分的学习时间都是花在理论学习上面，实践的机会很少。因而我对很多所学的理论知识如何跟实践联系的概念很模糊，这次的课程设计给了我这个机会，加深了我对理论联系实际的理解，增强了自己独立分析问题和解决问题的能力，开阔了自己的思维。
还有让我看到了自己的不足，自己对本专业的相关知识掌握的还很少，还有很多知识都没掌握，还让我认识到解决问题的方法、途径很多，做事要开阔自己的思维，看待问题要从多个角度看。通过本次信号处理课程设计，我了解到了做任何事都要有耐心、更要细心做事。这次的课程设计让我也意识到自己的理论知识还是不够好，在今后的学习中我们需要更努力的学习课本的专业知识。课程设计不仅是对前面所学知识的一种检验，而且也是对自己能力的一种提高。我学到了许多东西，体会到了从书本学习与实际应用中的不同，这种感同身受必将对我们今后的学习与生活带来很大的帮助。
在此我要感谢学校为我们提供这次课程设计的机会，感谢老师对我的悉心指导，也感谢同学对我的帮助。这次的课程设计让我理论联系实际，不仅巩固了我们的理论知识，还提高了我的动手能力，在这次课程设计中我所学到的知识是我的财富，让我终身受益。
在远距离数据通信中，为确保高效而无差错地传送数据，必须对数据进行校验即差错控制。循环冗余校验CRC(Cyclic Redundancy Check)是对一个传送数据块进行校验，是一种高效的差错控制方法。 1、循环冗余校验码原理 CRC 校验采用多项式编码方法，如一个8 位二进制数(B7B6B5B4B3B2B1B0)可以用7 阶二进制码多项式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。 例如11000001 可表示为 1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0 一般说，n 位二进制数可用(n-1)阶多项式表示。它把要发送的数据位串看成是系数只能为“1”或“0”的多项式。一个n 位的数据块可以看成是从Xn-1到X0的n 项多项式的系数 序列，位于数据块左边的最高位是X n-1项的系数，次高位是X n-2项的系数，依此类推，位 于数据块右边的最低位是X0项的系数，这个多项式的阶数为n-1。 多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2 为模，加减时不进、错位，如同逻辑异或运算。 采用CRC 校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。设m 位数据块的多项式为M(X)，生成多项式G(X)的阶数必需 比M(X)的阶数低。CRC 校验码的检错原理是：发送方先为数据块生成CRC 校验码，使这 个CRC 校验码的多项式能被G(X)除尽，实际发送此CRC 校验码；接收方用收到的CRC 校 验码除以G(X)，如果能除尽，表明传输正确，否则，表示有传输错误，请求重发。 生成数据块的CRC 校验码的方法是： (1) 设G(X)为r 阶，在数据块末尾添加r 个0，使数据块为m+r 位，则相应的多项式 为XrM(X)； (2) 以2 为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串； (3) 以2 为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC 校验码位串。 例如，设要发送的数据为1101011011，G(X)=X4+X+1，则首先在发送数据块的末尾加4 个0，得到11010110110000，然后用G(X)的位串10011 去除，再用11010110110000 减去余 数位串1110，得到的即为CRC 位串11010110111110，将对应多项式称为T(X)，显然，T(X) 能被G(X)除尽。这样，一旦接收到的CRC 位串不能被同样的G(X)的位串除尽，那么一定 有传输错误。 当使用CRC校验码进行差错控制时，除了为G(X)的整数倍的差错多项式不能被检测外，其它差错均能被查出。CRC 校验码的差错控制效果取决于G(X)的阶数，阶数越高，效果
拷贝数据时出现“数据错误循环冗余检查”的解决方法 问题描述：将硬盘中的文件数据复制到可移动磁盘，如U盘等设备中时，系统提示“无法复制：数据错误循环冗余检查”，导致无法复制文件，如下图所示； 数据错误循环冗余检查的解决办法： 第一步：如果是从硬盘的某一个盘符复制到另一个盘符时出错；打开“我的电脑”——>在复制文件出错的盘符上(如C盘)点击鼠标右键——>选择“属性”——>弹出“本地磁盘(X:)属性”窗口，切换到“工具”选项卡中——>点击第一个项目中的“开始检查(C)”——>弹出窗口中，勾选中“自动修复文件系统错误(A)”——>点击“开始”——>此时如果系统提示“磁盘检查不能执行，因为磁盘检查实用程序需要独占访问磁盘上的一些Windows文件...”，直接点击“是”——>然后重新启动计算机后，将自动进行磁盘错误检查并且修复出错的文件；
第二步：对出错的磁盘盘符进行“磁盘碎片整理”；点击“开始”菜单——>选择“所有程序”——>鼠标指向“附件”——>再指向“系统工具”——>单击“磁盘碎片整理程序”——>在“卷”下方选中出错的盘符，点击“碎片整理”——>耐心等待磁盘碎片整理结束，重新启动计算机即可； 第三步：检查磁盘格式是否不统一，如源文件所在盘符为NTFS，但需要保存复制的磁盘格式为FAT32，这种情况下也可能导致“数据错误循环冗余检查”无法复制的情况；打开“我的电脑”——>鼠标右键点击磁盘——>选择“属性”——>在“属性”窗口中部就能查看到该磁盘是哪种格式的——>如果两个磁盘不统一，将FAT32格式的磁盘格式转换为NTFS即可；
第四步：如果是复制文件到U盘或其他可移动磁盘时出错，采用上述步骤无效时，建议优先使用杀毒软件对U盘进行杀毒，如果杀毒也无法解决“数据错误循环冗余检查”的问题，就需要对U盘等可移动磁盘进行格式化了；先将U盘中的所有数据备份出来，然后鼠标右键点击U盘的盘符，选择“格式化”——>勾选中“快速格式化”——>点击“开始”——>直至格式化完毕后，在进行复制操作； 总结：U盘等可移动磁盘导致“数据错误循环冗余检查”的错误提示时，优先使用杀毒软件进行杀毒，很有可能是病毒木马感染导致的。
1、循环冗余校验码原理 CRC 校验采用多项式编码方法，如一个8 位二进制数(B7B6B5B4B3B2B1B0)可以用7 阶二进制码多项式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。 例如11000001 可表示为 1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0 一般说，n 位二进制数可用(n-1)阶多项式表示。它把要发送的数据位串看成是系数只能为“1”或“0”的多项式。一个n 位的数据块可以看成是从Xn-1到X0的n 项多项式的系数 序列，位于数据块左边的最高位是X n-1项的系数，次高位是X n-2项的系数，依此类推，位 于数据块右边的最低位是X0项的系数，这个多项式的阶数为n-1。 多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2 为模，加减时不进、错位，如同逻辑异或运算。 采用CRC 校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。设m 位数据块的多项式为M(X)，生成多项式G(X)的阶数必需 比M(X)的阶数低。CRC 校验码的检错原理是：发送方先为数据块生成CRC 校验码，使这 个CRC 校验码的多项式能被G(X)除尽，实际发送此CRC 校验码；接收方用收到的CRC 校 验码除以G(X)，如果能除尽，表明传输正确，否则，表示有传输错误，请求重发。 生成数据块的CRC 校验码的方法是： (1) 设G(X)为r 阶，在数据块末尾添加r 个0，使数据块为m+r 位，则相应的多项式 为XrM(X)； (2) 以2 为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串； (3) 以2 为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC 校验码位串。 例如，设要发送的数据为1101011011，G(X)=X4+X+1，则首先在发送数据块的末尾加4 个0，得到11010110110000，然后用G(X)的位串10011 去除，再用11010110110000 减去余 数位串1110，得到的即为CRC 位串11010110111110，将对应多项式称为T(X)，显然，T(X) 能被G(X)除尽。这样，一旦接收到的CRC 位串不能被同样的G(X)的位串除尽，那么一定 有传输错误。 当使用CRC校验码进行差错控制时，除了为G(X)的整数倍的差错多项式不能被检测外，其它差错均能被查出。CRC 校验码的差错控制效果取决于G(X)的阶数，阶数越高，效果越 好。目前，常用的有两种生成多项式G(X)的方法，分别是： CRC-16 X16+X15+X2+1 CCITT X16+X12+X5+1
摘要：在can网络中传输摄文时，噪声干扰或传输中断等因素往往使接收端收到的报文出现错码。为了及时可靠地把报文传输给对方并有效地检测错误，需要采用差错控制。详细介绍了can总线中循环冗余校验码的差错控制原理及其实现方法。关键词：循环冗余校验差错控制报文在can系统中为保证报文传输的正确性，需要对通信过程进行差错控制。目前常用的方法是反馈重发，即一旦收到接收端发出的出错信息，发送端便自动重发，此时的差错控制只需要检错功能。常用的检错码两类：奇偶校验码和循环冗余校验码。奇偶校验码是一种最常见的检错码，其实现方法简单，但检错能力较差；循环冗余校验码的编码也很简单且误判率低，所以在通信系统中获得了广泛的应用。下面介绍can网络中循环冗余校验码（即crc码）的原理和实现方法。 1 crc码检错的工作原理crc码检错是将被处理报文的比特序列当作一个二进制多项式a（x）的系数，该系数除以发送方和接收方预先约定好的生成多项式g(x)后，将求得的余数p(x)作为crc校验码附加到原始的报文上，并一起发给接收方。接收方用同样的g(x)去除收到的报文b(x)，如果余数等于p(x)，则传输无误（此时a（x）和b(x)相同）；否则传输过程中出错，由发送端重发，重新开始crc校验，直到无误为止。上述校验过程中有几点需注意：①在进行crc计算时，采用二进制（模2）运算法，即加法不进位，减法不借位，其本质就是两个操作数进行逻辑异或运算；②在进行crc计算前先将发送报文所表示的多项式a(x)乘以xn，其中n为生成多项式g(x)的最高幂值。对二进制乘法来讲，a(x)·xn就是将a(x)左移n 位，用来存放余数p（x），所以实际发送的报文就变为a（x）·xn+p(x)；③生成多项式g(x)的首位和最后一位的系数必须为1。图1为crc校验的工作过程。目前已经有多种生成多项式被列入国际标准中，如：crc-4、crc-12、crc-16、ccitt-16、crc-32等。can总线中采用的生成多项式为g(x)=x15+x14+x10+x8+x7+x4+x3+1。可以看出，canu叫线中的crc校验采用的多项式能够校验七级，比一般crc校验（crc-4、crc-12、crc-16等）的级数（二～五级）要高许多，因而它的检错能力很强，误判率极低，成为提高数据传输质量的有效检错手段。图 2 产生crc校验码的硬件电路 2 crc码的电路实现2.1 硬件电路的特点在can总线中为了产生crc码，硬件电路除了具有复位和时钟信号以外，还需要以下两个控制信号的参与：①填充位解除信号destuff，它的有效逻辑值是1；②crc检验的使能信号enable，有效逻辑也为1。该硬件电路的特点是采用选择器和反相器代替传统设计中用的异或门，既实现了比较功能，又降低了生产成本，同时也为工程师们提供了一种新的设计思路。2.2 硬件电路图图2即为实现crc码的硬件电路图。图中需要说明的几点如下：①使能信号和填充位解除信号省略；②crcnxt代表的逻辑值为输入报文序列和crc寄存器的最高位异或的结果；③标号0～14所指示的为15位crc寄存器，上升沿触发；④标号1～6所指示的为选择器和反相器的组合逻辑，实现异或功能，该选择器的逻辑功能为y=ab+ac，具体结构如图3所示。2. 3 电路工作过程从以上分析可知：①当enable=0时，crc清0；②当enable=1、destuff=1时，进行正常crc计算；③当enable=1而destuff=0时，正在解除填充时，数据暂停传送。在各个控制信号均有效时，输入报文的每一位都是和crc寄存器的最高位相异和后移入最低位，同时寄存器的第13、9、7、6、3、2位均和其最高位异或，结果分别左移一位；其它未进行异或操作的寄存器位值也分别左移一位，直到报文的每一位都移入crc寄存器为止，此时寄存器中的值取为计算得到的crc码。如果报文的比特序列长度为16，则需要左移16次才能对报文的每一位均进行处理。如果以ck表示crc寄存器的第k位位值、ck'表示移位后的第k位位值（k=0,1,2,3……15），则移位规律见表1。 表 1 移位规律表c14'=c13^crcnxtc13'=12c12'=c11c11'=c10c10'=c9^crcnxtc9'=c8c8'=c7^crcnxtc7'=c6^cr cnxtc6'=c5c5'=c4c4'=c3^crcnxtc3'=c2^crcnxtc2'=c1c1'=c0c0'=crcnxt^datain 3 crc校
循环冗余校验码（CRC）的基本原理 模2除（按位除） 模2除做法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位。所以实际上就是异或。然后再移位移位做下一位的模2减。步骤如下： a、用除数对被除数最高几位做模2减，没有借位。 b、除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位。 c、一直做到余数的位数小于除数时，该余数就是最终余数。 循环冗余校验码（CRC）的基本原理是：在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)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。 CRC码的生成步骤 4、得到011-------余数（校验位）
5、编码后的报文（CRC码）1010011 1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。 2、将信息码左移R位，相当与对应的信息多项式C(x)*2R 3、用生成多项式（二进制数）对信息码做模2除，得到R位的余数。 4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。 【例】假设使用的生成多项式是G(x)=x3+x+1。4位的原始报文为1010，求编码后的报文。解： 1、将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。 2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000 3、用生成多项式对应的二进制数对左移4位后的原始报文进行模2除
“数据错误，循环冗余检查”解决方法 从光盘、硬盘或其他介质复制文件时有时会出现“无法复制：数据错误（循环冗余检查）”的错误，导致某些文件不能复制。这时因为： 循环冗余检查（CRC）是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。若CRC校验不通过，系统重复向硬盘复制数据，陷入死循环，导致复制过程无法完成。 注意到在上述过程中实际已有一部分数据复制到硬盘，只是碰到某些数据CRC校验不通过时，Windows的复制命令无法跳过这些数据继续执行。而当操作无法完成后，系统会把已经复制到硬盘上的数据删除，这样导致复制完全失败。如果在复制时能跳过错误数据，这个问题就能得到解决。 解决方案一：重启电脑，不要运行任何软件，重试复制1-3次，若无法解决请看方案二。 解决方案二：尝试使用复制工具，例如FastCopy等。若问题依旧，请看第三条。解决方案三：（95%解决问题！） 思路：利用下载工具（迅雷，FlashGet等）的“断点续传”和“多进程多文件下载”特性。 操作步骤：假设无法复制的文件位于X:\光盘\123.RM ,需要复制到D:\资料 1.用操作系统安装光盘或通过网络下载安装IIS（Internet信息服务）,版本随意，XP下光盘安装为IIS5.1. 2.建立自己的站点，虚拟目录名称假设为"my" ,路径设置为X:\光盘\ 3.将“http://localhost/my/123.rm” 作为URL复制进迅雷（FlashGet）的“新建”下载任务的URL文本框。 选择要下载到的目录，这里假设为D:\资料，点击“确定”开始下载。 这样除了错误数据，其余均被下载到硬盘。影音文件可以正常使用。
循环冗余校验 CRC 的算法分析和程序实现 西南交通大学计算机与通信工程学院 刘东 摘要 通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC （Cyclic Redundancy Check ）的差错控制原理及其算法实现。 关键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4 概述 在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ ）、向前纠错方式（FEC ）和混合纠错（HEC ）。在传输过程误码率比较低时，用FEC 方式比较理想。在传输过程误码率较高时，采用FEC 容易出现“乱纠”现象。HEC 方式则式ARQ 和FEC 的结合。在许多数字通信中，广泛采用ARQ 方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。 循环冗余校验CRC （Cyclic Redundancy Check ）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC 校验的原理及其 算法实现。 一、循环冗余校验码（CRC ） CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个n 阶的二进制多项式，由012211a x a x a x a x n n n ++???++----。如一个8位二进制数10110101可以表示为：10101101234567+++++++x x x x x x x 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。 采用CRC 校验时，发送方和接收方用同一个生成多项式g （x ）,并且g （x ）的首位和最后一位的系数必须为1。CRC 的处理方法是：发送方以g （x ）去除t （x ），得到余数作为CRC 校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。 CRC 校验可以100％地检测出所有奇数个随机错误和长度小于等于k （k 为g （x ）的阶数）的突发错误。所以CRC 的生成多项式的阶数越高，那么误判的概率就越小。CCITT 建议：2048 kbit/s 的PCM 基群设备采用CRC-4方案，使用的CRC 校验码生成多项式g （x ）=14++x x 。采用16位CRC 校验，可以保证在1410 bit 码元中只含有一位未被检测出的错误]2[。在IBM 的同步数据链 路控制规程SDLC 的帧校验序列FCS 中，使用CRC-16，其生成多项式g （x ）=1 21516+++x x x ； 而在CCITT 推荐的高级数据链路控制规程HDLC 的帧校验序列FCS 中，使用CCITT-16，其生成多项式g （x ）=1 51516+++x x x 。CRC-32的生成多项式g （x ）
循环冗余校验检错方案 《深入理解计算机网络》第5章数据链路层，本章主要针对广域网中的数据链路层和局域网体系结构中的逻辑链路控制（LLC）子层的功能及相关技术进行全面、深入的介绍。本节为大家介绍循环冗余校验检错方案。 5.3.2 循环冗余校验检错方案 上节介绍的奇偶校验码（PCC）只能校验一位错误，本节要介绍的循环冗余校验码（CRC）的检错能力更强，可以检出多位错误。 1. CRC 校验原理 CRC 校验原理看起来比较复杂、难懂，因为大多数书上基本上都是以二进制的多项式形式来说明的。其实其原理很简单，根本思想就是先在要发送的帧后面附加一个数（这个数就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称为模2 除法的方法）。到达接收端后，再把接收到的新帧除以（同样采用模2 除法）这个选定的除数。因为在发送端发送数据帧之前就已附加了一个数，做了去余处理（也就已经能整除了），所以结果应该没有余数。如果有余数，则表明该帧在传输过程中出现了差错。 说明模2 除法与算术除法类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只以相同位数进行相除。模2 加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位。模2 减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位，相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101 除以1110，结果得到商为11，余数为1，如图5-9a 图所示。再如11×11=101，如图5-9b 图所示。
循环冗余校验码（CRC）的基本原理 循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R 的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设发送信息用信息多项式f(X)表示，将f(x)左移R位（则可表示成f(x)*X R），这样f(x)的右边就会空出R位，这就是校验码的位置。通过f(x)* X R除以生成多项式G(x)得到的余数就是校验码。 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式f(x)。 如生成多项式为G(x)=X4+X3+X+1，可转换为二进制数码11011。 而发送信息位1111，可转换为数据多项式为f(x)=X3+X2+X+1。
2、生成多项式 是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图9所示： N K 码距d G(x)多项式G(x) 7 4 3 x3+x+1 1011 7 4 3 x3+x2+1 1101 7 3 4 x4+x3+x2+1 11101 7 3 4 x4+x2+x+1 10111
一、奇偶校验码 奇偶校验可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。因此，若有一个码元是错的，就可以分辨得出，因为奇偶校验将成为奇性。奇偶校验编码通过增加一位校验位来使编码中1的个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2。因为其利用的是编码中1的个数的奇偶性作为依据，所以不能发现偶数位错误。 一个二进制码字，如果它的码元有奇数个1，就称为具有奇性。例如，码字“”有五个1，因此，这个码字具有奇性。同样，偶性码字具有偶数个1。 再以数字0的七位ASCII码（0110000）为例，如果传送后右边第一位出错，0变成1。接收端还认为是一个合法的代码0110001（数字1的ASCII码）。若在最左边加一位奇校验位，编码变为，如果传送后右边第一位出错，则变成，1的个数变成偶数，就不是合法的奇校验码了。但若有两位（假设是第1、2位）出错就变成，1的个数为5，还是奇数。接收端还认为是一个合法的代码（数字3的ASCII码）。所以奇偶校验不能发现。 奇偶校验位可由硬件电路（异或门）或软件产生： 偶校验位 a n=a0⊕a1⊕a2⊕…⊕a n-1，奇校验位 a n=NOT（a0⊕a1⊕a2⊕…⊕a n-1）。 在一个典型系统里，在传输以前，由奇偶发生器把奇偶校验位加到每个字中。原有信息中的数字在接收机中被检测，如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发。 在实际工作中还经常采用纵横都加校验奇偶校验位的编码系统--分组奇偶校验码。 现在考虑一个系统，它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组，则在这些不同的信息间，也如对单个信息一样，能够作奇偶校验。图4中n个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵向奇偶（VP）的形式编出奇偶校验位。 m位数字横向奇偶位 n 个 码 字 纵向奇偶 位
CRC 校验 循环冗余校验CRC 的算法分析和程序实现 摘要通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠 与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错 控制。本文详细介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其算法实 现。 关键字通信循环冗余校验CRC-32 CRC-16 CRC-4 概述 在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地 时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下 降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾， 是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控 制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC 方式比较理想。在传输过程误码率较高时，采用FEC 容易出 现“乱纠”现象。HEC 方式则式ARQ 和FEC 的结合。在许多数字通信中，广泛采用ARQ 方式， 此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验 和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验 码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的 校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。 循环冗余校验CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二 元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC 校验 的原理及其算法实现。 一、循环冗余校验码（CRC） CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个n 阶的二进制多项式，由 1 0 2 2 1 1 a x a x x a x a n n n + ? + ??? + + ? ? ?。如一个8 位二进制数10110101 可以表示为： 1x7 + 0x6 +1x5 +1x4 + 0x3 +1x2 + 0x +1。多项式乘除法运算过程与普通代数多项式的乘除法相 同。多项式的加减法运算以2 为模，加减时不进，错位，和逻辑异或运算一致。 采用CRC 校验时，发送方和接收方用同一个生成多项式g（x）_______,并且g（x）的首位和最后一 位的系数必须为1。CRC 的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC 校验码。 校验时，以计算的校正结果是否为0 为据，判断数据帧是否出错。 CRC 校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k 为g（x）的阶数）的 突发错误。所以CRC 的生成多项式的阶数越高，那么误判的概率就越小。CCITT 建议：2048 kbit/s 的PCM 基群设备采用CRC-4 方案，使用的CRC 校验码生成多项式g（x）= x4 + x +1。采用16 位CRC 校验，可以保证在1014 bit 码元中只含有一位未被检测出的错误[2]。在IBM 的同步数据链
实验十三循环冗余校验（CRC）模块设计 一、实验目的 1、学习使用FPGA器件完成数据传输中的差错控制； 2、了解循环冗余校验CRC模块的工作原理 3、应用VHDL语言设计循环冗余校验CRC模块，实现在数字传输中的校验和纠错功能。 3、学习实验环节的设计与实现。 二、实验仪器 计算机、Max+plusII或QuartusII软件、EDA试验箱、示波器。 三、实验内容 原理：CRC即Cyclic Redundancy Check 循环冗余校验，是一种数字通信中的信道编码技术。经过CRC方式编码的串行发送序列码，可称为CRC码，共由两部分构成：k位有效信息数据和r位CRC校验码。其中r位CRC校验码是通过k 位有效信息序列被一个事先选择的r+1位“生成多项式”相“除”后得到的(r位余数即是CRC校验码)，这里的除法是“模2运算”。CRC校验码一般在有效信息发送时产生，拼接在有效信息后被发送；在接收端，CRC码用同样的生成多项式相除，除尽表示无误，弃掉r位CRC校验码，接收有效信息；反之，则表示传输出错，纠错或请求重发。本设计完成12位信息加5位CRC校验码发送、接收，由两个模块构成，CRC校验生成模块(发送)和CRC校验检错模块(接收)，采用输入、输出都为并行的CRC校验生成方式。图12.1的CRC模块端口数据说明如下： sdata：12位的待发送信息；datald：sdata的装载信号； error：误码警告信号；datafini：数据接收校验完成； rdata：接收模块(检错模块)接收的12位有效信息数据；clk：时钟信号；datacrc：附加上5位CRC校验码的17位CRC码，在生成模块被发送，在接收模块被接收； hsend、hrecv：生成、检错模块的握手信号，协调相互之间关系； 实验要求： 1、设计CRC校验生成模块，采用的CRC生成多项式为X5+X4+X2+1，校验码为5位，有效信息数据为12位。 2、设计CRC校验查错模块，并将CRC校验生成模块和CRC校验查错模块连接在一起，协调工作。 3、估计实验使用的硬件资源，自行设定测试方法和测试内容。 4、自行设定测试方案和测试步骤。 5、自行设定实验步骤和设计纪录方式，完成实验报告。
循环冗余校验码 在串行传送（磁盘、通讯）中，广泛采用循环冗余校验码（CRC）。CRC也是给信息码加上几位校验码，以增加整个编码系统的码距和查错纠错能力。 CRC的理论很复杂，一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关，只能根据书上的结论死记。 循环冗余校验码（CRC）的基本原理是：在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)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x)。 如生成多项式为G(x)=x4+x3+x+1，可转换为二进制数码11011。 而发送信息位1111，可转换为数据多项式为C(x)=x3+x2+x+1。 2、生成多项式 是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。
武汉理工大学 计算机网络课程论文 题目循环冗余校验（CRC）算法的实现作者 学院信息工程学院 专业电子信息工程 学号 指导 教师 二〇一六年四月十四日
武汉理工大学信息工程学院课程论文诚信声明 本人声明：所呈交的课程论文，是本人在指导老师的指导下，独立开展工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本课程论文不含任何其他个人或集体已经发表或创作过的作品成果。对本文工作做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本科课程论文作者签名： 二○一六年四月十四日
课程论文成绩评定表 质量评价指标（在相应栏目打√） 论文与设计评价质量评价项目 按对应项目打分 工作量和态度（10分） 分析问题能力（10分） 解决问题能力（10分） 内容完整层次分明（10分） 设计、实验正确性（10分） 书写规范（10分） 流程图或拓扑图（10分） 论证充分（10分） 测试结果情况（10分） 总体评价（10分） 评定成绩（100分制） 指导教师签名 年月日
目录 一、选题背景 (1) 1.设计要求 (1) 2.循环冗余CRC简介 (1) 3.应解决的主要问题 (2) 二、方案论证 (2) 1.循环冗余检验的原理 (2) 2.方案的选择及特点 (4) 三、过程论述 (8) 1.第一部分 (8) 2.第二部分 (9) 3.第三部分 (11) 4.第四部分 (11) 四、结果分析 (12) 1.CRC算法的实现 (12) 2.突变的产生和校验结果 (13) 3.无法检错的实例 (14) 五、总结 (15) 心得体会 (17) 参考文献 (17) 附件一：程序源代码 (18) 一、