Efficient LDPC Codes Over GF(q) for Lossy Data Compression

Download Now Free registration required

Executive Summary

In this paper the authors consider the lossy compression of a binary symmetric source. They present a scheme that provides a low complexity lossy compressor with near optimal empirical performance. The proposed scheme is based on b-reduced ultra-sparse LDPC codes over GF(q). Encoding is performed by the Reinforced Belief Propagation algorithm, a variant of Belief Propagation. The computational complexity at the encoder is O(< d > .n.q. log2 q), where < d > is the average degree of the check nodes. For the code ensemble, decoding can be performed iteratively following the inverse steps of the leaf removal algorithm. For a sparse parity-check matrix the number of needed operations is O(n).

  • Format: PDF
  • Size: 132.69 KB