高等学校21世纪教材：《计算机网络》第2章 (2-3) 通信子网的基本技术2

第2章通信子网的基本技术(第二讲) 2.3差错控制技术 2.3.1差错的检测与校正 概括地说,传输中的差错都是由于噪声所引起的。噪声 有两大类,一类是信道所固有的,持续存在的随机热噪 声;另一类是由于外界特定的短暂原因所造成的冲击噪 声 衡量一个信道质量的重要参数是误码率: 发生差错的码元数 Pe 接收的总码元数 前页后页退出

前页 后页 退出 第2章 通信子网的基本技术 （第二讲） 2.3 差错控制技术 2.3.1差错的检测与校正 概括地说，传输中的差错都是由于噪声所引起的。噪声 有两大类，一类是信道所固有的，持续存在的随机热噪 声；另一类是由于外界特定的短暂原因所造成的冲击噪 声。 衡量一个信道质量的重要参数是误码率： Pe = 发生差错的码元数 接收的总码元数

差错控制编码又可分为检错码和纠错码,前者是指能自动发 现差错的编码,后者是指不仅能发现差错而且能自动纠正差 错的编码。衡量编码性能好坏的一个重要参数是编码效率R, 它是码字中信息位所占的比例。若码字中信息位为k位,编码 时外加冗余位为r位,则编码后得到的码字长为n=k+r位。 我们有 k k R ktr 显然,编码效率越高,即R越大,则信道中用来传送信息码元 的有效利用率就越高 下面我们各举一种检错码和纠错码的例子 定比码 定比码:是指每个码字中均含有相同数目的“1(码字长 定,“1”的数目一定后,所含“03的数目也就必然相同), 它是一种检错码 前页后页退出

前页 后页 退出 差错控制编码又可分为检错码和纠错码，前者是指能自动发 现差错的编码，后者是指不仅能发现差错而且能自动纠正差 错的编码。衡量编码性能好坏的一个重要参数是编码效率R， 它是码字中信息位所占的比例。若码字中信息位为k位，编码 时外加冗余位为r位，则编码后得到的码字长为n = k + r位。 我们有： k r k n k R + = = 显然，编码效率越高，即R越大，则信道中用来传送信息码元 的有效利用率就越高。 下面我们各举一种检错码和纠错码的例子： 一、定比码 定比码：是指每个码字中均含有相同数目的“1”（码字长一 定，“1”的数目一定后，所含“0”的数目也就必然相同）， 它是一种检错码

正反码 正反码是一种简单的纠错码,其中冗余位的个数与信息位个 数相同,而且两者或者完全相同或者完全相反,由信息位中 “1”的个数来决定。 2.3.2奇偶校验码 奇偶校验码:是通过增加冗余位来使得码字中“1的个数 保持奇或偶数的编码方法,是一种检错码。在使用时又可 分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等 几种。 前页后页退出

前页 后页 退出 二、正反码 正反码是一种简单的纠错码，其中冗余位的个数与信息位个 数相同，而且两者或者完全相同或者完全相反，由信息位中 “1”的个数来决定。 2.3.2 奇偶校验码 奇偶校验码：是通过增加冗余位来使得码字中“1”的个数 保持奇或偶数的编码方法，是一种检错码。在使用时又可 分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等 几种

垂直奇偶校验:是将整个发送的信息块分为定长p位的若干段 (比如说q段),每段后面按“1的个数为奇或偶数的规律加 上一位奇偶位,如下图所示 发送顺序 信息位 P2 F←冗余位 若用偶校验r;=I1I21⊕Ii 若用奇校验r;=I1;⊕I2;,,In1 这种方法的编码效率为:w=-b 前页后页退出

前页 后页 退出 垂直奇偶校验:是将整个发送的信息块分为定长p位的若干段 （比如说q段），每段后面按“1”的个数为奇或偶数的规律加 上一位奇偶位，如下图所示 ： 若用偶校验 ri = I1i⊕I2i⊕…⊕Ipi 若用奇校验 ri = I1i⊕I2i⊕…⊕Ipi⊕1 这种方法的编码效率为： +1 = p p R

水平奇偶校验:它是对各个信息段的相应位横向进行编码, 产生一个奇偶校验冗余位,如下图所示, 发送顺序 EI 信息位几余位 这种方法的编码效率为: d+I 前页后页退出

前页 后页 退出 水平奇偶校验：它是对各个信息段的相应位横向进行编码， 产生一个奇偶校验冗余位，如下图所示， 这种方法的编码效率为： +1 = q q R

同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇 偶校验,如下图所示。 II 12 发送顺序 +L.2 P+1,g 若都采用偶校验,则: r1a+1=11I12⊕…I p I,⊕I④..I 2 p q r ptI, q p, q 这种方法的编码效率为:R=_q (P+1)(q+1) 前页后页退出

前页 后页 退出 同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇 偶校验，如下图所示。 若都采用偶校验，则： r i,q+1 = I i1⊕I i2⊕…⊕I iq （i=1,2,…,p） r p+1,j = I 1j⊕I 2j⊕…⊕I pj （j=1,2,…,q） r p+1,q+1=rp+1,1⊕r p+1,2⊕…⊕r p+1,q=r1,q+1⊕r 2,q+1⊕…⊕r p,q+1 这种方法的编码效率为： ( +1)( +1) = p q pq R

23.3海明码 海明码是由R. Hamming在1950年首次提出的,它也是一种可 以纠正一位差错的编码,但它的编码效率要比正反码高得多 (当信息位足够长时)。 海明码只能纠正一位错,若用在纠正传输中出现突发性差 错时可以采用下述方法将连续P个码字排成一个矩阵,每 行一个码字。如下图中的例子,发送顺序为 011001100001..1110100011。如果发生突发长度≤P的突 发错误,那么在P个码字中最多每个码字有一位有差错, 正好由海明码能纠正 前页后页退出

前页 后页 退出 2.3.3 海明码 海明码是由R. Hamming在1950年首次提出的，它也是一种可 以纠正一位差错的编码，但它的编码效率要比正反码高得多 （当信息位足够长时）。 海明码只能纠正一位错，若用在纠正传输中出现突发性差 错时可以采用下述方法:将连续P个码字排成一个矩阵，每 行一个码字。如下图中的例子，发送顺序为 011001100001…1110100011。如果发生突发长度≤P的突 发错误，那么在P个码字中最多每个码字有一位有差错， 正好由海明码能纠正

信总位冗余位 010010 发1011001 送0100110LP个码字组成矩阵 0100110 每行一个码字 1101010 0110011 前页后页退出

前页 后页 退出

2.3.3循环冗余码 CRC码又称为多项式码。这是因为任何一个由二进制数 位串组成的代码都可以和一个只含有0和1两个系数的多 项式建立一一对应的关系。例如,代码1011011对应的多 项式为x6+x4+x3+x+1,而多项式x5+x4+x2+x对应的代码为 l10110。并且,CRC码在发送端编码和接收端校验时都 可以利用一事先约定的生成多项式G(x)来进行。k位要 发送的信息位可对应于一个(k-1)次多项式K(x),r位 冗余位对应于一个(r-1)次多项式R(x)。由k位信息位 后面加上r位冗余位组成的n=k+r位码字则对应于一个(n 1)次多项式T(x)=xK(x)+R(x) 前页后页退出

前页 后页 退出 2.3.3 循环冗余码 CRC码又称为多项式码。这是因为任何一个由二进制数 位串组成的代码都可以和一个只含有0和1两个系数的多 项式建立一一对应的关系。例如，代码1011011对应的多 项式为x 6+x4+x3+x+1，而多项式x 5+x4+x2+x对应的代码为 110110。并且，CRC码在发送端编码和接收端校验时都 可以利用一事先约定的生成多项式G（x）来进行。k位要 发送的信息位可对应于一个（k-1）次多项式K（x），r位 冗余位对应于一个（r-1）次多项式R（x）。由k位信息位 后面加上r位冗余位组成的n=k+r位码字则对应于一个（n- 1）次多项式T（x）=xr • K(x)+R(x)

按上述方法产生的循环码有下述性质 【性质1】若G(x)含有(x+1)的因子,则能检测出所有 奇数位错。 【性质2】若G(x)中不含有x的因子,或者换句话说,G(x) 中含有常数项1,那未能检测出所有突发长度<r的突发错 【性质3】若G(x)中不含有x的因子,而且对任何0<e≤n1 的e,除不尽xe+1,则能检测出所有的双错。 【性质4】若G(x)中不含有x的因子,则对突发长度为r+ 的突发错误的漏检率为2r1 【性质5】若G(x)中不含有x的因子,则对突发长度b大于 r+1的突发错误的漏检率为2r 前页后页退出

前页 后页 退出 按上述方法产生的循环码有下述性质。 【性质 1】 若G（x）含有（x+1）的因子，则能检测出所有 奇数位错。 【性质 2】 若G（x）中不含有x的因子，或者换句话说，G（x） 中含有常数项1，那末能检测出所有突发长度≤r的突发错。 【性质 3】 若G（x）中不含有x的因子，而且对任何0< e ≤ n–1 的e，除不尽x e +1，则能检测出所有的双错。 【性质 4】 若G（x）中不含有x的因子，则对突发长度为r + 1 的突发错误的漏检率为2 -(r-1)。 【性质 5】 若G（x）中不含有x的因子，则对突发长度b大于 r+1的突发错误的漏检率为2 -r