A Communication Channel Modeled on Contagion

Abstract

We introduce a binary additive communication channel with memory. The noise process of the channel is generated according to the contagion model of George Polya; our motivation is the empirical observation of Stapper et. al. that defects in semiconductor memories are well described by distributions derived from Polya's urn scheme. The resulting channel is stationary but not ergodic, and it has many interesting properties.<P>We First derive a maximum likelihood (ML) decoding algorithm for the channel; it turns out that ML decoding is equivalent to decoding a received vector onto either the closest codeword or the codeword that is farthest away, depending on whether an ﲡpparent epidemic has occurred. We next show that the Poly-contagion channel is an ﲡveraged channel in the sense of Ahlswede (and others) and that its capacity is zero. We then demonstrate that the Poly- contagion channel is a counter-example to the adage, ﲭemory cannot decrease capacity ; the capacity of the Poly-contagion channel is actually less than that of the associated memoryless channel. Finally, we consider a finite-memory version of the Poly-contagion model; this channel is (unlike the original) ergodic with a non-zero capacity that increases with increasing memory.