检错与纠错基本原理浅析

差错控制编码的基本思想是在被传输的信息码元中附加一些监督码元,并且使它们之间确定某一种关系,根据传输过程中这种关系是否被破坏来发现或纠正错误。可见这种差错控制能力是以降低信息传输效率为代价来换取的。

设编码后的码组长度、码组中所含信息码元以及监督码元的个数分别为n、k和r,三者间满足n=k+r,定义编码效率为R=k/n=1-r/n。可见码组长度一定时,所加入的监督码元个数越多,编码效率越低。

香农的信道编码定理指出:对于一个给定的有扰信道,若信道容量为C,只要发送端以低于C的速率R发送信息(R为编码器的输入二进制码元速率),则一定存在一种编码方法,使编码错误概率P随着码长n的增加,按指数下降到任意小的值。可以表示为

式中,E(R)称为误差指数,它与R和C的关系如图10.2.2所示。

由定理有如下结论:

(1)在码长及发送信息速率一定的情况下,为减小P可以增大信道容量。由图10.2.2可知,E(R)随信道容量的增加而增大。由式(10.2.1)可知,错误概率随E(R)的增大而指数下降。

(2)在信道容量及发送信息速率一定的条件下,增加码长,可以使错误概率指数下降。对于实际应用来说,此时的设备复杂性和译码延时也随之增加。

香农的信道编码定理为信道编码奠定了理论基础,虽然定理本身并没有给出具体的差错控制编码方法和纠错码的结构,但它从理论上为信道编码的发展指出了努力方向。

下面用3位二进制码组来说明检错纠错的基本原理。3位二进制码元共有8种可能的组合:000、001、010、011、100、101、110、111。如果这8种码组都可传递消息,若在传输过程中发生一个误码,则一种码组会错误地变成另一种码组。由于每一种码组都可能出现,没有多余的不可用码组。因此,接收端不可能发现错误,认为发送的就是另一种码组。

如果选其中000、011、101、110来传送消息,这相当于只传递00、01、10、11四种信息,而第3位是附加的。这位附加的监督码元与前面两位码元一起,保证码组中“1”码的个数为偶数。这4种码组称为许用码组。另外4种码组不满足这种校验关系,称为禁用码组,它们在编码后的发送码元中不会出现。接收时一旦发现有禁用码组,就表明传输过程中发生了错误。用这种简单的校验关系可以发现1个或3个错误,但不能纠正错误。因为当接收到的码组为禁用码组时,比如为010,无法判断发送的是哪个码组。虽然原发送码组为101的可能性很小(因为3个误码的概率一般很小),但不能绝对排除,即使传输过程中只发生一个误码,也有三种可能的发送码组即000、011和110。

假如进一步将许用码组限制为两种即000和111,显然这样可以发现所有2位以下的误码,若用来纠错,可以用最大似然准则纠正1位错误。

可以用一个三维立方体来表示上述3位二进制码组的例子,如图10.2.3所示。图中立方体各顶点分别表示8位码组,3位码元依次表示x、y、z轴的坐标。

图10.2.2　误差指数曲线

图10.2.3　码距的几何解释(www.xing528.com)

这里定义码组中非零码元的数目为码组的重量,简称码重。比如100码组的码重为1,101码组的码重为2。定义两个码组中对应码位上具有不同二进制码元的位数为两码组的距离,称为汉明(Hamming)距,简称码距。在前面3位二进制码组的例子中,当8种码组均为许用码组时,两码组间的最小距离为1,称这种编码的最小码距为1,一般记为dmin=1;当选4种码组为许用码组时,最小码距dmin=2;当用2种码组作为许用码组时,dmin=3。从图10.2.3所示的立方体可以看出,码距就是从一个顶点沿立方体各边移到另一个顶点所经过的最少边数。图中粗线表示000与111之间的一条最短路径。很容易得出前例中各种情况下的码距。

根据以上分析可知,编码的最小码距直接关系到这种码的检错和纠错能力,所以最小码距是差错控制编码的一个重要参数。对于分组码一般有以下结论:

(1)在一个码组内检测e个误码,要求最小码距

(2)在一个码组内纠正t个误码,要求最小码距

(3)在一个码组内纠正t个误码,同时检测e(e＞t)个误码,要求最小码距

这些结论可以用图10.2.4所示的几何图形简单地给予证明。

图10.2.4　码距与检错和纠错能力的关系

图10.2.4(a)中C表示某码组,当误码不超过e个时,该码组的位置移动将不超出以它为圆心、以e为半径的圆。只要其他任何许用码组都不落入此圆内,则C发生e个误码时就不可能与其他许用码组混淆。这意味着其他许用码组必须位于以C为圆心、以e+1为半径的圆上或圆外。因此该码的最小码距dmin为e+1。

图10.2.4(b)中C1、C2分别表示任意两个许用码组,当各自误码不超过t个时,发生误码后两码组的位置移动将各自不超出以C1、C2为圆心,以t为半径的圆。只要这两个圆不相交,当误码小于或等于t个时,根据它们落在哪个圆内可以正确地判断为C1或C2,就是说可以纠正错误。以C1、C2为圆心的两圆不相交的最近圆心距离为2t+1,即为纠正t个误码的最小码距。

式(10.2.4)所述情形中纠正t个误码同时检测e个误码,是指当误码不超过t个时能自动纠正误码,而当误码超过t个时则不可能纠正错误但仍可检测e个误码。图10.2.4(c)中C1、C2分别为两个许用码组,在最坏情况下C1发生e个误码而C2发生t个误码,为了保证此时两码组仍不发生混淆,则要求以C1为圆心、以e为半径的圆必须与以C2为圆心、以t为半径的圆不发生交叠,即要求最小码距dmin≥t+e+1。

可见dmin体现了码组的纠、检错能力。码组间最小距离越大,说明码字间最小差别越大,抗干扰能力就越强。

由于编码系统具有纠错能力,因此在达到同样误码率要求时,编码系统会使所要求的输入信噪比低于非编码系统,为此引入了编码增益的概念。其定义为,在给定误码率下,非编码系统与编码系统之间所需信噪比Eb/No之差(用dB表示)。采用不同的编码会得到不同的编码增益,但编码增益的提高要以增加系统带宽或复杂度来换取。