第八讲卷积码

1、主要内容主要内容n 卷积码卷积码卷积码与分组码的区别与联系卷积码与分组码的区别与联系卷积码的表示卷积码的表示卷积码的性质卷积码的性质维特比译码原理维特比译码原理基于网格图的维特比译码基于网格图的维特比译码为什么要采用卷积码？为什么要采用卷积码？卷积码可以用哪些形式进行表示？卷积码可以用哪些形式进行表示？卷积码的距离特性如何？如何求解？卷积码的距离特性如何？如何求解？维特比译码的基本原理是什么？维特比译码的基本原理是什么？维特比译码如何实现？维特比译码如何实现？研究对象研究对象n 研究对象在通信系统中的位置研究对象在通信系统中的位置 格式化 信源 编码 加密 信道 编码 多路 复用 脉冲 调制

2、带通 调制 频率 扩展 复用 多址 接入 格式化 信源 译码 解密 信道 译码 多路 分接 检测 解调 采样 频率 解扩 复用 多址 接入 信源 信宿 消息码元 数字输入消息码元 消息码元 数字输出消息码元 比特流 数字基带波形 数字频带波形 信 道 同步 卷积码的概念卷积码的概念n 为什么要引入卷积码为什么要引入卷积码回顾分组码回顾分组码把把k位信息比特的序列编成位信息比特的序列编成n个比特的码组，每个码个比特的码组，每个码组的组的(n-k)位校验码仅与本码组的位校验码仅与本码组的k位信息有关，而与位信息有关，而与其他码组无关其他码组无关回顾香农信道编码定理回顾香农信道编码定理在信道容量与发

3、送信息速率一定的条件下，增加码在信道容量与发送信息速率一定的条件下，增加码长，可以使错误概率指数下降长，可以使错误概率指数下降由此引起的问题由此引起的问题线性分组码增加码长，必然导致编解码的延时加大线性分组码增加码长，必然导致编解码的延时加大，复杂度也随之增大，如何解决这一矛盾？，复杂度也随之增大，如何解决这一矛盾？卷积码的概念卷积码的概念n 卷积码卷积码将将k位信息编成位信息编成n个比特，但此个比特，但此n个比特不但与当前位的个比特不但与当前位的k个信息有关，而且与前面个信息有关，而且与前面(N-1)组的信息有关。编码中组的信息有关。编码中相互关联的码元为相互关联的码元为N*n位位卷积码的纠

4、错能力随着卷积码的纠错能力随着N的增加而增大，而差错率随着的增加而增大，而差错率随着N的增加而成指数下降的增加而成指数下降类似输入序列与某一特定序列的卷积卷积码的表示卷积码的表示n 卷积码的参数卷积码的参数（n，k，N）N：约束长度，移位寄存器的级数（每级有：约束长度，移位寄存器的级数（每级有k个个)k：信息码位的数目，是卷积码编码器的每级输入的比：信息码位的数目，是卷积码编码器的每级输入的比特数目特数目n：k位信息码对应编码后的输出的比特数，它与位信息码对应编码后的输出的比特数，它与Nk个个输入比特相关输入比特相关码率码率卷积码的表示卷积码的表示n 最直观的描述最直观的描述编码器框图编码器框

5、图缺点：无法进行任何数学讨论，无法给出解码方案缺点：无法进行任何数学讨论，无法给出解码方案n 更有用的描述更有用的描述树状图表示：遍历可能性，用于分析最小距离树状图表示：遍历可能性，用于分析最小距离网格图表示：用于网格图表示：用于Viterbi解码解码状态图与生成函数：用于分析自由距状态图与生成函数：用于分析自由距半无限矩阵表示：用于类比分组码半无限矩阵表示：用于类比分组码从例子入手，从基本的树状图开始，进一步到状态图及网格图卷积码的表示卷积码的表示n 树状图树状图基本思想基本思想利用树的结构表征移位过程中产生的各种序列利用树的结构表征移位过程中产生的各种序列例子例子（2，1，3）卷积码）卷积

6、码卷积码的表示卷积码的表示n 树状图树状图第一步：假设寄存器中初始状态为全第一步：假设寄存器中初始状态为全0，给出树的根节，给出树的根节点点卷积码的表示卷积码的表示n 树状图树状图第二步：根据输入的各种变化，画出树的第一层第二步：根据输入的各种变化，画出树的第一层输入的比特数为输入的比特数为k，共有，共有 种变化种变化每一种变化对应树的一个分叉，共有每一种变化对应树的一个分叉，共有 个分叉个分叉每输入每输入k个比特，对应个比特，对应n个输入，每一分叉上标上输出的序列，分叉个输入，每一分叉上标上输出的序列，分叉的端点为新的状态的端点为新的状态分支的排列顺序相同，如上分支为输入分支的排列顺序相同，

7、如上分支为输入0，下分支为输入，下分支为输入1状态a卷积码的表示卷积码的表示n 树状图树状图第三步：按照第二步的方法，继续画出树的第二层、第第三步：按照第二步的方法，继续画出树的第二层、第三层三层状态b状态c卷积码的表示卷积码的表示n 树状图树状图第三步：继续第三步：继续状态d卷积码的表示卷积码的表示n 树状图树状图 第四步：还要再继续吗？第四步：还要再继续吗？状态是有限的状态是有限的 （n，k，N）卷积码的状）卷积码的状态数态数 （2，1，3）卷积码的状态）卷积码的状态数数4只要状态及其分支都出现了，只要状态及其分支都出现了，则后边的都是重复，没有必要则后边的都是重复，没有必要再继续了再继续

8、了 （2，1，3）卷积码共有）卷积码共有4个状态，树状图第二层即个状态，树状图第二层即出现了所有状态，因此画出现了所有状态，因此画到树状图的第三层就可以到树状图的第三层就可以了，此后即是重复了，此后即是重复卷积码的表示卷积码的表示n 树状图树状图由树状图求卷积码的最小距由树状图求卷积码的最小距卷积码也是线性码，卷积具有线性性质卷积码也是线性码，卷积具有线性性质类似于分组码，卷积码的最小码距也定义为非零码类似于分组码，卷积码的最小码距也定义为非零码字的最小码重字的最小码重卷积码中的码字卷积码中的码字:卷积码没有分组的概念卷积码没有分组的概念约束长度隐含某种独立性，即可以考虑约束长度隐含某种独立性

9、，即可以考虑kN个信息个信息比特编码后输出的码序列，即比特编码后输出的码序列，即nN个编码输出序列个编码输出序列非零码字，离开全零状态，经过约束长度个输入非零码字，离开全零状态，经过约束长度个输入后的一串编码输出后的一串编码输出卷积码的表示卷积码的表示n 树状图树状图由树状图求卷积码的最小距由树状图求卷积码的最小距（2，1，3)卷积码求最小距卷积码求最小距因为要离开全零状态，树状图的上半部不用考虑因为要离开全零状态，树状图的上半部不用考虑约束长度为约束长度为3，只考虑，只考虑 三级即可三级即可卷积码的表示卷积码的表示n 状态图状态图从树状图到状态图从树状图到状态图对树状图进行精简，对树状图进行

10、精简，去掉冗余的部分（树去掉冗余的部分（树状图中重复的部分）状图中重复的部分）状态图状态图节点是编码器的状节点是编码器的状态态边表示状态的转移边表示状态的转移边上标注对应该转边上标注对应该转移的输出移的输出卷积码的表示卷积码的表示n 状态图状态图（2，1，3）的例子）的例子卷积码的表示卷积码的表示n 状态图状态图由状态图计算自由距由状态图计算自由距自由距：无限长编码后序列之间的最小汉明距离（自由距：无限长编码后序列之间的最小汉明距离（卷积码不分组，自由距作为卷积码纠错性能的度量更卷积码不分组，自由距作为卷积码纠错性能的度量更合理）合理）自由距不小于最小距自由距不小于最小距自由距的求解自由距的求

11、解全零是一个无限长的编码后序列，因此编码后的全零是一个无限长的编码后序列，因此编码后的非零序列应包含尽可能多的零，从而保证与全零非零序列应包含尽可能多的零，从而保证与全零序列之间具有最小的汉明距序列之间具有最小的汉明距从全零出发，经历非零状态，又重新回到全零过从全零出发，经历非零状态，又重新回到全零过程中输出的程中输出的1的最少的个数即为自由距的最少的个数即为自由距卷积码的表示卷积码的表示n 状态图状态图由状态图计算自由距由状态图计算自由距（2，1，3）卷积码为例）卷积码为例状态图变形：从状态图变形：从a出发重新回到出发重新回到a的所有路径的所有路径卷积码的表示卷积码的表示n 状态图状态图由状

12、态图计算自由距由状态图计算自由距状态图和码距、转移次数等关联起来状态图和码距、转移次数等关联起来定义转移的增益为定义转移的增益为 ，其中，其中 表示输出表示输出序列的汉明重量，序列的汉明重量， 表示输入序列的汉明重量，表示输入序列的汉明重量，L为转移的支路数目为转移的支路数目卷积码的表示卷积码的表示n 状态图状态图由状态图计算自由距由状态图计算自由距根据梅森公式计算从根据梅森公式计算从a到到a的转移函数的转移函数存在长度为3的支路（L的幂次为3），码重为5（D的幂次为5），其它支路对应项中D的幂次大于5，所以5就是自由距卷积码的表示卷积码的表示n 网格图网格图 由树状图到网格图由树状图到网格图

13、树状图中的状态用分行的点表示，每一层树状图中相同状态的节点树状图中的状态用分行的点表示，每一层树状图中相同状态的节点合并到网格图中的每列相同的点合并到网格图中的每列相同的点树状图的每一层对应网格图中的每一级树状图的每一层对应网格图中的每一级树状图中的分支对应网格图中的连线（每一分支代表一种输入，分树状图中的分支对应网格图中的连线（每一分支代表一种输入，分支的排列按照相同的规则支的排列按照相同的规则(例如（例如（2，1，3）中上分支代表）中上分支代表0输入，下输入，下分支代表分支代表1输入）输入）卷积码的表示卷积码的表示n 网格图网格图网格图与状态图的对应网格图与状态图的对应状态图对应网格图中稳

14、态中的一节状态图对应网格图中稳态中的一节卷积码的表示卷积码的表示n 网格图网格图网格图可以表征编码过程网格图可以表征编码过程根据输入的码序列确定了一条路径，这条路径上的根据输入的码序列确定了一条路径，这条路径上的所有输出连接起来就是输出的码序列所有输出连接起来就是输出的码序列网格图在卷积码的维特比译码中具有非常重要的作用网格图在卷积码的维特比译码中具有非常重要的作用输入：输入：11001100输出：输出：1101010011010100卷积码的表示卷积码的表示n 网格图网格图由网格图求解最小自由距由网格图求解最小自由距从全零出发回到全零的输出序列的最少的从全零出发回到全零的输出序列的最少的1的

15、个数的个数路径abca，输出码序列111011，最小自由距5卷积码的表示卷积码的表示n 解析表示解析表示编码器的多项式表示编码器的多项式表示多项式系数的多项式系数的8进制表示进制表示卷积码的译码卷积码的译码n 卷积码的译码方法卷积码的译码方法 维特比译码维特比译码基于最大似然译码基于最大似然译码性能接近最优性能接近最优硬件实现复杂硬件实现复杂 序列译码序列译码基于最大似然译码基于最大似然译码性能接近维特比译码时，译码延时大性能接近维特比译码时，译码延时大译码延时小时，误码率增大译码延时小时，误码率增大 门限译码门限译码基于分组码的译码思想基于分组码的译码思想性能最差性能最差硬件最简单硬件最简单

16、卷积码的译码卷积码的译码n 最大似然译码最大似然译码 模型模型 数学描述数学描述译码器必须根据接收序列译码器必须根据接收序列y来产生信息序列来产生信息序列M的一个估计的一个估计M。如果二者不同，则表明译码器出现差错。如果二者不同，则表明译码器出现差错。信息序列信息序列M经过编码器输出经过编码器输出X，二者之间有一一对应的关系；，二者之间有一一对应的关系；译码器产生的码字是译码器产生的码字是X的一个估值的一个估值X，只有当，只有当X=X时，时，M=M，即无误码，即无误码如果信道中传送的码字是如果信道中传送的码字是X，当且仅当，当且仅当X/=X 出现译码错误出现译码错误卷积码的译码卷积码的译码n

17、最大似然译码最大似然译码错误概率最小的条件错误概率最小的条件进一步推导进一步推导物理意义：译码器在收到物理意义：译码器在收到Y序列的情况下，选择具有序列的情况下，选择具有最大条件概率最大条件概率 的序列的序列X作为译码输出，则作为译码输出，则将使译码后的序列具有最小差错概率。这种译码器称将使译码后的序列具有最小差错概率。这种译码器称为为最大似然译码最大似然译码卷积码的译码卷积码的译码n 最大似然译码最大似然译码最大似然译码的具体做法最大似然译码的具体做法定义，编码器输出序列定义，编码器输出序列X的长度为的长度为L，经信道传输后，经信道传输后比特错误概率为比特错误概率为p，发生错误的比特数为，发

18、生错误的比特数为e上式中，上式中，A和和B为常数，由编码序列长度以及信道所为常数，由编码序列长度以及信道所决定，要使上式最大化，则要求决定，要使上式最大化，则要求e最小，即最小，即X和和Y序列序列之间的汉明距离最小！之间的汉明距离最小！最大似然译码就是寻求和Y序列之间具有最小汉明距离的X序列！卷积码的译码卷积码的译码n 还是先看一个例子还是先看一个例子（2，1，3）卷积码）卷积码接收码序列接收码序列11010100路径abdcb与接收序列完全对应，汉明距为0，译码输出1100卷积码的译码卷积码的译码n 还是先看一个例子还是先看一个例子（2，1，3）卷积码）卷积码接收码序列接收码序列110101

19、10出现错误出现错误在网格图上找一条路径，其对应的编码输出与接收在网格图上找一条路径，其对应的编码输出与接收到的码字汉明距离最小，并将其对应的信息码元作为到的码字汉明距离最小，并将其对应的信息码元作为编码输出编码输出问题来了：汉明问题来了：汉明距一样，选哪一距一样，选哪一条？条？卷积码的译码卷积码的译码n 还是先看一个例子还是先看一个例子（2，1，3）卷积码）卷积码接收码序列接收码序列1101010011000001无限长，怎么办？无限长，怎么办？等所有码都接收下来以后再找汉明距最小的路径？等所有码都接收下来以后再找汉明距最小的路径？显然不可行，实时性太差了显然不可行，实时性太差了如果无限长则

20、根本做不到，存储器不可能无限大如果无限长则根本做不到，存储器不可能无限大n 总结最大似然译码中的两个问题总结最大似然译码中的两个问题可能出现多个具有相同汉明距离的分支可能出现多个具有相同汉明距离的分支译码的实时性如何保证译码的实时性如何保证n 维特比译码维特比译码基于动态规划的方法进行实时译码基于动态规划的方法进行实时译码维特比译码维特比译码n 几个概念几个概念路径量度路径量度该路径输出序列与接收序列之间的汉明距离该路径输出序列与接收序列之间的汉明距离含有多段路径的一条路径总的量度等于所有各段路含有多段路径的一条路径总的量度等于所有各段路径量度的总和径量度的总和幸存路径幸存路径经过量度比较之后

21、总量度较小的路径被保留下来，经过量度比较之后总量度较小的路径被保留下来，称为幸存路径称为幸存路径维特比译码维特比译码n 先看一个简单例子先看一个简单例子动态规划方法动态规划方法找出下图中总量度最小的一条路径（没标量度值的为找出下图中总量度最小的一条路径（没标量度值的为0)基本的规则：当前最优路径只能产生于上一步的最基本的规则：当前最优路径只能产生于上一步的最优路径优路径+当前一步的组合中当前一步的组合中第一步：第一步：aa、bb幸存，幸存，ab、ba淘汰淘汰第二步：第二步：aab、bba幸存，幸存，aaa、bbb淘汰淘汰第三步：第三步：aaba、aabb幸存，幸存，bbab、bbaa淘汰淘汰维特比译码维特比译码n 先看一个简单例子先看一个简单例子动态规划方法动态规划方法找出下图中总量度最小的一条路径找出下图中总量度最小的一条路径注意第三步的结果注意第三步的结果此时幸存的最优路径都是从此时幸存的最优路径都是从aab衍生出来，因此，衍生出来，因此，不管后边如何发展，