第五章卷积码的译码算法.PDFVIP

第五章 卷积码的译码算法 第五章 卷积码的译码算法 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：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 年提出的。 5.1 Viterbi 算法 为了理解 Viterbi 译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反 映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非 系统前馈编码器，其生成矩阵为： 22 G()D=+???? 1 D 1 + D 1 ++ DD （5.1） v(0) u v(1) v(2) （a） 1 Copyright by 周武旸 第五章 卷积码的译码算法 S 001 S 001 S 001 S 3 110 3 110 3 110 3 110 010 010 010 010 101 101 101 101 S1 101 S1 S1 S1 S1 100 100 100 S2 S2 S2 S2 S2 011 011 011 011 011 111