Capacity of Finite State Channels with Time-Invariant Feedback

Many of the communication channels encountered in practice, and especially wireless channels, have memory, which means that the behavior of the channels changes according to some pattern. We model this behavior through the notion of states, and we consider communication over point-to-point finite state channels (FSCs), and over finite state multi-access channels (FS-MACs) with feedback. The feedback considered here may be an arbitrary time-invariant deterministic function of the output samples. For the FSCs, a sequence of achievable rates and a sequence of upper bounds on the capacity are derived. The achievable rates and the upper bounds in the sequence are computable, and the limits of the sequences exist. We further show that when the channel is stationary, indecomposable and has no intersymbol interference (ISI), its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e., C = limN→infinity1 N max I(XN → YN), where the maximization is taken over the causal conditioning probability Q(xN-- zN-1) defined in this thesis. The causal conditioning distribution and the directed information expression play a significant role in the analysis and properties that are analogue to regular conditioning and mutual information are derived. A particular example of a FSC is the trapdoor channel. We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels; channels in which the state is a deterministic function of the output, input and previous state. The trapdoor channel is an instance that admits a simple analytic solution. Finally, a Finite-State Multiple Access Channel (FS-MAC) with time-invariant feedback is considered. We characterize both an inner and an outer bound for this region, using directed information, and, as in the analysis of the feedback capacity of FSC, causality plays a significant role; in particular, causal conditioning distributions are used rather than the regular conditioning distributions. These bounds are shown to coincide, and hence yield the capacity region, of FS-MACs where the state process is stationary and ergodic and not affected by the inputs. Though 'multi-letter' in general, our results yield explicit conclusions when applied to specific scenarios of interest. In particular, we identify a large class of FS-MACs under which feedback does not enlarge the capacity region, and for which source-channel separation holds.