Efficient data compression from statistical physics of codes over finite fields

Details Efficient data compression from statistical physics of codes over finite fields Efficient data compression from statistical physics of codes over finite fields

2011-08-31

arxiv.org/abs/1108.6239v2

Computer Science

Information Theory

10 pages, 4 figures

Scientific paper

In this paper we discuss a novel data compression technique for binary symmetric sources based on the cavity method over a Galois Field of order q (GF(q)). We present a scheme of low complexity and near optimal empirical performance. The compression step is based on a reduction of sparse low density parity check codes over GF(q) and is done through the so called reinforced belief-propagation equations. These reduced codes appear to have a non-trivial 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.

Affiliated with

Also associated with

No associations

Rating

Efficient data compression from statistical physics of codes over finite fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient data compression from statistical physics of codes over finite fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient data compression from statistical physics of codes over finite fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-625796