100 SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS, MARCH 2000Convergence Behavior of Iteratively DecodedParallel Concatenated CodesStephan ten Brink,Member, IEEEAbstr act— Mutual information transfer characteristics forsoft in/soft out deco ders are proposed as a to ol to betterunderstand the convergence behavior of iterative decodingschemes. The exchange of extrinsic information is visual-ized as a decoding trajectory in the Extrinsic InformationTransfer Chart (EXIT chart). This allows the predictionof turbo cliff position and bit error rate after an arbitrarynumber of iterations. The influence of code memory, codepolynomials as well as different constituent codes on the con-vergence behavior is studied for parallel concatena ted codes.The applicability to other than Gaussian channels is illus-trated. A code search based on the EXIT chart techniquehas been performed which yielded new recursive systematicconvolutional constituent codes exhibiting turbo cliffs at lowsignal–to–noise ratios not attainable by previously knownconstituent codes. With these results the gap to Shannon’scapacity limit on the Gaussian channel narrows to 0.3dB forcode rates of 1:2 and 1:3.Keywords— Iterative decoding, turbo codes, convergence,mutual information.I. IntroductionTYPICALLY , bit error rate (BER) charts of iterativedecoding schemes can be divided into three reg ions:1. the region of low Eb/N0with neglig ible iterative BERreduction, 2. the turb o cliff region (also referred to as“waterfall”–region) with persistent iterative BER reduc-tion over many iterations, and 3. the BER floor region formoderate to high Eb/N0in which a rather low BER can bereached after just a few num ber of iterations. While goodanalytical bounding techniques have been found for mod-erate to high Eb/N0, e. g. [1], [2], the turbo cliff has notyet attracted a comparable amount of interest, owing tothe limitations of the commonly used bounding techniquesin that region. This paper proposes extrinsic informationtransfer characteristics based on mutual information to de-scribe the flow of extrinsic information through the softin/soft out constituent decoders. This proves to be par-ticularly useful in the region of low Eb/N0. A decodingtrajectory visualizes the exchange of extrinsic informationbetween constituent decoders in the Extrinsic InformationTransfer Chart (EXIT chart).In [3], [4] the EXIT chart was introduced as a novel toolto provide design guidelines for mappings and signal con-stellations of an iterative demapping and decoding scheme(IDEM). IDEM can be regarded as a serial concatenationof two codes (SCC). In this paper the method of [3], [4]S. ten Brink is with the Institute of Telecommunications, Room2.333, Dep. 0408, University of Stuttgart, Pfaffenwaldring 47, 70569Stuttgart, Germany. Tel: +49 711 685 7937, Fax: +49 711 685 7929,E-mail: [email protected] . The paper was presented inpart at the 3rd IEEE/ITG Symposium on Source and Channel Cod-ing, Munich, Germany, January 2000. This work has been performedin a joint project with Bell Laboratories, Lucent Technologies.is applied to iterative decoding of parallel c oncatenatedco des (PCC). We do not claim to present a rigorous proofof stability and convergence of iterative decoding; however,simulation results suggest that the EXIT chart predicts thebest possible convergence behavior of the iterative decoderfor large interleaving depth.The paper is organized as follows: Section II introducesextrinsic information transfer characteristics for the con-stituent decoders. Section III explains the EXIT chart as anovel description of the iterative deco der, complementaryto BER charts. The applicability to other than Gaussianchannels is shown in Section IV for the case of a Rayleighchannel. Co de search results based on the EXIT chart tech-nique are presented in Section V yielding new constituentcodes which are optimized with respect to the turbo cliffposition. Finally, Section VI render s some conclusions.II. Extrinsic Transfer CharacteristicsA. Iter ative Decoder for Parallel Concatenated CodesThe iterative decoder for PCC is shown in Fig. 1.For each iteration, the first constituent decoder (BCJR–algorithm [5], [6]) takes channel observations Z1on thesystematic (information) bits i and respective parity bitsp1and outputs soft values D1. The extrinsic informationon the systematic bits E1= D1−A1−Z1is passed throughthe bit interleaver to become the a priori input A2of thesecond decoder. The second decoder takes the permutedchannel observations Z2on the systematic bits i and re-spective parity bits p2and feeds back extrinsic informationE2= D2−A2−Z2which becomes the a priori knowledgeA1of the first deco der. The variables Z1, A1, D1, E1, Z2,A2, D2and E2denote log–likelihoo d ratios (L–values [7]).For the received discrete–time signal z = x + n from theAWGN–channel, the conditional probability density func-tion (PDF) writes asp (z |X = x )=e−(z−x)22σ2n√2πσn. (1)The binary rando m variable X denotes the transmittedbits with realizations x ∈{±1}; for brevity of notation,we will not distinguish between X and x in the following(only where needed for clar ification). The correspondingL–values Z are calculated asZ =lnp (z |x =+1)p (z |x = −1)(2)which can be simplified toZ =2σ2n· z. (3)TEN BRINK: CONVERGENCE BEHAVIOR OF ITERATIVELY DECODED PARALLEL CONCATENATED CODES 1011stBCJRDecoderΠΠ-12ndBCJRDecoderE1A2E2A1Z2Z1MUXMUXΠDecodingresultInterleaverDeinterleaverD2p1p2iD1Fig. 1. Iterative decoder for parallel concatenated codes.The variable n is Gaussian distributed with mean zero andvariance σ2n= N0/2 (double–sided noise power spectraldensity). Note that Z can also be formulated asZ = µZ· x + nZ(4)withµZ=σ2Z2(5)and nZbeing Gaussian distributed with mean zero andvariance σ2Z=4/σ2n. This decomposition will turn outto be useful for modeling a priori knowledge in the nextsub–section.The par allel decoder of Fig. 1 is a symmetric arrange-ment: The situation for the second decoder with respectto Z2, A2, E2is essentially the same a s for Z1, A1,E1. Long sequence lengths make sure that tail effects(open/terminated trellises of convolutional codes) can b eneglected. Hence, it is sufficient to focus on the first de-coder for the remainder of Section II. To simplify notationthe decoder index “1” is omitted in the following.B. Transfer Characteristics of Constituent DecodersThe idea is to predict the behavior o f the