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:
Invited Speakers ( all confirmed):
Alexei Ashikhmin (Bell-Labs)— aea@research.bell-labs.com
Alexander Barg (U Maryland)— abarg@ieee.org
Vladimir Chernyak (Wayne State U.) — chernyak@chem.wayne.edu
Yoshiyuki
Kabashima (Tokyo Tech) — kaba@dis.titech.ac.jp
Ljupco Kocarev (UCSD)— lkocarev@ucsd.edu
Ralph Koetter (UIUC)— koetter@csl.uiuc.edu
Marc Mezard (Orsay, Paris)
— mezard@lptms.u-psud.fr
Olgica
Milenkovic (Boulder) — olgica.milenkovic@colorado.edu
Andrea
Montanari (ENS, Paris) — montanar@lpt.ens.fr
Tom
Richardson (Flarion, NJ) — richardson@flarion.com
David Saad
(Aston, Birmingham) — saadd@aston.ac.uk
M. Amin Shokrollahi (EPFL, Switzerland) — amin@shokrollahi.com
Paul H. Siegel (UCSD) — psiegel@ucsd.edu
Nicolas
Sourlas (ENS, Paris) — sourlas@lpt.ens.fr
Martin Wainwright (Berkeley) — wainwrig@eecs.berkeley.edu
Jonathan S. Yedidia
(Mitsubishi) — yedidia@merl.com
Local Participants:
This Workshop is Open to the Interested Public.
Administrative coordinator:
Roderick
Garcia, (505) 667-1444