一种具有较大围长的正则LDPC码构造方法

　　摘 要:提出一种新的具有较大围长的正则LDPC码构造方法。首先介绍以矩阵分裂技术为基础的高围长正则LDPC码的构造方法,并在此基础上分析了设计围长时参数的选取方法。仿真表明,用这种方法构造的正则LDPC码围长可以达到12,并且在AWGN信道下的性能不差于相同参数、随机构造的LDPC码,在高信噪比时甚至优于相同参数的随机码。
　　关键词:低密度奇偶校验码;高围长;矩阵分裂;正则LDPC码
　　中图分类号:TN911.72 文献标识码:A
　　文章编号:1004-373X(2010)03-087-03
　　
　　Method for Construction of Regular LDPC Code with Large Girth
　　HUANG Xiang,Senbai Dalabaev
　　(School of Information Science & Engineering,Xinjiang University,Urumqi,830046,China)
　　Abstract:A construction method of strucred regular Low-Density Parity-Check(LDPC)code with large girth based on matrix dividing is proposed.The parameter option about girth accuting is analysed.Simulation results show that these codes′ girth can achieve 12 based on this method,besides that,its performance is not worse than randomly constructed LDPC code in the same parameter under AWGN channel.Even better than the same parameter random code at high SNR situation.
　　Keywords:low-desity parity-check codes;large gith;matrix dividing;regular LDPC code
　　
　　1962年Gallager提出低密度校验(Low Density Parity Check,LDPC)码[1],后来Tanner对它进行了很有价值的补充[2],直到1995年又被Mackey重新提出[3]。如果采用和积迭代译码算法,LDPC码具有非常接近香农限的性能。如果在LDPC码的Tanner图中存在环,在迭代译码的过程中错误信息将会膨胀,对于LDPC的译码性能相当有害,尤其是较短环的存在,所产生的危害尤为严重。所以,在构造LDPC的过程当中,要尽量避免短环的出现。为了尽量减小Tanner图中环的存在对相应LDPC码在和积译码算法下所得性能的影响,一些研究学者基于代数方法和启发式搜索方法,提出了一些具有较大围长的LDPC码构造方法。研究表明,通过增大LDPC码的围长,在一定程度上可以改善码的纠错性能。本文构造了正则LDPC码,在构造过程中讨论了设计围长的参数选举,使得满足一定的条件就可以避免校验矩阵的小围长出现,使得所构造的矩阵具有较大围长。
　　
　　1 LDPC码的构造理论[3,4]
　　
　　考虑长为16的(2,4)正则LDPC码对应的Tanner,如图1所示。
　　图1 (16,2,4)LDPC码的Tanner图表示
　　从图1中很显然可以看出,该Tanner中环的最小长度为8,因此对应LDPC码的围长也为8。
　　按图1将其中的变量结点和校验结点依次编号,可以得到对应LDPC码的校验矩阵,如图2所示。
　　图2 (16,2,4)LDPC码的校验矩阵表示
　　图2矩阵很有规律,可以看作是由两个行重为2、维数为8×8的循环方阵拼接而成。因此可以猜想,采用某些有规律的矩阵合并成校验矩阵,这样生成的LDPC码很可能会具有较大的围长。或者说,将LDPC码的校验矩阵分裂为若干个子矩阵,然后每个子矩阵再按照某种规律构造,就有可能避免小环的出现。
　　这里采用矩阵分裂[5-7]的思想。设要构造一个长为n(n=ρUU∈N)的(λ,ρ)正则LDPC码,将该码的校验矩阵分裂为(λ,ρ)个U×U的子矩阵。
　　H=H0H1Hλ-1=H0,0H0,1…H0,ρ-1H1,0H1,1…H1,ρ-1Hλ-1,0Hλ-1,1…Hλ-1,ρ-1
　　(1)
　　式中:每个子矩阵Hi,j=I(ai,j)(0≤i<λ,0≤j<ρ)均为一个单位阵或者单位阵的循环移位;ai,j表示该单位阵的各行循环右移的位数。显然,这样构造的校验矩阵也不可能为满秩,至多为λρ-λ-1。
　　为便于描述,用A=(ai,j)表示由各个子方阵的循环移位参数组成的矩阵,用(I,J,i,j)表示校验矩阵中的元素,其中(I,J)为该元素所属的子矩阵的坐标,(i,j)为该元素在它所属的子矩阵中的坐标。称Tanner图中每个变量结点参与的所有环的最小长度为该变量结点的环长,则显然相应LDPC码的围长就等于各个变量结点环长的最小值。将n个变量结点分为P组,每一组变量结点对应一列子矩阵,则考虑到各个子矩阵的循环特性,有如下定理成立。
　　定理1 属于同组的变量结点具有相同的环长。
　　证明:设任意两个同组的变量结点x和y,分别对应一列子矩阵的第x列和第y列,且y-x=dmod U,其环长分别为C(x)和C(y),并设变量结点x的最小环路径如图3所示。
　　图3 变量节点x的环路示意图(一)
　　根据各个子矩阵的循环特性,可以找到另一个环的路径如图4所示。
　　图4 变量节点x的环路示意图(二)
　　显然该环路长度为C(x)且经过变量节点y,故有:
　　C(x)≥C(y)
　　(2)
　　同理可得:
　　C(x)≤C(y)
　　(3)
　　综合上面两式,有C(x)=C(y)即对任意两个同组的变量节点,它们的环长均相等,证毕。
　　由定理1可知,按照上述方法构造的校验矩阵所对应的LDPC码,所有变量节点的环长至多有ρ种情况,因此对这样构造的矩阵只需要分别从各组中抽取一个变量节点,然后只对这ρ个变量节点进行检测,即可确定整个码的围长。
　　2 校验矩阵中循环移位参数的选取
　　下面讨论4环的情况。如果一个LDPC码含有4环,则它所对应的校验矩阵中必然有4个“1”处于某个矩形的四个顶点,该环路路径可表示为:
　　显然,应有:
　　i+aI1J1=i+aI1J2-aI2J2+aI2J1mod U
　　(4)
　　化简后得:
　　aI1J1+aI1J2-aI2J2+aI2J1=0 mod U
　　(5)
　　至此,可以得到如下定理。
　　定理2 按照式(1)所示矩阵分裂方法构造的矩阵所对应的LDPC码不含长为4的环的充要条件有式(6)成立:
　　aI1J1+aI1J2-aI2J2+aI2J1≠0 mod U,
　　I1≠I2∈{0,1,…,λ-1},J1≠J2∈{0,1,…,ρ-1}
　　
　　(6)
　　该定理的正确性从前面的描述中即可得知,这里不再赘述。
　　由定理2很容易得到下面推论:
　　推论1:按照式(1)所示矩阵分裂构造方法构造的矩阵所对应的LDPC码不含长为2l的环的充要条件为:
　　∑l-1k=0(aIkJk-aIkJ(k+1)mod U)≠0mod U,
　　Ik≠I(K+1)mod l∈{0,1,…,λ-1},
　　Jk≠J(k+1)mod l∈{0,1,…,ρ-1}
　　在编码设计时,可以首先确定所构造LDPC码设计围长,然后根据上面的定理和推论列出相应的不等约束,进而寻找满足这些不等约束的参数即可。
　　在进行参数选择时,可以根据上面分析和设计的围长列出各参数所对应满足的约束方程,然后寻找满足这些约束方程的参数取值。然而,由于这些约束方程均为不等约束,因而无法采用一般的方程组求解法;如果采用穷举的方法去遍历各个参数的所有可能组合,继而从中找出满足约束的一组,搜索的范围将有U(λ-1)(ρ-1),这样即使U的取值范围很小(如102),总的搜索范围也将很大,因而无法实现。
　　为了实现参数的快速选取可以采用下述逐参试探算法:
　　(1) 令ai,0=0(i=0,1,…,λ-1)及a0,j=0(j=1,2,…,ρ-1);
　　(2) 随机在{0,1,…,U-1}中选取a1,1的取值,然后判断a1,1是否满足给定的不等约束,若满足则确定取值,否则重新执行(2)
　　(3) 按照(2)的方法一次确定剩余子矩阵的循环移位参数。
　　按照上面算法,每个参数至多需要U次试探,这样总共的试探次数至多为(λ-1)(ρ-1)U,远远小于整个搜索空间U(λ-1)(ρ-1)。
　　由于该算法采用逐个确定参数的方法,显然最后确定的参数受到的约束是最多的,定义N(l)为考虑消除Tanner图中长度为2l的环时最后一个参数受到的约束方程个数,则有:
　　N(2)=C15×C12=10
　　(7)
　　N(3)=C15×C12×C14=40
　　(8)
　　N(4)=C15×C12×C15×C12×C14=400
　　(9)
　　由于各个约束方程均为不等约束,每个约束只能限制参数不能取某个特定的值,因此所有不等约束限制参数所不能取的值的个数至多为约束方程数目的两倍。考虑到所要构造的LDPC码的码长,U的取值一般在100左右,因此消除六环一般都可行。
　　
　　3 仿真及性能分析
　　
　　取U=168,按照上面的方法构造长度为1 008的(3,6)正则LDPC码,通过计算机搜索检测发现,得到子方阵的循环参数为:
　　A=000000
　　06912291980
　　0955465859
　　检测发现LDPC码的围长为10,为了保证所构造码的码率严格等于0.5,可以从生成的检验矩阵中删去2个“1”。该码在AWGN信道下的纠错性能如图5所示,图中的另外两条曲线分别为相同长度、随即构造、不消除4环的(3,6)正则LDPC码的性能曲线。其中,girth表示围长;ave表示所有变量节点的平均环长。
　　文献[8,9]采用PEG算法所构造的长度为1 008的(3,6)正则LDPC码的围长为8,平均环长为9.66,稍劣于上面构造的LDPC码,因此该方法用于正则LDPC码的构造时要优于其他的构造方法。
　　通过分析发现,采用该方法构造的正则LDPC码与文献[10]所述方法一样,其围长存在一个上限,下面进行详细介绍。考虑一个维素为2U×3U的矩阵,将其分裂成6个维素为U×U的子方阵,每个方阵均为单位阵或单位阵的行循环移位,则可以得到一个行重为3、列重为2的矩阵。不失一般性,令第一行子方阵均为单位阵,其余两个方阵的行右循环移位参数分别为a1,1和a1,2,则不论a1,1和a1,2如何取值,该矩阵始终存在如图6所示的12环。
　　图5 长为1 008的(3,6)正则LDPC码的性能图
　　图6 12环在矩阵上的环路示意图
　　将图6环上各个的非零元素依次编号,并令编号为1的元素坐标为(0,0,x,x),则环上各节点的坐标如图7所示。
　　图7 12环上非零元素的坐标
　　因此,若采用上面的方法构造(λ,ρ)正则LDPC码,只要λ≥2,ρ≥2且λ+ρ≥5,相应的校验矩阵中也就必然包含图所示的字矩阵或其转置矩阵,于是得到的LDPC码的围长也就必然不可能超过12。
　　
　　4 结 语
　　
　　给出了一种高围长的正则LDPC码的构造方法,具体分析了去环方法和循环移位参数的选取。用这种方法构造的LDPC 码的H矩阵具有很好的结构。仿真表明,用该方法构造的码在AWGN信道下性能要优于随机构造的码。
　　
　　参考文献
　　[1]Gallager R G.Low-density Parity Check Codes[J].IRETrans.on Infor.Theory,1962,8:21-28.
　　[2]Tanner R M.A Recursive Approach to Low-complexity Codes[J].IEEE Trans.on Infor.Theory,1981,IT-27:533-547.
　　[3]Mackay D J C,Neal R M.Good Codes Based on Very Sparse Matrices[A].Cryptography and Coding,5th IMA Conference in Lecture Notes in Computer Science[C].1995,1025:100-111.
　　[4]袁东风,张海刚.LDPC码理论与应用[M].北京:人民教育出版社,2008.
　　[5]赵旦峰,陈艳,高敬鹏,等.基于单位阵的循环移位构造LDPC码的研究[J].应用技术,2007,34(5):8-10.
　　[6]刘建权.基于循环转置单位矩阵条件填充的LDPC 码构造方法[J].电子与信息学报,2007,29(12):107.
　　[7]Tanner R M.A Class of Group-Structured LDPC Codes[A].ICSTA 2001 Proceedings[C].Ambleside,2001.
　　[8]Xiao Yuhu.Progressive Edge-Growth Tanner Graphs[J].IEEE Trans.on Inform.Theory,2001:995-1001.
　　[9]雷菁,王建辉,唐朝京.基于PEG 算法的准循环扩展LDPC 码构造[J].通信学报,2008,29(9):104-107.
　　[10]乔华,管武.一种基于循环移位矩阵的LDPC码构造方法[J].电子与信息学报,2008,30(10):2 385-2 386.