INFORMATION THEORY

General Formula

The most general formula known to date for the capacity of single-user channels is found in

The key to that formula is a new approach to the converse coding theorem not based on Fano's inequality. The general capacity formula finds a particularly simple form in terms of the inf-information rate, a generalization of the conventional mutual information rate.

Capacity-achieving Codes

Finding the input distribution that maximizes mutual information leads, not only to the capacity of the channel, but to engineering insights that tell the designer what good codes should be like. This is due to the folk theorem: The empirical distribution of good codes (those with vanishing error probability and rate approaching capacity) maximizes mutual information. This folk-theorem (dating back to 1948) is formalized and proved in

Channel Capacity per Unit Cost

This work investigates the minimum cost incurred by the transmission of one bit of information through a noisy channel, which is a fundamental figure of merit characterizing the most economical way to communicate reliably. Its main applications are found in some modern communication systems, such as spread-spectrum and optical fiber, where energy, rather than bandwidth, is the main performance-limiting factor. The capacity per unit cost is defined similarly to the conventional capacity, except that the ratio of the logarithm of the number of codewords to their blocklength (rate) is replaced by the ratio of the logarithm of the number of codewords to their cost (rate-per-unit-cost).

shows that the channel capacity per unit cost is the maximum normalized Kullback-Leibler divergence between two conditional output distributions over the input alphabet. This formula holds in the common case where one of the input symbols has zero cost. In contrast to the Shannon theorem, this result admits a constructive proof using tools from large deviations theory. Moreover, in many channels where channel capacity is unknown (including non-Gaussian additive noise channels) that formula results in closed-form expressions for the capacity per unit cost. An interesting connection between information theory and estimation theory is discovered: the minimum energy necessary to transmit 0.721 bits through the channel cannot exceed the minimum conditional variance of an estimate of the input from the output given that the input has zero-energy.

Gaussian Channels

RMS (Root Mean Square) Bandwidth is a useful bandwidth measure for strictly time-limited waveforms introduced by D. Gabor.

shows that Shannon's celebrated capacity formula for the strictly bandlimited channel is equal to the capacity of the bandlimited PAM channel, thereby showing that the laxer frequency domain constraint precisely offsets the Pulse-Amplitude-Modulation time-domain constraint. The above paper also solves for the capacity of the RMS-bandlimited channel without the PAM constraint.

In applications, channels where Gaussian noise is contaminated by another non-Gaussian process arise frequently; this leads to the study of the sensitivity of channel capacity (derivative with respect to the power of the nonGaussian contamination)

shows an explicit formula for the sensitivity of the water-filling formula: it is proportional to the inner product of the contaminating spectral density and the nominal optimal signal-to-noise spectral density. Under mild technical conditions, it is shown that channel sensitivity depends on the contaminating process only through its autocorrelation function.

Exponential Channels

shows that the exponential distribution leads to information theoretic formulas which are strikingly similar to their Gaussian counterparts. In particular, the fundamental saddle-point property satisfied by the input-output mutual information of additive noise power-constrained Gaussian channels finds a complete parallel in the context of mean-constrained exponential-noise channels.

Worst-case Capacity

In channels with input-energy constraints the worst-case capacity of channels with arbitrary noise statistics with given power is well-known, as Gaussian noise minimizes capacity.

finds the worst-case capacity of binary-input channels over all possible noise statistics with given power.

Channels with Side Information

In some communication models of interest, the receiver obtains a noisy uncoded version of the source (in addition to the conventional channel response to the transmitted codeword). The capacity of that channel is found in:

This result gives an application of the fundamental Slepian-Wolf theorem in data transmission. Among the conclusions drawn from that formula is that the capacity of independent parallel binary symmetric channels can be achieved even if only one of them is encoded. The above paper also puts forth an information-theoretic interpretation of the surprisingly good performance of parallel-concatenated codes and in particular, Turbo codes.

The advent of digital communications in radio and television broadcasting poses the following scenario. Historically, a certain bandwidth has been allocated to the analog transmission of an information source. Then, additional channel bandwidth becomes available over which it is possible to transmit digitally-encoded information. This "digital" channel can be used to transmit additional information bandwidth, boost the received fidelity of the original information source, or both. For the sake of compatibility with existing equipment it may not be possible to convert the "analog" channel into a "digital" one, and the analog uncoded transmission of the original source must be preserved.

The above model can be extended to deal with this scenario by allowing a certain distortion level of the decoder output. The Wyner-Ziv rate-distortion function is used to solve for the capacity in this more general scenario in

For a Gaussian bandlimited source and a Gaussian channel, the invariance of the bandwidth-SNR (in dB) product is established, and the optimality of systematic transmission is demonstrated. Bernoulli sources transmitted over binary symmetric channels are also analyzed. It is shown that if nonnegligible bit error rate is tolerated, systematic encoding is strictly suboptimal.

Identification via Channels

A new set of problems arise by a seemingly innocuous modification of the Shannon channel coding problem. Suppose that the recipient of the message is only interest in knowing whether a certain selected message is the true message or not. If that selected message is not known to either the encoder and decoder, the situation is similar to the familiar one except that the decoder is free to declare a list of several messages to be simultaneously "true;" with the recipient simply checking whether the selected message is in the list of not. This problem was formulated by JaJa in 1985 and by Ahlswede and Dueck in a 1989 paper which showed that if the probability of the recipient making an error is arbitrarily small, then the number of messages that can be transmitted is doubly exponential in the blocklength with second-order rate given by the channel capacity. The converse of that result was first obtained in

with a very general strong converse proved later as a straightforward corollary of the direct coding theorem in (see 1.3.1)

The Jan. 1992 paper also formulated the new setting of identification plus transmission. This problem arises in a variety of situations in point-to-multipoint communication, where both the address of the recipient and the message have to be transmitted through a noisy channel. The solution places no assumptions on the allowable communication channels and shows that it is possible to maintain single-user transmission rates as long as the number of bits in the address does not exceed the total number of possible messages.

The only explicit coding construction known to achieve (in conjunction with traditional channel codes) the identification capacity is found in

using a certain concatenation of Reed-Solomon codes.

The strong connection between the identification problem and the problem of finding the maximum cardinality of probability measures separated by a given bound in variational distance is exploited in