理论教育 编码的纠检错能力:提升计算机网络技术

编码的纠检错能力:提升计算机网络技术

时间:2023-11-22 理论教育 版权反馈
【摘要】:在校验码中,码组中非零码元的个数称为码组的重量,简称码重。一种编码方案的抗干扰能力的大小通常用码距来衡量。码距d与编码的检错和纠错能力的关系如下。码距与编码的纠检错能力的这3种关系可用图3-3来解释。图中C1、C2表示任意两个合法码组。上述3种情况的发生概率与校验码的码距直接相关,也和差错控制方法有关。例如,某种校验码的码距d=3,如果只采用检错措施,则可检测出2位错。

编码的纠检错能力:提升计算机网络技术

校验码中,码组中非零码元的个数称为码组的重量,简称码重。码组之间差异的大小用距离来衡量,两个码组间的距离就是对应位之间不相同的个数。例如,“1001”码组的码重是2,“0010”码组的码重是1,这两个码组之间的距离是3。

一种编码方案的抗干扰能力的大小通常用码距来衡量。码距也叫海明(Hamming)距。各种资料中对码距或海明距的定义有所不同,特别是与码组间的距离相混淆,两者混用的地方很多,造成不必要的麻烦。在这里,我们定义:某种编码的码距是该编码全部码组中两两之间距离的最小值。因此,码距是一种编码方案的综合考虑,它考虑的是该编码方案按其编码规律所产生的全部码组之间的关系。

码距d与编码的检错和纠错能力的关系如下。

1)若de+1,只要出错位数不超过e,则可检测出e个错误。

2)若d≥2t+1,只要出错位数不超过t,则可纠正t个错误。

3)若de+t+1(e>t),只要出错位数不超过e,则可纠正t个错误,同时检测出e个错误。

码距与编码的纠检错能力的这3种关系可用图3-3来解释。图中CC1C2分别表示某个合法码组。如果一个码组符合编码规则,则称该码组是一个合法码组,否则称为非法码组。与C码组距离为ed的其他码组(不管是合法码组还是非法码组)的位置坐落在以C为圆心、以ed为半径的圆上(实际上是多维的球,码组有几位,球就是几维)。两个合法码组之间的距离至少为d

978-7-111-31053-2-Chapter03-4.jpg

图3-3 码距与编码的纠检错能力的关系

a)de+l b)d≥2t+l c)de+t+le>t)(www.daowen.com)

对于第1种情况可用图3-3a解释。当C码组在传输中出错位数(错码)不超过e个时,出错的非法码组的位置将不超过以C为中心且以e为半径的圆。当e<d时,由于两个合法码组之间的距离至少为d,因此合法码组不会落入此圆内,只能落在以d(即e+1)为半径的圆上或圆外,这样C码组发生e个误码时就不可能与其他合法码组相混,就能够判断出它是一个非法码组。

对于第2种情况可用图3-3b解释。图中C1C2表示任意两个合法码组。当各自的出错位数不超过t时,发生错码后的C1C2码组的位置移动将分别不会超出以C1C2为圆心且以t为半径的圆。只要这两个圆不相交,就可以根据它们落在哪个园内正确地判断为C1C2码组,把差错纠正过来。由此可见,纠错一般采用最大似然规则,即非法码组离哪个合法码组最近,就把该非法码组纠正为哪个合法码组。当d≥2t+1时,这两个圆才不会相交,所以纠正t个错误的最小码距是2t+1。

对于第3种情况可用图3-3c解释。这里所说的“可纠正t个错误,同时检测出e个错误”的含义是:当出错位数不超过t时能够自动纠正,当出错位数超过t又不超过e时,则不能纠正,但能检测出来。图中C1C2表示任意两个合法码组,在最坏的情况下,C1码组发生e个错码,C2码组发生t个错码,为了保证错码后的C1C2码组不发生相混而能够纠正错误,则要求以C1为圆心且以e为半径的圆与以C2为圆心且以t为半径的圆不相交,即要求码距de+t+1。当错码超过t个时,两个圆有可能相交,这时就失去了纠错能力,但仍落入以C1C2为圆心且以d为半径的圆内(图中未画出),即仍可以检测出错码。

接收方收到一个码组后,会有以下3种情况发生。

1)该码组在传输过程中无差错发生。

2)该码组在传输过程中有差错发生,所发生的差错被接收方检测出。例如,当合法码组的出错位数小于码距d时,就会变成非法码组,这时接收方根据编码规则就可以发现错误。

3)该码组在传输过程中有差错发生,但接收方未能检测出来。当合法码组的出错位数等于或大于码距d时,该合法码组就有可能变成另外一个合法码组,这时接收方就无法检测出来。

上述3种情况的发生概率与校验码的码距直接相关,也和差错控制方法有关。例如,某种校验码的码距d=3,如果只采用检错措施,则可检测出2位错。如果采用纠错措施,则可纠正1位错,这时若有2位错,则会被当做1位错来进行纠正,结果只能产生新的错误。如果出错位数超过2位,则可能被检测出来,也可能检测不出来。不过,出错位数越多,发生的概率就越小,而且要小的多,是呈指数下降的。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈