物种起源读后感：一步一惊心的人生

卷积码是一个有限记忆系统。当信息序列切割成长度k的一个个分组后，分组码单独对各分组编码，而卷积码不仅根据本时刻的分组，而且根据本时刻以前的L个分组共同来决定编码。 由于编码过程受L+1个信息分组的制约，因此称L+1为约束长度（ConstraintLength），也有的人直接把L称为约束长度。约束长度是卷积码的一个基本参数，我们常用(n，k，L)来表示某一码长n、信息位k、约束长度L+1的卷积码。约束长度的单位用“分组”而不用“码元”，是因为编码和译码时的约束分组数是一样的，而约束码元数却是不同的，编、译码时的约束码元数分别是(L+1)k与(L+1)n。/6/89.html1

卷积编码器（线性组合器）ci0c

i1…cin-2cin-1

第i分组第i-1分组第i-2分组……第i-L分组mi0mi1…mik-1mi-10…mi-1k-1m

i-20…m

i-2k-1…mi-L

0mi-L

1…mi-L

k-1输入编码输出Ci图5-1卷积编码示意2串/

并变换并/

串变换线性组合器m

i0mi-10mi-20…mi-L

0mi1mi-11mi-21…mi-L

1m

ik-1mi-1k-1m

i-2k-1…mi-L

k-1信号入m

i

编码输出

Ci

┇┇……┇┇图5-2卷积编码器的一般结构

3 图5-2记忆阵列中的每一存储单元都有一条连线将数据送到线性组合器，但实际上无需每个单元都有连接。这是因为二元域线性组合时的系数只能选“0”或者“1”，选“0”时表示该项在线性组合中不起作用，对应存储单元就不需要连接到线性组合器。从图上看到，每一个码元都是k×(L+1)个数据线性组合的结果，需要有k×(L+1)个系数来描述组合规则，于是每一个码字需用

n×k×(L+1)个系数才能描述。显然，只有将这些系数归纳为矩阵才能理顺它们的关系和便于使用。

4设（n,k,L）卷积码在时刻i及i之前L个时刻的输入、输出矢量分别是：时刻输入矢量(信息) 输出矢量(码字)i

Mi=(mi0,mi1

,…,mik-1) Ci=(ci0,ci1

,…,cin-1)i-1Mi-1=(mi-10,mi-11…mi-1k-1) Ci-1=(ci-10,ci-11…ci-1n-1)┇

┇

┇i-LMi-L=(mi-L0,mi-L1…mi-Lk-1)Ci-L=(ci-L0,ci-L1…ci-Ln-1)这里,大写字母表示码组，小写字母表示码元，上标表示码字中的码元顺序，下标表示时序。在任意时刻i,卷积码码字的第j个码元是约束长度内所有信息比特的线性组合，写作：5

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表示该位参与线性组合。

6例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

信号 ci0入Mi 输出

ci1C

i

c

i2图5-3二元(3,1,2)卷积编码器mi0mi-10mi-20输入信息行时延列输出码元行7例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入Mi

ci1输出

c

i2图5-4二进制(3,2,1)卷积编码器mi

0mi-10mi

1m

i-118上面两例表明，

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

95.2.1生成矩阵表示法

由式(5-1)，CiT

┇┇┇┇

=

=

=

+…10 … … = … +…+…

┇┇┇┇ … …=

求转置，上式写成： (5-2)式中，G0、G1、…GL是k×n矩阵，称作生成子矩阵：

…

Gl

= …l=0,1,…,L(5-3)

┇┇…11时刻i=0 C0=M0G0

时刻i=1 C1=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时刻)的信息组(MiMi-1…Mi-L)与生成子矩阵组(G0G1…GL)的卷积，这也就是卷积码名称的来历。(5-2)12令 G0 G1G2…GL00……

gG= G0G1G2…GL0……

=

Dg

(5-6) G0G1G2…GL

0… D2g ┆ ┆定义g

为基本生成矩阵，定义G为生成矩阵若码字序列是一个从0时刻开始的无限长右边序列，可写成有头无尾的半无限矩阵形式：C=C0,C1,

…，CL,CL+1,…） G0G1G2…GL0

……=(M0,…,ML,ML+1,…)

G0G1G2…GL0…

(5-5)

G0G1G2…GL0

…

┆13例5.1(续1)二进制(3,1,2)卷积编码器如图5-3。如果输入信息流是(101101011100…),求输出码字序列。解：对照例5.1算得的系数及式(5-3)生成子矩阵的定义，可知本题G0=[]=[111]，G1=[ ]=[011]G2=[ ]=[001] 111011001 111011001Ci=(101101011100…)111011001 111011001 ┆=(111,011,110,100,010,110,011,110,100,101,010,001┄)

14例5.2(续1)某二进制(3,2,1)卷积编码器如图5-4,若输入信息流是(101101011100…)，求输出码字序列解：对照例5.2算得的系数及式(5-3)生成子矩阵的定义，可知本题G0= =，G1==于是 101111 011100C=(10,11,01,01,11,00…) 101111 011100 101111 011100┄=(101,001,000,111,010,011,…)101011111100155.2.2多项式及转移函数矩阵表示法若M(D)=m0+m1D…+mkDk+mk+1Dk+1+…

…

+m2kD2k+m2k+1D2k+1+…，则串/并变换后M0

(D)=m0+mkD+m2kD2+…M1

(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)并/串16卷积编码器可视作一个k端口入、n端口出的线性多端口网络，可以用转移函数矩阵来描述其输入、输出间的数量关系。卷积编码器的特殊之处，在于其输入、输出均是无限长多项式，转移函数矩阵元素也是多项式。定义输入、输出多项式矩阵MP(D)、CP(D)为：M(D)串/并

MP(D)=[M0

(D),M1

(D),…Mk-1

(D)]C

(D)串/并

CP(D)=[C0

(D),C1

(D),…Cn-1

(D)]

这里，MP(D)、CP(D)的下标P表示“并行”。虽然M

(D)和MP(D)数量上有对应关系，然而在数学上有不同含义，M

(D)是多项式而MP(D)是矩阵17编码器k路输入和n路输出之间的转移关系为CP(D)

=MP(D)G

(D) (5-8)G(D)是k×n转移函数矩阵，

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列元素gji(D)描述了第i个输入支路如何对第j个输出支路产生影响的转移关系，也称子多项式，而第j个输出支路最终的输出是由全体k个输入支路共同决定的。

18由于约束长度是L+1,任何一个子多项式gji(D)的阶次不会大于L，可用通式表示为=+…+ (5-10)式(5-10)定义的子多项式gji(D)的各次系数与式(5-1)(5-3)中的系数是一致的，代表第k个输入支路中第l个移存器对第j个输出支路的影响。可见多项式表示法与矩阵表示法本质是一样的，只是多项式表示法通过时延因子D将L+1个生成子矩阵(式5-3)合成一个，而使矩阵元素由“数”变为“多项式”。其优点是能够一目了然地看到并行输入序列和输出序列之间的转移关系，而这正是卷积编码器的主要特征19由式(5-9)、(5-10)，可知第j个支路的输出是所有输入支路对它影响的总和，即 (5-11)最后，利用并/串变换公式将n个输出多项式合并成一个多项式 (5-12)转移函数矩阵用法归纳如下①输入信息序列经串/并变换得并行的输入多项式②用式(5-11)算出各并行支路的输出多项式③用并/串转换公式(5-12)算出输出多项式C(D)。

20例5.1(续2)二进制(3,1,2)卷积编码器如图5-3。如果输入信息流(101101011100…),求输出码字序列。解：本题为一路输入(k=1)、三路输出(n=3)，因此转移函数矩阵是1×3的多项式矩阵。一路输入为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)=[11+D1+D+D2]21由式(5-11)C0(D)=M0(D)g00(D)=(1+D2+D3+D5+D7+D8+D9…)1=1+D2+D3+D5+D7+D8+D9…C1(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+D7…C2(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┅并/串变换，得输出序列C＝{111,011,110,100,010,110,011,110┅}22例5.2(续2)二进制(3,2,1)卷积编码器如图5-4，若输入信息流是(101101011100…)，求输出码字序列。解：本题k=2,n=3,转移函数矩阵是2×3多项式矩阵。输入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)=D1123C0(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┅)。

245.2.3卷积码的编码矩阵和状态流图生成矩阵、转移函数矩阵重在描述编码器的结构，状态流图和网格图则利于揭示卷积码内在特性。状态：编码器记忆阵列的内容，记作Si

比如图5-3卷积编码器，除本时刻输入外还有两个存储器存放前两时刻的输入，其内容的组合有00,01,10,11四种可能，我们就说这种编码器可有四种状态一般，图5-2的移存器阵列有k行L列共k×L个存储单元，如果这些单元都参与编码，最多可以有2kL个状态。我们可以认为输出码组Ci

是本时刻输入信息组Mi

和本时刻编码器状态Si

的函数，表示为Ci=f(Mi,Mi-1,…,Mi-L

)=f(Mi,Si

) (5-13)25状态Si=h(Mi-1,…,Mi-L+1,Mi-L

),如图5-6所示

图5-6

状态和状态转移串/

并变换线性组合器m

i0mi-10…mi-L

0m

i1mi-11…mi-L

1m

ik-1mi-1k-1…mi-L

k-1┇┇MiSiLMi-1

Mi-L…

时刻i的状态Si向下一时刻状态Si+1的过渡称为状态转移。从图5-6可见，卷积编码器状态的转移不是任意的，因为移存的规则决定了下一个状态必然是：26Si+1=h(Mi,Mi-1,…,Mi-L+1

)将Si与Si+1作比较，可知Si+1中的(Mi-1,…,Mi-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触发的状态转移图来描述。27在式(5-14)决定状态转移的同时，式(5-13)也决定了输出码组，因此确定的状态转移必定伴随着确定的码组。二元码的kL个移存器最多可以有2kL个状态，但是作为状态机触发信号的k重信息分组Mi只能有2k种组合方式，

因此从Si出发，转移到的下一状态只可能是2k种之一，而不是所有的2kL个状态。若某卷积编码器有n个移存器(nkL)，那么编码器的状态数是2n个。我们可以构造一个2n×2n的编码矩阵，其i行j列的元素cij代表从i状态出发转移到下一时刻j状态时发出的码组。如果从i状态出发不可能转移到j状态，则相应的矩阵元素用“.”来表示28根据编码矩阵，我们可以画出卷积编码器的状态流图。以状态为节点、状态转移为分支、伴随转移的输入/输出码元与各分支对应，就不难得到卷积码的状态流图。下面的两个例子将有助于我们对编码矩阵和状态流图的理解。

例5.1(续3)二进制(3,1,2)卷积编码器如图5-3。试分别用编码矩阵和状态流图来描述该码。如果输入信息流是(101101011100…),求输出码字序列。

29状态mi-10mi-20S0 0 0S1 0 1S2 1 0S3 1 1表5-1(a)编码器状态的定义

状态输入m0i=0m0i=1S0 000 111S1 001 110S2 011 100S3 010 101表5-1(b)不同状态与输入时编出的码字状态输入 m0i=0m0i=1S0 S0 S2S1 S0 S2S2 S1 S3S3 S1 S3表5-1(c)不同状态Si与输入时的下一状态Si+1信号 ci0入Mi 输出

ci1C

i

c

i2

mi0mi-10mi-2030由表5-1(a)(b)(c)，可用比表更为简练和直观的编码矩阵来表示该卷积码：编码矩阵

若输入信息序列是1011010111…

结果是：S0

1/111S2

0/011

S11/110S2

1/100S30/010

S1……

0/000S01/1110/0011/110S2S10/0111/1000/010S31/101

图5-7(3,1,2)卷积码状态流图31例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 S1 S2 S3

S0

000 101 011 110 C=S1 111 010 100 001

S2

100 001 111 010

S3

011 110 000 10132状态流图

00/000

S000/10001/01100/11110/10100/01111/11001/11110/00110/010

S2

S101/10001/00011/01010/11011/001

S311/101

输入序列(10,11,01,01,11,00,┅)2bit/信息组S0

10/101S111/001S301/000S2

01/111S211/010S300/011S0

…对应码字序列为(101,001,000,111,010,011,…)335.2.4卷积码的网格图状态流图展示了状态转移的去向，但不能记录下状态转移的轨迹。网格图（或称格栅图）可以弥补这一缺陷。它可以将状态转移展开在时间轴上，使编码全过程跃然纸上，是分析卷积码的有力工具。网格图以状态为纵轴，以时间（抽样周期T）为横轴，将平面分割成格状。状态和状态转移的定义画法与流图法一样，也是用一个箭头表示转移，伴随转移的Mi/Ci表示转移发生时的输入信息组/输出码组。所不同的是网格图还体现时间的变化，一次转移与下一次转移在图上头尾相联。下面以一个例子来说明如何在网格图上画出编码器的工作轨迹。34例5.1(续4)用网格图描述图5-3二进制(3,1,2)卷积编码器。若信息序列是(1011010…),求输出码字序列。解：由例5.1(续3)所得的编码矩阵和状态流图，可得1/1100/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0001/1111/1100/0011/1110/0101/1000/0010/0111/110S0S1

S2S3网格图编码轨迹图35当输入5位信息10110时，输出码字和状态转移是S0

1/111S2

0/011S11/110S2

1/100 S30/010S1如果继续输入第6位信息，信息为0或1时，状态将分别转移到S0或S2，而不可能转移到S1或S3。网格图顶上的一条路径代表输入全0信息/输出全0码字时的路径，这条路径在卷积码分析时常被用作为参考路径。

36例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网格图编码轨迹图37卷积码的四种描述方法生成矩阵、转移函数矩阵、状态流图和网格图从不同侧面描述卷积码，各有用处。生成矩阵和转移函数矩阵属同一大类，它们沿用了分组码的描述方法，建立了代数与编码器的关联。特点是物理意义清楚，代数量（多项式系数，矩阵元素）与编码电路连接线之间的对应关系十分明确，非常利于用VHDL等硬件描述语言来表达以及用FPGA、DSP等来物理实现。状态流图和网格图属于另外一类表示法，状态流图可借助信号流图等图论工具或理论来分析卷积码的特性，网格图则特别适合用于计算机的穷尽搜索上，它使状态能在时域展开，所得的状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似然序列译码最得力的工具。

38

5.3.1卷积码的特性－码率对于有限长信息序列如M个k重，当M个分组全部输入编码器后，虽然再没有新的信息分组输入，但由于编码器内L组（约束长度）移存器的记忆效应，编码器将继续输出L个码字才能将记忆阵列中的内容完全移出，这就导致卷积码码率由R=k/n降低为。我们将码率下降的相对值定义为码率损失系数：码率损失系数= (5-15)39显然，M相对于L越大则效率损失越小。当信息序列很长而使M>>L时，效率损失趋于0因而可忽略不计，每一个k位信息组产生一个n位码字，卷积编码码率与分组码码率一样为R=k/n。相反，M相对于L越小则效率损失越大，当M=1时码率损失系数接近1。由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的“流媒体”，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。405.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(C0)=d(C,0)(5-16)41式(5-16)默认：两码字序列之和仍是码字序列，这样任意两码字序列间最小距离才能等效于全零序列与某非全零序列的距离。全零序列在网格图上表现为保持在零状态的一条横线，故两序列的最小距离也就是非全零路径与全零状态路径距离最小者。序列距离还与序列长度有关，同一序列对在不同长度比较时显然距离也不同。我们将长度l的任意两序列间的最小距离定义为l阶列距离。以长度l为变量的列距离特性称之为列距离函数，用dc(l)来表示：dc(l)min{d([C']l,[C”]l):[M']0[M”]0}(5-17)＝42所谓[M‘]0[M”]0即“不同”的两序列，在网格图上的表现就是从零时刻起两序列轨迹从零状态分道扬镳形成分叉点。由式(5-16)，式(5-17)可改写为dc(l)＝min{W([C']l＋[C”]l):[M']0[M”]0}=min{W([C]l):[M]00} (5-18)由于早期卷积码译码方法与约束长度（L+1）有关，于是曾把（L+1）阶列距离称为最小距离dm

dm=min{W([C]L+1):[M]00} (5-19)而把由零状态零时刻分叉的无限长的两个序列之间的最小距离定义为自由距离：df=min{W([C]

):[M]00} (5-20)43列距离、最小距离、自由距离三者之间的关系是：dm＝dc(l)|l=L+1 (5-21)df=dc(l) (5-22)以下举例说明三个距离的求法。例5-3二进制(3,1,2)卷积码网格图如图5-9，试求该码1至6阶列距离、最小距离和自由距离。解：距离的求法参见图5-10。

44110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111

最轻码字序列 列距离函数dc(l)

l＝1S0S2

dc(1)=3

l＝2S0S2S3

dc(2)=4

l＝3S0S2S3S1

dc(3)=5(最小距离dm)

l＝4S0S2S3S1S0

dc(4)=6 或S0S2S1S0

S0

l＝5S0S2S1S0

S0

dc(5)=6

l＝6S0S2S1S0

S0

S0

dc(6)=645由上例我们可以推广出一个一般的结论：自由距离就是从零状态分叉后又回到零状态的所有路径中重量最轻的那一条的重量。许多早期的卷积码文献都将最小距离dm看作是最重要的距离参数，这是由于那时的主要译码算法只有一个约束长度（L+1）的记忆容量。后来维特比译码和序列译码成为主要方法，这些译码算法的记忆长度在理论上可不受限制，因此与这两种译码相联系的自由距离df成了主要的列距离参数。加上df又是决定卷积码性能的一个主要参数，以致在df逐步替代dm的过程中有些论著把这两个概念混为一谈了。df对卷积码的性能是决定性的，我们有必要专门讨论一下df的计算方法。

465.3.1

自由距离df的计算对于像例5-3-1那样简单的卷积码，我们可以直接从网格图中找出df。但随着限制长度的增加，状态数将以指数速度增加，网格图将变得非常复杂庞大，直接找出df往往变得不可能了，于是各种计算df的方法应运而生。一般来说，在状态数小于16或32时，可以采用解析法，借助信号流图来求自由距离。当状态数较大时，只能依靠计算机的彻底搜索来寻找df。而当状态数非常大时，比如超过220，那么连现有计算机也难以胜任了。以下我们介绍两种计算方法：信号流图法和计算机搜索法。

47一．

信号流图法卷积码的状态流图(见5.2.3节)与信号流图之间具有拓扑等效性，我们可将信号流图的理论和方法应用于卷积码的研究上。原则上，利用信号流图可计算任何一个以支路为基础线性积累的量。如果希望这个量以“和”的形式积累，可将这个量写作某个特定底数的指数，并令其幂为该支路的增益。若干支路的串联构成一条路径，路径增益是组成此路径的各支路增益之乘积（其指数是各支路增益指数之和）。作为研究对象的两个节点之间可能有不止一条的路径，所以路径增益的和式便是全图增益，称之为两节点之间考虑对象量的生成函数T(D)。48将信号流图法用于自由距离计算时，一个“状态”对应一个节点，我们感兴趣的量是不同转移间的距离（与全零转移相比就是重量），在连续转移中是以和的形式累积的。因此，我们以各转移所对应的码字重量Wj为指数来定义支路增益和路径增益。由于自由距离是由零状态出发又回到零状态的最轻序列的重量，我们可以将零状态拆开成两个节点：一个是始发点，一个是归宿点。这样，沿着任一条由始发点到归宿点的路径都有一个路径增益，其中指数最小者就是最轻路径。49从生成函数T(D)的角度看，如果将所有指数相同的路径增益合并，各路径增益的和式可写作：

(5-23)式中，系数Ad是路径增益指数为d的不同路径的条数。T(D)最低次非零项的指数就是最轻序列的重量，即自由距离df

。

对(5-23)式的分析揭示了生成函数T(D)与自由距离df

的关系，这样就允许我们借用信号流图中所有计算生成函数的方法来计算卷积码的自由距离。

50实际中可供选用的方法主要有三种：(1).利用Mason的增益公式[参见S.J.MasonElectronicCircuit,signalandsystem1960]。这种方法过去使用较多，有人称之为标准方法。(2).根据有向图列出线性状态方程，从而把“图解”的问题转化为解线性方程的问题。这是一种经典的方法。因为列方程有一定的规律，解方程则有许多现成的程序和方法可供使用。(3).通过图论变换吸收部分节点，从而简化甚至直接求出生成函数T(D)，这适用于较简单的流图51例5-4二进制(3,1,2)卷积码状态流图如图5-7。试用信号流图法求该码自由距离df。解：将卷积码状态图（图5-7）的零状态S0拆成一始发一归宿两个节点(图5-12),状态的自环是全零码，在信号流图中不画出。令各支路的增益为Dj

（这里j是与相应转移对应的码字重量，比如码字011的重量为2，对应的支路增益是D2），可得信号流图(图5-13)。再根据信号流图的一些初等变换规则（图5-14），将图5-13步步简化（图5-15），最后得到生成函数：

52

101S3100010111110001S0S2S1S0011

图5-12零状态拆分后的状态流图图5-13相应信号流图和各支路增益

D2 D

DS0D3S2

D2S1DS0

D253ABABAA+BB

BBCADABDC

AB图5-14信号流图的初等变换AB1-CC

D2

D3D

D图5-15卷积码信号流图的简化

D2

1-D2

D254运用多项式除法（长除法），得：(5-24)这是一个无限多项式，多项式的每项对应网格图上的一类非零路径：幂次表示此类非零路径的重量，系数表示具有此重量的非零路径的条数。比如，(5.24)式生成函数告诉我们：从零状态分叉又回到零状态的非零路径中，有2条是重量为6的序列，有1条重量为8，有5条重量为10…。显然，自由距离等于其中最轻者即次数最低的第一项，本例df＝6。55110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111对照例5-3的图5-11，可以验证df确是6，而且重量为6的最轻非零序列确有两条，一条是S0S2S1S0,另一条是S0S2S3S1S0。重量为8的非零路径有一条，即S0S2S3S3S1S0。

56二.计算机搜索法

这种方法吸取了维特比译码算法的思路，只要知道卷积码网格图，就可以利用事先编好的程序很快求出自由距离，这是目前最实用的方法。设某卷积码网格图有N个状态，任何一个状态j(j=0,1,2…N-1)可以由上一时刻的K个状态转移而来，我们把可能转移到j状态的上一状态(predecessor)记作：

P(i,j)(i=0,1,…K-1,j=0,1,…N-1)而把与上述转移对应的码字重量记作W(i,j)(见图5-16)。57状态(l-1)时刻l时刻S0 S1P(0,j)

¦

¦P(1,j)

jSjP(2,j)

¦

SN-2P(K-1,j) SN-1 图5-16计算机搜索最轻路径设(l-1)时刻到达j状态最轻序列的重量是d(l-1)(j)，l时刻到达j状态的最轻路由的重量是d(l)(j)，那么计算d(l)(j)的方法应是将所有l时刻能够到达j状态的K个前状态P(i,j)在(l-1)时刻的重量d(l-1)(P(i,j))加上本次转移的重量，然后在K个结果中选出最轻者作为d(l)(j)。用数学语言表示即 (5-25)585.3.4系统码与恶性码(catastrophiccode)系统(systematic)卷积码是最常用的卷积码，与系统分组码类似，它是卷积码的一个子类。一个(n,k,L)系统卷积码的主要特征是其i时刻的输出码组Ci由两部分构成：前k位原封不动就是i时刻的输入信息组Mi，后(n-k)位则是校验位，是i到(i-L)各时刻各输入信息比特的线性组合(见图5-17)。

mi0 ci0信息入mi1 ci1

MI ┇ ┇ mik cik cik+1 ┇ ciN-1图5-17系统卷积码结构特点

串/并记忆阵列线性组合59如果采用转移函数矩阵来表示，系统卷积码的转移函数矩阵应符合如下形式(对照5-9式)：

10…0gk0(D)gk+10(D)…gn-10(D)

G

(D)=010…0gk1(D)gk+11(D)…gn-11(D) ┆ ┆ 00…01gkk-1(D)gk+1k-1(D)…gn-1k-1(D)对照例5.1

G(D)=[11+D1+D+D2]，是系统卷积码例5.2G(D)=1+DD1+D,非系统卷积码 D1160系统码优点之一：前k位无需编码，简单易行。系统码优点之二：译出码字Ci后可直接还原出信息Mi，无需复杂计算，是一类快检码。而非系统码在译码时必须用转移函数逆矩阵G-1(D)对接收码组进行某种运算才能完成。转移函数逆矩阵G-1(D)是转移函数矩阵G(D)的逆，但它与一般逆矩阵的概念有所不同。按照编码理论，G-1(D)必须满足关系式：G(D)G-1(D)=IkDl (5-29)

C(D)G-1(D)=M(D)G(D)G-1(D