S. Ciliberti 1, M. Mezard 1, R. Zecchina 2
Complexus 3 (2006) 58
The use of parity-check gates in information theory has proved to be very efficient. In particular, error correcting codes based on parity checks over low-density graphs show excellent performances. Another basic issue of information theory, namely data compression, can be addressed in a similar way by a kind of dual approach. The theoretical performance of such a Parity Source Coder can attain the optimal limit predicted by the general rate-distortion theory. However, in order to turn this approach into an efficient compression code (with fast encoding/decoding algorithms) one must depart from parity checks and use some general random gates. By taking advantage of analytical approaches from the statistical physics of disordered systems and SP-like message passing algorithms, we construct a compressor based on low-density non-linear gates with a very good theoretical and practical performance.
- 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
CNRS : UMR8626 – Université Paris XI – Paris Sud - 2. ICTP,
ICTP