(57)【要約】【課題】  テストパターンの増加を抑制して効果的にダイナミックコンパクションを行なう。【解決手段】  ＥＯＲゲートがＤフロンティア（D frontier）もしくはＪフロンティア（J frontier）になるとき、ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、この計数ステップによる計数結果に基づいて、検出不可能となる故障数が少なくなるステートを入力ピンに割り当てるステートとして選択する選択ステップと、この選択ステップにおいて選択されたステートに基づいてテストパターンを生成するテストパターン生成ステップとをそなえる。【選択図】        図１
2006010641.tif 000002
【特許請求の範囲】
【請求項１】
ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴とする、テストパターン生成方法。
【請求項２】
ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴とする、テストパターン生成方法。
【請求項３】
該テストパターン生成ステップにおいて、
前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意するステップと、
前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するステップとをそなえることを特徴とする、請求項２記載のテストパターン生成方法。
【請求項４】
ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラム。
【請求項５】
ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばＬＳＩ（Large Scale Integration）等の電子回路の故障を検出するためのテストパターンを生成する技術に関する。
【背景技術】
【０００２】
一般に、例えばＬＳＩ等の集積回路の製造不良の検出は、テスタを用いてＬＳＩの入力ピンに適当な信号値を印加し、その出力ピンに現れる信号値を期待される結果と比較することで行なわれる。入力ピンに印加される信号値と出力ピンに現れるべき期待値とを合わせてテストパターン（試験パターン）と呼ぶ。
ＬＳＩの製造不良によりＬＳＩの内部に生じる欠陥は故障と呼ばれ、ＬＳＩ内部で起こりうる全ての故障について検証を行なうためには、多くのテストパターンが必要となる。そして、これらのテストパターンの削減を目的として、ダイナミックコンパクション（dynamic compaction）と呼ばれる圧縮手法が一般的に用いられている（下記特許文献１参照）。
【０００３】
ダイナミックコンパクションとは、以下に示すような、テストデータの圧縮処理のことをいう。例えば、ＡＴＰＧ（Automatic Test Pattern Generator）により生成されたテストパターンによりターゲットの一次故障（primary fault）のテストに成功した場合、その一次故障を検出するために設定されたネットステート（net state）条件で、残存する未検出故障の集合から１つの二次故障（secondary fault）を選択し、まだ不定値であるテストポイントに新たに値を設定することにより上記二次故障に対するテストパターン生成を実行し、以下同様の処理を、他の二次故障が未検出故障の集合から選択されなくなるまで繰り返し実行する。なお、他の二次故障の選択に際し、同一故障を重複して選択することはないものとする。ダイナミックコンパクションとは、上述のようにしてテスト単位で検出される故障の数を増加させることにより、テストデータを減少させるものである。
【０００４】
さて、現在のハイスペックなプロセッサには、動作速度やチップ面積の要求から、no scan-ableな記憶素子であるＲＡＭ（Random Access Memory）及びno scan latch（NSL）arrayで構成されるＲＦ（register file）が搭載されることがある。
そして、このような記憶素子の前後には、しばしば繰り返し対象性の高い組み合わせ回路（例えば、write/read address selector）やＥＯＲ（exclusive OR）を含む組み合わせ回路（例えば、パリティチェック回路をはじめとするＥＣＣ（error correct circuit）やTAG RAMにあるマッチコンペア（match compare）回路）が配設される。
【０００５】
従来のダイナミックコンパクション手法（あるいは個々の故障に対するＡＴＧ（Automatic Test Generator））では、故障伝搬の未解決ゲート（Ｄフロンティア）、あるいは出力の未解決ゲート（Ｊフロンティア）の解決に関するデシジョン（decision）において、可制御／可観測基準（例えば、LEVEL，SCOAP，FANOUT BASE）、もしくはこのようにトポロジー的に決定される静的基準によるデシジョンの偏りを避けるために、rotating back-trace等の発見的手法が導入されることが多い。
【０００６】
なお、Ｊフロンティア（J frontier；Justify frontier）とは、出力に要求値が存在し、入力に２つ以上のX（不定値）が存在するために入力値の設定に選択が必要な未解決なゲートであり、Ｄフロンティア（D frontier；Different frontier）とは、入力の少なくとも１つに正常値と故障値に差異D（different）が存在し、その他の入力に１つ以上のXが存在するためにD伝播が不明な未解決なゲートである。又、デシジョン（decision）とは、上述したＪフロンティア／Ｄフロンティアを解決するためにＡＴＧが入力に与えるステートを選択することをいう。
【特許文献１】特開平１１−５２０３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
図１５はＣＡＭ（Content Address-able Memory）／ＴＬＢ（Translation Look-aside Buffer）構成をそなえる回路の例を部分的に示す図である。この図１５に示す回路は、scan_1，scan_2およびscan_3をそなえるキー（key）部１０１と、NSL array から構成されるＲＦ（広義にＲＡＭ）であるメモリ（memory）部１０２と、ＥＯＲを含む組み合わせ回路であるマッチコンペア（match compare）部１０３とをそなえて構成されている。なお、メモリ部１０２は、エントリ（entry）＃１およびエントリ＃２をそなえている。
【０００８】
さて、この図１５に示すＣＡＭ／ＴＬＢ回路を、メモリ部１０２とマッチコンペア部１０３とに分けて考えると、従来のダイナミックコンパクション手法では、ＥＯＲを含む組み合わせ回路であるマッチコンペア部１０３に関わる制御によって、あるいはエントリ（entry）方向にwrite排他性の高いメモリ部１０２のwriteに関わる制御によっては、十分なパターン圧縮を期待できない可能性がある。
【０００９】
以下に、（１）ＥＯＲを含む組み合わせ回路に関する制御と、（２）エントリ方向に排他性の高いＲＡＭ，ＲＦに関する制御とのそれぞれの場合におけるパターン圧縮の非効率化について説明する。
（１）ＥＯＲを含む組み合わせ回路に関する制御について
例えば、図１５に示す回路において、故障ｆ１１，ｆ１２およびｆ１３なる縮退０故障（stack at 0 fault）を検出対象の故障として考える。
【００１０】
目視によれば、これらの故障ｆ１１〜ｆ１３に対する理想的なテストを、
nsl_11 = nsl_12 = nsl_13 = 1
scan_1 = scan_2 = scan_3 = 0
のステート（state）割り当てにより、１つのタイムプレーン（time plane）上で故障励起と伝搬とを行なうことで実現される。なお、実際には、ＮＳＬを制御するための準備パターンとして１つ以上のタイムプレーンを必要とするが、ここでは簡単化のために準備パターンのタイムプレーンにおいて、少なくとも１つのエントリに関連するＮＳＬの制御は任意であるとすると、故障ｆ１１〜ｆ１３に対するテストは２つのタイムプレーンにより理想的な最小テスト（理想テスト）となる（図１６参照）。
【００１１】
図１６は図１５のエントリ＃１の故障ｆ１１〜ｆ１３検出における理想テストの例を示す図、図１７はその最悪テストの例を示す図である。
ここで、回路が初期状態、即ち全てのscan latch，ＮＳＬが不定Xである状態から、故障ｆ１１を一次故障（primary fault）とするときのダイナミックコンパクションを行なう過程を考える。故障ｆ１１に対するテスト生成では故障励起，故障伝搬について、ユニーク・パス・チェック（unique path check）により、nsl_11=１，n12=１，n 13=１は必須ステートとして唯一に決定可能である。
【００１２】
つまり、ＡＴＧにおけるデシジョンは、Ｄフロンティアであるeor_11を解決するためのscan_1のステートと、Ｊフロンティアであるeor_12〜13を解決するためのscan_2〜scan_3とnsl_12〜nsl_13のステートとをそれぞれ決定することである。
しかしながら、DフロンティアであるＥＯＲは、故障が伝搬する以外の入力ピンのステートがＸ以外であるならば解決し、ＪフロンティアであるＥＯＲは（input pin-1）pinの入力ステートを決定すれば、残りの１pinのステートは含意（インプリケーション）操作により直ちに決定される。
【００１３】
図１５において、Ｄフロンティアであるeor_11では、scan_1のステートをX 以外に決定すれば解決し、又、Ｊフロンティアであるeor_12，eor_13にあるような 2input ＥＯＲに関してはscan_2のステートを決定して解決することと、nsl_12のステートを決定して解決することとは等価である。これは、eor_13の解決に関する scan_3，nsl_13の決定についても同様である。従って、Dフロンティア（e or_11）、Ｊフロンティア（eor_12，eor_13）解決は、scan_11〜scan_13のステート決定へと帰着される。
【００１４】
このとき、eor_11〜eor_13から見たscan_1〜3のトポロジー的な可制御性は、回路の繰り返し性のため同一であり、かつscan_1〜scan_3は制御点自身であるため０及び１を設定することの制御性は対称であり同一であるために、故障ｆ１１に対するテスト生成において、従来のダイナミックコンパクションのＡＴＧで用いられる可制御／可観測性基準はマッチコンペア部のＥＯＲゲートの制御に関して何らの選択基準を示さないことになる。
【００１５】
そのため、故障ｆ１１に関して、故障励起のために nsl_11 = 1以外のnsl_12，nsl_13に関して、選択基準が示されないために、偶然にしてnsl_12 = nsl_13 = 0を割り当ててテストを成功とする可能性がある。なお、これらのnsl_12，nsl_13への０割り当ての可能性は、乱数動作であるrotating back traceであっても同様である。
さらに、図１５において、nsl_12 = nsl_13 =０のステートが割り当てられた故障ｆ１１のテストパターン生成後に、故障ｆ１２、ｆ１３が二次故障になる状況を考えると、故障ｆ１１を励起したタイムプレーン上では、もはや故障ｆ１２，ｆ１３の仮定されるネット状態が故障値（０）と等しくなるため励起不可能となる。
【００１６】
従って、ダイナミックコンパクションは、故障ｆ１２を二次故障としてターゲットにしたときに、故障ｆ１１を故障励起したタイムプレーンとは異なるタイムプレーンを拡張して故障ｆ１２の故障励起を行なってテストパターン生成を行なうことになる。
そして、故障ｆ１１に対するテストパターン生成と同様に、従来のダイナミックコンパクション手法では、故障ｆ１２に対するテストにおいてnsl_13 = 0を割り当てる可能性があり、故障ｆ１１〜ｆ１３の故障に対する故障励起で３つの異なるタイムプレーンを用いることになる。つまりは、前述のように理想的なテストであるならば、故障ｆ１１〜ｆ１３の故障励起／伝搬を１つのタイムプレーンで実現可能なのに対して、従来のダイナミックコンパクション手法では、図１７に示すように、最悪のケースでタイムプレーンが３つに増加する。そして、ここでのタイムプレーンの増加はテストパターンの増加を意味し、すなわち、パターン圧縮の効率が低下する。
【００１７】
従って、従来のダイナミックコンパクション手法においては、ＡＴＧで用いられる可制御／可観測性基準では回路の繰り返し性及び対称性により、ＥＯＲを含む回路（図１５のマッチコンペア部１０３参照）でのステート選択に関する基準を与えることができないおそれがある。
（２）エントリ方向に排他性の高いＲＡＭ，ＲＦに関する制御について
図１８は図１５のエントリ＃１，＃２の故障ｆ１１〜ｆ１３，ｆ２１〜ｆ２３検出における理想テストの例を示す図、図１９はその最悪テストの例を示す図である。
【００１８】
上述したＥＯＲを含む組み合わせ回路に関する制御は、同じエントリ内の故障（図１５の故障ｆ１１〜ｆ１３参照）について発生する可能性パターン増加に関するものであるが、その最悪のケース（最悪テスト；図１７参照）として示したように各々の故障励起に対して異なるタイムプレーンを用いる場合（図１５の故障ｆ１１〜ｆ１３の故障励起に３つのタイムプレーンを用いるような場合）では、エントリ方向でのwriteに関する排他性により、パターン増加は他のエントリにまで渡って影響を及ぼす可能性がある。
【００１９】
何故なら、ＣＡＭ／ＴＬＢにあるＲＦは元より、一般のＲＦ，ＲＡＭであっても１サイクルでwrite可能なエントリ数は保持するエントリ数に比べて小さいのが一般的である。即ち、極端なケースとして１クロックでwrite可能なエントリが１つであるようなＣＡＭ／ＴＬＢのＲＦを考えた場合には、エントリ＃１のＮＳＬへの書き込みを行なっているタイムプレーン（図１６の時刻（ｔ），図１７の時刻（ｔ）〜（ｔ＋２））では、＃１以外のエントリのＮＳＬへの書き込みは不可能である。
【００２０】
つまりは、エントリ間のwriteに関わる排他性が高い場合には、１つのエントリにおいてＮＳＬにwriteを行なう時刻では、他のエントリにおけるＮＳＬのwriteが不可能となるために、ある着目エントリの故障に対して多くのタイムプレーンを用いてＮＳＬにwriteを行なうことは、そのまま非着目であるエントリでのＮＳＬのwriteを阻害することになり、全体としてテストパターンが増加することを意味し、パターン圧縮の効率が低下する（図１８および図１９参照）。
【００２１】
従って、例えば、時刻tにおいてＮＳＬがＪフロンティアになるとき、その要求値を満たすためには過去時刻（t-n、n>1）において、
write動作：C lock=ON且つDin=要求値
set動作：Set= ON （ただし、Set値が要求値）
reset動作：Reset=ON（ただし、Reset値が要求値）
の各動作を行ない、ＮＳＬのステートを要求値に設定する必要がある。
【００２２】
しかしながら、上述したように、エントリ方向でのwrite排他性が高い場合には、ある１つのエントリのＮＳＬへのwriteを行なっている時刻では、他のエントリのＮＳＬへのwriteが不可能となる可能性があり、一つのエントリに対して何らの考慮もなく多くのタイムプレーンを費やすことは全体としてテストパターンの増加を招くおそれがある。
本発明は、このような課題に鑑み創案されたもので、例えば、プロセッサ内部に構成されるno scan-ableな記憶素子、および繰り返し対象性の高い組み合わせ回路やＥＯＲを含む組み合わせ回路に対して、テストパターンの増加を抑制して効果的にダイナミックコンパクションを行なうことができるようにすることを目的とする。
【課題を解決するための手段】
【００２３】
このため、本発明のテストパターン生成方法（請求項１）は、ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴としている。
【００２４】
また、本発明のテストパターン生成方法（請求項２）は、ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴としている。
【００２５】
なお、該テストパターン生成ステップにおいて、前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意するステップと、前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するステップとをそなえてもよい（請求項３）。
【００２６】
また、本発明のテストパターン生成プログラム（請求項４）は、ＥＯＲ（exc lusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴としている。
【００２７】
さらに、本発明のテストパターン生成プログラム（請求項５）は、ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴としている。
【発明の効果】
【００２８】
本発明によれば、テストパターン数を低減し効率的にパターン圧縮済印刷データを行なうことができる
【発明を実施するための最良の形態】
【００２９】
以下、図面を参照して本発明の実施の形態を説明する。
図１は本発明の一実施形態としてのテストパターン生成方法を実現する電子回路用試験システムの構成を模式的に示す図である。
電子回路用試験システム１は、試験対象の電子回路（以下、単に電子回路という）の出力パターンに応じてその電子回路の故障を検出するものであり、図１に示すように、テストパターン生成装置２および試験装置４をそなえて構成されている。
【００３０】
テストパターン生成装置２は、本発明の一実施形態としてのテストパターン生成方法によって電子回路に供給するテストパターンを生成するものであり、図１に示すように、レイアウト情報記憶部１１，プログラムメモリ１２，処理部１３，作業用メモリ（保持部）１４，入出力部１６，入力装置１７及びディスプレイ１８をそなえて構成されている。
レイアウト情報記憶部１１は、テスト対象のレイアウト情報を記憶するものであり、プログラムメモリ１２はテストパターン生成用のプログラムを格納するものである。作業用メモリ（保持部）１４は、後述する処理部１３の処理における中間結果などを記憶するものであり、又、ＮＳＬ（No Scan Latch）における複数種類のタイムプレーンでのステートをそれぞれ保持するようになっている。入出力部１６は命令及びデータなどの入出力を行なうものである。入力装置１７は、入出力部１６を介して命令、データを入力するものであり、ディスプレイ１８は、データの表示などを行なうものである。
【００３１】
処理部１３は、レイアウト情報記憶部１１に記憶されたレイアウト情報に応じてテストパターンを生成するものであり、プログラムメモリ１２に格納されたプログラムにより処理が実行される。具体的には、例えば、本テストパターン生成装置２はＣＰＵをそなえた情報処理装置（コンピュータシステム）として構成され、このＣＰＵがプログラムメモリ１２に格納されたプログラム（テストパターン生成プログラム）を実行することにより、処理部１３としての機能（計数部２１，選択部２２，保持制御部２３およびテストパターン生成部２５；詳細は後述）が実現される。
【００３２】
なお、これらの計数部２１，選択部２２，保持制御部２３およびテストパターン生成部２５としての機能を実現するためのプログラム（テストパターン生成プログラム）は、例えばフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。
【００３３】
計数部２１，選択部２２，保持制御部２３およびテストパターン生成部２５としての機能を実現する際には、内部記憶装置（本実施形態ではコンピュータシステムのＲＡＭやＲＯＭ）に格納されたプログラムがコンピュータのマイクロプロセッサ（本実施形態ではコンピュータのＣＰＵ）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。
【００３４】
なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、テストパターン生成装置２がコンピュータとしての機能を有しているのである。
【００３５】
さらに、本実施形態における記録媒体としては、上述したフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスクのほか、ＩＣカード，ＲＯＭカートリッジ，磁気テープ，パンチカード，コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ），外部記憶装置等や、バーコードなどの符号が印刷された印刷物等のコンピュータ読取可能な種々の媒体を利用することができる。
【００３６】
処理部１３は、図１に示すように、計数部２１，選択部２２，保持制御部２３およびテストパターン生成部２５として機能するようになっている。
計数部２１は、ＥＯＲ（exclusive OR）ゲートを有する検査対象の電子回路において、ＥＯＲゲートがＤフロンティア（D frontier）もしくはＪフロンティア（J frontier）になるとき、ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数するものである。
【００３７】
選択部２２は、計数部２１による計数結果に基づいて、０および１のうち検出不可能となる故障数が少なくなる方のステートを入力ピンに割り当てる状態として選択するものである。保持制御部２３は、ＮＳＬ（No Scan Latch）における複数種類のタイムプレーンでのステートを、それぞれ作業用メモリ１４等に保持させるように制御するようになっている。
【００３８】
テストパターン生成部２５は、選択部２２によって選択されたステートに基づいてテストパターンを生成するものであり、又、ＮＳＬが時刻tにおいてＪフロンティアになるときに、作業用メモリ１４において保持された、複数種類のタイムプレーンでのステートを検索して、時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるようにテストパターンを生成するものである。
【００３９】
さらに、このテストパターン生成部２５は、複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、その着目ＮＳＬのクロック端子からON値を含意（インプリケーション）し、複数のＮＳＬのうち着目ＮＳＬ以外のＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するようになっている。
【００４０】
試験装置４は、本テストパターン生成装置２で生成されたテストパターンに応じて電子回路を試験するものである。
以下、プロセッサ（processor）内部に構成されるno scan-ableな記憶素子、および繰り返し対象性の高い組み合わせ回路やＥＯＲを含む組み合わせ回路に対して、効果的なダイナミックコンパクション（dynamic compaction）手法について説明する。
【００４１】
なお、Ｊフロンティア（J frontier；Justify frontier）とは、出力に要求値が存在し、入力に２つ以上のX（不定値）が存在するために入力値の設定に選択が必要な未解決なゲートを表わし、Ｄフロンティア（D frontier；Different frontier）とは、入力の少なくとも１つに正常値と故障値に差異D（different）が存在し、その他の入力に１つ以上のXが存在するためにD伝播が不明な未解決なゲートを表わす。又、デシジョン（decision）とは、上述したＪフロンティア／Ｄフロンティアを解決するためにＡＴＧが入力に与えるステートを選択することをいう。
【００４２】
（Ａ）ＥＯＲを含む組み合わせ回路での解ステート（state）選択について
本テストパターン生成装置２においては、ＥＯＲゲート（図１５に示す電子回路の例においてはマッチコンペア部１０３）がＤ／Ｊフロンティアになるとき、ＥＯＲの個々のインプットピン（input pin）に与える０もしくは１のステートにより検出不可能となる故障数が少なくなるステートをインプットピンに割り当てるステートとして選択するようになっている。
【００４３】
すなわち、処理部１３において、計数部２１がＥＯＲの個々のインプットピン（input pin）に付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数し、選択部２２が、これらの計数結果に基づいて、検出不可能となる故障数が少なくなる方のステートをインプットピンに割り当てるステートとして選択するようになっている。
【００４４】
以下に、本発明の一実施形態としてのテストパターン生成方法におけるステート選択手法の具体例を示す。なお、以下に示す例においては、計数部２１は、0含意で検出不可能となる故障数をカウンタundetectable[0]を用いて、又、１含意で検出不可能となる故障数をカウンタundetectable[1]を用いて、それぞれ計数するようになっている。
step 1
D/J frontier であるEORのうちstateがXなinput pinを１つ選択。
/* 0 選択 */
step 2-1
0含意で検出不可能となる故障数 undetectable[0] = ∞に初期化。
step 2-2
step 1で選択したinput pinに0を含意。
step 2-2
step 2-2で矛盾が生じるならばstep 3-1へ。
step 2-3（計数ステップ）
undetectable[0]をfunction 1（後述）によりカウント。
step 2-4
step 2-2の含意をrecover。
/* 1選択 */
step 3-1
1含意で検出不可能となる故障数undetectable[1] = ∞に初期化。
step 3-2
step 1で選択したinput pinに1を含意。
step 3-2
step 3-2で矛盾が生じるならばstep 4へ。
step 3-3（計数ステップ）
undetectable[1]をfunction 1によりカウント。
step 3-4
step 3-2の含意をrecover。
/* 解ステート決定 */
step 4（選択ステップ）
if undetectable[0]> undetectable[1]
then state = 1を選択。
【００４５】
if undetectable[1]>undetectable[0]
then state = 0を選択
if undetectable[0]= undetectable[1]
then state = 0か1を選択。
function 1
・counter = 0に初期化
・含意操作によりstateが決定されたnetに関して以下を繰り返し
/* 故障励起不可能のカウント */
if
((含意された正常値stateが0)
かつ(未検出の０故障が存在))
あるいは
((含意された正常値stateが1)
かつ(未検出の１故障が存在))
then
cou nterをインクリメント。
【００４６】
/* 故障伝播不可能のカウント */
if
((含意された正常値stateが0)
かつ(netがAND gateのinput pin))
あるいは
((含意された正常値stateが1)
かつ(netがOR gateのinput pin))
then
着目しているinput pin以外からFFR (Fan-out Free Region)をback traceしtrace cone内に存在する未検出故障数をcounterに加算。
【００４７】
・counter値を復帰値として返す。
次に、本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を図２〜図８および図１５を参照しながら説明する。なお、図２は故障ｆ１１をprimary faultとするときに必須ステートとして決定可能なステートを割り当てた状態を示す図、図３は図１５に示す電子回路におけるＤフロンティア解決のために０を含意したときのステートを示す図、図４は図１５に示す電子回路におけるＤフロンティア解決のために１を含意したときのステートを示す図、図５は図１５に示す電子回路における１を含意したステートを示す図、図６は図１５に示す電子回路におけるnsl_12を０に含意したステートを示す図、図７は図１５に示す電子回路におけるnsl_12を１に含意したステートを示す図、図８は図１５に示す電子回路におけるフロンティアＤ１，Ｊ１，Ｊ２が解決したステートを示す図である。
【００４８】
なお、図２においてはＡＴＧのデシジョン対象となるＤフロンティア（Ｄ１：eor_11）、Ｊフロンティア（Ｊ１：eor_12，Ｊ２：eor_13）が存在する例を示しており、以下、本テストパターン生成装置２によるフロンティアＤ１，Ｊ１，Ｊ２でのステート選択手法を示す。
（１）Ｄフロンティア（Ｄ１：eor_11）でのステート選択
step 1
Ｄ１にはＸなステートをもつinput pinが１つ存在している。
step 2-1〜2-2
次にinput pinに０を含意する。なお、含意によりステートが決定されるnetを図３中に太線で示す。
step 2-3
上記function１によれば、step 2-2の含意によりand_1のinput netの１つ（n11）に0なる正常値が決定されるので、n12〜n13 から back traceが実行されｆ１２、ｆ１３の２つの故障が検出不可能故障としてカウントされ、undetectable[0]=２が設定される。
step 3-1〜3-2
次にinput pinに１を含意する。なお、含意によりステートが決定されるnetを図４に太線で示す。
step 3-3
上記function１によれば、step 3-2の含意により検出不可能故障としてカウントされる故障は存在せず、undetectable[1]=０が設定される。
step 4
undetectable[0] > undetectable [1]であることより、Ｄ１を解決するためのステートとしては１が選択される。なお、このstep 4で選択された１を含意したステートを図５に示す。
【００４９】
次に、図５に示したようにＤ１を解決した状態におけるＪ１，Ｊ２についてのステート選択の動作を説明する。
（２）Ｊフロンティア（Ｊ１： eor_12，Ｊ２： eor_13）でのステート選択
step 1
Ｊ１にはＸなステートをもつinput pinが２つ存在しているので、どちらか１つを選択する。なお、ここではnsl_12によりドライブされるinputを選択するものとする。
step 2-1〜2-2
次にinput pinに０を含意する。なお、含意によりステートが決定されるnetを図６に太線で示す。
step 2-3
上記function１によれば、step 2-2の含意によりnsl_12の出力が０に含意されるので、ｆ１２の故障が検出不可能故障としてカウントされ、 undetectable[0]=１が設定される。
step 3-1〜3-2
次にinput pinに１を含意する。なお、含意によりステートが決定されるnetを図７に太線で示す。
step 3-3
上記function１によれば、step 3-2の含意により検出不可能故障としてカウントされる故障は存在せず、undetectable[1]=０が設定される。
step 4
undetectable[0] > undetectable[1]であることより、Ｊ１を解決するためステートとしては１が選択される。
【００５０】
なお、同様にＪ２についても解決のためのnsl_13 のステートは１が選択されるのである。
上述の如き処理により、図８に示すように、本発明の一実施形態としてのテストパターン生成装置２によって、各フロンティアＤ１，Ｊ１，Ｊ２のステートが決定される。そして、テストパターン生成部２５は、このようにして決定（選択）されたステートに基づいてテストパターンの生成を行なう（テストパターン生成ステップ）。
【００５１】
このように、本テストパターン生成装置２により、故障ｆ１１〜ｆ１３に関して全ての故障を１つのタイムプレーンで同時に励起／伝播される理想的なテストパターンを生成することができる。
（Ｂ）エントリ方向に排他性の高いＲＡＭのwrite制御について
本テストパターン生成装置２においては、write に関して排他性のあるＮＳＬが時刻tにおいてＪフロンティアになるとき、タイムプレーンを過去の時刻方向、即ち（t-n，n>1）時刻方向に探索していき、時刻tの要求を満たせる過去時刻のタイムプレーンのうち最も古い時刻のタイムプレーンでwrite動作を行なうようになっている。
【００５２】
すなわち、作業用メモリ１４がＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持し（保持ステップ）、テストパターン生成部２５が、そのＮＳＬが時刻tにおいてＪフロンティアになるときに、作業用メモリ１４によって保持された複数種類のタイムプレーンでのステートを検索して、時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト（write）動作を行なわせるようになっている。
【００５３】
さて、時刻tにおいてＮＳＬがＪフロンティアになるとき、その要求値を満たすためには過去時刻（t-n，n>1）において、
write動作：
Clock=ONかつDin=要求値
set動作：
Set= ON (ただし、Set値が要求値)
reset動作：
Reset=ON(ただし、Reset値が要求値)
の動作を行ないＮＳＬのステートを要求値に設定する必要がある。
【００５４】
さて、エントリ方向でのwrite排他性が高い場合には、ある１つのエントリのＮＳＬへのwriteを行なっている時刻では他のエントリのＮＳＬへのwriteが不可能となるかもしれず、一つのエントリに対して何らの考慮もなく多くのタイムプレーンを費やすことは全体としてテストパターンの増加を招くおそれがある。
そこで、以下に示すようなwrite制御を行なうことにより、エントリ方向でのwrite排他性が高いＮＳＬに関して、必要以上のwrite動作を行なうことなく、他のエントリへwrite 動作を振り分けるようにテストパターンの増加を抑制する。
【００５５】
以下に、本テストパターン生成装置２におけるwrite制御手法の具体例を示す。
step 1
/*
時刻tにおいてＲＱなるステートを要求されるＮＳＬ（Ｊフロンティア）に関して、過去時刻（t-n、n>1）のタイムプレーンについてステート検索。
*/
時刻t' = t-1から可能な最小時刻のタイムプレーンのステートについて、
if
((Clock = ON)
かつ(Din = RQあるいはX))
あるいは
((Clock = ONあるいはX)
かつ(Din = RQ))
なステートが存在
then
探索成功フラグとその時刻(t')を記録。
【００５６】
if
(Clock = ON)かつ(Din = inv[RQ])なステートが存在
then
探索失敗フラグを記録して探索を終了。
step 2
if
成功フラグが記録されている
then
時刻（t'）において
ＮＳＬのClock = ON，Din = RQ を
時刻（t-n+1〜t-1）において
ＮＳＬのClock = OFFを
設定し時刻（t）でのＪフロンティアを解決。
step 3
if
失敗フラグが記録されている
then
時刻（t-1）において
ＮＳＬのclock = ON，Din = RQ
を設定し時刻（t）でのＪフロンティアを解決。
【００５７】
次に、本発明の一実施形態としてのテストパターン生成方法におけるＮＳＬのwrite制御手法を図９（ａ），（ｂ）を参照しながら説明する。なお、図９（ａ）はＮＳＬにおける複数のタイムプレーンでのステートを示す図、図９（ｂ）は図９（ａ）に示すＪフロンティアを解決するために設定されたステートを示す図である。又、図９（ａ）中においては、時刻（t）においてＮＳＬにＲＱなる要求が存在するときに、時刻（t-1）までのステートによってそのＮＳＬの状態が設定されないためＪフロンティアが発生している様子を示している。
step 1
図９（ａ）において時刻（t-1）から過去時刻に向けてタイムプレーン探索を行ない、
過去時刻（t-3）にて、
(Clock = ONかつDin = X)
を満たすwrite可能ステートが存在するので、探索成功フラグが記録される。
step 2
step 1にて探索成功フラグが設定されているので、
(t-3)  Clock = ＯＮ，Din =ＲＱ
(t-2)  Clock = ＯＦＦ
(t-1)  Clock = ＯＦＦ
が設定され、時刻（t）でのＪフロンティアが解決される。なお、図９（ｂ）中に本stepにより設定されるステートを太線で示す。
step 3
step 1にて探索失敗フラグが設定されていないので本stepは実行されない。
【００５８】
図１０は図１５に示す電子回路における故障ｆ１１〜ｆ１３を検出するための最小テストの例を示す図である。
さて、図１０中において、エントリ＃１に関わるｆ１１〜ｆ１３の故障の他にマッチコンペア部１０３にある故障ｆ１４なるsecondary fault（図示省略）を検出することを考える。
【００５９】
上述の如く、図１０に示したステートがエントリ＃１の故障ｆ１１〜ｆ１３を同時に検出する最小テストであるが、このテストでは、ｎ１１のステートがｆ１４の故障値と等しく故障励起されないため、ｆ１４を検出することは出来ず、これにより、ｆ１４の故障励起は（t +1）ではない他の時刻を用いる必要がある。
ここではｆ１１〜ｆ１３の励起／伝播を行なっている時刻（t+1）より以降の時刻、即ち、（t+2）以降の時刻においてｆ１４の故障励起を行なうことを考える。
【００６０】
図１１は図１５に示す電子回路のエントリ＃１のnsl_11〜nsl_13の各時刻（t〜t+2）におけるステートの詳細を示す図、図１２は故障ｆ１４を検出するテストでのnsl_11〜nsl_13のステートを示す図である。
故障ｆ１４の励起／伝播はn11 = 0，n12 = n13 = １なるステートが要求され、そして時刻 （t+2）ではeor_11〜eor_13を介して、時刻t+1でのClockがＸであるので、nsl_11〜nsl_13がＪフロンティアとなる。
【００６１】
このとき、Ｊフロンティアであるnsl_11〜nsl_13対して１を要求する選択を行なうとするならば、Ｊフロンティア解決には時刻（t+1）においてClock =ＯＮかつDin =１とするステート割り当ても考えられるが、Ｊフロンティア（ＮＳＬ）のwrite制御によっては、図１２に示すように、時刻（t+1）においてエントリ＃１のnsl_11〜nsl_13をhold状態とするステートが割り当てられる。
【００６２】
もし仮に、時刻（t+1）においてClock =ＯＮかつDin =１のステート割り当てを行なうことは、時刻（t）と同様のwrite動作を繰り返すこととなり、かつ時刻（t+1）ではエントリ＃１以外のＮＳＬでのwriteが不可能となるために、図１９に示した最悪テストと類似してテストパターンが増加することになる。
一方、本発明の一実施形態としてのテストパターン生成装方法におけるＮＳＬのwrite制御手法によれば、時刻（t+1）において、エントリ＃１のＮＳＬをhold状態にする制御が行われるので、他のエントリ（＃２以降）でのwrite動作が可能となるために、図１９に示した最小テストと類似してテストパターンの増加を抑制する効果がある。
【００６３】
（Ｃ）ＲＡＭのエントリ方向での排他性の認識について 
本テストパターン生成装置２においては、テストパターン生成部２５は、任意の１つのＮＳＬに着目し、この着目ＮＳＬのClock端子からＯＮ値を含意し、着目ＮＳＬ以外でClock端子にＯＦＦ値が到達するＮＳＬが存在するならば、ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するようになっている。
【００６４】
さて、エントリ間でwriteに関する排他性の高いＲＡＭ，ＲＦに対するダイナミックコンパクション手法において、テストパターン生成に対して最もシビアな影響をもつ排他性は1 entry write／１ 1clockの制御がなされる場合である。
以下、特に１entry write／1 clock制御である場合のエントリ間の排他性を認識するための具体的な手法を説明する。
step 1
任意のＮＳＬを選択。（以下、この選択したＮＳＬを注目ＮＳＬという。）
step 2
注目ＮＳＬのClock端子にＯＮ値を含意する。
step 3
上記step 1で選択した注目ＮＳＬ以外のＮＳＬ（以下、他ＮＳＬという）でのClock端子にＯＦＦ値が含意されるならば、注目ＮＳＬと他ＮＳＬとのそれぞれを排他性ＮＳＬとしてマーク（排他性マークを付与）する。
step 4
回路内の全てのＮＳＬの処理を完了、もしくは全てのＬＳＬに排他性マークが付与されるまで、上記step 1〜step3を繰り返し行なう。
【００６５】
次に、本発明のテストパターン生成方法におけるＮＳＬ間の排他性の認識手法を図１３，図１４および図１５を参照しながら説明する。なお、図１３はwrite entry decoderの例を示す図であり、４つのエントリをもつ1 entry write／1 clock、即ち、hard de-codedであるwrite entry decoderを示している。又、図１４は図１３に示すwrite entry decoderのnsl#1のClock端子＝ＯＮから含意されるステートの例を示す図である。
step 1
着目ＮＳＬとして、#1のＮＳＬ（nsl#1）を選択 。
step 2
nsl#1のClock 端子にＯＮ値を含意する（図１４参照）。
step 3
Clock=ＯＦＦが含意されるnsl#2，nsl#3，nsl#4および着目nsl#1を排他性ＮＳＬとしてマークする。
step 4
nsl#1〜nsl#4の全てに排他性マークがついたので終了。
【００６６】
上述したように、本手法によれば、1 entry write／1 clockであるようなhard de-codedされるwrite entry decoderであるならば、回路に冗長性がないので、１つのエントリのＮＳＬのClockをＯＮにする含意により、他のエントリのＮＳＬのClockにはＯＦＦが含意されるために、本発明の手段により容易にエントリ間の排他性を認識することが可能である。
【００６７】
そして、本発明は上述した実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
例えば、上述した実施形態においては、no scan-ableな記憶素子と繰り返し対象性の高い組み合わせ回路、およびＥＯＲを含む組み合わせ回路のそれぞれを含む回路の一例として、ＣＡＭ（Content Address-able Memory）によるaddress mappingを実装とするＴＬＢ（Translation Look-aside Buffer）構成を用いて説明するが、本発明はこのようなＣＡＭ／ＴＬＢ構成に限定されるものではなく、例えば、ＥＯＲを含む組み合わせ回路全般とエントリ（entry；address）間でのwrite排他性の高いＲＡＭ，ＲＦ全般を対象とする回路に含むことができる。
【００６８】
また、上述した実施形態においては、ＥＯＲを含む組み合わせ回路（電子回路）例として、ＣＡＭ／ＴＬＢにあるマッチコンペア部１０３（図１５参照）に着目して説明しているが、これに限定されるものではない。すなわち、ＡＴＧでの解ステートの選択は個々のＥＯＲゲートに着目し、０，１をそれぞれ解ステートとしたときの検出不可能となる故障数に基づいて選択肢を決定するようにしており、組み合わせ回路にある全てのＥＯＲに対して実施することができる。従って、本発明のテストパターン生成方法を、例えば、ＥＣＣにあるパリティチェック回路や加算／乗算などの演算器でのキャリィ（carry）演算等、ＥＯＲを含む組み合わせ回路全般に対して適用することができる。
【００６９】
さらに、上述した実施形態においては、エントリ方向でのwrite排他性の高いＲＦの例として、ＣＡＭ／ＴＬＢ構成にあるメモリ部１０２（NSL array；図１５参照）に着目して説明しているが、これに限定されるものではない。すなわち、ＡＴＧでのwrite制御をＲＦ（NSL array）にある個々のＮＳＬもしくはＲＡＭ内部のセル（cell）に着目してwrite動作の重複を回避するようにしており、ＲＦ，ＲＡＭにある全てのＮＳＬもしくはセルに対して適用することができる。従って、本発明のテストパターン生成方法を、write addressによりエントリが選択的に決定されwrite clockもしくはwrite enable信号により書き込みが行われる一般的なＲＦ，ＲＡＭ全般に対して適用することができる。
【００７０】
また、上述した実施形態においては、write entry de-coderを有するＲＦの例としてＣＡＭ／ＴＬＢ構成にあるメモリ部１０２（NSL array；図１５参照）に着目して説明しているが、これに限定されるものではない。すなわち、write address decoderにおいて選択エントリを決定する際に必然的に非選択が決定されるエントリに着目しwrite排他性を認識するようにしており、write entry（もしくはaddress）de-coderを有する全てのＲＦ，ＲＡＭに対して適用することができる。従って、本発明のテストパターン生成方法を、write addressにより書き込むエントリが選択的に決定される一般的なＲＡＭ，ＲＦ全般に対して適用することができる。
【００７１】
そして、本発明は、以下に示すように要約することができる。
（付記１）  ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴とする、テストパターン生成方法。
【００７２】
（付記２）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴とする、テストパターン生成方法。
【００７３】
（付記３）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有するとともにＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成方法であって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該選択ステップにおいて選択されたステートに基づくとともに、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；J ustify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとをそなえることを特徴とする、テストパターン生成方法。
【００７４】
（付記４）  該テストパターン生成ステップにおいて、
前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意するステップと、
前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するステップとをそなえることを特徴とする、付記２又は付記３記載のテストパターン生成方法。
【００７５】
（付記５）  ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成装置であって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数部と、
該計数部による計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択部と、
該選択部によって選択された状態に基づいて該テストパターンを生成するテストパターン生成部とをそなえることを特徴とする、テストパターン生成装置。
【００７６】
（付記６）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成装置であって、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持部と、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持部において保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成部とをそなえることを特徴とする、テストパターン生成装置。
【００７７】
（付記７）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有するとともにＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する電子回路用テストパターン生成装置であって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数部と、
該計数部による計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択部と、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持部と、
該選択部によって選択されたステートに基づくとともに、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成部とをそなえることを特徴とする、テストパターン生成装置。
【００７８】
（付記８）  該テストパターン生成部が、
前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意し、
前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識することを特徴とする、付記６又は付記７記載のテストパターン生成装置。
【００７９】
（付記９）  ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラム。
【００８０】
（付記１０）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラム。
【００８１】
（付記１１）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有するとともにＥＯＲ（exc lusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムであって、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該選択ステップにおいて選択されたステートに基づくとともに、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラム。
【００８２】
（付記１２）  該テストパターン生成ステップを該コンピュータに実行させる際に、
前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意するステップと、
前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するステップとを該コンピュータに実行させることを特徴とする、付記１０又は付記１１記載のテストパターン生成プログラム。
【００８３】
（付記１３）  ＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体であって、
該テストパターン生成プログラムが、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該選択ステップにおいて選択されたステートに基づいて該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体。
【００８４】
（付記１４）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体であって、
該テストパターン生成プログラムが、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体。
【００８５】
（付記１５）  ライト（write）に関して排他性のあるＮＳＬ（No Scan Latch）を複数有するとともにＥＯＲ（exclusive OR）ゲートを有する電子回路について、当該電子回路の出力パターンに応じて該電子回路の故障を検出するために該電子回路に供給するテストパターンを生成する機能をコンピュータに実行させるための電子回路用テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体であって、
該テストパターン生成プログラムが、
該ＥＯＲゲートがＤフロンティア（D frontier；Different frontier）もしくはＪフロンティア（J frontier；Justify frontier）になるとき、該ＥＯＲゲートの個々の入力ピンに付与可能な０および１の各ステートについて、検出不可能となる故障数をそれぞれ計数する計数ステップと、
該計数ステップによる計数結果に基づいて、前記０および１のうち前記検出不可能となる故障数が少なくなる方のステートを該入力ピンに割り当てるステートとして選択する選択ステップと、
該ＮＳＬにおける複数種類のタイムプレーンでのステートをそれぞれ保持する保持ステップと、
該選択ステップにおいて選択されたステートに基づくとともに、該ＮＳＬが時刻tにおいてＪフロンティア（J frontier；Justify frontier）になるときに、該保持ステップにおいて保持された、前記複数種類のタイムプレーンでのステートを検索して、該時刻tにおける要求を満たす過去時刻のタイムプレーンのうち最も古いタイムプレーンでライト動作を行なわせるように該テストパターンを生成するテストパターン生成ステップとを該コンピュータに実行させることを特徴とする、テストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体。
【００８６】
（付記１６）  該テストパターン生成プログラムが、
該テストパターン生成ステップを該コンピュータに実行させる際に、
前記複数のＮＳＬのうち一のＮＳＬである着目ＮＳＬについて、当該着目ＮＳＬのクロック端子からON値を含意するステップと、
前記複数のＮＳＬのうち該着目ＮＳＬ以外の該ＮＳＬにおいて、クロック端子にＯＦＦ値が到達するＮＳＬが存在する場合に、前記ＯＮ値を含意した着目ＮＳＬとＯＦＦ値が到達するＮＳＬとの間に排他性があると認識するステップとを該コンピュータに実行させることを特徴とする、付記１４又は付記１５記載のテストパターン生成プログラムを記録したコンピュータ読取可能な記録媒体。
【図面の簡単な説明】
【００８７】
【図１】本発明の一実施形態としてのテストパターン生成方法を実現する電子回路用試験システムの構成を模式的に示す図である。
【図２】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図３】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図４】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図５】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図６】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図７】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図８】本発明の一実施形態としてのテストパターン生成方法によるステート選択手法を説明するための図である。
【図９】（ａ），（ｂ）は本発明の一実施形態としてのテストパターン生成方法におけるＮＳＬのwrite制御手法を説明するための図である。
【図１０】図１５に示す電子回路における故障ｆ１１〜ｆ１３を検出するための最小テストの例を示す図である。
【図１１】図１５に示す電子回路のエントリ＃１のnsl_11〜nsl_13の各時刻（t〜t+2）におけるステートの詳細を示す図である。
【図１２】故障ｆ１４を検出するテストでのnsl_11〜nsl_13のステートを示す図である。
【図１３】本発明のテストパターン生成方法におけるＮＳＬ間の排他性の認識手法を説明するための図である。
【図１４】本発明のテストパターン生成方法におけるＮＳＬ間の排他性の認識手法を説明するための図である。
【図１５】ＣＡＭ（Content Address-able Memory）／ＴＬＢ（Translation Look-aside Buffer）構成をそなえる回路の例を部分的に示す図である。
【図１６】図１５のエントリ＃１の故障ｆ１１〜ｆ１３検出における理想テストの例を示す図である。
【図１７】図１５のエントリ＃１の故障ｆ１１〜ｆ１３検出における最悪テストの例を示す図である。
【図１８】図１５のエントリ＃１，＃２の故障ｆ１１〜ｆ１３，ｆ２１〜ｆ２３検出における理想テストの例を示す図である。
【図１９】図１５のエントリ＃１，＃２の故障ｆ１１〜ｆ１３，ｆ２１〜ｆ２３検出における最悪テストの例を示す図である。
【符号の説明】
【００８８】
１    電子回路用試験システム
２    テストパターン生成装置
４    試験装置
１１  レイアウト情報記憶部
１２  プログラムメモリ
１３  処理部
１４  作業用メモリ（保持部）
１６  入出力部
１７  入力装置
１８  ディスプレイ
２１  計数部
２２  選択部
２３  保持制御部
２５  テストパターン生成部
１０１  キー部
１０２  メモリ部
１０３  マッチコンペア部
【図１】
2006010641.tif 000003
【図２】
2006010641.tif 000004
【図３】
2006010641.tif 000005
【図４】
2006010641.tif 000006
【図５】
2006010641.tif 000007
【図６】
2006010641.tif 000008
【図７】
2006010641.tif 000009
【図８】
2006010641.tif 000010
【図９】
2006010641.tif 000011
【図１０】
2006010641.tif 000012
【図１１】
2006010641.tif 000013
【図１２】
2006010641.tif 000014
【図１３】
2006010641.tif 000015
【図１４】
2006010641.tif 000016
【図１５】
2006010641.tif 000017
【図１６】
2006010641.tif 000018
【図１７】
2006010641.tif 000019
【図１８】
2006010641.tif 000020
【図１９】
2006010641.tif 000021