(57)【特許請求の範囲】
【請求項１】
互いに接続される複数の記憶素子を備え、前記各記憶素子が出力を有する線形有限状態機械を生成し、
前記各記憶素子の負荷情報を獲得し、この負荷情報に基づいて、前記記憶素子の出力に接続される線形論理ゲートを有する線形移相器を生成し、
前記記憶素子の出力により前記線形移相器を駆動して、当該線形移相器を、任意の回路をテストする複数の走査チェーンに接続する
工程を含むテスト用移相器の生成方法。
【請求項２】
前記負荷情報に基づき、前記線形移相器をその負荷の均衡がとれるように生成することを特徴とする請求項１に記載の方法。
【請求項３】
前記記憶素子は、フリップフロップである請求項１に記載の方法。
【請求項４】
前記記憶素子は、順次接続されてシフトレジスタを形成する請求項１に記載の方法。
【請求項５】
前記線形移相器の生成工程は、前記各記憶素子の出力が接続される線形論理ゲートの数の履歴を格納する工程を含む請求項１に記載の方法。
【請求項６】
前記線形移相器の生成工程はさらに、前記記憶素子の負荷履歴を分析し、所定値を超える負荷を有する記憶素子を一時的に排除する工程を含む請求項５に記載の方法。
【請求項７】
前記線形移相器の生成工程は、
ａ）前記複数の記憶素子の負荷のヒストグラムを格納し、
ｂ）使用する候補として任意の記憶素子を選択し、
ｃ）前記ヒストグラムをチェックして、前記選択した記憶素子が所定値を超える負荷を有するか否かを判断し、
ｄ）前記選択した記憶素子の負荷が前記所定値を超える場合は、その他の記憶素子が同程度の負荷に至るまで、その記憶素子を一時的に前記線形移相器の生成から排除する
工程を含む請求項１に記載の方法。
【請求項８】
ａ）前記線形論理ゲートを駆動する記憶素子の組み合わせをランダムに選択し、
ｂ）前記線形有限状態機械をシミュレーションし、
ｃ）前記選択された記憶素子の組み合わせが許容可能か否かを、チャネル間の分離基準に基づいてチェックする
工程をさらに含む請求項１に記載の方法。
【請求項９】
前記シミュレーションは、デュアル変換ＬＦＳＭを用いてチャネル間分離をチェックする工程を含む請求項８に記載の方法。
【請求項１０】
前記チャネル間分離は、少なくとも最長走査チェーンの長さに対応する請求項９に記載の方法。
【請求項１１】
前記生成された線形移相器は、その負荷バランスの均衡がとれており、前記負荷バランスの均衡は、前記各記憶素子が、前記線形移相器内のほぼ同数の線形論理ゲートを駆動することに基づく請求項１に記載の方法。
【請求項１２】
対をなす記憶素子を選択して、当該対をなす記憶素子の負荷の均衡をはかり、負荷の均衡がとれた一対の記憶素子で前記線形論理ゲートを駆動する請求項１に記載の方法。
【請求項１３】
前記線形移相器の出力から得られるデータパターンの位相シフトは、前記走査チェーンの最長の長さよりも大きいことを検証する工程をさらに含む請求項１に記載の方法。
【請求項１４】
前記生成された線形移相器の論理合成を行う工程をさらに含む請求項１に記載の方法。
【請求項１５】
前記線形有限状態機械は、変換線形フィードバックシフトレジスタを含む請求項１に記載の方法。
【請求項１６】
前記線形有限状態機械は、タイプＩ型線形フィードバックシフトレジスタまたはタイプII型線形フィードバックシフトレジスタを含む請求項１に記載の方法。
【請求項１７】
線形有限状態機械から記憶素子の組み合わせをランダムに選択して、移相器の線形論理ゲートを駆動し、
前記選択された記憶素子の各組み合わせが許容可能の組み合わせか否かを、チャネル間分離基準に基づいて判断し、
許容可能であれば、その組み合わせを前記移相器に追加する
工程を含む線形依存性を低減した移相器の生成方法。
【請求項１８】
前記判断工程は、前記線形有限状態機械のサイクルのシミュレーションを含む請求項１７に記載の方法。
【請求項１９】
前記シミュレーションは、デュアル変換線形有限状態機械を用いてチャネル間分離をチェックする工程を含む請求項１８に記載の方法。
【請求項２０】
前記チャネル間分離は、少なくとも最長走査チェーンの長さである請求項１９に記載の方法。
【請求項２１】
前記チェック工程は、前記選択された記憶素子の組み合わせについて前記移相器のシミュレーションを行う工程と、前記移相器により生成されたシミュレーション結果のビットパターンと前回生成された許容可能な組み合わせの保護ベクトルとを比較する工程を含む請求項１７に記載の方法。
【請求項２２】
前記選択された記憶素子の組み合わせについて、前記シミュレーション結果のビットパターンが、前回生成された保護ベクトルとマッチする場合に、当該選択された組み合わせを拒否する工程をさらに含む請求項２１に記載の方法。
【請求項２３】
前記記憶素子の組み合わせを選択する工程は、
前記記憶素子の負荷のヒストグラムを作成し、
前記各記憶素子について前記ヒストグラムを読み取り、当該記憶素子が所定の負荷を超えるか否かを判断する
工程をさらに含む請求項１７に記載の方法。
【請求項２４】
前記記憶素子の組み合わせを選択する工程は、
前記記憶素子の負荷のヒストグラムを作成し、
前記各記憶素子に前処理を施して、所定値を超える負荷を有する記憶素子を一時的に排除する
工程をさらに含む請求項１７に記載の方法。
【請求項２５】
一対の記憶素子を選択し、当該一対の記憶素子の組み合わせ同一の前記線形論理ゲートを駆動する頻度に関して負荷バランスをとる工程をさらに含む請求項１７に記載の方法。
【請求項２６】
前記記憶素子の組み合わせを選択した後に、前記移相器上で論理合成を行う工程をさらに含む請求項１７に記載の方法。
【請求項２７】
負荷情報を用いて、前記選択された記憶素子の採用の可否を判断する工程をさらに含む請求項１７に記載の方法。
【請求項２８】
各々が出力を有する記憶素子の集合を含む線形有限状態機械と、
前記記憶素子が均一な負荷バランスを持つように前記記憶素子の出力に接続される複数の線形論理ゲートを有する移相器と、
前記移相器の論理ゲートに接続され、フリップフロップの組み合わせ系列を含む複数の走査チェーンと
を備える線形依存性の少ない集積回路用テスト回路。
【請求項２９】
前記線形論理ゲートは、前記記憶素子が対になって負荷バランスを有するように前記記憶素子の出力に接続される請求項２８に記載のテスト回路。
【請求項３０】
各々が線形移相器を駆動する出力を有する複数の互いに接続された記憶素子を備える線形有限状態機械を生成する手段と、
前記複数の記憶素子が均衡のとれた負荷バランスを有するように前記記憶素子の出力に線形論理ゲートを接続することによって線形移相器を生成する手段と、
前記線形移相器を集積回路のテストに用いる複数の走査チェーンに接続する手段と
を備える線形依存性の少ない集積回路用テスト回路。
【請求項３１】
多段の記憶素子を有する線形有限状態機械を生成し、
前記記憶素子の各段が接続される論理ゲートを有する移相器を生成し、
前記記憶素子と前記論理ゲートとの間で前記有限状態機械のすべての段の負荷バランスをとる
工程を含む集積回路のテスト用移相器の生成方法。
【請求項３２】
前記移相器を用いて複数の出力チャネルを駆動し、
前記記憶素子の対を選択し、当該選択された記憶素子対の負荷の均衡をはかり、負荷均衡のとれた前記記憶素子対により前記移相器内で同一出力チャネルを駆動する
工程をさらに含む請求項３１に記載の方法。
【請求項３３】
前記移相器を用いて複数の出力チャネルを駆動し、前記各出力チャネルが受け取るビットパターンのチャネル分離が所定値以上であることを検証する工程をさらに含む請求項３１に記載の方法。
【請求項３４】
前記移相器を用いて複数の出力チャネルを駆動し、前記出力チャネルの各々が、同一数のＸＯＲタップにより駆動されることを検証する工程をさらに含む請求項３１に記載の方法。
【請求項３５】
前記移相器の出力チャンネルの各々に奇数個のＸＯＲタップが接続されることを検証する工程をさらに含む請求項３１に記載の方法。
【発明の詳細な説明】
【０００１】
技術分野
本発明は、マルチ走査型の線形フィードバックシフトレジスタを用いた擬似ランダムテストベクトルの生成に関し、特に、位相シフトを制御して、並列テストパターン生成器の出力上のテストシーケンス相互の線形依存性を低減する手段および方法に関する。
背景技術
集積回路の集積度が高くなるしたがって、高いフォルトカバレッジを保証しつつ、低いコストでチップ面積のオーバーヘッドを最小にできる効率的なテスト方式への要望が高まっている。しかし、回路構成は複雑になる一方であり、伝統的なテストパラダイムでは、ある種のフォルトモデルにおいて高いフォルトカバレッジを達成するのが困難な状況にある。この困難さにはいくつかの理由がある。第１には、大規模な集積回路では、そのロジック対ピン比が非常に高い。ロジック対ピン比が高いと、チップピンでテストデータ転送の渋滞をきたすが、この比率はなおも増大している現状である。第２に、大規模な回路は大量のテストデータを必要とするが、このような大量のデータを外部のテスト装置に格納しなければならない。第３に、テストデータを大規模回路に適用するには、長いテスト時間を要する。第４に、現存のテスト装置は、大規模回路をその動作速度でテストできる機能を備えていない。
【０００２】
現在、集積回路のテストは、複数の組織的なＤＦＴ（Design for testability：テスト可能な設計）技術を駆使して行われている。これらの技術は、一部またはすべての状態変数（フリップフロップやラッチなどの記憶素子）を直接的に制御し、観察するという一般的なコンセプトに基づいている。このコンセプトによれば、組み合わせフォルトのテストが行われる限り、回路はほぼ組み合わせネットワークとして取り扱われる。もっとも、一般的に使用されているＤＦＴ体系は走査系によるものである。この方法では、米国特許第4,503,537号に開示されるように、テスト期間中は、すべての（あるいはほとんどすべての）記憶素子がひとつ以上のシフトレジスタに接続されている。テスト用に設計された回路は、ノーマルモードとテストモード（走査モード）を有し、ノーマルモードでは、記憶素子はその通常の機能を実行する。走査モードでは、記憶素子は走査セルとなり、走査セルが接続されて、走査チェーンと呼ばれる一連のシフトレジスタを形成する。走査チェーンは、一組のテストパターンを順次テスト回路に移し、回路から取り出し、そのテストパターンに対するテストレスポンスを得る。得られたテストレスポンスは、フォルトフリーのレスポンスと比較され、テスト回路（ＣＵＴ：Circuit Under Test）が適正に動作するか否かが判断される。
【０００３】
走査設計方法論は、テストパターンの自動生成（ＡＴＰＧ：Automatic Test Pattern Generation）が容易であり、シリコンンデバッグ能力にすぐれているため、広く普及し、採用されている。現在のＡＴＰＣソフトウエアツールはきわめて効率的であり、テストセット（テストパターンの集合）を生成して、スタックアット（stuck-at）、遷移、パス遅延フォルト、ブリッジングフォルトなど、いくつかの種類のフォルトモデルでほぼ完全なフォルトカバレッジを保証している。通常、ＡＴＰＧ（自動テストパターン生成）ツールを用いると、回路で起こり得る特定のフォルトをターゲットとし、特定のフォルトを検出するのに、少数の走査セル（たとえば２〜５％）を特定する必要がある。これにより特定されたセルを、決定論的指定セルと呼ぶ。走査チェーン中のその他の走査セルにはランダムな２進値が与えられる（ランダム指定セル）。この方法で、パターンは完全に指定され、さらに別のフォルトも検出できる。テスト結果は、テスタに保存可能である。
【０００４】
図１は、走査チェーンを用いた従来のディジタル回路テストシステム１０を示す。外部の自動テスト装置（ＡＴＥ：Automatic Testing Equipment）またはテスタ１２は、走査モードにおいて、ＣＵＴ（テスト回路）１６内の走査チェーン１８を介して、一連の指定テストパターン２４を順次ＣＵＴ１６に入力する。テスト回路（ＣＵＴ）は次いで、入力されたテストパターンを用いてノーマルモードで動作し、テストパターンに対するレスポンスを走査チェーンに格納する。テスト回路（ＣＵＴ）は再度走査モードになり、レスポンスをテスタ１２に送る。テスタ１２は、テストレスポンスを順次、フォルトフリーの基準レスポンス２０と比較する。しかし大規模回路になると、テストセットのサイズが大きくなりすぎ、また、テスト時間も長くなるので、この方法では対処できなくなる。実際、大規模設計では、論理ゲートごとに１キロビットずつテストデータ量が超過する場合もあると報告されている。この方法にはさらに、高価なメモリ集中型のテスタと、複雑な回路をテストするために長時間を要するという問題もある。
【０００５】
このような時間と容量に関する問題は、図２に示す内蔵型自己テスト（ＢＩＳＴ：Built-in Self-test）のフレームワークである程度解消できる。内蔵型自己テスト（ＢＩＳＴ）では、チップ上にテストパターンを生成するオンチップ（on-chip）回路が設けられ、テストレスポンスを評価し、テスト自体を制御する。たとえば、決定論的テストパターンを使用するかわりに、擬似ランダムパターン生成器（ＰＲＰＧ）２１がテストパターンを生成する。また、マルチ入力サインレジスタ（ＭＩＳＲ：Multiple Input Signature Register）２２は、テストレスポンスからサインを生成して、それを格納する。従来の内蔵型自己テスト（ＢＩＳＴ）では、テストパターンとして擬似ランダムテストパターンを用いた場合、耐ランダムパターンフォルトを扱うテストポイントを選定することを条件として、スタックアットフォルトで９５〜９６％のカバレッジを達成し得る。１０００ゲートにつき、平均して１または２のテストポイントが必要である。内蔵型自己テスト（ＢＩＳＴ）では、出力として検知されサインレジスタに入力されるすべてのレスポンスが既知のものでなければならない。未知の値は、サインの信頼性を損なうので、別のテストロジックで拘束される必要がある。擬似ランダムテストパターンはかなりのパーセンテージでスタックアットフォルトをカバーするとは言え、これらのパターンは、結局は残りの耐ランダムパターンフォルトをターゲットとする決定論的パターンによって補足されなければならない。ＢＩＳＴの補足パターンを格納するのに必要なテスタのメモリだけで、上述した決定論的アプローチに必要とされるメモリの５０％を超えることもしばしばである。ＢＩＳＴにおける別の問題点は、擬似パターンでは、遷移、パス遅延フォルトなど、その他のフォルトを十分に扱うことができないことである。回路の複雑さと上述したＢＩＳＴに特有の制限のせいで、ハード対テストフォルトを完全にカバーするテストパターン集合を提供するのは、不可能でないにしても非常に困難である。
【０００６】
擬似ランダムパターン生成器は、一般に線形フィードバックシフトレジスタ（ＬＦＳＲ）と呼ばれる簡単なハードウエア構造をとる。ＬＦＳＴは、シフトレジスタを構成する鎖状の一連のデータ記憶素子を含む。長さｎの線形フィードバックシフトレジスタ（ＬＦＳＲ）は、特性多項式ｈnｘn ＋ … ＋ ｈ1ｘ ＋ｈ0 で表される。ここでｈｉｘi の項は、このシフトレジスタのｉ番目のフリップフロップであり、ｈｉ＝１ならば、このフリップフロップから取り出されるフィードバックタップがあることになる。所定の多項式にしたがって適正なタップ接続が確立されているならば、各段の結合（加算単位２の）出力が、ＬＦＳＲの初段にフィードバックされる。このような構成をタイプＩ型ＬＦＳＲあるいはフィボナッチ生成器と称する。別の構成として、ＬＦＳＲセルの間にＸＯＲゲートを有するシフトレジスタがある。これをタイプII型ＬＦＳＲあるいはガロア（Galois）の真の除数と称する。この構成の顕著な特徴として、ＬＦＳＲの最終段の出力が、使用する特性多項式で示される段にフィードバックされる。ｎビットのＬＦＳＲに考えられ得るすべて（２n−１個）の非ゼロ状態を通るせる多項式を、原始特性多項式と呼ぶ。これに対応するＬＦＳＲを最大長ＬＦＳＲと称し、出力結果のシーケンスは最大長シーケンスあるいはｍ−シーケンスと呼ばれる。
【０００７】
図３は、マルチ走査チェーン２６に並列にテストパターンを供給するテスト生成器として用いられるＬＦＳＲ２４を示す。この設計の問題点は、ＬＦＳＲが有する構造的な依存性のせいで、満足のゆくフォルトカバレッジが得られないことである。実際、走査パス（経路）がＬＦＳＲの隣接ビットから直接延びる場合、その近接性のために、近隣の走査チェーンが相関度の高いテストパターンを含むことになる。この現象では、テスト回路（ＣＵＴ）から見たパターンが擬似ランダムにならないので、フォルトカバレッジに悪影響を与える。
【０００８】
走査チェーン間の相関をさらに低減するために、ＬＦＳＲ２４と走査チェーンの間に移相器２８が挿入される構成も知られている（図４参照）。一般的な移相器２８は、複数の走査パス間での同一データのバージョンシフトを回避するために採用される排他的ＯＲ（ＸＯＲ）ネットワークで構成される。各走査チェーンはＬＦＳＲ各段の出力の一次結合に対応する回路素子によって駆動される。この回路素子は、最大長シーケンス（ｍ−シーケンス）の「シフトアンドアッド（shift-and-add）」特性を用いることによって、他のシーケンスと間隔をおいたテストシーケンスを生成する。シフトアンドアッド特性によれば、最大長シーケンスと、その循環シフト（桁送り）との合計は、この最大長シーケンスの別の循環シフトになる。実際は、移相回路は異なる原理に従って設計される。コンスタント移相器においては、各走査パスのチャネル間の変位は、実際の合成プロセスの前に指定される。コンスタンと移相器は、ＬＦＳＲの振る舞いを記述する遷移マトリクスを使用して、連続シフトを実現するＬＦＳＲ出力を決定する。この方法の基本的な欠点は、マトリクス演算を要することと、演算結果の移相器が複雑であることである。この方法で得られる移相器は、因数分解の後でさえ多大な数のＸＯＲゲートと過大な伝達遅延を有する。ＬＦＳＲ上のひとつのタップ３０に接続されるＸＯＲゲートの数が多くなると、伝達遅延が大きくなるのは明白である。このような過剰な負荷によりキャパシタンスが増大し、信号伝達が遅くなる。ＬＦＳＲのその他のタップ（たとえばタップ３２）の出力には、単一のＸＯＲゲートだけが接続されている。ＬＦＳＲのタップ間でその負荷が一致しないと、走査チェーンに格納されるパターン間での線形依存性が増大する。
【０００９】
移相器設計プロセスに必要とされるハードウエアの量を制御する別の方法が、米国特許第4,959,832号に開示されている。この方法は、各チャネルの一次結合を求めるよりは、あらかじめ特定された移相器構造を用いて処理を開始し、結果としてのチャネルの移相を決定する。したがって、チャネル間の分離は可変になり、実際の値を求めるのに複雑な計算が必要になる。さらに、この米国特許に示される方法では、出力チャネルの数がＬＦＳＲの接続段の数に制限される。可変移相器を設計するための方法は本来的に特定目的のためのものであり、多数の走査チェーンを有する回路には非実用的である。
【００１０】
最近、２つの論文に新たな方法が掲載された。“Design of phases shifter for BIST application（ＢＩＳＴ適用の移相器設計）", Proc. VLSI Test Symposium, 1998 と、“Automated Synthesis of Large Phase Shifters for Built-in Self-Test（内蔵型自己テストのための大型移相器の自動合成）", Proc. ITC, 1998 である。これらの論文はＬＦＳＲの双対性（duality）のコンセプトを開示している。ＬＦＳＲの双対性によれば、タイプＩ型ＬＦＳＲが与えられると、最右端のタップを除くすべてのフィードバックタップの方向を反転することによって、デュアルＬＦＳＲ（すなわちタイプII型ＬＦＳＲ）が得られる。同様に、タイプII型ＬＦＳＲが与えられると、最右端のタップを除くすべてのフィードバックタップを反転することによってタイプＩ型のデュアルＬＦＳＲが導かれる。この方法は、以下のようにして、デュアルＬＦＳＲの論理状態と所望の移相器のアーキテクチャとを関連付ける。すなわち、デュアルＬＦＳＲを適切に初期化した後、連続するｋ回のステップでその論理シミュレーションを行う。デュアルＬＦＳＲの結果内容（すなわち“１”のロケーション）は、ｋビットシフトされたシーケンスを得るための移相器構造に含まれるべき位置を示している。時間効率のよいやり方で、走査チェーン間の最小位相変移を保証するとともに、実質的に出力チャネルごとにひとつの２ウェイＸＯＲゲート面積を低減した遅延の小さい大型の高速移相器の合成が可能になることが示されている。しかし、これらの論文に記載された方法は、負荷バランスの問題を有している。特に、ＬＦＳＲタップ間に存在する負荷のばらつき（不一致）は伝達遅延を増大し、走査チェーンに格納されるパターン間の線形依存性を増大する。
【００１１】
高集積化と、よりフレキシブルなＢＩＳＴ（内蔵型自己テスト）自動化ツールへの傾向が続く中で、時間効率のよい移相器合成処理と、これに対応する高速論理合成ルーチンへの要望は高まる一方である。このような技術は、多数の走査チェーンを用いる広範な種類の大型ＬＦＳＲを取り扱うことができ、所定の移相器ネットワークでコスト効率のよい処理ができるものでなければならない。最近の回路設計では、１００万を越える数のゲートを含むものもめずらしくない。このような大規模設計でフリップフロップの数は、数十万個におよぶ場合もある。たとえば、１００万個のゲート設計で約５万個のフリップフロップがあり、テスト時間を短縮するために、走査チェーンごとのフリップフロップの数を２５０に制限しているとすると、２００の走査チェーンを有する回路が得られる。綿密に設計された移相器を用いて構造依存性と線形依存性が排除できる場合に限り、これらの２００の走査チェーンを駆動するのに６４ビット幅のＬＦＳＲで間に合う。高いフォルトカバレッジと合理的なテスト時間を確保するには、このような走査チェーン間の依存性をなくすことが不可欠である。このことから、擬似ランダムＢＩＳＴ体系の成功の可否は、移相器回路の設計の適切さにかかっていると言える。
発明の概要
本発明は、線形有限状態機械（ＬＦＳＭ）と移相器との組み合わせにより、走査チェーンに相互の依存性を低減したテストパターンをロードする。線形有限状態機械（ＬＦＳＭ）は、多段の記憶素子（ＬＦＳＭセル）を含む。記憶素子は、通常は直列に接続され、中間フィードバックを有する場合が多い。線形有限状態機械の各段の出力は、移相器の線形論理ゲート（ＸＯＲゲート、ＸＮＯＲゲートなど）に接続される。移相器の出力チャネルは、テストパターンがロードされた走査チェーンに接続され、集積回路内のフォルトをテストする。
【００１２】
ひとつの側面では、線形有限状態機械は十分に均衡の取れた負荷バランスを有しており、線形有限状態機械の各セルの出力（すなわちタップ）は、移相器内のほぼ同数の線形論理ゲートを均等に駆動する。負荷バランスがよいので、複数の線形論理ゲートの各々が、線形有限状態機械の個別のセルからその入力を受け取ることができる。移相器を駆動する線形有限状態機械のセル出力は、０とｎ−１の区間で整数の一様分布を生成する擬似乱数生成器によって選択される。ここでｎは線形有限状態機械のサイズである。移相器の生成プロセスは、ＬＦＳＭセルのヒストグラムによって導かれる。ＬＦＳＭセルの各々について、ヒストグラムの対応するエントリが、どのくらいの頻度でこのセルが使用されるかを記録する。セルが使用された現在の数が所定値を超えたときは、残りのセルが同じ回数使用されるまで、この特定のセルは乱数生成プロセスから一時的にはずされる。この結果、各ＬＦＳＭセルはほぼ同じ数の移相器ゲートを駆動することになる。
【００１３】
別の側面では、検証プロセスに関連し、新たに生成されたタップの一次結合から生成されたテストパターン（テストシーケンス）は、既存のタップの組み合わせにより生成されたテストパターン（テストシーケンス）と重複しないことを検証する。また、与えられたタップの組み合わせがチャネル間分離基準を満たすか否かをチェックする。つまり、生成されたパターンの各々は、走査チェーンのその他のパターンから、少なくとも所定のビット数だけシフトされていなければならない。チャネル間の分離長は、適用の如何によって異なるが、たとえば、少なくとも最長走査チェーンの長さに対応する。
【００１４】
さらに別の側面では、双対性のコンセプトを用いて、線形有限状態機械の論理状態と、各出力に接続される入力の間隔を十分に確保する回路アーキテクチャとを関連付ける。この構成では、デュアルＬＦＳＭの簡単な論理シミュレーションを行うだけで、今回のシーケンスが、移相器ネットワークにすでに含まれているタップ一次結合により生成されたシーケンスと重複しないことを、所定期間で確認する。
【００１５】
本発明では、最大長シーケンスを生成する特性多項式の性質を示す線形有限状態機械を用いて実施することができる。その他の特徴、効果については、図面を参照して以下で説明する。
詳細な説明
擬似ランダムシーケンスを生成するのに、線形フィードバックシフトレジスタ（ＬＦＳＲ）やセルラオートマタ（ＣＡ:Cellular Automata）といった線形有限状態機械（ＬＦＳＭ）がしばしば用いられる。線形有限状態機械（ＬＦＳＭ）の一例として、ｎ次の特性原始多項式ｈ(ｘ)＝ｈnｘn ＋ … ＋ ｈ1ｘ ＋ｈ0 を演算する回路が挙げられる。この回路では、移相器の論理合成を行うために、生成される各シーケンスが、その他のすべてのシーケンスから少なくとも所定のビット数だけシフトするように、ＬＦＳＭセル出力の一次結合の集合を見つけなければならない。本明細書では、特定の実施例（たとえば変換ＬＦＳＲなど）を用いて、線形有限状態機械ＬＳＦＭについて説明するが、その他の適用も可能であることは言うまでもない。変換ＬＦＳＲ（ｔ−ＬＦＳＲ）は、図５の原始多項式ｘ32 ＋ｘ18 ＋ｘ14 ＋ｘ9 ＋１に示されるように、異なる段で開始、終了するフィードバック接続を有するリング構造の記憶素子で構成される。これはタイプＩ型ＬＦＳＲとも、タイプII型ＬＦＳＴとも異なる。本明細書では、図５に示す構成の線形フィードバックシフトレジスタを一般化して、ｔ−ＬＦＳＴと称する。
【００１６】
本明細書に記載される移相器の合成方法は、ｔ−ＬＦＳＲセルの組み合わせを、各セルの出力が加算されたときに一連の出力チャネル上に最大長のシーケンス（ｍ−シーケンス）が生成されるように、高速で選択することを目的とする。このとき、シーケンス間の相互分離が所定値以上となることを保証する。ここで、ｔ−ＬＦＳＲの出力をタップと称する。タップ集合(組み合わせ列)を順次生成し、生成された組み合わせが許容可能か否かを、チャネル間分離基準に基づいて判断する。
【００１７】
図１０は、移相器の生成方法を示すフローチャートである。処理ブロック４０で、複数のセル（フリップフロップなどの記憶素子）を有する線形有限状態機械（ＬＦＳＭ）を生成する。処理ブロック４２で、各セルの負荷情報を格納する。負荷情報はたとえば各セルの使用頻度である。このような負荷情報を移相器生成の過程で使用する。セルの出力は、通常、移相器の線形論理ゲートに接続されるが、一定のセル（記憶素子）だけが頻繁に使用され、その出力に負荷が偏ると、キャパシタンス(容量)が増大して、信号伝達が遅くなる。結果として、回路全体の動作速度が落ちる。また、ファンアウト（論理出力数）が増えると、これらを収容するために容量の大きな記憶素子が必要になり、装置の簡易化、小型化、コスト面で問題となる。そこで、負荷情報を記憶しておき、移相器生成の過程でこの負荷情報を分析して、負荷の均衡を図る。処理ブロック４４で、負荷情報を用いて移相器を生成する。負荷情報の用いる例として、たとえば、全体にわたって記憶素子を均等に使用する。記憶素子全体にわたって負荷を均等に分散させることにより、回路全体の動作速度が向上する。
【００１８】
図１１は、負荷バランスのとれた移相器を生成する詳細な構成を示すフローチャートである。処理ブロック４８で、線形有限状態機械（ＬＦＳＭ）から記憶素子をランダムに選択する。選択された記憶素子の集合（組み合わせ）は、移相器のひとつの線形論理ゲートを駆動する候補となる。処理ブロック５０で、ランダムに選択された記憶素子の組み合わせの各々について、チャネル間分離が許容範囲にあるか否かを判断する。チャネル間の分離を求めるには、ＬＦＳＭでシミュレーションを行い、各シーケンスがその他のすべてのシーケンスから少なくとも所定のビット数だけシフトしているか否かを確認する。このシミュレーションについては、以下でさらに詳述する。次に、処理ブロック５２で、チャネル間分離が十分であるとして許容された場合は、その記憶素子の組み合わせを、許容組み合わせリストに追加する。
【００１９】
図１２および１３は、記憶素子のランダムな生成について、より詳細な処理フローを示す。図１２は、負荷の均衡を図るために記憶素子に対して施される前処理の処理フローである。この前処理により、所定値を超える負荷を有する記憶素子を、使用可能な記憶素子の集合から一時的に排除する。具体的には、処理ブロック５６で、使用可能な記憶素子を示す集合（たとえば、テーブル、アレイ、リストなど）を生成する。この集合に含まれる線形有限状態機械の各記憶素子が、移相器の線形論理ゲートを駆動する素子の候補となる。集合内の各記憶素子は分析され、現在の負荷がどの程度かチェックされる。すなわち、処理ブロック５８で、現在分析中の記憶素子の負荷を検出する。記憶素子の負荷は、移相器の生成プロセスにわたって変化するので、各記憶素子の負荷量の変化を追跡する記憶機構が必要である。実施形態では、記憶素子の負荷の追跡にヒストグラムを用いるが、もちろんこの例に限定されない。判断ブロック６０で、現在処理中の記憶素子の負荷が所定値を超えるか否かを判断する。負荷が所定値を超えていれば（肯定判断）、処理ブロック６２に進み、その記憶素子を使用可能な記憶素子の集合から一時的に省く。負荷が所定値以下であれば（否定判断）、その記憶素子は使用可能な記憶素子集合に残しておく。判断ブロック６４で、生成された集合に含まれるすべての記憶素子について、上述の処理が完了したかどうかを判断する。処理が完了していない場合は、矢印６６で示すように、処理ブロック５８に戻り、上述した工程を繰り返す。すべての記憶素子について処理が完了したら（ブロック６４で肯定判断）、図１３の処理へ進む。
【００２０】
図１３は、図１２の前処理に引き続いて行われる、記憶素子のランダム選択工程を示す。処理ブロック７０で、所定値以下の負荷を有する記憶素子集合の中から、任意の記憶素子をランダムに選択する。このランダム選択は、公知のアルゴリズムを用いて行なう。処理ブロック７２で、後処理のために、選択した記憶素子を格納する。判断ブロック７４で、所定の数の記憶素子が選択されたか否かを判断する。所定数に達しない場合は、矢印７８で示すように、ランダム選択を繰り返す。所望の数の記憶素子がランダム選択されたなら、ブロック７６でこのルーチンを終了する。
【００２１】
以下に示すアルゴリズム１は、前処理および記憶素子の選択工程を詳細に示すものである。一例として、線形有限状態機械をｔ−ＬＦＳＲ（変換線形フィードバックシフトレジスタ）とする。アルゴリズム１が用いる補助ベクトルとしての“Taps"および“Position”は、それぞれ必要とされる数のＸＯＲタップおよびｔ−ＬＦＳＲのサイズに対応し、これらに等しいディメンションを有する。この前提に基づき、アルゴリズム１を実行することによって、所望の組み合わせが返ってくる。これらのベクトルを用いて、一連のＸＯＰタップ（出力)を格納し、移相器の生成プロセスを制御する。
【００２２】
【表１】
0003699397.tif 000002
アルゴリズム１は２つの主要部分で構成される。まずベクトル“Position”を初期化することから始まる。この初期化ベクトルは、アルゴリズムの全実行過程を通して、未選択のすべて段のｔ−ＬＦＳＲに対して同一である。これらの数は、すでに選択されＸＯＲタップとして使用されているベクトル位置のエントリに順次コピーされる。各エントリPosition[i]は、ｉ（ｉ＝０，１，…，ｎ−１）に設定される。ここでｎは与えられたｔ−ＬＦＳＲのサイズである。次いで、ループ内でベクトル“Position”にさらに前処理を施す。すなわち、一部のｔ−ＬＦＳＲ段の出力上でファンアウト（論理出力数）が大きくなるのを避けるために、負荷ヒストグラムに基づいて生成プロセスを進める。各ｔ−ＬＦＳＲセルについて、対応するヒストグラムのエントリは、そのセルがこれまでどれだけの頻度で使用されてきたかを記録するものである。セルの現在の値が所定の限界値を超える場合、その他のセルの使用頻度が同程度に達するまで、このセルを以降の処理から一時的にはずす。このようにして、すべてのセルが実質的に同じ数のＸＯＲタップを駆動することを保証する。
【００２３】
特定のセルを排除する方法は、アルゴリズム１の後半で、ＸＯＲタップの生成を実際に実行する段階に現れている。関数random (ａ，ｂ）は、ａからｂの範囲にわたって均一に分布する擬似ランダム整数のジェネレータである。ｒを必要なＸＯＲタップの数とすると、アルゴリズムは、ｎ個の素子集合の中からランダムな順序でｒ個の素子シーケンスを生成することによって、ベクトルタップを満たしてゆく。アルゴリズム１のこの部分は、ルーチンが呼び出される都度、正確にｒ工程行われてから、生成プロセスが終了する。実際、一連のＸＯＲタップは、関数random から直接導かれるというよりは、ベクトル“Position”を介して生成される。また、各生成工程で、関数random が作用する領域は１ずつ低減する。これによって、同じ擬似数が生成されたとしても、その擬似数で示されるエントリは前回と異なる内容を有することが確保される。同様の方法が初期化段階でも用いられ、これによって特定のｔ−ＬＦＳＲセルが酷使されるのを防止する。
【００２４】
この例では、変数“limit”は初期状態では「１」であり、“Position”ベクトルは上述した手順で初期化される。上述のコードを実行することによって、ヒストグラムの対応するエントリを変数limitの現在の値よりも小さいものだけに限定し、次回のＸＯＲタップの組み合わせとなる候補位置をしぼることができる。次に、候補として残された段のｔ−ＬＦＳＲの数を、ＸＯＲタップの必要数と比較する。新たな組み合わせが生成されない場合は、現在“limit”値を引き上げてプロセス全体を繰り返す。また、ＸＯＲタップの組み合わせによっては、チャネル間分離基準に基づいて拒否されることもあり得るので、セルが使用可能であったとしても、生成プロセスを完了する条件を満たさない場合がある。このため、拒否された数を記録しておき、失敗（拒否）が一定数以上連続して続く場合は、同じく変数limitを引き上げる必要がある。
【００２５】
ヒストグラムの例として、ｔ−ＬＦＳＲセルの負荷を表す１次元ヒストグラムおよび２次元ヒストグラムを以下の表に示す。表２および表３は、それぞれ出力数１００の移相器を駆動する２４ビットおよび３２ビットのｔ−ＬＦＳＲ上でアルゴリズム１を走らせて得られたヒストグラムである。双方の移相器で、１つのチャネルは７段のｔ−ＬＦＳＲの一次結合によって定義される。表２（２４ビット）および表２（３２ビット）において、論理合成前の単位セル当たりの期待負荷は（駆動ＸＯＲゲート数）は、それぞれ３０および２２である（表２および３の中段参照）。また、ｔ−ＬＦＳＲセルの各セル対が、どれだけの頻度で移相器の同一チャネルを駆動しているかを測定したところ、直交性があると仮定して、２４ビットと３２ビットで、それぞれ７．６１と、４．２３であった（表４および表５参照）。この生成されたヒストグラムの結果から、生成された数が理論値に非常に近く、すべてのＬＦＳＲが高度にバランスよく使用されていることがわかる。ＸＯＲタップの生成プロセスに続いて、論理合成を行うことにより、得られたＸＯＲタップは因数分解の対象となる。表２および３の下段は、この論理合成後のジェネレータ（生成プログラム）の負荷段数を示している。表２および３から明らかなように、この論理合成処理により実際に使用されるジェネレータの一連のステージが大幅に低減できることがわかる。
【００２６】
【表２】
0003699397.tif 000003
【００２７】
【表３】
0003699397.tif 000004
【００２８】
【表４】
0003699397.tif 000005
【００２９】
【表５】
0003699397.tif 000006
このように、線形有限状態機械（ＬＦＳＭ）の各記憶素子に渡って負荷の均衡がとれているだけではなく、同一の線形論理ゲートを駆動する記憶素子の対（ペア）においても、負荷バランスがとれていることがわかる。たとえば、表４の例では、０と１のＸＯＲタップ対は７回使用されている。これは、移相器内の７つの線形論理ゲートが、線形有限状態機械の記憶素子０と記憶素子１の組み合わせによって駆動されたことを意味する。このように、記憶素子の各対がほぼ同数の線形論理ゲートを駆動する。もちろん負荷バランスおよび記憶素子対に多少のばらつきはあるが、従来の設計に比較して、格段の効果を示している。
【００３０】
さて、最小チャネル分離幅ｄにおいて、新たに生成されたＸＯＲタップの一次結合により生成されるシーケンスが、既存のチャネルで生成されたシーケンスと重複しないことを確認する検証工程を実施するのが望ましい。検証工程を実施するために、双対性の概念を一般化した新たな方法を導入する。
【００３１】
図５に示すｔ−ＬＦＳＲ本来の構造があるとする。その二元的な形態としてのデュアルｔ−ＬＦＳＲは、図６に示すように、すべてのフィードバック接続ラインの方向を反転することによって導き出せる。すなわち、デュアルｔ−ＬＦＳＲでは、もとの回路のＸＯＲゲートの位置からフィードバックラインが延び、もとの回路でフィードバックタップを駆動したフリップフロップをフィードバック先として、そのフリップフロップの出力上にＸＯＲゲートを配置した構成をとる。このようにして新たに得られたデュアルｔ−ＬＦＳＲは、対応の遷移マトリクスＤによって特徴付けられる。もとのｔ−ＬＦＳＲの遷移行列Ｍと、デュアルｔ−ＬＦＳＲの遷移行列Ｄとの関係を詳細に調べると、これら２つの変換線形フィードバックシフトレジスタの間に、
ＭT ＝Ｄ-１
という基本的な関係があることがわかる。ここでＭT はＭの転置行列、Ｄ-１はＤの逆行列である。上記の関係が真であるならば、ＭT （すなわちＤ-１）とＤとの積は、恒等行列Ｉに等しくなければならない。転置行列ＭT が、主対角線より下の対角線沿いと、フィードバックレジスタのリング構造を保証するためにコーナーのエントリに「１」を有すること、および行列Ｄが主対角線より上の対角線沿いと、ループを閉じるためにコーナーのエントリに「１」を有することは、容易に検証できる。もっぱら行列ＤＤ-１の主対角線上に位置する「１」に寄与するだけのエントリがある。このベクトル行列の残りのエントリを計算すると、どの場合をとっても結果はゼロになる。これを説明するために、行列ＤＤ-１の行ｘと列ｙにあるエントリを考える。このエントリの計算で非ゼロの結果を得るためには、行ｘおよび列ｙの対応する位置にそれぞれ「１」を有する必要がある。一般性が失われないことを前提として、行ｘにおける非ゼロのエントリが２つの連続するフリップフロップ（たとえばｂ−１とｂ）の間の接続を表わすとすると、そのエントリは主対角線より下の対角線にある。これに整合する列ｙの非ゼロエントリは、フリップフロップｂ−１と別のフリップフロップｃとの間の接続に対応するはずである。この後者の接続は、もとの回路の中に対応する接続、すなわちフリップフロップｃ−１とｂとの間のフィードバック接続を有する。もとの回路におけるこのフィードバック接続は、行ｘの位置ｃ−１における「１」で表される。しかし、この「１」は、連続するフリップフロップｃ−１とｃとの間の接続に対応する列ｙのエントリによって補償される。つまり、２つの積算結果を足し合わせると、ゼロになる。
【００３２】
所定のチャネル間隔ｑにおいて、ベクトルＭq ｓjT が求まれば、従来の線形フィードバックシフトレジスタ（ＬＦＳＲ）のｊ番目のチャネルで生成された最大長シーケンス（ｍ−シーケンス）だけシフトダウンする移相器を見つけることは可能であるとわかっている。ここでｓjT は、ｊ番目の位置における単一のセレクションベクトルの転置行列である。
【００３３】
結果としてのベクトルは、ｑビットだけシフトされた所望の最大長シーケンス（ｍ-シーケンス）を得るために加算されるべき各位置に「１」を有することになる。２つのシフトレジスタの遷移行列がＭT ＝Ｄ-１の関係をみたすならば、次式が成立することが知られている。
【００３４】
[Ｍq]Ｔ＝Ｄm
ここでｍ＝２n −１−ｑである。この式から、ｔ−ＬＦＳＲの双対性の顕著な特性が導かれる。すなわち、行列Ｍをｑ回乗算した結果の第１カラム（列）の内容は、行列Ｄを（２n −１−ｑ）回乗算した結果の第１ロー（行）の内容に一致する。Ｄのべき乗行列の第１ローは（その初期値を１０…０として）、デュアルｔ−ＬＦＳＲを（２n −１−ｑ）クロックサイクル適用した状態であるとみなされるので、上述した公知の行列演算を、デュアルｔ−ＬＦＳＲのシンプルな論理シミュレーションに置き換えることができる。実際、デュアルｔ−ＬＦＳＲの論理シミュレーションは、わずかｑサイクル行うだけで完了する。シミュレーション後のデュアルｔ−ＬＦＳＲの状態は、もとのｔ−ＬＦＳＲのどの出力をＸＯＲ演算して、基準ｍ-シーケンス（すなわちｔ−ＬＦＳＲの所定の段から生成される最大長シーケンス）をチャネル間分離幅ｑだけシフトアップする所定のビットストリングを生成するか定義するものである。
【００３５】
一例として、図７Ａに示すｔ−ＬＦＳＲを考える。このｔ−ＬＦＳＲは、ｍ−シーケンス保存変換を何度も適用することによって得られたものである。適用結果であるｔ−ＬＦＳＲは、変換前と同様に原始特性多項式ｈ(ｘ)＝ｘ8 ＋ｘ6 ＋ｘ5 ＋ｘ ＋１ を実行するが、ＸＯＲゲート数、内部ファンアウト、および伝達遅延を低減するために最適化されている。以下の表６の第２列は、このｔ−ＬＦＳＲの状態を示し、第４列は図７Ｂに示すデュアルｔ−ＬＦＳＲの一連の状態を示している。また、表６の第３列は、デュアルｔ−ＬＦＳＲの状態により示されるもとのｔ−ＬＦＳＲの各出力を足し算することによって得られるｍ-シーケンス（最大長シーケンス）をリストしている。第３列のヘッダは結果としての位相シフトを示す。たとえば表６の行「１」で状態０１１０００００が生じていることから、この行で１ビットシフトしたｍ-シーケンスを得るには関数
【外１】
0003699397.tif 000007
を演算しなければならないことがわかる。ここでＳi はもとの（オリジナル）ｔ−ＬＦＳＲの第ｉ段である。同様に行「７」で生じる状態０００１００１１は、第４段、７段、８段を加算
【外２】
0003699397.tif 000008
すると、７ビットシフトしたｍ-シーケンスが得られることを示している。表にリストしたすべてのシーケンスが、実際にオリジナルｔ−ＬＦＳＲの最左端のビットに見られるｍ−シーケンスに対して、（ヘッダに示す）所望の位相シフトでシフトされていることが容易に検証される。
【００３６】
【表６】
0003699397.tif 000009
上述したシミュレーションベースの方法のみでも移相器の合成を行えるが、ＸＯＲタップのカウントを低く維持しようとすると、この方法では時間効率があまりよくない。大型のｔ−ＬＦＳＲによって生成されたｍ-シーケンスの中で、「１」の数が少ない（より単純に実現される）ｔ−ＬＦＳＲはきわめて稀だからである。このため、必要とされる最小分離幅を確保する所定数の組み合わせを許容する前に、非常に多くの状態を走査しなければならない。しかしながら、この方法は検証を行うのに利用することができる。すでに得られたシーケンスと新たに生成されたＸＯＲタップによるシーケンスとの間に重複がないということは、新たなＸＯＲタップを表わすバイナリコンビネーションβから少なくとも次のｄステップまでの間は、すでに移相器ネットワークに組み込まれたＸＯＲタップの一次結合によって生成される他のシーケンスの開始はないことを意味する。換言すれば、デュアルｔ−ＬＦＳＲの状態軌跡上で、少なくとも状態βに先立つ連続するｄ個の状態においては、すでに選択された組み合わせは発生しない。
【００３７】
前回の生成工程で許容可能として受け入れられたＸＯＲタップの組み合わせは、２つの２進ベクトル（保護ベクトル（guard combinations）と称する）で表わされる。２つの２進ベクトルは、実際のＸＯＲタップの一次結合（組み合わせ）と、所定のデュアルｔ−ＬＦＳＲの状態軌跡で前回のベクトルからｄステップ隔てられた位置のベクトルである。候補のＸＯＲタップから始まり、デュアルｔ−ＬＦＳＲの論理シミュレーションで新たな組み合わせが得られる都度、すでに許容されたＸＯＲタップを表わす保護ベクトルの辞書を検索して、新たに生成された組み合わせと同じ要素がすでに存在するか否かを調べる。同じ要素が存在する場合は、現在の候補によって生成される最大長シーケンス（ｍ−シーケンス）と、移相器内にすでに存在する他のシーケンスとが重複してしまうので、この候補は拒否される。なお、ＸＯＲタップの組み合わせ（シーケンス）が拒否されないときは、一定の検証工程の最後に、この候補のための保護ベクトルが決定される。
【００３８】
図１４は、移相器を生成するための処理フロー全体を示す詳細なフローチャートである。処理ブロック８０で、（たとえば図１２および１３を参照して説明した方法を用いて）所定の負荷の上限を超えない記憶素子の組み合わせを生成する。処理ブロック８２で、生成した記憶素子を用いて線形有限状態機械（ＬＦＳＭ）を初期化する。判断ブロック８４で、ＬＦＳＭの状態が先に生成された保護ベクトルと同じかどうかを判断する。同じであれば（ブロック８４で肯定判定）、処理ブロック８６へ進み、この記憶素子の組み合わせを拒否し、処理ブロック８０へ戻って同様の工程を繰り返す。同じ保護ベクトルがない場合は(ブロック８４で否定判定)、処理ブロック８８へ進み、ＬＦＳＭの次の状態をシミュレーションする。ＬＦＳＭをクロックしたあと、ブロック９０でチャネル間分離が所定分離幅に達しているかどうか判断する。この判断は、たとえば、結果として得られたシーケンスが、他のすべてのシーケンスから少なくとも所定のビット数だけシフトしているかどうかを確認することによって行う。もちろん、チャネル分離が十分か否かの判断は、種々の異なる基準を用いても実行できる。たとえば、チャネル分離が、少なくとも最長の走査チェーンの長さに達していれば、十分とするなどである。所定の分離幅がある場合（ブロック９０で肯定判定）は、処理ブロック９２で保護ベクトルの状態を更新し、処理ブロック９４でこの記憶素子の組み合わせを移相器の暫定バージョンに追加する。さらに処理ブロック９６で、処理を完了したチャネルの数をインクリメントする。判断ブロック９８で、決められた数のすべてのチャネルについて処理が完了したかどうかを判断する。処理が完了していない場合は、矢印１００で示すように、ブロック８０へ戻り、上述した工程を繰り返す。すべてのチャネルの処理を終えたならば、このルーチンを出る（ブロック１０２）。これで移相器が生成される。生成された移相器のサイズを低減するために、論理合成をさらに行ってもよい。負荷バランスのとれた移相器は、論理合成後であっても、その負荷の均衡を依然として保持する。
【００３９】
下記のアルゴリズム２は、ｔ−ＬＦＳＲの擬似コードの一例を示す。ベクトルが保護ベクトル（guard combinations）のリストにある場合は、生成された関数（ベクトル）は論理真（true）を返すと仮定する。
【表７】
0003699397.tif 000010
アルゴリズム２のコードは、３つの部分から構成される。ループの外側の各ステップにおいて、まず新たなＸＯＲタップの組み合わせを生成し、この組み合わせが許容可能かどうかをチェックする。許容可能であれば、この組み合わせと、対応する保護ベクトル（guard combination）をリストに追加し、生成されたチャネルの数を更新する。実際の妥当性検査は、ループの中で実行される。デュアルｔ−ＬＦＳＲの初期化の後、まず、その現在の状態が保護ベクトルのリストにあるかどうかをチェックし、デュアルｔ−ＬＦＳＲの次の状態を決定する。カウンタ値ｉが必要とされるチャネル間分離に達すれば、ループを終了する。変数（ＸＯＲタップの組み合わせ）が拒否された場合は、すぐに次のＸＯＲタップの生成にかかる。一例として、原始多項式ｘ16＋ｘ10＋ｘ7＋ｘ4＋１を演算するｔ−ＬＦＳＲによって駆動される１９出力の移相器を合成するのにアルゴリズム２を適用した場合、図８に示す構成が得られる。この合成プロセスは、各出力チャネルは３つのＸＯＲタップにより駆動され、最小チャネル間分離を１００として実行される。
【００４０】
上述した手法で生成された移相器は、特に移相器出力上に生成されるシーケンスの線形依存性を低減することを意図する。線形依存性の影響は、連続する走査チェーン間のチャネル分離の関数として線形依存性の発生確率によって評価することができる。チャネル変位の変化量と走査長を一定にして、所望のシーケンスを得る可能性（確率）を最大にするのに必要とされるチャネル間分離が決定される。これについて以下の例で説明する。以下の例では、数個のｔ−ＬＦＳＲで駆動されるある種の移相器で実行されるモンテカルロ試行を考慮する。
【００４１】
正確な評価を得るために、シミュレーションは、特定の位置で表されるテストキューブが得られる確率を査定することを主目的とする。このような確率の評価は、ｔ−ＬＦＳＲに適切な初期（シード）値をロードし、走査セルが所望のテストデータで満たされるまでこのｔ−ＬＦＳＲを駆動することによって得られる。ここで用いられる評価方法は、ガロア・フィールド（Galois Field）のモジュロ２の一次方程式の解法システムに基づく。ｔ−ＬＦＳＲの構成が与えられると、すべての走査セルにおいて、シード変数の一次結合である記号式（symbolic expression）を形成することができる。まず、ｎ個のシード変数をｎビットｔ−ＬＦＳＲにロードする。次に、各ステップ（あるいは各クロックサイクル）で、シード変数の一次結合を、移相器出力によって駆動される走査チェーンの連続するセルに関連付ける。採用するｔ−ＬＦＳＲのフィードバックネットワークと移相器によって、式の形態が決まる。記号式が決まると、与えられたテストキューブのための方程式が体系化される。方程式を得るには、テストキューブの特定の位置に対応する記号式を選択して左辺とし、右辺でこれらの特定位置の値を各記号式に代入する。このような方程式体系は、高速ビット式演算（fast bit-wise operations）を利用してガウス−ジョーダンの消去法を用いると効果的に解くことができる。
【００４２】
テストキューブで特定される位置に対応する一次方程式のシステムが解を有するならば、与えられたテストキューブの初期値が存在する。解の存在は、方程式の線形依存性の確率群によって適格とされ、したがって、これらの確率はｔ−ＬＦＳＲの主要評価として採用され、必要なテストシーケンスを生成する。リニアに依存する方程式がジェネレータの出力空間全体にわたって均等に振り分けられると仮定すると、種々のジェネレータサイズと特定された位置の数において、初期値を見つける確率は当業界において周知の方法で導かれる。これれらの確率は基準点として用いられる。
【００４３】
各々がｃ個のフリップフロップから成るｗ個の走査チェーンを生成するｎビットｔ−ＬＦＳＲにおいて、モンテカルロ法を試行した。ＸＯＲタップの数がある程度制限され、ｔ−ＬＦＳＲの記憶素子の負荷バランスがとれている移相器でプログラムを走らせたところ、ＸＯＲタップの数に制限をかけた移相器のほとんどにおいて、チャネル間の有効分離幅が、必要とされる分離幅をはるかに上回っていた。これは、デュアルｔ−ＬＦＳＲの軌跡上で、同数の「１」を有し、かつその数が少ない２つの状態間に、多くの状態が存在するためである。この２つの状態間に存在する状態の数が、実際の移相器を決定する。なお、このデュアルｔ−ＬＦＳＲは移相器の合成にも使用され得る。
【００４４】
この実験の主目的は、ｎ(ビット数)、ｃ（フリップフロップ数）、およびｓ（特定された位置の数）の値を変化させて、指定された走査セル上に所望の値を得る見込み可能性を決定することにある。ｎ＝３２、ｓ＝２９、ｗ＝１２８、ｃ＝５０の条件で、４個のＸＯＲタップのフィードバック構造を実施する１８の異なる原始多項式を用いた結果を図９に示す。この図は、チャネル間分離と、解が求まる確率との関係をプロットしたものである。このグラフに示されていない他の多く結果も同様の結果を示すことを記しておく。グラフはまた、理論限界確率を示している。プロットした曲線上の各データポイントは、１０万個のテストキューブを生成して得られたものである。これらのベクトルは、ジェネレータのｎ×ｃビットの出力空間から指定位置をランダムに選択し、それらの位置に２進値をランダムに付与することにより生成された。この実験結果は、移相器を有するｔ−ＬＦＳＲでは、シード変数を見つける確率は、実際にチャネル分離から独立したものになることを明確に示している。
【００４５】
また、適正に合成された移相器を配置した場合は、原始多項式もｔ−ＬＦＳＲの構造も実験結果にさほど影響しないことが容易にみてとれる。言い換えると、どの２つの走査チェーンにおいてもその内容が重複しなければ、最良の性能が達成できる。
【００４６】
特定の実施形態に基づき発明の原理を説明してきたが、この基本原理を逸脱することなく、多様な変形が可能であることは当業者にとって明白である。たとえば、実施形態では特定のアルゴリズムを例にとって説明したが、負荷の均衡を図るためにその他のアルゴリズムを用いることができることは言うまでもない。たとえば、前処理をするかわりに、まず記憶素子を選択しておいてから負荷をチェックして、その記憶素子が許容可能か否かを判断することも可能である。また、記憶素子の負荷は、記憶素子の接続の数（ファンアウト）に焦点をあてて考慮したが、接続に関するその他の物理的情報、たとえば抵抗、インダクタンス、キャパシタンスなどに関連して考慮することもできる。このような物理情報は相互接続長やパス幅によって影響され得る。
【００４７】
さらに、奇数のタップとしたほうが、線形依存性をより効率的に低減できる移相器を生成できることが観察されており、この特性をアルゴリズムの選択に反映して、奇数のタップが生成されるように構成することもできる。このような変更は当業者にとって容易なはずである。
【００４８】
このように多くの変形例が可能であり、実施形態は本発明を説明するための例示にすぎず、その技術的範囲を限定するものではない。本発明の範囲は、このような図示しない実施形態をも包含してクレームにより判断されるべきである。
【図面の簡単な説明】
【図１】  従来の集積回路テストシステムを示すブロック図である。
【図２】  内蔵型テスト（Built-in-test）システムを採用する従来のテストシステムのブロック図である。
【図３】  並列走査チェーンを生成する線形フィードバックシフトレジスタ（ＬＦＳＲ）を備えた従来システムの一例を示す回路図である。
【図４】  移相器を介して並列走査チェーンを生成する線形フィードバックシフトレジスタ（ＬＦＳＲ）を備える従来システムの一例を示す回路図である。
【図５】  多項式ｘ32＋ｘ18＋ｘ14＋ｘ9＋１を実行する変換ＬＦＳＲ（ｔ−ＬＦＳＲ）の回路図である。
【図６】  図５の変換ＬＦＳＲに対応するデュアル変換ＬＦＳＲの回路図である。
【図７Ａ】  最小数のＸＯＲゲートで原始多項式ｘ8＋ｘ6＋ｘ5＋ｘ＋１を実行する変換ＬＦＳＲの回路図である。
【図７Ｂ】  図７Ａの変換ＬＦＳＲに対応するデュアル変換ＬＦＳＲの回路図である。
【図８】  本発明により合成された移相器の回路図である。
【図９】  チャネル間の分離と、移相器を有する変換ＬＦＳＲの解が見つかる確率との関係を示すグラフである。
【図１０】  負荷バランスのとれた移相器を生成する方法を示すフローチャートである。
【図１１】  ＬＦＳＭセルのランダム生成に基づく移相器の生成方法を示すフローチャートである。
【図１２】  移相器生成におけるＬＦＳＭセルの前処理方法を示すフローチャートである。
【図１３】  図１２に示す手順で前処理されたタップのランダムな選択を示すフローチャートである。
【図１４】  移相器生成方法の詳細な手順を示すフローチャートである。
【図１】
0003699397.tif 000011
【図２】
0003699397.tif 000012
【図３】
0003699397.tif 000013
【図４】
0003699397.tif 000014
【図５】
0003699397.tif 000015
【図６】
0003699397.tif 000016
【図７Ａ】
0003699397.tif 000017
【図７Ｂ】
0003699397.tif 000018
【図８】
0003699397.tif 000019
【図９】
0003699397.tif 000020
【図１０】
0003699397.tif 000021
【図１１】
0003699397.tif 000022
【図１２】
0003699397.tif 000023
【図１３】
0003699397.tif 000024
【図１４】
0003699397.tif 000025