Statistical mechanics and capacity-approaching error-correcting codes

DOI10.1016/S0378-4371(01)00439-3MaRDI QIDQ5951415zbMATH OpenFDO

Authors Nicolas Sourlas

Publication date 6 January 2002

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0106570

zbMATH Keywords

capacity approaching codessignal to noise ratiospin glasses

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Linear codes (general theory) (94B05)

Abstract: I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold depends on the particular code, and can be computed analytically in many cases.

Recommendations

• Statistical mechanics and error-correcting codes
• Good error-correcting codes based on very sparse matrices
• Statistical mechanics of low-density parity-check codes
• Statistical Physics of Low Density Parity Check Error Correcting Codes
• The capacity of low-density parity-check codes under message-passing decoding

Cites work

• Efficient encoding of low-density parity-check codes
• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• Statistical mechanics of neural networks. Proceedings of the XIth Sitges conference, Sitges, Barcelona, Spain, 3-7 June, 1990

Cited in

(18)

• Finite-volume corrections to magnetization in the spin-glass phase of the Derrida model
• Statistical mechanics approach to coding theory.
• Statistical mechanics and error-correcting codes
• On the equivalence of Ising models on `small-world' networks and LDPC codes on channels with memory
• Performance of LDPC Decoding Algorithms with a Statistical Physics Theory Approach
• Quantum-mechanical variant of the Thouless-Anderson-Palmer equation for error-correcting codes
• Variational Bayes and a problem of reliable communication. II: Infinite systems
• Chains of mean-field models
• Capacity and zero-error capacity of Ising channels
• Course 10 Two lectures on iterative coding and statistical mechanics
• Renormalization group approach to error-correcting codes
• Statistical mechanics of low-density parity-check codes
• Statistical physics of irregular low-density parity-check codes
• Weight vs. Magnetization Enumerator for Gallager Codes
• Statistical Physics of Low Density Parity Check Error Correcting Codes
• Variational Bayes and a problem of reliable communication. I: Finite systems
• Error-correcting codes and phase transitions
• A large deviation principle for the free energy of random Gibbs measures with application to the REM

This page was built for publication: Statistical mechanics and capacity-approaching error-correcting codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951415)