Turbo码——与LDPC并称的现代编码双雄，我用C语言实现了迭代译码

作者：绳匠_ZZ0

从卷积码到Turbo码，我在交织器的魔法中看到了香农极限的影子

前言：Turbo码——一个诺基亚手机里走出的革命

1993年，两位法国学者Berrou和Glavieux在国际通信会议上提出了一种全新的信道编码方案，它的性能如此惊人，以至于很多人不敢相信。他们把它命名为Turbo码——Turbo这个词来自涡轮增压，寓意着这种编码像涡轮一样，通过反复“增压”信息，逼近香农极限。

Turbo码的出现，标志着信道编码领域进入了一个新时代。如今，它被广泛应用于3G/4G移动通信（UMTS、LTE）、深空通信、卫星通信等领域。与LDPC码并称为现代编码双雄。

在这篇文章中，我将从通信工程学生的视角，带你理解Turbo码的核心思想，并用C语言实现一个简化的Turbo编码器和迭代译码器（Log-MAP算法）。虽然是简化版，但足以让你感受“涡轮”的魔力。

一、Turbo码的直觉：两个码轮流给你“提建议”

1.1 为什么需要Turbo？

我们之前学过的卷积码，性能还不错，但离香农极限还有差距。LDPC码通过稀疏校验矩阵和迭代译码逼近了极限。而Turbo码走了另一条路：并行级联。

基本思想很简单：

• 把原始信息比特分成两路（或更多）。

• 第一路直接送入一个卷积编码器。

• 第二路先经过一个交织器（把比特顺序打乱），再送入另一个卷积编码器。

• 两个编码器的输出加上原始信息，一起发送。

接收端有两个对应的译码器，它们互相交换信息（软信息），经过多次迭代，性能大幅提升。

1.2 交织器的魔法

交织器是Turbo码的灵魂。它把信息比特的顺序打乱，这样如果信道突发错误影响了第一路，第二路因为顺序被打乱，错误就被“分散”了。两个译码器看到的错误模式不同，它们可以互相纠正。

想象两个人从不同角度观察同一个场景，然后讨论，最终得出更准确的结论。这就是Turbo译码的本质。

二、Turbo码结构：并行级联卷积码（PCCC）

最常见的Turbo码结构是并行级联卷积码（Parallel Concatenated Convolutional Code, PCCC）。它由两个相同的卷积码编码器组成，中间通过一个交织器连接。

发送的码字由三部分组成：[u, p1, p2]。码率一般为1/3（因为每1个信息比特产生2个校验比特）。如果需要更高码率，可以打孔（删除部分校验比特）。

三、Turbo译码：迭代的软输入软输出

3.1 软输入软输出（SISO）译码器

Turbo译码的核心是软输入软输出（Soft-Input Soft-Output, SISO）译码器。它接收软信息（LLR），输出软信息。常用的SISO算法是Log-MAP（最大后验概率的对数域实现）。

两个SISO译码器（对应两个编码器）交换“外信息”（extrinsic information）。外信息是某个译码器对信息比特的“新看法”，传递给另一个译码器作为先验信息。

3.2 迭代过程图示

3.3 Log-MAP算法简介

Log-MAP算法是在网格图上进行的，它计算每个状态和时刻的前向度量、后向度量，然后得到每个比特的后验LLR。公式如下（不要求完全记住，但理解思想）：

L(uk)=max⁡s,s′∗(αk−1(s′)+γk(s′,s)+βk(s))−max⁡s,s′∗(αk−1(s′)+γk(s′,s)+βk(s))L(uk​)=s,s′max∗​(αk−1​(s′)+γk​(s′,s)+βk​(s))−s,s′max∗​(αk−1​(s′)+γk​(s′,s)+βk​(s))

其中，max⁡∗max∗ 是修正的max操作：max⁡∗(x,y)=max⁡(x,y)+ln⁡(1+e−∣x−y∣)max∗(x,y)=max(x,y)+ln(1+e−∣x−y∣)。

听起来复杂，但代码实现有固定模式。我们下面会给出简化的实现。

四、C语言实现：一个简化的Turbo码

为了让你快速上手，我们选择一个非常小的Turbo码：

• 两个相同的卷积码：递归系统卷积码（RSC），生成多项式(1, 5/7)八进制，即反馈多项式7，前向多项式5。

• 约束长度：K=3（记忆深度2），状态数4。

• 交织器：简单的块交织器（给定长度，将索引映射到另一个位置）。

• 码率：1/3（无打孔）。

4.1 定义RSC编码器结构

首先实现一个RSC编码器，它可以输出系统比特和校验比特。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define K 3 // 约束长度 #define NUM_STATES (1 << (K-1)) // 4个状态 #define MAX_ITER 8 // 最大迭代次数 // RSC编码器参数: 反馈多项式7(111), 前向多项式5(101) int rsc_next_state[NUM_STATES][2] = { {0, 2}, // 状态00: 输入0->00, 输入1->10 {0, 2}, // 状态01 {1, 3}, // 状态10 {1, 3} // 状态11 }; int rsc_output_parity[NUM_STATES][2] = { {0, 1}, // 状态00: 输入0输出0, 输入1输出1 {1, 0}, // 状态01 {1, 0}, // 状态10 {0, 1} // 状态11 }; // 编码函数示例 void turbo_encode(int* input, int* output, int length) { int state1 = 0, state2 = 0; for(int i=0; i<length; i++) { // 第一个RSC编码器 int sys_bit = input[i]; int p1 = rsc_output_parity[state1][sys_bit]; state1 = rsc_next_state[state1][sys_bit]; // 第二个RSC编码器（使用交织后的输入） int interleaved_bit = input[(i*13) % length]; // 简单交织示例 int p2 = rsc_output_parity[state2][interleaved_bit]; state2 = rsc_next_state[state2][interleaved_bit]; // 输出系统位和两个校验位 output[3*i] = sys_bit; output[3*i+1] = p1; output[3*i+2] = p2; } } // BCJR译码算法框架（简化版） void bcjr_decode(float* received, float* llr_out, int length) { // 这里应实现前向/后向概率计算 // 简化示例仅做占位 for(int i=0; i<length; i++) { llr_out[i] = received[i] > 0 ? 1.0 : -1.0; // 简单硬判决 } } // Turbo译码主函数 void turbo_decode(float* received, int* decoded, int length) { float llr1[length], llr2[length], extrinsic[length]; for(int iter=0; iter<MAX_ITER; iter++) { // 第一个分量译码器 bcjr_decode(received, llr1, length); // 交织/解交织处理 for(int i=0; i<length; i++) { extrinsic[i] = llr1[i] - received[i]; // 计算外信息 llr2[(i*13)%length] = extrinsic[i]; // 交织 } // 第二个分量译码器 bcjr_decode(llr2, llr2, length); // 更新外信息 for(int i=0; i<length; i++) { extrinsic[(i*13)%length] = llr2[i] - llr1[i]; // 解交织 } } // 最终判决 for(int i=0; i<length; i++) { decoded[i] = llr1[i] > 0 ? 1 : 0; } } int main() { int input[] = {1,0,1,1,0,0,1,0}; int encoded[24]; // 8*3 int decoded[8]; float received[24]; turbo_encode(input, encoded, 8); // 模拟信道添加噪声 for(int i=0; i<24; i++) { received[i] = encoded[i] ? 0.8f : -0.8f; received[i] += (float)rand()/RAND_MAX*0.4-0.2; // 添加噪声 } turbo_decode(received, decoded, 8); printf("解码结果:"); for(int i=0; i<8; i++) printf("%d ", decoded[i]); return 0; }

考虑到篇幅和清晰度，我决定采用一个更简单的非递归系统卷积码作为编码器，重点演示Turbo译码的迭代流程。因为算法核心在于SISO译码器的迭代交换外信息，编码器可以暂时简化。

我们使用之前文章中的卷积码（约束长度3，生成多项式7和5）但改为系统形式：输出包含输入比特和两个校验比特。

实际上，标准Turbo码使用的是RSC，但初学者可以先理解迭代结构。

4.2 简化的SISO译码器（Log-MAP）

为了让你能运行，我提供一个基于网格的Log-MAP译码器（针对非递归系统卷积码），但经过调整可以处理Turbo码需要的软输入软输出。

由于完整的Log-MAP实现代码量较大（约200行），我将在下面给出核心框架，并解释关键步骤。

#define N 100 // 信息比特长度（帧长） double gamma[2][NUM_STATES][NUM_STATES]; // 分支度量 double alpha[N+1][NUM_STATES]; // 前向状态度量 double beta[N+1][NUM_STATES]; // 后向状态度量 double LLR[N]; // 后验LLR输出 void log_map_decode(double *recv_sys, double *recv_par, double *llr_a, double *llr_e, int len) { // 初始化alpha和beta矩阵 for (int state = 0; state < NUM_STATES; state++) { alpha[0][state] = (state == 0) ? 0.0 : -INF; // 初始状态为全零 beta[len][state] = (state == 0) ? 0.0 : -INF; // 终止状态为全零 } for (int t = 0; t < len; t++) { for (int s = 0; s < NUM_STATES; s++) { for (int bit = 0; bit < 2; bit++) { int s_next = next_state[s][bit]; double gamma = 0.5 * (bit * llr_a[t] + recv_sys[t] + bit * recv_par[t]); alpha[t+1][s_next] = max_star(alpha[t+1][s_next], alpha[t][s] + gamma); } } } for (int t = len-1; t >= 0; t--) { for (int s = 0; s < NUM_STATES; s++) { for (int bit = 0; bit < 2; bit++) { int s_prev = prev_state[s][bit]; double gamma = 0.5 * (bit * llr_a[t] + recv_sys[t] + bit * recv_par[t]); beta[t][s_prev] = max_star(beta[t][s_prev], beta[t+1][s] + gamma); } } } for (int t = 0; t < len; t++) { double sum0 = -INF, sum1 = -INF; for (int s = 0; s < NUM_STATES; s++) { for (int bit = 0; bit < 2; bit++) { int s_next = next_state[s][bit]; double gamma = 0.5 * (bit * llr_a[t] + recv_sys[t] + bit * recv_par[t]); double metric = alpha[t][s] + gamma + beta[t+1][s_next]; (bit == 0) ? (sum0 = max_star(sum0, metric)) : (sum1 = max_star(sum1, metric)); } } LLR[t] = sum1 - sum0; llr_e[t] = LLR[t] - llr_a[t] - recv_sys[t]; // 外信息提取 } // 第一次迭代 log_map_decode(recv_sys1, recv_par1, priori_llr, extrinsic_llr, N); // 第二次迭代（交织后） log_map_decode(recv_sys2, recv_par2, interleave(extrinsic_llr), new_extrinsic, N);

4.3 Turbo迭代译码主循环

现在，我们可以将两个相同的SISO译码器通过交织/解交织连接起来。

c int interleaver[N]; // 交织映射表 int deinterleaver[N]; // 解交织映射表 void init_interleaver(int len) { // 简单的块交织：将索引i映射到(i * 13) % len for (int i = 0; i < len; i++) { interleaver[i] = (i * 13) % len; deinterleaver[interleaver[i]] = i; } } void turbo_decode(double *recv_sys, double *recv_par1, double *recv_par2, int len, int *decoded_bits) { double llr_a1[N] = {0}; // 译码器1的先验信息（初始为0） double llr_a2[N] = {0}; double llr_e1[N] = {0}; // 译码器1的外信息 double llr_e2[N] = {0}; double interleaved[N], deinterleaved[N]; for (int iter = 0; iter < MAX_ITER; iter++) { // 译码器1 log_map_decode(recv_sys, recv_par1, llr_a1, llr_e1, len); // 将llr_e1交织后作为译码器2的先验 for (int i = 0; i < len; i++) interleaved[i] = llr_e1[interleaver[i]]; // 译码器2（注意接收的校验比特是recv_par2，系统比特需要同样交织） double recv_sys_interleaved[N]; for (int i = 0; i < len; i++) recv_sys_interleaved[i] = recv_sys[interleaver[i]]; log_map_decode(recv_sys_interleaved, recv_par2, interleaved, llr_e2, len); // 解交织llr_e2作为下一轮译码器1的先验 for (int i = 0; i < len; i++) deinterleaved[i] = llr_e2[deinterleaver[i]]; memcpy(llr_a1, deinterleaved, len * sizeof(double)); } // 最终硬判决：使用最后一次的后验LLR（这里简化，直接使用译码器1的LLR） for (int i = 0; i < len; i++) { decoded_bits[i] = (LLR[i] > 0) ? 0 : 1; } }

4.4 主函数测试

由于完整的Log-MAP实现较长，我们这里提供一个概念验证的简化测试：用随机比特模拟编码和加噪，调用Turbo译码，验证能否纠正错误。

c int main() { int len = 100; init_interleaver(len); // 生成随机信息比特 int info[len]; for (int i = 0; i < len; i++) info[i] = rand() % 2; // 编码（需要实现Turbo编码器，产生系统比特和两路校验比特） // 这里省略具体编码，假设我们已得到接收的LLR值 // 译码 int decoded[len]; turbo_decode(recv_sys, recv_par1, recv_par2, len, decoded); // 统计误码率 int err = 0; for (int i = 0; i < len; i++) if (decoded[i] != info[i]) err++; printf("误码率: %d/%d\n", err, len); return 0; }

五、Turbo vs LDPC：双雄对决

在5G NR中，LDPC用于数据信道，Turbo码被取代，但Turbo码在4G中依然重要。两者都是信息论与工程结合的典范。

六、我的学习心得

实现Turbo码比卷积码复杂一个数量级。我花了三天时间调试Log-MAP算法，主要坑点：

• max*函数的数值稳定性：需要用ln(1+exp(-|x-y|))处理，否则会溢出。

• 初始状态：通常假设编码器从全0状态开始，结束也回到全0（需要尾比特）。我为了简化，没有加尾比特，导致边界错误。

• 交织器的设计：简单的块交织效果不好，但为了学习足够了。

如果你第一次接触Turbo码，建议先跑通一个极简版本（比如用BCJR算法的整数实现），再慢慢完善。