The random code ensemble
Marc Mézard, Andrea Montanari · 2009
Abstract This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.