(57)【特許請求の範囲】
【請求項１】
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、該各格納データ毎に記憶する複数のメモリワードを備え、
各メモリワードが、該各メモリワードに対応する各アドレスを有するとともに、
各データ群を構成する複数の格納データを記憶する複数のメモリワードからなる各メモリワード群が、該各メモリワード群に対応する各代表アドレスを有することを特徴とする連想メモリ。
【請求項２】
前記代表アドレスが、該代表アドレスに対応するメモリワード群を構成する複数のメモリワードに対応する複数のアドレスのうちの１つのアドレスであることを特徴とする請求項１記載の連想メモリ。
【請求項３】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
前記代表アドレスが、該代表アドレスに対応するメモリワード群を構成する複数のメモリワードのうち前記データ群を構成する各属性を代表する所定の属性が格納されたメモリワードに対応するアドレスであることを特徴とする請求項１記載の連想メモリ。
【請求項４】
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、該各格納データ毎に記憶する複数のメモリワードと、
検索時に、入力された検索データに対応する格納データが検出された場合に、各データ群を構成する複数の格納データを記憶する複数のメモリワードからなる各メモリワード群のうち、前記対応する格納データが格納されたメモリワードが属するメモリワード群に対応する代表アドレスを出力するアドレス出力回路とを備えたことを特徴とする連想メモリ。
【請求項５】
前記アドレス出力回路が、
前記複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線と、
所定の優先順位づけに従って、活性化された一致線に対応するメモリワードの中の１つのメモリワードのアドレスを生成するプライオリティエンコーダと、
前記プライオリティエンコーダから出力された前記１つのメモリワードのアドレスを、該１つのメモリワードが属するメモリワード群に対応する代表アドレスに変換するアドレスコンバータとを備えたことを特徴とする請求項４記載の連想メモリ。
【請求項６】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
前記アドレスコンバータが、前記１つのメモリワードのアドレスに、該１つのメモリワードと、該１つのメモリワードが属するメモリワード群を構成する複数のメモリワードのうち、前記データ群を構成する各属性を代表する所定の属性が格納されたメモリワードとの間の相対アドレスを加算もしくは減算することにより、該メモリワード群に対応する代表アドレスを生成するものであることを特徴とする請求項５記載の連想メモリ。
【請求項７】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
前記アドレス出力回路が、前記複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線と、
前記属性それぞれに対応して備えられ検索時の前記属性により選択される、活性化された一致線に対応するメモリワードが属するメモリワード群に対応する代表アドレスを生成する複数のエンコード符号化回路とを具備することを特徴とする請求項４記載の連想メモリ。
【請求項８】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
前記アドレス出力回路が、前記複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線と、
一致線が活性化されたことを表わす情報を入力し、該情報の入力位置に応じたアドレスを生成するエンコード符号化回路と、
検索時の前記属性によって制御され、前記情報を、活性化された一致線に対応するメモリワードのアドレスと、該メモリワードが属するメモリワード群に対応する代表アドレスとの差分に対応する分だけ入力位置をシフトして前記エンコード符号化回路に入力するスイッチング回路とを具備することを特徴とする請求項４記載の連想メモリ。
【請求項９】
前記アドレス出力回路が、
前記メモリワード群を構成する前記複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される複数の一致線と、
前記複数のメモリワードにそれぞれ対応する複数の信号線を有し、検索時に、前記メモリワード群を構成する前記複数のメモリワードに対応する複数の前記一致線のうちのいずれか１本の一致線が活性化された場合に、この活性化された一致線に対応するメモリワードに記憶された格納データが属するデータ群を代表する格納データが記憶されたメモリワードに対応する前記信号線を活性化するゲート回路と、
所定の優先順位づけに従って、前記活性化された信号線に対応するメモリワードの中の１つのメモリワードのアドレスを生成し、該アドレスを、該１つのメモリワードが属するメモリワード群に対応する代表アドレスとして出力するプライオリティエンコーダとを備えたことを特徴とする請求項４記載の連想メモリ。
【請求項１０】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、前記ゲート回路が、前記メモリワードに格納された属性が前記データ群を構成する各属性を代表する所定の属性であり、かつ、該所定の属性が格納されたメモリワードが属するメモリワード群を構成する複数のメモリワードに対応する複数の前記一致線のうちのいずれか１本の一致線が活性化された場合に、対応する前記信号線を活性化するものであることを特徴とする請求項９記載の連想メモリ。
【請求項１１】
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、該各格納データ毎に記憶する複数のメモリワードと、
前記複数のメモリワードそれぞれに対応して備えられ、対応するメモリワードが、検索の対象とされる有効な検索データが記憶された記憶状態にあるメモリワードであるか、あるいは前記有効な検索データが記憶されておらずしたがって上書きが許容される空き状態にあるメモリワードであるかを示すエンプティフラグが記憶されるフラグレジスタと、
前記複数のメモリワードそれぞれに対応する信号線を有し、該メモリワードに格納された格納データが、該格納データが属するデータ群を代表する格納データであり、かつ、該格納データが格納されたメモリワードに対応する前記フラグレジスタに、前記空き状態を示すエンプティフラグが記憶されていた場合に、対応する前記信号線を活性化するゲート回路と、
所定の優先順位づけに従って、前記ゲート回路により活性化された前記信号線に対応するメモリワードの中の１つのメモリワードを指定するプライオリティエンコーダとを備えたことを特徴とする連想メモリ。
【請求項１２】
前記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、前記ゲート回路が、前記メモリワードに格納された属性が前記データ群を構成する各属性を代表する所定の属性であり、かつ、該所定の属性が格納されたメモリワードに対応する前記フラグレジスタに、前記空き状態を示すエンプティフラグが記憶されていた場合に、対応する前記信号線を活性化するものであることを特徴とする請求項１１記載の連想メモリ。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、一致検索の行われるデータ幅を複数のワードに拡張する機能、すなわち、連続する複数回の検索でそれぞれ一致が検出された場合に全体としての一致が検出される機能を備えた連想メモリに関する。
【０００２】
【従来の技術】
従来より、配列された複数の各メモリワードそれぞれに各ディジタルデータを記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ，内容アドレス式メモリ；Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）が提案されている。
【０００３】
図１０は、連想メモリの一例を表わした回路ブロック図である。
この連想メモリ１０には、ｍビットを１ワードとする、互いに図の横方向に並ぶｍビットのメモリセルからなる多数のメモリワード１１＿１，１１＿２，…，１１＿ｎが備えられている。またこの連想メモリ１０は、１ワードの検索データが入力されラッチされる検索データレジスタ１２を備え、検索データレジスタ１２にラッチされた検索データの全部もしくは所定の一部のビットパターンと、各メモリワード１１＿１，１１＿２，…，１１＿ｎに記憶された格納データのうち上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリワード１１＿１，１１＿２，…，１１＿ｎのそれぞれに対応して備えられた一致線１４＿１，１４＿２，…，１４＿ｎのうちビットパターンが一致したメモリワード１１＿１，１１＿２，…，１１＿ｎに対応する一致線１４＿１，１４＿２，…，１４＿ｎに論理‘１’（ここでは５Ｖとする）の一致信号が出力される。それ以外の一致線１４＿１，１４＿２，…，１４＿ｎは論理‘０’（ここでは０Ｖとする）にとどまる。
【０００４】
これらの一致線１４＿１，１４＿２，…，１４＿ｎは各フラグレジスタ１５＿１，１５＿２，…，１５＿ｎの出力線９１，９２，…，ｎを介してプライオリティエンコーダ１６に接続されており、これらの一致線１４＿１，１４＿２，…，１４＿ｎに出力された信号は、各フラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納される。ここでは、一例として、図示のように、各フラグレジスタ１５＿１，１５＿２，…，１５＿ｎにそれぞれ‘０’，‘１’，‘１’，‘０’，…，‘０’，‘０’が格納されたものとする。これらのフラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納された信号はプライオリティエンコーダ１６に入力される。プライオリティエンコーダ１６には、エンコードパルスＥＰが入力され、エンコードパルスＥＰが入力される毎に、所定の優先順位づけに従って、論理‘１’の信号が格納されたフラグレジスタ（ここではフラグレジスタ１５＿２とフラグレジスタ１５＿３の２つ）のうちの優先度の高いフラグレジスタに対応するアドレス信号ＡＤが順次出力される。ここでは、添字が若いほど優先順位が高いものとし、従ってエンコードパルスＥＰが１つだけ入力されると、フラグレジスタ１５＿２に対応するメモリアドレスが出力される。このプライオリティエンコーダ１６から出力されたアドレス信号ＡＤは、必要に応じてアドレスデコーダ１７に入力される。アドレスデコーダ１７ではこの入力されたアドレス信号ＡＤをデコードして、各メモリワード１１＿１，１１＿２，…，１１＿ｎそれぞれに対応して備えられたワード線１８＿１，１８＿２，…，１８＿ｎのうちの入力されたアドレス信号ＡＤに対応するいずれか１本のワード線（ここではワード線１８＿２）にアクセス信号（ここでは論理‘１’の信号）を出力する。これによりアクセス信号の出力されたワード線１８＿２に対応するメモリワード１１＿２に記憶されている格納データが出力レジスタ１９に読み出される。
【０００５】
次に、エンコードパルスＥＰがもう１つ入力されると、今度はフラグレジスタ１５＿３に対応するメモリワード１１＿３のアドレスを得ることができる。
上記のように、連想メモリ１０は、検索データの全部もしくは所定の一部のデータを用いて多数のメモリワード１１＿１，１１＿２，…，１１＿ｎに記憶された格納データを検索し、一致する格納データを有するメモリワードのアドレスを得、必要に応じてそのメモリワードに記憶されたデータ全体を読み出すことができるように構成されたメモリである。
【０００６】
上記のような基本構成を有する連想メモリにおいて、一致検索の対象となるデータ幅を２ワードもしくはそれ以上の複数ワードに拡張する技術が提案されている。
図１１は、データ拡張機能を備えた連想メモリの一例を示すブロック図である。図１０に示した連想メモリの構成要素と対応する構成要素には、図１０に付した符号と同一の符号を付して示し、その要素についての重複説明は省略する。
【０００７】
各メモリワード１１＿１，１１＿２，…から延びる各一致線１４＿１，１４＿２，…，は、各アンドゲート２０＿１，２０＿２，…の一方の入力端子に接続されている。また各アンドゲート２０＿１，２０＿２，…の他方の入力端子には各オアゲート２１＿２，２１＿３，…の出力端子が接続されており、各オアゲート２１＿２，２１＿３，…の一方の入力端子は、初回検索制御線２２に接続されている。ただし図示の一番上のアンドゲート２０＿１に対応するオアゲートは省略されており、そのアンドゲート２０＿１の入力端子に初回検索制御線２２が直接接続されている。
【０００８】
各アンドゲート２０＿１，２０＿２，…の出力端子は各第１のフラグレジスタ２３＿１，２３＿２，…のデータ入力端子に接続され、各第１のフラグレジスタ２３＿１，２３＿２，…の出力端子は各第２のフラグレジスタ２４＿１，２４＿２，…の入力端子に接続されている。各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子は、図１０に示すプライオリティエンコーダ１６（図１１では図示省略）に接続されるとともに、図１１の下方に隣接するメモリワードに対応するオアゲート２１＿２，２１＿３，…の入力端子に接続されている。
【０００９】
互いに対応する第１および第２のフラグレジスタ２３＿１，２４＿１，；２３＿２，２４＿２，…の各ペアが図４に示す各フラグレジスタ１５＿１，１５＿２，…に対応する。
第１のフラグレジスタ２３＿１，２３＿２，…と第２のフラグレジスタ２４＿１，２４＿２，…には、ともに、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１が入力され、その一致結果ラッチ信号Ｓ１により各データ入力端子から入力された入力データがラッチされるが、第１のフラグレジスタ２３＿１，２３＿２，…には、一致結果ラッチ信号５１の立ち上がりａの時点における入力データがラッチされ、第２のフラグレジスタ２４＿１，２４＿２，…には、一致結果ラッチ信号Ｓ１の立ち下がりｂの時点の入力データがラッチされる。
【００１０】
以上のように構成された連想メモリにおいては、以下のようにして一致検索が行われる。尚、ここでは図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４，１１＿５，１１＿６…には、各格納データＡ，Ｂ，Ｃ，Ｄ，Ｃ，Ｆ，…が格納されているものとする。
ここで、各格納データを単独に検索する際は、検索データＲＥＦ＿ＤＡＴＡを入力して検索を行う際に、初回検索制御線２２に初回検索タイミング信号Ｓ２を出力する。ここでは、検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｂ’を入力したものとすると、データ‘Ｂ’が格納されたメモリワード１１＿２に対応する一致線１４＿２に論理‘１’の一致信号が出力されてアンドゲート２０＿２に入力され、また、これとともに初回検索タイミング信号Ｓ２がオアゲート２１＿２を経由してアンドゲート２０＿２に入力されるため、アンドゲート２０＿２から論理‘１’の信号が出力される。またこのとき、他の一致線１４＿１；１４＿３，１４＿４，…には論理‘０’の信号が出力されるため、それに対応する他のアンドゲート２０＿１；２０＿３，２０＿４，…からは論理‘０’の信号が出力される。
【００１１】
アンドゲート２０＿２から出力された論理‘１’の信号は、一致結果ラッチ制御線２５に出力された一致結果ラッチ信号Ｓ１の立ち上がりａのタイミングで第１のフラグレジスタ２３＿２にラッチされ、それに引き続く一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで第２のフラグレジスタ２４＿２にラッチされる。
【００１２】
また第１のフラグレジスタ２３＿２および第２のフラグレジスタ２４＿２に論理‘１’の信号がラッチされる各タイミングで、他の第１フラグレジスタ２３＿１；２３＿３，２３＿４，…、および他の第２のフラグレジスタ２４＿１；２４＿３，；２４＿４，…には論理‘０’の信号がラッチされる。
このようにして各第２のフラグレジスタ２４＿１，２４＿２，２４＿３，…にラッチされた論理‘０’，‘１’，‘０’，…の信号が図４に示すプライオリティエンコーダ１６に入力され、メモリワード１１＿２のアドレス信号ＡＤが得られる。
【００１３】
次に、データ幅が拡張された検索を行う場合について説明する。ここでは、２ワードに拡張された、データ‘Ｂ’とデータ‘Ｃ’からなる２ワードデータを検索する場合について説明する。
この場合、先ず上記と同様にして、データ‘Ｂ’の検索を行う。これにより、メモリワード１１＿２に対応する第１および第２のフラグレジスタ２３＿２，２４＿２に論理‘１’の信号がラッチされる。次に検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｃ’を入力して検索を行うが、このときは初回検索制御線２２には初回検索タイミング信号Ｓ２は出力せずに、初回検索制御線２２は論理‘０’の状態に保っておく。検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｃ’を入力して検索を行うと、図示の２つのメモリワード１１＿３，１１＿５にそれぞれ対応する一致線１４＿３，１４＿５に論理‘１’の一致信号が出力されるが、オアゲート２１＿３には、第２のフラグレジスタ２４＿２にラッチされている論理‘１’の信号が入力されているため一致線１４＿３の一致信号はアンドゲート２０＿３を通過し、第１および第２のフラグレジスタ２３＿３，２４＿３に、一致を表わす論理‘１’の信号がラッチされる。一方オアゲート２１＿５には、第２のフラグレジスタ２４＿４にラッチされている論理‘０’の信号が入力されているため一致線１４＿５の一致信号はアンドゲート２０＿５で遮断され、第１および第２のフラグレジタ２３＿５，２４＿５には不一致を表わす論理‘０’の信号がラッチされることになる。このようにして、データ‘Ｂ’とデータ‘Ｃ’のペアからなる２ワードデータの一致検出が行われる。３ワード以上のデータの一致検出も同様にして行われる。
【００１４】
ただし、図１１に示す連想メモリは、データ幅拡張機能を備えてはいるが、２ワード，３ワード等に拡張されるデータは、互いに隣接したメモリワードに所定の順序で格納されている必要があり、検索しようとする複数のデータが互いに離れたメモリワードに格納されている場合や逆の順序、例えばデータ‘Ｃ’，データ‘Ｂ’の順序に格納されている場合には複数のデータを結合した一致検出を行うことはできない。
【００１５】
このような検索が必要となる場合のデータ構造を、図１２に示す。図１２には、それぞれ属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された４つのデータがセットとなって１つのデータ群を構成しているデータ構造が示されている。データ群および属性の概念を明確にするために一例を挙げると、例えば各群番号１，２，３，４，…毎の各データ群は各個人に属するデータであり、属性Ｉはその人の氏名，属性ＩＩはその人の生年月日、属性ＩＩＩは住所、……等を示している。
【００１６】
このように各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された複数のデータからなるデータ群を連想メモリに格納しておいて検索を行う場合に、例えば群番号１のデータ群を検索する場合を例に説明すると、データ‘Ａ’の検索とデータ‘Ｂ’の検索をこの順に行って、一致するデータ群の残りのデータ‘Ｃ’，‘Ｄ’を読み出すことだけではなく、例えばデータ‘Ａ’の検索とデータ‘Ｄ’の検索を行って残りのデータ‘Ｂ’，‘Ｃ’を読み出したい場合や、データ‘Ｂ’の検索を先に行い、次にデータ‘Ａ’の検索を行いたい場合がある。
【００１７】
しかし、上述したワード幅拡張機能を備えた連想メモリ（図１１参照）では、このような検索は不可能である。また上述した連想メモリでは、データ‘Ａ’とデータ‘Ｂ’の検索を行った場合に、図１２に示す群番号１の欄にある属性Ｉの付されたデータ‘Ａ’と属性ＩＩの付されたデータ‘Ｂ’とのペアと、群番号４の欄にある属性ＩＩの付されたデータ‘Ａ’と属性ＩＩＩの付されたデータ‘Ｂ’とのペアとの区別をすることはできず、例えば、‘氏名’という属性Ｉと‘生年月日’という属性ＩＩの情報を基にそれらが一致する特定の個人の属性ＩＩＩ，ＩＶの情報を知ろうとしても、属性ＩＩと属性ＩＩＩのペアでも一致が検出される等必要な情報以外のノイズが混入してしまうことになる。
【００１８】
このような問題を解決するために、不連続な属性における検索も可能とした新規な連想メモリを、特願平５−２４８１２１号に提案した。
【００１９】
【発明が解決しようとする課題】
しかしながら、この連想メモリにおいて、一連のデータ群中のデータについて、例えば属性毎に検索を行った場合に、一致あるいは不一致のアドレスの管理が煩雑化し、データ群が記憶されたメモリワード群を単位とした取扱いが複雑化するという問題点がある。
【００２０】
本発明は、上記事情に鑑み、データ群が記憶されたメモリワード群を単位とした取扱いが簡便化された連想メモリを提供することを目的とする。
【００２１】
【課題を解決するための手段】
上記目的を達成する本発明の第１の連想メモリは、
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
（１）それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、各格納データ毎に記憶する複数のメモリワードを備え、
（２）各メモリワードが、各メモリワードに対応する各アドレスを有するとともに、
（３）各データ群を構成する複数の格納データを記憶する複数のメモリワードからなる各メモリワード群が、各メモリワード群に対応する各代表アドレスを有する
ことを特徴とする。
【００２２】
ここで、上記本発明の第１の連想メモリにおいて、上記代表アドレスが、その代表アドレスに対応するメモリワード群を構成する複数のメモリワードに対応する複数のアドレスのうちの１つのアドレスであることが好ましい。
また、上記本発明の第１の連想メモリにおいて、上記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなる場合に、
上記代表アドレスが、その代表アドレスに対応するメモリワード群を構成する複数のメモリワードのうちデータ群を構成する各属性を代表する所定の属性が格納されたメモリワードに対応するアドレスであることが好ましい。
【００２３】
一方、上記本発明の第１の連想メモリは、一致が検出された場合にメモリワード群を単位としたアドレスによってその一致が検出されたメモリワード群を知る構成として、以下のように具体化することができる。
すなわち、そのように構成された、本発明の第２の連想メモリは、
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
（４）それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、該各格納データ毎に記憶する複数のメモリワード
（５）検索時に、入力された検索データに対応する格納データが検出された場合に、各データ群を構成する複数の格納データを記憶する複数のメモリワードからなる各メモリワード群のうち、上記対応する格納データが格納されたメモリワードが属するメモリワード群に対応する代表アドレスを出力するアドレス出力回路を備えたことを特徴とする。
【００２４】
ここで、さらに具体的には、上記（５）のアドレス出力回路は、例えば、
（５−１）複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線
（５−２）一致線が接続され、所定の優先順位づけに従って、活性化された一致線に対応するメモリワードの中の１つのメモリワードのアドレスを生成するプライオリティエンコーダ
（５−３）プライオリティエンコーダから出力された上記１つのメモリワードのアドレスを、その１つのメモリワードが属するメモリワード群に対応する代表アドレスに変換するアドレスコンバータ
を備えた構成とすることができる。
【００２５】
ここで、上記（５−１）の一致線は、上記（５−２）のプライオリティエンコーダに直接に接続されていてもよく、あるいはフラグレジスタ、ゲート回路、スイッチ等その一致線の信号を保持、変形あるいは伝達する回路を介して上記（５−２）のプライオリティエンコーダに接続されていてもよく、上記の本発明にはそれらの双方の態様が含まれる。
【００２６】
この、（５−１）〜（５−３）の構成要件を満足するアドレス出力回路を備えた場合において、上記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなる場合に、
上記（５−３）のアドレスコンバータが、上記１つのメモリワードのアドレスに、該１つのメモリワードと、該１つのメモリワードが属するメモリワード群を構成する複数のメモリワードのうち、データ群を構成する各属性を代表する所定の属性が格納されたメモリワードとの間の相対アドレスを加算もしくは減算することにより、該メモリワード群に対応する代表アドレスを生成するものであることが好ましい。
【００２７】
また、上記第２の連想メモリにおいて、例えば上記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
上記（５）のアドレス出力回路が、
（５−４）複数のメモリワードそれぞれに対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線
（５−５）上記属性それぞれに対応して備えられ検索時の属性により選択される、活性化された一致線に対応するメモリワードが属するメモリワード群に対応する代表アドレスを生成する複数のエンコード符号化回路
を具備する構成とすることも好ましい態様である。
【００２８】
また、例えば、上記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
上記（５）のアドレス出力回路が、
（５−６）複数のメモリワードそれぞれに対応して備えられ、検索時に入力された検索データに対応する格納データが記憶されていた場合に活性化される一致線
（５−７）一致線が活性化されたことを表わす情報を入力し、その情報の入力位置に応じたアドレスを生成するエンコード符号化回路
（５−８）検索時の前記属性によって制御され、上記情報を、活性化された一致線に対応するメモリワードのアドレスと、そのメモリワードが属するメモリワード群に対応する代表アドレスとの差分に対応する分だけ入力位置をシフトして前記エンコード符号化回路に入力するスイッチング回路
を具備する構成とすることもできる。
【００２９】
また、上記（５）のアドレス出力回路は、例えば、
（５−９）上記メモリワード群を構成する複数のメモリワードにそれぞれ対応して備えられ、検索時に、入力された検索データに対応する格納データが記憶されていた場合に活性化される複数の一致線
（５−１０）上記複数のメモリワードにそれぞれ対応しる複数の信号線を有し、検索時に、前記メモリワード群を構成する複数のメモリワードに対応する複数の一致線のうちのいずれか１本の一致線が活性化された場合に、この活性化された一致線に対応するメモリワードに記憶された格納データが属するデータ群を代表する格納データが記憶されたメモリワードに対応する信号線を活性化するゲート回路
（５−１１）上記信号線が接続され、所定の優先順位づけに従って、上記活性化された信号線に対応するメモリワードの中の１つのメモリワードのアドレスを生成し、該アドレスを、該１つのメモリワードが属するメモリワード群に対応する代表アドレスとして出力するプライオリティエンコーダ
を備えた構成とすることもできる。
【００３０】
ここで、上記（５−１０）の信号線は、上述した一致線（上記（５−１））の場合と同様、直接にプライオリティエンコーダに接続されていてもよく、あるいはフラグレジスタ、ゲート回路、スイッチ等、その信号線の信号を保持、変形あるいは伝達する回路を介してプライオリティエンコーダに接続されていてもよい。
【００３１】
また、上記（５−９）の一致線と、上記（５−１０）の信号線との間には、上記（５−１０）のゲート回路のみでなく、例えばフラグレジスタ、他のゲート回路、スイッチ等、一致線の信号を保持、変形あるいは伝達する回路が備えられていてもよい。
この、（５−９）〜（５−１１）の構成要件を満足するアドレス出力回路を備えた場合において、
上記格納データそれぞれが、該格納データが属するデータ群の中の位置づけを表わす属性と、該属性が付されたデータとのペアからなり、
上記ゲート回路が、メモリワードに格納された属性がデータ群を構成する各属性を代表する所定の属性であり、かつ、その所定の属性が格納されたメモリワードが属するメモリワード群を構成する複数のメモリワードに対応する複数の一致線のうちのいずれか１本の一致線が活性化された場合に、対応する信号線を活性化するものであることが好ましい。
【００３２】
また、前述した本発明の第１の連想メモリは、メモリワード群を単位して、そのメモリワード群が「記憶状態」にあるか「空き状態」にあるかを知るための構成として、以下のように具体化することができる。
すなわち、そのように具体化された、本発明の第３の連想メモリは、
多数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
（６）それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、各格納データ毎に記憶する複数のメモリワード
（７）上記複数のメモリワードそれぞれに対応して備えられ、対応するメモリワードが、検索の対象とされる有効な検索データが記憶された記憶状態にあるメモリワードであるか、あるいは有効な検索データが記憶されておらずしたがって上書きが許容される空き状態にあるメモリワードであるかを示すエンプティフラグが記憶されるエンプティフラグレジスタ
（８）上記複数のメモリワードそれぞれに対応する信号線を有し、そのメモリワードに格納された格納データが、その格納データが属するデータ群を代表する格納データであり、かつ、その格納データが格納されたメモリワードに対応する前記フラグレジスタに、空き状態を示すエンプティフラグが記憶されていた場合に、対応する信号線を活性化するゲート回路
（９）上記複数のメモリワードそれぞれに対応する信号線が接続され、所定の優先順位づけに従って、上記ゲート回路により活性化された信号線に対応するメモリワードの中の１つのメモリワードを指定するプライオリティエンコーダ
を備えたことを特徴とする。
【００３３】
ここで、上記本発明の第３の連想メモリは、上記格納データそれぞれが、その格納データが属するデータ群の中の位置づけを表わす属性と、属性が付されたデータとのペアからなり、
上記ゲート回路が、メモリワードに格納された属性がデータ群を構成する各属性を代表する所定の属性であり、かつ、その所定の属性が格納されたメモリワードに対応するフラグレジスタに、空き状態を示すエンプティフラグが記憶されていた場合に、対応する信号線を活性化するものであってもよい。
【００３４】
【作用】
本発明の第１の連想メモリは、各メモリワードが各アドレスを有するとともに、各メモリワード群が、各代表アドレスを有するものであるため、メモリワード群を単位としてアクセスする場合にはその代表アドレスを用いることにより、あるいは、そのメモリワード群内のいずれかのメモリワードをアクセスする場合には、代表アドレスと、メモリワード群内の相対アドレスを用いることにより、例えば複数のアドレスを１つのメモリワード群に対応づけるような煩雑さが回避され、メモリワード群を単位とした取扱いが簡便化される。
【００３５】
メモリワード群に対応する代表アドレスとして、メモリワードに対応するアドレスと全く別体系のアドレスを用いるよりは、そのメモリワード群を構成する複数のメモリワードのアドレスのうちの１つ、例えばそれら複数のアドレスのうちの数値の一番小さいアドレスを代表アドレスとして用いると、メモリワードのアドレスとメモリワード群のアドレスとがリンクされた解りやすいアドレス体系となる。
【００３６】
また、格納データが、属性とその属性が付されたデータとから成る場合、その属性のうちの所定の属性、例えば数値の一番小さい属性が格納されたメモリワードのアドレスをそのメモリワードが属するメモリワード群の代表アドレスとすると、メモリワードに格納データを記憶させることにより自動的に代表アドレスが定義される回路構成とすることができる。
【００３７】
また、本発明の第２の連想メモリは、上記（５）の、代表アドレスを出力するアドレス出力回路を備えたため、外部で複数のアドレスと１つのメモリワードとを対応づけるような煩雑な操作を行う必要がなく、メモリワード群を単位とした取扱いが簡便化され、使い勝手の良い連想メモリとなる。
尚、一連の検索の最後で一致が検索されたか否かは、各メモリワード群毎に、たかだか一本の一致線のみから出力される。したがってメモリワード群を構成する複数のメモリワードに対応する複数の一致線がすべてプライオリティエンコーダに接続されていても、本発明の第３の連想メモリにおける、空き状態にあるメモリワード群を認識するときとは異なり、一致が検出されたメモリワード群を認識するのに余計な時間がかかるわけではない。
【００３８】
また、本発明の第３の連想メモリは、各メモリワードに対応して備えられたエンプティフラグレジスタの出力を、そのメモリワードが、１つのデータ群が格納されるメモリワード群を代表するメモリワードであるか否かを判定するゲート回路を介してプライオリティエンコーダに入力する機能を備えているため、プライオリティエンコーダでは、各メモリワード群毎に空き状態にあるか否かが判定され、各メモリワード群が空き状態にあるか否かの検索が高速化され、データ書き込みの速度が向上する。
【００３９】
【実施例】
以下、本発明の実施例について、先願の、特願平５−２４８１２１号を参考に詳述する。
尚、本発明の第２の連想メモリの実施例あるいは本発明の第３の連想メモリの実施例は、すなわち、本発明の第１の連想メモリの実施例であるため、以下では本発明の第２の連想メモリの実施例と本発明の第３の連想メモリの実施例について説明する。
【００４０】
図６は、上記先願に係る連想メモリの一例を示すブロック図である。図１１に示す連想メモリの各構成要素と同一の構成要素には、図１１に付した符号と同一の符号を付して示し、相違点についてのみ説明する。
各メモリワード１１＿１，１１＿２，…は、属性を格納する属性格納部１１＿１＿１，１１＿２＿１，…とデータを格納するデータ格納部１１＿１＿２，１１＿２＿２，…とで構成されており、各メモリワード１１＿１，１１＿２，…には、互いに対応する属性とデータとのペアからなる格納データがそれぞれ格納されている。ここでは、図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４には、それぞれ、図１２に示す群番号１に属する、属性Ｉ，データ‘Ａ’、属性ＩＩ，データ‘Ｂ’、属性ＩＩＩ，データ‘Ｃ’、属性ＩＶ，データ‘Ｄ’が格納されている。また各メモリワード１１＿５，１１＿６，…には、それぞれ、図６に示す群番号２に属する、属性Ｉ，データ‘Ｃ’、属性ＩＩ，データ‘Ｆ’、……が格納されている。また検索にあたっては、属性とデータとのペアからなる検索データＲＥＦ＿ＤＡＴＡが入力される。
【００４１】
各メモリワード１１＿１，１１＿２には、そこに記憶された格納データ（属性及びデータの双方）が、入力された検索データ（属性及びデータの双方）と一致しているときに一致信号が出力される一致線１４＿１，１４＿２，…のほか、属性のみの一致不一致の信号が出力される属性一致線３０＿１，３０＿２，…が備えられている。尚、属性のみの一致も、属性及びデータの双方の一致も、従来の一致検出回路と同様に構成され、従来の一致検出回路は連想メモリの分野において極めて一般的な技術であるため、ここでの図示および説明は省略する。
【００４２】
各メモリワード１１＿１，１１＿２に対応して第３のフラグレジスタ３１＿１，３１＿２，…が備えられており、各属性一致線３０＿１，３０＿２，…は対応する第３のフラグレジスタ３１＿１，３１＿２，…のデータ入力端子に延びている。また、この連想メモリには、図１２に示す各データ群に属するデータが格納された複数のメモリワードからなるメモリワード群それぞれについて１本ずつデータ線３２＿１，３２＿２，…が備えられており、またデータ線３２＿１，３２＿２，…と各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子との間には各第１のスイッチ３３＿１，３３＿２，…が備えられている。これらの第１のスイッチ３３＿１，３３＿２，…は具体的にはトランジスタ等を用いて構成される。後述する他のスイッチについても同様である。各第１のスイッチ３３＿１，３３＿２，…は、対応する各第３のフラグレジスタ３１＿１，３１＿２，…に論理‘１’の信号がラッチされているときに導通され、論理‘０’の信号がラッチされているときには遮断される。各第３のフラグレジスタ３１＿１，３１＿２，…は、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで、対応する属性一致線３０＿１，３０＿２，…の信号をラッチする。
またデータ線３２＿１，３２＿２，…と各オアゲート２１＿１，２１＿２，…の入力端子との間に各第２のスイッチ３４＿１，３４＿２，…が備えられており、これら各第２のスイッチ３４＿１，３４＿２，…は、対応する属性一致線３０＿１，３０＿２，…の信号により、その信号が一致を表わす論理‘１’のときに導通状態、不一致を表わす論理‘０’の時に遮断状態となるように制御される。この遮断時における各オアゲート２１ １，２１ ２，…の入力レベルの安定化のために、この部分にプルダウン抵抗を入れるか、あるいは他の回路方式を採用してもよい。尚、この図６に示す連想メモリには、図５に示す連想メモリと異なり、図示の最上段のメモリワード１１＿１に対応するアンドゲート２０＿１の前段にもオアゲート２１＿１が備えられている。
【００４３】
以上のように構成された連想メモリにおいて、一致検索は以下のようにして行われる。
１ワード分の単独のデータ検索、および連続した複数ワードの検索のうち第１回目の検索は、図１１に示した従来のワード拡張機能付連想メモリの場合と同じであるためここでは説明は省略し、ここでは第１回目の検索において属性ＩＩとデータ‘Ｂ’とからなる検索データＲＥＦ＿ＤＡＴＡによってメモリワード１１＿２に対応する第１および第２のフラグレジスタ２３＿２，２４＿２に論理‘１’がラッチされたものとする。このとき、属性の一致を受けてメモリワード１１＿２に対応する属性一致線３０＿２に論理‘１’の信号が出力され、これにより、対応する第３のフラグレジスタ３１＿２にも論理‘１’の信号がラッチされ、対応する第１のスイッチ３３＿２がオンし、対応する第２のフラグレジスタ２４＿２に格納された、属性及びデータ双方の一致を表わす論理‘１’の信号がデータ線３２＿１に出力される。またこれとともに、対応する第２のスイッチ３４＿２もオンするが、第１回目の検索においてはこれは無用の動作である。
【００４４】
次に、属性ＩＶとデータ‘Ｄ’からなる検索データＲＥＦ＿ＤＡＴＡを入力して検索を行うものとする。このときは、図１１の連想メモリの場合と同様、初回検索制御線２２は論理‘０’に保持されている。このとき、属性の一致を受けてメモリワード１１＿４に対応する属性一致線３０＿４に論理‘１’の信号が出力され、これにより対応する第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されていた、メモリワード１１＿２に対応する第２のフラグレジスタ２４＿２の論理‘１’の信号がオアゲート２１＿４を経由してアンドゲート２０＿４に入力される。このため、メモリワード１１＿４で属性ＩＶとデータ‘Ｄ’の双方の一致が検出されて一致線１４＿４に論理‘１’の一致信号が出力され、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１により、対応する第１および第２のフラグレジスタ２３＿４，２４＿４に論理‘１’の信号がラッチされる。またこのとき、属性一致線３０＿４に出力された論理‘１’の信号が、対応する第３のフラグレジスタ３１＿４にラッチされ、対応する第１のスイッチ３３＿４がオンし、第２のフラグレジスタ２４＿４の論理‘１’の信号がデータ線３２＿１に出力される。またこの２回目の検索では、メモリワード１１＿２に対応する属性一致線３０＿２には属性の不一致を表わす論理‘０が出力されるため、対応する第３のフラグレジスタ３１＿２には‘０’が格納され、メモリワード１１＿２に対応する第１のスイッチ３３＿２はオフする。
【００４５】
これにより、メモリワード１１＿４に対応する第２のフラグレジスタ２４＿４の論理‘１’の信号が出力線１００ ４を介してプライオリティエンコーダ１６（図１０参照）に入力され、メモリワード１１＿４のアドレスが得られることになるが、メモリワード１１＿４には属性ＩＶが格納されていることは予め分かっており、同一群内の例えば属性ＩＩＩのデータを読み出したいときは、得られたアドレスから１を引いてメモリワード１１＿３のアドレスを求め、そのアドレスをアドレスデコーダ１７に入力してメモリワード１１＿３の内容を読み出せばよい。
【００４６】
一方、２回目の検索時に、属性ＩＶとデータ‘Ｄ’とからなる検索データに代わり、例えば属性ＩＶとデータ‘Ｂ’とからなる検索データで検索が行われた場合、メモリワード１１＿４については、属性は一致するため第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されている論理‘１’の信号が取り込まれるが、データが異なるため一致線１４＿４には不一致を表わす論理‘０’が出力され、第１及び第２のフラグレジスタ２３＿４，２４＿４には一致が検出されなかったことを示す論理‘０’がラッチされる。また、データ‘Ｂ’が一致するメモリワード１１＿２については属性が一致せず、したがって属性及びデータの双方も一致しない。
【００４７】
以上のようにして、図６に示す連想メモリでは、同一の群内においては、互いに離れたメモリワードに記憶されたデータであっても、もしくはデータの順序を逆にして検索した場合であっても、検索を行うことができる。
ここで、図６に示す連想メモリにおけるデータ線３２＿１，３２＿２，…，は、１つの群に属するデータの数が予め定まっているものとしてその長さが固定されたものであるが、このように固定長のデータ線を備えると、１つの群に属するデータの数の最大を見積もり、最大のデータ数に対応した長さのデータ線を備える必要がある。これではその最大よりも少ない数のデータによりデータ群が構成される場合に無駄なメモリワードが発生することになる。そこで、１つの群に属するデータの数に合せてデータ線を可変長とすることが好ましい。
【００４８】
図７は、可変長のデータ線を実現する一つの方式を示した模式図である。
データ線３２が複数のメモリワード１１＿１，１１＿２，１１＿３，…に亘って延び、そのデータ線３２には、最上端のメモリワード１１＿１を除く他のメモリワード１１＿２，１１＿３，…それぞれに対応する各スイッチ４０＿２，４０＿３，…が互いにシリーズに配置されている。これらの各スイッチ４０＿２，４０＿３，４０＿４，…は、対応するメモリワード１１＿２，１１＿３，１１＿４，…と、その直ぐ上段に隣接するメモリワード１１＿１，１１＿２，１１＿３，…との間に配置されている。それらのスイッチ４０＿２，４０＿３，４０＿４，…のうちの１つおきのスイッチ４０＿２，４０＿４，４０＿６，…は第１制御線４１に出力される第１のスイッチ制御信号によりオンし、３つおきのスイッチ４０＿３，４０＿７，…は第２制御線４２に出力される第２のスイッチ制御信号によりオンし、残りのスイッチのうち８つおきのスイッチ４０＿５，…は第３制御線４３に出力される第３のスイッチ制御信号によりオンされる。
【００４９】
１つのデータ群を構成するデータの数が２の場合は、第１制御線４１に第１のスイッチ制御信号を出力することにより１つおきのスイッチ４０＿２，４０＿４，４０＿６，…をオンさせる。これにより各２つのメモリワード１１＿１，１１＿２；１１＿３，１１＿４；１１＿５，１１＿６；…毎に切断されたデータ線が形成される。また、１つのデータ群を構成するデータの数が４の場合は、第１制御線４１に第１のスイッチ制御信号を出力するとともに第２制御線４２に第２のスイッチ制御信号を出力する。すると、各４つのメモリワード１１＿１，１１＿２，１１＿３，１１＿４；１１＿５，１１＿６，…毎に切断されたデータ線が形成される。同様にして、１つのデータ群を構成するデータの数が８の場合は、第１制御線４１、第２制御線４２にそれぞれ第１および第２のスイッチ制御信号を出力するとともに、第３制御線４３に第３のスイッチ制御信号を出力する。これにより各８つのメモリワード１１＿１，…，１１＿８；１１＿９…毎に切断されたデータ線が形成される。
【００５０】
この方式によれば、１つのデータ群を構成するデータの数が２のべき乗（＝２ｎ  ）の場合はメモリワードに空きは生じないが、それ以外の、例えば３，５，６等の場合空きのメモリワードが生じてしまうことになる。この空きのメモリワードが生じないように多数のスイッチ４０＿２，４０＿３，…を任意にオン，オフできるように構成すると、制御線の本数が多数本となり、またそれらの制御線にスイッチ制御信号を出力する制御回路が複雑となる。したがって、図７に示す方式は、データ線の長さを完全に任意に制御するには不向きである。
【００５１】
図８は、可変のデータ線を実現するもう一つの方式を示した模式図である。
多数のメモリワードに亘ってデータ線３２が延び、そのデータ線３２に互いにシリーズに接続された、最上端のメモリワードを除く他のメモリワードそれぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が備えられている点は図７の場合と同じである。各メモリワードには、各属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…が備えられており、それら属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…には、図示の各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶがそれぞれ格納されている。この例は、属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…に格納された属性が属性Ｉかそれ以外の属性ＩＩ，ＩＩＩ，ＩＶかに応じて、属性Ｉの場合は対応するスイッチをオフのままとし、それ以外の属性ＩＩ，ＩＩＩ，ＩＶの場合は対応するスイッチをオンするように構成したものである。このように構成すると、１つのデータ群を構成するデータの数がいくつであっても、また、データ数の異なるデータ群が混在していても、各データ群の先頭に属性Ｉのデータを配置することにより、自動的に過不足ない数のメモリワード毎に切断されたデータ線が形成されることになる。
【００５２】
図９は、属性がＩかそれ以外かを判定する属性判定回路の一例を示す回路図である。
ここでは属性Ｉに‘０００’が割り当てられており、属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ（‘０００’）の場合オアゲートから‘０’が出力され、したがってトランジスタ４０で構成されたスイッチはオフ状態となり、そのトランジスタ４０’の両側のデータ線が電気的に切断される。属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ以外の属性の場合はオアゲートから‘１’が出力され、トランジスタ４０はオン状態となり、そのトランジスタの両側のデータ線が接続される。
【００５３】
このように、図６に示す連想メモリにおいて、１つのデータ群を構成するデータの数に応じてデータ線３２＿１，３２＿２，…の長さを調整することもできる。もちろん、属性データを利用するのではなく、専用の制御フラグを１ビット設け、それによってスイッチを制御することによりデータ線の長さを調整してもよい。特に、制御専用のフラグビットを設けた場合、属性格納部１１ １ １，１１ ２ １，…等の値を自由に選択できる長所があり、図１２に示される群構造データの構成が更に容易になる。
【００５４】
群構造のデータを記憶しておいて一致検索を行う連想メモリにおいては、一致検索の結果知りたいのは一致したデータ群が記憶されたメモリワード群のアドレスである。ところが、上記のような連想メモリでは、多数のメモリワードそれぞれに対応して一致線が備えられ、それら多数本の一致線がすべて平等に取り扱われており、一致検索の結果出力されるのは、例えば一連の検索を行ったときの最後に一致が検出されたメモリワードのアドレスである。
【００５５】
したがってこの場合、どの複数のアドレスが１つのメモリワード群に対応しているかを外部で管理する必要があり、その管理が極めて煩わしいという問題がある。
そこで、この管理を容易化し得る手法に関して、以下に具体的に述べる。
図１は、本発明の第２の連想メモリの第１実施例の、本発明に特徴的なプライオリティエンコーダ５５の部分のみを取出して示した回路図である。
【００５６】
各メモリワード（図６参照）に対応して備えらえた各一致線１４＿１，１４＿２，…，１４＿ｎからの信号は、フラグレジスタ２３＿１，２４＿１；２３＿２，２４＿２；…等を介してプライオリティエンコーダ５５に接続されている。
プライオリティエンコーダ５５からは、エンコードパルスＥＰの入力に応じて、活性化された一致線に対応したアドレスが出力される。このアドレスは、特定のメモリワードに対応したアドレスであり、そのメモリワードが属するメモリワード群の代表アドレスとは限らない。
【００５７】
プライオリティエンコーダ５５から出力されたアドレスは、本発明にいうアドレスコンバータの一例である減算器５６に入力される。この減算器５６には、検索データを構成する属性を表わす数値（属性Ｉ，ＩＩ，ＩＩＩ，ＩＶに応じてそれぞれ‘０００’，‘００１’，‘０１０’，‘０１１’（２進数））；これを属性データＡＴＴ＿ＤＡＴＡと称する）も入力され、減算器５６では、プライオリティエンコーダ５５から出力されたアドレスからその直前に検索された属性データの値を減算する。これにより常に、プライオリティエンコーダ５５から出力されるアドレスは、対応するメモリワードが属するメモリワード群の代表アドレスＡＤとなる。すなわち、属性データＡＴＴ＿ＤＡＴＡはメモリワード群内の相対アドレスを表わしており、ここでは、そのメモリワード群を構成する複数のメモリワードのアドレスのうち値の一番若いアドレスを、そのメモリワード群の代表アドレスとしている。
【００５８】
図２は、本発明の第２の連想メモリの第２実施例のプライオリティエンコーダ５５を示した図である。
第１実施例と異なる点は、このプライオリティエンコーダ５５の構成にある。つまり、第１の実施例では、エンコード出力したアドレスに対して、その直前になされた検索の属性データの値を減算することで、そのメモリワード群を構成する複数のメモリワードのアドレスのうち値の一番若いアドレスを代表アドレスとしている。ところが、この減算のために、Δｔの処理時間が必要となる。そこでこの減算時間をなくすことを目的としたものが、本実施例である。つまり、図２に示すように、プライオリティエンコーダ５５内に属性データの種類に相当するエンコーダ５５ ａ，５５ ｂ，５５ ｃを設けておき、直前の検索がどの属性であったかによって、どのエンコーダ５５ ａ，５５ ｂ，５５ ｃを選択するかを決め、その出力からエンコードアドレスＡＤを得るものである。
【００５９】
例えば、図中の出力線１００ ２が１であり、その直前の検索が属性ＩＩ（‘００１’）に対して行なわれた場合は、ＡＴＴ ＤＡＴＡによりエンコーダ５５
ｂが選ばれる。
このエンコーダ５５ ｂの出力線１００ ２に対応する値は‘０’であり、この値がＡＤとして出力される。即ち、この出力線１００ ２のメモリワードが属するメモリワード群の一番若いアドレス‘０’が出力されたことになる。
【００６０】
ここで、このエンコーダ５５ ｂの選択は、エンコードが始まる前の直前の検索時に既にＡＴＴ ＤＡＴＡにより決定されており、第１の実施例のようなプライオリティエンコーダ５５以外の減算器５６のような遅延は不必要となる。
更に、図３に第３実施例を示す。これもまた、プライオリティエンコーダ５５の構成にその特徴がある。
【００６１】
図２は、図１に比べて減算器５６の遅延はないが、エンコーダ５５ ａ，５５ ｂ，５５ ｃを属性の種類だけ容易することが必要となり、ハードウェアの面積が増加してしまう。そこで、この点を改良したものが図３である。
プライオリティエンコーダ５５の入力となる出力線１００ １，１００ ２，…，１００ ｎとエンコーダ５５ ｅの間に、スイッチング回路５５ ｓが設けられている。
【００６２】
このスイッチング回路５５ ｓをＡＴＴ ＤＡＴＡにより制御し、エンコーダ５５ ｅへの接続位置を変えることを特徴としている。
例えば、出力線１００ ｉのものは、スイッチング回路５５ ｓにより、エンコーダ５５ ｅの（ｉ−ｋ）〜（ｉ−１）のいずれかを選択出力可能となっている。
【００６３】
ただし、ここでｋはエンコードの直前に行なわれた検索の属性の値を示すものであり、０≦ｉ≦ｎ，ｉ≧ｋの条件を満たすものである。
そこで、属性がｋの時は、エンコーダ５５ ｅの出力は、ｉ−ｋとなり、出力線１００ ｉのメモリワードが属するメモリワード群の内最も若いアドレスを出力することになる。
【００６４】
このような構成をとることで、エンコードアドレスＡＤを得るための遅延時間を最小にし、且つハードウェア面積をも最小とすることが可能となる。
また、次の実施例は、プライオリティエンコーダ５５へ入ってくる検索結果の出力に新たな改善を加えたものである。
図４は、本発明の第２の連想メモリの第４実施例の、本発明に特徴的な検索結果の出力部分のみを取出して示した回路図である。
【００６５】
ここには、図６に示すデータ線３２＿１，３２＿２，…と同一のデータ線３２＿１，３２＿２，…が示されており、このデータ線３２＿１，３２＿２，…には、図６を参照して説明したように、一致線１４＿１，１４＿２，…の信号がアンドゲート２０＿１，２０＿２，…、フラグレジスタ２３＿１，２４＿２；２３＿２，２４＿２；…、スイッチ３３＿１，３３＿２，…を介して伝達されている。
【００６６】
また、この図４には、属性格納部１１＿１＿１，１１＿２＿１，…が示されており、各属性格納部に格納された属性が属性Ｉ（‘０００’）の場合（図４の場合は、属性格納部１１＿１＿１と、属性格納部１１＿５＿１に属性Ｉ（‘０００’）が格納されている）、対応するノアゲート５７＿１，５７＿２，…（図４の場合、ノアゲート５７＿１とノアゲート５７＿５）から論理‘１’が出力される。各ノアゲート５１＿１，５１＿２，…の出力は、それぞれ、対応するアンドゲート５８＿１，５８＿２，…に、その一方の入力端子から入力される。
【００６７】
また各アンドゲート５８＿１，５８＿２，…の他方の入力端子には、対応するメモリワードが属するメモリワード群に対応するデータ線３２＿１，３２＿２，…が接続されている。また、各アンドゲート５８＿１，５８＿２，…の出力端子は、各信号線５９＿１，５９＿２，…により、プライオリティエンコーダ６０と接続されている。
【００６８】
図６を参照して説明したように、データ線３２＿１，３２＿２，…には、対応するメモリワード群を構成する何れかのメモリワードで一致が検出された場合に一致信号（論理‘１’）が出力される。したがって各アンドゲート５８＿１，５８＿２，…からは、対応するメモリワードに属性Ｉ（‘０００’）が格納されており、かつ、その対応するメモリワードが属するメモリワード群のうちのいずれかのメモリワードで一致が検出された場合に、プライオリティエンコーダ６０に論理‘１’の出力し、それ以外の場合、すなわち、対応するメモリワードが属するメモリワード群を構成するいずれのメモリワードでも一致が検出されなかったか、あるいは、一致が検出されても、対応する属性が属性Ｉ（‘０００’）以外の属性の場合は、プライオリティエンコーダ６０に論理‘０’を出力する。このようにして、プライオリティエンコーダ６０には、一致が検出されたメモリワード群を構成する複数のメモリワードのうちの先頭のメモリワードに対応するアンドゲードのみから、一致が検出された旨を表わす論理‘１’の信号が入力される。したがってプライオリティエンコーダ６０からは、エンコードパルスＥＰに従って、一致が検出されたメモリワード群の先頭アドレスが、代表アドレスＡＤとして出力されることになる。
【００６９】
尚、図４に示す実施例では、各データ群が格納されたメモリワード群の区切りのための情報として属性データが用いられているが、本発明の第３の連想メモリは、本発明の第２の連想メモリと同様、属性データを用いるものに限られるものではなく、例えば図７に示すように制御信号によってメモリワード群の区切りを定める場合にその制御信号を用いてもよいし、制御専用のフラグビットを用いてもよいことはいうまでもない。特に、制御専用のフラブビットを設けた場合、属性格納部１１ １ １，１１ ２ １，…等の値を自由に選択できる長所があり、図１２に示される群構造データの構成が更に容易になる。
【００７０】
また、以上は、検索結果の代表アドレスを求めることに関して述べられているが、連想メモリの場合、もう一つ重要なアドレスとしてデータ空きエリアのエンプティアドレスがある。以下に、この管理方法について説明する。
ただし、このエンプティアドレスに関しては、検索する属性によってその位置が変化することはなく、この点が検索結果の代表アドレスを求めることと比べ少し異なる点である。
【００７１】
エンプティとは、あるメモリワードが、そのメモリワードに、検索の対象とされる有効な検索データが記憶された「記憶状態」にあるメモリワードであるか、あるいは有効な検索データが記憶されておらずしたがって上書きが許容される「空き状態」にあるメモリワードであるかを区別するためのものであり、フラグが格納されるエンプティフラグレジスタが、各メモリワードに対応して備えられている。検索の際は、そのエンプティフラグレジスタに、対応するメモリワードが記憶状態にあることを示すフラグが記憶されていた場合に、そのメモリワードが検索の対象とされ、エンプティフラグレジスタに、対応するメモリワードが空き状態にあることをあらわすフラグが記憶されていた場合にはそのメモリワードは検索の対象から外される。
【００７２】
上述したように各メモリワードに属性とデータとの双方が格納される場合、メモリワードが記憶状態にあるか空き状態にあるかは各データ群が格納されたメモリワード群毎に行えば充分であるが、図７，図８に示すようにメモリワード群の区切りがあらかじめ定められておらず、制御信号ないし属性によりメモリワード群の区切りを定める場合、どこが区切りとなるかあらかじめはわからないため、エンプティフラグレジスタは、上記のように、各メモリワード毎に備えられる。
【００７３】
それらのエンプティフラグレジスタは、プライオリティエンコーダに接続されており、メモリワードに新たなデータを書き込もうとする際、そのプライオリティエンコーダで空き状態のメモリワードのアドレスを得、そのアドレスのメモリワードに所望のデータが書き込まれるが、本来、各データ群を格納するメモリワード群毎に空き状態にあるか否かを判定すればよいところ、各メモリワード毎のエンプティフラグレジスタがプライオリティエンコーダに接続されていると、そのプライオリティエンコーダにエンコードパルスＥＰ（図１０参照）をいくつも入力して空き状態にある所望のメモリワード群を選択する必要があり、データの書き込みの手順が複雑となり、またデータの書き込みに時間がかかるという問題がある。
【００７４】
図５は、本発明の第３連想メモリの一実施例の、本発明に特徴的な部分のみを取出して示した回路図である。
図１２に示すデータ構造を持つデータが格納されるものとし、属性Ｉに‘０００’が割り当てられるものとする。このとき属性格納部１１＿１＿１，１１＿２＿１，…，１１＿ｋ＿１，…に格納された属性が属性Ｉ（‘０００’）の場合（図５の場合は、属性格納部１１＿１＿１と属性格納部１１＿ｋ＿１に属性Ｉ（‘０００’）が格納されている）、対応するノアゲート５１＿１，５１＿２，…，５１＿ｋ，…（図５に図示の場合、ノアゲート５１＿１とノアゲート５１＿ｋ）から論理‘１’が出力される。各ノアゲート５１＿１，５１＿２，…，５１＿ｋ，…の出力は、それぞれ、対応するアンドゲート５２＿１，５２＿２，…，５２＿ｋ，…に、その一方の入力端子から入力される。
【００７５】
また各メモリワード（図５には図示せず）に対応して備えられたエンプティフラグレジスタ５３＿１，５３＿２，…，５３＿ｋ，…には、そのエンプティフラグレジスタ５３＿１，５３＿２，…，５３＿ｋ，…に対応するメモリワードが空き状態にあることを示す論理‘１’、もしくはそのメモリワードに検索の対象となる有効なデータが格納されていることを示す論理‘０’が格納されており、各エンプティフラグレジスタ５３＿１，５３＿２，…，５３＿ｋ，…に格納されている論理‘１’又は論理‘０’のデータは、対応するアンドゲート５２＿１，５２＿２，…，５２＿ｋ，…のもう一方の入力端子から入力される。アンドゲート５２＿１，５２＿２，…，５２＿ｋ，…の出力はプライオリティコーダ５４に入力される。
【００７６】
プライオリティコーダ５４にはエンコードパルスＥＰが入力され、エンコードパルスＥＰが入力される毎に、所定の優先順位に従って、論理‘１’が出力されているアンドゲート５２＿１，…に対応するメモリワードのアドレスＡＤが順次出力される。
図５に示すように構成すると、属性格納部１１＿１＿１，１１＿２＿１，…，１１＿ｋ＿１，…に属性Ｉを表わす‘０００’が格納されており、かつエンプティフラグレジスタ５３＿１，５３＿２，…，５３＿ｋ，…に空き状態を表わす論理‘１’が格納されている場合のみプライオリティエンコーダ５４に論理‘１’が入力され、属性格納部１１＿１＿１，１１＿２＿１，…，１１＿ｋ＿１に属性Ｉ以外の属性が格納されているか、あるいはフラグレジスタ５３＿１，５３＿２，…，５３＿ｋ，…に、対応するメモリワードに有効なデータが格納されていることを示す論理‘０’が格納されている場合には、プライオリティエンコーダ５４には、論理‘０’が入力される。
【００７７】
このようにプライオリティエンコーダ５４には、各データ群を代表する、属性Ｉのデータが格納されたメモリワードについてのみ、そのメモリワードが空き状態にあるときに論理‘１’が入力されるため、エンコードパルスＥＰを入力して所望のメモリワードのアドレスを得る際のシーケンスが簡単化され、所望のメモリワードへのデータ書込み速度が向上する。
【００７８】
また、このように構成することで、有効なデータ群が書き込まれている一連のメモリワードのうち、属性Ｉのデータが書き込まれているメモリワードのエンプティフラグ１ビットの値を変化させるだけで、その一連のメモリワードを空き状態にすることが可能となり、データの消去が極めて効率的に行なわれる。
尚、図５に示すプライオリティエンコーダ５４は、図１に示すプライオリティエンコーダ１６と比較し、データの書込みにあたり空き状態にあるメモリワードのアドレスを得るか検索の結果一致が検出されたメモリワードのアドレスを得るかという点が相違するのみであって、その構造は共通である。
【００７９】
また、図５に示す実施例では、各データ群が格納されたメモリワード群の区切りのための情報として属性データが用いられているが、これに限られるものではなく、例えば図７に示すように制御信号によってメモリワード群の区切りを定める場合にその制御信号を用いてもよいし、制御専用のフラグビットを用いてもよいことはいうまでもない。
【００８０】
【発明の効果】
以上説明したように、本発明の第１の連想メモリによれば、各メモリワード群が各代表アドレスを有するものであるため、メモリワード群（データ群）を単位とした取扱いが容易になる。
また、本発明の第２の連想メモリは、上記第１の連想メモリを、一致が検出されたメモリワード群のアドレスの生成に特化したものであり、外部で複数のアドレスと１つのメモリワードとを対応づけるような煩雑な操作を行う必要がなく、メモリワード群を単位とした取扱いが簡便化され、使い勝手の良い連想メモリが構成される。
【００８１】
さらに、本発明の第３の連想メモリは、上記第１の連想メモリを、空き状態にあるメモリワード群のアドレスの生成に特化したものであり、各データ群が格納された各メモリワード群を代表するメモリワードのみ、空き状態にあるか否かのデータをプライオリティエンコーダに入力するようにしたため、メモリワード群毎に空き状態にあるか否かが判定され、データを書込むメモリワードのアドレスを高速に検索することができる。
【図面の簡単な説明】
【図１】本発明の第２の連想メモリの第１実施例の、本発明に特徴的な部分を取出して示した回路図である。
【図２】本発明の第２の連想メモリの第２実施例の、本発明に特徴的な部分を取出して示した回路図である。
【図３】本発明の第２の連想メモリの第３実施例の、本発明に特徴的な部分を取出して示した回路図である。
【図４】本発明の第２の連想メモリの第４実施例の、本発明に特徴的な部分を取出して示した回路図である。
【図５】本発明の第３の連想メモリの一実施例の、本発明に特徴的な部分を取出して示した回路図である。
【図６】連想メモリの一例を示すブロック図である。
【図７】可変長のデータ線を実現する一つの方式を示した模式図である。
【図８】可変のデータ線を実現するもう一つの方式を示した模式図である。
【図９】属性判定回路の一例を示す回路図である。
【図１０】連想メモリの一例を表わした回路ブロック図である。
【図１１】データ拡張機能を備えた連想メモリの一例を示すブロック図である。
【図１２】群構造のデータの一例を示す図である。
【符号の説明】
１１＿１，１１＿２，…  メモリワード
１１＿１＿１，１１＿２＿１，…  属性格納部
１１＿１＿２，１１＿２＿２，…  データ格納部
１４＿１，１４＿２，…  一致線
１６  プライオリティエンコーダ
１７  アドレスデコータ
１８＿１，１８＿２，…  ワード線
２０＿１，２０＿２，…  アンドゲート
２１＿１，２１＿２，…  オアゲート
２３＿１，２３＿２，…  第１のフラグレジスタ
２４＿１，２４＿２，…  第２のフラグレジスタ
２５  一致結果ラッチ制御線
３０＿１，３０＿２，…  属性一致線
３１＿１，３１＿２，…  第３のフラグレジスタ
３２＿１，３２＿２，…  データ線
３３＿１，３３＿２，…  第１スイッチ
３４＿１，３４＿２，…  第２スイッチ
５１＿１，５１＿２，…  オアゲート
５２＿１，５２＿２，…  アンドゲート
５３＿１，５３＿２，…  フラグレジスタ
５４，５５，６０  プライオリティエンコーダ
５６  減算器
【図１】
0003605168.tif 000002
【図２】
0003605168.tif 000003
【図３】
0003605168.tif 000004
【図４】
0003605168.tif 000005
【図５】
0003605168.tif 000006
【図６】
0003605168.tif 000007
【図７】
0003605168.tif 000008
【図８】
0003605168.tif 000009
【図９】
0003605168.tif 000010
【図１０】
0003605168.tif 000011
【図１１】
0003605168.tif 000012
【図１２】
0003605168.tif 000013