The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nous considérons que les deux extrémités sont fixes k-ary colliers et énumérer tous ces colliers de longueur n du point de vue de la dynamique symbolique et des β-expansions, où n et k(≥ 2) sont des nombres naturels et β(> 1) est un nombre réel. Récemment, Sawada et al. proposé une construction efficace de k-ary de Bruijn séquence de longueur kn, qui pour chacun n ≥ 1, nécessite O(n) espace mais génère un seul k-ary de Bruijn séquence de longueur kn in O(1)-temps amorti par bit. Basé sur l'énumération des deux extrémités fixes k-ary colliers de longueur n, nous évaluons les valeurs d'autocorrélation du k-ary de Bruijn séquences de longueur kn construit par Sawada et al. Nous estimons également le comportement asymptotique des valeurs d'autocorrélation obtenues comme n tend vers l'infini.
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.
Copier
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
Copier
@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},}
Copier
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 -