Error-Correcting Codes with Feedback¶

Channel codes whose encoder causally adapts later transmissions to receiver-side information returned over a feedback link, with reliability, rate, delay, stopping, and feedback-noise assumptions stated as part of the code.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1787
Domain group: Formal Sciences
Origin domain: Information Theory
Subdomain: Feedback Channel Coding → Information Theory
Aliases: Feedback Codes, Channel Codes with Feedback, Feedback Channel Codes

Core Idea¶

Error-Correcting Codes with Feedback are channel codes in which information derived from the receiver’s observations returns to the transmitter and causally changes later channel inputs. In an ideal output-feedback model, a message \(W\in\{1,\ldots,M\}\) is sent over a forward channel and the encoder at time (i) chooses

\[ X_i=f_i(W,Y^{i-1}), \]

where (Y^{i-1}) is the receiver’s past output sequence returned noiselessly and without delay. The receiver ultimately computes \(\widehat W=g(Y^n)\), or stops at a random time \(\tau\) in a variable-length scheme. In noisy, delayed, rate-limited, or active-feedback models, the transmitter instead sees a causally available feedback record (Z^{i-1}) generated through an explicitly modeled reverse link.

How would you explain it like I'm…

Tell-Me-What-You-Heard Messages

Imagine you are telling a friend a secret across a noisy playground. Your friend keeps telling you what they think they heard. Then you can repeat only the confusing part, and you can stop once they have it right. The noise is still there, but listening back helps you fix mistakes faster.

Messages That Listen Back

When you send a message over a noisy line, some parts can get scrambled. In a code with feedback, the receiver's observations travel back to the sender. The sender uses them to choose what to send next. It might resend the confusing parts, add extra checks, confirm a guess, or stop early when the receiver is sure. Feedback does not make the noise disappear. It lets the sender spend its effort where it helps most.

Adaptive Coding Using Receiver Feedback

An error-correcting code with feedback lets the sender see, through a return link, what the receiver has observed so far. Each new symbol it sends can depend on both the message and that past feedback. So the code is a strategy, like a branching tree, rather than one fixed codeword per message. This lets the sender focus on alternatives that are still unresolved, confirm a tentative decision, or stop once the evidence is strong enough. A surprising limit applies to a standard memoryless channel with fixed-length blocks: even perfect feedback does not raise its ordinary capacity. What it can change is reliability, delay, and complexity. Any claim about such a code must say exactly how the feedback works, for example whether it is noisy or delayed.

In the ideal output-feedback model, a message W is encoded at time i as X_i = f_i(W, Y^{i-1}). Here Y^{i-1} is the receiver's past channel output, returned noiselessly and with no delay. The decoder outputs an estimate g(Y^n), or in variable-length schemes stops at a random time τ. With realistic feedback that is noisy, delayed, rate-limited, or active, the encoder instead sees a causally available record Z^{i-1} generated by an explicitly modeled reverse channel. Because inputs adapt to feedback, the code is a family of strategies or code trees rather than a fixed codebook. Feedback enables posterior-focused transmission, confirmation, retransmission or added redundancy after bad observations, and stopping rules. Shannon showed that perfect feedback does not increase the ordinary capacity of a stationary memoryless point-to-point channel under fixed-block asymptotics. It can, however, increase zero-error capacity and greatly improve error exponents and latency. Burnashev's result shows that variable-length coding with noiseless feedback achieves a stronger reliability function by splitting communication into an information-acquisition phase and a confirmation phase. Every guarantee must specify the forward and feedback channels, latency, endpoint information, length model, constraints, rate, decoder, and error criterion.

Scope of Application¶

For a discrete memoryless channel with noiseless output feedback, fixed-block codes allow each input to depend on past outputs. Shannon proved that this does not increase ordinary capacity, but the code tree can alter error probabilities and zero-error distinguishability. Berlekamp developed fixed-block feedback coding for the binary symmetric channel and its adversarial/search interpretations.

Sequential and variable-length schemes use feedback more deeply. Horstein’s binary symmetric-channel procedure continually refines the receiver’s posterior location of the message. Posterior matching generalizes the principle: transmit so the current message posterior is mapped back into the chosen input distribution, making the Horstein and Schalkwijk–Kailath schemes instances of one framework for memoryless channels.

Clarity¶

“Feedback” must specify what, when, and how reliably. Full output feedback returns every (Y_i). Decision feedback may return an estimate or confidence. ACK/NACK returns a small control alphabet. Stop-feedback sends only termination. Active feedback allows the receiver to encode reverse symbols. These are not interchangeable information structures.

Manages Complexity¶

Without feedback, a decoder’s confusion is hidden from the encoder until the predetermined block ends. The encoder must protect against all plausible noise histories with one fixed continuation. Feedback exposes a common or partially common state: which message alternatives remain likely, which symbols were erased, whether the receiver has enough evidence, or whether a confirmation is needed.

Abstract Reasoning¶

If (X_i) is independent of every returned observation given (W), the alleged feedback code collapses to a no-feedback encoder.
If feedback is available only after time (n), it cannot improve the encoding decisions of a fixed length-(n) transmission.
If a stationary memoryless point-to-point channel has perfect feedback, ordinary asymptotic capacity remains the no-feedback capacity; any claimed gain must concern another metric or model.

Knowledge Transfer¶

The full identity transfers across discrete, Gaussian, erasure, channel-with-memory, multiuser, and adversarial settings: receiver evidence returns causally, the encoder adapts, and reliability is evaluated under a declared resource model. Theorems do not transfer freely. Shannon’s no-capacity-gain result is for memoryless point-to-point channels under the relevant capacity model. Schalkwijk–Kailath depends on ideal Gaussian assumptions. Burnashev depends on variable length and noiseless feedback. Noisy-feedback exponents require a reverse-channel model.

Relationships to Other Abstractions¶

Current abstraction Error-Correcting Codes with Feedback Domain-specific

Parents (1) — outgoing typed relations

Error-Correcting Codes with Feedback is a kind of Feedback Prime

receiver-side output returns to change later encoder inputs or stopping.

Hierarchy path (1) — routes to 1 parentless root

Error-Correcting Codes with Feedback → is a kind of Feedback

Neighborhood in Abstraction Space¶

Error-Correcting Codes with Feedback sits in a sparse region of the domain-specific corpus (98^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Shannon–Weaver Communication Model — 0.80
Relay channel — 0.77
Online Machine Learning — 0.75
Model Inversion Attack — 0.75
Iterative reconstruction — 0.74

Computed from structural-signature embeddings · 2026-10-25