Solvay Conference on Physics
STATISTICAL MECHANICS APPROACH TO ERROR-CORRECTING CODES
Nicolas Sourlas
Abstract
I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. 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. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. 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, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.