卷积码 修改版

卷积码基本理论与应用组员：王宁王宇王鑫尹晓东主要内容卷积码卷积码与分组码的区别与联系卷积码的表示卷积码的性质维特比译码原理基于网格图的维特比译码为什么要采用卷积码？卷积码可以用哪些形式进行表示？卷积码的距离特性如何？如何求解？维特比译码的基本原理是什么？维特比译码如何实现？2020/4/163卷积码与分组码的区别与联系研究对象研究对象在通信系统中的位置格式化信源编码加密信道编码多路复用脉冲调制带通调制频率扩展复用多址接入格式化信源译码解密信道译码多路分接检测解调采样频率解扩复用多址接入信源信宿消息码元数字输入消息码元消息码元数字输出消息码元比特流数字基带波形数字频带波形信道同步卷积码的概念卷积码将k位信息编成n个比特，但此n个比特不但与当前位的k个信息有关，而且与前面(N-1)组的信息有关。编码中相互关联的码元为N*n位卷积码的纠错能力随着N的增加而增大，而差错率随着N的增加而成指数下降类似输入序列与某一特定序列的卷积卷积码的表示树状图第一步：假设寄存器中初始状态为全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）的例子卷积码的表示状态图由状态图计算自由距（2，1，3）卷积码为例状态图变形：从a出发重新回到a的所有路径卷积码的表示状态图由状态图计算自由距状态图和码距、转移次数等关联起来–定义转移的增益为，其中表示输出序列的汉明重量，表示输入序列的汉明重量，L为转移的支路数目卷积码的表示网格图由树状图到网格图树状图中的状态用分行的点表示，每一层树状图中相同状态的节点合并到网格图中的每列相同的点树状图的每一层对应网格图中的每一级树状图中的分支对应网格图中的连线（每一分支代表一种输入，分支的排列按照相同的规则(例如（2，1，3）中上分支代表0输入，下分支代表1输入）卷积码的表示网格图由网格图求解最小自由距从全零出发回到全零的输出序列的最少的1的个数路径abca，输出码序列111011，最小自由距5卷积码的表示卷积码的参数——（n，k，N）N：约束长度，移位寄存器的级数（每级有k个)k：信息码位的数目，是卷积码编码器的每级输入的比特数目n：k位信息码对应编码后的输出的比特数，它与Nk个输入比特相关码率卷积码的表示最直观的描述编码器框图缺点：无法进行任何数学讨论，无法给出解码方案更有用的描述树状图表示：遍历可能性，用于分析最小距离网格图表示：用于Viterbi解码状态图与生成函数：用于分析自由距半无限矩阵表示：用于类比分组码从例子入手，从基本的树状图开始，进一步到状态图及网格图卷积码的表示树状图第二步：根据输入的各种变化，画出树的第一层输入的比特数为k，共有种变化每一种变化对应树的一个分叉，共有个分叉每输入k个比特，对应n个输入，每一分叉上标上输出的序列，分叉的端点为新的状态分支的排列顺序相同，如上分支为输入0，下分支为输入1状态a第22页2020/4/16DepartmentofElectronicsandInformation,NCUTSongPeng10.1卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例9.1.1]：(2,1,3)码图10.1.1(2,1,3)码编码电路Kg0(1,1)C1g1(1,1)g2(1,1)g3(1,1)g0(1,2)g1(1,2)g2(1,2)g3(1,2)M2返回2020/4/1623第24页2020/4/16DepartmentofElectronicsandInformation,NCUTSongPeng卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例]：(2,1,3)码待编码的信息序列M：在对M进行编码之前，先将它每k个码元分成一组，在每单元时刻内，k个码元串行输入到编码器；移位寄存器组：(m+1)个，每个移位寄存器组内有k级寄存器；常数乘法器g(i,j)：i=1,2,…,k；j=1,2,…,n，共有(m+1)•n个，当g(i,j)=1时，常数乘法器为一条直通的连接线；当g(i,j)=0时，连接线断开。每一个码元都是k•(m+1)个数据组合，每一个码字需用n•k•(m+1)个系数才能描述；开关K在每一节拍中移动n次，每一节拍输入k个信息元而输出n个码元。参见图第25页2020/4/16卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例]：(2,1,3)码信息序列M=[m0(1)m1(1)…]；ml(1)表示第l个时刻的第k=1个信息元；卷积码的生成序列g(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]g(1,1)表明：任一时刻l时，输出端1的码元Cl(1)是由此时刻l输入的信息元ml(1)与前两个时刻输入的信息元ml－2(1)以及前三个时刻ml－3(1)输入的信息元模2加后的和；g(1,2)表明：Cl(2)是由ml(1)、ml－1(1)、ml－2(1)和ml－3(1)的模2和。参见图第26页2020/4/16DepartmentofElectronicsandInformation,NCUTSongPeng卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例]：(2,1,3)码信息序列M=[m0(1)m1(1)…]；ml(1)表示第l个时刻的第k=1个信息元；卷积码的生成序列生成序列：给定g(i,j)后，就可以生成编码器输出的码元。称g(1,1)和g(1,2)为(2,1,3)卷积码的生成序列。第l个时刻的编码器输出为：)1()1()1()1()2,1()1()2,1()1()2,1()1()2,1()1()2()1()1()1()2,1()1()1,1()1()1,1()1()1,1()1()1(3213322110323322110lllllllllllllllllmmmmgmgmgmgmCmmmgmgmgmgmC2,1),1()1()(30jjgmjCtttll或者：第27页2020/4/16DepartmentofElectronicsandInformation,NCUTSongPeng卷积码的基本概念(1)卷积码的生成序列、约束度和约束长度[例]：(2,1,3)码信息序列M=[m0(1)m1(1)…]；ml(1)表示第l个时刻的第k=1个信息元；卷积码的生成序列卷积码名称的由来：任一时刻编码器的输出可以由信息元与生成序列的离散卷积运算求出。ttnxthny)()()(卷积公式：2,1),1()1()(30jjgmjCtttll2020/4/1628(2,1,3)码每个子码中的码元不仅与此时此刻的信息元有关，而且还与前m个(m=3)时刻的信息元有关。编码存储：m（本例m=3）约束度：N=m+1，编码过程中相互约束的子码数。（本例N=4）编码约束长度：Nn，编码过程中相互约束的码元数。（本例Nn=8）非系统码：在码序列C中的每个子码不是系统码字结构。（本例是非系统码）2020/4/1629[例10.1.2]：(3,2,1)码n=3,k=2,m=1；它的任一子码有3个码元。每个码元由此时此刻的2个信息元和前一个时刻进入编码器的2个信息元模2运算和求出。这些信息元参加模2运算的规则由[nk]=3×2=6个生成序列{[nk(m+1)]=3×2×2=12个系数}所确定，每个生成序列含有2个元素。这6个输出序列是：g(1,1)=[g0(1,1)g1(1,1)]=[11]g(1,2)=[g0(1,2)g1(1,2)]=[01]g(1,3)=[g0(1,3)g1(1,3)]=[11]g(2,1)=[g0(2,1)g1(2,1)]=[01]g(2,2)=[g0(2,2)g1(2,2)]=[10]g(2,3)=[g0(2,3)g1(2,3)]=[10](1)卷积码的生成序列、约束度和约束长度与四则运算不同的是模2运算不考虑进位和借位，即模2加法是不带进位的二进制加法运算，模2减法是不带借位的二进制减法运算。这样，两个二进制位相运算时，这两个位的值就能确定运算结果，不受前一次运算的影响，也不对下一次造成影响。模2运算是一种二进制算法，CRC校验技术中的核心部分。与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。2020/4/1630模二运算补充2020/4/1631[例10.1.2]：(3,2,1)码若待编码的信息序列：M=[m0(1)m0(2)m1(1)m1(2)…ml(1)ml(2)…]则码序列C中的任一子码为：)2.1.10(3,2,1,),()()()3,()()3()2,()()2()1,()()1(2110211021102110jjigimjCigimCigimCigimCitttllitttllitttllitttll)3,2()2()3,2()2()3,1()1()3,1()1()3()2,2()2()2,2()2()2,1()1()2,1()1()2()1,2()2()1,2()2()1,1()1()1,1()1()1(110110110110110110gmgmgmgmCgmgmgmgmCgmgmgmgmClllllllllllllll(1)卷积码的生成序列、约束度和约束长度码序列：C=[C0(1)C0(2)…C0(n)C1(1)C1(2)…C1(n)…Cl(1)Cl(2)…Cl(n)…]待编码的信息序列：M=[m0(1)m0(2)…m0(k)m1(1)m1(2)…m1(k)…ml(1)ml(2)…ml(k)…]任一子码：可按如下卷积关系求出：2020/4/1632推论：(n,k,m)码完全由(nk)个生成序列所生成，每个生成序列中含有(N=m+1)个元素。)3.1.10(,,3,2,1),()()(10njjigimjCkimtttll只有K(N－K)个生成序列需要给定，以便确定每个子码中(N－K)个监督元。系统卷积码：是卷积码的一类。它的码序列中任一