A Combining Method of Quasi-Cyclic LDPC

LDPC码

IEEECOMMUNICATIONSLETTERS,VOL.9,NO.9,SEPTEMBER2005823

ACombiningMethodofQuasi-CyclicLDPCCodesbytheChineseRemainderTheorem

SehoMyungandKyeongcheolYang,Member,IEEE

Abstract—Inthispaperweproposeamethodofconstructingquasi-cycliclow-densityparity-check(QC-LDPC)codesoflargelengthbycombiningQC-LDPCcodesofsmalllengthastheircomponentcodes,viatheChineseRemainderTheorem.ThegirthoftheQC-LDPCcodesobtainedbytheproposedmethodisalwayslargerthanorequaltothatofeachcomponentcode.Byapplyingthemethodtoarraycodes,wepresentafamilyofhigh-rateregularQC-LDPCcodeswithno4-cycles.SimulationresultsshowthattheyhavealmostthesameperformanceasrandomregularLDPCcodes.

IndexTerms—ChineseRemainderTheorem,circulantpermu-tationmatrix,low-densityparity-check(LDPC)codes,quasi-cyclic.

Theoutlineofthepaperisasfollows.InSectionII,wereviewQC-LDPCcodesandde nenotationforourpresenta-tion.WeproposeamethodtoextendQC-LDPCcodesbasedontheCRTinSectionIIIandpresentafamilyofQC-LDPCcodeswithno4-cyclesbyapplyingtheproposedmethodtoarraycodesinSectionIV.Finally,wegiveconcludingremarksinSectionV.

II.QUASI-CYCLICLDPCCODES

AQC-LDPCcodeischaracterizedbytheparity-checkmatrixwhichconsistsofsmallsquareblockswhicharethezeromatrixorcirculantpermutationmatrices.LetCbetheQC-LDPCcodesoflengthnL,whoseparity-checkmatrixisgivenby

a P11Pa12···Pa1(n 1)Pa1n

Pa21Pa22···Pa2(n 1)Pa2n

(1)H= ........ ..···..

Pam1

Pam2

···

Pam(n 1)

Pamn

whereP=(Pij)istheL×Lpermutationmatrixde nedby

1ifi+1≡jmodL

(2)Pij=

0otherwiseandaij∈{0,1,...,L 1,∞}.Forsimplenotation,wedenotethezeromatrixbyP∞.

Forourconvenienceweintroducesomede nitions.

1)MotherMatrix:Them×nbinarymatrixM(H)canbeuniquelyobtainedbyreplacingzeromatricesandcir-culantpermutationmatricesby‘0’and‘1’,respectively,fromtheparity-checkmatrixHofaQC-LDPCcodein(1).ThenM(H)iscalledthemothermatrixofH.

2)ExponentMatrix:TheexponentmatrixE(H)ofHin(1)isde nedby

a11a12···a1(n 1)a1n

.......E(H)= ...···.. .(3)

am1

am2

···

am(n 1)

amn

NotethatithasthesamesizeasthemothermatrixofH.

3)ExponentCoupling:Aparity-checkmatrixHcanbeobtainedbycombininganexponentmatrixEandthecirculantpermutationmatrixP.Asanexample,Hin(1)willbeexpressedasH=E PwhereEisgivenbyE(H)in(3).Thisprocedureiscalledanexponentcoupling.

4)Block-Cycle:Ifthereisacyclegeneratedby1’sinM(H),itiscalledablock-cycle.

I.INTRODUCTION

L

OW-DENSITYparity-check(LDPC)codes rstdiscov-eredbyGallager[3]havearemarkableperformancewithiterativedecodingthatisveryclosetotheShannonlimitoveradditivewhiteGaussiannoise(AWGN)channels[5],[6].MostmethodsfordesigninggoodLDPCcodesarebasedonrandomconstruction,butalgebraicallystructuredLDPCcodesmaybeneededforimplementationpurposes.InthecaseofrandomLDPCcodesoflargecodelength,asigni cantamountofmemoryisneededtostoretheirparity-checkmatrices.Also,itishardtoaccessthememoryandencodedataef ciently.Quasi-cyclicLDPC(QC-LDPC)codesmaybeagoodcandidatetosolvethememoryproblemduetotheiralgebraicstructures.TherequiredmemoryforstoringQC-LDPCcodescanbereducedbyafactor1/L,whenL×Lcirculantper-mutationmatricesorthezeromatrixareemployed.Recently,severalcodingtheoristsproposedsomeclassesofQC-LDPCcodesbasedoncirculantpermutationmatricesandanalyzedtheirproperties[1],[2],[4],[8].ThesecodesperformquitewellcomparedtorandomLDPCcodes.

ThemaincontributionofthepaperistoproposeamethodforconstructingQC-LDPCcodesoflargelengthfromQC-LDPCcodesofsmalllengthusingtheChineseRemainderTheorem(CRT).Byapplyingthemethodtoarraycodes,wepresentafamilyofhigh-rateregularQC-LDPCcodeswithno4-cycles.

ManuscriptreceivedMarch2,2005.TheassociateeditorcoordinatingthereviewofthisletterandapprovingitforpublicationwasProf.MarcFossorier.ThisworkwassupportedinpartbytheCenterforBroadbandOFDMMobileAccess(BrOMA)atPOSTECH,supportedbytheITRCprogramoftheKoreanMinistryofInformationandCommunication(MIC)underthesupervisionoftheInstituteofInformationTechnologyAssessment(IITA).

TheauthorsarewiththeDepartmentofElectronicsandElectricalEngi-neering,PohangUniversityofScienceandTechnology(POSTECH),Pohang,Korea(e-mail:kcyang@postech.ac.kr).

DigitalObjectIdenti er10.1109/LCOMM.2005.09030.

c2005IEEE1089-7798/05$20.00