Equivalence of Insertion/Deletion Correcting Codes for $d$-dimensional Arrays

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.

Accepted to IEEE International Symposium on Information Theory 2022