第13章纠突发错误码课件.ppt

《第13章纠突发错误码课件.ppt》由会员分享，可在线阅读，更多相关《第13章纠突发错误码课件.ppt（63页珍藏版）》请在三一办公上搜索。

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

2、码,定义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)个,证毕。,定理13.2 一个(n,k)线性分组码，能发现长度不大于b的错误图样的条

3、件是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的突发错误的充要条件是：长度 2b的突发不是一个码字。证明假设存在一个长 2b的突发v是一个码字，则 v=u+w，其中 u、w都是长度 b的突发。必要性：若v是码字，因任意

4、一陪集只有一个错误图样，则u和w必在同一陪集中。设u为陪集首，则陪集中每一个字的错误都是此陪集首，w必为不可纠错误，否则不可能与u同在一个陪集。这样尽管v是一“码字”，但它是一个错码，与假设v是一码字矛盾，因此把u作为陪集首来纠错也是无效的，即它不能纠正所有长 b 的突发错误。充分性：若长度 2b的突发v不是码字，则u、w不在同一陪集中，若它们都是陪集首，则都是可以纠正的长 b 的突发错误。,定理13.4 纠正b 长突发错误码的校验位数目至少是2b+lb(n+2 2b)。证明根据定理13.1，将其中的b 换成2b，得 n k 2b 1+lb(n+2 2b)（13.3）证毕。由n 2b 知 lb

5、(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的任何突发错误，包括首尾相接的突发错误。证明：设错误图样e(x)是长度 n k的突发错误，则e(x)可表示为 e(x)=x jB(x)，0 j n 1 式中，B(x)是次数 n k 1的多项式。由于B(x)的次数小于循环码生成多项式g(x)的次数，

6、因此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,则,由于它的次数小于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的首尾相接的突发错误。证毕。,法尔码是最早

7、也是最大的一类用分析方法构造出的纠单个突发错误的二进制循环码。由于可以根据不同的要求很方便地设计所需要的码，译码也很简单，因此法尔码是一类比较实用的，也是最基本的纠单个突发错误循环码。,定义13.2 设p(x)是GF(2)上的m次既约多项式，令是使p(x)整除x+1的最小整数，称为p(x)的周期；令b是使b m且2b 1不能被整除的正整数，则由生成多项式g(x)=(x2b 1+1)p(x)生成的码称为法尔码。法尔码能纠正b长的突发错误码的长度n等于和2b 1的最小公倍数，即n=LCM2b 1,码的校验位数是 m+2b+1。,证明 只要证明长度b的任何突发都位于码的不同陪集中，这样它们便能作为陪

8、集首而成为可纠正的错误图样。令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),把式（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)中的 或能被整除或等于零。,

9、假定(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，所以由式（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

10、 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)互素。已假定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)生成的法尔码

11、的不同陪集中，因而它们是可纠正的错误图样。由于码是循环的，所以它亦能纠正长度 b的首尾相接的突发错误。,例13.1 考虑既约多项式 p(x)=1+x2+x5,已知它是本原多项式，m=op(x)=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或更少的突

12、发错误、并同时检测长为l b的任何突发的法尔码，可用下式生成：该码长度等于和b+l 1的最小公倍数。,交错是一种非常简单而又有效的构造码的方法，它可以大大提高纠随机错误码的纠突发错误能力，可使抗较短突发错误的码变成抗较长突发错误的码，使纠正单个定段突发错误的码变成纠多个定段突发错误的码。这种方法所付出的代价是增加存储设备和加大通信时延。,13.3交错码,将个(n,k)码的码矢排成 n的矩形阵列，每行一个码矢，然后按列送至通信信道，在收端恢复矩形阵列的排列次序，就构成交错度为的交错码。即给定一个(n,k)循环码，用交错法将码长扩大倍，信息位数目也扩大了倍，构成一个（n,k）循环码，见图13.1。

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

14、。（2）当且仅当每行中的错误图样是原（n,k）码中可纠正的图样时，此错误图样对整个阵列来说才是可纠正的。（3）若原码能纠正b的任何单个突发，则交错码能纠正 b 的任何单个突发，码长扩大倍，纠突能力也扩大倍。若(n,k)码有最大可能的纠正突发错误能力，即nk2b=0，则交错码(n,k)也具有最大可能的纠正突发错误能力。交错具有最大纠正突发错误能力的短码，能够构成实际上任意长的、具有最大可能纠突发错误能力的码。,（4）若原码是循环的，其生成多项式为g(x)，则交错码也是循环的，且生成多项式为g(x)。证明 设经次交错后得到的码是,(13.14),它的输出方式与图13.1相同，其中，所以有，即它们都

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

16、n第二定理，必然有更好的性能。,伯顿发现一类纠正定段突发错误的循环码。考虑一(n,k)码，码长n是整数m的倍数，如n=m。码多项式表示如下定义下式的m个相邻码位vi m,vi m+1,v(i+1)m 1 为一个分组，其中0 i。因此其码矢由 个分组组成。当且仅当长度等于或小于m的突发局限在个相邻分组内时，称此突发为定段突发，是小于的正整数。一个长n=m可纠正全部限制在等于或小于个分组内的定段突发错误的线性码，称为纠m长定段突发错误码。长为(1)m+1的突发不论从何处开始，最多只影响个分组，显然，纠m长定段突发错误码能够纠正任何长度等于或小于(1)m+1的单个突发错误。纠m长定段突发错误码可当作

17、纠(1)m+1长单个突发错误码使用。,13.4 伯顿码,定义13.3 令p(x)是m次既约多项式，令 是能使x+1被p(x)整除的最小正整数，并令n是m和的最小公倍数 n=LCM(m,)=m则对于任何正整数m，都存在一个长n=m的纠正m长定段突发错误的伯顿码，由下式生成,此码的校验位数目是2m，是 m,(2)m循环码。每个码矢包括 个分组。为了证明由上述生成式产生的伯顿码可以纠正全部局限在m位长的单个分组内的定段突发错误，只要证明没有这样的两个突发存在于此码标准阵列的相同陪集中的充分必要性。,对纠正m长定段突发错误的伯顿码交错，产生的(n,k)交错码可纠正任何限制在个相邻分组内的定段突发错误将

18、纠正m长定段突发错误的个码矢排列成为矩阵的行。此时将每行的一个分组作为一个单元，则阵列包含 列，每列包含个分组，将矩阵按列发送，每次从每行中发送一个分组。所以在交错码中，一个码矢包括个 分组。任何局限在 个分组的定段突发错误无论从何处开始，对每行的影响都不会多于一个分组。若按行对接收阵列进行译码，则此定段突发能够被纠正。若此交错码用作纠（(1)m+1）长突发错误码，则纠突发错误效率为,13.4 伯顿码,13.4.2 伯顿码的性能,当趋于无穷大时，伯顿码的纠突发错误效率趋于1，即。因而将伯顿码交错，可以得到一类渐近最佳的纠突发错误码。当值较大时，交错的伯顿码比具有同样纠突发错误能力的法尔码更有效

19、。实现将伯顿码交错的简便方法是组成编码阵列，按行编码和译码。因此，交错码的编码器包括原码编码器和用作存贮编码阵列行矢量的缓冲器。交错码的译码器包括原码译码器和用作存贮接收编码阵列的缓冲器。,纠突发错误卷积码分为B1型码和B2型码两类。从纠正突发错误能力的角度，B1型码作用于码元、B2型码则作用于码段，类似于分组码中的纠定段突发错误码，可以认为是B1型码的特例。假设（n0,k0,m）B1型码的纠突发错误的能力为b1，则它的纠B2型突发错误的能力b2为(13.17)若(n0,k0,m)B2型码的纠突发错误的能力为b2=n0，则它的纠B1型突发错误的能力b1为(13.18),13.5 纠突发错误卷积

20、码,如果将连续两个突发错误之间的无误区间定义为防护区间，则对于不同型的码要求有不同的防护区间。如果译码约束长度是n0(m+1)，则B1型码的防护区间长度f1为(13.19)而B2型码所要求的防护区间长度f2则为(13.20)B1型码和B2型码都属于无误纠突发错误码，能纠正长度分别 b1和 b2的全部突发错误。纠突发错误卷积码通常都是指无误纠突发错误码。还有一类纠突发错误卷积码，虽然不能纠正长度 b的所有突发错误，但能纠正其中绝大部分错误，即能以很小的译码错误概率纠正长度 b的突发错误，这类码称为有误纠突发错误码。,13.5 纠突发错误卷积码,定理13.6（n0,k0,m）卷积码纠突发错误能力为

21、b的充要条件是：其校验矩阵H中，由任意相邻b列为一组的互不相交的两组，它们列的任意线性组合不能为0，且其中一组至少有一列在H矩阵中的首n0列中选取。定理13.6表明，两个不重叠的长度 b的突发，其中一个突发从第0码段开始，则它们共同组成的错误图样，与H矩阵相乘所得的伴随式不能为0。也即要求不同的突发错误图样具有不同的伴随式，才能保证译码器能正确区分两个不同的突发，从而进行正确的判决。,13.5 纠突发错误卷积码,定理13.7对一个纠突发能力为b的有限记忆的二进制线性码，其防护区间f、纠突能力b和码率R之间必满足(13.21)例如对纠突发能力为b的(n,k)线性分组码，f=n b，则可以解得，对

22、于有误纠突发错误码，f,b和R之间必须满足下式：(13.22),13.5 纠突发错误卷积码,在式（13.21）和（13.22）中，能使等号成立的码，称为最佳纠突发错误码，简称为最佳码。寻找和构造最佳或接近最佳纠突发错误卷积码的方法：采用交错技术，由约束长度较短的最佳码得到约束长度较长的最佳码。利用分析法构造纠单个突发错误的最佳码，如岩垂码。确定突发位置然后予以纠正，即纠突发删除码，这类码属有误纠突发错误卷积码。在同样的码率和纠错能力下，有误纠突发错误卷积码所要求的防护区间比无误纠突发错误卷积码要小得多。因此，在突发错误较为严重的信道中，采用有误纠突发错误卷积码通常能取得更好的效果,13.5 纠

23、突发错误卷积码,岩垂（Iwadare）码是一种较为实用的纠突发错误卷积码，属于（n0,n0 1,m）B1型纠突发错误卷积码。特点是译码较为简单，并且当n0较小时接近最佳码。岩垂码的n0 1个子生成元为（13.23)其中(13.24)为整数。当i=1时，上式中的b(1)达到最大，此时(13.25)码的约束度为m=b(1)，能纠正长度为b1=n0的B1型突发错误，要求的防护区间为(13.26),13.6 岩垂码,H矩阵的首n0列构成了B0阵，一旦B0阵确定，则H矩阵也就确定了。由式（13.23），岩垂码B0阵的首n0 1列中的每列只有两个1，其位置是a(i)和b(i)，第n0列中只有一个1处于第0

24、行即首行。由此B0阵构成的H矩阵，与长度 n0的任何突发错误图样相乘所得的伴随式均不相同，且不为0，满足定理13.6的要求，因此能够纠正任何长度 n0的单个突发错误。,13.6 岩垂码,例13.2 设=1，n0=3，k0=2，m=8，构造一个(3,2,8)岩垂码，能够纠正长度为b1=n0=3个码元的任何单个突发错误。分析此岩垂码的编译码方式。解 码的两个子生成元为：H矩阵为,13.6 岩垂码,H矩阵的n0(3)列构成了B0阵，阵的前两列中只有两个1，分别位于由a(i)和b(i)决定的行，也即第3、第8行和第1、第7行；而第3列只有一个1，位于第0行。长度为n0=3比特的B1型突发错误图样共有3

25、种情况：,13.6 岩垂码,对应的伴随式分别为,13.6 岩垂码,由伴随式S1可知，构成了对e01码元位的两个正交校验和，构成了对e02码元位的两个正交校验和。,对E2错误图样而言，虽然 能构成对e02码元位正交的两个校验和，但 却不能构成对e01码元位正交的两个校验和。同样，对E3错误图样而言，也不能从 和 构成对e12和e11的两个正交校验和。因此采用一次大数逻辑译码的方法无法纠正B1型码的长度为3的单个突发图样。必须进行分段大数逻辑译码。由H矩阵的表达式可得,13.6 岩垂码,构成对第一码段第2信息比特e12的两个正交校验和式。,用上两式的大数判决结果对该码元进行纠错后，该子分组在译码器

26、中进入第0码段位置，由于第2信息元已纠错，错误对该信息元的影响已消除，所以由H矩阵的第4行和第9行可得它们构成了对第0段码第1个信息比特e01的两个正交校验和式，利用大数准则对该信息比特进行纠错。因此采用这种二次分段大数逻辑译码后，就实现了对e01和e02的纠错。一般而言，n0 1个信息比特中的错误，可以用n0 1次分段大数逻辑译码方法译码。,13.6 岩垂码,（3,2,8）岩垂码的译码器原理图如图13.2所示。,13.6 岩垂码,图13.2（3，2，8）岩垂码译码器,（3,2,8）岩垂码的译码步骤（1）将输入R(D)中的每一段的前两个信息元送入编码器求出新的校验元，与后面输入的校验元进行比较

27、，得到相应的伴随式分量，送入伴随式寄存器。（2）如果与门A2输出1，则表明第1码段的第2个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。（3）如果与门A1输出1，则表明第0码段的第1个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。,13.6 岩垂码,用这种分段大数逻辑译码方法能够纠正约束长度内的任意的长度 的突发错误。当=1时，岩垂码的防护区间与纠突发能力之比为对于R=(n0 1)/n0的最佳B1型码而言，由式（13.21）可知,13.6 岩垂码,对纠正b长突发错误的循环码的译码方法基于如下事实：令r(x)是接收矢量，e(x)是错误矢量，r(x)的伴随式为 如果e(

28、x)的错误限制在r(x)的b个高阶校验位 上，则 s(x)的b个高阶位 与e(x)错误一致，且s(x)的nkb个低阶位 为0。设e(x)的错误局限在r(x)的某b个相邻位上（包括首尾相接情况）。则r(x)经过i次循环移位后，错误被移位到r(x)的第i次移位r(i)(x)的 位上。令 si(x)是r(i)(x)的伴随式，则si(x)的前b个高阶位与错误一致，且si(x)的nkb个低阶位是0。,13.7 纠突发错误循环码的译码,基于以上分析所设计的捕错译码器如图13.3所示。,13.7 纠突发错误循环码的译码,译码步骤步骤1：门1打开，门2和门3关闭。将接收矢量r(x)全部移入伴随式寄存器，形成伴

29、随式s(x)，同时将r(x)的k位接收信息数字存入缓冲寄存器中。步骤2：门1打开，门2和门3关闭。伴随式寄存器开始移位。到最左边nkb级仅包含0时，最右边的b级就包含突发图样，可用于实现纠错。分别考虑以下3种情况。步骤3：如果第i次移位之后，0 i n k b，伴随式寄存器的最左边n k b级包含0，则突发e(x)的错误限制在r(x)的校验部分。因此缓冲器中k位接收信息数字是无错的。然后门3打开，缓冲器中k位无错信息数字移出，送到信宿。如果在伴随式寄存器的前n k b次移位期间，伴随式寄存器的最左边n k b级从未包含0，则突发不是限制在n k个校验位上。,13.7 纠突发错误循环码的译码,步

30、骤4：若伴随式寄存器第nkb+i次移位后，最左边nkb级包含0，则突发限制在r(x)的xni,xn1,x0,xbi1 位。从右端数起，伴随式寄存器第b,(b1),(bi+1)级中的位与r(x)的xni,xn2,xn1 位上的错误比特相对应。此时，时钟从nkb+i+1开始计数。门1关闭，伴随式寄存器移位。一旦时钟计数到nk，伴随式寄存器中最右端i位比特就与缓冲寄存器中首i位接收信息数字的相对应。然后门2和门3打开。接收信息从缓冲寄存器中读出并进行纠正。步骤5：若伴随式寄存器已移位nk次，而最左边nkb从未全含0，则门3打开，数字从缓冲寄存器一次一个读出。同时门1打开，伴随式寄存器移位。一旦伴随式

31、寄存器最左边nkb级包含0，其最右边b级内容就与将从缓冲寄存器输出的b位接收数字中的错误对应。然后门2打开，错误信息用伴随式寄存器输出（门1关闭）的数字进行纠正。,13.7 纠突发错误循环码的译码,13.7 纠突发错误循环码的译码,当k位信息已从缓冲器输出而伴随式寄存器最左边nkb级从未全含0，则查出长度b的突发或不能纠正突发。上述译码器仅能纠正长度b的突发，错误图样数目是n2b-1，当n较大时，它仅是2n-k个可纠正错误图样的一小部分。改进的译码器能纠正所有长度nk的突发错误，原理如下：接收矢量先全部移入伴随式寄存器。纠错之前伴随式寄存器循环移位n次。循环移位期间，记录出现在伴随式寄存器最右

32、边b级中最短突发的长度b。这个突发被认为是信道造成的错误突发。然后译码器便开始纠正过程。伴随式寄存器又开始移位。一旦最短的突发在伴随式寄存器最右边b级中，译码器便按上述方法进行纠正。此译码方法是Gallager提出的纠正突发错误码的最佳译码。,实际通信系统中绝大部分信道是随机错误和突发错误并存，需要能同时纠正这两种错误的码。交错技术就是可以构造这种码的一种好办法。把纠t个随机错误的(n,k)码进行度交织，得(n,k)码，能纠t个长或更短突发的任何组合，它显然具有纠随机和突发错误的能力。有些码本来就能纠这两种错误，交错后纠错能力也可提高。本节将进一步讨论由已知码导推出新码，并用作纠随机和突发错误

33、的其它一些方法。,13.8 纠突发和随机错误码,循环乘积码的编码规则考虑两个线性分组码c1=(n1,k1),c2=(n2,k2)。按图13.4构成一个新码，称为c1和c2的乘积码c=c1c2=(n1 n2,k1 k2)，首先，选c1码中的k2个码字排成k2行，再把其中的每一列当作c2的消息位，根据c2码的编码规则求出每一列中余下的n2 k2个校验数据。图中左下角的校验数据，则既可以用c1码的也可以用c2码的校验规则来计算，两者的结果是一致的。,编完k2个c1码再计算列校验（包括校验位的校验）或编完k1个c2码，再计算行校（包括校验位的校验）,图13.4 乘积码编码规则,乘积码的主要性能定理13

34、.8 若(n1,k1)线性分组码c1和(n2,k2)线性分组码c2的最小距离分别为d1和d2，则乘积码(n1n2,k1k2)码的最小距离为d1d2。证明：线性分组码的积码仍是线性分组码，因而只需证明(n1n2,k1k2)线性积码的非零码字的重量 d1d2即可。存在有(n1n2,k1k2)码的一个非零码字，它的非零行是(n1,k1)码的最小重量非零码字，它的非零列是(n2,k2)码的最小重量非零码字，则此码字必是积码c1c2的最小重量非零码字，因为除此以外的非零码字的重量一定不是最小的。而这个积码码字的重量正好是d1d2。证毕。,定理13.9 设d1和d2分别是线性码c1和c2的最小距离，则 积

35、码c1c2能纠正 个随机错误的任何组合，同时能纠正长b max n1t2,n2t1的突码错误，其中证明：只要证长 b的突发错误和有 t随机错误的图样不在积码标准阵列的同一陪集中即可。不失一般性，可设 n1t2 n2t1，则b=n1t2。,(续)若有一个长度 n1t2的突发，当把它排成一个n2行n1列的阵列时，每列至多含有t2个错误：,若该突发和某个有 t个随机错误的图样在积码的同一陪集中，则这两个错误图样的和是积码的一个码阵。因为c2的最小距离是d2,因此码阵中每一列至少有d2个非零分量（全0的一列除外）；和阵中每一个非零分量的列，至少含有随机错误图样中的d2 t2个错误，以及至多含有突发错误

36、图样中的t2个错误。,(续)由于至多只有t个随机错误，至多能分布在 个列中，因此和阵中至多含有 t2+t 个非零分量。,但是 2 t（d2 2t2）,因此和阵中仅含有少于2td1d2个非零分量，它不可能是乘积码的一个码阵。前面假设b=n1t2或更短的突发与有t个随机错误的图样在同一陪集的假设不成立，不能在积码的标准阵列的同一陪集中。所以两者都可作陪集首，都是可纠正的错误图样。证毕。,乘积码的传送顺序及译码乘积码有两种传输数据的方法：一是按行的次序逐行传送，或按列自左至右逐列传输；另一是按码阵的对角线次序传送数据。后者传输方法所得到的码与前者是不一样的。若乘积码以行或列的次序逐行传输，则译码时可

37、先以行按c1码，后按列以c2码进行译码，也可以先以列按c2码译码，后再以行按c1码译码；因此需要两级译码。可知乘积码译码器的复杂性完全决定于行码和列码译码器的复杂性，以及n1n2存储器的大小。由于乘积码纠错能力很强，因此得到很大发展，例如可以从二维扩展到多个子码组成的多维乘积码，以及由一般乘积码扩展到循环乘积码等。,随着码长n的增加，译码错误概率按指数接近于零。因此为使码有效就必须用长码。但译码器复杂性和计算量也相应增加以致难以实现。为解决这一矛盾，福尼提出了级联码的概念，把编制长码的过程分几级完成，通常分两级。级联码的应用见图13.5。,图13.5 应用级联码的通信系统,级联码构造(图13.

38、5)假定在内信道上使用的是码c1，在外信道上使用的是码c2，c2称为外码，c1称为内码。所以是(n1n2,k1k2)码，其中n1,k1和n2,k2分别是码c1和c2的长度和消息位数。一般c2是(n2,k2)的R-S码，而c1是(n1,k1)的二元码。编码时先将k1k2个消息数字分成k2个二元k1重，这k2个二元k1重按R-S码编码规则编码，转换成n2个k1重。然后，对每个k1重按c1码的规则编码，将每个k1重转换成一个n1重。译码时则先对c1码译码，再对c2码译码。若遇少量的随机错误，则内码c1就可纠正；若遇较长的突发错误，则这种突发错误纠能由纠密集型突发错误能力很强的R-S码所纠正。,本章小

39、结,本章讨论纠突发错误码。法尔码、伯顿码都是目前应用较多的纠突发错误码。乘积码和级联码则能够有效地抵抗随机错误和突发错误混杂的干扰。本章还介绍了纠突发错误卷积码的基本概念，以及在实际中应用较多岩垂码。,习题,1.若(n,k)循环码要纠正所有长度 b，同时检测所有长度 l且 b的突发，证明校验位n k b+l。2.证明纠正一个错误和检查两个错误的汉明码能纠正任何长度小于等于2（b=2）的单个突发。3.假定长为15的纠正一个错误并检查两个错误的汉明码用于纠正长度 2的突发，设计该码的捕错译码器。4.令p(x)为5次本原多项式。求纠正任何长度5的单个突发的法尔码生成多项式。码长是多少？构造该码的捕错译码器。5.令m=5，构造一伯顿码，能纠正任何局限在一个5位长分组内的定段突发。假设该码按交错度=5交错，求该码的长度、校验位数目、以及纠突发错误能力各是多少？,