LDPC码及其译码实现

LDPC码及其译码实现

LDPC码最早在

20

世纪

60

年代由Gallager在他的博士论文中提出，但限于当时的技术条件，缺乏可行的译码算法，此后的35

年间基本上被人们忽略，其间由Tanner在

1981

年推广了LDPC码并给出了

年前后MacKay和Neal发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注。LDPC码（低密度奇偶校验码）本质上是一种线形分组码，它通过一个生成矩阵G将信息序列映射成发送序列，也就是码字序列。对于生成矩阵G，完全等效地存在一个奇偶校验矩阵H，所有的码字序列C构成了H的零空间 (null

=0。LDPC码的奇偶校验矩阵H是一个稀疏矩阵，相对于行与列的长度，校验矩阵每行、列中非以称为低密度码的原因。由于校验矩阵H的稀疏性以及构造时所使用的不同规则，使得不同LDPC码的编码二分图(Taner图)具有不同的闭使得LDPC码在类似可信度传播(Belief

ProPagation)算法的一类迭代译码算法下，表现出完全不同的译码性能。当H的行重和列重保持不变或尽可能的保持均匀时，我们称这样的LDPC码为正则LDPC码，反之如果列、行重变化差异较大时，称为非正则的LDPC码。根据校验矩阵H中的元素是属于GF(2)还是GF(q)(q=2)，我们还可以将LDPC码分为二元域或多元域的LDPC码。Gallager当初为了介绍LDPC码，同时还提出了一种迭代的概率译码算法，Gallager概率译码算法，后来在此基础上又发展出了置信度传播译码算法（BPA，也称SPA或者MPA）。假设一个二进制序列是一个LDPC码字，那么这n个比特就要满足特

i含在其他更多的校验方程中。为了直观的表示这种关系，Gallager引入了校验集合树的概念。图2.1

所示为某一比特的校验集合树。 d图

2.1 校验集合树根节点表示比特d，和d相连的每一条边表示包含d的一个校验方程，在图

2.1

中，d包含在

3

个校验方程中；第一层中的每一线段上的节点表示这一校验方程中除dd的

3

个校验方程分别是：CCC

ddd

C

C

C

C

C

C

C

C

C

校验方程中的加法是模2

加。

即为比特d的数值，

即为比特d （1,1）的数值。与第一层各节点相连接的每条边同样表示包含该比特的一个校层比特以外的其他比特。以比特（2,2）为例，和比特（2,2）相连接的边有

3

条，其中一条与本层节点（2,1），（2,3d相连，另外两条与第二层中节点u,v,w和x,y,z相连。因此包含比特（2,2）的3个校验方程分别为：C

C

C

C

d

CC

C

C

C

C

C

C

w

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

i

仅与

i

及信道噪声有关，考虑根节点

d

和第一层节点组成的集合，这些比特组成了包含比特d

的j

个比特组成（包含比特

d

），显然发送的这些比特满足这

j

个校验方程。因此假设当发送的码字是

,

,

,

n

为

,

,

,

n

。这样在传送码字

时，码字中的各比特满足包含比特d

的

j个校验方程。当接收到相应的符号序列

时，比特

d

为

1

的条件概率可以表示为

d

,

。同理，比特d

为

0

的条件概率表示为

d

,

。又令当不考虑发送比特间的相关性时，

d

为

1

的概率表示为

有关。

d

，它与信道模型令

d

d

，

il

表示

d

的校验集合树第一层中包含

d

的第

i

个校验方程的第l

个比特为

1

的概率，那么有：d

j

d

j

(1

P )P

i

(1

P )l

P

[

dd

,

]

P

il

l

,

]

d

il

)

il

根据式

2.1，只要知道了图

2.1

的第一层中各比特为

1

的概率，就可以算出比特

d

的条件概率。在其他根节点的校验树里比特

d

又作为一个节点参与到根节点的概率计算中去，即比特d

从出用于计算其他的节点 ，由于在计算其他节点 时同样会用到i i计算比特

d

时所用过的运算，所以可以通过共享计算的中间结果而集合树并不方便，因此介绍一种新的图形表示法，Tanner图。对应于图

2.1

的Tanner图如图

2.2

所示。该图仅画出部分变量节点和校验节点。Tanner图中变量节点对应于校验集合树中的节点，校验节点对应于校验集合树中的边。 d

图

2.2 对应于图

2.1

校验集合树的部分Tanner图由Tanner的，变量节点d将自身的固有信息再加上与它有关的

，

，

校验 节点传给它的额外信息一起传递给校验节点

也 j是将自身的固有信息再加上与它有关的除某一变量节点

以外的其i余变量节点所传给

的额外信息一起传递给变量节点

，如此信息便j i到变量节点译码成功或者达到最大的迭代次数译码输出。因此，完整的BPA（也称SPA或MPA）表述如下：1)初始化：

q

p

，

q

q

，其中

表示的是信道的先验 l l l概率。2)校验节点更新：

q

q

q

，

r

r

r

，则有 r

(

m

q

lLmlr

r

)/ r

r

)/ 3)变量节点更新：

q

p lq

p l

mMlm

rmlrml

mMlm其中

是一个使得q

q

的值 4)似后验概率更新q

pl l l

r

q

pl l l

mMl

r

mMl同样

是一个使得q

q

的值l l l （5)q

，

i

, （i i i若

，或者迭代次数达到最大迭代次数，则结束迭代，将作为译码输出；否则返回到步骤2）继续迭代。由

2.2

介绍的BP算法可以看出BP

件实现，因此，又发展出了一种更加简便的对数域的BP算法，简称Log-BP算法。考虑一个二值随机变量

，它的对数似然比L

定义为L

根据对数似然比的定义，令

lll

qqqrqr

lll

r再对以上的BP算法在对数域内进行一系列的化简，最终可获得Log-BP算法的完整表述：1)初始化：

l2)校验节点更新：

[

]3)变量节点更新：

lLml

l

ml

mMlm4)似后验概率更新：

l l

若

若

，或者迭代次数达到最大迭代次数，则结束迭代，将 5)比特判决：如果

，则判

；否则判

，（l

,N l l l作为译码输出；否则返回到步骤2）继续迭代。由于Log-BP算法仍然具有连乘与反三角函数，因此仍然比较复杂，进而又发展出了Log-BP算法的近似算法，Min_Sum算法。最小和译码算法的优点是对LDPC码并行的迭代软译码算法，故其运算比BP算法以及Log-BP算法都要简单，它仅采用求最小值以及相加运算，而不需要乘法运算。Log-BP算法的基础上得到Min_Sum算法的完整表述，

Min_Sum算法仅步骤

2）与Log-BP算法不同，其余的步骤均和Log-BP算法的步骤相同，Min_Sum算法的步骤2）为：2)校验节点更新：lLlLml

lLml

其中

为每一个

Log-BP算法一致。在此选取CC与Matlab联调的方式来验证译码程序的结果，Matlab里完成m文件和script的编写，C语言与Matlab之间的联调通过Matlab的MEX文件来实现。译码算法程序流程图：

nodedecode

=

node

=

MAX

<

MAX

=

decode图

3.1 译码算法程序流程图差

以及校验矩阵

，按照以上程序流程运行后返回译码码字，其中MAX为最大迭代次数。具体的译码程序和Matlab的MEX文件中各函数的定义，调用以及各自的实现方式如下图：

*)

node

node

node

node

*);

node

node

node

node

node

node

node

node

*);

node

node

node

*);{}

node

node

node

node

node

node

node

{

node

node

node

*);

node

node

node

node

node

node

node

node

*);

node

node

node

*);{

}

*)

*)

*)

*)}图

3.2 函数的调用及实现关系图

biterr，并画出对应信噪比误码率biterr的图形。以Blks和SNRSNR和相应的Blks来进行仿真，用以衡量LDPC信道编码的性能，其中Blks为对应信噪比所传输的码字数量，SNR为信号与噪声的幅值比，实验图形如下：图

4.1Blks

=

[26

32

22

674

1500

2000]；