ダイオードノイズを利用した乱数発生の問題点と改良

NDC

ダイオードノイズを利用した乱数発生の問題点と改良

岸本俊祐＊ 赤田和美†

1理朧鴨麗掘…踏藩盈謙。鍛鯉2呈h島y叢諮

Shunsuke KlsHiMoTo  and Kazumi AKADAt

 To use good random numbers in quality for personal computers at any time， about 1 × 109 random digits were generated by a conventional way． They were generated depending on the randomness of the number of the shot−noise which occured in a Zener diode during a constant time． But， the digits had a little distortion and did not pass the statistical tests of randomness． So， the way of generating digits was changed to improve the randomness of the digits． ln the new method， two biased digits were converted into one random digit． The new digits got good statstical quality．

le

はじめに

 パソコンを用いたコンピューティングにおいて、

「乱数」はなくてはならないソフトウェアリソース の1つになった。特に、インターネットの発展で 高度なセキュリティが問題となるような情報を扱 う場合には乱数使用が必須である。そのため、パ ソコンの最も基本的なハードウェアであるマザー ボードのバスを制御するチップセットの中に、そ れを発生させる機能を組み込んでしまう試みがな

されようとしているほどである1）。

 しかし、現用のパソコンで利用できる乱数とい えば、アプリケーション開発用プログラミング言 語の中に用意されている乱数発生関数やサブルー チンによるものがほとんどである。それは「算術 乱数」と呼ばれ、簡単な漸化式をくり返し演算：す ることによって得られる。ソフトウェアのみで発 生できるので手軽ではあるが、もともと規則性の あるアルゴリズムにより無規則なものを発生させ ようとするところに矛盾があり、得られた乱数列 は品質があまりよくない部分を含んでいる。その 中で、乱数の並びに周期が現れることや各乱数の 独立性が保証されないこと等は致命的な欠陥で、

これを考慮なしで数値実験等へ応用することへの 警告がなされている2）。

 そこで、筆者らはパソコンで品質の保証された 乱数をいつでも安心して使うことができるように するため、「物理乱数」の発生に取り組んできた。

物理乱数は、ランダムな自然現象を でたらめさ

ウ情報工学科

†情報工学科卒業生、現在豊橋技科大大学院

平成11年8月31日受理

の根拠としてハードウェアで発生させるため、ハー ドウェアさえきちんと動作させれば、原理的に良 質の乱数をいくらでも発生できる可能性がある。

まず、自然界における典型的なランダム現象であ る放射性元素の自然崩壊を雑音源にして、それが 生起する時間間隔のランダムさをもとに乱数を発 生させる新しい方法を考案した。そして、その方 法を実現する電子回路の開発を行い、実際、良質

を構築した3）4）5）。

 しかし、雑音源として用いる放射性元素は取り 扱いに格段の注意を要し、また、放射線検出装置 等余分な装置が必要である。何よりもパソコン利 用の手軽さに比べ、その不便さは否めない。そこ で、次の雑音源として、半導体ダイオードの熱雑 音に注目した。この雑音は自然界における典型的 なホワイトノイズ源として良く知られ、その発生 も特別な装置は不要で容易である。そこで、一定 時間に発生するホワイトノイズの数のランダムさ

を根拠に乱数発生を試みてみた。この方法による

行われているので6）、最近の電子素子を用いた発 生回路を新たに設計しなおして追試を行った。そ の結果、得られた乱数は、乱数としての必要十分 条件の内、各乱数発生の等確率性（一様性）に関

しては統計的にほぼ満足できるレベルにあるもの の、独立性に関しては条件を満たすことができな い等問題があることがわかった。

 そこで、従来の発生方法に改良を加えてその問

題点を克服し、より高品質の乱数が得られるよう

にしたので報告する。

2． 乱数発生の原理と方法

2．1 発生原理

 一定時間内に発生する物理現象の数のランダム さを利用して乱数を発生させる方法は、古くから 多くの試みがなされている。その中で、最も簡単で 比較的特性の良い乱数が得られるものとして、以 下の方法がある。つまり、物理現象を反映させて頻 度の高いランダムパルスを発生させ、それをn進 の電子カウンタで十分オーバーフn一させながら 計数する。そして、計数値の最下位桁のみを読み出

し、それをn進1桁の整数乱数とする。この発生方 法は、オーバーフローが多いほど一様性の良い乱 数が得られる。それを数学的に解釈すれば、任意の 整i数m（m》n）をnで割った余りを求めているこ

とに相当するので、各乱数r（r＝0，1，2，．．，n一一1）

が生ずる確率の一様性については、理論的に計算 することができる。一定時間内に発生するランダ ムパルス数mの分布が標準偏差σの正規分布、も しくはそれに近ければ、各乱数rの発生確率p（r）

の1／nからのずれの最大相対誤差は

c， ＝ nP（r） 一 1 ± 2exp（一

      ）

（1）

で実質上評価できることが示されている7）。

 ランダムノイズ発生回路や計数時間を調整して、

σを10以上にすることは比較的容易である。例 えば、n＝10、σニ10として（1）式を評価し

てみると、Cr＝5×10『9となり、このような簡単 で単純な方法でも、ハードウェアがきちんと動作 しさえずれば、一様性の十分良い整数乱数列が得 られることがわかる。

2．2 乱数発生回路

 乱数発生回路の基本構成をFig．1に示す。まず、

ノイズ信号源は、ツェナー電圧が9V前後のツェ

ナーダイオードに適当な逆バイアス電流を流すこ

ショットノイズを発生させた。そしてそのノイズ を含んだ逆バイアス電流を小信号用トランジスタ のベースに直接流し込み、増幅を行って数Vppの 電圧出力のノイズ信号を得た。

 ノイズ信号の中で、極端に速く変化する高周波 成分は、後段に続くゲートやカウンタ等のデジタ ル論理回路を誤動作させる可能性があるので、遮

バタワース型ローパスフィルタを通し、高周波領 域を取り除いた。また、ダイオードからは1／ノノ イズも同時に発生するが、このノイズは乱数発生 にとっては好ましくない。幸いこのノイズは、極 低周波領域でそのパワーエネルギーが顕著である

Noise

唐盾浮窒モ

Amp．＆

@ LPF COMP

Personal

bomputer Counter Gate

Fig． 1 Block diagram of a random digit

    generation．

ため、信号源とフィルタとを交流結合にして、そ のノイズを直流成分に近い信号と共に取り除いた。

REF tO．O dBm 10dB／

AVG A 16 AVG A TI  16

RBW

30 kHz

10 kHz swp

2．0 s

9陀。τ露漏    箆＝ ag． oooo馳陶   73 ・39．72●▼

       6

рa飢

16

㎜■●冒

P0

香B

●      ㎜       L，縛      60し陶

START 100 kHz STOP 100 MHz

Fig． 2 Power spectrum of the diod noise．

 Fig．2にローパスフィルタを通過した後のノイズ 信号の周波数特性を示す。40KHzまでと100K：Hz 以上に分かれているのは、1つの測定器で全周波 数領域をカバーできなかったためである。両分布 とも測定周波数範囲で16回スキャンした平均値が

な特性で、この間のノイズ信号は白色性を持つと

 Fig．1に示したCOMPはゼロクロスコンパレー

タで、アナログのノイズ信号を2値化し、デジタル パルス信号に変換する。それを10進1桁カウンタ で400μ秒間計数することにより、毎秒2，500個 の割合で乱数を発生させた。乱数発生時と同じ条 件の時に、カウンタに入力するランダムパルス数 は、平均約9×105パルス／秒であった・また、400 μ秒間の数の分布をFig．3に示す。これは、400μ 秒間ずつ106回測定したものである。パルス数分 布の平均値はm＝382．5で、この分布を正規分布 と見なしたときの標準偏差はσ＝24．5であった。

m》10を十分満たしており、またこの条件で（1）

式を評価してみると、Cr＝7×10｝52となり、カ

ウンタに入力するパルス数としては十分であると

ダイオードノイズを利用した乱数発生の問題点と改良 岸本・赤田

0

O O O 8

00 0 6

0 0 0 4

0 0 0 2

0  00  00  00  60 0  00  0∩U  O齢0  4 0  0

0 20

♂c雪9﹂﹂

§霧§§§§§§§§§睾§§睾§

The number of the putses per 400  seo．

Fig． 3 The distribution of the random pulse     number for 400 pt sec．

いえる。

 以上の実験条件の下で、およそ1×109個の10

進整数乱数を発生させ、パソコンのハードディス

3。 発生乱数の統計的検定

 乱数として必要十分条件は、各乱数出現に対す る等確率性（一様性）と無規則性（独立性）であ る。それぞれについて様々な検定方法が提案され ているが、今回発生した乱数が10進1桁の整数型 乱数であることから、それに最も適した検定法と して、つまり、検定のためにわざわざ余分な変換 等を行わなくてよい方法として、一様性の検定に はそのものずばりの「度数検定」を、無規則性の 検定には「ギャップ検定」を取り上げた。

 いずれの検定も、ある仮説のもとで条件を付け て乱数を集計し、その集計度数分布と、乱数が理 想的な特性を持つ場合に確率的に期待される理論 的度数分布との「適合度」をx2検定によって調べ るものである。具体的には以下のように行う。今、

ある条件のもとにN階級に分けて集計したとき

の各階級の実測度数をni、それに対応する期待度

数をfi（i ＝1，2，．．。，1V）とすると、検定統計量は

ア

ゐ

η

一

︵ あ

NΣ圖

㌧

で与えられる8）。実測度数の分布と理論的に期待 される度数分布がずれていればいるほどそれに見

値（有意水準、または、危険率という）を設けてお

き、（2）式から得られるX2値がそれより大きくな れば、両分布は合っていないと判断するのである。

3．1 度数検定（一様性検定）

 発生した1×109個の乱数全体にわたって、0か ら9までの乱数がそれぞれいくら出現したか、そ の出現度数を集計した。その結果をFig．4に示す。

1．0005E＋08

 1．0000E＋08

♂

⊆ 

剥

す

L

 9．9850E＋07

9．9800E＋e7

Ot23456789

    Random Digit

Fig． 4 The histogram of the total frequencies      of each digit．

 もし、各乱数の出現確率が一様であるとすると、

各乱数の出現確率は全体の1／10で期待度数はfi＝

1×108個となる。この値とそれぞれの階級の観測度 数を（2）式に入れてX2値を計算すると、X2＝1L1

となった。集計階級の数は10階級なので、この 値の分布は自由度9のx2分布で表されることに

なる。自由度9の）（2分布で有意水準5％の棄却 域はλ12＞16．9である。実測値はその中に入って おらず、観測度数分布は出現確率1／10の一様分 布をしているとしてよいという検定結果になった。

つまり、各度数の凸凹の程度は、本来でたらめで あるが故の「ゆらぎ」の範囲であり、統計的に許 容できる範囲である。しかし、この図から明らか なように、0を含めた偶数乱数の方が奇数乱数よ

り多少多めに出現している系統的な偏りが見て取

れる。

3．2 ギャップ検定（無規則性検定）

 乱数列の中で、ある乱数Rに着目し、それが出

以外の乱数の個数をギャップgと定義する。今、0 から9までの数字がまったくでたらめに並んでい るとすると、最初の数字がRである確率は1／10、

次に続く数字がRでない確率は（1−1／10）だか ら、ギャップgが生ずる確率は

      1． 1

      p（g） ＝： ii6（1−fo）g ， （3）

となる。

 今回発生した109個の整数乱数列の中で、R＝3

とR＝8に対するギャップがどのように分布してい

るか調べた。R＝3の場合の結果をFig．5に示す。

1．2E＋07

1．OE＋07

〉， 8．OE＋06：

睾6，0E．。6

罫

O，OE＋OO

囮Ob騒orv●d

；；；．撃碁．山止卓．．

︷ 韮

⁝

葦

0  2 4 6 S le 12 14 16 IS 2e 22 24

    Gap g

Fig． 5 The histogram of the gap test．

 LOε◆07  9，8【go6

 9．5Ego5  きト ピリ  台，。、，。6

5

弓9 OE◆05

』 E◆06

：：：：：：：

：：：：：：：

O    t    2

 Gap

Fig． 6 Part magnification of the Fig．5．

 Fig．5の実線は（3）式から計算される理論度数 で、一見、観測された度数分布は理論度数分布に 良く合っているように見える。しかし、それは縦軸 の目盛りが両分布の偏差に比べて粗すぎるためで あり、実際、Fig．6に示すように先頭の3つのデー タのみを拡大表示してみると、実測度数分布は理 論度数分布と比べ一方的に小さい方に偏っている。

 Fig，5に示したように、9を0から1ずつ24ま でと25以上の26の階級に分け、自由度25のX2

分布で、両度数分布の適合度を検定してみた。こ のデータの場合、得られた値はX2＝418となった。

自由度25の）（2検定で、有意水準5％の棄却域は X2＞37．7であり、実測値はそれより極端に大き い。したがって、各乱数がまったくランダムに（独 立に）出現しているという仮説は成立しない。

 ともあれ、度数検：定での偶数乱数の方が多く出 現しているという偏りといい、ギャップ検定がパ スできないことといい、この乱数列が乱数として 好ましくない歪みを持っていることがわかる。

4．乱数の組み合わせによる良

      質化

 3．で行った検定により、集録した乱数に好ま しくない系統的な偏りが存在することがわかった。

それは、おそらくカウンタを構成しているフリッ プフロップ回路が、同じ入力パルスに対して、0 状態から1状態に遷移するしきい値とその逆状態 への遷移に対するしきい値との微妙なちがいによ り、わずかに異なって応答しているためと思われ る。しかし、この応答動作の非対称性は、程度の 差はあるもののどのカウンターCにも存在し、偶 然完壁なICに当たらない限り、ユーザーがそれ を回路的に調整することは不可能である。そこで、

ハードウェア的な改良はあきらめて、それで得ら れた偏りを持つ乱数をソフトウェアで操作し、そ の偏りを軽減する方法を考えた。もし、系統的な 偏りの原因が、カウンタを構成するフリップフロッ プ回路の状態遷移動作の非対称性によるものであ れば、以下の操作でそれによる歪みの軽減が可能

である。

 偶数乱数が得られたときのカウンタの最下位ビッ トは0に、奇数が得られたときは1となっている

乱数を2つずつ「くくり合わせ」て、最下位ビッ トどうしの和をとり、1ビット目のみを取り出す

とすると、

        O＋O−O： p2         0＋1−1： pq         1＋O 1： qp         1＋1 O： q2

であるから、くくり合わせの結果が0となる確率

間の偏差をEとし、P＝ O，5＋c、q＝1−P＝0．5一ε とおくと、

       p2 十 q2 ＝ O．5 十 2c2          2pq ＝ O．5 一 2c2

となり、くくり合わせを行った結果の偏りは元の 偏りの2次の微小項となる。

 偶数、奇数乱数出現の一様性に対し、どれくら い改善されるか半定量的に見積もってみる。例え ば、Fig．4に現れている偶奇の度数の相対偏差は、

各度数に統計的なゆらぎによる度数の増減が重畳

されていて、はっきりした値はわからない。Fig．4

程度となっている。一方、統計的な度数のゆらぎ

の程度は、度数分布がポアソン分布をすると仮定

すれば1×10−4ほどで、仮に、統計的ゆらぎを

ダイオードノイズを利用した乱数発生の問題点と改良 岸本・赤田

除いた相対偏差が最悪その値の2倍（統計的ゆら ぎが偏りをキャンセルする方向で重畳されている と考えた場合）としても、e＝3．2×10−4程度、

2〜＝2．Ox10−7程度となる。

 統計的なゆらぎの程度1x10｝4に比べ、3．2×

10−4はその3倍程度で度数分布に大きな影響を与 え、20×10−7は十分小さくほとんど問題になら ないことがわかる。つまり、発生したままの素乱 数では出現の一様性に対し見過ごすことのできな い偏りが存在し、改良後はその偏りが十分小さく なり無視できることがわかった。

 そこで、続けて発生した10進1桁乱数を2個ず

っくくり合わせ、1桁のみを採用するという方法 で新たに1×109個の乱数を発生させた。

5． 良質化後の検定

5．1 一様性検定と一様性のゆらぎ

 くくり合わせ法を適用して新たに得られた1×

109個の1桁整i数乱数について、3．1で示したの

t．OOOOE＋08

g 9．9950E＋O？

毎

コ

尾コ脚@9．9900E＋07

Le

 9．9850E＋07

9SSOOE．07

01234567Sg

    Random Digit

Fig． 7 The histogram of the total frequencies     of each digit．

 今回は特に偶数乱数が多いという傾向は見られ ない。理論的一様分布との適合度検定におけるx2 値は8．9で、有意水：準5％の棄却域には当然入ら ない。また、この乱数列の一様分布のゆらぎの分 布が統計的に期待されるような分布になっている

万のブロックに分け、各ブロックの中でOから9

までの乱数がそれぞれいくら出現するか、その度 数を集計した。1つのブロックの中では各乱数が 出現する平均の期待度数は200個で皆同じなので、

一様分布を仮定して実測度数分布の適合度をx2検

分けて集計した結果をFig．8に示す。50万ブロック

却域に入るものは24924ブロックで、全体の4．98

％であった。ほぼ理論通りの値が得られた。

soooo soeeo 0 0 0 0 4

0 0 0 0 3

0 0 00 2

︾20コσoよ

10000

Fig． 8 0

 0  2  4  6  e

囲Obsorv●d

@  Ex octod

、 、       ≧2

10 t2 14 16 te 20 22 24

The histogram of x2−values for 5 × 105 blocks．

 この図で、実線は自由度9のx2分布から期待

される理論度数分布で、各乱数がまったくでたら めに発生しているとしたとき、出現度数が統計的 にゆらぐ結果現れる分布を示している。観測度数 分布はこの理論度数分布とよく一致している。ち なみに、両分布の適合度を自由度25のλ：2検定 で調べた。得られたX2値は28．9であった。自由

X2＞37．7であるから、棄却域に入らない。実測 度数分布は得られた乱数列が統計的に期待される ような一様性のゆらぎを適度に含んでいることを

5．2 ギャップ検定

 良質化後の乱数1×109個を3．2で行ったのと

全く同じ方法でギャップ検定にかけてみた。R＝3 に対する結果をFig．9とFig．10に示す。

1．2EfO7

1．OE＋07

あ ロゆロう お

9

雪6．OE．o⑤琶

L4．OEfO6

2．OE＋06

O．OE＋oo

塵画陪Ob50rv◎d

．tr＝EEEE！tegj，

1

0 2 4 6 8 le 12 14 16 18 20 22 24

  Gap g

Fig． 9 The histogra m of the gap test．

 この分布に対するX2値はX2＝14．9、また、同

転07

戦

印06 ひ06

● 5 ひ06

脳

』06 恥05

0 9

即06 恥

㏄

6酔 5

即06 4 8

印05

2 8

印06 0 8

＞OCO5σO﹂﹂

0   1   2

 Gap

Fig． 10 Part magnification of the Fig．9．

度25のλ12検定における有意水準5％の棄却域は X2＞37．7であるから、両実測値ともその中に含 まれない。したがって、検定結果はx2検定の元に なっている仮定、つまり、各乱数はまったくでたら めに（独立に）発生しているという仮定が正しい ことを示している。なお、R＝3に対するギャップ の総数は99999495個、最大ギャップは111、100 以上のギャップの出現確率は（3）式による理論値 が2．66×10−5のところ、実測度数は2679個で 実測出現確率は2．68×10−5であった。したがっ て、このデータも上記仮説が正しいことを支持し

ている。

 以上、良質化した乱数列は、一様性および無規 則性の両検定を同時にバスし、統計的に見てほぼ 理想的な乱数列と見なして良いことがわかった。

6． おわりに

 ツェナーダイオードから生ずる高頻度のショッ トノイズによるランダムパルスを、10進1桁のカ ウンタで桁あふれさせながら計数し、一定時間後 にカウンタに残った計数値を10進整数乱数とする

という、最も簡単な方法で多数の乱数を発生させ た。桁あふれが十分ならばこのような簡単な発生 方法でも、理論上一様性の良い乱数が得られるは ずであるが、実際得られた乱数は、「一様性」に関 する検定は統計的にはパスするものの、偶数乱数 の方が奇数乱数よりわずかに多いという系統的な 偏りが見られ、さらに、「独立性」に関する検定は 到底パスできない偏りのある乱数列であった。そ の偏りの原因は、カウンタを構成するフリップフ ロップの2つの状態間遷移のしきい値が1→0と 0→1で微妙に異なっているためと思われる。し かし、その値はカウンタのアナログ特性であり、

ユーザーが調整することは不可能である。

 そこで、得られた偏りのある乱数2個の和をと

り、それを10で割った余りを新たに1個の乱数と する「くくり合わせ」という加工を施してその偏

りを軽減した。その結果、一様性と独立性の両検 定を同時にパスするほぼ理想的な乱数列となった。

ほぼと多少の限定句を付けたのは、問題にならな いとはいえ、一様性に対し2〜＝2．0×10−7程度 の偏りを持つためである。

 109個という乱数は、ハードディスクにそれを 圧縮なしで記憶させれば1Gバイト以上にもなり、

本格的なシミュレーション等で使用しても十分な 量である。現在、どのパソコンでも容易に利用で

を進めているところである。

 終わりに、ランダムノイズの周波数分析にスペ クトラムアナライザーを使用させていただいた、

津山高専電気工学科西山宗弘教授、同機械工学科 高本洋祐教授に感謝いたします。

参考文献

1）ASCII：月刊アスキーJ23，6（1999）177−179．

2）吉沢康和、他：日本物理学会誌26，1（1978）23−

 26．

3） S． Kishimoto et al．： J． Japan Statist． Soc．，

 11， 2 （1981） 169−173．

4） S． Kishimoto： J． Japanese Soc． Comp． S−

 tatist．， 6 （1993） 67−73．

5） S． Kishimoto：J． Japanese Soc． Comp． Statist．，

 8 （1995）． 47−55．

6）石田正次、他：日立評論，54（1972）894−898，

7）仁木直人：統計数理研究所彙報，27，no．1

 （1980） 115−131．

8）東京大学教養学部統計学教室：自然科学の統計