CCapacity Atlas
trapdoor-channel-with-feedback

Trapdoor channel with feedback

With causal noiseless output feedback and a known initial state, the binary trapdoor channel has capacity equal to the logarithm of the golden ratio.

Point-to-point Finite alphabet Binary Memory Feedback Capacity Exact

Channel and question

Input
A binary symbol inserted into a box already containing one binary state symbol.
Output
One of the two symbols is selected uniformly as output; the other becomes the next state.
Law
A unifilar finite-state channel with causal noiseless output feedback to the encoder.
Quantity
Feedback capacity \(C_{\mathrm{fb}}\), measured in bits per channel use.

Criterion. Causal encoding using past channel outputs.

  • The initial state is fixed and known to encoder and decoder.
  • Average decoding error vanishes.

Current status

\[C_{\mathrm{fb}}=\log_2\varphi\]
ResultRelationMethodYear
Exact\(C_{\mathrm{fb}}=\log_2\frac{1+\sqrt5}{2}\)Feedback dynamic program and an explicit capacity-achieving scheme.2006

Lean formalization

Canonical statementStatement

Version 1 · Lean. The finite-state transition and real-valued logarithmic identity are explicit.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  1. Haim H. Permuter, Paul Cuff, Benjamin Van Roy, and Tsachy Weissman (2006). Capacity of the Trapdoor Channel with Feedback. arXiv preprint.

Discussion

Thread key: capacityatlas:trapdoor-channel-with-feedback

Find discussionStart discussion

Related problems

AWGN channel with noiseless feedback

Noiseless feedback dramatically improves reliability schemes but leaves the ordinary AWGN capacity unchanged.

Point-to-point Continuous alphabet Gaussian Additive noise Feedback Power constraint Capacity Exact
Solved \(C_{\mathrm{AWGN,fb}}=\frac12\log_2\!\left(1+\frac PN\right)\)
Binary Z-channel Z-channel

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Binary Finite alphabet Discrete memoryless Asymmetric Capacity Exact
Solved \(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Binary erasure channel BEC

Each transmitted bit is received correctly or replaced by a visible erasure symbol.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Erasure Capacity Exact
Solved \(C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\)
Binary symmetric channel BSC

Each bit is independently flipped with probability p, giving the canonical finite noisy channel.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)