摘要
de Bruijn序列是一个周期为2n的0、1序列,去掉n阶de Bruijn序列中连续的n个0中的一个得到一个周期为2~n-1的序列,称为span n序列。一个n阶de Bruijn序列的线性复杂度在2^(n-1)+n和2~n-1之间,然而对应的span n序列的线性复杂度可能降为n。所以span n序列的线性复杂度成为了衡量一个de Bruijn序列好坏的重要标准,因此研究生成高线性复杂度的span n序列的方法是非常有意义的。研究文献[6]中提出的基于特殊函数和非线性反馈移位寄存器寻找span n序列的方法,发现span n序列与参数t的无关性,并基于此提出了几种改进算法。对各种算法进行横向比较,并指出了每种算法的局限和优点,以及今后可能的改进。
de Bruijn sequence is a binary sequence with length 2~n,by removing one zero from consecutive n zero of n-stage de Bruijn sequence,we get a sequence with length 2~n- 1 which is called span n sequence. The linear complexity of an n-stage de Bruijn sequence is between 2^(n-1)+ n and 2~n- 1,but the linear complexity of corresponding span n sequence could drop to n. Because of this,the linear complexity of span n sequence becomes an important property in measuring the quality of de Bruijn sequence,so it is very meaningful to study how to generate span n sequence with high linear complexity. In this article we study the method of searching span n sequence based on special function and non-linear feedback shift register proposed in literature [6],and find that the independency between span n sequence and parameter t,on this basis we propose some improved methods. We also make the horizontal comparison on various algorithms,and point out their pros and cons and the possible improvement in the future.
出处
《计算机应用与软件》
CSCD
2016年第10期311-316,320,共7页
Computer Applications and Software
