Statistical mechanics of the data compression theorem

Abstract

We analyse the performance of a linear code used for data compression of a Slepian-Wolf type. In our framework, two correlated data are separately compressed into codewords employing Gallager-type codes and cast into a communication network through two independent input terminals. At the output terminal, the received codewords are jointly decoded by a practical algorithm based on the Thouless-Anderson-Palmer approach. Our analysis shows that the achievable rate region presented in the data compression theorem is described as first-order phase transitions among several phases. The typical performance of the practical decoder is also well evaluated by the replica method.