外文翻译原文-LDPC的磁化性能降低复杂度

Int.J.Communications,NetworkandSystemSciences,2010,3,548-553doi:10.4236/ijcns.2010.36073PublishedOnlineJune2010(http:/www.SciRP.org/journal/ijcns/).Copyright2010SciRes.IJCNSMagnetizationPerformanceofLDPCReduced-ComplexityDecodingAlgorithmsManelAbdelhedi1,OmessaadHamdi2,AmmarBouallegue11SYSCOMLaboratory,ENIT,Tunis,Tunisia2LaBRILaboratory,UniversityofBordeaux,Bordeaux,FranceE-mail:abdelhedi_manelyahoo.fr,hamdiuniv-tln.fr,ammar.bouallegueenit.rnu.tnReceivedMarch20,2010;revisedApril21,2010;acceptedMay26,2010AbstractLow-densityparity-check(LDPC)codesareveryefficientforcommunicatingreliablythroughanoisychannel.N.Sourlas1showedthatLDPCcodes,whichrevolutionizethecodesdomainandusedinmanycommunicationsstandards,canbemappedontoanIsingspinsystems.Besides,ithasbeenshownthattheBelief-Propagation(BP)algorithm,theLDPCcodesdecodingalgorithm,isequivalenttotheThouless-Anderson-Palmer(TAP)approach2.Unfortunately,nostudyhasbeenmadefortheotherdecodingalgo-rithms.Inthispaper,wedeveloptheLog-LikelihoodRatios-BeliefPropagation(LLR-BP)algorithmanditssimplificationstheBP-Basedalgorithmandthe-minalgorithmwiththeTAPapproach.Wepresenttheperformanceofthesedecodingalgorithmsusingstatisticalphysicsargumenti.e.,wepresenttheperformanceasfunctionofthemagnetization.Keywords:LDPCCodes,IsingSpin,LLR-BPAlgorithm,BP-BasedAlgorithm,-MinAlgorithm,TAPApproach1.IntroductionLow-densityparity-check(LDPC)codeswerefirstdis-coveredbyGallager3,inhisthesis,in1962andhaverecentlybeenrediscoveredbyMackayandNeal3,4.ThesecodescangetveryclosetotheShannonlimitbymeanofaniterativedecodingalgorithmcalledBelief-Propagation(BP)algorithm5.Thisperformancecombinedwiththeirrelativelysim-pledecodingalgorithmmakesthesecodesveryattractiveforthenextgenerationofdigitaltransmissionsystems.Indeed,thesecodeshavebeenchosenasastandardforthesecondSatelliteDigitalVideoBroadcastingnormali-zation(DVB-S2).So,thesearchforefficientimplemen-tationsofdecodingalgorithmsisbeingachallenge.TheimplementationoftheBPalgorithmisdifficult.Thatswhydifferentsimplificationsofthisalgorithmwerediscovered.TheBPalgorithmcanbesimplifiedusingtheBP-Basedalgorithm6andthe-minalgorithm7.N.Sourlas1hasshownin1989thatthereisamathe-maticalequivalenceoferror-correctingcodestosometheoreticalspin-glassmodels.Thisanalogyhascontributedtothepresentproximityofthestatisticalphysicsandtheinformationtheory.Therefore,themethodsofstatisticalphysicsdevelopedinthestudyofdisorderedsystemsprovedtobeefficientforstudyingthepropertiesofthesecodes.OneofthesemethodsistheThouless-Anderson-Palmer(TAP)2approachwhichisshownequivalenttotheBPalgorithmbykabashima,etal.8.Unfortunately,nostudyhasbeenmadefortheotherdecodingalgorithms.Inthispaper,wedeveloptheLog-LikelihoodRatios-BeliefPropagation(LLR-BP),theBP-Basedandthe-mindecodingalgorithmswiththeTAPapproach.Theirper-formanceisevaluatedasafunctionofastatisticalphysicsparameterwhichisthemagnetization.Thispaperisorganizedasfollows.Section2corre-spondstoageneraldescriptionoftheLDPCcodesandtheirdecodingalgorithm.Section3describesthesimilar-itybetweentheBPalgorithmandtheTAPapproach.InSection4,wedeveloptheLLR-BPalgorithmanditssimplificationstheBP-Basedalgorithmandthe-minalgorithmwiththeTAPapproach.Finallyandbeforeconcluding,simulationresultsasfunctionofthemag-netizationarepresentedinSection5.2.LDPCCodesandDecodingAlgorithm2.1.Low-DensityParityCheckCodesBinaryLDPCcodes,arelinearblockcodesdefinedbyaM.ABDELHEDIETAL.Copyright2010SciRes.IJCNS549sparseparitycheckmatrixAMN,whereNdenotesthecodewordlengthandMthenumberofparity-checkequations.Usinganotationsimilartothatin4,6,letL/1jjAdenotethesetofbitjthatparticipateincheck.Similarly,wedefinethesetofchecksinwhichbitjparticipatesas1/jAjM.WedenoteasetLwithbitjexcludedbyjL,andasetjMwithparitycheckexcludedbyjM.Finally,Nsss,.,1denotesthetransmittedcode-word.2.2.BeliefPropagationAlgorithmThissectionsummarizesaccordingto4,5,theiterativedecodingofLDPCcodesbasedontheBPalgorithm.Thelikelihoodofsisgivenbyjajf,withajfP(sj=a).Letajqdenotestheprobabilitythatbitjofsisa,giventheinformationobtainedviachecksotherthancheck.Thequantityajrismeanttobetheprobabil-ityofcheckissatisfiedifbitjofsisconsideredfixedataandtheotherbitshaveaseparabledistribu-tiongivenbytheprobabilitiesjLlql:6.ThestandarditerativedecodingalgorithmbasedontheBPapproachconsistsonthefollowingmainsteps.Initialization:Thevariables0jqand1jqareini-tializedtothevalues0jfand1jfrespectively.Iterativeprocessing:1)Define10jjjqqqandforeach,Lj,andfor1,0a,computejaajjLlljrrqr1121)(2)ForeachjandjM,andfor1,0aupdate)(jMajajjajrfq)(jMajajjajrfqwherejandjarechosensuchthat110jjqqand.110jjqq3)Createtheword1(.)Nsssthedetectionofthetransmittedcodewordsuchthat:0if10if0jjjjqsqsIf0.TsHthedecodingprocessends.Otherwise,wepasstoanotheriterationofBP.Afailureisdeclaredandthedecodingprocessendsifthenumberofiterationsexceedsthemaximumnumberofiterationsandsisnotavalidcodeword.3.DecodingProblemfromStatisticalPhysicsPointofView3.1.StatisticalPhysicsAnalogyIntheprevioussection,wehavedescribedtheLDPCcodesusingtheadditiveBooleangroup,1,0.How-ever,inordertoapplymethodsofstatisticalphysics,itisconvenienttointroduceanequivalentgroup,themulti-plicativebinarygroup,1,11.Fromastatisticalphysicspointofview,thecodecanberegardedasaspinsystem.EachbitjsjS)1(iscalledaspinandtakesvaluesin1andthewordNssS1,.,11canbeseenasacollectionofNspins,calledaconfiguration.Theparity-checkmatrixgivesrisetotheinteractionsbetweenthespins1.ThedecodingproblemdependsonposteriorilikeJSPwhereJistheevidence(receivedmessageorsyndromevector).ByapplyingBayestheoremthisposterioricanbewrittenintheform1.SPSJPZSPSJPSPSJPJSPSlnlnexp1(1)Inthestatisticalphysicsdescription,theprobability(1)canbeexpressedasaBoltzmanndistributionatthein-versetemperature9.1expPSJHSJZ(2)whereJSHistheHamiltonianofthesystem.InthisHamiltonian,weidentifytwocomponentsthatarenecessaryfortheanalysisofLDPCcodes.Atermthatguaranteesthatallparitychecksaresat-isfied.ItcanbewrittenwiththeKroneckersdelta1.MLjjSJSJP1,According9,thescanbereplacedbyasoftcon-straint.MLjjSJconstSJP1expM.ABDELHEDIETAL.Copyright2010SciRes.IJCNS550where.Apriortermthatprovidessomestatisticalinforma-tiononthedynamicalvariablesS.Itcanberepre-sentedbythepriordistributionNNjjFSFSPcosh2exp)(1whereFistheexternalfield.ItisdeterminedbytheflipratefofchannelnoiseasffF1ln21.So,theHamiltonianJSHiswrittenasfollows:MLjNjjjSFSJJSH11whereJisthemuti-spincoupling.3.2.DecodingintheStatisticalPhysicsThedecodingprocesscorrespondstofindinglocalmagnetizationattheinversetemperature,jjSmandcalculatingestimatesas1.jjmSsign(3)Thedecodingperformanceinthestatisticalphysicsapproachcanbemeasuredbythemagnetization1definedbytheoverlapbetweentheactualmessageandestimate:NjjjSSNm11Heretheoverage.isperformedoverthematri-cesA.Thisvalueprovidesinformationaboutthetypicalperformanceofthecode.TheMagnetizationisanorderparameterwhichhasastandardofjudgmentwhetherthewholesystemexhib-itsanorderedstateornot.If1mthesystemisinanorderedphasecalledferromagneticphase.If0mthesystemisinadisorderedphasecalledparamagneticphase.Twomainmethodscanbeemployedforcalculatingthevalueofthemagnetization:thereplicamethodfordilutedsystems9andtheTAPapproach8.Inthispaper,weareinterestedonlyontheTAPapproach.3.3.TAPApproachKabashima,etal.8haveshownthesimilaritybetweenequationsderivedfromtheTAP2approachandthoseobtainedfromBP.Thefieldsajqcorrespondtothemeaninfluenceofsitesotherthanthesitejandthefieldsajrrepresenttheinfluenceofjbackoverthesystem(reactionfields)10.ThesimilaritycanbeexposedbyobservingthatthelikelihoodSJPisproportionaltotheBoltzmannweight11LjjjBSJLjSJexp:TheconditionalprobabilityjSjrcanbeseenasanor-malizedeffectiveBoltzmannweight(effectiveBoltz-mannprobability)obtainedbyfixingthebitjS10jLlSjLlSllBjjeffjSjlljqLlSJSJr:)(:SincespinvariablejStakesonlytwovalues1,itisconvenienttoexpresstheBP/TAPalgorithmusingspinaveragesjjSjSjqS1andjjSjSjrS1ratherthanthedis-tributionsjSjqandjSjrthemselves.WeusejjmqtodenotejjSjSjqS1.SimilarnotationjjmrisusedforjjSjSjrS1.Additionally,itwasshownin10thatthefollowingstatementsholdjLlljmJmtanh(5)1tanhtanhjMjjFmm(6)Thepseudo-posterioricanthenbecalculatedlMjjFmmtanhtanh1(7)ThisprovidesawayforcomputingtheBayesoptimaldecodingasfollows:jjjmqSsignsign(8)Theresultthatjjmqisdemonstratedasfollows:jSjjSSSjSjSjjjqJSPSJSPSJSPSJSHSZSmjjjexp1(9)M.ABDELHEDIETAL.Copyright2010SciRes.IJCNS5514.LLR-BPAlgorithmanditsSimplificationswithTAPApproach4.1.LLR-BPAlgorithmwithTAPApproachIntheLLR-BPalgorithminsteadofhandlingprobabili-tiesasin3,5wearegoingtodealwiththeLLRs.Inpractice,usingLLRsasmessagesoffersimplementationadvantagesoverusingprobabilitiesorlikelihoodratiosbecausemultiplicationsarereplacedbyadditionsandthenormalizationstepiseliminated11.Inthissection,wetrytodeveloptheLLR-BPwiththeTAPapproach.LetjxandjybetheLLRofbitjwhicharesentfrombitnodejtochecknodeandfromthechecknodetobitnodej,respectively.Fromthestatisticalphysicsdefinition,theLLRisdefinedasfollows12:2ln2111jjjjxqqx(10)And2ln2111jjjjyrry(11)Weneedalsothefollowingresultsjjjjjjjjjjmqqqqqqqqx11111111ln21tanhtanh(12)Likein(12),thevariablejmcanbealsowrittenas:jjymtanh(13)So,fromEquations(5),(12)and(13)wehaveFyFmxjMjjMjj11tanhtanhtanh1(14)Also,jycanbewrittenasjLlljjxJmy11tanhtanhtanh1tanh1(15)Finally,theposterioriLLRofbitjSisFyxjMjj(16)Itsnoteasytoimplement(15)whichhastheformofaproduct.Ourideaistodecomposethechecknodeup-dateintosignandmagnitudeprocessinglikein13.Wehavefrom(15)jLlljxJytanhtanhtanh(17)ReplacingJbyJJsignandlxbyllxxsignin(17)yieldsjLlljLlljxJxJy2signsignsign(18)jLlljjLlljxJyxJy2tanh22tanh2tanhtanhtanhtanh(19)Lettfbedefinedby11ln2tanhlntteettf(20)Then,takingthelogarithmoftheinverseofbothsidesof(19)yieldslntanhlntanh2lntanh2222jllLjjllLjyJxfyfJfx(21)TheEquation(20)verifiesteeeetfftttt111111ln(22)SotheEquation(21)canbewritten2jllLjyffJfx(23)Using(10)and(11),theEquation(23)canbewrittenasjLlljxfJffy222(24)From(18)and(24),thechecknodeprocessinginthestatisticalphysicsisdenotedbyM.ABDELHEDIETAL.Copyright2010SciRes.IJCNS5521sign222jllLjllLjyJxffJfx(25)4.2.BP-BasedwithTAPApproachInthissection,wetrytodeveloptheapproximationoftheBPalgorithm:theBP-Based6algorithm,withtheTAPapproach.Thekeyideaofthisalgorithmisthatminttftft.Theinequalityisclearwhilede-pictingthefunctiontfontheFigure1.TheEquation(24)isthenapproximatedby222min2,2min2,2jllLjllLjllLjyffJfxffJxJx(26)So,theextrinsicinformationintheBP-Basedalgo-rithmwrittenwiththeTAPequationisgivenby:1signmin2,22signmin,jlllLjlLjlllLjlLjyJxJxJxJx(27)Therefore,thereisanimportantsimplificationintheBP-BasedalgorithmwithTAPapproachsincethechecknodeupdateisreplacedbyaselectionoftheminimuminputvalue.4.3.-minAlgorithmwithTAPApproachInthissection,wetrytodevelopthe-minalgorithm7withtheTAPapproach.Inthechecknodeupdateof(25),themagnitudeprocessingisrunusingthefunctionde-finedby(20).WhiledepictingthisfunctionontheFig-ure1,itisclearthatttfcanbeapproximatedbythemaximalvaluesoftfwhichisobtainedfortheminimalvaluesoft.So,likeGuilloud,etal.7weproposetocompute(24)withonlythebitsthatparticipateincheckandwhichhavetheminimummagnitude.222jllLjyffJfx(28)-10-5051000.511.522.53tf(t)f(t)=-log(tanh|t/2|)Figure1.Shapeofthefunctionf.With10,.,jjLbethesubsetofLwhichcontainsthebitsthatparticipateincheckwhichlxhavethesmallestmagnitude.Theextrinsicinformationinthe-minalgorithmwrit-tenwiththeTAPequationisgivenby(29)1sign222jllLjllLjyJxffJfx(29)Twocaseswilloccur:ifthebitjbelongstothesub-setL,thenjyareprocessedover1valuesofjL,otherwisejyareprocessedoverthevaluesofL.Hence,forthesecondcase,thecom-putationshavetobeperformedonlyonce13.5.SimulationResultsSimulationshavebeenperformedusingregular(3,6)LDPCcodeoflength1008Nandwith20decodingiterations.Weaveragedtheresultsover10codes.ThisensembleofLDPCcodeischaracterizedbythesameblocklength,theonesineachcolumnandtheonesineachrow.Foreachrun,afixedcodeisusedtogenerate1008bitcodewordfrom504bitmessage.Corruptedver-sionsofthecodewordarethendecodedusingLLR-BP,BP-Basedand-mindecodingalgorithms.Toobservetheeffectofthesimplificationin(27)and(29)ontheperformancefromastatisticalphysicspointofview,wehavecalculatedtheoverlapbetweentheac-tualmessageandtheestimate(magnetization)foreachfixedcodeandforeachalgorithm.After,weaveragetheobtainedresultsforthe10differentcodes.Figure2de-pictsthemagnetizationperformanceoftheLLR-BP,BP-Basedandthe-minalgorithms.f(t)tM.ABDELHEDIETAL.Copyright2010SciRes.IJCNS553AccordingtheresultsofFigure2,wecanconcludetheeffectivenessofthe-minalgorithm.Atamagnetiza-tionof0.9,theBP-Basedalgorithmintroducesadegra-dationof0.5dBwith20iterations.The2-minalgorithmintroducesadegradationof0.3dB.Theperformanceofthe3-minalgorithmisslightlyworsethanthatoftheLLR-BPalgorithm,thedegradationisonly0.08dB.AnotherremarkfromFigure2isthatathighsignaltonoiseratiothemagnetizationisconcentrateatthevalue1m.Thisvaluecorrespondstotheferromagneticstateinthestatisticalphysicsandtotheperfectdecodingintheinformationtheory.TheanalogybetweentheBitErrorRate(BER)per-formanceandthemagnetizationperformancecanbeexa-minedin14.6.ConclusionsInthispaper,wehavebeeninterestedinthedecodingofLDPCcodesfromastatisticalphysicsapproach.First,wehaveexaminedthecorrespondencebetweenLDPCcodesandIsingspinsystems.TherelationbetweentheBPalgorithmandTAPapproachisinvestigated.Then,weshowedthatLLR-BPalgorithmanditssimplificationi.e.theBP-Basedalgorithmandthe-minalgorithmcanbeobtainedusingtheTAPapproachofIsingspinsys-temsinstatisticalphysics.Besides,wehavepresentedtheperformanceofthedecodingalgorithmsusingasta-tisticalphysicsparameterwhichisthemagnetization.Finally,weconcludedthattheBP-Basedalgorithmreducesthecomplexityforupdatingextrinsicinforma-tionbutthereisdegradationinperformancecomparedtotheLLR-BPalgorithm.The-minalgorithmreducesthecomplexityforupdatingextrinsicinformationwithoutdegradationinperformancecomparedtotheLLR-BPalgorithmespeciallywhenincreases.Theseresultscon-11.522.533.540.70.750.80.850.90.9511.05Eb/N0mLLR-BP3-min2-minBP-BasedFigure2.MagnetizationperformanceoftheLLR-BP,BP-Basedand-minalgorithmswith=2,3,forthe(1008,3,6)LDPCcodeensembleandwith20decodingiterations.firmwiththeresultsobtainedintheinformationtheory.Asaperspectiveofourwork,weproposetostudythereplicamethod.Thisisamethodfromthestatisticalphysicsappliedtofindthemagnetization.Besides,weproposetosimplifytheequationsofthismethodbythesameapproximationintheBP-Basedalgorithmandthe-minalgorithminordertocomparetheanalyticresultswiththeexperimentalones.7.References1N.Sourlas,“Spin-GlassModelsasError-CorrectingCodes,”Nature,Vol.339,No.6227,1989,pp.693-695.2D.J.Thouless,P.W.AndersonandR.G.Palmer,“Solu-tionofSolvableModelofASpinGlass,”PhilosophicalMagazine,Vol.35,No.3,1977,pp.593-601.3R.G.Gallager,“Lo