LDPC 低密度奇偶校验码的软判决译码算法浅析(一)
本系列文章列表：
LDPC 低密度奇偶校验码的软判决译码算法浅析(二)--降低运算量
LDPC 低密度奇偶校验码的软判决译码算法浅析（三）--算法和代码
LDPC 软判决算法之似然比形式 (三) tanh-lambda 规则
-----------------------------------------------------
本篇文章目的是简单易懂地介绍 LDPC 码的软判决译码。本人在开始学习 LDPC码时遇到最大的困惑是软判决译码中 “消息传播” ，很多书一上来就给出 “消息传播” 算法的具体描述，可为什么 “消息传播” 算法是那个流程，为什么能起作用？其背后有原理（数学原理）支撑吗？鲜有耐心详细的说明的，幸好，我挖掘到一本书 [1]，介绍得比较好，本文就是以这本书的内容为蓝本写就的.
本人在哔站上录制了一个视频，做了简单讲解：
https://www.bilibili.com/video/BV1AT411u7WJ/
在读者已经了解线性分组码的基本概念，以及校验矩阵的基础上，有概率方面的基本知识，就可以读懂本篇文章。建议读者在阅读本篇文章前，阅读一下本人写的关于比特翻转译码算法，可以领会一下背后的思想，对理解本篇文章有帮助。当然，不阅读比特翻转译码算法的文章，也完全可以理解本篇文章。
假设 LDPC 用的校验矩阵如下，本篇文章都是以这个校验矩阵为例子。
我们译码出来的码字表示成向量形式：
这个译码出来的码字，不是指发送的正确的码字，是表示我们待译码出来的，例如，我们可能想评估 的可能性（概率）。
我们把接收到的数据表示为一个向量：
特别说明一下，这里讲的接收的数据，并不是已经硬判决出来的 0 或者 1 ，而是通过信道传输过来后的小数。发送端发送的是 0 或者 1 ，但是，由于信道噪声的干扰，收到的数据是各种可能，从负无穷到正无穷都是有可能的，只是越偏离原始发送的数据则可能性越小而已，假如发送的是 1，则收到是 105.7 的可能性要比收到 1.1 的可能性要小得多。例如，可能收到的数据如下：
根据信道的特点，例如是高斯白噪声信道，我们根据接收到的上面的那些小数，可以计算出一个后验概率，例如，可以计算出：在收到 的条件下，
的概率，写成概率公式为：
用 表示这种后验概率。
如果我们直接用这个后验概率来判决 还是
，则没有利用码字内部各个比特之间是有关联的，那就没有使用编码带来的好处。
那么，有哪些关联的性质呢？即有哪些约束条件的？
根据线性分组码相关的原理，我们知道有如下的校验方程：
计算后的结果 z ，是一个含有5个元素的向量，记为：
为了易于理解，我们把上面这个矩阵形式的方程，展开成 5 个校验方程：
如果译码正确，则所有的方程都是等于 0 的。如果不是正确的码字，则上面的校验方程中至少有一个是不等于 0 的。
由于软判决没有直接判决出码字，然后来检验校验方程是否满足。使用软信息，咱们来判断各个校验方程成立的概率，然后有了各个方程是否成立的概率，来计算码字中各个比特 等于 0 或者等于 1 的概率。
咱们一点点来推导。
咱们知道，最佳译码是找下面这个概率最大的：
说明： 是 所有的校验方程都成立的意思。
例如：在满足校验方程和收到的数据为 r 的条件下
则可以计算概率
注意：上面公式中 r 是含有 10 个元素的向量，是接收到的数据。
那么，把所有满足校验方程的 c 都计算一遍上式的概率，在这些概率中选择最大的那个作为译码结果。
缺点：如果分组码中每个组中数据比特数量是 k, 编码后的长度为 n (例如上面例子中 k= 5, n = 10)，则需要计算 个概率出来，对于分组码长度为几百这种量级的，则这个计算量非常非常大，完全不可行。因此，需要一种折中的快速算法。
第一种折中，咱们先按照单个比特最优的角度来开始，咱们求解下面的概率：
对于二进制的传输数据，上面公式中的 x 要么取 0，要么取 1.
咱们对上面的公式进行一些推导，推导成这个概率是用 的概率来表示，即用校验方程成立的概率来表达对这个比特等于 0 或者 1 的概率。
上面的公式中，分母的部分是与 无关的项，可以认为是一个常数。
对分子中的两项，做进一步的简化（其实是一种近似）
第一: 令 即假设接收到的其它的数据(除了
以外的)不影响
的判决，这当然是一种简化，因为考虑校验方程的约束，其它数据的取值，对当前
的判断是可以给出更多信息的。这个概率，已经与 LDPC 码无关了，只由信道的特点决定。（有网友认为这里不是近似，因为校验方程的条件，在公式推导过程中已经被拿掉了，好像也有道理，我写在这里，大家自己来多思考一下吧）
第二：假设 参与的校验方程，在
以及收到 r 的条件下，各个校验方程是独立的，统计上独立的。这个只有在这些校验方程中，除了
以外，没有其它共同参与的比特 的情况下才成立。在实际的 LDPC 码的校验矩阵中，是无法保证的。因此，这个也是一种简化。 在这个假设的条件下，分子中的项可以展开为：
那么：
至此，我们已经走到了一个比较重要的步骤，或者说得到了一个比较重要的思想：
用校验方程成立的概率，来表达或者说来计算 的概率。这个与比特翻转算法的思想有点类似，再比特翻转算法中，校验方程不成立的个数，决定了参与这些校验方程的比特的出错的可能性。参与到错误校验方程的个数越多，这个比特出错的可能性越大。在上面的公式中，也可以看到这个思想的影子。校验方程成立的可能性越大，则可以看出来
的可能性就越大。
咱们举个例子来理解上面这个公式，在前面的 LDPC 码校验方程中，咱们考虑正在估计 的概率，
参与的校验方程有
这三个。
则估计 的概率可以表示成：
而上面式子中分子部分的左边第一个概率，在假设 相互独立的假设下，又可以展开为三个概率的乘积：
-------- 例子公式(1)
=========================================================
如果至此都理解了，咱们可以开始往下推导了。现在来看如何判断校验方程成立的概率呢？即
这个怎么计算呢？或者说如何估计呢？
咱们来解读一下上面这个公式，这个公式是估计 成立的概率，也就是这个第 m 个校验方程成立的可能性。我们可以很自然地理解，这个概率肯定与
检验方程中包含的比特有关，又由于前面的公式是一个条件概率，其中一个条件是
，这个是确定的。因此，评估上面这个概率，就只需要考虑这个校验方程含有的比特，除了
以外的那些比特。
下面，咱们做一些公式的推导，把其它参与的比特考虑进来：
首先用全概率公式：
对上面 "例子公式(1)" 右边的三个概率，分别都使用全概率公式展开。现在对第一个( ) 展开作为例子来说明。
这个校验方程，除了
参与了之外，还有
这 5 个比特参与，现在对这 5 个比特的取值进行全排列，每个取 0 或者 1，则有
种情况：
从上面举的例子容易看出来，在 的条件下，要求
，则可以看到上面的
中情况中并不是都成立，只有
这 5 个比特中有偶数个 1 才成立。
另外，公式(1) 中的 ，在所有
确定的情况下，
已经与 r 无关，因此：
因此公式(1)可以写成：
补充说明一下上面这个公式：其中的 是取
这个校验方程中参与的比特，除了
。 如在例子中第一个校验方程
，参与的比特有
，假如
是
，且 x=0，即
，那么
的取值就是
. 则上面公式的右边，需要考虑的就是
然后，这 5 个比特的取值，就是要满足
. 那么，上面的公式就可以展开为：
为了进一步简化，对公式 (2) 又做了一个假设，即 相互独立，则公式(2) 就可以变为：
对上面例子中的 ，假设
相互独立，则：
至此，公式(3) 中的 可以用
来代替，显然这里也是用了一个近似，则公式(3) 就可以计算出来，然后代入公式 (0) ，就可以计算出
此时就可以对比特
进行判决：
那么对所有的 ，都做一遍上面的流程，则
就都判决出来了。因为，上面的计算中用了几个假设和简化，这次判决出来的结果代入校验方程，可能不是所有的校验方程都成立。那么，我们要采取一些办法，来再做一次尝试。如果还是按照上面的流程做一遍，那还是会得到相同的结果，我们自然可以想：能否利用上一轮估计出来的某些参数，来做这一轮的尝试？利用上一轮的结果，把某些估计的概率能更准确一些？
咱们来看公式 (3)，对于公式 (3) 中右边乘法的部分 , 在第一轮中，是用
来近似的，这里没有考虑
参与的校验方程成立的可能性，如果把这个因素考虑进去，我们可以想到，应该能提高对
估计的准确性。因此，我们可以用下面的公式，来进一步提高估计的准确性：
因为在公式 (3) 中等号的左边，已经是假设 ，因此上面公式中的
要排除
这个校验方程。上面公式的右边，利用公式(0) 的推导方式，又可以转化为由
计算出来，这样，利用第一轮计算出来的关于校验方程成立的概率
，来递归循环第提高
的准确率。
[1] Error Correction Coding--Mathematical Methods and Algorithms , Todd K. Moon, Wiley, 2005 ，主要参考第 15.5 章节。
