(57)【要約】【課題】  正規乱数を生成する場合に少ないハードウェア規模で良好な正規分布特性を有する乱数を生成する乱数発生装置を提供することを課題とする。【解決手段】  所定の周期を有するＭ系列巡回符号を生成するＭ系列巡回符号生成手段（１０１）と、Ｍ系列巡回符号を基にそれぞれが一様分布特性を有する複数の一様乱数を生成する一様乱数生成手段（１０２）と、複数の一様乱数を用いて正規分布特性を有する正規乱数を生成する正規乱数生成手段（１０３）とを有する乱数生成装置が提供される。【選択図】        図１
2006293429.tif 000002
【特許請求の範囲】
【請求項１】
所定の周期を有するＭ系列巡回符号を生成するＭ系列巡回符号生成手段と、
前記Ｍ系列巡回符号を基にそれぞれが一様分布特性を有する複数の一様乱数を生成する一様乱数生成手段と、
前記複数の一様乱数を用いて正規分布特性を有する正規乱数を生成する正規乱数生成手段と
を有することを特徴とする乱数生成装置。
【請求項２】
前記一様乱数生成手段は、それぞれが異なる識別ビットを基に前記Ｍ系列巡回符号をビット操作する複数のビット操作手段を有することを特徴とする請求項１記載の乱数生成装置。
【請求項３】
前記ビット操作手段は、前記Ｍ系列巡回符号からビットを抽出するビット抽出手段と、前記抽出したビット及び前記識別ビットの排他的論理和を求める論理演算手段と、前記抽出したビット又は前記排他的論理和のビットを反転させるビット反転手段とを有することを特徴とする請求項２記載の乱数生成装置。
【請求項４】
上記ビット操作手段は、ハッシュ演算を行うことを特徴とする請求項２記載の乱数生成装置。
【請求項５】
前記一様乱数生成手段は複数サイクルで複数組みの一様乱数を生成し、前記正規乱数生成手段は前記複数組みの一様乱数を用いて正規乱数を生成することを特徴とする請求項１〜４のいずれか１項に記載の乱数生成装置。
【請求項６】
Ｍ系列巡回符号を生成してそのＭ系列巡回符号を基に一様分布特性を有する複数の一様乱数を生成する一様乱数生成手段と、
前記複数の一様乱数を加算して正規分布特性を有する正規乱数を生成する正規乱数生成手段と
を有することを特徴とする乱数生成装置。
【請求項７】
前記一様乱数生成手段は、共通の初期値を基に所定の周期の異なる原始多項式のＭ系列巡回符号を生成する複数のＭ系列巡回符号発生手段を有することを特徴とする請求項６記載の乱数生成装置。
【請求項８】
前記一様乱数生成手段は、前記Ｍ系列巡回符号の所定のビットを抽出することにより複数の一様乱数を生成することを特徴とする請求項６又は７記載の乱数生成装置。
【請求項９】
さらに、前記正規乱数をスケーリングするスケーリング手段を有することを特徴とする請求項６〜８のいずれか１項に記載の乱数生成装置。
【請求項１０】
前記一様乱数生成手段は、異なる周期を有するＭ系列巡回符号を生成してそのＭ系列巡回符号を基に複数の一様乱数を生成することを特徴とする請求項６〜９のいずれか１項に記載の乱数生成装置。
【請求項１１】
所定の周期を有するＭ系列巡回符号を生成するＭ系列巡回符号生成ステップと、
前記Ｍ系列巡回符号を基にそれぞれが一様分布特性を有する複数の一様乱数を生成する一様乱数生成ステップと、
前記複数の一様乱数を用いて正規分布特性を有する正規乱数を生成する正規乱数生成ステップと
を有することを特徴とする乱数生成方法。
【請求項１２】
Ｍ系列巡回符号を生成してそのＭ系列巡回符号を基に一様分布特性を有する複数の一様乱数を生成する一様乱数生成ステップと、
前記複数の一様乱数を加算して正規分布特性を有する正規乱数を生成する正規乱数生成ステップと
を有することを特徴とする乱数生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数生成技術に関し、特に正規分布特性を有する乱数の生成技術に関する。
【背景技術】
【０００２】
カラー複写機やカラープリンタにおいては、カラーイメージスキャナ等の原稿画像の読取装置やコンピュータから入力された画像信号に対して、Log変換、CMYKへの色空間変換や、プリンタエンジンの特性に合わせた、ガンマ変換が行われた後、誤差拡散処理などの擬似中間処理が行われる。通常、擬似中間処理においては、量子化歪みによるマッハバンドを目立ちにくくするために、意図的に乱数を画像信号に加算する乱数加算処理が行われている。
【０００３】
上記擬似中間処理はハードウェアで構成され、1サイクル当り1画素の処理が行われる場合、上記乱数加算処理に用いられる正規乱数の生成も1サイクルに1回行う必要がある。
【０００４】
上記正規乱数を生成する手法として、主にボックスミューラ法、極座標法、中心極限定理が利用されている。また、一様乱数を生成する手法は、主に線形合同法、M系列巡回符号を利用した手法などがある（下記の非特許文献１参照）。
【０００５】
正規乱数生成装置の回路規模を増大させないために、一様乱数を生成する手法を用いて生成された長ビットの一様乱数から複数の短ビットの乱数を抽出し、上記複数の短ビットの乱数を用いて正規乱数を生成する方法がある。例えば、M系列巡回符号から長ビットの一様乱数を生成し、上記長ビットの一様乱数から複数の短ビットの乱数を抽出し、上記複数の短ビットの乱数を用いて正規乱数を生成する方法がある。
【０００６】
しかし上記の方法では、上記長ビットの一様乱数から抽出した上記複数の短ビットの乱数の相互相関が強くなってしまうため、上記複数の短ビットの乱数を用いて生成された正規乱数の自己相関が強くなってしまう問題がある。
【０００７】
以上の問題を解決するためには、例えば、図８で示すように、それぞれシードレジスタ1000〜1011のシードが異なる複数のM系列巡回符号生成器1012〜1023が生成した複数の一様乱数をビット操作部1026〜1037でビット操作し、上記複数の一様乱数を用いて正規乱数生成部1025で正規乱数を生成する手法がある。また、下記の特許文献１に示されるように、一様乱数を生成するためのM系列巡回符号生成器とは別のM系列巡回符号生成器（以下、EXOR生成器と呼ぶ）を用意し、上記M系列巡回符号生成器から生成された乱数とEXOR生成器から生成された乱数をそれぞれのビットごとの排他的論理和を計算し、正規乱数を生成する手法がある。
【０００８】
【非特許文献１】三上直樹、「アルゴリズム教科書-実用的なプログラミングで示すアルゴリズムの基礎と応用」CQ出版  1996/5  初版
【特許文献１】特開平11-85474号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、以上のような自己相関が弱い正規乱数を生成する正規乱数生成装置は複数のM系列巡回符号器、又はEXOR生成器、及び上記M系列巡回符号生成器又は上記EXOR生成器に設定するシードを格納するレジスタを必要とするため、その分回路規模が増大してしまう。また、上記M系列巡回符号生成器又は上記EXOR生成器の数が増えることで、上記M系列巡回符号生成器、又は上記EXOR生成器に対するシード設定が困難になってしまう。
【００１０】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、正規乱数を生成する場合に少ないハードウェア規模で良好な正規分布特性を有する乱数を生成する乱数発生装置及び乱数生成方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の乱数生成装置は、所定の周期を有するＭ系列巡回符号を生成するＭ系列巡回符号生成手段と、前記Ｍ系列巡回符号を基にそれぞれが一様分布特性を有する複数の一様乱数を生成する一様乱数生成手段と、前記複数の一様乱数を用いて正規分布特性を有する正規乱数を生成する正規乱数生成手段とを有することを特徴とする。
【００１２】
また、本発明の乱数生成装置は、Ｍ系列巡回符号を生成してそのＭ系列巡回符号を基に一様分布特性を有する複数の一様乱数を生成する一様乱数生成手段と、前記複数の一様乱数を加算して正規分布特性を有する正規乱数を生成する正規乱数生成手段とを有することを特徴とする。
【００１３】
また、本発明の乱数生成方法は、所定の周期を有するＭ系列巡回符号を生成するＭ系列巡回符号生成ステップと、前記Ｍ系列巡回符号を基にそれぞれが一様分布特性を有する複数の一様乱数を生成する一様乱数生成ステップと、前記複数の一様乱数を用いて正規分布特性を有する正規乱数を生成する正規乱数生成ステップとを有することを特徴とする。
【００１４】
また、本発明の乱数生成方法は、Ｍ系列巡回符号を生成してそのＭ系列巡回符号を基に一様分布特性を有する複数の一様乱数を生成する一様乱数生成ステップと、前記複数の一様乱数を加算して正規分布特性を有する正規乱数を生成する正規乱数生成ステップとを有することを特徴とする。
【発明の効果】
【００１５】
正規乱数を生成する場合に少ないハードウェア規模で良好な正規分布特性を有する乱数を生成することができる。
【発明を実施するための最良の形態】
【００１６】
（第１の実施形態）
図１は、本発明の第１の実施形態による正規乱数生成装置の一様乱数生成法の概略を示す。100はシードレジスタ、101はM系列巡回符号生成器、102は一様乱数生成部、103は正規乱数生成部、104〜115はビット操作部、116〜127は識別ビットである。以上の構成において、本発明の第１の実施形態を図１を用いて説明する。第１の実施形態は、毎サイクル正規乱数を生成する正規乱数生成装置である。
【００１７】
シードレジスタ100について説明する。シードレジスタ100は、後述するM系列巡回符号生成器101に設定するためのシードを格納するレジスタである。
【００１８】
M系列巡回符号生成器101について説明する。M系列巡回符号生成器101は、所定の段数のシフトレジスタを構成し、シフトレジスタの所定の出力を排他的論理和による論理演算にてフィードバックすることにより、擬似乱数を生成している。また、上記M系列巡回符号生成器101がN段のシフトレジスタで構成されているとすると、上記M系列巡回符号生成器101が生成する擬似乱数の周期は2N-1である。例えば、28ビットM系列巡回符号生成器を用いた場合、28段のシフトレジスタを構成し、生成する擬似乱数の周期は2*28-1である。M系列巡回符号生成器101は、所定の周期を有するM系列巡回符号を生成する。
【００１９】
次に、一様乱数生成部102について説明する。上記一様乱数生成部102は上記M系列巡回符号生成器101が生成した擬似乱数を入力とするビット操作部104〜115を備え、またハードウェア固定値で、お互い異なる値の識別ビット116〜127を備えている。これにより、上記ビット操作部104〜115への入力はすべて異なる。例えば、図２で示すように、識別ビット116をハードウェア固定値"0000"としてビット操作部104に入力し、識別ビット117をハードウェア固定値"0001"としてビット操作部105に入力し、識別ビット118をハードウェア固定値"0010"としてビット操作部106に入力し、識別ビット119をハードウェア固定値"0011"としてビット操作部107に入力し、識別ビット120をハードウェア固定値"0100"としてビット操作部108に入力し、識別ビット121をハードウェア固定値"0101"としてビット操作部109に入力し、識別ビット122をハードウェア固定値"0110"としてビット操作部110に入力し、識別ビット123をハードウェア固定値"0111"としてビット操作部111に入力し、識別ビット124をハードウェア固定値"1000"としてビット操作部112に入力し、識別ビット125をハードウェア固定値"1001"としてビット操作部113に入力し、識別ビット126をハードウェア固定値"1010"としてビット操作部114に入力し、識別ビット127をハードウェア固定値"1011"としてビット操作部115に入力することで、上記ビット操作部104〜115はそれぞれ異なる32ビット長の値を入力していることになる。
【００２０】
以上の構成より上記一様乱数生成部102は、一様分布特性を有する相互相関の弱い一様乱数uk(0 <= k <= 11)を生成する。上記ビット操作部104〜115の詳細は後述する。
【００２１】
上記正規乱数生成部103について説明する。上記正規乱数生成部103は上記一様乱数生成部102で生成する一様乱数uk(0 <= k <= 11)を入力とする。互いに独立ないくつかの乱数の和は正規分布に近づくという中心極限定理に従って正規分布特性を有する正規乱数vn を出力している。例えば一様乱数生成部102が生成する12ビットの一様乱数uk  (k = 0,1,・・・11)を用いて中心極限定理に従って正規乱数vnを生成する。正規乱数vnは、式（１）で算出される。正規乱数生成部103は、一様乱数ukを用いて正規分布特性を有する正規乱数vnを生成する。
【００２２】
【数１】
2006293429.tif 000003
【００２３】
よってvn=-24570〜24570(16 ビット)となる。
【００２４】
次に、図３を使用して、上記ビット操作部104を説明する。101は図１記載のM系列巡回符号生成器、116は図１記載の識別ビット、300はビット抽出回路、301は排他的論理和演算回路、302はビット反転回路である。
【００２５】
以上の構成において、M系列巡回符号生成器101のビット長を28ビットにし、識別ビット116を4ビットにした場合の、12ビットの一様乱数u0を生成する上記ビット操作部104について説明する。上記識別ビット116のLSBから数えて、4ビット目をN3、3ビット目をN2、2ビット目をN1、1ビット目をN0とする。
【００２６】
ビット抽出回路300について説明する。上記M系列巡回符号生成器101が生成する上記擬似乱数は自己相関が強いので、ビット抽出回路300は、ビット操作部104が生成する一様乱数u0 の自己相関を軽減するように、上記擬似乱数のビットを任意に抽出する。例えば、一様乱数u0 を生成する際、上記M系列巡回符号生成器101が生成する上記擬似乱数からビットS0〜S13を抽出する必要があるとし、生成する一様乱数u0 のLSBから数えて1ビット目を生成するためにはS0、2ビット目を生成するためにはS1、3ビット目を生成するためにはS2、4ビット目を生成するためにはS3、5ビット目を生成するためにはS4、6ビット目を生成するためにはS5、7ビット目を生成するためにはS6、8ビット目を生成するためにはS7、9ビット目を生成するためにはS8、10ビット目を生成するためにはS9、11ビット目を生成するためにはS10、S11、12ビット目を生成するためにはS12、S13、が必要であるとすると、ビット操作部104は式（２）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００２７】
S13 = 12、S12 = 22、S11 = 1、S10 = 7、S9 = 25、S8 = 2、S7 = 18、S6 = 26、S5 = 3、S4 = 14、S3 = 23、S2 = 6、S1 = 21、S0 = 10  ・・・（２）
【００２８】
また、ビット操作部105〜115について図示していないが、S0〜S13を用いてビット操作部105〜115のビット抽出回路を説明すると、ビット操作部105は式（３）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００２９】
S13 = 20、S12 = 5、S11 = 0、S10 = 11、S9 = 15、S8 = 4、S7 = 19、S6 = 27、S5 = 9、S4 = 17、S3 = 16、S2 = 24、S1 = 13、S0 = 8  ・・・（３）
【００３０】
また、ビット操作部106は式（４）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００３１】
S13 = 26、S12 = 14、S11 = 10、S10 = 2、S9 = 21、S8 = 7、S7 = 18、S6 = 20、S5 = 5、S4 = 12、S3 = 22、S2 = 6、S1 = 0、S0 = 25  ・・・（４）
【００３２】
また、ビット操作部107は式（５）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００３３】
S13 = 23、S12 = 4、S11 = 3、S10 = 17、S9 = 13、S8 = 1、S7 = 19、S6 = 27、S5 = 9、S4 = 11、S3 = 16、S2 = 24、S1 = 8、S0 = 15  ・・・（５）
【００３４】
また、ビット操作部108は式（６）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００３５】
S13 = 27、S12 = 16、S11 = 9、S10 = 6、S9 = 21、S8 = 7、S7 = 18、S6 = 20、S5 = 5、S4 = 12、S3 = 22、S2 = 2、S1 = 13、S0 = 8  ・・・（６）
【００３６】
また、ビット操作部109は式（７）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００３７】
S13 = 13、S12 = 0、S11 = 8、S10 = 19、S9 = 17、S8 = 1、S7 = 26、S6 = 23、S5 = 4、S4 = 11、S3 = 14、S2 = 24、S1 = 10、S0 = 15  ・・・（７）
【００３８】
また、ビット操作部110は式（８）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００３９】
S13 = 21、S12 = 15、S11 = 10、S10 = 5、S9 = 19、S8 = 7、S7 = 9、S6 = 20、S5 = 6、S4 = 12、S3 = 26、S2 = 4、S1 = 27、S0 = 13  ・・・（８）
【００４０】
また、ビット操作部111は式（９）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００４１】
S13 = 18、S12 = 3、S11 = 1、S10 = 25、S9 = 16、S8 =0、S7 = 22、S6 = 23、S5 = 2、S4 = 11、S3 = 14、S2 = 24、S1 = 17、S0 = 8  ・・・（９）
【００４２】
また、ビット操作部112は式（１０）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００４３】
S13 = 22、S12 = 24、S11 = 7、S10 = 8、S9 = 19、S8 =1、S7 = 3、S6 = 20、S5 = 6、S4 = 12、S3 = 18、S2 = 10、S1 = 27、S0 = 13  ・・・（１０）
【００４４】
また、ビット操作部113は式（１１）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００４５】
S13 = 11、S12 = 9、S11 = 2、S10 = 16、S9 = 23、S8 =0、S7 = 26、S6 = 5、S5 = 4、S4 = 21、S3 = 14、S2 = 15、S1 = 17、S0 = 25  ・・・（１１）
【００４６】
また、ビット操作部114は式（１２）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００４７】
S13 = 25、S12 = 19、S11 = 10、S10 = 6、S9 = 22、S8 =7、S7 = 24、S6 = 20、S5 = 8、S4 = 12、S3 = 18、S2 = 2、S1 = 27、S0 = 3  ・・・（１２）
【００４８】
また、ビット操作部115は式（１３）のように構成される。右辺の値は上記M系列巡回符号101のビット番号である。
【００４９】
S13 = 13、S12 = 4、S11 = 1、S10 = 23、S9 = 15、S8 = 0、S7 = 26、S6 = 16、S5 = 9、S4 = 21、S3 = 14、S2 = 5、S1 = 17、S0 = 11  ・・・（１３）
【００５０】
次に、排他的論理和演算回路301について説明する。排他的論理和演算回路301は上記ビット抽出回路300で上記M系列巡回符号器101が出力した擬似乱数から抽出したビットS6〜S13と上記識別ビット116の排他的論理和の論理演算を行う。上記排他的論理和演算回路301の構成は、例えば出力が12ビットの乱数列で、上記乱数列をLSBから数えて1ビット目をP0、2ビット目をP1、3ビット目をP2、4ビット目をP3、5ビット目をP4、6ビット目をP5、7ビット目をP6、8ビット目をP7、9ビット目をP8、10ビット目をP9、11ビット目をP10、12ビット目をP11とし、また上記ビット抽出回路300が出力したビットS0〜S13、及び上記識別ビットの各ビットN0〜N3を用いて表すと式（１４）で表される。A EXOR BはAとBの排他的論理和の論理演算を意味する。
【００５１】
P11 = S13 EXOR S12、P10 = S11 EXOR S10、P9 = S9 EXOR N3、P8 = S8 EXOR N2 、P7 = S7 EXOR N1、 P6 = S6 EXOR N0、 P5 = S5、P4 = S4、P3 = S3、P2 = S2、P1 = S1、P0 = S0  ・・・（１４）
【００５２】
また、ビット操作部105〜115の排他的論理和演算回路及び識別ビット117〜127について図示してはいないが、ビット操作部105〜115の排他的論理和演算回路の構成は、ビット操作部104の排他的論理和演算回路301の構成の説明で使用したN0〜N3及びP0〜P11及びS0〜13を用いて表すと式（１４）で表される。A EXOR BはAとBの排他的論理和の論理演算を意味する。ただし、それぞれのビット操作部104〜115の記号が同じであっても上記記号に対するビットの値が同じとは限らない。例えば、ビット操作部104の出力ビットP11とビット操作部105の出力ビットP11の値が同じであるとは限らない。
【００５３】
以上のように、排他的論理和の論理演算を行うことで、極端な値を持つ一様乱数u0が連続して生成されることを回避できる。
【００５４】
次に、ビット反転回路302について説明する。ビット反転回路302は上記排他的論理和演算回路301の出力のビットP0〜P11のうちの任意のビットを反転させ、正規乱数を生成している。例えば、P9、P7、P4、P3、P0をビット反転させ、P11を12ビット目、P10を11ビット目、P9を10ビット目、P8を9ビット目、P7を8ビット目、P6を7ビット目、P5を6ビット目、P4を5ビット目、P3を2ビット目、P2を3ビット目、P1を2ビット目、P0を1ビット目とする12ビット長の一様乱数を生成する。
【００５５】
図示してはいないが、ビット操作部105〜115の反転回路について上記P0〜P11を用いて説明すると、上記ビット反転回路302の構成と同じである。ただし、反転するビットはP9、P7、P4、P3、P0に限定するものではない。
【００５６】
ビット操作部105〜115は、それぞれが異なる識別ビット116を基にM系列巡回符号をビット操作する。具体的には、ビット操作部105〜115は、M系列巡回符号からビットを抽出するビット抽出回路300と、上記抽出したビット及び識別ビット116の排他的論理和を求める排他的論理和演算回路301と、上記抽出したビット又は上記排他的論理和のビットを反転させるビット反転回路302とを有する。
【００５７】
第１の実施形態では、一様乱数生成部102はビット操作部104〜115を備えることで、例えば相互相関が弱い一様乱数uk(0 <= k <= 11)を生成していたが、一様乱数生成部102が出力した一様乱数uk(0 <= k <= 11)の相互相関が弱ければ、例えば上記ビット生成部104から一様乱数u0、u1を生成するように、上記ビット生成部104〜115が複数の一様乱数uk(0 <= k <= 11)を生成しても特に問題はない。また、一様乱数生成部102が生成した一様乱数uk(0 <= k <= 11)の相互相関が弱ければ、各上記ビット操作部104〜115の構成が同じであるか否かは特に問題ない。例えば、ビット操作部104〜115がハッシュ演算を行うものである場合、ビット操作部104〜115の入力が異なるものであれば、出力する一様乱数uk (0 <= k <= 11)の相互相関が弱いので、上記ビット操作部104〜115の構成がすべて同じであっても特に問題ない。
【００５８】
また、一様乱数生成部102はビット操作部104〜115に対してそれぞれ異なる値の記識別ビット116〜127が必要となるため、上記識別ビット116〜127のビット長は4ビットであったが、記識別ビットのビット長は各ビット操作部に対して識別ビットが異なる値を表現できるのであれば特に問題はないことはいうまでもない。また、識別ビット116〜127はハードウェア固定値として説明したが、レジスタ等の記憶媒体であっても特に問題ではない。
【００５９】
また、ビット操作部104〜115の反転回路の構成はすべて同じであるが、特に同じである必要はない。
【００６０】
（第２の実施形態）
図４は、本発明の第２の実施形態による正規乱数生成装置の一様乱数生成法の概略を示す。100は図１記載のシードレジスタ、101は図１記載のM系列巡回符号生成器、104〜109は図１記載のビット操作部、500は一様乱数生成部、501〜506は識別ビット、507は正規乱数生成部、508はカウンタである。以上の構成において、本発明の第２の実施形態を、図４を用いて説明する。
【００６１】
シードレジスタ100、M系列巡回符号生成器101、ビット操作部104〜109は、第１の実施形態と同じ構成なので説明を割愛する。数サイクルに1回正規乱数vnを生成する正規乱数生成装置、例えば、正規乱数vnを生成するために一様乱数uk(0 <= k <= 11)が必要で、2サイクルに1回正規乱数vnを生成する正規乱数生成装置は後述する一様乱数生成部500により回路規模を縮小することができる。
【００６２】
一様乱数生成部500について説明する。一様乱数生成部500はビット操作部104〜109と後述する識別ビット501〜506を備え、最初のサイクルで一様乱数uk(0 <= k <= 5)を生成し、次のサイクルで一様乱数uk(6 <= k <= 11)を生成する。
【００６３】
次に、識別ビット501〜506について説明する。各上記識別ビット501〜506は3ビットのビット長であり、第１の実施形態と同じ構成である。
【００６４】
次に、正規乱数生成部507について説明する。正規乱数生成部507は上記一様乱数生成部が生成した一様乱数uk(0 <= k <= 11)を入力とし、上記一様乱数uk(0 <= k <= 11)を保持する。カウンタ508は1ビットのカウンタであり、正規乱数生成部507はカウンタ508が"1"の時、つまり2サイクルに1回正規乱数vnを生成する。
【００６５】
第２の実施形態は正規乱数vnを生成するために一様乱数uk(0 <= k <= 11)が必要で、2サイクルに1回正規乱数vnを生成する場合について説明したが、正規乱数生成部で一様乱数生成部から出力する一様乱数を保持して、正規乱数生成部から正規乱数を生成するタイミングをカウンタで制御していれば、上記構成に限定するものではない。例えば、正規乱数vnを生成するために一様乱数uk(0 <= k <= 11)が必要で、6サイクルに一度だけ正規乱数vnを生成する正規乱数生成装置は、一様乱数生成部がビット操作部を2つ、異なる値を持つ1ビットの識別ビットを2つ備え、また0から５を表すカウンタを備えることで実現できる。
【００６６】
本実施形態では、上記シードレジスタ100及び上記M系列巡回符号生成器101のビット長を28ビットにし、上記一様乱数生成部102では12ビットの一様乱数を12個生成したが、特に上記ビット長や個数に限定することはないことは言うまでもない。
【００６７】
以上のように、第１及び第２の実施形態の正規乱数生成装置によれば、シードレジスタ及びM系列巡回符号生成器101が一組だけの構成であるため、M系列巡回符号に与えるシード設定を容易にし、回路のハードウェアの量を増大させることなく、また極端な値が連続して生成され自己相関が強くなってしまうことを回避した、正規乱数生成装置を提供することができる。また、毎サイクル出力を必要としない場合、カウンタを用いることによって、本実施形態の生成装置の回路規模を縮小することができる。
【００６８】
これにより画像処理において、正規乱数の自己相関による画質劣化を防ぐことができ、良質な画質を得ることができる。図５は本実施形態による正規乱数生成装置が生成した正規乱数の近傍の自己相関を示した図である。また、図６は本実施形態による正規乱数生成装置が生成した正規乱数の28ビットM系列の周期周辺の自己相関を示したグラフである。そして図７は本実施形態による正規乱数生成装置が生成した正規乱数の度数分布表である。標準偏差は127/3である。図５〜図７より相関が弱く、正規分布特性を持った正規乱数を発生することができる正規乱数生成装置であることを証明することができる。
【００６９】
（第３の実施形態）
カラー複写機やカラープリンタにおいては、カラーイメージスキャナ等の原稿画像の読取装置やコンピュータから入力された画像信号に対して、Log変換、CMYKへの色空間変換や、プリンタエンジンの特性に合わせた、ガンマ変換が行われた後、誤差拡散処理などの擬似中間処理が行われる。通常、擬似中間処理においては、量子化雑音によるモアレを目立ちにくくするために、故意に一様乱数値や正規乱数値を小雑音として加算する乱数加算処理が行われている。
【００７０】
上記擬似中間処理はハードウェアで構成され、1システムクロック当り1画素の処理が行われる場合、上記乱数加算処理は2画素に一回の処理を行うので正規乱数の生成は2システムクロックに1回行う必要がある。通常ハードウェアを用いて簡略的に正規乱数を生成する方法としては、所望の画素数内で正規乱数の相関が出ないようなビット長で、かつ１システムクロック当り１個の一様乱数を抽出することが可能な複数のM系列巡回符号発生器を用意し、中心極限定理に従って抽出した複数の一様乱数を加算することにより、正規乱数値の生成を行っている。ここで、一様乱数を複数のM系列巡回符号発生器から抽出している理由は、一様乱数間の相関を無くすためである。この時、各M系列巡回符号発生器は同一の原始多項式を基にした構成をとり、夫々のM系列巡回符号発生器に対して異なるシード値を与えることにより、抽出した一様乱数間の相関を無くしている。
【００７１】
例えば、A3 1200DPIの画素数について、相関が出ないように正規乱数を発生する為には、１画素おきに正規乱数を発生したとしても28ビット長のM系列巡回符号発生器が必要である。そして中心極限定理の一様乱数の加算個数を12個とし、28ビット長M系列巡回符号発生器をから12ビットの一様乱数値を２つ抽出する場合、28ビット長M系列巡回符号発生器が6個必要となる。
【００７２】
しかし、上記すべての巡回符号に同じ原始多項式を用意し、すべて同じシード値を与えると、1クロックでM系列のデータが1bitしかシフトさせないことから、こうして生成した一様乱数から生成した正規乱数の自己相関は強く出てしまう欠点がある。上記欠点を解消するために異なるシード値を各々のM系列巡回符号に与えることが考えられるが、複数のM系列巡回符号発生器に対して異なるシード値をCPU等から設定する必要があり、それらの設定値を格納するためのレジスタが巡回符号発生器のビット長と同等な分だけ必要となり、ハードウェア規模の増加を招いていた。
【００７３】
例えば上記28ビット長M系列巡回符号発生器を6個用いる構成とした場合、シード値設定用のレジスタとしては28x6=168ビット長のレジスタが必要となる。
【００７４】
図９は、本発明の第３の実施形態による乱数発生装置の概略を示す。11はCPU等からの設定を格納するレジスタ部、12は他のブロックの動作シーケンス制御を行う制御部、13は一様乱数を生成する一様乱数生成部、14は上記一様乱数生成部13で生成された一様乱数を入力とし、正規乱数を生成する正規乱数生成部、15は上記正規乱数生成部14が生成した正規乱数をスケーリングするスケーリング部である。上記構成において、本発明の第３の実施形態を図９を用いて説明する。
【００７５】
レジスタ部11はCPU等からの設定値を格納し、他のブロックに供給する。制御部12は他のブロックの動作シーケンス制御を行う。一様乱数生成部13は28ビット長M系列巡回符号発生器6個を備え、12ビットの一様乱数を12個抽出して出力する。ここで、一様乱数のビット長は、後述するスケーリング部15での出力値のビット長は10ビット以上の値が必要であるため、後述するスケーリング部15での演算誤差等を考えて12ビットとしている。正規乱数生成部14は中心極限定理に従って、一様乱数生成部13からの12個の一様乱数を加算して正規乱数を出力する。
【００７６】
この手法はXi(i=0,1,・・・11)を区間(0,1)上の一様乱数とすると、これらの乱数の和(X0+X2+・・・+X11)が平均値0、分散が１の正規分布によく近似することを利用する。ここで、出力される一様乱数をuk(k=1〜12)とすると正規乱数xは式（１５）で算出される。
【００７７】
【数２】
2006293429.tif 000004
【００７８】
よってx=-24570〜24570(16ビット)となる。
【００７９】
スケーリング部15は上記正規乱数生成部14から出力された16ビットの正規乱数に対して、スケーリングを行い、10ビットの乱数加算値を生成する。図１０にスケーリングの一例を示す。３σの値を255にスケーリングすることにより、正規乱数の最大値の6σが510にスケーリングされる。よって符号ビットも含めて10ビットの乱数加算値が生成される。
【００８０】
スケーリング部15の出力値の上記乱数加算値は図示していない前段のガンマ変換処理の10ビットの出力濃度値Din(0〜1023の整数値)との加算を行う。以下、図示していない後段のクリッピング処理、誤差拡散処理に出力される。
【００８１】
次に図１１を用いて一様乱数発生部13の詳細を説明する。31は28bitの共通のシード値（初期値）を格納するシードレジスタ、32はM系列巡回符号を発生させる28ビット長のM系列巡回符号発生器、33は32と原始多項式の異なる28ビット長のM系列巡回符号発生器、34は32、33と原始多項式の異なる28ビット長のM系列巡回符号発生器、35は32、33、34と原始多項式の異なる28ビット長のM系列巡回符号発生器、36は32、33、34、35と原始多項式の異なる28ビット長のM系列巡回符号発生器、37は32、33、34、35、36と原始多項式の異なる28ビット長のM系列巡回符号発生器である。
【００８２】
本実施形態において、M系列巡回符号発生部13は、28bit長のM系列巡回符号発生器を6個備える。上記28bit長のM系列巡回符号発生器は各々異なった原始多項式を持つ。例えば、6個の上記28bit長M系列巡回符号発生器各々をMa,Mb・・・Mfとすると、Ma,Mb・・・Mf は式（１６）に表される原始多項式を備える。上記原始多項式の組み合わせはなるべく次数が重ならないようにすることで、一様乱数間の相関を抑えることができる。
【００８３】
Ma:  h(X)=X28+X3
Mb:  h(X)=X28+X6+X4+X1
Mc:  h(X)=X28+X7+X6+X5
Md:  h(X)=X28+X9+X8+X5
Me:  h(X)=X28+X10+X3+X1
Mf:  h(X)=X28+X11+X7+X3      ・・・（１６）
【００８４】
ここで、Ma,Mb,Mc,Md,Me,Mfは28bit長M系列巡回符号発生器、h(X)は原始多項式である。また、シード値を格納するシードレジスタ31はレジスタ部11内から抜粋して明示している。
【００８５】
M系列巡回符号発生器32は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器32は、12ビットの一様乱数u0 [11:0]及びu1 [11:0]を出力する。ここで、一様乱数u0 [11:0]及びu1 [11:0]は28ビット長M系列巡回符号発生器32から以下のようにビットを抽出することにより出力される。
【００８６】
u0 [11:0]=[22,7,11,2,18,1,3,13,23,9,21,10]  ・・・（１７）
u1 [11:0]=[5,20,8,16,19,0,12,17,4,6,13,15]  ・・・（１８）
【００８７】
式（１７）の右辺の数字は、28ビット長M系列巡回符号発生器32のビット番号であり、所望のビットを抽出することにより一様乱数を生成している。またビットの抽出は、乱数としての特性を良くするために連続したビット位置にならないよう不連続なビット位置から抽出する。式（１８）で表されるu1 [11:0]についても同様である。ここで、u0 [11:0]とu1 [11:0]はお互いの相関を無くすために28ビット長M系列巡回符号発生器から抽出するビット位置が重ならないようにしている。
【００８８】
M系列巡回符号発生器33は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器33は、12ビットの一様乱数u2 [11:0]及びu3 [11:0]を出力する。ここで、一様乱数u2 [11:0]及びu3 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で28ビット長M系列巡回符号発生器33から以下の様にビットを抽出することにより出力される。
【００８９】
u2 [11:0]= [7,11,2,18,1,3,13,23,9,21,10,22]  ・・・（１９）
u3 [11:0]= [20,8,16,19,0,12,17,4,6,13,15,5]  ・・・（２０）
【００９０】
式（１９）及び式（２０）の表記は、式（１７）等と同様である。但し、28ビット長M系列巡回符号発生器33から抽出するビット位置に関して、u2 [11:0]はu0 [11:0]に対してMSB側に1ビットシフトし、u0 [11:0]でMSBだったビット番号'22'をLSBに割り当てている。同様にu3 [11:0]はu1 [11:0]に対してMSB側に1ビットシフトし、u1 [11:0]でMSBだったビット番号'5'をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【００９１】
M系列巡回符号発生器34は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器34は、12ビットの一様乱数u4 [11:0]及びu5 [11:0]を出力する。ここで、一様乱数u4[11:0]及びu5[11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で28ビット長M系列巡回符号発生器34から以下の様にビットを抽出することにより出力される。
【００９２】
u4 [11:0]= [11,2,18,1,3,13,23,9,21,10,22,7]  ・・・（２１）
u5 [11:0]= [8,16,19,0,12,17,4,6,13,15,5,20]  ・・・（２２）
【００９３】
式（２１）及び式（２２）の表記は、式（１７）等と同様である。但し、28ビット長M系列巡回符号発生器34から抽出するビット位置に関して、u4 [11:0]はu2 [11:0]に対してMSB側に1ビットシフトし、u2 [11:0]でMSBだったビット番号'7'をLSBに割り当てている。同様にu5 [11:0]はu3 [11:0]に対してMSB側に1ビットシフトし、u3 [11:0]でMSBだったビット番号'20'をLSBに割り当てている。
【００９４】
M系列巡回符号発生器35は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器35は、12ビットの一様乱数u6 [11:0]及びu7 [11:0]を出力する。ここで、一様乱数u6 [11:0]及びu7[11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で28ビット長M系列巡回符号発生器35から以下の様にビットを抽出することにより出力される。
【００９５】
u6 [11:0]= [2,18,1,3,14,23,9,21,10,22,7,11]  ・・・（２３）
u7 [11:0]= [16,19,0,12,17,4,6,13,15,5,20,8]  ・・・（２４）
【００９６】
式（２３）及び式（２４）の表記は、式（１７）等と同様である。但し、28ビット長M系列巡回符号発生器35から抽出するビット位置に関して、u6 [11:0]はu4[11:0]に対してMSB側に1ビットシフトし、u4[11:0]でMSBだったビット番号'11'をLSBに割り当てている。同様にu7 [11:0]はu5 [11:0]に対してMSB側に1ビットシフトし、u5 [11:0]でMSBだったビット番号'8'をLSBに割り当てている。
【００９７】
M系列巡回符号発生器36は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器36は、12ビットの一様乱数u8 [11:0]及びu9 [11:0]を出力する。ここで、一様乱数u8 [11:0]及びu9[11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で28ビット長M系列巡回符号発生器36から以下の様にビットを抽出することにより出力される。
【００９８】
u8 [11:0]= [18,1,3,13,23,9,21,10,22,7,11,2]  ・・・（２５）
u9 [11:0]= [19,0,12,17,4,6,13,15,5,20,8,16]  ・・・（２６）
【００９９】
式（２５）及び式（２６）の表記は、式（１７）等と同様である。但し、28ビット長M系列巡回符号発生器36から抽出するビット位置に関して、u8 [11:0]はu6 [11:0]に対してMSB側に1ビットシフトし、u6 [11:0]でMSBだったビット番号'2'をLSBに割り当てている。同様にu9 [11:0]はu7 [11:0]に対してMSB側に1ビットシフトし、u7 [11:0]でMSBだったビット番号'16'をLSBに割り当てている。
【０１００】
M系列巡回符号発生器37は28ビット長のM系列巡回符号発生器であり、シードレジスタ31に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号発生器37は、12ビットの一様乱数u10 [11:0]及びu11 [11:0]を出力する。ここで、一様乱数u10 [11:0]及びu11[11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で28ビット長M系列巡回符号発生器37から以下の様にビットを抽出することにより出力される。
【０１０１】
u10 [11:0]= [1,3,14,23,9,21,10,22,7,11,2,18]  ・・・（２７）
u11 [11:0]= [0,12,17,4,6,13,15,5,20,8,16,19]  ・・・（２８）
【０１０２】
式（２７）及び式（２８）の表記は、式（１７）等と同様である。但し、28ビット長M系列巡回符号発生器37から抽出するビット位置に関して、u10 [11:0]はu8 [11:0]に対してMSB側に1ビットシフトし、u8 [11:0]でMSBだったビット番号'18'をLSBに割り当てている。同様にu11 [11:0]はu9 [11:0]に対してMSB側に1ビットシフトし、u9 [11:0]でMSBだったビット番号'19'をLSBに割り当てている。
【０１０３】
本実施形態によれば、上記一様乱数生成手段を用いることで、上記シード値を一つだけ用いたとしても、良質な正規分布特性を持つ乱数を生成することができる。また、シード値を格納するためのレジスタを軽減できるので、ハードウェア規模を縮小させることができる。
【０１０４】
（第４の実施形態）
次に、図１２を用いて、本発明の第４の実施形態での一様乱数発生部13の詳細を説明する。401は17bitのシード値を格納するシードレジスタ、402は11bitのシード値を格納するシードレジスタ、403はM系列巡回符号を発生させる17ビット長のM系列巡回符号発生器、404はM系列巡回符号を発生させる11ビット長のM系列巡回符号発生器、405は403と原始多項式の異なる17ビット長のM系列巡回符号発生器、406は404と原始多項式の異なる11ビット長のM系列巡回符号発生器、407は403,405と原始多項式の異なる17ビット長のM系列巡回符号発生器、408は404,406と原始多項式の異なる11ビット長のM系列巡回符号発生器、409は403,405,407と原始多項式の異なる17ビット長のM系列巡回符号発生器である。410は404,406,408と原始多項式の異なる11ビット長のM系列巡回符号発生器、411は403,405,407,409と原始多項式の異なる17ビット長のM系列巡回符号発生器、412は404,406,408,410と原始多項式の異なる11ビット長のM系列巡回符号発生器、413は403,405,407,409,411と原始多項式の異なる17ビット長のM系列巡回符号発生器、414は404,406,408,410,412と原始多項式の異なる11ビット長のM系列巡回符号発生器である。
【０１０５】
第３の実施形態ではM系列巡回符号発生器31で28ビット長のM系列巡回符号を一つだけ使用していたが、第４の実施形態では上記M系列巡回符号発生器31で、17bit長のM系列巡回符号発生器、11bit長のM系列巡回符号発生器を各々6個備える。上記17bit長のM系列巡回符号発生器及び上記11bit長のM系列巡回符号発生器は各々異なった原始多項式を持つ。例えば、6個の上記17bit長M系列巡回符号発生器各々をM1a,M1b・・・M1fとすると、M1a,M1b・・・M1f は式（２９）に表される原始多項式を備える。また、6個の上記11bit長M系列巡回符号発生器各々をM2a,M2b・・・M2fとすると、M2a,M2b・・・M2f は式（３０）に表される原始多項式を備える。上記17bit長のM系列巡回符号発生器及び上記11bit長のM系列巡回符号発生器は、異なる周期を有するM系列巡回符号を生成する。
【０１０６】
17ビット M系列巡回多項式用原始多項式
M1a:  h(X)=X17+X
M1b:  h(X)=X17+X5+X3+X2
M1c:  h(X)=X17+X6+X4+X2 
M1d:  h(X)=X17+X7+X5+X
M1e:  h(X)=X17+X8+X3+X
M1f:  h(X)=X17+X9+X5+X4  ・・・（２９）
【０１０７】
11ビットM系列巡回多項式用原始多項式
M2a:  h(X)=X11+X2
M2b:  h(X)=X11+X4+X2+X
M2c:  h(X)=X11+X5+X3+X
M2d:  h(X)=X11+X6+X2+X
M2e:  h(X)=X11+X7+X5+X3
M2f:  h(X)=X11+X8+X3+X2  ・・・（３０）
【０１０８】
ここで、M1a,M1b,M1c,M1d,M1e,M1fは17bit長M系列巡回符号発生器、M2a,M2b,M2c,M2d,M2e,M2fは17bit長M系列巡回符号発生器、h(X)は原始多項式である。また、シード値を格納するシードレジスタ401、シードレジスタ402はレジスタ部11内から抜粋して明示している。
【０１０９】
M系列巡回符号発生器403は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器404は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器403及び11ビット長M系列巡回符号発生器404は、12ビットの一様乱数u0 [11:0]及びu1 [11:0]を出力する。ここで、一様乱数u0 [11:0]及びu1 [11:0]は17ビット長M系列巡回符号発生器403及び11ビット長M系列巡回符号発生器404から以下のようにビットを抽出することにより出力される。
【０１１０】
u0 [11:0]=[ 11,7',0,2',7,1',3',3,12,9',10,10']  ・・・（３１）
u1 [11:0]=[ 5',9,8',5,8,0',1,6,4',6',2,4]       ・・・（３２）
【０１１１】
式（３１）の右辺の数字は、「'」がない数字が17ビット長M系列巡回符号発生器403のビット番号であり、「'」がある数字が11ビット長M系列巡回符号発生器404のビット番号であり、所望のビットを抽出することにより一様乱数を生成している。またビットの抽出は、乱数としての特性を良くするために連続したビット位置にならないよう不連続なビット位置から抽出する。式（３２）で表されるu1 [11:0]についても同様である。ここで、u0 [11:0]とu1 [11:0]はお互いの相関を無くすために28ビット長M系列巡回符号発生器から抽出するビット位置が重ならないようにしている。
【０１１２】
M系列巡回符号発生器405は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器406は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器405及び11ビット長M系列巡回符号発生器406は、12ビットの一様乱数u2 [11:0]及びu3 [11:0]を出力する。ここで、一様乱数u2 [11:0]及びu3 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で17ビット長M系列巡回符号発生器405及び11ビット長M系列巡回符号発生器406から以下のようにビットを抽出することにより出力される。
【０１１３】
u2 [11:0]= [7',0,2',7,1',3',3,12,9',10,10',11]  ・・・（３３）
u3 [11:0]= [9,8',5,8,0',1,6,4',6',2,4,5']       ・・・（３４）
【０１１４】
式（３３）及び式（３４）の表記は、式（３１）等と同様である。但し、17ビット長M系列巡回符号発生器405及び11ビット長M系列巡回符号発生器406から抽出するビット位置に関して、u2 [11:0]はu0 [11:0]に対してMSB側に1ビットシフトし、u0 [11:0]でMSBだったビット番号「11」をLSBに割り当てている。同様にu3 [11:0]はu1 [11:0]に対してMSB側に1ビットシフトし、u1 [11:0]でMSBだったビット番号「5'」をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【０１１５】
M系列巡回符号発生器407は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器408は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器407及び11ビット長M系列巡回符号発生器408は、12ビットの一様乱数u4 [11:0]及びu5 [11:0]を出力する。ここで、一様乱数u4 [11:0]及びu5 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で17ビット長M系列巡回符号発生器407及び11ビット長M系列巡回符号発生器408から以下のようにビットを抽出することにより出力される。
【０１１６】
u4[11:0]= [0,2',7,1',3',3,12,9',10,10',11,7']  ・・・（３５）
u5[11:0]= [8',5,8,0',1,6,4',6',2,4,5',9]       ・・・（３６）
【０１１７】
式（３５）及び式（３６）の表記は、式（３１）等と同様である。但し、17ビット長M系列巡回符号発生器407及び11ビット長M系列巡回符号発生器408から抽出するビット位置に関して、u4[11:0]はu2 [11:0]に対してMSB側に1ビットシフトし、u2 [11:0]でMSBだったビット番号「7'」をLSBに割り当てている。同様にu5 [11:0]はu3 [11:0]に対してMSB側に1ビットシフトし、u3 [11:0]でMSBだったビット番号「9」をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【０１１８】
M系列巡回符号発生器409は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器410は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器409及び11ビット長M系列巡回符号発生器410は、12ビットの一様乱数u6 [11:0]及びu7 [11:0]を出力する。ここで、一様乱数u6 [11:0]及びu7 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で17ビット長M系列巡回符号発生器409及び11ビット長M系列巡回符号発生器410から以下のようにビットを抽出することにより出力される。
【０１１９】
u6 [11:0]= [7,1',3',3,12,9',10,10',11,7',0,2']  ・・・（３７）
u7 [11:0]= [5,8,0',1,6,4',6',2,4,5',9,8']       ・・・（３８）
【０１２０】
式（３７）及び式（３８）の表記は、式（３１）等と同様である。但し、17ビット長M系列巡回符号発生器409及び11ビット長M系列巡回符号発生器410から抽出するビット位置に関して、u6 [11:0]はu4 [11:0]に対してMSB側に1ビットシフトし、u4 [11:0]でMSBだったビット番号「2'」をLSBに割り当てている。同様にu7 [11:0]はu5 [11:0]に対してMSB側に1ビットシフトし、u5 [11:0]でMSBだったビット番号「8'」をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【０１２１】
M系列巡回符号発生器411は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器412は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器411及び11ビット長M系列巡回符号発生器412は、12ビットの一様乱数u8 [11:0]及びu9 [11:0]を出力する。ここで、一様乱数u8 [11:0]及びu9 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で17ビット長M系列巡回符号発生器411及び11ビット長M系列巡回符号発生器412から以下のようにビットを抽出することにより出力される。
【０１２２】
u8 [11:0]= [1',3',3,12,9',10,10',11,7',0,2',7]  ・・・（３９）
u9 [11:0]= [8,0',1,6,4',6',2,4,5',9,8',5]       ・・・（４０）
【０１２３】
式（３９）及び式（４０）の表記は、式（３１）等と同様である。但し、17ビット長M系列巡回符号発生器411及び11ビット長M系列巡回符号発生器412から抽出するビット位置に関して、u8 [11:0]はu6 [11:0]に対してMSB側に1ビットシフトし、u6 [11:0]でMSBだったビット番号「7」をLSBに割り当てている。同様にu9 [11:0]はu7 [11:0]に対してMSB側に1ビットシフトし、u7 [11:0]でMSBだったビット番号「5」をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【０１２４】
M系列巡回符号発生器413は17ビット長のM系列巡回符号発生器であり、シードレジスタ401に格納されたシード値を初期値として動作する。また、M系列巡回符号発生器414は11ビット長のM系列巡回符号発生器であり、シードレジスタ402に格納されたシード値を初期値として動作する。17ビット長M系列巡回符号発生器413及び11ビット長M系列巡回符号発生器414は、12ビットの一様乱数u10 [11:0]及びu11 [11:0]を出力する。ここで、一様乱数u10 [11:0]及びu11 [11:0]はu0 [11:0]及びu1 [11:0]と同様な方法で17ビット長M系列巡回符号発生器413及び11ビット長M系列巡回符号発生器414から以下のようにビットを抽出することにより出力される。
【０１２５】
u10 [11:0]= [3',3,12,9',10,10',11,7',0,2',7,1']  ・・・（４１）
u11 [11:0]= [0',1,6,4',6',2,4,5',9,8',5,8]       ・・・（４２）
【０１２６】
式（４１）及び式（４２）の表記は、式（３１）等と同様である。但し、17ビット長M系列巡回符号発生器413及び11ビット長M系列巡回符号発生器414から抽出するビット位置に関して、u10 [11:0]はu8 [11:0]に対してMSB側に1ビットシフトし、u8 [11:0]でMSBだったビット番号「1'」をLSBに割り当てている。同様にu11 [11:0]はu9 [11:0]に対してMSB側に1ビットシフトし、u9 [11:0]でMSBだったビット番号「8」をLSBに割り当てている。このように一様乱数間でM系列巡回符号発生器からの抽出位置を変更することにより、抽出位置の依存性による、一様乱数間の相関を少なくしている。
【０１２７】
図１２で説明した複数のM系列巡回符号から1個の一様乱数を生成する場合、生成した一様乱数間の相互相関だけでなく、M系列巡回符号間の相互相関が強く出ないようにシード値を決定する必要があるが、良いシード値を与えることで、28ビット長のM系列巡回符号を一つだけ用いる場合よりも11ビット長のM系列巡回符号と17ビット長のM系列巡回符号各々１個用いる場合の方が、良質な正規分布特性を持つ乱数を生成することができる。
【０１２８】
なお、上記実施形態は本発明の一例を示したものであり、本発明はこれに限定されるべきものではないことは言うまでもないことである。
【０１２９】
例えば、式（１６）又は式（２９）及び式（３０）で表した組み合わせの原始多項式をもつM系列巡回符号発生器を使用したが、一様乱数間の相関が出ないような原始多項式であれば、特に限定はない。
【０１３０】
また、一様乱数を生成するために28ビット長M系列巡回符号発生器の上記で示したビット位置からビットを抽出したが、乱数としての特性を良くするために連続したビット位置にならないよう不連続なビット位置から抽出していれば、特に限定はない。
【０１３１】
また、第４の実施形態で11ビット長と17ビット長のM系巡回符号器を使用したが、この組み合わせの合計ビット長が28ビット以上であれば、特に限定はない。
【０１３２】
以上説明したように、第３及び第４の実施形態によれば、中心極限定理を用いて正規乱数を生成する場合に、少ないハードウェア規模で良好な正規分布特性をもつ正規乱数発生装置を提供することができる。また、すべてのM系列巡回多項式のシード値を設定する必要がないので、良質な正規分布特性をもつ乱数を生成するシード値を決定しやすい。
【０１３３】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【図面の簡単な説明】
【０１３４】
【図１】本発明の第１の実施形態の正規乱数生成手法を説明する図である。
【図２】第１の実施形態の識別ビットのビット設定について説明する図である。
【図３】第１の実施形態のビット操作部について説明する図である。
【図４】本発明の第２の実施形態の正規乱数生成手法を説明する図である。
【図５】本実施形態の正規乱数生成装置により出力した正規乱数の近傍の相関を示したグラフである。
【図６】本実施形態の正規乱数生成装置により出力した正規乱数の28ビットM系列の周期周辺の相関を示したグラフである。
【図７】本実施形態の正規乱数生成装置により出力した正規乱数の度数密度グラフである。
【図８】従来技術を用いた正規乱数生成手法を説明する図である。
【図９】本発明の第３の実施形態を説明する図である。
【図１０】本実施形態のスケーリングを説明する図である。
【図１１】本実施形態の28bitM系列巡回符号発生器を用いた一様乱数生成部の構成を説明する図である。
【図１２】本発明の第４の実施形態の17bitM系列巡回符号発生器及び11bitM系列巡回符号発生器を用いた一様乱数生成部の構成を説明する図である。
【符号の説明】
【０１３５】
100  シードレジスタ、
101  M系列巡回符号生成器、
102  一様乱数生成部、
103  正規乱数生成部、
104〜115  ビット操作部、
116〜127  識別ビット、
300  ビット抽出回路、
301  排他的論理和演算回路、
302  ビット反転回路、
500  一様乱数生成部、
501〜506  識別ビット、
507  正規乱数生成部、
508  カウンタ、
1000〜1011  シードレジスタ、
1012〜1023   M系列巡回符号生成器、
1024  一様乱数生成部、
1025  正規乱数生成部、
1026〜1037  ビット操作部
【図１】
2006293429.tif 000005
【図２】
2006293429.tif 000006
【図３】
2006293429.tif 000007
【図４】
2006293429.tif 000008
【図５】
2006293429.tif 000009
【図６】
2006293429.tif 000010
【図７】
2006293429.tif 000011
【図８】
2006293429.tif 000012
【図９】
2006293429.tif 000013
【図１０】
2006293429.tif 000014
【図１１】
2006293429.tif 000015
【図１２】
2006293429.tif 000016