计算机通信中循环冗余校验码的设计设计大学论文.docx
《计算机通信中循环冗余校验码的设计设计大学论文.docx》由会员分享，可在线阅读，更多相关《计算机通信中循环冗余校验码的设计设计大学论文.docx（18页珍藏版）》请在冰点文库上搜索。
计算机通信中循环冗余校验码的设计设计大学论文
中文摘要
通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数据通信系统中可靠与快速往往是一对矛盾。
为了解决可靠性，通信系统都采用了差错控制。
CRC（CyclicalRedundancyChecking）循环冗余校验码是一种重要的线性分组码，通过多项式除法检测错误，是在数据通信和数据检测中广泛应用的检错校验的循环码。
关键词：
循环冗余校验；crc；检错；纠错；matlab软件
前言
随着科学技术的进步,人们对信息传递的要求逐渐提高。
但在通信系统中,可靠性与有效性是对矛盾,要求有效性提高,必然使每个码元所占的时间缩短,从而受干扰和产生错误的可能性增大,可靠性降低了;要提高信息的可靠性,又使信息速率变慢有效性降低。
因此,合理的解决有效性与可靠性这对矛盾,是正确设计一个通信系统的关键问题之一,为保证传输过程的可靠性,就需要对通信过程进行差错控制。
循环冗余校验码CRC（cyclicredundancycheck）是一种高效率且可靠的方法,由线性分组码分支而来的,是一种通过多项式除法检测错误的很不寻常而又巧妙的方法,一方面它有很强的检测能力,二是它的编码器电路及错误检测器电路都很容易实现,它的优点使它在通信系统中得到了广泛的应用。
现代社会发展要求通信系统功能越来越强，可靠性越来越高，构成也越来越复杂；这就要借助于功能强大的计算机辅助分析设计技术和工具才能实现。
现代计算机科学技术快速发展，已经研发出了新一代的可视化的仿真软件。
这些功能强大的仿真软件，使得通信系统仿真的设计和分析过程变得相对直观和便捷，由此也使得通信系统仿真技术得到了更快的发展。
本文使用的是功能强大的MATLAB语言软件。
MATLAB是一种科学计算软件，主要适用于矩阵运算及控制和信息处理领域的分析设计。
它使用方便，输入简捷，运算高效，内容丰富，并且很容易由用户自行扩展，因此，当前已成为教学和科研中最常用而必不可少的工具。
第一章计算机通信与纠错码
1.1计算机通信技术的历史和发展
1.1.1通信的概念
通信就是克服距离上的障碍，从一地向另一地传递和交换消息。
消息是信息源所产生的，是信息的物理表现，例如，语音、文字、数据、图形和图像等都是消息（Message）。
消息由模拟消息（如语音、图像等）以及数字消息（如数据、文字等）之分。
所有消息必须在转换成电信号（通常简称为信号）后才能在通信系统中传输。
所以，信号（Signal）是传输消息的手段，信号是消息的物资载体。
相应的信号可以分为模拟信号和数字信号，模拟信号的自变量可以是连续的或离散的，但幅度是连续的，如电话机、电视摄像机输出的信号就是模拟信号。
数字信号的自变量可以是连续的或离散的，但幅度是离散的，如计算机等各种数字终端设备输出的信号就是数字信号。
通信的目的是传递消息，但对受信者有用的是消息中包含的有效内容，即信息（Information）。
消息是具体的、表面的，而信息是抽象的、本质的，且消息中包含的信息的多少可以用信息量来度量。
通信技术，特别是数字通信技术近年来发展非常迅速，它的应用越来越广泛。
数字通信系统较模拟通信系统而言，具有抗干扰能力强、便于加密、易于实现集成化、便于与计算机连接等优点。
因而，数字通信更能适应对通信技术的高要求。
1.1.2通信的发展史简介
远古时代，远距离的传递消息是以书信的形式来完成的，这种通信方式明显具有传递时间长的缺点。
为了在尽量短的时间内传递尽量多的消息，人们不断
广域式是指在一个广泛的地域范围内所建立的计算机通信。
通信范围可以超越城市和国家，以至于全球。
广域计算机通信覆盖地区的直径一般在数十公里到数干公里乃至上万公里。
在通常情况下，计算机通信都是由多台计算机通过通信线路连接成计算机通信地尝试所能找到的各种最新技术手段。
1837年发明的莫尔斯电磁式电报标志着电通信的开始。
之后，利用电进行通信的研究取得了长足的进步。
1866年利用海底电缆实现了跨大西洋的越洋电报通信。
1876年贝耳发明了电话，利用电信号实现了语音信号的有线传递，使信息的传递变得既迅速又准确，这标志着模拟通信的开始，由于它比电报更便于交流使用，所以直到20世纪前半叶这种采用模拟技术的电话通信技术比电报得到了更为迅速和广泛的发展。
1937年瑞威斯发明的脉冲编码调制标志数字通信的开始。
20世纪60年代以后集成电路、电子计算机的出现，使得数字通信迅速发展。
在70年代末在全球发展起来的模拟移动电话在90年代中期被数字移动电话所代替，现有的模拟电视也正在被数字电视所代替。
数字通信的高速率和大容量等各方面的优越性也使人们看到了它的发展前途。
1.1.3计算机通信介绍
计算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。
它是现代计算机技术与通信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。
计算机通信按照传输连接方式的不同，可分为直接式和间接式两种。
直接式是指将两部计算机直接相联进行通信，可以是点对点，也可以是多点通播。
间接式是指通信双方必须通过交换网络进行传输。
按照通信覆盖地域的广度，计算机通信通常分为局域式、城域式和广域式三类。
局域式是指在一局部的地域范围内（例如一个机关、学校、军营等）建立计算机通信。
局域计算机通信覆盖地区的直径在数公里以内。
城域式是指在一个城市范围内所建立的计算机通信。
城域计算机通信覆盖地区的直径在十公里到数十公里。
网进行的，这样可共享网络资源，充分发挥计算机系统的效能。
1.2纠错码
纠错码（errorcorrectingcode），在传输过程中发生错误后能在收端自行发现或纠正的码。
仅用来发现错误的码一般常称为检错码。
为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。
关系的建立称为编码。
码字到达收端后，可以根据编码规则是否满足以判定有无错误。
当不能满足时，按一定规则确定错误所在位置并予以纠正。
纠错并恢复原码字的过程称为译码。
检错码与其他手段结合使用，可以纠错。
纠错编码又称信道编码，它与信源编码是信息传输的两个方面。
它们之间存在对偶的关系。
应用信道译码直接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。
为了使一种码具有检错或纠错能力，必须对原码字增加多余的码元，以扩大码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一个码字。
准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个码字的码元间有一定的关系。
关系的建立称为编码。
码字到达收端后，用编码时所用的规则去检验。
如果没有错误，则原规则一定满足，否则就不满足。
由此可以根据编码规则是否满足以判定有无错误。
当不能满足时，在可纠能力之内按一定的规则确定错误所在的位置，并予以纠正。
纠错并恢复原码字的过程称为译码；码元间的关系为线性时，称为线性码；否则称为非线性码。
检错码与其他手段结合使用，可以纠错。
检错反馈重发系统（ARQ系统）就是一例。
在构造纠错码时，将输入信息分成k位一组以进行编码。
若编出的校验位仅与本组的信息位有关，则称这样的码为分组码。
若不仅与本组的k个信息位有关，而且与前若干组的信息位有关，则称为格码。
这种码之所以称为格码，是因为用图形分析时它象篱笆或格架。
线性格码在运算时为卷积运算，所以叫卷积码。
1.3纠错原理
纠错码能够检错或纠错，主要是靠码字之间有较大的差别。
这可用码字之间的汉明距离d（x，y）来衡量。
它的定义为码字x与y之间的对应位取不同值的码元个数。
一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。
一种码要能发现e个错误,它的最小距离d应不小于e+1。
若要能纠正t个错误，则d应不小于2t+1。
一个码字中非零码元的个数，称为此码字的汉明重量。
一种码中非零码字的重量的最小值，称为该码的最小重量。
对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。
在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。
当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定；而多项式完全可由它的根规定。
这样,就容易对码进行构造和分析。
这是BCH码等循环码构造的出发点。
一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。
若一种码的码长为n，码字数为M,或信息位为h,以及最小距离为d，则可把此码记作【n,M,d】码。
若此码为线性码，常简记作（n，k）或（n,k,d）码。
人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。
R越大,则每个码元所携带的信息量越大，编码效率越高。
纠错码实现中最复杂的部分是译码。
它是纠错码能否应用的关键。
根据式
（1）,采用的码长n越大,则误码率越小。
但n越大，编译码设备也越复杂,且延迟也越大。
人们希望找到的译码方法是:
误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长n基本无关。
可惜，已经找到的码能满足这样要求的很少。
不过由于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。
因此，纠错码的应用越来越广泛。
纠错码传输的都是数字信号。
这既可用硬件实现，也可用软件实现。
前者主要用各种数字电路，主要是采用大规模集成电路。
软件实现特别适合计算机通信网等场合。
因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。
硬件实现的速度较高，比软件可快几个数量级。
在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。
因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。
纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。
在分组码的研究中，谱分析的方法受到人们的重视。
纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。
第二章CRC原理与介绍
2.1CRC介绍
CRC（CyclicRedundancyCheck）循环冗余校验码是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？
于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢贸然行动。
对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。
2.2CRC原理
2.2.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校验码。
2.2.2CRC码生成和校验
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．应用举例
发送端:
例如：
已知：
信息码：
1010信息多项式：
K（x）=X3+X生成码：
1011生成多项式：
G（x）=X3+X+1（r=3）
解：
1）（X3+X）*X3的积是X6+X4对应的码字是1010000
2）积／G（X）（按模二算法）由计算结果知冗余码是011，CRC码（码字）就是1010011
接收端：
例如：
已知：
接受码字：
1010011多项式：
T（x）=X6+X4+X+1生成码：
1011生成多项式：
G（x）=X3+X+1（r=3）
求：
码字的正确性。
若正确，则指出冗余码和信息码。
解：
1）用CRC码（码字）除以生成码，余数为0，所以CRC码（码字）正确。
2）因r=3，所以冗余码是：
011，信息码是:
1010。
第三章MATLAB语言编程与运行
3.1MATLAB语言的介绍
MATLAB是由美国MathWorks公司推出的用于数值计算和图形处理的科学计算系统环境。
MATLAB是英文MATrixLABoratory（矩阵实验室）的缩写。
它的第1版（DOS版本1.0）发行于1984年，经过10余年的不断改进，现在已推出它的Windows95版本（5.3版）。
新的版本集中了日常数学处理中的各种功能，包括高效的数值计算、矩阵运算、信号处理和图形生成等功能。
在MATLAB环境下，用户可以集成地进行程序设计、数值计算、图形绘制、输入输出、文件管理等各项操作。
MATLAB提供了一个人机交互的数学系统环境，该系统的基本数据结构是矩阵，在生成矩阵对象时，不要求明确的维数说明。
与利用C语言或FORTRAN语言作数值计算的程序设计相比，利用MATLAB可以节省大量的编程时间。
在美国的一些大学里，MATLAB正成为对数值线性代数以及其他一些高等应用数学课程进行辅助教学的有益工具。
在工程技术界，MATLAB也被用来解决一些实际课题和数学模型问题。
典型的应用包括数值计算、算法预设计与验证，以及一些特殊的矩阵计算应用，如自动控制理论、统计、数字信号处理（时间序列分析）等。
MATLAB系统由五个主要部分组成，下面分别加以介绍。
（1）MATLAB语言体系
MATLAB是高层次的矩阵/数组语言，具有条件控制、函数调用、数据结构、输入输出、面向对象等程序语言特性。
利用它既可以进行小规模编程，完成算发设计和算法实验的基本任务，也可以进行大规模编程，开发复杂的应用程序。
（2）MATLAB工作环境
这是对MATLAB提供给用户使用的管理功能的总称，包括管理工作空间的变量，数据输入输出的方式和方法，以及开发、调试、管理M文件的各种工具。
（3）图形句柄系统
这是MATLAB图形系统的基础，包括完成2D和3D数据图示、图像处理、动画生成、图形显示等功能的高层次MATLAB命令，也包括用户对图形图像等对象进行特性控制的低层次MATLAB命令，以及开发GUI应用程序的各种工具。
（4）MATLAB数学函数库
这是对MATLAB使用的各种数学算法的总称，包括各种初等函数的算法，也包括矩阵运算、矩阵分析等高层次数学算法。
（5）MATLAB应用程序接口（API）
这是MATLAB为用户提供的一个函数库，使得用户能够在MATLAB环境中使用C程序或FORTRAN程序，包括从MATLAB中调用子程序（动态链接），读写MAT文件的功能。
综上所述，可以看出MATLAB是一个功能十分强大的系统，是集数值计算、图形管理、程序开发为一体的环境。
除此之外，MATLAB还具有很强的功能扩展能力，与它的主系统一起，可以配置各种各样的工具箱，以完成一些特定的任务。
目前，MathWorks公司推出了18种工具箱。
用户可以根据自己的工作任务，开发自己的工具箱。
在本指导书中，我们主要利用MATLAB的关于信号处理的工具箱。
MATLAB具有程序结构控制、函数调用、数据结构、输入输出、面向对象等程序语言特征，而且简单易学、编程效率高。
MATLAB包含两部分内容：
基本部分和各种可选的工具箱。
MATLAB的源程序都是以扩展名为m的文件来存放的。
这种.m文件（或称m文件）其实就是一个纯文本文件，它采用的是MATLAB所特有的一套语言及语法规则。
本书应用MATLAB进行信号处理实际上就是通过编辑和运行这种.m文件来完成的。
.m文件有两种写法，一种称为脚本（Script），就像批处理文件一样，包含了一连串的MATLAB命令，执行时依序进行；另一种称为函数（Function），与在命令行中输入的命令一样，函数能接收输入的参数，然后执行并输出结果。
3.2程序流程图
N
Y
N
Y
3.3MATLAB程序
1．MATLAB程序编写
%CRC编码主程序
clear;clc;closeall;
uncode_sequence=randint（1,10）
sequence_length=length（uncode_sequence）;%得到原始信号长度
crc_ccitt=[10001000000100001];%常用的CRC生成多项式
add_bit=zeros（1,16）;%添加冗余比特位
crc_coded_sequence=[uncode_sequencezeros（1,16）];
%初始化输出检错码序列
uncode_sequence=[uncode_sequenceadd_bit];
remainder_bits=uncode_sequence;%初始化余数数组
fork=1:
sequence_length%开始循环计算长除得到最终余数
add_zeros=zeros（1,sequence_length-k）;%加入冗余位参与模2运算
register_bits=[crc_ccittadd_zeros];%构造除数数组
ifremainder_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=[10001000000100001];%常用的CRC生成多项式
remainder_bits=crc_coded_sequence;%初始化余数数组
cycle_length=sequence_length-length（crc_ccitt）+1;
%计算长除法的循环周期
fork=1:
cycle_length%开始循环计算长除得到最终余数
add_zeros=zeros（1,cycle_length-k）;
%加入冗余位参与模2运算
register_bits=[crc_ccittadd_zeros];%构造除数数组
ifremainder_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
ifsum（remainder_bits）==0%传输码元中没有发生奇数个错误
original_sequence=crc_coded_sequence（1:
cycle_length）
else
err=1%码元传输发生错误
end
2．MATLAB的运行结果
uncode_sequence=
1101001101
crc_coded_sequence=
11010011011100110000111010
original_sequence=
1101001101
>>
第四章结果分析
CRC校验的基本思想是利用线性编码理论，在发送端根据要传送一个n比特的帧或报文，发送器生成一个r比特的序列，称为帧检验序列（FCS）。
这样形成的帧将由（n+r）比特组成。
这个帧刚好能被某个预先规定的数整除。
接收器用相同的数去除外来的帧，结果无余数，则认为无差错。
循环冗余校验与奇偶校验不同，或者是一个字符校验一次，而前者是一个数据块校验一次。
在同步通信中，几乎都使用这种校验方法。
二进制多项式的加减运算为模2加减运算，即两个码多项式相加时，对应系数进行模2加减。
所谓模2加减就是各位做不带进位、借位的按位加
升级会员 