编码理论第十一章：LDPC码原理学习及其习题分析

参考：管武老师的课件习题-2022编码理论-11-LDPC码.PPT

• 1. LDPC码概述
• 2. LDPC码描述方法
• • 2.1 校验矩阵H
  • 2.2 二分图（tanner图）
  • 2.3 度分布函数
• 3. LDPC码的编码方法
• 4. LDPC的译码算法
• • 4.1 高斯消去法——peeling decoder（硬判决）
  • 4.2 和积算法（硬判决）
  • 4.2 置信传播算法（软判决）
• 5. 习题分析-和积算法

  低密度校验码（LDPC码），一种前向纠错码（前向纠错指利用发送端信道编码添加冗余的方式使得接收端解码时会自动纠正传输误码）。

特点：

1. 校验矩阵的稀疏性使得译码复杂度和最小码距随码长n线性增长。
2. AWGN信道中的仿真结果：采用密度演进分析得到在码长趋向无穷时传输速率距离香农极限0.0045dB

LDPC属于(n,K)线性分组码
举例一个源码： s = ( c 1 c 2 c 3 ) s=left(begin{array}{lll}c 1 & c 2 & c 3end{array}right) s=(c1​c2​c3​)→LDPC码： C ( s ) = ( c 1 c 2 c 3 c 4 c 5 c 6 ) C(s)=left(begin{array}{llllll}c 1 & c 2 & c 3 & c 4 & c 5 & c 6end{array}right) C(s)=(c1​c2​c3​c4​c5​c6​)的过程，不妨假设 G n ∗ K = ( 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 ) G_{n*K}=left(begin{array}{llllll} 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 1 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 end{array}right) Gn∗K​=⎝⎛​100​010​001​110​011​111​⎠⎞​，一般来说LDPC 码会更稀疏，这里仅作为一个例子供后续理解。

校验矩阵 H ( n − K ) ∗ n H_{(n-K)*n} H(n−K)∗n​

特性：

1. 每一行表示一个校验方程约束，包含k个码元
2. 每一列表示一个码元参加 j个校验方程
3. 任意两个校验方程包含至多一个相同码元

  如果上述 j、k为常数（一般来说 k ＞ j），即每一行都有 j 个1，每一列都有 k 个1，则为规则LDPC码，可记为(n，j，k)正则LDPC码；反之，如果每一行或者每一列中的j、k不固定（出现了不相等的情况），则为非规则LDPC码。

在sec2开篇的例子中， H ( n − K ) ∗ n = ( 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 ) H_{(n-K)*n}=left(begin{array}{llllll} 1 & 1 & 0 & 1 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 \ 1 & 1 & 1 & 0 & 0 & 1 end{array}right) H(n−K)∗n​=⎝⎛​101​111​011​100​010​001​⎠⎞​，显然每一列的j的数目不相等，所以这是个不规则的LDPC码编码。如果没有收到干扰，接受端 y = C ( s ) y=C(s) y=C(s)存在 y 1 ∗ n { H T } n ∗ ( n − k ) = 0 y_{1*n}{H^T}_{n*(n-k)}=0 y1∗n​{HT}n∗(n−k)​=0

  Tanner图里有两种节点：变量节点、校验节点。变量节点对应纠错码的各个码位（信息位+校验位）；校验节点就像是神经网络中中间层的节点，它负责接收、处理信号，并输出一个结果。举例中的H矩阵等价如下的Tanner图：

图二中c1、c2、c4连到校验节点s1上，表示校验方程： c 1 ⊕ c 2 ⊕ c 4 = 0 c 1 oplus c 2 oplus c 4=0 c1⊕c2⊕c4=0。
  图的一些定义（后续译码算法会涉及到）：

1. 相互之间有连接线的节点互为邻点（Neighbor）
2. 一个节点的邻点数量称为这个节点的度（Degree）
3. 回路（cycle，环）：从一个端点出发，经过不重复的边回到出发端点；经过的边数定义为回路的长度；图中最短回路长度称为图的周长（girth）

  变量节点的度分布函数： λ ( x ) : = ∑ i = 1 d y λ i x i − 1 lambda(x):=sum_{i=1}^{d_{y}} lambda_{i} x^{{i-1}} λ(x):=∑i=1dy​​λi​xi−1，其中 λ i lambda_{i} λi​表示二分图中度为i的变量节点相连的边数所占所有边数的比例。 d v d_v dv​表示变量节点的最大度。
  校验节点的度分布函数： ρ ( x ) : = ∑ i = 1 d c ρ i x i − 1 rho(x):=sum_{i=1}^{d_{c}} rho_{i} x^{i-1} ρ(x):=∑i=1dc​​ρi​xi−1，其中 ρ i rho_{i} ρi​表示二分图中度为i的校验节点相联的边（Edge）占所有边的比例。 d c d_c dc​表示校验节点的最大度。
  码率 r = k n = 1 − m n = 1 − ∫ 0 1 ρ ( x ) d x ∫ 0 1 λ ( x ) d x r = frac{k}{n}=1- frac{m}{n}=1-frac{int_{0}^{1} rho(x) d x}{int_{0}^{1} lambda(x) d x} r=nk​=1−nm​=1−∫01​λ(x)dx∫01​ρ(x)dx​

推导：校验节点数目 m = n − k = ∑ B ⋅ ρ i i = B ∫ 0 1 ρ ( x ) d x m=n-k=sum frac{B cdotrho_{i}}{i}=B int_{0}^{1} rho(x) d x m=n−k=∑iB⋅ρi​​=B∫01​ρ(x)dx，求和式从边化为节点数，求和为校验节点总数，即H矩阵的行数。
同理 n = ∑ B ⋅ λ i i = B ∫ 0 1 λ ( x ) d x n=sum frac{B cdot lambda_{i}}{i}=B int_{0}^{1} lambda(x) d x n=∑iB⋅λi​​=B∫01​λ(x)dx表示变量节点的总数，即H矩阵的列数。

构造目标：一个二进制稀疏矩阵

1. 任意两行之间至多只有一个共同的位置有 ‘ 1’
2. 任意两列之间至多只有一个共同的位置有 ‘ 1’
3. 避免出现长度为4的环

编码衡量方法：误码率（通过仿真得到）
构造准则：

1. 获得更好的误码性能
2. 更大的最小码距以及降低高信噪比下的error floor
3. 更均匀的环分布特性以便译码时更快更均匀的收敛
4. 更规则的H矩阵结构便于工程实现

LDPC码的构造方法：

1. 随机搜索法（最初论文里面的方法）

参考一：LDPC编译码原理

2. 边循序增长（Progressive Edge Growth，PEG）算法——图的方法

参考二：二进制LDPC码的构造及译码算法

3. 代数的方法，如基于RS码的方法

同参考二

高斯消去法是4.2中和积算法的特例，因为和积算法本身需要对单维度节点消去

相关定义：

1. 概率的对数似然比:
   LLR ⁡ ( u ) = log ⁡ P { u = + 1 } P { u = − 1 } operatorname{LLR}(u)=log frac{P{u=+1}}{P{u=-1}} LLR(u)=logP{u=−1}P{u=+1}​，其意义是概率 P { u = + 1 } = e L L R ( u ) 1 + e L L R ( u ) {{P{u=+1}}}=frac{e^{L L R(u)}}{{1+e^{L L R(u)}}} P{u=+1}=1+eLLR(u)eLLR(u)​的另外一种表现形式
2. 奇偶校验和的对数似然比：
   校验和 即：
   以BPSK为例子假设数字符号取值0，1映射为{+1，-1}编码系统中，各个符号之间存在校验和关系
   利用对数似然比可以推导出：

◼ 已知各个校验和的置信度，求出参与校验的各个符号的置信度
◼ 已知各个符号的置信度，求出各个校验和的置信度
数字符号 ui 遵从 N 个校验和 Sn，其中
• ui 之外的数字符号只出现一次
• ui 之外的数字符号相互独立
✓将数字符号 ui从校验和 Sn中除去，得到 “修正校验和” S ’ n S’n S’n
•“修正校验和”的似然比➔数字符号 ui的似然比
• 校验和包含的其余符号似然比➔” 修正校验和” 的似然比
其中乘积可以化简为

3. 对数似然比和置信度的关系
   对数似然比即概率，概率即置信度，只是表现形式不同，导致运算形式不同（概率相乘即对数似然比相加）
   数字符号置信度 = 修正校验和似然比 + 先验概率似然比： L L R ( u i ) ⁡ = ∑ n = 1 N L L R ( s n ′ ) + log ⁡ P ( u i = + 1 P ( u i = − 1 ) operatorname{LLR(u_{i})}=sum_{n=1}^{N} {L LRleft(s'_{n}right)}{}+log frac{Pleft(u_{i}=+1right.}{Pleft(u_{i}=-1right)} LLR(ui​)=∑n=1N​LLR(sn′​)+logP(ui​=−1)P(ui​=+1​

每次迭代结束之后，需要进行判决
❑ 求与 i i i有连接的所有校验节点传递给 i i i的似然比信息之和，判决
❑ 满足校验方程约束，则结束译码
❑ 不满足校验方程约束，则继续迭代

过程见习题(4)

参考blog LDPC编译码原理中的BP解码过程。
  置信传播算法是基于 Tanner 图的迭代译码算法。在迭代过程中，可靠性信息，即“消息”通过 Tanner图上的边在变量节点和校验节点中来回传递，经多次迭代后趋于稳定值，然后据此进行最佳判决。译码过程是在变量节点和校验节点之间传递信息。每个变量节点告诉它所连接的校验节点“我认为该变量是什么”，而校验节点告诉它所连接的变量节点“我认为该变量应该是什么”。经过反复的消息传递后，变量节点和校验节点不断改变自己对各个变量是什么的看法，最终能形成一个满足校验方程的码字，这就是译码的结果。如果经过充分的迭代后仍然不能形成一个满足校验方程的码字，则译码器宣布它无法译出这个码字，即译码失败。

一个简单的奇偶校验码
（1）写出其校验方程
（2）画出二分图，给出其周长
（3）计算其密度分布多项式，计算码率
（4）采用最小和算法进行解码

(1)可以定义变量节点和校验节点如下

校验方程为： C 3 = C 1 ⊕ C 2 C 6 = C 4 ⊕ C 5 C 7 = C 1 ⊕ C 4 C 8 = C 2 ⊕ C 5 begin{aligned} &C_{3}=C_{1} oplus C_{2} \ &C_{6}=C_{4} oplus C_{5} \ &C_{7}=C_{1} oplus C_{4} \ &C_{8}=C_{2} oplus C_{5} end{aligned} ​C3​=C1​⊕C2​C6​=C4​⊕C5​C7​=C1​⊕C4​C8​=C2​⊕C5​​
根据编码图可知校验矩阵为：

(2)根据校验矩阵，其二分图为

周长为最小环长, V 1 → C 1 → V 2 → C 4 → V 5 → C 2 → V 4 → C 3 → V 1 V 1→C 1→V 2→C 4→V 5→C 2→V 4→C 3→V 1 V1→C1→V2→C4→V5→C2→V4→C3→V1, 长度为 8

(3)

(4)最小和译码的迭代公式为： v i → j = ∑ k = 0 , k ≠ j d i v − 1 u k → i 求和 u j → i = ∏ k = 1 , k ≠ i d j v − 1 sign ⁡ ( v k → j ) × min ⁡ ∣ v k → j ∣ 求积 begin{aligned} &v_{i rightarrow j}=sum_{k=0, k neq j}^{d_{i}^{v}-1} u_{k rightarrow i} quad quad text{求和} \ &u_{j rightarrow i}=prod_{k=1, k neq i}^{d_{j}^{v}-1} operatorname{sign}left(v_{k rightarrow j}right) times min left|v_{k rightarrow j}right| quad quad text{求积} end{aligned} ​vi→j​=k=0,k​=j∑div​−1​uk→i​求和uj→i​=k=1,k​=i∏djv​−1​sign(vk→j​)×min∣vk→j​∣求积​

1. 初始化： v 1 = 0.5 , v 2 = 1.5 , v 3 = 1 , v 4 = 4 ， v 5 = 1 , v 6 = − 1.5 , v 7 = 2 , v 8 = − 2.5 v_{1}=0.5, v_{2}=1.5, v_{3}=1, v_{4}=4，v_{5}=1, v_{6}=-1.5, v_{7}=2, v_{8}=-2.5 v1​=0.5,v2​=1.5,v3​=1,v4​=4，v5​=1,v6​=−1.5,v7​=2,v8​=−2.5
   
   注意初始化过程本质是信道信息的体现：
   

2. 变量节点到校验节点，求和
   
   

3. 校验节点到变量节点，求符号+最小值
   
   

4. 变量节点到校验节点，求和
   
   

5. 进行译码硬判决（大于0表示BPSK为+1，判0，小于0表示BPSK为-1判1）：00001101，
   代入校验方程： H X T = 0 HX^T=0 HXT=0 ，满足校验方程，迭代结束