(57)【特許請求の範囲】
【請求項１】
複数の格納データの集合からなる１つのデータ群を構成する複数のデータを各データ毎に記憶する複数のメモリワードからなるメモリワード群を複数備え、検索データが入力される毎に、入力された検索データの全部もしくは所定の一部のビットパターンと前記メモリワードに記憶されたデータのうち前記ビットパターンと対応する全部又は一部分のビットパターンとの一致検索を行ない、１回もしくは連続する複数回からなる所定回数の一致検索全てにおいて、入力された検索データの全部もしくは各所定の一部のビットパターンと、同一の前記メモリワード群内に記憶されたデータのうち前記ビットパターンと対応する全部又は一部分との一致が検出されたことをもって、前記所定回数入力された検索データに対応するデータ群の存在を検出する連想メモリにおいて、
前記所定回数の一致検索の間、１回の検索毎に、入力された検索データを、検索の対象とされる有効データ群が記憶されておらず、したがって上書きが許容される空き状態にあるメモリワード群の中から選択された１つのメモリワード群内のいずれかのメモリワードに書き込むデータ書込回路を備えたことを特徴とする連想メモリ。
【請求項２】
前記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、前記有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは前記空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタと、
前記所定回数の一致検索の結果、該所定回数入力された検索データに対応するデータ群が検出されなかった場合に、前記１つのメモリワード群に対応する前記フラグレジスタに、前記記憶状態を示すフラグを記憶させるフラグ変更回路とを備えたことを特徴とする請求項１記載の連想メモリ。
【請求項３】
前記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、前記有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは前記空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタと、
外部から入力された所定の指示信号を受けて、前記１つのメモリワード群に対応する前記フラグレジスタに、前記記憶状態を示すフラグを記憶させるフラグ変更回路とを備えたことを特徴とする請求項１記載の連想メモリ。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、各データをそれぞれ記憶する複数のメモリワードを備えるとともに、各メモリワードの記憶されたデータと入力された検索データとの一致不一致を検索する機能を備えた連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ，内容アドレス式メモリ；Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）に関する。
【０００２】
【従来の技術】
近年、上記のような検索機能を備えた連想メモリが提案されている。ここでは、先ず最初に、連想メモリの構造、機能について説明し、次いで連想メモリの適用分野の例について説明する。
図９は従来の連想メモリの一例を表わした回路ブロック図である。
【０００３】
この連想メモリ１０には、互いに図の横方向に並ぶ複数のメモリセルからなるメモリワード１１ａ，１１ｂ，…，１１ｎが多数備えられている。またこの連想メモリ１０は、検索データが入力されラッチされる検索レジスタ１２を備え、検索レジスタ１２にラッチされた検索データの全部もしくは所定の一部のビットパターンと、各メモリワード１１ａ，１１ｂ，…，１１ｎに記憶されたデータのうち、上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリワード１１ａ，１１ｂ，…，１１ｎのそれぞれに対応して備えられた一致線１４ａ，１４ｂ，…，１４ｎのうちビットパターンが一致したメモリワード１１ａ，１１ｂ，…，１１ｎに対応する一致線１４ａ，１４ｂ，…，１４ｎに論理‘１’の一致信号が出力され、それ以外の一致線１４ａ，１４ｂ，…，１４ｎに論理‘０’の不一致信号が出力される。
【０００４】
ここでは各フラグ線１４ａ，１４ｂ，…，１４ｎにそれぞれ‘０’，‘１’，‘０’，‘０’，‘１’，…，‘０’の信号が出力されたものとする。この信号はプライオリティエンコーダ１５に入力され、このプライオリティエンコーダ１５からは論理‘１’の一致信号が出力された一致線（ここでは一致線１４ｂと一致線１４ｅの２本）のうちの優先度の最も高い最優先一致線に対応するアドレス信号ＡＤが出力される。ここでは、添字のアルファベットが若いほど優先順位が高いものとし、従ってここでは一致線１４ｂが最優先一致線となる。このプライオリティエンコーダ１５から出力された、最優先一致線１４ｂに対応するアドレス信号ＡＤは、必要に応じて、アドレスデコーダ１６に入力される。アドレスデコーダ１６ではこの入力されたアドレス信号ＡＤをデコードして各メモリワード１１ａ，１１ｂ，…，１１ｎのそれぞれに対応して備えられたワード線１７ａ，１７ｂ，…，１７ｎのうちの入力されたアドレス信号ＡＤに対応するいずれか１本のワード線（ここではワード線１７ｂ）にアクセス信号（ここでは論理‘１’の信号）を出力する。これによりアクセス信号の出力されたワード線１７ｂに対応するメモリワード１１ｂに記憶されているデータが出力レジスタ１８に読出される。
【０００５】
上記のように連想メモリ１０は、検索データを用いて多数のメモリワード１１ａ，１１ｂ，…，１１ｎに記憶された内容（データ）を検索し、一致するデータが記憶されたメモリワードのアドレスを得てそのメモリワードに記憶されたデータ全体を読出すことができるメモリである。
図１０は、連想メモリ中の１つのメモリワードを表わした詳細回路図である。
【０００６】
このメモリワード１１は、同一構成のｎ個のメモリセル１１−１，１１−２，…，１１−ｎから構成されている。各メモリセル１１−１，１１−２，…，１１−ｎには、互いの出力が互いの入力に接続された、第１インバータ２０−１，２０−２，…，２０−ｎと第２のインバータ２１−１，２１−２，…，２１−ｎが備えられており、これらのインバータ２０−１，２１−１；２０−２，２１−２；…；２０−ｎ，２１−ｎにより各メモリセル１１−１，１１−２，…，１１−ｎに論理‘１’もしくは論理‘０’の１ビットの情報が記憶される。
【０００７】
また各メモリセル１１−１，１１−２，…，１１−ｎにおいて、第１インバータ２０−１，２０−２，…，２０−ｎの出力はＮチャンネルトランジスタ２２−１，２２−２，…，２２−ｎを介してビット線２３−１，２３−２，…，２３−ｎと接続されており、このトランジスタ２２−１，２２−２，…，２２−ｎのゲートはワード線２４に接続されている。また第２のインバータ２１−１，２１−２，…，２１−ｎの出力はＮチャンネルトランジスタ２５−１，２５−２，…，２５−ｎを介してビットバー線２６−１，２６−２，…，２６−ｎと接続されており、このトランジスタ２５−１，２５−２，…，２５−ｎのゲートもワード線２４に接続されている。さらに各メモリセル１１−１，１１−２，…，１１−ｎは、ビット線２３−１，２３−２，…，２３−ｎとビットバー線２６−１，２６−２，…，２６−ｎとの間をつなぐように互いにシリーズに接続された２つのＮチャンネルトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎが配置されており、これら各２つのトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎのうちの一方のトランジスタ２７−１，２７−２，…，２７−ｎのゲートは第１のインバータ２０−１，２０−２，…，２０−ｎの出力、他方のトランジスタ２８−１，２８−２，…，２８−ｎのゲートは第２のインバータ２１−１，２１−２，…，２１−ｎの出力と接続されている。
【０００８】
また一致線１４には、各メモリセル１１−１，１１−２，…，１１−ｎに対応して１つずつトランジスタ３６−１，３６−２，…，３６−ｎが備えられており、それらのトランジスタ３６−１，３６−２，…，３６−ｎは互いにシリーズに接続され、それらのトランジスタ３６−１，３６−２，…，３６−ｎの各ゲートは、各２つのトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎの中点と接続されている。
【０００９】
またこの一致線１４にはもう１つのトランジスタ３６−０がシリーズに接続されており、一致線１４の図１０の左端はこのトランジスタ３６−０を介して接地されている。またこのトランジスタ３６−０のゲートは制御線３０に接続されている。
一致線１４の、図１０の右端にはセンス用インバータ３１が配置され、このインバータ３１の出力からは一致線１４がさらに延び、図９に示すプライオリティエンコーダ１５に接続されている。
【００１０】
またこのインバータ３１の入力と電源ＶDDとの間には２つのＰチャンネルトランジスタ３２，３３が配置されており、これら２つのトランジスタ３２，３３のうちの一方のトランジスタ３２のゲートは制御線３０と接続され、他方のトランジスタ３３のゲートはインバータ３１の出力と接続されている。
このような構造のメモリワード及びその周辺回路を備えた連想メモリにおいて、一致検索は以下のようにして行なわれる。
【００１１】
メモリセル１１−１には、論理‘１’の情報が記憶されているものとする。即ちこの場合第１のインバータ２０−１の出力側が論理‘１’、第２のインバータ２１−１の出力側が論理‘０’の状態にある。
このメモリセル１１−１に対して論理‘１’の検索が行なわれるものとする。即ち、ビット線２３−１が論理‘１’、ビットバー線２６−１が論理‘０’とされる。ワード線２４は論理‘０’のままの状態に保持されている。この場合トランジスタ２７−１のゲートには論理‘１’の電圧が印加され、ビット線２３−１の論理‘１’の信号がトランジスタ３６−１のゲートに印加され、これによりトランジスタ３６−１が‘オン’状態となる。即ちメモリセル１１−１に記憶されたビット情報とビット線２３−１、ビットバー線２６−１を経由して入力された検索データ中のビット情報が一致する場合に、対応するトランジスタ３６−１が‘オン’状態となる。
【００１２】
また、メモリセル１１−２には論理‘０’の情報が記憶されているものとする。この場合第１のインバータ２０−２の出力側が論理‘０’、第２のインバータ２１−２の出力側が論理‘１’の状態にある。
このメモリセル１１−２に対してやはり論理‘１’の検索が行なわれるものとする。即ち、ビット線２３−２が論理‘１’、ビットバー線２６−２が論理‘０’とされる。この場合、トランジスタ２８−２を経由して論理‘０’の状態にあるビットバー線２６−２の信号がトランジスタ３６−２のゲートに印加され、したがってこのトランジスタ３６−２は‘オフ’状態にととどまることになる。即ち不一致の場合、一致線１４にプリチャージされていた電荷はディスチャージされない。
【００１３】
また、マスクをかけたビットについては、メモリセル１１−ｎに示すように、ビット線２３−ｎ、ビットバー線２６−ｎの双方とも論理‘１’とされる。この場合このメモリセル１１−ｎに論理‘１’の情報が記憶されているか論理‘０’の情報が記憶されているかに応じてトランジスタ２７−ｎもしくはトランジスタ２８−５のいずれかが‘オン’状態となり、これによりいずれの場合もトランジスタ３６−５が‘オン’状態になる。すなわちそのメモリセルについては、記憶された情報と検索の情報とが一致しているものとみなされる。
【００１４】
検索にあたっては制御線３０が先ず論理‘０’となり、トランジスタ３２が‘オン’状態となってインバータ３１の入力側の一致線１４がプリチャージされ、その後制御線３０が論理‘１’となり、トランジスタ３２が‘オフ’状態となってプリチャージが停止するとともにトランジスタ３６−０が‘オン’状態となる。
【００１５】
このとき、メモリセルに記憶された情報と入力された検索の情報がこのメモリワード１１を構成する全てのメモリセルにわたって一致している（上述したようにマスクされたビットは一致とみなす）場合、トランジスタ３６−１，３６−２，…，３６−ｎの全てが‘オン’状態となり一致線１４にプリチャージされた電荷がディスチャージされ、インバータ３１から論理‘１’の信号が出力される。
【００１６】
尚、図１０に示す連想メモリのメモリ構造は一例に過ぎず、種々の構造のものが提案されている（例えば特願平５−２１６４２４号参照）。
次に、連想メモリの適用の一例として、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）への適用例について説明する。
図１１は、ＬＡＮの一例を示した図である。
【００１７】
図１１（Ａ）に示すように２つの通信回線ＬＡＮ１，ＬＡＮ２に、それぞれ複数の端末Ａ〜Ｇ，Ｔ〜Ｚが接続され、これにより２つの通信綱が構成されているものとする。通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量（その通信回線を流れるデータの量；その通信回線の混雑度）は、それぞれ’１０’であるとする。これら２つの通信回線を互いに接続する必要が生じた場合に、図１１（Ｂ）に示すように図１１（Ｂ）に示すように単純に接続すると、通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量は２０となり、極めて混雑し、各端末間がなかなか接続されず、待ち時間、空き時間が増大してしまうという結果を招く。
【００１８】
そこで通常は、図１１（Ｃ）に示すように２つの通信回線ＬＡＮ１，ＬＡＮ２の中間に、これらの通信回線ＬＡＮ１，ＬＡＮ２のうちの一方から発信されたデータを他方に伝送するか否かのフィルタリングを行なうブリッジを接続する。このブリッジを接続した場合、このブリッジを通過するデータのトラフィック量、すなわち２つの通信綱に跨るデータの授受についてのトラフィック量を１とすると、各通信回線ＬＡＮ１，ＬＡＮ２内部でのトラフィック量１０とを合わせ、各通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量はそれぞれ１１となり、２つの通信回線ＬＡＮ１，ＬＡＮ２を単純に接続した図１１（Ｂ）の場合と比べトラフィック量は大きく低下する。ここでは２つの通信回線ＬＡＮ１，ＬＡＮ２の接続について説明したが、１つのブリッジに多数の通信回線を接続すると、この差はさらに顕著となる。
【００１９】
図１２は、ブリッジの機能説明図である。
ブリッジは内部にメモリを持ち、最初は全て空白の状態から出発し、例えば通信回線ＬＡＮ１の端末Ａからデータが送信されると、ＬＡＮ１側からそのデータが送信されてきたことを受けて、端末Ａが通信回線ＬＡＮ１に接続されていることを学習する。この学習は、概念的には、ブリッジ内部のメモリに、通信回線ＬＡＮ１，ＬＡＮ２それぞれについてテーブル１，テーブル２を持ち、通信回線ＬＡＮ１に対応するテーブル１に端末Ａを書込むことによって行われる。端末Ａから送信されたデータの受信先が、端末Ａと同じＬＡＮ１側の通信網内にあるか否かは端末Ａについてのみ学習した時点では判らずしたがってこの時点は無条件にブリッジを通過させる。
【００２０】
このような学習を繰り返すことにより、ブリッジ中に図１２に示すようなテーブル１，テーブル２が作成され、これらが作成された後は、例えば図示のように、発信先が端末Ｂ（ＬＡＮ１側）、受信先が端末Ｘ（ＬＡＮ２側）のデータは、ブリッジで、それら端末Ｂ，Ｘがブリッジを跨っていることを認識してブリッジを通過させ、発信先，受信先がいずれもＬＡＮ１側の端末Ａ，Ｅの場合は、それらの端末Ａ，Ｅがブリッジから見て同じ側の通信網にあることを認識してブリッジでデータの通過を遮断する。これにより、前述したように、トラフィック量の低減化が図られる。
【００２１】
このブリッジに備えられるメモリとして連想メモリを採用すると、処理の高速化が図られる。例えば各端末Ａ〜Ｇ，Ｔ〜Ｚの情報と、それらの各端末がテーブル１に属するか（ＬＡＮ１側に接続されているか）、あるいはテーブル２に属するか（ＬＡＮ２側に属するか）という情報を連想メモリに記憶し、データを通過させるか否かの判断にあたっては、例えば受信先が端末Ｘであった場合、そのＸを検索データとして検索してそのＸがテーブル２（ＬＡＮ２）に属する端末であることを認識し、これに基づいてデータを通過させるか否かを定めることができる。
【００２２】
これに対し、ブリッジに通常のＲＡＭメモリ等を備えた場合は、メモリされたデータを１つずつ読み出してはそのデータが端末Ｘのデータであるか否かを逐次比較により検索する必要があり、ブリッジを通過させるか遮断するかを定めるために多大な時間を要することとなる。
【００２３】
【発明が解決しようとする課題】
上記のように、連想メモリは、例えばＬＡＮネットワーク等に好適に用いられるが、例えば端末Ａからデータが送信されてきたとき、それを受けて端末Ａがブリッジ内のメモリに既に登録されているかどうか確認し、未登録の場合は登録を行なう必要がある。このように、従来は、既に登録されているかどうかの確認と、未登録の場合の登録との２つのステップを必要としており、このことが、ブリッジの動作をさらに高速化する際の妨げの１つとなっている。
【００２４】
本発明は、上記事情に鑑み、未登録データの登録を高速に行なうことのできる連想メモリを提供することを目的とする。
【００２５】
【課題を解決するための手段】
上記目的を達成する本発明の第１の連想メモリは、
各データをそれぞれ記憶するメモリワードと、そのメモリワードに対応して備えられた、入力された検索データの全部もしくは所定の一部のビットパターンとそのメモリワードに記憶されたデータのうち上記ビットパターンと対応する全部又は一部分のビットパターンとの一致不一致を検出する一致検出回路とを備えた連想メモリにおいて、
前記一致検出回路のいずれからも、一致が検出されたことを示す一致信号が出力されなかった場合に、前記検索データを、上記メモリワードのうち検索の対象とされる有効データが記憶されておらずしたがって上書きが許容される空き状態にあるメモリワードの１つに記憶させるデータ追記回路を備えたことを特徴とするものである。
【００２６】
ここで、上記本発明の第１の連想メモリにおいて、上記データ追記回路は、
（１）上記のメモリワードに対応して備えられた、そのメモリワードが、有効データが記憶された記憶状態にあるメモリワードであるか、あるいは空き状態にあるメモリワードであるかを示すフラグが記憶されるフラグレジスタ
（２）空き状態にあるメモリワードの中から１つのメモリワードを選択してその１つのメモリワードに検索データを書き込む検索データ書込回路
（３）上記一致検出回路のいずれからも一致信号が出力されなかった場合に、上記１つのメモリワードに対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えたものであってもよい。
【００２７】
また、上記目的を達成する本発明の第２の連想メモリは、
複数の格納データの集合からなる１つのデータ群を構成する複数のデータを、各データ毎に記憶する複数のメモリワードからなるメモリワード群を複数備え、検索データが入力される毎に、入力された検索データの全部もしくは所定の一部のビットパターンと上記メモリワードに記憶されたデータのうち上記ビットパターンと対応する全部又は一部分のビットパターンとの一致検索を行ない、１回もしくは連続する複数回からなる所定回数の一致検索全てにおいて、入力された検索データの全部もしくは各所定の一部のビットパターンと、同一のメモリワード群内に記憶されたデータのうち上記ビットパターンと対応する全部又は一部分との一致が検出されたことをもって、上記所定回数入力された検索データに対応するデータ群の存在を検出する連想メモリにおいて、
上記所定回数の一致検索の間、１回の検索毎に、入力された検索データを、検索の対象とされる有効データ群が記憶されておらず、したがって上書きが許容される空き状態にあるメモリワード群の中から選択された１つのメモリワード群内のいずれかのメモリワードに書き込むデータ書込回路を備えたことを特徴とするものである。
【００２８】
ここで、上記本発明の第２の連想メモリにおいて、
（４）上記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタ
（５）上記所定回数の一致検索の結果、所定回数入力された検索データに対応するデータ群が検出されなかった場合に、上記１つのメモリワード群に対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えることが好ましい。
【００２９】
あるいは、上記本発明の第２の連想メモリにおいて、
（６）上記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、前記有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは前記空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタ
（７）外部から入力された所定の指示信号を受けて、上記１つのメモリワード群に対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えてもよい。
【００３０】
【作用】
上記本発明の第１の連想メモリは、検索によって一致検出が行なわれなかったことを受けて検索データをそのまま格納してしまうものであるため、従来のように、検索動作と、その検索により一致が検出されなかった場合にデータを書き込む動作との２回のステップは不要となり、処理の高速化が図られることになる。
【００３１】
ここで、特公昭６１−３１５５８号公報に、本発明と関連した技術が提案されているため、そこに提案された技術と本発明との相違を説明する。
連想メモリを構成する多数のメモリワードは、常に全てのメモリワードに検索の対象となるデータが記憶されている訳ではなく、それらのメモリワードの一部は有効なデータが記憶されていない空きの状態にあったり、その空きの状態にあるメモリワードに新たに有効データを書き込んだりすることがある。この場合、このメモリワードが空きの状態にあるか否かを外部で管理しておくのは煩雑であることから、上記の文献には、各メモリワードに対応してそのメモリワードに有効なデータが記憶されているかそれともそのメモリワードが空きの状態にあるかを示すフラグを各メモリワードに対応させて記憶しておき、新たな有効データを書き込む場合に連想メモリ自体で空きの状態にあるメモリワードを見つけてそのメモリワードに有効データを書き込むという技術が提案されている。
【００３２】
そこに提案された技術は、空き状態にあるメモリワードを外部で管理する必要をなくすためのものであって、未登録のデータの登録においては、やはり、そのデータが既登録が未登録かの検索と、未登録の場合の登録との２つのステップを要するものである。
本発明の第２の連想メモリは、データ群を記憶しておくメモリワード群を有し、検索データを入力して検索を行なうという動作を所定回数行なって対応するデータ群の存在を検出する連想メモリに関するものである。
【００３３】
このような連想メモリにおいて、例えば１００個のデータからなるデータ群を格納しておいて、検索データを入力して検索を行なうという動作を１００回繰り返して所望のデータ群を検出する場合、従来考えられているデータ群の存在を検出するタイプの連想メモリを用いると、１００回の検索を行なった結果所望のデータ群が見つからなかった場合、次に検索データを１００回書き込んではじめて新たな有効なデータ群が登録されることになる。
【００３４】
これに比較し、本発明の第２の連想メモリでは、１回の検索毎に、検索データが、空き状態にあるメモリワード群に書き込まれるため、１００回の検索を行なった結果、所望のデータ群が見つからなかった場合、既に１回の検索毎に検索データが書き込まれているため、この検索データが書き込まれたメモリワード群を次回以降の検索に用いるか否かを定めるだけで済み、データ書き込みの手間が大幅に低減され、処理の高速化が図られることになる。
【００３５】
検索データが書き込まれたメモリワード群を次回以降の検索に用いるか否かは、例えば上記（４）、上記（６）のフラグレジスタを備えておき、そのフラグレジスタに記憶されたフラグを書き換えることによって定めることができる。
このフラグの書き換えは、上記（５）のフラグ変更回路を備えることにより、所定回数の検索で所望のデータ群が検出されなかったことを受けて自動的に書き換えを行うように構成することがより好ましいが、上記（７）のフラグ変更回路を備え、外部からフラグ書換えの指示を入力するように構成してもよく、この場合であっても、従来と比べ処理の大幅な高速化を図ることができる。
【００３６】
【実施例】
以下、本発明の実施例について説明する。
図１は、本発明の第１の連想メモリの一実施例の特徴部分を示す回路図である。前述した従来例で参照した図面における構成要素に対応する構成要素には、それらの図面に付した番号と同一の番号を付して示す。
【００３７】
この図１では、メモリワード１１や一致線１４の構成は略示されている。この各メモリワード１１に対応して各フラグレジスタ５１が備えられており、このフラグレジスタ５１には、対応するメモリワード１１に、検索の対象となる有効ワードが記憶されている場合に’０’、検索の対象から除外され、したがって上書きを許容する無効のデータが記憶されている場合（ここではこれを、対応するメモリワード１１が「空き状態」に有る、と称する）に’１’の空きフラグが記憶される。ここでは、各フラグレジスタ５１には、図示のように、’０’，’０’，…，’１’が格納されているものとする。各フラグレジスタ５１のＱ出力は、対応して備えられた各複数選択分離回路５２に入力される。この選択分離回路５２は互いに直列的に接続されており、その接続により、この図の上方ほど優先度が高くなっており、’１’が格納されたフラグレジスタ５１のうち、優先度の最も高いフラグレジスタ５１に対応する複数選択分離回路５２のみから信号’１’が出力される。ここでは、図１の一番下に図示されたフラグレジスタ５１が最も優先度が高く、したがってそれに対応する一番下に図示された複数選択分離回路５２から’１’が出力されているものとする。
【００３８】
図２は、複数選択分離回路５２の回路例を示した図である。
図２（Ａ）に示す複数選択分離回路５２は、図示のように接続された、一方の入力が反転されるアンドゲート５２１と、オアゲート５２２から構成されている。また、図示の一番上の複数選択分離回路５２を構成するオアゲート５２２の一方の入力はグラウンドＧＮＤに接地されている。
【００３９】
この構成の複数選択分離回路５２では図示の上方ほど高い優先度を有しており、複数のフラグレジスタ５１に空きフラグ‘１’が格納されている場合に、それら複数のフラグレジスタ５１のうち最も高い優先度を有するフラグレジスタ５１に対応する複数選択分離回路５２のアンドゲート５２１から‘１’が出力される。
【００４０】
また、図２（Ｂ）に示す複数選択分離回路５２’は、図示のようにインバータ５２３、Ｎチャンネルトランジスタ５２４，Ｐチャンネルトランジスタ５２６、排他論理和（エクスクルーシブオア）ゲート５２５から構成されている。また各複数選択分離回路５２’を構成するＰチャンネルトランジスタ５２６の一端は電源ＶDDに接続され、図示の一番上の複数選択分離回路５２’を構成する排他論理和ゲート５２５の一方の入力はグラウンドＧＮＤに接地されている。
【００４１】
この図２（Ｂ）に示す複数選択分離回路５２’も、図２（Ａ）に示す複数選択分離回路５２と同様に、図示の上方ほど高い優先度を有しており、複数のフラグレジスタ５１に空きフラグ‘１’が格納されている場合に、それら複数のフラグレジスタ５１のうち最も高い優先度を有するフラグレジスタ５１に対応する複数選択分離回路５２’の排他論理和ゲート５２５から‘１’が出力される。
【００４２】
尚、この図２（Ａ）もしくは図２（Ｂ）に示す複数選択分離回路の後段にエンコーダを接続すれば、図９に示すプライオリティエンコーダ１５が構成される。
上記のようにして、図１の１番下に図示されたフラグレジスタ５１が、空きフラグ‘１’が格納された第２のフラグレジスタ５１の中の最優先のものであった場合、それに対応する複数選択分離回路５２から‘１’が出力され、対応するアンドゲート６７に入力される。またこのアンドゲート６７の入力にはワード線活性化タイミング信号線６８も接続されている。
【００４３】
ここで、ビット線ドライブ回路７０によりビット線２３−１，…，２３−ｎ、およびビットバー線２６−１，…，２６−ｎに検索データをのせて検索を行なう。その結果、その検索データと図示の最上段のメモリワード１１に記憶されたデータとが一致したものとすると、最上段の一致線１４が’１’となり、フラグレジスタ５１の出力は’０’であるためアンドゲート５３の出力が’１’となる。ここではアンドゲート５３の出力から延びる線も一致線１４０と称する。全てのメモリワード１１に対応する一致線１４０は全体一致検出回路７１に延び、さらに、従来の場合の一致線１４に代わり、図９に示すプライオリティエンコーダ１５に延びている。フラグレジスタ５１に空きフラグ’１’が格納されている場合は、そのフラグレジスタ５１に対応するメモリワード１１で一致が生じても、一致線１４の’１’信号はアンドゲート５３でストップされ、そのアンドゲート５３の出力側の一致線１４０は’０’のままにとどまる。すなわち、そのメモリワード１１は検索には寄与しないことになる。
【００４４】
全体一致検出回路７１では、各一致線１４０から入力された信号のオア演算を行い、これにより、１つでも一致があったか、もしくは全てのメモリワード１１にわたって不一致であったかが検出され、追記制御回路７２に入力される。
追記制御回路７２では、先ず、いずれかのメモリワード１１で一致が生じたか否かにはかかわりなく、ビット線２３−１，…，２３−ｎ、ビットバー線２６−１，…，２６−ｎに  検索データをのせて検索しているときに、ワード線活性化タイミング信号線６８に信号’１’をのせる。すると、’１’の信号を出力している、図示の１番下の複数選択分離回路５２に対応するアンドゲート６７の出力が’１’となり、対応するワード線２４が’１’となって、図示の１番下のメモリワード１１に検索データが書き込まれる。この検索データが書き込まれるタイミングは、検索と同時であり、したがってその検索において一致が生じたか否かとは無関係である。
【００４５】
その後、上述のように、全体一致検出回路７１においていずれかのメモリワード１１で一致が生じたか、あるいは全てのメモリワード１１にわたって不一致であったかが検出されて追記制御回路７２に入力される。追記制御回路７２ではいずれかのメモリワード１１で一致が生じていたときはその後は何も行なわない。すなわち、図示の一番下のメモリワード１１には検索データが上書きされたものの、それに対応するフラグレジスタ５１には依然として空きフラグ’１’が格納されており、一番下のメモリワード１１は依然として検索に寄与しない空き状態にとどまることになる。
【００４６】
一方、全体一致検出回路７１で全てのメモリワード１１にわたって不一致が検出された場合、追記制御回路７２は以下のように動作する。すなわち、フラグレジスタ５１に接続された空きフラグデータ線６６に論理’０’の信号を与え、その状態で空きフラグクロック信号線６５に’１’のクロックパルスを与える。すると図示の１番下のメモリワード１１のワード線２４は’１’となっており、その’１’の信号が信号線６０を経由して一番下のアンドゲート６１に入力されているため、空きフラグクロック信号線６５に与えられたクロックパルスはそのアンドゲート６１を通過し、一番下のフラグレジスタ５１に入力される。これにより、一番下のフラグレジスタ５１に対応するメモリワード１１に検索の対象となる有効なデータが格納されていることを表す’０’が格納される。
【００４７】
複数選択分離回路５２では、図示の１番下のフラグレジスタ５１に’０’が格納されたことに伴い、そのフラグレジスタ５１以外の、空きフラグ’１’が格納されているフラグレジスタ５１中から最も優先度の高いものが検出されることになる。
次に、本発明の第２の連想メモリの実施例について説明するが、本発明の第２の連想メモリの思想が好適に適用される、データ群を格納しておいてデータ群の検索を行なう連想メモリ自体が未だ公知ではないため（特願平５−２４８１２１号参照）、ここでは先ずそのベースとなる連想メモリ自体について説明し、次いで、本発明の第２の連想メモリの実施例について説明する。
【００４８】
図３は、群構造を成すデータの一例を示した図である。
この図３には、それぞれ属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された４つのデータがセットとなって１つのデータ群を構成しているデータ構造が示されている。データ群および属性の概念を明確にするために一例を挙げると、例えば各群番号１，２，３，４，…毎の各データ群は各個人に属するデータであり、属性Ｉはその人の氏名，属性ＩＩはその人の生年月日、属性ＩＩＩは住所、……等を示している。
【００４９】
このように各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された複数のデータからなるデータ群を連想メモリに格納しておいて検索を行う場合に、例えば群番号１のデータを検索する場合を例に説明すると、データ‘Ａ’の検索とデータ‘Ｂ’の検索をこの順に行って一致するデータ群の残りのデータ‘Ｃ’，‘Ｄ’を読み出すことだけではなく、例えばデータ‘Ａ’の検索とデータ‘Ｄ’の検索を行って残りのデータ‘Ｂ’，‘Ｃ’を読み出したい場合や、データ‘Ｂ’の検索を先に行い、次にデータ‘Ａ’の検索を行いたい場合があり、それら多様な検索を行なうことのできる連想メモリが考えられている。
【００５０】
尚、ここでは、後の説明の都合上、群番号ｎとｎ＋１は、有効なデータ群が記録されていない空き状態にあるものとする。
図４は、図３に示すような群構造のデータを取り扱うのに好適な連想メモリの一例を示すブロック図である。
各メモリワード１１＿１，１１＿２，…から延びる各一致線１４＿１，１４＿２，…，は、各アンドゲート２０＿１，２０＿２，…の一方の入力端子に接続されている。また各アンドゲート２０＿１，２０＿２，…の他方の入力端子には各オアゲート２１＿２，２１＿３，…の出力端子が接続されており、各オアゲート２１＿２，２１＿３，…の一方の入力端子は、初回検索制御線２２に接続されている。
【００５１】
各アンドゲート２０＿１，２０＿２，…の出力端子は各第１のフラグレジスタ２３＿１，２３＿２，…のデータ入力端子に接続され、各第１のフラグレジスタ２３＿１，２３＿２，…の出力端子は各第２のフラグレジスタ２４＿１，２４＿２，…の入力端子に接続されている。各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子は、図９に示すプライオリティエンコーダ１５（図４では図示省略）に接続されるとともに、各第１のスイッチ３３＿１，３３＿２，…を介して、図３に示す各データ群を格納する各メモリワード群毎に備えられたデータ線３２＿１，３２＿２，…に接続されている。
【００５２】
第１のフラグレジスタ２３＿１，２３＿２，…と第２のフラグレジスタ２４＿１，２４＿２，…には、ともに、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１が入力され、その一致結果ラッチ信号Ｓ１により、各データ入力端子から入力された入力データがラッチされるが、第１のフラグレジスタ２３＿１，２３＿２，…には、一致結果ラッチ信号Ｓ１の立ち上がりａの時点における入力データがラッチされ、第２のフラグレジスタ２４＿１，２４＿２，…には、一致結果ラッチ信号Ｓ１の立ち下がりｂの時点−の入力データがラッチされる。
【００５３】
各メモリワード１１＿１，１１＿２，…は、属性を格納する属性格納部１１＿１＿１，１１＿２＿１，…とデータを格納するデータ格納部１１＿１＿２，１１＿２＿２，…とで構成されており、各メモリワード１１＿１，１１＿２，…には、互いに対応する属性とデータとのペアからなる格納データがそれぞれ格納されている。ここでは、図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４には、それぞれ、図３に示す群番号１に属する、属性Ｉ，データ‘Ａ’、属性ＩＩ，データ‘Ｂ’、属性ＩＩＩ，データ‘Ｃ’、属性ＩＶ，データ‘Ｄ’が格納されている。また各メモリワード１１＿５，１１＿６，…には、それぞれ、図３に示す群番号２に属する、属性Ｉ，データ‘Ｃ’、属性ＩＩ，データ‘Ｆ’、……が格納されている。また検索にあたっては、属性とデータとのペアからなる参照データＲＥＦ＿ＤＡＴＡが入力される。
【００５４】
各メモリワード１１＿１，１１＿２には、そこに記憶された格納データ（属性及びデータの双方）が、入力された参照データ（属性及びデータの双方）と一致しているときに一致信号が出力される従来の一致線１４＿１，１４＿２，…のほか、属性のみの一致不一致の信号が出力される属性一致線３０＿１，３０＿２，…が備えられている。尚、属性のみの一致も、属性及びデータの双方の一致も、従来の一致検出回路と同様に構成され、従来の一致検出回路は連想メモリの分野において極めて一般的な技術であるため、ここでの図示および説明は省略する。各メモリワード１１＿１，１１＿２に対応して第３のフラグレジスタ３１＿１，３１＿２，…が備えられており、各属性一致線３０＿１，３０＿２，…は対応する第３のフラグレジスタ３１＿１，３１＿２，…のデータ入力端子に延びている。また、この実施例の連想メモリには、前述したように図３に示す各データ群に属する各データが格納されたメモリワードからなるメモリワード群それぞれについて１本ずつデータ線３２＿１，３２＿２，…が備えられており、またデータ線３２＿１，３２＿２，…と各第２のフラグレジスタ３１＿１，３１＿２，…の出力端子との間には各第１のスイッチ３３＿１，３３＿２，…が備えられている。これらの第１のスイッチ３３＿１，３３＿２，…は具体的にはトランジスタ等を用いて構成される。後述する他のスイッチについても同様である。各第１のスイッチ３３＿１，３３＿２，…は、対応する各第３のフラグレジスタ３１＿１，３１＿２，…に論理‘１’の信号がラッチされているときに導通され、論理‘０’の信号がラッチされているときには遮断される。各第３のフラグレジスタ３１＿１，３１＿２，…は、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで、対応する属性一致線３０＿１，３０＿２，…の信号をラッチする。
【００５５】
またデータ線３２＿１，３２＿２，…と各オアゲート２１＿１，２１＿２，…の入力端子との間に各第２のスイッチ３４＿１，３４＿２，…が備えられており、これら各第２のスイッチ３４＿１，３４＿２，…は、対応する属性一致線３０＿１，３０＿２，…の信号により、その信号が一致を表わす論理‘１’のときに導通状態、不一致を表わす論理‘０’の時に遮断状態となるように制御される。
【００５６】
以上のように構成された連想メモリにおいて、一致検索は以下のようにして行われる。
各検索データを単独で検索する際は、参照データＲＥＦ＿ＤＡＴＡを入力して検索を行う際に、初回検索制御線２２に初回検索タイミング信号Ｓ２を出力する。ここでは、参照データＲＥＦ＿ＤＡＴＡとして属性ＩＩおよびデータ‘Ｂ’を入力したものとすると、属性ＩＩおよびデータ‘Ｂ’が格納されたワードメモリ１１＿２に対応する一致線１４＿２に論理‘１’の一致信号が出力されてアンドゲート２０＿２に入力され、また、これとともに初回検索タイミング信号Ｓ２がオアゲート２１＿２を経由してアンドゲート２０＿２に入力されるため、アンドゲート２０＿２から論理‘１’の信号が出力される。またこのとき、他の一致線１４＿１；１４＿３，１４＿４，…には論理‘０’の信号が出力されるため、それに対応する他のアンドゲート２０＿１；２０＿３，２０＿４，…からは論理‘０’の信号が出力される。
【００５７】
アンドゲート２０＿２から出力された論理‘１’の信号は、一致結果ラッチ制御線２５に出力された一致結果ラッチ信号Ｓ１の立ち上がりａのタイミングで第１のフラグレジスタ２３＿２にラッチされ、それに引き続くの一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで第２のフラグレジスタ２４＿２にラッチされる。
【００５８】
また第１のフラグレジスタ２３＿２および第２のフラグレジスタ２４＿２に論理‘１’の信号がラッチされる各タイミングで、他の第１フラグレジスタ２３＿１；２３＿３，２３＿４，…、および他の第２のフラグレジスタ２４＿１；２４＿３，；２４＿４，…には論理‘０’の信号がラッチされる。
このようにして各第２のフラグレジスタ２４＿１，２４＿２，２４＿３，…にラッチされた論理‘０’，‘１’，‘０’，…の信号が図９に示すプライオリティエンコーダ１５に入力され、ワードメモリ１１＿２のアドレス信号ＡＤが得られる。
【００５９】
次に複数回の連続したデータ検索を行なう場合について説明する。複数回の連続した検索を行う場合における第１回目の検索については、上述の単独のデータ検索の動作と同じであるが、この第１回目のデータ検索では、上記の動作に加えて、第２回目のデータ検索の準備として、以下の動作が行なわれる。
上記の第１回目のデータ検索の際、属性の一致を受けてメモリワード１１＿２に対応する属性一致線３０＿２に論理‘１’の信号が出力され、これにより、対応する第３のフラグレジスタ３１＿２にも論理‘１’の信号がラッチされ、対応する第１のスイッチ３３＿２がオンし、対応する第２のフラグレジスタ２４＿２に格納された、属性及びデータ双方の一致を表わす論理‘１’の信号がデータ線３２＿１に出力される。またこれとともに、対応する第２のスイッチ３４＿２もオンするが、第１回目の検索においてはこれは無用の動作である。
【００６０】
次に、属性ＩＶとデータ‘Ｄ’からなる参照データＲＥＦ＿ＤＡＴＡを入力して検索を行うものとする。このときは、初回検索制御線２２は論理‘０’に保持されている。このとき、属性の一致を受けてメモリワード１１＿４に対応する属性一致線３０＿４に論理‘１’の信号が出力され、これにより対応する第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されていた、メモリワード１１＿２に対応する第２のフラグレジスタ２４＿２の論理‘１’の信号がオアゲート２１＿４を経由してアンドゲート２０＿４に入力される。このため、メモリワード１１＿４で属性ＩＶとデータ‘Ｄ’の双方の一致が検出されて一致線１４＿４に論理‘１’の一致信号が出力されると、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１により、対応する第１および第２のフラグレジスタ２３＿４，２４＿４に論理‘１’の信号がラッチされる。またこのとき、属性一致線３０＿４に出力された論理‘１’の信号が、対応する第３のフラグレジスタ３１＿４にラッチされ、対応する第１のスイッチ３３＿４がオンし、第２のフラグレジスタ２４＿４の論理‘１’の信号がデータ線３２＿１に出力される。またこの２回目の検索では、メモリワード１１＿２に対応する属性一致線３０＿２には属性の不一致を表わす論理‘０が出力されるため、対応する第３のフラグレジスタ３１＿２には‘０’が格納され、メモリワード１１＿２に対応する第１のスイッチ３３＿２はオフする。
【００６１】
これにより、メモリワード１１＿４に対応する第２のフラグレジスタ２４＿４の論理‘１’の信号がプライオリティエンコーダ１５（図９参照）に入力され、メモリワード１１＿４のアドレスが得られることになるが、メモリワード１１＿４には属性ＩＶが格納されていることは予め分かっており、同一群内の、例えば属性ＩＩＩのデータを読み出したいときは、得られたアドレスから１を引いてメモリワード１１＿３のアドレスを求め、そのアドレスをアドレスデコーダ１６に入力してメモリワード１１＿３の内容を読み出せばよい。  尚、２回目の検索時に、属性ＩＶとデータ‘Ｄ’とからなる参照データに代わり、例えば属性ＩＶとデータ‘Ｂ’とからなる参照データで検索が行われた場合、メモリワード１１＿４については、属性は一致するため第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されている論理‘１’の信号が取り込まれるが、データが異なるため一致線１４＿４には不一致を表わす論理‘０’が出力され、第１及び第２のフラグレジスタ２３＿４，２４＿４には一致が検出されなかったことを示す論理‘０’がラッチされる。また、データ‘Ｂ’が一致するメモリワード１１＿２については属性が一致せず、したがって属性及びデータの双方も一致しない。
【００６２】
以上のようにして、図４に示す実施例では、同一の群内においては、互いに離れたメモリワードに記憶されたデータであっても、もしくはデータの順序を逆にして検索した場合であっても、検索を行うことができる。
ここで、上記実施例におけるデータ線３２＿１，３２＿２，…，は、１つの群に属するデータの数が予め定まっているものとしてその長さが固定されたものであるが、このように固定長のデータ線を備えると、１つの群に属するデータの数の最大を見積もり、最大のデータ数に対応した長さのデータ線を備える必要がある。これではその最大よりも少ない数のデータによりデータ群が構成される場合に無駄なメモリワードが発生することになる。そこで、１つの群に属するデータの数に合せてデータ線を可変長とすることが好ましい。
【００６３】
図５は、可変長のデータ線を実現する一つの方式を示した模式図である。
データ線３２が複数のメモリワード１１＿１，１１＿２，１１＿３，…に亘って延び、そのデータ線３２には、最上端のメモリワード１１＿１を除く他のメモリワード１１＿２，１１＿３，…それぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が互いにシリーズに配置されている。これらの各スイッチ４０＿２，４０＿３，４０＿４，…は、対応するメモリワード１１＿２，１１＿３，１１＿４，…と、その直ぐ上段に隣接するメモリワード１１＿１，１１＿２，１１＿３，…との間に配置されている。それらのスイッチ４０＿２，４０＿３，４０＿４，…のうちの１つおきのスイッチ４０＿２，４０＿４，４０＿６，…は第１制御線４１に出力される第１のスイッチ制御信号によりオンし、３つおきのスイッチ４０＿３，４０＿７，…は第２制御線４２に出力される第２のスイッチ制御信号によりオンし、残りのスイッチのうち７つおきのスイッチ４０＿５，…は第３制御線４３に出力される第３のスイッチ制御信号によりオンされる。
【００６４】
１つのデータ群を構成するデータの数が２の場合は、第１制御線４１に第１のスイッチ制御信号を出力することにより１つおきのスイッチ４０＿２，４０＿４，４０＿６，…をオンさせる。これにより各２つのメモリワード１１＿１；１１＿２；１１＿３，１１＿４；１１＿５，１１＿６；…毎に切断されたデータ線が形成される。また、１つのデータ群を構成するデータの数が４の場合は、第１制御線４１に第１のスイッチ制御信号を出力するとともに第２制御線４２に第２のスイッチ制御信号を出力する。すると、各４つのメモリワード１１＿１，１１＿２；１１＿３，１１＿４；１１＿５，１１＿６，…毎に切断されたデータ線が形成される。同様にして、１つのデータ群を構成するデータの数が８の場合は、第１制御線４１、第２制御線４２にそれぞれ第１および第２のスイッチ制御信号を出力するとともに、第３制御線４３に第３のスイッチ制御信号を出力する。これにより各８つのメモリワード１１＿１，…，１１＿８；１１＿９…毎に切断されたデータ線が形成される。
【００６５】
この方式によれば、１つのデータ群を構成するデータの数が２の倍数の場合はメモリワードに空きは生じないが、２の倍数以外の、例えば３，５，９等の場合空きのメモリワードが生じてしまうことになる。この空きのメモリワードが生じないように多数のスイッチ４０＿２，４０＿３，…を任意にオン，オフできるように構成すると、制御線の本数が多数本となり、またそれらの制御線にスイッチ制御信号を出力する制御回路が複雑となる。したがって、図５に示す方式は、データ線の長さを任意に制御するには不向きである。
【００６６】
図６は、可変のデータ線を実現するもう一つの方式を示した模式図である。
多数のメモリワードに亘ってデータ線３２が延び、そのデータ線３２に互いにシリーズに接続された、最上端のメモリワードを除く他のメモリワードそれぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が備えられている点は図５の場合と同じである。各メモリワードには、各属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…が備えられており、それら属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…には、図示の各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶがそれぞれ格納されている。この例は、属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…に格納された属性が属性Ｉかそれ以外の属性ＩＩ，ＩＩＩ，ＩＶかに応じて、属性Ｉの場合は対応するスイッチをオフのままとし、それ以外の属性ＩＩ，ＩＩＩ，ＩＶの場合は対応するスイッチをオンするように構成したものである。このように構成すると、１つのデータ群を構成するデータの数がいくつであっても、また、データ数の異なるデータ群が混在していても、各データ群の先頭に属性Ｉのデータを配置することにより、自動的に過不足ない数のメモリワード毎に切断されたデータ線が形成されることになる。
【００６７】
図７は、属性がＩかそれ以外かを判定する属性判定回路の一例を示す回路図である。
ここでは属性Ｉに‘０００’が割り当てられており、属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ（‘０００’）の場合オアゲートから‘０’が出力され、したがってトランジスタ４０で構成されたスイッチ４０’はオフ状態となり、そのトランジスタ４０’の両側のデータ線が電気的に切断される。属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ以外の属性の場合はオアゲートから‘１’が出力され、トランジスタ４０はオン状態となり、そのトランジスタの両側のデータ線が接続される。
【００６８】
このように、図４に示す連想メモリにおいて、１つのデータ群を構成するデータの数に応じてデータ線３２＿１，３２＿２，…の長さを調整することもできる。もちろん、属性データを利用するのではなく、専用の制御線によってスイッチを制御することによりデータ線の長さを調整してもよい。
次に、図４に示す連想メモリに本発明の技術思想を適用した、本発明の第２の連想メモリの一実施例について説明する。
【００６９】
図８は、本発明の第２の連想メモリの一実施例の特徴部分を示す回路図である。図１に示す本発明の第１の連想メモリの各構成要素に対応する構成要素には、図１に付した番号と対応する番号を付して示し、相違点を中心に説明する。
この図８には、図３に示すデータ群のうち、群番号ｎのデータ群を格納するメモリワード群、すなわち、空き状態にあるメモリワード群のうち、最優先のメモリワード群が示されている。
【００７０】
この図８に示す連想メモリには、図１に示す連想メモリと同様に、各メモリワード…，１１ １ ｎ，１１ ２ ｎ，…，１１ １ ｎ＋１，…に対応してフラグレジスタ…，５１ １ ｎ，５１ ２ ｎ，…，５１ １ ｎ＋１，…が備えられているが、これらのフラグレジスタ…，５１ １ ｎ，５１ ２ ｎ，…，５１ １ ｎ＋１，…は、後述するようにして、各メモリワード群毎に一括して制御されるが、有効なフラグレジスタは、各メモリワード群毎の先頭のフラグレジスタである。
【００７１】
また、各メモリワード…，１１ １ ｎ，１１ ２ ｎ，…，１１ １ ｎ＋１，…は、属性を格納する属性格納部…，１１ １ １ ｎ，１１ ２ １ ｎ，…，１１ １ １ ｎ＋１，…と、データを格納するデータ格納部…，１１ １ ２ ｎ，１１ ２ ２ ｎ，…，１１ １ ２ ｎ＋１，…とで構成されている。ただし、図８では、図示の都合上、属性格納部１１ １ １ ｎ，１１ ２ １ ｎ，…，１１ １ １ ｎ＋１，…とデータ格納部１１ １ ２ ｎ，１１ ２ ２ ｎ，…，１１ １ ２ ｎ＋１，…は互いに離れた位置に図示されている。
【００７２】
ここでは、群番号ｎ、群番号ｎ＋１に対応する各メモリワード群は空き状態にあり、したがってそれらのメモリワード群に対応するフラグレジスタ５１ １ ｎ，５１ ２ ｎ，５１ ３ ｎ，５１ ４ ｎ，５１ １ ｎ＋１，…には、空き状態を示す論理‘１’のフラグが格納されている。
第１のトランジスタ…，８１ １ ｎ，８１ ２ ｎ，…，８１ １ ｎ＋１，…は対応する属性格納部…，１１ １ １ ｎ，１１ ２ １ ｎ，…，１１ １ １ ｎ＋１，…から延びる制御線によりそのオン／オフが制御されるトランジスタであり、属性Ｉが格納された属性格納部…，１１ １ １ ｎ，１１ １ １ ｎ＋１，…のみがオン状態となる。したがって群番号ｎに対応する第１の可変長データ線８３ ｎには、フラグレジスタ５１ １ ｎに格納された、空き状態を表わす論理‘１’（‘Ｈ’レベル）の信号が出力され、その信号がその群番号ｎに対応するメモリワード群内の４つの複数選択分離回路５２ １ ｎ，５２ ２ ｎ，５２ ３ ｎ，５２ ４ ｎに入力される。またその第１の可変長データ線８３−ｎの信号は、その論理が反転されて、その群番号ｎに対応するメモリワード群内の４つのアンドゲート５３ １ ｎ，５３ ２ ｎ，５３ ３ ｎ，５３ ４ ｎに入力される。
【００７３】
群番号ｎ＋１に対応するメモリワード群についても同様であり、フラグレジスタ５１ １ ｎ＋１に格納された論理‘１’の信号が第１のトランジスタ８１ １ ｎ＋１、第１の可変長データ線８３ ｎ＋１を経由して、４つの複数分離選択回路５２ １ ｎ＋１，…および論理が反転されて、４つのアンドゲート５３ １ ｎ＋１，…に入力される。
【００７４】
図３に示すように、１，２，…，群番号ｎ−１に対応するメモリワード群には有効なデータ群が格納されている場合、群番号ｎに対応するメモリワード群に備えられた４つの複数分離選択回路５２ １ ｎ，５２ ２ ｎ，５２ ３ ｎ，５２ ４ ｎのうち最上段の複数分離選択回路５２ １ ｎから最優先であることを示す論理‘１’（‘Ｈ’レベル）の信号が出力される。複数分離選択回路…，５２ １ ｎ，５２ ２ ｎ，５２ １ ｎ＋１，…の出力側には、第２のトランジスタ…，８２ １ ｎ，８２ ２ ｎ，８２ １ ｎ＋１，…が備えられている。この第２のトランジスタ…，８２ １ ｎ，８２ ２ ｎ，８２ １ ｎ＋１，…は、第１のトランジスタ…，８１ １ ｎ，８１ ２ ｎ，…，８１ １ ｎ＋１，…と同様に、属性格納部…，１１ １ １ ｎ，１１ ２ １ ｎ，…，１１ １ １ ｎ＋１，…に属性Ｉが格納されている場合のみオン状態となるトランジスタであり、複数分離選択回路５２ １ ｎから出力された論理‘１’の信号は、第２のトランジスタ８２ １ ｎを通って第２の可変長データ線８４ ｎに出力される。ここでは群番号ｎに対応するメモリワード群が最優先のメモリワード群であり、したがって群番号ｎ＋１に対応するメモリワード群の複数分離選択回路５２ １ ｎ＋１の出力は論理‘０’であって、群番号ｎ＋１に対応するメモリワード群の第２の可変長データ線８４ ｎ＋１には複数分離選択回路５２ １ ｎ＋１の出力である論理‘０’の信号が供給される。
【００７５】
また各属性格納部…，１１ １ １ ｎ，１１ ２ １ ｎ，…，１１ １ １ ｎ＋１，…からは、検索時に属性の一致を受けて論理‘１’（‘Ｈ’レベル）の信号が出力される属性一致線…，３０ １ ｎ，３０ ２ ｎ，３０ １ ｎ＋１，…が延び、対応するアンドゲート…，５３ １ ｎ，５３ ２ ｎ，５３ １ ｎ＋１，…の入力端子に接続されている。また、各データ格納部…，１１ １ ２ ｎ，１１ ２ ２ ｎ，…，１１ １ ２ ｎ＋１，…からは、検索時にデータの一致を受けて論理‘１’（‘Ｈ’レベル）の信号が出力されるデータ一致線…，１４ １ ｎ，１４ ２ ｎ，１４ １ ｎ＋１，…が延び、属性一致線…，３０ １ ｎ，３０ ２ ｎ，３０ １ ｎ＋１，…と同様に、対応するアンドゲート…，５３ １ ｎ，５３ ２ ｎ，５３ １ ｎ＋１，…の入力端子に接続されている。
【００７６】
ここで、属性ＩＩ，データ‘Ｂ’の検索データを入力してデータ検索を行なったとし、属性格納部１１ ２ １ ｎに属性ＩＩが格納されているメモリワード１１ ２ ｎのデータ格納部１１ ２ ２ ｎにたまたまデータ‘Ｂ’が格納されていたとすると、属性の一致を受けて属性一致線３０ ２ ｎが‘Ｈ’レベルとなり、またデータの一致を受けてデータ一致線１４ ２ ｎも‘Ｈ’レベルとなるが、第１の可変長データ線８３ ｎが、空き状態を表わす‘Ｈ’レベルにあるため、アンドゲート５３ ２ ｎからは一致を表わす‘Ｈ’レベルの信号は出力されない。すなわち、空き状態にあるメモリワード群は、検索には参加しない。
【００７７】
この検索を行なっているときに、いずれかのメモリワード群で一致が検出されたか否かとは無関係に、追記制御回路７２（図１参照）から、ワード線活性化タイミング信号線６８に‘１’の信号が出力される。すると、図８の上から２番目のメモリワード１１ ２ ｎに対応するアンドゲート６７ ２ ｎの入力が全て‘１’となりアンドゲート６７ ２ ｎの出力側に延びるワード線２４ ２ ｎが‘１’となり、メモリワード１１ ２ ｎに検索データが書き込まれる。この検索データが書き込まれたタイミングは、検索と同時であり、したがってその検索において一致が生じたか否かとは無関係である。
【００７８】
以上のような検索と検索データの書き込みが所定回数行なわれた後、最終的に所望のデータ群が検出されたか否かの情報が追記制御回路７２（図１参照）に入力される。追記制御回路７２では、いずれかのメモリワード群において所望のデータ群が検出された場合はその後は何も行なわない。すなわち、図８に示す群番号ｎに対応するメモリワード群には検索の都度検索データが書き込まれたものの、そのメモリワード群に対応するフラグレジスタ５１ １ ｎ，５１ ２ ｎ，，５１ ３ ｎ，５１ ４ ｎには依然として空きフラグ‘１’が格納されており、群番号ｎに対応するメモリワード群は、依然として検索には寄与しない空き状態にとどまることになる。
【００７９】
一方、全体一致検出回路７１で、全てのメモリワード群にわたって所望のデータ群が検出されなかったときは、追記制御回路７２（図１参照）は、以下のように動作する。すなわち、フラグレジスタ…，５１ １ ｎ，５１ ２ ｎ，…，５１ １ ｎ＋１，…に接続された空きフラグデータ線６６に論理‘０’の信号を与え、その状態で空きフラグクロック信号線６５に‘１’のクロックパルスを与える。すると、図示の群番号ｎに対応するメモリワード群に延びる第２の可変長データ線８４ ｎに論理‘１’の信号が出力されていることから空きフラグクロック信号線６５に与えられた‘１’のクロックパルスは、４つのアンドゲート６１ １ ｎ，６１ ２ ｎ，６１ ３ ｎ，６１ ４ ｎをそれぞれ通過して４つのフラグレジスタ５１ １ ｎ，５１ ２ ｎ，５１ ３ ｎ，５１ ４ ｎに入力され、それら４つのフラグレジスタ５１ １ ｎ，５１ ２ ｎ，５１ ３ ｎ，５１ ４ ｎに、有効なデータ群が記録されていることを示す論理‘０’のフラグが格納される。
【００８０】
複数選択分離回路…，５２ １ ｎ，５２ ２ ｎ，…，５２ １ ｎ＋１，…では、群番号ｎに対応するフラグレジスタ５１ １ ｎ，５１ ２ ｎ，５１ ３ ｎ，５１ ４ ｎに‘０’が格納されたことに伴い、その群番号ｎに対応するメモリワード群以外の、空きフラグ‘１’が格納されているフラグレジスタに対応するメモリワード群の中から最も優先度の高いメモリワード群（ここに示す例では群番号ｎ＋１に対応するメモリワード群）が検出されることになる。
【００８１】
尚、図８に示す実施例では、いずれのメモリワード群にも所望のデータ群が格納されていなかったことを受けて、追記制御回路７２が、自動的に、最優先のメモリワード群（図８の例では群番号ｎに対応するメモリワード群）に対応するフラグレジスタに空き状態を解除する論理‘０’のフラグを書き込んだが、追記制御回路７２に外部から所定の制御信号を入力できるように構成しておき、追記制御回路７２では、外部からその制御信号が入力されるのを待って、最優先のメモリワード群の空き状態を解除してもよい。
【００８２】
【発明の効果】
以上説明したように、本発明の連想メモリは、検索と同時に検索データをそのまま格納してしまうものであるため、未登録データの追記が高速に行なわれる。したがって本発明の連想メモリは、例えばＬＡＮシステム等に好適である。
【図面の簡単な説明】
【図１】本発明の第１の連想メモリの一実施例の特徴部分を示す回路図である。
【図２】複数選択分離回路の回路図である。
【図３】群構造のデータの一例を示す図である。
【図４】群構造のデータを取り扱うのに適した連想メモリの一例を示すブロック図である。
【図５】可変長のデータ線を実現する一つの方式を示した模式図である。
【図６】可変のデータ線を実現するもう一つの方式を示した模式図である。
【図７】属性がＩかそれ以外かを判定する属性判定回路の一例の回路図である。
【図８】本発明の第２の連想メモリの一実施例の特徴部分を示す回路図である。
【図９】従来の連想メモリの一例を表わした回路ブロック図である。
【図１０】連想メモリ中の１つのメモリワードを表わした詳細回路図である。
【図１１】ＬＡＮの一例を示した図である。
【図１２】ブリッジの機能説明図である。
【符号の説明】
１１，１１＿１ ｎ，１１＿２ ｎ，…，１１＿１ ｎ＋１  メモリワード
１１＿１＿１ ｎ，１１＿２＿１ ｎ，…，１１＿１ １ ｎ＋１
属性格納部
１１＿１＿２ ｎ，１１＿２＿２ ｎ，…，１１＿１ ２ ｎ＋１
データ格納部
１４    一致線
１４＿１ ｎ，１４＿２ ｎ，…，１４＿１ ｎ＋１  データ一致線
３０＿１ ｎ，３０＿２ ｎ，…，３０＿１ ｎ＋１  属性一致線
５１，５１＿１ ｎ，５１＿２ ｎ，…，５１＿１ ｎ＋１  フラグレジスタ
５２，５２＿１ ｎ，５２＿２ ｎ，…，５２＿１ ｎ＋１
複数選択分離回路
【図１】
0003636382.tif 000002
【図２】
0003636382.tif 000003
【図３】
0003636382.tif 000004
【図４】
0003636382.tif 000005
【図５】
0003636382.tif 000006
【図６】
0003636382.tif 000007
【図７】
0003636382.tif 000008
【図８】
0003636382.tif 000009
【図９】
0003636382.tif 000010
【図１０】
0003636382.tif 000011
【図１１】
0003636382.tif 000012
【図１２】
0003636382.tif 000013