The Porosity of Additive Noise Channels

Consider a binary modulo-additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process Z, the capacity is 1- H(Z) (H(·) denoting the entropy rate). It is shown analogously that when the noise is a deterministic sequence z^∞, the capacity under finite-state encoding and decoding is 1 - ρ̅(z^∞), where ρ̅(·) is Lempel and Ziv´s finite-state compressibility. This quantity, termed the porosity σ(·) of the channel, holds as the fundamental limit to communication - even when the encoder is designed with knowledge of the noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These results, both converse and achievability, may be interpreted as a channel-coding counterpart to Ziv and Lempel´s work in universal source coding, and also as an extension to existing work on communicating across modulo-additive channels with an individual noise sequence. In addition, a potentially more practical architecture is suggested that draws a connection with finite-state predictability, as introduced by Feder, Gutman, and Merhav.