Error exponents and statistical mechanics

General description
There are various performance measures for a code. An important one is given by the error exponents, which give the exponential speed of decay of the error probability for transmission rates below the channel capacity. These exponents are known for Shannon’s random code ensemble but beyond that, there still remains many open questions, specially at low rate.

One can look at error exponents from statistical mechanical point of view and relate them to (partial) free energies. A recent extension of the cavity method has allowed to compute such free energies and make analytical predictions for the error exponents. The goal of the project is to first understand the connection between error exponents and statistical mechanical quantities and then investigate various rigorous methods which would validate (at least partialy) the results of the cavity method.

R. Gallager, The random coding bound is tight for the average code, IEEE Trans. Inform. Theory, vol 19 (1973) pp. 244-246

A. Barg, D. Forney, Random codes: Minimum distances and error exponents, IEEE Trans. Inform. Theory vol 48 (2002) pp. 2568-2573

T. Mora, O. Rivoire, Statistical mechanics of error exponents for error-correcting codes, Phys. rev. E vol 74 (2006) pp. 056110:1-25

One among these three is sufficient: basic information theory or basic large deviation theory or basic statistical mechanics.

Dr. Nicolas Macris, LTHC, office inr134, tel 693 8114,