第13章纠突发错误码课件

《第13章纠突发错误码课件》由会员分享，可在线阅读，更多相关《第13章纠突发错误码课件（65页珍藏版）》请在金锄头文库上搜索。

1、第十三章纠突发错误码,本章内容提要,纠突发错误码的定义和基本性质 法尔码 交错码 伯顿码 纠突发错误卷积码 岩垂码 纠突发错误循环码的译码 纠突发和随机错误码,大部分实际信道如短波、散射、有线等信道中产生的错误是突发性的；某些数据存储系统所产生的错误，大部分也是突发性的，而不是随机性的。 这些信道中所产生的错误是突发错误，或突发错误与随机错误并存，通常称这类信道为突发信道。 循环码检测突发错误能力强，但纠错效果不大。 人们希望能设计出一类专门用作纠突发错误的码，这类码称为纠突发错误码。 这类码在纠突发错误时的效率应比对付随机错误而设计的码要高，即对于给定的n和k， (n, k)有尽可能小的多余

2、度，或者说n k 尽可能小。,第13章纠突发错误码,定义13.1 长为b的突发是针对错误图样来定义的：如果一个矢量的非零分量局限于b个连续数据位，且第一和最后一位是非零的，则称该矢量为一个长为b的突发。 一个线性码如能纠正长为b或更短的突发错误，但不能纠正长为b+1的所有突发错误，则称此码是一个纠b长突发错误码，即该码的纠错能力为b。,定理13.1 长n的二元码字中，突发长度不大于b 的码字的总数N=2b-1(n+2 b) 。 证明 在长为n的二元码字中，考虑b为各种可能值的情况 （突发字个数）如下： b = 0 1个 （0, 0, , 0） 1 n个 2 n 1个 3 2(n 2)个 ,证毕

3、。,定理13.2 一个 (n, k) 线性分组码，能发现长度不大于b的错误图样的条件是 n k b 1 + lb(n + 2 b) 证明 由于对于所有的错误图样，若s0则能被发现，(n, k) 线性分组码的陪集数为 (2n 2k )/2k = 2n k 1 相应的，在陪集中总错误图样数为长度 b的突发错误图样： 2 b 1 (n + 2 b ) 所以2 n k 1 2 b 1 (n + 2 b ) 一般有2n k 1 , n b 所以 n k b 1 + lb(n + 2 b) （13.2） 或 n k b 证毕。,定理13.3 一个（n, k）线性码能纠正所有长度 b的突发错误的充要条件是：

4、长度 2b的突发不是一个码字。 证明假设存在一个长 2b的突发v是一个码字，则 v = u + w ，其中 u、w都是长度 b的突发。 必要性：若v是码字，因任意一陪集只有一个错误图样，则u和w必在同一陪集中。设u为陪集首，则陪集中每一个字的错误都是此陪集首，w必为不可纠错误，否则不可能与u同在一个陪集。这样尽管v是一“码字”，但它是一个错码，与假设v是一码字矛盾，因此把u作为陪集首来纠错也是无效的，即它不能纠正所有长 b 的突发错误。 充分性：若长度 2b的突发v不是码字，则u、w不在同一陪集中，若它们都是陪集首，则都是可以纠正的长 b 的突发错误。,定理13.4 纠正b 长突发错误码的校验

5、位数目至少是2b + lb (n + 2 2b )。 证明根据定理13.1，将其中的b 换成2b，得 n k 2b 1 + lb(n + 2 2b) （13.3）证毕。 由n 2b 知 lb(n+22b)1 ，代入定理13.4得 n-k 2b 。 表述为：(1) 一个(n, k)线性分组码，若要纠正所有长度 b的突发错误，则应n k 2b。 (2)（n, k）码的纠突上限为 ，称为赖格尔限。 满足赖格尔限的码是最佳的。 (3) 比率z=2b/(n k)被用来衡量码的纠突发错误的效率， 最佳码纠突发错误的效率等于1。,定理13.5 （n, k）循环码能检测长 n k的任何突发错误，包括首尾相接的

6、突发错误。 证明：设错误图样e(x)是长度 n k的突发错误，则e(x)可表示为 e(x)=x jB(x)，0 j n 1 式中， B(x)是次数 n k 1的多项式。 由于B(x)的次数小于循环码生成多项式g(x)的次数，因此B(x)不能为g(x)所整除。 又因为g(x)是xn 1的因式，因此g(x)与x j互素。因此g(x)也不能整除x jB(x)。 因此，由此e(x)产生的伴随式不为零。即一个(n, k)循环码能检测长 n k的任何突发错误。,对于长度 n k的突发错误图样，当它的错误局限在前i位和后l i位时，即出现首尾相接的错误时，有,如果将它乘以 xl - i ,则,由于它的次数小

7、于g(x)的次数，所以它的伴随式不为零。又由于xl - i与g(x)互素，因此g(x)不能整除e(x)，即e(x)= f(x) g(x)+s(x)，而s(x)0。所以(n , k)循环码也能检测长度 n k的首尾相接的突发错误。证毕。,法尔码是最早也是最大的一类用分析方法构造出的纠单个突发错误的二进制循环码。 由于可以根据不同的要求很方便地设计所需要的码，译码也很简单，因此法尔码是一类比较实用的，也是最基本的纠单个突发错误循环码。,定义13.2 设p(x)是GF(2)上的m次既约多项式，令是使p(x) 整除x+1的最小整数，称为p(x)的周期；令b是使b m且2b 1不能被整除的正整数，则由生

8、成多项式g(x)=(x2b 1 +1) p(x) 生成的码称为法尔码。 法尔码能纠正b长的突发错误 码的长度n等于和2b 1的最小公倍数，即n=LCM2b 1, 码的校验位数是 m + 2b + 1。,证明 只要证明长度b的任何突发都位于码的不同陪集中，这样它们便能作为陪集首而成为可纠正的错误图样。 令x iA(x)和x jB(x)分别表示两个长为b1和b2突发的多项式，且b1 b ，b2 b ，而,如果假定xiA(x)和xjB(x)在码的同一陪集中，那么多项式 v(x) = xiA(x)+xjB(x) (13.4) 必是一个码多项式。不失一般，假定ij，用2b 1除j i得,(13.5),把

9、式（13.5）代入式（13.4），那么v (x)可表示为,(13.6),根据假定v (x)为码多项式，而循环码的生成多项式为 g(x) = (x2b 1 +1 ) p(x)，所以(x2b 1+1 )|v(x)。 由于(x2b 1+1 )| xq(2b 1)+1 ，因此式(13.6)中的 或能被整除或等于零。,假定 (13.7) 令D (x)的次数为d，那么D (x) (x2b 1 +1 )的次数是2b 1+ d。因为A (x)的次数是b11，所以 的次数必定由 的次数决定，而 的次数是b+b21。 由式（13.7）可得 b+b21= 2b 1+ d (13.8) 根据假定b1 b ，b2 b

10、，所以由式（13.8）可得 b b1 + d (13.9) 又因b110，由式(13.9)可得b b11 + d ，故有 b d (13.10),从式(13.10)可知 中有 这一项。因为2b 1b d ，故D(x)(x2b 1+1)不能有 这一 项。 这与假设 相矛盾。 所以必有D(x)=0和 =0，这要求b =0和 A(x)=B(x) (13.11) 由于b =0 ，根据j i = q(2b 1)+ b可知 j i = q(2b 1) (13.12) 把式（13.11）和（13.12）代入式（13.4）可得 (13.13),注意到B(x)的次数小于b，所以 。因此，B(x)和p(x)互素。

11、已假定v(x)是码多项式，所以xj i +1必能被p(x)整除，ji必为p(x)的周期的整数倍。但由式(13.12)知，ji也是2b1的整数倍。由此，ji必是n=LCM2b1, 的倍数。显然，因为j和i都小于n，所以这是不可能的。 综上所述，长度b的两个突发xiA(x)和xjB(x)在同一个陪集中的假设是不对的。因此所有长度b的突发都处在 g(x) =(x2b 1+1)p(x)定义的g(x)生成的法尔码的不同陪集中，因而它们是可纠正的错误图样。由于码是循环的，所以它亦能纠正长度 b的首尾相接的突发错误。,例13.1 考虑既约多项式 p(x)=1+x2+x5 , 已知它是本原多项式，m=op(x

12、)=5， 周期 =251=31；令b=5，可算得2b1=9不能整除 =31，故可构造法尔码，其生成多项式为 ： 码长为： n=LCM9,31=279 k = n (m + 2b 1 ) =279 14 =265 所以该法尔码是 (279, 265) 循环码，能纠长度 5的任何突发错误。,法尔码的纠突发错误的效率为 若b等于m，则有 当m的值较大时，z约等于2/3。因此，相对于赖格尔限而言，法尔码的效率并不是很高。 能够纠正任何长度为b或更少的突发错误、并同时检测长为l b的任何突发的法尔码，可用下式生成： 该码长度等于和b + l 1的最小公倍数。,交错是一种非常简单而又有效的构造码的方法，它

13、可以大大提高纠随机错误码的纠突发错误能力，可使抗较短突发错误的码变成抗较长突发错误的码，使纠正单个定段突发错误的码变成纠多个定段突发错误的码。 这种方法所付出的代价是增加存储设备和加大通信时延。,13.3交错码,将个 (n, k) 码的码矢排成 n的矩形阵列，每行一个码矢，然后按列送至通信信道，在收端恢复矩形阵列的排列次序，就构成交错度为的交错码。即给定一个 (n, k) 循环码，用交错法将码长扩大倍，信息位数目也扩大了倍，构成一个（n, k）循环码，见图13.1。,图13.1 交错码的编码方法，其中为交错度,实现交错码的简明方法是排出阵列，按行编码和译码。一般地说，这并不是最简单的实现方法。

14、 最简单的实现方法是基于这样一个事实，即若原码是循环的，则交错码也是循环的。 如果原码的生成多项式是g (x)，则交错码的生成多项式是g (x )。因此，可用移位寄存器完成编码和纠错。 只要简单地将原码译码器的每个移位寄存器用级置换，即可根据原码的译码器推导出交错码的译码器，而不必改变其他连接。 所以，如果原码译码器较简单，则交错码也同样简单，而对于短码而言，原码译码器通常是比较简单的。,交错码的性能 （1）交错编码使错误分散，长的任何突发无论从何处开始，都至多只能影响每行中的一位。 （2）当且仅当每行中的错误图样是原（n, k）码中可纠正的图样时，此错误图样对整个阵列来说才是可纠正的。 （3

15、）若原码能纠正b的任何单个突发，则交错码能纠正 b 的任何单个突发，码长扩大倍，纠突能力也扩大倍。 若 (n, k) 码有最大可能的纠正突发错误能力，即nk2b=0，则交错码 (n, k)也具有最大可能的纠正突发错误能力。交错具有最大纠正突发错误能力的短码，能够构成实际上任意长的、具有最大可能纠突发错误能力的码。,（4）若原码是循环的，其生成多项式为g(x)，则交错码也是循环的，且生成多项式为g (x)。 证明 设经次交错后得到的码是,(13.14),它的输出方式与图13.1相同，其中 ，所以有 ，即它们都是循环码 (g (x)中的码矢量。,如果把上述（n, k）线性分组码循环移位一次，得,(

16、13.15),显然，其中的每一行仍是(g (x)的码矢量。所以这个（ n, k）线性分组码是个循环码。,若把式(13.14)的循环码用多项式表示，则其码多项式为,式中,（5）交错技术把寻求长而有效的纠突发错误码这个问题，简化为寻求好的短码。 （6）交错码需增加存储设备，加大通信时延。 交错是一种时间扩散技术，它使信道突发错误的相关性减小。当足够大时可将突发错误离散为随机错误，从而可用纠随机错误码来纠突发错误。因此交错技术在短波、散射、有线等有记忆的信道中得到了广泛的应用。 （7）交错技术是一种等效长码的技术。根据Shannon第二定理，必然有更好的性能。,伯顿发现一类纠正定段突发错误的循环码。考虑一(n, k)码，码长n是整数m的倍数，如n =