1、3/27/2022信道编码信道编码1第五章 卷积码5.1 卷积码的基本概念卷积码的基本概念5.2 卷积码的矩阵描述与编码卷积码的矩阵描述与编码5.3 卷积码的状态图与格图描述卷积码的状态图与格图描述5.4 卷积码的概率译码卷积码的概率译码3/27/2022信道编码信道编码25.3 卷积码的状态图与格图描述p卷积码的状态图描述卷积码的状态图描述用编码器状态及其转移描述卷积码。例：(2,1,2)卷积码的子生成元为： g(1,1)=111 g(1,2)=101其编码器如图所示 编码器一共有4个状态：00,10,01,11 分别记为：S0,S1,S2,S3DDmCc(1)c(2)3/27/2022信道
2、编码信道编码35.3 卷积码的状态图与格图描述p卷积码的状态图描述卷积码的状态图描述(2,1,2)卷积码的状态转移图为：S000S110S201S3110/001/100/111/111/010/011/000/10n一般地：(n0,k0,m)卷积码共有2mk0个状态n每个状态有2k0个输入和2k0个输出DDmCc(1)c(2)3/27/2022信道编码信道编码45.3 卷积码的状态图与格图描述p卷积码的状态图描述卷积码的状态图描述n卷积码的状态图只表示编码状态之间的转移关系，无法表示状态转移与时间节拍的关系。n为了表示状态转移与时间节拍的关系，我们引入卷积码的格图(Trellis Diagr
3、am)表示。3/27/2022信道编码信道编码55.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述例：(2,1,2)卷积码，将状态转移图按时间节拍展开，如图所示。S000S110S201S31101234500000000001010101111111111101010010101011000000011111101010160010110110001101S000S110S201S3110/001/100/111/111/010/011/000/103/27/2022信道编码信道编码65.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述n卷积码的格图也称为篱笆图
4、。n从初始状态出发，格图上的每一条路经都对应着一个输入信息序列所对应的编码序列。n给定信息序列，可在格图上找到一条路经，进而得到所对应的编码序列。反过来，给定编码序列，也可在格图上找到一条路经，进而得到所对应的信息序列。3/27/2022信道编码信道编码75.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述例如：(2,1,2)卷积码，m=101100S000S110S201S311012345000000000010101011111111111010100101010110000000111111010101600101101100011013/27/2022信道编码信道编码8
5、5.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述例如：(2,1,2)码，C=11 01 01 00 10 11 S000S110S201S311012345000000000010101011111111111010100101010110000000111111010101600101101100011013/27/2022信道编码信道编码95.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述对于(n0,k0,m)卷积码：n 格图一共有2mk0个状态n 每个状态有2k0个输入分支和2k0个输出分支n 格图从第m个节拍以后开始重复n 长为L的格图一共有2Lk0条
6、路经n 每条路经对应一个长为L段的编码序列3/27/2022信道编码信道编码105.3 卷积码的状态图与格图描述p卷积码的格图描述卷积码的格图描述n由于(n0,k0,m)卷积码的格图从第m个节拍以后开始重复，因此，通常情况下只需研究一个节拍的格图即可；n格图是卷积码维特比译码的基本依据。利用格图也可以构造卷积码，是研究卷积码的重要工具。3/27/2022信道编码信道编码115.3 卷积码的状态图与格图描述课下作业：课下作业：1、已知一卷积码的子生成元为：、已知一卷积码的子生成元为： g(1,1)=110，g(1,2)=101 给出该码节拍数为给出该码节拍数为6的格图。的格图。 设设m=1011
7、00，结合格图给出码序列，结合格图给出码序列3/27/2022信道编码信道编码12第五章 卷积码5.1 卷积码的基本概念卷积码的基本概念5.2 卷积码的矩阵描述与编码卷积码的矩阵描述与编码5.3 卷积码的状态图与格图描述卷积码的状态图与格图描述5.4 卷积码的概率译码卷积码的概率译码3/27/2022信道编码信道编码135.4 卷积码的概率译码p概率译码概述概率译码概述pVitebi译码的基本原理译码的基本原理3/27/2022信道编码信道编码145.4 卷积码的概率译码p概率译码概述概率译码概述n概率译码概述概率译码不仅基于码的代数结构，还充分利用了信道的统计特性，因此，通常能获得最佳或准最
8、佳的译码性能（最大似然译码性能）。概率译码由于利用足够长序列的统计特性，其性能不再以纠错能力来衡量，而采用统计参数-编码增益来衡量。3/27/2022信道编码信道编码155.4 卷积码的概率译码p概率译码概述概率译码概述n概率译码最早始于1961年提出的序列译码，1963年费诺（Fano）改进后得以实际应用，称为Fano算法。n1967年维特比（Vitebi）提出一种卷积码译码方法，称为维特比算法。1973年Forney证明维特比译码是最大似然译码。n维特比算法具有效率较高、速度快、实现简单等特点，使得维特比算法得到了极为广泛的应用。3/27/2022信道编码信道编码165.4 卷积码的概率译
9、码p概率译码概述概率译码概述n维特比译码基于卷积码的格图实现，其基本思想是在格图上寻找一条最大似然路径，该条路经所对应的信息序列即为译码输出。n对于(n0,k0,m)卷积码，从某一个状态出发，长为L的格图上一共有2Lk0条不同的路径，可见当L足够大时寻找最大似然路径是极其困难的。n维特比算法解决了这一问题，可利用较为简单的方法找到足够长的最大似然路径。3/27/2022信道编码信道编码175.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理n最大似然译码：P(C|R)=MaxP(Cj | R) MaxP(R | Cj)n卷积码的最大似然译码与分组码原理相同，实现上的区别在于：分组
10、码的最大似然译码是计算单个码字的相似度，而卷积码是计算整个码序列的相似度。n在BSC上，最大似然译码和最小汉明距离译码是等价的。3/27/2022信道编码信道编码185.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理n维特比算法的中心思想是：将求解格图上整条路经的似然度转化为利用分支似然度逐步求解路径似然度。大大简化了译码的复杂性。n思路：在格图上，逐节拍（逐分支）、逐状态比较候选序列的似然度，在每个节拍上发现和排除不可能路径，从而将候选路径保持在与状态数相同的数量上。将复杂度系数从2Lk0降为Lx2mk0 (通常Lm)。3/27/2022信道编码信道编码195.4 卷积码的概
11、率译码p VitebiVitebi译码的基本原理译码的基本原理n结尾卷积码序列：设一个(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/27/2022信道编码信道编码205.4 卷积码的概率译码pV
12、itebi译码的基本原理译码的基本原理例：(2,1,2)卷积码： g(1,1)=111，g(1,2)=101该码的格图为： m=101100 对应的码序列为： C=11 10 00 01 01 11 设：R=01 10 01 01 01 11 0010110110001101S000S110S201S3113/27/2022信道编码信道编码215.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：S000S110S201S311011001010111R=0011110021121001130011320010110110001101S000S110S20
13、1S3113/27/2022信道编码信道编码225.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=0011110021121001131121130023/27/2022信道编码信道编码235.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=00111100211210
14、011311200210401 33/27/2022信道编码信道编码245.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=00111100211210011311200201301210 53/27/2022信道编码信道编码255.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010
15、111R=00111100211210011311200201301200 31143/27/2022信道编码信道编码265.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=0011110021121001131120020130120031130043/27/2022信道编码信道编码275.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S20
16、1S311S000S110S201S311011001010111R=0011110021121001131120020130120031131040123/27/2022信道编码信道编码285.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=00111100211210011311200201301200311320101210 43/27/2022信道编码信道编码295.4 卷积码的概率译码pVitebi译码的基本原理译码的基本
17、原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=00111100211210011311200201301200311320101200 41133/27/2022信道编码信道编码305.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=00111100211210011311200201301200311320101231050
18、12113/27/2022信道编码信道编码315.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S311011001010111R=001111002112100113112002013012003113201012320100 5112113/27/2022信道编码信道编码325.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理例：(2,1,2)卷积码：0010110110001101S000S110S201S311S000S110S201S3110
19、11001010111R=0011110021121001131120020130120031132010123201112113/27/2022信道编码信道编码335.4 卷积码的概率译码pVitebi译码算法步骤：译码算法步骤：结合例子，说明过程：结合例子，说明过程：1. 1. 从时间单位从时间单位j jm (2)m (2)开始，计算进入每一状态的单个路开始，计算进入每一状态的单个路径的部分量度，存储每一状态下的路径及其部分量度。径的部分量度，存储每一状态下的路径及其部分量度。2. j2. j增加增加1 1，n 分别计算进入每一状态的所有分枝量度，并分别将其与前一单位时间有关的部分量度相加
20、得到新的部分量度；n 对每一状态，比较进入它的所有路径的部分量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除其它路径。【加、比、选】3. 3. 若若j6j6，重复以上步骤，否则停止。，重复以上步骤，否则停止。3/27/2022信道编码信道编码345.4 卷积码的概率译码pVitebi译码的基本原理译码的基本原理注意：n从时间单位2(m)到4(L)中，每个状态都有一个幸存路径。时间单位4(L)之后，幸存路径减少，最后在时间单位2+4时，只有一个状态，即全0状态。n回溯：由估值序列根据网格图得出信息序列的过程。 经回溯，得到信息序列m（101100），去掉补的m2个0得译码信息序
21、列m（1011）。n以上过程是针对结尾卷积码序列的译码操作。3/27/2022信道编码信道编码355.4 卷积码的概率译码pVitebi最大似然路径算法步骤：最大似然路径算法步骤： 1. 1. 从时间单位从时间单位j jm m开始，计算进入每一状态的单个路径开始，计算进入每一状态的单个路径的部分量度，存储每一状态下的路径及其部分量度。的部分量度，存储每一状态下的路径及其部分量度。2. j增加1，分别计算进入每一状态的所有分枝量度，并分别将其与前一单位时间有关的部分量度相加得到新的部分量度，然后对每一状态比较进入它的所有路径的部分量度，选出其中具有最佳量度的路径（幸存路径）及其量度进行存储，删除
22、其它路径。【加、比、选】3. 若jLm，重复以上步骤，否则停止。3/27/2022信道编码信道编码365.4 卷积码的概率译码p软判决软判决 Vitebi 译码译码n软判决译码：译码输入为多电平量化信号。n硬判决译码用于BSC信道。n软判决译码用于一般DMC信道。n软判决维特比译码与硬判决原理相同，但路径度量不同。软判决维特比译码采用软距离作为分支和路径度量。3/27/2022信道编码信道编码375.4 卷积码的概率译码p软判决软判决Vitebi译码译码n软距离： 如采用8电平均匀量化，用07表示量化值，最小电平为0、最大电平为7。 比特0与电平0的软距离为0、与电平7的软距离为7；比特1与电
23、平0的软距离为7、与电平7的软距离为0。3/27/2022信道编码信道编码385.4 卷积码的概率译码p软判决软判决Vitebi译码译码例如：接收分组R(i)=(4 6 2) 同分支(110)之间的软距离为：3+1+2=6 同分支(011)之间的软距离为：4+1+5=10n有了软距离的定义，可采用与硬判决译码相同的原理实现软判决维特比译码。3/27/2022信道编码信道编码395.4 卷积码的概率译码p软判决软判决Vitebi译码译码软判决维特比译码的优点软判决维特比译码的优点：1、由于充分利用了信道输出信号的信息，软判决译码的、由于充分利用了信道输出信号的信息，软判决译码的性能要由于硬判决译码，性能提高约性能要由于硬判决译码，性能提高约23dB。2、除增加少量存储外，软判决维特比译码的复杂度与硬、除增加少量存储外，软判决维特比译码的复杂度与硬判决译码相当。判决译码相当。3、只需、只需8电平量化即可达到较好的性能：比硬判决提高电平量化即可达到较好的性能：比硬判决提高23dB，比无穷量化差，比无穷量化差0.20.3dB。
