(57)【要約】集積回路（ＩＣ）装置（１０）は、デジタル回路部分（１２０）を有する集積回路（１００）を具えており、デジタル回路部分（１２０）は複数のデジタル出力端（１２２）を有し、各デジタル出力端は、集積回路（１００）のテストモードにおいてテスト結果を生じるように構成配置されている。集積回路装置（１０）は更に、スペースコンパクション論理回路（１４０）を具えており、このスペースコンパクション論理回路（１４０）は、複数のコンパクションドメイン（１６２）を有するスペースコンパクション回路網（１６０）を具えており、各コンパクションドメイン（１６２）は、複数のテスト結果を他のテスト結果に圧縮するように構成され、スペースコンパクション論理回路（１４０）は更に、前記複数のデジタル出力端（１２２、２１０）と前記スペースコンパクション回路網（１６０）との間に結合されたスプレッド回路網（１５０）を具え、このスプレッド回路網は、前記デジタル出力端（１２２、２１０）からの各テスト結果を複数のコンパクションドメイン（１６２）に再現するように構成されている。ＩＣ１００上に、又はその外部に、例えば、テスト装置上或いはテストインタフェース上に配置しうるこのスペースコンパクション論理回路（１４０）は、スプレッド回路網を用いないスペースコンパクション論理回路に比べて、欠陥キャンセル又は欠陥エイリアシングのおそれを低減させる。
2009516164.tif 000002
【特許請求の範囲】
【請求項１】
集積回路と、スペースコンパクション論理回路とを具える集積回路装置であって、
前記集積回路が複数のデジタル出力端を有し、各デジタル出力端が、この集積回路のテストモードにおいてテスト結果を生じるように構成配置されており、
前記スペースコンパクション論理回路が、複数のコンパクションドメインを有するスペースコンパクション回路網を具え、各コンパクションドメインは、複数のテスト結果を他のテスト結果に圧縮するように構成配置されており、
前記スペースコンパクション論理回路は更に、前記複数のデジタル出力端と前記スペースコンパクション回路網との間に結合されたスプレッド回路網を具え、このスプレッド回路網は、前記デジタル出力端からの各テスト結果を複数のコンパクションドメインに再現するように構成配置されているようにした集積回路装置。
【請求項２】
請求項１に記載の集積回路装置において、各コンパクションドメインが排他的論理ゲートの回路網を有している集積回路装置。
【請求項３】
請求項１又は２に記載の集積回路装置において、各コンパクションドメインがデジタル出力端の独自の組に結合されている集積回路装置。
【請求項４】
請求項１〜３のいずれか一項に記載の集積回路装置において、各コンパクションドメインがその更なるテスト結果を生じる出力端を有し、前記集積回路は更に、この集積回路のテストデータ出力端に向けてデータを直列的にシフトさせるシフトレジスタを有し、前記コンパクションドメインのそれぞれの出力端がこのシフトレジスタのセルにそれぞれ結合されている集積回路装置。
【請求項５】
請求項１〜３のいずれか一項に記載の集積回路装置において、この集積回路装置が更に、自動テスト装置と、前記集積回路をこの自動テスト装置に結合するロードボードとを有するテスト手段を具えており、このテスト手段は更に、スペースコンパクション論理回路を具えている集積回路装置。
【請求項６】
請求項１〜５のいずれか一項に記載の集積回路装置において、前記スプレッド回路網は前記デジタル出力端に、設定自在に結合されるようになっている集積回路装置。
【請求項７】
複数のデジタル出力端を有する集積回路をテストするスペースコンパクション論理回路を設計する設計方法であって、このスペースコンパクション論理回路は、
ｍ個の出力端を有する複数のコンパクションドメインを具えるスペースコンパクション回路網であって、各コンパクションドメインが複数のテスト結果を他のテスト結果に圧縮するように構成配置されている当該スペースコンパクション回路網と、
前記複数のデジタル出力端と前記スペースコンパクション回路網との間を結合するｎ個の入力端を有するスプレッド回路網であって、このスプレッド回路網は前記複数のデジタル出力端からのテスト結果をｆ個のコンパクションドメインに再現させるように構成配置されている当該スプレッド回路網と
を具え、ｆ、ｎ及びｍは正の整数とし、ｎはｍよりも大きく、ｍはｆよりも大きくなるようにした設計方法において、この設計方法が、
一組のビットベクトルを発生させ、各ビットベクトルがｍ個のビットを有し、各ビットが、前記スプレッド回路網の入力端から前記スペースコンパクション回路網への導電路の存在を表し、１つのビットベクトル当たりの導電路の総数をｆとするステップと、
前記一組のビットベクトルからのｎ個のビットベクトルを組み合わせてｎ・ｍの大きさのマトリックスにし、ビットベクトルの方向に対し垂直なマトリックスの方向における前記導電路の個数を制限し、前記マトリックスが前記スペースコンパクション論理回路の設計を表すようにするステップと
を具える設計方法。
【請求項８】
請求項７に記載の設計方法において、前記一組のビットベクトルからのｎ個のビットベクトルを組み合わせてｎ・ｍの大きさのマトリックスにし、ビットベクトルの方向に対し垂直なマトリックスの方向における前記導電路の個数を制限し、前記マトリックスが前記スペースコンパクション論理回路の設計を表すようにする前記ステップが、前記導電路の個数を最小にするステップを有するようにする設計方法。
【請求項９】
集積回路の複数のデジタル出力端に接続される複数の入力端であって、これらデジタル出力端の各々は集積回路のテストモードでテスト結果を生じるようになっているこれら入力端と、
スペースコンパクション論理回路であって、このスペースコンパクション論理回路が、
各コンパクションドメインが複数のテスト結果を他のテスト結果に圧縮するように構成配置されている複数のコンパクションドメインを有するスペースコンパクション回路網と、
前記複数の入力端と前記スペースコンパクション回路網との間に結合されたスプレッド回路網であって、このスプレッド回路網が、前記デジタル出力端からの各テスト結果を複数のコンパクションドメインに再現させるように構成配置された当該スプレッド回路網とを有する
当該スペースコンパクション論理回路と
を具えるテスト装置。
【請求項１０】
請求項９に記載のテスト装置において、各コンパクションドメインが排他的論理ゲートの回路網を有しているテスト装置。
【請求項１１】
請求項９又は１０に記載のテスト装置において、各コンパクションドメインがデジタル出力端の独自の組に結合されるように構成配置されているテスト装置。
【請求項１２】
複数のデジタル出力端を有する集積回路を、この集積回路をテストするテスト装置の複数の入力端に結合するインタフェースであって、このインタフェースがスペースコンパクション論理回路を有し、このスペースコンパクション論理回路は、
各コンパクションドメインが複数のテスト結果を他のテスト結果に圧縮するように構成配置されているとともに、前記他のテスト結果を前記テスト装置の入力端に供給する出力端を有しているようにした複数のコンパクションドメインを有するスペースコンパクション回路網と、
前記複数の入力端と前記スペースコンパクション回路網との間に結合されたスプレッド回路網であって、このスプレッド回路網が、前記デジタル出力端からの各テスト結果を複数のコンパクションドメインに再現させるように構成配置された当該スプレッド回路網と
を有しているインタフェース。
【請求項１３】
請求項１２に記載のインタフェースにおいて、各コンパクションドメインが排他的論理ゲートの回路網を有しているインタフェース。
【請求項１４】
請求項１２又は１３に記載のインタフェースにおいて、各コンパクションドメインがデジタル出力端の独自の組に結合されるように構成配置されているインタフェース。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路装置における集積回路（ＩＣ）のデジタル出力端からのテスト結果を圧縮するスペースコンパクション論理回路を有する当該集積回路装置に関するものである。
【０００２】
本発明は更に、このようなスペースコンパクション論理回路を設計する方法にも関するものである。
【背景技術】
【０００３】
ＩＣをテストすることは、急速にＩＣの製造費における重用因子となりつつある。その主たる理由の１つは、複雑なＩＣの場合にテストに時間がかかるということである。その主たる理由は、多量のテスト入出力データを、テスト状態にあるＩＣとやりとりする必要がある為である。従って、このデータのやりとりに含まれるデータの大きさを小さくする手段がかなり注目されている。
【０００４】
例えば、デジタルテスト入力データを圧縮するテストの解決策が提案されており、ＩＣはテスト入力データをその元の大きさに戻すオンボードの伸長器を有する。同様に、テスト状態にあるＩＣのデジタルテスト出力はオンボードの圧縮器により圧縮され、ＩＣのテスト結果がこの圧縮形態で外部に生ぜしめられる。この解決手段の一例は、IEEE ETW2003（Proc. Of the Eight IEEE European Test Workshop）の論文：“Parity-based output compaction for core-based SOCs”（Sinanoglu 氏等著）から見いだすことができる。このような解決手段では、テスト状態にあるＩＣに与えられるテスト入力、例えばテストベクトルに対する各圧縮テスト応答が解析されて、与えられたテストベクトルが欠陥検出を行ったかどうかを決定する。
【０００５】
圧縮したテスト結果を用いる場合、特に主として排他的ＯＲ（ＸＯＲ）論理ゲートに基づくとともにパリティートリーに基づく圧縮器を用いる場合に、少なくとも幾つかの解を失うおそれがあるという欠点がある。従って、圧縮器に供給されるＩＣの出力に偶数個の誤りビットを生ぜしめる欠陥が生じるか、又は複数の欠陥が同時に生じることにより、誤りビットを互いに相殺させるおそれがある。又、複数の欠陥がスペースコンパクション論理回路の出力端に同じ誤りビットを生じる場合に（このことは、圧縮されたテスト応答が、複数の誤りビットを特定の欠陥に割り当てる可能性がなくこれら複数の誤りビットが発生していることのみを表すということを意味する）生じる欠陥エイリアシングの為に、欠陥の位置の決定がより一層困難となるおそれがある。
【非特許文献１】IEEE ETW2003（Proc. Of the Eight IEEE European Test Workshop）の論文：“Parity-based output compaction for core-based SOCs”（Sinanoglu 氏等著）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、テストの解決策を改善した頭書に記載の集積回路装置を提供することにある。
【０００７】
本発明の更なる目的は、このような集積回路装置に対するスペースコンパクション論理回路を設計する方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の観点によれば、集積回路と、スペースコンパクション論理回路とを具える集積回路装置であって、前記集積回路が複数のデジタル出力端を有し、各デジタル出力端が、この集積回路のテストモードにおいてテスト結果を生じるように構成配置されており、前記スペースコンパクション論理回路が、複数のコンパクションドメインを有するスペースコンパクション回路網を具え、各コンパクションドメインは、複数のテスト結果を他のテスト結果に圧縮するように構成配置されており、前記スペースコンパクション論理回路は更に、前記複数のデジタル出力端と前記スペースコンパクション回路網との間に結合されたスプレッド回路網を具え、このスプレッド回路網は、前記デジタル出力端からの各テスト結果を複数のコンパクションドメインに再現するように構成配置されているようにした集積回路装置を提供する。
【０００９】
スペースコンパクション論理回路を、ＸＯＲゲートのような排他的論理ゲートの別々のトリーとしうる複数のドメインに分割し、各ドメインがスプレッド回路網を介してＩＣのデジタル出力のサブセットを受けるようにすることにより、より詳細なＩＣテスト結果がスペースコンパクション論理回路の出力端に得られるようになる。特に、オンボードＩＣの欠陥の可観測性及び検出能力の双方又は何れか一方を阻害する欠陥相殺及び欠陥エイリアシングのおそれは減少する。その理由は、この欠陥相殺及び欠陥エイリアシングはある幾つかのコンパクションドメインにおいてのみ生じるおそれがあり、他のコンパクションドメインは、欠陥相殺及び欠陥エイリアシングとなる欠陥のサブセットにのみ感応し、これにより、これらのドメインにこれらの不所望な影響が発生するのを阻止する為である。
【００１０】
この理由のために、各コンパクションドメインをデジタル出力端の独自の組に結合するのが好ましい。その理由は、このようにすることにより、全てのドメインにおいて欠陥相殺及びエイリアシングが生じるおそれが最小になる為である。
【００１１】
スプレッド回路網はＩＣのデジタル出力端に設定自在に結合し、ＩＣの機能（すなわち、動作）モードでスペースコンパクション論理回路の側路を容易にするようにするのが好ましい。
【００１２】
スペースコンパクション回路網はＩＣ上に位置させ、その出力がＩＣの少なくともある幾つかのピンで直接観測しうるようにすることができる。この場合、テスト結果が、例えば、テストクロックの各サイクル後に容易に得られるようになり、これによりテスト結果の高速処理を容易にするという利点が得られる。
【００１３】
或いはまた、各コンパクションドメインがその更なるテスト結果を生じる出力端を有し、前記集積回路は更に、この集積回路のテストデータ出力端に向けてデータを直列的にシフトさせるシフトレジスタを有し、前記コンパクションドメインのそれぞれの出力端がこのシフトレジスタのセルにそれぞれ結合されているようにする。このようにすることにより、ＩＣは１つのみのテストデータ出力ピンを有すれば足り、従って、このことが、専用のテストピンが必要である場合にＩＣのピン数を減少させるのに役立つという利点が得られる。
【００１４】
スペースコンパクション論理回路は、ＩＣの外部に、例えば、自動テスト装置とこのテスト装置に集積回路を結合するロードボードとを有するテスト手段の一部として位置させることもでき、この場合、スペースコンパクション論理回路はロードボード又はテスト装置上に配置させる。
【００１５】
本発明の他の観点によれば、複数のデジタル出力端を有する集積回路をテストするスペースコンパクション論理回路を設計する設計方法であって、このスペースコンパクション論理回路は、ｍ個の出力端を有する複数のコンパクションドメインを具えるスペースコンパクション回路網であって、各コンパクションドメインが複数のテスト結果を他のテスト結果に圧縮するように構成配置されている当該スペースコンパクション回路網と、前記複数のデジタル出力端と前記スペースコンパクション回路網との間を結合するｎ個の入力端を有するスプレッド回路網であって、このスプレッド回路網は前記複数のデジタル出力端からのテスト結果をｆ個のコンパクションドメインに再現させるように構成配置されている当該スプレッド回路網とを具え、ｆ、ｎ及びｍは正の整数とし、ｎはｍよりも大きく、ｍはｆよりも大きくなるようにした設計方法において、この設計方法が、一組のビットベクトルを発生させ、各ビットベクトルがｍ個のビットを有し、各ビットが、前記スプレッド回路網の入力端から前記スペースコンパクション回路網への導電路の存在を表し、１つのビットベクトル当たりの導電路の総数をｆとするステップと、前記一組のビットベクトルからのｎ個のビットベクトルを組み合わせてｎ・ｍの大きさのマトリックスにし、ビットベクトルの方向に対し垂直なマトリックスの方向における前記導電路の個数を制限し、前記マトリックスが前記スペースコンパクション論理回路の設計を表すようにするステップとを具える設計方法を提供する。
【００１６】
この方法によれば、本発明の集積回路装置を設計しうる。
【発明を実施するための最良の形態】
【００１７】
以下に本発明の実施例を図面につき詳細に説明するが、本発明はこれらの実施例に限定されるものではない。
【００１８】
図面は線図的なものであり実際のものに正比例して描いていないことを理解すべきである。更に、全図にわたり、同じ又は類似の部分に同じ符号を付してあることをも理解すべきである。
【００１９】
図１は、デジタル部分１２０を有するＩＣ１００を具えるＩＣ装置１０を示す。デジタル部分１２０はデジタル出力端１２２を有し、これらデジタル出力端はスペースコンパクション（圧縮）論理回路１４０に導電接続されている。これらデジタル出力端１２２は、テストモード又はその他のデータ出力モードでＩＣ１００の内部を検査するスキャンチェーンの出力端とすることができる。スペースコンパクション論理回路１４０は、スプレッド回路網１５０と、スペースコンパクション回路網１６０とを具えており、スペースコンパクション回路網１６０は複数のスペースコンパクションドメイン１６２を有し、各スペースコンパクションドメインはＸＯＲツリーとして構成されているが、他の構成も同様に可能である。スプレッド回路網１５０は、デマルチプレクサ１２４をそれぞれ経てデジタル出力端１２２に結合されており、これらデマルチプレクサ１２４はテストイネーブル信号Ｔ＿ＥＮに応答する。このテストイネーブル信号が存在しない場合には、デマルチプレクサ１２４により、例えば、デジタル出力端１２２からの信号をＩＣピン１８０に回送することにより、スペースコンパクション論理回路１４０をデジタル出力端１２２からの導電性信号路から除外する。本発明は、図示のデマルチプレクサ１２４の例に限定されるものではなく、他の種類のスイッチ又はその他の機構も、ＩＣ１００をテストモードにするのに等しく適用しうる。
【００２０】
スプレッド回路網１５０は、各デジタル出力を複数回再現（複製）し、その回数に対応する個数のスペースコンパクションドメイン１６２にこのような再現出力を与えるように構成されている。好ましくは、各スペースコンパクションドメイン１６２がスプレッド回路網１５０から独自の（区別しうる）組の入力を受けるように、すなわち、各スペースコンパクションドメイン１６２がデジタル出力端１２２の独自のサブセットに結合されるようにする。２つのスペースコンパクションドメイン１６２は互いに同じ組の入力を受けない為、全てのスペースコンパクションドメイン１６２が欠陥（フォルト）キャンセル又はエイリアシングを被る機会が著しく減少する。スペースコンパクションドメイン１６２の各々における入力端の個数は互いに同じにすることができるが、必ずしもこのようにする必要はない。
【００２１】
スペースコンパクション回路網１６０の入力端の個数（すなわち、全てのスペースコンパクションドメイン１６２の入力端の合計）と、デジタル出力端１２２の個数との間の比が、スプレッド回路網１５０のスプレッド率、すなわち増倍率を決定する。例えば、デジタル部分１２０が１００個のデジタル出力端を有しており、スペースコンパクション回路網１６０が５００個の入力端を有している場合には、スプレッド回路網１５０のスプレッド率は５である。ルーティングの目的では、このスプレッド率をできるだけ低く保って、ＩＣ装置の設計におけるルーティングの混雑を回避するようにするのが好ましい。このことは、スペースコンパクション論理回路１４０が図１に示すようにＩＣ上に位置している場合に特に適している。
【００２２】
図１においては、ＩＣ１００が更にシフトレジスタ１７０を有し、このシフトレジスタ１７０にスペースコンパクション回路網１６０の出力端が結合されている。テストモードにおいては、IEEE1149.1（すなわち、ＪＴＡＧ）に準拠したテストアクセスポートコントローラ（図示せず）により制御しうるこのシフトレジスタ１７０が、スペースコンパクション回路網１６０から捕捉されたテスト結果を、IEEE1149.1に準拠したテストアクセスポート（図示せず）の一部としうるテストデータ出力（ＴＤＯ）ピン１７２に転送し、テスト結果の監視をＩＣ１００の外部で容易に行いうるようにする。これにより、自動テスト装置（ＡＴＥ）のような外部装置を接続する必要があるＩＣピンの個数を制限し、これによりこのようなピンへの損傷のおそれを減少させる。
【００２３】
強調すべきことは、シフトレジスタ１７０を設けることは本発明にとって必須のことではないということである。これに代えて、スペースコンパクション回路網１６０の出力端におけるテスト結果をＩＣピン１８０に転送し、テスト結果の監視をＩＣ１００の外部で容易に行いうるようにすることもできる。この場合、シフトレジスタに基づく解決策に比べて多くのピンを接続する必要があるが、テスト結果がＩＣ１００の外部でより急速に得られるようになり、その結果、テスト時間及び費用が低減されるという利点が得られる。
【００２４】
更に強調すべきことは、本明細書及び特許請求の範囲における用語「集積回路装置」は、集積回路の実施例を独立して（すなわち、外部テスト装置を存在させずに）含むことを意図しているということである。
【００２５】
図２は、本発明によるテスト装置２２０をＩＣ２００と一緒に示す本発明のＩＣ装置２０を示す。テスト装置２２０は複数の入力端２２２を有し、例えば、これら入力端はインタフェース２８０、例えばロードボードの相互接続端２８２を経てＩＣ２００のデジタル出力端２１０に導電結合されている。ＩＣ装置２０においては、図１で詳細に説明したようなスペースコンパクション論理回路１４０がテスト装置２２０の回路基板上に位置している。これにより、追加のハードウェア（すなわち、スペースコンパクション論理回路１４０）をＩＣ２００に加える必要がないという利点が得られる。圧縮したテスト結果を、他の処理及び解釈の双方又は何れか一方のために、プロセッサ２２４に転送しうる。
【００２６】
或いはまた、本発明のスペースコンパクション論理回路１４０をインタフェース２８０上に位置させた従来のテスト装置を用いることができる。このようにすることにより、テスト装置の融通性を改善する。その理由は、インタフェース２８０は、テスト装置よりも容易に、従って、廉価に変更又は製造しうる為である。
【００２７】
しかし、好適実施例では、スペースコンパクション論理（ＳＣＬ）回路１４０がＩＣ１００上に位置するようにするのが好ましい。ＩＣ１００のようなＩＣのテストの持続時間は代表的に、テスト中にアクセス可能なピンの個数に依存する。使用可能なピンが制限されている場合には、利用可能な少数のピンに僅かなスキャンチェーンしか結合できず、長いスキャンチェーンはデジタル部分の内部で用いて、全テスト時間に加わる充分なテストカバレッジを容易に達成しうるようにする。スペースコンパクション論理回路１４０が存在することは、より多くの且つより短いスキャンチェーンをＩＣ設計に含めることができ、従って、このようなＩＣのテストの持続時間を改善することを意味する。
【００２８】
スペースコンパクション論理（ＳＣＬ）回路１４０は以下のようにして設計しうる。ＩＣ１００はｎ個のデジタル出力端１２２を有し、ＩＣのテスト中、これらの出力端でテストの応答が監視されるようにする。ｎ個のデジタル出力端１２２は例えば、前述したようにスキャンチェーンの出力端又はデータの出力端とする。図１では、ＩＣ１００のｎ個のデジタル出力端１２２が、ｎ個のテスト応答ビットを各クロックサイクルでｍ個のビットに圧縮するためのスペースコンパクション論理回路１４０に接続されている。
【００２９】
スプレッド回路網１５０では、ｎ個のＳＣＬ入力信号の各々が、ｆファンアウトの分岐１５２に供給するためのファンアウトステムとして用いられている。従って、スプレッド回路網１５０は、ｎ個の入力とｎ・ｆ個の出力とを有する。スプレッド回路網１５０のｎ・ｆ個の出力は、テスト応答をｍ個の出力ビットに圧縮するスペースコンパクション回路網１６０に対する入力として用いられる。スペースコンパクション回路網１６０は、Ｘ（Ｎ）ＯＲゲートのｍ個のドメイン、すなわち、ｍ個のＸ（Ｎ）ＯＲトリーを具えており、ｎ・ｆ個の入力及びｍ個の出力を有する。スペースコンパクション回路網１６０における各ドメイン１６２は、１つの出力と、
【数１】
2009516164.tif 000003
個の入力とを有し、ｍ1 ・ｇ1 ＋ｍ2 ・ｇ2 ＝ｎ・ｆ及びｍ1 ＋ｍ2 ＝ｍとなる。ＳＣＬ回路１４０はｎビットをｍビットに圧縮し、従って、その圧縮比はｃ＝ｎ／ｍである。図１では、一例として、ＳＣＬ回路１４０の全体をＩＣ１００上に構成してある。ＳＣＬ回路１４０はチップ以外に、例えば、図２につき前述したロードボード２８０上に、又は自動テスト装置２２０の内部に配置することもできる。
【００３０】
ＳＣＬ回路１４０の全ての入力は互いに同じファンアウトｆを有することができ、一方、スペースコンパクション回路網１６０におけるＸＯＲトリーに基づくドメイン１６２の各々に対する入力数もほぼ等しい（ｇ1 又はｇ2 ）。このように選択するのが好ましい理由は、これによりＳＣＬ回路１４０の形成を容易にする為である。しかし、これは好適実施例であって、必ずしもこのようにする必要はない。
【００３１】
ｎ個の入力及びｍ個の出力を有するＳＣＬ回路１４０の関数はｎ列ｍ行のマトリックスＭで表わすことができる。要素ｍijは行ｉ及び列ｊにおけるマトリックスＭの要素に相当する。マトリックスは以下の特徴を有している。
・  ｍij＝１は、ＳＣＬ回路の入力端ｉから、スプレッド回路網及びスペースコンパクション回路網を通って、ＳＣＬ回路の出力端ｊへ通じる接続が存在することを表わしており、ｍij＝０は、このような接続が存在しないことを表わしている。
・  各行はＳＣＬ回路の１つの入力に対応する。スプレッド回路網１５０においては、ＳＣＬ回路の各入力がｆファンアウトの分岐に供給される。従って、各行はｆ個の１と、ｍ−ｆ個の０とを有する。
・  各列はＳＣＬ回路の１つの出力に対応する。スペースコンパクション回路網１６０においては、ＳＣＬ回路の各出力端がｇ個の入力端に接続されている（ここで、ｇはｇ1 又はｇ2 である）。従って、各行はｇ個の１とｎ−ｇ個の０とを有している。
【００３２】
【数２】
2009516164.tif 000004
である為、ＳＣＬ回路のいかなる入力のｆファンアウトの分岐の各々も互いに異なるＸＯＲトリーに接続されている。このことは、ｆ≦ｍの場合に保証される。ＳＣＬ回路の入力端からＳＣＬ回路の出力端に転送される情報量を最大にするためには、ＳＣＬ回路及び対応するマトリックスに以下の制約が課せられる。
・  全ての列を識別しうるようにする。従って、ＳＣＬ回路の各出力は、ＳＣＬ回路の入力の互いに異なる組からの情報を有する。
・  何れの２つの列間の重複（オーバーラップ）も最小にする。これにより、ＳＣＬ回路の各出力端における情報がＳＣＬ回路の何れかの他の出力端にも存在する量を最小にする。２つの列間の重複は以下のように規定される。
‐  ２ビットの場合、重複は、
重複(0,0) ＝重複(1,1) ＝１及び重複(0,1) ＝重複(1,0) ＝０
として規定される。これはＸＮＯＲ関数に対応し、従って、
重複(a,b) ＝ａＸＮＯＲｂ
となる。
‐  ２ビットのベクトルの場合、重複(a,b) は重み(aＸＮＯＲb)として規定される。ビットベクトルの重みは、１であるベクトル中のビットの個数を表わしている。例えば、重複(0100,0110) ＝重み(0100 ＸＮＯＲ 0110) ＝重み(1101)＝３である。ビットベクトル0100及び0110は共に３ビットを有している。
圧縮比を最大にするためには、デジタル出力の個数ｎを比較的大きくするとともに、ＳＣＬ回路の出力の個数ｍを比較的小さくする必要がある。更に、ＩＣ回路のレイアウトを決定する際のＳＣＬ回路の経路選択を容易にするために、ファンアウトの数ｆを小さく保つ必要がある。実際には、ｎをＯ(10)〜Ｏ(1000)の範囲内とし、ｍをＯ(1) 〜Ｏ(10)の範囲内とし、ｆをＯ(1) の範囲内とする。
【００３３】
ＳＣＬ回路のマトリックスＭにおいて、各列は、ｇ個のビットが１であるｎ個のビットを有し、各行は、ｆ個のビットが１であるｍ個のビットを有する。従って、個々の列及び個々の行の総数はそれぞれ、
【数３】
2009516164.tif 000005
に相当する。実際には、ｎ及びｇが比較的大きい為に、
【数４】
2009516164.tif 000006
は極めて大きく、一方、ｍ及びｆは比較的小さい為に、
【数５】
2009516164.tif 000007
はかなり小さくなる。例えば、ｎ＝１０００、ｍ＝１００、ｆ＝２及びｇ＝ｎ・ｆ／ｍ＝１０００・２／１００＝２０の場合、
【数６】
2009516164.tif 000008
となる。従って、実際には、
【数７】
2009516164.tif 000009
を列挙することはできるが、
【数８】
2009516164.tif 000010
を列挙することは不可能である。この特性は、ＳＣＬ回路１４０を有効に形成するのに以下のように適用する。
【００３４】
所定のパラメータｎ、ｍ及びｆに対し、ＳＣＬ回路１４０を図３のフローチャートを参照して以下のように設計する。
【００３５】
ステップ３１０において、ｆ個の１とｍ−ｆ個の０とを含むｍビット幅の全てのビットベクトルの組Ｃを発生させ、ステップ３２０において、組ＣからマトリックスＭを構成する。マトリックスＭの行は組Ｃからのビットベクトルである。これらのベクトルは、マトリックスＭにおける何れの２つの列間の重複も最小となるように組Ｃから選択する。ステップ３１０及び３２０の詳細は以下の通りである。
【００３６】
組Ｃは、ｆ個の１とｍ−ｆ個の０とを含むｍビット幅の全てのビットベクトルを有している。
【００３７】
［数５］個の可能なベクトルがあり、従って、
【数９】
2009516164.tif 000011
となる。組ＣはマトリックスＱに表われ、Ｃにおける各ベクトルｃi がＱにおける行ｉに相当するようになる。マトリックスＱは、ｍ個の列と、［数５］個の行とを有し、各行はｆ個の１を含む。更に、マトリックスＱの各列は
【数１０】
2009516164.tif 000012
個の１を有するようになる。（この個数は、或る１つ列の位置に１を有するとともに、残りのｍ−１個の列の位置に亘って任意に分布されている残りのｆ−１個の１を有している行の個数に相当する。）
【００３８】
マトリックスＭはマトリックスＱ中の行から構成されている。マトリックスＱからの行ｉがマトリックスＭ中に生じる回数をｎi で表すものとする。マトリックスＭはｎ個の行を有する為、
【数１１】
2009516164.tif 000013
となる。
【００３９】
行ｉ及び列ｊにおけるマトリックスＱの要素をｑijで表すものとする。マトリックスＭにおける各列がｇ個の１と、ｎ−ｇ個の０とを有すると、
【数１２】
2009516164.tif 000014
となる。式（１）及び（２）から、［数５］個の未知数（ｎi ）のｍ＋１個の一次方程式の系が得られる。この系は、
【数１３】
2009516164.tif 000015
の場合に、（複数の解法で）解決しうる。
【００４０】
マトリックスＭにおける何れの２つの列間の重複も最小にする必要があり、従って、マトリックスＱからの行がマトリックスＭ中に生じる回数を最小にする必要がある。従って、
【数１４】
2009516164.tif 000016
を最小にする制約がある。マトリックスＱには、同じ列の位置に１を有する
【数１５】
2009516164.tif 000017
個の行がある為、
【数１６】
2009516164.tif 000018
が得られる。この制約は、適切な解決策を選択しうるようにする。
【００４１】
ｆ＝１の場合には、ＳＣＬ回路１４０はスプレッド回路網１５０を有さず、スペースコンパクション回路網１６０のみから成る。この場合には、ＳＣＬ回路の各入力端がこのＳＣＬ回路の１つの出力端に接続され、従って、ＳＣＬ回路の各出力端はＳＣＬ回路の入力端の独自の組に接続される。
【００４２】
ｆ＞１の場合には、［数１６］＝１であり、その結果ｇ≦ｈ、従って、
【数１７】
2009516164.tif 000019
となると、重複が最小となる。この条件を条件ｍ＜ｎと組み合わせると、
【数１８】
2009516164.tif 000020
が得られ、この［数１８］は一次方程式の解決可能な系を得るのにも必要であるということを銘記すべきである。マトリックスＱは、［数５］個の行と、ｍ個の列とを有する。各行はｆ個の１を有し、各列は［数１０］個の１を有する。マトリックスＱにおけるいかなる２つの列間の最大の重複も、
【数１９】
2009516164.tif 000021
となる。この後者の結果は、２つの特定の列の位置に１を有し、従って、残りのｍ−２個の列の位置に亘って任意に分布された残りのｆ−２個の１を有する行の個数を計算することにより得られる。マトリックスＭにおけるいかなる２つの列間の最大の重複も、
【数２０】
2009516164.tif 000022
となる。
【００４３】
重複が最小である場合には、圧縮比は、
【数２１】
2009516164.tif 000023
となる。従って、ｆが大きい場合に圧縮比が大きくなり、ｆ＝ｍ／２の場合に圧縮比は最大となる。しかし、実際には、前述したように、ＳＣＬ回路１４０を配置する必要があるＩＣ１００のプレース‐アンド‐ルート中の混雑を回避する為には、ｆを小さく選択する必要がある。
【００４４】
本発明の設計方法を用い、ｎ＝１０、ｍ＝４及びｆ＝２としたＳＣＬ回路１４０を設計する一例は以下の通りである。本発明の方法の教示から、ｇ＝ｎ・ｆ／ｍ＝１０・２／４＝５及び
【数２２】
2009516164.tif 000024
が得られる。従って、
ａ）２つの１を有する４ビット幅の全てのビットベクトルの組Ｃは濃度
【数２３】
2009516164.tif 000025
を有する。Ｃ＝｛(1100),(1010),(1001),(0110),(0101),(0011) ｝である。
ｂ）６個の未知数のｍ＋１＝５個の式の系は以下の通りである。
ｎ1 ＋ｎ2 ＋ｎ3 ＋ｎ4 ＋ｎ5 ＋ｎ6 ＝ｎ＝１０
ｎ1 ・１＋ｎ2 ・１＋ｎ3 ・１＋ｎ4 ・０＋ｎ5 ・０＋ｎ6 ・０
＝ｎ1 ＋ｎ2 ＋ｎ3 ＝ｇ＝５
ｎ1 ・１＋ｎ2 ・０＋ｎ3 ・０＋ｎ4 ・１＋ｎ5 ・１＋ｎ6 ・０
＝ｎ1 ＋ｎ4 ＋ｎ5 ＝ｇ＝５
ｎ1 ・０＋ｎ2 ・１＋ｎ3 ・０＋ｎ4 ・１＋ｎ5 ・０＋ｎ6 ・１
＝ｎ1 ＋ｎ4 ＋ｎ6 ＝ｇ＝５
ｎ1 ・０＋ｎ2 ・０＋ｎ3 ・１＋ｎ4 ・０＋ｎ5 ・１＋ｎ6 ・１
＝ｎ3 ＋ｎ5 ＋ｎ6 ＝ｇ＝５
この系を解くと、以下の式がえられる。
ｎ1 ＝ｎ6 、ｎ2 ＝ｎ5 、ｎ3 ＝ｎ4 及びｎ1 ＋ｎ2 ＋ｎ3 ＝５
ｃ）
【数２４】
2009516164.tif 000026
である為、マトリックスＭにおける各行は、最大２回生じる。従って、適切な解は、
解１：ｎ1 ＝１、ｎ2 ＝２、ｎ3 ＝２、ｎ4 ＝２、ｎ5 ＝２、ｎ6 ＝１
解２：ｎ1 ＝２、ｎ2 ＝１、ｎ3 ＝２、ｎ4 ＝２、ｎ5 ＝１、ｎ6 ＝２
解３：ｎ1 ＝２、ｎ2 ＝２、ｎ3 ＝１、ｎ4 ＝１、ｎ5 ＝２、ｎ6 ＝２
である。解１によるマトリックスＭは、
【数２５】
2009516164.tif 000027
である。このマトリックスにおける行は、任意に再順序付けしうることに注意すべきである。
ｄ）マトリックスＭにおける列間の最大の重複は、
【数２６】
2009516164.tif 000028
である。重複を低減させるためには、全ての行を独自のものとする必要があり、且つ［数１７］を満足させる必要がある。最大の圧縮はｆ＝ｍ／２の場合に達成される。ｍ＝４及びｆ＝２の場合、ｎ≦６となり、これは条件ｎ＝１０と矛盾する。従って、ｎ＝１０及びｍ＝４に対しＳＣＬ回路の出力間の重複が最小となるようにこのＳＣＬ回路１４０を構成することができない。しかし、このことは、ｍを増大させることにより、例えば、ｍ＝５及びｆ＝２を選択することにより、達成しうる。
【００４５】
本発明によるＳＣＬ回路１４０の欠陥検出能力は以下の通りである。
・  マトリックスＭにおける全ての行が０でない場合には、常に１つの欠陥が検出される。ファンアウトｆの場合、ＳＣＬ回路のｆ個の出力端で欠陥が監視される。
・  全ての行が独自のものである場合には、２つの同時欠陥が検出される。この場合、いかなる２つの行のＸＯＲ（すなわち、モジュロ２加算）も０に等しくないベクトルである。
・  いかなる奇数個の行のＸＯＲ（すなわち、モジュロ２加算）も０に等しくないベクトルとなる場合には、いかなる奇数個の同時欠陥も検出される。このことは、例えば、ファンアウトｆが奇数である場合に達成される。この場合、全ての行が奇数個の１を有している。各行が奇数個の１を有しているいかなる奇数個の行の１の総数も２つの奇数の積であり、この積は常に奇数となる。
・  ４以上の偶数個の同時欠陥は検出できない。しかし、ＳＣＬ回路１４０の設計により、検出されない確率を最小にしうる。
【００４６】
本発明は上述した実施例に限定されず、当業者は特許請求の範囲に記載した本発明の範囲を逸脱することなく、種々の変形例を設計しうることを銘記すべきである。本発明は、幾つかの個別の素子を有するハードウェアにより構成しうる。幾つかの手段を列挙する装置の請求項では、これらの手段の幾つかを１つの同じハードウェアで構成しうる。ある手段を互いに異なる従属請求項で述べているという単なる事実は、これらの手段の組み合わせを有利に用いることができないということを表わすものではない。
【図面の簡単な説明】
【００４７】
【図１】図１は、本発明のＩＣ装置を示すブロック線図である。
【図２】図２は、本発明の他のＩＣ装置を示すブロック線図である。
【図３】図３は、本発明の設計方法を示すフローチャートである。
【図１】
2009516164.tif 000029
【図２】
2009516164.tif 000030
【図３】
2009516164.tif 000031
【国際調査報告】
2009516164.tif 000032
2009516164.tif 000033