自動試験パターン生成法
複数の内部配線を試験するデジタル試験パターンを生成する方法が記載されている。試験パターンの第１のセットが生成され、前記第１のセット内の試験パターンの数は、前記内部配線の数に関係し、符号語の第１のセットを定める。前記符号語の第１のセットから、符号語の第２のセットが選択される。前記第２のセット内の符号語の数は、前記内部配線の数に等しく、前記符号語の第２のセットの選択は、前記第２のセット内の符号語に対する遷移カウントの合計が最小化されるように行われる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動試験パターン生成に関し、特に、集積回路の試験中にグラウンドバウンス（ground-bounce）を避けることができる試験パターン生成に関する。
【背景技術】
【０００２】
デジタルシステムにおいて、通常は、構成要素間に多数の内部配線が存在する。既知の試験信号を使用してこれらの内部配線を試験することができることは、設計及び製造プロセスの重要な部分である。前記内部配線は、本明細書において“ネット”と称される。
【０００３】
多くの試験生成アルゴリズムが過去に提案されている。例えば、Jose T de Sousa and Peter Y K Cheung, “Boundary-Scan Interconnect Diagnosis”, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001を参照する。試験生成アルゴリズムの目的は、特定の最小の検出及び診断特性を用いて、試験パターンの最小の可能なセットを生成することである。典型的にこのような試験生成アルゴリズムによりアドレスされる故障モデルは、単一ネットの短絡及び複数ネットの橋絡である。
【０００４】
２つ以上のデジタル構成要素間の複数の内部配線（ネット）を試験するために、デジタル試験刺激（stimuli）の組み合わせがネット入力部に印加され、応答がネット出力部において観測され、予測された応答と比較される。前記ネットの入力部の完全な制御が存在し、前記ネットの出力部が完全に観測可能であると仮定される。
【０００５】
以下の記載において、試験刺激に対する以下の用語が使用される。これらの用語は添付図面の図１に図示される。
−試験パターン：試験パターン２は、試験下のネットに対して同時に並列に印加される試験データビットのセットである。図１において、試験パターンは、試験データの列として示される。試験パターンは、時には並列試験ベクトル（ＰＴＶ、Parallel Test Vector）として知られる。
−符号語：符号語４は、試験中に個別のネットに対して連続的に印加される試験データビットのリストである。図１において、符号語は、試験データの行である。符号語は、時には直列試験ベクトル（ＳＴＶ、Sequential
Test Vector）として知られる。
【０００６】
Jarwala及びJau（(Najimi Jarwala and Chi W Jau, “A New Framework for Analyzing Test Generation and Diagnosis Algorithm for Wiring Interconnects”, Proceedings IEEE International Test Conference (ITC), pages 63-70, October 1989)は、以下の内部配線に対する決定性故障モデルを記載している。
−複数ネット故障は、２つ以上のネットの間に短絡を作成する橋絡故障であり、以下の特徴を持つ。
＊ワイヤードＯＲ（Wired-OR）：ドミナント（dominant）‘１’ドライバの場合、短絡が、短絡されたネット間で論理‘ワイヤードＯＲ’のように機能する。
＊ワイヤードＡＮＤ（Wired-AND）：ドミナント‘０’ドライバの場合、短絡が、短絡されたネット間で論理‘ワイヤードＡＮＤ’のように機能する。
＊ストロングドライバ（Strong-Driver）：特定のドライバが短絡を支配し、したがって短絡されたネットがドミナントドライバに従う。
−単一ネット故障は、単一ネット上の“スタックアット（stuck-at）”故障及び“スタックオープン（stuck-open）”故障を含み、以下の特徴とを持つ。
＊スタックアット０：この故障は、ネット上のデータ値が常に論理‘０’として読み出されるようになる。
＊スタックアット１：この故障は、ネット上のデータ値が常に論理‘１’として読み出されるようになる。
【０００７】
短絡を試験する要件は、全てのネットが一意的な符号語を得なければならないことである。ネットが故障無しである場合、各応答は一意的である。短絡の場合、短絡に関係するネットは同じ応答を持つ。したがって、これらの応答はもはや一意的ではなく、短絡が検出される。William Kautz（William H Kautz, Testing of Faults in Wiring nterconnects, IEEE Transactions on Computers, Vol C-23 (No 4): 358-363, April 1974）は、カウント・シーケンス・アルゴリズム（Counting Sequence Algorithm）として知られるようになった短絡の試験を提案した。単純なバイナリ・カウント・アルゴリズムが符号語を生成する。ｋ個のネットに対して、log2ｋ個の試験パターンが必要とされる。前記カウント・シーケンス・アルゴリズムは、最小の数の試験パターンで全ての短絡の検出を保証する。
【０００８】
全てのネットがスタックアット０オープンに対して試験されることを保証するために、全ての符号語が少なくとも１つの‘１’を含む必要がある。同様に、スタックアット１故障に対して、全ての符号語は、少なくとも１つの‘０’を含む必要がある。前記カウント・シーケンス・アルゴリズムは、これを保証しない。したがって、Goel及びMcMahon（P
Goel and M T McMahon, “Electronic Chip-In-Place Test”, Proceedings IEEE International Test Conference (ITC), pages 83-90, October 1982）は、修正カウント・シーケンス・アルゴリズムとして知られるようになった試験生成アルゴリズムを提案した。主なアイデアは、全て０及び全て１の符号語を禁じる場合に、オープン故障が検出されることができることである。したがって、ｋ個のネットに対して、log2(ｋ＋２)個の試験パターンが必要とされ、これは、０の代わりに１で開始する単純なバイナリ・カウント・アルゴリズムにより再び生成されることができる。前記修正カウント・シーケンス・アルゴリズムは、最小の数の試験パターンで全ての短絡及びオープンの検出を保証する。
【０００９】
Eerenstein及びMurisにより発行された（Lars Eerenstein and Math Muris, “Method for Generating Test Patterns to Detect an Electric Short circuit, a Method for Testing Electric Circuitry While Using Test Patterns So Generated, and a Tester Device for Testing Electric Circuitry with such Test Patterns”, 米国特許公開公報５６３６２２９）、他の内部配線試験生成アルゴリズムは、ＬａＭａアルゴリズムとして知られている。このＬａＭａアルゴリズムは、修正カウント・シーケンス・アルゴリズムに基づくが、１ではなく３ずつインクリメントする。前記ＬａＭａアルゴリズムは、ｋ個のネットに対してlog2(３ｋ＋２)個の試験パターンを必要とする。
【００１０】
上述の試験生成アルゴリズムは、故障の検出を保証する。しかしながら、故障の検出は別にして、診断解像度は、しばしば試験の他の重要な性質である。Jarwala及びJauは、診断解像度を分かりにくくするエイリアシングの状況を記載した。エイリアシングは、故障ネットの故障応答が他の故障無しネットの故障無し応答に等しい場合に生じる。この場合、前記故障無しネットも故障ネットにおける故障の影響を被っているのかどうかを決定することができない。Paul T. Wagner（“Interconnect Testing with Boundary Scan”, Proceedings IEEE International Test Conference (ITC), pages 52-57, October 1987）は、エイリアシングを避けるために（修正）カウント・シーケンス・アルゴリズムを改良する真／補数試験アルゴリズム（True/Complement Test Algorithm）を提示した。Wagnerの方法は、元のカウント・シーケンス・アルゴリズムの全ての試験パターンを印加し、反転値を持つ同じ試験パターンが後に続く。この反転された試験パターンにより、全て０及び全て１の符号語は生成されない。したがって、カウントシーケンスの番号０及びｋ−１を除外する必要はない。したがって、前記真／補数試験アルゴリズムは、２log2ｋ個の試験パターンを必要とする。前記真／補数試験アルゴリズムは、反転により全ての符号語が等しい数の０及び１を含むことを保証する。
【００１１】
他のネットとの‘ワイヤードＯＲ’故障の場合、応答語において、１の数は増加され、０の数は減少される。同様に、他のネットとの‘ワイヤードＯＲ’故障の場合、応答語において、１の数が増加され、０の数が減少される。同様に、他のネットとの‘ワイヤードＡＮＤ’故障の場合、０の数が増加され、１の数が減少される。スタックアット・オープン故障の場合、全ての応答値は、全て０又は全て１のいずれかである。したがって、全ての故障の場合に、０及び１の数は変化し、この結果、応答語がもはや等しい数の０及び１を含むことはない。したがって、故障応答は、他のネットの故障無し応答と等しいことはなく、したがって、前記真／補数試験アルゴリズムは、エイリアシング無しである。図２（ｄ）の例において、ｋ＝４を用いて、
【数１】
の試験パターンを必要とする。符号語は、１１００、１００１、０１１０及び００１１であり、４つのネットに任意に割り当てられることができる。図１は、図示された５つのネット（ネット１…ネット５）に対する真／補数試験アルゴリズム試験パターンを図示する。
【００１２】
近年、グラウンドバウンスを避けることは、試験生成アルゴリズムに対する新しい制約になっている。グラウンドバウンスは、例えばＩＣ内部グラウンドと電源レベルとの間の並びに基板における電源電圧レベル及びグラウンドをシフトする現象を指し、ＩＣ上で同時に切り替わる多数の値により生じる可能性がある。グラウンドバウンスは、連続した試験パターン間の切り替え活動（switching activity）の量に上限を導入することにより避けられることができる。この制限は、同時切り替え出力制限（ＳＳＯＬ、Simultaneous Switching Output Limit）として知られている。
【００１３】
ＩＣの正常動作中に、トランジスタの間で大きな内部切り替え活動が存在する。大きすぎる活動は、電源からの電流需要（current demand）においてサージ（surge）を生じる可能性があり、ＩＣ内部電源又はグラウンドレベルを大幅に変動させる可能性がある。これは、システムクロック又はマスターリセットのような重要な信号上で擬似信号を生成させる可能性があり、これによりＩＣにおいて擬似的な挙動を生じる可能性がある。例えば、Hans Peter Richter and Norbert Munch, “Boundary-Scan Test Triumphs Over Ground-Bounce”, Test & Measurement World Europe, August/September 1997、又はAmitava Majumdar, Michio Komoda, and Tim Ayres, “Ground Bounce Considerations in DC Parametric Test Generation using Boundary Scan”, Proceedings IEEE VLSI Test Symposium (VTS), pages 86-91, April 1998を参照する。
【００１４】
グラウンドバウンスは、ＩＣの動作に負の影響を与える。ＩＣ内部グラウンド電圧レベルがＩＣ内部論理の閾値電圧まで上昇する場合、無効な論理挙動の可能性が存在する。バウンダリスキャン（Boundary-Scan）を備えたＩＣの場合、グラウンドバウンスは、擬似試験クロック（ＴＣＫ）を生じる可能性があり、前記擬似試験クロックは、オンボードのバウンダリスキャン装置を同期状態から外れさせる可能性がある。
【００１５】
グランドバウンスは、ＩＣが該ＩＣ内の（又は基板上のＩＣ間の）多量の切り替え活動を処理することができるようにＩＣ（又は基板）を設計することにより避けられることができる。試験中の切り替え活動は、典型的には、通常の（非試験）動作中より高い。この性質から、試験は回路を通して高感度の経路をセットアップし、これにより多くの出力の値を変化させる。試験時間を節約するために、しばしば試験生成アルゴリズムの目的は、最小の数の試験パターンで最高の可能な故障検出率を得ることである。これは、更に、試験パターンごとの内部切り替え活動の量を増加する。ＩＣ及び基板は、通常動作中及び試験動作中にグラウンドバウンスを処理するように設計される。実際に、ＩＥＥＥ１１４９.１２バウンダリスキャン規格は、バウンダリスキャンレジスタの使用に基づく全ての試験動作中に前記装置の内部にグラウンドバウンスが存在すべきでないことを命じる。問題は、基板レベルにおいて、内部配線試験に対するＥＸＴＥＳＴ試験モードにおける全てのオンボード・バウンダリスキャン装置で、たとえ各装置がグランドバウンス仕様内であっても、基板レベルのグラウンドバウンスが起こらないという保証は存在しない。実際に、数千以上のバウンダリスキャンからバウンダリスキャンへの内部配線が存在する場合、グラウンドバウンスが起こる確率は高い。
【００１６】
Richter及びMunchは、工業用電気通信基板上の１１４９.１準拠ＡＳＩＣ間のＥＸＴＥＳＴ試験中のグラウンドバウンス問題について報告した。全てのＡＳＩＣは、電気的なグラウンドバウンス仕様を満たし、シミュレーションは、多くとも５０％の同時に切り替わるＡＳＩＣ出力での通常動作の下でＡＳＩＣの正しい動作を確認した。ＡＳＩＣ設計者は、たとえ基板試験中に起こったことであっても、多くの（又は全ての）バウンダリスキャン出力が同時に切り替わることができる（最悪の場合のＥＸＴＥＳＴ）可能性を考慮していない。
【００１７】
グラウンドバウンスは、生成されて内部配線間に印加される試験パターンにおける切り替え活動の度合いを制御することにより基板レベルで避けられることができる。これは、幾つのバウンダリスキャン出力がある試験パターンから次の試験パターンへの遷移で同時に切り替えられることができるかに上限を導入することにより行われることができる。この記載において、この上限は、同時切り替え出力制限（ＳＳＯＬ）と称される。一般に、ＳＳＯＬは、基板の電気的設計に責任がある基板設計者により算出及び定義されるべきである。基板レベルの内部配線のＡＴＰＧツールの多くのベンダは、製品にＳＳＯＬ制約を加えている。
【００１８】
ＳＳＯＬ制約は、２つの連続した試験パターン間のデータビット遷移の最大数を制限する。連続した試験パターン間のビット遷移の数は、ハミング距離として知られており、図２に図示される。図２Ａにおいて、６つの試験パターン（ｐ1ないしｐ6）が示され、連続した試験パターン間のハミング距離６も示されている。試験パターンの連続した対の２つが、２のＳＳＯＬの推定レベルより大きいハミング距離を持つことがわかる。
【００１９】
したがって、これらの違反（violation）を除去するために前記試験パターンを修正する必要がある。違反を除去するためにこれまでに考えられた方法は、試験パターンの違反している対の間に追加の試験パターンを挿入することである。この場合、図２Ｂに示されるように、２つの追加の試験パターンｐ2i及びｐ5iが、これらの違反を除去するために追加される。図２Ｂの試験パターンの全ての対は、ＳＳＯＬレベルより小さいハミング距離を持つ。
【００２０】
しかしながら、試験生成にＳＳＯＬ制約を組み込むことは、一般に、追加の試験パターンの挿入を必要とするので、試験パターン数の増加、したがって試験時間の増加を引き起こす。
【００２１】
ＳＳＯＬ違反を克服するために単純に追加の試験パターンを挿入する従来のアプローチが不必要に大きな試験セットを生じる可能性があることは、Erik Jan Marinissen, Bart Vermeulen, Henk Hollmann, and Ben Bennetts, Minimizing Pattern ount for Interconnect Tests Under A Ground-Bounce Constraint. IEEE Design & Test of Computers, 20(2), March/April 2003に示されている。元の試験セットの全ての検出及び診断特性を維持しながら、挿入される必要がある追加の試験パターンの数を減少するために利用されることができる２つの自由度が存在する。
【００２２】
Marinissen他の論文は、本発明の背景を十分に記載するためにここでより詳細に説明される。
【００２３】
前記方法は、上述の真／補数試験パターン生成アルゴリズムを参照して記載されるが、前記方法が他のアルゴリズム又はアプローチにより生成された試験パターンに作用することができることは容易に理解される。
【００２４】
前記方法は２つの基本ステップ、即ち符号語サブセット選択及び試験パターン並べ替え（及び挿入）を使用する。全体的な方法は図３に図示される。ステップ１０において、自動試験パターン生成アルゴリズムが使用され、試験パターンの完全なセットを生成する。
【００２５】
ステップ１２（１２０、１２１、１２２）において、符号語サブセット選択が、何らかの方法（１２０）、遷移カウント方法（１２１）又は差分カウント方法（１２２）を使用して実行される。前記選択の結果は、並べ替えステップ１４にフィードされ、並び替えステップ１４は、試験パターンセットのＳＳＯＬ違反の数を最小化するために何らかの方法（１４１）、又は欲張り法（１４２）を使用して前記試験パターンを並び替える。様々な方法が下に詳細に記載される。
【００２６】
並び替えの後に、追加の試験パターンが、残りのＳＳＯＬ違反を除去するために必要な場所に挿入されることができる。
【００２７】
符号語サブセットの選択は、ここでより詳細に記載される。
【００２８】
ｋ個のネットに対して、試験生成アルゴリズムは、ｐ(ｋ)個の試験パターンを必要とする。ｐ(ｋ)個の試験パターンを用いて、前記アルゴリズムは、ｋ≦ｃ(ｋ)となるようなｃ(ｋ)個の一意的な符号語を生成する。関数ｐ(ｋ)及びｃ(ｋ)は、試験生成アルゴリズムに依存する。例えば、真／補数試験アルゴリズムに対して、ｐ(ｋ)及びｃ(ｋ)は以下のように与えられる。
【数２】
多くの実際的な場合において、ｋ、ｐ(ｋ)及びｃ(ｋ)は全て整数であるので、前記アルゴリズムは、厳密に必要な符号語より多い符号語を生成し、即ちｋ＜ｃ(ｋ)である。これは、前記の式が非整数を整数に切り上げるシール（ceil）演算子を有することを意味する。これらのシール演算子は、多くの場合、ｋ＜ｃ(ｋ)を生じる。
【００２９】
したがって、前記試験中に使用されるべき総数ｃ(ｋ)個の生成された符号語のサブセットを選択することが可能である。このようなサブセット選択は、試験の検出及び診断特性又は試験時間に影響を与えない。
【００３０】
選択するのに利用可能である
【数３】
個の可能なサブセットが存在する。一例として、ｋ＝２５７の真／補数試験アルゴリズムを考える。上記によると、ｃ(２５７)＝２log2257＝２9＝５１２である。したがって、
【数４】
個の代替符号語サブセットが存在する。
【００３１】
前記のサブセット選択手順は、ＳＳＯＬ違反無しの最小試験パターンセットを生じる符号語のサブセットを検索する。
【００３２】
前記符号語サブセット選択は、以下に記載される２つの発見的技法の１つにより実行されることができる。
【００３３】
第１の可能な発見的技法は、遷移カウントに基づき、図４に図示される。図４の例は、６つの試験パターン及び８つの符号語を生じるｋ＝５の場合を表す。図４Ａにおいて、試験パターンの完全なセット（ｃ1ないしｃ8）が、その中のビット遷移の数のカウント３０と一緒に示される。遷移カウント発見的方法を使用して、必要とされるｋ（＝５）個の符号語が、最小の遷移カウントを持つ５つの符号語として選択される。同じ遷移カウントを持つ符号語の選択のみが必要とされる場合、前記選択は任意に行われる。
【００３４】
図４Ｂは、連続した試験パターンの間のハミング距離３０と一緒に選択された符号語（ｃ1 ｃ2 ｃ4 ｃ5 ｃ8）を図示する。この場合、前記サブセットがＳＳＯＬ＝２に対する違反を持たない試験パターンセットを形成し、したがって他の処理が必要とされないことがわかる。当然、特にｋの大きな値に対しては、並び替え及び可能な挿入が必要とされる可能性がある。
【００３５】
第２の発見的アプローチは、差分カウント方法であり、これは図５に図示される。図５Ａは、真／補数方法を使用して生成されたｋ＝９及びＳＳＯＬ＝３の状況に対する完全な試験パターンセット（ｃ1ないしｃ16）を示す。各符号語は、前記符号語の前半のビットと前記符号語の後半のビットとの間の差の数に等しい関連した差分カウントを持つ。
【００３６】
この場合、最小の差分カウントを持つ符号語が選択され、正しい数ｋの符号語を提供する。同じ差分カウントを持つ符号語の間の選択が行われるべき場合、この選択は任意に行われる。
【００３７】
図５Ｂは、試験パターンの連続した対の間のハミング距離と一緒に符号語の選択されたサブセットを示す。複数の試験パターン対がＳＳＯＬ≦３の試験に不合格になり（fail）、したがって他の処理が必要とされることがわかる。以下に詳細に記載されるべき前記他の処理（並び替え）の結果は、図５Ｃに示される。
【００３８】
前記試験パターンの並び替え及び挿入はここでより詳細に記載される。
【００３９】
前記試験パターンの並び替えは、前の段階の間に選択された符号語のサブセットに実行される。したがって、ｐ個の試験パターンとｋ個の符号語とが存在する。
【００４０】
初めに、いわゆるＳＳＯＬ違反グラフが構築される。このようなグラフは、図６に示され、重み付けされ、完全に連結された無向グラフを有する。前記グラフのノードは、ｐ(ｋ)個の試験パターンに対応する。各対のノード間の辺は、前記対のノード間のハミング距離に依存する重みを与えられる。辺の重みは、これら２つのノード間のＳＳＯＬ違反の数を表す。
【００４１】
前記グラフのノードを通る経路を見つける問題は、巡回セールスマン問題（ＴＳＰ、traveling salesman problem）の１つのバージョンと見なされることができる。ＳＳＯＬ違反グラフに関して、ツアー（tour）に沿って通った辺の合計重みが最小化されるような前記グラフの全てのノードを通る経路を見つけることが必要である。
【００４２】
この問題は、周知の巡回セールスマン問題、M.R. Garey and D.S. Johnson, Computers and Intractability − A guide to the theory of NP-Completeness, W.H. Freeman and Company, San Francisco, CA, USA, 1979の最適化の改良に等しい。
【００４３】
巡回セールスマン問題（ＴＳＰ）が簡潔に記載され、以下のように要約されることができる。ｍ個の町のセットＣを仮定し、町ｃi,ｃj∈Ｃの各対に対する距離ｄ(ｃi,ｃj)及び正の整数Ｂを仮定する。長さＢ以下のＣのツアーは存在するか。
【００４４】
実際には、最適な解を計算するのに要する時間は、問題例（problem instance）のサイズと共に指数的に増加する。前記問題例サイズは、ノード（テストパターン）の数により決定される。幸いに、基板レベルの内部配線試験に対する問題例サイズはあまり大きくない。試験パターンの数は、log2ｋのオーダーであり、したがって、数千個のネットを持つ基板に対しても１０ないし２０個の試験パターンが存在する。したがって、最も実際的な問題例に対して、徹底的に、即ち前記グラフの全ての可能なツアーを数え上げることによりこの問題を解くことは実行可能と思われる。代わりに、文献に利用可能なＴＳＰに対する効果的及び効率的な発見的アルゴリズムが存在し、これは短い計算時間で最適に近い解でこの問題を解くことができる。例えば、David S. Johnson and Lyle A. McGeoch, “The traveling salesman problem: A case study”, in Emile H.L Aarts and Jan-Karel Lenstra, editors, “Local Search in Combinatorial Optimization”, pages 15-310, John Wiley & Sons Ltd., Chichester, England 1997を参照する。
【００４５】
図６Ｂは、ｋ＝５及びｓ＝２に対するＳＳＯＬ違反グラフを図示し、図６Ａは、前記グラフのノードを作り上げる順序付けられていない試験パターンセットを示す。順序付けられていない試験パターンセットは、ＳＳＯＬ基準を違反する試験パターンの対の２つの問題例を持つことがわかる。
【００４６】
図６Ｂにおいて、太線の矢印は、前記グラフを通るＳＳＯＬ違反なしのツアーを示す。図６Ｃは、前記試験パターンが前記グラフ内のＳＳＯＬ違反を最小化したツアーにより並べられた対応する結果の試験セットを示す。
【００４７】
ＴＳＰソルバ（TSP Solver）の実行後に、２つの可能な結果が存在し、即ち（１）合計重み０のツアーが得られる、又は（２）０より大きい合計重みを持つツアーが得られる。前者の場合、ＳＳＯＬ制約を満たす試験パターンの順序が見つけられている。後者の場合、依然として１つ以上のＳＳＯＬ違反を持つ試験パターンの順序が見つけられている。これは、合計重み０をもつツアーが存在しない、又はこのようなツアーが存在するが、使用された発見的ＴＳＰソルバがこれを見つけることができなかったという事実による可能性がある。いずれの場合にも、前記ツアーの合計重みの最小化は前記ＴＳＰソルバの目的関数だったので、ＳＳＯＬ違反の数が比較的低いことが予測される。
【００４８】
残りのＳＳＯＬ違反は、ＳＳＯＬ違反を持つ２つの連続した試験パターンの間に１つ以上の追加試験パターンを挿入することにより解決されることができる。連続した試験パターンｐ1及びｐ2がｗ(ｐ1,ｐ2)個のＳＳＯＬ違反を持つ（ｗ(ｐ1,ｐ2)＞０）場合、これら２つのパターンの間の全てのＳＳＯＬ違反を解決するためにｗ(ｐ1,ｐ2)／ｓの追加試験パターンを挿入することが必要である。
【００４９】
図５Ｃにおいて、試験パターンの１つの対がＳＳＯＬ基準を違反し、したがって１つの追加試験パターンがこの違反を除去するためにこれら２つの試験パターンの間に挿入されなければならないことがわかる。
【００５０】
Marinissen他の論文は、ＳＳＯＬ制約ｓの下でのｋ個のネットに対する試験パターンの最小の数に対する理論的上限及び下限の式を提供する。
【発明の開示】
【発明が解決しようとする課題】
【００５１】
したがって、ＳＳＯＬ制約を組み込むことができるが、生成されるべき試験パターンの数を更に最小化し、追加の最適化を使用する試験パターン生成アルゴリズムを提供することが望ましい。
【００５２】
本発明の実施例は、したがって、このようなアルゴリズムを提供し、ＳＳＯＬ違反無しの連続した試験パターンを所定の試験生成アルゴリズムに組み込むことを可能にする方法を提供することを志す。
【課題を解決するための手段】
【００５３】
本発明の１つの態様によると、複数の内部配線を試験するデジタル試験セットを生成する方法であって、各試験セットがビットのマトリクスを有し、前記マトリクスが第１の複数の試験パターン及び第２の複数の符号語を定め、各試験パターンの前記ビットが、互いに並列にそれぞれの内部配線に対して印加するものであり、内部配線に印加する連続した試験パターンのビットが該内部配線に対する符号語を形成し、各符号語が、ビット値遷移の数に関する遷移カウントを持ち、前記試験セットが、前記試験セット内の前記符号語の前記遷移カウントの和に関する合計遷移カウントを持ち、前記方法が、所定の閾値より小さい合計遷移カウントを持つ試験セットを生成するステップを有し、前記所定の閾値が前記試験セット内の試験パターンの数と所定の関係を持つ当該方法が提供される。
【発明を実施するための最良の形態】
【００５４】
本発明の好適な実施例は、添付図面を参照してここに記載される。
【００５５】
まず、初期試験パターンセットのバイナリコンテンツと連続した試験パターンに対する最大ハミング距離制約の違反を解決するために挿入される必要がある試験パターンの数との関係が解析される。
【００５６】
図７Ａは、行がｋ個の符号語に対応し、列がｂ個の試験パターンに対応する試験パターンマトリクスＣを図示する。前記ｋ個の符号語は、Ｃ1,...Ｃkにより示される。Ｃi,jは、１≦ｉ≦ｋ及び１≦ｊ≦ｂで符号語Ｃi内のビットｊを参照する。前記試験パターンはｐ1...ｐbにより示され、ここでｐj＝(Ｃ1,j,...,Ｃk,j)は、試験パターンマトリクスＣのｊ番目の列である。
【００５７】
遷移及び遷移カウントは解析において重要であるので、試験パターンマトリクスＣの代替表記が使用される。遷移マトリクスＴが計算され、これは、ｋ×(ｂ−１)マトリクスＴ及びｋ個の初期符号語値Ｃi,1を有する。遷移マトリクスＴは図７Ｂに図示される。マトリクスＣとマトリクスＴとの関係は、
【数５】
により与えられる。ｊ＝１...ｂ−１に対し、連続した試験パターンｐjとｐj+1との間のハミング距離は、
ｄj＝ｄH(ｐj,ｐj+1)
として定義される。単純のため、連続した試験パターンは相異なる、
即ち、全てのｊに対してｄj＞０
であると仮定される。この仮定が与えられると、試験パターンマトリクスＣがＳＳＯＬ制約ｓとの組み合わせで使用される場合、[ｄj／ｓ]−１個の試験パターンが、ｐjとｐj+1との間に挿入されなければならない。したがって、挿入後に、所定の試験セットに基づくＳＳＯＬ制約ｓの下で必要とされる試験パターンの総数Ｐsは、以下の式を満たす。
【数６】
ｉ＝１...ｋに対してτiが符号語Ｃiにおける遷移の数を示すとし、即ち
τi＝＃｛ｊ∈{１,...ｂ−１}｜Ｃi,j≠Ｃi,j+1｝
である。この目的は、試験パターンマトリクスＣ内の遷移の総数
【数７】
に関して試験パターンの総数Ｐsに対する下限及び上限を算出することである。この解析は、
【数８】
による前記試験の合計距離ｄtotの定義に基づく。
【００５８】
試験パターンマトリクスＣの１行の遷移の総数は、遷移マトリクスＴの対応する行の１の数により与えられる。連続した試験パターンの間のハミング距離は、遷移マトリクスＴの関連する列の１の数により与えられる。したがって、τtot及びｄtotの両方が、遷移マトリクスＴの１の総数を、一方は行により、及び他方は列により、カウントする。
【００５９】
形式的には、
【数９】
である。
【００６０】
合計ハミング距離が、遷移の総数に等しいという事実は、τtotのみに依存するＰsに対する上限及び下限を算出するために使用されることができる。
【００６１】
長さｂの符号語からなる試験パターンセットは、合計τtot個の遷移を含む。試験パターンの総数Ｐsは、ＳＳＯＬ制約ｓを満たすための挿入の後では、
【数１０】
により与えられる。この式の証明は下で与えられる。
０≦ｒ＜ｓで、τtot＝ｑｓ−ｒとする。各ｊに対し、０≦ｒj＜ｓで、ｄj＝ｑjｓ−ｒjとする。上で与えられた式によると、
【数１１】
である。これから続いて、
【数１２】
であり、｜ｄj／ｓ｜＝ｑjなので、
【数１３】
である。結果として、
【数１４】
及び
【数１５】
である。Ｐsは整数なので、この定理が従う。
【００６２】
この定理から、固定された符号語長ｂに対して、ＳＳＯＬ制約ｓの下での挿入の後の試験パターンの総数は、遷移の総数が小さい符号語の集合を使用することによってのみ小さくされることができる。
【００６３】
したがって、本発明の一実施例は、試験パターンマトリクスＣ内の遷移の総数を最小化しようとする。
【００６４】
本発明の他の態様がここに記載される。この態様は、ＳＳＯＬ制約ｓの下で必要とされる試験パターンの総数を最小化する、固定された長さｂのｋ個の符号語のほぼ最適なセットの選択を可能にする方法を生じる。少なくともｋ個の符号語を利用可能にするためには、２b≧ｋである。したがって、ｂ≧ｂmin＝｜log2ｋ｜が仮定される。
【００６５】
本発明のこの態様は、以下の符号語選択方法を使用する。０個の遷移を持つ全ての語を選択し、次いで１個の遷移を持つ全ての語を選択し、ｔ−１個の遷移を持つ全ての語まで選択し、最終的にｔ個の遷移を持つ幾つかの追加の語を選択する。ここでｔは、必要とされる符号語の数ｋが多くともｔ−１個の遷移を持つ長さｂの語の数より大きいが、多くともｔ個の遷移を持つ長さｂの語の数より大きくないような数である。
【００６６】
この技法は図８に図示され、試験パターンマトリクスＣ及び遷移マトリクスＴが示される。前記２つのマトリクスの行は、一番上の０個の遷移（マトリクスＣ）又は０個の１（マトリクスＴ）からこの図の下のｔ個の遷移又はｔ個の１まで並べられる。本発明の本実施例によると、前記符号語は、前記マトリクスの一番上から選択され、所要の数ｋの符号語が選択されるまで下に向かう。両方の試験セット表現に対し、前記図は、符号語が生成されるグレイの陰影を用いて示す。
【００６７】
このように選択された試験パターンセット内の遷移の総数が、ｔ個の遷移を持つ特定の符号語の選択に依存せず、構成により、長さｂのｋ個の符号語のセットにおける遷移の最小の数であることに注意するのは有用である。これはτtot(ｂ)により示される。
【００６８】
この方法に基づいてアルゴリズムを解析するために、及びτtot(ｂ)を計算することができるために、以下の結果が必要とされる。
【００６９】
正確にｉ個の１を持つ長さｂ−１の語の数は、
【数１６】
に等しい。図７に示されるようなｋ×ｂの符号語マトリクスＣとｋ×(ｂ−１)の遷移マトリクスとの間の対応関係から、これらの語のそれぞれがｉ個の遷移を持つ正確に２つの符号語に対応することがわかる。
【００７０】
ｋiを前記試験セットに含まれるｉ個の遷移を持つ符号語の数とする。前記試験セット内の遷移の総数Σiｉｋiを最小化するために、前記符号語選択方法は、多くともｔ−１個の遷移を含む全ての語とｔ個の遷移を含む語の幾つかとを符号語として選択する。したがって、０≦ｉ≦ｔ−１に対して
【数１７】
であり、ｔは、
【数１８】
となるものである。τtot(ｂ)に対して、ここで式
【数１９】
が得られる。この符号語選択方法は、ＳＳＯＬ制約ｓを満たし、長さｂの符号語を使用するｋ個のネットに対する試験セットにおいて必要とされる試験パターンの最小の数ｐ(ｋ,ｓ,ｂ)の限界を算出するために使用される。τtot＝τtot(ｂ)である長さｂの符号語を使用する試験セット（実際には多くの試験セット）が存在することが上で示され、明らかにこのような試験は同様な値のτtotを持つことができないので、
【数２０】
が結論付けられることができる。この符号語選択方法及びｋt個の追加の符号語を選択する特定の方法を使用するアルゴリズムは、この式の限界内に位置する挿入後の試験パターンの総数を得ることに注意する。
【００７１】
特に、これは、Marinissen他の遷移カウント符号語サブセット選択発見的アルゴリズムに適用できる。
【００７２】
本発明の実施例において、この式の上限は、改良された最悪の場合の挙動を持つアルゴリズムを使用することにより改良されることができる。前記アルゴリズムは、以下の関係
【数２１】
を使用し、ここでｋ及びｂは固定されている。
【００７３】
ここで、ＳＳＯＬｓを満たす多くとも
【数２２】
個の試験パターンを生成し、したがって上限を確立する符号語選択方法に基づくアルゴリズムが記載される。
【００７４】
このアルゴリズムの背後にあるアイデアは、以下のとおりである。ｋt個の追加符号語を選択した後に結果として生じる距離ｄjは、挿入後の結果として生じる試験パターンの数を決定する。前記符号語選択方法により、合計距離
【数２３】
は、常に同じ（即ちτtot(ｂ)）であるが、距離ｄjの正確な値は、追加のｋt個の符号語の選択に依存する。全てのｄjがわずかにｓの倍数の上である状況を避けることが望ましく、前記状況は最悪の場合の挙動であり、前記上限はこれに基づく。
【００７５】
好ましくは、全てのｄjは、ｓの倍数に等しいか又はわずかに下であるべきだが、これは、一般に保証するのは難しい。前記最悪の場合の挙動は、距離ｄjが全てほぼ等しいことを確実にすることにより避けられる。以下では、まず、多くともｔ−１個の遷移を持つ符号語の距離ｄjの部分がｊと独立に一定であることが示される。次いで、ｄjがほぼ等しいままであるような残りのｋt個の符号語を選択する方法が説明される。
【数２４】
を仮定し、ここでｄj,eは、ｌ（エル）個の遷移を含む符号語のｄjとｄj+1との間のハミング距離の部分であり、即ち
【数２５】
である。０個の遷移を持つ２つの符号語、即ち全て０及び全て１の符号語のみが存在し、したがってｄj,0＝０である。所定の位置ｊ∈{１,...,ｂ−１}に１を含むｌ（エル）個の１を持つ長さｂ−１のＴ内の語の数は、
【数２６】
である。Ｔのそれぞれのこのような語は、ｄj,eに対して１回だけそれぞれ寄与するｌ（エル）個の遷移を持つＣ内の２つの符号語（一方は０で始まり、他方は１で始まる）に対応するので、結果は以下のとおりである。
結果として、
【数２７】
である。ｔ個の遷移を含むｋt個の符号語の選択は、ここに記載される。
【数２８】
の場合、ｔ個の遷移を持ち０で開始する全ての語が、更に選択される。ここまでに選択された符号語による距離ｄjの部分がｊと独立に一定であることに注意することは重要である。ここで、ｋt*を
【数２９】
により定義されるものとする。後の使用のため、
【数３０】
であることに注意すべきである。この場合、（
【数３１】
の場合には全て０で開始し、
【数３２】
の場合には全て１で開始する）ｔ個の遷移を持つｋt*個の追加の符号語、又は同等に、（前記符号語内の遷移を表す）ｔ個の１を含む長さｂ−１のｋt*個の語を選択することは依然として必要である。便宜のため、サイズｔの｛１,...,ｂ−１｝のサブセットを持つｔ個の１を含む長さｂ−１の語が識別される。この場合、セットに関して、｛１,...,ｂ−１｝からサイズｔのｋt*個の相異なるサブセットを選択することは、依然として必要である。これらｋt*個の語に対応する位置における距離ｄjの（可変）部分が、セットに関して、これらｋt*個のセットにおける要素ｊの発生の頻度ｆjになることに注意する。したがって、以下の定義が必要とされる。ベクトルｆ＝(ｆ1,...,ｆn)は、ｉ＝１,...,ｎの全てに対してｆi∈{ｅ,ｅ＋１}となるような整数ｅが存在する場合にバランスされる（balanced）と称される。
【００７６】
ここで、残りのｋt*個の符号語が、これらｋt*個の符号語における距離ｄjの部分がバランスされるように選択されることが確実にされる。即ち、セットに関して、頻度ｆjがバランスされることが確実にされる。このアルゴリズムは以下の結果に基づく。
【００７７】
１≦ｔ≦ｎとする。
【数３３】
であるような重みｆ1＋...＋ｆn＝ｍｔを持つバランスされた整数ベクトルｆ＝(ｆ1,...,ｆn)が存在すると仮定する。この場合、各ｉがセットＳjのｆiで生じるような{１,...,ｎ}のサイズｔのｍ個の相異なるサブセットの集合Ｓ＝{Ｓ1,...,Ｓm}が存在する。
【００７８】
本発明のこの態様を実施するアルゴリズムは、以下の関数を実行し、図９に図示される。初めに、ステップ１００において、
【数３４】
にしたがって数ｔ及びｋtを選択する。
次に、ステップ１０２において、
【数３５】
から数ｍ＝ｋt*を決定する。
次に、ステップ１０４において、多くともｔ−１個の遷移を持つ長さｂの符号語の選択が行われ、ｍ＜ｋtの場合には、ｔ個の遷移を持ち、１で始まる長さｂの全ての語の選択も行われる。
【００７９】
最後に、ステップ１０６において、ｔ個の遷移を持ち、（ｍ＜ｋtの場合）０又は（ｍ≧ｋtの場合）１で始まる長さｂの他のｍ個の語が選択される。ここでｍｔ＝ｑ(ｂ−１)＋ｒの場合、ｒ個のインデックスｉに対してｆi＝ｑ＋１が選択され、残りのｂ−１−ｒ個のインデックスｉに対してｆi＝ｑが選択される。この場合、このアルゴリズムは、距離ｄjがバランスされることを確実にする。この方法は、“固定符号語長に対するＡＴＰＧ”と称されることができる。
【００８０】
ここで、平均ハミング距離は、τtot(ｂ)／(ｂ−１)に等しく、したがってｄj≦｜τtot(ｂ)／(ｂ−１)｜であり、したがって、
【数３６】
である。したがって、このアルゴリズムが、ＳＳＯＬ制約ｓを満たすための挿入の後に、パターンの総数が（多くとも）１＋(ｂ−１)≦τtot(ｂ)／((ｂ−１)s)であるような試験セットを生成すると結論付けることが可能であり、したがって前記上限を証明する。
【００８１】
少なくともｋ個の符号語を利用可能にするために、符号語長ｂは、ｂ≧ｂmin：＝｜log2ｋ｜となるように選択されなければならないと上で述べられた。しかしながら、ｂがこの最小値ｂminに等しく選択される場合に、必ず多数の符号語が多くの遷移を含む。
【００８２】
ｉ個の遷移を持つ長さｂの利用可能な符号語の数は、
【数３７】
により与えられる。したがって、ｉ個の遷移を持つ利用可能な符号語の数は、ｂの値が増加する場合に増加する。したがって、上述の符号語選択方法のように、最小の数の遷移を含むｋ個の符号語を選択することにより、結果として生じる遷移の数τtot(ｂ)、及びこれにしたがって確実に量τtot(ｂ)／(ｂ−１)は、ｂが増加すると減少する。
【００８３】
この提案は、以下のように始められることができる。関数τtot(ｂ)は、≧ｂminに対してｂの減少関数であり、即ちｂmin≦ｂ＜ｂ’の場合、τtot(ｂmin)≧τtot(ｂ)≧τtot(ｂ’)である。
この観測結果は、
【数３８】
であり、ＳＳＯＬ制約ｓを満たし、ｋ個のネットに対する試験セットで必要とされる試験パターンの最小の数は、しばしばｂminより大幅に大きい値ｂに対して実現されることを提案する。
【００８４】
変化するｂに対する上述の限界の挙動を示すために、図９は、ｂ≧ｂminに対して、ｋ＝６０００及びｓ＝６００に対して、上限
【数３９】
及び下限の１つ
【数４０】
の両方を示す。
ｂに対する最良の選択は、平均距離τtot(ｂ)／(ｂ−１)が多くともｓであるｂの第１の（最小の）値ｂ*に近い。この値ｂ*に対して、Ｕ(ｂ*)＝ｂ*であることに注意する。以下、ｂ*の値の推定値が与えられ、したがって試験パターンの対応する総数に対して、ｋ及びｓを前提とするとｐ(ｋ,ｓ,ｂ)＝ｂ*である。
符号語の数ｋ及びＳＳＯＬ値ｓが固定されているとする。前に見たように、各ｂに対して、ｔの値は、
【数４１】
のように選択され、この結果、スターリングの近似（Stirling's approximation）により
log2ｋ≒１＋(ｂ−１)ｈ(ｔ／(ｂ−１))
となり、ここでｈ(ｘ)＝−ｘlog2ｘ−(１−ｘ)log2(１−ｘ)である。
また、合計距離についても、
ｄtot＝τtot≒ｔｋ
したがって、ｔ／(ｂ−１)≒ｓ／ｋの場合、
ｄtot≒(ｂ−１)ｓ
である。
これらの式を組み合わせると、
Ｐ*＝ｂ*≒１＋(−１＋log2ｋ)／ｈ(ｓ／ｋ)
を与える。
結局のところ、ｂ*のこの推定値は、いくらか小さすぎるが、常に真の値の少なくとも約８０％である。
【００８５】
少し意外なことに、ｂの最適値、即ちｐ(ｋ,ｓ,ｂ)を最小化するｂの値は、実際には常に上で定義された数ｂ*に等しいことが判明し、即ち以下の結果が生じる。
【００８６】
ｋ≧２でｋ及びｓが正の整数であるとする。関数τtot(ｂ)を
【数４２】
となるように定義する。
ｂmin＝｜log2ｋ｜とし、数ｂ*をτtot(ｂ)≦(ｂ−１)ｓとなる最小の整数ｂ≧ｂminになるように定義する。次いで、ＳＳＯＬ制約ｓを満たし、ｋ個のネットに対する試験セットに必要とされる試験パターンの最小の数ｐ(ｋ,ｓ)は、ｐ(ｋ,ｓ)＝ｂ*を満たす。
【００８７】
この定理の結果として、ＳＳＯＬ制約ｓを満たし、最小の数の試験パターンを含むｋ個のネットに対する試験セットを生成するために、本発明の他の態様の実施例は、図１０に図示され、以下のように進行する。
まず、ステップ１１０において上で定義したように数ｂ*を決定する。次いで、上述のように、固定された長さｂ*を持つ符号語と共に固定符号語長アルゴリズムを適用する。次に、ステップ１１２において、
【数４３】
にしたがってｔ及びｋtを選択する。次に、ステップ１１４において、
【数４４】
から数ｍ＝ｋt*を決定する。次に、ステップ１１６において、多くともｔ−１個の遷移を持つ長さｂ*の符号語の選択が行われ、ｍ＜ｋtの場合、ｔ個の遷移を持ち１で始まる長さｂ*の全ての語の選択も行われる。
【００８８】
最後に、ステップ１１８において、０（ｍ＜ｋtの場合）又は１（ｍ≧ｋtの場合）で始まりｔ個の遷移を持つ長さｂ*の他のｍ個の語が選択される。ここで、ｍｔ＝ｑ(ｂ*−１)＋ｒの場合、ｒ個のインデックスｉに対してｆi＝ｑ＋１が選択され、残りのｂ*−１−ｒ個のインデックスｉに対してｆi＝ｑが選択される。このアルゴリズムは、この場合、距離ｄjがバランスされることを確実にする。
【００８９】
この方法は、ｂ*個のパターンを持ち、連続したパターンが多くともｓの距離を持つ試験パターンセットを生成する。前記方法は、“可変符号語長に対するＡＴＰＧ”と称されることができる。
【００９０】
実験結果が、新しいＳＳＯＬ制約ＡＴＰＧアルゴリズムに対して下に与えられ、これらの結果を他の方法からの結果に対して比較する。真／補数試験が、比較の基準として使用されるが、この技法は、試験パターンセットを生成する他の方法に適用されることができる。
【００９１】
実験データにおいて、３つの方法が比較される。
【００９２】
１．従来の方法
この方法は、従来のカウント及び後に続く補数演算（complementing）を用いて真／補数試験を生成する。この後に、前記ＳＳＯＬ制約が、従来の追加試験パターンの挿入により満たされる。この方法は、多くの専門（市販）ツールの基本である。
【００９３】
２．Marinissen他の最良の方法
この方法は、従来のカウント及び後に続く補数演算を用いて真／補数試験を生成する。この後に、遷移カウントに基づく符号語サブセット選択及び試験パターン並び替えが適用される。残りのＳＳＯＬ違反は、従来の追加試験パターンの挿入により解決される。この方法は、Marinissen他に記載された様々な方法から最良に実行されるものである。
【００９４】
３．可変符号語長に対するＡＴＰＧ
この方法は、上述のように“真の（True）”試験セットを生成する。この試験は、ＳＳＯＬ違反が無いことを保証され、したがって追加の試験パターンの挿入を必要としない。この後に、“補数（Complement）”部分が、再びＳＳＯＬ違反の無い補数の（complementary）試験セットを追加することにより生成される。“真の”及び“補数”試験パターンの間の境界において、通常は、少数の追加試験パターンが挿入される必要がある。図１２は、ｋ∈{5000，6000，7000，8000}個のネットを持つ問題例に対する実験結果を示す。ｋの５％と５０％との間で変化するＳＳＯＬ値ｓに対し、図１２は、３つ全ての方法に対する試験パターンカウントｐ(ｋ,ｓ)をプロットする。図１３は、基準の従来の方法に対して以前のMarinissen他の方法及び新しい可変符号語長に対するＡＴＰＧの試験パターンカウントの向上を示す。
【００９５】
図１２及び１３は、全てのＳＳＯＬ値ｓに対して、前記従来の方法が最高数の試験パターンを生じることを示す。ｋ及びｓの幾つかの値に対して、Marinissen他の最良の方法は、前記従来の方法に対する大幅な向上を提供するが、しかしながら、この方法が向上を与えない多くの値のｋ及びｓが存在する。
【００９６】
本発明の実施例、新しい可変符号語長に対するＡＴＰＧ技法は、明らかに他のアプローチより性能が優れており、ｋ＝5000，6000，7000，8000に対して、前記従来の方法に対する平均の相対的向上は、それぞれ４６％、４６％、４５％及び４４％である。この新しいＡＴＰＧアルゴリズムは、ｋ及びｓの全ての値に対して前記従来の方法から一貫して向上している。
【００９７】
ユーザが決めたネットの数ｋに対して、ユーザが決めたＳＳＯＬ制約ｓを順守する試験パターンの最小のセットｐ(ｋ,ｓ)を生成する最適なＡＴＰＧアルゴリズムが記載されている。このアルゴリズムは、形式化され上で証明された以下の観測結果に基づく。
−試験パターンの数は、符号語内の遷移の数に強く関係している。したがって、少数の試験パターンを持つ有効な試験セットを得るためには、少数の遷移を持つ符号語を選択しなければならない。
−上の観測に基づき、与えられたｋ、ｓ及びｂに対して、多くともｔ−１個の遷移を持つ長さｂの全ての符号語を選択し、この後に、連続した試験パターンの間のバランスされたハミング距離ｓを持つ正確に合計ｋ個の符号語が得られるように、ｔ個の遷移を持つ長さｂの幾つかの語を注意深く選択するアルゴリズムが提示されている。したがって、残りのＳＳＯＬ違反を解決するために挿入された追加試験パターンを加えた前記試験パターンからなる結果の試験セットが得られる。
−与えられたｋ及びｓに対して値ｂ＝ｂ*を見つける第２のアルゴリズムであって、上記アルゴリズムがこのｂ*に対して呼び出される場合に、ＳＳＯＬ制約を満たすために追加試験パターンが挿入される必要の無いことが保証されることができる当該第２のアルゴリズムが示されており、更に、この第２のアルゴリズムが証明可能に最小の試験パターンセットを生成することが示されている。
【００９８】
一例として一般に使用される真／補数試験アルゴリズムを使用して、ｋ∈{5000，6000，7000}及びｋの５％から５０％まで変化するｓに対する実験結果が示されている。この実験は、前記アルゴリズムが前記従来の方法と比較した場合に試験パターンの数の平均４５％の減少を生じることを示す。
【図面の簡単な説明】
【００９９】
【図１】試験パターン及び符号語を図示する。
【図２Ａ】真／補数試験パターン生成アルゴリズムに対する５つのネットに対する試験刺激を図示する。
【図２Ｂ】真／補数試験パターン生成アルゴリズムに対する５つのネットに対する試験刺激を図示する。
【図３】本発明の１つの態様を実施する方法を図示する。
【図４Ａ】符号語サブセット選択の第１の方法を図示する。
【図４Ｂ】符号語サブセット選択の第１の方法を図示する。
【図５Ａ】符号語サブセット選択の第２の方法を図示する。
【図５Ｂ】符号語サブセット選択の第２の方法を図示する。
【図５Ｃ】符号語サブセット選択の第２の方法を図示する。
【図６Ａ】試験パターンを並び替える方法を図示する。
【図６Ｂ】試験パターンを並び替える方法を図示する。
【図６Ｃ】試験パターンを並び替える方法を図示する。
【図７Ａ】試験マトリクス及び遷移マトリクスを図示する。
【図７Ｂ】試験マトリクス及び遷移マトリクスを図示する。
【図８Ａ】符号語の選択を図示する。
【図８Ｂ】符号語の選択を図示する。
【図９】本発明の実施する方法を図示する。
【図１０】本発明を実施する他の方法を図示する。
【図１１】符号語長選択を図示する。
【図１２ａ】試験パターンカウントを図示する。
【図１２ｂ】試験パターンカウントを図示する。
【図１２ｃ】試験パターンカウントを図示する。
【図１２ｄ】試験パターンカウントを図示する。
【図１３ａ】試験パターンカウント減少を図示する。
【図１３ｂ】試験パターンカウント減少を図示する。
【図１３ｃ】試験パターンカウント減少を図示する。
【図１３ｄ】試験パターンカウント減少を図示する。
【技術分野】
【０００１】
本発明は、自動試験パターン生成に関し、特に、集積回路の試験中にグラウンドバウンス（ground-bounce）を避けることができる試験パターン生成に関する。
【背景技術】
【０００２】
デジタルシステムにおいて、通常は、構成要素間に多数の内部配線が存在する。既知の試験信号を使用してこれらの内部配線を試験することができることは、設計及び製造プロセスの重要な部分である。前記内部配線は、本明細書において“ネット”と称される。
【０００３】
多くの試験生成アルゴリズムが過去に提案されている。例えば、Jose T de Sousa and Peter Y K Cheung, “Boundary-Scan Interconnect Diagnosis”, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001を参照する。試験生成アルゴリズムの目的は、特定の最小の検出及び診断特性を用いて、試験パターンの最小の可能なセットを生成することである。典型的にこのような試験生成アルゴリズムによりアドレスされる故障モデルは、単一ネットの短絡及び複数ネットの橋絡である。
【０００４】
２つ以上のデジタル構成要素間の複数の内部配線（ネット）を試験するために、デジタル試験刺激（stimuli）の組み合わせがネット入力部に印加され、応答がネット出力部において観測され、予測された応答と比較される。前記ネットの入力部の完全な制御が存在し、前記ネットの出力部が完全に観測可能であると仮定される。
【０００５】
以下の記載において、試験刺激に対する以下の用語が使用される。これらの用語は添付図面の図１に図示される。
−試験パターン：試験パターン２は、試験下のネットに対して同時に並列に印加される試験データビットのセットである。図１において、試験パターンは、試験データの列として示される。試験パターンは、時には並列試験ベクトル（ＰＴＶ、Parallel Test Vector）として知られる。
−符号語：符号語４は、試験中に個別のネットに対して連続的に印加される試験データビットのリストである。図１において、符号語は、試験データの行である。符号語は、時には直列試験ベクトル（ＳＴＶ、Sequential
Test Vector）として知られる。
【０００６】
Jarwala及びJau（(Najimi Jarwala and Chi W Jau, “A New Framework for Analyzing Test Generation and Diagnosis Algorithm for Wiring Interconnects”, Proceedings IEEE International Test Conference (ITC), pages 63-70, October 1989)は、以下の内部配線に対する決定性故障モデルを記載している。
−複数ネット故障は、２つ以上のネットの間に短絡を作成する橋絡故障であり、以下の特徴を持つ。
＊ワイヤードＯＲ（Wired-OR）：ドミナント（dominant）‘１’ドライバの場合、短絡が、短絡されたネット間で論理‘ワイヤードＯＲ’のように機能する。
＊ワイヤードＡＮＤ（Wired-AND）：ドミナント‘０’ドライバの場合、短絡が、短絡されたネット間で論理‘ワイヤードＡＮＤ’のように機能する。
＊ストロングドライバ（Strong-Driver）：特定のドライバが短絡を支配し、したがって短絡されたネットがドミナントドライバに従う。
−単一ネット故障は、単一ネット上の“スタックアット（stuck-at）”故障及び“スタックオープン（stuck-open）”故障を含み、以下の特徴とを持つ。
＊スタックアット０：この故障は、ネット上のデータ値が常に論理‘０’として読み出されるようになる。
＊スタックアット１：この故障は、ネット上のデータ値が常に論理‘１’として読み出されるようになる。
【０００７】
短絡を試験する要件は、全てのネットが一意的な符号語を得なければならないことである。ネットが故障無しである場合、各応答は一意的である。短絡の場合、短絡に関係するネットは同じ応答を持つ。したがって、これらの応答はもはや一意的ではなく、短絡が検出される。William Kautz（William H Kautz, Testing of Faults in Wiring nterconnects, IEEE Transactions on Computers, Vol C-23 (No 4): 358-363, April 1974）は、カウント・シーケンス・アルゴリズム（Counting Sequence Algorithm）として知られるようになった短絡の試験を提案した。単純なバイナリ・カウント・アルゴリズムが符号語を生成する。ｋ個のネットに対して、log2ｋ個の試験パターンが必要とされる。前記カウント・シーケンス・アルゴリズムは、最小の数の試験パターンで全ての短絡の検出を保証する。
【０００８】
全てのネットがスタックアット０オープンに対して試験されることを保証するために、全ての符号語が少なくとも１つの‘１’を含む必要がある。同様に、スタックアット１故障に対して、全ての符号語は、少なくとも１つの‘０’を含む必要がある。前記カウント・シーケンス・アルゴリズムは、これを保証しない。したがって、Goel及びMcMahon（P
Goel and M T McMahon, “Electronic Chip-In-Place Test”, Proceedings IEEE International Test Conference (ITC), pages 83-90, October 1982）は、修正カウント・シーケンス・アルゴリズムとして知られるようになった試験生成アルゴリズムを提案した。主なアイデアは、全て０及び全て１の符号語を禁じる場合に、オープン故障が検出されることができることである。したがって、ｋ個のネットに対して、log2(ｋ＋２)個の試験パターンが必要とされ、これは、０の代わりに１で開始する単純なバイナリ・カウント・アルゴリズムにより再び生成されることができる。前記修正カウント・シーケンス・アルゴリズムは、最小の数の試験パターンで全ての短絡及びオープンの検出を保証する。
【０００９】
Eerenstein及びMurisにより発行された（Lars Eerenstein and Math Muris, “Method for Generating Test Patterns to Detect an Electric Short circuit, a Method for Testing Electric Circuitry While Using Test Patterns So Generated, and a Tester Device for Testing Electric Circuitry with such Test Patterns”, 米国特許公開公報５６３６２２９）、他の内部配線試験生成アルゴリズムは、ＬａＭａアルゴリズムとして知られている。このＬａＭａアルゴリズムは、修正カウント・シーケンス・アルゴリズムに基づくが、１ではなく３ずつインクリメントする。前記ＬａＭａアルゴリズムは、ｋ個のネットに対してlog2(３ｋ＋２)個の試験パターンを必要とする。
【００１０】
上述の試験生成アルゴリズムは、故障の検出を保証する。しかしながら、故障の検出は別にして、診断解像度は、しばしば試験の他の重要な性質である。Jarwala及びJauは、診断解像度を分かりにくくするエイリアシングの状況を記載した。エイリアシングは、故障ネットの故障応答が他の故障無しネットの故障無し応答に等しい場合に生じる。この場合、前記故障無しネットも故障ネットにおける故障の影響を被っているのかどうかを決定することができない。Paul T. Wagner（“Interconnect Testing with Boundary Scan”, Proceedings IEEE International Test Conference (ITC), pages 52-57, October 1987）は、エイリアシングを避けるために（修正）カウント・シーケンス・アルゴリズムを改良する真／補数試験アルゴリズム（True/Complement Test Algorithm）を提示した。Wagnerの方法は、元のカウント・シーケンス・アルゴリズムの全ての試験パターンを印加し、反転値を持つ同じ試験パターンが後に続く。この反転された試験パターンにより、全て０及び全て１の符号語は生成されない。したがって、カウントシーケンスの番号０及びｋ−１を除外する必要はない。したがって、前記真／補数試験アルゴリズムは、２log2ｋ個の試験パターンを必要とする。前記真／補数試験アルゴリズムは、反転により全ての符号語が等しい数の０及び１を含むことを保証する。
【００１１】
他のネットとの‘ワイヤードＯＲ’故障の場合、応答語において、１の数は増加され、０の数は減少される。同様に、他のネットとの‘ワイヤードＯＲ’故障の場合、応答語において、１の数が増加され、０の数が減少される。同様に、他のネットとの‘ワイヤードＡＮＤ’故障の場合、０の数が増加され、１の数が減少される。スタックアット・オープン故障の場合、全ての応答値は、全て０又は全て１のいずれかである。したがって、全ての故障の場合に、０及び１の数は変化し、この結果、応答語がもはや等しい数の０及び１を含むことはない。したがって、故障応答は、他のネットの故障無し応答と等しいことはなく、したがって、前記真／補数試験アルゴリズムは、エイリアシング無しである。図２（ｄ）の例において、ｋ＝４を用いて、
【数１】
の試験パターンを必要とする。符号語は、１１００、１００１、０１１０及び００１１であり、４つのネットに任意に割り当てられることができる。図１は、図示された５つのネット（ネット１…ネット５）に対する真／補数試験アルゴリズム試験パターンを図示する。
【００１２】
近年、グラウンドバウンスを避けることは、試験生成アルゴリズムに対する新しい制約になっている。グラウンドバウンスは、例えばＩＣ内部グラウンドと電源レベルとの間の並びに基板における電源電圧レベル及びグラウンドをシフトする現象を指し、ＩＣ上で同時に切り替わる多数の値により生じる可能性がある。グラウンドバウンスは、連続した試験パターン間の切り替え活動（switching activity）の量に上限を導入することにより避けられることができる。この制限は、同時切り替え出力制限（ＳＳＯＬ、Simultaneous Switching Output Limit）として知られている。
【００１３】
ＩＣの正常動作中に、トランジスタの間で大きな内部切り替え活動が存在する。大きすぎる活動は、電源からの電流需要（current demand）においてサージ（surge）を生じる可能性があり、ＩＣ内部電源又はグラウンドレベルを大幅に変動させる可能性がある。これは、システムクロック又はマスターリセットのような重要な信号上で擬似信号を生成させる可能性があり、これによりＩＣにおいて擬似的な挙動を生じる可能性がある。例えば、Hans Peter Richter and Norbert Munch, “Boundary-Scan Test Triumphs Over Ground-Bounce”, Test & Measurement World Europe, August/September 1997、又はAmitava Majumdar, Michio Komoda, and Tim Ayres, “Ground Bounce Considerations in DC Parametric Test Generation using Boundary Scan”, Proceedings IEEE VLSI Test Symposium (VTS), pages 86-91, April 1998を参照する。
【００１４】
グラウンドバウンスは、ＩＣの動作に負の影響を与える。ＩＣ内部グラウンド電圧レベルがＩＣ内部論理の閾値電圧まで上昇する場合、無効な論理挙動の可能性が存在する。バウンダリスキャン（Boundary-Scan）を備えたＩＣの場合、グラウンドバウンスは、擬似試験クロック（ＴＣＫ）を生じる可能性があり、前記擬似試験クロックは、オンボードのバウンダリスキャン装置を同期状態から外れさせる可能性がある。
【００１５】
グランドバウンスは、ＩＣが該ＩＣ内の（又は基板上のＩＣ間の）多量の切り替え活動を処理することができるようにＩＣ（又は基板）を設計することにより避けられることができる。試験中の切り替え活動は、典型的には、通常の（非試験）動作中より高い。この性質から、試験は回路を通して高感度の経路をセットアップし、これにより多くの出力の値を変化させる。試験時間を節約するために、しばしば試験生成アルゴリズムの目的は、最小の数の試験パターンで最高の可能な故障検出率を得ることである。これは、更に、試験パターンごとの内部切り替え活動の量を増加する。ＩＣ及び基板は、通常動作中及び試験動作中にグラウンドバウンスを処理するように設計される。実際に、ＩＥＥＥ１１４９.１２バウンダリスキャン規格は、バウンダリスキャンレジスタの使用に基づく全ての試験動作中に前記装置の内部にグラウンドバウンスが存在すべきでないことを命じる。問題は、基板レベルにおいて、内部配線試験に対するＥＸＴＥＳＴ試験モードにおける全てのオンボード・バウンダリスキャン装置で、たとえ各装置がグランドバウンス仕様内であっても、基板レベルのグラウンドバウンスが起こらないという保証は存在しない。実際に、数千以上のバウンダリスキャンからバウンダリスキャンへの内部配線が存在する場合、グラウンドバウンスが起こる確率は高い。
【００１６】
Richter及びMunchは、工業用電気通信基板上の１１４９.１準拠ＡＳＩＣ間のＥＸＴＥＳＴ試験中のグラウンドバウンス問題について報告した。全てのＡＳＩＣは、電気的なグラウンドバウンス仕様を満たし、シミュレーションは、多くとも５０％の同時に切り替わるＡＳＩＣ出力での通常動作の下でＡＳＩＣの正しい動作を確認した。ＡＳＩＣ設計者は、たとえ基板試験中に起こったことであっても、多くの（又は全ての）バウンダリスキャン出力が同時に切り替わることができる（最悪の場合のＥＸＴＥＳＴ）可能性を考慮していない。
【００１７】
グラウンドバウンスは、生成されて内部配線間に印加される試験パターンにおける切り替え活動の度合いを制御することにより基板レベルで避けられることができる。これは、幾つのバウンダリスキャン出力がある試験パターンから次の試験パターンへの遷移で同時に切り替えられることができるかに上限を導入することにより行われることができる。この記載において、この上限は、同時切り替え出力制限（ＳＳＯＬ）と称される。一般に、ＳＳＯＬは、基板の電気的設計に責任がある基板設計者により算出及び定義されるべきである。基板レベルの内部配線のＡＴＰＧツールの多くのベンダは、製品にＳＳＯＬ制約を加えている。
【００１８】
ＳＳＯＬ制約は、２つの連続した試験パターン間のデータビット遷移の最大数を制限する。連続した試験パターン間のビット遷移の数は、ハミング距離として知られており、図２に図示される。図２Ａにおいて、６つの試験パターン（ｐ1ないしｐ6）が示され、連続した試験パターン間のハミング距離６も示されている。試験パターンの連続した対の２つが、２のＳＳＯＬの推定レベルより大きいハミング距離を持つことがわかる。
【００１９】
したがって、これらの違反（violation）を除去するために前記試験パターンを修正する必要がある。違反を除去するためにこれまでに考えられた方法は、試験パターンの違反している対の間に追加の試験パターンを挿入することである。この場合、図２Ｂに示されるように、２つの追加の試験パターンｐ2i及びｐ5iが、これらの違反を除去するために追加される。図２Ｂの試験パターンの全ての対は、ＳＳＯＬレベルより小さいハミング距離を持つ。
【００２０】
しかしながら、試験生成にＳＳＯＬ制約を組み込むことは、一般に、追加の試験パターンの挿入を必要とするので、試験パターン数の増加、したがって試験時間の増加を引き起こす。
【００２１】
ＳＳＯＬ違反を克服するために単純に追加の試験パターンを挿入する従来のアプローチが不必要に大きな試験セットを生じる可能性があることは、Erik Jan Marinissen, Bart Vermeulen, Henk Hollmann, and Ben Bennetts, Minimizing Pattern ount for Interconnect Tests Under A Ground-Bounce Constraint. IEEE Design & Test of Computers, 20(2), March/April 2003に示されている。元の試験セットの全ての検出及び診断特性を維持しながら、挿入される必要がある追加の試験パターンの数を減少するために利用されることができる２つの自由度が存在する。
【００２２】
Marinissen他の論文は、本発明の背景を十分に記載するためにここでより詳細に説明される。
【００２３】
前記方法は、上述の真／補数試験パターン生成アルゴリズムを参照して記載されるが、前記方法が他のアルゴリズム又はアプローチにより生成された試験パターンに作用することができることは容易に理解される。
【００２４】
前記方法は２つの基本ステップ、即ち符号語サブセット選択及び試験パターン並べ替え（及び挿入）を使用する。全体的な方法は図３に図示される。ステップ１０において、自動試験パターン生成アルゴリズムが使用され、試験パターンの完全なセットを生成する。
【００２５】
ステップ１２（１２０、１２１、１２２）において、符号語サブセット選択が、何らかの方法（１２０）、遷移カウント方法（１２１）又は差分カウント方法（１２２）を使用して実行される。前記選択の結果は、並べ替えステップ１４にフィードされ、並び替えステップ１４は、試験パターンセットのＳＳＯＬ違反の数を最小化するために何らかの方法（１４１）、又は欲張り法（１４２）を使用して前記試験パターンを並び替える。様々な方法が下に詳細に記載される。
【００２６】
並び替えの後に、追加の試験パターンが、残りのＳＳＯＬ違反を除去するために必要な場所に挿入されることができる。
【００２７】
符号語サブセットの選択は、ここでより詳細に記載される。
【００２８】
ｋ個のネットに対して、試験生成アルゴリズムは、ｐ(ｋ)個の試験パターンを必要とする。ｐ(ｋ)個の試験パターンを用いて、前記アルゴリズムは、ｋ≦ｃ(ｋ)となるようなｃ(ｋ)個の一意的な符号語を生成する。関数ｐ(ｋ)及びｃ(ｋ)は、試験生成アルゴリズムに依存する。例えば、真／補数試験アルゴリズムに対して、ｐ(ｋ)及びｃ(ｋ)は以下のように与えられる。
【数２】
多くの実際的な場合において、ｋ、ｐ(ｋ)及びｃ(ｋ)は全て整数であるので、前記アルゴリズムは、厳密に必要な符号語より多い符号語を生成し、即ちｋ＜ｃ(ｋ)である。これは、前記の式が非整数を整数に切り上げるシール（ceil）演算子を有することを意味する。これらのシール演算子は、多くの場合、ｋ＜ｃ(ｋ)を生じる。
【００２９】
したがって、前記試験中に使用されるべき総数ｃ(ｋ)個の生成された符号語のサブセットを選択することが可能である。このようなサブセット選択は、試験の検出及び診断特性又は試験時間に影響を与えない。
【００３０】
選択するのに利用可能である
【数３】
個の可能なサブセットが存在する。一例として、ｋ＝２５７の真／補数試験アルゴリズムを考える。上記によると、ｃ(２５７)＝２log2257＝２9＝５１２である。したがって、
【数４】
個の代替符号語サブセットが存在する。
【００３１】
前記のサブセット選択手順は、ＳＳＯＬ違反無しの最小試験パターンセットを生じる符号語のサブセットを検索する。
【００３２】
前記符号語サブセット選択は、以下に記載される２つの発見的技法の１つにより実行されることができる。
【００３３】
第１の可能な発見的技法は、遷移カウントに基づき、図４に図示される。図４の例は、６つの試験パターン及び８つの符号語を生じるｋ＝５の場合を表す。図４Ａにおいて、試験パターンの完全なセット（ｃ1ないしｃ8）が、その中のビット遷移の数のカウント３０と一緒に示される。遷移カウント発見的方法を使用して、必要とされるｋ（＝５）個の符号語が、最小の遷移カウントを持つ５つの符号語として選択される。同じ遷移カウントを持つ符号語の選択のみが必要とされる場合、前記選択は任意に行われる。
【００３４】
図４Ｂは、連続した試験パターンの間のハミング距離３０と一緒に選択された符号語（ｃ1 ｃ2 ｃ4 ｃ5 ｃ8）を図示する。この場合、前記サブセットがＳＳＯＬ＝２に対する違反を持たない試験パターンセットを形成し、したがって他の処理が必要とされないことがわかる。当然、特にｋの大きな値に対しては、並び替え及び可能な挿入が必要とされる可能性がある。
【００３５】
第２の発見的アプローチは、差分カウント方法であり、これは図５に図示される。図５Ａは、真／補数方法を使用して生成されたｋ＝９及びＳＳＯＬ＝３の状況に対する完全な試験パターンセット（ｃ1ないしｃ16）を示す。各符号語は、前記符号語の前半のビットと前記符号語の後半のビットとの間の差の数に等しい関連した差分カウントを持つ。
【００３６】
この場合、最小の差分カウントを持つ符号語が選択され、正しい数ｋの符号語を提供する。同じ差分カウントを持つ符号語の間の選択が行われるべき場合、この選択は任意に行われる。
【００３７】
図５Ｂは、試験パターンの連続した対の間のハミング距離と一緒に符号語の選択されたサブセットを示す。複数の試験パターン対がＳＳＯＬ≦３の試験に不合格になり（fail）、したがって他の処理が必要とされることがわかる。以下に詳細に記載されるべき前記他の処理（並び替え）の結果は、図５Ｃに示される。
【００３８】
前記試験パターンの並び替え及び挿入はここでより詳細に記載される。
【００３９】
前記試験パターンの並び替えは、前の段階の間に選択された符号語のサブセットに実行される。したがって、ｐ個の試験パターンとｋ個の符号語とが存在する。
【００４０】
初めに、いわゆるＳＳＯＬ違反グラフが構築される。このようなグラフは、図６に示され、重み付けされ、完全に連結された無向グラフを有する。前記グラフのノードは、ｐ(ｋ)個の試験パターンに対応する。各対のノード間の辺は、前記対のノード間のハミング距離に依存する重みを与えられる。辺の重みは、これら２つのノード間のＳＳＯＬ違反の数を表す。
【００４１】
前記グラフのノードを通る経路を見つける問題は、巡回セールスマン問題（ＴＳＰ、traveling salesman problem）の１つのバージョンと見なされることができる。ＳＳＯＬ違反グラフに関して、ツアー（tour）に沿って通った辺の合計重みが最小化されるような前記グラフの全てのノードを通る経路を見つけることが必要である。
【００４２】
この問題は、周知の巡回セールスマン問題、M.R. Garey and D.S. Johnson, Computers and Intractability − A guide to the theory of NP-Completeness, W.H. Freeman and Company, San Francisco, CA, USA, 1979の最適化の改良に等しい。
【００４３】
巡回セールスマン問題（ＴＳＰ）が簡潔に記載され、以下のように要約されることができる。ｍ個の町のセットＣを仮定し、町ｃi,ｃj∈Ｃの各対に対する距離ｄ(ｃi,ｃj)及び正の整数Ｂを仮定する。長さＢ以下のＣのツアーは存在するか。
【００４４】
実際には、最適な解を計算するのに要する時間は、問題例（problem instance）のサイズと共に指数的に増加する。前記問題例サイズは、ノード（テストパターン）の数により決定される。幸いに、基板レベルの内部配線試験に対する問題例サイズはあまり大きくない。試験パターンの数は、log2ｋのオーダーであり、したがって、数千個のネットを持つ基板に対しても１０ないし２０個の試験パターンが存在する。したがって、最も実際的な問題例に対して、徹底的に、即ち前記グラフの全ての可能なツアーを数え上げることによりこの問題を解くことは実行可能と思われる。代わりに、文献に利用可能なＴＳＰに対する効果的及び効率的な発見的アルゴリズムが存在し、これは短い計算時間で最適に近い解でこの問題を解くことができる。例えば、David S. Johnson and Lyle A. McGeoch, “The traveling salesman problem: A case study”, in Emile H.L Aarts and Jan-Karel Lenstra, editors, “Local Search in Combinatorial Optimization”, pages 15-310, John Wiley & Sons Ltd., Chichester, England 1997を参照する。
【００４５】
図６Ｂは、ｋ＝５及びｓ＝２に対するＳＳＯＬ違反グラフを図示し、図６Ａは、前記グラフのノードを作り上げる順序付けられていない試験パターンセットを示す。順序付けられていない試験パターンセットは、ＳＳＯＬ基準を違反する試験パターンの対の２つの問題例を持つことがわかる。
【００４６】
図６Ｂにおいて、太線の矢印は、前記グラフを通るＳＳＯＬ違反なしのツアーを示す。図６Ｃは、前記試験パターンが前記グラフ内のＳＳＯＬ違反を最小化したツアーにより並べられた対応する結果の試験セットを示す。
【００４７】
ＴＳＰソルバ（TSP Solver）の実行後に、２つの可能な結果が存在し、即ち（１）合計重み０のツアーが得られる、又は（２）０より大きい合計重みを持つツアーが得られる。前者の場合、ＳＳＯＬ制約を満たす試験パターンの順序が見つけられている。後者の場合、依然として１つ以上のＳＳＯＬ違反を持つ試験パターンの順序が見つけられている。これは、合計重み０をもつツアーが存在しない、又はこのようなツアーが存在するが、使用された発見的ＴＳＰソルバがこれを見つけることができなかったという事実による可能性がある。いずれの場合にも、前記ツアーの合計重みの最小化は前記ＴＳＰソルバの目的関数だったので、ＳＳＯＬ違反の数が比較的低いことが予測される。
【００４８】
残りのＳＳＯＬ違反は、ＳＳＯＬ違反を持つ２つの連続した試験パターンの間に１つ以上の追加試験パターンを挿入することにより解決されることができる。連続した試験パターンｐ1及びｐ2がｗ(ｐ1,ｐ2)個のＳＳＯＬ違反を持つ（ｗ(ｐ1,ｐ2)＞０）場合、これら２つのパターンの間の全てのＳＳＯＬ違反を解決するためにｗ(ｐ1,ｐ2)／ｓの追加試験パターンを挿入することが必要である。
【００４９】
図５Ｃにおいて、試験パターンの１つの対がＳＳＯＬ基準を違反し、したがって１つの追加試験パターンがこの違反を除去するためにこれら２つの試験パターンの間に挿入されなければならないことがわかる。
【００５０】
Marinissen他の論文は、ＳＳＯＬ制約ｓの下でのｋ個のネットに対する試験パターンの最小の数に対する理論的上限及び下限の式を提供する。
【発明の開示】
【発明が解決しようとする課題】
【００５１】
したがって、ＳＳＯＬ制約を組み込むことができるが、生成されるべき試験パターンの数を更に最小化し、追加の最適化を使用する試験パターン生成アルゴリズムを提供することが望ましい。
【００５２】
本発明の実施例は、したがって、このようなアルゴリズムを提供し、ＳＳＯＬ違反無しの連続した試験パターンを所定の試験生成アルゴリズムに組み込むことを可能にする方法を提供することを志す。
【課題を解決するための手段】
【００５３】
本発明の１つの態様によると、複数の内部配線を試験するデジタル試験セットを生成する方法であって、各試験セットがビットのマトリクスを有し、前記マトリクスが第１の複数の試験パターン及び第２の複数の符号語を定め、各試験パターンの前記ビットが、互いに並列にそれぞれの内部配線に対して印加するものであり、内部配線に印加する連続した試験パターンのビットが該内部配線に対する符号語を形成し、各符号語が、ビット値遷移の数に関する遷移カウントを持ち、前記試験セットが、前記試験セット内の前記符号語の前記遷移カウントの和に関する合計遷移カウントを持ち、前記方法が、所定の閾値より小さい合計遷移カウントを持つ試験セットを生成するステップを有し、前記所定の閾値が前記試験セット内の試験パターンの数と所定の関係を持つ当該方法が提供される。
【発明を実施するための最良の形態】
【００５４】
本発明の好適な実施例は、添付図面を参照してここに記載される。
【００５５】
まず、初期試験パターンセットのバイナリコンテンツと連続した試験パターンに対する最大ハミング距離制約の違反を解決するために挿入される必要がある試験パターンの数との関係が解析される。
【００５６】
図７Ａは、行がｋ個の符号語に対応し、列がｂ個の試験パターンに対応する試験パターンマトリクスＣを図示する。前記ｋ個の符号語は、Ｃ1,...Ｃkにより示される。Ｃi,jは、１≦ｉ≦ｋ及び１≦ｊ≦ｂで符号語Ｃi内のビットｊを参照する。前記試験パターンはｐ1...ｐbにより示され、ここでｐj＝(Ｃ1,j,...,Ｃk,j)は、試験パターンマトリクスＣのｊ番目の列である。
【００５７】
遷移及び遷移カウントは解析において重要であるので、試験パターンマトリクスＣの代替表記が使用される。遷移マトリクスＴが計算され、これは、ｋ×(ｂ−１)マトリクスＴ及びｋ個の初期符号語値Ｃi,1を有する。遷移マトリクスＴは図７Ｂに図示される。マトリクスＣとマトリクスＴとの関係は、
【数５】
により与えられる。ｊ＝１...ｂ−１に対し、連続した試験パターンｐjとｐj+1との間のハミング距離は、
ｄj＝ｄH(ｐj,ｐj+1)
として定義される。単純のため、連続した試験パターンは相異なる、
即ち、全てのｊに対してｄj＞０
であると仮定される。この仮定が与えられると、試験パターンマトリクスＣがＳＳＯＬ制約ｓとの組み合わせで使用される場合、[ｄj／ｓ]−１個の試験パターンが、ｐjとｐj+1との間に挿入されなければならない。したがって、挿入後に、所定の試験セットに基づくＳＳＯＬ制約ｓの下で必要とされる試験パターンの総数Ｐsは、以下の式を満たす。
【数６】
ｉ＝１...ｋに対してτiが符号語Ｃiにおける遷移の数を示すとし、即ち
τi＝＃｛ｊ∈{１,...ｂ−１}｜Ｃi,j≠Ｃi,j+1｝
である。この目的は、試験パターンマトリクスＣ内の遷移の総数
【数７】
に関して試験パターンの総数Ｐsに対する下限及び上限を算出することである。この解析は、
【数８】
による前記試験の合計距離ｄtotの定義に基づく。
【００５８】
試験パターンマトリクスＣの１行の遷移の総数は、遷移マトリクスＴの対応する行の１の数により与えられる。連続した試験パターンの間のハミング距離は、遷移マトリクスＴの関連する列の１の数により与えられる。したがって、τtot及びｄtotの両方が、遷移マトリクスＴの１の総数を、一方は行により、及び他方は列により、カウントする。
【００５９】
形式的には、
【数９】
である。
【００６０】
合計ハミング距離が、遷移の総数に等しいという事実は、τtotのみに依存するＰsに対する上限及び下限を算出するために使用されることができる。
【００６１】
長さｂの符号語からなる試験パターンセットは、合計τtot個の遷移を含む。試験パターンの総数Ｐsは、ＳＳＯＬ制約ｓを満たすための挿入の後では、
【数１０】
により与えられる。この式の証明は下で与えられる。
０≦ｒ＜ｓで、τtot＝ｑｓ−ｒとする。各ｊに対し、０≦ｒj＜ｓで、ｄj＝ｑjｓ−ｒjとする。上で与えられた式によると、
【数１１】
である。これから続いて、
【数１２】
であり、｜ｄj／ｓ｜＝ｑjなので、
【数１３】
である。結果として、
【数１４】
及び
【数１５】
である。Ｐsは整数なので、この定理が従う。
【００６２】
この定理から、固定された符号語長ｂに対して、ＳＳＯＬ制約ｓの下での挿入の後の試験パターンの総数は、遷移の総数が小さい符号語の集合を使用することによってのみ小さくされることができる。
【００６３】
したがって、本発明の一実施例は、試験パターンマトリクスＣ内の遷移の総数を最小化しようとする。
【００６４】
本発明の他の態様がここに記載される。この態様は、ＳＳＯＬ制約ｓの下で必要とされる試験パターンの総数を最小化する、固定された長さｂのｋ個の符号語のほぼ最適なセットの選択を可能にする方法を生じる。少なくともｋ個の符号語を利用可能にするためには、２b≧ｋである。したがって、ｂ≧ｂmin＝｜log2ｋ｜が仮定される。
【００６５】
本発明のこの態様は、以下の符号語選択方法を使用する。０個の遷移を持つ全ての語を選択し、次いで１個の遷移を持つ全ての語を選択し、ｔ−１個の遷移を持つ全ての語まで選択し、最終的にｔ個の遷移を持つ幾つかの追加の語を選択する。ここでｔは、必要とされる符号語の数ｋが多くともｔ−１個の遷移を持つ長さｂの語の数より大きいが、多くともｔ個の遷移を持つ長さｂの語の数より大きくないような数である。
【００６６】
この技法は図８に図示され、試験パターンマトリクスＣ及び遷移マトリクスＴが示される。前記２つのマトリクスの行は、一番上の０個の遷移（マトリクスＣ）又は０個の１（マトリクスＴ）からこの図の下のｔ個の遷移又はｔ個の１まで並べられる。本発明の本実施例によると、前記符号語は、前記マトリクスの一番上から選択され、所要の数ｋの符号語が選択されるまで下に向かう。両方の試験セット表現に対し、前記図は、符号語が生成されるグレイの陰影を用いて示す。
【００６７】
このように選択された試験パターンセット内の遷移の総数が、ｔ個の遷移を持つ特定の符号語の選択に依存せず、構成により、長さｂのｋ個の符号語のセットにおける遷移の最小の数であることに注意するのは有用である。これはτtot(ｂ)により示される。
【００６８】
この方法に基づいてアルゴリズムを解析するために、及びτtot(ｂ)を計算することができるために、以下の結果が必要とされる。
【００６９】
正確にｉ個の１を持つ長さｂ−１の語の数は、
【数１６】
に等しい。図７に示されるようなｋ×ｂの符号語マトリクスＣとｋ×(ｂ−１)の遷移マトリクスとの間の対応関係から、これらの語のそれぞれがｉ個の遷移を持つ正確に２つの符号語に対応することがわかる。
【００７０】
ｋiを前記試験セットに含まれるｉ個の遷移を持つ符号語の数とする。前記試験セット内の遷移の総数Σiｉｋiを最小化するために、前記符号語選択方法は、多くともｔ−１個の遷移を含む全ての語とｔ個の遷移を含む語の幾つかとを符号語として選択する。したがって、０≦ｉ≦ｔ−１に対して
【数１７】
であり、ｔは、
【数１８】
となるものである。τtot(ｂ)に対して、ここで式
【数１９】
が得られる。この符号語選択方法は、ＳＳＯＬ制約ｓを満たし、長さｂの符号語を使用するｋ個のネットに対する試験セットにおいて必要とされる試験パターンの最小の数ｐ(ｋ,ｓ,ｂ)の限界を算出するために使用される。τtot＝τtot(ｂ)である長さｂの符号語を使用する試験セット（実際には多くの試験セット）が存在することが上で示され、明らかにこのような試験は同様な値のτtotを持つことができないので、
【数２０】
が結論付けられることができる。この符号語選択方法及びｋt個の追加の符号語を選択する特定の方法を使用するアルゴリズムは、この式の限界内に位置する挿入後の試験パターンの総数を得ることに注意する。
【００７１】
特に、これは、Marinissen他の遷移カウント符号語サブセット選択発見的アルゴリズムに適用できる。
【００７２】
本発明の実施例において、この式の上限は、改良された最悪の場合の挙動を持つアルゴリズムを使用することにより改良されることができる。前記アルゴリズムは、以下の関係
【数２１】
を使用し、ここでｋ及びｂは固定されている。
【００７３】
ここで、ＳＳＯＬｓを満たす多くとも
【数２２】
個の試験パターンを生成し、したがって上限を確立する符号語選択方法に基づくアルゴリズムが記載される。
【００７４】
このアルゴリズムの背後にあるアイデアは、以下のとおりである。ｋt個の追加符号語を選択した後に結果として生じる距離ｄjは、挿入後の結果として生じる試験パターンの数を決定する。前記符号語選択方法により、合計距離
【数２３】
は、常に同じ（即ちτtot(ｂ)）であるが、距離ｄjの正確な値は、追加のｋt個の符号語の選択に依存する。全てのｄjがわずかにｓの倍数の上である状況を避けることが望ましく、前記状況は最悪の場合の挙動であり、前記上限はこれに基づく。
【００７５】
好ましくは、全てのｄjは、ｓの倍数に等しいか又はわずかに下であるべきだが、これは、一般に保証するのは難しい。前記最悪の場合の挙動は、距離ｄjが全てほぼ等しいことを確実にすることにより避けられる。以下では、まず、多くともｔ−１個の遷移を持つ符号語の距離ｄjの部分がｊと独立に一定であることが示される。次いで、ｄjがほぼ等しいままであるような残りのｋt個の符号語を選択する方法が説明される。
【数２４】
を仮定し、ここでｄj,eは、ｌ（エル）個の遷移を含む符号語のｄjとｄj+1との間のハミング距離の部分であり、即ち
【数２５】
である。０個の遷移を持つ２つの符号語、即ち全て０及び全て１の符号語のみが存在し、したがってｄj,0＝０である。所定の位置ｊ∈{１,...,ｂ−１}に１を含むｌ（エル）個の１を持つ長さｂ−１のＴ内の語の数は、
【数２６】
である。Ｔのそれぞれのこのような語は、ｄj,eに対して１回だけそれぞれ寄与するｌ（エル）個の遷移を持つＣ内の２つの符号語（一方は０で始まり、他方は１で始まる）に対応するので、結果は以下のとおりである。
結果として、
【数２７】
である。ｔ個の遷移を含むｋt個の符号語の選択は、ここに記載される。
【数２８】
の場合、ｔ個の遷移を持ち０で開始する全ての語が、更に選択される。ここまでに選択された符号語による距離ｄjの部分がｊと独立に一定であることに注意することは重要である。ここで、ｋt*を
【数２９】
により定義されるものとする。後の使用のため、
【数３０】
であることに注意すべきである。この場合、（
【数３１】
の場合には全て０で開始し、
【数３２】
の場合には全て１で開始する）ｔ個の遷移を持つｋt*個の追加の符号語、又は同等に、（前記符号語内の遷移を表す）ｔ個の１を含む長さｂ−１のｋt*個の語を選択することは依然として必要である。便宜のため、サイズｔの｛１,...,ｂ−１｝のサブセットを持つｔ個の１を含む長さｂ−１の語が識別される。この場合、セットに関して、｛１,...,ｂ−１｝からサイズｔのｋt*個の相異なるサブセットを選択することは、依然として必要である。これらｋt*個の語に対応する位置における距離ｄjの（可変）部分が、セットに関して、これらｋt*個のセットにおける要素ｊの発生の頻度ｆjになることに注意する。したがって、以下の定義が必要とされる。ベクトルｆ＝(ｆ1,...,ｆn)は、ｉ＝１,...,ｎの全てに対してｆi∈{ｅ,ｅ＋１}となるような整数ｅが存在する場合にバランスされる（balanced）と称される。
【００７６】
ここで、残りのｋt*個の符号語が、これらｋt*個の符号語における距離ｄjの部分がバランスされるように選択されることが確実にされる。即ち、セットに関して、頻度ｆjがバランスされることが確実にされる。このアルゴリズムは以下の結果に基づく。
【００７７】
１≦ｔ≦ｎとする。
【数３３】
であるような重みｆ1＋...＋ｆn＝ｍｔを持つバランスされた整数ベクトルｆ＝(ｆ1,...,ｆn)が存在すると仮定する。この場合、各ｉがセットＳjのｆiで生じるような{１,...,ｎ}のサイズｔのｍ個の相異なるサブセットの集合Ｓ＝{Ｓ1,...,Ｓm}が存在する。
【００７８】
本発明のこの態様を実施するアルゴリズムは、以下の関数を実行し、図９に図示される。初めに、ステップ１００において、
【数３４】
にしたがって数ｔ及びｋtを選択する。
次に、ステップ１０２において、
【数３５】
から数ｍ＝ｋt*を決定する。
次に、ステップ１０４において、多くともｔ−１個の遷移を持つ長さｂの符号語の選択が行われ、ｍ＜ｋtの場合には、ｔ個の遷移を持ち、１で始まる長さｂの全ての語の選択も行われる。
【００７９】
最後に、ステップ１０６において、ｔ個の遷移を持ち、（ｍ＜ｋtの場合）０又は（ｍ≧ｋtの場合）１で始まる長さｂの他のｍ個の語が選択される。ここでｍｔ＝ｑ(ｂ−１)＋ｒの場合、ｒ個のインデックスｉに対してｆi＝ｑ＋１が選択され、残りのｂ−１−ｒ個のインデックスｉに対してｆi＝ｑが選択される。この場合、このアルゴリズムは、距離ｄjがバランスされることを確実にする。この方法は、“固定符号語長に対するＡＴＰＧ”と称されることができる。
【００８０】
ここで、平均ハミング距離は、τtot(ｂ)／(ｂ−１)に等しく、したがってｄj≦｜τtot(ｂ)／(ｂ−１)｜であり、したがって、
【数３６】
である。したがって、このアルゴリズムが、ＳＳＯＬ制約ｓを満たすための挿入の後に、パターンの総数が（多くとも）１＋(ｂ−１)≦τtot(ｂ)／((ｂ−１)s)であるような試験セットを生成すると結論付けることが可能であり、したがって前記上限を証明する。
【００８１】
少なくともｋ個の符号語を利用可能にするために、符号語長ｂは、ｂ≧ｂmin：＝｜log2ｋ｜となるように選択されなければならないと上で述べられた。しかしながら、ｂがこの最小値ｂminに等しく選択される場合に、必ず多数の符号語が多くの遷移を含む。
【００８２】
ｉ個の遷移を持つ長さｂの利用可能な符号語の数は、
【数３７】
により与えられる。したがって、ｉ個の遷移を持つ利用可能な符号語の数は、ｂの値が増加する場合に増加する。したがって、上述の符号語選択方法のように、最小の数の遷移を含むｋ個の符号語を選択することにより、結果として生じる遷移の数τtot(ｂ)、及びこれにしたがって確実に量τtot(ｂ)／(ｂ−１)は、ｂが増加すると減少する。
【００８３】
この提案は、以下のように始められることができる。関数τtot(ｂ)は、≧ｂminに対してｂの減少関数であり、即ちｂmin≦ｂ＜ｂ’の場合、τtot(ｂmin)≧τtot(ｂ)≧τtot(ｂ’)である。
この観測結果は、
【数３８】
であり、ＳＳＯＬ制約ｓを満たし、ｋ個のネットに対する試験セットで必要とされる試験パターンの最小の数は、しばしばｂminより大幅に大きい値ｂに対して実現されることを提案する。
【００８４】
変化するｂに対する上述の限界の挙動を示すために、図９は、ｂ≧ｂminに対して、ｋ＝６０００及びｓ＝６００に対して、上限
【数３９】
及び下限の１つ
【数４０】
の両方を示す。
ｂに対する最良の選択は、平均距離τtot(ｂ)／(ｂ−１)が多くともｓであるｂの第１の（最小の）値ｂ*に近い。この値ｂ*に対して、Ｕ(ｂ*)＝ｂ*であることに注意する。以下、ｂ*の値の推定値が与えられ、したがって試験パターンの対応する総数に対して、ｋ及びｓを前提とするとｐ(ｋ,ｓ,ｂ)＝ｂ*である。
符号語の数ｋ及びＳＳＯＬ値ｓが固定されているとする。前に見たように、各ｂに対して、ｔの値は、
【数４１】
のように選択され、この結果、スターリングの近似（Stirling's approximation）により
log2ｋ≒１＋(ｂ−１)ｈ(ｔ／(ｂ−１))
となり、ここでｈ(ｘ)＝−ｘlog2ｘ−(１−ｘ)log2(１−ｘ)である。
また、合計距離についても、
ｄtot＝τtot≒ｔｋ
したがって、ｔ／(ｂ−１)≒ｓ／ｋの場合、
ｄtot≒(ｂ−１)ｓ
である。
これらの式を組み合わせると、
Ｐ*＝ｂ*≒１＋(−１＋log2ｋ)／ｈ(ｓ／ｋ)
を与える。
結局のところ、ｂ*のこの推定値は、いくらか小さすぎるが、常に真の値の少なくとも約８０％である。
【００８５】
少し意外なことに、ｂの最適値、即ちｐ(ｋ,ｓ,ｂ)を最小化するｂの値は、実際には常に上で定義された数ｂ*に等しいことが判明し、即ち以下の結果が生じる。
【００８６】
ｋ≧２でｋ及びｓが正の整数であるとする。関数τtot(ｂ)を
【数４２】
となるように定義する。
ｂmin＝｜log2ｋ｜とし、数ｂ*をτtot(ｂ)≦(ｂ−１)ｓとなる最小の整数ｂ≧ｂminになるように定義する。次いで、ＳＳＯＬ制約ｓを満たし、ｋ個のネットに対する試験セットに必要とされる試験パターンの最小の数ｐ(ｋ,ｓ)は、ｐ(ｋ,ｓ)＝ｂ*を満たす。
【００８７】
この定理の結果として、ＳＳＯＬ制約ｓを満たし、最小の数の試験パターンを含むｋ個のネットに対する試験セットを生成するために、本発明の他の態様の実施例は、図１０に図示され、以下のように進行する。
まず、ステップ１１０において上で定義したように数ｂ*を決定する。次いで、上述のように、固定された長さｂ*を持つ符号語と共に固定符号語長アルゴリズムを適用する。次に、ステップ１１２において、
【数４３】
にしたがってｔ及びｋtを選択する。次に、ステップ１１４において、
【数４４】
から数ｍ＝ｋt*を決定する。次に、ステップ１１６において、多くともｔ−１個の遷移を持つ長さｂ*の符号語の選択が行われ、ｍ＜ｋtの場合、ｔ個の遷移を持ち１で始まる長さｂ*の全ての語の選択も行われる。
【００８８】
最後に、ステップ１１８において、０（ｍ＜ｋtの場合）又は１（ｍ≧ｋtの場合）で始まりｔ個の遷移を持つ長さｂ*の他のｍ個の語が選択される。ここで、ｍｔ＝ｑ(ｂ*−１)＋ｒの場合、ｒ個のインデックスｉに対してｆi＝ｑ＋１が選択され、残りのｂ*−１−ｒ個のインデックスｉに対してｆi＝ｑが選択される。このアルゴリズムは、この場合、距離ｄjがバランスされることを確実にする。
【００８９】
この方法は、ｂ*個のパターンを持ち、連続したパターンが多くともｓの距離を持つ試験パターンセットを生成する。前記方法は、“可変符号語長に対するＡＴＰＧ”と称されることができる。
【００９０】
実験結果が、新しいＳＳＯＬ制約ＡＴＰＧアルゴリズムに対して下に与えられ、これらの結果を他の方法からの結果に対して比較する。真／補数試験が、比較の基準として使用されるが、この技法は、試験パターンセットを生成する他の方法に適用されることができる。
【００９１】
実験データにおいて、３つの方法が比較される。
【００９２】
１．従来の方法
この方法は、従来のカウント及び後に続く補数演算（complementing）を用いて真／補数試験を生成する。この後に、前記ＳＳＯＬ制約が、従来の追加試験パターンの挿入により満たされる。この方法は、多くの専門（市販）ツールの基本である。
【００９３】
２．Marinissen他の最良の方法
この方法は、従来のカウント及び後に続く補数演算を用いて真／補数試験を生成する。この後に、遷移カウントに基づく符号語サブセット選択及び試験パターン並び替えが適用される。残りのＳＳＯＬ違反は、従来の追加試験パターンの挿入により解決される。この方法は、Marinissen他に記載された様々な方法から最良に実行されるものである。
【００９４】
３．可変符号語長に対するＡＴＰＧ
この方法は、上述のように“真の（True）”試験セットを生成する。この試験は、ＳＳＯＬ違反が無いことを保証され、したがって追加の試験パターンの挿入を必要としない。この後に、“補数（Complement）”部分が、再びＳＳＯＬ違反の無い補数の（complementary）試験セットを追加することにより生成される。“真の”及び“補数”試験パターンの間の境界において、通常は、少数の追加試験パターンが挿入される必要がある。図１２は、ｋ∈{5000，6000，7000，8000}個のネットを持つ問題例に対する実験結果を示す。ｋの５％と５０％との間で変化するＳＳＯＬ値ｓに対し、図１２は、３つ全ての方法に対する試験パターンカウントｐ(ｋ,ｓ)をプロットする。図１３は、基準の従来の方法に対して以前のMarinissen他の方法及び新しい可変符号語長に対するＡＴＰＧの試験パターンカウントの向上を示す。
【００９５】
図１２及び１３は、全てのＳＳＯＬ値ｓに対して、前記従来の方法が最高数の試験パターンを生じることを示す。ｋ及びｓの幾つかの値に対して、Marinissen他の最良の方法は、前記従来の方法に対する大幅な向上を提供するが、しかしながら、この方法が向上を与えない多くの値のｋ及びｓが存在する。
【００９６】
本発明の実施例、新しい可変符号語長に対するＡＴＰＧ技法は、明らかに他のアプローチより性能が優れており、ｋ＝5000，6000，7000，8000に対して、前記従来の方法に対する平均の相対的向上は、それぞれ４６％、４６％、４５％及び４４％である。この新しいＡＴＰＧアルゴリズムは、ｋ及びｓの全ての値に対して前記従来の方法から一貫して向上している。
【００９７】
ユーザが決めたネットの数ｋに対して、ユーザが決めたＳＳＯＬ制約ｓを順守する試験パターンの最小のセットｐ(ｋ,ｓ)を生成する最適なＡＴＰＧアルゴリズムが記載されている。このアルゴリズムは、形式化され上で証明された以下の観測結果に基づく。
−試験パターンの数は、符号語内の遷移の数に強く関係している。したがって、少数の試験パターンを持つ有効な試験セットを得るためには、少数の遷移を持つ符号語を選択しなければならない。
−上の観測に基づき、与えられたｋ、ｓ及びｂに対して、多くともｔ−１個の遷移を持つ長さｂの全ての符号語を選択し、この後に、連続した試験パターンの間のバランスされたハミング距離ｓを持つ正確に合計ｋ個の符号語が得られるように、ｔ個の遷移を持つ長さｂの幾つかの語を注意深く選択するアルゴリズムが提示されている。したがって、残りのＳＳＯＬ違反を解決するために挿入された追加試験パターンを加えた前記試験パターンからなる結果の試験セットが得られる。
−与えられたｋ及びｓに対して値ｂ＝ｂ*を見つける第２のアルゴリズムであって、上記アルゴリズムがこのｂ*に対して呼び出される場合に、ＳＳＯＬ制約を満たすために追加試験パターンが挿入される必要の無いことが保証されることができる当該第２のアルゴリズムが示されており、更に、この第２のアルゴリズムが証明可能に最小の試験パターンセットを生成することが示されている。
【００９８】
一例として一般に使用される真／補数試験アルゴリズムを使用して、ｋ∈{5000，6000，7000}及びｋの５％から５０％まで変化するｓに対する実験結果が示されている。この実験は、前記アルゴリズムが前記従来の方法と比較した場合に試験パターンの数の平均４５％の減少を生じることを示す。
【図面の簡単な説明】
【００９９】
【図１】試験パターン及び符号語を図示する。
【図２Ａ】真／補数試験パターン生成アルゴリズムに対する５つのネットに対する試験刺激を図示する。
【図２Ｂ】真／補数試験パターン生成アルゴリズムに対する５つのネットに対する試験刺激を図示する。
【図３】本発明の１つの態様を実施する方法を図示する。
【図４Ａ】符号語サブセット選択の第１の方法を図示する。
【図４Ｂ】符号語サブセット選択の第１の方法を図示する。
【図５Ａ】符号語サブセット選択の第２の方法を図示する。
【図５Ｂ】符号語サブセット選択の第２の方法を図示する。
【図５Ｃ】符号語サブセット選択の第２の方法を図示する。
【図６Ａ】試験パターンを並び替える方法を図示する。
【図６Ｂ】試験パターンを並び替える方法を図示する。
【図６Ｃ】試験パターンを並び替える方法を図示する。
【図７Ａ】試験マトリクス及び遷移マトリクスを図示する。
【図７Ｂ】試験マトリクス及び遷移マトリクスを図示する。
【図８Ａ】符号語の選択を図示する。
【図８Ｂ】符号語の選択を図示する。
【図９】本発明の実施する方法を図示する。
【図１０】本発明を実施する他の方法を図示する。
【図１１】符号語長選択を図示する。
【図１２ａ】試験パターンカウントを図示する。
【図１２ｂ】試験パターンカウントを図示する。
【図１２ｃ】試験パターンカウントを図示する。
【図１２ｄ】試験パターンカウントを図示する。
【図１３ａ】試験パターンカウント減少を図示する。
【図１３ｂ】試験パターンカウント減少を図示する。
【図１３ｃ】試験パターンカウント減少を図示する。
【図１３ｄ】試験パターンカウント減少を図示する。
【特許請求の範囲】
【請求項１】
複数の内部配線を試験するデジタル試験セットを生成する方法において、各試験セットがビットのマトリクスを有し、前記マトリクスが第１の複数の試験パターン及び第２の複数の符号語を定め、各試験パターンのビットが互いに並列にそれぞれの内部配線に印加され、１つの内部配線に印加される連続した試験パターンのビットが該内部配線に対する符号語を形成し、各符号語が複数のビット値遷移に関する遷移カウントを持ち、前記試験セットが、前記試験セット内の前記符号語の前記遷移カウントの合計に関する合計遷移カウントを持ち、前記方法が、所定の閾値より小さい合計遷移カウントを持つ試験セットを生成するステップを有し、前記所定の閾値が前記試験セット内の前記試験パターンの数と所定の関係を持つ方法。
【請求項２】
前記所定の閾値が第２の閾値と所定の関係を持つ、請求項１に記載の方法。
【請求項３】
前記第２の閾値が前記内部配線に対する同時に切り替わる出力の制限である、請求項２に記載の方法。
【請求項４】
前記試験セットを生成するステップが、
符号語の第１のセットを定める第１の試験セットを生成するステップと、
前記符号語の第１のセットのサブセットを選択するステップであって、前記サブセット内の前記符号語に対する前記遷移カウントの合計が前記所定の閾値より小さくなるように当該サブセットを選択するステップと、
を有する、請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
前記符号語のサブセットを選択するステップが、
第１の値より小さい遷移カウント値を持つ第１の複数の符号語を選択するステップと、前記第１の値以上のそれぞれの遷移カウントを持つ第２の複数の符号語を選択するステップであって、前記第１及び第２の複数の選択された符号語の数の合計が前記内部配線の数に等しくなるように当該第２の複数の符号語を選択するステップと、
を有する、請求項４に記載の方法。
【請求項６】
前記試験セット内の前記符号語の数が前記内部配線の数に等しい、請求項１ないし５のいずれか一項に記載の方法。
【請求項７】
前記試験セットに追加の試験パターンを追加するステップを更に有する、請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
前記追加の試験パターンを追加するステップが、閾値より大きい元の遷移距離を持つ試験パターンの対の間に追加の試験パターンを挿入するステップを有し、前記挿入された試験パターンが遷移距離を前記元の遷移距離より小さくする、請求項７に記載の方法。
【請求項９】
前記挿入された試験パターンが遷移距離を所定の閾値レベル以下にする、請求項７に記載の方法。
【請求項１０】
前記追加の試験パターンを追加するステップが、最終的な真／補数試験セットを形成するために前記試験セットに前記試験セットの補数を追加するステップを有する、請求項７に記載の方法。
【請求項１１】
複数の内部配線を試験する方法において、
請求項１ないし１０のいずれか一項に記載された方法により生成された試験セットを複数の内部配線に印加するステップと、
この印加の結果を解析するステップと、
を有する方法。
【請求項１】
複数の内部配線を試験するデジタル試験セットを生成する方法において、各試験セットがビットのマトリクスを有し、前記マトリクスが第１の複数の試験パターン及び第２の複数の符号語を定め、各試験パターンのビットが互いに並列にそれぞれの内部配線に印加され、１つの内部配線に印加される連続した試験パターンのビットが該内部配線に対する符号語を形成し、各符号語が複数のビット値遷移に関する遷移カウントを持ち、前記試験セットが、前記試験セット内の前記符号語の前記遷移カウントの合計に関する合計遷移カウントを持ち、前記方法が、所定の閾値より小さい合計遷移カウントを持つ試験セットを生成するステップを有し、前記所定の閾値が前記試験セット内の前記試験パターンの数と所定の関係を持つ方法。
【請求項２】
前記所定の閾値が第２の閾値と所定の関係を持つ、請求項１に記載の方法。
【請求項３】
前記第２の閾値が前記内部配線に対する同時に切り替わる出力の制限である、請求項２に記載の方法。
【請求項４】
前記試験セットを生成するステップが、
符号語の第１のセットを定める第１の試験セットを生成するステップと、
前記符号語の第１のセットのサブセットを選択するステップであって、前記サブセット内の前記符号語に対する前記遷移カウントの合計が前記所定の閾値より小さくなるように当該サブセットを選択するステップと、
を有する、請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
前記符号語のサブセットを選択するステップが、
第１の値より小さい遷移カウント値を持つ第１の複数の符号語を選択するステップと、前記第１の値以上のそれぞれの遷移カウントを持つ第２の複数の符号語を選択するステップであって、前記第１及び第２の複数の選択された符号語の数の合計が前記内部配線の数に等しくなるように当該第２の複数の符号語を選択するステップと、
を有する、請求項４に記載の方法。
【請求項６】
前記試験セット内の前記符号語の数が前記内部配線の数に等しい、請求項１ないし５のいずれか一項に記載の方法。
【請求項７】
前記試験セットに追加の試験パターンを追加するステップを更に有する、請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
前記追加の試験パターンを追加するステップが、閾値より大きい元の遷移距離を持つ試験パターンの対の間に追加の試験パターンを挿入するステップを有し、前記挿入された試験パターンが遷移距離を前記元の遷移距離より小さくする、請求項７に記載の方法。
【請求項９】
前記挿入された試験パターンが遷移距離を所定の閾値レベル以下にする、請求項７に記載の方法。
【請求項１０】
前記追加の試験パターンを追加するステップが、最終的な真／補数試験セットを形成するために前記試験セットに前記試験セットの補数を追加するステップを有する、請求項７に記載の方法。
【請求項１１】
複数の内部配線を試験する方法において、
請求項１ないし１０のいずれか一項に記載された方法により生成された試験セットを複数の内部配線に印加するステップと、
この印加の結果を解析するステップと、
を有する方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１２ｄ】
【図１３ａ】
【図１３ｂ】
【図１３ｃ】
【図１３ｄ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１２ｄ】
【図１３ａ】
【図１３ｂ】
【図１３ｃ】
【図１３ｄ】
【公表番号】特表２００７−５１４１３１（Ｐ２００７−５１４１３１Ａ）
【公表日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願番号】特願２００６−５３０８８８（Ｐ２００６−５３０８８８）
【出願日】平成１６年５月１９日（２００４．５．１９）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０７５１
【国際公開番号】ＷＯ２００４／１０４６０９
【国際公開日】平成１６年１２月２日（２００４．１２．２）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願日】平成１６年５月１９日（２００４．５．１９）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０７５１
【国際公開番号】ＷＯ２００４／１０４６０９
【国際公開日】平成１６年１２月２日（２００４．１２．２）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]