Generating De Bruijn Sequences Of Order N By Prefer-Opposite Method

Binary de Bruijn sequence of order n has period N=2~nin which every binary n-tuple occurs exactly once.De Bruijn sequences are important nonlinear feedback shift register sequences and have important applications in many domains.Constructing new de Bruijn sequences is a key research issue,and the greedy algorithm is a main generating method.In this thesis,all existed methods of generating de Bruijn sequences based on greedy algorithm are summarized,and a Generalized Prefer-Opposite(GPO)Algorithm is pro-posed.We provide a sufficient condition for the feedback function and initial state of GPO Algorithm to generate de Bruijn sequences.It is proven that all the existed methods of generating de Bruijn sequences based on greedy algorithm are special cases of the GPO Algorithm.Also we modify this algorithm for the case that the feedback function does not meet the sufficient condition so that it also can be used to generate de Bruijn sequences.At last,we consider the case with arbitrary feedback function and propose a new method similar with the cycle joining method.By determining the successors of some special states,the algorithm can generate new de Bruijn sequences.The results in this thesis can be used to generating more new de Bruijn sequences and have important theoretical significances and application values.