Longest subsequences shared by two de Bruijn sequences
- PDF / 310,678 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 54 Downloads / 207 Views
Longest subsequences shared by two de Bruijn sequences Yupeng Jiang1
· Dongdai Lin1
Received: 6 September 2019 / Revised: 30 March 2020 / Accepted: 2 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract An order n binary de Bruijn sequence is a periodic sequence of bits with period 2n in which each n-tuple of bits occurs exactly once. We consider the longest subsequences shared by two de Bruijn sequences. First, we fix one de Bruijn sequence and prove that de Bruijn sequences sharing a longest subsequence with it must be those obtained by a single crossjoin operation from it. Then determining such sequences is equivalent to finding cross-join pairs with maximum diameter. Second, we prove that for n ≥ 5, there exist two de Bruijn sequences of order n sharing a subsequence of length 2n − 2, i.e., there exists sequence a0 a1 · · · a2n −3 with length 2n − 2 such that both a0 a1 · · · a2n −3 01 and a0 a1 · · · a2n −3 10 are periods of de Bruijn sequences. Keywords de Bruijn sequence · Cross-join pair · Cross-join operation · Prefer-one sequence Mathematics Subject Classification 94A55 · 94A60 · 05A15
1 Introduction Let n be a positive integer. An order n binary de Bruijn sequence is a sequence a = (a0 , a1 , a2 , . . . , ) with period 2n such that for i = 0, 1, . . . , 2n − 1, (ai , ai+1 , . . . , ai+n−1 ) runs over all n-tuples. De Bruijn sequences have long period, uniform pattern distribution and they have applications in coding, communications systems, pseudo-random number generators and cryptography. De Bruijn sequences have drawn much attention and many aspects
Communicated by L. Teirlinck. D. Lin: The work was supported by the National Natural Science Foundation of China under Grants 61872358, 61872359.
B
Yupeng Jiang [email protected] Dongdai Lin [email protected]
1
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, People’s Republic of China
123
Y. Jiang, D. Lin
have been studied, including cryptographic properties, constructions, the properties of their feedback functions, etc. See [14] and [30] for an exposition. In 1946, de Bruijn proves that the number of shift-distinct order n binary de Bruijn n−1 sequences is 22 −n [5]. Chan, Games and Key prove that linear complexities of order n de Bruijn sequences are between 2n−1 + n and 2n − 1 and the upper bound is achievable [2]. Later, Etzion and Lempel prove that the lower bound is also achievable [9]. Results and open problems about linear complexities of de Bruijn sequences are listed in [8]. For the correlation properties of de Bruijn sequences, it is easy to show that the auto-correlation values of de Bruijn sequences at ±1, ±2, . . . , ±(n − 1) are zero. Zhang and others study further properties of correlation functions of de Bruijn sequences[34,35]. The construction of de Bruijn sequences is very important. There are graphical, combinatorial and algebraic methods of generating de Bruijn sequences. For an early survey, see [13]. Re
Data Loading...
