循环冗余校验码的仿真与实现1综述.docx
- 文档编号:10667171
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:23
- 大小:154.72KB
循环冗余校验码的仿真与实现1综述.docx
《循环冗余校验码的仿真与实现1综述.docx》由会员分享,可在线阅读,更多相关《循环冗余校验码的仿真与实现1综述.docx(23页珍藏版)》请在冰点文库上搜索。
循环冗余校验码的仿真与实现1综述
******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2013年秋季学期
《计算机通信与网络》课程设计
题目:
(15,11)CRC冗余校验码的编译码仿真实现
专业班级:
通信工程(4)班
姓名:
王强
学号:
10250424
指导教师:
彭清斌
成绩:
摘要
现代社会的生产和生活都需要借助计算机网络来完成,在计算机网络日益发达的今天,人们对数据传输的准确性和传输的速度要求越来越高,数据传输不仅要保证实时,还要保证准确。
因此,数据通信技术是计算机通信网络技术发展的基础,已经为现代生活中不可缺少的一部分。
但是通过通信信道传输的数据往往会有差错的产生,而且差错的产生是不可避免的,因此我们的任务是分析循环码算法的实现原理及研究检查是否出现差错及如何纠正差错。
循环冗余校验码(CRC)是目前应用最广的纠错编码之一。
本次课设论述了循环冗余码的算法及其在数据通信中的作用,研究了纠错码及循环冗余校验码的原理,以及利用MATLAB对其进行了编程和编译仿真,实现了CRC循环冗余校验码的编码及校验,在接收端收到通过校验的码,从而确定传输过程是否出错,得到的结论和理论上是否一致。
关键词:
检错码CRC循环冗余校验码MATLAB计算机通信
目录
前言1
一、基本原理2
1.1计算机通信与纠错码2
1.1.1计算机通信2
1.1.2纠错码2
1.1.3纠错原理3
1.2CRC循环冗余校验码4
1.2.1CRC的介绍4
1.2.2CRC的基本原理5
二、推导过程9
三、MATLAB语言编程与运行11
3.1MATLAB语言的介绍11
3.2程序流程图13
3.3MATLAB程序14
设计总结17
致谢18
参考文献19
前言
通信技术的发展和新业务的不断出现对计算机网络通信系统的服务质量和数据的传输速度提出了更高的要求,数据交换量的迅速增加也加重了计算机网络的通信负担,网络很难对所有的数据进行完全正确的传输,网络通信中的实时差错控制技术显得尤为重要。
本设计中
对实时差错控制的分类和检测方法进行了分析,并在此基础上提出网络通信实时差错的控制方式。
CRC校验也叫循环冗余校验码,它在数据通信中利用广泛,技术人员可以任意选定校验字段和信息字段的长度,具有纠错能力强、知名度高以及应用广泛的特点。
CRC校验的原理是在k位的信息码之后拼接r位校验码,编码的整个长度是n位。
该种校验属于分块的校验,在编码的过程中会生成一段校验码,并将原信息与校验码一同发送到接收端。
同时,本次课程设计利用MATLAB软件进行仿真,并通过仿真的结果对CRC码做出分析,得出相应的结果,进而对于实时网络通信中的实时差错控制不仅有完备的编码方式和编码方法,还通过质量评估来保证了差错控制系统的性能良好,差错控制技术在计算机网络通信中的作用也越来越明显。
一、基本原理
1.1计算机通信与纠错码
1.1.1计算机通信
计算机通信是一种以数据通信形式出现,在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。
它是现代计算机技术与通信技术相融合的产物,在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。
计算机通信按照传输连接方式的不同,可分为直接式和间接式两种。
直接式是指将两部计算机直接相联进行通信,可以是点对点,也可以是多点通播。
间接式是指通信双方必须通过交换网络进行传输。
按照通信覆盖地域的广度,计算机通信通常分为局域式、城域式和广域式三类。
局域式是指在一局部的地域范围内(例如一个机关、学校、军营等)建立计算机通信。
局域计算机通信覆盖地区的直径在数公里以内。
城域式是指在一个城市范围内所建立的计算机通信。
城域计算机通信覆盖地区的直径在十公里到数十公里。
广域式是指在一个广泛的地域范围内所建立的计算机通信。
通信范围可以超越城市和国家,以至于全球。
广域计算机通信覆盖地区的直径一般在数十公里到数干公里乃至上万公里。
在通常情况下,计算机通信都是由多台计算机通过通信线路连接成计算机通信网进行的,这样可共享网络资源,充分发挥计算机系统的效能。
1.1.2纠错码
纠错码(errorcorrectingcode),在传输过程中发生错误后能在收端自行发现或纠正的码。
仅用来发现错误的码一般常称为检错码。
为使一种码具有检错或纠错能力,须对原码字增加多余的码元,以扩大码字之间的差别,即把原码字按某种规则变成有一定剩余度(见信源编码)的码字,并使每个码字的码之间有一定的关系。
关系的建立称为编码。
码字到达收端后,可以根据编码规则是否满足以判定有无错误。
当不能满足时,按一定规则确定错误所在位置并予以纠正。
纠错并恢复原码字的过程称为译码。
检错码与其他手段结合使用,可以纠错。
纠错编码又称信道编码,它与信源编码是信息传输的两个方面。
它们之间存在对偶的关系。
应用信道译码直接对一些自然信息进行处理,可以去掉剩余度,以达到压缩数据的目的。
为了使一种码具有检错或纠错能力,必须对原码字增加多余的码元,以扩大码字之间的差别,使一个码字在一定数目内的码元上发生错误时,不致错成另一个码字。
准确地说,即把原码字按某种规则变成有一定剩余度的码字,并使每个码字的码元间有一定的关系。
关系的建立称为编码。
码字到达收端后,用编码时所用的规则去检验。
如果没有错误,则原规则一定满足,否则就不满足。
由此可以根据编码规则是否满足以判定有无错误。
当不能满足时,在可纠能力之内按一定的规则确定错误所在的位置,并予以纠正。
纠错并恢复原码字的过程称为译码;码元间的关系为线性时,称为线性码;否则称为非线性码。
检错码与其他手段结合使用,可以纠错。
检错反馈重发系统(ARQ系统)就是一例。
在构造纠错码时,将输入信息分成k位一组以进行编码。
若编出的校验位仅与本组的信息位有关,则称这样的码为分组码。
若不仅与本组的k个信息位有关,而且与前若干组的信息位有关,则称为格码。
这种码之所以称为格码,是因为用图形分析时它象篱笆或格架。
线性格码在运算时为卷积运算,所以叫卷积码。
1.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基本无关。
可惜,已经找到的码能满足这样要求的很少。
不过由于大规模集成电路的发展,既使应用比较复杂的但性能良好的码,成本也并不太高。
因此,纠错码的应用越来越广泛。
纠错码传输的都是数字信号。
这既可用硬件实现,也可用软件实现。
前者主要用各种数字电路,主要是采用大规模集成电路。
软件实现特别适合计算机通信网等场合。
因为这时可以直接利用网中的计算机进行编码和译码,不需要另加专用设备。
硬件实现的速度较高,比软件可快几个数量级。
在传信率一定的情况下,如果采用纠错码提高可靠性,要求信道的传输率增加,带宽加大。
因此,纠错码主要用于功率受限制而带宽较大的信道,如卫星、散射等系统中。
纠错码还用在一些可靠性要求较高,但设备或器件的可靠性较差,而余量较大的场合,如磁带、磁盘和半导体存储器等。
在分组码的研究中,谱分析的方法受到人们的重视。
纠同步错误码、算术码、不对称码、不等错误纠正码等,也得到较多的研究。
1.2CRC循环冗余校验码
1.2.1CRC的介绍
在计算机通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余校验码CRC(CyclicalRedundancyChecking),又称多项式码。
这使因为,任何一个由二进制数位串组成的代码都可以和一个含有0和1两个系数的多项式建立一一对应关系,一个k位帧可以看成是从
到
的k次多项式的系数序列,这个多项式的阶数为k-1,高位(最左边)是
项的系数,下一位是
例如,1011011有7位,表示生成多项式是
;而生成多项式
对应的位串是110110。
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.2.2CRC的基本原理
CRC校验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。
在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。
16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(乘以216)后,再除以一个多项式,最后所得到的余数既是CRC码。
求CRC码所采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符合同样的规律。
接收方将接收到的二进制序列数(包括信息码和CRC码)除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误。
在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)=
,可转换为二进制数码11011。
而发送信息位1111,可转换为数据多项式为C(x)=
。
2、生成多项式
是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。
在发送方,利用生成多项式对信息多项式做模2除生成校验码。
在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
应满足以下条件:
a、生成多项式的最高位和最低位必须为1。
b、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做模2除后应该使余数不为0。
c、不同位发生错误时,应该使余数不同。
d、对余数继续做模2除,应使余数循环。
将这些要求反映为数学关系是比较复杂的。
但可以从有关资料查到常用的对应于不同码制的生成多项式如下所示:
N K 码距d G(x)多项式 G(x)
7 4 3
1011
7 4 3
1101
7 3 4
11101
7 3 4
10111
15 11 3
10011
15 7 5
111010001
31 26 3
100101
31 21 5
11101101001
63 57 3
1000011
63 51 5
1010000110101
1041 1024
11000000000000101
3、模2除(按位除)
模2除做法与算术除法类似,但每一位除(减)的结果不影响其它位,即不向上一位借位。
所以实际上就是异或。
然后再移位移位做下一位的模2减。
步骤如下:
a、用除数对被除数最高几位做模2减,没有借位。
b、除数右移一位,若余数最高位为1,商为1,并对余数做模2减。
若余数最高位为0,商为0,除数继续右移一位。
c、一直做到余数的位数小于除数时,该余数就是最终余数。
4、CRC码的生成步骤
生成CRC码的基本原理:
任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。
例如:
代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。
(1)、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
(2)、将信息码左移R位,相当与对应的信息多项式C(x)*2R
(3)、用生成多项式(二进制数)对信息码做模2除,得到R位的余数。
(4)、将余数拼到信息码左移后空出的位置,得到完整的CRC码。
5、CRC的和纠错
在接收端收到了CRC码后用生成多项式为G(x)去做模2除,若得到余数为0,则码字无误。
若如果有一位出错,则余数不为0,而且不同位出错,其余数也不同。
可以证明,余数与出错位的对应关系只与码制及生成多项式有关,而与待测碼字(信息位)无关。
下面给出了G(x)=1011,C(x)=1010的出错模式,改变C(x)(码字),只会改变表中码字内容,不改变余数与出错位的对应关系。
收到的CRC码字 余数 出错位
码位 A7 A6 A5 A4 A3A2 A1
正确 1 0 1 0 0 1 1
错误 1 0 1 0 0 1 0
1 0 1 0 0 0 1
1 0 1 0 1 1 1
1 0 1 1 0 1 1
1 0 0 0 0 1 1
1 1 1 0 0 1 1
0 0 1 0 0 1 1
001010100011110111101 1234567
得出(7,4)CRC码的出错模式(G(x)=1011),如果循环码有一位出错,用G(x)作模2除将得到一个不为0的余数。
如果对余数补0继续除下去,我们将发现一个有趣的结果;各次余数将按图10顺序循环。
例如第一位出错,余数将为001,补0后再除,第二次余数为010,以后依次为100,0ll…,反复循环,这就是“循环码”名称的由来。
这是一个有价值的特点。
如果我们在求出余数不为0后,一边对余数补0继续做模2除,同时让被检测的校验码字循环左移。
图10说明,当出现余数(101)时,出错位也移到A7位置。
可通过异或门将它纠正后在下一次移位时送回A1。
这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。
当位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因。
在串行通信中,生成多项式的选取时提高差错控制能力的关键因素。
在使用中,通常使用下列三种生成多项式
来产生CRC校验码。
CRC-16:
=
+
+
CRC-CCITT:
=
CRC-32:
=
CRC检验是一种较为简单的检验方法,而且纠错能力强,特别适合检测突发性错误,在计算机中得到广泛应用,是目前应用最多的一种校验方法之一。
一般情况下,r位生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于r的突发错以及(1-2-(r-1))的突发长度为r+1的突发错和(1-2-r)的突发长度大于r+1的突发错。
例如,对上述r=16的情况,就能检测出所有突发长度小于等于16的突发错以及99.997%的突发长度为17的突发错和99.998%的突发长度大于17的突发错。
所以CRC码的检错能力还是很强的。
这里,突发错误是指几乎是连续发生的一串错,突发长度就是指从出错的第一位到出错的最后一位的长度(但是,中间并不一定每一位都错)。
6、计算余数的二进制除法
第一步,要在数据位(被除数)后边补0,0的个数比除数(生成多项式)少一位。
第二步,做除法,从被除数的头五位减去五位的除数。
除数的每一位都与被除数的对应位在不涉及上一位的情况下独立进行减法(实际进行的是模2加)。
在本例中,除数11001与被除数的前五位10110进行的是模2加,得到1111(余数1前面的0被省略)。
在被除数中下一个没有使用过的比特接着被抄录下来,使得余数的位数和除数的位数相同。
如果位数不够,在商位补0(这与一般除法相同),因此,下一步就是1111011001,结果是111,依次类推。
在二进制除法中,除数总是以1开头的,然后从上一次的被除数/余数中与除数位数相同的部分中减去除数,并且只能从最左位是1的被除数/余数中减去除数。
每当被除数/余数的最左位是0时,就在该步骤中把0丢弃,再把被除数中的下一个未使用比特抄录下来填充余数,同时对应的商数位补一个零,并按上述方法进行二进制除法运算,一直重复这个过程直到被除数中所有比特都被使用过。
余数100只有3位,而余数应为4位(比除数少一位),因此,取校验码时应在前面填一个0,故其CRC校验码应为0100,于是可求出该信息码的循环冗余码为101100110100。
二、推导过程
本文要求实现(15,11)冗余循环校验的仿真实现,所以n=15,k=11,r=15-11=4。
即生成多项式G(x)的最高次幂是4次方,转化为二进制有r+1=4+1=5位。
根据生成多项式应满足的要求和查资料,可设G(x)=x4+x+1,对应的二进制数为10011。
11位的原始报文为11101010001,再根据校验码生成步骤可写出它的推导过程。
10110
10011
10011
10110
11001
11100
10011
11010
10011
0000
三、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种工具箱。
用户可以根据自己的工作任务
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 循环 冗余 校验码 仿真 实现 综述