A Rate-Optimal Construction of Codes with Sequential Recovery with Low Block Length
| Autor: | Babu, Balaji Srinivasan, Kini, Ganesh R., Kumar, P. Vijay |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | An erasure code is said to be a code with sequential recovery with parameters $r$ and $t$, if for any $s \leq t$ erased code symbols, there is an $s$-step recovery process in which at each step we recover exactly one erased code symbol by contacting at most $r$ other code symbols. In earlier work by the same authors, presented at ISIT 2017, we had given a construction for binary codes with sequential recovery from $t$ erasures, with locality parameter $r$, which were optimal in terms of code rate for given $r,t$, but where the block length was large, on the order of $r^{c^t}$, for some constant $c >1$. In the present paper, we present an alternative construction of a rate-optimal code for any value of $t$ and any $r\geq3$, where the block length is significantly smaller, on the order of $r^{\frac{5t}{4}+\frac{7}{4}}$ (in some instances of order $r^{\frac{3t}{2}+2}$). Our construction is based on the construction of certain kind of tree-like graphs with girth $t+1$. We construct these graphs and hence the codes recursively. Comment: Accepted for publication in NCC 2018 |
| Databáze: | arXiv |
| Externí odkaz: |
|