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