第八讲——卷积码的译码---.ppt

第八讲,卷积码的译码,回顾,卷积码是对信息流进行编码的一种有记忆分组的编码方法记忆有很多种，典型的为线性有限记忆和线性无限记忆当记忆为线性时，等效于输入信息流与冲激响应之间的卷积可分别用FIR和IIR滤波器来描述矩阵描述、树图描述和网格图表示,卷积码的概率译码,概率译码：结合信道符号统计特性的译码方法一种简单的译码方法：逐分支译码在码树图中每向前走一步，在决定走哪一个分支时根据该分支子码与该时刻接收子码之间的相似程度来判断,逐分支译码举例,编码符号为1时发+1，编码符号为0时发-1当接收符号为：0.8,0.7,-0.2,-0.3,0.5,-0.3时，尽管第二次分支为两个负数，但更象分支“1”，因此判信息序列为110,逐分支译码的局限,没有利用卷积码的记忆性例：当接收符号为：0.8,0.7,-0.2,0.1,0.5,-0.3时，判信息序列为101但从整体序列来看，更像110因此不是最大似然序列译码,译码准则：对数似然度量,logP(R|C)=logiP(ri|ci)=ilog(p(ri|ci)当在码树中沿正确路径行进时，对数度量的整体趋势呈线性变化。当在码树中沿完全错误（随机）路径行进时，对数度量的整体趋势也呈线性变化，但斜率要低于正确路径。,对数似然度量图示,正确路径与随机路径,正确路径与错误路径,由于信道干扰的原因，错误路径并不总是比正确路径的度量低，但一般情况下沿错误路径走下去总会导致度量的下降,局部错误,不过由于卷积码的记忆有限，可能会出现一条错误路径最终与正确路径会合的情况，这样就会出现一段局部错误,译码错误,当由于度量的起伏造成将局部错误的路径看成正确路径时，就发生误码。,对译码算法的要求,能以很大概率发现当前走在错误路径上能以很大概率回到正确路径运算量和存贮量要适中,费诺度量,为便于译码，要求正确路径的度量变化斜率大于0，而错误路径的度量变化斜率要小于0，因此要对分支度量加以调整同样也是为了不同长度的路径能进行比较费诺度量：二进制输入的DMC信道：log(p(ri|ci)/p(ri)-Rc,局部错误与判断门限,对卷积码来说，一般比较容易出现的错误都是较小的码距，而较小码距的差错图案一般都是集中在一些序列段中，即由一些局部错误组成。序列译码就是要尽早发现这些局部错误，因为过了这些局部错误之后两个序列的内容就相同了，因此后面的斜率也是相同的。局部错误在路径度量变化中的体现应是一段下垂后继续按正确斜率上升。因此要随时调整判断门限。,费诺算法,费诺算法的几种情形,在向前试探时，如果发现度量值大于当前门限，则向前移动到所试探的节点；如果这次试探是第一次，则可将门限作一定的提高；如果不是第一次，说明曾因门限太高而倒退过，因此不提高门限，以便后面的比较,费诺算法的另一些情形,向前试探时，如果发现度量小于当前门限，说明比试探节点还要坏的节点度量更不可能超过门限，因此在此节点上不必再向前试探下去，而应考虑向回作反向试探。如果反向试探结果是也小于门限，说明当前门限太高需要降低门限，再作向前试探；如果反向试探结果大于门限，说明反向试探节点度量门限前向试探节点，因此应考虑从反向试探节点另一个方向衍生一个试探节点，因此要回到反向试探节点，以便向前观察下一个最佳节点。,先找一个最佳节点,大于门限，则前进并提高门限,再向前找一个最佳节点,大于门限，则前进并提高门限,再向前找一个最佳节点,小于门限,堆栈算法,核心：存贮一组可能的路径，但每次只对当时认为的最佳路径进行延伸，然后再重新排序。从码树图起始节点开始将堆栈第一行中路径向各分支延伸，计算新度量删去第一行原存贮内容将延伸后的各路径在堆栈中重新排序，找出度量量大的路径放在第一行若第一行中的路径已达码树终点，则结束，否则回到步骤2,堆栈算法的本质,存贮一组可能路径每次只有最可能的（度量最大的）路径可以繁衍，同时删去父路径繁衍出的子路径与其它未繁衍的路径一起排序堆栈满时最坏路径被丢弃,序列译码的特点,运算量与信道质量有关需要输入缓冲器，其长度也与信道质量有关，有溢出现象计算量与约束长度无关,维特比译码,卷积码的网格图描述：将状态转移图按时间展开，用于描述从第k时刻的编码器状态到第k+1时刻的编码状态的转移情况，以及在转移过程中的输出情况。,有限状态编码的最大似然译码,当编码器的状态数有限时，不同编码路径必然会有会合的情况。例：一个信息长度为L的编码，所有可能路径数为2L个，而对于一个4状态码而言，任一时刻路径只能经过4个状态，因此大量的路径（当用状态转移来描述时）是有重合的。由于码的马氏特性，从某一时刻开始的后续编码只与该时刻的状态有关，而与之前如何到达该状态无关。,分段译码与残留路径,一个长度为L的码，在时刻k分为两段，之前的称为A，之后的称为B。最大似然序列必存在于从k时刻的M个状态出发（或在时刻k经过M个状态的）的M*2L-k条路径之中。而第k时刻到达每个状态都有2k/M条A路径，显然，从第k时刻状态S出发的最佳路径的前半段必然是到达该状态的2k/M条A路径中的最佳A路径。称此最佳A路径为第k时刻状态S的残留路径。,推广到每时刻一段,