Group Shuffled BP算法的密度演进和高斯近似

陈 文， 刘斌彬， 白 栋， 葛启宏

(国家广电总局广播科学研究院 北京泰美世纪科技有限公司，北京 100097)

0 引言

低密度校验（LDPC）码最早由Gallager提出，是一种校验矩阵非常稀疏的线性分组码。Mackey等人的进一步研究表明，LDPC码的性能在置信传播（BP）译码算法下可以接近Shannon极限，且译码复杂度低于Turbo码[1]。目前，LDPC码已经被越来越多的用于各种通信系统中。中国的数字电视地面广播标准DTTB和移动多媒体广播标准CMMB均采用了LDPC码的信道编码方案。

LDPC码在应用中所面临的一个问题是译码所需的迭代次数较多，从而影响了译码器的数据吞吐率[2-3]。为了加快译码的收敛速度，Zhang等人提出了Group Shuffled BP译码算法[4]。为了合理的设计译码器的算法，首先需要分析译码算法的收敛性能。密度演进通过跟踪迭代过程中各组节点信息概率密度的变化，可以分析Group Shuffled BP译码算法的收敛性能[5]，但计算的复杂度较高。

为了简化密度演进计算的复杂度，本文在证明对称性条件的基础上，提出了基于Group Shuffled BP译码算法的密度演进的高斯近似。

1 Group Shuffled BP译码算法

BP译码算法是一种性能最好的消息传递（MP）算法[1]。在BP译码算法中，信息在变量节点和校验节点之间来回的传递。设为第i次迭代中校验节点m传递给变量节点n的信息，为第i次迭代中变量节点n传递给校验节点m的信息，为从信道得到的变量节点n的初始信息。校验节点处的信息更新可表示为：

其中N(m) / n表示除变量节点n之外的所有与校验节点m相连的变量节点的集合。变量节点处的信息更新可表示为：

其中M(n)/m表示除校验节点m之外的所有与变量节点n相连的校验节点的集合。

在Group Shuffled BP译码算法中，将变量节点分为若干组，逐组的对信息进行更新，变量节点更新和校验节点更新交错的进行[4]。假设将N个变量节点分为G组，每组包含N / G =q个变量节点。对于第g ( 0≤g＜G ) 组中的变量节点n( g q≤n＜( g + 1) q )，式 (1) 被修改为：

对于校验节点信息和变量节点信息，越多的信息参与对其的更新，其置信度就越高。因此，采用Group Shuffled BP译码算法可以大大加快收敛速度。

2 Group Shuffled BP的密度演进

由于在Group Shuffled BP译码算法中，变量节点被分为若干组，在相应的密度演进中，也需要逐组的对节点信息的概率密度进行跟踪。

对于校验节点更新，定义函数：

则式 (1) 可以通过：

用一种递归的方式来计算[6]，其中 l为该校验节点的度。因此校验节点信息的概率密度为：

考虑Group Shuffled消息传递调度。从式 (3) 可以看出，对于第g组的校验节点信息( gq≤n＜(g+1)q)，其值取决于已更新的变量节点信息(n’＜gq) 和未更新的变量节点信息(n’≥gq)。为了避免对和所有可能组合的 复杂运算，定义已更新变量节点信息的平均概率密度[4]：

定义未更新变量节点信息的平均概率密度：

对于度为l的校验节点m，其传递给变量节点n的信息U(i)mn中共有种可能的组合。对于每一个j(j =0,1,…,l-1)，又有种可能的组合包含 j个已更新的变量节点信息和l -1- j个未更新的变量节点信息。考虑到校验节点度分布ρl，的概率密度为：

利用式(4)、(8)、(9) 和式(10)，则可以跟踪迭代过程中变量节点信息和校验节点信息概率密度的变化。

3 密度演进的高斯近似

可以看出，基于Group Shuffled BP译码算法的密度演进的计算比较复杂。我们考虑采用高斯近似对其进行简化。首先证明信息概率密度的对称性。

3.1 对称性条件的证明

根据文献[5]中)Γ(x的定义，式 (4) 可以写为：

其中⊗表示卷积。式 (10) 可以写为：

文献[5]中给出了下面的定理：

定理1 假设发送的是全零码，则对数似然比（LLR）形式的初始信息在二元无记忆对称信道下是对称性的。

定理2 对称信息的卷积仍然是对称性的。

定理3 函数()Γx和1()Γx-是对称的，当且仅当x是对称的。

定理4 如果函数()Γx是对称的，则它们的卷积也是对称的。

3.2 高斯近似

其中k为该变量节点的度。

对于校验节点更新，定义函数：

对式 (1) 两边取期望，并考虑到变量节点度分布kλ，有：

其中l为该校验节点的度。由于tanh ( μ/2 )为连续函数，其均值可以由μ / 2的均值和方差来近似[8]：

采用函数逼近，式 (16) 可以进一步简化为：

考虑Group Shuffled消息传递调度。类似的，定义已更新变量节点信息的平均均值：

定义未更新变量节点信息的平均均值：

考虑到校验节点度分布ρl，的均值为：

利用式 (13)、式(18)、式(19) 和式 (20)，则可以跟踪迭代过程中变量节点信息和校验节点信息均值的变化。

根据变量节点信息的概率密度，可以计算迭代过程中错误信息的概率，从而分析Group Shuffled BP译码算法的收敛性能。

4 分析与仿真

图 1为采用密度演进的高斯近似计算得到的信噪比Eb/ N0分别为1.8 dB、2.0 dB、2.2 dB和2.4 dB时，Group Shuffled BP译码算法下误码率与迭代次数的关系。分组数样G =36。所选用的码为码长N =9216、码率R =1/2的 (3, 6) 规则LDPC码。可以看出，当迭代次数分别达到5、6、7和8次时，基本上可以实现无错误的译码。

图 2为实际仿真得到的相同信噪比条件下，Group Shuffled BP译码算法的平均迭代次数。最大迭代次数为200次。对比图1可以看出，两者几乎完全一致。也就是说，采用基于Group Shuffled BP的密度演进及其高斯近似，可以比较准确的分析Group Shuffled BP译码算法的收敛性能。

图1 不同信噪比下误码率与迭代次数的关系

图2 不同信噪比下的平均迭代次数

图3为采用密度演进的高斯近似计算得到的分组数G分别为6、9、18和36时，Group Shuffled BP译码算法下误码率与迭代次数的关系。信噪比Eb/ N0=2.0 dB。可以看出，Group Shuffled BP译码算法对收敛速度的加快十分明显。且分组数越大，收敛速度越快。

图3 不同分组数下误码率与迭代次数的关系

5 结语

为了分析Group Shuffled BP译码算法的收敛性能，同时简化密度演进计算的复杂度，本文在证明对称性条件的基础上，提出了基于Group Shuffled BP译码算法的密度演进的高斯近似。从而将密度演进中计算消息概率密度的无限维问题，简化为跟踪高斯分布均值的一维问题。仿真结果表明，该方法具有较高的精确度，可以有效分析Group Shuffled BP译码算法的收敛性能。

[1] MacKay D J C. Good Error-correcting Codes Based on Very Sparse Matrices[J].IEEE Trans. Inform. Theory,1999,45(02):399-431.

[2] 陈燕,蔡灿辉. LDPC码的译码算法研究[J]. 通信技术,2008,41(12):87-91.

[3] 郑慧娟,童胜.LDPC卷积码的快速收敛译码[J].通信技术,2009,42(07):37-39.

[4] Zhang J, Fossorier M P C. Shuffled Iterative Decoding[J]. IEEE Trans. Commun.,2005,53(02):209-213.

[5] Richardson T J, Urbanke R L. The Capacity of Low-density Parity-check Codes Under Message Passing Decoding[J].IEEE Trans. Inform. Theory,2001,47(02):599-618.

[6] Chung S Y, Forney G D, Richardson T J, et al. On the Design of Low-density Parity-check Codes within 0.0045 dB of the Shannon Limit[J]. IEEE Commun. Lett.,2001,5(02):58-60.

[7] Chung S Y, Richardson T J, Urbanke R L. Analysis of Sum-product Decoding of Low-density Parity-check Codes Using Gaussian Approximation[J].IEEE Trans. Inform.Theory,2001,47(02):657-670.

[8] Asoodeh S, Ramezani H, Samimi H. Gaussian Approximation for LDPC Codes[C]//Proc.IEEE WiCOM.Shanghai:IEEE,2007:1437-1440.