Bellman meets Shannon: On the Applications of Dynamic Programming in Capacity Computation

# 24


In this talk, we shall go over dynamic programming-based (or DP-based) methods for computing the capacity of finite-state channels (FSCs) or channels with memory, with and without feedback. First, we consider the setting of FSCs without feedback and derive lower bounds on the capacity for the broad class of input-driven channels, where the current channel state is a time-invariant deterministic function of the previous state and the current input. The lower bounds are based on a DP characterization of a bound on the maximum reverse directed information rate. We show that one can explicitly solve the said DP problem, and in the process, obtain useful achievable rates for the runlength-limited input-constrained binary erasure and binary symmetric channels. This is based on joint work with Prof. Navin Kashyap. We then move on to the setting of a class of FSCs with feedback, where the feedback capacity expression is amenable to formulation as a DP problem. In particular, we shall consider the inter-cell interference (ICI) channel in NAND flash memories and provide numerical evaluations of the feedback capacity. We also discuss an interesting scenario where a simple constrained code achieves the capacity, with and without feedback. The results are from joint work with Aryabhatt M.R. and Prof. Navin Kashyap.

Srikrishna Acharya B

V. Arvind Rameshwar is a PhD student at the Code Design and Analysis Lab, in the Department of ECE, working under the guidance of Prof. Navin Kashyap. A goldmedallist from BITS Pilani, Hyderabad Campus, he graduated with a B.E. (Hons.) in ECE, in 2018. His research interests lie in the information theory of finite-state channels.