The Dynamic Phase Transition for Decoding Algorithms

Silvio Franz, Michele Leone, Andrea Montanari, Federico Ricci-Tersenghi

Published 2002-05-02Version 1

The state-of-the-art error correcting codes are based on large random constructions (random graphs, random permutations, ...) and are decoded by linear-time iterative algorithms. Because of these features, they are remarkable examples of diluted mean-field spin glasses, both from the static and from the dynamic points of view. We analyze the behavior of decoding algorithms using the mapping onto statistical-physics models. This allows to understand the intrinsic (i.e. algorithm independent) features of this behavior.