A coding theorem for a class of stationary channels with feedback

Young-Han Kim

IEEE Transactions on Information Theory, vol. 54, no. 4, pp. 1488–1499, April 2008.
A shorter version appeared in Proceedings of IEEE International Symposium on Information Theory, pp. 1856–1860, Nice, France, June 2007.
IEEE AbstractPlus.

A coding theorem is proved for a class of stationary channels with feedback in which the output $Y_n = f(X_{n-m}^n, Z_{n-m}^n)$ is the function of the current and past symbols from the channel input X_n and the stationary ergodic channel noise Z_n . In particular, it is shown that the feedback capacity is equal to
$lim_{ntoinfty} sup_{p(x^n||y^{n-1})} frac{1}{n} I(X^n to Y^n)$
where $I(X^n to Y^n) = sum_{i=1}^n I(X^i; Y_i|Y^{i-1})$ denotes the Massey directed information from the channel input to the output, and the supremum is taken over all causally conditioned distributions $p(x^n||y^{n-1}) = prod_{i=1}^n p(x_i|x^{i-1},y^{i-1})$ . The main ideas of the proof are a classical application of the Shannon strategy for coding with side information and a new elementary coding technique for the given channel model without feedback, which is in a sense dual to Gallager’s lossy coding of stationary ergodic sources. A similar approach gives a simple alternative proof of coding theorems for finite state channels by Yang–Kavcic–Tatikonda, Chen–Berger, and Permuter–Weissman–Goldsmith.