LDPC minSum Algorithm

[toc]

看过许多教科书，很多paper，其中描述LDPC的MinSum解码算法大都很简洁，细节程度不够，字母使用也各式各样，导致大家理解起来很吃力。于是，个人决定对这个基础算法做整理，采用比较容易理解，尽量有意义的字母表示方式来描述MinSum算法。同时，用Python程序来建模，希望以此能够对LDPC的MinSum解码算法的理解更加明晰。这里只描述最基础的算法，在这个基础算法上进行的改进和升级方法各式各样，文章颇多，不是入门学习所必须的。本文的目的是为了把问题描述清楚，而不是为了性能。

基础定义

对于稀疏矩阵H作为LDPC的校验矩阵，H维度为$M\times N$, M行代表有M个校验节点。 N列代表有N个变量节点。

变量节点使用VN表示(Variable Node)， 校验节点使用CN表示(Check Node).

对于坐标$(i,j)$, $i$代表行index，因为一行对应一个校验节点， 所以校验节点的index用字母$i$表示. $j$代表列index，每一列对应一个变量节点，因此，变量节点的index用字母$j$表示

$N(i), i=1,2,\ldots,M$表示和校验节点$CN_i$相连接的所有变量节点的集合。$N$表示其元素的取值范围是$【1,…,N】$

$M(j), j=1,2,\ldots,N$表示和变量节点$VN_j$相连接的所有校验节点的集合。$M$表示其元素的取值范围是$【1,…,M】$

算法

初始化

循环

Step 1: $VN_j$ to $CN_i$

Step 2: $CN_i$ to $VN_j$

每一个连接到变量节点$VN_j$的校验节点$CN_i$, 都有从$CN_i$传送到$VN_j$的信息$R_{i\to j}$.

对每个$CN_i$到固定变量节点$\cal{VN_j}$的信息$R_{i\to j}$, 使用所有变量节点到$CN_i$的信息，排除掉$\cal{VN_j}$到$CN_i$的信息. \(\forall j \in [1,\ldots, N]:\hspace{12em} \\ \hspace{12em} \forall i \in M(j) : R_{i\to j} = \prod _{j' \in [N(i)-j]} sign(Q_{j'\to i})\times Min(|Q_{j'\to i}|)\)

Step3: Update $L_j$

对每个变量节点$VN_j$, 在$M(j)$中任选一个$i$, 计算$L_j$: \(\forall j \in [1,\ldots,N]: select\ any\ i \in M(j), L_j = Q_{j\to i} + R_{i\to j}\)

Step 4: Check Valid