LDPC码的优化设计

LDPC码的优化设计[朱艳]搞要I通过码结构优化设计，可以得到性能接近香农限的LDPC好码，其关键是寻找好的次数分布对。本文阐述了几种有效分析LDPC码性能的方法:密度演进分析，高斯近似分析及基于EXIT图的方法， 在此基础上给出了LDPC码优化设计的过程。LDPC码结构设计的研究对提高码的性能和进一步 推动LDPC码的实际应用有着重要的意义。》关键词: LDPC码; 密度演进;高斯近似技术朱艳南京邮电大学通信与信息工程学院团1引言2 LDPC码基础LDPC (Low Density Parity Check)码，最初是由LDPC码是一种具有稀疏校验矩阵H的线性分组码,Gallager'l于1962年提出的。其后沉寂几十年，1993年性举例来说，一个码长N=8,码率R=1/2的LDPC码可 以用能可逼近香农限的Turbo码的出现，带来了纠错编码理论下面的校验矩阵来确定。任- -个 二进制的线性分组码，都上的突破，D.J.C.MacKay和M.Neal等人”对LDPC码重新可以用“二分图(Bipartite Graph)”描述。上面例子中进行了研究，发现它同样具有逼近香农限的性能。现在它的LDPC码二分图表示如图1所示。已成为通信技术中的新的研究热点，其技术也日趋成熟。实验上的结果表明LDPC性能极为优异,文献"中优化设计的非正则LDPC码在AWGN信道上的理论极限性能[1 0011001]m0 110101 0|m.若"仅仅比香农限高0.0045 dB.>m中国煤化工，LDPC码结构的优化是要找到具有更好性能，离香农限更近的次数分布对。本文介绍了几种码结构优化的分析1YHCNMHG4方法、密度演进、高斯近似、EXIT图等。n,图1 LDPC码的二分图66LDPC码的优化设计二分图由变量节点(Variable Nodes)、校验节点LLR(r,)=0(Check Nodes)以及连接它们的边(Edge)组成。左侧的节点为变量节点,代表了编码后的比特位，对应校验(2)计算变量节点i到校验节点j的消息，矩阵中相应的列;右侧的节点为校验节点，代表了编码比LLR(q,)= 2 LLR(ry)+ LLR(p,)特组成的校验方程，对应校验矩阵中相应的行;图中的边(3)计算校验节点到变量节点i的消息，则表示左侧的某个比特出现在右侧的某个校验方程中，对应了校验矩阵中的非0元素。校验方程表明，对一有效的LL()=(-1)40N2tanh-(. I tanh(; L(,))码字，与各个校验节点相连的变量节点其模2加的和应为0。在二分图中，d. d分别表示与变量节点和校验节点相(4)每个变量节点计算后验LLR,连的边数，称为该节点的次数(degree)。当d、 d。为 常数LLR(q,)= 2 LLR(y,)+ LLR(p,),1eM()时，这样的LDPC码称为正则(regular)码，如上例所示。而当二分图中的变量节点的次数各不相同(校验节点的次(5)进行硬判决LLR(q;)>=0判为1,否则判为0,数也有相应的变动)时，称为非正则irregular)码。非正得x_ hat,如果mode(x_ _hat'H' ,2)=0则译 码成功。则码通常用次数分布对(degree distribution pair)(1,p)来(6)否则重复步骤2~5,直到最大迭代次数，译码失描述:败。硬判决译码，复杂度最低，性能也最差，BP算法译技A(x)=金1p(p(x)=p;.x-分别码复杂度在MP算法类中最高，性能也最好。1=2从二分图中看，对于变量节点，与之相连的边越多为变量节点和校验节点的次数分布多项式; A(p,)表示越好，如果边越多，那么它可以从更多的相邻校验节点得与次数为i的比特(校验)节点相连的边数在总边数中所到更多的边信息，这样就可更准确的判断出它的正确值;占的比例; d,px (dgx) 表示比特(校验)节点中的但对校验节点来说，恰好相反，与之相连的边越少越好。如果与校验节点相连的边越少，那么它就可以给相邻的信最大次数。息节点发送更有效的校验信息。对于两种相矛盾的要求,LDPC码的性能与采用的译码算法密切相关，非正则码显然能较正则码可更好的实现两者的均衡。Gallager在提出LDPC码"时给出了两种迭代译码算法:但是并非所有的非正则码性能都优于正则码，优化硬判决和概率译码。后者虽有好的性能，但太复杂。选择节点的次数分布(.p),可以提高LDPC码的性能。Message Passing算法是一种工I作在图论基础上的译码算法，由于在算法的运行过程中，可靠性信息在二分图的变3次数分布对的优化设计量节点和校验节点之间来回的传递，因此称为MessageGallager在最初的文献"中，在BSC(二进制对称信Passing算法。它是-一个算法类，如果相互间传送的是硬道)上分析了(3,k)正则码进行硬判决译码的性能;判决信息，算法即成为Gallager提出的硬判决译码，如Richardson等人在文献[4]中分析了非正则码(3,2)在BEC果传递的消息是连续的软判决信息，就等价于BP(Belief(二元删除信道)上用MP (Message Passing)算法译Propagation)算法。码时的性能，发现LDPC码存在一种“门限BP译码算法过程如下所示:(Th中国煤化工于某一门限值时，2或信MHCNMHG,在码长足够大的(1)初始化: LLR(p;)==y; (AWGN信道).情况下，码集中的几乎任何一种码的误码率都能随着迭代σ2009.8广东通信技术》技术交流译码次数的增加而递减趋近于0;反之，误码率将始终大P= P 8 a[r"([(P_))(2)于某一正的常数。对应某一码集的门限值也可看成码容量其中，r. r-I 分别表示定义在两种消息域上的概(Capacity)。具有良好特征的二分图，其对应的LDPC率密度函数域之间的变换和反变换。码集有高译码噪声门限，也具有较大的码容量。(2)近似Density Evolution相关研究表明这个信噪比门限取决于LDPC码的次数分布。这方面研究往往结合次数分布优化技术和密度演进用密度演进(DE)计算门限，优化次数分布是困难(Density Evolution)技术来搜索具有高译码噪声门限的的，复杂度很高，相应的就有了近似DE算法。近似算法的基本思路是将PDF迭代的多维计算问题转化为仅仅次数分布对。计算一个参数(通常是高斯函数)迭代的-维计算问(1)基于BP算法的密度演进密度演进(DE: Density Evolution)分 析的思想是由题。几种常见的近似DE方案:高斯近似(GA-GaussianRichardson等'在研究MP(Message Passing)译码算法时Approximation),基于EXIT图的方法，Semi高斯近似。Sae-Young Chung等間提出对概率密度函数进行高提出的:通过考察译码消息的概率密度函数(PDF一Probability Density Function)在译码迭代中的演进情斯近似的方法，根据译码消息的独立性条件和大数定理,况，分析译码算法的收敛情况。变量节点次数d,较大时，从变量节点发往校验节点的译在DE分析中，通常需要满足对称性(symmetry)的条码消息v近似呈高斯分布;从校验节点发往变量节点的译件。Richardson等人“已证明，在对称性条件下， 译码差码消息u则不像高斯分布，尤其是当它的均值靠近0的时错概率具有条件独立性(Conditional Independence)，候。但是研究发现，假设译码消息V. u为高斯分布的随即，译码差错率与发送的码字无关。这样，就可以假设发机变量不仅不影响对BP算法的密度演进分析，还可以简送的是全1码字来计算DE.化密度演进的分析过程。而由对称性条件，消息的均值与在译码算法的消息独立性条件下，译码中的消息求方差之间存在着联系: σ°=2m° 因此，在GA分析中，和运算，其密度演进对应译码消息的PDF的卷积运算。因对应的密度演进就进-步简化为一个参数(均值)的运此，为简化DE分析，Richardson等'45)引入另一种消息形算。迭代公式如下所示:式，并定义了两种消息域上的映射Y:[-∞,+∞]→GF(2)x[0,+∞],使得BP算法的译码(4)迭代都为消息求和运算:其中，l为迭代次数，m。if(1=0)(u-x)户m"={mo+ 2 m") if(l≥1)qx)={-底' [uanh exp(-4-)du (x>0)c'eCct(x=0)m")=y"[ Er(m!=")](1)中(x)函数的直接计算很复杂，可以作如下近似计v'e叫算:其中，l为迭代次数，m(为从变量节点v发往校验对较小的x，如x <10，中(x)~e*+B, 其中节点C的译码消息，m"表示从校验节点发往变量节点的a=-0.4527，β=0.0218， Y= 0.86;中国煤化工)取上.下界的平均译码消息，mg为初始消息。 若令P. Q、P分别表MHCNMHG值，示它们的PDF.则话e(-元)LDPC码的优化设计这一简化不但使得求取LDPC码的门限值的计算变得似，EXIT图等方法得其门限值。简单，而且可以更直观地理解译码器的工作原理。另外,若采用GA算法计算门限值，则评价次数分布对高斯近似还方便了在AWGN信道上设计非正则码的次数分(h,p)时。先给定- -个较小的信道参数(高斯信道的σ参布对。数)，再将对应的初始消息的均值一代入式(4)中，EXIT ( Extrinsic Information Transfer)图是由S. tenBrink提出的一种用迭代译码器之间传输的外信息来表征进行迭代。若在给定的最大迭代译码次数内，译码的错误迭代译码中收敛行为的分析工具。s. ten Brink等人”将消息概率小于之前设定的目标值E(足够小，接近于0),则EXIT图技术引入到LDPC码译码分析中，即把LDPC码认为该信道参数小于门限值，并按某步长增大信道参数σ的译码过程可以看作是变量节点译码器和校验节点译码器重新代入计算;若新的信道参数使得迭代始终无法收之间外信息的迭代，用EXIT图跟踪译码器之间的互信息敛，即译码的错误消息概率不能达到目标值，则认为超出传递来估计LDPC码和积译码算法的收敛性。基于EXIT了门限值，并取增大前的信道参数σ作为该次数分布对图的方法可以看作是DE方法的一种简化方案，它的优点(.ρ)的门限值σ°。在于:在迭代的过程中跟踪的是互信息的值，与DE方法③优化算法中的概率密度函数. GA方法中的均值等相比较，具有更搜索具有高译码噪声门限的次数分布对是一种复杂好的鲁棒性。其对码的性能分析和估计比高斯近似方法更的非线性优化技术。主要有局部优化和全局优化的两种不准确，与密度演进方法相比计算复杂度也小得多。同的方法。局部优化的方法利用局部优化的结果进行试探技(3)优化设计过程术性的搜索.以减小搜索空间。全局优化的方法从整体上进LDPC码的门限是使得所有译码迭代收敛或译码消息行优化。的密度演进收敛的信道参数的上限。它表明了正则或非正采用DE. GA可以得出具体次数分布对下LDPC码的则LDPC码能够达到的码容量的上界，反映了LDPC码能门限值，结合优化算法可以优化设计次数分布对。优化算够容忍的信道环境的恶劣程度.因而是评价LDPC码的重法可以采用差分进化，PSO算法及各种改进算法等。要标准。④目前次数分布对寻找的成果而优化设计LDPC码，就是在次数分布的解空间中,对于二元输入的BI-AWGN信道，已经找到了门限值搜索具有高门限值的LDPC码。与香农限仅仅相差0.0045dB的次数分布对，而仿真表明.①解空间在码长为10'. R= 1/2时，它的性能曲线距离香农限只差次数分布多项式中的系数是待优化变量，相互之间0.04 dB*。J.Hou等鬥研究了平坦瑞利衰落信道中LDPC码存在码率约束Zp,/i=(1-R)22/j.归一化约束的优化和性能分析，证明优化了的非正则码(码长为3072)性能优于相应的Turbo码。h=1--三不. p:=1-Ep同时校验节点的次数4结束语分布具有集中形式: p(x)=ρ.x*-'+(1-ρ)x。 去除通过LDPC码的码结构优化设计，可以获得性能尽可次数分布对中的冗余变量后得到待优化的目标向量能好的LDPC码。LDPC码结构设计的研究对提高码的性能和进(...).其中独立变量数为L=d, -2.中国煤化工要的意义。本文介②计算LDPC码的门限值绍了密TYCHCNMHG点及LDPC码优化设给定次数分布对时，可以通过密度演进，高斯近计的过程，后面可将其他的优化技不与LDPC码性能分析方法相结合.如PSO算法及各种改进算法和DE技术或者EXIT692009.8广东通信技术》技术交流围方法进行结合，寻找一种兼顾性能和复杂度的有效搜索3 T.J.Richardson, M.A.Shokrollahi and R.L.Urbanke. Design方法，是码结构优化设计的一-个可行的研究方向。of Capacity-Approaching Iregular Low Density Parity-Check Codes. IEEE Trans. on Inform. Theory, 47(2):619-637, 2001参考文献1 R.G.Gallager. Low-Density Parity-Check Codes. IRE3 Sae-Young Chung, TJ.Richardson and R.L.Urbanke.Transactions on Information Theory, IT-8:21-28, 1962Analysis of Sum-Product Decoding of Low-Density Parity-2 David J.C.MacKay and R.M.Neal. Near Shannon LimitCheck Codes Using a Gaussian Appoximatin. IEEEPertormance of Low-Density Party-Check Codes.Transactions on Information Theory, 47(2): 657-670, 2001Electronics Ltters, 32(18): 1645-1646, 19963 Stephan ten Brink, Gerthard Kramer and Alexei Ashikhmin.3 S.Y. Chung, G. D. Fomey, Jr, T. J. Richardson, andDesign of Low-Density Parity Check Codes for Multi-R. Urbanke. On the design of low density parity-checkAntenna Modulation and Detection. IEEE Transactions oncodes within 0.0045 dB of the Shannon limit. IEEEcommunications,52(4):670-678.2004Communication Letters, 5(2): 58-60. 20013 J. Hou, P. H. Siegel and L. B. Milstein, Perormance3 T.J.Richardson and RL.Urbanke. The Capacity of Low-analysis and code optimization of low density parity checkDensity Parity-Check Codes under Message-Passingcodes on rayleigh fading channels, IEEE J.S.A in Commun.decoding. IEEE Trans. on Inform. Theory, 47(2);599-618,19(5):924-934. 20012001(收稿日期:2009-07-15)技:=:=:=:=i=:=:=i=:=:=:=:=:=:=:=:=: =:3 =:=: = =:=:=:=:=i=: = =:=(上接第58页)Wireless Networks, IEEE Jourmal on Selected Areas inConference, 2007, Globecom' 07. November 2007.Communications, January 2008.41 Niyato.D, Hossain.E. Equilibrum and Disequilibrum39 Dusit Niyato, Ekram Hossain. Competitive Pricing forPricing for Spectrum Trading in Cognitive Radio: A Control-Spectrum Sharing in Cognitive Radio Networks: DynamicTheoretic Approach. IEEE Global TelecommunicationsGame, Iefficiency of Nash Equlibrium, and Collusion.Conference, 2007, Giobecom' 07. November 2007.IEEE Joumal on Selected Areas in Communications,42 Kyasanur Pradeep and Valaya Nitin H. Protocol designVOL26, NO.1 January 2006.chanlenges for multi-hop dynamic spectrum access40 Niyato.D. Hossain.E. Optimal Price Compettion fornetworks. In Proe IEEE DySPAN' 05. Baltimore,Spectrum Sharing in Cognitive Radio: A Dynamic Game-November 2005:645-648(收稿日期:2009-07-10)欢迎订阅《广 东通信技术》《旷东通信技术》创刊于1981年，是中国电信股份有元，国内外公开发行。国际标准刊号: ISSN 1006- 6403;限公司广东分公司主管，广东省通信学会和广东省电信情报国内统-刊号: CN44- -1221/TN.中心站联合主办的广东省唯- -的综合性通信技术刊物。全国各地邮局均可订阅。国内邮发代号: 46-245.《广东通信技术》主要反映广东通信建设的最新成就中国煤化工里订阅，具体事宜与和交流引进、吸收国内外先进通信技术的经验，介绍国内外最新通信技术的发展及趋势等。MYHCNMHG《广东通信技术》月刊，大16开，全年定价120.00联系人:方小姐70|