Information theory has been closely related to concepts of statistical mechanics, almost from its inception. In recent years this connection has been extended to encompass: error correcting codes based on random graphs on one hand, and spin glasses on the other hand. In a nutshell, these systems display phase transitions of similar nature.
Phase transitions are an ubiquitous natural phenomenon and occur in almost all physical situations involving a macroscopic number of interacting degrees of freedom. The most well known ones are displayed in the phase diagram of ordinary matter (left picture). The system undergoes sudden transitions between liquid and solid or liquid and vapor phases when the control parameters such as pressure and/or temperature cross the solid lines. Simple but very important models which capture essential features of phase transitions belong to the class of Ising spin systems (right picture). Binary variables (also called spins) taking values +1/-1, and representing the presence/absence of a water molecule are attached to the red circles of the lattice. The blue squares indicate that there is an energy cost depending on the pair (+1,+1) (+1,-1) (-1,+1) (-1,-1) joined by the edge. Each configuration of spins on the lattice is assigned a probability weight depending on the total energy cost. The main qualitative features of the water-vapor phase transition are captured by the typical configurations of the Gibbs probability weight.
 |
 |
Modern error correcting codes are also based on probabilistic graphical models. For example, in Low Density Parity Check Codes (LDPC) the code words are strings of bits (1 and 0) attached to the red nodes, satisfying a set of linear constraints depicted by the graph below.
 |
All the bits that are connected to a square blue node (a parity check) sum to zero modulo 2. The code words are sent through a communication channel which flips each bit with a certain probability p (the noise level). As such, the code bits can be viewed as set of interacting spins and the communication system can be modelled by a probabilistic graphical model belonging to the Ising class.
The system displays a phase transition between a phase p<p_c where it is in principle possible to clean the errors and reconstruct perfectly the original code word; and a phase p>p_c where this is impossible. However for p<p_c it is not always possible to perform the error correction by an efficient algorithm. It turns out that a fundamental efficient algorithm, called belief propagation and related to mean field methods of statistical physics, can efficiently correct the errors for p<p_d. These phase transitions share deep similarities with the ones occurring in spin glasses which are spin systems based on random Gibbs weights. Indeed, the probabilistic models for graphical coding schemes have quenched randomness coming from the underlying graph code as well as the channel output realizations.
 |