New Results on the Analysis of Discrete Communication Channels with Memory

Abstract

The reliable transmission of information bearing signals over a communication channel constitutes a fundamental problem in communication theory. An important objective in analyzing this problem is to understand and investigate its ﲩnformation theoretic aspects - i.e., to determine the fundamental limits to how efficiently one can encode information and still be able to recover it with negligible loss. In this work we address this problem for the case where the communication channel is assumed to have memory - i.e., the effect of noise lingers over many transmitted symbols. Our motivation is founded on the fact that most real-world communication channels have memory.We begin by proposing and analyzing a contagion communication channel. A contagion channel is a system in which noise propagates in a way similar to the spread of an infectious disease through a population; each ﲵnfavorable event (i.e., an error) increases the probability of future unfavorable events. A contagion-based model offers an interesting and less complex alternative to other models of channels with memory like the Gilbert-Elliott burst channel. We call the model set forth the Polya-contagion channel - discrete binary communication channel with additive errors modeled according to the famous urn scheme of George Polya for the spread of contagion.We nest consider discrete channels with arbitrary (not necessarily stationary ergodic) additive noise. Note that such channels need not be memoryless; in general, they have memory. We show that output feedback does not increase the capacity of such channels. The same result is also shown for a larger class of channels to which additive channels belong, the class of discrete symmetric channels with memory. These channels have the property that their inf-information rate is maximized for equally likely iid input processes.Finally, we impose average cost constraints on the input of the additive channels, rendering them non-symmetric. We demonstrate that in the case where the additive noise is a binary stationary mixing Markov process, output feedback can increase the capacity-cost function of these channels.