第14讲_组合逻辑设计

《第14讲_组合逻辑设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、于给定的n和k，(n,k)有尽可能小的多余度，或者说n–k尽可能小。第13章　纠突发错误码定义13.1长为b的突发是针对错误图样来定义的：如果一个矢量的非零分量局限于b个连续数据位，且第一和最后一位是非零的，则称该矢量为一个长为b的突发。一个线性码如能纠正长为b或更短的突发错误，但不能纠正长为b+1的所有突发错误，则称此码是一个纠b长突发错误码，即该码的纠错能力为b。13.1纠突发错误码定义和基本性质13.1.1定义定理13.1长n的二元码字中，突发长度不大于b的码字的总数N=2b-1(n+2–b)。证明在长为n的二元码字

3、中，考虑b为各种可能值的情况（突发字个数）如下：b=01个（0,0,…,0）1n个2n–1个32(n–2)个…13.1纠突发错误码定义和基本性质13.1.2基本性质证毕。定理13.2一个(n,k)线性分组码，能发现长度不大于b的错误图样的条件是n–kb–1+lb(n+2–b)证明由于对于所有的错误图样，若s≠0则能被发现，(n,k)线性分组码的陪集数为(2n–2k)/2k=2n–k–1相应的，在陪集中总错误图样数为长度b的突发错误图样：2b–1(n+2–b)所以2n–k–12b–1(n+2–b)一般有2n–k>>1,

4、nb所以n–k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是码字，因任意一陪集只有一个错误图样，则u和w必在同一陪集中。设u为陪集首，则陪集中每一个字的错误都是此陪集首，w必为不可纠错误，否则不可能与u同在一个陪集。这样尽管v是一“码字”，但它是一个错码

5、，与假设v是一码字矛盾，因此把u作为陪集首来纠错也是无效的，即它不能纠正所有长b的突发错误。充分性：若长度2b的突发v不是码字，则u、w不在同一陪集中，若它们都是陪集首，则都是可以纠正的长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+2–2b)1，代入定理13.4得n-k2b。表述为：(1)一个(

6、n,k)线性分组码，若要纠正所有长度b的突发错误，则应n–k2b。(2)（n,k）码的纠突上限为，称为赖格尔限。满足赖格尔限的码是最佳的。(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)=xjB(x)，0jn–1式中，B(x)是次数n–k–1的多项式。由于B(

7、x)的次数小于循环码生成多项式g(x)的次数，因此B(x)不能为g(x)所整除。又因为g(x)是xn–1的因式，因此g(x)与xj互素。因此g(x)也不能整除xjB(x)。因此，由此e(x)产生的伴随式不为零。即一个(n,k)循环码能检测长n–k的任何突发错误。13.1纠突发错误码定义和基本性质13.1.2基本性质对于长度n–k的突发错误图样，当它的错误局限在前i位和后l–i位时，即出现首尾相接的错误时，有13.1纠突发错误码定义和基本性质13.1.2基本性质如果将它乘以xl-i,则由于它的次数小于g(x)的次数，所以

8、它的伴随式不为零。又由于xl-i与g(x)互素，因此g(x)不能整除e(x)，即e(x)=f(x)g(x)+s(x)，而s(x)0。所以(n,k)循环码也能检测长度n–k的首尾相接的突发错误。证毕。法尔码是最早也是最大的一类用分析方法构造出的纠单个突发错误的二进制循环码。由于可以根据不同的要求很方便