|Feedback Capacity of Finite-State Channels with Causal State Known at the Encoder
|Eli Shalom Shemuel, Oron Sabag, Haim Permuter, Ben Gurion University, Israel
|S.4: Channels with State
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|We consider finite state channels (FSCs) with feedback and state known causally at the encoder. This setting is general and includes both a channel with a Markovian state in which the state is input-independent, but also many other cases where the state is input-dependent such as the energy harvesting model. We characterize the capacity as a multi-letter expression that includes auxiliary random variables with memory. We derive a single-letter computable lower bound based on auxiliary directed graphs that are used to provide an auxiliary structure for the channel outputs and are called Q-graphs. This method is implemented for binary energy-harvesting model with a unit-sized battery and the noiseless channel, whose exact capacity has remained an open problem. We identify a structure of Q-graphs, with achievable rates that outperform the best achievable rates known in the literature.