The Feedback Capacity of Discrete Memoryless Channels with Input Constraints

Prof. Navin KASHYAP
Indian Institute of Science, Bangalore, India
Wednesday, 31 August, 2016
3:00 - 4:00pm
Room 833, Ho Sin Hang Engineering Building, CUHK

We consider the input-constrained feedback capacity of discrete memoryless channels. While we focus specifically on channels in which the inputs are binary sequences in which consecutive 1s are disallowed, the techniques apply more generally to any memoryless channel with finite input and output alphabets, and input sequences satisfying a constraint with finite memory. It is known that the feedback capacity computation for such channels can be formulated as an average-reward dynamic program (DP). In the case of the binary erasure channel with a no-consecutive-1s input constraint, we obtain an exact expression for the capacity by explicitly solving the Bellman equation associated with the DP formulation. Furthermore, the optimal policy of the DP leads to a simple and elegant zero-error coding scheme that achieves capacity. For a general binary-input, binary-output channel, we are able to obtain an explicit expression for feedback capacity under the no-consecutive-1s input constraint by solving the associated Bellman equation. The optimal policy for the DP suggests a capacity-achieving coding scheme based on posterior matching. 

 This is joint work with Oron Sabag and Haim Permuter (Ben-Gurion University, Israel).



Navin Kashyap received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1995, the M.S. degree in Electrical Engineering from the University of Missouri-Rolla in 1997, and the M.S. degree in Mathematics and the Ph.D. degree in Electrical Engineering from the University of Michigan, Ann Arbor, in 2001. During the period 2002-2003, he held a postdoctoral appointment (2002-2003) at the University of California San Diego. From 2004 until 2010, he was on the faculty of the Department of Mathematics and Statistics at Queen's University, Canada, where he still retains an appointment as an Adjunct Professor. Since January 2011, he has been an Associate Professor in the Department of Electrical Communication Engineering at the Indian Institute of Science, Bangalore. His research interests lie primarily in the application of combinatorial and probabilistic methods in information and coding theory.