| Presentation | 2022-01-20 Enumeration of Both-Ends-Fixed $k$-ary Necklaces and Its Applications Hiroshi Fujisaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider both-ends-fixed $k$-ary necklaces and enumerate all such necklaces of length $n$ from the viewpoints of symbolic dynamics and $beta$-expansions, where $n$ and $k$ are natural numbers, $kgeq2$, and $beta$ is a real number with $beta>1$. Recently, Sawada et al. proposed an efficient construction of $k$-ary de Bruijn sequence of length $k^n$, which for each $ngeq1$, requires $O(n)$ space but generates a single $k$-ary de Bruijn sequence of length $k^n$ 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 $k^n$ constructed by Sawada et al. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | $k$-ary necklaces / symbolic dynamics / $beta$-expansions / $k$-ary de Bruijn sequences / auto-correlation function |
| Paper # | IT2021-48,SIP2021-56,RCS2021-216 |
| Date of Issue | 2022-01-13 (IT, SIP, RCS) |
| Conference Information | |
| Committee | RCS / SIP / IT |
|---|---|
| Conference Date | 2022/1/20(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Eiji Okamoto(Nagoya Inst. of Tech.) / Yukihiro Bandou(NTT) / Tadashi Wadayama(Nagoya Inst. of Tech.) |
| Vice Chair | Toshihiko Nishimura(Hokkaido Univ.) / Tomoya Tandai(Toshiba) / Fumihide Kojima(NICT) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Takayuki Nakachi(Ryukyu Univ.) / Tetsuya Kojima(Tokyo Kosen) |
| Secretary | Toshihiko Nishimura(NEC) / Tomoya Tandai(Panasonic) / Fumihide Kojima(Xiaomi) / Toshihisa Tanaka(Takushoku Univ.) / Takayuki Nakachi(Tokyo Univ. Agri.&Tech.) / Tetsuya Kojima(Saitamai Univ.) |
| Assistant | Koichi Adachi(Univ. of Electro-Comm.) / Osamu Nakamura(Sharp) / Manabu Sakai(Mitsubishi Electric) / Masashi Iwabuchi(NTT) / Tatsuki Okuyama(NTT DOCOMO) / Taichi Yoshida(UEC) / Seisuke Kyochi(Univ. of Kitakyushu) / Masanori Hirotomo(Saga Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Radio Communication Systems / Technical Committee on Signal Processing / Technical Committee on Information Theory |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enumeration of Both-Ends-Fixed $k$-ary Necklaces and Its Applications |
| Sub Title (in English) | |
| Keyword(1) | $k$-ary necklaces |
| Keyword(2) | symbolic dynamics |
| Keyword(3) | $beta$-expansions |
| Keyword(4) | $k$-ary de Bruijn sequences |
| Keyword(5) | auto-correlation function |
| 1st Author's Name | Hiroshi Fujisaki |
| 1st Author's Affiliation | Kanazawa University(Kanazawa Univ.) |
| Date | 2022-01-20 |
| Paper # | IT2021-48,SIP2021-56,RCS2021-216 |
| Volume (vol) | vol.121 |
| Number (no) | IT-327,SIP-328,RCS-329 |
| Page | pp.pp.107-112(IT), pp.107-112(SIP), pp.107-112(RCS), |
| #Pages | 6 |
| Date of Issue | 2022-01-13 (IT, SIP, RCS) |