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.
Hiroshi FUJISAKI
Kanazawa University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hiroshi FUJISAKI, "Enumeration of Both-Ends-Fixed k-Ary Necklaces and Its Applications" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 431-439, March 2023, doi: 10.1587/transfun.2022TAP0007.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022TAP0007/_p
Copy
@ARTICLE{e106-a_3_431,
author={Hiroshi FUJISAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enumeration of Both-Ends-Fixed k-Ary Necklaces and Its Applications},
year={2023},
volume={E106-A},
number={3},
pages={431-439},
abstract={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.},
keywords={},
doi={10.1587/transfun.2022TAP0007},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - Enumeration of Both-Ends-Fixed k-Ary Necklaces and Its Applications
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 431
EP - 439
AU - Hiroshi FUJISAKI
PY - 2023
DO - 10.1587/transfun.2022TAP0007
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2023
AB - 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.
ER -