Name
Abstract | ||
|---|---|---|
We consider the problem of correcting insertion and deletion errors in the $d$-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is interesting to know whether the same properties of insertion/deletion correcting codes generalize to the $d$-dimensional space. In this work, we show that the equivalence between insertion and deletion correcting codes generalizes to the $d$-dimensional space. As a particular result, we show the following missing equivalence for arrays: a code that can correct $t_\mathrm{r}$ and $t_\mathrm{c}$ row/column deletions can correct any combination of $t_\mathrm{r}^{\mathrm{ins}}+t_\mathrm{r}^{\mathrm{del}}=t_\mathrm{r}$ and $t_\mathrm{c}^{\mathrm{ins}}+t_\mathrm{c}^{\mathrm{del}}=t_\mathrm{c}$ row/column insertions and deletions. The fundamental limit on the redundancy and a construction of insertion/deletion correcting codes in the $d$-dimensional space remain open for future work. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/ISIT50566.2022.9834350 | International Symposium on Information Theory (ISIT) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evagoras Stylianou | 1 | 0 | 0.68 |
| Lorenz Welter | 2 | 1 | 2.04 |
| Rawad Bitar | 3 | 0 | 1.01 |
| Antonia Wachter-Zeh | 4 | 129 | 33.65 |
| Eitan Yaakobi | 5 | 604 | 70.41 |