信息论与编码第六讲课件.ppt

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

2、积码的一个基本参数，常用基本参数，常用(n，k，L)来表示某一码长来表示某一码长n、信、信息位息位k、约束长度、约束长度L+1的卷积码。的卷积码。卷积编码器卷积编码器（线性组合器）（线性组合器）ci0 c i1 c in-2 c in-1第第i分组分组 第第i-1分组分组 第第i-2分组分组 第第i-L分组分组mi0mi1 mi k-1mi-10 m i-1k-1mi-20 mi-2k-1 mi-L0mi-L1 m i-Lk-1输入输入编码输出编码输出C i图图5-1 卷积编码示意卷积编码示意串串/并并变变换换并并/串串变变换换线线性性组组合合器器m i0 m i-10 m i-20 m i-

3、L 0m i1 m i-11 m i-21 m i-L 1m i k-1m i-1k-1m i-2k-1m i-L k-1信号入信号入 M i 编码编码输出输出 Ci 图图5-2 卷积编码器的一般结构卷积编码器的一般结构 图图5-2记忆阵列记忆阵列中的每一存储单元都有一条连线将中的每一存储单元都有一条连线将数据送到线性组合器，但实际上无需每个单元都有连数据送到线性组合器，但实际上无需每个单元都有连接。因为二元域线性组合时的系数只能选接。因为二元域线性组合时的系数只能选“0”或者或者“1”，选，选“0”时表示该项在线性组合中不起作用，对时表示该项在线性组合中不起作用，对应存储单元就不需要连接到线

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

5、Mi=(m i0,m i 1,mik-1)Ci=(c i0,c i 1,c in-1)i-1 Mi-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、性组合，写作：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 表示该位参与线性组合。表示该位参与线性组合。LlKkklikjljimgc010kjlgkjlgkjlg例例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 000g002g001g012g011g022g021g010g020g信号信号 c i0入入M i 输出输出 ci1 C i c i2 图图5-3 二元二元(3,1,2)卷积编码器卷积编码器m i0 m i-10 m i-20kjlg输入信息行输入信息行时延列时延列输出码元行输出码元行例例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 000g020g010g021g011g120g110g001g100gkjlg输入信息行输入信息行时延列时延列输出码元行输出码元行121g111g101g c i0 信号信号 Ci 入入M i ci1 输出输出 c i2图图5-4 二进制二进制(3,2,1)卷积编码器卷积编码器mi 0 mi-10mi 1 m i-

9、11上面两例表明：上面两例表明：从已知的编码电路可以找出对应的系数从已知的编码电路可以找出对应的系数 ，反之，已知系数反之，已知系数 即可画出相应的编码电路。即可画出相应的编码电路。因此，从电路结构角度，因此，从电路结构角度，(5-1)是很好的表达形是很好的表达形式。但是，通常需要从另外各种不同的角度去研究式。但是，通常需要从另外各种不同的角度去研究卷积码，或侧重于卷积码的物理意义，或强调卷积卷积码，或侧重于卷积码的物理意义，或强调卷积码的距离特性，或研究编码器的状态变迁。码的距离特性，或研究编码器的状态变迁。在不同角度，存在着描述卷积码的不同方法。在不同角度，存在着描述卷积码的不同方法。以下

10、介绍四种以下介绍四种卷积码的描述方法卷积码的描述方法：生成矩阵表示法生成矩阵表示法，转移函数矩阵表示法转移函数矩阵表示法，状态流图法状态流图法，网格图表示网格图表示法法。kjlgkjlg5.2 卷积码的描述卷积码的描述5.2.1 生成矩阵表示法生成矩阵表示法由式由式(5-1)，CiT LlKkkliklmg010010000Kkkikmg100KkkLikLmg LlKkkliklmg010110010Kkkikmg101KkkLikLmg LlKkkliklnmg010)1(1000)1(Kkkiknmg10)1(KkkLikLnmg0ic1ic=+1nic =+=000g100g100kg

11、00im00Lg10kLg0Lim010g110g110kg10im01Lg11kLg1Lim00)1(ng10)1(kng10kim0)1(Lng1)1(kLng1kLimTLiTLTiTTiTMGMGMG110求转置，上式写成：求转置，上式写成：(5-2)式中，式中，G0、G1、GL 是是kn矩阵，称作矩阵，称作生成子矩阵生成子矩阵：011GMGMGMCiiLLii Gl=l=0,1,L (5-3)00lg01lg0)1(lng10lg11lg1)1(lng10klg11klg1)1(klng011GMGMGMCiiLLii时刻时刻i=0 C0=M0G0 时刻时刻i=1 C1=M0G1+M

12、1G0 时刻时刻i=2 C2=M0G2+M1G1+M2G0 时刻时刻i=L CL=M0GL+M1GL-1+ML-1G1+MLG0 时刻时刻i=L+1 CL+1=M1GL+M2GL-1+MLG1+ML+1G0 式式(5-2)可写成：可写成：(5-4)式式(5-4)说明：说明：输出码字输出码字Ci是是i时刻之前时刻之前(含含i时刻时刻)的的信息组信息组(Mi Mi-1Mi-L)与生成子矩阵组与生成子矩阵组(G0 G1 GL)的卷积的卷积，这也就是卷积码名称的来历。，这也就是卷积码名称的来历。(5-2)LliilliiGMGMC0*令令 G0G1 G2 G L 0 0 g G =G0 G1 G2 G

13、L 0 =Dg (5-6)G0 G1 G2 GL 0 D2g 定义定义g 为为基本生成矩阵基本生成矩阵，定义定义G 为为生成矩阵生成矩阵。若码字序列是一个从若码字序列是一个从0时刻开始的无限长右边序列，时刻开始的无限长右边序列，可写成有头无尾的半无限矩阵形式：可写成有头无尾的半无限矩阵形式：C=(C0,C1,，CL,CL+1,）G0 G1 G2 GL 0 =(M0,ML,ML+1,)G0 G1 G2 GL 0 (5-5)G0 G1 G2 GL 0 例例5.1(续续1)二进制二进制(3,1,2)卷积编码器如图卷积编码器如图5-3。如果。如果输入信息流是输入信息流是(101101011100),求

14、输出码字序列。求输出码字序列。解：对照例解：对照例5.1算得的系数及式算得的系数及式(5-3)生成子矩阵的定生成子矩阵的定义，可知本题义，可知本题G0=1 1 1，G1=0 1 1G2=0 0 1111 011 001 111 011 001Ci=(101101011100)111 011 001 111 011 001 =(111,011,110,100,010,110,011,110,100,101,010,001 )000g010g020g002g012g022g001g011g021g例例5.2(续续1)某二进制某二进制(3,2,1)卷积编码器如图卷积编码器如图5-4,若若输入信息流是

15、输入信息流是(101101011100)，求输出码字序列，求输出码字序列解：对照例解：对照例5.2算得的系数及式算得的系数及式(5-3)生成子矩阵的生成子矩阵的定义，可知本题定义，可知本题G0=，G1=于是于是 101 111 011 100 C=(10,11,01,01,11,00)101 111011 100 101 111 011 100 =(101,001,000,111,010,011,)120g000g010g020g100g110g001g011g021g101g111g121g1010111111005.2.2 多项式及转移函数矩阵表示法多项式及转移函数矩阵表示法 若若M(D)

16、=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 卷积码的转移函数矩阵卷积码的转移函数矩阵串串/并并卷积卷积编码器编码器G(D)并并/串串 卷积编码器可视作一个卷积编码器可视作一个k端口入、端口入、n端口出的线性端口出的线性多端口网络，可以用多端口网络，可以用转移函数矩阵转移函数矩阵来描述输入、输出来描述输入、输出间关系。由于卷积编

17、码器其输入、输出均是无限长多间关系。由于卷积编码器其输入、输出均是无限长多项式，因而转移函数矩阵元素也是多项式。项式，因而转移函数矩阵元素也是多项式。定义输入、输出定义输入、输出多项式矩阵多项式矩阵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 n-1(D)这里，这里，MP(D)、CP(D)的下标的下标P表示表示“并行并行”。虽然虽然M(D)和和 MP(D)数量上有对应关系，然而在数量上有对应关系，然而在数学上有不同含义，数学上有不同含义，M(D)是多项式而是多项式而MP(

18、D)是矩阵。是矩阵。编码器编码器 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(D)的第的第 i 行第行第 j 列元素列元素gj i(D)描述了第描述了第i个输入支路如何对第个输入支路如何对第j个输出支路产生影响的转移关个输出支路产生影响的转移关系，也称系，也称子多项式子多项式，而第，而第j个输出支路最终的输出由个输出支路最终的输

19、出由全体全体k个输入支路共同决定。个输入支路共同决定。由于约束长度是由于约束长度是L+1,任何一个子多项式任何一个子多项式gj i(D)的阶的阶次不会大于次不会大于L，可用通式表示为，可用通式表示为:=+(5-10)式式(5-10)定义的子多项式定义的子多项式gji(D)的各次系数与式的各次系数与式(5-1)(5-3)中的系数是一致的，代表第中的系数是一致的，代表第k个输入支路中第个输入支路中第l个移存器对第个移存器对第j个输出支路的影响。可见多项式表示个输出支路的影响。可见多项式表示法与矩阵表示法本质一样，只是多项式表示法通过法与矩阵表示法本质一样，只是多项式表示法通过时延因子时延因子D将将

20、L+1个生成子矩阵个生成子矩阵(式式5-3)合成一个，合成一个，而使矩阵元素由而使矩阵元素由“数数”变为变为“多项式多项式”。其优点是。其优点是能够一目了然地看到并行输入序列和输出序列之间能够一目了然地看到并行输入序列和输出序列之间的转移关系，而这正是卷积编码器的主要特征。的转移关系，而这正是卷积编码器的主要特征。)(DgijDgij1LijLDgLllijlDg0ijg0由式由式(5-9)、(5-10)，可知第，可知第j个支路的输出是所有输入个支路的输出是所有输入支路对它影响的总和，即支路对它影响的总和，即 (5-11)最后，利用并最后，利用并/串变换公式将串变换公式将n个输出多项式合并成一

21、个输出多项式合并成一个多项式个多项式 (5-12)转移函数矩阵用法归纳如下：转移函数矩阵用法归纳如下：输入信息序列经串输入信息序列经串/并变换得并行的输入多项式；并变换得并行的输入多项式；用式用式(5-11)算出各并行支路的输出多项式；算出各并行支路的输出多项式；用并用并/串转换公式串转换公式(5-12)算出输出多项式算出输出多项式C(D)。10)()()(kiijijDgDMDC10)()(njnjjDCDDC例例5.1(续续2)二进制二进制(3,1,2)卷积编码器如图卷积编码器如图5-3。如果。如果输入信息流输入信息流(101101011100),求输出码字序列。求输出码字序列。解：本题为

22、一路输入解：本题为一路输入(k=1)、三路输出、三路输出(n=3)，因此，因此转移函数矩阵是转移函数矩阵是13的多项式矩阵。的多项式矩阵。一路输入为一路输入为M0(D)=1+D2+D3+D5+D7+D8+D9+根据例根据例5.1中算出的系数及通式中算出的系数及通式(5-10)定义，定义，g00 (D)=+D+D2=1 g10 (D)=+D+D2=1+D g20 (D)=+D+D2=1+D+D2由式由式(5-9)，该卷积编码器的转移函数矩阵是：，该卷积编码器的转移函数矩阵是：G(D)=1 1+D 1+D+D2 000g001g002g010g011g012g020g021g022g由式由式(5-

23、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+它们的系数序列分别是：它们的系数序列分别是：C0(D):1 0 1 1 0 1 0 1 C1(D):1 1 1 0

24、1 1 1 1 C2(D):1 1 0 0 0 0 1 0 并并/串变换，得输出序列串变换，得输出序列 C 111,011,110,100,010,110,011,110 )()()()()(00110DgDMDgDMDCjkkjkj例例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 串串/并变换后的两

25、个并行输入是：并变换后的两个并行输入是：(101101011100)M(D)=1+D2+D3+D5+D7+D8+D9+(1 1 0 0 1 0 )M0(D)=1+D+D4+(0 1 1 1 1 0 )M1(D)=D+D2+D3+D4+该卷积编码器的转移函数矩阵是：该卷积编码器的转移函数矩阵是：G(D)=g00(D)g10(D)g20(D)=1+D D 1+D g01(D)g11(D)g21(D)=D 1 1C0(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)

26、=(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)。)()(20jnjjDCDDC)D(CD)D(DC)D(C3223

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

28、2的移存器阵列有的移存器阵列有k行行L列共列共 kL个存储单元，如个存储单元，如果这些单元都参与编码，最多可以有果这些单元都参与编码，最多可以有2kL个状态。可以认为输出个状态。可以认为输出码组码组Ci 是本时刻输入信息组是本时刻输入信息组M i 和本时刻编码器状态和本时刻编码器状态S i 的函数，的函数，表示为表示为:Ci=f(Mi,Mi-1,Mi-L)=f(M i,S i)(5-13)状态状态S i=h(Mi-1,Mi-L+1,Mi-L),如图如图5-6所示所示 图图5-6 状态状态和状态转移和状态转移串串/并并变变换换线线性性组组合合器器 m i0 m i-10 m i-L 0 m i1

29、 m i-11 m i-L 1 m ik-1 m i-1k-1 m i-L k-1M iS iLM i-1 M i-L 时刻时刻i的状态的状态 Si 向下一时刻状态向下一时刻状态 Si+1 的过渡称为的过渡称为状态状态转移转移。从图。从图5-6可见，卷积编码器状态的转移不是任可见，卷积编码器状态的转移不是任意的，因为移存的规则决定了下一个状态必然是意的，因为移存的规则决定了下一个状态必然是：Si+1=h(Mi,Mi-1,Mi-L+1)将将Si与与Si+1作比较，可知作比较，可知Si+1中的中的(M i-1,M i-L+1)是是在在Si中就已确定的，中就已确定的，Si+1的可变因素只有的可变因素

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

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

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

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

34、 m i-20 S0 0 0 S10 1 S21 0 S31 1 表表5-1(a)编码器状态的定义编码器状态的定义状态状态 输入输入 m 0i=0 m 0i=1 S0 000111 S1 001110 S2 011100 S3 010101 表表5-1(b)不同状态与输入时编出的码字不同状态与输入时编出的码字状态状态输入输入 m 0i=0 m0i=1 S0 S0 S2 S1 S0 S2 S2 S1 S3 S3 S1 S3 表表5-1(c)不同状态不同状态Si与输入时的下一状态与输入时的下一状态Si+1信号信号 c i0入入M i 输出输出 ci1 C i c i2 m i0 m i-10 m

35、i-20由表由表5-1(a)(b)(c)，可用比表更为简练和直观的，可用比表更为简练和直观的编码编码矩阵矩阵来表示该卷积码：来表示该卷积码：编编码码矩矩阵阵 若输入信息序列若输入信息序列是是1011010111 结果是：结果是：S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010 S1 10101010001111000111100032103210SSSSSSSSC 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 图图5-7 (3,1,2)卷积码状态流图卷积码状态流图 例例5.2(续续3

36、)某二进制某二进制(3,2,1)卷积编码器如图卷积编码器如图5-4，分别用编码矩阵和状态流图来描述该码。如果输入分别用编码矩阵和状态流图来描述该码。如果输入信息流是信息流是(101101011100),求输出码字序列。求输出码字序列。解：本题解：本题k=2,n=3,有有2个移存器、个移存器、4种状态。由于每种状态。由于每次并行输入次并行输入2比特，即有限状态机触发信号比特，即有限状态机触发信号2比特，比特，所以从某一状态出发，下一个状态可以是所以从某一状态出发，下一个状态可以是4种状态种状态之一。由图之一。由图5-4列出类似于表列出类似于表5-1(a)(b)(c)的表后可的表后可得得(3,2,

37、1)卷积码的编码矩阵如下。卷积码的编码矩阵如下。S0 S1 S2 S3 S0 000 101 011 110 C =S1 111 010 100 001 S2 100 001 111 010 S3 011 110 000 101 状状态态流流图图 00/000 S0 00/100 01/011 00/111 10/101 00/011 11/11001/111 10/001 10/010 S2 S1 01/100 01/000 11/010 10/110 11/001 S3 11/101 输入序列输入序列(10,11,01,01,11,00,)S0 10/101 S1 11/001 S3 01

38、/000 S2 01/111 S211/010 S3 00/011 S0 对应码字序列为对应码字序列为 (101,001,000,111,010,011,)5.2.4 卷积码的网格图卷积码的网格图 状态流图展示了状态转移的去向，但不能记录下状态流图展示了状态转移的去向，但不能记录下状态转移的轨迹。网格图可以弥补这一缺陷。它可状态转移的轨迹。网格图可以弥补这一缺陷。它可以将状态转移展开在时间轴上，是分析卷积码的有以将状态转移展开在时间轴上，是分析卷积码的有力工具。力工具。网格图以状态为纵轴，以时间（抽样周期网格图以状态为纵轴，以时间（抽样周期T）为）为横轴，将平面分割成格状。状态和状态转移的定义

39、横轴，将平面分割成格状。状态和状态转移的定义画法与流图法一样，也是用一个箭头表示转移，伴画法与流图法一样，也是用一个箭头表示转移，伴随转移的随转移的 M i/C i表示转移发生时的输入信息组表示转移发生时的输入信息组/输出输出码组码组。所不同的是网格图还体现时间的变化，一次。所不同的是网格图还体现时间的变化，一次转移与下一次转移在图上头尾相联。下面以一个例转移与下一次转移在图上头尾相联。下面以一个例子来说明如何在网格图上画出编码器的工作轨迹。子来说明如何在网格图上画出编码器的工作轨迹。1/1100/001例例5.1(续续4)用网格图描述图用网格图描述图5-3二进制二进制(3,1,2)卷积编码卷

40、积编码器。若信息序列是器。若信息序列是(1011010),求输出码字序列。求输出码字序列。解：由例解：由例5.1(续续3)所得的编码矩阵和状态流图，可得所得的编码矩阵和状态流图，可得0/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0001/1111/1101/1110/0101/1000/0010/0111/110S0 S1 S2 S3网格图网格图编码轨迹图编码轨迹图当输入当输入5位信息位信息10110时，输出码字和状态转移是时，输出码字和状态转移是 S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010

41、S1如果继续输入第如果继续输入第6位信息，信息为位信息，信息为0或或1时，状态将分时，状态将分别转移到别转移到S0或或S2，而不可能转移到，而不可能转移到S1或或S3。网格图顶上的一条路径代表输入全网格图顶上的一条路径代表输入全0信息信息/输出全输出全0码码字时的路径，这条路径在卷积码分析时常被用作为字时的路径，这条路径在卷积码分析时常被用作为参考路径。参考路径。例例5.2(续续4)二进制二进制(3,2,1)卷积编码器如图卷积编码器如图5-4，用网格图描述该码。对于输入用网格图描述该码。对于输入(101101011100),求输出码字序列。求输出码字序列。解：由例解：由例5-2(续续3)结果，

42、结果，可得网格图如下可得网格图如下 10/010001/10011/01010/10100/00001/11101/01111/11000/11111/00100/10010/00110/11001/00011/10100/01110/10111/00101/00001/11111/01000/011网格图网格图编码轨迹图编码轨迹图 生成矩阵、转移函数矩阵、状态流图和网格图生成矩阵、转移函数矩阵、状态流图和网格图从不同侧面描述卷积码，各有用处。从不同侧面描述卷积码，各有用处。生成矩阵和转移函数矩阵属同一大类。它们沿生成矩阵和转移函数矩阵属同一大类。它们沿用了分组码的描述方法，建立了代数与编码器

43、的关用了分组码的描述方法，建立了代数与编码器的关联，物理意义清楚，代数量（多项式系数，矩阵元联，物理意义清楚，代数量（多项式系数，矩阵元素）与编码电路连接线之间的对应关系十分明确，素）与编码电路连接线之间的对应关系十分明确，非常利于用非常利于用VHDL等硬件描述语言来表达以及用等硬件描述语言来表达以及用FPGA、DSP等来物理实现。等来物理实现。状态流图和网格图属于另外一类表示法。状态状态流图和网格图属于另外一类表示法。状态流图可借助信号流图等图论工具或理论来分析卷积流图可借助信号流图等图论工具或理论来分析卷积码的特性，网格图则特别适合用于计算机的穷尽搜码的特性，网格图则特别适合用于计算机的穷

44、尽搜索上，它使状态能在时域展开，所得的状态轨迹是索上，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似研究差错事件、卷积码距离特性以及维特比最大似然序列译码的得力工具。然序列译码的得力工具。5.3 卷积码的特性卷积码的特性 5.3.1 卷积码的特性码率卷积码的特性码率 对于有限长信息序列如对于有限长信息序列如M个个k重，当重，当M个分组个分组全部输入编码器后，虽然再没有新的信息分组输全部输入编码器后，虽然再没有新的信息分组输入，但由于编码器内入，但由于编码器内L组（约束长度）移存器的记组（约束长度）移存器的记忆效应，编码器将继续输出忆效应，编码器将继续输出L个

45、码字才能将记忆阵个码字才能将记忆阵列中的内容完全移出，列中的内容完全移出，这就导致这就导致卷积码码率卷积码码率由由R=k/n 降低为降低为 。将码率下降的相对值定义为将码率下降的相对值定义为码率损失系数码率损失系数：码率损失系数码率损失系数=(5-15)(LMnkMRLMLRRR 显然，显然，M相对于相对于L越大则效率损失越小。越大则效率损失越小。当信息序列很长而使当信息序列很长而使M L时，效率损失趋于时，效率损失趋于 0 因而因而可忽略不计，每一个可忽略不计，每一个 k 位信息组产生一个位信息组产生一个 n 位码字，卷位码字，卷积编码码率与分组码码率一样为积编码码率与分组码码率一样为R=k

46、/n。相反，相反，M相对于相对于L越小则效率损失越大，当越小则效率损失越大，当M=1时码时码率损失系数接近率损失系数接近1。由此可见，卷积码的适用对象是电路交换的连续信由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的息流，或包交换的“流媒体流媒体”，或复用级的信息流，而，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。不适合短突发、目的地分散的用户端包交换纠错编码。5.3.2 卷积码的距离特性卷积码的距离特性 卷积码的性能取决于卷积码的距离特性和译码算法。距离卷积码的性能取决于卷积码的距离特性和译码算法。距离特性决定了该码的纠错能力，而译码方法只是研究如何将这种

47、特性决定了该码的纠错能力，而译码方法只是研究如何将这种潜在的纠错能力转化为现实的纠错能力。潜在的纠错能力转化为现实的纠错能力。表述距离特性的最好方法是网格图。若序列表述距离特性的最好方法是网格图。若序列C、C”是从同是从同一时刻（不妨称为一时刻（不妨称为0时刻）由零状态出发的两个不同的码字序时刻）由零状态出发的两个不同的码字序列，它们所对应的信息序列分别是列，它们所对应的信息序列分别是M 和和M”，且，且M M”。对。对于二元码，于二元码，序列距离序列距离d(C,C”)指汉明距离，等于指汉明距离，等于C、C”的对应的对应项逐一模项逐一模2加后所得的序列加后所得的序列C的重量，也等于序列的重量，

48、也等于序列C和全零序列和全零序列0的距离或序列的距离或序列C的重量。的重量。d(C,C”)=W(C C”)=W(C 0)=d(C,0)(5-16)式式(5-16)默认默认,两码字序列之和仍是码字序列。两码字序列之和仍是码字序列。全零序列在网格图上表现为保持在零状态的一全零序列在网格图上表现为保持在零状态的一条横线，故条横线，故两序列的最小距离也就是非全零路径与全两序列的最小距离也就是非全零路径与全零状态路径距离最小者零状态路径距离最小者。序列距离还与序列距离还与序列长度有关，同一序列对不同序列长度有关，同一序列对不同长度比较时长度比较时显然显然距离也不同。距离也不同。将长度将长度l 的任意两序

49、列的任意两序列间的最小距离定义为间的最小距离定义为l 阶列距离阶列距离。以以长度长度l为变量的列为变量的列距离特性称之为列距离函数，用距离特性称之为列距离函数，用dc(l)来表示来表示：dc(l)min d(Cl,C”l):M0 M”0 (5-17)所谓所谓M0 M”0即即“不同不同”的两序列，在网格图上的两序列，在网格图上的表现就是从零时刻起两序列轨迹从零状态分道扬镳的表现就是从零时刻起两序列轨迹从零状态分道扬镳形成分叉点。由式形成分叉点。由式(5-16)，式，式(5-17)可改写为可改写为dc(l)min W(C lC”l):M 0 M”0=min W(Cl):M0 0 (5-18)由于早

50、期卷积码译码方法与约束长度（由于早期卷积码译码方法与约束长度（L+1）有关，）有关，于是曾把（于是曾把（L+1）阶列距离称为）阶列距离称为最小距离最小距离dmdm=min W(CL+1):M0 0 (5-19)而把由零状态零时刻分叉的无限长的两个序列之间的而把由零状态零时刻分叉的无限长的两个序列之间的最小距离定义为最小距离定义为自由距离自由距离：df=min W(C ):M0 0(5-20)列距离、最小距离、自由距离三者之间的关系是：列距离、最小距离、自由距离三者之间的关系是：dmdc(l)|l=L+1 (5-21)df=dc(l)(5-22)以下举例说明三个距离的求法。以下举例说明三个距离的