下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 ldpc

ldpc.pdf

ldpc

proju
2014-04-07 0人阅读 举报 0 0 暂无简介

简介:本文档为《ldpcpdf》,可适用于IT/计算机领域

LowDensityParityCheckCodesJohnRBarryGeorgiaInstituteofTechnologybarryecegatecheduOctober,Wepresentatutorialoverviewoflowdensityparitycheck(LDPC)codesAsthenamesuggests,LDPCcodesareblockcodesdefinedbyaparitycheckmatrixthatissparseTheywerefirstproposedinbyGallager,alongwithanelegantiterativedecodingschemewhosecomplexitygrowsonlylinearlywithblocklengthDespitetheirpromise,LDPCcodeswerelargelyforgottenforseveraldecades,primarilybecausethecomputersatthetimewerenotpowerfulenoughtoexploitthemIntheywererediscoveredbyMacKayandNeal,sparkingaflurryoffurtherresearchTodaythevalueofLDPCcodesiswidelyrecognizedTheirremarkableperformanceensuresthattheywillnotbeforgottenagainIncontrasttomanycodesthatwereinventedwellafter,LDPCcodesofferbothbetterperformanceandlowerdecodingcomplexityInfact,itisanirregularLDPCcode(withblocklength)thatcurrentlyholdsthedistinctionofbeingtheworld’sbestperformingrate⁄code,outperformingallotherknowncodes,andfallingonlydBshortoftheShannonlimitParityCheckCodesAparitycheckcodeoflengthNisalinearbinaryblockcodewhosecodewordsallsatisfyasetofMlinearparitycheckconstraintsItistraditionallydefinedbyitsM×NparitycheckmatrixH,whoseMrowsspecifyeachoftheMconstraintsForexample,ifthefirstconstraintspecifiesthatbitsandmustbeequal,thenthefirstrowofHcontainsainpositionandandzeroselsewhereTheparitycheckcodeisthesetofbinaryvectorssatisfyingallconstraints,ie,thesetofcsatisfyingcHT=EachlinearlyindependentconstraintcutsthenumberofvalidcodewordsinhalfThus,ifr=rank(H)≤MisthenumberoflinearlyindependentrowsinH,thenthenumberofcodewordsisN–r,andthecodedimensionisK=N–rBecauseeachcodewordoflengthNconveysKinformationbits,thecoderateisK⁄NAlowdensityparitycheck(LDPC)codeisdefinedbyaparitycheckmatrixthatissparseParityCheckCodesDefinitionAregular(j,k)LDPCmatrixisanM×Nbinarymatrixhavingexactlyjonesineachcolumnandexactlykonesineachrow,wherej<kandbotharesmallcomparedtoN(AnirregularLDPCmatrixisstillsparse,butnotallrowsandcolumnscontainthesamenumberofonesTosimplifyourdiscussionwewillfocusonregularLDPCmatrices)Bythisdefinition,everyparitycheckequationofaregularLDPCcodeinvolvesexactlykbits,andeverybitisinvolvedinexactlyjparitycheckequationsTherestrictionj<kisneededtoensurethatmorethanjusttheallzerocodewordsatisfiesalloftheconstraints,orequivalently,toensureanonzerocoderateIndeed,thetotalnumberofonesinHisMk=Nj,sincethereareMrows,eachcontainingkones,andthereareNcolumns,eachcontainingjonesThecoderateR=–M⁄NisthenR=–j⁄k,assumingtheMrowsarelinearlyindependentTheneedforj<kisthusclearFromtheequationMk=Nj,wealsofindthatthenumberofrowsina(j,k)LDPCmatrixisM=Nj⁄kItimmediatelyfollowsthattheparametersN,j,andkcannotbechosenindependently,butmustberelatedinsuchawaythatNj⁄kisbeanintegerForexample,a(,)LDPCmatrixexistswhenN=andN=,butnotwhenN=Observethatthefractionofonesinaregular(j,k)LDPCmatrixisk⁄NThe“lowdensity”terminologyderivesfromthefactthatthisfractionapproacheszeroasN→∞Incontrast,theaveragefractionofonesinapurelyrandombinarymatrix(withindependentcomponentsequallylikelytobezeroorone)is⁄AnM×Nregular(j,k)LDPCmatrixcanoften(butnotalways)beconvenientlyexpressedintermsofthefollowingshorterparitycheckmatrixH:H=()IthasN⁄k=M⁄jrowsandNcolumnsThemthrowcontainsonesincolumns(m–)kthroughmkandzeroselsewhereByitself,HwoulddefineacodeconsistingofN⁄kindependentsingleparitycheckconstraints,withthefirstrowconstrainingtheparityofthefirstblockofkcodedbits,thenextrowconstrainingtheparityofthesecondblockofkbits,etcInthiscode,everyparitycheckinvolveskbits,andeachbitisinvolvedinoneandonlyoneparitycheckHence,Halonedefinesa(,k)regularLDPCcodeHowever,theperformanceofthiscodewouldbepoorInfact,becausethefirsttwocolumnsofHarelinearlydependent(orequivalentlybecause…and…arebothvalidcodewords),theminimumdistanceforthecodewouldbetwoWecanconstructaregular(j,k)LDPCmatrixbystackingjcolumnpermutationsofHoneatopanother:…………kkkLowDensityParityCheckCodesH=()Herepii(H)denotesamatrixwhosecolumnsareapermutedversionofthecolumnsofHSinceeachrowofHhaskones,eachrowofHalsohaskonesSimilarly,sinceeachcolumnofHcontainsasingleone,eachcolumnofHcontainsjonesWeremarkthatnotall(j,k)regularLDPCmatricesHsatisfyingDefncanbeexpressedintheformof()WeremarkthatthebuildingblockHin()waschosensomewhatarbitrarilyanycolumnpermutationofHcouldhavebeenusedinitsplaceForexample,wecanequivalentlyuseH=III…Iinplaceof(),whereHisaconcatenationofkidentitymatricesIN⁄kAproperchoiceofthepermutationswillallowtheminimumdistanceofthecodedefinedbyHtoincreasebeyondtwoTheprospectofdesigningjdifferentpermutationsoflengthNmayatfirstseemdaunting,especiallyforlargeNHowever,GallagerprovedthatatotallyrandomchoicewillonaverageproduceanexcellentcodeInparticular,ifeachpermutationischosenindependentlyanduniformlyfromthesetofallN!possiblepermutations,thentheexpectedminimumdistancethatresultswillincreaselinearlywithNAcodewithsuchapropertyissaidtobe“good”TheideaofdesigningcodesrandomlydidnotoriginatewithGallager,butdatesbacktoShannon’soriginalworkThebeautyofGallager’sdesignisthat,unlikeShannon’srandomcodes,wewillseethatitispossibletodecodeGallager’scodeswithcomplexitythatgrowsonlylinearlywithNExampleThefollowingisanexampleofaLDPCmatrixwithwordlengthN=,j=,andk=:H=()ThehorizontallinesseparateHanditstwopermutationsWeseethateachcolumncontainsj=ones,andeachrowcontainsk=onesThecorrespondingpermutationsarepi=…,pi=,andpi=ItcanbeshownthatthetenthrowofHisthesumofthefirstninerows,andthatthefifteenthrowisthesumofrowsonethroughfiveandrowseleventhroughfourteenThusrowstenandfifteenarelinearlydependentontheremainingrowsItcanbeshownthattheremainingrowsarelinearlyindependentHence,therankofHis,thedimensionoftheLDPCcodeisK=,andthecoderateisK⁄N=piH()piH()pijH()ParityCheckCodesThepreviousparitycheckmatrixhasrows,butonlyofthemareindependentWecoulddefineanewfullrankparitycheckmatrixbyeliminatingtheredundantrowsfromHThenwoulddescribethesamecodeasH,sincecHT=ifandonlyifcT=However,thenumberofonesinkcolumnsofwoulddecreaseeachtimearedundantrowisremoved,sothatwouldnolongerobeytheregularitypropertyofaregularLDPCmatrixWewilloftenchoosetodescribeanLDPCcodebyarankdeficientbutregularLDPCmatrix,asopposedtoitsmoreefficientbutirregularfullrankequivalentAnyparitycheckcode(includinganLDPCcode)maybespecifiedbyaTannergraph,whichisessentiallyavisualrepresentationoftheparitycheckmatrixHRecallthatanM×NparitycheckmatrixHdefinesacodeinwhichtheNbitsofeachcodewordsatisfyasetofMparitycheckconstraintsTheTannergraphcontainsN“bit”nodes,oneforeachbit,andM“check”nodes,oneforeachoftheparitychecksThebitnodesaredepictedusingcircles,whilethechecknodesaredepictedusingsquaresThechecknodesareconnectedtothebitnodestheycheckSpecifically,abranchconnectschecknodemtobitnodenifandonlyifthemthparitycheckinvolvesthenthbit,ormoresuccinctly,ifandonlyifHm,n=Thegraphissaidtobebipartitebecausetherearetwodistincttypesofnodes,bitnodesandchecknodes,andtherecanbenodirectconnectionbetweenanytwonodesofthesametypeExampleTheTannergraphassociatedwiththe×LDPCmatrixof()isshowninFigThebitnodesarerepresentedbytheN=circlesatthetop,whilethechecknodesarerepresentedbytheM=squaresatthebottomThefirst(leftmost)fivechecknodescorrespondtoH,thesecondfivetopi(H),andthelastfivetopi(H)Forthespecialcaseofa(j,k)regularLDPCcode,eachbitisinvolvedinjparitychecksHence,thenumberofbranchesemanatingfromabitnodeisalwaysjSimilarly,becauseeachparitycheckinvolvedkbits,thenumberofbranchesemanatingfromeachchecknodeisalwayskObservethatthegraphofFigsatisfiesthesepropertiesH˜H˜H˜H˜H˜FigTheTannergraphfortheLPDCmatrixof()LowDensityParityCheckCodesThevalueoftheTannergraphwillbecomeclearinthenextsection,wherewedescribeadecodingalgorithmforLDPCcodesThere,thegraphwillbeusedtodescribeaparallelimplementationofadecoder,withthedifferentnodesrepresentingseparateprocessors,andedgesrepresentingcommunicationbetweenprocessorsDecodingParityCheckCodesBackgroundandTerminologyTheprobabilitydistributionforabinaryrandomvariablec∈{,}isuniquelyspecifiedbythesingleparameterp=Prc=,sincePrc==–pAlternatively,theprobabilitydistributionisalsouniquelyspecifiedbythelogarithmoftheratio:λ=log()Torecoverpfromλ,weobservethateλ=p⁄(–p),andsolvingforpyieldsp=⁄(e–λ)Thesignofλindicatesthemostlikelyvalueforcλispositivewhenismorelikelythan,andλisnegativewhenismorelikelythanMoreover,themagnitude|λ|isameasureofcertaintyAtoneextreme,ifλ=thenandareequallylikelyAttheotherextreme,ifλ=∞thenc=withprobability,andλ=–∞impliesc=Givenarandombitc∈{,},letrdenoteanobservationwhosepdfdependsoncaccordingtof(r|c)Whencisfixedandf(r|c)isviewedasafunctionofr,itiscalledaconditionalpdfOntheotherhand,whenrisfixed,thenf(r|c)asafunctionofciscalledthelikelihoodfunctionBeforemakinganobservation,theaprioriprobabilitiesforcarePrc=andPrc=Aftermakinganobservation,theseprobabilitieschangetotheaposterioriprobabilities(APP)Prc=|randPrc=|rBecauseofBayesrule,theaposterioriprobabilityisproportionaltothelikelihoodfunction:Prc=|r=f(r|c=)Prc=⁄f(r)()Hence,thelogarithmoftheratioofaposterioriprobabilitiescanbeexpressedas:log=loglog()Thefirsttermontherighthandsideiscalledtheloglikelihoodratio(LLR)Strictlyspeaking,thesecondtermontherighthandsideisalogprobabilityratio,andthelefthandsideisalogAPPratioHowever,withanabuseofnotation,thesecondtermontherighthandsideismorecommonlycalledtheaprioriLLR,andthelefthandsideiscalledtheaposterioriLLRIfcisequallylikelytobezeroorone,thentheaprioriLLRiszero,andtheaposterioriLLRisequaltotheLLRPrc=Prc=Prc=|rPrc=|rf(r|c=)f(r|c=)Prc=Prc=DecodingParityCheckCodesTheTanhRuleLetφ(c)∈{,}denotetheparityofasetc=c…cnofnbits,sothatφ(c)=ifthereareanevennumberofonesinc,andφ(c)=ifthereareanoddnumberIfthebitsareindependent,theaprioriLLRfortheparityobeysthetanhruleExercise(TheTanhRule)Letc=c…cn∈{,}nbeavectorofnbitsthatareindependentbutnotequiprobableletλi=log(Prci=⁄Prci=)denotetheaprioriLLRfortheithbitShowthattheaprioriLLRλφ(c)=log(Prφ(c)=⁄Prφ(c)=)fortheparitysatisfiesthesocalled“tanhrule:”tanh=tanh()SolutionSeeAppendixASolving()forλφ(c)yieldsthefollowingequivalentrelationship:λφ(c)=–tanh–tanh()Alternatively,ifwetreatthesignsandmagnitudesoftheLLRsseparately,thenAppendixBshowsthat()canequivalentlybeexpressedas:λφ(c)=–sign(–λi)f,()wherewehaveintroducedthespecialfunction:f(x)=log=–log(tanh(x⁄))()Inhardwareimplementations,()ispreferredover()or(),becauseitinvolvesthesumofntermsinsteadoftheproductntermsNevertheless,()ispreferredinanalysisbecauseofitsconceptualsimplicityThefunctionf(x)hassomeinterestingpropertiesAsshowninFig,itispositiveandmonotonicallydecreasingforx>,withf()=∞andf(∞)=Furthermore,f(x)isitsowninverse!Thatis,f(f(x))=xforallx>ThispropertyiseasilyverifiedbydirectsubstitutionLet=…ndenotethemostlikelyvalueforc,where=ifλi>,else=Thesignofλφ(c),whichindicatesthemostlikelyvalueforφ(c),iscompletelydeterminedbyφ(),accordingto:sign(λφ(c))=–sign(–λi)=–(–)()Thisistobeexpected,sincetheparityismostlikelyevenwhenanevennumberofλi’sarepositive,andoddwhenanoddnumberarepositive–λφ(c)i=n∏–λii=n∏–λii=n∏Πi=nfλi()i=n∑exex–cˆcˆcˆcˆicˆicˆΠi=nφcˆ()LowDensityParityCheckCodesOntheotherhand,themagnitudeofλφ(c),whichmeasuresthecertaintythatφ(c)isitsmostlikelyvalue,isgivenby|λφ(c)|=f(Σif(|λi|))Supposethekthbitckofcisequallylikelytobeor,sothatλk=ThekthterminthesumΣif(|λi|)istheninfinity,sothattheentiresumisinfiniteBecausef(∞)=,itfollowsthat()reducestoλφ(c)=wheneveranyoneofthebitshaszerologlikelihoodratioThismakesintuitivesense,sinceifonebitisequallylikelytobezeroorone,thentheparityoftheentirevectorisequallylikelytobezeroorone,regardlessoftheprobabilitiesoftheremainingbitsMoregenerally,wheneveronebitissignificantlylesscertainthantheothers,sothatthesummationisdominatedbyf(|λmin|),where|λmin|=mini{|λi|},thenthemagnitudeofλφ(c)simplifiesto:|λφ(c)|=f(Σif(|λi|))≈f(f(|λmin|))=|λmin|()ThecertaintyintheparityofavectorcanthusbeapproximatedbythecertaintyoftheleastcertainbitSubstituting()into()yieldsthefollowingapproximation:λφ(c)≈–(–)|λmin|()Inthenextsectionwewillshowhow()canbeusedinthedecodingproblem,butalowercomplexityapproximationwoulduse()inplaceof()TheDecodingProblemLetusconsidertheproblemofdecodingacodewithparitycheckmatrixH,giventhatthechanneladdswhiteGaussiannoise,sothatthereceiverobservationr=r…rNisrelatedtothetransmittedcodewordc=c…cNby:r=c–n,()wherethecomponentsofthenoisevectornareindependentzeromeanGaussianrandomvariableswithvarianceσ(Thisimpliesanantipodalbittosymbolmapping→–,→)FigThefunctionf(x)xf(x)φcˆ()DecodingParityCheckCodesThedetectorthatminimizestheprobabilityoferrorforthenthbitwouldcalculatetheaposterioriLLR:λn=log=log,()andthendeciden=ifλn>,andn=otherwiseApplyingBayesrule,thenumeratorin()canbewrittenas:Prcn=|rn,{ri≠n}===()Thelastequalityexploitsthefactthat,givencn,rnisindependentof{ri≠n}Thedenominatorof()canbesimilarlyexpressedHence,()simplifiesto:λn=log=loglog=rnlog,()whereweusedthefactthatf(rn|cn)=exp(–(rn–cn)⁄(σ))fortheAWGNchannelThefirsttermin()representsthecontributionfromthenthchannelobservation,andiscalledtheintrinsicinformation,whilethesecondtermrepresentsthecontributionfromtheotherobservations,andiscalledtheextrinsicinformationInterestingly,thecontributionsarecombinedbysimplyaddingFurther,theintrinsicinformationisproportionaltothenthchannelobservationTheconstantofproportionality⁄σiscalledthechannelreliabilityExerciseConsiderabinarysymmetricchannelwithinputandoutputalphabet{±}ShowthattheaposterioriLLRisagaingivenby(),exceptthatthechannelreliabilityisloginsteadof⁄σ,wherepisthecrossoverprobabilityBeforewecansimplify()further,wemustexaminemorecloselythestructureoftheTannergraphConsiderFig,wherewedrawthegraphofaLDPCcodefromtheperspectiveofthenthbitnode,andwherewehaverearrangedthebitnodesandchecknodessoastoPrcn=|rPrcn=|rPrcn=|rn,{ri≠n}Prcn=|rn,{ri≠n}cˆcˆf(rn,cn=,{ri≠n})f(rn,{ri≠n})f(rn|cn=,{ri≠n})f(cn=,{ri≠n})f(rn|{ri≠n})f({ri≠n})f(rn|cn=)Prcn=|{ri≠n}f(rn|{ri≠n})f(rn|cn=)Prcn=|{ri≠n}f(rn|cn=)Prcn=|{ri≠n}f(rn|cn=)f(rn|cn=)Prcn=|{ri≠n}Prcn=|{ri≠n}σPrcn=|{ri≠n}Prcn=|{ri≠n}intrinsicextrinsicpiσ()–p–pLowDensityParityCheckCodesavoidcrossingedgesThenthbitisinvolvedinexactlyjparitychecks,numberedthroughj,andeachofthechecksinvolvek–otherbitsAsshowninthefigure,letc(i)=ci,…ci,kdenotethesetofbitsinvolvedintheithparitycheckequation,excludingcnAcycleisapaththroughthegraphthatbeginsandendsatthesamebitnodeThelengthofthecycleisthenumberofedgestraversedBecausethegraphisbipartite,theminimumlengthofacycleisfourForexample,forthegraphshowninFig,theexistenceofacycledependsonthedottededgeWiththedottededgeinplace,thegraphcontainsasinglecycleoflengthfourHowever,ifweweretoremovethedottededge,thegraphwouldhavenocyclesAgraphwithoutcyclesisatreeAcyclefreegraphhasthefollowingproperties:•removinganyedgecreatestwoseparatesubgraph•thereisauniquepathconnectinganypairofbitnodes•Asaspecialcaseoftheabove,fromthepointofviewofthebitnodecn:Everybitnodeisreachablefromcnthroughoneandonlyoneoftheedgesincidentoncn•Ifbitnodescjand

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/20

ldpc

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利