Consider the following unequal error protection scenario. One special message, dubbed the “red alert” message, is required to have an extremely small probability of missed detection. The remainder of the messages must keep their average probability of error and probability of false alarm below a certain threshold. The goal then is to design a codebook that maximizes the error exponent of the red alert message while ensuring that the average probability of error and probability of false alarm go to zero as the blocklength goes to infinity. This red alert exponent has previously been characterized for discrete memoryless channels. This paper completely characterizes the optimal red alert exponent for additive white Gaussian noise channels with block power constraints.
The fundamental mechanism through which high red alert exponents are achieved is a binary hypothesis test. By designing the induced distributions at the output of the channel to be far apart as measured by KL divergence, we can distinguish whether the red alert or some standard codeword was sent. The test threshold is biased to minimize the probability of missed detection and is analyzed via an application of Stein's Lemma. This sort of biased hypothesis test occurs in numerous other communication settings with feedback, such as @cite_16 @cite_8 @cite_13 and, as mentioned earlier, these codes are also used as a component in streaming data systems (see, for instance, @cite_3 @cite_19 @cite_15 @cite_2 ). There is also a rich literature on the interplay between hypothesis testing and information theory, which we cannot do justice to here (see, for instance, @cite_0 @cite_4 @cite_18 ).
@cite_18 @cite_4 @cite_8 @cite_3 @cite_0 @cite_19 @cite_2 @cite_15 @cite_16 @cite_13
1999805402 2021547642 2115827190 2034597819 2164985961 2108078432 2107543180 2040877654
The authors present the answer to a so-called converse problem by giving the explicit form of the power exponent. This strong converse should be regarded as completing a weak converse previously obtained by R.E. Blahut (1974). > A new class of statistical problems is introduced, involving the presence of communication constraints on remotely collected data. Bivariate hypothesis testing, H_ 0 : P_ XY against H_ 1 : P_ = XY , is considered when the statistician has direct access to Y data but can be informed about X data only at a preseribed finite rate R . For any fixed R the smallest achievable probability of an error of type 2 with the probability of an error of type 1 being at most is shown to go to zero with an exponential rate not depending on as the sample size goes to infinity. A single-letter formula for the exponent is given when P_ = XY = P_ X P_ Y (test against independence), and partial results are obtained for general P_ = XY . An application to a search problem of Chernoff is also given. By an extension of Gallager's bounding methods, exponential error bounds applicable to coding schemes involving erasures, variable-size lists, and decision feedback are obtained. The bounds are everywhere the tightest known. The testing of binary hypotheses is developed from an information-theoretic point of view, and the asymptotic performance of optimum hypothesis testers is developed in exact analogy to the asymptotic performance of optimum channel codes. The discrimination, introduced by Kullback, is developed in a role analogous to that of mutual information in channel coding theory. Based on the discrimination, an error-exponent function e(r) is defined. This function is found to describe the behavior of optimum hypothesis testers asymptotically with block length. Next, mutual information is introduced as a minimum of a set of discriminations. This approach has later coding significance. The channel reliability-rate function E(R) is defined in terms of discrimination, and a number of its mathematical properties developed. Sphere-packing-like bounds are developed in a relatively straightforward and intuitive manner by relating e(r) and E (R) . This ties together the aforementioned developments and gives a lower bound in terms of a hypothesis testing model. The result is valid for discrete or continuous probability distributions. The discrimination function is also used to define a source code reliability-rate function. This function allows a simpler proof of the source coding theorem and also bounds the code performance as a function of block length, thereby providing the source coding analog of E (R) . We show how to exploit a noisy feedback link to implement high-reliability communication. We specify a variable-length coding strategy that achieves the error exponent (in delay) of erasure decoding using any noisy feedback channel which has a positive zero-rate random coding error exponent. Building on this result, we give a second approach that, depending only on the capacity of the feedback link, achieves an error exponent up to half of the Burnashev exponent - the maximum exponent that can be achieved with a noiseless feedback link. The resulting exponent can be far larger than the exponent of erasure decoding, particularly at rates close to capacity In this paper we bound the reliability function of decoding with errors and erasures for a streaming multiple-access channel with feedback. We show that, subject to an arbitrarily small bound on the probability of erasure, the best known lower bound on the reliability function (i.e., achievable error exponent) for the single-user version of our problem can also be achieved in the multi-user setting for high sum-rates. In other words, at high rates the interference of another user need not decrease the achievable error exponent of either. For output-symmetric discrete memoryless channels (DMCs) at even moderately high rates, fixed-block-length communication systems show no improvements in their error exponents with feedback. This paper studies systems with fixed end-to-end delay and shows that feedback generally provides dramatic gains in the error exponents. A new upper bound (the uncertainty-focusing bound) is given on the probability of symbol error in a fixed-delay communication system with feedback. This bound turns out to have a form similar to Viterbi's bound used for the block error probability of convolutional codes as a function of the fixed constraint length. The uncertainty-focusing bound is shown to be asymptotically achievable with noiseless feedback for erasure channels as well as for any output-symmetric DMC that has strictly positive zero-error capacity. Furthermore, it can be achieved in a delay-universal (anytime) fashion even if the feedback itself is delayed by a small amount. Finally, it is shown that for end-to-end delay, it is generally possible at high rates to beat the sphere-packing bound for general DMCs - thereby providing a counterexample to a conjecture of Pinsker. The presence of a feedback channel makes possible a variety of sequential transmission procedures, each of which can be classified as either a block-transmission or a continuous-transmission scheme according to the way in which information is encoded for transmission over a noisy forward channel. A sequential continuous-transmission system employing a binary symmetric forward channel (but which is suitable for use with any discrete memoryless forward channel) and a noiseless feedback channel is described. Its error exponent is shown to be substantially greater than the optimum block-code error exponent at all transmission rates less than channel capacity. The average value and the first-order probability distribution of the effective constraint length, found by simulating the system on an IBM 709 computer, are also given.