LDPC码校验矩阵的一种构造方法的研究

LDPC码校验矩阵的一种构造方法的研究杨泽建（柳州铁道职业技术学院广西柳州545007）【摘要】采用“皇后算法”，构造出A矩阵，以及相应的B、c、D矩阵，再利用A、B、c、D进行排列与组合，构造出性能优越的校验矩阵。实践表明该矩阵在码率很高的时候也具有较好的性能。【关键词】LDPC校验矩阵编码、码率【收稿日期】2010-3-5【作者简介】杨泽建(1977-)，男，湖北孝感人，柳州铁道职业技术学院信息工程系教师，硕士研究生，主要从事计算机通信技术研究。【中图分类号】TN919【文章标识码】AResearchonaConstructionMethodofLDPCCodesCheckMatrixYangZe-jian(LiuzhouRailwayVocationalTechnicalCollege，LiuzhouGuangxi545007)Abstract:thispaperconstructsoutAmatrix,andcorrespondingmatrixofB、c、DbyQueen'salgorithm,andthenre-useA,B、c、Dtoconstructoutthesuperiorperformancecheckmatrixbyrankingthemwiththecombination.Practiceshowsthatthematrixhasagoodperformanceinthehighrate.Keywords:LDPC;checkmatrix;codes;coderate目前无线通信领域正在发展面向未来的通信技术，这些先进的技术将大大提高无线通信系统的频谱利用率和信息传输容量，增强系统的性能和功能。LDPC信道编码技术是近年来全球热点研究技术。LDPC码编码器是设计算法一直是是信道编码领域的研究热点，目前LDPC码的编码器设计问题成了阻碍LDPC码走向应用的瓶颈问题，这就要求我们在构造LDPC码的校验矩阵的时候考虑到是否易于工程实现[1]。用随机法构造的LDPC码的码字参数选择灵活，但是却没有一定的码的结构，编码复杂度太高，不易于工程上的实现，如用FPGA、DSP等。一定编码结构实现的LDPC码具有循环获者准循环结构，编码非常简单，显示了良好的性能，但是，码长、码率的参数选择受到很大的限制将码长为n、信息位为k的LDPC码校验矩阵H分为2个子矩阵ppddHcvHcH=[dH|pH]其中，dH是一个（n-k）k的矩阵，称为信息矩阵dH=11121,1,dddkddnknkkhhhhh（1）dH采用随机构造法，pH是一个（nk）（nk）的方阵，称为校验位矩阵，pH是双对角线形式的三角子矩阵，具有如下形式：pH=100000110000110000001000011（2）现在有一个88的pH为：1100000001100000001100110001100000001100000001100000001110000001相应地将H矩阵所对应的码矢量c分解为对应的校验位向量pc、信息位向量dc，即有：[|]dpccc,校验矩阵H与码向量c之间有如下关系：[|]0dTdpddpppcHcHHHcHcc（3）对于给定的任意一个信息位向量dc，可以利用构造出的校验矩阵pH、信息位矩阵dH以及映射矢量v产生码矢量c，v定义为方程（3）的解，因此有：ppddHcvHc(4)令1[]pH=pU，pU是三角矩阵，上式运算取模2和，则：ppcUv（5）先计算v，再利用式（5）转换v，计算出pc,从而得到码字向量c。值得注意的是，不一定采取对PH求逆的方法来求得pc，其具有线性计算复杂度。由于pH是双对角的上三角阵，对给定的信息位向量dc={jd，j=1，2,…..,k},根据式（1）和式（2）很容易求得校验位向量pc={ip，i=1，2，.……n-k}11,dkjjijphd（6）1,1kdiiijjjpphdi=0,1,….M-1(7)旋转码是在半随机基础构造的，校验矩阵信息位子矩阵dH由qt个旋转码按一定规则构成[2]，旋转码是mm的方阵，由此可以得到的dH矩阵是qmtm维，列重为t，行重为q，码长是()qtm，信息位长tm，码率为/()tqt。将旋转矩阵记为A，A的结构是每列只有一个1，每列只有一个1。将A顺时针或逆时针旋转90度得到B，以同样的方法再旋转2个90度，可以得到c和d。这就是旋转矩阵由此得名[3]。这四个矩阵均满足每列每行只有一个1的约束条件。如m=3的A矩阵，它所对应的B、c、D分别为：A=010001100B=100001010c=010100001D=001100010我们可以利用这四个矩阵的排列组合产生码率为1/2的dH矩阵dH=10110011011AAAADABCCDABBCDA将PH和dH合并，得到完整的校验矩阵H，形式如下：H=[|dpHH]=10110011011AAAADABCCDABBCDA（8）在这里提出一种构造比较好的A的构造方法，称为皇后算法，、用c程序实现了搜索该矩阵的功能。皇后问题：在nn的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。此算法的目的是消除了每个矩阵中的四环，求解皇后问题的递归模型如下：(1)palce(i,n):若i=n，则n个皇后放置完毕，输出解；(2)palce（k，n）：对于第k列的每个合适的位置i，在其上放置一个皇后；(3)place（k+1，n）其中，palce(k,n)表示在前面1，….k-1个皇后放置好后，用于放置k….,n的皇后，由此可得到的递归算法如下：place(intk,intn){if(k==n)输出一个解；elsefor(inti=1;i=n;i++)%在第k列上穷举每一个位置if（第k列的第i行合适）{在位置处放一个皇后;place(k+1,n);}}对每个n，可以产生不同的的矩阵。但是这种方法搜索的局限性是n取值不能超过20。采用旋转码，在码率很高的时候也具有较好的性能。LDPC码的构造方法很多，很多性能优越的码的构造正在研究中，是一个不断发展的研究课题。参考文献：[1]王新梅.纠错码原理[M].西安：电子科技大学出版社，2001[2]符初生，文红.LDPC码原理与应用[M].西安：电子科技大学出版社，2006[3]袁东风，张海霞.宽带移动通信中的先进信道编码技术[M].北京：北京邮电大学出版社，2004（责任编辑季同文）