检索结果-南通市图书馆

基于编织法的de Bruijn序列差异性研究

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

密码学报 2020年第2期7卷 169-178页

作者：王向宇王中孝战略支援部队信息工程大学郑州450001

由于de Bruijn序列具有周期最大、元素分布均衡、线性复杂度较高等良好的伪随机性质,因此在序列密码的研究领域中占有重要位置,其中de Bruijn序列的构造问题一直是研究的热点问题之一.目前已有多种构造de Bruijn序列的方法,而对于构造所... 详细信息

由于de Bruijn序列具有周期最大、元素分布均衡、线性复杂度较高等良好的伪随机性质,因此在序列密码的研究领域中占有重要位置,其中de Bruijn序列的构造问题一直是研究的热点问题之一.目前已有多种构造de Bruijn序列的方法,而对于构造所得de Bruijn序列的差异性则相对研究较少,本文主要讨论基于编织法得到的de Bruijn序列的差异性.基于编织法,高杨等人给出了一种由一条n级de Bruijn序列来构造四条2n级de Bruijn序列的方法.由于这四条2n级de Bruijn序列由两条编织序列I1和I2唯一决定,因此de Bruijn序列的差异性可由这两条编织序列的差异性来刻画,而这两条编织序列的差异性又可以转化为两个指定映射的差异性.映射的差异性问题进一步可归结为对n长状态(e0e2…e2n-2)来源序列的研究,最终本文得到两个映射出现差异的充要条件,进而得到这两个映射的差异数和差异率2(2^n-1+1)^-1.据此可知,由编织法构造的编织序列的差异率随着级数的增大而减少.

关键词： de Bruijn序列编织法编织序列差异性

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

二元de Bruijn序列的构造

二元De Bruijn序列的构造

作者：林占祥郑州大学

学位级别：硕士

de Bruijn序列因其良好的伪随机性,在如今的密码设计中应用越来越广泛。本文主要通过并圈法(CJM)来交换共轭对的后继状态,使得两个不同的圈合并成一个圈,直到变成一个2长的圈为止,即可得到一个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序列,因此也具有较高的研究价值。

关键词：反馈移位寄存器并圈法 de Bruijn序列后继规则全序

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

de Bruijn序列的快速生成算法研究

De Bruijn序列的快速生成算法研究

作者：朱云龙郑州大学

学位级别：硕士

de Bruijn序列因具有周期大、线性复杂度大、游程分布平衡等性质在密码学等领域有着广泛的应用,研究其快速生成算法具有重要意义。并圈法（CJM）是一种常用的快速生成de Bruijn序列的算法,是指通过改变共轭对的后继,将反馈移位寄存器（... 详细信息

de Bruijn序列因具有周期大、线性复杂度大、游程分布平衡等性质在密码学等领域有着广泛的应用,研究其快速生成算法具有重要意义。并圈法（CJM）是一种常用的快速生成de Bruijn序列的算法,是指通过改变共轭对的后继,将反馈移位寄存器（FSR）生成的不同的周期序列合并,从而生成成一个周期序列,即de Bruijn序列。并圈法能够基于给定FSR生成后继规则,从而构造对应de Bruijn序列。该方法的时间复杂度和空间复杂度均为O（n）,在硬件和软件实现上都具有明显优势,因此被认为是构造de Bruijn序列的一类重要方法。本文的研究内容主要分为两个部分。第一部分研究了以f（x）=xn+xn-1+x+1为特征多项式的二元线性反馈移位寄存器（LFSR）,利用并圈法生成de Bruijn序列的方法。该类LFSR的圈结构有较好的性质,基于此本文主要给出了两类后继规则,每类后继规则都能够生成n的指数数量的de Bruijn序列。其中第一类后继规则的证明根据Jansen关于de Bruijn序列构造方法的证明演变而来,将LFSR生成的不同的二元周期序列（圈）根据代表向量（代表元）的字典序进行排序,并使得除代表元字典序序最小的圈外,其余所有圈代表元的共轭向量均在更小序的周期序列中。对于第二类后继规则,本文给出了一种更一般化的证明方法,可以推广至更多圈结构具有某些性质的LFSR应用中。在本文中所研究的LFSR是一个新的LFSR,且在de Bruijn序列构造方法的证明上也有所创新。第二部分研究了多元情况下以f（x）=xn+1为特征多项式的多元LFSR,通过构造后继规则来生成de Bruijn序列的方法。因为多元时元素较多,本文利用了一种构造集合的方法来确定圈之间的链接,目前多元de Bruijn序列领域相比成果较少,且本文中的研究涵盖了这些内容,因此该研究也具有重要的应用价值。

关键词：周期序列 de Bruijn序列反馈移位寄存器后继规则并圈法

Necklace和de Bruijn序列生成方法的研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Necklace和de Bruijn序列生成方法的研究

作者：屈萌杉郑州大学

学位级别：硕士

de Bruijn序列是一类非常重要的非线性移位寄器序列,在密码学研究中起着至关重要的作用。Necklace是一个等价类中字典序最小的字符串,而Lyndon word是一个非周期的necklace,它们不仅在组合和计算机领域有重大的研究意义,还对de bruijn... 详细信息

de Bruijn序列是一类非常重要的非线性移位寄器序列,在密码学研究中起着至关重要的作用。Necklace是一个等价类中字典序最小的字符串,而Lyndon word是一个非周期的necklace,它们不仅在组合和计算机领域有重大的研究意义,还对de Bruijn序列的一种特殊形式的构造提供了新的方法。有学者曾经提出降序生成所有k元n级的necklace的算法,在此基础上又提出生成最小的de Bruijn序列的算法。除此之外,还有很多问题值得深入研究。本文主要考虑2元necklace和de Bruijn序列的构造问题。在已有生成necklace的算法的基础上,通过进一步的改进和创新,得出了三种新的生成necklace的算法,这些新的算法都是依据necklace的定义和性质得到的,而它们的不同之处在于necklace的排序方式发生了变化。之后基于新的生成necklace的算法,进一步探究如何生成de Bruijn序列。我们发现将生成的necklace进行周期约化或者先将其按条件循环移位后再进行周期约化,然后并置,就可以得到新的de Bruijn序列。这些新的生成necklace和de Bruijn序列的算法相对之前已有的算法更加简便,同时具有更好的应用价值和理论研究价值。

关键词： necklace Lvndon word de Bruijn序列循环移位周期约化

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

取反法构造n级de Bruijn序列

取反法构造n级De Bruijn序列

作者：耿志宇郑州大学

学位级别：硕士

二元n阶de Bruijn序列是具有2周期的序列,在一个周期中,任意的二元n长向量都出现且只出现一次。de Bruijn序列是一类非常重要的非线性反馈移位寄存器序列,在很多领域中都有重要应用。de Bruijn序列的构造是de Bruijn序列研究的一个重点... 详细信息

二元n阶de Bruijn序列是具有2周期的序列,在一个周期中,任意的二元n长向量都出现且只出现一次。de Bruijn序列是一类非常重要的非线性反馈移位寄存器序列,在很多领域中都有重要应用。de Bruijn序列的构造是de Bruijn序列研究的一个重点研究问题,而利用贪婪算法来构造de Bruijn序列是一类重要的构造方法。论文总结了已有的基于贪婪算法的de Bruijn序列的构造方法,提出了推广的优先取反算法,并给出了生成de Bruijn序列的关于反馈函数和初始向量的一个充分条件。新的算法包含所有已知的基于贪婪算法的de Bruijn序列构造方法作为特例。对于不满足条件的反馈函数,我们修改了算法,使之可以用来生成de Bruijn序列。我们还考虑了一般情形,对于任意的反馈函数,我们提出了类似于并圈法的概念,通过确定某些特殊状态的后继,我们的算法仍然可以生成de Bruijn序列。本文的结果可以用来构造更多新的de Bruijn序列,具有重要的理论意义和应用价值。

关键词：非线性反馈移位寄存器(NFSR) de Bruijn序列圈结构优先取反反馈函数

基于非线性反馈移位寄存器的de Bruijn序列的设计

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于非线性反馈移位寄存器的de Bruijn序列的设计

作者：谢坚锐西安电子科技大学

学位级别：硕士

移位寄存器序列中的M序列又称de Bruijn序列,由于有着良好的随机性质及密钥量大与难以破解的特点,在保密通信中具有非常重要的地位。近年来,诸如相关攻击与代数攻击的密码分析技术的发展,使得非线性反馈移位寄存器有取代线性反馈移位寄... 详细信息

移位寄存器序列中的M序列又称de Bruijn序列,由于有着良好的随机性质及密钥量大与难以破解的特点,在保密通信中具有非常重要的地位。近年来,诸如相关攻击与代数攻击的密码分析技术的发展,使得非线性反馈移位寄存器有取代线性反馈移位寄存器、成为相关学界的研究主流之势。本文着眼于移位寄存器的几何结构,以分析它们的状态图为出发点,尝试构造de Bruijn序列,取得了以下成果:（1）在MATLAB平台实现了依据反馈函数对任意反馈移位寄存器的状态图进行整体上的刻画,并统计相关特征,包括圈个数、连通分支个数、三叉点和叶子点等。实验数据显示,在小于17阶的情况下,该程序可以相当快速得到结果。（2）在Golomb给出的PSR和CSR的圈个数公式的基础上,给出并证明了PSR和CSR的圈长分布公式,完全确定了这两类经典移位寄存器的几何结构。（3）引入Etzion和Lempel提出的圈的扩展表示和扩展重量的概念,对CSR的圈结构展开讨论,由它的特殊性质提出了一个利用CSR生成de Bruijn序列的算法。利用该算法,n阶CSR可产生（?）条de Bruijn序列,运行内存约为n~2/2,产生下一比特最多需要n个循环移位操作和n个n比特按位比较操作。利用图论方法,给出了关于圈扩展重量的局限性的证明,圈扩展重量仅适用于PSR和CSR.（4）利用编写的MATLAB程序,给出了两个奇异反馈移位寄存器的具体实例,通过对二者的状态图进行严格的数学证明,提供了分析这一类具有满二叉树组合形式的状态图的奇异反馈移位寄存器的思路。

关键词： de Bruijn序列圈结构状态图奇异反馈移位寄存器非线性反馈移位寄存器

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

de Bruijn序列的计数方法

De Bruijn序列的计数方法

作者：赵悦郑州大学

学位级别：硕士

在飞速发展的信息时代,反馈移位寄存器序列得到广泛应用。随着分析方法的不断改进,LFSR序列逐渐不能满足安全需求,因此NFSR序列得到重视,而de Bruijn序列作为一类最为重要的非线性反馈移位寄存器序列更是得到深入研究。本文主要研究了de... 详细信息

在飞速发展的信息时代,反馈移位寄存器序列得到广泛应用。随着分析方法的不断改进,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序列。

关键词： de Bruijn序列有根树 de bruijn图欧拉回路

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

构造de Bruijn序列方法的研究

构造de Bruijn序列方法的研究

作者：张温馨郑州大学

学位级别：硕士

近年来,以NFSR序列作为驱动序列的序列密码体制逐渐受到密码设计者们的关注。如何构造大周期、伪随机性质良好的NFSR序列是一个热门课题。de Bruijn序列是一类非常重要的NFSR序列,具有大周期、良好的平衡性及高的线性复杂度等特性,在密... 详细信息

近年来,以NFSR序列作为驱动序列的序列密码体制逐渐受到密码设计者们的关注。如何构造大周期、伪随机性质良好的NFSR序列是一个热门课题。de Bruijn序列是一类非常重要的NFSR序列,具有大周期、良好的平衡性及高的线性复杂度等特性,在密码学及通信等领域中有广泛的应用。因此,debruijn序列的构造问题一直是研究的热点。本文给出了两种新的构造de Bruijn序列的方法。第一种是优先取补法。通过直接添加前一个比特的补,得到一种直接构造debruijn序列的方法。第二种是并圈法。对于纯轮换寄存器生成的圈,当且仅当给出的状态或其共轭状态为圈代表时进行并圈,就得到了一种基于PCR构造de Bruijn序列的方法。

关键词： NFSR序列伪随机性质 de Bruijn序列优先取补纯轮换寄存器

融合梯形相移的双目彩色结构光三维成像技术研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

融合梯形相移的双目彩色结构光三维成像技术研究

作者：胥艳湖南大学

学位级别：硕士

近年来,光学三维测量技术以其高精度、高精度和快速测量的优点逐渐成为三维测量领域的热点。而在近距离高速三维测量技术中,以双目立体视觉技术和结构光测量技术最为广泛采用,此两种技术各有优劣,将两者融合成为三维测量的一种新方式。... 详细信息

近年来,光学三维测量技术以其高精度、高精度和快速测量的优点逐渐成为三维测量领域的热点。而在近距离高速三维测量技术中,以双目立体视觉技术和结构光测量技术最为广泛采用,此两种技术各有优劣,将两者融合成为三维测量的一种新方式。本文在双目视觉的基础上,增加一台投影仪设备用于投射结构光信息,旨在解决弱纹理对象的重建困难问题,同时也能够避免投影仪的相关影响。本文研究的主要工作如下:(1)完成双目结构光成像系统的硬件平台搭建,并开发了相应的软件。(2)完成相机标定和立体校正工作,为后续三维点云获取提供基础并且方便后续处理。(3)针对传统de Bruijn序列的彩色结构光编码方案分辨率低的问题,提出融合梯形相移的编码方案,使得点云数量增加超20倍。其次对三种相移方案进行实验对比,实验结果显示梯形相移在获取更优越的解相效果的同时,解相速度相较正弦相移解相速度提高了约50%,提升了解码效率。最后针对颜色识别困难问题,提出基于投票机制的颜色优化方法识别图像的颜色标签,实验结果证明可以有效校正颜色识别错误问题。(4)为了减少外部因素对于条纹匹配的干扰,提出基于相位的阈值中心线提取方法。针对双目视觉由于表面遮挡,不连续而造成的匹配错误问题,提出基于Needleman-wunsch算法的中心线匹配算法,实验结果证明提升了匹配的鲁棒性。最后计算出像素点的三维坐标,实验结果表明本文提出的三维测量方案在具有不同反射率、不同复杂度、不连续的物体上均能有效重建物体。

关键词：双目视觉彩色结构光 de Bruijn序列梯形相移