超韧性叠加码：近最优构造与应用

《IEEE Transactions on Information Theory》：Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications

　　**摘要：**叠加码是一组二进制向量（码字）的集合，其特性是：任何向量都不包含在任何k个其他向量的布尔和中，从而可以在任意k个码字的组内唯一识别出这些码字。叠加码是基础的组合工具，应用范围涵盖分布式计算、数据检索到容错通信等多个领域。然而，经典叠加码依赖于严格的对齐假设，限制了它们在异步和易故障环境中的有效性，而这些环境在现代系统和应用中十分普遍。我们引入了超强韧性叠加码（URSCs），这是一类新的码，它在经典叠加码框架的基础上进行了扩展，通过确保更强的码字隔离特性和对两类对抗性扰动的抗扰能力来实现增强：任意循环移位和部分比特级损坏（翻转）。此外，URSCs还展现出通用性，能够在不需要预先知识的情况下，无缝适应任意数量的并发码字k。这是以往任何构造方法都未能实现的特性组合。我们首次提供了具有近最优长度的URSCs的多项式时间构造方法，在通用性更强的前提下，显著优于以往功能较为有限的构造方法，且无需预先知道并发码字的数量k。我们证明，我们的URSCs在多个应用领域中显著推动了技术的进步，包括非协调鸣叫网络，其中我们的码将本地广播的时间复杂度降低了将近两个数量级，以及多接入信道通信中的广义竞争解决。**I. 引言**叠加码由Kautz和Singleton于1964年提出[1]，是一种众所周知且被广泛使用的码类，以二进制矩阵表示，其中列对应码字。这些码具有以下独特特性：对于矩阵中任意一列子集，以及该子集中的任意一列c，都存在至少一行使得列c在该行的取值为1，而该子集中所有其他列在该行的取值均为0。这一特性使得可以在列子集中唯一识别出任意单列（码字）。