Overview

The publication of Shannon's historical paper ^[1] ushered in the era of reliable information transmission. The fact that Shannon's bounds could only be approached asymptotically, however, was conceived, until recently, as an indication of the unattainability of these bounds. Also, the proof of the channel coding theorem being based on a random coding argument led the coding theorists to believe that a good code (in the sense of achieving the channel capacity), should lack any structure ^[2] and, therefore, be almost impossible to decode. In the early 1990s, major advances in the area of digital hardware design, had made the implementation of some of the most complex functions feasible. These advances in digital electronics prompted some coding theorists to revisit the concepts of complexity and randomness ^[3] and others to look for practical decoding schemes for capacity achieving codes ^[4], ^[5]. However, it was not until the invention of Turbo Codes ^[6] and the demonstration of their amazing performance that the coding community's perception of randomness, asymptotic and complexity changed ^[1] and an intense research activity on iterative decoding of concatenated codes was initiated ^[7], ^[83], ^[9], ^[10], ^[11], ^[12], ^[13], ^[14].

An interesting aspect of Turbo codes is that their decoder was designed prior to their encoder ^[16], ^[17]. Earlier codes such as BCH and Reed-Solomon codes, were first developed based on mathematical (algebraic) principles, generally,...