JPH03201035A - 検査系列生成方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明（よ　ディジタル回路の検査系列生成方法に関す
る。

従来の技術 従来の検査系列生成方法（よ　プレンティスホー也　イ
ングルウッド　クリ７、ニュー　ジャージ（ＰＲＥＮＴ
ＩＣＥ−ＨＡＬＬ、　　Ｅｎｇ　Ｉ　ｅｗ。

ｏｄ　　Ｃ１１ｆｆ、Ｎｅｗ　　Ｊｅｒｓｅｙ）発行の
「フォールト　トレラント　コンピユーテイング　セオ
リ　アンド　テクニックス　ボリュームＩ　　（ＦＡＵ
ＬＴ　　ＴＯＬＥＲＡＮＴ　　ＣＯＭＰＵＴＩＮＧ　　
Ｔｈｅｏｒｙ　　ａｎｄ　　Ｔｅｃｈｎｉｑｕｅｓ　　
Ｖｏ　ｌｕｍｅ　　Ｉ）ＪのＣｈａｐｔｅｒｌの１．４
．２ｒスタツク　アット　フォールト　テスティング（
Ｓｔｕｃｋ　　ａｔ　　ＦａｕＩｔ　　Ｔｅｓｔｉｎｇ
）」と、　１９８９年のインターナショナルテストコン
ファレンスの資料［Ｍ。

）Ｌ　　５ｃｈｕｌｚ　　ａｎｄ　　Ｅ、Ａｕｔｈ、　
　　ＥＳＳＥＮＴＩＡＬ：　　Ａｎ　　Ｅｆｆｅｃｔｉ
ｖｅＳｅｌｆ−Ｌｅａｒｎｉｎｇ　　Ｔｅ５ｔ　　Ｐａ
ｔｔｅｒｎ　　Ｇｅｎｅｒａｔｉｏｎ　　Ａｌｇｏｒｉ
ｔｈｍ　　ｆｏｒ　　５ｅｑｕｅｎｔｉａｌ　　Ｃ１ｒ
ｃ　ｕ　ｉ　ｔ　ｓ、　　　　Ｐ　ｒ　ｏ　ｃ、　　　
Ｉ　ｎ　ｔ、　　　Ｔ　ｅ　ｓｔ　　Ｃｏｎｆ、、　　
　ｐｐ、　　２８−３７．　　　Ａｕｇ。

１９８９］およびこれらの参考文献に記載されている。

以下に本発明が関係する検査系列生成方法の従来技術を
図面を用いて説明する。

順序回路の検査系列方法に関する従来例として【よ　第
９図に示す時間軸展開法　第１０図に示す故障伝搬経路
決定の後状態正当化を行なう方法第１１図に示す故障伝
搬経路決定と状態正当化を同時に時間軸に逆向きに行な
う方法　などかあも第９図（よ　順序回路をタイムフレ
ームという時間軸に展開した反復組合せ回路を表す概念
図である。第９図において、　９０１はタイムフレーム
０．９１１はタイムフレーム１、９２１はタイムフレー
ムｌを表す。９０２はタイムフレーム０の組合せ回路部
分、　９０３はタイムフレームＯの記憶素子、　９０４
、９０５、９０６、９０７はそれぞれタイムフレーム０
におけ水　外部大息　疑似外部入力　外部出九　疑似外
部出力を表す。９１２はタイムフレームｌの組合せ回路
部分、　９１３はタイムフレームｌの記憶素子、　９１
４、９１５、９１６、９１７はそれぞれタイムフレーム
１におけ水　外部大息　疑似外部入力　外部出九　疑似
外部出力を表す。９２２はタイムフレームｉの組合せ回
路部分、　９２３はタイムフレームｌの記憶素子、　９
２４、９２５、９２６、９２７はそれぞれタイムフレー
ムｉにおけ水　外部大息　疑似外部入力　外部出九　疑
似外部出力を表も 時間軸展開法でＣヨ　　順序回路の時間的な広がりを空
間的な回路の広がりに置き換えることにより、順序回路
を組合せ回路で表現し　対象となる単一故障を多重故障
として、反復組合せ回路上で、組合せ回路用の検査入力
生成アルゴリズムを適用する方法であも 故障伝搬経路決定の後状態正当化を行なう方法（よ　第
１０図に処理の流れを示すように　まず１００１から処
理を開始り、　　１００２の処理で、可検査性コストに
基づき故障伝搬経路を決定し　次Ｅ、１００３の処理で
最も時刻の大きなタイムフレームの未正当化信号線の正
当化を行う。　１００４で未正当化信号線が存在するか
否かを判定し未正当化信号線が存在する場合Ｇ、ｔ、１
００５の処理で時間軸を逆向きに進、”ｘ　　１００３
の処理に移も　未正当化信号線が存在しない場合（よ　
１００６に進み検査系列生成を終了すん 故障伝搬経路決定と状態正当化を同時に時間軸に逆向き
に行なう方法ｃＡＬ　　第１１図に処理の流れを示すよ
うに　まず１１０１から処理を開始し１１０２の処理型
　故障伝搬経路が完成していない場合（よ　故障箇所ま
たＣ友　　疑似外部入力か板外部出力または　次の時刻
に故障信号が対応する疑似外部入力に存在するフリップ
フロップに対応する疑似外部出力へ至る経路を求△　ま
た次の時刻に未正当化信号線が存在する疑似外部入力に
対応するフリップフロップに対応する疑似外部出力に値
を割り当て、未正当化信号線とし　状態正当化を行なう
。　工１０３の判定で検査系列生成が終了していない場
合＋１１１０４に進へ　時刻をひとつ前の時刻にＬ　　
１１０２の処理へ移る。　１１０３の判定で検査系列が
生成されている場合Ｃヨ１１０５に進み検査系列生成を
終了する。

発明が解決しようとする課題 しかしなが転　従来の方法は以下のような問題点を有し
ていた （１）検査系列生成の結果　十分な故障検出率が得られ
ない場合には、　検査が容易となるように設計自体を変
更する検査容易化設計が必要となも待にパーシャルスキ
ャン設計を採用する場合に（よ検査系列生成の結果未検
出となった故障を数多く検出するために（よ　どの記憶
素子をスキャンするかということが重要であも　しかし
　従来の方法で（よ　検査系列生成の途中で計算時間の
制限等により、処理を打ち切った場合に　どの記憶素子
をスキャンすればよいかということを示す情報を得るこ
とし、困難であも 例えば時間軸展開法で（よ　反復組合せ回路上で、複数
のタイムフレームを同等に扱うた取　打ち切った時点で
タイムフレームにまたがって未正当化信号線および故障
の影響が散在するので、スキャンすべき記憶素子の選択
に役立つ情報を直ちに得ることし、困難である。

故障伝搬経路決定の後状態正当化を行なう方法および故
障伝搬経路決定と状態正当化を同時に時間軸に逆向きに
行なう方法で１′Ｌ　処理を打ち切った時点で、故障箇
所から外部出力までの故障伝搬経路が正当化されていな
い場合があるので、そのときはスキャンすべき記憶素子
の選択に役立つ情報は得られな賎 （２）故障伝搬処理に時間がかかん 故障伝搬処理に時間がかかる原因にζよ　故障伝搬が容
易である経路を選ぶことが困難であることと、各故障毎
に伝搬経路活性化を行なうことがあげられも 例えば時間軸展開法で（よ　反復組合せ回路上の各ゲー
トについて前方操作により順次故障信号の伝搬を行い、
　また経路選択が不適切であった場合に（よ　各ゲート
毎に行った値の割り当てについてバックトラックを行う
ので、計算時間がかかる。

故障伝搬経路決定の後、状態正当化を行なう方法でζよ
　最初の選択が不適切であった場合に　経路活性化が困
難な経路を活性化しようとして多数のバックトラックを
発生するた吹　検査系列生成の時間が非常に長くなる。

これらの方法および故障伝搬経路決定と状態正当化を同
時に時間軸と逆向きに行う方法とＬ　各故障毎に故障伝
搬経路の選択または故障伝搬操作を行なう必要があるの
玄　いずれも多くの計算時間を必要とする。

（３）立ち上がり、立ち下がり信号を生ぜしめる困難さ
を正確に表す尺度がな賎 従来の方法では　発見的手法を用いる暇　クロック動作
に関して、立ち上がり、立ち下がりを生ぜしめる困難さ
を直接反映する再検査性尺度がなく、　０に制御する困
難さと１に制御する困難さを用いて立ち上がり、立ち下
がり動作の困難さを表していたので、効率が悪くなるこ
とがありｔう例えば　２入力の排他的論理和素子では　
一方の入力に立ち上がり動作および立ち下がり動作を生
じさせることが容易であれば　他方の値は０でも１で転
　出力に立ち上がり、立゛ち下がりを生ぜしめることが
容易であるのに　従来の計算方法によると、出力にＯを
生ぜしめる困難さと１を生ぜしめる困難さを用いて出力
の立ち上がり、立ち下がりの困難さを表していたので、
実際に立ち上がり、立ち下がり信号を生ぜしめることが
容易であるにも関わらず困難であると見なされてしまう
た△　実際には立ち上がり、立ち下がり信号を生じさせ
ることが困難な他の信号線に立ち上がり信号、立ち下が
り信号を割り当てる努力を行なうことがあり、そのとき
は検査入力生成の効率が悪くなる。

（４）記憶素子の制御入力に入る故障信号の扱いが困難
である。

故障伝搬経路に　記憶素子の制御入力か板　記憶素子の
出力を通る経路が含まれているときなど、記憶素子の制
御入力に　立ち上がりまたは立ち下がり信号の有無の差
異を生じさせることにより、故障の有無を出力側へ伝搬
させるように故障伝搬を行なう隘　二つ以上の時刻を同
時に考慮する必要があるた数　メモリ量が増大し　また
二つ以上の時刻を管理するために検査入力生成の効率が
悪く　なる。

（５）再収れんしているクロック信号の扱いが困難であ
る。

従来の方法でｃヨ　　クロック信号が分岐し　異なる数
のタイムフレームを通過した眞　再収れんしている場合
、時間軸展開そのものが困難であったり、時間軸展開が
できても後方追跡で生じた要求の矛盾のためタイムフレ
ームにまたがるバックトラックが生じて検査系列生成の
効率が悪くなる。

例えば時間軸展開法で（′！、再収れん経路上に記憶素
子があるような場合に（よ　再収れん経路にそったタイ
ムフレームの数が一致しないときがあるの双　時間軸展
開そのものを行なうことが困難である。

故障伝搬経路決定の後状態正当化を行なう方法および故
障伝搬経路決定と状態正当化を同時に時間軸に逆向きに
行なう方法で（よ　実際には再収れん経路上の状態には
制約があるにも関わらず、処理上　独立して状態を割り
当てることができるものとして扱うたべ　再収れん点で
矛盾を生改　検査入力生成の効率が悪くなる。

（６）状態正当化に計算時間がかかる。

従来の方法で（よ　各故障についての検査系列生成の処
理毎に　状態正当化を行なう必要があったたべ　多くの
計算時間を必要としていた本発明は係る点に鑑みてなさ
れたものであり、効率のよい検査系列生成方法を提供す
ることを目的とすも 課題を解決するための手段 この目的を遠戚するために　請求項（１）の発明で（よ
　対象としている故障を含む組合せ回路部分についての
検査入力生成を行なし＼　その結果ドントケアでない状
態が設定された記憶素子と故障信号が到達している記憶
素子とを調べ　その後故障伝搬と状態正当化を行ない、
　計算時間の制限などにより、故障伝搬あるいは状態正
当化の途中で検査系列生成を打ち切った場合に（よ　前
記の記憶素子を調べた結果を出力ま　どの記憶素子をス
キャンするべきかを判断する材料とすることを特徴とす
る 請求項（２）および請求項（３）の発明で（友疑似外部
入力に仮定した故障についての検査系列生成の結果を他
の故障の検査系列生成に利用する。

請求項（２）の発明で（よ　前処理で疑似外部入力に仮
定した故障に対する組合せ回路部分についての検査入力
生成を行なｔ、Ｘ、その前処理の結果を用いて、疑似外
部出力へ達した故障信号を外部出力まで伝搬させること
を特徴とする 請求項（３）の発明で（戴　請求項（２）の発明の特徴
に加えて、疑似外部出力へ達した故障信号を、前処理の
結果を用いて外部出力へ伝搬させることが可能な疑似外
部出力まで、前処理の結果を用いて伝搬させることを特
徴とする 請求項（４）および請求項（５）の発明で（表立ち上が
り、立ち下がりを生ぜしめる困難さを表す可検査性尺度
を用いも 請求項（４）の発明で（よ　従来から用いられてきたＯ
可制御費、　１可制御費に加えて、前処理で、その信号
線に立ち上がり信号や立ち下がり信号を生ぜしめるのに
要する費用を求めておき、その費用を用いて検査系列生
成時にクロック信号を発生させる暇　どの信号線にクロ
ック信号を割り当てればよいかを判断することを特徴と
する請求項（５）の発明で（よ　請求項（４）の発明の
特徴に加えて、立ち上がり信号や立ち下がり信号を生ぜ
しめるのに要する費用に基づき、各信号線の状態を観測
するのに要する費用を求めておき、その費用を用いて検
査系列生成時に故障を伝搬させる経路などを選択するこ
とを特徴とする請求項（６）の発明で（友　記憶素子の
制御入力の故障信号を、立ち上がりまたは立ち下がり信
号の有無で表す。すなわ板　記憶素子の制御入力に故障
の影響を伝搬させるとき（よ　正常時と故障時の値の組
合せ爪　立ち上がりまたは立ち下がり信号とＯまたは１
の組合せ、またはその逆の組合せとなるように値を割り
当てることを特徴とする請求項（７）の発明では　前処
理で各記憶素子の制御入力にクロック信号が入る時刻を
求めておき、これに従い記憶素子に値を割り当てる。す
なわ板　記憶素子の制御入力にクロックを設定する胤　
設定する時刻を、前処理で求めた情報に従い決定するこ
とを特徴とする 請求項（８）の発明でζよ　後方追跡において、樹枝状
回路については　前処理で求めた情報により、値の設定
目標を樹枝状回路の出力から樹枝状回路の入力へ伝える
。すなわ板　この発明の検査系列生成方法ζよ　各樹枝
状回路の出力をＯ５１に設定するための樹枝状回路の入
力信号線の値の組合せを前処理で求めておき、これに従
って設定すべき目標値を出力側から入力側へ伝搬させる
ことを特徴とする検査系列生成方法である。

作用 請求項（１）の発明で（よ　組合せ回路部分について検
査入力生成を行（＼　その後故障伝搬と状態正当化を行
うことにより、組合せ回路の検査入力生成の結果　故障
の影響が到達している疑似外部出力に対応する記憶素子
と、検査入力が割り当てられている疑似外部入力に対応
する記憶素子とをスキャン構成にすれは　故障検出が可
能とな奴という情報を得ることができるので、効率よく
パーシャルスキャン設計を行うことができる。

請求項（２）の発明で（よ　前処理で求めた疑似外部入
力に仮定した故障についての検査系列生成の結果を他の
故障の検査系列生成にも利用することにより、故障伝搬
処理を高速化することができる。

請求項（３）の発明で（上　請求項（２）の発明と同じ
作用がある力丈　外部出力へ故障の影響が到達している
疑似外部入力の故障だけでなく、疑似外部出力へ故障の
影響が到達している疑似外部入力の故障に対する検査入
力生成の結果も用いるた取　適用範囲がさらに広くなる
。

請求項（４）の発明で（よ　立ち上がり、立ち下がりを
生ぜしめる困難さを表す再検査性尺度を用いることによ
り、より成功の可能性の高Ｌ＼　値の割り当ての選択を
行える。

請求項（５）の発明で（よ　請求項（４）の作用に加え
て、立ち上がり、立ち下がりを生じる困難さを考慮した
可観測費を用いることにより、故障伝搬経路の選択など
での成功の可能性を高めることができも 請求項（６）の発明で（よ　記憶素子の制御入力に故障
の影響を伝搬させるときζよ　正常と故障時の値の組合
せカミ　立ち上がりまたは立ち下がり信号とＯまたは１
の組合せ、またはその逆の組合せとすることにより、記
憶素子の制御入力を通る故障伝搬の処理を容易化できる
。

請求項（７）の発明で（よ　クロックの動作を前処理で
調べて、その情報に従って記憶素子の制御入力にクロッ
クが入る時刻を決定することにより、クロックの動作を
正当化する際の矛盾の発生頻度を低く抑えることができ
る。

請求項（８）の発明で（上　前処理で、樹枝状回路の出
力に０、１を設定するために樹枝状回路の入力に設定す
べき値を求めておき、設定すべき信号線と信号の選択を
行う際に　その情報を利用することにより、値の割り当
て箇所選択の処理を高速化することができる。

実施例 （実施例１） 実施例１の検査系列生成方法は　組合せ回路部分につい
て行った検査入力生成の結果　故障の影響が外部出力に
到達したとき（上　値が割り当てられている疑似外部入
力を記憶し　故障の影響が外部出力に到達しておらず疑
似外部出力に到達したとき（友　値が割り当てられてい
る疑似外部入力と故障の影響が到達している疑似外部出
力とを記憶し　検査系列生成に失敗した場合にはこれら
を出力することを特徴とする検査系列生成方法である。

第１図（ａ）ｆｔ　　本発明の第１の実施例を示すフロ
ーチャートである。第１図（ｂ）ｌ；Ｌ　　本発明の第
１の実施例を示すために用い衣　検査系列生成の対象と
している順序回路の回路図である。

第１図（ｂ）において、　１３１〜１３３（よ　外部入
力である。　１３４〜１３６　ｉＬ　　外部出力である
。　１３７〜１３９（よ　疑似外部入力である。　■４
０〜１４２Ｕ　　疑似外部出力である。　１４３　＋ｉ
組合せ回路部分である。　１４４　＋ｉ　　記憶素子で
ある。

第１図（ｃ）ｔ＆　　第１図（ｂ）の順序回路を、説明
の便宜上　時間軸に展開した概念図である。

第１図（ｃ）において、　１５１〜１５９（よ　外部入
力である。　１６０〜１６８　Ｉｔ　　外部出力である
。

１６９〜１７７　ｉＬ　　疑似外部入力である。　１７
８〜１８６は　疑似外部出力である。　１８７〜１８９
（友　組合せ回路部分であム　１９０、１９１１Ｌ記憶
素子である。

第１図（ｄ）と、第１図（ｅ）Ｉｔ　　本発明の検査系
列生成方法を示すために用いる回路図である。

第１図（ｄ）および第１図（ｅ）で（よ　第１図（ｂ）
と同じものについて（友　同じ番号を付し　説明を省略
する。１９３および１９７　ｉｔ　　検査系列生成の対
象としている故障の箇所である。　１９４および１９８
　Ｕ　　組合せ回路部分１４３について検査入力を生成
した際にドントケアでない値が割り当てられている外部
入力および疑似外部入力を表す。　１９５１−１　　組
合せ回路部分１４３について検査入力を生成した際に故
障の影響が到達している外部出力を表す。また１９９ｆ
：Ｌ　　組合せ回路部分１４３について検査入力を生成
した際に故障の影響が到達している疑似外部出力を表す
。

以下、一つの故障が与えられたときＱ　特許請求の範囲
第１項記載の検査系列生成方法の実施例を、第１図（ａ
）のフローチャートと、第１図（ｄ）および第１図（ｅ
）の回路図を用いて説明する。

１０１で処理を開始する。　１０２の処理で、第１図（
ｄ）の例で（よ　故障１９３を検査入力生成の対象と獣
　第１図（ｅ）の例で（よ　故障１９７を検査入力生成
の対象とし　それぞれ　疑似外部入力１３７〜１３９を
外部入力とみなし　疑似外部出力１４０〜１４２を外部
出力とみなし　組合せ回路部分１４３に着目して、検査
入力生成の対象となる故障を検出する検査入力を生成す
る。

次に１０３の処理で故障の影響が外部出力１３４〜１３
６のうちのいずれかに到達しているか否かを判定する。

第１図（ｄ）の例で（よ　故障の影響が外部出力１３４
に到達しているので、　１０７の処理に移り、　ドント
ケア以外の値の割り当てられた疑似外部入力を記憶する
。記憶する場所（よ後に１１１の処理で取り出せるとこ
ろなら、どこでもよく、例えは　計算機の主記憶上に記
憶する。

故障の影響（表　疑似外部出力１４０へも到達している
カミ　この場合は故障の影響が到達している疑似外部出
力を記憶する必要はなしも　なぜな転　故障の影響が到
達している疑似外部出力を記憶する目的（よ　検査系列
生成に最終的に失敗した場合にどの記憶素子をスキャン
構造のものに置き換えれば　故障の影響を観測すること
ができるようになるかという情報を出力することであり
、外部出力へ故障の影響が到達している場合に（よ　記
憶素子を観測のためにスキャン構造のものに置き換えな
くてＬ　故障の影響（友　外部出力において観測可能で
あるためである。また第１図（ｄ）で（よ　故障の影響
が外部出力へ到達している場合にＬ　値が割り当てられ
て、いる疑似外部入力の記憶は行なう必要があも　なぜ
な収　値が割り当てられている疑似外部入力を記憶する
目的は　検査系列生成に最終的に失敗した場合に　どの
フリップフロップをスキャン構造のものに置き換えれば
　故障の影響を生ぜしム　その故障の影響を外部出力あ
るいは疑似外部出力へ伝搬させることができるようにな
るかという情報を出力することであるからである。

１０７の処理が終了した転　１０９の処理に移る。

第１図（ｅ）の例ように　１０３の処理で、故障の影響
が外部出力に到達していないことが判明した場合に（１
１０４の処理に移り、疑似外部出力に故障の影響が到達
しているか否かを調べる。

１０４の処理（よ　故障の影響が外部出力に到達してい
ないときにのみ行われるので、　１０４の処理で、疑似
外部出力に故障の影響が到達していない場合（よ　故障
の影響が外部出九　疑似外部出力のいずれにも到達して
いないことになり、組合せ回路についての検査系列生成
は失敗となる。この場合（よ　疑似外部出力　疑似外部
出力の記憶は行わず、　１１２に移り、直ちに検査系列
生成を終了すん 第１図（ｅ）の例のように　１０４の処理で、故障の影
響が疑似外部出力１４１に到達している場合にζよ　１
０５の処理に移り、故障の影響が到達している疑似外部
出力１４１と、　ドントケアでない値が割り当てられて
いる疑似外部入力１３７．１３９とを記憶すん 次に１０６の処理型　故障の影響を外部出力まで伝搬さ
せることを目的として、故障箇所から外部出力へいたる
故障伝搬経路を活性化する。故障伝搬経路活性化は　順
序回路の基本的な操作であるカミ　一般に　回路によっ
て膨大な時間を要することがあるので、　１０６の処理
で（表　計算時間に制限を設けて、故障伝搬経路活性化
を行なう。１０６の故障伝搬経路活性化で、計算時間の
制限による打ち切りが生じたか否かを１０８の処理で調
べも　１０８の処理で打ち切りが生じていない場合にｌ
；Ｌｉ２Ｑの処理に移り、回路の状態を初期状態に戻す
ために　状態初期化のための検査系列生成を行なう。状
態初期化ｋ　順序回路の検査系列生成の基本的な操作で
ある力交　一般に（よ　回路によって膨大な計算時間を
必要とすることがあるので、　１０９の処理で（上　計
算時間に制限を設けて状態初期化を行なう。

１０９の処理で打ち切りが生じたか否かを１１０の処理
で調べ　打ち切りが生じていない場合には　検査系列生
成に成功しているので１１２の処理に移り、検査系列生
成を終了すも　な抵　正常に検査系列が生成されたとき
の検査系列の出力ば１１２で出力されるものとすも 打ち切りが発生したか否かを調べる１０８または１１０
の処理において、打ち切りが生じていることが判明した
場合にζ友　１１１の処理に移り、１０７の処理で記憶
した疑似外部入力また＋１　１０５の処理で記憶した疑
似外部出力および疑似外部入力を出力する。　１１１の
処理が終了した後、１１２に移り、検査系列生成を終了
する。

この方法によると、検査系列生成を終了する前に処理を
打ち切った場合に仮　組合せ回路部分で求めた検査入力
により、どの記憶素子をスキャンすれば検査が可能であ
るかが容易に判定できるので、効率よくパーシャルスキ
ャン設計を適用することが可能である。

（実施例２） 実施例２の検査系列生成方法（よ　疑似外部入力に仮定
した故障について行った検査入力生成の結果を利用する
ことを特徴とする検査系列生成方法であも 本実施例で（表　疑似外部入力のクラスという概念を用
いる。クラス０の疑似外部入力（よ　その疑似外部入力
に仮定した故障の影響を外部出九　疑似外部出力のいず
れへも伝搬させることが困難なことを表している。クラ
ス１の疑似外部入力（よ　その疑似外部入力に仮定した
故障の影響を直接外部出力へ伝搬させることし、困難で
ある力ｔ　疑似外部出力を経由して最終的に外部出力へ
伝搬させることし、容易であることを表していも　クラ
ス２の疑似外部入力（よ　その疑似外部入力に仮定した
故障の影響を直接外部出力へ伝搬させることが容易であ
ることを表している。

第２図（ａ）〜（ｃ）ｌ；Ｌ　　実施例２の検査系列生
成方法を示すフローチャートであも　第２図（ｄ）ｉｔ
　　疑似外部入力の分類方法を説明するために用いる回
路図である。２５１ζよ　疑似外部入力１３７に仮定し
た故障の影響の伝搬経慝　２５２（よ　疑似外部入力１
３８に仮定した故障の影響の伝搬経路を表す。

第２図（ｅ）ζよ　本実施例の検査系列生成方法を説明
するために用いる回路図であ４２６１１；Ａ検査系列生
成の対象としている故１１ｔ２６２１Ｌ。

組合せ回路１８７について検査系列生成を行った結果　
故障の影響が伝搬している経路を表す。２６３（友　前
処理で疑似外部入力１７２に仮定した故障の影響の伝搬
経路を表す。

まず、第２図（ａ）を用いて、本実施例の全体の処理を
説明する。

２０１で処理を開始する。　２０２〜２０４で、各疑似
外部入力について、疑似外部入力の分類を行なう。

まず２０２で（よ　未処理の疑似外部入力がないかを調
べ　すべての疑似外部入力についての処理が終了したこ
とが判明した場合にｉ、ｔ、、２０５の処理に移も　未
処理の疑似外部入力がある場合に（よ２０３へ移も ２０３の処理では　疑似外部入力ＰＰＩｊを選択すも ２０４の処理でＣヨ　　選択された疑似外部入力ＰＰＩ
ｊについて疑似外部入力の分類を行なう。

２０５〜２０７で（戴　与えられた各故障について検査
系列生成を行なう。

２０５で、未処理の故障がないかを調べ　未処理の故障
がなくなった気　２０８に移り、すべての処理を終了す
る。未処理の故障がある場合にζ友２０６に移る。

２０６の処理でｃａｔ、、　　未処理の故障ｆを選択す
る。

２０７の処理でｉｌｌ、２０６の処理で選択された故障
ｆについての検査系列生成を行なう。

第２図（ｂ）ｊ；Ｌ　　疑似外部入力の分類方法２０４
を示すフローチャートであも　以下、第２図（ｂ）と第
２図（ｄ）を用いて、疑似外部入力の分類方法を説明す
る。

２１１で処理を開始すも　２１２の処理で、組合せ回路
に着目し　疑似外部入力に仮定した故障の検査入力を生
成する。第２図（ｄ）の疑似外部入力１３７について２
１２の処理を行った結果２５１に示す故障伝搬経路に沿
って、故障の影響が外部出力１３５に到達しているもの
とすも　また　疑似外部入力１３８について組合せ回路
の検査入力生成２１２を行った結果　２５２の故障伝搬
経路にそって、故障の影響が疑似外部出力１４０と１４
２に到達したものとすも ２１３の処理でｃ′！、、外部出力に故障の影響がある
か否かを調べ　故障の影響がある場合にζよ　２２４へ
移り、外部出力に故障の影響がない場合には　２１４の
処理に移も　第２図（ｄ）の疑似外部入力１３７につい
て処理を行ったとき（戴　故障の影響が外部出力１３５
に到達しているので、　２２４に移も　また　疑似外部
入力１３８について処理を行っているときは　故障の影
響は外部出力へ到達していないので、　２１４に移モ２
２４の処理で（よ　疑似外部入力のクラスを２として、
　２１２の処理で得られた検査入力を記憶し　疑似外部
入力ＰＰＩｊの分類を終了する。第２図（ｄ）の疑似外
部１３７について処理を行ったとき（上　疑似外部入力
１３７のクラスを２とし２１２の検査入力生成で求めた
検査入力を記憶す２１４の処理でζ山　疑似外部出力に
故障の影響が到達しているか否かを調べも　疑似外部出
力に故障の影響が到達している場合にζ友　２１５に移
り、到達していない場合にζよ　２２６の処理に移る。

第２図（ｄ）の疑似外部入力１３８について処理を行っ
たとき（よ　故障の影響が疑似外部出力１４０と１４２
に到達しているの”ｎ　　２１５に移る。

２２６の処理では　疑似外部入力のクラスを０とり、、
２２７に移り、分類を終了する。

２１５の処理でζよ　故障の影響が到達している疑似外
部出力の集合をＳＰＯとする。第２図（ｄ）の疑似外部
１３８について処理を行ったとき（よ故障の影響が疑似
外部出力１４０と１４２に到達しているので、疑似外部
出力１４０と１４２とを集合ＳＰＯに入れも ２１６〜２２８で１よ　故障の影響が到達している各疑
似外部出力について、クラス１またはクラス２の疑似外
部入力へ故障の影響を伝搬できるものがないかを調べる
。

２１６の処理で（よ　故障の影響が到達している疑似外
部出力の集合ＳＰ○に要素があるかないかを調べ　ある
場合には２１７に移り、ない場合には２２６に移る。第
２図（ｄ）の疑似外部入力１３８について処理を行った
ときＣ−ｔ　　要素があるので、　２１７に移る。

２１７の処理で（よ　故障の影響が到達している疑似外
部出力の集合ＳＰ○から疑似外部出力ＰＰ○ｋを選択し
　これを集合ＳＰＯから取り除く。

第２図（ｄ）の疑似外部１３８について処理を行ったと
き＋亀　１４０が取り出されたものとする。

２１８の処理では　疑似外部出力ＰＰ０ｋにある故障の
影響を出力側にある疑似外部入力ＰＰＩｍに伝搬させる
ために（よ　記憶素子の入出力にどのような値を割り当
てればよいかを調べる。疑似外部入力に伝搬させること
ができない場合に（戴２１６に移り、伝搬できる場合に
ｌ友　２１９に移も　第２図（ｄ）の疑似外部入力１３
８について処理を行ったとき（よ　疑似外部出力１４０
の故障の影響を疑似外部入力１３７に伝搬できるものと
する。

２１９の処理では　故障の影響が到達している疑似外部
出力ＰＰ０ｋの出力側にある疑似外部入力ＰＰＩｍの分
類がされているか否かを調べ　分類がされていない場合
に４１２２０に移り、分類されている場合ににＬ２２１
に移も　第２図（ｄ）の疑似外部入力１３８について処
理を行った場合には　疑似外部入力１３７の分類はすん
でいるの玄　２２１に移も ２２０の処理で（よ　疑似外部入力ＰＰＩｍについて、
第２図（ｂ）に示した処理により、再帰的に疑似外部入
力の分類を行なう。

２２１の処理で（戴　疑似外部入力ＰＰＩｍのクラスを
調べる。疑似外部入力ＰＰ　Ｉｍのクラスが０のときｉ
＆２１６に移る。疑似外部入力ＰＰＩｍのクラスが１ま
たは２のとき＋１２２２へ移も第２図（ｄ）の疑似外部
入力１３８について処理を行った場合には　疑似外部入
力１３７のクラスは２であるので、　２２２へ移る。

２２２の処理で１よ　疑似外部入力ＰＰＩｊのクラスを
１とり、　　２１２の処理で求めた検査入力と、２１８
の処理で求めた疑似外部出力ＰＰ０ｋの故障の影響を疑
似外部入力ＰＰ　Ｉｍへ伝搬させるための値の割当と、
疑似外部入力ＰＰＩｍを記憶する。第２図（ｄ）の疑似
外部入力１３８について処理を行った場合に１友　疑似
外部入力１３８をクラス１とＬ　　２１２の処理で求め
た検査入力と、２１８の処理で求めた疑似外部出力１４
０の故障の影響を疑似外部入力１３７に伝搬させるため
の値と、疑似外部入力１３７とを記憶すん２２３で、疑
似外部入力ＰＰＩ　ｊの分類の処理を終了する。

第２図（ｃ）ｉ；＆　　分類された疑似外部入力の情報
を利用する検査系列生成２０７を説明するフローチャー
トである。第２図（ｃ）と第２図（ｅ）とを用いて、検
査系列生成方法を説明すも２３１で処理を開始する。　
２３２の処理で、与えられた故障について、組合せ回路
に着目して検査入力生成を行なう。第２図（ｅ）で（よ
　故障２６１について検査系列生成を行なう。

２３３の処理で（よ　外部出力に故障の影響が到達して
いるか否かを調べも　外部出力に故障の影響が到達して
いる場合にＧ′！、、　２４４に移も　故障の影響が外
部出力に到達していない場合に（よ　２３４に移る。第
２図（ｅ）で（戴　故障の影響力交外部出力へは到達し
ていないので、　２３４に移も２３４の処理で（よ　疑
似外部出力に故障の影響が到達しているか否かを調べる
。故障の影響が疑似外部出力に到達している場合ば　２
３５に移り、故障の影響が疑似外部出力に到達していな
い場合に１．１，２４６の処理に移り、検査系列を終了
すも第２図（ｅ）では　故障の影響バ　疑似外部出力１
７８と１８０に到達しているので、　２３５に移る。

２３５の処理で（瓜　故障の影響が到達している疑似外
部出力の集合をＳＰ○とすも　第２図（ｅ）で＋ＬＳＰ
○の要素ζよ　１７８と１８０となん２３６の処理では
　疑似外部出力の集合ｓＰｏに要素があるか否かを調べ
も　疑似外部出力の集合Ｓ２Ｏに要素がある場合に１Ｌ
２３７の処理に移も　疑似外部出力の集合ＳＰ○に要素
がない場合にζよ　２４３に移る。第２図、（ｅ）では
　Ｓ２Ｏに要素があるので、　２３７に移も ２３７の処理でＣ′！、故障の影響が到達している疑似
外部出力の集合ＳＰ○から疑似外部出力ＰＰ０ｋを選択
し　集合ＳＰＯから取り除く。第２図（ｅ）でζよ　１
７８を選択するものとすも２３８の処理で（よ　疑似外
部出力ＰＰ０ｋに到達している故障の影響を出力側にあ
る疑似外部入力ＰＰＩｍへ伝搬するための値の割当を行
なう。

故障の影響を疑似外部入力ＰＰＩｍへ伝搬できる場合に
ｊ；Ｌ、２３９へ移り、伝搬できない場合に（よ２３６
へ移る。第２図（ｅ）でＣ′！、疑似外部出力１７８の
故障の影響を出力側の疑似外部入力１７２に伝搬できる
ものとＬ　２３９に移る。

２３９の処理では　疑似外部入力ＰＰＩｍのクラスを調
べも　疑似外部入力ＰＰＩｍのクラスが２の場合に４；
ｔ、、２４０に移り、疑似外部入力ＰＰＩｍのクラスが
０または１のときは　２３６に移も　第２図（ｅ）でＣ
ヨ　　疑似外部入力１７２（よりラス２であるの′″Ｃ
Ｓ　２４０へ移る。

２４０の処理で（友　前処理２２４で求めた疑似外部入
力ＰＰＩｍの検査入力と、　２３２の処理で求めた検査
入力および２３８の処理で求めた疑似外部出力ＰＰ０ｋ
の故障の影響を疑似外部入力ＰＰＩｍに伝搬させるため
の値の割当を比較する。

２４１の処理で？友　２４０の処理で矛盾が生じたか否
かを調べも　矛盾が生じた場合に！！２３６に移り、矛
盾しない場合にＧ戴　２４２へ移も２４２の処理でζよ
　前処理で求めた疑似外部入力ＰＰＩｍの検査入力と、
　２３８の処理で求めた値を割り当てて、外部入力以外
に割当があったものを未正当化信号線とする。第２図（
ｅ）で（よ前処理で疑似外部入力１７２の故障について
求めた検査入力と、　２３８の処理で求めた値を割当て
、外部入力以外に割当があったものを、未正当化信号線
とすも ２４３の処理でζ戴　故障伝搬経路活性化のための検査
系列生成を行なう。これ（よ　未正当化信号線を正当化
することにより、故障の影響を故障箇所か転　外部出力
まで伝搬させる処理である。

２４４の処理で（よ　状態初期化のための検査系列生成
を行なう。これ（友　回路を初期状態か転故障の影響を
発生できる状態へ遷移させるための処理であも ２４５で処理を終了する。

この方法によれば　故障毎の検査系列生成のう叡　故障
伝搬経路活性化の部分を前処理の結果をそのまま用いる
ことができるために大幅に簡単化でき、効率のよい検査
系列生成が可能となも（実施例３） 実施例３の検査系列生成方法（よ　疑似外部入力に仮定
した故障について行った検査入力生成の結果を利用する
ことを特徴とする検査系列生成方法であも 第３図（ａ）Ｇ；Ｌ　　実施例３の検査系列生成方法を
示すフローチャートである。第３図（ｂ）ｉｔ実施例３
の検査系列生成方法を説明するために用いる回路図であ
も　第３図（ａ）ＩＬ　　第２図（ｃ）の２３９〜２４
２の処理を、　３０１〜３１０に置き換えたものであａ
　第３図（ａ）の中″Ｑ、第２図（ｃ）と同じ処理につ
いては説明を省略する。

３０１の処理で（上　故障の影響が到達している疑似外
部出力のう板　出力側にある疑似外部入力へ故障の影響
が伝搬でき、伝搬光の疑似外部入力がクラス１または２
のものを求めていも　伝搬光の疑似外部入力がクラス０
の場合ば　２３６に移り、クラスｌまたは２のとき＋Ｌ
３０２に移る。

第３図（ｂ）ｆＬ　　故障３３１の影響が到達している
疑似外部出力１８０力交　その出力側の疑似外部入力１
７４へ故障の影響を伝搬でき、　１７４がクラス１であ
る場合を示していも　従ってこの場合ζよ　３０２へ移
も ３０２の処理で（友　前処理で求めた疑似外部入力ＰＰ
Ｉｍの検査入力と、　２３２の処理で求めた検査入力お
よび２３８の処理で求めた疑似外部出力ＰＰ０ｋの故障
の影響を疑似外部入力ＰＰ　１ｍに伝搬させるための値
の割当とを比較する。第３図（ｂ）で（上　前処理で求
めた疑似外部入力１７４の検査入力と、　２３２の処理
で求めた検査入力及び２３８の処理で求めた疑似外部出
力１８０の故障の影響を疑似外部入力１７４へ伝搬させ
るための値の開通とを比較すも ３０３で＋Ｌ３０２の処理で矛盾が生じたか否かを調べ
る。矛盾が生じた場合には　２３６に移り、矛盾しない
場合にｉ戴　３０４へ移も　第３図（Ｃ）では　矛盾が
生じていないものとり、　　３０４へ移も ３０４の処理でば　検査系列を一時的に格納する集合Ｓ
ＰＴを空にする。

３０５の処理で（よ　疑似外部入力を分類する第２図（
ｂ）の２２４または２２２で求めた検査入力と、　２３
８の処理で求めた値の割当とをＳＰＴに加える。第３図
（ｂ）で？友　前処理で求めた１７４に仮定した故障の
検査系列と、２３８の処理で求めた疑似外部出力１８０
の故障の影響を疑似外部入力１７４へ伝搬させるための
値をＳＰＴに格納する。

その後、　３０６〜３０９の処理で、再帰的に出力側を
調べ　クラス２の疑似外部入力に出会うまで順次　疑似
外部入力の分類の前処理で求めた検査入力及び出力側の
疑似外部入力へ伝搬させるための値の割当を集合ＳＰＴ
に加えていく。

３０６の処理で（よ　疑似外部入力ＰＰ　Ｉｍのクラス
を調べ　クラスがＩの場合＜１３０７に移り、クラスが
２の場合に！；Ｌ３１０に移転　第３図（ｂ）で（友　
疑似外部入力１７４のクラスは１であるので、　３０７
へ移も ３０７の処理でＧ！　　前処理で求めた疑似外部入力Ｐ
ＰＩｍの故障の影響の伝般光の疑似外部入力をＰＰＩｎ
とすも　第３図（ｂ）で（よ　疑似外部入力３３４をＰ
ＰＩｎとすも ３０８の処理で【友　前処理で求めた疑似外部入力ＰＰ
Ｉｎの検査入力と、ＰＰＩｍの故障の影響をＰＰＩｎに
伝搬させるための値とをＳＰＴに加えも　第３図（ｂ）
では　前処理で求めた疑似外部入力３３４の検査系列と
、疑似外部入力１７４の故障の影響を疑似外部入力３３
４へ伝搬させる値とをＳＰＴに加えも ３０９の処理でｌ上　ＰＰＩｎを次のＰＰＩｍとＵ３０
６へ移も　第３図（ｂ）で（よ　疑似外部入力３３４を
次のＰＰＩｍとして、　３０６に移る。

第３図（ｂ）でζよ　３０６〜３０９の処理を繰り返し
て、最終的に　３０６の処理で、クラス２の疑似外部入
力１７６がＰＰ　Ｉｍとなっているものとすも　このと
き、　３１０に移る。

３１０の処理でにｔ、ＳＰＴに格納されている系列を割
り当てて、外部入力以外に割当があったものを未正当化
信号線とする。

この方法によれＩ′Ｌ　　第２の実施例と同様に　故障
毎の検査系列のうち故障伝搬経路活性化のための検査系
列生成の処理を、前処理の結果をそのまま用いることに
より大幅に削減することができもさらに第２の実施例に
比べて、前処理の結果を用いる場面が多くなるという利
点も有している。

（実施例４） 実施例４の検査系列生成方法は　立ち上がり信号　立ち
下がり信号を生じる困難さを表すＰ可制御費、Ｎ可制御
費を用いることを特徴とする検査系列生成方法である。

第４図（ａ）ｉ；Ｌ　　実施例４の検査系列生成方法を
示すフローチャートであも　第４図（ｂ）〜（ｅ）Ｉｔ
、Ｐ可制御費、Ｎ可制御費を求める４０２の処理を説明
する図であも　第４図（ｆ）ｌ；ＬＰ可制御費、Ｎ可制
御費を用いる検査系列生成４０３を説明する回路図であ
も　第４図（ｇ）にＬ　　第４図（ｆ）の回路の各信号
線のＯ可制′ａｇＬ　１可制御ｇＩＬＰ可制御ｔ　　Ｎ
可制御費の表であも以王　第４図（ａ）〜（ｇ）を用い
て本実施例の検査系列生成方法を説明すも ４０１で処理を開始すも　４０２でＣよ　検査系列生成
４０３の前処理として、通常用いられている０可制御覧
　１可制御費に加えて、Ｐ可制御費およびＮ可制御費を
計算する。その方法（よ　第４図（ｂ）〜（ｅ）を用い
て後はど詳細に説明する。

４０３では　第４図（ｂ）で説明するように　０可制御
費、　１可制御費、Ｐ可制御費、Ｎ可制御費を用いて検
査系列生成を行う。

従来から０可制御費、　１可制御費について（よ種々の
計算方法が知られていも　本実施例で（よそのうちの一
つであ久　アイ・イー・イー・イー・デザイン・アンド
・テスト・オン・コンピューターズ誌１９８６年８月号
の４３〜５４ページに記載されてい７ｘ　　Ｍ、Ａｂｒ
ａｍｏｖｉｃｉらによる論文ｒＳＭＡＲＴ　　ａｎｄ　
　ＦＡＳＴ：　　Ｔｅ５ｔ　　Ｇｅｎｅｒａｔｉｏｎ　
　ｆｏｒ　　ＶＬＳＩＳｃａｎ−Ｄｅｓｉｇｎ　　Ｃ１
ｒｃｕｉｔｓ」の中で紹介されている組合せ回路を対象
としたＯ可制御機　１可制御費を求める方法を拡張し　
新しくＰ可制御費、Ｎ可制御費を加えた方法で説明する
。

な抵　本発明は　これ以外に転　アイ・イー・イー・イ
ー・トランズアクション・オン・サーキット・アンド・
システムズ誌１９７９年９月号の６８５〜６９３ページ
に記載されてい７ｘ　　Ｌ、　　Ｇｏｌｄｓｔｅｉｎに
よる論文ｒｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ１０ｂｓｅ
ｒｖａｂｉｌｉｔｙＡｎａｌｙｓｉｓ　　ｏｆ　　Ｄｉ
ｇｉｔａｌ　　Ｃ１ｒｃｕｉｔｓ」等の方法にも適用で
きる。

第４図（ｂ）〜（ｅ）で（上　信号線ｌの０可制御ＩＪ
Ｉ、１可制御費、Ｐ可制御費、Ｎ可制御費を、それぞれ
　Ｃｏ　　（１）、Ｃ１（１）、ＣＰ　（１）、ＣＮ　
（１）と書き表す。可制御費は　ある信号線の状態を指
定された値に制御する困難さを表し数値が大きいものほ
ど制御が困難であることを、数値が小さいものほど制御
が容易であることを示している。外部入力は外部から直
接制御できるので、　ｌが外部入力である場合にｉ；Ｌ
ＣＯ（１）＝Ｃ１（１）＝ＣＰ　（１）＝ＣＮ　（１）
＝Ｏとなん第４図（ｂ）ｌ；Ｌ　　論理ゲートの出力側
の０可制御費、　１可制御費、Ｐ可制御費、Ｎ可制御費
を求める方法を示した図であ、４　４１１、４１２はＮ
ＡＮＤゲートの入力信号線　４１３はＮＡＮＤゲートの
出力信号線である。４１４１．１ＮＡＮＤゲートの出力
側のＯ可制御費、　１可制御費、Ｐ可制御費、Ｎ可制御
費を求める計算式である。

ＮＡＮＤゲートの出力信号線４１３をＯに制御するにｉ
；ＬＮＡＮＤゲートの入力信号線４１１および４１２を
両方１に制御する必要がある。従ってＮＡＮＤゲートの
出力信号線４１３の０可制御費Ｃｏ　（４１３）ｉ；Ｌ
　　ＮＡＮＤゲートの入力信号。

線４１１の１可制御費ＣＩ（４１１）とＮＡＮＤゲート
の入力信号線４１２の１可制御費Ｃ１（４１２）の和と
なる。同様ｊ、：、ＮＡＮＤゲートの出力信号線４１３
を１に制御するに？、１ＮＡＮＤゲートの入力信号線４
１１または４１２のいずれかを０に制御する必要がある
。従ってＮＡＮＤゲートの出力信号線４１３のｌ可制御
費Ｃ１（４１３）ｌｔＮＡＮＤゲートの入力信号線４１
１のＯ可制御費Ｃｏ（４１１）とＮＡＮＤゲートの入力
信号線４１２のＯ可制御費Ｃｏ（４１２）のうち大きく
ない方と等しい値となん ＮＡＮＤゲートの出力信号線４１３に立ち上がり信号を
生じるに４１ＮＡＮＤゲートの入力信号線４１１．４１
２の一方に立ち下がり信号を５丸他方を１に制御する力
＼　あるいｌ＆ＮＡＮＤゲートの入力信号線４１１．４
１２の両方に立ち下がり信号を与えるればよし１ ここで（よ　一つのゲートに複数の立ち上がり信号また
は立ち下がり信号が与えられる可能性は低いものとＬ　
　ＮＡＮＤゲートの出力信号線４１３のＰ可制御費ＣＰ
（４１３）ｌ友　ＮＡＮＤゲートの入力信号線４１１の
１可制御費ＣＩ（４１１）と、ＮＡＮＤゲートの入力信
号線４１２のＮ可制御費ＣＮ　（４１２）との和と、Ｎ
ＡＮＤゲートの入力信号線４１１のＮ可制御費ＣＮ　（
４１１）と、ＮＡＮＤゲートの入力信号線４１２の１可
制御費Ｃ１（４１２）との机　のうち大きくない方と等
しい値とすも ＮＡＮＤゲートの出力信号線４１３のＮ可制御費ＣＮ　
（４１３）について転 ４１４の式に示したように　Ｐ可制御費と同様に求める
ことができも 第４図（ｃ）ζよ　分岐点でのＯ可制御費、　１可制＠
ｔ　　Ｐ可制御ｇＬ　Ｎ可制御費を計算する方法を示し
た図であ、４４２１ｉ＆　　分岐元の信号風４２２〜４
２５は分岐先信号線　４２６〜４２９？、Ｌ　　分岐先
信号線のＯ可制御費、　１可制御費、Ｐ可制御費、Ｎ可
制御費を計算する際に用いム　再収れんのペナルティを
説明した式である。４３０（よ　分岐先信号線４２２の
Ｏ可制御覧　１可制御覧　Ｐ可制御費、Ｎ可制御費を計
算する計算式である。

一般に　検査系列生成を困難にしている大きな原因は　
再収れん分岐であることが知られている。

異なる再収れん経路にそって値を割り当てる場合に　再
収れん点への値の割当と、再収れん分岐点への値の割当
とが矛盾を生じることにより、検査系列生成が困難にな
るというわけである。

そのことを反映するために　再収れんのペナルティを導
入し　分岐先の信号線には分岐元の信号線より大きな可
制御費を割り当てる。分岐先信号線４２２から到達可能
な外部出力を、４２６の式の左の［］内に示している。

この例でζよ　分岐先信号線４２２から到達可能な外部
出力（ｉＰＯｌ、ＰＯ４、ＰＯ５の３つである。同じ分
岐元信号線から分岐している異なる分岐元信号線力交　
同じ外部出力へ到達可能である場合に　再収れんが生じ
る。再収れん経路の数が大きいものほど検査系列生成が
困難であると考えられるの玄　分岐先信号線から到達可
能な外部出力のう板　その外部出力に到達できる他の分
岐先信号線の数が最大のものについて、他の分岐先信号
線の数を、分岐先信号線の可制御費のペナルティとして
与えも　第４図（ｃ）の例で４１　　分岐先信号線４２
２から到達できる外部出力Ｐ○１、　ＰＯ４、ＰＯ５の
うｉＰＯｌに到達可能な他の分岐先信号線は４２３．４
２５の二つであり、ＰＯ４に到達可能な他の分岐先信号
線は４２５の一つであり、ＰＯ５に到達可能な他の分岐
先信号線は４２３の一つであも　従って分岐先信号線４
２２の再収れんのペナルティｐ（４２２）は２となる。

他の分岐信号線４２３．４２４、４２５の再収れんのペ
ナルティも全く同様に　それぞれｐ　（４２３）＝２、
ｐ（４２４）＝０、　ｐ（４２５）＝２と計算できる。

分岐先信号線４２２のＯ可制御費Ｃ０（４２２）ｉＬ４
３０の計算式に示すように　分岐元信号線４２１の０可
制御費Ｃｏ（４２１）に　再収れんのペナルティｐ（４
２２）を加えたものとする。

分岐先信号線４２２の１可制御費ＣＩ（４２２）、Ｐ可
制御費ＣＰ（４２２）、Ｎ可制御費ＣＮ　（４２２）に
ついても、　計算式４３０により、　０可制御費と同様
に計算することができる。

第４図（ｄ）ｉ；ｔ、　　記憶素子の出力信号線の０可
制御費、　１可制御徴　Ｐ可制御費、Ｎ可制御費を求め
る方法を示した図であも　４３１はＤフリップフロッズ
　４３２はＤフリップフロップ４３１のデータ入力信号
３４３３ＧｉＤフリツプフロツプ４３１の制御入力信号
線　４３４はＤフリップフロップ４３１の出力信号線で
ある。４３５４１Ｄフリツプフロツプの出力信号線の０
可制御費、１可制御費、Ｐ可制御費、Ｎ可制御費を求め
る計算式である。

Ｄフリップフロップ４３１の出力信号線４３４の出力を
Ｏに制御するに＋ｉ　　Ｄフリップフロップ４３１の入
力信号線４３２に０を設定ＬＤフリップフロップ４３１
の制御入力信号線４３３に立ち上がり信号を発生すれば
よ賎　従って、Ｄフリップフロップ４３１の出力信号線
４３４のＯ可制御費Ｃ０（４３４）ｉＬ　Ｄフリップフ
ロップ４３１のデータ入力信号線４３２の０可制御費Ｃ
ｏ（４３２）に　Ｄフリップフロップ４３１の制御入力
信号線４３３のＰ可制御費ＣＰ（４３３）を加えたもの
となる。

同様にＤフリップフロップ４３１の出力信号線４３４（
７）１可制御費Ｃ１（４３４）ｉＬ　　Ｄフリップフロ
ップ４３１のデータ入力信号線４３２の１可制御費ＣＩ
（４３２）に　Ｄフリップフロップ４３１の制御入力信
号線４３３のＰ可制御費ＣＰ（４３３）を加えたものと
なる。

記憶素子の出力側に立ち上がり信号または立ち下がり信
号を設定するにｆ上０．　１を独立に設定することがで
きるだけでなく、順序の制御まで行なう必要があるた＆
Ｐ可制御費、Ｎ可制御費として、　０可制御費と１可制
御費の和に記憶素子のペナルティを加算したものを用い
る。記憶素子のペナルティとして、特定のものを用いれ
ばよいカミここでは　１を用いる。

第４図（ｅ）！＆　　記憶素子のペナルティとし、て１
を加えることを説明する回路図であも　第４図（ｅ）ｉ
ＲＳラッチを表しており、　４４１．４４２は大息　４
４５は出力である。回路中に（よ分岐元信号線４４３か
ら分岐している分岐先信号線４４４と４４５があり、４
４５にＯと１を発生させて、立ち上がりまたは立ち下が
り信号をつくるときには　二つ目の信号が分岐先信号線
４４５に出るときに（よ　一つ目の信号が分岐先信号線
４４５に影響するた＆４４５＋ｉ　　再収れん経路上に
あると考えることができる。従って、記憶素子の出力の
Ｐ可制御費およびＮ可制御費を求めるときに限り、記憶
素子のペナルティとして１を加算する。

第４図（ｆｌｌ；ＬＰ可制御費、Ｎ可制御費を用いる検
査系列生１ｉ４０３を説明するために用いる回路図であ
る。４５１はＤフリップフロップ、　４５２〜４６０は
信号線である。第４図（ｇ）ｌ＆　　第４図（ｆ）の回
路の各信号線の０可制御費（ＣＯ）１可制御費（ＣＩ）
、Ｐ可制御費（ＣＰ）、Ｎ可制御費（ＣＮ）を示した表
であも　表かられかるようｔ、；４５７で（よ　０可制
御費と１可制御費の和よりＰ可制御費、Ｎ可制御費の方
が大きくなっている。これ４表　４５７の入力側に記憶
素子があり、立ち上がり信号、立ち下がり信号を発生さ
せることが困難であることを意味している。

以下、従来例で＋ｉ　　実際には立ち上がり信号を発生
させることが困難である４５７に立ち上がり信号を割り
当てる力交　本実施例の方法によりと、そのような割当
が行われない例を示す。

信号線４６０に立ち上がり信号を発生させることにより
、信号線４５２にある故障の影響を、信号線４５３に伝
搬させる場合を考えてみる。信号線４６０に立ち上がり
信号を発生するには、　信号線４５８を立ち下がり信号
に　信号線４５９を１に制御すれ力＼　あるい（よ　信
号線４５８をｌに信号線４５９を立ち下がり信号に制御
すればよ賎前者で（上　費用はＣＮ　（４５８）＋ＣＩ
　　（４５９）＝２８で、後者ではＣＩ　　（４５，８
）　＋ＣＮ　（４５９）＝２７であるので、後者を選択
する。さらに信号線４５８を１にするために　信号線４
５４．４５５のうちＯ可制御費が安いものを選Ｊ！ｏ　
　この場合両方とも５であるので、どちらでもよいた△
信号線４５４を０に制御する。また　信号線４５９に立
ち下がり信号を発生するため＋ＱＣＰ（４５６）＋Ｃ１
（４５７）とＣ１（４５６）＋ＣＰ（４５７）を比較す
る。前者の方が費用が少ないので、　４５６を立ち上が
り信号に　信号線４５７を１に制御すも 一方、従来の０可制御費と１可制御費のみを用いる方法
で（よ　信号線４６０をＯに制御するために　信号線４
５４、４５７を０に制御し　信号線４６０を１に制御す
るために　４５６、４５７を１に制御する。従って本発
明の場合と異なり、Ｐ可制御費の高い４５７を立ち上が
り信号に制御しようとしている。

以上のように　本発明によれば　より精度の高い可検査
性尺度を用いているた△　効率のよい検査系列生成を行
うことができる。

（実施例５） 実施例５の検査系列生成方法ζ表　立ち上がり信俵　立
ち下がり信号を生じる困難さを表すＰ可制御費、Ｎ可制
御費を用いて可観測費を計算することを特徴とする検査
系列生成方法である。

第５図（ａ）ζよ　実施例５の検査系列生成方法を示す
フローチャートである。第５図（ｂ）１．ｔ。

Ｐ可制御ＵＮ可制御費を用いて可観測費を求める５０３
の処理を説明する図である。第５図（ｃ）（よ　Ｐ可制
御費、Ｎ可制御費を用いて計算した可観測費を用いる検
査系列生成５０４を説明する図回路である。第５図（ｄ
）ｉ；ｔ、　　第５図（Ｃ）の各信号線のＯ可制御費、
　ｌ可制御費、Ｐ可制御費、Ｎ可制御覧　可観測費を示
した表である。

以下、第５図（ａ）〜（ｄ）を用いて実施例５の検査系
列生成方法を説明する。５０１で処理を開始り、　　５
０２の処理でＩｔ　　ｏ可制御費、　１可制御費、Ｐ可
制御費、Ｎ可制御費を求める。その内容は　実施例４の
４０２と同じである。５０３の処理でζよ　０可制御覧
　１可制御費、Ｐ可制御費、Ｎ可制御費を用いて可観測
費を求める。５０４の処理でＩｔ　　Ｏ可制御費、　１
可制御費、Ｐ可制御費、Ｎ可制御覧　可観測費を用いて
検査系列生成を行なう。

第５図（ｂ）において、　５１１はＤフリップフロップ
を表している。　５１２はＤフリップフロップ５１１の
データ入力信号線　５１３はＤフリップフロップ５１１
の制御入力信号線　５１４はＤフリップフロップ５１１
の出力信号線を表している。５１５はＤフリップフロッ
プの入力信号線の可観測費を求める計算式である。デー
タ入力信号線４１２の故障の影響を観測する費用は　デ
ータ入力信号線５．１２の故障の影響を出力信号線５１
４に伝搬させる費用と、出力信号線５１４の故障の影響
を観測する費用の和で表されも　従って、５１５に示す
ようにデータ入力信号線５１２の故障の影響を、出力信
号線５１４へ伝搬させるために必要状　制御入力信号線
５１３を立ち上がり信号に制御する費爪　すなわち制御
入力信号線５１３のＰ可制御費ＣＰ（５１３）と、出力
信号線５１４の故障の影響を観測する費爪　すなわ板　
出力信号線５１４の可観測費０Ｂ（５１４）との和で与
えられる。

まＬ　　Ｄフリップフロップの制御入力信号線５１３の
故障の影響を観測する費用（よ　制御入力信号線５１３
にある故障の影響をＤフリップフロップの出力信号線５
１４へ伝搬させる費用と、出力信号線５１４にある故障
の影響を観測する費用の和となる。制御入力信号線５１
３にある故障の影響を出力信号線５１４に伝搬させるに
ｃｔ　　データ入力信号線５１２と、出力信号線５１４
に異なる値を設定すればよ賎　５１２に０を設定し５１
４に１を設定する費用［５１２に１を設定し５１４に０
を設定する費用Ｌ　ともに　ＣＯ（５１２）　＋ＣＩ　
　（５１２）　＋ＣＰ　（５１３）で表されるので、０
Ｂ（５１３）ｊよ　５１５の二つ目の式で与えられる。

第５図（ｃ）において、　５２１．５２２はＤフリップ
フロツー７’；　　５２３〜５２９は　信号線である。

第５図（ｄ）ｌ＆　　第５図（ｃ）の各信号線の可制御
費および可観測費を示した表であも　信号線５２３にあ
る故障の影響を外部出力まで伝搬させることを考えてみ
る。このときにζよ　５２４．５２５のうち可観測費の
安い５２５を選んで、伝搬させも 本発明によれば　より精度の高い可観測費を用いること
により、故障伝搬の効率を改善することができも （実施例６） 実施例６の検査系列生成方法は　記憶素子の制御入力に
故障の影響を伝搬させる際には立ち上がりまたは立ち下
がりの有無で故障の影響を表すことを特徴とする検査系
列生成方法である。

第６図（ａ）、　　（ｂ）ｆ友　実施例６の検査系列生
成方法を示すフローチャートである。第６図（ｃ）は　
実施例６の検査系列生成方法を説明するために用いる回
路図である。　６４１、６４２　＋１Ｄフリツプフロツ
プである。　６４３〜６４９１創外部入力である。　６
５０〜６５４　ｉ！　　信号線であ；６Ｑ　６５５＋よ
　外部出力である。

以下、第６図（ａ）〜（ｃ）を用いて本実施例の検査系
列生成方法を説明する。

６０１で処理を開始する。　６０２〜６０７１４゜故障
の影響が記憶素子の制御信号線にしか到達しない信号線
を同定する処理であり、これらの処理により、記憶素子
の制御信号線にしか到達できない信号線は制御信号線　
その他の信号線はデータ信号線と分類されも ６０２の処理では　未処理の信号線があるか否かを調べ
る。未処理の信号線がある場合には６０３に移り、ない
場合には６０８に移も ６０３の処理でＣヨ　　信号線Ｓを選択すも６０４の処
理で４１　　組合せ回路内で、信号線Ｓから記憶素子の
入力または外部出力へいたる経路があるかを調べる。

６０５の処理でｃｉ６０４の処理の結凰　信号線Ｓから
記憶素子の入力または外部出力へいたる経路があるかど
うかにより、経路がある場合には６０７へ移り、ない場
合には６０６へ移も６０６の処理では　信号線Ｓを制御
入力信号線とすも ６０７の処理で（友　信号線Ｓをデータ入力信号線とす
る。

第６図（ｃ）の回路で（よ　６０２〜６０７の処理によ
り、信号線６４３、６４４、６４７、６４８、６５０、
６５３、６５５がデータ信号線となり、信号線６４５、
６４６、６４９、６５１．６５２、６５４が制御信号線
となる。

６０８から６１１の処理では　各故障についての検査系
列生成を行なう。

６０８の処理で（よ　未処理の故障がないか調べる。

未処理の故障がある場合にｔＬ６０９に移り、ない場合
に＋；！、６１２へ移り、すべての処理を終了する。

６０９の処理では　未処理の故障ｆを選択すも６１０の
処理でζよ　故障伝搬経路活性化のための検査系列生成
を行なう。

６１１の処理で（よ　状態初期化のための検査系列生成
を行なう。

第６図（ｂ）１よ　故障伝搬経路活性化のための検査系
列生成６１０を説明するフローチャートである。

６２１で処理を開始すも　６２２の処理で（よ故障箇所
か転　外部出力にいたる故障伝搬経路を選択する。第６
図（Ｃ）の回路で（よ　信号線６４３、６５０、６５２
、６５４、６５５が故障伝搬経路として選択されも ６２３〜６２７の処理で、伝搬経路上の各信号線に　デ
ータ信号線には０、１の違いで故障の影響を表す信号を
、制御信号線には立ち上がりまたは立ち下がりの有無で
故障の影響を表す信号を割り当て、未正当化信号線とす
も ６２３の処理でζ上　故障伝搬経路ｐ上に未処理の故障
があるか否かを調べる。未処理の信号線がある場合は　
６２４へ移り、ない場合には６２８へ移る。

６２４の処理で（よ　故障伝搬経路ｐ上の信号線Ｓを選
択する。６２５で（よ　信号線Ｓがデータ信号線である
力＼　制御信号線であるかを調べる。信号線Ｓカミ　デ
ータ信号線である場合には　６２７へ移り、制御信号線
である場合には６２６へ移も６２６の処理で（上　信号
線Ｓに　立ち上がりまたは立ち下がりの有無で故障の影
響を表す信号を割当て、信号線Ｓを未正当化信号線とす
る。

６２７の処理で（友　信号線Ｓに　０、１の値の違いで
故障の影響を表す信号を割当て、信号線Ｓを未正当化信
号線とする。

６２３〜６２７の処理で、故障伝搬経路上の信号線６４
３、６５０、６５５に（よ　０．　１の値の違いで、故
障の影響を表す信号が割り当てられ信号線６５２．６５
４に（よ　立ち上がり信号の有無で故障の影響を表す信
号が割り当てられる。例え＋戴　６５６が１縮退故障で
あるとすると、　６４３に（よ　正常時に０、故障時に
１という信号カミ６５０には正常時に１、故障時にＯと
いう信号カミ６５２に（ｉ　　正常時に立ち下がり、故
障時には０という信号カミ　６５４には正常時に立ち上
がり、故障時にはｌという信号カミ　６５５には正常時
に１、故障時に０となる信号力東　それぞれ割り当てら
れる。

６２８の処理でζ友　故障伝搬経路活性化のための検査
系列生成を行なう。第６図（Ｃ）の回路で（よ　以下の
ようにして故障伝搬経路が活性化される。ただり、　　
ｌ−ｖ　（ｔ）　ｉ戴　時刻ｔにおいて、信号線Ｉに　
値Ｖが割り当てられることを意味する。値Ｖを表すにζ
ヨＯ１１、Ｐ（立ち上がり）、Ｎ（立ち下がり）の４種
類を用１．Ｘ、故障の影響を表すに（よ　正常時の値と
、故障時の値を／で区切って表す。例えば　正常時に１
、故障時に０という故障の影響を表すにば　１１０を用
いる。

６５５−１１０　　（０）を正当化するために６５４−
Ｐ／１　　（０） ６５５−０（−１） ６５３−１　　（−１） ６５４−Ｐ／１　　（０）を正当化するために６５２−
Ｎ１０　　（０） ６４９−１　　（０）［外部入カコ ６５２−Ｎ１０　　（０）を正当化するために。

６５１−Ｐ　（０） ６５２−１１０　　（−１） ６５０−０　（−１） ６５１−Ｐ（０）を正当化するために ６４５−Ｎ（０）［外部入力］ ６４６−１　　（０）［外部入力］ ６５２−１１０　（−１）を正当化するために６５１−
Ｐ（−１） ６５０−１１０　（−２） ６５１−Ｐ（−１）を正当化するために６４５−Ｎ（−
１）［外部入力］ ６４６−１　　（−１）［外部入力］ ６５０−０（−１）を正当化するために６４３−１　　
（−１）［外部入力］ ６４４−１　　（−１）［外部入力］ ６５３−１　　（−１）を正当化するために６４７−０
　　（−１）［外部入力］ ６５５−０　　（−１）を正当化するために６５４−１
　　（−１） ６５５−０　　（−２） ６５４−１　　（−１）を正当化するために６４９−０
　　（−１） ６５０−１１０　　（−２）を正当化するために６４３
−０　（−２）［外部入力］ ４ ６　５　５−０ ５ ５ ５４−Ｐ ５ ４ ５２−Ｎ ５ ５ ５ ５１−Ｐ ４ ４ ６　５　０−０ ４ ４ ５２−１ ５ ５ ４−１（−２）［外部入力］ （−２）を正当化するために ４−Ｐ　（−２） ３−０　（−３） （−２）を正当化するために ２−Ｎ　（−２） ９−１　　（−２） （−２）を正当化するために １−Ｐ　（−２） ２−１　　（−３） ０−０　　（−３） （−２）を正当化するために ５−Ｎ　（−２）［外部穴カコ ６−１（−２）［外部入力］ （−３）を正当化するために ３−１（−３）［外部入力］ ４−１　　（−３）［外部入力］ （−３）を正当化するために １−Ｐ　（−３） ０−１　　（−４） ６５１−Ｐ（−３）を正当化するために６４５−Ｎ　（
−３）　　［外部穴カコ６４６−１　　（−３）［外部
入力］ ６５０−１　　（−４）を正当化するために６４４−０
　（−４）［外部入力］ ６２９の処理で（友　状態初期化のための検査系列生成
を行なう。第６図（Ｃ）の回路で（よ　伝搬経路活性化
の処理が終了した時点で、未正当化信号線は残っていな
いので、状態初期化は必要なｌ、Ｘ。

この方法により、組合せ回路の制御入力だけに立ち上が
りまたは立ち下がりの有無で表される故障の影響を割り
当てることができるたべ　従来二つ以上のタイムフレー
ムを同時に考慮する必要のあった記憶素子の制御入力に
故障の影響が入る場合を、一つのタイムフレームで表現
でき、メモリ量、計算時間の両面で有利となる。

（実施例７） 実施例７の検査系列生成方法（よ　前処理で記憶素子の
制御入力の動作を調べておき、これに従って値の割当を
行なう、検査系列生成方法である。

第７図（ａ）、　（ｂ）ｆ；ｔ、、　　実施例７の検査
系列生成方法を示すフローチャートである。第７図（ｃ
）Ｇ；ｔ、、　　実施例７の検査系列生成方法を説明す
るために用いる回路図であも　第７図（Ｃ）において、
　７４１、７４２はＤフリップフロップである。

７４３、７４４はＴフリップフロップである。　７４５
〜７４７は外部入力であも　７４８〜７５２は信号線で
ある。　７５３は外部出力である。

以下、第７図（ａ）〜（Ｃ）を用いて、本実施例の検査
系列生成方法を説明する。

７０２〜７０６の処理で、各記憶素子の制御入力につい
て、外部入力にイベントを与えることにより周期的なイ
ベントが発生できるかどうかを調べ　その結果を記憶し
ている。その後７０７〜７０９の処理で、各故障につい
ての検査系列生成を行なう。

７０１で処理を開始する。７０２の処理で（よ未処理の
記憶素子の制御入力があるか否かを調べる。未処理の記
憶素子の制御入力がある場合は７０３へ移る。未処理の
記憶素子の制御入力がない場合には７０７の処理に移る
。

７０３の処理で（友　記憶素子の制御入力Ｃを選択する
。例えば　第７図（ｃ）でｉ；（７４９が選択されたと
する。

７０４の処理でｃ友　　外部入力にイベントを与えて、
　Ｃに周期的なイベントを発生できるか調べる。

第７図（Ｃ）でＪｊ７４７にリセット信号を加えた後、
　７４６に周期２で、周期内の相対時刻が０の立ち上が
り信号、すなわ板　偶数時刻に立ち上がるクロック信号
を入れると、７４９に（よ　周期８で、周期内の相対時
刻が４の立ち下がり信残すなわ杖　時刻を８で割った余
りが４となる時刻に立ち下がる信号を発生できることが
わかる。

７０５の処理で７１７０４の処理で発生できたかどうか
により、発生できた場合には７０６に移り、発生できな
かった場合には７０２に移る。第７図（Ｃ）で（よ　発
生できたので７０６へ移る。

７０６の処理でＬＬ、　　外部入力のイベントとＣの周
期的なイベントの関係を記憶する。第７図（ｃ）で（友
　７４７にリセット信号を加えた後７４６に周期２、周
期内の相対時刻０で立ち上がる信号を与えれば７４９に
　周期８、周期内の相対時刻４で立ち下がる信号が発生
でき衣　ということを記憶する。

７０６で情報を記憶する場所は　検査系列生成で呼び出
せるところな板　どこでもよく、例えば計算機の主記憶
上に記憶する。次に未処理の記憶素子の制御入力がある
ので、　７０３に移も７０３の処理型　記憶素子の制御
入力信号線７４６が選択されたときｌ；Ｌ７４６は外部
入力でもあるの玄　７０４の処理で、外部入力信号線７
４６には自由に周期イベントが発生できることがわかる
。従って、７０５の処理で４１７０６に進む。

このとき、　７４９に周期的なイベントを発生させるた
めに　７４６にイベントを与えればよいことが記憶され
ているので、７０６で＋１７４６に周期２で、周期内の
相対時刻が０の立ち上がり信号を与えれば　同じ信号線
である７４６に　周期２で、周期内の相対時刻がＯの立
ち上がり信号が発生でき衣　ということを記憶する。次
に未処理の記憶素子の制御入力がないの玄　７０７へ移
る。

７０７の処理で（よ　未処理の故障があるかどうかを調
べる。未処理の故障かあ、る場合には７０８へ移り、未
処理の故障がない場合には７１０へ移り、すべての処理
を終了すも ７０８で（よ　未処理の故障ｆを選択する。例えば　第
７図（Ｃ）で（上　信号線７５１の０縮退故障７５５が
選択されたとする。

７０９でｌ＆７０８で選択された故障ｆについて検査系
列生成を行なう。

第７図（ｂ）ｉ！　　各故障についての検査系列生成を
詳細に説明したフローチャートである。

７２１で処理を開始する。７２２の処理で（よ故障箇所
から外部出力への故障伝搬経路を選択し故障の影響を経
路上の信号線に割り当てる。第７図（Ｃ）で（友　伝搬
経路を７５１．７５２．７５３とし　それぞれに　正常
時に１、故障時に０となる故障の影響を割り当てる。割
り当てられた故障の影響は正当化されていないので、　
７５１、７５２、７５３が未正当化信号線となる。

７２３の処理で（よ　故障の影響が外部出力へ到達する
時刻を現在時刻としている。

第７図（ｃ）で（上　例えば現在時刻をＯとする。

その後現在時刻を戻しなが転　未正当化信号線がなくな
るまで７２４〜７３４の処理を行なう。

７２４の処理で（よ　未正当化信号線があるかどうかを
調べる。未正当化信号線がある場合には７２５に移り、
ない場合には７３５に移り、検査系列生成を終了すん ７２５の処理でＧヨ　　現在時刻のタイムフレームで、
未正当化信号線を正当化することにより、故障伝搬ある
いは状態初期化を行なう。第７図（Ｃ）でｌ；Ｌ７５３
Ｌｔ、、　　他の信号線に値を割り当てることなく、Ｄ
フリップフロップの７４２の状態を、外部出力に伝える
ことができるので、　７５３を故障の影響が通過する時
刻においては伝搬経路は活性化されていも ７２６で（よ　記憶素子の出力の状態を正当化するため
に記憶素子の入出力に割り当てる値を調べる。第７図（
ｃ）でｔｉ７５３の状態を正当化するために　割り当て
るべき値を調べる。その結果７５２に故障の影響を設定
し　７４９に立ち下がり信号を割り当てればよいことが
わかる。

７２７の処理で（瓜　制御入力に割当があるかないかを
調べも　制御入力に割当がある場合に（よ７２８に移り
、ない場合には　７２９に移る。第７図（Ｃ）では　記
憶素子の制御入カフ４９に割当が要求されているので、
　７２８に移る。

７２８の処理で（よ　制御入力に　前処理で周期的なイ
ベントを発生させる方法が得られているかどうかを調べ
る。そのような情報がある場合に（よ７３０に移り、な
い場合にｌ友　７２９に移る。第７図（ｃ）で（よ　前
処理で得られた情報があるので、　７３０へ移る。

７２９の処理で４＆　　回路情報に従って、従来方法に
より、イベントを割り当てる。

７３０の処理では　前処理の情報に従いイベントを割り
当てる。第７図（Ｃ）でζ戴　７４７にリセット信号を
加えた後、７４６に周期２、周期内の相対時刻Ｏの立ち
上がり信号を与えると、　７４９に周期８、周期内の相
対時刻４の立ち下がり信号を割り当てることができるこ
とがわかっているので、　７４９に立ち下がり信号を与
える。

また　このことを正当化するために　以降の時刻におい
て４；３７２５の処理で、　７４６に　時刻０、−２、
−４に立ち上がり信号−１、−３に立ち下がり信号を４
丸　時刻−５以前の任意の時刻に７４７をＯにし　それ
より前の時刻に７４７を１にするものとすも ７３１の処理でζよ　記憶素子の状態が正当化されたか
どうかを７３２で調べも　正当化されている場合には７
３４に移り、正当化されていない場合には７３３へ移も
　第７図（ｃ）で！戴　７５３の故障の影響ｃｔ　　正
当化されているので、　７３４に移る。

７３３の処理でζよ　パックトラックを行った後、７３
１に移る。

７３４の処理では　時刻をひとつ戻Ｌ　７２４へ移る。

第７図（ｃ）で（よ　時刻を−１として、７２４へ移も 第７図（Ｃ）でζよ　時刻−１のタイムフレームにおい
て、信号線７５２の正当化を行なう。７２５の処理で（
よ　他の信号線に値を割り当てることなく、故障伝搬経
路７５２を活性化できる。

７２６の処理では　７４６に立ち上がり信号を割り当て
ればよいことがわかる。その後、　７２７．７２８の処
理を経て、　７３０に移る。

７３０の処理でｉ；Ｌ７４６？、、　　前処理で求めた
周期２で周期内の相対時刻が０の立ち上がり信号を与え
るという情報に従り＼　時刻−２で立ち上がり信号を割
り当てる。

その結果　７５２の故障の影響が正当化されるので、　
７３２か板　７３４へ移り、さらに時刻を一つ戻す。

時刻−３では　７２５の処理で、７４５にｌ、７５０に
１を割り当てることにより、故障伝搬経路の活性化を行
なう。

７２６の処理で、記憶素子の出カフ５０の状態を正当化
するために　７５２に値０，７４９に立ち下がり信号を
割り当てればよいと言うことがわかるので、７２７、７
２８と進へ　７３０の処理に移り、イベント時刻−８で
７４９に立ち下がり信号を割り当てる。また　このこと
を正当化するために　以降の時刻において＋１７２５の
処理で、７４６Ｉへ　時刻−８、−１０、−１２に立ち
上がり信号−９、−１１に立ち下がり信号を５丸時刻−
１３以前の任意の時刻に７４７をＯにしそれより前の時
刻に７４７を１にするものとする。

時刻−９でｉ：Ｌ７２５の処理では　他の信号線に値を
割り当てることなく、　７５２をＯにするという状態初
期化のタイムフレーム内での処理を行うことができる。

７２６でζよ　７５２のＯを正当化するために７５１を
０．７４６に立ち上がり信号を割り当てればよいことが
わかる。

その後、　７２７、７２８を経て、７３０　？、：、移
も７３０の処理では　前処理の情報に従い、　時刻−Ｉ
Ｏで立ち上がり信号を割り当ても 時刻−１１でｉ；ｉ、、７２５の処理において、　７５
１をＯにするために　７４５に０を割り当てる。

７２６では　正当化されていない記憶素子の出力はない
ので、　７２７かぺ　７２９に移る。

７２９で？＆　　割り当てるイベントがないので、なに
もせず、　７３１に移る。

７３１で（よ　正当化すべき記憶素子の出力がないので
、何もせず、　７３２か収　７３４へ移る。

時刻−１２まで進んだ後４＆　　信号線７４７のみが未
正当化信号線として残っているので、時刻−１３で（よ
　処理７２５で、７４７を０とする。

時刻−１４で（よ　処理７２５で、７４７を１とする。

以上の処理により、以下の検査系列が得られた時刻−１
４ニア４７を１ 時刻−１３ニア４７をＯ 時刻−１２＋７４６に立ち上がり 時刻−１１ニア４６に立ち下がり 時刻−１１ニア４５にＯ 時刻−１０ニア４６に立ち上がり 時刻−９ニア４６に立ち下がり 時刻−８ニア４６に立ち上がり 時刻−７ニア４６に立ち下がり 時刻−６ニア４６に立ち上がり 時刻−５ニア４６に立ち下がり 時刻−４ニア４６に立ち上がり 時刻−３ニア４６に立ち下がり 時刻−３ニア４５に１ 時刻−２ニア４６に立ち上がり 時刻−１ニア４６に立ち下がり 時刻　　０ニア４６に立ち上がり このように　本実施例の検査系列生成方法では複雑なり
ロック構造をもつ回路についても効率よく検査系列が生
皮できる。

（実施例８） 実施例８の検査系列生成方法（上　前処理で求めた樹枝
状回路の情報を利用することを特徴とする検査系列生成
方法である。

第８図（ａ）、　（ｂ）ｊ；ｌ、　　実施例８の検査系
列生成方法を示すフローチャートである。第８図（ｃ）
ｉ；ｔ、、　　実施例８の検査系列生成方法を説明する
ために用いる回路図であ＆　　８４１〜８４５は分岐信
号線　８４６、８４７は信号線　８４８は樹枝状回路で
ある。

第８図（ａ）において、　８０２〜８０６の処理で（よ
　各分岐点について、その分岐点を出力としその入力側
にある分岐先信号線　または外部人魚または疑似外部入
力を入力とし　内部に分岐点をもたない樹枝状回路を取
り出し　樹枝状回路の出力にＯｌ　１を割り当てるため
の樹枝状回路の入力の組合せを調べ　これを記憶する。

８０７〜８０９の処理で（よ　各故障について、前処理
で求めた樹枝状回路の情報を用いて検査系列を生皮する
。

順序回路の検査系列生成で（よ　故障の影響を故障箇所
から外部出力まで伝搬させるための故障伝搬経路活性化
の処理と、初期状態から故障の影響を発生できる状態ま
で遷移させるための状態初期化の処理とを行なう。

いずれにおいてｋ　まずどの信号線にどのような値を割
り当てるべきかという、初期目標を求める。初期目標を
満足する外部人魚　疑似外部入力とそこに割り当てるべ
き値の組合せを求めるために　後方追跡と呼ばれる処理
を行なう。これば初期目標から順次後方に目標を伝搬さ
せる処理である。後方追跡の結果により、外部入力また
は疑似外部入力に値の割当を行なう。外部入力または疑
似外部入力に値を割り当てた結果　矛盾が生じた場合に
はバックトラックと呼ばれる処理により、値の再割当を
行なう。

樹枝状回路の出力にＯｌ　１を割り当てるための樹枝状
回路の入力の組合せ（友　バックトラックなしで求める
ことができる。本実施例で４＆　　この結果を用いるこ
とにより、後方追跡で（よ　素子毎に目標を伝搬させる
ことなく、樹枝状回路の出力から入力への目標伝搬を行
うことができるので、処理を高速化することができも 以下、第８図（ａ、）、　（ｂ）を用いて、本実施例の
検査系列生成方法を詳細に説明すも８０１で処理を開始
す、Ｌ　　８０２の処理では未処理の分岐点がないかを
調べも　未処理の故障があった場合に１Ｌ８０３へ移り
、なくなった場合には８０７の処理へ移も ８０３の処理では　未処理の分岐点Ｓを一つ選択すも　
第８図（ｃ）で分岐信号線８４１が選択されたものとす
も 次１Ｑ８０４の処理で（よ　分岐点Ｓから入力側を調べ
　分岐点Ｓを出力とし　分岐戊　または外部大息　また
は疑似外部入力を入力とし　内部に分岐点をもたない樹
枝状回路ＦＦＲを取り出す。

第８図（Ｃ）でｌ；Ｌ８４８が取り出される。

８０５の処理で＋ｉ　　分岐点ＳをＯにするための樹枝
状回路ＦＦＲの入力の組合せを求へ　これを記憶すも　
第８図（Ｃ）では　８４１を０にするための樹枝状回路
８４８の入力の組合せとして、８４２が０，８４５がＯ
という組合せを記憶する。

８０６の処理で（よ　分岐点Ｓを１にする樹枝状回路Ｆ
ＦＲの出力の組合せを束数　これを記憶すん　第８図（
Ｃ）で＋１８４１をｌにするための樹枝状回路の入力８
４８の入力の組合せとして、８４４が１、８４５が１と
いう組合せを記憶する。

８０５、８０６の処理において、これらの情報を記憶す
る場所は　検査系列生成において呼び出せるところであ
ればどこでもよく、例えば計算機の主記憶上に記憶する
。ま？、８０５と８０６の処理は順序を入れ換えても構
わな鶏 ８０７の処理で（よ　未処理の故障がないかを調べも　
未処理の故障がある場合には８０８へ移る。

未処理の故障がなくなった場合に４ｉ８１０へ移り、す
べての処理を終了すも　８０８で（よ　未処理の故障ｆ
を選択すも　８０９の処理で（友　前処理で求めた樹枝
状回路の情報を用いて、未処理の故障ｆの検査系列を生
威すも 第８図（ｂ）ｆＬ　　前処理で求めた樹枝状回路の情報
を用いる検査系列生成８０９を示したフローチャートで
ある。

８２１で処理を開始する。８２２の処理で（よ可観測費
等の尺度を用いて故障箇所から外部出力への故障伝搬経
路を選択し　故障の影響を割り当てる。

８２３の処理で（よ　現在時刻を故障の影響が外部出力
に到達する時刻とする。

８２４で（よ　未正当化信号線がないかを調べる。

未正当化信号線がある場合には８２５へ移り、未正当化
信号線がなくなったら８３７へ移り、検査系列生成を終
了する。

８２５で（よ　現在時刻で、故障伝搬経路活性化あるい
は状態初期化を行うために　どの信号線にどのような値
を割り当てるべきかという初期目標を設定すも　故障箇
所から外部出力への故障伝搬経路がすべて正当化される
まで、故障伝搬経路活性化の処理を行なＬ＼　正当化さ
れた眞　回路の状態が初期状態に戻るまで、状態初期化
の処理を行なう。

後方追跡でζよ　複数の目標を順次後方へ伝えるために
　現在目標法　最終目標群という二つの集合を用いも　
現在目標群（上　伝搬している途中の目標を一時格納す
るものであり、最終目標群（よ値の割り当てを行なう組
合せを格納するためのものであも　８２６の処理で（友
　これらの現在目標群と最終目標群を空にする。

８２５の処理と、　８２６の処理Ｃａｔ　　どちらを先
に行ってもよｌ、％８２７の処理でｉ；１８２５の処理
で設定した初期目標を現在目標群に入れる。

次に　現在目標群が空でない阻　８２８〜８３２の処理
を繰り返す。まず、　８２８の処理で（よ現在目標群が
空でないかどうかを調べる。現在目標が空でない場合に
は８２９の処理に移る。現在目標群が空である場合にζ
よ　８３３の処理に移る。

８２９の処理で＋ｉ、現在目標群かム　−っの目、Ｉ（
ｓ、ｖ）を取り出す。ここで、　Ｓは目標としている信
号＠　Ｖは目標としている信号線Ｓに割り当てようとし
ている値である。

８３０の処理では　目標としている信号線Ｓが分岐信号
線か否かを調べる。目標としている信号線Ｓが分岐信号
線である場合には８３１の処理に移り、分岐信号線でな
い場合には８３２の処理に移る。

８３１の処理で（友　前処理で求めた樹枝状回路の情報
に従って次の目標を求める。例えハ８４１を１にする目
標については　前処理で求めたように　８４４が１、８
４５がｌという二つの目標カミ　次の目標として得られ
る。

求められた次の目標方丈　外部入力あるいは疑似外部入
力である場合に（よ　求めた次の目標を最終目標群に入
れ　それ以外のものｃヨ　　現在目標群に入れも ８３２の処理で（よ　回路情報により、次の目標を求め
る。求められた次の目標力文　外部入力あるいは疑似外
部入力である場合には　求めた次の目標を最終目標群に
入れ　それ以外のもの（よ　現在目標群に入れる。

８３３の処理で（友　最終目標群に格納されている目標
に従い値の割当を行なう。

８３４の処理でｌ＆８３３の処理で矛盾が生じたか否か
を調べ　矛盾が生じていない場合には８３５の処理に進
水　矛盾が生じた場合には８３６の処理に移る。

８３５の処理で（よ　時刻を二つ戻Ｌ　　８２４の処理
へ移へ ８３６の処理で（′！、値の割当が不適当であったため
に矛盾を生じているので、バックトラックを行な（＼　
値の再割当する。その後８３４に移り、矛盾がなくなる
まで８３６のバックトラックを繰り返も 本実施例の方法により、各故障について検査系列生成を
行なう暇　後方追跡の度にこの前処理の結果が使えるの
で、検査系列生成の高速化が可能となる。

発明の効果 以上述べてきたように　本発明に係る検査系列生成方法
ｃ友　　従来順序回路の検査系列生成が有していた種々
の課題を解決したものであり、効率よく、故障検出率の
高い検査系列を生成するという効果をもたらせるもので
あも

【図面の簡単な説明】

第１図（ａ）は実施例１の検査系列生成方法を示すフロ
ーチャートａ　　第１図（ｂ）は実施例１で検査系列生
成の対象としている順序回路の回路＠　第１図（ｃ）は
実施例１で検査系列生成の対象としている順序回路を、
説明の便宜上　時間軸に展開した概念は　第１図（ｄ）
と第１図（ｅ）は実施例１の検査系列生成方法をす説明
するために用いる回路＠　第２図（ａ）〜（ｃ）は実施
例２の検査系列生成方法を示すフローチャーｈａ第２図
（ｄ）は疑似外部入力の分類方法を説明するために用い
る回路＠　第２図（ｅ）は実施例２の検査系列生成方法
を説明するために用いる回路は　第３図（ａ）は実施例
３の検査系列生成方法を示すフローチャートは　第３図
（ｂ）は実施例３の検査系列生成方法を説明するために
用いる回路＠　第４図（ａ）は実施例４の検査系列生成
方法を示すフローチャートは　第４図（ｂ）〜（ｅ）は
Ｐ可制御費、Ｎ可制御費を求める４０２の処理を説明す
る阻　第４図（ｆ）はＰ可制御費、Ｎ可制御費を用いる
検査系列生成４０３を説明する回路は　第４図（ｇ）は
第４図（ｆ）の回路の各信号線のＯ可制御費、　ｌ可制
御費、Ｐ可制御費、Ｎ可制御費を示した阻　第５図（ａ
）は実施例５の検査系列生成方法を示すフローチャート
阻　　第５図（ｂ）はＰ可制御費、Ｎ可制御費を用いて
可観測費を求める５０３の処理を説明する猛　第５図（
Ｃ）はＰ可制御費、Ｎ可制御費を用いて計算した可観測
費を用いる検査系列生成５０４を説明する諷　第５図（
ｄ）は第５図（Ｃ）の各信号線の０可制御費、　１可制
御ｇＬ　Ｐ可制御ｇＬ　Ｎ可制御費、可観測費を示した
阻　第６図（ａ）、（ｂ）は実施例６の検査系列生成方
法を示すフローチャート＆　第６図（ｃ）は実施例６の
検査系列生成方法を説明するために用いる回路＠　第７
図（ａ）、（ｂ）は実施例７の検査系列生成方法を示す
フローチャー１１　　第７図（Ｃ）は実施例７の検査系
列生成方法を説明するために用いる回路は　第８図（ａ
）、（ｂ）は実施例８の検査系列生成方法を示すフロー
チャート＆　第８図（ｃ）は実施例８の検査系列生成方
法を説明するために用いる回路は　第９図は従来の検査
系列生成方法の一つである時間軸展開法を表わす概念＠
　第１０図は従来の検査系列生成方法の一つである故障
伝搬経路決定の後状態正当化を行なう方法を示す流れは
　第１１図は従来の検査系列生成方法の一つである故障
伝搬経路決定と状態正当化を同時に時間軸に逆向きに行
なう方法を示す流れ図であも １３１〜１３３，１５１〜１５９・・・外部久方　１３
４〜１３６，１６０〜１６８・・・外部出九　１３７〜
１３９，１６９〜１７７・・・疑似外部大息　１４０〜
１４２．１７８〜１８６・・・疑似外部出、ｆｉ　　１
４３．１８７〜１８９・・・組合せ回路部分、　１４４
，１９０．１９１・・・記憶素り

Claims (8)

【特許請求の範囲】
1. （１）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 与えられた故障に対し、その故障を含む組合せ回路部分
   に着目し、疑似外部入力を外部入力、疑似外部出力を外
   部出力と見なしたとき、前記故障を検出できる組合せ回
   路の検査入力を生成する処理と、 前記組み合せ回路の検査入力を生成する処理において、
   検査入力が割り当てられているすべての疑似外部入力と
   、故障の影響が一つ以上の疑似外部出力に到達しており
   、故障の影響が外部出力には到達していない場合には、
   前記故障の影響が到達しているすべての疑似外部出力と
   を記憶する処理と、 計算時間に制限を設けて与えられた順序回路の検査系列
   を生成する処理と、 前記順序回路の検査系列を生成する処理において、計算
   時間の制限により処理を打ち切った場合に、疑似外部出
   力を記憶している場合には、記憶した疑似外部入力およ
   び疑似外部出力を出力し、疑似外部出力を記憶していな
   い場合には、記憶した疑似外部入力を出力する処理とを
   備えたことを特徴とする検査系列生成方法。
2. （２）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 疑似外部入力に仮定した故障に対し、前記故障を含む組
   合せ回路部分に着目して、第１の検査入力を生成する処
   理と、 前記疑似外部入力に仮定した故障に対する検査入力生成
   の処理の結果により、故障を仮定した疑似外部入力を分
   類し、検査入力生成に失敗した場合、前記疑似外部入力
   をクラス０とし、成功して故障の影響が外部出力へ到達
   した場合、前記疑似外部入力をクラス２とし、得られた
   前記第１の検査入力を記憶し、 故障の影響が外部出力へは到達していないが、一つ以上
   の疑似外部出力へ到達しており、故障の影響が存在する
   疑似外部出力のうちの少なくとも一つが、その故障の影
   響を他の疑似外部出力および記憶素子の出力側にある第
   １の疑似外部入力に状態を割り当てることにより、前記
   第１の疑似外部入力へ伝搬させることが可能であり、か
   つ第１の疑似外部入力がクラス２またはクラス１の疑似
   外部入力となっている場合、故障を仮定した疑似外部入
   力をクラス１の疑似外部入力とし、得られた前記第１の
   検査入力と、故障の影響を第１の疑似外部入力へ伝搬さ
   せるために割り当てた前記の疑似外部出力および第１の
   疑似外部入力の値と、第１の疑似外部入力とを記憶する
   処理と、 与えられた各故障について、組合せ回路部分に着目して
   第２の検査入力を生成する処理と、前記組合せ回路の検
   査入力生成の処理において、故障の影響が外部出力へは
   到達していないが、一つ以上の疑似外部出力へ到達して
   おり、故障の影響が存在する疑似外部出力のうちの少な
   くとも一つが、その故障の影響を他の疑似外部出力およ
   び記憶素子の出力側にある第２の疑似外部入力に状態を
   割り当てることにより記憶素子の出力側にある第２の疑
   似外部入力へ伝搬させることが可能であり、かつ第２の
   疑似外部入力がクラス２の疑似外部入力となっている場
   合に、第２の検査入力および、故障の影響を第２の疑似
   外部入力へ伝搬させるために前記の疑似外部出力および
   第２の疑似外部入力に割り当てる値と、第２の疑似外部
   入力について求めた、前記第１の検査入力が矛盾しない
   かを調べる処理と、 前記処理において矛盾が生じない場合に、故障の影響を
   第２の疑似外部入力へ伝搬させるために値を割り当てる
   べき前記疑似外部出力および第２の疑似外部入力に値の
   割り当てを行い、これらを未正当化信号線とし、 第２の疑似外部入力について前処理で求めた前記第１の
   検査入力の割り当てを行い、そのうち疑似外部入力に値
   が割り当てられているものを未正当化信号線とする処理
   と、 前記未正当化信号線を時刻の大きいものから順に正当化
   する処理とを備えたことを特徴とする検査系列生成方法
   。
3. （３）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 疑似外部入力に仮定した故障に対し、前記故障を含む組
   合せ回路部分に着目して、第１の検査入力を生成する処
   理と、 前記疑似外部入力に仮定した故障に対する検査入力生成
   の処理の結果により、故障を仮定した疑似外部入力を分
   類し、検査入力生成に失敗した場合、前記疑似外部入力
   をクラス０とし、成功して故障の影響が外部出力へ到達
   した場合、前記疑似外部入力をクラス２とし、得られた
   前記第１の検査入力を記憶し、 故障の影響が外部出力へは到達していないが、一つ以上
   の疑似外部出力へ到達しており、故障の影響が存在する
   疑似外部出力のうちの少なくとも一つが、その故障の影
   響を他の疑似外部出力および記憶素子の出力側にある第
   １の疑似外部入力に状態を割り当てることにより、前記
   第１の疑似外部入力へ伝搬させることが可能であり、か
   つ第１の疑似外部入力がクラス２またはクラス１の疑似
   外部入力となっている場合、故障を仮定した疑似外部入
   力をクラス１の疑似外部入力とし、得られた前記第１の
   検査入力と、故障の影響を第１の疑似外部入力へ伝搬さ
   せるために割り当てた前記の疑似外部出力および第１の
   疑似外部入力の値と、第１の疑似外部入力とを記憶する
   処理と、 与えられた各故障について、組合せ回路部分に着目して
   第２の検査入力を生成する処理と、前記組合せ回路の検
   査入力生成の処理において、故障の影響が外部出力へは
   到達していないが、一つ以上の疑似外部出力へ到達して
   おり、故障の影響が存在する疑似外部出力のうちの少な
   くとも一つが、その故障の影響を他の疑似外部出力およ
   び記憶素子の出力側にある第２の疑似外部入力に状態を
   割り当てることにより記憶素子の出力側にある第２の疑
   似外部入力へ伝搬させることが可能であり、かつ第１の
   疑似外部入力がクラス１またはクラス２の疑似外部入力
   となっている場合に、第２の検査入力および、故障の影
   響を第２の疑似外部入力へ伝搬させるために前記の疑似
   外部出力および第２の疑似外部入力に割り当てる値と、
   第２の疑似外部入力について求めた、前記第１の検査入
   力が矛盾しないかを調べる処理と、 前記処理において矛盾が生じない場合に、値の割当を一
   時格納する集合を空にする処理と、故障の影響を第２の
   疑似外部入力へ伝搬させるために、前記疑似外部出力お
   よび第２の疑似外部入力に割り当てるべき値と、第２の
   疑似外部入力について前処理で求めた前記第１の検査入
   力とを前記の集合に加える処理と、 第２の疑似外部入力がクラス２である場合、前記集合に
   格納されている値の割当を行ない、外部入力以外の信号
   線に割当があったものを未正当化信号線とする処理と、 第２の疑似外部入力がクラス１である場合、第２の疑似
   外部入力について前記第１の検査入力を生成する処理に
   おいて記憶した、故障の影響を第１の疑似外部入力へ伝
   搬させるために割り当てた、疑似外部出力および前記第
   １の疑似外部入力の値と、第２の疑似外部入力について
   もとめた前記第１の検査入力とを、前記集合に加え、第
   １の疑似外部入力についても、第２の疑似外部入力につ
   いて行った処理と同じことを行なう処理と、 前記未正当化信号線を時刻の大きいものから順に正当化
   する処理とを備えたことを特徴とする検査系列生成方法
   。
4. （４）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 検査系列生成の前処理として、回路の構造に基づき、回
   路内の各信号線について、その信号線の状態を０に制御
   する困難さを表す０可制御費、その信号線の状態を１に
   制御する困難さを表す１可制御費、その信号線の状態を
   ０から１へ変化させるように制御する困難さをＰ可制御
   費、その信号線の状態を１から０へ変化させるように制
   御する困難さを表すＮ可制御費を計算する処理と、与え
   られた各故障について、回路内部のある信号線の状態を
   設定するために、その信号線の入力側にある一つ以上の
   信号線に、値を設定する場合に、入力側の信号線と割り
   当てるべき値の組合せの選択に自由度があれば、前記４
   種類の可制御費に基づき、期待される値設定の困難さが
   最も小さい組合せを選択する検査系列生成の処理とを備
   えたことを特徴とする検査系列生成方法。
5. （５）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 検査系列生成の前処理として、回路の構造に基づき、回
   路内の各信号線について、その信号線の状態を０に制御
   する困難さを表す０可制御費、その信号線の状態を１に
   制御する困難さを表す１可制御費、その信号線の状態を
   ０から１へ変化させるように制御する困難さをＰ可制御
   費、その信号線の状態を１から０へ変化させるように制
   御する困難さを表すＮ可制御費を計算する処理と、前記
   ４種類の可制御費に基づき、回路内の各信号線について
   、その信号線の状態を外部出力で観測する困難さを表す
   可観測費を計算する処理と、与えられた各故障について
   、故障伝搬経路を選択する場合に、経路の選択に自由度
   がある場合、前記可観測費に基づき、期待される観測の
   困難さが最も小さい経路を選択する検査系列生成の処理
   とを備えたことを特徴とする検査系列生成方法。
6. （６）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 組合せ回路の内部で、外部出力または記憶素子のデータ
   入力にいたる経路が存在する信号線をデータ入力信号線
   として記憶し、その他の信号線を制御信号線として記憶
   する処理と、 与えられた故障について、故障伝搬経路を求める処理と
   、 データ信号線については、故障の影響として、正常時に
   １で故障時に０となる組合せか、あるいは正常時に０で
   故障時に１となる組合せを用い、制御信号線については
   、故障の影響として、正常時に立ち上がりまたは立ち下
   がりがあり、故障時には立ち上がりおよび立ち下がりが
   ない組合せか、あるいは正常時に立ち上がりおよび立ち
   下がりがなく、故障時に立ち上がりまたは立ち下がりが
   ある組合せを用いて、故障伝搬経路上に値を割り当て、
   外部入力以外に割当があった信号線を未正当化信号線と
   する処理と、 前記未正当化信号線を時刻の大きなものから順に正当化
   する処理とを備えたことを特徴とする検査系列生成方法
   。
7. （７）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 外部入力にイベントを与えることにより回路内の各記憶
   素子の制御入力に周期的なイベントを発生させることが
   できるか否かを調べる処理と、前記処理において周期的
   なイベントを発生させることが可能であることが判明し
   た場合、前記外部入力のイベントと、前記制御入力に発
   生する周期イベントとを関連付けて記憶する処理と、前
   記記憶素子の制御入力に値を割り当てる際に、前記外部
   入力のイベントと、前記制御入力に発生する周期イベン
   トとを関連付けて記憶する処理で記憶した情報に従い、
   値の割当を行なう処理とを備えたことを特徴とする検査
   系列生成方法。
8. （８）順序回路中のある故障についての検査入力系列を
   求める際に、記憶素子の入力を疑似外部出力とし、記憶
   素子の出力を疑似外部入力とし、記憶素子の入力側から
   出力側へ信号が伝搬するときは、出力側に入力側より大
   きな時刻を割り当て、組合せ回路部分の内部を信号が伝
   搬するときは、同じ時刻を割り当てることを特徴とする
   検査系列生成方法において、 各分岐点について、その分岐点を出力とし、内部に分岐
   点をもたない樹枝状部分回路に分割する処理と、 各樹枝状部分回路について、出力の信号線に０を設定す
   るために入力の信号線に割り当てるべき値とを記憶する
   処理と、 各樹枝状部分回路について、出力の信号線に１を設定す
   るために入力の信号線に割り当てるべき値とを記憶する
   処理と、 組合せ回路部分のある目標信号線に、ある目標値を設定
   するために、回路内の他の信号線または外部入力または
   疑似外部入力に値を設定する際、目標信号線から順次後
   方の信号線を調べ、信号線と割り当てるべき値の対の集
   合を後方へ伝搬させ、樹枝状回路部分の出力に到達した
   場合、前記の各樹枝状部分回路について、出力の信号線
   に０を設定するために入力の信号線に割り当てるべき値
   とを記憶する処理において、記憶した内容、または、前
   記の各樹枝状部分回路について、出力の信号線に１を設
   定するために入力の信号線に割り当てるべき値とを記憶
   する処理において、記憶した内容に従い、次の目標を求
   め、さらに後方に割り当てるべき値を調べる処理とを備
   えたことを特徴とする検査系列生成方法。