LDPC码的改进译码算法

文章编号：1007-0249 (2007) 03-0128-03

LDPC码的改进译码算法*

林雪红， 吴伟陵

（北京邮电大学 信息工程学院，北京 100876）

摘要：由于短帧长LDPC码存在很多环路，其译码性能不具有最优性。本文首先推导了有环路LDPC码的概率译码算法，然后在传统的概率译码算法引入了修正系数，从而减小了环路对译码性能的影响。仿真结果表明，采用改进的译码算法可以提高译码性能。

关键词：LDPC码；概率译码算法；因子图；周长 中图分类号：TN919.22 文献标识码：A

1 引言

目前，在低信噪比下接近Shannon限的LDPC码[1]和Turbo码[2]倍受编码理论界的关注。之所以有如此优越的性能是由于它们不仅在编码端采用了不受约束的随机码的形式，而且译码均采用基于因子图的消息传递迭代算法[3]。当LDPC码不存在环路时，消息传递算法可以达到最优解；而当LDPC码存在环路时，当迭代次数大于最小周长（girth）的二分之一时，由于传递的消息具有相关性，使得其译码性能不再具有最优性。本文推导了有环路LDPC码的概率译码算法，并对该译码算法进行了修正。仿真结果表明，采用修正的译码算法可以提高译码性能。

2 LDPC码的概率译码算法

设LDPC码的校验矩阵H的维数为M×N，根据该矩阵得到与之对应的因子图（图1）。图中的节点分为两组，一组代表校验矩阵若Hij不为0，则因子图的节点si与xj相连。

设编码器的输出码字c=(c1,c2,\",cN)，通过BPSK调制后经过AWGN信道，译码器的输入序列为

r=(r1,r2,\",rN)，其中rn=2cn−1+vn，vn是均值为0，方差为σ2的高斯噪声。

图1 LDPC码的因子图

的列，用比特节点x=(x1,x2,\",xn)表示；另一组代表校验矩阵的行，用校验节点s=(s1,s2,\",sm)表示。

定义N(m)={n:Hmn≠0}表示所有与校验节点sm相连的比特节点，M(n)={m:Hmn≠0}表示所有与比特节点xn相连的校验节点，N(m)\\n表示N(m)中除去比特节点xn，M(n)\\m表示M(n)中除去校验节点

iism；qmn表示除校验式sm以外的其他校验式可信度信息已知的条件下，比特节点xn=i的概率；rmn表

示假设比特节点xn=0/1条件下，其他参与校验节点sm的比特节点提供给校验节点sn=i（也就是满足校验式m）的概率。则概率译码算法包括以下步骤[4]：

步骤1. 初始化

对每个比特节点n=1,\",N，令

⎛−(rn+1)2100

exp⎜ qmn=fn=

⎜2σ2

2πσ⎝

步骤2. 迭代过程 1）校验节点更新

0

−q1设δqmn=qmnmn，对每个校验节点m=1,\",M和n∈N(m)，计算

⎞

⎟， q1=fn1=mn⎟⎠

⎛−(rn−1)2exp⎜

⎜2σ2

2πσ⎝1

⎞

⎟ （1） ⎟⎠

* 收稿日期：2004-09-14 修订日期：2005-01-18 基金项目：国家自然科学基金项目（60272052）

第3期 林雪红等：LDPC码的改进译码算法 129

δrmn=

n'∈N(m)\\n

∏δ0

=qmn'， rmn

111

1+δrmn， rmn=1−δrmn （2） 22

()()2）比特节点更新

对每个比特节点n=1,\",N和m∈M(n)，计算

0011

qmn=αmnfn0∏rm'n， qmn=βmnfn

m'∈M(n)\\m

1

∏rm'n （3）

m'∈M(n)\\m

对每个比特节点n=1,\",N，计算

0011=αnfn0∏rm qn'n， qn=βnfn

m'∈M(n)

m'∈M(n)

1

∏rm'n （4）

其中αmn、βmn、αn和βn均为归一化因子。

步骤3. 尝试判决

ˆˆˆˆˆ根据判定条件：当q1n>0.5时，cn=1；否则，cn=0，得到码字c=(c1,\",cN)。若满足以下两个条

ˆ=0，cˆ作为有效译码值输出；件之一停止译码：（1）Hc（2）达到预定的迭代次数，计算误码率。否

则，返回步骤2开始下一轮迭代。

3 译码算法改进

当LDPC码所对应的因子图存在环路时，上述概率译码算法仍有可能得到优越的译码性能。这是因为码长N和校验式M较大时，不难构造出环路较少且周长较长的校验矩阵。而当码长较短时，由于很难构造出环数少、周长长的校验矩阵，这时循环路径就会影响译码性能。

设LDPC码比特节点xi的最小周长为2l，在l次迭代之前概率译码算法都是最优的，这是因为译码过程中采用的消息都是相互独立的。但当迭代次数再增加时，沿最短环路传递给节点xi（以及其他周长为2l的比特节点）的消息与节点xi（以及其他节点）已经不相互独立，其译码性能不再具有最优性。通常LDPC码的译码要几百甚至上千次迭代才能达到理想的性能，而构造LDPC码一般仅仅避免了周长为4的环路。因此，有必要针对有环路的LDPC码的译码算法进行改进。

假定两个比特满足校验约束关系，即x1⊕x2=0，并且p1=P(x1=1)，p2=P(x2=1)和q1=P(x1=0)，

q2=P(x2=0)。若x1和x2不相互独立，则有

P(x1⊕x2=0)=P(x1=0)⋅P(x2=0|x1=0)+P(x1=1)⋅P(x2=1|x1=1)

''

令 q2=P(x2=0|x1=0)=b0P(x2=0)， p2=P(x2=1|x1=1)=b1P(x2=1) ''

+p1p2 则校验节点的概率可表示为 P(x1⊕x2=0)=q1q2

通过初等变换，有 2P(x1⊕x2=0)−1=b1(q1−p1)(q2−p2)+θ

其中θ=2q1q2(b0−b1)+b1−1。

选择参数a1，使得 2P(x1⊕x2=0)−1≈a1(q1−p1)(q2−p2) （5） 进一步，假定有L个比特满足校验方程的约束关系，即x1⊕x2⊕\"⊕xL=0，并假定概率{p1,p2\",pL}对应{x1,x2,\",xL}为1的概率，根据（5）式的推广，校验节点zL=x1⊕x2⊕\"⊕xL=zL−1⊕xL的概率为

2P(zL=0)−1=aL(P(zL−1=0)−P(zL−1=1))(qL−pL)

通过递推，得到 2P(zL=0)−1=∏ai(qi−pi) （6）

i=1L

即，所有比特节点提供给该校验节点的信息

LL

1⎛⎞1⎛⎞1(12p)1a(qp)+−=+− P(zL=0)=⎜⎟⎜⎟∏∏iiii⎟2⎜⎟ 2⎜i=1i=1⎝⎠⎝⎠

L1⎛⎞

P(zL=1)=⎜1(12p)−−∏i⎟⎟=2⎜⎝i=1⎠

L

1⎛⎞1a(qp)−−⎜∏iii⎟⎟ （7） 2⎜⎝i=1⎠

因此，对概率译码算法校验节点的更新采用做如下修正：

1101

δrmn=∏an'δqmn'， rmn=(1+δrmn)， rmn=(1−δrmn) （8）

22n'∈N(m)\\n

130 电路与系统学报 第12卷

改进的译码算法与标准概率译码算法相比，区别在于校验节点的更新引入了修正系数ai来减少环路对译码性能的影响。当信噪比较高时，环路提供给比特x的冗余信息y朝着有利于环路的方向发展，即P(xy)>P(x)，为了降低环路对比特x的影响，需乘以一个小于1的系数；而当信噪比较低时，情况正好相反。若每次迭代修正系数ai均等于1时，改进的概率译码算法与原算法等价。

通过仿真，对系数ai的取值作了进一步的验证，即对最小周长为2l的LDPC码译码时，修正系数的取值遵循：当迭代次数k小于l时，a(k)=1；当迭代次数k大于l时，在高信噪比下选择a(k)<1，低信噪比下选择系数a(k)>1。同时也发现，在迭代的过程中，不需要对不同的节点取不同的修正系数。

4 仿真

图2 不同译码算法性能的比较

为了比较上述译码算法的性能，采用(504,3,6)和(1008,3,6)的规则LDPC码在AWGN信道下进行了计算机仿真。仿真中，校验矩阵采用随机生成方式，考虑到校验矩阵的最小周长为4，所以迭代次数k为1和2时，迭代系数a(1)和a(2)取1，当迭代次数k大于2，根据信噪比的范围来取值，当信噪比大于1.5dB时a(k)=0.9（k=3,…,10），a(k)=0.85（k>10），当信噪比小于1.5时，a(k)=1.05（k>3）。仿真结果如图2表明，从图中可以看出采用修正的概率译码算法性能有所提高。

5 结论

本文对有环路LDPC码的译码算法进行了推导，并给出了修正的概率译码算法。根据最小周长和信噪比来选择不同的修正系数，可以提高LDPC码的译码性能。从仿真结果来看，在低信噪比下，为了折中译码性能和算法复杂度，可以直接采用标准的概率译码算法。在高信噪比下，采用修正的算法可以提高译码性能。 参考文献：

[1]

Gallager R G. Low density parity check codes [J]. IRE Tran. on IT, 1962, 8(1): 21-28. Switzerland, 1993. 1064-1070. [3]

MacKay D.J.C. Good error-correcting codes based on very sparse matrice [J]. IEEE Trans. Inform. Theory, 1999, 45(2): 399-431. 1645-1646.

[4] MacKay D J C, Neal R M. Near Shannon limit performance of low density parity check codes [J]. Electronics Letters, 1996, 32(18): [2] Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbo codes [A]. ICC [C]. Geneva,

作者简介：林雪红（1977-），女，江西上饶人，北京邮电大学博士，研究方向：主要从事移动通信，编码理论方向

的研究；吴伟陵（1938-），男，出生于安徽，北京邮电大学信息工程学院教授，博士生导师，主要从事信息论、信息处理与移动通信方面的教学和研究工作。

Improved decoding algorithm of Low-Density Parity-Check codes

LIN Xue-hong, WU Wei-ling

( Department of Information Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China )

Abstract: LDPC codes with short blocks deviate from the predicted performance, the most likely reason is that they contain quite a few cycles. This paper deduces the probability decoding algorithm of LDPC codes with cycles, and proposes a new algorithm that introduces a correction coefficient to mitigate the impact of cycles on decoding performance. From the simulation results, the new algorithm can improve the decoding performance. Key words: LDPC code; probability decoding algorithm; tanner graph; girth