《纠突发错误码》PPT课件.ppt

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

1、东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件第十三章纠突发错误码第十三章纠突发错误码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件本章内容提要本章内容提要纠纠突发错误码的定义和基本性质突发错误码的定义和基本性质法尔码法尔码交错码交错码伯顿码伯顿码纠突发错误卷积码纠突发错误卷积码岩垂码岩垂码纠突发错误循环码的译码纠突发错误循环码的译码纠突发和随机错误码纠突发和随机错误码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件大部分实际信道如短波大部分实际信道如短波、散射散射、有线等信道中产生的有线等信道中产生的错误是突发

2、性的；某些数据存储系统所产生的错误，错误是突发性的；某些数据存储系统所产生的错误，大部分也是突发性的，而不是随机性的。大部分也是突发性的，而不是随机性的。这些这些信道中所产生的错误是突发错误，或突发错误与信道中所产生的错误是突发错误，或突发错误与随机错误并存，通常称这类信道为突发信道随机错误并存，通常称这类信道为突发信道。循环码循环码检测突发错误能力强，但纠错效果不大检测突发错误能力强，但纠错效果不大。人们希望能设计出一类专门用作纠突发错误的码，这人们希望能设计出一类专门用作纠突发错误的码，这类码称为纠突发错误码。类码称为纠突发错误码。这类码在纠突发错误时的效率应比对付随机错误而设这类码在纠突

3、发错误时的效率应比对付随机错误而设计的码要高计的码要高，即对于给定的，即对于给定的n和和k， (n, k)有尽可能小有尽可能小的多余度，或者说的多余度，或者说n k 尽可能小尽可能小。第第1313章纠突发错误码章纠突发错误码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定义定义13.1 长为长为b的突发是针对错误图样来定义的突发是针对错误图样来定义的：如果一个矢量的非零分量局限于的：如果一个矢量的非零分量局限于b个连续个连续数据位，且第一和最后一位是非零的，则数据位，且第一和最后一位是非零的，则称该称该矢量为一个长为矢量为一个长为b的突发的突发。一个线性码如能纠正长

4、为一个线性码如能纠正长为b或更短的突发错误，或更短的突发错误，但不能纠正长为但不能纠正长为b+1的所有突发错误，则的所有突发错误，则称此称此码是一个纠码是一个纠b长突发错误码，即该码的纠错能长突发错误码，即该码的纠错能力为力为b。 13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.1 定义定义 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.1 长长n的二元码字中，突发长度不大于的二元码字中，突发长度不大于b 的码字的码字的总数的总数N=2b-1(n+2 b) 。证明证明 在长在长为为n的二元码字中，考虑的二元码字中，考虑b为各种可能

5、值的情为各种可能值的情况况 （突发字个数）如下：（突发字个数）如下：b = 0 1个个 （0, 0, , 0） 1 n个个 2 n 1个个 3 2(n 2)个个 13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 证毕。证毕。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.2 一个一个 (n, k) 线性分组码，线性分组码，能发现长度不大于能发现长度不大于b的错误图样的条件是的错误图样的条件是n k b 1 + lb(n + 2 b) 证明证明 由于对于所有的错误图样，若由于对于所有的错误图样，若s0则能被发现，则

6、能被发现，(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.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课

7、件课件定理定理13.3 一个（一个（n, k）线性码能纠正所有长度线性码能纠正所有长度 b的突的突发错误的充要条件是：长度发错误的充要条件是：长度 2b的突发不是一个码字。的突发不是一个码字。证明证明假设存在一个长假设存在一个长 2b的突发的突发v是一个码字，则是一个码字，则 v = u + w ，其中其中 u、w都是长度都是长度 b的突发。的突发。必要性必要性：若：若v是码字，因任意一陪集只有一个错误图样，则是码字，因任意一陪集只有一个错误图样，则u和和w必在同一陪集中。设必在同一陪集中。设u为陪集首，则陪集中每一个字的错误都是为陪集首，则陪集中每一个字的错误都是此陪集首，此陪集首，w必为不

8、可纠错误，否则不可能与必为不可纠错误，否则不可能与u同在一个陪集。这同在一个陪集。这样尽管样尽管v是一是一“码字码字”，但它是一个错码，与假设，但它是一个错码，与假设v是一码字矛盾，是一码字矛盾，因此把因此把u作为陪集首来纠错也是无效的，即它不能纠正所有长作为陪集首来纠错也是无效的，即它不能纠正所有长 b 的突发错误。的突发错误。充分性：充分性：若长度若长度 2b的突发的突发v不是码字，则不是码字，则u、w不在同一陪集中，不在同一陪集中，若它们都是陪集首，则都是可以纠正的长若它们都是陪集首，则都是可以纠正的长 b 的突发错误。的突发错误。 13.1纠突发错误码定义和基本性质纠突发错误码定义和基

9、本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理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(n+22b) 1 ，代入定理代入定理13.4得得 n-k 2b 。表述为：表述为：(1) 一个一个(n, k)线性分组码，若要纠正所有长度线性分组码，若要纠正所有长度 b的突发错误，

10、则应的突发错误，则应n k 2b。 (2)（n, k）码的纠突上限为码的纠突上限为 ，称为赖格尔限。，称为赖格尔限。 满足赖格尔限的码是最佳的。满足赖格尔限的码是最佳的。 (3) 比率比率z=2b/(n k)被用来衡量码的纠突发错误的效率，被用来衡量码的纠突发错误的效率，最佳码纠突发错误的效率等于最佳码纠突发错误的效率等于1。 13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.5 （n, k）循环码能检测长循环码能检测长 n k的任何突发的任何突发错误，错误，包括首

11、尾相接包括首尾相接的突发错误。的突发错误。 证明：证明：设错误图样设错误图样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)产生的产生的伴随式不为零伴随

12、式不为零。即一个。即一个(n, k)循循环码能检测长环码能检测长 n k的任何突发错误。的任何突发错误。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件对于长度对于长度 n k的突发错误图样，当它的错误局限在前的突发错误图样，当它的错误局限在前i位和后位和后l i位时，即位时，即出现首尾相接的错误时出现首尾相接的错误时，有，有13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 如果将它乘以如果将它乘以 xl - i ,则则 由于它的由于它

13、的次数小于次数小于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的首尾相接的突发错误。证毕。的首尾相接的突发错误。证毕。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件法尔码是最早也是最大的一类法尔码是最早也是最大的一类用分析方法构造用分析方法构造出的纠单个突发错误的二进制循环码出的纠单个突发错误的二进制循环码。 由于可以根据

14、不同的要求很方便地设计所由于可以根据不同的要求很方便地设计所需要的码，译码也很简单，因此法尔码是一类需要的码，译码也很简单，因此法尔码是一类比较实用的，也是比较实用的，也是最基本的纠单个突发错误循最基本的纠单个突发错误循环码环码。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定义定义13.2 设设p(x)是是GF(2)上的上的m次既约多项式次既约多项式，令，令是使是使p(x) 整除整除x+1的最小整数，称的最小整数，称为为p(x)的的周期周期；令；令b是使是使b m且且2b 1不能被不能被整除的正整数，则整

15、除的正整数，则由生成多项由生成多项式式g(x)=(x2b 1 +1) p(x) 生成的码称为法尔码生成的码称为法尔码。法尔码能纠正法尔码能纠正b长的突发错误长的突发错误码的长度码的长度n等于等于和和2b 1的最小公倍数，即的最小公倍数，即n=LCM2b 1, 码的校验位数是码的校验位数是 m + 2b + 1。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件证明证明 只要证明只要证明长度长度 b的任何突发都位于码的不的任何突发都位于码的不同陪集中同陪集中，这样它们便能作为陪集首而成为可，这样它们便能作为陪集首

16、而成为可纠正的错误图样。纠正的错误图样。令令x iA(x)和和x jB(x)分别表示两个长为分别表示两个长为b1和和b2突发突发的多项式，且的多项式，且b1 b ，b2 b ，而而 13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 如果假定如果假定xiA(x)和和xjB(x)在在码的同一陪集中码的同一陪集中，那么多项式，那么多项式 v(x) = xiA(x)+xjB(x) (13.4)必是一个码多项式必是一个码多项式。不失一般，假定。不失一般，假定i

17、j，用用2b 1除除j i得得 (13.5)把式（把式（13.5）代入式（）代入式（13.4），那么），那么v (x)可表示为可表示为 (13.6)东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 根据假定根据假定v (x)为码多项式，而循环码为码多项式，而循环码的生成多项式为的生成多项式为 g(x) = (x2b 1 +1 ) p(x)，所以所以(x2b 1+1 )|v(x)。由于由于(x2b 1+1 )| xq(2b 1)+1 ，因此式因此式( (13.6) )中的中的 或能被整除或或能被整除或等于零。等于

18、零。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 假定假定 (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

19、)又因又因b11 0，由式由式( (13.9) )可得可得b b11 + d ，故有故有 b d (13.10)东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 从从式式(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

20、 i = q(2b 1) (13.12)把式（把式（13.11）和（）和（13.12）代入式（）代入式（13.4）可得）可得( (13.13) ) 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 注注意意到到B(x)的的次次数数小小于于b，所所以以 。因因此此，B(x)和和p(x)互互素素。已已假假定定v(x)是是码码多多项项式式，所所以以xj i +1必必能能被被p(x)整整除除，ji必必为为p(x)的的周周期期 的的整整数数倍倍。但但由由式式(13.12)知知，ji也也是是2b1的的整整数数倍倍。由由此此

21、，ji必必是是n=LCM2b1, 的的倍倍数。显然，因为数。显然，因为j和和i都小于都小于n，所以这是不可能的。所以这是不可能的。综综上上所所述述，长长度度 b的的两两个个突突发发xiA(x)和和xjB(x)在在同同一一个个陪陪集集中中的的假假设设是是不不对对的的。因因此此所所有有长长度度 b的的突突发发都都处处在在 g(x) = =(x2b 1+1)p(x)定定义义的的g(x)生生成成的的法法尔尔码码的的不不同同陪陪集集中中，因因而而它它们们是是可可纠纠正正的的错错误误图图样样。由由于于码码是是循循环环的的，所所以以它它亦亦能能纠正长度纠正长度 b的首尾相接的突发错误。的首尾相接的突发错误。

22、 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件例例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的任的任何突发错误。何突发错误。13.

23、2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件法尔码的纠突发错误的效率为法尔码的纠突发错误的效率为 若若b等于等于m，则有则有 当当m的值较大时，的值较大时，z约等于约等于2/3。因此，相对于赖格尔限。因此，相对于赖格尔限而言，法尔码的效率并不是很高。而言，法尔码的效率并不是很高。能能够够纠纠正正任任何何长长度度为为b或或更更少少的的突突发发错错误误、并并同同时时检检测测长为长为l b的任何突发的法尔码，可用下式生成：的任何突发的法尔码，可用下式生成： 该码长度等于该码长度等于和和b + l 1的最小公倍数。的最

24、小公倍数。 13.2法尔码法尔码13.2.2 法尔码的性能法尔码的性能 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件交错是一种非常交错是一种非常简单简单而又而又有效有效的构造码的构造码的方法，它可以大大提高纠随机错误码的方法，它可以大大提高纠随机错误码的纠突发错误能力，可的纠突发错误能力，可使抗较短使抗较短突发错突发错误的码误的码变成抗较长变成抗较长突发错误的码，使纠突发错误的码，使纠正正单个定段单个定段突发错误的码突发错误的码变成纠多个定变成纠多个定段段突发错误的码。突发错误的码。这种方法所付出的这种方法所付出的代价代价是增加存储设备是增加存储设备和加大通信时延

25、。和加大通信时延。13.3交错码交错码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件将将 个个 (n, k) 码的码矢排成码的码矢排成 n的矩形阵列，每行一个的矩形阵列，每行一个码矢，然后码矢，然后按列送至通信信道按列送至通信信道，在收端恢复矩形阵列，在收端恢复矩形阵列的排列次序，就构成交错度为的排列次序，就构成交错度为 的交错码。即给定一个的交错码。即给定一个 (n, k) 循环码，用交错法将码长扩大循环码，用交错法将码长扩大 倍，信息位数目倍，信息位数目也扩大了也扩大了 倍，倍，构成一个（构成一个（ n, k）循环码循环码，见图，见图13.1。 13.3 交错码

26、交错码13.3.1 交错码的编译码方法交错码的编译码方法 图图13.1 交错码的编码方法，其中交错码的编码方法，其中为交错度为交错度东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件实现交错码的简明方法是排出阵列，按行编码和译码。一实现交错码的简明方法是排出阵列，按行编码和译码。一般地说，这并不是最简单的实现方法。般地说，这并不是最简单的实现方法。最简单的实现方法是基于这样一个事实，即若最简单的实现方法是基于这样一个事实，即若原码是循环原码是循环的，则交错码也是循环的的，则交错码也是循环的。如果原码的生成多项式是如果原码的生成多项式是g (x)，则交错码的生成多项式是则

27、交错码的生成多项式是g (x )。因此，可用因此，可用移位寄存器完成编码和纠错移位寄存器完成编码和纠错。只要简单地将原码译码器的每个移位寄存器用只要简单地将原码译码器的每个移位寄存器用 级置换，级置换，即可根据原码的译码器推导出交错码的译码器，而不必改变即可根据原码的译码器推导出交错码的译码器，而不必改变其他连接。其他连接。所以，如果原码译码器较简单，则交错码也同样简单，而所以，如果原码译码器较简单，则交错码也同样简单，而对于短码而言，原码译码器通常是比较简单的。对于短码而言，原码译码器通常是比较简单的。 13.3 交错码交错码13.3.1 交错码的编译码方法交错码的编译码方法 东南大学移动通

28、信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件交错码的性能交错码的性能（1）交错编码）交错编码使错误分散使错误分散，长，长 的任何突发无论从何处开始，的任何突发无论从何处开始，都至多只能影响每行中的一位。都至多只能影响每行中的一位。（2）当且仅当每行中的错误图样是原（）当且仅当每行中的错误图样是原（n, k）码中可纠正的码中可纠正的图样时，此错误图样图样时，此错误图样对整个阵列来说才是可纠正的对整个阵列来说才是可纠正的。（3）若原码能纠正）若原码能纠正 b的任何单个突发，则交错码能纠正的任何单个突发，则交错码能纠正 b 的任何单个突发，的任何单个突发，码长扩大码长扩大 倍，纠突能

29、力也扩大倍，纠突能力也扩大 倍。倍。 若若 (n, k) 码有最大可能的纠正突发错误能力，即码有最大可能的纠正突发错误能力，即nk2b=0，则交错码则交错码 ( n, k)也具有最大可能的纠正突发错误也具有最大可能的纠正突发错误能力。交错具有最大纠正突发错误能力的短码，能够构成能力。交错具有最大纠正突发错误能力的短码，能够构成实际上任意长的、具有最大可能纠突发错误能力的码。实际上任意长的、具有最大可能纠突发错误能力的码。13.3 交错码交错码13.3.2 交错码的性能交错码的性能 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.3 交错码交错码13.3.2 交错

30、码的性能交错码的性能 （4）若）若原码是循环的原码是循环的，其生成多项式为，其生成多项式为g(x)，则则交错码也交错码也是循环的是循环的，且生成多项式为，且生成多项式为g (x )。 证明证明 设经设经 次交错后得到的码是次交错后得到的码是 (13.14)它的输出方式与图它的输出方式与图13.1相同，其中相同，其中 ，所以有所以有 ，即它们都是循环码，即它们都是循环码 (g (x)中的码矢量。中的码矢量。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.3 交错码交错码13.3.2 交错码的性能交错码的性能 如果把上述（如果把上述（ n, k）线性分组码循环移位

31、一次，得线性分组码循环移位一次，得 (13.15)显然，其中的每一行仍是显然，其中的每一行仍是(g (x)的码矢量。所以这个（的码矢量。所以这个（ n, k）线性分组码是个循环码。线性分组码是个循环码。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.3 交错码交错码13.3.2 交错码的性能交错码的性能 若把式若把式( (13.14) )的循环码用多项式表示，则其码多项式为的循环码用多项式表示，则其码多项式为 式中东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.3 交错码交错码13.3.2 交错码的性能交错码的性能 （5）交交错

32、错技技术术把把寻寻求求长长而而有有效效的的纠纠突突发发错错误误码码这这个个问问题题，简化为寻求好的短码简化为寻求好的短码。（6）交错码需增加）交错码需增加存储设备存储设备，加大，加大通信时延通信时延。交交错错是是一一种种时时间间扩扩散散技技术术，它它使使信信道道突突发发错错误误的的相相关关性性减减小小。当当足足够够大大时时可可将将突突发发错错误误离离散散为为随随机机错错误误，从从而而可可用用纠纠随随机机错错误误码码来来纠纠突突发发错错误误。因因此此交交错错技技术术在在短短波波、散射、有线等有记忆的信道中得到了广泛的应用。散射、有线等有记忆的信道中得到了广泛的应用。（7）交交错错技技术术是是一一

33、种种等等效效长长码码的的技技术术。根根据据Shannon第第二定理，必然有更好的性能。二定理，必然有更好的性能。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件伯顿发现一类纠正定段突发错误的循环码。考虑一伯顿发现一类纠正定段突发错误的循环码。考虑一(n, k)码，码，码长码长n是整数是整数m的倍数，如的倍数，如n = m。码多项式表示如下码多项式表示如下定义下式的定义下式的m个相邻码位个相邻码位vi m, vi m + 1, , v ( i+ 1) m 1 为一个分组，其中为一个分组，其中0 i 。因此其码矢由因此其码矢由 个分组组成。个分组组成。当且仅当长度等于或小

34、于当且仅当长度等于或小于 m的突发局限在的突发局限在 个相邻分组内时，个相邻分组内时，称此突发为定段突发，称此突发为定段突发， 是小于是小于 的正整数。的正整数。一个长一个长n = m可纠正全部限制在等于或小于可纠正全部限制在等于或小于 个分组内的定个分组内的定段突发错误的线性码，称为纠段突发错误的线性码，称为纠 m长定段突发错误码。长定段突发错误码。长为长为 ( 1) m +1的突发不论从何处开始，最多只影响的突发不论从何处开始，最多只影响 个个分组，显然，纠分组，显然，纠 m长定段突发错误码能够纠正任何长度等长定段突发错误码能够纠正任何长度等于或小于于或小于( 1 ) m +1的单个突发错

35、误。纠的单个突发错误。纠 m长定段突发长定段突发错误码可当作纠错误码可当作纠( 1) m +1长单个突发错误码使用。长单个突发错误码使用。13.4 伯顿码伯顿码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定义定义13.3 令令p(x)是是m次既约多项式，令次既约多项式，令 是能使是能使x +1被被p(x)整除的最小正整数，并令整除的最小正整数，并令n是是m和和 的最小公倍数的最小公倍数 n = LCM (m, ) = m则对于任何正整数对于任何正整数m，都存在一个长都存在一个长n = m的纠正的纠正m长定段突发错误的伯顿码，由下式生成长定段突发错误的伯顿码，由下式

36、生成13.4 伯顿码伯顿码13.4.1 伯顿码的构造伯顿码的构造 此码的校验位数目是此码的校验位数目是2m，是是 m, ( 2)m 循环码。循环码。 每个码矢包括每个码矢包括 个分组。为了证明由上述生成式产生的个分组。为了证明由上述生成式产生的伯顿码可以纠正全部局限在伯顿码可以纠正全部局限在m位长的单个分组内的定段突位长的单个分组内的定段突发错误，只要证明没有这样的两个突发存在于此码标准阵发错误，只要证明没有这样的两个突发存在于此码标准阵列的相同陪集中的充分必要性。列的相同陪集中的充分必要性。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件对纠正对纠正m长定段突发错

37、误的伯顿码交错，产生的长定段突发错误的伯顿码交错，产生的( n, k)交错码交错码可纠正任何限制在可纠正任何限制在 个相邻分组内的定段突发错误个相邻分组内的定段突发错误将纠正将纠正m长定段突发错误的长定段突发错误的 个码矢排列成为矩阵的个码矢排列成为矩阵的 行。此时行。此时将每行的一个分组作为一个单元，则阵列包含将每行的一个分组作为一个单元，则阵列包含 列，每列包含列，每列包含 个分组，将矩阵按列发送，每次从每行中发送一个分组。所以个分组，将矩阵按列发送，每次从每行中发送一个分组。所以在交错码中，一个码矢包括个在交错码中，一个码矢包括个 分组。分组。任何局限在任何局限在 个分组的定段突发错误无

38、论从何处开始，对每行个分组的定段突发错误无论从何处开始，对每行的影响都不会多于一个分组。若按行对接收阵列进行译码，则的影响都不会多于一个分组。若按行对接收阵列进行译码，则此定段突发能够被纠正。若此交错码用作纠（此定段突发能够被纠正。若此交错码用作纠（( 1) m+1）长突发错误码，则纠突发错误效率为长突发错误码，则纠突发错误效率为13.4 伯顿码伯顿码13.4.2 伯顿码的性能伯顿码的性能 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件当当 趋于无穷大时，伯顿码的纠突发错误效率趋于趋于无穷大时，伯顿码的纠突发错误效率趋于1，即即 。因而将伯顿码交错，可以得到一类渐近

39、最。因而将伯顿码交错，可以得到一类渐近最佳的纠突发错误码。当佳的纠突发错误码。当 值较大时，交错的伯顿码比具值较大时，交错的伯顿码比具有同样纠突发错误能力的法尔码更有效。有同样纠突发错误能力的法尔码更有效。实现将伯顿码交错的简便方法是组成编码阵列，按行实现将伯顿码交错的简便方法是组成编码阵列，按行编码和译码。因此，交错码的编码器包括原码编码器编码和译码。因此，交错码的编码器包括原码编码器和用作存贮编码阵列行矢量的缓冲器。交错码的译码和用作存贮编码阵列行矢量的缓冲器。交错码的译码器包括原码译码器和用作存贮接收编码阵列的缓冲器。器包括原码译码器和用作存贮接收编码阵列的缓冲器。 13.4 伯顿码伯顿

40、码13.4.2 伯顿码的性能伯顿码的性能 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件纠突发错误卷积码分为纠突发错误卷积码分为B1型码和型码和B2型码两类。从纠正型码两类。从纠正突发错误能力的角度，突发错误能力的角度，B1型码作用于码元、型码作用于码元、B2型码则型码则作用于码段，类似于分组码中的纠定段突发错误码，作用于码段，类似于分组码中的纠定段突发错误码，可以认为是可以认为是B1型码的特例。型码的特例。假设（假设（n0, k0, m）B1型码的纠突发错误的能力为型码的纠突发错误的能力为b1，则则它的纠它的纠B2型突发错误的能力型突发错误的能力b2为为(13.1

41、7) 若若(n0, k0, m)B2型码的纠突发错误的能力为型码的纠突发错误的能力为b2 = n0，则它的纠则它的纠B1型突发错误的能力型突发错误的能力b1为为(13.18)13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件如果将连续两个突发错误之间的无误区间定义为防护区间，则对于不同型的码要求有不同的防护区间。如果译码约束长度是n0 (m+1)，则B1型码的防护区间长度f1为 (13.19)而B2型码所要求的防护区间长度f2则为 (13.20)B1型码和B2型码都属于无误纠突发错误码无误纠突发错误码，能纠正长度分别 b1和 b

42、2的全部突发错误全部突发错误。纠突发错误卷积码通常都是指无误纠突发错误码。还有一类纠突发错误卷积码，虽然不能纠正长度不能纠正长度 b的所有突发错误，但能纠正的所有突发错误，但能纠正其中绝大部分错误其中绝大部分错误，即能以很小的译码错误概率纠正长度 b的突发错误，这类码称为有误纠突发错误码。 13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.6 （n0, k0, m）卷积码纠突发错误能力为卷积码纠突发错误能力为b的充的充要条件是：其校验矩阵要条件是：其校验矩阵H中，由任意相邻中，由任意相邻b列为一组的列为一组的互不相

43、交的两组，它们列的任意线性组合不能为互不相交的两组，它们列的任意线性组合不能为0，且，且其中一组至少有一列在其中一组至少有一列在H矩阵中的首矩阵中的首n0列中选取。列中选取。定理定理13.6表明，两个不重叠的长度表明，两个不重叠的长度 b的突发，其中一的突发，其中一个突发从第个突发从第0码段开始，则它们共同组成的错误图样，码段开始，则它们共同组成的错误图样，与与H矩阵相乘所得的伴随式不能为矩阵相乘所得的伴随式不能为0。 也即要求不同的突发错误图样具有不同的伴随式，也即要求不同的突发错误图样具有不同的伴随式，才能保证译码器能正确区分两个不同的突发，从而进才能保证译码器能正确区分两个不同的突发，从

44、而进行正确的判决。行正确的判决。 13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.7对一个纠突发能力为对一个纠突发能力为b的有限记忆的二进制的有限记忆的二进制线性码，其防护区间线性码，其防护区间f、纠突能力纠突能力b和码率和码率R之间必满足之间必满足(13.21)例如对纠突发能力为b的(n, k)线性分组码，f =n b，则可以解得， 对于有误纠突发错误码，f, b和R之间必须满足下式： (13.22)13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件

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

46、南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件岩垂（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列构成了

47、B0阵，一旦B0阵确定，则H矩阵也就确定了。由式（13.23），岩垂码B0阵的首n0 1列中的每列只有两个1，其位置是a (i)和b (i)，第n0列中只有一个1处于第0行即首行。由此B0阵构成的H矩阵，与长度 n0的任何突发错误图样相乘所得的伴随式均不相同，且不为0，满足定理13.6的要求，因此能够纠正任何长度 n0的单个突发错误。13.6 岩垂码岩垂码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件例例13.2 设 =1，n0 =3，k0 =2，m=8，构造一个(3, 2, 8)岩垂码，能够纠正长度为b1 = n0 =3个码元的任何单个突发错误。分析此岩垂码的编译

48、码方式。解解 码的两个子生成元为： H矩阵为13.6 岩垂码岩垂码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件H矩阵的n0 (3)列构成了B0阵，阵的前两列中只有两个1，分别位于由a (i)和b (i)决定的行，也即第3、第8行和第1、第7行；而第3列只有一个1，位于第0行。长度为n0 =3比特的B1型突发错误图样共有3种情况：13.6 岩垂码岩垂码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件对应的伴随式分别为13.6 岩垂码岩垂码由伴随式S1可知， 构成了对e01码元位的两个正交校验和， 构成了对e02码元位的两个正交校验和。东南大

49、学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件对E2错误图样而言，虽然 能构成对e02码元位正交的两个校验和，但 却不能构成对e01码元位正交的两个校验和。同样，对E3错误图样而言，也不能从 和 构成对e12和e11的两个正交校验和。因此采用一次大数逻辑译码的方法无法纠正B1型码的长度为3的单个突发图样。必须进行分段大数逻辑译码。由H矩阵的表达式可得13.6 岩垂码岩垂码构成对第一码段第2信息比特e12的两个正交校验和式。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件用上两式的大数判决结果对该码元进行纠错后，该子分组在译码器中进入第0码段位置，

50、由于第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）岩垂码译码器 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码”

51、 ”课件课件（3, 2, 8）岩垂码的译码步骤译码步骤（1）将输入R (D)中的每一段的前两个信息元送入编码器求出新的校验元，与后面输入的校验元进行比较，得到相应的伴随式分量，送入伴随式寄存器。（2）如果与门A2输出1，则表明第1码段的第2个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。（3）如果与门A1输出1，则表明第0码段的第1个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。13.6 岩垂码岩垂码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件用这种分段大数逻辑译码方法能够纠正约束长度内的任意的长度 的突发错误。当 = 1时，岩垂码的防

52、护区间与纠突发能力之比为对于R = ( n0 1) / n0的最佳B1型码而言，由式（13.21）可知13.6 岩垂码岩垂码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件对纠正对纠正b长突发错误的循环码的译码方法基于如下事实：长突发错误的循环码的译码方法基于如下事实：令令r(x)是接收矢量，是接收矢量， e(x)是错误矢量，是错误矢量，r(x)的伴随式为的伴随式为 如果如果e(x)的错误限制在的错误限制在r(x)的的b个高阶校验位个高阶校验位 上，上，则则 s(x)的的b个高阶位个高阶位 与与e(x)错误一致，且错误一致，且s(x)的的nkb个低阶位个低阶位 为为0

53、。设设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 纠突发错误循环码的译码纠突发错误循环码的译码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件基于以上分析所设计的捕错译码器如图基于以上分析所

54、设计的捕错译码器如图13.3所示。所示。 13.7 纠突发错误循环码的译码纠突发错误循环码的译码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件译码步骤译码步骤步骤1：门1打开，门2和门3关闭。将接收矢量r(x)全部移入伴随式寄存器，形成伴随式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

55、)的校验部分。因此缓冲器中k位接收信息数字是无错的。然后门3打开，缓冲器中k位无错信息数字移出，送到信宿。如果在伴随式寄存器的前n k b次移位期间，伴随式寄存器的最左边n k b级从未包含0，则突发不是限制在n k个校验位上。13.7 纠突发错误循环码的译码纠突发错误循环码的译码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件步骤步骤4：若伴随式寄存器第：若伴随式寄存器第nkb+i次移位后次移位后，最左边最左边nkb级包含级包含0，则突发限制在，则突发限制在r(x)的的xni,xn1, x0, , xbi1 位。从右端数起，位。从右端数起，伴随式寄存器第伴随式寄存器

56、第b, (b1), , (bi+1)级中的位与级中的位与r(x)的的xni , xn2 , xn1 位上的错误比特相对应。此时，时钟从位上的错误比特相对应。此时，时钟从nkb+i+1开始计数。门开始计数。门1关闭，伴随式寄存器移位。一旦时钟计数到关闭，伴随式寄存器移位。一旦时钟计数到nk，伴随式寄存器中伴随式寄存器中最右端最右端i位比特就与缓冲寄存器中首位比特就与缓冲寄存器中首i位接收信息数字的相对应。然后位接收信息数字的相对应。然后门门2和门和门3打开。接收信息从缓冲寄存器中读出并进行纠正。打开。接收信息从缓冲寄存器中读出并进行纠正。步骤步骤5：若伴随式寄存器已移位：若伴随式寄存器已移位nk

57、次，而最左边次，而最左边nkb从未全含从未全含0，则门则门3打开，数字从缓冲寄存器一次一个读出。同时门打开，数字从缓冲寄存器一次一个读出。同时门1打开，伴随打开，伴随式寄存器移位。一旦伴随式寄存器最左边式寄存器移位。一旦伴随式寄存器最左边nkb级包含级包含0，其最右边，其最右边b级内容就与将从缓冲寄存器输出的级内容就与将从缓冲寄存器输出的b位接收数字中的错误对应。然后位接收数字中的错误对应。然后门门2打开，错误信息用伴随式寄存器输出（门打开，错误信息用伴随式寄存器输出（门1关闭）的数字进行纠关闭）的数字进行纠正。正。13.7 纠突发错误循环码的译码纠突发错误循环码的译码东南大学移动通信国家重点

58、实验室“ “信息论与编码信息论与编码” ”课件课件13.7 纠突发错误循环码的译码纠突发错误循环码的译码当当k位位信信息息已已从从缓缓冲冲器器输输出出而而伴伴随随式式寄寄存存器器最最左左边边nkb级级从未全含从未全含0，则查出长度，则查出长度b的突发或不能纠正突发。的突发或不能纠正突发。上上述述译译码码器器仅仅能能纠纠正正长长度度 b的的突突发发，错错误误图图样样数数目目是是n2b-1，当，当n较大时，它仅是较大时，它仅是2n-k个可纠正错误图样的一小部分。个可纠正错误图样的一小部分。改进的译码器能纠正所有长度改进的译码器能纠正所有长度 nk的突发错误，原理如下：的突发错误，原理如下：接接收收

59、矢矢量量先先全全部部移移入入伴伴随随式式寄寄存存器器。纠纠错错之之前前伴伴随随式式寄寄存存器器循循环环移移位位n次次。循循环环移移位位期期间间，记记录录出出现现在在伴伴随随式式寄寄存存器器最最右右边边b级级中中最最短短突突发发的的长长度度b。这这个个突突发发被被认认为为是是信信道道造造成成的错误突发。的错误突发。然然后后译译码码器器便便开开始始纠纠正正过过程程。伴伴随随式式寄寄存存器器又又开开始始移移位位。一一旦旦最最短短的的突突发发在在伴伴随随式式寄寄存存器器最最右右边边b级级中中，译译码码器器便便按按上上述述方方法法进进行行纠纠正正。此此译译码码方方法法是是Gallager提提出出的的纠纠

60、正正突突发发错误码的最佳译码。错误码的最佳译码。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件实际通信系统中绝大部分信道是随机错误和突实际通信系统中绝大部分信道是随机错误和突发错误并存，需要能同时纠正这两种错误的码。发错误并存，需要能同时纠正这两种错误的码。交错技术就是可以构造这种码的一种好办法。交错技术就是可以构造这种码的一种好办法。把纠把纠t个随机错误的个随机错误的(n, k)码进行码进行度交织，得度交织，得( n, k)码，能纠码，能纠t个个 长或更短突发的任何组长或更短突发的任何组合，它显然具有纠随机和突发错误的能力。合，它显然具有纠随机和突发错误的能力。有

61、些码本来就能纠这两种错误，交错后纠错能有些码本来就能纠这两种错误，交错后纠错能力也可提高。力也可提高。本节将进一步讨论由已知码导推出新码，并用本节将进一步讨论由已知码导推出新码，并用作纠随机和突发错误的其它一些方法。作纠随机和突发错误的其它一些方法。13.8 纠突发和随机错误码纠突发和随机错误码东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.8 纠突发和随机错误码纠突发和随机错误码13.8.1 乘积码乘积码 循环乘积码的循环乘积码的编码规则编码规则考虑两个线性分组码考虑两个线性分组码c1 = (n1, k1), c2 = (n2, k2)。按按图图13.4构构成

62、成一一个个新新码码，称称为为c1和和c2的的乘乘积积码码c=c1 c2= (n1 n2, k1 k2)，首首先先，选选c1码码中中的的k2个个码码字字排排成成k2行行，再再把把其其中中的的每每一一列列当当作作c2的的消消息息位位，根根据据c2码码的的编编码码规规则则求求出出每每一一列列中余下的中余下的n2 k2个校验数据。个校验数据。图图中中左左下下角角的的校校验验数数据据，则则既既可可以以用用c1码码的的也也可可以以用用c2码码的校验规则来计算，两者的结果是一致的。的校验规则来计算，两者的结果是一致的。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件编完编完k2个

63、个c1码再计算列校验（包括校验位的校验）码再计算列校验（包括校验位的校验）或编完或编完k1个个c2码，再计算行校（包括校验位的校验）码，再计算行校（包括校验位的校验）图13.4 乘积码编码规则 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件乘积码的主要性能乘积码的主要性能定理定理13.8 若若(n1, k1)线性分组码线性分组码c1和和(n2, k2)线性分组码线性分组码c2的最小距离分别为的最小距离分别为d1和和d2，则乘积码则乘积码(n1n2, k1k2)码的码的最小距离为最小距离为d1d2 。证明：证明： 线性分组码的积码仍是线性分组码，因而只需线性分组码的积

64、码仍是线性分组码，因而只需证明证明(n1n2, k1k2)线性积码的非零码字的重量线性积码的非零码字的重量 d1d2即可。即可。存在有存在有(n1n2, k1k2)码的一个非零码字，它的非零行是码的一个非零码字，它的非零行是(n1, k1)码的最小重量非零码字，它的非零列是码的最小重量非零码字，它的非零列是(n2, k2)码的最小重量非零码字，则此码字必是积码码的最小重量非零码字，则此码字必是积码c1 c2的最小的最小重量非零码字，因为除此以外的非零码字的重量一定不重量非零码字，因为除此以外的非零码字的重量一定不是最小的。而这个积码码字的重量正好是是最小的。而这个积码码字的重量正好是d1d2。

65、证毕。证毕。13.8 纠突发和随机错误码纠突发和随机错误码13.8.1 乘积码乘积码 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件定理定理13.9 设d1和d2分别是线性码c1和c2的最小距离，则 积码c1c2能纠正 个随机错误的任何组合，同时能纠正长b max n1t2, n2t1的突码错误，其中证明证明：只要证长 b的突发错误和有 t随机错误的图样不在积码标准阵列的同一陪集中即可。 不失一般性，可设 n1t2 n2t1，则b = n1t2。13.8 纠突发和随机错误码纠突发和随机错误码13.8.1 乘积码乘积码 东南大学移动通信国家重点实验室“ “信息论与编码

66、信息论与编码” ”课件课件13.8 纠突发和随机错误码纠突发和随机错误码13.8.1 乘积码乘积码 (续)若有一个长度 n1t2的突发，当把它排成一个n2行n1列的阵列时，每列至多含有t2个错误： 若该突发和某个有 t个随机错误的图样在积码的同一陪集中，则这两个错误图样的和是积码的一个码阵。因为c2的最小距离是d2, 因此码阵中每一列至少有d2个非零分量（全0的一列除外）；和阵中每一个非零分量的列，至少含有随机错误图样中的d2 t2个错误，以及至多含有突发错误图样中的t2个错误。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.8 纠突发和随机错误码纠突发和随机

67、错误码13.8.1 乘积码乘积码 (续)由于至多只有t个随机错误，至多能分布在 个列中，因此和阵中至多含有 t2 + t 个非零分量。 但是 2 t （d2 2t2） 因此和阵中仅含有少于2td1d2个非零分量，它不可能是乘积码的一个码阵。前面假设b=n1t2或更短的突发与有t个随机错误的图样在同一陪集的假设不成立，不能在积码的标准阵列的同一陪集中。所以两者都可作陪集首，都是可纠正的错误图样。证毕。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件13.8 纠突发和随机错误码纠突发和随机错误码13.8.1 乘积码乘积码 乘乘积码的传送顺序及译码积码的传送顺序及译码乘积

68、码有两种传输数据的方法：一是按行的次序逐行传送，或按列自左至右逐列传输；另一是按码阵的对角线次序传送数据。后者传输方法所得到的码与前者是不一样的。若乘积码以行或列的次序逐行传输，则译码时可先以行按c1码，后按列以c2码进行译码，也可以先以列按c2码译码，后再以行按c1码译码；因此需要两级译码。可知乘积码译码器的复杂性完全决定于行码和列码译码器的复杂性，以及n1n2存储器的大小。 由于乘积码纠错能力很强，因此得到很大发展，例如可以从二维扩展到多个子码组成的多维乘积码，以及由一般乘积码扩展到循环乘积码等。 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件随着码长n的增加，

69、译码错误概率按指数接近于零。因此为使码有效就必须用长码。但译码器复杂性和计算量也相应增加以致难以实现。为解决这一矛盾，福尼提出了级联码的概念，把编制长码的过程分几级完成，通常分两级。级联码的应用见图13.5。13.8 纠突发和随机错误码纠突发和随机错误码13.8.2 级联码级联码 图图13.5 13.5 应用级联码的通信系统应用级联码的通信系统 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件级联码构造级联码构造(图13.5)假定在内信道上使用的是码c1，在外信道上使用的是码c2，c2称为外码外码， c1称为内码内码。所以是(n1n2, k1k2)码码，其中n1, k

70、1和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码所纠正。 13.8 纠突发和随机错误码纠突发和随机错误码13.8.2 级联码级联码 东南大学移动通信国家重点实验室“ “信息论与编码信息论与编

71、码” ”课件课件本章小结本章讨论纠突发错误码。法尔码、伯顿码都是目前应用较多的纠突发错误码。乘积码和级联码则能够有效地抵抗随机错误和突发错误混杂的干扰。本章还介绍了纠突发错误卷积码的基本概念，以及在实际中应用较多岩垂码。东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件习题习题1.若(n, k)循环码要纠正所有长度 b，同时检测所有长度 l且 b的突发，证明校验位n k b + l。2.证明纠正一个错误和检查两个错误的汉明码能纠正任何长度小于等于2（b=2）的单个突发。3.假定长为15的纠正一个错误并检查两个错误的汉明码用于纠正长度 2的突发，设计该码的捕错译码器。4.

72、令p(x)为5次本原多项式。求纠正任何长度5的单个突发的法尔码生成多项式。码长是多少？构造该码的捕错译码器。5.令m=5，构造一伯顿码，能纠正任何局限在一个5位长分组内的定段突发。假设该码按交错度 = 5交错，求该码的长度、校验位数目、以及纠突发错误能力各是多少？东南大学移动通信国家重点实验室“ “信息论与编码信息论与编码” ”课件课件6.令c1是由g(x)=x2+x+1生成的(3, 1, 3)二进制循环码，c2是由生成的 (7, 3, 4) 极长码，求c1 c2乘积码的g (x)及其最小距离，讨论它的纠错能力。7.构造一个行码和列码都是奇偶校验码的乘积码，要求该乘积码能够纠正长度 4的单个突发错误，并有最高码率。求出码的参数，列出码阵的数据传输次序。8.已知一 (n, k, d=2t+1) 循环码的生成多项式g(x)无(x+1)因子，试证明用g(x)=(x+1)g(x)生成的(n, k1, d=2t+2) 码，至少能纠正长度t +1的单个突发错误。9.构造 =1，n0 =4，k0 =3的岩垂码。 (1)求g(D)和H(D)，该码能够纠正长度为多少的突发错误? (2)画出该码的译码电路。10.证明以(n1, k1, d1)作内码，以(n2, k2, d2)作外码所生成的级联码，最小距离至少为d1 d2。习题习题