Clustering-Correcting Codes
Clustering-Correcting Codes
复制标题
聚类校正代码
DOI：
10.1109/isit.2019.8849737
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Wachter
中科院分区：
文献类型：
--
作者：
Tal Shinkar;Eitan Yaakobi;A. Lenz;A. Wachter
本文提出了一类新的码族，称为聚类纠错码。这一系列的代码是由存储在基于DNA的存储系统中的数据的特殊结构驱动的。存储在这些系统中的数据具有无序序列的形式，也称为链，每条链都被合成数千到数百万次，其中一些拷贝在测序过程中被读回。由于链的无序结构，解码过程中的一项重要任务是将它们以正确的顺序放置。这通常通过为索引分配一部分链来实现。然而，在索引字段中存在错误时，关于链的顺序的重要信息可能会丢失。纠错码确保如果两个链的索引字段之间的距离很小，那么它们的数据字段之间将有很大的距离。它示出了如何使这个属性能够将链在一起，即使在错误的存在下，在其正确的集群。我们提出了上下限的聚类校正码的大小和明确的建设，这些代码只使用一个单一的冗余位。
A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating a part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost.Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, then there will be a large distance between their data fields. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single bit of redundancy.