加元算法生成m+2元de Bruijn序列的构造方法

本文主要探讨了生成de Bruijn序列的一种加元算法，特别针对的是m+1元的序列扩展到m+2元。de Bruijn序列是一种特殊的循环移位寄存器序列，由于其巨大的码字数量和高的线性复杂度，被广泛应用于扩展频谱通信、跳频通信、保密通信系统以及天文测距等领域。 文章首先介绍了de Bruijn序列的基本概念，它是具有最长周期的序列，当一个m+1元序列的任何长度为n的子序列在循环中都是唯一的，这个序列就被定义为m+1元n级de Bruijn序列，如DB(m,n)。这里的m+1个符号通常取自集合∑m+1，例如{0,1,...,m}。 文献[10,11]和[12]分别研究了二元和多元de Bruijn序列的生成算法升级，而文献[13,14]则提供了任意元de Bruijn序列的升级和降级方法。相比之下，本文提出的加元算法不同于文献[5]，它基于文献[1]中的Look-up表和Look-up表标签的概念，这是一种创新的方法，旨在高效生成任意元任意级的de Bruijn序列，特别是对二元序列的生成效率有显著提升。 加元算法的核心步骤包括： 1. 首先，从一个给定的m+1元de Bruijn序列中构建Look-up表和相应的Look-up表标签，这一步涉及到了节点链的管理。 2. 然后，通过分析Look-up表标签，产生多个m+1元Look-up表标签，这些新的标签是加元操作的基础。 3. 合成这些Look-up表标签，构造出一个新的m+2元Look-up表标签，这个标签代表了加元后的序列结构。 4. 最后，根据新生成的m+2元Look-up表标签，通过循环移位和替换规则，生成完整的m+2元de Bruijn序列。 这种方法的优势在于，它能够保持原有的序列结构和周期性，并且在增加元数的同时，维持了序列的唯一性。这对于需要频繁改变元数或扩展序列长度的应用场景是非常有用的。通过这种方式，文章提供了一种简洁且有效的方法来扩展和生成复杂的de Bruijn序列，对于实际的通信和信息安全系统设计具有重要意义。