Abstract
Turbo codes, proposed by Berrou et al. in 1993, have been a very hot topic in coding theory recently. Turbo codes are systematic parallel concatenated convolutional codes whose encoder is formed by two (or more) convolutional encoders, parallel concatenated and joined through by an interleaver which rearranges the information bits with a different order. The information bits and their interleaved version are fed into the first and second convolutional encoder, respectively. This parallel concatenated code consists of the information bits entering the first encoder and the parity check bits of both component encoders. Turbo codes can be decoded iteratively. The turbo decoder consists of two component decoders. Soft values (reliability estimates) of the information bits are delivered iteratively between the two component decoders like a turbo engine. Simulation results have shown that turbo decoding by using iterative decoding schemes can achieve near Shannon-limit error performance. A required E_b/N_0 of 0.7 dB was reported for a bit error rate of 10^{-5} for a rate 1/2 turbo code. Various researches, simulations, and analysis results show that turbo codes could achieve surprisingly low bit error rates at very low signal-to-noise ratios if the size of interleaver is large enough, the permutation by the interleaver is sufficiently random, and the soft-output decoding algorithms used are properly designed. Before the concept of iterative decoding, the Viterbi algorithm (a hard output algorithm) was a good selection as a decoding algorithm for convolutional codes. This is because Viterbi algorithm has much lower complexity but about the same performance compared to other soft-output decoding algorithms. However, after the emergence of iterative decoding and the use of soft-output in this kind decoding scheme, soft-output decoding algorithms such as maximum a posteriori probability (MAP) algorithm, soft-output Viterbi algorithm (SOVA), and some of their modified or approximate versions have drawn much attention due to the dramatic performance when they are applied in iterative decoding. Various kinds of soft-output decoding algorithms are proposed These algorithms vary a lot in performance and computational complexity. The better performance always comes together with higher complexity. Besides, the reliability updating rules for these algorithms differ a lot in appearance such as two-way BCJR algorithms, one-way SOVA, etc. In this thesis, we perform a survey of the existing soft-output decoding algorithms and reveal the relationships among these different algorithms in an intuitive way. Moreover, we give a general representation for all the soft-output decoding algorithms. The general representation extracts path collection and $\max\leftrightarrow\textstyle{\max}^*$ exchange used in reliability computation as key adjustable factors in the design of decoding algorithms. Besides, new algorithms with low complexity and remarkable performance are also discovered. We will also unite these algorithms into a one-way implementation. Soft-output algorithms designed in this way can be transformed between one another with slightly change in path collections or $\max\leftrightarrow\textstyle{\max}^*$ exchange in reliability computation, and hence, any simplification on one algorithm could also be applied to the others. This study also provides a fair comparison among different soft-output decoding algorithms.