(57)【要約】      （修正有）【課題】  論理回路の故障箇所の推定、あるいは設計デバッグでの論理推定を行うために、機能レベルで入力値から出力値、及び出力値から入力値を算出する論理回路の論理推定方法を提供する。【解決手段】  論理回路の入出力端子の論理値、機能記述設計データを入力とする入力工程、指定された論理回路に対応する機能記述設計データを抽出してこれを決定グラフに変換し組合せ回路部分と順序回路部分とに分割及び階層化して論理回路を決定グラフに変換するＤＤ変換工程、期待値と逆論理推定値のいずれの論理を計算するかを選択する推定モード選択工程、選択された計算方法で分割及び階層化された決定グラフ毎に複数の時刻における論理値を計算し論理回路の期待値および逆論理推定値を算出する値推定工程、及び論理回路の期待値あるいは推定値を出力し、その決定グラフ構造を表示する出力工程を備える。【選択図】  図３
2007024513.tif 000002
【特許請求の範囲】
【請求項１】
論理回路の入力値および出力値を、論理推定あるいは逆論理推定により算出するための論理回路の論理推定方法であって、
論理推定対象となる前記論理回路の前記出力値および前記入力値の少なくとも一部と、機能記述設計データとを前記論理回路の入出力端子の入力として設定するための入力工程と、
前記入力工程で設定された前記論理回路に対応する前記機能記述設計データを抽出する回路抽出工程と、前記機能記述設計データを決定グラフに変換する変換工程と、前記決定グラフを組合せ回路部分と順序回路部分とに分割及び階層化する再変換工程とにより、前記論理回路を決定グラフ（ＤＤ：Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）に変換するＤＤ変換工程と、
前記入力工程で設定された前記論理回路の前記出力値および前記入力値に基づいて、前記出力値に対応する期待値を算出するための前記論理推定と前記入力値に対応する逆論理推定値を算出するための前記逆論理推定のいずれを計算するかを選択する推定モード選択工程と、
前記推定モード選択工程で選択された計算に基づいて、前記再変換工程によって分割及び階層化された決定グラフ毎に、複数の時刻における前記期待値あるいは前記逆論理推定値を算出する推定工程と、前記推定工程により算出された算出結果を保持管理する推定値管理工程とにより、前記論理回路の前記期待値および前記逆論理推定値を算出する値推定工程と、
前記論理回路の前記期待値、前記逆論理推定値、あるいは前記決定グラフの構造を出力する出力工程と
を具備する論理回路の論理推定方法。
【請求項２】
請求項１に記載の論理回路の論理推定方法において、
前記ＤＤ変換工程の前記変換工程は、前記機能記述設計データを使用し、前記論理回路の処理順序に従って複数の状態を持つ状態遷移表を作成し、
作成された前記状態遷移表において前記論理回路が階層化して記述されている場合には、階層化された前記論理回路の回路ブロックをモジュールノードとし、前記モジュールノードと、入力となる入力ノードと、特定時刻では入力となり、前記特定時刻とは別の時刻では出力となる入出力ノードと、演算子で構成される操作ノードと、複数の前記入力の値の組から１つを出力として選択する選択ノードと、出力ノードとをそれぞれ結線することにより、前記論理回路の全ての動作条件に対応するデータフローを示す決定グラフを作成する論理回路の論理推定方法。
【請求項３】
請求項１または２に記載の論理回路の論理推定方法において、
前記ＤＤ変換工程の前記再変換工程は、前記決定グラフが階層化されている場合には、前記モジュールノードに対応する前記決定グラフを前記モジュールノードに置き換えて、前記決定グラフを階層化されていないフラットな決定グラフ構造とし、前記フラットな決定グラフ構造を、順序回路ブロックと組合せ回路ブロックとに分離する論理回路の論理推定方法。
【請求項４】
請求項１または２に記載の論理回路の論理推定方法において、
前記ＤＤ変換工程の前記再変換工程は、前記決定グラフが階層化されていないフラットな構造を有している場合には、前記決定グラフを順序回路ブロックと組合せ回路ブロックとに分離し、さらに前記順序回路ブロックを前記モジュールノードに置き換えることにより、前記モジュールノードに対応する前記決定グラフを、前記順序回路ブロックに対応する決定グラフとする論理回路の論理推定方法。
【請求項５】
請求項１から４までの少なくとも一項に記載の論理回路の論理推定方法において、
前記値推定工程の前記推定工程は、前記推定モード選択工程により前記期待値を算出するための前記論理推定が選択された場合、前記決定グラフに基づいて、前記論理回路の状態が遷移するごとに、前記入力ノードと、前記操作ノードと、前記選択ノードと、前記モジュールノードと、前記入出力ノードと、前記出力ノードとの値を計算することで前記論理回路の前記期待値を算出し、
特に前記モジュールノードの値の計算では、前記モジュールノードに対応する前記決定グラフの期待値をモジュールノード期待値として算出し、前記モジュールノード期待値を前記モジュールノードの値とする論理回路の論理推定方法。
【請求項６】
請求項１から４までの少なくとも一項に記載の論理回路の論理推定方法において、
前記値推定工程の前記推定工程は、前記推定モード選択工程により前記逆論理推定値を算出するための前記逆論理推定が選択された場合、前記決定グラフに基づいて、前記論理回路に対応する最上層の前記決定グラフの前記出力ノードを起点として、前記論理回路の遷移状態を遡りながら、前記選択ノードと、前記操作ノードと、前記入出力ノードと、前記入力ノードと、前記モジュールノードとの値を計算することで前記論理回路の前記逆論理推定値を算出し、
特に前記モジュールノードの値の計算では、前記モジュールノードに対応するモジュールノード決定グラフを推定し、
前記モジュールノード決定グラフが前記順序回路ブロックである場合、複数の任意時刻における前記モジュールノード決定グラフの前記入力ノードの値と、前記任意時刻の単位時刻前の前記入力ノード及び前記出力ノードの値とをそれぞれ独立に計算し、計算した結果をそれぞれ前記複数の特定時刻に渡ってマージし、マージした前記モジュールノード決定グラフの前記入力ノードの値と、前記任意時刻の単位時刻前の前記入力ノード及び前記出力ノードの値とに基づいて、前記論理回路の任意時刻における前記入力値と、前記任意時刻の単位時刻前の前記入力値及び前記出力値とを算出する論理回路の論理推定方法。
【請求項７】
請求項１から６までの少なくとも一項に記載の論理回路の論理推定方法において、
前記入力工程により、前記値推定工程で前記期待値と前記逆論理推定値の何れを計算するかを設定する論理回路の論理推定方法。
【請求項８】
請求項１から７までの少なくとも一項に記載の論理回路の論理推定方法において、
前記機能記述設計データは、前記論理回路の構造あるいは動作を、Ｖｅｒｉｌｏｇ−ＨＤＬやＶＨＤＬなどのハードウェア記述言語、およびＣ言語などで記述したものである論理回路の論理推定方法。
【請求項９】
請求項１から８までの何れか一項に記載の論理回路の論理推定方法を実現するためのコンピュータ読み込み可能な論理回路の論理推定プログラム。
【請求項１０】
論理回路の入力値および出力値を、論理推定あるいは逆論理推定により算出するための論理推定装置であって、
論理推定対象となる前記論理回路の入出力端子の前記入力値、前記出力値、および機能記述設計データを取得するための外部データ取得部と、
ＣＰＵと、
前記外部データ取得部を介して取得された前記出力値および前記入力値の少なくとも一部と、前記機能記述設計データとを前記論理回路の前記入出力端子の入力として設定するための入力工程と、
前記入力工程で設定された前記論理回路に対応する前記機能記述設計データを抽出する回路抽出工程と、前記機能記述設計データを決定グラフに変換する変換工程と、前記決定グラフを組合せ回路部分と順序回路部分とに分割及び階層化する再変換工程とにより、前記論理回路を決定グラフ（ＤＤ：Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）に変換するＤＤ変換工程と、
前記入力工程で設定された前記論理回路の前記出力値および前記入力値に基づいて、前記出力値に対応する期待値を算出するための前記論理推定と前記入力値に対応する逆論理推定値を算出するための前記逆論理推定のいずれを計算するかを選択する推定モード選択工程と、
前記推定モード選択工程で選択された計算に基づいて、前記再変換工程によって分割及び階層化された決定グラフ毎に、複数の時刻における前記期待値あるいは前記逆論理推定値を算出する推定工程と、前記推定工程により算出された算出結果を保持管理する推定値管理工程とにより、前記論理回路の前記期待値および前記逆論理推定値を算出する値推定工程と、
前記論理回路の前記期待値、前記逆論理推定値、あるいは前記決定グラフの構造を出力する出力工程とをを実行するための論理推定プログラムを予め格納する記憶部と
前記論理回路の前記期待値、前記逆論理推定値、あるいは前記決定グラフの構造を出力する出力部と
を具備する論理推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理回路の故障箇所の推定を行う、あるいは設計デバッグでの論理推定を行うために、機能レベルで入力値から出力値、及び出力値から入力値を算出する論理回路の論理推定方法に関する。
【背景技術】
【０００２】
従来の論理回路の故障診断においては、論理回路の故障個所を推定するため、一般的な構成のコンピュータに論理回路の故障診断プログラムをインストールして、当該コンピュータの入力部から所望の診断に必要なコマンド入力を行うことにより故障診断を実施していた。
【０００３】
図１に、従来の論理回路の故障箇所推定方法における処理フローを示す。従来の論理回路の故障診断においては、故障シミュレータを用いて、論理回路内部に故障を仮定することにより、当該論理回路の機能もしくは論理シミュレーションを行う。そして、そのシミュレーション結果と予め備えていた期待値とを照合し、仮定した故障個所と、その故障を検出したテストベクタとを対応付けた故障辞書を作成する（ステップＳ１０１）。次に、論理回路の実際のテスト結果からフェイル情報を取得する（ステップＳ１０２）。フェイル情報を取得すると、フェイル情報のフェイルピン及びフェイルベクタに対応する故障辞書をそれぞれ検索し、仮定の故障個所を求める（ステップＳ１０３）。そして、複数得られた仮定の故障候補の中から、優先順位付けを行って故障個所の推定を行う（ステップＳ１０４）。
【０００４】
この他、従来の論理回路の故障個所特定方法として、例えば、電子ビームテスタを用いて論理回路の上位階層から故障個所を推定し、階層境界の内部信号を観察し、故障個所を論理回路の下位階層へ順に絞り込んでいく方法がある。
【０００５】
上記した技術に関連して、以下に示す提案がなされている。
【０００６】
特開２００３−１８５７０５号公報に開示されている「論理回路の故障箇所推定方法、および、論理回路の故障箇所推定プログラム」では、論理回路のテスト結果から取得されたフェイル情報に基づき論理回路の故障箇所を推定する、論理回路の故障箇所推定方法において、論理回路をハードウェア記述言語で回路ブロック単位に機能記述した記述情報からフェイル情報またはフェイル伝搬推定情報に基づき、フェイル出力ポートまたはフェイル推定出力ポートを有するフェイル推定回路ブロックを抽出し、フェイル推定回路ブロックの回路記述部をデータ処理単位のノードおよび結線によりデータフロー表示して全条件に対する動作を決定する決定グラフをそれぞれ作成し、フェイル出力ポートおよびフェイル推定出力ポートに対応したノードを起点としてフェイルベクタに基づき各ノードの出力推定および期待値比較により各ノードのフェイル推定を入力方向に行い、フェイル伝搬経路を推定し、このフェイル伝搬経路のフェイル伝搬元ノードと入力ポートとの対応に基づき、対応しないノードの情報を故障箇所推定情報として登録し、対応した入力ポートの情報を前記フェイル伝搬推定情報として登録し、フェイル伝搬元ノード全てが入力ポートと対応しなくなるまで、これら処理を繰り返し、故障箇所推定情報をリスト出力する論理回路の故障箇所推定方法が提案されている。
【０００７】
また、特開２００４−３０９２６１号公報に開示されている「論理回路の故障診断装置、故障診断方法およびそのプログラム」では、論理回路の構造あるいは動作を設計言語で回路ブロック単位に機能記述した記述情報から、フェイル抽出装置により抽出したフェイル推定出力ポートを有するフェイル推定回路ブロックごとに作成した状態遷移表に基づき、入力ノード、演算子で構成される操作ノード、複数の入力値の組から１つの出力値を選択する選択ノードおよび出力ノードとこれらの各ノードの結線を行い、表示手段にデータフロー表示して各ノードに対する動作を決定する決定グラフを作成し、データ系故障と制御系故障とを別々に想定しながら、決定グラフを用いたフェイル伝搬経路推定を行うことで、機能レベルでデータ系と制御系の故障個所を推定する機能を有する論理回路の故障診断装置が提案されている。本提案、および特開２００３−１８５７０５号公報に開示されている提案では、論理回路を決定グラフに変換し、テストパターンに対応した各ノードの期待値と推定値を比較追跡しながら、機能レベルで故障箇所を推定する。推定値を計算するには、決定グラフの出力を起点として、入力方向に各ノードの値を計算しながら、入力値を算出する。また、設計した回路をデバッグする場合、ある信号の変化する要因を追いかける際に、回路図をトレースしながら要因となる信号を探す。
【０００８】
また、特開平０８−１４６０９３号公報に開示されている「順序回路の故障箇所推定方法」では、半導体集積回路内の、全ラッチの全ベクタに対する全期待値情報と、テスタのパス／フェイル情報と、全回路の接続情報とを用い、当該半導体集積回路をラッチと組合わせ回路とに分割して故障推定する順序回路の故障箇所推定方法において、実際のフェイル出力ピンもしくはフェイルと推定されるラッチ入力線から、半導体集積回路の入力ピンまたはラッチ出力に到達するまでの入力方向に向って組合わせ回路を抽出するとともに、更に抽出された当該組合わせ回路の入力から、半導体集積回路の出力ピンまたはラッチ入力に到達するまでの出力方向に向って組合わせ回路を抽出する第１の処理手順と、組合わせ回路の出力部に接続されているラッチの出力が、他の何れのラッチに影響を及ぼしているか否かをチェックしてデータフローを作成する第２の処理手順と、組合わせ回路の入力境界における故障伝搬値を、単一故障伝搬確認、前段の組合わせ回路内の同一信号線分岐確認および分岐信号活性化確認、および入力境界部ラッチのクロックイネーブル確認によって、同時故障伝搬可能信号線組合わせを選択するシミュレーションにより推定確認する第３の処理手順と、組合わせ回路より、実際の半導体集積回路の出力までの後段の回路の抽出が確認されていない場合に、当該後段の回路を抽出する第４の処理手順と、組合わせ回路の入力境界における故障推定結果を用いた故障伝搬シミュレーションと実際のフェイル出力とが一致しているか否かを判定する第５の処理手順と、第５の処理手順において一致していると判定された場合に、ラッチ状態の推定値テーブルを作成するとともに、得られたラッチ状態の推定値テーブルを用いた組合わせ回路内の各信号線のシミュレーション結果により縮退故障の有無を判定し、組合わせ回路内の故障箇所を推定する第６の処理手順と、を少なくともフェイルベクタごとに、組合わせ回路の入力境界における故障伝搬推定値を求める処理手順として有しており、最終的に故障推定リストを作成する順序回路の故障推定方法が提案されている。
【０００９】
特開平０８−１４６０９３号公報に開示されている「順序回路の故障箇所推定方法」では、故障出力に故障を伝搬する可能性のある組合せ回路をダイナミックに抽出して、組合せ回路毎に論理状態及び故障の伝搬する経路を推定し、入力方法に遡ることにより故障個所を推定する。ここで組合せ回路の論理状態とは、ひとつの信号線の論理値だけでなく、回路内部の全ノード、すなわち信号線、ゲート、ゲート端子、入出力端子が０／１／Ｘ（Ｄｏｎ’ｔ  Ｃａｒｅ）／Ｚ（ハイインピーダンス）／Ｕ（不定）などの論理値を持っている状態のことである。
【００１０】
【特許文献１】特開２００３−１８５７０５号公報
【特許文献２】特開２００４−３０９２６１号公報
【特許文献３】特開平０８−１４６０９３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来の故障シミュレータによる論理回路の故障診断方法では、故障辞書を予め作成しておく必要がある。故障辞書の作成には多大な故障シミュレーション時間を要するため、論理回路が大規模化するにつれてシミュレーション時間も膨大となり、故障辞書のファイルも非常に大きくなるという問題があった。特に、故障シミュレーションで用いる故障モデルは単一縮退故障が一般的であるため、実際にブリッジ故障などの多重故障が生じた場合には、故障シミュレーションでは対応出来ない。しかし、故障シミュレーションモデルを多重故障に拡張すると、故障シミュレーションの処理時間の観点から現実化が困難であった。
【００１２】
また、従来の、電子ビームテスタを用いた論理回路の故障個所を推定するための故障診断方法は、論理回路の上位階層から下位階層へ故障個所を逐次観測しながら絞り込んでいくのに有効な手段であるが、論理回路が大規模化し、多層配線構造になると、下層配線の電位が観測不可能になるという問題がある。
【００１３】
また、従来のゲートレベルで故障個所を推定するための故障診断方法は、組合せ回路毎に故障個所を推定するのに有効な手段であるが、ゲート単位での推定処理のため、大規模な論理回路に対する精度の低下と処理時間の増加が問題となる。
【００１４】
また、従来の設計デバッグでは、ある信号の変化する要因を追いかける際に、回路図をトレースしながら要因となる信号を探すが、要因となる信号は通常複数存在し、要因となる信号とその値を推定するには多くの時間を必要とするという問題がある。
【００１５】
また、従来の機能レベルで故障個所を推定するための故障診断方法は、出力値から入力値を算出することができるが、更に処理時間を短縮できれば、大規模な論理回路に対しても有効な故障診断方法となる。
【課題を解決するための手段】
【００１６】
以下に、［発明を実施するための最良の形態］で使用する括弧付き符号を用いて、課題を解決するための手段を説明する。これらの符号は、［特許請求の範囲］の記載と［発明を実施するための最良の形態］の記載との対応関係を明らかにするために付加されたものであるが、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。
【００１７】
本発明の論理回路の論理推定方法は、論理回路の入力値および出力値を、論理推定あるいは逆論理推定により算出するための論理回路の論理推定方法であって、論理推定対象となる論理回路の出力値および入力値の少なくとも一部と、機能記述設計データとを論理回路の入出力端子の入力として設定するための入力工程と、入力工程で設定された論理回路に対応する機能記述設計データを抽出する回路抽出工程と、機能記述設計データを決定グラフに変換する変換工程と、決定グラフを組合せ回路部分と順序回路部分とに分割及び階層化する再変換工程とにより、論理回路を決定グラフ（ＤＤ：Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）に変換するＤＤ変換工程と、入力工程で設定された論理回路の出力値および入力値に基づいて、出力値に対応する期待値を算出するための論理推定と入力値に対応する逆論理推定値を算出するための逆論理推定のいずれを計算するかを選択する推定モード選択工程と、推定モード選択工程で選択された計算に基づいて、再変換工程によって分割及び階層化された決定グラフ毎に、複数の時刻における期待値あるいは逆論理推定値を算出する推定工程と、推定工程により算出された算出結果を保持管理する推定値管理工程とにより、論理回路の期待値および逆論理推定値を算出する値推定工程と、論理回路の期待値、逆論理推定値、あるいは決定グラフの構造を出力する出力工程とを備える。
【発明の効果】
【００１８】
本発明により、論理回路の故障箇所の推定を行う、あるいは設計デバッグでの論理推定を行うために、機能レベルで入力値から出力値、及び出力値から入力値を算出する論理回路の論理推定方法を提供することができる。
【００１９】
本発明の論理回路の論理推定方法により、論理回路を順序回路ブロックと組合せ回路ブロックとで分割及び階層化した決定グラフに変換し、分割及び階層化された決定グラフ毎に、複数の時刻における論理値を計算することで、階層化して記述された論理回路や順序回路に対しても、短時間で入力値から出力値、あるいは出力値から入力値を算出できる。本願に係わる、入力値から出力値を算出する期待値計算や、出力値から入力値を算出する逆論理推定は、故障箇所推定での故障経路の追跡に使用でき、これにより、故障箇所の推定時間の短縮が実現する。さらに、本願に係わる回路デバッグでは、ある信号に値を設定して、そこから逆論理推定することで、入力方向の任意の信号の値を算出でき、不具合原因のトレースを容易にすることができる。
【発明を実施するための最良の形態】
【００２０】
添付図面を参照して、本発明の論理回路の論理推定方法を実施するための最良の形態を以下に説明する。
【００２１】
本発明の論理回路の論理推定方法は、論理回路の期待値および逆論理を算出する論理回路の論理推定方法であって、（１）入力工程と、論理回路を決定グラフ（ＤＤ：Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）に変換する（２）ＤＤ変換工程と、期待値と逆論理推定値のいずれの論理を計算するかを選択する（３）推定モード選択工程と、論理回路の期待値および逆論理を算出する（４）値推定工程と、（５）出力工程とを備えている。
【００２２】
（１）入力工程は、論理推定の対象となる論理回路のシュミレーション、テストおよび解析などによって得られる入出力端子の論理値、あるいは機能記述設計データを入出力値として設定する。入力工程では、入力値のみ、出力値のみ、一部の出力値、出力値と一部の入力値、入力値と一部の出力値など、いずれの値を与えても良い。ここで論理値とは、期待値あるいは逆論理推定値である。また、機能記述設計データは、論理回路の構造あるいは動作を、Ｖｅｒｉｌｏｇ−ＨＤＬやＶＨＤＬなどのハードウェア記述言語やＣ言語などで記述したものである。
【００２３】
（２）ＤＤ変換工程は、回路抽出工程によって、入力工程で指定された論理回路に対応する機能記述設計データを抽出し、変換工程によって、機能記述設計データを決定グラフに変換し、再変換工程によって、決定グラフを組合せ回路部分と順序回路部分とに分割及び階層化する。また、ＤＤ変換工程の変換工程は、機能記述設計データにより、論理回路の処理順序に従って複数の状態を持つ状態遷移表を作成する。そして、状態遷移表に基づいて、論理回路が階層的に記述されている場合は、階層化された回路ブロックをモジュールノードとする。そして、入力となる入力ノード、ある時刻では入力となり、別の時刻では出力となる入出力ノード、演算子で構成される操作ノード、複数の入力値の組から１つの出力値を選択する選択ノード及び出力ノードをそれぞれ結線することにより、データフロー表示して全条件に対する動作を決定する決定グラフを作成する。これにより、論理推定に必要な決定グラフを作成することができる。また、ＤＤ変換工程の再変換工程は、決定グラフが階層化されていた場合に、モジュールノードが示す決定グラフをモジュールノードに置き換えて、フラットな決定グラフ構造（階層的に表現されていない決定グラフ）とする。ここで、一般的なモジュールノードＭを使用して決定グラフＡを作成した場合、決定グラフは２つできる。決定グラフＡと、モジュールノードＭを表現する決定グラフＢとである。論理回路は決定グラフＡで表現されるが、決定グラフＡの構成要件の一部が決定グラフＢとして階層的に表現される。このため、本願においては、この決定グラフＢを当該モジュールノードに置き換えることにより、階層的に表現されていない決定グラフを実現する。
【００２４】
次に、フラットな決定グラフ構造を、順序回路ブロックと組合せ回路ブロックとに分離する。ＤＤ変換工程の再変換工程は、決定グラフが階層化されてなくフラットな構造であった場合には、決定グラフを順序回路ブロックと組合せ回路ブロックとに分離して、順序回路ブロックをモジュールノードに置き換える。このとき、モジュールノードを表現する決定グラフは、順序回路ブロックを表現する決定グラフである。
【００２５】
（３）推定モード選択工程は、入力工程で指定された論理回路の入出力値をもとに、期待値計算と逆論理推定値計算のいずれを計算するかを判定する。
【００２６】
（４）値推定工程は、推定モード選択工程（３）で選択された計算方法で、再変換工程によって分割及び階層化された決定グラフ毎に、複数の時刻における論理値を計算する推定工程と、計算結果を保持管理する推定値管理工程とにより、論理回路の期待値および逆論理推定値を算出する。ここで、時刻とは、時間（ｓｅｃ，ｎｓｅｃ，ｐｓｅｃ）を意味する場合、論理回路が動作するサイクル番号を意味する場合などがある。例えば、１ｎｓｅｃを単位として、何単位時間（サイクル）目に信号が変化するという時刻の定義がある。また、シミュレーションやテストのときには、パターン（あるいはベクタ）を時刻単位として管理が行われる。また、論理回路の入力端子は複数あるが、入力工程では、それぞれの端子に“０”や“１”が設定され、例えば、３つの入力端子それぞれに、１番目として“０”、“１”、“０”という値を設定する時には、“０１０”という１つの入力パタンが設定される。次に、２番目として“１”、“１”、“１”という値を設定する時には、“１１１”という１つの入力パタンが設定される。テストにおいては、連続した何万ものパターンが入力端子に設定され、この場合には、１つのパターンがそれぞれ“時刻”の意味を持つ。
【００２７】
値推定工程の推定工程は、推定モード選択工程によって期待値計算が選択された場合、決定グラフを用いて、状態が遷移するごとに、入力ノード、操作ノード、選択ノード、モジュールノード、入出力ノード及び出力ノードの値を計算することで論理回路の期待値を算出する。モジュールノード計算では、モジュールノードに対応する決定グラフを用いて、決定グラフの期待値を算出し、期待値をモジュールノードの値とする。これにより、論理回路の期待値を算出することができる。値推定工程の推定工程は、推定モード選択工程によって逆論理推定が選択された場合、決定グラフを用いて、論理回路を表現する最上層の決定グラフの出力ノードを起点として、遷移状態を遡りながら、選択ノード、操作ノード、入出力ノード、入力ノード、モジュールノードそれぞれの値の推定を入力方向に行い、モジュールノードの推定ではモジュールノードに対応する決定グラフの推定をする。分離している決定グラフ、あるいは階層化された決定グラフが順序回路ブロックであれば、決定グラフの入力ノードの値と、直前の時刻の入力ノード及び出力ノードの値とを推定し、決定グラフが組合せ回路ブロックであれば、現時刻の推定と直前の時刻の推定とを別個に行い、両時刻の推定結果をマージすることで、論理回路の入力値と直前の時刻の入出力値を推定する。値推定工程で期待値計算と逆論理推定値計算のいずれを計算するかは、入力工程から直接指定してもよい。
【００２８】
（５）出力工程は、論理回路の期待値あるいは推定値を出力し、また論理回路の決定グラフ構造を表示する。
【００２９】
本発明の論理回路の論理推定方法においては、モジュールノードを設定することで、階層記述された論理回路に対しても、論理推定に必要な決定グラフを作成することができる。また、順序回路ブロックと組合せ回路ブロックとで決定グラフ構造を階層化及び分離し、順序回路ブロックについては、現時刻と直前時刻の推定とを別個に行うことで、逆論理推定時の計算量を抑えることができ、処理時間を短縮することができる。これにより、機能レベルで論理回路の期待値及び逆論理推定値を算出することができる。
【００３０】
（本発明の実施の形態）
本発明の論理回路の論理推定方法を実施するための、論理回路推定装置の概略構成を図２に示す。
【００３１】
本実施の形態に係わる論理回路の論理推定方法を実施するための、論理回路の論理回路推定装置１０は、論理推定対象となる論理回路の論理推定を実行するための指示を入力する入力部２０と、ＣＰＵ４０と、記憶部７０と、外部データ取得部５０と、必要に応じて論理推定結果を出力するための出力部３０とを備えている。記憶部７０には、予め、論理推定対象となる論理回路の故障箇所の推定を行う、あるいは設計デバッグでの論理推定を行うことにより、機能レベルで入力値から出力値、あるいは出力値から入力値を算出するための論理推定プログラム７０ａが格納されている。また、外部データ取得部５０には、論理推定対象となる論理回路のデストデータを記録した論理回路のテストデータ記憶装置１００が接続される。そして、入力部２０と、ＣＰＵ４０と、記憶部７０と、外部データ取得部５０と、出力部３０とは、それぞれバスラインで接続されている。
【００３２】
（実施の形態の動作原理）
本実施の形態に係わる論理回路の論理推定方法について、図３を用いて説明する。本実施の形態においては、論理回路の論理回路推定装置１０の入力部２０から、論理推定対象となる論理回路の論理推定を実行する旨の指示が入力されると、ＣＰＵ４０が、記憶部７０に格納されている論理推定プログラム７０ａを読み込んで実行する。論理推定プログラム７０ａの実行に伴い、外部データ取得部５０は、論理回路テストデータ記憶装置１００から、論理推定対象となる論理回路のデストデータを取得する。これにより、ＣＰＵ４０が、論理推定対象となる論理回路の論理推定を開始する。図３に示されるように、本実施の形態に係わる論理推定は、入力工程（ステップＳ０１）と、論理回路を決定グラフに変換するＤＤ変換工程（ステップＳ０２）と、期待値と逆論理推定値のいずれを計算するかを選択する推定モード選択工程（ステップＳ０３）と、論理回路の期待値および逆論理推定値を算出する値推定工程（ステップＳ０４）と、出力工程（ステップＳ０５）とを備えている。以下、各工程それぞれについて詳細に説明する。
【００３３】
入力工程（ステップＳ０１）においては、論理回路の入出力端子の論理値、あるいは機能記述設計データが入出力値として設定される。また、論理推定対象となる論理回路が指定される。
【００３４】
ＤＤ変換工程（ステップＳ０２）は、入力工程（ステップＳ０１）で指定された論理回路に対応する機能記述設計データを抽出する回路抽出工程と、機能記述設計データを決定グラフに変換する変換工程と、決定グラフを組合せ回路部分と順序回路部分とに分割及び階層化する再変換工程とを有している。
【００３５】
推定モード選択工程（ステップＳ０３）は、入力工程（ステップＳ０１）で指定された論理回路の入出力値をもとに、期待値と逆論理推定値のいずれを計算するかを判定する。
【００３６】
値推定工程（ステップＳ０４）は、推定モード選択工程（ステップＳ０３）で選択された計算方法で、再変換工程によって分割及び階層化された決定グラフ毎に、複数の時刻における論理値を計算する推定工程と、計算結果を保持管理する推定値管理工程とにより、論理回路の期待値および逆論理推定値を算出する。
【００３７】
出力工程（ステップＳ０５）は、論理回路の期待値あるいは推定値を出力し、また論理回路の決定グラフ構造を表示する。
【００３８】
次に、本実施の形態におけるＤＤ変換工程（ステップＳ０２）について、図４から図７までを用いて説明する。
【００３９】
図４は、論理回路：Ｃｉｒｃｕｉｔ−ＡのＶｅｒｉｌｏｇ−ＨＤＬ記述である。図５は、Ｃｉｒｃｕｉｔ−Ａの順序回路ブロックであるＣｉｒｃｕｉｔ−Ｂの状態遷移表である。Ｃｉｒｃｕｉｔ−Ｂは、信号ＤＹＮの変化を検出したら動作し、ＤＹＮが０ならばＯＵＴに１を出力し、ＤＹＮが１ならばＯＵＴに０を出力する回路である。
【００４０】
まず、機能記述設計データであるＶｅｒｉｌｏｇ−ＨＤＬ記述（図４参照）の処理順序に従って、図５に示される状態遷移表を作成する。Ｃｉｒｃｕｉｔ−Ａは、Ｖｅｒｉｌｏｇ−ＨＤＬ記述に時間遷移を含まないため、状態遷移表を作成する必要が無い。一方、Ｃｉｒｃｕｉｔ−Ｂは、Ｖｅｒｉｌｏｇ−ＨＤＬ記述に時間遷移を含むため、処理順序に従って状態遷移表を作成する。
【００４１】
最初の遷移状態として、ａｌｗａｙｓブロックのイベント発生の判断処理を状態ＳＴ０に割り当てる。ここで、信号ＤＹＮの変化を＠ＤＹＮと表現し、ＤＹＮの値に変化があれば、ｔｅｍｐはＴＲＵＥとなり、変化がなければＦＡＬＳＥとなる。次に、ａｌｗａｙｓブロック内に記述された処理を状態ＳＴ１に割り当てる。また、状態ＳＴ１では、ノンブロッキング代入式（ＯＵＴ＜＝１，ＯＵＴ＜＝０）における右辺の式の評価を一時的なレジスタ：＿ｒｅｇ１に代入する処理を割り当てる。次に、一時的なレジスタ：＿ｒｅｇ１に保持した値をノンブロッキング代入式の左辺の信号：ＯＵＴへ代入する処理を状態ＳＴ２に割り当てる。状態ＳＴ０では、ｔｅｍｐがＴＲＵＥならば状態ＳＴ１へ行き、ｔｅｍｐがＦＡＬＳＥならば状態ＳＴ３へ行く。状態ＳＴ１では、処理が終了したら状態ＳＴ２へ行く。状態ＳＴ２では、処理が終了したら状態ＳＴ３へ行く。状態ＳＴ３では、ＳＴ０へ行く。
【００４２】
次に、Ｃｉｒｃｕｉｔ−Ａ、およびＣｉｒｃｕｉｔ−Ｂの決定グラフの作成について説明する。Ｃｉｒｃｕｉｔ−Ａは、入力ポートであるＩＮ０，ＩＮ１，ＩＮ２を入力ノードとし、出力ポートであるＯＴ０を出力ノードとする。使用されているビット演算のＡＮＤ（＆）、ビット演算のＯＲ（｜）およびビット演算の論理反転（〜）を操作ノードとして設定する。信号：Ｗ００は、代入式の左辺において代入される変数であり、また回路ブロックＣｉｒｃｕｉｔ−Ｂの入力でもあるため、入出力ノードとして設定する。Ｉ１は、回路ブロックＣｉｒｃｕｉｔ−Ｂを表現するモジュールノードとして設定する。これらのノードを結線し、データフロー表示することで、Ｃｉｒｃｕｉｔ−Ａの決定グラフである図６が作成される。
【００４３】
また、Ｃｉｒｃｕｉｔ−Ｂは、入力ポートであるＤＹＮを入力ノードとして設定する。状態変数＿ｓｔａｔｅ，状態番号＿ｓｔ０，＿ｓｔ１，＿ｓｔ２，＿ｓｔ３を入力ノードとして設定する。また、条件式における定数、代入式の右辺において式の評価で使用されている定数である‘０’、‘１’、＿ｒｅｇ１を入力ノードとして設定する。信号の変化を判断するイベントノード“＿ｅｖｎｔ”を入力ノードとして設定する。出力ポートであるＯＵＴ及び状態変数＿ｓｔａｔｅを出力ノードとして設定する。代入式の左辺において代入される変数である＿ｒｅｇ１を出力ノードとして設定する。ｉｆ−ｅｌｓｅ構文の動作を表現するために、等号（＝）、論理演算のＮＯＴ（！）、論理演算のＡＮＤ（∩）、論理演算のＯＲ（∪）を操作ノードとして設定する。出力ノードＯＵＴ，＿ｓｔａｔｅおよび＿ｒｅｇ１のそれぞれに対応したＯＵＴ＿ａ，ｓｔａｔｅ＿ａ，ｒｅｇ１＿ａ、を選択ノードとして設定する。選択ノードは、例えば図７中における▽記号に示されるものである。図７の右下に記載されている選択ノードは、出力ノード“＿ｒｅｇ１”にデータを出力する。出力する値は、上方から伸びるノード“１”の値（＝‘１’）、もしくはノード“０”の値（＝‘０’）である。選択ノード▽の左方から接続される２本の線のうち、上側の１本が接続しているノード“∩”の値が１であるとき、上方から伸びる２本のうち左側の１本が接続しているノード“１”の値が選択される。また、選択ノード▽の左方から接続される２本の線のうち、下側の１本が接続しているノード“∩”の値が１であるとき、上方から伸びる２本のうち右側の１本が接続しているノード“０”の値が選択される。このように、選択ノード▽の左側に接続している結線が条件を示している。
【００４４】
各ノードのリンクは、まず、状態変数である入力ノード＿ｓｔａｔｅと、状態番号である入力ノード＿ｓｔ０，＿ｓｔ１，＿ｓｔ２および＿ｓｔ３とをそれぞれ操作ノード“＝”でリンクする。出力ノードＳＴＡＴＥは選択ノードｓｔａｔｅ＿ａの出力先としてリンクする。選択ノードｓｔａｔｅ＿ａは、出力値として、状態番号である入力ノード＿ｓｔ０，＿ｓｔ１，＿ｓｔ２および＿ｓｔ３とリンクする。次状態がＳＴ１となるのは、状態ＳＴ０で条件ｔｅｍｐがＴＲＵＥの場合であるため、選択ノードｓｔａｔｅ＿ａの出力値＿ｓｔ１に対応した状態結果として、「入力ノード＿ｓｔ０とリンクした等号“＝”」と「ＤＹＮおよび＿ｅｖｎｔとリンクした等号“＝”」とを、操作ノード“∩”にリンクし、操作ノード“∩”の出力先として選択ノードｓｔａｔｅ＿ａがリンクされる。次状態がＳＴ２となるのは、現状態がＳＴ１の場合であり、「入力ノード＿ｓｔ１とリンクした等号“＝”」の出力先として選択ノードｓｔａｔｅ＿ａがリンクされる。次状態がＳＴ３となるのは、現状態がＳＴ０で条件ｔｅｍｐがＦＡＬＳＥの場合と現状態がＳＴ２の場合であるため、「ＤＹＮおよび＿ｅｖｎｔとリンクした等号“＝”」を操作ノード“！”でリンクし、さらに「入力ノード＿ｓｔ０とリンクした等号“＝”」を操作ノード“∩”でリンクする。この操作ノード“∩”は、「入力ノード＿ｓｔ２とリンクした等号“＝”」とにより、操作ノード“∪”でリンクされ、この操作ノード“∪”の出力先として選択ノードｓｔａｔｅ＿ａがリンクされる。次状態がＳＴ０となるのは、現状態がＳＴ３の場合であり、「入力ノード＿ｓｔ３とリンクした等号“＝”」の出力先として選択ノードｓｔａｔｅ＿ａがリンクされる。選択ノードｒｅｇ＿ａは出力先として、出力ノード＿ｒｅｇ１とリンクする。ここで、出力値の一つである“１”に対応した状態結果として、「入力ノードＳＴ１とリンクした操作ノード“＝”」と、「入力ノードＤＹＮと“０”をリンクした操作ノード“＝”」とを操作ノード“∩”でリンクし、操作ノード“∩”が選択ノードｒｅｇ１＿ａとリンクされる。また、出力値“０”に対応した状態結果として、「入力ノードＤＹＮと“０”をリンクした操作ノード“＝”」を操作ノード“！”でリンクし、操作ノード“！”と「入力ノードＳＴ１とリンクした操作ノード“＝”」とを操作ノード“∩”でリンクし、操作ノード“∩”が選択ノードｒｅｇ１＿ａとリンクされる。入力ノード＿ｒｅｇ１は、出力値として選択ノードＯＵＴ＿ａとリンクする。選択ノードＯＵＴ＿ａは出力先として、出力ノードＯＵＴとリンクする。ここで、出力値である＿ｒｅｇ１に対応した状態結果として、入力ノード＿ｓｔ２とリンクした等号“＝”が選択ノードＯＵＴ＿ａとリンクされる。これらのノードを結線し、データフロー表示することで、Ｃｉｒｃｕｉｔ−Ｂの決定グラフである図７が作成される。
【００４５】
次に、本実施形態におけるＤＤ変換工程（ステップＳ０２）の再変換工程について、図８から図１４までを参照して説明する。図８に示される決定グラフ（ＤＤ１）は、入力ノードがＩＮ０，ＩＮ１，ＩＮ２，ＩＮ３，ＩＮ４であり、モジュールノードＭＤを介して、出力ノードＯＴ０に計算結果を出力する。図９はモジュールノードＭＤの決定グラフ（ＤＤ２）であり、決定グラフＤＤ１のＩＮ０とＩＮ１の演算結果、ＩＮ２の演算結果、ＩＮ３とＩＮ４の演算結果、ＯＴ０が、それぞれ決定グラフＤＤ２のＴ０，Ｔ１，Ｔ２，ＯＵＴに対応する。
【００４６】
ＤＤ変換工程（ステップＳ０２）の再変換工程においては、決定グラフＤＤ１のモジュールノードＭＤを決定グラフＤＤ２に置き換えて、図１０に示すフラットな決定グラフ（ＤＤ３）とする。また、決定グラフＤＤ３を、遷移状態を持つ順序回路ブロックと、遷移状態に関係しない組合せ回路ブロックに分離する。決定グラフＤＤ３のノードＤＹＮよりも入力側のノードは、組合せ回路であり、ノードＤＹＮで決定グラフを分離し、図１１に示す組合せ回路ブロックの決定グラフＤＤ４と、図１２に示す順序回路ブロックの決定グラフＤＤ５に分離する。また、決定グラフＤＤ４は、決定グラフＤＤ５を表現するモジュールノードＭＤ１を用いて、図１３に示す決定グラフに変換できる。また、図１４に示す、モジュールノードの入出力を明確に表現した決定グラフに変換できる。これにより、決定グラフにおいて、順序回路ブロックと組合せ回路ブロックとを分離して表現することができる。
【００４７】
また、ＤＤ変換工程（ステップＳ０２）の再変換工程の他の実施の形態について、図１０から図１４までを参照して説明する。ＤＤ変換工程（ステップＳ０２）のＤＤ再変換工程の他の実施の形態は、決定グラフが図１０に示すフラットな決定グラフ（ＤＤ３）の場合に、決定グラフＤＤ３を、図１１に示す組合せ回路ブロックの決定グラフＤＤ４と、図１２に示す順序回路ブロックの決定グラフＤＤ５とに分離する。フラットな決定グラフとは、ここでは階層的に表現されていない決定グラフのことである。決定グラフＤＤ４は、決定グラフＤＤ５を表現するモジュールノードＭＤ１を用いて、図１３に示す決定グラフに変換できる。また、図１４に示す、モジュールノードの入出力を明確に表現した決定グラフに変換できる。これにより、決定グラフにおいて、順序回路ブロックと組合せ回路ブロックとを分離して表現することができる。
【００４８】
次に、本実施の形態における推定モード選択工程（ステップＳ０３）について説明する。本実施の形態に係わる推定モード選択工程（ステップＳ０３）は、論理回路の全ての入力値が既に設定されており、出力値の一部あるいは全てが未設定の場合に、計算方法として、出力値の一部あるいは全てを計算するための期待値計算を選択する。あるいは、全ての出力値が既に設定されていて、入力値の一部あるいは全てが未設定の場合に、計算方法として、入力値の一部あるいは全てを計算するための逆論理計算を選択する。さらに、入力値の一部及び出力値の一部が未設定の場合には、計算方法として、入力値の一部を計算するための逆論理計算を選択する。但し、本実施の形態における推定モード選択工程（ステップＳ０３）において、期待値計算と逆論理推定のいずれを計算するかは、入力工程（ステップＳ０１）において指定しても良い。
【００４９】
次に、本実施形態に係わる値推定工程（ステップＳ０４）について説明する。初めに、値推定モード選択工程（ステップＳ０３）において、期待値計算が選択された場合における本実施形態に係わる値推定工程（ステップＳ０４）について、図１２および図１４を参照して説明する。
【００５０】
論理回路の決定グラフは、図１４に示す階層化記述された決定グラフ（ＤＤ６）であり、決定グラフＤＤ６のモジュールノードＭＤ１を表現する決定グラフは、図１２に示す決定グラフ（ＤＤ５）である。論理回路の入力として、直前時刻ではＩＮ０＝０，ＩＮ１＝０，ＩＮ２＝０，ＩＮ３＝０，ＩＮ４＝０であり、現時刻ではＩＮ０＝０，ＩＮ１＝０，ＩＮ２＝０，ＩＮ３＝１，ＩＮ４＝１であったとする。まず、論理回路を表現する最上層の決定グラフＤＤ６について、各ノードの値を計算する。直前時刻では、出力方向に順に操作ノード“＆”、“〜”及び“｜”の値を計算し、ＩＮ０＝０，ＩＮ１＝０，ＩＮ２＝０，ＩＮ３＝０，ＩＮ４＝０であるから、ノードＷ１＝０となる。現時刻では、ＩＮ０＝０，ＩＮ１＝０，ＩＮ２＝０，ＩＮ３＝１，ＩＮ４＝１であるから、ノードＷ１＝１となる。モジュールノードＭＤ１の入力値は、直前時刻で０、現時刻で１となる。モジュールノードＭＤ１の入力は、決定グラフＤＤ５の入力ノードＤＹＮに対応する。
【００５１】
次にモジュールノードＭＤ１の表現する決定グラフＤＤ５について、各ノードの値を出力方向に計算する。決定グラフＤＤ５の入力ノードＤＹＮは、直前時刻では０、現時刻では１となる。決定グラフＤＤ５は遷移状態が＿ｓｔ０から処理が始まるため、入力ノード＿ｓｔａｔｅには、遷移状態＿ｓｔ０を意味する０を設定する。＿ｅｖｎｔとＤＹＮにリンクした操作ノード“＝”（Ｘ１０）は、ＤＹＮの値が変化した場合に１を、変化しない場合に０を設定する。ここで、ＤＹＮは０から１に変化しているため、Ｘ１０は１となる。入力ノード＿ｓｔａｔｅ＝０であるから、Ｘ１３＝１，Ｘ１４＝０，Ｘ１＝０となる。順々に未設定の操作ノードの値を推定していき、操作ノードＸ２＝１，Ｘ３＝０，Ｘ５＝０，Ｘ６＝０となる。操作ノードＸ１＝０，Ｘ２＝１，Ｘ３＝０であるから、選択ノードＸ４では、２番目の入力が選択され、出力ノード＿ｓｔａｔｅは、遷移状態＿ｓｔ１を意味する１となる。操作ノードＸ５＝０，Ｘ６＝０であるから、選択ノードＸ７では、どの入力も選択されず、出力ノードＯＴ０は設定されない。遷移状態＿ｓｔ０での計算が終了し、出力ノード＿ｓｔａｔｅ＝１であるから、次に遷移状態＿ｓｔ１へ行く。
【００５２】
遷移状態＿ｓｔ１では、入力ノード＿ｓｔａｔｅ＝１となる。入力ノードＤＹＮの値は変化しないので、現時刻の値は１となる。直前時刻の値は、１つ前の遷移状態の値である１となる。ＤＹＮの値に変化がないため、操作ノードＸ１０＝０となる。操作ノードの値は、遷移状態＿ｓｔ０での推定と同様にして、Ｘ１＝０，Ｘ２＝０，Ｘ３＝１，Ｘ５＝０，Ｘ６＝１となる。操作ノードＸ１＝０，Ｘ２＝０，Ｘ３＝１であるから、選択ノードＸ４では、３番目の入力が選択され、出力ノード＿ｓｔａｔｅは、遷移状態＿ｓｔ２を意味する２となる。操作ノードＸ５＝０，Ｘ６＝１であるから、選択ノードＸ７では、２番目の入力が選択され、出力ノードＯＴ０＝０となる。遷移状態＿ｓｔ１での計算が終了し、出力ノード＿ｓｔａｔｅ＝２であるから、次に遷移状態＿ｓｔ２へ行く。
【００５３】
遷移状態＿ｓｔ２では、入力ノード＿ｓｔａｔｅ＝２となる。入力ノードＤＹＮの値は変化しないので、現時刻の値は１となる。直前時刻の値は、１つ前の遷移状態の値である１となる。ＤＹＮの値に変化がないため、操作ノードＸ１０＝０となる。操作ノードの値は、遷移状態＿ｓｔ１での推定と同様にして、Ｘ１＝１，Ｘ２＝０，Ｘ３＝０，Ｘ５＝０，Ｘ６＝０となる。操作ノードＸ１＝１，Ｘ２＝０，Ｘ３＝０であるから、選択ノードＸ４では、１番目の入力が選択され、出力ノード＿ｓｔａｔｅは、遷移状態＿ｓｔ０を意味する０となる。操作ノードＸ５＝０，Ｘ６＝０であるから、選択ノードＸ７では、どの入力も選択されず、出力ノードＯＴ０は、１つ前の遷移状態の値である０となる。遷移状態＿ｓｔ２での計算が終了し、出力ノード＿ｓｔａｔｅ＝０であり、最初の遷移状態に戻るため、処理を終了する。次の時刻の期待値を計算する場合は、最後の遷移状態＿ｓｔ２の値を設定し、処理を続ける。これにより、決定グラフＤＤ５の処理が終了し、次に、決定グラフＤＤ５が示す決定グラフＤＤ６のモジュールノードＭＤ１に戻る。決定グラフＤＤ６では、決定グラフＤＤ５の出力ノードＯＴ０が、モジュールノードＭＤ１の出力に対応する。決定グラフＤＤ５の出力ノードＯＴ０の現時刻の値が０であるため、決定グラフＤＤ６の出力ノードＯＴ０の値は０となる。
【００５４】
以上により、本実施形態に係わる値推定工程（ステップＳ０４）では、モジュールノードを設定することにより、階層記述された論理回路に対しても期待値を計算することができる。
【００５５】
次に、値推定モード選択工程（ステップＳ０３）において、逆論理推定が選択された場合における本実施の形態に係わる値推定工程（ステップＳ０４）について、図１２及び図１４を参照して説明する。
【００５６】
値推定工程（ステップＳ０４）における論理回路の決定グラフは、図１４に示す階層化記述された決定グラフ（ＤＤ６）であり、決定グラフＤＤ６のモジュールノードＭＤ１を表現する決定グラフは、図１２に示す決定グラフ（ＤＤ５）である。論理回路の現時刻の出力がＯＴ０＝１であったとし、現時刻の入力および直前時刻の入出力を推定する。まず、最上層の決定グラフＤＤ６の出力ノードＯＴ０を起点として、入力方向に遡りながら、各ノードの値を推定する。決定グラフＤＤ６の出力ノードＯＴ０の現時刻の値は１であるから、モジュールノードＭＤ１の出力の現時刻の値は１となる。次に、モジュールノードＭＤ１の表現する決定グラフＤＤ５について推定する。
【００５７】
決定グラフＤＤ５の推定では、次遷移状態が＿ｓｔ０であるとして、出力ノード＿ｓｔａｔｅの値を、遷移状態が＿ｓｔ０であることを意味する“０”と設定する。決定グラフＤＤ６のモジュールノードＭＤ１の出力の現時刻の値は１であるから、決定グラフＤＤ５の出力ノードＯＴ０＝１と設定する。出力ノード＿ｓｔａｔｅ＝０であるから、選択ノードＸ４では、１番目の入力である＿ｓｔ０が選択されている。１番目が選択されているため、操作ノードＸ１＝１，Ｘ２＝０，Ｘ３＝０となる。操作ノードＸ１＝１であるから、入力ノード＿ｓｔａｔｅ＝２となる。操作ノードＸ１３＝０，Ｘ１４＝０となる。操作ノードＸ３＝０であるから、Ｘ８＝０となる。Ｘ８＝０，Ｘ２＝０，Ｘ１３＝０であるから、Ｘ９＝ｘ，Ｘ１０＝ｘとなる。ここでｘは、０でも１でもどちらも良いことを意味する。Ｘ１０＝ｘであるから、ＤＹＮ＝ｘとなり、一つ前の遷移状態の値もｘとなる。操作ノードＸ１４＝０であるため、Ｘ５＝０，Ｘ６＝０となる。Ｘ５＝０，Ｘ６＝０のため、選択ノードＸ７では、どの入力も選択されないことから、一つ前の遷移状態での出力ノードＯＴ０の値は１となる。入力ノード＿ｓｔａｔｅ＝２であるから、遷移状態を遡り、遡った遷移状態では出力ノード＿ｓｔａｔｅ＝２となる。出力ノード＿ｓｔａｔｅ＝２、出力ノードＯＴ０の値を１と設定する。入力ノードＤＹＮはｘである。出力ノード＿ｓｔａｔｅ＝２であるから、操作ノードＸ４では、３番目の入力である＿ｓｔ２が選択されている。３番目が選択されているため、操作ノードＸ１＝０，Ｘ２＝０，Ｘ３＝１となる。操作ノードＸ３＝１であるから、Ｘ８とＸ１４は、「Ｘ８＝１かつＸ１４＝１」、「Ｘ８＝１かつＸ１４＝０」、あるいは「Ｘ８＝０かつＸ１４＝１」のいずれかである。ここで、「Ｘ８＝１かつＸ１４＝１」と仮定すると、Ｘ９＝１，Ｘ１３＝１となる。Ｘ１３＝１であるから入力ノード＿ｓｔａｔｅ＝０となり、Ｘ１４＝０となる。Ｘ１４の値が矛盾するため、「Ｘ８＝１かつＸ１４＝１」ではない。また、「Ｘ８＝１かつＸ１４＝０」と仮定すると、Ｘ９＝１，Ｘ１３＝１，Ｘ１０＝０となる。Ｘ１３＝１であるから入力ノード＿ｓｔａｔｅ＝０となる。操作ノードＸ１４＝０であるため、Ｘ５＝０，Ｘ６＝０となる。Ｘ５＝０，Ｘ６＝０のため、選択ノードＸ７では、どの入力も選択されないことから、一つ前の遷移状態での出力ノードＯＴ０の値は１となる。Ｘ１０＝０は、ＤＹＮの値に変化がないことを意味し、ＤＹＮは「現時刻値＝０か一つ前の遷移状態の値＝０」あるいは「現時刻値＝１か一つ前の遷移状態の値＝１」となる。入力ノード＿ｓｔａｔｅ＝０であり、これは初期状態を意味するから、遷移状態の遡りを終了する。決定グラフＤＤ５の推定値としては、最終の遷移状態の出力ノード値を現時刻の出力値、初期遷移状態の入力ノード値を現時刻の入力値とする。また、初期遷移状態の一つ前の遷移状態での、入力ノード及び出力ノードの値を直前時刻の入力値及び出力値とする。すなわち、決定グラフＤＤ５の推定値として、「ＤＹＮの直前時刻値＝０，ＤＹＮの現時刻値＝０，ＯＴ０の直前時刻値＝１，ＯＴ０の現時刻値＝１」及び「ＤＹＮの直前時刻値＝１，ＤＹＮの現時刻値＝１，ＯＴ０の直前時刻値＝１，ＯＴ０の現時刻値＝１」が求まる。
【００５８】
一方、「Ｘ８＝０かつＸ１４＝１」と仮定すると、入力ノード＿ｓｔａｔｅ＝１、およびＸ１３＝０となる。Ｘ８＝０，Ｘ２＝０，Ｘ１３＝０であるから、Ｘ９＝ｘ，Ｘ１０＝ｘとなる。Ｘ１０＝ｘであるから、ＤＹＮ＝ｘとなり、一つ前の遷移状態の値もｘとなる。次に、選択ノードＸ７を推定する。Ｘ７では、「何も選択されない」、「１番目の入力が選択される」、あるいは「２番目の入力が選択される」のいずれかである。ここで「何も選択されない」の場合を仮定すると、Ｘ６＝０，Ｘ５＝０である。Ｘ１４＝１，Ｘ６＝０からＸ１１＝０となり、Ｘ１２＝１となる。また、Ｘ１４＝１およびＸ５＝０から、Ｘ１２＝０となる。Ｘ１２の値が矛盾するため、Ｘ７＝「何も選択されない」場合は成立しない。Ｘ７が「２番目の入力が選択される」場合と仮定すると、入力ノード‘０’の値がＯＴ０に出力されるが、これは、ＯＴ０＝１に矛盾する。そこで、Ｘ７が「１番目の入力が選択される」と仮定すると、Ｘ５＝１，Ｘ６＝０である。するとＸ１１＝０，Ｘ１２＝１が成立する。Ｘ１２＝１であるから、ＤＹＮ＝０となる。選択ノードＸ７で値が選択されたことから、一つ前の遷移状態での出力ノードＯＴ０の値はｘとなる。入力ノード＿ｓｔａｔｅ＝１であるから、遷移状態を遡り、遡った遷移状態では、出力ノード＿ｓｔａｔｅ＝１となる。
【００５９】
次の遷移状態では、まず、出力ノード＿ｓｔａｔｅ＝１、出力ノードＯＴ０の値をｘと設定する。入力ノードＤＹＮは０である。出力ノード＿ｓｔａｔｅ＝１であるから、選択ノードＸ４では、２番目の入力である＿ｓｔ１が選択されている。選択ノードＸ４では２番目の入力が選択されているから、Ｘ１＝０，Ｘ２＝１，Ｘ３＝０である。Ｘ３＝０から、Ｘ８＝０，Ｘ１４＝０となる。Ｘ２＝１から、Ｘ１０＝１，Ｘ１３＝１となる。Ｘ１３＝１から、入力ノード＿ｓｔａｔｅ＝０となる。Ｘ１０＝１，ＤＹＮ＝０から、ＤＹＮの一つ前の遷移状態の値は１となる。Ｘ１４＝０から、Ｘ５＝０，Ｘ６＝０となる。Ｘ５＝０，Ｘ６＝０のため、選択ノードＸ７では、どの入力も選択されないことから、一つ前の遷移状態での出力ノードＯＴ０の値はｘとなる。入力ノード＿ｓｔａｔｅ＝０であり、これは初期状態を意味するから、遷移状態の遡りを終了する。決定グラフＤＤ５の推定値として、「ＤＹＮの直前時刻値＝１，ＤＹＮの現時刻値＝０，ＯＴ０の直前時刻値＝ｘ，ＯＴ０の現時刻値＝１」が求まる。
【００６０】
以上の処理により、決定グラフＤＤ５の推定を終了する。決定グラフＤＤ５の推定値として、「ＤＹＮの直前時刻値＝０，ＤＹＮの現時刻値＝０，ＯＴ０の直前時刻値＝１，ＯＴ０の現時刻値＝１」、「ＤＹＮの直前時刻値＝１，ＤＹＮの現時刻値＝１，ＯＴ０の直前時刻値＝１，ＯＴ０の現時刻値＝１」、「ＤＹＮの直前時刻値＝１，ＤＹＮの現時刻値＝０，ＯＴ０の直前時刻値＝ｘ，ＯＴ０の現時刻値＝１」の３つが求まる。
【００６１】
次に、決定グラフＤＤ６に戻る。決定グラフＤＤ５の推定により、モジュールノードＭＤ１の値は、「入力の直前時刻値＝０，入力の現時刻値＝０，出力の直前時刻値＝１，出力の現時刻値＝１」、「入力の直前時刻値＝１，入力の現時刻値＝１，出力の直前時刻値＝１，出力の現時刻値＝１」、「入力の直前時刻値＝１，入力の現時刻値＝０，出力の直前時刻値＝ｘ，出力の現時刻値＝１」の３通りとなる。
【００６２】
モジュールノードＭＤ１から入力側のノードの推定では、まず、順序回路ブロックである決定グラフＤＤ５の値の両時刻の結果をマージする。例えば、回路ブロックの推定値が、「入力の直前時刻値＝１，入力の現時刻値＝０，出力の直前時刻値＝１，出力の現時刻値＝１」と、「入力の直前時刻値＝０，入力の現時刻値＝０，出力の直前時刻値＝１，出力の現時刻値＝１」であった場合、入力の直前時刻値が０であっても１であっても成立するため、「入力の直前時刻値＝ｘ，入力の現時刻値＝０，出力の直前時刻値＝１，出力の現時刻値＝１」とマージできる。本実施例では、マージできないので、３通りについて推定する。
【００６３】
次に、モジュールノードＭＤ１の入力値として、決定グラフＤＤ５の３通りの推定結果の入力値からリストアップした０の場合と１の場合について、入力側のノードを推定する。
【００６４】
モジュールノードＭＤ１の入力値が０の場合、入出力ノードＷ１＝０となり、操作ノードＹ１＝０となる。Ｙ１＝０から、Ｙ２＝０，Ｙ５＝０となる。Ｙ５＝０から、「ＩＮ０＝０かつＩＮ１＝ｘ」あるいは「ＩＮ０＝１かつＩＮ１＝０」が求まり、このどちらも決定グラフＤＤ５で矛盾はない。Ｙ２＝０から、「Ｙ３＝０かつＹ４＝ｘ」あるいは「Ｙ３＝１かつＹ４＝０」となる。「Ｙ３＝０かつＹ４＝ｘ」と仮定すると、ＩＮ２＝１，ＩＮ３＝ｘ，ＩＮ４＝ｘが求まり、このどちらも決定グラフＤＤ５で矛盾はない。「Ｙ３＝１かつＹ４＝０」と仮定すると、ＩＮ２＝０となる。Ｙ４＝０から、「ＩＮ３＝０かつＩＮ４＝ｘ」あるいは「ＩＮ３＝１かつＩＮ４＝０」が求まり、このどちらも決定グラフＤＤ５で矛盾はない。以上により、（ＩＮ０，ＩＮ１，ＩＮ２，ＩＮ３，ＩＮ４）＝（０，ｘ，１，ｘ，ｘ）、（０，ｘ，０，０，ｘ）、（０，ｘ，０，１，０）、（１，０，１，ｘ，ｘ）、（１，０，０，０，ｘ）、（１，０，０，１，０）の６通りが求まる。
【００６５】
モジュールノードＭＤ１の入力値が１の場合、入出力ノードＷ１＝１となり、操作ノードＹ１＝１となる。Ｙ１＝１から、（Ｙ２，Ｙ５）は（１，ｘ）あるいは（０，１）が求まる。（Ｙ２，Ｙ５）＝（１，ｘ）と仮定すると、ＩＮ０＝ｘ，ＩＮ１＝ｘ，Ｙ３＝１，Ｙ４＝１となる。Ｙ３＝１からＩＮ２＝０となる。Ｙ４＝１からＩＮ３＝１，ＩＮ４＝１となる。（Ｙ２，Ｙ５）＝（０，１）と仮定すると、ＩＮ０＝１，ＩＮ１＝１となり、（Ｙ３，Ｙ４）は（０，ｘ）あるいは（１，０）となる。（Ｙ３，Ｙ４）＝（０，ｘ）と仮定すると、ＩＮ２＝１，ＩＮ３＝ｘ，ＩＮ４＝ｘとなる。（Ｙ３，Ｙ４）＝（１，０）と仮定すると、ＩＮ２＝０となり、（ＩＮ３，ＩＮ４）は（０，ｘ）あるいは（１，０）となる。以上より、（ＩＮ０，ＩＮ１，ＩＮ２，ＩＮ３，ＩＮ４）＝（ｘ，ｘ，０，１，１）、（１，１，１，ｘ，ｘ）、（１，１，０，０，ｘ）、（１，１，０，１，０）の４通りが求まる。
【００６６】
モジュールノードＭＤ１の値が「入力の直前時刻値＝０，入力の現時刻値＝０，出力の直前時刻値＝１，出力の現時刻値＝１」の場合は、直前時刻値としてＭＤ１の入力値が０の場合の推定結果を適用し、現時刻値としてＭＤ１の入力値が０の場合の推定結果を適用する。直前時刻値の６通りと現時刻値の６通りの組合せである３６通りの結果が得られる。
【００６７】
モジュールノードＭＤ１の値が「入力の直前時刻値＝１，入力の現時刻値＝１，出力の直前時刻値＝１，出力の現時刻値＝１」の場合は、直前時刻値としてＭＤ１の入力値が１の場合の推定結果を適用し、現時刻値としてＭＤ１の入力値が１の場合の推定結果を適用する。直前時刻値の４通りと現時刻値の４通りの組合せである１６通りの結果が得られる。
【００６８】
モジュールノードＭＤ１の値が「入力の直前時刻値＝１，入力の現時刻値＝０，出力の直前時刻値＝ｘ，出力の現時刻値＝１」の場合は、直前時刻値としてＭＤ１の入力値が１の場合の推定結果を適用し、現時刻値としてＭＤ１の入力値が０の場合の推定結果を適用する。直前時刻値の４通りと現時刻値の６通りの組合せである２４通りの結果が得られる。以上説明したように、決定グラフＤＤ６で表現された論理回路では、現時刻の出力がＯＴ０＝１だった場合に、現時刻の入力値と直前時刻の入出力値の組合せとして、７６通りの結果が求まる。
【００６９】
本実施の形態においては、決定グラフにモジュールノードを設定することで、階層記述された論理回路に対しても、論理推定に必要な決定グラフを作成する。特に、順序回路ブロックと組合せ回路ブロックとで決定グラフ構造を階層化、あるいは分離する。そして、順序回路ブロックについては、現時刻と直前時刻の推定とを別個に行うことにより、逆論理推定時の計算量を抑制して処理時間を短縮する。
【００７０】
上記してきたように、本発明の論理回路の論理推定方法により、論理回路を順序回路ブロックと組合せ回路ブロックとで分割及び階層化された決定グラフに変換する。そして、それぞれの決定グラフ毎に、複数の時刻における論理値を計算することで、階層化して記述された論理回路や順序回路に対しても、短時間に入力値から出力値、あるいは出力値から入力値を算出できる。特に、論理回路の設計においては、当該回路が設計したとおりに動作しない場合に、その原因を調べて設計を修正（デバック）する必要がある。デバックでは、予想と異なる動作をする信号に対して、回路図を入力方向にトレースしながら、原因となる信号を探していく。しかし、回路を入力方向に追いかけていくと追いかけなくてはならない信号線の数が増大し、原因となる信号線を探すのに多大な時間を必要とする。本願に係わる、入力値から出力値を算出する期待値計算や、出力値から入力値を算出する逆論理推定値計算は、上記したような論理回路の設計やデバック時に、故障箇所を機能レベルで推定するための故障診断装置に適用することが出来る。また、機能レベルでの論理シミュレーターや、論理シミュレーターをコンピュータに実現するためのプログラムといった用途にも適用することが出来る。これにより、当該論理回路における故障箇所の推定時間の飛躍的な短縮が実現する。
【図面の簡単な説明】
【００７１】
【図１】従来の論理回路の故障箇所推定の処理手順を示すフローチャートである。
【図２】本発明の論理回路の論理推定方法を実施するための論理回路の論理推定装置の概略構成を示す図である。
【図３】本発明の論理回路の論理推定方法の処理手順を示すフローチャートである。
【図４】論理回路のＶｅｒｉｌｏｇ−ＨＤＬ記述例である。
【図５】本発明の実施の形態に係わる状態遷移表である。
【図６】本発明の実施の形態に係わる階層化した決定グラフである。
【図７】本発明の実施の形態に係わる階層化した決定グラフである。
【図８】本発明の実施の形態に係わる階層化した決定グラフである。
【図９】本発明の実施の形態に係わる階層化した決定グラフである。
【図１０】本発明の実施の形態に係わるフラットな決定グラフである。
【図１１】本発明の実施の形態に係わる分離した決定グラフである。
【図１２】本発明の実施の形態に係わる分離した決定グラフである。
【図１３】本発明の実施の形態に係わる階層化した決定グラフである。
【図１４】本発明の実施の形態に係わる階層化した決定グラフである。
【符号の説明】
【００７２】
１０…論理回路の論理推定装置
２０…入力部
３０…出力部
４０…ＣＰＵ
５０…外部データ取得部
６０…バスライン
７０…記憶部
７０ａ…論理推定プログラム
１００…テストデータ記憶装置
Ｘ１〜Ｘ１４，Ｙ１〜Ｙ５…ノード
【図１】
2007024513.tif 000003
【図２】
2007024513.tif 000004
【図３】
2007024513.tif 000005
【図４】
2007024513.tif 000006
【図５】
2007024513.tif 000007
【図６】
2007024513.tif 000008
【図７】
2007024513.tif 000009
【図８】
2007024513.tif 000010
【図９】
2007024513.tif 000011
【図１０】
2007024513.tif 000012
【図１１】
2007024513.tif 000013
【図１２】
2007024513.tif 000014
【図１３】
2007024513.tif 000015
【図１４】
2007024513.tif 000016