JP4076497B2 - 内容アドレス・メモリ内の異なるテーブルの同時サーチ - Google Patents

Description

本発明は、メモリ・デバイスの分野、特に内容アドレス・メモリ（連想記憶装置）に関する。

ネットワークは、伝送回線により相互接続され、相互にデータの転送を行うことができるコンピューティング・システム（例えば、クライアントおよびサーバ）の集まりを含む。ネットワークは、通常、発信元から宛先へデータを転送するため伝送回線間でデータの切り換えおよび／または経路選択を行うことができる複数のアクセス・ポイント（例えば、ルータおよびサーバ）を備える。データは、通常、より小さなデータ・セルで構成されるパケットとして送信される。パケットとは、パケット交換ネットワーク上の発信元と宛先との間で経路選択が行われる１単位のデータのことである。ネットワーク上の一方の場所から他方の場所へファイル（例えば、電子メール、グラフィックスなど）を送信する場合、効率よく送信できる小さなパケットにファイルを分割する。データとデータの経路選択に関連する伝送情報の両方を各パケットに含めることで、所定のファイルの個々のパケットはそれぞれネットワーク全体の異なる経路をたどることができる。したがって、パケットは、データを含むペイロードと経路選択情報（例えば、宛先アドレス）を含む１つまたは複数のヘッダとを備えていると言うことができる。

すべてのパケットが宛先に到着すると、それらのパケットは受信側でオリジナル・ファイルに再構築される。このようなパケット交換方式は、コネクションレス・ネットワークでの伝送を取り扱ううえで効率のよい方法である。これは、接続（例えば、音声接続）の持続期間中、その接続に特定の経路を専用経路として割り当てる必要がある回線交換方式とは対照的である。

ルータとは、その宛先に向けてパケットが転送される次のネットワーク・セグメントを決定するデバイス（例えば、ハードウェア、ファームウェア、ソフトウェア）のことである。ルータは、ネットワーク内の複数のポイントに、または、あるネットワークが別のネットワークと出会う場所（ゲートウェイと呼ばれる）に配置することができる。ルータは、利用可能な経路とその条件を記述したテーブルを作成し、維持し、このテーブルを他の情報とあわせて使用し、与えられたパケットの最適な経路を決定することができる。通常、パケットは、宛先にたどり着くまでに、ルータを備えるいくつものネットワーク・ポイントを通過する。

図１に示されているように、データ・パケットがルータの入力のところに到着すると、何回かルックアップを実行し、パケットのそれ以降の処理を決定する。例えば、ルックアップは、パケットの次の送信先（Ｎｅｘｔ Ｈｏｐ）、サービス品質要件（ＱｏＳ）、Ｅｔｈｅｒｎｅｔ（登録商標）ポート・アドレスなどを含む。例えば、ルータＡに到着したパケットを考える。ルータＡは、パケットがルータＡに直接接続されているローカル・サーバを宛先としているかどうか、またはパケットを宛先への経路（ルータＢ）上の次のルータに送るべきかを決定する必要がある。さらに、ルータＡは、パケットの宛先アドレス（ＤＡ）および発信元アドレス（ＳＡ）に基づいて優先度を割り当てることができる。

まず、パケット・ヘッダを解析または処理して、異なるフィールド（例えば、ＳＡ、ＤＡ、プロトコルの種類、ＱｏＳなど）の値を取得し、さまざまなルックアップを実行する。例えば、ＳＡ、ＤＡ、およびパケット・ヘッダ内の他の関連するフィールドを使用してパケット分類ルックアップを実行する。例えば、「次のホップ」ルックアップを実行して、パケットの宛先をローカル・サーバにするか、またはルータＢにするかを決定する。パケットの宛先がルータＢの場合、パケットはルータＢのキューの中に置かれる。パケットの宛先がローカル・サーバ（例えば、サーバ１またはサーバ２）の場合、メディア・アクセス制御（ＭＡＣ）ルックアップを実行して、パケットを適切なサーバに送信する。前の例では、途中でパケットを送信するのに３つのルックアップ、「パケット分類」、「次のホップ」、「ＭＡＣ」が必要であった。しかし、パケット・ヘッダに対して他のルックアップが実行されることが多いので、ルックアップの個数は５つまたはそれ以上になることもある。

ルータでは、プロセッサおよび内容アドレス・メモリ（ＣＡＭ）デバイスを使用して、パケットに対してさまざまなルックアップを実行することができる。特定のメモリ・ロケーション・アドレスを指定して情報をアクセスするランダム・アクセス・メモリ（ＲＡＭ）デバイスとは対照的に、ＣＡＭに格納されているデータは、データの内容によりアクセスされる。より具体的には、ＣＡＭでは、アドレスを使用して特定のメモリ・ロケーションにアクセスするのではなく、メモリ・デバイス内の特定のメモリ・セルの所望の内容の一部を含むキーを使用する。図２に示されているように、プロセッサはＣＡＭに、コンパランド（被比較数）データ（例えば、パケットのヘッダ・データ）とも呼ばれるキーを連想メモリ・アレイに格納されているデータと比較することを命令する。ＣＡＭは同時にそのエントリのすべてを調べ、キーと一致する格納済みのデータを選択する。

ＣＡＭデバイス全体、またはそのいくつかのブロックが、キー・コンパランド・データと格納されているデータとの一致について同時にサーチされると、ＣＡＭデバイスは、一致フラグを立てて一致が存在することを示す。また、複数一致フラグを立てて複数の一致があることを示す。ＣＡＭデバイスは、通常、一致したロケーションを一致アドレスまたはＣＡＭインデックスに変換する優先エンコーダを含み、このアドレスをステータス・レジスタに出力し、一致したデータにアクセスすることができるようにする。優先エンコーダはさらに、複数の一致するエントリが存在する場合に、最高優先度で一致するメモリ・ロケーションを選別することができる。

２進数（ビット）ストリングの形式でデータを表すことができ、ビットはロー論理状態（「０」）とハイ論理状態（「１」）のいずれかをとる。異なる種類のＣＡＭを異なるデータ形式で使用することができる。２値ＣＡＭは、「０」状態と「１」状態で動作するように設計されているが、３値ＣＡＭは「０」状態、「１」状態、「ドントケア」状態で動作するように設計されている。ビットは、ワード（例えば、６４または７２ビット幅）などのグループにまとめ、ＣＡＭの異なるセグメントに格納することができる。異なるデータ・フィールドに使用されるキーは、異なるワード・サイズとすることができ、例えば、「分類」ルックアップのキーは１２８バイト幅であり、「次のホップ」ルックアップのキーは３２ビット幅である。

異なるルックアップを実行するために、ルータは、それぞれが異なるテーブルを持つ複数のＣＡＭを備えるか、あるいは、異なるテーブルのそれぞれについて複数のブロックを備える単一のＣＡＭを備える。例えば、ルータは３２ビット幅の「次のホップ」ＣＡＭ、１２８ビット幅の「分類」ＣＡＭ、および４８ビットの「ＭＡＣ」ＣＡＭを備える。ルータが複数のＣＡＭを備える場合、複数のＣＡＭのそれぞれは、通常、各ＣＡＭデバイスとさまざまなキーおよび他の入力および出力データを通信するために使用される共通バスに接続される。同様に、ルータが単一のＣＡＭを備え、ブロックが複数ある場合、共通バスを使用して各ブロックにアクセスする。したがって、ルックアップは、通常、パケットの処理（例えば、次の宛先または分類済みロケーションへ経路選択される）前に逐次的に実行される。バスがすべてのＣＡＭまたはＣＡＭブロックの多くの入力および出力機能と共有されているため、バス上にデータを多重化して出力するために多数のクロック・サイクルを必要とする。このため、一般に、従来のＣＡＭデバイスではサーチ速度および全体的なスループットが制限を受ける。従来のＣＡＭデバイスおよびアーキテクチャでは、ルータによってサポートされているポート、セグメント、またはデバイスの個数およびルックアップの回数が増えるとともに、システムの全体的なスループットが制限される可能性があり望ましくない。

本発明は、内容アドレス・メモリ・アレイ内の異なるテーブルを同時サーチするための方法と装置に関する。

一実施態様では、装置は、それぞれが対応するフィルタ回路に結合されている複数の内容アドレス・メモリ・ブロックを備える。フィルタ回路はそれぞれ、共通入力ストリングを受け取り、フィルタ処理されたコンパランド・ストリングをコンパランド情報としてその内容アドレス・メモリ・ブロックに送信するように構成されている。フィルタ・コンパランド・ストリングを圧縮することができる。

本発明の他の特徴および利点は、付属の図面と以下で述べる詳細な説明から明らかになる。

本発明は、例を用いて説明されているが、付属の図面の図の制限を受けることを意図していない。

図１はルータによるパケット処理を概念的に示す図である。

図２はＣＡＭデバイスの一実施形態の図である。

図３は同時ルックアップを実行するように構成されているＣＡＭデバイスを備えるルータのライン・カードまたはブレードの一実施形態の図である。

図４Ａは入力ストリング・フィルタ処理回路を備える複数ブロックＣＡＭデバイスの一実施形態の図である。

図４Ｂは複数ブロックＣＡＭデバイスのフィルタ処理回路の一実施形態の図である。

図５Ａは入力ストリングの一実施形態の図である。

図５Ｂは図５Ａの入力ストリングからの特定のパケット・ヘッダ・セグメントを使用するＣＡＭデバイスのオペレーションを概念的に示す図である。

図６は入力ストリングのフィルタ処理および圧縮の一実施形態を概念的に示す図である。

図７は入力ストリングのフィルタ処理および圧縮のビット操作の一実施形態を概念的に示す図である。

図８は入力ストリングをフィルタ処理し、圧縮されるようにフィルタ回路をプログラムする一方法を示す図である。

図９はクロスバ・スイッチの一実施形態の図である。

図１０は図９のクロスバ・スイッチのメモリ記憶素子の一実施形態の図である。

図１１はフィルタ回路の一実施形態の図である。

図１２は図１１のアドレス・ジェネレータの一実施形態の図である。

図１３は図１１のアドレス・ジェネレータの他の実施形態の図である。

図１４はフィルタ回路の他の実施形態の図である。

図１５はブロック・フィルタ・レジスタに結合されているデータ・ジェネレータの一実施形態の図である。

図１６は図１５の実施形態の使用例を示す図である。

図１７はブロック・フィルタ・レジスタ内のビット・パターン例に基づくクロスバ・スイッチの１０個のマトリックス接続を示す図である。

図１８はブロック・フィルタ・レジスタに結合されているデータ・ジェネレータの他の実施形態の図である。

図１９はセンス・アンプに結合されているブロック・フィルタ・レジスタの一実施形態の図である。

図２０はクロスバ・スイッチの一実施形態の図である。

図２１はフィルタ回路の他の実施形態の図である。

図２２はＯＲ論理回路およびブロック・フィルタ・レジスタに結合されている図２１のデータ・ジェネレータの一実施形態の図である。

図２３はクロスバ・スイッチの他の実施形態の図である。

以下の説明では、本発明を完全に理解できるように、特定のコンポーネント、回路、プロセスの例など具体的詳細事項を多数述べている。しかし、当業者にとっては、本発明を実施するうえでこれらの具体的詳細事項を使用する必要がないことは明白であろう。また他の場合については、本発明を不必要にわかりにくくすることを避けるため、よく知られているコンポーネントまたは方法について詳述していない。

本発明の実施形態は、後述のさまざまな方法ステップを含む。これらのステップは、ハードウェア・コンポーネントによって実行することも、また機械実行可能な命令で実現することもでき、これらの命令を使用することにより、これらのステップを実行する命令をハードウェア・コンポーネント（例えば、プロセッサ、プログラミング回路）にプログラムすることができる。別法として、これらのステップは、ハードウェアとソフトウェアの併用により実行することもできる。

本発明の実施形態は、命令が格納される機械読取可能媒体を備えるコンピュータ・プログラム製品、つまりソフトウェアとして提供することができる。機械読取可能媒体を使用し、本発明の実施形態を製造するために使用される物品（例えば、ウェハ・マスク）を生成するようにコンピュータ・システム（またはその他の電子デバイス）をプログラムすることができる。機械読取可能媒体としては、限定しないが、フロッピー（登録商標）・ディスク、光ディスク、ＣＤ−ＲＯＭ、および光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、フラッシュ・メモリ、または電子命令を格納するのに好適なその他の種類の媒体／機械読取可能媒体などがある。

機械読取可能媒体は、本発明の実施形態を含む集積回路のデザイン・レイアウトを表すデータを格納することができる。集積回路のダイスのデザイン・レイアウトは、さまざまな手段、例えば、回路図、テキスト・ファイル、ゲート・レベル・ネットリスト、ハードウェア記述言語、レイアウト・ファイルなどを使用して生成することができる。１つまたは複数の集積回路ダイスを含むウェハの加工のため、デザイン・レイアウトをマスク層に変換する。その後、集積回路ダイスをパッケージ化されたコンポーネントに組み立てる。デザイン・レイアウト、マスク層生成、および集積回路ダイスの加工およびパッケージングが当業で知られており、したがって、詳細な説明は行わない。

本明細書で説明する方法および装置は、１つまたは複数のフィルタ処理されたコンパランド・ストリングを生成する共通入力ストリングのフィルタ処理に対応している。一実施形態では、共通入力ストリングのフィルタ処理を行うことで、異なるＣＡＭテーブル内の同時ルックアップを異なるＣＡＭデバイス（またはＣＡＭデバイスの異なるブロック）によりフィルタ処理された複数のコンパランドに対し実行し、フィルタ処理されたコンパランド・ストリング内のデータと連想メモリに格納されているデータとの比較を行うことができる。複数のルックアップを逐次実行する代わりに並行実行すると、パケット・スループット（例えば、ルータの）を著しく向上させることができる。

複数のコンパランドまたはサーチ・キー情報を含む共通入力ストリングは、ネットワーク・プロセッサまたは中央処理ユニットなどのコントローラ・ユニットにより形成することができる。一実施形態では、共通入力ストリングは、１つまたは複数のパケット・ヘッダまたはその一部分を含んでいる。入力ストリングは、パケットのその後の処理、例えば、「分類」、「次のホップ」および「ＭＡＣ」を決定するために使用できる入力ストリングのフィールド・セグメント内のさまざまな経路選択データを含んでいる。同じ入力ストリングを異なるフィルタ回路に通す。フィルタ回路は、共通入力ストリングの１つまたは複数のセグメントをフィルタ処理されたコンパランド・データとして１つまたは複数のＣＡＭテーブルに選択的に渡せるように事前にプログラムしておくことができる。

一実施形態では、ビット毎にフィルタ処理を実行することができ、その場合、特定の予め決められているビットが、フィルタ処理されたストリング・セグメントを生成するように共通入力ストリングから選択される。フィルタ処理されたストリング・セグメントは、さらに、適切なビット位置へシフトされるため、フィルタ処理されたストリング・セグメントは圧縮され、フィルタ処理されたコンパランド・ストリングに圧縮される。入力ストリングに対し実行される異なる圧縮および／またはフィルタ処理オペレーションは、逐次実行ではなく、並列実行することができるため、フィルタ処理オペレーションは他のフィルタ処理オペレーションが完了する前に開始することができる。その後、フィルタ処理されたコンパランド・ストリングはそれぞれ、ＣＡＭデバイス・ブロックに供給することができる。こうして、ＣＡＭデバイス・ブロックのすべてが同時ルックアップを実行することができる。別法として、フィルタ処理および／または圧縮を逐次実行し、後のルックアップの前に完了させるか、または後のルックアップと同時に実行することもできる。

一実施形態では、フィルタ処理と圧縮オペレーションは、それぞれ対応するプログラミング回路の制御の下にある複数のクロスバ・スイッチにより実行することができる。入力ストリングは、クロスバ・スイッチのすべてに並行して送信される。各クロスバ・スイッチは、その対応するプログラミング回路により事前にプログラムすることで、入力ストリングの異なるセグメントをフィルタ処理し圧縮して、圧縮されフィルタ処理された複数のコンパランド・ストリングを生成することができる。その後、複数のフィルタ処理されたコンパランド・ストリングを使用して、異なるテーブルを使い異なるルックアップを実行することができる。圧縮されフィルタ処理されたコンパランド・ストリングは、ビット間にギャップができないように連続して埋めることができる。一実施例では、プログラミング回路はアドレス・ジェネレータ、ブロック・フィルタ・レジスタ、およびデータ・ジェネレータを含んでいる。一実施形態では、クロスバ・スイッチおよび／またはブロック・フィルタ・レジスタは、ランダム・アクセス・メモリ（ＲＡＭ）デバイスで実装することができる。

図３は、同時ルックアップを実行するように構成されているＣＡＭデバイスを備えるルータのライン・カードすなわちライン・ブレードの一実施形態の図である。ライン・カード３００は、プロセッサ３１０、入口インターフェース回路３３０、出口インターフェース回路３４０、ＣＡＭデバイス３２０、関連するデータ記憶ユニット３７０、トラフィック・マネージャ３６０、およびペイロード記憶ユニット３５０を備える。

プロセッサ３１０は、ライン・カード３００の他のコンポーネントと連携して、ライン・カード３００の動作全体を制御する機能を備える。例えば、本明細書で説明しているように、プロセッサ３１０は、ネットワーク媒体から入口インターフェース回路３３０を通じてパケットを受信し、パケットのペイロードをペイロード記憶ユニット３５０に格納し、パケット・ヘッダ情報を処理して、ＣＡＭデバイス３２０内の必要なルックアップおよびそれ以降のパケットの処理を決定する。例えば、入口回路は、ＰＨＹおよびＭＡＣデバイスを備える。プロセッサ３１０は、ＣＡＭデバイス３２０によって実行されるルックアップに基づき出口インターフェース回路３４０を通してネットワーク媒体上にパケットを送り出す。出口インターフェース回路３４０はスイッチ・ファブリックに接続されるか、または直接１つまたは複数の他のルータまたはスイッチに接続される。プロセッサ３１０は、１つまたは複数のネットワーク・プロセッサ・ユニット（ＮＰＵ）、マイクロプロセッサ、またはデジタル・シグナル・プロセッサ（ＤＳＰ）などの１つまたは複数の専用プロセッサとすることができる。他の実施形態では、プロセッサ３１０は、他の種類のコントローラ、例えば、フィールド・プログラマブル・ゲート・アレイまたは汎用プロセッサとすることができる。ルータのプロセッサ３１０、入口インターフェース回路３３０、および出口インターフェース回路３４０の各コンポーネントは、当業では知られており、したがって詳細を説明しない。

パケット・ヘッダ内の情報への応答として、特定のパケットに関して、プロセッサ３１０は、１つまたは複数のＣＡＭデバイス３２０により実行されるルックアップの回数および種類を決定し、それらのルックアップに対応するサーチ・キーを形成する。サーチまたはルックアップは、例えば、「分類」ルックアップ、転送ルックアップ（例えば、「次のホップ」または最長プレフィックス一致（ＬＰＭ）ルックアップ、ＭＡＣルックアップ、ＭＰＬＳルックアップなど）を含んでいる。サーチを何回も実行する必要がある場合、プロセッサ３１０は、ルックアップに対するさまざまなサーチ・キーのうち少なくとも２つ、およびすべてを含んでいる複合サーチ・キーを形成する。複合サーチ・キーは、ＣＡＭデバイス３２０に共通入力ストリングとして供給される。ＣＡＭデバイス３２０は、共通入力ストリングから個々のサーチ・キーを選択して識別し、抽出して、それらの個々のサーチ・キーを関連するＣＡＭブロックに供給して、ルックアップを実行する。ルックアップがＣＡＭデバイス３２０のＣＡＭブロック内で並行してまたは同時に実行することができ、そのため、サーチが逐次処理される従来のシステムに比べて総合的なスループットが向上するという効果が得られる。

ＣＡＭデバイス３２０を、図４Ａ、４Ｂに関して後述のように、１つの複数ブロックＣＡＭデバイスとし、各ブロックにコンパランド・ルックアップ用の異なるテーブルを格納するようにすることができる。別法として、ＣＡＭデバイス３２０を単一ブロックＣＡＭデバイスの多数の集まりとし（例えば、それぞれの単一ブロックＣＡＭデバイスは異なる集積回路基板上に形成されている）、各ＣＡＭデバイスをコンパランド・ルックアップ用の異なるテーブルを格納するために使用するようにしてもよい。ＣＡＭデバイス３２０でルックアップを複数回実行した後、一致するエントリの関連する情報（例えば、追加経路選択情報および／またはパケット情報）を関連するデータ・ユニット３７０から取り出すことができる。プロセッサ３１０は、次に、トラフィック・マネージャ３６０と交信し、出口インターフェース回路３４０を通じてライン・カード３００からのパケットの終了をスケジュールする。

図４Ａは、入力ストリング・フィルタ回路を備える複数ブロックＣＡＭデバイスの一実施形態の図である。ＣＡＭデバイス４００は図３のＣＡＭデバイス３２０である。図３のＣＡＭ３２０に関して上で述べたように、ブロックはアレイ全体またはそれよりも大きなアレイの一部とすることができる。一実施形態では、ＣＡＭデバイス４００は、それぞれのブロックが異なるルックアップ・テーブルまたは１つまたは複数の共通ルックアップ・テーブルの一部を格納する複数のブロック・メモリ・アレイ（Ｎ個のブロック）を含んでいる（たとえば、ブロック０およびブロック１は、ある１つのルックアップ・テーブルを格納し、ブロックＮ−３からＮ−１は異なるルックアップ・テーブルを格納するようにできる）。説明を簡単にするため５個のブロック４１０〜４１４が示されているが、ＣＡＭデバイス４００が含んでいるブロックの個数はそれよりも多くても少なくてもよい。ブロック４１０〜４１４のそれぞれは各フィルタ回路４２０〜４２４に結合されている。フィルタ回路４２０〜４２４はそれぞれ、共通入力ストリング４０５を受け取り、入力ストリング４０５に対して、ルックアップを実行するために使用される１つまたは複数のセグメントをフィルタ処理し、抽出し、または除去する処理を行うように構成されている。他の実施形態では、ＣＡＭデバイス４００は、図４Ａ、４Ｂに示されているように、単一の複数ブロックＣＡＭデバイスではなく、複数の単一ブロックＣＡＭデバイスを備えることができる。各フィルタ回路は、さらに、抽出されたサーチ情報を圧縮して、対応するＣＡＭブロックに格納されているデータとの比較操作に加わる連続するビットを形成することができる。

フィルタ回路４２０〜４２４はそれぞれ、専用のフィルタ機能を備えてもよく、また、各フィルタ回路は入力ストリング４０５の１つまたは複数のセグメントまたはビットを動的に選択するようにプログラム可能なものでもよい。

図４Ｂに示されている一実施形態では、フィルタ回路４２０〜４２４はそれぞれ、クロスバ・スイッチ（ＸＢＡＲ）およびプログラミング回路（ＰＧＭ）を備える。例えば、フィルタ回路４２０はクロスバ・スイッチ４３０とプログラミング回路４４０を備える。プログラミング回路４４０を使用してクロスバ・スイッチ４３０を事前にプログラミングすることにより、入力ストリング４０５の特定のフィールド・セグメントをフィルタ処理し、フィールド・セグメントのビット位置をシフトさせて、フィルタ処理されたストリング・セグメントを圧縮し、フィルタ処理されたコンパランド・ストリングに圧縮することができる。１つまたは複数のフィルタ回路４２０〜４２４はプログラミング回路を備えていなくてもよいことに留意されたい。例えば、１つまたは複数のクロスバ・スイッチは、外部デバイス・アクセスおよび直接プログラミングを行うように構成することができる（例えば、図３のプロセッサ３１０により）。ＣＡＭデバイス４００のプログラミング回路は、ユーザーにとって便利なように追加搭載することができる。

プログラミング回路４４０は、データ線４９１を介してフィルタ・データ（ＦＤＡＴＡ）を受信するように構成されており、このデータを使用して、クロスバ・スイッチ４３０を直接的にまたは間接的にプログラムし、共通入力ストリング４０５から特定のフィルタ処理されたコンパランド・ストリングを生成する。以下で詳しく説明するが、プログラミング回路４４０は、さらに、制御線４９２を介して１つまたは複数の制御信号を受信し、クロック・ジェネレータ（図に示されていない）から線４９３を介して１つまたは複数のクロック信号を受信して、プログラミング回路の動作を制御することができる。

フィルタ回路４２１〜４２４はフィルタ回路４２０について説明したのと同様に動作することに留意されたい。各フィルタ回路４２０〜４２４は、各ブロックに異なるテーブルが格納される共通入力ストリング４０５の異なるセグメント、またはセグメントの組み合わせを選択することができる。別法として、１つまたは複数のフィルタ回路は、例えば、対応するＣＡＭブロックに同じルックアップ・テーブルの一部が格納される場合に、共通入力ストリング４０５の同じセグメント、またはセグメントの同じ組み合わせを選択することができる。したがって、各クロスバ・スイッチ４３０〜４３４を対応するプログラミング回路４４０〜４４４でそれぞれ事前にプログラムすることにより、入力ストリングの適切なフィールド・セグメントをフィルタ処理することができる。すると、その結果得られたすべてのフィルタ処理されたコンパランド・ストリングを同時に、対応するＣＡＭブロック内に格納されているそれぞれのルックアップ・テーブルと比較することができる。例えば、フィルタ回路４２０により生成されたフィルタ処理済みコンパランド・ストリングをブロック４１０に格納されているルックアップ・テーブルと比較し、フィルタ回路４２１により生成されたフィルタ処理済みコンパランド・ストリングをブロック４１１に格納されているルックアップ・テーブルと比較する。

他の実施形態では、フィルタ処理されたコンパランド・ストリングまたはサーチ・キーを生成するための、共通入力ストリング４０５のフィルタ処理を逐次実行することができる。ブロック内のルックアップも、同時実行または逐次実行することができる。

図５Ａは、入力ストリングの一実施形態の図である。一実施形態では、入力ストリング４０５は、１つまたは複数のパケット・ヘッダ５１０、５２０から解析すなわち処理されたフィールド・セグメントを含んでいる。データ処理システム（例えば、ルータ、クライアント、サーバ）がネットワーク越しにデータ交換を行う場合、手順として、これらのシステムが互いに通信する方法に関して一致するプロトコルを使用する必要がある。設計の複雑さを軽減するために、ネットワークを一連の層として編成することができる。層の数や各層の機能は、ネットワーク毎に異なる。

例えば、伝送制御プロトコル（ＴＣＰ）／インターネット・プロトコル（ＩＰ）を使用する場合、これは、ネットワーク・アクセス層とインターネット層を含んでいる複数の層に分けられる。ネットワーク・アクセス層では、終端システムとネットワークの間でデータの交換を行うのにＴＣＰを使用している。インターネット層ではデータが複数の相互接続されたネットワークを横断できるようにＩＰを使用している。これらのプロトコルはそれぞれ、上述のように、経路選択情報を含んでいるパケット・ヘッダを使用する。例えば、ＴＣＰパケット・ヘッダ５１０は、発信元アドレス（ＳＡ）ポート・セグメント５５２と宛先アドレス（ＤＡ）ポート・セグメント５５３を含み、ＩＰパケット・ヘッダ５２０は、ＳＡセグメント５５４、ＤＡセグメント５５５、サービス・タイプ（ＴｏＳ）セグメント５５１、およびプロトコル・タイプ・セグメント５５６を含んでいる。

一実施形態では、例えば、図３のプロセッサ３１０は、パケット・ヘッダ５１０、５２０からいくつかのセグメントを解析し、入力ストリング４０５を生成し、入力ストリングをＣＡＭデバイス３２０に送信する。例えば、入力ストリング４０５は、ＭＡＣセグメント５５７、ＴＯＳセグメント５５１、ＳＡポート・セグメント５５１、ＤＡポート・セグメント５５２、ＳＡセグメント５５４，およびＤＡセグメント５５５を含んでいる。別法として、入力ストリング４０５が含んでいるセグメントの数は、示されているセグメントよりも多くても少なくてもよい。各フィルタ回路（図４Ａ、４Ｂに示されている）は、入力ストリング４０５の異なるフィールド・セグメントのビット値をフィルタ処理し、それぞれ異なるフィルタ処理済みコンパランド・ストリングを生成して、ＣＡＭブロック内で異なるルックアップを同時に実行することができる。他の実施形態では、プロセッサ３１０は、解析されていない受信されたときのままのヘッダ・セグメントをＣＡＭデバイス３２０に送信することができる。

図５Ｂは、図５Ａに示されている入力ストリング４０５のパケット・ヘッダ・セグメントを使用するＣＡＭデバイス４００の動作を概念的に示す図である。例えば、ＣＡＭデバイス４００は、３つのＣＡＭブロック４１０、４１１、４１２を含んでいるとする。各ブロック４１０、４１１、４１２はそれぞれ、対応するフィルタ回路４２０、４２１、４２２にそれぞれ結合されている。フィルタ回路４２０〜４２２はそれぞれ、入力ストリング４０５を受け取り、受け取った入力ストリング４０５を処理するように構成されている。

一実施形態では、フィルタ回路４２０〜４２２を事前にプログラムすることにより、入力ストリング４０５の特定のフィールド・セグメントをフィルタ処理し、ブロック４１０〜４１２に格納されているさまざまなテーブルに対し同時ルックアップを実行するようにできる。例えば、ＭＡＣセグメント５５７をフィルタ処理してフィルタ処理されたコンパランド・ストリング５８０が得られるようにフィルタ回路４２０を事前にプログラムする、ＤＡセグメント５５５をフィルタ処理してフィルタ処理されたコンパランド・ストリング５８１が得られるようにフィルタ回路４２１を事前にプログラムする、ＳＡセグメント５５４と、ＤＡフィールド・セグメント５５５と、ＴＯＳセグメント５５１をフィルタ処理してフィルタ処理されたコンパランド・ストリング５８２が得られるようにフィルタ回路４２２を事前にプログラムするといったことができる。共通入力ストリング４０５から異なるフィールド・セグメントをフィルタ処理することにより、並行して、フィルタ処理されたコンパランド・ストリング５８０〜５８１のそれぞれを使用して、さまざまなルックアップを同時実行することができる。例えば、フィルタ処理されたコンパランド・ストリング５８０を使用してＣＡＭブロック４１０内でＭＡＣルックアップを実行する、フィルタ処理されたコンパランド・ストリング５８１を使用してＣＡＭブロック４１１内で「次のホップ」（例えば、ＬＰＭ）ルックアップを実行する、フィルタ処理されたコンパランド・ストリング５８２を使用してＣＡＭブロック４１２内で「分類」ルックアップを実行するといったことができる。したがって、それぞれのルックアップが実行のためにＸクロック・サイクルを個々に必要とする場合、ルックアップは同時実行されるため、３つ全部のルックアップを実行するのに全部でＸクロック・サイクルあればよい。このようにして、ルータでのパケット・スループットは、従来のＣＡＭアーキテクチャを利用したルータに比べて著しく向上する。

図６は、入力ストリングのフィルタ処理および圧縮の一実施形態を概念的に示す図である。すでに述べたように、入力ストリング４０５は、パケットのヘッダの一部である。または全部であってもよい。すなわち、入力ストリング４０５はパケットの他の部分からのフィールド・セグメントまたは他の処理済み情報を含んでいる。入力ストリング４０５は、入力ストリング４０５の望ましくないフィールド・セグメントをマスク・アウト、つまりブロックするフィルタ６２０に通される。フィルタ６２０の出力は、１つまたは複数のフィルタ処理されたストリング・セグメント６２９である。例えば、４つのストリング・セグメントＸ₁、Ｘ₂、Ｘ₃、Ｘ₄をフィルタ６２０に通してフィルタ処理する。ストリング・セグメントＸ₁、Ｘ₂、Ｘ₃、Ｘ₄は、例えば、ＤＡ、ＳＡ、サービス・タイプ（ＴｏＳ）、プロトコル・タイプに対応する。入力ストリング４０５のフィルタ処理は、フィルタ回路４２０〜４２４のうち１つまたは複数により実行することができる。しかし、各フィルタ回路４２０〜４２４は、入力ストリング４０５の異なるフィールド・セグメントまたは同じフィールド・セグメントのうちの１つまたは複数をフィルタ処理するようにプログラムされている。入力ストリング４０５のフィルタ処理は、ビット毎に実行することができる。別法として、入力ストリング４０５のフィルタ処理は、他のサイズ、例えば、バイト・サイズに基づいて実行することができる。さらに、フィルタ回路４２０〜４２４をそれぞれ事前にプログラムすることにより、前のプログラムされた状態から入力ストリング４０５の異なるフィールド・セグメントをフィルタ処理することができる。

図６に示されているように、フィルタ処理されたストリング・セグメント（Ｘ₁、Ｘ₂、Ｘ₃、Ｘ₄）６２９は互いに隣接していなくてもよい。このような隣接していないフィルタ処理済みストリング・セグメントをシフトし、圧縮されたフィルタ処理済みのストリング６３９を生成することができる。例えば、フィルタ処理をビット毎に実行する場合、フィルタ回路（例えば、フィルタ回路４２０）はフィルタ処理されたストリング・セグメント６２９のビットを移動させ、フィルタ処理されたコンパランド・ストリング６３９を生成する。一実施形態では、例えば、フィルタ処理されたストリング・セグメント６２９のビットのすべてを最下位位置側にシフトさせる。別法として、フィルタ処理されたストリング・セグメント６２９のビットを、他の方法で、例えば、最上位側にシフトさせることもできる。

図７は、クロスバ・スイッチ７２０（例えば、クロスバ・スイッチ４３０）を使用して入力ストリングのフィルタ処理および圧縮に対するビット操作の一実施形態を概念的に示す図である。クロスバ・スイッチ７２０は、交差点からなるｎ×ｎ行列を含んでいるが、ただし、ｎは入力ストリング４０５のビット幅であり、また出力ストリングのビット幅でもある。各菱形（例えば、菱形７２１）は、フィルタ処理されたコンパランド・ストリングの入力ビットＩＮ（０）〜ＩＮ（ｎ−１）および出力ビットＹ（０）〜Ｙ（ｎ−１）に対する交差点および可能な接続を表す。１つまたは複数の交差点がアドレスで選択され、クロスバ・スイッチ７２０は、入力ストリング４０５から所定のビットを選択して圧縮されフィルタ処理されたコンパランド・ストリングの出力ビット位置に移動すなわち圧縮させるように、プログラム・データ（ＰＤＡＴＡ）によりプログラムされる。アドレスおよび／またはＰＤＡＴＡは、プログラム回路（例えば、図４Ｂのプログラム回路４４０）により生成するか、または外部で（例えば、図３のプロセッサ３１０により）生成することができる。

フィルタ回路の対角線上の線７２２は、入力ストリング４０５と出力フィルタ処理済みコンパランド・ストリング６３９のビット位置の間の１対１の接続相関関係を表す。選択された、またはプログラムされたビット、丸に＋の記号（例えば、図７の接続７２３）は入力ビット位置と出力ビット位置との接続を行うためのプログラムされたビットを表す。各接続は、交差点のところで１つまたは複数の回路要素をプログラムすることにより確立される。交差点のプログラミングでは、メモリ・セルの状態の書き込み、ヒューズまたはその他の接続の切断、接続をそのままにすることなどさまざまな手段を使用することができる。例えば、メモリ素子を使用して交差点での接続を確立する場合、第１の論理状態（例えば、論理「１」）をメモリ素子に書き込むと接続が確立され、第２の論理状態（例えば、論理「０」）をメモリ素子に書き込むと接続は確立されない。

結果としてフィルタ回路７２０により出力されるフィルタ処理済みコンパランド・ストリング６３９のビット・ギャップを避けるようにクロスバ・スイッチ７２０をプログラムする。図の例では、入力ストリング４０５の選択されたビットすべてが最下位ビット位置側にシフトされる。したがって、その結果のフィルタ処理されたコンパランド・ストリング６３９のビット位置の数は入力ストリング４０５よりもかなり少なくなる。例えば、入力ストリング４０５は、２８８ビット幅（ｎ＝２８８）とすると、フィルタ処理されたコンパランド・ストリング６３９は７２または１４４ビット幅のみである。クロスバ・スイッチの交差点の数を出力ビットの個数に合わせて減らすことができる。ＣＡＭブロック４１０〜４１４のそれぞれのルックアップ・エントリは、入力ストリング４０５のサイズよりもかなり小さいことのが望ましい。すなわち、幅の狭いＣＡＭアレイ（つまり、共通入力ストリングの全長よりも行当たりビット数が少ない）を使用することができる。また、ＣＡＭアレイの未使用列はグローバル・マスク回路（図には示されていない）により全体的にマスクされ、サーチ動作では使用されるすなわち消費される電力が最小または実質的に少ないため、圧縮されフィルタ処理されたストリングは望ましい省電力機能を備えることができる。そのためのグローバル・マスクは当業では知られており、したがって、本明細書では詳細を説明しない。

図７では、入力データを出力データ・ストリング内の上位ビット位置から下位ビット位置側に圧縮するすなわち移動させるプログラムされたクロスバ・スイッチが説明されている。他のフィルタも、入力データを出力ストリング内の下位ビット位置から上位ビット位置側に圧縮する、すなわち移動させることができる。さらに、フィルタ処理されたストリングは圧縮する必要はなく、ギャップのあるフィルタ処理されたストリングは、もしあれば、ルックアップのためＣＡＭブロックまたはテーブルに与えることができる。ＣＡＭブロックに供給されるサーチ・キーの中の未使用ビットは、グローバル・マスク・レジスタにより全体的にマスクすることができる。

クロスバ・スイッチ７２０により生成されたフィルタ処理されたコンパランド・ストリングのサイズは、入力ストリング４０５の選択されたビットが連続していたとしても入力ストリング４０５よりも小さい場合があることに留意されたい。例えば、選択する入力ストリング４０５のビットが行０から行２に対応する場合、選択された行は連続しているため、出力ビットをシフトする必要はない。したがって、入力ストリング４０５の目的のビットが連続しているとしても、その結果得られるフィルタ処理されたコンパランド・ストリング６３９のサイズもまた、全体として入力ストリング４０５のサイズよりも小さい場合がある。

図８は、入力ストリングをフィルタ処理し、圧縮されるようにフィルタ回路をプログラムする一方法を示す図である。この方法は、例えば、図４Ｂのプログラミング回路または図３のプロセッサ３１０により実行することができる。この方法は、リセットに基づいてＣＡＭデバイスに供給される明示的なプログラム命令または制御信号への応答として、または他の刺激に対する応答として開始する。一実施形態では、その結果得られる出力ストリング６３９のギャップを回避するために、入力ビットを連続して順次供給し、入力ビットが特定の出力ビットとして与えられるかどうかを判別する。

プログラミングはステップ８０２から開始する。ステップ８０４で、特定の入力ビットを特定の出力ビット位置に供給すべきかどうかを判定する（例えば、図４Ｂのプログラム回路４４０に供給されるＦＤＡＴＡにより判定する）。もし供給すべきであれば、ステップ８０６で、クロスバ・スイッチにおいて適切な接続が確立されるか、またはプログラムされる。ステップ８０８で、これが最後の入力ビットでなければ、この方法は次の入力ビット（ステップ８１０）に進み、ステップ８０４を繰り返す。すべての入力ビットが処理されると、プロセスは完了する（ステップ８１２）。

図４のクロスバ・スイッチ４３０には、任意の種類のクロスバ・スイッチを使用することができる。図９は、クロスバ・スイッチ４３０の一実施形態であるクロスバ・スイッチ１０００の図である。クロスバ・スイッチ１０００は、トランジスタ１０２０のゲートに結合されているメモリ記憶素子１０１０の行と列からなるアレイを含んでいる。各メモリ記憶素子／トランジスタのペアは、行と列の交差点に配置され、これを使用して、入力信号ＩＮ（０）〜ＩＮ（ｎ−１）と出力信号Ｙ（０）〜Ｙ（ｎ−１）との間の接続を確立する（または確立しない）。入力信号ＩＮは、入力ストリング・データ（例えば、図４Ａの入力ストリング４０５）を表し、出力信号Ｙは、ＣＡＭブロックまたはテーブルに供給されるフィルタ処理された出力ストリングを表す。

各メモリ記憶セル１０１０は、スイッチ１０００内の特定の行および列の交差点で接続が確立されているかどうかを示す状態を格納する。メモリ記憶セルは、ランダム・アクセス・メモリ（ＲＡＭ）セル（スタティックＲＡＭとダイナミックＲＡＭ）、読み取り専用（ＲＯＭ）セル、およびその他の揮発性または不揮発性メモリ記憶セルなどどのような種類のメモリでもよい。メモリ記憶セルは、メモリ記憶セルのタイプに適した書き込み回路を使用してプログラムまたは書き込みを行うことができる。メモリ記憶セルは論理「１」状態を格納している場合、関連するトランジスタ１０２０を有効にし、入力信号ＩＮを信号線１０３０（０）〜１０３０（ｎ−１）のいずれか１つに出し、出力Ｙのうちの１つを信号線１０４０（０）〜１０４０（ｎ−１）のいずれか１つに出す。出力信号線１０４０は、さらに、プリチャージ回路１０５０により所定の状態またはデフォルトの状態までプリチャージすることもできる。プリチャージ回路１０５０は、よく知られているどの回路でもよい。

クロスバ・スイッチ１０００は完全なクロスバ・スイッチであり、これにより任意の入力を出力Ｙに接続できる。他の実施形態については、入力ストリングが圧縮される場合などにクロスバ・スイッチ１０００の一部のみを必要とすることがある。例えば、出力ストリング内の上位ビット位置から下位ビット位置へ入力ストリングを圧縮する場合、下位ビット位置から上位ビット位置へ移動させるためのクロスバ・スイッチの対応する回路を完全なクロスバ・スイッチから取り除くことができる。同様に、出力ストリング内の下位ビット位置から上位有効ビット位置へ入力ストリングを圧縮する場合、上位ビット位置から下位有効ビット位置へ移動させるためのクロスバ・スイッチの対応する回路を完全なクロスバ・スイッチから取り除くことができる。以下では修正されたクロスバ・スイッチの実施例について説明する。

図１０は、メモリ記憶セル１０１０の一実施形態であるメモリ記憶セル１１００の図である。セル１１００は、ノード１１８０、１１９０でデータを格納するための双安定ラッチを形成するクロス・カップルド・インバータ１１３０、１１４０を備えている。パス・ゲート１１５０、１１６０では、信号線１１１０であるワード線の信号がアクティブになると、プログラム・データ（および読み取りデータ）を記憶装置ノードに伝達することができる。ノード１１８０はトランジスタ１０２０のゲートに結合されている。またリセット・トランジスタ１１７０を含めることで、信号線１１２０上のリセット信号ＲＥＳＥＴがアクティブになったときに、ノード１１８０を予め定められている論理「０」状態にすることができる。リセット・トランジスタ１１７０は、ゲートが信号線１１２０に結合され、ドレインがノード１１８０に結合され、ソースがグランドに結合されている。

図１１は、図４Ａのフィルタ回路４２０〜４２４の１つの一実施形態であるフィルタ回路１２００の図である。この実施形態では、フィルタ回路１２００はクロスバ・マトリックス・スイッチ４３０とプログラミング回路１２０４を備える。一実施形態では、完全なクロスバ・スイッチ（例えば、図９のクロスバ・スイッチ１０００）をクロスバ・スイッチ４３０に使用する。他の実施形態では、完全なクロスバ・スイッチを、必要な接続機能のみを持つように修正することにより、クロスバ・スイッチのサイズを縮小することができる。

この実施形態では、プログラミング回路１２４０はプログラム・データ・ジェネレータ１２０８とアドレス・ジェネレータ１２０６を備える。プログラム・データ・ジェネレータ１２０８は、クロスバ・スイッチの交差点のうち１つまたは複数をプログラムするためのプログラミング・データＰＤＡＴＡを生成する。ＰＤＡＴＡはフィルタ・データＦＤＡＴＡへの応答として生成される。フィルタ・データＦＤＡＴＡは、出力ストリングに入力ビットを入れるかどうか、および入力ビットを出力ストリングに圧縮するかすなわち移動させるかどうか、およびどのようにして圧縮すべきかを示す。例えば、図３のプロセッサ３１０によってＦＤＡＴＡを与えることができる。アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０に結合される。他の実施形態では、アドレス・ジェネレータ１２０６をさらに、プログラム・データ・ジェネレータ１２０８に結合することもできる。アドレス・ジェネレータ１２０６は、プログラミングのためクロスバ・スイッチ４３０の１つまたは複数の交差点にアクセスするオペレーションを実行する。アドレス・ジェネレータ１２０６は、例えば、１つまたは複数の行および／または列デコーダを備え、プログラミングのためクロスバ・スイッチ内の交差点の１つまたは複数の行または列を選択したり、またはプログラミングのため単一の交差点または交差点の他のグループを選択する。

一実施形態では、アドレス・ジェネレータ１２０６は、図１２に示されているように、アドレス・カウンタ１３０２によって制御されるデコーダ１３０４を備える。アドレス・カウンタ１３０２は、クロスバ・スイッチ４３０に結合されている信号線１３０６（０）〜１３０６（ｎ−１）の信号をアクティブにすることにより、クロスバ・スイッチ４３０の行または列を通じてデコーダ１３０４を順次実行させるように構成される。カウンタ１３０２は、クロック信号ＣＬＫおよびプログラムする場合にアクティブにされるイネーブル信号ＥＮＡＢＬＥに対する応答として、カウントを増分または減分し、新しい行または列を選択する。ＥＮＡＢＬＥ信号は、プログラム・データ・ジェネレータ１２０８によって制御するか（例えば、ＦＤＡＴＡへの応答として）、または外部から（例えば、図３のプロセッサ３１０により）制御することができる。別法として、アドレス・ジェネレータ１２０６は、他のコンポーネント、例えば、図１３に示されているように、クロスバ・スイッチ４３０の行および／または列を順次辿るためのシフト・レジスタ１４０２を備えることもある。アドレス・ジェネレータ、アドレス・デコーダ、レジスタ、およびカウンタは当業では知られており、したがって、詳細を説明しない。

図１４は、図１１のプログラム・データ・ジェネレータ１２０８の一実施形態であるプログラム・データ・ジェネレータ１５０２の図である。プログラム・データ・ジェネレータ１５０２は、バッファ書き込み回路１５０４、データ・ジェネレータ１５０６、ブロック・フィルタ・レジスタ（ＢＦＲ）１５０８を備える。データ・ジェネレータ１５０６、ＢＦＲ １５０８とアドレス・ジェネレータ１２０６は、任意選択により、図１４において破線で示されているように、１つまたは複数のクロック信号ＣＬＫを受信する。

ブロック・フィルタ・レジスタ１５０８は、目的のフィルタ処理されたコンパランド・ストリングを取得するため入力ストリング４０５のフィルタ処理に使用される特定のフィルタ・データＦＤＡＴＡを格納する。ブロック・フィルタ・レジスタ１５０８は、入力ストリング４０５の所望のフィルタ処理に基づいて特定の「１」および「０」ビット・パターンでプログラムすることができる（例えば、図３のプロセッサ３１０により）。したがって、フィルタ回路４２０〜４２４内のブロック・フィルタはそれぞれ、異なるビット・パターンを格納することができ、それにより、すべてのフィルタ回路４２０〜４２４に適用される共通入力ストリング４０５と異なるビットをフィルタ処理することができる。別法として、ブロック・フィルタ・レジスタは、他のブロック・フィルタ・レジスタと同じビット・パターンを格納することができる。他の実施形態では、複数のブロック・フィルタ・レジスタを単一のプログラム・ジェネレータ１５０２で使用したり、（例えば、図３のプロセッサ３１０、または他の素子により）選択することができ、適切なＦＤＡＴＡを供給することができる。

ブロック・フィルタ・レジスタ１５０８は、データ・ジェネレータ１５０６に結合されている。データ・ジェネレータ１５０６はＰＤＡＴＡビット・パターンを生成し、これをバッファ書き込み回路１５０４にロードし、クロスバ・スイッチ４３０内の交差点を選択してプログラムする。バッファ書き込み回路１５０４は、クロスバ・スイッチ４３０にプログラムされるデータをバッファリングする。一実施形態では、バッファ書き込み回路１５０４は、データ・ジェネレータ１５０６の一部でもよい。バッファ書き込み回路は当業では知られており、したがって、詳細を説明しない。

一実施形態では、入力データ・ストリング内にあるビットと同じ数だけＦＤＡＴＡのビットがＢＦＲ １５０８にロードされる。ＦＤＡＴＡの特定のビットにより、入力ストリング内の対応するビット位置が出力ストリング内に存在するかどうかが示される。このようにして、ＢＦＲ １５０８内のＦＤＡＴＡはマスクとして動作し、それにより、出力ストリング上でいくつかの入力ビットがフィルタ処理されＣＡＭブロックへ供給されない。ＦＤＡＴＡにより実行されるマスキングでは、データ・ジェネレータ１５０６はクロスバ・スイッチ４３０に適切なＰＤＡＴＡを生成することができ、スイッチ４３０は適宜、入力ストリングをフィルタ処理して圧縮する。

プログラム回路１２０４の作用を説明する例では、アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の第１の行を最初に選択するように構成されている。データ・ジェネレータ１５０６は、ブロック・フィルタ・レジスタ１５０８に格納されている対応するＦＤＡＴＡビットにおいてその行／列位置に対応するビット位置に「１」が格納されている場合、選択された行および特定の列に対する相互接続をプログラムする。ブロック・フィルタ・レジスタ１５０８に格納されているＦＤＡＴＡビットにおいて「０」がその後の行／列位置に対応するビット位置に格納される場合には、その入力行に対して接続が確立されないように、データ・ジェネレータ１５０６は、行および列相互接続に「０」をプログラムする。その後、アドレス・ジェネレータ１２０６は、行の残りとブロック・フィルタ・レジスタ内の追加ＦＤＡＴＡビットとを順次巡り、さらに、接続が確立されているかどうかを判定する。一実施形態では、アドレス・ジェネレータ１２０６は、ＦＤＡＴＡによる決定に従い、行の残りを順次巡り、条件付きで列を順次巡る。他の実施形態では、アドレス・ジェネレータ１２０６は、ＦＤＡＴＡによる決定に従い、条件付きで新しい行に順次進み、連続して列を順次巡る。

図１５は、それぞれデータ・ジェネレータ１５０６およびＢＦＲ １５０８の実施形態であるデータ・ジェネレータ１６０６とＢＦＲ １６０８の図である。データ・ジェネレータ１６０６は、シフト・レジスタ１６１０、論理回路１６２０、論理ゲート１６０５を備える。シフト・レジスタ１６１０は、データのｎ＋１個のビットを格納しており、第１のｎビットは最初すべて論理「０」であり、ｎ＋１ビットは論理「１」に設定される。シフト・レジスタ１６１０は、ループ・シフト・レジスタであり、ｎ＋１ビット位置に事前にロードされた「１」は、ＡＮＤゲート１６０５の出力に基づきシフト・レジスタ１６１０の他のビット位置を通してシフトされる。したがって、所定の時刻に、シフト・レジスタ１６１０内の１ビット位置のみ論理「１」が入り、他のビット位置には論理「０」が入る。

ＢＦＲ １６０８は、シフト・レジスタでもあり、ＦＤＡＴＡのｎ個のビットを格納する。ＢＦＲ １６０８に格納されているＦＤＡＴＡの各ビットは、信号線１６９５上のＣＬＫによりクロックに同期してＡＮＤゲート１６０５の１つの入力に出力される。ＡＮＤゲート１６０５は、さらに、ＣＬＫも受信し、ＦＤＡＴＡ入力とＣＬＫの両方の論理「１」への応答として、シフト・レジスタ１６１０の内容を１ビットだけ左にシフトさせることができる。したがって、ＢＦＲ １６０８に格納されているＦＤＡＴＡにより、シフト・レジスタ１６１０がその内容をシフトするかどうかが判別される。シフト・レジスタ１６１０とＢＦＲ １６０８が異なるクロック信号を受信するように構成できることに留意されたい。さらに、シフト・レジスタ１６１０と論理回路１６２０に信号を送る前に、ＡＮＤゲート１６０５の出力をラッチするか、またはレジスタに格納することもできる。

シフト・レジスタ１６１０内の各ビットが、論理回路１６２０のＡＮＤゲート１６０１（０）〜１６０１（ｎ−１）の１つの入力に結合されている。ＡＮＤゲート１６０１（０）〜１６０１（ｎ−１）の他の入力は一緒にされてＡＮＤゲート１６０５の出力を受け取る。ＣＬＫが低（つまり、「０」論理状態）の場合、ＡＮＤゲート１６０１は論理「０」を出力する。ＣＬＫが高（つまり、「１」論理状態）の場合、ＡＮＤゲート１６０１はシフト・レジスタ１６１０から受け取ったビット内容を出力する。このような構成では、論理回路１６２０は、すべて「０」か、またはシフト・レジスタ１６１０のビット内容のいずれかを出力する。ＡＮＤゲート１６０１（０）〜１６０１（ｎ−１）から出力される信号は、それぞれ信号線１６０３（０）〜１６０３（ｎ−１）に出力され、図１４のバッファ書き込み回路１５０４に結合される。次に、バッファ書き込み回路１５０４は、このデータをＰＤＡＴＡとしてクロスバ・スイッチに供給し、その行および列接続を確立する。

上述のように、論理回路１６２０は、すべて論理「０」またはシフト・レジスタ１６１０の内容のいずれかをＰＤＡＴＡとして出力し、クロスバ・スイッチ４３０の接続をプログラムする。クロスバ・スイッチ４３０の行がアドレス・ジェネレータ１２０６により選択された場合、出力ビット位置への入力ビットが確立されないように行はすべて論理「０」でプログラムされるか、または接続が確立されるように行の単一ビットがプログラムされる。アドレス・ジェネレータ１２０６は、その後、次の行へ順次進む。その後、論理回路１６２０により出力されたＰＤＡＴＡは、ＢＦＲ １６０８のＦＤＡＴＡにより示されているように更新される。次のＦＤＡＴＡビットが論理「０」状態であれば、次の行に対し接続は行われないが、次のＦＤＡＴＡビットが論理「１」状態であれば、接続がプログラムされる。このようにして、データ・ジェネレータ１６０６とＢＦＲ １６０８では、入力ストリングをフィルタ処理し、さらにそのストリングを圧縮するように、クロスバ・スイッチ４３０をプログラムすることができる。具体的な例が図１６に示されている。

図１６で、シフト・レジスタ１６１０は、１１個のビット位置（ｎ＝１０）を持ち、ＢＦＲ １６０８は１０個のビット位置を持つ。ＢＦＲ １６０８は、クロスバ・スイッチ４３０でいくつかの接続を確立し、入力ストリング４０５のビットをフィルタ処理し圧縮するために使用されるビット・パターン例とともに示されている。この例では、ＢＦＲ １６０８は、ビット位置１６８１、１６８２、１６８５、１６８６、１６８９、１６９０が「１」であるＦＤＡＴＡを格納する。入力ストリング４０５からのビットをマスクするために、ビット位置１６８３、１６８４、１６８７、１６８８に「０」を格納する。

最初に、図１４のアドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の交差点の行（または列）を選択し、第１の入力ビット位置ＩＮ（０）が対応する第１の出力ビット位置Ｙ（０）に結合されるかどうかを判別する。ＣＬＫの第１のクロック・サイクルで、ＢＦＲ １６０８のビット位置１６８１の「１」がＡＮＤゲート１６０５に供給される。ビット位置１６８１は「１」が設定されているので、次のクロック・サイクルで、ビット位置１６５０にある「１」はシフト・レジスタ１６１０のビット位置１６４０にシフトされる。その後、ＡＮＤゲート１６０１（９）〜１６０１（０）はそれぞれ、ＰＤＡＴＡとして、クロスバ・スイッチ４３０に（バッファ書き込み１５０４を介して）０００００００００１を出力し、スイッチ・マトリックスの列０および行０の交差点のＩＮ（０）とＹ（０）との間の接続を確立するが、これは、図１７の交差点の行０および列０で丸に「＋」の記号により示されている。ＡＮＤゲート１６０１（１）〜１６０１（９）は行０およびその他の列の他の可能な相互接続に「０」を出力するため、それらの交差点については接続は確立されない。

その後、アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の第２の行（行１）を選択し、第２の入力ビット位置ＩＮ（１）が第１または第２の出力ビット位置Ｙ（１）およびＹ（０）のいずれかに結合されるかどうかを判別する。ＢＦＲ １６０８のビット位置１６８２が「１」を格納しているため、ＣＬＫのその後クロック・サイクルで、シフト・レジスタ１６１０と論理回路１６２０により他のシフトとプログラムのオペレーションが実行される。ＡＮＤゲート１６０５に「１」が供給され、ビット位置１６４０の「１」がシフト・レジスタ１６１０のビット位置１６４１にシフトされ、「０」がビット位置１６４０にシフトされる。ＡＮＤゲート１６０１（９）〜１６０１（０）はそれぞれ、ＰＤＡＴＡとして、クロスバ・スイッチ４３０に（バッファ書き込み１５０４を介して）００００００００１０を出力し、スイッチ・マトリックスの列１、行１の交差点のＩＮ（１）とＹ（１）との間の接続を確立するが、これは、図１７の交差点の行１と列１で丸に「＋」の記号により示されている。ＡＮＤゲート１６０１（０）、１６０１（２）〜１６０１（９）は行１およびその他の列の他の可能な相互接続に「０」を出力するため、それらの交差点については接続は確立されない。

その後、アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の第３の行（行２）を選択し、第３の入力ビット位置ＩＮ（２）が第１、第２、または第３の出力ビット位置Ｙ（０）、Ｙ（１）、またはＹ（２）のいずれかに結合されるかどうかを判別する。次のクロック・サイクルでは、シフト・レジスタ１６１０は、ＢＦＲ １６０８のビット位置１６８３に「０」が格納されているため、シフトしない。したがって、行２についてスイッチ４３０の列または出力と接続が確立されない。つまり、ＩＮ（２）はフィルタ出力ストリング内の対応する出力ビット位置に結合されず、図１７に示されているように効果的にマスクされる。

その後、アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の第４の行（行３）を選択し、第４の入力ビット位置ＩＮ（３）が第１、第２、第３、または第４の出力ビット位置Ｙ（０）、Ｙ（１）、Ｙ（２）、またはＹ（３）のいずれかに結合されるかどうかを判別する。次のクロック・サイクルでは、シフト・レジスタ１６１０は、ＢＦＲ １６０８のビット位置１６８４に「０」が格納されているため、シフトしない。したがって、行３についてスイッチ４３０の列または出力と接続が確立されない。つまり、入力ビット４はフィルタ出力ストリング内の対応する出力ビット位置に結合されず、図１７に示されているように効果的にマスクされる。

その後、アドレス・ジェネレータ１２０６は、クロスバ・スイッチ４３０の第５の行（行４）を選択し、第５の入力ビット位置ＩＮ（４）が第１、第２、第３、第４、または第５の出力ビット位置Ｙ（０）、Ｙ（１）、Ｙ（２）、Ｙ（３）、またはＹ（４）のいずれかに結合されるかどうかを判別する。その後のクロック・サイクルで、「１」がビット位置１６８５に格納されているので、ビット位置１６４１にある「１」はシフト・レジスタ１６１０のビット位置１６４２にシフトされる。ＡＮＤゲート１６０１（９）〜１６０１（０）はそれぞれ、ＰＤＡＴＡとして、クロスバ・スイッチ４３０に（バッファ書き込み１５０４を介して）０００００００１００を出力し、スイッチ・マトリックスの列２および行４の交差点での接続を確立するが、これは、図１７の交差点の行４および列２で丸に「＋」の記号により示されている。そこで、ＩＮ（４）とＹ（２）との接続が確立される。ＡＮＤゲート１６０１（０）〜１６０１（１）および１６０１（３）〜１６０１（９）は行１およびその他の列の他の可能な相互接続に「０」を出力するため、それらの交差点については接続は確立されない。図１６のＢＦＲ １６０８に格納されているＦＤＡＴＡへの応答としてプログラムされたクロスバ・スイッチ４３０の完了したフィルタ処理および圧縮が図１７に示されている。

図１８は、図１５のデータ・ジェネレータ１５０６とＢＦＲ １５０８の他の実施形態であるデータ・ジェネレータ１９０６とＢＦＲ １９０８の図である。データ・ジェネレータ１９０６は、図１５に関してすでに述べているように、シフト・レジスタ１６１０、論理回路１６２０、ＡＮＤゲート１６０５を備え、さらにワイヤードＯＲ回路１９１３とシフト・レジスタ１９１６を備える。ワイヤードＯＲ回路１９１３は、ＢＦＲ １９０８の異なるＦＤＡＴＡビットおよびシフト・レジスタ１９１６からの対応するビットを受け取るように結合されているＡＮＤゲート１９３０とプルダウン・トランジスタ１９３１とのペアを備える。ＢＦＲ １９０８は、並行してビット位置データすべてをワイヤードＯＲ回路１９１３に出力する。ワイヤードＯＲ回路１９１３は、順に、シフト・レジスタ１６１０のシフト動作を制御する。ワイヤードＯＲ回路１９１３の出力は、信号線１９３５に結合されており、この信号線は、プリチャージ（ＰＣ）回路１９１８とインバータ１９１９の入力に結合されている。インバータ１９１９の出力は、ＡＮＤゲート１９０５の入力に結合されている。他の実施形態では、ＢＦＲ １６０８に格納されているＦＤＡＴＡを補完し、インバータ１９１９を省いてもかまわない。

シフト・レジスタ１９１６は、ＣＬＫのクロック毎に、「１」をそのビット位置にシフトさせる。ＡＮＤゲート１９３０の出力は、プルダウン・トランジスタ１９３１のゲートに結合されており、信号線１９３５は低レベルにプルダウンされ、ＢＦＲ １９０８のそれぞれの対応するビット位置およびシフト・レジスタ１９１６が「１」の場合にシフト・レジスタ１６１０はイネーブルされシフトできる。このようにして、シフト・レジスタ１９１６とＢＦＲ １９０８に格納されているＦＤＡＴＡにより、ワイヤードＯＲ回路１９１３に入力されるデータのうちどれが、所与のどのクロック・サイクルでシフト・レジスタ１６１０をクロックするかを判別する。

図１９は、ＢＦＲ １５０８を、フィルタ・マスク・ビット・パターンＦＤＡＴＡを格納する行が複数ある単一列ランダム・アクセス・メモリ（ＲＡＭ）２００２としても実装できることを示している。ＳＲＡＭ内の目的のビット位置にアクセスするには、復号化された行アドレスを入力する（例えば、図１４のアドレス・ジェネレータ１２０６から）。センス・アンプ（Ｓ／Ａ）２００４は、ＲＡＭの行に結合されており、アクセスされたビット位置に格納されているデータ値を出力する。例えば、センス・アンプ２００４の出力は、例えば、ＡＮＤゲート１６０５の入力に結合させることができる。ＲＡＭ ２００２は当業では知られており、したがって、本明細書では詳細を説明しない。図１２に関して説明したカウンタ１３０２やデコーダ１３０４などのカウンタやデコーダを使用して、または例えば、図１３のシフト・レジスタ１４０２を使用する他の手段により、ＲＡＭ ２００２の行のそれぞれを順次処理することができる。

上述のように、クロスバ・スイッチ４３０は、完全なクロスバ・スイッチ（例えば、図９に示されているように）でもよいし、あるいは接続を確立するために必要な相互接続のみを使用するように修正することもできる。出力ストリングの上位ビット位置から下位ビット位置へ入力データをフィルタ処理し圧縮するようにクロスバ・スイッチ４３０をプログラムする図１１〜１９に示されているデータ・プログラム回路１２０４の実施形態については、図２０に示されているように、図９のクロスバ・スイッチ１０００の一部だけあればよい。図２０は、修正されたクロスバ・スイッチの４つの行と４つの列しか示していないが、行と列はいくつでも使用できる。さらに、図２０は、メモリ記憶素子１０１０の各行はワード線（ＷＬ）に結合されており、それらの素子によりＤ（０）〜Ｄ（３）として表されている１つまたは複数のビット線上でデータを伝送することができることを示している。ビット線のそれぞれが、プログラム・データＰＤＡＴＡの１ビットを伝送する。

図２１は、図１１のプログラミング回路４４０の他の実施形態であるプログラミング回路２００４の図である。この実施形態では、プログラミング回路２００４は、図１４のアドレス・ジェネレータ２１１０とプログラム・データ・ジェネレータ１５０２を備える。アドレス・ジェネレータ２１１０は、カウンタ２１１２、デコーダ２１１４、ＯＲ論理回路２１１６を備える。プログラム時に、アドレス・ジェネレータ２１１０は、条件付きで、クロスバ・スイッチ４３０の行を順次巡り、ＢＦＲ １５０８に格納されているＦＤＡＴＡに基づいて接続をプログラムする。例えば、特定のＦＤＡＴＡビットが、クロスバ・スイッチ４３０内の選択された行について接続を確立することを示している場合、データ・ジェネレータ１５０６は、少なくとも１つの信号をバッファ書き込み回路と論理「１」状態であるＯＲ論理回路２１１６に出力する。それに対する応答として、ＯＲ論理回路２１１６は、インクリメント信号ＩＮＣを適切な論理状態にアサートし、カウンタ２１１２はクロック信号ＣＬＫへの応答としてカウントを更新する。カウンタの出力は、クロスバ・スイッチ４３０内の新しい行を選択するように、デコーダ２１１４により復号化される。他の実施形態では、インクリメント信号はカウンタ２１１２を減分するデクリメント信号であってもよい。他の実施形態では、カウンタ２１１２とデコーダ２１１４は、ＩＮＣが適切な論理状態にアサートされ、ＣＬＫがトグルされたときに行を１つ選択するように更新されるシフト・レジスタで置き換えることもできる。

図２２は、図２１のデータ・ジェネレータ１５０６の一実施形態であるデータ・ジェネレータ２２０２の図である。データ・ジェネレータ２２０２は、シフト・レジスタ２２０４とＡＮＤゲート２２０６（０）〜２２０６（ｎ−１）を備える。各ＡＮＤゲート２２０６（０）〜２２０６（ｎ−１）は、シフト・レジスタ２２０４とＢＦＲ １５０８から対応するビットを受け取り、信号線２２０８（０）〜２２０８（ｎ−１）上に複数のＰＤＡＴＡ信号を生成するように結合されている。ＰＤＡＴＡ信号は、バッファ書き込み回路１５０４とＯＲ論理回路２１１６に供給される。

この実施形態では、論理「１」状態は、シフト・レジスタ２２０４のビット位置の端から端までシフトされ、ＡＮＤゲート２２０６（０）〜２２０６（ｎ−１）によりＢＦＲ １５０８内の対応するＦＤＡＴＡビットとの論理ＡＮＤがとられる。ＦＤＡＴＡビットが論理「１」状態で、シフト・レジスタ２２０４内の対応するビットも論理「１」状態の場合、対応するＡＮＤゲート２２０６はＰＤＡＴＡ信号を生成し、クロスバ・スイッチ４３０内の対応する行と列の相互接続を選択し、プログラムする。選択された行の他のすべての列はプログラムされないか、または接続を確立しないように論理「０」状態にプログラムされる。さらに、ＡＮＤゲート２２０６の１つが論理「１」状態のＰＤＡＴＡ信号を出力した場合、ＯＲ論理回路２１１６により、次のクロック・サイクルで次の行が選択され、プログラミングのための新しい行に順次進む。

上述のように、クロスバ・スイッチ４３０は、完全なクロスバ・スイッチ（例えば、図９に示されているように）でもよいし、あるいは接続を確立するために必要な相互接続のみを使用するように修正することもできる。出力ストリングの上位ビット位置から下位ビット位置へ入力データをフィルタ処理し圧縮するようにクロスバ・スイッチ４３０をプログラムする図２１と２２に示されているデータ・プログラム回路１５０４の実施形態については、図２３に示されているように、図９のクロスバ・スイッチ１０００の一部だけあればよい。図２３は、修正されたクロスバ・スイッチの４つの行と４つの列しか示していないが、行と列はいくつでも使用できる。さらに、図２２３０は、メモリ記憶素子１０１０の各行はワード線（ＷＬ）に結合されており、それらの素子によりＤ（０）〜Ｄ（３）として表されている１つまたは複数のビット線上でデータを伝送することができることを示している。ビット線のそれぞれが、プログラム・データＰＤＡＴＡの１ビットを伝送する。

本明細書の本発明は特定の実施例を参照しながら説明されている。しかし、付属の請求項で定められているように、本発明の広い精神と範囲を逸脱することなく本発明にさまざまな修正と変更を加えられることは明白であろう。したがって、明細書と図面は、制限ではなく、説明することを目的としているものとみなすべきである。

ルータによるパケット処理を概念的に示す図である。 ＣＡＭデバイスの一実施形態の図である。 同時ルックアップを実行するように構成されているＣＡＭデバイスを備えるルータのライン・カードまたはブレードの一実施形態の図である。 入力ストリング・フィルタ処理回路を備える複数ブロックＣＡＭデバイスの一実施形態の図である。 複数ブロックＣＡＭデバイスのフィルタ処理回路の一実施形態の図である。 入力ストリングの一実施形態の図である。 図５Ａの入力ストリングからの特定のパケット・ヘッダ・セグメントを使用するＣＡＭデバイスのオペレーションを概念的に示す図である。 入力ストリングのフィルタ処理と圧縮の一実施形態を概念的に示す図である。 入力ストリングのフィルタ処理と圧縮のビット操作の一実施形態を概念的に示す図である。 入力ストリングをフィルタ処理し、圧縮されるようにフィルタ回路をプログラムする一方法を示す図である。 クロスバ・スイッチの一実施形態の図である。 図９のクロスバ・スイッチのメモリ記憶素子の一実施形態の図である。 フィルタ回路の一実施形態の図である。 図１１のアドレス・ジェネレータの一実施形態の図である。 図１１のアドレス・ジェネレータの他の実施形態の図である。 フィルタ回路の他の実施形態の図である。 ブロック・フィルタ・レジスタに結合されているデータ・ジェネレータの一実施形態の図である。 図１５の実施形態の使用例を示す図である。 ブロック・フィルタ・レジスタ内のビット・パターン例に基づくクロスバ・スイッチの１０個のマトリックス接続を示す図である。 ブロック・フィルタ・レジスタに結合されているデータ・ジェネレータの他の実施形態の図である。 センス・アンプに結合されているブロック・フィルタ・レジスタの一実施形態の図である。 クロスバ・スイッチの一実施形態の図である。 フィルタ回路の他の実施形態の図である。 ＯＲ論理回路とブロック・フィルタ・レジスタに結合されている図２１のデータ・ジェネレータの一実施形態の図である。 クロスバ・スイッチの他の実施形態の図である。

Claims (14)

1. 複数の内容アドレス・メモリ・ブロックと、
   複数のフィルタ回路とを備え、複数のフィルタ回路はそれぞれ、複数の内容アドレス・メモリ・ブロックのうちの対応する１つに結合され、複数のフィルタ回路はそれぞれ、共通入力ストリングを受信し、フィルタ処理されたコンパランド・ストリングを複数の内容アドレス・メモリ・ブロックのうちの対応する１つに送信するように構成されており、その複数のフィルタ回路はそれぞれ、共通入力ストリングを受信するように構成されているクロスバ・スイッチを備え、さらに、複数のフィルタ回路はそれぞれクロスバ・スイッチに結合されたプログラミング回路を備え、プログラミング回路は、フィルタ・データを受信して、共通入力ストリングからフィルタ処理されたコンパランド・ストリングを生成するようにクロスバ・スイッチをプログラムする構成とされている装置。
2. 複数の内容アドレス・メモリ・ブロックは、同時ルックアップを実行するように構成されている請求項１に記載の装置。
3. プログラミング回路は、
   クロスバ・スイッチに結合されたデータ・ジェネレータと、
   データ・ジェネレータに結合され、フィルタ・データを格納するブロック・フィルタ・レジスタと、
   クロスバ・スイッチに結合されたアドレス・ジェネレータとを備える請求項１に記載の装置。
4. データ・ジェネレータは、
   ブロック・フィルタ・レジスタに結合されたシフト・レジスタと、
   シフト・レジスタに結合された論理回路とを備える請求項３に記載の装置。
5. シフト・レジスタは複数のビット位置を持ち、シフト・レジスタは、フィルタとクロック信号に基づき複数のビット位置を通じて所定のビット値をシフトするように構成されている請求項４に記載の装置。
6. 論理回路は、シフト・レジスタの複数のビット位置からビット値を受け取り、クロック信号に基づきビット値を出力するように構成されている請求項５に記載の装置。
7. データ・ジェネレータは、
   第１のシフト・レジスタと、
   複数のビット位置を持つ第２のシフト・レジスタと、
   第１のシフト・レジスタに結合され、フィルタ・データを受け取るためブロック・フィルタ・レジスタに結合され、第２のシフト・レジスタを通じて所定のビット値のシフト動作を制御するため第２のシフト・レジスタに結合され、その第２のシフト・レジスタがフィルタ・データとクロック信号に基づき複数のビット位置を通じて所定のビット値をシフトするように構成されているワイヤード論理ゲートと、
   第２のシフト・レジスタの出力を受け取り、その出力をバッファ書き込み回路に送るように結合されている論理回路とを備える請求項３に記載の装置。
8. ブロック・フィルタ・レジスタは、複数行、単一列のランダム・アクセス・メモリである請求項３に記載の装置。
9. アドレス・ジェネレータが、
   制御入力とカウンタ出力を備えるカウンタと、
   カウンタの出力とクロスバ・スイッチに結合されたデコーダとを備える請求項３に記載の装置。
10. さらに、出力がカウンタの制御入力に結合され、複数の入力がデータ・ジェネレータに結合されているＯＲ回路を備える請求項９に記載の装置。
11. アドレス・ジェネレータはシフト・レジスタを備える請求項３に記載の装置。
12. さらに、アドレス・ジェネレータは、出力がシフト・レジスタに結合され、複数の入力がデータ・ジェネレータに結合されているＯＲ回路を備える請求項１１に記載の装置。
13. 複数の内容アドレス・メモリ・ブロックと、
    複数のフィルタ回路とを備え、複数のフィルタ回路はそれぞれ、複数の内容アドレス・メモリ・ブロックのうちの対応する１つに結合され、複数のフィルタ回路はそれぞれ、共通入力ストリングを受信し、フィルタ処理されたコンパランド・ストリングを複数の内容アドレス・メモリ・ブロックのうちの対応する１つに送信するように構成されており、複数のフィルタ回路はそれぞれ、
    共通入力ストリングを受け取るように構成されているクロスバ・スイッチと、
    クロスバ・スイッチに結合されたプログラミング回路とを備え、そのプログラミング回路は、フィルタ・データを受け取って、共通入力ストリングからフィルタ処理されたコンパランド・ストリングを生成するようにクロスバ・スイッチをプログラムする構成であり、プログラミング回路は、
    クロスバ・スイッチに結合されたバッファ書き込み回路と、
    バッファ書き込み回路に結合されたデータ・ジェネレータと、
    データ・ジェネレータに結合され、クロスバ・スイッチ内の接続を確立するためにビット・データ・パターンを格納するブロック・フィルタ・レジスタと、
    クロスバ・スイッチに結合されたアドレス・ジェネレータとを備え、アドレス・ジェネレータは、
    制御入力とカウンタ出力を備えるカウンタと、
    カウンタの出力とクロスバ・スイッチに結合されたデコーダと、
    出力がカウンタの制御入力に結合され、複数の入力がデータ・ジェネレータに結合されているＯＲ回路とを備える装置。
14. 複数のフィルタ回路がプログラム可能である請求項１３に記載の装置。

Images