Stationary feedback channels

A coding theorem for a class of stationary channels with feedback

Young-Han Kim

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 m 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.