卷积码的维特比译码

《卷积码的维特比译码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、卷积码的维特比译码卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi译码算法和BCJR译码算法。基于某种准则，这两种算法都是最优的。1967年，Viterbi提出了卷积码的Viterbi译码算法，后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路径问题的一个动态规划（DynamicProgramming）解决方案，随后，Forney证明它实际上是最大似然（ML，MaximumLikelihood）译码算法，即译码器选择输出的码字通常使接收序列的条件概率最大化。BCJR算法是1974年提出的，它实际

2、上是最大后验概率（MAP，MaximumAPosterioriprobability）译码算法。这两种算法的最优化目标略有不同：在MAP译码算法中，信息比特错误概率是最小的，而在ML译码算法中，码字错误概率是最小的，但两种译码算法的性能在本质上是相同的。由于Viterbi算法实现更简单，因此在实际应用比较广泛，但在迭代译码应用中，例如逼近Shannon限的Turbo码，常使用BCJR算法。另外，在迭代译码应用中，还有一种Viterbi算法的变种：软输出Viterbi算法（SOVA，Soft-OutputViterbiAlgorithm）

3、，它是Hagenauer和Hoeher在1989年提出的。为了理解Viterbi译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非系统前馈编码器，其生成矩阵为：GD=[1+D1+D21+D+D2]（1）图1（a）（3，1，2）编码器（b）网格图（h＝5）假定信息序列长度为h＝5，则网格图包含有h＋m＋1＝8个时间单元，用0到h＋m＝7来标识，如图1（b）所示。假设编码器总是从全0态S0开始，又回到全0态，前m＝2个时间单元对应于编码器开始从S0

4、“启程”，最后m＝2个时间单元对应于向S0“返航”。从图中我们也可以看到，在前m个时间单元或最后m个时间单元，并不是所有状态都会出现，但在网格图的中央部分，在每个时间单元都会包含所有状态，且在每个状态都有2k＝2个分支离开和到达。离开每个状态的上面分支表示输入比特为1（即ui＝1，i表示第i个时间单元），下面的分支表示输入比特为0。每个分支的输出vi由n个比特组成，共有2h＝32个码字，每个码字都可用网格图中的唯一路径表示，码字长度N＝n(h＋m)＝21。例如当信息序列为u＝（11101）时，对应的码字如图1（b）中红线所示，v＝（11

5、1，010，001，110，100，101，011）。在一般的（n，k，v）编码器情况下，信息序列长度K*=kh，离开和进入每个状态都有2k个分支，有2K*个不同路径通过网格图，对应着2K*个码字。假设长度K*=kh的信息序列u=(u0,u1uh-1)被编码成长度为N=n(h+m)的码字v=(v0,v1vh+m+1)，在经过一个二进制输入、Q-ary输出的离散无记忆信道（DMC，DiscreteMemorylessChannel）后，接收序列为r=(r0,r1rh+m+1)。也可表示为：u=(u0,u1uK*-1)，v=(v0,v1vN

6、-1)，r=(r0,r1rN-1)，译码器对接收到的序列r进行处理，得到v的估计v。在离散无记忆信道情况下，最大似然译码器是按照最大化对数似然函数logP(r

7、v)作为选择v的准则。因为对于DMC，Prv=l=0h+m-1Prlvl=l=0N-1Prlvl（2）两边取对数后为：logPrv=l=0h+m-1logPrlvl=l=0N-1logPrlvl（3）其中P(rl

8、vl)是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。对数似然函数logP(r

9、v)，用M(r

10、v)表示，称为路径度量（pathmetric）；logP(

11、rl

12、vl)，称为分支度量（branchmetric），用M(rl

13、vl)表示；logP(rl

14、vl)称为比特度量（bitmetric），用M(rl

15、vl)表示，这样（3）式可写为：M(r

16、v)=l=0h+m-1M(rl

17、vl)=l=0N-1M(rl

18、vl)（4）如果我们只考虑前t个分支，则部分路径度量可表示为：M(r

19、v)=l=0t-1M(rl

20、vl)=l=0nt-1M(rl

21、vl)（5）对于接收序列r，Viterbi算法就是通过网格图找到具有最大度量的路径，即最大似然路径（码字）。在每个时间单元的每个状态，都增加2k个分支度量到以前

22、存储的路径度量中（加）；然后对进入每个状态的所有2k个路径度量进行比较（比），选择具有最大度量的路径（选），最后存储每个状态的幸存路径及其度量。Viterbi算法：Step1:在t＝m时间单元开始，计算进入