信息论与编码第六讲精.ppt

《信息论与编码第六讲精.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第六讲精.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第六讲第1页，本讲稿共74页主要内容主要内容卷积码的基本概念卷积码的基本概念卷积码的描述卷积码的描述卷积码的特性卷积码的特性第2页，本讲稿共74页5.1 卷积码的基本概念卷积码的基本概念第3页，本讲稿共74页卷积码是一个有限记忆系统。当信息序列切割成卷积码是一个有限记忆系统。当信息序列切割成长度为长度为k的分组后，分组码单独对各分组编码，而卷的分组后，分组码单独对各分组编码，而卷积码不仅根据本时刻的分组，而且根据本时刻以前的积码不仅根据本时刻的分组，而且根据本时刻以前的L个分组共同来决定编码。个分组共同来决定编码。由于编码过程受由于编码过程受L+1个信息分组的制约，因此称个信息分组

2、的制约，因此称L+1为为约束长度约束长度。约束长度是卷积码的一个基本参数，约束长度是卷积码的一个基本参数，常用常用(n，k，L)来表示某一码长来表示某一码长n、信息位、信息位k、约束长度、约束长度L+1的卷积码。的卷积码。第4页，本讲稿共74页卷积编码器卷积编码器（线性组合器）（线性组合器）ci0c i1c in-2c in-1第第i分组分组第第i-1分组分组第第i-2分组分组第第i-L分组分组mi0mi1mi k-1mi-10 m i-1k-1mi-20mi-2k-1mi-L0mi-L1m i-Lk-1输入输入编码输出编码输出Ci图图5-1卷积编码示意卷积编码示意第5页，本讲稿共74页串串/

3、并并变变换换并并/串串变变换换线线性性组组合合器器m i0mi-10mi-20mi-L0mi1mi-11mi-21mi-L1m i k-1m i-1k-1mi-2k-1m i-Lk-1信号入信号入Mi编码编码输出输出Ci图图5-2卷积编码器的一般结构卷积编码器的一般结构第6页，本讲稿共74页 图图5-2记忆阵列记忆阵列中的每一存储单元都有一条连线将数据中的每一存储单元都有一条连线将数据送到线性组合器，但实际上无需每个单元都有连接。因为送到线性组合器，但实际上无需每个单元都有连接。因为二元域线性组合时的系数只能选二元域线性组合时的系数只能选“0”或者或者“1”，选，选“0”时时表示该项在线性组合

4、中不起作用，对应存储单元就不需表示该项在线性组合中不起作用，对应存储单元就不需要连接到线性组合器。从图上看到，每一个码元都是要连接到线性组合器。从图上看到，每一个码元都是k(L+1)个数据线性组合的结果，需要有个数据线性组合的结果，需要有k(L+1)个系数个系数来描述组合规则，于是每一个码字需用来描述组合规则，于是每一个码字需用nk(L+1)个系个系数才能描述。显然，只有将这些系数归纳为矩阵才能理数才能描述。显然，只有将这些系数归纳为矩阵才能理顺它们的关系。顺它们的关系。第7页，本讲稿共74页设设（n,k,L）卷卷积积码码在在时时刻刻i及及i之之前前L个个时时刻刻的的输输入入、输输出矢量分别是

5、：出矢量分别是：时刻时刻输入矢量输入矢量(信息信息)输出矢量输出矢量(码字码字)i Mi=(m i0,m i1,mik-1)Ci=(c i0,c i1,c in-1)i-1Mi-1=(mi-10,mi-11mi-1k-1)Ci-1=(ci-10,ci-11ci-1n-1)i-L Mi-L=(mi-L0,mi-L1mi-Lk-1)Ci-L=(ci-L0,ci-L1ci-Ln-1)这这里里,大大写写字字母母表表示示码码组组，小小写写字字母母表表示示码码元元，上上标标表表示示码码字中的码元顺序，下标表示时序。字中的码元顺序，下标表示时序。在在任任意意时时刻刻i,卷卷积积码码码码字字的的第第j个个码码

6、元元是是约约束束长长度度内内所所有有信息比特的线性组合，写作：信息比特的线性组合，写作：第8页，本讲稿共74页j=0,1,2,n-1(5-1)式中，式中，0,1表示图表示图5-2中第中第l列（列（l时刻的信息组时刻的信息组,l=0,L）、第）、第k行（信息组的第行（信息组的第k个码元，个码元，k=0,K-1）对第）对第j个输出码元的影响。个输出码元的影响。=0表示该位不参与线性组合，表示该位不参与线性组合，=1表示该位参与线性组合。表示该位参与线性组合。第9页，本讲稿共74页例例5.1某某二二进进制制(3,1,2)卷卷积积编编码码器器如如图图5-3所所示示，写写出出表表达其线性组合关系的全部系

7、数。达其线性组合关系的全部系数。解解：本本例例为为码码率率R=1/3的的卷卷积积码码，n=3,k=1,L=2。由由编编码器电路图，可写出码器电路图，可写出nk(L+1)=9个系数如下：个系数如下：=1=0=0=1=1=0=1=1=1信号信号 c i0入入M i输出输出 ci1Ci c i2图图5-3二元二元(3,1,2)卷积编码器卷积编码器mi0mi-10mi-20输入信息行输入信息行时延列时延列输出码元行输出码元行第10页，本讲稿共74页例例5.2某某二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，写写出出表表达达线线性组合关系的全部系数。性组合关系的全部系数。解解：本本例例为

8、为码码率率R=2/3的的卷卷积积码码,n=3,k=2,L=1。由由编编码码器电路图，器电路图，可写出可写出nk(L+1)=12个系数如下：个系数如下：=1,=1,=0,=1=0,=1,=1,=0=1,=1,=1,=0输入信息行输入信息行时延列时延列输出码元行输出码元行 c i0信号信号Ci入入M i ci1输出输出 c i2图图5-4二进制二进制(3,2,1)卷积编码器卷积编码器mi0mi-10mi1m i-11第11页，本讲稿共74页上面两例表明：上面两例表明：从已知的编码电路可以找出对应的系数从已知的编码电路可以找出对应的系数 ，反之，反之，已知系数已知系数 即可画出相应的编码电路。即可画

9、出相应的编码电路。因此，从电路结构角度，因此，从电路结构角度，(5-1)是很好的表达形式。是很好的表达形式。但是，通常需要从另外各种不同的角度去研究卷积码，但是，通常需要从另外各种不同的角度去研究卷积码，或侧重于卷积码的物理意义，或强调卷积码的距离特性，或侧重于卷积码的物理意义，或强调卷积码的距离特性，或研究编码器的状态变迁。或研究编码器的状态变迁。在不同角度，存在着描述卷积码的不同方法。以下介在不同角度，存在着描述卷积码的不同方法。以下介绍四种绍四种卷积码的描述方法卷积码的描述方法：生成矩阵表示法生成矩阵表示法，转移函数转移函数矩阵表示法矩阵表示法，状态流图法状态流图法，网格图表示法网格图表

10、示法。第12页，本讲稿共74页5.2 卷积码的描述卷积码的描述第13页，本讲稿共74页5.2.1生成矩阵表示法生成矩阵表示法由式由式(5-1)，CiT=+1-nic第14页，本讲稿共74页=+=求转置，上式写成：求转置，上式写成：(5-2)式中，式中，G0、G1、GL是是kn矩阵，称作矩阵，称作生成子矩阵生成子矩阵：Gl=l=0,1,L(5-3)第15页，本讲稿共74页时刻时刻i=0C0=M0G0时刻时刻i=1C1=M0G1+M1G0时刻时刻i=2C2=M0G2+M1G1+M2G0 时刻时刻i=LCL=M0GL+M1GL-1+ML-1G1+MLG0时刻时刻i=L+1CL+1=M1GL+M2GL

11、-1+MLG1+ML+1G0式式(5-2)可写成：可写成：(5-4)式式(5-4)说说明明：输输出出码码字字Ci是是i时时刻刻之之前前(含含i时时刻刻)的的信信息息组组(Mi Mi-1Mi-L)与与生生成成子子矩矩阵阵组组(G0 G1 GL)的的卷卷积积，这这也就是卷积码名称的来历。也就是卷积码名称的来历。(5-2)第16页，本讲稿共74页令令 G0G1G2 G L 00 g G=G0G1G2 GL 0 =Dg (5-6)G0G1G2 GL 0 D2g 定义定义g 为为基本生成矩阵基本生成矩阵，定义定义G 为为生成矩阵生成矩阵。若若码码字字序序列列是是一一个个从从0时时刻刻开开始始的的无无限限

12、长长右右边边序序列列，可可写写成有头无尾的半无限矩阵形式：成有头无尾的半无限矩阵形式：C=(C0,C1,，CL,CL+1,）G0 G1 G2 GL 0 =(M0,ML,ML+1,)G0 G1 G2 GL 0 (5-5)G0G1G2 GL 0 第17页，本讲稿共74页例例5.1(续续1)二二进进制制(3,1,2)卷卷积积编编码码器器如如图图5-3。如如果果输输入入信息流是信息流是(101101011100),求输出码字序列。求输出码字序列。解解：对对照照例例5.1算算得得的的系系数数及及式式(5-3)生生成成子子矩矩阵阵的的定定义义，可知本题可知本题G0=111，G1=011G2=0011110

13、11001111011001Ci=(101101011100)111011001111011001=(111,011,110,100,010,110,011,110,100,101,010,001)第18页，本讲稿共74页例例5.2(续续1)某二进制某二进制(3,2,1)卷积编码器如图卷积编码器如图5-4,若输入若输入信息流是信息流是(101101011100)，求输出码字序列，求输出码字序列解：对照例解：对照例5.2算得的系数及式算得的系数及式(5-3)生成子矩阵的定生成子矩阵的定义，可知本题义，可知本题G0=，G1=于是于是101111011100C=(10,11,01,01,11,00)

14、101111011100101111011100=(101,001,000,111,010,011,)101011111100第19页，本讲稿共74页5.2.2 多项式及转移函数矩阵表示法多项式及转移函数矩阵表示法 若若M(D)=m0+m1D+mkDk+mk+1Dk+1+m2kD2k+m2k+1D2k+1+，则串则串/并变换后并变换后M 0(D)=m0+mk D+m2kD2+M 1(D)=m1+mk+1 D+m2k+1D2+MP(D)CP(D)M0(D)C0(D)M1(D)C1(D)M(D)C(D)Mk-1(D)Cn-1(D)图图5-5卷积码的转移函数矩阵卷积码的转移函数矩阵串串/并并卷积卷积

15、编码器编码器G(D)并并/串串第20页，本讲稿共74页卷卷积积编编码码器器可可视视作作一一个个k端端口口入入、n端端口口出出的的线线性性多多端端口口网网络络，可可以以用用转转移移函函数数矩矩阵阵来来描描述述输输入入、输输出出间间关关系系。由由于于卷卷积积编编码码器器其其输输入入、输输出出均均是是无无限限长长多多项项式式，因因而而转移函数矩阵元素也是多项式。转移函数矩阵元素也是多项式。定义输入、输出定义输入、输出多项式矩阵多项式矩阵MP(D)、CP(D)为：为：M(D)串串/并并MP(D)=M 0(D),M 1(D),M k-1(D)C(D)串串/并并CP(D)=C 0(D),C 1(D),C

16、n-1(D)这里，这里，MP(D)、CP(D)的下标的下标P表示表示“并行并行”。虽然虽然M(D)和和 MP(D)数量上有对应关系，然而在数学上数量上有对应关系，然而在数学上有不同含义，有不同含义，M(D)是多项式而是多项式而MP(D)是矩阵。是矩阵。第21页，本讲稿共74页编码器编码器k路输入和路输入和n路输出之间的转移关系为路输出之间的转移关系为 CP(D)=MP(D)G(D)(5-8)G(D)是是kn转移函数矩阵转移函数矩阵，g00(D)g10(D)gn-10(D)G(D)=g01(D)g11(D)gn-11(D)(5-9)g0k-1(D)g1k-1(D)gn-1k-1(D)矩阵矩阵G(

17、D)的第的第 i 行第行第 j 列元素列元素gj i(D)描述了第描述了第i个输个输入支路如何对第入支路如何对第j个输出支路产生影响的转移关系，也称个输出支路产生影响的转移关系，也称子子多项式多项式，而第，而第j个输出支路最终的输出由全体个输出支路最终的输出由全体k个输入支路个输入支路共同决定。共同决定。第22页，本讲稿共74页由由于于约约束束长长度度是是L+1,任任何何一一个个子子多多项项式式gj i(D)的的阶阶次次不不会大于会大于L，可用通式表示为，可用通式表示为:=+(5-10)式式(5-10)定定义义的的子子多多项项式式gji(D)的的各各次次系系数数与与式式(5-1)(5-3)中中

18、的的系系数数是是一一致致的的，代代表表第第k个个输输入入支支路路中中第第l个个移移存存器器对对第第j个个输输出出支支路路的的影影响响。可可见见多多项项式式表表示示法法与与矩矩阵阵表表示示法法本本质质一一样样，只只是是多多项项式式表表示示法法通通过过时时延延因因子子D将将L+1个个生生成成子子矩矩阵阵(式式5-3)合合成成一一个个，而而使使矩矩阵阵元元素素由由“数数”变变为为“多多项项式式”。其其优优点点是是能能够够一一目目了了然然地地看看到到并并行行输输入入序序列列和和输输出出序序列列之之间间的的转转移移关关系系，而而这这正正是是卷卷积积编编码码器器的的主主要要特特征。征。第23页，本讲稿共7

19、4页由由式式(5-9)、(5-10)，可可知知第第j个个支支路路的的输输出出是是所所有有输输入入支支路路对它影响的总和，即对它影响的总和，即(5-11)最最后后，利利用用并并/串串变变换换公公式式将将n个个输输出出多多项项式式合合并并成成一一个个多多项项式式(5-12)转移函数矩阵用法归纳如下：转移函数矩阵用法归纳如下：输入信息序列经串输入信息序列经串/并变换得并行的输入多项式；并变换得并行的输入多项式；用式用式(5-11)算出各并行支路的输出多项式；算出各并行支路的输出多项式；用并用并/串转换公式串转换公式(5-12)算出输出多项式算出输出多项式C(D)。第24页，本讲稿共74页例例5.1(

20、续续2)二二进进制制(3,1,2)卷卷积积编编码码器器如如图图5-3。如如果果输输入入信息流信息流(101101011100),求输出码字序列。求输出码字序列。解解：本本题题为为一一路路输输入入(k=1)、三三路路输输出出(n=3)，因因此此转转移移函数矩阵是函数矩阵是13的多项式矩阵。的多项式矩阵。一路输入为一路输入为M0(D)=1+D2+D3+D5+D7+D8+D9+根据例根据例5.1中算出的系数及通式中算出的系数及通式(5-10)定义，定义，g00(D)=+D+D2=1g10(D)=+D+D2=1+Dg20(D)=+D+D2=1+D+D2由式由式(5-9)，该卷积编码器的转移函数矩阵是：

21、，该卷积编码器的转移函数矩阵是：G(D)=11+D1+D+D2第25页，本讲稿共74页由式由式(5-11)C0(D)=M0(D)g00(D)=(1+D2+D3+D5+D7+D8+D9)1=1+D2+D3+D5+D7+D8+D9C1(D)=M0(D)g10(D)=(1+D2+D3+D5+D7+D8+)(1+D)=(1+D)+(D2+D3)+(D3+D4)=1+D+D2+D4+D5+D6+D7C2(D)=M0(D)g20(D)=(1+D2+D3+D5+D7+)(1+D+D2)=(1+D+D2)+(D2+D3+D4)+(D3+D4+D5)+(D5+D6+D7)=1+D+D6+D9+它们的系数序列分别

22、是：它们的系数序列分别是：C0(D):10110101 C1(D):11101111 C2(D):11000010 并并/串变换，得输出序列串变换，得输出序列C111,011,110,100,010,110,011,110 第26页，本讲稿共74页例例5.2(续续2)二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，若若输输入入信信息息流流是是(101101011100)，求输出码字序列。，求输出码字序列。解：本题解：本题k=2,n=3,转移函数矩阵是转移函数矩阵是23多项式矩阵。多项式矩阵。输入输入M0(D)=1+D2+D3+D5+D7+D8+D9+D12+D13+D14串串/并

23、变换后的两个并行输入是：并变换后的两个并行输入是：(101101011100)M(D)=1+D2+D3+D5+D7+D8+D9+(110010)M0(D)=1+D+D4+(011110)M1(D)=D+D2+D3+D4+该卷积编码器的转移函数矩阵是：该卷积编码器的转移函数矩阵是：G(D)=g00(D)g10(D)g20(D)=1+DD1+D g01(D)g11(D)g21(D)=D11第27页，本讲稿共74页C0(D)=M0(D)g00(D)+M1(D)g01(D)=(1+D+D4+)(1+D)+(D+D2+D3+)D=1+D3+D6+C1(D)=M0(D)g10(D)+M1(D)g11(D)

24、=(1+D+D4+)D+(D+D2+D3+)1=D3+D4+D5+D6+C2(D)=M0(D)g20(D)+M1(D)g21(D)=(1+D+D4+)(1+D)+(D+D2+D3+)1=1+D+D3+D5+利用公式利用公式(5-12)并并/串变换串变换=1+(D3)3+(D3)6+(D3)3+(D3)4+(D3)5+(D3)6 D+1+(D3)+(D3)3+(D3)5+D2=1+D2+D5+D9+D10+D11+D13+D16+D17+其系数正是输出码元序列其系数正是输出码元序列(101001000111010011)。第28页，本讲稿共74页5.2.3 卷积码的编码矩阵和状态流图卷积码的编码

25、矩阵和状态流图生生成成矩矩阵阵、转转移移函函数数矩矩阵阵重重在在描描述述编编码码器器的的结结构构，状状态态流流图图和和网格图则利于揭示卷积码内在特性。网格图则利于揭示卷积码内在特性。状态：状态：编码器记忆阵列的内容，记作编码器记忆阵列的内容，记作Si。比比如如图图5-3卷卷积积编编码码器器，除除本本时时刻刻输输入入外外还还有有两两个个存存储储器器存存放放前前两两时时刻刻的的输输入入，其其内内容容的的组组合合有有00,01,10,11四四种种可可能能，那那么么这这种种编编码码器器可可有有四四种状态。种状态。一般，图一般，图5-2的移存器阵列有的移存器阵列有k行行L列共列共kL个存储单元，如果这些

26、个存储单元，如果这些单元都参与编码，最多可以有单元都参与编码，最多可以有2kL个状态。可以认为输出码组个状态。可以认为输出码组Ci 是本时刻输是本时刻输入信息组入信息组M i 和本时刻编码器状态和本时刻编码器状态S i 的函数，表示为的函数，表示为:Ci=f(Mi,Mi-1,Mi-L)=f(M i,S i)(5-13)第29页，本讲稿共74页状态状态S i=h(Mi-1,Mi-L+1,Mi-L),如图如图5-6所示所示图图5-6状态状态和状态转移和状态转移串串/并并变变换换线线性性组组合合器器m i0mi-10mi-L0m i1mi-11mi-L1m ik-1mi-1k-1mi-Lk-1M i

27、S iLM i-1 M i-L 时刻时刻i的状态的状态 Si 向下一时刻状态向下一时刻状态 Si+1的过渡称为的过渡称为状态转移状态转移。从图从图5-6可见，卷积编码器状态的转移不是任意的，因为可见，卷积编码器状态的转移不是任意的，因为移存的规则决定了下一个状态必然是移存的规则决定了下一个状态必然是：第30页，本讲稿共74页 Si+1=h(Mi,Mi-1,Mi-L+1)将将Si与与Si+1作比较，可知作比较，可知Si+1中的中的(M i-1,M i-L+1)是在是在Si中中就已确定的，就已确定的，Si+1的可变因素只有的可变因素只有Mi即本时刻输入信息即本时刻输入信息组一项。对于二进码，组一项

28、。对于二进码，Mi可以有可以有2k种组合，所以状态转种组合，所以状态转移也只能有移也只能有2k种。于是，同样可以把状态转移写成是种。于是，同样可以把状态转移写成是本时刻信息组本时刻信息组Mi 和本时刻编码器状态和本时刻编码器状态Si 的函数的函数:Si+1=h(Mi,Si)(5-14)式式(5-13)、(5-14)的含义是：本时刻输入信息组的含义是：本时刻输入信息组Mi和编码和编码器状态器状态Si一起决定了编码输出一起决定了编码输出Ci和下一状态和下一状态Si+1。由于编码。由于编码器状态和信息组花样都是有限数量的，所以卷积编码器可器状态和信息组花样都是有限数量的，所以卷积编码器可以看成是一个

29、有限状态机，用输入信息组以看成是一个有限状态机，用输入信息组Mi触发的触发的状态转状态转移图移图来描述。来描述。第31页，本讲稿共74页 在式在式(5-14)决定状态转移的同时，式决定状态转移的同时，式(5-13)也决定了输也决定了输出码组，因此，出码组，因此，确定的状态转移必定伴随着确定的码组。确定的状态转移必定伴随着确定的码组。二元码的二元码的kL个移存器最多可以有个移存器最多可以有2kL个状态，但是作个状态，但是作为状态机触发信号的为状态机触发信号的k重信息分组重信息分组M i只能有只能有2k种组合方式，种组合方式，因此从因此从S i出发，转移到的下一状态只可能是出发，转移到的下一状态只

30、可能是2k种之一，而种之一，而不是所有的不是所有的2kL个状态。个状态。若若某某卷卷积积编编码码器器有有n个个移移存存器器(n kL)，那那么么编编码码器器的的状状态态数数是是2n个个。可可以以构构造造一一个个2n2n 的的编编码码矩矩阵阵，其其i行行j列列的的元元素素cij代代表表从从i状状态态出出发发转转移移到到下下一一时时刻刻j状状态态时时发发出出的的码码组组。如如果果从从i状状态态出出发发不不可可能能转转移移到到j状状态态，则则相相应应的的矩矩阵元素用阵元素用“.”来表示。来表示。第32页，本讲稿共74页根根据据编编码码矩矩阵阵，可可以以画画出出卷卷积积编编码码器器的的状状态态流流图图

31、。以以状状态态为为节节点点、状状态态转转移移为为分分支支、伴伴随随转转移移的的输输入入/输输出出码码元与各分支对应，就不难得到卷积码的状态流图。元与各分支对应，就不难得到卷积码的状态流图。下面的两个例子有助于对编码矩阵和状态流图的理解。下面的两个例子有助于对编码矩阵和状态流图的理解。例例5.1(续续3)二进制二进制(3,1,2)卷积编码器如图卷积编码器如图5-3。试分别用编。试分别用编码矩阵和状态流图来描述该码。如果输入信息流是码矩阵和状态流图来描述该码。如果输入信息流是(101101011100),求输出码字序列。求输出码字序列。第33页，本讲稿共74页状态状态m i-10m i-20S00

32、0S101S210S311表表5-1(a)编码器状态的定义编码器状态的定义状态状态输入输入m0i=0m0i=1S0000111S1001110S2011100S3010101表表5-1(b)不同状态与输入时编出的码字不同状态与输入时编出的码字状态状态输入输入m0i=0m0i=1S0S0S2S1S0S2S2S1S3S3S1S3表表5-1(c)不同状态不同状态Si与输入时的下一状态与输入时的下一状态Si+1信号信号 c i0入入M i输出输出 ci1Ci c i2mi0mi-10mi-20第34页，本讲稿共74页由由表表5-1(a)(b)(c)，可可用用比比表表更更为为简简练练和和直直观观的的编编

33、码码矩矩阵阵来表示该卷积码：来表示该卷积码：编编码码矩矩阵阵若输入信息序列若输入信息序列是是1011010111结果是：结果是：S01/111S20/011S11/110S21/100S30/010S10/000S01/1110/0011/110S2S10/0111/1000/010S31/101图图5-7(3,1,2)卷积码状态流图卷积码状态流图第35页，本讲稿共74页例例5.2(续续3)某某二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，分分别别用用编编码码矩矩阵阵和和状状态态流流图图来来描描述述该该码码。如如果果输输入入信信息息流流是是(101101011100),求输出码

34、字序列。求输出码字序列。解解：本本题题k=2,n=3,有有2个个移移存存器器、4种种状状态态。由由于于每每次次并并行行输输入入2比比特特，即即有有限限状状态态机机触触发发信信号号2比比特特，所所以以从从某某一一状状态态出出发发，下下一一个个状状态态可可以以是是4种种状状态态之之一一。由由图图5-4列列出出类类似似于于表表5-1(a)(b)(c)的的表表后后可可得得(3,2,1)卷卷积积码码的编码矩阵如下。的编码矩阵如下。S0 S1S2S3S0000 101 011110C=S1111010 100 001 S2100001111010 S3011 110 000 101第36页，本讲稿共74页

35、状状态态流流图图00/000S000/10001/01100/11110/10100/01111/11001/11110/00110/010S2S101/10001/00011/01010/11011/001S311/101输入序列输入序列(10,11,01,01,11,00,)S010/101S111/001S301/000S201/111S211/010S300/011S0对应码字序列为对应码字序列为(101,001,000,111,010,011,)第37页，本讲稿共74页5.2.4 卷积码的网格图卷积码的网格图状状态态流流图图展展示示了了状状态态转转移移的的去去向向，但但不不能能记记录

36、录下下状状态态转转移移的的轨轨迹迹。网网格格图图可可以以弥弥补补这这一一缺缺陷陷。它它可可以以将将状状态态转转移移展展开开在时间轴上，是分析卷积码的有力工具。在时间轴上，是分析卷积码的有力工具。网网格格图图以以状状态态为为纵纵轴轴，以以时时间间（抽抽样样周周期期T）为为横横轴轴，将将平平面面分分割割成成格格状状。状状态态和和状状态态转转移移的的定定义义画画法法与与流流图图法法一一样样，也也是是用用一一个个箭箭头头表表示示转转移移，伴伴随随转转移移的的M i/C i表表示示转转移移发发生生时时的的输输入入信信息息组组/输输出出码码组组。所所不不同同的的是是网网格格图图还还体体现现时时间间的的变变

37、化化，一一次次转转移移与与下下一一次次转转移移在在图图上上头头尾尾相相联联。下下面面以以一个例子来说明如何在网格图上画出编码器的工作轨迹。一个例子来说明如何在网格图上画出编码器的工作轨迹。第38页，本讲稿共74页1/1100/001例例5.1(续续4)用用网网格格图图描描述述图图5-3二二进进制制(3,1,2)卷卷积积编编码码器器。若若信息序列是信息序列是(1011010),求输出码字序列。求输出码字序列。解：由例解：由例5.1(续续3)所得的编码矩阵和状态流图，可得所得的编码矩阵和状态流图，可得0/0110/0101/1010/0001/1000/0000/0000/0000/0000/00

38、00/0001/1111/1101/1110/0101/1000/0010/0111/110S0S1S2S3网格图网格图编码轨迹图编码轨迹图第39页，本讲稿共74页当输入当输入5位信息位信息10110时，输出码字和状态转移是时，输出码字和状态转移是S01/111S20/011S11/110S21/100S30/010S1如如果果继继续续输输入入第第6位位信信息息，信信息息为为0或或1时时，状状态态将将分分别别转转移移到到S0或或S2，而不可能转移到，而不可能转移到S1或或S3。网网格格图图顶顶上上的的一一条条路路径径代代表表输输入入全全0信信息息/输输出出全全0码码字字时时的路径，这条路径在卷

39、积码分析时常被用作为参考路径。的路径，这条路径在卷积码分析时常被用作为参考路径。第40页，本讲稿共74页例例5.2(续续4)二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，用用网网格格图图描描述述该该码码。对对于于输输入入(101101011100),求求输输出出码字序列。码字序列。解：由例解：由例5-2(续续3)结果，结果，可得网格图如下可得网格图如下10/010001/10011/01010/10100/00001/11101/01111/11000/11111/00100/10010/00110/11001/00011/10100/01110/10111/00101/000

40、01/11111/01000/011网格图网格图编码轨迹图编码轨迹图第41页，本讲稿共74页 生成矩阵、转移函数矩阵、状态流图和网格图从不生成矩阵、转移函数矩阵、状态流图和网格图从不同侧面描述卷积码，各有用处。同侧面描述卷积码，各有用处。生成矩阵和转移函数矩阵属同一大类。它们沿用了分组生成矩阵和转移函数矩阵属同一大类。它们沿用了分组码的描述方法，建立了代数与编码器的关联，物理意义清楚，码的描述方法，建立了代数与编码器的关联，物理意义清楚，代数量（多项式系数，矩阵元素）与编码电路连接线之间的代数量（多项式系数，矩阵元素）与编码电路连接线之间的对应关系十分明确，非常利于用对应关系十分明确，非常利于

41、用VHDL等硬件描述语言来等硬件描述语言来表达以及用表达以及用FPGA、DSP等来物理实现。等来物理实现。状态流图和网格图属于另外一类表示法。状态流图可状态流图和网格图属于另外一类表示法。状态流图可借助信号流图等图论工具或理论来分析卷积码的特性，网借助信号流图等图论工具或理论来分析卷积码的特性，网格图则特别适合用于计算机的穷尽搜索上，它使状态能在格图则特别适合用于计算机的穷尽搜索上，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似然序列译码的得力工具。特性以及维特比最大似然序列译码的得力工具。第42页，本讲稿共

42、74页5.3 卷积码的特性卷积码的特性第43页，本讲稿共74页 5.3.1 卷积码的特性码率卷积码的特性码率对对于于有有限限长长信信息息序序列列如如M个个k重重，当当M个个分分组组全全部部输输入入编编码码器器后后，虽虽然然再再没没有有新新的的信信息息分分组组输输入入，但但由由于于编编码码器器内内L组组（约约束束长长度度）移移存存器器的的记记忆忆效效应应，编编码码器器将将继继续续输输出出L个个码码字字才才能能将将记记忆忆阵阵列列中中的的内内容容完全移出，完全移出，这就导致这就导致卷积码码率卷积码码率由由R=k/n 降低为降低为。将码率下降的相对值定义为将码率下降的相对值定义为码率损失系数码率损失

43、系数：码率损失系数码率损失系数=(5-15)第44页，本讲稿共74页显然，显然，M相对于相对于L越大则效率损失越小。越大则效率损失越小。当信息序列很长而使当信息序列很长而使M L时，效率损失趋于时，效率损失趋于0因而可忽略因而可忽略不计，每一个不计，每一个k 位信息组产生一个位信息组产生一个n 位码字，卷积编码码率与位码字，卷积编码码率与分组码码率一样为分组码码率一样为R=k/n。相反，相反，M相对于相对于L越小则效率损失越大，当越小则效率损失越大，当M=1时码率损时码率损失系数接近失系数接近1。由此可见，卷积码的适用对象是电路交换的连续信息流，或由此可见，卷积码的适用对象是电路交换的连续信息

44、流，或包交换的包交换的“流媒体流媒体”，或复用级的信息流，而不适合短突发、目，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。的地分散的用户端包交换纠错编码。第45页，本讲稿共74页5.3.2卷积码的距离特性卷积码的距离特性卷卷积积码码的的性性能能取取决决于于卷卷积积码码的的距距离离特特性性和和译译码码算算法法。距距离离特特性性决决定定了了该该码码的的纠纠错错能能力力，而而译译码码方方法法只只是是研研究究如如何何将将这这种种潜潜在在的的纠纠错错能能力力转转化为现实的纠错能力。化为现实的纠错能力。表表述述距距离离特特性性的的最最好好方方法法是是网网格格图图。若若序序列列C、C

45、”是是从从同同一一时时刻刻（不不妨妨称称为为0时时刻刻）由由零零状状态态出出发发的的两两个个不不同同的的码码字字序序列列，它它们们所所对对应应的的信信息息序序列列分分别别是是M 和和M”，且且M M”。对对于于二二元元码码，序序列列距距离离d(C,C”)指指汉汉明明距距离离，等等于于C、C”的的对对应应项项逐逐一一模模2加加后后所所得得的的序序列列C的重量，也等于序列的重量，也等于序列C和全零序列和全零序列0的距离或序列的距离或序列C的重量。的重量。d(C,C”)=W(C C”)=W(C 0)=d(C,0)(5-16)第46页，本讲稿共74页 式式(5-16)默认默认,两码字序列之和仍是码字序

46、列。两码字序列之和仍是码字序列。全零序列在网格图上表现为保持在零状态的一条横全零序列在网格图上表现为保持在零状态的一条横线，故线，故两序列的最小距离也就是非全零路径与全零状态两序列的最小距离也就是非全零路径与全零状态路径距离最小者路径距离最小者。序序列列距距离离还还与与序序列列长长度度有有关关，同同一一序序列列对对不不同同长长度度比比较较时时显显然然距距离离也也不不同同。将将长长度度l 的的任任意意两两序序列列间间的的最最小小距距离离定定义义为为l 阶阶列列距距离离。以以长长度度l为为变变量量的的列列距距离离特特性性称称之之为为列距离函数，用列距离函数，用dc(l)来表示来表示：dc(l)mi

47、nd(Cl,C”l):M0 M”0(5-17)第47页，本讲稿共74页所所谓谓M0 M”0即即“不不同同”的的两两序序列列，在在网网格格图图上上的的表表现现就就是是从从零零时时刻刻起起两两序序列列轨轨迹迹从从零零状状态态分分道道扬扬镳镳形形成成分分叉叉点点。由式由式(5-16)，式，式(5-17)可改写为可改写为dc(l)minW(C lC”l):M 0 M”0=minW(Cl):M0 0(5-18)由由于于早早期期卷卷积积码码译译码码方方法法与与约约束束长长度度（L+1）有有关关，于于是是曾曾把（把（L+1）阶列距离称为）阶列距离称为最小距离最小距离dmdm=minW(CL+1):M0 0(

48、5-19)而而把把由由零零状状态态零零时时刻刻分分叉叉的的无无限限长长的的两两个个序序列列之之间间的的最最小距离定义为小距离定义为自由距离自由距离：df=minW(C):M0 0(5-20)第48页，本讲稿共74页列距离、最小距离、自由距离三者之间的关系是：列距离、最小距离、自由距离三者之间的关系是：dmdc(l)|l=L+1(5-21)df=dc(l)(5-22)以下举例说明三个距离的求法。以下举例说明三个距离的求法。例例5-3二进制二进制(3,1,2)卷积码网格图如图卷积码网格图如图5-9，试求该码，试求该码1至至6阶列距离、最小距离和自由距离。阶列距离、最小距离和自由距离。解：距离的求法

49、参见图解：距离的求法参见图5-10。第49页，本讲稿共74页110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111最轻码字序列最轻码字序列列距离函数列距离函数dc(l)l1S0S2dc(1)=3l2S0S2S3dc(2)=4l3S0S2S3S1dc(3)=5(最小距离最小距离dm)l4S0S2S3S1S0dc(4)=6或或S0S2S1S0S0l5S0S2S1S0S0dc(5)=6l6S0S2S1S0S0S0dc(6)=6第50页，本讲

50、稿共74页 由上例可得到结论：由上例可得到结论：自由距离就是从零状态分叉后又回到零状态自由距离就是从零状态分叉后又回到零状态的所有路径中重量最轻的那一条的重量。的所有路径中重量最轻的那一条的重量。许多早期的卷积码文献都将最小距离许多早期的卷积码文献都将最小距离dm看作是最重要的看作是最重要的距离参数，这是由于那时的主要译码算法只有一个约束长度距离参数，这是由于那时的主要译码算法只有一个约束长度（L+1）的记忆容量。后来维特比译码和序列译码成为主要方法，）的记忆容量。后来维特比译码和序列译码成为主要方法，这些译码算法的记忆长度在理论上可不受限制，因此与这两种这些译码算法的记忆长度在理论上可不受限