LDPC码及其译码实现

LDPC码及其译码实现

一、 LDPC码简介

LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出，但限于当时的技术条件，缺乏可行的译码算法，此后的35年间基本上被人们忽略，其间由Tanner在1981年推广了LDPC码并给出了LDPC码的图表示，即后来所称的Tanner图。1995年前后MacKay和Neal等人对LDPC码重新进行了研究，提出了可行的译码算法，从而进一步发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注。

LDPC码（低密度奇偶校验码）本质上是一种线形分组码，它通过一个生成矩阵G将信息序列映射成发送序列，也就是码字序列。对于生成矩阵G，完全等效地存在一个奇偶校验矩阵H，所有的码字序列C构成了H的零空间 (null space)，即HCT=0。LDPC码的奇偶校验矩阵H是一个稀疏矩阵，相对于行与列的长度，校验矩阵每行、列中非零元素的数目(我们习惯称作行重、列重)非常小，这也是LDPC码之所以称为低密度码的原因。由于校验矩阵H的稀疏性以及构造时所使用的不同规则，使得不同LDPC码的编码二分图(Taner图)具有不同的闭合环路分布。而二分图中闭合环路是影响LDPC码性能的重要因素，它使得LDPC码在类似可信度传播(Belief ProPagation)算法的一类迭代译码算法下，表现出完全不同的译码性能。

当H的行重和列重保持不变或尽可能的保持均匀时，我们称这样

的LDPC码为正则LDPC码，反之如果列、行重变化差异较大时，称为非正则的LDPC码。根据校验矩阵H中的元素是属于GF(2)还是GF(q)(q=2p)，我们还可以将LDPC码分为二元域或多元域的LDPC码。

二、LDPC译码算法

2.1、Gallager概率译码算法

Gallager当初为了介绍LDPC码，同时还提出了一种迭代的概率译码算法，Gallager概率译码算法，后来在此基础上又发展出了置信度传播译码算法（BPA，也称SPA或者MPA）。

假设一个二进制序列是一个LDPC码字，那么这n个比特就要满足由该码字的校验矩阵所确定的一系列的校验方程。并且，包含某一比特Ci的校验方程可能不止一个，这些校验方程中的其他比特又可能包含在其他更多的校验方程中。为了直观的表示这种关系，Gallager引入了校验集合树的概念。图2.1所示为某一比特的校验集合树。

(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)d

图2.1 校验集合树

根节点表示比特d，和d相连的每一条边表示包含d的一个校验方程，在图2.1中，d包含在3个校验方程中；第一层中的每一线段上的节点表示这一校验方程中除d以外的其他比特，因此包含d的3个校验方程分别是：

Cd?C1,1?C1,2?C1,3?0

Cd?C2,1?C2,2?C2,3?0 Cd?C3,1?C3,2?C3,3?0

校验方程中的加法是模2加。Cd即为比特d的数值，C1,1即为比特（1,1）的数值。

与第一层各节点相连接的每条边同样表示包含该比特的一个校验方程，第二层中的每一线段上的节点同样表示该校验方程中除第一层比特以外的其他比特。以比特（2,2）为例，和比特（2,2）相连接的边有3条，其中一条与本层节点（2,1），（2,3），及根节点d相连，另外两条与第二层中节点u,v,w和x,y,z相连。因此包含比特（2,2）的3个校验方程分别为：

C2,2?C2,1?C2,3?Cd?0 C2,2?Cu?Cv?Cw?0 C2,2?Cx?Cy?Cz?0

第三层（图中未画出）及以后的各层依此类推，每个比特都有相应的以该比特为根节点的校验集合树。

假设信道是无记忆信道，yi仅与ci及信道噪声有关，考虑根节点d和第一层节点组成的集合，这些比特组成了包含比特d的

j个校验方程，每个校验方程由k个比特组成（包含比特d），显然发送的这些比特满足这j个校验方程。因此假设当发送的码字是

c?(c0,c1,,cn?1)时，那么在以上情况下接收到的符号即

为y?(y0,y1,,yn?1)。

这样在传送码字c时，码字中的各比特满足包含比特d的j个校验方程。当接收到相应的符号序列y时，比特d为1的条件概率可以表示为P(cd?1|y,c)。同理，比特d为0的条件概率表示为P(cd?0|y,c)。又令当不考虑发送比特间的相关性时，d为1的概率表示为P(cd?1|y)，它与信道模型有关。

令Pd?P(cd?1|y)，Pil表示d的校验集合树第一层中包含d的第i个校验方程的第l个比特为1的概率，那么有：

k?1P[cd?0|y,c]j1??(1?2Pil)P[cc]?1?PdP?l?1d?1|y,di?11?k??1l?1(1?2Pil)

根据式2.1，只要知道了图2.1的第一层中各比特为1的概率

Pil，就可以算出比特d的条件概率。在其他根节点的校验树里比特d又作为一个节点参与到根节点的概率计算中去，即比特d从与其有关的节点中获取信息计算出概率，再将其计算出的概率信息传出用于计算其他的节点ci，由于在计算其他节点ci时同样会用到计算比特d时所用过的运算，所以可以通过共享计算的中间结果而使计算量大为降低，进而发展出了BPA（也称SPA或MPA）。

(2.1)

2.2BP算法（也称SP或MP算法）

校验集合树虽然比较直观，但对于每一个节点都有不同的校验集合树，因此在描述并行计算整个码字各比特的后验概率时，使用校验集合树并不方便，因此介绍一种新的图形表示法，Tanner图。对应于图2.1的Tanner图如图2.2所示。该图仅画出部分变量节点和校验节点。Tanner图中变量节点对应于校验集合树中的节点，校验节点对应于校验集合树中的边。

(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)dS1S2S3S4图2.2 对应于图2.1校验集合树的部分Tanner图

由Tanner图可看出，信息是在变量节点和校验节点之间来回传递的，变量节点d将自身的固有信息再加上与它有关的S1，S2，S3校验节点传给它的额外信息一起传递给校验节点S4。同理，校验节点cj也是将自身的固有信息再加上与它有关的除某一变量节点vi以外的其余变量节点所传给cj的额外信息一起传递给变量节点vi，如此信息便在变量节点和校验节点之间来回传递，不断更新变量节点和校验节点的值，所有变量节点和校验节点更新完一次称之为一次迭代结束，直

本文来源：https://www.bwwdw.com/article/zuod.html