The search functionality is under construction.
The search functionality is under construction.

Enumeration of Both-Ends-Fixed k-Ary Necklaces and Its Applications

Hiroshi FUJISAKI

  • Full Text Views

    0

  • Cite this

Summary :

We consider both-ends-fixed k-ary necklaces and enumerate all such necklaces of length n from the viewpoints of symbolic dynamics and β-expansions, where n and k(≥ 2) are natural numbers and β(> 1) is a real number. Recently, Sawada et al. proposed an efficient construction of k-ary de Bruijn sequence of length kn, which for each n ≥ 1, requires O(n) space but generates a single k-ary de Bruijn sequence of length kn in O(1)-amortized time per bit. Based on the enumeration of both-ends-fixed k-ary necklaces of length n, we evaluate auto-correlation values of the k-ary de Bruijn sequences of length kn constructed by Sawada et al. We also estimate the asymptotic behaviour of the obtained auto-correlation values as n tends to infinity.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.431-439
Publication Date
2023/03/01
Publicized
2022/08/23
Online ISSN
1745-1337
DOI
10.1587/transfun.2022TAP0007
Type of Manuscript
Special Section PAPER (Special Section on Information Theory and Its Applications)
Category
Fundamentals of Information Theory

Authors

Hiroshi FUJISAKI
  Kanazawa University

Keyword