(57)【要約】【課題】乱数性を向上させること。【解決手段】本発明は、複数のレジスタを有するシフトレジスタを備え、前記複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成する第１生成回路１０と、第２擬似乱数を生成する第２生成回路１２と、前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力する選択回路１４と、を具備する擬似乱数生成回路１００である。【選択図】図３
2014164342.tif 000002
【特許請求の範囲】
【請求項１】
複数のレジスタを有するシフトレジスタを備え、前記複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成する第１生成回路と、
第２擬似乱数を生成する第２生成回路と、
前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力する選択回路と、
を具備することを特徴とする擬似乱数生成回路。
【請求項２】
前記選択回路は、前記第２擬似乱数を用い前記複数ビットのうち出力する最初のビットを選択することを特徴とする請求項１記載の擬似乱数生成回路。
【請求項３】
前記選択回路は、前記複数ビットのうち前記最初のビットから一定数のビットを出力することを特徴とする請求項２記載の擬似乱数生成回路。
【請求項４】
前記第２擬似乱数のビット数は前記第１擬似乱数のビット数より少ないことを特徴とする請求項１から３のいずれか一項記載の擬似乱数生成回路。
【請求項５】
前記シフトレジスタは、線形帰還シフトレジスタであることを特徴とする請求項１から４のいずれか一項記載の擬似乱数生成回路。
【請求項６】
シフトレジスタが備える複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成するステップと、
第２擬似乱数を生成するステップと、
前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力するステップと、
を含むことを特徴とする擬似乱数生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、擬似乱数生成回路および擬似乱数生成方法に関し、例えばシフトレジスタを備える擬似乱数生成回路および擬似乱数生成方法に関する。
【背景技術】
【０００２】
ハードウエアを用いた擬似乱数生成方法として、線形帰還シフトレジスタを用いることが知られている。例えば、原始多項式を用い、擬似乱数としてＭ系列を発生する線形帰還シフトレジスタが知られている（例えば特許文献１から３）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−２９１６１９号公報
【特許文献２】特開平１−２６５６０９号公報
【特許文献３】特開２００３−３３０７０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
線形帰還シフトレジスタを用い発生させた乱数は、１ビットの擬似乱数としては非常によい性質を有している。しかしながら、複数ビットの擬似乱数を生成する場合、乱数性が悪化する場合がある。
【０００５】
本擬似乱数生成回路および擬似乱数生成方法は、乱数性を向上させることを目的とする。
【課題を解決するための手段】
【０００６】
複数のレジスタを有するシフトレジスタを備え、前記複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成する第１生成回路と、第２擬似乱数を生成する第２生成回路と、前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力する選択回路と、を具備することを特徴とする擬似乱数生成回路を用いる。
【０００７】
シフトレジスタが備える複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成するステップと、第２擬似乱数を生成するステップと、前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力するステップと、を含むことを特徴とする擬似乱数生成方法を用いる。
【発明の効果】
【０００８】
本擬似乱数生成回路および擬似乱数生成方法によれば、乱数性を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、Ｍ系列を生成する線形帰還シフトレジスタのブロック図である。
【図２】図２は、線形帰還シフトレジスタの出力例を示す図である。
【図３】図３（ａ）は、実施例１に係る擬似乱数生成回路のブロック図、図３（ｂ）は、擬似乱数を示す図である。
【図４】図４は、実施例２に係る擬似乱数生成回路を示すブロック図である。
【図５】図５は、第１生成回路の出力から選択回路が選択するビットを示す図である。
【図６】図６は、実施例２に係る擬似乱数生成回路の出力例を示す図である。
【図７】図７は、実施例３に係る疑似乱数生成回路を示すブロック図である。
【図８】図８は、実施例４に係る擬似乱数生成回路を示すブロック図である。
【図９】図９は、実施例５に係る擬似乱数生成回路を示すブロック図である。
【発明を実施するための形態】
【００１０】
まず、擬似乱数としてＭ系列を生成する線形帰還シフトレジスタについて説明する。図１は、Ｍ系列を生成する線形帰還シフトレジスタのブロック図である。図１を参照し、線形帰還シフトレジスタ５０は、複数のレジスタ２０と排他的論理和回路２２を備えている。各レジスタＤ０からＤ７の出力は、サイクルごとに、外部に出力されるとともに、次段のレジスタＤ１からＤ０に出力される。排他的論理和回路２２は２入力の排他的論理和を出力する。
【００１１】
線形帰還シフトレジスタ５０は、８次の原始多項式Ｍ（ｘ）＝ｘ８＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１を用い擬似乱数を発生させるものである。ｎ次の原始多項式からは、（２ｎ−１）個の擬似乱数を生成することができる。原始多項式は、有限個しか存在しない。
【００１２】
図２は、線形帰還シフトレジスタ５０の出力例を示す図である。Ｄ７からＤ０の項は各レジスタＤ７からＤ０からの出力を示している。１０進表示の項はＤ７からＤ０の値を１０進表示したものである。サイクルごとに１０進表示および各レジスタＤ７からＤ０の出力を示している。サイクル１のとき、任意の初期値として００１１００００を与えた場合を示している。例えば枠６０内のように、任意の列内の数字は乱数となる。また、枠６２内のように、任意の行内の数字は乱数となる。しかしながら、枠６４のように、複数行に跨る数字は乱数性が低い。これは、行の数字は隣接する行の数字から１ビットシフトした数字になるためである。例えばサイクル２のＤ７からＤ１は、それぞれサイクル１のＤ６からＤ０と同じ数値となる。
【００１３】
Ｍ系列の擬似乱数生成回路を用い、所望の複数ビット幅の乱数を不定期に用いる場合、以下の方法がある。第１に、図２の枠６０のように、所望サイクルの同じレジスタ（例えばレジスタＤ０）から所望ビット数の乱数を取得する方法である。第２に、図２の枠６２のように、あるサイクルの複数のレジスタＤ７からＤ０の数値を取得する方法である。第３に、所望のビット数に対応する数のレジスタを有する線形帰還シフトレジスタを準備する方法である。
【００１４】
しかしながら、第１の方法では、所望ビット数幅の乱数を生成するまでに時間がかかる。第２の方法では、枠６４のように、連続して乱数を取得した場合、ビット単位ではサイクルの前後で１ビットシフトした値のため、乱数性がよくない。第３の方法では、原始多項式は有限個のため、所望のビット分の線形帰還シフトレジスタを準備できるとは限らない。例えば、８次の原始多項式は８個、５次の原始多項式は３個であることが知られているが、３４次の多項式は１つも知られていない。
【００１５】
このように、不定期に擬似乱数を得られ、大きなビット幅にも対応し、乱数の前後に相関性がない擬似乱数生成回路が求められる。さらに、同じ乱数列を再現できることも求められる。
【実施例１】
【００１６】
図３（ａ）は、実施例１に係る擬似乱数生成回路のブロック図、図３（ｂ）は、擬似乱数を示す図である。図３（ａ）を参照し、擬似乱数生成回路１００は、第１生成回路１０、第２生成回路１２および選択回路１４を備えている。第１生成回路１０は、複数のレジスタを有するシフトレジスタを備える。第１生成回路１０は、複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成する。第２生成回路１２は、第２擬似乱数を生成する。第２生成回路１２は、シフトレジスタを備えてもよいが、他の回路でもよい。
【００１７】
図３（ｂ）を参照し、第１擬似乱数は例えばｎビットである。第２擬似乱数は例えばｍビットである。このときｎ＜２ｍである。例えば、ｎ＝７およびｍ＝３である。選択回路１４は、第２擬似乱数を用い第１擬似乱数の複数ビットのうち出力するビットを選択し出力する。例えば第２擬似乱数が示す数字に基づき第１擬似乱数の複数ビットの１つを選択する。例えば図３（ｂ）においては、第２擬似乱数が０１１のため、第１擬似乱数のうち４番目のビットを選択する。
【００１８】
実施例１によれば、選択回路１４が第２擬似乱数を用い第１擬似乱数の複数ビットのうち出力するビットを選択し出力する。これにより、１つの擬似乱数生成回路を用いる場合に比べ、乱数性を向上させることができる。
【実施例２】
【００１９】
実施例２は、Ｍ系列を生成する回路を用いた擬似乱数生成回路の例である。図４は、実施例２に係る擬似乱数生成回路を示すブロック図である。図４を参照し、擬似乱数生成回路１０２は、第１生成回路１０、第２生成回路１２、選択回路１４およびフリップフロップ回路１６を備えている。第１生成回路１０は、ｎ個のレジスタ２０ａ（ＲＤ０からＲＤｎ−１）を有するＭ系列生成回路であり、ｎビットのＭ系列（以下、Ｒ系列と記す）を出力する。原始多項式に応じ排他的論理和回路２２ａが設けられている。各レジスタ２０ａの出力は、第１擬似乱数（Ｒ系列）の各ビットとして選択回路１４に出力される。第２生成回路１２は、ｍ個のレジスタ２０ｂ（ＣＤ０からＣＤｍ−１）を有するＭ系列生成回路であり、ｍビットのＭ系列（以下、Ｃ系列と記す）を出力する。原始多項式に応じ排他的論理和回路２２ｂが設けられている。各レジスタ２０ｂの出力は、第２擬似乱数（Ｃ系列）の各ビットとして選択回路１４に出力される。第２擬似乱数は、ｍビットの数値として用いるためビットを連接して表現している。
【００２０】
選択回路１４は、第１擬似乱数（Ｒ系列）のうち第２擬似乱数（Ｃ系列）が示すビットからｋビット数分を選択し、フリップフロップ回路１６に出力する。ｋビットは、固定の値でもよいし、変更可能な値でもよい。フリップフロップ回路１６（保持回路）は、活性化信号Ｐｏｐが活性になると、選択回路１４が出力する擬似乱数を保持する。これにより、擬似乱数生成回路１０２は任意の時間において、擬似乱数を出力できる。
【００２１】
図５は、第１生成回路の出力から選択回路が選択するビットを示す図である。第１擬似乱数（Ｒ系列）は、レジスタＲＤ０からＲＤｎ−１に対応する複数のビットを有している。出力する擬似乱数のビット数ｋを４とする。第２擬似乱数（Ｃ系列）が示す数値Ｃが１の場合、選択回路１４は、ＲＤ１からＲＤ４に対応するビットを選択する。Ｃ＝５の場合、選択回路１４は、ＲＤ６からＲＤ９に対応するビットを選択する。Ｃ＝３の場合、選択回路１４は、ＲＤ３からＲＤ６に対応するビットを選択する。Ｃ＝ｎ−２の場合、選択回路１４は、ＲＤｎ−２、ＲＤｎ−１、ＲＤ０およびＲＤ１に対応するビットを選択する。このように、選択するビットがサイクルを越える場合は、次のサイクルの先頭からのビットを選択する。Ｃ＝ｎの場合、選択回路１４は、ＲＤ０からＲＤ３に対応するビットを選択する。
【００２２】
ｎおよびｍは、原始多項式が存在する次数である。また、Ｃ系列の示す数値がＲ系列からランダムに選択を開始するビットを選択するため、Ｃ系列の変域は、Ｒ系列の全てのレジスタを表現することが好ましい。すなわちＣ系列が示す数値はＲ系列のビット数以下となる。このため、ｎ＜２ｍであることが好ましい。例えば、ｎ＝１２７の場合、ｍ＝７とする。このように、第２擬似乱数のビット数は第１擬似乱数のビット数より少ない。
【００２３】
第１疑似乱数は、（２ｎ−１）周期、第２疑似乱数は（２ｍ−１）周期を有する。実施例２では、第１疑似乱数の値を第２疑似乱数の値を元に選択している。このため、（２ｎ−１）と（２ｍ−１）との最小公倍数が疑似乱数生成回路１０２が生成する疑似乱数の周期となる。
【００２４】
図６は、実施例２係る擬似乱数生成回路の出力例を示す図である。図６を参照し、８ビットの擬似乱数を出力する場合を示している。サイクルが隣接する場合もデータはランダムである。
【００２５】
実施例２に係る擬似乱数生成回路１０２は、Ｐｏｐをアクティブにすることにより不定期に擬似乱数が得られる。また、第１生成回路１０のレジスタ数を大きくすることにより大きなビット幅にも対応する。さらに、図６のように、隣接するサイクルの乱数間に相関性がない。さらに、Ｍ系列は、初期値（シード）が同じであれば、同じサイクルには同じ乱数が出現する。よって、同じ乱数列を再現できる。なお、初期値は０以外の数値とする。
【００２６】
また、選択回路１４は、第２擬似乱数を用い複数ビットのうち出力する最初のビットを選択することができる。さらに、選択回路１４は、複数ビットのうち最初のビットから一定数のビットを出力することができる。
【実施例３】
【００２７】
図７は、実施例３に係る疑似乱数生成回路を示すブロック図である。図７を参照し、疑似乱数生成回路１０４は、フリップフロップ回路が設けられていない。活性化信号Ｐｏｐが各レジスタ２０ａおよび２０ｂの活性化端子Ｅｎに入力する。その他の構成は、実施例２と同じであり、説明を省略する。
【００２８】
実施例３によれば、活性化信号Ｐｏｐが活性になると、第１生成回路１０は第１疑似乱数を生成する。また、第２生成回路１２は第２疑似乱数を生成する。これにより、擬似乱数生成回路１０４は任意の時間において、擬似乱数を出力できる。
【実施例４】
【００２９】
実施例４は、ＰＮ系列を生成する回路を用いた擬似乱数生成回路の例である。図８は、実施例４に係る擬似乱数生成回路を示すブロック図である。図８を参照し、擬似乱数生成回路１０６において、第１生成回路１０は、ｎ個のレジスタ２４ａ（ＲＤ０からＲＤｎ−１）を有するＰＮ系列生成回路であり、ｎビットのＲ系列を出力する。レジスタ２４ａごとに排他的論理和回路２６ａが設けられている。各レジスタ２４ａの出力は、第１擬似乱数（Ｒ系列）の各ビットとして選択回路１４に出力される。第２生成回路１２は、ｍ個のレジスタ２４ｂ（ＣＤ０からＣＤｍ−１）を有するＰＮ系列生成回路であり、ｍビットのＣ系列を出力する。レジスタ２４ｂごとに排他的論理和回路２６ｂが設けられている。各レジスタ２４ｂの出力は、第２擬似乱数（Ｃ系列）の各ビットとして選択回路１４に出力される。その他の構成は、実施例２と同じであり説明を省略する。
【００３０】
ＰＮ系列は、排他的論理和回路２６ａおよび２６ｂが任意のレジスタ２４ａおよび２４ｂの出力に設けられることにより生成できる。実施例４のように、レジスタ２４ａおよび２４ｂの出力の全てに排他的論理和回路２６ａおよび２６ｂが設けられてもよいし、レジスタ２４ａおよび２４ｂの一部の出力に排他的論理和回路２６ａおよび２６ｂが設けられてもよい。Ｍ系列は、ＰＮ系列のうち原始多項式に対応する特別な場合に対応する。
【実施例５】
【００３１】
実施例５は、Ｇｏｌｄ系列を生成する回路を用いた擬似乱数生成回路の例である。図９は、実施例５に係る擬似乱数生成回路を示すブロック図である。図９を参照し、擬似乱数生成回路１０８において、第１生成回路１０および第２生成回路１２は、Ｇｏｌｄ系列生成回路であり、それぞれｎビットのＲ系列およびｍビットのＣ系列を出力する。Ｇｏｌｄ系列は、複数のＭ系列の論理積により生成される。または、Ｇｏｌｄ系列は、複数のＭ系列の排他的論理和によっても生成できる。
【００３２】
第１生成回路１０は、ｎ個のレジスタ２８ａ（ＲＤ０からＲＤｎ−１）を一対有している。原始多項式に応じ排他的論理和回路３０ａが設けられている。一対の各レジスタ２８ａの出力は、論理積回路３２ａにより論理積され、各ビットとして選択回路１４に出力される。第２生成回路１２は、ｍ個のレジスタ２８ｂ（ＣＤ０からＣＤｍ−１）を一対有する。原始多項式に応じ排他的論理和回路３０ｂが設けられている。一対の各レジスタ２８ｂの出力は、論理積回路３２ｂにより論理積され、各ビットとして選択回路１４に出力される。その他の構成は、実施例２と同じであり説明を省略する。
【００３３】
実施例２から５のように、第１生成回路１０として、線形帰還シフトレジスタを用いることができる。実施例２および３においては、線形帰還シフトレジスタはＭ系列を生成する。実施例４においては、線形帰還シフトレジスタはＰＮ系列を生成する。実施例５においては、線形帰還シフトレジスタはＧｏｌｄ系列を生成する。
【００３４】
第２生成回路１２は、線形帰還シフトレジスタでなくともよいが、実施例２から５のように、線形帰還シフトレジスタでもよい。第１生成回路１０と第２生成回路１２とは異なるタイプの線形帰還シフトレジスタでもよい。
【００３５】
また、実施例４および５において、実施例３のように、各レジスタに活性化信号が入力し、活性化信号が活性になると、第１生成回路１０が第１擬似乱数を生成してもよい。
【００３６】
実施例１から５に係る擬似乱数生成回路は、例えば、論理エミュレータまたはＦＰＧＡ（Field Programmable Gate Array）を用いた論理検証に用いられる。このような分野では、乱数性のよい擬似乱数が求められている。ソフトウエアを用いて擬似乱数を生成する場合、高速動作が難しい。このため、ソフトウエアにより生成した擬似乱数をメモリに格納し、メモリから擬似乱数を読み出すことにより、高速動作を確保する。この方法では、メモリ使用量が大きくなり回路規模が大きくなる。実施例１から５に係る擬似乱数生成回路によれば、乱数性のよい擬似乱数を高速に生成することができる。これにより、メモリ使用量を削減し、回路規模を削減することができる。実施例１から５に係る擬似乱数生成回路は、上記以外の用途に用いることができることはいうまでもない。
【００３７】
以上、本発明の実施例について詳述したが、本発明は係る特定の実施例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【００３８】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）複数のレジスタを有するシフトレジスタを備え、前記複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成する第１生成回路と、第２擬似乱数を生成する第２生成回路と、前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力する選択回路と、を具備することを特徴とする擬似乱数生成回路。
（付記２）前記選択回路は、前記第２擬似乱数を用い前記複数ビットのうち出力する最初のビットを選択することを特徴とする付記１記載の擬似乱数生成回路。
（付記３）前記選択回路は、前記複数ビットのうち前記最初のビットから一定数のビットを出力することを特徴とする付記２記載の擬似乱数生成回路。
（付記４）前記第２擬似乱数のビット数は前記第１擬似乱数のビット数より少ないことを特徴とする付記１から３のいずれか一項記載の擬似乱数生成回路。
（付記５）前記シフトレジスタは、線形帰還シフトレジスタであることを特徴とする付記１から４のいずれか一項記載の擬似乱数生成回路。
（付記６）前記線形帰還シフトレジスタはＭ系列の擬似乱数を生成することを特徴とする付記５記載の擬似乱数生成回路
（付記７）前記線形帰還シフトレジスタはＧｏｌｄ系列の擬似乱数を生成することを特徴とする付記５記載の擬似乱数生成回路。
（付記８）前記線形帰還シフトレジスタはＰＮ系列の擬似乱数を生成することを特徴とする付記５記載の擬似乱数生成回路。
（付記９）活性化信号が活性になると、前記選択回路の出力を保持する保持回路を具備することを特徴とする付記１から８のいずれか一項記載の擬似乱数生成回路。
（付記１０）活性化信号が活性になると、前記第１生成回路は前記第１擬似乱数を生成することを特徴とする付記１から８のいずれか一項記載の擬似乱数生成回路。
（付記１１）シフトレジスタが備える複数のレジスタにそれぞれ対応する複数ビットを有する第１擬似乱数を生成するステップと、第２擬似乱数を生成するステップと、前記第２擬似乱数を用い前記第１擬似乱数の前記複数ビットのうち出力するビットを選択し出力するステップと、を含むことを特徴とする擬似乱数生成方法。
【符号の説明】
【００３９】
１０          第１生成回路
１２          第２生成回路
１４          選択回路
１６          フリップフロップ回路
２０          レジスタ
【図１】
2014164342.tif 000003
【図２】
2014164342.tif 000004
【図３】
2014164342.tif 000005
【図４】
2014164342.tif 000006
【図５】
2014164342.tif 000007
【図６】
2014164342.tif 000008
【図７】
2014164342.tif 000009
【図８】
2014164342.tif 000010
【図９】
2014164342.tif 000011