论文标题
对抗性撕裂的代码
Adversarial Torn-paper Codes
论文作者
论文摘要
我们研究了对抗性撕裂的通道。此问题是由DNA数据存储中的应用激发的，其中携带信息的DNA链可能会分解为较小的零件，这些零件被过失。我们的模型将先前研究的概率环境扩展到了最坏的情况。我们为可能的任何参数开发了代码构造，该通道的任何参数都可能是可能的，并显示我们的构造实现渐近最佳速率，同时允许有效地编码和解码。最后，我们将结果扩展到相关的设置，包括多链存储，存在替换错误或不完整的覆盖范围。
We study the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry information may break into smaller pieces which are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We develop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show our constructions achieve asymptotically optimal rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.
