Establishment of statistical mechanical methods in information sciences

我们利用统计力学的概念和技术，开发了一个框架来评估各种编码方法，如纠错和压缩编码，以及码分多址多用户通信系统的性能。该框架主要由以下三个方案组成：1.无限长码典型性能的评估方案将给定码看作一种自旋玻璃模型，该方案利用无序系统相变的概念来刻画当码长趋于无穷大时码的典型性能。一种刻画有限长代码非典型行为的方案将大偏差分析的评价方法与统计力学中发展起来的复制方法相结合，该方案使我们能够利用一定的指数来评估客观代码的非典型行为。信任传播典型行为的评估方案作为现代纠错码的标准译码算法，是目前码学研究中占有特殊地位的一种推理算法。我们已经开发了一种方案，使得利用宏观量来表征算法的典型行为成为可能，特别是对于密集连通性的系统。此外，我们还得到了关于统计力学方法性质的几个结果：4.我们发现了一个有限系统大小的模型系统，它可以精确地进行副本数的解析延拓，它提供了关于某种类型的副本对称破缺的起源的完整信息。我们得到了一个似是而非的猜想，即自旋玻璃系统静态分析中已知的De Almeida-Thouless不稳定性条件一般符合平均场模型下信念传播算法不动点的动力学不稳定性条件。

We have developed a framework to evaluate performance of various coding methods such as error correcting and compression codes, and CDMA multiuser communication systems utilizing notions and techniques of statistical mechanics. The developed framework is composed mainly of the following three schemes :1. Scheme for assessing typical performance of codes infinite length Regarding a given code as a kind of spin glass models, this scheme makes it possible to characterize the typical performance of the code as the length of the codes tends to infinity utilizing the concept of phase transition of disordered systems.2. Scheme for characterizing atypical behavior of codes of finite length Combining evaluation methods of large deviation analysis and the replica method that has been developed in statistical mechanics, this scheme enables us to assess atypical behavior of an objective code utilizing a certain exponent.3. Scheme for evaluating typical behavior of belief propagation Belief propagation is an inference algorithm that currently occupies a special status in research of codes as a standard decoding algmithm of modem error correcting codes. We have developed a scheme that makes it possible to characterize typical behavior of the algorithm utilizing macroscopic quantities, in particula4 for systems of dense connectivity. In addition, we have also obtained several results concerning nature of statistical mechanical methods :4. We have discovered a model system of finite system size for which analytical continuation of the replica number can be exactly performed, which provides complete information about the origin of the replica symmetry breaking of a certain type.5. We have gained a plausible conjecture that the condition of the de Almeida-Thouless instability known in static analysis of spin glass systems generally accords with the dynamical instability condition of the fixed point of the belief propagation algorithm in the case of mean field models..