De Bruijn sequence

A cyclic sequence over an alphabet of size $q$ in which every word of length $n$ appears exactly once as a cyclic window. Its length is $q^n$. The De Bruijn graph converts its construction into an Eulerian cycle problem.

A binary De Bruijn sequence of order $n\ge 1$ 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.