Search Results

Reliable transmission of information through noisy channels plays a vital role in modern society. Some aspects of this problem have close formal similarities to the theory of spin glasses. Noise in the transmission channel can be related to random interactions in spin glasses and the bit sequence representing information corresponds to the Ising spin configuration. The replica method serves as a powerful tool of analysis, and TAP-like equations can be used as a practical implementation of the algorithm to infer the original message. The gauge theory also provides an interesting point of view. This chapter introduces these problems.

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.

Low-density parity-check (LDPC) codes are among the most efficient error correcting codes in use. This chapter introduces an important family of LDPC ensembles, based on random factor graphs, and studies some of their basic properties. It focuses on performances under optimal decoding, when no constraint is imposed on the computational complexity of the decoding procedure. Bounds in their performances are derived through an analysis of the geometric properties of their codebook. In particular, it shows that appropriately chosen LDPC ensembles allow for communication reliably at rates close to Shannon's capacity.

This chapter introduces some of the basic concepts of information theory, as well as the definitions and notations of probability theory that are used throughout the book. It defines the fundamental notions of entropy, relative entropy, and mutual information. It also presents the main questions of information theory: data compression and data transmission. Finally, it offers a brief introduction to error correcting codes and Shannon's theory.

This chapter describes a combined maximum entropy/log-likelihood gain approach to crystal structure determination from powder diffraction data. The approach is described step-by-step, with a particular emphasis on the optimal selection of basis set reflections and the calculation of the log likelihood. The active use of likelihood to partition the intensities of overlapping reflections is described in some detail and is illustrated with an example of phasing a framework structure. The use of error correcting codes as a means of controlling the rapid increase in the number of phase sets that arises from full factorial permutation is addressed.

This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.