図面 (/)

技術 論理回路の原理的未検出故障判定方法及びテストパターン生成方法

出願人 株式会社日立製作所
発明者 旦代三弥子中田孝広新舎隆夫西田隆夫松嶋潤
出願日 1993年12月2日 (27年0ヶ月経過) 出願番号 1993-302799
公開日 1995年6月23日 (25年6ヶ月経過) 公開番号 1995-159499
状態 未査定
技術分野 電子回路の試験 電子回路の試験
主要キーワード 入力結線 論理値反転 故障診断方式 NOR演算 出力故障 共通論理 等価表現 不確定値
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1995年6月23日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

目的

本発明の目的は演算器系の論理回路原理未検出故障及びテストパターン生成を効率的に行うことである。

構成

演算器系の論理回路の故障診断において、故障が原理的未検出故障であるか否かを次の手順で判定する。

a)対象論理回路をいくつかの組合せ回路に分割する。

b)各分割回路一種類の基本ゲートからなる等価回路に変換する。

c)上記の等価回路を、故障を検出する入力パターンに対してのみ真値を出力する1出力回路に変換する。

d)上記の1出力回路内のEOR、ENOR論理を認識し、EOR、ENOR論理を簡約する。

e)上記の1出力回路を簡約する。

f)上記の簡約した回路において、回路の出力が1になる入力パターンが存在するか否かを判定する。

g)各分割回路における判定結果をもとに、対象故障が全体回路で原理的未検出故障であるか否かを判定する。

概要

背景

近年、論理回路の大規模化が進むにつれて、論理回路の故障診断方式の主流は、論理回路全体を対象に直接故障診断データを生成する方式から、論理回路を複数の組合せ回路に分割し、各組合せ回路ごとに部分的な故障診断データを生成し、それらを編集することにより論理回路全体の故障診断データを生成するスキャン設計方式へ移行しつつある。この移行に伴い、故障診断の対象となる回路も順序回路から組合せ回路に変わり、組合せ回路用の故障診断データ生成方式、特にその中核をなすテストパターン生成方法及び故障シミュレーション方法が重要な課題になっている。組合せ回路用のテストパターン生成方法としては、現在までにブール微分法、Dアルゴリズム、PODEM(Path Oriented DEcision Making)、FAN(FANout-oriented test generation algorithm)等が提案されており、検出率が高いテストパターンを生成できるようになっている。FANアルゴリズムに基づいたテストパターン生成方法は、「アイ・イー・イー・イートランザクションオンコンピュータ,1983年12月,NO.12,VOL.C-32,第1137−1144頁(IEEE TRANSACTIONS ON COMPUTERS,VOL.C-32,NO.12,DECEMBER1983,pp.1137-1144)」に記載されている。しかし、未検出故障に関しては、テストパターンが存在していても、それを生成できなかったのか、或いは、原理的にテストパターンが存在しないために未検出なのかが不明であることが多い。これは、テストパターン生成問題がNP完全問題であり、最悪の場合には回路規模指数オーダーの処理時間がかかるため、途中でテストパターン生成を諦めてしまうためである。このような場合、テストパターンが存在する故障に対してはテストパターンを効率良く生成し、原理的にテストパターンの存在しない故障に対しては、原理的未検出故障であると判定する方法がある。この方法については、現在までに、M.H.Schulz 等の方法が「アイ・イー・イー・イー トランザクション オン コンピュータ−エイデッドデザイン,1989年7月,NO.7,VOL.8,第811−816頁(IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN,VOL.8,NO.7,JULY 1989,pp.811-816)」に、回路の簡約手法を用いた原理的未検出故障判定方法が特開平5−5774号公報に記載されている。M.H.Schulz等の提案した方法は、SOCRATESと呼ばれるテストパターン生成システム拡張含意操作と一意活性化の機能を付加することにより、論理値が一意に決まるのに従来の含意操作等では論理値を定めることができなかった信号線に論理値を設定している。これにより、バックトラックの必要性を早期に把握でき、全入力パターンの空間における解(テストパターン)を探索する範囲を狭めることができるので、従来より効率的なテストパターン生成と原理的未検出故障の摘出が可能である。ゲート入力信号線の論理値によりそのゲートの出力信号線の論理値が一意的に定まる場合にその出力信号線にその論理値を割当てる、或いはゲートの出力信号線の論理値によりそのゲートの入力信号線の論理値が一意的に定まる場合にその入力信号線にその論理値を割当てるのが従来の含意操作である。これに対して、拡張含意操作とは、それぞれが必ずしもあるゲートの入力信号線と出力信号線という関係にない2組の信号線に対して、一方の組の信号線の論理値により、もう一方の組の信号線の論理値が一意的に定まる場合にその論理値を割当てる操作のことである。図2は、拡張含意操作の一例を示す図である。図2において、1m及び2mはANDゲート、3m、4m、5m、及び6mは信号線を表す。図2(a)において、信号線4mの論理値は0になっている。この場合、信号線5m及び6mの論理値は一意に定まらないが、ANDゲート1mと2mは同じ論理表現しているため、信号線3mと4mは常に同じ論理値をとらなければならない。したがって、図2(b)に示すように信号線3mの論理値に0を割当てる。一意活性化とは、故障信号が必ず通るゲートを全て活性化することである。すなわち、故障信号が必ず通るゲートの入力信号線の内、故障信号の絶対到達しない入力信号線に信号値を割当てる場合、そのゲートがANDまたはNANDならば1を、ORまたはNORならば0を割当てる。図3は、一意活性化の一例を示す図である。図3において、1n、2n、6n、7n、及び8nはANDゲート、3n、4n、及び5nはORゲート、9nは仮定故障箇所、10n、11n、及び12nは信号線を表す。図3(a)において、9nの論理値は0/1(正常回路では0、故障回路では1)である。テストパターンを生成するためには、この故障信号を出力エッジまで伝播しなければならない。図3(a)の回路ではゲート2n、5n、及び8nは故障信号が出力エッジまで伝播するために必ず通らなければならないゲートである。図3(b)は信号線10n、12nに1を、信号線11nに0を割当て、ゲート2n、5n、及び8nを活性化した状態を表す。一方、ゲート3nと4n及びゲート6nと7nは、そのいずれかのゲートを信号が通過するか現在のところ不明であるため、信号値の割当ては行わない。回路の簡約手法を用いた方法は、原理的未検出故障判定問題の問題「回路の出力は常に0か?」への変換と対象回路の簡約により原理的未検出故障判定及びテストパターン生成を困難にしている回路内の冗長性を除去することにより効率的に原理的未検出故障判定及びテストパターン生成を行う方法である。

概要

本発明の目的は演算器系の論理回路の原理的未検出故障及びテストパターン生成を効率的に行うことである。

演算器系の論理回路の故障診断において、故障が原理的未検出故障であるか否かを次の手順で判定する。

a)対象論理回路をいくつかの組合せ回路に分割する。

b)各分割回路一種類の基本ゲートからなる等価回路に変換する。

c)上記の等価回路を、故障を検出する入力パターンに対してのみ真値を出力する1出力回路に変換する。

d)上記の1出力回路内のEOR、ENOR論理を認識し、EOR、ENOR論理を簡約する。

e)上記の1出力回路を簡約する。

f)上記の簡約した回路において、回路の出力が1になる入力パターンが存在するか否かを判定する。

g)各分割回路における判定結果をもとに、対象故障が全体回路で原理的未検出故障であるか否かを判定する。

目的

上記従来技術で述べたM.H.Schulz等の方法及び回路の簡約手法を用いた方法は、テストパターン生成もしくは原理的未検出故障判定の困難な故障に対して大きな効果を持つが、演算器系の論理回路に対しては検出率向上が未だ十分でない、という問題点がある。例えば、回路の簡約手法を用いた方法では、回路をNORゲート入力エッジのみで構成する。2入力ExclusiveOR論理(以下EOR論理と略す)A+B及び3入力EOR論理A+B+CはNORゲートによりそれぞれ図4(a)及び(b)のように構成される。又、EOR論理の結合(A+B)+C及びA+(B+C)はNORゲートによりそれぞれ図4(c)及び(d)のように構成される。EOR論理の性質により(A+B)+C=A+(B+C)=A+B+Cであるが、回路の簡約手法を用いた方法では図4(b)、(c)、及び(d)のNORゲート表現が互いに等価な論理を表していることが認識できない。演算器系の論理回路にはEOR論理が多数含まれるため、EOR論理の性質に基づく回路内の情報を把握できないということは、演算器系のテストパターン生成及び原理的未検出故障判定を効率的に行えないということを意味する。本発明の目的は、このような問題点を改善し、回路内のEOR論理を認識し、EOR論理の性質に基づく回路の冗長性を統一的に把握し、冗長な部分を除去することにより、回路の簡約手法を用いた原理的未検出故障判定を効率的に行うことが可能な論理回路の原理的未検出故障判定方法及びテストパターン生成方法を提供することにある。

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

スキャン設計方式の論理回路故障診断方法において、フリップフロップ及び入出力エッジで分割して得られる組合せ回路からなる分割回路の内の対象未検出故障を含むものを全て抽出する第1のステップと、該分割回路を一種類の基本ゲートのみで構成した等価回路に変換する第2のステップと、該等価回路において該未検出故障を検出する入力パターンに対しては真値を出力し、それ以外の入力パターンに対しては値を出力する1出力回路に該等価回路を変換する第3のステップと、該1出力回路の出力が真値になる入力パターンが存在するか否かを判定する第4のステップと、各分割回路における判定結果が全て該入力パターンが存在しない場合に前記未検出故障のテストパターンが全体回路に存在しない故障であると判定する第5のステップとを備え、前記第4ステップには、前記第3ステップで得られた1出力回路においてEOR論理とENOR論理を抽出・簡約する第1のサブステップと、該第1サブステップで得られた回路内の同一論理を表す複数ゲートを1ゲートにまとめる第2のサブステップと、該第2サブステップで得られた回路において互いに独立に真値又は偽値に出力を制御できる該回路内のゲートの組であって該ゲートの組より入力側に信号線分岐点が存在するものを認識することにより該分岐点から到達可能な回路領域と該分岐点から到達不可能な回路領域の境界にある信号線を該ゲートの組より出力側更新する第3のサブステップと、該第3サブステップで得られた回路内の冗長な論理を簡約する第4のサブステップと、該第4サブステップで得られた回路で信号線の論理値割当てを試行することにより前記1出力回路の出力が真値になる入力パターンが存在するか否かを判定する第5のサブステップとを備えたことを特徴とする論理回路の原理的未検出故障判定方法

請求項2

請求項1記載の論理回路の原理的未検出故障判定方法を用いたテストパターン作成方法において、上記第4ステップにおいて該入力パターンが存在すると判定された該未検出故障に対し、値の定まった入力エッジ論理値情報からテストパターンを生成することを特徴とする論理回路のテストパターン生成方法

請求項3

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第1ステップには、未検出故障箇所を含む全ての1出力分割回路を抽出する第1のサブステップと、各該1出力分割回路について該1出力分割回路と該1出力分割回路の入力エッジと該1出力分割回路内の0縮退故障か1縮退故障の何れかが既に検出済みである出力信号線で囲まれ、該未検出故障箇所を含む1出力回路の内、回路規模が最小なものを原理的未検出故障判定に必要な関連領域として認識する第2のサブステップと、重複する関連領域を除去する第3のサブステップとを備え、有効な関連領域に限定して原理的未検出故障判定を行うことを特徴とする論理回路の原理的未検出故障判定方法。

請求項4

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第3ステップには、未検出故障箇所に故障信号をセットするような入力パターンに対しては回路の出力論理値が真値になり、それ以外の入力パターンに対しては回路の出力論理値が偽値となる回路に上記等価回路を変換する第1のサブステップと、前記未検出故障箇所に故障信号をセットし、該未検出故障箇所より最初の信号線の分岐点まで故障信号を伝播させるような入力パターンに対しては回路の出力論理値が真値になり、それ以外の入力パターンに対しては回路の出力論理値が偽値となる回路に前記第1サブステップで得られた回路を変換する第2のサブステップと、前記未検出故障箇所に故障信号をセットし、該未検出故障箇所より最初の信号線の分岐点まで故障信号を伝播させ、該分岐点より前記該等価回路の出力まで故障信号を伝播させる入力パターンに対しては回路の出力論理値が真値となり、それ以外の入力パターンに対しては回路の出力論理値が偽値となる回路に前記第2サブステップで得られた回路を変換する第3のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項5

請求項4記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップでは、未検出故障が偽値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に、論理値を反転させる1入力基本ゲートをはさん結線繋ぎ、該未検出故障信号線の結線を切り離し、前記未検出故障が真値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に結線を繋ぎ、該未検出故障信号線の結線を切り離すことを特徴とする論理回路の原理的未検出故障判定方法。

請求項6

請求項4記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップでは、未検出故障が偽値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に、論理値を反転させる1入力基本ゲートをはさんで結線を繋ぎ、該未検出故障信号線の結線を切り離し、前記未検出故障が真値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に結線を繋ぎ、該未検出故障信号線の結線を切り離し、上記第2サブステップでは、前記第1サブステップで得られた回路内の未検出故障箇所から最初の信号線の分岐点までの経路上の各基本ゲートに対して、該基本ゲートに対する入力基本ゲートであって該経路上にないものの出力に、新しく設けた出力基本ゲートを繋ぎ、該基本ゲートと該基本ゲートに対する全ての入力基本ゲートとの間の結線を切り離すことを特徴とする論理回路の原理的未検出故障判定方法。

請求項7

請求項4記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップでは、未検出故障が偽値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に、論理値を反転させる1入力基本ゲートをはさんで結線を繋ぎ、該未検出故障信号線の結線を切り離し、前記未検出故障が真値を出力値として持つ縮退故障ならば、未検出故障信号線を出力信号線として持つ基本ゲートと新しく設けた出力基本ゲートとの間に結線を繋ぎ、該未検出故障信号線の結線を切り離し、上記第2サブステップでは、前記第1サブステップで得られた回路内の未検出故障箇所から最初の信号線の分岐点までの経路上の各基本ゲートに対して、該基本ゲートに対する入力基本ゲートであって該経路上にないものの出力に、新しく設けた出力基本ゲートを繋ぎ、該基本ゲートと該基本ゲートに対する全ての入力基本ゲートとの間の結線を切り離し、上記第3サブステップでは、前記第2サブステップで得られた回路内の故障信号の伝播しうる回路領域を、未検出故障を含まない正常回路と未検出故障を含む故障回路に分離し、新たに基本ゲートで構成される2入力排他論理和を設け、該2入力排他論理和の入力と前記正常回路及び故障回路の各出力とを繋ぎ、該2入力排他論理和の出力と第1サブステップで新しく設けた出力基本ゲートとの間に、論理値を反転する1入力基本ゲートをはさんで結線を繋ぐことを特徴とする論理回路の原理的未検出故障判定方法。

請求項8

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップには、回路内のEOR論理及びENOR論理を認識してEORゲート及びENORゲート表現する第1のサブステップと、回路内のm入力EORゲートの入力ゲートにn入力EORゲートがある場合(m,n:整数)には両該ゲートを(m+n−1)入力EORゲートで置き換え、m入力EORゲートの入力ゲートにn入力ENORゲートがある場合には両該ゲートを(m+n−1)入力ENORゲートで置き換え、m入力ENORゲートの入力ゲートにn入力EORゲートがある場合には両該ゲートを(m+n−1)入力ENORゲートで置き換え、m入力ENORゲートの入力ゲートにn入力ENORゲートがある場合には両該ゲートを(m+n−1)入力EORゲートで置き換える第2のサブステップと、回路内のEORゲートの入力ゲートに1入力基本ゲートが偶数個存在する場合には該1入力基本ゲートの入力ゲート全てと該EORゲートを直接繋ぎ該1入力基本ゲートを全て削除し、EORゲートの入力ゲートに1入力基本ゲートが奇数個存在する場合には該1入力基本ゲートの入力ゲート全てと該EORゲートを直接繋ぎ該1入力基本ゲートを全て削除し該EORゲートをENORゲートに置き換え、ENORゲートの入力ゲートに1入力基本ゲートが偶数個存在する場合には該1入力基本ゲートの入力ゲート全てと該ENORゲートを直接繋ぎ該1入力基本ゲートを全て削除し、ENORゲートの入力ゲートに1入力基本ゲートが奇数個存在する場合には該1入力基本ゲートの入力ゲート全てと該ENORゲートを直接繋ぎ該1入力基本ゲートを全て削除し該ENORゲートをEORゲートに置き換える第3のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項9

請求項8記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップには、回路内の多入力基本ゲートの出力論理値を1として後方含意を行い、含意停止ゲート登録する第1のサブステップと、該第1サブステップで登録された各含意停止ゲートの出力論理値を1として後方含意を行い、含意停止ゲートを登録する第2のサブステップと、前記多入力基本ゲートの出力が該第2サブステップで登録された含意停止ゲートの出力のEOR論理もしくはENOR論理と等価であるかどうかを調べる第3のサブステップと、該第3サブステップで該多入力基本ゲートがEOR論理と等価であると判定された場合、該多入力ゲートから前記第2サブステップで登録された含意停止ゲートまでをEORゲートで置き換え、前記第3サブステップで該多入力基本ゲートがENOR論理と等価であると判定された場合、該多入力ゲートから前記第2サブステップで登録された含意停止ゲートまでをENORゲートで置き換える第4のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項10

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第3サブステップには、分岐を持つ先頭信号線に論理値0又は1をセットし、前方含意を行い、含意の止まった基本ゲートを登録する第1のサブステップと、該登録基本ゲートの入力側にある論理値Xの先頭信号線の論理値を0又は1に制御することにより、該登録基本ゲートの出力論理値を独立に0又は1に制御できるか否かを判定する第2のサブステップと、該第2サブステップにおいて該登録基本ゲートの該出力論理値を独立に0又は1に制御できると判定された場合に、前記第1サブステップにおいて論理値が0又は1に確定した信号線の結線を切り離すことにより、該先頭信号線を該登録基本ゲートより出力側に更新する第3のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項11

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第4サブステップには、上記第3サブステップで得られた回路内の多入力基本ゲートの入力側にある冗長な部分回路を簡約する第1のサブステップと、該第1サブステップで得られた回路の出力基本ゲートまでの何れの経路も偶数個の基本ゲートで構成されるような先頭信号線に対しては該先頭信号線の論理値を偽値にして前方含意を行い、論理値が0又は1に確定した信号線の結線を切り離し、前記第1サブステップで得られた回路の出力基本ゲートまでの何れの経路も奇数個の基本ゲートで構成されるような先頭信号線に対しては該先頭信号線の論理値を真値にして前方含意を行い、論理値が0又は1に確定した信号線の結線を切り離す第2のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項12

請求項12記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップには、該多入力基本ゲートの論理値を真値として後方含意を行い、後方含意の止まったところの基本ゲートを登録する第1のサブステップと、該多入力基本ゲートと該登録基本ゲートとの間の不要な論理回路を除去する第2のサブステップと、該登録基本ゲートの論理値が偽値ならば該登録基本ゲートと該多入力基本ゲートとの間に結線を繋ぎ、該登録基本ゲートの論理値が真値ならば該登録基本ゲートと該多入力基本ゲートとの間に論理値を反転する1入力基本ゲートをはさんで結線を繋ぐ第3のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項13

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第5サブステップには、上記第4サブステップで得られた回路の出力論理値に真値を設定し、含意操作を行う第1のサブステップと、該第1サブステップで生じた未正当化信号線を正当化し、正当化が成功した場合には該1出力回路の出力が真値になる入力パターンが存在すると判定し、どのように論理値を割当てても正当化ができない場合には該1出力回路の出力が真値になるような入力パターンが存在しないと判定する第2のサブステップと、該第2サブステップで該1出力回路の出力が真値になる入力パターンが存在すると判定した場合には、論理値が0又は1に定まった先頭信号線を入力エッジまで正当化する第3のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項14

請求項13記載の論理回路の原理的未検出故障判定方法において、上記第2サブステップには、含意操作による矛盾が生じない間は、未正当化信号線の有無を調べ、未正当化信号線が無ければ該1出力回路の出力が真値になる入力パターンが存在すると判定し、有れば未正当化信号線を一つ選択し、該未正当化信号線からの後方追跡と含意操作を行う第1のサブステップと、該含意操作による矛盾が生じた場合にバックトラックと含意操作を行う第2のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項15

請求項14記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップでは、未正当化信号線の有無を調べ、未正当化信号線が無ければ該1出力回路の出力が真値になる入力パターンが存在すると判定し、有れば未正当化信号線を1つ選択し、該未正当化信号線を出力信号線とするゲートを後方追跡目標ゲートとして、該未正当化信号線の論理値を目標値とし、後方追跡目標ゲートが先頭信号線を出力とするゲートになるまで、後方追跡目標ゲートを後方追跡目標ゲートの論理値未定の入力ゲートの一つに更新し、目標値を更新することを繰り返し、最終後方追跡目標ゲートの出力信号線に最終目標値を設定し、含意操作を行うことを特徴とする論理回路の原理的未検出故障判定方法。

請求項16

請求項14記載の論理回路の原理的未検出故障判定方法において、上記第2サブステップでは、上記第1サブステップの後方追跡で論理値を設定した信号線が全て既に論理値を反転済みならば、該1出力回路の出力が真値になるような入力パターンは存在しないと判定し、反転済みでなければ、論理値が未反転の信号線の内、最も最後に論理値を設定したものを選択し、該信号線よりも後に論理値を設定した信号線の論理値を全て未定に戻し、該信号線の論理値を反転し、含意操作を行うことを特徴とする論理回路の原理的未検出故障判定方法。

請求項17

請求項14記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップでは、未正当化信号線の有無を調べ、未正当化信号線が無ければ該1出力回路の出力が真値になる入力パターンが存在すると判定し、有れば未正当化信号線を一つ選択し、該未正当化信号線を出力信号線とするゲートを後方追跡目標ゲートとして、該未正当化信号線の論理値を目標値とし、後方追跡目標ゲートを後方追跡目標ゲートの論理値Xの入力ゲートの一つに更新し、目標値を更新し、後方追跡目標ゲートの出力信号線に目標値を設定し、含意操作を行うことを特徴とする論理回路の原理的未検出故障判定方法。

請求項18

請求項1記載の論理回路の原理的未検出故障判定方法において、上記第4ステップには、上記第3ステップで得られた1出力回路内の不確定入力エッジを除去することにより、該1出力回路を不確定入力エッジを含まない1出力回路に変換する第1のサブステップと、該第1サブステップで得られた回路においてEOR論理及びENOR論理を抽出・簡約する第2のサブステップと、該第2サブステップで得られた1出力回路内の同一論理を表す複数ゲートを一つのゲートにまとめる第3のサブステップと、該第3サブステップで得られた回路において互いに独立に真値又は偽値に出力を制御できる該回路内のゲートの組であってこのゲートの組より入力側に信号線の分岐点が存在するものを認識することにより該分岐点から到達可能の回路領域と該分岐点から到達不可能な回路領域の境界にある信号線を該ゲートの組より出力側に更新する第4のサブステップと、該第4サブステップで得られた回路内の冗長な論理を簡約する第5のサブステップと、該第5サブステップで得られた回路で信号線の論理値割当てを試行することにより該1出力回路の出力が真値になる入力パターンが存在するか否かを判定する第6のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

請求項19

請求項18記載の論理回路の原理的未検出故障判定方法において、上記第1サブステップには、出力先ゲートの出力値を原理的未検出故障判定に影響を与えることなく0又は1に制御可能な不確定入力エッジの出力ゲートの出力論理値の制御を行うことにより不確定入力エッジを除去する第1のサブステップと、該第1サブステップに示した制御が不可能な不確定入力エッジを、不確定入力エッジに0を入力した場合の回路と1を入力した場合の回路を合成することにより除去する第2のサブステップとを備えることを特徴とする論理回路の原理的未検出故障判定方法。

技術分野

0001

本発明は、論理回路故障診断方法に関し、特に組合せ回路からなる論理回路の原理未検出故障判定方法及びテストパターン生成方法に関する。

背景技術

0002

近年、論理回路の大規模化が進むにつれて、論理回路の故障診断方式の主流は、論理回路全体を対象に直接故障診断データを生成する方式から、論理回路を複数の組合せ回路に分割し、各組合せ回路ごとに部分的な故障診断データを生成し、それらを編集することにより論理回路全体の故障診断データを生成するスキャン設計方式へ移行しつつある。この移行に伴い、故障診断の対象となる回路も順序回路から組合せ回路に変わり、組合せ回路用の故障診断データ生成方式、特にその中核をなすテストパターン生成方法及び故障シミュレーション方法が重要な課題になっている。組合せ回路用のテストパターン生成方法としては、現在までにブール微分法、Dアルゴリズム、PODEM(Path Oriented DEcision Making)、FAN(FANout-oriented test generation algorithm)等が提案されており、検出率が高いテストパターンを生成できるようになっている。FANアルゴリズムに基づいたテストパターン生成方法は、「アイ・イー・イー・イートランザクションオンコンピュータ,1983年12月,NO.12,VOL.C-32,第1137−1144頁(IEEE TRANSACTIONS ON COMPUTERS,VOL.C-32,NO.12,DECEMBER1983,pp.1137-1144)」に記載されている。しかし、未検出故障に関しては、テストパターンが存在していても、それを生成できなかったのか、或いは、原理的にテストパターンが存在しないために未検出なのかが不明であることが多い。これは、テストパターン生成問題がNP完全問題であり、最悪の場合には回路規模指数オーダーの処理時間がかかるため、途中でテストパターン生成を諦めてしまうためである。このような場合、テストパターンが存在する故障に対してはテストパターンを効率良く生成し、原理的にテストパターンの存在しない故障に対しては、原理的未検出故障であると判定する方法がある。この方法については、現在までに、M.H.Schulz 等の方法が「アイ・イー・イー・イー トランザクション オン コンピュータ−エイデッドデザイン,1989年7月,NO.7,VOL.8,第811−816頁(IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN,VOL.8,NO.7,JULY 1989,pp.811-816)」に、回路の簡約手法を用いた原理的未検出故障判定方法が特開平5−5774号公報に記載されている。M.H.Schulz等の提案した方法は、SOCRATESと呼ばれるテストパターン生成システム拡張含意操作と一意活性化の機能を付加することにより、論理値が一意に決まるのに従来の含意操作等では論理値を定めることができなかった信号線に論理値を設定している。これにより、バックトラックの必要性を早期に把握でき、全入力パターンの空間における解(テストパターン)を探索する範囲を狭めることができるので、従来より効率的なテストパターン生成と原理的未検出故障の摘出が可能である。ゲート入力信号線の論理値によりそのゲートの出力信号線の論理値が一意的に定まる場合にその出力信号線にその論理値を割当てる、或いはゲートの出力信号線の論理値によりそのゲートの入力信号線の論理値が一意的に定まる場合にその入力信号線にその論理値を割当てるのが従来の含意操作である。これに対して、拡張含意操作とは、それぞれが必ずしもあるゲートの入力信号線と出力信号線という関係にない2組の信号線に対して、一方の組の信号線の論理値により、もう一方の組の信号線の論理値が一意的に定まる場合にその論理値を割当てる操作のことである。図2は、拡張含意操作の一例を示す図である。図2において、1m及び2mはANDゲート、3m、4m、5m、及び6mは信号線を表す。図2(a)において、信号線4mの論理値は0になっている。この場合、信号線5m及び6mの論理値は一意に定まらないが、ANDゲート1mと2mは同じ論理表現しているため、信号線3mと4mは常に同じ論理値をとらなければならない。したがって、図2(b)に示すように信号線3mの論理値に0を割当てる。一意活性化とは、故障信号が必ず通るゲートを全て活性化することである。すなわち、故障信号が必ず通るゲートの入力信号線の内、故障信号の絶対到達しない入力信号線に信号値を割当てる場合、そのゲートがANDまたはNANDならば1を、ORまたはNORならば0を割当てる。図3は、一意活性化の一例を示す図である。図3において、1n、2n、6n、7n、及び8nはANDゲート、3n、4n、及び5nはORゲート、9nは仮定故障箇所、10n、11n、及び12nは信号線を表す。図3(a)において、9nの論理値は0/1(正常回路では0、故障回路では1)である。テストパターンを生成するためには、この故障信号を出力エッジまで伝播しなければならない。図3(a)の回路ではゲート2n、5n、及び8nは故障信号が出力エッジまで伝播するために必ず通らなければならないゲートである。図3(b)は信号線10n、12nに1を、信号線11nに0を割当て、ゲート2n、5n、及び8nを活性化した状態を表す。一方、ゲート3nと4n及びゲート6nと7nは、そのいずれかのゲートを信号が通過するか現在のところ不明であるため、信号値の割当ては行わない。回路の簡約手法を用いた方法は、原理的未検出故障判定問題の問題「回路の出力は常に0か?」への変換と対象回路の簡約により原理的未検出故障判定及びテストパターン生成を困難にしている回路内の冗長性を除去することにより効率的に原理的未検出故障判定及びテストパターン生成を行う方法である。

発明が解決しようとする課題

0003

上記従来技術で述べたM.H.Schulz等の方法及び回路の簡約手法を用いた方法は、テストパターン生成もしくは原理的未検出故障判定の困難な故障に対して大きな効果を持つが、演算器系の論理回路に対しては検出率向上が未だ十分でない、という問題点がある。例えば、回路の簡約手法を用いた方法では、回路をNORゲート入力エッジのみで構成する。2入力ExclusiveOR論理(以下EOR論理と略す)A+B及び3入力EOR論理A+B+CはNORゲートによりそれぞれ図4(a)及び(b)のように構成される。又、EOR論理の結合(A+B)+C及びA+(B+C)はNORゲートによりそれぞれ図4(c)及び(d)のように構成される。EOR論理の性質により(A+B)+C=A+(B+C)=A+B+Cであるが、回路の簡約手法を用いた方法では図4(b)、(c)、及び(d)のNORゲート表現が互いに等価な論理を表していることが認識できない。演算器系の論理回路にはEOR論理が多数含まれるため、EOR論理の性質に基づく回路内の情報を把握できないということは、演算器系のテストパターン生成及び原理的未検出故障判定を効率的に行えないということを意味する。本発明の目的は、このような問題点を改善し、回路内のEOR論理を認識し、EOR論理の性質に基づく回路の冗長性を統一的に把握し、冗長な部分を除去することにより、回路の簡約手法を用いた原理的未検出故障判定を効率的に行うことが可能な論理回路の原理的未検出故障判定方法及びテストパターン生成方法を提供することにある。

課題を解決するための手段

0004

上記目的を達成するため、本発明の論理回路の原理的未検出故障判定方法及びテストパターン生成方法は、以下に述べるステップを実行することに特徴がある。すなわち、対象となる論理回路を分割した組合せ回路の内、対象となる未検出故障箇所を含むものを全て抽出する第1ステップ、各分割回路をNORゲートのみで表現した等価回路に変換する第2ステップ、第2ステップで変換された等価回路において対象未検出故障を検出する入力パターン(テストパターン)に対しては出力が1になり、それ以外の入力パターンに対しては出力が0になるような1出力回路にこの等価回路を変換する第3ステップ、および第3ステップで得られた1出力回路の出力が1になる入力パターンが存在するか否かを判定する第4ステップを実行する。特に第4ステップは、対象1出力回路内のEOR論理及びENOR論理の抽出・簡約を行う第1サブステップ、第1サブステップで得られた回路内の同一論理を表す複数ゲートを一つのゲートで置換させる第2サブステップ、第2サブステップで得られた回路において互いに独立に0又は1となる出力を制御できる回路内のゲートの組で、このゲートの組より入力側に信号線の分岐点が存在するようなものを抽出することにより、その分岐点から到達可能な回路領域とその分岐点から到達不可能な回路領域の境界にある信号線(先頭信号線)を、抽出したゲートの組より出力側更新する第3サブステップ、第3サブステップで得られた回路内の冗長な論理を簡約する第4サブステップ、第4サブステップで得られた回路で信号線の論理値割当てを試行することにより該1出力回路の出力が1になる入力パターンが存在するか否かを判定する第5サブステップからなる。さらに、各分割回路における判定の結果、何れの分割回路に対してもテストパターンが存在しなければ、その故障はテストパターンが全体回路に存在しない故障、すなわち、原理的未検出故障であると判定し、何れかの分割回路においてテストパターンが存在すれば、このテストパターンを出力する第5ステップを実行する。

0005

本発明においては、対象論理回路をいくつかの組合せ回路に分割し、各分割回路を一種類の基本ゲートからなる等価回路に変換する。次に、その等価回路を、故障を検出する入力パターンに対してのみ真値を出力する1出力回路に変換する。さらに、その1出力回路内のEOR論理及びENOR論理を認識してそれらを簡約し、得られた回路の出力が1になるような入力パターンが存在するか否かを判定する。より具体的には、対象1出力回路内のEOR論理及びENOR論理の抽出・簡約を行い、得られた回路内の同一論理を表す複数ゲートを一つのゲートで置換させ、こうして得られた回路において、互いに独立に0又は1となる出力を制御できる回路内のゲートの組で、このゲートの組より入力側に信号線の分岐点が存在するようなものを抽出することにより、その分岐点から到達可能な回路領域とその分岐点から到達不可能な回路領域の境界にある先頭信号線を、抽出したゲートの組より出力側に更新し、こうして得られた回路内の冗長な論理を簡約し、さらに、得られた回路で信号線の論理値割当てを試行することにより前記1出力回路の出力が1になる入力パターンが存在するか否かを判定する。その結果、何れの分割回路に対してもテストパターンが存在しなければ、原理的未検出故障と判定し、何れかの分割回路においてテストパターンが存在すれば、そのテストパターンを出力する。このように、回路内のEOR論理及びENOR論理を認識し、EOR論理及びENOR論理の性質に基づく回路内の冗長な論理を簡約することにより、演算器系の論理回路の原理的未検出故障判定を難しくしている回路の冗長性を統一的に捉え、且つ、冗長な回路部分を除去し、効率的に原理的未検出故障判定を行うことを可能にする。また、この判定結果を用いて容易にテストパターンを生成することができる。

0006

以下、本発明の一実施例を図面により説明する。図5は、本発明の論理回路の原理的未検出故障判定方法及びテストパターン生成方法を適用する計算機システムの構成図である。図5において、処理装置10には、本実施例の処理プログラムである原理的未検出故障判定プログラム20が格納されており、外部記憶装置には、本実施例の故障判定の対象となる論理回路データ30、回路中の故障に関する仮定故障テーブル40、45、及び出力結果であるテストパターン・データ50が格納されている。この論理回路データ30を図6に示し、出力仮定故障テーブル40、入力仮定故障テーブル45、及びテストパターン・データ50の構成をそれぞれ図7の(a1)、(a2)、及び(b)に示す。図6に示す論理回路データ30は、故障判定の対象となる論理回路を各ゲート間の接続関係として表したものであり、データはテーブル形式で格納されている。各ゲートに対応したデータは、以下に述べるようなフィールドから構成されている。項番(No.)31は各ゲートに対応したテーブルのエントリを示す番号である。要素(ELEMENT)32は、各ゲートを識別するID32aとそのゲートの種類(KIND)32bから構成されている。出力ゲート(OUTPUT GATE)33のフィールドには、要素32の出力値33a、要素32の出力側に接続されているゲートの個数(OUT NUM.)33b及びそれらゲートのID33c、33dが格納されている。入力ゲート(INPUT GATE)34のフィールドには、要素32の入力側に接続されているゲートの個数(IN NUM.)34a、それらゲートのID(I1、I2・・・)34b、34d及び入力値(V1、V2・・・)34c、34eが格納されている。制御データ(CONTROLDATA)35のフィールドには、要素32の出力信号線が束縛信号線、先頭信号線、或いは先頭信号線以外の非束縛信号線のいずれかを示す情報35aが登録される。出力段数(PO LEVEL)35bのフィールドには、要素32の回路の出力ゲートからのゲート段数が登録される。また、図6の各エントリには、一例として、後述の図13の(a)に示す論理回路に対応したデータが格納されている。なお、図6に示すように、論理回路データ30には入出力エッジも登録される。

0007

図7の(a1)、(a2)に示す出力仮定故障テーブル40と入力仮定故障テーブル45には、論理回路を診断するために仮定した故障に関する情報テーブルがテーブル形式で格納されている。この図7(a1)の出力仮定故障テーブル40において、各出力故障に対応したデータは、以下に述べるようなフィールドから構成されている。項番(No.)41は各出力故障に対応したテーブルのエントリを示す番号である。故障(FAULT)42は、各出力故障がどのゲートの出力信号線上に仮定されているのかを識別するID42aとその故障の種類(KIND)42bから構成されている。関連領域(RELATED REGION)43のフィールドには、故障42を含む関連領域の出力ゲートのID43a、及びそのID43aを出力ゲートとする関連領域において故障42が原理的未検出故障と判定されたか、テストパターンが存在すると判定されたか、或いは、まだ判定処理が行われていないかのいずれの状態にあるかを示す情報が格納されている。また、図7(a2)の入力仮定故障テーブル45において、各入力故障に対応したデータは、以下に述べるようなフィールドから構成されている。項番(No.)46は各入力故障に対応したテーブルのエントリを示す番号である。故障(FAULT)47は、各入力故障がどのゲートの入力信号線上に仮定されているのかを識別するID47a、要素47aの仮定故障入力信号線がどの入力ゲートに接続されているかを識別するINPUTID47b、及びその故障の種類(KIND)47cから構成されている。関連領域(RELATED REGION)48のフィールドには、故障47を含む関連領域の出力ゲートのID48a、及びそのID48aを出力ゲートとする関連領域において故障47が原理的未検出故障と判定されたか、テストパターンが存在すると判定されたか、或いは、まだ判定処理が行われていないかのいずれの状態にあるかを示す情報48bが格納されている。また、図7(a1)のエントリには、一例として、後述の図13(a)に示す論理回路に含まれている故障を出力故障(ゲート6bの出力信号線の0縮退故障)とみなした場合のデータが格納されている。図7(a2)のエントリには、一例として、上記の故障を入力故障(ゲート5bの入力信号線12bの0縮退故障)とみなした場合のデータが格納されている。また、図7(b)に示したテストパターン・データ50には、本実施例の故障判定の結果得られるテストパターン・データ、すなわち入力エッジに入力すべきデータがテーブル形式で格納されている。各入力エッジに対応したデータは、以下に述べるようなフィールドから構成されている。項番(No.)51は各入力エッジに対応したテーブルのエントリを示す番号である。ID52は各入力エッジの識別子である。設定値(VALUE)53は入力エッジに設定すべき値である。ケースNo.(TEST CASENo.)54は種々のテストパターンを識別するための番号である。故障(FAULT)55には、ケースNo.(TEST CASE No.)54のテストパターンがどの仮定故障に対して生成されたかを示す仮定故障テーブル中のエントリ番号41が格納されている。図7(b)のエントリには、一例として、後述の図13(a)に示す論理回路の入力エッジに対応したデータが格納されている。

0008

先ず、本発明の第1の実施例を説明する。図1は、本発明第1の実施例における論理回路の原理的未検出故障判定処理の各部の流れを表す図である。1は対象組合せ回路Xと対象未検出故障fを表している。1に対して、問題1「故障fは回路Xで原理的未検出故障か?」を考える。2は1の対象組合せ回路Xに対して故障fに関する変換を行って得られた1出力組合せ回路Yを表す。2に対して、問題2「回路Yの出力は常に0か?」を考えると、問題1と問題2は等価な問題になる。2’はNORゲート、EORゲート、ENORゲート、及び入力エッジのみから構成される2の回路Yの等価回路Y’を表す。2’に対して、問題2’「回路Y’の出力は常に0か?」を考えると、問題1と問題2’は等価な問題になる。4は簡約処理等により回路を簡単にする過程を表す。5は簡約処理後の回路における論理値割当て試行による回路の出力が1になる入力パターンの探索を表す。この探索により問題2’の答が得られる。問題2’の答がYESであれば、問題2と問題1の答もYESであり、問題2’の答がNOであれば、問題2と問題1の答もNOである。

0009

図8は、本発明の第1の実施例における論理回路の原理的未検出故障判定処理及びテストパターン生成処理の概要を表すフローチャートである。なお、この処理は図5の原理的未検出故障判定プログラム20による。ステップ100では、全ての未検出故障に対して関連領域を調査する。ステップ200では、まだ原理的未検出故障判定の対象になっていない関連領域が存在するかどうかを調べ、存在すればステップ300へ、存在しなければステップ1100へ分岐する。ステップ300では、まだ原理的未検出故障判定の対象になっていない関連領域を一つ選択する。ステップ400では、ステップ300で選択した関連領域をNORゲートと入力エッジのみで構成される等価回路に変換する。ステップ500では、ステップ400で変換した関連領域が未検出故障を持つような関連領域であって、その関連領域に対してまだ原理的未検出故障判定を行っていない故障があるかどうかを調べ、あればステップ600ヘ、なければステップ200へ分岐する。ステップ600では、ステップ400で変換した関連領域に含まれる未検出故障の内、この関連領域に対してまだ原理的未検出故障判定を行っていないものを一つ選択する。ステップ700では、ステップ600で選択した対象未検出故障がステップ400で変換した関連領域において原理的未検出故障であるかどうかを判定する。ステップ700のサブステップ700aでは、ステップ400でNORゲート変換された関連領域を、その対象未検出故障の関連領域におけるテストパターンに対しては出力が1になり、それ以外の入力パターンに対しては出力が0になるような1出力回路に変換する。ステップ700のサブステップ700bでは、サブステップ700aで得られた1出力回路の出力がどんな入力パターンに対しても0になるか否かを判定する。ステップ900では、ステップ700で対象未検出故障を含む関連領域においてテストパターンの生成が可能と判定されたかどうかを調べ、判定されたならばステップ1000へ、判定されなかったならばステップ500へ分岐する。ステップ1000では、対象未検出故障に対するテストパターンを生成する。ステップ1100では、各未検出故障の各関連領域での判定結果を編集し、各未検出故障が全体回路で原理的未検出故障かどうかを判定する。

0010

以下、図8の各ステップを詳細に説明する。図9は、図8のステップ100に示した関連領域調査の詳細なフローチャートである。ステップ101では、未検出故障の内、未検出故障箇所を含む関連領域がどのような範囲になるかを調査していないものが存在するかどうかを調べ、存在すればステップ102へ分岐し、存在しなければ処理を終了する。ステップ102では、未検出故障の内、未検出故障を含む関連領域がどのような範囲になるかを調査していないものを一つ選択する。ステップ103では、ステップ102で選択した未検出故障に関して関連領域調査を行っていないコーンが存在するかどうかを調べ、存在すればステップ104へ、存在しなければステップ101へ分岐する。ここで、コーンとは、スキャン設計方式を前提として分割された部分回路(組合せ回路)の1出力部分回路のことである。ステップ104では、ステップ102で選択した未検出故障に関して関連領域調査を行っていないコーンを一つ選択する。ステップ105では、ステップ102で選択した未検出故障箇所からステップ104で選択したコーンの出力エッジに到る全ての経路が通るようなゲートの内、最も入力側にあるものをDMとし、DMを出力とする領域RGを関連領域の候補とする。ステップ106から109は、この関連領域の候補が最終的に関連領域として確定できるか否かを判定する処理である。ステップ106では、ゲートDMの出力先にステップ104で選択したコーンの出力エッジが存在するかどうかを調べ、存在すれば領域RGは明らかに関連領域であるため、ステップ110へ分岐し、存在しなければステップ107へ分岐する。ステップ107では、ゲートDMの出力信号線の0縮退故障もしくは1縮退故障のどちらかのテストパターンが生成済みであるかどうかを調べ、テストパターンが生成済みならばステップ108へ分岐し、0縮退故障或いは1縮退故障のいずれに対してもテストパターンが生成されていないならばステップ109へ分岐する。ステップ108では、部分回路RG内のゲートDM以外の全てのゲートの該コーンにおけるファンアウト先ゲートが全ての部分回路RGに含まれるかどうかを調べ、含まれていればステップ110ヘ分岐し、含まれていなければステップ109へ分岐する。ステップ109では、ゲートDMから該コーンの出力エッジに到る全ての経路が通るようなゲートの内、最も入力側にあるものを新たにDMとし、このDMを出力とする新たな関連領域候補をRGとする。ステップ110では、関連領域をRGに確定する。

0011

図10は、本発明の第1の実施例における関連領域を表す図である。1a、2a、及び3aは未検出故障を含むコーンを、4aは未検出故障の仮定故障箇所を表す。5a及び6aは、信号線を表し、信号線5a及び6aにおける0縮退故障もしくは1縮退故障は検出済みであるとする。7aは未検出故障のコーン1a及び2aに対する関連領域、8aはコーン3aに対する関連領域を表す。コーン1aにおいて、関連領域が確定した時点でのDM及びRGはそれぞれ9a及び7aである。また、図11に、図8のステップ400において使用されるAND、NAND、OR、NORゲートのNORゲートによる等価表現の変換例を示す。

0012

図12は、図8のステップ700に示した対象未検出故障の関連領域における原理的未検出故障判定の詳細なフローチャートである。ステップ701は、図8のステップ700aに対応し、同じくステップ702から706は図8のステップ700bに対応する。ステップ701では、図8のステップ400でNORゲートに変換された関連領域を、対象未検出故障のその関連領域におけるテストパターンに対しては出力が1になり、それ以外の入力パターンに対しては出力が0になるような1出力回路に変換する。ステップ707では、ステップ701で得られた回路内のEOR論理及びENOR論理を認識し、回路をNORゲートとEORゲートとENORゲートと入力エッジで構成される等価回路に変換し、回路内のEORゲート及びENORゲートの簡約を行なう。ステップ702では、ステップ701で変換した回路内に入力の集合が全く同じ2つ以上のゲートが存在するかどうかを調べ、存在すればそれらのゲートを一つのゲートで置換する。ステップ703では、先頭信号線の更新を行う。ここで、非束縛信号線の内、束縛信号線と隣接しているものを先頭信号線と呼ぶ。非束縛信号線とは、回路内のどの分岐点から出力側に辿っていっても辿りつけない信号線のことであり、束縛信号線とは、回路内の適当な分岐点から出力側に辿っていくと到達可能な信号線のことである。ステップ704では、回路内の複雑な部分を簡単にする回路の簡約処理を行う。ステップ705では、ステップ704の簡約処理中に対象未検出故障がその関連領域において原理的未検出故障であると判定されたか、或いは、テストパターンの生成が可能であると判定されたかどうかを調べ、いずれかの判定がなされたならば処理を終了し、いずれの判定もなされていなければステップ706へ分岐する。ステップ706では、ステップ705で簡約処理を行った回路に対して論理値の割当てをいろいろ試行することにより、その関連領域において対象未検出故障が原理的未検出故障であるか否かを判定する。

0013

図13は、図12のステップ701に示した仮定故障に対する回路変換例を表す図である。図13(a)は変換の対象となる関連領域の回路図を示したものである。1b、2b、3b、4b、5b、及び6bは関連領域を構成するNORゲートを表し、7b、8b、9b、10b、及び11bは関連領域の入力エッジを表し、12bは対象未検出故障の仮定故障箇所を表し、故障の種類は1縮退故障であるとする。図13(b)は仮定故障箇所12bに関する変換後の回路図で、13bは新しく追加した回路の出力NORゲートを表す。図13(b)では、NORゲート6bと5bとの間の結線切り離し、NORゲート6bと13bとの間に新たに結線を繋いである。図13(b)で表される回路は、図13(a)で仮定故障箇所12bに故障信号がセットされるような入力パターンに対してはNORゲート13bの出力が1になり、それ以外の入力パターンに対してはNORゲート13bの出力が0になるという性質を持つ。図13(c)は仮定故障箇所12bから最初の分岐点までの部分を変換した後の回路図であり、14bは仮定故障箇所12bから出力側に辿って最初の分岐点を示す。図13(c)では、入力エッジ9bとNORゲート5bとの間の結線を切り離し、入力エッジ9bとNORゲート13bとの間に新たに結線を繋いである。図13(c)で表される回路では、図13(a)で仮定故障箇所12bに故障信号がセットされ、且つ仮定故障箇所12bから分岐点14bまで故障信号が伝播されるような入力パターンに対してはNORゲート13bの出力が1になり、それ以外の入力パターンに対してはNORゲート13bの出力が0になるという性質を持つ。

0014

図13(d)は分岐点14bから関連領域の出力までの部分を複写した後の回路図である。15b、16b、17b、18b、及び19bはそれぞれNORゲート1b、2b、3b、4b、及び5bをコピーしたゲートを表す。ここで、例えば被複写部分(NORゲート1b、2b、3b、4b、及び5bで構成された部分回路)は故障が存在しない場合の論理値をとる正常回路を、複写部分(NORゲート15b、16b、17b、18b、及び19bで構成された部分回路)は故障が存在する場合の論理値をとる故障回路を表す。(逆に、被複写部分を故障回路、複写部分を正常回路とみなしてもよい。)又、20bの部分は排他論理和を構成している。図13(d)において、NORゲート5b(正常回路の入力側切り口)の出力論理値を0に設定し、NORゲート19b(故障回路の入力側切り口)の出力論理値を1に設定して前方含意を行う。論理値が0又は1になった信号線の結線(ゲート5bと19bの出力線)と出力論理値が0且つ入力論理値に1が存在するようなゲート(入力論理値が1のゲート17bと18b)に接続されている全ての入力結線を切り離し、それに伴い生じた出力が浮きのゲートを削除すると、図13(e)の回路が得られる。図13(e)で表される回路では、図13(a)で仮定故障箇所12bに故障信号がセットされ、且つ、仮定故障箇所12bから関連領域の出力まで故障信号が伝播されるような入力パターン、すなわち対象仮定故障のその関連領域におけるテストパターンに対してはNORゲート13bの出力が1になり、それ以外の入力パターンに対してはNORゲート13bの出力が0になるという性質を持つ。

0015

図14は、図12のステップ707に示したEOR論理抽出・簡約処理におけるEOR論理抽出の詳細なフローチャートである。ステップ851では、出力論理がEOR論理もしくはENOR論理か否かを判定したいNORゲートEを選択する。ステップ852では、NORゲートEの出力論理値を1として後方含意を行なう。後方含意の結果、出力論理値が0且つ入力論理値に1の存在しないNORゲートをI1、I2、・・・、Imとおき、論理値を全てXに戻しておく。ステップ853では、Iiの全ての入力論理値を0として後方含意を行なう(i=1、2、・・・、m)。但し、この後方含意は論理値がXの入力の数が1個のゲートに対してのみ行なう。後方含意の結果、出力論理値が0又は1且つ入力論理値にXの存在するNORゲートもしくは入力エッジをJi1、Ji2、・・・、Jin(i)とおき、1回後方含意を行なう毎に論理値を全てXに戻しておく。ステップ854では、m個の集合{Ji1、Ji2、・・・、Jin(i)}(i=1、2、・・・、m)が互いに同じ集合であるか否かを調べ、同じであるならばJ1=J11=J21=・・・=Jm1、J2=J12=J22=・・・=Jm2、・・・、Jn=J1n(1)=J2n(2)=・・・=Jmn(m)としてステップ855へ分岐し、同じでなければ処理を終了する。ステップ855では、ステップ853のm回の後方含意でゲートJ1、J2、・・・、Jnにセットされた論理値の組(V1、V2、・・・、Vn)の集合GVを調べ、GV={(U1、U2、・・・、Un)|Ui=1となるiの個数は偶数個}ならばNORゲートEの出力はJ1、J2、・・・、Jnの出力のEOR論理であると判定し、GV={(U1、U2、・・・、Un)|Ui=1となるiの個数は奇数個}ならばNORゲートEの出力はJ1、J2、・・・、Jnの出力のENOR論理であると判定する。ステップ856では、ステップ855でNORゲートEの出力はJ1、J2、・・・、Jnの出力のEOR論理であると判定したならばステップ857へ分岐し、NORゲートEの出力はJ1、J2、・・・、Jnの出力のENOR論理であると判定したならばステップ858へ分岐し、それ以外ならば処理を終了する。ステップ857では、NORゲートEからJ1、J2、・・・、Jnまでの論理をEORゲートで置き換える。ステップ858では、NORゲートEからJ1、J2、・・・、Jnまでの論理をENORゲートで置き換える。

0016

図15は、図12のステップ707に示したEOR論理抽出・簡約処理におけるEOR論理抽出処理の具体例を表す図である。図15において、1s、2s、3s、4s、5s、6s、7s、8s、9s、10s、11s、12s、及び13sはNORゲートを表す。ここで、EOR論理判定対象ゲートはNORゲート3sである。図15(a)は、NORゲート3sの出力論理値を1に設定して後方含意を行った状態を表す(図14のステップ852)。ここで、図14のステップ852におけるI1、I2、I3、I4はそれぞれNORゲート4s、5s、6s、7sである。図15(b)は、NORゲート4s(=I1)の出力論理値を1に設定して後方含意を行った状態を表す(ステップ853)。ここで、図14のステップ853におけるJ11、J12、J13はそれぞれNORゲート11s、12s、13sである。図15(c)は、NORゲート5s(=I2)の出力論理値を1に設定して後方含意を行った状態を表す(ステップ853)。ここで、図14のステップ853におけるJ21、J22、J23はそれぞれNORゲート11s、12s、13sである。図15(d)は、NORゲート6s(=I3)の出力論理値を1に設定して後方含意を行った状態を表す(ステップ853)。ここで、図14のステップ853におけるJ31、J32、J33はそれぞれNORゲート11s、12s、13sである。図15(e)は、NORゲート7s(=I4)の出力論理値を1に設定して後方含意を行った状態を表す(ステップ853)。ここで、図14のステップ853におけるJ41、J42、J43はそれぞれNORゲート11s、12s、13sである。ここで、{J11、J12、J13}={J21、J22、J23}={J31、J32、J33}={J41、J42、J43}={11s、12s、13s}であることがわかる(ステップ854)。又、図15(b)、(c)、(d)、(e)での4回の後方含意でNORゲート11s、12s、13sの出力に設定された論理値の組の集合は{(0、0、0)、(0、1、1)、(1、0、1)、(1、1、0)}でこれは{(U1、U2、U3)|Ui=1となるiの個数は偶数個}と同じ集合である。よって、NORゲート3sの出力はNORゲート11s、12s、13sのEOR論理と等価であると判定される(ステップ856)。図15(f)は、NORゲート3sからNORゲート11s、12s、13sまでの論理をEORゲート14sで置き換えた回路を表す(ステップ857)。

0017

図16に、図12のステップ707に示したEOR論理抽出・簡約処理におけるEORゲート及びENORゲートの簡約例を示す。また、図17に、図12のステップ702に示した共通論理をまとめる処理の具体例を表す。図17(a)において、1c、2c、3c、4c、5c、6c、及び7cはNORゲートを表す。ここで、NORゲート4cと5cはどちらもNORゲート6cと7cをファンイン先ゲートとして持つ。従って、NORゲート4cと5cはそれぞれ同じ入力関係を持つので、NORゲート4cと5cを一つにまとめることが可能である。図17(b)は、NORゲート6c、7cと5cとの間の結線とNORゲート5cと2c、3cとの間の結線を切り離し、NORゲート4cと2c、3cとの間に結線を繋いで、図17(a)のNORゲート5cを4cで置換した回路を表す。

0018

図18は、図12のステップ703に示した先頭信号線の更新の詳細なフローチャートである。ここで、非束縛信号線の内、束縛信号線と隣接しているものを先頭信号線と呼ぶ。非束縛信号線とは、回路内のどの分岐点から出力側に辿っていっても辿りつけない信号線のことであり、束縛信号線とは、回路内の適当な分岐点から出力側に辿っていくと到達可能な信号線のことである。ステップ711では、分岐を持つ先頭信号線の中でまだ先頭信号線の更新の可能性について調査を行っていないものが存在するかどうかを調べ、存在すればステップ712へ分岐し、存在しなければ処理を終了する。ステップ712では、分岐を持つ先頭信号線の中で先頭信号線の更新の可能性について調査を行っていないものを一つ選択し、この先頭信号線をHとする。ステップ713では、先頭信号線Hの論理値を0にして前方含意を行う。ステップ714では、前方含意ができなくなった箇所の出力論理値Xのゲート(前方含意で入力論理値は変化したのに、出力論理値はXのままで変化しなかったゲート)の全てが互いに独立に出力信号線の論理値を0又は1に制御できるゲートであるかどうか、すなわち、分岐点を持たない出力論理値Xのゲートを通って入力エッジまで辿れるかどうかを調べ、辿れればステップ715へ分岐し、辿れなければステップ718へ分岐する。ステップ715では、論理値が0又は1の信号線の結線を切り離す。ステップ716では、ステップ715の処理の最中に出力が浮きになった束縛信号線に接続されたゲートを削除する。ステップ717では、先頭信号線Hの論理値を正当化する。ここで、正当化とは、その信号線を出力信号線として持つゲートの論理演算結果がその信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。ステップ718では、先頭信号線Hの論理値が1かどうかを調べ、1ならばステップ719へ分岐し、1でなければステップ720へ分岐する。ステップ719では、先頭信号線Hの論理値をXに設定して前方含意を行う。ステップ720では、先頭信号線Hの論理値をXに設定して前方含意を行う。ステップ721では、先頭信号線Hの論理値を1に設定して前方含意を行う。その後、ステップ714からの処理を繰り返す。

0019

図19は、図12のステップ703に示した先頭信号線の更新例を示す図である。図19(a)において、1d、2d、3d、4d、5d、6d、7d、及び8dはNORゲートを、9d、10d、11d、12d、及び13dは入力エッジを、14d、15d、16d、17d、及び18dは信号線を表す。ここで、先頭信号線は信号線14d、15d、16d、及び17dで、信号線14dは分岐を持ち、信号線15d、16d、及び17dは分岐を持たない。図19(b)は分岐を持つ先頭信号線14dの出力論理値を0とし、前方含意を行った状態を表す(図18のステップ713)。ここで、前方含意ができなくなり、且つ、出力論理値がXとなるNORゲート2d、3d、及び4dは、2dから入力エッジ9d、3dから入力エッジ10d、4dから入力エッジ11dのように分岐を持たず、出力論理値がXとなるゲートを通って入力エッジまで辿ることができるので、NORゲート2d、3d、及び4dの出力は互いに独立に0又は1に制御可能である。図19(c)は、図19(b)で論理値が0又は1の信号線の結線を切り離し(ステップ715)、信号線14dの正当化により入力エッジ12dの出力論理値を1とした状態を表す。すなわち、図19(b)において、信号線12d、13dの論理値のNOR演算結果が信号線14dの論理値0と等しくなるように、例えば図19(c)のように、信号線12dの論理値に1を割当てる。なお、図19(c)において、先頭信号線は信号線18dのみで、先頭信号線が図19(a)の信号線14d、15d、16d、及び17dから出力側の信号線18dに更新されている。

0020

図20は、図12のステップ704に示した回路の簡約処理の詳細なフローチャートである。本実施例における回路の簡約処理には、簡約処理A1、簡約処理A、簡約処理Bの3種類の簡約処理がある。簡約処理A1では、回路の出力ゲートの入力側にある冗長な論理を簡約する。簡約処理Aでは、回路の多入力ゲート(回路の出力ゲートを除く)の入力側にある冗長な論理を簡約する。簡約処理Bでは、先頭信号線の論理値が回路の出力論理値に与える影響を調べ、先頭信号線の論理値が0の時にその論理値が回路の出力を1にしようとする影響しか持たないならば、先頭信号線の論理値に0を割当てて固定し、先頭信号線の論理値が1の時にその論理値が回路の出力を1にしようとする影響しか持たないならば、先頭信号線の論理値に1を割当てて固定する。図20のステップ731では、簡約処理Aが可能な多入力ゲートが存在するかどうかを調べ、存在すればステップ732へ分岐し、存在しなければステップ737へ分岐する。ステップ732では、簡約処理Aが可能な多入力ゲートRを選択する。ステップ733では、多入力ゲートRが回路の出力ゲートかどうかを調べ、そうならばステップ734へ分岐し、そうでなければステップ735へ分岐する。ステップ734では、多入力ゲートRを対象に簡約処理A1を行う。ステップ735では、多入力ゲートRを対象に簡約処理Aを行う。ステップ736では、簡約処理A1又は簡約処理Aの途中で、対象未検出故障がその関連領域において原理的未検出故障である、或いは、テストパターンの生成が可能であるのいずれかであると判定されたかどうかを調べ、いずれかに判定されたならば処理を終了し、いずれにも判定されなかったならばステップ731へ分岐する。ステップ737では、簡約処理Bが可能な先頭信号線が存在するかどうかを調べ、存在すればステップ738へ分岐し、存在しなければ処理を終了する。なお、非束縛信号線の内、束縛信号線と隣接しているものを先頭信号線と呼ぶ。非束縛信号線とは、回路内のどの分岐点から出力側に辿っていっても辿りつけない信号線のことであリ、束縛信号線とは、回路内の適当な分岐点から出力側に辿っていくと到達可能な信号線のことである。ステップ738では、簡約処理Bが可能な先頭信号線Hを選択する。ステップ739では、先頭信号線Hを対象に簡約処理Bを行う。ステップ740では、簡約処理Bの途中で、対象未検出故障がその関連領域において原理的未検出故障である、或いは、テストパターンの生成が可能であるかのいずれかであると判定されたかどうかを調べ、いずれかに判定されたならば処理を終了し、いずれにも判定されなかったならばステップ741へ分岐する。ステップ741では、簡約処理Bが可能な新たな先頭信号線が存在するかどうかを調べ、存在すればステップ738へ分岐し、存在しなければステップ742へ分岐する。ステップ742では、簡約処理Aが可能な多入力ゲートが存在するかどうかを調べ、存在すればステップ732へ分岐し、存在しなければ処理を終了する。

0021

図21は、図20のステップ734に示した簡約処理A1の詳細なフローチャートである。ステップ751では、多入力ゲートRの出力論理値を1にして含意操作を行う。但し、非束縛信号線に対しては含意操作を行わない。ステップ752では、含意操作中に矛盾(含意操作中にそれぞれ異なる経路を介して0と1の2つの値が同一信号線に設定されようとする状況)が生じたかどうかを調べ、生じたならばステップ758へ分岐し、生じなかったならばステップ753へ分岐する。ステップ753では、出力論理値が0で入力論理値が0又はXであるゲートと、論理値が0又は1の先頭信号線を出力信号線として持つゲートを終端ゲート(入力エッジを含む)として登録する。ステップ754では、論理値が0又は1の信号線の結線を切り離す。ステップ755では、各終端ゲートに対して、その出力信号線が先頭信号線ならば出力論理値を入力エッジまで正当化し、その出力信号線が束縛信号線であって、且つ、入力数が1以上ならばその終端ゲートと多入力ゲートRとの間に結線を繋ぐ。ここで、正当化とは、対象となる信号線を出力信号線として持つゲートの論理演算結果がその信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。ステップ756では、多入力ゲートRの入力数が0かどうかを調べ、0ならばステップ757へ、0でなければステップ759へ分岐する。ステップ757では、対象未検出故障はその関連領域においてテストパターンの生成が可能であるとする。ステップ758では、対象未検出故障はその関連領域において原理的未検出故障であると判定する。ステップ759では、処理中に出力数が0となった浮きゲートの削除を行う。ステップ760では、論理値が0又は1の信号線の論理値を全てXに戻す。

0022

図22は、図20のステップ734に示した簡約処理A1の例を示す図である。図22(a)において、1e、2e、3e、4e、5e、6e、7e、8e、及び9eはNORゲートを、10e、11e、12e、13e、及び14eは入力エッジを表す。ここで、簡約処理A1の対象となっている多入力ゲートはNORゲート1eである。図22(b)は、NORゲート1eの出力論理値を1に設定して含意を行った状態を表す(図21のステップ751)。ここで、NORゲート8e、9e、及び入力エッジ10eが終端ゲートとなっている(ステップ753)。図22(c)は、論理値0又は1の信号線の結線(1eと2e、1eと3e、1eと4e、2eと8e、2eと6e、3eと5e、4eと6e、5eと8e、5eと10e、6eと9e、及び6eと10eとの間の結線)を切り離し(ステップ754)、終端ゲート8e及び9eの結線処理(ステップ755)と浮きゲート2e、7e、及び11eの削除(ステップ759)を行った状態を表す。

0023

図23は、図20のステップ735に示した簡約処理Aの詳細なフローチャートである。ステップ771では、多入力ゲートRの出力論理値を1にして後方含意を行う。但し、非束縛信号線に対しては含意を行わない。ステップ772では、含意中に矛盾(含意操作中にそれぞれ異なる経路を介して0と1の2つの値が同一信号線に設定されようとする状況)が生じたかどうかを調べ、生じたならばステップ779へ分岐し、生じなかったならばステップ773へ分岐する。ステップ773では、出力論理値が0であって、且つ、入力論理値が0又はXであるゲートと、論理値が0又は1の先頭信号線を出力信号線として持つゲートを終端ゲートとして登録する。ステップ774では、終端ゲートから出力側の回路を多入力ゲートRに収斂する部分と収斂しない部分とに分離する。ステップ775では、終端ゲートから多入力ゲートRに収斂する部分において、終端ゲートから前方含意を行う。但し、多入力ゲートRより出力側での含意は行わない。ステップ776では、前方含意中に矛盾が生じたかどうかを調べ、生じたならばステップ779へ分岐し、生じなかったならばステップ777へ分岐する。ステップ777では、論理値が0又は1の信号線の結線と、出力論理値が0であって、且つ、入力論理値に1が存在するゲートの全ての入力結線を切り離す。ステップ778では、各終端ゲートに対して、この終端ゲートが出力論理値が0であって且つ入力数が1以上、或いは、この終端ゲートの出力信号線が論理値0の先頭信号線ならば、その終端ゲートと多入力ゲートRとの間に結線を繋ぐ。又、この終端ゲートが出力論理値が1であって且つ入力数が1以上、或いは、この終端ゲートの出力信号線が論理値1の先頭信号線ならば、新たにNORゲートNを追加し、その終端ゲートとNORゲートNの間、及びNORゲートNと多入力ゲートRとの間に結線を繋ぐ。ステップ779では、多入力ゲートRの出力論理値に0を設定して前方含意を行う。ステップ780では、多入力ゲートRより出力側にある信号線の内、その論理値が0又は1の信号線の結線を切り離す。ステップ781では、上記の処理中に出力数が0となった浮きゲートを削除する。ステップ782では、回路の出力論理値を調べ、0ならばステップ783へ、1ならばステップ784へ、Xならばステップ785へそれぞれ分岐する。ステップ783では、対象未検出故障はその関連領域において原理的未検出故障であると判定する。ステップ784では、対象未検出故障はその関連領域においてテストパターンの生成が可能であると判定する。ステップ785では、論理値が0又は1の信号線の論理値を全てXに戻す。

0024

図24は、図20のステップ735に示した簡約処理Aの例を示す図である。図24(a)において、1f、2f、3f、4f、5f、6f、7f、8f、及び9fはNORゲートを表す。ここで、簡約処理Aの対象となっている多入力ゲートRはNORゲート2fである。図24(b)は、NORゲート2fの出力論理値に1を設定して後方含意を行った状態を表す(図23のステップ771)。ここで、終端ゲートはNORゲート4f、7f、及び8fである(ステップ773)。図24(c)は、NORゲート4f、7f、及び8fから出力側に到る回路をNORゲート2fに収斂する部分と収斂しない部分に分離した状態を表す(ステップ774)。図24(c)では、回路を分離するために、新たにNORゲート10f及び11fを追加した。図24(d)は、NORゲート4f、7f、及び8fからNORゲート2fに収斂する部分において、NORゲート4f、7f、及び8fから前方含意を行った状態を表す(ステップ775)。図24(e)は、論理値が0又は1の信号線の結線と、出力論理値が0であって、且つ、入力論理値に1が存在するゲートの全ての入力結線を切り離し(ステップ777)、終端ゲートの処理(ステップ778)と浮きゲートの削除(ステップ781)を行った状態を示す。

0025

図25は、図20のステップ739に示した簡約処理Bの詳細なフローチャートである。ステップ801では、先頭信号線Hから回路の出力に到るどの経路にもEORゲート及びENORゲートが含まれていないかどうかを調べ、いずれの経路にも含まれていなければステップ791へ分岐し、いずれかの経路に含まれていれば処理を終了する。ステップ791では、先頭信号線Hから回路の出力に到る全ての経路が偶数個のゲート(入力エッジを含む)から構成されているかどうかを調べ、構成されていればステップ792へ分岐し、構成されていなければステップ793へ分岐する。ステップ792では、先頭信号線Hの出力論理値に0を設定して前方含意を行う。ステップ793では、先頭信号線Hから回路の出力に到る全ての経路が奇数個のゲート(入力エッジを含む)から構成されているかどうかを調べ、構成されていればステップ794へ分岐し、構成されていなければ処理を終了する。ステップ794では、先頭信号線Hの論理値に1を設定して前方含意を行う。ステップ795では、論理値が0又は1である信号線の結線を切り離す。ステップ796では、先頭信号線Hの論理値の正当化を行う。ここで、正当化とは、対象となっている信号線を出力信号線として持つゲートの論理演算結果がその信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。ステップ797では、処理中に出力数が0となった浮きゲートを削除する。ステップ798では、回路の出力論理値が0ならばステップ799へ分岐し、1ならばステップ800へ分岐し、Xならば処理を終了する。ステップ799では、対象未検出故障はその関連領域において原理的未検出故障であると判定する。ステップ800では、対象未検出故障はその関連領域においてテストパターンの生成が可能であると判定する。

0026

図26は、図20のステップ739に示した簡約処理Bの例を示す図である。図26(a)において、1g、2g、3g、4g、及び5gはNORゲートを表し、6g及び7gは入力エッジを表し、8gは信号線を表す。ここで、簡約処理Bの対象となっている先頭信号線Hは信号線8gであり、信号線8gから回路の出力に到る2つの経路、すなわち、入力エッジ7g−>NORゲート4g−>NORゲート2g−>NORゲート1g及び入力エッジ7g−>NORゲート5g−>NORゲート3g−>NORゲート1gはどちらも入力エッジ7gも含めて4個のゲートから構成されている。先頭信号線8gの論理値を0とした場合には、NORゲート4g、2gの出力論理値はそれぞれ1、0になろうとし、NORゲート5g、3gの出力論理値はそれぞれ1、0になろうとするため、NORゲート1gの論理値は1になろうとする。逆に信号線8gの論理値を1とした場合にはNORゲート1gの論理値は0になろうとする。NORゲート1gの出力論理値すなわち回路の出力論理値を1にするように信号線8gの論理値を固定して得られた回路の出力が常に0ならば元の回路の出力も常に0という性質を持つ。図26(b)は、信号線8gの論理値を0に設定して前方含意を行った状態を表す(ステップ792)。図26(c)は、図26(b)で論理値が0又は1となった信号線の結線を切り離し(図25のステップ795)、浮きゲート(ゲート2gと4g)を削除(ステップ797)した状態を表す。

0027

図27は、図12のステップ706に示した論理値割当て試行による判定の詳細なフローチャートである。ステップ811aでは、図12のステップ704で得られた回路の出力論理値に1を設定して含意操作を行う。含意操作中に含意操作の対象となった各ゲートの出力信号線が未正当化信号線か否かがそのつどチェックされ、未正当化信号線ならばその出力信号線を登録しておく。ここで、未正当化信号線とは、入力論理値の演算結果が出力論理値と一致しないようなゲートの出力信号線のことである。ステップ812aでは、ステップ811aの含意操作で生じた未正当化信号線を先頭信号線まで正当化し、全ての未正当化信号線が正当化されたならば、対象未検出故障のテストパターンが存在すると判断する。一方、どのように論理値を割当てても正当化がうまくゆかなかったならば、対象未検出故障はその関連領域において原理的未検出故障であると判断する。ここで、正当化とは、対象信号線を出力信号線として持つゲートの論理演算結果が対象信号線の論理値と一致するように先頭信号線まで論理値を決めていくことである。ステップ813aでは、ステップ812aでテストパターンが存在すると判定されたならばステップ814aへ分岐し、判定されなかったならば処理を終了する。ステップ814aでは、論理値が0又は1のいずれかに定まった先頭信号線を入力エッジまで正当化する。ここで、正当化とは、対象信号線を出力信号線として持つゲートの論理演算結果が対象信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。

0028

図28は、図27のステップ812aに示した未正当化信号線に対する正当化の詳細なフローチャートである。ステップ821aでは、矛盾フラグに0を設定する。矛盾フラグとは、ステップ826a及びステップ830aの含意操作において、矛盾(含意操作中にそれぞれ異なる経路を介して0と1の2つの値が同一信号線上に設定されようとする状況)が生じたかどうかを表すフラグであり、矛盾フラグが0であるとは矛盾が無い状態を表し、矛盾フラグが1であるとは矛盾が生じた状態を表す。ステップ822aでは、矛盾フラグが0ならばステップ823aへ分岐し、1ならばステップ828aへ分岐する。ステップ823aでは、回路内に未正当化信号線があればステップ824aへ分岐し、無ければステップ827aへ分岐する。ステップ824aでは、登録されている未正当化信号線の中から1つを選択する。ステップ825aでは、ステップ824aで選択した未正当化信号線を出発点として後方追跡を行う。後方追跡では、出発点となった信号線から入力側に向かって論理値がXの信号線で構成される経路を辿っていき、追跡を打ち切った箇所の信号線に論理値を設定する。ステップ826aでは、ステップ825aで設定した論理値を元に含意操作を行う。ステップ827aでは、対象未検出故障のその関連領域におけるテストパターンが存在すると判定する。ステップ828aでは、矛盾解消のためのバックトラックを行う。ステップ829aでは、ステップ828aにおいて対象未検出故障が原理的未検出故障であると判定されたならば処理を終了し、判定されなかったんらばステップ830aへ分岐する。ステップ830aでは、バックトラック828aの過程で変更した信号線の論理値を元に含意操作を行う。

0029

図29は、図28のステップ825aに示した後方追跡の詳細なフローチャートである。ステップ831aでは、その出力信号線が未正当化信号線であるゲートを後方追跡の目標ゲートUIOBJNとし、目標値UIOBJLに未正当化信号線の論理値を設定する。ステップ832aでは、UIOBJNの出力信号線が先頭信号線ならばステップ834aへ分岐し、先頭信号線でなければステップ833aへ分岐する。ステップ833aでは、UIOBJNに対する入力ゲートであって、且つ、出力論理値がXであるゲートを1つ選択し、選択した入力ゲートをUIOBJNとし、UIOBJNを更新する。又、更新前のUIOBJNがNORゲートの場合には、UIOBJLの値を反転(0−>1、1−>0)させることによって、UIOBJLの値を更新し、更新前のUIOBJNがEORゲートもしくはENORゲートの場合には、更新後のUIOBJNの出力が1より0に制御しやすければUIOBJLに0を、そうでなければUIOBJLに1を設定することによってUIOBJLの値を更新する。但し、更新前のUIOBJNがEORゲート且つ論理値がXの入力数が1個の場合には、更新前のUIOBJNのXでない入力論理値全てとUIOBJLをEOR演算した値にUIOBJLを更新し、更新前のUIOBJNがENORゲート且つ論理値がXの入力数が1個の場合には、更新前のUIOBJNのXでない入力論理値全てとUIOBJLをENOR演算した値にUIOBJLを更新する。ステップ834aでは、UIOBJNの出力論理値にUIOBJLの値を設定する。ステップ835aでは、処理装置10内に設けた所定のスタックにUIOBJNのIDを積む。

0030

図30は、図28のステップ828aに示したバックトラックの詳細なフローチャートである。ステップ841aでは、スタックが空か否かを調べ、スタックが空ならばステップ847aへ分岐し、空でなければステップ842aへ分岐する。ステップ842aでは、スタックの1番上に積んであるIDに対応したゲートの論理値が反転済みであるか否かを調べ、反転済みならばステップ843aへ分岐し、未反転ならばステップ846aへ分岐する。ステップ843aでは、スタックの1番上に積まれたIDに対応するゲートの出力論理値をXに戻す。ステップ844aでは、含意操作を行う。ステップ845aでは、ゲートをスタックから除去する、すなわち、スタックの1番上に積まれたIDを除去する。ステップ846aでは、スタックの1番上に積まれたIDに対応するゲートの出力論理値を反転(0−>1、1−>0)する。ステップ847aでは、その関連領域において対象未検出故障は原理的未検出故障であると判定する。

0031

図31は、図12のステップ706に示した論理値割当て試行による判定処理の例を示す図である。図31において、1r、2r、3r、4r、5r、6r、及び7rはいずれもNORゲートを表し、8rは入力エッジを表し、9r、10r、11r、12r、13r、14r、及び15rはいずれも信号線を表す。図31(a)は、図12に示した簡約処理704で得られた回路の出力論理値に1を設定し、含意操作を行った回路を表す(図27のステップ811a)。ここで、信号線9rと10rをそれぞれ出力信号線とするNORゲート2rと3rの出力論理値が0であり、入力論理値が全てXであるため、信号線9rと10rはいずれも未正当化信号線である。図31(b)は、図31(a)に示した回路に含まれる未正当化信号線の中から9rを選択して後方追跡を行った図である(図28のステップ824a、ステップ825a)。ここで、(後方追跡の目標ゲート、目標値)は(2r、0)−>(4r、1)−>(6r、0)−>(8r、1)と順次更新される(図29のステップ833a)。図31(c)は、後方追跡の最終目標ゲート8rに最終目標値1を設定し(ステップ834a)、含意操作826aを行った結果を示した図である。ここで、論理値を設定したゲート8rはスタックに積まれる(ステップ835a)。ここで、NORゲート3rの出力論理値は0であるのに、入力論理値0と0のNOR演算結果は1であり、論理値に矛盾が生じている。図31(d)は、図31(c)に示した回路に対してバックトラックおよび含意操作を行った結果を示した図である(図28のステップ828a、ステップ829a)。スタックの1番上に積まれたゲート8rの論理値を1から0に反転して(図30のステップ846a)、含意操作を行うと今度はNORゲート2rで矛盾が生じる。図31(e)は、図31(d)の回路に対して更にバックトラックを行った結果を示した図である。スタックの1番上に積まれたゲート8rは既に論理値反転済みのため、論理値をXに戻し(ステップ843a)、含意操作を行い(ステップ844a)、次のバックトラックの対象となるゲートを探索するが、スタックが空のため、その関連領域において対象未検出故障は原理的未検出故障であると判定する(ステップ847a)。

0032

図32は、図28のステップ825aに示した後方追跡の別法を示す詳細なフローチャートである。図32に示すステップ831b、833b、834b、及び835bは図29に示したステップ831a、833a、834a、及び835aと同一のものである。本実施例では、目標ゲート(UIOBJN)および目標値(UIOBJL)の更新を1回行っただけで後方追跡を打ち切る

0033

図33は、図8のステップ1000に示したテストパターン生成の詳細なフローチャートである。ステップ1008では、図8のステップ700の処理中に出力論理値が0又は1となった先頭信号線を入力エッジまで正当化する。ここで、正当化とは、対象となっている信号線を出力信号線として持つゲートの論理演算結果がその信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。ステップ1009では、その関連領域の入力には生成した対象未検出故障のその関連領域におけるテストパターンを割当て、全体論理回路の中のその関連領域外の入力に対しては関連領域の出力ゲートの出力信号線の0縮退故障或いは1縮退故障の全体回路におけるテストパターン(既に生成済み)を割当ててマージする。

0034

図34は、図8のステップ1100に示した判定結果の編集の詳細なフローチャートである。ステップ1101では、まだ判定結果の編集を行っていない未検出故障が存在するかどうかを調べ、存在すればステップ1102へ分岐し、存在しなければ処理を終了する。ステップ1102では、まだ判定結果の編集を行っていない未検出故障を1つ選択する。ステップ1103では、ステップ1102で選択した未検出故障を含む全ての関連領域でこの未検出故障が原理的未検出故障であると判定されたかどうかを調べ、判定されたならばステップ1104へ分岐し、判定されなかったならばステップ1105へ分岐する。ステップ1104では、ステップ1102で選択した未検出故障は全体回路で原理的未検出故障であると判定する。ステップ1105では、ステップ1102で選択した未検出故障のテストパターンが生成されたかどうかを調べ、生成されたならばステップ1106へ分岐し、生成されなかったならばステップ1107へ分岐する。ステップ1106では、ステップ1102で選択した未検出故障はテストパターンの生成に成功したと判定する。ステップ1107では、ステップ1102で選択した未検出故障が原理的未検出故障であるかという判定ができなかったと判定する。

0035

次に、本発明の第2の実施例を説明する。本実施例では、第1の実施例と同様のシステム構成で論理回路の原理的未検出故障判定処理及びテストパターン生成処理を行なう。これらの処理は図8に示した手順に準ずるが、図8のステップ400において、関連領域のNOR変換を行う代わりに関連領域のNAND変換を行う。以下では、NAND変換に伴う処理の変更部(第1の実施例と異なる部分)のみについて説明する。図35は、本発明の第2の実施例における関連領域のNAND変換で使用される等価表現の変換を示す図である。図35は、図8のステップ400に示した関連領域のNAND変換において使用される等価表現の変換例であり、AND、NAND、OR、及びNORゲートをそれぞれNANDゲート組合せで表現したものである。また、図12図8のステップ700の詳細)に示したステップ701において、NANDゲート変換された関連領域を、対象未検出故障のその関連領域におけるテストパターンに対しては出力が0になり、それ以外の入力パターンに対しては出力が1になるような1出力回路に変換する。なお、図12のステップ703に示した先頭信号線の更新の詳細は図18に、ステップ704に示した回路の簡約処理の詳細は図20に、それぞれ示したものと同様である。また、非束縛信号線の内、束縛信号線と隣接しているものを先頭信号線と呼ぶ。非束縛信号線とは、回路内のどの分岐点から出力側に辿っていっても辿りつけない信号線のことであり、束縛信号線とは、回路内の適当な分岐点から出力側に辿っていくと到達可能な信号線のことである。また、図14図12のステップ707の詳細)に示したステップ852において、Eの出力論理値に1を設定して後方含意を行なう代わりにEの出力論理値に0を設定して後方含意を行う。又、ステップ853において、Iの全ての入力論理値に0を設定して後方含意を行う代わりにIの全ての入力論理値に1を設定して後方含意を行う。また、図21図20のステップ734の詳細)のステップ751において、Rの論理値に1を設定して含意を行う代わりにRの論理値に0を設定して含意を行う。また、図23図20のステップ735の詳細)のステップ771において、Rの論理値に1を設定して後方含意を行う代わりにRの論理値に0を設定して後方含意を行い、ステップ779において、Rの論理値に0を設定して前方含意を行う代わりにRの論理値に1を設定して前方含意を行う。更に、ステップ783において、対象未検出故障がその関連領域において原理的未検出故障であると判定する代わりにテストパターンの生成が可能であると判定し、ステップ784において、対象未検出故障がテストパターンの生成が可能であると判定する代わりに原理的未検出故障であると判定する。また、図25図20のステップ739の詳細)のステップ792において、Hの論理値に0を設定して前方含意を行う代わりにHの論理値に1を設定して前方含意を行い、ステップ794においてHの論理値に1を設定して前方含意を行う代わりにHの論理値に0を設定して前方含意を行う。更に、ステップ799において、対象未検出故障がその関連領域において原理的未検出故障であると判定する代わりにテストパターンの生成が可能であると判定し、ステップ800において、対象未検出故障がテストパターンの生成が可能であると判定する代わりにその関連領域において原理的未検出故障であると判定する。また、図27図12のステップ706の詳細)のステップ811aにおいて、回路の出力ゲートの出力論理値に1を設定して含意操作を行う代わりに回路の出力ゲートの出力論理値に0を設定して含意操作を行う。なお、第1の実施例を示した図28図29図30図32図33図34等については、本実施例でもこれらと同様の処理を行なうものとする。

0036

次に、本発明の第3の実施例を説明する。図36は、本発明の第3の実施例における不確定入力エッジを含む論理回路の原理的未検出故障判定処理の概要を表す図である。なお、21以外は図1に示したものと同一である。1に対して、問題1「故障fは回路Xで原理的未検出故障か?」を考える。2は1の対象となる組合せ回路Xをfに関して変換して得られた1出力組合せ回路Yを表す。2に対して、問題2「回路Yの出力は常に0か?」を考えると、問題1と問題2は等価な問題になる。21は2の1出力組合せ回路を変換して得られた不確定入力エッジを全く含まない1出力組合せ回路Y’を表す。21に対して、問題3「回路Y’の出力は常に0か?」を考えると、問題2と問題3は等価になる。3は、NORゲート、EORゲート、ENORゲート、及び入力エッジのみから構成される21の回路Y’の等価回路Y’’を表す。3に対して問題3’「回路Y’’の出力は常に0か?」を考えると、問題3と問題3’は等価な問題になる。4は簡約処理等により回路を簡単にする過程を表す。5は簡約処理後の回路における論理値割当て試行による回路の出力が1になる入力パターンの探索を表す。この探索により問題3’の答が得られる。問題3’の答がYESであれば問題3と問題2と問題1の答もYESであり、問題3’の答がNOであれば問題3と問題2と問題1の答もNOである。

0037

本実施例では、論理回路における原理的未検出故障判定処理の流れは第1の実施例に示した図8のフローチャートと同一である。図37は、図8のステップ700に示した対象未検出故障の関連領域における原理的未検出故障判定の詳細なフローチャートである。図37において、ステップ720以外の処理は図12と同一である。すなわち、ステップ720では、ステップ701で得られた回路を不確定入力エッジを含まない回路に変換する。不確定入力エッジとは、0、1のどちらにも確定できない入力エッジの事を表し、以下U入力エッジと呼ぶ。

0038

図38は、図37のステップ720のU入力エッジ除去のための回路変換の詳細なフローチャートである。本実施例では、U入力エッジを除去するためには2種類の回路変換A2、B1を行う。原理的未検出故障判定及びテストパターン生成の処理とは無関係に出力先ゲートに0又は1を設定できる(すなわち、0又は1を設定した回路に対して原理的未検出故障判定を行っても正しい判定結果が得られ、テストパターン生成を行っても正しいテストパターンが得られる。)。U入力エッジを除去する回路変換を回路変換A2とする。更に、回路変換A2で除去できなかったU入力エッジに対してU入力エッジに0を設定した場合の回路と1を設定した場合の回路を合成することによりこれらのU入力エッジを除去する回路変換を回路変換B1とする。ステップ721では取り扱う回路にU入力エッジが存在するかどうか判定し、存在すればステップ722へ、存在しなければ処理を終了する。なお、U入力エッジの有無は、図6に示した論理回路データの中にゲートの種類32bが入力エッジで出力論理値33aが不確定値であるようなゲートの有無を調べることにより、調べることができる。ステップ722では、U入力エッジで回路変換A2を実行していないものが存在するかを調べ、存在すればステップ723へ分岐し、存在しなければステップ724へ分岐する。ステップ723ではそのU入力エッジの回路変換A2を行う。ステップ724では、U入力エッジが存在するかどうかを調べ、存在すればステップ725へ分岐し、存在しなければ処理を終了する。ステップ725では、そのU入力エッジの回路変換B1を行う。

0039

図39は、図38のステップ723に示した回路変換A2の詳細なフローチャートである。ステップ723aでは、対象U入力エッジの出力ゲートでまだ調べていないものがあるかどうかを調べ、あればステップ723bへ分岐し、なければ処理を終了する。ステップ723bでは、U入力エッジの出力ゲートでまだ調べていないものを1つ選択する。ステップ723cでは、ステップ723bで選択した出力ゲートの入力ゲートでU入力エッジ以外ののものが存在するかどうかを調べ、存在すればステップ723dへ分岐し、存在しなければステップ723hへ分岐する。ステップ723dでは、ステップ723bで選択した出力ゲートの入力ゲートでU入力エッジ以外のものを1つ選択する。ステップ723eでは、ステップ723dで選択した入力ゲートの論理値がXであって、且つ、その入力ゲートが非束縛信号線であるか、或いは、分岐を持たない先頭信号線であるかどうかを調べ、条件を満たすならばステップ723fへ分岐し、条件を満たさなければステップ723cへ分岐する。ステップ723fでは、ステップ723dで選択した入力ゲートに論理値を設定する。ステップ723fにおいて、回路がNORゲートと入力エッジで構成されている場合には、論理値として1を設定し、回路がNANDゲートと入力エッジで構成されている場合には、論理値として0を設定する。ステップ723gでは、選択された入力ゲートに設定した論理値を入力エッジまで正当化する。ここで、正当化とは、対象信号線を出力信号線として持つゲートの論理演算結果が対象信号線の論理値と一致するように入力エッジまで辿りながら順次論理値を決めていくことである。一方、ステップ723hでは、ステップ723fで設定した論理値をもとに含意操作を行う。ステップ723iでは、論理値が0又は1のいずれかに定まった信号線の結線を切り離す。ステップ723jでは、出力が浮きになったゲートを削除する。

0040

図40は、本発明の第3の実施例における回路変換A2を示す図である。図40(a)において、U1はU入力エッジを表し、I1及びG1はNORゲートを表す。また、I1の論理値を1に設定することにより、U1の出力先ゲートG1の論理値を0に制御できる。更に、I1は非束縛信号線であるため、I1の論理値を1に設定すると、G1の論理値が0に制御されるだけで、他の回路部分への影響はない。図40(b)は、図40(a)において、I1の論理値に1を設定して前方含意操作を行い、I1の論理値を入力エッジまで正当化し(図39のステップ723f、ステップ723g、ステップ723h)、0又は1のいずれかの値に定まった信号線の結線を切り離し(ステップ723i)、出力が浮きになったゲートを削除して(ステップ723j)得られた回路を表す。図40(b)においてU入力エッジU1は除去されている。図40(c)に回路変換A2ができないU入力エッジの具体例を示す。図40(c)において、U2はU入力エッジを表し、I2、G2、及びG3はNORゲートを表す。また、I2の論理値を1に設定することによりU2の出力先ゲートG2の論理値を0に制御できる。しかし、I2の論理値を1に設定すると、G2以外のNORゲートG3の論理値に影響が及ぶため、U2に対する回路変換A2は不可能である。

0041

図41は、図38はステップ725に示した回路変換B1の詳細なフローチャートである。ステップ725aでは、U入力エッジが存在するかどうかを調べ、存在すればステップ725bへ分岐し、存在しなければ処理を終了する。ステップ725bでは、U入力エッジを1つ選択する。ステップ725cでは、ステップ725bで選択した対象U入力エッジから見て出力側にある回路をコピーする。コピーの操作は次の様に行う。まず、ステップ725bで選択した対象U入力エッジから辿ることができるゲートであって、且つ、回路の出力ゲートを除く全てのゲートの各々に対して1つずつコピーゲートを作る。更に、以下に述べるように、各コピーゲートの入力信号線を接続する。ゲートAのコピーゲートA’に対し、Aの全ての入力ゲートもしくは入力ゲートのコピーゲートとの間に入力信号線を繋ぐ。ここで、Aの入力ゲートBがコピーゲートを持つならば(すなわち、Bが対象U入力エッジから到達可能ならば)、BのコピーゲートB’とA’との間に信号線を繋ぎ、Bがコピーゲートを持たないならば(すなわち、Bが対象U入力エッジから到達不可能ならば)、BとA’との間に信号線を繋ぐ。最後に、回路の出力ゲートに接続されている入力ゲートのコピーゲートと回路の出力ゲートとの間に信号線を繋ぐ。ステップ725dでは、対象U入力エッジUE1に論理値0を設定し、UE1のコピーゲートUE2に論理値1を設定する。ここで、逆にUE1に論理値1を設定し、UE2に論理値0を設定しても構わない。ステップ725eでは、含意操作を行う。ステップ725fでは、論理値が0又は1のいずれかに定まった信号線の結線を切り離す。ステップ725gでは、出力が浮きになったゲートを削除する。

0042

図42は、本発明の第3の実施例における回路変換B1を示す図である。図42(a)において、U3はU入力エッジを表し、R1、R2、R3、R4、R5、R6、R7、及びR8はNORゲートを表し、O1は回路の出力NORゲートを表す。U3は回路変換A2が不可能なU入力エッジである。図42(b)は、図42(a)に示した回路でU3より出力側を複写した後の回路を表す。図42(b)において、U3’はU3をコピーしたU入力エッジを表し、C4、C5、C7、及びC8はそれぞれR4、R5、R7、及びR8をコピーしたNORゲートを表す(図41のステップ725c)。図42(c)は、図42(b)に示したU3に論理値0を、U3’に論理値1を設定して含意操作を行い、論理値が0又は1となった信号線を切り離し、出力が浮きになったゲートを削除した回路である(ステップ725d、ステップ725e、ステップ725f、ステップ725g)。図42(c)では、対象U入力エッジU3は除去されている。

発明の効果

0043

本発明によれば、必要な回路領域のみを切り出し、回路の冗長性を除去することにより、演算器系論理回路の原理的未検出故障判定が効率的にできる。また、この原理的未検出故障判定の結果を用いることにより、テストパターンを容易に生成できる。

図面の簡単な説明

0044

図1本発明の第1の実施例における論理回路の原理的未検出故障判定処理の概要を表す図である。
図2拡張含意操作の一例を示す図である。
図3一意活性化の一例を示す図である。
図4従来の簡約手法の一例を示す図である。
図5本発明の論理回路の原理的未検出故障判定方法及びテストパターン生成方法を適用する計算機システムの構成図である。
図6図5の論理回路データ30の構成を示す図である。
図7図5の出力仮定故障テーブル40、入力仮定故障テーブル45、及びテストパターン・データ50の構成を示す図である。
図8本発明の第1の実施例における論理回路の原理的未検出故障判定処理及びテストパターン生成処理の概要を表すフローチャートである。
図9図8のステップ100に示した関連領域調査の詳細なフローチャートである。
図10本発明の第1の実施例における関連領域を表す図である。
図11図8のステップ400において使用されるAND、NAND、OR、NORゲートのNORゲートによる等価表現の変換例を示す図である。
図12図8のステップ700に示した対象未検出故障の関連領域における原理的未検出故障判定の詳細なフローチャートである。
図13図12のステップ701に示した仮定故障に対する回路変換例を表す図である。
図14図12のステップ707に示したEOR論理抽出・簡約処理におけるEOR論理抽出の詳細なフローチャートである。
図15図12のステップ707に示したEOR論理抽出・簡約処理におけるEOR論理抽出処理の具体例を表す図である。
図16図12のステップ707に示したEOR論理抽出・簡約処理におけるEORゲート及びENORゲートの簡約例を示す図である。
図17図12のステップ702に示した共通論理をまとめる処理の具体例を表す図である。
図18図12のステップ703に示した先頭信号線の更新の詳細なフローチャートである。
図19図12のステップ703に示した先頭信号線の更新例を示す図である。
図20図12のステップ704に示した回路の簡約処理の詳細なフローチャートである。
図21図20のステップ734に示した簡約処理A1の詳細なフローチャートである。
図22図20のステップ734に示した簡約処理A1の例を示す図である。
図23図20のステップ735に示した簡約処理Aの詳細なフローチャートである。
図24図20のステップ735に示した簡約処理Aの例を示す図である。
図25図20のステップ739に示した簡約処理Bの詳細なフローチャートである。
図26図20のステップ739に示した簡約処理Bの例を示す図である。
図27図12のステップ706に示した論理値割当て試行による判定の詳細なフローチャートである。
図28図27のステップ812aに示した未正当化信号線に対する正当化の詳細なフローチャートである。
図29図28のステップ825aに示した後方追跡の詳細なフローチャートである。
図30図28のステップ828aに示したバックトラックの詳細なフローチャートである。
図31図12のステップ706に示した論理値割当て試行による判定処理の例を示す図である。
図32図28のステップ825aに示した後方追跡の別法を示す詳細なフローチャートである。
図33図8のステップ1000に示したテストパターン生成の詳細なフローチャートである。
図34図8のステップ1100に示した判定結果の編集の詳細なフローチャートである。
図35本発明の第2の実施例における関連領域のNAND変換で使用される等価表現の変換を示す図である。
図36本発明の第3の実施例における不確定入力エッジを含む論理回路の原理的未検出故障判定処理の概要を表す図である。
図37図8のステップ700に示した対象未検出故障の関連領域における原理的未検出故障判定の詳細なフローチャートである。
図38図37のステップ720のU入力エッジ除去のための回路変換の詳細なフローチャートである。
図39図38のステップ723に示した回路変換A2の詳細なフローチャートである。
図40本発明の第3の実施例における回路変換A2を示す図である。
図41図38のステップ725に示した回路変換B1の詳細なフローチャートである。
図42本発明の第3の実施例における回路変換B1を示す図である。

--

0045

1 対象組合せ回路Xと対象未検出故障f
2 対象組合せ回路Xに対象未検出故障fに関する変換を行って得られた1出力回路Y
2’NORゲート、EORゲート、ENORゲート、及び入力エッジで構成された1出力回路Yと等価な1出力回路Y’
4簡約処理
5論理値割当て試行
10処理装置
20原理的未検出故障判定プログラム
30論理回路データ
40 出力仮定故障テーブル
45入力仮定故障テーブル
50テストパターン・データ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ