JPH0326859B2 - - Google Patents

Description

【発明の詳細な説明】

［産業上の利用分野］ この発明はシフトレジスタ回路を利用した乱数
発生装置に関し、とくに簡易な構成でありながら
性質の良好な乱数を発生できるようにしたもので
ある。 ［従来技術〕 近年Ｍ系列発生器（Maximum Length Shift
Register Sequence Generator）を利用した一様
乱数発生装置が着目されている。Ｍ系列発生器は
その係数多項式をガロア体上の原始多項式に選ん
だものであり、出力される数列の周期を係数多項
式が同一次数の範囲で最大にするものである。も
ちろんＭ系列発生器から発生される数列からその
要素をどのように取り出して乱数に用いるかにつ
いては留意する必要がある。たとえばＭ系列
｛a₁｝から｛aj，……，aj_+k｝、｛aj₊₁，……，
aj_+k+1｝，｛aj₊₂，……，aj_+k+2｝というように乱
数を選んでいくと、継続する乱数間に強い関連性
が生じ不適切である。 Ｍ系列から一様乱数を発生させる主たる手法と
してはTausworthe方法とLewis及びPayneの方
法とが知られている。 Taworthe方法では、Ｍ系列｛a_i｝の継続する
ｌ（ｐ、ただしｐは系数多項式次数）個の要素
の並べて、ｌビツトの２進小数 W_i＝0.aσ_i+r-1aσ_i+r-2……a_it+r-l を得、これを乱数とするものである。なおσはＭ
系列から相続くｌ個の要素を取り出す間隔であ
る。この手法の概要を第５図に示す。このように
生成された乱数ではＭ系列の周期Ｔと間隔σとを
互いに素に選ぶと｛W_i｝の周期もＴとなり、ま
たその一周期中にはＯが2^p-l回ずつ現われる。従
つてｐがｌより十分大きければこの乱数は一様に
分布することがわかる。 Lewis及びPayne方法は特性方程式として ｆ(D)＝D^p＋D^q＋１（ｐ＞ｑ） を用い、これによつて生成されるＭ系列｛a_i｝の
位相を適当にずらしたものを並て、２進小数 W_i＝0.a_ia_i+〓₂……a_i+〓₃ を得、これを乱数とするものである。この手法の
概要を第６図に示す。この手法のＭ系列｛a_i｝は
漸化式 a_i＝a_i-r＋a_i-q（mod2） を満たし、この結果｛W_i｝は漸化式 W_i＝W_i-pW_i-q で生成できる。ただしはビツトごとの排他的論
理和である。 しかしながら上述２つの手法は重大な欠点があ
る。即ちTauswortheの方法では乱数発生に要す
る時間が長くなつてしまう。またLewis及び
Payheの方法では一様性が不明となる欠点があ
る。この方法自体からは乱数の一様性が保証され
ていず、そのため一様性があるのかないのかを吟
味する必要がある。 ［発明が解決しようとする問題点］ この発明は以上の事情を考慮してなされたもの
であり、Ｍ系列発生器のシフトレジスタ回路から
出力される数列をシヤツフリングして出力する乱
数発生装置であつて、その構成から乱数の性質を
知ることができ、このためその性質についての吟
味する必要がなく、かつ乱数発生の所要時間が短
かいもの提供することを目的としている。 この発明はより具体的にはＭ系列発生器を利用
して性質のすぐれた乱数を簡易に生成する乱数発
生装置を提供することを目的としている。 ［問題点を解決するための手段］ この発明は以上の目的を達成するために、“１”
及び“０”を要素とする数列を発生するシフトレ
ジスタ回路と、このシフトレジスタ回路からのパ
ラレルを出力Ａを受取りＡ×Ｇの行列積を実行す
る行列積回路とを有している。ただし、Ａはベク
トルＧは行列である。 ［実施例］ 以下この発明の一実施例について説明しよう。 第１図はこの実施例を示すものであり、この図
においてシフトレジスタ回路１は７ステージのシ
フトレジスタ２及びエクスクルーシブ・オア回路
３からなつている。このシフトレジスタ回路１の
特性方程式はｆ(D)＝D⁷＋D⁴＋１である。シフト
レジスタ回路１は明らかにＭ系列発生器であり、
2⁷−１の周期を有する。 シフトレジスタ２の各ステージからの出力は行
列積回路４にパラレルに供給されている。この行
列積回路４は行列Ｇ で表わすことができる。シフトレジスタ２の各ス
テージからの出力の成分をa_i（ｉ＝０〜６）とす
れば行列積回路４の出力b_j（ｊ＝０〜６）はb_j＝
〓ⁱ a_igj_i（mod2）である。ただし、gj_iは行列Ｇの成
分である。行列積回路の出力は一旦ラツチ５にラ
ツチされたのち２進小数乱数Ｗ Ｗ＝0.b₀b₁……b₆ として出力される。 なお行列積回路４は例えば第２図に示すように
構成することができる。この図において６はエク
スクルーシブ・オア回路、７は行信号線、８は列
信号線である。 この乱数発生装置から発生する乱数の性質を理
解するために２次元での分布を求めた。これを第
３図に示す。２次元の分布とは継続する乱数
（W_i，W_i+1）の分布を調べたものである。図に示
す分布には規則性がなく、かつ一様性があること
が明らかである。このことは継続する２つの乱数
の関連性がなく、しかも乱数の発生確率が特定の
ものにかたよらないことを意味する。この乱数発
生装置の乱数がすぐれた性質を有することがわか
る。このことの詳細はのちに理解される。つぎに
行列Ｇの意味について考察を加えることにする。 結論から言えば行列Ｇによつて生成される乱数
は７ビツトの漸近的なLewis及びPayneの乱数で
ある。漸近的乱数（asymptotically random
number）の意味はのちに理解される。 まずｋ次均等分布（ｋ−distribution）の概念
を導入しよう。この概念は乱数の一様性の目安と
なるものである。 定 義 乱数｛W_i｝の継続するｋ個の要素を座標成分
とする点をx_iとするとき、ｋ次元超立方体内の任
意の点ｘ（座標成分がｌビツトの２進小数で表わ
せるもの）に対してｐ（x_i＝ｘ）＝2^-klが成立する
とき乱数｛W_i｝はｋ次均等分布をするという。
ここで確率ｐは１周期全体にわたる相対頻度を意
味する。 座標成分がｌビツトで、次元がｋであるから超
立方体内の点は2^lk個である。ｐ＝（x_i＝ｘ）＝2^-kl
であれば乱数｛w_i｝が各点ｘに均等に分布するこ
とは明らかである。 Ｍ系列に基づく系列｛w_i｝の分布に即して言え
ば、ｋ次均等分布をつぎのように言うことができ
る。 定 義 （w_i，w_i+1，……，w_i+r-1をkl組と見なすと
き、１周期にすべての成分が０の組は2^p-kl−１
回、他のすべてのパターンはいずれも2^p-kl回出現
するならば、｛w_i｝はｋ次均等分布とする（この
ことからｐklであることは明らかである）。 ｋ個の継続する乱数を用いてシミユレーシヨン
を行うときｋ次均等分布が肝要とすることは明ら
かであろう。 てLewis及びPayneの乱数がｋ次均等分布であ
るためには、乱数w_iを w_i＝0.aj_1+iaj_z+i……aj_l+i とし、ｋ＝LP／ｌ」として、次の行列G^の各行
ベクトルが線形独立になることが、必要十分であ
る（このことについてはCommunications of
the ACM Vol.26，pp516〜523を参照された
い）。 ただし、｛a_i｝はＭ系列、ｐはＭ系列の特性方
程式の次数、Lp／ｌ」はｐ／ｌを超えない最大
の整数、A_iは（a_ia_i+1……）である。 このことをｐ＝７，ｌ＝７の乱数に適用する。 まずｋ＝L1／１」＝１である。そして を満たすG^₇の行うベクトルが線形独立であれば
よい。なおG^₇のサフイツクス７はｌ＝７である
ことを示す。 他方第１図の実施例の乱数は で表わすことができる。この式において行列Ｇの
行ベクトルが線形独立なことは明らかである。こ
のことから行列式回路４から出力される乱数
（aj₁aj_z……aj₇），（aj₁＋₁aj_z+1……aj₇₊₁）が７ビ
ツト１次均等をするLewis及びPayneの乱数であ
ることがわかる。 次に、漸近的乱数との関連でこの実施例の乱数
について考察する。 一般にモンテカルロ法等のシミユレーシヨンの
ために乱数を使用するとき、要求される精度（ビ
ツト長）はその目的によりさまざまである。従つ
て任意のビツト長に対しｋ次均等分布が保証され
ていることが望ましい。例えばｐ＝７のときの数
列aj₁₊₁、aj_z+i、aj_3+i……を考えよう。そしてこの
数列のうち上位７ビツトを乱数としたときには１
次均等分布（ｋ＝L7／７」）が確立されているけ
れども、上位３ビツトを乱数としたときには２次
均等分布（ｋ＝L7／３」＝２）が確立されていな
いとしよう。そうすると、この数列からｌ＝７の
乱数を取り出すことは好ましいが、ｌ＝３の乱数
を装取り出すことは不適切となつてしまう。この
ことは不都合である。 漸近的乱数は以上の不都合が解消されている乱
数である。これはつぎのようにいうことができ
る。 定 義 次の２条件を満たすLewis及びPayneの乱数を
漸近的にランダムなｓビツトのLewis及びPayne
の乱数と呼ぶ。 条件１：行列G^_lの行ベクトルが任意のｌ（ｓ）
に対して線形独立となる。 条件２：周期が素数となる。 なお、条件２はつぎのような要請に応えるもの
である。即ち通常ｋ次元のシミユレーシヨンで乱
数を使用する場合一様乱数w_iのオーバーラツプし
ないｋ組（w_kl，w_kl+1，……w_kl+k-1）を用いる。
条件２はこの列に対してｋ次均等分布を保証する
ために必要となる。 さて、第１図の実施例で発生させられる乱数が
漸近的乱数はどうかについて考えよう。まずｌ＝
７の場合にはｋ＝１であり、 が成立しているので１次均等分布が確立している
ことは明らかである。 ｌ＝４，５及び６の場合には、ｋ＝１でありそ
れぞれ上述から が導き出され、これらの式からｌ＝４，５及び６
の場合に一次均等分布が確立されるとは明らかで
ある。 ｌ＝３の場合にはｋ＝L7／３」＝２であり、ま
た上述G^₇から が導き出される。ここで横棒で表わした第２、第
４及び第６の行ベクトルがそれぞれ第１、第３及
び第５の行ベクトルか一意的に決定されることに
留意されたい。結論から述べよう。第１、第３第
５の行ベクトルのうち任意のものを_jで表わし、
第２、第４及び第６の行ベクトルのうち対応する
ものを_j+1で表わし、さらにを（g₁，g₂，g₃，
……，g₇）で表記するとしうよ。_j+1は次のよ
うにして_jから求まる。 g_j+1,1＝g_j,7 g_j+1,2＝g_j,1 g_j+1,3＝g_j,2 g_j+1,4＝g_j,3＋g_j,7 g_j+1,5＝g_j,4 g_j+1,6＝g_j,5 g_j+1,7＝g_j,6 例えば第３行の行ベクトルｇ _j2＝（0111001）で
あるから第４行の行ベクトル_j2 ⁺ ₁＝（1010100）
となる。同様にして第２行及び第６行の行ベクト
ルも求め、つぎの行列G^₃を得る。 この行列G₃各行ベクトルは線形独立となつて
いるので、この実施例の乱数はｌ＝３の場合に２
次均等分布となることがわかる。 さて行ベクトル_j+1が行ベクトル_jから一意
的に決定されることについて考えておく。 既述のとおりｌ＝３、ｋ＝２ではつぎの式が成
立する。 この式からA_i（A_j1，A_j2またはA_j3）は A_j＝g_j,1・A₁＋g_j,2・A₂＋g_j,3・A₃＋g_j,4・A₄＋
g_j,5・A₅＋₅g_j,6・A₆＋g_j,7・A₇ である。また上の式で数列Ａの位相１つずらす
と、 を得るのでA_j+1は A_j+1＝g_j,1・A₂＋g_j,2・A₃＋g_j,3・A₄＋g_j,4・A₅
＋g_j,5・A₆＋g_j,6・A₇＋g_j,7・A₈ である。 ところでLewis及びPhayneの数列｛a_i｝（ただ
しｆ(D)＝D^pD^q＋１）ではa_i＝a_j-p＋a_i-qが成立す
るのでA₈＝A₁＋A₄である。従つて、A_j+1はつぎ
のように整理される。 A_j+1＝g_j,7・A₁＋g_j,1・A₂＋g_j,2・A₃＋（g_j,3＋
g_j,7）・A₄＋g_j,4・A₅＋g_j,5・A₆＋g_j,6・A_{7 j}からg_j+1を求め得ることは以上から理解でき
る。 なおここではg_j+1とg_jとについて述べたが_j+
２，g_j+3……をそれぞれ_j+1，_j+2……から求め
ることができることももちろんである。このこと
の証明は上述と同様であり、繰り返さない。 さてこの実施例の漸近的ランダムネスの考察に
戻ろう。ｌ＝２の場合にはｋ＝L7／２」＝３であ
り、またG^₇及びG^₃から が導き出される。この場合も横棒で示す行ベクト
ルをそれぞれ直ぐ上の行ベクトルから決定して を得る。各行ベクトルは線形独立なので３次均等
分布が確立することがわかる。 ｌ＝１の場合にはｋ＝L7／１」＝７であり、ま
たG^₇，G^₃及びG^₂から が導き出される。この場合も横棒で示す行ベクト
ルをそれぞれ直ぐ上の行ベクトルから順次決定し
て を得る。各行ベクトルは線形独立なので７次均等
分布が確立することがわかる。 以上からこの実施例の乱数が７ビツト漸近的な
乱数であることがわかる。 なお、第４図はこの実施例の乱数の上位３ビツ
トを使つた場合の２次均等分布の状態を示してい
る。これに対し、第３図は下位の４ビツトも含め
た全ビツトを使用した場合の２次元分布の状態を
示している。第３図から下位４ビツトによつて２
次元分布の規則性を解消していることがわかる。
このような規則性の解消は下位４ビツトに対応す
る、行列Ｇの第４〜７の行ベクトルからなる行列
のランクを高することにより達成される。 つぎに実施例の行列Ｇの決定のしかたについて
述べる。７ビツト漸近的な乱数を発生させるため
にはｌ＝１から７まで順にｋ次均等分布を確立す
るように行ベクトルを決定していけばよい。 ｌ＝１ まず行列G^₁任意の１つの行ベクトルを設定す
る。上述から理解されるように他の行ベクトルは
一意的に決定される。つぎにこのようにして得た
行列G₁の各行ベクトルが線形独立になつている
かどうかを調べる。線形独立になつていれば、こ
の行列G^₁を正規なものとして選ぶ。線形独立に
なつていなければ最初に設定する行ベクトルを他
のものにして同様の操作を行う。 例ば行列G^₁の第１行ベクトル（1000000）とす
ると行列G₁はつぎのようになる。 この行列G^₁の各行ベクトルは線形独立である
のでこれを正規のものとして選ぶことができる。
この選択によりｌ＝１のときの７次均等分布が保
証される。 ｌ＝２ 行列G^₂の第１、第２及び第３行の行ベクトル
は行列G^₁の第１、第２及び第３行ベクトルと同
一であり、 である。横棒で示す未決定の行ベクトルはｌ＝１
の場合と同様に求める。即ち、得られる行列G^₂
の各行ベクトルが線形独立になるように、未決定
の行ベクトルのうち任意の１つを設定する。 例えば第４行の行ベクトルを（0111001）とす
ると行列G^₂としてつぎのものが得られる。 この行列G^₂の各行ベクトルは線形独立である
のでこれを正規のものとして選ぶことができる。
この選択によりｌ＝２のときの３次均等分布が保
証される。 ｌ＝３ 行列G^₃の第１、第２、第３及び第４の行ベク
トルは行列G^₂の第１、第２、第４及び第５の行
ベクトルと同一であり、 である。この場合も上述と同様に第５行及び第６
行の行ベクトルを適切に選定して２次均等分布を
満たす行列G^₃を得る。 例えば行列G₃はつぎのようなものである。 ｌ＝４，５，６及び７ ｌ＝４，５，６及びの場合にも同様にして行列
G^₄、G^₅、G^₆及びG^₇のうち未決定の行ベクトルを
決定していく。以下はそのようにして得た行列
G₄、G₅、G₆及びG₇の一例である。ただしアンダ
ーラインは新たく設定した行ベクトルを示す。 このような行列G^₄，G^₅，G^₆及びG^₇は一次均等
分布を保証する。 行列G^₇が行列積回路４の行列Ｇとして用いら
れることは既に述べた。行列積回路４の出力の上
位１ビツトを用いると７次均等分布の乱数が得ら
れ、上位２ビツト、３ビツトをそれぞれ用いて３
次、４次均等分布の乱数が得られることについて
は説明を要しないであろう。 なお、この発明は上述実施例の構成の細部に拘
束されないことはもちろんである。 例えば上述では７ビツト漸近的な乱数を発生す
るようにしたけれどもビツト数は適切に選定する
ことができる。例えば３ビツト漸近的な乱数をつ
ぎの行列を実現する行列積回路により生成するよ
うにしてもよい。なお特性方程式はｆ(D)＝D³¹＋
D²⁸＋１である。

【表】 ［発明の効果］ 以上説明したようにこの発明によればシフトレ
ジスタ回路の出力を行列積回路に供給してシヤツ
フリングするようにしている。従つて乱数の発生
の所要時間を短かくすることができる。また、行
列積回路の行列から乱数の性質を知ることがで
き、あらためてその性質を吟味する必要がない。 また行列積回路の行列を適切に選ぶことにより
ｓビツト漸近的な乱数を簡易に生成することがで
きる。

【図面の簡単な説明】

第１図はこの発明の一実施例を示すブロツク
図、第２図は第１図の行列積回路４の構成例を示
す回路図、第３図及び第４図は第１図実施例を説
明するための図、第５図及び第６図はそれぞれ
Tauswortheの方法及びLewis Payneの方法を説
明する図である。

Claims (1)

1. 【特許請求の範囲】 １ フイードバツクシフトレジスタを含んでなる
   Ｍ系列発生器と、 上記フイードバツクシフトレジスタから得られ
   るパラレルなビツトデータＡを受け取り Ａ Ｇ（ただしＡはベクトル、Ｇは行列である
   の行列積を実行する手段とを有し、 さらに上記行列Ｇをｋ次均等分布が生成される
   ように選定した乱数発生装置。 ２ 漸次的乱数が生成されるように上記行列Ｇを
   選定した特許請求の範囲第３項記載の乱数発生装
   置。