Exact Reconstruction From Insertions in Synchronization Codes
Exact Reconstruction From Insertions in Synchronization Codes
复制标题
通过插入同步代码进行精确重建
DOI：
--
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
L. Dolecek
中科院分区：
文献类型：
--
作者：
Frederic Sala;Ryan Gabrys;Clayton Schoeny;L. Dolecek
数据重构是一个应用广泛的重要领域。特别地，我们研究了从同步（插入/删除校正）码重建二进制和非二进制序列。这些序列被固定数量的符号插入（大于代码的最小编辑距离）破坏，产生许多不同的痕迹用于重建。我们希望知道精确重建所需的最小迹线数。这是Levenshtein为未编码序列解决的问题的一般版本。我们引入了序列在一定编辑距离上共享的公共超序列的最大数目的精确公式，给出了保证精确重构所需的不同迹线数目的上界。如果没有对码字的具体了解，这个上界就很紧。我们将我们的结果应用于著名的单删除/插入校正Varshamov-Tenengolts （VT）码，并表明大量的VT码字对达到精确重建所需的最坏情况输出数。我们还考虑了其他通道的扩展，如对抗性删除和插入/删除通道以及概率通道。
This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov–Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels.