Capacity of finite-state channels with time-invariant deterministic feedback

Haim Permuter; Tsachy Weissman; Andrea Goldsmith

doi:10.1109/ISIT.2006.261599

Capacity of finite-state channels with time-invariant deterministic feedback

Haim Permuter, Tsachy Weissman, Andrea Goldsmith

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

13 Scopus citations

Abstract

We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input X^N and the output Y^N, i.e. C = limN→∞ 1/N max I (X^N → Y^N), where the maximization is over the causal conditioning probability Q(x^N||k^N-1) defined in this paper.

Original language	English (US)
Title of host publication	Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006
Pages	64-68
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2006.261599
State	Published - 2006
Externally published	Yes
Event	2006 IEEE International Symposium on Information Theory, ISIT 2006 - Seattle, WA, United States Duration: Jul 9 2006 → Jul 14 2006

Publication series

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

Other

Other	2006 IEEE International Symposium on Information Theory, ISIT 2006
Country/Territory	United States
City	Seattle, WA
Period	7/9/06 → 7/14/06

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2006.261599

Cite this

@inproceedings{5e22baa27c2f457f97b4964a2e6e99cf,

title = "Capacity of finite-state channels with time-invariant deterministic feedback",

abstract = "We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e. C = limN→∞ 1/N max I (XN → YN), where the maximization is over the causal conditioning probability Q(xN||kN-1) defined in this paper.",

author = "Haim Permuter and Tsachy Weissman and Andrea Goldsmith",

year = "2006",

doi = "10.1109/ISIT.2006.261599",

language = "English (US)",

isbn = "1424405041",

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

pages = "64--68",

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

note = "2006 IEEE International Symposium on Information Theory, ISIT 2006 ; Conference date: 09-07-2006 Through 14-07-2006",

}

Permuter, H, Weissman, T & Goldsmith, A 2006, Capacity of finite-state channels with time-invariant deterministic feedback. in Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006., 4035922, IEEE International Symposium on Information Theory - Proceedings, pp. 64-68, 2006 IEEE International Symposium on Information Theory, ISIT 2006, Seattle, WA, United States, 7/9/06. https://doi.org/10.1109/ISIT.2006.261599

Capacity of finite-state channels with time-invariant deterministic feedback. / Permuter, Haim; Weissman, Tsachy; Goldsmith, Andrea.
Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006. 2006. p. 64-68 4035922 (IEEE International Symposium on Information Theory - Proceedings).

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

TY - GEN

T1 - Capacity of finite-state channels with time-invariant deterministic feedback

AU - Permuter, Haim

AU - Weissman, Tsachy

AU - Goldsmith, Andrea

PY - 2006

Y1 - 2006

N2 - We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e. C = limN→∞ 1/N max I (XN → YN), where the maximization is over the causal conditioning probability Q(xN||kN-1) defined in this paper.

AB - We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e. C = limN→∞ 1/N max I (XN → YN), where the maximization is over the causal conditioning probability Q(xN||kN-1) defined in this paper.

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

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

U2 - 10.1109/ISIT.2006.261599

DO - 10.1109/ISIT.2006.261599

M3 - Conference contribution

AN - SCOPUS:33947665966

SN - 1424405041

SN - 9781424405046

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 64

EP - 68

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

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

Y2 - 9 July 2006 through 14 July 2006

ER -

Capacity of finite-state channels with time-invariant deterministic feedback

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this