The Haroutunian exponent arises in the study of channel reliability functions for both block coding with feedback and fixed-delay coding without feedback. For asymmetric channels, such as the Z-channel, the Haroutunian exponent is strictly larger than the sphere-packing exponent. The spherepacking exponent is believed to be an upper bound for the reliability function in the two aforementioned communication problems, but in attempting to prove this, one gets stuck at the Haroutunian exponent because of entanglements between the channel behavior and the input distribution. In this paper, we present a characteristic of the Haroutunian exponent that differentiates it from the random coding and sphere-packing exponents. We consider the parallel channel, the repeated use of the original discrete memoryless channel independently some number of times. It is well known that the capacity of the parallel channel is L times the capacity of the original channel, and the random coding and sphere-packing exponents of the L-use parallel channel decompose into L times the exponents of the original channel. The main result of this paper is to show that the (appropriately normalized) Haroutunian exponent of the parallel channel asymptotically decomposes to the sphere-packing exponent of the original channel, as opposed to the Haroutunian exponent of the original channel. This fact is then used to prove two results. First, an upper bound for the reliability function for fixed blocklength coding with delayed feedback is proved. This upper bound converges to the sphere-packing exponent as the delay in the feedback path tends to infinity. Second, the reliability function for fixed delay coding without feedback is shown to be upper bounded by the sphere-packing exponent.

In the study of error exponents, the Haroutunian exponent is encountered as an upper bound for several point-to-point communication problems over DMCs including block coding with feedback and fixed-delay coding. For symmetric channels, such as the BSC or BEC, the Haroutunian exponent is equal to the sphere-packing exponent. But for asymmetric channels, such as the Z-channel, the Haroutunian bound is strictly larger than the sphere-packing exponent. It is generally believed that the sphere-packing bound should hold for these problems, even though they are different from the problem of block coding without feedback. The fundamental difficulty in these problems is that the distribution of the input is not known during the error event, and unlike symmetric channels, there is no `universally good' input distribution like the uniform distribution. The result is that a worst-case assumption is made on the input distribution to give the Haroutunian bound, even though the resulting input distribution is useless for communication purposes. In order to make progress on this issue, we study an extended notion of fixed-delay codes called anytime codes, a class of codes that indirectly enforce the property that nontrivial communication is attempted during the error event. For this class of codes, we give a new upper bound to the error exponent that strictly improves on the Haroutunian bound for asymmetric channels. While the new exponent still does not reach sphere-packing, we show that the ratio of the two exponents approaches 1 as the rate approaches capacity for Z-channels. This fact may have an interesting consequence for the viewpoint of maximum achievable rate for a given delay and desired error probability. Additionally, the improved exponent yields a tighter bound for a notion of sufficiency of a channel for control purposes.

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger's 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the `adversary' is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source.

The purpose of this paper is to develop an information-theoretic understanding of the tradeoffs between decoder power, probability of error and decoding throughput. We start by considering the power consumed in the decoder circuit's interconnects, modeled as a lumped capacitor and resistor. After making simplifying assumptions about the decoder circuit, we use a sphere-packing technique to lower bound the decoding error probability for a given number of clock-cycles (or iterations). The analysis can be used to give lower bounds on probability of error versus total decoding power at a fixed decoding throughput.

The issue of whether feedback can significantly increase reliability in the fixed-length channel code setting is further investigated. This paper considers the problem of error exponents for block codes with noiseless, delayed feedback used over discrete memoryless channels (DMCs) - including asymmetric channels with and without zeros in their transition matrix. We show that when output feedback is given to the encoder with a delay of T symbols, the error exponent is upper bounded by Esp(R - O((log T)/T )) + O((log T)/T ), where Espdenotes the sphere-packing exponent.

In computer vision, an active vision source is a sensor that explores its environment in an active way, deciding to investigate parts of the environment in greater depth based on what it currently sees. We study the problem of determining the rate required to compress the output of an active vision source to within a desired fidelity. In order to make the problem analytically tractable, we assume that the environment is memoryless and gain insights into the distinction between compression of passive and active sources. We show that modelling of the sources is crucial by considering two extreme cases: adversarially active sources and helpful active sources. The theory of arbitrarily varying sources is useful for these purposes and we expand on it by allowing the party controlling the variation in the source to have partial or noisy observations of the environment. We give several examples showing that there is a large difference in the rate required to compress active sources that are adversarially modelled and active sources that are jointly optimized with the coding system. The results suggest that when active sources are part of a networked system where rate comes at a premium, large savings can be reaped by jointly optimizing the coding system with the computer vision system.

It is well known that the rate-distortion function for a finite alphabet IID source with distribution p, denoted R(p,D), is uniformly continuous in its arguments. We prove an explicit bound on |R(p,D) - R(q,D)| for distributions p, q in terms of the variational distance parp-qpar1. A simple and elementary proof shows that |R(p,D) - R(q,D)| = O(-parp - qpar1log parp - qpar1), with constants depending on the distortion measure. The uniform continuity of the rate-distortion function has the same behavior as the uniform continuity of entropy in the order sense. The bounds are used for several applications. First, a simple sampling algorithm is presented to compute the rate-distortion function for an arbitrarily varying source to within a given accuracy. The uniform continuity bound is used here to roughly quantify the tradeoff between complexity and accuracy. Second, we comment on the problem of approximating the rate-distortion function for an unknown IID source to within a desired precision.

Berger's paper 'The Source Coding Game', IEEE Trans. Inform. Theory, 1971, considers the problem of finding the rate-distortion function for an adversarial source comprised of multiple known IID sources. The adversary, called the 'switcher', was allowed only causal access to the source realizations and the rate-distortion function was obtained through the use of a type covering lemma. In this paper, the rate-distortion function of the adversarial source is described, under the assumption that the switcher has non-causal access to all source realizations. The proof utilizes the type covering lemma and simple conditional, random 'switching' rules. The rate-distortion function is once again the maximization of the R(D) function for a region of attainable IID distributions.