(57)【要約】検索データに対し、最も長く一致した単語を見つけ出す、コンテントアドレサブルメモリであって、データの単語は、それぞれのメモリ・セルに格納され、前記データの単語は、あらかじめ定められた順序にならべられたサブワードの集団から構成され、それぞれのサブワードは、メモリの少なくとも１つのビットから構成され、それらのそれぞれの単語（データの単語）の連続してならべられたサブワードの内で同じ位置であるすべてのサブワードは、横断線に関連付けられたコンテントアドレサブルメモリに適用される方法および回路であって、ａ）検索データと一致する１番目のサブワードに、スティルマッチシグナルをセットし、ｂ）あらかじめ定められた順序における、同じ単語内のすべてのサブワードに対して、すべての先行するマッチシグナルが、セットされる場合に、サブワードに対してスティルマッチシグナルをセットし、前記スティルマッチシグナルは、関連付けられたサブワードが一致していることを示す信号（サブワードマッチシグナル）と、あらかじめ定められた順序内でのすべての先行するスティルマッチシグナルとの論理積の組み合わせであり、ｃ）前記横断線が、関連付けられたいずれかのサブワードに対して、続けて一致していること（スティルマッチ）がセットされる場合、横断線を論理１にセットし、ｄ）ｉ）サブワードのスティルマッチシグナルが、セットされているｉｉ）単語内の次のサブワードの桁位置では、横断線がセットされていない、という条件を満たす場合に、単語内の連続して一致している最後のサブワードで、もっとも長い一致であることを示す信号（最長一致信号）をセットし、ｅ）前記単語のいずれかのサブワードに、いずれかの最長一致信号がセットされている場合に、単語が一致していることを示す信号（単語一致信号）をセットする方法および回路。
2004526272.tif 000002
【特許請求の範囲】
【請求項１】
検索データに対し、最も長く一致した単語を見つけ出す、コンテントアドレサブルメモリに実装される回路であって、
それぞれのメモリ・セルが、データの単語を格納することができ、
前記単語は、あらかじめ定められた順序にならべられた、サブワードの集団から構成され、
それぞれのサブワードは、記憶回路とコンパレータ回路を備え、
それぞれのサブワードは、メモリの少なくとも１つのビットから構成され、
それぞれのサブワードは、前記サブワードで一致していることを示す信号（マッチシグナル）のすべてについて論理積関数を実行する第一の回路によって、前記あらかじめ定められた順序において前記サブワードに先行するすべてのサブワードと一緒に、続けて一致していることを示す線（スティルマッチライン）に接続され、
すべての続けて一致していることを示す信号（スティルマッチシグナル）は、それぞれの単語の前記あらかじめ定められた順序にならぶサブワードの中で同じ桁位置のすべてのサブワードから、前記論理関数の実行結果として導き出され、第一の広域論理和回路を介して前記横断線に接続され、
それぞれのサブワードの位置で、第二の論理積回路が、前記スティルマッチシグナルと、次のサブワードに関連付けられる横断線の反転信号を接続し、
一つの単語内のすべてのサブワードに対する、前記第二の論理積回路の出力のすべてが、第二の広域論理和回路に接続されていることにより、与えられたメモリの単語が、接続して一致しているサブワードの数が最大である場合に、単語一致信号（ワードマッチシグナル）を出力する回路。
【請求項２】
前記第一の論理積回路は、連続した複数の論理積ゲートによって、実装され、一つの論理積ゲートが、それぞれのサブワードに各自関連付けられ、
前記論理積ゲートは、前記サブワードのマッチシグナルと、先行するサブワードについて、スティルマッチシグナルとをインプットとして受け入れる、請求項１に記載の回路。
【請求項３】
ＶＬＳＩ装置に実装され、
少なくとも１つ以上の論理積回路が、あらかじめ充電されたライン、あるいはあらかじめ放電されたラインを、それぞれ放電する、あるいは充電する、複数の直列トランジスタを有する、請求項１に記載の回路。
【請求項４】
ＶＬＳＩ装置に実装され、
少なくとも１つ以上の論理和回路が、あらかじめ充電されたライン、あるいはあらかじめ放電されたラインについて、それぞれ放電する、あるいは充電する、複数の並列トランジスタを有する、請求項１に記載の回路。
【請求項５】
クロック信号が、複数の実行サイクルを同期させるために用いられる、請求項１、請求項３あるいは請求項４のいずれかに記載の回路。
【請求項６】
検索データに対し、最も長く一致した単語を見つけ出す、コンテントアドレサブルメモリであって、
データの単語は、それぞれのメモリ・セルに格納され、
前記データの単語は、あらかじめ定められた順序にならべられたサブワードの集団から構成され、
それぞれのサブワードは、メモリの少なくとも１つのビットから構成され、
それらのそれぞれの単語（データの単語）の連続してならべられたサブワードの内で同じ位置であるすべてのサブワードは、横断線に関連付けられたコンテントアドレサブルメモリに適用される方法であって、
ａ）検索データと一致する１番目のサブワードに、スティルマッチシグナルをセットし、
ｂ）あらかじめ定められた順序における、同じ単語内のすべてのサブワードに対して、すべての先行するマッチシグナルが、セットされる場合に、サブワードに対してスティルマッチシグナルをセットし、
前記スティルマッチシグナルは、関連付けられたサブワードが一致していることを示す信号（サブワードマッチシグナル）と、あらかじめ定められた順序内でのすべての先行するスティルマッチシグナルとの論理積の組み合わせであり、
ｃ）前記横断線が、関連付けられたいずれかのサブワードに対して、続けて一致していること（スティルマッチ）がセットされる場合、横断線を論理１にセットし、
ｄ）
ｉ）サブワードのスティルマッチシグナルが、セットされている
ｉｉ）単語内の次のサブワードの桁位置では、横断線がセットされていない、という条件を満たす場合に、単語内の連続して一致している最後のサブワードで、もっとも長い一致であることを示す信号（最長一致信号）をセットし、
ｅ）前記単語のいずれかのサブワードに、いずれかの最長一致信号がセットされている場合に、単語が一致していることを示す信号（単語一致信号）をセットする方法。
【請求項７】
前記コンテントアドレサブルメモリが、セットされる横断線の数に応じて、最長一致の長さを登録し、最長一致を超えたビットをマスキングした状態で、正確な検索が、共通するタイプの第二のコンテントアドレサブルメモリを用いて行うことができる、請求項６に記載の方法。
【請求項８】
前記コンテントアドレサブルメモリが、セットされている横断線の数に応じて、最長一致の長さを登録し、正確な検索が、共通のＣＡＭあるいはＣＯＭのモードで動作する、同じＣＡＭあるいは、ＣＯＭを用いて行うことができる、請求項６に記載の方法。
【請求項９】
複数のデータ単語を有するメモリ内のスティルマッチシグナルであって、
それぞれのデータ単語は、あらかじめ定められた順序のサブワードの集団をそなえ、
前記スティルマッチシグナルは、前記サブワードのそれぞれに、各自別々にセットされ、
同じデータ単語のすべての先行するサブワードの、すべての先行するスティルマッチシグナルが、前記あらかじめ定められた順序により、セットされている場合に、前記スティルマッチシグナルは、セットされ、
それぞれのスティルマッチシグナルは、関連付けられたサブワードマッチシグナルとあらかじめ定められた順序内の先行するスティルマッチシグナルの論理積機能の出力である、スティルマッチシグナル。
【請求項１０】
複数のデータ単語を有するコンテントアドレサブルメモリ内の、横断線のセットであって、
それぞれのデータ単語は、サブワード集団をそなえ、
前記サブワードは、あらかじめ定められた順序内の、可能な位置の連続したならびを占め、
前記横断線のひとつが、前記単語のそれぞれの内で、サブワードの前記可能な位置のそれぞれに、各自関連付けられ、
前記横断線と前記サブワード自身とに関連付けられた、サブワードの位置より先行する前記データ単語のひとつの中で、すべてのサブワードが検索された情報と一致している場合、横断線がセットされる横断線のセット。
【請求項１１】
複数のデータ単語を有するメモリ内での、最長一致信号であって、
それぞれのデータ単語は、あらかじめ定められた順序のサブワードの集団をそなえ、
前記最長一致信号は、別々にそれぞれの前記サブワードに、各自関連付けられ、
前記最長一致信号が、
ａ）前記スティルマッチシグナルが、前記単語のサブワードに対してセットされており、
ｂ）前記単語内の次のサブワードの桁位置では、前記横断線がセットされていない
場合に、データ単語に対して、セットされる信号。
【請求項１２】
複数のデータ単語を有するメモリ内での単語一致ラインのセットであって、
それぞれのデータ単語は、あらかじめ定められた順序のサブワードの集団をそなえ、
一つの単語一致信号は、別々にそれぞれの前記サブワードに、各自関連付けられ、
前記最長一致信号が、
ａ）前記スティルマッチシグナルが、前記単語のサブワードに対してセットされており、
ｂ）前記単語内の次のサブワードの桁位置では、前記横断線がセットされていない
場合に、データ単語に対して、前記最長一致信号がセットされるデータ単語。
【発明の詳細な説明】
【技術分野】
【０００１】
ワールドワイドウェブを一例とした、通信システムにおいて、大量のメッセージ（パケット）が、送信されている。それぞれのメッセージは、あて先アドレスを含んでおり、ルーティングシステムによって、そのあて先に基づき、ルーティングされる必要がある。あて先アドレスは、固定長の単語の中に格納される。共通のプレフィクスを持つアドレスの集団は、通常共通のドメインに割り当てられているので、同じルーティングを必要とする。しかしながら、これらのドメインアドレスは、異なる長さである場合がある。ルーティングシステムは、通常数多くのドメインプレフィクスのテーブルをメモリに有し、入ってくるメッセージの持つアドレスが、与えられたドメインに所属しているかどうかのチェックのための検索を実行する。そのアドレスを発見した場合、ルーティング情報が、関連のあるルーティングテーブルから抜き出される。ルーティングシステムは、大量のメッセージを、高速で振り分けなければならないため、保有するルーティングテーブルのプレフィクスに一致する、アドレスの最長プレフィクスを見つけるための高速稼動するシステムを設計することが好ましく、
背景技術として、ＰＣＴ／ＷＯ７０／８３２Ａ１において、経済的で速いことを目的とした、最長プレフィクス検索システムが開示されている。
【０００２】
従来のルーティングシステムにおいて、様々なアルゴリズムが、いくつものメモリ検索サイクルを使って、最長プレフィクス検索を達成している。多くのルーティングシステムにおいて、所定の長さを持つプレフィクスを検索するためにコンテントアドレサブルメモリが用いられ、最長一致が見つかるまで、ソフトウェアおよびハードウェア上で、異なる長さを用い、何度も繰り返し検索が行われている。そのようなシステムの例は、米国特許第６０６７５７４号（ＵＳ６０６７５７４）、米国特許第５９８３２２３号（ＵＳ５９８３２２３），米国特許第６０５２６８３号（ＵＳ６０５２６８３）に記載されている。
【０００３】
コンテントアドレサブルメモリ配列において、その配列の全メモリ・セルの中で、連続して一致するビットの最大数を持つデータ単語を有するメモリ・セルの位置を高速に見つける手段を提供することが好ましい。単一メモリ・サイクルにおいて、そのような「最長一致検索」の実行を可能にすることができることが、より好ましい。電子回路により、電子的スピードで「最長一致検索」を実現することは、有益である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ここに記載するメモリ・システムの目的は、コンテントアドレサブルメモリ配列において、その配列の全メモリ・セルの中で、連続して一致するビットの最大数を持つデータの１単語を有する一つのメモリ・セルの位置を高速に見つける手段を提供することである。最長一致検索は、以下のような方法を用い、電子的回路機構のみによって行われ、単一メモリ・サイクルにおいても行うことができる。
【０００５】
それぞれのデータ単語は、あらかじめ定義付けられた順序に並べられたサブワードの集団を含み、
与えられるサブワードＢｉ，ｊのサブワード一致信号Ｍｉ，ｊは、そのサブワードのコンパレータの出力に基づいてセットされる。
【０００６】
単語Ｗｉの連続して一致しているサブワードは、それぞれのサブワードにおいて個々に生成される「スティルマッチ」信号によって検出される。
【０００７】
この場合、「スティルマッチ」信号に、「一致」信号として同じ信号がセットされる、その単語の第一のサブワードを除き、サブワードの「一致」出力の各々は、論理積ゲートによって、同じ単語における先行サブワードの「スティルマッチ」信号と結合される。
【０００８】
現在のサブワードに先行する全サブワードが一致データを含む場合、スティルマッチ信号はセットされ（論理１）、これにより、少なくとも第一のサブワードが一致するワードのそれぞれについて、セットされた信号の「一致の連鎖」が得られる。
【０００９】
そして、最長一致は、最長一致連鎖を発見することにより発見される。
【００１０】
最長一致の連鎖の長さを見つけるタスクは、次に示す方法で、実現することができる。
【００１１】
最初の位置を除き、それぞれのサブワードの可能な位置に対し、横断線が結び付けられている。メモリ配列全ての単語の中で、少なくとも「スティルマッチ」信号の一つが、論理１にセットされている場合に限り、それぞれの横断線は、論理１にセットされる。これは、与えられたサブワードの位置に対する、すべての単語の全てのスティルマッチ信号の論理和の組み合わせによって行われる。
【００１２】
これにより、それぞれの単語は、横断線の上に一致連鎖の最後の長さを印付ける。
【００１３】
最終的に、最も高い桁位置で、論理１にセットされた線は、最長一致連鎖の長さを示す。
【００１４】
最長一致連鎖の最後の、サブワードはサブワードに関連付けられた横断線の信号と、次の横断線の信号とを論理ゲートにおいて結合することにより、検出される。これにより、最初の横断線の信号がセットされ、次の横断線の信号がセットされない場合に、最長一致信号が得られる。
【００１５】
スティルマッチ信号が、単語の最後のサブワードに対してセットされる箇所が、明らかに最長一致連鎖である。それゆえ、最後のサブワードに対しては、最長一致信号は、スティルマッチ信号と一致してセットされる。
【００１６】
最終的に、単語一致信号は、最長長さの持つ一致連鎖が発見された箇所で、それぞれの単語に対して有効にされる。これは、広域論理和ゲートにより、単語に対するすべての最長一致信号を集めることによって、行われる。
【００１７】
標準的なＣＡＭの場合、メモリのいくつかの単語は、単語一致信号を有効にし、それぞれのうち一つが、最長一致状態を満たしている。しかしながら、ＣＡＭあるいはＣＯＭは、１セルのアドレスのみを出力用に、選択する為に、優先エンコーダまたは、優先マスクを含むことがある。その選択は特定の種類のＣＡＭあるいはＣＯＭの優先システムによって行われる。そのような優先マスクは、ＰＣＴ／ＩＬ００／００１２１に詳細が記載されている。
【００１８】
本発明は、情報通信システムにおいて、例えばデータベースやデータ圧縮システムなどの他のシステムに劣らず、有益に使用されることができる。
【発明を実施するための最良の形態】
【００１９】
本発明は、単一検索サイクルにおいて最長一致単語を見つけるために、コンテントアドレサブルメモリ（ＣＡＭ）とコールアウトメモリ（ＣＯＭ）において結合されうるシステムと電子回路とに関連する。本発明の原理は、セットされた横断線の数によって最長一致の大きさを記録するＣＡＭまたはＣＯＭを設計するためにも用いることができる。このようなＣＡＭにおいて、最長一致の大きさがわかった後で、最長一致を超えるビットをマスキングした状態で、共通するタイプの２番目のＣＡＭまたはＣＯＭを用いて、あるいは、共通のＣＡＭまたはＣＯＭモードで動作する同じＣＡＭまたはＣＯＭを用いて、正確な検索が行われる。
【００２０】
ＣＡＭ、ＣＯＭあるいは、他の関係するメモリにおいて、コンパレータは、それぞれのメモリ・セルに設けられ、メモリ装置に与えられる参照データを用いて、メモリ・セルの中身の一致を見つける。一つのメモリ・セルの中身が、参照データ（一致セル）との所定の関係である場合は必ず、コンパレータは論理信号を出力する。そのとき、この論理信号は、特定のＣＡＭあるいはＣＯＭの優先システムによって、一致しているセルの一つの位置を出力するシステムを有効にする。
【００２１】
本発明によるメモリ・システムの目的は、コンテントアドレサブルメモリ配列において、一つのメモリ・セルの位置を電子的速度で見つける手段を提供することである。前記メモリ・セルは、その配列のすべてのメモリ・セルの中で、連続して一致するビット数が最大となるデータの１単語を格納する。本発明によれば、そのような最長一致検索が、電子回路だけで行われ、単一メモリ・サイクルにおいて行うことができる。
【００２２】
本発明は、情報通信システムにおいて、例えばデータベースやデータ圧縮システムなどの他のシステムに劣らず、有益に使用されることができる。
【００２３】
特定のアプリケーションの場合は、ビットは、集団（サブワード）に割り当てられ、最長一致機能が、これらのサブワードに適用されることもある。このような場合における、連続して一致するサブワードの最長連鎖を持つデータの単語として、最長一致単語について説明する。そのようなアプリケーションの例としては、最長一致は、テキスト文字列のテーブルにおいて検索され、文字列のそれぞれの文字が、８ビット単語を形成している。
【００２４】
本発明は、ＣＡＭにおいて結合されるシステムに関するため、まず図面に関して、典型的なＣＡＭの一般的な記述をする。図面は、直線的幾何学線を用いた電子回路の概要の表現であり、これらの回路の現実の形状は、図面と一致することに限定されない。
【００２５】
図１において、一般的に使用されるコンテントアドレサブルメモリが示されている。Ｗ１からＷｎまで、それぞれのデータの１単語を格納することができる多数のメモリ・セルが、アドレス・デコーダを通じて、アドレス・バスに接続されており、複数のビット・ラインにより、データ・バスに接続されている。
【００２６】
ＣＡＭには、２つの実行モードがある。
【００２７】
第一に、読み／書きモードがあり、データはメモリ・セルに書き込まれたり、メモリ・セルから、取り出されたりすることもできる。
【００２８】
第二に、データがデータ・バスに供給され、メモリが、一致したデータを格納しているメモリ・セルのアドレスを返すＣＡＭモードがある。このために、それぞれのメモリ・セルは、コンパレータ回路も含んでいる。システムが、ＣＡＭモードであるとき、そのコンパレータは、あらかじめ定義された関係が、単語に格納されたデータとデータ・バスに供給されたデータとの間で、確認された場合、単語一致信号を出力する。１つまたはそれ以上の単語が、単語一致信号を出力した場合、優先システムあるいは優先回路が、ただ１単語のみのアドレスを出力用に、選択するために用いられる。その選択は、ＣＡＭによって定義された特定のルールによって行われる。
【００２９】
図１は、コンテントアドレサブルメモリの１種類を示しているが、ここに示すように本発明の回路が適用されうるＣＡＭの構成には多くのバリエーションがある。発明の原理の実施は、メモリ構成の種類に依存せず、本発明の回路は、ＣＡＭあるいはＣＯＭの様々な種類において、結合されることができる。
【００３０】
図２に、従来の技術のコンテントアドレサブルメモリにおける単語一致信号の発生が示されている。この例では、一つのメモリ・セルは、データの単語Ｗｎを格納し、その単語は、ｗ個のサブワード（Ｂｉ，１・・・Ｂｉ，ｊ・・・Ｂｉ，ｗ）から構成されている。典型的に、それぞれのサブワードは、１ビットあるいは多数のビットから構成されている。
【００３１】
サブワードＢｉｊそれぞれに、コンパレータが関連付けられている。コンパレータは、サブワードに格納されたデータと、ビット・ラインにセットされたデータとを比較し、あらかじめ定義された関係が、確認されたときには、サブワード一致信号をセットする。典型的に、前記の関係は単にこれらのデータが等しいことであるが、どのような関係の種類でも、予測されうる。
【００３２】
単語のすべてのサブワード一致信号は、単語一致信号を形成するために、論理積ゲートに入力される。単語一致信号は、すべてのサブワードが一致していることが分かったときに、このように論理１にセットされる
そのようなシステムにおいて、単語一致信号を有効にするために、すべてのサブワードが一致していなければならない。
【００３３】
本発明の目的は、たとえ全てのサブワードが一致しないとしても、新しい条件により単語一致信号を有効にするシステムを提案することである。この新しい条件は、一番目のサブワードから始まる連続して一致するサブワードの数が、検索されたメモリに格納された全ての単語の中で最も高い場合に、単語一致信号を有効にすることである。この条件を、最長一致条件と称する。
【００３４】
図３および図４は、この新しい条件の実施のために、より好ましい形態を示している。メモリの単語の配列が示され、それぞれの単語Ｗｉは、ｗ個のサブワードＢｉ，ｊ（Ｂｉ，１〜Ｂｉ，ｗ）から構成されている。図３において、Ｗ１，Ｗ２，Ｗｗの３つの単語が示されており、それぞれの単語は、それぞれに３つのサブワードが１，２、ｗの位置で示されている。
【００３５】
Ｂｉ，ｊという表記は、位置Ｊにおける単語Ｗｉのサブワードを表現するために使用されており、各サブワードＢｉ，ｊにそれぞれ関連付けられた回路が図４に示されている。
【００３６】
それぞれのサブワードＢｉ，ｊは、所定のサイズのデジタルデータを格納することができるメモリの要素である。図４によれば、また図２を参照して上述したように、それぞれのサブワードＢｉ，ｊは、コンパレータも有している。前記コンパレータは、サブワードデータとビット・ラインにセットされたデータとが、所定の関係にある場合、一致信号を出力する。格納と取り出しの手段は公知であるので、メモリの構成要素の詳細は、ここには示さない。上述のとおり、メモリの構成要素は、読み込み／書き込み用のメモリ・セルのアドレスを指定する、手段を提供する。それぞれのサブワードは、ビット・ラインによってメモリに提供されたデータと、サブワードに格納されたデータとを比較するために、コンパレータをさらに有している。いくつかの単語一致信号が有効にされた場合に、優先エンコーダ回路（図示せず）は、唯一つのセルを選択するために用いられ、そのアドレスを出力する。そのような、優先エンコーダ回路あるいは、優先マスク回路は、ＰＣＴ／ＩＬ  ００／００１２１に記載されている。
【００３７】
図４によれば、所定のサブワードＢｉｊのサブワード一致信号Ｍｉ，ｊがそのサブワードのコンパレータの出力に応じて、セットされる。
【００３８】
１番目のサブワードＢｉ，１から始まる単語Ｗｉの連続して一致するサブワードを検出するために、「スティルマッチ」信号ＳＭｉ，ｊがそれぞれのサブワードに割り当てられる。
【００３９】
サブワードＢｉ，ｊのそれぞれの「一致」出力Ｍｉ，ｊは、論理積ゲートによって同じ単語の１つ前のサブワードの「スティルマッチ」信号ＳＭｉ，ｊ−１と結合される。単語Ｗｉの第一のサブワードＢｉ，１は例外であり、ＳＭｉ，１は、Ｍｉ，ｊとして同じ信号にセットされるだけである。
【００４０】
全てのサブワードＢｊ，ｋ（ｋ≦ｊ）が一致するデータを含んでいる場合、スティルマッチ信号ＳＭｉ，ｊが、論理１にセットされる。少なくとも１番目のサブワードが一致しているそれぞれの単語に対して、セットされたスティルマッチ信号ＳＭｉｊの連鎖が得られる。その連鎖を一致連鎖と呼び、最長一致を見つけるタスクは、最長一致連鎖を見つけることによって行われる。
【００４１】
図３および図４に示すような一致連鎖を形成する論理回路構成は、より好ましい実施例の一例であり、他の論理ゲートの組み合わせは、同じ結果を達成するために用いられる。例えば、すべてのサブワードＢｊ，ｋが、データと一致していることを確かめるために、すべての先行するＭｊ，ｋ（ｋ≦ｊ）を集める、広域論理積ゲートを使用することができる。そのような論理ゲートの組み合わせあるいは追加は、例えばシステムのレスポンスを短くするために用いられる。これらの組み合わせにおいて、Ｍｉ，ｋの同じ論理的機能、すなわちサブワードＢｉ，ｋ（ｋ≦ｊ）のすべての連鎖がデータと一致している場合にのみ、ＳＭｉ，ｊ信号はセットするという機能が得られる。
【００４２】
図３に示すように、最長一致連鎖の長さを発見するタスクは、次のように行われる。
【００４３】
それぞれのサブワードのそれぞれの可能な位置ｊへ、１番目の位置を除いて、横断線Ｔｊが関連付けられる。このように、合計でｗ−１個の横断線が、Ｔ２からＴｗまで、定義づけられる。位置ｊにおけるすべてのサブワードの中で、その位置ｊにおける少なくとも１つのサブワードがスティルマッチ信号ＳＭｉ，ｊを生成する場合に限り、それぞれの横断線Ｔｊは、論理１にセットされる。これは、与えられたサブワード位置ｊに対する、すべての単語ＷｉのすべてのＳＭｉ，ｊ信号の論理和組み合わせによって行われる。
【００４４】
このように、それぞれの単語は横断線の上に最長一致連鎖の長さの印をつける。最終的に、最も高いｊを持つ論理１のＴｊラインは、最長一致連鎖の長さを指し示す。
【００４５】
図４に、最長一致連鎖の最後でサブワードを探すタスクを示す。Ｔｊラインの上の信号がセットされ、Ｔｊ＋１の信号がセットされていないという条件が確認された場合、それぞれのサブワードＢｉ，ｊにおいて、横断線Ｔｊに関連付けられた信号と次の横断線Ｔｊ＋１に関連付けられた信号とが、最長一致信号ＬＭｉ、ｊを形成するために、論理ゲートによって結合される。
【００４６】
図４に示すように、この条件は、スティルマッチ信号ＳＭｉ，ｊと横断線Ｔｊ＋１が反転されたものとを論理積ゲートによって結合することにより、実行される。特別な場合が、単語Ｗｊの最後のサブワードＢｊ，ｗについて、定義づけられている。この場合、スティルマッチ信号ＳＭｉ，ｗがセットされたとき、ｗが、単語におけるサブワードの最大の数字であるため、それは明らかに最長一致連鎖である。それゆえに、前記最後のサブワードＢｊ，ｗに対して、信号ＬＭｉ，ｊは、信号ＳＭｉ，ｊと同一にセットされる。
【００４７】
図６に示すように、最長長さを持つ一致連鎖が検出された場合に、それぞれの単語の単語一致信号を有効にするタスクがある。図６によれば、単語ＷｉのすべてのＬＭｊ，ｊが、広域論理和ゲートに集められ、単語一致信号ＷＭｉ，ｊをセットする。
【００４８】
図に示すように、本発明にかかる回路とシステムは、最長一致の状況によって、単語Ｗｉの単語一致信号ＷＭｉを有効にするために使用される。標準的なＣＡＭの場合のように、メモリのいくつかの単語は、それぞれが最長一致の条件を満たすために、単語一致信号を有効にする。しかしながら、ＣＡＭあるいはＣＯＭは、出力のための一つのセルのアドレスのみを選択するために、優先エンコーダあるいは、優先マスクを含んでおり、ＣＡＭあるいはＣＯＭの特定の種類の優先システムによって、その選択がなされている。
【００４９】
本発明は、実施例としておよび好ましい実施形態として、上述され、発明および特許請求の範囲内において、他の多くの設計が可能である。このように、例えば他の構成が、好ましい実施例の線の代わりに、様々な要素を接続するために、使用される。
（ＶＬＳＩ実装の実施例）
図８は、１番目、２番目、３番目のサブワードをそれぞれに、Ｂｉ−１，１、Ｂｉ，１、Ｂｉ＋１，１とし、横断線なしでの実施例を示したものである。
【００５０】
図７および図８はＶＬＳＩ実行の好ましい実施例を示す。このＶＬＳＩ実装では、ＯＲ論理和は、線を放電するトランジスタを用いて実現され、一致の連鎖は、直列トランジスタにより実現される。図８は、単語Ｗｉ−１、Ｗｉ、Ｗｉ＋１用の一般的な配列を示しており、前記単語Ｗｉ−１、Ｗｉ、Ｗｉ＋１それぞれに、３つのサブワード番号ｊ、ｊ＋１、ｊ＋２を有している。
【００５１】
図９では、１つのサブワードＢｉ，ｊに関連付けられた回路が示されている。図９に示すように、それぞれのサブワードＢｉ，ｊに４つのトランジスタＱ１からＱ４までが関連付けられている。スティルマッチ信号ＳＭｉ，ｊは、図９に示すように、スティルマッチ信号ＳＭｉ,ｊ−１とＳＭｉ,ｊとの間に、それぞれの単語のそれぞれに関連付けられたラインの部分に、セットされる。これらのラインの部分をＳＭｉ，ｊラインと表記する。１つの単語のすべてのＳＭｉ，ｊラインは、直列接続されている。各ＳＭｉ，ｊラインの一方の端部は、トランジスタＱ２により、１つ前のＳＭｉ，ｊ−１ラインに接続され、他方の端部は同じ単語の次のＳＭｉ，ｊ＋１へ、トランジスタＱ２によって、接続されている。ＳＭｉ，ｊラインをＳＭｊ、ｊ−１に接続しているサブワードＢｉ，ｊのトランジスタＱ２のゲートは、サブワードＢｉ，ｊのサブワード一致信号に接続され、そのため、サブワードがデータに一致するなら、トランジスタが導通し、ラインＳＭｉ，ｊは、ＳＭｉ，ｊ−１に接続される。図８は、単語Ｗｉの１番目のサブワードＢｉ，１のために特別な場合を示している。前記１番目のサブワードＢｉ，１のＳＭｉ，１ラインは、トランジスタによって、グラウンド（０ボルト）に接続されている。そのトランジスタのゲートは、Ｂｉ，１のサブワード一致信号に接続されている。
【００５２】
初期化段階で、すべてのＳＭｉ，ｊライン、すべての横断線Ｔｊとすべての単語一致ラインが、あらかじめ充電される。予備充電は、ＶＬＳＩにおいて通常の技術である。また、クロック信号は、最初０ボルトにセットされる。反転論理を用いるときには、前述のとおり、あらかじめ充電する代わりに、単語一致ラインは、あらかじめ放電される。
【００５３】
最長一致検出のためのメモリを有効にするとき、サブワード一致信号は、一致信号を持つすべてのサブワードに対して、セットされる。図９に示す特定のサブワードＢｉ，ｊによれば、サブワード一致信号は、トランジスタＱ２を導通させる原因になり、ＳＭｉ，ｊラインの電位と１つ前のサブワードＳＭｉ，ｊ−１ラインの電位を等しくする。ここで図８について、１番目のサブワードにおいて、すべての前記サブワードＢｉ，ｋ（ｋ≦ｊ）が、一致しているとき、スティルマッチ信号ＳＭｉ，１は、グラウンドに接続され、すべてのＳＭｉ，ｋラインは、トランジスタＱ２を通って、グラウンドに放電される。このように、Ｂｉ，１からＢｉ，ｊの全てのサブワードが、一致するデータを含みさえすれば、ＳＭｉ，ｊ部分のラインは、グラウンドに放電される。これらのＳＭｉ，ｊに、論理１の０電位を定義する場合、この実行は上に記載した一致連鎖と同等の機能を実行する。
【００５４】
再び図７および図８を参照し、上に記載した本発明の原理によれば、横断線Ｔｊは、それぞれのサブワードの位置に、それぞれ割り当てられ、単語Ｗｉの一致連鎖がサブワードＢｉ，ｊに達する場合、サブワードＢｉ，ｊに割り当てられた横断線Ｔｊは、論理１にセットされる。これは、図９におけるサブワードＢｉ，ｊで示すと、次のように行われる。
【００５５】
それぞれの横断線Ｔｊは、前記サブワードＢｉ，ｊのサブワード一致信号Ｍｉ，ｊに接続されるゲートを持つトランジスタＱ１を通って、それぞれのサブワードＢｉ，ｊにおいて、ＳＭｉ，ｊラインに接続される。
【００５６】
ＳＭｉ，ｊが放電される（論理１）場合において、横断線Ｔｊもまた、一致信号Ｍｉ，ｊにより導通されたトランジスタＱ１とＳＭｊ，ｋライン（ｋ≦ｊ）の連鎖を通って、放電される。これにより図５のＯＲ論理和と同等のものが実現される。
【００５７】
図８において破線により囲まれた部分の描写を拡大したものである図９に示すように、Ｑ４およびＱ３のトランジスタは、単語一致線をＳＭｉ，ｊラインに接続している。
【００５８】
すべての一致信号がセットされた後、クロック信号は、高い電位にセットされ、すべてのＱ４トランジスタに供給され、それらを導通させる。サブワードＢｉ，ｊのＱ３トランジスタのゲートは、次の横断線Ｔｊ＋１に接続される。この横断線Ｔｊ＋１が、放電される（すなわち論理０のままである）場合、サブワードｊ＋１に到着した一致連鎖が存在しないことを意味し、そのときは、トランジスタＱ３は導通したままで、そのゲートをＴｊ＋１ラインに接続している。スティルマッチ信号ＳＭｉ，ｊが、グラウンドにセットされていない場合、一致連鎖がサブワードＢｉ，ｊに到着したことを意味し、そのときトランジスタＱ３およびＱ４を通して、単語一致ラインは、グラウンドに放電される。
【００５９】
言い換えると、単語一致ラインは、次に示すような条件が満たされている場合に放電される。
【００６０】
１つのサブワードの位置Ｂｉ，ｊで、
ＳＭｉ，ｊが放電されている、（すべてのサブワードＢｉ，ｋ（ｋ≦ｊ）が一致するデータを持っていることを示唆している）、
横断線Ｔｊ＋１は、放電されていない、（サブワードｊ＋１までの連続した一致データを持っている他の単語は無いことを示唆している）、
これにより、単語一致ラインが、一致するサブワードの最長連鎖を持つ単語のみに対して放電されることが確実になる。
【００６１】
上述のシステムと回路は、このようにメモリの単語が、与えられた単語位置から始まる連鎖であって、メモリの全単語中で連続して一致するサブワードの最長連鎖を含む場合に、メモリの各単語について信号を選択的にセットする手段を提供している。
【００６２】
発明を実施するために、クロック信号や、ゲートおよび／または放電回路の異なる組み合わせを用いたり、用いないことにより、同じ論理的機能が、いくつかの異なる方法で実現できる。しかしながら、本発明の手段と原理は、他の方法や実現可能な回路のデザインパターンを含んだ一般的な描写を提供する。
【００６３】
図は、直線的な幾何学的ラインを使用した電子的回路の概念的な表現であり、本発明の回路の現実の形状は、図に一致しない。
【図面の簡単な説明】
【００６４】
【図１】最長一致検索システムにおいて構成要素としてよく用いられるコンテントアドレサブルメモリの典型的で一般的なブロック図である。
【図２】典型的なコンテントアドレサブルメモリにおいて、単語一致信号の発生の方法を示す。
【図３】ＣＡＭまたはＣＯＭにおいて結合された発明の好ましい実施例である。
【図４】好ましい実施例における１つのサブワードに関連付けられる回路の詳細を示したものである。
【図５】好ましい実施例におけるすべての単語の与えられた位置Ｊにおけるすべてのサブワードが横断線Ｔｊを有効にする方法を示す。
【図６】サブワードの一つが最長一致出力を有効にする場合に、単語Ｗｉの単語一致行が、有効にされる方法を示したものである。
【図７】ＶＬＳＩ回路における一般的な好ましい実施例である。
【図８】サブワード位置が１，２，３の場合のＶＬＳＩ回路を示したものである。
【図９】破線部で囲まれた図８の部分についての回路の詳細を示したものである。
【図１】
2004526272.tif 000003
【図２】
2004526272.tif 000004
【図３】
2004526272.tif 000005
【図４】
2004526272.tif 000006
【図５】
2004526272.tif 000007
【図６】
2004526272.tif 000008
【図７】
2004526272.tif 000009
【図８】
2004526272.tif 000010
【図９】
2004526272.tif 000011
【国際公開パンフレット】
2004526272.tif 000012
2004526272.tif 000013
2004526272.tif 000014
2004526272.tif 000015
2004526272.tif 000016
2004526272.tif 000017
2004526272.tif 000018
2004526272.tif 000019
2004526272.tif 000020
2004526272.tif 000021
2004526272.tif 000022
2004526272.tif 000023
2004526272.tif 000024
2004526272.tif 000025
2004526272.tif 000026
2004526272.tif 000027
2004526272.tif 000028
2004526272.tif 000029
2004526272.tif 000030
2004526272.tif 000031
2004526272.tif 000032
2004526272.tif 000033
2004526272.tif 000034
2004526272.tif 000035
【国際調査報告】
2004526272.tif 000036
2004526272.tif 000037