Capacity of the trapdoor channel with feedback

Haim Permuter, Paul Cuff, Benjamine Van Roy, Tsachy Weissman

Research output: Contribution to journalArticle

76 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)3150-3165
Number of pages16
JournalIEEE Transactions on Information Theory
Volume54
Issue number7
DOIs
StatePublished - Jul 1 2008

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Bellman equation
  • Chemical channel
  • Constrained coding
  • Directed information
  • Feedback capacity
  • Golden-ratio
  • Infinite-horizon dynamic program
  • Trapdoor channel
  • Value iteration

Fingerprint Dive into the research topics of 'Capacity of the trapdoor channel with feedback'. Together they form a unique fingerprint.

  • Cite this