(57)【要約】【目的】ディジタルコンピュータのＯＳ上で、ロジスティック写像を浮動小数点６４ビット倍精度、有効数字５２ビットで計算し、固定小数点５２ビットを２進コードで取り出し、順次配列することによりＰＮ信号を生成する。そのＰＮ信号は複雑な組合せ問題を解くために、組合せと順列を取り出すために使われる。【構成】２進コードであらわされるＰＮ信号は０と１の連なりの分布が確率分をうわまわる。６４ビットコードで与える初期値から繰り返し再現でき、ＰＮ信号は初期値に固有である。周期に入るまでの長さは２２６〜１０８程度と十分長い。【選択図】　　　　図１
2004127209.tif 000002
【特許請求の範囲】
【請求項１】
ロジスティック写像をＯＳ（Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍ）上の浮動小数点６４ビット倍精度、有効数字５２ビットで逐次計算し、固定小数点５２ビットに変換して２進コードの配列としたことを特長とするＰＮ（ｐｓｅｕｄｏ　ｎｏｉｓｅ）信号生成方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
ディジタルコンピュータの進歩が止まっているように見える。ディジタルコンピュータに期待されている問題解決能力に進歩が見られないからである。ディジタルコンピュータの問題解決能力は、かつてｖｏｎ　Ｎｅｕｍａｎｎが指摘したように、質の高い乱数の高速生成に依存する。
【０００２】
ディジタルコンピュータに期待されている問題解決能力の代表的な例は、順列を利用するＴＳＰ（ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ）や組合せを利用するＮａｐ−Ｚａｋ問題である。組合せと順列をともに利用するロボットの経路選択問題も含まれている。そこでは、周期に入ることがない乱数（２進コードの配列）が必要とされる。
【０００３】
【従来の技術】
今日、ディジタルコンピュータは３２ビット幅のＣＰＵ（ｃｅｎｔｒａｌ　ｐｒｏｃｅｓｓｉｎｇ　ｕｎｉｔ）にまで発展している。その上にＯＳ（ｏｐｅｒａｔｉｎｇ　ｓｙｓｔｅｍ）が構築され、浮動小数点６４ビット倍精度、有効数字５２ビットの算術演算を可能にしている。カオスの生成が集積回路で確認され、ＡＤＣを用いた量子化観測でカオスの秩序が取り出されることがあきらかになった。このことは特願平０６−２２２３７６として出願され、本年１０月出版予定の著書（カオス　エンジニアリング、シュプリンガーフェアラーク東京、２００２年１０月出版予定）に記載されている。このことからロジスティック写像ｘｔ＋１＝４ｘｔ（１−ｘｔ）を計算し、同相変換量子化Ｙｔ，ｎ＝［２／π・ａｒｃｓｉｎ（ｘｔ）１／２・２ｎ］のｎ＝１のタイムシリーズＹｔ，１が良質の擬似乱数であることが解析された。ｔは離散時間であり、［］は小数点以下を切り捨てることを意味する。
【０００４】
ロジスティック写像の順計算とその同相変換量子化ｎ＝１を、ともに浮動小数点６４ビット倍精度、有効数字５２ビットで数値計算を実行し、出力は０か１の１ビットのみである。任意に与えた初期値から計算したとき、数１００万点を計算したところで必ず５００万点の長さの周期に入ることが知られている。
【０００５】
【発明が解決しようとする課題】
ＴＳＰやＮａｐ−Ｚａｋ問題の問題解決能力は、２進コードの組合せと順列を大量にしかも、高速に生成できるかどうかである。数１００万点で周期に入ってしまうと、組合せと順列を大量に必要とする要求には答えられない。ロジスティック写像の順計算と同相変換量子化を浮動小数点６４ビット倍精度、有効数字５２ビットでいちいち計算し、出力が２進コードの１ビットでは、高速にしかも大量に生成するという要求には答えられない。本案の実施例で具体的に示す問題で評価すると、すぐわかることである。
【０００６】
ディジタルコンピュータの普及はめざましく、ネットワーク環境もよく整えられている。ＯＳ上の浮動小数点演算は、問題解決のためのデータ処理を計算のすぐ近くで実行できるという便利性がある。ＣＰＵの外部に専用の擬似乱数またはＰＮ信号生成器をもうけるよりも、１つのＣＰＵの外部で乱数の生成と問題解決を同時に行う方が合理的である。
【０００７】
【課題を解決するための手段】
擬似乱数を生成するためには、ロジスティック写像を計算し、同相変換量子化を計算しなければならない。同相変換量子化ｎ＝１の計算は省略し、ロジスティック写像計算出力が０．５より大きければ、２進コード１を出力し、０．５より小さければ、２進コードを０として出力する。一方、ロジスティック写像を計算し、得られる６４ビット（指数１２ビット、仮数５２ビット）をそのまま、２進コードの配列を擬似乱数のかわりに使うことはできない。本案は６４ビットコードを固定小数点５２ビットに変換して２進コードを配列したものは、擬似乱数のかわりとすることができる。本案では、固定小数点５２ビットに変換した２進コードの配列をＰＮ信号と呼ぶ。
【０００８】
擬似乱数は、その２進コードの０と１の連なりの分布を調べたとき、確率分布となっている。固定小数点５２ビットに変換した２進コードの配列であるＰＮ信号は、０と１の連なりが小さい範囲では確率分布であるが、０と１の連なりが大きいところでは確率分布を上回っている。このような分布の特長は、複雑な組合せ問題の問題解決能力に有効だということを意味している。
【０００９】
ロジスティック写像の計算結果である６４ビットコードをそのまま並べて出力した配列の０と１の連なりの分布は、１の分布がおおきく、０の分布が小さく、確率分布からずれ過ぎていて、複雑な組合せ問題の問題解決能力を疎外する。
【００１０】
ロジスティック写像の写像だけの計算を行い、同相変換量子化の計算を行わないと、その分、高速に擬似乱数を生成するという要求には答えるが、１回の写像の計算で１ビットしか出力しない。一方、固定小数点５２ビットに変換した２進コードを配列したＰＮ信号は、１回の写像で５２ビットを出力する。
【００１１】
【作用】
ディジタルコンピュータのＯＳ上で、ロジスティック写像を浮動小数点６４ビット倍精度、有効数字５２ビットで計算したとき、擬似乱数が周期に入ることは知られている。周期に入る前までの擬似乱数が複雑な組合せ問題の問題解決能力をもつ。周期に入る前までの擬似乱数の長さには、カオスの初期値敏感性があるため、おおよその目安を知りうるだけだ。その長さは、有効数字５２ビットのとき、おおよそ２５２×１／２＝２２６＝１０７である。
【００１２】
ＰＮ信号も、同じように周期に入ることは避けられないが、周期に入るまでのＰＮ信号の長さが５２倍と長い。初期値によっては、１０１０を超す長さのＰＮ信号を取り出すこともできる。
【００１３】
ＰＮ信号からの組合せの生成は、たとえば４ビットコードの場合、０（００００）、１（０００１）、・・・、１５（１１１１）を初期値から重なりを許して取り出す。一方、順列は、相互に重なりのないコードの組合せであるから、ＰＮ信号の初期値から４ビットコードを順に取り出し、重ならないものだけを並べる。
【００１４】
複雑な組合せ問題の問題解決のためには、（１）組合せのみ（Ｎａｐ−Ｚａｋ問題）、（２）順列のみ（ＴＳＰ）、（３）組合せと順列の両者を必要とする問題（経路探索など）がある。両者を必要とする問題に、より高い問題解決能力が求められることは言うまでもない。
【００１５】
【実施例】
ロジスティック写像を浮動小数点６４ビット倍精度、有効数字５２ビットで計算し、固定小数点５２を出力とし、２進コードを配列したＰＮ信号を用い、組合せのみを取り出して問題解決をする具体例がＮａｐ−Ｚａｋ問題である。Ｎａｐ−Ｚａｋ問題は、私達の日常生活のいたるところに現れる。スーパーマーケットで、３０００円分の買い物をしたい。どういう商品をいくつづつ選べばよいか。答えは一通りではない。いろいろな組合せがありうる。その候補の組合せを生成してくれるのが、Ｎａｐ−Ｚａｋ問題である。
【００１６】
スーパーマーケットの品物には、バーコードで値段が付けられているだけでなく、それぞれの商品には重さがある。買い物かごごと、レジスターの台にのせたときその台が重量計になっていたとする。バーコードを読みとって値段の総計が求められるが、一方、商品の総重量が求まると、その重量となる商品の組合せを求めることができる。公平に組合せが生成されると、商品の重さを掛け合計を求めると、商品の総重量と一致する組合せが求められる。いろいろな組合せが可能になり、その組合せでもとめた値段の総計の一つはバーコードで求めた値段の総計でなければならない。
【００１７】
ＰＮ信号から順列を取り出すときには、重なりのない２進コードを順番に取り出す。重なった２進コードは捨てる。順列を用いた複雑な組合せ問題の具体例はＴＳＰである。ＴＳＰでは、ビットマップの地図上にセールスマンが巡回すべき都市に番号が付されて配置されている。地図上に配置された都市間の距離は容易に求めることができ、回るべき都市の順番が順列により与えられると、１回りするに必要な距離は容易に求まる。ＰＮ信号は、順列を公平に生成する役割をする。最短距離のみが出力される。最短距離を与える順番にセールスマンは回ってくればよい。
【００１８】
単に距離を求める問題にとどまらない。各都市で重み係数を与えることができる。たとえば、そこで荷物の積みおろしをする。重い荷物には大きな重みを与え、軽い荷物には小さい重みを与える。距離との積和を求めると、消費エネルギーが求められる。燃料消費を最小とするルートの検索問題となる。
【００１９】
ビットマップ上の経路探索や図形の出力は、組合せと順列の両者を用いた、複雑な組合せ問題の問題解決の具体例である。
【００２０】
経路探索問題の問題解決例を図１に示す。地図のビットマップサイズは１６×１６である。出発点Ａと終点Ｂがあらかじめ座標として与えられている。４点（０，１，２，３）を４ビットコード８ヶの組合せ３２ビットをＰＮ信号より取り出す。図１（ａ）のように配置されたとする。
【００２１】
（０，１，２，３）の順列を、他の初期値から生成したＰＮ信号より求める。与えられた順列にしたがって図１（ａ）の接続を変更し、距離計算を行い、短い距離のルートに置き換える。（０，１，２，３）の順列は２ビットコード４種類に対応する。Ａから変更された順列によりＢに至る最短距離のルートを図１（ｂ）のように求めることができる。
【００２２】
問題解決に至るためには、（ａ）、（ｂ）を繰り返し実行する。組合せを１０００組、順列をそれぞれに１２回試みて、図１（ｃ）のルートが得られる。ちなみに、ルート（ｃ）を出力するに要する時間は０．４ｍｓであった。
【００２３】
ビットマップを３２×３２に拡張し、８点を経由して、障害物を回避して経路選択を実行させることもできる。組合せを１０，０００回、順列を１，０００回としたとき、最短経路の出力に４０ｍｓを必要とする。図１（ｄ）は、ビットマップ１６×１６で障害物をもうけた例である。
【００２４】
図形抽出は、経路選択にくらべると解決の困難な組合せ問題である。１６×１６ビットマップ上で、正方形、矩形、菱形を抽出する例を図２に示す。まず、組合せにより４点（０，１，２，３）を図２（ａ）のように与えたとする。０，１，２，３はＴＳＰの都市番号と同じである。順列（０，１，２，３）の最短距離を求めると、図２（ｂ）のように四辺形の外周が求まる。抽出する図形として正方形、矩形、菱形のみを選び出すように制限をもうける。
【００２５】
任意に４点を組合せで与えて、四辺形を画かせるとたいていは正方形でも、矩形でも、菱形でもない。そういう組合せは捨てられ、条件を満たした図形の組合せを出力として取り出す。正方形は図２（ｃ）のように、矩形と菱形は図２（ｄ）のように出力される。
【００２６】
ビットマップ１６×１６の場合、条件を満たす図形は、約４０００回の図２（ａ）に対し１回の割合である。１回の図形出力に、組合せ３２ビットを必要とするから、条件を満たす図形１ヶが出力されるためには、２４８，０００ビットのＰＮ信号を必要とする。図２（ｂ）の巡回路を求めるためにも、同じ程度の長さのＰＮ信号を必要とする。組合せと順列を用いた問題解決のためには、十分に長いＰＮ信号の生成が不可欠である。
【００２７】
ビットマップを３２×３２、６４×６４に拡張したとしよう。１ヶの条件に合う図形を出力するためには、約６万５千回と約１００万回の組合せを必要とする。
【００２８】
ビットマップ１６×１６上の正方形が何種類あるか、矩形は何種類あるか、菱形は何種類あるか、という問題に、今日私達が手にできるＰＮ信号では答えられない。せいぜい、正方形と矩形と菱形が出力される割合が１３％、３７％、５０％ということが求められ、確率的に期待できる通りの答えが得られていることを確認できるにすぎない。
【００２９】
【発明の効果】
ディジタルコンピュータの数値計算能力はきわめて限られたものであるが、論理処理能力は十分に産業技術として有用であることがわかる。浮動小数点６４ビット倍精度、有効数字５２ビットでロジスティック写像を計算し、同相変換量子化ｎ＝１で擬似乱数Ｙｔ，１、１ビットを出力するのに対し、同じ計算精度でロジスティック写像を計算し、固定小数点５２ビットを出力するＰＮ信号は、組合せや順列を必要とする複雑な問題解決の問題解決能力を、少なくとも５２倍は向上させる。
【００３０】
今日、ディジタルコンピュータのＣＰＵは３２ビットであり、ＯＳ上の浮動小数点６４ビット倍精度計算が保証されている。今秋にもＣＰＵは６４ビットに拡張されるという。ＯＳが浮動小数点１２８ビット倍精度をサポートするようになると、ＰＮ信号の出力は５２ビットから１０４ビットに倍加される。その分、複雑な問題解決能力が向上することは言うまでもない。そういう発展は、本発明の基本思想に含まれるものである。
【図面の簡単な説明】
【図１】ビットマップ上の最短経路探索問題の問題解決例である。
【図２】ビットマップ上に４点を与えた特長のある図形抽出問題の例である。
【図１】
2004127209.tif 000003
【図２】
2004127209.tif 000004