Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 61, Issue 4, Pages 2148-2164Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2015.2401004
Keywords
Discrete memoryless channel; variable-length coding; sequential analysis; feedback gain; Burnashev's reliability function; optimal error exponent
Funding
- UCSD through Center for Wireless Communication
- NSF [CCF-1018722, CCF-1302588]
- city of Paris under Program entitled Emergences
Ask authors/readers for more resources
This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen-Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate-reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters R and E are guaranteed to achieve a rate R and an error exponent E. The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available