The Principles And Methods Of Constructing M Sequences

de Bruijn sequences, i.e. M sequences ,are the longest nonlinear shift register sequences. They can be used in many fields such as cryptography , telecommunications. So ,it is such a signification question to find how to construct this sequences.This paper studies some principles and methods of constructing M sequences, by generating spanning trees, or using cut-join method, or joining the cycles of the factorof Gn, Furthermore, the pairs of cycles of GPCR are defined. By use of the character of the pairs, a new recursive algorithm is presented for the generation of binary Msequences. It generates 25·g(n,s) M sequences of span n,where 1 ≤ s≤2 (n-4)/2 ,g(n,s)=n-2l-6-[n-2l-6/l+1]...