Computable bounds on the capacity of finite-state channels with feedback

Bashar Huleihel

Ben-Gurion University of the Negev

Abstract:

A finite-state channel (FSC) is a mathematical model for a discrete-time channel in which the channel output depends statistically on both the channel input and an underlying channel state. Such a channel is used to model a channel with memory since it allows the channel output to depend on past inputs and outputs via the channel state. Finding a computable characterization of the capacity of these fundamental channels is a long-standing open problem in information theory. Except for a few special cases where a closed-form single-letter formula can be obtained, for general FSCs, only a multi-letter formula exists. In this talk, I will introduce several methodologies to obtain computable upper and lower bounds on the capacity of FSCs with feedback. Further, it will be shown that, in many cases, the numerical bounds can be easily turned into simple analytical expressions. Lastly, I will present several examples of channels for which we derived capacity results or almost tight upper and lower bounds.

Biography:

Bashar Huleihel received his B.Sc. and M.Sc. degrees in electrical and computer engineering from the Ben-Gurion University of the Negev, Israel, in 2018 and 2020, respectively. He is currently pursuing a Ph.D. degree in electrical and computer engineering at the same institution. His research interests include information theory and machine learning. Bashar is the recipient of the Vatat fellowship for excellent Ph.D. students, and the High-tech, Bio-tech, and Chemo-tech fellowship for Ph.D. students.