(57)【要約】    【課題】  ３重みＷＲＰＴ  ＢＩＳＴ（ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ及びスキャン方式）におけるテストシーケンス長及びハードウェア・オーバーヘッドを削減する。    【解決手段】  検出困難故障用のテスト・セットを生成するための方法であって、検出困難故障セットを識別し、検出困難故障用のテスト・セットを、改良型の自動テスト・パターン生成器を使用して生成し、改良型自動テスト・パターン・生成器を、ハードウェア・オーバーヘッドとテスト・シーケンス長を考慮できるように適用し、ハードウェア・オーバーヘッドは、新規のテストキューブがテスト・セットに追加される際に発生させることを特徴とする。【選択図】    図１
2004301856.tif 000002
【特許請求の範囲】
【請求項１】
並列型スキャン方式ビルトイン・セルフテスト回路において、
入力を備えるテスト中の回路と、
各スキャン・フリップフロップの各々は少なくとも同期リセット（Ｒ）ピンまたは同期プリセット（Ｓ）ピンを有する、入力に接続されるスキャン・フリップフロップ・セットと、
スキャン・フリップフロップ・セットに入力を供給するランダム・ベクトルをロードするための線形フィードバックシフトレジスタと、
グローバル生成器の機能を備え、前記スキャン・フリップフロップ内のＲ及びＳピンを制御するデコーダ出力を供給するデコーダと、
前記デコーダ出力の状態を決定する前記デコーダに入力を供給するカウンタと、
前記デコーダ用のイネーブル信号の入力手段を備え、
前記デコーダはＲ及びＳピンへの入力を制御することによりＲ及びＳピンにオーバーライド信号を供給し、前記オーバーライド信号は困難な故障用テストパターンの生成器内のテストに基づいてランダム・ベクトルをオーバーライドし、前記テストは自動テストパターン生成器によって生成することを特徴とするスキャン方式ビルトイン・セルフテスト回路。
【請求項２】
前記イネーブル信号は、オーバーライド・イネーブル入力信号及び最終スキャン入力信号に対してＡＮＤ演算を実行するＡＮＤゲートによって供給されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項３】
「１」の入力をオーバーライド・イネーブル入力信号に供給することにより、ランダム・パターンがオーバーライドされ、ビルトインセルフテストが有効化されることを特徴とする請求項２に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項４】
最終スキャン入力信号は、各スキャン・シフト操作の最終サイクルでのみ１に設定されることを特徴とする請求項２に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項５】
前記カウンタは、初期に「０」に設定され、所定数（Ｔ）のランダム・パターンが入力されている間は「０」に維持し、前記ランダム・パターンはデコーダによって供給される生成器に基づいて変更され、前記カウンタはさらに、増分されて新規の生成器によりＴ個のランダム・パターンが適用されるようにし、前記増分はデコーダによってすべての生成器が適用されるまで反復されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項６】
マージ可能な互換のオーバーライド信号が、デコーダの同じ出力信号によって駆動され、それによりデコーダ出力数が低減されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項７】
逆互換のオーバーライド信号が、デコーダ出力によって直接駆動され、インバータを通過後にも同じデコーダ出力によって駆動されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項８】
重みセットを意味する生成器によってスキャン入力に「１」が割り当てられた場合は、対応するスキャン・フリップフロップがＳピンを有することを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項９】
重みセットを意味する生成器によってスキャン入力に「０」が割り当てられた場合は、対応するスキャン・フリップフロップがＲピンを有することを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１０】
重みセットを意味する生成器によってスキャン入力に「０」及び「１」が割り当てられた場合は、対応するスキャン・フリップフロップがＲピンとＳピンの両方を有することを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１１】
前記スキャン・フリップフロップがすでにハイ・アクティブＳピンを有し、重みセットを意味する生成器内の対応するスキャン入力に「１」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＯＲゲートが挿入されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１２】
前記スキャン・フリップフロップがすでにハイ・アクティブＲピンを有し、重みセットを意味する生成器内の対応するスキャン入力に０が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＯＲゲートが挿入されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１３】
前記スキャン・フリップフロップがすでにロー・アクティブＳピンを有し、重みセットを意味する生成器内の対応するスキャン入力に「１」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＡＮＤゲートが挿入されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１４】
前記スキャン・フリップフロップがすでにロー・アクティブＲピンを有し、重みセットを意味する生成器内の対応するスキャン入力に「０」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＡＮＤゲートが挿入されることを特徴とする請求項１に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１５】
逐次タイプのスキャン方式ビルトイン・セルフテスト回路において、
入力を備えるテスト中の回路と、
入力に接続されるスキャン・フリップフロップ・セットと、
スキャン・フリップフロップ・セットに入力を供給するランダム・ベクトルをロードするための線形フィードバックシフトレジスタと
前記線形フィードバックシフトレジスタとスキャン・フリップフロップ・セットの間に挿入されるＡＮＤゲート及びＯＲゲートと、
２個のデコーダ出力信号Ｄ０及びＤ１をＡＮＤゲート及びＯＲゲートに供給するデコーダと、
前記デコーダに入力を供給する生成器を選択する生成器カウンタと、
前記デコーダに入力を供給するスキャン・カウンタと、
前記デコーダ用のイネーブル信号の入力手段を備え、
前記デコーダ出力の状態は、前記生成器カウンタ入力及び前記スキャン・カウンタ入力の両方によって決定され、
前記デコーダは、オーバーライド信号を供給し、前記オーバーライド信号は困難な故障のテストパターン用の生成器のテストに基づいてランダム・ベクトルをオーバーライドし、前記テストは自動テストパターン生成器によって生成されることを特徴とするスキャン方式ビルトイン・セルフテスト回路。
【請求項１６】
前記デコーダの領域オーバーヘッドは、前記デコーダの２つの出力と前記ＡＮＤゲート及び前記ＯＲゲートへの入力の間に、トグル・フリップフロップを挿入することによって低減されることを特徴とする請求項１５に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１７】
前記生成器内の競合入力に対応するランダム・ベクトルからの入力はオーバーライドされないことを特徴とする請求項１５に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１８】
前記スキャン・カウンタが、１回のスキャン・クロックのポジティブ・エッジごとに１増分し、スキャン入力用の新規値は、すべてのピンに対応する入力がスキャンで取り込まれるまで逐次スキャンされ、
このとき、生成器内の値が「１」の場合、対応するピン内のスキャン入力として、ランダム・ベクトルによって供給される値の代わりに「１」がスキャンによって取り込まれ、
生成器内の値が「０」の場合、対応するピン内のスキャン入力として、ランダム・ベクトルによって供給される値の代わりに「０」がスキャンによって取り込まれ、
生成器内の値がドントケアまたは競合値の場合は、ランダム・ベクトル内の値がスキャンによって取り込まれることを特徴とする請求項１５に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項１９】
スキャンの順序は遺伝的アルゴリズムを使用して決定され、その際には、スキャン回路内のスキャン要素の順列が遺伝子コードとして使用され、遺伝的アルゴリズムを使用して最小項が最小数となるようにスキャン要素の順序が決定されることを特徴とする請求項１６に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項２０】
互換のオーバーライド信号は、遺伝的アルゴリズムを適用する前にマージされることを特徴とする請求項１９に記載のスキャン方式ビルトイン・セルフテスト回路。
【請求項２１】
互換のスキャン・グループ内のスキャン入力は、ルーティングまたはロード容量を満たすように並び替えられることを特徴とする請求項２０に記載のスキャン方式ビルトイン・セルフテスト回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明では、回路テスト用のテストパターンを生成するための新規の自動テストパターン生成器に関して開示する。本発明ではさらに、ハードウェア・オーバーヘッドの少ない、新規の逐次及び並列スキャン方式３重み加重ランダム・ビルトイン・セルフテスト（ＢＩＳＴ：Ｂｕｉｌｄ−ｉｎ  Ｓｅｌｆ−ｔｅｓｔ）アーキテクチャに関する。
【背景技術】
【０００２】
ビルトイン・セルフテストは、回路に自己テスト能力を与えるテスト手法である。この手法では、回路への入力セットからなるテストベクトル（「テストパターン」とも呼ばれる）がテスト中の回路（ＣＵＴ：ｃｉｒｃｕｉｔ  ｕｎｄｅｒ  ｔｅｓｔ）に適用され、適用されたテストベクトルへのＣＵＴの応答が良好な回路で期待される応答と比較される。テストパターン生成器（ＴＰＧ：ｔｅｓｔ  ｐａｔｔｅｒｎ  ｇｅｎｅｒａｔｏｒ）は、このテストパターンを生成する。
【０００３】
ＢＩＳＴは、テストベクトルがＣＵＴに適用される方法に従って、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ方式（並列）とスキャン方式（ｔｅｓｔ−ｐｅｒ−ｓｃａｎ方式）に分類することができる。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ方式のＢＩＳＴでは、ＴＰＧから出力されるテストパターンはＣＵＴの入力に直接接続される。新規のテストパターンは、１回のテストクロック・サイクルにつき１つ適用される。これに対しスキャン方式のＢＩＳＴでは、ＴＰＧによって生成されたテストパターンが、フリップフロップからなるスキャン回路を介してＣＵＴに適用される。従って、スキャン方式のＢＩＳＴでは、テストパターンはＣＵＴにｍ＋１サイクルごとに適用される。ここで、ｍはスキャン回路内のフリップフロップ数である。
【０００４】
ランダム・テストパターン生成器は、テストパターンをランダムに生成する。また、テストパターンを優先順位に従って生成し、ＢＩＳＴに記憶してテストに使用することも可能である。記憶式パターン生成器を使用して実装されたＢＩＳＴは、決定用テストパターンを記憶するためのメモリを要するため、大量なハードウェア・オーバーヘッドを必要とする。一方、疑似ランダム・パターン生成器を使用して実装されたＢＩＳＴでは、ハードウェア・オーバーヘッドはほとんど不要となる。一般的に使用される疑似ランダム・パターン生成器には、線形フィードバック・シフト・レジスタ（ＬＦＳＲ：ｌｉｎｅａｒ  ｆｅｅｄｂａｃｋ  ｓｈｉｆｔ  ｒｅｇｉｓｔｅｒ）とセルラー・オートマタ（ＣＡ：ｃｅｌｌｕｌａｒ  ａｕｔｏｍａｔａ）の２種類がある。
【０００５】
さらに、ＬＦＳＲまたはＣＡＲによって生成されたランダム・パターン・テストシーケンスは、記憶式テストパターンよりもモデル化されていない故障の適用範囲が高いことが報告されている。また、記憶式テストパターンでは、メモリ・サイズの制約が厳しいため、数が大幅に不足するケースが一般的である。一方、ランダム・パターンの場合は、回路によっては、十分な故障適用範囲を達成しようとするとシーケンスが適切なレベルをはるかに上回る長さになってしまうことがある。
【０００６】
高度な故障適用範囲を達成するために必要とされるランダム・パターン・テスト長は、わずか数個の検出困難故障によって決定されることが多い。これらの検出困難故障は、ランダム・パターンによる検出で発見されることは希なため、「ランダム・パターン耐性故障」とも呼ばれる。これらのランダム・パターン耐性故障はいずれも、検出確率が非常に低い。この検出確率は、「ランダムに生成されるベクトルが故障を検出する確率」と定義される。P. H. B., W. H. McAnney, and J. Savir, Built-In Test for VLSI:Pseudorandom Techniques (疑似ランダム手法), John Wiley & Sons, 1987を参照。
故障fの検出確率は、以下のように定義できる。
【０００７】
【数１】
2004301856.tif 000003
ここで、ｍは回路入力数である。
【０００８】
この式から分かるように、検出困難故障が検出されるためには多数の入力割り当てを必要とする。そのため、ランダムに生成されたベクトルが入力のすべての必要条件を満たす確率は必然的に低レベルとなる。
【０００９】
従来の加重ランダム・パターンテスト（ＷＲＰＴ：weighted random pattern testing）用ＢＩＳＴの極端なケースとして分類される検出困難故障の検出確率を向上させるＢＩＳＴ手法が、一部の専門家によって提案されている。S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits (キューブ格納ランダム・パターン及び合成多層回路の完全テストへのその適用), in Proceedings IEEE International Test Conference, pages 473-482, 1991、I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993、及びM. F. AlShalbi and C. R. Kime, Fixed-Biased Pseudorandom Built-in Self Test For Random Pattern Resistant Circuits(ランダム・パターン耐性回路のための固定バイアス疑似ランダム・ビルトイン・セルフテスト), in Proceedings IEEE International Test Conference, pages 929-938, 1994を参照。
【００１０】
（ＷＲＰＴ）ＢＩＳＴの詳細については、D. Neebel and C. R. Kline, Multiple Weighted Cellular Automata(複合加重セルラー・オートマタ), In VLSITS, pages 81-86, 1994、H. J. Wunderlich, Multiple Distributions for Biased Random Test Patterns(バイアス・ランダム・テストパターンに関する多重分布), in Proceedings IEEE International Test Conference, pages 236-244, 1988、及びR. Kapur, S. Patil, T. J. Snethen, and T. W. Williams, Design of an Efficient Weighted Random Pattern Generation System(効率的な加重ランダム・パターン生成システムの設計), in Proceedings IEEE International Test Conference, pages 491-500, 1994を参照。
【００１１】
従来のＷＲＰＴでは、例えば０、０．２５、０．５、０．７５、１．０といった様々な重みが割り当てられるのに対し、前述の検出困難故障の検出確率を向上させるための手法では、各入力に割り当てられる重みは０、０．５、１の３個だけである。使用される重みがわずか３個なので、重みを生成するための回路は単純である。例えば重み１（０）は、信号を１に固定することによって得られる。同様に、重み０は信号を０に固定することによって得られる。重み０．５は、ＬＦＳＲなどの純粋なランダム・パターン生成器の出力で信号を駆動することによって得られる。さらに、３個の重みしか使用されないので、重みセットを記憶するためのメモリは従来のＷＲＰＴよりもサイズが小さくてすむ。
【００１２】
本発明では、改良型自動テストパターン生成器（ＡＴＰＧ：ａｕｔｏｍａｔｉｃ  ｔｅｓｔ  ｐａｔｔｅｒｎ  ｇｅｎｅｒａｔｏｒ）を使用して、３重みＷＲＰＴにおけるハードウェア・オーバーヘッドとテストシーケンス長を最小化する手法を提示する。さらに本発明では、ＡＴＰＧに関する本発明による手法を使用して、少なくとも３種類の改良型ＢＩＳＴアーキテクチャを提示する。
【００１３】
「表記法及び定義」
本発明では、Ｓ．Ｐａｔｅｒａｓ  ｅｔ  ａｌで使用される表記法に多少の変更を加えたものを使用する。この表記法の詳細については、S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits (キューブ格納ランダム・パターン及び合成多層回路の完全テストへのその適用), in Proceedings IEEE International Test Conference, pages 473-482, 1991を参照。
「故障のテストキューブ」とは、「特定されていない入力を有するテスト」として定義される。ここで、Ｃ＝｛ｃ１，ｃ２，…，ｃｈ｝は、テスト中の回路（ＣＵＴ）における検出困難故障セットのテストキューブを示すと想定する。このうち、テストキューブｃｊ＝｛ｃｊ１，ｃｊ２，…，ｃｊｍ｝はｍビットであり、ｍはＣＵＴの入力数である。テストキューブｃｊ１∈｛０，１，Ｘ｝ＶｉとＸはドントケアである。さらに、Ｃ1，Ｃ２，…，Ｃｄをテストキューブ・セットＣのサブセットとし、生成器ｇｅｎ（Ｃｉ）｛ｇｉ１，ｇｉ２，…，ｇｉｍ｝（ｉ＝１，２，…，ｄ）は、以下のように定義されるｍビットの組（ここで、ｇｉｋ｛０，１，Ｘ，Ｕ｝（ｋ＝１，２，…，ｍ））を表すと想定する。
【００１４】
【数２】
2004301856.tif 000004
ここで使用する「生成器」という用語は、D. Neebel and C. R. Kime. Multiple Weighted Cellular Automata (複合加重セルラー・オートマタ), in VLSITS, pages 81-86, 1994、H.-J. Wunderlich. Multiple Distributions for Biased Random Test Patterns (バイアス・ランダム・テストパターンに関する多重分布), in Proceedings IEEE International Test Conference, pages 236-244, 1988、及びR. Kapur, S. Patil, T. J. Snethen, and T. W. Williams. Design of an Efficient Weighted Random Pattern Generation System (効率的な加重ランダム・パターン生成システムの設計), in Proceedings IEEE International Test Conference, pages 491-500, 1994で使用される「重みセット」と同義であることに注意されたい。
【００１５】
入力ｇiｋ＝Ｕの場合、テストキューブ・セットＣｉ内には入力ｐｋにおいて競合するテストキューブが存在する。すなわち、∋ａ，ｂによりｃａｋ＝Ｖ及びｃｂｋ＝¬v（ｖ∈｛１，０｝、¬ｖは２値データｖの否定（ＮＯＴ）の値）なので、入力ｐｋを２値データｖに固定すると、入力ｐｋに¬vを割り当てるべき故障がテスト不能となる可能性がある。一方、入力ｇｉｋ＝Ｘの場合、入力ｐｋはテストキューブ・セットＣｉ内のどのテストキューブにおいても指定されない。従ってこの場合には、入力ｐｋを任意の２値データに固定しても故障適用範囲が減じられることはない。テストキューブｃｊにおいては２値データを割り当てられ、生成器ｇｅｎ（Ｃｉ）の対応する位置ではＵを割り当てられた入力セットは、テストキューブｃｊの「競合ビット」と呼ばれる。図１にテストキューブの例を示す。図１に示すテストキューブ・セットでは、入力ｐ１、ｐ３、及びｐ６がテストキューブｃ１〜ｃ４において異なる２値データ（０または１）が割り当てられているので、テストキューブｃ１は３個の競合ビットを有する。従って、これらのピンには生成器ｇｅｎ（Ｃ）においてＵが割り当てられる。一方、生成器ｇｅｎ（Ｃ）内の対応するビットにＵが割り当てられた入力のうち、テストキューブ・セットＣ２内で２値データ０を割り当てられているのは入力ｐ３だけなので、テストキューブｃ２が有する競合ビットは１個だけである。
【００１６】
（ａ）「検出確率」
Ｆ＝｛ｆ１，ｆ２，…，ｆｎ｝を故障セットとし、Ｃ＝｛ｃ１，ｃ２，…，Ｃｎ｝をテストキューブ・セットとする。また、テストキューブｃｊｒ（ｊ＝１，２，…，ｎ）は、対応する故障ｆｊ（ｊ＝１，２，…，ｎ）の唯一のテストキューブとする。この想定のもとでは、故障ｆｊの検出確率は１／２ｍ−｜ｘｊ｜に過ぎない。ここで、ｍは入力数、｜Ｘｊ｜はドントケア（Ｘ）が割り当てられているテストキューブｃｊ内の入力数である。
【００１７】
図１に示すテストキューブｃ１、ｃ２、ｃ３、ｃ４の各々を、故障ｆ１、ｆ２、ｆ３、ｆ４に対応する唯一のテストキューブとする。テストキューブｃ１、ｃ２、ｃ３、ｃ４は各々、２個、２個、３個、１個のドントケア値を有する。各テストキューブは対応する故障の唯一のテストキューブなので、故障ｆ１、ｆ２、ｆ３、ｆ４の検出確率は各々、１／２４、１／２４、１／２３、１／２５として計算できる（この例では、入力数ｍは６個であることに注意すること）。
【００１８】
式２で説明したように、テストキューブ・セットＣ内のすべてのテストキューブにおいて入力ｐｋに１またはＸが割り当てられ、かつ少なくとも１個のテストキューブにおいて入力ｐｋに１が割り当てられている場合、入力ｐｋには重み１が割り当てられる（すなわち、入力ｇｋ＝１）。式２で説明したように、テストキューブ・セットＣ内のすべてのテストキューブにおいて入力ｐｋに０またはＸが割り当てられ、少なくとも１個のテストキューブにおいて０が割り当てられている場合、入力ｐｋには重み０が割り当てられる（すなわち、入力ｇｋ＝０）。
【００１９】
一方、入力ｇｋに１が割り当てられている場合には、入力ｐｋを１に固定でき、これにより、検出のために入力ｐｋで１を入力する必要がある故障セットＦ内のすべての故障の検出確率が２倍に向上する。同様に、入力ｇｋに０が割り当てられている場合には入力ｐｋを０に固定でき、これにより、検出のために入力ｐｋで０を入力する必要がある故障セットＦ内のすべての故障の検出確率が２倍に向上する。
【００２０】
故障セットＦ内には検出のために入力ｐｋにおいて０を割り当てるべき故障はないため、入力ｐｋを１に固定しても故障はテスト不能にならない。同様に、故障セットＦ内には検出のために入力ｐｋにおいて１を割り当てるべき故障はないため、入力ｐｋを０に固定しても故障はテスト不能にならない。
【００２１】
図１では、入力ｐ２を０に固定すると、検出のために入力ｐ２で０を割り当てるべき故障ｆ２及びｆ４の検出確率が、各々１／２３及び１／２４に向上する。同様に、入力ｐ４及び入力ｐ５は各々１及び０に固定できる。一方、他の入力ｐ１、ｐ３、ｐ６を２値データに固定した場合には、これらの故障のテストキューブは各入力に競合する値を有するので、一部の故障がテスト不能になる。例えば、入力ｐ１を０に固定すると、検出のためには入力ｐ１において１が割り当てられていなければならない故障ｆ３及びｆ４がテスト不能になる。
【００２２】
４個のテストキューブｃ１、ｃ２、ｃ３、ｃ４を２つのグループＣ１＝｛ｃ１，ｃ２｝及びＣ２＝｛ｃ３，ｃ４｝に分割した場合は、グループＣ１内の入力ｐ１、ｐ２、ｐ４、ｐ５、ｐ６を各々０、０、１、０、１に固定し、グループＣ２内の入力ｐ１、ｐ２、ｐ３、ｐ５を１、０、０、０に固定しても競合は生じない。グループＣ２内のすべてのテストキューブ（ｃ３及びｃ４）において入力ｐ４にはＸが割り当てられるので、生成器ｇｅｎ（Ｃ２）内では入力ｇ２４にＸが割り当てられる。その結果、生成器ｇｅｎ（Ｃ１）＝｛０，０，Ｕ，１，０，１，｝及び生成器ｇｅｎ（Ｃ２）＝｛１，０，０，Ｘ，０，Ｕ｝となる。入力ｐ１、ｐ２、ｐ４、ｐ５、ｐ６を０、０、１、０、１に固定することにより、故障ｆ１及びｆ２の検出確率が１／２に向上し、入力ｐ１、ｐ２、ｐ３、ｐ５を１、０、０、０に固定することにより、故障ｆ３及びｆ４の検出確率が１／２に向上する。２個の生成器ｇｅｎ（Ｃ１）及びｇｅｎ（Ｃ２）を適用するため、最初の時間間隔Ｔ１では入力ｐ１、ｐ２、ｐ４、ｐ５が０、０、１、０に固定され、続いて、次の時間間隔Ｔ２では入力ｐ１、ｐ２、ｐ３、ｐ５が１、０、０、０に固定される。これらの時間間隔の算出手順については、「各生成器のためのテストシーケンス」の節において説明する。
【００２３】
（ｂ）「適切なテストキューブを生成することの重要性」
図１、図２の故障ｆ１はテストキューブＣ’１＝０１１１ＸＸによっても検出できると想定し、さらにテストキューブ・セットＣ’１の構成要素としてｃ１ではなくｃ’１が使用されると想定する。この場合は、ｃ’１の入力ｐ２における１が、テストキューブ・セットＣ’１内の他のテストキューブｃ２の入力ｐ２における０と競合する。従って、固定してもテストキューブ・セットＣ’１内に競合が発生しないのは入力ｐ１、ｐ４、ｐ５、ｐ６に限られる。固定されるのは入力ｐ１、ｐ４、ｐ５、ｐ６だけなので、検出のために入力ｐ２において０を必要とする故障ｆ２の検出確率はこれで１／２２となり、ｃ１が使用される場合に比較して２分の１の低減となる。故障セットＦ内のすべての故障の検出確率が１／２以上に向上するためには、テストキューブ・セットＣ’１を、各々ｃ’１またはｃ２だけで構成される２つのグループに分割する必要がある。そのため、ｃ１が使用される場合の生成器の所要個数は２個であるのに対し、ｃ’１が使用される場合には３個の生成器が必要となる。
【００２４】
生成器の所要個数は、本発明のＢＩＳＴの実装により必要となるハードウェア・オーバーヘッドを決定する。この所要個数を最小にするためには、テストキューブ・セットに加えるテストキューブを慎重に選択しなければならない。新たに追加するテストキューブは、テストキューブ・セットにすでに存在する他のテストキューブと競合する入力数が最小となるように選択する必要がある。ただし、大規模なランダム・パターン耐性回路では、検出困難故障のテストキューブの総数は非常に多いことが知られている。そのため、検出困難故障の各々について、可能なすべてのテストキューブの中から最良のテストキューブ（すなわち、テストキューブ・セット内の他のテストキューブと競合する入力数が最小のテストキューブ）を選択するためには、実現不可能なほどに膨大な時間複雑性が要求される。このような回路では、テストキューブ・セットの構成要素としてどのテストキューブを選択するかによって生成器の所要個数が大きく変動する。以上の理由から、最小数の生成器を必要とするテストキューブ・セットを作成するための検出困難故障のテストキューブは慎重に生成しなければならない。
【００２５】
（ｃ）「回路入力への生成器の適用」
この項では、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴにおけるＣＵＴへの生成器の適用について、その概念を説明する。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴに関するこの情報は、「スキャン方式ビルトイン・セルフテストへの適用」の節で詳述するスキャン方式ビルトイン・セルフテスト（ｔｅｓｔ−ｐｅｒ−ｓｃａｎ  ＢＩＳＴ）に関する本発明による手法の理解を助けるための背景情報として提供される。純粋なランダム・パターンテストにおいて、入力ｐｋ（ｋ＝１，２，…，ｍ）が対応するランダム・パターン信号ｒｋ（ｋ＝１，２，…，ｍ）によって駆動されるとする。生成器（Ｃｉ）の入力中に、入力ｇｉｋ＝ｖである入力ｐｋは、対応するオーバーライド信号ｓｋ／ｖを１に設定してランダム・パターン信号ｒｋをオーバーライドすることにより、２値データｖに固定される。入力ｐｋのためのオーバーライド信号は、入力ｇｉｋ（ｉ＝１，２，…，ｄ、ここでｄは生成器の個数）によって決定される。例えば、すべてのｄ個の生成器において入力ｇｉｋ（ｉ＝１，２，…，ｄ）に常にＸまたはＵが割り当てられる場合、入力ｐｋはどの生成器においても固定されず、従って入力ｐｋにはオーバーライド信号は不要である。入力ｇｉｋに１またはＸが割り当てられ、かつ少なくとも１個の生成器において１が割り当てられている場合、入力ｇｉｋ＝１である生成器ｇｅｎ（Ｃｉ）の入力中には、入力ｐｋを１に固定しなければならない。同様に、入力ｇｉｋに０またはＸが割り当てられ、かつ少なくとも１個の生成器において０が割り当てられている場合、入力ｇｉｋ＝０である生成器ｇｅｎ（Ｃｉ）の入力中には、入力ｐｋを０に固定する必要がある。生成器ｇｅｎ（Ｃａ）（すなわち、入力ｇａｋ＝１）において入力ｇｋに１が割り当てられ、生成器ｇｅｎ（Ｃｂ）（すなわち、入力ｇｂｋ＝０）においては入力ｇｋに０が割り当てられている場合、入力ｇａｋ＝１である生成器ｇｅｎ（Ｃａ）の入力中には入力ｐｋを１に、入力ｇｂｋ＝０である生成器ｇｅｎ（Ｃｂ）の入力中には入力ｐｋを０に、それぞれ固定しなければならない。
【００２６】
オーバーライド信号の個数と各入力の優先値を表すため、ｇｌｏｂ＿ｇｅｎ＝｛ｇｇ１、ｇｇ２、…、ｇｇｍ｝（ここで、ｍは入力数）と入力ｇｇｋ（ｋ＝１，２，…，ｍ）は以下のように導入される。
【００２７】
【数３】
2004301856.tif 000005
ここで、ｄは生成器数である。
【００２８】
入力ｇｇｋ＝ｖ（ｖ∈｛１、０｝）の場合には、入力ｐｋに１個のオーバーライド信号ｓｋ／ｖのみが必要とされ、入力ｇｇｋ＝Ｂの場合には、２個のオーバーライド信号ｓｋ／ｌ及びｓｋ／０が必要とされる。最後に、入力ｇｇｋ＝Ｎの場合には、すべての入力ｇｉｋ（ｉ＝１，２，…，ｄ）はＸまたはＵであり、入力ｐｋはテスト入力中の全体にわたって常にランダム・パターン信号ｒｋによって駆動されるので、入力ｐｋにオーバーライド信号は必要とされない。
【００２９】
図１、図２に、５個の入力を有する回路のための生成器とオーバーライド信号を示す。入力ｐ１は１（ｇ０１）と（ｇ１１及びｇ３１）の両方に固定されているので、入力ｇｇ１にはＢが割り当てられ、入力ｐ１には２個のオーバーライド信号ｓ１／０及びｓ１／１が割り当てられる。一方、入力ｐ３は１（ｇ１３及びｇ３３）にのみ固定されるので、入力ｇｇ３には１が割り当てられ、入力ｐ３には１個のオーバーライド信号ｓ３／１のみが割り当てられる。最後に、いずれの生成器ｇｅｎ（Ｃｉ）（ｉ＝０，１，２，３）においても入力ｇｉ５には２値データが割り当てられないので、入力ｐ５は固定されず、常にランダム・パターン信号ｒ５によって駆動される。そのため、入力ｇｇ５にＮは割り当てられず、入力ｐ５にもオーバーライド信号が割り当てられない。つまり、２個の入力ｐ１及び入力ｐ４には入力ｇｇｋ＝Ｂ（ｋ＝１，４）が割り当てられ、入力ｐ２及び入力ｐ３にはそれぞれ入力ｇｇ２＝０と入力ｇｇ３＝１が割り当てられるので、図１、図２に示すｇｌｏｂ＿ｇｅｎ＝｛Ｂ，０，１，Ｂ，Ｎ｝を有する生成器は６個のオーバーライド信号ｓ１／０、ｓ１／１、ｓ２／０、ｓ３／１、ｓ４／０、ｓ４／１を必要とする。
【００３０】
図３に、図１、図２に示す生成器とオーバーライド信号に関するｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴのための３重みＷＲＰＴ回路の実装を示す。信号ｒｉ（ｉ＝１，２，．．，５）は、ランダム・パターン生成器の出力に接続される。図３のカウンタは、適切な生成器を選択する。カウンタの内容がｉの場合は、生成器ｇｅｎ（Ｃｉ）が選択される。各生成器ｇｅｎ（Ｃｉ）は、前述のＴｉテストサイクルのためのテストパターンの生成に使用される。入力ｇｉｋ＝ｖ（ｖ＝０または１）の場合、入力ｐｋは、対応する信号ｓｋ／ｖを１に設定してランダム・パターン信号ｒｋをオーバーライドすることにより２値データｖに固定される。
【００３１】
例えば、生成器ｇｅｎ（Ｃ１）＝｛０，Ｘ，１，１，Ｕ｝のＣＵＴへの入力中には、ランダム・パターン信号ｒ１、ｒ３、ｒ４をオーバーライドするためにｓ１／０、ｓ３／１及びｓ４／１が１に設定され、他のオーバーライド信号には０が割り当てられる。イネーブル信号は、ＷＲＰＴの有効化／無効化のために使用される。イネーブル信号を０に設定するとＷＲＰＴが無効化され、いずれの入力も固定されない。この場合は、ランダム・パターン生成器がすべての入力を駆動する。カウンタの個々の状態は１個の生成器に対応するので、カウンタの所要ビット数は［ｌｏｇ２（生成器数）］によって与えられる。オーバーライド信号は、図３に示すデコーダ(DECODER)から、カウンタの出力を入力として生成される。デコーダ(DECODER)の所要領域は、通常、入力数と出力数によって異なる。従って、３重みＷＲＰＴによるハードウェア・オーバーヘッドは、入力を固定するために必要とされるオーバーライド信号数、及び生成器数によって決定される。
【００３２】
ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴに関して述べた手順は、ほとんど変更を加えることなくスキャン方式ビルトイン・セルフテスト（ｔｅｓｔ−ｐｅｒ−ｓｃａｎ  ＢＩＳＴ）にも適用できる。検出困難故障を検出するために走査によりスキャン回路に組み込まれるビット・シーケンスを改変するための手法は、H,-J. Wunderlich and G. Kiefer. Bit-Flipping BIST (ビットフリップBIST), in Proceedings VLSI Testing Symposium, pages 337-343、1996、及びN. A. Touba and E. J. McCluskey. Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), in Proceedings IEEE International Test Conference, pages 167-175, 1996(Touba' 96)で提案されている。Touba '96では、Touba '95に類似した手順を使用して、新規故障を検出するテストの補数を未検出故障のテストに変換するマッピング関数が算出される。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference、pages 167-175, 1996、及びN. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), In Proceedings IEEE International Test Conference, pages 674-682, 1995を参照。
【００３３】
この手順はＣＵＴに入力されるテストシーケンスに大きく依存するので、当該テストの補数はときに同語反復に陥ることがあり、極端なケースでは、補数に多数の特定済み入力が含まれるためにハードウェア・オーバーヘッドが増大する結果となる。さらに、テストシーケンスが変更された場合には、ビット・シーケンスを改変するＢＩＳＴ回路全体を設計し直す必要が生じる。Karkalaでは、Ｔｏｕｂａ’９６と同じ手法を使用して、新規故障を検出しない疑似ランダム・シーケンスが決定用テストキューブに変換される。M. Karkala, N A. Touba, and H.-J. Wunderlich, Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), in proceedings 7γrd Asian Test Symposium, 1998、及びN. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), in proceedings IEEE International Test Conference, pages 167-175, 1996を参照。
【００３４】
ただし、Ｔｏｕｂａ’９５では決定用テストキューブは従来のＡＴＰＧ手順によって生成されるのに対し、Karkalaでは、決定用テストキューブは決定用ＢＩＳＴ間の相関を考慮する専用ＡＴＰＧによって生成される。N. A. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), in Proceedings IEEE International Test Conference, pages 674-682, 1995、及びM. Karkala, N A. Touba, and H.-J. Wunderlich, Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test Symposium, 1998を参照。
【００３５】
Ｈ．−１  ＷｕｎｄｅｒｌｌｃｈでもＴｏｕｂａ’９６に類似した手順が使用されるが、ランダム・パターン内のいくつかのビットをフリップすることにより、ランダム・パターンが決定用パターンに改変される点が異なる。H.-J. Wunderlich and G. Kiefer, Bit-Flipping BIST(ビットフリップBIST), in Proceedings VLSI Testing Symposium, pages 337-343, 1996、及びN. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), in Proceedings IEEE International Test Conference, pages 167-175, 1996を参照。この手法もまた、入力されるランダム・パターン・テストシーケンスに大きく依存する。
【００３６】
「従来の３重みＷＲＰＴ  ＢＩＳＴ用ＡＴＰＧ」
Ｐａｔｅｒａｓでは、合成回路の２層版を対象とする完全なテストキューブ・セットが生成される（２層回路の単純構造により、全テストの生成が可能となる）。S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits(キューブ格納ランダム・パターン及び合成多層回路の完全テストへのその適用), in Proceedings IEEE International Test Conference, pages 473-482, 1991を参照。これらのテストキューブは、１セット内のテストキューブの競合入力数がＭ以下となるように数個のセットに分割され、これらのセットの各々について生成器が算出される。「表記法及び定義」において述べたように、生成器数はテストキューブ・セット内のテストキューブによって左右されるので、多数の割り当てを必要とするテストキューブをフィルタリングによって除去することにより、所要生成器数が低減される。これを行うのは、セット内のテストキューブが必要とする割り当てが多いと、競合入力数が増大し、そのために各テストキューブ・セットに含めることのできるテストキューブ数が少なくなり、生成器数が増大するからである。そのため、生成器の作成に使用されるテストキューブ・セットには、必要な割り当てが少ないテストキューブが含まれる。ただし、２層回路用のテストキューブには、多層合成回路では必要ではないテストキューブが含まれていてもよい。
【発明の開示】
【発明が解決しようとする課題】
【００３７】
上述した従来の技術では、以下に述べるような問題点があった。
【００３８】
Ｓ．  Ｐａｔｅｒａｓで報告された実験結果によると、このフィルタリング手順には高度な時間複雑性が要求される（この手順の実行時間は、合成手順の実行時間よりも長いのが一般的である）。S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level 回路s(キューブ格納ランダム・パターン及び合成多層回路の完全テストへのその適用), in Proceedings IEEE International Test Conference, pages 473-482, 1991を参照。しかしそれにもかかわらず、この方法において完全なテストキューブ・セットから良好なテストキューブ（必要な割り当てがほとんどないテストキューブ）を選択するためには、このフィルタリング手順が必要だと考えられている。この方法では完全なテストキューブ・セットが必要とされるので、時間複雑性の観点から、２層版が入手不能な場合は大規模回路に適用することは不可能であろう。
【００３９】
本発明の目的は、上記従来技術の欠点を解決し、改良型の手法を提供することにある。
【課題を解決するための手段】
【００４０】
上記目的を達成するため本発明のスキャン方式ビルトイン・セルフテスト回路は、並列型スキャン方式ビルトイン・セルフテスト回路において、入力を備えるテスト中の回路と、各スキャン・フリップフロップの各々は少なくとも同期リセット（Ｒ）ピンまたは同期プリセット（Ｓ）ピンを有する、入力に接続されるスキャン・フリップフロップ・セットと、スキャン・フリップフロップ・セットに入力を供給するランダム・ベクトルをロードするための線形フィードバックシフトレジスタと、グローバル生成器の機能を備え、前記スキャン・フリップフロップ内のＲ及びＳピンを制御するデコーダ出力を供給するデコーダと、前記デコーダ出力の状態を決定する前記デコーダに入力を供給するカウンタと、前記デコーダ用のイネーブル信号の入力手段を備え、前記デコーダはＲ及びＳピンへの入力を制御することによりＲ及びＳピンにオーバーライド信号を供給し、前記オーバーライド信号は困難な故障用テストパターンの生成器内のテストに基づいてランダム・ベクトルをオーバーライドし、前記テストは自動テストパターン生成器によって生成されることを特徴とする。
【００４１】
請求項２の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記イネーブル信号は、オーバーライド・イネーブル入力信号及び最終スキャン入力信号に対してＡＮＤ演算を実行するＡＮＤゲートによって供給されることを特徴とする。
【００４２】
請求項３の本発明のスキャン方式ビルトイン・セルフテスト回路は、「１」の入力をオーバーライド・イネーブル入力信号に供給することにより、ランダム・パターンがオーバーライドされ、ビルトインセルフテストが有効化されることを特徴とする。
【００４３】
請求項４の本発明のスキャン方式ビルトイン・セルフテスト回路は、最終スキャン入力信号は、各スキャン・シフト操作の最終サイクルでのみ１に設定されることを特徴とする。
【００４４】
請求項５の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記カウンタは、初期に「０」に設定され、所定数（Ｔ）のランダム・パターンが入力されている間は「０」に維持し、前記ランダム・パターンはデコーダによって供給される生成器に基づいて変更され、前記カウンタはさらに、増分されて新規の生成器によりＴ個のランダム・パターンが適用されるようにし、前記増分はデコーダによってすべての生成器が適用されるまで反復されることを特徴とする。
【００４５】
請求項６の本発明のスキャン方式ビルトイン・セルフテスト回路は、マージ可能な互換のオーバーライド信号が、デコーダの同じ出力信号によって駆動され、それによりデコーダ出力数が低減されることを特徴とする。
【００４６】
請求項７の本発明のスキャン方式ビルトイン・セルフテスト回路は、逆互換のオーバーライド信号が、デコーダ出力によって直接駆動され、インバータを通過後にも同じデコーダ出力によって駆動されることを特徴とする。
【００４７】
請求項８の本発明のスキャン方式ビルトイン・セルフテスト回路は、グローバル生成器によってスキャン入力に「１」が割り当てられた場合は、対応するスキャン・フリップフロップがＳピンを有することを特徴とする。
【００４８】
請求項９の本発明のスキャン方式ビルトイン・セルフテスト回路は、グローバル生成器によってスキャン入力に「０」が割り当てられた場合は、対応するスキャン・フリップフロップがＲピンを有することを特徴とする。
【００４９】
請求項１０の本発明のスキャン方式ビルトイン・セルフテスト回路は、グローバル生成器によってスキャン入力に「０」及び「１」が割り当てられた場合は、対応するスキャン・フリップフロップがＲピンとＳピンの両方を有することを特徴とする。
【００５０】
請求項１１の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記スキャン・フリップフロップがすでにハイ・アクティブＳピンを有し、グローバル生成器内の対応するスキャン入力に「１」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＯＲゲートが挿入されることを特徴とする。
【００５１】
請求項１２の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記スキャン・フリップフロップがすでにハイ・アクティブＲピンを有し、グローバル生成器内の対応するスキャン入力に０が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＯＲゲートが挿入されることを特徴とする。
【００５２】
請求項１３の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記スキャン・フリップフロップがすでにロー・アクティブＳピンを有し、グローバル生成器内の対応するスキャン入力に「１」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＡＮＤゲートが挿入されることを特徴とする。
【００５３】
請求項１４の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記スキャン・フリップフロップがすでにロー・アクティブＲピンを有し、グローバル生成器内の対応するスキャン入力に「０」が割り当てられた場合は、Ｓピンと通常存在する信号の間に２入力ＡＮＤゲートが挿入されることを特徴とする。
【００５４】
請求項１５の本発明のスキャン方式ビルトイン・セルフテスト回路は、逐次タイプのスキャン方式ビルトイン・セルフテスト回路において、入力を備えるテスト中の回路と、入力に接続されるスキャン・フリップフロップ・セットと、スキャン・フリップフロップ・セットに入力を供給するランダム・ベクトルをロードするための線形フィードバックシフトレジスタと前記線形フィードバックシフトレジスタとスキャン・フリップフロップ・セットの間に挿入されるＡＮＤゲート及びＯＲゲートと、２個のデコーダ出力信号Ｄ０及びＤ１をＡＮＤゲート及びＯＲゲートに供給するデコーダと、前記デコーダに入力を供給する生成器を選択する生成器カウンタと、前記デコーダに入力を供給するスキャン・カウンタと、前記デコーダ用のイネーブル信号の入力手段を備え、前記デコーダ出力の状態は、前記生成器カウンタ入力及び前記スキャン・カウンタ入力の両方によって決定され、前記デコーダは、オーバーライド信号を供給し、前記オーバーライド信号は困難な故障のテストパターン用の生成器のテストに基づいてランダム・ベクトルをオーバーライドし、前記テストは自動テストパターン生成器によって生成されることを特徴とする。
【００５５】
請求項１６の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記デコーダの領域オーバーヘッドは、前記デコーダの２つの出力と前記ＡＮＤゲート及び前記ＯＲゲートへの入力の間に、トグル・フリップフロップを挿入することによって低減されることを特徴とする。
【００５６】
請求項１７の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記生成器内の競合入力に対応するランダム・ベクトルからの入力はオーバーライドされないことを特徴とする。
【００５７】
請求項１８の本発明のスキャン方式ビルトイン・セルフテスト回路は、前記スキャン・カウンタが、１回のスキャン・クロックのポジティブ・エッジごとに１増分し、スキャン入力用の新規値は、すべてのピンに対応する入力がスキャンで取り込まれるまで逐次スキャンされ、このとき、生成器内の値が「１」の場合、対応するピン内のスキャン入力として、ランダム・ベクトルによって供給される値の代わりに「１」がスキャンによって取り込まれ、生成器内の値が「０」の場合、対応するピン内のスキャン入力として、ランダム・ベクトルによって供給される値の代わりに「０」がスキャンによって取り込まれ、生成器内の値がドントケアまたは競合値の場合は、ランダム・ベクトル内の値がスキャンによって取り込まれることを特徴とする。
【００５８】
請求項１９の本発明のスキャン方式ビルトイン・セルフテスト回路は、スキャンの順序は遺伝的アルゴリズムを使用して決定され、その際には、スキャン回路内のスキャン要素の順列が遺伝子コードとして使用され、遺伝的アルゴリズムを使用して最小項が最小数となるようにスキャン要素の順序が決定されることを特徴とする。
【００５９】
請求項２０の本発明のスキャン方式ビルトイン・セルフテスト回路は、互換のオーバーライド信号は、遺伝的アルゴリズムを適用する前にマージされることを特徴とする。
【００６０】
請求項２１の本発明のスキャン方式ビルトイン・セルフテスト回路は、互換のスキャン・グループ内のスキャン入力は、ルーティングまたはロード容量を満たすように並び替えられることを特徴とする。
【発明の効果】
【００６１】
本発明によれば、以下のような効果が達成される。
【００６２】
３重みＷＲＰＴ  ＢＩＳＴ（ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ及びスキャン方式）におけるテストシーケンス長及びハードウェア・オーバーヘッドを削減する手法について提示する。本発明の３重みＷＲＰＴ  ＢＩＳＴでは、対応するオーバーライド信号が活動化されたときにランダム・パターン信号をオーバーライドすることにより入力が所要の値に固定される。３重みＷＲＰＴ  ＢＩＳＴの実装に伴うハードウェア・オーバーヘッドは、典型的には、生成器数及びオーバーライド信号の数によって決定される。生成器数とオーバーライド信号を減少させるため、検出困難故障用の特殊なテストキューブが生成される、ＰＯＤＥＭを基礎とする改良型ＡＴＰＧが開示される。本発明のＡＴＰＧにおける選択は、各目標を達成するために必要とされる生成器数及びオーバーライド信号を推定するコスト関数によって誘導される。本発明のＢＩＳＴのアーキテクチャは非常に単純なので、ＢＩＳＴを制御する回路を低コストで実装できる。さらに、本発明の改良型ＡＴＰＧでは、生成器数だけでなくオーバーライド信号数も最小化される。最後に、本発明の改良型ＡＴＰＧによって生成されたオーバーライド信号は、互換性分析とスキャン回路の順序変更によりさらに最小化される。合成ベンチマーク回路に関する実験結果によって、本発明の方法が必要とするハードウェア・オーバーヘッドが非常に少ないことが実証されている。
【００６３】
本発明の方法では、カレント・テストキューブ・セット内のテストキューブとの競合入力数が最も少ない適切なテストキューブだけが生成されるので、多数のテストキューブから適切なテストキューブを選択する手順が不要である。通常、この手順は高レベルの時間複雑性を伴う。さらに、コスト関数の算出に伴う複雑性は回路ライン数に直線的に現れるので、本発明の改良型ＡＴＰＧの時間複雑性は単純な組み合わせＡＴＰＧのそれとほぼ同じである。従って、本発明のＢＩＳＴ設計法は大規模な回路にも適用できる。
【００６４】
特殊設計のフリップフロップを必要とする一部の従来手法とは異なり、本発明の手法では特殊なライブラリ・モジュールは必要とされない。そのため、本発明の手法はそれをサポートするための特殊なライブラリ・モジュールを設計することなく、どんなＡＳＩＣ環境においても実装できる。本書のために実施された実験では純粋ランダム・パターン・シーケンスの生成にＬＦＳＲＳが使用されているが、本発明のＢＩＳＴ用のランダム・パターン・シーケンスの生成には、Ｍ．Ｂｅｒｓｈｔｅｙｎなどの従来の加重ランダム・パターン生成器を含むあらゆるランダム・パターン生成器を使用できる。M. Bershteyn. Calculation of Multiple Sets of Weights for Weighted Random Testing(加重ランダムテストのための複数重みセットの計算). In Proceedings IEEE International Test Conference, pages 1031-1040, 1993を参照。さらに、本発明のＢＩＳＴは、テストポイント挿入などの他のテスト容易化設計手法と組み合わせて使用することも可能である。
【００６５】
回路によっては、単一の内部ラインを所望の値に設定するために多数の入力が必要な場合がある。テストポイントの挿入によってこのようなラインを所望の値に直接設定すれば、オーバーライド信号数も削減される。
【実施例】
【００６６】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００６７】
「３重みＷＲＰＴ  ＢＩＳＴのための改良型ＡＴＰＧ」
本発明の３重みＷＲＰＴ  ＢＩＳＴのための改良型ＡＴＰＧでは、最初に、多数のランダム・パターン可試験性故障を検出するために、純粋な疑似ランダム・パターンのシーケンスが適用される。ここでいう「ランダム・パターン可試験性故障」とは、ランダム・パターン耐性を有さない故障のことである。純粋なランダム・パターンのシーケンスは、その全要素にＵが割り当てられた特殊な生成器と考えることができる。すべてのテストキューブが事前に生成されるS. Pateras et al、I. Pomeranz et at、及びM. F. AlShaibi et alとは対照的に、本発明の改良型ATPGでは、適切な検出困難故障のテストキューブが1個ずつ生成される。
【００６８】
S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits(キューブ格納ランダム・パターン及び合成多層回路の完全テストへのその適用), In Proceedings IEEE International Test Conference, pages 473-482, 1991、I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993、M. F. AlShaibi and C. R. Kime. Fixed-Biased Pseudorandom Built-In Self-Test For Random Pattern Resistant Circuits(ランダム・パターン耐性回路のための固定バイアス疑似ランダム・ビルトイン・セルフテスト）, in Proceedings IEEE International Test Conference, pages 929-938, 1994、及びM. F. AlShaibi and C. R. Kime. : A BIST Method for Random Pattern Resistant Circuits(MFBIST：ランダム・パターン耐性回路のためのBIST手法), in Proceedings IEEE International Test Conference, pages 176-185, 1996を参照。
【００６９】
本発明の手法では、適切なテストキューブのみが生成されるため、多数の割り当てが必要なテストキューブをフィルタリングによって除去するための手順は不要である。生成されたテストキューブは、「カレント・テストキューブ・セット」と呼ばれるテストキューブ・セットＣｉに入れられ、Ｃｉにそれ以上のテストキューブを入れると故障の検出確率が事前定義されたしきい値１／２Ｍよりも下回るようになるまで、すなわち、テストキューブ・セットＣｉ内の競合入力数が最も多いテストキューブの競合入力数がＭを上回るまで、これが続けられる。テストキューブ・セットＣｉが生成されると、以降に生成されるテストキューブを入れるための新規のカレント・テストキューブ・セットＣｉ＋１が作成される。
【００７０】
テストキューブがＣｉに入れられると、生成器ｇｅｎ（Ｃｉ）が式２に従って更新される。（生成器数を最小にするために）各テストキューブ・セットにできるだけ多くのテストキューブを入れるため、本発明の改良型ＡＴＰＧでは、各テストキューブは、カレント・テストキューブ・セット内のすべてのテストキューブを考慮に入れて生成される。なお、本発明の手法は、従来のＡＴＰＧ手法であるＰＯＤＥＭからの改良と考えることができる。ＰＯＤＥＭの詳細については、P. Goel, An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits(組み合わせ論理回路用テストを生成するための暗黙エミュレーション・アルゴリズム), IEEE Trans. on Computers, Vol. C-30(3), March 1981を参照。
【００７１】
本明細書の「回路入力への生成器の適用」の項目で述べたように、３重みＷＲＰＴ  ＢＩＳＴの実装によるハードウェア・オーバーヘッドは、生成器数だけでなく、ｇｌｏｂ＿ｇｅｎで表現されるオーバーライド信号数によっても左右される。そのため、ハードウェア・オーバーヘッドを最小化するためには、本発明の手法ではオーバーライド信号数の最小化も試みられる。グローバル生成器ｇｌｏｂ＿ｇｅｎは、各テストキューブ・セットＣｉが確定された後、すなわち、これ以上テストキューブをテストキューブ・セットＣｉに追加するとテストキューブの競合入力数が事前定義されたＭを上回る状態になったときに更新される。本発明の改良型ＡＴＰＧではさらに、カレントｇｌｏｂ＿ｇｅｎを考慮に入れることによってオーバーライド信号数が最小化される。
【００７２】
本発明の改良型ＡＴＰＧが、カレント・テストキューブ・セット内のテストキューブとの競合入力数が最小で、かつ必要なオーバーライド信号数が最小のテストキューブを生成するように誘導するため、可制御性、可観測性、及びテスト生成コストが定義される。
【００７３】
ライン調整のためのバックトレース・パスに複数の候補がある場合に本発明の改良型ＡＴＰＧを誘導する手段としては、各ラインの可制御性コストが使用される。入力ｐｋの可制御性コストＣＶ（ｐｋ）は、カレント・テストキューブ・セットの生成器ｇｅｎ（Ｃｉ）及びカレントｇｌｏｂ＿ｇｅｎを以下のように考慮することによって定義される。
【００７４】
【数４】
2004301856.tif 000006
ここで、ｖは２値データ「０」または「１」である。
【００７５】
各入力の可制御性コストの目的は、ラインｌを２値データｖに設定することによって生じる入力競合及びオーバーライド信号の数を推定することにある。入力ｇｋ＝Ｕの場合、カレント・テストキューブ・セットにはすでに、入力ｐｋにおいて競合するテストキューブが含まれている。よって、任意の２値データを入力ｐｋに割り当ててもそれ以上の悪影響は生じない。よって、ＣＶ（ｐｋ）＝０である。入力ｇｋ＝１（０）のとき、入力ｐｋに１（０）が割り当てられているテストキューブは、カレント・テストキューブ・セット内のどのテストキューブとも競合しない。よって、ＣＶ（ｐｋ）＝０である。入力ｇｋ＝１の場合、カレント・テストキューブ・セット内のすべてのテストキューブの入力ｐｋには１またはＸだけが割り当てられる。入力ｇｋ＝０の場合も同様に、カレント・テストキューブ・セット内のすべてのテストキューブの入力ｐｋには０またはＸだけが割り当てられる。よって、入力ｐｋが反対値０（１）に割り当てられているテストキューブは、入力ｐｋにおいてカレント・テストキューブ・セット内の他のテストキューブとの競合を引き起こす。よってこの割り当てが競合を引き起こすのは明らかであり、そのため、高いコストＣｖ（ｐｋ）＝ｗが割り当てられる。
【００７６】
入力ｇｉｋが現在Ｘである（よって、カレント・テストキューブ・セット内のどのテストキューブでも入力ｐｋが指定されていない）入力ｐｋに２値データが割り当てられている場合には、新規のオーバーライド信号をＢＩＳＴ  ＴＰＧに追加できる。入力ｇｉｋが現在Ｘである入力ｐｋが２値データｖに割り当てられると、入力ｇｋＸの現在の値が２値データｖに変わる。この状態では、入力ｇｇｋの現在の値によっては、ＢＩＳＴに追加のオーバーライド信号が必要になることがある。入力ｇｇｋが現在Ｂの場合、２個のオーバーライド信号ｓｋ／１及びｓｋ／０がすでに入力ｐｋに割り当てられている。よって、入力ｐｋを任意の２値データに割り当てても、追加のオーバーライド信号は必要とはならない。また、入力ｇｇｋが現在２値データｖに割り当てられている場合には、同じ値ｖを入力ｐｋに割り当てても、追加のオーバーライド信号は必要とはならない。前述の２つのケースでは追加のオーバーライド信号は必要ではなく、入力競合も発生しないが、ｖを入力ｐｋに割り当てると、後に¬vを入力ｐｋに割り当てるテストキューブが生成されたときに競合を引き起こす可能性がある。よって、２値データを入力ｐｋに割り当てることは後の競合の潜在的な原因であるという理由で、小さいコスト１が割り当てられる。現在入力ｇｇｋがＮで入力ｇｉｋ＝Ｘの場合、入力ｐｋを２値データｖに割り当てる必要があるテストキューブは、入力ｐｋのためにもう１個のオーバーライド信号Ｓｋ／ｖを生成する。現在入力ｇｇｋ＝¬vで入力ｇｉｋ＝Ｘの場合、入力ｐｋを２値データｖに割り当てる必要があるテストキューブは、入力ｇｇｋの値をＢに変え、入力ｐｋのためにもう１個のオーバーライド信号ｓｋ／ｖを追加する。この２つのケースについては、入力の可制御性はｈである。ここで、ｈはオーバーライド信号の追加によるコストを反映する変数である。
【００７７】
回路内の内部回路ラインｌの可制御性コストは、以下のように算出される。
【００７８】
【数５】
2004301856.tif 000007
ここで、ｌａ及びｌは各々、制御値ｃ及び反転ｉを有するゲートの入力及び出力である。上記の可制御性コストの計算は、Goldstein et alで使用される可試験性指標に類似していることに注意されたい。L. H. Goldstein and E. L. Thigpen. SCOAP: Sandia Controllability / Observability Analysis Program(SCOAP:Sandia可制御性 / 可観測性分析プログラム). In Proceedings IEEE-ACM Design Automation Conference, pages 190-196, 1980を参照。
【００７９】
回路１の可制御性コストＣｖ（ｌ）は、ラインｌをｖに設定することによる最小コストである。換言すると、入力の１つのみを２値データｖ’に設定することによってｌをｖに設定できる場合、すなわち、ｖ＝ｖ’xor ｉ（ｖ’はｌを駆動するゲートの制御値）であり、ｌの入力ｌｍｉｎがｌの入力の中で最小のコスト関数ＣＶ’（ｌｍｉｎ）を有する場合、Ｃｖ（ｌ）はＣＶ（ｌｍｉｎ）として定義される。ただし、回路内に再収束ファンアウトが存在する場合は、ｌｍｉｎをｖ’に設定することによってｌをｖに設定することは、他の目標と対立するという理由で不可能なことがある。その場合、本発明の改良型ＡＴＰＧは、ｌｍｉｎよりも高いコスト関数を有するｌの他の入力を選択することにより、ラインｌをｖに設定するという目標を満足する。よって、ラインｌをｖに設定することによる実際コストはＣｖ（ｌ）を上回る可能性はあるが、それを下回ることはない。
【００８０】
テスト生成中には、出力値が現時点では未知で、かつゲート入力のうち少なくとも１つが故障効果を有するすべてのゲートがＤフロンティアに属する。Ｄフロンティアの詳細については、P. Goel, An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits(組み合わせ論理回路用テストを生成するための暗黙エミュレーション・アルゴリズム), IEEE Trans. on Computers, Vol. C-30(3), March 1981を参照。本発明の改良型ＡＴＰＧでは、引き起こしうる競合が最小数で、入力における故障効果を伝播するために必要とされる追加のＴＰＧハードウェアが最小量のゲートがＤフロンティアから選択され、故障効果が１つ以上の一次出力に到達するまでこれが反復される。
【００８１】
以下で説明する可観測性コスト関数は、この目標を達成するための選択基準の役割を果たす。可観測性コスト関数は、一次出力から一次入力まで再帰的に計算される。ラインｌの可観測性コストは、以下によって得られる。
【００８２】
【数６】
2004301856.tif 000008
ここで、後者のケースでは、ｌ０は入力ｌを有するゲートの出力、ｌａは１以外のｌ０の全入力である。ラインｌの可観測性コストはまた、ラインｌにおける値を１つ以上の一次出力に伝播するための最小コストでもある。従って、可制御性コストの場合と同様に、回路内に再収束ファンアウトが存在する場合は、ラインｌにおける値を１つ以上の一次出力に伝播するための実際コストは、ラインｌの可観測性コスト０（ｌ）を上回る可能性はあるが、下回ることはない。
【００８３】
次に、本発明の改良型ＡＴＰＧについて、縮退故障モデルに関連する例を参照しつつ説明する。ラインｌにおけるｓｔｕｃｋ−ａｔ−¬v（ｓ−ａ−¬v、図４のフローチャートにおいては、¬ｖは上付き線付きのｖで表示）検出用のテストキューブを生成するために、まずライン１をｖに設定することにより故障が活動化される。ラインｌ  ｓ−ａ−¬vを活動化するためのコストは、Ｃｖ（ｌ）である。続いて、活動化された故障効果が１つ以上の一次出力に伝播される。ライン１における活動化された故障効果を伝播するためのコストは、Ｏ（ｌ）である。よって、ラインｌ  ｓ−ａ−¬v用のテストキューブを生成するためのテスト生成コストは、２つのコスト関数の和として定義される。
【００８４】
Ｔｖ（ｌ）＝Ｃｖ（ｌ）+Ｏ（ｌ）      式（７）
可制御性コスト及び可観測性コストは可能な最小のコストとして定義されるので、２つのコスト関数Ｃｖ（ｌ）及びＯ（ｌ）であるテスト生成コストＴｖ（ｌ）は、ｓｔｕｃｋ−ａｔ−¬v検出用のテストキューブを生成するための最小コストでもある。よって、ｓｔｕｃｋ−ａｔ−¬v検出用のテストキューブを生成するための実際コストは、常にテスト生成コスト関数Ｔｖ（ｌ）以上となる。本発明の改良型ＡＴＰＧによって生成されるテストキューブは指定過剰な場合が多いので、本発明の改良型ＡＴＰＧによって２値データを割り当てられた少数のビットをドントケアと置換しても、ターゲット故障の検出能力が損なわれることはない。指定入力の少ないテストキューブは、カレント・テストキューブ・セット内にすでに存在するテストキューブとの競合入力を少数しか有さないので、テストキューブ・セット内にそれだけ多くのテストキューブを入れることができる。テストキューブが生成されると常に、２値データが割り当てられた入力は、各入力をその２値データに割り当てることによるコストに基づいて順序付けされる。これらの入力の各々に割り当てられた値は、この順序でフリップされる。入力をフリップした後もまだターゲット故障を検出できる場合には、入力に割り当てられた値はドントケアに置換される。この手順は、「ビット・ストリッピング」と呼ばれる。
【００８５】
回路が再収束ファンアウトを有する場合は、ある目標を満たすために必要とされる入力割り当てが他の目標を満たすために必要とされる入力割り当てと競合する可能性があり、この状態となった場合は、本発明の改良型ＡＴＰＧが選択する目標またはバックトレース・パスはコストの高いものとなる。よって、再収束ファンアウトを有する回路では、１つの故障に関して生成されたテストキューブの実際コストが、式７に示す推定テスト生成コスト関数によって示される当該故障のコストをはるかに上回る可能性がある。
【００８６】
このようなテストキューブがカレント・テストキューブ・セットに追加されるのを防止するため、生成されたテストキューブの実際コストがその故障の推定テスト生成コストを一定の数値（例えば、１００）以上上回った場合には、その生成テストキューブは破棄される。その後、別のターゲット故障に関してテスト生成が実行され、実際コストが推定テスト生成コストに近い故障が見つかるか、あるいは故障リスト内のすべての故障がチェックされるまでこれが続けられる。ただし、故障リスト内のすべての故障がチェックされるワースト・ケースの場合でも、テストキューブの生成が必要となる故障はごく少数である。故障に関するテストキューブの実際コストは推定テスト生成コストを決して下回らないという点で、故障の推定テスト生成コストは常に故障の実際コストの楽観的な概算値ということができる。よって、ある故障の推定テスト生成コストが、カレント・テストキューブ・セットに追加するために生成されたテストキューブの中で最小の実際コストを示したテストキューブの値を上回り、実際コストが高いために破棄された場合は、その故障に関するテストキューブの中に実際コストがカレントの最小実際コストを下回るものはなく、よってその故障に関してテストキューブを生成する必要はない。故障リスト内のすべての故障のテストキューブが非常に高い実際コストを示した場合、最小の実際コストを有するテストキューブがカレント・テストキューブ・セットの新要素として選択される。
【００８７】
図４は、本発明の改良型ＡＴＰＧの好適な実施例を示すフローチャートである。
【００８８】
４．２０では、すべての検出困難故障のコストが算出される。４．３０では、最小コストを有する検出困難故障の中から、それまでに選択されていないターゲット故障が選択される。４．４０では、選択されたターゲット故障のテストキューブが生成される。４．５０では、ビット・ストリッピングが実行される。４．６０では、実質コストが推定コストと比較される。実質コストが推定コストと予定誤差の合計を上回り、かつ未選択の故障がある場合には、４．６０で処理が４．３０に戻される。未選択の故障が残っていない場合は、４．８０で最小実質コストを有するテストキューブが選択される。４．６０で実質コストが推定コストと予定誤差の合計を上回らない場合は、４．４０で生成されたテストキューブが、選択されたテストキューブとして保持される。最後に４．９０で、選択されたテストキューブによって検出されたすべての故障がマークされる。
【００８９】
ＡＴＰＧアルゴリズム全般に言えることであるが、従来のＰＯＤＥＭは非多項式ワースト・ケースの時間複雑性も有するので、一部の故障についてテストを生成しない場合や、事前定義されたバックトラック限度を超えるバックトラックのために生じた冗長性が識別されない場合がある。これらの故障は、「アボートされた故障」と呼ばれる。本発明の改良型ＡＴＰＧにより使用される新規のコスト関数がバックトラックの増大を引き起こすかどうかを確認するための実験を実施した。比較のため、同じ故障のテストキューブにより生じるバックトラックを低減する手段として、L．H．Goldsteinで定義されるコスト関数を使用したＰＯＤＥＭを実装した。L. H. Goldstein and E. L. Thigpen, SCOAP: Sandia Controllability/Observability Analysis Program(SCOAP: Sandia可制御性/可観測性分析プログラム), in Proceedings IEEE-ACM Design Automation Conference, pages 190-196, 1980を参照。同じバックトラック限度(500)を使用した場合、この実装でアボートされた故障の数は、本発明の改良型ATPGで全回路に関してアボートされた故障の数に近かった。この事実は、一部の回路に多数のバックトラックが生じたのは、新規のコスト関数によるものではなく、本発明のATPGが改良の基礎としたPODEMアルゴリズムの限界に起因するものであることを示唆している。
【００９０】
ある故障のテスト生成がアボートされた場合に実行されるその後の改善では、アボートされた故障に必要な入力割り当てを発見するために、ＴＥＧＵＳをベースとして実装されるＳＡＴ方式のＡＴＰＧが呼び出される。ＴＥＧＵＳの詳細な背景情報については、P. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Combinational Test Generation Using Satisfiability(満足化可能性を使用した組み合わせテスト生成). IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, Vol. 15(9), Sep. 1996を参照。
【００９１】
ＳＡＴ方式のＡＴＰＧで発見された必要な入力割り当ては、競合分析によってそれ以外の必要な入力割り当てを発見するためにさらに処理される。競合分析では、ＳＡＴ方式ＡＴＰＧによって故障の検出に必要な値を割り当てられなかった各入力ｐｋがまず０に設定され、入力ｐｋにおけるその０が内部回路ライン内に伝播される。伝播プロセスの後に故障効果（Ｄまたは¬Ｄ）がいずれかの一次出力に伝播された場合は、ＳＡＴ方式ＡＴＰＧ及び競合分析の結果一次入力に割り当てられた現在値からなるキューブが、その故障のテストキューブとなる。それ以外であれば、入力ｐｋにおける０の割り当てが、（１）回路内のすべてのｘパスをブロックしたか、（２）Ｄフロンティアからすべてのゲートを除去したか、または（３）故障値ｓ−ａ−ｖと同じ故障サイトに２値データｖを割り当てた場合には、故障を検出するために入力ｐｋに１（この１は、故障を検出するためにｐｋに必要な値）を割り当てなければならない。詳細な背景情報については、M. Abramovici, M. A. Breuer, and A. D. Friedman. Digital Systems Testing and Testable Design(デジタル・システムのテストとテスト可能な設計). Computer Science Press, New York, N.Y., 1990を参照。
【００９２】
競合分析の反復により、入力ｐｋに１が割り当てられる。この入力に０と１の両方を割り当てると前述の３つの競合条件のうち１つ以上が引き起こされる場合は、その故障は冗長である。ある入力で必要とされる入力値が当該入力に割り当てられた後には、さらに別の入力に必要な値を識別できる。競合分析は、必要な入力がもはや識別されなくなるまで反復される。アボートされた故障に関して算出された必要な入力割り当ては、本発明の改良型ＡＴＰＧに渡され、その故障のテストキューブが最終的に生成される。
【００９３】
「オーバーライド信号のマージ」
すべての検出困難故障のテストキューブが生成されたら、本明細書の「回路入力への生成器の適用」の項目で示した最終的なｇｌｏｂ＿ｇｅｎを拡張することによりオーバーライド信号が作成される。入力ｇｇｋに１が割り当てられた場合は、ＯＲゲートが入力ｐｋに割り当てられる。図３に示すように、入力ｇｉｋ＝１の生成器ｇｅｎ（Ｃｉ）が適用されている間、ＯＲの入力ｓｋ／１を１に設定することにより入力ｐｋが１に固定される。同様に、入力ｇｇｋに０が割り当てられた場合は、ＡＮＤゲートが入力ｐｋに割り当てられる。入力ｇｉｋ＝０の生成器ｇｅｎ（Ｃｉ）が適用されている間、ＡＮＤの入力ｓｋ／０を１に設定することにより入力ｐｋが０に固定される。生成器ｇｅｎ（Ｃｉ）内の入力ｇｉｋにＵが割り当てられている場合には、テストキューブＣｉ内に入力競合が生じる。この場合は入力ｐｋを固定することはできないので、生成器ｇｅｎ（Ｃｉ）が適用されている間には、入力ｐｋに割り当てられたすべてのオーバーライド信号は０に設定されなければならない。入力ｇｇｋにＢが割り当てられた場合には、入力ｐｋにはＯＲ及びＡＮＤゲートが割り当てられる。入力ｐｋは、対応するオーバーライド信号ｓｋ／１によって駆動されるＯＲゲートと、もう一方のオーバーライド信号ｓｋ／０によって駆動されるＡＮＤゲートによって駆動される（図３のオーバーライド信号ｓ１／０及びｓ１／１を参照のこと）。（入力ｇａｋ＝１の生成器ｇｅｎ（Ｃａ）の適用中に）入力ｐｋを１に固定する必要がある場合には、オーバーライド信号ｓｋ／ｌは１に設定され、ｓｋ／０の値はこの時点ではドントケアになる。逆に、（入力ｇｂｋ＝０の生成器ｇｅｎ（Ｃｂ）の適用中に）入力ｐｋを０に固定する必要がある場合には、ＡＮＤゲート０の出力における値がオーバーライドされないように、ｓｋ／ｌは０に設定されなければならない。生成器ｇｅｎ（Ｃｉ）内で入力ｇｉｋにＸが割り当てられた場合、生成器ｇｅｎ（Ｃｉ）の適用中には、対応するオーバーライド信号ｓかｓｋ／¬v、またはその両方がドントケアとなる。ただし、生成器ｇｅｎ（Ｃｉ）内で入力ｇｉｋにＵが割り当てられた場合には、入力ｐｋは１と０の両方に割り当てられなければならない。よって、対応するオーバーライド信号ｓｋ／ｖかｓｋ／¬v、またはその両方には、ランダム・パターン信号ｒｋがオーバーライドされないように、０を割り当てる必要がある。
【００９４】
どの生成器においてもｓａ／ｙ＝’ｖ及びｓｂ／ｚ＝¬v（ここで、ｖ∈｛０，１｝）の場合、２個のオーバーライド信号ｓａ／ｙ及びｓｂ／ｚ（ここで、ａ≠ｂ及びｙ、ｚ∈｛０，１，Ｘ｝）は互換ではない。それ以外の場合は、ｓａ／ｙとｓａ／ｚは互換である。互換のオーバーライド信号は、１個のオーバーライド信号にマージできる。例えば図１、図２では、生成器ｇｅｎ（Ｃｉ）を適用するためにはｓ１／１は０に設定され、ｓ３／１は１に設定されなければならないため、ｓ１／１とｓ３／１は互換ではない。一方、ｓ１／０とｓ２／０は互換である。
【００９５】
反転関係を考慮することにより、互換入力の定義を拡大できる。例えば図２では、オーバーライド信号ｓ１／１にｖ（ｖ＝０または１）が割り当てられた各生成器では、オーバーライド信号ｓ３／１には¬vまたはＸが割り当てられることに注意する必要がある。従って、入力ｐ３を固定する２入力ＯＲゲートを駆動する前にオーバーライド信号ｓ３／１が反転され、一方ｓ１／１は入力ｐ１を固定する２入力ＯＲゲートを直接駆動する場合には、ｓ３／１とｓ１／１はマージできる。このようなオーバーライド信号ｓａ／ｙ及びｓｂ／ｚ（ａ≠ｂ）は、逆互換性があるといわれる。最小数のオーバーライド信号を発見するステップは、最大独立集合問題として数式化できる。詳細な背景情報については、J. A. Bondy and U. S. R. Murty. Graph Theory with Applications(グラフ理論と応用例). American Elsevier Publishing Co. Inc., New York, N.Y., 1982を参照。
【００９６】
図５は、図１、図２に示す生成器とオーバーライド信号の実装において、互換のオーバーライド信号がマージされる場合を示したものである。図３の従来のアーキテクチャに示されるのと同じ生成器及びオーバーライド信号のためのＢＩＳＴ実装ではデコーダは６個の出力を有するのに対し、本発明の手法による実装ではデコーダは３個の出力しか有さないことに注意されたい。互換のオーバーライド信号ｓ１／０、ｓ２／０、及びｓ４／１がマージされ、デコーダの同じ出力によって駆動される。ｓ１／１との逆互換性を有するｓ３／１は、インバータを介してｓ１／１と同じデコーダ出力によって駆動される。互換または逆互換の入力を有さないｓ４／１は、他のどの入力ともマージされない。
【００９７】
本発明の改良型ＡＴＰＧ設計で使用されるアルゴリズムの全体を以下に大まかに示す。
【００９８】
（１）   ｉ←０，ｇｌｏｂ＿ｇｅｎ←｛Ｎ，Ｎ，…，Ｎ｝
（２）   カレント・テストキューブ・セットＣｉ←φを初期化する。故障リスト内のすべての故障のマークを解除する。生成器ｇｅｎ（Ｃｉ）＝｛Ｘ，Ｘ，…，Ｘ｝。ｊ←０
（３）  故障リスト内に故障がなくなったら、６に進む。本発明の改良型ＡＴＰＧによりテストキューブＣｊを生成する。
【００９９】
（４）  テストキューブｃｊをカレント・テストキューブ・セットＣｊ←Ｃｊ∪ｃｊ、ｊ←ｊ＋１に追加する。テストキューブｃｊによって検出された故障をマークする。
【０１００】
（５）  カレント・テストキューブ・セットＣｉ内のいずれかのテストキューブの競合入力数がＭ（Ｍは正の整数）を上回る場合には、Ｃｉ←Ｃｉ−ｃｊ，ｉ←ｉ＋１となる。ｇｌｏｂ＿ｇｅｎを更新し、ステップ２に進む。上回らない場合は、生成器ｇｅｎ（Ｃｉ）を更新し、ステップ３に進む。
【０１０１】
（６）  生成器ｇｅｎ（Ｃｉ）に応じて、入力を固定するかもしくは純粋なランダム・パターンを入力に適用することにより、３重みＷＲＰＴ用パターンを生成する。故障シミュレーションを実行して、生成された３重みＷＲＰＴ用パターンによって検出された故障を除去する。
【０１０２】
（７）  互換のオーバーライド信号をマージする。
【０１０３】
「各生成器のためのテストシーケンス」
ｍビットのＬＦＳＲを使用して、ｍ個の入力を有するＣＵＴにランダム・パターンを適用すると想定する。ＬＦＳＲはこれまで、最も低コストなランダム・パターン生成器として知られてきた。本項では、ＬＦＳＲを使用してランダム・パターンを生成する場合に、故障セットＦｉ内の全故障の検出に必要とされるパターン長を算出する方法について述べる。故障ｆのエスケープ確率とは、ｔ個のテストパターンを適用した後も故障ｆが検出されない確率である。エスケープ確率の詳細な背景情報については、P. H. B., W. H. McAnney, and J. Savir, Built-In Test for VLSI: Pseudorandom Techniques(疑似ランダム手法), John Wiley & Sons, 1987を参照。例えば、原始多項式を有するｍ段のＬＦＳＲによってｔ個のテストパターン（ここで、ｔ＜２ｍ）が生成された場合などには、テストパターンの反復は許可されない。このような場合には、ｔ個のテストパターンに対する故障ｆのエスケープ確率は以下によって得られる。
【０１０４】
【数７】
2004301856.tif 000009
ここで、Ｖｆは故障ｆのテストベクトル数である。２ｉｍ＞＞ｔの場合、式８は以下のように概算できる。
【０１０５】
【数８】
2004301856.tif 000010
エスケープ確率がε以下の場合において故障ｆの検出に必要なランダム・パターン長は、以下によって得ることができる。
【０１０６】
【数９】
2004301856.tif 000011
故障セットＦｉ＝｛ｆｉ，ｆ２，…，ｆｎ｝を、テストキューブ・セットＣｉ内のテストキューブによって検出される故障とする。故障セットＦｉ内のすべての故障を検出するためには、検出確率が最低の故障を検出するのに十分な長さを有するランダム・シーケンスを適用する必要がある。１サイクルごとに１個の新規のパターンが生成される場合には、時間間隔Ｔの間にＴ個のパターンを生成することができる。よって、時間間隔Ｔとテストシーケンス長Ｔは区別なく使用することができる。このようなシーケンスＴｍａｘは、以下によって得られる。
【０１０７】
【数１０】
2004301856.tif 000012
すべてのテストキューブの競合ビット数はＭ以上なので、各故障の検出確率は１／２Ｍ以下である。よって、式１１は以下のように書き換えることができる。
【０１０８】
【数１１】
2004301856.tif 000013
全数実験を実施した結果、０．２未満のｅを使用した場合には、いずれのＭ入力にも、２ｍＭビットのパターンを適用することができた。表１に、ε＝０．２及び０．１の場合に、異なるＭに必要とされるパターン長Ｔｍａｘを示す。
【０１０９】
【表１】
2004301856.tif 000014
単純なハードウェアについて、２の累乗でテストクロックを除算することによりパターン長Ｔｍａｘのクロックが生成される場合、時間間隔は、パターン長Ｔｍａｘ以上の２の最小累乗を算出することによって得られる。
【０１１０】
２Ｍ個の明確なＭビット・パターンがすべてＭ競合入力に適用され、かつ他の入力は時間間隔Ｔの間に生成器ｇｅｎ（Ｃｉ）に応じて固定された場合には、故障セットＦｉ内のすべての故障が検出されることが保証される。上記の条件を満たすパターンは、疑似全数テスト用に設計されたテストパターン生成器によっても生成できる。このようなパターンを生成できるテスト生成器としては、シンドローム・ドライバ・カウンタ、定数重みカウンタ、組み合わせＬＦＳＲ／ＳＲ、組み合わせＬＦＳＲ／ＸＯＲ、及び圧縮ＬＦＳＲが挙げられる。定数重みカウンタの詳細な背景情報については、D. T. Tang and L. S. Woo, Exhaustive Test Pattern Generation with Constant Weight Vectors(定数重みベクトルを有する全数テストパターンの生成). IEEE Trans. on Computers, Vol. C-32(12), December 1983、及びE. J. McCluskey, Verification Testing−A Pseudoexhaustive Test Techniques(確認テスト−疑似全数テスト手法), IEEE Trans. on Computers, Vol. C-33(6), June 1984を参照。組み合わせLSFR/SRの詳細な背景情報については、D.T.Tang and C.L. Chen, Logic Test Pattern Generation Using Linear Code (線形コードを使用した論理テストパターンの生成)、IEEE Trans. Computers, Vol. C-33(9), September 1984を参照。組み合わせLFSR/XORの詳細な背景情報については、S. B. Akers, On the Use of Linear Sums in Exhaustive Testing(全数テストにおける算術和の使用), in Proceedings IEEE International Conference on Fault-Tolerant Computing, pages 148-153, 1985を参照。圧縮ＬＦＳＲの詳細な背景情報については、L.-T. Wang and E. J. McCluskey, A New Condensed Linear Feedback Shift Register Design for VLSI/System Testing(VLSI／システムテストのための新規の圧縮線形フィードバック・シフト・レジスタ設計), in Proceedings IEEE International Conference on Fault-Tolerant Computing, pages 360-365, 1984、及びL.-T. Wang and E. J. McCluskey. Condensed Linear Feedback Shift Register (LFSR) Testing−A Pseudoexhaustive Test Techniques(圧縮線形フィードバック・シフト・レジスタ(LFSR)のテスト−擬似全数テスト手法). IEEE Trans. on Computers, Vol. C-35(4), April 1986を参照。
【０１１１】
「スキャン方式ビルトイン・セルフテストへの適用」
本項では、改良型スキャン方式ビルトイン・セルフテスト回路アーキテクチャの好適な実施例について論じる。Ｔｏｕｂａ’９６及びＷｕｎｄｅｒｌｉｃｈ  ｅｔ  ａｌとは対照的に、本発明のＢＩＳＴでは全２Ｍ個のＭビット・パターンを競合入力に適用するのに十分な長さの各時間間隔Ｔの間にランダム・シーケンスが生成されるので（本明細書の「各生成器のためのテストシーケンス」の項目を参照）、本発明のＢＩＳＴで達成される故障適用範囲は生成されるランダム・パターン・シーケンスによって左右されない。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), in Proceedings IEEE International Test Conference, pages 167-175, 1996、及びH.-J. Wunderlich and G. Kiefer, Bit-Flipping BIST(ビットフリップBIST), In Proceedings VLSI Testing Symposium, pages 337-343, 1996を参照。２種類のスキャン方式ビルトイン・セルフテストを開示する。ここでは、これら２種類のアーキテクチャを具体化する好適な実施例について論じる。
【０１１２】
「並列型スキャン方式ビルトイン・セルフテスト」
最初のタイプのスキャン方式ビルトイン・セルフテストは「並列型スキャン方式ビルトイン・セルフテスト」と呼ばれるもので、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴといくつかの点で類似している。図６は、本発明の手法を具体化する並列タイプスキャン方式ビルトイン・セルフテストの実装を示す。図６では、図１、図２に示す生成器及びオーバーライド信号と同じ回路例が使用されている。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴと同様に、オーバーライド信号はカウンタ６．３０の出力を入力としてデコーダ６．１０から生成される。ただし、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴではオーバーライド信号が対応するＡＮＤ及びＯＲゲートを駆動するのとは異なり、並列型スキャン方式ビルトイン・セルフテストでは、オーバーライド信号がスキャン回路６．６０〜６．６４内のスキャン要素のＳ（同期プリセット）及びＲ（同期リセット）ピンを駆動する。そのため、並列型スキャン方式ビルトイン・セルフテストでは、グローバル生成器ｇｌｏｂ＿ｇｅｎにおいて、スキャン要素ｈｉによって駆動されるスキャン入力ｐｉに１、０、またはＢが割り当てられている場合には、ＳまたはＲピンを有さないスキャン要素ｈｉ、（ｉ＝１，２，…）をＳまたはＲピン、またはその両方を有するスキャン要素に置換する必要がある。入力ｇｇｉ＝１の場合、スキャン要素ｈｉはＳピンを有するスキャン要素６．６２に置換される。入力ｇｇｉ＝０の場合、スキャン要素ｈｉはＲピンを有するスキャン要素６．６１に置換される。最後に、入力ｇｇｉ＝Ｂの場合、スキャン要素ｈｉはＳ及びＲピンの両方を有するスキャン要素６．６３に置換される。スキャン要素がすでに１つ以上の生成器において、対応するスキャン入力に１が割り当てられたハイ・アクティブＳピンを有する場合は、Ｓピンと通常のプリセット信号の間に２入力ＯＲゲート（または、Ｓピンがロー・アクティブの場合は２入力ＡＮＤゲート）が挿入されなければならない。同様に、スキャン要素がすでに１つ以上の生成器において、対応するスキャン入力に０が割り当てられたハイ・アクティブＲピンを有する場合は、Ｒピンと通常のリセット信号の間に２入力ＯＲゲート（または、Ｒピンがロー・アクティブの場合は２入力ＡＮＤゲート）が挿入されなければならない。例えば、図６に示す回路の入力ｐ１を駆動するスキャン要素６．６０は、元の回路内にその通常動作時にセット／リセット論理によって制御されるＳピンを有していたので、オーバーライド信号ｓ１／０とスキャン要素６．６０のＳピンの間にＯＲゲートが挿入される。ＬＦＳＲ６．２０は、ランダム・テストパターンを生成する。
【０１１３】
ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴと並列型ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴのもう１つの違いは、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴではデコーダ３．１０の入力ピンＥＮはイネーブル信号３．３０によって直接駆動されるのに対し、並列型ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴではデコーダ６．１０のＥＮは、２個の入力がそれぞれＬＡＳＴ＿ＳＣＡＮ信号とイネーブル信号によって駆動される２入力ＡＮＤゲート６．４０によって駆動されることである。スキャン方式ビルトイン・セルフテストはｎ個のテストクロックを必要とする。ここでｎは、スキャン・シフト操作時にテストベクトルをスキャン回路にスキャンにより取り込むための、スキャン回路内のスキャン要素数である。続いて、スキャン回路内のスキャン要素は、通常モードにおいてスキャンにより取り込まれたテストベクトルへの応答を捕捉するように構成される。ＬＡＳＴ＿ＳＣＡＮは、各スキャン・シフト操作の終わりの１サイクルについては１に設定され、他のサイクルでは０に設定される。従ってデコーダ６．１０は、スキャン・シフト操作の終わり、すなわちランダム・パターン生成器によって生成されたベクトルがスキャン回路内に完全にロードされた時点にのみ有効化される。デコーダが有効化されると、オーバーライド信号は、現在適用中の生成器内で２値データが割り当てられたスキャン要素のＳまたはＲピン、もしくはその両方を活動化することによってスキャン回路にロードされるランダム・ベクトルを変更する。
【０１１４】
並列型スキャン方式ビルトイン・セルフテストの領域オーバーヘッドは、ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴのそれに近い。また、並列型スキャン方式ビルトイン・セルフテストには、オーバーライド信号を減少させるためのマージ手法（本明細書の「オーバーライド信号のマージ」の項目を参照）を適用できる。
【０１１５】
「逐次タイプのスキャン方式ビルトイン・セルフテスト」
図７に、「逐次タイプのスキャン方式ビルトイン・セルフテスト」と呼ばれる本発明による第２のタイプのスキャン方式ビルトイン・セルフテストの好適な実施例を示す。デコーダ７．４０の２個の出力信号ＤＯ及びＤｌによってそれぞれ駆動されるＯＲ７．２０ゲートとＡＮＤ７．３０ゲートは、ＬＦＳＲ７．１０によって生成されるランダム・パターン・シーケンスを改変する。カウンタ７．６０及びスキャンカウンタ７．５０は、デコーダの２個の出力信号の状態を決定する。スキャンカウンタは、（ｎ＋１）モジュロ・カウンタである。ここで、ｎはスキャン回路７．７０内のスキャン要素数である。スキャンカウンタには、少なくとも［ｌｏｇ（ｎ）］段のカウンタが必要である。スキャンカウンタはすべてのスキャン方式ビルトイン・セルフテスト手法に必要とされるものであり、本発明の３重みＷＲＰＴ  ＢＩＳＴだけに必要とされるのではないことに注意されたい。
【０１１６】
並列タイプスキャン方式ビルトイン・セルフテスト及びｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴと同様に、逐次タイプのスキャン方式ビルトイン・セルフテストのデコーダの領域オーバーヘッドは、生成器数（カウンタの段数）及びグローバル生成器ｇｌｏｂ＿ｇｅｎ内で指定されるオーバーライド信号数によって決まる。典型的には、ランダム・パターン耐性が同等な場合は、回路内のスキャン要素が多いほど必要なオーバーライド信号も多くなる。そのため、多数のスキャン要素を有する回路では、デコーダを実装するために必要とされる領域オーバーヘッドは高レベルとなる。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴ及び並列型スキャン方式ビルトイン・セルフテストでは、現在適用中の生成器内で２値データが割り当てられたすべての入力が、同じサイクルにおいて並行して対応する２値データに固定されるため、すべての互換のオーバーライド信号を１個のオーバーライド信号にマージすることが可能である。
【０１１７】
一方、逐次タイプのスキャン方式ビルトイン・セルフテストにはわずか２個のオーバーライド信号しかないため、現在適用中の生成器内で２値データが割り当てられたスキャン入力用の値は、この２個のオーバーライド信号によって（異なるサイクルにおいて）逐次的に改変される。そのため、本明細書の「オーバーライド信号のマージ」の項目にて説明した、デコーダの領域オーバーヘッドを減少させるために互換のオーバーライド信号をマージする手法は、逐次タイプのスキャン方式ビルトイン・セルフテストには適用できない。逐次タイプのスキャン方式ビルトイン・セルフテストでは、図１１に示すデコーダの出力とＡＮＤ及びＯＲゲートの間にトグル・フリップフロップ９．１０及び９．２０を挿入することによってデコーダの領域オーバーヘッドを低減することができる。
【０１１８】
ここでは、図８に示す、２個の生成器ｇｅｎ（Ｃ０）及び生成器ｇｅｎ（Ｃ１）のための逐次タイプスキャン方式ビルトイン・セルフテストを実装する場合を取り上げる。最初に、図７に示す実装について考察する。この実装ではデコーダの出力はＡＮＤ及びＯＲゲートに直接接続されており、デコーダの一方の出力信号Ｄ０はＡＮＤゲートの入力に、デコーダのもう一方の出力信号Ｄ１はＯＲゲートの入力にそれぞれ接続されている。スキャンカウンタの初期値を０とし、スキャン入力ｐ０の値は最初にスキャンされ、スキャン入力ｐ７の値は最後にスキャンされるものと想定する。スキャンカウンタは各スキャン・シフト・サイクルのポジティブ（またはネガティブ）エッジにおいて１増分され、スキャン入力の新規の値がスキャンによりスキャン回路に取り込まれる。これは、スキャン入力全８個の新規の値がスキャンにより取り込まれるまで繰り返される。現在カウンタの値がｉ及びスキャンカウンタの値がｊであれば、入力ｇｉｊによって決定される入力ｐｊの値がスキャンにより取り込まれる。すなわち、入力ｇｉｊ＝１の場合には１がスキャンにより取り込まれ、入力ｇｉｊ＝０の場合には０がスキャンにより取り込まれ、入力ｇｉｊ＝ＵまたはＸの場合にはランダム２値データがスキャンにより取り込まれる。
【０１１９】
図８では、生成器ｇｅｎ（Ｃ０）内において入力ｇ０３、ｇ０５、及びｇ０６に１が割り当てられ、生成器ｇｅｎ（Ｃ１）内においては入力ｇ１４、ｇ１５、及びｇ１７に１が割り当てられている。従ってｓ１は、カウンタの値が０及びスキャンカウンタの値が３、５、６の場合と、カウンタの値が１及びスキャンカウンタの値が４、５、７の場合に１に設定される。ｓ１の関数のオンセットは６個の最小項を有する。同様にｓ０は、カウンタの値が０及びスキャンカウンタの値が１、２、４の場合と、カウンタの値が１及びスキャンカウンタの値が０、２、３の場合に１に設定される。ｓ０の関数のオンセットもやはり６個の最小項を有する（図９参照）。
【０１２０】
図１１は、前項で説明した逐次タイプスキャン方式ビルトイン・セルフテストの別の実装を示す。トグル・フリップフロップＴＦ１  ９．１０はデコーダ９．３０の出力Ｄ１とＯＲゲート９．４０の入力の間に挿入され、トグル・フリップフロップＴＦ０  ９．２０はデコーダのもう一方の出力信号Ｄ０とＡＮＤゲート９．５０の入力の間に挿入されることに注意されたい。各スキャン・シフト操作の開始前に、トグル・フリップフロップＴＦ０は１に初期化され、トグル・フリップフロップＴＦ１は０に初期化されると想定する。カウンタ及びスキャンカウンタは、それぞれ９．６０と９．７０である。最初に、生成器ｇｅｎ（Ｃ０）を適用する場合について考察する。ＴＦ１の状態は、カウンタの値が０及びスキャンカウンタの値が２になるまで０であり、この状態は入力ｐ３の値がスキャンされたとき、すなわちカウンタの値が０及びスキャンカウンタの値が３になったときに１にトグルされる。入力ｐ３は、生成器ｇｅｎ（Ｃ０）内で１を割り当てられたスキャン回路の最初のスキャン入力である。入力ｇ０４＝０なので、トグル・フリップフロップＴＦ１の状態は次のサイクル、すなわちスキャンカウンタの値が４で０にトグルされなければならない。さらに、トグル・フリップフロップＴＦ１の状態はカウンタの値が０及びスキャンカウンタの値が５でもう一度トグルされ、スキャン・シフト・サイクルの終わりまで１にとどまる必要がある。入力ｐ４は生成器ｇｅｎ（Ｃ１）において１を割り当てられたスキャン回路内の最初のスキャン入力なので、カウンタの値が１、すなわち生成器ｇｅｎ（Ｃ１）の適用中には、トグル・フリップフロップＴＦ１の状態はスキャンカウンタの値が４のときに１度だけトグルされる必要がある。そして、入力ｐ４に続くスキャン回路内のその他すべてのスキャン入力には、生成器ｇｅｎ（Ｃ１）内でＸまたは１だけが割り当てられる。以上の説明は、次のようにまとめることができる。ｓ１の関数のオンセットはわずか４個の最小項、すなわち、カウンタの値が０及びスキャンカウンタの値が３、カウンタの値が０及びスキャンカウンタの値が４、カウンタの値が０及びスキャンカウンタの値が５、カウンタの値が１及びスキャンカウンタの値が４を有している。同様に、ｓ０の関数のオンセットもやはり４個の最小項を有する（図１０参照）。入力ｇｉｊ＝１、すなわちトグル・フリップフロップＴＦ１＝１の場合、ＯＲゲートの出力にはトグル・フリップフロップＴＦ０の状態には関係なくトグル・フリップフロップＴＦ１＝１によって１を割り当てることができるので、トグル・フリップフロップＴＦ０の状態はドントケアである。従って、トグル・フリップフロップＴＦ０の状態はカウンタの値が０及びスキャンカウンタの値が５で変更されなければならない。この例では、トグル・フリップフロップを挿入することによる最小項の減少数は４個だけであるが、長いスキャン回路を有する実際の回路では、トグル・フリップフロップを挿入することによって最小項の数は劇的に減少する。
【０１２１】
必要な領域オーバーヘッドが最小のデコーダを得るためには、各生成器のためのスキャン・シフト操作中にトグル・フリップフロップが状態を変更する回数が最小になるように、スキャン回路の順序を変更する必要がある。本発明では、スキャン回路の順序変更の問題は、遺伝的アルゴリズムを使用することによって確立される。遺伝的アルゴリズムの詳細な背景情報については、D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning(探索、最適化、及び機械学習における遺伝的アルゴリズム). Addison Wesley, Reading, M.A., 1989を参照。
【０１２２】
遺伝的アルゴリズムは、Hollandによって紹介されて以来、適度な計算時間内にＮＰ完全問題を解決できる手法として広く使用されてきた。J. H. Holland, Adaptation in Natural and Artificial Systems(自然及び人工システムでの適用), University of Michigan Press, Ann Arbor, M.I., 1975を参照。遺伝的アルゴリズムは、ランダムに生成される初期母集団から開始する。各個体には遺伝コードが割り当てられ、さらに、遺伝コードから計算された適合関数が与えられる。各世代の個体は、遺伝的進化の過程で存続または消滅する。良好な適合関数を有する個体は、存続して次の世代に送られる可能性が高まる。存続する個体はしばしば、他の個体と遺伝子コードを交換し（クロスオーバー）、遺伝コードの一部をフリップする（突然変異）ことにより、部分的に異なる遺伝コードを持つ子孫を生み出す。
【０１２３】
本発明で使用される遺伝的アルゴリズムでは、スキャン回路に含まれるスキャン要素の順列が各個体の遺伝子コードとしてコード化される。本発明で使用される遺伝的アルゴリズムの目的は、最小数の最小項を有するデコーダの関数に到達するスキャン要素の順序を発見することにある。各生成器において割り当てられた値に応じてランダム・テストシーケンスを改変するために、２個のトグル・フリップフロップにおいて必要とされるトグルの回数を意味する非負適合関数が、現世代の各個体について以下の式により計算される。
【０１２４】
【数１２】
2004301856.tif 000015
ここで、ｄは生成器数、ｎはスキャン入力数であり、Toggle０（ｉ、ｊ）及びToggle１（ｉ，ｊ）は以下によって得られる。
【０１２５】
【数１３】
2004301856.tif 000016
ここで、トグル・フリップフロップＴＦ０（ｉ，ｊ−１）及びトグル・フリップフロップＴＦ１（ｉ，ｊ−１）は、直前のスキャン・シフト・サイクルにおけるトグル・フリップフロップの状態である。初期状態は（ｊ＝１）、トグル・フリップフロップＴＦ０（ｉ，ｊ）＝１、トグル・フリップフロップＴＦ１（ｉ，ｊ）＝０であり、それ以降は、トグル・フリップフロップＴＦ０（ｉ，ｊ）（ＴＦ１（ｉ，ｊ））はToggle０（ｉ，ｊ）＝１（Toggle１（ｉ，ｊ）＝１）の場合に常にその状態をトグルする。
【０１２６】
ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴと並列型スキャン方式ビルトイン・セルフテストで互換のオーバーライド信号のマージが可能であるのと同様に、逐次タイプのスキャン方式ビルトイン・セルフテストでも互換のスキャン入力のマージは可能である。このマージは、遺伝的アルゴリズムによるスキャン回路の順序付けの前に行われる。任意の２個のスキャン入力ｐｉ及び入力ｐｊは、入力ｇａｉの値が入力ｇａｊの値と同じか、あるいは各生成器において入力ｇａｉまたは入力ｇａｊのいずれかにＸが割り当てられていれば互換である。これ以外の場合は、入力ｐｉと入力ｐｊは互換ではない。個々のスキャン入力を順序付けする代わりに、互換のスキャン入力同士を１つのスキャン入力グループにマージしてグループ単位で順序付けを行うことにより、遺伝的アルゴリズムへの入力数が減少し、最小数の最小項に到達する順序が得られるまでの遺伝的アルゴリズムの実行時間が短縮される。
【０１２７】
スキャン要素にはルーティングまたはロード・キャパシタンスの制約（またはタイミングの制約）があるので、一部のスキャン要素を近隣に配置することにより、ルーティングやロード・キャパシタンスの制約違反を回避する必要がある。スキャン回路の順序変更におけるこの制約は、スキャン入力の互換性を活用することにより緩和できる。逐次タイプのスキャン方式ビルトイン・セルフテストのトグル・フリップフロップは、互換のスキャン入力の値がスキャンにより取り込まれている間は、その状態をトグルしない。そのため、互換スキャン入力グループ内でスキャン入力を並び替えることによってスキャン要素のルーティングやロード・キャパシタンスの制約を満足することができ、しかもオーバーライド信号を生成するデコーダを実装するための関数の最小項数は増大しない。典型的には、各生成器ではかなりの数のスキャン入力にＸが割り当てられる。これらのスキャン入力はスキャン回路内の他のどのスキャン入力とも互換性があるので、スキャン回路内の任意の場所に配置できる。これらのスキャン入力を適切な場所に配置すると、デコーダを実装するための最小項数を増大させることなく、スキャン要素のルーティングやロード・キャパシタンスの制約を満たすことができる。
【０１２８】
逐次タイプのスキャン方式ビルトイン・セルフテストはデコーダを実装するためのハードウェア・オーバーヘッドは、並列型スキャン方式ビルトイン・セルフテストのそれよりも多いのが典型的である。ただし、逐次タイプのスキャン方式ビルトイン・セルフテストでは、Ｒ及び／またはＳピンを有するスキャン要素や、並列型スキャン方式ビルトイン・セルフテストでスキャン入力を固定するために必要とされる追加の２入力ＯＲまたはＡＮＤゲートが不要なので、逐次タイプのスキャン方式ビルトイン・セルフテストを実装するための全体的なハードウェア・オーバーヘッドは、並列型スキャン方式ビルトイン・セルフテストを実装するためのそれと同等である。さらに、並列型スキャン方式ビルトイン・セルフテストでは、オーバーライド信号をデコーダの出力ピンから固定されるべきスキャン入力の対応するＳ及び／またはＲピンまで接続するためのルーティング・オーバーヘッドが必要とされるのに対し、逐次タイプのスキャン方式ビルトイン・セルフテストでは、オーバーライド信号は２個しかないのでルーティング・オーバーヘッドはほとんど必要とされない。従って、ＢＩＳＴが挿入される設計にルーティングの輻輳が存在する場合には、逐次タイプのスキャン方式ビルトイン・セルフテストの方が適している。
【０１２９】
「実験結果」
表２に、本発明のＢＩＳＴを使用したシミュレーションの実験結果を示す。これらの実験は、論理合成ベンチマーク回路とＩＳＣＡＳベンチマーク回路を使用して実施した。ほとんどの論理合成ベンチマーク回路には、ＩＳＣＡＳベンチマーク回路のそれよりもはるかに多い検出困難故障が存在する。また、本発明の改良型ＡＴＰＧのスケーラビリティを実証するため、大規模なＩＳＣＡＳベンチマーク回路に関する実験結果も報告する。実験は、１ギガバイトのメモリを搭載した３００ＭＨｚ  Ｓｕｎ  Ｕｌｔｒａ２上で実施した。
【０１３０】
ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴの実験では、回路のすべてのフリップフロップの出力を一次入力とし、すべてのフリップフロップの入力を一次出力とする。スキャン方式ビルトイン・セルフテストの実験ではさらに、どの一次入力も回路内の全フリップフロップを含む同じスキャン回路によって駆動され、これらのフリップフロップはすべてスキャン要素に変換されると想定する。「＃ＰＩ」のラベルが付けられたカラムは一次入力数を示し、「＃ｌｉｎｅｓ」のそれは各回路の回路ライン数を示す。「＃ＨＦ」のラベルが付けられたカラムは、疑似ランダム・パターン・セットの適用後に未検出のまま残る故障数を示す。このカラムの括弧内の数字は、検出容易な故障（短くて検出が容易な故障）を検出するために適用される疑似ランダム・パターン数である。「ＥＦＣ」のラベルが付けられたカラムは、疑似ランダム・パターンを適用することによって得られる故障適用範囲を示す。本発明の手法は多数の検出困難故障が含まれる回路にも適用可能であることを実証するため、非常に短いランダム・パターン・シーケンスを適用する。「＃ＲＰＬ」のラベルが付けられたカラムは、１００％かそれに近い故障適用範囲が達成されるまでにｍ段のＬＦＳＲ（ｍは入力数）によって生成される純粋な疑似ランダム・パターン数を示す。「Ｔｌｅｎ」のラベルが付けられたカラムは、１００％の故障適用範囲が達成されるまでに本発明のＢＩＳＴによって生成されるテストパターンの総数を示す。このカラムの括弧内の数字は本発明のＢＩＳＴ手法によるテストシーケンス長の減少率である。競合入力へのランダム・パターンの適用は、ｍ段のＬＦＳＲ（ｍは入力数）を使用して行われる。「Ｍ」のラベルが付けられたカラムは、各テストキューブ・セットの最大競合入力を示す。「Ｔ」のラベルが付けられたカラムは、各生成器が回路に適用される時間を示す。「＃Ｇ」のラベルが付けられたカラムは、本発明の改良型ＡＴＰＧによって生成される生成器数を示す。「前  ＃ＯＳ」のラベルが付けられたカラムは、互換のオーバーライド信号がマージされる前のオーバーライド信号数を示し、「後  ＃ＯＳ」は互換のオーバーライド信号がマージされた後のオーバーライド信号数を示す。「実行時間」のラベルが付けられたカラムに示される実行時間は、本発明の改良型ＡＴＰＧの実行時間と、本発明のＢＩＳＴによって生成されるテストシーケンス（容易な故障を検出するために適用される疑似ランダム・パターン・シーケンスと、３重みＷＲＰＴシーケンス）全体の故障シミュレーション時間の合計である。いずれの回路についても、バックトラック限度は５００とする。
【０１３１】
【表２】
2004301856.tif 000017
上記回路のランダム・パターン・シーケンスは（ＡＫ96）で報告されている。
【０１３２】
「デコーダ」の見出しのカラムは、ゲート等価としてオーバーライド信号を生成するデコーダを実装したことによるハードウェア・オーバーヘッドを示す。「ＴＰＣ」のラベルが付けられたカラムはｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴ実装のハードウェア・オーバーヘッドを示し、「ＴＰＳ」のラベルが付けられたカラムは逐次タイプスキャン方式ビルトイン・セルフテストのハードウェア・オーバーヘッドを示す。２個のトグル・フリップフロップを挿入し、スキャン回路の順序を変更する（セクション６．２参照）ことによりデコーダの実装によるハードウェア・オーバーヘッドの縮小が可能なことを実証するため、両実装のゲート等価についても報告する。これは、トグル・フリップフロップと順序を変更したスキャン回路を使用する実装（カラム左側の数字）と、トグル・フリップフロップを使用しない実装（このカラムの括弧内の数字）として示す。デコーダ回路は、２層回路実装用のＳＩＳを実行することによって得られる。デコーダの合成には、ＮＡＮＤ、ＮＯＲゲート、及びインバータのみを使用する。ゲート等価は、Ｊ．  Ｈａｒｔｍａｎｎで提案される方法で算出する。この方法では、ｉｎ入力ＮＡＮＤまたはＮＯＲゲートについては０．５ｎ、インバータについては０．５が使用される。I. Hartmann and G. Kemnitz, How to Do Weighted Random Testing for BIST(BISTのための加重ランダムテストの実行方法), in Proceedings IEEE International Conference on Computer-Aided Design, pages 568-571, 1993を参照。
【０１３３】
すべてのベンチマーク回路について、１００％故障適用範囲が達成される。１００％故障適用範囲の達成に要する時間は、本発明のＢＩＳＴ手法によって劇的に短縮される。Ｍ．Ｆ．ＡｌＳｈａｉｂｉには、ｓ８３８で１００％の故障適用範囲を達成するためには１億個以上のテストパターンが必要であると報告されている。M. F. AlShaibi and C. R. Kime, MFBIST: A BIST Method for Random Pattern Resistant Circuits(ランダム・パターン耐性回路のためのBIST法), In Proceedings IEEE International Test Conference, pages 176-185, 1996を参照。一方、本発明のＢＩＳＴによって生成されるテストパターンは、わずか５１２＋６×５１２＝３，０７２個のテストパターンで同じ故障適用範囲を達成する。ここで、５１２は容易な故障を検出するために適用される純粋ランダム・パターン数である。これは、全故障の検出に必要とされるテスト長が、約３２×１０６分の１に短縮されることを意味する。長い純粋ランダム・テストシーケンスを必要とするランダム・パターン耐性回路の場合は、これを上回る短縮が実現されることは明らかである。例えば、ｘｐａｒｃ、ｓ８３８、ｃ５３１５、ｃ７５５２などではテストシーケンス長は数桁分も縮小されるので、顕著な効果が期待できる。実験では３４２８個という非現実的なほどに多数の検出困難故障が使用されるにもかかわらず、最も多くの生成器を必要とするｓ３８４１７でさえもわずか２６個の生成器しか必要としないことに注目する必要がある。これは、検出のための入力割り当てが多数の検出困難故障のテストの間で共有されるためである。本発明のＢＩＳＴに必要とされるテストシーケンス長は生成器数によって決定されることから、この実験結果により、多数の検出困難故障を含む回路の場合でもテストシーケンス長は増大しないことが実証される。事実、すべての回路で非常に多くの検出困難故障が使用されているが、３重みＷＲＰＴのテストシーケンス長は、容易な故障を検出するためにほとんどの回路で適用される疑似ランダム・テストシーケンス長さえも下回る。このことから、大きなＭについて適度な長さのテストシーケンスを算出することにより、本発明のＢＩＳＴを実装するためのハードウェア・オーバーヘッドはほとんどの実用設計において低レベルに抑えられることは明らかである。
【０１３４】
本発明のＢＩＳＴ手法を実装するためにＬＦＳＲなどの疑似ランダムＢＩＳＴ回路に追加されるハードウェア・オーバーヘッドを推定するため、オーバーライド信号を生成するデコーダのゲート等価を列挙する。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴにおいてランダム信号をオーバーライドするために疑似ランダムＢＩＳＴ回路に追加すべきＡＮＤ及び／またはＯＲゲートの数（図３参照）は、互換の入力がマージされる前のオーバーライド信号の数（「前  ＃ＯＳ」のカラムに示す数）と同じである。各生成器を選択するカウンタを実装するためのフリップフロップ数は、単に［ｌｏｇ２（生成器数）］として算出できる。よって、生成器数の増大に伴う増大はごくわずかである。２６個の生成器を必要とするｓ３８４１７でも、５ビットのカウンタで十分である。ｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴ及び並列型スキャン方式ビルトイン・セルフテストのためのデコーダを実装するために必要とされるハードウェアは非常に少ない。ｓ３８４１７のような大規模な回路に３４２８個の困難な故障が含まれる場合でも、ゲート等価は１６９．５に過ぎない。デコーダを実装するためのハードウェア・オーバーヘッドについては、逐次タイプのスキャン方式ビルトイン・セルフテストの方がｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴよりも多いが、デコーダを実装するためのハードウェア・オーバーヘッドの影響はごくわずかである。例えば、組み合わせ部分が約２４，５００ゲート等価となるｓ３８４１７の場合、逐次タイプスキャン方式ビルトイン・セルフテストのデコーダを実装するために必要とされるゲート等価はわずか６２６である。これは、ｓ３８４１７の組み合わせ部分のゲート等価に対する比率でいえば２．６％に過ぎない。このことから、本発明のＢＩＳＴを適用することにより、多数の検出困難故障を有する大規模な回路でも低コストで故障を検出できることは明らかである。
【０１３５】
実験結果は、逐次タイプのスキャン方式ビルトイン・セルフテストの実装に伴うハードウェア・オーバーヘッドは、トグル・フリップフロップの挿入とスキャン回路の順序変更によって大幅に削減されることを示している。ｘｐａｒｃ、ｂｃ０、ｒｃｋｌなどの少数の回路を除いて、ほとんどの回路ではゲート等価が大幅に減少する（前述の回路においても、ゲート等価の増大はごくわずかである）。特に減少幅が大きいのは、ｓ９２３４（７６％の減少）、ｓ１３２０７（６８．５％の減少）、ｓ３８４１７（６６．４％の減少）、ｓ３８５８４（６６．３％の減少）などの大規模な回路である。
【０１３６】
表に示される実行時間からも、本発明の改良型ＡＴＰＧの有効性は明らかである。ほとんどの回路では、本発明の改良型ＡＴＰＧの実行時間よりもむしろ、本発明のＢＩＳＴシーケンスにより得られた故障適用範囲を測定するための故障シミュレーションの方に多くの実行時間が費やされることが、実験により示されている。
【０１３７】
表３は、テストシーケンス長（「Ｔｌｅｎ」の見出し）と純粋疑似ランダムＢＩＳＴに追加されるハードウェア・オーバーヘッドに関して、本発明のｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴの結果と、類似のランダム・パターンテスト手法を使用する他のｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴ法の結果を比較したものである。これらの他の方法の詳細な背景情報については、I. Pomeranz and S, Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993、M. Bershteyn, Calculation of Multiple Sets of Weights for Weighted Random Testing(加重ランダムテストのための複数重みセットの計算), in Proceedings IEEE International Test Conference, pages 1031-1040, 1993、M. F. AlShaibi and C. R. Kime, Fixed-Biased Pseudorandom Built-In Self-Test For Random Pattern Resistant Circuits(ランダム・パターン耐性回路のための固定バイアス疑似ランダム・ビルトイン・セルフテスト), in Proceedings IEEE International Test Conference, pages 929-938, 1994、及びN. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), in Proceedings IEEE International Test Conference, pages 674-682, 1995を参照。
【０１３８】
ハードウェア・オーバーヘッドは、フリップフロップＦＦとゲートＧＥについて個別に推定される。Bershetyn、Pomeranz et al及びTouba '95のGEは、Touba '95. M. Bershteyn, Calculation of Multiple Sets of Weights for Weighted Random Testing(加重ランダムテストのための複数重みセットの計算), In Proceedings IEEE International Test Conference, pages 1031-1040, 1993、I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993、N. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), In Proceedings IEEE International Test Conference, pages 674-682, 1995に述べられる方法で計算される。
【０１３９】
【表３】
2004301856.tif 000018
Ｍ．  Ｂｅｒｓｈｔｅｙｎでは、従来の加重ランダム・パターンＢＩＳＴが様々な重みと共に使用される。M. Bershteyn. Calculation of Multiple Sets of Weights for Weighted Random Testing(加重ランダムテストのための複数重みセットの計算). In Proceedings IEEE International Test Conference, pages 1031-1040, 1993を参照。「WS」のカラムは、重みセット数を示す。フリップフロップ、FF、及びゲートGEは以下のように計算される。
【０１４０】
ＦＦ＝ｌｏｇ２（重みセット数）
ＧＥ（４＋（１．５）ＷＳ）（ＣＵＴ内の入力数）
Pomeranzでは、本発明のＢＩＳＴと類似した手法が使用されている。I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993を参照。Pomeranzが本発明のBISTと異なっている点は、テストキューブの生成方法である。I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993を参照。
【０１４１】
本発明の手法とは対照的に、Pomeranzでは、固定すべき入力を発見するための手順を適用する前にすべての検出困難故障のテストキューブが生成される。I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits(組み合わせ回路及び順次回路のための決定用テストセットに基づく３重み疑似ランダム・テスト生成器), IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993を参照。入力のサブセットは、３ゲート・モジュールを使用して「拡張テスト」と呼ばれる決定用ベクトルに固定される。ハードウェア・オーバーヘッドは以下のように計算される。
【０１４２】
ＦＦ＝ｌｏｇ２（拡張テスト数）
ＧＥ＝（３ゲート・モジュール数）（１＋平均ファンイン）
Ｔｏｕｂａ’９５では、新規故障を検出しないランダム・ベクトルは、ＴＰＧとＣＵＴの入力の間に配置されたマッピング論理によって、検出困難故障の決定用ベクトルにマッピングされる。N. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), in Proceedings IEEE International Test Conference, pages 674-682, 1995を参照。「ＧＥ」のカラムは、マッピング論理のゲート等価を示す。ゲート等価の推定は、Ｊ．Ｈａｒｔｍａｎｎに基づき、ｎ入力ＮＡＮＤまたはＮＯＲについては０．５ｎＧＥ、ｉｎ入力ＸＯＲについては２．５（ｎ−１）ＧＥ、及び２−ｔｏ−１ＭＵＸについては１．５ＧＥを使用して行われる。J. Hartmann and G. Kemnitz, How to Do Weighted Random Testing for BIST(BISTのための加重ランダムテストの実行方法), in Proceedings IEEE International Conference on Computer-Aided Design, pages 568-571, 1993を参照。マッピング論理は回路のパフォーマンスを著しく減じる可能性があるので、通常動作時にはMUXを使用してマッピング論理をバイパスすることが推奨される。「ＧＥ」のカラムに括弧で示した数字には、これらのＭＵＸのゲート等価が含まれる。M. F. AlShaibi and C. R. Kime, MFBIST: A BIST Method for Random Pattern Resistant Circuits(ランダム・パターン耐性回路のためのBIST法), In Proceedings IEEE International Test Conference, pages 176-185, 1996を参照。
【０１４３】
M.F.AlShaibi’96は、複数のアイドラ・レジスタを使用してランダム・パターンまたは固定値を回路の入力に適用するM.F.AlShaibi’94の改良版である。M. F. AlShaibi and C. R. Kime, MFBIST: A BIST Method for Random Pattern Resistant Circuits(ランダム・パターン耐性回路のためのBIST法), in Proceedings IEEE International Test Conference, pages 176-185, 1996、及びM. F. AlShaibi and C. R. Kime, Fixed-Biased Pseudorandom Built-In Self-Test For Random Pattern Resistant Circuits(ランダム・パターン耐性回路のための固定バイアス疑似ランダム・ビルトイン・セルフテスト), in Proceedings IEEE International Test Conference, pages 929-938, 1994を参照。
【０１４４】
固定すべき各入力にＳＦＮセルが割り当てられる。２個のフリップフロップからなる各ＳＦＮセルは、２個のフリップフロップの接続部を再構成することにより４種類のモードで機能できる。各構成シーケンスについて、メモリ装置に記憶される新規の固定値セットが対応するＳＮＦセルにロードされる。報告されるハードウェア・オーバーヘッドは、ＳＦＮセル（固定入力数）分のゲート等価のみを含む。
【０１４５】
ＧＥ＝（ＳＦＮcostｘＦ＝７ｘＦ）
他の方法では、複合回路の可能性があるＢＩＳＴコントローラのハードウェア・オーバーヘッドはカウントされない。これに対し本発明のＢＩＳＴのＧＥには、入力が固定されるゲートだけでなく、ＢＩＳＴコントローラを実装するためのゲートも含まれる。それでもなお、本発明のＢＩＳＴのＧＥはほとんどの回路よりも小規模である。その主な理由は、本発明の改良型ＡＴＰＧを導入したことにあると考えられる。多数のフリップフロップを必要とするＭ．Ｆ．ＡｌＳｈａｉｂｉに比較して、本発明のＢＩＳＴではフリップフロップはほとんど必要とされない（最大規模の回路でもわずか５個）。同様に、Ｍ．Ｆ．ＡｌＳｈａｉｂｉでは複雑な制御方式が必要とされるのに対し、本発明のＢＩＳＴのアーキテクチャはごく単純である。M. F. AlShaibi and C. R. Kime, MFBIST: A BIST Method for Random Pattern Resistant Circuits(ランダム・パターン耐性回路のためのBIST法), In Proceedings IEEE International Test Conference, pages 176-185, 1996を参照。
【０１４６】
一部の回路は、テストシーケンス長が本発明のＢＩＳＴよりも短い。N. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST(BIST用の変換疑似ランダム・パターンを生成するためのマッピング論理の合成), in Proceedings IEEE International Test Conference, pages 674-682, 1995、M. F. AlShaibi and C.R. Kime, MFBIST: A BIST Method for Random Pattern Resistant Circuits (ランダム・パターン耐性回路のためのBIST法), In Proceedings IEEE International Test Conference, pages 176-185, 1996を参照。ただし、本発明の手法では、生成器ｇｅｎ（Ｃｉ）が適用される時間Ｔｉは、どの生成器ｇｅｎ（Ｃｉ）（ここで、ｉ＝０，１，２，…）についても同じである。そのため本発明のＢＩＳＴでは、全Ｔｉ個のテストパターンが適用される前に生成器ｇｅｎ（Ｃｉ）がターゲットとする全故障の検出が完了するが、生成器ｇｅｎ（Ｃｉ）のテストパターンの生成は全Ｔｉ個のテストパターンを生成し終わるまで続けられる。多数のテストパターンが新規故障を検出することなく破棄されるので、テストシーケンス長は不必要に長くなる。各生成器がターゲットとする全故障の検出完了と同時に各生成器の適用が終了するように可変時間を使用するとテストシーケンス長を短縮できるが、これによりＢＩＳＴコントローラが複雑となる。ＢＩＳＴコントローラの実装によるハードウェア・オーバーヘッドを含めても、本発明のＢＩＳＴのＧＥがほとんどの回路のそれよりも小さいのは、１つにはこの理由による。すべての生成器に同じ時間を使用することのもう１つの利点は、固定されていない入力に適用されるランダム・パターン・シーケンスへの実装されたＢＩＳＴの依存度が低減することである。これにより、ＢＩＳＴコントローラの実装後でも、本発明のＢＩＳＴのランダム・パターン・シーケンスを生成するために使用されるＬＦＳＲのフィードバック多項式またはシードを変更することが可能になる。各生成器を適用する時間は２の累乗（ランダム・パターン・シーケンスが容易な故障を検出するための時間も２の累乗）であることに注意されたい。これもまた本発明のＢＩＳＴのテストシーケンス長を増大させるが、ハードウェア・オーバーヘッドは減少する。
【０１４７】
表４は、本発明のスキャン方式ビルトイン・セルフテストの結果と他のスキャン方式ビルトイン・セルフテスト法のそれを比較したものである。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference, pages 167-175, 1996、H.-J. Wunderlich and G. Kiefer. Bit-Flipping BIST(ビットフリップBIST), In Proceedings VLSI Testing Symposium, pages 337-343, 1996、及びM. Karkala, N A. Touba, and H.-J. Wunderlich. Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test SymposIum, 1998を参照。テストシーケンス長とハードウェア・オーバーヘッドの結果を比較した。本発明のＢＩＳＴのハードウェア・オーバーヘッドは、逐次タイプのスキャン方式ビルトイン・セルフテスト実装のそれである。
【０１４８】
Ｔｏｕｂａ’９６及びKarkala et alでは、「ＬＦＳＲサイズ」のラベルが付けられたカラムは、疑似ランダム・シーケンスの生成に使用されるＬＦＳＲの段数を示す。「Ｓｅｑ．ＩＤ  Ｒｅｇ．サイズ」のラベルが付けられたカラムは、ビット固定シーケンス生成論理の入力の１つを駆動するそのシーケンスＩＤのレジスタのサイズを示す。N. A. Touba and E. J. McCluskey. Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), in Proceedings IEEE International Test Conference, pages 167-175, 1996、及びM. Karkala, N A. Touba, and H.-J. Wunderlich, Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test Symposium, 1998を参照。ビット固定シーケンス生成論理のもう一方の入力は、本発明のＢＩＳＴの  スキャンカウンタ（図７参照）に対応するＭｏｄ−（ｍ＋１）カウンタによって駆動される。ビット固定シーケンス生成論理は、本発明のＢＩＳＴにおけるオーバーライド信号を生成するデコーダに対応する。この論理は、無用な疑似ランダム・シーケンスを決定用テストキューブに変換するための制御信号を生成する。「Ｌｉｔ．カウント」のカラムは、多層ビット固定シーケンス生成論理のリテラル数を示す。Ｔｏｕｂａ’９６及びKarkala et alで発表された結果は、すべてのケースで１０，０００個のテストパターンを適用することによって得られる。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference, pages 167-175, 1996、及びM. Karkala, N A. Touba, and H.-J. Wunderlich. Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test Symposium, 1998を参照。
【０１４９】
【表４】
2004301856.tif 000019
Ｈ．−Ｊ．Ｗｕｎｄｅｒｌｉｃｈの「Ｈａｒｄ  Ｆａｕｌｔ」のラベルが付けられたカラムは、１０，０００個の疑似ランダム・パターンを適用した後にも未検出のまま残る非冗長故障数を示す。H.-J. Wunderlich and G. Kiefer. Bit-Flipping BIST(ビットフリップBIST). In Proceedings VLSI Testing Symposium, pages 337-343, 1996を参照。「Ｐｒｏｄ．  Ｔｅｒｍ」のラベルが付けられたカラムは、ビットフリップ関数を実装するために必要とされた積項数を示す。これは、本発明のＢＩＳＴにおけるビット固定シーケンス生成論理とデコーダに対応する。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference, pages 167-175, 1996、及びM. Karkala, N A. Touba, and H.-J. Wunderlich. Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In Proceedings 7γrd Asian Test Symposium, 1998を参照。ベンチマーク回路のためのビットフリップ関数はいずれも、１０，０００個のパターンが適用されたときに１００％の故障適用範囲を達成するように設計されている。いずれのケースについても、疑似ランダム・シーケンスは３２段のＬＦＳＲを使用して生成される。Ｈ．−Ｊ．Ｗｕｎｄｅｒｌｉｃｈでは、１０，０００個のパターンが適用された後も未検出のまま残る困難な故障についてのみ考慮していることに注意されたい。H.-J. Wunderlich and G. Kiefer. Bit-Flipping BIST(ビットフリップBIST). In Proceedings VLSI Testing Symposium, pages 337-343, 1996を参照。従って、容易な故障を検出するために適用される１０，０００個のパターンを含めると、各回路に適用される全テストパターンは２０，０００個である。
【０１５０】
本発明のＢＩＳＴでは、デコーダを実装するために必要とされる積項数及びリテラル数のいずれも報告されている。もし、本発明のＢＩＳＴで生成されるシーケンスが他のＢＩＳＴで生成されるシーケンスよりも短かかったとしても、本発明のＢＩＳＴの実装に伴うハードウェア・オーバーヘッドはｓ１１９６を除くすべての回路で最も低レベルである。(N. A. Touba and E. 3. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(走査方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference, pages 167-175, 1996; and M. Karkala, N A. Touba、及びH. -J. Wunderlich. Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test Symposium, 1998の場合は10，000パターン、H.-J. Wunderlich and G. Kiefer. Bit-Flipping BIST(ビットフリップBIST), In Proceedings VLSI Testing Symposium, pages 337-343, 1996の場合は20，000パターン)。
【０１５１】
本発明のＢＩＳＴのカウンタに対応するシーケンスＩＤのレジスタのサイズは、すべての回路について本発明によるＢＩＳＴのカウンタのサイズを上回っている。N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST(スキャン方式BISTのための疑似ランダム・ビット・シーケンスの改変), In Proceedings IEEE International Test Conference, pages 167-175, 1996、及びM. Karkala, N A. Touba, and H.-J. Wunderlich. Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST(低オーバーヘッド混合モードBIST用のテストパターンを相関するための専用ATPG), In proceedings 7γrd Asian Test Symposium, 1998を参照。特に、ｃ７５５２やｃ２６７０のように多数の故障を含む大規模な回路では、本発明のＢＩＳＴの実装に伴うハードウェア・オーバーヘッドは他のＢＩＳＴのそれよりも大幅に少ない。
【０１５２】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【図面の簡単な説明】
【０１５３】
【図１】テストキューブの例を示す。
【図２】生成器、及び5入力を有する回路のオーバーライド信号を示す。
【図３】図１、図２に対応するｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴのための３重みＷＲＰＴ回路の実装を示す。
【図４】本発明の改良型ＡＴＰＧ手法を説明するフローチャートを示す。
【図５】マージされたオーバーライド信号を有するｔｅｓｔ−ｐｅｒ−ｃｌｏｃｋ  ＢＩＳＴ実装を示す。
【図６】３重みＷＲＰＴを有する本発明の並列タイプスキャン方式ビルトイン・セルフテスト回路の好適な実施例を示す。
【図７】３重みＷＲＰＴを有する本発明の逐次タイプスキャン方式ビルトイン・セルフテスト回路の好適な実施例を示す。
【図８】トグルを使用した最小項数の最小化を示す。
【図９】トグルを使用した最小項数の最小化を示す。
【図１０】トグルを使用した最小項数の最小化を示す。
【図１１】トグル・フリップフロップを有する逐次タイプスキャン方式ビルトイン・セルフテスト回路を示す。
【符号の説明】
【０１５４】
３．１０  デコーダ
３．２０  カウンタ
３．３０  イネーブル信号
３．４０  ＣＵＴ
５．１０  デコーダ
５．２０  カウンタ
５．３０  イネーブル信号
５．４０  ＣＵＴ
６．１０  デコーダ
６．２０  ＬＦＳＲ
６．３０  カウンタ
６．４０  ２入力ＡＮＤゲート
６．６０  スキャン要素
６．６１  スキャン要素
６．６２  スキャン要素
６．６３  スキャン要素
６．５０  ＣＵＴ
７．１０  ＬＦＳＲ
７．２０  ＯＲゲート
７．３０  ＡＮＤゲート
７．４０  デコーダ
７．５０  カウンタ
７．６０  スキャンカウンタ
７．７０  スキャン回路
９．１０  トグル・フリップフロップＴＦ１
９．２０  トグル・フリップフロップＴＦ０
９．３０  デコーダ
９．４０  ＯＲゲート
９．５０  ＡＮＤゲート
９．６０  カウンタ
９．７０  スキャンカウンタ
【図１】
2004301856.tif 000020
【図２】
2004301856.tif 000021
【図３】
2004301856.tif 000022
【図４】
2004301856.tif 000023
【図５】
2004301856.tif 000024
【図６】
2004301856.tif 000025
【図７】
2004301856.tif 000026
【図８】
2004301856.tif 000027
【図９】
2004301856.tif 000028
【図１０】
2004301856.tif 000029
【図１１】
2004301856.tif 000030