Near-Shannon-limit-error-correcting-coding-and-dec

NEARSHANNONLIMITERROR-CORRECTINGCODINGANDDECODING:TURBO-CODES(1)ClaudeBerrou,AlainGlavieuxandPunyaThitimajshimaClaudeBerrou,IntegratedCircuitsforTelecommunicationLaboratoryAlainGlavieuxandPunyaThitimajshima,DigitalCommunicationLaboratoryEcoleNationaleSuNrieuredesTtlkommunicationsdeBretagne,France(1)PatentsNo9105279(France),No92460011.7(Europe),No07/870,483(USA)Abstract-ThispaperdealswithanewclassofconvolutionalcodescalledTurbo-codes,whoseperformancesintermsofBitErrorRate(BER)areclosetotheSHANNONlimit.TheTurbo-CodeencoderisbuiltusingaparallelconcatenationoftwoRecursiveSystematicConvolutionalcodesandtheassociateddecoder,usingafeedbackdecodingrule,isimplementedasPpipelinedidenticalelementarydecoders.I-INTRODUCTIONConsiderabinaryrateR=1/2convolutionalencoderwithconstraintlengthKandmemoryM=K-1.TheinputtotheencoderattimekisabitdkandthecorrespondingcodewordCkisthebinarycouple(Xk,Yk)withK-Ii=Oxk=zgIidk-;md.2gli=0,1(la)K-1Yk=zg2idk-imd.282i=0,1(Ib)i=OwhereGI:{gli),G2:(g2i}arethetwoencodergenerators,generallyexpressedinoctalform.Itiswellknown,thattheBERofaclassicalNonSystematicConvolutional(NSC)codeislowerthanthatofaclassicalSystematiccodewiththesamememoryMatlargeSNR.AtlowSNR,itisingeneraltheotherwayround.ThenewclassofRecursiveSystematicConvolutional(RSC)codes,proposedinthispaper,canbebetterthanthebestNSCcodeatanySNRforhighcoderates.AbinaryrateR=1/2RSCcodeisobtainedfromaNSCcodebyusingafeedbackloopandsettingoneofthetwooutputsXkorYkequaltotheinputbitdk.ForanRSCcode,theshiftregister(memory)inputisnolongerthebitdkbutisanewbinaryvariableak.IfXk=dk(respectivelyYk=dk),theoutputYk(resp.Xk)isequaltoequation(lb)(resp.la)bysubstitutingakfordkandthevariableakisrecursivelycalculatedasK-1ak=dk+1ria,-;md.2(2)i=lwhereyiisrespectivelyequaltogliifXk=dkandtog2iifYk=dk.Equation(2)canberewrittenasK-1i=Odk=Z7;Uk-itmd.2.(3)OneRSCencoderwithmemoryM=4obtainedfromanNSCencoderdefinedbygeneratorsG1=37,G2=21isdepictedinFig.1.Generally,weassumethattheinputbitdktakesvalues0or1withthesameprobability.Fromequation(2),wecanshowthatvariableakexhibitsthesamestatisticalproperty0-7803-0950-2/93/$3.00Q1993IEEE106.1Pr{ak=El,..ak-l=Ek-l)=Pr(dk=E)=1/2(4)withEisequaltoK-1I=1E=Cyieimd.2E=0,1.(5)ThusthetrellisstructureisidenticalfortheRSCcodeandtheNSCcodeandthesetwocodeshavethesamefreedistancedfHowever,thetwooutputsequences(Xk}and{Yk)donotcorrespondtothesameinputsequence(dk)forRSCandNSCcodes.Thisisthemaindifferencebetweenthetwocodes.Whenpuncturedcodeisconsidered,someoutputbitsXkorYkaredeletedaccordingtoachosenpuncturingpatterndefinedbyamatrixP.Forinstance,startingfromarateR=1/2code,thematrixPofrate2/3puncturedcodeisLJFig.1aClassicalNonSystematiccode.YkFig.1bRecursiveSystematiccode.'kI1-PARALLELCONCATENATIONOFRSCCODESWithRSCcodes,anewconcatenationscheme,calledparallelconcatenationcanbeused.InFig.2,anexampleoftwoidenticalRSCcodeswithparallelconcatenationisshown.Bothelementaryencoder(ClandC2)inputsusethesamebitdkbutaccordingtoadifferentsequenceduetothepresenceofaninterleaver.Foraninputbitsequence{&),encoderoutputsXkandYkattimekarerespectivelyequaltodk(systematicencoder)andtoencoderC1outputYlk,ortoencoderC2outputY2k.Ifthecodedoutputs(Ylk,Y2k)ofencodersC1andC2areusedrespectivelynltimesandn2timesandsoon,theencoderC1rateR1andencoderC2rateR2areequalto(6)n,+n,R,=2n,+nl**kSystemabCode(37,21)IFig.2RecursiveSystematiccodeswithparallelconcatenation.ThedecoderDECdepictedinFig.3a,ismadeupoftwoelementarydecoders(DEC1andDEC2)inaserialconcatenationscheme.ThefirstelementarydecoderDEClisassociatedwiththelowerrateR1encoderC1andyieldsasoft(weighted)decision.TheerrorburstsatthedecoderDECloutputarescatteredbytheinterleaverandtheencoderdelayL1isinsertedtotakethedecoderDECldelayintoaccount.Parallelconcatenationisaveryattractiveschemebecausebothelemenmyencoderanddecoderuseasinglefrequencyclock.Foradiscretememorylessgaussianchannelandabinarymodulation,thedecoderDECinputismadeupofacoupleRkoftworandomvariablesnkandyk,attimekxk=(24-1)+i,(74Y,=w,-u+q,,(76)whereikandqkaretwoindependentnoiseswiththesamevariance02.TheredundantinformationykisdemultiplexedandsenttodecoderDEClwhenYk=YlkandtowarddecoderDEC2whenYk=Y2k.Whentheredundantinformationofagivenencoder(ClorC2)isnotemitted,thecorrespondingdecoderinputissettozero.ThisisperformedbytheDEMUXDNSERTIONblock.Itiswellknownthatsoftdecodingisbetterthanharddecoding,thereforethefirstdecoderDEClmustdelivertotheseconddecoderDEC2aweighted(soft)decision.TheLogarithmofLikelihoodRatio(LLR),Al(dk)associatedwitheachdecodedbitdkbythefirstdecoderDEClisarelevantpieceofinformationfortheseconddecoderDEC2(8)P,{dk=1/observution)(dk'=LogP,{dk=O/observution)*whereP,{dk=ilobservation),i=0,1istheaposterioriprobability(APP)ofthedatabitdk.-_-DEMUWINSERTIONFig.3aPrincipleofthedecoderaccordingtoaserialconcatenationscheme.I11-OPTIMALDECODINGOFRSCCODESWITHWEIGHTEDDECISIONTheVITJZRBIalgorithmisanoptimaldecodingmethodwhichminimizestheprobabilityofsequenceerrorforconvolutionalcodes.UnfortunatelythisalgorithmisnotabletoyieldtheAPPforeachdecodedbit.Arelevantalgorithmforthispurposehasbe