RBP algorithm for lossy compression in reduced, ultrasparse GF(q) codes

AttachmentSize
gf-rbp.tgz24.36 KB

This code implements a novel data compression technique for binary symmetric sources based on the cavity method over GF(q), the Galois Field of order q. 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(q) 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 O(d n q log q) per iteration, where d is the average degree of the check nodes and n 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[1][2].


References

  1. Braunstein A, Kayhan F, Zecchina R. Efficient data compression from statistical physics of codes over finite fields. Phys. Rev. E. 2011;84:051111.
  2. Braunstein A, Kayhan F, Zecchina R. Efficient LDPC Codes over GF(q) for Lossy Data Compression. In: IEEE International Symposium on Information Theory, 2009. ISIT 2009. Seul, Korea; 2009.