数据通讯与计算机网络讲义 10章.ppt

使用汉明编码纠正多位差错 循环码是线性分组码，并具有性质：在一个循环码字集中，任何码字的循环移位的结果是该码字集中的另一个码字。 10.4 循环码 示例： CRC码字集 C(7, 4) ( 3个“1” ,4个“1” ,全“0” , 全“1” ) CRC编码与解码 CRC编码运算 CRC解码运算 CRC除法运算的硬件构成 1/0 CRC编码器的除法运算过程 CRC编码器的移位寄存器实现 若除数某位为0，则无该位对应的异或门(及异或门上端红色连线)。 polynomials（多项式） 多项式加法和减法 多项式乘法和除法 (x5+x3 ) + ( x6+x5) = x6+x3 加法=减法 10011 左移 3 bit: 10011 右移 3 bit: 10 (x4+x+1)x3 = x7+x4+x3 (x4+x+1)/x3 = x CRC的多项式除法 In received CRC code, If s(x) ≠ 0, error； If s(x) = 0,  either no error or error, but failed to detect. CRC编码分析 数据字 d(x) CRC码字 c(x) 除式 g(x) 编码余数 r(x) 差错模式 e(x) 解码余数 s(x) 能被g(x)整除的e(x)所对应的差错模式被漏检。 c(x)/g(x) = [xn-kd(x)+r(x)+e(x)] / g(x) = [xn-kd(x)]/g(x) + r(x)/g(x)+ e(x)/g(x) = [q(x)+ r(x)/g(x)] + r(x)/g(x)+e(x)/g(x) = q(x) + e(x)/g(x) 设计g(x)，使尽可能多的e(x)不能被g(x)整除。 数据字 d(x) CRC码字 c(x) 除式 g(x) 编码余数 r(x) 差错模式 e(x) 解码余数 s(x) 如果g(x) 多于1项，且x0系数为1，则所有的单比特差错均能被检测出来。 1. 单比特差错 讨论下述g(x)对单比特差错的检测能力。 a. x + 1 b. x3 c. 1 a. 单比特差错模式为e(x)= xi。任何xi不能被x+1整除，所以x+1可检测任何单比特差错。 b. 如果“i”大于或等于, xi 能被x3整除。所有在位置0～2的单比特差错能被检测出来。 c. 任何xi 能被1整除。该g(x)不能作为除数。 解: 例 10.15 2. 两个单独比特差错 如果g(x)不能整除xt + 1 (t∈1~n –1)，则任何两比特差错均能被检测。 差错模式e(x)=xj +xi=xi(xj-i+1)=xi(xt+1), (t∈1~n–1) 讨论下述g(x)对两个单独比特差错的检测能力。 a. x + 1 b. x4 + 1 c. x7 + x6 + 1 d. x15 + x14 + 1 a. 任何相邻的两个比特差错e(x)=xj+xj-1均能被x+1整除，故该类差错不能被该g(x)检测出来。 b. 任何相邻4个比特位置的两比特差错不能被该g(x)检测。 c. 类同于d。 d. 该除数g(x)的最高次项为x15。若e(x)=xt +1的最高次 t =15，则e(x)不能被该g(x)整除。一个码字中的两个差错比特只要间隔不大于15位即能被该g(x)检测出来。 例 10.16 解： 含因子x +1的g(x)能够检测所有奇数位差错。 3. 奇数个比特差错 分析：(x+1)与任何多项式的乘积为偶数项多项式。 (x+1)(x3+x+1)=x4+x3+x2+x+x+1=x4+x3+x2+1 (x+1)(x3+x)=x4+x3+x2+x (x+1)(x2+x)=x3+x2+x2+x=x3+x K项多项式被x+1 乘后为2k项（偶数项）。若其中有j对同类项，合并后减少2j项（偶数）。 所有差错长度L≤r的突发差错能被检测。 所有差错长度L = r + 1的突发差错能以概率1–(1/2)r–1被检