An efficient implementation algorithm for generating de Bruijn sequences ?
A nonsingular feedback shift register will generate pairwise disconnecting cycles. To get a de Bruijn cycle, we put a different mark on the states that are on the different cycle. This could help us find adjacent cycles easily and join them together. We modify the marks of the states that on the joined cycles to the same mark. At the same time, the feedback function is modified accordingly. Then a full cycle is obtained when the marks of all the states on different cycles are modified to the same mark. At the same time, the feedback function that could generate the de Bruijn sequences is also obtained.
algorithms de bruijn sequence shift register