Skip to Main content Skip to Navigation
Reports

Convergence of Turbo Algorithms for Systems Defined by Local Constraints

Eric Fabre 1
1 SIGMA2 - Signal, models, algorithms
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00071723
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:36:35 PM
Last modification on : Thursday, February 11, 2021 - 2:48:05 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:35:09 PM

Identifiers

  • HAL Id : inria-00071723, version 1

Citation

Eric Fabre. Convergence of Turbo Algorithms for Systems Defined by Local Constraints. [Research Report] RR-4860, INRIA. 2003. ⟨inria-00071723⟩

Share

Metrics

Record views

239

Files downloads

286