Sequential Necessary and Sufficient Conditions for Capacity Achieving Distributions of Channels with Memory and Feedback

Abstract

We derive sequential necessary and sufficient conditions for any channel input conditional distribution ${\mathcal{P}}_{0,n}\triangleq \{P_{X_t|X^{t-1},Y^{t-1}}:t=0,\dots ,n\}$ to maximize the finite-time horizon directed information defined by $$C_{X^n\to Y^n}^{FB}\triangleq \underset{{\mathcal{P}}_{0,n}}{\sup }I(X^n\to Y^n),I(X^n\to Y^n)=\sum _{t=0}^{n}I(X^t;Y_t|Y^{t-1})$$ for channel distributions $\{P_{Y_t|Y^{t-1},X_t}:t=0,\dots ,n\}$ and $\{P_{Y_t|Y_{t-M}^{t-1},X_t}:t=0,\dots ,n\}$, where $Y^t\triangleq \{Y_0,\dots ,Y_t\}$ and $X^t\triangleq \{X_0,\dots ,X_t\}$ are the channel input and output random processes, and $M$ is a finite nonnegative integer. \noi We apply the necessary and sufficient conditions to application examples of time-varying channels with memory and we derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Further, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit $$C_{X^{\infty }\to Y^{\infty }}^{FB}\triangleq \underset{n⟶\infty }{\lim }\frac{1}{n+1}{C}_{X^n\to Y^n}^{FB}$$ without any á priori assumptions, such as, stationarity, ergodicity or irreducibility of the channel distribution. The necessary and sufficient conditions can be easily extended to a variety of channels with memory, beyond the ones considered in this paper.

57 pages, 9 figures, part of the paper was accepted for publication in the proceedings of the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain 10-15 July, 2016 (Date of submission of the conference paper: 25/1/2016)