Error-correcting Codes on a Bethe-like Lattice

Part of Advances in Neural Information Processing Systems 13 (NIPS 2000)

Bibtex Metadata Paper


Renato Vicente, David Saad, Yoshiyuki Kabashima


We analyze Gallager codes by employing a simple mean-field approxi(cid:173) mation that distorts the model geometry and preserves important interac(cid:173) tions between sites. The method naturally recovers the probability prop(cid:173) agation decoding algorithm as an extremization of a proper free-energy. We find a thermodynamic phase transition that coincides with informa(cid:173) tion theoretical upper-bounds and explain the practical code performance in terms of the free-energy landscape.