de Bruijn序列的降级算法研究

本文主要探讨了de Bruijn序列之间的映射关系及其降级算法。de Bruijn序列，也称为M序列，是一种特殊的移位寄存器序列，因其极长的周期和高线性复杂度而在扩展频谱通信、跳频通信、保密通信和天文测距等多个领域中有广泛应用。现有的研究多关注于de Bruijn序列的生成和应用，而本文则侧重于降级算法的开发。 de Bruijn序列的一个关键特性是，对于一个m+1元n级的de Bruijn序列（DB(m, n)），其任意长度为n的子序列都是唯一的。这种序列可以通过一个LOOK-UP表标签来表示，并且可以通过特定的映射关系找到与之对应的n-1级de Bruijn序列。首先，通过n级de Bruijn序列构建其LOOK-UP表标签，然后修正这个标签以得到n-1级的LOOK-UP表标签，最后根据这个标签计算出n-1级的de Bruijn序列。这种方法揭示了不同级别de Bruijn序列之间的内在联系。 文章中，作者首先定义了一些基本概念和符号，如序列长度L=L(m+1)^n，L1=(m+1)^(n-1)，L2=(m+1)^(n-2)，以及de Bruijn序列的结构形式。序列的表示通常包括一个m+1进制的整数，且为了保持周期性，会在序列末尾添加0来填充。 在具体的降级算法中，作者引用了前人的工作，特别是关于de Bruijn序列升级算法的研究，如二元和多元序列的升级方法。不同于升级，降级算法的目标是从高级别的序列退化到低级别的序列，同时保持序列的唯一性和周期性。这个过程涉及到序列的子序列处理、LOOK-UP表标签的转换以及序列头部和尾部的操作。 为了实现这一目标，文章可能涉及的具体步骤包括：(1) 定义和构造n级de Bruijn序列的LOOK-UP表；(2) 设计映射函数，将n级序列的LOOK-UP表标签转换为n-1级的标签；(3) 使用修正后的标签生成n-1级序列的LOOK-UP表，并据此构建n-1级的de Bruijn序列；(4) 验证降级过程是否保持了序列的独特性质。 这篇论文提供了一种新的方法来理解和操作de Bruijn序列，这对于理解和生成这类序列，以及优化它们在通信和编码理论中的应用具有重要意义。通过降级算法，我们可以更有效地利用这些序列的特性，特别是在需要减少计算复杂度或存储需求的场景中。