JP4938612B2

JP4938612B2 - 乱数発生器

Info

Publication number: JP4938612B2
Application number: JP2007265138A
Authority: JP
Inventors: ナイジェルマッジトレバー; テオドールブラアフデーヴィッド; アルフォンソトクナガカルロス
Original assignee: University of Michigan Medical School
Current assignee: University of Michigan Medical School
Priority date: 2006-10-12
Filing date: 2007-10-11
Publication date: 2012-05-23
Anticipated expiration: 2027-10-11
Also published as: GB2442838B; GB2442838A; US8346832B2; GB0718090D0; CN101174201B; JP2008097610A; CN101174201A; US20080091755A1

Description

本発明の分野はデータ処理に関するものであり、特に、乱数の発生に関するものである。

真の乱数を発生することはかなり困難である。種々の方法は、ランダム出力値を生成するのに準安定事象（ｍｅｔａｓｔａｂｌｅｅｖｅｎｔｓ）を用いている。どの方法も理想からは遠く、ランダムでないと認めた場合は出力を操作してランダム性（ｒａｎｄｏｍｎｅｓｓ）を回復しようとする。これ自体が非ランダム・プロセスである。例えば、或る方法は０および１が長く続かないようにするためにフォン・ノイマン補正法を用いる（例えば、Ｒ．Ｂｒｅｄｅｒｌｏｗ他の「単一酸化物トラップのランダム電信雑音を用いる低電力の真の乱数発生器（ＡＬｏｗ−ＰｏｗｅｒＴｒｕｅＲａｎｄｏｍＮｕｍｂｅｒＧｅｎｅｒａｔｏｒＵｓｉｎｇｔｈｅＲａｎｄｏｍＴｅｌｅｇｒａｐｈＮｏｉｓｅｏｆＳｉｎｇｌｅＯｘｉｄｅ−Ｔｒａｐｓ）」、ＩＳＳＣＣＤｉｇ．Ｔｅｃｈ．Ｐａｐｅｒｓ，ｐｐ．５３６−５３２、２００６年２月、を参照のこと）。かかる補正は、最初のビット・ストリームが真にランダムでなかったことを隠しているだけであって、真のランダム性を回復することはできない。Ｋｉｎｎｉｍｅｎｔ他の「準安定を用いるオン・チップ乱数発生器の設計（ＤｅｓｉｇｎｏｆａｎＯｎ−ＣｈｉｐＲａｎｄｏｍＮｕｍｂｅｒＧｅｎｅｒａｔｏｒｕｓｉｎｇＭｅｔａｓｔａｂｉｌｉｔｙ）」、ＰｒｏｃＥｕｒｏｐｅａｎＳｏｌｉｄ−Ｓｔａｔｅｃｉｒｃｕｉｔｃｏｎｆ．，ｐｐ５９５−５９８、２００２年９月、が開示している方法は準安定を用い、ＸＯＲ補正器を用いて熱雑音を増幅し、システムをバイアスすることにより準安定動作を制御して同じ数の０と１を生成する。

本発明の第１の態様はランダム出力値を生成する回路を提供する。この回路は、双安定回路であって、０または１を出力する２つの安定状態を有し、また０と１の間の浮動値を出力する平衡準安定状態を有し、スイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し（ｒｅｓｏｌｖｉｎｇ）、前記状態は前記双安定回路のポートの電圧レベルに依存する双安定回路と、前記双安定回路の前記ポートの電圧レベルを制御するための電圧レベル制御回路と、スイッチ・オンの後で前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する切換え時間を測定するための時間測定回路と、制御論理であって、前記時間測定回路、前記電圧レベル制御回路、および前記双安定回路のスイッチ・オンおよびオフを制御し、以下のシーケンス、すなわち、前記電圧レベル制御回路を制御して前記双安定回路の前記ポートを或る予め決められた電圧レベルに設定し、前記双安定回路をスイッチ・オンし、測定した切換え時間を検出し、前記双安定回路をオフにするというシーケンスを実行し、前記測定した切換え時間が或る予め決められた値より長い場合は前記双安定回路の前記転換した安定状態を前記ランダム出力値として出力する制御論理と、を含む。

回路に準安定状態を与えると、回路はその準安定状態で平衡し、次に安定状態に切り換わるときは必ず熱プロセスにより切り換わる。熱プロセスはランダムである。このように、この安定状態への切換えを用いて、真のランダム出力値を生成することができる。かかるシステムがかかえる１つの問題は準安定状態に到達することが必ずしも容易ではないことである。しかし本発明者は、スイッチ・オンから安定状態への切換えまでに要する時間は、スイッチ・オンのときにこの回路が最初に準安定状態にあったかどうかを示すものであると認識した。実際に、すぐ切り換わる場合はこの回路は最初に準安定状態で平衡していなかった可能性があるが、少し長い時間を要した場合はしばらくの間その準安定状態にあったことになる。このように、準安定状態を持つ双安定回路を用いればランダム出力値が得られるだけでなく、切換えに要した時間を用いれば最初にその準安定状態にあったかどうか、したがって出力値が確かにランダム出力値かどうかの測度にすることができる。これにより、出力値がランダムかどうかを出力値自身で判断する必要がなくなる。

実際に、スイッチ・オンのときに回路が準安定状態に近いほど、最後に転換された状態は熱プロセス（すなわち、ランダムな物理プロセス）による可能性が高い。このように、出力ストリームを修正して一層ランダムにしようとする（これ自体が欠陥のあるプロセスである）のではなく、入力を修正して回路をその準安定状態に近づけるようにすればよい。実際にシステムは、ランダムな物理プロセス（例えば、熱雑音）がシステムに影響する程度によりランダムと認めることができる。
或る実施の形態では、前記制御論理は前記シーケンスを連続的に実行して複数のランダム出力値を出力する。
シーケンスの繰返しを用いて、例えば乱数を形成するのに用いることのできる複数のランダム値を生成することができる。

或る実施の形態では、複数の連続したシーケンスについて前記測定した切換え時間が前記予め決められた値より長くない場合は、前記制御論理はリセット操作を行う。このリセット操作では、前記双安定回路の前記ポートの異なる設定電圧レベルについて前記シーケンスを複数回実行し、また前記リセット操作中は前記転換した安定状態を出力しない。前記リセット操作の後に、前記制御論理は前記予め決められた電圧レベルをリセットして、前記リセット操作中の最も長い平均切換え時間を出力した電圧レベル値にする。

双安定回路がその平衡点の近くで動作を続けるようにするには、リセット操作をときどき実行する必要がある。したがって、制御論理は或る回数（この回数は環境に従って選択する）の連続的なシーケンスの間、測定した切換え時間が予め決められた値より小さくなるかどうか検出する。小さくなることは、回路がその最適動作位置から離れたことを示してよい。この場合はリセット操作を行う。リセット操作は双安定回路のポートの電圧レベルを変えて、異なる設定電圧レベル毎にシーケンスを或る回数実行し、最も長い平均切換え時間になった設定電圧レベルを選択し、その後のシーケンスではこれを予め決められた電圧レベルとしてリセットする。回路の開始状態がその準安定状態に近いほどランダムな転換状態が多くなり、ランダム値として出力してよい。したがって、できるだけ近い状態に保つことが望ましく、このために本発明の実施の形態では回路がこの状態からいつ離れたかを検出して、必要なときにリセット操作を行う。

或る実施の形態では、前記リセット操作中は、前記制御論理は、最初およびその後のシーケンスのセットについて前記平均切換え時間が増えるように前記設定電圧レベルを或る予め決められた量だけ修正し、次にシーケンスの更なるセットについて前記設定電圧レベルを前記予め決められた量だけ修正し、これを前記平均切換え時間が減少するまで行う。

リセット中の電圧レベルの修正を制御して、最初はシーケンスのセット毎に切換え時間が増え、その後切換え時間が減少し始めるようにするとよい。これにより、電圧平衡点を通り越したことが分かり、電圧を余り大きく調整し過ぎない限り恐らく準安定状態は達成され、したがって、シーケンスの或る集合の最大平均測定切換え時間はスイッチ・オンのときの準安定状態に対応し、これを生成した電圧は予め決められた値として適当である。

或る実施の形態では、前記リセット操作中は、前記制御論理はスイッチ・オンのときに設定した前記電圧レベルを修正して前記平均切換え時間を前のシーケンスに比べて長くし、前記平均切換え時間が前記予め決められた値を超えると前記電圧レベルを前記予め決められた電圧レベルとして設定し、前記変換された値を前記ランダム出力値として出力する。

リセット操作は平均切換え時間が予め決められた値より大きくなるまで電圧を修正し、次に電圧レベルを調整してこの値にしてよい。準安定状態を達成したことを示すように予め決められた値を選択したので、これは電圧レベルをリセットするのに用いてよい方法である。
この予め決められた値は回路内のデータ記憶装置内に記憶してよい。これは製造のときに較正した後で回路内に永久に記憶してよい。または使用中に回路を較正してもよいが、この場合は時々更新してよい。または、必要であれば外部から入力してもよい。

或る実施の形態では、前記予め決められた値は前記制御回路が較正操作を行ったときに生成される。前記較正操作は異なる設定電圧レベルについて前記転換した安定状態を出力せずに前記シーケンスを複数回実行して最も長い平均切換え時間を決定することを含み、前記制御回路は前記最も長い平均切換え時間を生成した前記電圧レベルに前記電圧レベルを設定して更なるシーケンスを複数回実行し、前記制御回路は前記更なるシーケンスが生成した前記転換した安定状態を分析して、スイッチ・オンのときに前記ラッチが前記準安定状態にあるかどうか判定し、そうであれば前記更なるシーケンスの前記最も長い平均切換え時間を前記予め決定された値として記憶する。

この回路を較正して、準安定状態を作る測定時間の予め決められた値を決定してよい。これは最初におよび／または必要であれば操作中に再び較正してよい。これは、例えばリセットした後も転換が速すぎる連続的なシーケンスが多い場合に必要であろう。
或る実施の形態では、前記分析によりスイッチ・オンのときに前記ラッチが前記準安定状態にないと判定した場合は、前記回路は誤り表示を出力する。
予め決められた値を用いることの別の利点は、測定した切換え時間がこの値を超えない場合はシステム内に誤りがあるかも知れないので、誤り表示を出力することができることである。これはシステムが決定性雑音から攻撃されている場合に有用であろう。このような場合は準安定状態に到達せず、誤り表示はこの問題を検出して対処するのに役立つ。

或る実施の形態では、前記回路は別のポートを備え、前記ポートおよび前記別のポートは前記出力値を出力し、前記電圧レベル制御回路は、前記別のポートに一定電圧を与えまた前記ポートに前記設定電圧レベルを与えることによりスイッチ・オンのときの前記ポートと前記別のポートとの電圧差を制御する。
多くの実施の形態で双安定回路は２つのポートを有し、電圧レベルは、一方に一定電圧を与え他方に変動する電圧を与えたときの２つのポートの電圧差として設定する。
双安定回路は２つの安定状態と１つの準安定状態とを有する任意の要素で形成してよいが、この回路には交差結合インバータ対が特に適している。なぜなら簡単に製作できるし、１つの準安定状態を有するからである。

或る実施の形態では、前記双安定回路に高電圧レール（ｒａｉｌｓ）および低電圧レールから電力を供給し、前記制御回路は前記高電圧レールおよび低電圧レールに電圧差を与えることにより前記双安定回路をオンにし、前記電圧レールのそれぞれに前記電圧差の半分の等しい電圧を与えることにより前記双安定回路をオフにする。
回路のスイッチ・オンおよびオフは準安定状態から双安定状態への切換え時間に明らかに影響するので、制御して行わなければならない。実施の形態によっては、両方の電圧レールを同じ中間電圧に設定し、スイッチ・オンのときはレールの電圧レベルをそれぞれ高い値と低い値に変える。

或る実施の形態では、前記時間測定回路はカウンタを備える。このカウンタは前記双安定回路の漸進的に遅延するスイッチ・オン信号によりそれぞれクロックされるフリップ・フロップの一連のアレイで構成する。前記双安定回路が安定状態に切り換わったことを示す信号を受けると前記カウンタは停止する。
時間は多くの方法で測定してよいが、簡単で正確な測定方法はカウンタを用いることである。このカウンタは漸進的に遅延するスイッチ・オン信号によりそれぞれクロックされるフリップ・フロップの一連のアレイで構成し、双安定回路が安定状態に切り換わると停止する。

或る実施の形態では、前記ランダム出力値は複数回生成され、前記複数のランダム出力値は乱数として出力される。
この回路は一般に乱数を生成するのに用いられる。したがって、ランダム出力値を多数回生成してこの乱数を作ってよい。
別の実施の形態では、本発明の第１の態様に係る複数の回路は、その出力を互いに並列に配置して乱数を生成する。

本発明の第２の態様はランダム出力値を生成する方法を提供する。この方法は、
（１）予め定められた電圧レベルを生成して前記電圧レベルを双安定回路に入力し、前記双安定回路は０または１を出力値としてそれぞれ生成する２つの安定状態を有し、また０と１の間の浮動出力値を持つ平衡準安定状態を有し、前記双安定回路はスイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し、前記双安定回路の前記状態は前記入力電圧レベルに依存するステップと、
（２）前記双安定回路をスイッチ・オンするステップと、
（３）前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する時間を測定するステップと、
（４）前記時間が或る予め決められた値より長い場合は前記転換した状態を前記ランダム出力値として出力するステップと、
を含む。

本発明の第３の態様はランダム出力値を生成する手段を提供する。この手段は、双安定手段であって、０または１を出力する２つの安定状態を有し、また０と１の間の浮動値を出力する平衡準安定状態を有し、スイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し、前記状態は前記双安定手段のポートの電圧レベルに依存する双安定手段と、前記双安定手段の前記ポートの電圧レベルを制御するための電圧レベル制御手段と、スイッチ・オンの後で前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する切換え時間を測定するための切換え時間測定手段と、制御手段であって、前記電圧レベル制御手段、前記切換え時間測定手段、および前記双安定手段のスイッチ・オンおよびオフを制御し、以下のシーケンス、すなわち、前記電圧レベル制御手段を制御して前記双安定手段の前記ポートを或る予め決められた電圧レベルに設定し、前記双安定手段をスイッチ・オンし、測定した切換え時間を検出するというシーケンスを実行し、前記測定した切換え時間が或る予め決められた値より長い場合は前記双安定手段の前記転換した安定状態を前記ランダム出力値として出力する制御手段と、を含む。

本発明の上記またはその他の目的、特徴、および利点は、例示の実施の形態の以下の詳細な説明を添付の図面と関連して読めば明らかになる。

図１は本発明の或る実施の形態に係る双安定回路３０と、インバータ１０および２０のそれぞれの入力電圧と出力電圧との差を示すグラフを示す。グラフから分かるように、各インバータは、入力電圧が０のとき対応する出力電圧は１である。入力電圧が上昇しても対応する出力電圧は約１を保ち、電圧が約０．５に達すると出力電圧はしばらくこの値を保ち、入力電圧が一層大きな値になると０に切り換わる。他方のインバータの入力／出力電圧も示されており、同じパターンに従う。点線で描き１２と示された点では準安定状態である。すなわち、入力電圧をこの値に設定すると２台のインバータは平衡し、電圧が少し変るとシステムはその安定状態の一方に反転して０または１を出力する。したがって、準安定状態はほんの一時的に安定であり、熱雑音などでも十分その状態から反転させることができる。このように、準安定状態が得られると熱雑音により状態の反転が起こる。これは確かにランダムである。

図２は双安定回路３０を示す。これは、この実施の形態ではトランジスタ形式の交差結合インバータ対である。図に見られるように、正電圧レール３５と、接地レール３６と、電圧出力および入力ポート３２とがある。

図３は本発明の或る実施の形態に係る回路５を示す。回路５は、制御論理４０、時間測定回路５０、データ記憶装置６０、比較器７０、双安定回路３０、および電圧制御回路８０を備える。動作を説明すると、入力信号が入ると制御論理４０は双安定回路３０にオフ信号を送ってこの回路の各電圧レールを中間電圧（この場合はそれぞれ０．５ボルト）に設定して、測定のシーケンスを開始する。次に制御信号を電圧制御回路８０に送り、ポート３２の電圧レベルを第１の測定のための第１のレベルに設定する。すなわち、一方のポートを一定電圧にセットし、他方を予め決められた電圧に設定する。この予め決められた電圧は前記一定電圧と同じでよく、またはこの電圧とは少し違ってよい。次に、制御回路４０は開始信号すなわちオン信号を双安定回路３０に送り、電圧レールを１ボルトと接地にそれぞれ設定する。この開始信号は時間測定回路５０にも送られる。この時間測定回路５０は、双安定回路３０が反転して安定状態になる（この時点で０または１をポート３２に出力する）までの時間を測定し、この反転により停止信号をトリガする回路３７をトリガして時間測定を停止する。

次に、測定した切換え時間とデータ記憶装置６０内に記憶されている値とを比較器７０で比較し、切換え時間がこの値より大きい場合は双安定回路３０からの出力値をランダムと見なして、これをランダム出力値としてデータ出力９０に出力する。切換え時間がこの値より大きくない場合は、制御論理４０はこの値を出力しない。次に双安定回路３０をオフにして測定シーケンスを繰り返し、測定した切換え時間がデータ記憶装置６０内に記憶されている値より大きい場合は、この値を（別の）ランダム出力値として出力する。必要な数のランダム値が出力されるまで、または測定した切換え時間がデータ記憶装置６０内に記憶されている値より或る連続した回数小さくなるまで、これを続ける。これが起こると回路がもはやその平衡点の近くで動作していないことを示すので、リセットする必要がある。注意すべきであるが、この実施の形態では或る連続した回数を超えるとリセットのトリガが起こるが、別の実施の形態では全回数の予め決められた何分の一かを超えたときにトリガしてよい。

リセット操作では、電圧制御回路８０が設定した少しずつ調整した制御電圧レベルについて、上に述べた測定シーケンスをそれぞれ予め決められた回数実行する。シーケンスのこの繰返しは最大平均測定切換え時間が見つかるまで続ける。これが見つかると、この時間を達成した電圧レベル制御回路が出力した電圧レベルを将来の測定シーケンスの電圧レベルとして用いる。注意すべきであるが、このシーケンスは入力電圧レベル毎に多数回実行しなければならない。なぜなら、準安定状態からの切換えはランダム・プロセスにより決まるので、達成される時間が異なるからである。どの電圧が平衡状態を作るかを決定するには平均測定時間が必要である。

リセットした後、連続した測定シーケンスを多数回実行しても十分長い測定時間が得られない場合は、システムを再び較正して異なる値をデータ記憶装置６０内に記憶してよい。これを行うには異なる電圧レベルについて測定シーケンスのセットを複数回実行して、最大平均切換え時間を見つける。次に、この最大平均切換え時間を得た電圧制御回路８０からの電圧レベルを回路の入力として多数回用い、９０に出力された出力値を統計的に分析して、それが真にランダムかどうか調べる。真にランダムである場合は、この値を得た切換え時間を新たな予め決められた値としてデータ記憶装置６０内に記憶し、実質的に再較正されたシステムと言えるシステムについてシーケンスを再び繰り返す。

真にランダムでない場合は、回路がその準安定状態を達成していないので誤り出力を出す。これは、決定性雑音のためか、または何らかの理由で不平衡な回路のためである。
すでに開示したように、測定シーケンスを複数回繰り返して複数のランダム出力値を生成し、これを乱数として用いてよい。またはかかる回路を多数並列に置いて、それぞれの出力９０を用いて乱数を作ってよい。

図４ａは電圧制御８０を含む双安定回路３０を詳細に示す。双安定回路３０は交差結合されたインバータ対１０，２０を備え、インバータ対はオン・オフするスイッチを備える。これらのスイッチは個々のインバータをその電圧レールにまたは中間電圧に接続する。これらのスイッチを動作させるために送られる開始信号は図３および図４Ｃの時間測定回路５０にも送られて時間測定を開始する。

双安定回路３０はポート３２に接続する電圧制御回路８０を有する。ポート３２の中央にまたがって等化器が接続される。開始またはリセットのとき、これらのポート３２は測定シーケンスの集合について少しずつ異なる電圧レベルを有するよう設定する。これらの少しずつ異なる電圧レベルを測定シーケンスの集合毎に変え、双安定回路が安定状態に到達するのに要する平均時間を集合毎に測定する。これはこの電圧の差に依存する。電圧制御信号を受けるポート３２はまた電圧レベルを出力し、またこの信号を用いて停止信号をトリガする。すなわち、これが安定状態に切り換わると、この信号を用いて時間測定回路５０の停止信号をトリガする。

図４ｂは電圧制御回路を詳細に示す。インバータへの入力電圧を設定するこの回路は、ＤＣ基準電圧バイアスと、容量結合によりポートに電荷を注入するコンデンサのアレイとを有する。注入される電荷の量は、ラッチを調整して準安定にする制御アルゴリズムによりプログラムする。制御の設定は、コンデンサのアレイを切り換えるドライバのイネーブル信号に与えられる。ポートに与えられる電荷の量は設定された電圧レベルに依存する。したがって、この回路はポートの電圧レベルを設定するものと見なしてもよいし、またはポートに電荷を注入するものと見なしてもよい。

図４ｃは、ラッチが準安定状態から安定状態に転換するのに要する時間を測定する回路を示す。時間測定回路５０に入力される開始信号は双安定ラッチ３０に入力される開始信号と同じである。停止信号は双安定回路３０がその安定状態に切り換わると生成される。時間測定回路５０は開始信号の遅延信号によりクロックされるフリップ・フロップの一連のアレイで構成し、また停止信号を捕らえる。この一連のアレイの出力は、開始信号と停止信号の差を量子化する遅延段の数を示す温度計コードで形成する。その範囲を広げるには、開始信号がアレイを回った回数を決定するカウンタを含めてよい。

停止信号は、ラッチが最終的にいつその状態を転換したかを決定する回路３７（図３参照）が生成する。或る実施の形態では、この回路は正および負の電源電圧に近い２つの電圧の比較器として用いられる１対の差動増幅器である。比較器の出力は論理ＸＯＲゲートに与えられる。論理ＸＯＲゲートは、比較器出力の１つが真のときだけ真と評価する（図１２参照）。

図５は、本発明の或る実施の形態に係る乱数を発生させる方法を示す流れ図である。まず、予め決められた電圧レベルを生成して双安定回路に入力する。双安定回路をオンにして、安定状態に切り換わるのに要した時間を測定する。次にこの時間を評価して、予め決められた値より長いかどうか調べる。この値より長い場合は、回路は最初準安定状態にあったので安定状態への切換えは熱雑音によるものであった。したがって安定状態はランダム・プロセスにより生成されたものであり、ランダム出力値として用いることができる。この値より長くない場合は、この転換された状態をランダム値として用いずに、この転換された状態が予め決められた値より長い時間で達成されるまでこのプロセスを繰り返す。

特定の実施の形態に係る真の乱数発生器（ｔＲＮＧ）の概要を以下に示す。
以下に提案する準安定に基づくｔＲＮＧは高いエントロピーを達成し、また出力ビット値に関わらず、転換時間を測定して準安定事象のランダム性の等級付けを行うことによるＮＩＳＴランダム性テストに合格する。これにより、準安定のときの元の雑音レベルを決定して、最大ランダム性になるように自身を調整することができる。完全な集積ｔＲＮＧが、０．０３６ｍｍ^２での０．１３μｍ技術で製作され測定された。

真の乱数発生器（ｔＲＮＧ）はランダム性の物理的ソース（例えば、熱雑音、電信雑音）を用いてランダム・ビット・ストリームを生成する。しかし、これらは電源雑音、プロセス変動、または故意の攻撃などの望ましくない決定性雑音に非常に敏感である。以下に示す乱数発生器は準安定性に基づくｔＲＮＧを提供する。これはかかる決定性事象に対抗し、またシステムの実際のランダム性に従って出力ストリームに資格を与えることができる。

ｔＲＮＧ法は、生成された出力ビットを観察せずに準安定動作を制御する。すなわち、各準安定事象の転換時間を記録する（出力が０か１かに関係なく）ことにより、システムは準安定のときの元の雑音レベルおよび事象のランダム性を決定することができる。これにより、出力ビットの質の「等級付けを行ない」また最大ランダム性になるようにシステムを調整するのを制御することができる。また提案された方法により、ユーザはビット・ストリームの質とビット生成率とを妥協（トレードオフ）させることができる。完全な集積ｔＲＮＧが０．０３６ｍｍ^２での０．１３μｍ技術で製作された。生成されたビット・ストリームは高いエントロピーを達成し、補正器の助けを借りずにＮＩＳＴテストに合格した。

ｔＲＮＧは準安定状態の近くで動作するラッチを用いる。準安定状態では素子の熱雑音により最終状態が反転してランダム出力値を生成する。しかし最初のラッチ電圧が準安定点にない場合は、ミスマッチまたは外部雑音のためにラッチは決定性出力値を有することがある。本発明の方法は、準安定事象のランダム性はラッチが転換するのに要する時間を測定することにより決定できると考える。転換時間はｔ_ｄ＝τ_ｒ・ｌｎ（Ｋ_ｆ／ΔＶ_ｉ）とモデル化することができる。ただしτ_ｒおよびＫ_ｆは素子および回路に依存する定数、ΔＶ_ｉは準安定点からの初期電圧差である。

ΔＶ_ｉは２つの成分を有する。すなわち、決定性電圧差ΔＶ_ｄ（例えば、外部雑音、電源雑音など）および熱ランダム雑音Ｖ_ｎであって、ΔＶ_ｉ＝ΔＶ_ｄ＋Ｖ_ｎである。ｔ_ｄを観察することにより元の電圧差ΔＶ_ｉを計算することができる。ＭＯＳ半導体素子内の熱雑音を、平均が０で分散がσ^２＝４ｋＴγｇ_ｍΔｆの正規ランダム変数とモデル化できるとすると、最終の準安定結果を熱雑音で規定する確率を計算することができる。これを図６に示す。図６では、ΔＶ_ｄの異なる値について準安定システムの繰返しシミュレーションを行った。

ΔＶ_ｄ＞＞Ｖ_ｎのとき、システム内は決定性雑音が優勢なのでランダム・ビット反転の確率が低く、そのためにｔ_ｄの平均および分散（ｔ_ｄ（バー）およびσｔ_ｄ）は小さい。ΔＶ_ｄが小さくなるに従ってシステム内は熱雑音が優勢になるので、ランダムな結果の確率とｔ_ｄ（バー）およびσｔ_ｄが増加する。したがって、ｔ_ｄの統計を評価することにより、ラッチを調整して準安定動作にすることができる。またΔＶ_ｄ≒Ｖ_ｎのときは、個々の準安定事象のｔ_ｄ値を用いて出力ストリームを更に濾波することができる。図６に示すように、ｔ_ｄ濾波しきい値を高くすると、ビット生成率は低くなるがランダム・ビット反転の確率は高くなる。

ｔＲＮＧの制御および等級付けシステムを図７に示す。動作には２つの要素がある。すなわち、サイクル毎のラッチによる出力ビットの生成（これは等級付けしてメモリ内に記憶する）と、準安定制御に用いる転換時間統計の計算とである。図８に示す準安定ラッチは、供給電圧をＶ_ｄｄの半分に落としかつＥＱ、バイアス、および開始信号を表明して出力ノードを等しくすることによりリセットされる。次に制御モジュールがノードｑに電荷を誘導するとラッチは準安定になる。電荷注入回路は容量結合を用い、０．２５から１００ｆＦの範囲のコンデンサのアレイから成る。電荷の注入により、ノードｑの電圧は１０μＶの分解能で１６ｍＶだけ変えることができる。しかし、１２０μＶの制御分解能を持つシリコンでは、ｔ_ｄに基づく濾波を用いるとラッチは十分準安定動作になって、資格のあるランダム出力が得られることが分かった。電荷注入の後、供給電圧を全Ｖ_ｄｄに回復しかつ「開始」を表明するとラッチは活動化する。次にラッチ出力はその最終状態に転換し、１対の相補形比較器（図１２）を用いて「停止」信号を生成する。図９は、準安定ラッチおよびその出力を制御する信号の時間的挙動を詳細に示す。

時間・ディジタル変換器（ＴＤＣ）を用いてｔ_ｄを決定する（図８）。これは２つの部分から成る。すなわち、５０ｐｓの分解能を有する精密カウンタと、ＴＤＣの範囲を２０ｎｓに拡張する粗カウンタとである。精密カウンタは開始信号の遅延信号でクロックされるフリップ・フロップのアレイを含む。カウンタは「停止」信号を離散時間でサンプリングして、「開始」と「停止」の時間差の量子化値を持つ温度計コードを作る。粗カウンタは、遅延した開始信号がリングを回るたびに表明される。

ラッチを調整して準安定にするために、制御アルゴリズムはｔ_ｄの平均値ｔ_ｄ（バー）を最大にする。図１０は、注入電荷を掃引するに従って１２８サンプルの集合について測定されたｔ_ｄの分布と、関連するｔ_ｄ（バー）の値とを示す。予想したように、システムを準安定点（約６０４ｍＶ）の下または上にバイアスするとｔ_ｄ（バー）およびσｔ_ｄは小さくなり、全てが０または１の偏ったビット・ストリームになる。システムが準安定に近づくと、ｔ_ｄ（バー）は急速に大きくなって制御フィードバックが良くなる。更に、ｔ_ｄの分散も大きくなり、また出力ストリーム内の０と１の百分率は５０％に達する。１０℃から６０℃の測定範囲で、ｔ_ｄの統計的特性および０／１の分布も温度と共に非常に良く追跡できる。

図１１は、決定性雑音に応答するときのテスト・チップの制御アルゴリズムの動作を示す。平均ｔ_ｄの値を最大にするように制御モジュールの設定を変えたときの平均ｔ_ｄをプロットした。システムは１０回の繰返しの後で準安定動作に固定された。１１５回の繰返しのとき、Ｖ_ｄｄトレースで示すように電源の供給電圧を５０ｍＶ下げた。誘導された雑音のために準安定点がシフトすると、平均ｔ_ｄは５ＴＤＣ単位以上も大幅に減少する。制御の設定を調整するとシステムは１０回の繰返しで応答して、平均ｔ_ｄの新しい最大値で安定する。電圧低下のために起こる駆動力の低下により、新しい安定動作点のｔ_ｄは一層高くなる。一定のｔ_ｄしきい値で濾波したときのシステムの効率はｔ_ｄの挙動に良く追従するので、ｔ_ｄの値が低い事象では更に多くの濾波が必要であることが分かる。

本発明の例示の実施の形態について添付の図面を参照して詳細に説明したが、理解されるように、本発明はこれらの実施の形態に限定されるものではなく、添付のクレーム規定されている本発明の範囲と精神から逸れない限り、当業者は種々の変更および修正を行ってよい。

本発明の或る実施の形態に係る双安定回路と、各インバータの入力電圧と出力電圧との差を示すグラフを示す。図１の双安定回路をトランジスタ形式で示す。本発明の或る実施の形態に係る回路を示す。本発明の或る実施の形態に係る双安定回路および電圧制御回路を示す。図４ａの電圧制御回路を詳細に示す。図３の時間測定回路を詳細に示す。乱数を生成する方法を示す流れ図である。電圧差に対する転換時間の統計的特性を示す。サイクル毎のランダム・ビット生成モジュールと制御および等級付けモジュールとを備える乱数発生器のブロック図を示す。準安定ラッチ、停止信号生成、および時間・ディジタル変換器回路を示す。準安定ラッチとその出力を制御する信号の時間的挙動を示す。双安定回路の平均転換時間の分布を示す。同調アルゴリズムを示す。相補形比較器回路を示す。

符号の説明

５乱数発生回路
３０双安定回路
５０時間測定回路
８０電圧レベル制御回路

Claims

ランダム出力値を生成する回路であって、
双安定回路であって、０または１を出力する２つの安定状態を有し、また０と１の間の浮動値を出力する平衡準安定状態を有し、スイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し、前記状態は前記双安定回路のポートの電圧レベルに依存する双安定回路と、
前記双安定回路の前記ポートの電圧レベルを制御するための電圧レベル制御回路と、
スイッチ・オンの後で前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する切換え時間を測定するための時間測定回路と、
制御論理であって、前記時間測定回路、前記電圧レベル制御回路、および前記双安定回路のスイッチ・オンおよびオフを制御し、以下のシーケンス、すなわち、前記電圧レベル制御回路を制御して前記双安定回路の前記ポートを或る予め決められた電圧レベルに設定し、前記双安定回路をスイッチ・オンし、測定した切換え時間を検出し、前記双安定回路をオフにするというシーケンスを実行し、前記測定した切換え時間が或る予め決められた値より長い場合は前記双安定回路の前記転換した安定状態を前記ランダム出力値として出力する制御論理と、を含み、
複数の連続したシーケンスについて前記測定した切換え時間が前記予め決められた値より長くない場合は前記制御論理はリセット操作を行い、前記リセット操作では、前記双安定回路の前記ポートの異なる設定電圧レベルについて前記シーケンスを複数回実行し、また前記リセット操作中は前記転換した安定状態を出力せず、前記リセット操作の後に、前記制御論理は前記予め決められた電圧レベルをリセットして、前記リセット操作中の最も長い平均切換え時間を出力した電圧レベル値にする、
ランダム出力値を生成する回路。
前記制御論理は前記シーケンスを連続的に実行して複数のランダム出力値を出力する、請求項１記載のランダム出力値を生成する回路。
前記リセット操作中は、前記制御論理は、最初およびその後のシーケンスの集合について前記平均切換え時間が増えるように前記設定された電圧レベルを或る予め決められた量だけ修正し、次にシーケンスの別の集合について前記設定電圧レベルを前記予め決められた量だけ修正し、これを前記平均切換え時間が減少するまで行う、請求項１記載のランダム出力値を生成する回路。
前記リセット操作中は、前記制御論理はスイッチ・オンのときに設定した前記電圧レベルを修正して前記平均切換え時間を前のシーケンスに比べて長くし、前記平均切換え時間が前記予め決められた値を超えると前記電圧レベルを前記予め決められた電圧レベルとして設定する、請求項１記載のランダム出力値を生成する回路。
前記予め決められた値は前記回路内のデータ記憶装置内に記憶する、請求項４記載のランダム出力値を生成する回路。
前記予め決められた値は前記制御回路が較正操作を行ったときに生成され、前記較正操作は異なる設定電圧レベルについて前記転換した安定状態を出力せずに前記シーケンスを複数回実行して最も長い平均切換え時間を決定することを含み、前記制御回路は前記最も長い平均切換え時間を生成した前記電圧レベルに前記電圧レベを設定して更なるシーケンスを複数回実行し、前記制御回路は前記更なるシーケンスが生成した前記転換した安定状態を分析して、スイッチ・オンのときに前記ラッチが前記準安定状態にあるかどうか判定し、そうであれば前記別のシーケンスの前記最も長い平均切換え時間を前記予め決定された値として記憶する、請求項１記載のランダム出力値を生成する回路。
前記分析によりスイッチ・オンのときに前記ラッチが前記準安定状態にないと判定した場合は、前記回路は誤り表示を出力する、請求項６記載のランダム出力値を生成する回路。
前記回路は別のポートを備え、前記ポートおよび前記別のポートは前記出力値を出力し、前記電圧レベル制御回路は、前記別のポートに一定電圧を与えまた前記ポートに前記設定電圧レベルを与えることによりスイッチ・オンのときの前記ポートと前記別のポートとの電圧差を制御する、請求項１記載のランダム出力値を生成する回路。
前記双安定回路は交差結合インバータ対を備える、請求項１記載のランダム出力値を生成する回路。
前記双安定回路に高電圧レールおよび低電圧レールから電力を供給し、前記制御回路は前記高電圧レールおよび低電圧レールに電圧差を与えることにより前記双安定回路をオンにし、前記電圧レールのそれぞれに前記電圧差の半分の等しい電圧を与えることにより前記双安定回路をオフにする、請求項１記載のランダム出力値を生成する回路。
前記時間測定回路はカウンタを備え、前記カウンタは前記双安定回路の漸進的に遅延するスイッチ・オン信号によりそれぞれクロックされるフリップ・フロップの一連のアレイで構成し、前記カウンタは前記双安定回路が安定状態に切り換わったことを示す信号を受けると停止する、請求項１記載のランダム出力値を生成する回路。
前記ランダム出力値は複数回生成され、前記複数のランダム出力値は乱数として出力される、請求項１記載のランダム出力値を生成する回路。
その出力を互いに並列に配置した、複数の請求項１記載の回路を備える乱数を発生する回路。
ランダム出力値を生成する方法であって、
（１）予め定められた電圧レベルを生成して前記電圧レベルを双安定回路に入力し、前記双安定回路は０または１を出力値としてそれぞれ生成する２つの安定状態を有し、また０と１の間の浮動出力値を持つ平衡準安定状態を有し、前記双安定回路はスイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し、前記双安定回路の前記状態は前記入力電圧レベルに依存するステップと、
（２）前記双安定回路をスイッチ・オンするステップと、
（３）前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する時間を測定するステップと、
（４）前記時間が或る予め決められた値より長い場合は前記転換した状態を前記ランダム出力値として出力するステップと、を含み、
予め決められた回数の連続的なシーケンスについてステップ（４）で測定した前記切換え時間が前記予め決められた値より小さい場合は、前記方法は以下のステップを含むリセット操作を実行する、すなわち、
（１ａ）別の電圧レベルを生成して前記電圧レベルを前記双安定回路に入力するステップと、
（２ａ）前記双安定回路をスイッチ・オンするステップと、
（３ａ）前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する時間を測定して前記双安定回路をスイッチ・オフするステップと、
（４ａ）前記ステップ（２ａ）と（３ａ）とを複数回繰り返して平均切換え時間を決定するステップと、
（５ａ）異なる入力電圧レベルについてステップ（１ａ）から（４ａ）を繰り返すステップと、
（６ａ）最も長い切換え時間を与える生成された電圧レベルを決定して、前記予め決められた電圧レベルを前記決定された電圧レベルに設定するステップと、
を含む、
ランダム出力値を生成する方法。
前記方法のステップ（２）から（４）を継続的に実行して複数のランダム出力値を出力することを含む、請求項１４記載のランダム出力値を生成する方法。
前記リセット操作中は、生成された前記電圧レベルをステップ（５ａ）で実行した各繰返しで予め決められた量だけ変え、前記電圧レベルはまず前記平均切換え時間が増加するレベルであり、前記繰返しは前記平均切換え時間が減少するまで更に多数回実行する、請求項１４記載のランダム出力値を生成する方法。
前記リセット操作中は、前記ステップ（５ａ）はステップ（１ａ）で生成された前記電圧レベルを修正して前記平均切換え時間を前のシーケンスのセットに比べて長くし、前記平均切換え時間が前記予め決められた値を超えるとステップ（５ａ）をそれ以上繰り返さずにステップ（６ａ）を実行する、請求項１４記載のランダム出力値を生成する方法。
ランダム出力値を生成する手段であって、
双安定手段であって、０または１を出力する２つの安定状態を有し、また０と１の間の浮動値を出力する平衡準安定状態を有し、スイッチ・オンすると前記準安定状態から前記安定状態の一方に転換し、前記状態は前記双安定手段のポートの電圧レベルに依存する双安定手段と、
前記双安定手段の前記ポートの電圧レベルを制御するための電圧レベル制御手段と、
スイッチ・オンの後で前記双安定回路が前記準安定状態から前記安定状態の一方に切り換わるのに要する切換え時間を測定するための切換え時間測定手段と、
制御手段であって、前記電圧レベル制御手段、前記切換え時間測定手段、および前記双安定手段のスイッチ・オンおよびオフを制御し、以下のシーケンス、すなわち、前記電圧レベル制御手段を制御して前記双安定手段の前記ポートを或る予め決められた電圧レベルに設定し、前記双安定手段をスイッチ・オンし、測定した切換え時間を検出するというシーケンスを実行し、前記測定した切換え時間が或る予め決められた値より長い場合は前記双安定手段の前記転換した安定状態を前記ランダム出力値として出力する制御手段と、
複数の連続したシーケンスについて前記測定した切換え時間が前記予め決められた値より長くない場合は前記制御手段はリセット操作を行い、前記リセット操作では、前記双安定手段の前記ポートの異なる設定電圧レベルについて前記シーケンスを複数回実行し、また前記リセット操作中は前記転換した安定状態を出力せず、前記リセット操作の後に、前記制御手段は前記予め決められた電圧レベルをリセットして、前記リセット操作中の最も長い平均切換え時間を出力した電圧レベル値にする、
ランダム出力値を生成する手段。