A Class of de Bruijn Sequences

作者：Li Chaoyun^*; Zeng Xiangyong; Li Chunlei; Helleseth Tor

来源：IEEE Transactions on Information Theory, 2014, 60(12): 7955-7969.

DOI：10.1109/TIT.2014.2361522

• de Bruijn sequence
• cycle structure
• NFSR
• LFSR
• cyclotomic number

In this paper, a class of linear feedback shift registers (LFSRs) with characteristic polynomial (1 + x(3)) p(x) is discussed, where p(x) is a primitive polynomial of degree n %26gt; 2. The cycle structure and adjacency graphs of the LFSRs are determined. A new class of de Bruijn sequences is constructed from these LFSRs, and the number of de Bruijn sequences in the class is also considered. To illustrate the efficiency of constructing de Bruijn sequences from these LFSRs, an algorithm for producing some corresponding maximum-length nonlinear feedback shift registers with time and memory complexity O(n) is also proposed.

• 出版日期2014-12
• 单位湖北大学