(57)【要約】【課題】遅延故障を検査するための高品質のテストパターンを高速に生成する。【解決手段】後のテスト周期で与えられる第２のテストパターンを生成するために、回路中に設定された故障値を観測点まで伝搬させる。回路中の分岐点では、分岐の枝の中から故障値を伝搬させる信号線を選択し、活性化と正当化を行うことにより回路中の信号線の値を求め、活性化と正当化に成功した場合には、求めた信号線の値に基づき第２のテストパターンを更新する。信号線を選択するときには、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択する。【選択図】図４
2007017430.tif 000002
【特許請求の範囲】
【請求項１】
テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法であって、
前記第１のテストパターンとして、テスト対象信号線の値を仮定した遅延故障に応じた初期値に一致させる入力値の組合せを求めるステップと、
前記第２のテストパターンとして、前記テスト対象信号線に設定された、仮定した遅延故障に応じた故障値を観測点まで伝搬させる入力値の組合せを求めるステップとを備え、
前記第２のテストパターンを求めるステップは、
前記テスト対象回路に含まれる分岐点において、複数の分岐の枝の中から、故障値を伝搬させる信号線を選択するステップと、
選択された信号線に故障値を伝搬させるために活性化および正当化を行い、前記テスト対象回路に含まれる信号線の値を求めるステップと、
活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第２のテストパターンを更新するステップとを含み、
前記信号線を選択するステップは、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択することを特徴とする、テストパターン生成方法。
【請求項２】
前記テスト対象信号線は、前記テスト対象回路に含まれる制御点および分岐の枝の中から選択され、
前記信号線を選択するステップは、分岐の枝から分岐点を経由せずに到達できる分岐の幹または観測点に至る経路を構成する信号線を一括して選択することを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項３】
前記信号線を選択するステップは、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝を信号線選択の候補から除外することを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項４】
前記信号線の値を求めるステップは、ロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第１のテストパターンを更新するステップをさらに含むことを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項５】
前記信号線の値を求めるステップは、ノンロバスト条件に従い活性化を行うことを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項６】
前記信号線の値を求めるステップは、当初はロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての分岐の枝についてロバスト条件下での活性化に失敗した場合には、ノンロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第１のテストパターンを更新するステップをさらに含むことを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項７】
前記信号線の値を求めるステップは、選択された分岐の枝について、ロバスト条件に従い活性化を行い、当該処理に失敗した場合にはノンロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第１のテストパターンを更新するステップをさらに含むことを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項８】
前記第２のテストパターンを求めるステップは、
ある分岐点で選択可能なすべての分岐の枝について活性化および正当化に失敗した場合には、過去に信号線の選択が行われた分岐点までバックトラックするステップをさらに含む、請求項１に記載のテストパターン生成方法。
【請求項９】
前記バックトラックするステップは、直前に信号線の選択が行われた分岐点までバックトラックすることを特徴とする、請求項８に記載のテストパターン生成方法。
【請求項１０】
前記バックトラックするステップは、いずれかの未選択の分岐の枝を含む最長テスト経路の長さが所定の基準を満たす分岐点のうち、直近に信号線の選択が行われた分岐点までバックトラックすることを特徴とする、請求項８に記載のテストパターン生成方法。
【請求項１１】
前記バックトラックするステップは、過去に信号線の選択が行われた分岐点のうち、未選択の分岐の枝を含む最長テスト経路の長さが最も長い分岐点までバックトラックすることを特徴とする、請求項８に記載のテストパターン生成方法。
【請求項１２】
前記バックトラックするステップは、バックトラック先の分岐点以降に故障値を伝搬させるために求められた制御点の値を保持したまま、バックトラックすることを特徴とする、請求項８に記載のテストパターン生成方法。
【請求項１３】
ある制御点を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該制御点は前記テスト対象信号線から除外され、
ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝は前記テスト対象信号線から除外されるとともに、前記信号線を選択するステップにおける信号線選択の候補から除外されることを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項１４】
前記テスト対象回路に含まれる制御点、信号線および観測点を指定するステップをさらに備え、
前記テスト対象回路に含まれる信号線のうち、指定された制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線、指定された信号線から任意の観測点に至る経路を構成する信号線、および、指定された観測点に到達する経路のみに含まれる信号線は、前記テスト対象信号線から除外され、前記信号線を選択するステップにおける信号線選択の候補から除外され、前記信号線の値を求めるステップでは固定値が与えられることを特徴とする、請求項１に記載のテストパターン生成方法。
【請求項１５】
テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法であって、
前記テスト対象回路に含まれる複数の信号線の中から選択されたテスト対象信号線に信号遷移を設定し、前記テスト対象信号線を制御信号線に設定するステップと、
前記制御信号線へと信号を伝搬する１以上の制御候補信号線の各々について、前記制御候補信号線から、信号が入力される制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、前記制御候補信号線の中から１本の制御候補信号線を選択するステップと、
選択された前記制御候補信号線から前記制御信号線へと信号遷移を伝播させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第１及び第２のテストパターンを決定するステップとを備える、テストパターン生成方法。
【請求項１６】
活性化及び正当化に成功した場合には、選択された制御候補信号線を制御信号線として再設定し、
活性化及び正当化に失敗した場合には、未選択の前記制御候補信号線の中から１本の信号線を再選択し、
可制御の制御点に到達するまで、前記信号線を選択するステップと、前記信号値を求めるステップと、前記第１及び第２のテストパターンを決定するステップとを繰り返し実行することを特徴とする、請求項１５に記載のテストパターン生成方法。
【請求項１７】
ある制御信号線に信号を伝搬する全ての前記制御候補信号線について活性化及び正当化に失敗した場合には、過去に信号線の選択が行われた信号線までバックトラックするステップを更に備える、請求項１５に記載のテストパターン生成方法。
【請求項１８】
前記信号値を求めるステップは、前記制御候補信号線が複数存在する場合には、前記制御候補信号線から前記制御点までの経路が最長である制御候補信号線についてのみ信号遷移を設定し、他の制御候補信号線には一定の信号値を設定することを特徴とする、請求項１５に記載のテストパターン生成方法。
【請求項１９】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路に含まれるゲート数が最大である経路を、最長経路として選択することを特徴とする、請求項１５に記載のテストパターン生成方法。
【請求項２０】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路に含まれるビア数が最大である経路を、最長経路として選択することを特徴とする、請求項１５に記載のテストパターン生成方法。
【請求項２１】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路の各々の遅延情報に基づいて、最長経路を選択することを特徴とする、請求項１５に記載のテストパターン生成方法。
【請求項２２】
テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法であって、
前記テスト対象回路に含まれる複数の信号線の中からテスト対象信号線を選択し、前記テスト対象信号線に信号遷移を設定するステップと、
前記テスト対象信号線に設定された信号遷移を、前記テスト対象信号線から、信号が出力される観測点まで伝搬させる前記第１及び第２のテストパターンを決定する第１の決定ステップと、
信号が入力される制御点から前記テスト対象信号線へと、設定された信号遷移を伝搬させる前記第１及び第２のテストパターンを決定する第２の決定ステップとを備え、
前記第１の決定ステップは、
前記テスト対象信号線を到達信号線に設定するステップと、
前記到達信号線から分岐する１以上の到達候補信号線の各々について、前記到達候補信号線からいずれか１つの観測点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づき、前記到達候補信号線の中から一本の到達候補信号線を選択するステップと、
選択された前記到達候補信号線に信号を伝搬させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
前記活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第１及び第２のテストパターンを決定するステップとを含み、
前記第２の決定ステップは、
前記テスト対象信号線を制御信号線に設定するステップと、
前記制御信号線へと信号を伝搬する１以上の制御候補信号線の各々について、前記制御候補信号線からいずれか１つの制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、前記制御候補信号線の中から１本の制御候補信号線を選択するステップと、
選択された前記制御候補信号線から前記制御信号線へと信号遷移を伝搬させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第１及び第２のテストパターンを決定するステップとを含む、テストパターン生成方法。
【請求項２３】
前記第１の決定ステップは、前記第２の決定ステップの前に行われることを特徴とする、請求項２２に記載のテストパターン生成方法。
【請求項２４】
前記第１の決定ステップは、前記第２の決定ステップの後に行われることを特徴とする、請求項２２に記載のテストパターン生成方法。
【請求項２５】
前記テスト対象信号線から前記観測点までの経路長の最大値を第１の最大経路長として算出し、前記テスト対象信号線から前記制御点までの経路長の最大値を第２の最大経路長として算出するステップを更に備え、
前記第１の最大経路長が前記第２の最大経路長より長いときには、前記第１の決定ステップは、前記第２の決定ステップの前に行われ、前記第１の最大経路長が前記第２の最大経路長以下であるときには、前記第１の決定ステップは、前記第２の生成ステップの後に行われることを特徴とする、請求項２２に記載のテストパターン生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路における遅延故障を検査するためのテストパターンを生成するテストパターン生成方法に関する。
【背景技術】
【０００２】
従来から、半導体集積回路内で信号伝搬中に発生する遅延故障を検査するために、遅延故障をいくつかの故障モデルに従って分類し、各故障モデルの特徴に合わせたテストパターンを生成する方法が知られている。遅延故障の故障モデルには、大きく分けて、パス遅延故障モデルと遷移故障モデルとがある。パス遅延故障モデルを用いれば、テスト対象経路上に発生する微小欠陥の積み重ねによる遅延故障や１箇所にある大きな遅延故障を検出することができる。これに対して、遷移故障モデルを用いれば、テスト対象となる信号線またはゲート上の１箇所にある大きな遅延故障を検出することができる。
【０００３】
一般に、遅延故障を検査するためには、２つの検査系列（以下、検査系列Ｔ１およびＴ２という）が必要とされる。自動テスト装置は、テスト対象回路に対してあるタイミングで検査系列Ｔ１を与え、次のテスト周期で検査系列Ｔ２を与える。この検査系列を＜Ｔ１，Ｔ２＞と記載する。以下、パス遅延故障を検査するためのテストパターン生成方法（以下、パス遅延故障用パターン生成方法という）および遷移故障を検査するためのテストパターン生成方法（以下、遷移故障用パターン生成方法という）について説明する。
【０００４】
なお、パス遅延故障用パターン生成方法については、例えば、C. J. Lin and S. M. Reddy, "On Delay Fault Testing in Logic Circuits", IEEE Transactions on Computer-Aided Design, CAD-6(5), pp.694-703, 1987.や、K. T. Cheng, A. Krstic and H. C. Chen, "Generation of High Quality Tests for Robustly Untestable Path Delay Faults",IEEE Transactions on Computers, 45(12), pp.1379-1392, 1996.などに記載されている。遷移故障用パターン生成方法については、例えば、E. S. Park and M. R. Mercer, "AnEfficient Delay Test Generation System for Combinational Logic Circuits", IEEE Transactions on Computer-Aided Design, 11(7), pp.926-938, 1992. などに記載されている。
【０００５】
まず、パス遅延故障用パターン生成方法について説明する。パス遅延故障用パターン生成方法では、テストパターンは、例えば、テスト対象回路内の各信号線に対して図４０に示す５値の論理値を、図４１に示す含意表や図４２に示す経路活性化表に従って割り当てることによって生成される。図４０に示す論理値Ｓ０は、信号線の値が検査系列Ｔ１とＴ２の両方で０であることを示す。論理値Ｓ１は、信号線の値が検査系列Ｔ１とＴ２の両方で１であることを示す。論理値Ｕ０は、信号線の値が検査系列Ｔ１ではＸ（０でも１でもよい）、検査系列Ｔ２では０であることを示す。論理値Ｕ１は、信号線の値が検査系列Ｔ１ではＸ、検査系列Ｔ２では１であることを示す。論理値ＸＸは、信号線の値が検査系列Ｔ１とＴ２の両方でＸであることを示す。
【０００６】
図４１（ａ）〜（ｃ）に、ＡＮＤゲート、ＯＲゲートおよびインバータの含意表を示す。各含意表には、上記５値の入力値の組合せに対する出力値が記載されている。例えば、ＡＮＤゲートの入力ａがＳ０、ｂがＵ０であるときの出力ｙは、次のようにして求められる。入力ａがＳ０であるので、ａの値は検査系列Ｔ１とＴ２の両方で０である。また、入力ｂがＵ０であるので、ｂの値は検査系列Ｔ１ではＸ、検査系列Ｔ２は０である。したがって、ｙの値は、検査系列Ｔ１とＴ２の両方で０となる。このことを５値を用いて表現すると、出力ｙはＳ０となる。
【０００７】
パス遅延故障用パターン生成方法では、テスト対象経路を活性化するときに、ロバスト条件およびノンロバスト条件のいずれかが使用される（図４２を参照）。ロバスト条件を用いれば、テスト対象経路上のゲートに接続された入力であって、テスト対象経路上にないもの（以下、テスト対象外入力という）に遅延故障が発生した場合でも、テスト対象経路上の遅延故障を正しく検出することができる。一方、ノンロバスト条件を用いれば、テスト対象外入力に遅延故障が発生した場合には、テスト対象経路上の遅延故障を正しく検出できない可能性がある。
【０００８】
以下、信号線の立上り遷移をＮＤ、信号線の立下り遷移をＤと表す。例えば、ＡＮＤゲートにおいて、入力ａの値が０から１に変化したときに出力ｙの値が必ず変化する（すなわち、立上り遷移ＮＤを入力ａから出力ｙに伝搬させる）ための条件は、入力ｂにＵ１を与えることである（図４２（ａ）を参照）。したがって、ＡＮＤゲートにおいてロバスト条件で立上り遷移ＮＤを伝搬させるための条件は、Ｕ１（テスト対象外入力にＵ１を与える）となる。また、ＯＲゲートにおいて、入力ａの値が１から０に変化したときに出力ｙの値が必ず変化する（すなわち、立下り遷移Ｄを入力ａから出力ｙに伝搬させる）ための条件は、入力ｂにＵ０を与えることである（図４２（ｂ）を参照）。したがって、ＯＲゲートにおいてロバスト条件で立下り遷移Ｄを伝搬させるための条件は、Ｕ０（テスト対象外入力にＵ０を与える）となる。
【０００９】
図４２（ｃ）に、ＡＮＤゲート、ＮＡＮＤゲート、ＯＲゲートおよびＮＯＲゲートのロバスト条件での活性化条件を示す。図４２（ｃ）には、各種類のゲートにおいて、ロバスト条件で立上り遷移ＮＤまたは立下り遷移Ｄを伝搬させるためにテスト対象外入力に与えるべき値が記載されている。図４２（ｄ）に、ＡＮＤゲート、ＮＡＮＤゲート、ＯＲゲートおよびＮＯＲゲートのノンロバスト条件での活性化条件を示す。図４２（ｄ）には、各種類のゲートにおいて、ノンロバスト条件で立上り遷移ＮＤまたは立下り遷移Ｄを伝搬させるためにテスト対象外入力に与えるべき値が記載されている。
【００１０】
テスト対象経路上のすべてのゲートのテスト対象外入力に対してロバスト条件を満たす値を設定できる場合には、そのテスト対象経路をロバストテスト可能経路という。また、テスト対象経路上の少なくとも１つのゲートのテスト対象外入力に対してノンロバスト条件を満たす値を設定できる場合には、そのテスト対象経路をノンロバストテスト可能経路という。ノンロバストテスト可能経路を検査するためのテストパターンは、テスト対象外入力に遅延故障が発生した場合でも、テスト対象経路上の遅延故障をできるだけ多く検査できることが好ましい。このようなテストパターンは、テスト対象外入力とテスト対象経路上のゲートの伝搬遅延値が最大になるように、テスト対象外入力に値を設定する経路を考慮する方法や、テスト対象経路上に多入力ゲートが存在する場合に、なるべく多くのテスト対象外入力にロバスト条件を満たす値を設定する方法によって生成される（非特許文献１を参照）。
【００１１】
図４３に、テスト対象回路の例を示す。図４３に示すＳＦＦ１〜６は、スキャンフリップフロップ（以下、スキャンＦＦという）であり、全体でスキャンチェーンを構成する。ＳＦＦ１〜６は、ＣＫ端子に入力されるクロック信号が立上ると、ＳＥ端子からの入力信号がテストモードを示す場合にはＤＴ端子からの入力信号を取り込み、ＳＥ端子からの入力信号が通常モードを示す場合にはＤ端子からの入力信号を取り込む。したがって、テストモードでクロックが入力されると、スキャン入力端子ＳＩＮからの入力信号がＳＦＦ１のＱ出力に、ＳＦＦ１〜５のＱ出力がそれぞれＳＦＦ２〜６のＱ出力に現れる。ＳＦＦ６のＱ出力は、外部出力端子ＰＯ１経由で外部に出力される。
【００１２】
図４３に示すテスト対象回路に含まれる経路Ｐ（入力端子Ｘ３からゲートｇ２、ｇ５、
ｇ６を経由してＳＦＦ６に至る経路；以下、テスト対象経路Ｐという）におけるパス遅延故障を検査するためのテストパターンは、以下のようにして生成される。まず、図４３に示すように、テスト対象経路Ｐ上の各信号線に信号遷移が設定される。次に、図４２（ｃ）に示す経路活性化表に従って、テスト対象経路Ｐ上の各ゲートのテスト対象外入力に対して、各ゲートを活性化する信号値が与えられる。さらに、図４１に示す含意表に従って、各信号線に与えられた信号値に基づき、各入力信号線に与えるべき信号値が決定される（図４４を参照）。
【００１３】
以上の処理により、検査系列Ｔ１として｛ＳＦＦ１，ＳＦＦ２，ＳＦＦ３，ＳＦＦ４，ＳＦＦ５｝＝｛０，Ｘ，０，０，Ｘ｝が生成され、検査系列Ｔ２として｛ＳＦＦ１，ＳＦＦ２，ＳＦＦ３，ＳＦＦ４，ＳＦＦ５｝＝｛０，Ｘ，１，０，０｝が生成される。最後に、検査系列＜Ｔ１，Ｔ２＞は、シリアルパターンに変換される。検査系列Ｔ２は、検査系列Ｔ１で各スキャンＦＦに設定された値をさらに１クロックだけスキャンシフトさせる方法（ＳＫＥＷＥＤ−ＬＯＡＤ手法）、あるいは、検査系列Ｔ１で各スキャンＦＦに値を設定した後に回路を１クロックだけ通常動作させる方法（ＢＲＯＡＤ−ＳＩＤＥ手法）のいずれかによって得られる。なお、どちらの方法を用いる場合でも、検査系列Ｔ２の値を各スキャンＦＦに設定できるか否かを判定する正当化処理を行う必要がある。図４３に示すテスト対象回路に含まれるテスト対象経路Ｐについては、ＳＫＥＷＥＤ−ＬＯＡＤ手法によれば図４５（ａ）に示すテストパターンが得られ、ＢＲＯＡＤ−ＳＩＤＥ手法によれば図４５（ｂ）に示すテストパターンが得られる。
【００１４】
次に、遷移故障用パターン生成方法について説明する。遷移故障用パターン生成方法では、テストパターンは、テスト対象の信号線またはゲートに信号遷移を設定し、その信号遷移を外部出力または観測フリップフロップまで伝搬させるように、各ゲートの信号値を決定することにより生成される。その際、テスト対象の信号線またはゲートから外部出力または観測フリップフロップに至る活性化経路に対して、所定の経路活性化表および含意表に従って、信号値が割り当てられる。例として図４６に、ＡＮＤゲートの経路活性化表および含意表を示す。
【００１５】
図４７（ａ）に、テスト対象回路の一例を示す。図４７（ａ）に示すテスト対象回路において、ＮＡＮＤゲートｇ３の出力の立上り遷移が遅くなる遷移故障（ｓｌｏｗ−ｔｏ−ｒｉｓｅ）を検査するためのテストパターンは、以下のようにして生成される。まず、図４７（ａ）に示すように、ＮＡＮＤゲートｇ３の出力に初期値０を与えるために、検査系列Ｔ１として｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ｝が生成される。次に、故障ゲートｇ３の出力が初期値０（設定した初期値）に固定される縮退故障を仮定し、この縮退故障を検査するための検査系列Ｔ２として｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５｝＝｛０，Ｘ，１，１，１｝が生成される（図４７（ｂ）を参照）。以上の処理によって得られた検査系列＜Ｔ１，Ｔ２＞が、ＮＡＮＤゲートｇ３の出力におけるｓｌｏｗ−ｔｏ−ｒｉｓｅ故障を検査するための検査系列となる。
【００１６】
遷移故障モデルを用いた場合、仮定される故障の総数は、回路の構造には依存せず、回路中のゲートの入出力端子数の合計になる。このため、遷移故障モデルを用いた場合、検査系列生成処理や検出判定処理で扱う状態数は、ゲート数のオーダーで済む。したがって、従来の方法を用いても、ほぼ完全な検出率を持つテストパターンを求めることができる。これに対して、パス遅延故障モデルを用いた場合、仮定される故障の総数は、回路の構造に依存し、最も多い場合には回路中のゲート数の指数に比例する。信頼性の点から見れば、すべての信号遷移の伝搬経路について網羅的な検査を行えるパス遅延故障モデルを用いることが好ましい。しかしながら、パス遅延故障用テストパターン生成方法を実行するには、テスト対象経路の本数に応じた長い時間がかかる。このため、パス遅延故障用パターン生成方法には、大規模回路用のテストパターンを現実的な時間では生成できないという問題がある。
【００１７】
この問題を解決する方法として、特許文献１には、テスト対象回路内の多数の経路の中から、パス遅延故障の検査対象とする経路を選択する方法が開示されている。この方法では、まず、テスト対象回路内のすべての経路の中から、設計上の遅延値が所定の閾値を超える経路が選択され、次に、選択された経路に含まれる２つの経路のうちで、どちらをパス遅延故障の検査対象とするが判断される。
【００１８】
また、特許文献２には、パス遅延故障の検査対象とする経路を選択する別の方法が開示されている。この方法では、テスト対象回路の設計遅延情報と、テスト対象回路内の経路の本数と比べて十分小さな数の経路を活性化する検査系列（あるいは乱数でもよい）とに基づき、設計上の遅延値が所定の閾値よりも小さい活性化可能な経路は検出可能と判断される。上記の検査系列あるいは乱数を用いても検出できない故障については、テスト対象信号線を選択した後、出力側に活性化条件を割り当てながら最長の活性化経路を求める処理が行われる。
【特許文献１】特開平１１−２１８５６３号公報
【特許文献２】特開２００１−５１０２７号公報
【非特許文献１】K. T. Cheng, "Delay Fault Testing for VLSI Circuits", pp.52-53, pp.112-113, 1998.
【発明の開示】
【発明が解決しようとする課題】
【００１９】
しかしながら、特許文献１に開示された方法では、パス遅延故障の検査対象として選択される経路の数は依然として膨大である。したがって、この方法で選択されたすべての経路についてパス遅延故障を検査することは現実的には不可能である。
【００２０】
また、特許文献２に開示された方法では、短い検査系列あるいは乱数を最初に与えることにより、検出可能なパス遅延故障を効率よく検出することができる。しかし、この処理で検出できなかったパス遅延故障については、活性化条件を割り当てながら最長の活性化経路を求める処理が行われる。一般に、分岐再収斂構造を持つ論理回路は、活性化条件の割り当ては可能であるが、正当化処理（入力側の記憶素子または外部入力端子へ信号を割り当てる処理）で矛盾が発生しやすいという性質を有する。したがって、特許文献２に開示された方法を分岐再収斂構造を持つ論理回路に適用すると、伝搬時間の長い経路を何度も探索する必要が生じ、処理時間が長くなる。
【００２１】
それ故に、本発明は、遅延故障を検査するための高品質のテストパターンを高速に生成するテストパターン生成方法を提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明のテストパターン生成方法は、テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法であって、第１のテストパターンとして、テスト対象信号線の値を仮定した遅延故障に応じた初期値に一致させる入力値の組合せを求めるステップと、第２のテストパターンとして、テスト対象信号線に設定された、仮定した遅延故障に応じた故障値を観測点まで伝搬させる入力値の組合せを求めるステップとを備え、第２のテストパターンを求めるステップは、テスト対象回路に含まれる分岐点において、複数の分岐の枝の中から、故障値を伝搬させる信号線を選択するステップと、選択された信号線に故障値を伝搬させるために活性化および正当化を行い、テスト対象回路に含まれる信号線の値を求めるステップと、活性化および正当化に成功した場合に、求めた信号線の値に基づき第２のテストパターンを更新するステップとを含み、信号線を選択するステップ
は、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択することを特徴とする（第１の局面）。
【００２３】
この場合、テスト対象信号線は、テスト対象回路に含まれる制御点および分岐の枝の中から選択され、信号線を選択するステップは、分岐の枝から分岐点を経由せずに到達できる分岐の幹または観測点に至る経路を構成する信号線を一括して選択してもよい（第２の局面）。
【００２４】
あるいは、信号線を選択するステップは、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝を信号線選択の候補から除外してもよい（第３の局面）。
【００２５】
あるいは、信号線の値を求めるステップは、ロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第１のテストパターンを更新するステップをさらに含んでいてもよい（第４の局面）。
【００２６】
あるいは、信号線の値を求めるステップは、ノンロバスト条件に従い活性化を行ってもよい（第５の局面）。
【００２７】
あるいは、信号線の値を求めるステップは、当初はロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての分岐の枝についてロバスト条件下での活性化に失敗した場合には、ノンロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第１のテストパターンを更新するステップをさらに含んでいてもよい（第６の局面）。
【００２８】
あるいは、信号線の値を求めるステップは、選択された分岐の枝について、ロバスト条件に従い活性化を行い、当該処理に失敗した場合にはノンロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第１のテストパターンを更新するステップをさらに含んでいてもよい（第７の局面）。
【００２９】
あるいは、第２のテストパターンを求めるステップは、ある分岐点で選択可能なすべての分岐の枝について活性化および正当化に失敗した場合には、過去に信号線の選択が行われた分岐点までバックトラックするステップをさらに含んでいてもよい（第８の局面）。
【００３０】
特に、バックトラックするステップは、直前に信号線の選択が行われた分岐点までバックトラックしてもよい（第９の局面）。
【００３１】
あるいは、バックトラックするステップは、いずれかの未選択の分岐の枝を含む最長テスト経路の長さが所定の基準を満たす分岐点のうち、直近に信号線の選択が行われた分岐点までバックトラックしてもよい（第１０の局面）。
【００３２】
あるいは、バックトラックするステップは、過去に信号線の選択が行われた分岐点のうち、未選択の分岐の枝を含む最長テスト経路の長さが最も長い分岐点までバックトラックしてもよい（第１１の局面）。
【００３３】
あるいは、バックトラックするステップは、バックトラック先の分岐点以降に故障値を伝搬させるために求められた制御点の値を保持したまま、バックトラックしてもよい（第１２の局面）。
【００３４】
あるいは、ある制御点を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該制御点はテスト対象信号線から除外され、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝はテスト対象信号線から除外されるとともに、信号線を選択するステップにおける信号線選択の候補から除外されてもよい（第１３の局面）。
【００３５】
あるいは、テストパターン生成方法は、テスト対象回路に含まれる制御点、信号線および観測点を指定するステップをさらに備え、テスト対象回路に含まれる信号線のうち、指定された制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線、指定された信号線から任意の観測点に至る経路を構成する信号線、および、指定された観測点に到達する経路のみに含まれる信号線は、テスト対象信号線から除外され、信号線を選択するステップにおける信号線選択の候補から除外され、信号線の値を求めるステップでは固定値が与えられることとしてもよい（第１４の局面）。
【００３６】
また、本発明の第１５の局面は、テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法に向けられている。当該テストパターン生成方法は、テスト対象回路に含まれる複数の信号線の中から選択されたテスト対象信号線に信号遷移を設定し、テスト対象信号線を制御信号線に設定するステップと、制御信号線へと信号を伝搬する１以上の制御候補信号線の各々について、制御候補信号線から、信号が入力される制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、制御候補信号線の中から１本の制御候補信号線を選択するステップと、選択された制御候補信号線から制御信号線へと信号遷移を伝播させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第１及び第２のテストパターンを決定するステップとを備える。
【００３７】
この場合、活性化及び正当化に成功した場合には、選択された制御候補信号線を制御信号線として再設定し、活性化及び正当化に失敗した場合には、未選択の制御候補信号線の中から１本の信号線を再選択し、可制御の制御点に到達するまで、信号線を選択するステップと、信号値を求めるステップと、第１及び第２のテストパターンを決定するステップとを繰り返し実行してもよい（第１６の局面）。
【００３８】
あるいは、ある制御信号線に信号を伝搬する全ての制御候補信号線について活性化及び正当化に失敗した場合には、過去に信号線の選択が行われた信号線までバックトラックするステップを更に備えてもよい（第１７の局面）。
【００３９】
あるいは、信号値を求めるステップは、制御候補信号線が複数存在する場合には、制御候補信号線から制御点までの経路が最長である制御候補信号線についてのみ信号遷移を設定し、他の制御候補信号線には一定の信号値を設定してもよい（第１８の局面）。
【００４０】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路に含まれるゲート数が最大である経路を、最長経路として選択してもよい（第１９の局面）。
【００４１】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路に含まれるビア数が最大である経路を、最長経路として選択してもよい（第２０の局面）。
【００４２】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路の各々の遅延情報に基づいて、最長経路を選択してもよい（第２１の局面）。
【００４３】
本発明の第２２の局面は、テスト対象回路で発生する遅延故障を検出するために、第１のテストパターンと、次のテスト周期で与えられる第２のテストパターンとを生成するテストパターン生成方法に向けられている。当該テストパターン生成方法は、テスト対象回路に含まれる複数の信号線の中からテスト対象信号線を選択し、テスト対象信号線に信号遷移を設定するステップと、テスト対象信号線に設定された信号遷移を、テスト対象信号線から、信号が出力される観測点まで伝搬させる第１及び第２のテストパターンを決定する第１の決定ステップと、信号が入力される制御点からテスト対象信号線へと、設定された信号遷移を伝搬させる第１及び第２のテストパターンを決定する第２の決定ステップとを備える。第１の決定ステップは、テスト対象信号線を到達信号線に設定するステップと、到達信号線から分岐する１以上の到達候補信号線の各々について、到達候補信号線からいずれか１つの観測点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づき、到達候補信号線の中から一本の到達候補信号線を選択するステップと、選択された到達候補信号線に信号を伝搬させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第１及び第２のテストパターンを決定するステップとを含む。また、第２の決定ステップは、テスト対象信号線を制御信号線に設定するステップと、制御信号線へと信号を伝搬する１以上の制御候補信号線の各々について、制御候補信号線からいずれか１つの制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、制御候補信号線の中から１本の制御候補信号線を選択するステップと、選択された制御候補信号線から制御信号線へと信号遷移を伝搬させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第１及び第２のテストパターンを決定するステップとを含む。
【００４４】
この場合、第１の決定ステップは、第２の決定ステップの前に行われてもよい（第２３の局面）。
【００４５】
あるいは、第１の決定ステップは、第２の決定ステップの後に行われてもよい（第２４の局面）。
【００４６】
テスト対象信号線から観測点までの経路長の最大値を第１の最大経路長として算出し、テスト対象信号線から制御点までの経路長の最大値を第２の最大経路長として算出するステップを更に備え、第１の最大経路長が第２の最大経路長より長いときには、第１の決定ステップは、第２の決定ステップの前に行われ、第１の最大経路長が第２の最大経路長以下であるときには、第１の決定ステップは、第２の生成ステップの後に行われてもよい（第２５の局面）。
【発明の効果】
【００４７】
上記第１の局面によれば、より長い経路を用いて故障を伝搬させることにより、テストパターンの品質を高めることができる。
【００４８】
上記第２の局面によれば、複数の信号線に対して一括して活性化、含意操作および正当化を行うことにより、処理時間を短縮することができる。
【００４９】
上記第３の局面によれば、短い経路に含まれる分岐の枝を信号線選択の候補から予め除外しておくことにより、処理時間を短縮することができる。
【００５０】
上記第４の局面によれば、ロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延故障を、他の信号線上に遅延故障が発生したか否かにかかわらず検査することができる。
【００５１】
上記第５の局面によれば、ノンロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延の影響を、より長い経路を利用して検出することができる。
【００５２】
上記第６の局面によれば、ロバスト条件による活性化に失敗した場合にはノンロバスト条件に従い活性化を行うことにより、ロバスト条件では検査できない故障を検査できるテストパターンを生成することができる。
【００５３】
上記第７の局面によれば、このようにロバスト条件に従った活性化を優先して実行することにより、遅延故障の検出経路が同じ場合でも、高品質のテストパターンを生成することができる。
【００５４】
上記第８の局面によれば、活性化および正当化に失敗した場合にはバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【００５５】
上記第９の局面によれば、直前に選択が行われた分岐点までバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【００５６】
上記第１０の局面によれば、バックトラックを行う際の戻り先を制限することにより、処理時間を短縮することができる。
【００５７】
上記第１１の局面によれば、バックトラックを行う際の戻り先を制限し、より長い経路を優先的に選択することにより、テスト対象信号線の遅延の影響をより長い経路で伝搬して検出することができる。
【００５８】
上記第１２の局面によれば、故障値を伝搬させるときに信号線に割り当てた値を保持する必要がなくなるので、処理時間を短縮し、メモリ使用量を削減することができる。
【００５９】
上記第１３の局面によれば、所定の基準を満たさない制御点および信号線を除外して処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【００６０】
上記第１４の局面によれば、指定された信号線を除いて処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【００６１】
上記第１５の局面によれば、制御点からテスト対象信号線までの経路がより長くなるようなテストパターンを生成することができるため、テストパターンの品質を高めることができる。
【００６２】
上記第１６の局面によれば、各ステップを繰り返し実行しながら、テスト対象信号線から制御点へと向かって経路を選択しながらテストパターンを決定することができるので、テストパターンをより効率的に生成することができる。
【００６３】
上記第１７の局面によれば、活性化および正当化に失敗した場合にはバックトラックするので、制御点からテスト対象信号線へと信号遷移を伝搬することができるテストパターンをより確実に生成することができる。
【００６４】
上記第１８の局面によれば、制御点からテスト対象信号線へと信号伝搬可能な最長の経路以外の経路には、固定値が設定されるので、テスト対象外経路の信号遅延の影響が低減し、テストパターンの信頼性が向上する。
【００６５】
上記第２２の局面によれば、テスト対象信号線から観測点までの経路長と、テスト対象信号線から制御点までの経路長とがより長くなるように経路が選択されるため、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【００６６】
上記第２３の局面によれば、最初にテスト対象信号線から観測点へと信号伝搬可能な経路が選択されるため、テスト対象信号線に確実に観測可能な経路について効率的にテストパターンを生成することができる。
【００６７】
上記第２４の局面によれば、最初に制御点からテスト対象信号線へと信号伝搬可能な経路が選択されるため、テスト対象信号線に確実に制御可能な経路について効率的にテストパターンを生成することができる。
【００６８】
上記第２５の局面によれば、テスト対象信号線から観測点までの最長経路の長さと、テスト対象信号線から制御点までの最長経路の長さとを比較して、より長い経路を伝搬するテストパターンを先に決定するので、テストパターンを効率的に生成することができる。
【発明を実施するための最良の形態】
【００６９】
本発明の第１〜第１３の実施形態では、遅延故障を検査するためのテストパターンを生成するテストパターン生成方法について説明する。以下、第１〜第１３の実施形態に係るテストパターン生成方法を、それぞれ、第１〜第１３の生成方法という。
【００７０】
まず、以下の説明で使用する表現および用語について説明する。信号線に設定される値「Ｘ」は、信号線に値０または値１のいずれを設定してもよいことを表す。信号線がある分岐点で複数に分岐するとき、当該信号線のうち分岐するまでの部分を「分岐の幹」といい、分岐した後の部分を「分岐の枝」という。スキャンＦＦの出力を「擬似外部入力」といい、スキャンＦＦの入力を「擬似外部出力」という。外部入力および擬似外部入力を「制御点」といい、外部出力および擬似外部出力を「観測点」という。テスト対象回路では、端子ＰＩ＊（＊は任意の文字列）は制御点を表し、端子ＰＯ＊は観測点を表す。各実施形態で示すステップのうち、先の実施形態で既に説明したステップについては、同一のステップ番号を付して説明を省略する。
【００７１】
図１は、第１〜第１３の生成方法を実行するテストパターン生成システムの構成を示す図である。図１に示すテストパターン生成システムＡ（以下、装置という）は、入力された回路情報Ｃに基づき、テストパターンＰを生成する。装置の動作概要は、以下のとおりである。ステップ１では、装置には、回路情報Ｃとして、テスト対象回路を構成する記憶素子、論理素子および素子間の配線に関する情報が入力される。ステップ２では、装置は、テスト対象の信号線および信号遷移を選択する。ステップ３では、装置は、ステップ２で選択した信号線に、ステップ２で選択した信号遷移を設定する。ステップ４では、装置は、ステップ３で設定した信号遷移を観測点まで伝搬させる経路を順次選択し、活性化、含意操作および正当化を行う。この際、信号遷移を伝搬している信号線が分岐する場合には、装置は、観測点までの伝搬経路の長さ（以下、観測距離という）が最長の分岐の枝を選択し、選択した分岐の枝に信号遷移を伝搬させる。ステップ４を実行することにより、検査系列＜Ｔ１，Ｔ２＞が得られる。ステップ５では、装置は、得られた検査系列＜Ｔ１，Ｔ２＞を一時的に内部またはファイルに記録する。ステップ６では、装置は、ステップ５で記録した検査系列を、自動テスト装置で使用可能なシリアル形式のテストパターンＰに変換する。なお、第１〜第１３の実施形態で示すフロー図は、いずれも、図１に示すフロー図を詳細化したものである。
【００７２】
ステップ４では、観測距離は、ステップ１で入力された回路情報Ｃに基づき、所定の計算方法に従って算出される。例えば、観測距離は、回路情報Ｃに含まれる遅延値テーブル（図２）やビアテーブル（図３）を用いて算出される。図２に示す遅延値テーブルでは、ゲートはテスト対象回路に含まれるゲートの名前を、ＩＮおよびＯＵＴはゲートの入力信号線および出力信号線の名前を示す。遷移は、入力信号線の遷移を示す。遷移ｒは立上り遷移を表し、遷移ｆは立下り遷移を表す。遅延値は、各ゲートのＩＮからＯＵＴまでの信号遷移の伝搬時間を示す。図３（ａ）に示すビアテーブルでは、ゲートはテスト対象回路に含まれるゲートの名前を、ＩＮおよびＯＵＴはゲートの入力信号線および出力信号線の名前を示す。ビア数は、各ゲートのＩＮからＯＵＴまでのビア数とコンタクト数の合計を示す。図３（ｂ）に示すビアテーブルでは、信号線は信号線の名前を示す。ビア数は、信号線上に設けられたビア数とコンタクト数の合計を示す。
【００７３】
なお、遅延値テーブルは、電圧や温度に依存して変化する遅延値を記憶していてもよい。また、ゲートに対応した遅延テーブルとともに、配線に対応した遅延値テーブルを使用してもよい。また、遅延値テーブルは、制御点や観測点に関する遅延値を記憶していてもよい。また、配線およびゲートに対応したビアテーブルに代えて、配線のみに対応したビアテーブル、あるいは、ゲートのみに対応したビアテーブルを使用してもよい。また、ビアテーブルは、制御点や観測点に関するビア数を記憶していてもよい。遅延値テーブルおよびビアテーブルは、人手で作成したものでも、電子計算機を用いて求めたものでもよく、その形式も任意でよい。
【００７４】
＜第１の実施形態＞
図４は、第１の生成方法を示すフロー図である。第１の生成方法では、以下の処理が実行される。
（ステップ１０）装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子（ゲート）および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
（ステップ１１）装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ１１では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
（ステップ１２）装置は、ステップ１１でテスト対象の信号線および信号遷移を選択した場合にはステップ１３へ進み、それ以外の場合にはステップ２０へ進む。
【００７５】
（ステップ１３）装置は、ステップ１１で選択したテスト対象信号線に、ステップ１１で選択した信号遷移の初期値（立上り遷移の場合は０、立下り遷移の場合は１）を設定する。
（ステップ１４）装置は、ステップ１１で選択したテスト対象信号線の値を、ステップ１３で設定した初期値に一致させるための入力値の組合せを求める。これにより、検査系列Ｔ１が生成される。
（ステップ１５）装置は、ステップ１４で検査系列Ｔ１の生成に成功した場合にはステップ１６へ進み、それ以外の場合にはステップ１１へ進む。
【００７６】
（ステップ１６）装置は、ステップ１１で選択したテスト対象信号線に、ステップ１１で選択した信号遷移に対応した故障値（立上り遷移のときはＮＤ、立下り遷移のときはＤ）を設定する。
（ステップ１００）装置は、後述する検査系列生成処理を行うことにより、検査系列Ｔ２を生成する。検査系列生成処理では、ステップ１４で生成された検査系列Ｔ１が更新される場合もある。装置は、検査系列Ｔ２の生成（および検査系列Ｔ１の更新）に成功した場合にはステップ１９へ進み、それ以外の場合はステップ１１へ進む。
【００７７】
（ステップ１９）装置は、ステップ１４、１００で生成した検査系列＜Ｔ１，Ｔ２＞を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列＜Ｔ１，Ｔ２＞を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ１１へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ１１〜１９が実行される。
（ステップ２０）装置は、ステップ１９で記録した検査系列＜Ｔ１，Ｔ２＞をシリアルパターンに変換し、処理を終了する。
【００７８】
ステップ１００では、以下の処理が実行される。以下、最も新しく故障値が伝搬するようになった信号線を「到達信号線」といい、到達信号線の出力側に接続された、次に故障値が到達する可能性がある信号線を「到達候補信号線」という。
（ステップ１０１）装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。なお、正当化によって制御点に与えるべき値が決定された場合には、検査系列Ｔ２が更新され、場合によっては検査系列Ｔ１も更新される。以下に示すすべての正当化処理においても、これと同じである。
（ステップ１０２）装置は、ステップ１０１で矛盾が発生した場合にはステップ１１へ進み、それ以外の場合にはステップ１０３へ進む。
【００７９】
（ステップ１０３）装置は、到達信号線に基づき、到達候補信号線を更新する。具体的には、ゲートの入力信号線が到達信号線であり、かつ、当該ゲートの出力信号線が分岐していない場合には、当該ゲートの出力信号線の全体が到達候補信号線となる。また、ゲートの入力信号線が到達信号線であり、かつ、当該ゲートの出力信号線が分岐している場合には、当該ゲートの出力信号線の分岐の幹が到達候補信号線となる。さらに、分岐の幹が到達信号線である場合には、当該分岐の幹の出力側に接続された分岐の枝の全体が到達候補信号線となる。
（ステップ１０４）装置は、到達候補信号線が１本以下（すなわち、０本または１本）である場合にはステップ１０５へ進み、それ以外の場合にはステップ１０８へ進む。
（ステップ１０５）装置は、到達候補信号線が観測可能であるか、または、０本である（すなわち、到達候補信号線が観測点に接続されているか、または、到達候補信号線がない）場合には、ステップ１９へ進み、それ以外の場合にはステップ１０６へ進む。
（ステップ１０６）装置がこのステップに到達するのは、到達候補信号線が１本である場合に限られる。装置は、唯一の到達候補信号線を新たな到達信号線に設定する。
【００８０】
（ステップ１０７）装置は、到達信号線の出力側へゲート１段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。なお、到達信号線が分岐の幹である場合には、分岐の枝の値はすでに含意操作により決定されているので、装置は、活性化、含意操作および正当化を行わない。その後、装置はステップ１０２へ進む。
【００８１】
（ステップ１０８）装置がステップ１０４からこのステップに到達するのは、到達候補信号線（分岐の枝）が２本以上ある場合に限られる。装置は、各分岐の枝について、各観測点までの経路の長さ（観測距離）を求め、観測距離の最大値（以下、最長観測距離という）を求める。観測距離は、上述したように、遅延値テーブル（図２）やビアテーブル（図３）など用いて算出される。装置は、到達候補信号線の中で最長観測距離が最も長い信号線を新たな到達信号線として選択する。
【００８２】
（ステップ１０９）装置は、ステップ１０８で到達信号線を選択した場合にはステップ１１０へ進み、それ以外の場合にはステップ１１へ進む。
（ステップ１１０）装置は、ステップ１０７と同じ処理を行う。
（ステップ１１１）装置は、ステップ１１０で矛盾が発生した場合にはステップ１１２へ進み、それ以外の場合にはステップ１０３へ進む。
（ステップ１１２）装置は、ステップ１０８で選択した到達信号線を到達候補信号線から除外し、ステップ１０８へ進む。
【００８３】
図５に示すテスト対象回路に対して第１の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ９の立上り遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１３）装置は、テスト対象信号線ｓ９に初期値０を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ９に初期値０を設定するために、制御点ＰＩ４に０を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ９に故障値ＮＤを設定する。
【００８４】
（ステップ１０１）装置は、テスト対象信号線ｓ９に故障値ＮＤを設定し、設定した故障値ＮＤを信号線ｓ１０へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ５、ｓ５ａ、ｓ５ｂ、ｓ５ｃおよび制御点ＰＩ２、ＰＩ４には１が設定され、信号線ｓ１０には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ１０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）装置は、信号線ｓ１０を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）信号線ｓ１０は観測不可なので、装置はステップ１０６へ進む。
（ステップ１０６）装置は、信号線ｓ１０を到達信号線に設定する。
（ステップ１０７）到達信号線ｓ１０は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ１０２へ進む。
【００８５】
（ステップ１０２）ステップ１０７では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）信号線ｓ１０は分岐の幹であるので、装置は、信号線ｓ１０ａ、ｓ１０ｂを到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が２本あるので、装置はステップ１０８へ進む。
【００８６】
（ステップ１０８）装置は、到達候補信号線ｓ１０ａ、ｓ１０ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１０ａの最長観測距離は３、信号線ｓ１０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１０ａを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ１０ａの故障値Ｄを信号線ｓ７へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ６、ｓ６ａ、ｓ６ｂおよび制御点ＰＩ３には０が設定され、信号線ｓ７には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１１１）ステップ１１０では矛盾が発生していないので、装置はステップ１０３へ進む。
【００８７】
（ステップ１０３〜１０６）装置は、信号線ｓ７（観測不可）を到達候補信号線に設定した後、信号線ｓ７を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ７の故障値Ｄを信号線ｓ８へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ１１および制御点ＰＩ５には０が設定され、信号線ｓ８には故障値ＮＤが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，０，Ｘ，Ｘ｝に更新される。
【００８８】
（ステップ１０２）ステップ１０７では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ８（観測不可）を到達候補信号線に設定した後、信号線ｓ８を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ８の故障値ＮＤを信号線ｓ４へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ３、ｓ２、ｓ１および制御点ＰＩ１には０が設定され、信号線ｓ４には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝に更新される。
【００８９】
（ステップ１０２）ステップ１０７では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）装置は、信号線ｓ４を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ４は観測点ＰＯ１に接続されており観測可能なので、装置はステップ１９へ進む。
【００９０】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。
【００９１】
図６は、従来の遷移故障用パターン生成方法を示すフロー図である。上記第１の生成方法は、図６に示す方法において、ステップ１７、１８をステップ１００に置換したものである。図６に示す方法では、ステップ１００に代えて、以下の処理が実行される。
（ステップ１７）装置は、ステップ１６で設定した故障値ＤまたはＮＤを観測点まで伝搬するために、活性化、含意操作および正当化を行うことにより、検査系列Ｔ２を生成する。
（ステップ１８）装置は、ステップ１７で検査系列Ｔ２の生成に成功した場合にはステップ１９へ進み、それ以外の場合にはステップ１１へ進む。
【００９２】
図５に示すテスト対象回路に対して図６に示す方法を実行したときの処理を説明する。ここでは、信号線ｓ６の立下り遷移をテスト対象とし、｛ＰＩ１、ＰＩ２、ＰＩ３、ＰＩ４、ＰＩ５、ＰＩ６、ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１３）装置は、テスト対象信号線ｓ６に初期値１を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ６に初期値１を設定するために、制御点ＰＩ３に１を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１６）装置は、テスト対象信号線ｓ６に故障値Ｄを設定する。
【００９３】
（ステップ１７）装置は、テスト対象信号線ｓ６の故障値Ｄを観測点まで伝搬させるために、活性化、含意操作および正当化を行う。まず信号線ｓ６の故障値Ｄを信号線ｓ３に伝搬させるために、信号線ｓ２には０が設定される。次に信号線ｓ３の故障値Ｄを信号線ｓ４に伝搬させるために、信号線ｓ８には０が設定される。観測点ＰＯ１まで故障値を伝搬させた後に、各信号線に対する正当化が行われる。信号線ｓ６を０に正当化するために、制御点ＰＩ３には０が設定される。信号線ｓ２を０に正当化するために、信号線ｓ１および制御点ＰＩ１には０が設定される。信号線ｓ８を０に正当化するために、信号線ｓ１１および制御点ＰＩ５には１が設定される。検査系列Ｔ２は｛Ｐ｝＝｛０，Ｘ，０，Ｘ，１，Ｘ，Ｘ｝に更新される。
【００９４】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，Ｘ，０，Ｘ，１，Ｘ，Ｘ｝が生成される。
【００９５】
図５に示すテスト対象回路には、信号線ｓ６に設定された故障値を伝搬させる経路の候補として、信号線ｓ６ａを経由する経路と、信号線ｓ６ｂを経由する経路とが含まれている。このように故障値を伝搬させる経路が複数ある場合、図６に示す従来の方法では、各信号線へ故障値を伝搬させるときの観測のし易さ（可観測費）や制御のし易さ（可制御費）などに基づき、次に故障値を伝搬させる信号線が選択される。上記の例では、可観測費の高い（観測しやすい）信号線ｓ６ａが選択されているが、ある条件下では信号線ｓ６ｂが選択されることもある。いずれの場合でも、観測点まで故障値を伝搬させた後に正当化が行われる。
【００９６】
これに対して、第１の生成方法では、故障値を伝搬させる経路が複数ある場合には、最長観測距離が最も長い分岐の枝が、次に故障値を伝搬させる信号線として選択される。このように、より長い経路を用いて故障を伝搬させることにより、テストパターンの品質を高めることができる。
【００９７】
なお、以上の説明では、装置は、ステップ１０８で各分岐の枝について最長観測距離を求めることとした。これに代えて、装置は、同じ分岐の枝について最長観測距離を繰り返し計算することを避けるために、例えばステップ１０とステップ１１との間で、テスト対象回路に含まれる各分岐の枝について最長観測距離を予め求めておいてもよい。
【００９８】
また、故障値を伝搬させる処理を行う際に、回路構成によっては、到達信号線の出力側に接続される到達候補信号線に故障値が既に伝搬している場合がある。このような場合には、装置は、到達候補信号線に対する活性化を行う必要はない。
【００９９】
＜第２の実施形態＞
図７は、第２の生成方法を示すフロー図である。第２の生成方法は、第１の生成方法に対して、ステップ２０１を追加し、ステップ１０７を削除し、ステップ１１、１６、１０１、１０６、１１０をそれぞれステップ２０２〜２０６に置換したものである。第２の生成方法は、テスト対象回路をエッジグラフで表現することにより、テストパターンを高速に生成することを特徴とする。エッジグラフの各頂点は、テスト対象回路内の１以上の信号線に対応する。以下、エッジグラフの各頂点に対応する信号線を、グループ内の信号線という。
【０１００】
第２の生成方法で初出のステップは、以下のとおりである。
（ステップ２０１）装置は、テスト対象回路に対して後述する回路変換を行うことにより、エッジグラフを求める。
（ステップ２０２）装置は、ステップ２０１で求めたエッジグラフの頂点の中からテスト対象の信号線を選択し、テスト対象の信号遷移を選択する。
（ステップ２０３）装置は、ステップ２０２で選択したテスト対象信号線に、ステップ２０２で選択した信号遷移に対応した故障値を設定する。この際、装置は、グループ内の各信号線に対して、グループ内の先頭の信号線に設定された故障値を正しく伝搬させた場合に得られる故障値を設定する。
（ステップ２０４）装置は、グループ内の信号線に故障値を設定し、設定した故障値を伝搬させるために、活性化、含意操作および正当化を行う。
（ステップ２０５）装置は、到達候補信号線のグループを新たな到達信号線として選択する。その後、装置はステップ２０４へ進む。
（ステップ２０６）装置は、ステップ２０４と同じ処理を行う。
【０１０１】
ステップ２０１では、以下の処理（図示せず）により、ステップ１０で入力された回路情報に基づき、エッジグラフが求められる。
（ステップ２０１ａ）装置は、１個の記憶素子または外部入力から１個の分岐の幹までの範囲にある部分回路（これには、ゲートと信号線とが含まれる）を、当該記憶素子または当該外部入力の名前を付した頂点に置換する。
（ステップ２０１ｂ）装置は、１個の分岐の枝から１個の分岐の幹または観測点までのに範囲にある部分回路を、当該分岐の枝の名前を付した頂点に置換する。
（ステップ２０１ｃ）テスト対象回路において、あるグループ内の要素と別のグループ内の要素とが接続されている場合には、装置は、これら２つのグループに対応した頂点間に、入力側から出力側へ向かう有向枝を生成する。
【０１０２】
図８に示すテスト対象回路に対してステップ２０１の回路変換を実行すると、図９に示すエッジグラフが得られる。図９に示すエッジグラフでは、頂点ＰＩ５０１〜ＰＩ５０８は制御点に、頂点ＰＯ５０１およびＰＯ５０２は観測点に、その他の頂点は分岐の枝に対応する。図９に示す頂点には、図８に示すテスト対象回路のうちで各頂点に対応した部分回路に含まれる分岐の枝の名前が付されている。例えば、頂点ＰＩ５０４から頂点ｓ５１０ａに向かう枝は、図８に示すテスト対象回路では、外部入力ＰＩ５０４か１以上の信号線を経由して分岐の枝ｓ５１０ａに至る経路があることを示す。
【０１０３】
なお、ステップ２０１ａおよび２０１ｂで頂点に付される名前は、互いに異なっていれば任意でよい。また、図１０に示す頂点ｓ５１７ａのように、入力枝と出力枝とが１本ずつ接続された頂点がエッジグラフに含まれている場合には、装置は、このような頂点を入力枝に接続された頂点（図１０では、頂点ＰＩ５０７）に併合する処理を行ってもよい。
【０１０４】
図８に示すテスト対象回路に対して第２の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ５０２の立上り遷移をテスト対象とし、｛ＰＩ５０１，ＰＩ５０２，ＰＩ５０３，ＰＩ５０４，ＰＩ５０５，ＰＩ５０６，ＰＩ５０７，ＰＩ５０８｝を｛Ｐ｝と記載する。
（ステップ２０１）装置は、図８に示すテスト対象回路に対して回路変換を行うことにより、図９に示すエッジグラフを求める。
（ステップ２０２）装置は、テスト対象の信号線および信号遷移として、信号線ｓ５０２の立上り遷移を選択する。これ伴い、信号線ｓ５０２、ｓ５０４、ｓ５０５が、グループ内の信号線となる。
【０１０５】
（ステップ１３）装置は、テスト対象信号線ｓ５０２に初期値０を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ５０２に初期値０を設定するために、制御点ＰＩ２に０を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ２０３へ進む。
【０１０６】
（ステップ２０３）装置は、グループ内の信号線ｓ５０２、ｓ５０４、ｓ５０５に対して、信号線ｓ５０２（グループ内の先頭の信号線に該当）に設定された故障値ＮＤを正しく伝搬させた場合に得られる故障値を設定する。これにより、信号線ｓ５０２、ｓ５０４、ｓ５０５には、故障値ＮＤが設定される。
（ステップ２０４）装置は、グループ内の信号線ｓ５０２、ｓ５０４、ｓ５０６に故障値ＮＤを設定あるいは伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ５０２、ｓ５０３には１が設定され、信号線ｓ５１０ａには０が設定される。これに伴い、制御点ＰＩ５０２、ＰＩ５０３には１が設定され、制御点ＰＩ５０４、ＰＩ５０５には０が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，１，０，０，Ｘ，Ｘ，Ｘ｝に更新される。
【０１０７】
（ステップ１０２）ステップ２０４では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０４）信号線ｓ５０５は分岐の幹であるので、装置は信号線ｓ５０５ａ、ｓ５０５ｂを到達候補信号線に設定し、ステップ１０８へ進む。
【０１０８】
（ステップ１０８）装置は、到達候補信号線ｓ５０５ａ、ｓ５０５ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ５０５ａの最長観測距離は４、信号線ｓ５０５ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ５０５ａを到達信号線として選択する。これに伴い、信号線ｓ５０５ａ、ｓ５０６が、グループ内の信号線となる。
（ステップ１０９）ステップ１０９で到達信号線を選択したので、装置はステップ２０６へ進む。
（ステップ２０６）装置は、グループ内の信号線ｓ５０５ａ、ｓ５０６に故障値を伝搬させるために、活性化、含意操作および正当化を行う。このステップが実行されるより前に、信号線ｓ５１１には１が設定されている。このため、新たに信号線に値を設定しなくても、グループ内の信号線ｓ５０５ａ、ｓ５０６には故障値ＮＤが伝搬する。
（ステップ１１１）ステップ２０６では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１０９】
（ステップ１０３〜１０４）信号線ｓ５０６は分岐の幹であるので、装置は信号線ｓ５０６ａ、ｓ５０６ｂを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ５０６ａ、ｓ５０６ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ５０６ａの最長観測距離は１、信号線ｓ５０６ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ５０６ｂを到達信号線として選択する。これに伴い、信号線ｓ５０６ｂ、ｓ５１３、ｓ５１４、ｓ５１５が、グループ内の信号線となる。
（ステップ２０６）装置は、グループ内の信号線ｓ５０６ｂ、ｓ５１３、ｓ５１４、ｓ５１５に故障値を伝搬させるために、活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、信号線ｓ５１９ａには０が設定されている。したがって、信号線ｓ５１３の故障値ＮＤを信号線ｓ５１４に伝搬させるために、装置が信号線ｓ５１９ａに１を設定すると、矛盾が発生する。
（ステップ１１１）ステップ２０６で矛盾が発生するので、装置はステップ１１２へ進む。
（ステップ１１２）装置は、到達候補信号線から到達信号線ｓ５０６ｂを除外する。この時点で、到達候補信号線は、信号線ｓ５０６ａのみとなる。
【０１１０】
（ステップ１０８）装置は、到達候補信号線ｓ５０６ａが属するグループを到達信号線として選択する。これに伴い、信号線ｓ５０６ａ、ｓ５０７が、グループ内の信号線となる。
（ステップ２０６）装置は、グループ内の信号線ｓ５０６ａ、ｓ５０７に故障値を伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ５０１および制御点ＰＩ５０１には０が設定され、信号線ｓ５０６ａ、ｓ５０７には故障値ＮＤが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛１，１，１，０，０，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１１１）ステップ２０６では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１１１】
（ステップ１０３）装置は、信号線ｓ５０７を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ５０７は観測点ＰＯ５０１に接続されており観測可能なので、装置はステップ１９へ進む。
【０１１２】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛１，１，１，０，０，Ｘ，Ｘ，Ｘ｝が生成される。
【０１１３】
以上に示すように、第２の生成方法によれば、複数の信号線について一括して活性化、含意操作および正当化を行うことにより、処理時間を短縮することができる。
【０１１４】
なお、以上の説明では、装置はステップ２０１で回路変換を行うこととしたが、これに代えて、到達信号線の活性化、含意操作および正当化を行う際に、分岐の枝（または外部入力）から分岐点を経由せずに接続する分岐の幹（または外部出力）までにある部分回路を１つのグループとして扱うこととしてもよい。この方法でも、同じ効果が得られる。
【０１１５】
＜第３の実施形態＞
図１１は、第３の生成方法を示すフロー図である。第３の生成方法は、第１の生成方法に対して、ステップ３０１および３０２を追加し、ステップ１０３をステップ３０３に置換したものである。第３の生成方法は、短い経路に含まれる分岐の枝を到達信号線の候補から予め除外しておくことを特徴とする。
【０１１６】
以下、テスト対象回路内のある点から別の点に至る経路の長さの最大値を、その２点間の最長距離という。また、テスト対象回路内の信号線について、各制御点から当該信号線を経由して各観測点に至る経路を考え、その経路の長さの最大値を、当該信号線の最長テスト経路長という。また、テスト対象回路内の制御点について、当該制御点から各観測点に至る経路を考え、その経路の長さの最大値を、当該制御点の最長テスト経路長という。なお、経路の長さは、回路の配線およびゲート遅延情報に基づく遅延時間や、経路上のゲート数や、経路上のビア数などに基づき算出される。
【０１１７】
第３の生成方法で初出のステップは、以下のとおりである。
（ステップ３０１）装置は、分岐の枝を到達候補信号線に含めるか否かを判断するための基準値を設定する。
（ステップ３０２）装置は、ステップ１１で選択したテスト対象信号線から任意の観測点に至る経路上の各分岐の枝について、最長テスト経路長を算出する。この長さは、選択されたテスト対象信号線と分岐の幹の間の最長距離と、分岐の枝と任意の観測点の間の最長距離とを加算することにより求められる。
（ステップ３０３）装置は、ステップ１０３と同様に到達候補信号線を更新する。ただし、到達信号線の出力側に接続される信号線が分岐の枝である場合には、最長テスト経路長がステップ３０１で設定された基準値以上の分岐の枝だけが、到達候補信号線に含められる。
【０１１８】
図５に示すテスト対象回路に対して第３の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ９の立上り遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ３０１）装置は、到達候補信号線の基準値を４に設定する。
（ステップ３０２）図５に示すテスト対象回路では、テスト対象信号線ｓ９から観測点ＰＯ１、ＰＯ２に至る経路上には、分岐の枝ｓ１０ａ、ｓ１０ｂが含まれている。ゲート段数で経路の長さを評価すると、テスト対象信号線ｓ９と分岐の幹ｓ１０の間の最長距離は１、分岐の枝ｓ１０ａと観測点ＰＯ１との間の最長距離は３、分岐の枝ｓ１０ｂと観測点ＰＯ２との間の最長距離は２である。したがって、分岐の枝ｓ１０ａ、ｓ１０ｂの最長テスト経路長は、それぞれ、４、３となる。
【０１１９】
（ステップ１３〜１６、１０１〜１０２）装置は、第１の生成方法と同じ処理を行う。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ３０３）装置は、信号線ｓ９を到達信号線に設定する。到達信号線の出力側に接続される信号線が分岐の枝ではないので、装置は、信号線ｓ１０を到達候補信号線に設定する。
（ステップ１０４〜１０７、１０２）装置は、第１の生成方法と同じ処理を行う。特にステップ１０６では、装置は、信号線ｓ１０を到達信号線に設定する。
【０１２０】
（ステップ３０３）到達信号線ｓ１０は分岐の幹であり、到達信号線ｓ１０の出力側には信号線ｓ１０ａ、ｓ１０ｂが接続されている。ここで、分岐の枝ｓ１０ａの最長テスト経路長は４で、ステップ３０１で設定された基準値以上である。一方、分岐の枝ｓ１０ｂの最長テスト経路長は３で、この基準値未満である。そこで、装置は、信号線ｓ１０ａを到達候補信号線に含めるが、信号線ｓ１０ｂを到達候補信号線に含めない。このように装置は、信号線ｓ１０ａを到達候補信号線に設定する。
（ステップ１０４〜１０６）到達候補信号線ｓ１０は１本かつ観測不可なので、装置は、信号線ｓ１０ａを到達信号線に設定する。
【０１２１】
（ステップ１０７）装置は、到達信号線ｓ１０ａの故障値Ｄを信号線ｓ７へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線ｓ６、ｓ６ａ、ｓ６ｂおよび制御点ＰＩ３には０が設定され、信号線ｓ７には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，Ｘ，Ｘ，Ｘ｝に更新される。
【０１２２】
（ステップ１０２）ステップ１０７では矛盾が発生していないので、装置はステップ３０３へ進む。
（ステップ３０３）装置は、信号線ｓ７を到達候補信号線に設定する。
（以降のステップ）装置は、第１の生成方法と同じ処理を行う。なお、第３の生成方法ではステップ１０３に代えてステップ３０３が実行されるが、到達信号線が分岐の枝でない場合、ステップ１０３の内容とステップ３０３の内容は同じである。
【０１２３】
以上の処理により、第１の生成方法と同様に、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。
【０１２４】
以上に示すように、第３の生成方法によれば、短い経路に含まれる分岐の枝を到達信号線の候補から予め除外しておくことにより、処理時間を短縮することができる。
【０１２５】
＜第４の実施形態＞
第４の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ４００（図１２）に置換したものである。ステップ４００は、ステップ１００において、ステップ１０１、１０７、１１０をそれぞれステップ４０１〜４０３に置換したものである。第４の生成方法は、ロバスト条件に従い活性化を行うことを特徴とする。ステップ４００では、検査系列Ｔ２に加えて、ステップ１４で生成された検査系列Ｔ１が更新される。
【０１２６】
第４の生成方法で初出のステップは、以下のとおりである。
（ステップ４０１）装置は、テスト対象信号線に故障値を設定し、設定した故障値を出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ロバスト条件に従い活性化を行う。
（ステップ４０２）装置は、到達信号線の出力側へゲート１段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ロバスト条件に従い活性化を行う。その後、装置はステップ１０２へ進む。
（ステップ４０３）装置は、ステップ４０２と同じ処理を行う。その後、装置はステップ１１１へ進む。
【０１２７】
図１３に示すテスト対象回路に対して第４の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ２５の立下り遷移をテスト対象とし、｛ＰＩ２１，ＰＩ２２，ＰＩ２３，ＰＩ２４，ＰＩ２５，ＰＩ２６，ＰＩ２７｝を｛Ｐ｝と記載する。
（ステップ１３）装置は、テスト対象信号線ｓ２５に初期値1を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ２５に初期値1を設定するために、制御点ＰＩ２２に１を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ３７に故障値Ｄを設定する。
【０１２８】
（ステップ４０１）装置は、テスト対象信号線ｓ３７に故障値Ｄを設定し、設定した故障値Ｄを信号線ｓ３０へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、制御点ＰＩ２２には０が設定され、信号線ｓ２９および制御点ＰＩ２４にはS１が設定され、信号線ｓ３０には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ４０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ３０（観測不可）を到達候補信号線に設定した後、信号線ｓ３０を到達信号線に設定する。
（ステップ４０２）到達信号線ｓ３０は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ１０２へ進む。
【０１２９】
（ステップ１０２）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０４）信号線ｓ３０は分岐の幹であるので、装置は、信号線ｓ３０ａ、ｓ３０ｂを到達候補信号線に設定し、ステップ１０８へ進む。
【０１３０】
（ステップ１０８）装置は、到達候補信号線ｓ３０ａ、ｓ３０ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ３０ａの最長観測距離は３、信号線ｓ３０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ３０ａを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ４０３へ進む。
（ステップ４０３）装置は、到達信号線ｓ３０ａの故障値Ｄを信号線ｓ２７へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、P２３にS1が設定され、信号線ｓ２７には故障値ＮＤが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，１，Ｘ，Ｘ，Ｘ｝、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，0，１，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１１１）ステップ４０３では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１３１】
（ステップ１０３〜１０６）装置は、信号線ｓ２７（観測不可）を到達候補信号線に設定した後、信号線ｓ２７を到達信号線に設定する。
（ステップ４０２）装置は、到達信号線ｓ２７の故障値ＮＤを信号線ｓ２８へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ３１および制御点ＰＩ２５にはＳ０が設定され、信号線ｓ２８にはＮＤが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，１，０，Ｘ，Ｘ｝、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，１，１，０，Ｘ，Ｘ｝に更新される。
【０１３２】
（ステップ１０２）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ２８（観測不可）を到達候補信号線に設定した後、信号線ｓ２８を到達信号線に設定する。
（ステップ４０２）装置は、到達信号線ｓ２８の故障値Ｄを信号線ｓ２４へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ２３、ｓ２２、ｓ２１および制御点ＰＩ２１にはＳ０が設定され、信号線ｓ２４には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛０，１，１，１，０，Ｘ，Ｘ｝、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，１，１，０，Ｘ，Ｘ｝に更新される。
【０１３３】
（ステップ１０２）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）装置は、信号線ｓ２４を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ２４は観測点ＰＯ２１に接続されており観測可能なので、装置はステップ１９へ進む。
【０１３４】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛０，１，１，１，０，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛Ｘ，０，１，１，０，Ｘ，Ｘ｝が生成される。なお、上記の例では、ロバスト条件での活性化、含意操作および正当化を行うときに、検査系列Ｔ１は更新されていないが、一般的には、ロバスト条件での活性化、含意操作および正当化を行うときに、検査系列Ｔ１は更新される。
【０１３５】
以上に示すように、第４の生成方法によれば、ロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延故障を、他の信号線上に遅延故障が発生したか否かにかかわらず検査することができる。
【０１３６】
＜第５の実施形態＞
第５の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ５００（図１４）に置換したものである。ステップ５００は、ステップ１００において、ステップ１０１、１０７、１１０をそれぞれステップ５０１〜５０３に置換したものである。第５の生成方法は、ノンロバスト条件に従い活性化を行うことを特徴とする。
【０１３７】
第５の生成方法で初出のステップは、以下のとおりである。
（ステップ５０１）装置は、テスト対象信号線に故障値を設定し、設定した故障値を出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ノンロバスト条件に従い活性化を行う。
（ステップ５０２）装置は、到達信号線の出力側へゲート１段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ノンロバスト条件に従い活性化を行う。その後、装置はステップ１０２へ進む。
（ステップ５０３）装置は、ステップ５０２と同じ処理を行う。その後、装置はステップ１１１へ進む。
【０１３８】
図５に示すテスト対象回路に対して第５の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ６の立下り遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１３）装置は、テスト対象信号線ｓ６に初期値１を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ６に初期値１を設定するために、制御点ＰＩ３に１を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ６に故障値Ｄを設定する。
【０１３９】
（ステップ５０１）装置は、テスト対象信号線ｓ６に故障値Ｄを設定するために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ６および制御点ＰＩ３には０が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝となる。
（ステップ１０２）ステップ５０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０４）信号線ｓ６は分岐の幹であるので、装置は、信号線ｓ６ａ、ｓ６ｂを到達候補信号線に設定し、ステップ１０８へ進む。
【０１４０】
（ステップ１０８）装置は、到達候補信号線ｓ６ａ、ｓ６ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ６ａの最長観測距離は２、信号線ｓ６ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ６ｂを到達信号線として選択する。
（ステップ１０９）ステップ１０８で矛盾が発生していないので、装置はステップ５０３へ進む。
（ステップ５０３）装置は、到達信号線ｓ６ｂの故障値Ｄを信号線ｓ７へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１０ａにはＵ０が設定され、信号線ｓ７には故障値Ｄが伝搬する。また、信号線ｓ９、ｓ５ｂおよび制御点ＰＩ２、ＰＩ４にはＵ１が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１１１）ステップ５０３では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１４１】
（ステップ１０３〜１０６）装置は、信号線ｓ７（観測不可）を到達候補信号線に設定した後、信号線ｓ７を到達信号線に設定する。
（ステップ５０２）装置は、テスト対象信号線ｓ７の故障値Ｄを信号線ｓ８へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１１および制御点ＰＩ５にはＵ０が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，０，Ｘ，Ｘ｝に更新される。
【０１４２】
（ステップ１０２）ステップ５０２では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ８（観測不可）を到達候補信号線に設定した後、信号線ｓ８を到達信号線に設定する。
（ステップ５０２）装置は、テスト対象信号線ｓ８の故障値ＮＤを信号線ｓ４へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ３、ｓ２、ｓ１および制御点ＰＩ１にはＵ０が設定され、信号線ｓ４には故障値Ｄが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝に更新される。
【０１４３】
（ステップ１０２）ステップ５０２では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）装置は、信号線ｓ４を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）信号線ｓ４は観測点ＰＯ１に接続されており観測可能であるので、装置はステップ１９へ進む。
【０１４４】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。
【０１４５】
以上に示すように、第５の生成方法によれば、ノンロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延の影響を、より長い経路を利用して検出することができる。
【０１４６】
＜第６の実施形態＞
第６の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ６００（図１５）に置換したものである。ステップ６００は、ステップ４００（図１２）に対してステップ６０１〜６０９を追加したものである。第６の生成方法は、ロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての到達候補信号線についてロバスト条件による活性化に失敗した場合には、ノンロバスト条件に従い活性化を行うことを特徴とする。ステップ６００では、検査系列Ｔ２に加えて、ステップ１４で生成された検査系列Ｔ１が更新される。
【０１４７】
第６の生成方法で初出のステップは、以下のとおりである。
（ステップ６０１）装置は、ステップ４０２で矛盾が発生した場合はステップ６０２へ進み、それ以外の場合はステップ１０３へ進む。
（ステップ６０２）装置は、ステップ５０２と同じ処理を行う。
（ステップ６０３）装置は、後で参照するために、その時点の到達候補信号線を保持する。
（ステップ６０４）装置は、ステップ６０３で保持した信号線を到達候補信号線に再設定する。
（ステップ６０５）装置は、ステップ１０８と同じ処理を行う。
（ステップ６０６）装置は、ステップ６０５で到達信号線を選択した場合にはステップ６０７へ進み、それ以外の場合はステップ１１へ進む。
（ステップ６０７）装置は、ステップ５０２と同じ処理を行う。
（ステップ６０８）装置は、ステップ６０７で矛盾が発生した場合はステップ６０９へ進み、それ以外の場合はステップ１０３へ進む。
（ステップ６０９）装置は、ステップ１１２と同じ処理を行う。その後、装置はステップ６０５へ進む。
【０１４８】
図１６に示すテスト対象回路に対して第６の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ１５０２の立下り遷移をテスト対象とし、｛ＰＩ１５０１，ＰＩ１５０２，ＰＩ１５０３，ＰＩ１５０４｝を｛Ｐ｝と記載する。
（ステップ１３）装置は、信号線ｓ１５０２に初期値１を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ１５０２に初期値１を設定するために、制御点ＰＩ１５０２に１を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ１５０２に故障値Ｄを設定する。
【０１４９】
（ステップ４０１）装置は、テスト対象信号線ｓ１５０２に故障値Ｄを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１５０２および制御点ＰＩ１５０２には０が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ４０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０４）信号線ｓ１５０２は分岐の幹であるので、装置は信号線ｓ１５０２ａ、ｓ１５０２ｂを到達候補信号線に設定し、ステップ６０３へ進む。
【０１５０】
（ステップ６０３）装置は、到達候補信号線ｓ１５０２ａ、ｓ１５０２ｂを保持する。
（ステップ１０８）装置は、到達候補信号線ｓ１５０２ａ、ｓ１５０２ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１５０２ａの最長観測距離は３、信号線ｓ１５０２ｂの最長観測距離は４である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１５０２ｂを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ４０３へ進む。
（ステップ４０３）装置は、到達信号線ｓ１５０２ｂの故障値Ｄを信号線ｓ１５０５へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１５０３および制御点ＰＩ１５０３にはＳ１が設定され、信号線ｓ１５０５には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，１，Ｘ｝に更新される。
（ステップ１１１）ステップ４０３では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１５１】
（ステップ１０３〜１０６）装置は、信号線ｓ１５０５（観測不可）を到達候補信号線に設定した後、信号線ｓ１５０５を到達信号線に設定する。
（ステップ４０２）到達信号線ｓ１５０５は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ６０１へ進む。
（ステップ６０１）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１５２】
（ステップ１０３〜１０４）信号線ｓ１５０５は分岐の幹であるので、装置は、信号線ｓ１５０５ａ、ｓ１５０５ｂを到達候補信号線に設定し、ステップ６０３へ進む。
（ステップ６０３）装置は、到達候補信号線ｓ１５０５ａ、ｓ１５０５ｂを保持する。
【０１５３】
（ステップ１０８）装置は、到達候補信号線ｓ１５０５ａ、ｓ１５０５ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１５０５ａの最長観測距離は３、信号線ｓ１５０５ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１５０５ａを到達信号線として選択する。信号線ｓ１５０５ａに伝搬した故障値は必ず信号線ｓ１５０８に伝搬するので、装置は、信号線ｓ１５０５ａを選択することにより、結果として、信号線ｓ１５０８を到達信号線として選択したことになる。信号線ｓ１５０８には故障値ＮＤが伝搬する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ４０３へ進む。
（ステップ４０３）装置は、到達信号線ｓ１５０８の故障値ＮＤを信号線ｓ１５０９へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１５０４ａおよび制御点ＰＩ１５０４にはＳ０が設定され、信号線ｓ１５０９には故障値ＮＤが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，０｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，０，１，０｝に更新される。
（ステップ１１１）ステップ４０３では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１５４】
（ステップ１０３〜１０６）装置は、信号線ｓ１５０９（観測不可）を到達候補信号線に設定した後、信号線ｓ１５０９を到達信号線に設定する。
（ステップ４０２）到達信号線ｓ１５０９は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ６０１へ進む。
（ステップ６０１）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１５５】
（ステップ１０３〜１０４）信号線ｓ１５０９は分岐の幹であるので、装置は信号線ｓ１５０９ａ、１５０９ｂ、１５０９ｃを到達候補信号線に設定し、ステップ６０３へ進む。
（ステップ６０３）装置は、到達候補信号線ｓ１５０９ａ、ｓ１５０９ｂ、１５０９ｃを保持する。
【０１５６】
（ステップ１０８）装置は、到達候補信号線ｓ１５０９ａ、１５０９ｂ、１５０９ｃの最長観測距離を求める。ゲート段数で観測距離を評価すると、これら３本の到達候補信号線の最長観測距離はいずれも１である。３本の到達候補信号線のいずれを選択してもよいので、装置は、到達候補信号線ｓ１５０９ａを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ１５０９ａの故障値ＮＤを信号線ｓ１５１１へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列Ｔ１における制御点ＰＩ１５０２の値は１に、信号線ｓ１５０７の値は１に決定されている。したがって、信号線ｓ１５０９ａの故障値ＮＤを信号線ｓ１５１１に伝搬させるために、装置が信号線ｓ１５０７にＳ０を設定すると、矛盾が発生する。
（ステップ１１１）ステップ２０６で矛盾が発生したので、装置はステップ１１２へ進む。
（ステップ１１２）装置は、到達候補信号線から到達信号線ｓ１５０９ａを除外する。この時点で、到達候補信号線は、信号線ｓ１５０９ｂ、ｓ１５０９ｃとなる。その後、装置はステップ１０８へ進む。
【０１５７】
（ステップ１０８）装置は、到達候補信号線ｓ１５０９ｂ、ｓ１５０９ｃの中から任意に到達候補信号線ｓ１５０９ｂを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ１５０９ｂの故障値ＮＤを信号線ｓ１５１２へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列Ｔ１における制御点ＰＩ１５０２、ＰＩ１５０３および信号線ｓ１５１０の値は１に決定されている。したがって、信号線ｓ１５０９ｂの故障値ＮＤを信号線ｓ１５１２に伝搬させるために、装置が信号線ｓ１５１０ａにＳ０を設定すると、矛盾が発生する。
（ステップ１１１）ステップ２０６で矛盾が発生したので、装置はステップ１１２へ進む。
（ステップ１１２）装置は、到達候補信号線から到達信号線ｓ１５０９ｂを除外する。この時点で、到達候補信号線は、信号線ｓ１５０９ｃのみとなる。その後、装置はステップ１０８へ進む。
【０１５８】
（ステップ１０８）装置は、到達候補信号線ｓ１５０９ｃを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ１５０９ｃの故障値ＮＤを信号線ｓ１５１３へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、上述したように、このステップが実行される前に、検査系列Ｔ１を与えるときの制御点ＰＩ１５１０の値は１に決定されている。したがって、信号線ｓ１５０９ｃの故障値ＮＤを信号線ｓ１５１３に伝搬させるために、装置が信号線ｓ１５１０ｂにＳ０を設定すると、矛盾が発生する。
（ステップ１１１）ステップ１１０で矛盾が発生したので、装置はステップ１１２へ進む。
（ステップ１１２）装置は、到達候補信号線から到達信号線ｓ１５０９ｃを除外する。この時点で、到達候補信号線はなくなる。その後、装置はステップ１０８へ進む。
【０１５９】
（ステップ１０８）到達候補信号線がないので、装置は、到達候補信号線を到達信号線として選択しない。
（ステップ１０９）ステップ１０８で到達信号線を選択しなかったので、装置はステップ６０４へ進む。
（ステップ６０４）装置は、ステップ６０３で保持した信号線ｓ１５０９ａ、１５０９ｂ、１５０９ｃを到達候補信号線に再設定する。
【０１６０】
（ステップ６０５）装置は、到達候補信号線ｓ１５０９ａ、１５０９ｂ、１５０９ｃの中から任意に到達候補信号線ｓ１５０９ａを到達信号線として選択する。
（ステップ６０６）ステップ６０５で到達信号線を選択したので、装置はステップ６０７へ進む。
（ステップ６０７）装置は、到達信号線ｓ１５０９ａの故障値ＮＤを信号線ｓ１５１１へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１５０７にはＵ０が設定され、制御点ＰＩ１５０１にはＵ１が設定され、信号線ｓ１５１１には故障値ＮＤが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，０｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，０，１，０｝に更新される。
（ステップ６０８）ステップ６０７では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１６１】
（ステップ１０３）装置は、信号線ｓ１５１１を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ１５１１は観測点ＰＯ１５０１に接続されており観測可能なので、装置はステップ１９へ進む。
【０１６２】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，１，１，０｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛１，０，１，０｝が生成される。
【０１６３】
以上に示すように、第６の生成方法によれば、ロバスト条件に従い活性化を行い、ある分岐点においてすべての到達候補信号線についてロバスト条件による活性化に失敗した場合には、ノンロバスト条件に従い活性化を行うことにより、ロバスト条件では検査できない故障を検査できるテストパターンを生成することができる。
【０１６４】
＜第７の実施形態＞
第７の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ７００（図１７）に置換したものである。ステップ７００は、ステップ６００（図１５）に対して、ステップ７０１を追加し、ステップ１１１、１１２、６０３〜６０６を削除したものである。第７の生成方法は、各到達候補信号線について、まずロバスト条件に従い活性化を行い、それに失敗した場合には、ノンロバスト条件に従い活性化を行うことを特徴とする。ステップ７００では、検査系列Ｔ２に加えて、ステップ１４で生成された検査系列Ｔ１が更新される。
【０１６５】
第７の生成方法で初出のステップは、以下のとおりである。
（ステップ７０１）装置は、ステップ４０３で矛盾が発生した場合はステップ６０７へ進み、それ以外の場合はステップ１０３へ進む。
【０１６６】
図５に示すテスト対象回路に対して第７の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ６の立下り遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１３〜１６）装置は、第５の生成方法と同じ処理を行う。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
【０１６７】
（ステップ４０１）装置は、テスト対象信号線ｓ６に故障値Ｄを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ６、ｓ６ａ、ｓ６ｂにはＵ０が設定され、制御点ＰＩ３には０が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ５０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０４）信号線ｓ６は分岐の幹であるので、装置は、信号線ｓ６ａ、ｓ６ｂを到達候補信号線に設定し、ステップ１０８へ進む。
【０１６８】
（ステップ１０８）装置は、到達候補信号線ｓ６ａ、ｓ６ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ６ａの最長観測距離は２、信号線ｓ６ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ６ｂを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ４０３へ進む。
（ステップ４０３）装置は、到達信号線ｓ６ｂの故障値Ｄを信号線ｓ２７へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１０ａにはＵ０が設定され、制御点ＰＩ２、ＰＩ４にはＵ１が設定され、信号線ｓ７には故障値Ｄが伝搬される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ７０１）ステップ４０３では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１６９】
（ステップ１０３〜１０６）装置は、信号線ｓ７（観測不可）を到達候補信号線に設定した後、信号線ｓ７を到達信号線に設定する。
（ステップ４０２）装置は、到達信号線ｓ７の故障値Ｄを信号線ｓ８へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１１および制御点ＰＩ５にはＵ０が設定され、信号線ｓ８には故障値ＮＤが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，１，０，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ４０２では矛盾が発生していないので、装置はステップ１０３へ進む。
【０１７０】
（ステップ１０３〜１０４）信号線ｓ８は分岐の幹であるので、装置は、信号線ｓ８ａ、ｓ８ｂを到達候補信号線に設定し、ステップ１０８へ進む。
【０１７１】
（ステップ１０８）装置は、到達候補信号線ｓ８ａ、ｓ８ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ８ａの最長観測距離は１、信号線ｓ８ｂの最長観測距離は０である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ８ｂを到達信号線として選択する。
（ステップ１０９）ステップ１０８で到達信号線を選択したので、装置はステップ４０３へ進む。
（ステップ４０３）装置は、到達信号線ｓ８aの故障値ＮＤを信号線ｓ４へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列Ｔ１における制御点ＰＩ３および信号線ｓ３の値は１に決定されている。したがって、信号線ｓ８ｂの故障値ＮＤを信号線ｓ４へ伝搬させるために、装置が信号線ｓ３にＳ０を設定すると、矛盾が発生する。
（ステップ７０１）ステップ７０１で矛盾が発生したので、装置はステップ６０７へ進む。
【０１７２】
（ステップ６０７）装置は、到達信号線ｓ８ｂの故障値ＮＤを信号線ｓ４へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１、ｓ２、ｓ３および制御点ＰＩ１にはＵ０が設定され、信号線ｓ４には故障値ＮＤが伝搬する。検査系列Ｔ２は｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ６０８では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３）装置は、信号線ｓ４を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ４は観測点ＰＯ１に接続されており観測可能なので、装置はステップ１９へ進む。
【０１７３】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。
【０１７４】
以上に示すように、第７の生成方法では、各到達候補信号線について、まずロバスト条件に従い活性化が行われ、それに失敗した場合には、ノンロバスト条件に従い活性化が行われる。このようにロバスト条件に従った活性化を優先して実行することにより、遅延故障の検出経路が同じ場合でも、高品質のテストパターンを生成することができる。
【０１７５】
なお、第６および第７の生成方法では、装置は、ロバスト条件で活性化できない場合には、ノンロバスト条件で活性化することとした。これに代えて、装置は、ロバスト条件で活性化できない場合には、ノンロバスト条件に代えて、図４６（ａ）に例示される経路活性化表および含意表に従って活性化を行ってもよい。また、装置は、ロバスト条件でもノンロバスト条件でも活性化できない場合には、図４６（ａ）に例示される経路活性化表および含意表に従って活性化を行ってもよい。
【０１７６】
＜第８の実施形態＞
第８の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ８００（図１８）に置換したものである。ステップ８００は、ステップ１００に対して、ステップ８０１、８０２、８０５〜８１０を追加し、ステップ１０９、１１１をステップ８０３、８０４に置換したものである。第８の生成方法は、ある分岐点ですべての到達候補信号線について活性化および正当化に失敗した場合には、直前に選択が行われた分岐点まで処理を戻す（バックトラックする）ことを特徴とする。
【０１７７】
第８の生成方法で初出のステップは、以下のとおりである。以下のステップでは、遷移経路集合と不到達信号線とが使用される。これら値の初期値は、空（要素なし）である。
（ステップ８０１）装置は、ステップ１０７で矛盾が発生した場合にはステップ８０５へ進み、それ以外の場合にはステップ８０２へ進む。
（ステップ８０２）装置は、その時点の到達信号線を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
（ステップ８０３）装置は、ステップ１０８で信号線を選択した場合にはステップ１１０へ進み、それ以外の場合にはステップ８０５へ進む。
（ステップ８０４）装置は、ステップ１１０で矛盾が発生した場合にはステップ１１２へ進み、それ以外の場合にはステップ８０２へ進む。
【０１７８】
（ステップ８０５）装置は、到達信号線から故障値の伝搬経路を遡った場合に、到達信号線と最初に現れる分岐の枝との間（両端の信号線を含む）にある信号線（以下、伝搬失敗信号線という）を求め、伝搬失敗信号線を不到達信号線に追加する。
（ステップ８０６）装置は、伝搬失敗信号線に故障値を伝搬するために割り当てた各信号線の値を元に戻す。
（ステップ８０７）装置は、伝搬失敗信号線の入力側信号線のうち、遷移経路集合に含まれる信号線を到達信号線に設定する。
（ステップ８０８）装置は、テスト対象信号線ではない到達信号線がある場合には、ステップ８０９へ進み、それ以外の場合にはステップ１１へ進む。
（ステップ８０９）装置は、ステップ８０７で設定された到達信号線の到達候補信号線を求め、不到達信号線に含まれない到達候補信号線がある場合にはステップ８１０へ進み、それ以外の場合にはステップ８０５へ進む。
（ステップ８１０）装置は、不到達信号線に含まれる信号線を到達候補信号線から削除する。その後、装置はステップ１０３へ進む。
【０１７９】
図８に示すテスト対象回路に対して第８の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ５０４の立上り遷移をテスト対象とし、｛ＰＩ５０１，ＰＩ５０２，ＰＩ５０３，ＰＩ５０４，ＰＩ５０５，ＰＩ５０６，ＰＩ５０７，ＰＩ５０８｝を｛Ｐ｝と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
（ステップ１３）装置は、テスト対象信号線ｓ５０４に初期値０を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ５０４に初期値０を設定するために、制御点ＰＩ５０２に０を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ５０４に故障値ＮＤを設定する。
【０１８０】
（ステップ１０１）装置は、テスト対象信号線ｓ５０４に故障値ＮＤを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、検査系列Ｔ２を与えるときの信号線ｓ５０２および制御点ＰＩ５０２の値には１が設定される。また、信号線ｓ５０３および制御点ＰＩ５０３にはＵ１が設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，１，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ１０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ５０４（観測不可）を到達候補信号線に設定した後、信号線ｓ５０４を到達信号線に設定する。
【０１８１】
（ステップ１０７）装置は、到達信号線ｓ５０４の故障値ＮＤを信号線ｓ５０５へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ５１０ａおよび制御点ＰＩ５０４、ＰＩ５０５にはＳ０が設定され、信号線ｓ５０５には故障値ＮＤが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，０，Ｘ，０，０，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，１，０，０，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ５０４を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０１８２】
（ステップ１０３〜１０６）装置は、信号線ｓ５０５（観測不可）を到達候補信号線に設定した後、信号線ｓ５０５を到達信号線に設定する。
（ステップ１０７）到達信号線ｓ５０５は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ８０１へ進む。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ５０５を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０１８３】
（ステップ１０３〜１０４）信号線ｓ５０５は分岐の幹であるので、装置は信号線ｓ５０５ａ、ｓ５０５ｂを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ５０５ａ、ｓ５０５ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ５０５ａの最長観測距離は４、信号線ｓ５０５ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ５０５ａを到達信号線として選択する。
（ステップ８０３）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ５０５ａの故障値ＮＤを信号線ｓ５０６へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、信号線ｓ５１０にはＳ０が設定されおり、信号線ｓ５１１にはＳ１が設定されている。このため、新たに信号線に値を設定しなくても、信号線ｓ５０６には故障値ＮＤが伝搬する。
（ステップ８０４）ステップ１１０では矛盾が発生していないので、装置はステップ８０２へ進む。
【０１８４】
（ステップ８０２）装置は、到達信号線ｓ５０５ａを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ５０６（観測不可）を到達候補信号線に設定した後、信号線ｓ５０６を到達信号線に設定する。
（ステップ１０７）到達信号線ｓ５０６は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ８０１へ進む。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ５０６を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０１８５】
（ステップ１０３〜１０４）信号線ｓ５０６は分岐の幹であるので、装置は信号線ｓ５０６ａ、ｓ５０６ｂを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ５０６ａ、ｓ５０６ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ５０６ａの最長観測距離は１、信号線ｓ５０５ｂの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ５０６ｂを到達信号線として選択する。
（ステップ８０３）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ５０６ｂの故障値ＮＤを信号線ｓ５１３へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、信号線ｓ５１０ｃにはＳ０が設定されている。このため、新たに信号線に値を設定しなくても、信号線ｓ５１３には故障値ＮＤが伝搬する。
（ステップ８０４）ステップ１１０では矛盾が発生していないので、装置はステップ８０２へ進む。
【０１８６】
（ステップ８０２）装置は、到達信号線ｓ５０６ｂを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ５１３（観測不可）を到達候補信号線に設定し、信号線ｓ５１３を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ５１３の故障値ＮＤを信号線ｓ５１４へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、制御点ＰＩ５０５および信号線ｓ５１９ａにはＳ０が設定されている。したがって、信号線ｓ５１３の故障値ＮＤを信号線ｓ５１４に伝搬させるために、装置が信号線ｓ５１９ａにＵ１を設定すると、矛盾が発生する。
（ステップ８０１）ステップ１０７で矛盾が発生したので、装置はステップ８０５へ進む。
【０１８７】
（ステップ８０５）この時点で、到達信号線ｓ５１３から故障値の伝搬経路を遡った場合に、到達信号線ｓ５１３と最初に現れる分岐の枝ｓ５０６ｂとの間には、信号線ｓ５１３、ｓ５０６ｂが存在する。そこで、装置は、これら伝搬失敗信号線ｓ５１３、ｓ５０６ｂを不到達信号線に追加する。
（ステップ８０６）装置は、伝搬失敗信号線ｓ５１３、ｓ５０６ｂに故障値を伝搬させるために設定した信号線の値を元に戻す。この例では、伝搬失敗信号線ｓ５１３、ｓ５０６ｂに故障値を伝搬させるために値が設定された信号線はないので、このステップでは何も行われない。
（ステップ８０７）装置は、伝搬失敗信号線ｓ５１３、ｓ５０６の入力側信号線のうち、遷移経路集合に含まれる信号線ｓ５０６を到達信号線に設定する。
【０１８８】
（ステップ８０８）テスト対象信号線ｓ５０４ではない到達信号線があるので、装置はステップ８０９へ進む。
（ステップ８０９）装置は、到達信号線ｓ５０６の出力側に接続される信号線ｓ５０６ａ、ｓ５０６ｂを到達候補信号線に設定する。このうち信号線ｓ５０６ａは不到達信号線に含まれていないので、装置はステップ８１０へ進む。
（ステップ８１０）装置は、不到達信号線に含まれる信号線ｓ６０６ｂを、到達候補信号線から削除する。その結果、到達候補信号線には、信号線ｓ６０６ａのみが含まれる。その後、装置はステップ１０３へ進む。
【０１８９】
（ステップ１０３〜１０６）装置は、信号線ｓ５０６ａ（観測不可）を到達候補信号線に設定し、信号線ｓ５０６ａを到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ５０６ａの故障値ＮＤを信号線ｓ５０７へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ５０１および制御点ＰＩ５０１にはＳ０が設定される。検査系列Ｔ１は｛Ｐ｝＝｛０，０，Ｘ，０，０，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛０，１，１，０，０，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ５０６ａを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０１９０】
（ステップ１０３）装置は、信号線ｓ５０７を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ５０７は観測点ＰＯ１に接続されており観測可能なので、装置はステップ１９へ進む。
【０１９１】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛０，０，Ｘ，０，０，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，１，０，０，Ｘ，Ｘ，Ｘ｝が生成される。
【０１９２】
以上に示すように、第８の生成方法によれば、ある分岐点ですべての到達候補信号線について活性化および正当化に失敗した場合には、直前に選択が行われた分岐点までバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【０１９３】
＜第９の実施形態＞
第９の生成方法は、第３の生成方法（図１１）において、ステップ３００をステップ９００（図１９）に置換したものである。ステップ９００は、ステップ８００（図１８）において、ステップ１０３、８０９をそれぞれステップ３０３、９０１に置換したものである。第９の生成方法は、所定の基準を満たす直近の分岐点までバックトラックすることを特徴とする。
【０１９４】
第９の生成方法で初出のステップは、以下のとおりである。
（ステップ９０１）装置は、ステップ８０７で設定された到達信号線の到達候補信号線を求め、不到達信号線に含まれず、かつ、所定の基準を満たす到達候補信号線がある場合にはステップ８１０へ進み、それ以外の場合はステップ３０２へ進む。なお、ここでは、到達候補信号線の最長テスト経路長がステップ３０１で設定された基準値以上である場合に、当該到達候補信号線は基準を満たすという。
【０１９５】
図８に示すテスト対象回路に対して第９の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ５０４の立上り遷移をテスト対象とし、｛ＰＩ５０１，ＰＩ５０２，ＰＩ５０３，ＰＩ５０４，ＰＩ５０５，ＰＩ５０６，ＰＩ５０７，ＰＩ５０８｝を｛Ｐ｝と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
（ステップ３０１）装置は、到達信号線の基準値を４に設定する。
（ステップ３０２）図８に示すテスト対象回路では、テスト対象信号線ｓ５０４から観測点ＰＯ５０１、ＰＯ５０２、ＰＯ５０３に至る経路上には、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ａ、ｓ５０６ｂが含まれている。ゲート段数で経路の長さを評価すると、テスト対象信号線ｓ５０４から分岐の幹ｓ５０５までの最長距離は１、テスト対象信号線ｓ５０４から分岐の幹ｓ５０６までの最長距離は２、分岐の枝ｓ５０５ａ、５０５ｂ、５０６ａ、５０６ｂから３つの観測点までの最長距離は、それぞれ、４、３、１、３である。したがって、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ａ、ｓ５０６ｂの最長テスト経路長は、それぞれ、５、４、３、５となる。
【０１９６】
第９の生成方法では、最長テスト経路長がステップ３０１で設定された基準値以上の分岐の枝だけが、基準を満たす分岐の枝として扱われ、到達候補信号線として設定される。したがって、この例では、上記４本の分岐の枝のうち、分岐の枝ｓ５０６ａは、ステップ３０３、９０１では、到達候補信号線として設定されない。ステップ３０２以降の処理は、このような条件下で実行される。このため、第９の生成方法によれば、以下に示すように、第８の生成方法とは異なるテストパターンが生成される。
【０１９７】
第８の生成方法では、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ａ、ｓ５０６ｂは、故障値を伝搬させる経路として選択され得る。装置は、信号線ｓ５０４に設定された故障値を伝搬させる際に、まず分岐の枝ｓ５０５ａ、５０５ｂのうちから、最長テスト経路長が長いほうの分岐の枝ｓ５０５ａを選択し、次に分岐の枝ｓ５０６ａ、ｓ５０６ｂのうちから、最長テスト経路長が長いほうの分岐の枝ｓ５０６ｂを選択する。分岐の枝ｓ５０６ｂより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。そこで、装置は、バックトラック処理（ステップ８０５〜８１０）を行い、直前に選択を行った分岐点までバックトラックする。その後、装置は、故障値を分岐の枝ｓ５０６ａ経由で観測点ＰＯ５０１へ伝搬させる。
【０１９８】
これに対して、第９の生成方法では、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ｂは、故障値を伝搬させる経路として選択され得るが、分岐の枝ｓ５０６ａは、故障値を伝搬させる経路として選択され得ない。装置は、信号線ｓ５０４に設定された故障値を伝搬させる際に、まず分岐の枝ｓ５０５ａ、５０５ｂのうちから、最長テスト経路長が長いほうの分岐の枝ｓ５０５ａを選択し、次に、選択し得る唯一の分岐の枝ｓ５０６ｂを選択する。分岐の枝ｓ５０６ｂより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。そこで、装置は、バックトラック処理（ステップ８０５〜８０８、９０１、８１０）を行う。この際ステップ９０１では、装置は、不到達信号線に含まれず、かつ、最長テスト経路長が基準値４以上の到達候補信号線として、分岐の枝ｓ５０５ｂを選択する。その後、装置は、故障値を分岐の枝ｓ５０５ｂ経由で観測点ＰＯ５０３へ伝搬させる。
【０１９９】
装置は、信号線ｓ５０５の故障値ＮＤを分岐の枝ｓ５０５ｂ経由で観測点ＰＯ５０３へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。なお、これら３つの処理は、故障値をゲート１段分だけ伝搬させるたびに行われる。これにより、信号線ｓ５４０、ｓ５２４にはそれぞれＳ０、Ｕ１が設定され、制御点ＰＩ５０７にはＳ０が設定される。
【０２００】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，０，Ｘ，０，０，Ｘ，０，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，１，０，０，Ｘ，０，Ｘ｝が生成される。
【０２０１】
以上に示すように、第９の生成方法によれば、バックトラックを行う際に戻り先を制限することにより、処理時間を短縮することができる。
【０２０２】
＜第１０の実施形態＞
第１０の生成方法は、第３の生成方法（図１１）において、ステップ３００をステップ１０００（図２０）に置換したものである。ステップ１０００は、ステップ９００（図１９）において、ステップ８０７をステップ１００１および１００２に置換し、ステップ９０１をステップ１００３に置換し、ステップ８１０を削除したものである。第１０の生成方法は、選択されていない分岐の枝を含む最長テスト経路長が最も長い分岐点までバックトラックすることを特徴とする。
【０２０３】
第１０の生成方法で初出のステップは、以下のとおりである。
（ステップ１００１）装置は、ステップ１１で選択したテスト対象信号線から任意の観測点に至る経路上の各分岐の枝について、最長テスト経路長を算出する。ただし、不到達信号線を含む経路は、最長テスト経路長の算出には使用されないものとする。
（ステップ１００２）装置は、遷移経路集合に含まれる分岐の幹のうち、ステップ１００１で算出された最長テスト経路長が最長の分岐の枝に接続されたものを、到達信号線に設定する。
（ステップ１００３）装置は、到達信号線の分岐の枝の中で、最長テスト経路長が最長で、かつ、所定の基準を満たすものがある場合にはステップ３０３へ進み、それ以外の場合にはステップ８０５へ進む。なお、ここでは、到達候補信号線の最長テスト経路長がステップ３０１で設定された基準値以上である場合に、当該到達候補信号線は基準を満たすという。
【０２０４】
図８に示すテスト対象回路に対して第１０の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ５０４の立上り遷移をテスト対象とし、｛ＰＩ５０１，ＰＩ５０２，ＰＩ５０３，ＰＩ５０４，ＰＩ５０５，ＰＩ５０６，ＰＩ５０７，ＰＩ５０８｝を｛Ｐ｝と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行い、ステップ３０１では到達信号線の基準値を４に設定するものとする。
【０２０５】
第１０の生成方法は、バックトラック処理を除き、第９の生成方法と同じである。したがって、第１０の生成方法でも、第９の生成方法と同様に、故障値を伝搬させる経路として選択され得るのは、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ｂに限られる。装置は、信号線ｓ５０４に設定された故障値を伝搬させる際に、まず分岐の枝ｓ５０５ａ、５０５ｂのうちから、最長テスト経路長が長いほうの分岐の枝ｓ５０５ａを選択し、次に、選択し得る唯一の分岐の枝ｓ５０６ｂを選択する。分岐の枝ｓ５０６ｂより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。ここで、装置は、第９の生成方法とは異なるバックトラック処理（ステップ８０５、８０６、８０８、１００１〜１００３）を行う。
【０２０６】
（ステップ１００１）この時点で不到達信号線には、信号線ｓ５１３、ｓ５０６ｂが含まれている。また、図８に示すテスト対象回路では、テスト対象信号線ｓ５０４から観測点に至る経路上には、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ａ、ｓ５０６ｂが含まれている。そこで、装置は、これら４本の分岐の枝について、信号線ｓ５１３、ｓ５０６ｂを含まない経路だけを考慮した最長テスト経路長を算出する。これにより、分岐の枝ｓ５０５ａ、ｓ５０５ｂ、ｓ５０６ａ、ｓ５０６ｂの最長テスト経路長は、それぞれ、３、４、３、０となる。
（ステップ１００２）装置は、遷移経路集合に含まれる分岐の幹のうち、ステップ１００１で算出された最長テスト経路長が最長の分岐の枝に接続されたものとして、分岐の幹ｓ５０５を到達信号線に設定する。
（ステップ８０８）テスト対象信号線ｓ５０４でない到達信号線があるので、装置はステップ１００３へ進む。
（ステップ１００３）このステップが実行される時点で、到達信号線ｓ５０５の分岐の枝ｓ５０５ａ、５０５ｂの中で、最長テスト経路長が最長であるのは分岐の枝ｓ５０５ｂである。また、分岐の枝ｓ５０５ｂの最長テスト経路長は、基準値４以上であり基準を満たす。そこで、装置は、ステップ１０３へ進む。
【０２０７】
その後、装置は、故障値を分岐の枝ｓ５０５ｂ経由で観測点ＰＯ５０３へ伝搬させる。したがって、第１０の生成方法によれば、第９の生成方法と同様に、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，０，Ｘ，０，０，Ｘ，０，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，１，０，０，Ｘ，０，Ｘ｝が生成される。
【０２０８】
以上に示すように、第１０の生成方法によれば、バックトラックを行う際の戻り先を制限し、より長い経路を優先的に選択することにより、テスト対象信号線の遅延の影響をより長い経路で伝搬して検出することができる。
【０２０９】
＜第１１の実施形態＞
第１１の生成方法は、第１の生成方法（図４）において、ステップ１００をステップ１１００（図２１）に置換したものである。ステップ１１００は、ステップ８００（図１８）からステップ８０６を削除したものである。第１１の生成方法は、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を保持したままにすることを特徴とする。
【０２１０】
図２２に示すテスト対象回路に対して第１１の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ１９０３の立下り遷移をテスト対象とし、｛ＰＩ１９０１，ＰＩ１９０２，ＰＩ１９０２，ＰＩ１９０３，ＰＩ１９０４，ＰＩ１９０５，ＰＩ１９０６，ＰＩ１９０７，ＰＩ１９０８｝を｛Ｐ｝と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
（ステップ１３）装置は、テスト対象信号線ｓ１９０３に初期値１を設定する。
（ステップ１４）装置は、テスト対象信号線ｓ１９０３に初期値１を設定するために、制御点ＰＩ１９０３に１を設定する。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１５）検査系列Ｔ１の生成に成功したので、装置はステップ１６へ進む。
（ステップ１６）装置は、テスト対象信号線ｓ１９０３に故障値Ｄを設定する。
【０２１１】
（ステップ１０１）装置は、テスト対象信号線ｓ１９０３に故障値Ｄを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、検査系列Ｔ２における制御点ＰＩ１９０３の値は０に設定される。検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ１０２）ステップ１０１では矛盾が発生していないので、装置はステップ１０３へ進む。
（ステップ１０３〜１０６）装置は、信号線ｓ１９０９（観測不可）を到達候補信号線に設定し、信号線ｓ１９０９を到達信号線に設定する。
【０２１２】
（ステップ１０７）装置は、到達信号線ｓ１９０３の故障値Ｄを信号線ｓ１９０９へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０２および制御点ＰＩ１９０２にはＳ１が設定される。検査系列Ｔ１は｛Ｐ｝＝｛Ｘ，１，１，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛Ｘ，１，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９０３を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２１３】
（ステップ１０３〜１０４）信号線ｓ１９０９は分岐の幹であるので、装置は信号線ｓ１９０９ａ、ｓ１９０９ｂ、ｓ１９０９ｃを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ１９０９ａ、ｓ１９０９ｂ、１９０９ｃの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１９０９ａの最長観測距離は６、信号線ｓ１９０９ｂの最長観測距離は５、信号線ｓ１９０９ｃの最長観測距離は３である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１９０９ａを到達信号線として選択する。
（ステップ８０３）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
【０２１４】
（ステップ１１０）装置は、到達信号線ｓ１９０９ａの故障値Ｄを信号線ｓ１９１０へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０１ｂおよび制御点ＰＩ１９０１にはＳ１が設定され、信号線ｓ１９１０には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛１，１，１，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，１，０，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０４）ステップ１１０では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９０９ａを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２１５】
（ステップ１０３〜１０６）装置は、信号線ｓ１９１０（観測不可）を到達候補信号線に設定し、信号線ｓ１９１０を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ１９１０の故障値Ｄを信号線ｓ１９１５へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、制御点ＰＩ１９０１、ＰＩ１９０２にはＳ１が設定されており、信号線ｓ１９１４ｃにはＳ０が設定されている。したがって、到達信号線ｓ１９１０の故障値Ｄを信号線ｓ１９１５へ伝搬させるために、装置が信号線ｓ１９１４ｃにＳ１を設定すると、矛盾が発生する。
（ステップ８１０）ステップ１０７で矛盾が発生したので、装置はステップ８０５へ進む。
【０２１６】
（ステップ８０５）装置は、伝搬失敗信号線ｓ１９１０、ｓ１９０９ａを不到達信号線に追加する。
（ステップ８０７）装置は、伝搬失敗信号線ｓ１９１０、ｓ１９０９ａの入力側信号線のうち、遷移経路集合に含まれる信号線ｓ１９０９を到達信号線に設定する。
（ステップ８０８）テスト対象信号線ｓ１９０３ではない到達信号線があるので、装置はステップ８０９へ進む。
（ステップ８０９）装置は、到達信号線ｓ１９０９の出力側に接続される信号線ｓ１９０９ａ、１９０９ｂ、１９０９ｃを到達候補信号線に設定する。このうち信号線ｓ１９０９ｂ、１９０９ｃは不到達信号線に含まれていないので、装置はステップ８１０へ進む。
（ステップ８１０）装置は、不到達信号線に含まれる信号線ｓ１９０９ａを到達候補信号線から削除する。その結果、到達候補信号線には、信号線ｓ１９０９ｂ、１９０９ｃが含まれる。その後、装置はステップ１０３へ進む。
【０２１７】
（ステップ１０３〜１０４）信号線ｓ１９０９は分岐の幹であるので、装置は信号線ｓ１９０９ｂ、ｓ１９０９ｃを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ１９０９ｂ、１９０９ｃの中から任意に到達候補信号線ｓ１９０９ｂを到達信号線として選択する。
（ステップ８０３）ステップ１０９で到達信号線を選択したので、装置はステップ１１０へ進む。
【０２１８】
（ステップ１１０）装置は、到達信号線ｓ１９０９ｂの故障値Ｄを信号線ｓ１９１１へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０４および制御点ＰＩ１９０４にはＳ１が設定され、信号線ｓ１９１１には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛１，１，１，１，Ｘ，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，１，０，１，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０４）ステップ１１０では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９０９ｂを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２１９】
（ステップ１０３〜１０６）装置は、信号線ｓ１９１１（観測不可）を到達候補信号線に設定し、信号線ｓ１９１１を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ１９１１の故障値Ｄを信号線ｓ１９１６へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、制御点ＰＩ１９０１、ＰＩ１９０２にはＳ１が設定されており、信号線ｓ１９１５にはＳ０が設定されている。したがって、信号線に新たに値を設定しなくても、信号線ｓ１９１６には故障値Ｄが伝搬する。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９１１を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２２０】
（ステップ１０３〜１０６）装置は、信号線ｓ１９１６（観測不可）を到達候補信号線に設定した後、信号線ｓ１９１６を到達信号線に設定する。
（ステップ１０７）到達信号線ｓ１９１６は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ８０１へ進む。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９１６を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２２１】
（ステップ１０３〜１０４）信号線ｓ１９１６は分岐の幹であるので、装置は信号線ｓ１９１６ａ、ｓ１９１６ｂを到達候補信号線に設定し、ステップ１０８へ進む。
（ステップ１０８）装置は、到達候補信号線ｓ１９１６ａ、ｓ１９１６ｂの最長観測距離を求める。ゲート段数で観測距離を評価すると、２本の到達候補信号線の最長観測距離は、いずれも３である。そこで、装置は、このうち任意に到達候補信号線ｓ１９１６ａを到達信号線として選択する。
（ステップ８０３）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
【０２２２】
（ステップ１１０）装置は、到達信号線ｓ１９１６ａの故障値Ｄを信号線ｓ１９１７へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、制御点ＰＩ１９０１、ＰＩ１９０２にはＳ０が設定され、信号線ｓ１９１４ｂにはＳ０が設定されている。したがって、到達信号線ｓ１９１６ａの故障値Ｄを信号線ｓ１９１７へ伝搬させるために、装置が信号線ｓ１９１４ｂにＳ１を設定すると、矛盾が発生する。
（ステップ８０４）ステップ１１０で矛盾が発生したので、装置はステップ１１２へ進む。
（ステップ１１２）装置は、到達信号線ｓ１９１６ａを到達候補信号線から除外する。この結果、到達候補信号線には、信号線ｓ１９１６ｂのみが含まれる。
【０２２３】
（ステップ１０８）装置は、唯一の到達候補信号線であるｓ１９１６ｂを選択する。
（ステップ８０３）ステップ１０８で到達信号線を選択したので、装置はステップ１１０へ進む。
（ステップ１１０）装置は、到達信号線ｓ１９１６ｂの故障値Ｄを信号線ｓ１９２４へ伝搬させるために、活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、制御点ＰＩ１９０１、ＰＩ１９０２にはＳ０が設定され、信号線ｓ１９１６ａにはＳ０が設定されている。したがって、到達信号線ｓ１９１６ｂの故障値Ｄを信号線ｓ１９２４へ伝搬させるために、装置が信号線ｓ１９１４ａにＳ１を設定すると、矛盾が発生する。
（ステップ８０４）ステップ１１０で矛盾が発生したので、装置はステップ１１２へ進む。
【０２２４】
（ステップ１１２）装置は、到達信号線ｓ１９１６ｂを到達候補信号線から除外する。この結果、到達候補信号線に含まれる信号線がなくなる。
（ステップ１０８）到達候補信号線に含まれる信号線がないので、装置は到達候補信号線を選択しない。
（ステップ８０３）到達信号線がないので、装置はステップ８０５へ進む。
（ステップ８０５）装置は、伝搬失敗信号線ｓ１９１１を不到達信号線に追加する。
（ステップ８０７）装置は、伝搬失敗信号線ｓ１９１１の入力側信号線のうち、遷移経路集合に含まれる信号線ｓ１９０９を到達信号線に設定する。
【０２２５】
（ステップ８０８）テスト対象信号線ｓ１９０３ではない到達信号線があるので、装置はステップ８０９へ進む。
（ステップ８０９）装置は、到達信号線ｓ１９０９の出力側に接続される信号線ｓ１９０９ａ、ｓ１９０９ｂ、ｓ１９０９ｃを到達候補信号線に設定する。このうち信号線ｓ１９０９ｃは不到達信号線に含まれていないので、装置はステップ８１０へ進む。
（ステップ８１０）装置は、不到達信号線に含まれる信号線ｓ１９０９ａ、ｓ１９０９ｂを到達候補信号線から削除する。その結果、到達候補信号線には、信号線ｓ１９０９ｃのみが含まれる。その後、装置はステップ１０３へ進む。
【０２２６】
（ステップ１０３〜１０６）装置は、信号線ｓ１９０９ｃを到達候補信号線に設定し、信号線ｓ１９０９ｃを到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ１９０９ｃの故障値Ｄを信号線ｓ１９２０へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０５および制御点ＰＩ１９０５にはＳ１が設定され、信号線ｓ１９２０には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛１，１，１，１，１，Ｘ，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，１，０，１，１，Ｘ，Ｘ，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９０９ｃを遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２２７】
（ステップ１０３〜１０６）装置は、信号線ｓ１９２１を到達候補信号線に設定し、信号線ｓ１９２１を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ１９２０の故障値Ｄを信号線ｓ１９２１へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０６および制御点ＰＩ１９０６にはＳ１が設定され、信号線ｓ１９２１には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛１，１，１，１，１，１，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，１，０，１，１，１，Ｘ，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９２０を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２２８】
（ステップ１０３〜１０６）装置は、信号線ｓ１９２１を到達候補信号線に設定し、信号線ｓ１９２１を到達信号線に設定する。
（ステップ１０７）装置は、到達信号線ｓ１９２１の故障値Ｄを信号線ｓ１９２３へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線ｓ１９０７および制御点ＰＩ１９０７にはＵ０が設定され、信号線ｓ１９２１には故障値Ｄが伝搬する。検査系列Ｔ１は｛Ｐ｝＝｛１，１，１，１，１，１，Ｘ，Ｘ｝に更新され、検査系列Ｔ２は｛Ｐ｝＝｛１，１，０，１，１，１，０，Ｘ｝に更新される。
（ステップ８０１）ステップ１０７では矛盾が発生していないので、装置はステップ８０２へ進む。
（ステップ８０２）装置は、到達信号線ｓ１９２１を遷移経路集合に追加する。その後、装置はステップ１０３へ進む。
【０２２９】
（ステップ１０３）装置は、信号線ｓ１９２３を到達候補信号線に設定する。
（ステップ１０４）到達候補信号線が１本なので、装置はステップ１０５へ進む。
（ステップ１０５）到達候補信号線ｓ１９２３は観測点ＰＯ１に接続されており観測可能なので、装置はステップ１９へ進む。
【０２３０】
以上の処理により、検査系列Ｔ１として｛Ｐ｝＝｛１，１，１，１，１，１，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛１，１，０，１，１，１，０，Ｘ｝が生成される。
【０２３１】
ここで、第１１の生成方法とは異なり、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を元に戻す処理を行うテストパターン生成方法を考える。図２２に示すテスト対象回路に対してこの方法を実行すると、ゲートｇ１９１１、ｇ１９１３の出力へ故障値を伝搬させるための活性化を行うときに、ゲートｇ１９０２の出力へ故障値を伝搬させるときに求めたｓ１９０１の値を繰り返し求める必要があり、処理時間が長くなる。
【０２３２】
以上に示すように、第１１の生成方法によれば、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を保持したままにすることにより、故障値を伝搬させるときに信号線に割り当てた値を保持する必要がなくなる。したがって、処理時間を短縮し、メモリ使用量を削減することができる。
【０２３３】
なお、第８〜第１１の実施形態では、ステップ８０５〜８０８では、装置は、ゲート１段分ずつバックトラックすることとしたが、これに代えて、１回の処理で、複数の到達候補信号線に接続された分岐の幹までバックトラックしてもよい。この場合、遷移経路集合に含まれる分岐の枝は、不到達信号線に設定される。また、これまでの説明では、装置はロバスト条件に従い活性化を行うこととしたが、これに代えて、ノンロバスト条件に従い活性化を行ってもよく、図４６（ａ）に例示される経路活性化表を用いた活性化を行ってもよい。
【０２３４】
＜第１２の実施形態＞
図２３は、第１２の生成方法を示すフロー図である。第１２の生成方法は、第１の生成方法に対して、ステップ１２０１、１２０２を追加したものである。第１２の生成方法は、所定の基準を満たさない制御点および信号線を除外して処理することを特徴とする。
【０２３５】
第１２の生成方法で初出のステップは、以下のとおりである。
（ステップ１２０１）装置は、制御点および信号線に関する基準値を設定する。なお、この基準値は、人手で入力してもよく、電子計算機を用いて入力してもよい。
（ステップ１２０２）装置は、テスト対象回路に含まれる制御点および分岐の枝について最長テスト経路長を求める。
【０２３６】
第１２の生成方法では、制御点の最長テスト経路長がステップ１２０１で設定された基準値よりも短い場合には、装置は、当該制御点をテスト対象信号線から除外する。すなわち、このような制御点は、ステップ１１で選択されない。また、分岐の枝の最長テスト経路長がステップ１２０１で設定された基準値よりも短い場合には、装置は、当該分岐の枝をテスト対象信号線から除外し、信号線を選択するときに信号線選択の候補から除外する。すなわち、このような分岐の枝は、ステップ１１で選択されず、ステップ１０８で到達信号線として選択されない。
【０２３７】
図５に示すテスト対象回路に対して第１１の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ９の立上り遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１２０１）装置は、制御点および信号線に関する基準値を４に設定する。
（ステップ１２０２）図５に示すテスト対象回路は、制御点ＰＩ１、ＰＩ２、ＰＩ３、ＰＩ４、ＰＩ５、ＰＩ６、ＰＩ７、および、分岐の枝ｓ５ａ、ｓ５ｂ、ｓ５ｃ、ｓ６ａ、ｓ６ｂ、ｓ１０ａ、ｓ１０ｂを含んでいる。装置は、これら制御点および分岐の枝について最長テスト経路長を求める。その結果、制御点ＰＩ１、ＰＩ２、ＰＩ３、ＰＩ４、ＰＩ５、ＰＩ６、ＰＩ７の最長テスト経路長は、それぞれ、３、４、３、４、２、３、１となり、分岐の枝ｓ５ａ、ｓ５ｂ、ｓ５ｃ、ｓ６ａ、ｓ６ｂ、ｓ１０ａ、ｓ１０ｂの最長テスト経路長は、３、４、３、２、３、４、３となる。
【０２３８】
ステップ１２０１以降の処理では、最長テスト経路長がステップ１２０１で指定された基準値４よりも短い制御点および分岐の枝は、処理対象から除外される。具体的には、ステップ１１では、７つの制御点のうち、制御点ＰＩ２、ＰＩ４のみがテスト対象として選択され、７本の分岐の枝のうち、分岐の枝ｓ５ｂ、ｓ１０ｂのみがテスト対象として選択される。また、ステップ１０３では、分岐の枝ｓ５ａ、ｓ５ｂ、ｓ５ｃのうち、分岐の枝ｓ５ｂのみが到達候補信号線に設定され、分岐の枝ｓ１０ａ、ｓ１０ｂのうち、分岐の枝ｓ１０ａのみが到達候補信号線に設定され、分岐の枝ｓ６ａ、ｓ６ｂは、どちらも到達候補信号線に設定されなくなる。
【０２３９】
この例では、第１の生成方法で選択された分岐の枝ｓ１０ａは、第１１の生成方法でも到達候補信号線として扱われる。したがって、この例では、第１１の生成方法によれば、第１の生成方法と同じテストパターンが生成される。すなわち、第１１の生成方法によれば、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。ただし、一般的には、第１１の生成方法では、所定の基準を満たさない制御点および信号線は処理対象から除外されるので、第１の生成方法とは異なるテストパターンが生成される。
【０２４０】
なお、装置は、ステップ１２０２を実行する前に、ステップ２０１（図７）を実行してもよい。例えば、図８に示すテスト対象回路に対してステップ２０１を実行すると、図９に示すエッジグラフが得られる。最長テスト経路長が基準値４より短い制御点および信号線を処理対象から除外することにより、図９に示すエッジグラフをさらに簡略化することができる（図２４を参照）。この場合、図２４に実線で示したグループに対してのみステップ１２０２を実行することにより、処理を高速化することができる。
【０２４１】
以上に示すように、第１２の生成方法によれば、所定の基準を満たさない制御点および信号線を除外して処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【０２４２】
＜第１３の実施形態＞
図２５は、第１３の生成方法を示すフロー図である。第１３の生成方法は、第１の生成方法に対して、ステップ１３０１、１３０２を追加したものである。第１３の生成方法は、指定された信号線を除いて処理することを特徴とする。
【０２４３】
第１３の生成方法で初出のステップは、以下のとおりである。
（ステップ１３０１）装置には、対象外信号線情報として、テスト対象回路に含まれる制御点、信号線および観測点を指定する情報が入力される。なお、この対象外信号線情報は、ステップ１０で回路情報とともに入力されることとしてもよい。
（ステップ１３０２）装置は、ステップ１３０１で入力された対象外信号線情報に基づき、処理対象から除外する信号線を決定する。
【０２４４】
第１３の生成方法では、対象外信号線情報に制御点が含まれている場合には、当該制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線が、処理対象から除外される。対象外信号線情報に信号線が含まれている場合には、当該信号線から任意の観測点に至る経路を構成する信号線が、処理対象から除外される。対象外信号線情報に観測点が含まれている場合には、当該観測点に到達する経路のみに含まれる信号線が、処理対象から除外される。
【０２４５】
図５に示すテスト対象回路に対して第１３の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ９の立上り遷移をテスト対象とし、｛ＰＩ１、ＰＩ２、ＰＩ３、ＰＩ４、ＰＩ５、ＰＩ６、ＰＩ７｝を｛Ｐ｝と記載する。
（ステップ１３０１）装置には、観測点ＰＯ２を指定した対象外信号線情報が入力される。
（ステップ１３０２）図５に示すテスト対象回路には、観測点ＰＯ２に到達するのみに経路を構成する信号線として、信号線ｓ５ｃ、ｓ１０ｂ、ｓ１２、ｓ１３、ｓ１４、ｓ１５、ｓ１６が含まれている。装置は、これらの信号線を処理対象から除外する。したがって、後にステップ１０３が実行されるときでも、信号線ｓ１０ｂは伝達候補信号線に設定されない。
【０２４６】
この例では、第１の生成方法で選択された分岐の枝ｓ１０ａは、第１１の生成方法でも到達候補信号線として扱われる。したがって、この例では、第１１の生成方法によれば、第１の生成方法と同じテストパターンが生成される。すなわち、第１１の生成方法によれば、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ｝が生成され、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝が生成される。ただし、一般的には、第１１の生成方法では、所定の基準を満たさない制御点および信号線は処理対象から除外されるので、第１の生成方法とは異なるテストパターンが生成される。
【０２４７】
以上に示すように、第１３の生成方法によれば、指定された信号線を除いて処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。例えば、テスト対象回路に含まれるマルチサイクルパスやフォールスパスを指定すれば、効果的である。
【０２４８】
なお、以上の説明では、装置には対象外信号線情報が外部から入力されることとしたが、これに代えて、装置自身が、テスト対象回路の静的タイミング解析や遅延値の計算結果に基づき、対象外信号線情報を自動的に求めてもよい。
【０２４９】
なお、第１〜第１３の実施形態では、装置は、外部入力端子とスキャンＦＦとの間にある組合せ回路、スキャンＦＦ間にある組合せ回路、および、スキャンＦＦと外部出力端子との間にある組合せ回路に対して、テストパターンを生成することとした。これに代えて、装置は、テスト対象回路の１テスト周期前の状態を考慮して、検査系列Ｔ１とＴ２を同時に生成してもよい。この場合、装置は、図４に示すステップ１３〜１６を検査系列生成処理に含めて実行すればよい。
【０２５０】
本発明の第１４〜第１６の実施形態におけるテストパターン生成方法においては、信号が入力される制御点からテスト対象信号線へと信号遷移を伝播することができる１以上の経路の中で、テスト対象信号線から制御点までの経路長がより長い経路が選択される。以下、第１４〜第１６の実施形態に係るテストパターン生成方法を、それぞれ、第１４〜第１６の生成方法という。
【０２５１】
図２６は、本発明の第１４〜第１９の実施形態に係るテストパターン生成方法で用いられる値を示す図である。図２６に示す論理値１Ｕは、信号線の値が検査系列Ｔ１では１であり、検査系列Ｔ２ではＸ（０でも１でもよい）であることを示す。論理値０Ｕは、信号線の値が検査系列Ｔ１では０であり、検査系列Ｔ２ではＸであることを示す。論理値１０は、信号線の値が検査系列Ｔ１では１であり、検査系列Ｔ２では０であることを示す。論理値０１は、信号線の値が検査系列Ｔ１では０であり、検査系列Ｔ２では１であることを示す。
【０２５２】
ここで、予め設定された信号遷移をゲートの出力に伝搬させるために、当該ゲートの入力に設定すべき条件について説明する。例えば、ＡＮＤゲートにおいて、出力ｙに立上がり遷移ＮＤを伝搬させるための条件は、入力ａに立上がり遷移ＮＤを与え、入力ｂにはＵ１を与えることである（図２７（ａ）を参照）。また、ＯＲゲートにおいて、出力ｙに立上がり立下がり遷移Ｄを伝搬させるための条件は、入力ａに立下がり遷移Ｄを与え、、入力ｂにＵ０を与えることである。
【０２５３】
図２７（ｃ）に、ＡＮＤゲートおよびＮＡＮＤゲートの活性化条件を示す。より詳細には、ＡＮＤゲート及びＮＡＮＤゲートにおいて、出力に設定される信号遷移と、信号の伝播経路となる入力に与えるべき値との組み合わせに対し、伝搬経路以外の入力に与えるべき値が記載されている。また、図２７（ｄ）には、ＯＲゲート及びＮＯＲゲートにおいて、出力に設定される信号遷移と、信号の伝播経路となる入力に与えるべき値との組み合わせに対し、伝搬経路以外の入力に与えるべき値が記載されている。また、図２７（ｃ）及び図２７（ｄ）の代わりに、図２８（ａ）及び図２８（ｂ）に示される活性化条件が用いられてもよい。
【０２５４】
＜第１４の実施形態＞
図２９は、本発明の第１４の生成方法を示すフロー図である。第１４の生成方法では、以下の処理が実行される。
（ステップ２１００）装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子（ゲート）および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
（ステップ２１０１）装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ２００１では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
（ステップ２１０２）装置は、ステップ２１０１でテスト対象の信号線および信号遷移を選択した場合にはステップ２１０３へ進み、それ以外の場合にはステップ２１１７へ進む。
【０２５５】
（ステップ２１０３）装置は、ステップ２１０１で選択したテスト対象信号線に、ステップ２１０１で選択した信号遷移に対応した故障値（立上り遷移のときはＮＤ、立下り遷移のときはＤ）を設定する。
（ステップ２４００）装置は、後述する検査系列生成処理を行うことにより、検査系列＜Ｔ１，Ｔ２＞を生成する。
（ステップ２１１５）装置は、検査系列生成処理において、検査系列＜Ｔ１，Ｔ２＞の生成に成功した場合にはステップ２１１６へ進み、それ以外の場合はステップ２１０１へ進む。
【０２５６】
（ステップ２１１６）装置は、ステップ２４００で生成した検査系列＜Ｔ１，Ｔ２＞を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列＜Ｔ１，Ｔ２＞を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ２１０１へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ２１０１〜２１１６が実行される。
（ステップ２１１７）装置は、ステップ２１１６で記録した検査系列＜Ｔ１，Ｔ２＞をシリアルパターンに変換し、処理を終了する。
【０２５７】
図３０は、図２９に示される検査系列生成処理の詳細を示すフロー図である。ステップ２４００では、以下の処理が実行される。以下、最も新しく信号遷移が決定された信号線を「制御信号線」といい、制御信号線の入力側に接続され、次に信号遷移が決定される可能性がある信号線を「制御候補信号線」という。
（ステップ２１０４）装置は、テスト対象信号線を制御信号線に設定する。
（ステップ２１０５）装置は、制御信号線に信号を伝搬することができる信号線、すなわち、制御信号線の入力端に接続されているゲートの入力信号線を制御候補信号線に設定する。
【０２５８】
（ステップ２１０６）装置は、制御候補信号線が１本以下（すなわち、０本または１本）である場合にはステップ２１０７へ進み、それ以外の場合にはステップ２１１１へ進む。
（ステップ２１０７）装置は、制御候補信号線が制御可能である場合には、ステップ２１１１に進み、それ以外の場合には、ステップ２１０８へ進む。
（ステップ２１０８）装置は、制御候補信号線から制御信号線へと信号を遷移可能であるか否かを判定し、遷移可能である場合にはステップ２１０８へ進み、それ以外に場合には、パタン生成失敗と判定し処理を終了する。
【０２５９】
（ステップ２１０９）装置は、制御候補信号線を新たな制御信号線に設定し、ステップ２１１０に進む。
（ステップ２０１０）装置は、検査系列＜Ｔ１、Ｔ２＞を更新し、ステップ２１０５へ進む。
【０２６０】
（ステップ２１１１）装置がステップ２１０７からステップ２１１０に到達するのは、制御候補信号線が可制御の制御点に接続されている場合である。装置は、制御候補信号線が接続される制御点に入力すべき検査系列＜Ｔ１，Ｔ２＞を更新し、ステップ２１０１（図２９）へ進む。
【０２６１】
（ステップ２１１２）装置がステップ２１０６からこのステップに到達するのは、制御候補信号線（ゲートの入力）が２本以上ある場合に限られる。装置は、各制御候補信号線について、制御候補信号線から１以上の制御点までの経路の長さ（制御距離）を求める。更に、装置は、各制御候補信号線について、求められた１以上の制御距離の最大値を各制御候補信号線についての最長制御距離として求める。制御距離は、上述した観測距離と同様に、遅延値テーブル（図２）やビアテーブル（図３）あるいは制御候補信号線と制御点との間に接続されるゲート数等のいずれか１つまたはこれらの組み合わせに従って算出される。そして、装置は、制御候補信号線の中で、最長制御距離が最も長い制御候補信号線を選択する。
【０２６２】
（ステップ２１１３）装置は、ステップ２１１２において選択された制御候補信号線から制御信号線へと信号遷移を伝搬させることができると判定した場合には、ステップ２１１４へ進み、それ以外の場合には、ステップ２１１７へ進む。
（ステップ２１１４）装置は、ステップ２１１２において制御信号線に対して信号を遷移可能と判定した制御候補信号線が可制御であるか否かを判定する。装置は、信号遷移可能な制御候補信号線が可制御である場合には、ステップ２１１１へ進み、それ以外の場合には、ステップ２１１５へ進む。
（ステップ２１１５）装置は、選択された制御候補信号線を新たな制御信号線に設定し、ステップ２１１６へ進む。
（ステップ２１１６）装置は、検査系列＜Ｔ１、Ｔ２＞を更新し、ステップ２１０５へ進む。
（ステップ２１１７）装置は、制御信号線についての制御候補信号線の中から、選択された制御候補信号線を除外し、ステップ２１０６へ進む。ステップ２１１７の処理は、制御信号線へと信号遷移を伝搬することができない信号線が再度選択されることを避けるためのものである。
【０２６３】
図３１に示すテスト対象回路に対して第１４の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ３の遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。また、ステップ２１１１において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【０２６４】
（ステップ２１０３）装置は、テスト対象信号線ｓ３に、信号遷移ＮＤを設定する。
（ステップ２１０４）装置は、テスト対象信号線ｓ３を制御信号線に設定する。
（ステップ２１０５）装置は、信号線ｓ２及びｓ６ａを制御候補信号線に設定する。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０２６５】
（ステップ２１１２）装置は、制御候補信号線ｓ２及び信号線ｓ６ａの各々について、最長制御距離を計算する。具体的には、図３１に示されるテスト対象回路において、信号線ｓ２は、制御点ＰＩ１及びＰＩ２に接続されている。制御候補信号線ｓ２から制御点ＰＩ１までの経路と、信号線ｓ２から制御点ＰＩ２までの経路とは、いずれも１つのゲートｇ１を含む。したがって、制御候補信号線から制御点までの距離をゲート数によって評価すると、制御候補信号線ｓ２から制御点までの最長制御距離は、１である。一方、制御候補信号線ｓ６ａは、制御点ＰＩ３に接続されている。制御候補信号線ｓ６ａから制御点ＰＩ３までの経路は、ゲートを含まないので、制御候補信号線ｓ６ａの最長制御距離は、０である。装置は、制御候補信号線ｓ２及びｓ６ａの各々について求められた最長制御距離の長さが最も長い制御候補信号線ｓ２を選択する。
【０２６６】
（ステップ２１１３）装置は、活性化、含意操作及び正当化を行い、選択された制御候補信号線ｓ２から制御信号線ｓ３へと信号遷移を伝搬させることができるか否かを判定する。装置は、図２７または図２８に示される活性化条件等を用いて、ステップ２１１２の判定を実行する。例えば、制御信号線ｓ３（出力）に立上がり遷移ＮＤが設定されている場合、図２８（ｂ）に従って、選択された制御候補信号線ｓ２（伝搬経路となる入力）に立上がり遷移ＮＤを与え、信号線ｓ６ａ（伝搬経路以外の入力）に、Ｓ０を与える必要がある。この場合、ステップ２１１２では矛盾が発生しないので、装置は、ステップ２１１３へと進む。
（ステップ２１１４）信号線ｓ２が直接外部端子に接続されていない（すなわち、可制御ではない）ので、装置は、ステップ２１１５へ進む。
【０２６７】
（ステップ２１１５）装置は、選択された制御候補信号線ｓ２を新たな制御信号線に設定し、ステップ２１１６へ進む。
（ステップ２１１６）装置は、検査系列Ｔ１及びＴ２を｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新し、ステップ２１０５へ進む。
（ステップ２１０５）装置は、制御信号線ｓ２の入力側に接続される信号線ｓ１及びｓ５ａを制御候補信号線に設定し、ステップ２１０６へ進む。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０２６８】
（ステップ２１１２）装置は、制御候補信号線ｓ１及びｓ５ａの各々について、最長経路長を計算する。制御候補信号線ｓ１及びｓ５ａの最長経路長は、いずれも０であるので、装置は、制御候補信号線ｓ１を選択し、ステップ２１１３へ進む。
（ステップ２１１３）制御信号線ｓ２には、信号遷移ＮＤが設定されているので、装置は、例えば図２８（ａ）に従って、信号線ｓ１に信号値ＮＤを設定し、信号線ｓ５ａに信号値Ｕ１を設定する。ステップ２１１２では矛盾が発生しないので、装置は２１１４へ進む。
【０２６９】
（ステップ２１１４）制御候補信号線ｓ１が可制御であるので、装置は、ステップ２１１１へ進む。
（ステップ２１１１）装置は、検査系列Ｔ１を、｛Ｐ｝＝｛０，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新し、検査系列Ｔ２は、｛Ｐ｝＝｛１，１，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新する。
【０２７０】
以上の処理により、装置は、検査系列Ｔ１として｛Ｐ｝＝｛０，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝を決定し、検査系列Ｔ２として｛Ｐ｝＝｛１，１，０，Ｘ，Ｘ，Ｘ，Ｘ｝を決定する。
【０２７１】
図３１に示されるテスト対象回路には、テスト対象信号線ｓ３に信号遷移を伝搬させる経路として、３つの経路、すなわち、信号線ｓ３から信号線ｓ２を経由してから制御点ＰＩ１に至る経路と、信号線ｓ３から信号線ｓ２を経由して制御点ＰＩ２に至る経路と、信号線ｓ３から信号線ｓ６ａを経由して制御点ＰＩ３に至る経路とが存在する。第１４の生成方法によれば、制御点に入力された信号値をテスト対象信号線に伝搬する経路が複数ある場合、信号遷移を伝搬可能な経路の中で、より長い経路（信号線ｓ３から信号線ｓ２を経由してから制御点ＰＩ１に至る経路）が優先的に選択される。より長い経路を用いて信号値を伝搬させることによって、テストパターンの品質を向上することができる。
【０２７２】
＜第１５の実施形態＞
図３２は、本発明の第１７の実施形態に係るテストパターン生成方法を示すフロー図である。第１７の生成方法は、第１５の生成方法に対して、ステップ２２０１、２２０２、２２０３及び２２０４を追加したものである。第１５の生成方法は、ある制御信号線へと信号を伝搬する全ての制御候補信号線について正当化に失敗した場合、過去に信号線の選択が行われた信号線までバックトラックするステップを備えることを特徴とする。
【０２７３】
第１７の生成方法で初出のステップは、以下の通りである。
（ステップ２２０１）装置は、ステップ２１０８において、ある制御信号線から信号遷移が可能でないと判定した場合、当該制御信号線がテスト対象信号線であるか否かを判定する。制御信号線がテスト対象信号線である場合には、装置は、処理が失敗であると判定してステップ２１１５（図２９）へ進み、それ以外の場合には、ステップ２２０２へ進む。ステップ２２０１において、制御信号線がテスト対象信号線であるか否かを判定するのは、後述のステップ２２０３において実行されるバックトラックの結果、テスト対象信号線が制御信号線に再設定される可能性があるからである。
【０２７４】
（ステップ２２０２）装置は、制御信号線を制御不能な信号線（以下、「非制御信号線」という）に設定し、ステップ２２０３へ進む。
【０２７５】
（ステップ２２０３）装置は、ステップ２２０２で設定した非制御信号線の出力側に接続されるゲートの出力信号線を新たな制御信号線に設定する。すなわち、装置は、テスト対象回路の出力側へとゲート１段分だけバックトラックする。なお、非制御信号線は、新たに設定された制御信号線（すなわち、バックトラック後の制御信号線）に対する制御候補信号線である。
【０２７６】
（ステップ２２０４）装置は、ステップ２２０２で設定された非制御候補信号線を、制御候補信号線から除外する。
【０２７７】
ここで、図３３に示されるテスト対象回路に対して第１７の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ４の立上がり遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。また、ステップ２１１２において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【０２７８】
（ステップ２１０３）装置は、テスト対象信号線ｓ４に、信号遷移ＮＤを設定する。
（ステップ２１０４）装置は、テスト対象信号線ｓ４を制御信号線に設定する。
（ステップ２１０５）装置は、信号線ｓ３およびｓ８を制御候補信号線に設定する。
（ステップ２２０４）非制御信号線は存在しないので、装置は、ステップ２１０６へ進む。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０２７９】
（ステップ２１１２）装置は、信号線ｓ３及び信号線ｓ８の各々について、最長制御距離を計算する。ゲート数で制御距離を評価すると、信号線ｓ３の最長制御距離は、２であり、信号線ｓ８の最長制御距離は、３である。装置は、制御候補信号線ｓ３及びｓ８の各々について求められた最長制御距離の長さの最大値に基づいて、制御候補信号線ｓ８を選択する。
【０２８０】
（ステップ２１１３）装置は、制御信号線ｓ４に信号遷移NＤが設定されているので、装置は、信号線ｓ８にＤを設定し、信号線ｓ３にU０を設定する。このとき、制御候補信号線ｓ８から制御信号線ｓ４へと信号遷移を伝搬させることが可能であるので、装置は、ステップ２１１４へ進む。
【０２８１】
（ステップ２１１４）装置は、選択された制御候補信号線ｓ８が可制御ではないので、ステップ２１１５へ進む。
（ステップ２１１５）装置は、選択された制御候補信号線ｓ８を新たな制御信号線に設定し、ステップ２１１６へ進む。
（ステップ２１１６）この段階では、検査系列Ｔ１及びＴ２の値は特定されない（｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝）ので、装置は、ステップ２１０５へ進む。
【０２８２】
（ステップ２１０５）装置は、制御信号線ｓ８の入力側に接続される信号線ｓ７及びｓ１１を制御候補信号線に設定する。
（ステップ２２０４）非制御信号線は存在しないので、装置は、ステップ２１０６へ進む。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０２８３】
（ステップ２１１２）装置は、制御候補信号線ｓ７及びｓ１１の各々について、最長経路長を計算する。制御候補信号線ｓ７の最長経路長は２、ｓ１１の最長経路長は、０であるので、装置は、制御候補信号線ｓ７を選択し、ステップ２１１３へ進む。
【０２８４】
（ステップ２１１３）装置は、制御候補信号線ｓ７から制御信号線ｓ８へと信号遷移を伝搬させるために、活性化、含意操作及び正当化を行う。装置は、信号線ｓ８にＤが設定されているので、信号線ｓ７にＮＤを設定し、信号線ｓ１１にＳ０を設定する。このとき制御候補信号線ｓ７からｓ８へと信号を伝播することが可能であるので、装置はステップ２１１４へ進む。
【０２８５】
（ステップ２１１４）選択された制御候補信号線は、可制御ではないので、装置は、ステップ２１１５へ進む。
（ステップ２１１５）装置は、選択された制御候補信号線ｓ７を新たな制御信号線に設定し、ステップ２１１６へ進む。
（ステップ２１１６）装置は、検査系列Ｔ１及びＴ２を｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，０，Ｘ，Ｘ｝に更新し、ステップ２１０５へ進む。
【０２８６】
（ステップ２１０５）装置は、制御信号線ｓ７の入力側信号線ｓ６ｂ及びｓ１０ａを制御候補信号線に設定する。
（ステップ２２０４）非制御信号線は存在しないので、装置は、ステップ２１０６へ進む。
（ステップ２１０６）制御候補信号線は２本であるので、装置はステップ２１１２へ進む。
【０２８７】
（ステップ２１１２）装置は、信号線ｓ６ｂ及びｓ１０ａの各々について、最長制御距離を計算する。ゲート数で制御距離を評価すると、信号線ｓ６ｂの最長制御距離は０であり、信号線ｓ１０ａの最長制御距離は１である。装置は、ｓ６ｂおよびｓ１０ａの各々について求められた最長制御距離の長さの最大値に基づいて、制御候補信号線ｓ１０ａを選択する。
【０２８８】
（ステップ２１１３）装置は、制御信号線ｓ７にＮＤが設定されているので、信号線ｓ１０ａにＮＤを設定し、信号線ｓ６ｂにＵ１を設定し、活性化、正当化および含意操作を行う。しかし、このステップが実施される前に信号線ｓ３にＵ０に設定されているため、ｓ６ｂにＵ１を設定すると矛盾が生じる。そこで、装置は、信号線ｓ１０ａから信号線ｓ８には信号遷移を伝播できないと判定し、ステップ２１１７へ進む。
【０２８９】
（ステップ２１１７）装置は、信号線ｓ８に対する制御候補信号線からｓ１０ａを除外し、ステップ２１０６へ進む。
（ステップ２１０６）信号線ｓ１０ａは、ステップ２１１４において、信号線ｓ８に対する制御候補信号線から除外されている。したがって、信号線ｓ８に対する制御候補信号線は、信号線ｓ６ｂのみである。制御候補信号線の数が１本であるので、装置は、ステップ２１０７へ進む。
【０２９０】
（ステップ２１０７）制御候補信号線ｓ６ｂは可制御ではないため、装置は、ステップ２１０８に進む。
（ステップ２１０８）装置は、制御信号線ｓ７にＮＤが設定されているので信号線ｓ６ｂにＮＤを設定し、信号線ｓ１０ａにＵ１を設定し、活性化、正当化および含意操作を行う。しかし、このステップが実行される前に信号線ｓ３にＵ０が設定されているため、信号線ｓ６ｂにＮＤを設定すると矛盾が生じる。そこで、装置は、信号線ｓ１０ａから信号線ｓ８に信号遷移を伝播できないと判定し、ステップ２２０１へ進む。
【０２９１】
（ステップ２２０１）テスト対象信号線は、信号線ｓ４であり、この時点での制御信号線はｓ７である。したがって、装置は、ステップ２２０２へ進む。
（ステップ２２０２）装置は、制御信号線ｓ７を非制御信号線に設定し、ステップ２２０３へ進む。
（ステップ２２０３）装置は、非制御信号線に設定した信号線ｓ７の到達ゲートの出力信号線ｓ８を制御信号線に再度設定し、ステップ２１０５へ進む。
【０２９２】
（ステップ２１０５）装置は、制御信号線ｓ８の入力側の信号線ｓ７、ｓ１１を制御候補信号線に設定しステップ２２０３へ進む。
（ステップ２２０４）装置は、ステップ２２０２において非制御信号線に設定した信号線ｓ７を制御候補信号線から除外し、ステップ２１０６へ進む。
【０２９３】
（ステップ２１０６）信号線ｓ７は、制御信号線ｓ８に対する制御候補信号線から除外されているので、制御信号線ｓ８に対する制御候補信号線は、信号線ｓ１１のみである。制御候補信号線が１本であるので、装置は、ステップ２１０７へ進む。
（ステップ２１０７）制御候補信号線ｓ１１は、可制御であるので、装置は、ステップ２１１１へ進む。
（ステップ２１１１）装置は、検査系列Ｔ１を｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ，０，Ｘ，Ｘ｝、検査系列Ｔ２を｛Ｐ｝＝｛Ｘ，０，Ｘ，Ｘ，１，Ｘ，Ｘ｝に更新し、処理を終了する。
【０２９４】
上記の第１５の生成方法によれば、活性化および正当化に失敗した場合にはバックトラックするので、制御点からテスト対象信号線へと信号遷移を伝搬することができるテストパターンをより確実に生成することができる。
【０２９５】
＜第１６の実施形態＞
図３４は、本発明の第１６の実施形態に係るテストパターン生成方法を示すフロー図である。第１６の生成方法は、第１４の生成方法に対して、ステップ２３０１を追加したものである。
【０２９６】
第１６の生成方法で初出のステップは、以下の通りである。
（ステップ２３０１）装置は、最長制御距離が最大でないと判定した制御候補信号線（以下、「非選択制御候補信号線」という）に固定の信号値を設定する。装置が、非選択制御候補信号線に固定値を設定するのは、信号遷移を伝搬する経路に対して、伝搬経路以外の経路において生じた信号遅延が影響することを、可能な限り抑制するためである。なお、ステップ２３０１において非選択制御候補信号線に固定値を設定することができない場合には、信号遷移を設定してもよい。
【０２９７】
ここで、図３１に示すテスト対象回路に対して第１６の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ３の立上がり遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。また、ステップ２１１１において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【０２９８】
（ステップ２１０３）装置は、テスト対象信号線ｓ３に、信号遷移ＮＤを設定する。
（ステップ２１０４）装置は、テスト対象信号線ｓ３を制御信号線に設定する。
（ステップ２１０５）装置は、信号線ｓ２及びｓ６ａを制御候補信号線に設定する。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０２９９】
（ステップ２１１２）装置は、制御候補信号線ｓ２及び信号線ｓ６ａの最長制御距離を計算する。ゲート段数で制御距離を評価すると、信号線ｓ２の最長制御距離は１、信号線ｓ６ａの最長観測距離は、０である。そこで、装置は、最長制御距離が最も長い制御候補信号線ｓ２を選択し、ステップ２１１３へ進む。
【０３００】
（ステップ２１１３）制御信号線ｓ３にＮＤが設定されているので、装置は、選択された制御候補信号線ｓ２にＮＤを設定し、信号線ｓ６ａにＳ０を設定し、活性化、正当化、含意操作を行う。このとき制御候補信号線ｓ２から制御信号線ｓ３に信号を伝播することが可能であるため、装置は、ステップ２１１４へ進む。
【０３０１】
（ステップ２１１４）選択された制御候補信号線ｓ２は、可制御ではないので、装置は、ステップ２３０１へ進む。
（ステップ２３０１）装置は、未選択制御候補信号線であるｓ６ａに制御候補信号線ｓ２から制御信号線ｓ３へ伝播可能な固定値である０を与え、ステップ２１１５へ進む。
【０３０２】
（ステップ２１１５）装置は、選択された制御候補信号線ｓ２を新たな制御信号線に設定する。
（ステップ２１１６）装置は、検査系列Ｔ１を、｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新し、検査系列Ｔ２を、｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新し、ステップ２１０５へ進む。
【０３０３】
（ステップ２１０５）装置は、制御信号線ｓ２の入力側に接続される信号線ｓ１及びｓ５ａを制御候補信号線に設定する。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０３０４】
（ステップ２１１２）装置は、制御候補信号線ｓ１及びｓ５ａの各々について、最長経路長を計算する。制御候補信号線ｓ１及びｓ５ａの最長経路長は、いずれも０であるので、装置は、制御候補信号線ｓ１を選択し、ステップ２１１３へ進む。
（ステップ２１１３）選択された制御信号線ｓ２には、ＮＤが設定されているので、装置は、制御候補信号線ｓ１にＮＤを設定し、制御候補信号線ｓ５ａにＵ１を設定し、活性化、正当化、含意操作を行う。このとき制御候補信号線ｓ１から制御信号線ｓ２に信号の伝達が可能であるため、ステップ２３０１へ進む。
【０３０５】
（ステップ２１１４）選択された制御候補信号線ｓ１は、可制御であるので、装置は、ステップ２１１１へ進む。
（ステップ２１１１）装置は、検査系列Ｔ１として｛Ｐ｝＝｛０，１，０，Ｘ，Ｘ，Ｘ，Ｘ｝を決定し、検査系列Ｔ２として｛Ｐ｝＝｛１，１，０，Ｘ，Ｘ，Ｘ，Ｘ｝を決定する。
【０３０６】
尚、この例では、検査系列Ｔ１において制御点ＰＩ２に与えられる値は、検査系列Ｔ２において制御点ＰＩ２に与えられる値が１である限り、検査系列Ｔ１では、Ｘまたは１のいずれの値であってもよい。しかしながら、検査系列Ｔ１及びＴ２の両方において、制御点ＰＩ２に固定値０が設定された場合、未選択制御候補信号線ｓ５ａ上に信号遅延が生じることはない。したがって、制御信号線ｓ２に対して、信号の伝搬経路である制御候補信号線ｓ１以外の経路において生じる信号遅延の影響を取り除くことができる。
【０３０７】
このように、第１６の生成方法によれば、制御点からテスト対象信号線へと信号伝搬可能な最長の経路以外の経路には、固定値が設定されるので、テスト対象外経路の信号遅延の影響が低減し、テストパターンの信頼性が向上する。
【０３０８】
以下、本発明の第１７〜第１９の各実施形態について説明する。第１７〜第１９の実施形態に係るテストパターン生成方法においては、制御点からテスト対象信号線を経由して観測点まで至る経路の中で、より長い経路が優先的に選択される。以下、第１７〜第１９の実施形態に係るテストパターン生成方法を、それぞれ、第１７〜第１９の生成方法という。
【０３０９】
＜第１７の実施形態＞
図３５は、本発明の第１７の生成方法を示すフロー図である。第１７の生成方法においては、まず、第１の決定処理において、テスト対象信号線から観測点へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、検査系列＜Ｔ１，Ｔ２＞が生成される。次に、第２の決定処理において、制御点からテスト対象信号線へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、生成された検査系列＜Ｔ１，Ｔ２＞が更新される。以下に、第１７の生成方法の処理について説明する。
【０３１０】
（ステップ２１００）装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子（ゲート）および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
（ステップ２１０１）装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ２００１では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
【０３１１】
（ステップ２１０２）装置は、ステップ２１０１でテスト対象の信号線および信号遷移を選択した場合にはステップ２１０３へ進み、それ以外の場合にはステップ２１１７へ進む。
（ステップ２１０３）装置は、ステップ２１０１で選択したテスト対象信号線に、ステップ２１０１で選択した信号遷移に対応した故障値（立上り遷移のときはＮＤ、立下り遷移のときはＤ）を設定する。
【０３１２】
（ステップ２６０１）装置は、後述する第１の決定処理を行うことにより、検査系列＜Ｔ１，Ｔ２＞を決定する。
（ステップ２６０２）装置は、第１の決定処理に成功した場合には、ステップ２６０２へ進み、それ以外の場合は、ステップ２１０１へ進む。
（ステップ２６０３）装置は、後述する第２の決定処理を行うことにより、ステップ２６０１において決定された検査系列＜Ｔ１，Ｔ２＞を更新しながら、検査系列＜Ｔ１，Ｔ２＞を決定する。
（ステップ２６０４）装置は、第２の決定処理に成功した場合には、ステップ２１１６へ進み、それ以外の場合は、ステップ２１０１へ進む。
【０３１３】
（ステップ２１１６）装置は、ステップ２６０３で生成した検査系列＜Ｔ１，Ｔ２＞を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列＜Ｔ１，Ｔ２＞を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ２１０１へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ２１０１〜２１１６が実行される。
（ステップ２１１７）装置は、ステップ２１１６で記録した検査系列＜Ｔ１，Ｔ２＞をシリアルパターンに変換し、処理を終了する。
【０３１４】
図３６は、図３５に示される第１の決定処理の詳細を示すフロー図である。
（ステップ２５０１）装置は、テスト対象信号線を到達信号線に設定する。
（ステップ２５０２）装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。なお、正当化によって制御点に与えるべき値が決定された場合には、検査系列Ｔ２が更新され、場合によっては検査系列Ｔ１も更新される。以下に示すすべての正当化処理においても、これと同じである。
【０３１５】
（ステップ２５０３）装置は、ステップ２５０２で矛盾が発生した場合にはステップ２１０１へ進み、それ以外の場合にはステップ２５０４へ進む。
（ステップ２５０４）装置は、到達信号線の出力側のゲートの信号線を到達候補信号線に設定する。
（ステップ２５０５）装置は、到達候補信号線が１本以下（すなわち、０本または１本）である場合にはステップ２５０６へ進み、それ以外の場合にはステップ２５０８へ進む。
【０３１６】
（ステップ２５０６）装置は、到達候補信号線が観測可能であるか、または、０本である（すなわち、到達候補信号線が観測点に接続されているか、または、到達候補信号線がない）場合には、ステップ２５１３へ進み、それ以外の場合にはステップ２５０７へ進む。
（ステップ２５０７）装置がこのステップに到達するのは、到達候補信号線が１本である場合に限られる。装置は、唯一の到達候補信号線を新たな到達信号線に設定する。
【０３１７】
（ステップ２５０８）装置は、各分岐の枝について、各観測点までの経路の長さ（観測距離）を求め、観測距離の最大値（以下、最長観測距離という）を求める。観測距離は、上述したように、遅延値テーブル（図２）やビアテーブル（図３）など用いて算出される。装置は、到達候補信号線の中で最長観測距離が最も長い信号線を選択する。
【０３１８】
（ステップ２５０９）装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。
（ステップ２５１０）装置は、ステップ２５０９で矛盾が発生した場合にはステップ２５１２へ進み、それ以外の場合にはステップ２５１１へ進む。
【０３１９】
（ステップ２５１１）装置は、到達候補信号線を新たな到達信号線に設定し、ステップ２５０２へ進む。
（ステップ２５１２）装置は、到達信号線についての到達候補信号線の中から、ステップ２５０９において矛盾を生じさせた到達候補信号線を除外し、ステップ２５０５へ進む。
（ステップ２５１３）装置は、検査系列＜Ｔ１，Ｔ２＞を更新し、ステップ２６０１へ進む。
【０３２０】
なお、第１の決定処理には、上記の第１〜第１３の生成方法における検査系列生成方法のいずれかを適用すればよい。また、第２の決定処理には、上記の第１４〜１６の生成方法における検査系列生成方法のいずれかを適用すればよいので、以下の説明を省略する。
【０３２１】
ここで、図３７に示すテスト対象回路に対して第１７の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ１０の立上がり遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。
【０３２２】
（ステップ２１０３）装置は、テスト対象信号線ｓ１０にＮＤを設定する。
（ステップ２５０１）装置は、テスト対象信号線ｓ１０を到達信号線に設定する。
（ステップ２５０２）到達信号線ｓ１０は、分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ２５０３へ進む。
（ステップ２５０３）ステップ２５０２では矛盾が発生していないので、装置は、ステップ２５０４へ進む。
（ステップ２５０４）到達信号線ｓ１０は、分岐の幹であるので、装置は、信号線ｓ１０ａ及びｓ１０ｂを到達候補信号線に設定する。
（ステップ２５０５）到達候補信号線が２本あるので、装置は、ステップ２５０８へ進む。
【０３２３】
（ステップ２５０８）装置は、到達候補信号線ｓ１０ａ及びｓ１０ｂのおのおのについて、最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１０ａの最長観測距離は３、信号線ｓ１０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線１０ａの最長観測距離は３、信号線ｓ１０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１０ａを選択する。
【０３２４】
（ステップ２５０９）装置は、到達候補信号線ｓ１０に設定された信号遷移をテスト対象回路の出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。これにより、装置は、信号線ｓ７にＮＤを設定し、信号線ｓ６ｂにＳ０を設定する。テスト系列Ｔ１は、｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新され、テスト系列Ｔ２は、｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，Ｘ，Ｘ，Ｘ｝に更新される。
【０３２５】
（ステップ２５１０）ステップ２５０９では矛盾が発生していないので、装置は、ステップ２５１２へ進む。
（ステップ２５１１）装置は、到達候補信号線ｓ７を新たな到達信号線に設定し、ステップ２５０２へ進む。
【０３２６】
装置は、同様に、図３６に示される処理を実行する。テスト対象信号線から観測点までの経路を選択しながらテストパターンを生成する方法は、第１〜第１４の実施形態において説明したので、以下の詳細な説明を省略する。結果として、装置は、テスト対象信号線ｓ１０から、信号線ｓ７、ｓ８ａ、ｓ４を順に経由して観測点ＰＯ１へと至る経路を選択しながら、テスト系列＜Ｔ１，Ｔ２＞を決定する。装置は、ステップ２５１３において、テスト系列Ｔ１を、｛Ｐ｝＝｛Ｘ，Ｘ，０，Ｘ，０，Ｘ，Ｘ｝に更新し、テスト系列Ｔ２を、｛Ｐ｝＝｛０，Ｘ，０，Ｘ，０，Ｘ，Ｘ｝に更新する。その後、装置は、ステップ２６０２へ進む。
（ステップ２６０２）第１の決定処理は成功したので、装置は、ステップ２６０３へ進む。
【０３２７】
以下、装置は、第２の決定処理として、第１４の実施形態に係る検査系列生成処理（図３０）を実行する場合を想定する。したがって、装置は、ステップ２１０４へ進む。
【０３２８】
（ステップ２１０４）装置は、テスト対象信号線ｓ１０を制御信号線に設定する。
（ステップ２１０５）装置は、信号線ｓ９及びｓ５ｂを制御候補信号線に設定する。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０３２９】
（ステップ２１１２）装置は、信号線ｓ９の及び信号線ｓ５ｂの各々について、制御距離を計算する。ゲート段数で経路長を評価すると、制御候補信号線ｓ９の最長制御距離は、０であり、制御候補信号線ｓ５ｂの最長制御距離は、１である。したがって、装置は、制御候補信号線ｓ５ｂを選択し、ステップ２１１３へ進む。
（ステップ２１１３）装置は、選択された制御候補信号線ｓ５ｂにＤを設定し、制御信号線ｓ１０へＮＤを伝搬させることができるか否かを判定する。正当化、活性化、含意操作の結果、信号遷移可能であるため、装置は、ステップ２１１４へ進む。
【０３３０】
（ステップ２１１４）制御候補信号線ｓ５ｂが可制御でないため、装置は、ステップ２１１５へ進む。
（ステップ２１１５）到達候補信号線ｓ５ｂを制御信号線に設定し、装置は、ステップ２１１６に進む。
（ステップ２１１６）装置は、検査系列Ｔ１を｛Ｐ｝＝｛Ｘ，Ｘ，０，１，０，Ｘ，Ｘ｝に更新し、検査系列Ｔ２を｛Ｐ｝＝｛０，Ｘ，０，１，０，Ｘ，Ｘ｝に更新し、ステップ２１０５へ進む。
【０３３１】
（ステップ２１０５〜２１１１）制御信号線ｓ５ｂの到達候補信号線はｓ５のみであるりｓ５は可制御である。そのためステップ２１０６、２１０７と進み、ステップ２１１１にて検査系列を更新する。
【０３３２】
以上の処理により、装置は、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，０，０，１，０，Ｘ，Ｘ｝を決定し、検査系列Ｔ２として｛Ｐ｝＝｛０，１，０，１，０，Ｘ，Ｘ｝を決定する。
【０３３３】
このように、まず、第１の決定処理において、テスト対象信号線から観測点までの経路長がより長い経路についてテストパターンが生成される。次に、第２の決定処理において、制御点から当該テスト対象信号線までの距離がより長い経路について、第１の決定処理で生成されたテストパターンを更新しながら、テストパターンが決定される。よって、第１７の生成方法によれば、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【０３３４】
また、最初にテスト対象信号線から観測点へと信号伝搬可能な経路が選択されるため、テスト対象信号線上の信号遷移を確実に観測可能な経路について効率的にテストパターンを生成することができる。
【０３３５】
＜第１８の実施形態＞
図３８は、本発明の第１８の生成方法を示すフロー図である。図３８に示されるように、第１８の生成方法は、第１７の生成方法において、ステップ２６０１と、ステップ２６０３との実行順序が入れ替えられたものであり、第１の決定処理（ステップ２６０１）は、第２の決定処理（ステップ２６０３）の後に実行される。より詳細には、まず、制御点からテスト対象信号線へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、生成された検査系列＜Ｔ１，Ｔ２＞が生成される。次に、テスト対象信号線から観測点へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、検査系列＜Ｔ１，Ｔ２＞が更新される。
【０３３６】
なお、第１の決定処理には、上記の第１〜第１３の生成方法における検査系列生成処理のいずれかを適用することができる。また、第１の決定処理として、第１７の生成方法と同様に、図３６に示される検査系列生成処理が適用されてもよい。一方、第２の決定処理には、上記の第１４〜第１６における検査系列生成処理のいずれかを適用することができる。
【０３３７】
ここで、図３７に示すテスト対象回路に対して第１８の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ１０の立上がり遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。
【０３３８】
また、以下の例においては、第１の決定処理として図３６に示される検査系列生成処理が適用され、かつ、第２の決定処理として図３０に示される検査系列生成処理が適用される場合を想定する。
【０３３９】
（ステップ２１０３）装置は、テスト対象信号線ｓ１０にＮＤを設定し、ステップ２１０４へ進む。
（ステップ２１０４）装置は、テスト対象信号線ｓ１０を制御信号線に設定する。
（ステップ２１０５）装置は、信号線ｓ９及びｓ５ｂを制御候補信号線に設定する。
（ステップ２１０６）制御候補信号線は、２本であるので、装置は、ステップ２１１２へ進む。
【０３４０】
（ステップ２１１２）装置は、信号線ｓ２の及び信号線ｓ６ａの各々について、制御距離を計算する。ゲート段数で経路長を評価すると、制御候補信号線ｓ９の最長制御距離は、０であり、制御候補信号線の最長制御距離は、１である。したがって、装置は、制御候補信号線ｓ５ｂを選択し、ステップ２１１３へ進む。
（ステップ２１１３）装置は、制御信号線ｓ１０に所定の信号遷移を発生させるために、活性化、含意操作及び正当化を行い、選択された制御候補信号線ｓ２から制御信号線ｓ３へと信号遷移を伝搬させることができるか否かを判定する。結果として、装置は、信号線ｓ５ｂにＤを設定し、信号線ｓ９にＳ１を設定し、ステップ２１１４へ進む。
【０３４１】
（ステップ２１１４）選択された制御候補信号線ｓ５ｂは、制御可能ではないので、装置は、ステップ２１１５へ進む。
（ステップ２１１５）装置は、選択された制御候補信号線ｓ５ｂを新たな制御信号線に設定し、ステップ２１１６へ進む。
（ステップ２１１６）装置は、検査系列Ｔ１を｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ｝を決定し、検査系列Ｔ２を｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新し、ステップ２１０５へ進む。
【０３４２】
（ステップ２１０５）装置は、制御信号線ｓ５ｂの入力側信号線ｓ５を制御候補信号線に設定する。
（ステップ２１０６〜２１１１）制御候補信号線は、１本であり、制御可能であるので、装置は、ステップ２１０７及び２１０９を経由して、ステップ２１１１へ進む。
【０３４３】
（ステップ２１１０）装置は、検査系列Ｔ１として｛Ｐ｝＝｛Ｘ，０，Ｘ，１，Ｘ，Ｘ，Ｘ｝を決定し、検査系列Ｔ２として｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝を決定する。その後、装置は、ステップ２６０２へ進む。
（ステップ２６０２）装置は、第２の決定処理に成功したので、ステップ２６０１に進む。
【０３４４】
（ステップ２５０１）装置は、テスト対象信号線ｓ１０を到達信号線に設定する。
（ステップ２５０２）到達信号線ｓ１０は、分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ２５０３へ進む。
（ステップ２５０３）ステップ２５０２では矛盾が発生していないので、装置は、ステップ２５０４へ進む。
（ステップ２５０４）到達信号線ｓ１０は、分岐の幹であるので、装置は、信号線ｓ１０ａ及びｓ１０ｂを到達候補信号線に設定する。
（ステップ２５０５）到達候補信号線が２本あるので、装置は、ステップ２５０８へ進む。
【０３４５】
（ステップ２５０８）装置は、到達候補信号線ｓ１０ａ及びｓ１０ｂの各々について、最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線ｓ１０ａの最長観測距離は３、信号線ｓ１０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線１０ａの最長観測距離は３、信号線ｓ１０ｂの最長観測距離は２である。そこで、装置は、最長観測距離が最も長い到達候補信号線ｓ１０ａを到達信号線として選択する。
【０３４６】
（ステップ２５０９）装置は、到達候補信号線ｓ１０ａに設定された信号遷移をテスト対象回路の出力側へゲート１段分だけ伝搬させるために、活性化、含意操作および正当化を行う。これにより、装置は、信号線ｓ７にＮＤを設定し、信号線ｓ６ｂにＳ０を設定する。テスト系列Ｔ１は、｛Ｐ｝＝｛Ｘ，０，０，１，１，Ｘ，Ｘ｝に更新され、テスト系列Ｔ２は、｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新される。
【０３４７】
（ステップ２５１０）ステップ２５０９では矛盾が発生していないので、装置は、ステップ２５１２へ進む。
（ステップ２５１１）装置は、到達候補信号線ｓ７を新たな到達信号線に設定し、ステップ２５０２へ進む。
【０３４８】
装置は、同様に、図３６に示される処理を実行する。テスト対象信号線から観測点までの経路を選択しながらテストパターンを生成する方法は、第１〜第１４の実施形態において説明したので、以下の詳細な説明を省略する。結果として、装置は、テスト対象信号線ｓ１０から、信号線ｓ７、ｓ８ａ、ｓ４を順に経由して観測点ＰＯ１へと至る経路を選択しながら、テスト系列＜Ｔ１，Ｔ２＞を決定する。装置は、ステップ２５１３において、テスト系列Ｔ１を、｛Ｐ｝＝｛Ｘ，０，０，１，１，Ｘ，Ｘ｝に更新し、テスト系列Ｔ２を、｛Ｐ｝＝｛Ｘ，１，Ｘ，１，Ｘ，Ｘ，Ｘ｝に更新する。その後、装置は、ステップ２６０４へ進む。
【０３４９】
このように、まず、第２の決定処理において、制御点から当該テスト対象信号線までの距離がより長い経路についてテストパターンが生成される。次に、第１の決定処理において、テスト対象信号線から観測点までの経路長がより長い経路について、第１の決定処理で生成されたテストパターンを更新しながら、テストパターンが決定される。よって、第１８の生成方法によれば、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【０３５０】
また、最初に制御点からテスト対象信号線へと信号伝搬可能な経路が選択されるため、テスト対象信号線上の信号伝搬を確実に制御可能な経路について効率的にテストパターンを生成することができる。
【０３５１】
＜第１９の実施形態＞
図３９は、本発明の第１９の生成方法を示すフロー図である。第１９の生成方法は、第１７の生成方法に主としてステップ２２００及び２７００が追加されている点で、第１７の生成方法と相違する。
【０３５２】
第１９の生成方法で初出のステップは、次の通りである。
（ステップ２２００）装置は、テスト対象信号線から観測点までの最長観測距離ｄ１と、テスト対象信号線から制御点までの最長制御距離ｄ２とを計算する。最長観測距離及び最長制御距離は、上記の各生成方法と同様に、遅延値テーブル（図２）やビアテーブル（図３）、または、制御候補信号線と制御点との間に接続されるゲート数等を用いて算出される。
【０３５３】
（ステップ２７００）装置は、ステップ２２００で算出した最長観測距離ｄ１と、最長制御距離ｄ２とを比較する。装置は、ｄ１がｄ２より小さくない（すなわち、ｄ１がｄ２以上である）場合には、第１の決定処理（ステップ２６０１）を実行した後、第２の決定処理（ステップ２６０３）を実行する。この場合における第１９の生成方法は、第１７の生成方法と同じである。一方、ｄ１がｄ２より小さい場合には、装置は、第２の決定処理（ステップ２６０３）を実行した後、第１の決定処理（ステップ２６０１）を実行する。この場合における第１９の生成方法は、第１８の生成方法と同じである。
【０３５４】
なお、第１の決定処理には、上記の第１〜第１３の生成方法における検査系列生成処理のいずれかを適用することができる。また、第１の決定処理として、第１７の生成方法と同様に、図３６に示される検査系列生成処理が適用されてもよい。一方、第２の決定処理には、上記の第１４〜第１６における検査系列生成処理のいずれかを適用することができる。
【０３５５】
ここで、図３７に示すテスト対象回路に対して第１９の生成方法を実行したときの処理を説明する。ここでは、信号線ｓ１０の立上がり遷移をテスト対象とし、｛ＰＩ１，ＰＩ２，ＰＩ３，ＰＩ４，ＰＩ５，ＰＩ６，ＰＩ７｝を｛Ｐ｝と記載する。初期状態においては、検査系列Ｔ１及びＴ２のいずれも、｛Ｐ｝＝｛Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ，Ｘ｝に設定されている。
【０３５６】
また、以下の例においては、第１の決定処理として図３６に示される検査系列生成処理が適用され、かつ、第２の決定処理として図３０に示される検査系列生成処理が適用される場合を想定する。
【０３５７】
（ステップ２１０３）装置は、テスト対象信号線ｓ１０にＮＤを設定し、ステップ２２００へ進む。
（ステップ２２００）装置は、テスト対象信号線ｓ１０から観測点までの最長観測距離を求める。観測距離をゲート数によって評価すると、テスト対象信号線ｓ１０から、信号線ｓ１０ａ、ｓ７、ｓ８ａ及びｓ４を順に経由して制御点ＰＯ１へと至る経路が最長であり、最長観測距離ｄ１は、３である。一方、制御距離をゲート数によって評価すると、テスト対象信号線ｓ１０から、信号線ｓ５ｂ及びｓ５を順に経由して制御点ＰＩ２へと至る経路が最長であり、最長制御距離ｄ２は、２である。
【０３５８】
（ステップ２７００）最長観測距離ｄ１は、最長制御距離ｄ２より小さくないので、装置は、ステップ２６０１へ進み、第１の決定処理を第２の決定処理の前に実行する。
なお、以降の具体的な処理は、第１７の生成方法と同一であるので、ここでの説明は繰り返さない。
【０３５９】
結果として、装置は、検査系列Ｔ１として｛Ｐ｝＝｛１，１，０，１，１，Ｘ，Ｘ｝を決定し、検査系列Ｔ２として｛Ｐ｝＝｛１，１，０，０，１，Ｘ，Ｘ｝を決定する。
【０３６０】
このように、第１９の生成方法においては、テスト対象信号線から観測点までの最長経路の長さは、当該テスト対象信号線から制御点までの最長経路の長さと比較され、比較結果に応じて、第１及び第２の決定処理の実行順序が決められる。テスト対象信号線の観測距離及び制御距離が長くなるにつれて、テストパターンの決定がより困難になるが、第１９の生成方法によれば、より長い経路を伝搬するテストパターンを先に決定するので、テストパターンを効率的に生成することができる。
【産業上の利用可能性】
【０３６１】
本発明のテストパターン生成方法は、遅延故障を検査するための高品質のテストパターンを高速に生成できるので、例えば、各種の半導体集積回路で発生する遅延故障を検査するためのテストパターンを生成するときに利用することができる。
【図面の簡単な説明】
【０３６２】
【図１】本発明の各実施形態に係るテストパターン生成方法を実行するテストパターン生成システムの構成を示す図
【図２】遅延値テーブルの例を示す図
【図３】ビアテーブルの例を示す図
【図４】本発明の第１の実施形態に係るテストパターン生成方法を示すフロー図
【図５】テスト対象回路の例を示す図
【図６】従来の遷移故障用パターン生成方法を示すフロー図
【図７】本発明の第２の実施形態に係るテストパターン生成方法を示すフロー図
【図８】テスト対象回路の例を示す図
【図９】図８に示すテスト対象回路に基づくエッジグラフを示す図
【図１０】エッジグラフの他の例を示す図
【図１１】本発明の第３の実施形態に係るテストパターン生成方法を示すフロー図
【図１２】本発明の第４の実施形態に係るテストパターン生成方法を示すフロー図
【図１３】テスト対象回路の例を示す図
【図１４】本発明の第５の実施形態に係るテストパターン生成方法を示すフロー図
【図１５】本発明の第６の実施形態に係るテストパターン生成方法を示すフロー図
【図１６】テスト対象回路の例を示す図
【図１７】本発明の第７の実施形態に係るテストパターン生成方法を示すフロー図
【図１８】本発明の第８の実施形態に係るテストパターン生成方法を示すフロー図
【図１９】本発明の第９の実施形態に係るテストパターン生成方法を示すフロー図
【図２０】本発明の第１０の実施形態に係るテストパターン生成方法を示すフロー図
【図２１】本発明の第１１の実施形態に係るテストパターン生成方法を示すフロー図
【図２２】テスト対象回路の例を示す図
【図２３】本発明の第１２の実施形態に係るテストパターン生成方法を示すフロー図
【図２４】図９に示すエッジグラフを簡略化したエッジグラフを示す図
【図２５】本発明の第１３の実施形態に係るテストパターン生成方法を示すフロー図
【図２６】本発明の第１４〜第１９の実施形態に係るテストパターン生成方法で用いられる値を示す図
【図２７】本発明の第１４〜第１９の実施形態に係るテストパターン生成方法で用いられる経路活性化表の一例を示す図
【図２８】本発明の第１４〜第１９の実施形態に係るテストパターン生成方法で用いられる経路活性化表の他の一例を示す図
【図２９】本発明の第１４の実施形態に係るテストパターン生成方法を示すフロー図
【図３０】図２９に示される検査系列生成処理の詳細を示すフロー図
【図３１】テスト対象回路の例を示す図
【図３２】本発明の第１５の実施形態に係るテストパターン生成方法を示すフロー図
【図３３】テスト対象回路の例を示す図
【図３４】本発明の第１６の実施形態に係るテストパターン生成方法を示すフロー図
【図３５】本発明の第１７の実施形態に係るテストパターン生成方法を示すフロー図
【図３６】図３５に示される第１の決定処理の詳細を示すフロー図
【図３７】テスト対象回路の例を示す図
【図３８】本発明の第１８の実施形態に係るテストパターン生成方法を示すフロー図
【図３９】本発明の第１９の実施形態に係るテストパターン生成方法を示すフロー図
【図４０】パス遅延故障用パターン生成方法で用いられる５値を示す図
【図４１】パス遅延故障用パターン生成方法で用いられる含意表を示す図
【図４２】パス遅延故障用パターン生成方法で用いられる経路活性化表を示す図
【図４３】パス遅延故障用パターン生成方法における信号遷移の伝搬を示す図
【図４４】パス遅延故障用パターン生成方法の実行例を示す図
【図４５】検査系列を変換して得られるシリアルパターンを示す図
【図４６】遷移故障用パターン生成方法で用いられる経路活性化表および含意表を示す図
【図４７】遷移故障用パターン生成方法の実行例を示す図
【符号の説明】
【０３６３】
Ａ…テストパターン生成システム
Ｃ…回路情報
Ｐ…テストパターン
【図１】
2007017430.tif 000003
【図２】
2007017430.tif 000004
【図３】
2007017430.tif 000005
【図４】
2007017430.tif 000006
【図５】
2007017430.tif 000007
【図６】
2007017430.tif 000008
【図７】
2007017430.tif 000009
【図８】
2007017430.tif 000010
【図９】
2007017430.tif 000011
【図１０】
2007017430.tif 000012
【図１１】
2007017430.tif 000013
【図１２】
2007017430.tif 000014
【図１３】
2007017430.tif 000015
【図１４】
2007017430.tif 000016
【図１５】
2007017430.tif 000017
【図１６】
2007017430.tif 000018
【図１７】
2007017430.tif 000019
【図１８】
2007017430.tif 000020
【図１９】
2007017430.tif 000021
【図２０】
2007017430.tif 000022
【図２１】
2007017430.tif 000023
【図２２】
2007017430.tif 000024
【図２３】
2007017430.tif 000025
【図２４】
2007017430.tif 000026
【図２５】
2007017430.tif 000027
【図２６】
2007017430.tif 000028
【図２７】
2007017430.tif 000029
【図２８】
2007017430.tif 000030
【図２９】
2007017430.tif 000031
【図３０】
2007017430.tif 000032
【図３１】
2007017430.tif 000033
【図３２】
2007017430.tif 000034
【図３３】
2007017430.tif 000035
【図３４】
2007017430.tif 000036
【図３５】
2007017430.tif 000037
【図３６】
2007017430.tif 000038
【図３７】
2007017430.tif 000039
【図３８】
2007017430.tif 000040
【図３９】
2007017430.tif 000041
【図４０】
2007017430.tif 000042
【図４１】
2007017430.tif 000043
【図４２】
2007017430.tif 000044
【図４３】
2007017430.tif 000045
【図４４】
2007017430.tif 000046
【図４５】
2007017430.tif 000047
【図４６】
2007017430.tif 000048
【図４７】
2007017430.tif 000049