(57)【要約】【課題】スキャンテストにおいて、故障の検出率を向上し、テスト時間を短縮することができるようにする。【解決手段】回路構築装置は、ＡＮＤゲート９１に着目し、元々、スキャンイン端子１０１からの値（信号）により制御されていたフリップフロップ７２−１乃至７２−４により構成されるスキャンチェーン８２を、別のスキャンイン端子１０２からの値により制御されるように変更する。これにより、ＡＮＤゲート９１は、スキャンイン端子１０１から値がスキャンインされるフリップフロップ７１−１およびフリップフロップ７１−２と、スキャンイン端子１０２から値がスキャンインされるフリップフロップ７３−１およびフリップフロップ７３−２の４つのフリップフロップにより値が入力されるので、１６種類の全ての組み合わせの値が入力されるようになる。本発明は、故障の検査を行うためのスキャンチェーンを構成する半導体集積回路に適用される。【選択図】      図７
2004239751.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路上に、複数のフリップフロップにより構成される複数のスキャンチェーンを構築する回路構築方法において、
前記フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、
前記スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示す前記フリップフロップの相関位置情報を取得する位置情報取得ステップと、
前記ゲート数取得ステップの処理により取得された前記ゲート数および前記位置情報取得ステップの処理により取得された前記フリップフロップの相関位置情報に基づいて、前記複数のスキャンチェーンを構築する構築ステップと
を含むことを特徴とする回路構築方法。
【請求項２】
前記論理トレースは、前記フリップフロップの入力端子を起点として前段に向かってトレースを行うバックワードトレースである
ことを特徴とする請求項１に記載の回路構築方法。
【請求項３】
前記ゲート数取得ステップは、前記フリップフロップの入力端子の論理を制御する信号を出力する半導体素子が他のフリップフロップであるか否かを判断する判断ステップと、
前記判断ステップの処理により前記半導体素子が前記他のフリップフロップであると判断された場合、前記半導体素子を、前記ゲート数を取得するための半導体素子リストに登録する登録ステップと
を含むことを特徴とする請求項２に記載の回路構築方法。
【請求項４】
前記論理トレースは、前記フリップフロップの出力端子を起点として後段に向かってトレースを行うフォワードトレースである
ことを特徴とする請求項１に記載の回路構築方法。
【請求項５】
前記ゲート数取得ステップは、前記フリップフロップの出力端子からの信号により制御される半導体素子が他のフリップフロップであるか否かを判断する判断ステップと、
前記判断ステップの処理により前記半導体素子が前記他のフリップフロップであると判断された場合、前記半導体素子を、前記ゲート数を取得するための半導体素子リストに登録する登録ステップと
を含むことを特徴とする請求項４に記載の回路構築方法。
【請求項６】
前記構築ステップは、前記ゲート数取得ステップの処理により取得された前記ゲート数に基づいて、前記複数のスキャンチェーンにおける、前記位置情報取得ステップの処理により取得された前記フリップフロップの相関位置情報に含まれる２つの前記フリップフロップからの信号が到達するゲート数を算出する算出ステップと、
前記算出ステップの処理により算出された前記複数のスキャンチェーンにおける前記フリップフロップ同士のゲート数が最小になるように、前記複数のスキャンチェーンの構成を変更する変更ステップと
を含むことを特徴とする請求項１に記載の回路構築方法。
【請求項７】
前記構築ステップは、前記ゲート数取得ステップの処理により取得された前記ゲート数に基づいて、前記複数のスキャンチェーンにおける、前記位置情報取得ステップの処理により取得された前記フリップフロップの相関位置情報に含まれる２つの前記フリップフロップからの信号が到達するゲート数を算出する算出ステップと、
前記算出ステップの処理により算出された前記複数のスキャンチェーンにおける前記フリップフロップ同士のゲート数が最小になるように、前記スキャンチェーン内の前記フリップフロップの位置を入れ換える入れ換えステップと
を含むことを特徴とする請求項１に記載の回路構築方法。
【請求項８】
半導体集積回路上に、複数のフリップフロップにより構成される複数のスキャンチェーンを構築する回路構築装置において、
前記フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得手段と、
前記スキャンチェーンの構成情報から、スキャンイン端子より同一の信号が入力される位置にあることを示す前記フリップフロップの相関位置情報を取得する位置情報取得手段と、
前記ゲート数取得手段により取得された前記ゲート数および前記位置情報取得手段により取得された前記フリップフロップの相関位置情報に基づいて、前記複数のスキャンチェーンを構築する構築手段と
を備えることを特徴とする回路構築装置。
【請求項９】
半導体集積回路上に、複数のフリップフロップにより構成される複数のスキャンチェーンを構築する回路構築処理を実行するプログラムであって、
前記フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、
前記スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示す前記フリップフロップの相関位置情報を取得する位置情報取得ステップと、
前記ゲート数取得ステップの処理により取得された前記ゲート数および前記位置情報取得ステップの処理により取得された前記フリップフロップの相関位置情報に基づいて、前記複数のスキャンチェーンを構築する構築ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１０】
半導体集積回路上に、複数のフリップフロップにより構成される複数のスキャンチェーンを構築する回路構築処理をコンピュータに実行させるプログラムであって、
前記フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、
前記スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示す前記フリップフロップの相関位置情報を取得する位置情報取得ステップと、
前記ゲート数取得ステップの処理により取得された前記ゲート数および前記位置情報取得ステップの処理により取得された前記フリップフロップの相関位置情報に基づいて、前記複数のスキャンチェーンを構築する構築ステップと
を実行させることを特徴とするプログラム。
【請求項１１】
複数のフリップフロップにより構成される複数のスキャンチェーンを有する半導体集積回路において、
前記複数のスキャンチェーンは、前記フリップフロップを起点とする論理トレースにより取得される、任意の２つのフリップフロップからの両方の信号が到達するゲート数、および、前記スキャンチェーンの構成情報から取得される、スキャンイン端子から同一の信号が入力される位置にあることを示す前記フリップフロップの相関位置情報に基づいて構築される
ことを特徴とする半導体集積回路。
【請求項１２】
前記スキャンイン端子は、前記複数のスキャンチェーンに信号を入力するスキャンイン端子により構成される
ことを特徴とする請求項１１に記載の半導体集積回路。
【請求項１３】
擬似乱数パターンの信号を、前記複数のスキャンチェーンに入力する乱数発生回路を有し、
前記スキャンイン端子は、前記乱数発生回路の端子により構成される
ことを特徴とする請求項１１に記載の半導体集積回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、回路構築方法および装置、記録媒体、プログラム、並びに半導体集積回路に関し、特に、スキャンテストにおいて、故障の検出率を向上させ、テスト時間を短縮することができるようにした回路構築方法および装置、記録媒体、プログラム、並びに半導体集積回路に関する。
【０００２】
【従来の技術】
半導体集積回路のテスト方法として広く用いられているスキャンパス回路は、特許文献１に示されるように、スキャンパス回路を構成するフリップフロップ（Ｆ／Ｆ）間をシリアルに接続したスキャンテスト専用のチェーン（以下、スキャンチェーンと称する）を構成することにより、スキャンパス回路の組み合わせ論理が所望の状態になるようにしている。その際、スキャンチェーンに入力されるテストデータは、一般に、スキャンチェーンの入口にあるスキャンイン端子からシフトインされる。
【０００３】
近年、回路規模の増大に伴い、スキャンチェーン長は、長くなる傾向にある。このため、スキャンチェーンに値（信号）をシフトインする時間が長くなり、テストデータの測定に時間がかかってしまう。したがって、スキャンパス回路においては、一般に、スキャンチェーンの本数を増加させ、スキャンチェーンをパラレル構成にすることで、１本あたりのスキャンチェーン長を短くするようにしている。しかしながら、スキャンテスト用の測定機器などの制約または回路の端子数の制限により、スキャンイン端子の数には、数十本という上限があり、それ以上増加させることができない。
【０００４】
このような問題に対応するため、少ないスキャンイン端子で多くのスキャンチェーンを制御する方法が提案されている。その方法を大きく２つに分けると、ファンアウト方法と、ＰＲＰＧ（Ｐｓｅｕｄｏ−Ｒａｎｄｏｍ  Ｐａｔｔｅｒｎ  Ｇｅｎｅｒａｔｉｏｎ）方法がある。
【０００５】
図１は、前者のファンアウト方法により構成されるスキャンパス回路の構成例を示している。図中の正方形は、フリップフロップを示しており、スキャンチェーン１−１乃至１−８は、それぞれ、ｎ個のフリップフロップがシリアル接続されて構成されている。図１の例においては、スキャンイン端子２は、スキャンチェーン１−１乃至１−４に値をシフトインし、その値によって、スキャンチェーン１−１乃至１−４を制御する。スキャンチェーン１−１乃至１−４は、スキャンイン端子２からシフトインされた値を、データ圧縮部（ＭＩＳＲ：Ｍｕｌｔｉｐｌｅ−Ｉｎｐｕｔ  Ｓｉｇｎａｔｕｒｅ  Ｒｅｇｉｓｔｅｒ）４に出力する。スキャンイン端子３は、スキャンチェーン１−５乃至１−８に値をシフトインし、その値によって、スキャンチェーン１−５乃至１−８を制御する。スキャンチェーン１−５乃至１−８は、スキャンイン端子３からシフトインされた値を、データ圧縮部４に出力する。換言すると、スキャンイン端子２は、スキャンチェーン１−１乃至１−４に共用されている。また、スキャンイン端子３は、スキャンチェーン１−５乃至１−６に共用されている。
【０００６】
このように、スキャンイン端子は、スキャンイン端子よりも多い数のスキャンチェーンに値を入力し、その値によって、スキャンチェーンを制御するので、図１のスキャンパス回路においては、結果として、スキャンチェーンの長さを短くすることができる。
【０００７】
しかしながら、スキャンイン端子２は、スキャンチェーン１−１乃至１−４に共用されているため、スキャンチェーン１−１乃至１−４のスキャンイン端子２から数えて２段目に位置する４つのフリップフロップ（図中ハッチング部）には、スキャンイン端子２から必ず同じ値（０か１）が入力されてしまうという根本的な問題がある。このことは、スキャンイン端子２（図中左側）から２段目の４つのフリップフロップだけではなく、スキャンチェーン１−１乃至１−４の同じ段（１段目乃至ｎ段目）に位置する縦４つのフリップフロップでも同様であり、同じスキャンイン端子２より制御されるスキャンチェーン１−１乃至１−４の同じ段の縦４つのフリップフロップは、回路の構成上、同じ値を取らざるを得ない。したがって、スキャンチェーンを介して設定できる回路の状態は、限られてしまい、結果的に、弊害が起こる恐れがある。なお、同じスキャンイン端子３に接続されるスキャンチェーン１−５乃至１−８の縦４つのフリップフロップの場合も同様である。
【０００８】
図２を参照して、上述した問題の弊害について説明する。図２においては、スキャンイン端子１１は、フリップフロップ１２−１乃至１２−３がシリアルに接続されるスキャンチェーンとフリップフロップ１３−１乃至１３−３がシリアルに接続されるスキャンチェーンに値を入力し、その値により、それらのスキャンチェーンを制御している。また、フリップフロップ１２−１，１２−２およびフリップフロップ１３−１，１３−２は、４入力ＡＮＤゲート１４に値を入力している。
【０００９】
図２の例においては、フリップフロップ１２−１，１３−１，１２−２，１３−２が４入力ＡＮＤゲート１４に入力する値には、例えば、それぞれ「０，０，０，０」、「０，１，０，０」、「０，０，１，０」、「０，０，０，１」、「１，０，０，０」、「０，１，１，０」、…というように、本来、１６通りの組み合わせがある。しかしながら、いまの場合、上述したようにスキャンイン端子１１を共用する複数のスキャンチェーンにおいて、同じ段の縦に並ぶフリップフロップには同一の値しか入力されないという制限があるため、実際に、フリップフロップ１２−１，１３−１，１２−２，１３−２から４入力ＡＮＤゲート１４に入力される値は、図３に示されるように、それぞれ「０，０，０，０」、「０，０，１，１」、「１，１，０，０」、および「１，１，１，１」の４通りしかない。したがって、残りの１２通りの値が４入力ＡＮＤゲート１４に入力された場合に初めて見つけることのできる故障は、見つけることができなくなり、結果として、検出率の低下を招く恐れがある。
【００１０】
このような問題を解決するため、例えば、スキャンチェーンとスキャンイン端子の対応を２種類用いるスキャンパス回路や、スキャンチェーンの長さを変更することにより対応するスキャンパス回路のように、リコンフィギャラブル（再構成可能）にスキャンチェーンを予め構成し、そのスキャンチェーン構成を変更することにより、原理的に見つからない故障をなくす方法が提案されている。
【００１１】
しかしながら、上述したリコンフィギャラブル（再構成可能）にスキャンチェーンを構成する２つの方法においては、スキャンチェーン構成を選択する回路を設置しなければならない、および、対応するスキャンチェーン構成のうちどのスキャンチェーン構成が最適であるか、またはどの長さのスキャンチェーンが最適であるかということは、試してみないと不明であるといった問題があった。
【００１２】
なお、ここで、上述したスキャンチェーンとスキャンイン端子の対応を２種類用いるスキャンパス回路において、実際にスキャンテストを行った場合、一方の種類の構成では、スキャンイン端子を共有化したことによることによる故障検出率の低下やパターンの増加はほとんど見受けられなかった。しかしながら、もう一方の構成にした場合、２５％も多いテストパターンデータを入力したとしても、例えば、実際には、１５０万個ある故障のうち、およそ６０００個の故障が見つけられなくなった。このように、例えば、２種類の構成があった場合、一方の種類の構成でしか見つからない故障の数が、他方の種類の構成でしか見つからない故障の数と同じくらいであった場合、テストパターン数が増加してしまうといった問題があった。
【００１３】
以上のように、リコンフィギャラブル（再構成可能）にスキャンチェーンを構成しても、図２を参照して説明した故障の検出率の低下やテストパターン数の増加が生じる恐れがある。
【００１４】
図４は、少ないスキャンイン端子で多くのスキャンチェーンを制御する方法のうちのもう一方の方法であるＰＲＰＧ方法によるスキャンパス回路の構成例を示している。ＰＲＰＧ方法は、一般的には、ロジックＢＩＳＴ（ｂｕｉｌｔ−ｉｎ−ｓｅｌｆ−ｔｅｓｔ）と呼ばれるテスト方法であり、スキャンチェーンを用いる点は、ファンアウト方法と同じである。なお、図４において、図１における場合と対応する部分には対応する符号を付してあり、その説明は繰り返しになるので省略する。
【００１５】
図４の例においては、乱数パターン発生部（ＰＲＰＧ）２１は、内部で発生した擬似パターンをテストデータとして、各スキャンチェーン１−１乃至１−８に入力する。スキャンチェーン１−１乃至１−８は、乱数パターン発生部２１より入力されたパターンデータを、データ圧縮部４に出力する。このように、ＰＲＰＧ方法を用いたスキャンパス回路では、スキャンイン端子に代わって、乱数パターン発生部２１が擬似パターンをスキャンチェーン１−１乃至１−８に入力することにより、多種のパターンのテストデータがスキャンチェーン１−１乃至１−８に入力される。これにより、スキャンイン端子不足に対応している。
【００１６】
しかしながら、ＰＲＰＧ方法においては、乱数パターン発生部２１がシフトレジスタをベースとしているため、図４のスキャンチェーン１−１において、乱数パターン発生部２１（図中左側）から１段目にあるフリップフロップ、スキャンチェーン１−２において、乱数パターン発生部２１から２段目にあるフリップフロップ、スキャンチェーン１−３において、乱数パターン発生部２１から３段目にあるフリップフロップ、スキャンチェーン１−４において、乱数パターン発生部２１から４段目にあるフリップフロップ、…などに示されるように、対角線状（図中のハッチング部分）に相関度の高いパターン（構成によるが、基本的には同じ値）が入力されてしまう問題がある。
【００１７】
これに対応して、一般的に、図中のハッチング部分のフリップフロップは、移相器（Ｐｈａｓｅ  Ｓｈｉｆｔｅｒ）などの回路で相関をなくすような工夫がなされている。しかしながら、その工夫をしたとしても、完全に相関が排除されるとは言えず、さらに、移相器などの回路を設置しなければならないなどの問題がある。
【００１８】
【特許文献１】
特開２００２−２８６８０３号公報
【００１９】
【発明が解決しようとする課題】
以上のように、図１を参照して上述したファンアウト方法により構成されるスキャンパス回路においては、スキャンイン端子から入力される値では、スキャンチェーン上の値の組み合わせを完全に制御することができない課題があった。また、図４を参照して上述したＰＲＰＧ方法により構成されるスキャンパス回路においても、乱数パターン発生部２１（の端子）から入力される値では、スキャンチェーン上の値の組み合わせを完全に制御することができない課題があった。したがって、従来のスキャンパス回路において、スキャンチェーンの一部分に常に相関度の高い値が入力してしまうフリップフロップが存在し、そのフリップフロップにより４入力ＮＡＮＤゲート１４（図２）などのゲートが制御されてしまうため、故障の検出率の低下が生じる恐れがある課題があった。
【００２０】
本発明は、このような状況に鑑みてなされたものであり、スキャンテストにおいて、故障の検出率を向上し、テスト時間を短縮することができるようにするものである。
【００２１】
【課題を解決するための手段】
本発明の回路構築方法は、フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報を取得する位置情報取得ステップと、ゲート数取得ステップの処理により取得されたゲート数および位置情報取得ステップの処理により取得されたフリップフロップの相関位置情報に基づいて、複数のスキャンチェーンを構築する構築ステップとを含むことを特徴とする。
【００２２】
論理トレースは、フリップフロップの入力端子を起点として前段に向かってトレースを行うバックワードトレースであるようにすることができる。
【００２３】
ゲート数取得ステップは、フリップフロップの入力端子の論理を制御する信号を出力する半導体素子が他のフリップフロップであるか否かを判断する判断ステップと、判断ステップの処理により半導体素子が他のフリップフロップであると判断された場合、半導体素子を、ゲート数を取得するための半導体素子リストに登録する登録ステップとを含むようにすることができる。
【００２４】
論理トレースは、フリップフロップの出力端子を起点として後段に向かってトレースを行うフォワードトレースであるようにすることができる。
【００２５】
ゲート数取得ステップは、フリップフロップの出力端子からの信号により制御される半導体素子が他のフリップフロップであるか否かを判断する判断ステップと、判断ステップの処理により半導体素子が他のフリップフロップであると判断された場合、半導体素子を、ゲート数を取得するための半導体素子リストに登録する登録ステップとを含むようにすることができる。
【００２６】
構築ステップは、ゲート数取得ステップの処理により取得されたゲート数に基づいて、複数のスキャンチェーンにおける、位置情報取得ステップの処理により取得されたフリップフロップの相関位置情報に含まれる２つのフリップフロップからの信号が到達するゲート数を算出する算出ステップと、算出ステップの処理により算出された複数のスキャンチェーンにおけるフリップフロップ同士のゲート数が最小になるように、複数のスキャンチェーンの構成を変更する変更ステップとを含むようにすることができる。
【００２７】
構築ステップは、ゲート数取得ステップの処理により取得されたゲート数に基づいて、複数のスキャンチェーンにおける、位置情報取得ステップの処理により取得されたフリップフロップの相関位置情報に含まれる２つのフリップフロップからの信号が到達するゲート数を算出する算出ステップと、算出ステップの処理により算出された複数のスキャンチェーンにおけるフリップフロップ同士のゲート数が最小になるように、スキャンチェーン内のフリップフロップの位置を入れ換える入れ換えステップとを含むようにすることができる。
【００２８】
本発明の回路構築装置は、フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得手段と、スキャンチェーンの構成情報から、スキャンイン端子より同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報を取得する位置情報取得手段と、ゲート数取得手段により取得されたゲート数および位置情報取得手段により取得されたフリップフロップの相関位置情報に基づいて、複数のスキャンチェーンを構築する構築手段とを備えることを特徴とする。
【００２９】
本発明の記録媒体のプログラムは、フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報を取得する位置情報取得ステップと、ゲート数取得ステップの処理により取得されたゲート数および位置情報取得ステップの処理により取得されたフリップフロップの相関位置情報に基づいて、複数のスキャンチェーンを構築する構築ステップとを含むことを特徴とする。
【００３０】
本発明のプログラムは、フリップフロップを起点として論理トレースを行い、任意の２つのフリップフロップからの両方の信号が到達するゲート数を取得するゲート数取得ステップと、スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報を取得する位置情報取得ステップと、ゲート数取得ステップの処理により取得されたゲート数および位置情報取得ステップの処理により取得されたフリップフロップの相関位置情報に基づいて、複数のスキャンチェーンを構築する構築ステップとを実行させることを特徴とする。
【００３１】
本発明の半導体集積回路は、複数のスキャンチェーンは、フリップフロップを起点とする論理トレースにより取得される、任意の２つのフリップフロップからの両方の信号が到達するゲート数、および、スキャンチェーンの構成情報から取得される、スキャンイン端子から同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報に基づいて構築されることを特徴とする。
【００３２】
スキャンイン端子は、複数のスキャンチェーンに信号を入力するスキャンイン端子により構成されるようにすることができる。
【００３３】
擬似乱数パターンの信号を、複数のスキャンチェーンに入力する乱数発生回路を有し、スキャンイン端子は、乱数発生回路の端子により構成されるようにすることができる。
【００３４】
本発明においては、フリップフロップを起点として論理トレースが行われ、任意の２つのフリップフロップからの両方の信号が到達するゲート数が取得され、スキャンチェーンの構成情報から、スキャンイン端子から同一の信号が入力される位置にあることを示すフリップフロップの相関位置情報が取得される。そして、取得されたゲート数およびフリップフロップの相関位置情報に基づいて、複数のスキャンチェーンが構築される。
【００３５】
【発明の実施の形態】
以下、図を参照して本発明の実施の形態について説明する。
【００３６】
図５は、本発明を適用した回路構築装置３１の構成を示すブロック図である。回路構築装置３１は、各処理を実行するための半導体素子などにより構成されるセルで構築されている半導体集積回路において、その半導体集積回路を検査するための複数のスキャンチェーンにより構成されるスキャンパス回路を構築する。図５の例においては、回路構築装置３１は、論理トレース処理部４１、記録部４２、位置情報取得部４３および構成構築処理部４４などにより構成される。
【００３７】
論理トレース処理部４１は、スキャンパス回路を構築するために、各処理を実行するためのセルが構築された半導体集積回路を準備し、半導体集積回路のフリップフロップから、バックワードトレースの対象であるキャプチャフリップフロップ（以下、キャプチャＦ／Ｆと称する）を１つ選択し、キャプチャＦ／Ｆの入力端子（入力ネット）からバックワードコーンを生成する。
【００３８】
バックワードコーンは、任意のネットの論理に対して、影響を与えている、フリップフロップを含めた論理ゲートの集合体である。例えば、キャプチャクロックを１回だけスキャンチェーンに入力するスキャンテストであるＤＣ（ｄｉｒｅｃｔ  ｃｕｒｒｅｎｔ）テストの場合のバックワードコーンは、前段のフリップフロップからそのネットに到達するパスの集合体となる。また、キャプチャクロックを２回入力するスキャンテストであるＡＣ（ａｌｔｅｒｎａｔｉｎｇ  ｃｕｒｒｅｎｔ）スキャンなどの場合のバックワードコーンは、前々段のフリップフロップからそのネットに到達するパスの集合体となる。ここで、ネットは、例えば、前段のフリップフロップの出力端子と後段のフリップフロップの入力端子を結ぶ接続（Ｗｉｒｅ）であり、その前段のフリップフロップの出力端子と後段のフリップフロップの入力端子を含む。
【００３９】
論理トレース処理部４１は、すべてのフリップフロップに対して、キャプチャＦ／Ｆの入力端子をドライブするセル、セルの入力端子をドライブするセル、…というように、セルが他のフリップフロップまたは外部端子であるとされるまで、キャプチャＦ／Ｆの入力端子を始点としてバックワードトレース（論理トレース）を実行し、バックワードコーンを生成する。そして、論理トレース処理部４１は、任意の２つのフリップフロップから生成された２つのバックワードコーンを比較し、バックワードコーンの要素（論理ゲート）の重なりである論理重なりを求め、記憶部４２の論理重なり表に登録する。
【００４０】
なお、任意の２つのフリップフロップから生成された２つのバックワードコーンに、バックワードコーンの要素（論理ゲート）の重なりがある場合、その２つのフリップフロップには論理重なりがあるとされる。また、論理重なりがある２つのフリップフロップを逆の視点から見ると、ある論理ゲートからフォワードコーン（図１１を参照して後述する）を生成した場合、その２つのフリップフロップは、そのフォワードコーンに含まれているとも言える。
【００４１】
論理重なり表は、半導体集積回路に含まれるフリップフロップ同士の論理重なりを２次元で表すものである。なお、このとき、バックワードコーンの要素（論理ゲート）から、重なりの度合いを示す論理重なり度を求めるようにしてもよい。なお、重なり度とは、重なりの度合いを相対的に示すものであり、例えば、バックワードコーンの要素の重なりが多い（すなわち、重なる論理ゲート数が多い）場合、論理重なり度は高いとされる。
【００４２】
位置情報取得部４３は、半導体集積回路のスキャンチェーン構成情報（何本のスキャンチェーンにより構成されるか、ＰＲＰＧ（ｐｓｅｕｄｏ−ｒａｎｄｏｍ  ｐａｔｔｅｒｎ  ｇｅｎｅｒａｔｉｏｎ）構成であるか、ファンアウト構成であるかなど）に基づいて、相関ＳＩ位置情報を取得する。相関ＳＩ位置とは、スキャンイン端子から同一、または非常に相関の高いデータが入力される位置のことである。具体的には、後述する図６の例の場合の相関ＳＩ位置は、フリップフロップ７１−１の位置とフリップフロップ７２−１の位置であり、フリップフロップ７１−２の位置とフリップフロップ７２−２の位置であり、フリップフロップ７１−３の位置とフリップフロップ７２−３の位置である。
【００４３】
構成構築処理部４４は、従来の方法で半導体集積回路上に形成されたスキャンパス回路を用いて、記憶部４２に記憶された論理重なり表および位置情報取得部４３により取得された相関ＳＩ位置情報に基づいて、相関ＳＩ位置に論理重なり度の最小の（論理重なりができるだけない）フリップフロップが位置するように、スキャンチェーンの構成（スキャンパス回路）を構築する。
【００４４】
図６は、半導体集積回路に従来の方法で形成されたスキャンパス回路６１の構成を示すブロック図である。
【００４５】
図６の例においては、スキャンパス回路６１は、フリップフロップ（Ｆ／Ｆ）７１−１乃至７１−４が順にシリアルに接続されたスキャンチェーン８１、フリップフロップ７２−１乃至７２−４が順にシリアルに接続されたスキャンチェーン８２、フリップフロップ７３−１乃至７３−４が順にシリアルに接続されたスキャンチェーン８３、およびフリップフロップ７４−１乃至７４−４が順にシリアルに接続されたスキャンチェーン８４の４つのスキャンチェーンで構成されている。なお、図示はしないが、各フリップフロップは、図中左側（矢印の先端部分）に、値（信号）が入力される入力端子を有し、図中右側（矢印の後端部分）に、値を出力する出力端子を有している。
【００４６】
ＡＮＤゲート９１は、フリップフロップ７１−１、フリップフロップ７１−２、フリップフロップ７２−１およびフリップフロップ７２−２の４つのフリップフロップからの値が入力される４入力ＡＮＤゲートにより構成される。ＮＡＮＤゲート９２は、フリップフロップ７３−１、フリップフロップ７３−２、フリップフロップ７４−１およびフリップフロップ７４−２の４つのフリップフロップからの値が入力される４入力ＮＡＮＤゲートにより構成される。
【００４７】
スキャンイン端子１０１および１０２は、外部からテストデータなどの値を、スキャンチェーンにシフトイン（入力）する外部端子である。スキャンイン端子１０１は、フリップフロップ７１−１乃至７１−４が順にシリアルに接続されたスキャンチェーン８１と、フリップフロップ７２−１乃至７２−４が順にシリアルに接続されたスキャンチェーン８２に値をシフトインし、その値によって、スキャンチェーン８１およびスキャンチェーン８２を制御している。
【００４８】
スキャンイン端子１０２は、フリップフロップ７３−１乃至７３−４が順にシリアルに接続されたスキャンチェーン８３と、フリップフロップ７４−１乃至７４−４が順にシリアルに接続されたスキャンチェーン８４に値をシフトインし、その値によって、スキャンチェーン８３およびスキャンチェーン８４を制御している。なお、実際には、上述したフリップフロップ、各ゲートおよびスキャンイン端子のようなセル以外にも他の機能をするため半導体素子などのセルが配置されているが、図示を省略する。
【００４９】
ここで、図６のスキャンパス回路６１は、従来の方法でスキャンチェーンが構築された回路である。したがって、スキャンパス回路６１においては、スキャンチェーン８１および８２において同じ段に位置するフリップフロップ７１−１と７２−１並びにフリップフロップ７１−２と７２−２は、スキャンイン端子１０１より同じ値がシフトインされる。同様に、スキャンチェーン８３および８４において同じ段に位置するフリップフロップ７３−１と７４−１並びにフリップフロップ７３−２と７４−２は、スキャンイン端子１０２より同じ値がシフトインされる。
【００５０】
すなわち、ＡＮＤゲート９１の入力とＮＡＮＤゲート９２の入力の組み合わせは、図３を参照して上述したように、「０，０，０，０」、「０，０，１，１」、「１，１，０，０」、および「１，１，１，１」の４通りの組み合わせしかないといった制限が生じ、これにより、スキャンパス回路６１においては、故障の検出率の低下が起こってしまう。
【００５１】
そこで、構成構築処理部４４は、従来の方法で半導体集積回路上に形成されたスキャンパス回路６１を用いて、記憶部４２に記憶された論理重なり表および位置情報取得部４３により取得された相関ＳＩ位置情報に基づいて、相関ＳＩ位置に論理重なり度が最小の（論理重なりができるだけない）フリップフロップが位置するように、例えば、同じスキャンイン端子の値が入力されるスキャンチェーンの組み合わせを変更したり、または、スキャンチェーン内のフリップフロップの順を入れ換えたりして、スキャンチェーンの構成を構築する。
【００５２】
図７は、構成構築処理部４４において構築されたスキャンパス回路１２１の構成例を示す。なお、図７において、図６における場合と対応する部分には対応する符号を付してあり、その説明は繰り返しになるので省略する。
【００５３】
構成構築処理部４４は、図６のスキャンイン端子１０１により値が入力されていたスキャンチェーン８２を、スキャンイン端子１０２により値が入力される構成に変更し、図６のスキャンイン端子１０２により値が入力されていたスキャンチェーン８３を、スキャンイン端子１０１により値が入力される構成に変更して、図７のスキャンパス回路１２１を構築する。
【００５４】
このようにすることで、スキャンイン端子１０１は、フリップフロップ７１−１乃至７１−４が順にシリアルに接続されるスキャンチェーン８１と、フリップフロップ７３−１乃至７３−４が順にシリアルに接続されるスキャンチェーン８３に値をシフトインし、その値によって、スキャンチェーン８１およびスキャンチェーン８３を制御するようになる。スキャンイン端子１０２は、フリップフロップ７２−１乃至７２−４が順にシリアルに接続されるスキャンチェーン８２と、フリップフロップ７４−１乃至７４−４が順にシリアルに接続されるスキャンチェーン８４に値をシフトインし、その値によって、スキャンチェーン８２およびスキャンチェーン８４を制御するようになる。
【００５５】
これにより、スキャンチェーン８１および８３において同じ段にあるフリップフロップ７１−１および７３−１、並びにフリップフロップ７１−２および７３−２には、スキャンイン端子１０１より同じ値がシフトインされる。また同様に、スキャンチェーン８２および８３において同じ段にあるフリップフロップ７２−１および７４−１、並びにフリップフロップ７２−２および７４−２には、スキャンイン端子１０２より同じ値がシフトインされる。
【００５６】
したがって、ＡＮＤゲート９１は、スキャン端子１０１により値がシフトインされるフリップフロップ７１−１とフリップフロップ７１−２、およびスキャン端子１０２により値がシフトインされるフリップフロップ７２−１とフリップフロップ７３−２の４つのフリップフロップにより値が入力される。すなわち、図７のスキャンパス回路１２１において、ＡＮＤゲート９１の入力には、図８に示されるように、１６種類の全ての組み合わせが入力されるようになり、スキャンテストにおいて故障の検出率の向上を図ることができる。
【００５７】
図８は、図７のスキャンパス回路１２１におけるＡＮＤゲート９１の入力の組み合わせを示している。上述したように、図７のフリップフロップ７１−１，７１−２，７２−１，７２−２に入力される値の制限はない。したがって、フリップフロップ７１−１，７１−２，７２−１，７２−２からＡＮＤゲート９１に入力される値は、「０，０，０，０」、「０，０，０，１」、「０，０，１，０」、「０，０，１，１」、「０，１，０，０」、「０，１，０，１」、「０，１，１，０」、「０，１，１，１」、「１，０，０，０」、「１，０，０，１」、「１，０，１，０」、「１，０，１，１」、「１，１，０，０」、「１，１，０，１」、「１，１，１，０」、および「１，１，１，１」の１６通りの組み合わせになる可能性がある。
【００５８】
なお、これは、ＮＡＮＤゲート９２においても同様であり、ＮＡＮＤゲート９２は、スキャン端子１０１により値がシフトインされるフリップフロップ７３−１とフリップフロップ７３−２、およびスキャン端子１０２により値がシフトインされるフリップフロップ７４−１とフリップフロップ７４−２の４つのフリップフロップにより値が入力される。したがって、ＮＡＮＤゲート９２には、１６種類の全ての組み合わせが入力されるようになり、スキャンテストにおいて故障の検出率の向上を図ることができる。
【００５９】
図９は、構成構築処理部４４において構築されたスキャンパス回路１４１の構成例を示している。なお、図９において、図６における場合と対応する部分には対応する符号を付してあり、その説明は繰り返しになるので省略する。
【００６０】
構成構築処理部４４は、図６において、スキャンイン端子１０１からフリップフロップ７２−１，７２−２，７２−３および７２−４の順にシリアルに接続されていたスキャンチェーン８２内において、フリップフロップ７２−１および７２−２の位置とフリップフロップ７２−３および７２−４の位置を入れ換えて、図９に示されるように、スキャンチェーン８２の並びが、スキャンイン端子１０１からフリップフロップ７２−３，７２−４，７２−１および７２−２の順にシリアルに接続されるように、スキャンパス回路１４１を構築する。
【００６１】
また、同様にして、構成構築処理部４４は、図６において、スキャンイン端子１０２からフリップフロップ７４−１，７４−２，７４−３および７４−４の順にシリアルに接続されていたスキャンチェーン８４内において、フリップフロップ７４−１および７４−２の位置とフリップフロップ７４−３および７４−４の位置を入れ換えて、図９に示されるように、スキャンチェーン８４の並びが、スキャンイン端子１０１からフリップフロップ７４−３，７４−４，７４−１および７４−２の順にシリアルに接続されるように、スキャンパス回路１４１を構築する。
【００６２】
これにより、フリップフロップ７１−１および７２−３、並びにフリップフロップ７１−２および７２−４には、スキャンイン端子１０１より同じ値がシフトインされ、フリップフロップ７３−１および７４−３、並びにフリップフロップ７３−２および７４−４には、スキャンイン端子１０２より同じ値がシフトインされる。
【００６３】
ＡＮＤゲート９１は、スキャンチェーン８１の左から一段目のフリップフロップ７１−１、スキャンチェーン８１の左から２段目のフリップフロップ７１−２、スキャンチェーン８２の左から３段目のフリップフロップ７２−１、およびスキャンチェーン８２の左から４段目のフリップフロップ７２−２により値が入力される。すなわち、ＡＮＤゲート９１は、４つの段数の異なるフリップフロップにより値が入力される。したがって、図９のスキャンパス回路１４１においては、図７のスキャンパス回路１２１のＡＮＤゲート９１の入力と同様に、１６種類の全ての組み合わせが入力できるようになる。
また、ＮＡＮＤゲート９２の場合も同様で、ＮＡＮＤゲート９２は、スキャンチェーン８３の左から１段目のフリップフロップ７３−１、スキャンチェーン８３の左から２段目のフリップフロップ７３−２、スキャンチェーン８４の左から３段目のフリップフロップ７４−１、およびスキャンチェーン８４の左から４段目のフリップフロップ７４−２により値が入力される。すなわち、ＮＡＮＤゲート９２は、４つの段数の異なるフリップフロップにより値が入力される。したがって、図９のスキャンパス回路１４１においては、図７のスキャンパス回路１２１のＮＡＮＤゲート９２の入力と同様に、１６種類の全ての組み合わせが入力できるようになる。
【００６４】
以上により、図９のスキャンパス回路１４１において、ＡＮＤゲート９１の入力とＮＡＮＤゲート９２は、図７のスキャンパス回路１２１とＡＮＤゲート９１の入力とＮＡＮＤゲート９２と同様に、共に、１６種類の全ての組み合わせが入力できるようになる。これにより、スキャンテストにおいて故障の検出率の向上を図ることができる。
【００６５】
なお、図７のスキャンパス回路１２１および図９のスキャンパス回路１４１は、図２および図３を参照して上述した入力される値に制限が生じるゲートがスキャンチェーン全体に渡って、最小となるように計算してスキャンチェーンを作りこんだものであり、従来のように、検出率低下の問題回避のためだけに、スキャンチェーンをリコンフィギャラブル（再構成可能）な構成にする必要はない。
【００６６】
次に、図１０のフローチャートを参照して、スキャンパス回路の構築処理について説明する。
【００６７】
ステップＳ１において、論理トレース処理部４１は、半導体集積回路を準備し、論理トレース処理を実行し、半導体集積回路のすべてのフリップフロップ同士に対しての論理重なり表を記憶部４２に記憶する。この論理トレース処理は、図１１および図１２のフローチャートを参照して後述する。
【００６８】
ステップＳ２において、位置情報取得部４３は、半導体集積回路のスキャンチェーン構成情報（何本のスキャンチェーンにより構成されるか、ＰＲＰＧ構成であるか、ファンアウト構成であるかなど）に基づいて、スキャンイン端子から同一、または非常に相関の高いデータが入力される位置である相関ＳＩ位置の情報を取得する。
【００６９】
ステップＳ３において、構成構築処理部４４は、スキャンパス回路６１が形成された半導体集積回路を用いて、記憶部４２に記憶された論理重なり表および位置情報取得部４３により取得された相関ＳＩ位置情報に基づいて、相関ＳＩ位置に論理重なりのあるフリップフロップ（論理重なり度の高いフリップフロップ）が接続されることがないように、例えば、スキャンチェーンの組み合わせを変更したり、または、スキャンチェーン内のフリップフロップを入れ換えたりして、スキャンチェーンの構成を構築する。これにより、スキャンパス回路が構築される。このスキャンチェーンの構成構築処理は、図１３のフローチャートを参照して後述する。
【００７０】
以上のように、図６のスキャンパス回路６１が、図７のスキャンパス回路１２１または図９のスキャンパス回路１４１として構築される。
【００７１】
次に、図１１のフローチャートを参照して、図１０のステップＳ１の論理トレース処理を説明する。なお、図１１の例においては、キャプチャクロックを１回入力するＤＣテストの場合において、あるキャプチャＦ／Ｆの入力端子に基づいてバックワードトレース（論理トレース）を行い、バックワードコーンを生成する処理について説明する。
【００７２】
論理トレース処理部４１は、ステップＳ２１において、半導体集積回路のフリップフロップから、キャプチャＦ／Ｆを１つ選択し、ステップＳ２２に進み、記憶部４２に記憶されているフリップフロップリスト（以下、Ｆ／Ｆリストと称する）および端子リストをクリアし、ステップＳ２３に進む。ここで、Ｆ／Ｆリストは、キャプチャＦ／Ｆの入力端子（入力ネット）を始点としてバックワードコーンを生成することにより到達したフリップフロップ（論理ゲート）を格納するテーブルである。端子リストは、バックワードトレース中に用いられる中間リストであり、まだ、バックワードトレースされていない入力端子を一時保管するリストである。
【００７３】
論理トレース処理部４１は、ステップＳ２３において、選択したキャプチャＦ／Ｆの入力端子を、記憶部４２の端子リストに登録し、ステップＳ２４に進み、登録した端子リストの中から１つの回路内部にあるセルの入力端子Ｐを取り出し、ステップＳ２５に進む。論理トレース処理部４１は、ステップＳ２５において、取り出した入力端子Ｐをドライブする（すなわち、入力端子Ｐの論理を制御する信号を、入力端子Ｐに出力する）ドライバＤ（セルまたは外部端子）の種類を取得し、ステップＳ２６に進み、そのドライバＤがフリップフロップであるか否かを判断する。
【００７４】
ステップＳ２６において、ドライバＤがフリップフロップであると判断された場合、処理は、ステップＳ２７に進み、論理トレース処理部４１は、ドライバＤ（フリップフロップ）を記憶部４２のＦ／Ｆリストに登録し、ステップＳ３０に進む。ステップＳ２６において、ドライバＤがフリップフロップではないと判断された場合、処理は、ステップＳ２８に進み、論理トレース処理部４１は、ドライバＤが外部端子（スキャンイン端子などの）であるか否かを判断する。
【００７５】
ステップＳ２８において、ドライバＤが外部端子ではないと判断された場合、ステップＳ２９に進み、論理トレース処理部４１は、そのドライバＤの入力端子すべてを記憶部４２の端子リストに追加して、ステップＳ３０に進む。ステップＳ２８において、ドライバＤが外部端子であると判断された場合、ステップＳ２９の処理は、スキップされ、ステップＳ３０に進む。
【００７６】
ステップＳ３０において、論理トレース処理部４１は、記憶部４２の端子リストにまだバックトレースを行っていないセルの入力端子が残っているか否かを判断し、端子リストに入力端子が残っていると判断した場合、処理は、ステップＳ２４に戻り、それ以降の処理を繰り返す。ステップＳ３０において記憶部４２の端子リストに入力端子が残っていないと判断された場合、処理は、ステップＳ３１に進む。
【００７７】
以上のようにして、キャプチャＦ／Ｆの入力端子をドライブするセル、セルの入力端子をドライブするセル、…というように、セルが他のフリップフロップまたは外部端子であるとされるまで、キャプチャＦ／Ｆの入力端子を始点としてバックワードトレース（すなわち、ステップＳ２４乃至Ｓ３０の処理）が実行される。そして、最終的に到達したフリップフロップ（論理ゲート）は、Ｆ／Ｆリストに登録される。すなわち、キャプチャＦ／Ｆを頂点としたバックワードコーンが生成され、バックワードコーンのうち、終端にあるすべてのフリップフロップがＦ／Ｆリストに登録される。このＦ／Ｆリストに登録されたフリップフロップ同士は、バックワードコーンの中のどこかしらの論理に関係し、最終的にキャプチャＦ／Ｆに到達していることになるので、論理重なりがあるとされる。
【００７８】
ステップＳ３１において、論理トレース処理部４１は、Ｆ／Ｆリストに基づいて、フリップフロップの論理重なりの有無を求めることにより、論理重なり表を生成し、記憶部４２に保存し、ステップＳ３２に進む。
【００７９】
ステップＳ３２において、論理トレース処理部４１は、上記処理が、半導体集積回路のすべてのフリップフロップに対して終わったか否かを判断し、まだ処理が終わっていないと判断した場合、処理はステップＳ２１に戻り、他のフリップフロップをキャプチャＦ／Ｆとし、それ以降の処理を繰り返す。これにより、半導体集積回路のすべてのフリップフロップ（論理ゲート）に対して、フリップフロップ同士の論理重なりの有無を示す論理重なり表が生成される。なお、いまの場合、論理重なりの有無を示す論理重なり表を生成したが、論理重なりの度合いを示す論理重なり度表を生成するようにしてもよい。
【００８０】
ステップＳ３２において、すべてのフリップフロップに対して処理が終わったと判断された場合、バックワードトレース（論理トレース）処理は、終了され、処理は、図１０のステップＳ２に進む。
【００８１】
以上のようにして、論理トレース処理を行うことにより、半導体集積回路のすべてのフリップフロップに対する論理重なり表が記憶部４２に記憶される。
【００８２】
なお、上記説明においては、あるキャプチャＦ／Ｆの入力端子に基づいてバックワードトレース（論理トレース）を行い、バックワードコーンを生成する方法について説明したが、論理トレース処理部４１は、フォワードトレースの対象であるスキャンフリップフロップ（以下、スキャンＦ／Ｆと称する）の出力端子に基づいてフォワードトレース（論理トレース）を行い、フォワードコーンを生成することもできる。
【００８３】
フォワードコーンは、所定のキャプチャサイクルにおいて、任意のネット（出力端子を含む）に着目した場合、その値（０／１）が伝達されることで、論理的に影響を与えている論理ゲート（フリップフロップを含む）の集合体である。例えば、キャプチャクロックを１回だけ入力するスキャンテストであるＤＣテストの場合のフォワードコーンは、そのネットを始点として後段のフリップフロップに到達するパスの集合体となる。また、キャプチャクロックを２回入力するスキャンテストであるＡＣスキャンなどの場合のフォワードコーンは、そのネットを始点として２段目後までのフリップフロップに到達するパスの集合体となる。
【００８４】
フォワードコーンにおいては、ある２つのフリップフロップの出力端子からフォワードコーンを生成した場合、生成されたフォワードコーン同士の要素（論理ゲート）に重なりがあるときに、その２つのフリップフロップに論理重なりがあるとされる。また、論理重なりがある２つのフリップフロップを逆の視点から見ると、ある論理ゲートからバックワードコーンを生成した場合、そのバックワードコーンに２つのフリップフロップが両方とも含まれているとき、その２つのフリップフロップに論理重なりがあると言える。
【００８５】
また、この場合、フォワードコーンの要素の重なる量が多いとき、その２つのフリップフロップの論理重なり度は高いとされる。逆の視点でいうと、ある論理ゲートからバックワードコーンを生成した場合、その２つのフリップフロップをバックワードコーンに含む論理ゲートが多くある状態のとき、その２つのフリップフロップの論理重なり度は高いとされる。
【００８６】
次に、図１２を参照して、スキャンＦ／Ｆの出力端子に基づいてフォワードトレースを行い、フォワードコーンを生成する場合の論理トレース処理について説明する。なお、この図１２のフローチャートは、図１１を参照して上述した図１０のステップＳ１の論理トレース処理の他の例である。
【００８７】
論理トレース処理部４１は、ステップＳ５１において、記憶部４２の終端フリップフロップリスト（以下、終端Ｆ／Ｆリストと称する）をクリアし、ステップＳ５２に進む。ここで、終端Ｆ／Ｆリストは、各スキャンＦ／Ｆについてフォワードコーンを生成した場合の終端のフリップフロップ（論理ゲート）を格納するテーブルである。
【００８８】
ステップＳ５２において、論理トレース処理部４１は、半導体集積回路６１のフリップフロップから、スキャンＦ／Ｆを１つ選択し、ステップＳ５３に進む。ステップＳ５３において、論理トレース処理部４１は、端子リストをクリアし、クリアした端子リストにスキャンＦ／Ｆの出力端子を登録し、ステップＳ５４に進む。なお、端子リストは、フォワードトレース中に用いられる中間リストであり、まだ、フォワードトレースされていない回路内部にあるセルの出力端子を一時保管するリストである。
【００８９】
論理トレース処理部４１は、ステップＳ５４において、登録した端子リストの中から１つの出力端子Ｑを取り出し、ステップＳ５５に進み、取り出した出力端子Ｑがドライブする（すなわち、出力端子Ｑからの信号により制御される）対象であるレシーバＲ（セルまたは外部出力端子）の種類を取得する。ステップＳ５６において、論理トレース処理部４１は、取得したレシーバＲの種類を確認し、レシーバＲがフリップフロップであるか否かを判断し、レシーバＲがフリップフロップであると判断した場合、ステップＳ５７に進む。ステップＳ５７において、論理トレース処理部４１は、そのレシーバＲ（フリップフロップ）を記憶部４２の終端Ｆ／Ｆリストに登録して、ステップＳ６０に進む。
【００９０】
一方、ステップＳ５６において、レシーバＲがフリップフロップではないと判断された場合、処理は、ステップＳ５８に進み、論理トレース処理部４１は、レシーバＲが外部端子であるか否かを判断する。ステップＳ５８において、レシーバＲが外部端子ではないと判断された場合、ステップＳ５９に進み、論理トレース処理部４１は、そのレシーバＲの出力端子すべてを記憶部４２の端子リストに追加する。ステップＳ５８において、レシーバＲが外部端子であると判断された場合、ステップＳ５９の処理は、スキップされ、ステップＳ６０に進む。
【００９１】
ステップＳ６０において、論理トレース処理部４１は、記憶部４２の端子リストにまだ出力端子が残っているか否かを判断し、端子リストにまだフォワードトレースされていないセルの出力端子が残っていると判断した場合、処理は、ステップＳ５４に戻り、それ以降の処理を繰り返す。ステップＳ６０において記憶部４２の端子リストに出力端子が残っていないと判断した場合、処理は、ステップＳ６１に進む。
【００９２】
ステップＳ６１において、論理トレース処理部４１は、上記処理が、半導体集積回路のすべてのフリップフロップに対して終わったか否かを判断し、まだ処理が終わっていないと判断した場合、処理はステップＳ５１に戻り、他のフリップフロップをスキャンＦ／Ｆとし、それ以降の処理を繰り返す。
【００９３】
ステップＳ６１において、すべてのフリップフロップに対して処理が終わったと判断された場合、ステップＳ６２において、論理トレース処理部４１は、記憶部４２の終端Ｆ／Ｆリストに基づいて、各フリップフロップ同士の重なりの有無を求め、フリップフロップの論理重なりの有無に基づいて、論理重なり表を生成し、記憶部４２に記憶する。
【００９４】
具体的には、上述したように、スキャンＦ／Ｆの出力端子をドライブするセル、セルの出力端子をドライブするセル、…というように、セルがフリップフロップまたは外部端子であるとされるまで、スキャンＦ／Ｆの出力端子を始点としてフォワードトレース（すなわち、ステップＳ５４乃至Ｓ６０の処理）が実行される。そして、最終的に到達したフリップフロップ（論理ゲート）は、終端Ｆ／Ｆリストに登録される。すなわち、スキャンＦ／Ｆを頂点としたフォワードコーンが生成され、フォワードコーンのうち、終端にあるすべてのフリップフロップ（論理ゲート）が終端Ｆ／Ｆリストに登録される。
【００９５】
そして、論理トレース処理部４１は、すべてのフリップフロップの終端Ｆ／Ｆリストに基づいて、フリップフロップ同士が同一の終端フリップフロップに到達しているか否かを求める。同一の終端フリップフロップに到達している場合、そのフリップフロップ同士は、論理重なりがある（独立性がない）とされる。したがって、論理トレース処理部４１は、すべてのフリップフロップ同士の組み合わせについて解析することにより、最終的に、論理重なり表を取得することができる。
【００９６】
以上のようにして、フォワードコーンの生成による論理トレース処理は、終了され、処理は、図１０のステップＳ２に進む。
【００９７】
なお、図１１および図１２においては、それぞれバックワードコーン、フォワードコーンにより論理重なり表を生成する処理を説明したが、それらを組み合わせた方法により論理重なり表を取得こともできる。例えば、スキャンＦ／Ｆの出力端子からフォワードトレースを繰り返すことで、図１２の例のようにフォワードコーンを生成した後、フォワードコーンに含まれる各ゲートの入力端子からバックワードトレースを繰り返すことで、図１１の例のようにバックワードコーンを生成していく。これにより、最初に選択したスキャンＦ／Ｆ以外のいくつかのフリップフロップ（論理ゲート）に到達する。これらのフリップフロップ同士は、論理重なりがあるとされる。したがって、フリップフロップ（論理ゲート）の数を数えていくと、論理重なり度が高い部分が取得される。
【００９８】
以上のようにして、論理トレース（フォワードトレース、バックワードトレース、または組み合わせトレース）によりフリップフロップ（論理ゲート）同士の論理重なりが取得される。したがって、論理トレースによりフリップフロップ同士の論理重なりが取得されるものであれば、具体的な構成、実現方法は、上述したものに限定されない。
【００９９】
次に、図１３のフローチャートを参照して、図１０のステップＳ３のスキャンチェーン構成の構築処理を説明する。なお、図１３の例においては、すでにスキャンチェーンの形成された図６のスキャンパス回路６１を用いて実行される。
【０１００】
ステップＳ９１において、構成構築処理部４４は、記憶部４２のスキャンチェーン間論理重なり度表をクリアし、ステップＳ９２に進む。スキャンチェーン間論理重なり度表は、スキャンパス回路６１を構成するスキャンチェーン同士において、相関ＳＩ位置にあるフリップフロップ同士の論理重なり度を総当りで計算し、それを表にしたものである。
【０１０１】
ステップＳ９２において、構成構築処理部４４は、記憶部４２に記憶された論理重なり度表および位置情報取得部４３により取得された相関ＳＩ位置情報に基づいて、図６のスキャンパス回路６１のスキャンチェーン同士において、相関ＳＩ位置にあるフリップフロップ同士の論理重なり度を総当りで計算し、それを、記憶部４２のスキャンチェーン間論理重なり度表に記憶し、ステップＳ９３に進む。なお、このとき、論理重なりの有無を、スキャンチェーン間論理重なり表として記憶部４２に記憶させるようにしてもよい。
【０１０２】
構成構築処理部４４は、ステップＳ９３において、スキャンチェーン間の論理重なり度表に基づいて、論理重なり度のできるかぎり低い（最小の）、または論理重なりのないスキャンチェーン同士が組み合わさるように（同じスキャンイン端子に制御されるように）、スキャンチェーンを変更し、ステップＳ９４に進む。これにより、例えば、図７を参照して上述したスキャンチェーン構成のスキャンパス回路１２１が構築される。構成構築処理部４４は、図６のスキャンパス回路６１において、フリップフロップ７１−１と７２−１、フリップフロップ７１−２と７２−２、並びに、フリップフロップ７３−１と７４−１、フリップフロップ７３−２と７４−２に論理重なりが高いとし、スキャンチェーン８２とスキャンチェーン８３を変更し、スキャンチェーンの組み合わせを変更して、スキャンパス回路１２１（図７）を構築する。
【０１０３】
ただし、上述した処理だけでは、論理重なり度が低く（最小に）ならない（論理重なりがなくならない）場合がある。したがって、ステップＳ９４において、構成構築処理部４４は、スキャンパス回路１２１において、論理重なり度の高いスキャンチェーンが存在するか否かを判断し、論理重なり度の高いスキャンチェーンが存在すると判断した場合、ステップＳ９５に進み、構成構築処理部４４は、そのスキャンチェーン内において、論理重なり度の高いフリップフロップの位置を、論理重なり度が最小になるように移動させ、スキャンチェーンの構成（スキャンパス回路）を構築し、処理を終了する。
【０１０４】
なお、以上においては、ステップＳ９３においてスキャンチェーンの組み合わせの変更処理を行っているが、この処理を省略し、スキャンチェーン内のフリップフロップの位置の入れ換え処理だけを行うようにしてもよい。これにより、例えば、図９のスキャンパス回路１４１が構築される。構成構築処理部４４は、図６のスキャンパス回路６１において、フリップフロップ７１−１と７２−１、フリップフロップ７１−２と７２−２、並びに、フリップフロップ７３−１と７４−１、フリップフロップ７３−２と７４−２の論理重なりが高いとし、スキャンチェーン８２において、フリップフロップ７２−１および７２−２とフリップフロップ７２−３および７２−４の位置を入れ換え、スキャンチェーン８４において、フリップフロップ７４−１および７４−２とフリップフロップ７４−３および７４−４の位置を入れ換えて、図９のスキャンパス回路１４１を構築する。
【０１０５】
以上のようにして、論理重なり度（論理重なりの有無）に基づいて、スキャンチェーンの組み合わせを変更すること、または、スキャンチェーン内のフリップフロップの位置を入れ換えることにより、最も適したスキャンチェーンの構成（スキャンパス回路）を構築することができる。
【０１０６】
したがって、図２および図３を参照して上述した入力される値に制限が生じるゲートがスキャンチェーン全体に渡って、最小となるように計算してスキャンチェーンが構築されるので、スキャンパス回路を、従来のように、検出率低下の問題回避のためだけに、リコンフィギャラブル（再構成可能）な構成にする必要はない。また、上述したように構築されたスキャンパス回路１２１または１４１は、スキャンパス回路をリコンフィギャラブルな構成にした場合と異なり、スキャンチェーン構成を選択する回路の追加が不要である。すなわち、スキャンパス回路１２１または１４１においては、予め構成された複数のスキャンチェーン構成の中から好ましいスキャンチェーン構成を選択する必要がなく、スキャンチェーン構成の選択による影響を受けないため、収束性がよく、高速なスキャンテストが実行できる。
【０１０７】
また、従来より、フリップフロップの順序の変更（並び替え）は実行されているが、それらは、フリップフロップの物理的な配置に基づいて実行されていたものであり、論理重なり度に基づいて実行されるものではない。
【０１０８】
以上のように、論理的な重なりがない（すなわち、重なる論理ゲートがない）ようにスキャンチェーンの構成を構築するようにしたので、スキャンイン端子に接続されるスキャンチェーンの数を極限まで増加させることができる。これにより、テスト時間を短縮することができる。
【０１０９】
また、スキャンチェーンの数を増加させた場合であっても、論理的な重なりがないようにスキャンチェーンの構成を決めるようにしたので、回路の対策をせずに、スキャンチェーンの数を増加した場合と比較すると、検出率の降下がない。その結果、検出率を保ったまま、スキャンテスト時間を短縮させることができる。
【０１１０】
また、上記処理においては、すでにスキャンパス回路６１の構築された半導体集積回路を用いて、スキャンパス回路６１を構築（変更）する処理を説明したが、スキャンパス回路６１がまだ構築されていない半導体集積回路を用いて、スキャンパス回路１２１または１４１を構築するようにしてもよい。
【０１１１】
また、上記説明においては、スキャンイン端子１０１および１０２を共有したファンアウト方法により構成されている例を説明したが、スキャンイン端子に代えて、乱数発生部を用いて、スキャンチェーンに値を入力するＰＲＰＧを用いた方法にも適用される。ＰＲＰＧによるランダムパターンをスキャンチェーンに供給するスキャンパス回路に適用すると、各ゲートにおいて、ランダム性の強い値が入力されるようになるため、半導体集積回路において故障の検出率が向上する。
【０１１２】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。この場合、例えば、図５の回路構築装置３１は、図１４に示されるような回路構築装置２０１により構成される。
【０１１３】
図１４において、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２１１は、ＲＯＭ（ＲｅａｄＯｎｌｙ  Ｍｅｍｏｒｙ）  ２１２に記憶されているプログラム、または、記憶部２１８からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２１３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ２１３にはまた、ＣＰＵ２１１が各種の処理を実行する上において必要なデータなどが適宜記憶される。
【０１１４】
ＣＰＵ２１１、ＲＯＭ２１２、およびＲＡＭ２１３は、バス２１４を介して相互に接続されている。このバス２１４にはまた、入出力インタフェース２１５も接続されている。
【０１１５】
入出力インタフェース２１５には、マウス、キーボードなどよりなる入力部２１６、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）などよりなるディスプレイ、並びにスピーカなどよりなる出力部２１７、ハードディスクなどにより構成される記憶部２１８、モデム、ターミナルアダプタなどより構成される通信部２１９が接続されている。通信部２１９は、バスや図示しないネットワークを介しての通信処理を行う。
【０１１６】
入出力インタフェース２１５にはまた、必要に応じてドライブ２２０が接続され、磁気ディスク２２１、光ディスク２２２、光磁気ディスク２２３、もしくは半導体メモリ２２４などが適宜装着され、それから読み出されたコンピュータプログラムが、必要に応じて記憶部２１８にインストールされる。
【０１１７】
一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば、汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１１８】
この記録媒体は、図１４に示すように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク２２１（フレキシブルディスクを含む）、光ディスク２２２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）を含む）、光磁気ディスク２２３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）（商標）を含む）、もしくは半導体メモリ２２４などよりなるパッケージメディアにより構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ２１２や、記憶部２１８などで構成される。
【０１１９】
なお、本明細書において、フローチャートに示されるステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１２０】
【発明の効果】
以上の如く、本発明によれば、スキャンテストにおいて、故障の検出率を向上させ、テスト時間を短縮することができる。
【図面の簡単な説明】
【図１】従来のスキャンパス回路の構成例を示すブロック図である。
【図２】図１のスキャンパス回路により生じる弊害について説明する図である。
【図３】図２の４入力ＡＮＤゲートが入力される値の組み合わせを示す図である。
【図４】従来のスキャンパス回路の他の構成例を示すブロック図である。
【図５】本発明を適用した回路構築装置の構成例を示すブロック図である。
【図６】図５の回路構築装置のスキャンパス回路構築処理に用いられる従来のスキャンパス回路の構成例を示すブロック図である。
【図７】図５の回路構築装置のスキャンパス回路構築処理により構築されたスキャンパス回路の構成例を示すブロック図である。
【図８】図７のスキャンパス回路のＡＮＤゲートに入力される値の組み合わせを示す図である。
【図９】図５の回路構築装置のスキャンパス回路構築処理により構築されたスキャンパス回路の他の構成例を示すブロック図である。
【図１０】図５の回路構築装置のスキャンパス回路構築処理を説明するフローチャートである。
【図１１】図１０のステップＳ１の論理トレース処理を説明するフローチャートである。
【図１２】図１０のステップＳ１の論理トレース処理の他の例を説明するフローチャートである。
【図１３】図１０のステップＳ３のスキャンチェーン構成構築処理を説明するフローチャートである。
【図１４】本発明を適用した回路構築装置の他の構成例を示すブロック図である。
【符号の説明】
３１  回路構築装置，４１  論理トレース処理部，４２  記憶部，４３  位置情報取得部，４４  構成構築処理部，６１  スキャンパス回路，７１−１乃至７１−４４，７２−１乃至７２−４，７３−１乃至７３−４，および７４−１乃至７４−４  フリップフロップ，８１乃至８４  スキャンチェーン，９１  ＡＮＤゲート，９２  ＮＡＮＤゲート，１０１，１０２  スキャンイン端子，１２１  スキャンパス回路，１４１  スキャンパス回路
【図１】
2004239751.tif 000003
【図２】
2004239751.tif 000004
【図３】
2004239751.tif 000005
【図４】
2004239751.tif 000006
【図５】
2004239751.tif 000007
【図６】
2004239751.tif 000008
【図７】
2004239751.tif 000009
【図８】
2004239751.tif 000010
【図９】
2004239751.tif 000011
【図１０】
2004239751.tif 000012
【図１１】
2004239751.tif 000013
【図１２】
2004239751.tif 000014
【図１３】
2004239751.tif 000015
【図１４】
2004239751.tif 000016