The porosity of additive noise sequences
Vinith Misra, Tsachy Weissman · 2012
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.