Anchor-Based Correction of Substitutions in Indexed Sets
Anchor-Based Correction of Substitutions in Indexed Sets
复制标题
索引集中基于锚的替换校正
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
A. Lenz;P. Siegel;A. Wachter;Eitan Yaakobi
基于DNA的数据存储的动机，我们研究了一个系统，其中数字信息存储在一个无序的集合中的几个向量在一个有限的字母表。每个向量都以一个唯一的索引开始，该索引表示它在整个数据集中的位置，并且不包含数据。本文讨论了在存在替换错误的情况下，这类索引集的纠错码的设计问题。我们提出了一个建设，有效地处理无序集设计代码时出现的挑战。使用一种新的机制，称为锚定，我们表明，它是可能的，以打击顺序损失的序列只有少量的冗余，这允许使用标准的编码技术，如张量积代码，以纠正序列内的错误。最后，我们得出的上限和下限所考虑的信道模型内的代码可实现的冗余，并验证我们的建设产生的冗余，是接近最好的可能实现的。我们的研究结果令人惊讶地表明，它需要更少的冗余来纠正错误的指数比在数据部分的向量。
Motivated by DNA-based data storage, we investigate a system where digital information is stored in an unordered set of several vectors over a finite alphabet. Each vector begins with a unique index that represents its position in the whole data set and does not contain data. This paper deals with the design of error-correcting codes for such indexed sets in the presence of substitution errors. We propose a construction that efficiently deals with the challenges that arise when designing codes for unordered sets. Using a novel mechanism, called anchoring, we show that it is possible to combat the ordering loss of sequences with only a small amount of redundancy, which allows to use standard coding techniques, such as tensor-product codes to correct errors within the sequences. We finally derive upper and lower bounds on the achievable redundancy of codes within the considered channel model and verify that our construction yields a redundancy that is close to the best possible achievable one. Our results surprisingly suggest that it requires less redundancy to correct errors in the indices than in the data part of vectors.
影响因子：
2.5
作者：
Jin Sima;Netanel Raviv;Jehoshua Bruck
通讯作者：
Jin Sima;Netanel Raviv;Jehoshua Bruck