Turbo 码迭代译码 | Codeboy's Blog

形式陈述

给定Turbo 码的两台递归系统卷积分量编码器，译码器为每台 trellis 运行一次 soft-input soft-output BCJR/MAP 递推。对信息 bit $u_i$ ，分量译码器输出后验对数似然比

L_i^{\mathrm{APP}} =\log\frac{\Pr(u_i=0\mid\text{本分量全部观测与先验})} {\Pr(u_i=1\mid\text{本分量全部观测与先验})}.

它被分解为

L_i^{\mathrm{APP}} =L_i^{\mathrm{ch}}+L_i^{\mathrm a}+L_i^{\mathrm e},

其中 $L^{\mathrm{ch}}$ 是该系统 bit 的信道证据， $L^{\mathrm a}$ 是另一分量上轮提供的先验， $L^{\mathrm e}$ 是本 trellis 通过状态约束与 parity 观测新产生的 extrinsic 信息。只有 $L^{\mathrm e}$ 经 $\pi$ 或 $\pi^{-1}$ 后送往另一台译码器；传完整 APP 会把双方已经使用过的信道证据反复计数。

BCJR 对状态 $s$ 定义前向量 $\alpha_i(s)$ 、后向量 $\beta_i(s)$ 和分支度量 $\gamma_i(s',s)$ 。某 bit 值 $b$ 的未归一化后验由所有标记为 $b$ 的转移求和：

\Pr(u_i=b,\text{观测}) =\sum_{(s',s):u_i=b} \alpha_{i-1}(s')\gamma_i(s',s)\beta_i(s).

这里先固定已知初态与允许的终态集合，并把外来先验按各 bit 的概率乘积输入分量译码器。分支度量 $\gamma_i$ 是该转移的先验概率、系统观测似然及 parity 观测似然的乘积；不合法转移取零。前向与后向递推分别为

\alpha_i(s)=\sum_{s'}\alpha_{i-1}(s')\gamma_i(s',s), \qquad \beta_{i-1}(s')=\sum_s\gamma_i(s',s)\beta_i(s).

$\alpha_0$ 集中在已知初态， $\beta_K$ 是允许终态集合的指示函数；若终态不受限，就取全一。tail-biting 的首尾相等约束需要另行联合处理这些边界，不能任取独立的两端分布。上面的求和可按相同正数逐层缩放，最后的两种 bit 值之比不变。

一个完整外循环从零外在 LLR 开始，先运行第一台 SISO，再把其外在信息按 $\pi$ 送到第二台；第二台完成后按 $\pi^{-1}$ 送回。最大轮数与停止规则均是输入，结束时报告硬判决与停止状态。有限 LLR 下，可由 APP 减去本 bit 的先验和系统项得到外在量；遇到零概率或无穷值时，应在因子求和中直接去掉这两项，避免不定式相减。

单个 trellis 上这一步是相对于给定的乘积先验与边界条件的精确 MAP 边缘化；两个 trellis 经 interleaver 连接后形成有圈图，轮流运行 SISO 相当于在一般有限因子的 sum-product中把整个分量约束分组，再用 BCJR 高效计算这份因子到 bit 的消息，整体不等于一次全局 MAP 译码。

直觉

两个软输入软输出 trellis 通过交织和解交织往返交换外在 LLR — Turbo 译码的双 trellis 外在信息环

第一台译码器从原次序的状态连续性看信息序列，第二台从交织次序看同一组 bit。每台都把另一台尚未掌握的部分作为“新证据”送出，而把共同的系统观测扣除。初始时通常令 extrinsic 为零；经过若干轮，两个 trellis 对模糊 bit 的约束可能相互补强，后验绝对值增大。

这种交换依赖近似独立性。长交织器使两台 trellis 中的短局部邻域较少重叠，所以 extrinsic 更像来自新观测；迭代深入后消息仍会沿圈返回，不能继续假设完全独立。算法成功的经验图像是证据逐轮扩散，不是每轮都严格优化同一个凸目标。

例子与边界

LLR 分解可用 odds 精确核对。假设某 bit 的信道 odds 为 $2$ 、另一分量给出的先验 odds 为 $3$ ，本次 BCJR 汇总 trellis 与 parity 后得到 APP odds $18$ 。在分量采用的乘积先验与因子模型中，这两份本地 bit 因子可从 APP odds 中约去，传出的外在 odds 是

\frac{18}{2\cdot3}=3,

所以传出的 extrinsic LLR 为 $\log3$ ，而不是 $\log18$ 。若第二台把 $\log18$ 当新先验，它会再次乘入 odds $2$ 与旧先验 odds $3$ ，造成正反馈式过度自信。

实际 BCJR 应在 log 域计算以避免长块下的下溢。对有限 $a,b$ ，Log-MAP 使用

\log(e^a+e^b)=\max(a,b)+\log(1+e^{-|a-b|}),

零权重的对数记为 $-\infty$ ，合并两个零权重时应直接返回 $-\infty$ ，避免在校正项中形成不定式。Max-Log-MAP 则丢掉校正项；后者更便宜但不是精确 MAP。固定轮数后停止、硬判决连续若干轮不变、校验通过或 extrinsic 增益很小都是不同停止规则。迭代可能振荡、停在错误伪码字或在低重量结构上形成 error floor，不能把“多迭代”写成单调改善保证。

推论与应用

若分量 trellis 的状态数固定，一次前向—后向递推是 $O(K)$ ，完整迭代扫描两台 trellis 仍为 $O(K)$ ；总成本再乘迭代次数。交织/解交织只重排 LLR，但会制造非连续访存，硬件吞吐量常受存储冲突而非算术次数限制。

EXIT chart 把每个 SISO 模块的输入、输出互信息关系画成两条曲线，用“隧道”预测大交织极限下的收敛区域。它是 ensemble/独立性近似下的分析工具，不替代具体有限码的距离谱或错误率证明。工程实现还会缩放 extrinsic、裁剪 LLR 并采用 sliding schedule；每项近似都应与精确 BCJR 接口分开报告。

参考资料

Lalit R. Bahl, John Cocke, Frederick Jelinek, and Josef Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory 20(2), 1974, 284–287.
Claude Berrou and Alain Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,” IEEE Transactions on Communications 44(10), 1996, 1261–1271.
Stephan ten Brink, “Convergence Behavior of Iteratively Decoded Parallel Concatenated Codes,” IEEE Transactions on Communications 49(10), 2001, 1727–1737.

形式陈述 ​

形式陈述