LDPC编码与译码全解析：从校验矩阵到逼近香农极限的工程实践

如果你稍微留意过身边的通信设备会发现一个很有意思的现象Wi-Fi 5/6、5G 手机、卫星电视机顶盒、万兆以太网口、甚至你正在用的 SSD 主控内部都在跑同一种纠错算法——LDPCLow-Density Parity-Check低密度奇偶校验码。一个 1962 年就被提出的老码为什么在最近十几年突然成了各种链路里近乎“默认选项”的存在答案是一个让人无法拒绝的数字LDPC 的性能可以逼近香农极限。换句话说在同样的信噪比下它能做到比其他经典方案更低的误码率或者反过来在同样的误码率要求下用更少的发射功率就能通信。这篇文章我会把 LDPC 从编码到译码的完整链路拆开讲清楚校验矩阵和 Tanner 图到底在表达什么编码为什么不能用最朴素的高斯消元硬算译码算法中的 BP 和 Min-Sum 每一步在做什么以及真正把它落地到硬件和仿真环境时大家最容易踩的坑在哪里。适合刚接触信道编码的初学者也适合已经在看 3GPP 协议或写浮点模型验证的人。我尽量少堆公式但该有的推导一步都不会省。1. 从“逼近香农极限”说起LDPC 解决的真实问题1.1 信道编码为什么重要以及传统方案的瓶颈任何一条物理链路无论是空口辐射、铜线传输还是闪存颗粒读回本质上都是往一个不完美的通道里写数据。噪声和干扰会让某些比特翻转而信道编码做的事情就是发送端在原始数据后面加一段结构化的冗余接收端利用这段冗余把错误纠正回来。这个“冗余”加得越高效能容忍的噪声就越大。在 LDPC 火起来之前业界用了很多年卷积码和它的级联方案。Turbo 码在上世纪九十年代一度非常亮眼逼近香农极限的性能让它在 3G/4G 时代大放异彩。但 Turbo 有个天生缺陷译码延迟很大因为交织器会引入一个块级别的处理时延同时在高吞吐场景下它需要大量的迭代计算功耗和面积都不好看。卷积码本身性能上限偏低Viterbi 译码虽然稳定但增益有限级联 RS 码之后系统复杂度又上去了。LDPC 的优势恰恰在于它采用一种全然的并行迭代结构计算密集型操作被拆成大量独立小任务天然适合硬件并行做高吞吐。而且随着码长增加它的性能可以非常接近 Shannon 界——在 AWGN 信道、长码块条件下LDPC 甚至能做到离香农极限不到 0.1dB 的距离。1.2 LDPC 从被遗忘到被重新发现的过程1962 年 Gallager 在他的博士论文里提出了 LDPC 码思路非常直接如果校验矩阵足够稀疏那么迭代译码的时候每个校验方程之间几乎没有交叠干扰错误信息可以被“逐个击破”。但那个年代没有足够强的芯片来处理迭代运算这套思想很快就没人理了。直到 1996 年MacKay 和 Neal 重新挖掘出它学界才发现它和 Turbo 码一样可以逼近极限而且拥有更低的错误平层。再后来准循环 LDPCQC-LDPC让编码器和译码器的电路实现变得可行于是 DVB-S2 率先采用IEEE 802.11n 也把它定为标准。到了 5G NR数据信道直接以 LDPC 为核心编码和极化码分工控制信道用极化码数据信道用 LDPC。这个格局背后不是偶然而是 LDPC 在长码块、高吞吐、混合自动重传请求HARQ场景下综合胜出的结果。2. 校验矩阵与 Tanner 图LDPC 的骨架语言2.1 校验矩阵 H 的稀疏性到底意味着什么LDPC 是一种线性分组码。假设信息位长度是 K编码后码字长度是 N那么校验位长度 M N - K。码字 c 必须满足H · c^T 0这里 H 是一个 M × N 的矩阵元素只有 0 和 1。所谓“低密度”指的就是 H 中 1 的数量非常少每一行、每一列只有个位数的 1其余全是 0。如果 H 是一个全稠密的矩阵那它描述的就不是 LDPC而是一般的线性码译码复杂度会指数级上升。为什么稀疏性这么重要因为译码本质上是求解一组有约束的方程。如果每个方程里涉及的变量很少那么每个方程单独看都很“简单”合在一起迭代信息能够在图结构中逐步传播。一旦矩阵密度变高变量之间严重耦合迭代很容易在一个错误的局部解上收敛。工程上稀疏性直接影响硬件存储。H 矩阵如果 10000 行 × 20000 列全存下来是两亿个比特但如果每行只有 6 个 1那就只用存大约 12 万个索引稀疏表达的成本完全不同。2.2 Tanner 图与度分布看码结构像看地图H 矩阵可以画成一张二分图叫 Tanner 图左边一类节点叫变量节点对应码字的 N 个比特右边一类节点叫校验节点对应 H 的 M 行方程。H 矩阵第 i 行第 j 列如果为 1就在第 j 个变量节点和第 i 个校验节点之间连一条边。一个变量节点连接的边数叫做它的“度”。校验节点也一样。所有变量节点的度构成的分布直接决定了一个 LDPC 码能好到什么程度。比如经典的规则 LDPC 可以写成 (dv, dc)意思是每个变量节点度数为 dv每个校验节点度数为 dc。dv3、dc6 是一个很经典的选择码率大约 1 - 3/6 1/2。在 AWGN 信道下规则码就能提供不错的性能。但更强大的码往往是非规则的不同的变量节点具有不同度数。为什么要这样可以这样理解度数高的变量节点和许多校验方程相连它在迭代中能更快收集外部信息相当于“更信任它”度数低的节点虽然信息少但不容易被噪声带偏。通过密度演进Density Evolution工具可以优化出一个最优度分布让迭代译码过程中错误概率下降最快。一般来说变量节点度高的节点比例大一些能显著提升低信噪比下的性能但要注意避免过高否则错误平层会变差。Tanner 图的另一个重要概念是所有环的长度里的最小值 girth。如果图中存在一个长度为 4 的环意味着某两个变量节点和某两个校验节点相互连接形成两条独立通路。迭代时两股消息会在环内互相加强形成一种“自我确认”效应让错误的置信度也被放大译码性能严重下滑。因此设计好的 LDPC 矩阵通常要求 girth 至少到 6更好的是 8。这也是为什么随机生成的稀疏矩阵不能直接入用的原因——你必须做环长检测。2.3 QC-LDPC从抽象矩阵到可实现的电路直接用一个任意稀疏矩阵做工程会遇到三个问题第一矩阵本身需要大量存储第二变量节点和校验节点的连接关系不规则导致硬件布线极其复杂第三编码时如果矩阵没有结构计算复杂度难以降低。QC-LDPC 的出现就是来解决这些问题的。QC-LDPC 的核心思想是把 H 矩阵分块组织每个子块是 Z × Z 的循环移位单位阵或者 Z × Z 的全零阵。一个循环移位单位阵可以通过把单位阵的每一行向右移动固定偏移量得到。这样一来整个 H 矩阵只需要存储每个子块的偏移量即可而且译码时对同一个 Z 组的校验方程可以并行计算天然支持高并行度。5G NR 里的 LDPC 就是 QC-LDPC。协议里定义了两套基图Base GraphBG1 用于大传输块和高码率场景BG2 用于小传输块和低码率场景。基图是基础的较小矩阵每个元素都代表一个 Z×Z 循环移位块Z 叫做提升因子。发送端需要根据实际的传输块大小选择一个 Z把基图“扩展”成真正使用的 H 矩阵。这个机制使得同一套硬件可以通过参数配置适配从几十个字节到几千个字节的数据块。3. 编码端如何用线性复杂度完成纠错编码3.1 最朴素的高斯消元编码为什么在工程上走不通给定校验矩阵 H最直接的编码方法是把 H 化成形如 [P | I] 的形式然后得到生成矩阵 G [I | P^T]编码时计算 c u · G。因为 G 要满足 H · G^T 0系统位直接摆放原始信息比特校验位通过生成矩阵计算。听起来很简单但代价非常明显经过高斯消元之后P 矩阵往往不再稀疏它可能变成一个几乎全密的矩阵。如果信息位 K 4096那么 P 就是 4096 × 4096 的一个稠密矩阵一次编码要做几千万次比特运算。对于高吞吐场景这几乎等于直接把编码器推到功耗和面积的绝路。更糟糕的是消元过程中 H 的稀疏结构被完全破坏你无法用任何并行电路去加速。所以工程上做 LDPC 编码基本不会走这条路。真正有效的方法是利用 H 本身的结构或者干脆设计编码友好的 H。3.2 Richardson-Urbanke 近似线性编码的直觉Richardson 和 Urbanke 在 2001 年提出了一种经典方法基本思路是不把 H 消成完全系统形式只把它消成一种“近似下三角”的形态即左上角很大一块保持稀疏只留右下角一个较小的区域需要稠密计算。具体来说把 H 重排列成如下分块形式H | A B | | C D |其中 A 是较大的稀疏方阵对应的变量参与编码中的中间变量计算B 和 C 保持稀疏D 是较小的矩阵。编码时信息位已知先利用 A 的稀疏性快速解出一组中间变量然后再通过 D 求解校验位。由于 D 的尺寸比较小即使对它做稠密运算总计算复杂度也只是近似线性的通常可以做到 O(N) 或 O(N log N)。这种方法的核心思想是“把稠密的部分限制在一个尽可能小的区域里”。它不需要设计者重新构造 LDPC 码只要现有的 H 矩阵结构具备满足要求的近似下三角形状就可以用。虽然现在很多标准和自研码都直接采用更加结构化的 QC-LDPC 编码方案但 RU 算法的思想仍然值得了解因为当你拿到一个任意的稀疏 H 矩阵时它是最通用的编码工具。3.3 5G NR 基图与编码速率匹配的工程逻辑5G NR 的 LDPC 编码并不需要做复杂的矩阵消元因为协议定义的基图本身带有可用于编码的结构。BG1 基图尺寸是 46 行 × 68 列BG2 是 42 行 × 52 列其中信息列数分别对应不同的最大信息位长度。实际信息比特长度 K 不支持任意值时协议采用填充比特filler bit补齐到 K 的整数倍对应的列数。真正重要的是速率匹配机制。LDPC 编码之后产生一个系统位加校验位的序列但发射机不一定全部发送。协议采用循环缓冲区从某个起始位置开始按照特定顺序连续取比特发射重传时从缓冲区的另一个位置取更多比特。这种增量冗余的方式和 HARQ 天然契合第一次发送尽量少、码率尽量高如果解码失败再发送更多校验比特接收端把这些合并起来用更低码率译码。编码器的硬件实现也很有意思由于 QC-LDPC 每个 Z 块内部的校验位计算是并行的编码器可以设计成多个 Z 通道同时运算每个通道内部做移位异或。在 5G 的典型配置下一个中等规格的 FPGA 或者 ASIC 就能做到数十 Gbps 的编码吞吐。4. 译码算法从置信传播到最小和4.1 LLR 域的和积算法推导LDPC 译码的主流算法是置信传播Belief Propagation也叫和积算法Sum-Product Algorithm。它的工作基础是接收端从信道拿到每个比特的软信息通常用对数似然比 LLR 表示L_i log(P(b_i0 | y_i) / P(b_i1 | y_i))在 BPSK 调制、AWGN 信道下如果发送映射是 0 - 11 - -1那么 L_i 2 y_i / σ²。LLR 大于 0 说明该比特偏向 0绝对值越大置信度越高。迭代译码的过程就是在 Tanner 图上不断地传递两种消息变量节点传给校验节点的消息等于自己的信道初始 LLR 加上除了目标校验节点以外所有其他相邻校验节点传回的外部信息之和。这个操作的直觉是变量节点综合“信道证据”和“邻居的校验意见”形成自己对这个比特的当前看法但传给某个校验节点时要刻意排除那个校验节点自己刚传来的信息防止自我强化。校验节点传给变量节点的消息是所有相邻变量节点把自己的值作为独立观测时校验方程能够推断出的信息。严格的计算公式为mc→v 2 arctanh( Π_{v ∈ N(c) \ {v}} tanh(m_{v→c} / 2) )这个公式看起来有点吓人但它的含义其实非常优雅把一个消息先映射到“概率空间”通过 tanh在这个空间里多个独立证据合起来判断某个比特是否满足校验方程相当于做乘法再把乘法结果映射回 LLR 域通过 arctanh。经过若干轮迭代每个变量节点把信道信息和所有校验节点传回的信息加起来得到后验 LLR对它取符号就得到判决。为了保证收敛后的结果是合法码字通常在每一轮迭代结束都要做一次硬判决并计算校验子 H·c^T 是否全零。一旦校验通过立即停止迭代这能省掉大量无效计算。4.2 Min-Sum 近似为什么敢省掉 tanh 和 arctanh和积算法的问题在于 tanh 和 arctanh 在硬件里非常昂贵即使是软件仿真每条边消息都算一遍也会拖慢速度。但看校验节点更新公式的结构会发现一个重要事实多个因子的乘积数值大小实际上由绝对值最小的那个因子主导其他因子的贡献主要体现在符号上。把 tanh 和 arctanh 全部省掉校验节点消息的幅值直接用相邻变量节点消息幅值的最小值来近似mc→v ≈ ( Π sign(m_{v→c}) ) · min_{v ≠ v} |m_{v→c}|这就是最小和算法Min-Sum。它的计算量比和积算法低一个数量级没有乘法器、没有查表只要做比较和异或。代价是性能会有损失在规则码、典型配置下大约差 0.2 到 0.4 dB。不过工程上几乎不会直接使用朴素 Min-Sum而是用两种改进方案归一化最小和Normalized Min-Sum把 Min-Sum 的输出消息乘一个小于 1 的归一化因子 α典型值在 0.75 到 0.8 之间。这个因子补偿了用 min 近似替代精确乘积时带来的幅值高估。偏移最小和Offset Min-Sum把幅值减去一个固定偏移 β小于 β 的消息直接置零原理是压制那些置信度太低的“可疑消息”。我在实际项目里测试过归一化因子对性能非常敏感选不好甚至会不如朴素 Min-Sum。推荐的做法是用 0.8 起步然后以 0.05 的步进做完整链路仿真找到在目标误块率处的最优值。4.3 迭代调度策略泛洪、分层与归一化修正消息更新的顺序叫调度策略。最基础的是泛洪Flooding调度每一轮迭代里先并行更新所有变量节点消息再并行更新所有校验节点消息。这种做法逻辑清晰、容易并行多核处理器和 FPGA 上都能跑但收敛速度一般要达到目标误码率往往需要比较多的迭代次数。分层调度Layered Scheduling是一个很实用的改进思路把校验节点按某种顺序逐批更新每更新完一批立刻把它的影响反馈到变量节点后续校验节点再更新时就能用上更新的消息。这个“即时反馈”机制让信息在图网络中传播得更快。实测中相同的迭代次数下分层调度的收敛速度大约是泛洪调度的两倍换句话说原本需要 10 次迭代才能达到的性能分层调度可能 5 到 6 次就达到了这对降低译码延迟非常有价值。但分层调度在硬件里有一个甜蜜的负担它要求变量节点消息存储支持同一周期内多个不同地址的读写否则就会出现内存冲突反而拖慢时钟频率。常见的解决办法是把变量节点的消息存储拆成多个 bank同时用基图的循环移位结构设计避免同一周期内访问同一个 bank。如果你的矩阵不是 QC-LDPC分层的收益会被存储冲突吃完这也是为什么标准化的 LDPC 几乎全是 QC-LDPC 的原因之一。5. 工程落地中的经典坑量化、短环与错误平层5.1 定点量化对译码性能的影响浮点仿真跑得很漂亮的 LDPC 译码器一旦转成定点实现性能往往掉得让人心疼。关键原因是消息在迭代中会不断更新、饱和、截断任何一步的精度损失都可能被迭代放大。我常用的设置是信道初始 LLR 用 6 bit 表示其中 1 bit 符号位、5 bit 幅值迭代过程中校验节点消息用 5 bit 幅值变量节点消息由于要累加多个外部信息用 8 bit。饱和值不能拍脑袋定如果初始 LLR 的幅值范围通常在 ±15变量节点累加后可能到 ±63所以至少需要使用 7 bit 幅值才不会让高置信度的正确消息被截断。一个很常见的坑是信道 LLR 的缩放系数没有对。理论上 L_i 2 y_i / σ²但实际系统经过 AGC、信道估计之后噪声方差估计不准的话这个系数就偏了。实践中我通常先做一次噪声方差估计然后对归一化系数做一个小范围扫描。你可能会觉得奇怪为什么一个放大系数对迭代译码影响这么大因为 Min-Sum 是基于消息幅值比较的全局缩放不会改变比较结果但和积算法里 tanh 和 arctanh 是非线性的缩放偏差会扭曲置信度分布。5.2 环路cycle与错误平层一个实测案例很多人在仿真中会发现一个现象信噪比提高到一定程度后误码率曲线不再陡峭下滑而是出现一个平台像是踩在了一个地板上上不去。这就是所谓错误平层error floor。我遇到过最典型的一次是设计一个码率 0.89 的高码率 LDPC浮点仿真中错误平层出现在误码率大约 1e-7 的位置怎么加迭代次数都不下去。后来把 H 矩阵的四环分布画出来发现问题集中在几个特定的短环组合上某些变量节点度数只有 2且它们参与的环长度只有 6这些节点在迭代中很容易形成 trapping set——一组变量节点的硬判决卡在某个错误状态即使反复迭代也无法逃离。解决错误平层的方法有几个第一是设计阶段避免低度数节点组成小环特别是度数为 2 的节点它们在迭代中消息来源少容错能力差第二是增加迭代次数上限虽然不能从根源上消除平层但能把平台位置压得更低第三是级联一个外码比如闪存控制器里普遍的做法是在 LDPC 外面再叠一个 BCH 码用 BCH 去纠正 LDPC 残留的极少量错误。另外Min-Sum 算法的错误平层通常比和积算法更早出现这是归一化因子不足和低幅值消息过早截断共同造成的。如果目标误码率在 1e-8 以下建议在仿真阶段就把定点模型跑起来别总拿浮点结果去估算。5.3 提前停机准则与吞吐率平衡迭代译码的功耗和吞吐很大程度取决于“平均迭代次数”而不是“最大迭代次数”。如果每次都跑满最大迭代白白浪费功耗如果停机太早性能又会下降。提前停机early termination是译码器设计的必修课。最简单的准则是校验子检测每轮迭代结束裁决出硬判决比特乘以 H 矩阵如果校验子全零就停止迭代。但在高信噪比区域往往很早就能通过校验子检测而在低信噪比区域大部分数据包都会一直跑到最大迭代次数无法通过提前停机省时间。另一个工程上实用的准则是“相邻两轮迭代的硬判决结果不再变化”如果输入消息还在更新但判决输出已经稳定了说明继续迭代大概率也没用。我测试过这个准则能减少约 10% 到 15% 的平均迭代次数且不影响性能延迟基本无损。但要注意实现它会增加额外的硬判决比较逻辑你需要权衡存储和比较开销是否值得。如果你做的是 5G NR 场景还要考虑 HARQ 的影响初传失败后重传到达时接收端通常会把本次的信道 LLR 和上一次译码过程中保留的变量节点外部信息合并再用新的迭代起始点重新译码。这个过程里提前停机准则同样适用但要注意第一次迭代时旧消息不能直接当作信道信息处理否则会造成过度置信。6. 我的实现与测试经验总结6.1 仿真工具链与浮点到定点的标准流程我的 LDPC 验证流程一直遵循一套从“纯浮点模型”到“定点模型”再到“RTL/FPGA 原型验证”的三步走策略。千万不要跳过浮点模型直接开始写硬件代码否则一个算法选择错误返工代价极高。第一步用 MATLAB 或 Python 搭建浮点链路。Python 里我习惯用 ldpc 的自研脚本配合 numpy 做矩阵操作码字用随机数生成信道用 AWGN译码分别实现和积和最小和两套方便性能对比。建议把环长检测、度分布统计、错误平层扫描这些脚本也一次性写好后面会反复用到。第二步把译码器改成定点模型。定点模型必须和浮点模型逐步对比先固定信道 LLR 的量化参数观察变量节点消息的分布范围再确定内部消息位宽。通常要对比三轮短码长、中码长、长码长分别观察误码率和误块率曲线。我给自己定过一条规矩定点模型相对于浮点模型的性能损失控制在 0.1 dB 以内才允许进入硬件设计。第三步在 FPGA 上做原型验证。个人经验是不要一开始就做全并行先用一个“时间分片少量并行单元”的架构跑通功能再逐步提升并行度。全并行结构的数据对齐、存储冲突、时序收敛任何一个问题都够纠结两周。6.2 关于性能对照和参数调优的个人建议如果你拿到一个现成的 LDPC 代码想把它用到自己的系统里一定不要只看官方文档里的那组仿真曲线。不同信噪比定义、不同调制方式、不同码率、不同块长都会大幅影响可比性。我建议你在自己的链路里跑一遍参考码和候选码并记录几组固定对比点最高码率、最低码率、中间码率长块和短块BPSK 和 16QAM。参数调优时我最开始会固定迭代次数为 20然后单独扫归一化因子 α找到误块率最低的点接着扫描偏移量 β最后把迭代次数从 4 到 30 挨个跑一遍看有没有性能饱和。还有一个容易被忽略的点是码字映射关系发送端 0/1 映射成 BPSK 符号时到底是 0 映射 1 还是 -1会直接影响接收端 LLR 的正负号约定。这个看似愚蠢的细节真的会让你的译码器在第一次上链路时输出全零反而导致校验失败别问我怎么知道的。另外如果你需要在一些特殊场景下自定义 LDPC可以尝试用 PEGProgressive Edge-Growth算法构造稀疏矩阵。PEG 的核心是逐条添加边并且每次都选择能最大化当前局部最小环长度的变量节点和校验节点对。用 PEG 构造出来后再用 QC 结构进行循环移位扩展实测能稳定做出 girth 为 8 的中短码。说了这么多LDPC 最迷人的地方其实不是那堆公式而是它把两个看起来矛盾的目标同时做到了极致结构足够简单简单到每一条边都可以独立计算结构又足够复杂复杂到百万级码长的误码纠错能逼近理论极限。做编译码器和写普通软件完全是两种心态你需要面对的不只是逻辑正确还有资源约束、时序边界和那一点点永远差着的信噪比。希望这篇文章能帮你把这条路上的几个大坑提前填平让你把精力花在真正有意思的优化上。