卷积码维特比译码.docx

卷积码的维特比译码卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi 译码算法和 BCJR 译码算法。基于某种准则，这两种算法都是最优的。1967 年，Viterbi 提出了卷积码的 Viterbi 译码算法，后来 Omura 证明 Viterbi 译码算法等效于在加权图中寻找最优路径问题的一个动态规划（Dynamic Programming）解决方案，随后，Forney 证明它实际上是最大似然（ML，Maximum Likelihood）译码算法，即译码器选择输出的码字通常使接收序列的条件概率最大化。BCJR 算法是 1974 年提出的，它实际上是最大后验概率（MAP，Maximum A Posteriori probability）译码算法。这两种算法的最优化目标略有不同：在 MAP 译码算法中，信息比特错误概率是最小的，而在 ML 译码算法中，码字错误概率是最小的，但两种译码算法的性能在本质上是相同的。由于 Viterbi 算法实现更简单，因此在实际应用比较广泛，但在迭代译码应用中，例如逼近 Shannon 限的 Turbo 码，常使用 BCJR 算法。另外，在迭代译码应用中，还有一种 Viterbi 算法的变种：软输出 Viterbi 算法（SOVA，Soft-Output Viterbi Algorithm），它是 Hagenauer 和 Hoeher 在 1989 年提出的。为了理解 Viterbi 译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非系统前馈编码器，其生成矩阵为：（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“启程”，最后 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＝（111，010，001， 110，100，101，011）。在一般的（n，k，v）编码器情况下，信息序列长度 K*=kh，离开和进入每个状态都有 2k 个分支，有2K* 个不同路径通过网格图，对应着2K* 个码字。假设长度K*=kh的信息序列u=(u0,u1 uh-1) 被编码成长度为 N=n(h+m) 的码字v=(v0, v1 vh+m+1) ，在经过一个二进制输入、Q-ary 输出的离散无记忆信道（DMC， Discrete Memoryless Channel ）后，接收序列为r=(r0 ,r1 rh+m+1)。也可表示为： u=(u0 ,u1 uK*-1) ，v=(v0 ,v1 vN-1)，r=(r0,r1 rN-1)，译码器对接收到的序列r进行处理，得到 v 的估计。在离散无记忆信道情况下，最大似然译码器是按照最大化对数似然函数log P(r | v) 作为选择的准则。因为对于 DMC，（2）两边取对数后为：（3）其中P(rl | vl )是信道转移概率，当所有码字等概时，这是个最小错误概率译码准则。对数似然函数 log P(r | v) ，用 M(r |v )表示，称为路径度量（path metric）；log P(rl | vl ) ，称为分支度量（branch metric），用M(rl | vl ) 表示；log P(rl | vl ) 称为比特度量（bit metric），用M(rl | vl )表示，这样（3）式可写为：（4）如果我们只考虑前 t 个分支，则部分路径度量可表示为：（5）对于接收序列r，Viterbi 算法就是通过网格图找到具有最大度量的路径，即最大似然路径（码字）。在每个时间单元的每个状态，都增加2k个分支度量到以前存储的路径度量中（加）；然后对进入每个状态的所有 2k 个路径度量进行比较（比），选择具有最大度量的路径（选），最后存储每个状态的幸存路径及其度量。Viterbi 算法：Step 1:在 t＝m 时间单元开始，计算进入每个状