IEEE Transactions on Information Theory Special Is

ADistanceSpectrumInterpretationofTurboCodes.¤LanceC.PerezDepartmentofElectricalEngineeringUniversityofNebraska-LincolnLincoln,NE68588JanSeghersInstituteforSignalandInformationProcessingSwissFederalInstituteofTechnologyZurich,SWITZERLANDDanielJ.Costello,Jr.DepartmentofElectricalEngineeringUniversityofNotreDameNotreDame,IN46616IEEETransactionsonInformationTheorySpecialIssueonCodingandComplexitySubmitted:January,1996Revised:April,1996AbstractTheperformanceofTurbocodesisaddressedbyexaminingthecode'sdistancespectrum.The`error°oor'thatoccursatmoderatesignal-to-noiseratiosisshowntobeaconsequenceoftherelativelylowfreedistanceofthecode.Itisalsoshownthatthe`error°oor'canbeloweredbyincreasingthesizeoftheinterleaverwith-outchangingthefreedistanceofthecode.Alternatively,thefreedistanceofthecodemaybeincreasedbyusingprimitivefeedbackpolynomials.TheexcellentperformanceofTurbocodesatlowsignal-to-noiseratiosisexplainedintermsofthedistancespectrum.TheinterleaverintheTurboencoderisshowntoreducethenumberoflowweightcodewordsthroughaprocesscalled`spectralthinning'.Thisthinneddistancespectrumresultsinthefreedistanceasymptotebeingthedominantperformanceparameterforlowandmoderatesignal-to-noiseratios.Keywords:Turbocodes,convolutionalcodes,distancespectrum.¤ThisworkwassupportedbyNASAgrantNAG5{557,NSFgrantNCR95{22939,andtheLockheed-MartinCorporation.11IntroductionThediscoveryofTurbocodesandthenearcapacityperformancereportedin[1]hasstimulateda°urryofresearche®ortstofullyunderstandthisnewcodingscheme[2]-[43].Initiallygreetedwithsomeskepticism,theoriginalresultswereindependentlyrepro-ducedbyseveralresearchers[6],[7],[10]{[11],[12],[13],and[30].Subsequently,recentresearchonTurbocodeshasfocusedonunderstandingthereasonsfortheiroutstandingperformance[8]{[9],[16],[22]{[24],[28].Atthispoint,therearetwofundamentalquestionsregardingTurbocodes.First,doestheiterativedecodingschemepresentedin[1]alwaysconvergetotheoptimumsolution?Second,assumingoptimumornearoptimumdecoding,whydotheTurbocodesperformsowell?Inthispaper,weaddressthesecondissueinasemi-tutorialmannerbyexaminingthedistancespectrumofTurbocodes.Indoingso,wewilldrawontheworkofseveralresearchgroupsinvolvedwithTurbocodes[6]{[9],[12]{[14],[18]{[24].Duetotheintenseinterestinthissubject,manyresultsinvolvingTurbocodeshavebeendevelopedindependentlybyothersandthereaderisencouragedtoperusethereferencesforanalternativepointofview.Inparticular,therecentpapersbyBenedettoandMontorsi[8]{[9]werethe¯rsttoo®eracomprehensivepictureofTurbocodes.Thesimulatedperformanceofarate1/2Turbocodewiththesameparametersasin[1]isshowninFigure1alongwithsimulationresultsforarateR=1=2,memoryº=14,convolutionalcode.ThecomparisonofthesesimulationresultsraisestwoissuesregardingtheperformanceofTurbocodes.First,whatisitthatallowsTurbocodestoachieveabiterrorrate(BER)of10¡5atasignal-to-noiseratio(SNR)ofEb=N0=0:7dB,whichisonly0.7dBfromtheShannonlimit?Second,whatcausesthe\error°oor[10],[13],thatis,the°atteningoftheperformancecurve,formoderatetohighSNR's?Here,weendeavortoexplaintheperformanceofTurbocodes,andthusaddressthesetwoissues,intermsofthecode'sdistancespectrum.Wedonotattempttoaddressthemanyinterestingquestionsconcerningtheiterativedecodingmethod(see,e.g.,[15],[26],[42],and[43]),i.e.,weassumethatanoptimumornearoptimumdecoderisavailable.Inordertoexplaintheirperformanceintermsofthefreedistanceandthedistancespectrum,wewillexaminethecodewordstructureofTurbocodesindetail.Here,thefreedistanceisde¯nedtobetheminimumHammingweightofallpossiblecodewordsandtheerrorcoe±cientisthetotalnumber,ormultiplicity,offreedistancecodewords.Thegoalistousespeci¯cexamplestoelucidatethekeystructuralpropertiesthatresultinthenearcapacityperformanceofTurbocodesatBER'saround10¡5.Aswillbeseen,thise®ortleadstoanexplanationthatappliestoTurbocodesandalsolendsinsightintodesigningcodesingeneral.Throughoutthepaper,Turbocodesarecomparedtoamaximumfree2distance,rateR=1=2,memoryº=14,i.e.,a(2;1;14),convolutionalcodetoemphasizethedi®erencesinperformanceandstructure.TechniquesforanalyzingtheperformanceofTurbocodesusingtransferfunctionsandrelatedmethodsmaybefoundin[6],[9],and[22].ThepaperbeginswithadetailedexaminationofthestructureofcodewordsinaTurbocodeinSectionII.ThisleadstothecalculationofthefreedistanceofaparticularTurbocodeandanexplanationforthe\error°oorinitsperformancecurve.InSectionIII,thedistancespectrumof\averageTurbocodesisconsideredandatheorycalledspectralthinningisintroducedandusedtoexplaintheperformanceofTurbocodesatlowSNR's.TheideaofspectralthinningisthenformalizedinSectionIVthroughtheuseofrandominterleaving.Finally,someconclusionsaredrawnconcerningthedistancespectrumofTurbocodesandtheconsequencesofthisonthedesignofcodesingeneral.2TheFreeDistanceofTurboCodesInorderto¯ndthefreedistanceofaTurbocode,itisnecessarytounderstandthebasicstructureoftheencoderandtheresultingcodewords.AtypicalTurboencoderconsistsoftheparallelconcatenationoftwoormore,usuallyidentical,rate1/2encoders,realizedinsystematicfeedbackform,andaninterleaver.Thisencoderstructureiscalledaparallelconcaten