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\]
Known results and bounds for Trapdoor channel with feedback
ResultRelationMethodYear
Exact\(C_{\mathrm{fb}}=\log_2\frac{1+\sqrt5}{2}\)Feedback dynamic program and an explicit capacity-achieving scheme.2006

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • Feedback trapdoor capacity with a fixed state known to both terminals.
    operational-capacity · exact capacity · solved · Formally stated · v2
Lean declarations (2)

References

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

Discussion

Find discussionStart discussion

Related problems

AWGN channel with noiseless feedback

Noiseless output feedback improves reliability without changing AWGN capacity.

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 memory with encoder-known stuck-at defects

Independent stuck-at defects are known noncausally to the encoder but not the decoder.

Point-to-point Binary Finite alphabet Discrete memoryless Noncausal state information Capacity Exact
Solved \(C=1-\delta\)