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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K12057/
• 关键词: k進ネックレス; 記号力学系; β進展開; k進 de Bruijn 系列; 自己相関関数; 超離散力学系; マルコフ連鎖; 非対称2進数系(ABS)

長さ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）六角项链是{0,1，...，k-1}的有限序列，是循环移位的等效类别词典词典顺序的最小序列。长度为n的K型项链的总数很长一段时间[Redfield，1927年]。自从Redfield以来，尚未解决两种固定的固定k advance项链的计数，这些固定的固定k advance项链无法应用于常规使用的代数方法方法。在2021年，基于符号力学系统和β-促进的扩展，对长度为n的两端的固定k辅助项链的总数进行计数。在这里，β是β> 1的实数。在2022度时，我们扩大了2021年的结果，以计算两端的固定K辅助项链的总数，长度为n具有给定的单词启动和结尾。最近，Gabric等人。提出的四种算法使用O（n）内存为任何自然数n生成长度为k^n的单个k高级de bruijn序列。关于每位计算复杂性，其中三种是O（n），其余的是O（1）。它由两种不同的算法组成，总共产生了八个k-add de bruijn序列[Gabric等，2019]。已知K-De de Bruijn序列的归一化自相关函数是K-决策转换的超差异，已知具有零相关性（ZCZ），该相关性（ZCZ）在时间t = 0时以1为1的值，并在-n <t <n at-n <t = 0以外，值为0。基于两端的固定k高级项链的总数，长度为n，在2022年获得的给定开始和结尾，自相关函数值t = | n |评估了Gabric等人的算法产生的所有八个K ad-vanced de bruijn系列长度k^n，并得出了该公式。

项目成果

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

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

• 发表时间: 2022
• 作者: 迫間季生;瀬尾昌孝;陳延偉;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
• 作者: 迫間季生;瀬尾昌孝;陳延偉;FUJISAKI Hiroshi
• 通讯作者: FUJISAKI Hiroshi

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

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

• 发表时间: 2022
• 期刊: IEICE Technical Report
• 作者: 迫間季生;瀬尾昌孝;陳延偉;FUJISAKI Hiroshi;Hiroshi Fujisaki
• 通讯作者: Hiroshi Fujisaki