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

LDPC码

8245)ExponentChain:Ablock-cycleoflength2linM(H)canberepresentedasanexponentchainasfollows:

Pa1→···→Pa2l→Pa1

or

(a1,···,a2l,a1).

HerebothPaiandPai+1arelocatedineitherthesame

columnablockorthesamerowblockofH,andbothandPi+2arelocatedinthedistinctcolumnandrowblocks.Sincethecyclesofshortlengthmaydegradetheperfor-manceofLDPCcodes,itiscriticaltounderstandtheirstruc-ture.Duetothespecialstructureoftheirparity-checkmatricesforQC-LDPCcodes,thecyclesmaybeeasilyanalyzedinanalgebraicway.Thefollowingpropositionwas rstpresentedbyFossorierin[2].

Proposition1([2]):LetPa1→Pa2→···→Pa2lPa→1betheexponentchaincorrespondingtoa2l-block-cycle.Ifristheleastpositiveintegersuchthat

2lr·

( 1)i 1ai≡0modL,

(4)

i=1

thentheblock-cycleleadstoacycleoflength2lr.

Itiseasilycheckedthatr|L,thatis,rdividesLduetoits

choiceinProposition1.

BININGOFQC-LDPCCODESBYTHECRTInthissectionweintroduceasimplemethodtoobtaintheexponentmatrixforaQC-LDPCcodeoflargelengthbycombiningtheexponentmatricesforgivenQC-LDPCcodesofsmallerlength.

Fork=1,2,...,s,letCkbeaQC-LDPCcodewhoseparity-checkmatrixHkisanmLandmotherk×nLmatriceskbinarymatrix.ThecorrespondingexponentaregivenbyE(HM(Hk)=(akij)andM(Hk)L,respectively.Assumethatallk)arethesameandgcd(wewishtoconstructE(Hl,L)andk)=1foralll,k(l=k).Now,M(H)foraQC-LDPCcodeCwhoseparity-checkmatrixHisanmL×nLmatrix.TheideacomesfromtheChineseRemainderTheorem(CRT)[7]inthefollowing.

CombiningbytheCRT

Step1)Ifak

ij=∞for1≤k≤s,then

a sij=

akijbkL

k

modL

k=1

where

L=L1L2···Ls,L L

k=

k

andbkL k≡1modLk.Otherwise,a StepE(H2))=The(aexponentmatrixE(H)forijH=∞is.

de nedby

Step3)Theijparity-check).

matrixHisobtainedbyexpo-nentcouplingofE(H)andP,i.e.,H=E(H) PwherePistheL×Lcirculantpermutationmatrixde nedin(2).

Forsimplicity,considertwoQC-LDPCcodesCL(H1andCsuchthatgcd(2

1,L2)=1,E1)=(aij),E(H2)=(bij)

IEEECOMMUNICATIONSLETTERS,VOL.9,NO.9,SEPTEMBER2005

andM(H1)=M(H2)in(1).BythecombiningbasedontheCRT,theexponentmatrixE(H)=(cij)isgivenby

cij≡aijA1L2+bijA2L1

modL1L2.

(5)

whereA1andAmodL2aretwointegerssuchthatAmodL1L2≡11andA2Lobtained1≡1byexponent2.Thentheparity-checkmatrixHcanbecouplingofE(H)andtheL1L2×L1L2circulantpermutationmatrixPin(2).SinceM(H1)=M(H2)=M(H),a2l-block-cycleinthemothermatrixcanberepresentedbythechains(a(cbb1,a2,...,a2l,a1),1,2,...,b2l,b1),and(c1,c2,...,c2Hl,c),1)respectively.whereaHi,bTheseiandchainsicomefromE(arecloselyrelated1),E(Hin2)andE(thefollowing.

Theorem2:Ifr1,r2,andraretheleastpositiveintegerssuchthat

r

2l1·( 1)i 1ai≡0modL1,(6)i=1

r 2l2·( 1)i 1bi

≡0modL2,(7)i=1r·

2l( 1)i 1ci

≡0modL1L2,

(8)

i=1

thentheblock-cycleleadstoacycleoflength2lr,andacycleoflength2lrinH1,acycle

oflength2lr21,HFurthermore,r=r2andH,respectively.Proof.ByProposition1,itiseasily1r2.

checkedthattheblock-cycleleadstoacycleoflength2lr1,acycleoflength2lrandacycleoflength2lrinH,respectively.2,Therefore,itsuf cestoshowthat1,Hr=2andHrcanbe1ramongtheexponentsin(5),(8)expressed2.Fromtherelationas

rA 2l1L2·( 1)i 1

arA

2li+2L1·( 1)i 1bi≡0

modL1L2.

i=1

i=1

Thisequationcanbedividedintotwoparts:

rA 2l1L2·( 1)i 1ai≡0modL1,i=1rA 2l2L1·

( 1)i 1bi≡0

modL2.

i=1

SinceArand1L2r≡1modL1andA2L1,r≡1modL2,wehave

r1|2|r.Notethatgcd(r12)=1sincer1|L1,r2|L2andgcd(L1,L2)=1.Thereforer1r2|r.Ontheotherhand,wehave

2l 2 r 1c

l1r2·( 1)ii=r2A1L2r1( 1)i 1ai

i=1

i=1

2l

+r1A2

L1r2

( 1)i 1bi

≡0modLi=1

1L2

whichimpliesr=r1r2.

Theorem2impliesthatifweapplytheexponentcouplingtoE(H)andtheLin(2),thenwecan1L2obtain×L1La2circulantpermutationmatrixPnewQC-LDPCcodeCwith

LDPC码

MYUNGandYANG:ACOMBININGMETHODOFQUASI-CYCLICLDPCCODESBYTHECHINESEREMAINDERTHEOREM

825

Fig.1.PerformanceofsomeregularQC-LDPCcodesconstructedwiththeexponentcombiningbytheCRT.

girthlargerthanorequaltothoseofC1andC2.Theorem2canbedirectlyextendedtothegeneralcasewithmorethantwoQC-LDPCcodes.

IV.AFAMILYOFQC-LDPCCODESWITHNO4-CYCLESThecombiningbytheCRTcanbeusedtoconstructalargeQC-LDPCcodewithno4-cyclesfromsmallQC-LDPCcodesascomponentcodes.Here,onlyarraycodeswillbeconsideredascomponentcodes,eventhoughotherQC-LDPCcodescanbenaturallyemployed.

TheexponentmatrixEofanarraycodeC(p,m)isde nedbyEij=(i 1)(j 1)for1≤i≤mand1≤j≤p[1].Herepisprimeandmisapositiveintegersuchthatm≤p.Theparity-checkmatrixH(p,m)ofC(p,m)canbeobtainedbyexponentcouplingofEandthep×pcirculantpermutationmatrixPin(2).Itiswell-knownthatthegirthofC(p,m)is6[1],[9].

Theorem3:LetC(p,m)bethearraycodewithparity-checkmatrixH(p,m)foraprimepandapositiveintegerm≤p.Fori=1,2,letpibeaprime(p1=p2)andE(Hi)bethem×p1p2exponentmatrixofHi,respectively,where

H1=[H

(p1,m)H(p1,m)···H(p1,m)]p ,

2times

H2=[H

(p2,m)H(p2,pm)···H(p2,m)].times

1LetEbethem×p1p2matrixoverZE(Hp1p2obtainedby

combiningE(Hmp1)and2)basedontheCRTandletbethe2

H

ofEandthe1p2×p2p1p2matrixobtainedbyexponentcoupling1p2×p1p2circulantpermutationmatrixin(2).ThentheQC-LDPCcodewithparity-checkmatrixHhasno4-cycles.

Proof.Letr1andr2betheleastpositiveintegerssatisfying(6)and(7)for4-block-cyclesinHp1andH2,respectively.Sincethe(i+j11)thandthe(i+j2p1)thcolumnblocksin

H1arethesameforjareno1=j4-cycles2,thereexist4-cyclesbetweenthem.But,therebetweenthe(i1+j1p1)thandthe(i2+jotherhand,2pthe1)thcolumnblocksinH(i+j1fori1=icolumn2.OntheblocksinH1p1)thandthe(i+j2p1)th(jj2aredistinctsince(i+j.Therefore,there1p1) (i+jareno4-cycles2p1)=between1 2)pthe1=0modp(i+j21p1)thandthe(i+jandH2p1)thcolumnblocksinH2.Thisimpliesthatr1r2>1hasno4-cyclesbyTheorem2. ThemethodgiveninTheorem3cannotbedirectlyusedtoconstructlow-rateQC-LDPCcodesoflargelength,sincethenumberofrowblocksareconstant.However,itmaybepossibletoconstructlow-rateQC-LDPCcodeswithoutshortcyclesinasimilarway.NotethatthecombiningmethodbasedontheCRTcanbeappliedtoconstructingQC-LDPCcodes,regardlessofwhethertheyareregularornot.

Figure1showsthebiterrorrate(BER)andframeerrorrate(FER)performanceoftheshortenedQC-LDPCcodescon-structedbythecombiningmethodviatheCRToveranAWGNchannel.Here,(N,K,j)(p1,p2)denotes(codelength,infor-mationlength,columnweight)(arraycodesC(p1,j),C(p2,j)).Theyhavelittleperformancedegradationduetotheirrestrictedstructure,ascomparedwithrandomlyconstructedregularLDPCcodeswiththesameparameters.Inthecasethatthecolumnweightislargerthan3,therearenoseriouserror oorsatFER=10 4.

V.CONCLUDINGREMARKS

WediscussedhowtocombineQC-LDPCcodesofsmalllength,basedontheCRT.WeshowedthatthemethodcanbeusedforconstructingQC-LDPCcodeswithno4-cycles.Byapplyingthemethodtoarraycodesascomponentcodes,wepresentedafamilyofQC-LDPCcodeswithno4-cycles.ThisapproachcanbedirectlyextendedtootherQC-LDPCcodes.

REFERENCES

[1]J.L.Fan,“Arraycodesaslow-densityparity-checkcodes,”inProc.2nd

Int.Symp.TurboCodes,Brest,France,Sept.4-7,2000,pp.543-546.[2]M.P.C.Fossorier,“Quasi-cycliclowdensityparitycheckcodesfrom

circulantpermutationmatrices,”rm.Theory,vol.50,pp.1788-1794,Aug.2004.

[3]R.G.Gallager,“Low-densityparity-checkcodes,”rm.

Theory,vol.IT-8,pp.21-28,Jan.1962.

[4]J.-L.Kim,U.N.Peled,I.Perepelitsa,V.Pless,andS.Friedland,“Explicit

constructionoffamiliesofLDPCcodeswithno4-cycles,”rm.Theory,vol.50,pp.2378-2388,Oct.2004.

[5]D.J.C.MacKayandR.M.Neal,“NearShannonlimitperformanceof

low-densityparity-checkcodes,”Electron.Lett.,vol.32,pp.1645-1646,Aug.1996.

[6]T.J.Richardson,A.Shokrollahi,andR.Urbanke,“Designofcapacity-approachinglow-densityparity-checkcodes,”rm.The-ory,vol.47,pp.619-637,Feb.2001.

[7]K.H.Rosen,ElementaryNumberTheoryandItsApplications.Reading,

MA:Addison-Wesley,pp.322-324,2000.

[8]R.M.Tanner,D.Sridhara,T.Fuja,andD.J.Costello,Jr.,“LDPC

blockandconvolutionalcodesbasedoncirculantmatrices,”rm.Theory,vol.50,pp.2966-2984,Dec.2004.

[9]K.YangandT.Helleseth,“Ontheminimumdistanceofarraycodesas

LDPCcodes,”rm.Theory,vol.49,pp.3268-3271,Dec.2003.

本文来源：https://www.bwwdw.com/article/zg61.html