第五章-卷积码码2

第五章卷积码5.1卷积码的基本概念5.2卷积码的矩阵描述与编码5.3卷积码的状态图与格图描述5.4卷积码的概率译码3/2/20231信道编码5.3卷积码的状态图与格图描述卷积码的状态图描述用编码器状态及其转移描述卷积码。[例]：(2,1,2)卷积码的子生成元为：

g(1,1)=111 g(1,2)=101

其编码器如图所示编码器一共有4个状态：00,10,01,11

分别记为：S0,S1,S2,S33/2/20232信道编码5.3卷积码的状态图与格图描述卷积码的状态图描述(2,1,2)卷积码的状态转移图为：一般地：(n0,k0,m)卷积码共有2mk0个状态每个状态有2k0个输入和2k0个输出3/2/20233信道编码5.3卷积码的状态图与格图描述卷积码的状态图描述卷积码的状态图只表示编码状态之间的转移关系，无法表示状态转移与时间节拍的关系。为了表示状态转移与时间节拍的关系，我们引入卷积码的格图(TrellisDiagram)表示。3/2/20234信道编码5.3卷积码的状态图与格图描述卷积码的格图描述[例]：(2,1,2)卷积码，将状态转移图按时间节拍绽开，如图所示。3/2/20235信道编码5.3卷积码的状态图与格图描述卷积码的格图描述卷积码的格图也称为篱笆图。从初始状态动身，格图上的每一条路经都对应着一个输入信息序列所对应的编码序列。给定信息序列，可在格图上找到一条路经，进而得到所对应的编码序列。反过来，给定编码序列，也可在格图上找到一条路经，进而得到所对应的信息序列。3/2/20236信道编码5.3卷积码的状态图与格图描述卷积码的格图描述例如：(2,1,2)卷积码，m=101100…3/2/20237信道编码5.3卷积码的状态图与格图描述卷积码的格图描述例如：(2,1,2)码，C=110101001011…3/2/20238信道编码5.3卷积码的状态图与格图描述卷积码的格图描述对于(n0,k0,m)卷积码： 格图一共有2mk0个状态 每个状态有2k0个输入分支和2k0个输出分支 格图从第m个节拍以后起先重复 长为L的格图一共有2Lk0条路经 每条路经对应一个长为L段的编码序列3/2/20239信道编码5.3卷积码的状态图与格图描述卷积码的格图描述由于(n0,k0,m)卷积码的格图从第m个节拍以后起先重复，因此，通常状况下只需探讨一个节拍的格图即可；格图是卷积码维特比译码的基本依据。利用格图也可以构造卷积码，是探讨卷积码的重要工具。3/2/202310信道编码5.3卷积码的状态图与格图描述课下作业：1、已知一卷积码的子生成元为：

g(1,1)=110，g(1,2)=101

给出该码节拍数为6的格图。 设m=101100…，结合格图给出码序列3/2/202311信道编码第五章卷积码5.1卷积码的基本概念5.2卷积码的矩阵描述与编码5.3卷积码的状态图与格图描述5.4卷积码的概率译码3/2/202312信道编码5.4卷积码的概率译码概率译码概述Vitebi译码的基本原理3/2/202313信道编码5.4卷积码的概率译码概率译码概述概率译码概述 概率译码不仅基于码的代数结构，还充分利用了信道的统计特性，因此，通常能获得最佳或准最佳的译码性能（最大似然译码性能）。 概率译码由于利用足够长序列的统计特性，其性能不再以纠错实力来衡量，而接受统计参数--编码增益来衡量。3/2/202314信道编码5.4卷积码的概率译码概率译码概述概率译码最早始于1961年提出的序列译码，1963年费诺（Fano）改进后得以实际应用，称为Fano算法。1967年维特比（Vitebi）提出一种卷积码译码方法，称为维特比算法。1973年Forney证明维特比译码是最大似然译码。维特比算法具有效率较高、速度快、实现简洁等特点，使得维特比算法得到了极为广泛的应用。3/2/202315信道编码5.4卷积码的概率译码概率译码概述维特比译码基于卷积码的格图实现，其基本思想是在格图上找寻一条最大似然路径，该条路经所对应的信息序列即为译码输出。对于(n0,k0,m)卷积码，从某一个状态动身，长为L的格图上一共有2Lk0条不同的路径，可见当L足够大时找寻最大似然路径是极其困难的。维特比算法解决了这一问题，可利用较为简洁的方法找到足够长的最大似然路径。3/2/202316信道编码5.4卷积码的概率译码Vitebi译码的基本原理最大似然译码： P(C|R)=Max[P(Cj|R)]⇔Max[P(R|Cj)]卷积码的最大似然译码与分组码原理相同，实现上的区分在于：分组码的最大似然译码是计算单个码字的相像度，而卷积码是计算整个码序列的相像度。在BSC上，最大似然译码和最小汉明距离译码是等价的。3/2/202317信道编码5.4卷积码的概率译码Vitebi译码的基本原理维特比算法的中心思想是：将求解格图上整条路经的似然度转化为利用分支似然度逐步求解路径似然度。大大简化了译码的困难性。思路：在格图上，逐节拍（逐分支）、逐状态比较候选序列的似然度，在每个节拍上发觉和解除不行能路径，从而将候选路径保持在与状态数相同的数量上。将困难度系数从2Lk0降为Lx2mk0(通常L>>m)。3/2/202318信道编码5.4卷积码的概率译码Vitebi译码的基本原理结尾卷积码序列： 设一个(n0,k0,m)编码器输入是一个k0L位信息和后面跟着k0m位全0的序列 m=(m0,m1,m2,…,mL-1,0,0,…,0) 其中，最终m段全0序列是使编码器复原到初始状态所必需的。由编码器输出的码序列C=(C0,C1,…,Cm+L-1)是一个长为n0(L+m)的二元序列。 由于编码器输出的码序列C确定复原到初始全0状态，因此称这种码序列为结尾卷积码序列。 由于信息序列共有2k0L个，因此对应的码序列也有2k0L个，即格图上共有2k0L条路径。3/2/202319信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：

g(1,1)=111，g(1,2)=101

该码的格图为：

m=101100…对应的码序列为：

C=111000010111…

设：R=011001010111…3/2/202320信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001130011323/2/202321信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131121130023/2/202322信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120021040133/2/202323信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130121053/2/202324信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031143/2/202325信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031130043/2/202326信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031131040123/2/202327信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031132010121043/2/202328信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031132010120041133/2/202329信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123105012113/2/202330信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201005112113/2/202331信道编码5.4卷积码的概率译码Vitebi译码的基本原理[例]：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201112113/2/202332信道编码5.4卷积码的概率译码Vitebi译码算法步骤：结合例子，说明过程：1.从时间单位j＝m(2)起先，计算进入每一状态的单个路径的部重量度，存储每一状态下的路径及其部重量度。2.j增加1，分别计算进入每一状态的全部分枝量度，并分别将其与前一单位时间有关的部重量度相加得到新的部重量度；对每一状态，比较进入它的全部路径的部重量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除其它路径。【加、比、选】3.若j<6，重复以上步骤，否则停止。3/2/202333信道编码5.4卷积码的概率译码Vitebi译码的基本原理留意：从时间单位2(m)到4(L)中，每个状态都有一个幸存路径。时间单位4(L)之后，幸存路径削减，最终在时间单位2+4时，只有一个状态，即全0状态。回溯：由估值序列依据网格图得出信息序列的过程。经回溯，得到信息序列m’＝（101100），去掉补的m＝2个0得译码信息序列m＝（1011）。以上过程是针对结尾卷积码序列的译码操作。3/2/202334信道编码5.4卷积码的概率译码Vitebi最大似然路径算法步骤： 1.从时间单位j＝m起先，计算进入每一状态的单个路径的部重量度，存储每一状态下的路径及其部重量度。2.j增加1，分别计算进入每一状态的全部分枝量度，并分别将其与前一单位时间有关的部重量度相加得到新的部重量度，然后对每一状态比较进入它的全部路径的部重量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除其它路径。【加、比、选】3.若j<L＋m，重复以上步骤，否则停止。3/2/20233