第3章 差错控制技术.ppt

第第3 3章章 差错控制技术差错控制技术3.1 差错控制的基本概念差错控制的基本概念3.2 流量控制方法流量控制方法3.3 常用差错控制编码方法常用差错控制编码方法3.4 常用差错控制方法常用差错控制方法3.5差错控制的性能估算和应用差错控制的性能估算和应用CH3 差错控制技术差错控制技术 必要性必要性：数据通信要求信息传输过程具有高度的可靠性数据通信要求信息传输过程具有高度的可靠性即误码率足够低；即误码率足够低；信号在传输过程中由于传输损耗（噪声，衰损，信号在传输过程中由于传输损耗（噪声，衰损，失真）不可避免要产生一些差错即出现误码。失真）不可避免要产生一些差错即出现误码。大体上分为：大体上分为：随机差错随机差错随机噪声随机噪声 突发差错突发差错脉冲噪声脉冲噪声CH3 差错控制技术差错控制技术 解决的办法解决的办法：一是改善传输信道的电气特性（先进的物一是改善传输信道的电气特性（先进的物理设备要付出成本）提高传输可靠性；理设备要付出成本）提高传输可靠性；另一种办法在相应的物理设备条件下采用另一种办法在相应的物理设备条件下采用计算机技术进行差错编码和控制，自动检计算机技术进行差错编码和控制，自动检测错误并在可能情况下纠正错误，这就是测错误并在可能情况下纠正错误，这就是所谓的所谓的差错控制技术。差错控制技术。3.1 差错控制的基本概念差错控制的基本概念3.1.1 差错控制的基本概念差错控制的基本概念3.1.2 差错控制编码的特性和能力差错控制编码的特性和能力 3.1.1差错控制的基本概念差错控制的基本概念 所谓差错即为误码；所谓差错即为误码；差错控制的核心是差错控制的核心是抗干扰编码，简称抗干扰编码，简称差错编码差错编码（属于二次（属于二次编码即信道编码），它的编码即信道编码），它的基本思想基本思想是通是通过对信息序列作某种变换，使原来彼此过对信息序列作某种变换，使原来彼此独立、互不相关的信息码元产生某种规独立、互不相关的信息码元产生某种规律性（相关性），从而在接收端根据这律性（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序种规律性来检查，进而纠正传输信号序列中的差错列中的差错。变换的方法不同就构成了。变换的方法不同就构成了不同的编码。不同的编码。3.1.1差错控制的基本概念差错控制的基本概念1.1.信息码和监督码信息码和监督码2.2.差错控制的基本特点差错控制的基本特点3.3.差错控制的理论基础差错控制的理论基础4.4.差错控制编码的基本原理差错控制编码的基本原理5.5.差错控制实例差错控制实例6.6.编码效率编码效率7.7.差错编码的分类差错编码的分类 1.1.信息码和监督码信息码和监督码 信息码（元）信息码（元）：发送用户端欲发送的信：发送用户端欲发送的信息序列，本来彼此独立，互不相关；由息序列，本来彼此独立，互不相关；由用户控制，最终也交给接收用户。用户控制，最终也交给接收用户。监督码（元）监督码（元）:为了使信息码元产生某为了使信息码元产生某种规律性，可按照某种规则在用户信息种规律性，可按照某种规则在用户信息序列中插入一定数量的新码元，这种新序列中插入一定数量的新码元，这种新码元叫监督码（元）。码元叫监督码（元）。监督码元不受用户控制，最终也不交给接监督码元不受用户控制，最终也不交给接受用户。受用户。9 插入监督码元的目的是使原来彼此独插入监督码元的目的是使原来彼此独立、互不相关的信息码元产生某种规立、互不相关的信息码元产生某种规律性（相关性）从而使接收端能够根律性（相关性）从而使接收端能够根据这种规律性来检测传输过程是否有据这种规律性来检测传输过程是否有误。误。2.差错控制的基本特点差错控制的基本特点 引入差错编码控制后，实际传输的引入差错编码控制后，实际传输的 信息序列信息序列=（信息码元（信息码元+监督码元）监督码元），称为，称为码组。码组。在信道容量既定的情况下，信息传输速在信道容量既定的情况下，信息传输速率有所降低，但信息传输的可靠性有所提率有所降低，但信息传输的可靠性有所提高，既差错控制编码用高，既差错控制编码用降低降低通信系统通信系统信息信息传输的有效性传输的有效性的代价来的代价来提高信息传输的可提高信息传输的可靠性靠性。Why?同样的信息量要用更多的比特位！同样的信息量要用更多的比特位！3.差错控制的理论基础差错控制的理论基础香农信道编码定理香农信道编码定理 香农信道编码定理：每个信道都具有确每个信道都具有确定的信道容量定的信道容量C，只要信息传输速率：，只要信息传输速率：Rb（bps）=C则理论上就一定存在一种编则理论上就一定存在一种编码方式，使其译码差错概率码方式，使其译码差错概率Pe满足：满足：Pe=A e-n E(Rb)式中式中香农另一个定理:通信系统极限传输速率通信系统极限传输速率NSBC1log2n n码字长度（码长）码字长度（码长）E E（R Rb b）误差指数（当误差指数（当R Rb b=C00）A A正系数正系数P Pe eN Ne eN N误码率是指二进制码元在数据误码率是指二进制码元在数据传输系统中被传错的概率传输系统中被传错的概率 ；N N为传输的为传输的二进制码元总数，二进制码元总数，N Ne e为被传错的码元数。为被传错的码元数。香农信道编码定理香农信道编码定理E E（R Rb b）与）与R Rb b的关系如图所示：的关系如图所示：C 使使E(Rb)或或 n 使使e-nE(Rb)可见要使可见要使Pe满足要求：满足要求：一是增加信道容量一是增加信道容量C C，从而使，从而使E E（Rb ）增加（通信硬件系统设计人员通常采增加（通信硬件系统设计人员通常采用的方法）；用的方法）；另一种方法是只要另一种方法是只要R Rb b=C=连环码。连环码。差错编码的分类差错编码的分类(4)(4)按照纠正错误的类型可分为按照纠正错误的类型可分为纠正随机错纠正随机错误的码误的码和和纠正突发错误的码纠正突发错误的码。(5)(5)按照每个码元取值来分按照每个码元取值来分二进制码二进制码和和多进多进制码制码。3.1.2 差错控制编码的特性和能力差错控制编码的特性和能力1.1.海明（海明（hamminghamming）距离）距离2.2.最小距离最小距离3.3.海明距离（码距）海明距离（码距）4.4.最小距离与抗干扰能力的关系最小距离与抗干扰能力的关系1.1.海明（海明（hamminghamming）距离）距离 1.1.海明（海明（hamming）距离：）距离：指两个不同的指两个不同的码组其对应码位（二进制位）的码元不同码组其对应码位（二进制位）的码元不同的个数，简称的个数，简称码距码距；用用d表示：表示：nikijiaad1)(式中式中表示模表示模2 2加（异或）加（异或）n n表示码组长表示码组长度度a akiki和和a ajiji表示第表示第k k个码组和第个码组和第j j个码组的第个码组的第i i位码元位码元 例：（10111011）和（）和（01000100）两码组间距离：）两码组间距离：d=d=（1011010010110100）=4 =4 （0000）和（）和（0000）两码组间码距：）两码组间码距：d=0 d=0 （0101）和（）和（1111）两码组间距离：）两码组间距离：d=1 d=1 （001001）和（）和（100100）两码组间距离：）两码组间距离：d=2d=2（101101）和（）和（010010）两码组间距离：）两码组间距离：d=3d=3海明（海明（hamminghamming）距离实例）距离实例 2.2.最小距离：最小距离：一个一个中，任何两个码中，任何两个码组间海明距离组间海明距离(即码距即码距)的最小值称为码组集的最小值称为码组集合的最小距离。用合的最小距离。用d0d0或或d dminmin表示表示:表示)(min/01minnikijiaadd式中式中表示模表示模2 2加加 n n表示码组长度表示码组长度a akiki和和a ajiji表示第表示第k k个码组和第个码组和第j j个码组的第个码组的第i i位位码元码元 minmin表示最小值表示最小值2.2.最小距离最小距离 举例：码组集合码组集合（000000）（）（001001）（）（010010）（）（011011）（100100）（）（101101）（）（110110）（）（111111）d0=1 d0=1 没有检错能力。没有检错能力。码组集合码组集合（000000）（）（011011）（）（101101）（110110）d0=2 d0=2 能检测出能检测出1 1位码位出错。位码位出错。码组集合码组集合（000000）（）（111111）d0=3 d0=3 能能检测出检测出2 2位出错并能纠正位出错并能纠正1 1位错误。位错误。最小距离实例最小距离实例n如果如果8 8种码组都作为许用码组，任两个种码组都作为许用码组，任两个码距间的最小距离为码距间的最小距离为1 1，记，记dmin=1;=1;n如果如果4 4种码组种码组(000 011 101 110)(000 011 101 110)作为许作为许用码组，任两个码距间的最小距离为用码组，任两个码距间的最小距离为2 2，记记dmin=2;=2;n如果如果2 2种码组作为许用码组种码组作为许用码组(000 111)(000 111)，任两个码距间的最小距离为任两个码距间的最小距离为3 3，记，记dmin =3;=3;n所以码组集合中最小距离越大，其抗干扰能力（包括检错和纠错能力）越强。3.3.海明距离（码距）海明距离（码距）n3.3.海明距离（码距）海明距离（码距）就是从一个顶点移动就是从一个顶点移动到另一个顶点所经历立方体的最少边数；到另一个顶点所经历立方体的最少边数；n则所谓则所谓最小距离最小距离就是立方体中从一个顶点就是立方体中从一个顶点移到另一个顶点所经历的最少边数移到另一个顶点所经历的最少边数 。4.4.最小距离与抗干扰能力的关系最小距离与抗干扰能力的关系 定理定理3.13.1若一种码的最小距离为若一种码的最小距离为d0d0，则它能，则它能检查传输错误个数（检错能力）检查传输错误个数（检错能力）e e应满足：应满足：d0=e+1d0=e+1 定理定理3.23.2若一种码的最小距离为若一种码的最小距离为d0d0，则它能，则它能纠正传输错误个数（纠错能力）纠正传输错误个数（纠错能力）t t应满足：应满足：d0=2t+1d0=2t+1 定理定理3.33.3若一种码的最小距离为若一种码的最小距离为d0d0，则它的，则它的检错能力和纠错能力应满足：检错能力和纠错能力应满足：d0=e+t+1 d0=e+t+1 （e=te=t）例例3.1 3.1 求码集合求码集合(000),(011),(101),(110)(000),(011),(101),(110)和和(000),(111)(000),(111)最小距离最小距离d d0 0及纠（检）错的及纠（检）错的能力。能力。实例（实例（P53）解：最小距离实例实例 检错和纠错能力检错和纠错能力第一组：第一组：d0=2，e=d0 1=1，可检测出一个错，可检测出一个错，（定理（定理1）第二组：第二组：d0=3e=d0 1=2，可检测出二个错，（定理可检测出二个错，（定理1）t=(d0-1)/2=1，可纠正一个错，（定理可纠正一个错，（定理2）e+t=d0-1=2 ，令（，令（t=e）e=1，t=1，纠错、检错各纠错、检错各1，（定理，（定理3）3.2 3.2 流量控制流量控制 流量控制必要性：流量控制必要性：任何设备都有一个处理数据的速率任何设备都有一个处理数据的速率限制，并且存储输入数据的存储容器容量也是有限制，并且存储输入数据的存储容器容量也是有限的。接收设备必须在达到这些限制之前通知发限的。接收设备必须在达到这些限制之前通知发送设备并且请求发送设备发送较少的数据帧或是送设备并且请求发送设备发送较少的数据帧或是暂停一会。暂停一会。水池水池 -打印机打印机 -电话电话 缓冲区缓冲区：接收方在使用