第八讲卷积码

现代通信原理2010.9~2011.1主要内容卷积码卷积码与分组码的区别与联系卷积码的表示卷积码的性质维特比译码原理基于网格图的维特比译码为什么要采用卷积码？卷积码可以用哪些形式进行表示？卷积码的距离特性如何？如何求解？维特比译码的基本原理是什么？维特比译码如何实现？研究对象研究对象在通信系统中的位置格式化信源编码加密信道编码多路复用脉冲调制带通调制频率扩展复用多址接入格式化信源译码解密信道译码多路分接检测解调采样频率解扩复用多址接入信源信宿消息码元数字输入消息码元消息码元数字输出消息码元比特流数字基带波形数字频带波形信道同步卷积码的概念为什么要引入卷积码回顾分组码把k位信息比特的序列编成n个比特的码组，每个码组的(n-k)位校验码仅与本码组的k位信息有关，而与其他码组无关回顾香农信道编码定理在信道容量与发送信息速率一定的条件下，增加码长，可以使错误概率指数下降由此引起的问题线性分组码增加码长，必然导致编解码的延时加大，复杂度也随之增大，如何解决这一矛盾？卷积码的概念卷积码将k位信息编成n个比特，但此n个比特不但与当前位的k个信息有关，而且与前面(N-1)组的信息有关。编码中相互关联的码元为N*n位卷积码的纠错能力随着N的增加而增大，而差错率随着N的增加而成指数下降类似输入序列与某一特定序列的卷积卷积码的表示卷积码的参数——（n，k，N）N：约束长度，移位寄存器的级数（每级有k个)k：信息码位的数目，是卷积码编码器的每级输入的比特数目n：k位信息码对应编码后的输出的比特数，它与Nk个输入比特相关码率卷积码的表示最直观的描述编码器框图缺点：无法进行任何数学讨论，无法给出解码方案更有用的描述树状图表示：遍历可能性，用于分析最小距离网格图表示：用于Viterbi解码状态图与生成函数：用于分析自由距半无限矩阵表示：用于类比分组码从例子入手，从基本的树状图开始，进一步到状态图及网格图卷积码的表示树状图基本思想利用树的结构表征移位过程中产生的各种序列例子——（2，1，3）卷积码卷积码的表示树状图第一步：假设寄存器中初始状态为全0，给出树的根节点卷积码的表示树状图第二步：根据输入的各种变化，画出树的第一层输入的比特数为k，共有种变化每一种变化对应树的一个分叉，共有个分叉每输入k个比特，对应n个输入，每一分叉上标上输出的序列，分叉的端点为新的状态分支的排列顺序相同，如上分支为输入0，下分支为输入1状态a卷积码的表示树状图第三步：按照第二步的方法，继续画出树的第二层、第三层…状态b状态c卷积码的表示树状图第三步：继续状态d卷积码的表示树状图第四步：还要再继续吗？状态是有限的–（n，k，N）卷积码的状态数–（2，1，3）卷积码的状态数4只要状态及其分支都出现了，则后边的都是重复，没有必要再继续了–（2，1，3）卷积码共有4个状态，树状图第二层即出现了所有状态，因此画到树状图的第三层就可以了，此后即是重复卷积码的表示树状图由树状图求卷积码的最小距卷积码也是线性码，卷积具有线性性质类似于分组码，卷积码的最小码距也定义为非零码字的最小码重卷积码中的码字:–卷积码没有分组的概念–约束长度隐含某种独立性，即可以考虑kN个信息比特编码后输出的码序列，即nN个编码输出序列–非零码字，离开全零状态，经过约束长度个输入后的一串编码输出卷积码的表示树状图由树状图求卷积码的最小距（2，1，3)卷积码求最小距因为要离开全零状态，树状图的上半部不用考虑约束长度为3，只考虑三级即可卷积码的表示状态图从树状图到状态图对树状图进行精简，去掉冗余的部分（树状图中重复的部分）状态图–节点是编码器的状态–边表示状态的转移–边上标注对应该转移的输出卷积码的表示状态图（2，1，3）的例子卷积码的表示状态图由状态图计算自由距自由距：无限长编码后序列之间的最小汉明距离（卷积码不分组，自由距作为卷积码纠错性能的度量更合理）自由距不小于最小距自由距的求解–全零是一个无限长的编码后序列，因此编码后的非零序列应包含尽可能多的零，从而保证与全零序列之间具有最小的汉明距–从全零出发，经历非零状态，又重新回到全零过程中输出的1的最少的个数即为自由距卷积码的表示状态图由状态图计算自由距（2，1，3）卷积码为例状态图变形：从a出发重新回到a的所有路径卷积码的表示状态图由状态图计算自由距状态图和码距、转移次数等关联起来–定义转移的增益为，其中表示输出序列的汉明重量，表示输入序列的汉明重量，L为转移的支路数目卷积码的表示状态图由状态图计算自由距根据梅森公式计算从a到a的转移函数存在长度为3的支路（L的幂次为3），码重为5（D的幂次为5），其它支路对应项中D的幂次大于5，所以5就是自由距卷积码的表示网格图由树状图到网格图树状图中的状态用分行的点表示，每一层树状图中相同状态的节点合并到网格图中的每列相同的点树状图的每一层对应网格图中的每一级树状图中的分支对应网格图中的连线（每一分支代表一种输入，分支的排列按照相同的规则(例如（2，1，3）中上分支代表0输入，下分支代表1输入）卷积码的表示网格图网格图与状态图的对应状态图对应网格图中稳态中的一节卷积码的表示网格图网格图可以表征编码过程根据输入的码序列确定了一条路径，这条路径上的所有输出连接起来就是输出的码序列网格图在卷积码的维特比译码中具有非常重要的作用输入：1100输出：11010100卷积码的表示网格图由网格图求解最小自由距从全零出发回到全零的输出序列的最少的1的个数路径abca，输出码序列111011，最小自由距5卷积码的表示解析表示编码器的多项式表示多项式系数的8进制表示卷积码的译码卷积码的译码方法维特比译码基于最大似然译码性能接近最优硬件实现复杂序列译码基于最大似然译码性能接近维特比译码时，译码延时大译码延时小时，误码率增大门限译码基于分组码的译码思想性能最差硬件最简单卷积码的译码最大似然译码模型数学描述译码器必须根据接收序列y来产生信息序列M的一个估计M’。如果二者不同，则表明译码器出现差错。信息序列M经过编码器输出X，二者之间有一一对应的关系；译码器产生的码字是X的一个估值X’，只有当X’=X时，M’=M，即无误码如果信道中传送的码字是X，当且仅当X’/=X出现译码错误卷积码的译码最大似然译码错误概率最小的条件进一步推导物理意义：译码器在收到Y序列的情况下，选择具有最大条件概率的序列X作为译码输出，则将使译码后的序列具有最小差错概率。这种译码器称为最大似然译码卷积码的译码最大似然译码最大似然译码的具体做法定义，编码器输出序列X的长度为L，经信道传输后比特错误概率为p，发生错误的比特数为e上式中，A和B为常数，由编码序列长度以及信道所决定，要使上式最大化，则要求e最小，即X和Y序列之间的汉明距离最小！最大似然译码就是寻求和Y序列之间具有最小汉明距离的X序列！卷积码的译码还是先看一个例子——（2，1，3）卷积码接收码序列11010100路径abdcb与接收序列完全对应，汉明距为0，译码输出1100卷积码的译码还是先看一个例子——（2，1，3）卷积码接收码序列11010110——出现错误在网格图上找一条路径，其对应的编码输出与接收到的码字汉明距离最小，并将其对应的信息码元作为编码输出问题来了：汉明距一样，选哪一条？卷积码的译码还是先看一个例子——（2，1，3）卷积码接收码序列1101010011000001…——无限长，怎么办？等所有码都接收下来以后再找汉明距最小的路径？–显然不可行，实时性太差了–如果无限长则根本做不到，存储器不可能无限大总结最大似然译码中的两个问题可能出现多个具有相同汉明距离的分支译码的实时性如何保证维特比译码基于动态规划的方法进行实时译码维特比译码几个概念路径量度该路径输出序列与接收序列之间的汉明距离含有多段路径的一条路径总的量度等于所有各段路径量度的总和幸存路径经过量度比较之后总量度较小的路径被保留下来，称为幸存路径维特比译码先看一个简单例子——动态规划方法找出下图中总量度最小的一条路径（没标量度值的为0)基本的规则：当前最优路径只能产生于上一步的最优路径+当前一步的组合中第一步：aa、bb幸存，ab、ba淘汰第二步：aab、bba幸存，aaa、bbb淘汰第三步：aaba、aabb幸存，bbab、bbaa淘汰维特比译码先看一个简单例子——动态规划方法找出下图中总量度最小的一条路径注意第三步的结果–此时幸存的最优路径都是从aab衍生出来，因此，不管后边如何发展，前三步的最优路径已经确定，前三步的译码结果就可以输出–实现了实时译码，减小了复杂度，降低了系统实现代价维特比译码译码过程从全零开始计算每一段的量度及路径总量度，保留幸存路径，淘汰其他路径所有幸存路径合并的部分即可输出译码结果，其他部分继续译码维特比译码（2，1，3)卷积码译码的例子接收码字序列1101011001101110维特比译码维特比译码维特比译码维特比译码维特比译码维特比译码维特比译码红色路径最有可能，译码输出11001111，红框内发生误码！本讲回顾卷积码的定义卷积码的编码器卷积码的表示（n，k，N）参数的含义树状图网格图状态图要求可以根据给定的编码器给出上述各种表示方式卷积码的距离特性根据树状图求最小距离根据网格图求最小自由距本讲回顾最大似然译码的概念维特比译码要求会根据网格图进行维特比译码作业12.1（第5、7小问不要求），12.7，12.8