Duplication-correcting codes
Duplication-correcting codes
复制标题
重复校正代码
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
A. Lenz;A. Wachter;Eitan Yaakobi
在这项工作中，我们提出了纠正多个连续符号重复的结构。这些错误被称为串联重复，其中重复了一系列符号。分别作为腔圆底重复，其中序列以反向顺序重复。我们将这些构造的冗余与从球体填料参数获得的代码大小上限进行比较。证明串联删除的代码基数的上限也是插入串联重复的上限，我们根据此特殊的串联删除误差得出界限，因为这会导致更紧密的范围。我们对基数的上限直接暗示了冗余的下限，这与最知名的结构的冗余相比，校正了任意爆发插入。我们的结果表明，校正后，重复需要比串联重复的校正更大，并且均显着小于任意爆发插入。
In this work, we propose constructions that correct duplications of multiple consecutive symbols. These errors are known as tandem duplications, where a sequence of symbols is repeated; respectively as palindromic duplications, where a sequence is repeated in reversed order. We compare the redundancies of these constructions with code size upper bounds that are obtained from sphere packing arguments. Proving that an upper bound on the code cardinality for tandem deletions is also an upper bound for inserting tandem duplications, we derive the bounds based on this special tandem deletion error as this results in tighter bounds. Our upper bounds on the cardinality directly imply lower bounds on the redundancy which we compare with the redundancy of the best known construction correcting arbitrary burst insertions. Our results indicate that the correction of palindromic duplications requires more redundancy than the correction of tandem duplications and both significantly less than arbitrary burst insertions.