chapter 9 最近の更新履歴 Hideo Fujiwara

第９章 テスト生成

9.1 _{ブール微分}

変数_xi に関する関数 _F のブール微分

F(x

, x

, _!!! , x

)

dF

dx

^{= F(x}

^{, !!! , x}

^{, !!! , x}

^{) ! F(x}

^{, !!! , x}

^{, !!! , x}

⁾

3

9.1 _{ブール微分}

変数_xi に関する関数 _F のブール微分

dF

dx

^{= F(x}

^{, !!! , x}

^{, !!! , x}

^{) ! F(x}

^{, !!! , x}

^{, !!! , x}

⁾

シャノンの展開定理より

F(x₁, _!!! , x_i, _!!! , x_n) = x_iF_i(1) ! x_iF_i(0)

F(x

,

, x

,

, x

) = x

F

(1) ! x

F

(0)

F

(1) = F(x

, _!!! , x

,1, x

, !!! , x

)

F

(0) = F(x

, _!!! , x

,0, x

, _!!! , x

)

9.1 _{ブール微分}

dF

dx

^{= F(x}

^{, !!! , x}

^{, !!! , x}

^{) ! F(x}

^{, !!! , x}

^{, !!! , x}

⁾

= x

F

(1) ! x

F

(0) ! x

F

(1) ! x

F

(0)

= F

(1) ! F

(0)

5

9.1 _{ブール微分}

F = (x

+ x

)(x

+ x

)

dF

dx

^{= F}

^{(1) ! F}

⁽⁰⁾

= (x ₃ + x ₄ ) ! x ₂ (x ₃ + x ₄ )

= x ₂ (x ₃ + x ₄ )

テストベクトル

F

(x

, x

, _!!! , x

) = F(x

, _!!! , x

,0, x

, _!!! , x

)

= F

(0)

F(x

, x

, _!!! , x

)

組合せ回路の出力関数を

入力線 _x

i^{が０に縮退する故障 α の故障関数 F} α^は

を満たす入力の組み合わせ

F(X) ! F

(X) = 1

故障 _α を検出するテスト入力は

!!"!#$!%!$!%!&&&%!$!'

7

テストベクトル

F(X) ! F

(X) = x

F

(1) ! x

F

(0) ! F

(0)

= x

F

(1) ! x

F

(0) ! (x

! x

)F

(0)

= x

F

(1) ! F

(0)

= x

^dF

dx

故障 x_{i /0} を検出するテストパターンの集合は

{X | x

dF

dx

^{= 1}}

同様に

故障 xi /1 を検出するテストパターンの集合は

{X | x

dF

dx

^{= 1}}

テストベクトル

故障 _x

i ^/0 を検出するテストパターンの集合は

_{{X | x}

_dF

dx

^{= 1}}

= x

F

(1) ! F

(0)

= x

^dF

dx

^＝１

x

x

dF_／dxi =1 誤りを外部出力まで伝搬

9

テストベクトル

x

dF

dx

^{= x}

^x

^(x

^{+ x}

⁾

= x

^x

^x

^{+ x}

^x

^x

x ₁ =x ₂ =x ₃ =1 _x

1

^=x

^=x

₌₁

1^{/0 のテストパターンは}

X s-a-0

テストベクトル

x

dF

dx

^{= x}

^x

^(x

^{+ x}

⁾

= x

x

x

+ x

x

x

x ₁ =x ₂ =x ₃ =1 _x

1

^=x

^=x

₌₁

1^{/0 のテストパターンは}

X s-a-0 1

1

1

0/1

1/0

0/1

1/-

11

経路活性化

x

dF

dx

^{= x}

^x

^(x

^{+ x}

⁾

= x

x

x

+ x

x

x

x ₁ =x ₂ =x ^{3 =1} _x

_=x

_=x

₌₁

したがって、故障 _x

1^{/0 のテストパターンは}

X s-a-0 1

1

1

0/1

1/0

0/1

-

1/-

活性化された経路

多重経路活性化

x

dF

dx

^{= x}

^x

^(x

^{+ x}

⁾

= x

x

x

+ x

x

x

x ₁ =x ₂ =x ^{3 =1} _x

_=x

_=x

₌₁

したがって、故障 _x

1^{/0 のテストパターンは}

13

内部信号線のテスト

故障点_hで誤りを発生するために h(X) = 1

h の値を出力まで伝搬するために

h/0 の故障のテストパターンの集合は  F*(X, h) = F(X)

dF*(X, h) dh ^{= 1} 信号線 _h の０縮退故障

{X | h(X) ^{dF*(X, h)}

dh ^{= 1}}

内部信号線のテスト

信号線 _h の1縮退故障

F = (x

+ x

)(x

+ x

)

F*(X) = ( x

+ x

)x

+ h

h(X) = x

x

+ x

dF*(X, h)

dh ^{= 1 ! (x1 + x2)x4}

^{= x}

^x

^{+ x}

h dF*

dh ^{= (x}

^{+ x}

^)x

^x

^{= x}

^x

^x

^{+ x}

^x

^x

x

x

x

x

x

x

h/1 の故障のテストパターンは または

F*(X, h)

15

演習問題１

図 _9.26 の回路に対して、出力関数をｆとするとき、つぎのブール微分を求 めよ。

(a)_{f を x1} , x₂ , x₃ , x₄ ^{で表現するとき、}f ^の x₁^{に関するブール微分} (b)   f を h と x3 ^{, x}4 ^{で表現するとき、f の h に関するブール微分}

演習問題１（ (a)解答）

(a)_{f を x1} , x₂ , x₃ , x₄ ^{で表現するとき、}f ^の x₁^{に関するブール微分}

f = (x

1

x

2

) (x

3

x

4

) + (x

1

x

2

) (x

3

x

4

) = (x

1

x

2

) + (x

3

x

4

)

df/dx

1

= (x

3

x

4

) + x

2

+ (x

3

x

4

) = x

2

17

演習問題１（ (b)解答）

(b)  _f を _h と _x

3 ^{, x}4 ^{で表現するとき、f の h に関するブール微分}

f = h (x

3

x

4

) + h (x

3

x

4

) = h + (x

3

x

4

) df/dh = (x

3

x

4

) + (1 +(x

3

x

4

)) = 1

演習問題２

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンの集合を ブール微分で求めよ

19

演習問題２（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンの集合を ブール微分で求めよ

df/dh = (x

3

x

4

) + (1 +(x

3

x

4

)) = 1 h(df/dh) = h = x

1

x

2

x

1

= 1, x

2

= 1

演習問題２（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンの集合を ブール微分で求めよ

x

1

= 1, x

2

= 1

1 1/0

df/dh = (x

3

x

4

) + (1 +(x

3

x

4

)) = 1 h(df/dh) = h = x

1

x

2

21

演習問題２（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンの集合を ブール微分で求めよ

x

1

= 1, x

2

= 1

1 1

1/0

0

1

1/0

1/0 0

0

x df/dh = (x

3

x

4

) + (1 +(x

3

x

4

)) = 1 h(df/dh) = h = x

1

x

2

演習問題２（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンの集合を ブール微分で求めよ

x

1

= 1, x

2

= 1

1 1

1/0

1

0

0/1

0

0/1

0/1

1 1 df/dh = (x

3

x

4

) + (1 +(x

3

x

4

)) = 1 h(df/dh) = h = x

1

x

2

23

9.2 組合せ回路のテスト生成

与えられた故障が冗長であるか否かを判定し 冗長でない故障であれば

それを検出するテストパターンを常に求めることができる 完全なテスト生成アルゴリズムとして

1966^年 IBM ^のJ.P. Roth ^により Ｄアルゴリズム（D-algorithm^{）が考案された}

想定する縮退故障をテストするためのテストパターンを生成する

０縮退故障

D _{アルゴリズム}

25

1 1

D

故障を活性化するために _D=1/0

誤り ₌ 正常_/故障

D _{アルゴリズム}

想定する縮退故障をテストするためのテストパターンを生成する

1 1

D

誤りを伝搬するために

0

D

D 1

D _{アルゴリズム}

想定する縮退故障をテストするためのテストパターンを生成する

27

1 1

D

正当化するために

0

D

D 1

0

0 1

D _{アルゴリズム}

想定する縮退故障をテストするためのテストパターンを生成する

1 1

D

テストパターン f s-a-0

D _{アルゴリズム}

想定する縮退故障をテストするためのテストパターンを生成する

29

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

誤り発生

D _{アルゴリズム}

31

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

１ _/ ０

１ １ _/ ０

１

１

１

誤り伝播

D _{アルゴリズム}

33

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

１

０

１

１

０ _/ １

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

１

０

１

１

０ _/ １

１

１

１ _/ ０

D _{アルゴリズム}

35

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

正当化

０

１

１

０ _/ １

１

１

１ _/ ０

０

１

１

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

１ _/ ０

１ １ _/ ０

１

１

０

１

１

０ _/ １

１ _/ ０

含意

D _{アルゴリズム}

37

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

１

０

１

１

０ _/ １

１

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

１

０

１

１

０ _/ １

１

０ _/ １

１

０

１

D _{アルゴリズム}

39

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１ _/ ０

１

１ １ _/ ０

１ _/ ０

１

１

０

１

１

０ _/ １

１

１

０ _/ １

１

０

１

１ _/ ０

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

１ _/ ０

１ １ _/ ０

１

１

０

１

１

０ _/ １

１ _/ ０

D _{アルゴリズム}

41

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

D _{アルゴリズム}

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

誤り発生

D _{アルゴリズム}

Ｄ

D=1/0 誤り ₌ 正常_/故障

43

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

D _{アルゴリズム}

Ｄ

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

１

１

１

１

誤り伝播

D _{アルゴリズム}

Ｄ

Ｄ

45

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

１

０

１

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

D=0/1 誤り ₌ 正常_/故障

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

１

０

１

１

１

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

Ｄ

47

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

正当化

０

１

１

１

１

０

１

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

Ｄ

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

１

１

１

０

１

１

含意

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

49

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

１

０

１

１

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

１

０

１

１

１

１

０

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

Ｄ

51

テスト生成（Dアルゴリズム）

1 2

3

4

5

6

7

8

9

10

11

12 G1 X

G2

G3

G4

G5

G6

G7

G8 0 縮退故障

１

１

１

１

０

１

１

１

１

１

０

１

D _{アルゴリズム}

Ｄ

Ｄ

Ｄ

Ｄ

Ｄ

Ｄ

テスト生成（Dアルゴリズム）

1

3

5

6

8

9

12 G2

G4

G5

G

Ｄ

１

１

１

０

１

１

Ｄ

D _{アルゴリズム}

D=0/1 誤り ₌ 正常_/故障 D=1/0

誤り ₌ 正常_/故障

53

演習問題３

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンを Dアルゴリズムで求めよ

演習問題３（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンを Dアルゴリズムで求めよ

D 1

1

D 1

0 D

0 0

x

55

演習問題３（解答）

図 _9.26 の回路において、 _h の ０縮退故障に対するテストパターンを Dアルゴリズムで求めよ

D 1

1

D 0

0

D 1

1

1

D

Present state at time q Initial state

is unknown

Next state at time q

fault fault fault

9.3 _{順序回路のテスト生成}

57

9.3 _{順序回路のテスト生成}

Stuck-at-1

  Time expansion model (3 time frames)

9.3 _{順序回路のテスト生成}

59

  Time expansion model (3 time frames) D = 1 / 0 D = 0 / 1

D-drive Fault propagation

9.3 _{順序回路のテスト生成}

D = 1 / 0 D = 0 / 1

State justification

9.3 _{順序回路のテスト生成}

61

  Time expansion model (4 time frames) D = 1 / 0 D = 0 / 1

D-drive Fault propagation

9.3 _{順序回路のテスト生成}

  Time expansion model (4 time frames) D = 1 / 0 D = 0 / 1

State justification

Initial state is (X,X)

9.3 _{順序回路のテスト生成}

63

テスト生成アルゴリズムの歴史

Combinational ATPG

1966

D-algorithm (Roth, IBM)

1981

PODEM (Goel)

1983

FAN (Fujiwara)

1985

ISCAS-85 Benchmarks (Fujiwara & Brglez)

1988

SOCRATES (Schulz, et al.)

1990

Recursive Learning (Kunz,et al.)

1999

ITC-99 benchmarks

2001

SPIRIT (Gizdarski

& Fujiwara) 1993

NEMESIS (Larrabee)

1992

TRAN (Chakradhar, et al.)

2000

IGRAINE (Tafertshofer, et al.)

The first ATPG able to achieve 100% fault efficiency

for ISCAS’85

SAT-based ATPG

The first ATPG able to achieve 100% fault efficiency

for ITC’99

Combinational ATPG

1966

D-algorithm (Roth, IBM)

1981

PODEM (Goel)

1983

FAN (Fujiwara)

1985

ISCAS-85 Benchmarks

1988

SOCRATES (Schulz, et al.)

1990

Recursive Learning (Kunz,et al.)

1999 2001

SPIRIT (Gizdarski

& Fujiwara) 1993

NEMESIS (Larrabee)

1992

TRAN (Chakradhar, et al.)

2000

IGRAINE (Tafertshofer, et al.)

テスト生成アルゴリズムの歴史

65

9.4 _{故障シミュレーション}

並列故障シミュレーション（parallel fault simulation^）

演繹故障シミュレーション（deductive fault simulation^）

同時故障シミュレーション（concurrent fault simulation^）

演繹故障シミュレーション

   L

A

= {a, e}    L

B

= {b, c}    L

C

= {a, b, c, d}    _L

D = {a, d, f}

L_E = L_{A!LB " LC" LD}

L_E = L_{A!LB " LC" LD ! E/1}

67

演繹故障シミュレーション

L_A = _{A/1} LB = {B/0} LC = ^{{
 } L_D = {D/0}

LE = LA ! LB " {E/1} ={A/1, E/1}

LH =LF ! {H/0} ={C/0, D/0, F/0, H/0} LN =LF ! {N/0} ={C/0, D/0, G/0, N/0}

LJ =LE ! {J/1} ={A/1, E/1, J/1} LK =LE ! {K/1} ={Q/1, E/1, K/1}

LL =LH ! {L/1} ={C/0, D/0, F/0, H/0, L/1}

LM =LJ ! {M/0} ={A/1, E/1, J/1, M/0} L_P = L_K ! L_L " {P/1} ={P/1} L_{Q = LM ! LN ! {Q/0}}

={A/1, C/0, D/0, E/1, F/0, J/1, M/0, N/0, Q/0}

L

= L

! L

" {R/0}

同時故障シミュレーション

69

同時故障シミュレーション

同時故障シミュレーション

71

同時故障シミュレーション

同時故障シミュレーション

73

演習問題４

図 _9.27 に示すように、４入力 _NAND に対して、A=B=0, C=D=1 ^の 入力パターンが与えられているとする

  故障リスト _L

A ^{, L}B ^{, L}C ^{, L}D ^{が出力 E} にどのように伝搬するかを計算する 集合算を示せ

演習問題４（解答）

L

A

={A/1}, L

B

={B/1}, L

C

={C/0}, L

D

={D/0}

L

E

= (L

A

∩  L

B

∩  L

C

∩  L

D

)∪ {E/ 0}

まず、入力 A, B, C, D の故障リストはつぎのようになる。

つぎに、NANDゲートにおいて、_E の故障リストは