第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
论文研究-LDPC码译码算法研究 .pdf
LDPC 码的译码算法研究
http://www.paper.edu.cn
胡维钢，赵振纲
北京邮电大学信息工程学院，北京（100876）
E-mail：qingtianaaa@yeah.net
摘 要：本文首先简要介绍了 LDPC 码和其二分图表示方法，接着对 BP（Belief Propagation）
概率译码算法的主要公式进行了推导，然后利用二分图研究了 BP 算法的物理解释，最后给
出了高斯信道下 BP 算法的核心部分的 C 语言伪码。
关键词： LDPC 码，二分图，迭代译码，BP 算法
中图分类号：TN911.22
1. 引言
LDPC（Low Density Parity Check，低密度奇偶校验）码一种基于稀疏校验矩阵的线性
分组码[1]，最初由 Gallager 在 1962 年提出。Gallager 同时证明了 LDPC 码具有逼近仙农限的
性能，并且首次提出了迭代译码的思想。然而当时 LDPC 码并没有引起足够的重视，直到
1993 年 Berrou 提出了 Turbo 码，同样具有迭代译码算法的 LDPC 码才重新为研究者们所注
意。而后几年，Mackay 和 Neal 等人的研究表明 LDPC 码在码长很长时可以得到优于 Turbo
码的性能[2]，并且更容易实现，由此在信道编码领域引发又一研究热潮。
LDPC 码的构造特殊之处在于它的奇偶检验矩阵 H 是稀疏矩阵，即 H 矩阵中非零元素
个数远小于零元素个数。规则 LDPC 码校验矩阵中每列包含 dv 个非零元素，每行包含 dc
（dc>dv）个非零元素，若码长为 N，则可记为(N,dv,dc).其码率为
R = − 。典型的中短
1
dv
dc
码长、码率为 0.5 的 LDPC 码有（512，3，6）或（1024，3，6）等。每行或每列含有的非
零元素个数不固定的 LDPC 码称为不规则 LDPC 码，不规则 LDPC 码比规则 LDPC 码具有
更好的逼近仙农限的性能。
2. LDPC 码译码算法简介
信道编码的译码算法好坏往往是决定其码性能和其应用前景的一个重要因素。通常分组
码的译码复杂度与码长成指数关系,在码长较长时译码复杂度急剧上升,因而实际应用非常困
难。而 LDPC 码由于其奇偶校验矩阵特有的稀疏性,使其存在高效译码算法,其简化译码算法
的复杂度与码长成线性关系,这就为长 LDPC 码的应用奠定了基础。
LDPC 码的译码算法主要是基于二分图的消息传递 MP(Message Passing)算法。Gallager
在其博士论文[3]中提出了两种基于消息传递的译码算法：树型译码的硬判决算法和概率译码
软判决算法。在概率译码算法中，Gallager 提出了软输入、软输出迭代译码的思想，在无穷
阶量化即连续性的 MP 算法时即成为 BP (Belief Propagation)算法，其译码复杂度最高而其性
能也最好。当二分图中没有环，BP 算法等价于最大似然泽码，具有最优译码的性能。本文
主要介绍 Gallager 概率译码算法，即 BP 算法。
3. LDPC 码的二分图（Tanner 图）表示
消息传递算法（MP 算法）的提出是基于二分图的。LDPC 码的二分图表示最早是由
Tanner 于 1981 年在文[4]中提出的，所以也称为 Tanner 图。
设 LDPC 码的校验矩阵 H 为一个 M N× 阶的矩阵，该矩阵可以由二分图表示。二分图
-1-
http://www.paper.edu.cn
的左边用 N 个节点来表示校验矩阵的 N 列，称为变量节点(也可称为比特节点或信息节点)；
右边有 M 个节点，每个节点表示一个校验约束，称为校验节点；译码信息就在多个变量结
点和校验结点之间来回传递。与校验矩阵中‘1’元素相对应的左右两个节点之间用边连接，
将这条边称为两端节点的相邻边，相邻边两端的节点称为相邻点。每个节点的总相邻边数称
为该节点的度数。对于规则的 LDPC 码来说，其校验矩阵中每行和每列中‘1’的个数是一定
的，对应的二分图中变量节点度数和校验节点度数分别对应着一个固定值。以 (12,3,6)规则
LDPC 码为例，图 1(a)为其二分图表示，(b)为其对应的校验矩阵，（c）为其校验约束方程。
二分图左边的变量节点的度数为 3，意味着每个信息比特要参与 3 个校验约束；右边校验节
点的度数为 6，表示每个校验约束有 6 个信息比特参与。
图 1 （12，3，6）规则 LDPC 码的校验矩阵、二分图表示及其对应校验约束方程
4. BP 算法的推导
Gallager 在其博士论文[3]中提出了概率译码的 BP 算法，下面我们对高斯信道下的比特
译码算法进行理论推导。
=
j
j
=
j
p r
(
p x
(
b S r
, )
|
假设比特码元之间相互独立，则根据 Bayes 准则有：
b r
, )
其中对二进制比特位，b＝0 或 1； jx 是编码器输出的第 j 位发送比特， jr 为 jx 通过噪
声信道后收到的第 j 位接收比特；
是一系列事件的集合，其中 mjS 表
S
示与 jx 相关的第 m 个校验方程得到满足， jS 即为与 jx 相关的所有校验方程都得到满足。
—— <1
b p S
)
(
,......,
S
=
S
{
,
S
1
j
|
x
=
|
x
j
}
kj
=
j
j
0
j
j
-2-
http://www.paper.edu.cn
1>式后半部分即为在已知 b 与 r 的条件下，与 jx 相关的所有校验方程都得到满足的概率。
1>式前半部分容易计算，对高斯噪声而言，有：
p r
(
j
|
x
j
=
b
)
=
1
2
2
πσ
(
1/ 2
)
(
r
j
exp[
2
( 1) )
b
+ −
2
2
σ
]
—— <2
对相互独立的比特码元，1>式后半部分可以做如下变换为：
p S
p S
(
(
,......,
b r
, )
b r
, )
p S
(
S
=
=
=
=
x
x
,
|
|
S
1
j
0
j
kj
j
j
j
∏
|
x
j
mj
=
b r
, )
－<3
m M j
( )
∈
上式中 ( )M j 代表与 jx 相关的所有校验方程的集合， (
p S
x
即为与 jx 相关的
b r=
, )
第 m 个校验方程得到满足的概率。如果 0
等效为第 m 个校验方程
中除开 jx 外的其他所有位中含“1”个数为偶数的概率（实际是保证校验方程模二和为 0）；如
等效为第 m 个校验方程中除开 jx 外的其他所有位中含“1”个数
p S
果 1b = ，则 (
mj
为奇数的概率。
x
|
j
mj
b r=
, )
p S
b = ，则 (
b r=
, )
x
mj
|
|
j
j
|
mj
x
b r=
, )
p S
据此下面推导 (
首先做一个简单推导，假设两个比特位 1x 和 2x 满足校验约束方程 1
x
p x
1(
=
x⊕ = ，设
= − 。那么校验约束方程得到满足
q
1
= − 和 2
具体表示式。
q
1)
= ，令 1
p x
2(
p
2
p
1
=
0
1
2
j
p
p
1)
= 和 2
1
的概率可以写为：
0)
(1
= −
p
1
)(1
−
p
2
)
=
2
p p
1
2
−
p
1
−
p
2
1
+ ，
q
(
−
1
,......,
)
−
p
2
—— <4
p q
)(
1
2
x 相应位为1的概率，令 x 序列的模二
}L
x
2
p x
(
1
⊕ =
做简单变换后得到:
p x
2 (
1
x
⊕ =
2
p p
{ ,
如果令 1
2
z
x
= ⊕ ⊕
2
x
1
L
和为
−
p
1
p
)
− = −
=
2
p 为比特序列 1
x x
}L
{ ,
2
x
⊕ ，则推导可得：
0) 1 (1 2 )(1 2
,......,
......
L
L
P z
2 (
L
=
0) 1
− =
−∏
p
(1 2 )
i
，即
i
1
=
L
P z
(
L
=
0)
=
1
2
[1
+
−∏
q
i
(
i
1
=
p
i
)]
—— <5
类似的有：
1
2
−∏
p S
利用式5>、6>,我们可得到 (
P z
(
1)
[1
q
i
=
=
−
1
=
(
L
L
i
p
i
)]
—— <6
|
x
j
mj
b r=
, )
的表示式：
p S
(
mj
|
x
j
=
r
0, )
=
p S
(
mj
|
x
j
=
r
1, )
=
1
2
1
2
[1
+
j
'
j
'
−
[1
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <7
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <8
上式中 0
'mjq 表示在接收序列 r 已知情况下，参与第 m 个校验约束的比特位
'jx 为 0 的
-3-
http://www.paper.edu.cn
(
) \
'jx 参与校验约束 m 后传递的概率信息；
概率。注意此处的概率表示 'j 位的初始概率，不含
N m j 表示除 jx 位外其他所有参与第 m 个校验方程的序列 'jx 的集合。7>、8>式右端连
乘时要排除第 j 位概率的原因是我们这里所求的概率是在除开 jx 外后，其他所有位中含“1”
个数为奇数或偶数的概率。
将3>、7>式代入1>式，我们可以得到每个比特的后验概率表达式：
p x
(
j
=
0 |
S r
, )
j
=
p r
(
j
|
x
j
=
0)
∏
m M j
( )
∈
1
2
[1
+
j
'
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <9
类似可得：
p x
(
j
=
1|
S r
, )
j
=
p r
(
j
|
x
j
=
1)
∏
m M j
( )
∈
1
2
[1
−
j
'
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <10
有了单个比特的译码算法，BP 算法实质上就是在此基础上展开的迭代运算过程，为了
清楚地了解 BP 算法的物理意义和迭代过程，下面我们结合二分图进行分析。
5. BP 算法的物理意义
设一段未知数据信息，经 LDPC 编码后成为二进制序列 X ， X 通过高斯信道传输后由
于噪声和衰落等的影响，在收端接收到的实际上是一串实数域上的矢量 R 。而 BP 算法译码
的实质就是根据接收到的实数矢量 R 计算发送比特序列的后验概率，并根据其所参与的校
验约束尽可能准确的对发送序列 X 进行译码。
首先我们考虑对单个信息比特 jx 的译码过程。在一次迭代译码过程中，可将LDPC码校验矩
阵H所对应的二分图以 jx 为根节点展开成树，如下图是展开三层的译码树结构。
图 2 变量节点展开的三层译码树图
上图中层矩形框为校验节点，代表了根变量节点 jx 所参与的校验约束；底层变量节点
即代表了与 jx 一同参与此校验约束的其他变量节点。译码过程中，对每一个校验节点而言，
就是根据底层各变量节点的后验概率，在不考虑根节点 jx 概率信息的情况下，分别计算出
在根变量节点 jx 为 0 或 1 的条件下，校验约束得到满足的概率。在整个过程中，译码的概
率信息由底层变量节点传递给中层校验节点，再由校验节点传递给根变量节点。
设所考虑的校验节点 m 的父变量节点为第 j 个变量节点，参与该校验的变量节点集合
-4-
)N m ，则其子变量节点集合记为差集 (
记为 (
校验和为 0 和 1 的概率，则有下式：（即式 7>、式 8>）
N m j ，设 0
) \
mjr 和 1
mjr 分别记为子变量节点的
http://www.paper.edu.cn
r
0
mj
=
p S
(
mj
|
x
r
1
mj
=
p S
(
mj
|
x
=
r
0, )
=
=
r
1, )
=
j
j
1
2
1
2
[1
+
j
'
j
'
−
[1
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <11
∏
∈
N m j
)\
(
0
(
q
mj
'
q
1
−
mj
'
)]
—— <12
mjr 和 1
上式概率信息 0
mjr 与 1
mjr 也就是其父变量节点取值为 0 或 1 时，校验约束得到满足的概率;
mjr 计算时没有包含父变量节点 j 的概率信息，故可作为独立信息沿树中边向上发
由于 0
送给根变量节点。
根变量节点收到这些以条件概率形式发送的边信息后，可以计算出根节点比特取值分别
为 0 或 1 的条件下，该比特所参与的所有校验约束都得到满足的概率。并根据自己的后验概
率，重新计算其取值为 0 和 1 的概率。
设所考察的信息节点 j 所参与的校验方程的集合为 ( )M j ，变量节点在给定子校验节点
边信息的条件下取值为 0 和 1 的概率记为 0
P
0
j
=
p x
(
j
=
0 |
S r
, )
j
=
p r
(
j
|
x
j
P
1
j
=
p x
(
j
=
1|
S r
, )
j
=
p r
(
j
|
x
j
jP 和 1
jP ,则有下式：（即式 9>、式 10>）
r
0
mj
= ∏ —— <13
0)
= ∏ —— <14
1)
m M j
( )
r
1
mj
∈
m M j
( )
∈
上式中
∏
r
0
mj
为信息比特 j 取值为 0 时其所有子校验约束得到满足的概率，
)
m M j
(
∈
为信息比特 j 取值为 1 时所有子校验约束得到满足的概率。
∏
r
1
mj
∈
m M j
(
)
若一次迭代无法对 jx 正确译码，则我们可增加迭代次数，对二分图来说就是增加 jx 展
开树图的层数。其实质是以更多的底层变量节点概率信息参与计算，为 jx 译码提供更多的
校验约束信息。如下图所示是以 jx 为根节点展开成五层树图结构。
-5-
http://www.paper.edu.cn
图3 变量节点展开的五层译码树图
如上图所示，在二分图中无环时，底层变量节点的概率信息按前述方式进行。中部变量
节点可看作由底层变量节点和其子校验约束构成的子树图的根变量节点，仍可按前述方式处
理其概率信息；与前不同的是此时计算得到的中间变量节点的译码信息不包含其上层校验节
点信息，也不作为该变量节点的判别信息，而是作为译码中间信息继续向上层校验节点传递。
由上图与图 2 比较可见，当译码树图展开深度增加时，计算 jx 概率信息时实际包含了更多
的底层变量节点概率信息和校验约束信息，故能增加 jx 的译码准确性，当然同时译码复杂
度也会随之增加。
设所考虑的变量节点为 j 的父校验节点为第 m 个校验节点，它所参与的校验节点的集
合记为 ( )M j ，那么其参与的子校验节点集合为差集 ( ) \M j m ，和上类似，可得树中部信
息节点的后验概率:
x
—— <15
p r
(
=
|
'
P
0
j
—— <16
j
j
r
0
m j
'
= ∏
0)
= ∏
1)
m M j m
r
1
m j
'
( )\
∈
'
m M j m
( )\
'
∈
P
1
j
'
=
p r
(
j
|
x
j
由此整个运算过程从最底层开始，由底层变量节点将后验概率向上发送，逐级向上，在
校验节点按式 11>、12>处理信息，变量节点按 15>、16>处理信息，最后所有信息汇集到根
jP > 0.5 则判为 1，否则判
变量节点时按 13>、14>计算根节点比特的概率分布 0
为 0。
jP 。若 1
jP 和 1
有了上述对单个比特进行译码的手段，可将之应用于编码的每一个比特，计算出发送端
发送的所有码字比特，并将计算结果代入校验约束方程，若方程得到满足，所得的译码结果
就是发送的码字。否则可增加迭代次数，即加大译码树的深度，以给每个比特的译码提供更
多的边信息，重复上述计算，直到所有的校验约束都得到满足，或树的深度大于某一预先指
定的值（即设定的译码最大迭代次数）而宣告译码失败。
-6-
6. BP 算法实现
http://www.paper.edu.cn
下面我们给出高斯信道下 BP 算法的 C 语言伪码，首先定义一些需要用到的变量和函数：
2σ ：信道高斯噪声方差。
j ：校验矩阵的列，即变量节点，也代表了译码的比特位。
N ：校验矩阵的列数。
m ：校验矩阵的行，即校验节点，代表译码的校验约束。
M ：校验矩阵的行数。
jx ：编码器输出的码元，即发送的第 j 位比特。
jr ： jx 通过高斯信道后接收端收到的加噪码元。
P
,α βj
j ：使 0
j
S
S
S
{
=
1
P
1 1
+
=
的归一化系数。
j
S
是一系列事件的集合，其中 mjS 表示与 jx 相关的第 m 个校验方
}
,......,
,
kj
0
j
j
j
程得到满足。 jS 即为与 jx 相关的所有校验方程都得到满足。
( )M j ：与变量节点 j 相关的所有校验约束的集合； ( ) \M j m 为其除开第 m 个校验约
束后的差集。
)N m ：参与第 m 个校验约束的所有变量节点的集合， (
N m j 为其除开第 j 个变量
) \
(
节点后的差集。
x
|
x
|
=
=
0
j
j
=
的概率。
=
的概率。
P
1
j
f
f
1
j
P
0
j
p r
(
p r
(
j
p x
(
=
j
=
j
0 |
：在发送 jx 为0时，收到信息为 jr 的先验概率。
0)
：在发送 jx 为1时，收到信息为 jr 的先验概率。
1)
S r
, )
j
：在接收信息已知，所有校验约束 jS 都得到满足时， jx 取值为0
=
j
p x
(
j
=
1|
S r
, )
j
：在接收信息已知，所有校验约束 jS 都得到满足时， jx 取值为1
0
1
'mjq 表示在接收序列 r 已知情况下，参与第 m 个校验约束的比特
'mjq 表示在接收序列 r 已知情况下，参与第 m 个校验约束的比特
r
0
mj
r
1
mj
： jx 取值为0时第 m 个校验约束得到满足的概率。
： jx 取值为1时第 m 个校验约束得到满足的概率。
r
0, )
r
1, )
p S
(
p S
(
x
x
=
=
=
=
|
|
mj
mj
j
j
'jx 为0的概率。
'jx 为1的概率
6.1 算法实现
6.1.1 初始化（对高斯信道噪声）
for
for
j =
m =
q
0
mj
=
f
，
，
1,2,......,N
1,2,......,M
1
2
2
πσ
=
0
j
(
)
1/ 2
exp[
2
(
r
1)
+
j
2
2
σ
]
-7-
http://www.paper.edu.cn
q
1
mj
=
f
1
j
=
1
2
2
πσ
(
1/ 2
)
exp[
2
(
r
1)
−
j
2
2
σ
]
end
end
6.1.2 迭代
1,2,......,M
，
0
q
mj
'
q
1
−
mj
'
)]
0
q
mj
'
q
1
−
mj
'
)]
m =
∏
I．校验节点更新：
for
j N m∈
(
)
for
1 [1
2
1 [1
2
∏
j N m j
'
)\
∈
j N m j
'
)\
∈
r
0
mj
r
1
mj
=
+
=
−
(
(
(
(
end
end
II．变量节点更新：
1,2,......,N
，
for
r
q
0
0
0
j
m j
mj
'
j =
= ∏
f
= ∏
m M j m
r
1
m j
'
q
1
mj
( )\
1
j
f
'
∈
（ 0
End
( )\
m M j m
'
∈
mjq 作为下一次译码的初始值，从而实现迭代过程）
mjq 和 1
6.1.3 试验译码
j =
=
α
j
for
P
0
j
0
j
1,2,......,N
，
∏
f
r
0
m j
'
∏
m M j
( )
r
1
m j
'
1
j
f
'
∈
P
1
j
=
β
j
'
∈
m M j
( )
0.5>jP
1
if
then ˆ
jx = ；
else ˆ
jx =
0
end
1
6.1.4 中止条件（可预先设定最大迭代次数）
1,2,......,N
T
j =
jx H = ，done，quit
for
if ˆ
else got to 6.1.2
end
0
-8-
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
