米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 測定; 光学 -> 松下電器産業株式会社

発明の名称 テストパターン生成方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−17430(P2007−17430A)
公開日 平成19年1月25日(2007.1.25)
出願番号 特願2006−152172(P2006−152172)
出願日 平成18年5月31日(2006.5.31)
代理人 【識別番号】100098291
【弁理士】
【氏名又は名称】小笠原 史朗
発明者 吉村 慎一 / 三浦 友和 / 太田 光保 / 市川 修
要約 課題
遅延故障を検査するための高品質のテストパターンを高速に生成する。

解決手段
後のテスト周期で与えられる第2のテストパターンを生成するために、回路中に設定された故障値を観測点まで伝搬させる。回路中の分岐点では、分岐の枝の中から故障値を伝搬させる信号線を選択し、活性化と正当化を行うことにより回路中の信号線の値を求め、活性化と正当化に成功した場合には、求めた信号線の値に基づき第2のテストパターンを更新する。信号線を選択するときには、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択する。
特許請求の範囲
【請求項1】
テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法であって、
前記第1のテストパターンとして、テスト対象信号線の値を仮定した遅延故障に応じた初期値に一致させる入力値の組合せを求めるステップと、
前記第2のテストパターンとして、前記テスト対象信号線に設定された、仮定した遅延故障に応じた故障値を観測点まで伝搬させる入力値の組合せを求めるステップとを備え、
前記第2のテストパターンを求めるステップは、
前記テスト対象回路に含まれる分岐点において、複数の分岐の枝の中から、故障値を伝搬させる信号線を選択するステップと、
選択された信号線に故障値を伝搬させるために活性化および正当化を行い、前記テスト対象回路に含まれる信号線の値を求めるステップと、
活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第2のテストパターンを更新するステップとを含み、
前記信号線を選択するステップは、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択することを特徴とする、テストパターン生成方法。
【請求項2】
前記テスト対象信号線は、前記テスト対象回路に含まれる制御点および分岐の枝の中から選択され、
前記信号線を選択するステップは、分岐の枝から分岐点を経由せずに到達できる分岐の幹または観測点に至る経路を構成する信号線を一括して選択することを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項3】
前記信号線を選択するステップは、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝を信号線選択の候補から除外することを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項4】
前記信号線の値を求めるステップは、ロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第1のテストパターンを更新するステップをさらに含むことを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項5】
前記信号線の値を求めるステップは、ノンロバスト条件に従い活性化を行うことを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項6】
前記信号線の値を求めるステップは、当初はロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての分岐の枝についてロバスト条件下での活性化に失敗した場合には、ノンロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第1のテストパターンを更新するステップをさらに含むことを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項7】
前記信号線の値を求めるステップは、選択された分岐の枝について、ロバスト条件に従い活性化を行い、当該処理に失敗した場合にはノンロバスト条件に従い活性化を行い、
ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき前記第1のテストパターンを更新するステップをさらに含むことを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項8】
前記第2のテストパターンを求めるステップは、
ある分岐点で選択可能なすべての分岐の枝について活性化および正当化に失敗した場合には、過去に信号線の選択が行われた分岐点までバックトラックするステップをさらに含む、請求項1に記載のテストパターン生成方法。
【請求項9】
前記バックトラックするステップは、直前に信号線の選択が行われた分岐点までバックトラックすることを特徴とする、請求項8に記載のテストパターン生成方法。
【請求項10】
前記バックトラックするステップは、いずれかの未選択の分岐の枝を含む最長テスト経路の長さが所定の基準を満たす分岐点のうち、直近に信号線の選択が行われた分岐点までバックトラックすることを特徴とする、請求項8に記載のテストパターン生成方法。
【請求項11】
前記バックトラックするステップは、過去に信号線の選択が行われた分岐点のうち、未選択の分岐の枝を含む最長テスト経路の長さが最も長い分岐点までバックトラックすることを特徴とする、請求項8に記載のテストパターン生成方法。
【請求項12】
前記バックトラックするステップは、バックトラック先の分岐点以降に故障値を伝搬させるために求められた制御点の値を保持したまま、バックトラックすることを特徴とする、請求項8に記載のテストパターン生成方法。
【請求項13】
ある制御点を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該制御点は前記テスト対象信号線から除外され、
ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝は前記テスト対象信号線から除外されるとともに、前記信号線を選択するステップにおける信号線選択の候補から除外されることを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項14】
前記テスト対象回路に含まれる制御点、信号線および観測点を指定するステップをさらに備え、
前記テスト対象回路に含まれる信号線のうち、指定された制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線、指定された信号線から任意の観測点に至る経路を構成する信号線、および、指定された観測点に到達する経路のみに含まれる信号線は、前記テスト対象信号線から除外され、前記信号線を選択するステップにおける信号線選択の候補から除外され、前記信号線の値を求めるステップでは固定値が与えられることを特徴とする、請求項1に記載のテストパターン生成方法。
【請求項15】
テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法であって、
前記テスト対象回路に含まれる複数の信号線の中から選択されたテスト対象信号線に信号遷移を設定し、前記テスト対象信号線を制御信号線に設定するステップと、
前記制御信号線へと信号を伝搬する1以上の制御候補信号線の各々について、前記制御候補信号線から、信号が入力される制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、前記制御候補信号線の中から1本の制御候補信号線を選択するステップと、
選択された前記制御候補信号線から前記制御信号線へと信号遷移を伝播させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第1及び第2のテストパターンを決定するステップとを備える、テストパターン生成方法。
【請求項16】
活性化及び正当化に成功した場合には、選択された制御候補信号線を制御信号線として再設定し、
活性化及び正当化に失敗した場合には、未選択の前記制御候補信号線の中から1本の信号線を再選択し、
可制御の制御点に到達するまで、前記信号線を選択するステップと、前記信号値を求めるステップと、前記第1及び第2のテストパターンを決定するステップとを繰り返し実行することを特徴とする、請求項15に記載のテストパターン生成方法。
【請求項17】
ある制御信号線に信号を伝搬する全ての前記制御候補信号線について活性化及び正当化に失敗した場合には、過去に信号線の選択が行われた信号線までバックトラックするステップを更に備える、請求項15に記載のテストパターン生成方法。
【請求項18】
前記信号値を求めるステップは、前記制御候補信号線が複数存在する場合には、前記制御候補信号線から前記制御点までの経路が最長である制御候補信号線についてのみ信号遷移を設定し、他の制御候補信号線には一定の信号値を設定することを特徴とする、請求項15に記載のテストパターン生成方法。
【請求項19】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路に含まれるゲート数が最大である経路を、最長経路として選択することを特徴とする、請求項15に記載のテストパターン生成方法。
【請求項20】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路に含まれるビア数が最大である経路を、最長経路として選択することを特徴とする、請求項15に記載のテストパターン生成方法。
【請求項21】
前記信号線を選択するステップは、前記制御信号線から前記制御点までの経路の各々の遅延情報に基づいて、最長経路を選択することを特徴とする、請求項15に記載のテストパターン生成方法。
【請求項22】
テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法であって、
前記テスト対象回路に含まれる複数の信号線の中からテスト対象信号線を選択し、前記テスト対象信号線に信号遷移を設定するステップと、
前記テスト対象信号線に設定された信号遷移を、前記テスト対象信号線から、信号が出力される観測点まで伝搬させる前記第1及び第2のテストパターンを決定する第1の決定ステップと、
信号が入力される制御点から前記テスト対象信号線へと、設定された信号遷移を伝搬させる前記第1及び第2のテストパターンを決定する第2の決定ステップとを備え、
前記第1の決定ステップは、
前記テスト対象信号線を到達信号線に設定するステップと、
前記到達信号線から分岐する1以上の到達候補信号線の各々について、前記到達候補信号線からいずれか1つの観測点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づき、前記到達候補信号線の中から一本の到達候補信号線を選択するステップと、
選択された前記到達候補信号線に信号を伝搬させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
前記活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第1及び第2のテストパターンを決定するステップとを含み、
前記第2の決定ステップは、
前記テスト対象信号線を制御信号線に設定するステップと、
前記制御信号線へと信号を伝搬する1以上の制御候補信号線の各々について、前記制御候補信号線からいずれか1つの制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、前記制御候補信号線の中から1本の制御候補信号線を選択するステップと、
選択された前記制御候補信号線から前記制御信号線へと信号遷移を伝搬させるために活性化及び正当化を行い、前記テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、
活性化及び正当化に成功した場合に、求められた信号値に基づいて、前記第1及び第2のテストパターンを決定するステップとを含む、テストパターン生成方法。
【請求項23】
前記第1の決定ステップは、前記第2の決定ステップの前に行われることを特徴とする、請求項22に記載のテストパターン生成方法。
【請求項24】
前記第1の決定ステップは、前記第2の決定ステップの後に行われることを特徴とする、請求項22に記載のテストパターン生成方法。
【請求項25】
前記テスト対象信号線から前記観測点までの経路長の最大値を第1の最大経路長として算出し、前記テスト対象信号線から前記制御点までの経路長の最大値を第2の最大経路長として算出するステップを更に備え、
前記第1の最大経路長が前記第2の最大経路長より長いときには、前記第1の決定ステップは、前記第2の決定ステップの前に行われ、前記第1の最大経路長が前記第2の最大経路長以下であるときには、前記第1の決定ステップは、前記第2の生成ステップの後に行われることを特徴とする、請求項22に記載のテストパターン生成方法。

発明の詳細な説明
【技術分野】
【0001】
本発明は、半導体集積回路における遅延故障を検査するためのテストパターンを生成するテストパターン生成方法に関する。
【背景技術】
【0002】
従来から、半導体集積回路内で信号伝搬中に発生する遅延故障を検査するために、遅延故障をいくつかの故障モデルに従って分類し、各故障モデルの特徴に合わせたテストパターンを生成する方法が知られている。遅延故障の故障モデルには、大きく分けて、パス遅延故障モデルと遷移故障モデルとがある。パス遅延故障モデルを用いれば、テスト対象経路上に発生する微小欠陥の積み重ねによる遅延故障や1箇所にある大きな遅延故障を検出することができる。これに対して、遷移故障モデルを用いれば、テスト対象となる信号線またはゲート上の1箇所にある大きな遅延故障を検出することができる。
【0003】
一般に、遅延故障を検査するためには、2つの検査系列(以下、検査系列T1およびT2という)が必要とされる。自動テスト装置は、テスト対象回路に対してあるタイミングで検査系列T1を与え、次のテスト周期で検査系列T2を与える。この検査系列を<T1,T2>と記載する。以下、パス遅延故障を検査するためのテストパターン生成方法(以下、パス遅延故障用パターン生成方法という)および遷移故障を検査するためのテストパターン生成方法(以下、遷移故障用パターン生成方法という)について説明する。
【0004】
なお、パス遅延故障用パターン生成方法については、例えば、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. などに記載されている。
【0005】
まず、パス遅延故障用パターン生成方法について説明する。パス遅延故障用パターン生成方法では、テストパターンは、例えば、テスト対象回路内の各信号線に対して図40に示す5値の論理値を、図41に示す含意表や図42に示す経路活性化表に従って割り当てることによって生成される。図40に示す論理値S0は、信号線の値が検査系列T1とT2の両方で0であることを示す。論理値S1は、信号線の値が検査系列T1とT2の両方で1であることを示す。論理値U0は、信号線の値が検査系列T1ではX(0でも1でもよい)、検査系列T2では0であることを示す。論理値U1は、信号線の値が検査系列T1ではX、検査系列T2では1であることを示す。論理値XXは、信号線の値が検査系列T1とT2の両方でXであることを示す。
【0006】
図41(a)〜(c)に、ANDゲート、ORゲートおよびインバータの含意表を示す。各含意表には、上記5値の入力値の組合せに対する出力値が記載されている。例えば、ANDゲートの入力aがS0、bがU0であるときの出力yは、次のようにして求められる。入力aがS0であるので、aの値は検査系列T1とT2の両方で0である。また、入力bがU0であるので、bの値は検査系列T1ではX、検査系列T2は0である。したがって、yの値は、検査系列T1とT2の両方で0となる。このことを5値を用いて表現すると、出力yはS0となる。
【0007】
パス遅延故障用パターン生成方法では、テスト対象経路を活性化するときに、ロバスト条件およびノンロバスト条件のいずれかが使用される(図42を参照)。ロバスト条件を用いれば、テスト対象経路上のゲートに接続された入力であって、テスト対象経路上にないもの(以下、テスト対象外入力という)に遅延故障が発生した場合でも、テスト対象経路上の遅延故障を正しく検出することができる。一方、ノンロバスト条件を用いれば、テスト対象外入力に遅延故障が発生した場合には、テスト対象経路上の遅延故障を正しく検出できない可能性がある。
【0008】
以下、信号線の立上り遷移をND、信号線の立下り遷移をDと表す。例えば、ANDゲートにおいて、入力aの値が0から1に変化したときに出力yの値が必ず変化する(すなわち、立上り遷移NDを入力aから出力yに伝搬させる)ための条件は、入力bにU1を与えることである(図42(a)を参照)。したがって、ANDゲートにおいてロバスト条件で立上り遷移NDを伝搬させるための条件は、U1(テスト対象外入力にU1を与える)となる。また、ORゲートにおいて、入力aの値が1から0に変化したときに出力yの値が必ず変化する(すなわち、立下り遷移Dを入力aから出力yに伝搬させる)ための条件は、入力bにU0を与えることである(図42(b)を参照)。したがって、ORゲートにおいてロバスト条件で立下り遷移Dを伝搬させるための条件は、U0(テスト対象外入力にU0を与える)となる。
【0009】
図42(c)に、ANDゲート、NANDゲート、ORゲートおよびNORゲートのロバスト条件での活性化条件を示す。図42(c)には、各種類のゲートにおいて、ロバスト条件で立上り遷移NDまたは立下り遷移Dを伝搬させるためにテスト対象外入力に与えるべき値が記載されている。図42(d)に、ANDゲート、NANDゲート、ORゲートおよびNORゲートのノンロバスト条件での活性化条件を示す。図42(d)には、各種類のゲートにおいて、ノンロバスト条件で立上り遷移NDまたは立下り遷移Dを伝搬させるためにテスト対象外入力に与えるべき値が記載されている。
【0010】
テスト対象経路上のすべてのゲートのテスト対象外入力に対してロバスト条件を満たす値を設定できる場合には、そのテスト対象経路をロバストテスト可能経路という。また、テスト対象経路上の少なくとも1つのゲートのテスト対象外入力に対してノンロバスト条件を満たす値を設定できる場合には、そのテスト対象経路をノンロバストテスト可能経路という。ノンロバストテスト可能経路を検査するためのテストパターンは、テスト対象外入力に遅延故障が発生した場合でも、テスト対象経路上の遅延故障をできるだけ多く検査できることが好ましい。このようなテストパターンは、テスト対象外入力とテスト対象経路上のゲートの伝搬遅延値が最大になるように、テスト対象外入力に値を設定する経路を考慮する方法や、テスト対象経路上に多入力ゲートが存在する場合に、なるべく多くのテスト対象外入力にロバスト条件を満たす値を設定する方法によって生成される(非特許文献1を参照)。
【0011】
図43に、テスト対象回路の例を示す。図43に示すSFF1〜6は、スキャンフリップフロップ(以下、スキャンFFという)であり、全体でスキャンチェーンを構成する。SFF1〜6は、CK端子に入力されるクロック信号が立上ると、SE端子からの入力信号がテストモードを示す場合にはDT端子からの入力信号を取り込み、SE端子からの入力信号が通常モードを示す場合にはD端子からの入力信号を取り込む。したがって、テストモードでクロックが入力されると、スキャン入力端子SINからの入力信号がSFF1のQ出力に、SFF1〜5のQ出力がそれぞれSFF2〜6のQ出力に現れる。SFF6のQ出力は、外部出力端子PO1経由で外部に出力される。
【0012】
図43に示すテスト対象回路に含まれる経路P(入力端子X3からゲートg2、g5、
g6を経由してSFF6に至る経路;以下、テスト対象経路Pという)におけるパス遅延故障を検査するためのテストパターンは、以下のようにして生成される。まず、図43に示すように、テスト対象経路P上の各信号線に信号遷移が設定される。次に、図42(c)に示す経路活性化表に従って、テスト対象経路P上の各ゲートのテスト対象外入力に対して、各ゲートを活性化する信号値が与えられる。さらに、図41に示す含意表に従って、各信号線に与えられた信号値に基づき、各入力信号線に与えるべき信号値が決定される(図44を参照)。
【0013】
以上の処理により、検査系列T1として{SFF1,SFF2,SFF3,SFF4,SFF5}={0,X,0,0,X}が生成され、検査系列T2として{SFF1,SFF2,SFF3,SFF4,SFF5}={0,X,1,0,0}が生成される。最後に、検査系列<T1,T2>は、シリアルパターンに変換される。検査系列T2は、検査系列T1で各スキャンFFに設定された値をさらに1クロックだけスキャンシフトさせる方法(SKEWED−LOAD手法)、あるいは、検査系列T1で各スキャンFFに値を設定した後に回路を1クロックだけ通常動作させる方法(BROAD−SIDE手法)のいずれかによって得られる。なお、どちらの方法を用いる場合でも、検査系列T2の値を各スキャンFFに設定できるか否かを判定する正当化処理を行う必要がある。図43に示すテスト対象回路に含まれるテスト対象経路Pについては、SKEWED−LOAD手法によれば図45(a)に示すテストパターンが得られ、BROAD−SIDE手法によれば図45(b)に示すテストパターンが得られる。
【0014】
次に、遷移故障用パターン生成方法について説明する。遷移故障用パターン生成方法では、テストパターンは、テスト対象の信号線またはゲートに信号遷移を設定し、その信号遷移を外部出力または観測フリップフロップまで伝搬させるように、各ゲートの信号値を決定することにより生成される。その際、テスト対象の信号線またはゲートから外部出力または観測フリップフロップに至る活性化経路に対して、所定の経路活性化表および含意表に従って、信号値が割り当てられる。例として図46に、ANDゲートの経路活性化表および含意表を示す。
【0015】
図47(a)に、テスト対象回路の一例を示す。図47(a)に示すテスト対象回路において、NANDゲートg3の出力の立上り遷移が遅くなる遷移故障(slow−to−rise)を検査するためのテストパターンは、以下のようにして生成される。まず、図47(a)に示すように、NANDゲートg3の出力に初期値0を与えるために、検査系列T1として{X1,X2,X3,X4,X5}={X,X,0,X,X}が生成される。次に、故障ゲートg3の出力が初期値0(設定した初期値)に固定される縮退故障を仮定し、この縮退故障を検査するための検査系列T2として{X1,X2,X3,X4,X5}={0,X,1,1,1}が生成される(図47(b)を参照)。以上の処理によって得られた検査系列<T1,T2>が、NANDゲートg3の出力におけるslow−to−rise故障を検査するための検査系列となる。
【0016】
遷移故障モデルを用いた場合、仮定される故障の総数は、回路の構造には依存せず、回路中のゲートの入出力端子数の合計になる。このため、遷移故障モデルを用いた場合、検査系列生成処理や検出判定処理で扱う状態数は、ゲート数のオーダーで済む。したがって、従来の方法を用いても、ほぼ完全な検出率を持つテストパターンを求めることができる。これに対して、パス遅延故障モデルを用いた場合、仮定される故障の総数は、回路の構造に依存し、最も多い場合には回路中のゲート数の指数に比例する。信頼性の点から見れば、すべての信号遷移の伝搬経路について網羅的な検査を行えるパス遅延故障モデルを用いることが好ましい。しかしながら、パス遅延故障用テストパターン生成方法を実行するには、テスト対象経路の本数に応じた長い時間がかかる。このため、パス遅延故障用パターン生成方法には、大規模回路用のテストパターンを現実的な時間では生成できないという問題がある。
【0017】
この問題を解決する方法として、特許文献1には、テスト対象回路内の多数の経路の中から、パス遅延故障の検査対象とする経路を選択する方法が開示されている。この方法では、まず、テスト対象回路内のすべての経路の中から、設計上の遅延値が所定の閾値を超える経路が選択され、次に、選択された経路に含まれる2つの経路のうちで、どちらをパス遅延故障の検査対象とするが判断される。
【0018】
また、特許文献2には、パス遅延故障の検査対象とする経路を選択する別の方法が開示されている。この方法では、テスト対象回路の設計遅延情報と、テスト対象回路内の経路の本数と比べて十分小さな数の経路を活性化する検査系列(あるいは乱数でもよい)とに基づき、設計上の遅延値が所定の閾値よりも小さい活性化可能な経路は検出可能と判断される。上記の検査系列あるいは乱数を用いても検出できない故障については、テスト対象信号線を選択した後、出力側に活性化条件を割り当てながら最長の活性化経路を求める処理が行われる。
【特許文献1】特開平11−218563号公報
【特許文献2】特開2001−51027号公報
【非特許文献1】K. T. Cheng, "Delay Fault Testing for VLSI Circuits", pp.52-53, pp.112-113, 1998.
【発明の開示】
【発明が解決しようとする課題】
【0019】
しかしながら、特許文献1に開示された方法では、パス遅延故障の検査対象として選択される経路の数は依然として膨大である。したがって、この方法で選択されたすべての経路についてパス遅延故障を検査することは現実的には不可能である。
【0020】
また、特許文献2に開示された方法では、短い検査系列あるいは乱数を最初に与えることにより、検出可能なパス遅延故障を効率よく検出することができる。しかし、この処理で検出できなかったパス遅延故障については、活性化条件を割り当てながら最長の活性化経路を求める処理が行われる。一般に、分岐再収斂構造を持つ論理回路は、活性化条件の割り当ては可能であるが、正当化処理(入力側の記憶素子または外部入力端子へ信号を割り当てる処理)で矛盾が発生しやすいという性質を有する。したがって、特許文献2に開示された方法を分岐再収斂構造を持つ論理回路に適用すると、伝搬時間の長い経路を何度も探索する必要が生じ、処理時間が長くなる。
【0021】
それ故に、本発明は、遅延故障を検査するための高品質のテストパターンを高速に生成するテストパターン生成方法を提供することを目的とする。
【課題を解決するための手段】
【0022】
本発明のテストパターン生成方法は、テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法であって、第1のテストパターンとして、テスト対象信号線の値を仮定した遅延故障に応じた初期値に一致させる入力値の組合せを求めるステップと、第2のテストパターンとして、テスト対象信号線に設定された、仮定した遅延故障に応じた故障値を観測点まで伝搬させる入力値の組合せを求めるステップとを備え、第2のテストパターンを求めるステップは、テスト対象回路に含まれる分岐点において、複数の分岐の枝の中から、故障値を伝搬させる信号線を選択するステップと、選択された信号線に故障値を伝搬させるために活性化および正当化を行い、テスト対象回路に含まれる信号線の値を求めるステップと、活性化および正当化に成功した場合に、求めた信号線の値に基づき第2のテストパターンを更新するステップとを含み、信号線を選択するステップ
は、各分岐の枝から観測点までの最長経路の長さに基づき、いずれかの分岐の枝を選択することを特徴とする(第1の局面)。
【0023】
この場合、テスト対象信号線は、テスト対象回路に含まれる制御点および分岐の枝の中から選択され、信号線を選択するステップは、分岐の枝から分岐点を経由せずに到達できる分岐の幹または観測点に至る経路を構成する信号線を一括して選択してもよい(第2の局面)。
【0024】
あるいは、信号線を選択するステップは、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝を信号線選択の候補から除外してもよい(第3の局面)。
【0025】
あるいは、信号線の値を求めるステップは、ロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第1のテストパターンを更新するステップをさらに含んでいてもよい(第4の局面)。
【0026】
あるいは、信号線の値を求めるステップは、ノンロバスト条件に従い活性化を行ってもよい(第5の局面)。
【0027】
あるいは、信号線の値を求めるステップは、当初はロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての分岐の枝についてロバスト条件下での活性化に失敗した場合には、ノンロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第1のテストパターンを更新するステップをさらに含んでいてもよい(第6の局面)。
【0028】
あるいは、信号線の値を求めるステップは、選択された分岐の枝について、ロバスト条件に従い活性化を行い、当該処理に失敗した場合にはノンロバスト条件に従い活性化を行い、テストパターン生成方法は、ロバスト条件下での活性化および正当化に成功した場合に、求めた信号線の値に基づき第1のテストパターンを更新するステップをさらに含んでいてもよい(第7の局面)。
【0029】
あるいは、第2のテストパターンを求めるステップは、ある分岐点で選択可能なすべての分岐の枝について活性化および正当化に失敗した場合には、過去に信号線の選択が行われた分岐点までバックトラックするステップをさらに含んでいてもよい(第8の局面)。
【0030】
特に、バックトラックするステップは、直前に信号線の選択が行われた分岐点までバックトラックしてもよい(第9の局面)。
【0031】
あるいは、バックトラックするステップは、いずれかの未選択の分岐の枝を含む最長テスト経路の長さが所定の基準を満たす分岐点のうち、直近に信号線の選択が行われた分岐点までバックトラックしてもよい(第10の局面)。
【0032】
あるいは、バックトラックするステップは、過去に信号線の選択が行われた分岐点のうち、未選択の分岐の枝を含む最長テスト経路の長さが最も長い分岐点までバックトラックしてもよい(第11の局面)。
【0033】
あるいは、バックトラックするステップは、バックトラック先の分岐点以降に故障値を伝搬させるために求められた制御点の値を保持したまま、バックトラックしてもよい(第12の局面)。
【0034】
あるいは、ある制御点を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該制御点はテスト対象信号線から除外され、ある分岐の枝を含む最長テスト経路の長さが所定の基準を満たさない場合には、当該分岐の枝はテスト対象信号線から除外されるとともに、信号線を選択するステップにおける信号線選択の候補から除外されてもよい(第13の局面)。
【0035】
あるいは、テストパターン生成方法は、テスト対象回路に含まれる制御点、信号線および観測点を指定するステップをさらに備え、テスト対象回路に含まれる信号線のうち、指定された制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線、指定された信号線から任意の観測点に至る経路を構成する信号線、および、指定された観測点に到達する経路のみに含まれる信号線は、テスト対象信号線から除外され、信号線を選択するステップにおける信号線選択の候補から除外され、信号線の値を求めるステップでは固定値が与えられることとしてもよい(第14の局面)。
【0036】
また、本発明の第15の局面は、テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法に向けられている。当該テストパターン生成方法は、テスト対象回路に含まれる複数の信号線の中から選択されたテスト対象信号線に信号遷移を設定し、テスト対象信号線を制御信号線に設定するステップと、制御信号線へと信号を伝搬する1以上の制御候補信号線の各々について、制御候補信号線から、信号が入力される制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、制御候補信号線の中から1本の制御候補信号線を選択するステップと、選択された制御候補信号線から制御信号線へと信号遷移を伝播させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第1及び第2のテストパターンを決定するステップとを備える。
【0037】
この場合、活性化及び正当化に成功した場合には、選択された制御候補信号線を制御信号線として再設定し、活性化及び正当化に失敗した場合には、未選択の制御候補信号線の中から1本の信号線を再選択し、可制御の制御点に到達するまで、信号線を選択するステップと、信号値を求めるステップと、第1及び第2のテストパターンを決定するステップとを繰り返し実行してもよい(第16の局面)。
【0038】
あるいは、ある制御信号線に信号を伝搬する全ての制御候補信号線について活性化及び正当化に失敗した場合には、過去に信号線の選択が行われた信号線までバックトラックするステップを更に備えてもよい(第17の局面)。
【0039】
あるいは、信号値を求めるステップは、制御候補信号線が複数存在する場合には、制御候補信号線から制御点までの経路が最長である制御候補信号線についてのみ信号遷移を設定し、他の制御候補信号線には一定の信号値を設定してもよい(第18の局面)。
【0040】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路に含まれるゲート数が最大である経路を、最長経路として選択してもよい(第19の局面)。
【0041】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路に含まれるビア数が最大である経路を、最長経路として選択してもよい(第20の局面)。
【0042】
あるいは、信号線を選択するステップは、制御信号線から制御点までの経路の各々の遅延情報に基づいて、最長経路を選択してもよい(第21の局面)。
【0043】
本発明の第22の局面は、テスト対象回路で発生する遅延故障を検出するために、第1のテストパターンと、次のテスト周期で与えられる第2のテストパターンとを生成するテストパターン生成方法に向けられている。当該テストパターン生成方法は、テスト対象回路に含まれる複数の信号線の中からテスト対象信号線を選択し、テスト対象信号線に信号遷移を設定するステップと、テスト対象信号線に設定された信号遷移を、テスト対象信号線から、信号が出力される観測点まで伝搬させる第1及び第2のテストパターンを決定する第1の決定ステップと、信号が入力される制御点からテスト対象信号線へと、設定された信号遷移を伝搬させる第1及び第2のテストパターンを決定する第2の決定ステップとを備える。第1の決定ステップは、テスト対象信号線を到達信号線に設定するステップと、到達信号線から分岐する1以上の到達候補信号線の各々について、到達候補信号線からいずれか1つの観測点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づき、到達候補信号線の中から一本の到達候補信号線を選択するステップと、選択された到達候補信号線に信号を伝搬させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第1及び第2のテストパターンを決定するステップとを含む。また、第2の決定ステップは、テスト対象信号線を制御信号線に設定するステップと、制御信号線へと信号を伝搬する1以上の制御候補信号線の各々について、制御候補信号線からいずれか1つの制御点までの最長経路の長さを求め、求められた最長経路の長さの最大値に基づいて、制御候補信号線の中から1本の制御候補信号線を選択するステップと、選択された制御候補信号線から制御信号線へと信号遷移を伝搬させるために活性化及び正当化を行い、テスト対象回路に含まれる信号線に設定する信号値を求めるステップと、活性化及び正当化に成功した場合に、求められた信号値に基づいて、第1及び第2のテストパターンを決定するステップとを含む。
【0044】
この場合、第1の決定ステップは、第2の決定ステップの前に行われてもよい(第23の局面)。
【0045】
あるいは、第1の決定ステップは、第2の決定ステップの後に行われてもよい(第24の局面)。
【0046】
テスト対象信号線から観測点までの経路長の最大値を第1の最大経路長として算出し、テスト対象信号線から制御点までの経路長の最大値を第2の最大経路長として算出するステップを更に備え、第1の最大経路長が第2の最大経路長より長いときには、第1の決定ステップは、第2の決定ステップの前に行われ、第1の最大経路長が第2の最大経路長以下であるときには、第1の決定ステップは、第2の生成ステップの後に行われてもよい(第25の局面)。
【発明の効果】
【0047】
上記第1の局面によれば、より長い経路を用いて故障を伝搬させることにより、テストパターンの品質を高めることができる。
【0048】
上記第2の局面によれば、複数の信号線に対して一括して活性化、含意操作および正当化を行うことにより、処理時間を短縮することができる。
【0049】
上記第3の局面によれば、短い経路に含まれる分岐の枝を信号線選択の候補から予め除外しておくことにより、処理時間を短縮することができる。
【0050】
上記第4の局面によれば、ロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延故障を、他の信号線上に遅延故障が発生したか否かにかかわらず検査することができる。
【0051】
上記第5の局面によれば、ノンロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延の影響を、より長い経路を利用して検出することができる。
【0052】
上記第6の局面によれば、ロバスト条件による活性化に失敗した場合にはノンロバスト条件に従い活性化を行うことにより、ロバスト条件では検査できない故障を検査できるテストパターンを生成することができる。
【0053】
上記第7の局面によれば、このようにロバスト条件に従った活性化を優先して実行することにより、遅延故障の検出経路が同じ場合でも、高品質のテストパターンを生成することができる。
【0054】
上記第8の局面によれば、活性化および正当化に失敗した場合にはバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【0055】
上記第9の局面によれば、直前に選択が行われた分岐点までバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【0056】
上記第10の局面によれば、バックトラックを行う際の戻り先を制限することにより、処理時間を短縮することができる。
【0057】
上記第11の局面によれば、バックトラックを行う際の戻り先を制限し、より長い経路を優先的に選択することにより、テスト対象信号線の遅延の影響をより長い経路で伝搬して検出することができる。
【0058】
上記第12の局面によれば、故障値を伝搬させるときに信号線に割り当てた値を保持する必要がなくなるので、処理時間を短縮し、メモリ使用量を削減することができる。
【0059】
上記第13の局面によれば、所定の基準を満たさない制御点および信号線を除外して処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【0060】
上記第14の局面によれば、指定された信号線を除いて処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【0061】
上記第15の局面によれば、制御点からテスト対象信号線までの経路がより長くなるようなテストパターンを生成することができるため、テストパターンの品質を高めることができる。
【0062】
上記第16の局面によれば、各ステップを繰り返し実行しながら、テスト対象信号線から制御点へと向かって経路を選択しながらテストパターンを決定することができるので、テストパターンをより効率的に生成することができる。
【0063】
上記第17の局面によれば、活性化および正当化に失敗した場合にはバックトラックするので、制御点からテスト対象信号線へと信号遷移を伝搬することができるテストパターンをより確実に生成することができる。
【0064】
上記第18の局面によれば、制御点からテスト対象信号線へと信号伝搬可能な最長の経路以外の経路には、固定値が設定されるので、テスト対象外経路の信号遅延の影響が低減し、テストパターンの信頼性が向上する。
【0065】
上記第22の局面によれば、テスト対象信号線から観測点までの経路長と、テスト対象信号線から制御点までの経路長とがより長くなるように経路が選択されるため、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【0066】
上記第23の局面によれば、最初にテスト対象信号線から観測点へと信号伝搬可能な経路が選択されるため、テスト対象信号線に確実に観測可能な経路について効率的にテストパターンを生成することができる。
【0067】
上記第24の局面によれば、最初に制御点からテスト対象信号線へと信号伝搬可能な経路が選択されるため、テスト対象信号線に確実に制御可能な経路について効率的にテストパターンを生成することができる。
【0068】
上記第25の局面によれば、テスト対象信号線から観測点までの最長経路の長さと、テスト対象信号線から制御点までの最長経路の長さとを比較して、より長い経路を伝搬するテストパターンを先に決定するので、テストパターンを効率的に生成することができる。
【発明を実施するための最良の形態】
【0069】
本発明の第1〜第13の実施形態では、遅延故障を検査するためのテストパターンを生成するテストパターン生成方法について説明する。以下、第1〜第13の実施形態に係るテストパターン生成方法を、それぞれ、第1〜第13の生成方法という。
【0070】
まず、以下の説明で使用する表現および用語について説明する。信号線に設定される値「X」は、信号線に値0または値1のいずれを設定してもよいことを表す。信号線がある分岐点で複数に分岐するとき、当該信号線のうち分岐するまでの部分を「分岐の幹」といい、分岐した後の部分を「分岐の枝」という。スキャンFFの出力を「擬似外部入力」といい、スキャンFFの入力を「擬似外部出力」という。外部入力および擬似外部入力を「制御点」といい、外部出力および擬似外部出力を「観測点」という。テスト対象回路では、端子PI*(*は任意の文字列)は制御点を表し、端子PO*は観測点を表す。各実施形態で示すステップのうち、先の実施形態で既に説明したステップについては、同一のステップ番号を付して説明を省略する。
【0071】
図1は、第1〜第13の生成方法を実行するテストパターン生成システムの構成を示す図である。図1に示すテストパターン生成システムA(以下、装置という)は、入力された回路情報Cに基づき、テストパターンPを生成する。装置の動作概要は、以下のとおりである。ステップ1では、装置には、回路情報Cとして、テスト対象回路を構成する記憶素子、論理素子および素子間の配線に関する情報が入力される。ステップ2では、装置は、テスト対象の信号線および信号遷移を選択する。ステップ3では、装置は、ステップ2で選択した信号線に、ステップ2で選択した信号遷移を設定する。ステップ4では、装置は、ステップ3で設定した信号遷移を観測点まで伝搬させる経路を順次選択し、活性化、含意操作および正当化を行う。この際、信号遷移を伝搬している信号線が分岐する場合には、装置は、観測点までの伝搬経路の長さ(以下、観測距離という)が最長の分岐の枝を選択し、選択した分岐の枝に信号遷移を伝搬させる。ステップ4を実行することにより、検査系列<T1,T2>が得られる。ステップ5では、装置は、得られた検査系列<T1,T2>を一時的に内部またはファイルに記録する。ステップ6では、装置は、ステップ5で記録した検査系列を、自動テスト装置で使用可能なシリアル形式のテストパターンPに変換する。なお、第1〜第13の実施形態で示すフロー図は、いずれも、図1に示すフロー図を詳細化したものである。
【0072】
ステップ4では、観測距離は、ステップ1で入力された回路情報Cに基づき、所定の計算方法に従って算出される。例えば、観測距離は、回路情報Cに含まれる遅延値テーブル(図2)やビアテーブル(図3)を用いて算出される。図2に示す遅延値テーブルでは、ゲートはテスト対象回路に含まれるゲートの名前を、INおよびOUTはゲートの入力信号線および出力信号線の名前を示す。遷移は、入力信号線の遷移を示す。遷移rは立上り遷移を表し、遷移fは立下り遷移を表す。遅延値は、各ゲートのINからOUTまでの信号遷移の伝搬時間を示す。図3(a)に示すビアテーブルでは、ゲートはテスト対象回路に含まれるゲートの名前を、INおよびOUTはゲートの入力信号線および出力信号線の名前を示す。ビア数は、各ゲートのINからOUTまでのビア数とコンタクト数の合計を示す。図3(b)に示すビアテーブルでは、信号線は信号線の名前を示す。ビア数は、信号線上に設けられたビア数とコンタクト数の合計を示す。
【0073】
なお、遅延値テーブルは、電圧や温度に依存して変化する遅延値を記憶していてもよい。また、ゲートに対応した遅延テーブルとともに、配線に対応した遅延値テーブルを使用してもよい。また、遅延値テーブルは、制御点や観測点に関する遅延値を記憶していてもよい。また、配線およびゲートに対応したビアテーブルに代えて、配線のみに対応したビアテーブル、あるいは、ゲートのみに対応したビアテーブルを使用してもよい。また、ビアテーブルは、制御点や観測点に関するビア数を記憶していてもよい。遅延値テーブルおよびビアテーブルは、人手で作成したものでも、電子計算機を用いて求めたものでもよく、その形式も任意でよい。
【0074】
<第1の実施形態>
図4は、第1の生成方法を示すフロー図である。第1の生成方法では、以下の処理が実行される。
(ステップ10)装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子(ゲート)および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
(ステップ11)装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ11では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
(ステップ12)装置は、ステップ11でテスト対象の信号線および信号遷移を選択した場合にはステップ13へ進み、それ以外の場合にはステップ20へ進む。
【0075】
(ステップ13)装置は、ステップ11で選択したテスト対象信号線に、ステップ11で選択した信号遷移の初期値(立上り遷移の場合は0、立下り遷移の場合は1)を設定する。
(ステップ14)装置は、ステップ11で選択したテスト対象信号線の値を、ステップ13で設定した初期値に一致させるための入力値の組合せを求める。これにより、検査系列T1が生成される。
(ステップ15)装置は、ステップ14で検査系列T1の生成に成功した場合にはステップ16へ進み、それ以外の場合にはステップ11へ進む。
【0076】
(ステップ16)装置は、ステップ11で選択したテスト対象信号線に、ステップ11で選択した信号遷移に対応した故障値(立上り遷移のときはND、立下り遷移のときはD)を設定する。
(ステップ100)装置は、後述する検査系列生成処理を行うことにより、検査系列T2を生成する。検査系列生成処理では、ステップ14で生成された検査系列T1が更新される場合もある。装置は、検査系列T2の生成(および検査系列T1の更新)に成功した場合にはステップ19へ進み、それ以外の場合はステップ11へ進む。
【0077】
(ステップ19)装置は、ステップ14、100で生成した検査系列<T1,T2>を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列<T1,T2>を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ11へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ11〜19が実行される。
(ステップ20)装置は、ステップ19で記録した検査系列<T1,T2>をシリアルパターンに変換し、処理を終了する。
【0078】
ステップ100では、以下の処理が実行される。以下、最も新しく故障値が伝搬するようになった信号線を「到達信号線」といい、到達信号線の出力側に接続された、次に故障値が到達する可能性がある信号線を「到達候補信号線」という。
(ステップ101)装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。なお、正当化によって制御点に与えるべき値が決定された場合には、検査系列T2が更新され、場合によっては検査系列T1も更新される。以下に示すすべての正当化処理においても、これと同じである。
(ステップ102)装置は、ステップ101で矛盾が発生した場合にはステップ11へ進み、それ以外の場合にはステップ103へ進む。
【0079】
(ステップ103)装置は、到達信号線に基づき、到達候補信号線を更新する。具体的には、ゲートの入力信号線が到達信号線であり、かつ、当該ゲートの出力信号線が分岐していない場合には、当該ゲートの出力信号線の全体が到達候補信号線となる。また、ゲートの入力信号線が到達信号線であり、かつ、当該ゲートの出力信号線が分岐している場合には、当該ゲートの出力信号線の分岐の幹が到達候補信号線となる。さらに、分岐の幹が到達信号線である場合には、当該分岐の幹の出力側に接続された分岐の枝の全体が到達候補信号線となる。
(ステップ104)装置は、到達候補信号線が1本以下(すなわち、0本または1本)である場合にはステップ105へ進み、それ以外の場合にはステップ108へ進む。
(ステップ105)装置は、到達候補信号線が観測可能であるか、または、0本である(すなわち、到達候補信号線が観測点に接続されているか、または、到達候補信号線がない)場合には、ステップ19へ進み、それ以外の場合にはステップ106へ進む。
(ステップ106)装置がこのステップに到達するのは、到達候補信号線が1本である場合に限られる。装置は、唯一の到達候補信号線を新たな到達信号線に設定する。
【0080】
(ステップ107)装置は、到達信号線の出力側へゲート1段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。なお、到達信号線が分岐の幹である場合には、分岐の枝の値はすでに含意操作により決定されているので、装置は、活性化、含意操作および正当化を行わない。その後、装置はステップ102へ進む。
【0081】
(ステップ108)装置がステップ104からこのステップに到達するのは、到達候補信号線(分岐の枝)が2本以上ある場合に限られる。装置は、各分岐の枝について、各観測点までの経路の長さ(観測距離)を求め、観測距離の最大値(以下、最長観測距離という)を求める。観測距離は、上述したように、遅延値テーブル(図2)やビアテーブル(図3)など用いて算出される。装置は、到達候補信号線の中で最長観測距離が最も長い信号線を新たな到達信号線として選択する。
【0082】
(ステップ109)装置は、ステップ108で到達信号線を選択した場合にはステップ110へ進み、それ以外の場合にはステップ11へ進む。
(ステップ110)装置は、ステップ107と同じ処理を行う。
(ステップ111)装置は、ステップ110で矛盾が発生した場合にはステップ112へ進み、それ以外の場合にはステップ103へ進む。
(ステップ112)装置は、ステップ108で選択した到達信号線を到達候補信号線から除外し、ステップ108へ進む。
【0083】
図5に示すテスト対象回路に対して第1の生成方法を実行したときの処理を説明する。ここでは、信号線s9の立上り遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。
(ステップ13)装置は、テスト対象信号線s9に初期値0を設定する。
(ステップ14)装置は、テスト対象信号線s9に初期値0を設定するために、制御点PI4に0を設定する。検査系列T1は{P}={X,X,X,0,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s9に故障値NDを設定する。
【0084】
(ステップ101)装置は、テスト対象信号線s9に故障値NDを設定し、設定した故障値NDを信号線s10へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s5、s5a、s5b、s5cおよび制御点PI2、PI4には1が設定され、信号線s10には故障値Dが伝搬する。検査系列T2は{P}={X,1,X,1,X,X,X}に更新される。
(ステップ102)ステップ101では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)装置は、信号線s10を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)信号線s10は観測不可なので、装置はステップ106へ進む。
(ステップ106)装置は、信号線s10を到達信号線に設定する。
(ステップ107)到達信号線s10は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ102へ進む。
【0085】
(ステップ102)ステップ107では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)信号線s10は分岐の幹であるので、装置は、信号線s10a、s10bを到達候補信号線に設定する。
(ステップ104)到達候補信号線が2本あるので、装置はステップ108へ進む。
【0086】
(ステップ108)装置は、到達候補信号線s10a、s10bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s10aの最長観測距離は3、信号線s10bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線s10aを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s10aの故障値Dを信号線s7へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s6、s6a、s6bおよび制御点PI3には0が設定され、信号線s7には故障値Dが伝搬する。検査系列T2は{P}={X,1,0,1,X,X,X}に更新される。
(ステップ111)ステップ110では矛盾が発生していないので、装置はステップ103へ進む。
【0087】
(ステップ103〜106)装置は、信号線s7(観測不可)を到達候補信号線に設定した後、信号線s7を到達信号線に設定する。
(ステップ107)装置は、到達信号線s7の故障値Dを信号線s8へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s11および制御点PI5には0が設定され、信号線s8には故障値NDが伝搬する。検査系列T2は{P}={X,1,0,1,0,X,X}に更新される。
【0088】
(ステップ102)ステップ107では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s8(観測不可)を到達候補信号線に設定した後、信号線s8を到達信号線に設定する。
(ステップ107)装置は、到達信号線s8の故障値NDを信号線s4へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s3、s2、s1および制御点PI1には0が設定され、信号線s4には故障値Dが伝搬する。検査系列T2は{P}={0,1,0,1,0,X,X}に更新される。
【0089】
(ステップ102)ステップ107では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)装置は、信号線s4を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s4は観測点PO1に接続されており観測可能なので、装置はステップ19へ進む。
【0090】
以上の処理により、検査系列T1として{P}={X,X,X,0,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。
【0091】
図6は、従来の遷移故障用パターン生成方法を示すフロー図である。上記第1の生成方法は、図6に示す方法において、ステップ17、18をステップ100に置換したものである。図6に示す方法では、ステップ100に代えて、以下の処理が実行される。
(ステップ17)装置は、ステップ16で設定した故障値DまたはNDを観測点まで伝搬するために、活性化、含意操作および正当化を行うことにより、検査系列T2を生成する。
(ステップ18)装置は、ステップ17で検査系列T2の生成に成功した場合にはステップ19へ進み、それ以外の場合にはステップ11へ進む。
【0092】
図5に示すテスト対象回路に対して図6に示す方法を実行したときの処理を説明する。ここでは、信号線s6の立下り遷移をテスト対象とし、{PI1、PI2、PI3、PI4、PI5、PI6、PI7}を{P}と記載する。
(ステップ13)装置は、テスト対象信号線s6に初期値1を設定する。
(ステップ14)装置は、テスト対象信号線s6に初期値1を設定するために、制御点PI3に1を設定する。検査系列T1は{P}={X,X,1,X,X,X,X}に更新される。
(ステップ16)装置は、テスト対象信号線s6に故障値Dを設定する。
【0093】
(ステップ17)装置は、テスト対象信号線s6の故障値Dを観測点まで伝搬させるために、活性化、含意操作および正当化を行う。まず信号線s6の故障値Dを信号線s3に伝搬させるために、信号線s2には0が設定される。次に信号線s3の故障値Dを信号線s4に伝搬させるために、信号線s8には0が設定される。観測点PO1まで故障値を伝搬させた後に、各信号線に対する正当化が行われる。信号線s6を0に正当化するために、制御点PI3には0が設定される。信号線s2を0に正当化するために、信号線s1および制御点PI1には0が設定される。信号線s8を0に正当化するために、信号線s11および制御点PI5には1が設定される。検査系列T2は{P}={0,X,0,X,1,X,X}に更新される。
【0094】
以上の処理により、検査系列T1として{P}={X,X,1,X,X,X,X}が生成され、検査系列T2として{P}={0,X,0,X,1,X,X}が生成される。
【0095】
図5に示すテスト対象回路には、信号線s6に設定された故障値を伝搬させる経路の候補として、信号線s6aを経由する経路と、信号線s6bを経由する経路とが含まれている。このように故障値を伝搬させる経路が複数ある場合、図6に示す従来の方法では、各信号線へ故障値を伝搬させるときの観測のし易さ(可観測費)や制御のし易さ(可制御費)などに基づき、次に故障値を伝搬させる信号線が選択される。上記の例では、可観測費の高い(観測しやすい)信号線s6aが選択されているが、ある条件下では信号線s6bが選択されることもある。いずれの場合でも、観測点まで故障値を伝搬させた後に正当化が行われる。
【0096】
これに対して、第1の生成方法では、故障値を伝搬させる経路が複数ある場合には、最長観測距離が最も長い分岐の枝が、次に故障値を伝搬させる信号線として選択される。このように、より長い経路を用いて故障を伝搬させることにより、テストパターンの品質を高めることができる。
【0097】
なお、以上の説明では、装置は、ステップ108で各分岐の枝について最長観測距離を求めることとした。これに代えて、装置は、同じ分岐の枝について最長観測距離を繰り返し計算することを避けるために、例えばステップ10とステップ11との間で、テスト対象回路に含まれる各分岐の枝について最長観測距離を予め求めておいてもよい。
【0098】
また、故障値を伝搬させる処理を行う際に、回路構成によっては、到達信号線の出力側に接続される到達候補信号線に故障値が既に伝搬している場合がある。このような場合には、装置は、到達候補信号線に対する活性化を行う必要はない。
【0099】
<第2の実施形態>
図7は、第2の生成方法を示すフロー図である。第2の生成方法は、第1の生成方法に対して、ステップ201を追加し、ステップ107を削除し、ステップ11、16、101、106、110をそれぞれステップ202〜206に置換したものである。第2の生成方法は、テスト対象回路をエッジグラフで表現することにより、テストパターンを高速に生成することを特徴とする。エッジグラフの各頂点は、テスト対象回路内の1以上の信号線に対応する。以下、エッジグラフの各頂点に対応する信号線を、グループ内の信号線という。
【0100】
第2の生成方法で初出のステップは、以下のとおりである。
(ステップ201)装置は、テスト対象回路に対して後述する回路変換を行うことにより、エッジグラフを求める。
(ステップ202)装置は、ステップ201で求めたエッジグラフの頂点の中からテスト対象の信号線を選択し、テスト対象の信号遷移を選択する。
(ステップ203)装置は、ステップ202で選択したテスト対象信号線に、ステップ202で選択した信号遷移に対応した故障値を設定する。この際、装置は、グループ内の各信号線に対して、グループ内の先頭の信号線に設定された故障値を正しく伝搬させた場合に得られる故障値を設定する。
(ステップ204)装置は、グループ内の信号線に故障値を設定し、設定した故障値を伝搬させるために、活性化、含意操作および正当化を行う。
(ステップ205)装置は、到達候補信号線のグループを新たな到達信号線として選択する。その後、装置はステップ204へ進む。
(ステップ206)装置は、ステップ204と同じ処理を行う。
【0101】
ステップ201では、以下の処理(図示せず)により、ステップ10で入力された回路情報に基づき、エッジグラフが求められる。
(ステップ201a)装置は、1個の記憶素子または外部入力から1個の分岐の幹までの範囲にある部分回路(これには、ゲートと信号線とが含まれる)を、当該記憶素子または当該外部入力の名前を付した頂点に置換する。
(ステップ201b)装置は、1個の分岐の枝から1個の分岐の幹または観測点までのに範囲にある部分回路を、当該分岐の枝の名前を付した頂点に置換する。
(ステップ201c)テスト対象回路において、あるグループ内の要素と別のグループ内の要素とが接続されている場合には、装置は、これら2つのグループに対応した頂点間に、入力側から出力側へ向かう有向枝を生成する。
【0102】
図8に示すテスト対象回路に対してステップ201の回路変換を実行すると、図9に示すエッジグラフが得られる。図9に示すエッジグラフでは、頂点PI501〜PI508は制御点に、頂点PO501およびPO502は観測点に、その他の頂点は分岐の枝に対応する。図9に示す頂点には、図8に示すテスト対象回路のうちで各頂点に対応した部分回路に含まれる分岐の枝の名前が付されている。例えば、頂点PI504から頂点s510aに向かう枝は、図8に示すテスト対象回路では、外部入力PI504か1以上の信号線を経由して分岐の枝s510aに至る経路があることを示す。
【0103】
なお、ステップ201aおよび201bで頂点に付される名前は、互いに異なっていれば任意でよい。また、図10に示す頂点s517aのように、入力枝と出力枝とが1本ずつ接続された頂点がエッジグラフに含まれている場合には、装置は、このような頂点を入力枝に接続された頂点(図10では、頂点PI507)に併合する処理を行ってもよい。
【0104】
図8に示すテスト対象回路に対して第2の生成方法を実行したときの処理を説明する。ここでは、信号線s502の立上り遷移をテスト対象とし、{PI501,PI502,PI503,PI504,PI505,PI506,PI507,PI508}を{P}と記載する。
(ステップ201)装置は、図8に示すテスト対象回路に対して回路変換を行うことにより、図9に示すエッジグラフを求める。
(ステップ202)装置は、テスト対象の信号線および信号遷移として、信号線s502の立上り遷移を選択する。これ伴い、信号線s502、s504、s505が、グループ内の信号線となる。
【0105】
(ステップ13)装置は、テスト対象信号線s502に初期値0を設定する。
(ステップ14)装置は、テスト対象信号線s502に初期値0を設定するために、制御点PI2に0を設定する。検査系列T1は{P}={X,0,X,X,X,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ203へ進む。
【0106】
(ステップ203)装置は、グループ内の信号線s502、s504、s505に対して、信号線s502(グループ内の先頭の信号線に該当)に設定された故障値NDを正しく伝搬させた場合に得られる故障値を設定する。これにより、信号線s502、s504、s505には、故障値NDが設定される。
(ステップ204)装置は、グループ内の信号線s502、s504、s506に故障値NDを設定あるいは伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s502、s503には1が設定され、信号線s510aには0が設定される。これに伴い、制御点PI502、PI503には1が設定され、制御点PI504、PI505には0が設定される。検査系列T2は{P}={X,1,1,0,0,X,X,X}に更新される。
【0107】
(ステップ102)ステップ204では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜104)信号線s505は分岐の幹であるので、装置は信号線s505a、s505bを到達候補信号線に設定し、ステップ108へ進む。
【0108】
(ステップ108)装置は、到達候補信号線s505a、s505bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s505aの最長観測距離は4、信号線s505bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s505aを到達信号線として選択する。これに伴い、信号線s505a、s506が、グループ内の信号線となる。
(ステップ109)ステップ109で到達信号線を選択したので、装置はステップ206へ進む。
(ステップ206)装置は、グループ内の信号線s505a、s506に故障値を伝搬させるために、活性化、含意操作および正当化を行う。このステップが実行されるより前に、信号線s511には1が設定されている。このため、新たに信号線に値を設定しなくても、グループ内の信号線s505a、s506には故障値NDが伝搬する。
(ステップ111)ステップ206では矛盾が発生していないので、装置はステップ103へ進む。
【0109】
(ステップ103〜104)信号線s506は分岐の幹であるので、装置は信号線s506a、s506bを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s506a、s506bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s506aの最長観測距離は1、信号線s506bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s506bを到達信号線として選択する。これに伴い、信号線s506b、s513、s514、s515が、グループ内の信号線となる。
(ステップ206)装置は、グループ内の信号線s506b、s513、s514、s515に故障値を伝搬させるために、活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、信号線s519aには0が設定されている。したがって、信号線s513の故障値NDを信号線s514に伝搬させるために、装置が信号線s519aに1を設定すると、矛盾が発生する。
(ステップ111)ステップ206で矛盾が発生するので、装置はステップ112へ進む。
(ステップ112)装置は、到達候補信号線から到達信号線s506bを除外する。この時点で、到達候補信号線は、信号線s506aのみとなる。
【0110】
(ステップ108)装置は、到達候補信号線s506aが属するグループを到達信号線として選択する。これに伴い、信号線s506a、s507が、グループ内の信号線となる。
(ステップ206)装置は、グループ内の信号線s506a、s507に故障値を伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s501および制御点PI501には0が設定され、信号線s506a、s507には故障値NDが伝搬する。検査系列T2は{P}={1,1,1,0,0,X,X,X}に更新される。
(ステップ111)ステップ206では矛盾が発生していないので、装置はステップ103へ進む。
【0111】
(ステップ103)装置は、信号線s507を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s507は観測点PO501に接続されており観測可能なので、装置はステップ19へ進む。
【0112】
以上の処理により、検査系列T1として{P}={X,0,X,X,X,X,X,X}が生成され、検査系列T2として{P}={1,1,1,0,0,X,X,X}が生成される。
【0113】
以上に示すように、第2の生成方法によれば、複数の信号線について一括して活性化、含意操作および正当化を行うことにより、処理時間を短縮することができる。
【0114】
なお、以上の説明では、装置はステップ201で回路変換を行うこととしたが、これに代えて、到達信号線の活性化、含意操作および正当化を行う際に、分岐の枝(または外部入力)から分岐点を経由せずに接続する分岐の幹(または外部出力)までにある部分回路を1つのグループとして扱うこととしてもよい。この方法でも、同じ効果が得られる。
【0115】
<第3の実施形態>
図11は、第3の生成方法を示すフロー図である。第3の生成方法は、第1の生成方法に対して、ステップ301および302を追加し、ステップ103をステップ303に置換したものである。第3の生成方法は、短い経路に含まれる分岐の枝を到達信号線の候補から予め除外しておくことを特徴とする。
【0116】
以下、テスト対象回路内のある点から別の点に至る経路の長さの最大値を、その2点間の最長距離という。また、テスト対象回路内の信号線について、各制御点から当該信号線を経由して各観測点に至る経路を考え、その経路の長さの最大値を、当該信号線の最長テスト経路長という。また、テスト対象回路内の制御点について、当該制御点から各観測点に至る経路を考え、その経路の長さの最大値を、当該制御点の最長テスト経路長という。なお、経路の長さは、回路の配線およびゲート遅延情報に基づく遅延時間や、経路上のゲート数や、経路上のビア数などに基づき算出される。
【0117】
第3の生成方法で初出のステップは、以下のとおりである。
(ステップ301)装置は、分岐の枝を到達候補信号線に含めるか否かを判断するための基準値を設定する。
(ステップ302)装置は、ステップ11で選択したテスト対象信号線から任意の観測点に至る経路上の各分岐の枝について、最長テスト経路長を算出する。この長さは、選択されたテスト対象信号線と分岐の幹の間の最長距離と、分岐の枝と任意の観測点の間の最長距離とを加算することにより求められる。
(ステップ303)装置は、ステップ103と同様に到達候補信号線を更新する。ただし、到達信号線の出力側に接続される信号線が分岐の枝である場合には、最長テスト経路長がステップ301で設定された基準値以上の分岐の枝だけが、到達候補信号線に含められる。
【0118】
図5に示すテスト対象回路に対して第3の生成方法を実行したときの処理を説明する。ここでは、信号線s9の立上り遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。
(ステップ301)装置は、到達候補信号線の基準値を4に設定する。
(ステップ302)図5に示すテスト対象回路では、テスト対象信号線s9から観測点PO1、PO2に至る経路上には、分岐の枝s10a、s10bが含まれている。ゲート段数で経路の長さを評価すると、テスト対象信号線s9と分岐の幹s10の間の最長距離は1、分岐の枝s10aと観測点PO1との間の最長距離は3、分岐の枝s10bと観測点PO2との間の最長距離は2である。したがって、分岐の枝s10a、s10bの最長テスト経路長は、それぞれ、4、3となる。
【0119】
(ステップ13〜16、101〜102)装置は、第1の生成方法と同じ処理を行う。検査系列T1は{P}={X,X,X,0,X,X,X}に更新され、検査系列T2は{P}={X,1,X,1,X,X,X}に更新される。
(ステップ303)装置は、信号線s9を到達信号線に設定する。到達信号線の出力側に接続される信号線が分岐の枝ではないので、装置は、信号線s10を到達候補信号線に設定する。
(ステップ104〜107、102)装置は、第1の生成方法と同じ処理を行う。特にステップ106では、装置は、信号線s10を到達信号線に設定する。
【0120】
(ステップ303)到達信号線s10は分岐の幹であり、到達信号線s10の出力側には信号線s10a、s10bが接続されている。ここで、分岐の枝s10aの最長テスト経路長は4で、ステップ301で設定された基準値以上である。一方、分岐の枝s10bの最長テスト経路長は3で、この基準値未満である。そこで、装置は、信号線s10aを到達候補信号線に含めるが、信号線s10bを到達候補信号線に含めない。このように装置は、信号線s10aを到達候補信号線に設定する。
(ステップ104〜106)到達候補信号線s10は1本かつ観測不可なので、装置は、信号線s10aを到達信号線に設定する。
【0121】
(ステップ107)装置は、到達信号線s10aの故障値Dを信号線s7へ伝搬させるために、活性化、含意操作および正当化を行う。これにより、信号線s6、s6a、s6bおよび制御点PI3には0が設定され、信号線s7には故障値Dが伝搬する。検査系列T2は{P}={X,1,0,1,X,X,X}に更新される。
【0122】
(ステップ102)ステップ107では矛盾が発生していないので、装置はステップ303へ進む。
(ステップ303)装置は、信号線s7を到達候補信号線に設定する。
(以降のステップ)装置は、第1の生成方法と同じ処理を行う。なお、第3の生成方法ではステップ103に代えてステップ303が実行されるが、到達信号線が分岐の枝でない場合、ステップ103の内容とステップ303の内容は同じである。
【0123】
以上の処理により、第1の生成方法と同様に、検査系列T1として{P}={X,X,X,0,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。
【0124】
以上に示すように、第3の生成方法によれば、短い経路に含まれる分岐の枝を到達信号線の候補から予め除外しておくことにより、処理時間を短縮することができる。
【0125】
<第4の実施形態>
第4の生成方法は、第1の生成方法(図4)において、ステップ100をステップ400(図12)に置換したものである。ステップ400は、ステップ100において、ステップ101、107、110をそれぞれステップ401〜403に置換したものである。第4の生成方法は、ロバスト条件に従い活性化を行うことを特徴とする。ステップ400では、検査系列T2に加えて、ステップ14で生成された検査系列T1が更新される。
【0126】
第4の生成方法で初出のステップは、以下のとおりである。
(ステップ401)装置は、テスト対象信号線に故障値を設定し、設定した故障値を出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ロバスト条件に従い活性化を行う。
(ステップ402)装置は、到達信号線の出力側へゲート1段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ロバスト条件に従い活性化を行う。その後、装置はステップ102へ進む。
(ステップ403)装置は、ステップ402と同じ処理を行う。その後、装置はステップ111へ進む。
【0127】
図13に示すテスト対象回路に対して第4の生成方法を実行したときの処理を説明する。ここでは、信号線s25の立下り遷移をテスト対象とし、{PI21,PI22,PI23,PI24,PI25,PI26,PI27}を{P}と記載する。
(ステップ13)装置は、テスト対象信号線s25に初期値1を設定する。
(ステップ14)装置は、テスト対象信号線s25に初期値1を設定するために、制御点PI22に1を設定する。検査系列T1は{P}={X,1,X,X,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s37に故障値Dを設定する。
【0128】
(ステップ401)装置は、テスト対象信号線s37に故障値Dを設定し、設定した故障値Dを信号線s30へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、制御点PI22には0が設定され、信号線s29および制御点PI24にはS1が設定され、信号線s30には故障値Dが伝搬する。検査系列T1は{P}={X,1,X,1,X,X,X}検査系列T2は{P}={X,0,X,1,X,X,X}に更新される。
(ステップ102)ステップ401では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s30(観測不可)を到達候補信号線に設定した後、信号線s30を到達信号線に設定する。
(ステップ402)到達信号線s30は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ102へ進む。
【0129】
(ステップ102)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜104)信号線s30は分岐の幹であるので、装置は、信号線s30a、s30bを到達候補信号線に設定し、ステップ108へ進む。
【0130】
(ステップ108)装置は、到達候補信号線s30a、s30bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s30aの最長観測距離は3、信号線s30bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線s30aを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ403へ進む。
(ステップ403)装置は、到達信号線s30aの故障値Dを信号線s27へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、P23にS1が設定され、信号線s27には故障値NDが伝搬する。検査系列T1は{P}={X,1,1,1,X,X,X}、検査系列T2は{P}={X,0,1,1,X,X,X}に更新される。
(ステップ111)ステップ403では矛盾が発生していないので、装置はステップ103へ進む。
【0131】
(ステップ103〜106)装置は、信号線s27(観測不可)を到達候補信号線に設定した後、信号線s27を到達信号線に設定する。
(ステップ402)装置は、到達信号線s27の故障値NDを信号線s28へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s31および制御点PI25にはS0が設定され、信号線s28にはNDが伝搬する。検査系列T1は{P}={X,1,1,1,0,X,X}、検査系列T2は{P}={X,0,1,1,0,X,X}に更新される。
【0132】
(ステップ102)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s28(観測不可)を到達候補信号線に設定した後、信号線s28を到達信号線に設定する。
(ステップ402)装置は、到達信号線s28の故障値Dを信号線s24へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s23、s22、s21および制御点PI21にはS0が設定され、信号線s24には故障値Dが伝搬する。検査系列T2は{P}={0,1,1,1,0,X,X}、検査系列T2は{P}={X,0,1,1,0,X,X}に更新される。
【0133】
(ステップ102)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)装置は、信号線s24を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s24は観測点PO21に接続されており観測可能なので、装置はステップ19へ進む。
【0134】
以上の処理により、検査系列T1として{P}={0,1,1,1,0,X,X}が生成され、検査系列T2として{P}={X,0,1,1,0,X,X}が生成される。なお、上記の例では、ロバスト条件での活性化、含意操作および正当化を行うときに、検査系列T1は更新されていないが、一般的には、ロバスト条件での活性化、含意操作および正当化を行うときに、検査系列T1は更新される。
【0135】
以上に示すように、第4の生成方法によれば、ロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延故障を、他の信号線上に遅延故障が発生したか否かにかかわらず検査することができる。
【0136】
<第5の実施形態>
第5の生成方法は、第1の生成方法(図4)において、ステップ100をステップ500(図14)に置換したものである。ステップ500は、ステップ100において、ステップ101、107、110をそれぞれステップ501〜503に置換したものである。第5の生成方法は、ノンロバスト条件に従い活性化を行うことを特徴とする。
【0137】
第5の生成方法で初出のステップは、以下のとおりである。
(ステップ501)装置は、テスト対象信号線に故障値を設定し、設定した故障値を出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ノンロバスト条件に従い活性化を行う。
(ステップ502)装置は、到達信号線の出力側へゲート1段分だけ故障値を伝搬させるために、活性化、含意操作および正当化を行う。この際、装置は、ノンロバスト条件に従い活性化を行う。その後、装置はステップ102へ進む。
(ステップ503)装置は、ステップ502と同じ処理を行う。その後、装置はステップ111へ進む。
【0138】
図5に示すテスト対象回路に対して第5の生成方法を実行したときの処理を説明する。ここでは、信号線s6の立下り遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。
(ステップ13)装置は、テスト対象信号線s6に初期値1を設定する。
(ステップ14)装置は、テスト対象信号線s6に初期値1を設定するために、制御点PI3に1を設定する。検査系列T1は{P}={X,X,1,X,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s6に故障値Dを設定する。
【0139】
(ステップ501)装置は、テスト対象信号線s6に故障値Dを設定するために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s6および制御点PI3には0が設定される。検査系列T2は{P}={X,X,0,X,X,X,X}となる。
(ステップ102)ステップ501では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜104)信号線s6は分岐の幹であるので、装置は、信号線s6a、s6bを到達候補信号線に設定し、ステップ108へ進む。
【0140】
(ステップ108)装置は、到達候補信号線s6a、s6bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s6aの最長観測距離は2、信号線s6bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s6bを到達信号線として選択する。
(ステップ109)ステップ108で矛盾が発生していないので、装置はステップ503へ進む。
(ステップ503)装置は、到達信号線s6bの故障値Dを信号線s7へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s10aにはU0が設定され、信号線s7には故障値Dが伝搬する。また、信号線s9、s5bおよび制御点PI2、PI4にはU1が設定される。検査系列T2は{P}={X,1,0,1,X,X,X}に更新される。
(ステップ111)ステップ503では矛盾が発生していないので、装置はステップ103へ進む。
【0141】
(ステップ103〜106)装置は、信号線s7(観測不可)を到達候補信号線に設定した後、信号線s7を到達信号線に設定する。
(ステップ502)装置は、テスト対象信号線s7の故障値Dを信号線s8へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s11および制御点PI5にはU0が設定される。検査系列T2は{P}={X,1,0,1,0,X,X}に更新される。
【0142】
(ステップ102)ステップ502では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s8(観測不可)を到達候補信号線に設定した後、信号線s8を到達信号線に設定する。
(ステップ502)装置は、テスト対象信号線s8の故障値NDを信号線s4へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s3、s2、s1および制御点PI1にはU0が設定され、信号線s4には故障値Dが伝搬する。検査系列T2は{P}={0,1,0,1,0,X,X}に更新される。
【0143】
(ステップ102)ステップ502では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)装置は、信号線s4を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)信号線s4は観測点PO1に接続されており観測可能であるので、装置はステップ19へ進む。
【0144】
以上の処理により、検査系列T1として{P}={X,X,1,X,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。
【0145】
以上に示すように、第5の生成方法によれば、ノンロバスト条件に従い活性化を行うことにより、テスト対象信号線を含む経路上の遅延の影響を、より長い経路を利用して検出することができる。
【0146】
<第6の実施形態>
第6の生成方法は、第1の生成方法(図4)において、ステップ100をステップ600(図15)に置換したものである。ステップ600は、ステップ400(図12)に対してステップ601〜609を追加したものである。第6の生成方法は、ロバスト条件に従い活性化を行い、ある分岐点で選択可能なすべての到達候補信号線についてロバスト条件による活性化に失敗した場合には、ノンロバスト条件に従い活性化を行うことを特徴とする。ステップ600では、検査系列T2に加えて、ステップ14で生成された検査系列T1が更新される。
【0147】
第6の生成方法で初出のステップは、以下のとおりである。
(ステップ601)装置は、ステップ402で矛盾が発生した場合はステップ602へ進み、それ以外の場合はステップ103へ進む。
(ステップ602)装置は、ステップ502と同じ処理を行う。
(ステップ603)装置は、後で参照するために、その時点の到達候補信号線を保持する。
(ステップ604)装置は、ステップ603で保持した信号線を到達候補信号線に再設定する。
(ステップ605)装置は、ステップ108と同じ処理を行う。
(ステップ606)装置は、ステップ605で到達信号線を選択した場合にはステップ607へ進み、それ以外の場合はステップ11へ進む。
(ステップ607)装置は、ステップ502と同じ処理を行う。
(ステップ608)装置は、ステップ607で矛盾が発生した場合はステップ609へ進み、それ以外の場合はステップ103へ進む。
(ステップ609)装置は、ステップ112と同じ処理を行う。その後、装置はステップ605へ進む。
【0148】
図16に示すテスト対象回路に対して第6の生成方法を実行したときの処理を説明する。ここでは、信号線s1502の立下り遷移をテスト対象とし、{PI1501,PI1502,PI1503,PI1504}を{P}と記載する。
(ステップ13)装置は、信号線s1502に初期値1を設定する。
(ステップ14)装置は、テスト対象信号線s1502に初期値1を設定するために、制御点PI1502に1を設定する。検査系列T1は{P}={X,1,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s1502に故障値Dを設定する。
【0149】
(ステップ401)装置は、テスト対象信号線s1502に故障値Dを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1502および制御点PI1502には0が設定される。検査系列T2は{P}={X,0,X,X}に更新される。
(ステップ102)ステップ401では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜104)信号線s1502は分岐の幹であるので、装置は信号線s1502a、s1502bを到達候補信号線に設定し、ステップ603へ進む。
【0150】
(ステップ603)装置は、到達候補信号線s1502a、s1502bを保持する。
(ステップ108)装置は、到達候補信号線s1502a、s1502bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s1502aの最長観測距離は3、信号線s1502bの最長観測距離は4である。そこで、装置は、最長観測距離が最も長い到達候補信号線s1502bを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ403へ進む。
(ステップ403)装置は、到達信号線s1502bの故障値Dを信号線s1505へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1503および制御点PI1503にはS1が設定され、信号線s1505には故障値Dが伝搬する。検査系列T1は{P}={X,1,1,X}に更新され、検査系列T2は{P}={X,0,1,X}に更新される。
(ステップ111)ステップ403では矛盾が発生していないので、装置はステップ103へ進む。
【0151】
(ステップ103〜106)装置は、信号線s1505(観測不可)を到達候補信号線に設定した後、信号線s1505を到達信号線に設定する。
(ステップ402)到達信号線s1505は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ601へ進む。
(ステップ601)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
【0152】
(ステップ103〜104)信号線s1505は分岐の幹であるので、装置は、信号線s1505a、s1505bを到達候補信号線に設定し、ステップ603へ進む。
(ステップ603)装置は、到達候補信号線s1505a、s1505bを保持する。
【0153】
(ステップ108)装置は、到達候補信号線s1505a、s1505bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s1505aの最長観測距離は3、信号線s1505bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線s1505aを到達信号線として選択する。信号線s1505aに伝搬した故障値は必ず信号線s1508に伝搬するので、装置は、信号線s1505aを選択することにより、結果として、信号線s1508を到達信号線として選択したことになる。信号線s1508には故障値NDが伝搬する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ403へ進む。
(ステップ403)装置は、到達信号線s1508の故障値NDを信号線s1509へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1504aおよび制御点PI1504にはS0が設定され、信号線s1509には故障値NDが伝搬する。検査系列T1は{P}={X,1,1,0}に更新され、検査系列T2は{P}={X,0,1,0}に更新される。
(ステップ111)ステップ403では矛盾が発生していないので、装置はステップ103へ進む。
【0154】
(ステップ103〜106)装置は、信号線s1509(観測不可)を到達候補信号線に設定した後、信号線s1509を到達信号線に設定する。
(ステップ402)到達信号線s1509は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ601へ進む。
(ステップ601)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
【0155】
(ステップ103〜104)信号線s1509は分岐の幹であるので、装置は信号線s1509a、1509b、1509cを到達候補信号線に設定し、ステップ603へ進む。
(ステップ603)装置は、到達候補信号線s1509a、s1509b、1509cを保持する。
【0156】
(ステップ108)装置は、到達候補信号線s1509a、1509b、1509cの最長観測距離を求める。ゲート段数で観測距離を評価すると、これら3本の到達候補信号線の最長観測距離はいずれも1である。3本の到達候補信号線のいずれを選択してもよいので、装置は、到達候補信号線s1509aを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s1509aの故障値NDを信号線s1511へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列T1における制御点PI1502の値は1に、信号線s1507の値は1に決定されている。したがって、信号線s1509aの故障値NDを信号線s1511に伝搬させるために、装置が信号線s1507にS0を設定すると、矛盾が発生する。
(ステップ111)ステップ206で矛盾が発生したので、装置はステップ112へ進む。
(ステップ112)装置は、到達候補信号線から到達信号線s1509aを除外する。この時点で、到達候補信号線は、信号線s1509b、s1509cとなる。その後、装置はステップ108へ進む。
【0157】
(ステップ108)装置は、到達候補信号線s1509b、s1509cの中から任意に到達候補信号線s1509bを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s1509bの故障値NDを信号線s1512へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列T1における制御点PI1502、PI1503および信号線s1510の値は1に決定されている。したがって、信号線s1509bの故障値NDを信号線s1512に伝搬させるために、装置が信号線s1510aにS0を設定すると、矛盾が発生する。
(ステップ111)ステップ206で矛盾が発生したので、装置はステップ112へ進む。
(ステップ112)装置は、到達候補信号線から到達信号線s1509bを除外する。この時点で、到達候補信号線は、信号線s1509cのみとなる。その後、装置はステップ108へ進む。
【0158】
(ステップ108)装置は、到達候補信号線s1509cを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s1509cの故障値NDを信号線s1513へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、上述したように、このステップが実行される前に、検査系列T1を与えるときの制御点PI1510の値は1に決定されている。したがって、信号線s1509cの故障値NDを信号線s1513に伝搬させるために、装置が信号線s1510bにS0を設定すると、矛盾が発生する。
(ステップ111)ステップ110で矛盾が発生したので、装置はステップ112へ進む。
(ステップ112)装置は、到達候補信号線から到達信号線s1509cを除外する。この時点で、到達候補信号線はなくなる。その後、装置はステップ108へ進む。
【0159】
(ステップ108)到達候補信号線がないので、装置は、到達候補信号線を到達信号線として選択しない。
(ステップ109)ステップ108で到達信号線を選択しなかったので、装置はステップ604へ進む。
(ステップ604)装置は、ステップ603で保持した信号線s1509a、1509b、1509cを到達候補信号線に再設定する。
【0160】
(ステップ605)装置は、到達候補信号線s1509a、1509b、1509cの中から任意に到達候補信号線s1509aを到達信号線として選択する。
(ステップ606)ステップ605で到達信号線を選択したので、装置はステップ607へ進む。
(ステップ607)装置は、到達信号線s1509aの故障値NDを信号線s1511へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1507にはU0が設定され、制御点PI1501にはU1が設定され、信号線s1511には故障値NDが伝搬する。検査系列T1は{P}={X,1,1,0}に更新され、検査系列T2は{P}={1,0,1,0}に更新される。
(ステップ608)ステップ607では矛盾が発生していないので、装置はステップ103へ進む。
【0161】
(ステップ103)装置は、信号線s1511を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s1511は観測点PO1501に接続されており観測可能なので、装置はステップ19へ進む。
【0162】
以上の処理により、検査系列T1として{P}={X,1,1,0}が生成され、検査系列T2として{P}={1,0,1,0}が生成される。
【0163】
以上に示すように、第6の生成方法によれば、ロバスト条件に従い活性化を行い、ある分岐点においてすべての到達候補信号線についてロバスト条件による活性化に失敗した場合には、ノンロバスト条件に従い活性化を行うことにより、ロバスト条件では検査できない故障を検査できるテストパターンを生成することができる。
【0164】
<第7の実施形態>
第7の生成方法は、第1の生成方法(図4)において、ステップ100をステップ700(図17)に置換したものである。ステップ700は、ステップ600(図15)に対して、ステップ701を追加し、ステップ111、112、603〜606を削除したものである。第7の生成方法は、各到達候補信号線について、まずロバスト条件に従い活性化を行い、それに失敗した場合には、ノンロバスト条件に従い活性化を行うことを特徴とする。ステップ700では、検査系列T2に加えて、ステップ14で生成された検査系列T1が更新される。
【0165】
第7の生成方法で初出のステップは、以下のとおりである。
(ステップ701)装置は、ステップ403で矛盾が発生した場合はステップ607へ進み、それ以外の場合はステップ103へ進む。
【0166】
図5に示すテスト対象回路に対して第7の生成方法を実行したときの処理を説明する。ここでは、信号線s6の立下り遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。
(ステップ13〜16)装置は、第5の生成方法と同じ処理を行う。検査系列T1は{P}={X,X,1,X,X,X,X}に更新される。
【0167】
(ステップ401)装置は、テスト対象信号線s6に故障値Dを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s6、s6a、s6bにはU0が設定され、制御点PI3には0が設定される。検査系列T2は{P}={X,X,0,X,X,X,X}に更新される。
(ステップ102)ステップ501では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜104)信号線s6は分岐の幹であるので、装置は、信号線s6a、s6bを到達候補信号線に設定し、ステップ108へ進む。
【0168】
(ステップ108)装置は、到達候補信号線s6a、s6bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s6aの最長観測距離は2、信号線s6bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s6bを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ403へ進む。
(ステップ403)装置は、到達信号線s6bの故障値Dを信号線s27へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s10aにはU0が設定され、制御点PI2、PI4にはU1が設定され、信号線s7には故障値Dが伝搬される。検査系列T2は{P}={X,1,0,1,X,X,X}に更新される。
(ステップ701)ステップ403では矛盾が発生していないので、装置はステップ103へ進む。
【0169】
(ステップ103〜106)装置は、信号線s7(観測不可)を到達候補信号線に設定した後、信号線s7を到達信号線に設定する。
(ステップ402)装置は、到達信号線s7の故障値Dを信号線s8へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s11および制御点PI5にはU0が設定され、信号線s8には故障値NDが伝搬する。検査系列T2は{P}={X,1,0,1,0,X,X}に更新される。
(ステップ102)ステップ402では矛盾が発生していないので、装置はステップ103へ進む。
【0170】
(ステップ103〜104)信号線s8は分岐の幹であるので、装置は、信号線s8a、s8bを到達候補信号線に設定し、ステップ108へ進む。
【0171】
(ステップ108)装置は、到達候補信号線s8a、s8bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s8aの最長観測距離は1、信号線s8bの最長観測距離は0である。そこで、装置は、最長観測距離が最も長い到達候補信号線s8bを到達信号線として選択する。
(ステップ109)ステップ108で到達信号線を選択したので、装置はステップ403へ進む。
(ステップ403)装置は、到達信号線s8aの故障値NDを信号線s4へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、検査系列T1における制御点PI3および信号線s3の値は1に決定されている。したがって、信号線s8bの故障値NDを信号線s4へ伝搬させるために、装置が信号線s3にS0を設定すると、矛盾が発生する。
(ステップ701)ステップ701で矛盾が発生したので、装置はステップ607へ進む。
【0172】
(ステップ607)装置は、到達信号線s8bの故障値NDを信号線s4へ伝搬させるために、ノンロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1、s2、s3および制御点PI1にはU0が設定され、信号線s4には故障値NDが伝搬する。検査系列T2は{P}={0,1,0,1,0,X,X}に更新される。
(ステップ102)ステップ608では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103)装置は、信号線s4を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s4は観測点PO1に接続されており観測可能なので、装置はステップ19へ進む。
【0173】
以上の処理により、検査系列T1として{P}={X,X,1,X,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。
【0174】
以上に示すように、第7の生成方法では、各到達候補信号線について、まずロバスト条件に従い活性化が行われ、それに失敗した場合には、ノンロバスト条件に従い活性化が行われる。このようにロバスト条件に従った活性化を優先して実行することにより、遅延故障の検出経路が同じ場合でも、高品質のテストパターンを生成することができる。
【0175】
なお、第6および第7の生成方法では、装置は、ロバスト条件で活性化できない場合には、ノンロバスト条件で活性化することとした。これに代えて、装置は、ロバスト条件で活性化できない場合には、ノンロバスト条件に代えて、図46(a)に例示される経路活性化表および含意表に従って活性化を行ってもよい。また、装置は、ロバスト条件でもノンロバスト条件でも活性化できない場合には、図46(a)に例示される経路活性化表および含意表に従って活性化を行ってもよい。
【0176】
<第8の実施形態>
第8の生成方法は、第1の生成方法(図4)において、ステップ100をステップ800(図18)に置換したものである。ステップ800は、ステップ100に対して、ステップ801、802、805〜810を追加し、ステップ109、111をステップ803、804に置換したものである。第8の生成方法は、ある分岐点ですべての到達候補信号線について活性化および正当化に失敗した場合には、直前に選択が行われた分岐点まで処理を戻す(バックトラックする)ことを特徴とする。
【0177】
第8の生成方法で初出のステップは、以下のとおりである。以下のステップでは、遷移経路集合と不到達信号線とが使用される。これら値の初期値は、空(要素なし)である。
(ステップ801)装置は、ステップ107で矛盾が発生した場合にはステップ805へ進み、それ以外の場合にはステップ802へ進む。
(ステップ802)装置は、その時点の到達信号線を遷移経路集合に追加する。その後、装置はステップ103へ進む。
(ステップ803)装置は、ステップ108で信号線を選択した場合にはステップ110へ進み、それ以外の場合にはステップ805へ進む。
(ステップ804)装置は、ステップ110で矛盾が発生した場合にはステップ112へ進み、それ以外の場合にはステップ802へ進む。
【0178】
(ステップ805)装置は、到達信号線から故障値の伝搬経路を遡った場合に、到達信号線と最初に現れる分岐の枝との間(両端の信号線を含む)にある信号線(以下、伝搬失敗信号線という)を求め、伝搬失敗信号線を不到達信号線に追加する。
(ステップ806)装置は、伝搬失敗信号線に故障値を伝搬するために割り当てた各信号線の値を元に戻す。
(ステップ807)装置は、伝搬失敗信号線の入力側信号線のうち、遷移経路集合に含まれる信号線を到達信号線に設定する。
(ステップ808)装置は、テスト対象信号線ではない到達信号線がある場合には、ステップ809へ進み、それ以外の場合にはステップ11へ進む。
(ステップ809)装置は、ステップ807で設定された到達信号線の到達候補信号線を求め、不到達信号線に含まれない到達候補信号線がある場合にはステップ810へ進み、それ以外の場合にはステップ805へ進む。
(ステップ810)装置は、不到達信号線に含まれる信号線を到達候補信号線から削除する。その後、装置はステップ103へ進む。
【0179】
図8に示すテスト対象回路に対して第8の生成方法を実行したときの処理を説明する。ここでは、信号線s504の立上り遷移をテスト対象とし、{PI501,PI502,PI503,PI504,PI505,PI506,PI507,PI508}を{P}と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
(ステップ13)装置は、テスト対象信号線s504に初期値0を設定する。
(ステップ14)装置は、テスト対象信号線s504に初期値0を設定するために、制御点PI502に0を設定する。検査系列T1は{P}={X,0,X,X,X,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s504に故障値NDを設定する。
【0180】
(ステップ101)装置は、テスト対象信号線s504に故障値NDを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、検査系列T2を与えるときの信号線s502および制御点PI502の値には1が設定される。また、信号線s503および制御点PI503にはU1が設定される。検査系列T2は{P}={X,1,1,X,X,X,X,X}に更新される。
(ステップ102)ステップ101では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s504(観測不可)を到達候補信号線に設定した後、信号線s504を到達信号線に設定する。
【0181】
(ステップ107)装置は、到達信号線s504の故障値NDを信号線s505へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s510aおよび制御点PI504、PI505にはS0が設定され、信号線s505には故障値NDが伝搬する。検査系列T1は{P}={X,0,X,0,0,X,X,X}に更新され、検査系列T2は{P}={X,1,1,0,0,X,X,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s504を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0182】
(ステップ103〜106)装置は、信号線s505(観測不可)を到達候補信号線に設定した後、信号線s505を到達信号線に設定する。
(ステップ107)到達信号線s505は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ801へ進む。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s505を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0183】
(ステップ103〜104)信号線s505は分岐の幹であるので、装置は信号線s505a、s505bを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s505a、s505bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s505aの最長観測距離は4、信号線s505bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s505aを到達信号線として選択する。
(ステップ803)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s505aの故障値NDを信号線s506へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、信号線s510にはS0が設定されおり、信号線s511にはS1が設定されている。このため、新たに信号線に値を設定しなくても、信号線s506には故障値NDが伝搬する。
(ステップ804)ステップ110では矛盾が発生していないので、装置はステップ802へ進む。
【0184】
(ステップ802)装置は、到達信号線s505aを遷移経路集合に追加する。その後、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s506(観測不可)を到達候補信号線に設定した後、信号線s506を到達信号線に設定する。
(ステップ107)到達信号線s506は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ801へ進む。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s506を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0185】
(ステップ103〜104)信号線s506は分岐の幹であるので、装置は信号線s506a、s506bを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s506a、s506bの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s506aの最長観測距離は1、信号線s505bの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s506bを到達信号線として選択する。
(ステップ803)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s506bの故障値NDを信号線s513へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、信号線s510cにはS0が設定されている。このため、新たに信号線に値を設定しなくても、信号線s513には故障値NDが伝搬する。
(ステップ804)ステップ110では矛盾が発生していないので、装置はステップ802へ進む。
【0186】
(ステップ802)装置は、到達信号線s506bを遷移経路集合に追加する。その後、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s513(観測不可)を到達候補信号線に設定し、信号線s513を到達信号線に設定する。
(ステップ107)装置は、到達信号線s513の故障値NDを信号線s514へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行される前に、制御点PI505および信号線s519aにはS0が設定されている。したがって、信号線s513の故障値NDを信号線s514に伝搬させるために、装置が信号線s519aにU1を設定すると、矛盾が発生する。
(ステップ801)ステップ107で矛盾が発生したので、装置はステップ805へ進む。
【0187】
(ステップ805)この時点で、到達信号線s513から故障値の伝搬経路を遡った場合に、到達信号線s513と最初に現れる分岐の枝s506bとの間には、信号線s513、s506bが存在する。そこで、装置は、これら伝搬失敗信号線s513、s506bを不到達信号線に追加する。
(ステップ806)装置は、伝搬失敗信号線s513、s506bに故障値を伝搬させるために設定した信号線の値を元に戻す。この例では、伝搬失敗信号線s513、s506bに故障値を伝搬させるために値が設定された信号線はないので、このステップでは何も行われない。
(ステップ807)装置は、伝搬失敗信号線s513、s506の入力側信号線のうち、遷移経路集合に含まれる信号線s506を到達信号線に設定する。
【0188】
(ステップ808)テスト対象信号線s504ではない到達信号線があるので、装置はステップ809へ進む。
(ステップ809)装置は、到達信号線s506の出力側に接続される信号線s506a、s506bを到達候補信号線に設定する。このうち信号線s506aは不到達信号線に含まれていないので、装置はステップ810へ進む。
(ステップ810)装置は、不到達信号線に含まれる信号線s606bを、到達候補信号線から削除する。その結果、到達候補信号線には、信号線s606aのみが含まれる。その後、装置はステップ103へ進む。
【0189】
(ステップ103〜106)装置は、信号線s506a(観測不可)を到達候補信号線に設定し、信号線s506aを到達信号線に設定する。
(ステップ107)装置は、到達信号線s506aの故障値NDを信号線s507へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s501および制御点PI501にはS0が設定される。検査系列T1は{P}={0,0,X,0,0,X,X,X}に更新され、検査系列T2は{P}={0,1,1,0,0,X,X,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s506aを遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0190】
(ステップ103)装置は、信号線s507を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s507は観測点PO1に接続されており観測可能なので、装置はステップ19へ進む。
【0191】
以上の処理により、検査系列T1として{P}={0,0,X,0,0,X,X,X}が生成され、検査系列T2として{P}={0,1,1,0,0,X,X,X}が生成される。
【0192】
以上に示すように、第8の生成方法によれば、ある分岐点ですべての到達候補信号線について活性化および正当化に失敗した場合には、直前に選択が行われた分岐点までバックトラックすることにより、バックトラックなしでは生成できないテストパターンを生成することができる。
【0193】
<第9の実施形態>
第9の生成方法は、第3の生成方法(図11)において、ステップ300をステップ900(図19)に置換したものである。ステップ900は、ステップ800(図18)において、ステップ103、809をそれぞれステップ303、901に置換したものである。第9の生成方法は、所定の基準を満たす直近の分岐点までバックトラックすることを特徴とする。
【0194】
第9の生成方法で初出のステップは、以下のとおりである。
(ステップ901)装置は、ステップ807で設定された到達信号線の到達候補信号線を求め、不到達信号線に含まれず、かつ、所定の基準を満たす到達候補信号線がある場合にはステップ810へ進み、それ以外の場合はステップ302へ進む。なお、ここでは、到達候補信号線の最長テスト経路長がステップ301で設定された基準値以上である場合に、当該到達候補信号線は基準を満たすという。
【0195】
図8に示すテスト対象回路に対して第9の生成方法を実行したときの処理を説明する。ここでは、信号線s504の立上り遷移をテスト対象とし、{PI501,PI502,PI503,PI504,PI505,PI506,PI507,PI508}を{P}と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
(ステップ301)装置は、到達信号線の基準値を4に設定する。
(ステップ302)図8に示すテスト対象回路では、テスト対象信号線s504から観測点PO501、PO502、PO503に至る経路上には、分岐の枝s505a、s505b、s506a、s506bが含まれている。ゲート段数で経路の長さを評価すると、テスト対象信号線s504から分岐の幹s505までの最長距離は1、テスト対象信号線s504から分岐の幹s506までの最長距離は2、分岐の枝s505a、505b、506a、506bから3つの観測点までの最長距離は、それぞれ、4、3、1、3である。したがって、分岐の枝s505a、s505b、s506a、s506bの最長テスト経路長は、それぞれ、5、4、3、5となる。
【0196】
第9の生成方法では、最長テスト経路長がステップ301で設定された基準値以上の分岐の枝だけが、基準を満たす分岐の枝として扱われ、到達候補信号線として設定される。したがって、この例では、上記4本の分岐の枝のうち、分岐の枝s506aは、ステップ303、901では、到達候補信号線として設定されない。ステップ302以降の処理は、このような条件下で実行される。このため、第9の生成方法によれば、以下に示すように、第8の生成方法とは異なるテストパターンが生成される。
【0197】
第8の生成方法では、分岐の枝s505a、s505b、s506a、s506bは、故障値を伝搬させる経路として選択され得る。装置は、信号線s504に設定された故障値を伝搬させる際に、まず分岐の枝s505a、505bのうちから、最長テスト経路長が長いほうの分岐の枝s505aを選択し、次に分岐の枝s506a、s506bのうちから、最長テスト経路長が長いほうの分岐の枝s506bを選択する。分岐の枝s506bより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。そこで、装置は、バックトラック処理(ステップ805〜810)を行い、直前に選択を行った分岐点までバックトラックする。その後、装置は、故障値を分岐の枝s506a経由で観測点PO501へ伝搬させる。
【0198】
これに対して、第9の生成方法では、分岐の枝s505a、s505b、s506bは、故障値を伝搬させる経路として選択され得るが、分岐の枝s506aは、故障値を伝搬させる経路として選択され得ない。装置は、信号線s504に設定された故障値を伝搬させる際に、まず分岐の枝s505a、505bのうちから、最長テスト経路長が長いほうの分岐の枝s505aを選択し、次に、選択し得る唯一の分岐の枝s506bを選択する。分岐の枝s506bより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。そこで、装置は、バックトラック処理(ステップ805〜808、901、810)を行う。この際ステップ901では、装置は、不到達信号線に含まれず、かつ、最長テスト経路長が基準値4以上の到達候補信号線として、分岐の枝s505bを選択する。その後、装置は、故障値を分岐の枝s505b経由で観測点PO503へ伝搬させる。
【0199】
装置は、信号線s505の故障値NDを分岐の枝s505b経由で観測点PO503へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。なお、これら3つの処理は、故障値をゲート1段分だけ伝搬させるたびに行われる。これにより、信号線s540、s524にはそれぞれS0、U1が設定され、制御点PI507にはS0が設定される。
【0200】
以上の処理により、検査系列T1として{P}={X,0,X,0,0,X,0,X}が生成され、検査系列T2として{P}={0,1,1,0,0,X,0,X}が生成される。
【0201】
以上に示すように、第9の生成方法によれば、バックトラックを行う際に戻り先を制限することにより、処理時間を短縮することができる。
【0202】
<第10の実施形態>
第10の生成方法は、第3の生成方法(図11)において、ステップ300をステップ1000(図20)に置換したものである。ステップ1000は、ステップ900(図19)において、ステップ807をステップ1001および1002に置換し、ステップ901をステップ1003に置換し、ステップ810を削除したものである。第10の生成方法は、選択されていない分岐の枝を含む最長テスト経路長が最も長い分岐点までバックトラックすることを特徴とする。
【0203】
第10の生成方法で初出のステップは、以下のとおりである。
(ステップ1001)装置は、ステップ11で選択したテスト対象信号線から任意の観測点に至る経路上の各分岐の枝について、最長テスト経路長を算出する。ただし、不到達信号線を含む経路は、最長テスト経路長の算出には使用されないものとする。
(ステップ1002)装置は、遷移経路集合に含まれる分岐の幹のうち、ステップ1001で算出された最長テスト経路長が最長の分岐の枝に接続されたものを、到達信号線に設定する。
(ステップ1003)装置は、到達信号線の分岐の枝の中で、最長テスト経路長が最長で、かつ、所定の基準を満たすものがある場合にはステップ303へ進み、それ以外の場合にはステップ805へ進む。なお、ここでは、到達候補信号線の最長テスト経路長がステップ301で設定された基準値以上である場合に、当該到達候補信号線は基準を満たすという。
【0204】
図8に示すテスト対象回路に対して第10の生成方法を実行したときの処理を説明する。ここでは、信号線s504の立上り遷移をテスト対象とし、{PI501,PI502,PI503,PI504,PI505,PI506,PI507,PI508}を{P}と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行い、ステップ301では到達信号線の基準値を4に設定するものとする。
【0205】
第10の生成方法は、バックトラック処理を除き、第9の生成方法と同じである。したがって、第10の生成方法でも、第9の生成方法と同様に、故障値を伝搬させる経路として選択され得るのは、分岐の枝s505a、s505b、s506bに限られる。装置は、信号線s504に設定された故障値を伝搬させる際に、まず分岐の枝s505a、505bのうちから、最長テスト経路長が長いほうの分岐の枝s505aを選択し、次に、選択し得る唯一の分岐の枝s506bを選択する。分岐の枝s506bより後段側のゲートへ故障値を伝搬させるために、装置が活性化および正当化を行うと、矛盾が発生する。ここで、装置は、第9の生成方法とは異なるバックトラック処理(ステップ805、806、808、1001〜1003)を行う。
【0206】
(ステップ1001)この時点で不到達信号線には、信号線s513、s506bが含まれている。また、図8に示すテスト対象回路では、テスト対象信号線s504から観測点に至る経路上には、分岐の枝s505a、s505b、s506a、s506bが含まれている。そこで、装置は、これら4本の分岐の枝について、信号線s513、s506bを含まない経路だけを考慮した最長テスト経路長を算出する。これにより、分岐の枝s505a、s505b、s506a、s506bの最長テスト経路長は、それぞれ、3、4、3、0となる。
(ステップ1002)装置は、遷移経路集合に含まれる分岐の幹のうち、ステップ1001で算出された最長テスト経路長が最長の分岐の枝に接続されたものとして、分岐の幹s505を到達信号線に設定する。
(ステップ808)テスト対象信号線s504でない到達信号線があるので、装置はステップ1003へ進む。
(ステップ1003)このステップが実行される時点で、到達信号線s505の分岐の枝s505a、505bの中で、最長テスト経路長が最長であるのは分岐の枝s505bである。また、分岐の枝s505bの最長テスト経路長は、基準値4以上であり基準を満たす。そこで、装置は、ステップ103へ進む。
【0207】
その後、装置は、故障値を分岐の枝s505b経由で観測点PO503へ伝搬させる。したがって、第10の生成方法によれば、第9の生成方法と同様に、検査系列T1として{P}={X,0,X,0,0,X,0,X}が生成され、検査系列T2として{P}={0,1,1,0,0,X,0,X}が生成される。
【0208】
以上に示すように、第10の生成方法によれば、バックトラックを行う際の戻り先を制限し、より長い経路を優先的に選択することにより、テスト対象信号線の遅延の影響をより長い経路で伝搬して検出することができる。
【0209】
<第11の実施形態>
第11の生成方法は、第1の生成方法(図4)において、ステップ100をステップ1100(図21)に置換したものである。ステップ1100は、ステップ800(図18)からステップ806を削除したものである。第11の生成方法は、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を保持したままにすることを特徴とする。
【0210】
図22に示すテスト対象回路に対して第11の生成方法を実行したときの処理を説明する。ここでは、信号線s1903の立下り遷移をテスト対象とし、{PI1901,PI1902,PI1902,PI1903,PI1904,PI1905,PI1906,PI1907,PI1908}を{P}と記載する。なお、以下に示す例では、装置は、ロバスト条件に従い活性化を行うものとする。
(ステップ13)装置は、テスト対象信号線s1903に初期値1を設定する。
(ステップ14)装置は、テスト対象信号線s1903に初期値1を設定するために、制御点PI1903に1を設定する。検査系列T1は{P}={X,X,1,X,X,X,X,X}に更新される。
(ステップ15)検査系列T1の生成に成功したので、装置はステップ16へ進む。
(ステップ16)装置は、テスト対象信号線s1903に故障値Dを設定する。
【0211】
(ステップ101)装置は、テスト対象信号線s1903に故障値Dを設定するために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、検査系列T2における制御点PI1903の値は0に設定される。検査系列T2は{P}={X,X,0,X,X,X,X,X}に更新される。
(ステップ102)ステップ101では矛盾が発生していないので、装置はステップ103へ進む。
(ステップ103〜106)装置は、信号線s1909(観測不可)を到達候補信号線に設定し、信号線s1909を到達信号線に設定する。
【0212】
(ステップ107)装置は、到達信号線s1903の故障値Dを信号線s1909へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1902および制御点PI1902にはS1が設定される。検査系列T1は{P}={X,1,1,X,X,X,X,X}に更新され、検査系列T2は{P}={X,1,0,X,X,X,X,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1903を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0213】
(ステップ103〜104)信号線s1909は分岐の幹であるので、装置は信号線s1909a、s1909b、s1909cを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s1909a、s1909b、1909cの最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s1909aの最長観測距離は6、信号線s1909bの最長観測距離は5、信号線s1909cの最長観測距離は3である。そこで、装置は、最長観測距離が最も長い到達候補信号線s1909aを到達信号線として選択する。
(ステップ803)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
【0214】
(ステップ110)装置は、到達信号線s1909aの故障値Dを信号線s1910へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1901bおよび制御点PI1901にはS1が設定され、信号線s1910には故障値Dが伝搬する。検査系列T1は{P}={1,1,1,X,X,X,X,X}に更新され、検査系列T2は{P}={1,1,0,X,X,X,X,X}に更新される。
(ステップ804)ステップ110では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1909aを遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0215】
(ステップ103〜106)装置は、信号線s1910(観測不可)を到達候補信号線に設定し、信号線s1910を到達信号線に設定する。
(ステップ107)装置は、到達信号線s1910の故障値Dを信号線s1915へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、制御点PI1901、PI1902にはS1が設定されており、信号線s1914cにはS0が設定されている。したがって、到達信号線s1910の故障値Dを信号線s1915へ伝搬させるために、装置が信号線s1914cにS1を設定すると、矛盾が発生する。
(ステップ810)ステップ107で矛盾が発生したので、装置はステップ805へ進む。
【0216】
(ステップ805)装置は、伝搬失敗信号線s1910、s1909aを不到達信号線に追加する。
(ステップ807)装置は、伝搬失敗信号線s1910、s1909aの入力側信号線のうち、遷移経路集合に含まれる信号線s1909を到達信号線に設定する。
(ステップ808)テスト対象信号線s1903ではない到達信号線があるので、装置はステップ809へ進む。
(ステップ809)装置は、到達信号線s1909の出力側に接続される信号線s1909a、1909b、1909cを到達候補信号線に設定する。このうち信号線s1909b、1909cは不到達信号線に含まれていないので、装置はステップ810へ進む。
(ステップ810)装置は、不到達信号線に含まれる信号線s1909aを到達候補信号線から削除する。その結果、到達候補信号線には、信号線s1909b、1909cが含まれる。その後、装置はステップ103へ進む。
【0217】
(ステップ103〜104)信号線s1909は分岐の幹であるので、装置は信号線s1909b、s1909cを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s1909b、1909cの中から任意に到達候補信号線s1909bを到達信号線として選択する。
(ステップ803)ステップ109で到達信号線を選択したので、装置はステップ110へ進む。
【0218】
(ステップ110)装置は、到達信号線s1909bの故障値Dを信号線s1911へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1904および制御点PI1904にはS1が設定され、信号線s1911には故障値Dが伝搬する。検査系列T1は{P}={1,1,1,1,X,X,X,X}に更新され、検査系列T2は{P}={1,1,0,1,X,X,X,X}に更新される。
(ステップ804)ステップ110では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1909bを遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0219】
(ステップ103〜106)装置は、信号線s1911(観測不可)を到達候補信号線に設定し、信号線s1911を到達信号線に設定する。
(ステップ107)装置は、到達信号線s1911の故障値Dを信号線s1916へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。このステップが実行される前に、制御点PI1901、PI1902にはS1が設定されており、信号線s1915にはS0が設定されている。したがって、信号線に新たに値を設定しなくても、信号線s1916には故障値Dが伝搬する。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1911を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0220】
(ステップ103〜106)装置は、信号線s1916(観測不可)を到達候補信号線に設定した後、信号線s1916を到達信号線に設定する。
(ステップ107)到達信号線s1916は分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ801へ進む。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1916を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0221】
(ステップ103〜104)信号線s1916は分岐の幹であるので、装置は信号線s1916a、s1916bを到達候補信号線に設定し、ステップ108へ進む。
(ステップ108)装置は、到達候補信号線s1916a、s1916bの最長観測距離を求める。ゲート段数で観測距離を評価すると、2本の到達候補信号線の最長観測距離は、いずれも3である。そこで、装置は、このうち任意に到達候補信号線s1916aを到達信号線として選択する。
(ステップ803)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
【0222】
(ステップ110)装置は、到達信号線s1916aの故障値Dを信号線s1917へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、制御点PI1901、PI1902にはS0が設定され、信号線s1914bにはS0が設定されている。したがって、到達信号線s1916aの故障値Dを信号線s1917へ伝搬させるために、装置が信号線s1914bにS1を設定すると、矛盾が発生する。
(ステップ804)ステップ110で矛盾が発生したので、装置はステップ112へ進む。
(ステップ112)装置は、到達信号線s1916aを到達候補信号線から除外する。この結果、到達候補信号線には、信号線s1916bのみが含まれる。
【0223】
(ステップ108)装置は、唯一の到達候補信号線であるs1916bを選択する。
(ステップ803)ステップ108で到達信号線を選択したので、装置はステップ110へ進む。
(ステップ110)装置は、到達信号線s1916bの故障値Dを信号線s1924へ伝搬させるために、活性化、含意操作および正当化を行う。しかし、このステップが実行されるより前に、制御点PI1901、PI1902にはS0が設定され、信号線s1916aにはS0が設定されている。したがって、到達信号線s1916bの故障値Dを信号線s1924へ伝搬させるために、装置が信号線s1914aにS1を設定すると、矛盾が発生する。
(ステップ804)ステップ110で矛盾が発生したので、装置はステップ112へ進む。
【0224】
(ステップ112)装置は、到達信号線s1916bを到達候補信号線から除外する。この結果、到達候補信号線に含まれる信号線がなくなる。
(ステップ108)到達候補信号線に含まれる信号線がないので、装置は到達候補信号線を選択しない。
(ステップ803)到達信号線がないので、装置はステップ805へ進む。
(ステップ805)装置は、伝搬失敗信号線s1911を不到達信号線に追加する。
(ステップ807)装置は、伝搬失敗信号線s1911の入力側信号線のうち、遷移経路集合に含まれる信号線s1909を到達信号線に設定する。
【0225】
(ステップ808)テスト対象信号線s1903ではない到達信号線があるので、装置はステップ809へ進む。
(ステップ809)装置は、到達信号線s1909の出力側に接続される信号線s1909a、s1909b、s1909cを到達候補信号線に設定する。このうち信号線s1909cは不到達信号線に含まれていないので、装置はステップ810へ進む。
(ステップ810)装置は、不到達信号線に含まれる信号線s1909a、s1909bを到達候補信号線から削除する。その結果、到達候補信号線には、信号線s1909cのみが含まれる。その後、装置はステップ103へ進む。
【0226】
(ステップ103〜106)装置は、信号線s1909cを到達候補信号線に設定し、信号線s1909cを到達信号線に設定する。
(ステップ107)装置は、到達信号線s1909cの故障値Dを信号線s1920へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1905および制御点PI1905にはS1が設定され、信号線s1920には故障値Dが伝搬する。検査系列T1は{P}={1,1,1,1,1,X,X,X}に更新され、検査系列T2は{P}={1,1,0,1,1,X,X,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1909cを遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0227】
(ステップ103〜106)装置は、信号線s1921を到達候補信号線に設定し、信号線s1921を到達信号線に設定する。
(ステップ107)装置は、到達信号線s1920の故障値Dを信号線s1921へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1906および制御点PI1906にはS1が設定され、信号線s1921には故障値Dが伝搬する。検査系列T1は{P}={1,1,1,1,1,1,X,X}に更新され、検査系列T2は{P}={1,1,0,1,1,1,X,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1920を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0228】
(ステップ103〜106)装置は、信号線s1921を到達候補信号線に設定し、信号線s1921を到達信号線に設定する。
(ステップ107)装置は、到達信号線s1921の故障値Dを信号線s1923へ伝搬させるために、ロバスト条件での活性化、含意操作および正当化を行う。これにより、信号線s1907および制御点PI1907にはU0が設定され、信号線s1921には故障値Dが伝搬する。検査系列T1は{P}={1,1,1,1,1,1,X,X}に更新され、検査系列T2は{P}={1,1,0,1,1,1,0,X}に更新される。
(ステップ801)ステップ107では矛盾が発生していないので、装置はステップ802へ進む。
(ステップ802)装置は、到達信号線s1921を遷移経路集合に追加する。その後、装置はステップ103へ進む。
【0229】
(ステップ103)装置は、信号線s1923を到達候補信号線に設定する。
(ステップ104)到達候補信号線が1本なので、装置はステップ105へ進む。
(ステップ105)到達候補信号線s1923は観測点PO1に接続されており観測可能なので、装置はステップ19へ進む。
【0230】
以上の処理により、検査系列T1として{P}={1,1,1,1,1,1,X,X}が生成され、検査系列T2として{P}={1,1,0,1,1,1,0,X}が生成される。
【0231】
ここで、第11の生成方法とは異なり、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を元に戻す処理を行うテストパターン生成方法を考える。図22に示すテスト対象回路に対してこの方法を実行すると、ゲートg1911、g1913の出力へ故障値を伝搬させるための活性化を行うときに、ゲートg1902の出力へ故障値を伝搬させるときに求めたs1901の値を繰り返し求める必要があり、処理時間が長くなる。
【0232】
以上に示すように、第11の生成方法によれば、バックトラックを行うときに、伝搬失敗信号線に故障値を伝搬させるために求められた制御点の値を保持したままにすることにより、故障値を伝搬させるときに信号線に割り当てた値を保持する必要がなくなる。したがって、処理時間を短縮し、メモリ使用量を削減することができる。
【0233】
なお、第8〜第11の実施形態では、ステップ805〜808では、装置は、ゲート1段分ずつバックトラックすることとしたが、これに代えて、1回の処理で、複数の到達候補信号線に接続された分岐の幹までバックトラックしてもよい。この場合、遷移経路集合に含まれる分岐の枝は、不到達信号線に設定される。また、これまでの説明では、装置はロバスト条件に従い活性化を行うこととしたが、これに代えて、ノンロバスト条件に従い活性化を行ってもよく、図46(a)に例示される経路活性化表を用いた活性化を行ってもよい。
【0234】
<第12の実施形態>
図23は、第12の生成方法を示すフロー図である。第12の生成方法は、第1の生成方法に対して、ステップ1201、1202を追加したものである。第12の生成方法は、所定の基準を満たさない制御点および信号線を除外して処理することを特徴とする。
【0235】
第12の生成方法で初出のステップは、以下のとおりである。
(ステップ1201)装置は、制御点および信号線に関する基準値を設定する。なお、この基準値は、人手で入力してもよく、電子計算機を用いて入力してもよい。
(ステップ1202)装置は、テスト対象回路に含まれる制御点および分岐の枝について最長テスト経路長を求める。
【0236】
第12の生成方法では、制御点の最長テスト経路長がステップ1201で設定された基準値よりも短い場合には、装置は、当該制御点をテスト対象信号線から除外する。すなわち、このような制御点は、ステップ11で選択されない。また、分岐の枝の最長テスト経路長がステップ1201で設定された基準値よりも短い場合には、装置は、当該分岐の枝をテスト対象信号線から除外し、信号線を選択するときに信号線選択の候補から除外する。すなわち、このような分岐の枝は、ステップ11で選択されず、ステップ108で到達信号線として選択されない。
【0237】
図5に示すテスト対象回路に対して第11の生成方法を実行したときの処理を説明する。ここでは、信号線s9の立上り遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。
(ステップ1201)装置は、制御点および信号線に関する基準値を4に設定する。
(ステップ1202)図5に示すテスト対象回路は、制御点PI1、PI2、PI3、PI4、PI5、PI6、PI7、および、分岐の枝s5a、s5b、s5c、s6a、s6b、s10a、s10bを含んでいる。装置は、これら制御点および分岐の枝について最長テスト経路長を求める。その結果、制御点PI1、PI2、PI3、PI4、PI5、PI6、PI7の最長テスト経路長は、それぞれ、3、4、3、4、2、3、1となり、分岐の枝s5a、s5b、s5c、s6a、s6b、s10a、s10bの最長テスト経路長は、3、4、3、2、3、4、3となる。
【0238】
ステップ1201以降の処理では、最長テスト経路長がステップ1201で指定された基準値4よりも短い制御点および分岐の枝は、処理対象から除外される。具体的には、ステップ11では、7つの制御点のうち、制御点PI2、PI4のみがテスト対象として選択され、7本の分岐の枝のうち、分岐の枝s5b、s10bのみがテスト対象として選択される。また、ステップ103では、分岐の枝s5a、s5b、s5cのうち、分岐の枝s5bのみが到達候補信号線に設定され、分岐の枝s10a、s10bのうち、分岐の枝s10aのみが到達候補信号線に設定され、分岐の枝s6a、s6bは、どちらも到達候補信号線に設定されなくなる。
【0239】
この例では、第1の生成方法で選択された分岐の枝s10aは、第11の生成方法でも到達候補信号線として扱われる。したがって、この例では、第11の生成方法によれば、第1の生成方法と同じテストパターンが生成される。すなわち、第11の生成方法によれば、検査系列T1として{P}={X,X,X,0,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。ただし、一般的には、第11の生成方法では、所定の基準を満たさない制御点および信号線は処理対象から除外されるので、第1の生成方法とは異なるテストパターンが生成される。
【0240】
なお、装置は、ステップ1202を実行する前に、ステップ201(図7)を実行してもよい。例えば、図8に示すテスト対象回路に対してステップ201を実行すると、図9に示すエッジグラフが得られる。最長テスト経路長が基準値4より短い制御点および信号線を処理対象から除外することにより、図9に示すエッジグラフをさらに簡略化することができる(図24を参照)。この場合、図24に実線で示したグループに対してのみステップ1202を実行することにより、処理を高速化することができる。
【0241】
以上に示すように、第12の生成方法によれば、所定の基準を満たさない制御点および信号線を除外して処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。
【0242】
<第13の実施形態>
図25は、第13の生成方法を示すフロー図である。第13の生成方法は、第1の生成方法に対して、ステップ1301、1302を追加したものである。第13の生成方法は、指定された信号線を除いて処理することを特徴とする。
【0243】
第13の生成方法で初出のステップは、以下のとおりである。
(ステップ1301)装置には、対象外信号線情報として、テスト対象回路に含まれる制御点、信号線および観測点を指定する情報が入力される。なお、この対象外信号線情報は、ステップ10で回路情報とともに入力されることとしてもよい。
(ステップ1302)装置は、ステップ1301で入力された対象外信号線情報に基づき、処理対象から除外する信号線を決定する。
【0244】
第13の生成方法では、対象外信号線情報に制御点が含まれている場合には、当該制御点から分岐点を経由せずに到達できる分岐点までの経路を構成する信号線が、処理対象から除外される。対象外信号線情報に信号線が含まれている場合には、当該信号線から任意の観測点に至る経路を構成する信号線が、処理対象から除外される。対象外信号線情報に観測点が含まれている場合には、当該観測点に到達する経路のみに含まれる信号線が、処理対象から除外される。
【0245】
図5に示すテスト対象回路に対して第13の生成方法を実行したときの処理を説明する。ここでは、信号線s9の立上り遷移をテスト対象とし、{PI1、PI2、PI3、PI4、PI5、PI6、PI7}を{P}と記載する。
(ステップ1301)装置には、観測点PO2を指定した対象外信号線情報が入力される。
(ステップ1302)図5に示すテスト対象回路には、観測点PO2に到達するのみに経路を構成する信号線として、信号線s5c、s10b、s12、s13、s14、s15、s16が含まれている。装置は、これらの信号線を処理対象から除外する。したがって、後にステップ103が実行されるときでも、信号線s10bは伝達候補信号線に設定されない。
【0246】
この例では、第1の生成方法で選択された分岐の枝s10aは、第11の生成方法でも到達候補信号線として扱われる。したがって、この例では、第11の生成方法によれば、第1の生成方法と同じテストパターンが生成される。すなわち、第11の生成方法によれば、検査系列T1として{P}={X,X,X,0,X,X,X}が生成され、検査系列T2として{P}={0,1,0,1,0,X,X}が生成される。ただし、一般的には、第11の生成方法では、所定の基準を満たさない制御点および信号線は処理対象から除外されるので、第1の生成方法とは異なるテストパターンが生成される。
【0247】
以上に示すように、第13の生成方法によれば、指定された信号線を除いて処理することにより、処理時間を短縮し、メモリ使用量を削減することができる。例えば、テスト対象回路に含まれるマルチサイクルパスやフォールスパスを指定すれば、効果的である。
【0248】
なお、以上の説明では、装置には対象外信号線情報が外部から入力されることとしたが、これに代えて、装置自身が、テスト対象回路の静的タイミング解析や遅延値の計算結果に基づき、対象外信号線情報を自動的に求めてもよい。
【0249】
なお、第1〜第13の実施形態では、装置は、外部入力端子とスキャンFFとの間にある組合せ回路、スキャンFF間にある組合せ回路、および、スキャンFFと外部出力端子との間にある組合せ回路に対して、テストパターンを生成することとした。これに代えて、装置は、テスト対象回路の1テスト周期前の状態を考慮して、検査系列T1とT2を同時に生成してもよい。この場合、装置は、図4に示すステップ13〜16を検査系列生成処理に含めて実行すればよい。
【0250】
本発明の第14〜第16の実施形態におけるテストパターン生成方法においては、信号が入力される制御点からテスト対象信号線へと信号遷移を伝播することができる1以上の経路の中で、テスト対象信号線から制御点までの経路長がより長い経路が選択される。以下、第14〜第16の実施形態に係るテストパターン生成方法を、それぞれ、第14〜第16の生成方法という。
【0251】
図26は、本発明の第14〜第19の実施形態に係るテストパターン生成方法で用いられる値を示す図である。図26に示す論理値1Uは、信号線の値が検査系列T1では1であり、検査系列T2ではX(0でも1でもよい)であることを示す。論理値0Uは、信号線の値が検査系列T1では0であり、検査系列T2ではXであることを示す。論理値10は、信号線の値が検査系列T1では1であり、検査系列T2では0であることを示す。論理値01は、信号線の値が検査系列T1では0であり、検査系列T2では1であることを示す。
【0252】
ここで、予め設定された信号遷移をゲートの出力に伝搬させるために、当該ゲートの入力に設定すべき条件について説明する。例えば、ANDゲートにおいて、出力yに立上がり遷移NDを伝搬させるための条件は、入力aに立上がり遷移NDを与え、入力bにはU1を与えることである(図27(a)を参照)。また、ORゲートにおいて、出力yに立上がり立下がり遷移Dを伝搬させるための条件は、入力aに立下がり遷移Dを与え、、入力bにU0を与えることである。
【0253】
図27(c)に、ANDゲートおよびNANDゲートの活性化条件を示す。より詳細には、ANDゲート及びNANDゲートにおいて、出力に設定される信号遷移と、信号の伝播経路となる入力に与えるべき値との組み合わせに対し、伝搬経路以外の入力に与えるべき値が記載されている。また、図27(d)には、ORゲート及びNORゲートにおいて、出力に設定される信号遷移と、信号の伝播経路となる入力に与えるべき値との組み合わせに対し、伝搬経路以外の入力に与えるべき値が記載されている。また、図27(c)及び図27(d)の代わりに、図28(a)及び図28(b)に示される活性化条件が用いられてもよい。
【0254】
<第14の実施形態>
図29は、本発明の第14の生成方法を示すフロー図である。第14の生成方法では、以下の処理が実行される。
(ステップ2100)装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子(ゲート)および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
(ステップ2101)装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ2001では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
(ステップ2102)装置は、ステップ2101でテスト対象の信号線および信号遷移を選択した場合にはステップ2103へ進み、それ以外の場合にはステップ2117へ進む。
【0255】
(ステップ2103)装置は、ステップ2101で選択したテスト対象信号線に、ステップ2101で選択した信号遷移に対応した故障値(立上り遷移のときはND、立下り遷移のときはD)を設定する。
(ステップ2400)装置は、後述する検査系列生成処理を行うことにより、検査系列<T1,T2>を生成する。
(ステップ2115)装置は、検査系列生成処理において、検査系列<T1,T2>の生成に成功した場合にはステップ2116へ進み、それ以外の場合はステップ2101へ進む。
【0256】
(ステップ2116)装置は、ステップ2400で生成した検査系列<T1,T2>を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列<T1,T2>を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ2101へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ2101〜2116が実行される。
(ステップ2117)装置は、ステップ2116で記録した検査系列<T1,T2>をシリアルパターンに変換し、処理を終了する。
【0257】
図30は、図29に示される検査系列生成処理の詳細を示すフロー図である。ステップ2400では、以下の処理が実行される。以下、最も新しく信号遷移が決定された信号線を「制御信号線」といい、制御信号線の入力側に接続され、次に信号遷移が決定される可能性がある信号線を「制御候補信号線」という。
(ステップ2104)装置は、テスト対象信号線を制御信号線に設定する。
(ステップ2105)装置は、制御信号線に信号を伝搬することができる信号線、すなわち、制御信号線の入力端に接続されているゲートの入力信号線を制御候補信号線に設定する。
【0258】
(ステップ2106)装置は、制御候補信号線が1本以下(すなわち、0本または1本)である場合にはステップ2107へ進み、それ以外の場合にはステップ2111へ進む。
(ステップ2107)装置は、制御候補信号線が制御可能である場合には、ステップ2111に進み、それ以外の場合には、ステップ2108へ進む。
(ステップ2108)装置は、制御候補信号線から制御信号線へと信号を遷移可能であるか否かを判定し、遷移可能である場合にはステップ2108へ進み、それ以外に場合には、パタン生成失敗と判定し処理を終了する。
【0259】
(ステップ2109)装置は、制御候補信号線を新たな制御信号線に設定し、ステップ2110に進む。
(ステップ2010)装置は、検査系列<T1、T2>を更新し、ステップ2105へ進む。
【0260】
(ステップ2111)装置がステップ2107からステップ2110に到達するのは、制御候補信号線が可制御の制御点に接続されている場合である。装置は、制御候補信号線が接続される制御点に入力すべき検査系列<T1,T2>を更新し、ステップ2101(図29)へ進む。
【0261】
(ステップ2112)装置がステップ2106からこのステップに到達するのは、制御候補信号線(ゲートの入力)が2本以上ある場合に限られる。装置は、各制御候補信号線について、制御候補信号線から1以上の制御点までの経路の長さ(制御距離)を求める。更に、装置は、各制御候補信号線について、求められた1以上の制御距離の最大値を各制御候補信号線についての最長制御距離として求める。制御距離は、上述した観測距離と同様に、遅延値テーブル(図2)やビアテーブル(図3)あるいは制御候補信号線と制御点との間に接続されるゲート数等のいずれか1つまたはこれらの組み合わせに従って算出される。そして、装置は、制御候補信号線の中で、最長制御距離が最も長い制御候補信号線を選択する。
【0262】
(ステップ2113)装置は、ステップ2112において選択された制御候補信号線から制御信号線へと信号遷移を伝搬させることができると判定した場合には、ステップ2114へ進み、それ以外の場合には、ステップ2117へ進む。
(ステップ2114)装置は、ステップ2112において制御信号線に対して信号を遷移可能と判定した制御候補信号線が可制御であるか否かを判定する。装置は、信号遷移可能な制御候補信号線が可制御である場合には、ステップ2111へ進み、それ以外の場合には、ステップ2115へ進む。
(ステップ2115)装置は、選択された制御候補信号線を新たな制御信号線に設定し、ステップ2116へ進む。
(ステップ2116)装置は、検査系列<T1、T2>を更新し、ステップ2105へ進む。
(ステップ2117)装置は、制御信号線についての制御候補信号線の中から、選択された制御候補信号線を除外し、ステップ2106へ進む。ステップ2117の処理は、制御信号線へと信号遷移を伝搬することができない信号線が再度選択されることを避けるためのものである。
【0263】
図31に示すテスト対象回路に対して第14の生成方法を実行したときの処理を説明する。ここでは、信号線s3の遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。また、ステップ2111において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【0264】
(ステップ2103)装置は、テスト対象信号線s3に、信号遷移NDを設定する。
(ステップ2104)装置は、テスト対象信号線s3を制御信号線に設定する。
(ステップ2105)装置は、信号線s2及びs6aを制御候補信号線に設定する。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0265】
(ステップ2112)装置は、制御候補信号線s2及び信号線s6aの各々について、最長制御距離を計算する。具体的には、図31に示されるテスト対象回路において、信号線s2は、制御点PI1及びPI2に接続されている。制御候補信号線s2から制御点PI1までの経路と、信号線s2から制御点PI2までの経路とは、いずれも1つのゲートg1を含む。したがって、制御候補信号線から制御点までの距離をゲート数によって評価すると、制御候補信号線s2から制御点までの最長制御距離は、1である。一方、制御候補信号線s6aは、制御点PI3に接続されている。制御候補信号線s6aから制御点PI3までの経路は、ゲートを含まないので、制御候補信号線s6aの最長制御距離は、0である。装置は、制御候補信号線s2及びs6aの各々について求められた最長制御距離の長さが最も長い制御候補信号線s2を選択する。
【0266】
(ステップ2113)装置は、活性化、含意操作及び正当化を行い、選択された制御候補信号線s2から制御信号線s3へと信号遷移を伝搬させることができるか否かを判定する。装置は、図27または図28に示される活性化条件等を用いて、ステップ2112の判定を実行する。例えば、制御信号線s3(出力)に立上がり遷移NDが設定されている場合、図28(b)に従って、選択された制御候補信号線s2(伝搬経路となる入力)に立上がり遷移NDを与え、信号線s6a(伝搬経路以外の入力)に、S0を与える必要がある。この場合、ステップ2112では矛盾が発生しないので、装置は、ステップ2113へと進む。
(ステップ2114)信号線s2が直接外部端子に接続されていない(すなわち、可制御ではない)ので、装置は、ステップ2115へ進む。
【0267】
(ステップ2115)装置は、選択された制御候補信号線s2を新たな制御信号線に設定し、ステップ2116へ進む。
(ステップ2116)装置は、検査系列T1及びT2を{P}={X,X,0,X,X,X,X}に更新し、ステップ2105へ進む。
(ステップ2105)装置は、制御信号線s2の入力側に接続される信号線s1及びs5aを制御候補信号線に設定し、ステップ2106へ進む。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0268】
(ステップ2112)装置は、制御候補信号線s1及びs5aの各々について、最長経路長を計算する。制御候補信号線s1及びs5aの最長経路長は、いずれも0であるので、装置は、制御候補信号線s1を選択し、ステップ2113へ進む。
(ステップ2113)制御信号線s2には、信号遷移NDが設定されているので、装置は、例えば図28(a)に従って、信号線s1に信号値NDを設定し、信号線s5aに信号値U1を設定する。ステップ2112では矛盾が発生しないので、装置は2114へ進む。
【0269】
(ステップ2114)制御候補信号線s1が可制御であるので、装置は、ステップ2111へ進む。
(ステップ2111)装置は、検査系列T1を、{P}={0,X,0,X,X,X,X}に更新し、検査系列T2は、{P}={1,1,0,X,X,X,X}に更新する。
【0270】
以上の処理により、装置は、検査系列T1として{P}={0,X,0,X,X,X,X}を決定し、検査系列T2として{P}={1,1,0,X,X,X,X}を決定する。
【0271】
図31に示されるテスト対象回路には、テスト対象信号線s3に信号遷移を伝搬させる経路として、3つの経路、すなわち、信号線s3から信号線s2を経由してから制御点PI1に至る経路と、信号線s3から信号線s2を経由して制御点PI2に至る経路と、信号線s3から信号線s6aを経由して制御点PI3に至る経路とが存在する。第14の生成方法によれば、制御点に入力された信号値をテスト対象信号線に伝搬する経路が複数ある場合、信号遷移を伝搬可能な経路の中で、より長い経路(信号線s3から信号線s2を経由してから制御点PI1に至る経路)が優先的に選択される。より長い経路を用いて信号値を伝搬させることによって、テストパターンの品質を向上することができる。
【0272】
<第15の実施形態>
図32は、本発明の第17の実施形態に係るテストパターン生成方法を示すフロー図である。第17の生成方法は、第15の生成方法に対して、ステップ2201、2202、2203及び2204を追加したものである。第15の生成方法は、ある制御信号線へと信号を伝搬する全ての制御候補信号線について正当化に失敗した場合、過去に信号線の選択が行われた信号線までバックトラックするステップを備えることを特徴とする。
【0273】
第17の生成方法で初出のステップは、以下の通りである。
(ステップ2201)装置は、ステップ2108において、ある制御信号線から信号遷移が可能でないと判定した場合、当該制御信号線がテスト対象信号線であるか否かを判定する。制御信号線がテスト対象信号線である場合には、装置は、処理が失敗であると判定してステップ2115(図29)へ進み、それ以外の場合には、ステップ2202へ進む。ステップ2201において、制御信号線がテスト対象信号線であるか否かを判定するのは、後述のステップ2203において実行されるバックトラックの結果、テスト対象信号線が制御信号線に再設定される可能性があるからである。
【0274】
(ステップ2202)装置は、制御信号線を制御不能な信号線(以下、「非制御信号線」という)に設定し、ステップ2203へ進む。
【0275】
(ステップ2203)装置は、ステップ2202で設定した非制御信号線の出力側に接続されるゲートの出力信号線を新たな制御信号線に設定する。すなわち、装置は、テスト対象回路の出力側へとゲート1段分だけバックトラックする。なお、非制御信号線は、新たに設定された制御信号線(すなわち、バックトラック後の制御信号線)に対する制御候補信号線である。
【0276】
(ステップ2204)装置は、ステップ2202で設定された非制御候補信号線を、制御候補信号線から除外する。
【0277】
ここで、図33に示されるテスト対象回路に対して第17の生成方法を実行したときの処理を説明する。ここでは、信号線s4の立上がり遷移をテスト対象とし、{PI1,PI2,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。また、ステップ2112において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【0278】
(ステップ2103)装置は、テスト対象信号線s4に、信号遷移NDを設定する。
(ステップ2104)装置は、テスト対象信号線s4を制御信号線に設定する。
(ステップ2105)装置は、信号線s3およびs8を制御候補信号線に設定する。
(ステップ2204)非制御信号線は存在しないので、装置は、ステップ2106へ進む。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0279】
(ステップ2112)装置は、信号線s3及び信号線s8の各々について、最長制御距離を計算する。ゲート数で制御距離を評価すると、信号線s3の最長制御距離は、2であり、信号線s8の最長制御距離は、3である。装置は、制御候補信号線s3及びs8の各々について求められた最長制御距離の長さの最大値に基づいて、制御候補信号線s8を選択する。
【0280】
(ステップ2113)装置は、制御信号線s4に信号遷移NDが設定されているので、装置は、信号線s8にDを設定し、信号線s3にU0を設定する。このとき、制御候補信号線s8から制御信号線s4へと信号遷移を伝搬させることが可能であるので、装置は、ステップ2114へ進む。
【0281】
(ステップ2114)装置は、選択された制御候補信号線s8が可制御ではないので、ステップ2115へ進む。
(ステップ2115)装置は、選択された制御候補信号線s8を新たな制御信号線に設定し、ステップ2116へ進む。
(ステップ2116)この段階では、検査系列T1及びT2の値は特定されない({P}={X,X,X,X,X,X,X})ので、装置は、ステップ2105へ進む。
【0282】
(ステップ2105)装置は、制御信号線s8の入力側に接続される信号線s7及びs11を制御候補信号線に設定する。
(ステップ2204)非制御信号線は存在しないので、装置は、ステップ2106へ進む。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0283】
(ステップ2112)装置は、制御候補信号線s7及びs11の各々について、最長経路長を計算する。制御候補信号線s7の最長経路長は2、s11の最長経路長は、0であるので、装置は、制御候補信号線s7を選択し、ステップ2113へ進む。
【0284】
(ステップ2113)装置は、制御候補信号線s7から制御信号線s8へと信号遷移を伝搬させるために、活性化、含意操作及び正当化を行う。装置は、信号線s8にDが設定されているので、信号線s7にNDを設定し、信号線s11にS0を設定する。このとき制御候補信号線s7からs8へと信号を伝播することが可能であるので、装置はステップ2114へ進む。
【0285】
(ステップ2114)選択された制御候補信号線は、可制御ではないので、装置は、ステップ2115へ進む。
(ステップ2115)装置は、選択された制御候補信号線s7を新たな制御信号線に設定し、ステップ2116へ進む。
(ステップ2116)装置は、検査系列T1及びT2を{P}={X,X,X,X,0,X,X}に更新し、ステップ2105へ進む。
【0286】
(ステップ2105)装置は、制御信号線s7の入力側信号線s6b及びs10aを制御候補信号線に設定する。
(ステップ2204)非制御信号線は存在しないので、装置は、ステップ2106へ進む。
(ステップ2106)制御候補信号線は2本であるので、装置はステップ2112へ進む。
【0287】
(ステップ2112)装置は、信号線s6b及びs10aの各々について、最長制御距離を計算する。ゲート数で制御距離を評価すると、信号線s6bの最長制御距離は0であり、信号線s10aの最長制御距離は1である。装置は、s6bおよびs10aの各々について求められた最長制御距離の長さの最大値に基づいて、制御候補信号線s10aを選択する。
【0288】
(ステップ2113)装置は、制御信号線s7にNDが設定されているので、信号線s10aにNDを設定し、信号線s6bにU1を設定し、活性化、正当化および含意操作を行う。しかし、このステップが実施される前に信号線s3にU0に設定されているため、s6bにU1を設定すると矛盾が生じる。そこで、装置は、信号線s10aから信号線s8には信号遷移を伝播できないと判定し、ステップ2117へ進む。
【0289】
(ステップ2117)装置は、信号線s8に対する制御候補信号線からs10aを除外し、ステップ2106へ進む。
(ステップ2106)信号線s10aは、ステップ2114において、信号線s8に対する制御候補信号線から除外されている。したがって、信号線s8に対する制御候補信号線は、信号線s6bのみである。制御候補信号線の数が1本であるので、装置は、ステップ2107へ進む。
【0290】
(ステップ2107)制御候補信号線s6bは可制御ではないため、装置は、ステップ2108に進む。
(ステップ2108)装置は、制御信号線s7にNDが設定されているので信号線s6bにNDを設定し、信号線s10aにU1を設定し、活性化、正当化および含意操作を行う。しかし、このステップが実行される前に信号線s3にU0が設定されているため、信号線s6bにNDを設定すると矛盾が生じる。そこで、装置は、信号線s10aから信号線s8に信号遷移を伝播できないと判定し、ステップ2201へ進む。
【0291】
(ステップ2201)テスト対象信号線は、信号線s4であり、この時点での制御信号線はs7である。したがって、装置は、ステップ2202へ進む。
(ステップ2202)装置は、制御信号線s7を非制御信号線に設定し、ステップ2203へ進む。
(ステップ2203)装置は、非制御信号線に設定した信号線s7の到達ゲートの出力信号線s8を制御信号線に再度設定し、ステップ2105へ進む。
【0292】
(ステップ2105)装置は、制御信号線s8の入力側の信号線s7、s11を制御候補信号線に設定しステップ2203へ進む。
(ステップ2204)装置は、ステップ2202において非制御信号線に設定した信号線s7を制御候補信号線から除外し、ステップ2106へ進む。
【0293】
(ステップ2106)信号線s7は、制御信号線s8に対する制御候補信号線から除外されているので、制御信号線s8に対する制御候補信号線は、信号線s11のみである。制御候補信号線が1本であるので、装置は、ステップ2107へ進む。
(ステップ2107)制御候補信号線s11は、可制御であるので、装置は、ステップ2111へ進む。
(ステップ2111)装置は、検査系列T1を{P}={X,0,X,X,0,X,X}、検査系列T2を{P}={X,0,X,X,1,X,X}に更新し、処理を終了する。
【0294】
上記の第15の生成方法によれば、活性化および正当化に失敗した場合にはバックトラックするので、制御点からテスト対象信号線へと信号遷移を伝搬することができるテストパターンをより確実に生成することができる。
【0295】
<第16の実施形態>
図34は、本発明の第16の実施形態に係るテストパターン生成方法を示すフロー図である。第16の生成方法は、第14の生成方法に対して、ステップ2301を追加したものである。
【0296】
第16の生成方法で初出のステップは、以下の通りである。
(ステップ2301)装置は、最長制御距離が最大でないと判定した制御候補信号線(以下、「非選択制御候補信号線」という)に固定の信号値を設定する。装置が、非選択制御候補信号線に固定値を設定するのは、信号遷移を伝搬する経路に対して、伝搬経路以外の経路において生じた信号遅延が影響することを、可能な限り抑制するためである。なお、ステップ2301において非選択制御候補信号線に固定値を設定することができない場合には、信号遷移を設定してもよい。
【0297】
ここで、図31に示すテスト対象回路に対して第16の生成方法を実行したときの処理を説明する。ここでは、信号線s3の立上がり遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。また、ステップ2111において、制御距離は、経路に含まれるゲート数に基づいて計算される場合を想定する。
【0298】
(ステップ2103)装置は、テスト対象信号線s3に、信号遷移NDを設定する。
(ステップ2104)装置は、テスト対象信号線s3を制御信号線に設定する。
(ステップ2105)装置は、信号線s2及びs6aを制御候補信号線に設定する。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0299】
(ステップ2112)装置は、制御候補信号線s2及び信号線s6aの最長制御距離を計算する。ゲート段数で制御距離を評価すると、信号線s2の最長制御距離は1、信号線s6aの最長観測距離は、0である。そこで、装置は、最長制御距離が最も長い制御候補信号線s2を選択し、ステップ2113へ進む。
【0300】
(ステップ2113)制御信号線s3にNDが設定されているので、装置は、選択された制御候補信号線s2にNDを設定し、信号線s6aにS0を設定し、活性化、正当化、含意操作を行う。このとき制御候補信号線s2から制御信号線s3に信号を伝播することが可能であるため、装置は、ステップ2114へ進む。
【0301】
(ステップ2114)選択された制御候補信号線s2は、可制御ではないので、装置は、ステップ2301へ進む。
(ステップ2301)装置は、未選択制御候補信号線であるs6aに制御候補信号線s2から制御信号線s3へ伝播可能な固定値である0を与え、ステップ2115へ進む。
【0302】
(ステップ2115)装置は、選択された制御候補信号線s2を新たな制御信号線に設定する。
(ステップ2116)装置は、検査系列T1を、{P}={X,X,0,X,X,X,X}に更新し、検査系列T2を、{P}={X,X,0,X,X,X,X}に更新し、ステップ2105へ進む。
【0303】
(ステップ2105)装置は、制御信号線s2の入力側に接続される信号線s1及びs5aを制御候補信号線に設定する。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0304】
(ステップ2112)装置は、制御候補信号線s1及びs5aの各々について、最長経路長を計算する。制御候補信号線s1及びs5aの最長経路長は、いずれも0であるので、装置は、制御候補信号線s1を選択し、ステップ2113へ進む。
(ステップ2113)選択された制御信号線s2には、NDが設定されているので、装置は、制御候補信号線s1にNDを設定し、制御候補信号線s5aにU1を設定し、活性化、正当化、含意操作を行う。このとき制御候補信号線s1から制御信号線s2に信号の伝達が可能であるため、ステップ2301へ進む。
【0305】
(ステップ2114)選択された制御候補信号線s1は、可制御であるので、装置は、ステップ2111へ進む。
(ステップ2111)装置は、検査系列T1として{P}={0,1,0,X,X,X,X}を決定し、検査系列T2として{P}={1,1,0,X,X,X,X}を決定する。
【0306】
尚、この例では、検査系列T1において制御点PI2に与えられる値は、検査系列T2において制御点PI2に与えられる値が1である限り、検査系列T1では、Xまたは1のいずれの値であってもよい。しかしながら、検査系列T1及びT2の両方において、制御点PI2に固定値0が設定された場合、未選択制御候補信号線s5a上に信号遅延が生じることはない。したがって、制御信号線s2に対して、信号の伝搬経路である制御候補信号線s1以外の経路において生じる信号遅延の影響を取り除くことができる。
【0307】
このように、第16の生成方法によれば、制御点からテスト対象信号線へと信号伝搬可能な最長の経路以外の経路には、固定値が設定されるので、テスト対象外経路の信号遅延の影響が低減し、テストパターンの信頼性が向上する。
【0308】
以下、本発明の第17〜第19の各実施形態について説明する。第17〜第19の実施形態に係るテストパターン生成方法においては、制御点からテスト対象信号線を経由して観測点まで至る経路の中で、より長い経路が優先的に選択される。以下、第17〜第19の実施形態に係るテストパターン生成方法を、それぞれ、第17〜第19の生成方法という。
【0309】
<第17の実施形態>
図35は、本発明の第17の生成方法を示すフロー図である。第17の生成方法においては、まず、第1の決定処理において、テスト対象信号線から観測点へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、検査系列<T1,T2>が生成される。次に、第2の決定処理において、制御点からテスト対象信号線へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、生成された検査系列<T1,T2>が更新される。以下に、第17の生成方法の処理について説明する。
【0310】
(ステップ2100)装置には、回路情報として、テスト対象回路を構成する記憶素子、論理素子(ゲート)および素子間の配線に関する情報が入力される。これに加えて、装置には、テスト対象の信号線を特定する情報が入力される。なお、テスト対象の信号線を特定する情報は、人手で入力してもよく、電子計算機を用いて入力してもよい。
(ステップ2101)装置は、テスト対象の信号線と、テスト対象の信号遷移とを選択する。ステップ2001では、既にテストパターン生成済みの信号線や、テストパターンを生成できないと判断された信号線は、選択の対象から除外される。なお、テスト対象の信号線および信号遷移は、人手で選択してもよく、回路情報に基づき電子計算機が自動的に選択してもよい。
【0311】
(ステップ2102)装置は、ステップ2101でテスト対象の信号線および信号遷移を選択した場合にはステップ2103へ進み、それ以外の場合にはステップ2117へ進む。
(ステップ2103)装置は、ステップ2101で選択したテスト対象信号線に、ステップ2101で選択した信号遷移に対応した故障値(立上り遷移のときはND、立下り遷移のときはD)を設定する。
【0312】
(ステップ2601)装置は、後述する第1の決定処理を行うことにより、検査系列<T1,T2>を決定する。
(ステップ2602)装置は、第1の決定処理に成功した場合には、ステップ2602へ進み、それ以外の場合は、ステップ2101へ進む。
(ステップ2603)装置は、後述する第2の決定処理を行うことにより、ステップ2601において決定された検査系列<T1,T2>を更新しながら、検査系列<T1,T2>を決定する。
(ステップ2604)装置は、第2の決定処理に成功した場合には、ステップ2116へ進み、それ以外の場合は、ステップ2101へ進む。
【0313】
(ステップ2116)装置は、ステップ2603で生成した検査系列<T1,T2>を一時的に内部またはファイルに記録する。また、以前にテストパターン生成不可と判断された信号線が存在する場合は、装置は、生成された検査系列<T1,T2>を用いて、それらの信号線を検査できるか否かを調べてもよい。次に、装置はステップ2101へ進む。このようにして、テスト対象の信号線および信号遷移のすべての組合せについて、ステップ2101〜2116が実行される。
(ステップ2117)装置は、ステップ2116で記録した検査系列<T1,T2>をシリアルパターンに変換し、処理を終了する。
【0314】
図36は、図35に示される第1の決定処理の詳細を示すフロー図である。
(ステップ2501)装置は、テスト対象信号線を到達信号線に設定する。
(ステップ2502)装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。なお、正当化によって制御点に与えるべき値が決定された場合には、検査系列T2が更新され、場合によっては検査系列T1も更新される。以下に示すすべての正当化処理においても、これと同じである。
【0315】
(ステップ2503)装置は、ステップ2502で矛盾が発生した場合にはステップ2101へ進み、それ以外の場合にはステップ2504へ進む。
(ステップ2504)装置は、到達信号線の出力側のゲートの信号線を到達候補信号線に設定する。
(ステップ2505)装置は、到達候補信号線が1本以下(すなわち、0本または1本)である場合にはステップ2506へ進み、それ以外の場合にはステップ2508へ進む。
【0316】
(ステップ2506)装置は、到達候補信号線が観測可能であるか、または、0本である(すなわち、到達候補信号線が観測点に接続されているか、または、到達候補信号線がない)場合には、ステップ2513へ進み、それ以外の場合にはステップ2507へ進む。
(ステップ2507)装置がこのステップに到達するのは、到達候補信号線が1本である場合に限られる。装置は、唯一の到達候補信号線を新たな到達信号線に設定する。
【0317】
(ステップ2508)装置は、各分岐の枝について、各観測点までの経路の長さ(観測距離)を求め、観測距離の最大値(以下、最長観測距離という)を求める。観測距離は、上述したように、遅延値テーブル(図2)やビアテーブル(図3)など用いて算出される。装置は、到達候補信号線の中で最長観測距離が最も長い信号線を選択する。
【0318】
(ステップ2509)装置は、テスト対象信号線に故障値を設定し、設定した故障値をテスト対象信号線の出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。
(ステップ2510)装置は、ステップ2509で矛盾が発生した場合にはステップ2512へ進み、それ以外の場合にはステップ2511へ進む。
【0319】
(ステップ2511)装置は、到達候補信号線を新たな到達信号線に設定し、ステップ2502へ進む。
(ステップ2512)装置は、到達信号線についての到達候補信号線の中から、ステップ2509において矛盾を生じさせた到達候補信号線を除外し、ステップ2505へ進む。
(ステップ2513)装置は、検査系列<T1,T2>を更新し、ステップ2601へ進む。
【0320】
なお、第1の決定処理には、上記の第1〜第13の生成方法における検査系列生成方法のいずれかを適用すればよい。また、第2の決定処理には、上記の第14〜16の生成方法における検査系列生成方法のいずれかを適用すればよいので、以下の説明を省略する。
【0321】
ここで、図37に示すテスト対象回路に対して第17の生成方法を実行したときの処理を説明する。ここでは、信号線s10の立上がり遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。
【0322】
(ステップ2103)装置は、テスト対象信号線s10にNDを設定する。
(ステップ2501)装置は、テスト対象信号線s10を到達信号線に設定する。
(ステップ2502)到達信号線s10は、分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ2503へ進む。
(ステップ2503)ステップ2502では矛盾が発生していないので、装置は、ステップ2504へ進む。
(ステップ2504)到達信号線s10は、分岐の幹であるので、装置は、信号線s10a及びs10bを到達候補信号線に設定する。
(ステップ2505)到達候補信号線が2本あるので、装置は、ステップ2508へ進む。
【0323】
(ステップ2508)装置は、到達候補信号線s10a及びs10bのおのおのについて、最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s10aの最長観測距離は3、信号線s10bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線10aの最長観測距離は3、信号線s10bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線s10aを選択する。
【0324】
(ステップ2509)装置は、到達候補信号線s10に設定された信号遷移をテスト対象回路の出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。これにより、装置は、信号線s7にNDを設定し、信号線s6bにS0を設定する。テスト系列T1は、{P}={X,X,0,X,X,X,X}に更新され、テスト系列T2は、{P}={X,X,0,X,X,X,X}に更新される。
【0325】
(ステップ2510)ステップ2509では矛盾が発生していないので、装置は、ステップ2512へ進む。
(ステップ2511)装置は、到達候補信号線s7を新たな到達信号線に設定し、ステップ2502へ進む。
【0326】
装置は、同様に、図36に示される処理を実行する。テスト対象信号線から観測点までの経路を選択しながらテストパターンを生成する方法は、第1〜第14の実施形態において説明したので、以下の詳細な説明を省略する。結果として、装置は、テスト対象信号線s10から、信号線s7、s8a、s4を順に経由して観測点PO1へと至る経路を選択しながら、テスト系列<T1,T2>を決定する。装置は、ステップ2513において、テスト系列T1を、{P}={X,X,0,X,0,X,X}に更新し、テスト系列T2を、{P}={0,X,0,X,0,X,X}に更新する。その後、装置は、ステップ2602へ進む。
(ステップ2602)第1の決定処理は成功したので、装置は、ステップ2603へ進む。
【0327】
以下、装置は、第2の決定処理として、第14の実施形態に係る検査系列生成処理(図30)を実行する場合を想定する。したがって、装置は、ステップ2104へ進む。
【0328】
(ステップ2104)装置は、テスト対象信号線s10を制御信号線に設定する。
(ステップ2105)装置は、信号線s9及びs5bを制御候補信号線に設定する。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0329】
(ステップ2112)装置は、信号線s9の及び信号線s5bの各々について、制御距離を計算する。ゲート段数で経路長を評価すると、制御候補信号線s9の最長制御距離は、0であり、制御候補信号線s5bの最長制御距離は、1である。したがって、装置は、制御候補信号線s5bを選択し、ステップ2113へ進む。
(ステップ2113)装置は、選択された制御候補信号線s5bにDを設定し、制御信号線s10へNDを伝搬させることができるか否かを判定する。正当化、活性化、含意操作の結果、信号遷移可能であるため、装置は、ステップ2114へ進む。
【0330】
(ステップ2114)制御候補信号線s5bが可制御でないため、装置は、ステップ2115へ進む。
(ステップ2115)到達候補信号線s5bを制御信号線に設定し、装置は、ステップ2116に進む。
(ステップ2116)装置は、検査系列T1を{P}={X,X,0,1,0,X,X}に更新し、検査系列T2を{P}={0,X,0,1,0,X,X}に更新し、ステップ2105へ進む。
【0331】
(ステップ2105〜2111)制御信号線s5bの到達候補信号線はs5のみであるりs5は可制御である。そのためステップ2106、2107と進み、ステップ2111にて検査系列を更新する。
【0332】
以上の処理により、装置は、検査系列T1として{P}={X,0,0,1,0,X,X}を決定し、検査系列T2として{P}={0,1,0,1,0,X,X}を決定する。
【0333】
このように、まず、第1の決定処理において、テスト対象信号線から観測点までの経路長がより長い経路についてテストパターンが生成される。次に、第2の決定処理において、制御点から当該テスト対象信号線までの距離がより長い経路について、第1の決定処理で生成されたテストパターンを更新しながら、テストパターンが決定される。よって、第17の生成方法によれば、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【0334】
また、最初にテスト対象信号線から観測点へと信号伝搬可能な経路が選択されるため、テスト対象信号線上の信号遷移を確実に観測可能な経路について効率的にテストパターンを生成することができる。
【0335】
<第18の実施形態>
図38は、本発明の第18の生成方法を示すフロー図である。図38に示されるように、第18の生成方法は、第17の生成方法において、ステップ2601と、ステップ2603との実行順序が入れ替えられたものであり、第1の決定処理(ステップ2601)は、第2の決定処理(ステップ2603)の後に実行される。より詳細には、まず、制御点からテスト対象信号線へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、生成された検査系列<T1,T2>が生成される。次に、テスト対象信号線から観測点へと信号遷移を伝播することが可能な経路の中から、より長い経路が選択され、検査系列<T1,T2>が更新される。
【0336】
なお、第1の決定処理には、上記の第1〜第13の生成方法における検査系列生成処理のいずれかを適用することができる。また、第1の決定処理として、第17の生成方法と同様に、図36に示される検査系列生成処理が適用されてもよい。一方、第2の決定処理には、上記の第14〜第16における検査系列生成処理のいずれかを適用することができる。
【0337】
ここで、図37に示すテスト対象回路に対して第18の生成方法を実行したときの処理を説明する。ここでは、信号線s10の立上がり遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。
【0338】
また、以下の例においては、第1の決定処理として図36に示される検査系列生成処理が適用され、かつ、第2の決定処理として図30に示される検査系列生成処理が適用される場合を想定する。
【0339】
(ステップ2103)装置は、テスト対象信号線s10にNDを設定し、ステップ2104へ進む。
(ステップ2104)装置は、テスト対象信号線s10を制御信号線に設定する。
(ステップ2105)装置は、信号線s9及びs5bを制御候補信号線に設定する。
(ステップ2106)制御候補信号線は、2本であるので、装置は、ステップ2112へ進む。
【0340】
(ステップ2112)装置は、信号線s2の及び信号線s6aの各々について、制御距離を計算する。ゲート段数で経路長を評価すると、制御候補信号線s9の最長制御距離は、0であり、制御候補信号線の最長制御距離は、1である。したがって、装置は、制御候補信号線s5bを選択し、ステップ2113へ進む。
(ステップ2113)装置は、制御信号線s10に所定の信号遷移を発生させるために、活性化、含意操作及び正当化を行い、選択された制御候補信号線s2から制御信号線s3へと信号遷移を伝搬させることができるか否かを判定する。結果として、装置は、信号線s5bにDを設定し、信号線s9にS1を設定し、ステップ2114へ進む。
【0341】
(ステップ2114)選択された制御候補信号線s5bは、制御可能ではないので、装置は、ステップ2115へ進む。
(ステップ2115)装置は、選択された制御候補信号線s5bを新たな制御信号線に設定し、ステップ2116へ進む。
(ステップ2116)装置は、検査系列T1を{P}={X,X,X,1,X,X,X}を決定し、検査系列T2を{P}={X,X,X,1,X,X,X}に更新し、ステップ2105へ進む。
【0342】
(ステップ2105)装置は、制御信号線s5bの入力側信号線s5を制御候補信号線に設定する。
(ステップ2106〜2111)制御候補信号線は、1本であり、制御可能であるので、装置は、ステップ2107及び2109を経由して、ステップ2111へ進む。
【0343】
(ステップ2110)装置は、検査系列T1として{P}={X,0,X,1,X,X,X}を決定し、検査系列T2として{P}={X,1,X,1,X,X,X}を決定する。その後、装置は、ステップ2602へ進む。
(ステップ2602)装置は、第2の決定処理に成功したので、ステップ2601に進む。
【0344】
(ステップ2501)装置は、テスト対象信号線s10を到達信号線に設定する。
(ステップ2502)到達信号線s10は、分岐の幹であるので、装置は、活性化、含意操作および正当化を行わずに、ステップ2503へ進む。
(ステップ2503)ステップ2502では矛盾が発生していないので、装置は、ステップ2504へ進む。
(ステップ2504)到達信号線s10は、分岐の幹であるので、装置は、信号線s10a及びs10bを到達候補信号線に設定する。
(ステップ2505)到達候補信号線が2本あるので、装置は、ステップ2508へ進む。
【0345】
(ステップ2508)装置は、到達候補信号線s10a及びs10bの各々について、最長観測距離を求める。ゲート段数で観測距離を評価すると、信号線s10aの最長観測距離は3、信号線s10bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線10aの最長観測距離は3、信号線s10bの最長観測距離は2である。そこで、装置は、最長観測距離が最も長い到達候補信号線s10aを到達信号線として選択する。
【0346】
(ステップ2509)装置は、到達候補信号線s10aに設定された信号遷移をテスト対象回路の出力側へゲート1段分だけ伝搬させるために、活性化、含意操作および正当化を行う。これにより、装置は、信号線s7にNDを設定し、信号線s6bにS0を設定する。テスト系列T1は、{P}={X,0,0,1,1,X,X}に更新され、テスト系列T2は、{P}={X,1,X,1,X,X,X}に更新される。
【0347】
(ステップ2510)ステップ2509では矛盾が発生していないので、装置は、ステップ2512へ進む。
(ステップ2511)装置は、到達候補信号線s7を新たな到達信号線に設定し、ステップ2502へ進む。
【0348】
装置は、同様に、図36に示される処理を実行する。テスト対象信号線から観測点までの経路を選択しながらテストパターンを生成する方法は、第1〜第14の実施形態において説明したので、以下の詳細な説明を省略する。結果として、装置は、テスト対象信号線s10から、信号線s7、s8a、s4を順に経由して観測点PO1へと至る経路を選択しながら、テスト系列<T1,T2>を決定する。装置は、ステップ2513において、テスト系列T1を、{P}={X,0,0,1,1,X,X}に更新し、テスト系列T2を、{P}={X,1,X,1,X,X,X}に更新する。その後、装置は、ステップ2604へ進む。
【0349】
このように、まず、第2の決定処理において、制御点から当該テスト対象信号線までの距離がより長い経路についてテストパターンが生成される。次に、第1の決定処理において、テスト対象信号線から観測点までの経路長がより長い経路について、第1の決定処理で生成されたテストパターンを更新しながら、テストパターンが決定される。よって、第18の生成方法によれば、制御点から観測点までの経路の長さがより長くなるようなテストパターンを生成することが可能となる。
【0350】
また、最初に制御点からテスト対象信号線へと信号伝搬可能な経路が選択されるため、テスト対象信号線上の信号伝搬を確実に制御可能な経路について効率的にテストパターンを生成することができる。
【0351】
<第19の実施形態>
図39は、本発明の第19の生成方法を示すフロー図である。第19の生成方法は、第17の生成方法に主としてステップ2200及び2700が追加されている点で、第17の生成方法と相違する。
【0352】
第19の生成方法で初出のステップは、次の通りである。
(ステップ2200)装置は、テスト対象信号線から観測点までの最長観測距離d1と、テスト対象信号線から制御点までの最長制御距離d2とを計算する。最長観測距離及び最長制御距離は、上記の各生成方法と同様に、遅延値テーブル(図2)やビアテーブル(図3)、または、制御候補信号線と制御点との間に接続されるゲート数等を用いて算出される。
【0353】
(ステップ2700)装置は、ステップ2200で算出した最長観測距離d1と、最長制御距離d2とを比較する。装置は、d1がd2より小さくない(すなわち、d1がd2以上である)場合には、第1の決定処理(ステップ2601)を実行した後、第2の決定処理(ステップ2603)を実行する。この場合における第19の生成方法は、第17の生成方法と同じである。一方、d1がd2より小さい場合には、装置は、第2の決定処理(ステップ2603)を実行した後、第1の決定処理(ステップ2601)を実行する。この場合における第19の生成方法は、第18の生成方法と同じである。
【0354】
なお、第1の決定処理には、上記の第1〜第13の生成方法における検査系列生成処理のいずれかを適用することができる。また、第1の決定処理として、第17の生成方法と同様に、図36に示される検査系列生成処理が適用されてもよい。一方、第2の決定処理には、上記の第14〜第16における検査系列生成処理のいずれかを適用することができる。
【0355】
ここで、図37に示すテスト対象回路に対して第19の生成方法を実行したときの処理を説明する。ここでは、信号線s10の立上がり遷移をテスト対象とし、{PI1,PI2,PI3,PI4,PI5,PI6,PI7}を{P}と記載する。初期状態においては、検査系列T1及びT2のいずれも、{P}={X,X,X,X,X,X,X}に設定されている。
【0356】
また、以下の例においては、第1の決定処理として図36に示される検査系列生成処理が適用され、かつ、第2の決定処理として図30に示される検査系列生成処理が適用される場合を想定する。
【0357】
(ステップ2103)装置は、テスト対象信号線s10にNDを設定し、ステップ2200へ進む。
(ステップ2200)装置は、テスト対象信号線s10から観測点までの最長観測距離を求める。観測距離をゲート数によって評価すると、テスト対象信号線s10から、信号線s10a、s7、s8a及びs4を順に経由して制御点PO1へと至る経路が最長であり、最長観測距離d1は、3である。一方、制御距離をゲート数によって評価すると、テスト対象信号線s10から、信号線s5b及びs5を順に経由して制御点PI2へと至る経路が最長であり、最長制御距離d2は、2である。
【0358】
(ステップ2700)最長観測距離d1は、最長制御距離d2より小さくないので、装置は、ステップ2601へ進み、第1の決定処理を第2の決定処理の前に実行する。
なお、以降の具体的な処理は、第17の生成方法と同一であるので、ここでの説明は繰り返さない。
【0359】
結果として、装置は、検査系列T1として{P}={1,1,0,1,1,X,X}を決定し、検査系列T2として{P}={1,1,0,0,1,X,X}を決定する。
【0360】
このように、第19の生成方法においては、テスト対象信号線から観測点までの最長経路の長さは、当該テスト対象信号線から制御点までの最長経路の長さと比較され、比較結果に応じて、第1及び第2の決定処理の実行順序が決められる。テスト対象信号線の観測距離及び制御距離が長くなるにつれて、テストパターンの決定がより困難になるが、第19の生成方法によれば、より長い経路を伝搬するテストパターンを先に決定するので、テストパターンを効率的に生成することができる。
【産業上の利用可能性】
【0361】
本発明のテストパターン生成方法は、遅延故障を検査するための高品質のテストパターンを高速に生成できるので、例えば、各種の半導体集積回路で発生する遅延故障を検査するためのテストパターンを生成するときに利用することができる。
【図面の簡単な説明】
【0362】
【図1】本発明の各実施形態に係るテストパターン生成方法を実行するテストパターン生成システムの構成を示す図
【図2】遅延値テーブルの例を示す図
【図3】ビアテーブルの例を示す図
【図4】本発明の第1の実施形態に係るテストパターン生成方法を示すフロー図
【図5】テスト対象回路の例を示す図
【図6】従来の遷移故障用パターン生成方法を示すフロー図
【図7】本発明の第2の実施形態に係るテストパターン生成方法を示すフロー図
【図8】テスト対象回路の例を示す図
【図9】図8に示すテスト対象回路に基づくエッジグラフを示す図
【図10】エッジグラフの他の例を示す図
【図11】本発明の第3の実施形態に係るテストパターン生成方法を示すフロー図
【図12】本発明の第4の実施形態に係るテストパターン生成方法を示すフロー図
【図13】テスト対象回路の例を示す図
【図14】本発明の第5の実施形態に係るテストパターン生成方法を示すフロー図
【図15】本発明の第6の実施形態に係るテストパターン生成方法を示すフロー図
【図16】テスト対象回路の例を示す図
【図17】本発明の第7の実施形態に係るテストパターン生成方法を示すフロー図
【図18】本発明の第8の実施形態に係るテストパターン生成方法を示すフロー図
【図19】本発明の第9の実施形態に係るテストパターン生成方法を示すフロー図
【図20】本発明の第10の実施形態に係るテストパターン生成方法を示すフロー図
【図21】本発明の第11の実施形態に係るテストパターン生成方法を示すフロー図
【図22】テスト対象回路の例を示す図
【図23】本発明の第12の実施形態に係るテストパターン生成方法を示すフロー図
【図24】図9に示すエッジグラフを簡略化したエッジグラフを示す図
【図25】本発明の第13の実施形態に係るテストパターン生成方法を示すフロー図
【図26】本発明の第14〜第19の実施形態に係るテストパターン生成方法で用いられる値を示す図
【図27】本発明の第14〜第19の実施形態に係るテストパターン生成方法で用いられる経路活性化表の一例を示す図
【図28】本発明の第14〜第19の実施形態に係るテストパターン生成方法で用いられる経路活性化表の他の一例を示す図
【図29】本発明の第14の実施形態に係るテストパターン生成方法を示すフロー図
【図30】図29に示される検査系列生成処理の詳細を示すフロー図
【図31】テスト対象回路の例を示す図
【図32】本発明の第15の実施形態に係るテストパターン生成方法を示すフロー図
【図33】テスト対象回路の例を示す図
【図34】本発明の第16の実施形態に係るテストパターン生成方法を示すフロー図
【図35】本発明の第17の実施形態に係るテストパターン生成方法を示すフロー図
【図36】図35に示される第1の決定処理の詳細を示すフロー図
【図37】テスト対象回路の例を示す図
【図38】本発明の第18の実施形態に係るテストパターン生成方法を示すフロー図
【図39】本発明の第19の実施形態に係るテストパターン生成方法を示すフロー図
【図40】パス遅延故障用パターン生成方法で用いられる5値を示す図
【図41】パス遅延故障用パターン生成方法で用いられる含意表を示す図
【図42】パス遅延故障用パターン生成方法で用いられる経路活性化表を示す図
【図43】パス遅延故障用パターン生成方法における信号遷移の伝搬を示す図
【図44】パス遅延故障用パターン生成方法の実行例を示す図
【図45】検査系列を変換して得られるシリアルパターンを示す図
【図46】遷移故障用パターン生成方法で用いられる経路活性化表および含意表を示す図
【図47】遷移故障用パターン生成方法の実行例を示す図
【符号の説明】
【0363】
A…テストパターン生成システム
C…回路情報
P…テストパターン




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013