TDA Progress Report 42-127 November 15, 1996A Soft-Input Soft-Output Maximum A Posteriori(MAP) Module to Decode Parallel andSerial Concatenated CodesS. Benedetto,aD. Divsalar,bG. Montorsi,aand F. PollarabConcatenated coding schemes with interleavers consist of a combination of twosimple constituent encoders and an interleaver. The parallel concatenation knownas “turbo code” has been shown to yield remarkable coding gains close to theoreticallimits, yet admitting a relatively simple iterative decoding technique. The recentlyproposed serial concatenation of interleaved codes may offer performance superiorto that of turbo codes. In both coding schemes, the core of the iterative decodingstructure is a soft-input soft-output (SISO) module. In this article, we describethe SISO module in a form that continuously updates the maximum a posteriori(MAP) probabilities of input and output code symbols and show how to embedit into iterative decoders for parallel and serially concatenated codes. Results arefocused on codes yielding very high coding gain for space applications.I. IntroductionConcatenated coding schemes have been studied by Forney [1] as a class of codes whose probabilityof error decreased exponentially at rates less than capacity, while decoding complexity increased onlyalgebraically. Initially motivated only by theoretical research interests, concatenated codes have sincethen evolved as a standard for those applications where very high coding gains are needed, such as(deep-)space applications.The recent proposal of “turbo codes” [2], with their astonishing performance close to the theoreticalShannon capacity limits, has once again shown the great potential of coding schemes formed by twoor more codes working in a concurrent way. Turbo codes are parallel concatenated convolutional codes(PCCCs) in which the information bits are first encoded by a recursive systematic convolutional codeand then, after passing through an interleaver, are encoded by a second systematic convolutional encoder.The code sequences are formed by the information bits, followed by the parity check bits generated byboth encoders. Using the same ingredients, namely convolutional encoders and interleavers, seriallyconcatenated convolutional codes (SCCCs) have been shown to yield performance comparable, and insome cases superior, to turbo codes [5].aPolitecnico di Torino, Torino, Italy.bCommunications Systems and Research Section.1Both concatenated coding schemes admit a suboptimum decoding process based on the iterations of themaximum a posteriori (MAP) algorithm [12] applied to each constituent code. The purpose of this articleis to describe a soft-input soft-output module (denoted by SISO) that implements the MAP algorithm inits basic form, the extension of it to additive MAP (log-MAP), which is indeed a dual-generalized Viterbialgorithm with correction,1and finally extension to the continuous decoding of PCCC and SCCC. Asexamples of applications, we will show the results obtained by decoding two low-rate codes, with veryhigh coding gain, aimed at deep-space applications.II. Iterative Decoding of Parallel and Serial Concatenated CodesIn this section, we show the block diagram of parallel and serially concatenated codes, together withtheir iterative decoders. It is not within the scope of this article to describe and analyze the decodingalgorithms. For them, the reader is directed to [2,4,6,7] (for PCCC) and [3,5,8] (for SCCC). Rather,we aim at showing that both iterative decoding algorithms need a particular module, named soft-input,soft-output (SISO), which implements operations strictly related to the MAP algorithm, and which willbe analyzed in detail in the next section.A. Parallel Concatenated CodesThe block diagram of a PCCC is shown in Fig. 1 (the same construction also applies to block codes).In the figure, a rate 1/3 PCCC is obtained using two rate 1/2 constituent codes (CCs) and an interleaver.For each input information bit, the codeword sent to the channel is formed by the input bit, followed bythe parity check bits generated by the two encoders. In Fig. 1, the block diagram of the iterative decoderis also shown. It is based on two modules denoted by “SISO,” one for each encoder, an interleaver, and adeinterleaver performing the inverse permutation with respect to the interleaver. The input and outputreliabilities for each SISO module in Fig. 1 are described in Section V.The SISO module is a four-port device, with two inputs and two outputs. A detailed description of itsoperations is deferred to the next section. Here, it suffices to say that it accepts as inputs the probabilitydistributions of the information and code symbols labeling the edges of the code trellis, and forms asoutputs an update of these distributions based upon the code constraints. It can be seen from Fig. 1 thatthe updated probabilities of the code symbols are never used by the decoding algorithm.B. Serially Concatenated CodesThe block diagram of a SCCC is shown in Fig. 2 (the same construction also applies to block codes).In the figure, a rate 1/3 SCCC is obtained using as an outer encoder a rate 1/2 encoder, and as aninner encoder a rate 2/3 encoder. An interleaver permutes the output codewords of the outer code beforepassing them to the inner code. In Fig. 2, the block diagram of the iterative decoder is also shown. It isbased on two modules denoted by “SISO,” one for each encoder, an interleaver, and a deinterleaver.The SISO module is the same as described before. In this case, though, both updated probabilities ofthe input and code symbols are used in the decoding procedure. The input and output reliabilities foreach SISO module in Fig. 2 are described in Section V.C. Soft-Output algorithmsThe SISO module is based on MAP algorithms. MAP algorithms have been known since theearly seventies [10–14]. The algorithms in [11–14] perform both forward and backward recursionsand, thus, require that the whole sequence be received before starting the decoding operations. As a1A. J. Viterbi, “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes,”submitted to the JSAC issue on “Concatenated Coding Techniques and Iterative Decoding: Sailing Toward ChannelCapacity.”2¥ENCODER1RATE = 1/2TO CHANNELNOT TRANSMITEDENCODER2RATE = 1/2TO CHANNEL (c;O)TO CHANNELNOT USED (c;I) (u;O) (u;I)FROMDEMODDECISIONSISO2SISO1 (c;O) (u;O)NOT USED (c;I) (u;I)FROMDEMOD(a)(b)–1Fig. 1.