Conference logo

Applications of Statistical Physics to Coding Theory
Santa Fe, New Mexico
Jan 10 — Jan 12, 2005
Organizing committee: M. Chertkov (T-13), I. Gabitov (T-7 & UA, Tucson), B. Vasic (UA, Tucson)

      The last several years have witnessed major theoretical advances in communications and coding theory resulting in a new coding concept called codes on graphs. Codes on graphs, and specially their prime examples, low-density parity check (LDPC) codes and turbo codes is a research area of great current interest. One of the key results regarding codes on graphs is that iterative decoding algorithms developed for these codes are instances of probability propagation algorithms that have been independently developed in the expert systems literature. When operating on a graphical model of a code, belief propagation algorithms show an unprecedented ability to correct errors that occur due to noise and impairments encountered during the transmission/storage of information. Moreover, it is known that codes on graphs can approach optimal theoretical limits of reliable transfer of information. The theory of codes on graphs has not only improved the error performance of communications systems, but it has also opened new research avenues for investigating code constructions and alternative sub-optimal decoding schemes.
      Despite the fact that in recent years there has been a great deal of research in both code construction and decoding algorithms, codes on graphs have not yet found an application in communication systems in which very low bit error rates are required, such as fiber optics communications systems. One of the reasons (if not a main reason) is that no analytical characterization of the bit error rate (BER) performance is known for these codes under iterative decoding.
      Recently, the relationship between codes on graphs and spin models was discovered and described in a series of papers. Following this relation, it has been shown that turbo codes correspond to “coupled spin chains”, while LDPC represent “spin models on diluted graphs”. Using the spin model approach it is possible to re-derive many known results regarding conditions for error-free communication with iterative decoding, since error-thresholds correspond to phase transitions in spin models. Moreover, it seems that the theory of spin glasses can be used to determine if an iterative decoding algorithm can reach the threshold of optimum decoding in a finite number of iterations, or if there exists a lower dynamical threshold where the decoding algorithm gets trapped in a locally stable state. Answering this question would resolve issues regarding the decoding complexity of LDPC codes, BER characterization at very low error probabilities, the existence of error floor, etc.
      For emerging new coding paradigms to benefit from the achievements made in statistical physics, and for physics to benefit from recent major theoretical advances in coding theory, it is necessary to identify principles and methods unique to both disciplines despite their terminological difference. We believe that an effort to better understand and mathematically formulate them will offer new directions in information and coding theory as well as in statistical physics. It will also motivate revisiting the existing communications system models and coding and detection methodologies, which, in turn, can improve traditional systems as well.
      This workshop will bring together experts who work on coding theory and statistical physics from a variety of viewpoints. In order to facilitate a synthesis of perspectives, the workshop will be organized around half-day sessions followed by active discussions. The workshop will be an excellent venue with outstanding speakers and high-quality technical content.
      The primary topics of inquiry will be:

  • Recent advances in coding
  • Forward Error Correction as Statistical Mechanics on a graph
  • Low-density-parity check codes
  • Evaluation of Bit-Error-Rate and Frame-Error-Rate on a finite graph
  • Modern applications for coding theory: optics communication, wireless, magnetic recording
  • Foreword Error Correction and Physics of Networks
  • Foreword Error Correction and Combinatorial optmization
  • Invited Speakers ( all confirmed):

    Alexei Ashikhmin (Bell-Labs)—
    Alexander Barg (U Maryland)—
    Vladimir Chernyak (Wayne State U.) —
    Yoshiyuki Kabashima (Tokyo Tech) —
    Ljupco Kocarev (UCSD)—
    Ralph Koetter (UIUC)—
    Marc Mezard (Orsay, Paris) —
    Olgica Milenkovic (Boulder) —
    Andrea Montanari (ENS, Paris) —
    Tom Richardson (Flarion, NJ) —
    David Saad (Aston, Birmingham) —
    M. Amin Shokrollahi (EPFL, Switzerland) —
    Paul H. Siegel (UCSD) —
    Nicolas Sourlas (ENS, Paris) —
    Martin Wainwright (Berkeley) —
    Jonathan S. Yedidia (Mitsubishi) —

    Local Participants:

    This Workshop is Open to the Interested Public.

    LANL logo Administrative coordinator:
    Roderick Garcia
    , (505) 667-1444