Constructing modified binary de Bruijn sequences via cycle joining based on the prefer-complement algorithm - Musthofa Musthofa; Agus Maman Abadi; Karyati Karyati; Lusi Harini (Faculty of Mathematics and Natural Science (FMIPA), Universitas Syiah Kuala, 2026)
This paper presents a generalized implementation of the cycle joining algorithm for generating binary sequences corresponding to modified de Bruijn sequences of order . The proposed approach can be interpreted in terms of a modified de Bruijn graph, where vertices represent binary strings of length and edges correspond to allowable transitions under the modification rules. The algorithm can be applied to any integer and can start from any chosen initial vertex. The procedure begins by constructing an initial sequence using the prefer-complement algorithm. The method can produce multiple disjoint cycles, which are iteratively extended and joined into a single sequence. A key challenge in cycle joining is identifying suitable conjugate pairs for merging cycles. In this approach, conjugate pairs are efficiently determined through the algorithm’s structured scheme, simplifying the joining process. The resulting sequence achieves the maximal length , which corresponds to a modified de Bruijn sequence. The flexibility of the algorithm allows it to accommodate varying initial vertices, making it highly adaptable for sequence generation. Its ability to systematically join multiple cycles into a single sequence corresponding to a modified de Bruijn sequence demonstrates potential applications in cryptographic keystream generation, pseudorandom binary sequence design, and other areas requiring structured yet complex binary sequences.