On a Small Class of Binary Modified de Bruijn Sequences of Maximal Linear Span
Musthofa, Indah Emilia Wijayanti, Diah Junia Eksi Palupi, Martianus Frederic Ezerman · 2023
The linear complexity of a periodic binary sequence is the degree of its minimal polynomial. It has been conjectured that, for any positive integer n ≥ 4, there exist binary modified de Bruijn sequences of order n whose linear complexity is $2^{n}-2$, which is the highest possible. A proof remains elusive, much less a constructive general approach to such modified binary sequences, given any arbitrary order n. This work focuses on a small class of modified binary de Bruijn sequences whose linear spans are maximal or near maximal. We devise a method to determine the liner span of the sequences in this class and show heuristically that the sequences have high linear spans, often reaching the maximal values for their respective order n.