LDPC如何把数据找回来？
LDPC是怎么把一个“读错的bit”找回来的？
上一篇我们认识了LDPC。它通过稀疏的校验矩阵H建立起大量的校验关系，再用Tanner图把这些关系表示成一张由bit节点和校验节点组成的网络。
但知道“谁和谁有关系”还不够。
真正的数据读取过程中，如果某几个bit已经发生了错误，LDPC到底怎样利用这张网络，把错误找出来？
答案是：让信息在bit节点和校验节点之间不断传递，并通过反复判断逐步逼近正确结果。这是LDPC解码的基本思路。
先从最直观的Bit-flipping开始
假设一个bit参与了多个校验方程。
如果它本身发生了错误，那么它参与的某些校验很可能无法通过。
例如，一个bit同时参与了5个校验，而其中4个都出现了异常。
那么很自然可以怀疑：这个bit很可能有问题。
于是，最直接的处理方式就是：把它翻转过来，再重新检查。
这就是Bit-flipping算法的基本思想。
它并不是先精确计算每一个bit出错的概率，而是通过校验结果寻找“最可疑”的bit，再尝试修正。
整个过程可以简单理解为：读取数据 → 检查校验 → 判断可疑bit → 翻转 → 再次检查
如果所有校验都恢复正常，解码就可以结束。
如果仍然存在错误，就继续下一轮。
为什么要反复进行？
因为一个bit发生变化之后，和它相关的多个校验结果也会随之变化。
这意味着：上一轮修正的结果，会影响下一轮的判断。
有时候，一次翻转就能让所有校验恢复正常；有时候则需要连续进行多轮调整。
因此，LDPC解码通常是一个不断迭代的过程：检查 → 判断 → 更新 → 再检查
直到满足停止条件。
最理想的情况是：所有校验方程都满足。
如果始终无法满足，也不能无限计算下去，因此实际解码器还会设置最大迭代次数。Bit-flipping很好理解，也很直观。但它还有一个明显的局限：它看到的主要是“结果”，却没有充分利用“结果有多可信”。
这就引出了另一种更重要的解码方式。
只知道0和1，还不够
在最简单的情况下，SSD读取一个bit之后，可以把它直接判断为：0 或者：1 。
这种方式叫硬判决（Hard Decision）。
硬判决实际上把原本更丰富的读取信息压缩成了一个结果：这一位，我认为是0。
但想象一下这样的情况。
某个存储单元读取出来的状态非常明确，几乎可以确定它是0。
另一个单元读取出来的状态则处在两个状态之间，虽然最终也被判断成0，但实际上并不是特别确定。
对于硬判决来说，它们最后得到的结果完全一样：都是0。
但对于纠错系统来说，这两种情况显然不应该被同等看待。
如果能够保留更多读取信息，ECC就可以知道：这一位不仅是0，而且这个判断到底有多可靠。这就是软判决（Soft Decision）。
软判决：不仅判断结果，还保留“可信程度”
软判决提供的并不只是一个简单的0或1，而是更丰富的信道信息。
可以把它简单理解成：
硬判决：这一位是0；
软判决：这一位更倾向于0，而且我对这个判断有较高或较低的把握。
这种信息对于LDPC非常重要。
因为当多个校验关系同时给出不同的判断时，解码器不仅可以参考“谁说是0、谁说是1”，还可以参考：谁的判断更可信。
这样，LDPC就能从更丰富的信息中不断更新对每个bit的判断。
这也是软判决通常能够获得更强纠错能力的重要原因之一。
不过，在SSD实际的数据恢复过程中，硬判决和软判决往往不是二选一的关系，而可以形成逐级增强的纠错手段。
让信息在Tanner图里流动
现在再回到Tanner图。我们前面说过：bit节点代表具体的数据bit。校验节点代表具体的校验关系。两者之间通过连线建立联系。
解码时，这些节点并不是静止不动的。它们会不断交换信息。
最开始，每一个bit都有一个来自NAND读取结果的初始判断。
然后：bit节点把自己的信息发送给相连的校验节点。校验节点根据自己的校验关系，对收到的信息进行判断。
如果发现当前组合满足校验条件，说明这些bit之间的关系是合理的；如果校验失败，则说明相关bit中至少存在一个错误。
于是，校验节点会把自己的判断反馈回去。bit节点收到来自多个校验节点的信息之后，再综合这些信息更新自己的判断。
然后进入下一轮。
整个过程可以理解成：读取信息 → 校验 → 反馈 → 更新 → 再校验
这就是所谓的消息传递（Message Passing）。
为什么这种方法能够工作？
关键在于：一个bit通常不会只接受一个判断。它可能同时连接多个校验节点。
因此，一个bit最终的状态，并不是由某一个校验节点决定，而是综合了多条校验关系提供的信息。
如果多个独立的校验关系都在“怀疑”同一个bit，那么这个bit出错的可能性就会不断提高。
反过来，如果多数校验关系都支持当前状态，那么保持原状态就更合理。
于是，错误信息会在Tanner图中不断传播。
经过多轮迭代之后，整个系统逐渐收敛到一个满足校验关系的状态。
和积算法：让“消息传递”有了数学依据
上面的过程很好理解，但真正实现时还要回答一个问题：这些消息到底应该怎么计算？
如果采用软判决，就不能简单地说“这个bit应该翻转”或者“不应该翻转”，而需要综合概率、可信度等信息。
其中一种经典方法，就是和积信息传播算法（Sum-Product Message Passing）。
你可以不用记住复杂公式。理解它最核心的思路就够了：
每个节点都把自己掌握的信息传给相邻节点，相邻节点再结合其他来源的信息进行重新计算，并把新的结果继续传出去。
以一个bit节点为例。假设它连接了3个校验节点。
来自校验节点1的信息认为：它更像0。
来自校验节点2的信息认为：它也更像0。
来自校验节点3的信息则认为：它可能是1。
那么bit节点就不会简单地“少数服从多数”，而是结合这些信息的可信程度重新计算：
这个bit究竟更可能是0还是1？
算出新的判断之后，再继续把结果传给下一轮的校验节点。这样不断重复，直到结果趋于稳定。这就是和积算法最核心的思想。
由于在具体的数学计算中，消息更新会反复出现两类基本操作：求和和相乘。不同路径上的信息会进行组合，再通过求和得到新的概率或权重。因此，这类算法被称为Sum-Product。而LDPC就是和积信息传播算法的经典应用之一。
总之，LDPC解码并不是“找到一个错误就结束”。实际的LDPC解码是：利用大量校验关系，让错误在不断的信息交互中逐渐暴露，并通过迭代不断修正结果。
从“算法有效”到“SSD真正可用”
现在回头看整个过程，我们已经可以把LDPC解码串起来了：
NAND读取数据→得到初始读取信息→硬判决或软判决→bit节点与校验节点交换信息→不断迭代更新→校验通过→恢复出原始数据
至此，我们终于完成了从上一篇“LDPC有一张怎样的校验网络”，到这一篇“这张网络究竟怎样工作”的跨越。
但问题又来了。
理论上的LDPC只需要考虑：能不能把错误纠回来？
可真正放进SSD主控以后，却还必须考虑另一组现实问题：纠错够不够强？处理速度够不够快？芯片占用的面积大不大？功耗和发热能不能接受？
下一篇，我们就从算法走进主控芯片，看看一个真正用于SSD的LDPC纠错引擎，究竟要面对哪些工程挑战。
