JP2000214906A

JP2000214906A - テスト生成問題解決システム及びテスト生成問題解決方法

Info

Publication number: JP2000214906A
Application number: JP11694A
Authority: JP
Inventors: T Chakuradaa Surimatto; スリマット・ティー・チャクラダー; B Doresuwamii Kiran; キラン・ビー・ドレスワミ―; Surendra K Bommu; スレンドラ・ケイ・ボムー; Rin Jijan; ジジャン・リン
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1999-01-20
Filing date: 2000-01-20
Publication date: 2000-08-04
Also published as: US6378096B1

Abstract

(57)【要約】【課題】シーケンス回路に関するテスト生成問題を解
決するための方法を提案する。【解決手段】この方法は、原テスト生成問題をより規
模の小さい副問題に再帰的に分割し、副問題が従属関係
にありながらも、１つかそれ以上の従属副問題が特定の
解に対して独立性を有することができ、副問題の解を検
出し、従属副問題が特定の解に対して独立性を有する場
合に、当該副問題の解を再使用し、複数の目標を達成す
るために解決すべき副問題に解がない場合に、対立する
目標の最小サブセットを識別する。

Description

【発明の詳細な説明】

【０００１】

【発明が属する技術分野】本発明は複合問題の解決に関
する。本発明は、特に、シーケンス回路に関するテスト
生成問題を解決する方法に関する。本発明は、問題を解
決するための方法、シーケンス回路に関するテスト生成
問題を解決するための方法、シーケンス回路テスト用の
テストベクトルを生成するための方法、テストベクトル
を生成するためのシステム、およびシーケンス回路に関
するテスト生成問題を解決するためのコンピューター・
コードを備えるコンピューター・プログラム製品として
実施される。

【０００２】

【従来の技術】複合問題は大規模な制約セットによって
定義されることが多い。シーケンス回路をテストするた
めのテスト生成は、こうした複合問題の一例である。問
題によっては、解を得るための現実的な方法はオンライ
ン解法しかない。図２０に、オンライン解法を説明する
フローチャートを示す。これらのオンライン解法による
と、（２０．１）および（２０．２）で示すように、主
問題の１つの副問題に対応する制約サブセットがまず考
慮される。この副問題について解が導き出される（２
０．３）。こうした副問題の解は主問題の１つの制約サ
ブセットだけを満足するので、「部分解」と呼ばれる。
副問題の部分解が存在しない場合は、主問題自体の解も
ないことは明らかである。この場合は、解の存在を阻む
制約サブセットが識別される（２０．４）。

【０００３】次に、部分解が主問題のさらに別の制約を
すべて満足するかどうかのチェックが行われる（２０．
５）。部分解がこれらの追加の制約を満足する場合は、
部分解自体が主問題の完全解となる（２０．６）。当該
副問題に対応する制約の一部を成さない追加の制約を部
分解が満足しない場合、オンライン解法では当該副問題
に関する制約サブセットが増補される。これは、１つか
それ以上の追加の制約を組み込むことによって行われる
（２０．７）。オンライン解法では、増補の後、別の部
分解が導き出される。図２０のループに示すように、こ
のプロセスは、すべての制約を満足する部分解が導き出
されるか、制約サブセットが部分解を持たないと判断さ
れるまで繰り返される。通常は、すべての制約が考慮さ
れる最終反復のかなり前に、解が検出されるか、解の不
在が確立されるかのいずれかである。

【０００４】オンライン解法の一例としては、従来の時
間フレーム展開法が挙げられる。ここで、従来の時間フ
レーム展開法を使用してシーケンステスト生成問題を解
決する場合について考察する。時間フレーム展開法につ
いては、以下の参考文献で詳細に記述されている。Ｇ．
Ｒ．ＰｕｚｏｌｕａｎｄＪ．Ｐ．Ｒｏｔｈ，
“ＡＨｅｕｒｉｓｔｉｃＡｌｇｏｒｉｔｈｍｆｏ
ｒｔｈｅＴｅｓｔｉｎｇｏｆＡｓｙｎｃｈｒｏ
ｎｏｕｓＣｉｒｃｕｉｔｓ（非対称回路のテストのた
めのヒューリスティック・アルゴリズム）”，ＩＥＥ
ＥＴｒａｎｓ．ｏｎＣｏｍｐｕｔｅｒｓ，ｐ
ｐ．６３９−６４７，Ｊｕｎ．１９７１、Ｒ．
Ｍａｒｌｅｔｔ， “ＡｎＥｆｆｉｃｉｅｎｔＴｅ
ｓｔＧｅｎｅｒａｔｉｏｎＳｙｓｔｅｍｆｏｒ
ＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔｓ（シーケンス
回路のための効率的なテスト生成システム）”，２３
ｒｄＤｅｓｉｇｎＡｕｔｏｍａｔｉｏｎＣｏｎｆｅ
ｒｅｎｃｅ，Ｊｕｎｅ１９８６，ｐｐ．２５０−
２５６、Ｈ−Ｋ．Ｔ．Ｍａ，ｅｔ．ａｌ．，
“ＴｅｓｔＧｅｎｅｒａｔｉｏｎｆｏｒＳｅｑｕ
ｅｎｔｉａｌＣｉｒｃｕｉｔｓ（シーケンス回路のた
めのテスト生成）”，ＩＥＥＥＴｒａｎｓ．ｏｎ
Ｃｏｍｐｕｔｅｒ−ＡｉｄｅｄＤｅｓｉｇｎ，Ｖ
ｏｌ．７，Ｎｏ．１０，ｐｐ．１０８１−１０９
３，Ｏｃｔ．１９８８、Ｍ．Ｓｃｈｕｌｚａｎ
ｄＥ．Ａｕｔｈ， “ＥＳＳＥＮＴＩＡＬ：Ａｎ
ＥｆｆｉｃｉｅｎｔＳｅｌｆ−Ｌｅａｒｎｉｎｇ
ＴｅｓｔＰａｔｔｅｒｎＧｅｎｅｒａｔｉｏｎＡ
ｌｇｏｒｉｔｈｍＦｏｒＳｅｑｕｅｎｔｉａｌＣ
ｉｒｃｕｉｔｓ（基本：シーケンス回路のための効率
的な自己学習テストパターン生成アルゴリズム）”，
１９８９ＩｎｔｅｒｎａｔｉｏｎａｌＴｅｓｔＣ
ｏｎｆｅｒｅｎｃｅ，ｐｐ．２８−３７、Ｗ．Ｃ
ｈｅｎｇａｎｄＴ．Ｃｈａｋｒａｂｏｒｔｙ，
“Ｇｅｎｔｅｓｔ −− ＡｎＡｕｔｏｍａｔｉｃ
ＴｅｓｔＧｅｎｅｒａｔｉｏｎＳｙｓｔｅｍｆｏ
ｒＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔｓ（Ｇｅｎ
ｔｅｓｔ −− シーケンス回路のための自動テスト生
成システム）”，ＩＥＥＥＣｏｍｐｕｔｅｒｐ
ｐ．４３−４９，Ａｐｒｉｌ１９８９、Ｄ．Ｈ．
ＬｅｅａｎｄＳ．Ｍ．Ｒｅｄｄｙ， “ＡＮｅｗ
ＴｅｓｔＧｅｎｅｒａｔｉｎＭｅｔｈｏｄｆｏｒ
ＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔｓ（シーケン
ス回路のための新しいテスト生成法）”，Ｐｒｏｃ．
ｏｆＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅ
ｎｃｅｏｎＣｏｍｐｕｔｅｒＡｉｄｅｄＤｅｓ
ｉｇｎ，ｐｐ．４４６−４４９，１９９１、Ｔ．
ＮｉｅｒｍａｎｎａｎｄＪ．Ｐａｔｅｌ， “ＨＩ
ＴＥＣ：ＡＴｅｓｔＧｅｎｅｒａｔｉｏｎＰａ
ｃｋａｇｅｆｏｒＳｅｑｕｅｎｔｉａｌＣｉｒｃ
ｕｉｔｓ（ＨＩＴＥＣ：シーケンス回路のためのテスト
生成パッケージ）”，ＥｕｒｏｐｅａｎＣｏｎｆ．
ｏｎＤｅｓｉｇｎＡｕｔｏｍａｔｉｏｎ１９９
１，ｐｐ．２１４−２１８、およびＴ．Ｋｅｌｓｅ
ｙ，Ｋ．Ｓａｌｕｊａ，ａｎｄＳ．Ｌｅｅ，
“ＡｎＥｆｆｉｃｉｅｎｔＡｌｇｏｒｉｔｈｍｆ
ｏｒＳｅｑｕｅｎｔｉａｌＣｉｒｃｕｉｔＴｅｓｔ
Ｇｅｎｅｒａｔｉｏｎ（シーケンス回路テスト生成の
ための効率的なアルゴリズム）”，ＩＥＥＥＴｒａ
ｎｓ．ｏｎＣｏｍｐｕｔｅｒ，ｖｏｌ．４２，
ｐｐ．１３６１−１３７１，Ｎｏｖ．１９９３。

【０００５】

【発明が解決しようとする課題】時間フレーム展開法で
は、シーケンス回路に関するテスト生成問題が副問題に
分割される。各副問題は、対応する時間フレームによっ
て識別される。これらの副問題は互いに独立していな
い。副問題間の従属関係は、ある時間フレームについ
て、状態変数入力によって想定できる（または、想定で
きない）値の組み合わせに制約があるときに生じる。し
かし、ある時間フレームが近傍の時間フレームから受け
るすべての制約を明示的に決定することもまた困難であ
る。さらに、この決定は原テスト生成問題を解決するの
と同程度に困難となることもある。それは、状態変数値
の合法的な組み合わせと違法な組み合わせのすべてを決
定するためには、ときに法外な計算資源が必要となるか
らである。しかも、ターゲットとする故障に関して考慮
しなければならない副問題（時間フレーム）の数が不明
なこともある。こうした事情から、代わりに、（時間フ
レームに対応する）副問題の１つの部分解は、近傍の時
間フレームから受ける制約を無視して決定される。その
結果得られる部分解は、無視された制約を満足しないこ
とがある（例えば、部分解が正当化できない現在状態を
必要とする場合など）。満足されない制約を追加する
と、その副問題の初期制約セットが増補され、これによ
って新たな部分解が導き出される。このことから、シー
ケンステスト生成で使用される時間フレーム展開法がオ
ンライン解法であることは明らかである。

【０００６】換言すれば、オンライン解法とは、関連す
る一連の問題Ｐ_１，・・・，Ｐ_ｎを解決することによっ
て解を導き出す方法である。ここで、（１）問題Ｐ_ｉ
（１≦ｉ≦ｎ−１）を定義する制約セットは、問題Ｐ
_ｉ＋１に関する制約セットのサブセットであり、（２）
問題Ｐ_ｉ＋１に関する制約は、通常、問題Ｐ_ｉの解を
導き出す間には不明である。

【０００７】Ｐ_１の解の検出にアルゴリズムを使用でき
る場合は、各Ｐ_ｉ（１≦ｉ≦ｎ）を互いに独立した問題
とみなすことにより、同じアルゴリズムを繰り返し使っ
て問題Ｐ_２，・・・，Ｐ_ｎの解を導き出すことができ
る。ただし、これはオンライン解法で解を検出する方法
としては効率的なものではない。

【０００８】一般に、問題は副問題に再帰的に区分化す
ることによって解決される。区分化を行うと、以下の２
点を期待できるようになる。

【０００９】（１）副問題を互いに独立して解決する
ことができる。および、（２）副問題の解を結合し
て、原問題の解を導き出すことができる。

【００１０】副問題が互いに独立しているのは、副問題
の解を検出する際にチェックすべき検索スペースが互い
に独立している場合である。ただし、副問題間の独立性
を必須にすると、１つの副問題が原問題と同程度の規模
になる恐れがあることは明らかであろう。

【００１１】当業者の間では、オンライン解法で再帰的
な区分化を使用するとさらに別の問題点が発生すること
はよく知られている。問題Ｐ_ｉについて管理可能で独立
した区分を導き出すことができたとしても、これらの区
分が問題Ｐ_ｉ＋１にとっても独立した区分であるとは限
らない。それは、問題Ｐ_ｉ＋１に組み込まれた追加の制
約によって、Ｐ_ｉ内の独立副問題に従属関係が発生する
可能性があるからである。

【００１２】本発明の目的は、前述の問題点を解消した
改良型オンライン問題解法を提供することにある。本発
明の具体的な目的は、区分化された副問題が従属関係を
持つことのできる、シーケンス回路に関するテスト生成
問題を解決するためのオンライン解法を提供することに
ある。本発明の他の具体的な目的は、シーケンス回路テ
スト用のテストベクトルを生成するための改良型生成法
を提供することにある。

【００１３】

【課題を解決するための手段】本発明の目的を達成する
ため、下記要件を備えるシーケンス回路に関するテスト
生成問題を解決するための方法が提供される。すなわ
ち、原テスト生成問題をより規模の小さい副問題に再帰
的に分割し、前記副問題が従属関係にありながらも、１
つかそれ以上の前記従属副問題が特定の解に対して独立
性を有することができる。前記副問題の解を検出する。
従属副問題が特定の解に対して独立性を有する場合に、
当該副問題の解を再使用する。および、複数の目標を達
成するために解決すべき副問題に解がない場合に、対立
する目標の最小サブセットを識別する。

【００１４】本発明の他の態様は、シーケンス回路をテ
ストするためのテストベクトルを生成する方法であっ
て、前記方法は下記要件を備える。すなわち、テスト生
成問題を識別する。次の決定変数を選択する。当該決定
変数の次の値を選択する。選択された値が無矛盾ラベル
付けに対応するかどうかチェックし、無矛盾ラベル付け
が存在しない場合は、対立セットを戻す。前記チェック
により無矛盾ラベル付けが検出された場合は、以下の３
つのサブステップを実行する。すなわち、（１）テスト
生成問題を副問題に区分化して、前記副問題の各々に本
請求の方法を再帰的に適用する、（２）現在の副問題に
解が存在せず、従属区分が存在する場合は、前記従属区
分をマージする、および（３）現在の副問題に解が存在
せず、従属区分も存在しない場合は、終了する。上記サ
ブステップを実行した後、前記チェックで矛盾ラベル付
けが検出された場合で、変数が現在の区分の一部ではな
い場合に、矛盾ラベル付けを発生させる変数を追加す
る。選択された変数のすべての値について繰り返す。す
べての変数について繰り返す。および、解が検出された
場合は解を戻し、検出されなかった場合は識別された対
立セットを戻す。

【００１５】本発明の他の態様は、問題を解決する方法
であって、前記方法は下記要件を備える。すなわち、問
題をより規模の小さい副問題に再帰的に分割し、前記副
問題が従属関係にありながらも、１つかそれ以上の前記
従属副問題が特定の解に対して独立性を有することがで
きる。前記副問題の解を検出する。従属副問題が特定の
解に対して独立性を有する場合に、当該副問題の解を再
使用する。および、複数の目標を達成するために解決す
べき副問題に解がない場合に、対立する目標の最小サブ
セットを識別する。

【００１６】本発明の他の態様は、コンピューターを備
えるテスト生成システムであって、前記コンピューター
がＣＰＵとメモリーを有し、前記メモリーが前記システ
ムのコンポーネントを実装することのできる命令を備
え、前記コンポーネントは下記要件を備える。すなわ
ち、テスト生成問題を再帰的に解決するためのテスト生
成問題ソルバーであって、副問題の解が再使用される。
テスト生成問題を受け取り、前記テスト生成問題を副問
題に区分化するための問題パーティショナーであって、
前記副問題が従属関係にあることができ、前記副問題が
特定の問題に対する従属性を有することができる。問題
ソルバーからテスト生成問題を受け取り、無矛盾ラベル
付けが存在するかどうかを判断するための無矛盾ラベル
チェッカー。副問題の前記サブセットの解が存在せず、
副問題の前記サブセットが従属関係にある場合に、副問
題のサブセットをマージするための区分マージャー。お
よび、特定の副問題が解を持つことを阻む目標の対立セ
ットを生成するための対立セット・ジェネレーター。

【００１７】本発明のさらに他の態様は、命令を有する
コンピューター読み取り可能媒体を備えるコンピュータ
ー・プログラム製品であって、前記命令はコンピュータ
ーがテスト生成問題を解決することを可能にし、前記命
令が下記要件を備える。すなわち、コンピューターがテ
スト生成問題を再帰的に解決することを可能にするため
のテスト生成問題ソルバーであって、副問題の解が再使
用される。コンピューターがテスト生成問題を受け取
り、前記テスト生成問題を副問題に区分化することを可
能にする問題パーティショナー・コードであって、前記
副問題は従属関係にあることができ、前記副問題は特定
の解に対して従属性を有することができる。コンピュー
ターが問題ソルバーからテスト生成問題を受け取ること
を可能にし、無矛盾ラベル付けが存在するかどうかを判
断するための無矛盾ラベル・チェッカー・コード。副問
題の前記サブセットの解が存在せず、副問題の前記サブ
セットが従属関係にある場合に、コンピューターが副問
題のサブセットをマージすることを可能にする区分マー
ジャー・コード。および、コンピューターが特定の副問
題が解を持つことを阻む目標の対立セットを生成するこ
とを可能にする対立セット・ジェネレーター・コード。

【００１８】

【発明の実施の形態】オンライン解法の適用を必要とす
る問題を解決するための新規な手法が提供される。本発
明の手法では、以下を行う新規なオンライン区分化手法
が使用される。

【００１９】（１）副問題の部分解を検出する。およ
び、（２）オンライン解法によって解決された連続する
問題の間に存在しうる有意な類似性を認識し、形式化
し、活用する。

【００２０】オンライン区分化は、以下の３点において
従来の区分化とは大きく異なる。

【００２１】（１）副問題が独立していなくてもよい。

【００２２】（２）分岐・結合検索プロセス中に、問題
が数回にわたって再区分化される。

【００２３】（３）区分が明示的に計算されない。

【００２４】副問題は独立している必要はないので、複
合問題をより小規模で管理可能な副問題に分割すること
ができる。このようなプロセスでは、区分間の従属関係
が検索プロセス中にオンザフライで認識される。検索プ
ロセス中の各決定後に問題が再区分化されるので、大規
模な問題の場合は区分化コストがかなりのレベルとな
る。ただし、すべての区分を明示的に計算する必要がな
いことに留意する必要がある。オンライン区分化は、従
来型区分化が持つ以下の利点を継承している。

【００２５】（１）副問題の部分解を容易に結合して、
問題全体の解を得ることができる。および、（２）複数
の同一の副問題が同じ解を共有できる。（オンライン区分）本発明の第１の実施例について、図
１に示すサンプル回路を使用して説明する。この回路
は、ａ、ｂ、ｃ、ｄ、ｅという５個の１次入力を備え
る。この回路は、７個の排他ＯＲゲート１．１〜１．７
を備える。１次出力は、信号１のみである。目標は、信
号ｊ上の０値縮退故障に関するテストを検出することで
ある。０値縮退故障は、特定の信号が、回路の他の部分
が変動しているにもかかわらず値０のまま動かない状態
を示す。この問題は、２個の独立副問題Ｓ_１＝｛ａ，
ｂ，ｃ，ｆ，ｇ，ｈ，ｉ，ｊ｝とＳ_２＝｛ｄ，ｅ，ｋ｝
に分割される。副問題Ｓ_１の副目標は、信号ｊに値１を
取らせる入力ａ、ｂ、およびｃの値を検出することであ
る。第２の副問題の副目標は、信号ｋに値０または１を
取らせる入力ｄおよびｅの値を検出することである。Ｓ
_１の解が得られると、故障が活動化される。Ｓ _２の解が
得られると、故障の影響が１次出力１に伝搬される。こ
こで、Ｓ_１およびＳ_２は共通の信号を持たないことに留
意する必要がある。そのため、２個の副問題は互いに独
立している。この実施例では、副問題が互いに独立して
いることは明らかである。

【００２６】テスト生成問題の区分化は、静的区分化と
して知られている。区分化により以下の３つの利点が得
られる。

【００２７】（１）どの副問題にも解が存在しない場
合、故障は冗長である。

【００２８】（２）副問題Ｓ_１またはＳ_２を解決するの
は１回だけでよい。および、（３）副問題の解を単純に
構成する（結合する）だけで、原問題の解が得られる。

【００２９】このサンプル回路では、副問題Ｓ_１および
Ｓ_２の目標を満足する１次入力の値が、当該故障のため
のテストとなる。副問題は互いに独立しているので、ど
んな順序で解決してもよい。Ｓ_１の解決に分岐・結合プ
ロシージャーを使用する場合、このプロシージャーが検
査しなければならない信号ａ、ｂ、およびｃの値の組み
合わせは、多くて８組である。このサンプル回路では、
副問題Ｓ_１に解が存在しない。この場合に検索プロシー
ジャーが行うバックトラックは多くて８回である。Ｓ_１
に解が存在しないので、副問題Ｓ_２を解決する必要はな
い。

【００３０】区分化を使用しない場合、原問題を解決す
るための分岐・結合プロシージャーは非常に効率が悪く
なる。ここでも、信号ｊの０値縮退故障に関するテスト
を検出する問題（図１）について考察する。この解は、
１次入力の値のさまざまな組み合わせを系統だって検査
することによって決定される。この解を検出するため
に、分岐・結合プロシージャーを使用すると想定する。
すべての１次入力は、決定変数である。分岐・結合プロ
シージャーが、ｄ、ｅ、ａ、ｂ、およびｃの順序で決定
変数に値を割り当てると想定する。故障は冗長なので、
５個の決定変数値における３２通りの組み合わせはいず
れもテストではない。そのため、解が存在する可能性が
ないことを確立するために、分岐・結合プロシージャー
が必要とするバックトラックは３２回にもなりうる。決
定変数ａ、ｂ、およびｃは副問題Ｓ _１の一部であり、変
数ｄおよびｅは副問題Ｓ_２の一部である。選択された決
定順序により、副問題Ｓ_２はＳ_１の前に考慮されること
が暗黙に定義される。分岐・結合プロシージャーは副問
題Ｓ_２の４個の解を決定する。これは、Ｓ_２が２個の決
定変数ｄおよびｅを持ち、これらの変数の値のどの組み
合わせもＳ_２の解となるからである。副問題Ｓ_１はＳ_２
の各解について１回ずつ解決される。そのため、分岐・
結合プロシージャーは副問題Ｓ_１を４回も解決すること
になる。これとは対照的に、区分化方式では、ワースト
・ケースでも、Ｓ_１またはＳ_２の１個の解について１回
検査するだけでよい。さらに、Ｓ_１またはＳ_２に解がな
い場合、故障は冗長であることが確立される。

【００３１】区分化が有利なことは明白である。ただ
し、問題をより小規模な独立副問題に分割できないケー
スが多々ある。図２は、サンプル回路を使用して本発明
の第２の実施例を説明したものである。この回路は６個
の１次入力と１個の１次出力を備える。この回路は、３
個の排他ＯＲゲート２．１〜２．３、２個のＯＲゲート
２．４および２．５、および１個のＡＮＤゲート２．６
を備える。ここで、信号ｇ上の０値縮退故障に関するテ
ストベクトルを生成する問題について考察する。ゲート
ｊはドミネーターなので、故障のない回路ではｇ＝１お
よびｈ＝ｉ＝０という信号割り当てを必須割り当てとし
て実行できる。

【００３２】次のステップは、１次入力に適切な値を選
択することによって、これらすべての割り当てを正当化
することである。初期区分は、信号｛ａ，ｂ，ｃ，ｄ，
ｅ，ｆ，ｇ，ｈ，ｉ，ｊ｝から成る。目標ｇ＝１は、信
号｛ａ，ｂ，ｅ｝から成る副回路（副問題）Ｓ_１を考慮
することによって達成できる。目標ｈ＝０は、副問題Ｓ
_２＝｛ａ，ｂ，ｅ｝を考慮することによって達成でき
る。目標ｉ＝０は、副問題Ｓ_３＝｛ｂ，ｃ，ｄ，ｆ｝を
考慮することによって達成できる。副問題Ｓ_１およびＳ
_２は、共通の信号ａ、ｂ、およびｅを有する。これらの
信号への値の割り当ては、両方の副問題の目標を満足す
るように行わなければならない。そのため、副問題Ｓ_１
およびＳ_２は互いに独立していない。同様の分析によ
り、副問題Ｓ _２およびＳ_３も互いに独立していないこと
が示される。そのため、原問題を静的に独立副問題に小
分割することは不可能である。第２の実施例では、副問
題は互いに独立していない。

【００３３】２個の副問題Ｓ_１およびＳ_３は従属関係に
ある。ただし、副問題Ｓ_３の一部の解については、この
２個の副問題は互いに独立していると考えることができ
る。例えば、副問題Ｓ_３の解としてｄ＝０が可能であ
る。この解については、信号ｂ、ｃ、またはｆの値は副
問題Ｓ_３により制約を受けない。そのため、これらの変
数は副問題Ｓ_１の目標だけを満足する値を取ることがで
きる。よって、Ｓ_１に解が存在しなければ、原問題にも
解は存在しないと結論付けて安全である。本サンプル回
路の場合、信号ａおよびｂの値における組み合わせの中
で、目標ｇ＝１およびｈ＝０を同時に満足できるものは
ない。Ｓ_３の解がｂ＝ｃ＝０とすると、副問題Ｓ_１およ
びＳ_３は互いに独立していない。これは、Ｓ_３が解決さ
れた後に、副問題Ｓ_ｉがｂ＝０との想定のもとで解決さ
れるからである。この場合、Ｓ_１に解が存在しなくて
も、原問題に解が存在しないとは結論付けることはでき
ない。

【００３４】本発明のオンライン区分化の主眼は、問題
をより小規模な、従属関係にあることができる副問題に
分割することにある。副問題が独立しているかどうかの
判断は、副問題について検出された特定の解を分析する
ことによって行われる。独立副問題に解が存在しない場
合は、原問題に解が存在しないことが示唆される。ただ
し、副問題Ｓ_ｉの特定の解が副問題Ｓ_ｊの独立性を示さ
ない場合は、Ｓ_ｊに解が存在しないことはＳ_ｉに異なる
解が検出されうることを示唆するにとどまる。（テスト
ベクトルを生成するためのオンライン区分化方法の好適
な実施の形態）図２１に、オンライン区分化方法の好適
な実施例のフローチャートを示す。原テスト生成問題２
１．１は、副問題２１．２に分割される。２１．３で、
アルゴリズムは副問題ごとにループに入る。解決すべき
副問題がさらに存在する場合は、２１．４で未解決の副
問題が選択される。ステップ２１．５でテストが実行さ
れ、その副問題が解決可能かどうか判断される。選択さ
れた副問題が解決不能な場合は、２１．７で対立目標セ
ットが識別される。副問題が解決可能な場合、選択され
た副問題は再帰的に解決される。この副問題の解決にお
いては、従属副問題の解が再使用される。２１．９で
は、すべての副問題が解決されたかどうか判断するため
のテストが実行される。すべての副問題が解決されてい
る場合は、２１．８で解が戻され、解決されていない場
合は、２１．９１で対立目標セットが戻される。

【００３５】この新規なオンライン区分化手法の一般的
フレームワークは、図２５に示すアルゴリズム１に示さ
れている。ここで、１つの例を取り上げて、当該アルゴ
リズムの主プロシージャーについて説明する。図３に示
す回路を、この好適な実施例を説明するための例として
取り上げる。このサンプル回路は、排他ＯＲゲートｇ１
〜ｇ４およびｇ６〜ｇ８、ＯＲゲートｇ５およびｇ９、
および出力信号ｙを有する１個のＡＮＤゲートを備え
る。１次入力は、ａ、ｂ、ｃ、ｄ、およびｅである。信
号ｙ上の０値縮退故障に関するテストを生成するという
問題があるとする。この問題の決定変数セットは、１次
入力｛ａ，ｂ，ｃ，ｄ，ｅ｝である。関数ＮＥＸＴ＿Ｄ
ＥＣＩＳＩＯＮ＿ＶＡＲＩＡＢＬＥ、ＰＡＲＴＩＴＩＯ
ＮＮＥＸＴ＿ＵＮＳＯＬＶＥＤ＿ＰＡＲＴＩＴＩＯ
Ｎ、およびＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧ
は、変数と区分の順序付けを決定する検索である。これ
らは、さまざまな方法で実装できる。これらを実際にど
のように実装するかによって、アルゴリズムの実行時間
に劇的な差が生じうる。効率的な実装については本明細
書で後述する。

【００３６】アルゴリズム１の挙動は、図４のようなＡ
ＮＤ−ＯＲツリーとしてグラフィカルに描写することが
できる。ツリーの各ノードは、括弧で囲んだ信号リスト
によって示される区分か∧のいずれかである。区分によ
って示されるノードは、ＯＲノードに対応する。ここで
は、各子ノードは、区分の信号に値が割り当てられたと
きに発生する問題を表す。ここでは、各分岐の下で１つ
の解が検出されなければならない。∧で示される各ノー
ドはＡＮＤノードを表す。これらのノードの子ノード
は、親決定から生じる区分を示す。ここでは、解決すべ
き問題に関して、これらすべての区分が解決されなけれ
ばならない。太線の矢印は、回路の無矛盾ラベル付けを
表す。「ｃｏｎｆｌｉｃｔ（対立）」のラベルが付けら
れた細線の矢印は、矛盾信号ラベル付けを表す。これら
のラベルに関連付けられた括弧内の信号リストは、矛盾
を引き起こした割り当てのリストを示す。関数ＣＯＮＳ
ＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧが「矛盾」と判断する
とき、このリストが戻されると想定される。

【００３７】オンライン解決への最初の呼び出しは、Ｏ
ＮＬＩＮＥ＿ＳＯＬＶＥ（Ｃ＝｛ａ，ｅ，ｃ，ｄ，
ｂ｝）である。第２行のＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿
ＶＡＲＩＡＢＬＥ（ｃ）の呼び出しによって、決定変数
ａが戻されると想定する。これは０に設定されているの
で、ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧは矛盾信
号割り当てを検出しない。第７行でＰＡＲＴＩＴＩＯＮ
が呼び出され、｛ｅ，ｃ｝および｛ｄ，ｂ｝という２個
の区分を戻される。

【００３８】次の試行は区分｛ｅ，ｃ｝に対して行われ
ると想定すると、次の再帰呼び出しはＯＮＬＩＮＥ＿Ｓ
ＯＬＶＥ｛ｅ，ｃ｝である。この区分は、以降の再帰呼
び出しでｅを０に、続いてｃを０に設定することにより
解決される。このプロセスは、図４のＡＮＤ−ＯＲツリ
ーにおける左側の分岐に対応する。

【００３９】次の試行は区分Ｃ＝｛ｄ，ｂ｝に対して行
われる。ＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲＩＡＢＬ
Ｅ（ｃ）が、決定変数ｄを戻すと想定する。ｄを０に設
定すると、ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧは
ｇ７上で対立項は｛ｄ，ｅ｝を持つ対立を検出する。制
御は第２０行に転送される。この対立項には区分の一部
を成すｄが含まれているので、関数ＶＡＲＩＡＢＬＥ＿
ＩＮＤＥＰＥＮＤＥＮＴ＿ＰＡＲＴＩＴＩＯＮは偽を戻
す。制御は第４行に転送され、ｄが１に設定される。関
数ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧはｇ８上の
矛盾を戻す。ここでも対立項は｛ｄ，ｅ｝である。この
対立項は、現在の区分｛ｄ，ｂ｝のメンバーであるｄを
含むので、関数ＶＡＲＩＡＢＬＥ＿ＩＮＤＥＰＥＮＤＥ
ＮＴ＿ＰＡＲＴＩＴＩＯＮは偽を戻す。上記は、図４の
ＡＮＤ−ＯＲツリーのａ＝０，ｄ＝１分岐上にグラフィ
カルに描かれている。

【００４０】変数ｄの両方の値に対する試行が完了して
いるので、第４行のテストはＶ_ｖａ _ｌｕｅに対してＮＵ
ＬＬを戻す。これにより、第１０行でＯＮＬＩＮＥ＿Ｓ
ＯＬＶＥ｛ｄ，ｂ｝がＮＯを戻す。この時点で、区分
｛ｄ，ｂ｝は区分｛ｅ，ｃ｝に従属していることが判明
する。そのため、これらの区分は第１４行でマージされ
る。制御は第９行に移動する。ここでは、先ほどマージ
された区分の解の検出が試行される。ＯＮＬＩＮＥ＿Ｓ
ＯＬＶＥ（ｅ，ｃ，ｄ，ｂ）が呼び出される。これは、
適応区分化の一例である。区分化の決定が行われたとき
には、｛ｅ，ｃ｝と｛ｄ，ｂ｝間の区分従属関係は明ら
かではなかった。この従属関係は後の段階で検出され、
その時点で区分のマージが実行された。続いて、このマ
ージされた区分について解の検出が試行される。このマ
ージは、図４内の対応するＯＲノードの隣にアスタリス
クを付けることによって示される。

【００４１】次の再帰呼び出しは、ＯＮＬＩＮＥ＿ＳＯ
ＬＶＥ（Ｃ＝｛ｅ，ｃ，ｄ，ｂ｝）である。第２行のＮ
ＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲＩＡＢＬＥ（ｃ）が
ｅを戻すと想定する。信号ｅはその後０に設定される
（第４行のＮＥＸＴ＿ＶＡＬＵＥ（ｅ））。続いて、第
７行のＰＡＲＴＩＴＩＯＮ（Ｃ＝｛ｅ，ｃ，ｄ，ｂ｝）
が２つの区分｛ｃ｝および｛ｄ，ｂ｝を戻す。次に
｛ｃ｝が選択されると想定すると、変数ｃが０に設定さ
れ、それにより無矛盾ラベル付けが発生する。次の試行
は区分｛ｄ，ｂ｝に対してなされる。ｄへのいずれの割
り当ても、矛盾ラベル付けを発生させる結果となる。Ｃ
ＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧへのいずれの呼
び出しでも、ｃから独立した対立セットが戻される。そ
のため、この区分化の失敗は、その兄弟区分から独立し
ていると考えられる。そのため、親区分へのバックトラ
ックが行なわれ、次に信号ｅ上で１の値について試行が
なされる。以上は、区分が独立しており、解が存在しな
いことを確立するために構成要素の信号の全組み合わせ
について試行する必要がないケースの説明である。

【００４２】ｅを１に設定すると、同じ２つの区分
｛ｃ｝および｛ｄ，ｂ｝が発生する。ここで、区分
｛ｄ，ｂ｝の失敗は区分｛ｃ｝に従属すると考えられ
る。その結果、この兄弟区分はマージされる。次に行わ
れる再帰呼び出しは、ＯＮＬＩＮＥ＿ＳＯＬＶＥ（Ｃ＝
｛ｃ，ｄ，ｂ｝）である。これも、｛ｃ｝と｛ｂ，ｄ｝
間の区分従属関係が事前に明らかとなっていないケース
である。よって、対立により従属関係が明らかになる
と、従属区分がマージされる。

【００４３】図４には、制御フローのその他の部分も描
かれている。次に試行されるのは、マージされた区分
｛ｃ，ｄ，ｂ｝である。最終解は、図４の右端の分岐に
描かれている。最終信号割り当ては、ａ＝１，ｂ＝０，
ｃ＝０，ｄ＝１、ｅ＝１である。この値の割り当てが、
出力信号ｙ上の０値縮退故障に関するテストを構成す
る。

【００４４】（テストベクトルを生成するためのオンラ
イン区分化方法の効率的な実装を示すもっとも好適な実
施例）図２６に示すアルゴリズム２は、オンライン区分
化の概念の効率的な実装を示すもっとも好適な実施例を
示している。この実装では、特に、従属関係にありうる
区分が特定の解に対して有する独立性を決定および活用
し、その区分を再使用する方法が記述されている。

【００４５】アルゴリズム２は、汎用オンライン区分化
アルゴリズムの効率的な実装を提供する。ここでは、特
定の解に対する独立性を効率的に実装するために必要な
主要データ構造、区分の解の再使用、および初期目標の
対立目標の選択について説明する。区分化概念の中核を
成す主データ構造は、ｐａｒｔｉｔｉｏｎ_ｄｂ（区分の
データベース）と呼ばれる。これは、有向グラフとして
実装される。グラフ内の各ノードは、その親によって暗
黙に定義される。そのため、ソース・ノードは決定ポイ
ントである。したがって、このグラフ内の連結されたコ
ンポーネントは、回路内の関連区分に対応する。

【００４６】このアルゴリズムは関数ＢＡＣＫＴＲＡＣ
ＫおよびＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳＥを使用する。
これらの関数にはこの新規な手法の核心部分が組み込ま
れている。これらの関数に可能な実装を、図２７のアル
ゴリズム３、および図２８のアルゴリズム４に示す。そ
の他の関数の実装については、文脈から明らかであろ
う。この節の残りの部分では、これらの関数について説
明する。

【００４７】関数ＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲ
は、決定変数をピックするために使用される。この関数
は、Ｍｅｒｇｅｄ＿ｐａｒｔｉｔｉｏｎ_ｄｂの内容に従
って変数をピックする。このデータベースは、非結合セ
ットのツリー・ベース実装であると想定される。Ｍｅｒ
ｇｅｄ＿ｐａｒｔｉｔｉｏｎ_ｄｂには、検索プロセスに
おける対立によって関連付けられた区分のセットが保持
される。関数ＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲは、
Ｓｔａｃｋの現在の最上位と同じセットに帰属する、未
だ割り当てられていない変数を戻そうとする。これによ
り、可能な限り同じ区分から、連続する変数が確実にピ
ックされるようになる。

【００４８】この例では、関数ＮＥＸＴ＿ＤＥＣＩＳＩ
ＯＮ＿ＶＡＲは、Ｍｅｒｇｅｄ＿ｐａｒｔｉｔｉｏｎ
_ｄｂの内容により次にピックすべき特定の変数が暗黙に
定義されていなければ、デフォルトの変数順序でａ、
ｅ、ｃ、ｄ、ｂの順序に従ってピックする。

【００４９】関数ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩ
ＮＧは、決定が回路内の矛盾する信号割り当てセットを
発生させる状況を検出するために呼び出される。この例
の趣旨においては、この関数は、純粋に回路上のシミュ
レーション調整パスのセットとして実装されると想定さ
れる。この関数が回路内で信号割り当てを検出すると、
常に、有向弧がｐａｒｔｉｔｉｏｎ_ｄｂに追加される。
これを行うためには、関数ＡＤＤ＿ＴＯ＿ＰＡＲＴＩＴ
ＩＯＮ＿ＤＢが呼び出される。これらの弧は、新規な区
分従属関係セットが検出されたことを示す。

【００５０】関数ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩ
ＮＧが矛盾する信号割り当てセットを検出すると、常
に、関数ＢＡＣＫＴＲＡＣＫが呼び出される。ＢＡＣＫ
ＴＲＡＣＫは、対立分析を実装する。この関数は、ｐａ
ｒｔｉｔｉｏｎ_ｄｂの内容を使用して、現在の対立を取
消すために再解決されなければならない区分の最大数を
決定する。これは、最初にＤＥＰＥＮＤＥＮＴ＿ＰＡＲ
ＴＩＴＩＯＮＳを呼び出し、次にＭＯＳ＿ＲＥＣＥＮＴ
＿ＰＡＲＴＩＴＩＯＮを呼び出すことによって行われ
る。また、ＢＡＣＫＴＲＡＣＫは、関数ＰＡＲＴＩＴＩ
ＯＮ＿ＲＥＵＳＥを呼び出すことによって、Ｓｔａｃｋ
を再編成してこの情報を組み込む。

【００５１】関数ＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳＥは、
現在の対立により暗黙に定義される関連区分から独立し
た区分を決定する。この関数は、区分が再使用に適格と
なるために満足しなければならない２つの条件を実装す
る。例を使用して、これらの条件について説明する。

【００５２】関数ＭＥＲＧＥ＿ＰＡＲＴＩＴＩＯＮＳ
は、回路内の各対立の後に呼び出される。この関数は、
現在対立している区分のセットを使用して、Ｍｅｒｇｅ
ｄ＿ｐａｒｔｉｔｉｏｎ_ｄｂ内の情報を更新する。

【００５３】関数ＳＥＴ＿ＶＡＬＵＥおよびＵＮＳＥＴ
＿ＶＡＬＵＥは、信号値で構造をカプセル化する。関数
ＦＩＲＳＴ＿ＶＡＬＵＥおよびＮＥＸＴ＿ＶＡＬＵＥ
は、決定変数の連続する値割り当てをステップスルーす
るために使用される。

【００５４】ここで再び、信号ｙ上の０値固定故障に関
するテストを生成する問題について考察する（図３）。
この例では、テストは信号ｇ４、ｇ８、およびｇ７に値
１を想定する必要がある。

【００５５】図５〜１９は、それぞれ２つの部分に分か
れている。各図の左半分は、Ｓｔａｃｋデータ構造の内
容を示し、右半分はｐａｒｔｉｔｉｏｎ_ｄｂの状態を示
す。図６〜１９はそれぞれ、図２６に示すアルゴリズム
２における最外部ループの１回の反復に対応する。

【００５６】図５は、最外部ループを１回目から３回目
まで反復した後のデータ構造の状態を示す。この場合、
３回のいずれの決定も対立とはならない。各回の反復に
おける実行パスは、アルゴリズム２の第４、５、６、
７、１９、２０、および２１行に対応する。信号ｅを０
に設定した後にＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮ
Ｇを呼び出すと、ｇ９がａ０に割り当てられた。これに
より、ｐａｒｔｉｔｉｏｎ_ｄｂがｅおよびｃからｇ９ま
での弧によって増補される結果となった。

【００５７】次にＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲ
ＩＡＢＬＥを呼び出すと、変数順序に従ってｄが戻され
る。ここで、ｄは第６行の０（ＦＩＲＳＴ＿ＶＡＬＵ
Ｅ）に設定される。その後、ＣＯＮＳＩＳＴＥＮＴ＿Ｌ
ＡＢＥＬＩＮＧが呼び出され、シミュレーションによっ
て信号ｇ５、ｇ６、ｇ７、ｇ８が決定される。区分デー
タベースは、これらの固定を示すために増補される。図
６は、Ｓｔａｃｋとｐａｒｔｉｔｉｏｎ_ｄｂの対応する
状態を示す。必須割り当てによってｇ７およびｇ８は１
でなければならないことが示されているので、ｇ７とｇ
８を０に割り当てると、矛盾した信号割り当てセットが
発生する。ほとんどの実装システムは、最初に決定され
た対立で停止する。この例の趣旨においては、最初に検
出された対立はｇ７上にあると想定される。変数ｃｏｎ
ｆｌｉｃｔは、無矛盾ラベル付けによってＹＥＳに設定
される。また、ｃｏｎｆｌｉｃｔｉｎｇ＿ｖａｌｕｅｓ
はｇ７に設定される。制御は、ルーチンＢＡＣＫＴＲＡ
ＣＫに転送される。ＢＡＣＫＴＲＡＣＫの第４行でＤＥ
ＰＥＮＤＥＮＴ＿ＰＡＲＴＩＴＩＯＮＳを呼び出すと、
｛ｄ，ｅ｝が戻される。これは、区分データベースか
ら、ｇ７の値を決定するために必要とされる区分はｅと
ｄだけであることが明らかなためである。ＭＯＳＴ＿Ｒ
ＥＣＥＮＴ＿ＰＡＲＴＩＴＩＯＮを呼び出すとｄが戻さ
れ、制御はＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳＥに転送され
る。この場合、ｍｒｐはＳｔａｃｋの最上位と同じなの
で、制御は第１７行のＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳＥ
に転送される。これによりｄの値が値テーブル内で設定
解除され、ｐａｒｔｉｔｉｏｎ_ｄｂ内のｄに対応する弧
が削除される。制御は、アルゴリズム２の第１６行に戻
される。これにより、｛ｄ，ｅ｝がＭｅｒｇｅｄ＿ｐａ
ｒｔｉｔｉｏｎ_ｄｂに追加される。第１９行では、ｄが
ＮＥＸＴ＿ＶＡＬＵＥの１に設定される。第２０行で、
ｅからｄまでの弧がｐａｒｔｉｔｉｏｎ_ｄｂに追加され
る。これは、区分ｄの値が区分ｅによって完全に決定さ
れたことを示す。

【００５８】この時点で、ｐａｒｔｉｔｉｏｎ_ｄｂが同
様の制御フローによって図７のように増補される。今回
は、ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧが信号ｇ
８上の対立を決定する。ここでは、関数ＤＥＰＥＮＤＥ
ＮＴ＿ＰＡＲＴＩＴＩＯＮＳがｅを戻す。ＰＡＲＴＩＴ
ＩＯＮ＿ＲＥＵＳＥが、ｍｒｐ＝ｅと共に呼び出され
る。制御は、ｐａｒｔｉｏｎ＿ｌｉｓｔ｛ｄ，ｃ｝を持
つ第９行に到達する。設定ｄｅｌｅｔｅ＿ｓｅｔは、ｅ
を保持している。続いて第１０行でｐａｒｔｉｔｉｏｎ
＿ｌｉｓｔの各要素がチェックされ、再使用が可能かど
うかが判断される。テストＣＨＩＬＤは、ｗをｄｅｌｅ
ｔｅ＿ｓｅｔの各要素と比較して、そのペアによって固
定が導き出されるかどうか判断する。ｐａｒｔｉｔｉｏ
ｎ_ｄｂの有向グラフ実装では、これはそのペアの各ノー
ドから深度１の走査となる可能性がある。検査対象の区
分が現在の対立によって暗黙に定義された区分関係から
独立している場合は、このような固定は存在しないはず
である。テストＡＮＣＥＳＴＯＲは、ｐａｒｔｉｔｉｏ
ｎ_ｄｂ内のｗの祖先のうち現在ｄｅｌｅｔｅ＿ｓｅｔ内
にあるものがあるかどうかを判断するためのチェックを
行う。ｄｅｌｅｔｅ＿ｓｅｔ内に祖先が１つでもある
と、区分は独立していないことになる。この場合、区分
ｃは、ｅと結合して固定ｇ９を生成しているので、再使
用はできない（すなわち、ＣＨＩＬＤ（｛ｃ，ｅ｝）＝
ｇ９）。ＡＮＣＥＳＴＯＲ（ｄ）＝＝ｅなので、ｐａｒ
ｔｉｔｉｏｎ_ｄｂから区分ｄを使用することはできな
い。そのため、ｄ、ｃ、およびｅは設定解除され、区分
データベースｐａｒｔｉｔｉｏｎ_ｄｂから削除される。
第２０行で変数ｅはスタック上にプッシュバックされ、
制御はアルゴリズム２の第１３行に転送される。アルゴ
リズム２の第２２行では、ｐａｒｔｉｔｉｏｎ_ｄｂとス
タックは図８の状態となる。

【００５９】次に、Ｍｅｒｇｅｄ＿ｐａｒｔｉｔｉｏｎ
_ｄｂ内に区分セット｛ｄ，ｅ｝が存在するという事実を
利用するために、ＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲ
ＩＡＢＬＥを呼び出す。現在、Ｓｔａｃｋの最上位はｅ
なので、ＮＥＸＴ＿ＤＥＣＩＳＩＯＮ＿ＶＡＲＩＡＢＬ
Ｅはｄを戻す。それは、ｄとｅは以前は従属関係にある
区分だったからである。ここでは、区分分析によって、
変数順序付けが強制的に変更されている。デフォルトの
変数順序付けであればｄではなくｃがピックされていた
はずである。変数ｄは０（ＦＩＲＳＴ＿ＶＡＬＵＥ）に
設定され、ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧの
呼び出しによって、ｐａｒｔｉｔｉｏｎ _ｄｂが図９のよ
うに増補される。ｇ７およびｇ８上で対立が検出され
る。いずれかが検出されると、ＢＡＣＫＴＲＡＣＫの呼
び出しによってｄｅｐ＿ｐａｒｔｉｏｎｓが｛ｄ，ｅ｝
に設定される。アルゴリズム２内の第２０行での呼び出
しによって、ｐａｒｔｉｔｉｏｎ_ｄｂ内にｅからｄまで
の弧が発生する。ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩ
ＮＧの呼び出しが実行されると、図１０のようなｐａｒ
ｔｉｔｉｏｎ_ｄｂとなる。

【００６０】図１１〜１６は、Ｓｔａｃｋ上に変数ｄお
よびｃを追加すると実行されるオンライン区分化プロセ
スを示したものである。ｃを１に設定した後に呼び出さ
れる関数ＣＯＮＳＩＳＴＥＮＴ＿ＬＡＢＥＬＩＮＧは、
ｇ４上の対立を検出する。これは図１６に示されてい
る。これに対応するＢＡＣＫＴＲＡＣＫへの呼び出しに
よって、ｍｒｐが｛ａ｝であることが検出される。関数
ＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳＥが呼び出される。ＰＡ
ＲＴＩＴＩＯＮ＿ＲＥＵＳＥの第２行で変数ｄｅｌｅｔ
ｅ＿ｓｅｔがａに初期化され、第９行でｐａｒｔｉｏｎ
＿ｌｉｓｔが｛ｅ，ｄ，ｂ，ｃ｝を格納する。変数ｃお
よびｂはＡＮＣＥＳＴＯＲテストに不合格となるので、
後退されなければならない。変数ｄおよびｅはいずれも
テストに合格するので、再使用できる。ＰＡＲＴＩＴＩ
ＯＮ＿ＲＥＵＳＥを呼び出した後のＳｔａｃｋは、図１
７のようになる。従来の分岐・結合解法では、ａ上の新
規な値に対する試行の前に、ｄおよびｅの影響が解消さ
れる。一方、オンライン区分化法では、ｄとｅの含意は
解消されない。図１８および１９は、アルゴリズム２の
最外部ループにおける以後２回の反復を示したものであ
る。決定変数ｃおよびｂがピックされる。図１９では、
対立は検出されず、故障の検出に有効な値の割り当てが
取得されている。（テスト生成システム）図２２に、テスト生成システム
の好適な実施例を示す。このテスト生成システムは、コ
ンピューターを備える。ここで、コンピューターは、Ｐ
Ｃ、メインフレーム、ワークステーション、ネットワー
ク上のリモート・コンピューターなど、どんな種類でも
よいことに留意する必要がある。このコンピューター
は、ＣＰＵ２２．１およびメモリー２２．２を備える。
メモリーは、コンピューターがテスト生成システムの各
種コンポーネントを実装することを可能にする命令を保
持している。テスト生成システムのコンポーネントに
は、副問題の解が再使用されるテスト生成問題を再帰的
に解決するテスト生成問題ソルバー２２．２１が含まれ
る。問題パーティショナー２２．２２は、テスト生成問
題を受け取り、前記テスト生成問題を副問題に区分化す
る。これらの副問題は従属関係にあってもよい。これら
の副問題は、従属関係にありながらも、特定の解に対す
る独立性を有することができる。無矛盾ラベルチェッカ
ー２２．２３は、問題ソルバーからテスト生成問題を受
け取り、無矛盾ラベル付けが存在するかどうかを判断す
る。区分マージャー２２．２４は、副問題の当該サブセ
ットの解が存在せず、副問題の前記サブセットが従属関
係にある場合に、副問題のサブセットをマージする。最
後に、対立セット・ジェネレーターは、特定の副問題が
解を持つことを阻む目標の対立セットを生成する。（テスト生成コンピューター・プログラム製品）本発明
の重要な態様は、コンピューター・プログラム製品であ
る。このプログラム製品は、コンピューターがテスト生
成問題を解決することを可能にする命令を有するコンピ
ューター読み取り可能媒体を備える。ここで、コンピュ
ーター読み取り可能媒体は、フロッピー・ディスク、ハ
ード・ディスク、ＣＤ、チップ、テープ、大容量記憶装
置付きのカートリッジを含みそれに限定されないどんな
固定媒体でもよいことに留意する必要がある。コンピュ
ーター読み取り可能媒体は、さらに、ネットワークを介
して伝送されるか、インターネットからダウンロードさ
れる命令を備える。命令は、テスト生成問題ソルバー・
コードを備える。問題ソルバー・コードは、コンピュー
ターがテスト生成問題を再帰的に解決することを可能に
する。問題ソルバーは、副問題の解を再使用することが
できる。問題パーティショナー・コードは、コンピュー
ターがテスト生成問題を受け取り、前記テスト生成問題
を副問題に区分化することを可能にする。これらの副問
題は、特定の解に対して従属性を有しながら、従属関係
にあることができる。

【００６１】無矛盾ラベル・チェッカー・コードは、コ
ンピューターが問題ソルバーからテスト生成問題を受け
取り、無矛盾ラベル付けが存在するかどうかを判断する
ことを可能にする。区分マージャー・コードは、コンピ
ューターが副問題のサブセットの解が存在せず、副問題
の前記サブセットが従属関係にある場合に、副問題のサ
ブセットをマージする。対立セット・ジェネレーター・
コードは、特定の副問題が解を持つことを阻む目標の対
立セットを生成する。（実験結果）先の節で説明したオンライン区分化手法
を、推移閉包ベースＡＴＰＧシステムの一部として実装
した。図２３および２４に示す表１および２は、それぞ
れ、本発明によるオンライン区分化手法で増補されたＡ
ＴＰＧシステムのパフォーマンスを示す。「Ｂａｓｅｌ
ｉｎｅｓｙｓｔｅｍ（ベースライン・システム）」と
して示されるカラムは、これらの新規な手法を使用しな
いＡＴＰＧシステムのパフォーマンスを示す。

【００６２】「Ｔｏｔａｌ（合計）」のラベルが付けら
れたカラムは、テスト生成が試みられた故障の総数を示
す。カラム「Ｓｏｌｖｅｄ（解決済み）」は、ＡＴＰＧ
システムがテストを生成できたか、ＵＮＴＥＳＴＡＢＬ
Ｅ（テスト不能）として分類した故障の総数を示す。カ
ラム「Ｂｔ（バックトラック）」は、各回路内の故障を
分類しようとする過程でＡＴＰＧシステムが実行を強い
られたバックトラックの総数を示す。カラム「Ｔｉｍｅ
（時間）」は、ＡＴＰＧシステムがその回路に費やした
時間の合計である。各故障に与えられた制限時間は１秒
間である。いずれの実験も、３００ＭＨｚＳＰＡＲＣ
プロセッサーを備えるＳｏｌａｒｉｓシステム上で実行
された。最後の３カラムは、新手法の使用によって実現
されたベースライン・システムからの改善をパーセンテ
ージで示す。表１は、ＩＳＣＡＳ回路での結果を示す。
表２は、いくつかの生産回路での結果を示す。これらの
回路の規模は、１０Ｋ〜４００Ｋゲートである。

【００６３】本発明のその他の変更態様と異型について
は、前述の開示と教示から当業者には明らかであろう。
したがって、本書では本発明の一部の実施例を具体的に
説明したにすぎないが、本発明の精神と範囲から乖離す
ることなく無数の変更態様を作成できることは明らかで
あろう。

【００６４】

【発明の効果】以上説明したように本発明によれば、従
来の問題点を解消した改良型オンライン問題解法を提供
することができる。すなわち、区分化された副問題が従
属関係を持つことのできる、シーケンス回路に関するテ
スト生成問題を解決するためのオンライン解法を実現す
る。さらに、シーケンス回路テスト用のテストベクトル
を生成するための改良型生成法を提供することができ
る。

【図面の簡単な説明】

【図１】静的区分化を説明するための回路の例を示す
回路図である。

【図２】従属副問題をともなうオンライン区分化を説
明するための回路の例を示す回路図である。

【図３】オンライン区分化手法の好適な実施例を説明
するためのサンプル回路を示す回路図である。

【図４】図２５に示されるオンライン解法の好適な実
施例の挙動を説明するためのＡＮＤ−ＯＲツリーを示す
図である。

【図５】本発明のテスト生成方法の好適な実施例の実
装における各ステップを経た後のスタックと区分化され
たデータベースの内容を示す図である。

【図６】本発明のテスト生成方法の好適な実施例の実
装における各ステップを経た後のスタックと区分化され
たデータベースの内容を示す図である。

【図７】本発明のテスト生成方法の好適な実施例の実
装における各ステップを経た後のスタックと区分化され
たデータベースの内容を示す図である。

【図８】本発明のテスト生成方法の好適な実施例の実
装における各ステップを経た後のスタックと区分化され
たデータベースの内容を示す図である。

【図９】本発明のテスト生成方法の好適な実施例の実
装における各ステップを経た後のスタックと区分化され
たデータベースの内容を示す図である。

【図１０】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１１】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１２】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１３】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１４】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１５】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１６】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１７】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１８】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図１９】本発明のテスト生成方法の好適な実施例の
実装における各ステップを経た後のスタックと区分化さ
れたデータベースの内容を示す図である。

【図２０】問題を解決するためのオンライン解法を説
明するフローチャートである。

【図２１】本発明によるテスト生成問題の解法の好適
な実施例を説明するフローチャートである。

【図２２】本発明によるテスト生成システムの好適な
実施例を示すブロック図である。

【図２３】ＩＳＣＡＳベンチマーク回路に関するオン
ライン区分化の結果を描写する表１を示す図である。

【図２４】生産回路に関するオンライン区分化の結果
を描写する表２を示す図である。

【図２５】本発明によるテスト生成方法の好適な実施
例に関する疑似コードを示す図である。

【図２６】本発明によるテスト生成方法のもっとも好
適な実施例に関する疑似コードを示す図である。

【図２７】本発明によるテスト生成方法のもっとも好
適な実施例で使用されるＢＡＣＫＴＲＡＣＫ関数に関す
る疑似コードを示す図である。

【図２８】本発明によるテスト生成方法のもっとも好
適な実施例で使用されるＰＡＲＴＩＴＩＯＮ＿ＲＥＵＳ
Ｅ関数に関する疑似コードを示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者キラン・ビー・ドレスワミ― アメリカ合衆国，ニュージャージー 08540，プリンストン，４インディペンデンスウェイエヌ・イー・シー・ユー・エス・エーインク内 (72)発明者スレンドラ・ケイ・ボムーアメリカ合衆国，ニュージャージー 08540，プリンストン，４インディペンデンスウェイエヌ・イー・シー・ユー・エス・エーインク内 (72)発明者ジジャン・リンアメリカ合衆国，アイオワ 52246，アイオワシティ，1512 ダーウェンドライブアイオワ大学内

Claims

【特許請求の範囲】

【請求項１】シーケンス回路に関するテスト生成問題
を解決する方法であって、下記ステップを備える。ａ）原テスト生成問題をより規模の小さい副問題に再
帰的に分割し、前記副問題が従属関係にありながらも、
１つかそれ以上の前記従属副問題が特定の解に対して独
立性を有することができる。ｂ）前記副問題の解を検出する。ｃ）従属副問題が特定の解に対して独立性を有する場
合に、当該副問題の解を再使用する。および、ｄ）複数の目標を達成するために解決すべき副問題に
解がない場合に、対立する目標の最小サブセットを識別
する。
【請求項２】シーケンス回路をテストするためのテス
トベクトルを生成する方法であって、前記方法は下記ス
テップを備える。ａ）テスト生成問題を識別する。ｂ）次の決定変数を選択する。ｃ）ステップｂの決定変数に関する次の値を選択す
る。ｄ）ステップｂで選択された値が無矛盾ラベル付けに
対応するかどうかチェックし、無矛盾ラベル付けが存在
しない場合は、対立セットを戻す。ｅ）ステップｄのチェックにより無矛盾ラベル付けが
検出された場合は、以下のサブステップを実行する。ｉ）テスト生成問題を副問題に区分化して、前記副問
題の各々に本請求の方法を再帰的に適用する。ｉｉ）現在の副問題に解が存在せず、従属区分が存在
する場合は、従属区分をマージする。ｉｉｉ）現在の副問題に解が存在せず、従属区分も存
在しない場合は、ステップｃに進む。ｆ）前記チェックで矛盾ラベル付けが検出された場合
で、変数が現在の区分の一部ではない場合に、矛盾ラベ
ル付けを発生させる変数を追加する。ｇ）選択された変数のすべての値についてｃ〜ｆを繰
り返す。ｈ）すべての変数についてｂ〜ｇを繰り返す。およ
び、ｉ）解が検出された場合は解を戻し、検出されなかっ
た場合は識別された対立セットを戻す。
【請求項３】問題を解決する方法であって、前記方法
は下記ステップを備える。ａ）問題をより規模の小さい副問題に再帰的に分割
し、前記副問題が従属関係にありながらも、１つかそれ
以上の前記従属副問題が特定の解に対して独立性を有す
ることができる。ｂ）前記副問題の解を検出する。ｃ）従属副問題が特定の解に対して独立性を有する場
合に、当該副問題の解を再使用する。および、ｄ）複数の目標を達成するために解決すべき副問題に
解がない場合に、対立する目標の最小サブセットを識別
する。
【請求項４】コンピューターを備えるテスト生成シス
テムであって、前記コンピューターがＣＰＵとメモリー
を有し、前記メモリーが前記システムのコンポーネント
を実装することのできる命令を備え、前記コンポーネン
トは下記要件を備える。テスト生成問題を再帰的に解決
するためのテスト生成問題ソルバーであって、副問題の
解が再使用されるテスト生成問題ソルバー、テスト生
成問題を受け取り、前記テスト生成問題を副問題に区分
化するための問題パーティショナーであって、前記副問
題が従属関係にあることができ、前記副問題が特定の問
題に対する従属性を有することができる問題パーティシ
ョナー、問題ソルバーからテスト生成問題を受け取り、無矛盾ラ
ベル付けが存在するかどうかを判断するための無矛盾ラ
ベルチェッカー、副問題の前記サブセットの解が存在せず、副問題の前記
サブセットが従属関係にある場合に、副問題のサブセッ
トをマージするための区分マージャー、及び特定の副問
題が解を持つことを阻む目標の対立セットを生成するた
めの対立セット・ジェネレーター。
【請求項５】命令を有するコンピューター読み取り可
能媒体を備えるコンピューター・プログラム製品であっ
て、前記命令はコンピューターがテスト生成問題を解決
することを可能にし、前記命令が下記要件を備える。コ
ンピューターがテスト生成問題を再帰的に解決すること
を可能にするためのテスト生成問題ソルバー・コードで
あって、副問題の解が再使用されるテスト生成問題ソル
バー・コード、コンピューターがテスト生成問題を受け取り、前記テス
ト生成問題を副問題に区分化することを可能にする問題
パーティショナー・コードであって、前記副問題は従属
関係にあることができ、前記副問題は特定の解に対して
従属性を有することができる問題パーティショナー・コ
ードであって、コンピューターが問題ソルバーからテスト生成問題を受
け取ることを可能にし、無矛盾ラベル付けが存在するか
どうかを判断するための無矛盾ラベル・チェッカー・コ
ード、副問題の前記サブセットの解が存在せず、副問題の前記
サブセットが従属関係にある場合に、コンピューターが
副問題のサブセットをマージすることを可能にするため
の区分マージャー・コード、及びコンピューターが特定
の副問題が解を持つことを阻む目標の対立セットを生成
することを可能にするための対立セット・ジェネレータ
ー・コード。