| Paper ID | D7-S5-T4.3 |
| Paper Title |
Capacity and Construction of Recoverable Systems |
| Authors |
Ohad Elishco, Ben-Gurion University of the Negev, Israel; Alexander Barg, University of Maryland, College Park, United States |
| Session |
D7-S5-T4: Locally Recoverable Codes I |
| Chaired Session: |
Tuesday, 20 July, 23:20 - 23:40 |
| Engagement Session: |
Tuesday, 20 July, 23:40 - 00:00 |
| 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. In the first part of the paper we address the problem of finding the maximum growth rate of the set as well as constructions of explicit families (based on constrained coding) that approach the optimal rate. In the second part we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet, and the recovery condition requires that the Shannon entropy of the k-tuple conditioned on its l-neighborhood be bounded above by some epsilon>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 epsilon-recoverable measure from a corresponding deterministic system, and prove that for small epsilon the constructed measure is a maximizer of the metric entropy.
|
