换算法
第12卷第5期
2011年l0月
郭金服信息工程大学JournalofInformationEngineeringUniversity
V o1.12NO.5
Oct.2011
解决LDPC码准线性编码
复杂度的贪婪置换算法
斋待
(爱尔兰梅努斯国立大学汉密尔顿研究所，爱尔兰梅努斯)
摘要:LDPC码被认为是目前比较好的一种信道编码，但编码的高复杂度一直困扰LDPC码的
应用.针对这一问题，提出一种新的编码方法——贪婪置换算法.该方法是基于近似下三角 阵(AL T)准线性编码的思想，将一个稀疏校验矩阵高效地转化为一个近似下三角阵.文章具 体给出了这种方法和运算步骤，实现了AL T的准线性编码，使得对于任何一种LDPC码，可以
实现0(n+g)以内的编码低复杂度.文章对若干正则和非正则LDPC 码进行了编码方案的
开关电源模块并联供电系统模拟，得出复杂度，并和目前国际上最先进的编码方法加以比较，体现出了本方法在复杂度上
的优越性.
关键词：信道编码;LDPC码；准线性编码；近似下三角阵；贪婪置换算法
中图分类号:TN911.22文献标识码:A文章编号:1671—0673(2011)05—0578—06 GreedyPermutationAlgorithmforAlmost LinearEncodingofLDPCCodes
QIHang—hang
(HamiltonInstitute,NationalUniversityofIrelandMaynooth,Kildare,Irela nd.)
后启示录电影
Abstract:LDPCcodingisconsideredasoneofthemostpromisingchannelcod ing;howeverthe complexityofthisencodinginhibitsitsfurtherdevelopmentandapplication. Thispaperdealswith
thisproblem,proposingnewencodingmethod:thegreedypermutationalgori thm.Followingtheidea
ofapproximatelowermatrix(AL T)encoding,thegreedypermutationalgorit hmcanefficientlytrans-
formasparseLDPCparitycheckmatrixintoanAL T.Thispaperstudiesthisme thodindepthand
discussesitsstep—by-stepprocess,withAL Tencodingcomplexityexamine d.ForanyLDPCcodes, thismethodcankeepencodingcomplexitywithinO(n+g).Theencodingmeth odissimulatedon severalclassesofregularandirregularLDPCcodes.Theencodingcomplexit yiscomparedwithother
popularmethods’complexity,whichreflectsthesuperiorityofthismethod. Keywords:channelencoding;LDPCcodes;almostlinearencoding;approxi matelowermatrix
(AL T);greedypermutationalgorithm
LDPC码.是目前研究较多的一类信道编码，在相同信噪比情况下，具有解码后误码率较低的高性
能，受到人们的普遍关注.LDPC码可认为是最接近香农限的一类纠错码,LDPC码系统的BP迭代解码
结构相对完善，技术比较成熟，但是LDPC码的编码高复杂度是限制其广泛应用的一个因素.因为LD.
Pc码的编码比较困难，其编码技术一直不完善，编码较难形成结构化，编码的复杂度难以降低，这些一直
是LDPC码的技术难题.
收稿日期:2011-03?27；修回t3期:2011_04-2l
ilife 11作者简介：齐行行(1982一)，博士生，主要研究方向为信息论和信道编码,E-mail:****************.
第5期齐行行：解决LDPC码准线性编码复杂度的贪婪置换算法579 LDPC码校验矩阵的稀疏性保证了基于图模型解码器的低复杂性.但是低复杂性的编码器却并不
容易解决，因为LDPC码是由校验矩阵定义的，生成矩阵却不确定.分组码常规的方式是通过初等变换得
到标准型校验矩阵，从标准型校验矩阵得到标准型的系统码生成矩阵，从而进行系统编码(systematicen.
coding).但这种方法用于LDPC码却并没有利用到LDPC码校验矩阵的稀疏特性.实际编码(矩阵乘
法)的复杂度是O(n)(矩阵变换预处理复杂度为O(n))，其中n是码长，对于较大码长n,O(n)的复杂
度相当高.
近几年，研究人员提出了一些基于校验矩阵稀疏性的解决高复杂度LDPC码编码问题的新想法”.
基于图模型的消息传递编码器是一种利用解码器结构进行编码的技术，它的基本想法是把要进行编码的
冗余位看作是码字经过删除信道后的删除位.因此编码的过程和BEC信道下解码的过程一样.这种思
路可以适用于所有种类的LDPC码，但是这种直接将所有冗余位都视为删除位的编码方式,stoppingsets
的存在H绝大多数都不可行.
另外一种方法，被称为基于近似下三角(AL T)矩阵法的编码方法.这种方法的基本思想是先把原
始已有的校验矩阵只通过行置换和列置换变换为一个近似下三角(AL T)矩阵，这种只有行列置换的AL T
变换不改变矩阵的稀疏性.得到新的AL T稀疏检验矩阵后，可以利用这个矩阵，用逆推的方法由信息位
依次得到每一个冗余位.这样的编码复杂度可以达到O(+g)，其中,n 为码长,g是一个相对于/7,
的小量，称之为”线性编码缺陷”(gap).”线性编码缺陷”实质上就是近似下三角阵中不能转化为下三角
阵所剩下部分的行数.汤静
虽然基于AL T变换的编码方法思想原则上可以实现准线性编码，但实际上是否可以实现，如何从方
法上实现，仍然需要有一整套技术和算法.如何实际验证这种思想方法的可行性和达到的效果，这是本文
所要陈述的主旨和主要贡献.贪婪置换算法可以将任何一个稀疏校验矩阵变换为接近下三角阵的编码系
统方案，即”贪婪置换算法”的编码方案.将此编码系统方案应用于正则和非正则LDPC码，得到复杂度的
结果.将其复杂性与当前最新的编码方案的复杂性加以比较，该方案可与当前最新编码方案相当，甚至对
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议