容错代码

《IEEE Transactions on Information Theory》：Break-Resilient Codes

　　

摘要：

我们研究了将数据编码为(n,t)抗断裂码（(n,t)-BRC）的问题，即一组长度为n的序列集合，即使它们在多达t个任意位置被对抗性折断，原始数据仍可被重建。我们建立了任何(n,t)-BRC冗余度的下界，并给出了能够以渐近可忽略项的精度达到这些下界的码构造方案。有趣的是，该问题与近期研究的撕裂纸张信道具有相似性，后者已在DNA数据存储的背景下被提出。

I. 引言

现代数据嵌入技术越来越多地在传统数字信道之外运作，在这些环境中，数据可能会被故意折断，而不仅仅是被随机噪声损坏。一个具有启发性质的应用示例是嵌入在三维打印组件中的数字指纹，用于身份验证或溯源。尽管文献[1]、[2]、[3]、[4]、[5]、[6]、[7]、[8]中已提出了多种在三维打印品中嵌入比特的技术，但数据重建依赖于物体物理几何的完整性。如果物体被折断为多个碎片，其结构中所存储的信息也将随之分裂为多个无明确顺序的片段，从而导致数据重建过程失败。