第8讲 海明码和滑动窗口机制

《第8讲 海明码和滑动窗口机制》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8讲海明码和流量控制协议海明码流量控制非受限协议停-等协议退后N帧协议选择性重传协议海明码码字（codeword）：一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字海明距离（Hammingdistance）：两个码字之间不同的比特位数目例：0000000000与0000011111的海明距离为5编码系统中，任意两个码字的最小码距就是该编码系统的码距海明码信息序号a0a1a200001001201030114100510161107111信息序号a0a1a2a3000001100121010300114110050101601107111

2、1系统码距为1系统码距为2海明码为使系统检测一位错误，码距最小为2为使系统纠正一位错误，码距最小为3海明码系统中，有关系式：L－1＝C＋DL：码距D：检错位数C：纠错位数D≥C码距检错纠错100210311421522632733海明码海明距离与纠错性能如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字为了检查d个错，需要使用海明距离为d+1的编码为了纠正d个错，需要使用海明距离为2d+1的编码海明码设计纠错码要求：纠正单比特错(m个信息位，r个校验位)对2m个合法码字中任何一个，有n个与其距离为1的非法码字，因此有：(n+1)2m

3、2n利用n=m+r，得到(m+r+1)2r给定m，利用该式可以得出校正单比特误码的校验位数目的下界海明码有效信息位数m与校验位数r的关系海明码基本思想将r位校验位分成r组，采用奇偶校验的方式产生r位检错信息，这些检错信息能指示出传输信息中哪一位发生了错误有效信息位数m校验位数r1~435~11412~26527~57658~1207海明码的生成确定所需最少的校验位数码位从右边/左边开始编号，从“1”开始位号为2的幂的位是校验位，编号为r1,r2…r2n-1;其余位是信息位，编号为d1,d2…dn每个校验位使得包括自己在内的一些位的“1”的个数为奇数/偶数（奇偶

4、校验）为看清信息位k对哪些校验位有影响，将k写成2的幂的和例：11=1+2+8海明码海明码例：对7位信息1001000进行偶校验海明编码。7位信息需要4位校验，编号为r1,r2,r4,r8B1B2B3B4B5B6B7B8B9B10B11海明码：r1r2d1r4d2d3d4r8d5d6d700110010000r1=d1+d2+d4+d5+d7r2=d1+d3+d4+d6+d7r4=d2+d3+d4r8=d5+d6+d7s1=r1+d1+d2+d4+d5+d7s2=r2+d1+d3+d4+d6+d7s3=r4+d2+d3+d4s4=r8+d5+d6+d712345

5、678910111111122222444888海明监督关系式海明码工作过程1每个码字到来后，接收方计算海明监督关系式是否全部等于0，如果是，则证明接收数据无误；否，则证明数据出错出错的位数可以根据海明监督关系式推出，由sn…s2s1组成的值等于出错的位数海明码海明码工作过程2每个码字到来前，接收方计数器清零接收方检查每个校验位k(k=1,2,4…)的奇偶值是否正确若第k位奇偶值不对，计数器加k所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错若校验位1、2、8出错，则第11位变反海明码海明码例.接收码字为：0011101(7/4码，从

6、左至右编码)，求：信息码解：1)由海明码的监督关系式计算得S3S2S1=1012)由监督关系式推出：出错位是第5位3)对第5位取反，得正确码字：00110014)把第1、2、4位的冗余码删除，得发送端的信息码：1001海明码使用海明码纠正突发错误可采用k个码字（n=m+r）组成kn矩阵，按列发送，接收方恢复成kn矩阵kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错123456789101111111222224448882流量控制数据链路层上控制的是网络中相邻结点之间的数据传输局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域

7、网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简单模型局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动数据链路层的简单模型完全理想化的数据传输所基于的两个假定假定1：链路是理想的传输信道，所传送的任何数据既不会出差错

8、也不会丢失。假定2：不管