Iterative algorithms for achieving near-ML decoding performance in concatenated coding systems

摘要

Over the last decade, the demand for reliable and high data rate wireless communication has been rapidly growing. The success of turbo codes has led to many applications of concatenated coding to support a reliable transmission at a data rate close to the channel capacity. At the receiver, maximum likelihood (ML) decoding is optimal in the sense of minimizing the frame error rate (FER). It is known that ML decoding is NP-hard for the class of concatenated codes. For turbo codes, the heuristically invented iterative turbo decoding algorithm is able to offer near-ML decoding performance. The idea behind it, i.e., the turbo principle, is therefore extended to cover the whole receiver design in concatenated coding systems. In this thesis, the theoretical relation between ML decoding and iterative turbo decoding is investigated. The obtained results are further applied to establish a systematic framework for deriving approximate ML decoding algorithms in practical concatenated coding systems. First, the ML decoding problem is linked to a constrained Bethe free energy minimization problem commonly studied in statistical physics. More specifically, sufficient conditions on the existence of a deterministic relation between the global optimal solutions of the two problems are derived. On this theoretical basis, the constrained Bethe free energy minimization problem is further interpreted as an approximation to the ML decoding problem that allows for computationally efficient solutions. One effective iterative method to minimize the constrained Bethe free energy is turbo decoding. Second, the Bethe free energy based approximation to the ML decoding problem is extended to obtain an approximate ML decoding algorithm in a system using bit-interleaved turbo-coded modulation and multiple antennas. The resulting algorithm consists of two nested loops. The implementation of such doubly iterative decoding process in practical multiple antenna systems is addressed. In particular, an ant colony optimization (ACO) based scheme is presented for determining the execution order of the inner and outer iterations based on the knowledge of channel statistics. Furthermore, upper bounds on the error probability of ML decoding are analytically derived, providing baselines for validating the capability of the doubly iterative decoding algorithm in achieving near-ML decoding performance. Finally, the ML decoding problem with incomplete channel information is considered. Based on the Bethe free energy approximation, two approximate iterative algorithms are derived for joint channel density estimation and ML decoding. Furthermore, the Bethe free energy approach is shown to provide a link that can connect iterative channel estimation and decoding algorithms in the literature to the ML decoding problem.