Dynamic phase transition for decoding algorithms

Abstract

The state-of-the-art error correcting codes are based on large random constructions (random graphs, random permutations, etc.) 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 dynamic points of view. We analyze the behavior of decoding algorithms by mapping them onto statistical-physics models. This allows us to understand the intrinsic (i.e., algorithm independent) features of this behavior.