N 回衝突テスト圧縮パターンの検出故障解析

N 回衝突テスト圧縮パターンの検出故障解析

日大生産工（院）○ 湯本 仁高 日大生産工 細川 利典

九大 吉村 正義

1

． はじめに

近年，半導体集積技術の急速な進展に伴い，超大規 模集積回路(VLSI:Very Large Scale Integration)が大 規模化，高機能化している．したがって，テスト設計 の工数が増大しており，その自動化技術が重要になっ ている．一般の順序回路の自動テストパターン生成 (ATPG:Auto Test Pattern Generation)は困難な問題 であり，高い故障検出効率を得るテストパターンを生 成するには，フルスキャン設計[1][2]に代表されるテス ト容易化設計(DFT:Design For Testability)が必要で ある．また，VLSI が大規模化，高集積化することに より，回路内のゲート数が増加しており，それに比例 してテストパターン数も増加し，テストコストが激増 している[3]．

そこで上記の問題を解決するための一手法として，

テストポイントの挿入によりテストパターン圧縮の効 率を高める手法が提案されている[4][5][6][7]．回路内 部の信号線にテストポイントが挿入された場合，その 信号線は可制御かつ可観測となり，テストポイントが 挿入された内部信号線は擬似外部入出力として扱うこ とが可能となる．回路内にテストポイントを挿入する ことにより，外部入力数とテストパターン集合中のド ントケア数(X:don’t care)が増加し，テストパターン圧 縮の効率が高くなる．その結果テストパターン数が削 減できると考えられている．文献[4]，[5]，[6]のテス トポイント挿入箇所探索アルゴリズムは，テスト圧縮 の原理と，回路構造のみに着目し，回路構造上テスト パターン圧縮が困難であると予想される箇所にテスト ポイントを挿入し，テストパターン数の削減を図って いる．

一方で，回路構造からではなく生成されたテストパ ターン集合に着目し，テストパターン数の削減を図る テストポイント挿入法も提案されている[7]．テストパ ターンを圧縮する方法に，ドントケア(X)に基づく圧縮 がある．0，1，Xからなるテストパターンを衝突が発 生しないように圧縮する方法である．文献[7]では，圧 縮可能な条件を，ハミング距離がN以下であるものと

したNハミング距離テストパターン圧縮を用いて，値 の衝突が起こっている N ビットに対してテストポイ ントを挿入する N ハミング距離テストパターンに基 づくテストパターン数削減指向テストポイント挿入法 が提案されている．

本稿では，文献[7]で提案された N ハミング距離テ ストパターン圧縮に注目し，Nハミング距離テストパ ターン圧縮後のテストパターンで検出される故障が，

圧縮前のテストパターンで検出される故障を包含して いるか否か検証・解析を行った．また，検証・解析結 果を基に文献[7]で提案されているテストポイント挿 入候補探索アルゴリズムについて考察を行った．

2

．

ハミング距離テストパターン圧縮

本章では，文献[7]のテストポイント挿入法で用いら れているＮハミング距離テストパターン圧縮について 述べる．2.1では，N ハミング距離テストパターン圧 縮可能[7]と N ハミング距離テストパターン圧縮可能 グラフ[7]を定義する．2.2 では，1 ハミング距離テス トパターン圧縮について述べる．

2.1

諸定義

(

定義

：Ｎハミング距離圧縮可能

外部入力(PI1，PI2，…，PIm)を持つ組合せ回路に 対する 2 つのテストパターンをT1，T2とする(mは外 部入力数)．また，T1，T2の外部入力PIiの値をそれぞ れT1(PIi)，T2(PIi

T

)と表記する(1≦ｉ≦m)．

1(PIi)， T2(PIi)∈{0，1，X}

表

．Ｎハミング距離圧縮演算∩

∩

Ｎ

Ｎ

０ １ Ｘ

０ ０ Ｗ ０ １ Ｗ １ １ Ｘ ０ １ Ｘ

Analysis for Detected Faults by N-Humming Compacted Test Patterns.

Yoshitaka YUMOTO,

Toshinori HOSOKAWA

，

表１に示すＮハミング距離圧縮演算∩_Nを用いると，

Ｎハミング距離圧縮演算結果Tは任意のi(1≦ｉ≦m) について式(1)で表すことができる．

(1) )

( ) ( )

(PI_i T1 PI_{i N}T2 PI_i

　･･･

T = 

∑

i

i N

PI T V

1

)) (

( ^{であるとき，T1とT2はNハミン}

グ距離圧縮可能であるという．ただし，Ｖ(T(PIi))は T(PIi)＝Ｗの時 1，それ以外の時0であるとする．こ のとき演算結果TをT1とT2のマスターパターンという．

(

定義

：Ｎハミング距離圧縮可能グラフ

∀u，v∈(u≠v)において辺(u，v)∈EはuとvがNハ ミング距離圧縮可能であることを示す．

2.2 1

ハミング距離テストパターン圧縮

文献[7]で提案されている N ハミング距離テストパ ターン圧縮は，テストポイントを挿入すべき箇所を探 索するための情報を作成することを目的としている．

以下に1ハミング距離におけるテストパターン圧縮 について示す．まず，図1のテストパターン集合から 1 ハミング距離圧縮可能グラフを作成する．次に，作 成された1ハミング距離圧縮可能グラフを最小クリー ク分割[8]を行う．図2は，最小クリーク分割の例を示 している．各ノードは，テストパターンを表し，実線 はテストパターン圧縮可能，点線は1ハミング距離圧 縮可能であることを表している．最後にマスターパタ ーンを生成する．マスターパターンとは，1 ハミング 距離圧縮可能な2つのテストパターンを圧縮したテス トパターンであり，値の衝突が起こっている箇所をW と表す．図3は図1のT2，T3

文献[7]では，1ハミング距離テストパターンペアを 圧縮可能とするために必要最小限のテストポイント数 は1個であると仮定しており，1箇所にテストポイン ト挿入を行ったときに圧縮可能となり，1ハミング距 離テストパターンペアの値の衝突が解消できるとして いる．

というテストパターンか らマスターパターンTを生成する例を示す．

本稿では，文献[7]の仮定である1つの1ハミング距 離テストパターンペアに対して1個のテストポイント 挿入でテストパターンの値の衝突が本当に解消可能で あるかを検証し，考察を行う．また，Nハミング距離 圧縮前のテストパターンで検出された故障が圧縮後で も検出されているか検証・解析を行う．

T₁=１０Ｘ１ＸＸ１ T₂=ＸＸ１１０Ｘ１ T₃=Ｘ００１０ＸＸ T₄=０００１ＸＸＸ T₅=１ＸＸ１１ＸＸ T₁=１０Ｘ１ＸＸ１ T₂=ＸＸ１１０Ｘ１ T₃=Ｘ００１０ＸＸ T₄=０００１ＸＸＸ T₅=１ＸＸ１１ＸＸ

図

．テストパターン集合

クリーク数 1 T₁ T₅

T₃ T₄ T₂

クリーク数 1 T₁ T₅

T₃ T₄ T₂

図

．最小クリーク分割

T₃ Ｘ００１０ＸＸ T Ｘ０w１０Ｘ１

マスターパターン

T₂ ＸＸ１１０Ｘ１

T₃ Ｘ００１０ＸＸ T Ｘ０w１０Ｘ１

マスターパターン

図

．マスターパターン生成

FFR5

a(1, 0) b(1, X)

c(1, 0)

FFR1

FFR2

FFR3

FFR4

非衝突

衝突 衝突 非衝突 d(1, 1)

e

f

h

i^FFR6

衝突

g(1, 0) j

k

FFR5

a(1, 0) b(1, X)

c(1, 0)

FFR1

FFR2

FFR3

FFR4

非衝突非衝突

衝突衝突 衝突衝突 非衝突非衝突 d(1, 1)

e

f

h

i^FFR6

衝突衝突

g(1, 0) j

k

図

．テストポイント挿入候補信号線

3

． テストポイント挿入候補信号線探索

本章では，文献[7]において1ハミング距離テストパ ター ンペアに 対するテス トポイ ント挿入(TPI:Test Point Insertion)候補信号線をどのように探索してい るのか述べる．文献[7]では， 1 ハミング距離テスト パターンペアが持つ衝突ビットWに着目し，回路中の 値の衝突原因となる信号線を探索し，その結果より求 められた信号線を1ハミング距離テストパターンペア におけるTPI候補信号線としている．ここで述べてい る値の衝突とは，分岐先信号線から送られる値割当て 要求が分岐元信号線で衝突することであり，値の衝突 は分岐元信号線でのみ発生するものと仮定している．

1 ハミング距離テストパターンペアに対するTPI挿 入候補信号線の探索例を図4に示す．図4においてa は外部入力，d，gは外部出力，b，cは分岐元の信号線 を表し，e，f，h，i，j，kは分岐先信号線を表してい る．また，各信号線の括弧内の値は1ハミング距離テ ストパターンペアであるT1, T2の論理シミュレーショ ン結果を表している．

まず，外部入力である信号線aから到達可能な分岐 元信号線もしくは，外部出力の信号線を探索する．図 4 の例では外部入力aはbとcの 2つの分岐元信号線に 到達可能である．ここで，外部入力aはT1とT2の信号 値が衝突しているが，分岐元信号線bではT1とT2の信 号値が非衝突となっているので，外部入力aと分岐元 信号線bの間にある分岐先信号線eはTPI候補信号線と なる．次に分岐元信号線cのT1とT2の信号値が衝突し ているので，分岐先信号線fはTPI候補信号線とはなら ない．次に衝突のある分岐元信号線cから分岐している 2つの分岐先がTPI候補信号線となるか否かを調べる．

外部出力dのT1とT2の信号値が非衝突となっているの で，分岐先信号線hはTPI候補信号線となる．外部出力 gのT1とT2の信号値が衝突となっているので，分岐先 信号線iはTPI候補信号線とはならない．よって， T1

とT2の 1 ハミング距離テストパターンペアに対する TPI候補信号線は信号線eと信号線hとなり，T1とT2

の1ハミング距離テストパターンペアに対するTPI候 補信号線の探索を終了する．この探索例から，1 つの 1 ハミング距離テストパターンペアに対するテストポ イント挿入候補信号線は複数存在することがわかる．

4

． テストポイント挿入後の

ハミング距離テ ストパターンペアの検出故障解析

本章では，1ハミング距離テストパターン圧縮した テストパターンで検出された故障が，圧縮前のテスト パターンペアで検出される故障を包含するかを解析す る方法について述べる．図5は検出故障解析の手順を 示している．STEP1 では，ATPG を用いてテストパ ターン集合を生成する．STEP2では，STEP1で生成 されたテストパターンに対して X 抽出[9]を行う．

STEP3では，STEP2で生成されたX抽出後のテスト パターン集合で故障シミュレーションを実行し，故障 リストを生成する．故障リストとは，ある特定のテス トパターンに対して検出される故障が列挙されたもの である．STEP4では，1つの1ハミング距離テストパ ターンペアにおいて，TPI候補を探索し，値の衝突を 解消する部分をランダムに１つ選択しTPIを行い，回 路変更を行う．STEP5では，1ハミング距離テストパ ターンペアの情報を基に1ハミング距離テストパター ン圧縮を行い，圧縮後のテストパターンを生成する．

STEP6では，STEP5で生成した1ハミング距離テス トパターン圧縮後のテストパターンに対して故障シミ ュレーションを行い，故障リストを生成する． STEP7 では，STEP3で生成した故障リストとSTEP6で生成 した故障リストを比較し，1ハミング距離テストパタ ーン圧縮後のテストパターンで検出される故障が，圧

テストパターン生成 X（ドントケア）抽出

Xを含んだテストパターンで 故障シミュレーション

Nハミング距離の圧縮後の テストパターンを故障シミュレーション

TPI箇所探索・挿入・回路変更

Nハミング距離圧縮後の テストパターンを作成

検出故障の比較 STEP1

STEP2 STEP3

STEP4

STEP5

STEP6 STEP7

START

END テストパターン生成

X（ドントケア）抽出

Xを含んだテストパターンで 故障シミュレーション

Nハミング距離の圧縮後の テストパターンを故障シミュレーション

TPI箇所探索・挿入・回路変更

Nハミング距離圧縮後の テストパターンを作成

検出故障の比較 STEP1

STEP2 STEP3

STEP4

STEP5

STEP6 STEP7

START

END

図

．検出故障解析の手順

縮前のテストパターンペアで検出される故障を包含し ているか否か検証する．STEP4～STEP6を1ハミン グ距離テストパターンペア数回繰り返す．

5

． 実験結果

ISCAS’85ベンチマーク回路のc5315回路に対して，

1 ハミング距離圧縮後のテストパターンが圧縮前のテ ストパターンペアで検出される故障を包含するか否か 検証・解析を行った．本実験では，ATPGと故障シミ ュレーションをSynopsys社のTetra MAXを用い，N ハミング距離を１に設定し，実験を行った．表 2 に c5315回路の回路情報を示す．test_pattern_numはテ ストパターン数，1humming_numは1ハミング距離 のテストパターンペア数を表している．

図６(a)，(b)に1ハミング距離のテストパターンペア ごとに対して，圧縮前のテストパターンペアで検出さ れた故障数と圧縮後のテストパターンで検出された故 障数の比較結果を示す．横軸は1ハミング距離圧縮可 能テストパターンペア番号を表し，縦軸は検出された 故障の数を表している．黒の棒グラフは圧縮前のテス トパターンペアで検出された故障数，白の棒グラフは，

圧縮後のテストパターンで圧縮前のテストパターンで 検出される故障を検出した数を表している．検出故障 数を比較してみると，全体的に圧縮後のテストパター ンは圧縮前のテストパターンペアで検出できる故障を 検出できていないことが分かった．しかし，1ハミン グ距離ペアパターン番号30，39，41，42，43の箇所 においては，圧縮後のテストパターンでも圧縮前のテ ストパターンペアが検出した故障数と同等の故障を検 出することができている．図7に1ハミング距離テス トパターンペア番号41，72において，全てのTPI候 補箇所に対してTPIを行った結果を示す．直線は圧縮 前のテストパターンペアで検出された故障数，棒グラ フはペア番号における各TPI候補で検出された故障数

である．この結果より，TPI候補を変更してもあまり 効果がないことがわかる．

6

． おわりに

1 ハミング距離テストパターン圧縮後のテストパタ ーンで検出される故障が，圧縮前のテストパターンペ アで検出される故障を包含できているか検証・解析を 行った．結果として， 1ハミングテストパターン圧縮 後のテストパターンは，圧縮前のテストパターンペア で検出された故障をあまり検出していなかった．この ことからテストパターンペアを1ハミング距離テスト パターン圧縮し，値の衝突を1つのテストポイントを 挿入して解消することができていないことが考えられ，

文献[7]の仮定が誤っていると思われる．また，このよ うな結果になった要因を考察すると，文献[7]における TPI箇所探索アルゴリズムに欠陥があるのではないか と考えられる．図4のTPI候補探索例では，値の衝突 が解消された信号線がTPI候補となっており，信号線 e，hが選択されている．しかしながら，外部出力信号 線d，gに到達する分岐元信号線cの衝突が解消され ていないにもかかわらず信号線eをTPI候補にするこ とはおかしいのではないかと思われる．また，外部出 力線gにおいて値の衝突が解消できないまま探索を終 了してしまっており，衝突が解消されず探索を終了す ることはおかしいのではないかと思われる．

表

．

回路の回路情報

test_pattern_num 1humming_num

c5315 98 76

0 500 1000 1500 2000 2500

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 pair_pattern_num

detect_fault

圧縮前テストパターン 圧縮後テストパターン

(a)pair_pattern_num

１

0 200 400 600 800 1000 1200 1400 1600

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 pair_pattern_num

detect_fault

圧縮前テストパターン 圧縮後テストパターン

(b) pair_pattern_num39~76

図

．圧縮前と圧縮後の検出故障数の検証

0 100 200 300 400 500 600 700 800 900 1000

123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 pair_pattern_num

detect_faults

圧縮後のテストパターン 圧縮前のテストパターン

(a)

テストパターンペア番号

0 100 200 300 400 500 600 700 800 900 1000

1 23 4 5 6 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 pair_pattern_num

detect_faults

圧縮後のテストパターン 圧縮前のテストパターン

(b)

テストパターンペア番号

図

．テストポイント番号と検出故障数の解析

[参考文献]

[1] H.Fujiwara，Logic Testing and Design for Testability， The MIT Press，1985

[2] M Abramovici, M.A.Breuer, and A.D.Frindman, Digital Systems Testing and Testable Design, Computer Science Press, 1990.

[3] Y.Sato, T.Ikeda, M.Nakao, and T.Nagumo, “A bist approach for very deepsub-micron (vdsm) defect,

“Proc. Interunational Test Conference, pp. 283291, 2000.

[4] 吉村正義，細川利典，大田光保，”テストパターン数削 減指向テストポイント挿入方法，”信学論，vol. J86-D-I， no. 12， PP. 884-896，2003.

[5] M.J.Geuzebroek J.Th.van der Linden, and A.J.van de Goor,”Test Point Insertion for Compact Test Sets, ”Pros. Int. TestConf., PP. 348-357,1999.

[6] Rafamani Sethuram, Seongmoon Wang, Srimat T.

Chakradhar, Michael L. Bushnell, “Zero Cost Test Point Insertion Technique to Reduce Test Set Size and Test Generation Time for Structured ASICs,”

Pros. Asian Test Symposium, pp. 339-346, 2006.

[7] 斉藤義洋，湯本仁高，細川利典，吉村正義，“Nハミン グ距離テストパターン圧縮に基づくテストパターン数 削減指向テストポイント挿入法”，第58回FTC研究会，

2008/01/10

[8] J．ホロムコヴィッチ 著，和田幸一，増澤利光，元木 光雄 訳“計算困難問題に対するアルゴリズム理論”

Springer出版，2005．

[9] Kohei Miyase and Seiji Kajihara, Irith Pomeranz,

“XID: Don’t Care Identification of Test Patterns for Combinational Circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 23, No. 2, pp. 321-326, Feb. 2004.