论文标题
单个编辑的平衡重建代码
Balanced reconstruction codes for single edits
论文作者
论文摘要
由Levenshtein引发的序列重建问题的激励，由CAI \ emph {et al}引入重建代码。当有固定数量的嘈杂通道可用时，请打击错误。该主题的核心问题是设计具有尽可能大的大小的代码，以便可以从任何$ n $不同的嘈杂读取中唯一地重建每个代码，其中$ n $是固定的。在本文中，我们以这样的约束研究二进制重建代码，即每个代码字均衡，这是基于DNA的存储技术的普遍要求。对于具有单个编辑错误及其变体的所有可能的频道，我们为所有$ n $设计了渐近的最佳平衡重建代码，并表明其冗余符号的数量从$ \ frac {3} {2} {2} {2} \ log_2 n+o（1）$（1）$降低$ \ frac {1} {2} \ log_2n+\ log_2 \ log_2n+o（1）$，最后to $ \ frac {1} {2} {2} \ log_2n+o（1）$，但是以不同的速度，如果$ n $ n $是代码的长度。与不平衡的情况相比，我们的结果表明，平衡属性不会降低相应代码簿中重建代码的速率。
Motivated by the sequence reconstruction problem initiated by Levenshtein, reconstruction codes were introduced by Cai \emph{et al}. to combat errors when a fixed number of noisy channels are available. The central problem on this topic is to design codes with sizes as large as possible, such that every codeword can be uniquely reconstructed from any $N$ distinct noisy reads, where $N$ is fixed. In this paper, we study binary reconstruction codes with the constraint that every codeword is balanced, which is a common requirement in the technique of DNA-based storage. For all possible channels with a single edit error and their variants, we design asymptotically optimal balanced reconstruction codes for all $N$, and show that the number of their redundant symbols decreases from $\frac{3}{2}\log_2 n+O(1)$ to $\frac{1}{2}\log_2n+\log_2\log_2n+O(1)$, and finally to $\frac{1}{2}\log_2n+O(1)$ but with different speeds, where $n$ is the length of the code. Compared with the unbalanced case, our results imply that the balanced property does not reduce the rate of the reconstruction code in the corresponding codebook.
