Recoverable Systems

DOI10.1109/TIT.2022.3153330zbMATH Open1505.94062arXiv2010.00589OpenAlexW4214549771MaRDI QIDQ5088498

Publication date: 13 July 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every

k

-tuple of consecutive entries is uniquely recoverable from its

l

-neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the

k

-tuple conditioned on its

l

-neighborhood be bounded above by some

e p s i l o n > 0 .

We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an

e p s i l o n

-recoverable measure from a corresponding deterministic system.

Full work available at URL: https://arxiv.org/abs/2010.00589

zbMATH Keywords

metric entropy measures on infinite sequences recoverability condition

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)