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

v2 · 2026-08-30 · History

Domain-specific #

1787

Origin domain

information theory

Subdomain

feedback channel coding

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. A feedback code is therefore a family of strategies or code trees, not just a fixed codeword assigned to each message.^[1][2]

Feedback lets the transmitter learn what the receiver has probably learned, focus later symbols on unresolved alternatives, confirm a tentative decision, retransmit or add redundancy after adverse observations, and stop when evidence is sufficient. It does not magically remove noise. The guarantee must name the forward channel, feedback channel, latency, information available at each endpoint, length model, input or power constraints, code rate, decoder, and probability or worst-case error criterion.

A foundational limit prevents overclaiming: perfect feedback does not increase the ordinary Shannon capacity of a stationary memoryless point-to-point channel under the usual fixed-block asymptotic model, although it may increase zero-error capacity and can greatly change achievable reliability, complexity, and latency.^[1] With variable length and noiseless feedback, Burnashev showed that a discrete memoryless channel can attain a stronger reliability function by separating information acquisition from confirmation.^[3] In finite-block and stop-feedback regimes, the exact model of termination and delay is likewise decisive.^[4]

The locked identity is message set + noisy forward channel + receiver observations + causal reverse information + adaptive encoder + decoder and optional stopping rule + explicit error and resource budget + a reliability guarantee. The abstraction survives as domain-specific because coding rate, capacity, error exponent, code tree, channel law, posterior, and decoding remain essential. Its portable skeleton instantiates Feedback, Redundancy, Adaptation, Sequential Decision, Error Correction, and Common Knowledge.

Structural Signature

• the message (W) — one value selected from a finite or asymptotically growing message set;
• the forward channel — a stochastic or adversarial map from each input (X_i) to an observation (Y_i), possibly with memory or state;
• the receiver history (Y^i) — evidence accumulated about the message after each use;
• the feedback signal — raw output, acknowledgment, posterior summary, stop signal, quantized information, or actively encoded reverse transmission;
• the feedback channel — noiseless or noisy, passive or active, delayed or instantaneous, rate- and power-constrained or ideal;
• the causal information pattern — the exact past feedback available when (X_i) is chosen, excluding future observations;
• the adaptive encoder (f_i) — a strategy mapping the message and feedback history to the next input;
• the code tree — branches representing different later transmissions after different returned histories;
• the decoder (g) — a rule mapping receiver observations, and possibly a stopping time, to an estimate \(\widehat W\);
• the length model — fixed blocklength, variable-length full feedback, stop-feedback, deadline, or expected-length constraint;
• the channel-use budget — blocklength, expected duration, forward and reverse rates, energy, average or peak power, and feedback cost;
• the reliability criterion — average, maximal, zero, erasure, list, or adversarial error under stated channel assumptions;
• the rate — message information divided by fixed or expected forward uses under the chosen convention;
• the synchronization invariant — encoder and decoder must agree sufficiently on histories, posteriors, and stopping; feedback errors can break that common state;
• the achieved guarantee — capacity, zero-error rate, error exponent, finite-block bound, correction radius, or latency–reliability trade-off.

Recognition requires feedback to affect encoding, stopping, or redundancy. A return telemetry stream observed only after the codeword is complete does not create a feedback code for that transmission.

What It Is Not

• Not an ordinary forward error-correcting block code. A conventional encoder chooses the entire codeword from the message before observing channel outputs.
• Not generic Feedback. The prime says output returns to affect input; this node adds a channel, message, causal encoder, decoder, resources, and a formal reliability criterion.
• Not Predictive Coding. Predictive coding transmits innovations or prediction residuals; it need not use receiver-to-transmitter observations.
• Not a decision-feedback equalizer. A receiver-side equalizer feeds its own past symbol decisions into later detection without returning information to the transmitter.
• Not transmitter channel-state information alone. Knowing a channel state can guide encoding but is not receiver-output feedback unless the information path and model say so.
• Not acknowledgment without adaptation. An ACK logged for monitoring but unable to change transmission or stopping is not operational feedback coding.
• Not Automatic Repeat reQuest in full. ARQ is an important neighboring protocol family using error detection and ACK/NACK retransmission; feedback codes also include symbolwise posterior schemes and interactive redundancy beyond repeat requests.
• Not Hybrid ARQ in full. Incremental redundancy is one realization, not the mathematical class.
• Not an interactive protocol merely because both sides send messages. The forward objective must include reliable encoding of the designated message under a channel-error model.
• Not the claim that feedback raises every capacity. Capacity, reliability, zero-error performance, and finite-length delay are different criteria.

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.^[1] Berlekamp developed fixed-block feedback coding for the binary symmetric channel and its adversarial/search interpretations.^[2]

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.^[5] 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.^[6]

For an additive white Gaussian-noise channel with ideal noiseless feedback, the Schalkwijk–Kailath scheme successively transmits the receiver’s estimation error. It achieves capacity with extremely rapid error decay under its model, but its ideal-feedback and precision assumptions are load-bearing; injecting feedback noise changes the problem rather than slightly perturbing the theorem.^[7]

Variable-length feedback codes can have a receiver-dependent stopping time. Burnashev’s reliability function for suitable discrete memoryless channels is (E(R)=C_1(1-R/C)), where (C) is capacity and (C_1) is the maximum relative entropy between two output distributions induced by channel inputs. The two factors correspond to communicating the message and confirming the leading hypothesis.^[3] Stop-feedback is weaker: the receiver may tell the transmitter only when to terminate. It can nevertheless supply large finite-length gains in some settings.^[4]

Noisy feedback includes passive return of corrupted observations and active transmission in which the receiver encodes a reverse-link signal subject to its own resource constraint. Rate limitation, delay, intermittent availability, and channel memory each change the admissible strategy and theorem.^[8] In adversarial channels and adaptive search with lies, code trees correspond to questions chosen after prior possibly corrupted answers, but the equivalence requires matched alphabets, error budgets, and roles.

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.

Noiseless feedback means the signal available to the transmitter equals the designated receiver information under the assumed delay; it does not mean the forward channel is noiseless. Noisy feedback introduces a second inference problem. If the transmitter believes the receiver saw one output when it saw another, their posteriors or code-tree branches can diverge. A robust scheme must model re-synchronization, protect the return link, or tolerate branch disagreement.

Fixed blocklength, expected variable length, and guaranteed deadline produce different rates and reliability results. Allowing a rare very long transmission can dramatically lower average error at the same expected length. A theorem about expected stopping time cannot be advertised as a hard-delay guarantee. Likewise, zero-error capacity, vanishing-error capacity, and error exponent measure different properties.

Feedback also differs from retransmission after final decoding failure. If the original codeword has ended and a higher-layer protocol starts a new attempt, that is feedback-based error control; whether it belongs to the narrow coding theorem depends on whether the attempts and stopping are modeled as one variable-length code.

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.

The code-tree representation makes this state explicit. At depth (i), two messages can share or separate branches depending on feedback history. Reliability questions then become questions about how strategies partition the remaining message set under possible channel outputs. In probabilistic channels, posterior mass is repeatedly reshaped; in adversarial channels, uncertainty sets are reduced while respecting the error budget.

Variable length further separates communication from confirmation. The first phase raises one message’s posterior; the second asks whether the receiver’s tentative choice is correct, using highly distinguishable inputs. This localization explains Burnashev’s exponent rather than treating feedback gain as an unexplained bonus.

The abstraction also exposes implementation costs often omitted from ideal theorems: reverse-link bandwidth and energy, delay, feedback packet errors, storage of shared history, precision, encoder computation, channel-model mismatch, and the risk of duplicated or missing termination. An honest design treats those as part of the code model.

Abstract Reasoning

1. If (X_i) is independent of every returned observation given (W), the alleged feedback code collapses to a no-feedback encoder.
2. If feedback is available only after time (n), it cannot improve the encoding decisions of a fixed length-(n) transmission.
3. 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.
4. If variable stopping is allowed, feedback can improve reliability and average latency even where fixed-block capacity is unchanged.
5. If a receiver sends only a stop signal, it cannot support arbitrary posterior matching, but it can prevent unnecessary symbols after decoding evidence is sufficient.
6. If feedback noise can put the encoder and decoder on different code-tree branches, a noiseless-feedback proof no longer applies.
7. If the reverse link consumes scarce bandwidth or power, forward-only rate comparisons can overstate end-to-end gain.
8. If the transmitter knows the receiver’s exact past outputs, it can target the receiver’s remaining ambiguity rather than resend redundancy useful under histories that did not occur.
9. If the channel has memory, feedback can reveal information about state as well as decoder belief, so capacity behavior need not match the memoryless theorem.
10. If an error exponent improves but blocklength and rate stay fixed, the gain is reliability, not capacity.
11. If termination is permitted only in expectation, a low average latency can coexist with a long tail and fail a hard real-time requirement.
12. If the adversary observes feedback or encoder randomness, the correctable-error guarantee can differ from a private-feedback model; adversarial knowledge must be stated.

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.

The adaptive-search correspondence transfers when the unknown message is an item, each forward input corresponds to a partitioning question or response strategy, returned outcomes update the uncertainty set, and lies correspond to channel errors. It breaks if roles, timing, noise budget, or feedback observation differ.

At a generic level, the node demonstrates that return information can convert a fixed plan into a contingent strategy and concentrate resources on realized errors. That skeleton belongs to Feedback, Adaptation, Sequential Decision, and Active Learning. The coding identity remains tied to messages, channels, rates, code trees, and decoding guarantees.

Examples

• binary symmetric channel posterior scheme: past received bits are fed back without error, both endpoints update the message posterior, and each new symbol bisects or otherwise reshapes the remaining posterior mass;
• Gaussian refinement: the receiver’s estimation error is learned through perfect output feedback and a scaled correction is sent on the next use;
• binary erasure channel: feedback tells the encoder which symbols were erased, permitting retransmission or continued incremental information until decoding succeeds;
• variable-length confirmation: after one message becomes likely, the encoder sends one of two highly distinguishable confirmation patterns before the receiver stops;
• stop-feedback: the encoder follows a forward rateless sequence until the receiver sends a reliable termination signal;
• Hybrid ARQ: a NACK triggers additional parity rather than restarting the identical block, making redundancy contingent on observed decoding failure;
• noisy active feedback: the receiver encodes a reverse-link signal under its own power constraint; both forward and backward error events enter the guarantee;
• adaptive search with lies: each answer narrows a candidate set, later questions depend on earlier answers, and the strategy guarantees identification under a bounded lie count;
• non-example—decision-feedback equalization: only the receiver adapts its detector; the transmitter never receives the decisions;
• failure—ideal-link transplant: a noiseless-feedback scheme is deployed on a delayed noisy return link without branch synchronization.

Structural Tensions

• capacity invariance vs. reliability gain — memoryless capacity may remain fixed while error exponent, zero-error behavior, complexity, or delay improves;
• fixed delay vs. adaptive stopping — guaranteed latency simplifies service bounds, while variable length concentrates effort on difficult noise histories;
• rich feedback vs. reverse cost — full outputs enable precise adaptation, while ACK/NACK or stop signals consume much less bandwidth and energy;
• noiseless theory vs. noisy implementation — ideal feedback yields sharp schemes, while small reverse errors can desynchronize aggressive refinements;
• passive vs. active feedback — echoing observations avoids reverse encoding, while active feedback can protect or compress the information at a resource cost;
• posterior precision vs. robust quantization — exact beliefs support elegant capacity-achieving recursions, while finite precision and model mismatch demand coarse resilient state;
• average latency vs. tail latency — expected-length guarantees permit rare long transmissions, while real-time systems care about deadlines;
• forward reliability vs. feedback security — detailed returned observations help adaptation, while they can reveal receiver state or create attack surfaces;
• retransmission vs. new redundancy — repeating is simple, while incremental or posterior-targeted symbols use history more efficiently;
• common history vs. branch divergence — adaptation gains depend on shared state, while feedback corruption makes maintaining that state a coding problem of its own.

Structural–Framed Character

The abstraction is structural. Once the message prior, forward and reverse channel laws, causal information pattern, input constraints, encoder family, decoder, stopping rule, and error criterion are fixed, achievable rate and reliability are mathematical questions. Whether a scheme is capacity-achieving or satisfies an error budget is not a matter of interpretive framing.

Model selection remains load-bearing. “Feedback available” is incomplete until noise, delay, rate, power, activity, and stopping are specified. Those are observer choices about which physical communication system is represented, but the consequences inside the chosen model are formally constrained. This keeps the node structural while making its boundary discipline unusually important.

Structural Core vs. Domain Accent

The structural core is uncertain transmission + returned outcome information + causal plan revision + sequential uncertainty reduction + confirmation + stopping + bounded residual error. The domain accent is message alphabet, forward and reverse channels, encoder functions, code trees, rate, capacity, blocklength, error probability, and decoder.

Remove the accent and the result is generic Feedback or adaptive decision making. Retain redundancy without returned observations and the result is ordinary forward error correction. Retain the complete causal channel-and-code package and the node applies across stochastic communication and matched search games.

Instantiates / Related Primes

• Feedback — receiver-side output returns to change later encoder inputs or stopping.
• Redundancy — additional channel symbols protect message identity against noise.
• Adaptation — the transmission strategy is conditional on realized observations rather than fixed in advance.
• Sequential Decision — each symbol or stopping choice uses a growing information history.
• Error Correction — the decoder recovers the intended message despite specified alterations or uncertainty.
• Common Knowledge — aggressive schemes depend on encoder and decoder sharing enough history to coordinate posterior or branch state.
• Confirmation — a high-confidence tentative decision is explicitly tested before stopping.
• Trade-off — rate, error, average and tail delay, power, precision, and reverse-link cost cannot generally be optimized simultaneously.
• Robustness — practical schemes must tolerate mismatch, delay, quantization, and feedback corruption outside ideal models.

prime:predictive_coding is the rematch leader but not coverage: prediction residuals need no receiver-to-transmitter link or adaptive decoding guarantee. The smallest prospective parent is prime:feedback; the candidate is its strict coding-theoretic specialization.

Relationships to Other Abstractions

Current abstraction Error-Correcting Codes with Feedback Domain-specific

Parents (1) — more general patterns this builds on

• 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 → 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 (1565 abstractions)

Nearest neighbors

• Shannon–Weaver Communication Model — 0.80
• Model Inversion Attack — 0.75
• Communication source — 0.74
• Language expectancy theory — 0.73
• Additive White Gaussian Noise — 0.73

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

• ordinary forward error-correcting codes with fixed codewords;
• generic feedback loops without messages and decoding;
• predictive coding or differential pulse-code modulation;
• receiver-side decision-feedback equalization;
• channel-state information at the transmitter from a source other than receiver feedback;
• Automatic Repeat reQuest as the entire class;
• Hybrid ARQ as one protocol family;
• rateless or fountain codes without a return signal;
• interactive communication without a forward message-recovery guarantee;
• control over a communication channel, although control and feedback coding can interact;
• noiseless forward transmission with acknowledgments;
• the universal claim that feedback raises Shannon capacity.

References

[1] Claude E. Shannon, “The Zero Error Capacity of a Noisy Channel,” IRE Transactions on Information Theory 2, no. 3 (1956): 8–19, https://doi.org/10.1109/TIT.1956.1056798. registry ↩a ↩b ↩c

[2] Elwyn R. Berlekamp, Block Coding with Noiseless Feedback, PhD dissertation, Massachusetts Institute of Technology, 1964, https://dspace.mit.edu/handle/1721.1/14783. registry ↩a ↩b

[3] M. V. Burnashev, “Data Transmission over a Discrete Channel with Feedback: Random Transmission Time,” Problems of Information Transmission 12, no. 4 (1976): 250–265, https://m.mathnet.ru/php/archive.phtml?jrnid=ppi&option_lang=eng&paperid=1706&wshow=paper. registry ↩a ↩b

[4] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdú, “Feedback in the Non-Asymptotic Regime,” IEEE Transactions on Information Theory 57, no. 8 (2011): 4903–4925, https://doi.org/10.1109/TIT.2011.2158476. registry ↩a ↩b

[5] Michael Horstein, “Sequential Transmission Using Noiseless Feedback,” IEEE Transactions on Information Theory 9, no. 3 (1963): 136–143, https://doi.org/10.1109/TIT.1963.1057832. registry ↩

[6] Ofer Shayevitz and Meir Feder, “Optimal Feedback Communication via Posterior Matching,” IEEE Transactions on Information Theory 57, no. 3 (2011): 1186–1222, https://doi.org/10.1109/TIT.2010.2104992. registry ↩

[7] J. P. M. Schalkwijk and Thomas Kailath, “A Coding Scheme for Additive Noise Channels with Feedback—Part I: No Bandwidth Constraint,” IEEE Transactions on Information Theory 12, no. 2 (1966): 172–182, https://doi.org/10.1109/TIT.1966.1053879. registry ↩

[8] Young-Han Kim, Amos Lapidoth, and Tsachy Weissman, “Error Exponents for the Gaussian Channel with Active Noisy Feedback,” IEEE Transactions on Information Theory 57, no. 3 (2011): 1223–1236, https://doi.org/10.1109/TIT.2011.2104991. registry ↩

[9] Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2^nd ed. (Wiley, 2006), https://doi.org/10.1002/047174882X. registry

[10] “Error-correcting codes with feedback,” Wikipedia, frozen revision 1328568450, https://en.wikipedia.org/wiki/Error-correcting_codes_with_feedback. registry