信息论与编码-第17讲-信道编码-卷积码

第1页2024/4/14第10章卷积码10.1卷积码的基本概念10.2卷积码的编码10.3卷积码的译码10.4卷积码的图描述10.5维特比译码的基本原理10.6软判决维特比译码10.7维特比译码的应用ElectronicsEngineeringDepartment,XXXXXxxXxxx第2页2024/4/1410.1卷积码的基本概念

卷积码（连环码）首先由麻省理工学院于1955年提出。卷积码与分组码的不同之处：在任意给定单元时刻，编码器输出的

n

个码元中，每一个码元不仅和此时刻输入的k

个信息元有关，还与前连续m

个时刻输入的信息元有关。卷积码常用(n,k,m)表示。

n—子码，k—信息位，m—编码存储在同样的编码效率R下，卷积码的性能优于分组码，至少不低于分组码。第3页2024/4/1410.1卷积码的基本概念

卷积码的译码方法

代数译码：门限译码。译码延时是固定的。概率译码：序列译码：译码延时是随机的。

维特比译码：译码延时是固定的。第4页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度(2)系统码形式的卷积码第5页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码第6页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码待编码的信息序列m：在对m

进行编码之前，先将它每k个码元分成一组，在每单元时刻内，k个码元串行输入到编码器；移位寄存器组：

(m+1)个，每个移位寄存器组内有k级寄存器；常数乘法器g(i,j)：i=1,2,…,k；j=1,2,…,n，共有(m+1)•n

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

个系数才能描述；第7页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码开关K在每一节拍中移动n次，每一节拍输入k个信息元而输出n个码元。信息序列m=[m0(1)m1(1)m2(1)…]；

ml(1)表示第l个时刻的第k=1个信息元；第8页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-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]

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和。第9页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码卷积码的生成序列

生成序列：给定g(i,j)后，就可以生成编码器输出的码元。称g(1,1)和g(1,2)为(2,1,3)卷积码的生成序列。第l个时刻的编码器输出为：第10页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码卷积码的生成序列

卷积码名称的由来：任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出。第11页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码设m

=[m0(1)m1(1)m2(1)m3(1)]=[1011]，则编码器两个输出端的序列分别是：

子码：在任一单元时刻，送入编码器一个信息元（k=1），编码器输出由2个(n=2)码元组成的一个码组，称之为子码。第12页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-1]：(2,1,3)码每个子码中的码元不仅与此时此刻的信息元有关，而且还与前m个(m=3)时刻的信息元有关。

编码存储：m（本例

m=3）

约束度：N=m+1，编码过程中相互约束的子码数。（本例N=4）

编码约束长度：N

n，编码过程中相互约束的码元数。（本例N

n=8）

非系统码：在码序列C

中的每个子码不是系统码字结构。（本例是非系统码）第13页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-2]：(3,2,1)码

n=3,k=2,m=1；它的任一子码有3个码元。每个码元由此时此刻的2个信息元和前一个时刻进入编码器的2个信息元模2运算和求出。这些信息元参加模2运算的规则由[n

k]=3×2=6

个生成序列{[n

k

(m+1)]=3×2×2=12个系数}所确定，每个生成序列含有2个元素。第14页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-2]：(3,2,1)码这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](10-3)第15页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-2]：(3,2,1)码若待编码的信息序列：m=[m0(1)m0(2)m1(1)m1(2)…

ml(1)ml(2)…]

则码序列C中的任一子码为：第16页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-2]：(3,2,1)码

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]第17页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例10-2]：(3,2,1)码每个时刻单元输入编码器k=2个信息元，它们与前一个时刻进入编码器的2个信息元按式(10-4)所确定的卷积关系进行运算后，在输出端1、2、3分别得到该时刻子码中的3个码元。编码器由N=2个移位寄存器组和模2加法器构成，每个移位寄存器组含有k=2级移位寄存器，每级移位寄存器的输出按式(10-3)的规则引出后进行模2加的运算。本例也是非系统码形式的卷积码。第18页2024/4/1410.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度推论：(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)…]

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

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

k)

个生成序列是固定的，即：第20页2024/4/1410.1卷积码的基本概念(2)系统码形式的卷积码只有k

(n－k)个生成序列需要给定，以便确定每个子码中(n－k)个监督元。第21页2024/4/1410.1卷积码的基本概念(2)系统码形式的卷积码任一子码由下式计算：上式表明：在约束长度N内，每个子码中的(n－k)个监督元与信息元的卷积关系。第22页2024/4/1410.1卷积码的基本概念(2)系统码形式的卷积码[例10-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]第23页2024/4/1410.1卷积码的基本概念(2)系统码形式的卷积码[例10-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]

任一时刻子码为：第24页2024/4/14(2)系统码形式的卷积码[例10-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]10.1卷积码的基本概念第25页2024/4/14(2)系统码形式的卷积码[例10-4]：(3,2,2)系统卷积码该码的任一子码Cl中前两位与ml(1)、ml(2)相同，后一位的监督元由式(10-6)确定，即：10.1卷积码的基本概念第26页2024/4/14(2)系统码形式的卷积码[例10.1.4]：(3,2,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]10.1卷积码的基本概念第27页2024/4/14(1)串行输入、串行输出的编码电路(2)(n－k)

m级移位寄存器构成的并行编码电路（Ⅰ型编码电路）(3)k

m级移位寄存器编码电路（Ⅱ型编码电路）(4)结论10.2卷积码的编码第28页2024/4/14(1)串行输入、串行输出的编码电路非系统码编码器：根据式(10-5)构造的是非系统编码器。图10-5是(n,k,m)非系统卷积码串行编码电路。10.2卷积码的编码第29页2024/4/14(1)串行输入、串行输出的编码电路10.2卷积码的编码第30页2024/4/14(1)串行输入、串行输出的编码电路系统码编码器：根据式(10-6)构造的是系统编码器；图10-6是(n,k,m)系统卷积码串行编码电路。10.2卷积码的编码第31页2024/4/14(1)串行输入、串行输出的编码电路10.2卷积码的编码第32页2024/4/14(4)结论：以上三种形式电路各有不同的特点在一般的串行通信方式下，用串行编码电路比较方便，虽然它所需的电路级数较多；在并行通信时，若(n－k)<k，采用Ⅰ型编码电路较Ⅱ型更为简单；否则，应采用Ⅱ型编码电路。10.2卷积码的编码第33页2024/4/1410.3卷积码的译码(1)卷积码译码的种类：卷积码的译码可分为代数译码和概率译码。(2)代数译码：从码的代数结构出发，以一个约束度的接收序列为单位，对该接收序列的信息码组进行译码。大数逻辑译码是代数译码的主要方法。代数译码中，用矩阵描述比较方便。(3)概率译码：从信道的统计特性出发，以远大于约束度的接收序列为单位，对信息码组进行最大似然的判决。维特比译码和序列译码是其最主要的方法。在维特比译码中，用网格图来描述码的译码更为方便。第34页2024/4/1410.4卷积码的图描述(1)卷积码的状态(2)卷积码的状态转移图(3)卷积码的网格图第35页2024/4/1410.4卷积码的图描述(1)卷积码的状态定义：卷积码编码器要存储m段消息，这些消息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。第36页2024/4/1410.4卷积码的图描述(1)卷积码的状态[例]：(2,1,2)码的状态向量为D=(D2,D1)，共有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]第37页2024/4/1410.4卷积码的图描述(1)卷积码的状态[例]：其状态转移图如图

10-14和图10-17所示。第38页2024/4/1410.4卷积码的图描述(1)卷积码的状态[例]：其状态转移图如图

10-14和图10-17所示。第39页2024/4/1410.4卷积码的图描述(2)卷积码的状态转移图闭合型的状转移态图：直接地描述了卷积编码器在任一时刻的工作状况；开放型的状态转移图：更适合去描述一个特定输入序列的编码过程。第40页2024/4/1410.4卷积码的图描述(2)卷积码的状态转移图[例10-13]：(3,2,1)码的状态向量为D=(D2,

D1)，共有4种状态S0,S1,S2,S3，如图10-15所示。

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]第41页2024/4/1410.4卷积码的图描述(2)卷积码的状态转移图[例10-13]：第42页2024/4/1410.4卷积码的图描述(2)卷积码的状态转移图[例10-13]：第43页2024/4/1410.4卷积码的图描述(3)卷积码的网格图状态图不能反映出状态转移与时间的关系网格图：将开放型的状态转移图按时间顺序级联形成一个网格图。编码路径：状态序列D在网格图中形成的一条有向路径。当有向路径始于全“0”状态S0，又终于S0时，表明此时编码器又回到全“0”状态，这条始于S0又首次终于S0的路径是一个卷积码码字。第44页2024/4/1410.4卷积码的图描述(3)卷积码的网格图红实线表示m=0时输入产生的转移分支；兰虚线表示m=1时输入产生的转移分支。第45页2024/4/1410.4卷积码的图描述(3)卷积码的网格图第46页2024/4/1410.5维特比译码的基本原理(1)维特比译码的度量(2)维特比译码和网格图(3)最大似然译码／最小距离译码(4)举例说明维特比译码工作原理(5)总结维特比算法的步骤第47页2024/4/1410.5维特比译码的基本原理(1)维特比译码的度量待编码的信息序列m：m=[m0,m1,…,mL－1]；编码器输入序列的总长度：k(L+m)；编码器输出的码序列C：C=[C0,C1,…,CL+m－1]，其中每个子码Ci含有n个码元；经离散无记忆信道（DMC）传输后，译码器接收的序列R：R=[R0,R1,…,RL+m－1]；第48页2024/4/1410.5维特比译码的基本原理(1)维特比译码的度量对于DMC信道：

码序列C的路径度量

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

子码Ci的度量（分支度量）M(Ri/Ci)

：计算第l时刻接收子码Ri相对于各子码的相似度—logp(Ri/Ci)。第49页2024/4/1410.5维特比译码的基本原理(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]

图10-20是(2,1,2)码的网格图：它由结点和分支构成。共有8个结点（单元时刻），在图中的上方以0,1,2,…,7标号，0结点表示第0个时刻。第50页2024/4/1410.5维特比译码的基本原理(2)维特比译码和网格图编码器的工作过程：第51页2024/4/1410.5维特比译码的基本原理(2)维特比译码和网格图

编码器的工作过程：在起始的第0个到第2个时刻内，编码器根据输入的信息元不同从S0状态向四个可能的状态之一行进；本例假定信息序列长为L=5个信息组，最后m个信息组是全0，所以在网格图上的最后两个时刻向S0状态返回；网格图上各连续分支组成了可能的路径，它们代表了各种可能的码序列；

由于可能的输入信息序列有2kL=25=32个，可能的路径有32条；每个分支上的数字表示输出的子码。第52页2024/4/1410.5维特比译码的基本原理(3)最大似然译码/最小距离译码译码器接收到R

序列后，按最大似然法则力图寻找编码器在网格图上原来走过的路径，也就是寻找具有最大度量的路径；因此，译码器必须计算max[M(R/Cj)]，j=1,2,…,2kL，对BSC信道，就是寻找与R

有最小距离的路径，即计算和寻找min[d(R,Cj)]。第53页2024/4/1410.5维特比译码的基本原理(3)最大似然译码/最小距离译码译码的实现：最大似然译码方法只是提供了一个译码准则，实现起来尚有一定困难。因为它是考虑了长度为(L+m)n的接收序列来译码的，这样的序列可能有2kL条；若实际接收序列中，L=50，k=2，则可能的路径有2100条。译码器每接收一个序列R，就要计算1030个似然函数才能做出译码判决。若kL再大一些，译码器按最大似然译码准则译码将是很困难的。第54页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理维特比提出了一种算法：译码器不是在网格图上一次就计算和比较2kL条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。维特比译码的基本思想：将接收序列R

与网格图上的路径逐分支地比较，比较的长度一般取(5～6)mn，然后留下与R

距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。幸存路径的数目：等于状态数

2km第55页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理以(2,1,2)非系统码为例说明维特比译码的基本思想：设发送序列为全零序列。维特比译码的一次运算计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。网格图中共有2km个状态，因此，维特比译码的计算量与编码存储m成指数关系变化，所以采用维特比算法译码的卷积码，其m不能选的太大。第56页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理累积路径值累积路径值累积路径值第57页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第58页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第59页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第60页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第61页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第62页2024/4/149.6维特比译码的基本原理(4)举例说明维特比译码工作原理第63页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第64页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理第65页2024/4/1410.5维特比译码的基本原理(4)举例说明维特比译码工作原理对本例，按上述算法进行到第11个分支后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为(