数据的检错与纠错.ppt

1、电力系统通信与网络技术,第三讲 数据的检错与纠错,2.3 数据的检错与纠错,2.3.1 差错控制编码的基本概念 2.3.2 差错控制方式 2.3.3 纠错检错码的基本原理 2.3.4 常用差错控制编码方法 2.3.5 差错控制的应用,2.3.1 差错控制编码的基本概念,传输差错：简称“差错”，在数据通信中,由于来自信道中的各种干扰，使数据在传输与接收的过程中可能发生差错。即接收端接收的数据与发送端出现不一致的现象。 差错控制技术的核心是采用高效的纠错检错编码方法。,差错控制编码的基本思想（Shannon第二定律）： 在数字信号序列中加入一些冗余码元，这些冗余码元不含有通信信息，但与信号序列中的

2、信息码元有着某种制约关系，这种关系在一定程度上可以帮助人们发现或纠正在信息序列中出现的错误也就是误码，从而起到降低误码率的作用 差错控制编码：寻找合适的方法将信息码元和冗余码元编排在一起的过程。,两种通信系统干扰示意图,香农第二定律,对于一个给定的有扰信道，若该信道容量为C，则只要信道中的信息传输速率R小于C，就一定存在一种编码方式，使编码后的误码率随着码长n的增加按指数下降到任意小的值。或者说只要RC，就存在传输速率为R的纠错码。,2.3.2 差错控制方式,前向纠错（FEC） 检错重发（ARQ） 混合纠错（HEC）,前向纠错（FEC）,收、发信之间只有一条单向通道（正向信道）。 实现纠错的唯

3、一办法是传送纠错码。 可以在收端及时纠正差错，它要求的监督码多且复杂，效率低，常用于误码较少的单向信道。,检错重发（ARQ）,发送端经编码后，发出能够检错的码；接收端收到后，在通过反向信道反馈给发送端一个应答信号；发送端收到应答信号后，进行分析，若是接收端认为有错，发送端就把存储在缓冲存储器中的原有码组复本读出，重新传输；如此重复，直至接收端接收到正确的信息为止。,检错重发的三种工作方式,检错重发三种工作方式的比较,停发等侯重发： 原理简单，发送过程是间歇式的，数据传输效率不高，仍在计算机通信中应用。 返回重发： 传输效率比停发等候系统有很大改进，在很多数据传输系统中得到应用。 选择重发： 传

4、输效率最高，但要求较为复杂的控制，在收、发两端都要求有数据缓存器，价格也最贵。,混合纠错,将前向纠错和检错重发方式的结合。当在该码的纠错能力范围内时，自动纠正；当错误过多，超出其纠错能力时，反馈重发。,2.3.2 纠错检错码的基本原理,两种错误形式 冗余度 分组码,两种错误形式,随机错误： 由随机噪声引起的码元错误。 突发错误： 由突发噪声引起的码元错误，如闪电、电器开关的瞬态、磁带缺陷等。,冗余度,冗余码：监督码元或校验码元 冗余度：监督码元的位数 在信息码序列中加入监督码元才能完成检错和纠错功能，其前提是监督码元要与信息码之间有一种特殊的关系。 监督码元越多，冗余度越大，纠错能力也越强，但

5、效率却低。,举例,例如：3位二进制数构成的码组集合为23=8种不同的码组，即，000，001，010，011，100，101，110，111，下面分三种情况来讨论： 若8组都作为有用的码组，如表示天气， 000（晴），001（云），010（阴），011（雨），100（雪），101（霜），110（雾），111（雹），那么其中任一码组出错都会变成另一码组，接收端将无法识别哪一组出错。,举例（续1）,若只取其中4个码组作为许用码组： 000（晴）、011（云）、101（阴）、110（雨） 当000中错一位，变为100、010或001，而这三种码组都是禁用码组，故可判定出错。 当出现三个错误时000变

6、为111，它也是禁用码组。 若发生两个错误，如000变为011，则无法判断对错。 只能识别错误，但无法纠错，因为在收到100时，000，101和110都可能变为100。,举例（续2）,增加冗余度，只取两个作为许用码组： 000（晴） 111（雨） 可以检测两个以下的错误，并能纠正一位错误。 如收到011时，若只有一个错误，则判断错码在第一位，纠正为111。 但若错误码数不超过两位，则存在两种可能，000错两位和111错一位均可能变为011，因此只能检错，而无法纠错。,分组码,分组码：将信息码分组，为每组信息码附加若干监督码的编码，可用符号（n，k）表示。 分组码结构： 设码长n，信息位k，监督

7、位r，有n=k+r。,基本概念,码组重量：分组码的一个码组中“1”的数目。 码距：两个码组对应位上数字不同的位数称码组间的码距。 最小码距： 某种编码所产生的各个码组间距离的最小值。用d0表示。,最小码距d0与编码的检错和纠错能力的关系,检错：设要检测的错码个数为e，则要求最小码距d0e+1 纠错：设要纠正的错码个数为t，则要求最小码距d02t+1 同时纠错检错： d0e+t+1(et) 满足条件3可以同时纠正t个错，检出 e个错。,例题,已知6个码组为：0000000，0001011，0010101，0011110，0100110，101101。求其间的最小码距dmin和能检出和纠正的错码数

8、t。 dmin=3 纠错：要求最小码距d02t+1 则 t=1,结论,要提高纠错检错能力，必须增大最小码距。 用码率R=k/n表征编码效率。最小码距越大，编码效率越低。 编码理论要解决的问题就是找出许用码的集合，既要纠错能力强，又要编码效率高。,2.3.3 常用差错控制编码方法,奇偶校验码 恒比码 汉明码 循环码,奇偶校验码,奇偶校验码又称奇偶监督码，是最简单、最常用的检错码。有奇数监督码和偶数监督码两种。 特点：奇偶校验编码只需在信息码后加一位校验位（又称监督位），使得码组中“1”的个数为奇数或偶数即可。奇偶监督码能够检测奇数个错码。 偶校验码：监督码元a0 奇校验码：监督码元a0,垂直监督

9、码和水平监督码,垂直奇偶监督码,水平奇偶监督码,水平偶校验码表,按列发送,二维奇偶监督码,二维奇偶监督码,能够检测出全部奇数个错码和大部分偶数个错码。但无法检出在水平垂直方向上都成偶数的那些错码，例如构成矩形的四个顶点位置上的错码就无法检出。,按列发送,恒比码,恒比码又称定比码。在恒比码中，每个码组中“1” 的数目和“0”的数目保持恒定的比例。故在收端只需检测接收码组中“1”的个数是否正确。其纠错能力比奇偶监督码强。,汉明码,线性码是一种将信息位和监督位由一些线性代数方程联系在一起的编码。 线性分组码：也称为（n，k）线性码，可用线性方程组表述规律性的分组码。 汉明码是线性码的一种。 设总码长

10、为n，信息位为k，监督位数为r=n-k ； 若希望用r个监督位构造出r个监督关系式来指示一位错码的n个可能的位置，则要求 ： 2r-1n 或 2r k+r+1,例题,对于（n,k）汉明码，k=6，若要求能纠正一位错误，则所需监督位r至少多少位？ 要求2r k+r+1 可得 r=4,循环码(CRC码),如果一个码组的每一次循环移位是另一码组，这种码组叫做循环码。 循环码可以用线性方程确定。,循环码的生成,CRC码在发送端编码和接收端校验时，均可用事先约定的生成多项式G(X)来得到。 K位要发送的信息码对应一个 k-1次多项式K（X），r位冗余位对应r-1次多项式R（X）,由k位信息码后面加上r位

11、冗余位组成的n=k+r位码字则对应于一个n-1次多项式： T（X）=XrK（X）+ R（X）。,举例,信息位： 1011001 K（X）= X6+ X4 + X3+ 1 冗余位： 1010 R（X）= X3+ X 码字： 10110011010 T（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）

12、 即 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+ X T（X）/ G（X）= X6+ + X5 + X3+ X 可以整除，故接收正确,例题,在数据传输过程中，若信息码的信息为1011001，生成多项式为G(X)=X4+ X3+ 1, 求T（X）,常用CRC码,目前广泛使用（推荐）的 (Cyclic Redundancy Check)生成多项式有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 差错控制的应用,差错控制技术的应用，要视具体情况而定。 当出现少量错码在接收端能够纠正时，可采用前向纠错法（