第9章 信道编码 —卷积码信息与通信工程学院 无线信号处理与网络实验室 彭岳星 yxpeng@ 6228 22459.5 卷积码例: {gi}={1,1,0,1}, 输出ci为:iiimi mmi m mmcugu gg u−−=⊗==∑∑?卷积?序列{ui}通过冲激响应为{gi}的线性系统,输出ci是 卷积的结果011223313iiiiiiiicg ug ug ug uuuu−−−−−=+++=++卷积的三种计算方法离散卷积；生成矩阵；码多项式卷积码?卷积编码?信息序列{ui}通过冲激响应为{gi}的线性系统,输 出ci是编码序列?码率为1,不存在冗余注?增加冗余 例: (7，5) CC码输入{ui}={1011000…} 冲激响应{gi}={111,101} 输出{ci}?(n,k,m)/(n,k,K)卷积码?(n,k,m)卷积码：k个输入信息比特, n个输出编码比特, m=K-1组移位寄存器, 每组k个寄存器单元?m: 约束长度; 一般n,k取值小, m大?可看成(n×k)个FIR构成的MIMO网络?约束长度越大,一般码字纠错性能越好?编码的效率: k/nn×kk input n output 卷积码与分组码的区别?编码?分组码的当前的一组输出（n个码元）只与当前的一组 输入（k个输入信息位）有关（无记忆性）?卷积码的当前的一组输出（n个码元）不仅与当前的一 组输入（k个输入信息位）有关，还与前面的m组输入 （记忆性）。
即卷积码的当前一组输出（n个码元）共 与(m+1)k个输入信息位有关?性能?在编码结构相当的情况下，卷积码的性能优于分组 码，因而是作为前向纠错码的好的选择之一研究成熟度?分组码有好的代数工具，研究比较成熟透彻；?卷积码没有好的代数工具，研究不是很透彻卷积码的表示方法?解析表示法?离散卷积法?生成矩阵法?码多项式法?图形表示法?状态图法?树图法?格图法离散卷积法?输入到输出的每个分支所构成的系统都是线 性时不变系统，用冲激响应来表征线性时不 变系统，输出是输入与冲激响应的卷积()012uu u u=?()()11112222 0101,mmgg gggg gg==??1122,cug cug=⊗=⊗()()111 12222 0 12012,cc c ccc c c==??()121212 001 122cc c c c c c=?例：离散卷积法(2,1,3)卷积码（图9.5.2）?相应的冲激响应也叫生成序列()()()()() ()121122101111011 ,1111*10000001*110111011101000101010011uggcu gcu gc========码多项式法?将输入序列、生成序列和输出序列分别用码多项式 表示，容易验证，输出码多项式等于输入码多项式 和生成序列码多项式的乘积( )( )( ) ( )( ) ( ),,uu xgg xcc xc xu x g x↔↔↔=注意：?线性分组码中，约定从左到右是MSB (Most Significant Bit) 到LSB (Least Significant Bit)，对应多项式的高次到低次?卷积码中，习惯是从左到右对应多项式的次数从低到高?例：1101如是循环码生成多项式,则g(x)=x3+x2+1 如是卷积码的第i个生成多项式,则gi(x)=1+x+x3例:码多项式法?(2,1,3)卷积码（图9.5.2）()( )()( )()( )234112322231011111011111111uu xxxxggxxxggxxxx=↔= +++=↔= ++=↔= +++( )( )( )()( )( )( )()11712234572110000001111011101cxu x gxxccxu x gxxxxxxc== +↔=== +++++↔=例: 生成矩阵法?(2,1,3)卷积码1101 11111101 11111101 11111101 11 111101 11 11G⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟= ⎜⎟ ⎜⎟⎜⎟⎝⎠()10111u =()1101000101010011cu G==i生成矩阵法?以(2,1,3)卷积码为例推导12121212 00112233 12121212 00112233 12121212 00112233012301230123g gg gg gg gg gg gg gg g Gg gg gg gg gGGGGGGGG GGGG⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟=⎜⎟ ⎜⎟ ⎜⎟⎝⎠ ⎛⎞ ⎜⎟ ⎜⎟=⎜⎟ ⎜⎟⎝⎠???? ??? ?????(n,k,m)生成矩阵法?生成矩阵0101011,11,21,2,12,22,,1,2,mmmn lll n lll lkkk n lllGGGGGGGGGGggggggGggg⎛⎞ ⎜⎟ ⎜⎟=⎜⎟ ⎜⎟⎝⎠⎛⎞ ⎜⎟ ⎜⎟=⎜⎟ ⎜⎟⎜⎟⎝⎠??????????????生成矩阵法?(n,k,m)卷积码的生成序列一般表示式为 ()()()()()0 111g,,,,,,,,,, ;,, ;,,====?????lmi jgi jgi jgi jik jn lm0(1,1)g(),1,2,,,,tttt kuuuu=?0( ,1)g k1( ,1)g k1(1,1)g( ,1)mgk(1,1)mg0(1, )gi0( , )g k i1( , )g k i1(1, )gi( , )mgk i(1, )mgi( )1tc( ),1,,tciin=?例: (n,k,m)卷积码生成矩阵法?(3,2,2)卷积码()()()()()()1,11,21,32,12,22,311 ,01 ,1101 ,10 ,10gggggg======1c2c3c()12u u01101111,011100GG⎛⎞⎛⎞==⎜⎟⎜⎟⎝⎠⎝⎠()110110u =()010101110000001111GGcu GuGG GG⎛⎞ ⎜⎟===⎜⎟⎜⎟⎝⎠ii卷积码状态图寄存器状态：当前状态 (A, B, C), 前一时刻状态(a, b, c), 当前 输入d卷积码状态图?状态：mk个寄存器单元中存储的数据表示状态（共有2mk 种状态）?卷积编码是个Markov链：当前输出和下一步的状态决定于 当前的状态和当前输入?k位输入：输入的可能组合有2k种?状态转移：对每一种状态，均有2k种状态转移方式（对应 2k种输入和输出）树图()1001u =?树图缺点?表示困难，无限扩展?当级数l>m后，树图中的2mk个状态开始重复出现?合并重复出现的状态并保持清晰的时序关系？?格图格图?从l=m+1开始，合并树图中重复 出现的状态?保持了时序的清晰性，表达简洁?研究维特比译码算法的重要工具例：格图方法编码(7, 5) 码输入的信息序列u=(1011100)输出的编码序列c=(11 10 00 01 10 01 11)001001110/000/00 1/111/110/10 1/010/11 1/000/011/101/011/100/010/11卷积码编码(7, 5) 码输入的信息序列u=(1011100)输出的编码序列c=(11 10 00 01 10 01 11)例：卷积编码例：某卷积码的网格图，圆圈中数字代表卷积码状态，实线和虚线分别代表编码器 输入为0和1时的状态转移，其旁边数字代表对应的编码器输出。
请问该卷积码 的编码器的原理框图解：假设输入10000…, 由格图可以看出输出为：11101100…， 因此两路的冲激响应分别是111和101,该编码器原理图为最小最小最小最小( (汉明汉明汉明汉明) )距离译码规则距离译码规则距离译码规则距离译码规则?(准)最佳译码准则: 最大似然译码?二进编码信道或BSC信道, 最大似然译码准则 就是最小汉明距译码准则?发送码字 C=[c1, c2 ,…, cN], 经误码率为p的BSC 信道后接收到Y=[y1, y2 ,…, yN], 似然概率为寻找最小汉明距离路径?每一种发送序列是格图上的一条路径，从0状 态出发，最后达到0状态路径之间的汉明距离?发送序列和接收序列之间的距离为汉明距离，它等 于各条支路的距离之和最佳的译码算法最佳的译码算法最佳的译码算法最佳的译码算法 —— 穷举法穷举法穷举法穷举法?5个信息比特的所有可能的 25 = 32 种组合进行编码， 把编码结果与接收序列比较，计算汉明距离?汉明距离最小的序列就是最有可能的发送序列?复杂度与存储量是信息比特数N的指数函数，实用性 太差，理论意义001001110/000/00 1/111/110/10 1/010/11 1/000/011/101/011/100/010/11递推最短路径?0状态起始?0状态结束?第n步时到达所有状态的最近路径分别已知， 第n+1步到达各状态的最近路径易知?路径减少1，复杂度降低1?每个状态只保留最小距径：幸存路径VA:第一步VA:第二步VA:第三步VA:第三步后的幸存路径VA:第四步VA:第五步VA:第六步VA:第七步VA:最终结果VA的一些定义与算法总结?称汉明距离为度量,累积距离为累积度量,分支的距离为 分支度量?到达每步的累积度量最小的那条路径为幸存路径?全局最优路径为最大似然路径?VA算法?用前一状态的幸存路径与本步的分支度量计算出到达每个状 态的累积度量，保留幸存路径?从第一步开始迭代计算到最后一步得到全局最优路径?复杂度?每步需要比较多路径数2k+m，共L步, 复杂度为O(L2k+m)?穷举法的复杂度O(2L)截短VA算法?VA译码时延为L+m个时钟周期?译码进行到一定步数后前面路径可能已聚合?如果已聚合，ML路径必然经过此聚合路径?如无聚合则以最有可能的路径(当前累积度量最小 的幸存路径),输出前面的比特?局部最佳不等于全局最优，性能有所损失?当L>5m时,性能非常接近最大似然译码直观的译码信息序列 u=(1011100)? 编码序列 c = (11 10 00 01 10 01 11)接收序列 y = (11 10 11 01 11 00 11) 译码序列 u1’ = (1000100) , u2’ = (1001100) 汉明距离 d1 = 4, d2 = 5; 错误比特数 e1 = 2, e2 = 1正确正确:11/1 10/0 00/1 01/1 10/1 01/0 11/0译码1:译码1:11/1 10/0 11/0 00/0 11/1 01/0 11/0译码2:译码2:11/1 10/0 11/0 11/1 01/1 01/0 11/0例例：一卷积码的网格图如图所示，图中实虚线分别表示信息为0和1，各分支 上的数字表示编码输出。
求：1.如输入11 01 11 01 01 11 00 00，请用viterbi译码算法求出译码输出； 2. 画出状态转移图 3. 写出生成多项式 4. 画出编码器框图例解：1.Viterbi译码进程如表所示2/d2/d1/d1/d1/d0/b1/d1/d1/d0/bd3/dd3/d2/d2/d3/d3/d1/d2/bc3/a or 3/c3/a2/c2/c3/a3/d3/d1/d2/bc3/a or 3/c3/a2/c2/c3/a0/a0/ab b2/a2/c2/a2/c5/a or 5/c3/a2/c4/c3/a2/aa到达此状态的幸存路径的：累积度量/前一状态到达状态0000110101110111译码器输入87654321时序5/a or 5/c3/a2/c4/c3/a2/aa到达此状态的幸存路径的：累积度量/前一状态到达状态0000110101110111译码器输入87654321时序因此viterbi译码得到的ML路径是：a-b-d-d-d-d-c-a-a2. 从格图可直接得到状态转。