JPH0551999B2

JPH0551999B2 -

Info

Publication number: JPH0551999B2
Application number: JP59266761A
Authority: JP
Inventors: Hachiro Yamada; Tsunesuke Takahashi
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1984-12-18
Filing date: 1984-12-18
Publication date: 1993-08-04
Also published as: JPS61144798A

Description

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

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

また、日経エレクトロニクス（1980.10.27発
行）の102〜136ページには、リスト処理、画像処
理、デンタベースへの応用が記載されている。

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

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

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

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

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

（発明の構成）すなわち、本発明によれば入力データの入力数
を計数する計数手段と、記憶素子が行列状に配置
された記憶手段と、登録動作時に記憶手段の全て
の行選択線を並列に駆動し、探索動作時に入力デ
ータで指定された行選択線を選択的に駆動する行
選択手段と、登録動作時に登録アドレスと計数手
段の内容で指定された記憶手段の列選択線を選択
的に駆動し、探索動作時に計数手段の内容で指定
される複数の列選択線を並列に駆動する列選択手
段と、入力データで指定される行のみ反転する書
込みデータを記憶手段の全ての列の書込みデータ
線に供給する書込みデータ発生手段と、計数手段
の内容で指定された記憶手段の各列の読取り信号
を入力データが与えられる毎に取込み、整合した
か否かを判定する整合処理手段と、この出力につ
ながるエンコード手段とを備えた連想記憶装置が
得られる。

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

第１図は本発明による連想記憶装置の一実施例
の説明図である。この連想記憶装置は入力データ
１０１として探索情報を入力とし、探索情報に一
致する情報が格納されている探索アドレス１６２
を出力するものであり、入力データ１０１に対す
る計数手段となるカウンタ１７０と記憶素子が行
列状に配置された記憶手段１１０と、これと行選
択線１２１でつながり、登録動作時に全ての行選
択線１２１を並列に駆動し、探索動作時に入力デ
ータ１０１で指定された行選択線１２１を駆動す
る行選択手段１２０と、記憶手段１１０と各列選
択線１３１でつながり、登録動作時に登録アドレ
ス１３２とカウンタ１７０の出力１７５とで指定
された列選択線１３１を駆動し、探索動作時にカ
ウンタ１７０の内容で指定される複数の列選択線
１３１を並列に駆動する列選択手段１３０と、記
憶手段１１０の各行の記憶素子への書込みデータ
を供給する書込みデータ線１４１で記憶手段１１
０とつながり、入力データ１０１で指定された書
込みデータ線１４１のみ反転する書込みデータを
書込みデータ線１４１に供給する書込みデータ発
生手段１４０と、記憶手段１００に読取り信号１
５１逐次を入力し、探索情報に整合する情報が登
録されているか否かを判断する整合処理手段１５
０と、この出力を入力とし、その中に“１”が含
まれていれば“１”の整合信号１６１と共に
“１”の位置を示す探索アドレス１６２とを出力
するエンコード手段１６０とを備えている。

記憶手段１１０は所望のデータの格納位置を示
すアドレスを与えることによりアクセスされる通
常の記憶素子で構成される。この連想記憶装置の
記憶構成をＮワードＭ×Ｋビツトとすると、記憶
手段１１０の記憶構成は2^M行Ｎ×Ｋ列すなわち2^M
ワードＮ×Ｋビツトとなる。また、入力データ１
０１のビツト数はＭビツト、登録アドレス１３２
と探索アドレス１６２のビツト数はlog₂ ^Nビツト
となる。またカウンタ１７０のビツト数はlog₂ ^K
ビツトとなる。記憶手段１１０は第１図に示すよ
うに破線で区切られたＫ列をブロツクとするとＮ
個のブロツクで構成される。ブロツクがこの連想
記憶装置のワードに対応する。ブロツクの指定は
登録アドレス１３２で行なわれ、ブロツク内の列
の指定はカウンタ１７０で行なわれる。Ｍ×Ｋビ
ツトの探索情報や登録情報はＭビツトの入力デー
タ１０１毎に分割され、Ｋ回に分けて上位から順
次行選択手段１２０や書込みデータ発生手段１４
０に送られる。Ｋ個の入力データ１０１として送
られる登録情報は、入力データ１０１毎に記憶手
段１１０の登録アドレス１３２で指定されるブロ
ツク内の各列に格納される。

第２図は記憶手段１１０の記憶内容の説明図で
ある。同図は一例として、４個のＭビツトの部分
データ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₀，A₁，A₂，A₃の入力に対する
Ｊブロツクの各列の読取り信号１５１は共に
“１”となる。“１”の読取り信号１５１は探索情
報Ａの部分データに一致する部分データが登録さ
れていることを示す。整合処理手段１５０は探索
情報Ａの各部分データA₀，A₁，A₂，A₃に対する
読取り信号１５１が全て“１”であるか否かによ
り、整合したか否かを判断する。この例では記憶
手段１１０のＪブロツク目の第０、１、２、３列
の読取り信号１５１が共に“１”となるので、Ｊ
ブロツクに探索情報Ａに整合する情報が格納され
ていると判断される。従つて、整合処理手段１５
０の出力である整合結果信号１５２のＪビツト目
は一致を示す“１”となる。

この整合信号１５２はエンコード手段１６０に
供給される。エンコード手段１６０は“１”の整
合結果信号１５２が入力されていることを示す整
合信号１６１と、そのビツト位置を探索アドレス
１６２として出力する。整合信号１６１は連想記
憶装置内に探索情報に一致する情報が登録されて
いることを示し、探索アドレス１６２はその格納
アドレスを示す。この例では記憶手段１１０のＪ
ブロツク目に登録情報Ａが格納されているので、
探索アドレス１６２としてアドレスＪを出力す
る。

なお、探索情報Ａに整合する複数の情報が登録
されている場合の多重整合時には、複数ビツトの
“１”の整合結果信号１５２が発生する。この場
合、探索アドレス１６２を入力とし、それで指定
される整合処理手段１５０にリセツト信号を供給
するデコーダを設けることで、整合した複数の探
索アドレス１６２を求めることができる。

また、マスクしようとする探索情報の部分デー
タが入力される時に、整合処理手段１５０へのク
ロツク信号１１２を禁止することにより、入力デ
ータ１０１毎のマスク処理が可能である。

以上説明したように、この連想記憶装置は2^Mワ
ードNKビツトの通常の記憶素子による記憶手段
１１０を用いて、ＮワードMKビツトの連想記憶
装置を構成でき、その価格低下をもたらす。また
探索動作や登録動作はＫ回のメモリアクセスでな
され、高速動作が可能である。

第３図は第１図の連想記憶装置に用いられた行
選択手段１２０の一実施例の説明図である。この
行選択手段は登録情報や探索情報となる入力デー
タ１０１を入力とするデコーダ３１０と、その各
出力と動作モード信号１０３との論理和を行ない
記憶手段１１０の行選択線１２１を駆動するオア
ゲート３２０とからなる。

登録動作を示す“１”の動作モード信号１０３
が供給されている場合のオアゲート３２０の各出
力は全て“１”になり、全ての行選択線１２１が
並列して駆動される。しかし、探索動作を示す
“０”の動作モード信号１０３が供給された場合
には、探索情報となる入力データ１０１で指定さ
れる行選択線１２１のみ駆動される。これによ
り、登録動作時には記憶手段１１０の全ての行が
並列に駆動され、探索動作時には探索情報で指定
される行のみ選択的に駆動される。

第４図は第１図の連想記憶装置に用いられた列
選択手段１３０の一実施例の説明図である。この
列選択手段は登録アドレス１３２を入力とするブ
ロツクデコーダ４１０と、動作モード信号１０３
を反転させるインバータ４２０と、この出力とブ
ロツクデコーダ４１０の各出力との論理和を行な
うオアゲート４３０と、カウンタ１７０の出力１
７５をデータ入力とし、オアゲート４３０の出力
をイネーブル入力とし、記憶手段１１０の各列選
択線１３１に出力がつながる列デコーダ４４０と
を備えて構成される。

各列デコーダ４４０は記憶手段１１０の各ブロ
ツク内の列を選択し、ブロツクデコーダ４１０は
記憶手段１１０のブロツクを選択する。

登録動作時には“１”の動作モード信号１０３
が供給されるので、ブロツクデコーダ４１０は登
録アドレス１３２で指定される列デコーダ４４０
のイネーブル入力にのみ“１”の信号を供給す
る。その列デコーダ４４０はカウンタ１７０の出
力１７５で指定された列選択線１３１のみ駆動す
る。すなわち、登録アドレス１３２とカウンタ１
７０の出力１７５で指定された列選択線１３１の
み駆動される。

探索動作時には“０”の動作モード信号１０３
が供給されるため、オアゲート４３０により、全
ての列デコーダ４４０のイネーブル入力に“１”
の信号が供給される。これにより、各列デコーダ
４４０はカウンタ１７０の出力１７５で指定され
る列選択線１３１を並列に駆動する。

第５図は第１図の連想記憶装置に用いられる書
込みデータ発生手段１４０の一実施例の説明図で
ある。デコーダ５１０は登録情報の部分データを
入力データ１０１として入力とし、それで指定さ
れる記憶手段１１０の行のみ“１”となる書込み
データを書込みデータ線１４１に供給する。従つ
て、登録情報は第２図に示したように記憶手段１
１０に格納される。

第６図は第１図に示した連想記憶装置に用いた
整合処理手段１５０の一実施例の説明図である。
第１図では連想記憶装置のワード数Ｎに等しい数
の第５図の整合処理手段が用いられている。この
整合処理手段は記憶手段１１０の読取り信号１５
１を入力とするアンドゲート６１０と、その出力
を一時記憶するレジスタ６２０とを備えている。

レジスタ６２０は探索動作開始時に初期設定信
号１１１によりセツトされ、クロツク信号１１２
に同期してアンドゲート６１０の出力を取込む。
探索情報Ａの部分データA₀〜A_K-１に対する読取
り信号１５１を各々E₀〜E_K-1とすると（第１図
ではＫ＝４）、レジスタ６２０には部分データが
入力される毎にそれに対する読取り信号１５１の
論理積が蓄積される。従つて、全ての部分データ
の入力が終了すると、レジスタ６２０にはE₀・
E₁・…・E_K-1の論理演算結果が格納される。す
なわち、レジスタ６２０の出力は、この読取り信
号１５１を出力した記憶手段１１０のブロツクに
格納されている情報が、探索情報Ａに一致するか
否かを示す整合結果信号１５２となる。

（発明の効果）以上説明したように本発明による連想記憶装置
は所望のデータの格納位置を示すアドレスを供給
することによりアクセスされる安価な通常の記憶
素子を用いて構成できる。ＮワードＭ×Ｋビツト
の連想記憶装置は2^MワードＭ×Ｋビツトの通常の
記憶素子で構成できる。

従つて、１メガビツトの半導体技術を用いれ
ば、一例として、ブロツク内の列数を８、入力デ
ータ１０１のビツト数を６ビツトとすると、２キ
ロワード48ビツトの連想記憶装置を１チツプで実
現できる。一般市販されている半導体連想メモ
リ、例えばシグネテイツクス（Signetics）社の
連想メモリIC8220は４ワード２ビツトであるの
に比較し、本発明による連想記憶装置は極めて大
容量であるといえる。

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

さらに、探索情報の一部をマスクしての探索動
作や複数のアドレスで整合した場合の多重整合処
理も可能である。

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

なお、以上の説明において記憶手段１１０の登
録情報で指定される行のみ“１”を格納させてい
たが、“０”を格納させることも可能である。ま
た、記憶手段１１０のブロツク内の列を隣接させ
ていたが、各ブロツクの同一列をまとめて配置す
ることも可能である。この場合、カウンタ１７０
が上行、登録アドレス１３２が下位の行を指定す
ることになる。したがつて、列選択手段１３０、
書込みデータ発生手段１４０、整合処理手段１５
０は種々の変形を適用できる。

また、登録アドレス１３２と探索アドレス１６
２とを共通にし、入力出端子数を削減することも
可能である。

したがつて、以上の説明は本発明の特許請求の
範囲を限定するものではない。

【図面の簡単な説明】

第１図は本発明による連想記憶装置の一実施例
の説明図、第２図は記憶手段１１０の記憶内容の
説明図、第３図は第１図の行選択手段１２０の一
実施例の説明図、第４図は第１図の列選択手段１
３０の一実施例の説明図、第５図は第１図の書込
みデータ発生手段１４０の一実施例の説明図であ
る。第６図は整合処理手段の一実施例を示す図。１１０……記憶手段、１２０……行選択線、１
３０……列選択手段、１４０……書込みデータ発
生手段、１５０……整合処理手段、１６０……エ
ンコード手段、３１０，５１０……デコーダ、３
２０，４３０……オアゲート、４１０……ブロツ
クデコーダ、４４０……列デコーダ、４２０……
インバータ、６１０……アンドゲート、６２０…
…レジスタ。

Claims

【特許請求の範囲】

１入力データの入力数を計数する計数手段と、
記憶素子が行列状に配置された記憶手段と、登録
動作時に記憶手段の全ての行選択線を並列に駆動
し、探索動作時に入力データで指定された行選択
線を選択的に駆動する行選択手段と、登録動作時
に登録アドレスと計数手段の内容で指定された記
憶手段の列選択線を選択的に駆動し、探索動作時
に計数手段の内容で指定される複数の列選択線を
並列に駆動する列選択手段と、入力データで指定
された行のみ反転する書込みデータを記憶手段の
全ての列の書込みデータ線に供給する書込みデー
タ発生手段と、計数手段の内容で指定された記憶
手段の各列の読取り信号を入力データが与えられ
る毎に取込み、整合したか否かを判定する整合処
理手段と、この出力につながるエンコード手段と
を備えたことを特徴とする連想記憶装置。