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
- The same trapdoor state transition as the feedback entry, but the encoder observes no channel outputs.
- Quantity
- Feedforward capacity \(C\), measured in bits per channel use.
Criterion. Nonfeedback encoding over arbitrary blocklengths.
- The initial state is fixed and known.
- Average decoding error vanishes.
Current status
\[0.572\le C\le0.5765\]
Both endpoints are reported numerical bounds rather than exact symbolic constants; the exact feedforward capacity remains open.
| Result | Relation | Method | Year |
|---|---|---|---|
| Lower | \(C\ge0.572\) | Finite-block Blahut-Arimoto maximization using recursive trapdoor-channel matrices.The reported decimal is extrapolated from computations through blocklength 10. | 2003 |
| Upper | \(C\le\log_2(3/2)\) | Q-graph dual capacity bound with an analytic Bellman-equation solution. | 2021 |
| Upper | \(C\le0.5765\)The initial state is known to the encoder and decoder; delayed feedback upper-bounds feedforward capacity. | Four-step delayed-feedback Q-graph converse evaluated by convex optimization.The source reports this rounded value from computer-based simulations, not as an exact analytic endpoint. | 2024 |
| Lower | \(1/2\le C\) | Repeat each message bit twice. With known entering state, each output pair determines the input bit and leaving state.The source introduction records the zero-error value 1/2 and credits earlier work. Only this analytic lower bound is selected, not 0.572. | 2006 |
Open question
Determine the exact capacity without encoder access to past outputs.
Channel state depends on the unobserved output history and creates input-dependent memory.
Improve finite-state achievability and converse bounds under a fixed initial-state convention.
Tasks
Formal verification
Lean coverageFormally stated
New statements await mathematical review and proofs. The admitted analytic claim uses 1/2 and log2(3/2). The separately displayed 0.572 and 0.5765 numerical endpoints are not certified by this claim.
Claims
- Analytic no-feedback bounds. Rounded or extrapolated numerical endpoints are not asserted.
analytic-capacity-bounds· capacity bounds · solved · Formally stated · v2 - Independently tracked repetition achievability.
repetition-achievability· achievability · solved · Formally stated · v1 - Independently tracked analytic converse.
analytic-converse· converse · solved · Formally stated · v1
Lean declarations (4)
CapacityAtlas.Channel.trapdoorFeedforwardModeldefinition
lean/CapacityAtlas/Channels/Trapdoor.lean — Concrete finite-state trapdoor channel used for the no-feedback problem.CapacityAtlas.Claims.trapdoorBoundsclaim · analytic-capacity-bounds
lean/CapacityAtlas/Claims/TrapdoorBounds.lean — Analytic no-feedback bounds. Rounded or extrapolated numerical endpoints are not asserted.CapacityAtlas.Claims.trapdoorRepetitionclaim · repetition-achievability
lean/CapacityAtlas/Claims/TrapdoorBounds.lean — Independently tracked repetition achievability.CapacityAtlas.Claims.trapdoorAnalyticConverseclaim · analytic-converse
lean/CapacityAtlas/Claims/TrapdoorBounds.lean — Independently tracked analytic converse.
References
- Haim H. Permuter, Paul Cuff, Benjamin Van Roy, and Tsachy Weissman (2006). Capacity of the Trapdoor Channel with Feedback. arXiv preprint.
- Kingo Kobayashi, Hiroyoshi Morita, and Mamoru Hoshi (2003). Some Considerations on the Trapdoor Channel. Proceedings of the 3rd Asian-European Workshop on Information Theory.
- Kingo Kobayashi (2006). Capacity Problem of Trapdoor Channel. General Theory of Information Transfer and Combinatorics, Lecture Notes in Computer Science 4123. DOI 10.1007/11889342_76.
- Bashar Huleihel, Oron Sabag, Haim H. Permuter, Navin Kashyap, and Shlomo Shamai (2021). Computable Upper Bounds on the Capacity of Finite-State Channels. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2021.3091691.
- Bashar Huleihel, Oron Sabag, Haim H. Permuter, and Victoria Kostina (2024). Capacity of Finite-State Channels With Delayed Feedback. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2023.3304408.