JPH0550078B2

JPH0550078B2 -

Info

Publication number: JPH0550078B2
Application number: JP59225233A
Authority: JP
Inventors: Hachiro Yamada; Tsunesuke Takahashi
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1984-10-26
Filing date: 1984-10-26
Publication date: 1993-07-28
Also published as: JPS61104496A

Description

【発明の詳細な説明】（産業上の利用分野）この発明は連想記憶装置すなわち記憶内容に基
づいて番地づけを行なうことのできる記憶装置に
関する。

（従来技術とその問題点）この種の連想記憶装置は電子計算機の一つの構
成要素として使われる重要な装置である。連想記
憶装置の応用例は「大型プロジエクトによる超高
性能電子計算機」（通商産業省工業技術院編集、
日本産業技術振興協会発行47年７月発行）の
PP45〜48に述べられている。これによると連想
記憶装置は、バツフアメモリのセレクタが主記憶
装置のどのアドレスに対応するかを記憶し、論理
アドレスから物理アドレスへのアドレス変換を内
容探索によつて高速に行なうことを可能にする。
また、日経エレクトロニクス（1980.10.27発行）
の102〜136ページには、リスト処理、画像処理、
データベースへの応用が記載されている。

この種の連想記憶装置に使われる連想記憶素子
については既に多くの文献にたとえば「情報処理
ハンドブツク）に掲載されている「論理記憶」
（47年５月オーム社発行、情報処理学会編集、
PP13〜96〜PP13〜99）などに紹介されている。
これによると、この種の連想記憶装置は情報を記
憶しうる各記憶素子ごとに記憶内容と探索情報と
の一致を調べる一致検出回路を設けた構成の連想
記憶素子を必要とする。従つて所望のデータの格
納位置を示すアドレスを供給することによりアク
セスされる通常の記憶装置に使われる記憶素子に
比べ、従来の連想記憶素子は構成が複雑であり、
そのビツト当りのコストが数十倍におよぶという
欠点を有していた。

この欠点を除去するため、情報を記憶する部分
に通常の記憶素子を用い、ワード単位に一致検出
回路を設けた連想記憶装置が従来考えられてい
た。しかし、この連想記憶装置の探索にはビツト
数に対応した回数の探索動作が必要である欠点を
有していた。

さらに、探索情報をアドレス入力とし、データ
情報を記憶する第１の通常の記憶素子と、データ
情報あるいは第１の通常の記憶素子の読取り出力
をアドレス入力とし、探索情報を記憶する第２の
通常の記憶素子とを用いた連想記憶装置が特開昭
49−73039に開示されている。しかし、この連想
記憶装置は通常の記憶素子で構成できる利点を有
しているが、探索情報あるいはデータ情報のビツ
ト数が多くなると、必要とする記憶素子数が著し
く増大し、価格上昇をもたらす欠点を有してい
る。

（発明の目的）本発明は上記従来の欠点を容易に解決し、アド
レスを供給することによりアクセスされる通常の
記憶素子で構成され、高速、大容量、低価格な連
想記憶装置を提供することにある。

また、本発明の他の目的は、探索情報の一部を
マスクしての探索動作が可能である連想記憶装置
を提供することにある。

さらに、本発明の他の目的は、探索情報の一部
の誤りを許容できる連想記憶装置を提供すること
にある。

（発明の構成）従つて、本発明によれば以下の連想記憶装置が
得られる。

入力データをアドレス入力とし、入力データで
指定されワードのみ異なるデータを、書込みアド
レスで指定されるビツトに記憶する第１の記憶手
段と、書込みアドレスで指定されるワードに登録
時の入力データを記憶する第２の記憶手段と、入
力データと第２の記憶手段の読取り出力とを入力
とし、いずれか一方を選択的に第１の記憶手段の
アドレス入力に供給する選択回路と、第１の記憶
手段の書込みアドレスで指定されるビツトへの書
込みを制御する書込みデコーダと、第１の記憶手
段の読み取り信号を取込む一時記憶手段と、この
出力につながるエンコード手段と、この出力を入
力とし、一時記憶手段のリセツトを行なうデコー
ド手段とを備えたことを特徴とする連想記憶装
置、および外部から供給される一次データの一部
を変調して入力データを発生する探索情報変調手
段と、入力データをアドレス入力とし、入力デー
タで指定されるワードのみ異なるデータを、書込
みアドレスで指定されるビツトに記憶する第１の
記憶手段と、書込みアドレスで指定される第１の
記憶手段のビツト位置に書き込みを行なう書込み
手段と、第１の記憶手段の読み取り信号を取込む
一時記憶手段と、この出力につながるエンコード
手段と、この出力を入力とし、一時記憶手段のリ
セツトを行なうデコード手段とを備えたことを特
徴とする連想記憶装置である。

（実施例）以下、図面を用いて本発明のさらに詳細な説明
を行なう。

第１図は本発明による連想記憶装置の一例の構
成図を示す。この連想記憶装置は入力データ１０
１を入力とし、それに整合するデータが格納され
ている探索アドレスを出力するものであり、入力
データ１０１をアドレス入力とする第１の記憶手
段１１０と、書込みアドレス１５１で指定される
第１の記憶手段１１０のビツト位置に入力データ
１０１のデコード結果を格納させる書込み手段１
５０と、第１の記憶手段１１０の各読取り信号１
０２を取込むレジスタ１２０と、レジスタ１２０
の内容が“１”であるビツト位置を示す探索アド
レス１３１を出力するエンコーダ１３０と、探索
アドレス１３１で指定されたレジスタ１２０のビ
ツトのリセツトを行なうデコーダ１４０とからな
る。レジスタ１２０、エンコーダ１３０、デコー
ダ１４０は各々一時記憶手段、エンコード手段、
デコード手段に対応する。

第１の記憶手段１１０は所望のデータの格納位
置を示すアドレスを与えることによりアクセスさ
れる通常の記憶素子で構成される。この連想記憶
装置の記憶構成をＮワードＭビツトとすると、第
１の記憶手段１１０の記憶セル数は2MワードＮ
ビツトとなり、入力データ１０１のビツト数はＭ
ビツトとなる。またレジスタ１２０のビツト数と
エンコーダ１３０の入力ビツト数と、デコーダ１
４０の出力ビツト数は各々Ｎビツトとなり、また
エンコーダ１３０の出力あるいはデコーダ１４０
の入力となる探索アドレス１３１のビツト数は
log₂Nとなる。

この連想記憶装置は登録、削除、探索の３つの
動作を行なう。入力データ１０１は登録動作時に
は登録情報として与えられ、探索動作時には探索
情報として与えられる。以下に第１の記憶手段１
１０の全内容が“０”にクリアされている状態か
ら登録動作、削除動作、探索動作について順次に
説明を行なう。

登録動作において、書込みアドレス１５１と
“１”の登録／削除信号１５２と書込みパルス信
号１５３とが書込み手段１５０に与えられ、入力
データ１０１として登録情報が第１の記憶手段１
１０に与えられる。登録／削除信号１５２は
“１”と“０”により各々登録動作と削除動作と
を選択する。第１の記憶手段１１０は登録情報１
０１を受けて、登録情報１０１で指定されるワー
ドのアクセスを許可する。この状態で書込み手段
１５０は書込みアドレス１５１で指定される第１
の記憶手段１１０のビツト位置に登録／削除信号
１５２で指示される“１”を書込むように書込み
制御信号１５４を与える。これにより、第１の記
憶手段１１０の登録情報１０１と書込みアドレス
１５１とで指定されたビツトに“１”が格納され
る。すなわち、登録情報１０１はそれで指定され
るアドレスのみ“１”となるビツトパタンで第１
の記憶手段１１０に格納される。このビツトパタ
ーンは登録情報１０１のデコード結果と等しい。

同様に削除動作は第１の記憶手段１１０の書込
みアドレス１５１で指定されるビツト“０”を格
納させるように書込み手段１５０に“０”の登
録／削除信号１５２を与えることで登録動作と同
様に行なわれる。この削除動作により、第１の記
憶手段１１０の書込みアドレス１５１で指定され
るビツト位置の全てのアドレスの内容は“０”に
クリアされる。

探索動作を説明するにあたり、先に説明した登
録動作により、この連想記憶装置に登録情報Ａ、
Ｂ、Ｃ、Ｉが各々書込みアドレス０、１、２、ｊ
で指定されるアドレスに登録されているものとす
る。すなわち、第１の記憶手段１１０の第０ビツ
トのＡ番地、第１ビツトのＢ番地、第２ビツトの
Ｃ番地、第ｊビツトのＩ番地にのみ“１”が格納
されている。探索動作では入力データ１０１とし
てＡ、Ｂ、Ｃ、Ｉが与えられたとき、各々探索ア
ドレス１３１として、０、１、２、ｊが出力され
ることが必要である。

まず、入力データ１０１として探索情報Ａが与
えられると、第１の記憶手段１１０のＡ番地の内
容が読取り信号１０２として出力される。この読
取り信号１０２は先に登録されている登録データ
Ａ、Ｂ、Ｃ、Ｉが各々異なつているならば、第０
ビツトのみ“１”となる。読取り信号１０２は探
索情報１０１に同期して与えられる探索クロツク
信号１２１により、レジスタ１２０に取込まれ、
エンコーダ１３０に供給される。エンコーダ１３
０の入力は第０ビツトのみ“１”である。“１”
である入力は連想記録装置内に探索情報Ａに整合
するデータが登録されていることを意味する。エ
ンコーダ１３０は入力内に“１”の入力があれ
ば、マツチ信号１３２と共に“１”の入力のビツ
ト位置を探索アドレス１３１として出力する。こ
の場合、エンコーダ１３０の第０ビツトの入力の
み“１”であるので、探索アドレスは０となる。
すなわち、探索情報Ａが格納されているアドレス
が探索アドレス１３１として出力される。プロセ
ツサ等の外部機器は探索アドレス１３１を読取つ
た後にリセツト信号１４１をデコーダ１４０に与
える。デコーダ１４０はレジスタ１２０内の探索
アドレス１３１で指定されるビツトのリセツト入
力にリセツト信号１４１を供給し、そのビツトの
内容を“１”から“０”に変える。探索情報Ａに
整合するデータが一個だけならば、マツチ信号１
３２の発生が止まり、探索動作も完了する。

但し、探索情報Ａに整合する複数のデータが登
録されている場合の多重マツチ時には、さらにマ
ツチ信号１３２と次の整合データの格納アドレス
を示す探索アドレス１３１がエンコーダ１３０に
より発生される。この場合、外部機器はマツチ信
号１３２が発生しなくなるまで、繰返し、探索ア
ドレス１３１の読取りと共にリセツト信号１４１
を与えることで、探索情報に整合する全ての探索
アドレス１３１を求めることができる。

第２図は第１図の連想記憶装置に用いられた書
込み手段１５０の一実施例の説明図である。この
書込み手段は書込みデコーダ２１０で構成され、
書込みパルス信号１５３を書込みアドレス１５１
で指定されるビツト位置の書込み許可信号２１１
として導く。登録／削除信号１５２と書込み許可
信号２１１は書込み制御信号１５４として第１図
の第１の記憶手段１１０の各ビツトに供給され
る。登録／削除信号１５２は第１の記憶手段１１
０の書込みデータとなり、登録動作時に“１”、
削除動作時に“０”となる。

この書込み手段により、書込みアドレス１５１
で指定された第１の記憶手段１１０に登録／削除
信号１５２で示されるデータを格納することがで
きる。

第３図は第１図の連想記憶装置に用いられた書
込み手段１５０の他の実施例の説明図である。こ
の書込み手段は書込みデコーダ２１０とオアゲー
ト３１０とスイツチ３２０とで構成され、書込み
アドレス１５１と登録／削除信号１５２と書込み
パルス信号１５３とを受けて、第１図の第１の記
憶手段１１０に書込み許可信号２１１とビツト電
源３２１とを書込み制御信号１５４として供給す
る。ビツト電源３２１は第１の記憶手段１１０の
各ビツトに対する電源となり、このビツト電源３
２１の供給が一時的に止められた第１の記憶手段
１１０のビツトの内容は“０”にクリアされる。
このために、第１の記憶手段１１０として、スイ
ツチング速度が異なるトランジスタで記憶セルの
フリツプフロツプが構成されたスタテイツク
RAMや、電源の切断により記憶セルの電荷が放
電されるダイナミツクRAMで構成される。この
ビツト電源のオン・オフはスイツチ３２０で行な
われる。各スイツチ３２０には電源３２２とオア
ゲート３１０の出力とが接続される。“０”のオ
アゲート３１０の出力につながるスイツチ３２０
は電源３２２の通貨を禁止し、ビツト電源３２１
を切断する。

削除動作時には削除動作を示す“０”の登録／
削除信号１５２と負パルスの書込みパルス信号１
５３と書込みアドレス１５１とが供給される。書
込みデコーダ２１０は書込みパルス信号１５３を
書込みアドレス１５１で指定されるビツト位置に
書込み許可信号２１１として導く。この書込み許
可信号２１１はオアゲート３１０を介してスイツ
チ３１０を切断させる。従つて、書込みアドレス
１５１で指定されるビツト位置のビツト電源３２
１が切断され、第１の記憶手段１１０の書込みア
ドレス１５１で指定されたビツトの全アドレスの
内容が“０”にクリアされる。すなわち、削除動
作がなされる。

登録動作は削除動作と一対になり行なわれる。
まず、登録動作は削除動作で既に登録されている
データを削除し、次に登録／削除信号１５２を
“１”に戻し、再度書込みパルス信号１５３をデ
コーダ２１０に与える。再度の書込みパルス信号
１５３の供給時には第１の記憶手段１１０の全て
のビツトにビツト電源３２１が供給され、書込み
アドレス１５１で指定された第１の記憶手段１１
０のビツトに書込み許可信号２１１が与えられ
る。第１の記憶手段１１０の書込みデータとして
は常に“１”を与えておくことで、第１の記憶手
段１１０の入力データ１０１で指定されたアドレ
スの書込みアドレス１５１で指定されるビツトに
“１”が書込まれる。このようにして、登録情報
として与えられた入力データ１０１の登録が可能
となる。

この書込み手段は登録動作あるいは削除動作に
おいて、既に登録されているデータを入力データ
１０１として与える必要がないため、より使い易
い連想記憶装置の実現を可能にする。

第４図は第１図の連想記憶装置に用いられた書
込み手段１５０の他の実施例の説明図である。第
４図は破線で囲まれた書込み手段１５０と他の構
成要素との接続関係を理解しやすくするため、連
想記憶装置の全体の構成も示す。この書込み手段
は書込みアドレス１５１をアドレス入力とし、入
力データ１０１を記憶する第２の記憶手段４１０
と、入力データ１０１と第２の記憶手段４１０の
読取り出力である登録済みデータ４１１とを入力
とし、登録／削除信号１５２によりいずれか一方
を選択的に第１の記憶手段１１０のアドレス入力
に供給する選択回路４２０とから構成される。第
４図に示す連想記憶装置の記憶構成をＮワードＭ
ビツトとすると、第２の記憶手段４１０の記憶構
成もＮワードＭビツトとなる。

登録動作に際して、内容“１”が格納されてい
るアドレスで表現される形式で第１の記憶手段１
１０の各ビツトに格納された登録情報は、第１の
記憶手段１１０の各ビツトに対応する第２の記憶
手段４１０のアドレスにも格納される。例えば、
登録データＡ、Ｂ、Ｃ、Ｉを各々書込みアドレス
０、１、２、ｊで指定されるアドレスに登録する
と、第１の記憶手段１１０には第１図と同様に第
０ビツトのＡ番地、第１ビツトのＢ番地、第２ビ
ツトのＣ番地、第ｊビツトのＩ番地のみ“１”が
格納され、第２の記憶手段４１０には０、１、
２、ｊ番地に各々Ａ、Ｂ、Ｃ、Ｉが格納される。

すなわち、“１”の登録／削除信号１５２を与
えて第１図の連想記憶装置と同じ登録動作を行な
うことで、第１の記憶手段に登録情報を格納し、
さらに第２の記憶手段４１０の書込みアドレス１
５１で指定されるアドレスに登録情報となる入力
データ１０１を格納する。これにより、登録動作
がなされる。なお、第２の記憶手段４１０の内容
である登録済みデータは次に説明する削除動作で
利用される。

削除動作では“０”の登録／削除信号１５２を
与え、書込みアドレス１５１で示される第２の記
憶手段４１０の内容すなわち登録済みデータ４１
１を第１の記憶手段１１０のアドレス入力に供給
する。さらに、第１図の連想記憶装置の削除動作
と同様に書込みパルス信号１５３を書込みデコー
ダ２１０に供給することで、第１の記憶手段１１
０の書込みアドレス１５１で示されるビツトの内
容“１”は“０”に書換えられ、登録済みデータ
は削除される。

なお、登録動作に際しては、まず登録済みデー
タを消すためにこの削除動作を行なう必要があ
る。

この連想記憶装置は第２図の書込み手段を用い
た第１図の連想記憶装置の削除動作に必要であつ
た登録済みデータを外部機器から与える必要もな
く、また第２の記憶手段４１０の読取り出力を外
部に出力することにより容易に登録済みデータ４
１１を確認できる。

第５図は第２の本発明による連想記憶装置の一
実施例の説明図である。この連想記憶装置は第１
図、第４図の連想記憶装置に比べよりビツト数の
多い探索情報を取扱うことができ、探索情報の一
部をマスキングしての探索が可能である。このた
め、第２図や第３図の書込み手段を用いた第１図
の連想記憶装置に論理積手段となるアンドゲート
５１０とマスク手段となるオアゲート５２０と計
数手段となるカウンタ５３０とが追加されてい
る。

この連想記憶装置の記憶構成をＮワードＭ×Ｋ
ビツトとすると、第１の記憶手段１１０の記憶構
成は2^M×ＫワードＮビツトになり、カウンタ５３
０のビツト数はlog₂Kビツトとなる。従つて、こ
の第１の記憶手段１１０は第１図における2^Mワー
ドの第１の記憶手段１１０をブロツクとすると、
Ｋブロツクで構成される。第０ブロツクはアドレ
ス０〜2^M−１、第Ｋ−１ブロツクはアドレス（Ｋ
−１）×2^M〜Ｋ×2^M−１のアドレス範囲となる。
ブロツクの指定はカウンタ５３０により行なわれ
る。Ｍ×Ｋビツトの探索情報や登録情報はＭビツ
トの入力データ１０１Ｋ個に分割されて第１の記
憶手段１１０に送られる。Ｋ個の入力データ１０
１で送られる登録情報は入力データ１０１毎に第
１の記憶手段１１０の各ブロツクに格納される。
例えば、４つのＭビツトデータA₀、A₁、A₂、A₃
からなる登録情報Ａは第１の記憶手段１１０の第
０ブロツクのアドレスA₀と第１ブロツクのアド
レスA₁と第２ブロツクのアドレスA₂と第３ブロ
ツクのアドレスA₃のみ“１”にセツトした状態
で格納される。

さらに詳細に登録動作及び削除動作と探索動作
について説明する。

まず、先に示した４つのＭビツトデータA₀、
A₁、A₂、A₃からなる登録情報ＡをアドレスＪに
登録する登録動作について説明する。登録動作の
場合、連想記憶装置にカウンタクリア信号５３１
と登録動作を示す“１”の登録／削除信号１５２
とアドレスＪの書込みアドレス１５１をまず供給
する。これにより、カウンタ５３０の内容はクリ
アされ、第１の記憶手段１１０の第０ブロツクを
指定する。

次に登録情報Ａの一部であるデータA₀を入力
データ１０１として供給すると共に、負パルス信
号の探索クロツク信号１２１及び書込みパルス信
号１５３を供給すると、第１の記憶手段１１０の
Ｊビツト目で第０ブロツクのアドレスA₀に“１”
が格納される。カウンタ５３０の内容は探索クロ
ツク信号１２１の立上り時に増加するので、この
動作が終了した後のカウンタ５３０は第１ブロツ
クを指定する。入力データ１０１としてデータ
A₁、A₂、A₃に変えてこの動作を３回実行する
と、第１の記憶手段のＪビツト目で第０ブロツク
のアドレスA₀、第１ブロツクのアドレスA₁、第
２ブロツクのアドレスA₂、第３ブロツクのアド
レスA₃にのみ“１”が格納される。

以上、計４回の入力データ１０１の登録によ
り、データA₀、A₁、A₂、A₃からなる登録情報Ａ
の登録動作が完了する。

削除動作は“０”の登録／削除信号１５２と書
込みパルス信号１５３をさらに供給することで登
録動作と同様に行なわれる。すなわち、第１の記
憶手段１１０の書込みアドレス１５１で指定され
るビツトの全アドレスの内容は“０”になる。

次に登録情報ＡがアドレスＪに登録されている
状態で同じ探索情報Ａで探索した場合の動作につ
いて説明する。この連想記憶装置は探索情報の一
部をマスキングしての探索動作が可能である。初
めに“０”のマスク信号５３２を供給し、マスク
処理を施さない探索動作について説明する。

探索動作に際してカウンタクリア信号５３１を
供給する。カウンタクリア信号５３１はカウンタ
５３０の内容をクリアすると共に、レジスタ１２
０の全ビツトの内容を“１”にセツトする。次に
探索情報Ａの一部であるデータA₀を入力データ
１０１として供給すると共に負パルス信号の探索
クロツク信号１２１を供給する。カウンタ５３０
は第０ブロツクを指定しているので、第１の記憶
装置１１０の読取り信号１０２は第０ブロツクの
アドレスA₀の内容となる。従つて、Ｊビツト目
の読取り信号１０２は少なくとも“１”である。
レジスタ１２０の全ビツトの内容は“１”にセツ
トされており、しかも“０”のマスク信号５３２
が供給されているので、読取り信号１０２はオア
ゲート５２０とアンドゲート５１０を通過し、探
索クロツク信号１２１の立上り時にレジスタ１２
０に取込まれる。全ビツト“１”にセツトされて
いたレジスタ１２０は、データA₀を登録情報の
一部として第１の記憶手段１１０の第０ブロツク
に格納しているビツトに対応するレジスタ１２０
のビツトのみ“１”が保持され、他のビツトは
“０”に変る。ここでは、少なくともレジスタ１
２０のＪビツト目の内容は一致を意味する“１”
を示す。また、カウンタ５３０は１だけ増加し、
第１の記憶手段１１０の第１ブロツクを指定す
る。

さらに、探索情報Ａの残りの部分であるデータ
A₁、A₂、A₃を入力データ１０１として探索クロ
ツク信号１２１と共に印加すると、探索情報に整
合しない登録情報を格納している第１の記憶手段
１１０のビツトに対応するレジスタ１２０のビツ
トの内容は“０”にリセツトされる。従つて、
“１”を保持するレジスタ１２０のビツトに対応
する第１の記憶手段１１０のビツトには探索情報
Ａに等しい登録情報Ａが登録されていることにな
る。連想記憶装置に登録情報ＡをアドレスＪに登
録している場合、レジスタ１２０のＪビツト目が
“１”として残る。

エンコーダ１３０は第１図に示した連想記憶装
置と同様にレジスタ１２０の内容を符号化、すな
わち内容“１”を保持するビツト番号を探索アド
レス１３１として出力する。また、同じ探索情報
に整合する複数のデータが登録されている場合に
は、レジスタ１２０の複数ビツトの内容が整合を
示す“１”になる。エンコーダ１３０はその中の
下位のビツト番号を探索アドレス１３１として出
力し、デコーダ１４０は出力した探索アドレス１
３１に対応するレジスタ１２０のビツトを“０”
にリセツトする。これにより、エンコーダ１３０
は“１”にセツトされているレジスタ１２０の下
位からビツト番号を順次に探索アドレス１３１と
して発生する。

このようにしてマスキングを行なわない探索動
作がなされる。探索情報のマスキングは入力デー
タ１０１の単位に行ない、マスクしようとする探
索情報の一部が入力データ１０１として印加する
時期に“１”のマスク信号５３２を印加すること
で容易になされる。“１”のマスク信号５３２が
印加されると、オアゲート５２０の出力は読取り
信号１０２に関係なく“１”になり、その時の入
力データ１０１は無視される。よつて、探索情報
の一部のマスキングがなされる。

以上、説明したように本発明によれば、Ｎワー
ドＭ×Ｋビツトの連想記憶装置を2^M×ＫワードＮ
ビツトの通常の第１の記憶手段１１０を用いて構
成できる。第１図に示した連想記憶装置では第１
の記憶手段１１０として2^M×KワードＮビツトの通
常の記憶素子を必要としたのに比べ、第５図の連
想記憶装置はより小容領の記憶素子で構成でき、
低価格をもたらす。また、探索情報の一部をマス
キングしての探索動作が可能である。

第６図は第３の発明による連想記憶装置の一実
施例の説明図である。この連想記憶装置は第１
図、第４図の連想記憶装置に比べ、よりビツト数
の多い探索情報や登録情報を取扱いや、探索情報
の一部をマスキングしての探索動作ができ、また
第５図の連想記憶装置に比べより高速に探索動作
や登録動作が可能である。このため、第１図の連
想記憶装置にアンドゲート６１０と複数の第１の
記憶手段１１０とが設けられている。

この連想記憶装置の記憶構成をＮワードＭ×Ｋ
ビツトとすると、各第１の記憶手段の記憶構成は
2^MワードＮビツトとなり、また第１の記憶手段１
１０の数はＫ個となる。第５図の連想記憶装置の
ビツト数の拡張が第１の記憶手段１１０のワード
数の拡張によりなされたが、この連想記憶装置で
は第１の記憶手段１１０の個数を増すことで拡張
している。第５図の連想記憶装置における第１の
記憶手段１１０のブロツクは、この連想記憶装置
における各第１の記憶手段１１０に対応する。Ｍ
×Ｋビツトの探索情報や登録情報はＫ個のＭビツ
トの入力データ１０１に分割され、各々Ｋ個の第
１の記憶手段１１０に並列に供給される。Ｋ個の
入力データ１０１で供給される登録情報は、入力
データ１０１毎に各第１の記憶手段１１０の入力
データ１０１で指定されたアドレスのみ“１”と
する形式で格納される。例えば、３つのＭビツト
データA₀、A₁、A₂からなる登録情報Ａは、第０
番目の第１の記憶手段１１０のアドレスA₀と第
１番目の第１の記憶手段１１０のアドレスA₁と
第２番目の第１の記憶手段１１０のアドレスA₂
のみ“１”にセツトすることで格納される。格納
される第１の記憶手段１１０のビツト番号は書込
みアドレス１５１で指定される。この書込みは第
２図、第３図あるいは第４図に示した書込み手段
１５０により制御される。

登録されているデータと同じ探索情報Ａによる
探索動作では、探索情報Ａを構成するデータA₀、
A₁、A₂が各入力データ１０１として各第１の記
憶手段１１０に供給される。各第１の記憶手段１
１０からの読取り信号１０２はビツト毎にまとめ
られてアンドゲート６１０に導かれる。アンドゲ
ート６１０の各出力は、各第１の記憶手段１１０
の各ビツトに格納されている登録情報と与えられ
た探索情報Ａと整合するか否かを“１”、“０”で
示す整合結果となる。探索情報Ａに整合する登録
情報Ａが各第１の記憶手段１１０のＪビツト目に
格納されているとすると、第Ｊ番目のアンドゲー
ト６１０の出力は“１”を示す。アンドゲート６
１０の出力すなわち整合結果は、探索クロツク信
号１２１によりレジスタ１２０に取込まれる。以
後、第１図、第４図、第５図の連想記憶装置と同
様にエンコーダ１３０を介して探索アドレス１３
１が求められる。

Ｋ個のマスク信号５３２は探索情報のＭビツト
単位のマスキングに利用される。マスク信号５３
２が入力されると、その信号につながる第１の記
憶手段１１０の読取信号１０２は強制的に“１”
にされる。従つて、入力されたマスク信号５３２
に対応する探索情報の一部がマスクされ、探索情
報の一部をマスクしての探索動作が可能となる。

以上説明したように、この連想記憶装置はＫ個
の2^MワードＮビツトの第１の記憶手段１１０を用
いてＮワードＭ×Ｋビツトの連想記憶装置を構成
でき、その探索動作や登録動作を１回の第１の記
憶手段１１０のアクセスで行なえ高速動作が可能
である。また、探索情報の一部をマスクしての探
索動作も可能である。

なお、書込みアドレス１５１と探索アドレス１
３１を共通にしたり、あるいは第６図の複数の入
力データ１０１毎にレジスタを設け、それらを共
通の入力線につなぐことで、入出力ピン数を削減
することも可能である。

第７図は第４の発明による連想記憶装置の一実
施例の説明図である。この連想記憶装置は与えら
れた探索情報の１ビツトの誤りを許容する探索も
可能にした柔軟な連想記憶装置であり、第１図、
第４図、第５図あるいは第６図に示した連想記憶
装置に相当する連想記憶部７１０と、外部機器か
ら与えられる一次データ７２１を入力とし、連想
記憶部７１０に入力データ１０１を供給する探索
情報変換手段７２０とから構成される。

外部から与えられた一次データ７２１はセツト
パルス信号７２２により探索情報変換手段７２０
に格納される。格納された一次データ７２１は
“０”の変換信号７２３を与えるとそのまま入力
データ１０１として連想記憶部７１０に与えら
れ、“１”の変換信号７２３が与えられると格納
された一次データ７２１内の１ビツトを変化させ
て入力データ１０１として出力する。変換される
ビツト位置は最下位ビツトから初まり、シフトパ
ルス信号７２４が印加される毎に上位ビツトに移
動する。

登録動作、削除動作及び一次データ７２１をそ
のまま入力データ１０１に与えての探索動作は第
１図、第４図、第５図あるいは第６図の連想記憶
装置の動作と同じである。

一次データ７２１と１ビツト異なる探索情報に
対する探索動作は、“１”の変換信号７２３を供
給し、まず一次データ７２１の最下位ビツトを変
化させたデータを入力データ１０１として連想記
憶部７１０に供給して行なう。これにより、一次
データ７２１の最下位ビツトが異なる探索情報に
対する探索動作が行なわれ、その格納アドレスで
ある探索アドレス１３１が求まる。

次にシフトパルス信号７２４を供給し、一次デ
ータ７２１の変化させるビツト位置を１ビツトず
らせて入力データ１０１を連想記憶部７１０に供
給する。

以上の探索動作を繰返し行なうことにより、一
次データ７２１と１ビツト異なる全ての探索情報
に対する探索動作がなされる。すなわち、一次デ
ータ７２１とハミング距離１だけ離れたデータに
対しての探索動作が可能である。

第８図は第７図に示した探索情報変換手段７２
０の一実施例の説明図である。この探索情報変換
手段は一次データ７２１をセツトパルス信号７２
２により取込むデータレジスタ８１０と、セツト
パルス信号７２２により最下位ビツトのみ“１”
となる内容に初期設定されるシフトレジスタ８２
０と、シフトレジスタ８２０とデータレジスタ８
１０の出力とを入力とし、入力データ１０１を発
生する排他的論理和ゲート８３０とから構成され
る。

シフトレジスタ８２０は“０”の変換信号７２
３を受けるとその全ての出力を“０”にし、“１”
の変換信号７２３を受けたときのみ内容を出力す
る。従つて、“０”の変換信号７２３が供給され
ると、データレジスタ８１０に格納された一次デ
ータ７２１をそのまま入力データ１０１として出
力する。“１”の変換信号７２３が供給されると、
シフトレジスタ８２０の内容が“１”を示すビツ
トに対応するデータレジスタ８１０の出力を反転
させて入力データ１０１として出力する。シフト
レジスタ８２０の内容はシフトパルス信号７２４
により１ビツトずつ上位方向（右側）にシフトす
る。従つて、シフトパルス信号７２４が与えられ
る毎に、反転するビツト位置が上位方向にシフト
した入力データ１０１が出力される。すなわち、
一次データ７２１とハミング距離が１だけ離れた
入力データ１０１を発生できる。

なお、一次データ７２１内の反転させるビツト
を特定のビツトにしぼることにより探索情報のビ
ツト単位のマスク処理が可能となる。

（発明の効果）以上説明したように本発明による連想記憶装置
は所望のデータの格納位置を示すアドレスを供給
することによりアクセスされる安価な通常の記憶
素子を用いて構成できる。ＮワードＭビツトの第
１図あるいは第４図の連想記憶装置は第１の記憶
手段１１０として2^MワードＮビツトの通常の記憶
素子で構成でき、ＮワードＭ×Ｋビツトの第５図
あるいは第６図の連想記憶装置は2^M×ＫワードＮ
ビツトの通常の記憶素子あるいは2^MワードＮビツ
トの通常の記憶素子Ｋ個で構成できる。従つて、
256KビツトRAMの半導体技術を用いれば、一例
として１キロワード８ビツトの第１図に示した連
想記憶装置、あるいは１キロワード24ビツトの第
５図、第６図の連想記憶装置を１チツプで実現で
きる。一般に市販されている半導体連想メモリ、
例えばシグネテイツクス（Signetics）社の連想
メモリIC8220は４ワード２ビツトであるのに比
較し、本発明による連想記憶装置は極めて大容量
であるといえる。

また、この連想記憶装置の探索動作や登録動作
は１回ないし数回の通常の記憶素子のアクセスで
終了でき、従来のワードシリアル・ビツトパラレ
ルあるいはワードパラレル・ビツトシリアルの連
想記憶装置に比べ高速である。

さらに、探索情報の一部をマスクしての探索動
作や、探索情報とハミング距離１以内の探索動作
や、複数の登録情報と整合する場合の多重マツチ
処理が可能である。

このような高速、大容量、低価格の連想記憶装
置が情報処理システムの記憶装置に利用される
と、データベース、パタン認識、人工知能などの
における連想処理を高速に実行する情報処理シス
テムを実現できる。

なお、以上の説明において、論理積手段、マス
ク手段としてアンドゲート５１０、オアゲート５
２０を用いたが、他の論理ゲートに置かえること
も可能であり、本発明の特許請求の範囲を限定す
るものではない。

【図面の簡単な説明】

第１図は第１の発明による連想記憶装置の一実
施例の説明図、第２図は書込み手段の一実施例の
説明図、第３図は書込み手段の他の実施例の説明
図、第４図は第１の発明の他の実施例の説明図、
第５図は第２の発明による連想記憶装置の一実施
例の説明図、第６図は第３の発明による連想記憶
装置の一実施例の説明図、第７図は第４の発明に
よる連想記憶装置の一実施例の説明図、第８図は
第７図の連想記憶装置に用いられた探索情報変換
手段の一実施例の説明図である。１１０……第１の記憶手段、１２０……レジス
タ、１３０……エンコーダ、１４０……デコー
ダ、１５０……書込み手段、２１０……書込みデ
コーダ、３１０，７２０……オアゲート、３２０
……スイツチ、４１０……第２の記憶手段、４２
０……選択回路、５１０，６１０……アンドゲー
ト、５２０……オアゲート、５３０……カウン
タ、７１０……連想記憶部、７２０……探索情報
変換手段、８１０……データレジスタ、８２０…
…シフトレジスタ、８３０……拝他的論理和ゲー
ト。

Claims

【特許請求の範囲】１入力データをアドレス入力とし、入力データ
で指定されワードのみ異なるデータを、書込みア
ドレスで指定されるビツトに記憶する第１の記憶
手段と、書込みアドレスで指定されるワードに登
録時の入力データを記憶する第２の記憶手段と、
入力データと第２の記憶手段の読取り出力とを入
力とし、いずれか一方を選択的に第１の記憶手段
のアドレス入力に供給する選択回路と、第１の記
憶手段の書込みアドレスで指定されるビツトへの
書込みを制御する書込みデコーダと、第１の記憶
手段の読み取り信号を取込む一時記憶手段と、こ
の出力につながるエンコード手段と、この出力を
入力とし、一時記憶手段のリセツトを行なうデコ
ード手段とを備えたことを特徴とする連想記憶装
置。２外部から供給される一次データの一部を変調
して入力データを発生する探索情報変調手段と、
入力データをアドレス入力とし、入力データで指
定されるワードのみ異なるデータを、書込みアド
レスで指定されるビツトに記憶する第１の記憶手
段と、書込みアドレスで指定される第１の記憶手
段のビツト位置に書き込みを行なう書込み手段
と、第１の記憶手段の読み取り信号を取込む一時
記憶手段と、この出力につながるエンコード手段
と、この出力を入力とし、一時記憶手段のリセツ
トを行なうデコード手段とを備えたことを特徴と
する連想記憶装置。