《纠突发错误码》PPT课件.ppt
《《纠突发错误码》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《纠突发错误码》PPT课件.ppt(65页珍藏版)》请在三一办公上搜索。
1、第十三章纠突发错误码,本章内容提要,纠突发错误码的定义和基本性质法尔码交错码伯顿码纠突发错误卷积码岩垂码纠突发错误循环码的译码纠突发和随机错误码,大部分实际信道如短波、散射、有线等信道中产生的错误是突发性的;某些数据存储系统所产生的错误,大部分也是突发性的,而不是随机性的。这些信道中所产生的错误是突发错误,或突发错误与随机错误并存,通常称这类信道为突发信道。循环码检测突发错误能力强,但纠错效果不大。人们希望能设计出一类专门用作纠突发错误的码,这类码称为纠突发错误码。这类码在纠突发错误时的效率应比对付随机错误而设计的码要高,即对于给定的n和k,(n,k)有尽可能小的多余度,或者说n k 尽可能小
2、。,第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)个,证毕。,定理13.2 一个(n,k)线性分组码,能发现长度
3、不大于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的突发错误的充要条件是:长度 2b的突发不是一个码字。证明假设存在一个长 2b的突发v是一个码字,则 v=u+w,其中 u、w都是长度 b的突发。必要
4、性:若v是码字,因任意一陪集只有一个错误图样,则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)证毕
5、。由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的任何突发错误,包括首尾相接的突发错误。证明:设错误图样e(x)是长度 n k的突发错误,则e(x)可表示为 e(x)=x jB(x),0 j n 1 式中,B(x)是次数 n k 1的多项式。由于B(x)的次数小于循环码生成
6、多项式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,则,由于它的次数小于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.1
10、1)由于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)互素。已假定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)定义
11、的g(x)生成的法尔码的不同陪集中,因而它们是可纠正的错误图样。由于码是循环的,所以它亦能纠正长度 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。因此,相对于赖格尔限而言,法尔码的效率并不是很高。能够纠正
12、任何长度为b或更少的突发错误、并同时检测长为l b的任何突发的法尔码,可用下式生成:该码长度等于和b+l 1的最小公倍数。,交错是一种非常简单而又有效的构造码的方法,它可以大大提高纠随机错误码的纠突发错误能力,可使抗较短突发错误的码变成抗较长突发错误的码,使纠正单个定段突发错误的码变成纠多个定段突发错误的码。这种方法所付出的代价是增加存储设备和加大通信时延。,13.3交错码,将个(n,k)码的码矢排成 n的矩形阵列,每行一个码矢,然后按列送至通信信道,在收端恢复矩形阵列的排列次序,就构成交错度为的交错码。即给定一个(n,k)循环码,用交错法将码长扩大倍,信息位数目也扩大了倍,构成一个(n,k)
13、循环码,见图13.1。,图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)交错技术是一种等效长码的
16、技术。根据Shannon第二定理,必然有更好的性能。,伯顿发现一类纠正定段突发错误的循环码。考虑一(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),1
20、3.5 纠突发错误卷积码,如果将连续两个突发错误之间的无误区间定义为防护区间,则对于不同型的码要求有不同的防护区间。如果译码约束长度是n0(m+1),则B1型码的防护区间长度f1为(13.19)而B2型码所要求的防护区间长度f2则为(13.20)B1型码和B2型码都属于无误纠突发错误码,能纠正长度分别 b1和 b2的全部突发错误。纠突发错误卷积码通常都是指无误纠突发错误码。还有一类纠突发错误卷积码,虽然不能纠正长度 b的所有突发错误,但能纠正其中绝大部分错误,即能以很小的译码错误概率纠正长度 b的突发错误,这类码称为有误纠突发错误码。,13.5 纠突发错误卷积码,定理13.6(n0,k0,m)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 纠突发错误码 突发 错误 PPT 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5641140.html