Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 5/2022

15-10-2020 | Original Paper

On greedy algorithms for binary de Bruijn sequences

Authors: Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 5/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Literature
1.
go back to reference de Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758–764 (1946)MATH de Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758–764 (1946)MATH
2.
go back to reference Golomb, S.W.: Shift Register Sequences, 3rd edn. World Scientific, Singapore (2017)CrossRef Golomb, S.W.: Shift Register Sequences, 3rd edn. World Scientific, Singapore (2017)CrossRef
3.
go back to reference Fredricksen, H., Maiorana, J.: Necklaces of beads in k colors and k-ary de bruijn sequences. Discrete Math. 23(3), 207–210 (1978)MathSciNetCrossRef Fredricksen, H., Maiorana, J.: Necklaces of beads in k colors and k-ary de bruijn sequences. Discrete Math. 23(3), 207–210 (1978)MathSciNetCrossRef
4.
go back to reference Fredricksen, H.: A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24(2), 195–221 (1982)MathSciNetCrossRef Fredricksen, H.: A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24(2), 195–221 (1982)MathSciNetCrossRef
5.
go back to reference Ralston, A.: De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science. Math. Mag. 55(3), 131–143 (1982)MathSciNetMATH Ralston, A.: De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science. Math. Mag. 55(3), 131–143 (1982)MathSciNetMATH
6.
go back to reference Sawada, J., Williams, A., Wong, D.: Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles. Electr. J. Comb. 23(1), P1.24 (2016)MathSciNetCrossRef Sawada, J., Williams, A., Wong, D.: Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles. Electr. J. Comb. 23(1), P1.24 (2016)MathSciNetCrossRef
7.
go back to reference Sawada, J., Williams, A., Wong, D.: A surprisingly simple de Bruijn sequence construction. Discrete Math. 339(1), 127–131 (2016)MathSciNetCrossRef Sawada, J., Williams, A., Wong, D.: A surprisingly simple de Bruijn sequence construction. Discrete Math. 339(1), 127–131 (2016)MathSciNetCrossRef
8.
go back to reference Sawada, J., Williams, A., Wong, D.: A simple shift rule for k-ary de Bruijn sequences. Discrete Math. 340(3), 524–531 (2017)MathSciNetCrossRef Sawada, J., Williams, A., Wong, D.: A simple shift rule for k-ary de Bruijn sequences. Discrete Math. 340(3), 524–531 (2017)MathSciNetCrossRef
9.
go back to reference Dragon, P.B., Hernandez, O.I., Sawada, J., Williams, A., Wong, D.: Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence. Eur. J. Comb. 72, 1–11 (2018)MathSciNetCrossRef Dragon, P.B., Hernandez, O.I., Sawada, J., Williams, A., Wong, D.: Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence. Eur. J. Comb. 72, 1–11 (2018)MathSciNetCrossRef
11.
go back to reference Etzion, T., Lempel, A.: Algorithms for the generation of full-length shift-register sequences. IEEE Trans. Inform. Theory 30(3), 480–484 (1984)MathSciNetCrossRef Etzion, T., Lempel, A.: Algorithms for the generation of full-length shift-register sequences. IEEE Trans. Inform. Theory 30(3), 480–484 (1984)MathSciNetCrossRef
12.
13.
go back to reference Li, C., Zeng, X., Li, C., Helleseth, T., Li, M.: Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials. IEEE Trans. Inf. Theory 62(1), 610–624 (2016)MathSciNetCrossRef Li, C., Zeng, X., Li, C., Helleseth, T., Li, M.: Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials. IEEE Trans. Inf. Theory 62(1), 610–624 (2016)MathSciNetCrossRef
14.
go back to reference Chang, Z., Ezerman, M.F., Ling, S., Wang, H.: On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials. Des. Codes Cryptogr. 87(5), 1137–1160 (2019)MathSciNetCrossRef Chang, Z., Ezerman, M.F., Ling, S., Wang, H.: On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials. Des. Codes Cryptogr. 87(5), 1137–1160 (2019)MathSciNetCrossRef
15.
16.
17.
go back to reference Wang, X., Wong, D., Zhang, W.G.: A simple greedy de Bruijn sequence construction. In: Presented at Sequences and Their Applications (SETA), Hong Kong, Oct. 1–6 (2018) Wang, X., Wong, D., Zhang, W.G.: A simple greedy de Bruijn sequence construction. In: Presented at Sequences and Their Applications (SETA), Hong Kong, Oct. 1–6 (2018)
18.
go back to reference Tutte, W.: Graph Theory. Cambridge Mathematical Library. Cambridge University Press, Cambridge (2001)MATH Tutte, W.: Graph Theory. Cambridge Mathematical Library. Cambridge University Press, Cambridge (2001)MATH
20.
go back to reference Knuth, D.E.: The Art of Computer Programming. Vol. 4A, Combinatorial Algorithms. Part 1, Addison-Wesley, Upple Saddle River (2011) Knuth, D.E.: The Art of Computer Programming. Vol. 4A, Combinatorial Algorithms. Part 1, Addison-Wesley, Upple Saddle River (2011)
Metadata
Title
On greedy algorithms for binary de Bruijn sequences
Authors
Zuling Chang
Martianus Frederic Ezerman
Adamas Aqsa Fahreza
Publication date
15-10-2020
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 5/2022
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00459-3

Other articles of this Issue 5/2022

Applicable Algebra in Engineering, Communication and Computing 5/2022 Go to the issue

Premium Partner