Two Dimensional Deletion Correcting Codes and their Applications
Two Dimensional Deletion Correcting Codes and their Applications
复制标题
二维缺失校正码及其应用
DOI：
10.1109/isit45174.2021.9517903
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Vu Van Khu
中科院分区：
文献类型：
--
作者：
Yeow Meng Chee;Manabu Hagiwara;Vu Van Khu
二维(2D)纠错码由于其广泛的应用而被研究了很长时间。最近，纠正行删除和列删除的二维码，也被称为纵横交错删除校正码，作为一维删除校正码的推广而被研究。在这项工作中，我们证明了2D删除纠错码对于纠正赛道记忆中的错误是有用的。从理论和实践的角度出发，我们对这些二维码进行了研究，旨在改进已有的研究成果。我们的第一个主要结果是构造了一个冗余度最大的最优(1，1)-交叉删除纠错码。然后，我们还提出了一种渐近最优交叉删除纠错码的构造方法，该纠错码的冗余度比已知结果要小。此外，由于纠正多个行删除的二维二进制代码等价于纠正多个删除的I1DQ-ary代码，因此我们还改进了已有的一些关于纠正多个删除的1DQ-ary代码的结果。
Two dimensional (2D) error correcting codes have been investigated for a long time owing to their numerous applications. Recently, 2D codes correcting row-deletions and column-deletions, also known as criss-cross deletion correcting codes, have been studied as a generalisation of one dimensional deletion correcting codes. In this work, we show that 2D deletion correcting codes are useful to correct errors in racetrack memories. With motivation from both theoretical and practical point of view, we study these 2D codes and aim to improve the previous known results. Our first main result is a construction of an optimal (1,1)-criss-cross deletion correcting code with the redundancy is at mostbits. Then, we also present a construction of an asymptotic optimal-criss-cross deletion correcting code with less redundancy than the best known results. Furthermore, since a 2D binary code correcting multiple row-deletions is equivalent to a I1D q-ary code correcting multiple deletions with large, we also improve some previous known results on 1D q-ary code correcting multiple deletions.