[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Experimental results show that, when the order n is odd, there are de Bruijn sequences such that the corresponding complement sequence and the reverse sequence are the same. In this paper, we propose one efficient method to generate such de Bruijn sequences. This solves an open problem asked by Fredricksen forty years ago for showing the existence of such de Bruijn sequences when the odd order \(n >1\). Moreover, we refine a characterization of de Bruijn sequences with the same complement and reverse sequences and study the number of these de Bruijn sequences, as well as the distribution of de Bruijn sequences of the maximum linear complexity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Similar content being viewed by others

Data Availability

No datasets were generated or analysed during the current study.

References

  1. Booth K.S.: Lexicographically least circular substrings. Inf. Process. Lett. 10(4–5), 240–242 (1980).

    Article  MathSciNet  MATH  Google Scholar 

  2. Chan A.H., Games R.A., Key E.L.: On the complexities of de Bruijn sequences. J. Comb. Theory A 33(3), 233–246 (1982).

    Article  MathSciNet  MATH  Google Scholar 

  3. de Bruijn N.G.: A combinatorial problem. Proc. Kon. Ned. Akad. Wetensh. 49(7), 758–764 (1946).

    MATH  Google Scholar 

  4. Etzion T.: On the distribution of de Bruijn sequences of low complexity. J. Comb. Theory A 38, 241–253 (1985).

    Article  MathSciNet  MATH  Google Scholar 

  5. Etzion T., Lempel A.: On the distribution of de Bruijn sequences of given complexity. IEEE Trans. Inf. Theory 30(4), 611–614 (1984).

    Article  MathSciNet  MATH  Google Scholar 

  6. Fredricksen H.: A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24(2), 195–221 (1982).

    Article  MathSciNet  MATH  Google Scholar 

  7. Gabric D., Sawada J., Williams A., Wong D.: A framework for constructing de Bruijn sequences via simple successor rules. Discret. Math. 341(11), 2977–2987 (2018).

    Article  MathSciNet  MATH  Google Scholar 

  8. Golomb S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1981).

    MATH  Google Scholar 

  9. Golomb S.W., Gong G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, New York (2004).

    MATH  Google Scholar 

  10. Hauge E.R., Helleseth T.: de Bruijn sequences, irreducible codes, and cyclotomy. Discret. Math. 159, 143–154 (1996).

    Article  MathSciNet  MATH  Google Scholar 

  11. Jansen C., Franx W., Boekee D.: An efficient algorithm for the generation of de Bruijn cycles. IEEE Trans. Inf. Theory 37(5), 1475–1478 (1991).

    Article  MathSciNet  MATH  Google Scholar 

  12. Mayhew G.L.: Weight class distributions of de Bruijn sequences. Discret. Math. 126, 425–429 (1994).

    Article  MathSciNet  MATH  Google Scholar 

  13. Sawada J., Williams A., Wong D.: A surprisingly simple de Bruijn sequence construction. Discret. Math. 339(1), 127–131 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  14. Sloane N.J.A.: On single-deletion-correcting codes. In: Arasu K.T., Seress A. (eds.), An Earlier Version appeared in Codes and Designs, Ohio State University, May 2000 (Ray–Chaudhuri Festschrift), pp. 273–291. Walter de Gruyter, Berlin (2002). http://neilsloane.com/doc/dijen.pdf.

  15. Zhu Y., Chang Z., Ezerman M.F., Wang Q.: An efficiently generated family of binary de Bruijn sequences. Discret. Math. 344(6), 112368 (2021).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We thank the anonymous reviewers for their helpful suggestions. The research of authors is supported by National Natural Science Foundation of China (62272420) and Natural Sciences and Engineering Research Council of Canada (RGPIN-2023-04673).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, 450001, China

    Zuling Chang

  2. School of Mathematics and Statistics, Carleton University, 1125 Colonel by Drive, Ottawa, ON, K1S 5B6, Canada

    Qiang Wang

Authors
  1. Zuling Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qiang Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Both authors contributed equally to this work.

Corresponding author

Correspondence to Qiang Wang.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chang, Z., Wang, Q. Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences. Des. Codes Cryptogr. (2025). https://doi.org/10.1007/s10623-025-01580-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10623-025-01580-5

Keywords

Mathematics Subject Classification