Coding with frame synchronization for finite-state channels with feedback

We study the effect of feedback on the capacity of discrete, finite-state channels (FSCs). We focus on indecomposable FSCs - a class of channels in which the effect of the initial channel state on the state transition probabilities becomes negligible as time evolves. This class is frequently encountered in communication scenarios. In particular, we characterize a large family of indecomposable FSCs for which the channel state is determined by a finite number of the most recent channel inputs and outputs (e.g., multipath channels) and derive their feedback capacity. We present a capacity-achieving scheme that combines random coding with a Tx-Rx frame synchronization mechanism. We then show that the feedback capacity of these channels is independent of the initial channel state. These results extend to FSCs in which the receiver can identify when the optimal initial state is achieved using a synchronization scheme based on the channel outputs and partial channel state information (CSI). An example of such channels is a slowly-varying channel with intersymbol interference.