Mass Error-Correction Codes for Polymer-Based Data Storage
Mass Error-Correction Codes for Polymer-Based Data Storage
复制标题
用于基于聚合物的数据存储的大规模纠错码
DOI：
10.1109/isit44484.2020.9174404
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
O. Milenkovic
中科院分区：
文献类型：
--
作者：
Ryan Gabrys;Srilakshmi Pattabiraman;O. Milenkovic
我们考虑纠正二进制聚合物串编码信息中的质量读出错误的问题。我们的工作建立在使用组合多重集 [1] 和 [2] 中提出的独特字符串重建框架解决字符串重建问题的结果的基础上。基于二元聚合物的数据存储系统 [3] 通过设计两个质量显着不同的分子来表示符号 {0,1} 并通过嘈杂的串联质谱法进行读出。串联质谱仪将要读取的字符串分段为较短的子字符串，并且仅报告它们的质量，通常由于不精确的电离而产生错误。根据复合多重集对碎片过程输出进行建模，允许设计渐近最优代码，该代码能够通过使用加泰罗尼亚路径的导数进行唯一重建和单个质量误差的校正[2]。然而，目前尚无已知的多质量纠错解决方案。我们的工作通过描述第一个多重纠错码来解决这个问题，该码使用多项式因式分解方法来解决收费公路问题 [4] 以及 [1] 中描述的相关因式分解。将 Reed-Solomon 类型编码冗余添加到相应的多项式中，可以使用 ${\mathcal{O}}\left( {{t^2}\log k} \right)$ 冗余位在多项式时间内纠正 t 个质量错误，其中 k 是信息串长度。冗余可以改进为${\mathcal{O}}(t + \log k)$。然而，目前还没有针对该方案在 t 和 n 中运行多项式时间的解码算法，其中 n 是编码字符串的长度。
We consider the problem of correcting mass readout errors in information encoded in binary polymer strings. Our work builds on results for string reconstruction problems using composition multisets [1] and the unique string reconstruction framework proposed in [2]. Binary polymer-based data storage systems [3] operate by designing two molecules of significantly different masses to represent the symbols {0,1} and perform readouts through noisy tandem mass spectrometry. Tandem mass spectrometers fragment the strings to be read into shorter substrings and only report their masses, often with errors due to imprecise ionization. Modeling the fragmentation process output in terms of composition multisets allows for designing asymptotically optimal codes capable of unique reconstruction and the correction of a single mass error [2] through the use of derivatives of Catalan paths. Nevertheless, no solutions for multiple-mass error-corrections are currently known. Our work addresses this issue by describing the first multiple-error correction codes that use the polynomial factorization approach for the Turnpike problem [4] and the related factorization described in [1]. Adding Reed-Solomon type coding redundancy into the corresponding polynomials allows for correcting t mass errors in polynomial time using ${\mathcal{O}}\left( {{t^2}\log k} \right)$ redundant bits, where k is the information string length. The redundancy can be improved to ${\mathcal{O}}(t + \log k)$. However, no decoding algorithm that runs polynomial-time in both t and n for this scheme are currently known, where n is the length of the coded string.