LDPC minSum Algorithm

[toc]

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

基础定义和数据结构

对于稀疏矩阵H作为LDPC的校验矩阵，H维度为$M\times N$, M行代表有M个校验节点。 N列代表有N个变量节点。(python代码中用row表示M, col表示N)

举例：如下是一个18*36的稀疏矩阵，每行有6个1，每列有3个或2个1.是非规则稀疏矩阵。

H = \
 [[1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0]
  [0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0]
  [0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0]
  [0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0]
  [0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0]
  [0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1]
  [0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0]
  [0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0]
  [0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0]
  [0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
  [1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1]
  [0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0]
  [1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0]
  [0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
  [0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
  [0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
  [0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
  [0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0]]

变量节点使用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】$

对$H$矩阵中任意一个不为0的元素 $h_{ij}$, 表明 i属于M(j),且 j属于N(i). 也就是说，如果$i\in M(j) \iff j \in N(i)$

row, col = 18, 36
M = [[0, 10, 12],
 [1, 11, 13],
 [2, 6, 14],
 [3, 7, 15],
 [4, 8, 16],
 [5, 9, 17],
 [0, 9, 16],
 [1, 10, 17],
 [2, 11, 12],
 [3, 6, 13],
 [4, 7, 14],
 [5, 8, 15],
 [0, 8, 17],
 [1, 9, 12],
 [2, 10, 13],
 [3, 11, 14],
 [4, 6, 15],
 [5, 7, 16],
 [0, 7, 13],
 [1, 8, 14],
 [2, 9, 15],
 [3, 10, 16],
 [4, 11, 17],
 [5, 6, 12],
 [0, 6],
 [1, 7],
 [2, 8],
 [3, 9],
 [4, 10],
 [5, 11],
 [0, 11, 15],
 [1, 6, 16],
 [2, 7, 17],
 [3, 8, 12],
 [4, 9, 13],
 [5, 10, 14]]

N = [[0, 6, 12, 18, 24, 30],
 [1, 7, 13, 19, 25, 31],
 [2, 8, 14, 20, 26, 32],
 [3, 9, 15, 21, 27, 33],
 [4, 10, 16, 22, 28, 34],
 [5, 11, 17, 23, 29, 35],
 [2, 9, 16, 23, 24, 31],
 [3, 10, 17, 18, 25, 32],
 [4, 11, 12, 19, 26, 33],
 [5, 6, 13, 20, 27, 34],
 [0, 7, 14, 21, 28, 35],
 [1, 8, 15, 22, 29, 30],
 [0, 8, 13, 23, 33],
 [1, 9, 14, 18, 34],
 [2, 10, 15, 19, 35],
 [3, 11, 16, 20, 30],
 [4, 6, 17, 21, 31],
 [5, 7, 12, 22, 32]]

$R_{i\to j}$ 表示从校验节点$CN_i$传给变量节点$VN_j$的概率信息。用python二维List表示，List里面元素也是List.

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

R = np.zeros((row, col), dtype=float)
Q = np.zeros((col, row), dtype=float) # 尺寸等于R的转置的尺寸

$L_j$ 表示变量节点$VN_j$的总概率信息。用来做最后的判断

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

算法

初始化

\[\forall j \in [1, \ldots, N]:\\ \hspace{4em} L_j = LLR_j \\ \hspace{8em} \forall i \in M(j) : R_{i\to j} = 0\]

循环

Step 1: $VN_j$ to $CN_i$

\[\forall i \in [1,\ldots, M]: \\ \hspace{12em} \forall j \in N(i) : Q_{j\to i} = L_j - R_{i\to j}\]

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

\[\forall j \in [1,\ldots,N]: \overline x_j = \left\{ \begin{array}{ll} 0 & \textrm{if $L_j\ge 0$}\\ 1 & \textrm{else}\\ \end{array} \right. \\ if\quad H\overline X = 0: output(\overline X);\quad return \quad Success\\ if\quad maxIteration : return \quad Fail\]

Python实例

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

0	0	0	0	0
1	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

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

0	0	0	0	0	0
2	3	4	5	0	1
0	2	1	5	None	3

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

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

芯有所想

about