LDPC

LDPC 码的基本原理 | 带你读《5G-NR信道编码》之七

LDPC相对于 turbo 码的优势就在于

  • 没有低权重码字：码字的hamming距得以增大，获得更小的误码率
  • 低复杂度的交互式解码：使用简单的校验 网格

ldpc码可以是系统码也可以是非系统码，关键看你是如何编码的。换句话说，同样的校验矩阵可以用作系统码也可以用作非系统码。这主要根据 G 矩阵的产生方式。

构造 LDPC

LDPC 码的校验阵为稀疏矩阵 A，即 0 的数量远大于 1。

通常用 (n,tc,tr)(n, t_c, t_r) 来描述一个 LDPC 码，其中 nn 为分组长度，tct_c 为各列码重，trt_r 为各行码重，且 tr>tct_r>t_c。

有 r=1−tctrr=1-\frac{t_c}{t_r}

还需检验有效性：令 ρ\rho 代表 A 中 1 的密度，则可得 tc=ρ(n−k),tr=ρnt_c=\rho(n-k), t_r=\rho n，其中 n - k 为 A 的行数，n 为列数（譬如分段长）
故有 tctr=1−kn\frac{t_c}{t_r}=1-\frac{k}{n}

规则 LDPC 和非规则 LDPC

LDPC 码可以用二分图表示，其中有两种节点：变量节点 和 校验节点

  • 规则 LDPC：每个校验节点连接的变量节点数（3）一致，每个变量节点连接的校验节点数（2）也一致；即：每行有 3 个非零元素，每列有 2 个非零元素
  • 非规则 LDPC：每个节点的自由度可以不一样，但是需要满足：

变量节点自由度λ(x)=∑i=2dvλixi−1变量节点自由度\lambda(x)=\sum^{d_v}_{i=2}\lambda_ix^{i-1}

校验节点自由度ρ(x)=∑i=2dcρixi−1校验节点自由度\rho(x)=\sum^{d_c}_{i=2}\rho_ix^{i-1}

系数λi\lambda_i和ρi\rho_i分别表示自由度为ii的从变量节点和校验节点发出的边数所占的比例

然而实际上非规则 LDPC 更灵活，更常用

置信传播

原文链接：https://blog.csdn.net/sinat_38151275/article/details/98102699

译码过程是在变量节点和校验节点之间传递信息。每个变量节点告诉它所连接的校验节点“我认为该变量是什么”，而校验节点告诉它所连接的变量节点“我认为该变量应该是什么”。经过反复的消息传递后，变量节点和校验节点不断改变自己对各个变量是什么的看法，最终能形成一个满足校验方程的码字，这就是译码的结果。如果经过充分的迭代后仍然不能形成一个满足校验方程的码字，则译码器宣布它无法译出这个码字，即译码失败。

Min-Sum

Min：VN到CN，Sum：CN到VN

公式前提：

  • 三比特校验式：L1⊞L2⊞L3=0→L1⊞L2=L3L_1{\boxplus}L_2{\boxplus}L_3=0{\rightarrow}L_1{\boxplus}L_2=L_3
  • 似然比输出：L3=L1⊞L2=log⁡P(x3=+1)P(x3=+1)=log⁡1+eL1eL2eL1+eL2L_3=L_1\boxplus{L_2}=\log\frac{P(x_3=+1)}{P(x_3=+1)}=\log\frac{1+e^{L_1}e^{L_2}}{e^{L_1}+e^{L_2}}
  • ⊞\boxplus运算：L1⊞0=0,L1⊞±∞=L1L_1\boxplus0=0,L_1\boxplus\pm\infty=L_1
  • 最小和近似：L3=sgn⁡(L1)⋅sgn⁡(L2)⋅min⁡(∣L1∣,∣L2∣)+log⁡(1+e−∣L1+L2∣)−log⁡(1+e−∣L1−L2∣)≈sgn⁡(L1)⋅sgn⁡(L2)⋅min⁡(∣L1∣,∣L2∣)L_{3}=\operatorname{sgn}\left(L_{1}\right) \cdot \operatorname{sgn}\left(L_{2}\right) \cdot \min \left(\left|L_{1}\right|,\left|L_{2}\right|\right) +\log \left(1+e^{-\left|L_{1}+L_{2}\right|}\right)-\log \left(1+e^{-\left|L_{1}-L_{2}\right|}\right) \\ \approx \operatorname{sgn}\left(L_{1}\right) \cdot \operatorname{sgn}\left(L_{2}\right) \cdot \min \left(\left|L_{1}\right|,\left|L_{2}\right|\right)

BP算法校验节点计算：

rmnk=∑n′∈B(m)\n⊞qk−1n′mr_{m n}^{k}=\sum_{n^{\prime} \in B(m) \backslash n}^\boxplus q^{k-1} n^{\prime} m

MS算法校验节点计算：

  • 校验节点对于变量节点i，输出除i以外的其它变量节点的最小和近似。如图中，−0.17=sgn(3.57)⋅sgn(−0.17)⋅min{∣3.57∣,∣−0.17∣}-0.17=sgn(3.57){\cdot}sgn(-0.17){\cdot}min\{|3.57|,|-0.17|\}

rmn,MSk=(∏n′∈B(m)\nsgn⁡(Ln′mk−1))min⁡n′∈B(m)\n∣qn′mk−1∣r_{m n, MS}^{k}=\left(\prod_{n^{\prime} \in B(m) \backslash n} \operatorname{sgn}\left(L_{n^{\prime} m}^{k-1}\right)\right) \min _{n^{\prime} \in B(m) \backslash n}\left|q_{n^{\prime} m}^{k-1}\right|

变量节点计算：

  • 变量节点将上一次迭代中从各校验节点接收到的值与自身值相加。如图中，6.17=−0.80−0.17+3.57+3.40+0.176.17=-0.80-0.17+3.57+3.40+0.17
  • 本次迭代中，变量节点向校验节点j输出的值是上式计算出的值减去上次校验节点j向本变量节点输出的值。如图中，6.34=6.17−(−0.17)6.34=6.17-(-0.17)

MS算法初始化计算：（与信道噪声方差σ2\sigma^2无关）

qnm0=ynq^0_{nm}=y_n

迭代直到与H相乘为0

下图以发送全零信息为例，绿色为0，红色为1

NMS

Normalized Min-Sum，似乎是直接在 LL 上除以一个大于1的系数即可，而这个系数貌似是定死的。后期演变为ANMS（自动NMS），能够自动调整这个系数。

SPA

（其实应该先讲 SPA 再讲 MS 的）

MS 与 SPA 唯一不同点就在于校验节点的计算。实质上，MS 是 SPA 的简化版，它将 SPA 中的非线性的 tanhtanh、atanhatanh 的运算转换为了简单的取最小值。

SPA 的校验节点计算：

rmn,SPAk=2×atanh⁡(∏n′∈B(m)\ntanh⁡(Ln′mk−12))r_{m n, SPA}^{k}=2\times\operatorname{atanh}\left(\prod_{n^{\prime} \in B(m) \backslash n} \operatorname{tanh}\left(\frac{L_{n^{\prime} m}^{k-1}}{2}\right)\right)

常见常识

  • 编码后的信噪比：EsN0=EbN0∗rate,rate=KN\frac{E_s}{N_0} = \frac{E_b}{N_0} * rate,rate=\frac{K}{N}

NB-LDPC

多元 LDPC 也即是在 GF(q),q=2p,p>1\mathbf{GF}(q),q=2^{p},p>1 的有限域下实现的 LDPC。

GFq

有限域，又叫 伽罗瓦域（Galois Field）

以 GF(4)\mathbf{GF}(4) 为例，有限域由 0,1,α,α20,1,\alpha,\alpha^2 组成。在 LDPC 中，通常用 0，1，2，3 这四个十进制数来表示。

有限域的计算法则如下：

  1. α2=α+1\alpha^2=\alpha+1
  2. 系数 mod 2

以简单的加法为例：
1+α2=1+α+1=α+2=α1+\alpha^2=1+\alpha+1=\alpha+2=\alpha

由此便可得到如下两表（取自维基百科）

+ | 0 1 2 3       ·| 0 1 2 3
--+--------       --+--------
0 | 0 1 2 3       0 | 0 0 0 0
1 | 1 0 3 2       1 | 0 1 2 3
2 | 2 3 0 1       2 | 0 2 3 1
3 | 3 2 1 0       3 | 0 3 1 2

所以这些运算常常用查找表来实现，速度快，也很直观。

到底是怎么回事！

参考 伽罗华域(Galois Field，GF，有限域)

好吧，前面的都没讲通，归根结底 GF(q)\mathbf{GF}(q) 就是 n=log⁡2qn=\log_2{q} 位二进制数，加减法和乘除法都没有进位（也就是模2）。
遇到结果溢出时，就用 本原多项式 把它化归到 n 位内，形成健全的有限域。

那么什么是本原多项式呢？本原多项式可以理解为模2下的素多项式，即：

  1. 不能因式分解

列表参考百度百科列出的如下图片：

重新回到前面 GF(4)\mathbf{GF}(4) 的例子中。
显然，0 = 00, 1 = 01, 2 = 10, 3 = 11，那么，1 + 3 = 01 + 11 = 10 = 2 就理解得通了（不就是直接异或吗喂喂！）；
而减法其实就是加法，因为异或本身就是它自己的逆运算；
再看乘法，2 * 3 = 10 * 11 = 100 + 10 = 11 + 10 = 01 = 1，其中 100 = 11 是根据本原多项式 x3+x+1x^3 + x + 1 得到的。

为什么我看到的和你说的不一样！

因为实际应用的时候，具体一个十进制数究竟代表哪个多元域的数，有不同的实现方式。

一种方法是 十进制数 dd 代表 αd−2\alpha^{d-2}，d=0d=0 时代表 00。这种方法被称为 Power 表示，常在论文中使用。
而还有一种所谓 Vector 表示，也叫 多项式 表示，经常在以 MATLAB 为主的代码实现中使用。这种方法以下图中第三栏中向量的最左为低位，最右为高位，所以 α9=10\alpha^9=10
上一节中由于使用的是 GF(4)\mathbf{GF}(4)，两种方法是一致的。

  • Power 表示的加法需要查表，或者转换到 Vector 后异或；而乘法则直接相加
  • Vector 表示的加法直接异或，乘法则同样用查表或者转换到 Power 后相加

有限域带来的麻烦

引入有限域后，许多原本理所应当的操作变得不直观起来。以下会按照 编码-调制解调-解码 来一一观察。

编码：
改用有限域后，由于生成矩阵一般都使用有限域表示，所以信息序列也需要用有限域表示。至于二进制和有限域之间如何转换，只要前后一致即可。

调制解调：
一般使用高阶调制，即一个有限域符号与调制的一个星座点对应，这样性能最好；而如果仍使用 BPSK 等二元调制，则需要将码字转回二元进行调制。

解码
解码时，若使用的二元调制，就要先算出各比特的 LLR，再合成有限域符号的 LLR。而高阶调制则可以直接生成符号 LLR。

LLR(b)=log⁡Pr(b=0∣r=(x,y))Pr(b=1∣r=(x,y))LLR(b)=\log\frac{Pr(b=0|r=(x,y))}{Pr(b=1|r=(x,y))}

AWGN 下的 LLR 计算可以参考 Matlab 文档