二元De Bruijn序列的构造

作     者：林占祥 

作者单位：郑州大学 

学位级别：硕士

导师姓名：常祖领

授予年度：2021年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：反馈移位寄存器 并圈法 De Bruijn序列 后继规则 全序 

摘      要：De Bruijn序列因其良好的伪随机性,在如今的密码设计中应用越来越广泛。本文主要通过并圈法(CJM)来交换共轭对的后继状态,使得两个不同的圈合并成一个圈,直到变成一个2长的圈为止,即可得到一个de Bruijn序列。本文主要通过一些简单的反馈移位寄存器来快速的生成de Bruijn序列,主要成果包含两个方面。首先,在反字典序下提出三种基于CCR(Complementary Circulating Reg-ister)构造 de Bruijn 序列的算法;定义游程序,通过在每个圈中确定不同的唯一的以1开头后跟最长0-游程的状态来构造不同的序列。另一方面,对于 CSR(Complementary Summing Register)在反字典序下定义 necklace 序,通过在每个圈中确定不同的唯一状态来构造不同的de Bruijn序列;结合necklace序和重量序定义混合序,并进一步构造不同的序列。本文提出的算法生成下一个比特所需的空间复杂度为O(n),时间复杂度为O(n)到O(nlogn)。这些算法可以生成更多的de Bruijn序列,因此也具有较高的研究价值。