Details

Autor(en) / Beteiligte

• Chaoyun Li
• Xiangyong Zeng
• Chunlei Li
• Helleseth, Tor
• Ming Li

Titel

Construction of de Bruijn Sequences From LFSRs With Reducible Characteristic Polynomials

Ist Teil von

• IEEE transactions on information theory, 2016-01, Vol.62 (1), p.610-624

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2016

Link zum Volltext

• IEEE_Xplore

Quelle

IEEE/IET Electronic Library (IEL)

Beschreibungen/Notizen

• 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 p0(x), p1(x), . . . , pk(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) = π 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 (2 k -1) n ) n-stage maximum-length NFSRs with memory complexity O(2 k kn) and time complexity O(2 n-dk kn), where n and dk are the degrees of q(x) and pk(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) ).