标题： 基于聚合物的数据存储编码 显示英文标题

标题： Coding for Polymer-Based Data Storage

摘要： 受基于聚合物的数据存储平台的启发，这些平台使用二进制合成聚合物链作为记录介质，并通过串联质谱仪读取内容，我们提出了一种新的代码族，允许同时进行唯一字符串重建和多个质量误差的纠正。 我们考虑了两种方法：第一种方法涉及非对称错误，它基于引入冗余度，该冗余度与错误数量成线性关系，与字符串长度成对数关系。 该构造允许仅根据其有错误的子串组成多重集来唯一地重建字符串。 我们唯一重建方法的关键思想是将（移位的）Catalan-Bertrand路径与任意二进制字符串交错，并“反射”它们，以迫使相同长度的前缀和后缀具有不同的权重。 该方案的渐近码率是1，解码通过简化版本的回溯算法完成，该算法用于Turnpike问题。 对于对称错误，我们使用质量信息的多项式表征，并为此设置适应多项式评估码构造。 在此过程中，我们为常数个组成错误开发了新的高效解码算法，并表明该方案的冗余度与错误数量成二次关系，与码长成对数关系。 显示英文摘要

摘要： Motivated by polymer-based data-storage platforms that use chains of binary synthetic polymers as the recording media and read the content via tandem mass spectrometers, we propose a new family of codes that allows for both unique string reconstruction and correction of multiple mass errors. We consider two approaches: The first approach pertains to asymmetric errors and it is based on introducing redundancy that scales linearly with the number of errors and logarithmically with the length of the string. The construction allows for the string to be uniquely reconstructed based only on its erroneous substring composition multiset. The key idea behind our unique reconstruction approach is to interleave (shifted) Catalan-Bertrand paths with arbitrary binary strings and "reflect" them so as to force prefixes and suffixes of the same length to have different weights. The asymptotic code rate of the scheme is one, and decoding is accomplished via a simplified version of the backtracking algorithm used for the Turnpike problem. For symmetric errors, we use a polynomial characterization of the mass information and adapt polynomial evaluation code constructions for this setting. In the process, we develop new efficient decoding algorithms for a constant number of composition errors and show that the redundancy of the scheme scales quadratically with the number of errors and logarithmically with the codelength.