How Binary de Bruijn Sequences Work

A binary de Bruijn sequence of order \(n\) is a cyclic bit sequence of length \(2^n\) that contains every possible \(n\)-bit binary pattern exactly once as a contiguous sub-sequence. This article explains how these compact combinatorial sequences are constructed, detailing the graph theory principles, shift-register operations, and algorithmic generation methods that make them possible.

The Mathematical Foundation

In a standard binary system, there are \(2^n\) distinct combinations for an \(n\)-bit word. Listing all these combinations separately requires \(n \times 2^n\) bits. A de Bruijn sequence eliminates redundancy by overlapping adjacent patterns by \(n-1\) bits.

Because the sequence is cyclic, the end of the sequence wraps around to the beginning. Moving a sliding window of length \(n\) along the cycle one bit at a time reveals each of the \(2^n\) unique binary configurations exactly once before returning to the initial state.

Graph Theory Construction: De Bruijn Graphs

The most common way to generate and conceptualize a binary de Bruijn sequence is through graph theory using a directed graph known as a de Bruijn graph.

1. Defining Vertices and Edges

• Vertices: Each vertex represents a unique binary string of length \(n - 1\). There are \(2^{n-1}\) total vertices.
• Edges: A directed edge exists from vertex \(u\) to vertex \(v\) if the suffix of length \(n-2\) of \(u\) matches the prefix of length \(n-2\) of \(v\). Each edge represents a transition formed by shifting in a new bit (either 0 or 1), corresponding to an \(n\)-bit sequence.

2. Finding an Eulerian Path

In a binary de Bruijn graph: * Every vertex has an in-degree of 2 (two incoming edges). * Every vertex has an out-degree of 2 (two outgoing edges).

Because the in-degree equals the out-degree for every vertex and the graph is strongly connected, the graph is Eulerian. An Eulerian circuit visits every single edge exactly once. Recording the binary value associated with each edge traversal along this circuit yields a complete de Bruijn sequence of length \(2^n\).

Generation Methods

Several practical algorithms can generate binary de Bruijn sequences without needing to store the entire graph in memory.

Linear-Feedback Shift Registers (LFSRs)

A maximal-length linear-feedback shift register (m-sequence) of order \(n\) naturally generates a pseudo-random cyclic sequence of length \(2^n - 1\). This sequence contains all non-zero \(n\)-bit patterns. A full de Bruijn sequence of length \(2^n\) is created by identifying the sequence of \(n-1\) consecutive zeros and inserting an additional 0 into that run.

The Prefer-Opposite (Greedy) Algorithm

A sequence can be constructed sequentially using a greedy approach: 1. Start with an initial state of \(n\) zeros (00...0). 2. At each step, attempt to append a bit that is the complement (opposite) of the bit shifted out \(n\) steps prior. 3. If appending that bit forms an \(n\)-bit pattern that has already appeared, append the alternative bit instead. 4. Repeat until all \(2^n\) unique \(n\)-bit sequences have been generated.

Concatenation of Lyndon Words

The Fredricksen-Maiorana algorithm generates de Bruijn sequences in lexicographic order. A Lyndon word is a non-empty string that is strictly smaller in lexicographic order than all of its non-trivial cyclic rotations. By generating all Lyndon words whose lengths divide \(n\) and concatenating them in lexicographical order, the resulting string forms a valid de Bruijn sequence.

Example: Order \(n = 3\)

For \(n = 3\), there are \(2^3 = 8\) unique combinations: 000, 001, 010, 011, 100, 101, 110, and 111.

A valid cyclic de Bruijn sequence for \(n = 3\) is:

0 0 0 1 1 1 0 1

Evaluating the 3-bit sliding window around the cycle: * 000 (indices 0, 1, 2) * 001 (indices 1, 2, 3) * 011 (indices 2, 3, 4) * 111 (indices 3, 4, 5) * 110 (indices 4, 5, 6) * 101 (indices 5, 6, 7) * 010 (indices 6, 7, 0 - wrap-around) * 100 (indices 7, 0, 1 - wrap-around)

Every 3-bit pattern appears exactly once in only 8 total bits.