Error Correction Coding, 2nd Edition

Chapter 14Turbo Codes

“Tell me how you decode and I'll be able to understand the code.” When you have no particular gift for algebra, … then think about the decoding side before the encoding one. Indeed, for those who are more comfortable with physics than with mathematics, decoding algorithms are more accessible than coding constructions, and help to understand them.

— Claude Berrou [37]

14.1 Introduction

Shannon's channel coding theorem implies strong coding behavior for random codes as the code block length increases, but increasing block length typically implies an exponentially increasing decoding complexity. Sequences of codes with sufficient structure to be easily decoded as the length increases were, until fairly recently, not sufficiently strong to approach the limits implied by Shannon's theorem. However, in 1993, an approach to error‐correction coding was introduced which provided for very long codewords with only (relatively) modest decoding complexity. These codes were termed turbo codes by their inventors [. They have also been termed parallel concatenated codes [. Because the decoding complexity is relatively small for the dimension of the code, very long codes are possible, so that the bounds of Shannon's channel coding theorem become, for all practical purposes, achievable. Codes which can operate within a fraction of a dB of channel capacity are now possible. Since their announcement, turbo codes have generated considerable research enthusiasm leading ...