LDPC 低密度奇偶校验码的软判决译码算法浅析(二)--降低运算量
本系列文章列表：
LDPC 低密度奇偶校验码的软判决译码算法浅析(二)--降低运算量
LDPC 低密度奇偶校验码的软判决译码算法浅析（三）--算法和代码
LDPC 软判决算法之似然比形式 (三) tanh-lambda 规则
-----------------------------------------------------
这篇文章以及对应录制的视频，是对上面文章和视频的进一步完善。
在上面的文章和视频中，对 LDPC 软判决译码算法 的背后思想和数学公式做了一个初步的推导，大致明白了 LDPC 软判决译码算法的流程，但是，其中还有一个细节需要进一步优化，这个优化主要是为了降低运算量的。
录制了一个小视频来讲解这个文章：https://www.bilibili.com/video/BV1B24y1Z7BY/
本篇文章和对应的视频，属于 “续集”，建议看完前面的文章和视频后再看。
在前面的文章中，我们根据各个比特的概率，来估算各个校验方程成立的概率，得出如下的公式：
这个公式看起来很吓人！
首先，这个公式的含义是计算校验方程成立的概率，即校验方程 $z_m=0$ 成立的概率，给定的条件是 第 n 个 比特的值已知，以及收到的数据 r ，这里的 r 是一个向量。
其次，这个方程的右边，涉及到的是这个校验方程中含有的比特取值 0 或者 1 的概率，把这些比特相关的概率做相乘及求和等动作，完成对校验方程成立的概率的估计。
下面还是用例子来说明比较好。
假设 LDPC 用的校验矩阵如下，本篇文章都是以这个校验矩阵为例子（这个例子与前面文章的例子是相同的）。
我们译码出来的码字表示成向量形式：
这个译码出来的码字，不是指发送的正确的码字，是表示我们待译码出来的，例如，我们可能想评估 的可能性（概率）。
我们把接收到的数据表示为一个向量：
5 个校验方程为：
假如我们在考虑比特 2 取值 为 1 的概率，那么上面公式 (1) 中的 就是 n=2, x=1,
， 进一步假如咱们考虑的是第一个校验方程，则公式 (1) 中的
，
就是一个下标的集合，表示第 m个校验方程中，含有的比特的下标，但是不包括下标 n 的。在这个具体的例子中，就是 m=1 个校验方程中，除了比特 n=2 之外的那些比特的下标，
.
重写公式(1)
求和的部分，是对所有能使第 m=1 个校验方程成立的那些比特，都要做一次求和，总共有以下这么多情况：
因为 了，所以，要使第 m=1 个校验方程成立，则其它 5 个比特，需要有奇数个 1，即
这 5 个比特中应该有奇数个 1.
则含有 1 个 1 的有 5 种情况：含有 3 个 1 的有 10 种情况：
含有 5 个 1 的就 1 种情况：
总计 16 种情况。
对这 16 种情况中的任何一种，都需要再做一个连乘。例如：， 需要做的连乘为：
所以，总的计算量就是 16x4=64个乘法（还有几乎可以忽略的15个加法）：
其实，从上面的计算，我们也可以看到很多冗余的，例如上面第一个连乘和第二个连乘中，前三个元素相乘都是相同的，可以只计算一次。那么，我们如何来优化掉这些冗余呢？牛人们推导出了一个简洁的公式。
先引入一个临时函数：
求和公式中下标有点多，不容易看清楚，求和是对 x 求和，只是下标不同，下标为： ，以前面的例子看，这个
则：
所以，例如当 k = 3时：
其中， 表示的是
的取值。
我们把 中元素的个数记为 L.
那么，可以形成一个如下所示的图：
若 (其中 x 是
的取值)，则这种情况是被考虑到进来的，否则，这种组合就不用考虑，不用展开连乘并参与到累加中。继续上面的例子，因为
， 所以 L=5.
要考虑的 ，所以，
的组合是我们需要考虑的，也就是凡是满足
的组合是我们需要考虑的，这就是前面 “不厌其烦” 列出来的那 16 种情况的公式表达。
下面开始推导关键的递推公式，利用这个递推公式，就可以简化计算，消除计算过程中的冗余了(这里先用上面的例子来讲解，最后再总结成通用的公式)
首先令
那么 ，就依赖于
的取值
然后 , 就依赖于
的取值
然后 , 就依赖于
的取值
然后 , 就依赖于
的取值
最后 , 就依赖于
的取值.
为了书写方便，我们再引入一个记号 , 表示在上面图形的第 k 步，或者说加到第 k 个数时 结果为 x 的概率。在例子中 x =1 ，那么
表示的是
的概率
表示的是
的概率
表示的是
的概率
表示的是
的概率
表示的是
的概率
因为是 从 0 开始的，所以，，即在 0 节点上，等于 0 的概率是 1， 等于 1 的概率是 0.
我们来看一下：
节点 1 上 等于 0 的情况有两种：
节点 0 上等于 0，且
节点 0 上等于 1，且
则
同理：
那么：
依次类推，则：
用上面两个式子相减：
同理可得：
其中：
把递推公式逐级代回去，则有：
而
又有
则可以把 都解出来。
为了书写方便，我们令：
则解出来的结果可以表示为：
我们来看一下计算量，有 4 个乘法，6 个加减法，以及一个除以 2（可以右移实现），相比之前的 64 个乘法，运算量小了很多。
前面，用具体的例子先做了一个推导。从具体例子的推导和分析中，我们可以得到更一般的递推公式。
令：
递推公式为：
两式相减，则：
这个递推公式一直推下去，则有：
那么，若 L 是 中元素的个数，则：
前面咱们所有的推导，其实都隐含这一个背景条件：“就是在收到数据 r 的条件下“。把这个条件加上变成条件概率，则：
另外，
则公式(2)递推公式就推导为：
又因为
所以，容易把 和
解出来。
所以，运算量大致等于 L-1 次乘法.
这样，我们就得到了公式 (1) 简化算法。
