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⁡(1e−∣x−y∣)max∗(x,y)max(x,y)ln(1e−∣x−y∣)。听起来复杂但代码实现有固定模式。我们下面会给出简化的实现。四、C语言实现一个简化的Turbo码为了让你快速上手我们选择一个非常小的Turbo码两个相同的卷积码递归系统卷积码RSC生成多项式(1, 5/7)八进制即反馈多项式7前向多项式5。约束长度K3记忆深度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 i0; ilength; 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*i1] p1; output[3*i2] p2; } } // BCJR译码算法框架简化版 void bcjr_decode(float* received, float* llr_out, int length) { // 这里应实现前向/后向概率计算 // 简化示例仅做占位 for(int i0; ilength; 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 iter0; iterMAX_ITER; iter) { // 第一个分量译码器 bcjr_decode(received, llr1, length); // 交织/解交织处理 for(int i0; ilength; i) { extrinsic[i] llr1[i] - received[i]; // 计算外信息 llr2[(i*13)%length] extrinsic[i]; // 交织 } // 第二个分量译码器 bcjr_decode(llr2, llr2, length); // 更新外信息 for(int i0; ilength; i) { extrinsic[(i*13)%length] llr2[i] - llr1[i]; // 解交织 } } // 最终判决 for(int i0; ilength; 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 i0; i24; 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 i0; i8; 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[N1][NUM_STATES]; // 前向状态度量 double beta[N1][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[t1][s_next] max_star(alpha[t1][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[t1][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[t1][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双雄对决特性Turbo码LDPC码提出时间1993年1962年但被遗忘90年代重新发现核心思想并行级联 迭代译码稀疏校验矩阵 置信传播译码算法Log-MAP网格BP图复杂度较高指数于状态数较低线性于码长但需要足够长误码平台可能出现较高平台平台较低应用3G/4G、深空、DVB5G、Wi-Fi、以太网、SSD交织器必须不需要在5G NR中LDPC用于数据信道Turbo码被取代但Turbo码在4G中依然重要。两者都是信息论与工程结合的典范。六、我的学习心得实现Turbo码比卷积码复杂一个数量级。我花了三天时间调试Log-MAP算法主要坑点max*函数的数值稳定性需要用ln(1exp(-|x-y|))处理否则会溢出。初始状态通常假设编码器从全0状态开始结束也回到全0需要尾比特。我为了简化没有加尾比特导致边界错误。交织器的设计简单的块交织效果不好但为了学习足够了。如果你第一次接触Turbo码建议先跑通一个极简版本比如用BCJR算法的整数实现再慢慢完善。