2012/05/31 by Vinith Misra, Misra, Vinith, Tsachy Weissman +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1205.6974
22 pages, 9 figures
arxiv created 2012/05/31 · openalex publication_date 2012/05/31 · arxiv updated 2012/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a binary additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process Z, the capacity is 1-ℍ(Z) (ℍ(⋅) 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 \underlineσ(⋅) of an individual noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These converse and achievability 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 to the work by Lomnitz and Feder and Shayevitz and Feder on communication across modulo-additive channels. Additionally, a slightly more practical architecture is suggested that draws a connection with finite-state predictability, as introduced by Feder, Gutman, and Merhav.