Abstract
In this paper we discuss a novel data compression technique for binary symmetric sources based on the cavity method over GF(), the Galois Field of order . We present a scheme of low complexity and near-optimal empirical performance. The compression step is based on a reduction of a sparse low-density parity-check code over GF() and is done through the so-called reinforced belief-propagation equations. These reduced codes appear to have a nontrivial geometrical modification of the space of codewords, which makes such compression computationally feasible. The computational complexity is per iteration, where is the average degree of the check nodes and is the number of bits. For our code ensemble, decompression can be done in a time linear in the code's length by a simple leaf-removal algorithm.
- Received 1 September 2011
DOI:https://doi.org/10.1103/PhysRevE.84.051111
©2011 American Physical Society