LDPC低密度奇偶校验码的比特翻转译码浅析
本系列文章列表：
LDPC 低密度奇偶校验码的软判决译码算法浅析(二)--降低运算量
LDPC 低密度奇偶校验码的软判决译码算法浅析（三）--算法和代码
LDPC 软判决算法之似然比形式 (三) tanh-lambda 规则
-----------------------------------------------------
LDPC码（low-density parity-check）实际上就是一种线性分组码，但是，由于LDPC码的 low-density 特性，可以用比较高效的算法来实现译码。这篇小文不是探讨 LDPC 码的方方面面，而是在读者已经了解线性分组码的基本概念，以及校验矩阵的基础上，试图对 LDPC码中一个简单的译码算法进行一个描述。在 Gallager 博士论文 [1] 中非常简要描述了一种称之为 Bit-Flipping 的 hard decoder 方法来译码。下面这段英文摘自 Gallager 博士论文 [1] :
（在哔站本人录制了一个小视频，做简单讲解：
https://www.bilibili.com/video/BV1C24y1Z7Uf/ ）
......, the decoder computes all the parity checks and then changes any digit that is contained in more than some fixed number of unsatisfied parity-check equations. Using these new values, the parity checks are recomputed, and the process is repeated until the parity checks are all satisfied.
下面举个例子来具体说明这个过程。
假设校验矩阵是：
把接收到的码字表示为一个向量：
则根据收到的码字 ，可以计算出伴随式 syndrome（这个词在医学里面是症状的意思，在这里，可以理解为用来“诊断”接收到的码字是否有错误，以及诊断哪些校验方程是没有被满足的）：
计算后的结果 ，是一个含有5个元素的向量，记为：
为了易于理解，我们把上面这个矩阵形式的方程，展开成 5 个校验方程：
现在，我们举一个具体的例子，发送一个码子，接收到的码字有一个错误，用 bit-flipping 算法做一个译码。
发送的码字为：
接收到的码字有错误：
可以看到 是有错误的。下面，用 bit-flipping 算法，尝试做一个译码：
第一步，计算出伴随式：
注：上面是模 2 加法， 1+1=0
第二步，看伴随式是否都为 0 ，若都为 0 ，则结束译码，此时的 就是正确的码字；如果伴随式不为0，跳到第三步。
第三步，看 到
分别在哪几个校验方程中出现，在出现的校验方程中，有几个校验方程是不满足的，即不等于0.
出现在
中，其中
，因此，出现
的校验方程中有 1 个方程不满足；
出现在
中，其中
，因此，出现
的校验方程中有 1 个方程不满足；
以此类推，可以列出如下这个表格：
在 "不满足的校验方程的个数" 中选择最大的，上表中最大的是 3 ，对应的是 所在的那一列，因此，把
从 1 翻转（Flipping）成 0，接收到的码字被翻转后，记为新的
. 跳转到第一步继续执行。
此时的 为：
再来计算伴随式 ，得出的结果为
译码结束。
正确的码字为：
可见，与最初的发送码字相同：
通俗来理解，这种迭代算法，就是考虑收到的码字中的比特，如果参与的校验方程中，越多的方程不满足，则越说明这个比特出错的可能性比较大，优先对这个比特进行翻转来尝试。
以前一直不太理解的 sum-product 方法的思想，现在似乎有所领悟。上面是一种硬判决，如果换成软判决，则考虑的是每个校验方程不满足的 “概率”，从绝对的满足与不满足，换成了满足或不满足的概率。进而来计算每个参与的比特，在各个校验方程中，不满足的概率，找出概率最大的那个进行某种修改。
[1] R.G.Gallager, Low-Density Parity-Check Codes, *IRE Trans.Info.Theory* IT-8:21-28. 1962.
