信息论与编码第六讲课件

主要内容主要内容卷积码的基本概念卷积码的基本概念卷积码的描述卷积码的描述卷积码的特性卷积码的特性主要内容卷主要内容卷积码积码的基本概念的基本概念15.1卷积码的基本概念卷积码的基本概念5.1卷卷积码积码的基本概念的基本概念2卷积码是一个有限记忆系统。当信息序列切割卷积码是一个有限记忆系统。当信息序列切割成长度为成长度为k的分组后，分组码单独对各分组编码，的分组后，分组码单独对各分组编码，而卷积码不仅根据本时刻的分组，而且根据本时而卷积码不仅根据本时刻的分组，而且根据本时刻以前的刻以前的L个分组共同来决定编码。个分组共同来决定编码。由于编码过程受由于编码过程受L+1个信息分组的制约，因此个信息分组的制约，因此称称L+1为为约束长度约束长度。约束长度是卷积码的一个基本约束长度是卷积码的一个基本参数，常用参数，常用(n，k，L)来表示某一码长来表示某一码长n、信息位、信息位k、约束长度、约束长度L+1的卷积码。的卷积码。卷卷积码积码是一个有限是一个有限记忆记忆系系统统。当信息序列切割成。当信息序列切割成长长度度3卷积编码器卷积编码器（线性组合器）（线性组合器）ci0c i1c in-2c 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输入输入编码输出编码输出Ci图图5-1卷积编码示意卷积编码示意卷卷积编码积编码器器ci0ci14串串/并并变变换换并并/串串变变换换线线性性组组合合器器m i0mi-10mi-20mi-L0mi1mi-11mi-21mi-L1m i k-1m i-1k-1mi-2k-1m i-Lk-1信号入信号入Mi编码编码输出输出Ci图图5-2卷积编码器的一般结构卷积编码器的一般结构mi0mi-10mi-20mi5 图图5-2记忆阵列记忆阵列中的每一存储单元都有一条连线将中的每一存储单元都有一条连线将数据送到线性组合器，但实际上无需每个单元都有连数据送到线性组合器，但实际上无需每个单元都有连接。因为二元域线性组合时的系数只能选接。因为二元域线性组合时的系数只能选“0”或者或者“1”，选，选“0”时表示该项在线性组合中不起作用，时表示该项在线性组合中不起作用，对应存储单元就不需要连接到线性组合器。从图上看对应存储单元就不需要连接到线性组合器。从图上看到，每一个码元都是到，每一个码元都是k(L+1)个数据线性组合的结果，个数据线性组合的结果，需要有需要有k(L+1)个系数来描述组合规则，于是每一个码个系数来描述组合规则，于是每一个码字需用字需用nk(L+1)个系数才能描述。显然，只有将这些个系数才能描述。显然，只有将这些系数归纳为矩阵才能理顺它们的关系。系数归纳为矩阵才能理顺它们的关系。图图5-2记忆阵记忆阵列中的每一存列中的每一存储单储单元都有一条元都有一条连线连线将数据送将数据送6设设（n,k,L）卷卷积积码码在在时时刻刻i及及i之之前前L个个时时刻刻的的输输入入、输出矢量分别是：输出矢量分别是：时刻时刻输入矢量输入矢量(信息信息)输出矢量输出矢量(码字码字)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个个码码元元是是约约束束长长度度内所有信息比特的线性组合，写作：内所有信息比特的线性组合，写作：设设（n,k,L）卷）卷积码积码在在时时刻刻i及及i之前之前L个个时时7j=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表示该位参与线性组合。表示该位参与线性组合。信息信息论论与与编码编码第六第六讲课讲课件件8例例5.1某某二二进进制制(3,1,2)卷卷积积编编码码器器如如图图5-3所所示示，写出表达其线性组合关系的全部系数。写出表达其线性组合关系的全部系数。解解：本本例例为为码码率率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输入信息行输入信息行时延列时延列输出码元行输出码元行例例5.1某二某二进进制制(3,1,2)卷卷积编码积编码器如器如图图5-3所示所示9例例5.2某某二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，写写出出表达线性组合关系的全部系数。表达线性组合关系的全部系数。解解：本本例例为为码码率率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例例5.2某二某二进进制制(3,2,1)卷卷积编码积编码器如器如图图5-4，写，写10上面两例表明：上面两例表明：从已知的编码电路可以找出对应的系数从已知的编码电路可以找出对应的系数 ，反之，已知系数反之，已知系数 即可画出相应的编码电路。即可画出相应的编码电路。因此，从电路结构角度，因此，从电路结构角度，(5-1)是很好的表达形是很好的表达形式。但是，通常需要从另外各种不同的角度去研究式。但是，通常需要从另外各种不同的角度去研究卷积码，或侧重于卷积码的物理意义，或强调卷积卷积码，或侧重于卷积码的物理意义，或强调卷积码的距离特性，或研究编码器的状态变迁。码的距离特性，或研究编码器的状态变迁。在不同角度，存在着描述卷积码的不同方法。在不同角度，存在着描述卷积码的不同方法。以下介绍四种以下介绍四种卷积码的描述方法卷积码的描述方法：生成矩阵表示法生成矩阵表示法，转移函数矩阵表示法转移函数矩阵表示法，状态流图法状态流图法，网格图表示法网格图表示法。上面两例表明：上面两例表明：115.2卷积码的描述卷积码的描述5.2卷卷积码积码的描述的描述125.2.1生成矩阵表示法生成矩阵表示法由式由式(5-1)，CiT=+1-nic5.2.1生成矩生成矩阵阵表示法表示法13=+=求转置，上式写成：求转置，上式写成：(5-2)式中，式中，G0、G1、GL是是kn矩阵，称作矩阵，称作生成子矩阵生成子矩阵：Gl=l=0,1,L(5-3)14时刻时刻i=0C0=M0G0时刻时刻i=1C1=M0G1+M1G0时刻时刻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)时时刻刻i=0C0=M0G0(5-2)15令令 G0G1G2 G L 00 g G=G0G1G2 GL 0 =Dg (5-6)G0G1G2 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)G0G1G2 GL 0 令令若若码码字序列是一个从字序列是一个从0时时刻开始的无限刻开始的无限长长右右边边序序16例例5.1(续续1)二二进进制制(3,1,2)卷卷积积编编码码器器如如图图5-3。如如果果输入信息流是输入信息流是(101101011100),求输出码字序列。求输出码字序列。解解：对对照照例例5.1算算得得的的系系数数及及式式(5-3)生生成成子子矩矩阵阵的的定定义，可知本题义，可知本题G0=111，G1=011G2=001111011001111011001Ci=(101101011100)111011001111011001=(111,011,110,100,010,110,011,110,100,101,010,001)例例5.1(续续1)二二进进制制(3,1,2)卷卷积编码积编码器如器如图图5-17例例5.2(续续1)某二进制某二进制(3,2,1)卷积编码器如图卷积编码器如图5-4,若若输入信息流是输入信息流是(101101011100)，求输出码字序列，求输出码字序列解：对照例解：对照例5.2算得的系数及式算得的系数及式(5-3)生成子矩阵的生成子矩阵的定义，可知本题定义，可知本题G0=，G1=于是于是101111011100C=(10,11,01,01,11,00)101111011100101111011100=(101,001,000,111,010,011,)101011111100例例5.2(续续1)某二某二进进制制(3,2,1)卷卷积编码积编码器如器如图图185.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卷积码的转移函数矩阵卷积码的转移函数矩阵串串/并并卷积卷积编码器编码器G(D)并并/串串5.2.2多多项项式及式及转转移函数矩移函数矩阵阵表示法表示法19卷卷积积编编码码器器可可视视作作一一个个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 n-1(D)这里，这里，MP(D)、CP(D)的下标的下标P表示表示“并行并行”。虽然虽然M(D)和和 MP(D)数量上有对应关系，然而在数量上有对应关系，然而在数学上有不同含义，数学上有不同含义，M(D)是多项式而是多项式而MP(D)是矩阵。是矩阵。卷卷积编码积编码器可器可视视作一个作一个k端口入、端口入、n端口出的端口出的线线性性20编码器编码器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个输出支路最终的输出由个输出支路最终的输出由全体全体k个输入支路共同决定。个输入支路共同决定。编码编码器器k路路输输入和入和n路路输输出之出之间间的的转转移关系移关系为为21由由于于约约束束长长度度是是L+1,任任何何一一个个子子多多项项式式gj i(D)的的阶阶次不会大于次不会大于L，可用通式表示为，可用通式表示为:=+(5-10)式式(5-10)定定义义的的子子多多项项式式gji(D)的的各各次次系系数数与与式式(5-1)(5-3)中中的的系系数数是是一一致致的的，代代表表第第k个个输输入入支支路路中中第第l个个移移存存器器对对第第j个个输输出出支支路路的的影影响响。可可见见多多项项式式表表示示法法与与矩矩阵阵表表示示法法本本质质一一样样，只只是是多多项项式式表表示示法法通通过过时时延延因因子子D将将L+1个个生生成成子子矩矩阵阵(式式5-3)合合成成一一个个，而而使使矩矩阵阵元元素素由由“数数”变变为为“多多项项式式”。其其优优点点是是能能够够一一目目了了然然地地看看到到并并行行输输入入序序列列和和输输出出序序列列之之间间的的转移关系，而这正是卷积编码器的主要特征。转移关系，而这正是卷积编码器的主要特征。由于由于约约束束长长度是度是L+1,任何一个子多任何一个子多项项式式gji(D)的的阶阶次次22由由式式(5-9)、(5-10)，可可知知第第j个个支支路路的的输输出出是是所所有有输输入入支路对它影响的总和，即支路对它影响的总和，即(5-11)最最后后，利利用用并并/串串变变换换公公式式将将n个个输输出出多多项项式式合合并并成成一一个多项式个多项式(5-12)转移函数矩阵用法归纳如下：转移函数矩阵用法归纳如下：输入信息序列经串输入信息序列经串/并变换得并行的输入多项式；并变换得并行的输入多项式；用式用式(5-11)算出各并行支路的输出多项式；算出各并行支路的输出多项式；用并用并/串转换公式串转换公式(5-12)算出输出多项式算出输出多项式C(D)。由式由式(5-9)、(5-10)，可知第，可知第j个支路的个支路的输输出是所有出是所有输输23例例5.1(续续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)，该卷积编码器的转移函数矩阵是：，该卷积编码器的转移函数矩阵是：G(D)=11+D1+D+D2例例5.1(续续2)二二进进制制(3,1,2)卷卷积编码积编码器如器如图图5-3。24由式由式(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+它们的系数序列分别是：它们的系数序列分别是：C0(D):10110101 C1(D):11101111 C2(D):11000010 并并/串变换，得输出序列串变换，得输出序列C111,011,110,100,010,110,011,110 由式由式(5-11)25例例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串串/并变换后的两个并行输入是：并变换后的两个并行输入是：(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例例5.2(续续2)二二进进制制(3,2,1)卷卷积编码积编码器如器如图图5-4，26C0(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)=(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)。C0(D)=M0(D)g00(D)+M1(D)g01(D)=275.2.3 卷积码的编码矩阵和状态流图卷积码的编码矩阵和状态流图生生成成矩矩阵阵、转转移移函函数数矩矩阵阵重重在在描描述述编编码码器器的的结结构构，状状态态流流图和网格图则利于揭示卷积码内在特性。图和网格图则利于揭示卷积码内在特性。状态：状态：编码器记忆阵列的内容，记作编码器记忆阵列的内容，记作Si。比比如如图图5-3卷卷积积编编码码器器，除除本本时时刻刻输输入入外外还还有有两两个个存存储储器器存存放放前前两两时时刻刻的的输输入入，其其内内容容的的组组合合有有00,01,10,11四四种种可可能能，那那么么这种编码器可有四种状态。这种编码器可有四种状态。一般，图一般，图5-2的移存器阵列有的移存器阵列有k行行L列共列共kL个存储单元，如个存储单元，如果这些单元都参与编码，最多可以有果这些单元都参与编码，最多可以有2kL个状态。可以认为输出个状态。可以认为输出码组码组Ci 是本时刻输入信息组是本时刻输入信息组M i 和本时刻编码器状态和本时刻编码器状态S i 的函数，的函数，表示为表示为:Ci=f(Mi,Mi-1,Mi-L)=f(M i,S i)(5-13)5.2.3卷卷积码积码的的编码编码矩矩阵阵和状和状态态流流图图28状态状态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 iS iLM i-1 M i-L 时刻时刻i的状态的状态 Si 向下一时刻状态向下一时刻状态 Si+1的过渡称为的过渡称为状态状态转移转移。从图。从图5-6可见，卷积编码器状态的转移不是任可见，卷积编码器状态的转移不是任意的，因为移存的规则决定了下一个状态必然是意的，因为移存的规则决定了下一个状态必然是：状状态态Si=h(Mi-1,Mi-L+1,Mi-29 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即本时即本时刻输入信息组一项。对于二进码，刻输入信息组一项。对于二进码，Mi可以有可以有2k种组种组合，所以状态转移也只能有合，所以状态转移也只能有2k种。于是，同样可以种。于是，同样可以把状态转移写成是本时刻信息组把状态转移写成是本时刻信息组Mi 和本时刻编码和本时刻编码器状态器状态Si 的函数的函数:Si+1=h(Mi,Si)(5-14)式式(5-13)、(5-14)的含义是：本时刻输入信息组的含义是：本时刻输入信息组Mi和编码器状态和编码器状态Si一起决定了编码输出一起决定了编码输出Ci和下一状态和下一状态Si+1。由于编码器状态和信息组花样都是有限数量。由于编码器状态和信息组花样都是有限数量的，所以卷积编码器可以看成是一个有限状态机，的，所以卷积编码器可以看成是一个有限状态机，用输入信息组用输入信息组Mi触发的触发的状态转移图状态转移图来描述。来描述。Si+1=h(Mi,Mi-30 在式在式(5-14)决定状态转移的同时，式决定状态转移的同时，式(5-13)也决也决定了输出码组，因此，定了输出码组，因此，确定的状态转移必定伴随着确定的状态转移必定伴随着确定的码组。确定的码组。二元码的二元码的kL个移存器最多可以有个移存器最多可以有2kL个状态，但个状态，但是作为状态机触发信号的是作为状态机触发信号的k重信息分组重信息分组M i只能有只能有2k种种组合方式，组合方式，因此从因此从S i出发，转移到的下一状态只可出发，转移到的下一状态只可能是能是2k种之一，而不是所有的种之一，而不是所有的2kL个状态。个状态。若若某某卷卷积积编编码码器器有有n个个移移存存器器(n kL)，那那么么编编码码器器的的状状态态数数是是2n个个。可可以以构构造造一一个个2n2n 的的编编码码矩矩阵阵，其其i行行j列列的的元元素素cij代代表表从从i状状态态出出发发转转移移到到下下一一时时刻刻j状状态态时时发发出出的的码码组组。如如果果从从i状状态态出出发发不不可可能能转转移移到到j状态，则相应的矩阵元素用状态，则相应的矩阵元素用“.”来表示。来表示。在式在式(5-14)决定状决定状态转态转移的同移的同时时，式，式(5-13)也也31根根据据编编码码矩矩阵阵，可可以以画画出出卷卷积积编编码码器器的的状状态态流流图图。以以状状态态为为节节点点、状状态态转转移移为为分分支支、伴伴随随转转移移的的输输入入/输输出出码码元元与与各各分分支支对对应应，就就不不难难得得到到卷卷积积码码的的状态流图。状态流图。下面的两个例子有助于对编码矩阵和状态流图的下面的两个例子有助于对编码矩阵和状态流图的理解。理解。例例5.1(续续3)二进制二进制(3,1,2)卷积编码器如图卷积编码器如图5-3。试分。试分别用编码矩阵和状态流图来描述该码。如果输入信别用编码矩阵和状态流图来描述该码。如果输入信息流是息流是(101101011100),求输出码字序列。求输出码字序列。根据根据编码编码矩矩阵阵，可以画出卷，可以画出卷积编码积编码器的状器的状态态流流图图。32状态状态m i-10m i-20S000S101S210S311表表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状状态态mi-10mi-20状状态态输输入入33由由表表5-1(a)(b)(c)，可可用用比比表表更更为为简简练练和和直直观观的的编编码码矩阵矩阵来表示该卷积码：来表示该卷积码：编编码码矩矩阵阵若输入信息序列若输入信息序列是是1011010111结果是：结果是：S01/111S20/011S11/110S21/100S30/010S10/000S01/1110/0011/110S2S10/0111/1000/010S31/101图图5-7(3,1,2)卷积码状态流图卷积码状态流图由表由表5-1(a)(b)(c)，可用比表更，可用比表更为简练为简练和直和直观观的的编码编码矩矩34例例5.2(续续3)某某二二进进制制(3,2,1)卷卷积积编编码码器器如如图图5-4，分分别别用用编编码码矩矩阵阵和和状状态态流流图图来来描描述述该该码码。如如果果输输入入信息流是信息流是(101101011100),求输出码字序列。求输出码字序列。解解：本本题题k=2,n=3,有有2个个移移存存器器、4种种状状态态。由由于于每每次次并并行行输输入入2比比特特，即即有有限限状状态态机机触触发发信信号号2比比特特，所所以以从从某某一一状状态态出出发发，下下一一个个状状态态可可以以是是4种种状状态态之之一一。由由图图5-4列列出出类类似似于于表表5-1(a)(b)(c)的的表表后后可可得得(3,2,1)卷积码的编码矩阵如下。卷积码的编码矩阵如下。S0 S1S2S3S0000 101 011 110C=S1111 010 100 001 S2100 001 111 010 S3011 110 000 101例例5.2(续续3)某二某二进进制制(3,2,1)卷卷积编码积编码器如器如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,)状状00/000输输365.2.4 卷积码的网格图卷积码的网格图状状态态流流图图展展示示了了状状态态转转移移的的去去向向，但但不不能能记记录录下下状状态态转转移移的的轨轨迹迹。网网格格图图可可以以弥弥补补这这一一缺缺陷陷。它它可可以以将将状状态态转转移移展展开开在在时时间间轴轴上上，是是分分析析卷卷积积码码的的有有力工具。力工具。网网格格图图以以状状态态为为纵纵轴轴，以以时时间间（抽抽样样周周期期T）为为横横轴轴，将将平平面面分分割割成成格格状状。状状态态和和状状态态转转移移的的定定义义画画法法与与流流图图法法一一样样，也也是是用用一一个个箭箭头头表表示示转转移移，伴伴随随转转移移的的M i/C i表表示示转转移移发发生生时时的的输输入入信信息息组组/输输出出码码组组。所所不不同同的的是是网网格格图图还还体体现现时时间间的的变变化化，一一次次转转移移与与下下一一次次转转移移在在图图上上头头尾尾相相联联。下下面面以以一一个个例例子来说明如何在网格图上画出编码器的工作轨迹。子来说明如何在网格图上画出编码器的工作轨迹。5.2.4卷卷积码积码的网格的网格图图371/1100/001例例5.1(续续4)用用网网格格图图描描述述图图5-3二二进进制制(3,1,2)卷卷积积编编码码器器。若信息序列是若信息序列是(1011010),求输出码字序列。求输出码字序列。解：由例解：由例5.1(续续3)所得的编码矩阵和状态流图，可得所得的编码矩阵和状态流图，可得0/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0001/1111/1101/1110/0101/1000/0010/0111/110S0S1S2S3网格图网格图编码轨迹图编码轨迹图1/1100/001例例5.1(续续4)用网格用网格图图描述描述图图5-3二二进进38当输入当输入5位信息位信息10110时，输出码字和状态转移是时，输出码字和状态转移是S01/111S20/011S11/110S21/100 S30/010S1如如果果继继续续输输入入第第6位位信信息息，信信息息为为0或或1时时，状状态态将将分分别转移到别转移到S0或或S2，而不可能转移到，而不可能转移到S1或或S3。网网格格图图顶顶上上的的一一条条路路径径代代表表输输入入全全0信信息息/输输出出全全0码码字字时时的的路路径径，这这条条路路径径在在卷卷积积码码分分析析时时常常被被用用作作为为参考路径。参考路径。当当输输入入5位信息位信息10110时时，输输出出码码字和状字和状态转态转移是移是39例例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/00001/11111/01000/011网格图网格图编码轨迹图编码轨迹图例例5.2(续续4)二二进进制制(3,2,1)卷卷积编码积编码器如器如图图5-4，40 生成矩阵、转移函数矩阵、状态流图和网格图生成矩阵、转移函数矩阵、状态流图和网格图从不同侧面描述卷积码，各有用处。从不同侧面描述卷积码，各有用处。生成矩阵和转移函数矩阵属同一大类。它们沿生成矩阵和转移函数矩阵属同一大类。它们沿用了分组码的描述方法，建立了代数与编码器的关用了分组码的描述方法，建立了代数与编码器的关联，物理意义清楚，代数量（多项式系数，矩阵元联，物理意义清楚，代数量（多项式系数，矩阵元素）与编码电路连接线之间的对应关系十分明确，素）与编码电路连接线之间的对应关系十分明确，非常利于用非常利于用VHDL等硬件描述语言来表达以及用等硬件描述语言来表达以及用FPGA、DSP等来物理实现。等来物理实现。状态流图和网格图属于另外一类表示法。状态状态流图和网格图属于另外一类表示法。状态流图可借助信号流图等图论工具或理论来分析卷积流图可借助信号流图等图论工具或理论来分析卷积码的特性，网格图则特别适合用于计算机的穷尽搜码的特性，网格图则特别适合用于计算机的穷尽搜索上，它使状态能在时域展开，所得的状态轨迹是索上，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似研究差错事件、卷积码距离特性以及维特比最大似然序列译码的得力工具。然序列译码的得力工具。生成矩生成矩阵阵、转转移函数矩移函数矩阵阵、状、状态态流流图图和网格和网格图图从不同从不同侧侧面描面描415.3 卷积码的特性卷积码的特性5.3卷卷积码积码的特性的特性42 5.3.1 卷积码的特性码率卷积码的特性码率对对于于有有限限长长信信息息序序列列如如M个个k重重，当当M个个分分组组全全部部输输入入编编码码器器后后，虽虽然然再再没没有有新新的的信信息息分分组组输输入入，但但由由于于编编码码器器内内L组组（约约束束长长度度）移移存存器器的的记记忆忆效效应应，编编码码器器将将继继续续输输出出L个个码码字字才才能能将将记记忆忆阵阵列中的内容完全移出，列中的内容完全移出，这就导致这就导致卷积码码率卷积码码率由由R=k/n 降低为降低为。将码率下降的相对值定义为将码率下降的相对值定义为码率损失系数码率损失系数：码率损失系数码率损失系数=(5-15)5.3.1卷卷积码积码的特性的特性码码率率43显然，显然，M相对于相对于L越大则效率损失越小。越大则效率损失越小。当信息序列很长而使当信息序列很长而使M L时，效率损失趋于时，效率损失趋于0因而因而可忽略不计，每一个可忽略不计，每一个k 位信息组产生一个位信息组产生一个n 位码字，卷位码字，卷积编码码率与分组码码率一样为积编码码率与分组码码率一样为R=k/n。相反，相反，M相对于相对于L越小则效率损失越大，当越小则效率损失越大，当M=1时码时码率损失系数接近率损失系数接近1。由此可见，卷积码的适用对象是电路交换的连续信由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的息流，或包交换的“流媒体流媒体”，或复用级的信息流，而，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。不适合短突发、目的地分散的用户端包交换纠错编码。显显然，然，M相相对对于于L越大越大则则效率效率损损失越小。失越小。445.3.2卷积码的距离特性卷积码的距离特性卷卷积积码码的的性性能能取取决决于于卷卷积积码码的的距距离离特特性性和和译译码码算算法法。距距离离特特性性决决定定了了该该码码的的纠纠错错能能力力，而而译译码码方方法法只只是是研研究究如如何何将将这这种种潜在的纠错能力转化为现实的纠错能力。潜在的纠错能力转化为现实的纠错能力。表表述述距距离离特特性性的的最最好好方方法法是是网网格格图图。若若序序列列C、C”是是从从同同一一时时刻刻（不不妨妨称称为为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)5.3.2卷卷积积45 式式(5-16)默认默认,两码字序列之和仍是码字序列。两码字序列之和仍是码字序列。全零序列在网格图上表现为保持在零状态的一条全零序列在网格图上表现为保持在零状态的一条横线，故横线，故两序列的最小距离也就是非全零路径与全零两序列的最小距离也就是非全零路径与全零状态路径距离最小者状态路径距离最小者。序序列列距距离离还还与与序序列列长长度度有有关关，同同一一序序列列对对不不同同长长度度比比较较时时显显然然距距离离也也不不同同。将将长长度度l 的的任任意意两两序序列列间间的的最最小小距距离离定定义义为为l 阶阶列列距距离离。以以长长度度l为为变变量量的的列列距距离特性称之为列距离函数，用离特性称之为列距离函数，用dc(l)来表示来表示：dc(l)mind(Cl,C”l):M0 M”0(5-17)式式(5-16)默默认认,两两码码字序列之和仍是字序列之和仍是码码字序列。字序列。46所所谓谓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(5-19)而而把把由由零零状状态态零零时时刻刻分分叉叉的的无无限限长长的的两两个个序序列列之之间间的的最小距离定义为最小距离定义为自由距离自由距离：df=minW(C):M0 0(5-20)所所谓谓M0M”0即即“不同不同”的两序列，在网格的两序列，在网格图图47列距离、最小距离、自由距离三者之间的关系是：列距离、最小距离、自由距离三者之间的关系是：dmdc(l)|l=L+1(5-21)df=dc(l)(5-22)以下举例说明三个距离的求法。以下举例说明三个距离的求法。例例5-3二进制二进制(3,1,2)卷积码网格图如图卷积码网格图如图5-9，试求该码，试求该码1至至6阶列距离、最小距离和自由距离。阶列距离、最小距离和自由距离。解：距离的求法参见图解：距离的求法参见图5-10。列距离、最小距离、自由距离三者之列距离、最小距离、自由距离三者之间间的关系是：的关系是：48110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111最轻码字序列最轻码字序列 列距离函数列距离函数dc(l)l1S0S2dc(1)=3l2S0S2S3dc(2)=4l3S0S2S3S1dc(3)=5(最小距离最小距离dm)l4S0S2S3S1S0 dc(4)=6或或S0S2S1S0S0l5S0S2S1S0S0 dc(5)=6l6S0S2S1S0S0S0dc(6)=611001101010100010000000000000049 由上例可得到结论：由上例可得到结论：自由距离就是从零状态分叉后又自由距离就是从零状态分叉后又回到零状态的所有路径中重量最轻的那一条的重量。回到零状态的所有路径中重量最轻的那一条的重量。许多早期的卷积码文献都将最小距离许多早期的卷积码文献都将最小距离dm看作是最重要看作是最重要的距离参数，这是由于那时的主要译码算法只有一个约束的距离参数，这是由于那时的主要译码算法只有一个约束长度（长度（L+1）的记忆容量。后来维特比译码和序列译码成）的记忆容量。后来维特比译码和序列译码成为主要方法，这些译码算法的记忆长度在理论上可不受限为主要方法，这些译码算法的记忆长度在理论上可不受限制，因此与这两种译码相联系的自由距离制，因此与这两种译码相联系的自由距离df成了主要的列成了主要的列距离参数。加上距离参数。加上df又是决定卷积码性能的一个主要参数，又是决定卷积码性能的一个主要参数，以致在以致在df逐步替代逐步替代dm的过程中有些论著把这两个概念混为的过程中有些论著把这两个概念混为一谈了。一谈了。df对卷积码的性能是决定性的，有必要专门讨论对卷积码的性能是决定性的，有必要专门讨论一下一下df的计算方法。的计算方法。由上例可得到由上例可得到结论结论：自由距离就是从零状：自由距离就是从零状态态分叉后又回到零分叉后又回到零505.3.4自由距离自由距离d df f的计算的计算 对于像例对于像例5-3-1那样简单的卷积码，可以直接从网格图中找那样简单的卷积码，可以直接从网格图中找出出df。但随着限制长度的增加，状态数将以指数速度增加，网。但随着限制长度的增加，状态数将以指数速度增加，网格图将变得非常复杂庞大，直接找出格图将变得非常复杂庞大，直接找出df往往变得不可能了，于往往变得不可能了，于是各种计算是各种计算df的方法应运而生。一般来说，在状态数小于的方法应运而生。一般来说，在状态数小于16或或32时，可以采用解析法，借助信号流图来求自由距离。当状态时，可以采用解析法，借助信号流图来求自由距离。当状态数较大时，只能依靠计算机的彻底搜索来寻找数较大时，只能依靠计算机的彻底搜索来寻找df。而当状态数。而当状态数非常大时，比如超过非常大时，比如超过2 22020，那么连现有计算机也难以胜任了。以，那么连现有计算机也难以胜任了。以下介绍两种计算方法：信号流图法和计算机搜索法。下介绍两种计算方法：信号流图法和计算机搜索法。5.3.4自由距离自由距离df的的计计算算51（1 1）信号流图法信号流图法 卷积码的状态流图卷积码的状态流图(见见5.2.3节节)与与信号流图信号流图之间具有拓扑等之间具有拓扑等效性，可将信号流图的理论和方法应用于卷积码的研究上。原效性，可将信号流图的理论和方法应用于卷积码的研究上。原则上，利用信号流图可计算任何一个以支路为基础线性积累的则上，利用信号流图可计算任何一个以支路为基础线性积累的量。如果希望这个量以量。如果希望这个量以“和和”的形式积累，可将这个的形式积累，可将这个量写作某量写作某个特定底数的指数，并令其幂为该支路的增益。个特定底数的指数，并令其幂为该支路的增益。若干支路的串若干支路的串联构成一条路径，联构成一条路径，路径增益是组成此路径的各支路增益之乘积路径增益是组成此路径的各支路增益之乘积（其指数是各支路增益指数之和）（其指数是各支路增益指数之和）。作为研究对象的两个节点。作为研究对象的两个节点之间可能有不止一条的路径，所以路径增益的和式便是全图增之间可能有不止一条的路径，所以路径增益的和式便是全图增益，称之为两节点之间考虑对象量的生成函数益，称之为两节点之间考虑对象量的生成函数T(D)。（1）信号流信号流图图法法52 将信号流图法用于自由距离计算时，一个将信号流图法用于自由距离计算时，一个“状态状态”对对应一个节点，我们感兴趣的量是不同转移间的距离（与全应一个节点，我们感兴趣的量是不同转移间的距离（与全零转移相比就是重量），在连续转移中是以和的形式累积零转移相比就是重量），在连续转移中是以和的形式累积的。因此，我们以各转移所对应的码字重量的。因此，我们以各转移所对应的码字重量Wj为指数来定为指数来定义支路增益义支路增益 和路径增益和路径增益 。由于自由距离是由零。由于自由距离是由零状态出发又回到零状态的最轻序列的重量，我们可以将零状态出发又回到零状态的最轻序列的重量，我们可以将零状态拆开成两个节点：一个是始发点，一个是归宿点。这状态拆开成两个节点：一个是始发点，一个是归宿点。这样，沿着任一条由始发点到归宿点的路径都有一个路径增样，沿着任一条由始发点到归宿点的路径都有一个路径增益，其中指数最小者就是最轻路径。益，其中指数最小者就是最轻路径。将信号流将信号流图图法用于自由距离法用于自由距离计计算算时时，一个，一个“状状态态”对应对应一一53 从生成函数从生成函数T(D)的角度看，如果将所有指数相的角度看，如果将所有指数相同的路径增益合并，各路径增益的和式可写作：同的路径增益合并，各路径增益的和式可写作：(5-23)式中，系数式中，系数Ad 是路径增益指数为是路径增益指数为d的不同路径的条数。的不同路径的条数。T(D)最低次非零项的指数就是最轻序列的重量，即最低次非零项的指数就是最轻序列的重量，即自由距离自由距离df。对对(5-23)式的分析揭示了生成函数式的分析揭示了生成函数T(D)与自由距与自由距离离df 的关系，这样就允许我们借用信号流图中所有的关系，这样就允许我们借用信号流图中所有计算生成函数的方法来计算卷积码的自由距离。计算生成函数的方法来计算卷积码的自由距离。从生成函数从生成函数T(D)的角度看，如果将所有指数相同的路径的角度看，如果将所有指数相同的路径54实际中可供选用的方法有三种：实际中可供选用的方法有三种：(1).利利 用用 Mason的的 增增 益益 公公 式式 参参 见见 S.J.MasonElectronicCircuit,signalandsystem1960。这这种种方方法过去使用较多，有人称之为标准方法。法过去使用较多，有人称之为标准方法。(2).根根据据有有向向图图列列出出线线性性状状态态方方程程，从从而而把把“图图解解”的的问问题题转转化化为为解解线线性性方方程程的的问问题题。这这是是一一种种经经典典的的方方法法。因因为为列列方方程程有有一一定定的的规规律律，解解方方程程则则有有许许多现成的程序和方法可供使用。多现成的程序和方法可供使用。(3).通通过过图图论论变变换换吸吸收收部部分分节节点点，从从而而简简化化甚甚至至直直接求出生成函数接求出生成函数T(D)，这适用于较简单的流图。，这适用于较简单的流图。实际实际中可供中可供选选用的方法有三种：用的方法有三种：55例例5-4二进制二进制(3,1,2)卷积码状态流图如图卷积码状态流图如图5-7。试用。试用信号流图法求该码自由距离信号流图法求该码自由距离df。解：将卷积码状态图（图解：将卷积码状态图（图5-7）的零状态）的零状态S0拆成一始拆成一始发一归宿两个节点发一归宿两个节点(图图5-12),状态的自环是全零码，状态的自环是全零码，在信号流图中不画出。令各支路的增益为在信号流图中不画出。令各支路的增益为D j（这里（这里j是与相应转移对应的码字重量，比如码字是与相应转移对应的码字重量，比如码字011的重的重量为量为2，对应的支路增益是，对应的支路增益是D2），可得信号流图），可得信号流图(图图5-13)。再根据。再根据信号流图的一些初等变换规则信号流图的一些初等变换规则（图（图5-14），将图），将图5-13步步简化（图步步简化（图5-15），最后得到生），最后得到生成函数：成函数：例例5-4二二进进制制(3,1,2)卷卷积码积码状状态态流流图图如如图图5-7。试试用用56101S3100010111110001S0S2S1S0011图图5-12零状态拆分后零状态拆分后的状态流图的状态流图图图5-13相应信号流图相应信号流图和各支路增益和各支路增益D2 DDS0D3S2D2S1DS0D257ABA BAA+BBBBCADABDCAB图图5-14信号流图的初等变换信号流图的初等变换AB1-CCD2D3DD图图5-15卷积码信号流图的简化卷积码信号流图的简化D21-D2D2ABCD2D258运用多项式除法（长除法），得：运用多项式除法（长除法），得：(5-24)(5-24)这这是一个无限多项式，多项式的每项对应网格图上是一个无限多项式，多项式的每项对应网格图上的一类非零路径：幂次表示此类非零路径的重量，的一类非零路径：幂次表示此类非零路径的重量，系数表示具有此重量的非零路径的条数。比如，系数表示具有此重量的非零路径的条数。比如，(5.24)式式生成函数告诉我们：从零状态分叉又回到零生成函数告诉我们：从零状态分叉又回到零状态的非零路径中，有状态的非零路径中，有2条是重量为条是重量为6的序列，有的序列，有1条条重量为重量为8，有，有5条重量为条重量为10。显然，自由距离等于。显然，自由距离等于其中最轻者即次数最低的第一项，本例其中最轻者即次数最低的第一项，本例df6。运用多运用多项项式除法（式除法（长长除法），得：除法），得：59110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111对照例对照例5-3的图的图5-11，可以验证，可以验证df确是确是6，而且重量，而且重量为为6的最轻非零序列确有两条，的最轻非零序列确有两条，一条是一条是S0S2S1S0,另一条是另一条是S0S2S3S1S0。重量为重量为8的非零路径有一条，的非零路径有一条，即即S0S2S3S3S1S0。11001101010100010000000000000060（2 2）计算机搜索法）计算机搜索法与与维维特特比比译译码码算算法法的的思思路路相相同同，只只要要知知道道卷卷积积码码网网格格图图，就就可可以以利利用用事事先先编编好好的的程程序序很很快快求求出自由距离。出自由距离。设设某某卷卷积积码码网网格格图图有有N个个状状态态，任任何何一一个个状状态态j(j=0,1,2N-1)可可以以由由上上一一