The theoretical capacity of the Parity Source Coder
arXiv:cond-mat/0506652 · doi:10.1088/1742-5468/2005/10/P10003
Abstract
The Parity Source Coder is a protocol for data compression which is based on a set of parity checks organized in a sparse random network. We consider here the case of memoryless unbiased binary sources. We show that the theoretical capacity saturate the Shannon limit at large K. We also find that the first corrections to the leading behavior are exponentially small, so that the behavior at finite K is very close to the optimal one.
Added references, minor changes
References in corpus (8)
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Survey Propagation as local equilibrium equations
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Thouless-Anderson-Palmer Approach for Lossy Compression
- Lossy data compression with random gates
- Statistical mechanics of lossy data compression using a non-monotonic perceptron
- One step RSB scheme for the rate distortion function