An Efficiently Generated Family of Binary de Bruijn Sequences
share
We study how to generate binary de Bruijn sequences efficiently from the class of simple linear feedback shift registers with characteristic polynomial f(x)=x^n+x^n-1+x+1 ∈F_2[x], for n ≥ 3, using the cycle joining method. Based on the properties of this class of LFSRs, we propose two classes of successor rules, each of which generates O(2^n-3) de Bruijn sequences. The cost to produce the next bit is O(n) time and O(n) space for a fixed n.
READ FULL TEXT