CLR cover

Problem 118: Recursive Generation of de Bruijn Words

Following Problem 117, the present problem provides another method to generate a de Bruijn word on the alphabet $\Bi = \{\sa{0},\sa{1}\}$. The method is recursive and its description requires a few preliminary definitions.

Let us first define $\Shift$. When a word $u$ occurs circularly exactly once in a word $x$, $|u|\lt |x|$, $\Shift(x,u)$ denotes the conjugate of $x$ admitting $u$ as a suffix.

Let us then define the operation $\oplus$ between two words $x,y\in \Bi^N$, $N={2^n}$, for which the suffix $u$ of length $n$ of $x$ has a unique circular factor occurrence in $y$: $x \oplus y$ denotes $x\cdot \Shift(y,u)$.

Eventually, for a binary word $w$, let $\Psi(w)$ be the binary word $v$ of length $|w|$ defined, for $0 \leq i \leq |w|-1$, by $$v[i] = (w[0]+w[1]+ \cdots +w[i]) \bmod 2.$$ Also denote by $\overline{x}$ the complement of $x$, that is, its bitwise negation.

Show that if $x$ is a binary de Bruijn word of length $2^n$ then $\Psi(x) \oplus \overline{\Psi(x)}$ is a de Bruijn word of length $2^{n+1}$.
Count circular factors of $\Psi(x) \oplus \overline{\Psi(x)}$.

References

  • S. W. Golomb. Shift Register Sequences. World Scientific, Singapore, 2017. Third revised edition.
  • A. Lempel. On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Trans. Computers, 19(12):1204-1209, 1970.
  • D. Repke and W. Rytter. On semi-perfect de Bruijn words. Theor. Comput. Sci., 720:55-63, 2018.