JPH08304517A

JPH08304517A - 順序論理回路内のテスト不能及び冗長故障を識別するための方法

Info

Publication number: JPH08304517A
Application number: JP7338407A
Authority: JP
Inventors: Miron Abramovici; アブラモヴッチミロン; Mahesh A Iyer; アナンザラマンアイヤーマヘシュ
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1994-12-29
Filing date: 1995-12-26
Publication date: 1996-11-22
Also published as: CA2159036A1; CA2159036C; EP0720097A3; EP0720097A2

Abstract

(57)【要約】（修正有）【課題】順序論理回路内の冗長及びテスト不能な故障
を識別するための方法が開示される。【解決手段】回路内の一つのリードが選択され、その
回路が、その選択された回路リードがある開始時間フレ
ームにおいて論理０を取ることができないと仮定すれば
ある与えられた時間フレームにおいてどの故障が仮説的
にテスト不能であるか、及びその選択された回路リード
がその開始時間フレームにおいて論理１を取ることがで
きないと仮定すればその与えられた時間フレームにおい
てどの故障が仮説的にテスト不能であるか、を決定する
ために分析される。その与えられた時間フレームにおい
て両方の仮説ケースにおいて検出不能である故障が、冗
長及びテスト不能な故障として識別される。この分析
が、開始時間フレームを含む時間フレームのレンジ内の
複数の時間フレームの個々に対して反復される。仮説的
に検出不能な故障が、結果としての指標及びそれらの対
応する回路リードと関連する時間フレームに基づいて決
定される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は順序デジタル論理回路の
ための自動テスト生成（ＡＴＧ）の分野に関係し、より
詳細には、順序デジタル論理回路内の冗長及びテスト不
能な故障の識別に関する。

【０００２】

【従来の技術】デジタル論理回路を充分にテストする問
題は、設計及び製造される複雑さの急速な増加ととも
に、年をおってますます複雑になってきている。この問
題に対する殆どの現在のアプローチは、自動テスト生成
（ＡＴＧ）システムの使用をともない、ＡＴＧシステム
には、ある与えられた回路設計に対する包括的なテスト
計画を自動的に生成する仕事が課せられる。このような
ＡＴＧシステムに、回路設計の記述が、典型的には、そ
の構成回路要素（例えば、論理ゲート）とこれら要素間
の及びその回路の一次入力及び一次出力への相互接続の
形式にて提供される。すると、ＡＴＧシステムは、その
与えられた回路設計の製造された一例の一次入力に加え
られたときその回路の一次出力の所にその製造された回
路がその与えられた回路設計に従って動作しているか否
かを（妥当な確からしさにて）識別する一つの応答を与
える回路刺激を自動的に生成する。

【０００３】ある製造された回路が示すであろうと理論
的に考えられる潜在的な機能障害の数は莫大である。こ
のために、ＡＴＧシステムは、典型的には、比較的少数
の潜在的な機能障害のみを考慮する故障“モデル”に基
づいて、それらのタスクを遂行し、また、（それらの結
果の品質を測定する）。“スタックアット”故障モデル
と称される最も一般的な故障モデルは、各回路リード
（つまり、ある回路要素への各入力及びこれからの各出
力）がその可能な値の一つ（例えば、論理０或は論理
１）に個別に“スタック（固着）”するような機能障害
の集合を列挙する。このようにして、考慮されるべき可
能な故障の数が回路リードの数の二倍に制限される。こ
の“スタックアット”故障モデルは、製造プロセスの結
果として典型的に発生する潜在的な物理的エラーの集合
に対する妥当な対応を提供するために、普通に受け入れ
られるようになってきている。

【０００４】殆どのＡＴＧシステムはモデル化された故
障を一度に一つづつ選択し、その故障を“検出”するこ
とができるテスト（つまり、回路刺激）を生成すること
を試みる。つまり、このシステムの目標は、ある“欠
陥”回路（つまり、ある与えられた故障を持つ回路）の
一次入力に加えられたとき、その回路の出力の所に正常
に動作する回路のそれとは異なる応答を与えるような回
路刺激を見つけることにある。通常、これら回路刺激
は、かなりの試行錯誤を伴う莫大な探索手続きの結果と
して生成される。ただし、最も典型的な回路設計におい
ては、その回路のある製造された一例内に実際に存在し
た場合でも、その回路の挙動に認識できる変化を全く与
えることのないわずかな故障が存在する。これら故障
は、従って、検出不能或はテスト不能である。（実際、
これらはしばしばその回路設計内の生来的な論理的冗長
を表わす。）このために、テスト不能な故障を識別する
ためのなんらかの手段を持たないと、殆どのＡＴＧシス
テムは、このような故障を、調べられている探索空間を
消耗しつくした後に、やっと、テスト不能であると識別
することとなる。さらに、ＡＴＧシステムの時間も（殆
ど全てでない場合でも）かなりの部分が実りのないテス
ト不能な故障に対するテストを生成することに費やされ
るはめとなる。

【０００５】

【発明が解決しようとする課題】幾らかのテスト不能な
故障を削除する従来の技術による技法が使用されるよう
になってきている。これら技法は、典型的には、テスト
不能な故障全体の中のほんの一部分のみを削除する。よ
り詳細には、従来の技術においては、回路リードの“可
制御性”及び“可観察性”分析が、ある与えられた論理
値にセットすることができない（つまり、その値に制御
することができない）、或はその回路の一次出力の所で
そのリードの値を観察することができない回路リードを
識別するために遂行される。このような分析の結果とし
て、限られた数のテスト不能な故障を識別することがで
きる。ただし、テスト不能な故障の大多数の識別はそれ
ほど単純なものではない。殆どのテスト不能な故障は、
そこにおいては、関連する回路リードの全てが個別的に
見ると両方の論理値に制御可能であり、しかも、その回
路の一次出力において観察可能であるという、より複雑
な回路冗長に起因して発生する。

【０００６】上に説明のテスト生成問題に加えて、ます
ます複雑になっている論理回路が設計者の仕事をますま
す困難にしており、これを救済する手段に対する必要性
が存在する。より具体的には、回路が可能な限り効率的
に設計されることが要望されるが、それでも、初期回路
はしばしば、その削除がその回路の挙動に影響を与えな
い冗長回路を含む。通常、回路設計者にとっては、回路
のこのような冗長部分を手作業で識別することは困難で
ある。

【０００７】

【課題を解決するための手段】本発明によると、順序回
路内の冗長及びテスト不能な故障を識別するための方法
が提供される。より具体的には、順序回路内の一つのリ
ードが選択され、その回路が、その選択された回路リー
ドがある与えられた開始時間フレームにおいて第一の値
（例えば、論理０）を取ることができないと仮定すると
ある与えられた時間フレームにおいてどの故障が仮説的
に検出不能であるか、及び、その選択された回路リード
がその与えられた開始時間フレームにおいて第二の値
（例えば、論理１）を取ることができないと仮定すると
その与えられた時間フレームにおいてどの故障が仮説的
に検出不能であるか、を決定するために分析される。次
に、その与えられた時間フレームにおいて両方の仮説ケ
ースにおいて検出不能である故障が冗長及びテスト不能
な故障であると識別される。この分析が、好ましくは、
一つの開始時間フレームを含むあるレンジの時間フレー
ム内の複数の時間フレームの個々に対して反復される。
これら時間フレームは、例えば、順序論理回路の従来の
組合わせ反復配列回路モデルのブロックから構成され
る。

【０００８】こうして選択される回路リードは、例え
ば、回路線茎（例えば、ファンアウト点）或は再収束回
路要素（例えば、ゲート）の再収束入力である。好まし
くは、本発明の方法が、これらの各回路線茎及びこれら
の各再収束ゲートの入力に対して反復され、結果とし
て、その与えられた論理回路に対するテスト不能な故障
の、全てではないとしても、殆どが識別される。

【０００９】本発明の一つの実施例によると、その選択
されたリードがある開始時間フレームにおいて第一及び
第二の値のある与えられた一つを取ることができないと
仮定するならばある与えられた時間フレームにおいて仮
説的に検出不能である故障が順序インプリケーション
（含意）手続きに基づいて決定される。このインプリケ
ーション手続きは、制御不能指標を伝播すること及び観
察不能指標を後ろ向きに伝播することから構成される。
より詳細には、与えられた（第一或は第二の）値に対す
る制御不能指標が選択された回路リードに割り当てら
れ、これがあらかじめ定められた伝播規則の集合に従っ
て、回路を通じて及び／或は時間フレームのあるレンジ
を通じて伝播される。加えて、観察不能指標がその回路
内で様々な時間フレームにおいてこれら制御不能指標に
基づいて生成され、これら観察不能指標が次に、これも
あらかじめ定められた伝播規則の集合に従って、その回
路を通じて及び／或は時間フレームのレンジを通じて後
ろ方向に伝播される。次に、仮説的に検出不能な故障
が、結果としての指標及びそれらの対応する回路リード
と関連する時間フレームに基づいて決定される。

【００１０】本発明のもう一つの実施例によると、順序
論理回路設計が、論理的冗長を削除するために修正され
る。本発明のこの方法が冗長及びテスト不能な故障を識
別するために使用され、その回路の一部分が識別された
故障に基づいて削除される。

【００１１】

【実施例】図１は、本発明の方法の一つの実施例によっ
て発生されるテストを使用する論理回路に対するテスト
プロセスを図解する。より詳細には、テスト生成器１１
は、テストされるべき回路記述に基づいて、入力刺激及
び対応する期待される出力応答を生成する。具体的に
は、テスト生成器１１は、例えば、後に図５との関連で
説明される本発明の方法の一つの実施例に従って動作す
る。テスト生成器１１は、例えば、汎用コンピュータシ
ステム及びその上で実行されるソフトウエアから構成さ
れる。各製造された回路１２は、複数の相互接続され
た、要素１３（例えば、ゲート及びフリップフロッ
プ）、一つ或は複数の一次入力１４、及び一つ或は複数
の一次出力１５を含む。

【００１２】ある与えられた製造された回路１２をテス
トしたい場合、テスト生成器１１によって生成された入
力刺激が、回路１２の一次入力１４に加えられ、結果と
しての出力応答が、一次出力１５上で測定される。この
結果としての出力応答が（テスト生成器によって生成さ
れた）期待される出力応答と、比較回路１６によって比
較され、これによって、その回路の故障が識別される。
ここに開示されるテストプロセスは、最も一般的には、
通常、自動テスト設備（ＡＴＥ）として知られているコ
ンピュータ制御されたシステムによって遂行される。典
型的なＡＴＭシステムは、（制御用コンピュータに加え
て）、ある製造された回路に、刺激を加え、その製造さ
れた回路からの応答を測定し、こうして測定された応答
を、あらかじめ定められた期待される応答と比較するよ
うに設計されたハードウエア要素を含む。テストされる
べき各製造された回路は、通常、ＡＴＥシステムに、標
準化されたインタフェースを介して“プラグイン”され
る。

【００１３】図２は、テスト不能な故障を持つ一例とし
ての組合わせ回路を示す。この一例としての回路は、
“Ａｎｄ”ゲート２１、２２、２３及び“Ｏｒ”ゲート
２４を含み、これらが互いに、相互接続され、さらに、
一次入力ａ、ｂ、ｃ及び一次出力ｇに、相互接続され
る。“Ｏｒ”ゲート２４への第一の入力リードが論理０
の値に永久的に固定されるｆの０スタック故障を想定す
る。（この例のように、回路線がファンアウトを含まな
い場合は、駆動ゲートの出力リードの所のスタック故障
と対応する受信ゲートの入力リードの所のスタック故障
との間には、意味のある区別は存在しないことに注意す
る。）

【００１４】ある与えられた回路リードの所のスタック
故障（例えば、０スタック）を検出（つまり、テスト）
するためには、その与えられたリードを、故障回路と正
常に動作する回路との値の差（例えば、０対１）を生成
するように“起動”すること、及び、さらに、結果とし
ての値の差をその回路の一次出力に、テストプロセスに
よって観察できるように、“伝播”することが必要であ
る。ある与えられた回路リード上のスタック故障を起動
することは簡単であり、単に、その回路リードをそのス
タック値とは反対の論理値にセットすることのみが必要
とされる。例えば、ある０スタック故障を検出するため
には、そのリードを論理１にセットすることが要求され
る。一方、故障（差）を伝播するためには、その与えら
れた回路リードから一次出力にいたる経路を“敏感化”
することが要求される。つまり、その経路に沿っての各
ゲートが、その与えられた経路上の値に対して敏感にな
ることが要求される。これは、これらゲートの全ての他
の入力上の値を適当な値にセットすることによって達成
される。（例えば、“Ｎａｎｄ”或は“Ａｎｄ”ゲート
のいずれかの入力からその出力に至る経路を敏感化する
ためには、全ての他の入力が論理１にセットされること
が要求される。）

【００１５】従って、ｆの０スタック故障を検出するた
めには、まず最初に、回路リードｃ及びｄを論理１にセ
ットすることが必要であり、次に、含意により（by imp
lication）、回路リードａ及びｂを両方とも論理１にセ
ットすることが要求される。しかしながら、このｆの０
スタック故障の影響を、ｆから一次出力に伝播するため
には、回路リードｅを（リードｅが論理０である場合に
のみ“Ｏｒ”ゲート２４が敏感化され、リードｆ上の論
理値が一次出力ｇに伝播することを許されるために）論
理０にセットすることが要求される。従って、含意によ
り、回路リードａ及びｂの少なくとも一つが論理０にセ
ットされなければならないこととなる！。この矛盾（つ
まり、回路リードａ及びｂが両方とも、論理１にセット
される必要があることと、回路リードａ及びｂの少なく
とも一つが、論理０にセットされることを要求されるこ
と、との間の矛盾）は、このｆの０スタック故障が、必
然的に、テスト不能であることを示す。換言すれば、こ
のｆの０スタック故障を検出するためには、回路リード
ａ或はｂの一つが、同時に、論理０かつ論理１であるこ
とが要求される。

【００１６】上の分析は、ＡＴＭシステムによって典型
的に遂行されるそれに類似する手続きを示すものであ
る。つまり、このｆの０スタック故障に対するテストを
考案するに当って、解決することができない矛盾が発生
することが理解できる。より典型的な（つまり、より複
雑な）回路においては、このような矛盾が、より頻繁に
発生する。ただし、これら矛盾は、しばしば、任意的な
決定（つまり、選択）が行なわれたポイントまで後方追
跡（バックトラッキング）し、そのポイントにおいて、
別の決定を行なうことによって解決することが可能であ
る。（例えば、ある“Ｎａｎｄ”ゲートの出力は、それ
らの入力の任意の一つを論理０にセットすることによっ
て論理１にセットすることができる）。ただし、図２の
一例としての回路内のｆの０スタック故障に対する上の
分析のケースにおいては、代替の選択は存在せず（別の
決定を行なうことはできず）、従って、後方追跡は不可
能である。

【００１７】図３は図２の一例としての回路のような組
合わせ回路内のテスト不能な故障を検出するための一例
としての方法の流れ図を示す。この一例としての手続き
は、回路内の複数の回路リードの個々を順番に反復的に
選択する。この手続きは、ステップ３１から開始され、
ここで、分析のためにこのような一つの（前に選択され
てない）回路リードが選択される。好ましくは、これら
の選択されるリードは、回路内の個々の全ての回路リー
ドを順番に選択するのではなく、再収束ファンアウトを
持つ回路線の茎（つまり、最終的に別の一つのゲートへ
の入力として再収束する経路に沿って進むファンアウト
枝を持つゲートの出力）及び再収束ゲートの再収束入力
に制限される。この望ましい制限は、テスト不能な故障
の原因となる矛盾は、再収束ファンアウト構造の結果と
してのみ生成するという事実に基づいて行なわれる。本
発明の方法の一つの実施例においては、選択されるリー
ドは回路線の茎に制限される。選択されるリードをこの
ように制限することによって、ある回路内のテスト不能
な故障の幾つかが発見できなくなる。にもかかわらず、
この制限されたアプローチは、典型的には、再収束入力
の分析を含めて識別されるテスト不能な故障の殆どを識
別することができ、一方において、回路線の茎のみを分
析することにより計算時間の大幅な短縮を達成する。

【００１８】ある与えられた回路リードが選択される
と、図３の一例としての手続きのステップ３２によっ
て、その回路リードが、論理０に（仮説的に）制御不能
であると（つまり、回路の入力に加えられる入力に関係
なく、論理０の値を取ることができないと）“マーク”
される。次に、ステップ３３において、インプリケーシ
ョン（含意）手続きが適用され、他の回路ノードが、最
初仮定された制御不能な状態からの含意により（by imp
lication）適当であると推論される適当な論理値に制御
できない或は観察不能である（つまり、その値を一次出
力に伝播することができない）とマークされる。結果と
しての制御不能及び観察不能指標に基づいて、仮説的に
テスト不能な故障の第一の集合が演繹的に決定される。
（図４に示されるインプリケーション規則の説明及び図
５のインプリケーション手続きの説明を参照するこ
と。）

【００１９】次に、ステップ３４において、選択された
回路リードが論理１に（仮説的に）制御不能である（つ
まり、論理１の値を取ることができない）とマークされ
る。次に、ステップ３５において、インプリケーション
手続きが再び適用され、これによって、最初仮定された
制御不能な状態から含意により正しと推論される適当な
論理値に制御不能である或は観察不能であるとマークさ
れる。制御不能及び観察不能指標のこの結果としての集
合に基づいて、仮説的にテスト不能な故障の第二の集合
が演繹的に決定される。

【００２０】こうして、仮説的にテスト不能な故障の二
つの集合、つまり、選択された回路リードが論理０に制
御不可能であると仮定した場合に、個々がテスト不能で
ある故障の第一の集合と、選択された回路リードが論理
１に制御不可能であると仮定した場合に、個々がテスト
不能である故障の第二の集合が演繹的に決定されること
となる。いま、時間上の任意の点において、その選択さ
れた回路リードは、二つの可能な論理値の一つのみを取
ることができるために、両方の集合内に出現する故障
は、必然的に、テスト不能である。ステップ３６におい
て、この選択された回路リードの分析に基づいてテスト
不能であると演繹的に決定された故障の内の両方の集合
内に出現する故障が、テスト不能な故障として、テスト
不能な故障として識別される。次に、判定３７におい
て、選択されるべき追加の回路リードが存在するか（例
えば、再収束ファンアウトを持つ回路線の全ての茎及び
再収束ゲートの全ての再収束入力が調べられたか）決定
され、分析されるべき追加のリードが存在する場合は上
に説明された手続きが繰り返される。一方、分析される
べき追加の回路リードが存在しない場合は、ステップ３
８において、自動テスト生成（ＡＴＧ）プロセスが、ス
テップ３１から３７の手続きによってテスト不能である
と識別された故障を明示的に排除して、この回路に関し
て遂行される。上に説明されたように、ステップ３８に
おいて、ＡＴＧプロセスは回路刺激及び期待される出力
応答を生成する。

【００２１】図４は制御不能標識の伝播及び観察不能標
識の後方伝播のための幾つかの一例としての規則を示
す。これら規則は、図３の手続きにおいて使用され、ま
た、図５により詳細に示される、一例としてのインプリ
ケーション手続きによって使用される。ゲート４１、４
２、４３、及び回路線ファンアウト点４４は、制御不能
標識の伝播に対する規則を説明し、ゲート４５、４６及
び４７は、観察不能標識の後方伝播に対する規則を説明
する。慣習的に、“バー０”が、論理値０に（仮説的
に）制御不能な回路リードの状態を示すために使用され
る。同様にして、“バー１”が、論理１に（仮説的に）
制御不能な回路リードの状態を示すために使用される。
加えて“＊”が（仮説的に）観察不能である回路リード
の状態を示すために使用される。

【００２２】例えば、インバータゲート４１は、インバ
ータゲートの入力が“バー０”にてマークされていると
きは、その出力は“バー１”にてマークされることを示
す。同様にして、インバータゲートの入力が“バー１”
にてマークされている場合は、その出力は“バー０”に
てマークされる。さらに、インバータゲートの出力が
“バー０”にてマークされているときは、その入力は
“バー１”にてマークされ、一方、インバータゲートの
出力が“バー１”にてマークされているときは、その入
力は“バー０”にてマークされる。これら規則は、イン
バータの入力がある与えられた値にセットできないとき
は、その出力は反対の値にセットすることができず、ま
た、この逆のことも言える、という明白な事実による。

【００２３】“Ｎａｎｄ”ゲート４２は、“Ｎａｎｄ”
ゲートの入力の全てが“バー０”にマークされたとき
に、その出力が“バー１”にマークされることを示す。
これは、“Ｎａｎｄ”ゲートの入力のどれも論理０にセ
ットできない場合は、その出力を論理１にセットする方
法は存在しないためである。さらに、“Ｎａｎｄ”ゲー
トの出力が“バー１”にてマーマされている場合は、そ
の入力の全てが“バー０”にマークされる。これは、
“Ｎａｎｄ”ゲートの出力が論理１にセットできない場
合は、その任意の入力を論理０にセットする方法はない
はずであるためである。“Ｎａｎｄ”ゲート４３は、
“Ｎａｎｄ”ゲートの任意の入力が“バー１”にてマー
クされているときは、その出力は“バー０”にてマーク
されることを示す。これは、もし“Ｎａｎｄ”ゲートの
任意の入力が論理１にセットできない場合は、その出力
を論理０にセットする方法は存在しないためである。

【００２４】ファンアウト点４４は、ある回路線茎が
“バー０”にてマークされているときは、そのファンア
ウト枝のおのおのは“バー０”にてマークされ、同様に
して、ある回路線茎が“バー１”にてマークされている
ときは、そのファンアウト枝のおのおのは“バー１”に
マークされることを示す。これは、あるファンアウト枝
は、ある与えられた値にその対応する枝をその値にセッ
トすることによってのみセットできるためである。さら
に、ある回路線茎の各ファンアウト枝が“バー０”にマ
ークされている場合は、その枝は“バー０”にてマーク
され、同様にして、各ファンアウト枝が“バー１”にて
マークされているときは、その枝は、同一の理由にて、
“バー１”にマークされる。他のゲートタイプ或は組合
わせ回路要素に適用される制御不能指標の伝播のための
類似する規則が当業者においては明白であると考えられ
る。

【００２５】インバータゲート４５は、インバータゲー
トの出力が“＊”にてマークされているとき、その入力
もまた“＊”にてマークされることを示す。“Ｎａｎ
ｄ”ゲート４６は、“Ｎａｎｄ”ゲートの出力が“＊”
にてマークされているとき、その入力の個々が“＊”に
てマークされることを示す。これら規則は、任意のゲー
トの出力が観察不能であるときは、その入力のどれもが
観察できないという事実による。“Ｎａｎｄ”ゲート４
７は、その入力の一つが“バー１”にてマークされてい
るとき、その他の入力のおのおのが“＊”にてマークさ
れることを示す。これは、“Ｎａｎｄ”ゲートへの入力
は、他の入力の全てを論理１にセットすることによって
のみ観察できるためである。他のゲートタイプ或は組合
わせ回路要素に適用される観察不能標識の後方伝播に対
する類似する規則が当業者においては明らかになるもの
である。（ただし、回路線茎は、幾つかの状況において
は、そのファンアウト枝の全てが観察不能の場合でも、
観察できることがあることに注意する。）

【００２６】図５は、図３の一例としての手続きのステ
ップ３３及び３５において使用される一例としてのイン
プリケーション手続きの流れ図を示す。具体的には、図
５の手続きは、ある与えられた選択された回路リードが
指定される値に制御不能である場合に、（仮説的に）テ
スト不能である故障の集合を決定する。この一例として
の手続きは、一例として、図４に示され、上に説明され
たような伝播規則を使用する。

【００２７】ステップ５１において、初期制御不能指標
が選択された回路リードに割り当てられる。この制御不
能指標は、選択されたリードを、その手続きが図３の手
続きのステップ３３を実現するために使用されている
か、ステップ３５を実現するために使用されているかに
依存する指定された論理値（０或は１）に制御不能であ
るとマークする。次に、ステップ５２において、あらか
じめ定められた制御不能指標伝播規則（例えば、図４の
ゲート４１、４２、４３及び回路線ファンアウト点４４
に関して示される規則）を使用して、制御不能指標が回
路を通じて伝播される。ステップ５３において、あらか
じめ定められた観察不能生成規則（例えば図４７のゲー
ト４７に関して示される規則）を使用して、適当な回路
リードに初期観察不能指標が割り当てられる。次に、ス
テップ５４において、あらかじめ定められた観察不能指
標伝播規則（例えば、図４のゲート４５及び４６に関し
て示される規則）を使用して、観察不能指標が回路を通
じて後方に伝播される。

【００２８】この時点で、（あらかじめ定められた規則
の集合に基づく）初期制御不能想定から制御不能及び／
或は観察不能であると含意できる全ての回路リードが、
そのようにマークされたこととなる。従って、後は、単
に、仮説的にテスト不能な故障を演繹的に決定する問題
のみが残され、これは、様々な回路リード上に出現する
マークから行なわれる。これら故障には、より詳細に
は、起動不能な故障と伝播不能な故障が含まれる。そし
て、（仮説的に）起動不能な故障には、論理１に制御不
能であるとマークされたリード上の０スタック故障と、
論理０に制御不能であるとマークされたリード上の１ス
タック故障が含まれる。一方、（仮想的に）伝播不能な
故障には、観察不能であるとマークされたリード上の０
スタック故障及び１スタック故障の両方が含まれる。

【００２９】従って、図５の手続きのステップ５５にお
いて、制御不能指標にてマークされた個々の回路リード
が選択され、（判定５６によって決定される）そのマー
クと関連する制御不能の値に依存して、その回路リード
上の１スタック故障（ステップ５７）、或はその回路リ
ード上の０スタック故障（ステップ５８）のいずれかが
仮説的にテスト不能な故障の集合に加えられる。判定５
９は、個々の全ての制御不能指標が処理されるまで、次
の制御不能標識にてマークされた回路リードを選択する
ために、ステップ５５に戻る。同様にして、ステップ６
１は、観察不能指標にてマークされた個々の回路リード
を選択し、ステップ６２は、その回路リード上の０スタ
ック故障及び１スタック故障の両方を、仮説的にテスト
不能な故障の集合に加える。判定６３は、個々の全ての
観察不能指標が処理されるまで、次の観察不能指標にて
マークされた回路リードを選択するためにステップ６１
に戻る。

【００３０】ここまでの説明は組合わせ回路内のテスト
不能な故障を識別するための技法に限定されてきたが、
これら技法に対して（本発明に従って）幾つかの改良を
施すことができ、これによって、順序回路に適用可能な
類似する技法を得ることが可能である。図６はテスト不
能な故障を持つ一例としての順序回路を示す。この一例
としての回路は、“Ｏｒ”ゲート６４、６９、“Ａｎ
ｄ”ゲート６６、及び“フリップフロップ”要素６５、
６７、６８を含み、これらが互いに、相互接続され、さ
らに一次入力ａ、ｂ、ｃ、及び二次出力ｉに、相互接続
される。“フリップフロップ”６５、６７及び６８は、
同期順序回路において典型的であるように、一つの共通
のクロック信号ＣＬＫによって制御される。クロック信
号の各動作（つまり、各クロックパルス）とともに、新
たな“時間フレーム”が始まる。回路内の各リードは
（少なくとも理論的には）各時間フレームにおいて別個
の論理値を取ることができる。ただし、同期順序回路に
おいては、各時間フレームにおいてある与えられた回路
リードによってこれらの中の一つの（安定な）論理値の
みが取られる。従って、ある与えられた故障の検出が同
一の時間フレームにおいて、幾つかの回路リードが矛盾
する論理値を取ることを要求する場合、この故障は、必
然的に、検出不能である。

【００３１】例えば、ｇの０スタック故障を考えるもの
とする。この故障をある与えられた時間フレーム（これ
を時間“ｔ”と呼ぶ）において“起動”するためには、
回路リードｇが時間“ｔ”において、論理値１を取るこ
とが要求される。これは、回路リードｆが前の時間フレ
ーム（つまり、時間“ｔ−１”において論理１であるこ
とを含意（imply ）し、一方、このことは、回路リード
ｅ及びｃ１の両方が時間“ｔ−１”において両方とも論
理１であることを含意する。従って、回路リードｃは、
時間“ｔ−１”において論理１でなければならない。し
かしながら、ｇの０スタック故障を伝播するためには、
回路リードｈがこの故障が起動された時間（つまり、時
間“ｔ”において論理０であることが要求される。これ
は、今度は、回路リードｃ２が前の時間フレーム（つま
り、時間“ｔ−１”）において論理０であるべきことを
含意する。従って、回路リードｃは、時間“ｔ−１”に
おいて論理０でなければならず、これは、回路リードｃ
が時間“ｔ−１”において論理１でなければならないと
いう上の要件と矛盾する。

【００３２】図６を参照しての上の説明からわかるよう
に、テスト不能な故障は、同期順序回路においては、複
数の時間フレームを通じての論理値割り当てを分析する
ことによって識別することができる。より詳細には、あ
る故障はこのような分析を矛盾に到達するまで遂行する
ことによってテスト不能であると決定することができ
る。しかしながら、図６の一例としての順序回路の上に
説明の分析は、図２の一例としての組合わせ回路を参照
して上に説明された分析と同様に、ＡＴＧシステムによ
って典型的に遂行されるそれと類似する、通常、時間の
かかる莫大な探索を必要とする手続きを採用する。

【００３３】一方、本発明の一例としての実施例による
順序回路内のテスト不能な故障を識別するための方法に
おいては、それらの検出のためには、ある選択された回
路リードが二つの異なる論理値を同時に（つまり、同一
の時間フレームにおいて）取ることを要求するような故
障が決定される。この一例としての方法は、分析のため
にある回路リードを選択し、その時間においてその回路
リードの所で論理値の割り当ての矛盾が仮説的に発生す
ると推定される任意の時間フレーム（ここでは開始時間
フレーム或は時間“０”と呼ばれる）を定義する。さら
に、この開始時間フレームを含むあらかじめ定められた
レンジの時間フレームが指定される。次に、（これら時
間フレームの任意の一つにおいてける）その起動及び／
或は伝播がその選択されたリード上の割り当てられた論
理値の上述のような矛盾を要求することが決定された故
障がその開始時間フレームにおいて識別される。ある与
えられた時間フレームにおけるその起動及び伝播がこの
ような矛盾を要求する故障は、その与えられた時間フレ
ームにおいて、検出不能であると称される。しかしなが
ら、開始時間フレームは任意に選択されるために（つま
り、開始時間フレームは任意の時間フレームであり得る
ために）、これら故障は、必然的に、テスト不能であ
る。

【００３４】図７はそれらを通じて順序回路のこのよう
な分析が遂行される複数の時間フレームを示す。より詳
細には、開始時間フレームが“０”として識別される
が、これは、そのとき衝突が（仮説的に）発生すると推
定される時間フレームを表わす。前方向の時間フレーム
１８−１から１８−ｆは、開始時間フレームの直後に続
くあらかじめ定められた数の相対時間フレーム（時間フ
レーム“１”から時間フレーム“ｆ”までとして識別さ
れる“ｆ”個の時間フレーム）を表わす。後ろ方向の時
間フレーム１９−１から１９−ｂは、開始時間フレーム
の直前のあらかじめ定められた相対時間フレーム（時間
フレーム“−１”から時間フレーム“−ｂ”までとして
識別される“ｂ”個の時間フレーム）を表わす。こうし
て、おのおのが開始時間フレームとの相対的な位置に基
づいて識別される全部で“ｆ＋ｂ＋１”個の時間フレー
ム（時間フレーム“−ｂ”から時間フレーム“ｆ”まで
が、時間フレーム“ｆ”を含めて）考慮される。

【００３５】いま、例えば、図６の一例としての回路に
おいて、ｇが０スタック故障を持つものと考える。上の
分析からわかるように、ある与えられた時間フレーム
“ｔ”においてこの故障を起動するためには、回路リー
ドｃが時間フレーム“ｔ−１”において論理１であるこ
とが要求され、一方、これと同一の時間フレーム“ｔ”
におけるこの影響の伝播には、回路リードｃが時間フレ
ーム“ｔ−１”において論理０であることが要求され
る。開始時間フレーム（つまり、時間フレーム“０”）
においてリードｃ上の矛盾の可能性を仮定することによ
って、（本発明の一つの実施例に従って）、ｇの０スタ
ック故障を、（相対的な）時間フレーム“１”において
検出不能であると、このような矛盾を起こすことなく、
決定することが可能である。換言すれば、ｇの０スタッ
ク故障の検出には、故障が起動伝播されることを要求さ
れる時間フレームより、１時間フレームだけ前の時点
で、回路リードｃ上に矛盾が発生することが要求され
る。従って、ｇの０スタックは、必然的に、テスト不能
な故障である。当業者においては、開始時間フレームを
基準とした後ろ方向時間フレーム“−ｂ”から“−１”
も含む他の時間フレームにおいて検出不能であると決定
される故障に対しても類似する分析を適用できることが
理解できるものである。

【００３６】図８は順序回路内のテスト不能な故障を識
別するための本発明の方法の一つの実施例を説明する流
れ図である。最初に、ステップ７１において、分析に対
する時間フレームのレンジが指定される。つまり、図７
に示されるような開始時間フレーム直後のあらかじめ定
められた数の時間フレーム（“ｆ”）及び開始時間フレ
ーム直前のあらかじめ定められた数の時間フレーム
（“ｂ”）が指定される。従って、図８の一例としての
手続きによって評価されるべき時間フレームの総数は、
“ｆ＋ｂ＋１”である。これらあらかじめ定められた数
（“ｆ”及び“ｂ”）は、新たなテスト不能な故障が発
見されるとともに徐々に、或は、所定の最大値（例え
ば、５）に達するまで、徐々に増加することができる。

【００３７】ステップ７２において、分析のために（前
に選択されていない）回路リードが選択される。ステッ
プ７３において、各“ｆ＋ｂ＋１”個の相対時間フレー
ムに対して１つづつ得られる複数の、開始時間フレーム
（つまり、時間フレーム“０”）においてその選択され
た回路リードが論理０の値に制御不能であるならば（仮
説的に）テスト不能である故障の集合が決定される。同
様にして、ステップ７４において、各“ｆ＋ｂ＋１”相
対時間フレームに対して１つづつ得られる複数の、開始
時間フレーム“０”においてその選択された回路リード
が論理１の値に制御不能であるならば（仮説的に）テス
ト不能である故障の第二の集合が決定される。より詳細
には、各相対時間フレームに対して、ステップ７３及び
７４において、それぞれ、選択された回路リードが時間
フレーム“０”において対応する論理値を取ることがで
きないという仮説的な想定が与えられたとき、その時間
フレームにおいて起動することができないか、或は、起
動されたとしてもその時間フレームにおいてその影響を
伝播することができないような故障が決定される。次
に、ステップ７５において、仮説的にテスト不能である
とれる上の第一と第二の故障の集合の両方に含まれるこ
れら故障の内の同一の（相対的）時間フレームに対応す
る故障がテスト不能であると識別する。従って、こうし
て識別された故障を検出するためには、必然的に、その
選択された回路リードが、開始時間フレームにおいて、
同時に矛盾する論理値を取ることが要求される。判定７
６において、選択されるべき残されたリードが存在する
か決定され、最後に、ステップ７７において、ステップ
７１から７６の手続きによってテスト不能であると識別
された故障を明示的に排除して、元の順序回路に関して
自動テスト生成（ＡＴＧ）プロセスが遂行される。

【００３８】図８の一例としての手続きのステップ７３
及び７４は、様々な時間フレームにおいて、様々な回路
リードに制御不能指標及び観察不能指標を割り当てる順
序インプリケーション手続きを使用して遂行される。図
５の一例としてのインプリケーション手続きと概念的に
は類似するが、順序回路の場合は、このインプリケーシ
ョン手続きは、フリップフロップ回路要素を扱い、さら
に、これら指標のおのおのを特定の時間フレームに対し
て割り当てることが要求される。さらに、順序インプリ
ケーション手続きは、時間フレーム境界を横断してこれ
ら割り当てを行なうことができなければならない。

【００３９】図９は、フリップフロップ回路要素を通じ
て制御不能指標を伝播するため、及び観察不能指標を後
ろ方向に伝播するための一例としての規則を示す。より
詳細には、“フリップフロップ”４８は、ある与えられ
た時間フレーム（例えば、時間“ｉ”）においてフリッ
プフロップのデータ入力が“バー０”にてマークされて
いる場合、次の時間フレーム（例えば、時間“ｉ＋
１”）においてその（“Ｑ”）出力が“バー０”にてマ
ークされることを示す。同様にして、フリップフロップ
のデータ入力が時間“ｉ”において“バー１”にてマー
クされている場合、その出力は時間“ｉ＋１”において
“バー１”にてマークされる。さらに、あるフリップフ
ロップの出力が時間“ｉ＋１”において“バー０”にて
マークされている場合、そのデータ入力は時間“ｉ”に
おいて“バー０”にてマークされ、あるフリップフロッ
プの出力が時間“ｉ＋１”において“バー１”にてマー
クされている場合、そのデータ入力は時間“ｉ”におい
て“バー１”にてマークされる。これら規則は、あるフ
リップフロップのデータ入力がある与えられた時間フレ
ームにおいてある与えられた値にセットできない場合、
その出力は、続く時間フレームにおいてその値にセット
することができず、また、逆のこともいえる、という事
実に基づく。観察不能に関しては、“フリップフロッ
プ”４９は、あるフリップフロップの（“Ｑ”）出力が
ある与えられた時間フレーム（例えば、時間“ｉ”）に
おいて“＊”にてマークされている場合、そのデータ入
力はその前の時間フレーム（例えば、時間“ｉ−１”に
おいて“＊”とマークされることを示す。つまり、ある
フリップフロップの出力がある与えられた時間フレーム
において観察不能である場合、そのデータ入力は、その
前の時間フレームにおいて観察不能である。

【００４０】図１０は図８の一例としての手続きのステ
ップ７３及び７４において使用されるための一例として
の順序インプリケーション手続きを示す。より詳細に
は、図１０の手続きは、時間フレームレンジ内の各時間
フレームに対して、ある与えられた、選択された回路リ
ードが開始時間フレームにおいてある指定された値に制
御不能であるとき、その時間フレームにおいて（仮説的
に）検出不能であると推定される故障の集合を決定す
る。この一例としての手続きは、一例として、図４及び
９との関連で上に説明されたような伝播規則を使用す
る。

【００４１】ステップ９１において、選択された回路リ
ードに、その開始時間フレーム（つまり、時間フレーム
“０”）において、初期制御不能指標が割り当てられ
る。制御不能指標は、選択されたリードを、その手続き
が、図８の手続きのステップ７３を実現するために使用
されるか或は７４を実現するために使用されるかに依存
して指定される論理値（０或は１）に制御不能であると
マークする。次に、ステップ９２において、（図４のゲ
ート４１、４２、４３及び回路線ファンアウト点４４、
及び図９のフリップフロップ４８に関して示されるよう
な）あらかじめ定められた制御不能標識伝播規則を使用
して、制御不能指標が、回路を通じて、及び時間フレー
ムレンジ内の様々な時間フレームを横断して伝播され
る。（図９のフリップフロップ４８に関して示される伝
播規則は、それを行なった場合、制御不能指標が時間フ
レームレンジの外側の時間フレームに伝播されるような
ときは、好ましくは、使用されるべきでないことに注意
する。）ステップ９３において、あらかじめ定められた
観察不能指標生成規則（例えば、図４のゲート４７に関
して示される規則）を使用して、適当な回路リードに、
初期観察不能指標が割り当てられる。次に、ステップ９
４において、あらかじめ定められた観察不能指標伝播規
則（例えば、図４のゲート４５及び４６、並びに図９の
フリップフロップ４９との関連で示されるような規則）
を使用して、観察不能指標が回路を通じて後方に、及び
時間フレームレンジ内の時間フレームを横断して後方
に、伝播される。（図９のフリップフロップ４９との関
連で示される伝播規則は、それを行なった場合、観察不
能指標が時間フレームレンジの外側に伝播するようなと
きは、好ましくは、使用されるべきでないことに注意す
る。）

【００４２】この時点で、初期制御不能想定から（あら
かじめ定められたセットの規則に基づいて）制御不能及
び／或は観察不能であると含意できる（時間フレームレ
ンジ内の）全ての時間フレームにおける全ての回路リー
ドのマーク付けが完了する。従って、残された唯一の仕
事は、各時間フレームごとに、仮説的に検出不能な故障
を演繹的に決定することであり、これは、その時間フレ
ームにおいて様々な回路リード上に出現するマーキング
の結果として遂行される。より詳細には、その特定の時
間フレームにおいて、起動することができない、或は伝
播することができない故障の集合が存在する。つまり、
これらの中には、（仮説的に）起動することができない
故障として、論理１に制御不能であるとマークされたリ
ード上の０スタック故障と、論理０に制御不能であると
マークされたリード上の１スタック故障が含まれる。一
方、（仮説的に）伝播することができない故障として、
観察不能としてマークされたリード上の０スタック故障
と１スタック故障の両方が含まれる。

【００４３】このために、ステップ９５において、分析
された時間フレーム内の各時間フレームが選択され、次
に、ステップ９６において、その時間フレームにおいて
制御不能指標にてマークされた各回路リードが選択され
る。次に、（判定９７によって決定される）マークされ
た制御不能の値によって、その回路リード上の１スタッ
ク故障（ステップ９８）、或は、その回路リード上の０
スタック故障が、その与えられた時間フレームに対する
仮説的に検出不能な故障の集合に加えられる。判定１０
０において、その与えられた時間フレームに対する個々
の制御不能指標の処理が終了したと決定されるまで、こ
のプロセスは、ステップ９６に戻る。

【００４４】同様に、ステップ１０１において、その与
えられた時間フレームに対して観察不能指標がマークさ
れた各回路リードが選択され、ステップ６２において、
その回路リード上の０スタック故障及び１スタック故障
の両方がその与えられた時間フレームに対する仮説的に
検出不能な集合に加えられる。判定１０３において、そ
の与えられた時間フレームに対する個々の観察不能指標
の処理が終了したと決定されるまで、このプロセスは、
ステップ１０１に戻る。

【００４５】その与えられた時間フレームに対する全て
の制御不能指標及び観察不能指標が処理された時点で、
その時間フレームに対する仮説的に検出不能な故障の集
合の処理は完結する。判定１０４において、その時間フ
レームレンジ内の全ての時間フレームが処理され、その
時間フレームレンジ内の各時間フレームに対する仮説的
に検出不能な故障の生成が終了したことが判定されるま
で、このプロセスは、ステップ９５に戻る。

【００４６】図１１は、順序回路から冗長を削除するた
めの本発明の方法の追加の一つの実施例を説明する流れ
図である。本発明のこの方法は、順序回路内のテスト不
能な故障のみでなく、事実、冗長も識別するために、本
発明の方法の一つの実施例に従って、テスト不能／冗長
故障を反復的に識別し、これに従って回路設計を整理す
ることによって、順序回路を簡素化することが可能であ
る。結果としての回路は、より小さいが、論理的には元
の回路と等価なものとなる。（このような回路の整理
は、好ましくは、あるテスト不能な故障が識別されるご
とに、一つづつ遂行されるべきである。これは、テスト
不能な故障に基づく回路の一部分の削除が回路の他の故
障のテスト可能性に影響を与えることがあるためであ
る。）

【００４７】図１１の一例としての冗長削除手続きは、
（一度に）一つのテスト不能な故障を識別し、その故障
のテスト不能によって含意にされる回路の冗長部分を削
除し、次に、このプロセスを、さらにテスト不能な故障
が識別されなくなるまで反復する。より詳細には、ステ
ップ８１において、最初に、回路のある与えられた（現
在の）バージョンから初期回路リードが分析のために選
択され、分析に対する時間フレームレンジが指定され、
こうして、この冗長削除手順のある与えられた反復部分
が開始される。ステップ８２において、複数の仮説的に
テスト不能な故障の第一の集合が、各時間フレームに対
して一つづつ、選択された回路リードが開始時間フレー
ムにおいて、例えば、論理０に制御できないという想定
に基づいて決定される。同様にして、ステップ８３にお
いて、複数の仮説的にテスト不能な故障の第二の集合
が、各時間フレームに対して１つづつ、選択された回路
リードが開始時間フレームにおいて、例えば、論理１に
制御できないという想定に基づいて決定される。次に、
ステップ８４において、仮説的にテスト不能な故障の両
方の（第一及び第二の）集合内に含まれる故障の内の同
一時間フレームに対応する故障がテスト不能であると識
別される。

【００４８】判定８５において、ステップ８４において
テスト不能であると識別された故障が存在するか否か決
定され、存在する場合は、ステップ８６において、これ
ら識別されたテスト不能な故障の任意の一つが選択され
る。次に、ステップ８７において、選択された故障のテ
スト不能性に基づいて冗長であると決定される回路の部
分が削除される。例えば、ある与えられた回路リード上
の０スタック故障がテスト不能な故障である場合は、そ
の与えられた回路リードに信号を送る全ての回路が（そ
れが削除されない他の回路リードに信号を送らないとい
う条件で）削除され、その与えられた回路リードが論理
０の値に固定される（例えば、アースに繋がれる）。ス
テップ８６におけるテスト不能な故障の選択は、勝手に
行なうことも、或は、好ましくは、その選択に基づいて
ステップ８７において削除されるであろう回路の部分に
基づいて行なうこともできる。（例えば、テスト不能な
故障は、好ましくは、その選択によって削除されること
となる回路の品質に基づいて選択することもできる。こ
のようにして、この冗長削除手続きの効率を向上させる
ことができる。

【００４９】初期化後のその回路の挙動に影響を与えな
い順序回路の幾つかの部分は、それらがその回路の初期
化を阻止する場合は、冗長ではないことに注意する。従
って、本発明の一つの実施例においては、選択されたテ
スト不能な故障は、好ましくは、最初に、関連する冗長
回路の削除が結果として初期化不能な回路を与えないこ
とを確かめるために分析される。この検証プロセスは、
例えば、その与えられたノードを各時間フレームにおい
てそのノードがその故障値に制御不能になるような時間
が存在しないか調べることによって遂行される。例え
ば、本発明の方法によって、ノード“ｎ”上の１スタッ
ク故障が冗長及びテスト不能な故障であると識別された
場合、この回路は、ノード“ｎ”が任意の複数の時間フ
レームの一つ一つにおいて制御不能であるとして出現し
ないかぎり、対応する回路の削除によって初期化不能と
なることはない。

【００５０】ステップ８７において冗長回路が削除され
たら、ステップ８１に戻ることによって、この冗長削除
手続きの一つの新たな反復が開始される。この新たな反
復は、その回路の新たなバージョンをその現在のバージ
ョンとして使用することとなる。

【００５１】判定８５において、ステップ８４において
故障が識別されなかったことが決定された場合は、判定
８８において、その与えられた反復内で（つまり、ステ
ップ８７によって最後に修正された回路以降の）分析さ
れるべき回路リードがさらに存在するか否か決定され
る。存在する場合は、ステップ８９において、その与え
られた反復内でまだ選択されてない回路リードが選択さ
れ、その回路の現在のバージョン内のテスト不能な故障
を識別するために、ステップ８２に戻る。ステップ８８
において、その与えられた反復内で分析されるべきそれ
以上の回路リードが存在しないことが発見された場合
は、この手続きの全反復がテスト不能な故障を識別する
ことなく遂行されたこと、つまり、その回路の現在のバ
ージョン内にテスト不能な故障が発見されなかったここ
となる。従って、図８の冗長削除手続きは終了し、その
回路のこの最終バージョンが元の回路設計に論理的に等
価な回路として採用される。

【００５２】本発明の幾つかの特定の実施例が説明され
たが、これら実施例は、本発明の原理を適用することに
よって考案することができる多くの可能性の内の特定の
構成を解説することを目的とするものであることを理解
されるべきである。当業者においては、本発明の精神及
び範囲から逸脱することなしに、多数の様々な他の構成
を考案できるものである。例えば、上の実施例は論理０
及び論理１の値から構成される二値（二進）論理系に基
づいて動作する論理回路に制限されたが、３値（三進論
理）或はそれ以上の値に基づく論理系を使用する他の実
施例を考えることも可能である。加えて、上に説明され
た図５のインプリケーション手続き及び図１０の順序イ
ンプリケーション手続き以外の技法を、ある回路リード
がある与えられた論理値に仮説的に制御不能なら、テス
ト不能であると推定される故障の集合を決定するために
使用することも可能である。さらに、順序回路内のテス
ト不能な故障を識別するための上に説明された方法は同
期順序回路との関連で説明されたが、当業者において
は、他の実施例を考案すること、例えば、本発明の技法
を、非同期順序回路に適用することも、また、可能であ
る。

【図面の簡単な説明】

【図１】本発明の方法の一つの実施例によって生成され
たテストを使用する論理回路に対するテストプロセスを
図解する。

【図２】テスト不能な故障を持つ一例としての組合わせ
回路を示す。

【図３】組合わせ回路内のテスト不能な故障を識別する
ための一例としての方法を説明する流れ図である。

【図４】制御不能指標の伝播及び生成及び観察不能標識
の後方伝播のための選択された一例としての規則を示
す。

【図５】図３の一例としての手続きにおいて使用される
べき一例としてのインプリケーション手続きの流れ図を
示す。

【図６】テスト不能な故障を持つ一例としての順序回路
を示す。

【図７】順序回路のテスト不能な故障の分析がそれを通
じて遂行される複数の時間フレームを図解する。

【図８】順序回路内のテスト不能な故障を識別するため
の本発明の方法の一つの実施例を説明する流れ図であ
る。

【図９】フリップフロップ回路要素を通じて及び時間フ
レームを横断して、制御不能信号を伝播するため及び観
察不能指標を後ろ方向に伝播するための一例としての規
則を示す。

【図１０】図８の一例としての手続きにおいて使用され
るための一例としての順序インプリケーション手続きの
流れ図を示す。

【図１１】順序回路から冗長を削除するために使用され
る本発明の方法のもう一つの実施例を説明する流れ図で
ある。

フロントページの続き (72)発明者マヘシュアナンザラマンアイヤーアメリカ合衆国．08512 ニュージャーシィ，クランバリー，レミントンサークル２

Claims

【特許請求の範囲】

【請求項１】順序論理回路のモデル内のテスト不能な
故障を識別するための方法であって、この順序論理回路
のモデルが順序論理回路を表わし、この順序論理回路が
複数の回路要素から構成され、これら回路要素が一つ或
は複数の回路リード及びこれら回路要素の回路リードを
相互接続する複数の回路線を持ち、これら回路要素が少
なくとも一つのフリップフロップを持ち、前記の各回路
リードが複数の時間フレームのおのおのにおいてあらか
じめ定められた複数の論理値の一つを取る能力を持ち、
この複数の時間フレームが一つの開始時間フレームを含
み、この方法が：前記の順序論理回路の複数の回路リー
ドの一つを選択するステップ；故障の第一の集合を決定
するステップ；及び故障の第二の集合を決定するステッ
プを含み；前記の故障の第一の集合が前記の選択された
回路リードがもし前記の開始時間フレームにおいて前記
のあらかじめ定められた複数の論理値の第一の値をとる
ことができないと仮定するならば、前記の複数の時間フ
レームのある一つにおいて検出不能であると推定される
複数の故障から構成され；前記の故障の第二の集合が前
記の選択された回路リードがもし前記の開始時間フレー
ムにおいて前記のあらかじめ定められた複数の論理値の
第二の値をとることができないと仮定するならば、前記
の与えられた時間フレームにおいて検出不能であると推
定される複数の故障から構成され；この方法がさらに前
記の故障の第一の集合と前記の故障の第二の集合の両方
に含まれる一つ或は複数の故障をテスト不能な故障とし
て識別するステップを含むことを特徴とする方法。
【請求項２】順序論理回路に対するテストをそのモデ
ルに基づいて生成するための自動的方法であって、この
順序論理回路が複数の回路要素から構成され、これら回
路要素が一つ或は複数の回路リード及びこれら回路要素
の回路リードを相互接続する複数の回路線を持ち、これ
ら回路要素が少なくとも一つのフリップフロップを持
ち、前記の各回路リードが複数の時間フレームのおのお
のにおいてあらかじめ定められた複数の論理値の一つを
取る能力を持ち、この複数の時間フレームが一つの開始
時間フレームを含み、この方法が：前記の順序論理回路
の複数の回路リードの一つを選択するステップ；故障の
第一の集合を決定するステップ；及び故障の第二の集合
を決定するステップを含み；前記の故障の第一の集合が
前記の選択された回路リードがもし前記の開始時間フレ
ームにおいて前記のあらかじめ定められた複数の論理値
の第一の値をとることができないと仮定するならば、前
記の複数の時間フレームのある一つにおいて検出不能で
あると推定される複数の故障から構成され；前記の故障
の第二の集合が前記の選択された回路リードがもし前記
の開始時間フレームにおいて前記のあらかじめ定められ
た複数の論理値の第二の値をとることができないと仮定
するならば、前記の与えられた時間フレームにおいて検
出不能であると推定される複数の故障から構成され；こ
の方法がさらに前記の故障の第一の集合と前記の故障の
第二の集合の両方に含まれる一つ或は複数の故障をテス
ト不能な故障であると識別するステップ；及びテスト不
能な故障であると識別されなかった一つ或は複数の故障
に基づいてテストを発生するステップを含むことを特徴
とする方法。
【請求項３】製造された論理回路を自動的に生成され
たテストを使用してテストする方法であって、前記のテ
ストが前記の製造された論理回路のモデルに基づいて生
成され、前記のテストが一つの回路刺激と一つの対応す
る期待される回路応答から構成され、前記の論理回路が
複数の回路要素から構成され、これら回路要素が一つ或
は複数の回路リード及びこれら回路要素の回路リードを
相互接続する複数の回路線を持ち、これら回路要素が少
なくとも一つのフリップフロップを持ち、前記の各回路
リードが複数の時間フレームのおのおのにおいてあらか
じめ定められた複数の論理値の一つを取る能力を持ち、
この複数の時間フレームが一つの開始時間フレームを含
み、この方法が：前記の論理回路の複数の回路リードの
一つを選択するステップ；故障の第一の集合を決定する
ステップ；及び故障の第二の集合を決定するステップを
含み；前記の故障の第一の集合が前記の選択された回路
リードがもし前記の開始時間フレームにおいて前記のあ
らかじめ定められた複数の論理値の第一の値をとること
ができないと仮定するならば、前記の複数の時間フレー
ムのある一つにおいて検出不能であると推定される複数
の故障から構成され；前記の故障の第二の集合が前記の
選択された回路リードがもし前記の開始時間フレームに
おいて前記のあらかじめ定められた複数の論理値の第二
の値をとることができないと仮定するならば、前記の与
えられた時間フレームにおいて検出不能であると推定さ
れる複数の故障から構成され；この方法がさらに前記の
故障の第一の集合と前記の故障の第二の集合の両方に含
まれる一つ或は複数の故障をテスト不能な故障であると
識別するステップ；前記のテストをテスト不能な故障で
あると識別されなかった一つ或は複数の故障に基づいて
生成するステップ；前記の生成された回路刺激を製造さ
れた論理回路に加えるステップ；前記の製造された論理
回路からの回路応答を測定するステップ；及び前記の製
造された論理回路からの前記の回路応答が前記の生成さ
れた回路刺激に対応して生成されることが期待される回
路応答と異なるか否かを決定するステップを含むことを
特徴とする方法。
【請求項４】製造された論理回路を自動的に生成され
たテストを使用してテストする方法であって、前記のテ
ストが前記の製造された論理回路のモデルに基づいて生
成され、前記のテストが一つの回路刺激と一つの対応す
る期待される回路応答から構成され、前記の論理回路が
複数の回路要素から構成され、これら回路要素が一つ或
は複数の回路リード及びこれら回路要素の回路リードを
相互接続する複数の回路線を持ち、これら回路要素が少
なくとも一つのフリップフロップを持ち、前記の各回路
リードが複数の時間フレームのおのおのにおいてあらか
じめ定められた複数の論理値の一つを取る能力を持ち、
この複数の時間フレームが一つの開始時間フレームを含
み、このテストを生成する方法が：前記の論理回路の複
数の回路リードの一つを選択するステップ；故障の第一
の集合を決定するステップ；及び故障の第二の集合を決
定するステップを含み；前記の故障の第一の集合が前記
の選択された回路リードがもし前記の開始時間フレーム
において前記のあらかじめ定められた複数の論理値の第
一の値をとることができないと仮定するならば、前記の
複数の時間フレームのある一つにおいて検出不能である
と推定される複数の故障から構成され；前記の故障の第
二の集合が前記の選択された回路リードがもし前記の開
始時間フレームにおいて前記のあらかじめ定められた複
数の論理値の第二の値をとることができないと仮定する
ならば、前記の与えられた時間フレームにおいて検出不
能であると推定される複数の故障から構成され；このテ
ストを生成する方法がさらに前記の故障の第一の集合と
前記の故障の第二の集合の両方に含まれる一つ或は複数
の故障をテスト不能な故障であると識別するステップ；
及び前記のテストをテスト不能な故障であると識別され
なかった一つ或は複数の故障に基づいて生成するステッ
プを含み；この方法が前記の生成された回路刺激を製造
された論理回路に加えるステップ；前記の製造された論
理回路からの回路応答を測定するステップ；及び前記の
製造された論理回路からの前記の回路応答が前記の生成
された回路刺激に対応して生成されることが期待される
回路応答と異なるか否かを決定するステップを含むこと
を特徴とする方法。
【請求項５】順序論理回路設計を論理的冗長が削除さ
れるように修正するための方法であって、前記の順序論
理回路設計が複数の回路要素から構成される回路を表わ
し、前記の複数の回路要素が一つ或は複数の回路リード
及びこれら回路要素の回路リードを相互接続する複数の
回路線を持ち、前記の複数の回路要素が少なくとも一つ
のフリップフロップを持ち、前記の各回路リードが複数
の時間フレームのおのおのにおいてあらかじめ定められ
た複数の論理値の一つを取る能力を持ち、この複数の時
間フレームが一つの開始時間フレームを含み、この方法
が：前記の回路の複数の回路リードの一つを選択するス
テップ；故障の第一の集合を決定するステップ；及び故
障の第二の集合を決定するステップを含み；前記の故障
の第一の集合が前記の選択された回路リードがもし前記
の開始時間フレームにおいて前記のあらかじめ定められ
た複数の論理値の第一の値をとることができないと仮定
するならば、前記の複数の時間フレームのある一つにお
いて検出不能であると推定される複数の故障から構成さ
れ；前記の故障の第二の集合が前記の選択された回路リ
ードがもし前記の開始時間フレームにおいて前記のあら
かじめ定められた複数の論理値の第二の値をとることが
できないと仮定するならば、前記の与えられた時間フレ
ームにおいて検出不能であると推定される複数の故障か
ら構成され；この方法がさらに前記の故障の第一の集合
と前記の故障の第二の集合の両方に含まれる一つ或は複
数の故障をテスト不能な故障として識別するステップ；
前記の識別されたテスト不能な故障の一つを選択するス
テップ；及び前記の順序論理回路設計をその設計のある
選択された部分を削除することによって修正するステッ
プを含み、前記の選択された部分が前記の識別されたテ
スト不能な故障の選択された一つにも基づいて決定され
ることを特徴とする方法。
【請求項６】論理回路を初期論理回路設計に基づいて
製造するための方法であって、この初期論理回路設計が
複数の回路要素から構成される初期回路を表わし、前記
の複数の回路要素が一つ或は複数の回路リード及びこれ
ら回路要素の回路リードを相互接続する複数の回路線を
持ち、前記の複数の回路要素が少なくとも一つのフリッ
プフロップを持ち、前記の各回路リードが複数の時間フ
レームのおのおのにおいてあらかじめ定められた複数の
論理値の一つを取る能力を持ち、この複数の時間フレー
ムが一つの開始時間フレームを含み、この方法が：前記
の初期回路の複数の回路リードの一つを選択するステッ
プ；故障の第一の集合を決定するステップ；及び故障の
第二の集合を決定するステップを含み；前記の故障の第
一の集合が前記の選択された回路リードがもし前記の開
始時間フレームにおいて前記のあらかじめ定められた複
数の論理値の第一の値をとることができないと仮定する
ならば、前記の複数の時間フレームのある一つにおいて
検出不能であると推定される複数の故障から構成され；
前記の故障の第二の集合が前記の選択された回路リード
がもし前記の開始時間フレームにおいて前記のあらかじ
め定められた複数の論理値の第二の値をとることができ
ないと仮定するならば、前記の与えられた時間フレーム
において検出不能であると推定される複数の故障から構
成され；この方法がさらに前記の故障の第一の集合と前
記の故障の第二の集合の両方に含まれる一つ或は複数の
故障をテスト不能な故障として識別するステップ；前記
の識別されたテスト不能な故障の一つを選択するステッ
プ；及び前記の初期論理回路設計を、修正された回路設
計を製造するために、前記の初期論理回路設計のある選
択された部分を削除することによって修正するステップ
を含み、前記の選択された部分が前記の識別されたテス
ト不能な故障の選択された一つにも基づいて決定され；
この方法がさらに前記の論理回路を前記の修正された回
路設計に基づいて製造するステップを含むことを特徴と
する方法。
【請求項７】前記の選択されたリードが再収束ファン
アウトを持つ回路線の茎から成ることを特徴とする請求
項１、２、３、４、５或は６の方法。
【請求項８】前記の選択された回路リードが再収束回
路要素の再収束入力から成ることを特徴とする請求項
１、２、３、４、５或は６の方法。
【請求項９】前記の第一の論理値に対応する前記の故
障の第一の集合を決定するステップ、及び前記の第二の
論理値に対応する前記の故障の第二の集合を決定するス
テップが、それぞれ、一つの順序インプリケーション
（含意）手続きを含み、このインプリケーション手続き
が：前記の選択された回路リードに前記の開始時間フレ
ームにおいて初期制御不能指標を割り当てるステップを
含み、この初期制御不能指標が前記の選択された回路リ
ードが前記の開始時間フレームにおいて前記の第一の論
理値及び前記の第二の論理値の対応する値を取ることが
できないことを仮定し；このインプリケーション手続き
がさらに制御不能標識を選択された回路リードに関連す
る時間フレームにおいて、前記の初期制御不能指標をあ
るあらかじめ定められた制御不能標識伝播規則の集合に
従って前記の論理回路のモデルを通じて伝播することに
よって割り当てるステップを含み、この制御不能指標が
前記の選択された回路リードが前記の複数の関連する時
間フレームの対応する一つにおいて前記の論理値の識別
される一つを取ることができないことを仮定し；このイ
ンプリケーション手続きがさらに初期観察不能指標を選
択された回路リードに関連する時間フレームにおいて前
記の割り当てられた制御不能標識及びそれと関連する前
記の時間フレームに基づいて割り当てるステップを含
み、この観察不能指標が前記の選択された回路リードに
よって取られる値が前記の複数の関連する時間フレーム
の対応する一つにおいて観察できないことを仮定し；こ
のインプリケーション手続きがさらに追加の観察不能指
標を選択された回路リードに関連する時間フレームにお
いて、初期観察不能指標をあらかじめ定められた観察不
能標識伝播規則の集合に従って前記の論理回路の前記の
モデルを通じて後ろ方向に伝播することによって指定す
るステップを含み、前記の観察不能指標が前記の選択さ
れた回路リードによって取られる値が前記の複数の関連
する時間フレームの対応する一つにおいて観察できない
ことを仮定し；このインプリケーション手続きがさらに
前記の複数の時間フレームの一つを選択するステップ；
及び前記の故障の集合を前記の選択された時間フレーム
及びそれらの対応する回路リードと関連する前記の制御
不能指標及び前記の制御不能指標に基づいて決定するス
テップを含むことを特徴とする請求項１、２、３、４、
５、或は６の方法。