《数据的检错与纠错》PPT课件.ppt

电力系统通信与网络技术,第三讲数据的检错与纠错,2.3数据的检错与纠错,2.3.1差错控制编码的基本概念2.3.2差错控制方式2.3.3纠错检错码的基本原理2.3.4常用差错控制编码方法2.3.5差错控制的应用,2.3.1差错控制编码的基本概念,传输差错：简称“差错”，在数据通信中,由于来自信道中的各种干扰，使数据在传输与接收的过程中可能发生差错。即接收端接收的数据与发送端出现不一致的现象。差错控制技术的核心是采用高效的纠错检错编码方法。,差错控制编码的基本思想（Shannon第二定律）：在数字信号序列中加入一些冗余码元，这些冗余码元不含有通信信息，但与信号序列中的信息码元有着某种制约关系，这种关系在一定程度上可以帮助人们发现或纠正在信息序列中出现的错误也就是误码，从而起到降低误码率的作用差错控制编码：寻找合适的方法将信息码元和冗余码元编排在一起的过程。,两种通信系统干扰示意图,香农第二定律,对于一个给定的有扰信道，若该信道容量为C，则只要信道中的信息传输速率R小于C，就一定存在一种编码方式，使编码后的误码率随着码长n的增加按指数下降到任意小的值。或者说只要Rt)满足条件3可以同时纠正t个错，检出e个错。,例题,已知6个码组为：0000000，0001011，0010101，0011110，0100110，101101。求其间的最小码距dmin和能检出和纠正的错码数t。dmin=3纠错：要求最小码距d02t+1则t=1,结论,要提高纠错检错能力，必须增大最小码距。用码率R=k/n表征编码效率。最小码距越大，编码效率越低。编码理论要解决的问题就是找出许用码的集合，既要纠错能力强，又要编码效率高。,2.3.3常用差错控制编码方法,奇偶校验码恒比码汉明码循环码,奇偶校验码,奇偶校验码又称奇偶监督码，是最简单、最常用的检错码。有奇数监督码和偶数监督码两种。特点：奇偶校验编码只需在信息码后加一位校验位（又称监督位），使得码组中“1”的个数为奇数或偶数即可。奇偶监督码能够检测奇数个错码。偶校验码：监督码元a0奇校验码：监督码元a0,垂直监督码和水平监督码,垂直奇偶监督码,水平奇偶监督码,水平偶校验码表,按列发送,二维奇偶监督码,二维奇偶监督码,能够检测出全部奇数个错码和大部分偶数个错码。但无法检出在水平垂直方向上都成偶数的那些错码，例如构成矩形的四个顶点位置上的错码就无法检出。,按列发送,恒比码,恒比码又称定比码。在恒比码中，每个码组中“1”的数目和“0”的数目保持恒定的比例。故在收端只需检测接收码组中“1”的个数是否正确。其纠错能力比奇偶监督码强。,汉明码,线性码是一种将信息位和监督位由一些线性代数方程联系在一起的编码。线性分组码：也称为（n，k）线性码，可用线性方程组表述规律性的分组码。汉明码是线性码的一种。设总码长为n，信息位为k，监督位数为r=n-k；若希望用r个监督位构造出r个监督关系式来指示一位错码的n个可能的位置，则要求：2r-1n或2rk+r+1,例题,对于（n,k）汉明码，k=6，若要求能纠正一位错误，则所需监督位r至少多少位？要求2rk+r+1可得r=4,循环码(CRC码),如果一个码组的每一次循环移位是另一码组，这种码组叫做循环码。循环码可以用线性方程确定。,循环码的生成,CRC码在发送端编码和接收端校验时，均可用事先约定的生成多项式G(X)来得到。K位要发送的信息码对应一个k-1次多项式K（X），r位冗余位对应r-1次多项式R（X）,由k位信息码后面加上r位冗余位组成的n=k+r位码字则对应于一个n-1次多项式：T（X）=XrK（X）+R（X）。,举例,信息位：1011001K（X）=X6+X4+X3+1冗余位：1010R（X）=X3+X码字：10110011010T（X）=X4K（X）+R（X）=X10+X8+X7+X4+X3+X以上多项式中的“+”都是模2加。,由于R（X）是XrK（X）除以G（X）的余式，所以，XrK（X）=G（X）Q（X）+R（X）其中，Q（X）为商式。根据模2运算规则R（X）+R（X）=0的特点，将上式改写为：,XrK（X）+R（X）/G（X）=Q（X）即T（X）/G（X）=Q（X）,检错方法,信道上发送的码字多项式T（X）=XrK（X）+R（X），若传输过程无错，那么，接收到的码字多项式能被G（X）整除。（即余式为零）。除法是模2除法。,例题,在数据传输过程中，若收到发送方送来的信息为10110011010，生成多项式为G(X)=X4+X3+1,接受方收到的数据是否正确？T（X）=X10+X8+X7+X4+X3+XT（X）/G（X）=X6+X5+X3+X可以整除，故接收正确,例题,在数据传输过程中，若信息码的信息为1011001，生成多项式为G(X)=X4+X3+1,求T（X）,常用CRC码,目前广泛使用（推荐）的(CyclicRedundancyCheck)生成多项式有4种：（一）CRC12=X12+X11+X3+X2+X+1（二）CRC16=X16+X15+X2+1（三）CRC16=X16+X12+X5+1（四）CRC32=X32+X26+X23+X22+X16+X10+X8+X7+X5+X4+X2+X+1,2.3.4差错控制的应用,差错控制技术的应用，要视具体情况而定。当出现少量错码在接收端能够纠正时，可采用前向纠错法（FEC）纠正，当错码较多超过纠正能力，但可以检测时，就可以用反向纠错法。通常应对整个系统全面考虑后才能决定采用哪种技术。,编码所研究的问题,根据实际通信系统对纠错能力的要求，寻找合适的码型（通常是一种长码型）。要求该码型可以在数学上证明具有满足要求的纠错能力，并具有数学结构，且能够根据此结构用一些设备实现编码和译码。寻找实用的编码方法，尽量提高编码效率。寻找实用的译码方法，尽量降低译码的复杂性。,