Turbo-Gallager Codes: The Emergence of an Intelligent Coding Scheme

Abstract

In 1948, C. Shannon developed fundamental limits on the efficiency of communication over noisy channels. However it is only in 1993 (about half a century later) that Berrou, Glavieux and Thitimajshima developed turbo codes and demonstrated performance close to that limit. Overnight, much of the  algebraic coding techniques of the pre-turbo era were rendered obsolete. Turbo codes employ iterative algorithms and focus on exchange of soft (or probabilistic) information. Shortly after, it was recognised that another class of codes developed by Gallager in 1963 shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Today, both turbo codes and low-density parity-check codes are largely superior to other code families and are being used in an increasing number of modern communication systems including 3G standards, satellite and deep space communications. However, the two codes have certain distinctive characteristics that differentiate them. This work proposes a blend of the two technologies, yielding a code that we nicknamed Turbo-Gallager or TG Code. The code has additional “intelligence” compared to its parents. It detects and corrects the so-called “undetected errors” and recovers from individual decoder failure by making use of a network of decoders.

Keywords: TG codes, message-passing algorithms, low-density parity-check codes, turbo codes, bipartite graphs