第五章-卷积码码2.ppt

5/11/2020,信道编码,1,第五章卷积码,5.1卷积码的基本概念5.2卷积码的矩阵描述与编码5.3卷积码的状态图与格图描述5.4卷积码的概率译码,5/11/2020,信道编码,2,5.3卷积码的状态图与格图描述,卷积码的状态图描述用编码器状态及其转移描述卷积码。例：(2,1,2)卷积码的子生成元为：g(1,1)=111g(1,2)=101其编码器如图所示编码器一共有4个状态：00,10,01,11分别记为：S0,S1,S2,S3,5/11/2020,信道编码,3,5.3卷积码的状态图与格图描述,卷积码的状态图描述(2,1,2)卷积码的状态转移图为：,一般地：(n0,k0,m)卷积码共有2mk0个状态每个状态有2k0个输入和2k0个输出,5/11/2020,信道编码,4,5.3卷积码的状态图与格图描述,卷积码的状态图描述卷积码的状态图只表示编码状态之间的转移关系，无法表示状态转移与时间节拍的关系。为了表示状态转移与时间节拍的关系，我们引入卷积码的格图(TrellisDiagram)表示。,5/11/2020,信道编码,5,5.3卷积码的状态图与格图描述,卷积码的格图描述例：(2,1,2)卷积码，将状态转移图按时间节拍展开，如图所示。,5/11/2020,信道编码,6,5.3卷积码的状态图与格图描述,卷积码的格图描述卷积码的格图也称为篱笆图。从初始状态出发，格图上的每一条路经都对应着一个输入信息序列所对应的编码序列。给定信息序列，可在格图上找到一条路经，进而得到所对应的编码序列。反过来，给定编码序列，也可在格图上找到一条路经，进而得到所对应的信息序列。,5/11/2020,信道编码,7,5.3卷积码的状态图与格图描述,卷积码的格图描述例如：(2,1,2)卷积码，m=101100,5/11/2020,信道编码,8,5.3卷积码的状态图与格图描述,卷积码的格图描述例如：(2,1,2)码，C=110101001011,5/11/2020,信道编码,9,5.3卷积码的状态图与格图描述,卷积码的格图描述对于(n0,k0,m)卷积码：格图一共有2mk0个状态每个状态有2k0个输入分支和2k0个输出分支格图从第m个节拍以后开始重复长为L的格图一共有2Lk0条路经每条路经对应一个长为L段的编码序列,5/11/2020,信道编码,10,5.3卷积码的状态图与格图描述,卷积码的格图描述由于(n0,k0,m)卷积码的格图从第m个节拍以后开始重复，因此，通常情况下只需研究一个节拍的格图即可；格图是卷积码维特比译码的基本依据。利用格图也可以构造卷积码，是研究卷积码的重要工具。,5/11/2020,信道编码,11,5.3卷积码的状态图与格图描述,课下作业：1、已知一卷积码的子生成元为：g(1,1)=110，g(1,2)=101给出该码节拍数为6的格图。设m=101100，结合格图给出码序列,5/11/2020,信道编码,12,第五章卷积码,5.1卷积码的基本概念5.2卷积码的矩阵描述与编码5.3卷积码的状态图与格图描述5.4卷积码的概率译码,5/11/2020,信道编码,13,5.4卷积码的概率译码,概率译码概述Vitebi译码的基本原理,5/11/2020,信道编码,14,5.4卷积码的概率译码,概率译码概述概率译码概述概率译码不仅基于码的代数结构，还充分利用了信道的统计特性，因此，通常能获得最佳或准最佳的译码性能（最大似然译码性能）。概率译码由于利用足够长序列的统计特性，其性能不再以纠错能力来衡量，而采用统计参数-编码增益来衡量。,5/11/2020,信道编码,15,5.4卷积码的概率译码,概率译码概述概率译码最早始于1961年提出的序列译码，1963年费诺（Fano）改进后得以实际应用，称为Fano算法。1967年维特比（Vitebi）提出一种卷积码译码方法，称为维特比算法。1973年Forney证明维特比译码是最大似然译码。维特比算法具有效率较高、速度快、实现简单等特点，使得维特比算法得到了极为广泛的应用。,5/11/2020,信道编码,16,5.4卷积码的概率译码,概率译码概述维特比译码基于卷积码的格图实现，其基本思想是在格图上寻找一条最大似然路径，该条路经所对应的信息序列即为译码输出。对于(n0,k0,m)卷积码，从某一个状态出发，长为L的格图上一共有2Lk0条不同的路径，可见当L足够大时寻找最大似然路径是极其困难的。维特比算法解决了这一问题，可利用较为简单的方法找到足够长的最大似然路径。,5/11/2020,信道编码,17,5.4卷积码的概率译码,Vitebi译码的基本原理最大似然译码：P(C|R)=MaxP(Cj|R)MaxP(R|Cj)卷积码的最大似然译码与分组码原理相同，实现上的区别在于：分组码的最大似然译码是计算单个码字的相似度，而卷积码是计算整个码序列的相似度。在BSC上，最大似然译码和最小汉明距离译码是等价的。,5/11/2020,信道编码,18,5.4卷积码的概率译码,Vitebi译码的基本原理维特比算法的中心思想是：将求解格图上整条路经的似然度转化为利用分支似然度逐步求解路径似然度。大大简化了译码的复杂性。思路：在格图上，逐节拍（逐分支）、逐状态比较候选序列的似然度，在每个节拍上发现和排除不可能路径，从而将候选路径保持在与状态数相同的数量上。将复杂度系数从2Lk0降为Lx2mk0(通常Lm)。,5/11/2020,信道编码,19,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条路径。,5/11/2020,信道编码,20,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：g(1,1)=111，g(1,2)=101该码的格图为：m=101100对应的码序列为：C=111000010111设：R=011001010111,5/11/2020,信道编码,21,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,00,11,3,2,5/11/2020,信道编码,22,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,11,3,00,2,5/11/2020,信道编码,23,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,10,4,01,3,5/11/2020,信道编码,24,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,10,5,5/11/2020,信道编码,25,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,4,5/11/2020,信道编码,26,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,00,4,5/11/2020,信道编码,27,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,10,4,01,2,5/11/2020,信道编码,28,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,2,01,01,2,10,4,5/11/2020,信道编码,29,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,2,01,01,2,00,4,11,3,5/11/2020,信道编码,30,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,2,01,01,2,3,10,5,01,2,11,5/11/2020,信道编码,31,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,2,01,01,2,3,2,01,00,5,11,2,11,5/11/2020,信道编码,32,5.4卷积码的概率译码,Vitebi译码的基本原理例：(2,1,2)卷积码：,S000,S110,S201,S311,01,10,01,01,01,11,R=,00,11,1,1,00,2,11,2,10,01,1,3,11,2,00,2,01,3,01,2,00,3,11,3,2,01,01,2,3,2,01,11,2,11,5/11/2020,信道编码,33,5.4卷积码的概率译码,Vitebi译码算法步骤：结合例子，说明过程：1.从时间单位jm(2)开始，计算进入每一状态的单个路径的部分量度，存储每一状态下的路径及其部分量度。2.j增加1，分别计算进入每一状态的所有分枝量度，并分别将其与前一单位时间有关的部分量度相加得到新的部分量度；对每一状态，比较进入它的所有路径的部分量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除其它路径。【加、比、选】3.若j6，重复以上步骤，否则停止。,5/11/2020,信道编码,34,5.4卷积码的概率译码,Vitebi译码的基本原理注意：从时间单位2(m)到4(L)中，每个状态都有一个幸存路径。时间单位4(L)之后，幸存路径减少，最后在时间单位2+4时，只有一个状态，即全0状态。回溯：由估值序列根据网格图得出信息序列的过程。经回溯，得到信息序列m（101100），去掉补的m2个0得译码信息序列m（1011）。以上过程是针对结尾卷积码序列的译码操作。,5/11/2020,信道编码,35,5.4卷积码的概率译码,Vitebi最大似然路径算法步骤：1.从时间单位jm开始，计算进入每一状态的单个路径的部分量度，存储每一状态下的路径及其部分量度。2.j增加1，分别计算进入每一状态的所有分枝量度，并分别将其与前一单位时间有关的部分量度相加得到新的部分量度，然后对每一状态比较进入它的所有路径的部分量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除其它路径。【加、比、选】3.若jLm，重复以上步骤，否则停止。,5/11/2020,信道编码,36,5.4卷积码的概率译码,软判决Vitebi译码软判决译码：译码输入为多电平量化信号。硬判决译码用于BSC信道。软判决译码用于一般DMC信道。软判决维特比译码与硬判决原理相同，但路径度量不同。软判决维特比译码采用软距离作为分支和路径度量。,5/11/2020,信道编码,37,5.4卷积码的概率译码,软判决Vitebi译码软距离：如采用8电平均匀量化，用07表示量化值，最小电平为0、最大电平为7。比特0与电平0的软距离为0、与电平7的软距离为7；比特1与电平0的软距离为7、与电平7的软距离为0。,5/11/2020,信道编码,38,5.4卷积