(57)【要約】【課題】ロジスティック写像を高速生成することができ、よく混じり合った０と１との符号列を高速に生成することができるロジスティック写像用固定小数点演算器を提供する。【解決手段】所定ビット長で固定小数点演算する演算器１０であって、所定ビット長のビットコードである入力値Ｘｔの反転Ｘｔ′プラス１である所定ビット長のビットコードである第二値（Ｘｔ′＋１）を求める第二値取得手段１２と、前記入力値Ｘｔと前記第二値とを乗算する乗算手段１３と、所定ビット長のビットコードである初期値Ｘ０の入力を受け付けて前記第二値取得手段１２へ前記入力値Ｘｔとして入力する初期値入力手段１１と、前記乗算手段１３が得た結果を所定ビット長の２倍のビット長のビットコードとした場合の３ビット目から所定ビット長のビットコードを取得してこれを前記第二値取得手段１２の前記入力値Ｘｔとして入力する入力値入力手段１４，１１とを具備し、前記初期値Ｘ０が入力されてから前記乗算手段１３が得た結果から所望の値を順次取得する写像取得手段１４とを具備する。【選択図】　　　　図１
2004093756.tif 000002
【特許請求の範囲】
【請求項１】
所定ビット長で固定小数点演算する演算器であって、所定ビット長のビットコードである入力値Ｘｔの反転Ｘｔ′プラス１である所定ビット長のビットコードである第二値（Ｘｔ′＋１）を求める第二値取得手段と、前記入力値Ｘｔと前記第二値とを乗算する乗算手段と、所定ビット長のビットコードである初期値Ｘ０の入力を受け付けて前記第二値取得手段へ前記入力値Ｘｔとして入力する初期値入力手段と、前記乗算手段が得た結果を所定ビット長の２倍のビット長のビットコードとした場合の３ビット目から所定ビット長のビットコードを取得してこれを前記第二値取得手段の前記入力値Ｘｔとして入力する入力値入力手段とを具備し、前記初期値Ｘ０が入力されてから前記乗算手段が得た結果から所望の値を順次取得する写像取得手段とを具備することを特徴とするロジスティック写像用固定小数点演算器。
【請求項２】
請求項１において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の３ビット目を順次取り出して疑似乱数Ｙｔ，１（ｔ＝１，２，・・・）を出力することを特徴とするロジスティック写像用固定小数点演算器。
【請求項３】
請求項１又は２において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の３ビット目以降のビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器。
【請求項４】
請求項１〜３の何れかにおいて、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の先頭の２ビットを最下位に移動したビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器。
【請求項５】
請求項１〜４の何れかにおいて、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の先頭２ビット及び下位の所定ビットを切り捨てたビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器。
【請求項６】
請求項１〜５の何れかにおいて、前記写像取得手段は、前記乗算手段が得たビットコードを順次出力することを特徴とするロジスティック写像用固定小数点演算器。
【請求項７】
請求項１〜６の何れかにおいて、前記演算器を集積回路で実現したことを特徴とするロジスティック写像用固定小数点演算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ロジスティック写像を高速に求めることができるロジスティック写像用固定小数点演算器に関する。
【０００２】
【従来の技術】
近年、コンピュータネットワークや携帯電話の発達により、大量のディジタルデータが送受信される時代となり、必要な情報を必要な相手に確実に送り届ける必要がある。そのためには高品質の暗号が必要とされ、送り直しをなくすためには拡散符号化が必要である。
【０００３】
このような拡散符号系列を発生する新たな手法として、ロジスティックマップ（ロジスティック写像）を用いたスペクトル拡散信号発生方法が開示されている（特開２０００−２５２７５１号公報）。
【０００４】
ここで、ロジスティック写像はカオス的な振る舞いをする数列として知られており、ロジスティック写像Ｘｔ＋１＝ｃＸｔ（１−Ｘｔ），Ｘｔ＝Ｘｔ＋１がｃ＝４のとき、リヤプノフ指数λ＝Ｉｎ２＝０．６９３・・・を持つカオスを生成することもよく知られている。
【０００５】
何れにしてもこのような手法を用いて、よく混じり合った０と１との符号列の高速生成は、上述したような暗号化復元だけでなく、可逆的圧縮展開、ＴＰＳ（巡回セールスマン問題）やＮａｐ−Ｚａｋ問題などの解決、すなわち、ディジタルコンピュータの問題解決能力を向上、発展させるために不可欠である。
【０００６】
【発明が解決しようとする課題】
ところで、特開２０００−２５２７５１号公報に開示されているように、ロジスティック写像に同相変換量子化を加味した計算は、ディジタルコンピュータで行うことができる。かかる計算をＯＳ上で行う場合、例えば、浮動小数点６４ビット倍精度、有効数字５２ビット、つまり２進数で２−５２、すなわち、１０進数で１０−１６の精度では数値計算を実行できるが、１つの写像を取得するのにマイクロセコンドオーダの時間がかかるので、例えば、ＴＳＰやＮａｐ−Ｚａｋの問題を解決するには全く不十分である。
【０００７】
一方、ＣＭＯＳ電子回路を用いて内部状態を高速に決定できる一次元写像回路が提案されている（特開平７−２６２１５９号公報）。
【０００８】
しかしながら、この公報に開示された技術は、ロジスティック写像のアナログ電子回路で決定した内部状態をＡ／Ｄ変換しなければならず、よく混じり合った０と１との符号列を直接高速生成するものではない。
【０００９】
本発明はこのような事情に鑑み、ロジスティック写像を高速生成することができ、よく混じり合った０と１との符号列を高速に生成することができるロジスティック写像用固定小数点演算器を提供することを課題とする。
【００１０】
【課題を解決するための手段】
前記解題を解決する本発明の第１の態様は、所定ビット長で固定小数点演算する演算器であって、所定ビット長のビットコードである入力値Ｘｔの反転Ｘｔ′プラス１である所定ビット長のビットコードである第二値（Ｘｔ′＋１）を求める第二値取得手段と、前記入力値Ｘｔと前記第二値とを乗算する乗算手段と、所定ビット長のビットコードである初期値Ｘ０の入力を受け付けて前記第二値取得手段へ前記入力値Ｘｔとして入力する初期値入力手段と、前記乗算手段が得た結果を所定ビット長の２倍のビット長のビットコードとした場合の３ビット目から所定ビット長のビットコードを取得してこれを前記第二値取得手段の前記入力値Ｘｔとして入力する入力値入力手段とを具備し、前記初期値Ｘ０が入力されてから前記乗算手段が得た結果から所望の値を順次取得する写像取得手段とを具備することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１１】
本発明の第２の態様は、第１の態様において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の３ビット目を順次取り出して疑似乱数Ｙｔ，１（ｔ＝１，２，・・・）を出力することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１２】
本発明の第３の態様は、第１又は２の態様において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の３ビット目以降のビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１３】
本発明の第４の態様は、第１〜３の何れかの態様において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の先頭の２ビットを最下位に移動したビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１４】
本発明の第５の態様は、第１〜４の何れかの態様において、前記写像取得手段は、前記乗算手段が得た結果を前記所定ビット長の２倍のビット長のビットコードとした場合の先頭２ビット及び下位の所定ビットを切り捨てたビットコードをＰＮ信号として順次出力することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１５】
本発明の第６の態様は、第１〜５の何れかの態様において、前記写像取得手段は、前記乗算手段が得たビットコードを順次出力することを特徴とするロジスティック写像用固定小数点演算器にある。
【００１６】
本発明の第７の態様は、第１〜６の何れかの態様において、前記演算器を集積回路で実現したことを特徴とするロジスティック写像用固定小数点演算器にある。
【００１７】
【発明の実施の形態】
以下、本発明を実施形態に基づいて説明するが、本発明はこれに限定されるものでないことは言うまでもない。
【００１８】
図１には一実施形態に係るロジスティック写像用固定小数点演算器の機能ブロックを示す。図１に示すように、本実施形態のロジスティック写像用固定小数点演算器１０は、所定ビット長のビットコードである初期値Ｘ０の入力を受け付ける入力値Ｘｔとして入力する初期値入力手段として機能する入力部１１と、入力部１１からの入力値Ｘｔの反転Ｘｔ′プラス１である所定ビット長のビットコードである第二値（Ｘｔ′＋１）を求める第二値取得手段１２と、入力部１１からの入力値Ｘｔと第二値取得手段１２からの第二値（Ｘｔ′＋１）とを乗算する乗算手段（掛算器）１３と、掛算器１３が得た結果を取得するセレクタ１４とを具備する。ここで、セレクタ１４は、所定ビット長の２倍のビット長のビットコードとした場合の３ビット目から所定ビット長のビットコードを取得してこれを第二値取得手段１２の入力値Ｘｔとして入力するように入力部１１へ戻すように機能し、入力部１１は戻された値を入力値Ｘｔとして第二値取得手段１２へ出力するように機能するので、このとき、セレクタ１４及び入力部１１は入力値入力手段として機能する。また、セレクタ１４は、初期値Ｘ０が入力されてから掛算器１３が得た結果、すなわち、初期値Ｘ０が入力されることによって掛算器１３が出力した値、さらに出力の一部が入力値Ｘｔとして入力部１１へ戻されることにより掛算器１３が繰り返し出力した値から、所望の値を順次取得する写像取得手段として機能する。
【００１９】
このようなロジスティック写像用固定小数点演算器１０は、固定小数点演算を実現する集積回路、例えば、ＣＭＯＳからなるＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）などの専用チップにより構成されるものであるが、以下、具体的な機能を示しながらさらに詳細に説明する。
【００２０】
本実施形態のロジスティック写像用固定小数点演算器１０は、ロジスティック写像Ｘｔ＋１＝４Ｘｔ（１−Ｘｔ），Ｘｔ＝Ｘｔ＋１を同相変換量子化し、固定小数点演算で高速演算するものである。固定小数点の桁数は特に限定されないが、実用的なロジスティック写像を得るためには最低３２ビット以上、好ましくは５２ビット以上とするのがよく、所定の固定小数点を選択できるようにしてもよい。なお、５２ビット固定小数点演算は、３２ビットディジタルコンピュータでの浮動小数点６４ビット精度となる。
【００２１】
図２には、ロジスティック写像用固定小数点演算器１０によって６ビット固定小数点で演算した計算過程を示す。図２に示すように、６ビットのビットコードである（００１０１１）を初期値Ｘ０として入力部１１へ入力すると、入力値Ｘｔ＝（００１０１１）が第二値取得手段１２へ入力され、その反転Ｘｔ′プラス１である６ビット長のビットコードである第二値（Ｘｔ′＋１）＝（１１０１００）＋（１）＝（１１０１０１）が第二値取得手段１２から出力される。
【００２２】
ここで、初期値（００１０１１）は、１０進数の１１である｛１１｝（１０進数の１１を意味する）を２進数で表したものであり、６ビット（２６＝６４）の固定小数点演算では１１／６４＝０．１７１８７５という小数を表す。一方、第二値（Ｘｔ′＋１）＝（１１０１０１）は、６ビット固定小数点演算では｛１１｝の補数（１−Ｘ０）＝｛５３｝であり、小数で表すと、５３／６４＝０．８２８１２５＝（１−０．１７１８７５）となる。
【００２３】
次に、掛算器１３は、入力部１１からのＸｔ＝（００１０１１）と、第二値取得手段１２からの第二値（Ｘｔ′＋１）＝（１１０１０１）＝（１−Ｘｔ）とを掛け算する。このとき、図示のようにビットシフトを行って加算すればよく、結果は先頭に０を付けて１２ビットで得られるとすると、先頭の２桁は必ず００となる。
【００２４】
ここで、掛算器１３での計算は、Ｘｔ（１−Ｘｔ）となり、｛５８３｝＝５８３／４０９６＝０．１７１８７５×０．８２８１２５となる。したがって、これを４倍算するとロジスティック写像となるが、この場合には、４倍算を行う必要はなく、その代わりに先頭の００を末尾に移動したデータを出力値とするようにすればよい。
【００２５】
したがって、レジスタ１４は、掛算器１３からの出力を所定ビット長（この場合には６ビット長）の２倍のビット長（この場合には１２ビット長）のビットコードとした場合の先頭の２ビットを末尾に移動し又は捨て、このデータから各種出力を得ると共に、先頭の２桁の次の３ビット目から６ビットのビットコード（（１００１００）を次のＸｔ＋１として入力部１１へ戻す。これにより、これをＸｔとした演算が再度行われ、これが繰り返される。この演算の繰り返しは、所定の回数、或いは終了の指示があるまで繰り返すようにしてもよいし、一回の出力を取り出した後、指示がある毎に演算を繰り返すようにしてもよい。
【００２６】
このような演算を５２ビット固定小数点演算で実施した様子を図３及び図４に示す。演算の手順は同一であり、５２ビットの初期値Ｘ０が入力部１１へ入力されると、これがＸｔとして第二値取得手段１２へ入力され、５２ビットの（１−Ｘｔが取得され、掛算器１３でＸｔ（１−Ｘｔ）が演算され、セレクタ１４にその結果が出力され、セレクタ１４では結果を１０４ビット長としたときの３ビット目から５２ビットをＸｔ＋１として入力部１１へ戻す処理をすると共に、所望の形式で出力する。
【００２７】
ここで、掛算器１３の出力値を１０４ビット長としたときの先頭の００の次の値をＹ１，１とし、これを順次並べたＹｔ，１（ｔ＝１，２，３・・・）は質のよい乱数となる。
【００２８】
また、先頭の２ビットを末尾に移動した１０４ビットの出力も、０と１の連なり分布が十分満足できる確率分布を示しており、これを乱数として使用することもできる。ここでは、これをＰＮ（ｐｓｅｕｄｏ　ｎｏｉｓｅ）信号と呼ぶ。また、このようなＰＮ信号を取り出す場合には、３ビット目（先頭の２ビットを末尾に移送した信号からは先頭）から９６ビットのビットコードを出力すると、９６＝３２×３＝１６×６＝８×１２となるので、扱うのに都合のよい信号となる。
【００２９】
さらに、出力をソフト的に処理して組み合わせや順列を取り出すことができるのは勿論である。このような組み合わせや順列は、例えば、疑似乱数Ｙｔ，１（ｔ＝１，２，３・・・）やＰＮ信号から容易に取り出すことができる。例えば、０〜１５の組み合わせを取り出したいときは、４ビットコードを順番に１６ヶ取り出して並べればよい。一方、０〜１５の順列は、重なりのない４ビットコードを１６ヶ順番に取り出し、重なるコードは捨てるようにすればよい。
【００３０】
５２ビット固定小数点演算は、浮動小数点６４ビット演算に相当すると先に説明したが、浮動小数点６４ビットでロジスティック写像をシミュレートしたときと比較して（０００・・・０）に収束しないという利点を有する。
【００３１】
ここで、１万個の初期値を入力したときの周期を見つけた結果を図５に示す。また、１３万個の初期値に対して浮動小数点６４ビットで四捨五入した場合と切り捨て処理した場合とにおいて、周期を見つけた結果を図６（ａ）及び（ｂ）に示す。この結果より、固定小数点５２ビット演算では、９２％以上は、８３４０９１０の周期を有し、浮動小数点６４ビット演算と比較して（００・・・０）に収束しがたいことがわかった。
【００３２】
また、ディジタルコンピュータ上でこのような演算を行うと、一回の写像を計算するのにμｓｅｃオーダの時間がかかるが、上述した演算器によると、ｎｓｅｃオーダの時間で実現でき、高速に良質の乱数を供給できる。上述した演算器をＦＰＧＡで構成するとしてシミュレーションすると、一回の写像の処理時間は６６ｎｓｅｃとなるので、０．５μｍ程度の技術で製造した集積回路で実現すると一回の写像の処理時間は６０〜７０ｎｓｅｃとなる。
【００３３】
したがって、ストリーム暗号化復元、ＴＳＰ、Ｎａｐ−Ｚａｋなどの問題解決の高速処理を実現でき、その他、コンピュータグラフィックス、作曲への応用、ディジタルファイルの可逆的圧縮展開などへの適用など幅広い用途が期待できる。
【００３４】
以上説明したロジスティック写像用固定小数点演算器は、上述したようにＣＭＯＳ集積回路などの専用チップにより実現でき、ディジタルコンピュータに接続又は内蔵して使用できる。したがって、この場合、入力部１１への初期値Ｘ０の入力はディジタルコンピュータを介して行われ、セレクタ１４からの出力はディジタルコンピュータへ行われるようになる。
【００３５】
勿論、専用チップとして独立して使用できるようにしてもよく、この場合には、初期値Ｘ０を入力するための手段、及び出力を表示するための手段、順次出力されるデータを格納保持するための手段、出力されたデータを取り出すためのインターフェースなどを必要に応じて設ける必要がある。
【００３６】
また、何れの場合にも、例えば、Ｙｔ，１をｎ回分、例えば、８回分ためておいて、Ｙ１，ｎを出力するようにすることもできる。
【００３７】
また、ロジスティック写像の性質から、初期値Ｘ０によっては早期に周期に入ってしまう場合があるので、予めディジタルコンピュータなどで検証して入力するか、予め周期に入ってしまうことがわかっているもの、又は周期に入りやすい範囲のものは入力しないようにするのが好ましい。
【００３８】
【発明の効果】
以上説明したように、本発明のロジスティック写像用固定小数点演算器は、所定ビット長のビットコードである入力値Ｘｔの反転Ｘｔ′プラス１である所定ビット長のビットコードである第二値（Ｘｔ′＋１）を求め、入力値Ｘｔと前記第二値とを乗算し、この結果を所定ビット長の２倍のビット長のビットコードとした場合の３ビット目から所定ビット長のビットコードを取得してこれを元に戻して入力値Ｘｔとして演算を繰り返すことにより、ロジスティック写像を順次高速に取得することができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るロジスティック写像用固定小数点演算器の機能ブロック図である。
【図２】本発明の一実施形態に係るロジスティック写像用固定小数点演算器の演算を６ビットで説明する説明図である。
【図３】本発明の一実施形態に係るロジスティック写像用固定小数点演算器の演算を５２ビットで実行する様子を説明する図である。
【図４】本発明の一実施形態に係るロジスティック写像用固定小数点演算器の演算を５２ビットで説明する説明図である。
【図５】本発明の一実施形態に係るロジスティック写像用固定小数点演算器で実現したＹｔ，１の周期の長さを示す図である。
【図６】ロジスティック写像を浮動小数点６４ビットで演算したときの周期の長さを示す図である。
【符号の説明】
１０　ロジスティック写像用固定小数点演算器
１１　入力部
１２　第二値取得手段
１３　掛算器
１４　セレクタ
【図１】
2004093756.tif 000003
【図２】
2004093756.tif 000004
【図３】
2004093756.tif 000005
【図４】
2004093756.tif 000006
【図５】
2004093756.tif 000007
【図６】
2004093756.tif 000008