Abstract
We present a mapping of the binary prefer-opposite de Bruijn sequence of order n onto the binary prefer-one de Bruijn sequence of order \(n-1\). The mapping is based on the differentiation operator \(D(\langle {b_1,\ldots ,b_l}\rangle ) = \langle b_2-b_1, b_3-b_2,\ldots , b_{l}-b_{l-1} \rangle \) where bit subtraction is modulo two. We show that if we take the prefer-opposite sequence \(\langle {b_1,b_2,\ldots ,b_{2^n}}\rangle \), apply D to get the sequence \(\langle {\hat{b}_1, \ldots , \hat{b}_{2^n-1}}\rangle \) and drop all the bits \(\hat{b}_i\) such that \(\langle {\hat{b}_i,\ldots ,\hat{b}_{i+n-1}}\rangle \) is a substring of \(\langle {\hat{b}_1,\ldots ,\hat{b}_{i+n-2}}\rangle \), we get the prefer-one de Bruijn sequence of order \(n-1\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alhakim A.M.: A simple combinatorial algorithm for de Bruijn sequences. Am. Math. Mon. 117(8), 728–732 (2010).
de Bruijn N.G.: A combinatorial problem. Proc. Koninklijke Ned. Akad. Wet. Ser. A 49(7), 758 (1946).
Lempel A.: On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Trans. Comput. 100(12), 1204–1209 (1970).
Martin M.H.: A problem in arrangements. Bull. Am. Math. Soc. 40(12), 859–864 (1934).
Acknowledgements
This research was supported by the ISRAEL SCIENCE FOUNDATION (Grants No. 857/12 and 856/16).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by M. Paterson.
Rights and permissions
About this article
Cite this article
Rubin, A., Weiss, G. Mapping prefer-opposite to prefer-one de Bruijn sequences. Des. Codes Cryptogr. 85, 547–555 (2017). https://doi.org/10.1007/s10623-016-0322-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-016-0322-4