JPH11223664A

JPH11223664A - 論理回路のテスト集合圧縮方法

Info

Publication number: JPH11223664A
Application number: JP10320218A
Authority: JP
Inventors: Chakladder Slimatt; チャクラッダースリマット; Haashio Michael; ハーシオマイケル
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1997-12-31
Filing date: 1998-11-11
Publication date: 1999-08-17
Anticipated expiration: 2018-11-11
Also published as: JP3365325B2; US6145106A

Abstract

(57)【要約】【課題】短い実行時間で極めて高度な圧縮が達成され
る部分列除去方法を提供すること。【解決手段】有限状態を有する順序回路において高速
静的圧縮を行なう方法であり、機械の出力状態を緩和す
るステップと、削除候補の再帰部分列を識別するステッ
プと、故障シミュレーション解析を行なって部分列が削
除可能かどうかを判定するステップと、部分列を削除、
および／または削除のための次の再帰部分列候補を識別
するステップを有する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、論理回路、特に順
序回路のためのテスト集合を圧縮する方法に関する。特
に、順序回路における高速静的圧縮のための状態緩和に
基づく部分列削除方法に関する。

【０００２】本出願は、本発明の譲受人に譲渡され、本
明細書中に参考として取り入れる、“Ｐａｒｔｉｔｉｏ
ｎｉｎｇａｎｄＲｅｃｏｒｄｉｎｇＭｅｔｈｏｄ
ｓｆｏｒＳｔａｔｉｃＴｅｓｔＳｅｑｕｅｎｃｅ
ＣｏｍｐａｃｔｉｏｎｏｆＳｅｑｕｅｎｔｉａｌ
Ｃｉｒｃｕｉｔｓ”と題する米国特許出願第０９／００
１５４２号（出願日１９９７年１２月３１日）に関連し
ている。

【０００３】

【従来の技術】順序回路のテスト適用時間（ＴＡＴ）
は、テスト集合のテストベクトル数に比例し、テストの
コストに直接的な影響を与える。このため、より短いテ
ストシーケンスが望まれる。圧縮技術には、２種類、す
なわち、動的圧縮と静的圧縮がある。動的圧縮技術で
は、テスト生成プロセスと同時に圧縮が行なわれ、テス
トジェネレータの変更を必要とすることが多い。一方、
静的テストシーケンス圧縮は、テスト生成後の後処理ス
テップである。静的圧縮技術は、テスト生成アルゴリズ
ムとは関係なく、テストジェネレータの変更を必要とし
ない。動的圧縮がテスト生成中に行なわれたとしても、
静的圧縮により、テスト生成後に得られたテスト集合の
大きさをさらに縮小させることができる。

【０００４】順序回路のためのいくつかの静的圧縮法
が、以下の論文に提案されている。すなわち、Ｔ．Ｍ．
Ｎｉｅｒｍａｎｎらによる“ＴｅｓｔＣｏｍｐａｃｔ
ｉｏｎｆｏｒＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔ
ｓ”（ＩＥＥＥＴｒａｎｓ．Ｃｏｍｐｕｔｅｒ−Ａ
ｉｄｅｄＤｅｓｉｇｎ、Ｖｏｌ．１１、Ｎｏ．２、２
６０〜６７頁、１９９２年２月）や、Ｂ．Ｓｏによる
“Ｔｉｍｅ−ｅｆｆｉｃｉｅｎｔＡｕｔｏｍａｔｉｃ
ＴｅｓｔＰａｔｔｅｒｎＧｅｎｅｒａｔｉｏｎ
Ｓｙｓｔｅｍ”（Ｐｈ．Ｄ．Ｔｈｅｓｉｓ、ＥＥＤｅ
ｐｔ．Ｕｎｉｖ．ｏｆＷｉｓｃｏｎｓｉｎ−Ｍａｄｉ
ｓｏｎ、１９９４年）、Ｉ．Ｐｏｍｅｒａｎｚらによる
“ＯｎＳｔａｔｉｃＣｏｍｐａｃｔｉｏｎｏｆ
ＴｅｓｔＳｅｑｕｅｎｃｅｓｆｏｒＳｙｎｃｈｒｏ
ｎｏｕｓＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔｓ"
（ＰｒｏｃＤｅｓｉｇｎＡｕｔｏｍａｔｉｏｎＣ
ｏｎｆ．、２１５−２０頁、１９９６年６月）、Ｍ．
Ｓ．Ｈｓｉａｏらによる“ＦａｓｔＡｌｇｏｒｉｔｈ
ｍｓｆｏｒＳｔａｔｉｃＣｏｍｐａｃｔｉｏｎ
ｏｆＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔＴｅｓ
ｔＶｅｃｔｏｒｓ”（Ｐｒｏｃ．ＩＥＥＥＶＬＳ
ＩＴｅｓｔＳｙｍｐ．、１８８−１９５頁、１９９
５年４月）などである。

【０００５】最近の提案には、個々の故障にターゲット
を定めて得られたテストシーケンスを重ね合わせたり、
並べかえたりして圧縮を達成することが含まれている
（Ｎｉｅｒｍａｎｎ及びＳｏ）。しかしながら、このよ
うな手法を、ランダムあるいはシミュレーションに基づ
くテストジェネレータにより生成されるテストシーケン
スに用いることはできない。

【０００６】ベクトルの挿入、削除、又は選択に基づく
静的圧縮も研究されている（Ｐｏｍｅｒａｎｚ）。この
ような方法では、多数の故障シミュレーションパスが必
要となる。このような方法では、元のテスト集合を用い
て得ることができる故障検出率を低下させることなく、
テスト集合からベクトルを削除する。ベクトルを削除あ
るいは交換するとき、テストシーケンスに対する変更に
よって故障検出率が影響を受けないことを確実にするた
めに、故障シミュレータが起動される。途方もなく長い
実行時間を費やせば、非常に圧縮されたテスト集合を得
ることができる。

【０００７】テストベクトルの部分列削除に基づく順序
回路の高速静的圧縮技術が最近報告されている（Ｈｓｉ
ａｎｏ）。この手法は、次の２つの知見に基づいてい
る。すなわち、（１）テストシーケンスは、繰り返し現
れる状態の小集合をトラバースする。（２）ある条件の
もとではサイクルに対応する部分列をテスト集合から削
除してもよい。しかしながら、テスト集合に、繰り返し
現れる状態がほとんどあるいは全くなければ、部分列削
除アルゴリズムはあまり効果がない。図１は、いくつか
のＩＳＣＡＳ８９ベンチマーク回路について、ＨＩＴＥ
Ｃテスト集合によりトラバースされたベクトルと状態の
数を示す表である。このようなテスト集合と回路に関す
る情報は、以下の論文に見出だすことができる：Ｔ．
Ｍ．Ｎｉｅｒｍａｎｎらによる“ＨＩＴＥＣ：Ａ
ＴｅｓｔＧｅｎｅｒａｔｉｏｎＰａｃｋａｇｅｆ
ｏｒＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔｓ”（Ｐ
ｒｏｃ．ＥｕｒｏｐｅａｎＣｏｎｆ．Ｄｅｓｉｇｎ
Ａｕｔｏｍａｔｉｏｎ（ＥＤＡＣ）、２１４〜２１８
頁、１９９１年）と、Ｔ．Ｍ．Ｎｉｅｒｍａｎｎらに
よる“ＭｅｔｈｏｄｆｏｒＡｕｔｏｍａｔｉｃａｌ
ｌｙＧｅｎｅｒａｔｉｎｇＴｅｓｔＶｅｃｔｏｒ
ｓｆｏｒＤｉｇｉｔａｌＩｎｔｅｇｒａｔｅｄ
Ｃｉｒｃｕｉｔｓ”（米国特許第５，３７７，１９７
号、１９９４年）と、Ｆ．Ｂｒｇｌｅｚらによる“Ｃｏ
ｍｂｉｎａｔｉｏｎａｌＰｒｏｆｉｌｅｓｏｆＳｅ
ｑｕｅｎｔｉａｌＢｅｎｃｈｍａｒｋＣｉｒｃｕｉ
ｔｓ”（Ｉｎｔ．ＳｙｍｐｏｓｉｕｍｏｎＣｉｒ
ｃｕｉｔｓａｎｄＳｙｓｔｅｍｓ、１９２９〜３４
頁、１９８９年）。他のテストジェネレータによって生
成されたテスト集合においても同様な傾向が見られる。

【０００８】

【発明が解決しようとする課題】繰り返し現れる状態を
もたないテスト集合Ｔについて考えてみる。このテスト
集合にはサイクルがない。明らかに、Ｈｓｉａｏに報告
されている部分列削除アルゴリズムでは、このテスト集
合を圧縮することはできない。しかしながら、状態緩和
を用いることによって、削除し得る部分列を識別するこ
とができる。

【０００９】ここで、本発明でいう「状態緩和」の意味
について以下に説明する。例えば、テスト集合Ｔがある
状態を繰り返すことなく、有限状態機械を状態Ｓ
_initialからＳ_finalに遷移させるものと仮定する。有
限状態機械を状態Ｓ_ｉから状態Ｓ_ｊに遷移させるテスト
集合Ｔの部分列をＴ_subとすれば、このテスト集合はサ
イクルをもたないため、状態Ｓ_ｉとＳ_ｊは異なっていな
ければならない。部分列Ｔ_subを用いて状態Ｓ_ｊに到達
するために、状態Ｓ_ｉにおける値すべてを指定すること
が必須であるとは限らない。したがって、状態Ｓ_ｉにお
いて必須でないビットを指定しないことにより、状態Ｓ
_ｉを緩和することができる。同様に、有限状態機械を状
態Ｓ_finalに遷移させるために、状態Ｓ_ｊにおけるビッ
トすべてを指定する必要はない。

【００１０】一般性を失うことなく、状態Ｓ_ｉとＳ_ｊを
それぞれ、１０１１０と００１００と仮定する。状態Ｓ
_ｊをＸ０１Ｘ０に緩和できると仮定すると、第１及び第
４の状態ビット（フリップフロップ値）は指定されな
い。状態緩和は、部分列Ｔ_subをテスト集合から削除し
ても、修正されたシーケンスを用いて、有限状態機械を
状態Ｓ_finalに遷移させることができることを保証する
ものである。部分列Ｔ_subを削除するということは、ベ
クトルＶ_ｉ〜Ｖ_j-1をテスト集合Ｔから削除することを
意味する。ここで、部分列Ｔ_subの最後のベクトル（ベ
クトルＶ_ｊ）は、依然として、テスト集合の一部をなし
ている。別の言い方をすれば、緩和された状態Ｓ_ｊは状
態Ｓ_ｉをカバーし、部分列Ｔ_subは、圧縮を達成するた
めに削除し得るサイクルを生成している。以上が本発明
でいう「状態緩和」の意味である。

【００１１】状態の緩和は、Ａ．Ｒａｇｈｕｎａｔｈａ
ｎによる“ＡｃｃｅｌｅｒａｔｉｏｎＴｅｃｈｎｉｑ
ｕｅｓｆｏｒＤｙｎａｍｉｃＶｅｃｔｏｒＣｏ
ｍｐａｃｔｉｏｎ”（Ｐｒｏｃ．Ｉｎｔｌ．Ｃｏｎｆ．
Ｃｏｍｐｕｔｅｒ−ＡｉｄｅｄＤｅｓｉｇｎ、３１
０−３１７頁）と題する論文に述べられているようなサ
ポート集合アルゴリズムを用いて効率的に計算すること
ができる。サポート集合は、線形の時間・領域計算量と
して計算することができ、これにより、緩和法は非常に
実現可能なものとなる。テスト集合がサイクルをもって
いる場合には、状態緩和は、より大きいサイクルを見出
だすために用いることができる。サイクルのサイズは、
そのサイクルを生じる部分列内のベクトルの数である。

【００１２】

【課題を解決するための手段】本発明の基本ステップ
は、（１）有限状態機械の出力状態を緩和させること、
（２）削除候補としての再帰[recurrent] 部分列を識別
すること、（３）故障シミュレーション解析を実行し
て、この部分列が削除可能かどうかを判定すること、
（４）この部分列を削除、および／または削除のために
次の再帰部分列候補を識別することである。

【００１３】本発明にはいくつかの利点がある。サイク
ルをもたないために既存の部分列削除技術では圧縮でき
なかったテスト集合を圧縮することができる。テスト集
合におけるサイクルのサイズを状態緩和により著しく増
大させることができ、より大きいサイクルを削除するこ
とで、より良好な圧縮が達成される。本発明によれば、
多数の故障シミュレーションパスを必要とする試行・再
試行法と比較して、わずか２つの故障シミュレーション
パスしか必要としない。現在知られている部分列削除方
法と比較して、短い実行時間で、極めて高度な圧縮が達
成される。ＩＳＣＡＳ８９順序ベンチマーク回路といく
つかの合成回路における実験によれば、公知の部分列削
除方法と比較して、本発明では、常に、短い実行時間で
極めて高度な圧縮が達成される。

【００１４】

【発明の実施の形態】以下、本発明の好ましい実施の形
態を図面を参照して説明する。ｎ個のベクトルＶ_１〜Ｖ
_ｎからなる順序回路テストベクトル集合Ｔを考える。集
合Ｔのｉ番目のベクトルからｊ番目のベクトル（０≦ｉ
≦ｊ≦ｎ）までの部分列を、Ｔ［Ｖ_ｉ，Ｖ_i+1，…，Ｖ
_ｊ］であらわす。ここで、Ｖ_ｉとＶ_ｊとは、それぞれ、
テストベクトル集合Ｔにおけるｉ番目のベクトルおよび
ｊ番目のベクトルである。重要な用語について、以下に
説明する。

【００１５】再帰部分列Ｔ_recは、有限状態機械をある
初期状態から同じ状態に遷移させる。再帰部分列Ｔ_rec
は、必ず、有限状態機械の初期状態を再訪する。この部
分列は、有限状態機械の状態図におけるサイクルをトラ
バースする役割をもつ。

【００１６】再帰部分列は、テスト集合Ｔの、故障ドロ
ッピングをともなう故障シミュレーション中に、この部
分列内に故障が検出されなければ、不活性部分列（Ｔ
_inert）である。故障ドロッピングとは、テスト集合を
圧縮する際に、最終圧縮テストベクトル集合中に残るこ
とになるテストベクトルにより検出される故障を、残り
の未圧縮テストベクトルにより検出しなければならない
故障のプールから排除することを意味する。不活性部分
列は、ある条件のもとで、故障検出率に悪影響を与えず
にテスト集合から削除することができる。例えば、上記
に引用したＨｓｉａｏを参照されたい。

【００１７】ドントケア値Ｘを割り当てられたフリップ
フロップは、指定されていないとみなされる。状態Ｓ_ｉ
を部分的に指定した場合には、状態Ｓ_ｉのドントケア
（未割り当て）値を数え上げることにより、状態の網羅
集合[exhaustive set]を得ることができる。例えば、状
態Ｘ０１は部分的に指定されたものであり、これは、２
つの状態００１と１０１を表わす。

【００１８】状態Ｓ_ｊは、状態Ｓ_ｉにより表わされる状
態のグループが状態Ｓ_ｊによって表わされる状態の部分
集合であるならば、状態Ｓ_ｉをカバーする。例えば、そ
れぞれ、ビットベクトルＸ０１と００Ｘで表わされる２
つの状態Ｓ_１およびＳ_２について考えてみる。状態Ｓ_１
は状態Ｓ_２をカバーしない。これは、状態Ｓ_２が２つの
状態０００と００１を表わし、状態Ｓ_１には状態０００
が含まれていないからである。状態Ｓ_１とＳ_２とを完全
に指定するならば、状態Ｓ_１とＳ_２が同一のときのみ、
状態Ｓ_１はＳ_２をカバーする。

【００１９】フリップフロップは、その値が０あるいは
１からドントケア値Ｘに変化するならば、緩和される。

【００２０】状態Ｓ_ｉ、Ｓ_ｊとこれらの緩和状態
Ｓ_ｉ ^Ｒ、Ｓ_ｊ ^Ｒについて考えてみる。緩和状態Ｓ
_ｊ ^Ｒは、Ｓ_ｊ ^Ｒが非緩和状態Ｓ_ｉをカバーするならば、
緩和状態Ｓ_ｉ ^Ｒを完全にカバーする。ここで、緩和状態
Ｓ_ｊ ^Ｒは、Ｓ_ｉ ^Ｒをカバーするかもしれないし、カバー
しないかもしれない。例えば、緩和状態Ｓ_ｊ ^ＲをＸ０
１、Ｓ_ｉ ^Ｒを００Ｘとする。緩和状態Ｓ_ｊ ^ＲはＳ_ｉ ^Ｒを
カバーしていない。しかしながら、緩和前には状態Ｓ_ｉ
が００１であったならば、緩和状態Ｓ_ｊ ^Ｒは状態Ｓ_ｉを
カバーする。したがって、緩和状態Ｓ_ｊ ^Ｒは、Ｓ_ｉ ^Ｒを
完全にカバーする。

【００２１】２つの緩和状態Ｓ_ｉ ^ＲとＳ_ｊ ^Ｒについて考
えてみよう。緩和再帰部分列Ｔ_{relaxed_rec}は、有限状
態機械を緩和状態Ｓ_ｊ ^ＲがＳ_ｉ ^Ｒを完全にカバーするよ
うに緩和状態Ｓ_ｉ ^Ｒから緩和状態Ｓ_ｊ ^Ｒに遷移させる。

【００２２】緩和不活性部分列Ｔ_{relaxed_inert}は、テ
スト集合Ｔの故障シミュレーション（故障ドロッピング
をともなう）中に、この部分列内に故障が検出されない
ならば、緩和再帰部分列である。

【００２３】状態Ｓ_ｉが与えられると、サポート集合を
とり出すことによりその緩和状態を算出することができ
る。サポート集合をとり出す方法は周知である。例え
ば、本明細書中に参考として取り入れた、Ａ．Ｒａｇｈ
ｕｎａｔｈａｎらによる“Ａｃｃｅｌｅｒａｔｉｏｎ
ｔｅｃｈｎｉｑｕｅｓｆｏｒｄｙｎａｍｉｃｖｅ
ｃｔｏｒｃｏｍｐａｃｔｉｏｎ”（Ｐｒｏｃ．Ｉｎｔ
ｌ．ｃｏｎｆ．Ｃｏｍｐｕｔｅｒ−ＡｉｄｅｄＤｅｓ
ｉｇｎ、３１０−３１７頁、１９９５年）を参照された
い。組み合わせ回路の一次出力Ｚにおける応答ｖ（０あ
るいは１）を生成する入力ベクトルについて考えてみ
る。入力ベクトルは完全に指定されていてもされていな
くともよい。ベクトルは、一次入力のいくつかが指定さ
れていなければ（これらの入力には、ドントケア値Ｘが
割り当てられる）、完全には指定されない。一次出力Ｚ
のサポート集合は、以下の条件すべてを満たす信号の任
意の集合（一次入力を含む）である。

【００２４】ＳＳ１集合におけるすべての信号は、論
理値０あるいは１をとる（すなわち、どの信号も、未知
の値をとらない）。

【００２５】ＳＳ２一次出力Ｚは、集合の構成要素で
ある。

【００２６】ＳＳ３サポート集合における一次入力信
号以外の任意の信号の論理値は、サポート集合内の別の
信号の論理値によってのみ、一義的に決定される。

【００２７】条件ＳＳ２あるいはＳＳ３に反することな
く、集合内の信号を削除することができなければ、サポ
ート集合は最小である。この最小サポート集合は、最小
基数[least cardinality] のサポート集合である。最小
サポート集合はまた、極小であるが、その逆は真ではな
い。

【００２８】入力ベクトルにより、回路のいくつかの一
次出力に既知の値をとらせることができる。一次出力が
多数の場合には、条件ＳＳ２は、一次出力の各々がサポ
ート集合に含まれることを必要とするように修正され
る。サポート集合は、ある任意の入力ベクトルについて
所望の次の状態を生成するのに十分な、現在の状態にお
けるフリップフロップ値の集合を計算するために用いる
ことができる。

【００２９】図２に示すＩＳＣＡＳ８９順序ベンチマー
ク回路ｓ２７について考えてみる。この回路は、４つの
一次入力（Ｇ１、Ｇ２、Ｇ３、Ｇ４）と、１つの一次出
力（Ｇ１７）と、３個のフリップフロップ（Ｇ５、Ｇ
６、Ｇ７）と、中間論理素子Ｇ８、Ｇ９、Ｇ１０、Ｇ１
１、Ｇ１２、Ｇ１３、Ｇ１４、Ｇ１５、Ｇ１６とを有す
る。回路への入力をベクトル＜Ｇ１，Ｇ２，Ｇ３，Ｇ４
＞で表わす。順序回路の状態は、ベクトル＜Ｇ５，Ｇ
６，Ｇ７＞で与えられる。回路の初期状態を１００と
し、入力ベクトル１Ｘ１０を与えると、回路は出力値１
を出力する。入力ベクトルは、順序回路を状態１００に
遷移させる。論理シミュレーションは、有限状態機械の
初期状態が以下の３つの状態、すなわち、１０１、１１
０、あるいは、１１１のいずれかであったならば、同一
の次の状態および一次出力値が得られることを示す。こ
の例は、ある入力ベクトルについて、順序回路を同一の
次の状態および一次出力値に遷移させるいくつかの初期
状態があり得ることを示すものである。例えば、初期状
態の集合を状態ベクトル１ＸＸで簡潔に表わすことがで
きる。この状態は、４つの初期状態のすべての緩和状態
である。

【００３０】状態緩和により、故障シミュレーションに
おいて顕著な利点が得られる。緩和値を有するフリップ
フロップにおける故障結果が、一次出力やフリップフロ
ップのどれかに伝搬することはあり得ない。これは、緩
和フリップフロップ上の０あるいは１の値が一次出力や
次の状態値に何の影響も与えないからである。もう一
度、図２に例示した回路ｓ２７について検討してみる。
緩和フリップフロップＧ７上での故障結果が一次出力や
フリップフロップに伝搬することはあり得ない。これ
は、制御値Ｇ１６＝０により、一次出力やフリップフロ
ップＧ５およびＧ６に故障結果が伝搬するのが妨げら
れ、制御値Ｇ３＝１により、フリップフロップＧ７へ故
障結果が伝搬するのを妨げられるからである。

【００３１】状態緩和は、いくつかの手法を用いて達成
することができる。緩和状態を効率的に導き出すため
に、サポート集合が用いられる。サポート集合の算出
は、線形の時間・領域計算量を有する。再び、図２に示
した回路ｓ２７について考えてみる。信号（Ｇ３＝１）
のみが割り当て（Ｇ１３＝０）のためのサポート集合で
ある。一方、信号（Ｇ５＝１，Ｇ９＝１，Ｇ１６＝０，
Ｇ４＝０，Ｇ８＝０，Ｇ１４＝０，Ｇ１＝１）が組み合
わさって、（Ｇ１１＝０）のためのサポート集合を形成
する。

【００３２】理論上、テスト集合Ｔの論理シミュレーシ
ョン中に逆の順番で緩和される状態について考慮する必
要がある。このことは、緩和フリップフロップ値の数を
最大化する。テスト集合をＴ［Ｖ_１，…，Ｖ_ｎ］とし、
Ｓ_ｉ（１≦ｉ≦ｎ）を、ベクトルＶ_ｉをシミュレートす
る際の機械の状態とする。緩和値を最大にするために、
Ｓ_ｎ…Ｓ_１の順に状態を緩和することができる。フリッ
プフロップ上の次の状態値が現在の状態に対して可能な
緩和の程度を決定するため、すべての状態Ｓ_ｉ（１≦ｉ
≦ｊ）について考慮する前に、まず状態Ｓ_ｊを緩和する
ことが有用である。しかしながら、逆順での緩和のため
のメモリ記憶のコストは、非常に高い。これは、テスト
集合Ｔ内のベクトルすべてについて信号値の論理値を記
憶することを必要とする。

【００３３】これに代わる、より経済的な方法は、テス
ト集合Ｔの論理シミュレーション中に状態が現れるのと
同じ順序で、状態を緩和することである。このことは、
次の状態がまだ緩和されていないため、各状態は、完全
に指定された次の状態に対して緩和されることを意味す
る。

【００３４】テスト集合全体について数回にわたり状態
を反復緩和させることにより、サポート集合内のフリッ
プフロップ数をさらに減少させることができる。第一回
目の反復では、完全に指定された次の状態に対して各状
態を緩和し、第二回目の反復では、第一回目の反復にお
いて計算されたすでに緩和された継続する状態に対して
対応するサポート集合を計算することによりあらゆる状
態をさらに緩和させる、などである。しかしながら、状
態の反復緩和は、実行時間を増大させてしまう。実験結
果によれば、以降の完全に指定された状態に基づく最小
サポート集合がテスト集合を大幅に圧縮するのに十分で
あることが示されている。

【００３５】フリップフロップは、正常な回路と故障回
路について異なるブール値（０あるいは１）を有するな
らば、故障結果を有する。フリップフロップが正常な回
路において１（０）の値を有し、故障回路において０
（１）の値を有するならば、この値の組み合わせはＤ
（Ｄバー（図３においてＤの上にバーが付された記号
で、Ｄの反転値を表すものとする））として表わされ
る。フリップフロップは、部分列Ｔ_subにおいて第１の
ベクトルを印加する前にすでに故障結果を有し得る。同
様に、フリップフロップは、部分列が与えられた後にも
故障結果を有し得る。

【００３６】不活性部分列Ｔ_subについて考えてみる。
この部分列はある条件のもとでは、故障検出率を全く低
下させずに、テスト集合から削除することができる。不
活性部分列を与える前と与えた後でフリップフロップ上
の故障結果が同一（図３（ａ）参照）であるならば、こ
の部分列を問題なく削除することができる。しかしなが
ら、部分列を与える前と与えた後で故障結果が異なる
（図３（ｂ）参照）こともある。この状況では、部分列
を削除する前に、さらなる解析が必要となる。

【００３７】例えば、部分列を与える前には故障結果を
もたないが、部分列のシミュレーション後には、故障結
果を示すフリップフロップを考えてみよう。テスト集合
Ｔにおける残りのベクトルによって、故障結果を一次出
力に伝搬し得ないことが証明できる場合にのみ、部分列
の削除は可能である。

【００３８】再帰部分列は、（１）この部分列が不活性
部分列について指定されたすべての条件を満たし、
（２）部分列内で検出された故障がテスト集合Ｔ内のど
こか他のところでも検出できるならば、削除することが
できる。

【００３９】基本的な部分列削除アルゴリズムは以下の
とおりである。

【００４０】ｂａｓｉｃ＿ｓｕｂｓｅｑｕｅｎｃｅ＿ｒｅｍｏｖａｌ（）（基本部分列削除）／＊ＦＩＲＳＴＦＡＵＬＴＳｉｍｕｌａｔｉｏｎＰＡＳＳ＊／（第１の故障シミュレーションパス）Ｃｏｌｌｅｃｔｒｅｃｕｒｒｅｎｔ＆ｉｎｅｒｔｓｕｂｓｅｑｕｅｎｃｅｓ（再帰・不活性部分列収集）／＊ＳＥＣＯＮＤＦＡＵＬＴＳＩＭＵＬＡＴＩＯＮＰＡＳＳ＊／（第２の故障シミュレーションパス）ＦｏｒｅａｃｈｓｕｂｓｅｑｕｅｎｃｅＴ_subi ｃｏｌｌｅｃｔｅｄ（収集された各部分列Ｔ_subiについて）Ｉｆａｎｙｏｆｔｈｅｒｅｍｏｖａｌｃｒｉｔｅｒｉａｓａｔｉｓｆｉｅｄ（削除基準のいずれかが満たされたならば）ＲｅｍｏｖｅＴ_subi ｆｒｏｍｔｈｅｔｅｓｔｓｅｔ（テスト集合からＴ_subiを削除）このアルゴリズムは、２つのパスからなる。第１の故障
シミュレーションパスは、故障のない機械を仮定して不
活性および再帰部分列を識別し、収集するために用いら
れる。第２の故障シミュレーションパスは、故障のある
機械を解析することにより、不活性および再帰部分列が
部分列を削除するために指定された条件すべてを満足す
るかどうかを判断する。このツーパスアルゴリズムは、
第２のパスにおいてのみ故障状態を記録すればよいた
め、メモリを大幅に節約する。故障状態は、各不活性あ
るいは再帰部分列の境界においてのみ記録される。

【００４１】ベクトルＶ_ｉ…Ｖ_ｊからなる部分列Ｔ_sub
について考えてみる。部分列の論理シミュレーションに
おいてベクトルＶ_ｉをシミュレートする際の、機械の初
期状態をＳ_ｉとする。図４に示された場合について検討
すると、部分列Ｔ_subは、初期状態Ｓ_ｉ（１０１１）が
部分列Ｔ_subの最終状態Ｓ_j+1（０１１０）と異なるた
め、再帰部分列ではない。状態緩和によって、状態Ｓ_ｉ
の第１のフリップフロップ値および状態Ｓ_ｊの第２のフ
リップフロップ値を緩和することが可能となると仮定す
る（すなわち、これらのフリップフロップの緩和は、こ
れらのフリップフロップ値が、対応する次の状態Ｓ_i+1
あるいはＳ_j+1にそれぞれ到達するために必要ないこと
を示す）。ここで、緩和状態Ｓ_ｊ ^Ｒは、状態Ｓ_ｉにおけ
る第１のフリップフロップの非緩和値が１であるため、
緩和状態Ｓ_ｉ ^Ｒを完全にカバーする。部分列Ｔ_subをテ
スト集合から削除するとしても、回路の現在の状態がＳ
_ｊではなくＳ_ｉである場合には、ベクトルＶ_j+1を与え
ることにより、状態Ｓ_j+1に到達することは依然として
可能である。部分列Ｔ_sub内に故障が検出されなけれ
ば、部分列Ｔ_subは単に緩和不活性部分列であり、境界
条件が以下の具体例に述べられているとおりであれば、
その削除が故障検出率に影響を及ぼすことはない。故障
が部分列Ｔ_sub内に検出されたとしても、この部分列内
に検出された故障がテストシーケンス中の他のベクトル
によっても検出できるのであれば、部分列Ｔ_subを削除
することは依然として可能である。

【００４２】緩和部分列削除技術もやはり、２つの故障
シミュレーションパスを必要とする。第１のパスにおい
て、テスト集合によりトラバースされる無故障状態が緩
和される。このパスではさらに、緩和された不活性およ
び再帰部分列を識別する。第２の故障シミュレーション
パスにおいて、緩和された不活性あるいは再帰部分列を
それぞれ削除するための境界条件が調べられる。

【００４３】故障マスキングが不活性部分列内に生じる
ことがあり得る。また、緩和された不活性部分列が故障
をマスキングすることもあり得る。ここで、緩和された
不活性部分列は、対応する不活性部分列が故障をマスキ
ングしない場合であっても、故障をマスキングし得る。
ベクトルＶ_ｉ…Ｖ_ｊからなる部分列Ｔ_subを用いて、図
５（ａ）および５（ｂ）に示された例について考えてみ
る。図５（ａ）の状態Ｓ_ｉとＳ_ｊについて、いくつかの
関連するフリップフロップ値が示されている。故障回路
におけるこれらのフリップフロップ値を、図５（ｂ）に
示す。フリップフロップ値は、正常な回路において１
（０）の値とし、故障回路では０（１）の値をとるとす
ると、Ｄ（Ｄバー）で表わされる。故障シミュレーショ
ン中に、状態Ｓ_ｉにおける２つのフリップフロップが、
それぞれ、ＤおよびＤバーの故障結果を有すると仮定し
よう。ＡＮＤゲートは、ＡＮＤゲートの入力における故
障結果が互いをマスキングするため、故障結果を示さな
い。しかしながら、部分列Ｔ_subのシミュレーションの
過程において、両方のフリップフロップが同一の故障結
果Ｄバーを有し、結果としてＡＮＤゲートを越えて故障
結果が伝搬する可能性がある。この場合には、故障結果
は、ＡＮＤゲートによりマスキングされず、ＡＮＤゲー
トの出力側にとりだされた故障結果はさらに、一次出力
に伝搬する。

【００４４】次に、状態緩和シナリオについて考えてみ
る。状態Ｓ_ｊの状態緩和により、図５（ａ）に示す状態
Ｓ_ｊ ^Ｒが得られると仮定する。部分列Ｔ_subの削除は、
ベクトルＶ_ｉ…Ｖ_j-1が削除されることを意味する。し
たがって、ベクトルＶ_ｊには、部分列の削除後、現在の
状態Ｓ_ｉが加えられることになる（図５（ｂ））。変更
されたシーケンスにおいて、故障マスキングにより、Ａ
ＮＤゲートの出力に故障結果が現れることはない。まれ
にではあるが、テストシーケンス圧縮後の故障検出率
が、故障マスキングにより、若干低くなることがある。

【００４５】次に、図６を参照して、本方法のより具体
的な例について説明する。１５個のテストベクトルから
なるテスト集合を仮定する（パートＡ）。出力状態の欄
は、各テストベクトルが加えられた後の、無故障機械の
一次出力を反映している。テストベクトル３〜１２は再
帰部分列を表わす。これはテストベクトル３と１２の両
方を加えた後の、機械の出力状態が同一であるからであ
る。テストベクトル２〜１１もやはり再帰部分列であ
る。

【００４６】第１のステップは、出力状態を緩和するこ
とである。緩和状態の欄は、緩和の結果を示している。
次のステップは、緩和再帰部分列を識別することによ
り、削除候補の部分列を識別することである。このよう
な部分列の１つはテストベクトル２〜１４からなる。緩
和によって、より大きい部分列候補を識別することが可
能となる。

【００４７】ここで、この部分列候補が削除可能かどう
かを判断するために部分列の境界条件を調べなければな
らない。第１に、パートＢに示すように、テストベクト
ル２〜１３をテスト集合から削除する。次に、識別され
たすべての故障（この例では５個）について故障シミュ
レーションを実行し、出力状態を緩和させる。テストベ
クトル１４を加えることで、各故障について故障のない
機械と同じ出力状態が生成されるのであれば（緩和状態
の欄）、境界条件が満たされ、部分列候補をテストベク
トル集合から永久的に削除できる。しかしながら、パー
トＢに示すように、故障２を有するテストベクトル１４
を与えると、異なる出力状態（００）が生成される。

【００４８】このことは、部分列を削除できないことを
意味するものではないが、さらなる解析が必要とされ
る。部分列は、故障２がテストベクトルの別の部分列に
より見出だされるか、あるいは、故障２が集合内のどの
テストベクトルによっても見出だされなければ、まだ削
除可能である。ここで、テストベクトル集合のほとんど
すべてが、機械における故障すべてを検出することはな
い。これらの条件のどちらも満たさなければ、部分列候
補は削除できず、次の部分列候補が解析される。

【００４９】この例において、別の部分列候補はテスト
ベクトル２〜１３からなる。パートＣは、テストベクト
ル２〜１２を削除した後の故障シミュレーションの結果
を示している。ここで、故障シミュレーション後、テス
トベクトル１４を加えることで、故障のない機械と同じ
出力状態が生成される（緩和状態の欄）。したがって、
境界条件が満たされ、部分列候補をテストベクトル集合
から永久的に削除することが可能となる。

【００５０】このプロセスは、部分列候補のすべてを調
べ終えるまで続けられる。

【００５１】実験結果緩和再帰部分列削除アルゴリズムは、Ｃ言語において実
現された。ＩＳＣＡＳ８９順序ベンチマーク回路といく
つかの合成回路が、アルゴリズムの有効性を評価するた
めに用いられた。２５６ＭビットのＲＡＭを備えたＳｕ
ｎＵｌｔｒａＳＰＡＲＣ上で、すべての実験が行なわ
れた。２個のテストジェネレータ（ＨＩＴＥＣとＳＴＲ
ＡＴＥＧＡＴＥ）によって生成されたテスト集合は、静
的に圧縮された。ＨＩＴＥＣは、順序回路のための決定
論的テストジェネレータであり、ＳＴＲＡＴＥＧＡＴＥ
は、テストベクトルを生成するために発生論的アルゴリ
ズムを用いている。

【００５２】ＨＩＴＥＣとＳＴＲＡＴＥＧＡＴＥテスト
ベクトルについての圧縮結果を図７と図８にそれぞれ示
す。回路の故障の総数は、図７のみに示されている。ベ
クトルと故障検出率の元の数が各図に示されており、上
述したＨｓｉａｏの論文に述べられた従来の手法と、本
発明とによる圧縮結果を合わせて示す。圧縮結果には、
圧縮後の故障検出率と、元のテスト集合サイズに対する
縮小率（％）と、実行時間（秒）が含まれている。圧縮
法は、テスト集合すべてについて、不活性部分列削除と
それに続く再帰部分列削除を組み合わせた手法を用い
た。緩和再帰部分列削除アルゴリズムは、非緩和削除ア
ルゴリズムより実行時間が若干長い。これは、サポート
集合を計算するためと、削除するのに適したものとなっ
たより多くの部分列候補について検討するために余分な
時間が必要となるからである。

【００５３】ほとんどの回路について、テスト集合の大
きさが著しく縮小することが観察された。例えば、回路
ｓ１４８８とｓ１４９４において、ＨＩＴＥＣテストベ
クトルの縮小率はそれぞれ、７．９５％から３４．２
％、８．６７％から４２．７％に増加した。ｓ３５９３
２については、縮小率は４．４４％から４０．０％に増
加した。同様な傾向が他の多くの回路についても観察さ
れる。回路ｓ１４２３とｓ５３７８では、ＨＩＴＥＣテ
スト集合の元々のベクトル数が少なく、故障検出率も低
い。そこで、これらについては考察しなかった。

【００５４】ＳＴＲＡＴＥＧＡＴＥテストベクトルにつ
いても大幅な縮小が達成される。例えば、ｓ１４２３テ
ストベクトルにおいて、テスト集合は、すでに３８．１
％の縮小を達成していた従来の技術よりさらに２３％縮
小し、故障検出率が低下することはなかった。例えば、
回路ｓ２９８とｓ３４４では、緩和再帰部分列削除によ
り、テスト集合の縮小率は、これらの２つの回路につい
てそれぞれ、０％から７．７％、８．１％から２５．６
％に増加した。

【００５５】圧縮テストベクトル集合のうちには、元の
テスト集合に比べて故障検出率が若干低くなるものもい
くつかあった。これは、故障マスキングの現象によるも
のである。先に引用したＨｓｉａｏに記載されているオ
リジナル部分列削除圧縮技術にも、この問題は存在し
た。しかし、故障検出率の低下はごくわずかである。

【００５６】緩和再帰部分列削除に基づく静的テスト集
合圧縮フレームワークについて説明してきた。従来公知
の技術に比べてテスト集合の大きさの大幅な縮小が短い
実行時間で達成される。故障検出率に悪影響を与えず
に、完全に特定されたそれぞれ異なる状態に始まって終
わる部分列を削除するための十分な条件がわかった。試
行及び再試行に基づく静的圧縮法に比べて、本圧縮技術
においては、２つの故障シミュレーションパスしか必要
とされない。その結果、大規模なテスト集合と回路を、
この技術によって迅速に処理できる。さらに、状態緩和
技術は、最近提案されている多くの静的圧縮技術を大幅
に向上させるためにも用いることができる一般的なアプ
ローチである。

【００５７】以上、本発明を好ましい実施の形態につい
て説明したが、本発明の趣旨および範囲を逸脱すること
なく種々の変形が可能であることはいうまでもない。

【００５８】

【発明の効果】本発明によれば、サイクルをもたないた
めに既存の部分列削除技術では圧縮できなかったテスト
集合を圧縮することができる。また、テスト集合におけ
るサイクルのサイズを状態緩和により著しく増大させる
ことができ、より大きいサイクルを削除することで、よ
り良好な圧縮が達成される。

【００５９】本発明によればまた、多数の故障シミュレ
ーションパスを必要とする試行・再試行法と比較して、
わずか２つの故障シミュレーションパスしか必要としな
い。現在知られている部分列削除方法と比較して、短い
実行時間で、極めて高度な圧縮が達成される。

【図面の簡単な説明】

【図１】ＨＩＴＥＣテスト集合によりトラバースされた
状態の数を示す図である。

【図２】ＩＳＣＡＳ８９順序ベンチマーク回路ｓ２７を
示す図である。

【図３】部分列に入出力される故障結果が同一である場
合（図３（ａ））、及び部分列に入出力される故障結果
が異なる場合（図３（ｂ））を示す図である。

【図４】緩和された部分列の削除を示す図である。

【図５】無故障状態緩和（図５（ａ））、及び部分列削
除後の故障マスキング（図５（ｂ））を示す図である。

【図６】テストベクトル集合に本発明を適用した例を示
す図である。

【図７】ＨＩＴＥＣテスト集合についての圧縮結果を示
す図である。

【図８】ＳＴＲＡＴＥＧＡＴＥテスト集合についての圧
縮結果を示す図である。

【符号の説明】

Ｓ_ｉ、Ｓ_ｊ状態Ｖ_ｉ、Ｖ_ｊベクトル

Claims

【特許請求の範囲】

【請求項１】テストベクトル集合からテストベクトル
の部分列を削除することにより、有限状態を有する論理
回路のテスト集合圧縮を行なう方法において、（ａ）論理回路有限状態を緩和するステップと、（ｂ）削除のためにテストベクトルの部分列候補を識別
するステップと、（ｃ）上記テストベクトルの部分列候補を一時的に削除
するステップと、（ｄ）残りのテストベクトルに対して故障シミュレーシ
ョンを実行するステップと、（ｅ）故障シミュレーション結果を一組の削除基準に照
らして検査するステップと、（ｆ）上記一組の削除基準が満たされた場合に、上記部
分列候補を永久に削除するステップと、（ｇ）上記一組の削除基準が満たされない場合に、上記
部分列候補を置き換えるステップと、（ｈ）テストベクトルのすべての部分列候補が識別され
るまで、ステップ（ａ）〜（ｇ）を繰り返すステップと
を有する圧縮方法。
【請求項２】上記論理回路有限状態は、サポート集合
をとり出すことにより緩和されることを特徴とする請求
項１記載の圧縮方法。
【請求項３】上記サポート集合は、逆順にとり出され
ることを特徴とする請求項２記載の圧縮方法。
【請求項４】上記サポート集合は、正順にとり出され
ることを特徴とする請求項２記載の圧縮方法。
【請求項５】上記サポート集合は、繰り返してとり出
されることを特徴とする請求項２記載の圧縮方法。
【請求項６】上記一組の削除基準は、（ａ）上記部分列候補が、不活性であること、（ｂ）上記部分列候補により検出される故障が、上記テ
ストベクトル集合内のどこか別の箇所で検出可能である
こと、（ｃ）故障結果が、上記テストベクトル集合におけるど
のテストベクトルによっても検出できない故障の結果で
あること、の少なくとも一つからなることを特徴とする
請求項１記載の圧縮方法。