The Porosity of Additive Noise Channels

Vinith Misra, Tsachy WeissmanIEEE Trans. Information Theory 2014 · OpenReview

Abstract

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> , the capacity under finite-state encoding and decoding is 1 - ρ̅(z <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> ), 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.
BibTeX
@article{misra2014porosity,
  author = {Vinith Misra and Tsachy Weissman},
  title = {{The Porosity of Additive Noise Channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=mIxx6JQfuo},
}

Loading related content...

Figure