カオス・タイムシリーズの生成方法

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	カオス・タイムシリーズの生成方法
【発明者】	【氏名】庄野克房【氏名】今野肇
【要約】	【課題】【解決手段】

【特許請求の範囲】
【請求項１】複数の初期値から出発したカオスの軌道を相互作用させることにより、特異点に収束しないようにしたことを特長とするカオス・タイムシリーズの生成方法。

【発明の詳細な説明】【０００１】
【産業上の利用分野】産業を支える技術としてのカオスに第１位に必要とされるものは、質の高い擬似乱数の生成である。非線形関数がロジスティックマップｘ_t+1＝４ｘ_t（１－ｘ_t）、ｘ_t＝ｘ_t+1のとき、タイムシリーズｘ_t、（tは離散時間、t＝0,1,2,…）、の同相変換量子化値Ｙ_t,n＝［２／π・arcsin（ｘ_t）^1/2・２ⁿ］、（nは量子化分解能、n＝１が擬似乱数、［］は小数点以下を切り捨てる）、は質の高い擬似乱数の例である。ただし、倍精度計算を行った場合である。
【０００２】産業において実用的であるためには、単精度で工業用汎用ＣＰＵにインストールして実現できなければならない。通信を含むエレクトロニクス産業において実用されている工業用汎用ＣＰＵは単精度に限られている。
【０００３】
【従来の技術】カオスの内部状態ｘ_tは実数を意味している。本来、無限の整数列で表現されねばならぬが、ディジタルコンピュータ上で計算されるときには、できるだけ高い計算精度という意味で倍精度（浮動小数点または固定小数点）演算を行い、結果として線形となるように量子区分を設けて量子化を行って観測をしている。２進小数５２ビットで内部状態ｘ_tを計算したとき、観測の量子化分解能ｎは２６までである。
【０００４】単精度の場合、特異点に容易に収束してしまうことが知られている。非線形関数がロジスティックマップの場合、特異点はｘ_t＝０．００…（原点）と０．７５００…（不動点）である。同相変換量子化ｎ＝１のときＹ_t,1＝０００…あるいは１１１…への収束となる。１１１…への収束より、０００…への収束の方が起こりやすい。
【０００５】
【発明が解決しようとする課題】非線形関数がロジスティックマップの場合、０００…への収束を避けるために、ｘ_t＞０．９９９９９（単精度）となったとき、そのときのｔの値を用いて補正を行う方法がある。この方法は擬似乱数生成のデータフローを妨げる。また、ハードウェアに大きな負担を要求する。
【０００６】この補正方法の優れた点は、０の連なりと１の連なりの分布が確率分布のまま、補正が行える点にある。ＴＳＰ（巡回セールスマン問題）やNAP－Zak（買い物の組み合わせ）問題においては、乱数の確率分布に関する性質は重要な要素となる。一方、通信においては擬似乱数はＰＮ（擬似雑音）信号として使われる。このときには、確率分布に関する保証は強くは要求されない。情報が抜けてしまわないために、００…への収束が生じないことが重要になる。
【０００７】単精度、浮動小数点演算においては、仮数部は２３ビットである。組み合わせの総数は２²³＝８４０万程度にすぎない。したがって、単精度で長い擬似乱数を生成させると、長い周期に入っている。その長さは約４０万ぐらいである。実際に使用されるＰＮ信号の長さからすると、周期に入っていることの心配は必要ではない。
【０００８】
【課題を解決するための手段】単精度において質の高い擬似乱数を生成し、かつ工業用汎用ＣＰＵにインストールできるためには、（１）組み合わせの数を原理的に増すこと、（２）補正をデータフロー形に実行できるようにすること、である。
【０００９】カオスは初期値敏感性をもつ。初期値を複数個用意し、複数本のカオスの軌道を相互作用させることにより、組み合わせの数を増やす。複数個の初期値は、原理的には、２個、ｘ₀⁽⁰⁾とｘ₀⁽¹⁾の場合を考察するとよい。
【００１０】ディジタルコンピュータを用いるとき、初期値の与え方には注意が必要である。初期値ｘ₀は実数を意味するため、１０進数の小数で与えることが常識的であるが、単精度の場合３２ビットコードで与える方が、安定した初期値を再現性よく与えられる。
【００１１】初期値ｘ₀⁽⁰⁾を１個写像する。ｘ₁⁽⁰⁾＝４ｘ₀⁽⁰⁾（１－ｘ₀⁽⁰⁾）が得られる。同様に初期値ｘ₀⁽¹⁾を１回写像する。ｘ₁⁽¹⁾＝４ｘ₀⁽¹⁾（１－ｘ₀⁽¹⁾）が得られる。差△ｘ₁＝｜ｘ₁⁽⁰⁾-ｘ₁⁽¹⁾｜を求める。差を求めるという相互作用をさせた場合である。
【００１２】
【作用】ｘ₁⁽⁰⁾とｘ₁⁽¹⁾の大小を比較する。大きい方をとり、改めてｘ₁⁽⁰⁾とする。次の世代の写像へはｘ₁⁽⁰⁾と、改めてｘ₁⁽¹⁾＝△ｘ₁としたｘ₁⁽¹⁾について行う。この計算を繰り返し実行する。
【００１３】この写像の計算は固定小数点で行っても、浮動小数点で行ってもよい。ｘ_t⁽⁰⁾、ｘ_t⁽¹⁾の両方、または片方を並べてＰＮ信号としてよい。また、同相変換量子化値Ｙ_t,n＝［２／π・arcsin（ｘ_t）^1/2・２ⁿ］により整数化したものをディジタルコードとみなし、ＰＮ信号としてもよい。
【００１４】ｘ_t⁽⁰⁾＝ｘ_t⁽¹⁾となったとき、△ｘ_t＝０となり、０に収束してしまう。そのときには、ｘ_t⁽⁰⁾かｘ_t⁽¹⁾の一方を、他の値例えばｘ_t⁽⁰⁾／２にかえる。必ずしも２で割る必要はない、２は１例である。ディジタルコードのままであれば、３２ビットの１ビットあるいは数ビットを取り出して反転するだけでもよい。このような補正はデータフローのまま実施できる。
【００１５】
【実施例】相互作用を２本の軌道の差の値にとるのは１つの例である。ゲートアレイやFPGAのようなＣＰＵデバイスにインストールするときに、ゲート数を増加させずにすむ演算を取り入れるとよい。また、写像の結果である２つの値ｘ_t⁽⁰⁾かｘ_t⁽¹⁾のいずれを改めてｘ_t⁽⁰⁾として残すかも、大きい方だけに制限されない。小さい方を残すのも選択の１つである。
【００１６】汎用デバイスにインストールするにあたって、量子化値の演算Ｙ_t,n＝［２／π・arcsin（ｘ_t）^1/2・２ⁿ］は多数のゲートを消費するであろう。あらかじめ計算してテーブル化しておくとよい。ディジタルコンピュータにおいては、関数の数値演算処理よりはルックアップテーブルの検索といった論理操作を得意とするからである。
【００１７】写像の演算をできるだけ高精度に維持して実行する方が望ましい。そのためには、浮動小数点演算よりは固定小数点演算の方が望ましい。
【００１８】２つの初期値ｘ₀⁽⁰⁾とｘ₀⁽¹⁾から出発し、差△ｘを求める相互作用を見本例としてその作用を示してきたが、初期値を３つにして組み合わせの組み合わせとすると、３２ビットの制限されたコードであってもより複雑な組み合わせを提供できることは言うまでもない。相互作用も、和、積、商といった算術演算だけでなく、ビットの反転、天地などの論理操作も利用することができる。
【００１９】本案はあくまでもカオスを生成する非線形関数の写像を単精度で忠実に実行し、その上で複数のカオスの軌道を相互作用させ、限定された組み合わせを実質的に増大させ、しかも補正をストリームに実行できることを基本思想としている。
【００２０】
【発明の効果】通信に用いられる暗号化用擬似乱数の生成は高速でなければならない。そのために専用チップ（ゲートアレイ、FPGA等）へのインストールが必要である。本案のアルゴリズムは、そのことを念頭において、必要最小限のアナログ計算を単精度で実行し、論理的処理操作を加味することにより、データフロー形に実現したものである。
【００２１】本案は通信において有用なだけではない。例えば、ＰＣのメモリの中を暗号コード化して保護をするようなとき、本案の擬似乱数は管理すべき文書の長さだけのＰＮ信号を単精度３２ビットまたは仮数２３ビットの初期値で管理するシステムを提供する。暗号鍵としての初期値を２ヶ採用しても、６４ビットあるいは４６ビットの管理でよい。ゲートアレイ、FPGA等にインストールした擬似乱数発生部はＰＣカード化でき、ＰＣ本体とは切り離して持ち運び可能になる。

【出願人】	【識別番号】５０１１３６９９４【氏名又は名称】有限会社カオス産業技術研究所【識別番号】５０１１２０７３１【氏名又は名称】株式会社ジー・エム・ツー
【出願日】	平成１３年４月１８日（２００１．４．１８）
【代理人】	【識別番号】１００１０２３３６【弁理士】【氏名又は名称】久保田直樹
【公開番号】	特開２００２－３１２１６１（Ｐ２００２－３１２１６１Ａ）
【公開日】	平成１４年１０月２５日（２００２．１０．２５）
【出願番号】	特願２００１－１１９０１０（Ｐ２００１－１１９０１０）