Feedback Capacity of Finite-State Channels with Causal State Known at the Encoder

Abstract

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 unitsized 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.