卷积码译码

第五章卷积码的译码算法1Copyrightby周武旸第五章卷积码的译码算法卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi译码算法和BCJR译码算法。基于某种准则，这两种算法都是最优的。1967年，Viterbi提出了卷积码的Viterbi译码算法，后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路径问题的一个动态规划（DynamicProgramming）解决方案，随后，Forney证明它实际上是最大似然（ML，MaximumLikelihood）译码算法，即译码器选择输出的码字通常使接收序列的条件概率最大化。BCJR算法是1974年提出的，它实际上是最大后验概率（MAP，MaximumAPosterioriprobability）译码算法。这两种算法的最优化目标略有不同：在MAP译码算法中，信息比特错误概率是最小的，而在ML译码算法中，码字错误概率是最小的，但两种译码算法的性能在本质上是相同的。由于Viterbi算法实现更简单，因此在实际应用比较广泛，但在迭代译码应用中，例如逼近Shannon限的Turbo码，常使用BCJR算法。另外，在迭代译码应用中，还有一种Viterbi算法的变种：软输出Viterbi算法（SOVA，Soft-OutputViterbiAlgorithm），它是Hagenauer和Hoeher在1989年提出的。5.1Viterbi算法为了理解Viterbi译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非系统前馈编码器，其生成矩阵为：22()111DDDDDG（5.1）(0)v(1)vu(2)v（a）第五章卷积码的译码算法2Copyrightby周武旸0S2S3S000012345671S0S0S0S0S0000S0S0S0000000000000001S3S0013S3S0011S1S1S2S2S2S2S001111111111111111011011011011011100100100010010010010110110110110101101101101101时间单元（b）图5.1（a）（3，1，2）编码器（b）网格图（h＝5）假定信息序列长度为h＝5，则网格图包含有h＋m＋1＝8个时间单元，用0到h＋m＝7来标识，如图5.1（b）所示。假设编码器总是从全0态S0开始，又回到全0态，前m＝2个时间单元对应于编码器开始从S0“启程”，最后m＝2个时间单元对应于向S0“返航”。从图中我们也可以看到，在前m个时间单元或最后m个时间单元，并不是所有状态都会出现，但在网格图的中央部分，在每个时间单元都会包含所有状态，且在每个状态都有2k＝2个分支离开和到达。离开每个状态的上面分支表示输入比特为1（即ui＝1，i表示第i个时间单元），下面的分支表示输入比特为0。每个分支的输出vi由n个比特组成，共有2h＝32个码字，每个码字都可用网格图中的唯一路径表示，码字长度N＝n(h＋m)＝21。例如当信息序列为u＝（11101）时，对应的码字如图5.1（b）中红线所示，v＝（111，010，001，110，100，101，011）。在一般的（n，k，v）编码器情况下，信息序列长度K*=kh，离开和进入每个状态都有2k个分支，有*2K个不同路径通过网格图，对应着*2K个码字。假设长度*Kkh的信息序列011(,)huuuu被编码成长度为()Nnhm的码字011(,)hmvvvv，在经过一个二进制输入、Q-ary输出的离散无记忆信道（DMC，DiscretememorylessChannel）后，接收序列为011(,)hmrrrr。也可表示为：01*1(,)Kuuuu，011(,)Nvvvv，011(,)Nrrrr，译码器对接收到的序列r进行处理，得到v的估计ˆv。在离散无记忆信道情况下，最大似然译码器是按照最大化对数似然函数log(|)Prv作为选择ˆv的准则。因为对于DMC，1100(|)(|)(|)hmNllllllPPPrvrvrv（5.2）两边取对数后为：第五章卷积码的译码算法3Copyrightby周武旸1100log(|)(|)(|)hmNllllllPPPrvrvrv（5.3）其中(|)llPrv是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。对数似然函数log(|)Prv，用(|)Mrv表示，称为路径度量（pathmetric）；(|)llPrv，称为分支度量（branchmetric），用(|)llMrv表示；(|)llPrv称为比特度量（bitmetric），用(|)llMrv表示，这样（5.3）式可写为：1100(|)(|)(|)hmNllllllMMMrvrvrv（5.4）如果我们只考虑前t个分支，则部分路径度量可表示为：1100(|)(|)(|)tntllllllMMMrvrvrv（5.5）对于接收序列r，Viterbi算法就是通过网格图找到具有最大度量的路径，即最大似然路径（码字）。在每个时间单元的每个状态，都增加2k个分支度量到以前存储的路径度量中（加）；然后对进入每个状态的所有2k个路径度量进行比较（比），选择具有最大度量的路径（选），最后存储每个状态的幸存路径及其度量。Viterbi算法：Step1:Step1：在t＝m时间单元开始，计算进入每个状态的单个路径的部分度量，存储每个状态的路径（幸存）及其度量；Step2:tt＋1，对进入每个状态的所有2k个路径计算部分度量，并加上前一时间单元的度量。对于每个状态，比较进入该状态的所有2k个路径度量，选择具有最大度量的路径，存储其度量，并删掉其他路径。Step3:如果th+m，返回step2；否则，就停止。Viterbi算法的基本计算“加、比、选”体现在step2。注：实际工程中，在每个状态存储（在step1和step2）的是对应于幸存路径的信息序列，而不是幸存路径自身，这样当算法结束时，就无需再通过估计码字ˆv来恢复信息序列ˆu。从时间单元m到随后的h个时间单元，共有开始2v个幸存路径，每个状态（共有2v个状态）一个。随后，幸存路径数就会变少，因为当编码器回到全0态时，状态数就会变少。最后，在时间单元h＋m，就只有一个状态（即全0态），因此，也就只有一个幸存路径了，算法中止。现在我们证明最后的幸存者是最大似然路径。定理5.1：在Viterbi算法中最后的幸存者ˆv是最大似然路径，即ˆˆ(|)(|),MMforrvrvvv（5.6）从实现的角度看，用正整数度量来表示要比用实际的比特度量表示更方便。比特度量(|)log(|)llllMrvPrv可用21log(|)llcPrvc来代替，其中c1是任意实数，c2是任意第五章卷积码的译码算法4Copyrightby周武旸正实数。可证明，如果路径v最大化1100(|)(|)log(|)NNllllllMMrvPrvrv，则它也最大化21log(|)llcPrvc，因此可以使用修正的度量，且不影响Viterbi算法的性能。如果选择c1使最小度量为0，则c2可选择为使所有度量近似为整数。这样，由于用整数来近似表示度量，Viterbi算法的性能变成了次最优算法，但通过选择c1和c2可使得这种性能降低非常小。＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝例5.1：对于二输入、4-ary输出的DMC信道下的Viterbi算法二输入、4-ary输出的DMC如图5.2所示。该信道的比特度量如图5.3（a）所示（按照底为10的对数计算），选择c1＝1，c2＝17.3，得到整数度量表如图5.3（b）所示。0.40.40.20.30.10.30.20.10101021112图5.2二输入、4-ary输出DMC信道模型lrlv010211120-0.41-0.52-0.7-1.0-1.0-0.7-0.52-0.4lrlv010211120101850(a)(b)05810图5.3度量表假设图5.1中的一个码字在这样的信道中传输，接收到的序列为：r＝（111201，111102，111101，111111，011201，120211，120111）(5.7)对该序列进行Viterbi译码如图5.4所示。第五章卷积码的译码算法5Copyrightby周武旸0S2S3S0001S0S0S0S0S0000S0S0S0000000000000001S3S0013S3S0011S1S1S2S2S2S2S001111111111111111011011011011011100100100010010010010110110110110101101101101101r＝（111201，111102，111101，111111，011201，120211，120111）18366070104403315234386111124139536676808895121图5.4DMC信道下的Viterbi算法每个状态上的数字表示幸存路径的度量，另一个路径就将被删除（绿线部分）。这样最后的码字（红线部分的输出）判决为：ˆ(111,010,110,011,000,000,000)v（5.8）它对应的输入序列为ˆ(11000)u。注意：网格图中最后的m＝2个分支是清空寄存器的，不能算作为输入信息序列。＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝在BSC信道情况下，转移概率为p1/2，接收序列r是2-ary输出的，此时对数似然函数为（在第一章的时候推导过1(,)(,)0(|)(|)(1)NNddlllPPrvpprvrvrv）：log(|)(,)loglog(1)1pPdNpprvrv（5.9）其中(,)drv是r和v之间的Hamming距离。由于log01pp，且log(1)Np对所有v来说都是一个常数，因此最大似然译码（maxlog(|)Prv）就是最小化Hamming距离（min(,)drv）。1100(,)(,)(,)hmNlllllldddrvrvrv（5.10）第五章卷积码的译码算法6Copyrightby周武旸因此，当我们将Viterbi算法应用到BSC信道时，(,)lldrv成为分支度量，(,)lldrv为比特度量，该算法就是寻找具有最小度量的路径，即与r汉明距离最近的路径。该算法运算仍然相同，只是用Hamming距离代替了似然函数作为度量，在每个状态的幸存路径是具有最小度量的路径。＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝例5.2：BSC信道下的Viterbi算法假设接收到的序列为(110,110,110,111,010,101,101)r（5.10）0S2S3S0001S0S0S0S0S0000S0S0S0000000000000001S3S0013S3S0011S1S1S2S2S2S2S001111111111111111011011011011011100100100010010010010110110110110101101101101101r＝（110，110，110，111，010，101，101）124643324534674245755图5.5BSC信道下的Viterbi算法最后的码字判决为：ˆ(111,010,110,011,111,101,011)v（5.11）它所对应的信息序列为ˆ(11001)u。最后的幸存路径度量值为7，表示接收序列和判决码字之间有7个对应位置不同，而其他路径所对应的码字和接收序列之间的位置不同数目都要大于7。在上图中紫色对应的线表示两条路径度量值相同，此时随便选其中一条就OK了。＝＝＝＝＝＝＝＝＝＝＝＝＝＝