PI-1510: Convergence of Turbo Algorithms for Systems Defined by Local
Constraints
Eric Fabre
http://www.irisa.fr/bibli/publi/pi/2003/1510/1510.html
36 pages - juin 2003

Abstract
We consider a general notion of system, composed of a set of variables
and a set of legal (possibly random) ``behaviors'' on these variables.
Such systems are provided with a composition law, which allows to build
large models out of elementary components. This framework captures large
constraint systems, Markov random fields (in particular graphical models
of powerful error correcting codes), but also some aspects of
distributed dynamic systems. Many problems with these models can be
expressed under the form of a ``reduction'' operation : i.e. compute the
influence of the whole compound system on a given component. For example
compute the posterior distribution of a given bit, in a codeword, given
all available measurements on that codeword at the output of a
channel. The reduction of a system to one or each of its components is
generally NP hard, but good approximations can be obtained, which take
advantage of the so-called interaction graph of the compound system. We
investigate properties of one of them, known as the turbo procedure,
initially derived for error correcting codes. In particular, we show
that turbo algorithms are possible as soon as some axioms on composition
and reduction are satisfied. Convergence cannot be proved in general,
except for constraint systems, which can be considered as the simplest
family of compound systems. Finally, in our axiomatic framework, we
study the structure of approximately reduced components obtained at a
stationary point of the turbo procedure, which extends results
previously published by Weiss et al.

Résumé
On considère une classe générale de systèmes, définis par un ensemble de
variables, et par des ``comportements'' permis sur ces variables
(éventuellement aléatoires). Ces systèmes sont munis d'une loi de
composition qui permet d'obtenir de grands modèles à partir de
composants élémentaires. Ce cadre permet de modéliser les systèmes de
contraintes, les champs de Markov (et en particulier des modèles
graphiques de codes correcteurs d'erreurs), de même que certains aspects
des systèmes dynamiques distribués. De nombreux traitements associés à
ces modèles peuvent formuler sous la forme d'une opération de réduction
; cela consiste à calculer l'influence d'un (gros) système composite sur
l'un (ou chacun) de ses composants. Par exemple, pour les codes
correcteurs d'erreurs, cela revient à calculer la distribution a
posteriori de chaque bit du mot de code connaissant toutes les mesures
reçues sur les bits de ce mot en sortie de canal. Le problème de
réduction est en général de complexité NP, mais on peut en donner de
bonnes solutions approchées, en utilisant la structure d'interaction
entre les composants. Nous nous intéressons à l'une d'entre elles, la
procédure ``turbo'', proposée à l'origine pour les codes correcteurs
(les turbo-codes). Nous montrons que ces algorithmes turbo peuvent être
mis en oeuvre dès qu'un ensemble d'axiomes sur la composition et la
réduction de systèmes sont vérifiés. La convergence n'est pas
démontrable en général, mais elle l'est pour les systèmes de
contraintes, que l'on peut voir comme la classe la plus simple de
systèmes composites. Nous nous intéressons ensuite aux propriétés des
points fixes des algorithmes turbo, ce qui permet d'étendre des
résultats présentés par Weiss et al.

Keywords: Turbo algorithm, fix point, graphical model, bayesian network,
constraint system, estimation, error correcting code

Mots clefs: Algorithme turbo, point fixe, modèle graphique, réseau
bayésien, système de contraintes, estimation, code correcteur d'erreurs