De Bruijn Sequences for the Binary Strings with Maximum Density

摘要

A de Bruijn sequence is a circular binary string of length 2~n that contains each binary string of length n exactly once as a substring. A maximum-density de Bruijn sequence is a circular binary string of length (no)+(n1)+(n2)+···+(nm) that contains each binary string of length n with density (number of Is) between 0 and m, inclusively. In this paper we efficiently generate maximum-density de Bruijn sequences for all values of n and m. An interesting special case occurs when n - 2m + 1. In this case our result is a "complement-free de Bruijn sequence" since it is a circular binary string of length 2~(n-1) that contains each binary string of length n or its complement exactly once as a substring.