The porosity of additive noise sequences

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 is termed the porosity ρ̅(·) of an individual noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These results may be interpreted both as a channel-coding counterpart to Ziv and Lempel´s work in universal source coding, as well as an extension of the work by Lomnitz and Feder and Shayevitz and Feder on communication across modulo-additive channels.