Errors-and-Erasures Decoding for Block Codes With Feedback

Barış Nakiboğlu, Lizhong ZhengIEEE Trans. Information Theory 2012 · DOI · arXiv

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:

  1. Communication Phase: The transmitter sends the message using a standard fixed-composition code over a portion of the total block length.
  2. 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

Abstract

Inner and outer bounds are derived on the optimal performance of fixed-length block codes on discrete memoryless channels with feedback and errors-and-erasures decoding. First, an inner bound is derived using a two-phase encoding scheme with communication and control phases together with the optimal decoding rule for the given encoding scheme, among decoding rules that can be represented in terms of pairwise comparisons between the messages. Then, an outer bound is derived using a generalization of the straight-line bound to errors-and-erasures decoders and the optimal error-exponent tradeoff of a feedback encoder with two messages. In addition, upper and lower bounds are derived, for the optimal erasure exponent of error-free block codes in terms of the rate. Finally, a proof is provided for the fact that the optimal tradeoff between error exponents of a two-message code does not improve with feedback on discrete memoryless channels (DMCs).
BibTeX
@article{nakiboglu2012errors,
  author = {Barış Nakiboğlu and Lizhong Zheng},
  title = {{Errors-and-Erasures Decoding for Block Codes With Feedback}},
  journal = {IEEE Transactions on Information Theory},
  year = {2012},
  doi = {10.1109/tit.2011.2169529},
}
Figure