编码理论 第12章 卷积码的序列译码

编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院第十二章卷积码的序列译码有实用价值的卷积码译码算法编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院第1节堆叠（叠式）存贮算法•1、卷积码的马树•2、费诺量度•3、堆栈存储算法•4、堆栈存储算法举例•5、两类最大似然算法的比较•6、堆栈存储算法分析编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院1、卷积码的码树（1）:12.12135L],DD,1DD,1[1DG1mLkL2mLnNm,kn,22kl中码的码树示于图），，时的（信息序列长度为）（对于任何一条路径。总体上说都不同于其他形式，其中每一条路径树是篱笆图的一种展开元或级的路径。这个码个时间单树上包含的信息序列表示成微码个码字和长为的）（）的码长为便的方法是将（在讨论序列译码时，方编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院1、卷积码的码树（2）•图12.1L=5的(3,1,2)码的码树编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院1、卷积码的码树（3）算。合于理解序列译码的运会看到，树的形式更适重要的，但是，我们将样，意识到这一点是很笆图或状态图所含的一关吗的信息量恰好和篱示出，码树所包含的有中以粗线表相对应的码字在图例如，与信息序列来表示。路径在树上总体分为不同的个码字中每一个都通过的标示，且长为个输出支以于输入序列的每一个分个节点为终结点。相应右边的最因此称它是树梢，且称回全零状态时，且相当于编码器返入时，输个分支了。这表示在离开每个节点就只有一个时间单元后，中，树的分叉部分经过在图称作是树的分叉部分。个分支离开，这级中每个节点都有）码，在前。对于（态表编码器的起始状作是初始接点，并且代。树中最左边的接点称到个树级标以中将中，在图图此码的篱笆图已显示于12.110111u2NVin2.S0U1mL,...1LL,iL12.12Lm,k,nSmL01mL12.111.1klkl0ik0编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院1、卷积码的码树（4）度”的尺度。受序列和路径“接近程接联系的量度，此量度是路径取决于和此路径相望成为一部分最大似然希一个特定的路径是否有，求得最大似然路径。来搜索通过码树的节点）不需要检验太多的节点以一种有效的方法（即译码算法的目的是试图算法和费诺算法。序列算法，即的堆栈算法或讨论其中最常用的两种的本章，我们将相当详细有若干种树搜索算法。在序列译码的大标题下ZL编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院2、费诺量度（1）了歧变。近程度”的图形就产生与接受序列“接似然函数量度，则路径数径。若这些路径采用对都是很多不等长的路受检验的路径集合通常在任何译码步骤之后所，但在序列译码中，比较的路径都是等长的译码的任何一步上进行是最佳量度，因为在。对维特比算法来说这式的对数似然函数给定）有（，维特比算法中的量度元输出的对于二元输入，11.1DMCQ编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院2、费诺量度（2）累积起来。之间的附加距离更可能开头的路径与径远远比作为开头的路比特。换句话说，以加开头的整条路径只要求成以比特，而完附加开头来完成一条路径要以分最大似然路径。因为更可能是部要比径而，直觉告诉我们，路中“较好的”一个。然是两条路径这表明和）（部分路径量度是的部分路径量度。）（）和，，，，，（截短码字例如：条不同长度的路径。小的路径，现在比较两然路径，即一条量度最给定，他是最大似度值由的量径，维特比算法中一条路对我序列为传送，且接受一个码字经由的码树，假定此码中的研究图例r][vv][3]v[18]v[]v[]v[]v[,1)]v[],r[d(2]v[,]r[d]000]v[101100110001010111[v][v)d(r,)VBSC).011,101,100,110,001,010,010(rBSC12.112.1505050005505编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院2、费诺量度（3）对称的。就称是，若元输出的。一个二元输入，）式得出）和（。比较（量度加起来之后算得的比特的比特）是将该分支上的（个分支的分支量度给出，其中第）（由条分支的部分路径量度的前。一条路径的是码速率，）是信道输出符号概率（概率，）是心到转移（其中）（最佳量度是所用的，比较不同长度的路径元输出的入径的长度。对于二元输路考虑到进行比较的各条码中采用的量度，以便所以有必要调整序列译)4.12(,1,...,1,0),1|1()0|(DMCQ)3.12(,)(log)|(log)|v]|M([r12.212.1n|Mj)2.12(,)v|r(M)v|r(M]v|r[MlV]5[RrPv|rP)1.12(,R)p(r)v|r(Plogv|rMDMCQ1-nl021-nl021-l1nl0iii1-l0jjj1liiiiii2iiQjjQPjPnlRrPvrPvrijiijij编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院2、费诺量度（4）。路径的一部分即最可能是最大似然径。径被认为是“最佳”路时，具有费诺量度的路径度。当比较不等长的路还提出了一些另外的量称作是费诺译码。虽然此根据直观而引出的。因费诺）式的比特量度最早由然路径。（似因而更可以是部分最大们更接近于树的终点。路径有更大的偏置。他较短的）。因此较长的路径比和（因为度线性增加的正偏置，项表示一个随路径长比算法中的量度。第二）式中的第一项是维特（式简化为且和所有，对于）（即出符号也是等可能的，的对称信道，其信道输对于输入符号为等可能][]2[12.11R2Q12.5(12.5)R),Qnl(log)|(lognlRQ1nllog)|(log)|v]|M([r)3.12(i,101P21-nl0221-nl021-liijiijjvrPvrPQjQjr编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院3、费诺量度举例（1）了路径长度之差。诺量度中的偏置项反映费所取得的结果。因为在于应用维特比算法量度的“较好”者。这不同是两条路径中表明对于给定，和费诺量度由的和中截短码字），例（的对于转移概率为例505222202222505[v]63,.1)]v|[r(M92.2)v]|M([r10,.0p,2plog)p1(2log)3/11(3plog)p1(2log)]v|M([r12p2log)p1(16log)3/11(18p2log)p1(16log)v]|M([r]v[]v[12.12QBSCp12.2编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院3、费诺量度举例（2））所示的整数量度表。（图作为调整比例就得到于实现。本例中若以使其接近于整数值而便度。正常的数来调整这个量通常的实践中都用一个中所表示的量度表。在）（我们有图若若）（，和若例）（，若）（若）（，其比特量度是的一般，对于转移概率为b12.20.52/1a12.2,vr,,0.52vr,,2.65-v|rM0.10p1/3R12.312.6vr,,RP-12logvr,,R2Plogv|rMBSCPiiiiiiii2ii2ii编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院3、费诺量度举例（3）•图12.2R=1/3码和p=0.10的BSC的量度表编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院4、堆栈存储算法（1）终点时，算法结束。中的领先路径处于树的新安排堆栈。当存储器减小次序重个后继，且根据量度值路径，嵌入存储器中删去这个领先后从是领先路径的后续。然条新路径。这些新路径路径的量度上得到而后将这些加到领先存储器中的领先路径。个相继分支量度来扩展的径译码都通过计算顶部路量度减小次序列出每部径放在顶部。其他的按路量度。具有最大量度的元都含有一条路径及其有序表或堆栈。每一栈的路径的前面检验过的不同长度算法中，存储器中存有在堆栈存储或kkk222ZL编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院4、堆栈存储算法（2）二步。第就停机。否则，就转到领先路径处于树的终点第五步：若存储器中的器。储减小的次序重新安排存存储器中，并按量度值第四步：将新路径嵌入去领先路径。第三步：从存储器总删先路径后继的量度。第二步：计算存储器领作零。于存储器中，其量度取第一步：将树的原点置堆栈算法编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院4、堆栈存储算法（3）的译码步数。量粗略等于算法终止时故存储器的容）（部分通常远远大于尾部增加了。由于树的分叉再于树的尾部时就跟本不增加一，但当译码器处步，存储器的容量就要每译一）码，在树的分叉部分注意：对于（一个新的量度要计算。树的尾部，只有个新的量度要计算。在步上有在树的分叉部分，第一程图。存储算法的一个完整流中示出堆栈码路径。图中的领先路径就作为译当算法终止时，存储器,mLm,1,n212.3k编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院4、堆栈存储算法（4）•图12.3堆栈算法的流程图编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院5、堆栈存储算法举例（1）误概率。它不会影响译码器的错等时的取舍是任意的，相降低，但一般情况下，这将使总的译码数稍有路径置于顶部来决定。相等的情况将最长）相应。本例中量度值（它与信息序列译码路径是步后算法终止。最后的中，在第图的存树示于进行一步之后，存储器）整数量度表，算法每（应用图传送，且接收序列的码字通过一个的码树，假定此码中的中的考查将堆栈算法用于图例10111u,101,011)01,110,100(111,010,0v1012.4b12.2)011,101,100,110,001,010,010(rBSC0.10p3/1R12.112.4编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院5、堆栈存储算法举例（2）•图12.4例12.4中存储器的存数编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院6、两类最大似然算法的比较（1）。等于信道转移概率，在此情况下，它粗略中的错误概率是，则上传送的是位上都相同。假定实际而在其余位的不同有仅与中的特比算法。注意，例码在计算上常常优于维大太多时，序列译移概率的错误概率不比信道转受扰不太严重，即其中次计算，当接收序列只需要的接收序列，堆栈算法一些，但为译例杂译码或计算显得稍微复存储的次序，使每步的扩张之后必须重新按排算法在路径每次的篱笆图）。虽然堆栈次计算。（见图比算法需要维特的接收序列，译例选择等运算。因此，为每个状态都实行比较和的步骤或计算时对篱笆图后，维特比算法的译码的。当超出时间单元趣的步数进行比较是很有步数与维特比算法所需将堆栈算法所需的译码10.0p0.09521/2rv192vv12.4P1012.411.61512.4m编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院6、两类最大似然算法的比较（2））。（序列），它相应于，，，，，，（是法终止，最后译码路径步译码之后算中给出，存储器的存数在图算法在每进行一步之后），，，，，，（是相同，就假定接收序列码、信道和量度表与例例一另一个例子来说明。，情况则有所不同，这当接收序列受扰严重时10011u011101111011110010111v2012.5101101010111110110110r12.412.5编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院6、两类最大似然算法的比较（3）•图12.5例12.5中存贮器的存数编码理论第十二章卷积码的序列译码北京邮电大学信息工程学院6、两类最大似然算法的比较（4）码一样。概率本质上和维特比译定的码序列译码的错误给也不例外。因此，对于当接收