(57)【特許請求の範囲】
【請求項１】
繰り返して試行が行われ，Ｎ（但し，Ｎ≧２とする。）進乱数値の割当てが可能な複数の有効事象のいずれかを試行毎に示しうる乱数源と，
前記各有効事象へのＮ進乱数値の割当てを定める当番割当てに従って，前記乱数源が示した有効事象に対応するＮ進乱数値を出力する出力手段と，
前記当番割当てを，前記出力手段の出力の繰返し周期以上の割当て保持期間毎に，第ｉの割当てで前記各有効事象に割り当てるＮ進乱数値が，第ｊ（但し，ｉとｊは，ｊ≠ｉなる１〜Ｎの任意の自然数とする。）の割当てで同じ有効事象に割り当てるＮ進乱数値と異なるような第１〜第Ｎの割当てから選択される割当てに更新させる制御，及び前記割当て保持期間を，前回の割当て保持期間の１回又は複数回の経過毎に，相異なる第１〜第Ｌ（但し，Ｌ≧２とする。）の期間から選択される期間に更新させる制御であって，前記第１〜第Ｌの期間からの前記割当て保持期間の選択が，それらの各期間の長さとは無関係に出現確率分布が決まるＬ進乱数列を用いてなされるか，又はそれらの期間が予め定められた順番に従って出現するようになされる制御を行う制御手段と
を備えた乱数生成装置。
【請求項２】
さらに，前記乱数源が示した有効事象の或る長さの時系列パターンであって，前記乱数源が有効事象を示す毎にその内容が順次更新される時系列パターン，又は前記出力手段が出力した乱数値の或る長さの時系列パターンであって，前記出力手段が乱数値を出力する毎にその内容が順次更新される時系列パターンを記憶する記憶手段を備え，
前記制御手段が，前記記憶手段に記憶された時系列パターンを前記Ｌ進乱数列として読み込み，その読み込んだＬ進乱数列を用いて前記第１〜第Ｌの期間からの前記割当て保持期間の選択を行う請求項１に記載の乱数生成装置。
【請求項３】
外部からＮ（但し，Ｎ≧２とする。）進の素乱数値を取得し，取得した素乱数値を順番に，前記各素乱数値へのＮ進の新乱数値の割当てを定める当番割当てに従って，その素乱数値に対応する新乱数値に読み替えて出力する出力手段と，
前記当番割当てを，前記出力手段の出力の繰返し周期以上の割当て保持期間毎に，第ｉの割当てで前記各素乱数値に割り当てる新乱数値が，第ｊ（但し，ｉとｊは，ｊ≠ｉなる１〜Ｎの任意の自然数とする。）の割当てで同じ素乱数値に割り当てる新乱数値と異なるような第１〜第Ｎの割当てから選択される割当てに更新させる制御，及び前記割当て保持期間を，前回の割当て保持期間の１回又は複数回の経過毎に，相異なる第１〜第Ｌ（但し，Ｌ≧２とする。）の期間から選択される期間に更新させる制御であって，前記第１〜第Ｌの期間からの前記割当て保持期間の選択が，それらの各期間の長さとは無関係に出現確率分布が決まるＬ進乱数列を用いてなされるか，又はそれらの期間が予め定められた順番に従って出現するようになされる制御を行う制御手段と
を備えた乱数データ処理装置。
【請求項４】
コンピュータを，請求項３に記載の乱数データ処理装置として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，Ｎ（但し，Ｎは２以上の自然数とする。）進乱数列を生成する技術に関し，特に乱数列における乱数値の出現確率の偏りを低減する技術に関する。
【背景技術】
【０００２】
乱数列に求められる性質の１つに，乱数値の出現確率の一様性がある。２進乱数列を例にとれば，これは０と１の出現確率が等しくあるべきということである。
【０００３】
特許文献１〜３に示されように，２進乱数列においては，他の２進乱数列（以下，反転トリガ数列という。）との排他的論理和（以下，ＸＯＲと記す。）をとることで，０と１の出現確率の偏りを低減できることが知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】実開昭５６−１５６１３４号公報
【特許文献２】特開２０００−２９８５７７号公報
【特許文献３】特開２００４−１６４４８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
反転トリガ数列とのＸＯＲをとる処理で偏りを低減できるというのは，処理後の乱数列を無限区間でみてのことである。処理後の乱数列を，或る任意の有限区間でみた場合，必ずしも偏りが低減されているとは限らない：
【０００６】
例えば，反転トリガ数列における数値の変動の激しさが，元の乱数列における数値の変動の激しさと同程度の区間では，処理後の乱数列をその有限区間でみて，却って元の乱数列よりも偏りが増大していることが起こりうる。
【０００７】
このため，反転トリガ数列においては，数値の変動の激しさが一様であることよりも，むしろ変動が相対的に緩やかな区間も適宜に出現することが望まれる。
【０００８】
反転トリガ数列における変動の緩やかな区間の出現確率を評価するために，０の出現確率をβ，１の出現確率を１−βとして，０（又は１）がｓ回続けて出現したのち，１（又は０）がｓ回続けて出現する確率Ｑを求めると，Ｑ＝｛β（１−β）｝ｓとなる。ここでｓが変動の緩やかさを表す。
【０００９】
特許文献１及び２の技術では，βは例えば１／２である。このとき，Ｑ＝（１／４）ｓとなる。この式は，大きなｓ程，即ち変動が緩やかな区間程，出現しにくいことを示す。
【００１０】
特許文献３の技術では，反転トリガ数列中で同じ数値がｓ回続く確率Ｇを，Ｇ＝（１−γ）γｓ−１とすることができる。γは，特許文献３の物理乱数生成手段が０を出力する確率である。例えばγ＝１／２のとき，Ｒ＝（１／２）ｓとなる。
【００１１】
この分布Ｇでは，上記分布Ｑに比べると，ｓの増大に伴う減少が抑えられる。しかし，分布Ｇも分布Ｑと同様，ｓの単調減少関数であり，大きなｓ程出現しにくいことに変わりはない。即ち，反転トリガ数列中に，変動が緩やかな区間が出現することは稀であり，上述した有限区間で生じうる偏りの問題を防止することは難しい。
【００１２】
本発明の目的は，乱数列の有限区間でみた偏りを生じにくくすることができる技術を提供することである。
【課題を解決するための手段】
【００１３】
本願発明者は，反転トリガ数列とのＸＯＲをとる処理の意味を次のように捉えた。
【００１４】
コイン投げのベルヌーイ試行を例にとる。表が出た事象を０，裏が出た事象を１に対応させれば，コイン投げを繰り返すことで，２進乱数列を得る。
【００１５】
コインに偏りがある場合を考える。表が出る確率をα（但し，０＜α＜１／２とする。）とすると，裏が出る確率は１−αである。この偏りのあるコインを用いて，無限区間でみて，偏りの低減された２進乱数列を得るには，次のようにすればよい：
【００１６】
表１に示すように，第１，第２の割当てを考える。これら２つの割当てを適宜切り替えながら採用し，表か裏かの事象が示される毎に，そのとき採用している割当て（以下，当番割当てという。）に従って，乱数値を出力する。
【００１７】
【表１】
0005586807.tif 000002
【００１８】
コイン投げを繰り返す過程で，当番割当てとして，第１の割当てを確率βで採用し，第２の割当てを確率１−βで採用する。すると，０の出現確率Ｐ０は，第１の割当てを採用し，かつ表が出現する確率と，第２の割当てを採用し，かつ裏が出現する確率との和，Ｐ０＝αβ＋（１−α）（１−β）となる。同様にして，１の出現確率Ｐ１は，Ｐ１＝α（１−β）＋（１−α）βとなる。
【００１９】
これより，任意のβ（＞０）に対して，１／２−α＞｜１／２−Ｐ０｜の成立が確かめられる。この意味は，当番割当てを，第１，第２の割当てのいずれかに適宜に更新しさえすれば，各割当ての採用確率がどのような値であっても，無限区間でみて０と１の出現確率の偏りが改善されるということである。
【００２０】
以下では，偏りを低減する処理の対象となる乱数を素乱数と呼ぶことにする。
【００２１】
これまで，事象に乱数値を割り当てたが，表，裏の各事象をそれぞれ直接的に，素乱数値０，１とよんでもよいであろう。すると，第１の割当てを採用することは，素乱数値をそのまま出力することであり，第２の割当てを採用することは，素乱数値を反転させて出力することである。
【００２２】
素乱数値に０とのＸＯＲを施しても素乱数値は反転しない。従って，素乱数値に０とのＸＯＲを施すことは，第１の割当てを採用することである。素乱数値に１とのＸＯＲを施すと素乱数値が反転する。従って，素乱数値に１とのＸＯＲを施すことは，第２の割当てを採用することである。
【００２３】
そうすると，反転トリガ数列とは，当番割り当てを定めるものであり，反転トリガ数列における０の出現確率は，第１の割当ての採用確率βに対応し，反転トリガ数列における１の出現確率は，第２の割当ての採用確率１−βに対応する。
【００２４】
そして，当番割当てとして同じ割当てが保持される期間を，割当て保持期間と呼ぶことにすれば，反転トリガ数列中に変動の緩やかな区間が出現しにくいという従来の課題は，長い割当て保持期間が実現されにくい課題と解釈できる。
【００２５】
以上，２進乱数列を例に挙げて説明したが，反転トリガ数列とのＸＯＲをとる処理を，当番割当てを切り替える処理と捉える着想が与えられたならば，２進以上のＮ進乱数列を生成する場合にも，偏りの低減のためには，当番割当てを切り替える処理が有効であると理解できよう。その場合にも，長い割当て保持期間が実現されにくいことに起因する有限区間での偏りの問題が生じ得，かかる問題が次の発明によって解決される：
【００２６】
本発明の一観点によれば，繰り返して試行が行われ，Ｎ進乱数値の割当てが可能な複数の有効事象のいずれかを試行毎に示しうる乱数源と，前記各有効事象へのＮ進乱数値の割当てを定める当番割当てに従って，前記乱数源が示した有効事象に対応するＮ進乱数値を出力する出力手段と，前記当番割当てを，前記出力手段の出力の繰返し周期以上の割当て保持期間毎に，第ｉの割当てで前記各有効事象に割り当てるＮ進乱数値が，第ｊ（但し，ｉとｊは，ｊ≠ｉなる１〜Ｎの任意の自然数とする。）の割当てで同じ有効事象に割り当てるＮ進乱数値と異なるような第１〜第Ｎの割当てから選択される割当てに更新させる制御，及び前記割当て保持期間を，前回の割当て保持期間の１回又は複数回の経過毎に，相異なる第１〜第Ｌ（但し，Ｌ≧２とする。）の期間から選択される期間に更新させる制御であって，前記第１〜第Ｌの期間からの前記割当て保持期間の選択が，それらの各期間の長さとは無関係に出現確率分布が決まるＬ進乱数列を用いてなされるか，又はそれらの期間が予め定められた順番に従って出現するようになされる制御を行う制御手段とを備えた乱数生成装置が提供される。
【００２７】
本発明の他の観点によれば，外部からＮ進の素乱数値を取得し，取得した素乱数値を順番に，前記各素乱数値へのＮ進の新乱数値の割当てを定める当番割当てに従って，その素乱数値に対応する新乱数値に読み替えて出力する出力手段と，前記当番割当てを，前記出力手段の出力の繰返し周期以上の割当て保持期間毎に，第ｉの割当てで前記各素乱数値に割り当てる新乱数値が，第ｊの割当てで同じ素乱数値に割り当てる新乱数値と異なるような第１〜第Ｎの割当てから選択される割当てに更新させる制御，及び前記割当て保持期間を，前回の割当て保持期間の１回又は複数回の経過毎に，相異なる第１〜第Ｌの期間から選択される期間に更新させる制御であって，前記第１〜第Ｌの期間からの前記割当て保持期間の選択が，それらの各期間の長さとは無関係に出現確率分布が決まるＬ進乱数列を用いてなされるか，又はそれらの期間が予め定められた順番に従って出現するようになされる制御を行う制御手段とを備えた乱数データ処理装置も提供される。
【発明の効果】
【００２８】
長さの異なるＬ通りの割当て保持期間を出現させるにあたり，相対的に長い割当て保持期間が実現されにくいという従来の問題を回避でき，当番割当ての切替わりの激しさが種々変化することとなる。このため，当番割当ての切替わりの激しさが，乱数源が示す有効事象（素乱数値）の変動の激しさと同程度となる可能性を低減できる。この結果，乱数列の有限区間での偏りを生じにくくすることができる。
【図面の簡単な説明】
【００２９】
【図１】実施例による２進乱数生成装置の概念図，
【図２】制御手段の動作手順を示すフローチャート，
【図３】割当て保持期間の出現確率分布を示すグラフ，
【図４】他の実施例による２進乱数生成装置の概念図，
【図５】さらに他の実施例による２進乱数生成装置の概念図，
【図６】さらに他の実施例による２進乱数生成装置の概念図，
【図７】反転トリガ数列のタイミングチャート，
【図８】制御手段の動作手順を示すフローチャート，
【図９】さらに他の実施例による２進乱数生成装置の概念図，
【図１０】実施例による４進乱数生成装置の概念図。
【発明を実施するための形態】
【００３０】
図１に，実施例による２進乱数生成装置の概念図を示す。
【００３１】
雑音源１１が，自然現象である雑音を出力する。雑音源１１は，例えば，熱雑音を出力する半導体ダイオードで構成される。増幅器１２が，その雑音を増幅する。二値化回路１３が，その増幅された雑音を二値化し，結果を素乱数値として出力する。これら雑音源１１，増幅器１２，及び二値化回路１３を含んで，物理乱数源１が構成されている。
【００３２】
物理乱数源１では，発信回路２から与えられる共通クロック信号に同期して，増幅された雑音を二値化するという試行が繰り返し行われる。物理乱数源１は，試行毎に，有効事象としての２進の素乱数値０又は１を出力する。
【００３３】
シフトレジスタ３に，物理乱数源１から出力された素乱数列１ａが格納される。シフトレジスタ３は，カスケード接続された４段のレジスタで構成され，各レジスタに１つの素乱数値を格納し，発信回路２から共通クロック信号を与えられる毎に，前段のレジスタの内容を次段のレジスタにシフトさせる。
【００３４】
シフトレジスタ３の最後段のレジスタに格納された素乱数値が，順次シリアルにＸＯＲゲート６に出力される。シフトレジスタ３はまた，パラレルな読み取りも可能な構成をもち，自己に格納されている４ビットの素乱数値を，割当て保持期間決定数値３ａとして，クロック制御回路４に出力することができる。
【００３５】
クロック制御回路４が，シフトレジスタ３から読み取った割当て保持期間決定数値３ａに基づき，発信回路２からの共通クロック信号に同期して，制御クロック信号４ａを疑似乱数生成器５に与える。
【００３６】
疑似乱数生成器５は，シフトレジスタと，そのシフトレジスタを構成する相異なる２つのレジスタの内容を，両者のＸＯＲをとって最前段のレジスタに帰還させる帰還回路とを備え，制御クロック信号４ａに応じて，疑似乱数であるＭ系列（Maximal length sequence）を生成する。
【００３７】
疑似乱数生成器５は，具体的には，制御クロック信号４ａが１のとき，新たに乱数値を生成して反転トリガ数値５ａとして出力する。これは，当番割当てを更新させることに対応する。また，疑似乱数生成器５は，制御クロック信号４ａが０のとき，前回出力した乱数値と同一の乱数値を反転トリガ数値５ａとして出力する。これは，当番割当てを前回の割当てと同じ割当てに保持させることに対応する。
【００３８】
ＸＯＲゲート６が，シフトレジスタ３の最後段からシリアルに出力される素乱数列と，疑似乱数生成器５から出力される反転トリガ数列５ａとのＸＯＲを演算し，結果を出力乱数列ＲＮとして外部に出力する。
【００３９】
図２は，クロック制御回路４と疑似乱数生成器５の動作を示すフローチャートである。両者が，以下のようにして，反転トリガ数列５ａを通じて，当番割当て及び割当て保持期間を更新させる制御を行う。
【００４０】
以下では，簡単のため，当番割当てを同じ割当てに保持する割当て保持期間の長さを，発信回路２が出力する共通クロック信号の繰返し周期を単位として表す。
【００４１】
まず，クロック制御回路４は，シフトレジスタ３から割当て保持期間決定数値３ａを読み込み，その値を用いて，割当て保持期間を決定する（手順Ｓ２１）。具体的には，クロック制御回路４は，割当て保持期間決定数値３ａを１０進数に変換した値に，１を加えた値を割当て保持期間とする。割当て保持期間決定数値３ａは，４ビットの素乱数値００００〜１１１１であるから，割当て保持期間は，１〜１６から選ばれることになる。
【００４２】
そして，クロック制御回路４は，その決定した割当て保持期間の間，発信回路２から共通クロック信号を与えられる毎に，制御クロック信号４ａとして，０を出力する（手順Ｓ２２及びＳ２３のＮＯ）。この期間は，疑似乱数生成器５が反転トリガ数値５ａの値を変化させない。即ち，ＸＯＲゲート６において当番割り当てが保持される。
【００４３】
なお，クロック制御回路４は，割当て保持期間が経過したか否かの判定（手順Ｓ２３）を，発信回路２からの共通クロック信号をカウントすることにより行える。
【００４４】
次に，クロック制御回路４は，割当て保持期間が経過すると（手順Ｓ２３のＹＥＳ），制御クロック信号４ａとして，１を出力する（手順Ｓ２４）。これにより，疑似乱数生成器５が，新たに乱数値を生成して反転トリガ数値５ａとして出力する（手順Ｓ２５）。即ち，ＸＯＲゲート６において当番割当ての更新がなされる。そして，再び手順Ｓ２１に戻って同じ手順を繰り返す。
【００４５】
以上のようにして，疑似乱数生成器５が，割当て保持期間毎に，当番割当てを更新させる制御を行い，クロック制御回路４が，前回の割当て保持期間の１回の経過毎に，割当て保持期間決定数値３ａを読み込んで，割当て保持期間を更新させる制御を行う。
【００４６】
表２に，割当て保持期間別にその出現確率を示す。表２で，ｐは，物理乱数源１が０を出力する確率を示す。括弧書きは，割当て保持期間に対応する４ビットの割当て保持期間決定数値３ａを示す。
【００４７】
【表２】
0005586807.tif 000003
【００４８】
割当て保持期間決定数値３ａは４ビットであるから，１６進の乱数値とみることができる。その各１６進乱数値の出現確率は，物理乱数源１が０を出力する確率ｐ（１を出力する確率１−ｐ）のみによって決まり，割当て保持期間の長さとは無関係である。クロック制御回路４は，この１６進乱数列としての割当て保持期間決定数値３ａを用いて，割当て保持期間の１〜１６からの選択を行う。
【００４９】
図３は，割当て保持期間の出現確率分布を示すグラフである。横軸は割当て保持期間の長さを示し，縦軸は出現確率を示す。
【００５０】
折線グラフＩが，本実施例による割当て保持期間の出現確率分布である。これは表２の各出現確率をプロットしたものである。この確率分布が規格化されていること，即ち表２の出現確率の総和が１であることは，二項定理を用いて容易に示される。
【００５１】
ｐの値は，物理乱数源１の偏りが極端な場合を想定して，ｐ＝０．４とした。但し，ｐが１／２に近い程，この確率分布Ｉが一様分布に近づき，ｐ＝１／２で完全に一様分布に一致することが，表２から分かる。
【００５２】
なお，本明細書において，或る事象の出現確率とは，１００００回の試行におけるその事象の出現回数の相対頻度をいうものとする。
【００５３】
グラフＵが，一様分布（Uniform distribution）を示す。割当て保持期間の候補の数が１６通りであるから，１／１６の値を示す。
【００５４】
折線グラフＧ１〜Ｇ４は，比較例による割当て保持期間の出現確率分布を示す。その一般式は，割当て保持期間の長さをｓとしたとき，Ｇ＝（１−γ）γｓ−１と表され，これは幾何分布（Geometric distribution）である。この式は次のようにして得た。
【００５５】
比較例として，特許文献３の技術を想定した。これは，図１の疑似乱数生成器５に与える制御クロック信号４ａが，任意の単なる乱数列である場合に相当する。その乱数列における０の出現確率をγとすれば，０がｓ回続く確率は，（１−γ）γｓで与えられ，これをｓに関する０から∞までの総和が１となるように規格化すると，（１−γ）γｓ−１を得る。なお，これをファーストサクセス分布と呼ぶ流儀もあるが，本明細書では，等比数列（幾何数列）で表される確率分布はすべて幾何分布の概念に含まれるものとする。
【００５６】
折線グラフＧ１はγ＝１／２，折線グラフＧ２はγ＝０．６，折線グラフＧ３はγ＝０．７，折線グラフＧ４はγ＝０．８の場合をそれぞれ示す。
【００５７】
幾何分布Ｇ１〜Ｇ４は，割当て保持期間の長さｓの単調減少関数であり，速やかにゼロに収束している。即ち，幾何分布Ｇ１〜Ｇ４に従う従来技術では，長い割当て保持期間の出現が稀である。このことは，従来の反転トリガ数列は，数値の変動が激しく，かつその激しさが殆ど変化しないことを意味する。そして，従来は，反転トリガ数列の変動の激しさが，素乱数列の変動の激しさと同程度の区間では，出力乱数列をその有限区間でみて，却って素乱数列よりも偏りが増大しうるという弊害が生じていた。
【００５８】
本実施例の確率分布Ｉの方が，比較例の分布Ｇ１〜Ｇ４よりも，一様分布Ｕに近い。本実施例では，割当て保持期間の長さと元々無関係な出現確率分布をもつ１６進乱数値に，事後的に割当て保持期間を対応付ける手法を採ったから，長い割当て保持期間が出現しにくいという従来の問題を回避でき，一様分布Ｕに近い分布Ｉの実現が容易となる。
【００５９】
なお，或る確率分布の，一様分布への近さは，例えば，その確率分布が示す各値と，一様分布が示す一定値との差の絶対値の総和で定量化できる。この値は，実施例の確率分布Ｉでは約０．３，比較例の確率分布Ｇ１では約１．４，確率分布Ｇ２では約１．２，確率分布Ｇ３では約１．０，確率分布Ｇ４では約０．８であった。
【００６０】
本実施例によれば，長さ１〜１６の割当て保持期間のうち，長さ８以上の相対的に長い割当て保持期間も，反転トリガ数列５ａ中に適宜に出現するから，反転トリガ数列５ａの変動の激しさが種々変化することとなる。このため，反転トリガ数列５ａの変動の激しさが，素乱数列１ａの変動の激しさと同程度となる区間が存在する可能性を低減できる。従って，従来技術における上記弊害を緩和できる。
【００６１】
本実施例において，１６通りの割当て保持期間のうち，相対的に長いものの出現は，素乱数列がもつ変動の激しさを減殺することなく出力乱数列中に生かす効果をもち，相対的に短いものの出現は，出力乱数列の変動を促進する効果をもつ。確率分布Ｉが一様分布Ｕに近いということは，これらの効果が適度にバランスされているということであり，この結果，出力乱数列の有限区間での偏りを生じにくくすることができる。
【００６２】
なお，１６通りの割当て保持期間の選択に用いる１６進乱数列は，その出現確率分布が割当て保持期間の長さに無関係に決まるものであれば，その生成源は特に限定されず，例えば物理乱数や疑似乱数を用いてもよい。本実施例では，その１６進乱数列の生成源を，偏りを低減する処理の対象である物理乱数源１としたから，１６進乱数列を得るための専用の乱数源が不要となり，装置の簡素化が図られる。
【００６３】
図４は，他の実施例による２進乱数生成装置の概念図である。この例では，図１の例において，シフトレジスタ３を，ＸＯＲゲート６の後段に配置し，そのシフトレジスタ３に格納されている４ビットの出力乱数値ＲＮを，割当て保持期間決定数値３ｂとした。出力乱数列ＲＮは，物理乱数源１が出力する素乱数列１ａよりも偏りが改善されているから，表２のｐの値を，図１の例の場合よりも，１／２に近づけることができる。
【００６４】
図５は，さらに他の実施例による２進乱数生成装置の概念図である。この例では，図４の疑似乱数生成器５の代わりに，レジスタ７を備えた。レジスタ７は，制御クロック信号４ｂが１のとき，ＸＯＲゲート６から出力された出力乱数値を１ビット取り込み，それを反転トリガ信号７ａとしてＸＯＲゲート６に帰還させ，制御クロック信号４ｂが０のとき，前回取り込んだ出力乱数値と同一の数値を反転トリガ信号７ａとしてＸＯＲゲート６に出力する。この例では，当番割り当ての更新に出力乱数値ＲＮが用いられるから，図４の疑似乱数生成器５が不要となって，装置の簡素化が図られる。
【００６５】
以上，当番割り当ての更新に乱数を用いる例を示した。当番割り当ての更新に乱数を用いると，割当て保持期間毎の当番割当ての更新が，同じ割当てが続けて採用される確率が幾何分布の示す確率以下となる条件でなされることとなる。但し，当番割当ての更新の仕方は特に限定されず，更新しさえすれば，無限区間での偏りは改善される。
【００６６】
図６は，さらに他の実施例による２進乱数生成装置の概念図である。
【００６７】
シフトレジスタ８に，物理乱数源１から出力された素乱数列１ａが格納される。シフトレジスタ８は，５段のレジスタで構成され，そのうちの１段のレジスタに格納されている１ビットの素乱数値をシーケンス決定数値８ａとして，残りの４段のレジスタに格納されている４ビットの素乱数値を割当て保持期間決定数値８ｂとして，それぞれパラレルに出力することができる。
【００６８】
制御回路９が，シフトレジスタ８から読み取ったシーケンス決定数値８ａ及び割当て保持期間決定数値８ｂを用いて，反転トリガ数列９ａを出力する。
【００６９】
図７に，反転トリガ数列９ａのタイミングチャートを例示する。
【００７０】
数値が０の期間Ｔ０は，表１の，第１の割当てが当番割当てとなる期間である。数値が１の期間Ｔ１は，表１の，第２の割当てが当番割当てとなる期間である。期間Ｔ０，Ｔ１の各々の長さが，割当て保持期間を示す。
【００７１】
このタイミングチャートは，第１の割当てに続いて第２の割当てが当番割り当てとなる（以下，｛第１の割当て→第２の割当て｝と表す。）シーケンスＸと，第２の割当てに続いて第１の割当てが当番割り当てとなる（以下，｛第２の割当て→第１の割当て｝と表す。）シーケンスＹとで構成される。各シーケンス内で割当て保持期間は等しいが（Ｔ０＝Ｔ１），シーケンス間では割当て保持期間は異なりうる。
【００７２】
図８は，このタイミングチャートを得るための，制御回路９の動作を示すフローチャートである。
【００７３】
まず，制御回路９は，以下のようにして，シーケンス及び割当て保持期間を定める（手順Ｓ８１）。即ち，制御回路９は，シフトレジスタ８からシーケンス決定数値８ａを読み込み，シーケンス決定数値８ａが０ならばシーケンスＸを採用し，シーケンス決定数値８ａが１ならばシーケンスＹを採用する。また，制御回路９は，シフトレジスタ８から割当て保持期間決定数値８ｂも読み込み，それを１０進数に変換した値に，１を加えた値を割当て保持期間とする。
【００７４】
次に，制御回路９は，採用したシーケンスが表す最初の割当てを，当番割当てに決定する（手順Ｓ８２）。例えば，手順Ｓ８１で，シーケンスＸ｛第１の割当て→第２の割当て｝を採用したならば，当番割当てを第１の割当てに決定する。また，手順Ｓ８１で，シーケンスＹ｛第２の割当て→第１の割当て｝を採用したならば，当番割当てを第２の割当てに決定する。そして，制御回路９は，その決定した当番割当てを，手順Ｓ８１で決定した割当て保持期間だけ保持する（手順Ｓ８３のＮＯ）。
【００７５】
具体的には，第１の割当てを，割当て保持期間Ｔ０保持することは，反転トリガ数値９ａとして０をＴ０個続けて出力することである。第２の割当てを，割当て保持期間Ｔ１保持することは，反転トリガ数値９ａとして１をＴ１個続けて出力することである。
【００７６】
次に，制御回路９は，割当て保持期間が経過したら（手順Ｓ８３のＹＥＳ），手順Ｓ８１で採用したシーケンスに沿って，当番割当てを次の割当てに変更し（手順Ｓ８４），その更新された当番割当てを，手順Ｓ８１で決定した同じ割当て保持期間だけ保持する（手順Ｓ８５）。
【００７７】
制御回路９は，以上の手順Ｓ８４とＳ８５を，手順Ｓ８１で採用したシーケンスに沿った当番割当ての更新が完了するまで繰り返す（手順Ｓ８６のＮＯ）。いまの例では，１つのシーケンスを構成する割当ての数が２であるから，手順Ｓ８６でＹＥＳと判定されることとなるが，１つのシーケンスを構成する割当ての数は２以上でもよく，その数に応じて手順Ｓ８４とＳ８５が繰り返される。
【００７８】
制御回路９は，手順Ｓ８１で決定したシーケンスに沿った当番割当ての更新が完了すると（手順Ｓ８６のＹＥＳ），再び手順Ｓ８１に戻って，同様の制御を繰り返す。
【００７９】
以上のようにして，制御回路９が，割当てを時系列に並べてなるシーケンスに沿って当番割当てを更新させ，或るシーケンスに沿った更新に続けて，それと同一又は別のシーケンスに沿った更新をさせ，割当て保持期間を，１つのシーケンス内で固定とし，シーケンス間では可変として，シーケンス毎に変更させる。本実施例では，１つのシーケンスを構成する割当ての数が２であるから，割当て保持期間は，前回の割当て保持期間の２回の経過毎に更新されることとなる。
【００８０】
本実施例によれば，１つのシーケンス内に第１，第２の割当てが均等に含まれ，かつシーケンス内で割当て保持期間を共通とするので，第１，第２の割当ての出現確率が一様となる。このため，出力乱数列の無限区間でみた偏りを完全に無くすことができる。
【００８１】
また，シーケンス間では割当て保持期間が種々変化するので，反転トリガ数列９ａの変動の激しさが，素乱数列１ａの変動の激しさと同程度となる区間が存在する可能性を低減でき，出力乱数列の有限区間でみた偏りを生じにくくすることができる。
【００８２】
図９は，さらに他の実施例による２進乱数生成装置の概念図である。この例では，図６の例において，シフトレジスタ８を，ＸＯＲゲート６の後段に配置し，そのシフトレジスタ８に格納されている１ビットの出力乱数値ＲＮ，４ビットの出力乱数値ＲＮを，それぞれシーケンス決定数値８ｃ，割当て保持期間決定数値８ｄとした。出力乱数列ＲＮは，素乱数列１ａよりも偏りが改善されているから，シーケンスＸとＹの出現確率の偏り，及び１６通りの割当て保持期間の出現確率の偏りを，図６の例よりも低減できる。
【００８３】
図１０は，実施例による４進乱数生成装置の概念図である。
【００８４】
光源２０１が，１パルスあたりの光子数が単一光子レベルに抑えられたパルスレーザ光を試行毎に出射する。光源２０１は，例えば，半導体レーザと光減衰器で構成される。
【００８５】
第１のビームスプリッタ２０２に，光源２０１から出射された光が入射する。第１のビームスプリッタ２０２を透過した光は，第２のビームスプリッタ２０３に入射し，第１のビームスプリッタ２０２で反射した光は，第３のビームスプリッタ２０４に入射する。
【００８６】
第２のビームスプリッタ２０３を透過した光は，光子検出器Ａに入射し，第２のビームスプリッタ２０３で反射した光は，光子検出器Ｂに入射する。第３のビームスプリッタ２０４を透過した光は，光子検出器Ｃに入射し，第３のビームスプリッタ２０４で反射した光は，光子検出器Ｄに入射する。
【００８７】
光子検出器Ａ〜Ｄの各々は，例えば，アバランシェフォトダイオードで構成され，自己に光子が入射すると，検出信号をインタフェース２１に出力する。
【００８８】
物理乱数源２０が，光源２０１，ビームスプリッタ２０２〜２０４，及び光子検出器Ａ〜Ｄによって構成されている。物理乱数源２０では，光源２０１から出射された１つの光子を，光子検出器Ａ〜Ｄのいずれかに入射させる試行が繰り返し行われる。物理乱数源２０は，試行毎に，４進乱数値の割当てが可能な光子検出器Ａ〜Ｄのいずれかからの検出信号を有効事象として出力しうる。
【００８９】
但し，光源２０１から出射されるパルスレーザ光に偶発的に２つ以上の光子が含まれる場合もあり，１回の試行で光子検出器Ａ〜Ｄのうち２つ以上が同時に検出信号を出力する事象も生じうる。そのような事象は有効事象ではなく，無視されるものとする。
【００９０】
インタフェース２１に，光子検出器Ａ〜Ｄから出力される検出信号が入力される。インタフェース２１は，各検出信号への４進乱数値の割当てを定める当番割当てに従って，物理乱数源２０から出力された検出信号に対応する４進乱数値を出力する。
【００９１】
表３に，有効事象としての各検出信号への４進乱数値の割当てを示す。表３で，Ａ〜Ｄとは，それぞれ光子検出器Ａ〜Ｄからの検出信号のことである。
【００９２】
【表３】
0005586807.tif 000004
【００９３】
表３に示すように，第１〜第４の割当ては，第ｉの割当てで各有効事象に割り当てる４進乱数値が，第ｊ（但し，ｉとｊは，ｊ≠ｉなる１〜４の任意の自然数とする。）の割当てで同じ有効事象に割り当てる４進乱数値と異なるように構成されている。
【００９４】
このような構成は，一般に，まず第１の割当てを任意に定めると，残りの第２〜第Ｎの割当ては，その第１の割当てを巡回的にシフトさせることで得られる。このとき，第１〜第Ｎの割当ては全体としてＮ行Ｎ列の巡回行列をなす。即ち，表３を行列としてみると，４行４列の巡回行列になっている。
【００９５】
なお，表３には，有効事象への４進乱数値の割当てを示したが，有効事象Ａ〜Ｄをそれぞれ直接的に素乱数値０〜３とみれば，インタフェース２１は，物理乱数源２０から取得した素乱数値を，各素乱数値への４進の新乱数値の割当てを定める当番割当てに従って，その素乱数値に対応する新乱数値に読み替えて出力しているとも言える。
【００９６】
図１０に戻って説明を続ける。４進数用シフトレジスタ２２に，インタフェース２１から出力された４進乱数値が順番に格納される。４進数用シフトレジスタ２２は３段で構成され，インタフェース２１が４進乱数を出力する毎に，前段の内容が次段にシフトされ，最後段の４進乱数値ＲＮが外部に出力される。
【００９７】
４進数用シフトレジスタ２２は，パラレルな読み取りが可能な構成になっていて，自己が記憶している２桁の４進乱数値を，シーケンス決定数値２２ａとして，残りの１桁の４進乱数値を，割当て保持期間決定数値２２ｂとして出力することができる。
【００９８】
なお，このような４進数用シフトレジスタ２２の機能が，ハードウエアによってもソフトウエアによっても実現可能であることは当業者に理解できるであろう。
【００９９】
制御回路２３が，シーケンス決定数値２２ａを用いて，当番割当ての更新順序を定めるシーケンスを決定する。以下，具体的に説明する。第１〜第４の割当てを時系列に並べてなるシーケンス（順列）は，全部で４Ｐ４＝２４通りある。ここでは，そのうちの１６通りのシーケンスを用いるものとする。シーケンス決定数値２２ａは，２桁の４進数であるから，これを１０進数としてみると，０〜１５の１６通りの値をとる。そこで，シーケンス決定数値２２ａを１６通りの各シーケンスに対応付けることができる。
【０１００】
制御回路２３はまた，割当て保持期間決定数値２２ｂを用いて，割当て保持期間を決定する。具体的には，制御回路２３は，割当て保持期間決定数値２２ｂを１０進数として読んだ値に１を加えた値を，割当て保持期間とする。割当て保持期間決定数値２２ｂは１桁の４進数であるから，割当て保持期間は１〜４から選ばれることになる。
【０１０１】
但し，ここでは，割当て保持期間を，インタフェース２１による４進乱数値の出力の繰返し周期を単位として表した。
【０１０２】
制御回路２３の動作は，図８の例と同様である。即ち，制御回路２３は，割当て保持期間決定数値２２ｂが表す割当て保持期間毎に，シーケンス決定数値２２ａに対応するシーケンスに沿って当番割当てが更新されるように，インタフェース２１を制御し，１つのシーケンスに沿った当番割当ての更新を終える毎に，シーケンス決定数値２２ａ及び割当て保持期間決定数値２２ｂを読み込んで，同様の制御を繰り返す。
【０１０３】
図１０で，第１のビームスプリッタ２０２の透過率をＴ１，反射率をＲ１とし，第２のビームスプリッタ２０３の透過率をＴ２，反射率をＲ２とし，第３のビームスプリッタ２０４の透過率をＴ３，反射率をＲ３とする。すると，表３の，有効事象Ａ〜Ｄの出現確率は，それぞれＴ１Ｔ２，Ｔ１Ｒ２，Ｒ１Ｔ３，Ｒ１Ｒ３となる。理想的には，Ｔ１＝Ｒ１＝Ｔ２＝Ｒ２＝Ｔ３＝Ｒ３＝１／２であるが，現実には，有効事象Ａ〜Ｄの出現確率に偏りが生じる。
【０１０４】
本実施例では，１つのシーケンス内で第１〜第４の割当てが均等に出現し，かつシーケンス内で割当て保持期間を共通とするので，第１〜第４の割当ての出現確率が一様となる。このため，４進乱数値０，１，２，３のいずれの出現確率も，無限区間でみて，（Ｔ１Ｔ２＋Ｔ１Ｒ２＋Ｒ１Ｔ３＋Ｒ１Ｒ３）／４＝１／４に収束させることができ，４進乱数値の出現確率の，ビームスプリッタ２０２〜２０４の透過率及び反射率への依存性を無くすことができる。
【０１０５】
また，シーケンス間では，割当て保持期間が可変であるから，当番割当ての切替わりの激しさが種々変化することとなる。このため，当番割当ての切替わりの激しさが，物理乱数源２０が示す有効事象の変動の激しさと同程度となる可能性を低減でき，出力乱数列の有限区間での偏りを生じにくくすることができる。
【０１０６】
以上，実施例に沿って本発明を説明したが，本発明はこれに限られない。
【０１０７】
上記各実施例では，第１〜第Ｌの期間からの割当て保持期間の選択を，Ｌ進乱数列（割当て保持期間決定数値）を用いて行うこととしたが，第１〜第Ｌの期間が，予め定められた順番に従って割当て保持期間に採用されるようにしてもよい。例えば，第１〜第Ｌの期間を或る順列で時系列に並べてなるシーケンスが周期的に繰り返されるようにすれば，第１〜第Ｌの期間の出現確率分布を一様分布とすることができる。
【０１０８】
上記各実施例では，素乱数列と同じ基数をもつ乱数列を外部に出力することとしたが，両者の基数が異なっていてもよい。例えば，Ｎが２のｍ乗（但し，ｍは２以上の自然数とする。）の場合，出力手段が出力したＮ進の新乱数値ＲＮを，２進数に変換して外部に出力する変換手段をさらに備えてもよい。
【０１０９】
上記各実施例では，乱数生成装置のハードウエア構成を示したが，各装置（但し，物理乱数源１及び２０を除く。）の少なくとも一部の機能は，ソフトウエアによっても実現できる。また，上記各実施例では，物理乱数源１及び２０を，偏りを低減する処理の対象としたが，疑似乱数源を，偏りを低減する処理の対象としてもよい。その場合は，その疑似乱数源もソフトウエアによって実現することができる。この他，種々の変更，改良，及び組み合わせ等が可能なことは当業者に自明であろう。
【産業上の利用可能性】
【０１１０】
本発明は，例えば，確率過程を伴う現象のシミュレーション，数値計算，暗号技術，ゲームといったＮ進乱数を用いるあらゆる用途に利用することができる。
【符号の説明】
【０１１１】
１…物理乱数源（乱数源），
１１…雑音源，
１２…増幅器，
１３…二値化回路，
１ａ…素乱数列，
２…発信回路，
３…シフトレジスタ（記憶手段），
３ａ…割当て保持期間決定数値（Ｌ進乱数列），
３ｂ…割当て保持期間決定数値（Ｌ進乱数列），
４…クロック制御回路（制御手段），
４ａ…制御クロック信号，
５…疑似乱数生成器（制御手段），
５ａ…反転トリガ数列，
６…ＸＯＲゲート（出力手段），
７…レジスタ（制御手段），
７ａ…反転トリガ数列，
８…シフトレジスタ（記憶手段），
８ａ…シーケンス決定数値，
８ｂ…割当て保持期間決定数値（Ｌ進乱数列），
８ｃ…シーケンス決定数値，
８ｄ…割当て保持期間決定数値（Ｌ進乱数列），
９…制御回路（制御手段）
９ａ…反転トリガ数列，
９ｂ…反転トリガ数列，
２０…物理乱数源（乱数源），
２０１…光源，
２０２〜２０４…ビームスプリッタ，
２１…インタフェース（出力手段），
２２…４進数用シフトレジスタ（記憶手段），
２２ａ…シーケンス決定数値，
２２ｂ…割当て保持期間決定数値（Ｌ進乱数列），
２３…制御回路（制御手段），
Ａ〜Ｄ…光子検出器，
ＲＮ…出力乱数列。
【要約】
【課題】乱数列の有限区間でみた偏りを生じにくくすることができる技術を提供する。
【解決手段】乱数源１が出力した素乱数列１ａと，反転トリガ数列５ａとがＸＯＲゲート６に入力される。反転トリガ数列５ａを通じて，素乱数列１ａが，各素乱数値への新乱数値の割当てを定める当番割当てに従って読み替えられて出力されるように，ＸＯＲゲート６を制御する。疑似乱数生成器５が，その当番割当てを，ＸＯＲゲート６の出力の繰返し周期以上の割当て保持期間毎に，相異なる第１，第２の割当てから選択される割当てに更新させる。クロック制御回路４が，その割当て保持期間を，前回の割当て保持期間の経過毎に，相異なる第１〜第１６の期間から選択される期間に更新させる。その第１〜第１６の期間からの割当て保持期間の選択を，それらの各期間の長さとは無関係に出現確率分布が決まる１６進乱数列３ａを用いて行う。
【選択図】図１【図１】
0005586807.tif 000005
【図２】
0005586807.tif 000006
【図３】
0005586807.tif 000007
【図４】
0005586807.tif 000008
【図５】
0005586807.tif 000009
【図６】
0005586807.tif 000010
【図７】
0005586807.tif 000011
【図８】
0005586807.tif 000012
【図９】
0005586807.tif 000013
【図１０】
0005586807.tif 000014