JPH08221991A - 連想メモリにおける複数選択分離方法および装置 - Google Patents

Abstract

(57)【要約】 【目的】 検索動作によって選択された複数個のワード
の中からアドレスの昇順（降順）に順次１つのワードを
分離指示する動作を少ない検索動作回数で実行する。 【構成】 検索動作（１）の結果、検索応答とエンコー
ダ出力を装置外部に出力し（２）、選択ワードが１個の
ときはワードの分離は終了とし、その後、新たなキーデ
ータを生成する（８）。選択ワードが複数の場合には、
これをさらに１個ずつに分離するために新たなキーデー
タを生成する。これには使用したキーデータのＬＳＢか
ら続く一連の“ｘ”の内、対応するエンコーダ出力が
“１”である一番左側にある“ｘ”を“０”とする
（５）。選択ワードなしの場合には新たなキーデータを
生成する（４）。この動作を繰り返す構成を特徴として
いる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、検索動作によって選択
された複数個のワードの中から順次１つのワードを分離
指示する複数選択分離動作を少ない検索動作回数で実現
する連想メモリにおける複数選択分離方法および連想メ
モリ装置に関するものである。

【０００２】

【従来の技術】連想メモリ装置では、検索動作によって
複数のワードが選択される可能性がある。複数のワード
が選択された場合、選択されたワードのデータあるいは
アドレスを装置外部に出力するためには、選択された複
数個のワードの中から順次１つのワードを分離指示する
複数選択分離動作を行なう必要がある。この複数選択分
離動作の実現法としては、複数選択分離回路と呼ばれる
専用の論理回路を用いるハード的な方法と、検索対象の
ビット位置を指定するマスクデータと検索のキーデータ
を変更しながら複数回の検索動作を繰返すソフト的な方
法の２種類に大別でき、それぞれ各種の構成、方法が知
られている。

【０００３】ハード的な方法では複数選択分離回路が必
要であり、このため装置価格が上昇したり、同一ハード
量で実現できる連想メモリ装置の容量が低下するという
欠点がある。さらに、連想メモリ装置を大容量化してワ
ード数が増加した場合、検索動作に代表される連想メモ
リ装置の動作と整合した速度で動作する複数選択分離回
路を構成することが難しくなり、これが装置全体の動作
速度を低下させたり、あるいは実現容量を決定するとい
う可能性もあり、連想メモリ装置の高性能化、大容量
化、低価格化に対する阻害要因となる。

【０００４】ソフト的な複数選択分離動作の実現法とし
ては、少ない検索動作回数でこれを実現する２つの方法
が知られている。第１の方法は、R.R.Seeber and A.B.L
indquist,"Associative Memory with Ordered Retrieva
l," IBM J.Jan.1962,pp.126に示されている。この方法
では、検索動作によって選択されたワードが１つあるか
否かを示すシングルヒットフラグ（ＳＨ）と検索動作に
よって選択されたワードが複数あるか否かを示すマルチ
ヒットフラグ（ＭＨ）を出力できる連想メモリ装置を前
提としており、当初の検索で検索対象外であったデータ
内容の大小順に読み出すことができる。なお、ＳＨは選
択されたワードがあるか否かを示す信号とＭＨとから容
易に生成することができる。連想メモリ装置外部では、
ＳＨとＭＨを見ながら検索対象とするビット位置とキー
データを順次変更して繰返し検索動作を行なって複数選
択分離動作を実現する。この方法では、選択されたワー
ドがあるか否かを示す信号のみを生成出力しＭＨを生成
出力する機能を持たない連想メモリ装置の場合と比較
し、平均的には複数選択分離に必要な検索動作回数は少
なくてすむが、分離すべきデータ内容によっては、多く
の検索動作回数を必要とするという欠点がある。

【０００５】ソフト的な複数選択分離動作の第２の方法
は、Ｍ．Ｈ．Ｌｅｗｉｎ ”Ｒｅｔｒｉｅｖａｌ ｏｆ
Ｏｒｄｅｒｅｄ Ｌｉｓｔｓ ｆｒｏｍ ａ Ｃｏｎ
ｔｅｎｔ−Ａｄｄｒｅｓｓｅｄ Ｍｅｍｏｒｙ，” Ｒ
ＣＡ Ｒｅｖｉｅｗ Ｊｕｎｅ １９６２，ｐｐ．２１
５に示されている。この方法では、選択されたワードの
同一ビット位置のデータ内容が、すべて“１”か、すべ
て“０”か、あるいは“１”と“０”の混在かを出力で
きる連想メモリ装置を前提としており、当初の検索で検
索対象外であったデータ内容の大小順に読み出すことが
できる。連想メモリ装置外部では、この出力を見ながら
検索対象とするビット位置とキーデータを順次変更して
繰返し検索動作を行なって複数選択分離動作を実現す
る。この方法では、無駄な検索動作が存在せず、どの検
索動作においても少なくとも１個以上のワードを分離で
きるため、第１の方法と比較して、つねに分離のために
必要な検索動作の回数は少なくなる。しかし、選択され
たワードの同一ビット位置のデータ内容が、すべて
“１”か、すべて“０”か、あるいは“１”と“０”の
混在かを出力するには、きわめて多くのハード量が必要
であり、現実的には実現できないという欠点がある。

【０００６】一方、対応するワードのワードアドレスと
ともに該ワードアドレスの相補の情報が記憶され該検索
結果に応じて駆動される読出し専用型メモリであって複
数のワード線が駆動された場合には各ビットの出力値と
してワード線が駆動された複数のワードの同一ビット位
置に記憶されていた論理値の論理積あるいは論理和を出
力する読出し専用型メモリと、該読出し専用型メモリか
らのワードアドレスを装置外部へ出力する手段と、検索
動作によって選択されたワードがあるか否かおよび複数
個のワードが選択されているか否かの信号を生成し装置
外部へ出力する手段を備えた連想メモリ装置が、特願平
５−２３４１６号に示されている。これは、ＳＨあるい
はＭＨを少ないハード量で高速に生成することができる
連想メモリ装置である。

【０００７】また、キーデータと固定記憶データの一部
もしくは全部との一致を検出して内容を出力する読出し
専用型の連想ＲＯＭの回路が特許第１３９８８４８号に
示されている。

【０００８】さらに、アドレスの任意ビットをマスクす
ることで、マスクされたビットの情報に無関係にアドレ
スをデコードするマスカブルアドレスデコーダをもつ連
想メモリ装置が特許第１３２００３１号に示されてい
る。

【０００９】

【発明が解決しようとする課題】以上説明したように、
従来の連想メモリにおける複数選択分離方法では、次の
ような欠点があることがわかる。 （１）上記第１の方法では、分離すべきデータ内容によ
っては、多くの検索動作回数が必要であった。 （２）上記第２の方法では、選択されたワードの同一ビ
ット位置のデータ内容が、すべて“１”か、すべて
“０”か、あるいは“１”と“０”の混在かを出力する
には、きわめて多くのハード量が必要であり、現実的に
は実現できないという欠点があった。

【００１０】本発明にかかる請求項１乃至８に記載の発
明は、通常の連想メモリ装置のもつ、アドレスエンコー
ダに類する読出し専用型メモリの出力とアドレスに対す
る検索機能と検索動作によって選択されたワードがある
か否かおよび複数個のワードが選択されているか否かの
信号を用いることを特徴とし、その目的は、検索動作に
よって選択された複数個のワードの中からアドレスの昇
順あるいは降順に順次１つのワードを分離指示する複数
選択分離動作を少ない検索動作回数で実行する連想メモ
リにおける複数選択分離方法および連想メモリ装置を実
現することにある。

【００１１】

【課題を解決するための手段】請求項１に記載の連想メ
モリにおける複数選択分離方法の発明は、アドレスに対
する検索結果と、複数のワード線が駆動された場合には
各ビットの出力値としてワード線が駆動された複数のワ
ードの同一ビット位置に記憶されていた論理値の論理積
あるいは論理和を出力する読出し専用型メモリで構成さ
れたアドレスエンコーダからの出力と、先に用いたキー
データとマスクデータとから、検索動作によって選択さ
れたワードがあるか否かおよび複数個のワードが選択さ
れているか否かの信号に応じて、新たなキーデータとマ
スクデータを生成して検索動作を繰り返すものである。

【００１２】請求項２に記載の連想メモリ装置の発明
は、読出し専用型メモリからワードアドレスが記憶され
ているビット位置の出力とワードアドレスの相補の情報
が記憶されているビット位置の出力を装置外部へ出力す
る手段を備えたものである。

【００１３】請求項３記載の連想メモリにおける複数選
択分離方法の発明は、アドレスに対する検索結果と、読
出し専用型メモリからワードアドレスが記憶されている
ビット位置の出力と、ワードアドレスの相補の情報が記
憶されているビット位置の出力と、先に用いたキーデー
タとマスクデータとから、検索動作によって選択された
ワードがあるか否かおよび複数個のワードが選択されて
いるか否かの信号に応じて、新たなキーデータとマスク
データを生成して検索動作を繰返すものである。

【００１４】請求項４に記載の連想メモリ装置の発明
は、読出し専用型メモリからワードアドレスが記憶され
ているビット位置の出力と、ワードアドレスが記憶され
ているビット位置の出力とワードアドレスの相補の情報
が記憶されているビット位置の出力の論理をとった結果
を装置外部へ出力する手段を備えたものである。

【００１５】請求項５に記載の連想メモリにおける複数
選択分離方法の発明は、アドレスに対する検索結果と、
ワードアドレスが記憶されているビット位置の出力とワ
ードアドレスの相補の情報が記憶されているビット位置
の出力の論理をとった結果と、先に用いたキーデータと
マスクデータとから、検索動作によって選択されたワー
ドがあるか否かおよび複数個のワードが選択されている
か否かの信号に応じて、新たなキーデータとマスクデー
タを生成して検索動作を繰返すものである。

【００１６】請求項６に記載の連想メモリにおける複数
選択分離方法の発明は、ワードアドレスをあらかじめ記
憶させる第１のフィールドおよびワードアドレスを記憶
する読出し専用型メモリとして、記憶情報が固定であっ
て検索結果を生成することができる読出し専用型連想メ
モリを用いるものである。

【００１７】請求項７に記載の連想メモリにおける複数
選択分離方法の発明は、ワードアドレスをあらかじめ記
憶させる第１のフィールドとして、記憶情報が固定であ
って検索結果を生成することができるマスカブルアドレ
スデコーダを用いるものである。

【００１８】請求項８に記載の連想メモリ装置の発明
は、複数選択分離方法を実行する論理回路ブロックおよ
び制御回路ブロックを備えたものである。

【００１９】

【作用】請求項１に記載の発明においては、検索動作に
よって選択されたワードがあるか否かおよび複数個のワ
ードが選択されているか否かの信号のみを用いる方法と
比較し、等しいかあるいは、より少ない検索動作回数で
複数選択分離動作を実行できる。

【００２０】請求項２に記載の発明においては、検索動
作で複数個のワードが選択された場合、選択された複数
個のワードのアドレスの各ビット毎の等価的な論理積お
よび論理和を装置外部へ出力できる。

【００２１】請求項３に記載の発明においては、請求項
１の発明と比較し、等しいかあるいは、より少ない検索
動作回数で複数選択分離動作を実行できる。

【００２２】請求項４に記載の発明においては、検索動
作で複数個のワードが選択された場合、選択された複数
個のワードのアドレスの各ビットの値が“０”のみか、
“１”のみか、“０”と“１”の混在かを各ビット対応
に装置外部へ出力できる。

【００２３】請求項５に記載の発明においては、請求項
３の発明と比較し、少ない装置外部での処理と等しい検
索動作回数で複数選択分離動作を実行できる。

【００２４】請求項６に記載の発明においては、固定的
なデータであるアドレスの検索機能と読出しが、少ない
ハード量の読出し専用型連想メモリで実行される。

【００２５】請求項７に記載の発明においては、固定的
なデータであるアドレスの検索機能が、通常の連想メモ
リ装置に広く用いられているマスカブルアドレスデコー
ダで実行される。

【００２６】請求項８に記載の発明においては、複数選
択分離動作が装置に備えられた論理回路ブロックと制御
回路ブロックで実現され、装置外部での処理が軽減され
る。

【００２７】

【実施例】図１は、本発明の第１の実施例であり、請求
項１に記載の発明に対応し、複数のワード線が駆動され
た場合には各ビットの出力値としてワード線が駆動され
た複数のワードの同一ビット位置に記憶されていた論理
値の論理和を出力するアドレスエンコーダと、選択され
たワードがあるか否かおよび複数個のワードが選択され
ているか否かの信号を出力できる連想メモリ装置におけ
る複数選択分離方法の処理手順を示したものである。図
２、図３、図４は、それぞれ第１の実施例で前提とした
連想メモリ装置の構成例を示している。説明の都合上、
はじめに、第１の実施例を実施するための連想メモリ装
置の例を図２〜４により説明する。

【００２８】図２、図３、図４は、それぞれ第１の実施
例で前提とした連想メモリ装置の構成例（公知）であ
り、いずれも４ワード構成の場合を示している。図２に
おいて、１０１〜１０４はデータを記憶するとともに検
索動作を行って検索結果を生成できる連想メモリのワー
ドであり、１０５は複数の連想メモリのワードで構成さ
れた連想メモリワードアレイであり、キーデータやマス
クデータ等を格納するレジスタやデータの入出力のため
の回路等が含まれる。１０６は前記連想メモリワードア
レイ１０５へのデータの入出力端子であり、記憶データ
の入出力、キーデータ、マスクデータの入力等に使用さ
れる。１０８は所定のフィールド（便宜上、第１のフィ
ールドという）を示しており、対応するワードアドレス
が記憶されていることを示している。１１１〜１１４
は、それぞれ対応するワードの検索結果を供給する信号
線である。１２０は複数のワード線が駆動された場合に
は各ビットの出力値としてワード線が駆動された複数の
ワードの同一ビット位置に記憶されていた論理値の論理
和を出力するアドレスエンコーダで、読出し専用型メモ
リであり、対応するワードアドレスが記憶されているこ
とを示している。１２１は前記アドレスエンコーダ１２
０の出力端子であり、１２２は選択されたワードがある
か否かおよび複数個のワードが選択されているか否かの
信号を生成する回路ブロック、１２３は前記回路ブロッ
ク１２２で生成された信号の出力端子である。

【００２９】図３において、１５０は読出し専用型の連
想ＲＯＭであり、ワードアドレスが格納されていること
を示している。連想ＲＯＭ１５０は、複数のワード線が
駆動された場合には各ビットの出力値としてワード線が
駆動された複数のワードの同一ビット位置に記憶されて
いた論理値の論理和を出力するように構成でき、格納さ
れているワードアドレスに対する検索とアドレスエンコ
ードの両機能を実現する。１５１〜１５４は、連想ＲＯ
Ｍ１５０からの検索結果を供給する信号線であり、１５
５は、連想メモリ装置のワードアレイ部であり、１５６
は前記ワードアレイ部１５５へのデータの入出力端子で
あり、本連想メモリ装置の場合、アドレスデータもこの
入出力端子１５６から入出力される。１６１〜１６４
は、連想ＲＯＭ１５０からの検索結果と連想メモリワー
ドからの検索結果の論理積をとり、各ワードに対応する
検索結果を生成する論理回路である。なお、本構成例は
連想ＲＯＭ１５０と連想メモリのワードの関係を模式的
に示したものであり、実際には一体として構成できる。
その他は図２と同じである。

【００３０】図４において、１３０はマスカブルアドレ
スデコーダであり、ワードアドレスが格納されているこ
とを示している。１３１〜１３４はマスカブルアドレス
デコーダ１３０の出力線であり、１３５は連想メモリの
ワードアレイ部であり、１３６はワードアレイ部１３５
へのデータの入出力端子である。１４１〜１４４は、マ
スカブルアドレスデコーダ１３０の出力と連想メモリワ
ードからの検索結果の論理積をとり、各ワードに対応す
る検索結果を生成する論理回路である。その他は図２と
同様である。

【００３１】以下、図１から図４を用いて、本発明の連
想メモリにおける複数選択分離方法を説明する。

【００３２】図１において、（１）〜（８）は各ステッ
プを示す。ステップ（１），（２）は連想メモリ装置の
動作であり、ステップ（３）〜（８）は装置外部での処
理を示している。図１において、キーデータとしてはア
ドレスに対応する部分のみを示しており、左側が上位ビ
ット、右側が下位ビットとしている。また、マスクデー
タにおいてマスクされているビットをキーデータ“ｘ”
と表している。図１において、ステップ（３）の処理
は、複数選択分離の対象となるワードを検索する通常の
データを対象とした検索動作と同時に実行可能である
が、ここでは本発明の複数選択分離方法の一部として説
明する。ステップ（４），（５），（６）の処理は、検
索動作によって選択されたワードがないか、複数か、１
個かによって切替えて実行されるが、選択されたワード
がないか、複数か、１個かは、装置から出力された、検
索動作によって選択されたワードがあるか否かおよび複
数個のワードが選択されているか否かの信号から容易に
判断できる。装置から選択されたワードがないか、複数
か、１個かを示す信号を出力することも容易に可能であ
る。

【００３３】図２から図４に示した連想メモリ装置が、
図１の処理手順を実行するに必要な機能をもつことは明
らかである。

【００３４】図１の処理手順による複数選択分離動作の
具体例を図５および図６に示す。

【００３５】図５は、１０ビットのアドレスをもつ５個
のワードが選択された場合を示しており、（ａ）が選ば
れたワードのアドレスであり、（ｂ）は図１の処理手順
に従って順次検索動作を行なった時のキー＆マスクデー
タと検索応答、エンコーダ出力およびその検索動作で選
択されたワードのＩＤを示している。検索応答の“Ｐ”
は、複数個のワードが選択されていることを示し、検索
応答の“１”は１個のワードが選択されていることを示
し、検索応答の“０”はワードが選択されていないこと
を示している。図１および図５から、本複数選択分離方
法により、選択された複数個のワードがアドレスの昇順
に分離されていることがわかる。必要な検索動作回数は
１５回である。一方、第１の方法が提案された文献
Ｒ．Ｒ．Ｓｅｅｂｅｒａｎｄ Ａ．Ｂ．Ｌｉｎｄｑｕｉ
ｓｔ，”Ａｓｓｏｃｉａｔｉｖｅ Ｍｅｍｏｒｙ ｗｉ
ｔｈ Ｏｒｄｅｒｅｄ Ｒｅｔｒｉｅｖａｌ，” ＩＢ
Ｍ Ｊ．Ｊａｎ．１９６２，ｐｐ．１２６ では、図５
に示した５個のアドレスと同一のデータを分離するため
には、２５回の検索動作が必要であることが示されてお
り、本発明の複数選択分離方法が少ない検索動作回数で
分離を実現していることがわかる。

【００３６】図６は、１０ビットのアドレスをもつ２個
のワードが選択された場合を示しており、（ａ）が選ば
れたワードのアドレスであり、（ｂ）は図１の処理手順
に従って順次検索動作を行なった時のキー＆マスクデー
タと検索応答、エンコーダ出力およびその検索動作で選
択されたワードのＩＤであり、（ｃ）は同一のデータに
対して前述した従来例における第１の方法を適用した場
合を示している。図１および図６から、本複数選択分離
方法により、選択された複数個のワードがアドレスの昇
順に分離されていることがわかる。本発明の複数選択分
離方法に必要な検索動作回数は３回であるのに対し、第
１の方法では、２１回の検索動作回数が必要であり、き
わめて高速化が図れていることがわかる。図１で処理手
順を示した本発明の複数選択分離方法に必要な検索動作
回数は、多くの場合、第１の方法で必要な検索動作回数
より少なくてすみ、最悪の場合でも第１の方法で必要な
検索動作回数と等しくなる。

【００３７】以上説明したように、本発明により、付加
的なハードを必要とすることなく、高速な複数選択分離
動作が実現できることがわかる。なお、図１の処理手順
は、複数のワード線が駆動された場合には各ビットの出
力値としてワード線が駆動された複数のワードの同一ビ
ット位置に記憶されていた論理値の論理和を出力するア
ドレスエンコーダあるいは連想ＲＯＭを用い、ワードア
ドレスの昇順に１つのワードを分離指示する複数選択分
離動作を実現する複数選択分離方法を示しているが、こ
れは、複数のワード線が駆動された場合には各ビットの
出力値としてワード線が駆動された複数のワードの同一
ビット位置に記憶されていた論理値の論理積を出力する
アドレスエンコーダあるいは連想ＲＯＭを用いたり、ワ
ードアドレスの降順に分離するといった処理手順も本発
明により構成できることは明らかである。さらに、図１
において装置外部で処理するとして説明したステップ
（３）〜（８）の処理について、これらの処理を実行す
る論理回路ブロックおよび制御回路ブロックを装置内部
に付与できることも明らかである。

【００３８】図７、図８は本発明の第２、第３の実施例
であって、請求項２，３，６，７，８に記載の発明に対
応するものである。図７は読出し専用型メモリからのワ
ードアドレスが記憶されているビット位置の出力とワー
ドアドレスの相補の情報が記憶されているビット位置の
出力を切り替えて同一端子から装置外部へ出力する手段
を具備した連想メモリ装置の構成例であり、４ワード構
成の場合を示している。図８は図７に示すような連想メ
モリ装置における複数選択分離方法の処理手順を示した
ものである。

【００３９】図７において、２２０はワードアドレスと
ともに該ワードアドレスの相補の情報が記憶され、該検
索結果に応じて駆動される読出し専用型メモリであっ
て、複数のワード線が駆動された場合には、各ビットの
出力値としてワード線が駆動された複数のワードの同一
ビット位置に記憶されていた論理値の論理和を出力する
読出し専用型メモリであり、対応するワードアドレスと
相補情報が記憶されていることを示している。２２１は
読出し専用型メモリ２２０からのワードアドレスが記憶
されているビット位置の出力２２２とワードアドレスの
相補の情報が記憶されているビット位置の出力２２３を
切り替え回路２２４によって切り替えて装置外部へ出力
する端子である。その他は図２と同じである。

【００４０】図８において、（１１）〜（１８）は各ス
テップを示す。ステップ（１２）〜（１４）は連想メモ
リ装置の動作であり、ステップ（１１）〜（１８）は装
置外部での処理を示している。図８において、キーデー
タとしてはアドレスに対応する部分のみを示しており、
左側が上位ビット、右側が下位ビットとしている。ま
た、マスクデータにおいてマスクされているビットをキ
ーデータ“ｘ”と表している。図８において、ステップ
（１１）の処理は、複数選択分離の対象となるワードを
検索する通常のデータを対象とした検索動作と同時に実
行可能であるが、ここでは本発明の複数選択分離方法の
一部として説明する。ステップ（１４），（１６）の処
理は、検索動作によって選択されたワードが複数か、１
個かによって切り替えて実行されるが、選択されたワー
ドが複数か、１個かは、装置から出力された、検索動作
によって選択されたワードがあるか否かおよび複数個の
ワードが選択されているか否かの信号から容易に判断で
きる。装置から選択されたワードが複数か、１個かを示
す信号を出力することも容易に可能である。

【００４１】以下、図７と図８を用いて説明する。図７
に示した連想メモリ装置が、図８の処理手順を実行する
に必要な機能をもつことは明らかである。図８の処理手
順による複数選択分離動作の具体例を図９に示す。

【００４２】図９は、１０ビットのアドレスをもつ５個
のワードが選択された場合を示しており、（ａ）が選ば
れたワードのアドレスであり、図５（ａ）と同一であ
る。（ｂ）は図８の処理手順に従って順次検索動作を行
なった時のキー＆マスクデータと検索応答、読出し専用
型メモリからの１回目の出力と２回目の出力およびその
検索動作で選択されたワードのＩＤを示している。検索
応答のＰは、複数個のワードが選択されていることを示
し、検索応答の“１”は１個のワードが選択されている
ことを示している。

【００４３】図８および図９から、本複数選択分離方法
により、選択された複数個のワードがアドレスの昇順に
分離されていることがわかる。必要な検索動作回数は９
回であり、第１の実施例と比べてさらに高速化されてい
ることがわかる。本発明の複数選択分離方法で必要な検
索操作回数は、M.H.Lewin "Retrieval of Ordered List
s from a Content-Addressed Memory," RCA Review Jun
e 1962,pp.215 に示された第２の方法の検索動作回数と
つねに等しい。これは、読出し専用型メモリからのワー
ドアドレスが記憶されているビット位置の出力とワード
アドレスの相補の情報が記憶されているビット位置の出
力を比較することにより、第２の方法でいうところの、
選択されたワードの同一ビット位置のデータ内容が、す
べて“１”か、すべて“０”か、あるいは“１”と
“０”の混在かを検出しているためである。

【００４４】以上説明したように、本発明により、わず
かな付加ハードで、高速な複数選択分離動作が実現でき
ることがわかる。なお、図７の連想メモリ装置および図
８の処理手順は、複数のワード線が駆動された場合には
各ビットの出力値としてワード線が駆動された複数のワ
ードの同一ビット位置に記憶されていた論理値の論理和
を出力する読出し専用型メモリを用い、該読出し専用型
メモリの出力を２回に分けて同一端子から出力し、ワー
ドアドレスの昇順に１つのワードを分離指示する複数選
択分離動作を実現する連想メモリ装置と複数選択分離方
法を示しているが、これは、複数のワード線が駆動され
た場合には各ビットの出力値としてワード線が駆動され
た複数のワードの同一ビット位置に記憶されていた論理
値の論理積を出力する読出し専用型メモリを用いたり、
多くの出力端子を用いて該読出し専用型メモリの出力を
１度に装置外部に出力したり、ワードアドレスの降順に
分離するといった連想メモリ装置および処理手順も本発
明により構成できることは明らかである。さらに、図８
において装置外部で処理するとして説明したステップ
（１１），（１５）〜（１８）の処理について、これら
の処理を実行する論理回路ブロックおよび制御回路ブロ
ックを装置内部に付与できることも明らかである。ま
た、図７に示すような連想メモリ装置が、図３、図４の
場合と同様、連想ＲＯＭやマスカブルアドレスエンコー
ダを用いても構成できることも明らかである。

【００４５】図１０は本発明の第４の実施例であって、
請求項４，５に記載の発明に対応し、読出し専用型メモ
リからのワードアドレスが記憶されているビット位置の
出力とワードアドレスの相補の情報が記憶されているビ
ット位置の出力の論理をとり、これと読出し専用型メモ
リからのワードアドレスが記憶されているビット位置の
出力とを切り替えて同一端子から装置外部へ出力する手
段を具備した連想メモリ装置の構成であり、４ワード構
成の場合を示している。図１０において、２３１は前記
読出し専用型メモリ２２０からのワードアドレスが記憶
されているビット位置の出力と、読出し専用型メモリ２
２０からのワードアドレスが記憶されているビット位置
の出力とワードアドレスの相補の情報が記憶されている
ビット位置の出力の論理をとった結果を切り替えて装置
外部へ出力する端子であり、２３４は読出し専用型メモ
リからのワードアドレスが記憶されているビット位置の
出力と、読出し専用型メモリ２２０からのワードアドレ
スが記憶されているビット位置の出力とワードアドレス
の相補の情報が記憶されているビット位置の出力の論理
をとった結果を切り替える処理を行なう論理回路ブロッ
クである。その他は図７と同様である。

【００４６】以下、図１０を用いて本発明による連想メ
モリ装置と複数選択分離方法を説明する。図１０の論理
回路ブロック２３４では、読出し専用型メモリ２２０か
らのワードアドレスが記憶されているビット位置の出力
とワードアドレス相補の情報が記憶されているビット位
置の出力の対応するビット毎に論理積をとり、これと、
読出し専用型メモリ２２０からのワードアドレスが記憶
されているビット位置の出力とを切り替えて出力する。
これにより、ワードアドレスが記憶されているビット位
置の出力とワードアドレスの相補の情報が記憶されてい
るビット位置の出力がともに“１”の場合のみ、“１”
を出力することとなり、先に示した第３の実施例の場合
に必要であった、読出し専用型メモリからの１回目の出
力と２回目の出力の論理処理が不要であり、２回目の出
力が“１”であるビットを対象に第３の実施例と同様な
処理を進めればよいことがわかる。

【００４７】以上説明したように、本発明により、わず
かな付加ハードで、高速な複数選択分離動作が実現でき
ることがわかる。また、図１０に示すような連想メモリ
装置が、図３、図４の場合と同様、連想ＲＯＭやマスカ
ブルアドレスエンコーダを用いても構成できることも明
らかである。

【００４８】

〔請求項１に記載の発明に関して〕

（１）従来知られていた連想メモリ装置を用いて、付加
的なハードを必要とすることなく、高速な複数選択分離
動作が実現できる。 （２）複数選択分離のための膨大なハードを搭載する必
要がないため、同一ハードウェア量でより大容量の連想
メモリ装置を構成できるとともに、低価格化も図れる。 （３）複数選択分離のための回路によって、動作速度が
規定されるということがなく、高速に動作する連想メモ
リ装置を実現できる。複数選択分離のための回路は、連
想メモリ装置が大容量になるに従い、その動作に時間が
かかるため、本発明は、連想メモリ装置が大容量になれ
ばなるほど、その効果を発揮する。 〔請求項２，３に記載の発明に関して〕 （４）わずかなハードを付加するだけで、より高速な複
数選択分離動作を実現できるとともに、上記（２）と
（３）の効果をあわせもつ。 〔請求項４，５に記載の発明に関して〕 （５）複数選択分離動作を実効する際の、装置外部での
処理が簡単になり、ひいては連想メモリ装置を含むシス
テム全体としての低価格化が図れる。 〔請求項６に記載の発明に関して〕 （６）読出し専用型の連想ＲＯＭを用いることにより必
要なハード量が低減できるため、同一ハードウェア量で
より大容量の連想メモリ装置を構成できるとともに、低
価格化も図れる。 〔請求項７に記載の発明に関して〕 （７）通常の連想メモリ装置がもつアドレスエンコーダ
にマスク機能を付与するだけでアドレスに対する検索機
能が実現でき必要なハード量が低減できるため、同一ハ
ードウェア量でより大容量の連想メモリ装置を構成でき
るとともに、低価格化も図れる。 〔請求項８に記載の発明に関して〕 （８）連想メモリ装置外部からの制御なしで複数選択分
離動作を実現できるため、外部装置が不要になるととも
に、外部装置で動作速度が規定されるということがな
く、より高速に動作する連想メモリ装置が実現できる。

【図面の簡単な説明】

【図１】本発明の第１の実施例であり、連想メモリ装置
における複数選択分離方法の処理手順を示したフローチ
ャートである。

【図２】第１の実施例で前提とした連想メモリ装置の第
１の構成例を示すブロックである。

【図３】第１の実施例で前提とした連想メモリ装置の第
２の構成例を示すブロック図である。

【図４】第１の実施例で前提とした連想メモリ装置の第
３の構成例を示すブロック図である。

【図５】第１の実施例における複数選択分離動作の第１
の具体例の説明図である。

【図６】第１の実施例における複数選択分離動作の第２
の具体例の説明図である。

【図７】本発明の第２の実施例であって、高速な複数選
択分離動作を実現する連想メモリ装置の構成例を示すブ
ロック図である。

【図８】本発明の第３の実施例であって、図７に示すよ
うな連想メモリ装置における複数選択分離方法の処理手
順を示したフローチャートである。

【図９】第２、第３の実施例における複数選択分離動作
の具体例の説明図である。

【図１０】本発明の第４の実施例であって、高速な複数
選択分離動作を実現する連想メモリ装置の構成例を示す
ブロック図である。

【符号の説明】

１０１ ワード １０２ ワード １０３ ワード １０４ ワード １０５ 連想メモリワードアレイ １０６ 入出力端子 １１１ 信号線 １１２ 信号線 １１３ 信号線 １１４ 信号線 １２０ アドレスエンコーダ １２１ 出力端子 １２２ 回路ブロック １２３ 出力端子 １３０ マスカブルアドレスデコーダ １３１ 出力線 １３２ 出力線 １３３ 出力線 １３４ 出力線 １３５ ワードアレイ部 １３６ 入出力端子 １４１ 論理回路 １４２ 論理回路 １４３ 論理回路 １４４ 論理回路 ２２０ 読出し専用型メモリ ２２１ 端子 ２２２ 出力 ２２３ 出力 ２３１ 端子 ２３４ 論理回路ブロック

Claims (8)

【特許請求の範囲】
1. 【請求項１】 データを記憶するとともにキーデータと
   マスクデータを用いた検索動作によって該記憶されたデ
   ータに対する検索結果を生成する複数個のワードと、対
   応するワードのワードアドレスが記憶され該検索結果に
   応じて駆動される読出し専用のメモリであって複数のワ
   ード線が駆動された場合には各ビットの出力値としてワ
   ード線が駆動された複数のワードの同一ビット位置に記
   憶されていた論理値の論理積あるいは論理和を出力する
   読出し専用型メモリと、該読出し専用型メモリからの出
   力を装置外部へ出力する手段と、該検索動作によって選
   択されたワードがあるか否かをおよび複数個のワードが
   選択されているか否かの信号を生成し装置外部へ出力す
   る手段を備えた連想メモリ装置における複数選択分離方
   法であって、 選択されている複数のワードの中から順次１つのワード
   を分離指示する複数選択分離動作を実現するに際し、各
   ワードに記憶するデータの一部として当該ワードのワー
   ドアドレスをあらかじめ所定のフィールドに記憶させて
   おくとともに、検索動作によって選択されたワードがあ
   るか否かおよび複数個のワードが選択されているか否か
   の信号に応じて、装置外部へ出力された該読出し専用型
   メモリからの出力と先に用いたキーデータとマスクデー
   タとから生成した所定のフィールドに対するキーデータ
   とマスクデータを用いた検索動作を繰り返し、ワードア
   ドレスの降順あるいは昇順に１つのワードを分離指示す
   る複数選択分離動作を実現することを特徴とする連想メ
   モリにおける複数選択分離方法。
2. 【請求項２】 データを記憶するとともにキーデータと
   マスクデータを用いた検索動作によって該記憶されたデ
   ータに対する検索結果を生成する複数個のワードと、対
   応するワードのワードアドレスとともに該ワードアドレ
   スの相補の情報が記憶され該検索結果に応じて駆動され
   る読出し専用のメモリであって複数のワード線が駆動さ
   れた場合には各ビットの出力値としてワード線が駆動さ
   れた複数のワードの同一ビット位置に記憶されていた論
   理値の論理積あるいは論理和を出力する読出し専用型メ
   モリと、該読出し専用型メモリからのワードアドレスが
   記憶されているビット位置の出力を装置外部へ出力する
   手段と、該検索動作によって選択されたワードがあるか
   否かおよび複数個のワードが選択されているか否かの信
   号を生成し装置外部へ出力する手段を備えた連想メモリ
   装置において、該読出し専用型メモリからのワードアド
   レスが記憶されているビット位置の出力とワードアドレ
   スの相補の情報が記憶されているビット位置の出力を装
   置外部へ出力する手段を付与したことを特徴とする連想
   メモリ装置。
3. 【請求項３】 請求項２に記載の連想メモリ装置を用
   い、選択されている複数のワードの中から順次１つのワ
   ードを分離指示する複数選択分離動作を実現するに際
   し、各ワードに記憶するデータの一部として当該ワード
   のワードアドレスをあらかじめ所定のフィールドに記憶
   させておくとともに、検索動作によって選択されたワー
   ドがあるか否かおよび複数個のワードが選択されている
   か否かの信号に応じて、装置外部へ出力された該読出し
   専用型メモリからのワードアドレスが記憶されているビ
   ット位置の出力と、ワードアドレスの相補の情報が記憶
   されているビット位置の出力と、先に用いたキーデータ
   とマスクデータとから生成した該所定のフィールドに対
   するキーデータとマスクデータを用いた検索動作を繰返
   し、ワードアドレスの降順あるいは昇順に１つのワード
   を分離指示する複数選択分離動作を実現することを特徴
   とする連想メモリにおける複数選択分離方法。
4. 【請求項４】 ワードアドレスの相補の情報が記憶され
   ているビット位置の出力に替えて、該読出し専用型メモ
   リからのワードアドレスが記憶されているビット位置の
   出力とワードアドレスの相補の情報が記憶されているビ
   ット位置の出力の論理をとった結果を装置外部へ出力す
   る手段を付与したことを特徴とする請求項２に記載の連
   想メモリ装置。
5. 【請求項５】 請求項４に記載連想メモリ装置を用い、
   選択されている複数のワードの中から順次１つのワード
   を分離指示する複数選択分離動作を実現するに際し、各
   ワードに記憶するデータの一部として当該ワードのワー
   ドアドレスをあらかじめ所定のフィールドに記憶させて
   おくとともに、検索動作によって選択されたワードがあ
   るか否かおよび複数個のワードが選択されているか否か
   の信号に応じて、装置外部へ出力された、ワードアドレ
   スが記憶されているビット位置の出力とワードアドレス
   の相補の情報が記憶されているビット位置の出力の論理
   をとった結果と、先に用いたキーデータとマスクデータ
   とから生成した第１のフィールドに対するキーデータと
   マスクデータを用いた検索動作を繰返し、ワードアドレ
   スの降順あるいは昇順に１つのワードを分離指示する複
   数選択分離動作を実現することを特徴とする連想メモリ
   における複数選択分離方法。
6. 【請求項６】 当該ワードのワードアドレスをあらかじ
   め記憶させる所定のフィールドおよびワードアドレスを
   記憶する読出し専用型メモリとして、記憶情報が固定で
   あって検索結果を生成することができる読出し専用型連
   想メモリを用いることを特徴とする請求項１，３，５の
   いずれかに記載の複数選択分離方法。
7. 【請求項７】 当該ワードのワードアドレスをあらかじ
   め記憶させる所定のフィールドとして、記憶情報が固定
   であって検索結果を生成することができるマスカブルア
   ドレスデコーダを用いることを特徴とする請求項１，
   ３，５のいずれかに記載の連想メモリにおける複数選択
   分離方法。
8. 【請求項８】 請求項１，３，５，６，７のいずれかに
   記載の複数選択分離方法を実行する論理回路ブロックお
   よび制御回路ブロックを備えたことを特徴とする請求項
   ２または４に記載の連想メモリ装置。