Tree-based Construction of LDPC codes

Tree-BasedConstructionofLDPCCodesDeepakSridhara,ChristineKelley,andJoachimRosenthal1InstitutfurMathematik,UniversitatZurich,CH-8057Zurich,Switzerland.email:cak,rosen,sridharamath.unizh.chAbstractWepresentaconstructionofLDPCcodesthathaveminimumpseudocodewordweightequaltotheminimumdis-tance,andperformwellwithiterativedecoding.Theconstructioninvolvesenumeratingad-regulartreeforafixednumberoflayersandemployingaconnectionalgorithmbasedonmutuallyorthogonalLatinsquarestoclosethetree.Methodsarepresentedfordegreesd=psandd=ps+1,forpaprime,oneofwhichincludesthewell-knownfinite-geometry-basedLDPCcodes.I.INTRODUCTIONLowDensityParityCheck(LDPC)codesarewidelyac-knowledgedtobegoodcodesduetotheirnearShannon-limitperformancewhendecodediteratively.However,manystructure-basedconstructionsofLDPCcodesfailtoachievethislevelofperformance,andareoftenoutperformedbyran-domconstructions.(Exceptionsincludethefinite-geometry-basedLDPCcodes(FG-LDPC)of1,whichwerelatergeneralizedin2.)Moreover,therearediscrepanciesbetweeniterativeandmaximumlikelihood(ML)decodingperformanceofshorttomoderateblocklengthLDPCcodes.Thisbehaviorhasrecentlybeenattributedtothepresenceofso-calledpseudocodewordsoftheLDPCconstraintgraphs,whicharevalidsolutionsoftheiterativedecoderwhichmayormaynotbeoptimal3.AnalogoustotheroleofminimumHammingdistance,dmin,inML-decoding,theminimalpseudocodewordweight,wmin,hasbeenshowntobealeadingpredictorofperformanceiniterativedecoding.Furthermore,theerrorfloorperformanceofiterativedecodingisdominatedbyminimalweightpseudocodewords.Althoughthereexistpseudocode-wordswithweightlargerthandminthathaveadverseaffectsondecoding,pseudocodewordswithweightwmindminareespeciallyproblematic4.TheTypeI-AconstructionandcertaincasesoftheTypeIIconstructionpresentedinthispaperaredesignedsothattheresultingcodeshaveminimalpseudocodewordweightequaltotheminimumdistanceofthecode,andconsequently,theseproblematiclow-weightpseudocodewordsareavoided.Theresultingcodeshaveminimumdistancewhichmeetsthelowertreeboundoriginallypresentedin5,andsincewminsharesthesamelowerbound4,6,andisupperboundedbydmin,theproposedconstructionshavewmin=dmin.ItisworthnotingthatthispropertyisalsoacharacteristicofsomeoftheFG-LDPCcodes2,andindeed,theprojective-geometry-basedcodesof1ariseasspecialcasesofourTypeII1ThisworkwassupportedbyNSFGrantNo.CCR-ITR-02-05310.construction.Furthermore,theTypeI-BconstructionpresentedhereinisamodificationoftheTypeI-Aconstruction,andityieldsafamilyofcodeswithawiderangeofratesandblocklengthsthatarecomparabletothoseobtainedfromfinitegeometries.Wenowpresentthetreeboundonwminderivedin6.Theorem1.1:LetGbeabipartiteLDPCconstraintgraphwithsmallestleft(variablenode)degreedandgirthg.Thentheminimalpseudocodewordweightwmin(fortheAWGN/BSCchannels)islowerboundedbywminbraceleftbigg1+d+d(d1)+d(d1)2+.+d(d1)g64,g2odd1+d+d(d1)+.+d(d1)g84+(d1)g44,g2evenThisboundisalsothetreeboundontheminimumdistanceestablishedbyTannerin5.Andsincethesetofpseudocode-wordsincludesallcodewords,wehavewmindmin.InthefollowingsectionswepresenttwoconstructiontechniquesofLDPCcodeswhereinforcertaincases,wmin=dmin.II.PRELIMINARIESTheconnectionalgorithmsforthetreeconstructionsTypeI-BandTypeIIarebasedonmutuallyorthogonalLatinsquares.Awell-knownconstructionofafamilyofmutuallyorthogonalLatinsquaresoforderps,apowerofaprime,maybefoundin7.LetM(1),M(2),.,M(ps1)denoteps1mutuallyorthogonalLatinsquares(MOLS)oforderps.Lettherows(andcolumns)ofeachsquarebeindexedbytheintegers0,1,2,.,ps1.Withoutlossofgenerality,assumethatthefirstcolumnofeachoftheLatinsquaresis0,1,2,.,ps1T.Inaddition,defineanewsquareofsizepsps,denotedM(0),whereeachcolumnofM(0)is0,1,2,.,ps1T.III.TREE-BASEDCONSTRUCTION:TYPEIIntheTypeIconstruction,firstad-regulartreeofalternatingvariableandconstraintnodelayersisenumeratedfromarootvariablenode(layerL0)forlayers.Ifisodd(respectively,even),thefinallayerL1iscomposedofvariablenodes(respectively,constraintnodes).CallthistreeT.ThetreeTisthenreflectedacrossanimaginaryhorizontalaxistoyieldanothertree,T,andthevariableandconstraintnodesarereversed.Thatis,iflayerLiinTiscomposedofvariablenodes,thenthereflectionofLi,callitLi,iscomposedofconstraintnodesinthereflectedtree,T.Theunionofthesetwotrees,alongwithedgesconnectingthenodesinlayersL1andL1accordingtoaconnectionalgorithmthatisdescribednext,comprisethegraphrepresentingaTypeILDPCcode.WenowpresenttwoconnectionschemesthatcanbeusedinthisTypeImodel,anddiscusstheresultingcodes.A.TypeI-AFord=3,theTypeI-Aconstructionyieldsad-regularLDPCconstraintgraphhaving1+d+d(d1)+.+d(d1)g42variableandconstraintnodes,andgirthg.ThetreeThasg2layers.ToconnectthenodesinLg21toLg21,firstlabelthevariable(resp.,constraint)nodesinLg21(resp.,Lg21)wheng2isodd,asv0,v1,.,v2g221,v2g22,.,v22g221,v22g22,.,v32g221(resp.,c0,c1,.,c32g221).Thenodesv0,v1,.,v2g221formthe0thclass,thenodesv2g22,.,v22g221formthe1stclass,andthenodesv22g22,.,v32g221formthe2ndclass;classifytheconstraintnodesinasimilarmanner.Inaddition,definethreepermutations(),(),()oftheset0,1,.,2g221asfollows.ThenodesinLg21andLg21areconnectedasfollows:1)Fori=0,1,andj=0,1,.,2g221,thevariablenodevj+i2g22isconnectedtonodesc(j)+i2g22andc(j)+(i+1)2g22.2)Fori=2,andj=0,1,.,2g221,thevariablenodevj+i2g22isconnectedtonodesc(j)+22g22andc(j).Thepermutationsforthecasesg=6,8,10,12aregivenbelow.Theaboveconstructioncanbeextendedforhigherginanaturalwayandweareworkingonanexplicitclosedformexpressionforthepermutations,forhigherg.g=6,=(0)(1),theidentitypermutation.g=8,=(0)(2)(1,3),=(0)(2)(1,3),=(0,2)(1)(3).g=10,=(0)(2)(4)(6)(1,5)(3,7),=(0)(2)(4)(6)(1,7)(3,5),=(0,4)(2,6)(1,3)(5,7).g=12,=(0)(4)(8)(12)(2,6)(10,14)(1,9)(3,15)(5,13)(7,11),=(0)(4,12)(8)(2,6,10,14)(1,15,13,11)(3,9,7,5),=(0,8)(4,12)(2,14)(6,10)(1,3,5,7)(9,11,13,15).Wheng2isodd,theminimumdistanceoftheresultingcodemeetsthetreebound,andhence,dmin=wmin.Wheng2iseven,dminisstrictlylargerthanthetreebound;webelievehowever,thatwminisequaltodmininthiscaseaswell.Figure1illustratesthegeneralconstructionprocedureandFigure2showsagirth10TypeI-ALDPCconstraintgraph.B.TypeI-BFord=ps,paprime,theTypeI-Bconstructionyieldsad-regularLDPCconstraintgraphhaving1+d+d(d1)variableandconstraintnodes,andgirth6.ThetreeThas3layersL0,L1,andL2.L2(resp.,L2)iscomposedofpssetsSips1i=0ofps1variable(resp.,constraint)nodesineachset;thesetSicorrespondstothechildrenofbranchioftherootnode.LetSi(resp.,Si)containthevariable(resp.,constraint)nodesvi,1,vi,2,.,vi,ps1Ll1Ll1L0L1L2L2L1L0v0v1v2v3v4v5c0c1c2c3c4c52l1c2l1c+12l2v2l2v+12l1v2l1v+12l2c+12l2cFig.1.TreeconstructionofTypeI-ALDPCcode.c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15c16c17c18c19c20c21c22c23c0v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v18v19v20v21v22v23v0Fig.2.TypeI-ALDPCconstraintgraphhavingdegreed=3andgirthg=10.(resp.,ci,1,ci,2,.,ci,ps1).TouseMOLSoforderpsintheconnectionalgorithm,animaginarynode,vi,0(resp.,ci,0)istemporarilyintroducedintoeachsetSi(resp,Si).Theconnectionalgorithmproceedsasfollows:1)Letxt(i,j)denotethe(j,t)thentryofthesquareM(i)definedinSectionII.Fori=0,.,ps1andj=0,.,ps1,connectvariablenodevi,jtoconstraintnodesc0,x0(i,j),c1,x1(i,j),.,cps1,xps1(i,j).2)Deleteallimaginarynodesvi,0,ci,0ps1i=0andtheedgesincidentonthem.3)Fori=1,.,ps1,deletetheedgeconnectingv0,itoc0,i.Theresultingd-regularconstraintgraphrepresentstheTypeI-BLDPCcode.Figure3illustratestheconstructionprocedureandFigure4providesaspecificexampleofaTypeI-BLDPCconstraintgraphwithd=4;thesquaresusedforconstructingthisgrapharebracketleftbigg0000111122223333bracketrightbigg,bracketleftbigg0123103223013210bracketrightbigg,bracketleftbigg0231132020133102bracketrightbigg,bracketleftbigg0312120321303021bracketrightbigg.TheTypeI-BalgorithmyieldsLDPCcodeshavingawiderangeofratesandblocklengthsthatarecomparableto,butdifferentfrom,thetwo-dimensionalLDPCcodesfromfiniteEuclideangeometries1,2.TheTypeI-BLDPCcodesareps-regularwithgirthsix,blocklengthN=p2s+1,anddistancedminps+1.Fordegreesoftheformd=2s,theresultingTypeI-Bcodeshaveverygoodrates,above0.5,andperformwellwithiterativedecoding.IV.TREE-BASEDCONSTRUCTION:TYPEIIIntheTypeIIconstruction,firstad-regulartreeTofalternatingvariableandconstraintnodelayersisenumeratedv1,1v1,0v1,2vp1,0ssvp1,1svp1,p1sc1,1c1,0c1,2c1,p1cp1,0scp1,1scp1,p1ssv0,p1sv0,2v0,1c0,1c0,0c0,2c0,p1ssv1,p1sv0,0Fig.3.TreeconstructionofTypeI-BLDPCcode.(Shadednodesareimaginarynodesanddottedlinesareimaginarylines.)c1,1c1,2c1,3c2,1c2,2c2,3c3,1c3,2c3,3c0,1c0,2c0,3c0,0c1,0c2,0c3,0v0,1v0,2v0,3v0,0v1,1v1,2v1,3v1,0v2,1v2,2v2,3v2,0v3,1v3,2v3,3v3,0Fig.4.TypeI-BLDPCconstraintgraphhavingdegreed=4andgirthg=6.fromarootvariablenode(layerL0)forlayers,asinTypeI.ThetreeTisnotreflected;rather,asinglelayerof(d1)1nodesisaddedtoformlayerL.Ifisodd(resp.,even),thislayeriscomposedofconstraint(resp.,variable)nodes.TheunionofTandL,alongwithedgesconnectingthenodesinlayersL1andLaccordingtoaconnectionalgorithmthatisdescribednext,comprisethegraphrepresentingaTypeIILDPCcode.WenowpresenttheconnectionschemethatisusedforthisTypeIImodel,anddiscusstheresultingcodes.Theconnectionalgorithmfor=3and=4proceedsasfollows.A.=3ThedconstraintnodesinL1arelabeledB0,B1,.,Bpstorepresentthedbranchesstemmingfromtherootnode,andthed(d1)variablenodesinthethirdlayerL2arelabeledasB0,0,B0,1,.,B0,ps1,B1,0,.,B1,ps1,.,Bps,0,.,Bps,ps1.Thep2sconstraintnodesinthefinallayerL=L3arelabeledA0,0,A0,1,.,A0,ps1,A1,0,A1,1,.,A1,ps1,.,Aps1,0,Aps1,1,.,Aps1,ps1.1)TheconstraintnodesinL3aregroupedintod1=psclassesofd1=psnodesineachclass.Similarly,thevariablenodesinL2aregroupedintod=ps+1classesofd1=psnodesineachclass.ThosenodesdescendingfromB0formthe0thclass,thosedescendingfromB1formthefirstclass,andsoon.2)EachofthevariablenodesdescendingfromB0isconnectedtoalltheconstraintnodesofoneclass.Thatis,B0,0isconnectedtoA0,0,A0,1,.,A0,ps1,B0,1isconnectedtoA1,0,A1,1,.,A1,ps1,andingeneral,B0,kisconnectedtoAk,0,Ak,1,.,Ak,ps1whichcorrespondtotheconstraintnodesinthekthclass.3)Letxt(i,j)denotethe(j,t)thentryofM(i1).4)ThenconnectthevariablenodeBi,jtotheconstraintnodesA0,x0(i,j),A1,x1(i,j),A2,x2(i,j),.,Aps1,xps1(i,j).Figure5illustratestheconstructionprocedureandFigure6providesanexampleofaTypeIILDPCconstraintgraphwithdegreed=4andgirthg=6;thesquaresusedforconstructingthisexampleareM(0)=bracketleftBig000111222bracketrightBig,M(1)=bracketleftBig012120201bracketrightBig,M(2)=bracketleftBig021102210bracketrightBig.Theratioofminimumdistancetoblocklengthofthecodesisatleast2+ps1+ps+p2s,andthegirthissix.Fordegreesdoftheformd=2s+1,thetreeboundonminimumdistanceandminimumpseudocodewordweight5,6ismet,i.e.,dmin=wmin=2+2s,fortheTypeII,=3,LDPCcodes.B.RelationtofinitegeometrycodesThecodesthatresultfromthis=3constructioncorrespondtothetwo-dimensionalprojective-geometry-basedLDPC(PGLDPC)codesof2.WithalittlemodificationoftheTypeIIconstruction,wecanalsoobtainthetwo-dimensionalEuclidean-geometry-basedLDPCcodesof2.Sinceatwo-dimensionalEuclideangeometrymaybeob-tainedbydeletingcertainpointsandline(s)ofatwo-dimensionalprojectivegeometry,thegraphofatwo-dimensionalEG-LDPCcode2maybeobtainedbyperform-ingthefollowingoperationsontheTypeII,=3,graph:1)InthetreeT,therootnodealongwithitsneighbors,i.e.,theconstraintnodesinlayerL1,aredeleted.2)Consequently,theedgesfromtheconstraintnodesB0,.,BpstolayerL2arealsodeleted.3)Atthisstage,theremainingvariablenodeshavedegreeps,andtheremainingconstraintnodeshavedegreeps+1.Now,aconstraintnodefromlayerL3ischosen,say,constraintnodeA0,0.Thisnodeanditsneighboringvariablenodesandtheedgesincidentonthemaredeleted.DoingsoremovesexactlyonevariablenodefromeachclassofL2,andthedegreesoftheremainingconstraintnodesinL3arelessenedbyone.Thus,theresultinggraphisnowps-regularwithagirthofsix,hasp2s1constraintandvariablenodes,andcorrespondstothetwo-dimensionalEuclidean-geometry-basedLDPCcodeEG(2,ps)of2.C.=41)ThetreeTisnowenumeratedforfourlayers,withthenodesinL0,L1,andL2labeledasinthe=3case.Fori=0,.,ps,theconstraintnodesintheithclassofL3arelabeledBi,0,0,Bi,0,1,.,Bi,0,ps1,Bi,1,0,Bi,1,1,.,Bi,1,ps1,.,Bi,ps1,0,.,Bi,ps1,ps1.B0B1BpB0,0B0,p1B1,0B1,p1Bp,0Bp,p1A0,p1A0,0A1,p1Ap1,0A1,0Ap1,p1B0,1BsssssssssssFig.5.Treeconstructionofgirth6TypeII(=3)LDPCcode.B0B0,0B1,0B1,1B1,2B2,0B2,1B2,2B3,0B3,1B3,2B3B2B1B0,1B0,2A2,0A2,1A2,2A0,2A0,0A0,1A1,0A1,1A1,2BFig.6.TypeIILDPCconstraintgraphhavingdegreed=4andgirthg=6.(Shadednodeshighlightaminimumweightcodeword.)2)Thep3svariablenodesinthefinallayerL4arelabeledA0,0,0,A0,0,1,.,A0,0,ps1,A0,1,0,A0,1,1,.,A0,1,ps1,.Aps1,0,0,Aps1,0,1,.,Aps1,0,ps1,.,Aps1,ps1,0,Aps1,ps1,1,.,Aps1,ps1,ps1.3)For0ips1,0jps1,connectthevariablenodeB0,i,j,thatisinthe0thclassofL3,totheconstraintnodesAi,j,0,Ai,j,1,.,Ai,j,ps1.4)Letxt(i,k)=M(i1)(k,t),the(k,t)thentryofM(i1),andletyt(i,j)=M(i)(j,t),the(j,t)thentryofM(i),wherei=imodps.5)Then,for1ips,0j,kps1,connectthevariablenodeBi,j,ktotheconstraintnodesA0,x0(i,k),y0(j,k),A1,x1(i,k),y1(j,k),.,Aps1,xps1(i,k),yps1(j,k).TheTypeII,=4,LDPCcodeshavegirtheight,minimumdistancedmin2(ps+1),andblocklengthN=1+ps+p2s+p3s.(WebelievethatthetreeboundontheminimumdistanceisactuallymetforalltheTypeII,=4,codes,i.e.dmin=wmin=2(ps+1).)Figure7illustratesthegeneralconstructionprocedure.Ford=3,theTypeII,=4,LDPCconstraintgraphasshowninFigure8correspondstothe(2,2)-Finite-Generalized-Quadrangles-basedLDPC(FGQLDPC)codeof8;thesquaresusedforconstructingthiscodeareM(0)=bracketleftbig0011bracketrightbig,M(1)=bracketleftbig0110bracketrightbig.WebelievethattheTypeII,=4,constructionresultsinotherFGQLDPCcodesforotherchoicesofd.TheTypeIIconstructionalgorithmcanbemodifiedforlargerbyinvolvingmoreiterationsoftheMOLSintheconnectionscheme,aswillbediscussedinaforthcomingpaper.B0B1BpB0,0B0,p1B1,0B1,p1Bp,0Bp,p1A0,0,0A0,0,p1B1,p1,p1B1,p1,0B1,0,p1B1,0,0B0,p1,p1B0,p1,0B0,0,0Bp,0,p1Bp,0,0Bp,p1,p1Bp,p1,0B0,0,p1A0,p1,0A0,p1,p1Ap1,p1,0Ap1,0,0Ap1,0,p1Ap1,p1,p1BsssssssssssssssssssssssssssssssFig.7.Treeconstructionofgirth8TypeII(=4)LDPCcode.B0B1B2B0,0B0,1B1,0B1,1B2,0B2,1B0,0,0B0,0,1B0,1,0B0,1,1B1,0,0B1,0,1B1,1,0B1,1,1B2,0,0B2,0,1B2,1,0B2,1,1A0,0,0A0,0,1A0,1,0A0,1,1A1,0,0A1,0,1A1,1,0A1,1,1BFig.8.TypeIILDPCconstraintgraphhavingdegreed=3andgirthg=8.(Shadednodeshighlightaminimumweightcodeword.)V.SIMULATIONRESULTSFigures9,10,11,12showthebit-error-rateperformanceofTypeI-A,TypeI-B,TypeIIgirthsix,andTypeIIgirtheightLDPCcodes,respectivelyoverabinaryinputadditivewhiteGaussiannoisechannelwithmin-sumiterativedecoding.Theperformanceofregularorsemi-regularrandomlyconstructedLDPCcodesofcomparableratesandblocklengthsarealsoshown.(AlloftherandomLDPCcodescomparedinthispaperhaveavariablenodedegreeofthreeandareconstructedfromtheonlineLDPCsoftwareavailableat/radford/ldpc.software.html.)Figure9showsthattheTypeI-ALDPCcodesperformsubstantiallybetterthantheirrandomcounterparts.Figure10revealsthattheTypeI-BLDPCcodesperformbetterthancomparablerandomLDPCcodesatshortblocklengths;butastheblocklengthsincrease,therandomLDPCcodestendtoperformbetterinthewaterfallregion.Eventuallyhowever,astheSNRincreases,theTypeI-BLDPCcodesoutperformtherandomonessince,unliketherandomcodes,theydonothaveaprominenterrorfloor.Figure11revealsthattheperformanceofTypeIIgirth-sixLDPCcodesisalsosignificantlybetterthancomparablerandomcodes;thesecodescorrespondtothetwodimensionalPGLDPCcodesof2.Figure12indicatestheperformanceofTypeIIgirth-eightLDPCcodes;thesecodesperformcomparablytorandomcodesatshortblocklengths,butatlargeblocklengths,therandomcodesperformbetterastheyhavelargerrelativeminimumdistancescomparedtotheTypeIIgirth-eightLDPCcodes.Asageneralobservation,min-sumiterativedecodingof123456789107106105104103102101100Eb/No(dB)BERPerformanceofTypeIversusRandomLDPCsTypeI,d=3,g=6,N=10,rate=0.400Random,N=10,rate=0.400TypeI,d=3,g=8,N=22,rate=0.182Random,N=22,rate=0.182TypeI,d=3,g=10,N=46,rate=0.217Random,N=46,rate=0.217TypeI,d=3,g=12,N=94,rate=0.148Random,N=94,rate=0.148TypeIRandomFig.9.PerformanceofTypeI-AversusRandomLDPCcodeswithmin-sumiterativedecoding.mostofthetree-basedLDPCcodes(particularly,TypeI-A,TypeII,andsomeTypeI-B)presentedheredidnottypicallyrevealdetectederrors,i.e.,errorscausedduetothedecoderfailingtoconvergetoanyvalidcodewordwithinthemaximumspecifiednumberofiterations.Detectederrorsarecausedprimarilyduetothepresenceofpseudocodewords,especiallythoseofminimalweight.WethinkthatthelackofdetectederrorswithiterativedecodingoftheseLDPCcodesisprimarilyduetotheirgoodminimumpseudocodewordweightwmin.VI.CONCLUSIONSTheTypeIconstructionyieldsafamilyofLDPCcodesthat,tothebestofourknowledge,donotcorrespondtoanyoftheLDPCcodesobtainedfromfinitegeometriesorothergeometricalobjects.Thetwotree-basedconstructionspresentedinthispaperyieldawiderangeofcodesthatperformwellwhendecodediteratively,largelyduetothemaximizedminimalpseudocodewordweight.However,theoverallminimumdistanceofthecodeisrelativelysmall.Constructingcodeswithlargerminimumdistance,whilestillmaintainingdmin=wmin,remainsanopenproblem.REFERENCES1Y.Kou,S.Lin,andM.Fossorier,“Low-densityparity-checkcodesbasedonfinitegeometries:Arediscoveryandnewresults”,IEEETrans.ofInformationTheory,vol.IT-47,no.7,pp.2711-2736,Nov.2001.2S.Lin,H.Tang,Y.Kou,J.Xu,andK.Abdel-Ghaffar,“CodesonFiniteGeometries”,Proceedingsofthe2001IEEEInfo.TheoryWorkshop,(Cairns),Sept.2-7,2001.3R.KoetterandP.O.Vontobel,“Graph-coversanditerativedecodingoffinitelengthcodes”,inProceedingsoftheIEEEInternationalSymposiumonTurboCodesandApplications,(Brest,France),Sept.2003.4C.KelleyandD.Sridhara,“PseudocodewordsofTannerGraphs”