A Stochastic Control Viewpoint on 'Posterior Matching'-style Feedback Communication Schemes

被引:16
作者
Coleman, Todd P. [1 ]
机构
[1] Univ Illinois, ECE Dept, Coordinated Sci Lab, Chicago, IL 60680 USA
来源
2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4 | 2009年
关键词
D O I
10.1109/ISIT.2009.5205844
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
This paper re-visits Shayevitz & Feder's recent 'Posterior Matching Scheme', a deterministic, recursive, capacity-achieving feedback encoding scheme for memoryless channels. We here consider the feedback encoder design problem from a stochastic control perspective. The state of the system is the posterior distribution of the message given current outputs of the channel. The per-trial reward is the average 'reduction in distance' of the posterior to the target unit step function. We show that the converse to the channel coding theorem with feedback upper bounds the optimal reward, and that the posterior matching scheme is an optimal policy. We illustrate that this 'reduction in distance' symbolism leads to the existence of a Lyapunov function on the Markov chain under this optimal policy, which leads to demonstration of achievability for all rates less than capacity.
引用
收藏
页码:1520 / 1524
页数:5
相关论文
共 12 条
[1]  
Bertsekas D. P., 2005, DYNAMIC PROGRAMMING, V1
[2]  
Cover T. M., 2001, Elements of information theory
[3]  
Dudley R. M., 2002, Real Analysis and Probability , Vol. 74 Cambridge Studies in Advanced Mathematics, V74
[4]  
Gray R. M., 1990, Entropy and Information Theory
[5]   SEQUENTIAL TRANSMISSION USING NOISELESS FEEDBACK [J].
HORSTEIN, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1963, 9 (03) :136-&
[6]  
Huber PJ., 2004, Robust statistics, V523
[7]  
Meyn S. P., 1993, MARKOV CHAINS STOCHA
[8]   Querying the user properly for high-performance brain-machine interfaces: Recursive estimation, control, and feedback information-theoretic perspectives [J].
Omar, Cyrus ;
Johnson, Miles ;
Bretl, Timothy W. ;
Coleman, Todd P. .
2008 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING, VOLS 1-12, 2008, :5216-+
[9]   The necessity and sufficiency of anytime capacity for stabilization of a linear system over a noisy communication link - Part I: Scalar systems [J].
Sahai, Anant ;
Mitter, Sanjoy .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (08) :3369-3395
[10]   A CODING SCHEME FOR ADDITIVE NOISE CHANNELS WITH FEEDBACK .2. NO BANDWIDTH CONSTRAINT [J].
SCHALKWIJK, JP ;
KAILATH, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1966, 12 (02) :172-+