= Binary De Bruijn sequence
= Binary circle
{synonym}
A <binary De Bruijn sequence> of order $n\geq1$ is a cyclic <binary string> in which every length-$n$ <binary string> occurs exactly once as a consecutive window. It has length $2^n$. For $n=3$, `00010111` has cyclic windows `000`, `001`, `010`, `101`, `011`, `111`, `110`, `100`; the windows at the end wrap around to the beginning. A linear recording must repeat the first $n-1$ symbols at its end. Finding an <Eulerian cycle> in the <De Bruijn graph> on length-$(n-1)$ words constructs one: each edge supplies exactly one required window.
Back to article page
