On greedy algorithms for binary de Bruijn sequences
- PDF / 634,676 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 195 Views
On greedy algorithms for binary de Bruijn sequences Zuling Chang1 · Martianus Frederic Ezerman2 · Adamas Aqsa Fahreza2 Received: 3 June 2020 / Accepted: 5 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We propose a general greedy algorithm for binary de Bruijn sequences, called Generalized Prefer-Opposite Algorithm, and its modifications. By identifying specific feedback functions and initial states, we demonstrate that most previously-known greedy algorithms that generate binary de Bruijn sequences are particular cases of our algorithm. Keywords Binary periodic sequence · de Bruijn sequence · Greedy algorithm · Feedback function · State graph Mathematics Subject Classification 11B50 · 94A55 · 94A60
1 Introduction There are 22 −n binary de Bruijn sequence of order n [1]. Each has period N = 2n in which every binary n-tuple occurs exactly once. Relatively fast generation of a few de Bruijn sequences has a long history in the literature. Any primitive polynomial of degree n generates a maximal length sequence (also known as m-sequence) that can be easily modified to a de Bruijn sequence [2]. There are at least three different algorithms to generate a Ford sequence, which is the lexicograpically smallest de Bruijn sequence. They were treated, respectively, by Fredricksen and Maiorana in [3], by Fredricksen in [4], and by Ralston in [5]. There n−1
B
Martianus Frederic Ezerman [email protected] Zuling Chang [email protected] Adamas Aqsa Fahreza [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore 637371, Singapore
123
Z. Chang et al.
are frameworks for construction via successor rules. More recent, necklace-based, successor rules and their co-necklace variants can be found in several works, e.g., [6–9]. Many, often less efficient, methods that produce much larger numbers of de Bruijn sequences are known. The majority of them work by joining smaller cycles into de Bruijn sequences. Prominent examples include methods to join cycles generated by pure cycling register or pure summing registers given by Fredricksen in [10], Etzion and Lempel in [11], and Huang in [12]. Examples of recent works on more general component cycles are the work of Li et al. [13] and Chang et al. [14]. Here we focus on greedy algorithms to generate de Bruijn sequences. There have also been many known ones, e.g., Prefer-One and Prefer-Same in [4] and Prefer-Opposite in [15]. They have since been generalized using the notion of preference functions in [16]. A paper of Wang et al. [17], which was presented at SETA 2018, discusses a greedy algorithm based on the feedback function xn−2 + xn−1 for n ≥ 3. In general one can come up with numerous feedback functions to generate de Bruijn sequences using greedy algorithms. It had unfortunately been rather challenging to confirm which ones of these functions
Data Loading...
