计算机通信课设讲解Word文档下载推荐.docx
- 文档编号:6290293
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:184.09KB
计算机通信课设讲解Word文档下载推荐.docx
《计算机通信课设讲解Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《计算机通信课设讲解Word文档下载推荐.docx(17页珍藏版)》请在冰点文库上搜索。
CRC校验的基本思想是利用线性编码理论,在发送端根据要传送一个
比特的帧或者报文,发送器生成一个
比特的序列,称为帧检验序列(FCS)。
这样所形成的帧将由
比特组成。
这个帧刚好能被某个预先确定的数整除。
接收器用相同的数去除外来的帧,如果无余数,则认为无差错。
循环冗余校验码与奇偶校验码不同,后者是字符校验一次,而前者是字符串校验一次。
在同步串行通信中,几乎都是用这种校验方法。
一个n位的循环码是由k位信息位加上r位校验位组成的,其中r=n-k。
如图1所示。
k位r位(r=n-k)
信息位校验位(CRC校验)
图1n位循环码
通常把这样的新组成的二进制位序列叫做循环冗余码(CRC)。
表征CRC码
的多项式叫生成多项式。
K位二进制数加上r位CRC码后,即信息位要向左移
(n-r)位,这相当于B(X)乘以X^rB(X)被生成多项式除,得整数多项式加上余数多项式。
由以上分析可知,CRC校验的关键是如何求出余数,此余数即为校验码(CRC校验码)。
以前通常用数字电路来实现,而现在用计算机来完成。
2.2循环冗余校验码(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)*XR),这样f(x)的右边就会空出R位,这就是校验码的位置。
通过f(x)*XR除以生成多项式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除,应使余数循环。
将这些要求反映为数学关系是比较复杂的。
但可以从有关资料查到常用的对应于不同码制的生成多项式如图2所示:
N
K
码距d
G(x)多项式
G(x)
7
4
3
x3+x+1
1011
7
4
3
x3+x2+1
1101
3
x4+x3+x2+1
11101
x4+x2+x+1
10111
15
11
x4+x+1
10011
7
5
x8+x7+x6+x4+1
111010001
31
26
3
x5+x2+1
100101
21
5
x10+x9+x8+x6+x5+x3+1
11101101001
63
57
x6+x+1
1000011
51
x12+x10+x5+x4+x2+1
1010000110101
1041
1024
x16+x15+x2+1
11000000000000101
图2常用的生成多项式
3、模2除(按位除)
模2除做法与算术除法类似,但每一位除(减)的结果不影响其它位,即不向上一位借位。
所以实际上就是异或。
然后再移位做下一位的模2减。
步骤如下:
a、用除数对被除数最高几位做模2减,没有借位。
b、除数右移一位,若余数最高位为1,商为1,并对余数做模2减。
若余数最高位为0,商为0,除数继续右移一位。
c、一直做到余数的位数小于除数时,该余数就是最终余数。
4、CRC码的生成步骤
(1)将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
(2)将信息码左移R位得到多项式f(x)*XR。
(3)用生成多项式(二进制数)对f(x)*XR做模2除,得到余数(即校验码)。
(4)将余数多项式加到f(x)*XR中,得到完整的CRC码。
【例】假设使用的生成多项式是G(x)=x3+x+1。
4位的原始报文为1010,求编码后的报文。
解:
(1)将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。
(2)此题生成多项式有4位(R+1),要把原始报文F(x)左移3(R)位变成1010000
(3)用生成多项式对应的二进制数对左移4位后的原始报文进行模2除:
1001-------商
------------------------
1010000
1011----------除数
------------
1000
1011
11-------余数(校验位)
(4)编码后的报文(CRC码):
+
11
------------------
1010011
CRC码为1010011(和纠错)。
在接收端收到了CRC码后用生成多项式为G(x)去做模2除,若得到余数为0,则码字无误。
若得到余数不为0,则接收的数据有错。
5、通信与网络中常用的CRC
在数据通信与网络中,通常k相当大,由一千甚至数千数据位构成一帧,而后采用CRC码产生r位的校验位。
它只能检测出错误,而不能纠正错误。
一般取r=16,标准的16位生成多项式有CRC-16=x16+x15+x2+1和CRC-CCITT=x16+x15+x2+1。
CRC码在发送端编码和接收端校验时,都可以利用事先约定的生成多项式
来得到。
位要发送的信息位可对应于一个
次多项式
,
位冗余位则对应于一个
,由
位信息位后面加上
位冗余位组成的
位码字则对应于一个
。
由信息位产生冗余位的编码过程,就是已知
求
的过程。
在CRC码中可以通过找到一个特定的
(其最高项
的系数恒为1),然后用
去除以
,得到的余式就是
特别要强调的是,这些多项式中的“+”都是模2加(也即异或运算),此外,这里的除法用的也是模2除法,即除法过程中用到的减法是模2减法,它和模2加法的运算规则一样,都是异或运算,这是一种不考虑加法进位和减法借位的运算,即
在进行基于模2运算的多项式除法时,只要部分余数首位为1,便可上商1,否则上商0。
然后按模2减法求得余数,该余数不计最高位。
当被除数逐位除完时,最后得到比除数少一位的余数。
此余数即为冗余位,将其添加在信息位后便构成CRC码字。
若传输过程无错,则接收方收到的码字也对应于此多项式,也即接收到的码字多项式能被
整除。
因而接收端的校验过程就是将接收到的码字多项式除以
若余式为零则认为传输无差错,若余式不为零则传输有差错。
第3章循环冗余校验码CRC的系统分析
3.1循环冗余校验码CRC算法设定
循环冗余校验码CRC是线性分组码的一种,具有严密的代数学理论。
循环码除了具有线性分组码的封闭性,即两个循环码组的模二加仍是一个循环码组外,还具有循环性,即一个循环码组循环移位后,将最右端的码组移至左端,仍是一个循环码组。
本次课程设计选取循环冗余校验CRC码的生成多项式
3.2循环冗余校验码CRC算法分析
3.2.1CRC码编码规则
CRC码是由两部分组成,前部分是信息码,就是需要校验的信息;
后部分是校验码,如果CRC码共长n个bit,信息码长k个bit,就称为(n,k)码。
它的编码规则是:
1、移位:
将原信息码(kbit)左移r位(k+r=n)
2、相除:
运用一个生成多项式
(也可看成二进制数)用模2除以生成多项式
,得到的余数就是校验码。
非常简单,要说明的:
模2除就是在除的过程中用模2加,模2加实际上就是我们熟悉的异或运算,就是加法不考虑进位,公式是0+0=1+1=0,1+0=0+1=1即‘异’则真,‘非异’则假。
由此得到定理:
a+b+b=a也就是‘模2减’和‘模2加’直值表完全相同。
有了加减法就可以用来定义模2除法,于是就可以用生成多项式g(x)生成CRC校验码。
3.2.2CRC校验码的性质
可靠性:
除了正好数据块的比特值是按除数值变化的错误外,循环冗余校验讲检测出其他所有错误,甚至对于上面所提到的四比特错误——这种情况放生的可能性仍然是很小的。
而且,常用的CRC除数通常有17或是33比特,使得不可检测的错误可能降低到几乎近于零。
3.3系统流程图
利用MATLAB对CRC循环冗余校验码的生成及还原过程进行仿真,其编码的流程图如图3所示。
N
结束
余数是否为零
是否除完
输出error=0
输出接收端的码
用合成码长除生成多项式
合成编码序列输出
循环计算长除
添加冗余比特位
初始化,随机产生信息码并输出
开始
图3系统流程图
第4章循环冗余校验码CRC程序设计
根据循环冗余校验码CRC的编码原理用MATLAB软件写出以下程序代码,程序中运用了CRC-16码,首先自定义一个生成多项式
,将生成多项式系数写成二进制序列[11001],然后编码序列后面补零,补零的个数比生成多项式二进制序列位数少一位,补零后的编码序列作为被除数,生成多项式二进制序列作为除数,进行长除,求出余数,此余数为冗余位。
而循环冗余校验码CRC是编码序列加冗余位,在此次课程设计中即为[1101100110111],如果得到的循环冗余校验码CRC二进制序列除以生成多项式二进制序列,若余数为零,则译码无差错,若余数不为零,则译码有差错。
4.1循环冗余校验码CRC编码程序
MATLAB编程
%CRC编码主程序
clear;
clc;
closeall;
uncode_sequence=input('
输入信息码:
'
);
%信息码
sequence_length=length(uncode_sequence);
%得到原始信号长度
crc_ccitt=[11001];
%常用的CRC生成多项式
add_bit=zeros(1,4);
%添加冗余比特位
crc_coded_sequence=[uncode_sequencezeros(1,4)];
%初始化输出检错码序列
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位
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;
%初始化输出序列
remainder_bits=crc_coded_sequence;
cycle_length=sequence_length-length(crc_ccitt)+1;
%计算长除法的循环周期
cycle_length%开始循环计算长除得到最终余数
add_zeros=zeros(1,cycle_length-k);
ifremainder_bits
(1)==0%被除数第一位为0则将除数所有位置0
remainder_bits=bitxor(register_bits,remainder_bits);
%将寄存器恢复为除数数组
remainder_bits
(1)=[];
ifsum(remainder_bits)==0
%传输码元中没有发生奇数个错误
original_sequence=crc_coded_sequence(1:
cycle_length)
else
err=1%码元传输发生错误
根据循环冗余校验码CRC的编码原理用MATLAB软件写出以上程序代码,程序中运用了CRC-16码,首先自定义一个生成多项式
用MATLAB编码程序如图4-1所示。
图4-1循环冗余校验码CRC编码、译码程序仿真
编码、译码之后的结果如图4-2所示。
图4-2循环冗余校验码CRC编码、译码仿真结果
第5章循环冗余校验CRC的结果分析
CRC校验的基本思想是利用线性编码理论,在发送端根据要传送一个n比特的帧或报文,发送器生成一个r比特的序列,称为帧检验序列(FCS)。
这样形成的帧将由(n+r)比特组成。
这个帧刚好能被某个预先规定的数整除。
接收器用相同的数去除外来的帧,结果无余数,则认为无差错。
循环冗余校验与奇偶校验不同,或者是一个字符校验一次,而前者是一个数
据块校验一次。
在同步通信中,几乎都使用这种校验方法。
二进制多项式的加减运算为模2加减运算,即两个码多项式相加时,对应系
数进行模2加减。
所谓模2加减就是各位做不带进位、借位的按位加减。
这种加
减运算实际上是逻辑上的异或运算,即加法和减法等价。
信息码多项式和余数多项式可以合并成一个新的多项式,称为循环码的码多项式,则该多项式是生成多项式的整数倍,即能被声称多项式整除。
根据这一原理,在发送端用信息码多项式除以生成多项式所得的余数多项式就是所要加的监督位。
将循环码的码多项式除以生成多项式,若能除尽,说明传输正确,否则说明出错。
CRC校验的关键是如何求出余数,此余数即为校验码(CRC)校验码。
以前用数字电路来实现,而现在可以用计算机来完成。
为了传输的正确性,在接收端要有一个CRC检验器。
它的功能和发生器一样,
当收到CRC冗余校验码后,做同样的模2除法,注意,这里采用的生成多项式一
定要与发送端相同。
如果余数是0,则说明传输正确,否则,传输错误,应重传。
本次课设通过对循环冗余校验码CRC的编译码的设计与仿真得出仿真过程得的结果和理论是一致的。
参考文献
[1]樊昌信著.通信原理[M].国防工业出版社,1999,10.
[2]宋祖顺著.现代通信原理[M].电子工业出版社,2001,2.
[3]黄新亚,米央编著.信息编码技术及其应用大全[M].电子工业出版社,1994.8
[4]孙丽华著.信息论与纠错编码[M].电子工业出版社,2005,3
[5]Proakis著,张力军译.数字通信(第四版)[M].电子工业出版社,2004,7.
[6]潘新民著.计算机通信技术(第二版)[M].电子工业出版社,2006,7.
[7]吴玲达,李国辉,杨冰等著.计算机通信原理与技术[M].国防科技大学出版社,2003,3.
致谢
通过这段时间的课程设计,我感觉自己学到了很多的技能,在设计的过程中,我还从老师身上学到好多东西:
彭老师教学认真,他用实际行动告诉我们在工作中要脚踏实地,在学术上要严谨,在思维上要活跃,在学业上要勤奋刻苦。
做设计的过程中,我们都会遇到大大小小的问题,有许多不懂得地方,因为有老师的全程跟进,不时的给我们进行疑难解答,使我们对有的问题能够迎刃而解,在老师的指导下我一步步的解决问题完成论文,在完成过程中老师指导我去怎么选择资料,如何去利用网络资源,在这个学习的过程中,我了解到MATLAB软件的实用价值,更深的理解循环冗余校验码的原理。
经过我的努力和老师的耐心指导本次设计顺利按时完成,它是对我们把所学的理论知识运用到实践中的一次系统的检验。
在本次设计中,在老师的指导和帮助下,我完成了课设内容。
在此我十分的感谢此次课设的所有的辅导老师,正是通过他们的认真传授和细心讲解我们才能如此顺利的完成此次课程设计。
最后,感谢所有辅导老师的耐心指导和同学们热心的帮助。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 通信 讲解