Zero-Error Communication with Variable-Length Feedback

43 concepts24 papers1 proposal

In classical information theory, Shannon's capacity formula assumes we can tolerate a vanishingly small probability of error ($\epsilon \to 0$) as the block length of our code approaches infinity. For downloading a file or streaming a video, this probabilistic guarantee is perfectly acceptable.

However, for safety-critical systems—such as autonomous vehicles tracking a physical state, adversarial networks, or real-time distributed control loops—a single decoding error can cause catastrophic failure. These applications require a zero-error constraint: the receiver must never misidentify the transmitted message.

As noted by Siddharth Bhandari et al. in Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel, enforcing absolute certainty fundamentally changes the mathematical landscape. Instead of optimizing smooth, continuous probabilities, zero-error communication becomes a rigid combinatorial challenge. If two distinct codewords can produce even a single overlapping output symbol under the channel's noise profile, they become completely indistinguishable to the decoder.

The Combinatorial Geometry of Confusion

To understand why zero-error capacity is notoriously difficult to compute, we must look at it through the lens of graph theory. As explored by Lele Wang et al. in Graph Information Ratio, we can model a channel using a confusion graph. In this graph, vertices represent input symbols, and an edge connects two symbols if they can be mapped to the same output symbol by the channel (making them "confusable"). Finding a zero-error code means finding an independent set of this graph—a collection of vertices with no edges between them.

Probabilistic Channel (Shannon)           Zero-Error Channel (Shannon/Körner)
      Inputs       Outputs                      Inputs (Confusion Graph)
       [A] --------> [X]                         (A) ------- (B)  <- Confusable!
        \  \___       ^                           |           |
         \     \     /                            |           |
          v     v   /                             (C) ------- (D)
         [B] --------> [Y]                      
                                                Valid Code: {A, D} or {B, C}
  (Errors can vanish asymptotically)             (Zero overlap permitted)

When we send sequences of symbols, the problem scales via graph products. However, the capacity of these products does not always behave cleanly. Nicolas Charpenay et al. demonstrate in On the Additivity of Optimal Rates for Independent Zero-Error Source and Channel Problems that determining exact capacity formulas remains an enduring mathematical hurdle because zero-error constraints strip away the smoothing effects of large-sample averages.

In multi-user or adversarial settings, this geometry becomes even more intricate. For instance, Yihan Zhang 0001 et al. in Zero-Error Communication Over Adversarial MACs formalize these boundaries using "confusability sets" to map out exactly what distributions a code must avoid to withstand active tampering by an opponent.

Bridging the Gap with Variable-Length Feedback

If zero-error communication over noisy channels is so restrictive, how can we achieve practical transmission rates? The breakthrough comes from combining two mechanisms: feedback and variable-length coding.

In standard fixed-length communication, a famous result by Shannon states that noiseless feedback does not increase the capacity of a memoryless channel. However, when the transmitter can receive feedback and vary the duration of the transmission dynamically, the game changes entirely.

Consider a state-dependent channel where the channel's behavior fluctuates over time. In Error-Free Communication Over State-Dependent Channels with Variable-Length Feedback, Mladen Kovacevic 0001 et al. show that variable-length feedback acts as a bridge, allowing the system to achieve zero-error communication at the exact same rate as the standard Shannon capacity.

Why does this work? The intuition is elegant:

  1. Fixed-length codes must be designed for the absolute worst-case noise conditions to guarantee zero error. This forces the transmission rate to drop drastically, often to zero.
  2. Variable-length codes with feedback allow the transmitter to monitor the receiver's state in real time. If the channel experiences a rare, catastrophic noise event that creates ambiguity, the transmitter uses the feedback link to recognize this and simply keeps sending clarifying information until the ambiguity is completely resolved.

Because worst-case noise events are rare, the average transmission time remains low. Thus, the average throughput matches the standard Shannon capacity, while the maximum transmission time flexes dynamically to guarantee absolute reliability.

The Binary Capacity Phenomenon

This interplay leads to a striking mathematical property discovered by Mladen Kovacevic 0001 et al. in Fundamental Limits of Communication Over State-Dependent Channels With Feedback. For a wide class of state-dependent channels, the zero-error capacity under variable-length coding exhibits a binary behavior: it is either exactly zero, or it is exactly equal to the standard Shannon capacity.

Zero-Error Capacity Region
^
|          /| Variable-Length Feedback Capacity (= Shannon Capacity)
|         / | 
|        /  | 
|       /   | 
|      /    | 
|     /     | 
|    /      | 
+---/-------+------------------------> Channel Quality
   |
   +-- If any error-free rate is possible, 
       the system jumps immediately to full Shannon Capacity.

This means that if a channel allows for any non-zero rate of perfectly reliable communication, the combination of feedback and variable-length coding can scale that reliability up to the theoretical maximum speed of the channel. You do not have to sacrifice throughput to buy absolute certainty; the primary utility of feedback is not to boost raw speed, but to collapse the error probability from "vanishingly small" to "exactly zero."

Alternatively, if a system cannot tolerate variable transmission lengths but can tolerate occasional erasures, a similar threshold behavior occurs. Rajai Nasser demonstrates in Erasure schemes using generalized polar codes: Zero-undetected-error capacity and performance trade-offs that generalized polar codes exhibit a sharp trade-off at a specific "zero-undetected-error capacity." Below this capacity, the receiver can achieve zero undetected errors with minimal erasures, but pushing the rate any higher forces a sharp spike in erasures to prevent incorrect messages from slipping through.

Accelerating Reliability Near Capacity

Even when operating in regimes where zero-error is impossible without feedback, feedback dramatically accelerates how fast the remaining error probability drops. In fixed-length codes, approaching capacity causes the error probability to decay slowly.

Lan V. Truong et al. in Moderate Deviation Asymptotics for Variable-Length Codes With Feedback analyze this near-capacity regime, proving how feedback shifts the error decay from a slow quadratic rate to a much faster linear rate.

This acceleration is also vital in multi-user environments. Achilleas Anastasopoulos et al. in On the Reliability Function of Discrete Memoryless Multiple-Access Channel With Feedback demonstrate that variable-length codes paired with feedback significantly boost the "error exponent" (the exponential speed of error decay) for multiple-access channels (MACs). By allowing multiple users to dynamically adjust their transmissions based on shared feedback, the network avoids catastrophic collisions and maintains high reliability even under heavy loads.

Why It Matters: Bounded State Estimation

The ultimate practical value of this framework shines in control theory and cyber-physical systems. If you are controlling a physical system (like an autonomous drone or a power grid) over a wireless link, an uncorrected communication error can cause the controller's state estimation error to grow exponentially, leading to physical instability.

Amir Hossein Saberi et al. explicitly connect these fields in Bounded Estimation Over Finite-State Channels: Relating Topological Entropy and Zero-Error Capacity. They prove that to guarantee a bounded estimation error over a finite-state channel, the critical metric is not the ordinary Shannon capacity, but the channel's zero-error capacity. Specifically, the zero-error capacity must exceed the system's topological entropy—the rate at which the physical system naturally generates uncertainty.

This principle extends directly to multi-user control systems. In Uniformly Bounded State Estimation Over Multiple Access Channels, Ghassen Zafzouf et al. show that the combined topological entropy of multiple interconnected systems must fit within the zero-error capacity region of a shared Multiple Access Channel to guarantee worst-case performance bounds. By shifting the focus from average-case performance to combinatorial zero-error limits, this body of research provides the foundational mathematics needed to guarantee absolute safety in networked control systems.

Key Foundational Work

A training based scheme for communicating over unknown channels with feedback (2009) — contributed 2 concept elements to this direction.
The Gaussian Channel with Noisy Feedback (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_zero_error_communication_constraint_7a6ccca6,
  title = {zero-error communication constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zero-error-communication-constraint/rdr_7a6ccca607884a87b63034f9f273f540},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_zero_error_communication_constraint_7a6ccca6_v1,
  title = {zero-error communication constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zero-error-communication-constraint/rdr_7a6ccca607884a87b63034f9f273f540/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake