Efficient data compression from statistical physics of codes over finite fields

A. Braunstein, F. Kayhan, and R. Zecchina
Phys. Rev. E 84, 051111 – Published 14 November 2011

Abstract

In this paper we discuss 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(dnqlog2q) 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 1 September 2011

DOI:https://doi.org/10.1103/PhysRevE.84.051111

©2011 American Physical Society

Authors & Affiliations

A. Braunstein1,2,3, F. Kayhan4, and R. Zecchina1,2,3

  • 1Dipartimento di Fisica and Center for Computational Sciences, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy
  • 2HuGeF, Via Nizza 52, I-10126 Torino, Italy
  • 3Collegio Carlo Alberto, Via Real Collegio 30, I-10024 Moncalieri, Italy
  • 4Dipartimento di Elettronica, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 84, Iss. 5 — November 2011

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×