*18:17*[Pub][ePrint] De Bruijn Sequences from Nonlinear Feedback Shift Registers, by Ming Li and Dongdai Lin

We continue the research in \\cite{jans1991} 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 in \\cite{jans1991}, 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^{\\frac{n}{2}-\\mathrm{log} n})$ 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.