| Fifty years after Shannon determined the capacity of memoryless channels, we finally know of practical encoding and decoding algorithms that closely approach this limit. This remarkable feat was first achieved by the invention of turbo codes in 1993 [5]. Since then, turbo codes have essentially revolutionized the coding field and became one of the central research problems in recent years. While there has been a great deal of excellent theoretical work on turbo codes, it is fair to say practice still leads theory by a considerable margin.; This thesis endeavors to fill some of that gap. The main body of the thesis concerns coding theorems for general turbo codes. By “coding theorems” we mean in a classical Shannon sense: for a code ensemble, there exists a code threshold, if the channel noise is below that, the error probability of optimal decoder goes to zero as the code length approaches infinity. We first prove coding theorems for some simple serial turbo code ensembles on the AWGN channel. Then we generalize the results for a broader class of turbo-like codes on any memoryless channel. To closely estimate the noise threshold in the coding theorems, we develop a method based on “typical pairs decoding.” This method is powerful enough to reproduce Shannon's original coding theorems on any memoryless binary-input symmetric channels. Finally we introduce a class of codes of linear encoding and decoding complexity with performance provably close to Shannon's limit.; One main contribution of both theoretical and practical interests in this thesis is the introduction of (regular and irregular) “repeat-accumulate” codes. RA codes are shown to be a serious competitor against turbo codes and LDPC codes. |
