Statistical mechanics of error correcting codes

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama +1 more

Nicolas Sourlas

Nicolas Sourlas

I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. A particular spin-glass model, which is exactly soluble, corresponds to an ideal code, i.e. a code which allows error-free communication if the rate is below channel capacity.

James L. Massey

Yaodong Li, Matthew P. A. Fisher

Random quantum dynamics generates quantum error correcting codes that are robust against observers and errors. Here, the authors describe a simple physical picture of such codes, mapping characteristic code properties to the statistical mechanics of fluctuating ``entanglement domain walls''. The error correcting criterion is understood as a decoupling condition of domain walls, which leads to a universal scaling law of the ``code distance''.

祥介 樺島, YOSHIYUKI KABASHIMA