首页 理论教育码间距离d及其检错能力分析

码间距离d及其检错能力分析

【摘要】:因此,一个码组的最小码间距离d0就决定了该码组的检错、纠错能力。只要最小码距不小于3,在半径位的圆上及圆内就不会有其他许用码,因而能检测错码的位数等于2。

1.码间距离d

码间距离是一个码组中任意两个码字之间对应位上码元取值不同的位数,用d表示。码间距离(Code Distances)简称码距,又称汉明距离。对二元码,码间距离d可用式(4-3)计算

即码间距离d等于两个码字对应位模2相加后 “1”的个数。如三位重复码的码距d(111 000)=3。如有两个码字Ci,Cj分别为101110和101011,则码距计算如下

故d(Ci,Cj)=2。在一个码组中各码之间的距离不一定都相等,码组中的码距称为最小码间距离,用d0表示。由重复编码的例子可知,两个码字之间不同的位数越多,其检错、纠错能力越强,即码间距离越大,其检错、纠错能力越强。因此,一个码组的最小码间距离d0就决定了该码组的检错、纠错能力。

图4-3 码间距离的几何意义

对于三位编码的码间距离,可用三维几何空间来说明。三位编码的码字共有23=8个,可用三维几何空间立方体的8个顶点来表示,如图4-3所示。码字之间的距离可用对应两顶点间沿立方体各棱行走的最短几何距离来示意。由图4-3可见,对上述重复编码的例子,其码组只有“111”、“000”两个许用码,从 “111”到 “000”要经过三条边,显然它们之间的距离d=3。同样,对于多位编码的码间距离,可用多维空间来说明。

2.最小码间距离d0与检错纠错能力的关系

(1)当码组仅用于检测错误时,若要求检测e个错误,则最小码距为

这可由图4-4 (a)来说明。图中A为一个码字,B为另一个码字。若码字A有两位错,则A变为以2为半径的圆上某点。只要最小码距不小于3,在半径位的圆上及圆内就不会有其他许用码,因而能检测错码的位数等于2。即最小码距为d0,将能检测 (d0-1)个错误。若要检测e个错误,则必须满足d0≥e+1的要求。

图4-4 码间距离与检纠能力的关系

(2)当码组仅用于纠正错误时,为纠正t个错误,要求最小码距为

这可由图4-4(b)来说明。当码字A发生两位错时,则落在以A为圆心以2为半径的圆上某点。码字B有两位错时,则落在以B为圆心以2为半径的圆上某点。只要这两个圆不重叠、不相交,就能区分出左边圆上的为码字A,右边圆上的为码字B。可见,能纠正两位错码,它要求的最小码距为5。所以纠正t个错误,必须满足d0≥2t+1的要求。

(3)当码组既要检错,又要纠错时,为纠正t个错误,同时检测e个错误,则要求的最小码距为

可用图4-4 (c)来说明。当码字A出现e个错误,将落在以A为圆心,以e为半径的圆上某点。码字B出现t个错误时,将落在以B为圆心以t为半径的圆上某点,要纠正码字B的错误,同时又能检出码字A的错误,就要求A的大圆和B 的小圆不相交、不重叠。即A和B 之间的距离要大于(e+t),也即最小码距满足d0≥e+t+1。

3.纠错编码的分类

纠错编码的分类如图4-5所示。

图4-5 纠错编码分类示意

纠错编码按照其实现的功能可分为检错码和纠错码。一般来说,能够发现错误的码称为检错码。在译码时不仅能够发现错误,而且能够自动纠正错误,通过译码恢复正确的码字,称为纠错码。

按信息码元与监督码元的关系,可以分为线性码和非线性码。线性码中信息码元与监督码元之间存在线性关系。实际应用的一般都是线性码。当信息码元与监督码元之间为非线性关系时,称为非线性码。

纠错编码还可分为分组码和卷积码。分组码是把信息码分为许多小段,即分组,每组信息码附加若干监督码。监督码元仅与本分组的信息码元有关。而卷积码中,监督码元不仅与本组的信息码有关,而且与前后若干组中的信息码有关。

另外,按照码字的结构特点是否具有循环性,还可分为循环码和非循环码;按照码元的取值可分为二进制码和多进制码;按照纠错的类别分为纠随机错误的码和突发错误的码。

4.编码效率

在分组码编码中,加入的监督位越多,检错纠错能力越强。但这会使总的码长增加,即要传输的位数增加,使编码的效率降低。设码字的信息码元个数为k,监督码元的个数为r,总码元的个数(总的码长)为

编码效率η是指码字的信息码元个数与总k的码长n的比值,即

可见码长一定时,监督位越多,编码效率越低。