1、东南大学移动通信国家重点实验室本章内容提要本章内容提要纠突发错误码的定义和基本性质纠突发错误码的定义和基本性质法尔码法尔码交错码交错码伯顿码伯顿码纠突发错误卷积码纠突发错误卷积码岩垂码岩垂码纠突发错误循环码的译码纠突发错误循环码的译码纠突发和随机错误码纠突发和随机错误码东南大学移动通信国家重点实验室 大部分实际信道如短波、散射、有线等信道中产生的大部分实际信道如短波、散射、有线等信道中产生的错误是突发性的；某些数据存储系统所产生的错误，错误是突发性的；某些数据存储系统所产生的错误，大部分也是突发性的，而不是随机性的。大部分也是突发性的，而不是随机性的。这些这些信道中所产生的错误是突发错误，或突
2、发错误与信道中所产生的错误是突发错误，或突发错误与随机错误并存，通常称这类信道为突发信道随机错误并存，通常称这类信道为突发信道。循环码循环码检测突发错误能力强，但纠错效果不大检测突发错误能力强，但纠错效果不大。人们希望能设计出一类专门用作纠突发错误的码，这人们希望能设计出一类专门用作纠突发错误的码，这类码称为纠突发错误码。类码称为纠突发错误码。这类码在纠突发错误时的效率应比对付随机错误而设这类码在纠突发错误时的效率应比对付随机错误而设计的码要高计的码要高，即对于给定的，即对于给定的n和和k，(n,k)有尽可能小的有尽可能小的多余度，或者说多余度，或者说n k 尽可能小尽可能小。第第1313章纠
3、突发错误码章纠突发错误码东南大学移动通信国家重点实验室定义定义13.1 长为长为b的突发是针对错误图样来定义的突发是针对错误图样来定义的：如果一个矢量的非零分量局限于的：如果一个矢量的非零分量局限于b个连续个连续数据位，且第一和最后一位是非零的，则数据位，且第一和最后一位是非零的，则称该称该矢量为一个长为矢量为一个长为b的突发的突发。一个线性码如能纠正长为一个线性码如能纠正长为b或更短的突发错误，或更短的突发错误，但不能纠正长为但不能纠正长为b+1的所有突发错误，则的所有突发错误，则称此称此码是一个纠码是一个纠b长突发错误码，即该码的纠错能长突发错误码，即该码的纠错能力为力为b。13.1纠突发
4、错误码定义和基本性质纠突发错误码定义和基本性质13.1.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)个个 bibibninnN212)2(2)1(2113.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 证毕。证
5、毕。东南大学移动通信国家重点实验室 定理定理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
6、 b 1+lb(n+2 b)（13.2）或或 n k b 证毕。证毕。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室 定理定理13.3 一个（一个（n,k）线性码能纠正所有长度）线性码能纠正所有长度 b的突的突发错误的充要条件是：长度发错误的充要条件是：长度 2b的突发不是一个码字。的突发不是一个码字。证明证明假设存在一个长假设存在一个长 2b的突发的突发v是一个码字，则是一个码字，则 v =u+w，其中，其中 u、w都是长度都是长度 b的突发。的突发。必要性必要性：若：若v是码字，因任意一陪集只有一个错误图样，则是码
7、字，因任意一陪集只有一个错误图样，则u和和w必在同一陪集中。设必在同一陪集中。设u为陪集首，则陪集中每一个字的错误都是为陪集首，则陪集中每一个字的错误都是此陪集首，此陪集首，w必为不可纠错误，否则不可能与必为不可纠错误，否则不可能与u同在一个陪集。这同在一个陪集。这样尽管样尽管v是一是一“码字码字”，但它是一个错码，与假设，但它是一个错码，与假设v是一码字矛盾，是一码字矛盾，因此把因此把u作为陪集首来纠错也是无效的，即它不能纠正所有长作为陪集首来纠错也是无效的，即它不能纠正所有长 b 的突发错误。的突发错误。充分性：充分性：若长度若长度 2b的突发的突发v不是码字，则不是码字，则u、w不在同一
8、陪集中，不在同一陪集中，若它们都是陪集首，则都是可以纠正的长若它们都是陪集首，则都是可以纠正的长 b 的突发错误。的突发错误。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质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。表
9、述为：表述为：(1)一个一个(n,k)线性分组码，若要纠正所有长度线性分组码，若要纠正所有长度 b的突发错误，则应的突发错误，则应n k 2b。(2)（n,k）码的纠突上限为）码的纠突上限为 ，称为赖格尔限。，称为赖格尔限。满足赖格尔限的码是最佳的。满足赖格尔限的码是最佳的。(3)比率比率z=2b/(n k)被用来衡量码的纠突发错误的效率，被用来衡量码的纠突发错误的效率，最佳码纠突发错误的效率等于最佳码纠突发错误的效率等于1。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 2knb东南大学移动通信国家重点实验室 定理定理13.5（n,k）循环码能检测
10、长）循环码能检测长 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)的次数，因的次数，因此此B(x)不能为不能为g(x)所整除所整除。又因为又因为g(x)是是xn 1的因式，因此的因式，因此g(x)与与x j互素互素。因此。因此g(x)也不能整除也不能整除x jB(x
11、)。因此，由此因此，由此e(x)产生的产生的伴随式不为零伴随式不为零。即一个。即一个(n,k)循循环码能检测长环码能检测长 n k的任何突发错误。的任何突发错误。13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 东南大学移动通信国家重点实验室对于长度对于长度 n k的突发错误图样，当它的错误局限在前的突发错误图样，当它的错误局限在前i位和后位和后l i位时，即位时，即出现首尾相接的错误时出现首尾相接的错误时，有，有13.1纠突发错误码定义和基本性质纠突发错误码定义和基本性质13.1.2 基本性质基本性质 11)()(1110000)(nnilnilni
12、ixexexexeexe如果将它乘以如果将它乘以 xl-i,则则 111101)()(000)(liilililnilnilxexexexeexex由于它的由于它的次数小于次数小于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、分析方法构造用分析方法构造出的纠单个突发错误的二进制循环码出的纠单个突发错误的二进制循环码。由于可以根据不同的要求很方便地设计所由于可以根据不同的要求很方便地设计所需要的码，译码也很简单，因此法尔码是一类需要的码，译码也很简单，因此法尔码是一类比较实用的，也是比较实用的，也是最基本的纠单个突发错误循最基本的纠单个突发错误循环码环码。13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室定义定义13.2 设设p(x)是是GF(2)上的上的m次既约多项式次既约多项式，令，令是使是使p(x)整除整除x+1的最小整数，称的最小整数，称为为p(x)的的周期周期；令；令
14、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的任何突发都位于码的不的任何突发都位于码的不同陪集中同陪集中，这样它们便能作为陪集首而成为可，这样它们便能作为陪集首而
15、成为可纠正的错误图样。纠正的错误图样。令令x iA(x)和和x jB(x)分别表示两个长为分别表示两个长为b1和和b2突发突发的多项式，且的多项式，且b1 b，b2 b，而，而 13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 1111221()1bbbA xxaxa x2221221()1bbbB xxbxb x东南大学移动通信国家重点实验室13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 如果假定如果假定xiA(x)和和xjB(x)在码的同一陪集中在码的同一陪集中，那么多项式，那么多项式 v(x)=xiA(x)+xjB(x)(13.4)必是一个码多项式必是一个码多项式。
16、不失一般，假定。不失一般，假定i j，用，用2b 1除除j i得得(21)jiqbb(13.5)把式（把式（13.5）代入式（）代入式（13.4），那么），那么v(x)可表示为可表示为 021bb(13.6)1)()()()()()()()()()()12()12()12(bqbibibbqbbibbqixxBxxBxxAxxBxxBxxBxxAxxBxxAxxv东南大学移动通信国家重点实验室13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 根据假定根据假定v(x)为码多项式，而循环码的为码多项式，而循环码的生成多项式为生成多项式为 g(x)=(x2b 1+1)p(x)，所以所以(x
17、2b 1+1)|v(x)。由于由于(x2b 1+1)|xq(2b 1)+1，因此式，因此式(13.6)中的中的 或能被整除或等于零。或能被整除或等于零。()()bA xx B x东南大学移动通信国家重点实验室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)根
18、据假定根据假定b1 b，b2 b，所以由式（，所以由式（13.8）可得）可得b b1+d (13.9)又因又因b11 0，由式，由式(13.9)可得可得b b11+d，故有，故有 b d (13.10)21()()()(1)bbA xx B xD x x()()bA xx B x()bx B x()()bA xx B x东南大学移动通信国家重点实验室13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 从式从式(13.10)可知可知 中有中有 这一项。因为这一项。因为2b 1b d，故，故D(x)(x2b 1+1)不能有不能有 这一这一 项。项。这与假设这与假设 相矛盾。相矛盾。所以必有
19、所以必有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)()()bA xx B xbxbx21()()()(1)bbA xx B xD x x()()bA xx B x()()(1)j iv xx B x x东南大学移动通信国家重点实验室13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 注意到注意到B(x)的次数小于的次数小于b，所以，所以 。因此，。因此，B
20、(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)=(x
21、2b 1+1)p(x)定义的定义的g(x)生成的法尔码的不同陪集中，因而生成的法尔码的不同陪集中，因而它们是可纠正的错误图样。由于码是循环的，所以它亦能它们是可纠正的错误图样。由于码是循环的，所以它亦能纠正长度纠正长度 b的首尾相接的突发错误。的首尾相接的突发错误。()()B xbp xm 东南大学移动通信国家重点实验室 例例13.1 考虑既约多项式考虑既约多项式 p(x)=1+x2+x5,已知它是本原多已知它是本原多项式，项式，m=op(x)=5，周期周期 =251=31；令；令b=5，可算得，可算得2b1=9不能整除不能整除 =31，故可构造法尔码，其生成多项，故可构造法尔码，其生成多项式
22、为式为：码长为：码长为：n=LCM9,31=279 k=n (m+2b 1)=279 14=265所以该法尔码是所以该法尔码是(279,265)循环码，能纠长度循环码，能纠长度 5的任的任何突发错误。何突发错误。14119525291)1)(1()(xxxxxxxxxg13.2法尔码法尔码13.2.1 法尔码的构造法尔码的构造 东南大学移动通信国家重点实验室 法尔码的纠突发错误的效率为法尔码的纠突发错误的效率为 若若b等于等于m，则有，则有 当当m的值较大时，的值较大时，z约等于约等于2/3。因此，相对于赖格尔限。因此，相对于赖格尔限而言，法尔码的效率并不是很高。而言，法尔码的效率并不是很高。
23、能够纠正任何长度为能够纠正任何长度为b或更少的突发错误、并同时检测或更少的突发错误、并同时检测长为长为l b的任何突发的法尔码，可用下式生成：的任何突发的法尔码，可用下式生成：该码长度等于该码长度等于和和b+l 1的最小公倍数。的最小公倍数。122bmbz132mmz13.2法尔码法尔码13.2.2 法尔码的性能法尔码的性能)()1()(1xpxxglb东南大学移动通信国家重点实验室交错是一种非常交错是一种非常简单简单而又而又有效有效的构造码的构造码的方法，它可以大大提高纠随机错误码的方法，它可以大大提高纠随机错误码的纠突发错误能力，可的纠突发错误能力，可使抗较短使抗较短突发错突发错误的码误的
24、码变成抗较长变成抗较长突发错误的码，使纠突发错误的码，使纠正正单个定段单个定段突发错误的码突发错误的码变成纠多个定变成纠多个定段段突发错误的码。突发错误的码。这种方法所付出的这种方法所付出的代价代价是增加存储设备是增加存储设备和加大通信时延。和加大通信时延。13.3交错码交错码东南大学移动通信国家重点实验室 将将 个个(n,k)码的码矢排成码的码矢排成 n的矩形阵列，每行一个的矩形阵列，每行一个码矢，然后码矢，然后按列送至通信信道按列送至通信信道，在收端恢复矩形阵列，在收端恢复矩形阵列的排列次序，就构成交错度为的排列次序，就构成交错度为 的交错码。即给定一个的交错码。即给定一个(n,k)循环码
25、，用交错法将码长扩大循环码，用交错法将码长扩大 倍，信息位数目倍，信息位数目也扩大了也扩大了 倍，倍，构成一个（构成一个（n,k）循环码）循环码，见图，见图13.1。13.3 交错码交错码13.3.1 交错码的编译码方法交错码的编译码方法 nkk图图13.1 交错码的编码方法，其中交错码的编码方法，其中为交错度为交错度东南大学移动通信国家重点实验室实现交错码的简明方法是排出阵列，按行编码和译码。一实现交错码的简明方法是排出阵列，按行编码和译码。一般地说，这并不是最简单的实现方法。般地说，这并不是最简单的实现方法。最简单的实现方法是基于这样一个事实，即若最简单的实现方法是基于这样一个事实，即若原
26、码是循环原码是循环的，则交错码也是循环的的，则交错码也是循环的。如果原码的生成多项式是如果原码的生成多项式是g(x)，则交错码的生成多项式是，则交错码的生成多项式是g(x )。因此，可用。因此，可用移位寄存器完成编码和纠错移位寄存器完成编码和纠错。只要简单地将原码译码器的每个移位寄存器用只要简单地将原码译码器的每个移位寄存器用 级置换，级置换，即可根据原码的译码器推导出交错码的译码器，而不必改变即可根据原码的译码器推导出交错码的译码器，而不必改变其他连接。其他连接。所以，如果原码译码器较简单，则交错码也同样简单，而所以，如果原码译码器较简单，则交错码也同样简单，而对于短码而言，原码译码器通常是
27、比较简单的。对于短码而言，原码译码器通常是比较简单的。13.3 交错码交错码13.3.1 交错码的编译码方法交错码的编译码方法 东南大学移动通信国家重点实验室交错码的性能交错码的性能（1）交错编码）交错编码使错误分散使错误分散，长，长 的任何突发无论从何处开始，的任何突发无论从何处开始，都至多只能影响每行中的一位。都至多只能影响每行中的一位。（2）当且仅当每行中的错误图样是原（）当且仅当每行中的错误图样是原（n,k）码中可纠正的）码中可纠正的图样时，此错误图样图样时，此错误图样对整个阵列来说才是可纠正的对整个阵列来说才是可纠正的。（3）若原码能纠正）若原码能纠正 b的任何单个突发，则交错码能纠
28、正的任何单个突发，则交错码能纠正 b 的任何单个突发，的任何单个突发，码长扩大码长扩大 倍，纠突能力也扩大倍，纠突能力也扩大 倍。倍。若若(n,k)码有最大可能的纠正突发错误能力，即码有最大可能的纠正突发错误能力，即nk2b=0，则交错码，则交错码(n,k)也具有最大可能的纠正突发也具有最大可能的纠正突发错误能力。交错具有最大纠正突发错误能力的短码，能够错误能力。交错具有最大纠正突发错误能力的短码，能够构成实际上任意长的、具有最大可能纠突发错误能力的码。构成实际上任意长的、具有最大可能纠突发错误能力的码。13.3 交错码交错码13.3.2 交错码的性能交错码的性能 东南大学移动通信国家重点实验
29、室13.3 交错码交错码13.3.2 交错码的性能交错码的性能 （4）若）若原码是循环的原码是循环的，其生成多项式为，其生成多项式为g(x)，则，则交错码也交错码也是循环的是循环的，且生成多项式为，且生成多项式为g(x)。证明证明 设经设经 次交错后得到的码是次交错后得到的码是 10111,120212,101,1.nnnvvvvvvvvv(13.14)它的输出方式与图它的输出方式与图13.1相同，其中相同，其中 ，所以有所以有 ，即它们都是循环码，即它们都是循环码(g(x)中的码矢量。中的码矢量。01,1(,.)()iiii nvvvvg x(1),10,2(,.)()ii nii nvvv
30、vg x东南大学移动通信国家重点实验室13.3 交错码交错码13.3.2 交错码的性能交错码的性能 如果把上述（如果把上述（n,k）线性分组码循环移位一次，得）线性分组码循环移位一次，得 20212,130313,11,01,11,1,0,1,11,1101,2.nnnnnnvvvvvvvvvvvvvvv(13.15)显然，其中的每一行仍是显然，其中的每一行仍是(g(x)的码矢量。所以这个的码矢量。所以这个（n,k）线性分组码是个循环码。）线性分组码是个循环码。东南大学移动通信国家重点实验室13.3 交错码交错码13.3.2 交错码的性能交错码的性能 若把式若把式(13.14)的循环码用多项式
31、表示，则其码多项式为的循环码用多项式表示，则其码多项式为 1)1(1,1)1(1,1)1(1,11,11,110,10,10,)(xxvxxvxvxxvxxvxvxvvxvnnnnnn 111,11,10,111,11,10,111,1,0,xxvxvvxxvxvvxvxvvnnnnnn xgxxkxxkxk111式中101,1()()()()niii nivvxvxk xg x东南大学移动通信国家重点实验室13.3 交错码交错码13.3.2 交错码的性能交错码的性能 （5）交错技术把寻求）交错技术把寻求长而有效的纠突发错误码长而有效的纠突发错误码这个问题，这个问题，简化为寻求好的短码简化为寻
32、求好的短码。（6）交错码需增加）交错码需增加存储设备存储设备，加大，加大通信时延通信时延。交错是一种交错是一种时间扩散技术时间扩散技术，它使信道突发错误的相关性，它使信道突发错误的相关性减小。当减小。当足够大时可将突发错误离散为随机错误，从而足够大时可将突发错误离散为随机错误，从而可用纠随机错误码来纠突发错误。因此交错技术在短波、可用纠随机错误码来纠突发错误。因此交错技术在短波、散射、有线等有记忆的信道中得到了广泛的应用。散射、有线等有记忆的信道中得到了广泛的应用。（7）交错技术是一种）交错技术是一种等效长码等效长码的技术。根据的技术。根据Shannon第第二定理，必然有更好的性能。二定理，必
33、然有更好的性能。东南大学移动通信国家重点实验室 伯顿发现一类纠正定段突发错误的循环码。考虑一伯顿发现一类纠正定段突发错误的循环码。考虑一(n,k)码，码，码长码长n是整数是整数m的倍数，如的倍数，如n=m。码多项式表示如下。码多项式表示如下 定义下式的定义下式的m个相邻码位个相邻码位vi m,vi m+1,v(i+1)m 1 为一个分组，其中为一个分组，其中0 i 。因此其码矢由。因此其码矢由 个分组组成。个分组组成。当且仅当长度等于或小于当且仅当长度等于或小于 m的突发局限在的突发局限在 个相邻分组内个相邻分组内时，称此突发为定段突发，时，称此突发为定段突发，是小于是小于 的正整数。的正整数
34、。一个长一个长n=m可纠正全部限制在等于或小于可纠正全部限制在等于或小于 个分组内的定个分组内的定段突发错误的线性码，称为纠段突发错误的线性码，称为纠 m长定段突发错误码。长定段突发错误码。长为长为(1)m+1的突发不论从何处开始，最多只影响的突发不论从何处开始，最多只影响 个个分组，显然，纠分组，显然，纠 m长定段突发错误码能够纠正任何长度等长定段突发错误码能够纠正任何长度等于或小于于或小于(1)m+1的单个突发错误。纠的单个突发错误。纠 m长定段突发错长定段突发错误码可当作纠误码可当作纠(1)m+1长单个突发错误码使用。长单个突发错误码使用。112210)(mmxvxvxvvxv13.4
35、伯顿码伯顿码东南大学移动通信国家重点实验室 定义定义13.3 令令p(x)是是m次既约多项式，令次既约多项式，令 是能使是能使x +1被被p(x)整除的最小正整数，并令整除的最小正整数，并令n是是m和和 的最小公倍数的最小公倍数 n=LCM(m,)=m则对于任何正整数对于任何正整数m，都存在一个长，都存在一个长n=m的纠正的纠正m长定段突发错误的伯顿码，由下式生成长定段突发错误的伯顿码，由下式生成)()1()(xpxxgm13.4 伯顿码伯顿码13.4.1 伯顿码的构造伯顿码的构造 此码的校验位数目是此码的校验位数目是2m，是，是 m,(2)m 循环码。循环码。每个码矢包括每个码矢包括 个分组
36、。为了证明由上述生成式产生的个分组。为了证明由上述生成式产生的伯顿码可以纠正全部局限在伯顿码可以纠正全部局限在m位长的单个分组内的定段突位长的单个分组内的定段突发错误，只要证明没有这样的两个突发存在于此码标准阵发错误，只要证明没有这样的两个突发存在于此码标准阵列的相同陪集中的充分必要性。列的相同陪集中的充分必要性。东南大学移动通信国家重点实验室 对纠正对纠正m长定段突发错误的伯顿码交错，产生的长定段突发错误的伯顿码交错，产生的(n,k)交错码交错码可纠正任何限制在可纠正任何限制在 个相邻分组内的定段突发错误个相邻分组内的定段突发错误 将纠正将纠正m长定段突发错误的长定段突发错误的 个码矢排列成
37、为矩阵的个码矢排列成为矩阵的 行。此时行。此时将每行的一个分组作为一个单元，则阵列包含将每行的一个分组作为一个单元，则阵列包含 列，每列包含列，每列包含 个分组，将矩阵按列发送，每次从每行中发送一个分组。所个分组，将矩阵按列发送，每次从每行中发送一个分组。所以在交错码中，一个码矢包括个以在交错码中，一个码矢包括个 分组。分组。任何局限在任何局限在 个分组的定段突发错误无论从何处开始，对每个分组的定段突发错误无论从何处开始，对每行的影响都不会多于一个分组。若按行对接收阵列进行译码，行的影响都不会多于一个分组。若按行对接收阵列进行译码，则此定段突发能够被纠正。若此交错码用作纠（则此定段突发能够被纠
38、正。若此交错码用作纠（(1)m+1）长突发错误码，则纠突发错误效率为长突发错误码，则纠突发错误效率为mmmmknmz1112112)(11213.4 伯顿码伯顿码13.4.2 伯顿码的性能伯顿码的性能 东南大学移动通信国家重点实验室 当当 趋于无穷大时，伯顿码的纠突发错误效率趋于趋于无穷大时，伯顿码的纠突发错误效率趋于1，即即 。因而将伯顿码交错，可以得到一类渐近最。因而将伯顿码交错，可以得到一类渐近最佳的纠突发错误码。当佳的纠突发错误码。当 值较大时，交错的伯顿码比具值较大时，交错的伯顿码比具有同样纠突发错误能力的法尔码更有效。有同样纠突发错误能力的法尔码更有效。实现将伯顿码交错的简便方法是
39、组成编码阵列，按行实现将伯顿码交错的简便方法是组成编码阵列，按行编码和译码。因此，交错码的编码器包括原码编码器编码和译码。因此，交错码的编码器包括原码编码器和用作存贮编码阵列行矢量的缓冲器。交错码的译码和用作存贮编码阵列行矢量的缓冲器。交错码的译码器包括原码译码器和用作存贮接收编码阵列的缓冲器。器包括原码译码器和用作存贮接收编码阵列的缓冲器。1limz13.4 伯顿码伯顿码13.4.2 伯顿码的性能伯顿码的性能 东南大学移动通信国家重点实验室 纠突发错误卷积码分为纠突发错误卷积码分为B1型码和型码和B2型码两类。从纠正型码两类。从纠正突发错误能力的角度，突发错误能力的角度，B1型码作用于码元、
40、型码作用于码元、B2型码则型码则作用于码段，类似于分组码中的纠定段突发错误码，作用于码段，类似于分组码中的纠定段突发错误码，可以认为是可以认为是B1型码的特例。型码的特例。假设（假设（n0,k0,m）B1型码的纠突发错误的能力为型码的纠突发错误的能力为b1，则，则它的纠它的纠B2型突发错误的能力型突发错误的能力b2为为(13.17)若若(n0,k0,m)B2型码的纠突发错误的能力为型码的纠突发错误的能力为b2=n0，则它的纠则它的纠B1型突发错误的能力型突发错误的能力b1为为(13.18)0102nbnb1)1(01nb13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室
41、如果将连续两个突发错误之间的无误区间定义为防护区间，则对于不同型的码要求有不同的防护区间。如果译码约束长度是n0(m+1)，则B1型码的防护区间长度f1为 (13.19)而B2型码所要求的防护区间长度f2则为(13.20)B1型码和B2型码都属于无误纠突发错误码无误纠突发错误码，能纠正长度分别 b1和 b2的全部突发错误全部突发错误。纠突发错误卷积码通常都是指无误纠突发错误码。还有一类纠突发错误卷积码，虽然不能纠正长度不能纠正长度 b的所有突发错误，但能纠正的所有突发错误，但能纠正其中绝大部分错误其中绝大部分错误，即能以很小的译码错误概率纠正长度 b的突发错误，这类码称为有误纠突发错误码。)1
42、(1)1(010mnfmnmnf0213.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室 定理定理13.6（n0,k0,m）卷积码纠突发错误能力为）卷积码纠突发错误能力为b的充的充要条件是：其校验矩阵要条件是：其校验矩阵H中，由任意相邻中，由任意相邻b列为一组的列为一组的互不相交的两组，它们列的任意线性组合不能为互不相交的两组，它们列的任意线性组合不能为0，且，且其中一组至少有一列在其中一组至少有一列在H矩阵中的首矩阵中的首n0列中选取。列中选取。定理定理13.6表明，两个不重叠的长度表明，两个不重叠的长度 b的突发，其中一的突发，其中一个突发从第个突发从第0码段开始，则它
43、们共同组成的错误图样，码段开始，则它们共同组成的错误图样，与与H矩阵相乘所得的伴随式不能为矩阵相乘所得的伴随式不能为0。也即要求不同的突发错误图样具有不同的伴随式，也即要求不同的突发错误图样具有不同的伴随式，才能保证译码器能正确区分两个不同的突发，从而进才能保证译码器能正确区分两个不同的突发，从而进行正确的判决。行正确的判决。13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室 定理定理13.7对一个纠突发能力为对一个纠突发能力为b的有限记忆的二进制的有限记忆的二进制线性码，其防护区间线性码，其防护区间f、纠突能力、纠突能力b和码率和码率R之间必满足之间必满足(13.21)
44、例如对纠突发能力为b的(n,k)线性分组码，f=n b，则可以解得，对于有误纠突发错误码，f,b和R之间必须满足下式：(13.22)RRbf11knknRRbbn112knb13.5 纠突发错误卷积码纠突发错误卷积码RRbf1东南大学移动通信国家重点实验室 在式（13.21）和（13.22）中，能使能使等号成立的码，等号成立的码，称称为为最佳纠突发错误码，最佳纠突发错误码，简称为简称为最佳码最佳码。寻找和构造最佳或接近最佳纠突发错误卷积码的方法：方法：采用交错技术，由约束长度较短的最佳码得到约束长度较长的最佳码。利用分析法构造纠单个突发错误的最佳码，如岩垂码。确定突发位置然后予以纠正，即纠突发
45、删除码，这类码属有误纠突发错误卷积码。在同样的码率和纠错能力下，有误纠突发错误卷积码所要求的防护区间比无误纠突发错误卷积码要小得多。因此，在突发错误较为严重的信道中，采用有误纠突发错误卷积码通常能取得更好的效果13.5 纠突发错误卷积码纠突发错误卷积码东南大学移动通信国家重点实验室 岩垂（Iwadare）码是一种较为实用的纠突发错误卷积码，属于（n0,n0 1,m）B1型纠突发错误卷积码。特点是译码较为简单，并且当n0较小时接近最佳码。岩垂码的n0 1个子生成元为（13.23)其中 (13.24)为整数。当i=1时，上式中的b(1)达到最大，此时 (13.25)码的约束度为m=b(1)，能纠正
46、长度为b1=n0的B1型突发错误，要求的防护区间为(13.26)1,2,1,)(0)()(),(0niDDDibianig1,3)2)(1()(1,1)(1()(00iinibiniamnb2)12)(1()1(013.6 岩垂码岩垂码1)12)(1(1)1(00001nnnmnf东南大学移动通信国家重点实验室 H矩阵的首n0列构成了B0阵，一旦B0阵确定，则H矩阵也就确定了。由式（13.23），岩垂码B0阵的首n0 1列中的每列只有两个1，其位置是a(i)和b(i)，第n0列中只有一个1处于第0行即首行。由此B0阵构成的H矩阵，与长度 n0的任何突发错误图样相乘所得的伴随式均不相同，且不为0
47、，满足定理13.6的要求，因此能够纠正任何长度 n0的单个突发错误。13.6 岩垂码岩垂码东南大学移动通信国家重点实验室 例例13.2 设=1，n0=3，k0=2，m=8，构造一个(3,2,8)岩垂码，能够纠正长度为b1=n0=3个码元的任何单个突发错误。分析此岩垂码的编译码方式。解解 码的两个子生成元为：H矩阵为7)3,2(83)3,1()()(DDDDDDgg13.6 岩垂码岩垂码8 7 6 5 4 3 2 1 000101000010000000000001010000101010001000101010000000101010000000101010000000101010000101
48、0000001010001H 东南大学移动通信国家重点实验室 H矩阵的n0(3)列构成了B0阵，阵的前两列中只有两个1，分别位于由a(i)和b(i)决定的行，也即第3、第8行和第1、第7行；而第3列只有一个1，位于第0行。长度为n0=3比特的B1型突发错误图样共有3种情况：0,0,00,00,0,000,121103311030220302011eeeeeeeeeEEE13.6 岩垂码岩垂码东南大学移动通信国家重点实验室,0000000282726252423222120110211020322ssssssssseeeeeTHES,0000000383736353433323130111211
49、120333ssssssssseeeeeTHES ,0000000181716151413121110010201020311ssssssssseeeeeTHES对应的伴随式分别为13.6 岩垂码岩垂码由伴随式S1可知，构成了对e01码元位的两个正交校验和，构成了对e02码元位的两个正交校验和。1813,ss1711,ss东南大学移动通信国家重点实验室 对E2错误图样而言，虽然 能构成对e02码元位正交的两个校验和，但 却不能构成对e01码元位正交的两个校验和。同样，对E3错误图样而言，也不能从 和 构成对e12和e11的两个正交校验和。因此采用一次大数逻辑译码的方法无法纠正B1型码的长度为3
50、的单个突发图样。必须进行分段大数逻辑译码。由H矩阵的表达式可得2721,ss2823,ss3731,ss3833,ss8372511278231212eeeesseess13.6 岩垂码岩垂码构成对第一码段第2信息比特e12的两个正交校验和式。东南大学移动通信国家重点实验室 用上两式的大数判决结果对该码元进行纠错后，该子分组在译码器中进入第0码段位置，由于第2信息元已纠错，错误对该信息元的影响已消除，所以由H矩阵的第4行和第9行可得 它们构成了对第0段码第1个信息比特e01的两个正交校验和式，利用大数准则对该信息比特进行纠错。因此采用这种二次分段大数逻辑译码后，就实现了对e01和e02的纠错。
