Enumeration Of De Bruijn Sequences

In the rapidly developmental information age,feedback shift register sequences have been widely used.With the continuous improvement of cryptanalysis,the linear feedback shift register(LFSR)sequences are gradually unable to meet security requirements,so nonlinear feedback shift register(NFSR)sequences are important more and more,and de Bruijn sequence,as one of most important NFSR sequences,has been deeply studied.In this thesis,we mainly study the counting problem of de Bruijn sequences.Firstly,we summarize in detail the existed counting methods of de Bruijn sequences,including de Bruijn graph method,permutation method and BEST theorem method.Based on these counting methods,one new method named the rooted tree method is proposed.This method mainly uses the relationship between the number of rooted trees and de Bruijn sequences.According to de Bruijn sequences of order n,the branchless trees with root 0~n in the n-th order de Bruijn graph are obtained,and then all the trees with root 0~nare deduced by changing the successor of any state in each branchless tree.Finally,the number of de Bruijn sequences of order n+1 are determined by counting the number of rooted trees with root 0~n.This new counting method provided in this paper is constructive.According to this method,we can construct all rooted trees and construct all de Bruijn sequences inductively.