409 research outputs found
Recommended from our members
A Beta-Beta Achievability Bound with Applications
No full textA channel coding achievability bound expressed in terms of the ratio between two Neyman-Pearson β functions is proposed. This bound is the dual of a converse bound established earlier by Polyanskiy and Verdu ́ (2014). The new bound turns out to simplify considerably the analysis in situations where the channel output distribution is not a product distribution, for example due to a cost constraint or a structural constraint (such as orthogonality or constant composition) on the channel inputs. Connections to existing bounds in the literature are discussed. The bound is then used to derive 1) the channel dispersion of additive non-Gaussian noise channels with random Gaussian codebooks, 2) the channel dispersion of an exponential-noise channel, 3) a second-order expansion for the minimum energy per bit of an AWGN channel, and 4) a lower bound on the maximum coding rate of a multiple-input multiple-output Rayleigh-fading channel with perfect channel state information at the receiver, which is the tightest known achievability result
Hypothesis testing via a comparator
No full textThis paper investigates the best achievable performance by a hypothesis test satisfying a structural constraint: two functions are computed at two different terminals and the detector consists of a simple comparator verifying whether the functions agree. Such tests arise as part of study of fundamental limits of channel coding, but are also useful in other contexts. A simple expression for the Stein exponent is found and applied to showing a strong converse in the problem of multi-terminal hypothesis testing with rate constraints. Connections to the Gács-Körner common information and to spectral properties of conditional expectation operator are identified. Further tightening of results hinges on finding λ-blocks of minimal weight. Application of Delsarte's linear programming method to this problem is described.Center for Science of Information (Grant Agreement CCF-09-39370
Upper bound on list-decoding radius of binary codes
No full textConsider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most L. For odd L ≥ 3 an asymptotic upper bound on the rate of any such packing is proven. The resulting bound improves the best known bound (due to Blinovsky' 1986) for rates below a certain threshold. The method is a superposition of the linear- programming idea of Ashikhmin, Barg and Litsyn (that was used previously to improve the estimates of Blinovsky for L = 2) and a Ramsey-theoretic technique of Blinovsky. As an application it is shown that for all odd L the slope of the rate-radius tradeoff is zero at zero rate.National Science Foundation (U.S.) (Grant CCF-13-18620)National Science Foundation (U.S.). Science and Technology Center (Grant CCF-09-39370
On asynchronous capacity and dispersion
No full textRecently Tchamkerten et al. proposed a mathematical formulation of the problem of joint synchronization and error-correction in noisy channels. A variation of their formulation in this paper considers a strengthened requirement that the decoder estimate both the message and the location of the codeword exactly. It is shown that the capacity region remains unchanged and that the strong converse holds. The finite blocklength regime is investigated and it is demonstrated that even for moderate blocklengths, it is possible to construct capacity-achieving codes that tolerate exponential level of asynchronism and experience only a rather small loss in rate compared to the perfectly synchronized setting; in particular, the channel dispersion does not suffer any degradation due to asynchronism
On dispersion of compound DMCs
No full textCode for a compound discrete memoryless channel (DMC) is required to have small probability of error regardless of which channel in the collection perturbs the codewords. Capacity of the compound DMC has been derived classically: it equals the maximum (over input distributions) of the minimal (over channels in the collection) mutual information. In this paper the expression for the channel dispersion of the compound DMC is derived under certain regularity assumptions on the channel. Interestingly, dispersion is found to depend on a subtle interaction between the channels encoded in the geometric arrangement of the gradients of their mutual informations. It is also shown that the third-order term need not be logarithmic (unlike single-state DMCs). By a natural equivalence with compound DMC, all results (dispersion and bounds) carry over verbatim to a common message broadcast channel.National Science Foundation (U.S.) (CAREER Award CCF-12-53205)National Science Foundation (U.S.). Center for Science of Information (Grant Agreement CCF-0939370
Bounds on the reliability of a typewriter channel
No full textWe give new bounds on the reliability function of a typewriter channel with 5 inputs and crossover probability 1/2. The lower bound is more of theoretical than practical importance; it improves very marginally the expurgated bound, providing a counterexample to a conjecture on its tightness by Shannon, Gallager and Berlekamp which does not need the construction of algebraic-geometric codes previously used by Katsman, Tsfasman and VlǍduţ. The upper bound is derived by using an adaptation of the linear programming bound and it is essentially useful as a low-rate anchor for the straight line bound
Saddle Point in the Minimax Converse for Channel Coding
No full textA minimax metaconverse has recently been proposed as a simultaneous generalization of a number of classical results and a tool for the nonasymptotic analysis. In this paper, it is shown that the order of optimizing the input and output distributions can be interchanged without affecting the bound. In the course of the proof, a number of auxiliary results of separate interest are obtained. In particular, it is shown that the optimization problem is convex and can be solved in many cases by the symmetry considerations. As a consequence, it is demonstrated that in the latter cases, the (multiletter) input distribution in information-spectrum (Verdú-Han) converse bound can be taken to be a (memoryless) product of single-letter ones. A tight converse for the binary erasure channel is rederived by computing the optimal (nonproduct) output distribution. For discrete memoryless channels, a conjecture of Poor and Verdú regarding the tightness of the information spectrum bound on the error exponents is resolved in the negative. Concept of the channel symmetry group is established and relations with the definitions of symmetry by Gallager and Dobrushin are investigated.National Science Foundation (U.S.) (Center for Science of Information, under Grant CCF-0939370
On the bit error rate of repeated error-correcting codes
No full textClassically, error-correcting codes are studied with respect to performance metrics such as minimum distance (combinatorial) or probability of bit/block error over a given stochastic channel. In this paper, a different metric is considered. It is assumed that the block code is used to repeatedly encode user data. The resulting stream is subject to adversarial noise of given power, and the decoder is required to reproduce the data with minimal possible bit-error rate. This setup may be viewed as a combinatorial joint source-channel coding. Two basic results are shown for the achievable noise-distortion tradeoff: the optimal performance for decoders that are informed of the noise power, and global bounds for decoders operating in complete oblivion (with respect to noise level). General results are applied to the Hamming [7, 4, 3] code, for which it is demonstrated (among other things) that no oblivious decoder exist that attains optimality for all noise levels simultaneously.National Science Foundation (U.S.) (Grant CCF-13-18620
Asynchronous Communication: Exact Synchronization, Universality, and Dispersion
No full textRecently, Tchamkerten and coworkers proposed a novel variation of the problem of joint synchronization and error correction. This paper considers a strengthened formulation that requires the decoder to estimate both the message and the location of the codeword exactly. Such a scheme allows for transmitting data bits in the synchronization phase of the communication, thereby improving bandwidth and energy efficiencies. It is shown that the capacity region remains unchanged under the exact synchronization requirement. Furthermore, asynchronous capacity can be achieved by universal (channel independent) codes. Comparisons with earlier results on another (delay compensated) definition of rate are made. The finite blocklength regime is investigated and it is demonstrated that even for moderate blocklengths, it is possible to construct capacity-achieving codes that tolerate exponential level of asynchronism and experience only a rather small loss in rate compared to the perfectly synchronized setting; in particular, the channel dispersion does not suffer any degradation due to asynchronism. For the binary symmetric channel, a translation (coset) of a good linear code is shown to achieve the capacity-synchronization tradeoff.National Science Foundation (U.S.) (Center for Science of Information Grant CCF-0939370
Converse and duality results for combinatorial source-channel coding in binary Hamming spaces
No full textThis article continues the recent investigation of combinatorial joint source-channel coding. For the special case of a binary source and channel subject to distortion measured by Hamming distance, the lower (converse) bounds on achievable source distortion are improved for all values of channel noise. Operational duality between coding with bandwidth expansion factors ρ and 1 over ρ is established. Although the exact value of the asymptotic noise-distortion tradeoff curve is unknown (except at ρ = 1), some initial results on inter-relations between these curves for different values of ρ are shown and lead to statements about monotonicity and continuity in ρ.National Science Foundation (U.S.) (Grant CCF-13-18620
- …
