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】$

$R_{i\to j}$ 表示从校验节点$CN_i$传给变量节点$VN_j$的概率信息。

$Q_{j\to i}$ 表示从变量节点$VN_j$传给校验节点$CN_i$的概率信息。

$L_j$ 表示变量节点$VN_j$的总概率信息。

$LLR_j$ 表示从Channel中获得的概率信息，作为解码的初始输入。

算法

初始化

循环

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} = \alpha\prod _{j' \in [N(i)-j]} sign(Q_{j'\to i})\times \min_{j' \in [N(i)-j]}(|Q_{j'\to i}|)\)

Step3: Update $L_j$

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

Step 4: Check Valid

Python实例

以一个简单的准循环校验矩阵为例. 单位循环矩阵$I$大小为$6\times6$,即：

用一个数字$k$表示循环子矩阵，$k$的值表示对$I$进行了多少步的列循环右移 。以如下校验矩阵H为例子：

H矩阵的实际大小为$(36)\times(66)$。None代表全0矩阵。

此矩阵不是行满秩矩阵，Rank(H) = 17, 因此是一个(36, 19)线性码, 校验位有17位。