(57)【特許請求の範囲】
【請求項１】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定システムにおいて、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、入力方向に前記組合せ論理回路のネットリストをトレースすることにより、ファンインコーンを抽出し、前記ファンインコーンに含まれる論理状態の定まっていない信号線を、故障伝搬経路とし
て登録する第１の故障伝搬経路簡易検索手段と、
を備えたことを特徴とする故障伝搬経路推定システム。
【請求項２】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定するシステムにおいて、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索手段と、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索手段と、
検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録手段と、
を備えたことを特徴とする故障伝搬経路簡易検索システム。
【請求項３】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定システムにおいて、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、前記仮決定レベルが上限を超えた場合に、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を、入力方向にトレースし、前記トレースした信号線を故障伝搬経路として登録する第２の故障伝搬経路簡易検索手段と、
を備えたことを特徴とする故障伝搬経路推定システム。
【請求項４】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定するシステムにおいて、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索手段と、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索手段と、
検索した入力信号線の中から、ゲートの機能とゲートの入出力端子の期待値を参照して、ゲートの出力論理状態を故障状態にする可能性のある入力信号線を検索する故障伝搬経路判定手段と、
検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録手段と、
を備えたことを特徴とする故障伝搬経路簡易検索システム。
【請求項５】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、前記仮決定レベルが上限を超えた場合に高速に処理を行う簡易的な故障伝搬経路の検索に切り替えるステップと、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、入力方向に、前記組合せ論理回路のネットリストをトレースすることにより、ファンインコーンを抽出し、前記ファンインコーンに含まれる論理状態の定まっていない信号線を故障伝搬経路として登録するステップ、
とを含む、ことを特徴とする故障伝搬経路抽出方法。
【請求項６】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索するステップと、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索し、検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録するステップと、
を含む、ことを特徴とする故障伝搬経路簡易検索方法。
【請求項７】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
論理状態の仮決定の回数を表す仮決定レベルに上限を設けて、仮決定レベルが上限を超えた場合に高速に処理を行う簡易的な故障伝搬経路の検索に切り替えるステップと、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を入力方向にトレースし、前記トレースした信号線を故障伝搬経路として登録するステップと、
を含む、ことを特徴とする故障伝搬経路抽出方法。
【請求項８】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索して、未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索するステップと、
検索した入力信号線の中から、ゲートの機能とゲートの入出力端子の期待値を参照して、ゲートの出力論理状態を故障状態にする可能性のある入力信号線を検索し、検索した信号線の論理状態を故障状態として、論理状態記憶部に記録するステップと、
を含む、ことを特徴とする故障伝搬経路簡易検索方法。
【請求項９】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
論理状態の仮決定の回数を表す仮決定レベルに上限を設けて、仮決定レベルが上限を超えた場合に高速に処理を行う簡易的な故障伝搬経路の検索に切り替える仮決定制限判定処理と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから入力方向に、前記組合せ論理回路のネットリストをトレースすることにより、ファンインコーンを抽出し、前記ファンインコーンに含まれる論理状態の定まっていない信号線を故障伝搬経路として登録する第１の故障伝搬経路簡易検索処理と、
の各処理を前記コンピュータに実行させるためのプログラム。
【請求項１０】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索処理と、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索処理と、検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録処理と、
の各処理を前記コンピュータに実行させるためのプログラム。
【請求項１１】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
論理状態の仮決定の回数を表す仮決定レベルに上限を設けて、仮決定レベルが上限を超えた場合に高速に処理を行う簡易的な故障伝搬経路の検索に切り替える仮決定制限判定処理と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を入力方向にトレースしてトレースした信号線を故障伝搬経路として登録する第２の故障伝搬経路簡易検索処理と、
の各処理を前記コンピュータに実行させるためのプログラム。
【請求項１２】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索処理と、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索処理と、
検索した入力信号線の中から、ゲートの機能とゲートの入出力端子の期待値を参照して、ゲートの出力論理状態を故障状態にする可能性のある入力信号線を検索する故障伝搬経路判定処理と、
検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録処理と、
の各処理をコンピュータに実行させるためのプログラム。
【請求項１３】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定方法であって、
（ａ）入力装置から与えられた前記組合せ論理回路の入出力端子の論理状態を設定し、論理状態の仮決定の回数を表す仮決定レベルを初期化するとともに、仮決定レベルの上限値を設定するステップと、
（ｂ）前記組合せ論理回路内の各ゲートにおいて既推定のゲートの入出力信号線の論理状態より、未推定のゲートの入出力線の論理状態を推定する含意操作を行い、推定された論理状態を論理状態記憶部に記録し、仮決定レベル及び含意操作の履歴を仮決定状態記憶部に記録するステップと、
（ｃ）前記含意操作における論理矛盾が許容回数を許容回数を越えていない場合、前記論理状態記憶部に記憶されている信号線の論理状態を参照し、全信号線の論理状態が、第１、第２の論理値、ドントケアのいずれかの論理状態に推定されたか否かを判定するステップと、
（ｄ）全信号線の論理状態の推定が終了していない場合に、前記組合せ論理回路内のゲートの入出力の論理状態を調べ、論理状態が不完全な未確定ゲートを検索するステップと、
（ｅ）検索した未確定ゲートの中から、論理回路構成記憶部に記憶されている論理回路構成、及び前記論理状態記憶部に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索するステップと、
（ｆ）仮決定レベルがその上限値を超えているか否かを判定するステップと、
（ｇ）仮決定レベルがその上限値を超えていない場合、論理値仮決定手段において検出した信号線に対して第１論理値と仮決定を行い、仮決定の回数を表す仮決定レベルを１つ増加し、前記ステップ（ｂ）に戻るステップと、
（ｈ）仮決定レベルがその上限値を超えている場合、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索し、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索し、
検索した信号線の論理状態を故障状態として、前記論理状態記憶部に記録する処理よりなる第１の故障伝搬経路簡易検索を実行するステップと、
（ｉ）全信号線の論理状態が推定されたと判定された場合には、期待値と異なる状態を持つ信号線を、故障伝搬経路として抽出し、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出し、出力装置に出力するステップと、
（ｊ）仮決定を行った全仮決定線に対して、第１、第２の論理値の両方の仮決定処理が終了しているか否かを判定するステップと、
（ｋ）仮決定処理が終了していないと判定された場合、バックトラック処理により、論理状態が第２の論理値と仮決定されていない仮決定線を検索し、仮決定線の状態を第２の論理値と仮決定し、前記ステップ（ｂ）の含意操作処理に戻るステップと、
（ｌ）仮決定処理が終了していると判定された場合には、故障伝搬経路の抽出処理を終了するステップと、
を含むことを特徴とする故障伝搬経路推定方法。
【請求項１４】
論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定方法であって、
（ａ）入力装置から与えられた前記組合せ論理回路の入出力端子の論理状態を設定し、論理状態の仮決定の回数を表す仮決定レベルを初期化するとともに、仮決定レベルの上限値を設定するステップと、
（ｂ）前記組合せ論理回路内の各ゲートにおいて既推定のゲートの入出力信号線の論理状態より、未推定のゲートの入出力線の論理状態を推定する含意操作を行い、推定された論理状態を論理状態記憶部に記録し、仮決定レベル及び含意操作の履歴を仮決定状態記憶部に記録するステップと、
（ｃ）前記含意操作における論理矛盾が許容回数を許容回数を越えていない場合、前記論理状態記憶部に記憶されている信号線の論理状態を参照し、全信号線の論理状態が、第１、第２の論理値、ドントケアのいずれかの論理状態に推定されたか否かを判定するステップと、
（ｄ）全信号線の論理状態の推定が終了していない場合に、前記組合せ論理回路内のゲートの入出力の論理状態を調べ、論理状態が不完全な未確定ゲートを検索するステップと、
（ｅ）検索した未確定ゲートの中から、論理回路構成記憶部に記憶されている論理回路構成、及び前記論理状態記憶部に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索するステップと、
（ｆ）仮決定レベルがその上限値を超えているか否かを判定するステップと、
（ｇ）仮決定レベルがその上限値を超えていない場合、論理値仮決定手段において検出した信号線に対して第１論理値と仮決定を行い、仮決定の回数を表す仮決定レベルを１つ増加し、前記ステップ（ｂ）に戻るステップと、
（ｈ）仮決定レベルがその上限値を超えている場合、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索し、
前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索し、
検索した入力信号線の中から、ゲートの機能とゲートの入出力端子の期待値を参照して、ゲートの出力論理状態を故障状態にする可能性のある入力信号線を検索し、
検索した信号線の論理状態を故障状態とし、前記論理状態記憶部に記録する処理よりなる第２の故障伝搬経路簡易検索を実行するステップと、
（ｉ）全信号線の論理状態が推定されたと判定された場合には、期待値と異なる状態を持つ信号線を、故障伝搬経路として抽出し、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出し、出力装置に出力するステップと、
（ｊ）仮決定を行った全仮決定線に対して、第１、第２の論理値の両方の仮決定処理が終了しているか否かを判定するステップと、
（ｋ）仮決定処理が終了していないと判定された場合、バックトラック処理により、論理状態が第２の論理値と仮決定されていない仮決定線を検索し、仮決定線の状態を第２の論理値と仮決定し、前記ステップ（ｂ）の含意操作処理に戻るステップと、
（ｌ）仮決定処理が終了していると判定された場合には、故障伝搬経路の抽出処理を終了するステップと、
を含むことを特徴とする故障伝搬経路推定方法。
【請求項１５】
論理回路の構成及び接続情報を記憶している論理回路構成記憶部と、
含意操作処理中に論理矛盾が生じたゲートと論理矛盾の回数を記憶する論理矛盾記憶部と、
各信号線の論理状態が含意操作により推定された時点における仮決定レベルを記憶する仮決定状態記憶部と、
各信号線における論理状態、含意操作の履歴、及び、前記組合せ論理回路が正常である時の各信号線の論理状態である期待値を記憶する論理状態記憶部と、
入力装置から与えられた論理回路の種類、入出力端子の論理状態の設定を行い、前記論理回路の信号線の論理状態を初期化し、仮決定レベルの初期化及びその上限値の設定を行う初期設定手段と、
前記論理回路構成記憶部に記憶されている論理回路構成、及び前記論理状態記憶部に記憶されている各信号線の論理状態を参照して、前記初期設定手段で設定された入出力信号線に接続されたゲート、及び、論理値仮決定手段において仮決定した信号線に接続されたゲートにおいて含意操作を行い、ゲートの入出力信号線の論理状態の推定を行い、論理値が新たに推定された場合は、その論理値及び含意操作の履歴を前記論理状態記憶部に記録し、さらに、前記仮決定状態記憶部に、その推定が何回の仮決定の下に推定されたかを示す仮決定レベルを記録する含意操作手段と、
前記論理矛盾記憶部を参照して、含意操作手段において検出された信号線の論理矛盾の回数が予め定められた許容回数を越えているか否か判定する論理矛盾判定手段と、
前記論理状態記憶部に記憶された各信号線の論理状態を参照して、全信号線の論理状態が推定されたか否かの判定を行う処理終了判定手段と、
仮決定状態記憶部に記憶された仮決定状態と、前記論理状態記憶部に記憶された信号線の論理状態とを参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を仮決定を行う前の論理状態に戻すバックトラック手段と、
論理回路内のゲートの入出力の論理状態を調べ、論理状態が不完全なゲートを検索する未確定ゲート検索手段と、
前記未確定ゲート検索手段において検索された未確定ゲートの中から、論理回路構成記憶部に記憶されている論理回路構成、及び前記論理状態記憶部に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索する故障伝搬経路影響線検索手段と、
次の仮決定が予め定められた仮決定の上限値を超えているか否かを判定する仮決定制限判定手段と、
前記故障伝搬経路影響線検索手段において検出した出力信号が故障状態であるような未確定ゲートの入力信号線を選択して論理状態を決定する論理値仮決定手段と、
未確定ゲートから、入力方向に、回路をトレースして、ファンインコーンを抽出し、ファンインコーンの中に含まれる経路の内、論理状態の定まっていない信号線を全て故障伝搬経路として、論理状態記憶部に登録する第１の故障伝搬経路簡易検索手段と、
前記求めた各信号線の論理状態を、正常回路において論理シミュレーションによって求めた各信号線の論理状態を表す期待値と比較して、故障伝搬経路を抽出する論理値比較手段と、
前記論理値比較手段において抽出された故障伝搬経路の内、その経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出して、出力装置に、データを出力する故障出力端子関係線抽出手段と、
を備えたことを特徴とする故障伝搬経路推定装置。
【請求項１６】
前記第１の故障伝搬経路簡易検索手段が、未処理ゲート検索手段と、入力信号線検索手段と、故障伝搬経路登録手段とを備え、
前記未処理ゲート検索手段は、前記論理回路構成記憶部及び前記論理状態記憶部を参照して、前記故障伝搬経路影響線検索手段において検出された、出力信号が故障状態であるような未確定ゲート、及び、前記故障伝搬経路登録手段において登録された、信号線の入力側ゲートのうち、故障伝搬経路簡易検索がまだ施されていないゲートを検索し、
前記入力信号線検索手段は、前記未処理ゲート検索手段で検索された未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索し、
前記故障伝搬経路登録手段は、前記入力信号線検索手段において検索された信号線の論理状態を故障状態とし、前記論理状態記憶部に記録する、ことを特徴とする請求項１５記載の故障伝搬経路推定装置。
【請求項１７】
論理回路の構成及び接続情報を記憶している論理回路構成記憶部と、
含意操作処理中に論理矛盾が生じたゲートと論理矛盾の回数を記憶する論理矛盾記憶部と、
各信号線の論理状態が含意操作により推定された時点における仮決定レベルを記憶する仮決定状態記憶部と、
各信号線における論理状態、含意操作の履歴、及び、前記組合せ論理回路が正常である時の各信号線の論理状態である期待値を記憶する論理状態記憶部と、
入力装置から与えられた論理回路の種類、入出力端子の論理状態の設定を行い、前記論理回路の信号線の論理状態を初期化し、仮決定レベルの初期化及びその上限値の設定を行う初期設定手段と、
前記論理回路構成記憶部に記憶されている論理回路構成、及び論理状態記憶部に記憶されている各信号線の論理状態を参照して、前記初期設定手段で設定された入出力信号線に接続されたゲート、及び、論理値仮決定手段において仮決定した信号線に接続されたゲートにおいて含意操作を行い、ゲートの入出力信号線の論理状態の推定を行い、論理値が新たに推定された場合は、その論理値及び含意操作の履歴を前記論理状態記憶部に記録し、さらに、前記仮決定状態記憶部に、その推定が何回の仮決定の下に推定されたかを示す仮決定レベルを記録する含意操作手段と、
前記論理矛盾記憶部を参照して、含意操作手段において検出された信号線の論理矛盾の回数が予め定められた許容回数を越えているか否か判定する論理矛盾判定手段と、
前記論理状態記憶部に記憶された各信号線の論理状態を参照して、全信号線の論理状態が推定されたか否かの判定を行う処理終了判定手段と、
仮決定状態記憶部に記憶された仮決定状態と、前記論理状態記憶部に記憶された信号線の論理状態とを参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を仮決定を行う前の論理状態に戻すバックトラック手段と、
組合せ回路内のゲートの入出力の論理状態を調べ、論理状態が不完全なゲートを検索する未確定ゲート検索手段と、
前記未確定ゲート検索手段において検索された未確定ゲートの中から、論理回路構成記憶部に記憶されている論理回路構成、及び前記論理状態記憶部に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索する故障伝搬経路影響線検索手段と、
次の仮決定が予め定められた仮決定の上限値を超えているか否かを判定する仮決定制限判定手段と、
前記故障伝搬経路影響線検索手段において検出した出力信号が故障状態であるような未確定ゲートの入力信号線を選択して論理状態を決定する論理値仮決定手段と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を、入力方向にトレースし、前記トレースした信号線を故障伝搬経路として登録する第２の故障伝搬経路簡易検索手段と、
前記求めた各信号線の論理状態を、正常回路において論理シミュレーションによって求めた各信号線の論理状態を表す期待値と比較して、故障伝搬経路を抽出する論理値比較手段と、
前記論理値比較手段において抽出された故障伝搬経路の内、その経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出して、出力装置に、データを出力する故障出力端子関係線抽出手段と、
を備えたことを特徴とする故障伝搬経路推定装置。
【請求項１８】
前記第２の故障伝搬経路簡易検索手段が、未処理ゲート検索手段と、入力信号線検索手段と、故障伝搬経路判定手段と、故障伝搬経路登録手段とを備え、
前記未処理ゲート検索手段は、前記論理回路構成記憶部及び前記論理状態記憶部を参照して、前記故障伝搬経路影響線検索手段において検出された、出力信号が故障状態であるような未確定ゲート、及び、前記故障伝搬経路登録手段において登録された、信号線の入力側ゲートのうち、故障伝搬経路簡易検索がまだ施されていないゲートを検索し、
前記入力信号線検索手段は、前記未処理ゲート検索手段で検索された未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索し、
前記故障伝搬経路判定手段は、前記論理回路構成記憶部に記憶されているゲートの機能と論理状態記憶部に記憶されているゲートの入出力端子の期待値を参照して、前記入力信号線検索手段で検索した入力信号線の中から、ゲートの出力論理値を故障状態にする可能性のある入力信号線を検索し、
前記故障伝搬経路登録手段は、前記故障伝搬経路判定手段において検索された信号線の論理状態を故障状態とし、前記論理状態記憶部に記録する、ことを特徴とする請求項１７記載の故障伝搬経路推定装置。
【請求項１９】
論理値の仮定と含意操作を繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作する時の論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定システムにおいて、
予め定められた仮決定制限再設定条件が満たされているか否かを判定し、前記仮決定制限再設定条件を満たしている場合には、論理状態の仮決定の回数を表す仮決定レベルを再設定し、仮決定の回数が再設定された仮決定制限値以下となる論理状態に戻す仮決定制限変更手段と、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、入力方向に前記組合せ論理回路のネットリストをトレースすることにより、ファンインコーンを抽出し、前記ファンインコーンに含まれる論理状態の定まっていない信号線を、故障伝搬経路として登録する第１の故障伝搬経路簡易検索手段、あるいは、
ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を、入力方向にトレースし、前記トレースした信号線を故障伝搬経路として登録する第２故障伝搬経路簡易検索手段と、を備えたことを特徴とする故障伝搬経路推定システム。
【請求項２０】
前記仮決定制限変更手段が、前記仮決定制限再設定条件として、推定処理時間の上限値を予め定めておき、推定処理時間が前記推定処理時間の上限値を越えているか否かを判定する仮決定制限再設定条件判定手段と、
前記仮決定制限再設定条件を満たした場合に、仮決定制限値を再設定する仮決定制限再設定手段と、
仮決定の回数が、前記仮決定制限再設定手段において再設定された前記仮決定制限値を越える場合に、既に推定処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が前記仮決定制限値を越える前の論理状態に戻すバックトラック手段と、
を備えることを特徴とする請求項１９記載の故障伝搬経路推定システム。
【請求項２１】
論理値の仮定と含意操作を繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作する時の論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定するシステムにおいて、
予め仮決定制限再設定条件として、推定処理時間の上限値を定めておき、推定処理時間が前記推定処理時間の上限値を越えているか否かを判定する仮決定制限再設定条件判定手段と、
前記仮決定制限再設定条件を満たした場合に、仮決定制限値を再設定する仮決定制限再設定手段と、
仮決定の回数が、前記仮決定制限再設定手段において再設定された前記仮決定制限値を越える場合に、既に推定処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が前記仮決定制限値を越える前の論理状態に戻すバックトラック手段と、
を備えたことを特徴とする仮決定制限再設定システム。
【請求項２２】
論理値の仮定と含意操作を繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作する時の論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
予め定めておいた仮決定制限再設定条件が満たされているか否かを判定し、前記仮決定制限再設定条件を満たしている場合には、論理状態の仮決定の回数を表す仮決定レベルを再設定し、仮決定の回数が再設定された仮決定制限値以下となる論理状態に戻すステップと、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替えるステップと、
請求項６または請求項８に記載された故障伝搬経路簡易検索を行うステップと、を含む、ことを特徴とする故障伝搬経路推定方法。
【請求項２３】
論理値の仮定と含意操作を繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作する時の論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する方法において、
予め仮決定制限再設定条件として、推定処理時間の上限値を定めておき、推定処理時間が前記推定処理時間の上限値を越えているか否かを判定するステップと、
前記仮決定制限再設定条件を満たした場合に、仮決定制限値を再設定するステップと、
仮決定の回数が、前記仮決定制限再設定手段において再設定された前記仮決定制限値を越える場合に、既に推定処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が前記仮決定制限値を越える前の論理状態に戻すステップと、
を含む、ことを特徴とする仮決定制限再設定方法。
【請求項２４】
論理値の仮定と含意操作とを繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
予め定めておいた仮決定制限再設定条件が満たされているか否かを判定し、前記仮決定制限再設定条件を満たしている場合は、論理状態の仮決定の回数を表す仮決定レベルを再設定し、仮決定の回数が再設定された仮決定制限値以下となる論理状態に戻す仮決定制限変更処理と、
論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定処理と、
請求項１０または請求項１２に記載された故障伝搬経路簡易検索処理と、
の各処理をコンピュータに実行させるためのプログラム。
【請求項２５】
論理値の仮定と含意操作とを繰り返して組合せ回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定処理をコンピュータで実行させるためのプログラムであって、
予め仮決定制限再設定条件として、推定処理時間の上限値を定めておき、推定処理時間が前記推定処理時間の上限値を越えているか否かを判定する仮決定制限再設定条件判定処理と、前記仮決定制限再設定条件を満たした場合に、仮決定制限値を再設定する仮決定制限再設定処理と、
仮決定の回数が、前記仮決定制限再設定処理において再設定された前記仮決定制限値を越える場合に、既に推定処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が前記仮決定制限値を越える前の論理状態に戻すバックトラック処理と、
の各処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は組合せ論理回路において、故障が伝搬している可能性のある経路を高速に求める故障伝搬経路推定システムと方法、並びにコンピュータに故障伝搬経路推定を実行させるプログラムに関する。
【０００２】
【従来の技術】
故障伝搬経路推定技術は、故障出力を含む出力パターンを満足するような故障が伝搬している可能性のある経路を推定するものであり、例えば特開平０８−１４６０９３号（特許第２６５５１０５号）公報、あるいは特開平１０−０６２４９４号（特許第２９２１５０２号）公報等に記載されているように、順序回路の故障箇所推定システムの一部として使用可能である。この時、故障は、組合せ回路内部に存在してもよいし、あるいは、入力パターンに故障状態が含まれていてもよい。
【０００３】
従来の故障伝搬経路推定システムとしては、Ｄｏｎ’ｔ  Ｃａｒｅ（ドントケア）を導入したバックトラック方式を利用した逆論理展開方式を利用することができる（特開平１０−１５４１７１号（特許第２９５６６２４号）公報参照）。これは、逆論理展開により求めた入力推定状態とその過程で求めた組合せ論理回路内部の論理状態を予め正常回路における論理シミュレーションによって求めておいた期待値と比較することで故障伝搬経路を抽出する方法である。特開平１０−１５４１７１号（特許第２９５６６２４号）公報に記載された方法によれば、出力論理状態を満足するような入力論理状態を全て求めることが可能であり、論理シミュレーションによって求めた期待値と比較することで、故障伝搬経路を抽出することができる。
【０００４】
しかしながら、乗算回路などでは、仮決定の回数が膨大になり、計算時間が長時間に渡ることが予想される。
【０００５】
そこで、回路内部の信号線の論理状態の推定において、信号線に対する論理値の仮決定（Ｄｅｃｉｓｉｏｎ）を故障伝搬経路に関係する信号線に限定することによって処理を高速化した故障伝搬経路抽出システム（特開平１１−１５３６４６号公報）が提案されている。
【０００６】
特開平１１−１５３６４６号公報に提案されている故障伝搬経路抽出システムの構成について、図１６を参照して説明する。図１６を参照すると、この従来の故障伝搬経路抽出システムは、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、ハードディスクやメモリなどの情報を記憶する記憶装置４と、ディスプレイ装置や印刷装置などの出力装置５とを含む。
【０００７】
記憶装置４は、論理回路構成記憶部４１と、論理矛盾記憶部４２と、仮決定状態記憶部４３と、論理状態記憶部４４とを備えている。
【０００８】
論理回路構成記憶部４１は、論理回路の構成、すなわち、ゲートの種類、ゲート同士の接続関係、ゲートと信号線の接続関係、信号線同士の接続関係など、論理回路の構成を予め記憶している。
【０００９】
論理矛盾記憶部４２は、含意操作処理中に論理矛盾が生じたゲートと論理矛盾の回数を記憶している。
【００１０】
仮決定状態記憶部４３は、何回の仮決定を行なったかを表す仮決定レベル、各信号線の論理状態が含意操作により推定された時点における仮決定レベルを記憶している。
【００１１】
論理状態記憶部４４は、処理中の各信号線における論理状態、含意操作の履歴、及び、回路が正常である時の各信号線の論理状態（期待値）を記憶している。
【００１２】
データ処理装置２は、初期設定手段２１と、含意操作手段２２と、論理矛盾判定手段２３と、処理終了判定手段２４と、バックトラック手段２５と、未確定ゲート検索手段２６と、故障伝搬経路関係線検索手段２７と、論理値仮決定手段２９と、論理値比較手段３１と、故障出力端子関係線抽出手段３２と、を備える。初期設定手段２１は、入力装置１から与えられた論理回路の種類、入出力端子の論理状態の設定を行い、信号線の論理状態を初期化する。また、仮決定レベルの初期化や上限値の設定も、初期設定手段２１で行う。
【００１３】
含意操作手段２２は、論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、初期設定手段２１で設定された入出力信号線に接続されたゲート、及び、論理値仮決定手段２９において仮決定した信号線に接続されたゲートにおいて、含意操作を行い、ゲートの入出力信号線の論理状態の推定を行う。
【００１４】
このとき、含意操作手段２２において、論理値が新たに推定された場合には、その論理値及び含意操作の履歴を論理状態記憶部４４に記録し、さらに、仮決定状態記憶部４３に、その推定が何回の仮決定の下に推定されたかを示す仮決定レベルを記録する。
【００１５】
含意操作手段２２において、含意操作中に論理矛盾が生じた場合には、論理矛盾記憶部４２を参照して、論理矛盾の回数が、予め定められた所定の許容回数を越えているか否か判定する。なお、論理矛盾の回数が許容回数を越えている場合には、回路内部の論理状態の推定精度を高めるために、論理回路構成記憶部４１と、論理矛盾記憶部４２及び論理状態記憶部４４に記憶されている含意操作の履歴を参照して、論理矛盾の原因となっている信号線の論理状態を初期化し、その結果に従って、論理矛盾記憶部４２、仮決定状態記憶部４３、論理状態記憶部４４の情報を更新する、などの処理を行ってもよい。
【００１６】
論理矛盾判定手段２３は、論理矛盾記憶部４２を参照して、含意操作手段２２において検出された信号線の論理矛盾の回数が、予め定められた許容回数を越えているか否かを判定する。
【００１７】
処理終了判定手段２４は、論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、全信号線の論理状態が推定されたか否かの判定を行う。
【００１８】
バックトラック手段２５は、仮決定状態記憶部４３に記憶されている仮決定状態と、論理状態記憶部４４に記憶されている信号線の論理状態を参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定を行う前の論理状態に戻す。
【００１９】
未確定ゲート検索手段２６は、組合せ回路内のゲートの入出力の論理状態を調べ、論理状態が不完全なゲートを検索する。例えば、ＮＡＮＤゲートにおいて、出力信号が｀１’の場合、入力信号の一つが必ず｀０’であるが、入力信号線の論理状態が決まっておらず、どの入力信号線が｀０’であるかわからない時、そのゲートの入出力論理状態は不完全であり、当該ゲートは、未確定ゲートとなる。
【００２０】
故障伝搬経路影響線検索手段２７は、未確定ゲート検索手段２６において検索された未確定ゲートの中から、論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号を持つ未確定ゲートを検索する。
【００２１】
論理値仮決定手段２９は、故障伝搬経路影響線検索手段２７において検出された、出力信号が故障状態であるような未確定ゲートの入力信号線を選択して、論理状態を決定する。
【００２２】
論理値比較手段３１は、求めた各信号線の論理状態を、正常な回路において論理シミュレーションによって求めた各信号線の論理状態を表す期待値と比較して、故障伝搬経路を抽出する。
【００２３】
故障出力端子関係線抽出手段３２は、論理値比較手段３１において抽出された故障伝搬経路の内、その経路上に故障が存在する時に、故障出力端子に、直接影響を与えるような故障伝搬経路を抽出して、出力装置５に、データを出力する。
【００２４】
図１７は、従来の従来の故障伝搬経路抽出システムの動作を説明するためのフローチャートである。図１６、図１７、及び図７を参照して、従来の故障伝搬経路抽出システムの動作について説明する。
【００２５】
入力装置１から与えられた入出力端子の論理状態を、初期設定手段２１において設定し、仮決定の回数を表す仮決定レベル（ｄｌｅｖｅｌ）を初期化する（図１７のステップＡ１及びステップＡ２）。
【００２６】
次に含意操作手段２２において含意操作を行う（ステップＡ４）。含意操作とは、各ゲートにおいて既推定のゲートの入出力信号線の論理状態より、未推定のゲートの入出力線の論理状態を推定する操作である。含意操作が可能なゲート、すなわち、ゲートの機能と、該ゲートに接続されかつ既に論理状態が確定している入出力信号線の論理状態を用いて、該ゲートに接続された未だ論理状態が決定していない入出力信号線の論理状態を含意できるようなゲートを検索する。
【００２７】
そして、検出されたゲートにおいて入出力信号線の論理状態の推定を行う。推定された論理状態は論理状態記憶部４１に記録され、そのときの仮決定レベル、及び、含意操作の履歴と共に仮決定状態記憶部４３に記録される。
【００２８】
具体例として、２入力ＮＡＮＤゲートにおける含意操作を図７に示す。図７（ａ）は、２入力ＮＡＮＤゲートの入力信号線の論理状態が決定される場合の出力信号線の論理状態推定結果を示しており、図７（ｂ）は、２入力ＮＡＮＤゲートの出力信号線の論理状態が決定されている場合の入力信号線の論理状態推定結果を示している。図７（ａ）を参照すると、ＮＡＮＤゲートの場合、入力信号線に論理状態｀０’が１つでも存在すれば、出力信号線の論理状態は｀１’と推定され、また入力信号線に論理状態が全て｀１’であれば、出力信号線の論理状態は｀０’と推定される。また図７（ｂ）に示すように、２入力ＮＡＮＤゲートの出力信号線の論理状態が｀０’であれば、入力信号線の論理状態は全て｀１’と推定され、２入力ＮＡＮＤゲートの出力信号線の論理状態が｀１’であり、一方の入力信号線の論理状態が｀１’であれば、入力信号線の論理状態は｀０’と推定される。
【００２９】
論理矛盾判定手段２３により、論理矛盾記憶部４２を参照して、論理矛盾が許容回数を越えているか否かを判定する（図１７のステップＡ５）。
【００３０】
論理矛盾判定手段２３において、矛盾が許容回数を越えていなければ、処理終了判定手段２４により、論理状態記憶部４４に記憶されている信号線の論理状態を参照し、全信号線の論理状態が｀０’，  ｀１’または｀Ｘ’に推定されたかを判定する（ステップＡ６）。矛盾が許容回数を超えていれば、現在の仮決定では故障伝搬経路が求まらないということであるので、ステップＡ１２の処理に移る。
【００３１】
ステップＡ６において、全信号線の論理状態推定が終了していないと判定した場合に、未確定ゲート検索手段２６おいて、組合せ回路内のゲートの入出力の論理状態を調べ、論理状態が不完全な未確定ゲートを検索する（ステップＡ７）。
【００３２】
次に、故障伝搬経路影響線検索手段２７において、ステップＡ６で検索した未確定ゲートの中から、論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索する（ステップＡ８）。
【００３３】
論理値仮決定手段２９において検出した信号線に対して、｀０’と仮決定を行い、仮決定の回数を表す仮決定レベル（ｄｌｅｖｅｌ）を１つ増加し（ステップＡ１０）、含意操作手段２２による含意操作処理（ステップＡ４）に戻る。
【００３４】
ステップＡ６において、処理終了判定手段２５によって全信号線の論理状態が推定されたと判定された場合には、回路内部の論理状態が｀０’，  ｀１’または｀Ｘ’に定まったわけであるから、論理値比較手段３１（ステップＡ１２）において、期待値と異なる状態を持つ信号線、すなわち、故障伝搬経路を抽出する。さらに、故障出力端子関係線抽出手段３２において、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出し、出力装置５に出力する（ステップＡ１３）。
【００３５】
次に、仮決定を行った全仮決定線に対して、｀０’と｀１’の両方の仮決定処理が終了しているかを判定する（ステップＡ１４）。ステップＡ１４において、全信号線の論理状態が推定されたと判定された時には、組合せ論理回路内部の信号線の論理状態は｀０’，  ｀１’または｀Ｘ’と推定されている。論理矛盾判定手段２４において矛盾が検出された場合にも、ステップＡ１４の判定処理を行う。
【００３６】
処理終了判定手段２４（ステップＡ１４）において、仮決定処理が終了していないと判定された場合には、バックトラック手段２５において、状態｀１’と仮決定していない仮決定線を仮決定レベルの大きい方から一つ検索し、検出された仮決定線の仮決定レベル以上の仮決定において推定された信号線の論理状態を初期化して、各信号線の論理状態をその仮決定を行う前の論理状態に戻し（ステップＡ１５）、論理値仮決定手段２９において、バックトラック手段２５で検出された仮決定線の状態を｀１’と仮決定し（ステップＡ１６）、含意操作手段２２による含意操作処理（ステップＡ４）に戻る。
【００３７】
処理終了判定手段２４（ステップＡ１２）において、仮決定処理が終了していると判定された場合には、故障伝搬経路抽出処理を終了する。
【００３８】
従来の故障伝搬経路抽出システムについて、図１６、図１７、図８、及び、図１８を参照して詳細に説明する。具体例として、図８に示した組み合わせ回路に適用する場合を説明する。
【００３９】
初期状態として、対象ゲートの入出力端子の期待値と出力信号の論理値（Ｌ２２＝１，  Ｌ２３＝１）が与えられている場合を考える。従って、Ｌ２３が故障出力である。
【００４０】
最初に、初期設定手段２１において、入出力端子及び信号線の論理状態と期待値を設定する。Ｌ１＝Ｘ［１］，  Ｌ２＝Ｘ［１］，  Ｌ３＝Ｘ［１］，  Ｌ６＝Ｘ［１］，  Ｌ７＝Ｘ［１］，  Ｌ２２＝１［１］，  Ｌ２３＝１［０］が設定される。なお、括弧［］内の数字は期待値を表している。（図１７のステップＡ１）。
【００４１】
仮決定レベル（ｄｌｅｖｅｌ）を初期化し（図１７のステップＡ２）、次にステップＡ４において、第１の含意操作手段２２によって、論理回路内部の信号線の論理値を求める。ここでは、Ｌ２２＝１，Ｌ２３＝１によって含意される信号線はない。論理矛盾は生じないので、論理矛盾判定手段２３（ステップＡ５）で論理矛盾はないと判断する。
【００４２】
Ｌ２３の故障出力の原因となる故障伝搬経路は求まっていないので、処理終了判定手段２４（ステップＡ６）において、処理は終了していないと判定され、ステップＡ７に処理を移る。
【００４３】
ステップＡ７において、未確定ゲート検索手段２６によって、出力信号１を持ち、入力信号にまだ０が推定されていないＮＡＮＤゲートであるＧ２２，  Ｇ２３が未確定ゲートとして検索される。
【００４４】
ステップＡ８において、故障伝搬経路影響線検索手段２７によって、故障信号線を出力信号としてもつ未確定ゲートＧ２３の入力信号線の中から、論理値が定まっていない信号線として、Ｌ１６を選ぶ。
【００４５】
ステップＡ８において、検出された信号線Ｌ１６の論理値を｀０’と仮決定し、仮決定レベルを１だけ増やす（ステップＡ１０）。
【００４６】
ステップＡ４の含意操作では、Ｌ１６＝０から、Ｇ１６において、Ｌ２＝１，  Ｌ１１＝１が含意される。
【００４７】
ステップＡ５において、論理矛盾は検出されず、推定は終了していないため、ステップＡ７に処理を移る。
【００４８】
ステップＡ７では、未確定ゲートとして、Ｇ１１が検出され、さらに、ステップＡ８において、Ｇ１１は出力信号として故障信号が推定されているため、その入力信号線Ｌ３が選ばれる。
【００４９】
ステップＡ８において、検出された信号線Ｌ３の論理値を｀０’と仮決定し、仮決定レベルを１だけ増やす（ステップＡ１０）。
【００５０】
ステップＡ４の含意操作では、Ｌ３＝０から、Ｇ１０において、Ｌ１０＝１が含意される。
【００５１】
ステップＡ５において、論理矛盾は検出されず、論理状態は全て定まったので、ステップＡ６において、論理状態推定が終了したと判定され、ステップＡ１２に処理を移る。
【００５２】
論理値比較手段３１（ステップＡ１２）において、期待値と異なる状態を持つ信号線、すなわち、故障伝搬経路を抽出する。その結果、Ｌ３，  Ｌ１１，  Ｌ１６，  Ｌ２３が故障伝搬経路として抽出される。
【００５３】
さらに、故障出力端子関係線抽出手段３２において、Ｌ３，  Ｌ１１，  Ｌ１６，  Ｌ２３は、故障伝搬経路の中から経路上に故障が存在する時に、故障出力端子に直接影響を与えるような故障伝搬経路であることから、これらを出力装置５に出力する（ステップＡ１３）。
【００５４】
ステップＡ１４において、Ｌ３は仮決定線として１と仮決定されていないため、処理は終了していないと判定されて、ステップＡ１５に処理を移す。
【００５５】
バックトラック手段２５により、Ｌ３の仮決定の直前の状態に戻す。従って、仮決定レベルは１となり、論理値が定まっている信号線は、Ｌ２２＝１，  Ｌ２３＝１，  Ｌ１６＝０，  Ｌ２＝１，  Ｌ１１＝１となる（ステップＡ１５）。
【００５６】
今度は、Ｌ３＝１と仮決定を行い、仮決定レベルは、ｄｌｅｖｅｌ＝２となる（ステップＡ１６）。
【００５７】
次にステップＡ４において、論理状態設定手段２４によって、論理回路内部の信号線の論理値を求める。Ｇ１６における含意操作により、Ｌ６＝０が含意され、全信号線の論理値が求まる。
【００５８】
ステップＡ５において、矛盾は検出されず、論理状態の推定は終了し、ステップＡ１２に処理を移る。
【００５９】
ステップＡ１２において、論理比較手段３１によって期待値と比較することにより、Ｌ６，  Ｌ１１，  Ｌ１６，  Ｌ２３が故障伝搬経路として抽出される。
【００６０】
これらの経路は全て、故障出力端子Ｌ２３に、故障状態を伝搬することが可能であるため、これらの経路を出力装置５に出力する（ステップＡ１３）。
【００６１】
以上の処理を繰り返すことにより、出力Ｌ２２＝１，  Ｌ２３＝１を満足するような全ての論理状態を求めることができる。
【００６２】
図１８は、以上の処理を、木構造で表したものである。２箇所の信号線において仮決定を行い、３つの論理状態が求まり、それぞれの状態に対応した故障伝搬経路が求まる。仮決定レベル（ｄｌｅｖｅｌ）は、図１８に示すように、木構造の深さに相当する。
【００６３】
従来の故障伝搬経路抽出システムは、論理の仮決定と含意操作を繰り返すことにより、全ての故障伝搬経路を求めるものであるが、回路が大規模化、故障箇所、あるいは、入力するパターンによって、必要とする論理の仮決定の回数が大きく変化し、場合によっては、多数回の仮決定による長時間の処理が必要となる。
【００６４】
推定処理を実用的な処理時間内に収めるために、途中で処理を中断することも可能であるが、推定処理が実際の故障箇所に到達しない場合があり、この場合には、求めた故障伝搬経路を基にして作成した故障候補のリストに実際の故障が含まれない可能性があり、推定精度が低下する。
【００６５】
第一の問題点は、故障伝搬経路の推定処理が増大し、処理時間が長時間におよぶ可能性がある。その理由は、論理の仮決定の回数が増大するためである。
【００６６】
第二の問題点は、処理を途中で中断した場合に、故障伝搬経路の推定精度が低下する。その理由は、処理を中断することにより、推定処理が実際の故障箇所に到達しないため、故障伝搬経路に実際の故障が含まれないためである。
【００６７】
【発明が解決しようとする課題】
したがって、本発明が解決しようとする課題は、高速な故障伝搬経路推定システム及び方法並びにプログラムを提供することにある。
【００６８】
本発明が解決しようとする他の課題は、推定処理を中断した場合にも実際の故障が含まれるような故障伝搬経路推定できる故障伝搬経路推定システム及び方法並びにプログラムを提供することである。
【００６９】
【課題を解決するための手段】
前記課題を解決するための手段を提供する本発明は、論理状態の仮定と含意操作とを繰り返して組合せ論理回路内の論理状態を推定し、前記組合せ論理回路が正常動作するときの論理状態である期待値と比較することで、前記組合せ論理回路内の故障伝搬経路を推定する故障伝搬経路推定システムにおいて、論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、入力方向に前記組合せ論理回路のネットリストをトレースすることにより、ファンインコーンを抽出し、前記ファンインコーンに含まれる論理状態の定まっていない信号線を、故障伝搬経路として登録する第１の故障伝搬経路簡易検索手段と、を備えている。
【００７０】
本発明において、第１の故障伝搬経路簡易検索手段は、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索手段と、前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索手段と、検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録手段と、を備えて構成される。
【００７１】
また本発明は、論理状態の仮決定の回数を表す仮決定レベルに上限を設け、前記仮決定レベルが上限を超えた場合に、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートから、信号線の期待値とゲートの機能を参照しながら、未確定ゲートに故障状態を伝搬する可能性のある信号線を、入力方向にトレースし、前記トレースした信号線を故障伝搬経路として登録する第２の故障伝搬経路簡易検索手段と、を備える。
【００７２】
本発明において、第２の故障伝搬経路簡易検索手段は、ゲートの出力信号が故障状態であり、かつ、入出力信号線に論理状態がＵ（不定状態）である信号線を持つ未確定ゲートのうち故障伝搬経路簡易検索を施していない未処理ゲートを検索する未処理ゲート検索手段と、前記未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する入力信号線検索手段と、検索した入力信号線の中から、ゲートの機能とゲートの入出力端子の期待値を参照して、ゲートの出力論理状態を故障状態にする可能性のある入力信号線を検索する故障伝搬経路判定手段と、検索した信号線の論理状態を故障状態とし、論理状態記憶部に記録する故障伝搬経路登録手段と、を備える。
また、本発明の他のアスペクトに係るシステムは、予め定めておいた仮決定制限再設定条件が満たされているか否かを判定し、前記仮決定制限再設定条件を満たしている場合は、論理状態の仮決定の回数を表す仮決定レベルを再設定し、仮決定の回数が再設定された前記仮決定制限値以下となる論理状態に戻す仮決定制限変更手段と、論理状態の仮決定の回数を表す仮決定レベルに上限を設け、論理状態の仮決定の回数が前記仮決定レベルの上限を超えた場合に、論理状態の仮判定を、簡易的な故障伝搬経路の検索に切り替える仮決定制限判定手段と、前記第２の故障伝搬経路簡易検索手段、あるいは、前記第２の故障伝搬経路簡易検索手段と、を備える。
本発明において、仮決定制限変更手段は、予め仮決定制限再設定条件として、推定処理時間の上限値を定めておき、推定処理時間が前記推定処理時間の上限値を越えているか否かを判定する仮決定制限再設定条件判定手段と、前記仮決定制限再設定条件を満たした場合に、仮決定制限値を再設定する仮決定制限再設定手段と、仮決定の回数が、前記仮決定制限再設定手段において再設定された前記仮決定制限値を越える場合に、既に推定処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が前記仮決定制限値を越える前の論理状態に戻すバックトラック手段と、を備える。
以下の説明からも直ちに明らかとされるように、本願特許請求の範囲の各請求項の本発明は、いずれも、前記課題を解決するための手段を提供するものである。
【００７３】
【発明の実施の形態】
本発明の実施の形態について説明する。本発明は、論理の仮決定回数の上限を設定して、推定途中に仮決定回数が上限に達した場合には、簡易的な故障伝搬経路検索により、未確定ゲートから入力方向にファンインコーンをトレースして、ファンインコーン内の論理が定まっていない信号線を故障伝搬経路として登録するというものである。
【００７４】
より具体的には、データ処理装置（図１の２）において、仮決定制限判定手段（図１の２８）と、第１の故障伝搬経路簡易検索手段（図１の３０）と、を有する。第１の故障伝搬経路簡易検索手段（図１の３０）は、未処理ゲート検索手段（図２の３０１）と、入力信号線検索手段（図２の３０２）と、故障伝搬経路登録手段（図２の３０３）と、を有する。
【００７５】
また本発明は、論理の仮決定回数の上限を設定して、推定途中に仮決定回数が上限に達した場合には、簡易的な故障伝搬経路検索により、未確定ゲートに故障を伝搬する可能性のある信号線を故障伝搬経路として登録する、というものである。
【００７６】
より具体的には、データ処理装置（図１０の２）において、仮決定制限判定手段（図１０の２８）と第２の故障伝搬経路簡易検索手段（図１０の６０）とを有する。第２の故障伝搬経路簡易検索手段（図１０の６０）は、未処理ゲート検索手段（図１１の３０１）と、入力信号線検索手段（図１１の３０２）と、故障伝搬経路登録手段（図１１の３０３）と、故障伝搬経路判定手段（図１１の６０１）と、を有する。
【００７７】
仮決定制限判定手段は、予め定められた仮決定の上限値と現在の仮決定回数を比較して、上限値を超えていない場合は、仮決定と含意操作の繰り返しによる詳細な故障伝搬経路推定を継続し、上限値を超えた場合は簡易的な故障伝搬経路検索手段に切り替えるための判定を行う。
【００７８】
未処理ゲート検索手段は、簡易的な故障伝搬経路検索において、まだ処理していないゲートを検索し、入力信号線検索手段は、検索した未処理のゲートの入力信号線からまだ値が定まっていない信号線を検索し、故障伝搬経路登録手段は、検索した信号線を故障状態の信号線として登録することにより、未確定ゲートから入力方向に信号線をトレースして、それらの信号線を故障伝搬経路として登録する簡易的な経路追跡を可能とする。
【００７９】
故障伝搬経路判定手段は、ゲートの入出力信号線の期待値を参照することにより、入力信号線検索手段で検索した入力信号線からさらに、故障状態をゲートの出力に伝搬する可能性のある入力信号線を検索することにより、処理時間を増大することなくより精度の良い経路追跡を可能とする。かかる手段を備えたシステムは、論理状態の仮決定と含意操作の繰り返し処理を含む故障伝搬経路推定システムにおいて、高速処理を実現する故障伝搬経路簡易検索システムを提供している。
また本発明においては、予め定めておいた仮決定制限再設定条件が満たされているか否かを判定し、前記仮決定制限再設定条件を満たしている場合は、論理状態の仮決定の回数を表す仮決定レベルを再設定し、仮決定の回数が再設定された前記仮決定制限値以下となる論理状態に戻して、推定途中に仮決定回数が上限に達した場合には、簡易的な故障伝搬経路検索により、未確定ゲートに故障を伝搬する可能性のある信号線を故障伝搬経路として登録する、というものである。
より具体的には、データ処理装置（図１９の２）において、仮決定制限変更手段（図１９の３３）を有する。仮決定制限変更手段（図１９の３３）は、仮決定制限再設定条件判定手段（図２０の３３１）と、仮決定制限再設定手段（図２０の３３２）と、バックトラック手段（図２０の３３３）と、を有する。
仮決定制限再設定条件判定手段（図２０の３３１）は、予め定めておいた仮決定制限再設定条件が満足しているかを判定する。例えば、推定処理時間が上限値を越えた場合に、仮決定制限値を再設定すると定めている場合は、推定処理時間が予め定めておいた上限値を越えているか否かを判定する。仮決定制限再設定手段（図２０の３３２）は、予め定めておいたルールに従って、仮決定制限値を再設定する。バックトラック手段（図２０の３３３）は、仮決定状態記憶部を参照して、現在の仮決定状態を検索し、仮決定の回数が、仮決定制限再設定手段において再設定された制限値を越える場合に、論理状記憶部に記憶された信号線の論理状態を参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が仮決定制限値を越える前の論理状態に戻す。
【００８０】
［発明の第１の実施の形態］
次に本発明の第１の実施の形態について図面を参照して詳細に説明する。図１は、本発明の第１の実施の形態の構成を示す図である。図１を参照すると、本発明の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、ハードディスクやメモリなどの情報を記憶する記憶装置４と、ディスプレイ装置や印刷装置などの出力装置５とを含む。
【００８１】
記憶装置４は、論理回路構成記憶部４１と、論理矛盾記憶部４２と、仮決定状態記憶部４３と、論理状態記憶部４４とを備えている。
【００８２】
論理回路構成記憶部４１は、論理回路の構成、すなわち、ゲートの種類、ゲート同士の接続関係、ゲートと信号線の接続関係、信号線同士の接続関係など、論理回路の構成を予め記憶している。
【００８３】
論理矛盾記憶部４２は、含意操作処理中に論理矛盾が生じたゲートと論理矛盾の回数を記憶している。
【００８４】
仮決定状態記憶部４３は、何回の仮決定を行なったかを表す仮決定レベル、各信号線の論理状態が含意操作により推定された時点における仮決定レベルを記憶している。
【００８５】
論理状態記憶部４４は、処理中の各信号線における論理状態、含意操作の履歴、及び、回路が正常である時の各信号線の論理状態（期待値）を記憶している。
【００８６】
データ処理装置２は、初期設定手段２１と、含意操作手段２２と、論理矛盾判定手段２３と、処理終了判定手段２４と、バックトラック手段２５と、未確定ゲート検索手段２６と、故障伝搬経路関係線検索手段２７と、仮決定制限判定手段２８と、論理値仮決定手段２９と、第１の故障伝搬経路簡易検索手段３０と、論理値比較手段３１と、故障出力端子関係線抽出手段３２とを備える。これらの各手段２１−３２は、データ処理装置２で実行されるプログラムによりその機能が実現される。図１を参照すると、データ処理装置２において、図１６に示した構成に、仮決定制限判定手段２８と、第１の故障伝搬経路簡易検索手段３０とがあらたに追加されている。
【００８７】
初期設定手段２１は、入力装置１から与えられた論理回路の種類、入出力端子の論理状態の設定を行い、信号線の論理状態を初期化する。また、仮決定レベルの初期化や上限値の設定もここで行う。
【００８８】
含意操作手段２２は、論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、初期設定手段２１で設定された入出力信号線に接続されたゲート、及び、論理値仮決定手段２９において仮決定した信号線に接続されたゲートにおいて含意操作を行い、ゲートの入出力信号線の論理状態の推定を行う。
【００８９】
このとき、論理値が新たに推定された場合は、その論理値及び含意操作の履歴を論理状態記憶部４４に記録し、さらに、仮決定状態記憶部４３にその推定が何回の仮決定の下に推定されたかを示す仮決定レベルを記録する。含意操作中に論理矛盾が生じた場合には、論理矛盾記憶部４２を参照して、論理矛盾の回数が予め定められた許容回数を越えているか判定する。なお、許容回数を越えている場合は、回路内部の論理状態の推定精度を高めるために、論理回路構成記憶部４１と論理矛盾記憶部４２、及び、論理状態記憶部４４に記憶されている含意操作の履歴を参照して、論理矛盾の原因となっている信号線の論理状態を初期化し、その結果に従って、論理矛盾記憶部４２、仮決定状態記憶部４３、論理状態記憶部４４の情報を更新する、などの処理を含んでもよい。
【００９０】
論理矛盾判定手段２３は、論理矛盾記憶部４２を参照して、含意操作手段２２において検出された信号線の論理矛盾の回数が予め定められた許容回数を越えているか判定する。
【００９１】
処理終了判定手段２４は、論理状態記憶部４４に記憶された各信号線の論理状態を参照して、全信号線の論理状態が推定されたかの判定を行う。
【００９２】
バックトラック手段２５は、仮決定状態記憶部４３に記憶された仮決定状態と、論理状態記憶部４４に記憶された信号線の論理状態とを参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を仮決定を行う前の論理状態に戻す。
【００９３】
未確定ゲート検索手段２６は、組合せ回路内のゲートの入出力の論理状態を調べ、論理状態が不完全なゲートを検索する。例えば、ＮＡＮＤゲートにおいて出力信号が｀１’の場合、入力信号の一つが必ず｀０’であるが、入力信号線の論理状態が決まっておらず、どの入力信号線が｀０’であるかわからない時、そのゲートの入出力論理状態は不完全であり、そのゲートは未確定ゲートとなる。
【００９４】
故障伝搬経路影響線検索手段２７は、未確定ゲート検索手段２６において検索された未確定ゲートの中から、論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索する。
【００９５】
仮決定制限判定手段２８は、次の仮決定が予め定められた仮決定の上限値を超えているかどうかを判定する。
【００９６】
論理値仮決定手段２９は、故障伝搬経路影響線検索手段２７において検出した出力信号が故障状態であるような未確定ゲートの入力信号線を選択して論理状態を決定する。
【００９７】
第１の故障伝搬経路簡易検索手段３０は、未確定ゲートから、入力方向に回路をトレースして、図６に模式的に示すような、ファンインコーンを抽出し、ファンインコーンの中に含まれる経路の内、論理状態の定まっていない信号線を全て故障伝搬経路として、論理状態記憶部４４に登録する。
【００９８】
図２は、図１の第１の故障伝搬経路簡易検索手段３０の構成を示す図である。図２を参照すると、第１の故障伝搬経路簡易検索手段３０は、未処理ゲート検索手段３０１と、入力信号線検索手段３０２と、故障伝搬経路登録手段３０３とを含む。
【００９９】
未処理ゲート検索手段３０１は、論理回路構成記憶部４１及び論理状態記憶部４４を参照して、
・故障伝搬経路影響線検索手段２７において検出された、出力信号が故障状態であるような未確定ゲート、及び、
・故障伝搬経路登録手段３０３において登録された、信号線の入力側ゲートのうち、第１の故障伝搬経路簡易検索がまだ施されていないゲート、
を検索する。
【０１００】
入力信号線検索手段３０２は、未処理ゲート検索手段３０１で検索された未処理ゲートの入力信号線のうち、論理状態が確定していない信号線を検索する。
【０１０１】
故障伝搬経路登録手段３０３は、入力信号線検索手段３０２において検索された信号線の論理状態を故障状態とし、それを論理状態記憶部４４に記録する。
【０１０２】
再び、図１を参照して、本発明の第１の実施の形態について説明を続ける。論理値比較手段３１は、求めた各信号線の論理状態を、正常回路において論理シミュレーションによって求めた各信号線の論理状態を表す期待値と比較して、故障伝搬経路を抽出する。
【０１０３】
故障出力端子関係線抽出手段３２は、論理値比較手段３１において抽出された故障伝搬経路の内、その経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出して、出力装置５に、データを出力する。
【０１０４】
図１に示したデータ処理装置２は、各ブロックを、論理回路で構成するのは容易であり、１チップ化することにより、高速処理が可能であり、記憶装置４をメモリで構成してシステムＬＳＩとして組み込むことにより、更なる高速処理が期待できる。
【０１０５】
図３、図４は、本発明の第１の実施の形態の動作の処理の流れを説明するためのフローチャートである。図１乃至図４、及び図７を参照して、本発明の第１の実施の形態の動作について説明する。以下の説明では、便宜上、信号線の論理状態を｀０’，｀１’，｀Ｕ（Ｕｎｋｎｏｗｎ）’、及び｀Ｘ（Ｄｏｎ’ｔ  Ｃａｒｅ）’の４値で表現するが、本発明は、かかる４値表現に限定されるものではなく、これとは異なる表現による論理状態を使用する場合にも適用可能であることは勿論である。
【０１０６】
なお、論理状態｀Ｕ（Ｕｎｋｎｏｗｎ）’は、信号線の論理状態が｀０’あるいは｀１’に決定することができない不定状態を表している。
【０１０７】
論理状態｀Ｘ（Ｄｏｎ’ｔ  Ｃａｒｅ）’は、信号線の論理状態が｀０’と｀１’の両方とも論理回路全体の論理状態に矛盾を生じない時に、｀０’と｀１’の両方の論理状態を許すことを意味する論理状態である。
【０１０８】
入力装置１から与えられた入出力端子の論理状態を初期設定手段２１において設定し、仮決定の回数を表す仮決定レベル（ｄｌｅｖｅｌ）を初期化する（図３のステップＡ１及びステップＡ２）。
【０１０９】
次に、仮決定レベルの上限値（ｄｍａｘ）を設定する（ステップＡ３）。
【０１１０】
次に含意操作手段２２において含意操作を行う（ステップＡ４）。含意操作とは、各ゲートにおいて既推定のゲートの入出力信号線の論理状態より、未推定のゲートの入出力線の論理状態を推定する操作である。含意操作が可能なゲート、すなわち、ゲートの機能とそのゲートに接続され、かつ、既に論理状態が確定している入出力信号線の論理状態を用いて、そのゲートに接続された未だ論理状態が決定していない入出力信号線の論理状態を含意できるようなゲートを検索する。そして、検出されたゲートにおいて入出力信号線の論理状態の推定を行う。推定された論理状態は論理状態記憶部４１に記録され、そのときの仮決定レベル、及び、含意操作の履歴と共に仮決定状態記憶部４３に記録される。具体例として、ＮＡＮＤゲートにおける含意操作を図７に示す。
【０１１１】
論理矛盾判定手段２３により、論理矛盾記憶部４２を参照して、論理矛盾が許容回数を越えているかを判定する（ステップＡ５）。
【０１１２】
論理矛盾判定手段２３において矛盾が許容回数を越えていなければ、処理終了判定手段２４により、論理状態記憶部４４に記憶されている信号線の論理状態を参照し、全信号線の論理状態が｀０’，｀１’または｀Ｘ’に推定されたかを判定する（ステップＡ６）。矛盾が許容回数を超えていれば、現在の仮決定では故障伝搬経路が求まらないということであるので、ステップＡ１２の処理に移る。
【０１１３】
ステップＡ６において全信号線の論理状態推定が終了していないと判定した場合に未確定ゲート検索手段２６おいて、組合せ回路内のゲートの入出力の論理状態を調べ、論理状態が不完全な未確定ゲートを検索する（ステップＡ７）。
【０１１４】
次に、故障伝搬経路影響線検索手段２７において、ステップＡ６で検索した未確定ゲートの中から論理回路構成記憶部４１に記憶されている論理回路構成、及び論理状態記憶部４４に記憶されている各信号線の論理状態を参照して、故障状態が推定されている出力信号をもつ未確定ゲートを検索する（ステップＡ８）。
【０１１５】
仮決定制限判定手段２８において、仮決定レベルがステップＡ３で設定した仮決定レベルの許容値を超えているかを判定する（ステップＡ９）。
【０１１６】
仮決定レベルが仮決定レベルの許容値を超えていなければ、論理値仮決定手段２９において検出した信号線に対して｀０’と仮決定を行い、仮決定の回数を表す仮決定レベル（ｄｌｅｖｅｌ）を１つ増加し（ｄｌｅｖｅｌ＋＋）（ステップＡ１０）、含意操作手段２２による含意操作処理（ステップＡ４）に戻る。
【０１１７】
ステップＡ９において、仮決定レベルが許容値を超えていれば、第１の故障伝搬経路簡易検索手段３０において、故障伝搬経路の簡易検索を行う（ステップＡ１１）。
【０１１８】
第１の故障伝搬経路簡易検索手段３０について、その構成を示した図２、及びその処理の流れを示した図４を参照して、詳細に説明する。
【０１１９】
まず、図４のステップＢ１において、未処理ゲート検索手段３０１は、論理回路構成記憶部４１及び論理状態記憶部４４を参照して、図３のステップＡ８において検出された出力信号が故障状態であるような未確定ゲート、及び、故障伝搬経路登録手段３０３において登録された信号線の入力側ゲートのうち、第１の故障伝搬経路簡易検索をまだ施されていないゲートを検索する。
【０１２０】
未処理ゲートが検出されない場合は、第１の故障伝搬経路簡易検索の処理を終了する。未処理ゲートが検出された場合は、ステップＢ３の処理に移る（ステップＢ２）。
【０１２１】
入力信号線検索手段３０２は、未処理ゲート検索手段３０１で検索された未処理ゲートの入力信号線のうち、論理状態が推定されていない信号線を検索する（ステップＢ３）。
【０１２２】
故障伝搬経路登録手段３０３は、入力信号線検索手段３０２において検索された信号線の論理状態を故障状態とし、それを論理状態記憶部４４に記録する（ステップＢ４）。
【０１２３】
再び図３に戻り、システムの動作の説明を続ける。図３のステップＡ６において、処理終了判定手段２５によって、全信号線の論理状態が推定されたと判定された場合には、回路内部の論理状態が｀０’，｀１’または｀Ｘ’に定まったわけであるから、論理値比較手段３１（ステップＡ１２）において、期待値と異なる状態を持つ信号線、すなわち、故障伝搬経路を抽出する。さらに、故障出力端子関係線抽出手段３２において、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路を抽出し、出力装置５に出力する（ステップＡ１３）。
【０１２４】
次に仮決定をおこなった全仮決定線に対して｀０’と｀１’の両方の仮決定処理が終了しているかを判定する（ステップＡ１４）。
【０１２５】
図３のステップＡ１４において、全信号線の論理状態が推定されたと判定された時には、組合せ論理回路内部の信号線の論理状態は｀０’，｀１’または｀Ｘ’と推定されている。論理矛盾判定手段２４において矛盾が検出された場合にも、ステップＡ１４の判定処理を行う。
【０１２６】
処理終了判定手段２４（ステップＡ１４）において、仮決定処理が終了していないと判定された場合には、バックトラック手段２５において、状態｀１’と仮決定されていない仮決定線を仮決定レベルの大きい方から一つ検索し、検出された仮決定線の仮決定レベル以上の仮決定において推定された信号線の論理状態を初期化して、各信号線の論理状態をその仮決定を行う前の論理状態に戻し（ステップＡ１５）、論理値仮決定手段２９において、バックトラック手段２５で検出された仮決定線の状態を｀１’と仮決定し（ステップＡ１６）、含意操作手段２２による含意操作処理（ステップＡ４）に戻る。
【０１２７】
処理終了判定手段２４（ステップＡ１２）において、仮決定処理が終了していると判定された場合は故障伝搬経路抽出処理を終了する。
【０１２８】
【実施例】
本発明の第１の実施の形態について具体的に説明すべく、その具体的な例をなす実施例を、図１乃至図６を参照して、説明する。この実施例のシステム構成は、図１に示した通りのものであり、第１の故障伝搬経路簡易検索手段３０の構成は、図２に示した通りのものであり、システムの動作及び第１の故障伝搬経路簡易検索手段３０の動作は、それぞれ、図３、及び図４に流れ図として示した通りのものである。
【０１２９】
図１を参照すると、この実施例では、初期設定手段２１において、初期設定を行った後に、含意操作手段２２、論理矛盾判定手段２３、バックトラック手段２５、未確定ゲート検索手段２６、故障伝搬経路影響線検索手段２７、論理値仮決定手段２９により、回路内の信号線の論理状態を推定していく。ある回数の論理の仮決定と含意操作を行った結果、例えば図５に示すような故障伝搬経路が推定される。
【０１３０】
次の処理として、仮決定回数が上限を越えていない場合には、図５の未確定ゲートＡまたは未確定ゲートＢの入力信号線に、論理の仮定をおき、故障状態が伝搬している経路の推定を継続する。
【０１３１】
仮決定回数が上限を越える場合には、第１の故障伝搬経路簡易検索手段３０により、図６に示すように、未確定ゲートＡ及び未確定ゲートＢのファンインコーンをトレースし、その中の信号線を全て故障伝搬経路として登録する。ここで、ファンインコーンとは、あるゲートの入力信号線を入力方向に、再帰的にトレースした時の信号線及びゲートの集合を表す。
【０１３２】
これらの処理により、論理の仮決定と、含意操作の処理が長時間必要となる推定処理を途中で、高速な故障伝搬経路簡易検索を実行することにより、短時間で故障箇所を推定することが可能となる。また、仮決定回数の上限を適切に選択することにより、処理時間と推定精度を調節することが可能となる。
【０１３３】
本発明の第１の実施の形態のより具体的な動作について、図１乃至図４、図８、及び、図９を参照して詳細に説明する。図８に示した組合せ論理回路に対して、本発明を適用する場合を説明する。
【０１３４】
初期状態として、対象ゲートＣ１７の入出力端子の期待値と出力信号の論理値（Ｌ２２＝１，Ｌ２３＝１）が与えられている場合を考える。従って、Ｌ２３が故障出力である。
【０１３５】
最初に、初期設定手段２１において、入出力端子及び信号線の論理状態と期待値を設定する。Ｌ１＝Ｘ［１］，Ｌ２＝Ｘ［１］，Ｌ３＝Ｘ［１］，Ｌ６＝Ｘ［１］，Ｌ７＝Ｘ［１］，Ｌ２２＝１［１］，Ｌ２３＝１［０］が設定される。なお、括弧［］内の数字は期待値を表している（ステップＡ１）。仮決定レベル（ｄｌｅｖｅｌ）を初期化し（ステップＡ２）、仮決定レベルの許容値（ｄｍａｘ）も設定する（ステップＡ３）。ここでは、仮決定レベルの許容値を１とする。
【０１３６】
次に、図３のステップＡ４において、含意操作手段２２によって、論理回路内部の信号線の論理値を求める。ここでは、Ｌ２２＝１，Ｌ２３＝１によって含意される信号線はない。論理矛盾は生じないので、論理矛盾判定手段２３（ステップＡ５）で論理矛盾はないと判断する。
【０１３７】
Ｌ２３の故障出力の原因となる故障伝搬経路は求まっていないので、処理終了判定手段２４（ステップＡ６）において処理は終了していないと判定され、ステップＡ７に処理を移る。
【０１３８】
ステップＡ７において、未確定ゲート検索手段２６によって、出力信号１を持ち、入力信号にまだ０が推定されていないＮＡＮＤゲートであるＧ２２，Ｇ２３が未確定ゲートとして検索される。
【０１３９】
ステップＡ８において、故障伝搬経路影響線検索手段２７によって、故障信号線を出力信号としてもつ未確定ゲートＧ２３の入力信号線の中から、論理値が定まっていない信号線としてＬ１６を選ぶ。
【０１４０】
仮決定レベル（ｄｌｅｖｅｌ＝０）は、制限値（ｄｍａｘ＝１）に到達していないため、ステップＡ１０に処理を移る（ステップＡ９）。
【０１４１】
ステップＡ８において検出された信号線の論理値を｀０’と仮決定し、仮決定レベルを１だけ増やす（ステップＡ１０）。
【０１４２】
ステップＡ４の含意操作では、Ｌ１６＝０からＧ１６においてＬ２＝１，Ｌ１１＝１が含意される。
【０１４３】
ステップＡ５において、論理矛盾は検出されず、推定は終了していないのでステップＡ７に処理を移る。
【０１４４】
ステップＡ７では、未確定ゲートとしてＧ１１が検出され、さらに、ステップＡ８において、Ｇ１１は出力信号として故障信号が推定されているため、その入力信号線Ｌ３が選ばれる。
【０１４５】
ここで、仮決定レベルは１で、制限値（ｄｍａｘ＝１）に到達しているため、ステップＡ９において制限値に到達したと判定され、ステップＡ１１に処理を移る。
【０１４６】
図４のステップＢ１において、未処理ゲート検索手段３０１によってＧ１１が検索される。
【０１４７】
未処理ゲートが検索されたので、ステップＢ３に処理を移る。
【０１４８】
入力信号線検索手段３０２によって、Ｇ１１の入力信号線で論理値の定まっていないＬ３，Ｌ６が検索される（ステップＢ３）。
【０１４９】
次に、ステップＢ４において、Ｌ３，Ｌ６を故障信号線として論理状態記憶部４４に登録する。
【０１５０】
未処理ゲートは全て処理したので、第１の故障伝搬経路簡易検索を終了し、次の処理に移る。
【０１５１】
論理状態は全て定まったので、ステップＡ６において論理状態推定が終了したと判定され、ステップＡ１２に処理を移る。
【０１５２】
論理値比較手段３１（ステップＡ１２）において、期待値と異なる状態を持つ信号線、すなわち、故障伝搬経路を抽出する。その結果、Ｌ３，Ｌ６，Ｌ１１，Ｌ１６，Ｌ２３が故障伝搬経路として抽出される。
【０１５３】
さらに、故障出力端子関係線抽出手段３２において、Ｌ３，Ｌ６，Ｌ１１，Ｌ１６，Ｌ２３は、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路であるので、これらを出力装置５に出力する（ステップＡ１３）。
【０１５４】
ステップＡ１４において、Ｌ１６は仮決定線として１と仮決定されてないので、処理は終了していないと判定されて、ステップＡ１５に処理を移る。
【０１５５】
バックトラック手段２５により、Ｌ１６の仮決定の直前の状態に戻す。従って、仮決定レベルは０となり、論理値が定まっている信号線はＬ２２＝１，Ｌ２３＝１となる（ステップＡ１５）。今度はＬ１６＝１と仮決定を行い、仮決定レベルはｄｌｅｖｅｌ＝１となる（ステップＡ１６）。
【０１５６】
次にステップＡ４において、論理状態設定手段２４によって、論理回路内部の信号線の論理値を求める。Ｇ１６における含意操作により、Ｌ１６＝１が含意される。以降、Ｇ２２においてＬ１０＝０、Ｇ１０においてＬ１＝１，Ｌ３＝１、Ｇ２３においてＬ１９＝０、Ｇ１９においてＬ７＝１，Ｌ１１＝１、Ｇ１１においてＬ６＝０が含意され、全信号線の論理値が求まる。
【０１５７】
ステップＡ５において矛盾は検出されず、論理状態の推定は終了し、ステップＡ１２に処理を移る。
【０１５８】
ステップＡ１２において、論理比較手段３１によって期待値と比較することにより、故障伝搬経路としてＬ２，Ｌ６，Ｌ１１，Ｌ１９，Ｌ２３が抽出される。
【０１５９】
これらの経路は全て故障出力端子Ｌ２３に故障状態を伝搬することが可能であるので、これらを出力装置５に出力する（ステップＡ１３）。
【０１６０】
図９は、以上の処理を木構造で表したものである。論理の仮決定の回数は、１回のみで、２回以上の仮決定が必要な時は簡易経路検索を用いることにより、故障伝搬経路を高速に求めることが可能となる。
【０１６１】
［発明の第２の実施の形態］
次に本発明の第２の実施の形態について図面を参照して詳細に説明する。図１０は、本発明の第２の実施の形態の構成を示す図である。図１０を参照すると、本発明の第２の実施の形態においては、データ処理装置２が、図１に示した前記実施の形態のデータ処理装置２における第１の故障伝搬経路簡易検索手段２９の代わりに、第２の故障伝搬経路簡易検索手段６０を備えている点が、図１に示した前記実施の形態と相違している。
【０１６２】
図１１は、本発明の第２の実施の形態の第２の故障伝搬経路簡易検索手段６０の構成を示す図である。図１１を参照すると、第２の故障伝搬経路簡易検索手段６０は、第２に示した第１の故障伝搬経路簡易検索手段３０の構成に、さらに故障伝搬経路判定手段６０１が追加されている。
【０１６３】
第２の故障伝搬経路簡易検索手段６０は、未確定ゲートから入力方向に回路をトレースして、図１４に示すような故障伝搬可能経路を抽出し、それを全て故障伝搬経路として論理状態記憶部４４に登録する。
【０１６４】
図１１を参照すると、第２の故障伝搬経路簡易検索手段６０は、未処理ゲート検索手段３０１と、入力信号線検索手段３０２と、故障伝搬経路登録手段３０３と、故障伝搬経路判定手段６０１を含む。
【０１６５】
故障伝搬経路判定手段６０１は、論理回路構成記憶部４１に記憶されているゲートの機能と論理状態記憶部４４に記憶されているゲートの入出力端子の期待値を参照して、入力信号線検索手段３０２で検索した入力信号線の中から、ゲートの出力論理値を故障状態にする可能性のある入力信号線を検索する。
【０１６６】
例えば、ある２入力ゲートに入力信号線Ｉ１，Ｉ２及び出力信号線Ｏ１が接続し、出力信号に故障状態が推定され、入力信号が両者とも定まっていない時に、出力信号を故障状態とする可能性のある入力信号線がＩ１のみでＩ２がどんな値をとっても出力信号が故障状態とならない場合には、第１の故障伝搬経路簡易検索手段３０は、Ｉ１，Ｉ２の両者を検索するのに対して、第２の故障伝搬経路簡易検索手段６０は、Ｉ１のみを検索する。
【０１６７】
図１２は、本発明の第２の実施の形態のシステムの動作を説明するためのフローチャートである。図１３は、本発明の第２の実施の形態の第２の故障伝搬経路簡易検索手段６０の動作を説明するためのフローチャートである。図１０乃至１３を参照して、本発明の第２の実施の形態の動作について詳細に説明する。
【０１６８】
図１２のステップＡ１〜Ａ１０，Ａ１２〜Ａ１６で示される本発明の第２の実施の形態における、データ処理装置２の第２の故障伝搬経路簡易検索手段６０以外の各手段２１〜２９，３１，３２及びその動作は、前記第１の実施の形態の各手段２１〜２９，３１，３２の動作（図３のステップＡ１〜Ａ１０、Ａ１２〜Ａ１６）と同一のため、説明は省略する。
【０１６９】
第２の故障伝搬経路簡易検索手段６０の処理（図１２のステップＡ１７）について図１１及び図１３を参照して、詳細に説明する。
【０１７０】
まず、図１３のステップＢ１において、未処理ゲート検索手段３０１は、論理回路構成記憶部４１及び論理状態記憶部４４を参照して、図１２のステップＡ８において検出した出力信号が故障状態であるような未確定ゲート、及び、故障伝搬経路登録手段３０３において登録した信号線の入力側ゲートのうち、第１の故障伝搬経路簡易検索をまだ施していないゲートを検索する。
【０１７１】
入力信号線検索手段３０２は、未処理ゲート検索手段３０１で検索した未処理ゲートの入力信号線のうち、論理状態が推定されていない信号線を検索する（ステップＢ２）。
【０１７２】
次に、故障伝搬経路判定手段６０１は、論理回路構成記憶部４１に記憶されているゲートに機能と論理状態記憶部４４に記憶されているゲートの入出力端子の期待値を参照して、ステップＢ３で入力信号線検索手段３０２で検索された入力信号線の中から、ゲートの出力論理値を故障状態にする可能性のある入力信号線を検索する（ステップＢ５）。
【０１７３】
故障伝搬経路登録手段３０３は、入力信号線検索手段３０２において検索された信号線の論理状態を故障状態とし、それを論理状態記憶部４４に記録する（ステップＢ４）。
【０１７４】
以上のようにして、ファンインコーンに含まれる故障が伝搬している可能性のある経路のみを、未確定ゲートから入力方向にトレースして故障伝搬経路として登録することが可能となる。
【０１７５】
［実施例］
本発明の第２の実施の形態についてさらに詳細に説明すべく、具体的な実施例について、図５、図１０乃至図１４を参照して説明する。
【０１７６】
初期設定手段２１において初期設定を行った後に、含意操作手段２２、論理矛盾判定手段２３、バックトラック手段２５、未確定ゲート検索手段２６、故障伝搬経路影響線検索手段２７、論理値仮決定手段２９により、回路内の信号線の論理状態を推定していく。ある回数の論理の仮決定と含意操作を行った結果、図５のような故障伝搬経路が推定される。
【０１７７】
次の処理として、仮決定回数が上限を越えていない場合は、未確定ゲートＡまたはＢの入力信号線に論理の仮定をおき、故障状態が伝搬している経路の推定を継続する。
【０１７８】
仮決定回数が上限を越える場合は、第１の故障伝搬経路簡易検索手段により、図１４のように未確定ゲートＡ及びＢから、未確定ゲートの出力信号線に故障状態を伝搬する可能性のある信号線を入力方向に再帰的にトレースして故障伝搬経路として登録する。
【０１７９】
これらの処理により、論理の仮決定と含意操作の処理が長時間必要となる推定処理を途中で高速な故障伝搬経路簡易検索することにより、短時間で故障箇所を推定することが可能となる。また、仮決定回数の上限を適切に選択することにより、処理時間と推定精度を調節することが可能となる。
【０１８０】
本発明の第２の実施の形態のより具体的な動作について、図８乃至図１３を参照して詳細に説明する。図８に示す回路に、本発明を適用した場合について説明する。
【０１８１】
初期状態として、対象ゲートの入出力端子の期待値と出力信号の論理値（Ｌ２２＝１，Ｌ２３＝１）が与えられている場合を考える。従って、Ｌ２３が故障出力である。
【０１８２】
最初に、初期設定手段２１において、入出力端子及び信号線の論理状態と期待値を設定する。Ｌ１＝Ｘ［１］，Ｌ２＝Ｘ［１］，Ｌ３＝Ｘ［１］，Ｌ６＝Ｘ［１］，Ｌ７＝Ｘ［１］，Ｌ２２＝１［１］，Ｌ２３＝１［０］が設定される。なお、括弧［］内の数字は期待値を表している。（ステップＡ１）。仮決定レベル（ｄｌｅｖｅｌ）を初期化し（ステップＡ２）、仮決定レベルの許容値（ｄｍａｘ）も設定する（ステップＡ３）。ここでは、仮決定レベルの許容値を１とする。
【０１８３】
次にステップＡ４において、含意操作手段２２によって、論理回路内部の信号線の論理値を求める。ここでは、Ｌ２２＝１，Ｌ２３＝１によって含意される信号線はない。論理矛盾は生じないので、論理矛盾判定手段２３（ステップＡ５）で論理矛盾はないと判断する。
【０１８４】
Ｌ２３の故障出力の原因となる故障伝搬経路は求まっていないため、処理終了判定手段２４（ステップＡ６）において処理は終了していないと判定され、ステップＡ７に処理を移る。
【０１８５】
ステップＡ７において、未確定ゲート検索手段２６によって、出力信号１を持ち、入力信号にまだ０が推定されていないＮＡＮＤゲートであるＧ２２，Ｇ２３が未確定ゲートとして検索される。
【０１８６】
ステップＡ８において、故障伝搬経路影響線検索手段２７によって、故障信号線を出力信号としてもつ未確定ゲートＧ２３の入力信号線の中から、論理値が定まっていない信号線としてＬ１６を選ぶ。
【０１８７】
仮決定レベル（ｄｌｅｖｅｌ＝０）は、制限値（ｄｍａｘ＝１）に到達していないため、ステップＡ１０に処理を移る（ステップＡ９）。
【０１８８】
ステップＡ８において検出された信号線の論理値を｀０’と仮決定し、仮決定レベルを１だけ増やす（ステップＡ１０）。
【０１８９】
ステップＡ４の含意操作では、Ｌ１６＝０からＧ１６において、Ｌ２＝１，Ｌ１１＝１が含意される。
【０１９０】
ステップＡ５において、論理矛盾は検出されず、推定は終了していないことから、ステップＡ７に処理を移る。
【０１９１】
ステップＡ７では、未確定ゲートとしてＧ１１が検出され、さらに、ステップＡ８において、Ｇ１１は出力信号として故障信号が推定されているため、その入力信号線Ｌ３が選ばれる。
【０１９２】
ここで、仮決定レベルは１で、制限値（ｄｍａｘ＝１）に到達しているため、ステップＡ９において制限値に到達したと判定され、ステップＡ１１に処理を移る。
【０１９３】
図１３のステップＢ１において、未処理ゲート検索手段３０１によってＧ１１が検索される。
【０１９４】
未処理ゲートが検索されたので、ステップＢ３に処理を移る。
【０１９５】
入力信号線検索手段３０２によって、Ｇ１１の入力信号線で論理値の定まっていないＬ３，Ｌ６が検索される（ステップＢ３）。
【０１９６】
故障伝搬経路判定手段６０１において、Ｇ１１の出力信号を故障状態Ｌ１１＝１とする可能性のある入力信号線は、Ｌ３＝０，Ｌ６＝０の両者とも可能性があるので、Ｌ３，Ｌ６の両者が検索される（ステップＢ５）。
【０１９７】
次に、ステップＢ４において、Ｌ３，Ｌ６を故障信号線として論理状態記憶部４４に登録する。
【０１９８】
未処理ゲートは、全て処理したことから、第１の故障伝搬経路簡易検索を終了し、次の処理に移る。
【０１９９】
論理状態は全て定まったので、ステップＡ６において論理状態推定が終了したと判定され、ステップＡ１２に処理を移る。
【０２００】
論理値比較手段３１（ステップＡ１２）において、期待値と異なる状態を持つ信号線、すなわち、故障伝搬経路を抽出する。その結果、Ｌ３，Ｌ６，Ｌ１１，Ｌ１６，Ｌ２３が故障伝搬経路として抽出される。
【０２０１】
さらに、故障出力端子関係線抽出手段３２において、Ｌ３，Ｌ６，Ｌ１１，Ｌ１６，Ｌ２３は、故障伝搬経路の中から経路上に故障が存在する時に故障出力端子に直接影響を与えるような故障伝搬経路であるので、これらを出力装置５に出力する（ステップＡ１３）。
【０２０２】
ステップＡ１４において、Ｌ１６は仮決定線として、１と仮決定されてないので、処理は終了していないと判定されて、ステップＡ１５に処理を移る。
【０２０３】
バックトラック手段２５により、Ｌ１６の仮決定の直前の状態に戻す。従って、仮決定レベルは０となり、論理値が定まっている信号線は、Ｌ２２＝１，Ｌ２３＝１となる（ステップＡ１５）。今度は、Ｌ１６＝１と仮決定を行い、仮決定レベルはｄｌｅｖｅｌ＝１となる（ステップＡ１６）。
【０２０４】
次に、ステップＡ４において、論理状態設定手段２４によって、論理回路内部の信号線の論理値を求める。Ｇ１６における含意操作により、Ｌ１６＝１が含意される。
【０２０５】
以降、Ｇ２２においてＬ１０＝０、
Ｇ１０においてＬ１＝１，Ｌ２＝１、
Ｇ２３においてＬ１９＝０、
Ｇ１９においてＬ７＝１，Ｌ１１＝１、
Ｇ１１においてＬ６＝０
が含意され、全信号線の論理値が求まる。
【０２０６】
ステップＡ５において矛盾は検出されず、論理状態の推定は終了し、ステップＡ１２に処理を移る。
【０２０７】
ステップＡ１２において、論理比較手段３１によって期待値と比較することにより、故障伝搬経路として、Ｌ２，Ｌ６，Ｌ１１，Ｌ１９，Ｌ２３が抽出される。
【０２０８】
これらの経路は、全て故障出力端子Ｌ２３に故障状態を伝搬することが可能であるので、これらを出力装置５に出力する（ステップＡ１３）。
【０２０９】
この実施例の場合、処理の木構造は、前記第１の実施の形態の実施例の木構造（図９参照）と同一のものとなる。論理の仮決定の回数は、１回のみであり、２回以上の仮決定が必要な時は簡易経路検索を用いることにより、故障伝搬経路を高速に求めることが可能となる。
【０２１０】
［発明の第３の実施の形態］
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。図１５は、本発明の第３の実施の形態の構成を示す図である、図１５を参照すると、本発明の第３の実施の形態は、故障伝搬経路推定システムは、データ処理装置８で実行されるプログラム（故障伝搬経路推定プログラム）により実現され、この故障伝搬経路推定プログラムを記録した記録媒体７を備えている。この記録媒体７は、磁気ディスク、光ディスク、磁気テープ、半導体メモリその他の記録媒体であってよい。
【０２１１】
故障伝搬経路推定プログラムは、記録媒体７からデータ処理装置８に読み込まれ、データ処理装置８の動作を制御する。データ処理装置８は故障伝搬経路推定プログラムの制御により以下の処理、すなわち第１及び第２の実施の形態におけるデータ処理装置２及び６による処理と同一の処理、を実行する。
【０２１２】
入力装置１から組合せ回路の入出力端子の論理状態が与えられると、入出力端子の論理状態の設定を行い、信号線の論理状態を初期化する。
【０２１３】
仮決定状態記憶部４３及び論理状態記憶部４４を参照して含意操作と仮決定を繰り返すことにより、信号線の論理状態を推定していく。
【０２１４】
仮決定の回数が予め定められた上限を超えた場合には、第１の故障伝搬経路簡易検索手段３０、あるいは、第２の故障伝搬経路簡易検索手段６０によって、簡易的な故障伝搬経路検索を行う。
【０２１５】
全ての信号線の論理状態を推定した場合は、論理状態記憶部に記憶されている各信号線の論理状態と期待値を比較することにより、故障伝搬経路を抽出し、さらに故障出力端子に関係する故障伝搬経路のみを出力装置５に表示させる。
【０２１６】
［発明の第４の実施の形態］
次に、本発明の第４の実施の形態について図面を参照して詳細に説明する。図１９は、本発明の第４の実施の形態の構成を示す図である。図１９を参照すると、本発明の第４の実施の形態においては、データ処理装置２が、図１に示した前記実施の形態のデータ処理装置２に、仮決定制限変更手段２２を備えており、この点が、図１に示した前記第１の実施の形態と相違している。
【０２１７】
仮決定制限変更手段３３は、予め定めておいた仮決定制限再設定条件を満足しているか否かを判定し、もし条件を満たしている場合、仮決定の上限値（ｄｍａｘ）を再設定し、仮決定の回数（ｄｌｅｖｅｌ）が仮決定の再設定された制限値（ｄｍａｘ）以下となる論理状態に戻す。仮決定制限再設定条件が満たされていない場合や、仮決定の制限値（ｄｍａｘ）が再設定しようとしている値と同一である場合には、何も行わない。
【０２１８】
図２０は、本発明の第４実施の形態の仮決定制限変更手段３３の構成を示す図である。図２０を参照すると、仮決定制限変更手段３３は、仮決定制限再設定条件判定手段３３１と、仮決定制限再設定手段３３２と、バックトラック手段３３３と、を含む。なお、記憶装置４は、前記第１の実施の形態と同様、論理回路構成記憶部４１、論理矛盾記憶部４２、仮決定状態記憶部４３、論理状態記憶部４４を備えている。
【０２１９】
仮決定制限再設定条件判定手段３３１は、予め定めておいた仮決定制限再設定条件が満足されているか否かを判定する。例えば、推定処理時間が上限値を越えた場合に、仮決定制限値を再設定すると定めている場合には、推定処理時間が予め定めておいた上限値を越えているか否かを判定する。判定の結果、もし、処理時間上限値を越えていなければ、仮決定制限変更手段３３の処理を終了し、処理時間上限値を越えていれば、仮決定制限再設定手段３３２に処理を移す。
【０２２０】
仮決定制限再設定条件には、推定処理時間の他に、推定した故障伝搬経路の数、処理したパターン数、本発明に係る故障伝搬経路推定システムの負荷、温度の上昇、ユーザによる仮決定制限再設定変更信号の受信など、または、これらの複合した条件などを用いてもよい。
【０２２１】
また、仮決定制限値の再設定は、一度に限られるものではなく、予め定められたルールに従って、仮決定制限値（ｄｍａｘ）を変化させることも可能である。たとえば、推定処理を実用的な時間内に処理するために、推定処理時間に応じて段階的に仮決定制限値を変化させるようにしてもよい。
【０２２２】
仮決定制限再設定手段３３２は、予め定めておいたルールに従って、仮決定制限値を再設定する。
【０２２３】
バックトラック手段３３３は、仮決定状態記憶部４３を参照して、現在の仮決定状態を検索し、仮決定の回数（ｄｌｅｖｅｌ）が、仮決定制限再設定手段３３２において再設定された制限値（ｄｍａｘ）を越える場合に、論理状記憶部４４に記憶された信号線の論理状態を参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が仮決定制限値（ｄｍａｘ）を越える前の論理状態に戻す。
【０２２４】
図２１は、本発明の第４の実施の形態のシステムの動作を説明するためのフローチャートである。図１９乃至図２１を参照して、本発明の第４の実施の形態の動作について詳細に説明する。
【０２２５】
図２１のステップＡ１〜Ａ１６で示される本発明の第４の実施の形態におけるデータ処理装置２の仮決定制限変更手段３３以外の各手段２１〜３２及びその動作は、前記第１の実施の形態の各手段２１〜３２の動作（図３のステップＡ１〜Ａ１６）と同一のため、説明は省略する。
【０２２６】
仮決定制限変更手段３３（図２１のステップＡ１８〜Ａ２０）を、図１９及び図２０を参照して詳細に説明する。
【０２２７】
図２１のステップＡ１８において、仮決定制限再設定条件判定手段３３１は、予め定めておいた仮決定制限再設定条件が満足しているかを判定する。例えば、推定処理時間が上限値を越えた場合に、仮決定制限値を再設定すると定められている場合には、推定処理時間が予め定めておいた上限値を越えているか否かを判定する。もし、処理時間上限値を越えていなければ、仮決定制限変更手段３３の処理を終了して、ステップＡ４の含意操作に処理を移り、処理時間上限値を越えていれば、仮決定制限値の再設定を行うステップＡ１９に処理を移る。
【０２２８】
次に、ステップＡ１９において、仮決定制限再設定手段３３２は、予め定めておいたルールに従って、仮決定制限値を再設定する。
【０２２９】
ステップＡ２０において、バックトラック手段３３３は、仮決定状態記憶部４３を参照して、現在の仮決定状態を検索し、仮決定の回数（ｄｌｅｖｅｌ）が、仮決定制限再設定手段３３２において再設定された制限値（ｄｍａｘ）を越える場合に、論理状記憶部４４に記憶された信号線の論理状態を参照して、既に処理の終了した仮決定レベルの論理状態、及び、含意操作の履歴、論理矛盾を消去し、各信号線の論理状態を、仮決定の回数が仮決定制限値（ｄｍａｘ）を越える前の論理状態に戻す。
【０２３０】
以上のようにして、推定処理がユーザの想定している条件を越える場合には、故障伝搬経路簡易検索に切り替えて、高速に故障伝搬経路を推定することが可能となる。
【０２３１】
故障伝搬経路推定システムは、ＬＳＩのテストにおいて、ＬＳＩにテストパターンを印加して、異常な応答（フェイルログ）が得られた時に、そのフェイルログを使用してＬＳＩの故障伝搬経路を推定する際に用いられるため、通常、論理回路の入出力端子の論理状態は１組（１パターン）ではなく、複数組（複数パターン）の論理状態が与えられる。
【０２３２】
処理時間は論理回路のサイズ、故障箇所、そして、印加したパターンに依存するため、パターン毎に処理時間が異なる。
【０２３３】
印加するパターンによっては、論理値の仮定と含意操作に基づく詳細な故障伝搬経路推定において仮決定を多数回するにもかかわらず、含意操作においてすぐに論理矛盾を検出するために、高速に推定できるものもあれば、仮決定は少ないが処理時間が長時間になるものもある。
【０２３４】
推定精度は詳細な故障伝搬経路推定の方が高いため、全てのパターンにおいて仮決定制限値を同一にするのではなく、本発明の第４の実施の形態のように、処理時間などの条件を設けて、第１段階では詳細な故障伝搬経路推定を行ない、予め定めておいた条件を満たすときに簡易的な故障伝搬経路推定を行なった方が、仮決定回数が多くても短時間で処理できるパターンなど、さまざまなパターンに対応することが可能となり、その結果、短時間で高精度の推定が可能となる。
【０２３５】
また、前記第３の実施の形態の説明で参照した図１５に示したように、故障伝搬経路推定プログラムを記録媒体７からデータ処理装置８に読み込み、データ処理装置８の動作を制御し、データ処理装置８において、上記した本発明の第４の実施の形態におけるデータ処理装置２の仮決定制限変更手段３３と同一の処理を実行するようにしてもよい。仮決定制限変更手段３３において、仮決定制限再設定条件が満足しない場合には、簡易的な故障伝搬経路検索を行なわず、論理の仮定と含意操作を継続する処理を行う。すなわち、記録媒体７からデータ処理装置８に読み込みまれる上記第３の実施の形態に係る故障伝搬経路推定プログラムには、図２１のステップＡ１８〜Ａ２０を行う仮決定制限変更手段３３の処理をデータ処理装置８（図１５参照）に実行するためのプログラムがさらに含まれる。
【０２３６】
【発明の効果】
以上説明したように、本発明によれば下記記載の効果を奏する。
【０２３７】
本発明の第１の効果は、論理の仮決定と含意操作の繰り返し処理を基本とした故障伝搬経路推定において、高速な処理を可能としている、ということである。
【０２３８】
その理由は、本発明においては、論理の仮決定の回数に上限を設定して、論理の仮決定と含意操作の繰り返しに基づく詳細な推定処理から簡易的な推定処理に切り替える構成としたためである。
【０２３９】
本発明の第２の効果は、推定処理を中断した場合にも実際の故障が含まれるような故障伝搬経路ができる、ということである。
【０２４０】
その理由は、本発明においては、論理の仮決定と含意操作の繰り返しに基づく詳細な推定処理を中断する際に、未確定ゲートから入力方向に故障伝搬経路を簡易的に推定処理を行うためである。
【０２４１】
本発明の第３の効果は、故障伝搬経路の推定において、推定精度と処理時間を調節が可能としている、ということである。
【０２４２】
その理由は、本発明においては、論理の仮決定の回数の上限を設定することにより、推定精度と処理時間の調整が可能であるからである。すなわち、仮決定回数の上限を高くすると、推定精度は良くなるが処理時間は長くなる。仮決定回数の上限を低くすると、推定精度は良くないが処理時間は短くなる。
【０２４３】
本発明の第４の効果は、故障伝搬経路の推定において、複数のパターンを処理する場合に短時間でより高精度な推定を可能としている、ということである。
【０２４４】
その理由は、本発明においては、処理時間に応じて、論理の仮決定の回数の上限を再設定することにより、長い処理時間を必要とするパターンにおいては、故障伝搬経路の簡易検索に切り替え、短い処理時間で処理できるパターンにおいては、論理の仮定と含意操作を繰り返す詳細な故障伝搬経路推定処理を行うためである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態のシステム構成を示す図である。
【図２】本発明の第１の実施の形態における第１の故障伝搬経路簡易検索手段の構成を示す図である。
【図３】本発明の第１の実施の形態のシステムの動作を示す流れ図である。
【図４】本発明の第１の実施の形態における第１の故障伝搬経路簡易検索手段の動作を示す流れ図である
【図５】本発明の第１の実施の形態の実施例を説明するための図面である。
【図６】本発明の第１の実施の形態の実施例を説明するための図面である。
【図７】本発明の第１の実施の形態の実施例を説明するための図面である。
【図８】本発明の第１の実施の形態の実施例を説明するための図面である。
【図９】本発明の第１の実施の形態の実施例を説明するための図面である。
【図１０】本発明の第２の実施の形態の構成を示す図である。
【図１１】本発明の第２の実施の形態における第２の故障伝搬経路簡易検索手段の構成を示す図である。
【図１２】本発明の第２の実施の形態の動作を示す流れ図である。
【図１３】本発明の第２の実施の形態における第２の故障伝搬経路簡易検索手段の動作を示す流れ図である。
【図１４】本発明の第２の実施の形態を説明するための図である。
【図１５】本発明の第３の実施の形態の構成を示す図である
【図１６】従来の技術の構成を示す図である。
【図１７】従来の技術の動作を示す流れ図である。
【図１８】従来の技術を説明するための図である。
【図１９】本発明の第４の実施の形態の構成を示す図である。
【図２０】本発明の第４の実施の形態における仮決定制限変更手段の構成を示す図である。
【図２１】本発明の第４の実施の形態の動作を示す流れ図である。
【符号の説明】
１  キーボード等の入力装置
２  データ処理装置
４  情報を記憶する記憶装置
５  出力装置
２１  初期設定手段
２２  含意操作手段
２３  論理矛盾判定手段
２４  処理終了判定手段
２５  バックトラック手段
２６  未確定ゲート検索手段
２７  故障伝搬経路影響線検索手段
２８  仮決定制限判定手段
２９  論理値仮決定手段
３０  第１の故障伝搬経路簡易検索手段
３１  論理値比較手段
３２  故障出力端子関係線抽出手段
３３  仮決定制限再設定条件判定手段
４１  論理回路構成記憶部
４２  論理矛盾記憶部
４３  仮決定状態記憶部
４４  論理状態記憶部
６０  第２の故障伝搬経路簡易検索手段
３０１  未処理ゲート検索手段
３０２  入力信号線検索手段
３０３  故障伝搬経路登録手段
３３１  仮決定制限再設定条件判定手段
３３２  仮決定制限再設定手段
３３３  バックトラック手段
６０１  故障伝搬経路判定手段
【図１】
0003614811.tif 000002
【図２】
0003614811.tif 000003
【図３】
0003614811.tif 000004
【図４】
0003614811.tif 000005
【図５】
0003614811.tif 000006
【図６】
0003614811.tif 000007
【図７】
0003614811.tif 000008
【図８】
0003614811.tif 000009
【図９】
0003614811.tif 000010
【図１０】
0003614811.tif 000011
【図１１】
0003614811.tif 000012
【図１２】
0003614811.tif 000013
【図１３】
0003614811.tif 000014
【図１４】
0003614811.tif 000015
【図１５】
0003614811.tif 000016
【図１６】
0003614811.tif 000017
【図１７】
0003614811.tif 000018
【図１８】
0003614811.tif 000019
【図１９】
0003614811.tif 000020
【図２０】
0003614811.tif 000021
【図２１】
0003614811.tif 000022