Performance analysis and optimization of source coding based on random discretized chaotic transformations and its applications

基于随机离散混沌变换的源编码性能分析与优化及其应用

基本信息

批准号：
21K12057
负责人：
藤崎礼志
金额：
$ 2.66万
依托单位：
Kanazawa University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

長さnのk(≧2)進ネックレスとは，{0,1,...,k-1}上の有限列であって，巡回シフトに関する同値類の内，辞書式順序で最小の系列である．長さnのk進ネックレスの総数は古くから知られている[Redfield,1927]．先頭の1文字と末尾の1文字を固定した両端固定k進ネックレスの数え上げは，従来用いられた代数的接近法を適用することができないため，本研究代表者が知る限り，Redfield以来未解決であった．2021年度には，長さnの両端固定k進ネックレスの総数を記号力学系およびβ進展開に基づき数え上げた．ここでβはβ>1の実数である．2022度には，2021年度の結果を拡張し，与えられた語頭と語尾を有する長さnの両端固定k進ネックレスの総数を数え上げた．最近，Gabricらは，任意の自然数nに対して，O(n)のメモリを用いて，長さk^nの，単一のk進 de Bruijn 系列を生成するアルゴリズムを4種類提案した．1ビットあたりの計算量に関して，これらの内，3種はO(n)，残りの1種は，ならし計算量O(1)である．各種2つのアルゴリズムから成り，合計8個のk進 de Bruijn 系列を生成する[Gabric et al., 2019]．k進変換の超離散化であるk進 de Bruijn 系列の規格化自己相関関数は，時刻t=0に値1を取り，t=0を除く-n<t<nにおいて値0を取るという零相関帯(ZCZ (Zero Correlation Zone))を有することが知られている．2022年度に得られた，与えられた語頭と語尾を有する長さnの両端固定k進ネックレスの総数に基づき，任意のnに対して，Gabricらのアルゴリズムにより生成される長さk^nのk進 de Bruijn 系列8個すべてに対して，t=|n|における自己相関関数値を評価し，その公式を導出した．

长度为 n 的 k(≥2)-adic 项链是 {0,1,...,k-1} 上的有限序列，它是有关循环移位的等价类中按字典顺序排列的最小序列。长度为 n 的 k-adic 项链的总数早已为人所知 [Redfield, 1927]。具有固定第一个字符和固定最后一个字符的双固定 k-adic 项链的计数不能应用于传统的代数方法，并且据主要研究者所知，自 Redfield 以来这个问题还没有得到解决。 2021年，我们根据符号动力学系统和β-adic展开式，统计了两端长度为n固定的k-adic项链的总数。这里β是实数且β>1。 2022年，我们扩展了2021年的结果，统计了给定开头和结尾、长度为n的双端固定k-adic项链的总数。最近，Gabric 等人提出了四种算法，使用 O(n) 内存为任何自然数 n 生成长度为 k^n 的单个 k 元 de Bruijn 序列。就每一位的计算量而言，其中三个为 O(n)，其余一位为 O(1)。它由两种不同的算法组成，总共生成八个 k 元 de Bruijn 序列 [Gabric et al., 2019]。 k 元 de Bruijn 级数的归一化自相关函数是 k 元变换的超离散化，它是一个零值，在时间 t = 0 时取值 1，在 -n < t 时取值 0 < n（不包括 t = 0）。已知有一个相关区（ZCZ（零相关区））。根据 2022 年获得的长度为 n 的双端固定 k-adic 项链总数，对于任意 n，通过 Gabric 等人的算法生成的长度 k^n 我们评估了自相关函数。 t=|n| 处所有八个 k-adic de Bruijn 序列的值并推导出其公式。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

数論とエルゴード理論 in Kanazawa ー伊藤俊次先生が我々に遺されたものー

金泽的数论和遍历论-伊藤俊二教授给我们留下的-

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
迫間季生;瀬尾昌孝;陳延偉;FUJISAKI Hiroshi;Hiroshi Fujisaki;FUJISAKI Hiroshi;藤崎礼志
通讯作者：
藤崎礼志

Enumeration of Both-Ends-Fixed <i>k</i>-Ary Necklaces and Its Applications

两端固定<i>k</i>-Ary项链的枚举及其应用

DOI：
10.1587/transfun.2022tap0007
发表时间：
2023
期刊：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
影响因子：
0
作者：
迫間季生;瀬尾昌孝;陳延偉;FUJISAKI Hiroshi
通讯作者：
FUJISAKI Hiroshi

Enumeration of both-ends-fixed k-ary necklaces and Its applications

两端固定k元项链的枚举及其应用