Abstract
In this paper, a family of new de Bruijn sequences is proposed through the construction of maximum-length nonlinear feedback shift registers (NFSRs). Let k be a positive integer and p(0)(x), p(1)(x),..., p(k)(x) be the primitive polynomials in F-2[x] with their degrees strictly increasing and pairwise coprime. We determine the cycle structure and adjacency graphs of linear feedback shift registers (LFSRs) with characteristic polynomial q(x) = Pi(k)(i=0) p(i) (x). In the case that p(0)(x) = 1 + x, an algorithm is proposed to produce maximum-length NFSRs from these LFSRs, and it is shown that the algorithm can generate O(2((2k-1)n)) n-stage maximum-length NFSRs with memory complexity O(2kkn) and time complexity O(2(n-dk) kn), where n and d(k) are the degrees of q(x) and p(k)(x), respectively. Finally, we illustrate the proposed algorithm in the case of k = 2. In this case, we prove that for any integer n >= 8, the algorithm can produce n-stage maximum-length NFSRs with time complexity as low as O(n(loglog(n))).