基于树构造非规则LDPC 码

IrregularLDPCCodeBasedonTreeQunyaoYIN1,BinWEN2*,JianminHE11SchoolofEconomicsandManagement,SoutheastUniversity,Nanjing,Jiangsu,China,2111892DepartmentofMathematics,ChangshuInstituteofTechnology,Suzhou,Jiangsu,China,215500Email:*Abstract:Alowcomplexitygreedysearchalgorithmbasedontreeisproposed.Thisalgorithmcanbeusedtogetthemaximumaveragegirthbyadjustingthecycledistributionofcheckmatrixanddecreasingtheshortlengthcycles,thusresultingingoodshortblocklengthirregularLDPCcodes.Keywords:LDPCcode;Bipartitegraph;girth;searchalgorithm基于树构造非规则LDPC码尹群耀1，闻斌2*，何建敏11东南大学，经济管理学院，南京，江苏，中国，2111892常熟理工学院数学系，苏州，江苏，中国，215500Email:*摘要：本文给出了一种低复杂度的基于树的贪婪搜索算法，此算法通过调整校验矩阵中环的分布情况，尽量减少短长度环，获得最大的平均最小环，从而构造性能很好的短码长不规则LDPC码。关键词：LDPC码；二分图；周长；搜索法1引言近年来，低密度校验（LDPC）码的良好性能吸引了整个编码界的关注。事实上，LDPC码早在1962年便由Gallager1提出，但之后30年几乎被遗忘,直到1995年Mackay和Neal的重新发现才引起了LDPC码新一轮的研究热潮。研究表明,采用迭代译码算法，如置信传播算法（BPA），LDPC码可获得惊人的编码增益。迭代译码算法性能由LDPC码的构造所决定，Tanner等人采用图论的方法分析了LDPC码的迭代译码算法性能，指出LDPC码的最小环长是影响其译码性能的关键因素之一。LDPC码是一种线性码,其码重分布特别是最小码距的大小决定了误码平层的出现，最小码距越大其平层越低，所以一种具有低平层的LDPC好码必然有较好的码重分布特性。LDPC码具有非常好的性能，但是校验矩阵还是由计算机随机构成的，没有一种好的系统分析方法来得到。因此对构造好码的研究分为两个方面：一是寻找构造码的分析方法，二是构造综合性能更好的码。本文提出了一个有效的算法，利用二进制序列构造出了环长大于4的LDPC码，这种码具有较好的码重分布，在保持码长不变的情况下可以增加校验矩阵的列重；并且码长、码率的选择也具有很大的灵活性。仿真表明，所构造的非规则LDPC码在码率相近时，随着码长的增长其误比特率越来越小，并且没有误码平层的出现。2低密度校验(LDPC)码LDPC码是一种线性码，可由它的校验矩阵H来定义；它的校验矩阵又称为稀疏奇偶校验矩阵2，“奇偶性”指的是H中元素的取值只能是0或1，“稀疏性”指的是H中包含0的个数远大于1的个数。LDPC码有两类，一类是规则LDPC码，其校验矩阵中具有相同的行重和列重；另一类是非规则LDPC码，其校验矩阵中的行重和列重不相同。规则LDPC码用（n，j，k）表示，其中n表示码长，j表示列重，k表示行重且H的列数为n，行数为nj/k。后来人们将LDPC码的校验矩阵H对应到二分图。图1所示，上面的节点是比特节点，可以认为是一个码子中的一个比特或者是校验矩阵中的一列；下边的节点是校验节点，每个节点表示一个校验方程或者是校验矩阵中的一行。当码子中某一比特包含在某一校验方程中即校验矩阵相应的位为1时，图1中的上下节点之间存在连线，对于每个节点与之相连的2073Proceedingsofthe20113rdInternationalConferenceonInformationTechnologyandScientificManagement(ICITSM2011)978-1-935068-93-82011SciRes.边数称为这个节点的度数。规则码与非规则码同样可以通过上下节点度数是否分别相同来定义，这种二分图对于LDPC码的译码过程表现的比较直观。图1.LDPC码的校验矩阵与二分图有限码长的LDPC码中存在一种环状结构，使得从某一校验节点或比特节点出发，经过一些彼此相连的边（同一条边不重复经过）之后回到原节点形成环形，这样的环所包含的边数称之为环长，其中最短环的长度称为周长（girth）。如图1所示，V4-C3-V5-C4-V4构成一个长度为4的环，V1-C1-V2-C3-V5-C4-V1构成一个长度为6的环。LDPC码校验矩阵的二分图的周长都是偶数并且大于等于4。3非规则LDPC码的构造假定校验矩阵有m行、n列，即对应一个有m个校验节点、n个变量节点的二分图。1/niiggn为二分图的平均最小环，ig为第i个节点的最小环。给定节点u，其最小环计算方法很简单：我们以u为根，经过f步（f大于或等于），所有与根节点u距离为f的节点都包含在树中。假定在第k步，树中第一次出现了相同节点叶子，则2k便是u的最小环。对于短码长而言，这个算法的复杂度较低。实际上，我们很容易得出上述二分图平均最小环的计算复杂度是2()n。在给定码长n、度数分布对(,)后，我们这样构造校验矩阵：首先设定一个mn维的全零校验矩阵H（其中1100()/()mnxdxxdx），再将列向量按重量非递减顺序依次从右至左添人校验矩阵H中。如,ijvv分别表示第i和第j个列向量，当ij时，iv的列重不大于jv的列重。对于前mn次列添加，我们都要对它进行高斯消去计算，使这mn个列向量线性独立，以保证校验矩阵行满秩。添入校验阵中的所有列向量都是在满足度数分布对条件下随机生成，当准备添入的某一列向量通过贪婪树搜索法所得校验阵的平均最小环达到某一设定门槛时，此次扩展完成。为保证算法收敛且便于控制，我们引人了记数器，当记数器达到设定最大值而校验矩阵的平均最小环还没达到我们要求时，此次计算自动中断，并从先前计算中选出拥有最大平均最小环的列向量添人校验矩阵中。算法的具体细节如下所述。图2.69维的校验矩阵图3.以1v节点出发的GTS搜索法,生存路径由粗实线表示图2是一个69维的校验矩阵。图3是以1v节点为根展开的树，其中，v表示变量节点，c表示校验节点。GTS搜索法是指设定校验阵中各列向量的最小环为一固定值2(1)L，每当选择一列向量（如节点1v）准备加人矩阵时，以1v节点为根展开L级树，逐级搜索树中所有环，确定环中各变量节点因节点1v引入对它们最小环的影响，如最小环值降低，则此次所得值代替原值，反之则不改变原值。在树的逐级拓展中，重复节点只保留一个，保证在生存路径上的节点得以成长，而其它路径上的节点枯姜。这样可避免大量节点的最小环重复计算，从而将计算复杂度从与节点数成指数级关系降为线性关系。以拥有4级节点树的图3为例，实线表示生存路径。在树的逐级拓展中，只有生成路径上的节点才需要计算其最小环。从图中我们很容易看出各节点的最小2074Proceedingsofthe20113rdInternationalConferenceonInformationTechnologyandScientificManagement(ICITSM2011)978-1-935068-93-82011SciRes.环，其中1234,vvvv的最小环为4，8v的最小环为6，7v的最小环为8，而当L设定为4时，56,vv的最小环为10。图4.不同长度的LDPC码的误比特率曲线比较4仿真结果和性能比较下面将分析和比较不同长度的二进制序列构造的LDPC码性能曲线情况，其中当信噪比大于3.5dB时，图4由上至下的5条曲线对应的码长和码率依次为300，0.763，50，0.756，800，0.716，1000，0.699，2000，0.688，从图2中可以看到，所构造的非规则LDPC码在码率相近时，随着码长的增长其误比特率越来越小，并且没有误码平层的出现。References（参考文献）1Gallager.RG.LowdensityparitycheckcodesJ.IEEETransInformTheory,1962,27(8):21-28.2MacKayDJC.GooderrorcorrectingcodesbasedonverysparesmatricesJ.IEEETransInformTheory,1999,45(2):399-431.2075Proceedingsofthe20113rdInternationalConferenceonInformationTechnologyandScientificManage