(57)【要約】【課題】実動作速度機能テストにおけるテスト品質の高いテスト系列をコンパクトに生成する。【解決手段】論理合成したコントローラから組み合わせ回路を抽出し（ｓｔｅｐ１）、それに対するテストパターンを生成する（ｓｔｅｐ２）。テストパターンに対してＸ抽出を行ない（ｓｔｅｐ３）、各テストパターンをＦＳＭの状態遷移にマッピングする（ｓｔｅｐ４）。状態遷移にマッピングされた有効テストパターンが生成されたテスト系列にすべて被覆されるまで（ｓｔｅｐ５）、所定の基準に従ってテストパターンを被覆する所定長の状態遷移系列を決定してテスト系列に追加し（ｓｔｅｐ７）Ｘ抽出する操作（ｓｔｅｐ）を繰り返す。最後に、残ったテストパターンを実現する状態遷移をテスト系列に追加する（ｓｔｅｐ８）。【選択図】      図６
2004302894.tif 000002
【特許請求の範囲】
【請求項１】
ＲＴＬ回路の段階においてコントローラをテスト容易化することによる集積回路のテスト容易化設計方法であって、
コントローラを、コントローラの現在の状態を表わす疑似外部入力とコントローラ外部からの外部入力とを入力としてコントローラの次の状態を表わす疑似外部出力とコントローラ外部への外部出力とを出力する組み合わせ回路で表し、組み合わせ回路と組み合わせ回路が出力する現在の状態を保持して組み合わせ回路へ供給するレジスタによって到達可能なコントローラの状態を有効状態、到達不可能な状態を無効状態とするとき、
（ａ）組み合わせ回路をテストするための複数のテストパターンの集合であって各テストパターンが疑似外部入力と外部入力とからなるものを生成し、
（ｂ）複数のテストパターンのうち、コントローラの１つの有効状態から他の有効状態への状態遷移に対応するものを、対応する状態遷移にマッピングし、
（ｃ）状態遷移にマッピングされたすべてのテストパターンを被覆するテスト系列を決定し、
（ｄ）ステップ（ｃ）の後、状態遷移にマッピングされていないテストパターンがあれば、それを実現する状態遷移をテスト系列に追加し、
（ｅ）ステップ（ｄ）の後、テスト系列に基いてテスト容易化済みコントローラを生成するステップを具備する集積回路のテスト容易化方法。
【請求項２】
ステップ（ｃ）は、
（ｉ）ｎを所定の自然数として、コントローラの初期状態から始まり、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路をテスト系列として決定し、
（ｉｉ）決定されたテスト系列に続き、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路を決定してテスト系列に追加し、
（ｉｉｉ）  状態遷移にマッピングされたすべてのテストパターンがテスト系列に被覆されるまで、サブステップ（ｉｉ）を繰り返すサブステップを含む請求項１記載の方法。
【請求項３】
ステップ（ｃ）は、（ｉｖ）サブステップ（ｉｉｉ  ）において状態遷移にマッピングされたすべてのテストパターンがテスト系列に被覆された後、１つの有効状態から他の有効状態への状態遷移であって、テスト系列に被覆されていないものがあればそれをテスト系列に追加するサブステップをさらに含む請求項２記載の方法。
【請求項４】
（ｆ）ステップ（ａ）の後、ステップ（ｂ）の前において、テストパターンの集合を構成する複数のビットの中で、いずれの値をとっても故障検出効率に変化のないものをドントケアビットとして特定するステップをさらに具備し、
ステップ（ｃ）は、
（ｉｖ）ステップ（ｉｉ）の後、ステップ（ｉｉｉ  ）の前において、テスト系列に被覆されているテストパターンをドントケアビット特定の対象から除外した上で、テストパターンの集合に対してドントケアビットを特定するサブステップをさらに含む請求項２または３記載の方法。
【請求項５】
ＲＴＬ回路の段階においてコントローラをテスト容易化することによる集積回路のテスト容易化設計装置であって、
コントローラを、コントローラの現在の状態を表わす疑似外部入力と集積回路外部からの外部入力とを入力としてコントローラの次の状態を表わす疑似外部出力と集積回路外部への外部出力とを出力する組み合わせ回路で表し、組み合わせ回路と組み合わせ回路が出力する現在の状態を保持して組み合わせ回路へ供給するレジスタによって到達可能なコントローラの状態を有効状態、到達不可能な状態を無効状態とするとき、
組み合わせ回路をテストするための複数のテストパターンの集合であって各テストパターンが疑似外部入力と外部入力とからなるものを生成する手段と、
複数のテストパターンのうち、コントローラの１つの有効状態から他の有効状態への状態遷移に対応するものを、対応する状態遷移にマッピングする手段と、
状態遷移にマッピングされたすべてのテストパターンを被覆するテスト系列を決定する手段と、
テスト系列の決定の後、状態遷移にマッピングされていないテストパターンがあれば、それを実現する状態遷移をテスト系列に追加する手段と、
テスト系列に基いてテスト容易化済みコントローラを生成する手段とを具備する集積回路のテスト容易化装置。
【請求項６】
テスト系列決定手段は、
ｎを所定の自然数として、コントローラの初期状態から始まり、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路をテスト系列として決定する手段と、
決定されたテスト系列に続き、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路を決定してテスト系列に追加する手段と、
状態遷移にマッピングされたすべてのテストパターンがテスト系列に被覆されるまで、テスト系列の追加を繰り返す手段とを含む請求項４記載の装置。
【請求項７】
テスト系列決定手段は、状態遷移にマッピングされたすべてのテストパターンがテスト系列に被覆された後、１つの有効状態から他の有効状態への状態遷移であって、テスト系列に被覆されていないものがあればそれをテスト系列に追加する手段をさらに含む請求項６記載の装置。
【請求項８】
テストパターン集合の生成の後、テストパターンのマッピングの前において、テストパターンの集合を構成する複数のビットの中で、いずれの値をとっても故障検出効率に変化のないものをドントケアビットとして特定する手段をさらに具備し、
テスト系列決定手段は、
テスト系列の追加の後、次の繰り返しの前において、テスト系列に被覆されているテストパターンをドントケアビット特定の対象から除外した上で、テストパターンの集合に対してドントケアビットを特定する手段をさらに含む請求項５記載の装置。
【請求項９】
請求項１〜４のいずれかに記載の方法をコンピュータに実現させるプログラム。
【請求項１０】
請求項１〜４のいずれか記載の方法により生成されたテスト容易化済みコントローラを具備する集積回路。
【請求項１１】
テスト容易化済みコントローラへ与える前記テスト系列を生成するテストパターン発生器と、テスト系列が与えられたコントローラの応答を符号化する符号化ユニットとをさらに具備する請求項１０記載の集積回路。
【請求項１２】
コントローラの組み合わせ回路をテストする複数のテストパターンを生成し、複数のテストパターンの各々をコントローラの有効状態または無効状態にマッピングし、マッピング結果に基いてテスト容易化済みコントローラおよびテスト系列を生成する方法により生成されたテスト容易化済みコントローラと、該テスト系列を生成するテストパターン発生器と、テスト系列が与えられたコントローラの応答を符号化する符号化ユニットとを具備する集積回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＲＴＬ回路の段階においてＲＴＬ回路に含まれるコントローラをテスト容易化する集積回路の非スキャンテスト容易化設計に関する。
【０００２】
半導体回路または半導体回路を構成するコアの設計工程において、ゲートレベル回路に変換する前の段階においては、ＲＴＬ回路はデータを処理するデータパスとデータパスの動作を制御するコントローラとから構成される。本明細書では、このコントローラの非スキャンテスト容易化設計に言及する。
【０００３】
【従来の技術】
下記非特許文献１および特許文献１には、ＲＴＬ回路に含まれるコントローラの非スキャンテスト容易化に適用可能なテスト容易化設計の手法が開示されている。
【０００４】
コントローラは、レジスタ転送レベルでは図１に示されるように有限状態機械（ＦＳＭ：Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）として記述される。ＦＳＭの各状態ｓｉ  に状態レジスタの実際の値をそれぞれ割り当てて論理合成を行なって、図２に示すような、状態レジスタＳＲと組み合わせ論理回路ＣＣとからなる順序回路を得る。上記論文に開示された手法においては、まず、図３に示すように、状態レジスタＳＲを状態レジスタＳＲの出力である現状態ＰＳに相当する疑似外部入力ＰＰＩと状態レジスタＳＲの入力である次状態ＮＳに相当する疑似外部出力ＰＰＯで置き換えて組み合わせテスト生成モデルを生成し、組み合わせ回路ＣＣに周知の組み合わせテスト生成アルゴリズムを適用してテスト生成を行なってテストパターンの集合を得る。
【０００５】
生成された各テストパターンを構成する外部入力ＰＩと疑似外部入力ＰＰＩのうち、外部入力ＰＩは集積回路の外部から与え、疑似外部入力ＰＰＩは内部的に生成する。各テストパターンに含まれるＰＰＩのうち図１の状態ｓ０  〜ｓ６  （有効状態と呼ばれる）のいずれかに相当するものはコントローラ本来の機能によりリセット状態Ｓ０  から順次状態遷移させてそれぞれの状態に到達させることにより実現可能であり、これらは有効テスト状態と呼ばれる。一方、これらｓ０  〜ｓ６  とは異なる状態（無効状態と呼ばれる）のうち、生成されたテストパターンに含まれる疑似外部入力ＰＰＩに相当する状態ｉｓ１  〜ｉｓ５  （無効テスト状態と呼ばれる）が存在すればそれらはコントローラ本来の機能で実現できないので、テスト容易化のために回路を付加して実現しなければならない。
【０００６】
そこで、図４に示すように、状態遷移モード切換信号ｔが１のときにリセット状態ｓ０  からすべての無効テスト状態ｉｓ１  〜ｉｓ５  を通る経路が追加され、図５に示すように、この遷移を実現するための無効テスト状態生成論理ＩＳＧとマルチプレクサＭＵＸが追加される。テストパターン集合の中には、ＰＩの値が異なっていてもＰＰＩの値が同じであるものが通常含まれているので、これらを効率良く実現するため、レジスタＳＲにはホールド信号Ｈが追加される。ＰＰＩの値が同じテストパターンを印加するときは、ホールド信号ＨによりレジスタＳＲをホールドする間に異なるＰＩの値が印加される。そして、すべての有効テスト状態を通る最短の状態遷移系列を求め、ｔ＝０としてこれを順次印加して状態遷移させ、必要に応じてホールドすることにより有効テスト状態に属するすべてのテストパターンを印加し、さらにｔ＝１として図４の経路に沿って遷移させ必要に応じてホールドすることにより無効テスト状態に属するすべてのテストパターンを印加する。テストパターンの印加と同時に、テスト用にｔ＿ｏｕｔとして引き出されたＭＵＸの出力を用いて疑似外部出力ＰＰＯへ伝播してきた出力を観測することで故障の観測が行なわれる。
【０００７】
【特許文献１】
特許第３２４３２０７号
【非特許文献１】
大竹哲史他「完全故障検出効率を保証するコントローラの非スキャンテスト容易化設計法」、電子情報通信学会論文誌Ｄ−１  Ｖｏｌ．Ｊ８１−Ｄ−Ｉ，  Ｎ          Ｏ．１２，  ｐｐ．１２５９−１２７０、１９９８年１２月
【非特許文献２】
Ｓ．  Ｋａｊｉｈａｒａ  ａｎｄ  Ｋ．  Ｍｉｙａｓｅ，“Ｏｎ  Ｉｄｅｎｔｉｆｙｉｎｇ  Ｄｏｎ’ｔ  Ｃａｒｅ  Ｉｎｐｕｔｓ  ｏ          ｆ  Ｔｅｓｔ  Ｐａｔｔｅｒｎｓ  ｆｏｒ  Ｃｏｍｂｉｎａｔｉｏｎａｌ  Ｃｉｒｃｕｉｔｓ，”Ｐｒｏｃ．  ｏｆ  Ｉｎｔ’ｌ  Ｃｏ          ｎｆ．  ｏｆ  ＣＡＤ，  ｐｐ．３６４−３６９，  ２００１
【非特許文献３】
Ｋ．  Ｍｉｙａｓｅ  ｅｔ  ａｌ．，“Ｄｏｎ’ｔ−Ｃａｒｅ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｏｎ  Ｓｐｅｃｉｆｉｃ  Ｂｉｔｓ            ｏｆ  Ｔｅｓｔ  Ｐａｔｔｅｒｎｓ”，  ＩＣＣＤ，  ２００２
【非特許文献４】
Ｋ．  Ｙａｍａｇｕｃｈｉ  ｅｔ  ａｌ．，“Ｈｉｅｒａｒｃｈｉｃａｌ  ＢＩＳＴ：  Ｔｅｓｔ−Ｐｅｒ−Ｃｌｏｃｋ  ＢＩＳＴ  ｗ          ｉｔｈ  Ｌｏｗ  Ｏｖｅｒｈｅａｄ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ３ｒｄ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ＲＴＬ  ａｎｄ  Ｈｉｇ          ｈ  Ｌｅｖｅｌ  Ｔｅｓｔｉｎｇ，  ｐｐ．４２−４７
【非特許文献５】
Ｔ．  Ｈｏｓｏｋａｗａ，  ｅｔ  ａｌ．，“Ａ  Ｓｔａｔｅ  Ｒｅｄｕｃｔｉｏｎ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｎｏｎ−ｓｃａｎ  Ｂａ          ｓｅｄ  ＦＳＭ  Ｔｅｓｔｉｎｇ  ｗｉｔｈ  Ｄｏｎ’ｔ  Ｃａｒｅ  Ｉｎｐｕｔｓ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｔｅｃｈｎｉｑｕ          ｅ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｅｌｅｖｅｎｔｈ  Ａｓｉａｎ  Ｔｅｓｔ  Ｓｙｍｐｏｓｉｕｍ，  ｐｐ．５５−６          ０
【０００８】
【発明が解決しようとする課題】
コントローラの組み合わせ論理部ＣＣにテストパターンを実動作速度で与えるだけでなく、同時に、状態から状態への状態遷移を実動作速度で動作させることができれば実動作速度における機能テストの品質が向上する。
【０００９】
上記論文に記載された手法においては、各テストパターンをコントローラの「状態」にマッピングし、コントローラ本来の機能を利用してテストパターンを生成している。したがって、異なる状態にマッピングされたテストパターンへ移る際には状態遷移を動作させることになる。しかしながら、テスト長をできるだけ短かくするため、同一の状態にマッピングされたテストパターンの生成にあたっては状態レジスタＳＲをホールドしてテストパターンを生成しているので、全体として状態遷移を動作させる割合が低いという問題がある。
【００１０】
したがって本発明の目的は、コントローラの組み合わせ論理部を完全故障検出効率でテストすることが可能で、コントローラの状態遷移を被覆する割合が高く、かつ、可能な限りコンパクトなテスト系列を与えるテスト容易化設計方法を提供することにある。
【００１１】
【課題を解決するための手段】
本発明によれば、ＲＴＬ回路の段階においてコントローラをテスト容易化することによる集積回路のテスト容易化設計方法であって、コントローラを、コントローラの現在の状態を表わす疑似外部入力とコントローラ外部からの外部入力とを入力としてコントローラの次の状態を表わす疑似外部出力とコントローラ外部への外部出力とを出力する組み合わせ回路で表し、組み合わせ回路と組み合わせ回路が出力する現在の状態を保持して組み合わせ回路へ供給するレジスタによって到達可能なコントローラの状態を有効状態、到達不可能な状態を無効状態とするとき、（ａ）組み合わせ回路をテストするための複数のテストパターンの集合であって各テストパターンが疑似外部入力と外部入力とからなるものを生成し、（ｂ）複数のテストパターンのうち、コントローラの１つの有効状態から他の有効状態への状態遷移に対応するものを、対応する状態遷移にマッピングし、（ｃ）状態遷移にマッピングされたすべてのテストパターンを被覆するテスト系列を決定し、（ｄ）ステップ（ｃ）の後、状態遷移にマッピングされていないテストパターンがあれば、それを実現する状態遷移をテスト系列に追加し、（ｅ）ステップ（ｄ）の後、テスト系列に基いてテスト容易化済みコントローラを生成するステップを具備する集積回路のテスト容易化方法が提供される。
【００１２】
ステップ（ｃ）は、（ｉ）ｎを所定の自然数として、コントローラの初期状態から始まり、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路をテスト系列として決定し、（ｉｉ）決定されたテスト系列に続き、状態遷移にマッピングされたテストパターンを被覆する長さｎの経路を決定してテスト系列に追加し、（ｉｉｉ  ）状態遷移にマッピングされたすべてのテストパターンがテスト系列に被覆されるまで、サブステップ（ｉｉ）を繰り返すサブステップを含むことが好ましい。
【００１３】
前述の方法は、ステップ（ａ）の後、ステップ（ｂ）の前において、テストパターンの集合を構成する複数のビットの中で、いずれの値をとっても故障検出効率に変化のないものをドントケアビットとして特定するステップをさらに具備し、ステップ（ｃ）は、（ｉｖ）ステップ（ｉｉ）の後、ステップ（ｉｉｉ  ）の前において、テスト系列に被覆されているテストパターンをドントケアビット特定の対象から除外した上で、テストパターンの集合に対してドントケアビットを特定するサブステップをさらに含むことがさらに好ましい。
【００１４】
本発明によれば上記手法により生成されたテスト容易化済みコントローラを具備する集積回路もまた提供される。
【００１５】
【発明の実施の形態】
図６は本発明で提案する品質の高い実動作速度機能テストを行うための、テスト生成方法のフローチャートである。テスト容易化回路は図７に示したようになる。図５と比較すると、レジスタＳＲにホールド信号が供給されないのが注目される。
【００１６】
図６において、Ｓｔｅｐ１はＦＳＭを論理合成し、その組合せ回路部を抽出するステップである。抽出した組合せ回路を組合せテスト生成モデルとする。Ｓｔｅｐ２は組合せテスト生成モデルに対して、単一縮退故障を仮定してテスト生成を行うステップである。Ｓｔｅｐ３は生成したテストパターンに対して、前記非特許文献２および３に記載された手法により、ドントケア（Ｘ）抽出を行うステップである。Ｓｔｅｐ４はＦＳＭの状態遷移に対応するテストパターンをマッピングし、有向グラフで構成されるＦＳＭテスト生成グラフを生成するステップである。以下、状態遷移にマッピングされたテストパターンを有効テストパターンと呼ぶ。Ｓｔｅｐ５は、生成したＦＳＭのテスト系列による状態遷移がすべての有効テストパターンを被覆しているか否かを判断するステップである。すべての有効テストパターンを被覆している場合、Ｓｔｅｐ８へ進み、それ以外の場合はＳｔｅｐ６へ進む。Ｓｔｅｐ６は深さｎ（自然数）の状態遷移を探索し、有効テストパターンを最も多く被覆する状態遷移経路を選択する処理である。すなわち長さｎのテスト系列を生成する。経路選択後、状態遷移にマッピングされている被覆された有効テストパターンを削除し、ＦＳＭテスト生成グラフを更新する。Ｓｔｅｐ７はテスト系列に被覆されたテストパターンはＸ抽出の対象としない条件付Ｘ抽出を行うステップである。Ｘ抽出後、再度有効テストパターンをＦＳＭの状態遷移にマッピングし直し、ＦＳＭテスト生成グラフを更新する。Ｓｔｅｐ８は、生成したテスト系列がすべての有効テストパターンを被覆した後で、最終的にＦＳＭの状態遷移にマッピングできなかったテストパターンを無効テストパターンとし、その無効テスト状態をＦＳＭの状態遷移に追加し、図７に示したテスト機能をＦＳＭに挿入するステップである。
【００１７】
図８は本発明の実施例を説明するために用いる２入力６状態のＦＳＭである。図８において、頂点Ｓ０〜Ｓ５は有効状態（特にＳ０はリセット状態）であり、ＦＳＭの入力が状態遷移の辺上に示した値であれば、次のクロックで状態遷移先に遷移することを示す。Ｓ０〜Ｓ５の下に示した符号はエンコードされた状態値を示す。
【００１８】
図９はＳｔｅｐ３のＸ抽出の例を示している。Ｔ１はＳｔｅｐ１，Ｓｔｅｐ２の処理の後、ＦＳＭの組合せテスト生成モデルに対して生成されたテストパターン集合である。Ｔ２はＸ抽出後のテストパターン集合である。図中、テストパターンのビットの並びは（ＰＩ１，ＰＩ２，ＰＰＩ１，ＰＰＩ２，ＰＰＩ３）である。
【００１９】
図１０はＳｔｅｐ４でＴ２の有効テストパターンを図８のＦＳＭの状態遷移にマッピングした結果を示す。例えば、ｔ４＝（１０１０１）であるので、状態１０１（Ｓ５）から入力条件１０で状態遷移する状態遷移上にマッピングされている。またｔ１０＝（０１００Ｘ）であるので、状態０００（Ｓ０）から入力条件０１で状態遷移する状態遷移上と、状態００１（Ｓ１）から入力条件ＸＸで状態遷移する状態遷移上にマッピングされている。Ｓ１からの状態遷移は入力が何であってもＳ２に遷移するので、ｔ１は入力値がＸ０に相当し、ｔ１０は入力値が０１に相当することを表すために（  ）に入力値が記述されている。Ｓ４からＳ５への状態遷移にマッピングされているｔ８，ｔ１１、Ｓ２からＳ４への状態遷移にマッピングされているｔ１２も同様である。
【００２０】
図１１は図１０からテスト系列を生成するために作られたＦＳＭテスト生成グラフ（有向グラフ）である。ＦＳＭテスト生成グラフにおいて、頂点は状態を表し、頂点の重みｗ５はテスト系列をＦＳＭに印加した時に、各頂点を通る回数を表す（ｗ５→Ｚ＋（非負の整数））。枝は状態遷移を表し、枝の重みｗ１〜ｗ４の意味は以下のとおりである。
【００２１】
・ｗ１→｛０，１｝：１は枝にテスト系列に被覆されていない有効テストパターンが存在することを表す。それ以外のときは０となる。
【００２２】
・ｗ２→Ｒ＋（非負の実数）：テスト系列に被覆されていないかつ、枝にマッピングされているテストパターン数を表す。ただしテストパターンｔがｍ個の枝にマッピングされている時、その枝にマッピングされているテストパターンｔは１／ｍ個と数える。
【００２３】
・ｗ３→｛０，１｝：１はテスト系列によって、その枝に対する状態遷移を行ったことを示す。それ以外のときは０である。
【００２４】
・ｗ４→Ｚ＋（非負の整数）：その枝に対する状態遷移の条件となる入力の組合せで、テスト系列にない組合せ数を示す。
【００２５】
例えば、Ｓ０からＳ５への枝には重み（１，０．５，０，１）が割り付けられている。ｗ１＝１は、この枝にテスト系列に被覆されていないテストパターンｔ１１がマッピングされていることを示す。ｗ２＝０．５はｔ１１がＳ４からＳ５への枝にもマッピングされているので１／２、すなわち０．５となる。ｗ３＝０はまだこの枝、すなわち状態遷移はテスト系列によって行われていないことを示す。ｗ４＝１はこの枝に対する状態遷移は入力組み合わせ（１１）のとき、実行されるが、まだテスト系列にこの状態遷移を起こした履歴がないので、１となる。
【００２６】
まだ、テスト系列は生成されていないので、Ｓｔｅｐ５ですべての有効テストパターンはテスト系列に被覆されていないと判断される。
【００２７】
Ｓｔｅｐ６で、図１１のＦＳＭテスト生成グラフに対してｎ状態遷移系列を探索する（ｎ＝３）。図１２に、リセット状態Ｓ０から３状態遷移を起こす状態遷移系列をすべて探索した結果を示す。太線は結果として選択された状態遷移経路を示す。状態遷移経路の選択基準は以下の通りである。探索した状態遷移経路数をｍ、枝の数をＮｅ、超点数Ｎｖとする。また状態遷移経路ｐに枝ｅが存在するか否かを示す関数としてＲｅ（ｐ，ｅ）∈｛０，１｝を用いる。ｐにｅが含まれるならばＲｅ（ｐ，ｅ）＝１となり、それ以外のときはＲｅ（ｐ，ｅ）＝０となる。同様に状態遷移経路ｐに頂点ｖが存在するか否かを示す関数Ｒｖ（ｐ，ｖ）∈｛０，１｝を用いる。ｐにｖが含まれるならばＲｖ（ｐ，ｖ）＝１となり、それ以外のときはＲｖ（ｐ，ｖ）＝０となる。
【００２８】
【数１】
2004302894.tif 000003
【００２９】
優先度１〜２はできるだけ多数の有効テストパターンが被覆されるためのヒューリスティックである。テスト長を短くすることが目的である。優先度３〜５は、テスト系列による状態遷移の被覆率、すなわち実動作速度機能テストの品質を向上させるためのヒューリスティックである。上記に示した優先度１〜５は、一例として１→２→…５の順に適用されるが、他の順序で適用しても良い。
【００３０】
図１２ではＳ０→Ｓ０→Ｓ１→（Ｓ２）の状態遷移経路が優先度１，２の計算結果から一意に選択される。テスト系列（００，０１，００）が生成される。３番目の系列はｔ１を被覆するように決定した。結果として、このテスト系列により、｛ｔ６，ｔ１０，ｔ１｝が被覆された。図１３はこのテスト系列により被覆されたテストパターンをＦＳＭの状態遷移のマッピングから削除したものである。またテスト系列によって状態遷移が行われた部分を太線で示している。図１４は図１３の処理を反映したＦＳＭテスト生成グラフである。
【００３１】
次にＳｔｅｐ７において条件付Ｘ抽出が実行される。図１５に示すように、前回のｎ状態遷移経路探索の結果、生成されたテスト系列で被覆された有効テストパターンをＸ抽出の対象からはずして、Ｔ２′のＸ抽出を行っている。Ｔ２′はｔ１とｔ１０のＸの部分を実際のテスト系列によって組合せ回路部分に印加される値に置き換えたテストパターン集合である。Ｘ抽出ビットでＦに相当するテストパターンのビットはＸ抽出を行わないことを示す。またＸ抽出ビットでＸに相当するテストパターンのビットはＸ抽出を行うことを示す。今回は、この処理によってＸは増えなかった。
【００３２】
図１３に示すように、Ｓｔｅｐ５でまだテスト系列ですべての有効テストパターンが被覆されていないと判断され、Ｓｔｅｐ６へ進む。
【００３３】
Ｓｔｅｐ６で、図１４のＦＳＭテスト生成グラフに対してｎ状態遷移系列を探索する（ｎ＝３）。図１６に、状態Ｓ２から３状態遷移を起こす状態遷移系列をすべて探索した結果を示す。太線は結果として選択された状態遷移経路を示す。図１６ではＳ２→Ｓ４→Ｓ５→（Ｓ３）の状態遷移経路が優先度１，２，３，４，５の計算結果から一意に選択される。テスト系列（１０，００，００）が生成される。１番目、２番目の系列はそれぞれｔ１２，ｔ８を被覆するように決定した。結果として、このテスト系列により、｛ｔ１２，ｔ８，ｔ２｝が被覆された。図１７はこのテスト系列により被覆されたテストパターンをＦＳＭの状態遷移のマッピングから削除したものである。またテスト系列によって状態遷移が行われた部分を太線で示している。図１８は図１７の処理を反映したＦＳＭテスト生成グラフである。
【００３４】
次にＳｔｅｐ７において条件付Ｘ抽出が実行される。図１９に示すように、前回のｎ状態遷移経路探索の結果、生成されたテスト系列で被覆された有効テストパターンをＸ抽出の対象からはずして、Ｔ２″のＸ抽出を行っている。Ｔ２″はｔ８のＸの部分を実際のテスト系列によって組合せ回路部分に印加される値に置き換えたテストパターン集合である。今回は、この処理によってｔ１３のＰＰＩ１の値がＸとなった。よって、新たなテストパターン集合としてＴ３とする。これにより、ｔ１３は無効テストパターンから有効テストパターンに変化した。図２０は新たに生じた有効テストパターンｔ１３をＳ４からＳ３への状態遷移にマッピングしたものである。図２１は図２０の処理を反映したＦＳＭテスト生成グラフである。
【００３５】
図２０に示すように、Ｓｔｅｐ５でまだテスト系列ですべての有効テストパターンが被覆されていないと判断され、Ｓｔｅｐ６へ進む。
【００３６】
Ｓｔｅｐ６で、図２１のＦＳＭテスト生成グラフに対してｎ状態遷移系列を探索する（ｎ＝３）。図２２に、状態Ｓ３から３状態遷移を起こす状態遷移系列をすべて探索した結果を示す。太線は結果として選択された状態遷移経路を示す。図２２ではＳ３→Ｓ２→Ｓ５→（Ｓ０）の状態遷移経路が優先度１の計算結果から一意に選択される。テスト系列（１０，０１，１０）が生成される。結果として、このテスト系列により、｛ｔ７，ｔ４｝が被覆された。図２３はこのテスト系列により被覆されたテストパターンをＦＳＭの状態遷移のマッピングから削除したものである。またテスト系列によって状態遷移が行われた部分を太線で示している。図２４は図２３の処理を反映したＦＳＭテスト生成グラフである。
【００３７】
次にＳｔｅｐ７において条件付Ｘ抽出が実行される。図２５に示すように、前回のｎ状態遷移経路探索の結果、生成されたテスト系列で被覆された有効テストパターンをＸ抽出の対象からはずして、Ｔ３′のＸ抽出を行っている。Ｔ３′はＳ３からＳ２への状態遷移によって得られた新しいテストパターンｔ１４＝（１，０，０，１，１）をＴ３に加えたテストパターン集合である。今回は、この処理によってｔ５のすべての値がＸとなった。ｔ５は不要なテストパターンと判断される。図２６は不要となった有効テストパターンｔ５に対するＳ５からＳ１への状態遷移のマッピングを削除したものである。図２７は図２６の処理を反映したＦＳＭテスト生成グラフである。
【００３８】
図２６に示すように、Ｓｔｅｐ５でまだテスト系列ですべての有効テストパターンが被覆されていないと判断され、Ｓｔｅｐ６へ進む。
【００３９】
Ｓｔｅｐ６で、図２７のＦＳＭテスト生成グラフに対してｎ状態遷移系列を探索する（ｎ＝３）。図２８に、状態Ｓ０から３状態遷移を起こす状態遷移系列をすべて探索した結果を示す。太線は結果として選択された状態遷移経路を示す。図２８ではＳ０→Ｓ５→Ｓ４→（Ｓ３）の状態遷移経路が優先度１の計算結果から一意に選択される。テスト系列（１１，１１，０１）が生成される。結果として、このテスト系列により、｛ｔ１１，ｔ１３｝が被覆された。図２９はこのテスト系列により被覆されたテストパターンをＦＳＭの状態遷移のマッピングから削除したものである。またテスト系列によって状態遷移が行われた部分を太線で示している。図３０は図２９の処理を反映したＦＳＭテスト生成グラフである。
【００４０】
次にＳｔｅｐ７において条件付Ｘ抽出が実行される。図３１に示すように、前回のｎ状態遷移経路探索の結果、生成されたテスト系列で被覆された有効テストパターンをＸ抽出の対象からはずして、Ｔ４′のＸ抽出を行っている。Ｔ４′はｔ１１とｔ１３のＸの部分を実際のテスト系列によって組合せ回路部分に印加される値に置き換えたテストパターン集合である。今回は、この処理によってＸは増えなかった。
【００４１】
図２９に示すように、Ｓｔｅｐ５でまだテスト系列ですべての有効テストパターンが被覆されていないと判断され、Ｓｔｅｐ６へ進む。
【００４２】
Ｓｔｅｐ６で、図３０のＦＳＭテスト生成グラフに対してｎ状態遷移系列を探索する（ｎ＝３）。図３２に、状態Ｓ３から３状態遷移を起こす状態遷移系列をすべて探索した結果を示す。太線は結果として選択された状態遷移経路を示す。図３２ではＳ３→Ｓ４→Ｓ１→（Ｓ２）の状態遷移経路が優先度１の計算結果から一意に選択される。テスト系列（０１，１０，１０）が生成される。結果として、このテスト系列により、｛ｔ９｝が被覆された。図３３はこのテスト系列により被覆されたテストパターンをＦＳＭの状態遷移のマッピングから削除したものである。またテスト系列によって状態遷移が行われた部分を太線で示している。
【００４３】
次にＳｔｅｐ７において条件付Ｘ抽出が実行される。図３４に示すように、前回のｎ状態遷移経路探索の結果、生成されたテスト系列で被覆された有効テストパターンをＸ抽出の対象からはずして、Ｔ４″のＸ抽出を行っている。Ｔ４″はＳ３からＳ４への状態遷移、Ｓ１からＳ２への状態遷移によって得られた新しいテストパターンｔ１６＝（０，１，０，１，１），ｔ１７＝（１０００１）をＴ４′に加えたテストパターン集合である。今回は、この処理によってＴ４″のＸの数は増加しなかった。
【００４４】
図３３に示すように、Ｓｔｅｐ５でテスト系列ですべての有効テストパターンが被覆されたと判断され、Ｓｔｅｐ８へ進む。
【００４５】
Ｓｔｅｐ８で、ｔ３＝（０１１１Ｘ）は無効テストパターンと判断され、無効状態１１ＸがＦＳＭに追加される。このとき、残った無効テストパターンに対応する無効状態が複数存在するときは、無効テストパターン数が多い無効状態をリセット状態により近く配置することが望ましい。
【００４６】
以上の処理により、単一縮退故障の故障検出効率が１００％のテスト系列は図３５のようになり、そのテスト長は１６となった。またＦＳＭの全状態遷移数１８のうち、生成したテスト系列で１４の状態遷移を実行させることができた。状態遷移の被覆率１４／１８＝７７．７８％となり（図３３参照）、実動作速度機能テストの品質を改善することができた。前述の従来技術における状態遷移の被覆率は４／１８＝２２．２％である（図３６参照）。追加した無効テスト状態数も１と従来技術における方法の追加無効テスト状態数２を削除することができた。
【００４７】
上記の例では、Ｓｔｅｐ５ですべての有効テストパターンがテスト系列に被覆されたと判断されたらＳｔｅｐ８へ進んでいるが、ＦＳＭの状態遷移のうちテスト系列に被覆されていないものが残っていればそれをテスト系列に追加した後Ｓｔｅｐ８へ進むようにすれば、被覆率を１００％とすることができる。
【００４８】
以上の処理はコンピュータに上記の処理を実行させるソフトウェアにより実現することができる。
【００４９】
図７に示したテスト容易化済みコントローラは、ＰＩのパターンを外部から与え、ＰＯの出力を外部で判定する外部テスト方式の構成のものである。図７の回路に、上記の処理で決定されたテスト系列を順次発生するテストパターン発生器と出力ＰＯおよび疑似外部出力ＰＰＯの結果を符号化するＭＩＳＲ（Ｍｕｌｔｉｐｌｅ  Ｉｎｐｕｔ  Ｓｉｇｎａｔｕｒｅ  Ｒｅｇｉｓｔｅｒ）を付加してＢＩＳＴ（Ｂｕｉｌｔ−ｉｎ  Ｌｏｇｉｃ  Ｂｌｏｃｋ  Ｏｂｓｅｒｖｅｒ）構成とすることができる。図３７には、前述の例において、テスト容易化済みコントローラをＢＩＳＴ方式とした例を示す。テストパターン発生器１０はリセット信号（Ｒ）が入力された後、図３５のテストパターンを順次出力する。信号Ｂが“１”であるときテストパターン発生器１０が出力するＰＩがセレクタ１２で選択されて組み合わせ回路１８へ印加され、テストパターン発生器１０が出力する信号Ｒがセレクタ１４で選択されて状態レジスタ１６のリセット端子へ印加される。ＲＡ２０は、２ビットのＰＯ出力および３ビットのＰＰＯ出力を符号化する。
【００５０】
組み合わせ回路のテストパターンをＦＳＭの有効状態および無効状態にマッピングし、同一の状態に属するテストパターンについては状態レジスタをホールドしてテストパターンを発生する従来技術についても同様に、図３８に示すようにＢＩＳＴ構成とすることができる。図３７との回路構成上の相違は状態レジスタのホールド信号がパターン発生器から与えられる点のみである。
【００５１】
【発明の効果】
以上説明したように本発明によれば、コントローラの組み合わせ論理部を完全故障検出効率でテストすることが可能で、コントローラの状態遷移を被覆する割合が高く、かつ、可能な限りコンパクトなテスト系列およびテスト容易化済みコントローラが得られる。
【図面の簡単な説明】
【図１】ＦＳＭとして記述されたコントローラの図である。
【図２】順序回路として表わしたコントローラの図である。
【図３】図２の回路から生成された組み合わせテスト生成モデルの図である。
【図４】無効テスト状態を実現する状態遷移を示す図である。
【図５】従来技術におけるテスト容易化済みのコントローラを示す図である。
【図６】本発明の一実施形態に係るテスト生成方法のフローチャートである。
【図７】本発明の一実施形態に係るテスト容易化済みコントローラの構成を示すブロック図である。
【図８】ＦＳＭとして示したコントローラの一例を示す図である。
【図９】図８のコントローラについて生成されたテストパターンに対する最初のＸ抽出を示す図である。
【図１０】最初のＸ抽出後の有効テストパターンをＦＳＭの状態遷移にマッピングした結果を示す図である。
【図１１】図１０から得られたＦＳＭテスト生成グラフを示す図である。
【図１２】図１１のＦＳＭテスト生成グラフに対する３状態遷移系列の探索結果と長さ３の経路選択結果を示す図である。
【図１３】テスト系列に被覆されたテストパターンを削除した後の状態遷移マッピングを示す図である。
【図１４】図１３から得られたＦＳＭテスト生成グラフを示す図である。
【図１５】２回目のＸ抽出処理を示す図である。
【図１６】図１４のＦＳＭテスト生成グラフに対する３状態遷移系列の探索結果と長さ３の経路選択結果を示す図である。
【図１７】テスト系列に被覆されたテストパターンを削除した後の状態遷移マッピングを示す図である。
【図１８】図１７から得られたＦＳＭテスト生成グラフを示す図である。
【図１９】３回目のＸ抽出処理を示す図である。
【図２０】３回目のＸ抽出後の状態遷移マッピングを示す図である。
【図２１】図２０から得られたＦＳＭテスト生成グラフを示す図である。
【図２２】図２１のＦＳＭテスト生成グラフに対する３状態遷移系列の探索結果と長さ３の経路選択結果を示す図である。
【図２３】テスト系列に被覆されたテストパターンを削除した後の状態遷移マッピングを示す図である。
【図２４】図２３から得られたＦＳＭテスト生成グラフを示す図である。
【図２５】４回目のＸ抽出処理を示す図である。
【図２６】４回目のＸ抽出後の状態遷移マッピングを示す図である。
【図２７】図２６から得られたＦＳＭテスト生成グラフを示す図である。
【図２８】図２７のＦＳＭテスト生成グラフに対する３状態遷移系列の探索結果と長さ３の経路選択結果を示す図である。
【図２９】テスト系列に被覆されたテストパターンを削除した後の状態遷移マッピングを示す図である。
【図３０】図２９から得られたＦＳＭテスト生成グラフを示す図である。
【図３１】５回目のＸ抽出処理を示す図である。
【図３２】図３０のＦＳＭテスト生成グラフに対する３状態遷移系列の探索結果と長さ３の経路選択結果を示す図である。
【図３３】テスト系列に被覆されたテストパターンを削除した後の状態遷移マッピングを示す図である。
【図３４】６回目のＸ抽出処理を示す図である。
【図３５】最終的に生成されたテスト系列を示す図である。
【図３６】従来技術により生成されたテスト系列における状態遷移の被覆割合を示す図である。
【図３７】ＢＩＳＴ方式で実現した本発明の一実施例に係るテスト容易化済みコントローラを示す図である。
【図３８】従来技術により生成されたテスト系列に基づくＢＩＳＴ方式で実現されたテスト容易化済みコントローラの例を示す図である。
【図１】
2004302894.tif 000004
【図２】
2004302894.tif 000005
【図３】
2004302894.tif 000006
【図４】
2004302894.tif 000007
【図５】
2004302894.tif 000008
【図６】
2004302894.tif 000009
【図７】
2004302894.tif 000010
【図８】
2004302894.tif 000011
【図９】
2004302894.tif 000012
【図１０】
2004302894.tif 000013
【図１１】
2004302894.tif 000014
【図１２】
2004302894.tif 000015
【図１３】
2004302894.tif 000016
【図１４】
2004302894.tif 000017
【図１５】
2004302894.tif 000018
【図１６】
2004302894.tif 000019
【図１７】
2004302894.tif 000020
【図１８】
2004302894.tif 000021
【図１９】
2004302894.tif 000022
【図２０】
2004302894.tif 000023
【図２１】
2004302894.tif 000024
【図２２】
2004302894.tif 000025
【図２３】
2004302894.tif 000026
【図２４】
2004302894.tif 000027
【図２５】
2004302894.tif 000028
【図２６】
2004302894.tif 000029
【図２７】
2004302894.tif 000030
【図２８】
2004302894.tif 000031
【図２９】
2004302894.tif 000032
【図３０】
2004302894.tif 000033
【図３１】
2004302894.tif 000034
【図３２】
2004302894.tif 000035
【図３３】
2004302894.tif 000036
【図３４】
2004302894.tif 000037
【図３５】
2004302894.tif 000038
【図３６】
2004302894.tif 000039
【図３７】
2004302894.tif 000040
【図３８】
2004302894.tif 000041