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