我第一次动手写LDPC译码器是在一个需要自研信道编码模块的项目里。当时满脑子觉得译码嘛不过就是把教材上的和积算法置信传播抄成代码。结果Matlab一跑误码率曲线惨不忍睹逐行查了一天最后定位到问题概率值在迭代乘法中下溢成了0后续的比值计算直接变NaN整个译码器就废了。这件事逼着我把概率公式从头推了一遍才真正理解LDPC译码在干什么。这篇博文就把这套推导过程完整记录下来。内容从“译码为什么是个概率问题”讲起一步步推后验概率、似然比、对数似然比LLR再推到校验节点消息更新那条经典的tanh规则最后落到工程实现里最容易让人头大的数值稳定性问题上。适合刚接触信道编码、被教材里一堆术语劝退的读者也适合已经在跑仿真但遇到性能或数值问题的同学。1. 译码问题的本质从校验约束到后验概率推断1.1 校验矩阵定义了码字空间也定义了译码目标LDPC码Low-Density Parity-Check Code的核心是一个稀疏校验矩阵H。说它稀疏是因为矩阵里1的个数远小于0的个数。一个长度为n的码字c合法当且仅当满足$$H c^T 0 \quad (\text{模2运算})$$每一行H_j都代表一个校验约束通俗说就是“这个约束涉及的比特中必须有偶数个1”。所有这些约束合在一起勾勒出码字空间的边界。发射端做的事很简单从所有合法码字里挑一个发出去。真正难的在于接收端——你拿到的是被信道污染过的接收序列y要反推出最有可能的发送码字c。为什么这天然是一个概率问题因为信道噪声是随机的你永远无法确定地知道发的是什么只能计算“给定接收y发送码字是c的概率有多大”。译码器最理想的目标是找到条件概率P(c|y)最大的那个码字这叫做最大后验概率译码也就是MAP译码。数学上写出来很干净但直接求解是灾难码字空间大小是2^k量级遍历是不可能的。所以实际译码必须另辟蹊径。1.2 因子图分解把全局概率问题拆成局部消息传递LDPC码能高效译码的真正原因在于校验矩阵的稀疏性。稀疏意味着每个校验约束只涉及少数比特每个比特也只参与少数几个约束。这种结构天然适合用因子图Factor Graph来表达图中一边是变量节点对应每个码字比特另一边是校验节点对应每一行校验约束两者之间用边连接表示“这个比特参与了那个约束”。置信传播Belief Propagation, BP算法就是在这样一张图上做消息传递。每个节点根据自己收到的输入消息处理后把新的消息发给邻居节点反复迭代最终逼近每个比特的后验概率。这个过程也叫和积算法Sum-Product Algorithm名字里的“和”和“积”分别对应后面要讲的两类更新操作。理解这条主线就理解了LDPC译码的骨架全局概率推断问题被因子图的稀疏结构分解成了一堆局部计算每个节点只关心和自己直接相连的邻居。2. 从概率到对数似然比把乘法变成加法的关键一步2.1 单个比特的后验概率怎么用贝叶斯公式展开考虑最简单的情形信道上只有一个比特。设发送端采用BPSK调制把编码比特0映射为发送符号1编码比特1映射为发送符号-1。接收端得到y x n其中n是均值为0、方差为σ²的高斯白噪声。我们关心的是条件概率P(x1|y)和P(x-1|y)。用贝叶斯公式展开$$P(x1|y) \frac{P(y|x1)P(x1)}{P(y)}$$$$P(x-1|y) \frac{P(y|x-1)P(x-1)}{P(y)}$$如果发送端0和1等概率出现即P(x1)P(x-1)1/2那么分母P(y)和先验项都会约掉。后验概率的比较就只剩下似然函数P(y|x±1)的比较。这正是信道模型起作用的地方——它告诉我们给定发送符号接收值在什么分布下产生。2.2 高斯信道下的似然比与对数似然比在加性高斯白噪声AWGN信道下给定x1接收y服从均值为1、方差为σ²的高斯分布给定x-1接收y服从均值为-1、方差为σ²的高斯分布。把高斯概率密度函数代进去$$L(y) \ln\frac{P(x1|y)}{P(x-1|y)} \ln\frac{e^{-(y-1)^2/(2\sigma^2)}}{e^{-(y1)^2/(2\sigma^2)}} \frac{2y}{\sigma^2}$$这个结果漂亮得让人意外在BPSK加AWGN信道下接收符号的对数似然比LLR就是接收幅度的线性函数。y越大越倾向于是1LLR为正y越小越倾向于是-1LLR为负。LLR的绝对值大小则代表置信度的高低。数值上y0.5、σ²0.5时LLR2意味着这个比特为0的概率大约是为1的概率的e²≈7.4倍。硬判决时LLR0判为0LLR0判为1即可。2.3 对数域为什么是工程上的必然选择顺着上面的推导你可能觉得概率公式也没多复杂。但真实译码器面对的不是一个比特而是成百上千个比特在图上相互传递消息。每一轮迭代都有大量概率乘法变量节点要乘上所有相邻校验节点的贡献校验节点又要处理一堆概率的组合。概率值通常在0到1之间乘多了会急剧变小动态范围极大。这件事在浮点运算下就会出问题——我在开头提到的下溢成0就是这么来的。引入对数的第一个好处就是压缩动态范围概率的乘积变成对数域的加法LLR从10⁻¹⁰量级变成-23左右的普通浮点数计算稳定得多。对数域的第二个好处是加法的“耦合”也变简单了——两个独立事件同时成立的概率相乘转到对数域就是LLR相加这恰好匹配了因子图上消息合并的语义。所以现代LDPC译码器几乎都是全LLR域实现概率域实现只存在于教学代码里。3. 校验节点更新用代数恒等式撬开核心公式3.1 校验约束在BPSK映射下变成了乘积约束校验节点更新是整个推导里最硬核的部分。先明确一下问题校验节点j连接d个变量节点现在要从除i以外的d-1个节点收到的消息推算出发给节点i的消息。这d-1个消息以LLR形式给出每个消息隐含了对应比特为1或-1的概率。关键一步是把校验约束翻译成产品形式。校验约束“这些比特中必须有偶数个1”在BPSK映射下等价于“这些比特对应的±1符号相乘必须等于1”。这是从模2加法到实数乘法的自然转化也是后续所有代数技巧能施展的前提。设其他d-1个比特的符号分别为s_1, s_2, ..., s_{d-1}每个符号取1或-1。已知的LLR消息L_k ln(p_k / q_k)其中p_k P(s_k1)q_k P(s_k-1)且p_k q_k 1。为了让整个校验约束满足目标比特的符号s_i必须等于其他符号的乘积T s_1 s_2 ... s_{d-1}。因此问题变成了已知一组独立符号的概率分布求这组符号乘积为1和-1的概率之比。3.2 用期望算符求“偶数为-1”的概率计算P(T1)和P(T-1)看起来要枚举2^{d-1}种组合但有一个取巧的办法。注意T的期望值满足$$E[T] P(T1) - P(T-1)$$而另一方面由于各符号独立乘积的期望等于期望的乘积$$E[T] \prod_{k1}^{d-1} E[s_k]$$每个符号的期望是$$E[s_k] (1)p_k (-1)q_k p_k - q_k \frac{e^{L_k}-1}{e^{L_k}1} \tanh\left(\frac{L_k}{2}\right)$$再加上P(T1) P(T-1) 1这个基本约束解二元一次方程组就得到$$P(T1) \frac{1 \prod_{k1}^{d-1}\tanh(L_k/2)}{2}$$$$P(T-1) \frac{1 - \prod_{k1}^{d-1}\tanh(L_k/2)}{2}$$这个推导不仅省掉了组合爆炸的枚举还直接把tanh函数引了进来。现在目标比特的似然比可以写出来了$$r_i \frac{P(T1)}{P(T-1)} \frac{1 \prod_{k1}^{d-1}\tanh(L_k/2)}{1 - \prod_{k1}^{d-1}\tanh(L_k/2)}$$这个形式就是概率域校验节点更新的完整表达式。有意思的是这个式子对任意数量的输入消息都成立不需要单独处理d-12、3等特殊情况跟暴力枚举的结果完全一致但计算量小得多。3.3 取对数得到tanh规则如果消息以LLR形式流动还需要把似然比r_i转成对数形式。这里用到反双曲正切恒等式$$\ln\left(\frac{1x}{1-x}\right) 2,\operatorname{arctanh}(x)$$于是校验节点发给变量节点i的消息为$$L_{j\to i} 2,\operatorname{arctanh}\left(\prod_{k\neq i}\tanh\left(\frac{L_{k\to j}}{2}\right)\right)$$这就是教材里那条著名的tanh规则。推导走到这里关键逻辑已经闭环校验约束用乘积形式表达输入LLR通过tanh映射到(-1,1)区间乘积汇总所有外部证据再用arctanh映射回LLR域。每一步都有明确的概率含义而不是凭空冒出来的公式。3.4 符号-幅度分解与Min-Sum的萌芽tanh规则虽然精确但每个校验节点每轮都要算一堆tanh和arctanh数值代价不小。工程上常用近似而近似的基础是把公式拆成符号和幅度两部分。由于tanh是奇函数乘积的符号等于输入消息符号的乘积而乘积的幅度则受限于绝对值最小的那一项——因为|tanh(L/2)|始终小于1乘得越多幅度越小其中最小的那个因子对最终幅度影响最大。这个观察直接导出了Min-Sum近似如果把所有输入消息中绝对值最小的那个挑出来用它作为输出消息的幅度再用所有输入符号的乘积作为输出消息的符号就得到了一条极简单的更新规则。它没有浮点初等函数运算实现成本极低代价是比精确BP差零点几个dB的性能。怎么修正这个误差后面的章节会专门讲。4. 变量节点更新与完整迭代流程4.1 变量节点的消息合并其实就是一个累加器变量节点的更新比校验节点简单得多。假设变量节点i连接若干个校验节点它还接收到来自信道的固有LLR消息L_ch 2y_i/σ²。在独立性假设下所有这些来源的概率相乘转到对数域就是LLR相加。所以变量节点发给某个校验节点j的消息等于信道LLR加上除j以外所有校验节点传来消息的总和$$L_{i\to j} L_{ch} \sum_{j\in N(i)\setminus{j}} L_{j\to i}$$这里有一个很容易忽略但极其重要的细节计算发往j的消息时必须排除来自j自身的消息。这就是“外部信息原则”。如果没有这个排除一条消息沿着i→j→i→j的路径自我强化迭代几次后LLR的绝对值会膨胀到几倍甚至几十倍译码器要么震荡不收敛要么过早收敛到错误码字。我在第一次实现时就踩过这个坑——去掉排除项后低信噪比下误码率反而飙升。4.2 从初始化到终止判定一次完整迭代的运作顺序整个BP译码是一个干净的两阶段交替过程。初始化时所有校验节点发给变量节点的消息设为0因为还没有任何统计证据。变量节点发给校验节点的初始消息直接取信道LLR这是每个比特的第一手观测。然后开始迭代第一步校验更新对每个校验节点j收集所有相连变量节点发来的消息用tanh规则给每个邻居计算新的输出消息。第二步变量更新对每个变量节点i累加信道LLR和所有校验节点消息算出新的输出消息。第三步计算后验LLR变量节点把信道LLR和所有校验节点的消息全部加起来得到当前对所有比特的概率估计。第四步硬判决与终止判断根据后验LLR的符号做硬判决然后代入校验方程H c^T 0检查。如果所有校验都满足说明找到了一个合法码字提前终止否则继续下一轮直到达到最大迭代次数。这个流程的核心价值在于它不是一次性给出答案而是让证据在图上反复流动、互相印证每轮迭代都在修正上一轮的判断。实际实现里大多数码字在信噪比不太差时5到10轮就能收敛很少跑满最大迭代次数。4.3 从公式到可执行代码的落点把上面的流程转成代码核心结构并不复杂。这里给一个Python风格的伪代码框架def ldpc_bp_decode(H, llr_ch, max_iter50): m, n H.shape # 初始化消息 msg_c_to_v np.zeros((m, n)) # 校验节点给变量节点的消息 msg_v_to_c llr_ch.copy() # 变量节点给校验节点的消息 for it in range(max_iter): # 校验节点更新简化写法实际按稀疏索引遍历 for j in range(m): neighbors np.where(H[j, :] 1)[0] for i in neighbors: others [k for k in neighbors if k ! i] product np.prod(np.tanh(msg_v_to_c[j, others] / 2)) msg_c_to_v[j, i] 2 * np.arctanh(product) # 变量节点更新 for i in range(n): neighbors np.where(H[:, i] 1)[0] for j in neighbors: others [k for k in neighbors if k ! j] msg_v_to_c[j, i] llr_ch[i] np.sum(msg_c_to_v[others, i]) # 后验LLR与硬判决 llr_post llr_ch np.sum(msg_c_to_v[:, :], axis0) c_hat (llr_post 0).astype(int) # 校验终止条件 if np.all(H c_hat % 2 0): break return c_hat这段代码为了可读性牺牲了效率真正的工程实现会用稀疏矩阵存储、消息索引压缩、并行化批量更新。但它把消息传递的骨架展示得很清楚照着这个结构去填细节不容易跑偏。5. 工程实现中的数值稳定性与近似方案5.1 概率下溢我第一次实现时的惨痛教训回到开头那个问题。首次实现时我图省事直接用概率域做BP校验节点的输出是概率比值变量节点做概率乘法。从数值角度看这埋了一个巨大的雷。LDPC译码的消息在迭代中会变得极度自信——某一个比特的LLR可能从初始的2迅速增长到20甚至30换算成概率就是e²⁰/(1e²⁰)≈0.999999998。反方向另一个消息的概率可能小到10⁻²⁰以下多轮迭代后直接突破双精度浮点的下限变成0。一旦某个概率变成0下一个对数运算就是ln(0)-∞再往后一步就是NaN。而NaN在浮点运算里会像病毒一样蔓延所有涉及到这个值的消息全部失效。我当时看到误码率曲线在某个信噪比点突然塌陷就是这个问题。解决的办法很简单但也很彻底整个译码过程不要出现“概率”这个量全部改用LLR。LLR的取值范围是对称的无论多自信绝对值也就是几十不会出现0或∞这样的病态值除非数学上真的需要。5.2 tanh与arctanh的计算问题全LLR域实现之后新的问题是tanh和arctanh的计算代价。这两个函数涉及指数运算在浮点DSP或FPGA上都不便宜。更麻烦的是tanh在输入很大的时候饱和到±1arctanh在输入接近±1的时候急剧增长到±∞形成潜在的不稳定点。工程上通用的做法是对LLR做钳位clamp。具体来说把消息的绝对值限制在某个范围比如±30。理由很简单LLR30对应的概率置信度已经超过了一切实际需求再大的值只会在数值上找麻烦不会对译码性能有任何帮助。在这个范围内tanh和arctanh都可以用查表法或多项式逼近实现精度损失在0.01dB以内。我在一个定点实现里试过用9位查表索引性能相比浮点参考只差了不到0.05dB但对芯片面积和功耗的节省是实打实的。另外一个细节如果用的是C/C标准库的tanhf和atanhf在IEEE浮点下会正确返回±1或±∞并不会直接崩但后续运算中∞参与加减或乘除时会产生NaN所以钳位必须在函数调用前做而不是等返回后再处理。5.3 Min-Sum近似的误差分析与修正手段Min-Sum近似的公式非常简洁$$L_{j\to i} \approx \left(\prod_{k\neq i}\operatorname{sign}(L_{k\to j})\right) \cdot \min_{k\neq i}|L_{k\to j}|$$它把每个校验节点的消息更新压缩成了“符号乘积×最小绝对值”不需要任何初等函数运算。但代价是误差。精确tanh规则的输出幅度总是小于或等于最小输入幅度因为|tanh(L/2)|1相乘后更小arctanh后再放大所以Min-Sum在幅度上系统性偏大。偏大的后果是译码器过于自信性能会有损失。针对这个偏差业界有两个非常成熟的修正思路。第一个是归一化Min-SumNMS把Min-Sum的输出乘一个小于1的因子α取值通常在0.7到0.9之间。第二个是偏移Min-SumOMS从输出幅度中减去一个固定偏移β如果结果为负就截断到0β通常在0.5左右。归一化因子更像对系统误差的整体校准偏移项则更贴合“小消息需要更多压制”的特性。实际选哪种看实现平台NMS只需一个乘法和一个系数存储OMS是加法减法在定点实现里更友好。两种修正方案的性能差距通常在0.1到0.2dB以内可以在仿真里直接对比选定。5.4 信道LLR失配对性能的影响很多实现者容易忽略的是初始化时那个简单的2y_i/σ²对整条译码性能曲线有决定性影响。σ²在这里是信道噪声方差如果估计不准相当于给所有信道消息加了一个错误的全局缩放因子。在实践中我发现一个规律σ²估小了也就是以为信道比实际干净信道LLR会被放大译码器表现“过于自信”中高信噪比下容易过早收敛到伪码字误码率曲线出现错误平层σ²估大了信道LLR被压小译码器表现“过于保守”需要更多迭代才能收敛性能整体下移但不会出现灾难性的错误平层。所以在接收机设计里噪声方差估计的精度比很多人想象的重要。如果实在拿不准宁可按保守方向估计也不要高估信道质量。某些工程实现干脆省略σ²的精确估计直接用固定因子初始化然后靠迭代修正性能略差但鲁棒性更高这也是一种取舍。最后分享一个我在反复调参中总结的小技巧测试译码器时先用全零码字和零噪声输入跑一遍理想情况下所有LLR应该为正且一轮迭代后硬判决全对。如果这一步都过不了问题几乎一定出在初始化或消息索引上。等这个边界用例通过了再叠加噪声做性能曲线排错效率会高很多。推导公式的过程虽然枯燥但它会让你在调这些参数时清楚地知道自己在动哪块数学结构而不是拿着经验值瞎试。