Min/Random/Max Discrepancy  Output  

As articulated in [Gol17], binary DB sequences
 are balanced as they contain the same number of $0$s and $1$s;
 satisfy a run property as there are an equal number of contiguous runs of 0s and 1s of the same length in the sequence;
 satisfy a span$n$ property as they contain every distinct length $n$ binary string as a substring.
Discrepancy
The DB sequences with the smallest discrepancy are based on the complementing cycling register (CCR). The two CCR concatenation constructions in [GS18], which correspond to the shiftrules CCR2 and CCR3, have discrepancy less than $2n$. This is because the maximum discrepancy in any single CCR cycle is $n$ [GS17]. Experimentally, the shift rule by Huang [H90] demonstrates slightly smaller discrepancy.
The greedy Prefersame and Preferopposite, along with the lexicographic composition concatenation approach can all be generated via shiftrules based on the PRR. They all appear to have discrepancies of $O(n^2)$. The table below summarizes their discrepancies along with the four shift rules based on the CCR.
The DB sequences with the maximal discrepancy can be obtained by considering weight (density) ranges. By taking a universal cycle $U_1$ for all binary strings with weight from 0 to $\lceil n/2 \rceil 1$ and joining it with a universal cycle $U_2$ for all binary strings with weights from $\lceil n/2 \rceil$ to $n$, the discrepancy will be close to the discrepancy of $U_1$, which is ${n1 \choose \lfloor n/2 \rfloor}$. It is conjectured that the maximal discrepancy for any DB sequence is ${n1 \choose \lfloor n/2 \rfloor} + \lfloor n/2 \rfloor$, which by Stirling's approximation is $\Theta(\frac{2^n}{\sqrt{n}})$. This is exactly the discrepancy obtained by this construction, which is available for generation and download above [GS20]. The table below shows the discrepancy of this sequence, along with the coollex concatenation construction which is also based on weight ranges (and the PSR/CSR). The table also illustrates the discrepancies for the shift rules PCR1 (Granddaddy), PCR2 (Grandmama), PCR3, and PCR4. The sequences generated by the PCR1 construction are known to have discrepancy $\Theta(\frac{2^n\log n}{n})$ [CH10].
The "Random" column is obtained by taking the average discrepancy of 10000 random sequences of length $2^n$. Such a random sequence is expected to have discrepancy $\Theta(2^{n/2} \sqrt{\log n})$. It remains an interesting problem to define/construct a DB sequence that is provably close to these random values. Experimentally, the shiftrule PCR4 constructs a DB sequence that is closest to the expected discrepancy of a random sequence.
The table below considers the discrepancy over all LFSRs based on primitive polynomials. The minimum, average, and maximum discrepancies are illustrated against our random target. While these sequences demonstrate discrepancy closest to what one expects from a random sequence, the fact that the underlying LFSR can be so easily decoded (as noted above) limits their application.
For $12< n \leq 25$, there exists a DB sequence generated by an LFSR (try it above!) that has discrepancy differing by at most one from the random target. Feedback functions for such LFSRs are given below.
 [CH10] J. Cooper and C. Heitsch. The discrepancy of the lexleast de Bruijn sequence. Discrete Math., 310(67):11521159, 2010.
 [Gol17] S. W. Golomb. Shift Register Sequences (Third Edition). World Scientific, Singapore, 2017.
 [GS17] D. Gabric and J. Sawada. A de Bruijn sequence construction by concatenating cycles of the complemented cycling register. In Combinatorics on words, volume 10432 of Lecture Notes in Comput. Sci., pages 4958. Springer, Cham, 2017.
 [GS18] D. Gabric and J. Sawada. Constructing de Bruijn sequences by concatenating smaller universal cycles. Theoret. Comput. Sci., 743:1222, 2018.
 [GS20] D. Gabric and J. Sawada. Investigating the discrepancy property of de Bruijn sequences. Manuscript, 2020.
 [Mas69] J. Massey. Shiftregister synthesis and BCH decoding. IEEE Transactions on Information Theory, 15(1):122–127,1969.