(57)【要約】【課題】データ信号線のビット幅が不均一である場合も適用可能なテスト容易化設計を提供し、テスト時間を短縮してテストのための付加回路を削減し、極めて大規模な回路に対するテスト容易化設計を実現可能にするアーキテクチャを提供する。【解決手段】各回路要素の制御経路および観測経路についてデータ線の不足個所をマーキングし（ステップ１００６）、回路要素側でマークのない個所に仮想テストピンを割り当て（ステップ１００８）、テスト時に不足分のデータ線が外部入出力側と接続されるように回路を追加する（ステップ１０１０）。再収斂分岐構造を構成する回路要素を見い出してそれらを１つの回路要素とみなしてテスト容易化設計を行なう。圧縮テストプラン表毎にデコーダを分割し、テスト長およびテストコントローラの規模を最適化する圧縮テストプラン表を得るようにテストプランをグルーピングする。【選択図】図１３
2006228238.tif 000002
【特許請求の範囲】
【請求項１】
ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計方法であって、
データパスに含まれるテスト対象の回路要素の各々について、テスト時にデータパスの入力から回路要素の入力へデータを伝搬する第１の経路上で、データ線の数が回路要素の入力のビット数よりも不足している個所とその不足ビット数を決定し、
テスト対象の回路要素の各々について、テスト時に回路要素の出力からデータパスの出力へデータを伝搬する第２の経路上で、データ線の数が回路要素の出力のビット数よりも不足している個所とその不足ビット数を決定し、
第１の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第１の経路に沿って回路要素側にある個所に第１の仮想テストピンを割り当て、
第２の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第２の経路に沿って回路要素側にある個所に第２の仮想テストピンを割り当て、
不足ビットを有する個所のいずれよりも第１の経路に沿ってデータパス入力側にある個所と第１の仮想テストピンの間が、第１の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第１の回路を付加し、
不足ビットを有する個所のいずれよりも第２の経路に沿ってデータパス出力側にある個所と第２の仮想テストピンの間が、第２の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第２の回路を付加し、
第１および第２の回路が付加されたデータパスに対してテスト対象の回路要素のテストプランを生成するステップを具備する集積回路のテスト容易化設計方法。
【請求項２】
同一の個所に複数の回路要素のための複数の仮想テストピンが割り当てられるとき、複数の仮想テストピンはそれらのビット数の最大値を有する１つの仮想テストピンで置換される請求項１記載のテスト容易化設計方法。
【請求項３】
外部入力が不足ビットを有するとき不足ビット数に相当する数の外部入力ピンが追加され、
外部出力が不足ビットを有するとき不足ビット数に相当する数の外部出力ピンが追加される請求項１または２記載のテスト容易化設計方法。
【請求項４】
ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計方法であって、
データパスを構成する回路要素の中から、レジスタを含まない複数の回路要素を１つの回路要素とみなしたデータパスに対してテスト容易化を行ない、
テスト容易化されたデータパスに対するテストプランを生成するステップを具備する集積回路のテスト容易化設計方法。
【請求項５】
データパスを構成する回路要素の中から、複数の回路要素で構成された再収斂分岐構造を見い出すステップをさらに具備し、
前記テスト容易化を行なうステップにおいて、見い出された再収斂分岐構造を構成する複数の回路要素が１つの回路要素とみなされる請求項４記載の方法。
【請求項６】
再収斂分岐構造を見い出すステップは、
分岐した出力を有する回路要素を見い出し、
分岐した出力を有する回路要素を起点としてデータの流れに沿ってデータが流れる方向へ回路要素を探索し、
データの流れる方向へ２度以上探索された回路要素を起点として、データの流れに沿ってデータの流れと逆の方向へ、１度以上データの流れる方向へ探索されたことのある回路要素のみを対象として探索し、
データの流れと逆の方向へ１度以上探索された回路要素を再収斂分岐構造を構成する回路要素と特定するサブステップを含む請求項５記載の方法。
【請求項７】
データパスを構成する各回路要素について決定されたテストプランをグループ化してグループ毎に圧縮して得られた複数の圧縮テストプラン表を用いてデータパスのテスト時にデータパスの制御信号を生成するテストコントローラであって、
圧縮テストプラン表の実行開始時において、実行する圧縮テストプラン表を識別する圧縮テストプラン表識別子をデータパスの入力からロードして格納する圧縮テストプラン表ＩＤレジスタと、
回路要素のテスト時に、その回路要素の制御入力に与えるべき制御値をデータパス入力からロードして格納するテストパターンレジスタと、
圧縮テストプラン表ＩＤレジスタに格納されている圧縮テストプラン表識別子に従って決定される圧縮テストプラン表及び、テストパターンレジスタに格納されている制御値に基いてテスト時のデータパスの制御信号を生成するテストプラン生成器と、
外部からのリセット信号またはテストプラン生成器の出力に基いて、テストパターンレジスタにデータパス入力から制御値をロードさせるロード信号を生成することによって、圧縮テストプラン表の実行開始時および実行途中において制御値のロードを可能にする論理和機能とを具備するテストコントローラ。
【請求項８】
複数の圧縮テストプラン表を識別する圧縮テストプラン表識別子、および回路要素のテスト時にその回路要素の制御入力に与えるべき制御値に基いて、テスト時のデータパスの制御信号を生成するテストプラン生成器であって、
実行中の圧縮テストプラン表の時刻を示す時刻信号を出力する有限状態機械と、
複数の圧縮テストプラン表のそれぞれに対して設けられた複数のデコーダであって、各デコーダは時刻信号及び制御値に基いて、それぞれの圧縮テストプラン表におけるデータパスの制御信号を生成するものと、
前記圧縮テストプラン表識別子に基いて、複数のデコーダがそれぞれ生成する制御信号のいずれか１つを選択するセレクタとを具備するテストプラン生成器。
【請求項９】
テストコントローラ面積の制約下でデータパスのテスト長を最適化するテストプランのグループ化を決定する方法であって、
（ａ）面積の制約に関する複数の条件を定め、
（ｂ）該複数の条件のもとでテスト長を最適化する整数計画問題を解くステップを具備する方法。
【請求項１０】
前記複数の条件は、グループ数がｍであるという条件、各グループに属するテストプランの長さの総和の上限がｐであるという条件、各グループに属するテストプランの駆動制御信号表の論理和における有効な制御信号の数の上限がｑであるという条件、および各グループに属するテストプランを連結した連結テストプランの密度の上限がｒであるという条件を含み、
（ｃ）ステップ（ｂ）において解が得られないときｍをインクリメントしてステップ（ｂ）を繰り返すステップをさらに具備する請求項９記載の方法。
【請求項１１】
（ｄ）ステップ（ｂ）において解が得られたときで、得られた解において生成される圧縮テストプラン表から推定されるテストコントローラの面積およびテスト長が目標値を満足しないとき、ｍを変更してステップ（ｂ）を繰り返すステップをさらに具備する請求項１０記載の方法。
【請求項１２】
ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計装置であって、
データパスに含まれるテスト対象の回路要素の各々について、テスト時にデータパスの入力から回路要素の入力へデータを伝搬する第１の経路上で、データ線の数が回路要素の入力のビット数よりも不足している個所とその不足ビット数を決定する手段と、
テスト対象の回路要素の各々について、テスト時に回路要素の出力からデータパスの出力へデータを伝搬する第２の経路上で、データ線の数が回路要素の出力のビット数よりも不足している個所とその不足ビット数を決定する手段と、
第１の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第１の経路に沿って回路要素側にある個所に第１の仮想テストピンを割り当てる手段と、
第２の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第２の経路に沿って回路要素側にある個所に第２の仮想テストピンを割り当てる手段と、
不足ビットを有する個所のいずれよりも第１の経路に沿ってデータパス入力側にある個所と第１の仮想テストピンの間が、第１の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第１の回路を付加する手段と、
不足ビットを有する個所のいずれよりも第２の経路に沿ってデータパス出力側にある個所と第２の仮想テストピンの間が、第２の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第２の回路を付加する手段と、
第１および第２の回路が付加されたデータパスに対してテスト対象の回路要素のテストプランを生成する手段とを具備する集積回路のテスト容易化設計装置。
【請求項１３】
同一の個所に複数の回路要素のための複数の仮想テストピンが割り当てられるとき、複数の仮想テストピンはそれらのビット数の最大値を有する１つの仮想テストピンで置換される請求項１２記載のテスト容易化設計装置。
【請求項１４】
外部入力が不足ビットを有するとき不足ビット数に相当する数の外部入力ピンが追加され、
外部出力が不足ビットを有するとき不足ビット数に相当する数の外部出力ピンが追加される請求項１２または１３記載のテスト容易化設計装置。
【請求項１５】
ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計装置であって、
データパスを構成する回路要素の中から、レジスタを含まない複数の回路要素を１つの回路要素とみなしたデータパスに対してテスト容易化を行なう手段と、
テスト容易化されたデータパスに対するテストプランを生成する手段とを具備する集積回路のテスト容易化設計装置。
【請求項１６】
データパスを構成する回路要素の中から、複数の回路要素で構成された再収斂分岐構造を見い出す手段をさらに具備し、
前記テスト容易化手段は、見い出された再収斂分岐構造を構成する複数の回路要素を１つの回路要素とみなす請求項１５記載のテスト容易化設計装置。
【請求項１７】
再収斂分岐構造を見い出す手段は、
分岐した出力を有する回路要素を見い出す手段と、
分岐した出力を有する回路要素を起点としてデータの流れに沿ってデータが流れる方向へ回路要素を探索する手段と、
データの流れる方向へ２度以上探索された回路要素を起点として、データの流れに沿ってデータの流れと逆の方向へ、１度以上データの流れる方向へ探索されたことのある回路要素のみを対象として探索する手段と、
データの流れと逆の方向へ１度以上探索された回路要素を再収斂分岐構造を構成する回路要素と特定する手段とを含む請求項１３記載の装置。
【請求項１８】
テストコントローラ面積の制約下でデータパスのテスト長を最適化するテストプランのグループ化を決定する装置であって、
面積の制約に関する複数の条件を定める手段と、
該複数の条件のもとでテスト長を最適化する整数計画問題を解く手段を具備する装置。
【請求項１９】
前記複数の条件は、グループ数がｍであるという条件、各グループに属するテストプランの長さの総和の上限がｐであるという条件、各グループに属するテストプランの駆動制御信号表の論理和における有効な制御信号の数の上限がｑであるという条件、および各グループに属するテストプランを連結した連結テストプランの密度の上限がｒであるという条件を含み、
解が得られないときｍをインクリメントして前記整数計画問題を繰り返し解かせる手段をさらに具備する請求項１８記載の装置。
【請求項２０】
解が得られたときで、得られた解において生成される圧縮テストプラン表から推定されるテストコントローラの面積およびテスト長が目標値を満足しないとき、ｍを変更して前記整数化問題を繰り返し解かせる手段をさらに具備する請求項１９記載の装置。
【請求項２１】
請求項１〜６のいずれか１項記載の方法によりテスト容易化されたデータパスとそのためのテストプランを生成するテストコントローラを具備する集積回路。
【請求項２２】
請求項９〜１１のいずれか１項記載の方法によるグループ化に従って設計されたテストパターン発生器を具備する集積回路。
【請求項２３】
請求項１〜６，９〜１１のいずれか１項記載の方法をコンピュータに実現させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＲＴＬ回路の段階において、ＲＴＬ回路に含まれるデータパスをテスト容易化することによる大規模集積回路（ＬＳＩ）のテスト容易化設計に関する。
【背景技術】
【０００２】
近年、ＬＳＩに搭載される回路規模の増大により、ＬＳＩのテストがますます重要になり、ＬＳＩのテスト設計の自動化は必要不可欠である。ＬＳＩのテスト設計の自動化のためには、高い故障検出効率の達成が必要であり、そのためにテスト容易化設計（ＤＦＴ）が必要である。
【０００３】
ＬＳＩの設計段階において、ゲートレベルへ変換される前のＲＴＬ回路は、データを処理するデータパスとデータパスの動作を制御するコントローラという２つの部分回路で構成されている。データパスはレジスタ、マルチプレクサ、演算器などの回路要素で構成されている。このＲＴＬ回路の段階で、データパスを構成する各回路要素を対象として完全故障検出効率を実現するテスト容易化を可能にすることが望まれている。その理由は、論理合成後のゲートレベル回路の段階でテスト容易化を行なう完全スキャン設計とは違って、ゲートレベル回路への変換前のテスト容易化であるからタイミング等の論理合成の制約が損なわれず、また、通常動作時のクロックと同じ速度のクロックを与えるテスト（ａｔ−ｓｐｅｅｄテスト）が可能になるからである。
【０００４】
「和田ほか、“完全故障検出効率を保証するデータパスの非スキャンテスト容易化設計法”、信学論、Ｊ８２−Ｄ−Ｉ、ｐｐ．８４３−８５１，１９９９年７月」および特開２００１−１３５７９１号公報には、データパスを構成する回路要素に適宜スルー機能とホールド機能を付加することによって、外部入力から各回路要素の入力へ任意の値を伝搬すること（強可制御性）と各回路要素の任意の出力値を外部出力へ伝搬すること（強可観測性）を保証することが記載されている。このスルー機能とホールド機能を追加してテスト容易化されたデータパスについて、任意の値を外部入力から各回路要素へ伝搬し（正当化）、テスト結果を外部出力へ伝搬するための制御系列であるテストプランが生成される。テストプランに具体的な制御値を代入することによって、テストのための制御信号の系列（テスト系列）が生成され、データパスに与えられる。
【０００５】
上記特開２００１−１３５７９１号公報にはテスト実施のために、コントローラとデータパスで構成されるＲＴＬ回路に、テストコントローラを追加することが記載されている。テストコントローラは、テストプランを識別するテストプランＩＤを格納するテストプランＩＤレジスタＴＭＲと、テスト系列を実現するためにテストプランへ代入される制御値を格納するテストパターンレジスタＴＰＲと、テストプラン生成回路とを含んでいる。テストプラン生成回路は、ＴＭＲに格納されているテストプランＩＤに従ってテストプランを生成し、生成したテストプランにＴＰＲに格納されている制御値を代入してデータパスに与える制御信号の系列を生成する。ＴＭＲおよびＴＰＲへは、１つのテスト系列の開始時にリセット信号により外部入力から値がロードされる。
【０００６】
ＴＭＲに必要なビット幅は、テストプラン数（＝回路要素数）をＭとするとき〔ｌｏｇ2 Ｍ〕である（ただし、〔ｘ〕はｘの小数部を切り上げて整数化したものを表わす。以下同じ）。ＴＰＲに必要なビット幅は、各テストプランに含まれる制御値を代入すべき個所の数の最大をＮとするときＮである。
【０００７】
特願２００１−３５６５１１号には、１つのデータパスのテストに必要な複数のテストプランに圧縮演算を施して１つの圧縮テストプラン表を生成することが開示されている。この圧縮テストプラン表は可能な限り多くの回路要素のテストプランを並列に実行することによってテスト時間の圧縮および回路規模の削減を図るものである。この場合、圧縮テストプラン表は１つであるからＴＭＲは不要となり、ＴＰＲに必要なビット幅は圧縮テストプラン表に含まれる制御値を代入すべき個所の数に等しい。
【０００８】
この場合に、個々の回路要素に必要なテストパターン数に差があるときでも、テストパターン数の最大値に相当する回数だけ圧縮テストプラン表が繰り返し使用されることになるので、無駄を生じる。そこで、テストパターン数に応じてテストプランを複数のグループにグループ化し、グループ毎に圧縮して複数の圧縮テストプラン表として実行することも上記出願には提案されている。この場合、ＴＭＲに必要なビット幅は〔ｌｏｇ2 （圧縮テストプラン表数）〕となるが、テスト系列長の合計は短かくなる。その理由は、各圧縮テストプラン表はテストパターン数が互いに近似した複数のテストプランからそれぞれ生成され、それぞれのグループに属するテストプランのテストパターン数の最大値に相当する回数だけ繰り返し使用されるので、テストパターン数の違いによる無駄が少なくなるからである。
【０００９】
【特許文献１】特開２００１−１３５７９１号公報
【非特許文献１】和田ほか、“完全故障検出効率を保証するデータパスの非スキャンテスト容易化設計法”、信学論、Ｊ８２−Ｄ−Ｉ、ｐｐ．８４３−８５１，１９９９年７月
【発明の開示】
【発明が解決しようとする課題】
【００１０】
前述の論文および特開２００１−１３５７９１号公報に記載された手法では、データ信号線のビット幅がすべて等しいという前提があるのに対して、実際の回路ではこの前提が常に満たされるとは限らない。
【００１１】
また、データパス中に、データの流れが分岐しその後再び合流する再収斂分岐構造が存在する場合には故障の影響が出力に伝搬されない冗長故障が存在する。しかしながら上記の手法ではこのことが考慮されず、再収斂分岐構造を構成する回路要素のすべてを対象としてスルー機能およびホールド機能が追加されるので、ハードウェア規模およびテスト時間が必要以上に増大する。
【００１２】
前述のテストパターンレジスタＴＰＲのサイズに関しては、１つの圧縮テストプラン表に含まれる制御値を代入すべき個所の数に相当するビット幅が必要であるので、回路が大規模になると、ＴＰＲに必要な回路面積が増大する。
【００１３】
前述のテストプラン生成回路に関しては、前述の特開２００１−１３５７９１号公報には機能の定義のみが与えられており、極めて大規模な回路について、論理合成により実際に実現可能なテストパターン生成回路をいかにして実現するかは示されていない。
【００１４】
前述の特願２００１−３５６５１１号に開示されたテストプランのグループ化に関しては、テスト長の最適化のみが考慮されており、最終的なテストコントローラの構成とテスト長を最適にするグルーピングの最適化については考慮されていない。
【００１５】
したがって本発明の第１の目的は、データ信号線のビット幅が均一でない場合でも適用可能な、データパスのテスト容易化設計を提案することにある。
【００１６】
本発明の第２の目的は、再収斂分岐構造を有するデータパスを効率良くテスト容易化する、データパスのテスト容易化設計を提案することにある。
【００１７】
本発明の第３の目的は、テストパターンレジスタＴＰＲのサイズの削減を可能とする、データパスのテスト容易化設計を提案することにある。
【００１８】
本発明の第４の目的は、極めて大規模な回路についても実現可能なテストパターン生成回路のアーキテクチャを提案することにある。
【００１９】
本発明の第５の目的は、提案されたアーキテクチャのもとでテストコントローラの構成およびテスト長を最適にする、テストプランのグルーピングの最適化手法を提案することにある。
【課題を解決するための手段】
【００２０】
前述の第１の目的は、ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計方法であって、データパスに含まれるテスト対象の回路要素の各々について、テスト時にデータパスの入力から回路要素の入力へデータを伝搬する第１の経路上で、データ線の数が回路要素の入力のビット数よりも不足している個所とその不足ビット数を決定し、テスト対象の回路要素の各々について、テスト時に回路要素の出力からデータパスの出力へデータを伝搬する第２の経路上で、データ線の数が回路要素の出力のビット数よりも不足している個所とその不足ビット数を決定し、第１の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第１の経路に沿って回路要素側にある個所に第１の仮想テストピンを割り当て、第２の経路上に不足ビットを有する少なくとも１つの個所が存在するとき、不足ビットを有する個所のいずれよりも第２の経路に沿って回路要素側にある個所に第２の仮想テストピンを割り当て、不足ビットを有する個所のいずれよりも第１の経路に沿ってデータパス入力側にある個所と第１の仮想テストピンの間が、第１の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第１の回路を付加し、不足ビットを有する個所のいずれよりも第２の経路に沿ってデータパス出力側にある個所と第２の仮想テストピンの間が、第２の経路上の不足ビット数の最大値に相当する数のデータ線でテスト時に付加的かつ実質的に接続されるように第２の回路を付加し、第１および第２の回路が付加されたデータパスに対してテスト対象の回路要素のテストプランを生成するステップを具備する集積回路のテスト容易化設計方法により達成される。
【００２１】
前述の第２の目的は、ＲＴＬ回路の段階においてデータパスをテスト容易化することによる集積回路のテスト容易化設計方法であって、データパスを構成する回路要素の中から、レジスタを含まない複数の回路要素を１つの回路要素とみなしたデータパスに対してテスト容易化を行ない、テスト容易化されたデータパスに対するテストプランを生成するステップを具備する集積回路のテスト容易化設計方法により達成される。
【００２２】
前述の第３の目的は、データパスを構成する各回路要素について決定されたテストプランをグループ化してグループ毎に圧縮して得られた複数の圧縮テストプラン表を用いてデータパスのテスト時にデータパスの制御信号を生成するテストコントローラであって、圧縮テストプラン表の実行開始時において、実行する圧縮テストプラン表を識別する圧縮テストプラン表識別子をデータパスの入力からロードして格納する圧縮テストプラン表ＩＤレジスタと、回路要素のテスト時にその回路要素の制御入力に与えるべき制御値をデータパス入力からロードして格納するテストパターンレジスタと、圧縮テストプラン表ＩＤレジスタに格納されている圧縮テストプラン表識別子に従って決定される圧縮テストプラン表及び、テストパターンレジスタに格納されている制御値に基いてテスト時のデータパスの制御信号を生成するテストプラン生成器と、外部からのリセット信号またはテストプラン生成器の出力に基いて、テストパターンレジスタにデータパス入力から制御値をロードさせるロード信号を生成することによって、圧縮テストプラン表の実行開始時および実行途中において制御値のロードを可能にする論理和機能とを具備するテストコントローラにより達成される。
【００２３】
前述の第４の目的は、複数の圧縮テストプラン表を識別する圧縮テストプラン表識別子および回路要素のテスト時にその回路要素に与えるべき制御値に基いて、テスト時のデータパスの制御信号を生成するテストプラン生成器であって、実行中の圧縮テストプラン表の時刻を示す時刻信号を出力する有限状態機械と、複数の圧縮テストプラン表のそれぞれに対して設けられた複数のデコーダであって、各デコーダは時刻信号及び制御値に基いて、それぞれの圧縮テストプラン表におけるデータパスの制御信号を生成するものと、前記圧縮テストプラン表識別子に基いて、複数のデコーダがそれぞれ生成する制御信号のいずれか１つを選択するセレクタとを具備するテストプラン生成器により達成される。
【００２４】
前述の第５の目的は、テストコントローラ面積の制約下でデータパスのテスト長を最適化するテストプランのグループ化を決定する方法であって、（ａ）面積の制約に関する複数の条件を定め、（ｂ）該複数の条件のもとでテスト長を最適化する整数計画問題を解くステップを具備する方法により達成される。
【発明を実施するための最良の形態】
【００２５】
実施形態１
図１はデータ線のビット幅がすべて等しい、という前提が満たされていないデータパスの一例を示す。図中、丸で囲まれた数字は定数を表わし、丸で囲まれた“Ｓ”は例えば８本のデータ線が６本と２本に分かれる、といったセパレータを表わし、丸で囲まれた“Ｂ”は例えば６本のデータ線と２本の線が束ねられて８本になる、といったバインダを表わす。図１に示したデータパスを例にとって、本発明の第１の実施形態に係るテスト容易化設計を具体的に説明する。
【００２６】
まず、図１のデータパスに対して、図２に示すような、制御林が生成される。制御林とは、外部入力（図１の例ではＰＩ，ＰＩ２）から外部出力（ＰＯ）を含むすべての回路要素の入力端子へデータを伝搬する制御経路の集合である。テスト実行時間を短縮し、追加されるＤＦＴ要素の削減のため、従来技術により、制御林はデータパス上で外部入力を始点として順序深度に基いた最短経路林を構成するように定められる。
【００２７】
次に、図３に示すような観測林が生成される。観測林とは、外部入力を含むすべての回路要素の出力から外部出力へデータを伝搬する観測経路の集合である。従来技術により、観測経路と制御経路の共有部分を極大化してＤＦＴ要素を削減するため、制御林に含まれない観測経路上の辺が最小となるように観測林が定められる。
【００２８】
そして、テスト対象の回路要素（ａｄｄ，ｍｕｌｔ１，ｍｕｌｔ２，ＭＵＸ１，ＭＵＸ２，ｃｏｍｐ）のそれぞれについて、制御林に沿って回路要素の入力から外部入力までの制御経路を探索して、回路要素の入力のビット数に対してデータ線の数が不足している辺があればそこに不足ビット数を示すマークを付し、観測林に沿って回路要素の出力から外部出力までの観測経路を探索して、回路要素の出力のビット数に対してデータ線の数が不足している辺があればそこに不足ビット数を示すマークを付す。
【００２９】
図４〜図９はそれぞれ、回路要素ａｄｄ，ｍｕｌｔ１，ｍｕｌｔ２，ＭＵＸ１，ＭＵＸ２，ｃｏｍｐについて、制御経路および観測経路を調べた結果を示す。例えば、図４において、ａｄｄの左側の入力についてはＰＩまでの制御経路上でデータ線の数が６未満である個所はないので、マークは付されない。右側の入力についても同様である。ａｄｄの出力については、ｍｕｌｔ２とＭＵＸ２の間のセパレータとＭＵＸ２の左側の入力を接続するデータ線の本数は４であり、ａｄｄの出力の６ビットから２ビット不足しているので、２ビットを示すマークが付される。ＭＵＸ２とＰＯの間にも同様に２ビットのマークが付される。
【００３０】
ｍｕｌｔ１については、図５に示すように２つの入力の２ビットおよび出力４ビットと比べて不足する個所はないのでマークは付されない。
【００３１】
ｍｕｌｔ２については、図６に示すように、右側の入力とＰＩ２の間で入力６ビットに対してデータ線の本数が２および４である個所にそれぞれ４ビットおよび２ビットのマークが付され、出力とＰＯの間で出力１２ビットに対してデータ線の本数が４である２個所に８ビットのマークが付される。
【００３２】
次に、テスト対象の各回路要素について、入力側で不足するビット数および出力側で不足するビット数を補う仮想テストピンを割り当てる。具体的には、制御林に沿ってテスト対象回路要素の入力と外部入力の間の制御経路を探索して、マークが存在していればそれらの最大値を不足ビット数と決定し、観測林に沿ってテスト対象回路要素の出力と外部出力の間の観測経路を探索して、マークが存在していればその最大値を不足ビット数と決定する。仮想テストピンを割り当てる位置は、各回路要素の入力および出力で良いが、それに限らず、マークが付された個所のいずれよりも制御経路または観測経路に沿って内側、すなわち回路要素側にある個所のいずれでも良い。
【００３３】
図示した例では、ｍｕｌｔ２の右側の入力については、図６において、制御林（図２）に沿ってＰＩとの間に４ビットのマークと２ビットのマークが付されているので、図１０に示すように、ｍｕｌｔ２の右側の入力にそれらの最大値４ビットの仮想テストピン入力ＴＰＩが割り当てられる。ｃｏｍｐに関しては、図９において、左側の入力には制御林に沿って２ビットのマークが４個、右側の入力には２ビットのマークが４個（うち３個は左側の入力と共通）付されているので、図１０に示すように、双方の入力に２ビットの仮想テストピン入力ＴＰＩ２，ＴＰＩ３が割り当てられる。ａｄｄの出力に関しては、図４において観測林に沿ってａｄｄの出力からｍｕｌｔ２の出力まではマークがないので、２ビットの仮想テストピンをこの間のどこに割り当てても良いが、他と共用するためｍｕｌｔ２の出力に割り当てることとする。ＭＵＸ１の出力に必要な２ビット（図７）も同様にｍｕｌｔ２の出力に割り当てる。これらをｍｕｌｔ２の出力のために必要な８ビット（図６）と共用して、図１０に示すように８ビットの仮想テストピン出力ＴＰＯが割り当てられる。各回路要素のテストは互いに独立に実行されるので、複数の回路要素のテストのための仮想テストピンを共用しても問題はない。
【００３４】
次に、これら仮想テストピン入力の位置に必要なビット数のテストデータをテスト時に外部入力から与え、必要なビット数の仮想テストピン出力をテスト時に外部出力へ供給するための接続を実現するための回路を付加する。この場合において、仮想テストピン入力は制御経路上でマークが付された個所のいずれよりも外部入力の側にある個所（外部入力自身を含む）と接続され、仮想テストピン出力は観測経路上でマークが付された個所のいずれよりも外部出力の側にある個所（外部出力自身を含む）と接続される。外部入力または外部出力自身にマークが付されているときは、必要な数の外部入力ピンまたは外部出力ピンが追加される。
【００３５】
図１０の例では、図１１に示すように、ＴＰＩのあったｍｕｌｔ２の右側の入力と外部入力ＰＩ２がマルチプレクサＤＭＵＸ１を介して４本のデータ線で接続されＴＰＩ２のあったｃｏｍｐの左側の入力と外部入力ＰＩ２がマルチプレクサＤＭＵＸ２を介して２本のデータ線で接続され、ＴＰＩ３のあったｃｏｍｐの右側の入力と外部入力ＰＩがマルチプレクサＤＭＵＸ３を介して２本のデータ線で接続される。マルチプレクサＤＭＵＸ１〜３は通常動作時とテスト時とを切り換えるために設けられ信号Ｔ４〜６で制御される。ＴＰＯの８ビットに関しては、ＰＯに８ビットのマークが付されているので（図６）、ピンを追加してそのまま外部出力ＴＰＯとする。
【００３６】
図１１において、ａｄｄおよびｍｕｌｔ１の右側の入力に付されている矩形は、従来技術によりスルー機能が付加されていることを意味し、信号Ｔ１およびＴ２によりそれぞれ制御される。ｍｕｌｔ２については両方の入力にスルー機能が付加されており、２ビットの信号Ｔ３で制御される。
【００３７】
最後に、図１１のようにテスト容易化されたデータパスの各回路要素のテストプランが以下の表１のように生成される。表１において、空欄はドントケアを表わす。
【００３８】
【表１】
2006228238.tif 000003
【００３９】
図１２は、仮想テストピンＴＰＩのためのデータを、外部入力ＰＩ２からではなく、制御経路の途中でＰＩ２との間にマークのない個所から引き出す例を示す。なお、必要なデータ線のすべてを回路要素側のマークのない個所と外部入出力側のマークのない個所との間で接続する必要は必ずしもなく、データ線の一部については、不足ビット数が最大でない個所のデータ線を利用しても良い。
【００４０】
以上説明した処理をフローチャートに表わすと図１３のようになる。図１３において、まず従来技術に従い、図２の制御林を生成し（ステップ１０００）、図３の観測林を生成し（ステップ１００２）、必要なスルー機能、ホールド機能を付加する（ステップ１００４）。次に、本発明に従い、テストに必要なデータ線の不足個所と不足ビット数を特定するマーキング処理を行ない（ステップ１００６）、その結果に基いて、仮想テストピンを割り当てる（ステップ１００８）。テスト時に外部入力から仮想テストピン入力が割り当てられた個所に必要なデータビットを供給するための回路、およびテスト時に仮想テストピン出力が割り当てられた個所から必要なデータビットを取り出し外部出力へ供給するための回路を追加し（ステップ１０１０）、これに対してテストプランを生成する（ステップ１０１２）。
実施形態２
図１４に示す論理回路はレジスタ１００の出力データが分岐し、加算器１０２で再び合流する再収斂分岐構造を含んでいる。このため、加算器１０２の左右の入力は独立ではなく、任意のデータを設定することはできない。従来技術では、各演算器とマルチプレクサを対象としてテストを実行するため、それぞれの演算器とマルチプレクサに任意の入力データを印加し、出力応答を観測できるように論理を追加する。
【００４１】
図１５に従来技術によるテスト容易化設計処理後の回路を示す。図１４の乗算器１０４、減算器１０６は、それぞれ入力データを変更することなく出力に伝搬するスルー機能を付加したスルー機能付き乗算器１０８、スルー機能付き減算器１１０に置き換えられる。また、加算器１０２の入力にはテスト用レジスタ１１２とテスト時と通常動作の経路切替のためのテスト用マルチプレクサ１１４が付加され、左右のデータ伝搬経路の順序深度を変え、時分割で独立のデータが設定できるようにする。また、これらの付加回路を制御するため、テスト用制御入力１１６，１１８，１２０が付加される。
【００４２】
表２に図１５の回路に対するテストプランを示す。４つの演算器と３つのマルチプレクサそれぞれ１種、計７種である。各テストプランのＴｉｍｅの欄はテストパターンを印加するタイムフレームを示す。テストプランには各タイムフレームのデータ入力（ＰＩ１，ＰＩ２）、制御入力（Ｃ１〜Ｃ３）テスト用制御入力（ＴＣ１〜ＴＣ３）のそれぞれの入力論理値とデータ出力（ＰＯ１）の観測の有無が示されている。入力論理値のうち、ｂはテストデータ、Ｘはドントケアを示している。データ出力は＊が出力応答の観測タイムフレームであることを示す。なお、各演算器のスルー機能はいずれもテスト用制御信号が１でスルー状態とする。
【００４３】
【表２】
2006228238.tif 000004
【００４４】
以上のうち、特に留意が必要なのは、加算器１０２のテストデータ入力のための付加回路、テスト用マルチプレクサ１１４とテスト用レジスタ１１２である。再収斂分岐によってテスト不可能になる故障は通常動作ではもともと出力に故障の影響が伝搬されない冗長故障である。したがって、これら２つの要素は元々テスト不要な故障を検査するために付加されている。
【００４５】
通常、テストパターンの作成ツールはこのような冗長故障を判定し、テスト対象外とする機能を有している。しかし、上記の従来技術では、個々の組み合わせ回路回路要素を対象にテストパターンを作成するため、グローバルな再収斂構造が識別されず、テスト不要であることが認識できない。テスト用レジスタ１１２とテスト用マルチプレクサ１１４は、本来追加不要な回路である。
【００４６】
以上のように、再収斂分岐構造を含む論理回路に対し、従来技術では余分なテスト回路が付加されるため、データパスのテスト回路面積が増えるという問題がある。また、上記の不要な付加回路を制御するテスト用制御信号が増えるため、制御信号を生成するテストコントローラの面積が無駄に増大するという問題がある。
【００４７】
さらに、従来技術におけるレジスタの追加は、テストプランの時刻数を増大させるため、テスト実行時間が増大するという問題がある。
【００４８】
制御信号数・テストプラン数の増大はテストコントローラ作成の計算機リソースが増えるという問題がある。
【００４９】
図１６に本発明の第２の実施形態に係るデータパスのテスト容易化設計の流れを示す。まず、ＲＴＬ回路の中で再収斂分岐構造を見い出し、再収斂分岐構造を構成する回路要素を特定する（ステップ１１００）。次に再収斂分岐構造を構成する複数の回路要素を１つの回路要素とみなし（ステップ１１０２）、これに対して従来技術と同様のテスト容易化設計を適用してテストプランおよびテスト容易化済みＲＴＬを生成する（ステップ１１０４）。
【００５０】
図１４の回路に適用した例について、さらに詳細に説明する。図１７は図１４の論理回路を、そのレジスタと各テスト単位をノードとし、レジスタおよびテスト単位間のデータ線の接続をエッジとする有向グラフで表したものである。
【００５１】
表３に無閉路の有向グラフの再収斂分岐構造に含まれるノードを抽出するアルゴリズムを示す。
【００５２】
【表３】
2006228238.tif 000005
【００５３】
図１８に示すように、グラフ中の出力が分岐するノード（Ｒ１およびｓｕｂ）から出発し、ｆｓｅａｒｃｈ（）で深さ優先の前方（出力側）探索を行い、分岐点から到達可能なノードについて到達済みフラグＦＬＧに１を立てる。探索中、到達済みのノードに再到達したら、そのノードを再収斂ノードと認識し、再収斂フラグＲＥＣＯＮＶを立てる。
【００５４】
Ｆｓｅａｒｃｈが終了した後、図１９に示すように、ＲＥＣＯＮＶフラグが立ったノード（ａｄｄ１およびｍｕｘＣ３）からｂｓｅａｒｃｈ（）で深さ優先の後方（入力側）探索を行う。このとき、到達フラグが立っている（ＦＬＧ＝＝１）ノードのみを辿り、フラグを塗り替えてゆく（ＦＬＧ＝＝２）。
【００５５】
Ｂｓｅａｒｃｈが終了した時点でＦＬＧ＝＝２のノードが再収斂構造に含まれるノードである。
【００５６】
以上を全ての分岐点から実行することで、グラフ中の再収斂構造に含まれるノードを括り出すことが出来る。
【００５７】
以上により、Ｒ１，ｍｕｘＣ２，ａｄｄ１，ｍｕｘＣ３，ｓｕｂ，ａｄｄ２からなる集合が再収斂構造内のノードの集合として認識される。なお、もう一つの分岐ノードであるｓｕｂからの探索では、上記の集合の部分集合が抽出される。
【００５８】
図２０に以上の処理により見い出された再収斂構造に含まれる回路要素を一まとめにした「テスト単位階層」を付加した後の論理回路を示す。（この例では従来技術との比較のため、テスト単位を組合せ論理とし、レジスタはテスト単位階層に含めない。）
図２０では図１４の論理回路のうち、ｍｕｘＣ３，ａｄｄ１，ｍｕｘＣ３，ｓｕｂ，ａｄｄ２を一つのテスト単位階層１２２として２データ入力１データ出力の演算器で表している。テスト単位階層１２２は、スルー機能の実現のためにテスト用制御入力１２４を備える。スルー機能の実現例として、図２１に右側スルー機能、図２２に左側スルー機能を付加した例を示す。いずれもＴＣ１＝１でスルー状態である。
【００５９】
以上のテスト単位階層作成処理により出力した新たな階層とスルー情報を利用し、階層テスト容易化設計処理を行う。
【００６０】
図２３に図２０の回路の観測林、図２４に制御林を示す。これらより、テスト単位階層１２２には右側スルー機能が、ｍｕｌｔｉに左側スルー機能が必要であることがわかる。
【００６１】
図２５に図２０の回路にテスト容易化設計を施した回路を示す。また、表４に図２５の回路のテストプランを示す。
【００６２】
【表４】
2006228238.tif 000006
【００６３】
次に、図１４の論理回路に従来技術と本実施形態を適用した結果を比較し、本実施形態の利点を述べる。
【００６４】
第一に、本手法のテスト回路面積は、従来技術と比較して個々の演算器にスルー機能を付加しなくて済み、冗長論理への回路付加がなくなるため低減される。従来技術適用後の図１５と本実施形態適用後の図２１および図２５で比較すると、ｓｕｂのスルー機能とレジスタＲ５の分だけ従来手法より付加回路が減少している。
【００６５】
第二に、上記付加回路の低減に伴い、テスト用制御信号を低減できる。本実施形態では、テスト用制御信号は図１５の従来例でＴＣ１〜３の３本なのに対し、図２５の本実施形態適用例ではＴＣ１〜ＴＣ２の２本で済ませることができた。言い換えると、テストコントローラの出力数を低減できるため、テストコントローラの面積を減らすことができる。
【００６６】
第三に、複数のテスト単位を１つにまとめることで、テスト単位の数が減るのでテストプラン数が減る。それにより、テストプランを管理するテストコントローラの内部状態数を低減できる点でも、テストコントローラの面積低減が期待できる。本実施形態では表２の従来例で６個のテスト対象回路要素であったものを図２５の本実施形態適用後の例で１個の階層としたため、表４に示すようにテストプラン数が７個から２個に低減された。
【００６７】
制御信号数、テストプラン数の低減はテストコントローラの生成時の計算機リソースを低減できるため、扱える回路規模がより大きくでき、階層テストの実用性を高めることができる。
【００６８】
最後に、テスト時間に関しても、従来例より短縮が期待できる。実施例で示したように再収斂分岐構造に対し従来例ではレジスタを追加するのに対し、本発明を適用すればレジスタの追加が不要であるため、テストプラン長を短くできる可能性がある。実施例では、表２の従来例で加算器１つ、マルチプレクサ３つのテストプランが４時刻を要するものであった。これらは本発明適用時、図２５に示すように、右側スルー機能付きテスト単位階層１２２に集約されており、表４に示すように、そのテストプラン長は３時刻に低減されている。テスト時間は
テスト時間＝テストパターン数×テストプラン長÷テストクロック周波数
で計算されるため、テストプラン長の増減はテスト時間の増減につながる。
実施形態３
表５に、図２６に示す、ＧＣＤ（最大公約数）を求める回路のデータパスの各組合せ回路要素毎のテストプランを示す。なお、図２６の回路において、テスト容易化設計により、ｓｕｂ．１の出力にセレクタが追加されている。表６は表５で示したテストプランを３つのグループに分割し、それぞれのグループで生成した圧縮テストプラン表を示す。テストプランのグループ化および圧縮についての詳細は、特願２００１−３５６５１１号に記載されている。
【００６９】
【表５】
2006228238.tif 000007
【００７０】
【表６】
2006228238.tif 000008
【００７１】
表６の（ｃ）に示されるＧ３の圧縮テストプラン表に着目すると、制御入力（Ｌ１〜Ｔ１）のｂの個数は４個であり、特願２００１−３５６５１１号の先行技術によれば、図２７に示すように、前述したテストコントローラ中のＴＰＲ（テストパターンレジスタ）のビット幅は４となる。このように、先行技術では、圧縮テストプラン表の制御入力のｂの個数分のビット幅を持つＴＰＲが必要となる。
【００７２】
図２８に、本発明の第３の実施形態に係るテストコントローラのアーキテクチャを示す。従来ＴＰＲのロード・ホールドの制御はオリジナルコントローラのリセット信号によって制御されていたが、ＴＰＧから１本信号を出力するようにし（ロード信号）、リセット信号と論理和をとった信号線でＴＰＲのロード・ホールドの制御を行うようにする。ＴＰＲは外部入力Ｘｉｎから信号を入力しているとすると、表６の（Ｃ）の圧縮テストプラン表の時刻４に着目するとＸｉｎの値はＸであるので、このタイミングで時刻６のｍ１とｍ３に与えるｂに相当する信号値を入力し、ＴＰＧからロード信号（論理値１）を出力するようにする（それ以外の時刻ではロード信号は論理値０を出力するようにする）。時刻５でＴＰＲはロードモードになり、時刻６でｍ１とｍ３に与えるべき値がＸｉｎからＴＰＲに設定される。このようにＸｉｎの値がＸである時刻ｔでＴＰＧからロード信号として論理値１を出力し、時刻ｔ＋１で、ｔ＋１以上の時刻で制御入力に与える論理値をＴＰＲに設定することで、ＴＰＲのビット幅を削減することができる。図２８の例では、時刻４でＴＰＧからロード信号として論理値１を出力することにより、ＴＰＲのビット幅を２ビットに削減することができる。
実施形態４
従来技術ではテストコントローラのＴＰＧについて機能のみが定義されており、ＴＰＧのアーキテクチャに関する説明は一切ない。ＴＰＧはテストプランまたは圧縮テストプラン表の現在時刻を状態で表し、各テストプラン（圧縮テストプラン表）毎にデータパスの制御信号に与える論理値をデコードして出力する機能を有する。テストプラン数（圧縮テストプラン表数）の増加、テストプラン長（圧縮テストプラン表の長さ）の増加、データパスの制御信号数の増加を考えると、大規模なデータパスの場合、ＴＰＧのデコーダが爆発的に大きくなり、事実上論理合成が不可能になる。
【００７３】
図２９は本発明の第４の実施形態に係るＴＰＧのアーキテクチャを示す。図２９に示すように、各テストプラン（または圧縮テストプラン表）Ｇ1 ，Ｇ2 …Ｇm 毎にデコーダブロックを完全に分割し、それぞれに対して有限状態機械ＦＳＭから実行中のテストプラン（圧縮テストプラン表）の時刻を与える。各デコーダが出力する信号線をＴＭＲの値に従ってマルチプレクサ（ＭＵＸ部）で選択することによって、ＴＭＲ（ＣＴＰＴ−ＩＤＲ）で指定されたテストプラン（圧縮テストプラン表）によるテスト系列を選択し、制御信号Ｃ1 ，Ｃ2 …としてデータパスへ与える。各デコーダ毎に論理合成が適用されるので、後述するように、デコーダの入出力信号線数を制約するように圧縮テストプラン表を生成することで、大規模データパスの場合でも、容易にＴＰＧを論理合成することができる。なお、各テストプラン（圧縮テストプラン表）ｊの長さをＧＬj とするとき、ＦＳＭから各デコーダへ時刻を２進数にエンコードして与えるとき、デコーダの入力信号線数は〔ｌｏｇ2 ＧＬj 〕であり、デコードした形で与えるときは、図２９に示すように、デコーダの入力信号線数はＧＬj である。また各デコーダの出力信号線数はそれぞれのテストプラン（圧縮テストプラン表）が駆動する制御信号の数（後述）ＧＮＣj である。
実施形態５
特願２００１−３５６５１１号において提案されたテストプランのグルーピング方法は、テスト長のみの最適化を考えたもので、実際に生成された圧縮テストプラン表の値をデータパスの制御信号に与えるためのテストコントローラの規模が膨大になる可能性がある。前述のＴＰＧのアーキテクチャを採用したとしても、各デコーダの入出力数が膨大になり、論理合成不可能になる可能性もある。
【００７４】
表７は本発明の第５の実施形態を説明するために用いるデータパスのテストプランと駆動制御信号表である。駆動制御信号表ＤＣi はそのテストプランＴi がデータパスの或る制御信号を駆動するか否かを示すものである。或る制御信号線ｃk がそのテストプランＴi で駆動される場合ＤＣi （ｃk )は１になり、それ以外の場合は０となる。具体的には、テストプランＴi の制御信号ｃk の値が０，１，ｂになる時刻が存在すれば、駆動制御信号表ＤＣi のその制御信号ｃk の値ＤＣi （ｃk )は１になる。それ以外の場合は０になる。各テストプランの駆動制御信号表中の１の数はそのテストプランが駆動する制御信号線の数に相当する。
【００７５】
【表７】
2006228238.tif 000009
【００７６】
また、テストプランＴi の密度ＤＤTiを次の様に定義する。
【００７７】
【数１】
2006228238.tif 000010
【００７８】
ただし、ｕは制御信号線の数、ｃ０k はテストプランＴi 中で制御信号ｃk に現われる値０の個数、ｃ１k はＴi 中で制御信号ｃk に現われる値１の個数、ｃｂk はＴi 中でｃk に現われるｂの個数である。δkiは０−１変数であり、以下の条件を少なくとも１つ満たせばδkiは０でありそれ以外のときは１となる。
【００７９】
（ｃ１）ｃ０k とｃｂk が共に０
（ｃ２）ｃ１k とｃｂk が共に０
（ｃ３）ｃ０k とｃ１k が０でかつｃｂk が１
テストプラン中の０，１，ｂの総数であるΣ（ｃ０k ＋ｃ１k ＋ｃｂk ）はそのテストプランに基いて出力される制御信号を生成する回路の規模に反映するものと考えられるが、上記の（ｃ１），（ｃ２），（ｃ３）の条件が成立する制御信号ｃk については値を固定して良いから回路規模に影響を及ぼさない。そこでテストプランＴi の密度ＤＤTiを計算するにあたって、その様な制御信号Ｃk についてはδkiを０にすることにより加算から除外している。テストプランＴi の密度ＤＤTiはテストプランＴi に従って制御信号を生成するデコーダの規模に反映すると考えられる。
【００８０】
テストプランのグルーピングにおいて、グループの数、すなわち各グループに属するテストプランから生成される圧縮テストプラン表の数は、図２９のＴＰＧのアーキテクチャにおけるデコーダ（Ｄｅｃｏｄｅｒ−Ｇj ）の数ｍに相当する。そこでｍを第１のパラメータとする。
【００８１】
各グループに属するテストプランの長さの総和は各グループに属するテストプランを圧縮して生成される圧縮テストプラン表の長さＧＬj に反映するものと考えられる。圧縮テストプラン表の長さＧＬj または〔ｌｏｇ2ＧＬj〕は、図２９のＴＰＧのアーキテクチャにおける各デコーダの入力信号線の数に相当する。デコーダの入力信号線数は図２９のＦＳＭの規模または面積に反映すると考えられる。そこで論理合成可能なＦＳＭの制約として、各グループに属するテストプランの長さの総和の上限値を第２のパラメータｐとする。
【００８２】
前述したように、テストプランＴi の駆動制御信号表ＤＣi 中の“１”の数はそのテストプランが駆動する制御信号線の本数に相当する。そして、各グループに属するテストプランから生成される圧縮テストプラン表に対する駆動制御信号表を作成したとすれば、それはそのグループに属するテストプランの駆動信号表ＤＣの論理和をとったものになる。圧縮テストプラン表に対する駆動制御信号表の中の１の数は、図２９におけるデコーダの出力信号線の本数ＧＮＣj に相当する。各デコーダの出力信号線の本線ＧＮＣj は図２９のＭＵＸの規模に反映すると考えられる。そこで、論理合成可能なＭＵＸの制約として、各グループに属するテストプランの駆動制御信号表ＤＣをそのグループに属するすべてのテストプランについて論理和をとったものにおける１の数（有効な制御信号の数）ＧＮＣj の上限値を第３のパラメータｑとする。
【００８３】
前述したように、テストプランＴi の密度ＤＤTiはテストプランＴi に従って制御信号を生成するデコーダの規模に反映する。そして各グループｊに属するテストプランを連結した連結テストプランＣＴj の密度ＤＤCTj は、グループｊに属するテストプランから生成された圧縮テストプラン表の密度に反映するものと考えられる。圧縮テストプラン表の密度は対応するデコーダの規模に反映するものと考えられる。そこで、論理合成可能なデコーダの制約として、グループｊに属するテストプランを連結した連結テストプランＣＴj の密度ＤＤCTj の上限値を第４のパラメータｒとする。
【００８４】
図３０は本発明の第５の実施形態に係るグルーピング処理のフローチャートである。まず、グループ数ｍの初期値、テストコントローラの面積制約、データパスのテスト長目標を設定し（Ｓ３６−１）その制約、目標値からパラメータｐ，ｑ，ｒを定め（Ｓ３６−２）、ｍ，ｐ，ｑ，ｒを制約としてテスト長を最短にするテストプランのグループ化の解を以下の表８に示す整数計画問題を解くことにより求め（Ｓ３６−３）、解が得られなければ（Ｓ３６−４）、グループ数ｍをインクリメントして（Ｓ３６−８）再度ステップＳ３６−３を実行する。解が得られたらそれに基づいて各グループの圧縮テストプラン表を生成し（Ｓ３６−５）、その圧縮テストプラン表からテスト長とテストコントローラ面積推定値を算出する（Ｓ３６−６）。具体的には、圧縮テストプラン表の長さの最大値からＦＳＭの状態数を求め、圧縮テストプラン表の長さの種類数から状態遷移数を求め、ＦＳＭ部の面積を推定する。また圧縮テストプラン表の駆動制御信号表からＭＵＸの面積を推定する。さらに、圧縮テストプラン表の密度から各Ｄｅｃｏｄｅｒ部の面積を推定する。これらからテストコントローラ面積を推定する。もし制約又はテスト長の目標値を満足しなければ（Ｓ３６−７）ｍを変更して再度Ｓ３６−２から実行する。
【００８５】
【表８】
2006228238.tif 000011
【００８６】
表８において、（３）の評価関数Ｆは各グループｊ内でテストパターン数が最大であるテストプランのテストパターン数ＭＡＸＴＰj とグループ内の他のテストプランのテストパターン数の差（ＭＡＸＴＰj −Ｎi ）にテストプランの長さＬi を乗じたものの総和である。このＦが小さい程、圧縮テストプラン表をＭＡＸＴＰj に等しい回数だけ繰り返し実行するときの無駄な部分が少ないことになるので、全体のテスト長の指標となる。
【００８７】
表７のテストプランに対して、ｍ＝３，ｑ＝５，ｒ＝２２，ｐ＝１５として、上記の評価関数Ｆを最小化する整数計画問題を解くことによって、テストプランのグルーピングを行い、その結果３つのグループＧ１（Ｔ１，Ｔ５，Ｔ８）、Ｇ２（Ｔ２）、Ｇ３（Ｔ３，Ｔ４，Ｔ６，Ｔ７）に分割される。ただし、回路要素１のテストパターン数を２０、回路要素２のテストパターン数を８、回路要素３のテストパターン数を１０、回路要素４のテストパターン数を１０、回路要素５のテストパターン数を２５、回路要素６のテストパターン数を３０、回路要素７のテストパターン数を３０、回路要素８のテストパターン数を３０とする。Ｆ＝（３０−２０）×３＋（３０−２５）×４＋（３０−１０）×４＋（３０−１０）×４））＝２１０となる。Ｓ３６−５において生成された圧縮テストプラン表を表９に示す。すべての圧縮テストプラン表の長さが８以下であるので条件を満足する。
【００８８】
【表９】
2006228238.tif 000012
【００８９】
表９の圧縮テストプラン表中の信号値を生成するテストコントローラのＴＰＧ部を図３１に示す。テスト長は３０×（４＋１）＋８×（５＋１）＋３０×（４＋１）＝３４８となる。一方、従来のテスト長のみを重視したテストプランのグルーピング方法を適用すると、３つのグループＧ１（Ｔ６，Ｔ７，Ｔ８）、Ｇ２（Ｔ１，Ｔ５）、Ｇ３（Ｔ２，Ｔ３，Ｔ４）に分割される（参考：Ｆ＝１９７．９）。表１０に３つの圧縮テストプラン表を示す。テスト長は３０×（３＋１）＋２５×（５＋１）＋１０×（６＋１）＝３４０となる。表１０の圧縮テストプラン表中の信号値を生成するテストコントローラのＴＰＧ部を図３２に示す。本発明を用いてテストプランをグルーピングすると、テスト長は若干長くなるものの、図３１と図３２の比較からテストコントローラの面積は圧倒的に小さくなる。
【００９０】
【表１０】
2006228238.tif 000013
【００９１】
以上説明したように本発明によれば、データ信号線のビット幅が均一でない場合でも適用可能となり、再収斂分岐構造を有するデータパスを効率良くテスト容易化でき、テストパターンレジスタＴＰＲのサイズの削減が可能となり、極めて大規模な回路についても実現可能なテストパターン生成回路のアーキテクチャが提供され、そのもとでテストコントローラの構成およびテスト長を最適にする、テストプランのグルーピングの最適化が可能となる。
【図面の簡単な説明】
【００９２】
【図１】本発明の第１の実施形態が適用されるデータ信号線のビット幅が不均一なデータパスの一例を示す図である。
【図２】図１のデータパスに対する制御林を示す図である。
【図３】図１のデータパスに対する観測林を示す図である。
【図４】回路要素ａｄｄに対するマーキングを説明する図である。
【図５】回路要素ｍｕｌｔｉ１に対するマーキングを説明する図である。
【図６】回路要素ｍｕｌｔｉ２に対するマーキングを説明する図である。
【図７】回路要素ＭＵＸ１に対するマーキングを説明する図である。
【図８】回路要素ＭＵＸ２に対するマーキングを説明する図である。
【図９】回路要素ｃｏｍｐに対するマーキングを説明する図である。
【図１０】仮想テストピンの割り当てを説明する図である。
【図１１】仮想テストピンが割り当てられた個所と外部入力・出力との接続を説明する図である。
【図１２】途中の信号線への接続の例を示す図である。
【図１３】本発明の第１の実施形態に係るテスト容易化設計のフローチャートである。
【図１４】本発明の第２の実施形態が適用されるデータパスの一例を示す図である。
【図１５】従来技術によるテスト容易化設計を示す図である。
【図１６】本発明の第２の実施形態に係るテスト容易化設計のフローチャートである。
【図１７】図１４のデータパスのデータ線の接続を有向グラフで表わした図である。
【図１８】再収斂分岐構造を見い出すための最初の探索を説明する図である。
【図１９】再収斂分岐構造を見い出すための２回目の探索を説明する図である。
【図２０】再収斂分岐構造を構成する複数の回路要素が１つのテスト単位階層に置換されたデータパスを示す図である。
【図２１】テスト単位階層１２２に対する右側スルー機能の実現を示す図である。
【図２２】テスト単位階層１２２に対する左側スルー機能の実現を示す図である。
【図２３】図２０の回路の観測林を示す図である。
【図２４】図２０の回路の制御林を示す図である。
【図２５】図２０の回路に対するテスト容易化設計を示す図である。
【図２６】ＧＣＤを求める回路のテスト容易化設計済みのデータパスを示す図である。
【図２７】図２６の回路にテストのための制御信号を与えるための従来技術によるテストコントローラの構成を示す図である。
【図２８】本発明の第３の実施形態に係るテストコントローラの構成を示す図である。
【図２９】本発明の第４の実施形態に係るテストパターン生成器の構成を示す図である。
【図３０】本発明の第５の実施形態に係るグルーピング決定方法のフローチャートである。
【図３１】本発明の第５の実施形態に係るグルーピングに従って設計されたテストパターン生成器を示す図である。
【図３２】従来技術によるグルーピングに従って設計されたテストパターン生成器を示す図である。
【図１】
2006228238.tif 000014
【図２】
2006228238.tif 000015
【図３】
2006228238.tif 000016
【図４】
2006228238.tif 000017
【図５】
2006228238.tif 000018
【図６】
2006228238.tif 000019
【図７】
2006228238.tif 000020
【図８】
2006228238.tif 000021
【図９】
2006228238.tif 000022
【図１０】
2006228238.tif 000023
【図１１】
2006228238.tif 000024
【図１２】
2006228238.tif 000025
【図１３】
2006228238.tif 000026
【図１４】
2006228238.tif 000027
【図１５】
2006228238.tif 000028
【図１６】
2006228238.tif 000029
【図１７】
2006228238.tif 000030
【図１８】
2006228238.tif 000031
【図１９】
2006228238.tif 000032
【図２０】
2006228238.tif 000033
【図２１】
2006228238.tif 000034
【図２２】
2006228238.tif 000035
【図２３】
2006228238.tif 000036
【図２４】
2006228238.tif 000037
【図２５】
2006228238.tif 000038
【図２６】
2006228238.tif 000039
【図２７】
2006228238.tif 000040
【図２８】
2006228238.tif 000041
【図２９】
2006228238.tif 000042
【図３０】
2006228238.tif 000043
【図３１】
2006228238.tif 000044
【図３２】
2006228238.tif 000045
【手続補正書】
【提出日】平成18年3月17日(2006.3.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データパスを構成する各回路要素について決定されたテストプランをグループ化してグループ毎に圧縮して得られた複数の圧縮テストプラン表を用いてデータパスのテスト時にデータパスの制御信号を生成するテストコントローラであって、
圧縮テストプラン表の実行開始時において、実行する圧縮テストプラン表を識別する圧縮テストプラン表識別子をデータパスの入力からロードして格納する圧縮テストプラン表ＩＤレジスタと、
回路要素のテスト時に、その回路要素の制御入力に与えるべき制御値をデータパス入力からロードして格納するテストパターンレジスタと、
圧縮テストプラン表ＩＤレジスタに格納されている圧縮テストプラン表識別子に従って決定される圧縮テストプラン表及び、テストパターンレジスタに格納されている制御値に基いてテスト時のデータパスの制御信号を生成するテストプラン生成器と、
外部からのリセット信号またはテストプラン生成器の出力に基いて、テストパターンレジスタにデータパス入力から制御値をロードさせるロード信号を生成することによって、圧縮テストプラン表の実行開始時および実行途中において制御値のロードを可能にする論理和機能とを具備するテストコントローラ。
【請求項２】
複数の圧縮テストプラン表を識別する圧縮テストプラン表識別子、および回路要素のテスト時にその回路要素の制御入力に与えるべき制御値に基いて、テスト時のデータパスの制御信号を生成するテストプラン生成器であって、
実行中の圧縮テストプラン表の時刻を示す時刻信号を出力する有限状態機械と、
複数の圧縮テストプラン表のそれぞれに対して設けられた複数のデコーダであって、各デコーダは時刻信号及び制御値に基いて、それぞれの圧縮テストプラン表におけるデータパスの制御信号を生成するものと、
前記圧縮テストプラン表識別子に基いて、複数のデコーダがそれぞれ生成する制御信号のいずれか１つを選択するセレクタとを具備するテストプラン生成器。
【請求項３】
テストコントローラ面積の制約下でデータパスのテスト長を最適化するテストプランのグループ化を決定する方法であって、
（ａ）面積の制約に関する複数の条件を定め、
（ｂ）該複数の条件のもとでテスト長を最適化する整数計画問題を解くステップを具備する方法。
【請求項４】
前記複数の条件は、グループ数がｍであるという条件、各グループに属するテストプランの長さの総和の上限がｐであるという条件、各グループに属するテストプランの駆動制御信号表の論理和における有効な制御信号の数の上限がｑであるという条件、および各グループに属するテストプランを連結した連結テストプランの密度の上限がｒであるという条件を含み、
（ｃ）ステップ（ｂ）において解が得られないときｍをインクリメントしてステップ（ｂ）を繰り返すステップをさらに具備する請求項３記載の方法。
【請求項５】
（ｄ）ステップ（ｂ）において解が得られたときで、得られた解において生成される圧縮テストプラン表から推定されるテストコントローラの面積およびテスト長が目標値を満足しないとき、ｍを変更してステップ（ｂ）を繰り返すステップをさらに具備する請求項４記載の方法。
【請求項６】
テストコントローラ面積の制約下でデータパスのテスト長を最適化するテストプランのグループ化を決定する装置であって、
面積の制約に関する複数の条件を定める手段と、
該複数の条件のもとでテスト長を最適化する整数計画問題を解く手段を具備する装置。
【請求項７】
前記複数の条件は、グループ数がｍであるという条件、各グループに属するテストプランの長さの総和の上限がｐであるという条件、各グループに属するテストプランの駆動制御信号表の論理和における有効な制御信号の数の上限がｑであるという条件、および各グループに属するテストプランを連結した連結テストプランの密度の上限がｒであるという条件を含み、
解が得られないときｍをインクリメントして前記整数計画問題を繰り返し解かせる手段をさらに具備する請求項６記載の装置。
【請求項８】
解が得られたときで、得られた解において生成される圧縮テストプラン表から推定されるテストコントローラの面積およびテスト長が目標値を満足しないとき、ｍを変更して前記整数化問題を繰り返し解かせる手段をさらに具備する請求項７記載の装置。
【請求項９】
請求項３〜５のいずれか１項記載の方法によるグループ化に従って設計されたテストパターン発生器を具備する集積回路。
【請求項１０】
請求項３〜５のいずれか１項記載の方法をコンピュータに実現させるプログラム。