Statistical Mechanics and Error-Correcting Codes

Nicolas Sourlas, Ecole Normale Superior, Paris

I will first show that there is a mathematical correspondence between error-correcting codes and certain mathematical models of disordered spin systems.

I will then show how the recently discovered (or rediscovered) codes which approach Shannon's Chanel Capacity (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, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.

Finally, I will discuss some open problems.

The P/T Colloquium is
typically held each
Thursday, 3:45–5:00 PM.
Refreshments are served
at 3:15 PM.