IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 46, NO. 1, JANUARY 2000 9The Geometry of Turbo-Decoding DynamicsTom RichardsonAbstract—The spectacular performance offered by turbo codessparked intense interest in them. A considerable amount of re-search has simplified, formalized, and extended the ideas inherentin the original turbo code construction. Nevertheless, the natureof the relatively simple ad hoc turbo-decoding algorithm has re-mained something of a mystery.We present a geometric interpretation of the turbo-decoding al-gorithm. The geometric perspective clearly indicates the relation-ship between turbo-decoding and maximum-likelihood decoding.Analysis of the geometry leads to new results concerning existenceof fixed points, conditions for uniqueness, conditions for stability,and proximity to maximum-likelihood decoding.Index Terms—Decoding, geometry, maximum likelihood, turbocodes.I. INTRODUCTIONSINCE their appearance in 1993 [3], turbo codes have beenwidelylaudedas one of the most significantrecentadvancesin coding. Turbo codes offer near-optimal performance whilerequiring only moderate complexity. The structure of the codespresented in [3] and the reasons for their performance lie outsidethe conventional wisdom of coding theory. Nevertheless, thestructure of the codes is now fairly well understood [2] and it isfairly well understood why the codes would perform well undermaximum-likelihood decoding. Maximum-likelihood decodingof turbo codes is, however, prohibitively complex and the mod-erate complexity of turbo codes is due to the ad hoc decodingalgorithm presented in [3]. Although “turbo codes” is by now anentrenched term, it is really a misnomersince“turbo” refers onlyto the ad hoc turbo-decoding algorithm. The turbo-decodingalgorithm also appeared in [5] although, as applied to differentcodes, with less spectacular results than those presented in [3].The performance results in [3] arise from a synergy betweenthe decoding algorithm and the codes used there. These resultssparked intense interest in turbo codes and in turbo-decodinggenerally. A considerable amount of research has simplified,formalized, and extended the ideas inherent in the original turbocode construction. Nevertheless, the nature of the relativelysimple turbo-decoding algorithm has remained something of amystery. The turbo-decoding algorithm has been recognized asan instance of a general algorithm for propagating informationon graphs known as “belief propagation” [7]. In the case oflow-density parity-check codes, the algorithm was proposed in1961 [4]. Belief propagation is known to be correct on trees [7].For both turbo codes and low-density parity-check codes theManuscript received December 23, 1997; revised September 3, 1999.The author is with Bell Laboratories, Lucent Technologies, Murray Hill, NJ07974 USA.Communicated by F. R. Kschischang, Associate Editor for Coding Theory.Publisher Item Identifier S 0018-9448(00)00360-6.correspondinggraphisnot atree.Fromthisperspective, theworkin this paper can be said to be directed toward obtaining a globalqualitative understanding of the effect of loops in the graph.It appears that the turbo-decoding algorithm performs almostas well as maximum-likelihood decoding when applied toturbo codes. (Throughout the paper we use the terms “max-imum-likelihood decoding” and “turbo decoding” to refer to thesoft-decoding process which outputs (estimates of) posteriorlikelihoods for each bit. When we wish to refer to the impliedbit value we will speak of the decoding “decision.”) Thereare known codes where turbo-decoding is markedly inferiorto maximum-likelihood decoding [9]. The largest gap in thetheory of turbo codes is the lack of understanding of turbodecoding in general and its relationship to maximum-likelihooddecoding in particular.In this paper we interpret turbo decoding in a geometric set-ting as a dynamical system. The goal is to obtain general in-formation concerning the convergence and stability of turbo de-coding and its relationship to maximum-likelihood decoding.The geometric interpretation is a natural one. In particular, itimmediately indicates how turbo decoding is related to max-imum-likelihood decoding, at least when the two are close. Theinterpretation applies to the decoding algorithm generally, i.e.,it is not limited to turbo codes. Analysis of the geometry leads tovarious new results concerning turbo decoding. For simplicitywe concentrate on the case of two parallel concatenated codes,although these need not be recursive convolutional codes. Manyof the results generalize in various ways: to multiple parallelcodes, for example, and, with some effort, to serially concate-nated codes. Most of the results are qualitative and concern fixedpoints of turbo decoding. In particular, we establish the exis-tence of fixed points to the turbo-decoding algorithm. We alsoindicate conditions for uniqueness of fixed points and condi-tions for stability of fixed points. Furthermore, we consider theproximity of fixed-point solutions to maximum-likelihood de-coding.The geometric interpretation indicates another interpretationin which the turbo-decoding algorithm appears as an iterativealgorithm aimed at solving a system ofequations in un-knowns, whereis the number of bits in the data sequence.If the turbo-decoding algorithm converges, then the limit pointgives rise to a solution to these equations. Conversely, solutionsto these equations provide fixed points of turbo decoding.The system of equations which turbo decoding attempts tosolve captures the underlying geometry in analytical form. Byconsidering the algorithm as a purely geometric one, abstractingaway from decoding, we are able to obtain several insights thatthen guide our analysis of the equations.A key object in decoding is the posterior density on the spaceof input sequences arising from the observation of the codeword0018–9448/00$10.00 © 2000 IEEE10 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 46, NO. 1, JANUARY 2000after it has been passed through a channel. The geometry wefocus on is the geometry of densities onthe -dimensionalhypercube. Within the space of densities, a special role will beplayed by the subset of “product densities” and sets of densitiessharing common bit-wise marginal distributions. The geometryof these subsets within the larger space is the dominant themeof this paper.In Section II, we outline a turbo encoder and decoder in an ab-stract manner,