第五章 卷积码的译码算法 for presention.pdf

第五章 卷积码的译码算法 第五章 卷积码的译码算法 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法： 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 ）非系统前馈编码器，其生成矩阵为： 1 Copyright by 周武旸 第五章 卷积码的译码算法 G(D ) 1D 1D2 1D D2    （5.1） (0) v (1) u v (2) v （a ） 001 001 001 S S S S 3 3 3 3 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 S1 S1 1 S1 1 S1 1 S1 1 1 0 0 0