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

点击翻译按钮获取中文摘要

長さ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|における自己相関関数値を評価し，その公式を導出した．