Construction of de Bruijn Sequences From LFSRs With Reducible Characteristic Polynomials

摘要

In this paper, a family of new de Bruijn sequences is proposed through the construction of maximum-length nonlinear feedback shift registers (NFSRs). Let be a positive integer and be the primitive polynomials in 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 . In the case that , an algorithm is proposed to produce maximum-length NFSRs from these LFSRs, and it is shown that the algorithm can generate -stage maximum-length NFSRs with memory complexity and time complexity , where and are the degrees of and , respectively. Finally, we illustrate the proposed algorithm in the case of . In this case, we prove that for any integer