De Bruijn序列的计数方法

发布时间：2024-03-02 20:08

　　在飞速发展的信息时代,反馈移位寄存器序列得到广泛应用。随着分析方法的不断改进,LFSR序列逐渐不能满足安全需求,因此NFSR序列得到重视,而de Bruijn序列作为一类最为重要的非线性反馈移位寄存器序列更是得到深入研究。本文主要研究了de Bruijn序列的计数问题。论文总结了de Bruijn序列已有的计数方法,包括De Bruijn图法、置换法和BEST定理法,对它们进行了详细地论述和整理。基于已有的计数方法,本文给出了一种新的计数方法:有根树法。这个方法利用有根树和de Bruijn序列的对应关系,由n阶de Bruijn序列得到de Bruijn图中以0ⁿ为根的无叉树,然后通过改变无叉树中任意状态的后继得到de Bruijn图中的以0ⁿ为根的所有有根树,最后通过树的个数归纳得到n+1阶de Bruijn序列的个数。本文给出的新计数方法是构造性的。根据新的计数方法,我们可以构造出所有的有根树,并可以构造出所有的de Bruijn序列。

【文章页数】：50 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 前言
    1.1 研究背景及意义
    1.2 研究现状
    1.3 本文主要内容
第二章 预备知识
    2.1 群的相关知识
    2.2 反馈移位寄存器的相关知识
    2.3 De Bruijn序列的相关知识
    2.4 De Bruijn序列的相关知识
第三章 De Bruijn序列基础计数法
    3.1 De Bruijn图计数法
    3.2 置换计数法
    3.3 BEST定理计数法
第四章 De Bruijn序列改进计数法
    4.1 二元有根树计数法
    4.2 k元有根树计数法
第五章 总结与展望
    5.1 结论总结
    5.2 展望
参考文献
致谢



本文编号：3917333