Capacity of the trapdoor channel with feedback

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

doi:10.1109/TIT.2008.924681

Capacity of the trapdoor channel with feedback

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

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

88 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 language	English (US)
Pages (from-to)	3150-3165
Number of pages	16
Journal	IEEE Transactions on Information Theory
Volume	54
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2008.924681
State	Published - Jul 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

Access to Document

10.1109/TIT.2008.924681

Cite this

@article{275d12ffadf54b57a183bc4d75d39d70,

title = "Capacity of the trapdoor channel with feedback",

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.",

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

author = "Haim Permuter and Paul Cuff and {Van Roy}, Benjamine and Tsachy Weissman",

note = "Funding Information: Manuscript received October 8, 2006; revised January 25, 2008. This work was supported by the National Science Foundation (NSF) under Grants CCR-0311633, CCF-0515303, IIS-0428868, and the NSF CAREER Grant. The material in this paper was presented in part at the 44th Annual Allerton Conference on Communications, Control, and Computers, Monticello, IL, September 2006, and the IEEE International Symposium on Information Theory, Nice, France, June 2007 H. Permuter, P. Cuff, and B. Van Roy are with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: haim1@stanford.edul; pcuff@stanford.edu; bvr@stanford.edu).",

year = "2008",

month = jul,

doi = "10.1109/TIT.2008.924681",

language = "English (US)",

volume = "54",

pages = "3150--3165",

journal = "IRE Professional Group on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Capacity of the trapdoor channel with feedback

AU - Permuter, Haim

AU - Cuff, Paul

AU - Van Roy, Benjamine

AU - Weissman, Tsachy

N1 - Funding Information: Manuscript received October 8, 2006; revised January 25, 2008. This work was supported by the National Science Foundation (NSF) under Grants CCR-0311633, CCF-0515303, IIS-0428868, and the NSF CAREER Grant. The material in this paper was presented in part at the 44th Annual Allerton Conference on Communications, Control, and Computers, Monticello, IL, September 2006, and the IEEE International Symposium on Information Theory, Nice, France, June 2007 H. Permuter, P. Cuff, and B. Van Roy are with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: haim1@stanford.edul; pcuff@stanford.edu; bvr@stanford.edu).

PY - 2008/7

Y1 - 2008/7

N2 - 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.

AB - 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.

KW - Bellman equation

KW - Chemical channel

KW - Constrained coding

KW - Directed information

KW - Feedback capacity

KW - Golden-ratio

KW - Infinite-horizon dynamic program

KW - Trapdoor channel

KW - Value iteration

UR - http://www.scopus.com/inward/record.url?scp=46749102975&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46749102975&partnerID=8YFLogxK

U2 - 10.1109/TIT.2008.924681

DO - 10.1109/TIT.2008.924681

M3 - Article

AN - SCOPUS:46749102975

SN - 0018-9448

VL - 54

SP - 3150

EP - 3165

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

IS - 7

ER -

Capacity of the trapdoor channel with feedback

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this