Some results for special families of channels with memory

Abstract

The main concerns of this thesis are some special families of channels with memory, which are of great importance both in theory and in practical applications. Unlike discrete memoryless channels, the capacity of channels with memory generally admits no single-letter characterization and it is difficult to numerically evaluate the channel capacity.

As prominent examples of channels with memory, finite-state channels have attracted much interest. However, the numerical computation of the channel capacity of a finite-state channel is still an open problem. Recently, two algorithms have been proposed to numerically compute the channel capacity for a special family of finite-state channels with Markovian inputs. One sufficient condition for the convergence of the proposed algorithms is the concavity of mutual information rate with respect to some chosen parameters of the input Markov chains. In this thesis, under mild positivity conditions, concavity is proved at the high signal-to-noise ratio and counterexamples are given to show that concavity may fail in general.

The input-constrained discrete erasure channels are examples of channels with memory and the channel capacity is unknown and has been a long-standing open problem in information theory. In this thesis, an \explicit" formula of the mutual information rate for a discrete erasure channel with a Markovian input is derived. Moreover, if the input Markov chain is of first-order and supported on the (1; ∞)- run length limited constraint, the mutual information rate is shown to be strictly concave with respect to the transition probability of the input Markov chain. By comparing the asymptotics in the high SNR regime, feedback capacity is shown to be strictly larger than the non-feedback capacity, which disproves a statement of Shannon.

The other example of channels with memory is the recently proposed ash memory channel model, which possesses both input and output memory. In this thesis, the ash memory channels are shown to be indecomposable under rather weak conditions. Then the channel capacity is shown to be achievable by a stationary process and consequently, as its order tends to infinity, the Markov capacity converges to the real channel capacity. This result suggests that it is highly possible to apply the ideas and techniques in the computation of the capacity of finite-state channels, which are relatively better explored, to that of the capacity of ash memory channels.