2005/08/30 by S. Ciliberti, Ciliberti, S., M. Mezard +5 · 1 citation
Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.48550/arxiv.cond-mat/0508723
13 pages, European Conference on Complex Systems, Paris (Nov 2005)
arxiv created 2005/08/30 · openalex publication_date 2005/08/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.