Capacity of the Trapdoor Channel With Feedback

We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoor channel is an instance that admits a simple closed-form solution.

• Publication year

  2006

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2006-10-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2008.924681arXiv cs/0610047
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Achieving the Gaussian Rate–Distortion Function by Prediction

  2007cited by this paper
• A Coding Theorem for a Class of Stationary Channels with Feedback

  2007cited by this paper
• Capacity and Zero-Error Capacity of the Chemical Channel with Feedback

  2007cited by this paper
• \constrained Systems and Coding for Recording Channels," to Appear as Book Chapter in Handbook for Coding Theory, Symbolic Dynamics to Coding, Automata and System Theory 8. Symbolic Dynamics and System Theory

  2007cited by this paper
• Finite-state Modulation Codes for Data Storage, Ieee

  2007cited by this paper
• A Coding Theorem for a Class of Stationary Channels With Feedback

  2007cited by this paper
• Feedback Capacity of Stationary Gaussian Channels

  2006cited by this paper
• The Capacity of Channels With Feedback

  2006cited by this paper
• Capacity of Finite-State Channels with Time-Invariant Deterministic Feedback

  2006influential reference
• Achieving the Gaussian Rate-Distortion Function by Prediction

  2006cited by this paper
• Finite State Channels With Time-Invariant Deterministic Feedback

  2006cited by this paper
• Inference of Biologically Relevant Gene Influence Networks Using the Directed Information Criterion

  2006cited by this paper
• Feedback capacity of finite-state machine channels

  2005influential reference
• Value iteration for average cost Markov decision processes inBorel spaces

  2005cited by this paper
• The capacity of finite-State Markov Channels With feedback

  2005influential reference
• Conservation of mutual and directed information

  2005cited by this paper
• Feedback capacity of the first-order moving average Gaussian channel

  2004cited by this paper
• Codes for mass data storage systems

  2004cited by this paper
• Source coding with feedforward: Gaussian sources

  2004cited by this paper
• Control under communication constraints

  2004cited by this paper
• An input/output recursion for the trapdoor channel

  2002cited by this paper
• The Golden Ratio: The Story of Phi, the World's Most Astonishing Number

  2002cited by this paper
• Capacity results for the discrete memoryless network

  1999cited by this paper
• Directed information for channels with feedback

  1998cited by this paper
• Zero-error capacity for models with memory and the enlightened dictator channel

  1997cited by this paper
• Coding Strategies for the Permuting Jammer Channel

  1993cited by this paper
• Discrete-time controlled Markov processes with average cost criterion: a survey

  1993cited by this paper
• CAUSALITY, FEEDBACK AND DIRECTED INFORMATION

  1990cited by this paper
• Two results on the permuting mailbox channel

  1989cited by this paper
• Information Theory

  1987cited by this paper
• Combinatorial structure and capacity of the permuting relay channel

  1987influential reference
• Optimal coding strategies for certain permuting channels

  1987influential reference
• Universal decoding for finite-state channels

  1985cited by this paper
• Coding for a noisy channel with permutation errors (Ph.D. Thesis abstr.)

  1975cited by this paper
• Elementary classical analysis

  1974cited by this paper
• Enumerative source encoding

  1973cited by this paper
• Causality

  1938cited by this paper
• Ieee Transactions on Information Theory 2 on the Feedback Capacity of Power Constrained Gaussian Noise Channels with Memory

  year unknowncited by this paper

• On Secrecy Capacity of Binary Beampointing Channels with Block Memory and Feedback

  2025cites this paper
• Poset-Markov Channels: Capacity via Group Symmetry

  2025cites this paper
• InfoMat: Leveraging Information Theory to Visualize and Understand Sequential Data

  2025influential citation
• Communication over LQG Control Systems: A Convex Optimization Approach to Capacity

  2025cites this paper
• Signalling and Control in Nonlinear Partially Observable Stochastic Systems: An Information State Approach and LQG Applications

  2025cites this paper
• Signalling and Control of Nonlinear Partially Observable Stochastic Systems: Information States, Sufficient Statistics, and Applications

  2025cites this paper
• Capacity Bounds for Poset-Causal Channels Via Group Symmetry

  2025cites this paper
• Integrated Control and Communication in LQG Systems

  2025cites this paper
• A Memory-Based Reinforcement Learning Approach to Integrated Sensing and Communication

  2024cites this paper
• Zero-Error Capacity of the Chemical Residual Channel

  2024cites this paper
• The Duality Upper Bound for Finite-State Channels With Feedback

  2024influential citation
• Capacity of Finite State Channels With Feedback: Algorithmic and Optimization Theoretic Properties

  2024cites this paper
• Signalling and Control in Nonlinear Stochastic Systems: An Information State Approach with Applications

  2024cites this paper
• Feedback Capacity of Nonlinear Decision Models with General Noise: Gaussian Applications with Filtering and Control Riccati Equations

  2024cites this paper
• Code Rate Optimization via Neural Polar Decoders

  2024cites this paper
• Capacity of Finite-State Channels With Delayed Feedback

  2023influential citation
• Reinforcement Learning for Near-Optimal Design of Zero-Delay Codes for Markov Sources

  2023cites this paper
• Feedback Capacity of MIMO Gaussian Channels

  2023cites this paper
• Data-Driven Optimization of Directed Information Over Discrete Alphabets

  2023influential citation
• Finite-State Channels With Feedback and State Known at the Encoder

  2022influential citation
• Feedback Capacity of Ising Channels With Large Alphabet via Reinforcement Learning

  2022influential citation
• Neural Estimation and Optimization of Directed Information Over Continuous Spaces

  2022cites this paper
• Capacity of Finite State Channels with Feedback: Algorithmic and Optimization Theoretic Properties

  2022cites this paper
• An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning

  2021cites this paper
• The Feedback Capacity of Noisy Output Is the STate (NOST) Channels

  2021cites this paper
• Bounds on the Feedback Capacity of the (d, ∞)-RLL Input-Constrained Binary Erasure Channel

  2021cites this paper
• Feedback Capacity of MIMO Gaussian Channels

  2021cites this paper
• Computable Lower Bounds for Capacities of Input-Driven Finite-State Channels

  2020cites this paper
• Reinforcement Learning Evaluation and Solution for the Feedback Capacity of the Ising Channel with Large Alphabet

  2020cites this paper
• Shannon Meets Turing: Non-Computability and Non-Approximability of the Finite State Channel Capacity

  2020influential citation
• The Capacity of Multidimensional Permutations with Restricted Movement

  2020cites this paper
• Smart Meter Data Privacy

  2020cites this paper
• On the Capacity of the Flash Memory Channel with Feedback

  2020influential citation
• Feedback Capacity and Coding for the $(0,k)$ -RLL Input-Constrained BEC

  2019cites this paper
• Graph-Based Encoders and Their Performance for Finite-State Channels With Feedback

  2019influential citation
• Computable Upper Bounds for Unifilar Finite-State Channels

  2019cites this paper
• Computing the Feedback Capacity of Finite State Channels using Reinforcement Learning

  2019influential citation
• Master's thesis: Permutations With Restricted Movement.

  2019cites this paper
• Computable Upper Bounds on the Capacity of Finite-State Channels

  2019cites this paper
• Permutations With Restricted Movement

  2019cites this paper
• On the Structure of the Capacity Formula for General Finite State Channels with Applications

  2019cites this paper
• Privacy-Aware Smart Metering: Progress and Challenges

  2018cites this paper
• Capacity Achieving Distributions and Separation Principle for Feedback Gaussian Channels With Memory: the LQG Theory of Directed Information

  2018cites this paper
• Graph-based Encoders and their Achievable Rates for Channels with Feedback

  2018cites this paper
• Information Structures for Feedback Capacity of Channels With Memory and Transmission Cost: Stochastic Optimal Control and Variational Equalities

  2018cites this paper
• Finite-State Channel with Feedback and Causal State Information Available at the Encoder

  2018influential citation
• An optimal coding scheme for the BIBO channel with a no-repeated-ones input constraint

  2017cites this paper
• Feedback Capacity and Coding for the BIBO Channel With a No-Repeated-Ones Input Constraint

  2017cites this paper
• Variable-length codes for channels with memory and feedback: error-exponent upper bounds

  2017cites this paper
• Single Letter Expression of Capacity for a Class of Channels with Memory

  2017cites this paper
• Variable-length codes for channels with memory and feedback: Error-exponent lower bounds

  2017influential citation
• Coding for the $\boldsymbol \ell _\infty $ -Limited Permutation Channel

  2017cites this paper
• On the capacity of burst noise-erasure channels with and without feedback

  2017cites this paper
• Signalling of information in networked stochastic dynamical control systems

  2017cites this paper
• Capacity of Burst Noise-Erasure Channels With and Without Feedback and Input Cost

  2017cites this paper
• Feedback capacity and coding for the (0, k)-RLL input-constrained BEC

  2017cites this paper
• Single-letter bounds on the feedback capacity of unifilar finite-state channels

  2016cites this paper
• Information Structures of Maximizing Distributions of Feedback Capacity for General Channels with Memory & Applications

  2016cites this paper
• Extremum problems of directed information

  2016influential citation
• On the capacity of the general trapdoor channel with feedback

  2016cites this paper
• The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint

  2016cites this paper
• Information structures of capacity achieving distribution for channels with memory and feedback

  2016cites this paper
• The feedback capacity of the BIBO channel with a no-consecutive-ones input constraint

  2016cites this paper
• On the capacity of the chemical channel with feedback

  2016cites this paper
• Information Structures of Extremum Problems of Feedback Capacity for General Channels with Memory

  2016cites this paper
• A Single-Letter Upper Bound on the Feedback Capacity of Unifilar Finite-State Channels

  2016influential citation
• On AWGN Channels and Gaussian MACs with Variable-Length Feedback

  2016cites this paper
• Optimal Zero Delay Coding of Markov Sources: Stationary and Finite Memory Codes

  2016cites this paper
• Capacity of Remotely Powered Communication

  2016cites this paper
• Sequential Necessary and Sufficient Conditions for Capacity Achieving Distributions of Channels With Memory and Feedback

  2016cites this paper
• On Gaussian MACs With Variable-Length Feedback and Non-Vanishing Error Probabilities

  2016cites this paper
• A single-letter upper bound on the feedback capacity of unifilar finite-state channels

  2016cites this paper
• Capacity Achieving Distributions & Information Lossless Randomized Strategies for Feedback Channels with Memory: The LQG Theory of Directed Information-Part II

  2016cites this paper
• Information-theoretic analysis of refractory effects in the P300 speller

  2016cites this paper
• Zero-rate achievability of posterior matching schemes for channels with memory

  2016cites this paper
• Capacity of the (1, ∞)-RLL input-constrained erasure channel with feedback

  2015influential citation
• Information-Theoretic Privacy for Smart Metering Systems with a Rechargeable Battery

  2015cites this paper
• On the Capacity of Generalized Ising Channels

  2015cites this paper
• The Feedback Capacity of the (1, ∞)-RLL Input-Constrained Erasure Channel

  2015cites this paper
• Information Structures for Feedback Capacity of Channels with Memory and Transmission Cost: Stochastic Optimal Control & Variational Equalities-Part I

  2015cites this paper
• Information Structures of Capacity Achieving Distributions for Feedback Channels with Memory and Transmission Cost: Stochastic Optimal Control & Variational Equalities-Part I

  2015cites this paper
• The feedback capacity of the binary symmetric channel with a no-consecutive-ones input constraint

  2015cites this paper
• The Feedback Capacity of the $(1,\infty)$-RLL Input-Constrained Erasure Channel

  2015cites this paper
• Coding for the ℓ∞-limited permutation channel

  2015cites this paper
• Recursions for the trapdoor channel and an upper bound on its capacity

  2014cites this paper
• Capacity of a POST Channel With and Without Feedback

  2014cites this paper
• To Feed or Not to Feedback

  2014cites this paper
• Capacity of Binary Symmetric POST Channels

  2014cites this paper
• Coding for Half-Duplex Relay Networks and the Trapdoor Channel

  2014influential citation
• The feedback capacity of a class of finite state multiple access channels

  2014cites this paper
• Various Views on the Trapdoor Channel and an Upper Bound on its Capacity

  2014influential citation
• On the Capacity of Channels with Synchronization Errors

  2013cites this paper
• Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information

  2013cites this paper
• Feedback Communication and Control Over a Single Channel

  2013cites this paper
• Directed Information on Abstract Spaces: Properties and Variational Equalities

  2013cites this paper
• Capacity of a Simple Intercellular Signal Transduction Channel

  2013cites this paper
• Capacity of a POST channel with and without feedback

  2013cites this paper
• On the Capacity of Channels With Timing Synchronization Errors

  2013cites this paper
• An interpretation of the Cover and Leung capacity region for the MAC with feedback through stochastic control

  2012cites this paper
• Characterizing the Efficacy of the NRL Network Pump in Mitigating Covert Timing Channels

  2012influential citation