Relations between random coding exponents and the statistical physics of random codes
Neri Merhav · 2008
The partition function of finite-temperature decoding of a typical random code has three phases in the plane of rate vs. temperature: the ferromagnetic phase, corresponding to correct decoding, the paramagnetic phase, which is dominated by exponentially many incorrect codewords, and the glassy phase, where the system is frozen at minimum energy and dominated by subexponentially many incorrect codewords. We show that the statistical physics of the two latter phases are intimately related to random coding exponents: The exponent of the probability of correct decoding at rates above capacity is directly related to the free energy in the glassy phase, and the exponent associated with the error probability at rates below capacity is strongly related to the free energy in the paramagnetic phase. We derive alternative expressions of these exponents in terms of the corresponding free energies, and make an attempt to obtain insights from them.