(57)【要約】ある論理製品のテストにおいて用いるためのテストベクトルデータを圧縮するための方法と装置が開示される。元のテストベクトルデータが“ケア”ビットと“ドントケア”ビットを含む２つ又はそれ以上のビットのシーケンスの形式にて生成される。このテストベクトルデータは、その後、２つ又はそれ以上の連続するベクトルの対応するビットを比較いし、もしこれら２つ又はそれ以上のベクトルのこれら対応するビットの全てが互換的であることが見つけられたときは、これらを表す単一のベクトルに併合することで、圧縮される。２つのビットの互換性は、これらが指定された非互換的なすなわち反対の値を有さないという条件のもとで達成される。
2006525507.tif 000002
【特許請求の範囲】
【請求項１】
１つのベクトルが少なくとも一つ以上のビットを含む少なくとも２つの連続するベクトルのシーケンスを含むデータを圧縮する方法であって、
i）２つ又はそれ以上の連続するベクトルの対応するビットを比較し、対応するビットが互換的であるか否かを決定するステップと、
これらベクトルの全ての対応するビットが互換的であるときは、
ii）前記２つ又はそれ以上のベクトルを併合し、前記２つ又はそれ以上のベクトルを表す単一のベクトルを形成するステップと、
を含み、
２つのビットの互換性は、前記２つのビットが指定された非互換的なすなわち反対の値を有さないという条件のもとで達成されることを特徴とする方法。
【請求項２】
前記データは、論理製品のテストにおいて用いるためのテストベクトルデータを含み、前記方法は、”ケア（care）”ビットと”ドントケア（don't care）”ビットとを含む元のテストベクトルデータを生成又は得るステップと、これらテストベクトルデータをステップi）とii）とに従って圧縮するステップとを含む請求項１記載の方法。
【請求項３】
前記元のテストベクトルデータは、自動テストパターン生成（ＡＴＰＧ）ツールを用いて生成される請求項２記載の方法。
【請求項４】
１または複数の併合されたベクトルに関して反復値を生成するステップを含み、この反復値は、各々の併合されたベクトルが、その併合されたベクトルが代表しているベクトル内のケアビットを再構成するために反復されるべき回数を示す請求項１乃至３のいずれかに記載の方法。
【請求項５】
論理製品のテストにおいて用いるためのテストベクトルデータを含むデータの組であって、前記テストベクトルデータは請求項４記載の方法によって圧縮されているデータの組。
【請求項６】
論理製品をテストする方法であって、
圧縮されたテストベクトルデータを請求項５に従って生成するステップと、
前記併合されたベクトルをそれらの各々の反復値に従って１回又は複数回反復することで前記テストベクトルデータを再構成するステップと、
前記再構成されたテストベクトルデータを前記論理製品の入力に加えるステップと、
結果として起こる出力データを得るステップと、
を含む方法。
【請求項７】
更に、前記出力データを請求項１乃至４のいずれかの１つに従って圧縮するステップを含む請求項６記載の方法。
【請求項８】
１つのベクトルが少なくとも一つ又はそれ以上のビットを含む少なくとも２つの連続するベクトルのシーケンスを含むデータを圧縮する装置であって、
i）２つ又はそれ以上の連続するベクトルの対応するビットを比較し、対応するビットが互換的であるか否かを決定する手段と、
ii）前記ベクトルの全ての対応するビットが互換的である前記２つ又はそれ以上のベクトルを併合し、前記２つ又はそれ以上のベクトルを表す単一のベクトルを形成する手段と、を含み、
２つのビットの互換性は、前記２つのビットが指定された非互換的なすなわち反対の値を有さないという条件のもとで達成される装置。
【請求項９】
前記データは、論理製品のテストにおいて用いるためのテストベクトルデータを含み、前記装置は、１つのベクトルが、”ケア（care）”ビットと”ドントケア（don't care）”ビットとを含む１つ又は複数のビットを有する２つ又はそれ以上のベクトルのシーケンスを含む元のテストベクトルデータを生成又は受信する手段を含む請求項８記載の装置。
【請求項１０】
論理製品をテストする装置であって、
元のテストベクトルデータを生成する手段と、
前記元のテストベクトルデータを請求項９に従って圧縮する装置と、
前記圧縮されたデータから前記テストデータを再構成する手段と、
前記再構成されたデータを前記論理製品の入力に加える手段と、
結果として起こる出力データを得る手段と、
を含む装置。
【請求項１１】
前記ドントケアビットは、テストベクトルデータがｎより小さなベクトルのシーケンスを含むときにはランダムに充填され、他方、前記ドントケアビットは、テストベクトルデータがｎ以上の互換的なベクトルのシーケンスを含むときには、互換的なベクトルを併合することによって充填される請求項１０記載の装置。
【請求項１２】
前記出力データを圧縮するための請求項８に従う装置を含む請求項１０記載の装置。
【請求項１３】
前記元のテストベクトルデータを生成する手段は、自動テストパターン生成（ＡＴＰＧ）ツールを含む請求項１０乃至１２のいずれかに記載の装置。
【請求項１４】
テストパターンを、その圧縮の前に、並べかえる手段を含む請求項１３記載の装置。
【請求項１５】
併合されたデータシーケンスを、論理製品のテストにおいて用いるためのデータの組の形式にて格納する手段を含む請求項１０記載の装置。
【請求項１６】
請求項１５記載の装置を用いて作成されたデータの組が格納される電子データストレージ手段。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの圧縮に用いる方法と装置に関し、とりわけ、必ずしも排他的にではないが、論理製品、例えば集積回路チップその他のテストにおいて用いるためのテストデータのボリュームを、これら製品をテストするために要求されるコンピュータメモリ、ディスクストレージ及び時間の量を節約するために、低減するための、すなわちこれらテストデータを圧縮するための方法と装置とに関する。
【背景技術】
【０００２】
個々の製造された集積回路（ＩＣ）は、製造欠陥について、それが顧客に出荷される前に、徹底的にテストされなければならない。ＩＣをテストするための従来の方法は、テストパターンをＡＴＰＧ（Automated Test Pattern Generation：自動テストパターン生成）ツールを用いて自動的に生成することと、ＡＴＥ（Automated Testing Equipment：自動化されたテスト装置）と、オン・チップＤｆＴ（design-for-testablity：テストを可能とするための設計）構造とを用いて、これらテストパターンをＩＣに加えることから成る。
【０００３】
デジタル論理回路に対する普通のＤｆＴ技法は、テストモードの際に、回路内のフリップフロップがシリアルシフトレジスタ（“スキャンチェーン”）に構成されることを許す、“スキャンデザイン（scan design）”である。図面の図６を参照しながら説明すると、スキャンテストの際に、テスト刺激が、１つ又は複数のピン２０４を介して、最初に、スキャンチェーン２００内にシフトされる。テスト刺激が全てシフトインされた後に、回路２０８は、１又は複数クロックサイクルだけ、機能（すなわち“通常（normal）”）モードにて動作する。通常モードサイクルの際に、これらフリップフロップ内の刺激が回路内の論理セル２０２に加えられ、これらの応答がこれらフリップフロップ内に捕捉される。これら通常モードサイクルの後に、回路は再びテストモードに構成され、これらフリップフロップ内に捕捉された応答はシフトアウトされる。このプロセスが全てのテスト刺激が加えられるまで反復される。典型的には、新たなテスト刺激のこれらスキャンチェーン内へのシフトインと、前のテスト刺激のテスト応答のシフトアウトとは、実質的に同時的に遂行される。
【０００４】
ＡＴＰＧツールは、あるデジタル論理回路に対するテストパターンを、ある特定の障害モデル（fault model）を考慮しながら生成する。この障害モデルは、ある回路内で起こり得る物理的な欠陥、例えば、短絡回路、（抵抗性）開回路、或いはワイヤ間のブリッジなどをモデル化するために用いられる。例えば、ＡＴＰＧツールによって生成される、各パターンは、こうしてモデル化された障害の幾つかを検出するために用いることができる。あるＡＴＰＧテストパターンセットの障害カバレッジ（ＦＣ（fault coverage））は、それらテストパターンによって検出されたところのモデル化された障害の数と、モデル化された障害の総数との比として定義される。各テストパターンは、あるテスト刺激と、対応するテスト応答とから成る。
【０００５】
ＡＴＰＧツールによって生成されるようなあるテストパターンセットはｐ個のテストパターンから成る。組合せ回路、又はフル・スキャンシーケス回路（full-scan sequential circuits）に対しては、典型的には、組合せ（combinatorial）ＡＴＰＧが用いられ、他方、部分スキャン、又はノン・スキャン（non-scan）シーケンス回路に対しては、典型的には、シーケンシャルＡＴＰＧが用いられる。組合せＡＴＰＧによって生成されたパターンの組については、その組内のパターンの順番はしばしば任意である。シーケンシャルＡＴＰＧについては、ある組内のパターンは、典型的にはグループ化され、これらパターンの順番は各グループ内においては固定される。
【０００６】
概念的には、各テストパターンは、テストベクトルから成り立つ。あるテストベクトルは、典型的には、“０”と“１”の値のシーケンスであり、ＩＣ入力ピンに対する刺激ビット（stimulus bits）と、ＩＣ出力ピンに対する応答ビット（response bits）とを含む。もしあるＩＣがｎ個のピンを有するときは、このＩＣに対するテストベクトルは、ｎ個のビットを、各ピンに対して１ビット、を含むこととなる。あるテストパターンは、典型的には、ｖ個の連続するテストベクトルのシーケンスから成り、これらがＩＣにある特定の順番にて加えられる。
【０００７】
これらテストベクトルは、ＡＴＥベクトルメモリ内に格納される。ＡＴＥは、ベクトルメモリからある特定のテストベクトル内の刺激データを読み出し、これをＩＣピンに加える。ＩＣ出力ピン上のこれら応答は、ＡＴＥによって捕捉され、例えば、ＡＴＥベクトルメモリ内に格納されているところの障害のない応答（fault-free responses）と比較される。ＡＴＥは、各テストベクトルについて、それが合格であるか、不合格であるかを示す能力を有し、そして、不合格の場合は、ＡＴＥは、障害応答（faulty response）を出力した全てのＩＣピンを報告することができる。
【０００８】
現在の傾向は、ますます多くのトランジスタを単一のＩＣに集積化する方向にある。ムーアの法則（Moore's law）によると、この成長は、指数関数的であり、ＩＣ当りのトランジスタの量は、１．５年毎に、約２倍となる。典型的なＩＣのサイズが増加すると、結果として、このようなＩＣをテストするために要求されるテストデータのボリュームもまた増加することを余儀なくされる。さらに、ディープ・サブミクロン（deep sub-micron）ＩＣプロセス技術は、以前のプロセス技術においては発生しなかったような、新たな欠陥タイプを導入する。これら新たな欠陥は、典型的には、回路のタイミング挙動（timing behavior）に影響を及ぼし、追加のテストパターンがこれら欠陥を検出するために必要となる。結果として、テストデータのボリュームは、ＩＣザイズの増加と共に、超直線的（super-linear）に増加しつつある。事実、テストデータのボリュームは、これらはもはや従来のＡＴＥベクトルメモリ内に収まらなくなる程度まで、成長することが予期されている。
【０００９】
この問題に対する以下のような幾つかの可能な解決策が存在する
１．テストデータのボリュームを、ＡＴＥベクトルメモリの容量に制限する。しかし、これは、あるＩＣをテストするために、テストパターンのすべては用いられず、このためテスト品質が低減することを含蓄し、これは、明らかに望ましくない。
２．テストデータのボリュームを複数のテストセットに、各個々のテストセットがＡＴＥベクトルメモリ内に収まるように分割する。しかし、各テストセットを収容するためのＡＴＥベクトルメモリの“再ロード（reloading）”は、あるＩＣに対する総テスト時間を増加させ、これも、望ましくない。
３．ＡＴＥベクトルメモリを拡張する。しかし、ベクトルメモリは高価であり、そしていずれにしても、ＡＴＥアーキテクチャによって、メモリの拡張に対する上限が課される。
４．従来のＡＴＥを、より多くのベクトルメモリを提供する、より新たなＡＴＥにて取りかえる。しかし、これは、非常に高価につく。
【００１０】
上の４つの可能な解決策のいずれも、テストデータのボリュームの増加を扱うためには真に十分ではない。一つの代替の解決策として、テストデータは、ＡＴＥベクトルメモリ内に圧縮された形式にて格納しても良い。このデータは、ＡＴＥ自身の上、チップ上、又はＡＴＥとＩＣとの間の通信路内（例えば、“ロードボード（load board）”上に存在する回路によって伸張（decompressed）される。
【００１１】
近年、多数のテストデータ圧縮技法が提唱されている。殆どのテストデータ圧縮技法は、テストデータの多くの量は、実際には、ランダムデータであるという事実を利用する。各テストパターン内において、ある限られた量の刺激ビット（通常はたった数パーセント）のみが指定されており、すなわち“ケア（care）”ビットであり、他方、殆どの刺激ビットは、“ドントケア（don't care）”であり、このため、ランダムに充填（fill）することができる。原理的には、ＡＴＥ内に格納しなければならないのは、これら指定されている刺激ビットのみであり、この事実は、格納されるべきテストデータのボリュームを圧縮することに対する可能性を提供する。
【００１２】
テストデータを生成している際に、ＡＴＰＧツールは、これらドントケア刺激ビットに対しては、ランダム値を挿入する。このプロセスは、“ランダムパディング（random padding）と呼ばれている。公開されている米国特許出願公開第2002/0099991号明細書及び米国特許出願公開第2002/0099992号明細書に記述される装置においては、ケアビットとドントケアビットの両方を含むテストベクトルが生成される。ドントケアビットは、ある反復値（repeated value）を充填され、結果としてのテストベクトルは、ベクトル反復（vector repeat）を用いて圧縮される。上述のこれら従来技術の文献において提唱されている充填戦略（すなわち、“パディング（padding）”タイプ）は、以下の通りである
a）ドントケアは“反復充填（repeat fill）”を用いて充填するか、又は
b）ドントケアは反復的バックグラウンドデータ（repetitive background data）を用いて充填する。
【００１３】
反復的バックグラウンドデータの使用は、０−充填又は１−充填に対応し、ここでは、ドントケアビットは全て、“０”、又は“１”にて充填される。反復充填は、あるシーケンス内の各ドントケアビットには最近のケアビットと同一の値が与えられることを含意する。
【００１４】
例えば、０ＸＸ１ＸＸなるシーケンスを考慮する。ここで、シンボルＸはドントケアビットを表す。このシーケンスに０−充填を適用すると、結果として、０００１００となる（すなわち、全てのＸは０にて置換される）。これと同一のシーケンスに１−充填を適用すると、結果として、０１１１１１となる。反復充填を適用すると、結果として、０００１１１となる（すなわち、０の後から１の前までのＸには値０が割当てられ、他方、１の後のＸには値１が割当てられる）。
【００１５】
テストベクトルは、殆どのＡＴＥ構成によってサポートされるようなベクトル反復能力（vector repeat capability）を用いて圧縮することもできる。図１Ａは、ある典型的なＡＴＥアーキテクチャを図解する略ブロック図である。これらテストベクトルはＡＴＥベクトルメモリ１００内に格納されるが、他方で、インストラクションメモリ１０２は、これらベクトルをＩＣ１０４にどのように加えるかに関するインストラクションを含む。このインストラクションメモリ１０２は、例えば、ある特定のベクトルを、ある回数のサイクルだけ、加えるためのインストラクションを含んでもよく、これは、”ベクトル反復（vector repeat）”と呼ばれる。これによると、ｖ個の同一のテストベクトルのシーケンスを、ＡＴＥ上に、ＡＴＥベクトルメモリ１００内の単一のベクトルを用いて格納することができ、そして、ＡＴＥインストラクションメモリ１０２内のインストラクションによってこのベクトルをｖ回だけ反復することができるために、テストデータを圧縮することが可能となる。
【００１６】
１つの代替のＡＴＥアーキテクチャが図１Ｂに図解されているが、ここでは、ベクトルメモリ１００とインストラクションメモリ１０２は分散されている。各ベクトルメモリ１００ａ，１００ｂ及びそれと対応するインストラクションメモリ１０２ａ，１０２ｂは、ここでは、データをＩＣピンのサブセットに加えるために用いられる。このようなＩＣピンのサブセットは、ここでは、ピン−グループ又はポートと呼ばれる。図１Ｂは２つのポートしか示さないが、しかし、これは、必要であれば、２つより多くのポートに拡張することもできる。ポート当りのこれらピンの数はポート毎に変えてもよい。幾つかのケースにおいては、各ポートは、ある単一のＩＣピンに対応してもよく、他方、他の幾つかのケースにおいては、ｎ−ピンポートを用いてもよく、ここで、ｎは、１より大きな整数を表す。
【００１７】
各ポートは、自身のベクトルメモリとインストラクションメモリとを有するために、ベクトルデータを、ポート毎に反復することも可能である。
【発明の開示】
【００１８】
我々は、ある改善された構成を発明した。
【００１９】
本発明によると、少なくとも２つの連続するベクトルを含むデータを圧縮する方法が提供されるが、ここで、あるベクトルは、１つ又は複数のビットを含む。この方法は、特徴として、
i）２つの連続するベクトル内の対応するビットを比較し、それらが互換的であるか否かを決定するステップと、もしこれらビットが互換的であるときは、
ii）これらベクトルを併合し、これらを表す単一のベクトルを形成するステップと、を含み、
ここで、２つのビットの互換性は、それらが指定された非互換的な、すなわち、反対の値を有さないという条件の下で達成される。
【００２０】
２つのビットは、もしそれらが別個であることが保証されるときは、非互換的であるといわれる。すなわち、２つのビットｂ１とｂ２とは、もしｂ１≠ｂ２、かつ、ｂ１≠Ｘ、かつ、ｂ２≠Ｘであるときは、非互換的である。
【００２１】
１つの好ましい実施例においては、この方法は、１つ又は複数のベクトルに関して、反復値を生成するステップを含み、この反復値は、対応する併合されたベクトルが、その併合されたベクトルが表す元のベクトルシーケンスを再構成するために反復されるべき回数を表す。
【００２２】
好ましくは、このデータは、ある論理製品のテストにおいて用いるためのテストベクトルデータを含み、この方法は、“ケア（care）”ビットと“ドントケア（don't care）”ビットを含む元のテストベクトルデータを生成するステップと、このテストデータを、上で定義されるステップi）とii）に従って圧縮するステップと、を含む。
【００２３】
この元のテストベクトルデータは、ＡＴＰＧ（自動テストパターン生成）ツールを介して生成してもよい。
【００２４】
本発明は、さらに、ある論理製品のテストにおいて用いるためのテストベクトルデータを含むデータセットにも及ぶが、このテストベクトルデータは、上で定義された方法によって圧縮されている。
【００２５】
さらに、本発明によると、ある論理製品をテストするための方法であって、上で定義されたように圧縮されたテストベクトルデータを生成するステップと、このテストベクトルデータ内のケアビットを、併合されたベクトルを、それに対応する反復値に従って１度又は複数回反復することによって再構成するステップと、この再構成されたテストベクトルデータをこの論理製品の入力に加えるステップと、結果としての出力データを得るステップと、を含む、方法も提供される。理解できるように、これら元のテストベクトル内には、ケアビットと、ドントケアビットとが存在する。圧縮の後は、これらドントケアビットに関して、情報は失われる。このため、ここで用いられる“再構成（reconstructing）”なる用語は、これらベクトル内のケアビットを、すなわち、ドントケアビットなしに、再構成することを意味する。（これらドントケアビットを有する）元のテストベクトルは、このやり方では、再構成することはできない。
【００２６】
上で定義された方法は、さらに、この出力データを上で定義されたようなデータを圧縮する方法に従って圧縮するステップを含んでもよい。
【００２７】
さらに、本発明によると、少なくとも２つの連続するベクトルのシーケンスを含むデータを圧縮するための装置も提供されるが、ここで、あるベクトルは、１つ又は複数のビットを含む。この装置は、特徴として、
i）２つ又はそれ以上の連続するベクトル内の対応するビットを比較し、それらが互換的であるか否かを決定する手段と、
ii）これらベクトルの全ての対応するビットが互換的であるところの前記２つ又はそれ以上のベクトルを併合し、これら２つ又はそれ以上のベクトルを表す単一のベクトルを形成する手段と、を含み、
２つのビットの互換性は、それらが指定された非互換的な、すなわち、反対の、値を有さないという条件の下で達成される。
【００２８】
理解できるように、あるベクトルは、ｎ個のビットを含んでもよく、ここで、ｎは正の整数（すなわち、１又はそれ以上）である。換言すれば、あるベクトルは、１つ又は複数のビットを含んでもよい。
【００２９】
ここでも、このデータは、ある論理製品のテストにおいて用いるためのテストベクトルデータを含んでもよく、この装置は、“ケア（care）”ビットと“ドントケア（don't care）”ビットを含む２つ又はそれ以上のベクトルを含む元のテストベクトルデータを生成又は受信する手段を含む。
【００３０】
さらに、本発明によると、ある論理製品をテストするための装置であって、元のテストベクトルデータを生成するための手段と、この元のテストベクトルデータを上で定義されたように圧縮する装置と、このテストベクトルデータ内のケアビットを再構成する手段と、この再構成されたテストベクトルデータをこの論理製品の入力に加える手段と、結果としての出力データを得る手段と、を含む装置が提供される。
【００３１】
この出力データも、上で定義されたデータ圧縮装置を介して圧縮してもよい。この装置は、さらに、テストパターンを、その圧縮の前に、並べかえる手段を含んでもよい。ここでも、元のテストベクトルデータを生成する手段は、ＡＴＰＧ（自動テストパターン生成）ツールを含んでも良い。
【００３２】
この装置は、併合されたデータシーケンスを、ある論理製品のテストにおいて用いるためのデータセットの形式にて格納するための手段を含んでも良く、さらに、本発明は、このような装置を用いて作成されたデータの組が格納される電子データストレージ手段にも及ぶ。
【００３３】
こうして、要約すると、テストベクトルは、典型的には、多量の“ドントケア（don't care）”ビット（しばしば９０％以上）を含み、これらドントケアビットは、これらベクトルの障害カバレッジに影響を与えることなく修正することができる。これらドントケアビットは、本発明によると、テストベクトルを圧縮し、従って、テストデータのボリュームを低減するために、利用することができる。テストデータのシーケンスを圧縮するためにはラン長符号化（run-length encoding）が採用される。このような圧縮は、平均ラン長が極大にあるとき、最適化にすることができ、この最適化は、本発明によると、“併合充填（merge fill）”を適用することで、達成される。
【００３４】
この併合充填の基本的なアイデアは、これらドントケアビットを、互換的なテストベクトルのシーケンスが形成されるようなやり方にて充填するところにある。互換的なテストベクトルの各シーケンスは、単一のテストベクトルと、これに加えて、好ましくは、１つの反復カウント値（repeat count value）と、に併合することができる。この併合されたテストベクトルと反復カウントの格納は、元のテストベクトルの格納と比較して、より少ないＡＴＥメモリを必要とする。終局的には、この併合充填を用いることで、ラン長符号化が最適化され、従来の技法と比較して、テストデータボリュームのより大きな低減が可能となる。
【００３５】
こうして、本発明の方法は、従来のパディング方法は、ドントケアビットが、ある単一のピンに加えられるビットのみでなく、（ｎ−ピンポートが採用されるようなケースにおけるように）あるポート上の全てのビットに加えられるビットをも考慮してパディングされるという理由で異なる。従来技術の構成は、図１Ａに図解されるような、そこにおいては全てのＩＣピンが単一のＩＣメモリに接続されている、ＡＴＥ構成に対するパディングしか考慮しないが、他方で、本発明は、図１Ｂに示されるようなＡＴＥ構成内においても用いることができる。両方のＡＴＥ構成について、併合充填によると、他のパディングタイプと比較して、はるかに高い反復カウントが可能となり、このため、格納することを要求されるテストデータボリュームを大幅に低減することが可能となる。
【００３６】
これらテストパターンを（以下で説明されるように）並べかえることで追加の自由度を達成することができ、ＡＴＥベクトルメモリ内に格納されるべきテストベクトルの数をさらに低減することが可能となる。
【００３７】
本発明のもう一つの実施例として、これらドントケアビットは、ｎ個より小さなベクトルのシーケンスの場合は、ランダムに充填し、そして、本発明による併合充填は、ｎ個より大きな互換的ベクトルのシーケンス内のドントケアビットを充填するために用いてもよい。
【００３８】
原理上は、テストベクトル内のこれらドントケアビットには、任意の値を割当てることができる。しかし、ドントケアビットの充填は、これらテストベクトルのテスト品質に影響を及ぼす。とりわけ、実際の欠陥（defect）カバレッジ、すなわち、検出される物理的欠陥の数、並びに、診断の解像度、すなわち、ある不合格な回路（failing circuit）内にどのような障害が存在するのかを識別する能力は、ドントケアビットの充填によって影響を受ける。これらドントケアビットがランダムに充填されたテストベクトルは、ドントケアビットが、例えば、０−充填、１−充填、反復充填、又は併合充填におけるように、より規則的な値にて充填されたテストベクトルよりも、より高いテスト品質を有する傾向がある。テスト品質を改善するために、従って、非互換的ベクトル内のドントケアビットは、ランダム値にて充填されることが望ましい。さらに、ある互換的ベクトルのシーケンスが短いとき（つまり、ある値ｎより小さなとき）も、これらベクトル内のドントケアビットは、ランダム値にて充填される。そして、もし、互換的なテストベクトルのシーケンスが大きなとき（つまり、ｎより大きいか又は等しいとき）は、これらベクトル内のドントケアビットを充填するために、併合充填を適用することもできる。結果として、併合充填のみを用いたときと比較してより高いテスト品質が、ラン長符号化、すなわちベクトル反復を用いるときよりテストデータの圧縮は幾らか落ちるという犠牲の下で、達成される。
【００３９】
本発明のこれら及びその他の態様が以下の実施例を用いての詳細な説明から明らかになろう。
【発明を実施するための最良の形態】
【００４０】
併合（merging）の概念について最初に考察される。３−値論理
Ｌ＝｛０，１，Ｘ｝
について考慮する。この表記法を用いると、これは、あるシーケンス内の各ビットは、“０”、“１”、又は“Ｘ”（ドントケア）なる値を持つことができることを含蓄する。理解できるように、従来の技術におけるように、あるドントケアビットは、“０”又は“１”に、任意に設定することができる。
【００４１】
以下の目的に対しては、２つのビットｂ１ｂ２のシーケンスは、もし、そのシーケンスが００、０Ｘ、Ｘ０、１１、１Ｘ、Ｘ１又はＸＸであるときは互換的であるといわれる。そのシーケンスは、もし、それが、１０又は０１であるときは非互換的であるといわれる。これは、ｎ＞２なるビットのシーケンスに対しても拡張することができ、この場合は、このシーケンスは、もし、このシーケンス内のビットの全てが、全て０又はＸ、全て１又はＸ、もしくは全てＸであるときは、互換的であるといわれる。このシーケンスは、もし、これが、０である少なくとも１つのビットと、１である少なくとも１つのビットとを含むときは、非互換的であるといわれる。
【００４２】
本発明のこの実施例によると、２つの互換的なビットは、“merge”演算子（operator）を用いて、以下のように、単一のビットに併合することができる
１．  merge（００）＝merge（０Ｘ）＝merge（Ｘ０）＝０
２．  merge（１１）＝merge（１Ｘ）＝merge（Ｘ１）＝１
３．  merge（ＸＸ）＝Ｘ
４．  merge（０１）とmerge（１０）とは、（これらシーケンスは非互換的であるため）定義されていない。
【００４３】
これは、ｎ＞２なるビットのシーケンスに対しては、以下のように、一般化することができる
１．  merge（｛０，Ｘ｝−）＝０、ここで、｛０，Ｘ｝−は、少なくとも１つの０を有する複数の０とＸのシーケンスを示す。
２．  merge（｛１，Ｘ｝−）＝１、ここで、｛１，Ｘ｝−は、少なくとも１つの１を有する複数の１とＸのシーケンスを示す。
３．  merge（｛Ｘ｝＋）＝Ｘ、ここで、｛Ｘ｝＋は、１つ又は複数のＸのシーケンスを示す。
４．  merge（｛０，１，Ｘ｝−）は定義されない。ここで、｛０，１，Ｘ｝−は、少なくとも１つの０と、少なくとも１つの１と、零個又は複数のＸとを有する、複数の０、１及びＸのシーケンスを示す。
【００４４】
ベクトルｖｉはｎビット（ｖｉ１，．．．．．．．，ｖｉｎ）のシーケンスとして定義することができる。２つのｎ−ビットベクトルｖ１、ｖ２は、全てのｊ（１≦ｊ≦ｎ）に対して、これらビットｖｉｊとｖ２ｊとが互換的である場合には互換的であるといわれる。２つの互換的なベクトルｖ１とｖ２は、新たなベクトルｖｍｅｒｇｅｄに併合することができるが、ここで、ｖｍｅｒｇｅｄ＝（merge（ｖ１１，ｖ２１），．．．，merge（ｖ１ｎ，ｖ２ｎ））である。
【００４５】
あるテストパターンは、ｖ個の連続するテストベクトルのシーケンスから成り、ここでｖは、典型的には、スキャンシフトサイクルと、これに通常モードサイクルを加えた数に等しい。あるテストパターン内のこれらｖ個のベクトルは、固定された順番を有する。
【００４６】
あるテストパターンの組は、ｐ個のテストパターンから成り、この組は、並べられていることも、並べられていないこともある。もしそのテストパターンの組が並べられているときは、これらｐ個のテストパターンの順番は固定されており、このテストパターンの組は、この場合は、固定された順序のｐ・ｖ個のテストベクトルのシーケンスから成る。もし、そのテストパターンの組が並べられていないときは、これは、ｐ・ｖ個のテストベクトルのシーケンスから成り、ここで、各サブシーケンス内のｖ個のベクトルは、固定された順番を有するが、しかし、これらサブシーケンスの順番は、固定されていない。
【００４７】
あるテストベクトルのシーケンスは、連続する互換的なベクトルを併合することで圧縮することができ、結果は、ｋ個の併合されたテストベクトルのシーケンスとなる。これを行うためのアルゴリズムが下に示されている。この圧縮アルゴリズムは、最適であること、すなわち、結果として、併合の後に、可能な限り最も短なシーケンスとなることを、数学的に証明することができる
k=1                           /*  kはmerge-vectorsの数をカウントする*/
vkmerged＝vl                    /*  merge-vector v1mergedはベクトルv1となる */
For (2＜i＜p・v){               /*  全てのp・v個のベクトルに対して反復*/
If compatible(vi,vkmerged)      /*  もしベクトルviとvkmergedとが互換的なら*/
vkmerged  = merge(vi,vkmerged)  /*  これらベクトルを併合する*/
Else{                      /*  もしベクトルviとvkmergedとが非互換的なら*/
k++
vkmerged  =vi                   /*  新たなmerge-vectorを生成する*/
｝
｝
例１
【表１】
2006525507.tif 000003
【００４８】
上の例を参照しながら説明すると、（ａ）は６個のテストベクトルのシーケンスを表し、そして、（ｂ）は上のアルゴリズムを実行したとき生成される併合されたテストベクトルを示す。結果としてのシーケンスは、（ｃ）に示されるような３個の併合されたテストベクトルから成る。（ａ）のテストベクトルの元のシーケンス内の指定されているビットは、（ｃ）の併合されたテストベクトルのシーケンスから、各併合されたベクトルを、（ｄ）によって示されるような回数だけ反復することで再構成することができる。こうして再構成されたベクトルシーケンスが（ｅ）に示されているが、ここでは、（ａ）と異なるところに下線が付されている。見ればわかるように、両方のシーケンスは、同一の指定されたビットを有するが、しかし、幾つかのドントケアビットは、（ｅ）においては既に充填されている。これら併合されたテストベクトル内の残りのドントケアビットは、例えば、（ｆ）に図解されるように、ランダムに充填することができる。
【００４９】
上の例においては、元のテストベクトルシーケンスの格納には、６個のテストベクトルの格納が必要とされる。併合されたテストベクトルシーケンスの格納には、たった３個の併合されたテストベクトルと、これに加えての、各併合されたテストベクトルに対する反復カウント、の格納のみが必要とされる。正味効果として、このベクトルシーケンスを格納するための、テストデータボリュームの大幅に低減される。
【００５０】
順序つけられていないパターンの組（unordred pattern set）については、これらテストパターンを再順序つけられることができるために、追加の自由度が提供される。これらパターンは、あるパターンの最後の併合されたテストベクトルが、それに続くパターンの最初の併合されたテストベクトルと互換的となるように順序つけることが好ましい。もし、このようにした場合は、これら２つの併合されたテストベクトルは、単一の併合されたテストベクトルに併合することができる。
【００５１】
（下の）例２は、２つのテストパターン（カラム（ａ））に言及する。パターン１の最後のベクトル（ｖ３ｍｅｒｇｅｄ）はパターン２の最初のベクトルの最初のベクトル（ｖ４ｍｅｒｇｅｄ）と非互換的であり、このため、パターン２をパターン１の後ろに並べることは好ましくない。パターン２の最後のベクトル（ｖ６ｍｅｒｇｅｄ）はパターン１の最初のベクトル（ｖ１ｍｅｒｇｅｄ）と互換的であり、このため、パターン２をパターン１の前に並べることが好ましい。テストパターンを並べ替えた後の、結果としての併合されたベクトルのシーケンスが、それらの反復カウントとともに、カラム（ｂ）によって図解されている。
例２
【表２】
2006525507.tif 000004
【００５２】
従って、パターンを並べ替えるための上の手続は最適であること、すなわち、結果として、可能な限り最も短かな、併合されたテストベクトルのシーケンスが得られることがわかる。
【００５３】
このテストベクトルの併合とテストパターンの並べ替えは、ＡＴＰＧ手続内に統合化することができる。ドントケア刺激ビットは、ここでは、併合することができる、互換的なテストベクトルが形成されるように充填されている。
【００５４】
２つの可能なＡＴＰＧフローが、それぞれ、図２Ａと図２Ｂとに示されている。図２Ａにおいては、併合充填が、各個々のテストパターンに対して、そのパターンが生成された後ただちに行なわれる。このアプローチの長所は、障害シミュレーションの際に、パディングされた刺激ビットが考慮され、従って、これら刺激ビットに起因して検出される障害が、検出された障害としてマークされることである。図２Ｂにおいては、併合充填は全てのパターンが生成された後に行なわれる。障害シミュレーションはこれらパターンに関して、パディングされずに遂行されるために、テストパターンの数は、図２Ａのフローに対するそれよりも少し大きくなる。図２Ｂのフローの長所は、幾分か、より柔軟であることである。両方のフローにおいて、パターンの並べ替えとベクトルの併合、及び最終的な障害シミュレーションはオプションである。
【００５５】
ベクトルの併合は、サイズｎを有するベクトルの任意のシーケンスに対して行うことができる。原理的には、ｔ個のピンを有する回路に対しては、全てのテストベクトルは、サイズｔを有し、従って、ｎ＝ｔとなる。また、各ｔ−ビットベクトルｖｉを複数のサブセットのベクトルｖｉ１，．．．，ｖｉｍに分割することも可能である。各サブベクトルｖｉｊは、サイズｓ（ｖｉｊ）を有するが、ここで、１＜ｓ（ｖｉｊ）＜ｔ、そして、Σi<j<mｓ（ｖｉｊ）＝ｔである。あるサブベクトルは、ＩＣピンのあるセットに対する刺激ビットに対応する。このようなピンのセットは、通常は、”ピン・グループ（pin-group）”又は”ポート（ｐｏｒｔ）”と呼ばれる。
【００５６】
テストデータのボリュームの低減は、現在のＡＴＥによってサポートされるベクトル反復機能（vector-repeat capability）によって達成される。幾つかのＡＴＥ上では、ベクトル反復は、全てのピンに対してのみ可能である。つまり、たった１つのピンポートしか存在せず、これが全てのＩＣピンを含み、このため、単一のベクトルシーケンスしか存在しない。他のＡＴＥ上では、ベクトル反復は、ピンのグループ毎に可能である。つまり、複数のポートが存在し、ここでは、各ポートは、ＩＣピンの幾つかのサブセットを含み、そして、存在するポートと同数のサブベクトルのシーケンスが存在する。極端なケースにおいては、各ポートが単一のピンを含んだり、単一のポートが全てのピンを含んだりすることもある。他の構成においては、ポート当りのピンの数は、１とＩＣピンの数との間で変動する。
【００５７】
（下の）例３においては、サブベクトルの第一のシーケンスｖｉ１はポート１上に加えられ、サブベクトルの第二のシーケンスｖｉ２はポート２上に加えられる。テストベクトルを併合するための上のアルゴリズムは、ここでは、２度実行される。つまり、一度はサブベクトルの第一のシーケンスｖｉ１に関して実行され、そして、サブベクトルの第二のシーケンスｖｉ２に関して独立的に実行される。これらの結果がカラム（ｂ）と（ｃ）内に示されている。これら併合されたサブベクトルのシーケンスは、カラム（ｄ）と（ｅ）に示されるように圧縮することができる。各ポートに対して、併合されたサブベクトルと、各サブベクトルが反復される回数が、示されている。ポート２上のシーケンスは、単一のベクトル“１０”によって表され、これが６度反復される。
例３
【表３】
2006525507.tif 000005
【００５８】
上で提唱された基本的なアイデアは、併合充填を、ＡＴＰＧパディング戦略として用いることである。この併合充填の使用は最適な結果を与えること、すなわち、結果として、互換的なベクトルの可能な限り最も長いシーケンス、従って、最も長い反復カウントが得られることを数学的に証明することができる。分析、並びに、シミュレーション結果は、以下を示す。
【００５９】
ピン毎の反復（repeat-per-pin）の場合は（つまり、あるポートが単一のピンを含む場合は）、併合充填（merge fill）は、反復充填（repeat fill）と、同じである。こうして、この場合は、併合充填と反復充填は、両方とも、最適な性能を示し、そして、併合充填又は反復充填を用いたときの平均反復カウントは、他のパディング戦略、例えば、ランダム充填、零充填、又は１充填を用いて得られる平均反復カウントよりも高くなることが証明される。ポート毎の充填（repeat-per-port）の場合は（つまり、あるポートが１つより多くのピンを含む場合は）、併合充填を用いたときの平均反復カウントが最適であり、反復充填又は他のパディングタイプを用いたときの平均反復カウントよりも、かなり大きくなることが証明される。
【００６０】
数学的分析は、ｎビットのポートの場合、平均反復カウントは、
【数１】
2006525507.tif 000006
なる形式であることを示す。ここで、ｐ・ｑは、ある刺激ビットが０である確率であり、ｐ（１−ｑ）は、ある刺激ビットが１である確率であり、１−ｐは、ある刺激ビットがＸである確率である。ｃｎ（ｑ）は、ｎとｑとに依存するある定数である。例えば、もしｎ＝１であるときは、併合充填を用いたときの平均反復カウントは
【数２】
2006525507.tif 000007
となる。そして、もしｎ＝２であるときは、
【数３】
2006525507.tif 000008
となる。
【００６１】
例えば、ｑ＝１／３、ｐ＝０．００３のときは、Ｅ１＝７５０、Ｅ２＝４８３となる。これら結果は、ランダムなテストベクトルを用いたときのシミュレーション結果と対応し、この結果は、それぞれ、７４４と、４８５とを示す。
【００６２】
ランダムなテストベクトルを用いたときのシミュレーションの結果が図３に示されている。この図面は、様々なパディングタイプに対する平均反復カウントを、ポート当りのピンの数を変えながら示す。この図面は、ｎ＝１の場合は（つまりピン毎の反復の場合は）、併合充填と反復充填とは、同程度の性能を有することを示す。ｎ＞１の場合は（つまりポート毎の反復の場合は）、併合充填の性能の方が明らかに反復充填及び他のパディングタイプよりも優れる。
【００６３】
図４は、併合充填を用いたときの平均反復カウントをｐの様々な値に対して示す。この図は、ｐが増加すると、平均反復カウントは減少することを示す。これは、ｐを増加することは、ドントケア刺激ビットの量が低減することを含蓄し、このため、これらドントケアを上手に充填することにより反復カウントを最適化する余地が少なくなるために、予期されることである。図３及び図４は、両方とも、平均反復カウントはポート当りのピンの数を増加させたときも低減することを示す。これも、ポート当りより多くのピンを有すると、互換的なベクトルを有する確率が低下するために、予期されることである。
【００６４】
図５は、併合充填と反復充填とを用いて得られる平均反復カウントの比を、ポート当りのピンの数と、確率ｐとを変化させながら示す。例えば、ｐ・ｑ＝０．０１のときは、併合充填を用いたときの平均反復カウントは、反復充填を用いたときよりも最大で６倍大きくなる。
【００６５】
例
ベクトル反復の以下の例は、米国特許出願公開第２００２／００９９９２号明細書から取られたものである。以下の９ビット幅の１５個のベクトルについて考慮する。（各カラムはあるベクトルに対応し、これらベクトルは右から左へと並べられている。“−”なるシンボルは、そのビットはドントケアであることを示す）。これら１５個のベクトルを格納するためには、１５×９＝１３５ビットが必要となる
【数４】
2006525507.tif 000009
【００６６】
以下のベクトルは、米国特許出願公開第２００２／００９９９２号明細書において提唱されているようなやり方にて、当初のドントケアビットに対して、反復充填と、零充填を、適用したときに得られる。（これらベクトルはここでも右から左へと並べられている）。
【数５】
2006525507.tif 000010
【００６７】
ここでは、（太字にて示されている）５ベクトルを、２（ベクトル１−２）、３（ベクトル３−５）、２（ベクトル６−７）、２（ベクトル８−９）、及び６（ベクトル１０−１５）なる反復カウントと共に、格納することのみが必要とされる。これは、メモリの５ｘ９＝４５ビットと、これに加えての、５個の反復カウント値を必要とするが、これは、結果として、（１３５−４５）／１３５＝６７％なる低減となる。
【００６８】
以下のベクトルは、本発明によって提唱されるようなやり方にて、併合充填を適用したときに得られる（これらベクトルはここでも右から左へと並べられている）。
【数６】
2006525507.tif 000011
【００６９】
ここでは、（太字にて示されている）たった３個のベクトル、２（ベクトル１−２）、５（ベクトル３−７）、及び８（ベクトル８−１５）なる反復カウントと共に、格納することのみが必要とされる。これは、３×９＝２７ビットと、これに加えての、３個の反復カウント値のみを必要とし、結果として、（１３５−２７）／１３５＝８０％なる低減となる。
【００７０】
こうして、本発明は、テストデータのボリュームを低減するために、ＡＴＰＧパディングにおける併合充填を提唱する。テストベクトルは、典型的には、多量のドントケアビット（しばしば９０％以上）を含み、これらドントケアビットは、これらベクトルの障害カバレッジに影響を及ぼすことなく修正することができる。併合充填の基本的アイデアは、これらドントケアビットを互換的なテストベクトルのシーケンスが形成されるようなやり方にて充填することである。互換的なベクトルは単一のテストベクトルとこれに加えての反復カウント値に併合することができる。我々の圧縮はテストベクトルのシーケンスのラン長符号化に対応する。併合充填を用いると、結果として、最適ラン長符号が、可能な限り最も長いラン長が達成されるという意味において、得られることを証明することができる。
【００７１】
併合されたテストベクトルと反復カウントを格納するためには、元のテストベクトルを格納することと比較して、より少ないＡＴＥメモリが必要とされる。併合充填が最適であり、全ての従来のパディングタイプよりも性能が優れる。
【００７２】
この明細書においては、併合充填なる概念は、そこでは、各テストベクトルはポート当り１つのサブベクトルとしての、複数のサブベクトルに分割される、ポート毎の反復まで拡張された。各ポートに対して、併合充填は、独立的に適用することができる。我々は、さらに、併合されたテストベクトルの量をさらに低減するために、テストパターンを並べ替えることができるという追加の自由度を利用した。
【００７３】
本発明は、上で言及されたような増加するテストデータボリュームを扱うための効率的かつ効果的な解決手段を提供する。本発明を適用によって、テスト品質、テスト時間、及びテストコストに悪影響が及ぶことは回避される。
【００７４】
上では本発明の実施例が単に例示として説明されたが、当業者においては明らかなように、説明された実施例に対する修正とバリエーションが、添付のクレームに定義される本発明の範囲から逸脱することなく可能である。さらに、理解できるように、“含む（comprising）”なる単語は、他の要素又はステップを排除することを意図するものではなく、“ａ”又は“ａｎ”なる冠詞は複数性を排除することを意図するものではなく、さらに、単一のプロセッサ、又は他のユニットによって、これらクレーム内に列挙される複数の手段の機能を満足させても良い。
【図面の簡単な説明】
【００７５】
【図１Ａ】本発明の１つの実施例によるＡＴＥアーキテクチャを図解する略ブロック図である。
【図１Ｂ】本発明のもう１つの実施例によるＡＴＥアーキテクチャを図解する略ブロック図である。
【図２Ａ】本発明の１つの実施例によるＡＴＰＧ手続きを図解する流れ図である。
【図２Ｂ】本発明のもう１つの実施例によるＡＴＰＧ手続きを図解する流れ図である。
【図３】様々なパディングタイプに対する平均反復カウントを、ポート当りのピンの数を変えながら図解する（すなわち、併合充填と他のパディングタイプとの比較を図解する）グラフである。
【図４】併合充填内の平均反復カウントを、確率ｐを変化させて、図解するグラフである。
【図５】併合充填と反復充填によって得られる平均反復カウントの比を、ポート当りのピンの数と、確率ｐとを変化させながら図解する（すなわち、併合充填と反復充填との比較を図解する）グラフである。
【図６】フリップフロップと組合せ論理とを有し、これらフリップフロップはスキャンチェーンに構成することができるところのＩＣを図解する略図である。
【図１Ａ】
2006525507.tif 000012
【図１Ｂ】
2006525507.tif 000013
【図２Ａ】
2006525507.tif 000014
【図２Ｂ】
2006525507.tif 000015
【図３】
2006525507.tif 000016
【図４】
2006525507.tif 000017
【図５】
2006525507.tif 000018
【図６】
2006525507.tif 000019
【国際調査報告】
2006525507.tif 000020
2006525507.tif 000021