| 講演名 | 2022-01-20 Enumeration of Both-Ends-Fixed $k$-ary Necklaces and Its Applications 藤崎 礼志(金沢大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 両端固定$k$進ネックレスを考え，記号力学系および$beta$進展開に基づき，長さ$n$の両端固定$k$進ネックレスの総数を数え上げる．ここで$n$と$k$は自然数であり，$kgeq2$，$beta$は$beta>1$の実数である．最近，Sawadaらは，任意の自然数$n$に対して，$O(n)$のメモリを用いて，1ビット当たりならし計算量$O(1)$で，長さ$k^n$の，単一の$k$進 de Bruijn 系列を生成するという驚く程高効率なアルゴリズムを発見した．長さ $n$ の 両端固定$k$進ネックレスの総数に基づき，Sawadaらのアルゴリズムにより生成される長さ$k^n$の$k$進 de Bruijn 系列の自己相関関数値を評価する． |
| 抄録(英) | 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. |
| キーワード(和) | $k$進ネックレス / 記号力学系 / $beta$進展開 / $k$進 de Bruijn 系列 / 自己相関関数 |
| キーワード(英) | $k$-ary necklaces / symbolic dynamics / $beta$-expansions / $k$-ary de Bruijn sequences / auto-correlation function |
| 資料番号 | IT2021-48,SIP2021-56,RCS2021-216 |
| 発行日 | 2022-01-13 (IT, SIP, RCS) |
| 研究会情報 | |
| 研究会 | RCS / SIP / IT |
|---|---|
| 開催期間 | 2022/1/20(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 無線通信のための信号処理，学習，数理，情報理論および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 岡本 英二(名工大) / 坂東 幸浩(NTT) / 和田山 正(名工大) |
| 委員長氏名（英） | Eiji Okamoto(Nagoya Inst. of Tech.) / Yukihiro Bandou(NTT) / Tadashi Wadayama(Nagoya Inst. of Tech.) |
| 副委員長氏名（和） | 西村 寿彦(北大) / 旦代 智哉(東芝) / 児島 史秀(NICT) / 田中 聡久(東京農工大) / 仲地 孝之(琉球大学) / 小嶋 徹也(東京高専) |
| 副委員長氏名（英） | Toshihiko Nishimura(Hokkaido Univ.) / Tomoya Tandai(Toshiba) / Fumihide Kojima(NICT) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Takayuki Nakachi(Ryukyu Univ.) / Tetsuya Kojima(Tokyo Kosen) |
| 幹事氏名（和） | 村岡 一志(NEC) / 山本 哲矢(パナソニック) / 杉本 憲治郎(Xiaomi) / 渡辺 修(拓殖大) / 田中 雄一(東京農工大) / 松田 哲直(埼玉大) / 野崎 隆之(山口大) |
| 幹事氏名（英） | Kazushi Muraoka(NEC) / Tetsuya Yamamoto(Panasonic) / Kenjiro Sugimoto(Xiaomi) / Osamu Watanabe(Takushoku Univ.) / Yuichi Tanaka(Tokyo Univ. Agri.&Tech.) / Tetsunao Matsuta(Saitamai Univ.) / Takayuki Nozaki(Yamaguchi Univ.) |
| 幹事補佐氏名（和） | 安達 宏一(電通大) / 中村 理(シャープ) / 酒井 学(三菱電機) / 岩渕 匡史(NTT) / 奥山 達樹(NTTドコモ) / 吉田 太一(電通大) / 京地 清介(北九州市立大) / 廣友 雅徳(佐賀大) |
| 幹事補佐氏名（英） | 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.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Radio Communication Systems / Technical Committee on Signal Processing / Technical Committee on Information Theory |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Enumeration of Both-Ends-Fixed $k$-ary Necklaces and Its Applications |
| サブタイトル（和） | |
| タイトル（英） | Enumeration of Both-Ends-Fixed $k$-ary Necklaces and Its Applications |
| サブタイトル（和） | |
| キーワード(1)（和/英） | $k$進ネックレス / $k$-ary necklaces |
| キーワード(2)（和/英） | 記号力学系 / symbolic dynamics |
| キーワード(3)（和/英） | $beta$進展開 / $beta$-expansions |
| キーワード(4)（和/英） | $k$進 de Bruijn 系列 / $k$-ary de Bruijn sequences |
| キーワード(5)（和/英） | 自己相関関数 / auto-correlation function |
| 第 1 著者 氏名（和/英） | 藤崎 礼志 / Hiroshi Fujisaki |
| 第 1 著者 所属（和/英） | 金沢大学(略称：金沢大) Kanazawa University(略称：Kanazawa Univ.) |
| 発表年月日 | 2022-01-20 |
| 資料番号 | IT2021-48,SIP2021-56,RCS2021-216 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | IT-327,SIP-328,RCS-329 |
| ページ範囲 | pp.107-112(IT), pp.107-112(SIP), pp.107-112(RCS), |
| ページ数 | 6 |
| 発行日 | 2022-01-13 (IT, SIP, RCS) |