一种快速生成k元de Bruijn序列的算法.pdf

《一种快速生成k元de Bruijn序列的算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第16卷第1期安徽机电学院学报VOl.16,NO.12·00218年·3月JOurnalO安fAnh徽uiIns机titute电OfMe学chani院cal学Elec报tricalEngineeringMa2r.00,12年001文章编号：1007-5240(2001)01-0028-04一种快速生成!元deBruijn序列的算法王传玉(安徽机电学院应用数理系，安徽芜湖241000)摘要：DeBruijn序列是一类最重要的非线性移位寄存器序列.通过并置所有循环圈的周期约化，进而提出一种新的生成I元deBruijn序列的算法.该算法每步运算可生成一列元素而不是一个元素，因此减少了运算次数，加快

2、了生成速度，且在I＞3和I＞4时，这种算法能生成一大批deBruijn序列.关键词：移位寄存器；DeBruijn序列；循环圈中图分类号：0157.4文献标识码：A引言设有整数环ZI={0,1,⋯,I-1}.DeBruijn序列是一类最长的非线性移位寄存器序列，它在密码学、电讯学等领域中有广泛的应用，因而如何有效地构造deBruijn序列是一个有意义的问题.通常的构造方法是先由某一移位寄存器生成很多短圈，再将所有的短圈合并成全长圈，进而得到一个deBruijn序列.本文基于文献[1]的作者提出的思想，提出了一种新的生成I元deBruijn序列的算法，该算法不仅容易实现，且每步运算可生成一列元素

3、而不象文献[1，2]中的算法每次只能生成一个元素.本文提出的算法能生成一大批的deBruijn序列.而文献[1]给出的算法仅能生成一个I元deBruijn序列.1基本原理算法对任意自然数I，I＞2,ZI{A=a},若A。ZII=1,a2⋯aIIai。ZI,i=1,2,⋯,II，称A为一个I级状态，若bi

4、如果arj

5、D=a(aD为不可约循环圈，i=1,2,I一I-1，则T1a2⋯aI-1I+i⋯,I-1.用(iDI记长为I的循环圈i⋯i其中i。Z，则0I，(I-1DI均为循环圈，若A为循环圈，1,I则0II，且必存在t。N，使A=Tt(0ID，故可由算子T列出介于0I与(I-1DI之

6、圈，则它的后继循环圈是Th(AD，其中h是使得Th(AD为循环圈的最小自然数；序列中最后一个循环圈为(I-1DI.(2D按(1D中循环圈为顺序，并置所有循环圈的周期约化，形成一个I元deBruijn序列.例1在I=I=4时，由算法1(1D可得循环圈的升列如下：0000000100020003001100120013002200230032003301010102010301110112011301210122012301310132013302020203021102120213022102220223023102320233030303110312031303210322032303320

7、333111111121113112211231131113211331212121312221223123212331313132213231331133213332222222322332323233332333333显然，根据算法1仅能生成一个长为44的4元deBruijn序列.由算法1(2D得一个长为44的4元deBruijn序列如下0I0001I0002I0003I0011I0012I0013I00