Paper 2015/667

De Bruijn Sequences from Nonlinear Feedback Shift Registers

Ming Li and Dongdai Lin

Abstract

We continue the research of Jansen et al. (IEEE Trans on Information Theory 1991) to construct de Bruijn sequences from feedback shift registers (FSRs) that contains only very short cycles. Firstly, we suggest another way to define the representative of a cycle. Compared with the definition made by Jansen et al., this definition can greatly improve the performance of the cycle joining algorithm. Then we construct a large class of nonlinear FSRs that contains only very short cycles. The length of the cycles in these n-stage FSRs are less than 2n. Based on these FSRs, O(2^{n/2-logn) de Bruijn sequences of order n are constructed. To generate the next bit in the de Bruijn sequence from the current state, it requires only 2n bits of storage and less than 2n FSR shifts.