信息论与编码-卷积码

卷积码本章节教学内容、基本要求、重点与难点1.

教学内容：卷积码的基本概念。卷积码的编码与译码。卷积码的矩阵描述。卷积码的状态转移图与栅格描述。维特比译码的基本原理。维特比译码的性能与应用。2.

教学基本要求：掌握卷积码的编码方法。

了解卷积码的生成矩阵的表示法。

掌握卷积码的状态转移图与栅格描述。

掌握卷积码的维特比译码的基本原理和算法实现。

3.

重点与难点：

卷积码的编码。卷积码的状态转移图与栅格描述。

维特比译码的基本原理。

卷积码（又称连环码）首先由麻省理工学院于1955年提出。卷积码与分组码的不同之处：在任意给定单元时刻，编码器输出的n个码元中，每一个码元不仅和此时刻输入的k个信息元有关，还与前连续m个时刻输入的信息元有关。在同样的编码效率R下，卷积码的性能优于分组码，至少不低于分组码。卷积码的译码方法代数译码：门限译码。译码延时是固定的。概率译码：序列译码。译码延时是随机的。维特比译码。译码延时是固定的。卷积码的基本概念卷积码的生成序列、约束度和约束长度[例1](2,1,3)码该码的编码原理图示于下页图；设待编码的信息序列为M；在对信息序列M进行编码之前，先将它每k个码元分成一组，在每单元时刻内，k个码元串行输入到编码器；编码器由(m+1)个移位寄存器组构成，每个移位寄存器组内有k级寄存器；g(i,j)：表示常数乘法器，i=1,2,…,k；j=1,2,…,n；共有n•k

个序列。当g(i,j)=1时，常数乘法器为一条直通的连接线；当g(i,j)=0时，连接线断开。每一个码元都是k•(m+1)个数据组合，每一个码字需用n•k•(m+1)

个系数才能描述；开关K在每一节拍中移动n次，每一节拍输入k个信息元而输出n个码元。信息序列M=[m0(1)m1(1)…]；ml(1)表示第l个时刻的第k=1个信息元；卷积码的生成序列

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]g(1,1)表明：任一时刻l时，输出端1的码元Cl(1)是由此时刻l输入的信息元ml(1)与前两个时刻输入的信息元ml－2(1)以及前三个时刻ml－3(1)输入的信息元模2加后的和；g(1,2)表明：Cl(2)是由ml(1)、ml－1(1)、ml－2(1)和ml－3(1)的模2和。只要给定g(i,j)以后，就可以生成编码器输出的码元。称g(1,1)和g(1,2)为(2,1,3)卷积码的生成序列。第l个时刻的编码器输出为：上式表明：任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出。这就是卷积码名称的由来。设M=[m0(1)m1(1)m2(1)m3(1)]=[1011]，则编码器两个输出端的序列分别是子码：在任一时刻单元，送入编码器一个信息元(k=1)，编码器输出由2个(n=2)码元组成的一个码组，称之为子码。每个子码中的码元不仅与此时此刻的信息元有关，而且还与前m个(m=3)时刻的信息元有关。m：编码存储（本例

m=3）

。N=m+1：为编码的约束度。（本例N=4）。N

n：编码约束长度。（本例N

n=8）。本例是非系统码，在码序列C中的每个子码不是系统码字结构。[例2](3,2,1)码n=3,k=2,m=1；它的任一子码有3个码元。每个码元由此时此刻的2个信息元和前一个时刻进入编码器的2个信息元模2运算和求出。这些信息元参加模2运算的规则由[n(m+1)]=3×2=6个生成序列{[n

k

(m+1)]=3×2×2=12个系数}所确定，每个输出序列含有2个元素。这6个输出序列是

g(1,1)=[g0(1,1)

g1(1,1)]=[11]g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(1,3)=[g0(1,3)

g1(1,3)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]g(2,3)=[g0(2,3)

g1(2,3)]=[10]若待编码的信息序列M=[m0(1)m0(2)m1(1)m1(2)…ml(1)ml(2)…]则码序列C中的任一子码为g(1,1)=[g0(1,1)

g1(1,1)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]g(1,3)=[g0(1,3)

g1(1,3)]=[11]g(2,3)=[g0(2,3)

g1(2,3)]=[10]每个时刻单元输入编码器k=2个信息元，它们与前一个时刻进入编码器的2个信息元按卷积关系进行运算后，在输出端1，2，3分别得到该时刻子码中的3个码元。编码器由N=2个移位寄存器组和模2加法器构成，每个移位寄存器组含有k=2级移位寄存器，每级移位寄存器的输出按一定规则引出后进行模2加的运算。本例也是非系统码形式的卷积码。推论：(n,k,m)码完全由(n

k)个生成序列所生成，每个生成序列中含有(N=m+1)

个元素。码序列C=[C0(1)C0(2)…C0(n)C1(1)C1(2)…C1(n)…Cl(1)Cl(2)…Cl(n)…]

任一子码可以由待编码的信息序列M=[m0(1)m0(2)…m0(k)m1(1)m1(2)…m1(k)…ml(1)ml(2)…ml(k)…]

按如下卷积关系求出系统码形式的卷积码系统卷积码：是卷积码的一类。它的码序列中任一子码Cl，也是有n个码元，其前k位与待编码信息序列中的第l信息组ml(i)相同，而后(n－k)

位监督元由生成序列生成；每个码中的前k位就是此时刻待编码的k位信息元，所以在生成序列g(i,j)中有(k

k)

个生成序列是固定的,即任一子码由下式计算上式表明：在约束长度N内，每个子码中的(n－k)个监督元与信息元的卷积关系。[例3](3,1,2)系统卷积码：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[110]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]任一时刻子码为[例4](3,2,2)系统卷积码：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]该码的任一子码Cl

中前两位与ml(1)、ml(2)相同，后一位的监督元由卷积

确定，即g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110](1)串行输入、串行输出的编码电路非系统码编码器：根据下式构造的是非系统编码器。卷积码的编码系统码编码器：根据下式构造的是系统编码器；(2)(n－k)

m级移位寄存器构成的并行编码电路（Ⅰ型编码电路）这是系统码形式的一种编码电路，又称Ⅰ型编码电路；将上面的系统码形式展开后可以改写为式(6.4.5)。式(6.4.5)表明：在并入并出方式下，为了获得第l个子码的(n－k)个监督元，需要(n－k)个移位寄存器组，每一组移位寄存器的数目为m级；它们根据生成序列g(i,j)所确定的关系存储了第l个信息组相邻的前m个信息组。2.卷积码的编码[例5](3,2,2)码Ⅰ型编码电路解：生成序列为g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]根据式(6.4.5)，第l个子码的监督元为Cl(3)=ml(1)g0(1,3)+ml(2)g0(2,3)+ml－1(1)g1(1,3)+ml－1(2)g1(2,3)+ml－2(1)g2(1,3)+ml－2(2)g2(2,3)将生成序列诸元素带入后有Cl(3)=ml(1)+ml(2)+ml－1(2)+ml－2(1)(3,2,2)码的Ⅰ型编码电路如图6.4.7所示。图6.4.8是(n,k,m)系统码Ⅰ型编码电路。2.卷积码的编码(3)k

m级移位寄存器编码电路（Ⅱ型编码电路）将上面系统形式展开后可以另外改写为式(6.4.6)。式(6.4.6)表明：只需将第l时刻的k个信息元与前m个时刻的诸信息元按生成序列所确定的关系模2相加，就可以得到此时刻的(n－k)个监督元。Ⅱ型编码电路由k个移位寄存器组构成，每一组有m级移位寄存器。它们分别寄存了前m时刻进入编码器的第一个到第k个信息元。[例6](3,1,2)码，码的生成序列为g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]由式(6.4.6)，该码任一子码的监督元为Cl(2)=ml(1)g0(1,2)+ml－1(1)g1(1,2)+ml－2(1)g2(1,2)=ml(1)+ml－1(1)

Cl(3)=ml(1)g0(1,3)+ml－1(1)g1(1,3)+ml－2(1)g2(1,3)=ml(1)+ml－2(1)其编码电路如图6.4.9所示。[例7](3,2,2)码，已知码的生成序列为g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]由式(6.4.6)，该码任一子码的监督元为Cl(3)=ml(1)g0(1,3)+ml－1(1)g1(1,3)+ml－2(1)g2(1,3)+ml(2)g0(2,3)+ml－1(2)g1(2,3)+ml－2(2)g2(2,3)=ml(1)+ml－2(1)+ml(2)+ml－1(2)其编码电路如图6.4.10所示。图6.4.11所示的是(n,k,m)码的Ⅱ型编码电路。Cl(3)=ml(1)+ml－2(1)+ml(2)+ml－1(2)(4)结论

以上三种形式电路各有不同的特点。在一般的串行通信方式下，用串行编码电路比较方便，虽然它所需的电路级数较多；在并行通信时，若(n－k)<k，采用Ⅰ型编码电路较Ⅱ型更为简单；否则，应采用Ⅱ型编码电路。描述卷积码编译码的过程，可以用不同的描述方法：如矩阵法、码树法、状态图法、篱笆图法等。采用何种方法与卷积码的译码方法有很大关系。代数译码时：用矩阵法对译码原理的叙述和理解较方便。概率译码时：借助码树和篱笆图能更清晰地分析和了解译码过程和码的性能。(1)卷积码的生成矩阵(2)卷积码的监督矩阵卷积码的矩阵描述(1)卷积码的生成矩阵以(2,1,3)码为例说明它的生成矩阵是如何得到的g(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]其中：将上式表示成矩阵方程，则有：即C∞T=G∞TM∞T=(M∞G∞)T或者C∞=M∞G∞码的生成矩阵G∞：G∞称为(2,1,3)码的生成矩阵。当输入的信息序列是有头无尾的半无限序列时，生成矩阵也是半无限矩阵，G∞的下标就是这个含义，这时码序列C∞亦为半无限序列。由式(6.4.7)可以看出，生成矩阵G∞中，只要第一行G0G1G2G3确定以后，生成矩阵G∞也就确定了。基本生成矩阵g∞

：生成矩阵G∞的第一行为该码的基本生成矩阵。(2,1,3)码的基本生成矩阵g∞为：g∞=[G0G1G2G300…]g∞中的每一个元素完全由码生成序列g(i,j)诸元素所确定。编码器的输出码序列C∞可根据生成矩阵得到。(2,1,3)码：基本生成矩阵中的每个元素G0,G1,G2,G3都是(1×2)阶矩阵(k

n,k=1,n=2)，元素的数目共4个(m+1=N=4)。[例9](3,2,2)非系统卷积码。它的6个生成序列为：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[110]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[010]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[100]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[001]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[111]设信息序列

M=[m0(1)m0(2)m1(1)m1(2)m2(1)m2(2)m3(1)m3(2)…]由式(6.4.3)，编码器的输出C为：6.4.3卷积码的矩阵描述写成矩阵方程，可得到(3,2,2)码的生成矩阵和基本生成矩阵(n,k,m)码的基本生成矩阵和生成矩阵(1)卷积码译码的种类：卷积码的译码可分为代数译码和概率译码。(2)代数译码：从码的代数结构出发，以一个约束度的接收序列为单位，对该接收序列的信息码组进行译码。大数逻辑译码是代数译码的主要方法。代数译码中，用矩阵描述比较方便。(3)概率译码：从信道的统计特性出发，以远大于约束度的接收序列为单位，对信息码组进行最大似然的判决。维特比译码和序列译码是其最主要的方法。在维特比译码中，用篱笆图来描述码的译码更为方便。卷积码的译码(1)卷积码的状态定义：卷积码编码器要存储m段消息，这些消息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。有效存储单元M：M≤km状态向量σ(l)/σ：σ(l)=(σM(l),σM－1(l),…,σ2(l),σ1(l))二元(n,k,m)卷积码共有2M个不同的状态，记为新的状态σ(l+1)/σ’转移分支(σ(l),σ(l+1))/(σ,σ’)输入段U(l)/U输出段V(l)/V状态转移方程：σ’=φ(σ,U)输出方程：V=ψ(σ,U)卷积码的状态转移图与栅格描述[例1](2,1,2)码的状态向量为σ=(σ2σ1)，共有4种状态S0,S1,S2,S3，如图所示。g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]其状态变化表如表6.4.1所示。该码的状态转移方程和输出方程分别为

σ1’=Uσ2’=σ1

V1=U+σ1+σ2V2=U+σ2其状态转移图如图6.4.14和图5.4.15所示。[例2](3,2,1)码的状态向量为σ=(σ2σ1)，共有4种状态S0,S1,S2,S3，如图6.4.13所示。g(1,1)=[g0(1,1)g1(1,1)]=[11]g(1,2)=[g0(1,2)g1(1,2)]=[01]g(1,3)=[g0(1,3)g1(1,3)]=[11]g(2,1)=[g0(2,1)g1(2,1)]=[01]g(2,2)=[g0(2,2)g1(2,2)]=[10]g(2,3)=[g0(2,3)g1(2,3)]=[10]其状态为

S=(σ2σ1)S0=(00),S1=(01),S2=(10),S3=(11)

V=(V1V2V3)U=(U1U2)状态方程和输出方程为

σ1’=U1

σ2’=U2

V1=U1+σ1+σ2V2=U2+σ1V2=U1+U2+σ1(3)卷积码的栅格图(篱笆图)状态图不能反映出状态转移与时间的关系栅格图/篱笆图：将开放型的状态转移图按时间顺序级联形成一个栅格图。编码路径：状态序列σ在栅格图中形成的一条有向路径。当有向路径始于全“0”状态S0，又终于S0时，表明此时编码器又回到全“0”状态，这条始于S0又首次终于S0的路径是一个卷积码码字。红实线表示U=0时输入产生的转移分支；黄虚线表示U=1时输入产生的转移分支。维特比译码的基本原理Viterbi译码的特点维特比算法是最大似然的序列译码算法译码复杂度与信道质量无关运算量和存贮量都与码长呈线性关系运算量和存贮量都与状态数呈线性关系状态数随k及m呈指数关系(1)维特比译码的度量待编码的信息序列M：M=[M0,M1,…,ML－1]；编码器输入序列的总长度：k(L+m)；编码器输出的码序列C：C=[C0,C1,…,CL－1]，其中每个子码Ci含有n个码元；经离散无记忆信道(DMC)传输后，译码器接收的序列R：R=[R0,R1,…,RL－1]；对于DMC信道：码序列C的路径度量

M(R/C)：计算第l时刻到达状态i的最大似然路径的相似度logp(R/C)；子码Ci

度量M(Ri/Ci)：计算第l时刻接收子码Ri

相对于各码字的相似度logp(Ri/Ci)，也称为分支度量。(2)维特比译码和篱笆图在维特比译码中，用状态图和篱笆图描述码的译码比较方便。以(2,1,2)码为例说明

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]图6.4.20所示的是(2.1.2)码的篱笆图：它由结点和分支构成。共有8个结点（单元时刻），在图中的上方以0,1,2,…7标号，0结点表示第0个时刻。编码器的工作过程：在起始的第0个到第2个时刻内，编码器根据输入的信息元不同从S0状态向四个可能的状态之一行进；本例假定信息序列长为L=5个信息组，最后m个信息组是全0，所以在篱笆图上的最后两个时刻向S0状态返回；篱笆图上各连续分支组成了可能的路径，它们代表了各种可能的码序列；由于可能的输入信息序列有2kL=25=32个，可能的路径有32条；每个分支上的数字表示输出的子码。(3)码参数和篱笆图的关系对(n,k,m)码而言，编码器的可能状态数目为2km个，进入每个状态的分支数为2k个，从每个状态输出的分支数2k

个，若输入信息序列长为k(L+m)（后mk个码元全为0），则篱笆图上共有2kL条不同的路径，相应于编码器输出的2kL个码序列。(4)最大似然译码/最小距离译码译码器接收到R序列后，按最大似然法则力图寻找编码器在篱笆图上原来走过的路径，也就是寻找具有最大度量的路径；因此，译码器必须计算max[M(R/Cj)]，j=1,2,…,2Lk，对BSC信道，就是寻找与R有最小距离的路径，即计算和寻找min[d(R,Cj)]。译码的实现(续下页…….)：译码的实现：最大似然译码方法只是提供了一个译码准则，实现起来尚有一定困难。因为它是考虑了长度为(L+m)n的接收序列来译码的，这样的序列可能有2Lk条；若实际接收序列中，L=50，k=2，则可能的路径有2100条。译码器每接收一个序列R，就要计算1030个似然函数才能做出译码判决。若kL

再大一些，译码器按最大似然译码准则译码将是很困难的。(5)举例说明维特比译码工作原理维特比提出了一种算法：译码器不是在篱笆图上一次就计算和比较2Lk条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。维特比译码的基本思想：将接收序列R与篱笆图上的路径逐分支地比较，比较的长度一般取(5~6)mn，然后留下与R距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐次分支地延长并存储起来。幸存路径的数目等于状态数：2km

以(2,1,2)非系统码为例说明维特比译码的基本思想：设发送序列C为全0；接收序列R=[10,00,01,00,00,00,00,…]假设译码器的初始状态为全0；第0个时刻：接收序列的第0个分支R0=10进入译码器。从S0状态有两个分支，它们是00和11，R0与这两个分支比较，比较的结果和到达的状态如表6.4.2所示：每个状态/节点都有两个存储器：路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值(累加距离)。第一个时刻：进入译码器的接收码组R1=00和此时刻出发的四条分支比较，比较结果和达到状态如表6.4.3所示：从第一个时刻到第二个时刻：共有四条路径，到达S0,S1,S2和S3。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器存储了此时刻到达该状态的幸存路径累加值(累加距离)。从第二个时刻起：第二个接收码组R2=01进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组R2与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：经过比较后选择：部分路径

000000为到达S0

状态的幸存路径；部分路径000011为到达

S1状态的幸存路径；部分路径110101为到达

S2状态的幸存路径；部分路径001101为到达

S3

状态的幸存路径。按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个