Abstract
This paper derives inner and outer bounds on the optimal performance of fixed-length block codes on discrete memoryless channels (DMCs) with feedback and errors-and-erasures decoding. An inner bound is established using a two-phase encoding scheme—consisting of communication and control phases—paired with an optimal decoding rule based on pairwise message comparisons. The outer bound is developed by generalizing the straight-line bound to errors-and-erasures decoders and leveraging the optimal error-exponent tradeoff of a two-message feedback encoder. Additionally, the paper characterizes the optimal erasure exponent for error-free block codes and proves that the optimal tradeoff between error exponents for a two-message code does not improve with feedback on DMCs.
Introduction
In classical information theory, Claude Shannon established that feedback does not increase the capacity of a discrete memoryless channel (DMC). However, it has long been understood that feedback can significantly improve the reliability of communication, specifically by increasing the error exponent, which dictates the rate at which the probability of error decays as the block length increases.
While much of the literature focuses on variable-length codes or fixed-length codes without an erasure option, practical communication systems (such as those employing Automatic Repeat Request, or ARQ) often utilize an "erasure" mechanism. In such systems, the receiver can declare a doubt (an erasure) rather than risking a decoding error. This paper addresses the fundamental limits of this tradeoff, characterizing the relationship between the error exponent ($E_e$) and the erasure exponent ($E_x$) for fixed-length codes in the presence of a noiseless feedback link.
Methodology
Inner Bound: Two-Phase Encoding
The authors propose a two-phase encoding strategy to achieve high reliability:
- Communication Phase: The transmitter sends the message using a standard fixed-composition code over a portion of the total block length.
- Control Phase: Utilizing the noiseless feedback, the transmitter observes the receiver's tentative state. It then transmits a simple "accept" or "reject" signal (a confirmation) to guide the final decoding decision.
Decoding is performed using a rule based on pairwise comparisons of messages across both phases. This allows the receiver to determine whether the evidence for a specific message is strong enough to accept or if an erasure should be declared.
Outer Bound: Generalizing the Straight-Line Bound
To establish the fundamental limits (the converse), the authors generalize the classic straight-line bound—originally developed by Shannon, Gallager, and Berlekamp—to accommodate decoders with an erasure option. A pivotal component of this analysis is the proof that for a code with only two messages, feedback does not improve the optimal tradeoff between the error exponents of those messages. This "two-message anchor" provides a rigorous constraint on the performance of codes with larger message sets.
Key Insights and Results
The Role of Feedback as Confirmation
The analysis demonstrates that the primary power of feedback in this context is not to send more data, but to provide confirmation. The two-phase scheme effectively uses the second phase to validate the receiver's initial hypothesis. This "decision feedback" is the mechanism that allows the error exponent to increase dramatically compared to non-feedback scenarios.
The Error-Erasure Tradeoff
The research quantifies a strict tradeoff: by allowing a higher probability of erasure (a lower $E_x$), the system can achieve a significantly higher error exponent ($E_e$). This relationship is particularly visible in symmetric channels like the Binary Symmetric Channel (BSC), where the derived inner and outer bounds are remarkably close, especially at high transmission rates. This proximity suggests that the proposed two-phase scheme is near-optimal.
Error-Free Communication
The paper also explores the limit where the probability of error is forced to zero ($P_e = 0$). For symmetric channels, the authors show that the optimal erasure exponent in this error-free regime is exactly the sphere-packing exponent. This provides a unified framework that connects feedback communication with classical non-feedback bounds.
Conclusion and Future Work
This work establishes tight bounds on the performance of fixed-length block codes with feedback and erasures, bridging a gap in the understanding of feedback's role in reliability. While the bounds are tight at high rates, a gap remains at lower rates, suggesting that more sophisticated strategies—perhaps involving multiple phases or continuous feedback—could be explored. Furthermore, while the results are robust for symmetric channels, future research is needed to refine the bounds for non-symmetric DMCs where the sphere-packing bound is not always tight. Finally, the computational complexity of the optimal pairwise decoding rule presents an opportunity for developing more efficient, near-optimal decoding architectures for practical implementation.
Summary updated