熊 磊,姚冬萍,陈 霞

(北京交通大学轨道交通控制与安全国家重点实验室,北京100044)

1962年Gallager提出的低密度奇偶校验(Lowdensity Parity-Check,LDPC)码是一种具有逼近Shannon容量限和相对较低译码复杂度的优异信道编码,近年来得到了广泛关注[1-2].Chung S.Y.等人采用离散密度进化算法搜索LDPC码的最佳次数分布对,在采用置信传播(Belief Propagation,BP)译码算法下获得了距Shannon容量限仅0.004 5 dB的优异性能[3],然而这一性能是在假定码长无限长且Tanner图中不存在环的情况下得出的.当存在环时,译码时将发生信息的自反馈,破坏了信息传播的独立性,导致译码性能的降低.最短环长(即围长)越小,短环的数量越多,码字性能的恶化就越明显.构造具有较大围长和较少短环的码字是当前LDPC码研究的重要问题之一.

Kim J.L.等人提出了不包含环长为4的环(4线循环)LDPC码的构造方法[4];Yu Kou等人提出的有限几何构造法,可以按围长要求进行码字的构造[5];Campello J.和Modha D.S.提出的比特填充(Bit Filling,BF)构造方法,在给定的围长约束条件下,向校验矩阵逐个添加‘1'元素,可以获得具有较大围长的码字,但构造复杂度与码长的3次方呈正比[6-7].Hu X.Y.提出的渐进边增长(Progressive Edge-Grow th,PEG)构造法由无环的Tanner图开始,逐条增加边,每次增加时都使得新增边所形成的环尽可能地长,从而以较低的复杂度(与码长的平方呈正比)实现了较大的围长,被普遍认为是当前性能最好的 LDPC码构造方法[8-9].Lin Yi-Kai和 Wei Zhan等人将PEG构造法应用于结构化LDPC码的构造也获得极佳的性能[10-11].Dejan Vukobratovi等人提出了优化环的外信息度[12],Richter G.则提出停止集(Stopping Sets)的概念来改善PEG构造法的性能[13].

针对现有PEG构造法忽视最短环数量所造成的性能恶化,本文作者提出了环多项式的概念,并在此基础上提出了基于环多项式的渐进边增长(Progressive Edge Growth based on Polynomial of Cycle,PEGPC)构造法.该构造法借助环多项式,优化了新增边的选择,不仅可以实现较大的围长,而且有效地减少了最短环的数量,改善了LDPC码的性能.

1 树型图与环多项式

如图1所示,假定PEG构造法要为比特节点si增加一条边,则以其为顶点,将Tanner图逐层展开,直到树型图包含的校验节点数达到最大为止.假定某校验节点cj首次出现于树型图中的第l层,如果在si和cj之间增加一条边,该新增边所形成的最短环长为2(l+1).显然,PEG构造法尽可能选择处于树型图底部(即 l值较大)的校验节点.由于新增边所形成的环相对较长,从而尽力而为(Best-Effort)地避免了短环的出现,以较低的复杂度实现较大的围长.然而PEG构造法没有考虑减少短环的数量.为了更全面地表征新增边对Tanner图的影响,本文提出了环多项式的概念.

如图1所示,假定树型图中某校验节点cv是由比特节点su扩展而来,则称节点su为cv的父节点,而cv则为su的子节点.父节点与子节点是相对的,且一个节点的父节点和子节点可能不只一个.

图1 树型Tanner图Fig.1 Tree-like Tanner graph

节点的环多项式的计算方法如下:①令顶点的环多项式为1,如图1中,f(si)=1;②子节点的环多项式为其父节点环多项式的幂次加1,即乘以 x ,如cv的多项式f(cv)=xf(su);当父节点不唯一时,则先对其各父节点的环多项式求和,然后幂次再加1;③未在树型图中出现节点的环多项式为0.

由于Tanner图是二分图,所以校验节点的环多项式的幂次必为奇数,而比特节点的环多项式的幂次则必为偶数.假设校验节点cj的环多项式为

式中:f(cj)表示新增边(si,cj)将给整个Tanner图添加hk条长度为2k的环;hk+1条长度为2(k+1)的环,依此类推.

校验节点环多项式的幂次表示新增边所形成的环长,而系数则为所对应环长的数量.如果 cj的多项式为0,则表明cj未曾在树型图中出现,那么增加边(si,cj)不会导致任何环长小于2(l+2)环,其中l为树型图扩展的最大层数.

需要注意的是,cj的环多项式反映的是由于增加边(si,cj)而形成的环,且只有校验节点的环多项式才具有实际的意义.

环多项式以多项式的形式实现了对环的长度和数量精确的数学刻画,可用于码字分析和构造等领域.

2 PEGPC构造法

PEGPC构造法采用比较各校验节点的环多项式进行新增边的选择,比较过程包括如下两步:

步骤1:比较各校验节点的多项式的最低幂次,选择最低幂次最大的校验节点.最低幂次越大,则表明选择该校验节点所形成的最短环的环长也就越大.当结果不唯一时,则继续进行第2步.

步骤2:比较最低幂次的系数值,选取系数值较小的校验节点.幂次的系数值越小,选择该节点所形成最短环也就越少.如果选择结果仍不唯一,则回到第1步比较幂次较高的项,也可以从中随机选择一个.

在实际构造中,为了简化比较过程,通常给 x赋一个值(如令x=0.1),将环多项式简化为一个代数值,从而将比较环多项式的幂次和系数值简化为比较环多项式的值,将两步比较大大简化一步比较.与PEG构造法相比,简化后的PEGPC构造法的复杂度没有明显增加,而且只要满足0＜x≪1,其构造性能基本不会发生恶化.

假定要构造一个码长为N,包含m个校验式的LDPC码,PEGPC构造法步骤如下所示:

对每一个比特节点si,

1)添加与si相连的第1条边,选择当前节点度最小校验节点的cj,添加第1条边,即.

2)初始化:

①比特节点环多项式初始化

②校验节点环多项式初始化

3)如图1所示以si为顶点扩展树型图,每扩展一层对各节点的环多项式进行以下更新:

①校验节点环多项式更新,若校验节点cv由比特节点su扩展而来,则

②比特节点环多项式更新,若比特节点sq由校验节点cp扩展而来

4)新增边,选择环多项式的值最小的校验节点cj,即

其中 Vc为可选校验节点的集合.

为si增加第k条边,即Eksi=(si,cj).

返回步骤2),继续为 si增加边,直至与 si相连全部边增加完毕.

3 仿真结果

本节在高斯白噪声(AWGN)信道下,对PEGPC的性能进行仿真.仿真采用(N=504,R=1/2,dv=3,dc=6)正规 LDPC码;在 PEGPC构造法中,令 x=0.1;采用BPSK调制,归一化BP译码算法,归一化常数α=1.15,最大迭代译码次数设定为100,在每个信噪比点至少收集50个错误码字.

图2 本地围长分布图Fig.2 Girth histograms of PEGPC code,PEG code and a random code

图2给出了PEGPC码、PEG码和删除了4线循环的随机码的本地围长(即各比特所参与的最短环长)分布图.随机码的围长仅为6,本地围长均值为6.43,而PEGPC和PEG码的围长均达到了8,本地围长均值则分别为8.079和8.004(见表1).与随机码相比,PEGPC和PEG码的围长和本地围长均值都有了明显提高.相比于PEG码,PEGPC码的围长和本地围长均值虽然没有明显提高,但最短环(即长度为8的环)的数量却有了明显的下降,如图3所示.PEG码共包含844个最短环,而PEGPC码则减少为398个,下降约52.8%.

表1 围长、本地围长和最短环数量比较Tab.1 Comparison of girth,local girth and number of shortest cycles

图3 最短环数量分布图Fig.3 Histograms of number of the shortest cycles

图4为PEGPC码、PEG码和随机码的误比特率(Bit Error Rate,BER)曲线对比图.随着的增大,PEGPC码在性能上的优势逐渐明显,在=3.5 dB时,PEGPC码的BER只有约PEG码的1/3,而比随机码则要低近两个数量级,在BER=10-5时,PEGPC码要优于PEG码约0.1 dB,优于随机码约0.45 dB.

图4 PEGPC码、PEG码和随机码的 BER性能Fig.4 BER curves for PEGPC code,PEG code and random code

4 结论

本文作者提出了环多项式的概念,并在此基础上提出了基于环多项式的渐进边增长构造法,在选择新增边时,利用环多项式,不仅保证了新增边形成的环尽可能长,而且短环的数量尽可能少,优化了码字构造.仿真结果表明,该方法在保证较大围长的同时,短环数量可以降低约52.8%.短环数量的减少降低了信息自反馈对译码性能的影响,明显改善了LDPC码的性能,且构造灵活,构造复杂度低.

[1]Gallager R G.Low-Density Parity-Check Codes[J].IRE Transactions on Information Theoryy,1962,IT-18,:21-28.

[2]Gallager R G.Low-Density Parity-Check Codes.Cambridge[M].MA:MIT Press,1963.

[3]CHUNG Saeyoung,Forney G D,Richardson T J,et al.On the Design of Low-Density Parity-Check Codes with in 0.0045 dB of the Shannon Limit[J].IEEE Communications Letters,2001,5(2):58-60.

[4]Kim Jonlark,Peled U N,Perepelitsa I,et al.Explicit Construction of Families of LDPC Codes with no 4-Cycles[J].IEEE Transactions on Information Theory,2004,50(10):2378-2388.

[5]Kou Y,Lin S,Fossorier M.Low-Density Parity-Check Codes Based on Finite Geometries:A Rediscovery and New Results[J].IEEE Transactions on Information Theory,2001,47(7):2711-2736.

[6]Campello J,Modha D S.Designing LDPC Codes Using Bit-Filling[C]∥IEEE ICC 01',2001:55-59.

[7]Campello J,Modha D S.Extended Bit-Filling and LDPC Code Design[C]∥IEEE Globecom 01',2001:985-989.

[8]HU Xiaoyu,Eleftheriou E,Arnold D M.Progressive Edge-Growth Tanner Graphs[C]∥IEEE Globecom 01',2001:995-1001.

[9]Hu Xiaoyu,Eleftheriou E,Arnold D M.Irregular Progressive Edge-Growth(PEG)Tanner graphs[C]∥IEEE Internation Symposium on Information Theory(ISIT 02'),2002:480.

[10]Lin Yikai,Chen Chinlung,Liao Yenchin,et al.Structured LDPC Codes with Low Error Floor Based on PEG Tanner Graphs[C]∥IEEE Internation Symposium on Circuits and Systems(ISCAS 08'),2008:1846-1849.

[11]Zhan Wei,Zhu Guangxi,Li Peng,et al.Quasi-Cyclic LDPC Codes Based on D and Q Matrices Through Progressive Edge Growth[C]∥IEEE Internation Symposium on Intelligent Signal Processing and Communication System(ISPACS 07'),2007:12-15.

[12]Vukobratovic D,Senk V.Generalized ACE Constrained Progressive Edge-Growth LDPC Code Design[J].IEEE Communication Letters,2008,12(1):32-34.

[13]Richter G,Hof A.On A Construction Method of Irregular LDPC Codes Without SmallStopping Sets[C]∥IEEE Internation Conference on Communication(ICC 06'),2006:1119-1124.