纠突发错误码.ppt

1、第十三章纠突发错误码第十三章纠突发错误码本章内容提要本章内容提要纠纠突发错误码的定义和基本性质突发错误码的定义和基本性质法尔码法尔码交错码交错码伯顿码伯顿码纠突发错误卷积码纠突发错误卷积码岩垂码岩垂码纠突发错误循环码的译码纠突发错误循环码的译码纠突发和随机错误码纠突发和随机错误码大部分实际信道如短波大部分实际信道如短波、散射散射、有线等信道中产生的有线等信道中产生的错误是突发性的；某些数据存储系统所产生的错误，错误是突发性的；某些数据存储系统所产生的错误，大部分也是突发性的，而不是随机性的。大部分也是突发性的，而不是随机性的。这些这些信道中所产生的错误是突发错误，或突发错误与信道中所产生的错误

2、是突发错误，或突发错误与随机错误并存，通常称这类信道为突发信道随机错误并存，通常称这类信道为突发信道。循环码循环码检测突发错误能力强，但纠错效果不大检测突发错误能力强，但纠错效果不大。人们希望能设计出一类专门用作纠突发错误的码，这人们希望能设计出一类专门用作纠突发错误的码，这类码称为纠突发错误码。类码称为纠突发错误码。这类码在纠突发错误时的效率应比对付随机错误而设这类码在纠突发错误时的效率应比对付随机错误而设计的码要高计的码要高，即对于给定的，即对于给定的n和和k，(n,k)有尽可能小的有尽可能小的多余度，或者说多余度，或者说n k 尽可能小尽可能小。第第1313章纠突发错误码章纠突发错误码定

3、义定义13.1 长为长为b的突发是针对错误图样来定义的突发是针对错误图样来定义的：如果一个矢量的非零分量局限于的：如果一个矢量的非零分量局限于b个连续个连续数据位，且第一和最后一位是非零的，则数据位，且第一和最后一位是非零的，则称该称该矢量为一个长为矢量为一个长为b的突发的突发。一个线性码如能纠正长为一个线性码如能纠正长为b或更短的突发错误，或更短的突发错误，但不能纠正长为但不能纠正长为b+1的所有突发错误，则的所有突发错误，则称此称此码是一个纠码是一个纠b长突发错误码，即该码的纠错能长突发错误码，即该码的纠错能力为力为b。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.

4、1 定义定义 定理定理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.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 证毕。证毕。定理定理13.2 一个一个(n,k)线性分组码，线性分组码，能发现长度不大于能发现长度不大于b的错误图样的条件是的错误图样的条件

5、是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.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 定

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

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

8、基本性质基本性质 定理定理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的突发错误，则应的突发错误，则应n k 2b。(2)（n,k）码的纠突上限为码的纠突上限为 ，称为赖格尔限。，称为赖格尔限。满足赖格尔限的码

9、是最佳的。满足赖格尔限的码是最佳的。(3)比率比率z=2b/(n k)被用来衡量码的纠突发错误的效率，被用来衡量码的纠突发错误的效率，最佳码纠突发错误的效率等于最佳码纠突发错误的效率等于1。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 定理定理13.5（n,k）循环码能检测长循环码能检测长 n k的任何突发错的任何突发错误，误，包括首尾相接包括首尾相接的突发错误。的突发错误。证明：证明：设错误图样设错误图样e(x)是是长度长度 n k的突发错误，则的突发错误，则e(x)可表示为可表示为 e(x)=x jB(x)，0 j n 1 式中，式中，B(x)

10、是次数是次数 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的任何突发错误。的任何突发错误。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 对于长度对于长度 n k的突

11、发错误图样，当它的错误局限在前的突发错误图样，当它的错误局限在前i位和后位和后l i位时，即位时，即出现首尾相接的错误时出现首尾相接的错误时，有，有13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 如果将它乘以如果将它乘以 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的首尾相

12、接的突发错误。证毕。的首尾相接的突发错误。证毕。法尔码是最早也是最大的一类法尔码是最早也是最大的一类用分析方法构造用分析方法构造出的纠单个突发错误的二进制循环码出的纠单个突发错误的二进制循环码。由于可以根据不同的要求很方便地设计所由于可以根据不同的要求很方便地设计所需要的码，译码也很简单，因此法尔码是一类需要的码，译码也很简单，因此法尔码是一类比较实用的，也是比较实用的，也是最基本的纠单个突发错误循最基本的纠单个突发错误循环码环码。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 定义定义13.2 设设p(x)是是GF(2)上的上的m次既约多项式次既约多项式，令，令是使是使p(x)整

13、除整除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。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 证明证明 只要证明只要证明长度长度 b的任何突发都位于码的不的任何突发都位于码的不同陪集中同陪集中，这样它们便能作

14、为陪集首而成为可，这样它们便能作为陪集首而成为可纠正的错误图样。纠正的错误图样。令令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 j，用用2b 1除除j i得得(13.5)把

15、式（把式（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)中的中的 或能被整除或或能被整除或等于零。等于零。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 假定假定 (13.7)令令D(x)的次数为的次数为d，那么那么D(x)(x2b 1+1)

16、的次数是的次数是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)又因又因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

17、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)13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 注注意意到到B(x)的的次次数数小小于于b，所所以以 。因因此此，B(x)和和p(x)互互素素。已已假假定定v(x)是是码码多多项项式式，所所以以xj i+1必必能能被被p(x)

18、整整除除，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)生生成成的的法法尔尔码码的的不不同同陪陪集集中中，因因而而它它们们是是可可纠纠正正的的错

19、错误误图图样样。由由于于码码是是循循环环的的，所所以以它它亦亦能能纠正长度纠正长度 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的任的任何突发错

20、误。何突发错误。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 法尔码的纠突发错误的效率为法尔码的纠突发错误的效率为 若若b等于等于m，则有则有 当当m的值较大时，的值较大时，z约等于约等于2/3。因此，相对于赖格尔限。因此，相对于赖格尔限而言，法尔码的效率并不是很高。而言，法尔码的效率并不是很高。能能够够纠纠正正任任何何长长度度为为b或或更更少少的的突突发发错错误误、并并同同时时检检测测长为长为l b的任何突发的法尔码，可用下式生成：的任何突发的法尔码，可用下式生成：该码长度等于该码长度等于和和b+l 1的最小公倍数。的最小公倍数。13.2法尔码法尔码13.2.2 法尔码的性能法

21、尔码的性能 交错是一种非常交错是一种非常简单简单而又而又有效有效的构造码的构造码的方法，它可以大大提高纠随机错误码的方法，它可以大大提高纠随机错误码的纠突发错误能力，可的纠突发错误能力，可使抗较短使抗较短突发错突发错误的码误的码变成抗较长变成抗较长突发错误的码，使纠突发错误的码，使纠正正单个定段单个定段突发错误的码突发错误的码变成纠多个定变成纠多个定段段突发错误的码。突发错误的码。这种方法所付出的这种方法所付出的代价代价是增加存储设备是增加存储设备和加大通信时延。和加大通信时延。13.3交错码交错码将将 个个(n,k)码的码矢排成码的码矢排成 n的矩形阵列，每行一个的矩形阵列，每行一个码矢，然

22、后码矢，然后按列送至通信信道按列送至通信信道，在收端恢复矩形阵列，在收端恢复矩形阵列的排列次序，就构成交错度为的排列次序，就构成交错度为 的交错码。即给定一个的交错码。即给定一个(n,k)循环码，用交错法将码长扩大循环码，用交错法将码长扩大 倍，信息位数目倍，信息位数目也扩大了也扩大了 倍，倍，构成一个（构成一个（n,k）循环码循环码，见图，见图13.1。13.3 交错码交错码13.3.1 交错码的编译码方法交错码的编译码方法 图图13.1 交错码的编码方法，其中交错码的编码方法，其中为交错度为交错度实现交错码的简明方法是排出阵列，按行编码和译码。一实现交错码的简明方法是排出阵列，按行编码和译

23、码。一般地说，这并不是最简单的实现方法。般地说，这并不是最简单的实现方法。最简单的实现方法是基于这样一个事实，即若最简单的实现方法是基于这样一个事实，即若原码是循环原码是循环的，则交错码也是循环的的，则交错码也是循环的。如果原码的生成多项式是如果原码的生成多项式是g(x)，则交错码的生成多项式是则交错码的生成多项式是g(x )。因此，可用因此，可用移位寄存器完成编码和纠错移位寄存器完成编码和纠错。只要简单地将原码译码器的每个移位寄存器用只要简单地将原码译码器的每个移位寄存器用 级置换，级置换，即可根据原码的译码器推导出交错码的译码器，而不必改变即可根据原码的译码器推导出交错码的译码器，而不必改

24、变其他连接。其他连接。所以，如果原码译码器较简单，则交错码也同样简单，而所以，如果原码译码器较简单，则交错码也同样简单，而对于短码而言，原码译码器通常是比较简单的。对于短码而言，原码译码器通常是比较简单的。13.3 交错码交错码13.3.1 交错码的编译码方法交错码的编译码方法 交错码的性能交错码的性能（1）交错编码）交错编码使错误分散使错误分散，长，长 的任何突发无论从何处开始，的任何突发无论从何处开始，都至多只能影响每行中的一位。都至多只能影响每行中的一位。（2）当且仅当每行中的错误图样是原（）当且仅当每行中的错误图样是原（n,k）码中可纠正的码中可纠正的图样时，此错误图样图样时，此错误图

25、样对整个阵列来说才是可纠正的对整个阵列来说才是可纠正的。（3）若原码能纠正）若原码能纠正 b的任何单个突发，则交错码能纠正的任何单个突发，则交错码能纠正 b 的任何单个突发，的任何单个突发，码长扩大码长扩大 倍，纠突能力也扩大倍，纠突能力也扩大 倍。倍。若若(n,k)码有最大可能的纠正突发错误能力，即码有最大可能的纠正突发错误能力，即nk2b=0，则交错码则交错码(n,k)也具有最大可能的纠正突发错误也具有最大可能的纠正突发错误能力。交错具有最大纠正突发错误能力的短码，能够构成能力。交错具有最大纠正突发错误能力的短码，能够构成实际上任意长的、具有最大可能纠突发错误能力的码。实际上任意长的、具有

26、最大可能纠突发错误能力的码。13.3 交错码交错码13.3.2 交错码的性能交错码的性能 13.3 交错码交错码13.3.2 交错码的性能交错码的性能 （4）若）若原码是循环的原码是循环的，其生成多项式为，其生成多项式为g(x)，则，则交错码也交错码也是循环的是循环的，且生成多项式为，且生成多项式为g(x)。证明证明 设经设经 次交错后得到的码是次交错后得到的码是(13.14)它的输出方式与图它的输出方式与图13.1相同，其中相同，其中 ，所以有所以有 ，即它们都是循环码，即它们都是循环码(g(x)中的码矢量。中的码矢量。13.3 交错码交错码13.3.2 交错码的性能交错码的性能 如果把上述

27、如果把上述（n,k）线性分组码循环移位一次，得线性分组码循环移位一次，得(13.15)显然，其中的每一行仍是显然，其中的每一行仍是(g(x)的码矢量。所以这个（的码矢量。所以这个（n,k）线性分组码是个循环码。线性分组码是个循环码。13.3 交错码交错码13.3.2 交错码的性能交错码的性能 若把式若把式(13.14)的循环码用多项式表示，则其码多项式为的循环码用多项式表示，则其码多项式为 式中13.3 交错码交错码13.3.2 交错码的性能交错码的性能 （5）交交错错技技术术把把寻寻求求长长而而有有效效的的纠纠突突发发错错误误码码这这个个问问题题，简化为寻求好的短码简化为寻求好的短码。（6

28、交错码需增加）交错码需增加存储设备存储设备，加大，加大通信时延通信时延。交交错错是是一一种种时时间间扩扩散散技技术术，它它使使信信道道突突发发错错误误的的相相关关性性减减小小。当当足足够够大大时时可可将将突突发发错错误误离离散散为为随随机机错错误误，从从而而可可用用纠纠随随机机错错误误码码来来纠纠突突发发错错误误。因因此此交交错错技技术术在在短短波波、散射、有线等有记忆的信道中得到了广泛的应用。散射、有线等有记忆的信道中得到了广泛的应用。（7）交交错错技技术术是是一一种种等等效效长长码码的的技技术术。根根据据Shannon第第二定理，必然有更好的性能。二定理，必然有更好的性能。伯顿发现一类纠

29、正定段突发错误的循环码。考虑一伯顿发现一类纠正定段突发错误的循环码。考虑一(n,k)码，码，码长码长n是整数是整数m的倍数，如的倍数，如n=m。码多项式表示如下码多项式表示如下定义下式的定义下式的m个相邻码位个相邻码位vi m,vi m+1,v(i+1)m 1 为一个分组，其中为一个分组，其中0 i 。因此其码矢由因此其码矢由 个分组组成。个分组组成。当且仅当长度等于或小于当且仅当长度等于或小于 m的突发局限在的突发局限在 个相邻分组内时，个相邻分组内时，称此突发为定段突发，称此突发为定段突发，是小于是小于 的正整数。的正整数。一个长一个长n=m可纠正全部限制在等于或小于可纠正全部限制在等于或

30、小于 个分组内的定个分组内的定段突发错误的线性码，称为纠段突发错误的线性码，称为纠 m长定段突发错误码。长定段突发错误码。长为长为(1)m+1的突发不论从何处开始，最多只影响的突发不论从何处开始，最多只影响 个个分组，显然，纠分组，显然，纠 m长定段突发错误码能够纠正任何长度等长定段突发错误码能够纠正任何长度等于或小于于或小于(1)m+1的单个突发错误。纠的单个突发错误。纠 m长定段突发错长定段突发错误码可当作纠误码可当作纠(1)m+1长单个突发错误码使用。长单个突发错误码使用。13.4 伯顿码伯顿码定义定义13.3 令令p(x)是是m次既约多项式，令次既约多项式，令 是能使是能使x +1被被

31、p(x)整除的最小正整数，并令整除的最小正整数，并令n是是m和和 的最小公倍数的最小公倍数 n=LCM(m,)=m则对于任何正整数对于任何正整数m，都存在一个长都存在一个长n=m的纠正的纠正m长定段突发错误的伯顿码，由下式生成长定段突发错误的伯顿码，由下式生成13.4 伯顿码伯顿码13.4.1 伯顿码的构造伯顿码的构造 此码的校验位数目是此码的校验位数目是2m，是，是 m,(2)m 循环码。循环码。每个码矢包括每个码矢包括 个分组。为了证明由上述生成式产生的个分组。为了证明由上述生成式产生的伯顿码可以纠正全部局限在伯顿码可以纠正全部局限在m位长的单个分组内的定段突位长的单个分组内的定段突发错误

32、只要证明没有这样的两个突发存在于此码标准阵发错误，只要证明没有这样的两个突发存在于此码标准阵列的相同陪集中的充分必要性。列的相同陪集中的充分必要性。对纠正对纠正m长定段突发错误的伯顿码交错，产生的长定段突发错误的伯顿码交错，产生的(n,k)交错码交错码可纠正任何限制在可纠正任何限制在 个相邻分组内的定段突发错误个相邻分组内的定段突发错误将纠正将纠正m长定段突发错误的长定段突发错误的 个码矢排列成为矩阵的个码矢排列成为矩阵的 行。此时行。此时将每行的一个分组作为一个单元，则阵列包含将每行的一个分组作为一个单元，则阵列包含 列，每列包含列，每列包含 个分组，将矩阵按列发送，每次从每行中发送一个分

33、组。所以个分组，将矩阵按列发送，每次从每行中发送一个分组。所以在交错码中，一个码矢包括个在交错码中，一个码矢包括个 分组。分组。任何局限在任何局限在 个分组的定段突发错误无论从何处开始，对每行个分组的定段突发错误无论从何处开始，对每行的影响都不会多于一个分组。若按行对接收阵列进行译码，则的影响都不会多于一个分组。若按行对接收阵列进行译码，则此定段突发能够被纠正。若此交错码用作纠（此定段突发能够被纠正。若此交错码用作纠（(1)m+1）长长突发错误码，则纠突发错误效率为突发错误码，则纠突发错误效率为13.4 伯顿码伯顿码13.4.2 伯顿码的性能伯顿码的性能 当当 趋于无穷大时，伯顿码的纠突发错误

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

35、贮接收编码阵列的缓冲器。器包括原码译码器和用作存贮接收编码阵列的缓冲器。13.4 伯顿码伯顿码13.4.2 伯顿码的性能伯顿码的性能 纠突发错误卷积码分为纠突发错误卷积码分为B1型码和型码和B2型码两类。从纠正型码两类。从纠正突发错误能力的角度，突发错误能力的角度，B1型码作用于码元、型码作用于码元、B2型码则型码则作用于码段，类似于分组码中的纠定段突发错误码，作用于码段，类似于分组码中的纠定段突发错误码，可以认为是可以认为是B1型码的特例。型码的特例。假设（假设（n0,k0,m）B1型码的纠突发错误的能力为型码的纠突发错误的能力为b1，则则它的纠它的纠B2型突发错误的能力型突发错误的能力b2

36、为为(13.17)若若(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和 b2的全部突发错误全部突发错误。纠突发错误卷积码通常都是指无误纠突发错误码。

37、还有一类纠突发错误卷积码，虽然不能纠正长度不能纠正长度 b的所有突发错误，但能纠正的所有突发错误，但能纠正其中绝大部分错误其中绝大部分错误，即能以很小的译码错误概率纠正长度 b的突发错误，这类码称为有误纠突发错误码。13.5 纠突发错误卷积码纠突发错误卷积码定理定理13.6（n0,k0,m）卷积码纠突发错误能力为卷积码纠突发错误能力为b的充的充要条件是：其校验矩阵要条件是：其校验矩阵H中，由任意相邻中，由任意相邻b列为一组的列为一组的互不相交的两组，它们列的任意线性组合不能为互不相交的两组，它们列的任意线性组合不能为0，且，且其中一组至少有一列在其中一组至少有一列在H矩阵中的首矩阵中的首n0列

38、中选取。列中选取。定理定理13.6表明，两个不重叠的长度表明，两个不重叠的长度 b的突发，其中一的突发，其中一个突发从第个突发从第0码段开始，则它们共同组成的错误图样，码段开始，则它们共同组成的错误图样，与与H矩阵相乘所得的伴随式不能为矩阵相乘所得的伴随式不能为0。也即要求不同的突发错误图样具有不同的伴随式，也即要求不同的突发错误图样具有不同的伴随式，才能保证译码器能正确区分两个不同的突发，从而进才能保证译码器能正确区分两个不同的突发，从而进行正确的判决。行正确的判决。13.5 纠突发错误卷积码纠突发错误卷积码定理定理13.7对一个纠突发能力为对一个纠突发能力为b的有限记忆的二进制的有限记忆的

39、二进制线性码，其防护区间线性码，其防护区间f、纠突能力纠突能力b和码率和码率R之间必满足之间必满足(13.21)例如对纠突发能力为b的(n,k)线性分组码，f=n b，则可以解得，对于有误纠突发错误码，f,b和R之间必须满足下式：(13.22)13.5 纠突发错误卷积码纠突发错误卷积码在式（13.21）和（13.22）中，能使能使等号成立的码，等号成立的码，称为称为最佳纠突发错误码，最佳纠突发错误码，简称为简称为最佳码最佳码。寻找和构造最佳或接近最佳纠突发错误卷积码的方法：方法：采用交错技术，由约束长度较短的最佳码得到约束长度较长的最佳码。利用分析法构造纠单个突发错误的最佳码，如岩垂码。确定突

40、发位置然后予以纠正，即纠突发删除码，这类码属有误纠突发错误卷积码。在同样的码率和纠错能力下，有误纠突发错误卷积码所要求的防护区间比无误纠突发错误卷积码要小得多。因此，在突发错误较为严重的信道中，采用有误纠突发错误卷积码通常能取得更好的效果13.5 纠突发错误卷积码纠突发错误卷积码岩垂（Iwadare）码是一种较为实用的纠突发错误卷积码，属于（n0,n0 1,m）B1型纠突发错误卷积码。特点是译码较为简单，并且当n0较小时接近最佳码。岩垂码的n0 1个子生成元为（13.23)其中 (13.24)为整数。当i=1时，上式中的b(1)达到最大，此时 (13.25)码的约束度为m=b(1)，能纠正长度

41、为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行即首行。由此B0阵构成的H矩阵，与长度 n0的任何突发错误图样相乘所得的伴随式均不相同，且不为0，满足定理13.6的要求，因此能够纠正任何长度 n0的单个突发错误。13.6 岩垂码岩垂码例例13.2 设=1，n0=3，k0=2，m=8，构造一个(3,2,8)岩垂码，能够纠正长度为b1=n0=3个码元的任何单个突发错误。分析此岩

42、垂码的编译码方式。解解 码的两个子生成元为：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码元位的两个正交校验和。对E2错误图样而言，虽然 能构成对e02码元位正交的两个校验和，但 却不能构成对e01码元位正交的两个校验和。同样，对E3错误图样而言，也不能从 和 构成对e

43、12和e11的两个正交校验和。因此采用一次大数逻辑译码的方法无法纠正B1型码的长度为3的单个突发图样。必须进行分段大数逻辑译码。由H矩阵的表达式可得13.6 岩垂码岩垂码构成对第一码段第2信息比特e12的两个正交校验和式。用上两式的大数判决结果对该码元进行纠错后，该子分组在译码器中进入第0码段位置，由于第2信息元已纠错，错误对该信息元的影响已消除，所以由H矩阵的第4行和第9行可得它们构成了对第0段码第1个信息比特e01的两个正交校验和式，利用大数准则对该信息比特进行纠错。因此采用这种二次分段大数逻辑译码后，就实现了对e01和e02的纠错。一般而言，n0 1个信息比特中的错误，可以用n0 1次分

44、段大数逻辑译码方法译码。13.6 岩垂码岩垂码（3,2,8）岩垂码的译码器原理图如图13.2所示。13.6 岩垂码岩垂码图13.2 （3，2，8）岩垂码译码器（3,2,8）岩垂码的译码步骤译码步骤（1）将输入R(D)中的每一段的前两个信息元送入编码器求出新的校验元，与后面输入的校验元进行比较，得到相应的伴随式分量，送入伴随式寄存器。（2）如果与门A2输出1，则表明第1码段的第2个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。（3）如果与门A1输出1，则表明第0码段的第1个信息元出错，对它进行纠错，同时修正伴随式以消去此错误的影响。13.6 岩垂码岩垂码用这种分段大数逻辑译码方法能

45、够纠正约束长度内的任意的长度 的突发错误。当=1时，岩垂码的防护区间与纠突发能力之比为对于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。设设e(x)的错误局限

46、在的错误局限在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 纠突发错误循环码的译码纠突发错误循环码的译码译码步

47、骤译码步骤步骤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)的校验部分。因此缓冲器中k位接收信息数字是无错的。然后门3打开，缓冲器中k位无错信息数字移出，送到信宿。如果在伴随式寄存器的前n k b次移位期间，伴随式寄存器的最左边n k

48、 b级从未包含0，则突发不是限制在n k个校验位上。13.7 纠突发错误循环码的译码纠突发错误循环码的译码步骤步骤4：若伴随式寄存器第：若伴随式寄存器第nkb+i次移位后次移位后，最左边最左边nkb级包含级包含0，则突发限制在，则突发限制在r(x)的的xni,xn1,x0,xbi1 位。从右端数起，伴随位。从右端数起，伴随式寄存器第式寄存器第b,(b1),(bi+1)级中的位与级中的位与r(x)的的xni,xn2,xn1 位位上的错误比特相对应。此时，时钟从上的错误比特相对应。此时，时钟从nkb+i+1开始计数。门开始计数。门1关闭，关闭，伴随式寄存器移位。一旦时钟计数到伴随式寄存器移位。一旦

49、时钟计数到nk，伴随式寄存器中最右端伴随式寄存器中最右端i位比特就与缓冲寄存器中首位比特就与缓冲寄存器中首i位接收信息数字的相对应。然后门位接收信息数字的相对应。然后门2和和门门3打开。接收信息从缓冲寄存器中读出并进行纠正。打开。接收信息从缓冲寄存器中读出并进行纠正。步骤步骤5：若伴随式寄存器已移位：若伴随式寄存器已移位nk次，而最左边次，而最左边nkb从未全含从未全含0，则门则门3打开，数字从缓冲寄存器一次一个读出。同时门打开，数字从缓冲寄存器一次一个读出。同时门1打开，伴随打开，伴随式寄存器移位。一旦伴随式寄存器最左边式寄存器移位。一旦伴随式寄存器最左边nkb级包含级包含0，其最右边，其最

50、右边b级内容就与将从缓冲寄存器输出的级内容就与将从缓冲寄存器输出的b位接收数字中的错误对应。然后位接收数字中的错误对应。然后门门2打开，错误信息用伴随式寄存器输出（门打开，错误信息用伴随式寄存器输出（门1关闭）的数字进行纠关闭）的数字进行纠正。正。13.7 纠突发错误循环码的译码纠突发错误循环码的译码13.7 纠突发错误循环码的译码纠突发错误循环码的译码当当k位位信信息息已已从从缓缓冲冲器器输输出出而而伴伴随随式式寄寄存存器器最最左左边边nkb级级从未全含从未全含0，则查出长度，则查出长度b的突发或不能纠正突发。的突发或不能纠正突发。上上述述译译码码器器仅仅能能纠纠正正长长度度 b的的突突发发