Stationary feedback channels

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.
Preliminary results 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.