Efficient data compression from statistical physics of codes over finite fields

Il contenuto (Full text) non è disponibile all'interno di questo archivio. Spedisci una richiesta all'autore per una copia del documento
Tipo di pubblicazione: Articolo su rivista
Tipologia MIUR: Contributo su Rivista > Articolo in rivista
Titolo: Efficient data compression from statistical physics of codes over finite fields
Autori: Braunstein A.; Kayhan F.; Zecchina R.
Autori di ateneo:
Titolo del periodico: PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS
Tipo di referee: Tipo non specificato
Editore: APS
Volume: 84
Intervallo pagine: 051111-
Numero di pagine: 7
ISSN: 1539-3755
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
Data: 2011
Status: Pubblicato
Lingua della pubblicazione: Inglese
Parole chiave: lossy compression, statistical physics, cavity method
Dipartimenti (originale): DIFIS - Fisica
DELEN - Dipartimento di Elettronica
Dipartimenti: DISAT - Dipartimento Scienza Applicata e Tecnologia
URL correlate:
Area disciplinare: Area 02 - Scienze fisiche > FISICA TEORICA, MODELLI E METODI MATEMATICI
Data di deposito: 15 Nov 2011 17:22
Data ultima modifica (IRIS): 20 Apr 2016 12:17:26
Data inserimento (PORTO): 22 Apr 2016 03:34
Numero Identificativo (DOI): 10.1103/PhysRevE.84.051111
Permalink: http://porto.polito.it/id/eprint/2460654
Link resolver URL: Link resolver link
Citazioni:

Il campo presenta il numero di citazioni presenti sulle banche dati Scopus e Web of Science e permette di accedere ai relativi record. Visualizza inoltre il link al record presente su Google Scholar.

Possono verificarsi discrepanze rispetto ai dati presenti sulle banche dati per i seguenti motivi:

  • Differenze tra i dati riportati su IRIS e quelli presenti nelle banche dati.
  • Il numero di citazioni riportate su PORTO viene estratto mensilmente. Il dato citazionale presente sulle singole banche dati è aggiornato in tempo reale
  • Il numero di citazioni per WoS viene calcolato sulla base delle collezioni in abbonamento (Science citation index Expanded e Conference Proceedings Citation Index)

Per informazioni o segnalazioni contattare scrivia/porto

+
-

Azioni (richiesto il login)

Visualizza il documento (riservato amministratori) Visualizza il documento (riservato amministratori)