JPH04147068A - 組合せ回路の故障シミュレーション方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［目　　　次］ 概　　　要 産業上の利用分野 従来の技術（第５〜７図） 発明が解決しようとする課題 課題を解決するための手段 作　　　用 実施例（第１〜４図） 発明の効果 ［概　　要コ 記憶素子を含まない組合せ回路について縮退故障を含む
状態を仮定し、この組合せ回路の動作を模擬する故障シ
ミュレーション方式に関し、回路構造を解析し、同時法
による故障シミュレーションの対象となる故障の数を削
減することで、処理に必要な計算量ならびに記憶量を抑
え、故障シミュレーション処理の高速化ならびに省メモ
リ化を実現することを目的とし、 組合せ回路内の樹枝状部分回路を認識し、該樹枝状部分
回路の先端信号線の故障のみを対象とした同時法による
故障シミュレーションを行ない、該樹枝状部分回路の先
端信号線の故障が検出可能である場合に限り、該樹枝状
部分回路内の故障検出可能性をチェックするように構成
する。

［産業上の利用分野コ 本発明は、記憶素子を含まない組合せ回路について縮退
故障を含む状態を仮定し、この組合せ回路の動作を模擬
する故障シミュレーション方式に関する。

故障シミュレーションは、回路内に故障を仮定してその
動作を模擬する処理で、ランダムパターンや、アルゴリ
ズムによって生成されたテストパターンを入カバターン
として対象回路に与え、その故障をどれだけ検出できる
かを調へるために不可欠な処理である。

［従来の技術］ 一般に、故障シミュレーションが対象とする故障は、信
号線の縮退故障である。これは、回路内の信号線の論理
値が常にＯないし１に固定されてしまう故障である。

このような縮退故障を含む回路の動作をそのまま模擬す
れば故障シミュレーションを行なったことになるが、こ
の場合、通常の論理シミュレーションを故障の数だけ繰
り返す必要があり、計算量がゲート数の二乗にもなって
、シミュレーション処理にかなりの時間を要する。

そこで、並列法、演睡法、同時法などのアルゴリズムが
提案されている。

故障シミュレーションの高速化のポイントは次の２点に
ある。

■−度に処理できる故障／入力数の拡大■処理すべき故
障数の削減 並列法は、計算機の一語に複数の故障または入力を割り
当てることによって、前者■を実現する手法である。演
鐸法や同時法は、入カバターンに応じて、陽に模擬すべ
き故障を制限することによって後者■を実現している。

以下、同時法による故障シミュレーションのアルゴリズ
ムを具体的に説明する。

第５図に示す回路は、２つのアンドゲート１゜２と１つ
のオアゲート３とからなる組合せ回路で、この回路にお
ける２つのアンドゲート１，２への入力信号線ａ、ｂ、
ｃに、入力として例えば（１゜０．１）を与えたとする
。このとき、アンドゲート１に着目すると、故障が存在
しない場合、第６図（ａ）に示すように、その信号線ｄ
からの出力は０である。

ここで、アンドゲート１の入力に故障を挿入することを
考え、信号ＩＩＡｘ　（＝ａ、ｂ、ｄ）のＶ（＝１また
はＯ）縮退故障をｘ　／　ｖと書くことにする。アンド
ゲート１に影響を与える信号線はａ。

ｂ、ｄの３本で、これらの信号線ａ、ｂ、ｄに対する６
通りの縮退故障のうち、ａ／１．ｂｌｏ。

ｄｌｏは、信号線ａ、ｂ、ｄの値を変化させないため、
動作模擬の対象からはずすほか、第６図（ｂ）に示すよ
うに、ａ　／　Ｏもアンドゲートｌの出力値を変化させ
ないため、この故障も動作模擬の対象からはずす。

同時法では、正常回路に対する動作模擬と同時にこれら
の故障が存在する際の動作をも模擬する。

その結果、出力値が正常値と異なる故障のみを。

ゲートの出力信号線に伝播させる。即ち、本例では、第
６図（Ｃ）、（ｄ）に示すように、ｂ／１ならびにゲー
ト出力の信号線ｄの故障ｄ／１が伝わる。

このように、信号線に、正常な回路の信号値だけでなく
、信号値を変化させる故障のリストを添付して動作の模
擬を行なうことが、同時法による故障シミュレーション
の特徴である。一般に、故障の影響は、故障の存在する
信号線を基点とする回路のごく一部にしか現われないこ
とが多いため、同時法は単純な故障シミュレーションと
比較して処理量が小さく抑えられる。

一般的な組合せ回路に対する同時法のアルゴリズムを第
７図により説明すると、まず、ランダムパターン、テス
トパターンで与えられる入カバターンが残っているか否
かを判定して（ステップＡ１）、残っていない場合には
処理を終了する一方、残っている場合には、残っている
入カバターンから新規のものを設定しくステップＡ２）
、最も入力端子に近い未処理ゲートを選択する（ステッ
プＡ３）。そして、正常回路でのその未処理ゲートの応
答（出力値）を模擬してから（ステップＡ４）、入力端
子（入力信号線）でアクティブな故障、つまり、入力端
子の値を変えてしまう故障の集合（リスト）Ｆを作成す
る（ステップＡ５）。第６図（ａ）〜（ｄ）に示す例で
は、ａｌｏ、ｂ／１である。続いて。

選択した未処理ゲートの出力の故障リスト（つまり出力
端子の値を変えてしまう故障のリスト）Ｌを設定する。

ここでは、初期値としてＬ＝φ（空集合）を設定してお
く（ステップＡ６）。

ついで、集合Ｆが空集合（φ）であるか否かを判定しく
ステップＡ７）、空集合でなければ、その集合Ｆ中から
故障ｆを選択しこの故障ｆを集合Ｆから除去した後（ス
テップＡ８）、この故障ｆを含む回路での未処理ゲート
の動作を模擬する（ステップＡ９）。その模擬の結果の
未処理ゲートの出力値が、ステップＡ４で求めた正常回
路の場合と同一か否かを判定する（ステップＡｌ０）。

同一でなければ、故障ｆは出力端子の値を変えてしまう
もの（例えば前記ｂ／１）であるとして、故障ｆを故障
リストしに加える一方（ステップＡ１１）、同一であれ
ば、その故障ｆは出力端子の値を変えるものではなく（
例えば前記ａ１０）、ステップＡ７に戻る。

ステップＡ７において集合Ｆが空集合であると判定され
た場合には、すべてのゲートの動作を模擬したか否か（
未処理ゲートがなくなったか）を判定しくステップＡ１
２）、未だすべてのゲートの動作模擬を行なっていない
場合には、ステップＡ３に戻る一方、すべてのゲートの
模擬を終了した場合には、すべての故障を検出できたか
否かを判定しくステップＡ１３）、検出できている場合
には処理を終了する一方、検出できていない場合には、
ステップＡ１に戻って処理を続行する。

［発明が解決しようとする課題］ しかしながら、上述した従来の同時法による故障シミュ
レーションでは、大規模回路を扱う際に記憶量が爆発的
に増大するという課題があった。

同時法は、故障の影響が回路全体に波及することが一般
には少ないという経験的事実に基盤を置く手法であり、
多くの場合、処理量、記憶量ともにほぼゲート数に比例
する。

ところが、同時法ではパターンによって、論理値に付加
される故障リストが非常に大きくなることがある。この
ような状況に陥ると、ゲートで動作を模擬しなければな
らない故障の数が増えることになり、処理量が本質的に
増大する。さらに、シミュレーションの処理に必要な記
憶量が大きくなると、仮想記憶機構が働いて、主記憶領
域からスワップアウトされるようになり、処理時間が実
時間のレベルで非常に大きくなってしまう。故障リスト
の大きさは、回路の構造と入カバターンに依存するため
、予測が困難である。

このように、従来の同時法による故障シミュレーション
では、思わぬ処理時間の増大に直面することがあり、特
に大規模回路を扱う際に大きな問題となっていた。

本発明は、このような課題に鑑みなされたもので、回路
構造を解析し、同時法による故障シミュレーションの対
象となる故障の数を削減することで、処理に必要な計算
量ならびに記憶量を抑え。

故障シミュレーション処理の高速化ならびに省メモリ化
を実現した組合せ回路の故障シミュレーション方式を提
供することを目的としている。

［課題を解決するための手段］ このため、本発明の組合せ回路の故障シミュレーション
方式（請求項１）は５組合せ回路内の樹枝状部分回路を
認識し、この樹枝状部分回路の先端信号線の故障のみを
対象とした同時法による故障シミュレーションを行ない
、その先端信号線の故障が検出可能である場合に限り、
該樹枝状部分回路内の故障検出可能性をチェックするこ
とを特徴としている。

また、樹枝状部分回路内の故障検出可能性のチェックを
、この樹枝状部分回路内部だけで同時法による故障シミ
ュレーションにて行なったり（請求項２）、その樹枝状
部分回路の構成素子の性質を考慮し、該樹枝状部分回路
の先端信号線から演桿的に検出可能な故障を求めて行な
ったりする（請求項３）。

［作　　用］ 上述の本発明の組合せ回路の故障シミュレーション方式
では、まず、組合せ回路内の樹枝状部分回路が認識され
、認識された樹枝状部分回路の先端信号線の故障のみを
対象とした同時法による故障シミュレーションが行なわ
れる。つまり、樹枝状部分回路内部の故障を、先端信号
線の故障で代表させて、同時法による故障シミュレーシ
ョンを行なうことで、処理すべき故障の数を大幅に削減
することができる。一般に、ゲートレベルの故障シミュ
レーションの計算量や記憶量は、シミュレーションの際
に評価すべきゲート数と処理すべき故障の数との積に比
例し、故障の数はゲート数に比例する。従って、上述の
ごとく処理すべき故障数を減らすことによって、故障シ
ミュレーションにおける計算量、記憶量の大幅な削減に
つながる。

樹枝状部分回路内部の故障に関しては、その先端信号線
の故障が検出可能である場合に限り、同時法によりもし
くは演繹的に故障可能性をチェックされる。

［実施例］ 以下、図面を参照して本発明の詳細な説明する。

第１図は本発明の一実施例としての故障シミュレーショ
ン方式の手順を説明するためのフローチャートであり、
本実施例では、例えば、第２図（ａ）に示すような組合
せ回路４に本発明を適用した場合について説明する。こ
の組合せ回路４は、第５図に示したものと同様に、２つ
のアンドゲート１，２と１つのオアゲート３とを構成素
子として構成されている。

本実施例では、まず、組合せ回路４を樹枝状部分回路５
ａ、５ｂの集合に分割して先端信号線・６ａ、６ｂの集
合Ｎを求める（ステップＳＬ）。その分割の様子を第２
図（ａ）〜（ｃ）および第３図に示す。第２図（ａ）に
示す組合せ回路４は、第２図（ｂ）に示すように、各信
号線を矢印とし、ゲート１〜３の出力を節点とする有向
グラフに変換される。この有向グラフで示される回路を
、第２図（ｃ）に示すように、複数の矢印が出ている節
点で回路を切断する。この結果、元の回路４は、分割を
行なった節点を先端とする樹枝状部分回路５ａ。

５ｂの集合となる。また、この節点に相当するゲート３
，１の出力線６ａ、６ｂを先端信号線と呼ぶことにする
。

このとき、シミュレーションの対象故障として、樹枝状
部分回路５　ａ　（５ｂ）の先端となる信号１ｉＡ６ａ
（６ｂ）の故障のみを考える。すなわち、樹脂状部分回
路５ａ（５ｂ）内部の故障を、先端信号線６ａ（６ｂ）
の故障で代表させ、回路全体での同時法による故障シミ
ュレーションを実行する。

つまり、第１図に示すように、ランダムパターン、テス
トパターンで与えられる入カバターンが残っているか否
かを判定して（ステップＳ２）、残っていない場合には
処理を終了する一方、残っている場合には、ステップＳ
１で抽出した集合Ｎが空集合か否かを判定しくステップ
Ｓ３）、空集合である場合には処理を終了する一方、空
集合でなければ、残っている入カバターンから新規のも
のを設定しくステップＳ４）、集合Ｎに含まれる信号線
６ａ、６ｂの故障のみを対象とした同時法による故障シ
ミュレーションを実行する（ステップＳ５）。

この後、検出可能な未処理故障があるか否かを判定しく
ステップＳ６）、存在する場合にはステップＳ２に戻っ
て同様の処理を繰り返す一方、存在しない場合には検出
可能な故障を含む信号線（６ａ、６ｂ）を先端とする樹
枝状部分回路（５ａ、５ｂ）を抽出する（ステップＳ７
）。

そして、樹脂状部分回路（５ａ、５ｂ）内部の故障に関
しては、ステップＳ７で抽出した先端信号線ｎ　（６ａ
　ｒ　６　ｂ　）の故障が検出可能なものについてのみ
、検出可能性をチェックする（ステップＳ８）。なお、
そのチェック手法については、後で詳述する。

樹脂状部分回路（５ａ、５ｂ）内部の故障検出可能性チ
ェック後には、樹脂状部分回路（５ａ、５ｂ）の故障を
すべて検出できたか否かを判定しくステップＳ９）、検
出できた場合には、その信号線ｎを集合Ｎから除去した
後、ステップＳ６に戻る一方、ステップＳ９にて検出で
きなかったと判定された場合には、そのままステップＳ
６ｉこ戻る。

ところで、第３図に示すような樹枝状構造をとる組合せ
回路の樹枝状部分回路（例えば５ａ）では次のような性
質がある。なお、第３図において、樹枝状部分回路内部
の信号線をｎ、この信号線ｎ上の故障をｆ、部分回路の
先端の信号線をＮ、この信号線Ｎ上の故障をＦとする。

また、信号線ｎ。

Ｎの期待値をそれぞれｖ、Ｖとすると、故障ｆ。

Ｆはそれぞれ〜Ｖ縮退、〜Ｖ縮退故障であるとする。

与えられた入カバターンに対して、 ・故障Ｆが外部端子で検出不能ならば、部分回路内部の
故障ｆは検出不能 ・故障ｆが信号線Ｎで検出可能で、且つ、故障Ｆが外部
端子で検出可能ならば、故障ｆも外部端子で検出可能 である。

従って、樹枝状部分回路内のすべての故障を対象とする
場合でも、上述のステップＳ５にて行なわれる通り、樹
枝状部分回路の先端信号線の故障のみを対象として同時
法による故障シミュレーションを行なう。

ここで、同時法では、加えた入カバターンで検出可能な
故障を１パスですべて求める。これを実現するため、第
７図により前述した通り、動作を模擬する際に、回路内
の各信号線で、論理値と、その信号線で検出可能な故障
のリストとを伝播させる。従って、本手法を適用して対
象故障を先端信号線（６ａ、６ｂ）の故障に限定すれば
、伝播すべき故障のリストが小さくなり、記憶量の削減
に大きな効果がある。さらに、素子では、入力信号線の
故障リストに登録されている故障の数に等しい回数だけ
動作を模擬するため、処理量の削減にも大きな効果があ
る。

また、一般に、回路全体の故障数と比較すると、先端信
号線（６ａ、６ｂ）の故障数は著しく少ないタメ、故障
シミュレーションで取り扱うべき故障数が抑えられる。

即ち、処理に必要な記憶量を大幅に削減することができ
る。

さらに、ある先端信号１ｉＡ（６ａ　、　６　ｂ）の故
障が外部端子で検出可能でなければ、対応する樹枝状部
分回路（５ａ、５ｂ）内部の故障は全く検出できないこ
とが証明され処理対象から外すことができる。従来の故
障シミュレーションでは、樹枝状部分回路（５ａ、５ｂ
）内部のすべての故障に対しても検出可能性を調べてい
たことになるため、本手法では無駄な処理が省かれて、
さらに処理の高速化および省メモリ化を実現できる。こ
れに対し、先端信号線（６ａ、６ｂ）の故障が検出可能
であれば、その樹枝状部分回路（５ａ、５ｂ）内部の故
障も検出できる可能性がある。ただし、内部の故障に対
して、回路全体の故障シミュレーションを行なう必要は
無く、その樹枝状部分回路（５ａ、５ｂ）内部で、先端
に故障の影響が現れるかどうかをチェックすればよい。

このような理由に基づいて、本発明に基づく手法では、
上述のステップ８７．Ｓ８の通り、樹脂状部分回路（５
ａ、５ｂ）内部の故障に関しては、その先端信号線（６
ａ、６ｂ）の故障が検出可能な場合に限り、検出可能性
を調べている。このとき、部分回路（５ａ、５ｂ）が樹
脂状構造であること力ら、検出可能性のチェックは部分
回路（５ａ、５ｂ）の規模に比例する処理時間で行なう
ことができる。

また、部分回路（５ａ、５ｂ）の故障がすべて検出でき
た場合には、先端信号線（６ａ、６ｂ）の故障をシミュ
レーションの対象とする必要がなくなる。これは、通常
の同時法の故障シミュレーションで用いられる故障ドロ
ップと同様の効果をもち処理の高速化、省メモリ化に貢
献する。

さて、前述したステップＳ８における樹枝状部分回路（
５ａ、５ｂ）の故障検出性チェックの手法としては、次
の二つの手法が考えられる。一つは樹枝状部分回路（５
ａ、５ｂ）内部だけで同時法による故障シミュレーショ
ンを実施して、部分回路（５ａ、５ｂ）内部の故障のう
ち、先端信号線（６ａ、６ｂ）に故障の影響が伝播する
ものを選びだす手法であり、もう一つは、先端信号１ｉ
（６ａ。

６ｂ）からスタートして、構成素子（符号１〜３）の性
質を考慮して演繹的に検出可能な故障を求めていく手法
である。

前者の手法は実装が容易であり、また、対象が比較的小
規模の部分回路に限定されるため、処理量、記憶量の問
題が顕在化することが少なく、十分実用的である。具体
的な手順等は、第７図にて前述した通りである。

後者の手法では、先端信号１ｉ（６ａ　、　６　ｂ）の
故障シミュレーションとは別の機構によって部分回路（
５ａ、５ｂ）の故障を検出するため、実装はやや困難で
あるが、樹枝状部分回路（５ａ、５ｂ）を出力側から調
べるため、途中で探索範囲を大きく狭めることができ、
処理の効率化が期待できる。

第４図および表１を用いて、後者の手法をより具体的に
説明する。なお、第４図に示す組合せ回路は、２つの樹
枝状部分回路５ｃ、５ｄと、これらの回路５ｃ、５ｄの
先端信号線６ｃ、６ｄを入力とするアンドゲート７とか
ら構成されている。

これらの樹枝状部分回路５ｃ、５ｄにおいて、各先端信
号線６ｃ、６ｄの故障が検出可能であったとする。この
とき、樹枝状部分回路６ｃ、６ｄを出力側から入力側に
向かって故障検出性をチェックすることができる。今、
先端信号線６ｃ、６ｄを駆動する素子が２人力のアンド
ゲート７であり、正常な信号値がＸ（信号線６　ｃ　）
　＝　Ｏ＋　ｙ　（信号線６ｄ）＝１であると仮定する
と、Ｘの故障はアンドゲート７の先端信号線６ｅ（ｚ）
で検出可能であるが、ｙの故障はＸにマスクされ検出で
きない。さらに、ｙを先頭とする樹枝状回路５ｄ内部の
すべての信号線の故障も検出できないことがわかる。

表　　　　　１ このように、素子の種類と正常回路の論理値とを組み合
わせると、出力側から入力側に１回トレースするだけで
、樹枝状部分回路６ｃ、６ｄ内のスヘての信号線の故障
検出性を調べることができる。その際に、故障検出でき
ない信号線を発見することができれば、そこから入力側
の信号線の故障が検出できないことが即座に判明し、処
理量の削減につながる。

［発明の効果］ 以上説明したように、本発明の組合せ回路の故障シミュ
レーション方式（請求項１〜３）によれば、組合せ回路
内の樹枝状部分回路を認識し、この樹枝状部分回路の先
端信号線の故障のみを対象とした同時法による故障シミ
ュレーションを行ない、その先端信号線の故障が検出可
能である場合に限り、該樹枝状部分回路内の故障検出可
能性をチェックすることにより、同時法による故障シミ
ュレーションで問題であった記憶量の爆発的増大を回避
することができ、故障シミュレーシゴン処理の実時間レ
ベルでの高速化を実現できるという点で、論理回路設計
の効率化に寄与するところが極めて大きい６

【図面の簡単な説明】

第１図は本発明の一実施例としての組合せ回路の故障シ
ミュレーション方式の手順を説明するためのフローチャ
ート、 第２図（ａ）〜（ｃ）は本実施例における樹枝状部分回
路の認識・分割を説明するための図、第３図は樹枝状部
分回路の性質を説明するための図、 第４図は樹枝状部分回路内部の故障検出可能性チェック
の一例を説明するための回路図、第５図は組合せ回路の
一例を示す回路図。 第６図（ａ）〜（ｄ）は一般的な同時法による故障シミ
ュレーションについて説明するための図、第７図は従来
の同時法による故障シミュレーション方式の手順を説明
するためのフローチャートである。 図において。 １．２はアンドゲート（構成素子）、 ３はオアゲート（構成素子）、 ４は組合せ回路、 ５ａ、５ｂ、５ｃ、５ｄは樹枝状部分回路、６ａ、６ｂ
、６ｃ、６ｄ、６ｅは先端信号線、７はアンドゲート（
構成素子）である。

Claims (3)

【特許請求の範囲】
1. （１）組合せ回路（４）について縮退故障を含む状態を
   仮定し、該組合せ回路（４）の動作を模擬する組合せ回
   路の故障シミュレーション方式において、該組合せ回路
   （４）内の樹枝状部分回路（５ａ、５ｂ）を認識し、 該樹枝状部分回路（５ａ、５ｂ）の先端信号線（６ａ、
   ６ｂ）の故障のみを対象とした同時法による故障シミュ
   レーションを行ない、該樹枝状部分回路（５ａ、５ｂ）
   の先端信号線（６ａ、６ｂ）の故障が検出可能である場
   合に限り、該樹枝状部分回路（５ａ、５ｂ）内の故障検
   出可能性をチェックすることを 特徴とする組合せ回路の故障シミュレーション方式。
2. （２）該樹枝状部分回路（５ａ、５ｂ）内部だけで同時
   法による故障シミュレーションを行なって、該樹枝状部
   分回路（５ａ、５ｂ）内の故障検出可能性をチェックす
   ることを特徴とする請求項１記載の組合せ回路の故障シ
   ミュレーション方式。
3. （３）該樹枝状部分回路（５ａ〜５ｄ）の構成素子（１
   〜３、７）の性質を考慮し、該樹枝状部分回路（５ａ〜
   ５ｄ）の先端信号線（６ａ〜６ｅ）から演繹的に検出可
   能な故障を求めて、該樹枝状部分回路（５ａ〜５ｄ）内
   の故障検出可能性をチェックすることを特徴とする請求
   項１記載の組合せ回路の故障シミュレーション方式。