《第5章 信道编码（差错控制编码）.pdf》由会员分享，可在线阅读，更多相关《第5章 信道编码（差错控制编码）.pdf（153页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第5卡信差错控制编玛）5.1 信道编玛基本概念5.2 几种常用地检错吗5.3 线性分组吗5.4 循环玛5.5 卷积玛5.6 支狼编玛本章内参小结学习要点信源编彳地概念差错控制编码地分类及其工作原理 常用地检错码 线性分组 循环码 卷积码 交织码学习1点信源编彳当地概念与目地差错控制编码检错与纠错原理 汉明码及编码过程（监督矩阵与生成矩 阵）循环码地编译码方法卷积码地编解码及图解表示来自其他信源信道编码(channel coding)是为了提高通信系统传输可靠性而进行地一种信号变 换。有地文献或书籍也称其为差错控制编码,纠错编码,可靠性编码或抗干扰编码等。本章着重分析信道编码地基本概念,常用纠错
2、码,线性分组码,卷积码等地构造原理及 其应用。5.1.1 是错控制编码概念差错控制编码是检错码与纠错码地总称。具有检测差错能力地编码称为检错码,具有纠正差错能力地编码称为纠错码O差错控制编码地基本思路:在发送端将被传输地信息附上一些多余地码元（称为监督 码元江这些监督码元与信息码元之间以某种 确定地规则相互关联（约束）。接收端则按照既定地规则校验信息码元与监督码元之间地关系,一旦传输发生差错,信息码元与监督码元地关系就受到破坏,从而 接收端可以发现错误乃至纠正错误O研究各种编码与译码方法是差错控制编码所要解决地问题。随着差错控制编码理论地完善与数字电路技术地发展,信道编码已经成功地应用于各 种
3、通信系统中,并且在计算机,磁记录与存储 中也得到日益广泛地应用。5.1.2 是错控制地基本方式差错控制地根本目地是发现传输过程中 出现地差错并加以纠正。X i：差错控制地基本工作方式主要基于两种基本思想:一是通过抗干扰编码,使得系统接 收端译码器能发现错误并能准确地判断错误 地位置,从而自动纠正它优，二是在系统接收 端仅能发现错误,但不知差错地确切位置,无 法自动纠错,需要通过请求发送端重发等方式 达到纠正错误地目地。按照这些基本思想,在数字通信中,利用差错控制编码进行差错控制地基本工作方式 一般分为三种:检错重发,前向纠错与混合纠这些方法地关键是要识别或纠正传输中施差檐 rn 1(a)前向纠
4、错用(b)检错重发用f用?(c)混合纠错图上1_差错控制地基本方式5.1.3 是错控制编码分类差错控制编码有多种分类方法。按照信息码元与附加地监督码元之间地检验关系,差错控制编码可以分为线性码与非线性码。若信息码元与监督码元之间地关系为线性关系,则称为线性码;反之,若两者不存在线性关系，则称为非线性码。按照信息码元与监督码元之间地约束方d式不同,差错控制编码可以分为分组码与卷积在分组码中,编码后地码元序列每n位分为一组,其中k个是信息码元,*个是附加地监督码元,r=n-ko监督码元仅与本码组地信息码元有关,而与其它码组地信息码元无关。卷积码地编码序列也划分为码组,但监督码元不但与本组信息码有关
5、,而且与前面码组地信息码元也有约束关系。按照信息码元在编码后是否保持原来地形式不变,差错控制编码可划分为系统码与非系统码。在差错控制编码中,通常信息码元与监督码元在分组内有确定地位置,般是信息码元集中在码组前k位,而监督码元集中在后有时两者也可以倒置）。在系统码中,编码后地信息码元保持原样不变,而非系统码中信息码元则改变了原有地 信号形式。系统码地性能大体上与非系统码相同,但是在某些卷积码中非系统码地性能优于系统o由于非系统码中地信息位已面目全非,这对观察与译码都带来麻烦,因此很少使用。系统码地编码与译彳玛相对简单些,因而得到了广泛地应用。按照纠正错误地类型不同,差错控制编可以分为纠正随机错误
6、地码与纠正突发错误地码前者主要用于发生零星独立错误地信道,如卫星信道容易出现随机性错误;而后者则用 于对付以突发错误为主地信道,如短波信道或 存储系统。按照构造差错控制编码地数学方法来分类,差错控制编码可以分为代数码,几何码与 算术码。代数码建立在近似代数学基础上才是目前发展最为完善地编码。线性码就是代数码地一个最重要地分支O需要指出地是,在传统地数字传输系统中,纠错编码与数字调制是各自独立设计实现地。目前已把编码器与调制器合成1个统一地整体，这就是所谓地网格编码调制（T）。限于篇幅,本书对此不作介绍。各种分类方法之间地关系如图5-2所示。差错控制编码纠正突发 错误码纠正随机 错误码纠正随机
7、突发错误码5.14差错揖制码基本原理 w-1-科福舄检偌他某洋晨理前已述及,差错控制包括检错与纠错,它们能够有效地检测出通信过程中产生地差错,并进行纠正,从而提高通信质量。通常,原始地待传输地数据码序列本身变化是随机地,一般不带有任何规律性。但是,通过加进冗余码可使其具有某种规律性;在接收端,通过对规律性地检测,就可发现传输中地错误。为了便于理解纠错与检错地基本原理,下面通过一个例子来说明。我们先考察由三位二进制码构成地码组:存位二进制码有8种不同地组合,即 ooonirowjoii,io(rioi,liodiii,我们用这些组合表示8种不同地天气,例如000晴雨雾 zk z(x0011X云雪
8、雹,010八阴,101（霜）,110其中任一码组在传输中若发现错误,则将变成另一码组,由于是其中地一个彳玛组，这时传输错误在接收端就无法发现。，例如选择用彳000100001,010,101 二阴110=雨码组选择其中地4种作为诜通其余4种作为禁用 lllo码组,即本来4种不同信息,用两位二进制码地不同组合表示即可,若用三位表示,则有一位是 多余地,称之为冗余码。用三位二进制码地不同组合表示4种信息,在接收端可用来发现传输中地一位错误。4例如，发送地是000（晴河传输中发生了 土位错误，可能变成001（云）,010（阴）或 ibd（蜀）。H这三个码组都是禁用码组,故接收端收到禁用码组时,就判定
9、传输中肯定发生了错误。当发生三位错误时,000（晴）就变成111（雹），它也是禁用码组，故也能发现三位错 误。但是,这种编码不能发现两位错误,因为错两位后产生地码组是许用码组O上述编码只能用于检测错误,而不能用于纠正错误。例如，当收到地码组是iooR雪）时，收端无法判定是哪一位码发生了错误造成地。因为ooo（晴），由4（雨）阴）三者错一位都可变为100工雪）。要想纠正错误,还需要增加冗余例如,只选用两位码作为许用码组,如000（晴）,111（雹），其余地都是禁用码组口这 样,用三位二进制码代表两种不同地信息,就 有两位码是多余地。此时,收端可以检测两位以下地错误,或纠卡卜社施格膜。T 1例如,
10、当收端收到禁用码组100（雪）时,若认为只有一位错误,则可以纠正为 喇）11 H I I I U H H H因为111（雹）中任何J位错误都不可能索为1g4串）。工但是,若认为错码数不超过两位,则存在两种可能性:000（晴）错一位变为1004国巨 或者111（雹）错两位变为100（雪）士因而只 能检测出有错误码位而无法纠正它O合2.科布易立II中池几个木语（1）冗余度香农定理告诉我们:信源编石当地目地就是去冗余,提高编码地效率。但要注意并不是不压缩地信号抗干扰能力就一定很强,一般地信号都有大量地冗余,但抗干扰能力并不好,主要是因为没有或无法 利用其冗余找到其有关性地规律。因此,要先去掉冗余,再
11、用更有效地编不方法加进冗余,这就是在数字通信过程中为什么要两次编码地原因。所谓冗余就是在信息中附加比特以便于接收端进行错误检测。（2）分组码口Z符无冗余度地信息彳 附加若干位监督码地编彳 丁在分组码中，监督型四分组,为每组信息码 吗,称为分组码。3元仅监督本码组中地（3分组码结构分组码一般可用符号他k）表示,其中n是信息码组地总位数，又称为码组地长度（码W k是每组二进制信息码元地数 g,rln-k为每码组中地监督码元数印分组码地结构如图5-3所示。左个信息位r个监督位图生8分组码地结构;(4)码组重量分组码地一个码组中Q地数目称为不组重量,简称码重。(5)码蹈两个码组对应位上数字不同地位数称
12、石组地距离，简称码距，又称为汉明(Hamming)距离。例如001,016,100,111这4个码组之间,任意两个码组地距离均为2。我们把某种编码中各个码组之间距离地最小值称为1三J，、码距(d0)o图距地几何意义.C6)螂R=匕通常用码率 丁表示码组中信息码所占的比 例，称为编码效率。“在差错控制能力相同的前提下，希望找到编 码效率尽可能高，同时译码方法尽量简单的编码 方法，这是使差错控制编码实用化的关键技术。队最小码距与检纠错能力=J，、码距(dO1决定一种编码地抗干扰能力地大小。因此，最小码距(dO)是信道编码地个重要参数。抗干扰编码理论地研究结果表明,最小码距4d4与检,纠错能力之间满
13、足下列关系。(3)为纠正1个错码，同时检测e个错码，要 求最小码距/4=3(a)(b)(c)5#最小码距与检纠错能力地关系示意图zW5.2.1奇偶监督码（奇偶校验码）奇偶监督码工又称为奇偶校验码）是一种最简单也是最基本地检错码,在计算机数据 传输中得到了广泛地应用。奇偶监督码又分奇监督码与偶监督码,两者编码方法相同,就是在信息码元后面附加一 个监督码元,使得码组中 1地个数为奇数或偶数,奇数时称为奇监督码，偶数时称为偶监，码,统称为奇偶监督码。奇监督码：T-2L苗&二J二维奇偶监督码，又称为水平一垂直奇偶监 督码、方阵码，它是在上述奇偶监督码的基础上 形成的。将奇偶监督码的若干码组排列成方阵，
14、每一 码组排列成一行，然后再按列的方向增加第二维 监督位，如图5-6所示。图中.L以为必行奇偶监督码中的个监督 位，比代为按列进行的第二次编码所增加的 监督位，刀个监督位构成了一监督位行。11 1 1 1Cn-2 I Co2 C-l22Cn-2 Cl2 Co行监督m-1m mCn-2 Clo C-lo oCn-2 Ci列监督0 Co图56三偶监督码其拼咧结构）表5T 二维奇偶监督码（偶校验）列监督码元t.t-1 t 信,息彳玛元仃肯也兀 1010110113010101010010000011000011111000111301001111111100001001111111101100301
15、001110000105.2.3胖计数码把信息码元中中地个数用二进制数字表示,并作为监督码元放在信息码元地后面,这样构成地码称为群计数码。例如,一码组地信息码元为1010111,其中勺地个数为5,用二进制数字表示为 101,将它作为监督码元附加在信息码元之后;即传输地码组为1010111101。群计数码有较强地检错能力,除了同时出现码组中 1 变为0与0变为1地成对错误外,它能纠正所有形式地错误。码字中“1”的数目与“0”的数目保持恒定 比例的码称为恒比码。恒比码是一种检错码，在检测中，只要计算“1”的个数就可知接收码是否有错。国际无线电报码就是一种恒比码，在这种编 码方案中，每码字中有3个“
16、1”(国际无线电报 码，又称为“7”中取“3”码)，共允许用码字 7!/(3!x4!)=35个,它们分别用来代表26 个英文字母及其他符号，如表5-2所示。表52 国际通用地也申取三码字 符码 字字 符码 字A 0011010电0010011B?0011001G1100001C:1001100H1010010D+0011100281110000E30111000J0100011K(0001000X!0010110L)1100010760010101M.1010001Z+0110001N,1010100回车1000011091000110换行1011000P01001010字母键0100110Q
17、10001101数字键0001110R41100100间隔1101000S0101010（不用）0000111T51001010110100U10110010a0101001K=10010010101100W20100101AlJISBN国际缆一书编号际统一图书编号也是一种检错码，主要目地是为了防止书号在通信过程中发生误传。图书编号地格式有统主地规定工口上一节介绍了 一些简单编彳其中奇偶监当地编码原理利用了代数关系式,这类建立 在代数学基础上地编码称为代数码O在代数码中,最常见地是线性码。作为差错控制编码地学习基础,本节讨论线性分组彳口,主要使用矩阵与多项式等数学工具。线性分组码是建立在近代代
18、数基础上地,利用代数关系构造地一种代数码。在(n,k)分组码中,若每千个监督码元都是码组中某些信息码元按线性关系相加得到 地,则称为线性分组码。或者说,用线性方程组表述规律性地分组码称为线性分组码。例如,设某叶(7,分组码为A=a6 a5 a4 a3 a2 alaO其中前三位是信息彳马兀,后I【位是监督码肥元,可以用下列线性方程组来表述,即%。3%=0，%=6%=。6。5%r。0=。6%已知信息码元后，就可直接按式(5-12)计 算出监督位，结果如表5-4所示。表54 发送地汉明码亿4）码字表-7-I I信息码元监督码元信息码元。6“5 14。32 1。0备。5“4 的一0 0 0 00 0
19、010 0 00 0 0 10 1 110 0 1 0 0 101 0 110 100 0 111 1 010 110 10 01 1 0110 0-0 10 11 0 1110 10 1100 1 111100 1110 0 01111监督码元“2 0111100010001001010100111接收端收到每个码组后，先按式(5-8)(5-10)计算出S,&的值，再按表5-4判断 错码情况。例如，若接收码组为0000011,则S=0,S=L&=1由于ssw=on,查表5-3可知悬位有一位 错码。该(7,4)汉明码的最小码距4=3,所以这种 码能够纠正一位错码或检测两个错码。533对一般线性
20、分组1，1.畿钱犍拿袍鹏地摊裨构闽在了解了汉明码地基本构造后,下面对线性分组码地一般原理进行讨论。前已述及,线性分组码是指信息位与监督位满足一组线性方程关系地码O(5-1 1)就是这种线性方程,现将式(5-1 1)改写为1。6 1%1,。4 。3 1.。2 。0=01%1，%0，。41，的。，。21%0%=D，1,4%1。4 1 “3 “2 ”1 1 “0=0，上式还可以简记为HA TOT或1A HT=O式中H称为监督矩阵，只要监督矩阵H给定,编彳得时监督位与信息位地关系就完全确定。上面H矩阵也可以分成两部分,即H=1rxr阶方阵.1 1 0 I 1 0 0I1 0 1 I 0 1 0=也rx
21、k阶矩阵.其中,P为r/k阶矩曲r为口阶方阵,将具有prf形式地H矩阵称为典型阵。式(512)也可以改写成%9,1110、=110 1Mon/IX%或者zi i r11 o=0 =。6牝43。0 1 b式中，Q为一 Er阶矩阵，它为尸的转置，即。=产式(5-19)表明，信息位确定后，用信息位的行矩阵乘矩阵Q就可产生监督矩阵。将Q的左边加上一个人上阶单位方阵就构成一矩阵G,即r 1 o o o 111 aG=.IkQA 0 10 0 1100 0 10 10 110 0 0 1 0 1 1JG称为生成矩阵，因为由它可以产生整个码组，即有。6%a4 a3 al al 他=。6 a5 a4 3G 或
22、者/=。6。5。4 3.GBEM因此,若找到了码地生成矩阵G,则编码地方法就完全确定了。具有IkQ形式地生成矩阵称为典型生成矩阵由典型生成矩阵得出地码组A中,信息位不变,监督位附加其同这种码被称为系统码。2,一皴钦辘争做居地检辐能力发送码组在传输过程中可能由于干扰引入 差错,则接收码组一般来说与发送码组不一定 相同。设接收码组为一n列地行矩阵B,即B=bn 1 bn 2,bO则发送码组A与接收码组B之差,即b；Ha O（模2）式中E就是传输中产生地错不3行矩阵E,设E=en-1 en-2 eO若ei=0,表示该位无差错;若ei=1,表示该位接收码元有错。这样式(5-24)也可以写成bU k 4
23、&I(棋，生)钱植令做妈地重要11111111浚性分组码地一个重要性质就是它地封闭性。所谓封闭性工是指一种线性码中地任意两个码组之与仍为这种码地一个码组。这就是说,若如与A 2是十种线性码中地两个许用码组,贝！|(A 1+A 2)仍为其中一个码组。既然线性分组码具有封闭性,因而两个码组之间地距离必是另一码组地重量。故码地最小距离即是码地最小码重(除全0码组外)。循环码是线性分组码地一个重要分支O1957年,普兰奇(P range)最早提出循环码地概念,在其后地20多年中,人们对循环码 地代数结构，性能与编译方法等方面进行了大 量地研究,并取得了许多重要成果,从而大大 推动了循环码在实际差错控制
24、系统中地应用o由于循环码有许多特殊地代数性质,特别是它地编译码器易于实现,而且综合性能良好,目前其编码,译码,检测与纠错已由集成电路 产品实现,其速度与软件算法相比大大地提高 了,是目前通信传送系统与磁介质存储器中广 泛采用地一种编码。5.4.1循环码地代数结构循环码是一种系统分组码，它除了具有线性分组码地封闭性外，还具有循环性O循环性是指任一许用码组经过循环移位后所得到地码组仍为一许用码组。若C=clc2 T是一个循环码组，一次循环移位得到C(1)二心2 c3cl也是许用码组，移位i次得到CRi)上回也值讦衣同巾ci也是许用码组。不论右移或左移,移位位数多少，其结果均为循环码组。基于循环移位
25、的特性，使用多项式描述其性 质是很方便的。码组。与多项式之间的关系，可用下式表示C（K）=+L+cn上式C（x）称为码多项式，变量X表示多项式 的元素，它的幕次对应元素的位置，它的系数对 应元素的取值，系数之间的加法和乘法运算服从 模2运算。码组。移位1次得到。仍是码组，相应的 码多项式小X)为c(1)(x)=c.x1+c3xra-2+L+cnx+cY(5-32)式(5-32)正好是xc(x)除以3+1)后得到 的余式，即x-c(x)=+c1xn1+L+cnx-+1)+(x)(-33)上述结论可用竖式进行验算，计算过程如下 _xl+1 cxxl+c2xJl i+L+cnxn,cxx+qc2x/
26、-1+L+cnx+.I 余式依此类推，码组。移位/次，相应的码多项式心&）是/（星）除以（父+1）后的余式。因此，在模夕+1）意义下，若。（X）是码多项式，则k c（x）都是码多项式。循环码的编码过程同样可以用多项式来描 述。=一个k位的信息码组可用信息码D=4,4可用信息多项式(%)表示，有 一 或)=4，一1+%/一？+4(534)一若已知一(X),求解相应的码组多项式C(x),就构成了编码问题。假设码组多项式可表示为 c(x)=d(%)g(x)(5-35)式中g(x)是(父+1)的刀-左次因式，称为生成多项式。二将式(5-34)代入式(5-35),得c(x)=dlxklg(x)+d2xk
27、2g(x)T-卜 dkg(x)再将式(5-35)表示的码多项式c(x)提高1次，得x.c(x)=x-g(x)(5-36)根据式(5-33)提供的另一表达式为 x-c(x)=+1)+c(x)E 由于前面已假设(4+i)是g(力的倍式，所以E 产(%)也是g(x)的倍式,可以表示为。=4(%)g(x)(5-37)二 式中d(x)对应于某个信息码组。-因此，以上分析过程说明用式(5-35)产生二 的码组一定是循环码。循环码的校验能力很强,既能检测随机差错，又能检测突发性差错，其检错性能如下：二(1)能检测出全部单个错误；二=(2)能检测出全部随机的两位错误；三二(3)能检测出全部奇数个错误；二二(4
28、)能检测出全部长度小于攵位的突发性错二误；(5)能以”片的概率检测出长度为(4+1)位的突发性错误。蜀踪福维渴器 如前所述,循环码地编码需要将一个多项式除以另一个多项式,这种操作是由多项式除法运算完成地,在硬件上是由多项式除法电路（带反馈地移位寄存器）实现地。M有两种不同地除法电路一种采用内接 地异或（或模2号）电路;另一种采用外接 地算匐电蝌 口口在实际应用中,地除法电路。通常采用内接异或门电路内接异或门电路除法电路地工作过程与采用手算进行长除法地过程完全一致,每当一个 勺移出寄存器进入反馈线时,相当于从被除 式中减去除式由里地减也是模2与）；一般来说,译码器通常要比编码器复杂得多,特别是对
29、纠错能力强地纠错码更是如此。因此,对纠错码地译码研究主要集中在算法上。如前所述,校正子与错误图样之间存在某循环码地译彳可以分以下三步进行(1)由接收地码多项式r(x)计算出校正子(伴随式)多项式0(x);可一(2)由校正子k伴随式)多项或s9确耨快鼾电k“n 口3)将错误图样4(x)与r(x加加,纠正错误。为简化校正子地计算,上述校正干(伴随式)多项式s(X)可以用接收到地码多项式r(x)除以生成多项式g(X)所得到地余式O用除法电路作校正子计算电路或有一个重要性质:某码组循环移位i次地校正子等于 原码组校正子在除法电路中循环移位i次所得地结果。令S(x)为码多项式/(%)循环移位/次后计 算
30、得到的校正子，即而裕KG mod gx)南三向 mod g(x)(5-42)(5-43)(5-44)s(x)循环移位？次，有得三山 mod gx)-将式(5-44)减去式(5-42)得 金乳力-乳X)三。mod gx)即 虱乃三mod g(x)(5-45)卷积码（又称连环彳冯M是1995年由麻省理工学院地伊利亚斯（P.Elias）提出地。它与前面所介绍地汉明码与循环码等分组码不同,卷积码是一种非分组码,卷积码在 编码过程中充分利用各码组之间地有关性,其 性能要优于分组码,而且实现简单,因此在通 信领域应用越来越广泛。在以计算机为中心地数据通信系统 卷积码主要应用于前向纠错（FEC）。卷积码编码
31、地一般形或分组码是在任何一段规定时间内把k个信息比特地序列编成n个比特地码组,每个码组 地(n-k)个监督位仅与本码组地k个信息位有 关,而与其它码组无关。卷积码编码地一般结构如图5-12所示,它包括一个由N段组成地输入移位寄存器,每段 有k级,共Nk位寄存器;一组N个模2加法器;二 个由N级组成地输出移位寄存器,对应于每段 kbit地输入序列,输出Nbit由图5-12可知,卷积码是把kbit信息段编成nbit地码组,所编地n长码组,不仅取决于当 前地k个信息码元,而且还取决于前(N-1)个信息段,编码过程中相互关联地k个码元为Nn个J|t这时，监督后监督着这N段时间内地信息。这N段时间内地码
32、元数目Nn称为这种卷积码 约束长度。注意约束长度地定义没有统一地标准,地有地书或文献把N或(N-1)称为约束长度。通常把卷积码记为(n,k,N),其编码效率为R二 k/no2N1图舁w卷粗码编码器地二般形式5.5.2卷积码编码器地工作原理F面用一个简单例子说明卷积彳码地编码原理。图5-13所示地电路是一个简单地(2,1,3)卷积码地编码器,它由有两个触点地转换开关与一组3位 移位寄存器ml,m2,m3及模2相加电路组成。编码前各移位寄存器清零,信息码元按顺序ala2aj依次输入到编码如每输入=个信息码元或一开关依次为接到每*个触点各一次。如图5-13所示,编码器每输入一个信息码元,经该编码器后
33、产生2个输出比特。输入序列图曰3（如卜3熠积码编码器假设该移位寄存器地起始状态全为零,编码器地输出比特clc2表示为cl=ml+m2+m3 c2=ml+m3其中,ml表示当前地输入比特,而mlin2表示存 唐钿帆曲峭眼当第一个输入比特为1时,即ml因1 1 1 31 n2=100,所以输出clc2=11,这时朝二u m3喟=01,clc2=01,依此类推,为保证输入 地信息1 1 01 0都能通过移位寄存器,还需要 在输入信息位后填加3个0。二为了说明编码圈地状态，采用如图所示地图解方式给出整个编码器地工作过程。图易 1 博鹤43）卷积码编码地过程图解（输入自上而下为帆。聊）-1-|-.I合输
34、入0001A+2=1。图蜀卷积码编惇地过程图解Y输入自上而F为T101皿将上述编码过程列成表格形式,如表5-8所示列出了它地状态变化过程O表5名（毒1,3）卷积码编码器地状态变化过程增加3个0mi11010000m3m2000111100110000011010010110000状态表示abdcbcaa卷积码地图；描述卷积码地方法有两类:图形表示与解析表示。本节仅介绍卷积码地图形描述OM树囹编码器中移位过程中可能产生地各种序列可以用树图来表示,如图5-15所示。输入信息码元序列。出状 态d=110000-a01a11eg00输入比特夕移位后的状态 I0010b 0100a 1110 b 011
35、1。0001 d 10O a Ob Oc O d。aO b O c Cd上半部00a 1110b 01O b 0 c。d JO a Ob O c Qd O a卜下半部图年15(2a3)卷积码地树图ALd2,从卷积码地树图可以看出,存在着重复性,据此可以得到更为严重紧凑地图形表示O在网格图中,把码树中具有相同地节点合并在起,码树中地上支路对应于输入比特01用实线表 示;下支路对应于输入比特1,用虚线表示。网格图中支路上标注地码元为输出比特，自上而下4行节点分别表示四种状态,如图5-16所示。一般情况下有2N+1种状陶从第N巧（从左向 右计数）开始,网格图图形开始重复而完全相同工10 10 108
36、回C回d|n|图蜀卷粉码地网格整Aw3.献态囹从树图地第三级各节点状态与第四级各仲簸间地关系,或者取出已达到稳定状态地一节网格(如图5-16中第三级到第四级节点间地一节网格)，就可将当前状态与“一个状 态之间地关系用状态图来表示，如图5V7(a)漏。口图中实线表示输入比特为0地路径,虚线 表示输入比特为1地路径,并在路径上写出了相应地输出码元;再把当前状态与下一个状态重叠起来,即可得到哪-17(fbi所示地反映状态转移地状态图。在图51 7(b)附四个节点,即a,b,c与 d,其对应取值与图5T 7(a)相同。每个节点有两条离开地弧线,实线表示输入比特为0,虚线表示输入比特为1,弧线旁地 数字
37、为输出码元。力 当输入比特为11010时，状态转移过程为 a-b-d+c-b,相应地输出码元序列为 11010100.土图3里乙（号四蜀卷积码地状态图口 由以上可见,当给定输入信息比特序列与 起始状态时,可用上述三种图解法,找到输出 序列与状态变化地路径。5.5.4卷积码地维特比注码卷积码地译码方式有3种:维特比译码,序列译码与门限译码。限于篇幅,本节只介绍维特比译码。维特比译码算法是由维特比在1967年提出地,该算法地实质是最大似然译码,它利用 了编码网格图地特殊结构,从而降低了计算地 复杂性。维特比译码算法考虑地是如果有两条路径到达同一状态,则具有最佳量度地路径被选号称为聿存路华。对所有状
38、态都进行这样地选路操作，译器不断地在网格图上深入,通过去除可能性最 小地路径实现判决。为了更好地理解卷积码译码地过程，仍以图5-15所示地(2,1,3)卷积码编石当为例。为方便起见,假设经(2,1,3)编码器输出序列X为全。码(不失一般性)，接收序列为Y 二001 001 000000-4 o对照编码器输出序列,则接收序列是误码序列,即卷积码输出序列X:00 00 00 00 0000 00100接收序列Y:；1 影羸分为误棺)汉明距离(或路径度量)接收 y-o o 5/_-1起始点 0*-*0(0)/X/b0、加(2)(a)接收 y=o o io o i00。1(0)00。2 00。3(2)
39、一起始点-r 区 起始点7 7 x/ii、2(1)/乂、v w嚼C，-2)S-g1 01/凶d2(4)V-10 接收y=o o io00 6(0)00 a2(1)起始点。0弋-,11 11。V SCl(2)c2(2)S(b)接收 y=o o io。o o00 0(0)00 00 67,(2)00 处(2)俏*-y-弋-1-r悦“x X弋八力 z)2(l)7-3(2)/、&砥犷 V、7,、C、10 10 X/JO白。2出/破 弋吗01 0!/色(4).V-t_L图多19 维特比译码过程地网格图示1001o oo o接收y=o o5T9维持比隆码过程地网格图如续zW接收 y=o o 10 01 o
40、 o o o o o o o o o起始点维特比隆码过程地网格图心续接收 y=o o 10 01 o o o o o o o o o o o o起始点制.11仿0010C400隼(2)002(2)00啜 00 的11%00。1(0)00。2 00。3 00处(2)00。5000101。心嘿 c8(v常用地检错彳冯有:奇偶监督而（奇偶校验码），三维奇偶监督码,群计数彳，恒比不3与IS BN国际统一图书编码。线性分组码是建立在近似代数基础上地,利用代数关系构造地一种代数码。在(n,k)分组码中,用线性方程组表述规律性地分组码称为线性分组码O线性分组码是一类重要地纠错码,应用很广泛。(1)汉明码汉明
41、码是第一个用于纠正一位错码地效率较高地线性分组码。一般来说,若码长为n,信息码元位数为k,则监督码元位数为r。若要用r个监督位构造能纠正一位或一位以上错误地线性码,则需要满足2,一 1 2%2三上+/+1般线性分组码地矩阵构成HAT=OTT 或 A；HT=O Q=PT(3)一般线性分组码地检错能力设接收码组为一 n列地行矩阵BB=bn-1 bn-2 bO则发送码组A与接收码组B之差为BA E（模 2）式中E就是传输中产生地错码行矩阵E,设EL=en-1 1 en-2T eO 不若ei=0,表示该位无差错;若ei=1,表示该位接收码元有错。5,循林鸠环彳循环码是线性分组码地一个重要分支。循吗是一
42、种系统分组码,它除了具有线性分组码地封闭性外,还具有循环性。-1。)循笏码地编码 1 rn rrrm u u h u u u u 一一个上位的信息码组可用信息码二4&4可用信息多项式d(x)表示，有d(x)=4九 J+心力-2,|-卜人若已知d(x),求解相应的码组多项式C(x),假设码组多项式可表示为c(x)=d(xg(x)式中g(x)是(4+1)的刀-左次因式，称为生成二多项式。二z 循环码完全由其码组长度n及生成多项式二g(x)决定。(2)循环码译码循环码地译码可以分以下三步进行:由接收地码多项式r(x)计算出校正子伴随式)多项式s(xX n由校正好(伴随式才多项式也)确定 错误图样e(
43、x);将错误图样e(x)与r(x)相加，凶工错误。Or”筑环码地检错性能循环码的校验能力很强，既能检测随机差错,又能检测突发性差错，其检错性能:能以口心尸的概率检测出长度为（4+1）位的突发性错误；Z 能检测出全部长度小于左位的突发性错误;二能检测出全部奇数个错误；二 能检测出全部随机的两位错误；能检测出全部单个错误。卷积码是把k比特信息段编成n比特地码组o所编地n长码组,不仅取决于当前地k个信息石马兀,而且还取决于前(N 1)个信息段,编码过程中相互关联地k个码元为Nn个。这时,监督位监督着这N段时间内地信息。这N段时间内地码元数目Nn称为这种卷积码地约束长度。通常把卷积码记为(n,k,N),其编码效率为R=k/no描述卷积码地方法有两类:图形表示与解析表示。