JPH0894720A - 論理回路における試験不能欠陥を特定する方法 - Google Patents

Abstract

(57)【要約】 【課題】 論理回路における試験不能欠陥を特定する方
法の提供。 【解決手段】 論理回路の導線の１つが選択され、もし
選択された回路導線が論理値０を取ることができないと
した場合にどの欠陥が仮定的に試験不能か及びもし選択
された回路導線が論理値１を取ることができないとした
場合にどの欠陥が仮定的に試験不能かを定めるため回路
が解析される。両事例で試験不能な欠陥が試験不能欠陥
と特定される。もし選択された回路導線が特定値を取る
ことができないとした場合に仮定的に試験不能であるよ
うな欠陥が含意手順に基づいて特定される。順序論理回
路における試験不能欠陥が、固定数の時間フレ−ムにつ
いて、同等な組合せ反復アレイ回路モデルを生成するこ
とにより特定される。両事例において試験不能であり且
つ最後の時間フレ−ムに位置するような順序論理回路に
おける欠陥が本来の順序論理回路の試験不能欠陥として
特定される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は概して、ディジタル
論理回路に対する「試験の自動生成」（自動試験生成）
（ＡＴＧ）の分野に関し、詳しくは、このような回路に
おける試験不能な欠陥（試験不能欠陥）の識別同定（特
定）に関する。

【０００２】

【従来の技術】ディジタル論理回路を十分に試験すると
いう問題は、設計製造されるディジタル論理回路の複雑
性が急速に増大するにつれて、何年もの間に相当に、よ
り一層複雑なものになって来ている。この問題に対する
最も現代的な対処方法においては、与えられた回路設計
に対する「包括的な試験計画」（以下、試験と称する）
を自動的に生成する業務（タスク）を受け持つ「自動試
験生成（ＡＴＧ）システム」が用いられる。

【０００３】この自動試験生成システムに、上記回路設
計についての記述が与えられる。この記述は一般に、回
路を構成する回路素子（例えば論理ゲート）、これらの
素子間の相互接続、並びに回路の主入力への相互接続及
び主出力への相互接続に関して行われる。回路設計の記
述が与えられると、自動試験生成システムは回路への刺
激（回路刺激）を自動的に生成する。

【０００４】この回路刺激が、与えられた回路設計に基
づいて製造された回路の主入力に供給されると、その結
果として回路の主出力に回路からの応答（回路応答）が
出力され、この応答によって、この与えられた回路がこ
の与えられた回路設計に合致して作動しているかどうか
が、妥当な確実度をもって識別される。

【０００５】製造された回路が理論的に示す、可能性あ
る誤動作の数は極めて大きいので、自動試験生成システ
ムにおいては一般に、可能性ある誤動作の数が比較的小
さい場合だけを考えた欠陥モデルに基づいて、そのタス
クの実行及びその結果の品質の測定を行う。

【０００６】このようなモデルで最も一般的なものであ
る「固執」（stuck-at）欠陥モデルは、各回路導線（す
なわち、回路素子への各入力及び回路素子からの各出力
が個別に、可能性ある値（例えば論理値０または論理値
１）のうちの１つに固執するようにした誤動作の集合
（セット）を列挙する。このようにして、可能性ある欠
陥として考慮される欠陥の数は、回路導線の数の２倍に
限定される。

【０００７】「固執」欠陥モデルは、一般に製造プロセ
スから起因する有りそうな物理的エラーセットに対して
妥当な対応が得られることがよく認められている。

【０００８】大抵の自動試験生成システムは、モデル化
された欠陥のうちから１度に１個の欠陥を選択し、その
欠陥を検出できるような試験（すなわち回路刺激）を生
成しようと意図する。すなわち、システムの目標は、回
路刺激が欠陥回路（与えられた欠陥を有する回路）の主
入力に供給された場合に、適切に作動する回路の応答と
異なる応答がその欠陥回路の主出力に発生するような回
路刺激、を見出すことである。

【０００９】通常、これらの回路刺激の生成には、かな
りの試行錯誤を伴う消耗的な探索手順の実行を必要とす
る。しかし、最も一般的な回路設計については、多くの
欠陥は、もし製造された回路に実際に存在したとして
も、回路挙動に識別可能な変化をもたらすものでは全く
ない。したがって、これらの欠陥は検出不能すなわち試
験不能である（実際には、これらの欠陥は通常、回路設
計における本来の論理冗長を反映するものである）。

【００１０】

【発明が解決しようとする課題】その結果として、試験
不能欠陥を特定するなんらかの手段を持たない大抵の自
動試験生成システムは、点検対象の探索空間全部を消耗
的に探索し尽くした後に初めてこれらの欠陥を試験不能
欠陥として識別同定（特定）することになる。したがっ
て、自動試験生成システムの時間の、殆ど全てでないに
しても大きな部分が、試験不能欠陥についての試験を生
成するという無駄な試みに費やされることになる。

【００１１】試験不能ないくつかの欠陥を除去する手法
は従来も用いられて来ているが、これらの従来手法にお
いては一般に、全ての試験不能欠陥のうちの小部分しか
除去されない。詳しくは、与えられた論理値に設定でき
ない（すなわちその値に制御することが不能である）又
は回路の主出力において値を観測できないような（観測
不能）回路導線を特定するために、回路導線の「制御可
能性」及び「観測可能性」の通常解析が行われる。この
ような解析の結果として、限定された数の試験不能欠陥
の特定が可能である。

【００１２】しかし、膨大な大多数の試験不能欠陥を特
定することはそのように簡単ではない。大抵の試験不能
欠陥は、回路において全ての関連回路導線が個別に両方
の論理値に制御可能であり、又回路の主出力において観
測可能であるような、より複雑な回路冗長、に由来する
ものである。したがって、これら大多数の試験不能欠陥
を特定する方法が求められている。

【００１３】

【課題を解決するための手段】本発明に基づいて、論理
回路における試験不能欠陥を識別同定（特定）する方法
が提供される。具体的には、論理回路（以下単に、回路
とも記す）の導線の１つが選択されて、次にもし選択さ
れた回路導線が第１の論理値（例えば論理値０）を取る
ことができないとした場合にどの欠陥が仮定的に（仮定
として）試験不能であるか、及びもし選択された回路導
線が第２の論理値（例えば論理値１）を取ることができ
ないとした場合に、どの欠陥が仮定的に試験不能である
かを定めるために、この回路が解析される。

【００１４】それから、これら両方の仮定事例において
試験不能であるような欠陥が、試験不能欠陥として特定
される。

【００１５】選択された回路導線は例えば、回路内の回
線（回路線）の幹部（ステム）（例、ファン・アウト
点）、又は再収束回路素子（例、ゲート）の再収束入力
部である。本発明の方法の有利な点として、与えられた
論理回路についての試験不能欠陥の、全てではないにし
ても、大部分を特定するために、本発明の方法が、この
ような回路線幹部の各々及び再収束ゲートのこのような
再収束入力の各々について反復される。

【００１６】本発明の一実施例によれば、もし選択され
た回路導線が第１及び第２の論理値のうちの与えられた
値を取ることができないとした場合に仮定的に試験不能
であるような欠陥が含意手順に基づいて特定される。こ
の含意手順は、前方への制御不能表示子の伝播と、後方
への観測不能表示子の伝播とからなる。

【００１７】詳しくは、与えられた（第１または第２
の）値に設定できない（制御不能）という状態を示す制
御不能表示子が、選択された回路導線に割り当てられ、
よく定義された伝播ルールのセットに基づいて、この回
路を通して前方へ伝播される。これに加えて、制御不能
表示子に基づいて回路導線に観測不能の状態を示す観測
不能表示子が生成され、それからこれらの観測不能表示
子が、同じく、よく定義された伝播ルールのセットに基
づいて、この回路を通して後方へ伝播される。

【００１８】そして、上記処理によって得られた制御不
能表示子と観測不能表示子とこれらの表示子に対応する
回路導線とに基づいて、仮定的に試験不能な欠陥が定め
られる。

【００１９】本発明の別の実施例によれば、順序（シー
ケンス）論理回路（組合せ論理回路に対向して）におけ
る試験不能欠陥が、予め定められた数の時間フレ−ムに
ついて組合せ反復アレイ回路モデルを順序論理回路から
生成することによって特定される。

【００２０】本発明の方法は、組合せ反復アレイ回路モ
デルにも適用可能である。両方の仮定事例において試験
不能である組合せ反復アレイ回路モデルにおける欠陥に
対応し、且つ最後（すなわち時間的に最も後）の時間フ
レ−ムに位置するような、順序論理回路における欠陥、
が本来の順序論理回路の試験不能欠陥として特定され
る。

【００２１】

【発明の実施の形態】図１は、本発明の方法の一実施例
によって生成された試験を用いて論理回路を試験するプ
ロセスの例を示す。詳しくは、試験生成装置１１が入力
刺激と、これに対応する出力応答とを試験対象の回路の
回路記述に基づいて生成する。具体的には、試験生成装
置１１が、例えば図３に示すような本発明の方法の一実
施例に基づいて作動する。試験生成装置１１は例えば、
汎用コンピュータシステムとこのシステム上で動くソフ
トウエアとからなる。

【００２２】符号１２は製造された論理回路例（製造済
回路）を表し各々、複数の相互接続された回路素子１３
（例えばゲ−ト）と、１個以上の主入力１４と、１個以
上の主出力１５とからなる。

【００２３】与えられた製造済回路１２が試験される場
合、試験生成装置１１によって生成された入力刺激が製
造済回路１２の主出力に供給され、結果として得られた
出力応答が主出力１５において測定される。結果として
得られた出力応答は比較回路１６によって、試験生成装
置において生成された期待出力応答と比較され、これに
よって製造済回路１２の欠陥が特定される。

【００２４】ここに述べる試験プロセスは、総括的に自
動試験装置（ＡＴＥ）として知られているコンピュータ
制御されたシステム（以下、自動試験システム）によっ
て行われるのが最も普通である。一般的な自動試験シス
テムは例えば、制御コンピュータに加えて、一連のハー
ドウエア構成要素からなり、これらの構成要素は、製造
済回路へ刺激を供給し、この製造済回路からの応答を測
定し、この測定された応答を予め定められた期待応答と
比較するといういくつもの動作を行うように適応されて
いる。

【００２５】試験される製造済回路は通常、標準化され
たインタフェ−スを用いて自動試験システムにさし込ま
れる（プラグイン）。

【００２６】図２は、本発明の方法の一実施例が有利に
適用される組合せ論理回路の例を示す。この回路例は、
ＡＮＤ（論理積）ゲ−ト２１、２２、及び２３と、ＯＲ
（論理和）ゲ−ト２４とからなり、これらのゲ−トは、
互いに、又主入力ａ、ｂ、及びｃ、並びに主出力ｇにそ
れぞれ相互接続されている。ここで値「０」に固執する
「固執」欠陥ｆを想定する。すなわち、ＯＲゲ−ト２４
への第１の入力導線が論理値０に常時固定される。

【００２７】（ここで注記したいのは、このような、回
路線がファン・アウトを含まない事例においては、駆動
側ゲ−トの出力導線における「固執」欠陥と、受け側ゲ
−トの入力導線におけるこれに対応する「固執」欠陥と
の間には意味のある区別は存在しないということであ
る。）

【００２８】与えられた回路導線において「固執」欠陥
（例えば論理値０に固執）を検出（すなわち試験）する
ためには、欠陥回路と適切に作動する回路との間の値の
差（例えば０対１）を生成するようにこの与えられた回
路導線を起動させることが必要であり、更には、結果と
して得られた値の差を、この差を試験プロセスが観測で
きる箇所である回路主出力へ「伝播」させることが必要
である。

【００２９】与えられた回路導線において「固執」欠陥
を起動させるために必要なのは、この回路導線を「固
執」値と反対の論理値に設定することだけである。例え
ば、「０に固執」の欠陥を検出するには、回路導線を論
理値１に設定することが必要である。

【００３０】欠陥を伝播させるには与えられた回路導線
から主出力への回線路（パス）を感知可能化する必要が
ある。すなわち、このようなパスに沿った各ゲ−トが、
この与えられたパス上の論理値に対して感知可能状態に
ならなければならない。このことは、これらのゲ−トの
他の入力の全てにおける値を適切な値に設定することに
よって達成できる（例えば、ＮＡＮＤ（否定論理積）又
はＡＮＤ（論理積）のいずれかのゲ−トの入力からその
出力へのパスを感知可能化するには、他の入力全てを論
理値１に設定する必要がある）。

【００３１】したがって、「０に固執」の欠陥ｆを検出
するにはまず、回路導線ｃ及びｄを論理値１に設定する
ことが必要であり、又、含意により、回路導線ａ及びｂ
の両方を論理値１に設定することが必要である。しか
し、「０に固執」の欠陥の効果をｆから主出力に伝播さ
せるには、回路導線ｅを論理値０に設定しなければなら
ない（その理由は、回路導線ｅが論理値０である場合に
だけ、ＯＲゲ−ト２４が感知可能化されて導線ｆ上の論
理値を主出力ｇへ伝播させることができるようになるか
らである）。

【００３２】又、含意によって、回路導線ａ及びｂのう
ちの少なくとも１個が論理値０に設定される必要があ
る。この矛盾（すなわち、回路導線ａ及びｂの両方が論
理値１に設定されなければならないことと、回路導線ａ
及びｂのうちの少なくとも１個が論理値０に設定されな
ければならないこととの矛盾）は、「０に固執」の欠陥
ｆが必然的に試験不能であることを示している。別言す
れば、「０に固執」の欠陥ｆを検出するには回路導線ａ
又はｂのうちの１個が同時に論理値０且つ論理値１であ
ることが必要となる。

【００３３】上記の解析は、自動試験生成システムによ
って一般に行われる手順に類似の手順から構成されてい
た。「０に固執」の欠陥ｆについての試験を生成しよう
と意図することにより、解決できない矛盾が生じた。

【００３４】より一般的な（すなわち、より複雑な）回
路においては、これらの矛盾が生じることがしばしばあ
るが、これらの矛盾が、無作意な決定（すなわち、選
択）がなされた点まで遡及してその点において代わりの
決定を行うことによって解決されることもしばしばある
（例えば、或るＮＡＮＤゲ−トの入力のどれかを論理値
０に設定することにより、このゲ−トの出力が論理値１
に設定される）。

【００３５】図２の回路例における「０に固執」の欠陥
ｆについての上記の解析事例において、代わりの仕方で
なし得るような選択が存在しなかったので、遡及が不可
能であった。

【００３６】図３は、図２の回路例のような組合せ論理
回路に用いた本発明の方法の一実施例を説明する流れ図
である。例示の手順は、回路内の複数の回路導線の各々
を交替に反復して選択する。手順はステップ３１におい
て、解析のためにこのような（前に選択されなかった）
回路導線の１個を選択することで始まる。

【００３７】選択される導線は、回路内の回路導線の各
々を全て交替に選択するのではなく、再収束ファン・ア
ウト（すなわち、パスに沿って進むファン・アウト支線
を有するゲ−トの出力で、最終的に別のゲ−トの入力と
して再収束する出力）を有する回路導線幹部と、再収束
ゲ−トの再収束入力とに限定されるので有利である。こ
の利点は、試験不能欠陥をもたらす矛盾が再収束ファン
・アウト構造だけに起因するという事実から得られる。

【００３８】本発明の方法の一実施例においては、選択
された回路導線は回路線幹部だけに限定される。回路導
線の選択をこのように限定することにより、本発明の手
法が、与えられた回路における試験不能欠陥の或るもの
については特定できないことが有り得る。それにも拘ら
ず、このような限定された手法において、再収束入力の
解析を含めることにより一般に、試験不能欠陥の大部分
が特定され、一方、回路線幹部だけを解析することによ
り計算時間が顕著にな削減される。

【００３９】与えられた回路の導線が選択されると、図
３の例示手順のステップ３２において、その回路導線が
論理値０に（仮定的に）制御不能（すなわち、回路の主
入力に供給される値に無関係に、論理値０を取ることが
できない）としてマーク付けされる。

【００４０】それからステップ３３において含意手順が
適用され、これにより、他の回路ノードが或る適切な論
理値に制御不能であること、又は当初仮定された制御不
能の状態から含意によって適切であるとして観測不能
（すなわち、その値を主出力へ伝播できない）であるこ
と、をマーク付けされる。得られた制御不能表示子及び
観測不能表示子に基づいて、仮定的に試験不能な欠陥の
第１セットが導出される（下で図４に示す含意ルールの
説明及び下の図５の含意手順の説明を参照）。

【００４１】次に、ステップ３４において、選択された
回路導線が、論理値１に（仮定的に）制御不能（すなわ
ち、論理値１を取ることができない）としてマーク付け
される。それから、ステップ３５において、含意手順が
再び適用され、これにより他の回路ノードが或る適切な
論理値に制御不能であること、又は当初仮定された制御
不能状態から含意によって適切であるとして観測不能で
あること、をマーク付けされる。

【００４２】このようにして得られた制御不能表示子及
び観測不能表示子のセットに基づいて、仮定的に試験不
能な欠陥の第２セットが導出される。

【００４３】このようにして、２セットの仮定的に試験
不能な欠陥が導出された。すなわち、その第１のセット
は、その欠陥が各々、もし選択された回路導線が論理値
０に制御不能であるとした場合に試験不能であるような
欠陥のセットであり、その第２のセットは、その欠陥が
各々、もし選択された回路導線が論理値１に制御不能で
あるとした場合に試験不能であるような欠陥のセットで
ある。

【００４４】与えられたどの時点においても、選択され
た回路導線は可能な２個の論理値のうちの１個だけを取
るので、両方の欠陥セットに現れる欠陥は、必然的に試
験不能である。したがって、ステップ３６において、両
方の欠陥セットに現れる欠陥によって、選択された回路
導線の解析に基づいて導出される試験不能欠陥が特定さ
れる。

【００４５】それから、決定ステップ３７において、選
択すべき回路導線が更にあるかどうか（すなわち、再収
束ファン・アウトを有する回路線幹部の全て及び再収束
ゲ−トの再収束入力の全てが解析され終ったかどうか）
が判断され、もし解析すべき回路導線が更にある場合に
は、上記の手順が反復される。

【００４６】もし解析すべき回路導線が更にない場合に
はステップ３８において、ステップ３１からステップ３
７までの手順によって試験不能として識別特定された欠
陥を明白に除いて、この回路についての自動試験生成プ
ロセスが実行される。上記したように、ステップ３８の
自動試験生成プロセスにおいては、試験刺激と期待出力
応答とが生成される。

【００４７】図４は、制御不能表示子の、前方への伝
播、及び観測不能表示子の、後方への伝播についてのル
ールの例を示す。これらのルールは、図３の手順におい
て用いられる含意手順が使用するもので、含意手順につ
いては図５において更に詳しく述べる。ゲ−ト４１、４
２、及び４３、並びに回路線ファン・アウト点４４が制
御不能表示子の、前方への伝播についてのルールを例示
し、ゲ−ト４５、４６、及び４７が観測不能表示子の、
後方への伝播についてのルールを例示する。

【００４８】ここで約束として、図４中、０の上に横線
（オーバライン）を引いた記号によって、論理値０に
（仮定的に）制御不能な回路導線状態を示すこととする
（本文中では「上線０」と表す）。同様に、１の上に横
線（オーバライン）を引いた記号によって、論理値１に
（仮定的に）制御不能な回路導線状態を示すこととする
（本文中では「上線１」と表す）。更に、記号＊によっ
て、（仮定的に）観測不能な回路導線状態を示すことと
する。

【００４９】例えば、インバータ・ゲ−ト４１では、イ
ンバータ・ゲ−トの入力が「上線０」とマーク付けされ
ている場合、その出力は「上線１」となる。同様に、イ
ンバータ・ゲ−トの入力が「上線１」とマーク付けされ
ている場合、その出力は「上線０」となる。これらのル
ールは、もしインバータ・ゲ−トの入力が或る与えられ
た値に設定できない場合にはその出力は他方の値に設定
できないという明白な事実に基づいている。

【００５０】ＮＡＮＤ（否定論理積）ゲ−ト４２におい
ては、ＮＡＮＤゲ−トの入力の全てが「上線０」とマー
ク付けされている場合、その出力は「上線１」となるこ
とを示す。その理由は、もしＮＡＮＤゲ−トの入力のい
ずれも論理値０に設定できない場合、その出力を論理値
１に設定することはできないからである。

【００５１】ＮＡＮＤゲ−ト４３においては、ＮＡＮＤ
ゲ−トの入力のどれかが「上線１」とマーク付けされて
いる場合、その出力は「上線０」となることを示す。そ
の理由は、もしＮＡＮＤゲ−トの入力のどれかが論理値
１に設定できない場合、その出力を論理値０に設定する
ことはできないからである。

【００５２】そして、ファン・アウト点４４において
は、回路線幹部が「上線０」とマーク付けされている場
合、そのファン・アウト支線の各々が「上線０」とマー
ク付けされることを示す。同様に、回路線幹部が「上線
１」とマーク付けされている場合、そのファン・アウト
支線の各々が「上線１」とマーク付けされることを示
す。その理由は、ファン・アウト支線は、その設定用に
与えられた値と同じ値にその支線に対応する幹部を設定
することによってのみ、その値に設定することが可能だ
からである。

【００５３】他のゲート形式又は回路素子に適用される
制御不能表示子の、前方への伝播についての同様なルー
ルも、この技術分野の当業者には明白である。

【００５４】インバータ・ゲート４５は、インバータ・
ゲ−トの出力が＊とマーク付けされている場合、その入
力も＊とマーク付けされることを示す。ＮＡＮＤゲ−ト
４６においては、ＮＡＮＤゲ−トの出力が＊とマーク付
けされている場合、その入力の各々が＊とマーク付けさ
れることを示す。これらのルールは、もしどれかのゲー
トの出力が観測できない場合にはその入力がどれも観測
できないという事実に基づいている。

【００５５】そしてＮＡＮＤゲート４７は、その入力の
うちの１つが「上線１」とマーク付けされている場合、
そのゲートの他の入力の各々が＊とマーク付けされるこ
とを示す。その理由は、ＮＡＮＤゲートへの入力が、そ
の他の入力の全てを論理値１に設定することによっての
み、観測可能となるためである。

【００５６】他のゲート形式又は回路素子に適用される
観測不能表示子の、後方への伝播についての同様なルー
ルも、この技術分野の当業者には明白である（しかし、
或る場合には、たとえ回路のファン・アウト支線の全て
が観測可能でなくても、回路線幹部が観測可能であるこ
とに留意したい）。

【００５７】図５は、図３の例示手順ののステップ３３
及びステップ３５において用いられる含意手順の例を示
す流れ図である。具体的には、図５の手順が、もし与え
られた、選択された回路導線が或る指定された値に制御
不能であるとした場合に（仮定的に）試験不能であるよ
うな欠陥セットを定める。この例示手順は例えば、図４
に図示し上に述べたような伝播ルールを用いる。

【００５８】ステップ５１において、選択された回路導
線に初期の制御不能表示子が割り当てられる。この制御
不能表示子は、選択された回路導線に対し、手順が図３
の流れ図のステップ３３又はステップ３５のうちのどち
らを実行するのに用いられるかに依って、指定された論
理値（０又は１）に制御不能であるとしてマーク付けを
行う。

【００５９】次にステップ５２において、予め定められ
た制御不能表示子伝播ルール（図４のゲ−ト４１、４
２、及び４３並びに回路線ファン・アウト点４４につい
て示したルールのような）を用いて、制御不能表示子が
回路を通して前方へ伝播される。ステップ５３におい
て、予め定められた観測不能表示子生成ルール（図４の
ゲ−ト４７について示したルールのような）を用いて、
初期の観測不能表示子が、適切な回路導線に割り当てら
れる。

【００６０】それからステップ５４において、予め定め
られた観測不能表示子伝播ルール（図４のゲ−ト４５、
及び４６について示したルールのような）を用いて、観
測不能表示子が回路を通して後方へ伝播される。

【００６１】この時点において、（予め定められたルー
ルセットに基づいて）初期の制御不能状態の仮定から制
御不能及び／又は観測不能として含意することの可能な
回路導線は全て、そのようにマーク付けされ終ってい
る。したがって、種々の回路導線に現れているマークか
ら結果として得られる仮定的に試験不能な欠陥の導出だ
けが残っている。

【００６２】詳しくは、これらの欠陥は、起動不可能な
欠陥及び伝播不可能な欠陥である。（仮定的に）起動不
可能な欠陥は、論理値１に制御不能としてマーク付けさ
れた導線上の「０に固執」の欠陥、及び論理値０に制御
不能としてマーク付けされた導線上の「１に固執」の欠
陥である。（仮定的に）伝播不可能な欠陥は、観測不能
としてマーク付けされた導線上の「０に固執」の欠陥及
び「１に固執」の欠陥の両方である。

【００６３】したがって、図５の手順のステップ５５に
おいて、制御不能表示子をマーク付けされた各回路導線
が選択される。そして、そのマーク付けされた、制御不
能状態における制御不能な値（決定ステップ５６によっ
て定められた値）に依って、回路導線上の「１に固執」
の欠陥（ステップ５７）又は回路導線上の「０に固執」
の欠陥（ステップ５８）のどちらかが、仮定的に試験不
能な欠陥のセットに追加される。

【００６４】処理すべき制御不能表示子がまだある間、
すなわち制御不能表示子の各々が処理され終るまで、決
定ステップ５９から手順はステップ５５に戻り、別の回
路導線が選択され、上記の処理が反復される。

【００６５】同様に、ステップ６１において、観測不能
表示子をマーク付けされた各回路導線が選択される。ス
テップ６２において、回路導線上の「０に固執」の欠陥
及び回路導線上の「１に固執」の欠陥の両方が、仮定的
に試験不能な欠陥のセットに追加される。

【００６６】処理すべき観測不能表示子がまだある間、
すなわち観測不能表示子の各々が処理され終るまで、決
定ステップ６３から手順はステップ６１に戻り、別の回
路導線が選択され、上記の処理が反復される。

【００６７】図６は、本発明の方法の一実施例が適用さ
れる順序論理回路の組合せ反復アレイ回路モデルの例を
示す。従来の組合せ反復アレイモデルを用いることによ
って、順序回路がこれと「同等」の組合せ回路に変換さ
れることは、この技術分野の当業者に周知である。

【００６８】組合せ反復アレイは、順序回路を、各々が
同一の組合せ回路（すなわち、本来の順序回路の組合せ
の部分）であるような（仮定的に）無限の数のブロッ
ク、に拡張することによって得られる。各ブロックは、
異なる時点におけるその回路の状態を表す。すなわち、
各ブロックは、各々が時間的にその前の１個の時間フレ
−ムに続くような、別個の時間フレ−ムを表す。

【００６９】順序回路の実際的な試験に含まれる入力刺
激は有限でなければならない（したがって、時間フレ−
ムの数が有限となる）ので、組合せ反復アレイ回路モデ
ルは、固定（すなわち有限）数のフレ−ムに限定され
る。

【００７０】図６は、例として、１個の順序論理回路を
５個の（同一の）組合せ論理回路ブロック６５、６６、
６７、６８、及び６９に拡張する場合を示す。各ブロッ
ク（時間フレ−ム）への主入力を対応するブロックの上
方に、又各ブロックからの主出力を対応するブロックの
下方にそれぞれ示す。各ブロックの左側の入力は、現在
の状態変数（対応する時間フレ−ムに対する）を表し、
各ブロックの右側の出力は、次の状態変数（次の時間フ
レ−ムによって現在の状態変数として用いられる）に対
応する。

【００７１】最も左側（時間的に最も前）のブロック
（すなわち図６のブロック６５）の状態変数入力は、
「完全に制御可能」と考えられている（各時間フレ−ム
の主入力も同様）。又、最も右側（時間的に最も後）の
ブロック（すなわち図６のブロック６９）の状態変数出
力は、「完全に観測可能」と考えられている（各時間フ
レ−ムの主出力も同様）。

【００７２】順序回路の（有限）組合せ反復アレイ回路
モデルの最も右側のブロック内の「固執」欠陥であって
試験不能である欠陥は、本来の順序回路においても試験
不能であることが、この技術分野の当業者に知られてい
る（例えば文献（V.D. Agrawal and S.T. Chakradhar,
"Combinational ATPG Theorems for Identifying Unte
stable Faults in Sequential Circuits," Proc. Europ
ean Test Conf., pp.249-253, April 1993） を参照さ
れたい）。

【００７３】したがって本発明の方法の一実施例によれ
ば、順序回路における試験不能欠陥は、まずその順序回
路を、予め定められた数の時間フレ−ムからなる同等の
組合せ反復アレイ回路モデルに変換することによって、
そして次に、結果として得られた組合せ反復アレイ回路
上の試験不能欠陥を特定するために上記手順（例えば図
３の手順）を行うことによって特定される。

【００７４】しかし、組合せ反復アレイ回路のモデル時
間的に最も後の時間フレ−ムにおける欠陥だけが、試験
不能として特定される。それで、これらの特定された欠
陥（すなわち、対応する回路導線上の対応する「固執」
欠陥）が、本来の順序回路における試験不能欠陥として
特定される。

【００７５】図７は、順序論理回路に用いた本発明の方
法の一実施例を説明する流れ図を示す。まず、ステップ
７１において、与えられた順序回路が、予め定められた
数の時間フレ−ムを有する組合せ反復アレイ回路モデル
に、従来の手法を用いて変換される。この予め定められ
た時間フレ−ムの数は定数（例えば５）に固定するが、
別の実施例のように、新たな試験不能欠陥が見出された
とき又は予め定められた最大値（例えば５）に達するま
で徐々に増大するようにもできる。

【００７６】こうして生成された組合せ反復アレイ回路
モデルが与えられると、ステップ７２において、回路導
線（前に選択されていないもの）が選択される。この回
路導線は、組合せ反復アレイ回路モデルの時間フレ−ム
のうちのどの時間フレ−ムに位置してもよい（異なる時
間フレ−ム内の回路導線は異なる回路導線として扱われ
る。すなわち、これら異なる導線の各々が交替に選択さ
れる）。

【００７７】ステップ７３において、もし選択された回
路導線が論理値１に制御不能であるとした場合に（仮定
的に）試験不能であるような組合せ反復アレイ回路モデ
ルの第１の欠陥セットが定められる。又ステップ７４に
おいて、もし選択された回路導線が論理値０に制御不能
であるとした場合に（仮定的に）試験不能であるような
組合せ反復アレイ回路モデルの第２の欠陥セットが定め
られる。

【００７８】それからステップ７５において、これら第
１及び第２の仮定的に制御不能な欠陥セットの両方に含
まれ、且つ組合せ反復アレイ回路モデルの時間的に最も
後の時間フレ−ムに位置する欠陥（に対応する順序回路
内の欠陥）が、試験不能欠陥として特定される。

【００７９】決定ステップ７６において、選択すべき回
路導線がまだあるかどうかが定められ、最後にステップ
７７において、本手順のステップ７１からステップ７６
までによって試験不能であるとして特定された欠陥を明
白に除外して、本来の順序回路について自動試験生成プ
ロセスが行われる。

【００８０】図８は、組合せ論理回路から冗長が除去さ
れた本発明の方法の付加的実施例を説明する流れ図を示
す。具体的には、組合せ回路内に試験不能欠陥がある場
合、これが回路設計における論理冗長の存在を含意する
ことがこの技術分野の当業者には周知である。すなわ
ち、組合せ回路内で試験不能欠陥を特定することによ
り、回路内のこれに対応する部分を、回路の論理挙動に
影響することなく回路から除去することが可能である。

【００８１】したがって、本発明の方法の一実施例によ
れば、試験不能欠陥を反復して特定しそれに基づいて回
路設計を節減することにより、組合せ回路が簡素化され
る。結果として得られる回路は、本来の回路に比して小
さくなるが論理的には同等である（試験不能欠陥に基づ
いて回路の一部分を除去することが回路内の他の欠陥の
試験可能性に影響を与え得るという事実から、上記のよ
うな回路節減が、１度に１個の特定された試験不能欠陥
に基づいて行われるので有利であることを注記した
い）。

【００８２】図８に例示する冗長除去手順においては、
（１度に）１個の試験不能欠陥を特定し、その欠陥の試
験不能性によって含意される回路内の冗長部分を除去
し、もはや試験不能欠陥が特定されなくなるまで以上の
プロセスを反復する。具体的には、ステップ８１におい
て、まず与えられた（現）状態版（バージョン）の回路
から初めの回路導線が解析のために選択され、これによ
って冗長除去手順のうちの与えられた反復プロセスが開
始される。

【００８３】ステップ８２において、選択された回路導
線が例えば論理値０に制御不能であるとの仮定に基づ
き、仮定的に試験不能な欠陥の第１のセットが定められ
る。同様に、ステップ８３において、選択された回路導
線が例えば論理値１に制御不能であるとの仮定に基づ
き、仮定的に試験不能な欠陥の第２のセットが定められ
る。それからステップ８４において、これらの仮定的に
試験不能な欠陥の両方のセットに含まれる欠陥が試験不
能として特定される。

【００８４】決定ステップ８５において、ステップ８４
において試験不能として特定された欠陥があったかどう
かが判断され、もしあった場合にはステップ８６におい
て、試験不能と特定されたこれら欠陥のうちの１個が選
択される。それからステップ８７において、選択された
欠陥の試験不能性に基づいて冗長と判断し得る回路部分
が除去される。

【００８５】例えば、もし与えられた回路導線上の「０
に固執」の欠陥が試験不能欠陥である場合、与えられた
回路導線に流入する全ての回線が（除去されない他の回
路導線にその回線が流入しない範囲で）除去され、与え
られた回路導線が、論理値０に固定される（例えば接地
される）。

【００８６】ステップ８６における試験不能欠陥の選択
は任意に行ってよいが、この選択に基づいてステップ８
７において除去される回路部分に基づいて行うと有利で
ある（例えば、これら欠陥の選択によって除去される回
線の量に基づいてこれら試験不能欠陥の選択を行うと有
利である。このようにすれば、冗長除去手順の効率が改
善される）。

【００８７】ステップ８７において冗長回線が除去され
た後、ステップ８１に戻って冗長除去手順の次の反復プ
ロセスが開始される。この新たな反復においては、回路
の新バージョンが現バージョンとして用いられる。

【００８８】もしステップ８５において、ステップ８４
において試験不能として特定された欠陥がなかったと判
断された場合には、決定ステップ８８において、与えら
れた反復プロセスの中で解析すべき回路導線がまだある
かどうかが判断される（理由は、回路がステップ８７に
よって変更されたからである）。

【００８９】もし解析すべき回路導線がまだある場合
は、ステップ８９において、与えられた反復プロセスに
おいてまだ選択されていなかった回路導線が選択され、
それからプロセスはステップ８２に戻って回路の現バー
ジョンにおける試験不能欠陥を特定する試みが更になさ
れる。

【００９０】もし決定ステップ８８において、与えられ
た反復プロセスの中で解析すべき回路導線がもはやない
と判断された場合には、手順の反復プロセス全体が試験
不能欠陥を特定することなしに行われたわけで、現バー
ジョンの回路には試験不能欠陥が見出されなかったこと
になる。このようにして図８の冗長除去手順が終結し、
最後のバージョンの回路が、本来の回路設計と論理的に
同等の回路として採用される。

【００９１】以上、本発明のいくつもの実施例について
図示及び説明を行ったが、これらの実施例は、本発明の
原則の適用に当たって考慮し得る多数の可能な具体的実
現例の単なる例示に過ぎない。この技術分野の当業者で
あれば、本発明の原則に基づいて他の種々の変形例を考
え得るが、それらはいずれも本発明の精神及び技術的範
囲に包含される。

【００９２】例えば、上記実施例は、論理値０及び論理
値１からなる２値（２進）システムに基づいて作動する
論理回路に限定したが、３値（３進）又はそれ以上の多
値に基づく論理システムに基づいて別の実施例を考慮す
ることが可能である。加えて、もし与えられた回路導線
が或る与えられた論理値に仮定的に制御不能とした場合
に試験不能な欠陥のセットを定めるために、上記の図５
に示した含意手順以外の手法を用いてもよい。

【００９３】

【発明の効果】以上のように本発明の方法によれば、論
理回路における試験不能欠陥の特定に際して、従来の方
法では特定が困難だった複雑な回路冗長に由来する膨大
な大多数の試験不能欠陥を効率よく特定することが可能
となり、これによって試験不能欠陥を有効に除去して試
験を行うことができるので、論理生産の能率が改善され
る。

【図面の簡単な説明】

【図１】本発明の方法の一実施例によって生成された試
験を用いて論理回路を試験するプロセスの例を示す説明
図である。

【図２】本発明の方法の一実施例が有利に適用される組
合せ論理回路の例を示す説明図である。

【図３】組合せ論理回路に用いた本発明の方法の一実施
例を説明する流れ図である。

【図４】制御不能表示子の、前方への伝播、並びに観測
不能表示子の生成及び後方への伝播についての数例を選
んで示す説明図である。

【図５】図３の流れ図の手順に用いられる含意手順の例
を示す流れ図である。

【図６】本発明の方法の一実施例が適用される順序論理
回路の組合せ反復アレイ回路モデルの例を示す説明図で
ある。

【図７】順序論理回路に用いた本発明の方法の一実施例
を説明する流れ図である。

【図８】組合せ論理回路から冗長が除去される本発明の
方法の付加的実施例を説明する流れ図である。

【符号の説明】

１１ 試験生成装置 １２ 製造された論理回路例（製造済回路） １３ 回路素子 １４ 主入力 １５ 主出力 ２１、２２、２３ ＡＮＤ（論理積）ゲ−ト ２４ ＯＲ（論理和）ゲ−ト ４１、４５ インバータ・ゲ−ト ４２、４３、４６、４７ ＮＡＮＤ（否定論理積）ゲ−
ト ４４ 回路線ファン・アウト点 ６５、６６、６７、６８、６９ 組合せ論理回路ブロッ
ク ａ、ｂ、ｃ 主入力 ｇ 主出力

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

Claims (10)

【特許請求の範囲】
1. 【請求項１】 各々１個以上の回路導線を有する複数の
   回路素子と、該回路素子の該回路導線を相互接続する複
   数の回線とからなる、順序論理回路のモデルであって、
   該回路導線が各々、予め定められた複数の論理値の１つ
   を取ることができるような順序論理回路のモデル、にお
   ける試験不能欠陥、を特定する方法であって、 前記モデルの前記回路導線の１つを選択するステップ
   と、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第１の値を取ることができないとした場合に
   は試験不能であるような、第１の欠陥セットを定めるス
   テップと、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第２の値を取ることができないとした場合に
   は試験不能であるような、第２の欠陥セットを定めるス
   テップと、 前記第１の欠陥セットと前記第２の欠陥セットとの両方
   に含まれる１個以上の欠陥を試験不能欠陥として特定す
   るステップと、からなることを特徴とする、論理回路に
   おける試験不能欠陥を特定する方法。
2. 【請求項２】 各々１個以上の回路導線を有する複数の
   回路素子と、該回路素子の該回路導線を相互接続する複
   数の回線とからなる、順序論理回路のモデルであって、
   該回路導線が各々、予め定められた複数の論理値の１つ
   を取ることができるような、順序論理回路のモデル、に
   基づいて該順序論理回路に対する試験を生成する、自動
   化された順序論理回路試験生成方法であって、 前記モデルの前記回路導線の１つを選択するステップ
   と、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第１の値を取ることができないとした場合に
   は試験不能であるような第１の欠陥セット、を定めるス
   テップと、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第２の値を取ることができないとした場合に
   は試験不能であるような第２の欠陥セット、を定めるス
   テップと、 前記第１の欠陥セットと前記第２の欠陥セットとの両方
   に含まれる１個以上の欠陥を試験不能欠陥として特定す
   るステップと、 試験不能欠陥として特定されなかった１個以上の欠陥に
   基づいて前記試験を生成するステップと、からなること
   を特徴とする、自動化された順序論理回路試験生成方
   法。
3. 【請求項３】 前記方法において、 前記順序論理回路の前記モデルが、順序論理回路の組合
   せ反復アレイ回路モデルからなり、該組合せ反復アレイ
   回路モデルが、予め定められた数の時間フレ−ムからな
   り、 前記選択された回路導線が、前記組合せ反復アレイ回路
   モデルの前記時間フレ−ムの１つから選択された回路導
   線であり、 前記第１の欠陥セットと前記第２の欠陥セットとの各々
   が、前記組合せ反復アレイ回路モデルの、時間的に最も
   後の時間フレ−ムにおける欠陥からなる、ことを特徴と
   する請求項１、又は請求項２の方法。
4. 【請求項４】 前記方法において、 前記第１の論理値に対応する前記第１の欠陥セットを定
   めるステップと前記第２の論理値に対応する前記第２の
   欠陥セットを定めるステップとが各々、含意手順からな
   り、 該含意手順が、 前記選択された回路導線が前記第１の論理値及び前記第
   ２の論理値のうちの対応する論理値を取ることができな
   いことを仮定するような初期の制御不能表示子を前記選
   択された回路導線に割り当てるステップと、 伝播ルールセットに基づいて前記論理回路を通して前方
   へ前記初期の制御不能表示子を伝播させることによっ
   て、制御不能表示子を、前記選択された回路導線以外の
   回路導線に割り当てるステップと、 前記対応する回路導線によって取られた値を観測するこ
   とができないことを仮定するような初期の観測不能表示
   子を回路導線に、前記割り当てられた初期の制御不能表
   示子に基づいて、割り当てるステップと、 伝播ルールセットに基づいて前記論理回路を通して後方
   へ観測不能表示子を伝播させることによって、付加的な
   観測不能表示子を回路導線に割り当てるステップと、 前記制御不能表示子と前記観測不能表示子とこれらの表
   示子に対応する回路導線とに基づいて前記欠陥セットを
   定めるステップと、からなる、ことを特徴とする請求項
   １又は請求項２の方法。
5. 【請求項５】 前記方法において、 前記順序論理回路の前記モデルが、順序論理回路の組合
   せ反復アレイ回路モデルからなり、該組合せ反復アレイ
   回路モデルが、予め定められた数の時間フレ−ムからな
   り、 前記選択される回路導線が、前記組合せ反復アレイ回路
   モデルの前記時間フレ−ムの１つから選択され、 前記欠陥セットを定めるステップが、前記制御不能表示
   子と前記観測不能表示子とこれらの表示子に対応する回
   路導線とに基づいて前記欠陥セットを定めるその前記ス
   テップにおいて、前記対応する回路導線が、前記組合せ
   反復アレイ回路モデルの時間的に最も後の時間フレ−ム
   に位置するおける欠陥からなる、ことを特徴とする請求
   項４の方法。
6. 【請求項６】 製造された順序論理回路を、該製造され
   た順序論理回路の或るモデルに基づいて自動的に生成さ
   れた試験を用いて試験する方法であって、該試験が回路
   刺激と、対応する期待回路応答とからなり、該モデルが
   各々１個以上の回路導線を有する複数の回路素子と、該
   回路素子の該回路導線を相互接続する複数の回線とから
   なり、該回路導線が各々、予め定められた複数の論理値
   の１つを取ることができるようにした、製造された順序
   論理回路を試験する方法において、 前記モデルの前記回路導線の１つを選択するステップ
   と、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第１の値を取ることができなかった場合には
   試験不能であるような第１の欠陥セット、を定めるステ
   ップと、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第２の値を取ることができなかった場合には
   試験不能であるような第２の欠陥セット、を定めるステ
   ップと、 前記第１の欠陥セットと前記第２の欠陥セットとの両方
   に含まれる１個以上の欠陥を試験不能欠陥として特定す
   るステップと、 試験不能欠陥として特定されなかった１個以上の欠陥に
   基づいて前記試験を生成するステップと、 前記生成された回路刺激を前記製造された順序論理回路
   に対して適用するステップと、 前記製造された順序論理回路からの、回路応答を測定す
   るステップと、 前記製造された順序論理回路からの前記回路応答が前記
   生成された回路刺激に対応する前記生成された期待回路
   応答と異なるかどうかを定めるステップと、からなるこ
   とを特徴とする、製造された順序論理回路を試験する方
   法。
7. 【請求項７】 製造された順序論理回路を、該製造され
   た順序論理回路の或るモデルに基づいて自動的に生成さ
   れた試験を用いて試験する方法であって、該試験が回路
   刺激と、対応する期待回路応答とからなり、該モデルが
   各々１個以上の回路導線を有する複数の回路素子と、該
   回路素子の該回路導線を相互接続する複数の回線とから
   なり、該回路導線が各々、予め定められた複数の論理値
   の１つを取ることができるようにした、製造された順序
   論理回路を試験する方法において、 前記試験が、 前記モデルの前記回路導線の１つを選択するステップ
   と、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第１の値を取ることができなかった場合には
   試験不能であるような第１の欠陥セット、を定めるステ
   ップと、 もし前記選択された回路導線が前記予め定められた複数
   の論理値の第２の値を取ることができなかった場合には
   試験不能であるような第２の欠陥セット、を定めるステ
   ップと、 前記第１の欠陥セットと前記第２の欠陥セットとの両方
   に含まれる１個以上の欠陥を試験不能欠陥として特定す
   るステップと、 試験不能欠陥として特定されなかった１個以上の欠陥に
   基づいて前記試験を生成するステップと、 によって生成され、 前記方法が、 前記生成された回路刺激を前記製造された順序論理回路
   に対して適用するステップと、 前記製造された順序論理回路からの、回路応答を測定す
   るステップと、 前記製造された順序論理回路からの前記回路応答が前記
   生成された回路刺激に対応する前記生成された期待回路
   応答と異なるかどうかを定めるステップと、からなる、
   ことを特徴とする、製造された順序論理回路を試験する
   方法。
8. 【請求項８】 前記方法において、 前記順序論理回路の前記モデルが、順序論理回路の組合
   せアレイ回路モデルからなり、該組合せアレイ回路モデ
   ルが、予め定められた数の時間フレ−ムからなり、 前記選択された回路導線が、前記組合せアレイ回路モデ
   ルの前記時間フレ−ムの１つから選択された回路導線で
   あり、 前記第１の欠陥セットと前記第２の欠陥セットとの各々
   が、前記組合せアレイ回路モデルの、最後の時間フレ−
   ムにおける欠陥からなる、ことを特徴とする請求項６、
   又は請求項７の方法。
9. 【請求項９】 前記方法において、 前記第１の論理値に対応する前記第１の欠陥セットを定
   めるステップと前記第２の論理値に対応する前記第２の
   欠陥セットを定めるステップとが各々、含意手順からな
   り、 該含意手順が、 前記選択された回路導線が前記第１の論理値及び前記第
   ２の論理値のうちの対応する論理値を取ることができな
   いことを仮定する初期の制御不能表示子、を前記選択さ
   れた回路導線に割り当てるステップと、 伝播ルールセットに基づいて前記論理回路を通して前方
   へ前記初期の制御不能表示子を伝播させることによっ
   て、初期の制御不能表示子を前記選択された回路導線以
   外の回路導線に割り当てるステップと、 前記対応する回路導線によって取られた値を観測するこ
   とができないことを仮定する、初期の観測不能表示子、
   を回路導線に、前記割り当てられた初期の制御不能表示
   子に基づいて割り当てるステップと、 伝播ルールセットに基づいて前記論理回路を通して後方
   へ観測不能表示子を伝播させることによって、付加的な
   観測不能表示子を回路導線に割り当てるステップと、 前記制御不能表示子と前記観測不能表示子とこれらの表
   示子に対応する回路導線とに基づいて前記欠陥セットを
   定めるステップと、からなる、ことを特徴とする請求項
   ６、又は請求項７の方法。
10. 【請求項１０】 前記方法において、 前記順序論理回路の前記モデルが、順序論理回路の組合
    せアレイ回路モデルからなり、該組合せアレイ回路モデ
    ルが、予め定められた数の時間フレ−ムからなり、 前記選択された回路導線が、前記組合せアレイ回路モデ
    ルの前記時間フレ−ムの１つから選択された回路導線で
    あり、 前記欠陥セットを定めるステップが、前記制御不能表示
    子と前記観測不能表示子とこれらの表示子に対応する回
    路導線とに基づいて前記欠陥セットを定めるその前記ス
    テップにおいて、前記対応する回路導線が、前記組合せ
    アレイ回路モデルの、時間的に最も後の時間フレ−ムに
    位置する欠陥からなる、ことを特徴とする請求項９の方
    法。