第10章_检错与纠错

1、P.174 本章学习如何检测和纠正数据传输中“位差错”。l本章研究：l“位差错”的概念和类型l检错技术基本原理l三种常用的检错技术l奇偶校验技术l循环冗余校验技术l校验和技术l汉明码纠错技术本章仅讲技术原理，数学细节留给大家自己去深入1 差错类型差错类型 Types of Error 2 差错检测差错检测 Error Detection3 差错纠正差错纠正 Error Detection l传输中差错是不可避免的。所以必须检测和纠正比特流在传输中出现的“位差错”。l所谓“位差错” ，就是指将数据从一个节点传送到下一个节点的过程中，数据中的一位（比特）或多位发生了改变。l“位差错”检测的基本原理

2、是“冗余校检技术”。l检错技术的基本要求：检错技术的基本要求：接收方应在不知道实际发送的数据的情况下，能发现所接收到的数据是否有错。l在计算机通信中，通常是先检错，发现差错时不是对有错的数据进行纠错，而是丢弃有差错的数据，并通过“重传”（将数据重新发送一遍）实现纠错。l无论是检错还是纠错技术，都是数学研究的成果。l信号在物理信道中传输时，线路本身电器特性造成的随机噪声、信号幅度的衰减、频率和相位的畸变、电器信号在线路上产生反射造成的回音效应、相邻线路间的串扰以及各种外界因素（如大气中的闪电、开关的跳火、外界强电流磁场的变化、电源的波动等）都会造成传输信号的失真。l在数据通信中，以上原因将会使接

3、收端收到的二进制数位和发送端实际发送的二进制数位不太一致，从而造成由“0”变成“1”或由“1”变成“0”的差错。l信道本身的随机热噪声 随机错误(某位错）,可通过提高信道的信噪比等方法来抑制l外界原因引起的冲击噪声 突发错误（一连串码元均出错）【突发长度】从突发错误发生的第一个码元到有错的最后一个码元间所有码元的个数 一位差错：数据单元中仅某一位差错多位差错：数据单元中两位或两位以上差错突发差错：数据单元中连续两位或两位以上差错。受影响的位数取决于数据速度和噪声的持续时间。参见P174-175图10.1, 图10.2 发生差错的码元数 Pe = 接收的总码元数 在计算机网络中，误码率一般要求低

4、于10-6。l实现差错检测的基本思路 发送方添加一些附加的比特作为差错检测码l从最简单的做法说起l问题：知道了可能发生的差错类型，如何把它们检测出来？l一种可用的方法：将每个数据单元发送两次。如输入密码或告诉对方电话号码两遍。l缺点：这样做将使数据传送速率奇慢传输时间将要增加一倍，需花费大量时间进行逐个比特的比较。l使用“冗余校验技术” 最常用的技术是在每个数据单元中加入一些称为“冗余位”的附加比特（即“差错控制编码差错控制编码”）。 这种技术之所以被称为“冗余校验技术”,因为一旦传输被确认无误，那些附加的冗余数位便被自动丢弃。 （第二遍给出的密码或电话号码即为“冗余位”） 数据位数据位要发送

5、的数据 冗余位冗余位差错控制编码 码码 字字codewordl数据字：报文划成的数据块（假设为k位）l码字：数据字冗余位P17图10.P175图10.3差错控制编码差错控制编码可分为： 检错码检错码 用于自动发现传输差错的编码 纠错码纠错码 能自动发现而且能自动纠正传输差错的编码 编码效率计算编码效率计算: : k k R= = k+r n 式中: k - 码字中信息位数 r - 码字中冗余位数 n - 码字总位数差错控制的两大目标：差错控制的两大目标：l 尽量降低误码率尽量降低误码率 尽量提高编码效率尽量提高编码效率l又称异或运算(XOR), 计算机编码常用。l运算法则: l相同是0,不同是

6、1l或者视为没有进位的1和0的简单加法P176 图10.4l汉明距离汉明距离 两个码字作XOR运算，运算结果中1的个数。 例 10.4 1. d(000,011)的汉明距离是2 2. d(10101,11110)的汉明距离是3l在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 例如： 1011101 与 1001001 之间的汉明距离是 2。 2143896 与 2233796 之间的汉明距离是 3。 “toned” 与 “roses” 之间的汉明距离是 3。l汉明距离是以美国数学家理查德卫斯里

7、汉明(Richard Wesley Hamming,1915-1998)的名字命名的。l最小汉明距离最小汉明距离 有效码字表中所以码字对的最小汉明距离。 例10.5 求表10.1的最小汉明距离(dmin=2) 例10.6 求表10.2的最小汉明距离(dmin=3)l编码方案三参数编码方案三参数 码字长度n， 数据位长度k，最小汉明距离dmin 写法 C(n,k)和dmin=l检错定理检错定理 一个编码方案的最小汉明距离如果是dmin=s+1，那么只能检测出不多于s个的差错。l纠错定理纠错定理 一个编码方案的最小汉明距离如果是dmin=2s+1，那么只能纠正不多于s个的差错。l奇偶校验l奇、偶位

8、值的加入，使字符中“1”的个数为偶数（“偶校验”）或奇数（“奇校验”）l无法检测整数倍偶数个比特差错l使用奇偶校验并不是十分安全，因为噪声脉冲持续的时间经常足以破坏一个以上的比特，特别是在数据率较高的情况下。l奇偶校验码 通过增加冗余位使码字中“1”的个数保持奇数或偶数的编码方法。简单经济，但漏检率较高。 垂直奇偶校验 (简单奇偶校验，行奇偶校验) 水平奇偶校验（列奇偶校验） 水平垂直奇偶校验(两维奇偶校验)P176 图10.4l垂直奇偶校验( “简单奇偶校验”或“行奇偶校验”) 编码和校验实现最简单。 可以边发送边插入冗余位。 最常用而且最经济的检错技术。l偶校验（even-parity c

9、heck） 使码字中“1”的个数保持偶数。l奇校验（odd-parity check） 使码字中“1”的个数保持奇数。偶校验位 p = (d1+d2+dn-1) = 奇校验位 p = (d1+d2+dn-1+1) =)2模(11niik)2模( 111niikl表10.1和表10.3分别是数据位为2和5时的“简单奇偶校验码” C(3,2)和C(5,4)。l可以证明C(3,2)和C(5,4)编码方案的最小汉明距离都是dmin=2。l根据检错定理，这种编码只能检测出单个位的差错，且不能纠正任何差错。l实际上，简单奇偶校验码可以检测出发生奇数个差错出现的问题，但不能检测出发生偶数个差错的问题。lP1

10、82 例10.12 (数据见下页)l如果接收到的码字不在上表，则被拒收（检错成功）l如果接收到的码字在上表中，则被接收（无出错或漏检）垂直奇偶校验可以检测出所有的1位差错，但只能检测差错数为奇数的多位差错或突发差错。差错漏检率1/2。【例】原始数据000111011，采用偶校验。 则发送端通过线路传输发出的码字为1000111011。 若接收端接收到的是 1111111011 或0110111011 或 1100010011，将均被拒收。 但若接收端接收到的是1110111011或1100011011或 1000011010，仍会通过验收（漏检）。 编码效率 R： (设发送的数据为k位,发送时

11、另加一个奇校验位或偶校验位) 水平奇偶校验又称水平奇偶校验又称“列奇偶校验列奇偶校验” 。 P183 图10.11au水平奇偶校验(列奇偶校验)差错漏检率1/2；编码和校验实现复杂；不能边发送边生成并插入冗余位。l两维奇偶校验编码，又称“水平垂直奇偶校验”。水平冗余校验位水平冗余校验位( (列奇偶位列奇偶位) )垂直冗余校验位垂直冗余校验位( (行奇偶位行奇偶位) )u误码率可减少到原误码率1/1001/10000，但如某个信息段中出现偶数个差错，而另一个信息段的对应位置处也正好都出现差错，这种差错无法检测出来。l一种最有效的冗余校验技术。l与基于加法的奇偶校验不同，CRC基于二进制除法。l在

12、CRC中，不是把二进制数位相加来获得一个所需的奇偶数位，而是在数据单元（比如一个字节）的后面附加一个称为“循环冗余码循环冗余码”或“CRC余数余数”的冗余比特串，使该数据单元可被另一个预先给定的二进制数完全除尽。l接收端将所接收的数据单元用同样的二进制数相除，如果无余数，则可认为所接收的数据单元正确无误，如果有余数，则认定该数据单元已有差错。lCRC所用的冗余位串是通过将数据单元除以预先给定的除数获得。余数即为“循环冗余码”。l一个有效的“循环冗余码”应具有两种品质：必须正好比给定的除数少一位，附加到数据串后必须使新形成的位串能被该除数完全除尽。l可靠性 除了正好数据块的比特值是按除数值变化的

13、差错外，CRC将检测出其他所有的差错。由于常用的CRC除数为13、17或是33个比特，所以误码的可能性几乎为零。l假设给定除数的位数是n+1，首先在数据单元的末尾加上n个0。l用二进制除法将加长后的数据单元除以给定除数，得到的余数即为循环冗余编码（CRC）。码字码字l用以上获得的n位CRC码替换数据单元附加的n个0，然后传送。l如余数为0（被整除了），则以n位0为CRC码（即不作替换）。l如果余数位数小于n，则最左边的不足位数用0填充。l接收方收到数据单元和CRC后，将整个码字除以给定除数（同生成CRC用的除数）。l如果到达的数据没有差错，接收方CRC校验器产生的余数应是0，数据被接收，如果产

14、生的余数非0则被拒收。 “循环冗余码”的产生使用所谓“模2”除法按位作异或运算。右图为其过程示意。P187 图10.15l产生“循环冗余码”的除数通常不是用0和1二进制位串表示，而是用一个代数多项式（称为“生成多项式”）表示。使用生成多项式的原因有两个：简短，且可从数学角度验证有关概念。（进行多项式除法时，只要对其相应系数相除即可）。参见P190 图10.21l常用的“循环冗余码”生成多项式已有三个国际标准： CRC-12 = x12+x11+x3+ x2+x+1 （13位除数：1100000001111） CRC-16= x16+x15+x2+1 （17位除数：110000000000001

15、01） CRC-ITU= x16+x12+x5+1 （ITU-国际电信联盟） （17位除数：10001000000100001）l另外还有（在若干网络协议中被规定为选件）： CRC-32=x32+x26+x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+x4+ x2+x+1 （33位除数：100000100110000010001110110110111）参见P195 表10.7有资料指出，如果使用CRC-16或CRC-ITU为生成多项式(即发生器产生16位数作循环冗余校验）,可以查出全部一位差错、双位差错、奇数位差错，全部16位或16位以下突发差错，99.99

16、7%的17位突发差错及99.998%的18位或更长的突发差错；传输速率为9600 bps时，数据传输3000年才会有一个差错漏检。l高层协议中使用的差错检测技术称为“校验和技术” 。校验和技术也是建立在冗余技术的概念上的。l校验和技术原理 在发送端，由校验和发生器将数据分成相同的n位数据段（通常是16位）。然后以每两个字节为1个单位相加，若相加的结果有进位，那么将和加1。如此反复，直到全部数据都相加完为止。将最后的和值取二进制反码，便得到16位的校验和。将此校验和作为冗余位附加在数据上发送给接收方以供校验。 为了生成校验和，发送方要做以下工作：n将数据单元分为 k 个分段，每段n个比特n以反码

17、相加的规则将分段1和分段2相加起来n将分段3与以上求得的结果相加n将分段4与以上求得的结果相加n重复以上步骤，直到第 k 个分段也被相加为止n将最后结果取反，即得到该数据单元的校验和自动请求重发自动请求重发 (ARQ , Automatic Repeat Request） 自动发现差错并要求对方重发正向纠错正向纠错 (FEC , Forward Error Correction） 自动发现并纠正错误lARQ只需检错码，编码效率高，设备简单，但要求双向信道，发送方要有数据缓冲区。lFEC要用纠错码，编码效率低，设备复杂，但实时性好，只需单向信道。 l理论上，自动纠正每一个二进制代码的传输差错是可

18、以做到的。但纠错码比检错码复杂得多，而且需要更多的冗余位。用于多位或突发差错纠错的位数太大的，以致大部分情况下，将使编码效率低到不可接受的程度。为此，大部分纠错码只限于处理1位、2位或3位差错。l在数据通信中，最常用的纠错码是所谓“汉明码”(Hamming Code），是贝尔实验室的科学家R.W.Hamming 于1950年提出的，主要用来纠正1位差错。l奇偶校验可以检测出1位差错的情况，方法是加上一个冗余的奇校验位或偶校验位。纠错则需确定其中哪位有差错。l如果要确定一个ASCII字符（7位）中的某位差错，此时需要区别8种情况：没差错，第1位错，第2位错，第7位错。于是，需要3个冗余位来表示8

19、种不同的状态（000 -111）。l实际上，3位冗余是不够的。因为，冗余位本身也可能出现差错！l如何计算为m位数据纠错时所需的冗余位数 r 呢? l此时数据传输的总位数是m+r，且要求 r必须能够至少表示 m+r+1 种状态。其中，一种状态表示无差错，m+r 种状态分别表示在 m+r 位每个位置上发生的差错。l由于r 位二进制数可以表示2r种不同的状态,所以，2r必须大于或等于 m+r+1。 2 r m+r+1 如果m=7（ASCII代码），则能满足上式的最小 r 值是4。因为： 24 7+4+11234567 2333444 356791011 下表为一些可能的 m 值及其对应的 r 值。l冗余位的定位冗余位的定位 汉明码可用于任何长度的数据块，并利用了上面讨论的数据位数和冗余位数的关系。例如，一个7位ASCII码要求4个冗余位，它们可以附加在数据位的后面，亦可散布在数据位之中。下图中，各冗余位处于第1、2、4、8位（2的n次方处），分别用r1，r2，r4，r8表示。l在汉明码中，每一个r位都是一组数据位的奇偶校验码。用于计算7数据位4个r值（奇偶校验码）的方案