海明码和滑动窗口机制.ppt

重传时间 重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。 为方便起见，我们设重传时间为 tout = tp + tpr+ ta + tp + tpr 设上式右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为两倍的传播时延，即tout = 2tp 停止等待协议 ARQ 的优缺点 优点：比较简单 。 缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。 为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。 海明码 流量控制 非受限协议 停-等协议 第8讲 海明码和停等协议 码字（codeword）：一个帧包括m个数据位，r个校验位，n = m + r，则此n比特单元称为n位码字。 海明距离（Hamming distance）：两个码字之间不同的比特位数目。 例：0000000000 与0000011111的海明距离为5 1 海明码* 如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字； 为了检查出d个错（单比特错），需要使用海明距离为 d + 1 的编码； 为了纠正d个错，需要使用海明距离为 2d + 1 的编码； 1 海明码 1 海明码 设计纠错码 要求：m个信息位，r个校验位，纠正单比特错； 对2m个有效信息中任何一个，有n个与其距离为1的无效码字，因此有：(n + 1) 2m ? 2n 利用 n = m + r，得到 (m + r + 1) ? 2r 给定m，利用该式可以得出校正单比特误码的校验位数目的下界 1 海明码 码位从右边开始编号，从“1”开始； 位号为2的幂的位是校验位，其余是信息位； 每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。 为看清数据位k对哪些校验位有影响，将k写成2的幂的和。 例：11 = 1 + 2 + 8 1 海明码 工作过程 每个码字到来前，接收方计数器清零； 接收方检查每个校验位k (k = 1, 2, 4 …)的奇偶值是否正确； 若第 k 位奇偶值不对，计数器加 k； 所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。 若校验位1、2、8出错，则第11位变反。 使用海明码纠正突发错误 可采用k个码字（n = m + r）组成 k ? n 矩阵，按列发送，接收方恢复成 k ? n 矩阵 kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。 1 海明码 数据： 1 0 1 1 0 1 0 d7 d6 d5 d4 d3 d2 d1 位置： 11 10 9 8 7 6 5 4 3 2 1 海明码： 1 0 1 0 1 0 1 0 0 0 0 d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1 1 海明码 11 10 9 8 7 6 5 4 3 2 1海明码： 1 0 1 0 1 0 1 0 0 0 0 d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1 接收方接收到数据后，按照同样的规则进行奇偶校验 得出新的r1，r2，r4，r8。 如果传输正确，对于偶校验来说，这4个新值都应为0。 假设第4位发生了错误，即接收到的数据为10101011000，那么接收方计算的结果是：r1=0，r2=0，r4=1，r8=0，4位组合起来为0100，即表示第4位出现了错误，然后把1取反，从而纠正了该错误。 1 海明码 1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 2 2 2 2 2 4 4 4 8 8 8