循环冗余码-CRC课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《循环冗余码-CRC课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 循环 冗余 CRC 课件
- 资源描述:
-
1、* Network Center (NC) of Qinghai Normal University CRC码算法码算法设G(x)为 r 阶,在帧的末尾加 r 个0,使帧为m + r位,相应多项式为xrM(x);按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串;按模2减法从对应于xrM(x)的位串中减去余数(等于或小于r位),结果就是要传送的带校验和的多项式T(x)。* Network Center (NC) of Qinghai Normal University CRC的检错能力的检错能力发送:T(x);接收:T(x) + E(x);余数(T(x) + E(x) / G(x)
2、= 0 + 余数(E(x) / G(x)若 余数(E(x) / G(x) = 0,则差错不能发现;否则,可以发现。 四个多项式已成为国际标准CRC-12 = x12 + x11 + x3 + x2 + x + 1CRC-16 = x16 + x15 + x2 + 1CRC-CCITT = x16 + x12 + x5 + 1CRC-32 硬件实现CRC校验。* Network Center (NC) of Qinghai Normal University1010001101000001101011101011101010110111011110101111010110101111110110
3、10110110011010111001011010101110n信息位串1010001101,K(x)x9+x7+ x3+x2+1n生成多项式110101,G(x)x5+x4+ x2 +1CRC计算例程* Network Center (NC) of Qinghai Normal UniversityCRC检测方法的特点 相比于奇偶校验法, CRC校验码的检错能力很强,而奇偶校验法实现简单,检错能力低,一般只适合于通信要求较低环境; CRC校验码除了能查出离散错外,还能检查出突发错,主要包括: 所有单个错; 全部离散的二位错; 全部奇数个错; 全部长度小于或等于K位的突发错(K是生成多项式的
4、最高幂);* Network Center (NC) of Qinghai Normal University检验和(checksum)算法| 检验字段初值置0;| 待检验的数据拆分成一个个与检验字段等长的分片,不足部分补0以满足长度要求;| 将所有分片逐位取反,并连续累加逐位取反,并连续累加,丢弃最高进位;| 计算结果置入检验字段;| 填充的0仅参与计算,不参与传输;| 检验字段自身不参与计算;| 接收段执行相同的过程,并将计算结果和传输过来的检验和进行比较以决定数据是否出现差错;| 适用于高层的字节型协议,如适用于高层的字节型协议,如IP、TCP、UDP等等;| 常见分片长度:常见分片长度
5、:8位、位、16位和位和32位。位。* Network Center (NC) of Qinghai Normal University检验和算法举例 待传输数据为:10010100,01110110,1100 计算过程 (10010100)+(01110110)=11110100 11110100+(11000000)=00110011 带检验和的传输数据是 10010100,01110110,1100 00110011* Network Center (NC) of Qinghai Normal University数据链路层通信模型数据链路层通信模型帧AP1缓存发送方AP2缓存接收方数据
6、链路高层数据链路主机A主机B层* Network Center (NC) of Qinghai Normal University数据链路层控制机制数据链路层功能:通过该层协议的作用,在一条不太可靠的通讯链路上实现可靠的数据传输;数据链路:在数据链路层,通讯的对等实体之间的数据传输通道,包括物理链路和必要的传输控制规程;理想的数据链路基于以下两个假设: 不管发方以多快的速率发送数据,收方总能够来得及接收、处理并上交。也就是说收方有足够的接收缓存区和处理速度; 链路是理想的传输通道,传输的任何数据既不会出现差错也不会丢失;* Network Center (NC) of Qinghai Norm
7、al University数据链路层控制机制 流量控制:保证发送数据在如何情况下都不会“淹没”收方接收缓存区,而且还应使传输达到理想的吞吐率,由收方控制发方的数据流量是计算机网络中流量控制的一个基本思路;一个重要的方法是滑动窗口机制。 差错控制:使得链路传输出现差错时等到补救。主要有两种差错发生,帧丢失和帧损坏。基本方式是确定重发机制(反馈重发纠错)数据链路层控制机制* Network Center (NC) of Qinghai Normal University4.5 滑动窗口机制机制:在发送方和接收方分别设置发送窗口和接收窗口,在数据传输过程中受控的向前滑动,从而控制传输过程。 发送窗口
8、:对发方进行流量控制,其大小WT指明在收到对方ACK之前发方最多可以发送多少个数据帧,落在窗口内的帧可以连续发送。 接收窗口:控制哪些数据帧可以接收,只有到达的数据帧的序号落在接收窗口内时才可以被接收,否则将被丢弃。当收方收到一个有序且无差错的帧后,接收窗口想起滑动,准备接收下一帧,并向发方发送一个确认(ACK)。为了提高效率收方可以采用累积确认或捎带确认。* Network Center (NC) of Qinghai Normal University发送方的滑动窗口作用设发送序号用3个比特编码,WT5* Network Center (NC) of Qinghai Normal Univ
9、ersity4.6 停等协议 差错控制的基本方式是确认重发机制,即反馈重发纠错,收方对收到的数据予以某种形式的反馈信息,发方根据反馈信息对出错的帧进行重发。一般基于以下措施:差错发现确认ACK累积确认负确认(NAK)超时重发 确认重发机制又称为自动请求重发(ARQ),根据确认重发方式不同,分为停等ARQ、回退-N ARQ、选择重传ARQ。* Network Center (NC) of Qinghai Normal University停等ARQ 停等ARQ机制:在发方发出一个数据帧后停下来不再发送,等待收方ACK到达后再发送下一帧。(实际使用滑动窗口技术,发送窗口WT=1,接收窗口也是1)
10、处理的差错问题: 收方收到发来的数据帧,但检测出帧有差错; 发方发出的数据帧丢失,收方不可能发出ACK; 收方收到数据帧,但ACK丢失;(重复帧处理,对数据帧和确认帧边上序号,对于停等ARQ,用0和1交替编号。发方正确收到0/1号数据帧,发回ACK1/ACK0,确认序号表明期待收到的下一个序号)* Network Center (NC) of Qinghai Normal University在无差错的正常情况下,停等ARQ把流量控制在每往返时间一个数据帧的水平,一个往返时间为:TDATA+TACK+2+TPRO链路利用率=TDATA/(TDATA+TACK+2+TPRO) TDATA/(TD
11、ATA+2) =1/(1+2) = / TDATA=链路比特长度/帧比特长度出错差错而重传情况下,停等ARQ引起的重传时间等于超时重传的定时时间TOUT解决链路利用率低的办法:回退-N ARQ和选择重传ARQ停等ARQ的效率分析* Network Center (NC) of Qinghai Normal University回退-N ARQ使用滑动窗口机制,WT1,WR=1,发方在每收到一个ACK之前不用等待,可以连续发送窗口内的多个帧,如果这时收到ACK,还可以则调整发方窗口,继续发送后续的帧;(连续ARQ)对于发送的每一帧设置超时定时器,发方发出一个帧后启动该定时器。若因帧效验错误、帧丢
12、失、ACK丢失使定时器超时后还没有收到ACK,发方则要重复此帧,而且还必须重发此帧后面所有的已发帧;(回退-N ARQ)收方每收到一次失序的数据帧时都重发上次发送过的ACK,这可弥补上次已发送的确认帧的丢失;* Network Center (NC) of Qinghai Normal University回退-N ARQ * Network Center (NC) of Qinghai Normal University选择重传ARQ 接收窗口WR1,这样可以接收和保存正确到达的失序帧 出现传输差错时只重传出错的帧,后续的正确到达的帧不再重传,提高了信道的利用率 WT=WR=2n/2* Ne
13、twork Center (NC) of Qinghai Normal University4.5 停等协议前面介绍了帧边界的划分办法和检查帧是否错误的方法,如果帧在传输过程中出现错误,发送方就要重发错误帧,如何控制帧重发? 简单停等协议 带流量控制的停等协议 带差错控制的停等协议* Network Center (NC) of Qinghai Normal University简单停等协议假设:通信线路(信道)不损坏或丢失信息帧。发送数据的速率低于接受数据的速率理想传输协议、单工传输工作过程 发送程序: 取数据,构成帧,发送帧; 接收程序:等待,接收帧,送数据给高层。* Network Ce
14、nter (NC) of Qinghai Normal University带流量控制的停等协议无差错单工停等协议增加约束条件:接收方不能无休止接收。 例如:缓冲区数量有限,接受速率比发送速率低等。解决办法: 接收方每收到一个帧后,给发送方回送一个响应。接收方每收到一个帧后,给发送方回送一个响应。工作过程发送程序:取数据,成帧,发送帧,等待响应帧;接收程序:等待,接收帧,送数据给高层,回送响应帧。* Network Center (NC) of Qinghai Normal University带差错控制的停等协议增加约束条件:信道(线路)有差错,信息帧可能损坏或丢失。 使用正向应答正向应答+
15、重发机制重发机制来解决差错的控制问题。 使用超时重发计时器解决数据帧、确认帧丢失问题。 为判断重复帧重复帧,必须在数据帧附加上不同的发送序号,数据序号采用循环序号循环序号机制。 协议效率低协议效率低* Network Center (NC) of Qinghai Normal University数据帧差错情况时间送主机BA(a)正常情况DATA0DATA1ACKACK送主机BA(b)数据帧出错DATA0DATA0NAKACK送主机出错BA(c)数据帧丢失DATA0DATA0ACK送主机丢失重传超时BA(d)确认帧丢失DATA0DATA0ACK重传超时ACK丢失送主机丢弃* Network C
16、enter (NC) of Qinghai Normal University有噪声信道单工停等协议流程图从网络层取数,成帧从网络层取数,成帧发送帧发送帧帧到否帧到否应答到否应答到否超时否超时否重复重复正确否正确否接收帧,送网络层接收帧,送网络层发应答发应答发送帧发送帧应答帧应答帧YNYNYNNY定时器定时器丢弃丢弃丢弃丢弃NY注:P127* Network Center (NC) of Qinghai Normal University数据帧间时序关系BADATAACKDATA传播时延tp 传播时延tp 处理时延处理时延tpr 确认帧发送时间ta tpr 时间连续成功发送数据帧之间的最小时间
17、间隔tT 数据帧发送时间tf 重传时间tout * Network Center (NC) of Qinghai Normal University停等协议的效率分析 重传时间 两个发送成功的数据帧间最小时间间隔 正确传送一个数据帧所需的平均时间: tavtT (1一个帧的平均重传次数) 1(1)(1)niavTTTittpip ttp* Network Center (NC) of Qinghai Normal University停等协议的效率分析(续)每秒成功发送的最大帧数就是链路的最大吞吐量max,显然:max1/ tav(1-p)/ tT。在发送方,设数据帧的实际到达率为(即每秒到达
18、个帧),则不应超过最大吞吐量max,即(1-p)/ tT,用时间tf进行规一化,得出规一化的吞吐量为: tf (1-p)/1,其中参数是tT的规一化时间: tT/tf 1。当重传时间小于发送时间时,1,此时的规一化吞吐量 (1-p)。针对单工协议效率低,引入连续ARQ和选择重传ARQ 。* Network Center (NC) of Qinghai Normal University4.6 连续ARQ协议 1、工作原理连续停等协议是指不需要等前面帧的应答收到就可连续连续停等协议是指不需要等前面帧的应答收到就可连续不断的发下面的帧。不断的发下面的帧。1)全部重发流水线协议)全部重发流水线协议当
19、一帧出错时,需重发出错帧之后的所有帧;接收方的缓冲区数量只需要一个。2)选择重发流水线协议)选择重发流水线协议当一帧出错时,只重发出错帧;接收方的缓冲区数量足够多。* Network Center (NC) of Qinghai Normal UniversityDATA0ACK1ACK1确认DATA0DATA1ACK2确认DATA1ACK2DATA2 ?DATA3DATA4DATA5重传时间tout ACK2DATA3乱序,丢弃,重传ACK2ACK2ACK2DATA4乱序,丢弃,重传ACK2DATA5乱序,丢弃,重传ACK2重传DATA2重传DATA3重传DATA4重传DATA5ACK3AC
展开阅读全文