A Simple Converse of Burnashev's Reliability

Abstract

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.

10 pages, 1 figure, updated missing reference

References in corpus (1)

• On the error exponent of variable-length block-coding schemes over finite-state Markov channels with feedback

Cited by in corpus (11)

• Active sequential hypothesis testing
• Variations on a theme by Schalkwijk and Kailath
• Unequal Error Protection: An Information Theoretic Perspective
• Extrinsic Jensen-Shannon Divergence: Applications to Variable-Length Coding
• Error-and-Erasure Decoding for Block Codes with Feedback
• Noisy Bayesian Active Learning
• Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria
• Bit-wise Unequal Error Protection for Variable Length Block Codes with Feedback
• On the Reliability Function of the Common-Message Broadcast Channel with Variable-Length Feedback
• Rateless Codes for Finite Message Set
• Optimal Active Social Network De-anonymization Using Information Thresholds