(57)【特許請求の範囲】
【請求項１】
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに対する複数のテストプランを生成し、
生成された複数のテストプランを圧縮可能なスキューのもとで圧縮して圧縮テストプランを生成するステップを具備する集積回路のテストのための圧縮テストプランの生成方法。
【請求項２】
前記テストプラン圧縮ステップは、
（ａ）テストプランの集合の中から１つの第１のテストプランを選択して取り出し、
（ｂ）サブステップ（ａ）の後において、テストプランの集合の中からさらに０個以上の第２のテストプランを選択して取り出し、
（ｃ）第１および第２のテストプランを圧縮して部分圧縮テストプランを生成し、
（ｄ）テストプランの集合が空集合になるまでサブステップ（ａ）〜（ｃ）を繰り返し、
（ｅ）部分圧縮テストプランの数が１になるまで、生成された部分圧縮テストプランの集合を新たなテストプランの集合としてサブステップ（ａ）〜（ｄ）を繰り返すサブステップを含む請求項１記載の方法。
【請求項３】
前記テストプラン圧縮ステップは、
（ｆ）初期条件を変えてサブステップ（ａ）〜（ｅ）を所定回数繰り返し、
（ｇ）サブステップ（ｆ）における各繰り返しにより得られた各圧縮テストプランの中で長さが最小のものを採用するサブステップをさらに含む請求項２記載の方法。
【請求項４】
前記テストプラン圧縮ステップは、
（ａ）複数のテストプランの中から、圧縮後に長さが最小となる部分圧縮テストプランを与えるテストプランのペアを選択し、
（ｂ）選択されたテストプランのペアを圧縮して部分圧縮テストプランを生成し、
（ｃ）残りのテストプランの中から、該部分圧縮テストプランとの間で圧縮したときに長さが最小となる部分圧縮テストプランを与えるテストプランを選択し、
（ｄ）選択されたテストプランと部分圧縮テストプランを圧縮して部分圧縮テストプランを生成し、
（ｅ）残りのテストプランがなくなるまでサブステップ（ｃ）〜（ｄ）を繰り返すサブステップを含む請求項１記載の方法。
【請求項５】
前記テストプラン生成ステップにおいて、ＲＴＬデータパス回路に含まれるセレクタ以外の回路要素についてテストプランが生成される請求項１〜４のいずれか１項記載の方法。
【請求項６】
前記複数のテストプランを各回路要素に必要な推定テストパターン数に応じて複数のグループにグループ化するステップをさらに具備し、
前記テストプラン圧縮ステップにおいて、各グループごとにテストプランを圧縮することにより、各グループごとに圧縮テストプランが生成される請求項１〜５のいずれか１項記載の方法。
【請求項７】
請求項１〜６のいずれか１項に記載の方法により、圧縮テストプランを生成し、
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに必要な数のテストパターンを生成し、
該圧縮テストプランにテストパターンを代入してテスト系列を生成するステップを具備する集積回路のテストのためのテスト系列の生成方法。
【請求項８】
請求項７記載の方法により生成されたテスト系列をデータパス回路に順次与えるステップを具備する集積回路のテスト方法。
【請求項９】
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれについて、テストプランを各回路要素に必要なテストパターン数だけ生成し、
生成されたテストプランを圧縮可能なスキューのもとで圧縮して圧縮テストを生成し、
該圧縮テストに、各回路要素に必要なテストパターンを代入してテスト系列を生成するステップを具備する集積回路のテストのためのテスト系列の生成方法。
【請求項１０】
ＲＴＬ回路に含まれる第１の回路ブロックのＲＴＬデータパスに含まれる複数の回路要素のそれぞれに対する第１の複数のテストプランを生成し、
該ＲＴＬ回路に含まれる第２の回路ブロックのＲＴＬデータパスに含まれる複数の回路要素のそれぞれに対する第２の複数のテストプランを生成し、
第１および第２の複数のテストプランを圧縮可能なスキューのもとで圧縮して１つの圧縮テストプランを生成するステップを具備する集積回路のテストのための圧縮テストプランの生成方法。
【請求項１１】
請求項１０記載の方法により圧縮テストプランを生成し、
前記第１および第２の回路ブロックに含まれる回路要素のそれぞれに必要な数のテストパターンを生成し、
該圧縮テストプランにテストパターンを代入してテスト系列を生成し、
該テスト系列をデータパス回路に順次与えるステップを具備する集積回路のテスト方法。
【請求項１２】
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに対する複数のテストプランを生成する手段と、
生成された複数のテストプランを圧縮可能なスキューのもとで圧縮して圧縮テストプランを生成する手段とを具備する集積回路のテストのための圧縮テストプランの生成装置。
【請求項１３】
前記テストプラン圧縮手段は、
テストプランの集合の中から１つの第１のテストプランを選択して取り出す第１の手段と、
第１のテストプラン取り出し手段によるテストプランの取り出しの後において、テストプランの集合の中からさらに０個以上の第２のテストプランを選択して取り出す第２の手段と、
第１および第２のテストプランを圧縮して部分圧縮テストプランを生成する手段と、
テストプランの集合が空集合になるまで第１および第２のテストプラン取り出し手段および部分圧縮テストプラン生成手段の処理を繰り返す第１の手段と
部分圧縮テストプランの数が１になるまで、生成された部分圧縮テストプランの集合を新たなテストプランの集合として第１および第２のテストプラン取り出し手段、部分圧縮テストプラン生成手段、および第１の繰り返し手段の処理を繰り返す第２の手段とを含む請求項１２記載の装置。
【請求項１４】
前記テストプラン圧縮手段は、
初期条件を変えて前記第１および第２のテストプラン取り出し手段、部分圧縮テストプラン生成手段、および第１および第２の繰り返し手段の処理を所定回数繰り返す第３の手段と、
第３の繰り返し手段による各繰り返しにより得られた各圧縮テストプランの中で長さが最小ものを採用する手段をさらに含む請求項１３記載の装置。
【請求項１５】
前記テストプラン圧縮手段は、
複数のテストプランの中から、圧縮後に長さが最小となる部分圧縮テストプランを与えるテストプランのペアを選択する第１の手段と、
選択されたテストプランのペアを圧縮して部分圧縮テストプランを生成する第１の手段と、
残りのテストプランの中から、該部分圧縮テストプランとの間で圧縮したときに長さが最小となる部分圧縮テストプランを与えるテストプランを選択する第２の手段と、
選択されたテストプランと部分圧縮テストプランを圧縮して部分圧縮テストプランを生成する第２の手段と、
残りのテストプランがなくなるまで第２の選択手段と第２の生成手段の処理を繰り返す手段を含む請求項１２記載の装置。
【請求項１６】
前記テストプラン生成手段は、ＲＴＬデータパス回路に含まれるセレクタ以外の回路要素についてテストプランを生成する請求項１２〜１５のいずれか１項記載の装置。
【請求項１７】
前記複数のテストプランを各回路要素に必要な推定テストパターン数に応じて複数のグループにグループ化する手段をさらに具備し、
前記テストプラン圧縮手段は、各グループごとにテストプランを圧縮することにより、各グループごとに圧縮テストプランを生成する請求項１２〜１６のいずれか１項記載の装置。
【請求項１８】
請求項１〜６のいずれか１項に記載の方法により、圧縮テストプランを生成する手段と、
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに必要な数のテストパターンを生成する手段と、
該圧縮テストプランにテストパターンを代入してテスト系列を生成する手段とを具備する集積回路のテストのためのテスト系列の生成装置。
【請求項１９】
テストの対象となるデータパス回路と、請求項７記載の方法により生成されたテスト系列を該データパス回路に順次与えるテストコントローラとを具備する、テスト機能を備えた集積回路。
【請求項２０】
ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれについて、テストプランを各回路要素に必要なテストパターン数だけ生成する手段と、
生成されたテストプランを圧縮可能なスキューのもとで圧縮して圧縮テストを生成する手段と、
該圧縮テストに、各回路要素に必要なテストパターンを代入してテスト系列を生成する手段とを具備する集積回路のテストのためのテスト系列の生成装置。
【請求項２１】
ＲＴＬ回路に含まれる第１の回路ブロックのＲＴＬデータパスに含まれる複数の回路要素のそれぞれに対する第１の複数のテストプランを生成する手段と、
該ＲＴＬ回路に含まれる第２の回路ブロックのＲＴＬデータパスに含まれる複数の回路要素のそれぞれに対する第２の複数のテストプランを生成する手段と、
第１および第２の複数のテストプランを圧縮可能なスキューのもとで圧縮して１つの圧縮テストプランを生成する手段とを具備する集積回路のテストのための圧縮テストプランの生成装置。
【請求項２２】
テストの対象となるデータパス回路と、
請求項１０記載の方法により圧縮テストプランを生成し前記第１および第２の回路ブロックに含まれる回路要素のそれぞれに必要な数のテストパターンを生成し該圧縮テストプランにテストパターンを代入して得られたテスト系列をデータパス回路に順次与えるテストコントローラとを具備するテスト機能を備えた集積回路。
【請求項２３】
請求項１〜７，９および１０のいずれか１項に記載の方法をコンピュータに実行させるためのプログラムを記憶した記憶媒体。
【請求項２４】
請求項１〜７，９および１０のいずれか１項に記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、集積回路のテストのための圧縮テストプランの生成方法、テスト系列の生成方法、テスト方法、それらの方法を実現する装置、およびそれらの方法を実現するプログラムに関する。
【０００２】
【従来の技術】
近年、ＬＳＩに搭載される回路規模の増大により、ＬＳＩのテストがますます重要になり、ＬＳＩのテスト設計の自動化は必要不可欠である。ＬＳＩのテスト設計の自動化のためには、高い故障検出効率の達成が必要であり、そのためにテスト容易化設計（ＤＦＴ）が必要である。スキャン設計はＬＳＩのテスト容易化設計として、最も普及している技術であるが、以下の問題点がある。
【０００３】
（１）論理合成後の回路を変更するので、タイミング等の合成時の制約を損なう。
【０００４】
（２）テスト系列長が長い。
【０００５】
（３）実動作速度テストができない。
【０００６】
上記の問題点を解決するために、論理合成前のＲＴＬ設計回路を対象としたＤＦＴが提案されている。ここで、ＲＴＬ設計回路は、データを処理するデータパスとデータパスの動作を制御するコントローラという２つの部分回路で構成されているのが一般的である。データパスからコントローラへの信号をステータス信号、コントローラからデータパスへの信号を制御信号と呼ぶが、本明細書では、ＲＴＬデータパス回路を主として対象とする。まずＲＴＬ回路に対してＤＦＴを行うことで、論理合成後の回路へのＤＦＴが不要となるため、問題点（１）は解決される。問題点（２）、（３）を解決する目的で、データパスが通常使用するデータ転送経路を通じて、対象とする回路要素の入力に外部入力からテストパターンを伝搬し、回路要素の出力応答を外部出力まで伝搬するＤＦＴとして強可検査ＤＦＴ方法（和田ほか、“完全故障検出効率を保証するデータパスの非スキャンテスト容易化設計法”、信学論、Ｊ８２−Ｄ−Ｉ、ｐｐ．８４３−８５１，１９９９年７月）が提案されている。
【０００７】
この文献によれば、すべての回路要素に対して、１）外部入力から任意の値を入力端子に伝搬可能（強可制御性）かつ、２）出力端子の取り得る任意の値が外部出力まで伝搬可能（強可観測性）ならば、データパス回路は強可検査性であるという。そして、データパス回路が強可検査性ならば、全回路要素に対してテストプランが存在することから、各回路要素ごとに完全故障検出効率をもつテストパターン集合を用いることで完全故障検出効率を実現する階層テストが可能となる。なおここで、回路要素には組み合わせモジュールとレジスタが含まれ、組み合わせモジュールが階層テストの対象となることが多い。
【０００８】
この文献では、強可検査性データパス回路中の単一の組合せモジュールに対するテストを順番に実行していくので、回路中の組合せモジュール数をｎ、各組合せモジュールのテストプラン長をＬj(ｊ＝１，２，…，ｎ）、各組合せモジュールのテストパターン数をＮj(ｊ＝１，２，…，ｎ）とすると、強可検査性データパス回路のテスト系列長Ｌは以下の式（１）で表される。
【０００９】
【数１】
0003803283.tif 000002
【００１０】
【発明が解決しようとする課題】
式（１）からわかるように、組合せモジュール数や各組合せモジュールの回路規模が増大すると、強可検査性データパス回路のテスト系列長は急速に増加する。
【００１１】
したがって本発明の目的は、テスト系列全体の長さを短縮することによって、テストのための回路の回路規模を削減し、かつ、テストに要する時間を短縮することにある。
【００１２】
【課題を解決するための手段】
本明細書では、強可検査性のデータパス回路を対象とし、できるだけ多数の組合せモジュールに対するテストを並列に実行することによって、強可検査性データパス回路のテスト系列長を短縮するために、各組合せモジュールのテストプランをスケジューリングして圧縮した、圧縮テストプラン表（または圧縮テストプラン）を用いたテスト生成方法を提案する。また長さが最短の圧縮テストプランを生成するヒューリスティックアルゴリズムを提案する。
【００１３】
本発明の圧縮テストプランの生成方法は、ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに対する複数のテストプランを生成し、生成された複数のテストプランを圧縮して圧縮テストプランを生成するステップを具備することを特徴とする。
【００１４】
前記テストプラン圧縮ステップは、（ａ）テストプランの集合の中から１つの第１のテストプランを選択して取り出し、（ｂ）サブステップ（ａ）の後において、テストプランの集合の中からさらに０個以上の第２のテストプランを選択して取り出し、（ｃ）第１および第２のテストプランを圧縮して部分圧縮テストプランを生成し、（ｄ）テストプランの集合が空集合になるまでザブステップ（ａ）〜（ｃ）を繰り返し、（ｅ）部分圧縮テストプランの数が１になるまで、生成された部分圧縮テストプランの集合を新たなテストプランの集合としてサブステップ（ａ）〜（ｄ）を繰り返すサブステップを含むことが好ましい。
【００１５】
前記テストプラン圧縮ステップは、（ｆ）初期条件を変えてサブステップ（ａ）〜（ｅ）を所定回数繰り返し、（ｇ）サブステップ（ｆ）における各繰り返しにより得られた各圧縮テストプランの中で長さが最小のものを採用するサブステップをさらに含むことが好ましい。
【００１６】
前記テストプラン圧縮ステップはまた、（ａ）複数のテストプランの中から、圧縮後に長さが最小となる部分圧縮テストプランを与えるテストプランのペアを選択し、（ｂ）選択されたテストプランのペアを圧縮して部分圧縮テストプランを生成し、（ｃ）残りのテストプランの中から、該部分圧縮テストプランとの間で圧縮したときに長さが最小となる部分圧縮テストプランを与えるテストプランを選択し、（ｄ）選択されたテストプランと部分圧縮テストプランを圧縮して部分圧縮テストプランを生成し、（ｅ）残りのテストプランがなくなるまでサブステップ（ｃ）〜（ｄ）を繰り返すサブステップを含むことでも良い。
【００１７】
本発明のテスト系列の生成方法は、前述の方法により、圧縮テストプランを生成し、ＲＴＬデータパス回路に含まれる複数の回路要素のそれぞれに必要な数のテストパターンを生成し、該圧縮テストプランにテストパターンを代入してテスト系列を生成するステップを具備することを特徴とする。
【００１８】
本発明のテスト方法は、前述の方法により生成されたテスト系列をデータパス回路に順次与えるステップを具備することを特徴とする。
【００１９】
【発明の実施の形態】
ゲートレベルに変換される前の回路は、図１に示すようにデータを処理するデータパス１００とデータパス１００の動作を制御するコントローラ１０２で構成されデータパス１００はレジスタ転送レベル（以下ＲＴＬ）で記述される。
【００２０】
図２にＲＴＬで記述されたデータパスの一例として、最大公約数（ＧＣＤ）を求める回路のデータパスを示す。図２中、回路要素１，２は外部入力ｘｉｎ，ｙｉｎ、回路要素３は外部出力、回路要素４〜６は比較器、回路要素７は減算器、回路要素８〜１０はレジスタ、回路要素１１〜１４はマルチプレクサ（またはセレクタ）である。ｘｉｎ，ｙｉｎは図１のＰＩに相当し、外部出力はＰＯに、Ｌ１〜Ｌ３およびｍ１〜ｍ４は制御入力（信号線）１０１に、比較器４〜６の出力はステータス信号線１０３に相当する。
【００２１】
図２のデータパス回路は、図３に示すように、回路要素７の右側の入力の値を出力側にスルーさせるためのマルチプレクサを付加することにより強可検査性（またはＤＦＴ済み）になる。このテスト用のマルチプレクサの制御入力をＴ１とする。図３のＤＦＴ済のデータパス回路の各回路要素（組合せモジュールのみ）のテストプランを表１に示す。表１中、ｂは１ビットまたは複数ビットの値を表わし、Ｘはドントケアを表わす。
【００２２】
【表１】
0003803283.tif 000003
【００２３】
ここでテストプランとは、外部入力から特定の回路要素の入力へ値を伝搬し、またその回路要素の出力の値を外部出力まで伝搬するための外部入力の時系列である。回路要素１３のテストプランを例にとると、時刻０において外部入力ｙｉｎにテスト入力値が与えられ、ｍ３が０、Ｌ２が１であるから、その値は回路要素９のレジスタにロードされて、回路要素１３のセレクタの“１”側の入力へ与えられる。時刻１において外部入力ｘｉｎに他のテスト入力値が与えられ、ｍ１が０であるからその値はセレクタ１３の“０”側の入力へ与えられる。そして、セレクタ１３およびその周辺に故障がなければｍ２に与えられる０または１の値に応じてそれらの一方が選択されて出力され、Ｌ１が１であるから回路要素１０のレジスタにロードされる。時刻２においてｍ４が０でありＬ３が１になるからテスト結果が回路要素８のレジスタにロードされて外部へ出力される。
【００２４】
このテストプランは、図４に示すように、ＲＴＬ記述からテスト容易化済ＲＴＬ記述へのテスト容易化（例えば図３に示したセレクタの付加）の際に同時に生成される（ステップ１０００）。図５に示すように、各回路要素について例えば論理合成後のゲートレベル回路の単一縮退故障を検出する各回路要素のテストパターン（テストプランにおけるｂの具体的な値）が生成され（ステップ１００２）、従来技術によれば、各回路要素のテストプランにこのテストパターンを代入することによりデータパス回路のテスト系列が生成される（ステップ１００４）。
【００２５】
本発明では、各回路要素のテストプランにテストパターンを代入する前に複数のテストプランを圧縮して圧縮テストプランを生成し、これにテストパターンを代入することにより、テスト系列を生成する。
【００２６】
表２に示す２つのテストプランを圧縮して圧縮テストプランを生成する場合を例にとって説明する。
【００２７】
【表２】
0003803283.tif 000004
【００２８】
圧縮テストプラン生成のための圧縮演算∩f を表３に示す。
【００２９】
【表３】
0003803283.tif 000005
【００３０】
表３において、演算結果のφは圧縮できないことを示す。
【００３１】
第２のテストプランが第１のテストプランの時刻ｋから始まるように第２のテストプランを第１のテストプランに対してスケジューリングするとき、両者が重なり合う各時刻における入力ごとの圧縮演算結果にφが１つもないとき、第２のテストプランは第１のテストプランにスキューｋで圧縮可能である。表２に示す例では、次式（２）に示すように、表２の（ｂ）のテストプランは、（ａ）のテストプランにスキュー２で圧縮可能であり、その結果、式（２）の右辺に示す圧縮テストプランが生成される。
【００３２】
【数２】
0003803283.tif 000006
【００３３】
すなわち本発明では、図６に示すように、ＲＴＬ記述をテスト容易化して（ステップ１０００）生成されるデータパスの各回路要素のテストプランから圧縮テストプランを生成し（ステップ１００６）、図５における各回路要素のテストプランに代えてこの圧縮テストプランを使用してテスト系列を生成する。
【００３４】
圧縮の順序は通常複数存在するので、その中で、最終的にテストプラン長が最も短い圧縮テストプランを与える順序で圧縮を実行すべきである。しかしながら、テストプランの数が多数になると最短の圧縮テストプランを与える圧縮順序を見い出すことは容易ではない。最短と考えられる圧縮テストプランを与える順序に従ってテストプランの圧縮を行なうための、第１のヒューリスティックアルゴリズムを図７に示す。
【００３５】
図７においてまず、配列ＦＶＡ（ｉ）を生成する（ステップ１１００）、後に詳述するが、ＦＶＡ（ｉ）は、各テストプランの各時刻における要素の集合を基準１（後述）に従ってソートしたものである。ｉ＝０とし（ステップ１１０２）、圧縮前の複数のテストプランの中からの最初の選択のときはＦＶＡ（ｉ）に対応するテストプランを選択し（ステップ１１０６）、そうでない場合は、基準２で１つのテストプランを選択する（ステップ１１０８）。次に、選択されたテストプランとともに圧縮するテストプランを基準３に従って選択し（ステップ１１１０）、選択されたテストプランを圧縮して部分圧縮テストプランを生成する（ステップ１１１２）。
【００３６】
未圧縮のテストプランがなくなるまで（ステップ１１１４）ステップ１１０４〜１１１２の処理を繰り返し、これらの処理が終わったところで生成された部分圧縮テストプランの数が２以上であれば、部分圧縮テストプランの集合をテストプランの集合として（ステップ１１１８）、ステップ１１０４〜１１１６の処理を繰り返す。
【００３７】
部分圧縮テストプランの数が１になったら、ｉをインクリメントし（ステップ１１２０）、ｉがＮでなければ（ステップ１１２２）、ステップ１１０４〜１１２０の処理を繰り返す。
【００３８】
こうして得られたＮ個の圧縮テストプランの中から最短のものを採用する（ステップ１１２４）。
【００３９】
上記のフローにおいて、ステップ１１１６において部分圧縮テストプランの数が永久に１にならない場合がある。このため、ステップ１１１６において部分圧縮テストプランの数が前回の繰り返しの結果と同じである場合には、例外処理として複数の部分圧縮テストプランを連結して圧縮テストプランとしてステップ１１２０の進むものとする。
【００４０】
前述の配列ＦＶＡ（ｉ）と基準１〜３について説明する前に、テストプラン圧縮可能グラフについて説明する。
【００４１】
４つのテストプランＴ1 〜Ｔ4 が表４のように与えられているとき、これに対応して図８に示すテストプラン圧縮可能グラフが生成される。
【００４２】
【表４】
0003803283.tif 000007
【００４３】
テストプラン圧縮可能グラフの各頂点に付されたラベル（ｉ，ｊ）は、テストプランｉの時刻ｊの部分を表わし、頂点（ｉ，ｊ）と頂点（ｋ，ｍ）の間のエッジはテストプランｉに対してテストプランｋがスキューｊ−ｍ（≧０）で圧縮可能であることを意味している。図８の例では、頂点（２，０）と頂点（１，０）の間および頂点（２，１）と頂点（１，１）の間にエッジが存在していることは、テストプランＴ2 に対してテストプランＴ1 がスキュー０で圧縮可能であることに対応している。また、頂点（２，１）と頂点（１，０）の間にもエッジが存在していることは、テストプランＴ2 に対してテストプランＴ1 がスキュー１でも圧縮可能であることに対応している。さらに、頂点（１，２）と頂点（２，０）の間のエッジは、逆にテストプランＴ1 に対してテストプランＴ2 がスキュー２で圧縮可能であることに対応している。
【００４４】
図８の圧縮可能グラフには、例えば頂点（１，０），（２，１），（３，２）からなるクリークが存在しているが、このことは、次式（３）に示すように、テストプランＴ3 に対してテストプランＴ1 およびＴ2 をそれぞれスキュー２および１で圧縮すれば３つのテストプランがすべてに共通の重なり部分を持つ形で圧縮可能であることを意味している。
【００４５】
【数３】
0003803283.tif 000008
【００４６】
本発明の第１のヒューリスティックアルゴリズムでは、圧縮可能グラフから最大クリークを所定の基準で順次抽出することに対応して、テストプランを圧縮して部分圧縮テストプランを順次生成し（図７ステップ１１０４〜ステップ１１１４）、部分圧縮テストプランの数が２以上であるときは部分圧縮テストプランの集合を圧縮テストプランの集合として再度圧縮可能グラフを生成して上記の処理を繰り返す。
【００４７】
そして、部分圧縮可能グラフから最初にクリークを取り出すときのそのクリークに最初に入れる頂点を変えてＮ通りの圧縮テストプランを生成し（図７のステップ１１２０，１１２２）、それらの中から最短のものを採用する（ステップ１１２４）。配列ＦＶＡ（図７のステップ１１００）はこの最初に取り出す頂点の優先順位を示す配列であり、ＦＶＡはテストプラン圧縮可能グラフの頂点を以下の要素でソートした配列である。
【００４８】
（ソート要素１）各頂点ｖの隣接頂点集合をｎｂｒ（ｖ）とし、ｎｂｒ（ｖ）の要素をｕで表すと、Σｎｂｒ（ｕ）の大きいもの順に全部の頂点をソートする。
【００４９】
（ソート要素２）Σｎｂｒ（ｕ）の値が同じである頂点ｖに対して、ｎｂｒ（ｖ）の大きいもの順にソートする。
【００５０】
（ソート要素３）ｎｂｒ（ｖ）の値が同じである頂点ｖに対して、Σｗ（ｖ，ｕ）（ｕ∈ｎｂｒ（ｖ））の小さいもの順にソートする。
【００５１】
本発明の第１のヒューリスティックアルゴリズムの詳細を疑似Ｃ言語を用いて表５に示し、その中で使用されている関数を表６に示す。
【００５２】
【表５】
0003803283.tif 000009
【００５３】
【表６】
0003803283.tif 000010
【００５４】
表５の３行目においてＦＶＡ（ｉ）を生成し、４行目においてｉに０からＮ−１までの値を代入して６〜２１行の処理（後に詳述）が繰り返される。２２〜２８行目において、各ｉについて生成された圧縮テストプランＳＴのうち長さが最短のものがＭｉｎ ＣＴＰＴとして採用される。
【００５５】
６〜２１行の処理については、まずいくつかのテストプランを圧縮した部分圧縮テストプランの集合ＳＣを空集合に初期化する（７行目）。次にテストプラン集合ＣＴが空集合になるまで、以下の処理を繰り返す（８行目）。
【００５６】
・まずＴからテストプラン圧縮可能グラフＧ＝（Ｖ，Ｅ，ｊ，ｔ）を生成する（９行目）。
【００５７】
・次に関数Ｅｘｔｒａｃｔ−ｆｉｒｓｔ−ｃｌｉｑｕｃ（）またはＥｘｔｒａｃｔ ｃｌｉｑｕｅ（）によって（後述）、テストプラン圧縮可能グラフＧから最大クリークＣを１つ抽出する（１０〜１５行）。
【００５８】
・次に関数Ｓｃｈｅｄｕｌｅ ｔｅｓｔ ｐｌａｎ（）によって、クリークＣの要素であるテストプランをスケジューリング情報に従って、テストプラン圧縮スケジューリング表の適当な時刻にスケジューリングし、部分圧縮テストプランＳＴを生成する（１６行目）。
【００５９】
・次に部分圧縮テストプラン集合ＳＣにＳＴを追加する（１７行目）。
【００６０】
・次にテストプラン集合ＴからクリークＣの要素であるテストプランを削除する（１８行目）。
【００６１】
ＣＴが空集合になったとき、上記の繰り返し処理（８行目〜１９行目）を抜けだし、部分圧縮テストプラン集合ＳＣを新たにＣＴとし（２０行目）、部分圧縮テストプラン集合の要素数が１になるまで（２１行目）、６行目から２１行目までの処理を繰り返す。すなわち、部分圧縮テストプランを新たなテストプランと考える。部分圧縮テストプラン集合の要素数が１つのとき、その要素ＳＴが各ｉの値における圧縮テストプランを与える。
【００６２】
１０〜１５行の処理において、ＣＴがＴに等しいとき、すなわち、グラフＧから最初のクリークが抽出されるとき、Ｅｘｔｒａｃｔ−ｆｉｒｓｔ−ｃｌｉｑｕｃ（）が使用され、それ以外の場合、Ｅｘｔｒａｃｔ−ｃｌｉｑｕｃ（）が使用される。両者の違いは、前者では抽出されるクリークに最初に入れる頂点がＦＶＡ（ｉ）であるのに対して後者では関数Ｂｅｓｔ−ｆｉｒｓｔ−ｖｅｒｔｅｘ（）により決定される点にある。関数Ｂｅｓｔ−ｆｉｒｓｔ−ｖｅｒｔｅｘ（）は以下の基準により頂点を決定する。なお、この基準は図７のステップ１１０８における基準２に対応する。
【００６３】
（Ｈ１）頂点ｖの隣接頂点集合ｎｂｒ（ｖ）にあるすべての頂点ｕの隣接頂点数の総和Σ｜ｎｂｒ（ｕ）｜がもっとも大きい頂点を選択する（頂点集合Ｖ１、表６の１２行目）。
【００６４】
隣接頂点の隣接頂点数の総和が最大の頂点を選択することで、Ｃに加えられる可能性がある頂点数が増加し、結果として最大クリークが抽出される可能性が高くなる。
【００６５】
（Ｈ２）頂点集合Ｖ１において、隣接頂点数がもっとも多い頂点を選択する（頂点集合Ｖ２、１３行目）。
【００６６】
隣接頂点数が最大の頂点をＣに加えることで、（Ｈ１）と同様に結果として最大クリークが抽出される可能性が高くなる。
【００６７】
（Ｈ３）頂点集合Ｖ２において、頂点ｖと頂点ｖの隣接頂点集合ｎｂｒ（ｖ）にあるすべての頂点ｕとの間にある辺（ｕ，ｖ）につけられた重みｗ１（ｕ，ｖ）の総和がもっとも小さい頂点を選択する（頂点集合Ｖ３、１４行目）。
【００６８】
重みの総和が最小となる頂点を選択することで、（Ｈ１）と同様に結果として最大クリークが抽出される可能性が高くなる。
【００６９】
Ｖ３の頂点数が複数ある場合は、１つの頂点を選択するために、モジュール番号が最小のものを１つ選択し、Ｃに挿入し（１５行目）、Ｃをリターンする（１６行目）。
【００７０】
上記により１つの頂点が決定されたら関数Ｃａｎｄｉｄａｔｅｓ（）によって、クリーク集合Ｃに含まれる各頂点ｕの隣接頂点集合の積集合を求め、それを新たにＳとする（４または３４行目）。Ｓが空集合になるまで、Ｓの探索（４または３４行目）とＳの中から１つの頂点ｖを選択し（５または３５行目）、Ｃに挿入する処理（６または３６行目）を繰り返す。Ｓが空集合になったとき、Ｃをリターンする。この「Ｓの中から１つの頂点ｖを選択する」ときは、候補となる頂点の集合Ｓの各頂点について、以下の３つのヒューリスティックを用いる（関数Ｂｅｓｔ ｖｅｒｔｅｘ（））。なおこれは、図７における基準３に対応する。
【００７１】
Ｈ１’：隣接頂点数の最大な頂点を選択
頂点集合Ｓにおいて、頂点ｖのＳに属する隣接頂点数がもっとも多い頂点を選択する（頂点集合Ｖ４）。
【００７２】
結果として最大クリークが抽出される可能性が高くなる。
【００７３】
Ｈ２’：圧縮演算後のテストプラン長が最短となる頂点を選択
頂点集合Ｖ４において、頂点ｖとＣ中のすべての頂点を圧縮演算して生成したテストプラン長がもっとも最短である頂点を選択する（頂点集合Ｖ５）。
【００７４】
クリークを抽出した後、その要素を圧縮演算して生成したテストプラン長が短くなる可能性が高くなる。
【００７５】
Ｈ３’：圧縮演算後のテストプラン中のＸの数（またはＸの割合）が最大（最高）となる頂点を選択
頂点集合Ｖ５において、頂点ｖとＣ中のすべての頂点を圧縮演算して生成したテストプラン長のＸの数（またはＸの割合）が最大（最高）である頂点を選択する（頂点集合Ｖ６）。クリークを抽出して、その要素を圧縮演算して生成したテストプランのＸの数（またはＸの割合）が多く（高く）なり、他の圧縮テストプランと圧縮できる可能性が高くなる。
【００７６】
Ｈ１’とＨ２’とＨ３’の順番を入れ替えても良い。
【００７７】
図９に本発明に係る最適な圧縮テストプランを得るための第２のヒューリスティックアルゴリズムを示す。ステップＳ１で、任意のテストプランのペアの圧縮演算を試行した結果、その部分圧縮テストプラン長が最も短いペアを１組選択する。ステップＳ２で、２つのテストプランをテストプランスケジューリングテーブルの適切な時刻にスケジューリングし、部分圧縮テストプランを生成する。ステップＳ３で、すべてのテストプランがテストプランスケジューリング表にスケジューリングされているか否かを判定する。もし全てのテストプランがスケジュールされているならば、部分圧縮テストプランを圧縮テストプランとし、処理を終了する。それ以外の場合はステップＳ４へ進む。ステップＳ４では部分圧縮テストプランとまだスケジューリングされていないテストプランの各ペアの圧縮演算を試行した結果、その部分圧縮テストプラン長が最も短いペアを１組選択する。ステップＳ５ではスケジューリング結果を更新するとともに、部分圧縮テストプランを更新する。
【００７８】
表１のＧＣＤのテストプランの例を用いて図９のアルゴリズムの動作を説明する。Ｓ１で、すべてのテストプランから圧縮後のテストプラン長が最短になるペアを１つ選択すると、回路要素５のテストプランＴ５に対して回路要素６のテストプランＴ６がスキュー０で圧縮可能であり、圧縮後の長さが２となり最短となる（Ｔ５とＴ６のペア選択）ので、Ｓ２で表７に示すようにＴ５，Ｔ６がテストプランスケジューリング表の時刻０にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ１とする）を生成する。Ｓ３で、テストプランＴ４，Ｔ７，Ｔ１１，Ｔ１２，Ｔ１３，Ｔ１４がまだスケジューリングされていないので、Ｓ４へ進む。
【００７９】
【表７】
0003803283.tif 000011
【００８０】
次にＳ４で、Ｔ１１に対してＰＴ１がスキュー１で圧縮可能であり、圧縮後の長さが３となり最短となるので、Ｔ１１が選択される。次にＳ５で、表８に示すようにＴ１１がテストプランスケジューリング表の時刻０に、Ｔ５，Ｔ６が時刻１にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ２とする）を生成する。Ｓ３で、テストプランＴ４，Ｔ７，Ｔ１２，Ｔ１３，Ｔ１４がまだスケジューリングされていないので、Ｓ４へ進む。
【００８１】
【表８】
0003803283.tif 000012
【００８２】
次にＳ４で、Ｔ４に対してＰＴ２がスキュー１で圧縮可能であり、圧縮後の長さが４となり最短となるので、Ｔ４が選択される。次にＳ５で、表９に示すようにＴ４がテストプランスケジューリング表の時刻０に、Ｔ１１が時刻１にスケジューリングされ、Ｔ５，Ｔ６が時刻２にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ３とする）を生成する。Ｓ３で、テストプランＴ７，Ｔ１２，Ｔ１３，Ｔ１４がまだスケジューリングされていないので、Ｓ４へ進む。
【００８３】
【表９】
0003803283.tif 000013
【００８４】
次にＳ４で、Ｔ１２に対してＰＴ３がスキュー１で圧縮可能であり、圧縮後の長さが７となり最短となるので、Ｔ１２が選択される。次にＳ５で、表１０に示すようにＴ１２がテストプランスケジューリング表の時刻０に、Ｔ４が時刻３にスケジューリングされ、Ｔ１１が時刻４にスケジューリングされ、Ｔ５，Ｔ６が時刻５にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ４とする）を生成する。Ｓ３で、テストプランＴ７，Ｔ１３，Ｔ１４がまだスケジューリングされていないので、Ｓ４へ進む。
【００８５】
【表１０】
0003803283.tif 000014
【００８６】
次にＳ４で、ＰＴ４に対してＴ１３がスキュー０で圧縮可能であり、圧縮後の長さが７となり最短となるので、Ｔ１３が選択される。次にＳ５で、表１１に示すようにＴ１３，Ｔ１２がテストプランスケジューリング表の時刻０に、Ｔ４が時刻３にスケジューリングされ、Ｔ１１が時刻４にスケジューリングされ、Ｔ５，Ｔ６が時刻５にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ５とする）を生成する。Ｓ３で、テストプランＴ７，Ｔ１４がまだスケジューリングされていないので、Ｓ４へ進む。
【００８７】
【表１１】
0003803283.tif 000015
【００８８】
次にＳ４で、Ｔ１４に対してＰＴ５がスキュー２で圧縮可能であり、圧縮後の長さが９となり最短となるので、Ｔ１４が選択される。次にＳ５で、表１２に示すようにＴ１４がテストプランスケジューリング表の時刻０に、Ｔ１３，Ｔ１２が時刻２に、Ｔ４が時刻５にスケジューリングされ、Ｔ１１が時刻６にスケジューリングされ、Ｔ５，Ｔ６が時刻７にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ６とする）を生成する。Ｓ３で、テストプランＴ７がまだスケジューリングされていないので、Ｓ４へ進む。
【００８９】
【表１２】
0003803283.tif 000016
【００９０】
次にＳ４で、Ｔ７に対してＰＴ６がスキュー１で圧縮可能であり、圧縮後の長さが１０となり最短となるので、Ｔ７が選択される。次にＳ５で、表１３に示すようにＴ７がテストプランスケジューリング表の時刻０に、Ｔ１４が時刻１に、Ｔ１３，Ｔ１２が時刻３に、Ｔ４が時刻６にスケジューリングされ、Ｔ１１が時刻７にスケジューリングされ、Ｔ５，Ｔ６が時刻８にスケジューリングされ、圧縮演算∩f を行い部分圧縮テストプラン（ＰＴ７とする）を生成する。Ｓ３で、すべてのテストプランのスケジューリングが完了したのでＰＴ７を圧縮テストプラン表として処理を終了する。
【００９１】
【表１３】
0003803283.tif 000017
【００９２】
図１０に示すように、圧縮テストプランを用いたデータパス回路のテスト系列生成処理１００４では、各モジュール毎にテスト生成することにより生成したテストパターンファイル（モジュール数分のファイルが存在）と圧縮テストプランを入力とし、結果としてデータパス回路のテスト系列を出力する。図１１に、データパス回路のテスト系列生成フローを示す。Ｓ１はモジュールの個数を表す変数ｉを０に初期化する処理である。Ｓ２は各モジュールのテストパターンファイルをテストパターン数の多い順にソートする処理である。Ｓ３は０番目のモジュールのテストパターン数分の個数の圧縮テストプランを作成する処理である。Ｓ４はすべてのモジュールの処理が終了したか否かを判断する処理であり、終了していればＳ１２へ進み、それ以外の場合はＳ５へ進む。Ｓ５はｉ番目のモジュールを選択する処理である。Ｓ６はｉ番目のモジュールのテストパターン数を表す変数ｊを１に初期化する処理である。Ｓ７はｉ番目のモジュールの全テストパターンに関する処理が完了したか否かを判断する処理であり、完了した場合、Ｓ８へ進み、それ以外の場合はＳ９へ進む。Ｓ８は変数ｉをインクリメントする処理である。Ｓ９はｉ番目のモジュールのｊ番目のテストパターンを選択する処理である。Ｓ１０は変数ｊをインクリメントする処理である。Ｓ１１はｉ番目のモジュールのｊ番目のテストパターンをｊ番目の圧縮テストプラン表のｂi に代入する処理である。Ｓ１２は全ての圧縮テストプラン表を連結し、データパスのテスト系列とする処理である。Ｓ１３はデータパスのテスト系列中に残ったｂとＸにランダムに０または１を割り当てる処理である。
【００９３】
表４に示す４つのテストプランから、表１４の圧縮テストプランが生成される（表１４中、ｂi はテストプランＴi 内のｂを示す）。
【００９４】
【表１４】
0003803283.tif 000018
【００９５】
この例においてモジュール１のテストパターンが以下のＶ１１〜Ｖ１４であったとする。
【００９６】
Ｖ１１＝（Ｐ０，Ｐ１，Ｐ３）＝（１，０，１）
Ｖ１２＝（Ｐ０，Ｐ１，Ｐ３）＝（０，０，０）
Ｖ１３＝（Ｐ０，Ｐ１，Ｐ３）＝（１，１，０）
Ｖ１４＝（Ｐ０，Ｐ１，Ｐ３）＝（０，１，０）
モジュール２のテストパターンが以下のＶ２１〜Ｖ２４であったとする。
【００９７】
Ｖ２１＝（Ｐ０，Ｐ２）＝（０，０）
Ｖ２２＝（Ｐ０，Ｐ２）＝（１，０）
Ｖ２３＝（Ｐ０，Ｐ２）＝（０，１）
Ｖ２４＝（Ｐ０，Ｐ２）＝（１，１）
モジュール３のテストパターンが以下のＶ３１〜Ｖ３２であったとする。
【００９８】
Ｖ３１＝（Ｐ１）＝（０）
Ｖ３２＝（Ｐ１）＝（１）
モジュール４のテストパターンが以下のＶ４１〜Ｖ４２であったとする。
【００９９】
Ｖ４１＝（Ｐ０）＝（０）
Ｖ４２＝（Ｐ０）＝（１）
表１４の圧縮テストプランに上記のテストパターンを代入してデータパスのテスト生成を行う。まずモジュールのテストパターン数の最大は４であるので圧縮テストプランを４個作成する。Ｖ１１〜Ｖ４２のテストパターンを４個の圧縮テストプランに代入した結果を表１５に示す。この４つのテスト系列を連結して作成したデータパスのテスト系列を表１６に示す。表１６に残ったｂi とＸの箇所にはランダムに０または１を設定する。
【０１００】
【表１５】
0003803283.tif 000019
【０１０１】
【表１６】
0003803283.tif 000020
【０１０２】
図１２は、従来方式に従い、表１のＧＣＤ回路のテストプランを圧縮しないで各テストプランにテストパターンを代入したテスト系列をＤＦＴ済みデータパス回路１００’に与えるテストコントローラ１０４を有するＧＣＤ回路を示し、図１３はテストコントローラ１０４の詳細を示す。図１４はテストコントローラ１０４の状態遷移図である。
【０１０３】
図１２において、テストコントローラ１０４はテストモード用の信号ｔ１、コントローラのリセット信号、データパスの外部入力からの４ビットを入力とし、データパスの制御信号（既存のモジュールの制御信号とＤＦＴのために追加した制御信号）を発生する。
【０１０４】
図１３において、ＴＭＲはテストプランＩＤレジスタであり、テストされる各モジュールＩＤを記憶するためのレジスタである。ＧＣＤではテストされるモジュール数は８であるので、ｌｏｇ2 ８＝３ビットレジスタが必要である。ＴＰＲはテストパターンレジスタであり、各モジュールの制御信号に目標故障毎に異なる値ｂを与える。ＧＣＤでは各モジュールに多くても１ビットの制御信号しかもたないので、１ビットレジスタのみ必要である。もしすべてのテストプランにおいて制御入力にｂが出現する時刻において、かならず値がＸである外部入力が存在する場合は、その外部入力からＴＰＲを介さず直接制御信号に値を入力することができる。ＴＰＲとＴＭＲはロード・ホールド機能を持ち、コントロール回路のリセット入力で制御される。リセットがオン状態のとき、ロードモードになり、オフのとき、ホールドモードになる。
【０１０５】
図１４において、状態数は各モジュールに対するテストプラン長の最大値に等しいので、５状態必要であり状態レジスタのビット幅は〔ｌｏｇ2 ５〕で３となる（ただし、〔ｘ〕はｘの小数部を切り捨てて整数化したものを表す。以下同じ）。回路要素１１をテストする場合を考える。Ｔ１１は時刻１で制御入力ｍ４にｂを入力する必要がある（表１）。Ｔ１１をテストするためのテストパターン数が４であり、そのうちｂが０となる場合が２つ、１となる場合が２つあるとする。まず時刻０でＲをＯＮ、ｔ１＝０にして、ｘｉｎからＴＭＲへ回路要素１１のＩＤ（例えば０００とする）、ＴＰＲへ０を設定する。時刻１でＲをＯＦＦ、ｔ＝１にし、Ｔ１１の時刻０の値を制御信号へ出力する（Ｓ０）。時刻２でＴ１１の時刻１の値（ｍ４の値は０）を制御信号へ出力する（Ｓ１）。時刻３でＴ１１の時刻２の値を制御信号へ出力する（Ｓ２）。時刻４でＴ１１の時刻０の値を制御信号へ出力する（Ｓ０）。時刻５でＴ１１の時刻１の値（ｍ４の値は０）を制御信号へ出力する（Ｓ１）。時刻６でＴ１１の時刻２の値を制御信号へ出力する（Ｓ２）。時刻７でＲをＯＮ、ｔ１＝０にして、ｘｉｎからＴＭＲへ回路要素１１のＩＤ（０００）、ＴＰＲへ１を設定する。時刻８でＲをＯＦＦ、ｔ＝１にし、Ｔ１１の時刻０の値を制御信号へ出力する（Ｓ０）。時刻９でＴ１１の時刻１の値（ｍ４の値は１）を制御信号へ出力する（Ｓ１）。時刻１０でＴ１１の時刻２の値を制御信号へ出力する（Ｓ２）。時刻１１でＴ１１の時刻０の値を制御信号へ出力する（Ｓ０）。時刻１２でＴ１１の時刻１の値（ｍ４の値は１）を制御信号へ出力する（Ｓ１）。時刻６でＴ１３の時刻２の値を制御信号へ出力する（Ｓ２）。この従来のテストコントローラはデータパス中の全モジュールを識別するためのＴＭＲが約ｌｏｇ2 ｎ個（ｎはモジュール数）必要となる。また各状態遷移において最大ｎ個の条件分岐が存在し、そのための回路規模が膨大になる。
【０１０６】
図１５は本発明の圧縮テストプランを用いたテスト生成方法を用いたときのＧＣＤのテストコントローラを示す。圧縮テストプラン（表１３のＰＴ７参照）の制御入力にｂが５つ存在するので、５ビットのＴＰＲが必要となる。またはＴＰＲを用いない場合は、圧縮テストプランの同一時刻の制御入力に最大２個のｂが存在するので、テスト用の２本の外部入力を直接にＴＰＧに入力することもできる。
【０１０７】
図１６は図１５のテストプラン生成回路の状態遷移図である。図１６において、ＧＣＤの圧縮テストプランの長さは１０であるので、状態数は１０個になる。〔ｌｏｇ2 １０〕で状態レジスタのビット幅は４となる。ｔ１＝１のとき、状態遷移を行い、出力はｉｆ文を必要とせず、ただひととおりの制御入力を出力する。出力にｉｆ文を必要としないので、モジュール数の多い大規模回路に対してはＴＰＧの組合せ回路の面積を従来方法と比べて大幅に削減できる。
【０１０８】
表１６のテスト系列にはｂｉの中でテストパターンの実際の値が代入されずに残っているものがいくつかある。これは、各モジュール（回路要素）のテストパターンの数が等しくないために生じる。そこで、複数のテストプランをそれぞれの推定テストパターン数に応じて複数のグループに分類し、各グループごとに圧縮テストプランを生成してテストパターンを代入し、それらを連結すれば、全体のテスト系列長を短くすることができる。
【０１０９】
図１７は、テストプランをグルーピングして、複数の圧縮テストプランを生成する処理フローを示している。図６のフローに加えて、回路要素の推定テストパターン数を入力して、テストパターン数に応じてテストプランをグループ化して（ステップ１２００）、各グループに対して圧縮テストプランを生成する。
【０１１０】
図１８はテストプランのグループ化の処理フローを示している。Ｓ１は、回路モジュールのテストパターン数が多い順にテストプランをソートする処理である。Ｓ２は、テストプランをソートし、テストパターン数が変化するテストプラン間を減少点と定義し、指定されたグループ数−１の減少点のすべての組合せについて無効領域値を計算する処理である。無効領域値とは
【０１１１】
【数４】
0003803283.tif 000021
【０１１２】
で定義される。ｎはテストプラン数、ｍａｘ Ｎは各モジュールが属するグループ内のテストパターン数の最大値、Ｎi はモジュールｉのテストパターン数、Ｌi はモジュールｉのテストプラン長である。無効領域値は無駄になるテスト系列長を表す。Ｓ３は、無効領域値が最小となる減少点の組合せを選択し、圧縮テストプラン表を生成するテストプランをグループ化する処理である。
【０１１３】
図１９にＧＣＤのテストプラングループ化の例を示す。Ｔ４，Ｔ５，Ｔ６のテストパターン数２０，Ｔ７のテストパターン数１６，Ｔ１４，Ｔ１３，Ｔ１２のテストパターン数５，Ｔ１１のテストパターン数４が与えられている。Ｓ１で図１９に示すようにテストプランをソートする。減少点としてＰ１，Ｐ２，Ｐ３の３点ができる。いまテストプランを３つのグループに分割しようとすると。減少点を２点選ぶ必要がある。 3Ｃ2 で３通りの減少点の組合せが考えられる。Ｓ２で３通りの減少点の組合せで無効領域値を計算する。減少点Ｐ１，Ｐ２を選択した場合、無効領域値は３、減少点Ｐ１，Ｐ３を選択した場合、無効領域値は１４３、減少点Ｐ２，Ｐ３を選択した場合、無効領域値は１６となる。Ｓ３で、無効領域値が最小が３となる減少点Ｐ１，Ｐ２が選択される。Ｔ４，Ｔ５，Ｔ６をグループ化（Ｇ１）、Ｔ７をグループ化（Ｇ２）、Ｔ１４，Ｔ１３，Ｔ１２，Ｔ１１（Ｇ３）をグループ化する。この場合の各グループの圧縮テストプランを表１７に示す。データパス全体のテスト系列長は１５９となる。
【０１１４】
【表１７】
0003803283.tif 000022
【０１１５】
図２０は３つの圧縮テストプラン（表１７）を用いる場合の、ＧＣＤのテストコントローラを示したものである。表１７（ｃ）の制御入力のｂの個数が４で表１７の中で最大となるので、ＴＰＲのビット幅は４ビットなる。また３つの圧縮テストプランを識別するために、ＣＴＰＴ−ＩＤＲのビット幅は〔ｌｏｇ2 ３〕で２ビットとなる。
【０１１６】
図２１に３つの圧縮テストプラン表を用いた場合の、ＧＣＤのテストプラン生成回路の状態遷移図を示す。表１７（ｃ）の圧縮テストプランが長さ７で最大となるので、状態数は７となり状態レジスタのビット幅は〔ｌｏｇ2 ７〕で３ビットとなる。各状態で制御入力は最大３種類存在する。
【０１１７】
図１９の例でわかるように、セレクタまたはマルチプレクサ（図１９の例では図３中の回路要素１１〜１４）のテストパターンの数は比較的少ない。また、他の回路要素のテストの結果が正常であればこれらの回路要素も正常であるはずであることが多い。そこで、セレクタまたはマルチプレクサについてのテストプランについては圧縮の対象から除外して圧縮テストプランを生成すれば、テスト系列長を一層短縮することができる。前述のＧＣＤ回路の例では、テストプランＴ４〜Ｔ７から圧縮テストプランを生成することにより、表１８の圧縮テストプランが得られ、テスト系列長は１００になる。
【０１１８】
【表１８】
0003803283.tif 000023
【０１１９】
圧縮テストプランを生成する段階で各回路要素に必要なテストパターンの数が既知であるとき、各テストプランをそれぞれテストパターン数だけ用意して（これをテストと称する）これらを圧縮したもの（これを圧縮テストと称する）を生成し、これにテストパターンを代入することによりテスト系列をつくることもできる。例えば回路要素１〜３のテストプランＴ１〜Ｔ３が表１９〜表２１のように与えられ、回路要素１〜３のテストパターン数がそれぞれ１，２および１であるとき、テストＴ11，Ｔ21，Ｔ22およびＴ31が生成され、それらが表２２のようにスケジューリングされ、表２３に示す圧縮テストが生成される。
【０１２０】
【表１９】
0003803283.tif 000024
【０１２１】
【表２０】
0003803283.tif 000025
【０１２２】
【表２１】
0003803283.tif 000026
【０１２３】
【表２２】
0003803283.tif 000027
【０１２４】
【表２３】
0003803283.tif 000028
【０１２５】
図２２には、上位階層ブロックＺが２つのＧＣＤ回路ブロックＡ，Ｂを含む、階層構造をなした回路が示されている。各ブロックＡ，Ｂがブロックの外側から強可検査性であれば、図２３に示すように、２つのセレクタを追加することにより、上位階層ブロックの外側からも強可検査性となり、そのピン割当て表は表２４に示す如くになる。
【０１２６】
【表２４】
0003803283.tif 000029
【０１２７】
このピン割当て表に従って表１のテストプランを上位モジュールＺのピンからのテストプランに変換すると、回路ブロックＡおよび回路ブロックＢについてそれぞれ表２５および表２６に示すようなテストプランが得られる。
【０１２８】
【表２５】
0003803283.tif 000030
【０１２９】
【表２６】
0003803283.tif 000031
【０１３０】
これら合計１６個のテストプランをテストプランスケジューリング表にスケジューリングして、その結果から圧縮演算を実行した結果、表２７に示す圧縮テストプランが生成される。この圧縮テストプランの長さは１５であり、テストパターン数の最大は２０であるので（図１９参照）、ブロックＡ，Ｂのデータパスのテスト系列長は３００となる。一方、各ブロックＡ，Ｂのテストプランをそれぞれ圧縮してブロックＡ，Ｂを順番にテストする場合、それぞれの圧縮テストプラン長は１０であるので、全体のテスト系列長は４００であり、ブロックＡ，Ｂを並列にテストすれば、テスト系列を大幅に削減できることがわかる。
【０１３１】
【表２７】
0003803283.tif 000032
【０１３２】
図２４はテストコントローラを挿入した回路全体図を示す。テストコントローラから各ブロックのデータパスの制御入力を駆動している。また表２７からＴＰＲは１０ビット必要となり、状態数は１５であるので、状態レジスタは〔ｌｏｇ2 １５〕で４ビットなる。
【０１３３】
これまでに説明した圧縮テストプランの生成方法およびテスト系列生成方法はいずれもコンピュータに所定の処理を実行させるためのプログラムにより実現される。このプログラムは、コンピュータに接続されたハードディスクに格納しても良いし、ＣＤ−ＲＯＭなどの記憶媒体に記憶させて必要に応じてＣＤ−ＲＯＭをＣＤ−ＲＯＭドライブへ挿入することにより、ＣＤ−ＲＯＭに格納されたプログラムをコンピュータ内の記憶装置へ読み込ませても良いし、ネットワークを介してネットワークに接続された記憶装置から必要に応じてパーソナルコンピュータ内の記憶装置へ読み込ませても良い。それによって、本発明の方法及び装置が実現される。
【０１３４】
【発明の効果】
以上述べたように本発明によれば、ＲＴＬデータパス回路を構成する回路要素のテストプランを圧縮可能な形で並列にスケジューリングし、圧縮テストプランを生成することでテスト系列長を大幅に削減することができ、テストのために付加される回路の規模を削減することができる。
【図面の簡単な説明】
【図１】ゲートレベルに変換される前の回路の構成を示す図である。
【図２】ＲＴＬレベルで記述された回路の一例としてのＧＣＤ回路のデータパスを示す図である。
【図３】ＤＦＴ済みのＧＣＤ回路のデータパスを示す図である。
【図４】テスト容易化処理を示す図である。
【図５】テスト系列生成処理を示す図である。
【図６】圧縮テストプラン生成処理を示す図である。
【図７】圧縮テストプラン生成のための第１のヒューリスティックアルゴリズムを示すフローチャートである。
【図８】圧縮可能グラフの一例を示す図である。
【図９】圧縮テストプラン生成のための第２のヒューリスティックアルゴリズムを示すフローチャートである。
【図１０】テスト系列生成処理を示す図である。
【図１１】テスト系列生成処理の詳細を示すフローチャートである。
【図１２】従来技術によるテストコントローラを示す図である。
【図１３】図１２のテストコントローラの詳細を示す図である。
【図１４】図１３の順序回路ＴＰＧの状態遷移図である。
【図１５】本発明によるテストコントローラの詳細を示す図である。
【図１６】図１５の順序回路ＴＰＧの状態遷移図である。
【図１７】グループ化したテストプランからの圧縮テストプランの生成を示す図である。
【図１８】テストプランのグループ化処理のフローチャートである。
【図１９】減少点を説明するグラフである。
【図２０】グループ化を導入した場合のテストコントローラの詳細を示す図である。
【図２１】図２０の順序回路ＴＰＧの状態遷移図である。
【図２２】階層構造をなす回路の一例を示す回路ブロック図である。
【図２３】ＤＦＴ済みの図２２の回路を示す回路ブロック図である。
【図２４】階層構造をなす回路のためのテストコントローラを示す回路ブロック図である。
【図１】
0003803283.tif 000033
【図２】
0003803283.tif 000034
【図３】
0003803283.tif 000035
【図４】
0003803283.tif 000036
【図５】
0003803283.tif 000037
【図６】
0003803283.tif 000038
【図７】
0003803283.tif 000039
【図８】
0003803283.tif 000040
【図９】
0003803283.tif 000041
【図１０】
0003803283.tif 000042
【図１１】
0003803283.tif 000043
【図１２】
0003803283.tif 000044
【図１３】
0003803283.tif 000045
【図１４】
0003803283.tif 000046
【図１５】
0003803283.tif 000047
【図１６】
0003803283.tif 000048
【図１７】
0003803283.tif 000049
【図１８】
0003803283.tif 000050
【図１９】
0003803283.tif 000051
【図２０】
0003803283.tif 000052
【図２１】
0003803283.tif 000053
【図２２】
0003803283.tif 000054
【図２３】
0003803283.tif 000055
【図２４】
0003803283.tif 000056