セルオートマトンモデルによる擬似乱数の位相差の解析
M2004MM017
指導教員

伊藤 彰浩
伏見 正則
の検査用の擬似乱数の周期に近い長さの擬似乱数

1 はじめにでの検証が可能となり、高次化によって実用性を高める事が可能となる。

近年、VLSI（超大規模集積回路）の集積度が非常に高くなっていく中で、フォールトのチップをより効率的に見つけるという事が重要な課題となっている。そのような課題の下、VLSI の取りうる全内部状態の検査を行う事は事実上不可能なため、「疑似ランダムテスト」が用いられている。[2] を引用すると、具体的には以下のようになる。
ランダムパターン生成器から被検査用 VLSI にコント

3 フィボナッチ多項式
フィボナッチ多項式とは、フィボナッチ数列の多項式版
として 1960 年代に取り上げられたもので、以下の漸化式
により定義される。

比較しフォールトの判定をする。以上が処理の流れであFi (z) = Ai (z)Fi−1 (z) + Fi−2 (z)(F−1 (z) = 0, F0 (z) = 1)(1)
また、参考文献 [2] の中で、手塚・伏見両氏によって、漸化式 (1) において Ai (z)(i = 1, 2, · · ·) が z または z + 1 であるとして生成される GF(2) 上の多項式 Fi (z) を（GF(2)る。テスト時間を短縮するために、このテスト機能はチッ

上の）フィボナッチ多項式と定義されている。ただし、こプの中に組み込まれることが多く、これを Built-In-Self-の場合、Ai (z)(i = 1, 2, · · ·) は 2 通り（z または z + 1）のTest(BIST) と呼ぶ。この場合には、参照用 VLSI からの可能性があるので、フィボナッチ多項式は、列ではなく木

結果はあらかじめシミューレーションにより計算して蓄を生成する (図 1 参照)。

ロールおよびデータ信号が送られる。

それに対する出

力がコンプレッサーの中に圧縮されて溜められる。

十分な長さの入力を与えた後に、コンプレッサーの中に圧縮されてできた結果を正しい参照用 VLSI からの結果とえてしまうので、ハードウェアのオーバーヘッドになるの

1

は、ランダムパターン生成器とコンプレッサーの占める面z積であり、これを如何に小さく実現するかが問題となる。

z+1

この問題を解決するにあたり、ランダムパターン生成器
z 2 +1に用いられる擬似乱数の特性が、１つの重要な要素とな

z 2 +z+1

z 2 +z+1z2る。言い換えると、その擬似乱数を生成するのに用いられる原始多項式の選び方が重要と言える。これについて現z3

z 3 +z 2 +1

z 3 +z 2

z 3 +z+1

3
3
3
2
z 3 +z 2 +1 z +z z +z+1 z +z +z+1

在では、[1]、[2]、[6] に、その原始多項式の導出方法、入力となる擬似乱数の発生法が掲載されており、[3] に出力、

図 1: フィボナッチ多項式の木

16 次の原始多項式の出力結果が掲載されている。本論文
では、その VLSI の内部状態の検査をするために考えられた、「疑似ランダムテスト」に用いられる、混合型線形

また、1987 年に Mesirov と Sweet が GF(2) 上の多項式

セルオートマトン (以下 CA) の各セルの出力の位相差が、の対 (P (z)、Q(z)) に対して、証明した次の定理は本論文

VLSI の検査用の擬似乱数としての特性に与える影響について研究を行ったものである。具体的には、CA モデルでにとって非常に重要である。

発生させた擬似乱数の位相差について、同次ごとでの数学的な解析を行い、検査用の擬似乱数を生成する原始多項式の実用性について多角的に検証を行っている。

2 研究目的同次内のすべての原始多項式の導出、解析

任意の原始多項式から同次内のすべての原始多項式を導出し、次数ごとでの出力の位相差の解析を行い、VLSI の¶³

定理 1 Q(z) が GF(2) 上 の 既 約 多 項 式 の と き 、P (z)/Q(z)(ただし、P (z) の次数＜ Q(z) の次数) の連分数表現における部分商の次数がすべて 1 となるような P (z) が常に 2 つ存在する。
µ´
この定理から、GF(2) 上のすべての既約多項式はフィボ
ナッチ多項式である事がわかる。次にこの GF(2) 上のフィボナッチ多項式を応用し、VLSI テストに用いられる
CA モデルについて説明を行う。

検査に用いる上で、最も有用性の高い原始多項式を4 CA モデルの概要導出する。
高次の原始多項式の位相差の解析

可能な限り高次の原始多項式の解析を行う。これにより、VLSI テスト

CA 法とは、ノイマン（J.von Neumann）の有限オー
トマトン理論に起源をもつシミュレーション手法である。

この手法は従来のシミュレーション手法で対応できないような「複雑」な現象に多く用いられる。CA 法を具体的に述べると、直線状に並んだセルが、隣接する他のセルと¶³与えられた原始多項式を Fn (x) として、次式が成り立つように n 行 n 列の行列 B =(bij ) を定める。
nXの関係則によって経時的に変わるというものである (図 2参照)。

bij xj−1 = xi−1 + x2i−1 + x2i (modFn (x)) (8)j=1

C i-1 C it

GF(2) 上の方程式

C i+1

ai

By = (0, · · · , 0, 1)T

(9)

Ci

t+1

を解いてy=(1, q2 , · · · , qn )T を求める。(2 つ存在す
図 2: セルオートマトン

る。)

ここで、時刻 t における Ci の状態を xi (t) と書くと、次の式が成り立つ。

xi (t + 1) = xi−1 (t) + ai xi (t) + xi+1 (t)(mod2)(2)

Fn (x)(x−1 + q2 x−2 + · · · + qn x−n ) の非負冪部分を Fn−1 (x) とする。
Fn−1 (x)/Fn (x) の連分数展開の部分商 Ai (x) を求め、Ai (x) = x + ai を満たすように
ai (i = 1, · · · , n)

こ こ で 、式 (2) に 対 し て 、境 界 条 件 と し て 、x0 (t) =xn+1 (t) = 0、n をセルの個数とおくと次の方程式で示

(10)

を定める。

µ

す事ができる。

X(t + 1) = AX(t)(3)´

これにより、任意の原始多項式を特性多項式とする行列 A
を試行錯誤に頼ることなく、かつ、効率的に求められる。

T

式 (3) は、GF(2) 上の式で、X(t) = (x1 (t), · · · , xn (t))

は縦ベクトルを示している。また、A は次の (4) のような

5 CA モデルの出力生成アルゴリズム

3 重対角行列の形をしており、X の状態遷移行列 (statetransition matrix, 以下 STM) となる。


a1 1

 1 a2 1
1 a3 1



(4)
A=
..
.. ..


.
.
.



1 an−1 1 
1
an

5.1

式 (3) で、X(t) は n 次の 0-1 ベクトルであるから、X(t)xi (t)CA モデル
ここでは、与えられた行列 A によって、t ≥ 0 のすべての状態で、x1 (t) = xi (t+ji ) となるような整数 j2 , · · · , jn 、つまり CA の出力の位相差を計算するアルゴリズムを示す。
はじめに、x を n 個のセルの CA とし、1 ≤ i ≤ n, t ≥ 0の条件の下で、xi (t) の i はセルの番号を、t は時間を表しているものとする。その時に、t ≥ 0 での x の状態は、X(t) = (x1 (t), · · · , xn (t)) となる。以下が x の次の状態を決定する式である。(上の式は GF(2) 上の式とする。)=の周期は、2n − 1 を超える事はなく、特性多項式が原始=多項式の時に限り、最大周期になる事が知られている。こ=a1 x1 (t − 1) + x2 (t − 1)
xi−1 (t − 1) + ai xi (t − 1) + xi+1 (t − 1)

(i = 1)(1 < i < n)xn−1 (t − 1) + an xn (t − 1)

こで、(i = n)(11)

Pn (x) = det(xI + A)

(5)と定義する。Pn (x) は、余因子展開をすることにより再帰的に計算する事が可能である。

5.2 斉次線形漸化式
ここでは、CA モデルの出力の位相差解析アルゴリズ

Pk (x) = (x + ak )Pk−1 (x) + Pk−2 (x)(6)

ムを説明するのに用いられる数式についての説明を行う。

P0 (x) = 1, P−1 (x) = 0(7)数列 sm を生成する次の式 (12) は n 次の斉次線形漸化式

これら、(6)、(7) の式は、フィボナッチ多項式の漸化式であり、Mesirov-Sweet の定理から、任意の原始多項式 Fnと呼ばれている (本論文では、GF(2) 上で)。

sm+n = cn−1 sm+n−1 + cn−2 sm+n−2 + · · · + c0 sm (12)に対応する A が存在する。従来は、そのような条件を満足する行列 A を見つけるのは試行錯誤に頼っていたが、nが大きくなると効率が悪く、また、そのような A が任意のn に対して常に存在するかどうかもわかっていなかった。
しかし、参考文献 [2] で手塚・伏見が、Mesirov-Sweet のf or m = 0, 1, · · ·(12) の式で、cn−1 , cn−2 , · · · , c0 は、本論文では GF(2) の要素を表しているため、0 もしくは 1 となる。そして、この漸化式から定義される特性多項式が次の (13) である。

結果を用いて、これらの問題を簡単に解決している。 以
下が、A を求める具体的アルゴリズムである。

f (z) = z n − cn−1 z n−1 − cn−2 z n−2 − · · · − c0

(13)

また、特性多項式 f (z) の相反多項式 f ∗ (z) を、GF(2) 上

16で、式 (14) によって定義する。

1f ∗ (z) = z n f ( )
z

j 4=

4

4

3
22

(14)

1

続いて、1 ≤ i ≤ n に対して、次の式を定義する。

j 3=
n

20

j 1=

00

22

j 2=

30
30

2

Pi (z) = xi (0) + xi (1)z + xi (2)z 2 + · · · + xi (2n − 2)z 2 −2
(15)
P (z) = P1 (z)
(16)

1
j 5=

そして、上の多項式 (15) と (16) とおいたことにより、以下の (17) の式を導く事ができ、式 (17) を満たす整数

8j1 = 0, j2 , · · · , jn が存在する。
Pi (z) = z ji P (z)n(mod1 − z 2 −1 )図 3: z 5 + z 2 + 1 における位相差(17)

上記の整数 j2 , · · · , jn は、x1 (t) に対する x2 (t), · · · , xn (t)の相対的なシフトとなる。そして、以下の定理 2[3] から、

j2 , · · · , jn を計算するためのアルゴリズムを得ることが可

いくつかの原始多項式の出力の位相差を比べる上での方法としては、1 つ 1 つの原始多項式の 1 番小さい位相差を比較した際に、その中でもっとも位相差が大きいものを持能となる。

³つ原始多項式が、同次の中で最も有用性が高いものだと判断するという形で行っている。次数が 5 の原始多項式に定理 2 式 (11) で定義される GF(2) 上の n 次の CA
ついては、表 1 の出力結果（j の値）から、f4 の原始多項の原始特性多項式を f (z) とし、その相反多項式を¶式が最もよいという結論となっている。またこのような

f ∗ (z) とする。このとき、次の事が成り立つ。

位相差の解析をプログラムを用いて次数を高めていった

z ji (zai − 1) + z ji+1 +1 ≡ 0 mod f ∗ (z)(i = 1)

結果は、表 2 のようになる。

z ji−1 +1 + z ji (zai − 1) + z ji+1 +1 ≡ 0 mod f ∗ (z)(1 < i < n)z ji−1 +1 + z ji (zai − 1)

≡ 0 mod f ∗ (z)(i = n)
(18)

µ

n
5
6
7
´ 8

6 解析結果6.1 同次の原始多項式での解析の比較結果
ここでは、同次内のすべての原始多項式の出力の位相差を、次数ごとに比較した結果を示している。例として、次

9
10
11
12

数が 5 の原始多項式 (周期:25 − 1=31) を用いた出力結果
は、表 1 のようになる。
表 1: 5 次の原始多項式実行結果

f0
j1 · · · j5
f1
j1 · · · j5
f2
j1 · · · j5
f3
j1 · · · j5
f4
j1 · · · j5
f5
j1 · · · j5

z5 + z3 + 1
y1 : 0, 30, 3, 24, 25, y2 : 0, 30, 9, 5, 6
z5 + z3 + z2 + z + 1
y1 : 0, 19, 29, 21, 22, y2 : 0, 30, 7, 28, 9
z5 + z4 + z3 + z + 1
y1 : 0, 30, 5, 25, 7, y2 : 0, 18, 29, 23, 24
z5 + z2 + 1
y1 : 0, 30, 20, 4, 22, y2 : 0, 13, 29, 8, 9
z5 + z4 + z3 + z2 + 1
y1 : 0, 11, 29, 15, 4, y2 : 0, 11, 25, 7, 27
z5 + z4 + z2 + z + 1
y1 : 0, 30, 24, 28, 16, y2 : 0, 12, 8, 14, 15

表 1 より、図 3 のように位相差の計算が可能となる。

13
14
15
16
17
18
19
20
21

表 2: 位相差の解析結果

原始多項式z5 + z4 + z3 + z2 + 1
z6 + z5 + z2 + z + 1
z7 + z6 + z5 + z4 + 1
z8 + z6 + z4 + z3 + z2 + z + 1
z8 + z7 + z2 + z + 1
z8 + z7 + z6 + z5 + z2 + z + 1
z8 + z7 + z6 + z5 + z4 + z2 + 1
z9 + z8 + z7 + z6 + z5 + z4 + z3 + z+1z 10 + z 4 + z 3 + z + 1
z 11 + z 10 + z 9 + z 8 + z 3 + z + 1
z 12 + z 11 + z 10 + z 9 + z 8 + z 7 + z 5+z 4 + z 3 + z + 1
z 13 + z 7 + z 4 + z 3 + z 2 + z + 1
z 14 + z 10 + z 6 + z + 1
z 15 + z 14 + z 13 + z 12 + z 9 + z 8 + 1
z 16 + z 10 + z 9 + z 8 + z 7 + z 6 + z 5+z 4 + 1
z 17 + z 16 + z 15 + z 14 + z 6 + z 5 + z 4+z 3 + z 2 + z + 1
z 18 + z 17 + z 14 + z 13 + z 11 + z 9+z 8 + z 7 + 1
z 19 + z 18 + z 15 + z 14 + z 13 + z 12
+z 10 + z 8 + z 7 + z 6 + z 3 + z 2 + 1
z 20 + z 18 + z 14 + z 13 + z 12 + z 11
+z 10 + z 4 + z 3 + z + 1
z 21 + z 15 + z 14 + z 13 + z 11 + z 7+z 5 + z 4 + z 3 + z 2 + 1

位相差

2
4
8
2
10
4
22
57
237
183
905
951
2787
4657
9205
20523
33843

表 2 は、5 次から 21 次までの、同次内での最も有用性の高い原始多項式を、まとめたものである。表 2 の位相差が必要とされる。これは、26 次といった高次にいたってについては、それぞれの原始多項式の最も小さい位相差をも、CA の出力の最小位相差が 1 となるような原始多項式

表記したものである。この表から、10 次までの低い次数が存在している点から、そのような原始多項式を VLSI のでの最小位相差は、 最も有用性の高いものでも 10 以下とテストに用いる事が大変危険だと言えるからである。そなっており、20、21 次の位相差となると、20523、33843

こで、より高次の次数での CA の出力の解析を行うと共と大きな位相差となっていることがわかる。

に、テストに用いられる擬似乱数を生成する上で、最も有ここで注目すべき点は、20、21 次のような最小位相差が用性の高い原始多項式の導出を行うために、次数ごとでの大きな値を持つような原始多項式の存在する次数であっすべての原始多項式の導出とその位相差の解析を行った。

ても、最小位相差が 1 となるような、使用を避けたい原始

同次内での最も有用性の高い原始多項式の導出という点

多項式が多々存在している点である。このことは、次数がに関しては、次数ごとでのすべての原始多項式の導出をより高くなるほど原始多項式の選び方が重要となること

21 次まで行った。その上で、導出した原始多項式を基に、を示しており、表 2 の原始多項式を使用することが望ま

出力の位相差の解析を行った。解析結果からは、同じ位相

しいと考えられる。

差の原始多項式が 4 つ存在している 8 次を除くと、それ6.2 高次の原始多項式の解析結果
21 次を超える場合については、使用した計算機の性能

ぞれの次数に最も有用性の高い原始多項式が１つずつ存の制約のため、すべての原始多項式を調べることはできなすべての次数に対して、位相差が 1 となるような、テスト

かったが、26 次までの各次数については、ひとつずつのに用いる事の危険な原始多項式が存在しているという結

原始多項式について解析を行った。表 3 に 26 次の場合の果を得た。高次の原始多項式の解析という点に関しては、計算結果を示す。周期は 226 − 1=67108863 である。

26 次の原始多項式までの解析結果は得られたが、26 次内

表 3: 26 次の原始多項式実行結果

f (z)a1 · · · a26
j1 · · · j26

z 26 + z 6 + z 2 + z + 1
01110,00100,01100,00010,00111,0
0,67108862,2156381,2513379,52436048,
19093026,66737659,31587164,26846356,
50250807,56988247,28850809,62821929,
19287549,11615250,39917996,67097001,
17567466,24307953,1795530,42961633,
33950907,55923454,59697361,47835274,
66228865在していた。また、本研究で解析を行った、21 次までのでのすべての原始多項式での解析が今後の課題となる。

謝辞
直接の指導教官である南山大学大学院の伏見正則教授には、終始暖かいご指導をいただいた。研究の進展の途中で、何度も的確なご指摘をいただき、先生のご発言に幾度となく救われました。深く感謝致します。南山大学大学
院の鈴木敦夫、尾崎俊治両教授には、中間発表の際、有益なご助言をいただくことができ深く感謝致します。

この結果をソートし、最小な位相差を出すと、67108862 →0(226 − 1 = 67108863) の位相差が最小で、位相差は 1 となる。26 次という高い次数にも関わらず、位相差が 1 という事、これは、この原始多項式を擬似ランダムテストに用いる事は、危険だという事を示唆している一例だと言える。しかし、この点に関しては、a1 もしくは an の値が 0か 1 かという点で判別可能であり、a1 の値が 0 の際には(18) 式の (i=1) の場合の式より、また、an の値が 0 の際には、(i = n) の場合の式から、それぞれ、j2 = j1 − 1、
jn−1 = jn − 1 となり、最小の位相差が 1 となる事がわかる。よって、少なくとも a1 もしくは an の値が 1 となる原始多項式を、VLSI テストに用いる事は危険と言える。
6.3 本研究のまとめ本研究では、VLSI の内部検査用の「疑似ランダムテスト」(以下テスト) に用いられる CA の各セル間の位相差の解析を行うにあたり、テストの入力となる擬似乱数を生成している原始多項式を、21 次以下の次数ごとですべて導出し、検証を行った。従来の研究では、CA の次数ごとでの各セルの出力の結果の検証は行われてきた。しかし、原始多項式による擬似乱数の入力を用いる際に、さらに出力の位相差が大変重要となる。つまり、次数ごとで、すべての原始多項式に対しての、CA の出力の位相差の解析

参考文献[1] 伏見正則:乱数, 東京大学出版会,1989.
[2] 手塚集, 伏見正則:フィボナッチ多項式とその応用, 応
用数理,Vol.4,No.1 March,1994,pp.2-12.
[3] P.Sarkar:Computing shifts in 90/150 cellular automata sequences,Finite Fields and Their Applications ,Vol.9,Issue2,April 2003,pp.175-186.
[4] S.Tezuka and M.Fusimi:A method of designing cellular automata as pseudorandom number generators for built-in self-test for VLSI, Contemporary
Mathematics,Vol.168,AMS,1994,pp.363-367[5] P.H.Bardell:Analysis of cellular automata used as
pseudo random pattern generators,Proc.Int.Test
Conference,IEEE,1990,pp.762-768.
[6] J.P.Mesirov and M.M.Sweet:Continued fraction
expansions of rational expressions with irreducible denominators in characteristic 2,J.Number
Theory,Vol.27,1987,pp.144-148.
[7] S.Wolfram: Statistical mechanics of cellular automata, Rev.Modern Physics,55,1983,pp.601-644.