(57)【要約】  システムモデルの各時点の明示的な時間仮説を立てることを含むモデルシステムを解析する際に使用される信号モデルを生成するための方法及びコンピュータ製品が提供される。時間仮説は、任意の２つの仮説が相互に矛盾し、それによって全ての推論を個々の時間に分けるべく定義される。モデルシステムのコンポーネントモデルを実体化すべく非単調ルールが適用される。結果は、先行する時点の存在に依存しないものとして定義され、単純化された信号モデルが生成される。信号モデルはモデルシステム中における値の経時的展開を表す。
2010531480.tif 000002
【特許請求の範囲】
【請求項１】
モデルシステムの解析に使用される信号モデルを生成する方法であって、前記方法は、
システムモデルの各時点における明示的な時間仮説を立て、
相互に矛盾する任意の２つの時間仮説を定義し、それにより全ての推論を個々の時間に分け、
モデルシステムのコンポーネントモデルを実体化すべく非単調ルールを適用し、
先行する時点の存在に依存しないものとして結果を定義し、
単純化された信号モデルを生成する、
ことを含み、
前記信号モデルは、モデルシステムにおける値の経時的な展開を表す、
方法。
【請求項２】
ｔを時間としｉを時点とするとき、前記明示的な時間仮説がｔ＝ｉである請求項１に記載の方法。
【請求項３】
前記信号モデルが時間及び基礎的な仮説の両方の抽象化により記述される請求項１に記載の方法。
【請求項４】
前記信号モデルがＡＴＭＳ中でモデル化される請求項１に記載の方法。
【請求項５】
前記コンポーネントモデルの単一のコピーのみ必要とされる請求項１に記載の方法。
【請求項６】
前記モデルシステムの全ての変数を記述するために信号モデルが利用される請求項１に記載の方法。
【請求項７】
組み合わせシステムにおける時間的挙動をトラブルシュートする方法であって、前記方法は、
ＧＤＥ（ｇｅｎｅｒａｌ  ｄｉａｇｎｏｓｔｉｃ  ｅｎｇｉｎｅ）フレームワークを利用して、モデルベース解析用の現実世界のシステムのモデルを生成し、
前記モデルシステムに関する信号の単純化されたモデルを生成すべく前記ＧＤＥフレームワークの時間的拡張を実施し、
前記ＧＤＥフレームワークに対し、時間的拡張及び単純化された信号を伝播させ、
前記時間的拡張及び単純化された信号モデルを有する前記ＧＤＥフレームワークを適用することを含む解析を前記モデルシステムについて実施し、
前記解析の結果を取得する、
ことを含む方法。
【請求項８】
前記ＧＤＥフレームワークの時間的拡張を生成することは、
システムモデルの各時点における明示的な時間仮説を立て、
相互に矛盾する任意の２つの時間仮説を定義し、それにより全ての推論を個々の時間に分け、
モデルシステムのコンポーネントモデルを実体化すべく非単調ルールを適用し、
先行する時点の存在に依存しないものとして結果を定義し、
単純化された信号モデルを生成する、
ことを含み、
前記信号モデルは、モデルシステムにおける値の経時的な展開を表す、
請求項７記載の方法。
【請求項９】
ｔを時間としｉを時点とするとき、前記明示的な時間仮説がｔ＝ｉである請求項８に記載の方法。
【請求項１０】
前記信号モデルが時間及び基礎的な仮説の両方の抽象化により記述される請求項８に記載の方法。
【請求項１１】
前記信号モデルがＡＴＭＳ中でモデル化される請求項８に記載の方法。
【請求項１２】
前記コンポーネントモデルの単一のコピーのみ必要とされる請求項８に記載の方法。
【請求項１３】
前記モデルシステムの全ての変数を記述するために信号モデルが利用される請求項８に記載の方法。
【請求項１４】
計算デバイスと共に使用されるコンピュータプログラム製品であって、前記コンピュータ製品は、
システムモデルの各時点における明示的な時間仮説を立て、
相互に矛盾する任意の２つの時間仮説を定義し、それにより全ての推論を個々の時間に分け、
モデルシステムのコンポーネントモデルを実体化すべく非単調ルールを適用し、
先行する時点の存在に依存しないものとして結果を定義し、
単純化された信号モデルを生成する、
ことを含み、
前記信号モデルは、モデルシステムにおける値の経時的な展開を表す、
コンピュータプログラム製品。
【請求項１５】
ｔを時間としｉを時点とするとき、前記明示的な時間仮説がｔ＝ｉである請求項１４に記載のコンピュータプログラム製品。
【請求項１６】
前記信号モデルが時間及び基礎的な仮説の両方の抽象化により記述される請求項１４に記載のコンピュータプログラム製品。
【請求項１７】
前記信号モデルがＡＴＭＳ中でモデル化される請求項１４に記載のコンピュータプログラム製品。
【請求項１８】
前記コンポーネントモデルの単一のコピーのみ必要とされる請求項１４に記載のコンピュータプログラム製品。
【請求項１９】
前記モデルシステムの全ての変数を記述するために信号モデルが利用される請求項１４に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００７年５月２４日に出願されたジョアン・デ・クリーア（Ｊｏｈａｎ  ｄｅ  Ｋｌｅｅｒ）の米国仮出願第６０／９３１，５２６号「組合わせ回路における時間的挙動のトラブルシューティング（Ｔｒｏｕｂｌｅｓｈｏｏｔｉｎｇ  Ｔｅｍｐｏｒａｌ  Ｂｅｈａｖｉｏｒ  ｉｎ  Ｃｏｍｂｉｎａｔｉｏｎａｌ  Ｃｉｒｃｕｉｔ）」に対し優先権を主張し、その全開示内容を参照によって本明細書に援用する。
【背景技術】
【０００２】
モデルベース診断（ＭＢＤ）は、テスト中のシステムのうちいくつかの（通常は機能的な）側面を記述するモデルからテストケースの全部または一部を導出する、モデルに基づくテストに関する。モデルは、通常はテストにおいて望ましい（ｔｅｓｔ−ｄｅｓｉｒｅｄ）挙動を示す際のシステムの抽象的且つ部分的な表現である。このモデルから導出されるテストケースは、モデルと同一の抽象化レベルの機能テストである。
【０００３】
モデルベース診断は診断的であり、システムによって管理される。特に、不正な挙動の観察から始め、故障の可能性のある下層コンポーネントへ向かって動作する。
【０００４】
モデルベース診断は、故障システム挙動の検知、故障コンポーネントの識別、システムの修復及びシステムの再構成を含む各種領域において利用可能である。ＭＢＤを適用可能な他の分野として、認識モデルのデバッグ、遺伝子経路の改良モデル構築実験の設計、電力網のトラブルシューティング、生産ラインのトラブルシューティング、宇宙機及び飛行機における欠陥の識別、及びプログラムのデバッグが挙げられる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、ＭＢＤの他に、「個別（ａｄ  ｈｏｃ）」のハンドコーディングされたルール、パターンの機械学習、Ｄアルゴリズム検索及び解析的冗長性の関係などの他のテスト方法を利用するシステム診断に関連した問題は、その組み合わせ論理に意図的又は非意図的なサイクルを含みうるデジタル回路と関係がある。特に、このような回路は、論理ゲートレベルで解析される際に、即時の矛盾を生ずることが多い。
【０００６】
従って、これらの意図的又は非意図的なサイクルは発振挙動を生じさせ、あるいは当初は組み合わせ回路であると思われたものを順序回路に変換させるため、本出願はこうしたデジタル回路において推論及び診断するという課題に取り組むものである。
【０００７】
２００７年１１月１５日に出願されたジョアン・デ・クリーアの米国出願第１１／９４０，４９３号（代理人整理番号第２００７０１６２−ＵＳ−ＮＰ／ＸＥＲＺ  ２  ０１５８９号「間欠的故障の診断（Ｄｉａｇｎｏｓｉｎｇ  ｉｎｔｅｒｍｉｔｔｅｎｔ  ｆａｕｌｔｓ）」、並びに２００７年１０月３０日に出願されたジョアン・デ・クリーアの米国出願第１１／９２５，４４４号（代理人整理番号第２００７０２５８−ＵＳ−ＮＰ／ＸＥＲＺ２０１５８８号「メタ解析を通じたダイナミックドメイン抽出（Ｄｙｎａｍｉｃ  ｄｏｍａｉｎ  ａｂｓｔｒａｃｔｉｏｎ  ｔｈｒｏｕｇｈ  ｍｅｔａ−ａｎａｌｙｓｉｓ）」を参照によって本明細書に組み込む。
【課題を解決するための手段】
【０００８】
システムモデルの各時点において明示的な時間仮説を立てることを含む、モデルシステムの解析に使用される信号モデルを生成するための方法及びコンピュータ製品を提供する。時間仮説は、全ての推論を個々の時間に分割すべく、任意の二つの仮説が相互に矛盾するように定義される。モデルシステムのコンポーネントのモデルを実体化すべく、非単調なルールを適用する。結果は、その先行する時点の存在に依存しないように定義され、単純化された信号モデルが生成される。信号モデルはモデルシステム中における値の経時的展開を表す。
【図面の簡単な説明】
【０００９】
【図１】モデルベース診断エンジンの主な入力及び出力を示す図である。
【図２】単純なリングオシレータを示す図である。
【図３】ｔゲート遅延の後のリングオシレータのインバータ出力を示す図であり、オシレータは６つのゲート遅延後に初期状態に戻り、従って出力はゲート遅延時間の６倍の周期を有する矩形波である。
【図４】クロス結合された２つのＮＡＮＤゲートからなるＳＲフリップフロップを示す図である。
【図５】ＳＲフリップフロップ用の真理値表を示す図である。
【図６】不都合な発振を生ずる短絡回路を示す図である。
【図７】メモリを生成する短絡回路を示す図である。
【図８】リングオシレータの視覚化を示す図であり、頂点は各々Ａ、Ｂ、Ｃの出力に関する値でラベル付けされている。
【図９】リングオシレータの定性シミュレーションを示す図であり、頂点はｔ：Ａ，Ｂ，Ｃとラベル付けされ、ｔはゲート遅延における時間、Ａ、Ｂ、Ｃは個々のインバータ出力を表す。
【図１０】リングオシレータの所望出力を示す図である。
【図１１】よりよく設計されたリングオシレータを示す図であり、クロックが可能とされると、リングオシレータは既知の好適な状態である０１１で開始される。
【図１２】よりよいリングオシレータの発振挙動を示す図であり、頂点をｔ：ｎｎｎｎでラベル付けし、ｔは時間、ｎｎｎｎはゲートＡ、Ｂ、Ｃの出力及びイネーブル入力であり、イネーブル信号は０００*１である。
【図１３】リングオシレータの望ましくない偽発振を示す図である。
【図１４】よりよいリングオシレータの定性シミュレーションを示す図であり、頂点をｔ：ｎｎｎｎでラベル付けし、ｔは時間、ｎｎｎｎはゲートＡ、Ｂ、Ｃの出力及びイネーブル入力であり、イネーブル信号は０００*１である。
【図１５】５ゲートのリングオシレータを示す図である。
【図１６】静止時に観察された、故障した５ゲートのリングオシレータを示す図である。
【図１７】リングオシレータと組み合わされたフリップフロップを示す図であり、数字は初期入力を示し、静止時において、Ｓ＝*０、Ｒ＝*１、Ｃ＝*０、Ｂ＝*１、Ａ＝*１であることが観察され、これは全てのコンポーネントモデルにおいて一貫しているが、出力は正確でない。
【図１８】第一のフロー図を示す図である。
【図１９】第二のフロー図を示す図である。
【図２０】本出願の概念を組み込んだ診断デバイスの一実施形態に関する図である。
【図２１】埋め込まれた診断デバイスの実施形態に関する図である。
【発明を実施するための形態】
【００１０】
図１は、モデルベース、コンポーネントベースの診断（ＭＢＤ）エンジン機構１０の主な入力及び出力を示している。コンポーネント形態（例えば、アナログ電子回路の概略）１２ａ、コンポーネントモデル（例えば、レジスタはオームの法則に従う）１２ｂ、及び観察（例えば、レジスタＲ６に印加される電圧は４ボルトである）１２ｃを所与とすると、モデルベース診断（ＭＢＤ）エンジン１４は、全ての観察１２ｃを説明する診断１６を計算する。期待値と一致しない観察は、診断の発見につながる。モデルベース診断（ＭＢＤ）エンジンが診断を発見できない場合、それは失敗１８を発信する。
【００１１】
ＧＤＥフレームワークは、制約もしくは従来のルールとして表現されるコンポーネントの挙動を有することを含む。ＧＤＥは、これらのモデルから導出される全ての結論及び観察を記録するために、仮説に基づく真理維持システム（Ａｓｓｕｍｐｔｉｏｎ−Ｂａｓｅｄ  Ｔｒｕｔｈ  Ｍａｉｎｔｅｎａｎｃｅ  Ｓｙｓｔｅｍ：ＡＴＭＳ）を利用できる。
【００１２】
ＧＤＥは各候補診断について事後確率を算出する。コンポーネントの故障確率を所与とし、コンポーネントが独立して故障すると仮定して、ＧＤＥは各診断について事前確率を割り当てる。観察結果が蓄積すると、診断の（事後）確率はベイズの法則に従って変化する。証拠によって論理上消去可能な候補診断には０の確率が付与される。ＧＤＥは（仮説的定義とは対照的な）一貫性に基づく診断定義を利用するが、ベイズの法則を適用することで、単に一致するだけのものと比較して、観察を伴う診断の事後確率が高まる。結果として、確率を更新するベイズの法則を適用することで、一貫性に基づく診断の特性と仮説に基づく診断の特性を合わせた特性を有するＧＤＥが生成される。
【００１３】
システムに実際に生じた問題を判定するためには、通常は更なる測定値を取得する必要がある。一実施形態において、ＧＤＥは、次に実施すべき最良の測定を選択することで、順次診断を行う。ＧＤＥは、一般的に最小エントロピー（例えば、近視眼的最小エントロピー戦略）に基づいた１ステップの予測機能を利用する。ＧＤＥは、平均的に正確な診断を局地化するための最小数の測定を必要とする１組の測定の実施を提案する。
【００１４】
仮説に基づく真理維持システム（ＡＴＭＳ）及びハイブリッド真理維持システム（Ｈｙｂｒｉｄ−Ｔｒｕｔｈ  Ｍａｉｎｔｅｎａｎｃｅ  Ｓｙｓｔｅｍ：ＨＴＭＳ）のフレームワークは、複雑な問題空間を効率的に探索する問題解決法の構造を単純化すべく設計された命題推論エンジンを含む。ＡＴＭＳは、問題の状態を、主要な二者択一型選択に対応する仮説と、真理値が仮説の真理値に依存する命題に対応するノードと、と共に表す。仮説とノードとの依存関係は、従来の推論エンジンなどの、分野特有の問題解決法によって決定される。問題解決法は、これらの関係を、節及び根拠としてＡＴＭＳに対して提示する。ＡＴＭＳは、仮説のいずれの組み合わせが一貫性を有しているかを決定し、それらが導出する結論を識別する。
【００１５】
ＡＴＭＳは、これまでは解決する問題に適した従来の推論エンジンと組み合わされて利用されていた。拡張は、命題推論と、推論エンジンから呼び出しを受けて命題推論へ引き渡し、結果を推論エンジンに戻すインタフェースとを含む。推論エンジン、インタフェース及び命題推論は全て単一のシリアルプロセッサ上で、従来のプログラミング技術により実行される。
【００１６】
本明細書に記載された概念は、経時的に信号を表すモデルの生成に関連する。この新しいモデルは、このような回路の組み合わせ論理に意図的又は非意図的なサイクルを含みうるデジタル回路を解析しうまくトラブルシュートする方法を提供する。ある実施形態において、このことは既知のＧＤＥフレームワークに時間的拡張を提供することにより遂行される。ここに提示される時間的解析は、特別な後処理を必要とせず、計算可能である方法で、基本的なＧＤＥ系モデル及び接続モデルの両方を拡張する。この応用では、以下の単純化仮説が立てられる。
・全てのゲート遅延は等しい
・信号は接続線を通じて伝播する際に時間を要さない
・非間欠性公理を利用しない
【００１７】
２．動機付けの例
【００１８】
図２の３つのインバータを備える回路について考察する。この回路は、デジタル回路中でクロック信号を生成すべく利用されるよく知られた一般的な回路である。３つのインバータ（Ａ、Ｂ、Ｃ）は容易にワイヤ接続される。システムは物理的に実現可能であり、このようにインバータを接続することでインバータが破損することはない。図３は、ｔゲート遅延後のリングオシレータ２０の真理値表３０を示している。図３には、６つ（０〜６）のゲート遅延後にオシレータが初期状態に戻り、従って出力はゲート遅延の６倍の期間を有する矩形波であることが示されている。
【００１９】
しかし、例えばＧＤＥフレームワークや、特別な後処理を必要とせず、計算可能である接続用の拡張モデルなどのゲートの通常モデルを利用した場合、（ＧＤＥシステムなど）システムがコンポーネント又はノードの少なくとも１つは必ず故障しているという結論を下して直ちに矛盾を検出する。このことは、現実の世界（例えば、物理的世界）における実施において、いずれのインバータも故障を生じていない場合においても当てはまる。よって、問題は調査及び／又は解析を行うべく利用されるモデル側にある。
【００２０】
2010531480.tif 000003
【００２１】
図６は、広く利用可能な組み合わせの論理テストスイートＩＳＣＡＳ−８５からの回路ｃ１７などのベンチマーク回路において非意図的な発振を発生しうる短絡接続６２を備えるデジタル回路６０を示す。示された入力の場合、Ｏ１の出力は０となるはずである。Ｏ１がＩ２に短絡されていれば、回路は発振する。接続（例えば、特別な後処理を要さず、計算可能な接続のための拡張モデル）をモデル化すると、Ｏ１はＩ２を０とし、ＮＡＮＤゲートＧ１の出力は０から１となり、従ってＮＡＮＤゲートＧ５の出力は１となる。Ｏ１はＩ２に短絡され、これに従いＩ２は１となる。このようにして回路は永久的に発振を継続する。ＧＤＥ及び接続モデル（例えば、特別な後処理を要さず、計算可能な接続のための拡張モデル）によりモデル化されると、これらの入力を有するこの回路は完全に矛盾し、従って正しい故障が考察から完全に除かれる。ＶＬＳＩ設計において利用される設計ルールの多くのセットは、入力と出力が隣接しないようにすることにより、分離が困難な故障を最小化しようとするものである。
【００２２】
図７は、ＳＲフリップフロップを非意図的に生成する一般に発生するＣＭＯＳ短絡７２を備えたデジタル回路７０を表している。ここでは前の単純な組合わせ回路が状態を有するようになることから、この回路のトラブルシュートは困難である。後述するように、本出願はこの問題に対処する。
【００２３】
３  コンポーネントのモデル化
【００２４】
インバータに関する従来のＧＤＥモデルは次のとおりである。
2010531480.tif 000004
【００２５】
単一の遅延Δを有するものとしてインバータをモデル化する際、モデルは次のように変化する。
2010531480.tif 000005
【００２６】
接続不良を扱うためには、ワイヤ上の信号を更に詳細なレベルでモデル化する必要がある。コンポーネントの各端子は２つの変数でモデル化される。一方の変数は、コンポーネントがその出力（電流に概ね類似）に影響を及ぼそうとしているかをモデル化し、他方の変数は結果（電圧に概ね類似）を特徴付ける。正確に機能するノードについては、これらの電圧状の変数は等しい。ノードに対するコンポーネントの影響に対する、相互に一致しない５つの定性値（「ドライバ」又は「ｄ」と呼ぶ）が存在する。
・Ｄ（−∞）は接地への直接短絡を示す
・ｄ（０）は接地（すなわち、０）へ向けて引く
・ｄ（Ｒ）は高い（すなわち、ほとんど電流を引かない）受動抵抗型負荷を表す
・ｄ（１）は電力（すなわち、１）へ向けて引く
・ｄ（＋∞）は、電力への直接短絡を示す
【００２７】
上記５つの定性値は、コンポーネント端子の可能な電流シンク／ソース挙動の範囲を直観的に記述している。接地への直接短絡は大量の電流流入を引くことがある。接地への直接電力は大量の電流流出を駆動しうる。結果変数（「ｓ」）に対する３つの可能な定性値が存在する。
・ｓ（０）：結果は接地に十分に近いため、デジタル値０として検出される
・ｓ（ｘ）：結果は０でも１でもない
・ｓ（１）：結果は電力に十分に近いため、デジタル値１として検出される
【００２８】
これらの接続モデルにより、インバータは次のようにモデル化される。
2010531480.tif 000006
【００２９】
時間的・因果的挙動をより正確に記述すべくインバータをモデル化する。
2010531480.tif 000007
【００３０】
４  時間を表示する
【００３１】
実施はＡＴＭＳ／ＨＴＭＳ構成に基づいて行われる。各時点は明示的仮説ｔ＝ｉによりモデル化され、任意の２つの時間仮説は相互に矛盾する。これらの仮説は、全ての推論を個々の時間に分ける。しかし、時間の展開を組み込んだコンポーネントモデルを実体化するために、非単調ＡＴＭＳルールが必要である。特定のインバータＡのためのモデルの実体化は、以下の２つの節中でコード化される。
2010531480.tif 000008
【００３２】
しかし、時間は、明示的仮説により暗黙的に表される。従って、ｔ＝ｉについての仮説はｉｎ（Ａ，ｉ）に関する任意の演繹において暗黙的である。ｉｎ（Ａ）の任意の演繹は単一のｔ＝ｉｔｉ仮説を有する。本発明では、引数が先行点を超え次の点に適用されることを特定する新しいモード演算子Ｎを導入する。よって、２つのインバータ節は次のようになる。
2010531480.tif 000009
【００３３】
2010531480.tif 000010
【００３４】
結果がもはや先行する時点の存在に依存しないことから、このルールは非単調である。この推論ルールがなければ、時間が本質的に非単調であることから、時間のモデル展開は可能でない。
【００３５】
時間を表すこのスキームの利点は、毎回コンポーネントモデルを多数複製する必要がない点にある。一旦システムモデルを表す節が表されれば、更なる伝搬は全てＡＴＭＳによって遂行される。
【００３６】
リングオシレータの第１インバータへの入力がｔ1において０であると観測されたと仮定する。推論は以下のように進行する。
2010531480.tif 000011
【００３７】
後続の全ての推論は同一のパターンに従う。新しい仮説は追加されない。
【００３８】
５  リングオシレータのモデル化
【００３９】
時間的モデルを適用することで、図２のリングオシレータ２０について、図８の視覚化（ｅｎｖｉｓｉｏｎｍｅｎｔ）８０が生成される。図８中の頂点は各々Ａ、Ｂ、Ｃの出力に対する値でラベル付けされる。リングオシレータに関連する通常状態は、視覚化図の外側の状態によって記述される。これは、周期６ゲート遅延の安定発振に対応している。曖昧な移行がないことから、この発振は安定している。しかし、視覚化図の中心において、メタ安定発振に２つの偽状態が存在する。経時的に、ゲート遅延のうちの１つがわずかに長くあるいはわずかに短くなると、他のゲート遅延及びシステムは６つの安定状態のうちの１つに移行する。多数の移行が同時に発生することから、０００及び１１１からの全ての移行は曖昧である。０００〜１１１における発振は、図１３の望ましくない偽発振１３０のように見える。この理由から、多くの実際的なリングオシレータは、回路が既知の安定状態で起動するように、イネーブル入力（ＮＡＮＤゲート１１２を有する図１１の回路１１０を参照）を有する。
【００４０】
図９は、リングオシレータの定性シミュレーション９０を示す。同図において、頂点はｔ：Ａ，Ｂ，Ｃとラベル付けされている。ｔはゲート遅延における時間、Ａ、Ｂ、Ｃは個々のインバータ出力を表し、図１０はリングオシレータの所望出力１００を示す。
【００４１】
６  信号
【００４２】
値を表す表記ｆ（ｇ，ｔ）（例えばｉｎ（Ａ，ｔ））は、時間（変量）の可変値を表すアプローチとしては不適切である。ここでは、信号の概念を導入する。
【００４３】
定義１：信号は、（ゲート遅延の粒状度における）経時的な値の展開を表す。それは、０，１，？＞，から選択される一連のシンボルにより表示される。０と１はそれぞれの値を示し、「?」は値が未知であることを示し、「＞」は多数（未知数）のゲート遅延を示し、「*」は、以下のパターンが反復されることを意味する。信号は「*」を１つのみ有し、これは可及的に早い位置で出現する必要がある。１つの*を含み、その後に１と０が続く信号を明確な発振性（ｄｅｆｉｎｉｔｅｌｙ  ｏｓｃｉｌｌａｔｏｒｙ）と呼ぶ。*の後に１つの０又は１が続く信号を、安定（ｓｔｅａｄｙ）と呼ぶ。有効な信号の例を以下に示す。
・*０：安定信号が常に０
・＞*１：安定信号が最終的に１
・＞*０００１１１：３つのゲートリングオシレータの発振出力
【００４４】
信号はシステムの変数を全て記述すべく利用される。図１４は図１２のシミュレーション１２０の続き１４０を示す。詳細には、１４０はリングオシレータの出力における結果的な信号が？*１１１０００であることを示している。この拡張ＧＤＥは、特定の時点（例えば、ｉｎ（Ａ，ｔ1））における変数の値だけでなく、全ての最も一般的な信号（全ての信号が最終的には反復するパターンを有すると仮定する）を推論する。この派生を支持する仮説は、そのコンポーネントの仮説である。
2010531480.tif 000012
【００４５】
多くの場合において、信号はシステムの全コンポーネントの非アブノーマル挙動に依存することから、表面上はこれらの派生が多くの診断パワーを有するものとは見えない。
【００４６】
複雑な信号を推論する診断パワーを例示するために、４つのインバータ及び１つのＮＡＮＤゲートからなるやや複雑な図１５のリングオシレータ１５０を考慮する。入力が０００００*１であると仮定する。ＧＤＥは、＞*０００００１１１１１の出力を算出する。出力が*０であることが観察されたと仮定する。すると、以下のコンフリクトが生じたことが即座にわかる。
2010531480.tif 000013
【００４７】
（単純な０が観察された場合と同様に）観察*０が伝播される。全てのコンポーネントの故障の確立が同一であれば、通常のＧＤＥ調査ストラテジは次回の測定（Ｂ又はＣの出力のいずれか）を選択する。また、通常通り、不良発振を生ずるゲートは分離可能である。より直観的に、全ての観察及び入力が安定している場合、システムの観察において、回路は容易に解析可能な図１６の回路１６０のように見える。
【００４８】
ここで、ＳＲフリップフロップをリングオシレータと組み合わせた図１７の回路１７０について考察する。この回路の目的は、フリップフロップがＳにおいて単一の負パルスを見るとき、クロックがオンである（既にオンであることもある）ことを保証することにある。クロック出力が静止時０であることが観察されたと仮定する。静止時に観察されると、全てのコンポーネントがその入出力挙動Ｓ＝*０、Ｒ＝*１、Ｃ＝*０、Ｂ＝*１、Ａ＝*１に従っていたが、回路は故障している。静止時における所与の２つの入力が１であるとき、Ｓ及びＲの出力は正確には推測できない。たとえ、Ｓが*０であると観察された場合でも、そのことは静止時には推測できない。よって、Ｓ又はＲにおける故障の有無に関する情報は観察によって提供されない。幸い、Ｓ及びＲの故障は信号の基本的な伝搬によって直接決定できる。示されるような観察を所与とすると、Ｓの出力における信号は？？？１*である必要があり、よってＳ又はＲのうち一方が故障している。例えば、Ｓが０、又はＲが１であることは、この観察結果を説明している。静止時に診断を行うことが困難である理由は、０であるＳが正常に機能している際と同様の出力である点にある。この場合故障は過去に発生したことになる。
【００４９】
上記議論では、組み合わせ回路における時間的挙動のトラブルシューティング又は解析を可能とするプロセス及びシステムを示した。一般的な意味において、図１８に示されるように、回路システムの組み合わせ論理における意図的又は非意図的なサイクルを含むデジタル信号を解析しトラブルシュートすることを可能とする、システム信号の単純なモデルが生成される。
【００５０】
図１８の全体フロー図は上記概念を図示したものである。詳細には、ステップ１８０で、各時点に対し明示的仮説（ｔ＝ｉ）が立てられる。続くステップ１８２で、任意の２つの時間仮説が相互に矛盾すると定義され、全ての推論が個々の時間に分けられる。その後、展開する時間を組み込むコンポーネントモデルを実体化すべく非単調ルールが適用される。続くステップ１８４で、先行する時点の存在に依存しないものとして結果が定義される。続くステップ１８６で、単純化された信号モデルが上記に基づいて生成される。信号はシステムにおける経時的な値の展開を表す。
【００５１】
これらの概念は、場合により、図１９のフロー図に示されるようなＧＤＥフレームワークに更に詳細に適用される。詳細には、ステップ１９０で、モデルベースの解析のための、現実世界のシステム用モデルがＧＤＥフレームワークを利用して生成される。ステップ１９２で、テスト中のシステムの信号の単純化モデルを生成すべくＧＤＥフレームワークの時間的拡張が実施される。続くステップ１９４で、時間的拡張及び単純化された信号がＧＤＥフレームワークに伝播される。ステップ１９６で、時間的拡張を行ったＧＤＥフレームワークの適用を含むテスト中のシステムについて解析が行われる。続くステップ１９８で解析結果が取得される。
【００５２】
７  関連研究
【００５３】
関連する研究では、発振を停止したアナログオシレータのトラブルシュート、並びに定性推論システム又はソフトウェア（Ｑｕａｌｉｔａｔｉｖｅ  Ｒｅａｓｏｎｉｎｇ  Ｓｙｓｔｅｍ  ｏｒ  Ｓｏｆｔｗａｒｅ：ＱＳＩＭ）を備えたＣＭＯＳ設計のシミュレートに集中してきた。いずれのアプローチも、より多くの観察を通じて故障コンポーネントを分離するため、適切な挙動の仮説を明示的に記録するように一般化できない。
【００５４】
上記議論は、テスト中のシステムの故障を診断する、改善されたシステム及び方法の提供に注目した。既述の如くこのような診断テストは様々な領域で実施可能である。例えば、図２０に示されるように、本出願に示された概念は、本体２０２及びプローブ２０４を含む診断デバイス又はシステム２００で具体化することができる。プローブ２０４は、被測定デバイス２０６に対し操作的に関連する位置にあるように設計される。本体２０２は入力２０８及び出力２１０を含むことができる。入力２０８は英数字のキーパッド、スタイラス、音声、あるいはデータ又は指示を入力するための既知の他の入力設計もしくはインタフェースを含むことが可能である。出力２１０は診断調査の結果を表示する任意の種類のディスプレイとすることができる。本体２０２は、更に第２のセットの入力２１２を含むことができる。この場合、プローブ２０４によって検出された情報は自動的に診断デバイス２００に入力される。
【００５５】
本体２０２は、少なくともプロセッサ２１４、及び本明細書中に記載された概念を組み込んだコードを含むソフトウェアコードの処理を許可するメモリ２１６を含む計算能力を有することを理解されたい。更に、診断デバイス又はシステム２００は、出力報告のハードコピーの印刷、出力報告の口頭での陳述、あるいは解析又は診断結果に関する出力デバイス１９との通信を許可すべく出力デバイス２１９に接続される出力２１８を含むことができる。
【００５６】
上記説明はカスタマイズされた診断デバイス上で実行されてもよく、及び／又はハンドヘルドコンピュータ、ラップトップ、デスクトップ又は携帯情報端末を含む他の計算デバイスの一部として含まれてもよいことを認識されたい。更に、診断デバイス又はシステム２００は、本出願の概念を実施する方法の一例であることが意図されている。
【００５７】
別の実施形態では、図２０はプローブ２０４を含まず、診断は診断デバイス上で作動しあるいは計算能力を有する別のデバイスと関連付けられたコンピュータソフトウェア上で実施されてもよい。
【００５８】
図２１に示される別の実施形態において、診断デバイス又はシステム２２０自体がより大きい総合システム２２２に一部として埋め込まれる。総合システム２２２は、例えば、操作的に相互接続される、実線２３２で示されたコンポーネント２２４〜２３０を含むことができる。診断デバイス又はシステム２２０は、次いで、コンポーネント２２４〜２３０と操作により関連されることが点線２３４で示される。図２１は、本出願による診断デバイス又はシステムを利用可能なシステムの高レベルの例であることが認識されよう。診断デバイス又はシステム２２０の目的は、総合システム２２２の欠陥を識別し、人間の介在なく修理を開始することにある。このような総合システムの例として、電子複写機、自動車、宇宙機及び飛行機が挙げられる。
【００５９】
８  結論
【００６０】
この研究は、信号を表す単純な語彙によりＧＤＥフレームワークを経時的に拡張した。ＧＤＥと同一の基本的アーキテクチャ及び推論メカニズムは、一般化された信号の伝播に利用可能である。観察された信号と、推論され一般化された信号との間の不一致により、故障システムコンポーネントを分離するための診断が導出されうる。これらの一般化された信号は時間的挙動を経時的に捕捉し、同様にシーケンス回路（例えば、フリップフロップを含む）をトラブルシュートすべくこの信号を利用できる。静止時に観察可能な徴候を有さないことから、シーケンス回路の解析は困難であることがある。拡張により、従来に比して著しく広範囲な回路をトラブルシュートすべくＧＤＥを利用できる。
【００６１】
上記及びその他の各種特徴及び機能、又はその代替物は、所望の組み合わせにより他の多くの別のシステムもしくは応用とすることができることを理解されたい。現時点で予知又は予期されない代替、修正、変更又は改良は、今後当業者により実施される可能性があり、またこれらは以下の特許請求の範囲に含まれることが意図されている。
【図１】
2010531480.tif 000014
【図２】
2010531480.tif 000015
【図３】
2010531480.tif 000016
【図４】
2010531480.tif 000017
【図５】
2010531480.tif 000018
【図６】
2010531480.tif 000019
【図７】
2010531480.tif 000020
【図８】
2010531480.tif 000021
【図９】
2010531480.tif 000022
【図１０】
2010531480.tif 000023
【図１１】
2010531480.tif 000024
【図１２】
2010531480.tif 000025
【図１３】
2010531480.tif 000026
【図１４】
2010531480.tif 000027
【図１５】
2010531480.tif 000028
【図１６】
2010531480.tif 000029
【図１７】
2010531480.tif 000030
【図１８】
2010531480.tif 000031
【図１９】
2010531480.tif 000032
【図２０】
2010531480.tif 000033
【図２１】
2010531480.tif 000034
【国際調査報告】
2010531480.tif 000035