论文标题
插入/删除校正代码的等效性$ d $二维数组
Equivalence of Insertion/Deletion Correcting Codes for $d$-dimensional Arrays
论文作者
论文摘要
我们考虑在$ d $维空间中纠正插入和删除错误的问题。对于矢量（一维空间），该问题已被充分理解，最近研究了阵列（二维空间）。对于向量和阵列，问题是由几种实际应用（例如基于DNA的存储和赛马场记忆）的动机。从理论的角度来看，很有趣的是知道插入/删除的相同属性是否校正代码将概括为$ d $维空间。在这项工作中，我们表明插入和删除校正代码之间的等效性概括为$ d $维空间。作为一个特别的结果，我们显示了以下数组的缺失等效性：可以纠正$ t_ \ mathrm {r} $和$ t_ \ mathrm {c} $行/列删除的代码可以纠正任何组合美元$ t_ \ mathrm {c}^{\ mathrm {ins}}+t_ \ mathrm {c}^{\ mathrm {del}} = T_ \ Mathrm {c} $ row/count/colund/colund/colund insertions and deletions。 $ d $维空间中插入/删除校正代码的冗余和构建的基本限制仍然开放，以便将来的工作。
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.
