Capacity and zero-error capacity of the chemical channel with feedback

Haim Permuter; Paul Cuff; Benjamin Van Roy; Tsachy Weissinan

doi:10.1109/ISIT.2007.4557493

Capacity and zero-error capacity of the chemical channel with feedback

Haim Permuter, Paul Cuff, Benjamin Van Roy, Tsachy Weissinan

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.

Original language	English (US)
Title of host publication	Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007
Pages	1866-1870
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2007.4557493
State	Published - 2007
Event	2007 IEEE International Symposium on Information Theory, ISIT 2007 - Nice, France Duration: Jun 24 2007 → Jun 29 2007

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8101

Other

Other	2007 IEEE International Symposium on Information Theory, ISIT 2007
Country/Territory	France
City	Nice
Period	6/24/07 → 6/29/07

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2007.4557493

Cite this

@inproceedings{41a25b21b7d740578727671493302af8,

title = "Capacity and zero-error capacity of the chemical channel with feedback",

abstract = "We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.",

author = "Haim Permuter and Paul Cuff and {Van Roy}, Benjamin and Tsachy Weissinan",

year = "2007",

doi = "10.1109/ISIT.2007.4557493",

language = "English (US)",

isbn = "1424414296",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "1866--1870",

booktitle = "Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007",

note = "2007 IEEE International Symposium on Information Theory, ISIT 2007 ; Conference date: 24-06-2007 Through 29-06-2007",

}

Permuter, H, Cuff, P, Van Roy, B & Weissinan, T 2007, Capacity and zero-error capacity of the chemical channel with feedback. in Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007., 4557493, IEEE International Symposium on Information Theory - Proceedings, pp. 1866-1870, 2007 IEEE International Symposium on Information Theory, ISIT 2007, Nice, France, 6/24/07. https://doi.org/10.1109/ISIT.2007.4557493

Capacity and zero-error capacity of the chemical channel with feedback. / Permuter, Haim; Cuff, Paul; Van Roy, Benjamin et al.
Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007. 2007. p. 1866-1870 4557493 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Capacity and zero-error capacity of the chemical channel with feedback

AU - Permuter, Haim

AU - Cuff, Paul

AU - Van Roy, Benjamin

AU - Weissinan, Tsachy

PY - 2007

Y1 - 2007

N2 - We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.

AB - We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.

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

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

U2 - 10.1109/ISIT.2007.4557493

DO - 10.1109/ISIT.2007.4557493

M3 - Conference contribution

AN - SCOPUS:46749116284

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1866

EP - 1870

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -

Capacity and zero-error capacity of the chemical channel with feedback

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this