JPH06101232B2

JPH06101232B2 - 連想記憶装置

Info

Publication number: JPH06101232B2
Application number: JP59223227A
Authority: JP
Inventors: 八郎山田; 恒介高橋
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1984-10-24
Filing date: 1984-10-24
Publication date: 1994-12-12
Anticipated expiration: 2009-12-12
Also published as: JPS61104495A

Description

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

〔従来技術とその問題点〕

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

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

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

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

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

〔発明の目的〕

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

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

さらに、本発明の他の目的は探索条件として一致だけで
なく、大小関係についての探索動作を可能にした連想記
憶装置を提供することにある。

〔発明の構成〕

したがって、本発明によれば以下すなわち、記憶素子が
2^M行2N列（Ｍ、Ｎは正の整数）の行列状に配置された記
憶手段と、入力データを入力とし、出力が記憶手段の各
行選択線につながる行選択手段と、登録アドレスを入力
とし、出力が記憶手段の各列選択線につながり、登録時
に前記登録アドレスで指定される特定の列を選択し、探
索時に全ての列を選択する列選択手段と、入力データを
入力とし、入力データで指定される行のみ値が変化する
第１のデータと入力データで指定された行から値が変化
する第２のデータとを選択的に前記記憶手段の各行への
書込みデータ線に供給する書込みデータ発生手段と、前
記記憶手段の読取り出力が与えられた探索条件に適合す
るか否かを判定する探索条件処理手段と、この出力につ
ながるエンコード手段とを備えた連想記憶装置と、入力
データの入力数を計数する計数手段と、記憶素子が行列
状に配置された記憶手段と、入力データと計数手段の出
力とを入力とし、出力が記憶手段の各行選択線につなが
る行選択手段と、登録アドレスを入力とし、出力が記憶
手段の各列選択線につながり、登録時に前記登録アドレ
スで指定される特定の列を選択し、探索時に全ての列を
選択する列選択手段と、入力データを入力とし、入力デ
ータで指定される行のみ値が変化する第１のデータと入
力データで指定された行から値が変化する第２のデータ
とを選択的に前記記憶手段の各行への書込みデータ線に
供給する書込みデータ発生手段と、前記入力データが与
えられる毎に記憶手段の読取り出力を取込む比較処理手
段と、この出力が与えられた探索条件に適合するか否か
を判定する探索条件処理手段と、その出力につながるエ
ンコード手段とを備えた連想記憶装置である。

〔実施例〕

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

第１図は第１の発明による連想記憶装置の一実施例の説
明図である。この連想記憶装置は入力データ101と探索
条件102とを入力とし、探索条件102を満たすデータが格
納されている探索アドレス162を出力するものであり、
記憶素子が行列状に配置された記憶手段110と、これと
行選択線121でつながり、登録動作時に全ての行選択線1
21を駆動し、探索動作時に入力データ101で指定された
行選択線121を駆動する行選択手段120と、記憶手段110
と各列選択線131でつながり、登録動作時に登録アドレ
ス132と一致列選択信号133とで指定された列選択線131
を駆動し、探索動作時に全ての列選択線131を駆動する
列選択手段130と、記憶手段110の各行の記憶素子への書
込みデータを供給する書込みデータ線141で記憶手段110
とつながり、入力データ101で指定された書込みデータ
線141のみ値が異なるデータと入力データ101で指定され
た書込みデータ線141から値が異なるデータとを一致選
択信号133により選択的に書込みデータとして書込みデ
ータ線141に供給する書込みデータ発生手段140と、記憶
手段110の１行の内容を読取り信号151,151′を入力と
し、それらが探索条件を満たすか否かを出力する探索条
件処理手段150と、この出力を入力とし、その中に“1"
が含まれていれば“1"の整合信号161と共に“1"の位置
を示す探索アドレス162とを出力するエンコード手段160
とを備えている。

記憶手段110は所望のデータの格納位置を示すアドレス
を与えることによりアクセスされる通常の記憶素子で構
成される。この連想記憶装置の記憶構成をＮワードＭビ
ットとすると、記憶手段110の記憶構成は2^M行２・Ｎ列
すなわち、2^Mワード２・Ｎビットとなる。また、入力デ
ータ101のビット数はＭビット、登録アドレス132と探索
アドレス162のビット数はlog₂ ^Nビットとなる。

この連想記憶装置の基本的動作は登録動作と探索動作と
からなる。入力データ101は登録動作時には登録情報、
探索動作時には探索情報として与えられる。また、探索
条件データ102として与えられる探索条件は大、小、一
致及びそれらの任意の組合せを選択できる。以下に登録
動作と探索動作について順次に説明を行なう。

登録動作において、登録動作を示す“1"の動作モード信
号103と登録アドレス132及び入力データ101として登録
情報が与えられる。さらに、“0",“1"の順序で一致選
択信号133が与えられる。“1"の動作モード信号103によ
り、行選択手段120は記憶手段110の全ての行を選択す
る。登録アドレス132は記憶手段110の隣接する２列を指
定し、一致列選択信号133は論理値“0"と“1"により２
列内の１列を指定する。“0"の一致列選択信号133は２
列内の左側の偶数列を選択し、“1"の一致列選択信号13
3は２列内の右側となる奇数列を選択する。一致列選択
信号133は“0",“1"の順序で与えられるので、列選択手
段130は登録アドレス132で指定される記憶手段110の２
列内の偶数列、奇数列の順序で列を選択する。

第２図は記憶手段110の記憶内容の説明図であり、また
書込みデータ発生手段140により発生される書込みデー
タ141の説明図も兼ねている。左側の列が偶数列、右側
の列が奇数列であり、上方に位置する行ほど小さい値の
入力データ101で指定される。なお、第２図に示した書
込みデータの具体的な発生方法については、第６図の書
込みデータ発生手段140の構成図を用いて後に詳細に説
明する。書込みデータ発生手段140は登録情報となる入
力データ101を入力とし、一致列選択信号133で指定され
る書込みデータ線141を発生し、記憶手段110に供給す
る。登録情報をＡとすると、書込みデータ発生手段140
は“0"の一致列選択信号133の入力時に、第２図の左側
の列に対応する書込みデータ141、すなわちＡ行のみ
“1"となる書込みデータ141を発生する。また、“1"の
一致列選択信号133の入力時には、第２図の右側の列に
対応する書込みデータ141、すなわちＡ以上の行が“1"
となる書込みデータ141を発生する。第２図は、記憶手
段の行数が８行であり、登録情報Ａとして２進数の“1
1"が供給されている例である。従って、記憶手段の第１
列に供給する書込みデータ141は“11"の登録情報で指定
される第４行のみ“1"となる。第２列に供給する書込み
データ141は第４行から“1"になる。これらの書込みデ
ータ141は書込みパルス信号104により、第２図に示すよ
うに登録アドレス132で指定される記憶手段110の２列に
順次格納される。すなわち、登録情報は記憶手段110の
隣接する２列に格納される。

以上の動作により登録動作がなされる。探索動作に際し
ては、探索動作を示す“0"の動作モード信号103と共に
入力データ101として探索情報が与えられる。さらに、
探索条件処理手段150に探索条件データ102が供給され
る。“0"の動作モード信号103により、行選択手段120は
探索情報で指定される記憶手段110の１行を選択し、列
選択手段130は記憶手段110の全ての列の選択駆動を行な
う。したがって、記憶手段110からは探索情報で指定さ
れる記憶手段110の１行の内容が偶数列と奇数列の読取
り信号151と151′として出力される。記憶手段110には
第２図に示すように情報が格納されているので、探索情
報に一致する登録情報が格納されている隣接する偶数
列、奇数列の読取り信号151,151′は（1,1）となる。ま
た、探索情報より値が小さいあるいは大きい登録情報が
格納されている２列の読取り信号151,151′の値はそれ
ぞれ（0,0）あるいは（0,1）となる。

記憶手段110の各２列からの各ビットの読取り信号151,1
51′は探索条件処理手段150に供給される。また、各探
索条件処理手段150には大、小、一致の探索条件を示す
３ビットの探索条件データ102が供給されている。各探
索条件処理手段150に入力されている各２ビットの読取
り信号151,151′が探索条件データ102による探索条件を
満たす場合のみ、その探索条件処理手段150は“1"の探
索結果信号152を発生し、エンコード手段160に供給す
る。

第３図は探索条件が満たされたことを意味する“1"の探
索結果信号152を発生する探索条件と２ビットの読取り
信号151,151′との対応を示す。

第３図に示すように、小の探索条件は（0,0）の読取り
信号151,151′の場合に満たされ、小または一致の探索
条件は（0,0）あるいは（1,1）の読取り信号151,151′
の場合に満たされる。

エンコード手段160は探索結果信号152を入力とし、その
中に“1"の探索結果信号152が含まれていれば、整合信
号161と共に“1"の探索結果信号152の位置を示す探索ア
ドレス162を外部機器に出力する。整合信号161は探索情
報と探索条件を満たす情報が記憶手段110に格納されて
いることを示し、そのアドレスすなわち列は探索アドレ
ス162で示される。

以上説明したように、この連想記憶装置は2^Mワード2Nビ
ットの通常の記憶素子による記憶手段110を用いて、Ｎ
ワードＭビットの連想記憶装置を構成でき、その価格低
下をもたらす。また、探索動作や登録動作は１回のメモ
リアクセスでなされ、高速動作が可能である。さらに、
大小関係等を含む種々の探索条件による探索動作が可能
であり、高機能な連想記憶装置を提供する。

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

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

第５図は第１図の連想記憶装置に用いられた列選択手段
130の一実施例の説明図である。この列選択手段は登録
アドレス132と一致列選択信号133とを各々上位と下位の
入力とするデコーダ510と、動作モード信号103を反転さ
せるインバータ520と、インバータ520の出力とデコーダ
510の各出力との論理和を行ない、記憶手段110の列選択
線131を駆動するオアゲート530とからなる。

登録動作時には“1"の動作モード信号103が供給され、
デコーダ510はオアゲート530を介して登録アドレス132
と一致列選択信号133とで指定される記憶手段110の列選
択線131を選択的に駆動する。一致列選択信号133はデコ
ーダ510の下位入力に供給され、記憶手段510の偶数列あ
るいは奇数列のいずれか一方を選択する。従って、記憶
手段110の特定の列への書込みを許す。探索動作時には
“0"の動作モード信号103が供給され、オアゲート530は
デコーダ510の出力に影響されずに全ての列選択線131を
駆動する。従って、記憶手段110の全ての列の並列読取
りを可能にする。

第６図は第１の連想記憶装置に用いられた書込みデータ
発生手段140の一実施例の説明図である。この書込みデ
ータ発生手段は登録情報となる入力データ101を入力と
するデコーダ610と、アンドゲート620と、オアゲート63
0とから構成される。登録情報がＡとすると、書込みデ
ータ線141には第２図に示した記憶手段110の内容に対応
する書込みデータが供給される。“0"あるいは“1"の一
致列選択信号133により、第２図の第１列あるいは第２
列に対応する書込みデータが書込みデータ線141に発生
する。すなわち、“0"の一致列選択信号133の供給時に
は、各アンドゲート620の出力は“0"になり、入力デー
タ101上の登録情報で指定される書込みデータ線141のみ
“1"となる書込みデータが発生する。“1"の一致列選択
信号133の供給時には、デコーダ610の出力はアンドゲー
ト620とオアゲート630を介して下位の書込みデータ線14
1にも供給され、登録情報の値以上で指定される書込み
データ線141に“1"の書込みデータを発生させる。

第７図は第１図に示した連想起憶装置に用いた探索条件
処理手段150の一実施例の説明図である。この探索条件
処理手段は２個のインバータ710,720と、３個のアンド
ゲート730,740,750と、オアゲート760とから構成され、
記憶手段110から隣接する２ビットの読取り信号151,15
1′が供給され、探索条件データ102として小条件信号71
1と一致条件信号712と大条件信号713が供給される。各
アンドゲート730,740,750は各々第３図に示した探索条
件の小、一致、大の条件を処理する。例えば、小条件信
号711の“1"の探索条件が与えられると、（0,0）の読取
り信号151,151′が供給されたときのみ探索条件が満た
されたことを示す“1"の探索結果信号152を発生する。
小条件信号711、一致条件信号712、大条件信号713を組
合せることにより、第３図に示す探索条件を処理するこ
とができる。

なお、以上の説明においてオアゲート420,530,630,760
やアンドゲート620,730,740,750は論理値“0"を真とす
ることにより各々アンドゲートやオアゲート等の他の論
理ゲートに置換えることも可能である。

第８図は第２の発明による連想記憶装置の別の一実施例
の説明図である。この連想記憶装置は第１図に示した連
想記憶装置に比べよりビット数の多い探索情報を取扱う
ことができ、探索情報の一部をマスキングしての探索が
可能である。このため、第１図の連想記憶装置に比較処
理手段810とマスク手段となるオアゲート820と、計数手
段となるカウンタ830とが追加されている。

この連想記憶装置の記憶構成をＮワードＭ×Ｋビットと
すると、記憶手段110は2^M×Ｋ行２×Ｎ列の行列状に配
置された記憶素子で構成される。すなわち、記憶手段11
0の記憶構成は2^M×Ｋワード２×Ｎビットとなる。ま
た、カウンタ830のビット数はlog₂Kビットとなる。従っ
て、第１図における2^M行２×Ｎ列の記憶手段110をブロ
ックとすると、この記憶手段110はＫ個のブロックで構
成されることになり、ブロックの指定はカウンタ830に
より行なわれる。Ｍ×Ｋビットの探索情報や登録情報は
Ｍビットの入力データ101毎に分割し、Ｋ回に分けて上
位から順次に行選択手段120や書込みデータ発生手段140
に送られる。Ｋ個の入力データ101として送られる登録
情報は入力データ101毎に記憶手段110の各ブロックに格
納される。例えば、４個のＭビットデータA₀，A₁，A₂，
A₃からなる登録情報Ａは記憶手段110の第０ブロックに
データA₀，第１ブロックにデータA₁，第２ブロックにデ
ータA₂，第３ブロックにデータA₃が各々第２図に示した
ように格納される。

さらに詳細に登録動作及び探索動作について説明する。
まず、先に示した４個のＭビットデータA₀，A₁，A₂，A₃
からなる登録情報ＡをアドレスＪに登録する登録動作に
ついて説明する。ここで、データA₀が登録情報Ａの上位
部分であり、データA₃が最下位部分であるとし、上位デ
ータA₀から順次に供給する。次に同じ情報による探索動
作について説明する。両動作とも開始時に初期設定信号
811を供給し、比較処理手段810とカウンタ830の初期値
設定をしておく。

登録動作の場合、初期設定信号811を与えると共に登録
動作を示す“1"の動作モード信号103とアドレスＪの登
録アドレス132とをまず供給する。これにより、カウン
タ830の内容はクリアされ、記憶手段110の第０ブロック
を指定する。次に登録情報Ａの上位部分であるデータA₀
を入力データ101として供給すると共に、“0"の一致列
選択信号133と書込みパルス信号104を供給すると、記憶
手段110の2J列目の第０ブロックにデータA₀のデコード
結果が格納される。さらに、“1"の一致列選択信号133
と共に負パルス信号のクロック信号812と書込みパルス
信号104を供給することにより、記憶手段110の（2J＋
１）列目の第０ブロックにデータA₀の値以上で指定され
る行が“1"となる書込みデータが格納される。カウンタ
830はクロック信号812の立上り時に増加するため、この
書込み終了時にカウンタ830の内容は増加し、記憶手段1
10の第１ブロックを指定する。

以上の動作により、登録情報Ａの部分データA₀の書込み
がなされる。このように部分データの書込み動作は入力
データ101、書込みパルス信号104、“0"の一致列選択信
号133とを供給する前半の動作と、入力データ101、書込
みパルス信号104、“1"の一致列選択信号133、クロック
信号812とを供給する後半の動作とによりなされる。登
録情報Ａの登録は、データA₀，A₁，A₂，A₃を入力データ
101として４回の上記部分データの書込み動作を行なう
ことによりなされる。

第９図は記憶手段110の記憶内容の説明図である。以上
説明したように、４個の部分データA₀，A₁，A₂，A₃から
なる登録情報Ａを登録アドレスＪに登録する動作を行な
うと、記憶手段110の2J列及び（2J＋１）列には同図に
示すようなデータが格納される。すなわち、偶数列とな
る2J列には第０ブロックのA₀で指定される行、第１ブロ
ックのA₁で指定される行、第２ブロックのA₂で指定され
る行、第３ブロックのA₃で指定される行のみ“1"が格納
される。奇数列となる（2J＋１）列の各ブロックには各
々A₀，A₁，A₂，A₃の値以上て指定される行に“1"が格納
される。

このように、この連想記憶装置の登録動作における部分
データの書込み動作は第１図に示した連想記憶装置の登
録動作と同様に行なわれる。

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

探索動作では“0"の動作モード信号103を供給する。ま
た、初期設定信号811を与え、カウンタ830と比較処理手
段810の内容を初期値設定しておく。次に探索情報Ａの
部分データA₀，A₁，A₂，A₃を入力データ101として順次
に負パルス信号のクロック信号812と共に入力する。こ
れにより、カウンタ830の内容はクロック信号812が入力
される毎に増加し、行選択手段120は順次に記憶手段110
の第０ブロックのデータA₀、第１ブロックのデータA₁、
第２ブロックのデータA₂、第３ブロックのデータA₃で指
定される行選択線121を駆動する。この行選択線121につ
ながる記憶手段110の内容はブロック毎にクロック信号8
12に同期して偶数列、奇数列の読取り信号151,151′と
して出力され、比較処理手段810に供給される。記憶手
段110には第９図に示した内容が格納されているので、
データA₀，A₁，A₂，A₃の入力に対する2J列と（2J＋１）
列の読取り信号151,151′は共に（1,1）となる。

次に、探索情報ＡがＫ個のＭビットの部分データA₀，
A₁，……,Ai,……，Ak-₁（A₀が上位）に分割されて入力
データ101として供給されるとする。各部分データAiに
対する記憶手段110読取り信号151,151′は、記憶手段11
0の隣接する２列に書込みデータ発生手段140によりコー
ド化されて格納された登録情報の部分データと探索情報
Ａの部分データAiとの比較結果を示す。偶数列の各読取
り信号151は＝（一致）結果、奇数列の読取り信号151′
は（大または一致）結果を示す。各部分データAiに対
する偶数列と奇数列の読取り信号151,151′を各々Ei,Li
（ｉ＝０〜Ｋ−１）とすると、探索情報Ａと記憶手段11
0の各２列に格納された登録情報との比較結果である＝
結果Ｅと結果Ｌは各々（１），（２）式で表現でき
る。

Ｅ＝E₀・E₁・…・Ei・…・E_k-1 ……（１）比較処理手段810は各部分データに対する読取り信号15
1,151′をクロック信号812に同期して取込み、（１），
（２）式の論理演算を行なって、＝結果Ｅと結果Ｌを
各々Ｅ信号814、Ｌ信号815として探索条件処理手段150
に供給する。

これらのＥ信号814とＬ信号815及び探索条件データ102
とを入力とし、探索条件処理手段150とそれにつながる
エンコード手段160は、第１図の連想記憶装置と同様に
動作し、探索情報と探索条件を満たす登録情報が格納さ
れているか否かを示す整合信号161と格納位置を示す探
索アドレス162とを発生する。

以上の探索動作の説明は探索情報にマスキングを施さな
い動作について説明した。この連想記憶装置は探索情報
を部分データ毎にマスキングしての探索が可能である。
これはマスクする部分データを入力する時期に“1"のマ
スク信号813をオアゲート820に与え、比較処理手段810
に同時期に与えられたクロック信号812の印加を禁止す
ることで行なわれる。部分データAiの入力時に比較処理
手段810へのクロック信号がマスクングされると、前記
（１），（２）式においてEi,Liが取除かれ、部分デー
タAiをマスキングしての比較結果が求まる。

以上説明したように、本発明によればＮワードＭ×Ｋビ
ットの連想記憶装置を2^M×Ｋワード2Nビットの通常の記
憶手段110を用いて構成できる。第１図に示した連想記
憶装置では記憶手段110として２^Ｍ×Ｋワード2Nビット
の通常の記憶素子を必要としたのに比べ、この連想記憶
装置はより小容量の記憶素子で構成でき、低価格化をも
たらす。また、探索条件として一致関係だけではなく大
小関係についての探索や、探索情報の一部をマスキング
しての探索も可能である。

第10図は第８図に示した連想記憶装置に用いられる比較
処理手段810の一実施例の説明図である。この比較処理
手段は、第1,第２のレジスタ1010,1020と、２個のオア
ゲート1030,1040と、２個のアンドゲート1050,1060と、
インバータ1070とで構成される。

この比較処理手段は前記（１），（２）式に比較処理の
中間結果Ｅ′ｉ＝E₀・E₁・…・Ei（ｉ＝０〜Ｋ−１）……（３）Ｌ′ｉ＝Li・Ei・Ｅ′_i-1（ｉ＝０〜Ｋ−1,E_-1＝１）…
…（４）を導入し、（１），（２）式を各々以下の（５），
（６）式で求めている。

Ｅ＝Ｅ′_k-1 ……（５）第１のレジスタ1010とアンドゲート1050は（３）式及び
（５）式の論理演算を行ない、記憶手段110の偶数列の
読取り信号151を反転させるインバータ1070の出力と奇
数列の読取り信号151′と第１のレジスタ1010の内容と
を入力とするアンドゲート1060は（４）式の論理演算を
行なう。また、第２のレジスタ1020とオアゲート1030は
（６）式の第１項の論理演算を行ない、さらにオアゲー
ト1040を含めて（６）式の論理演算を行なう。このよう
な論理演算を行なう前に初期設定信号811により、第１
のレジスタ1010をセットし、第２のレジスタ1020をリセ
ットしておく必要がある。また、探索情報の部分データ
の入力毎に記憶手段110から出力される読取り信号151,1
51′を入力とし、第８図のオアゲート820を介して入力
されるクロック信号816に同期して、上記論理演算を行
なう。全ての部分データに対する読取り信号151,151′
が入力されると、第１のレジスタ1010には（５）式の＝
結果Ｅが格納され、第２のレジスタ1020には（６）式の
第１項の演算結果が格納される。従って、この比較処理
手段からＥ信号814とＬ信号815とが出力され、これらの
信号は第８図の探索条件処理手段150に供給される。

第11図は第２の発明による連想記憶装置の一実施例の説
明図である。この連想記憶装置は第８図に示した連想記
憶装置に、多重整合処理機能を実現するためのデコード
手段1110が付加され、第８図の連想記憶装置における比
較処理手段810と探索条件処理手段150の代りにそれらを
包含し、内部リセット機能を含む探索処理手段1120が導
入されている。

この連想記憶装置の基本的な動作、特に登録動作は第８
図に示した連想記憶装置と同じである。探索動作におい
ても探索情報の入力及びそれに対する読取り信号151,15
1′の発生も第８図の連想記憶装置と同様に行なわれ
る。

第８図と同様にＫ個の部分データA₀，A₁，…，A_k-1から
なる探索情報Ａによる探索動作においても、入力データ
101として供給される各部分データA₀〜A_k-1に対する読
取り信号151,151′は探索処理手段1120に供給される。
探索処理手段1120は前記（３）〜（６）式に基づいた論
理演算を行なうと共に、その論理演算結果が探索条件デ
ータ102として与えられる探索条件を満たすか否かを探
索結果信号152としてエンコード手段160に供給する。エ
ンコード手段160は第８図と同様に整合信号161を探索ア
ドレス162とを発生する。

多重整合、すなわち探索条件が満たされたことを示す
“1"の探索結果信号152が複数の探索処理手段1120から
発生した場合、エンコード手段160は探索結果信号152に
優先順位をつけて探索アドレス162を出力する。この探
索アドレス162はデコード手段1110にも供給される。外
部機器はこの探索アドレス162を読取った後、リセット
信号1111をデコード手段1110に印加する。デコード手段
1110の各出力1112は各探索処理手段1120の内部リセット
入力につながる。したがって、デコード手段1110はリセ
ット信号を探索アドレス162で指定される探索処理手段1
120の内部リセット入力に供給する。リセット信号1111
が供給された探索処理手段1120の出力、すなわち探索結
果信号152の値は“1"から“0"にかわる。従って、エン
コード手段160は次に優先順位の高い“1"の探索結果信
号152の位置を次の探索アドレス162として外部に出力す
る。このように、探索条件を満たす複数の探索アドレス
を次々と発生でき、多重整合に対する処理が可能とな
る。

第12図は第11図の連想記憶装置に用いられる探索処理手
段1120の一実施例の説明図である。この探索処理手段は
第1,第2,第３のレジスタ1210,1220,1230と、アンドゲー
ト1240,1241,1242,1243,1244,1245と、オアゲート1250,
1251,1252,1253と、インバータ1260,1261とから構成さ
れる。この中の第1,第２のレジスタ1210,1220とアンド
ゲート1240,1241とオアゲート1250とインバータ1260は
第10図の比較処理手段における第1,第２のレジスタ101
0,1020とアンドゲート1050,1060とオアゲート1030とイ
ンバータ1070とに各々対応し、同様な動作を行ない、先
に示した（３）〜（５）式と（６）式の第１項の論理演
算を実行する。

この探索処理手段は記憶手段110の偶数列と奇数列の読
取り信号151,151′を各々Ei,Li（ｉ＝０〜Ｋ−１）と
し、探索情報が記憶手段110の各２列に格納された登録
情報より小さいことを示す＜結果Ｓを以下の（７）式で
求めている。

第３図のレジスタ1230とアンドゲート1242とオアゲート
1251とインバータ1261は上記（７）式の論理演算を実行
し、第３のレジスタ1230に＜結果Ｓが格納される。した
がって、第1,第2,第３のレジスタ1210,1220,1230には、
探索情報と記憶手段110の２列に格納された登録情報と
の比較結果、すなわち両者の一致結果、前者が大きいこ
とを示す結果、後者が小さいことを示す結果が各々格納
される。これらの結果と探索条件データ102として供給
される一致条件信号712,大条件信号713,小条件信号711
とは各々アンドゲート1243,1244,1245で論理積が行なわ
れる。各アンドゲート1243,1244,1245の各出力は一致、
大、小の条件が満たされた場合に“1"となる。オアゲー
ト1253は各アンドゲート1243,1244,1245の各出力の論理
和を行ない、探索条件が満たされたか否かを示す探索結
果信号152を出力する。

初期設定信号811は探索動作開始時に供給され第１のレ
ジスタ1210のセットと第2,第３のレジスタ1220,1230の
リセットを行なう。一方、第11図のデコード手段1110を
介して供給されるリセット信号1112は第1,第2,第３のレ
ジスタ1210,1220,1230のリセットを行なう。この結果、
探索結果信号152は強制的に“0"にクリアされる。従っ
て、探索結果信号152を入力とするエンコード手段は、
次の探索アドレスを発生できる。

第13図は第２の発明による連想記憶装置の一実施例の説
明図である。この連想記憶装置は第１図の連想記憶装置
に比べ、よりビット数の多い探索情報や登録情報を取扱
うことができ、また第８図の連想記憶装置に比べより高
速に探索動作や登録動作が可能である。このために第１
図の連想記憶装置において、ブロック毎に分割された記
憶手段110と、行選択手段120と、書込みデータ発生手段
140と、各記憶手段110の偶数列と奇数列の読取り信号15
1,151′を入力とし、これらが探索条件データ102で求め
られる探索条件を満たすか否かを求める探索条件処理手
段1310と、これから供給される探索結果信号152を一時
記憶するレジスタ1320と、エンコード手段160と、デコ
ード手段1330と、登録アドレス132を入力とし、各記憶
手段110の列選択線131を選択的に駆動する列選択手段13
0とからなる。

この連想記憶装置の記憶構成をＮワードＭ×Ｋビットと
すると、各記憶手段110は2^M行2N列の記憶素子すなわち2
^Mワード2Nビットとなり、その数はＫ個となる。第８
図、第11図の連想記憶装置はビット数の拡張を記憶手段
110のワード数の拡張により行なったが、この連想記憶
装置では記憶手段110の個数を増すことでビット数を拡
張している。従って、第８図、第11図の連想記憶装置に
おける記憶手段110のブロックはこの連想記憶装置にお
ける各記憶手段110に対応する。Ｍ×Ｋビットの探索情
報や登録情報はＫ個のＭビットの入力データ101に分割
され、各々Ｋ個の行選択手段120や書込みデータ発生手
段140に並列に供給される。第13図ではＫ＝３としてい
る。

登録動作に際して３個の入力データ101で供給される登
録情報は入力データ101毎に第２図に示したように各記
憶手段110に格納され登録される。探索動作に際して、
探索情報として供給される各入力データ101で指定され
る各記憶手段110の内容は偶数列と奇数列の読取り信号1
51,151′として探索条件処理手段1310に供給される。探
索条件処理手段1310は読取り信号151,151′が探索条件
データ102で求められた探索条件を満たすか否かを調
べ、結果を探索結果信号152としてＮビットのレジスタ1
320に供給する。レジスタ1320はこの探索結果信号152を
クロック信号812に同期して取込む。レジスタ1320の内
容は記憶手段110の各２列に格納されている登録情報が
入力データ101として与えられる探索情報と探索条件デ
ータ102として与えられる探索条件に整合したか否かを
“1",“0"で示す。整合したことを示す“1"の内容をレ
ジスタ1320が保持していることと、そのビット位置はエ
ンコード手段160により整合信号161と探索アドレス162
として出力される。この探索アドレス162が探索条件を
満たす登録情報が格納されているアドレスを示す。

複数のアドレスで整合する場合の多重整合時には、レジ
スタ1320内の複数のビットが“1"を保持する。この場
合、リセット信号1111を印加する。デコード手段1330は
リセット信号1111を探索アドレス162で指定されるレジ
スタ1320のビットのリセット入力に供給する。これによ
り、先に出力した探索アドレス162に対応するレジスタ1
320のビットはリセットされる。従って、エンコード手
段160は次の探索アドレス162を出力する。外部機器は整
合信号161を監視し、それが“0"になるまでリセット信
号1111を与えることで、多重整合時の全ての探索アドレ
ス162を求めることができる。

このように、この連想記憶装置は探索情報や登録情報の
ビット数を記憶手段110の記憶容量を余り増加させずに
拡張できる。また、一致条件だけでなく大小関係を含む
探索条件による探索動作や多重整合処理も可能である。
さらに、第８図や第11図の連想記憶装置では登録情報や
探索動作を複数回に分けて入力していたが、この連想記
憶装置では並列に入力できる。したがって、１回の記憶
手段110のアクセスで探索動作を行なえ、高速化されて
いる。

第14図は第13図の連想記憶装置に用いられた探索条件処
理手段1310の一実施例の説明図である。この探索条件処
理手段は９個のアンドゲート1410〜1418と、２個のオア
ゲート1420,1421と、５個のインバータ1430〜1434とを
備えている。この探索条件処理手段は各記憶手段の偶数
の同一列の読取り信号151と奇数列の同一列の読取り信
号151′と、外部から探索条件データ102として一致条件
信号712,大条件信号713,小条件信号711が入力される。
第13図の連想記憶装置では記憶手段110の２列毎にこの
探索条件処理手段が設けられている。

Ｋ個の記憶手段110の特定の偶数列の読取り信号151をE₀
〜Ei〜E_k-1とし、それに隣接する奇数列のＫ個の読取り
信号151′をL₀〜Li〜L_k-1とすると、＝結果E,＞結果L,
＜結果Ｓはそれぞれ（８），（９），（10）式で表わさ
れる。但し、E₀，L₀が上位の比較結果とす。

Ｅ＝E₀・E₁・…・Ei・…・E_k-1 ……（８）Ｓ＝L₀＋L₁・E₀＋…＋Li・E₀・E₁・…・E_i-1＋…＋L_k-1
・E₀・E₁・…・E_k-2 ……（10）なお、＜結果Ｓは、＞結果L,＝結果Ｅとから（11）式で
も求まる。

Ｓ＝・ ……（11）この探索条件処理手段はＫ＝３の例をとり、（８），
（９），（11）式により、＝結果E,＞結果L,＜結果Ｓを
求めている。さらに、探索条件となる一致条件信号712,
大条件信号713,小条件信号711との論理演算により、探
索条件が満たされたか否かを判断し、それを探索結果信
号152として発生している。この論理演算の論理式を（1
2）式に示す。

探索結果信号＝Ｅ・一致条件信号＋Ｌ・大条件信号＋Ｓ
・小条件信号 ……（12）＝結果Ｅはアンドゲート1410,1411で求まり，＞結果Ｌ
はアンドゲート1412,1413,1414とインバータ1430,1431,
1432とオアゲート1420で求まり、さらに＜結果Ｓはイン
バータ1433,1434とアンドゲート1415で求まる。探索結
果信号152は（12）式に示したように、アンドゲート141
6,1417,1418とオアゲート1421で求まる。

このようにして求みられた探索結果信号152は第13図に
おけるレジスタ1320に供給される。

第15図はさらに他の発明による連想記憶装置の一実施例
の説明図である。この連想記憶装置はより大容量化を目
指し、第１図、第８図、第11図、第13図に示した連想記
憶装置に対応する連想記憶ユニット1510を複数個利用
し、それにつながる複数の出力手段1520と、各出力手段
1520につながるエンコード手段1530と、各連想記憶ユニ
ット1510に書込みパルス信号104を印加するデコード手
段1540とから構成される。各連想記憶ユニット1510には
並列にマスク信号813,クロック信号812,探索条件データ
102,初期設定信号811,入力データ101、動作モード信号1
03、登録アドレス132、一致列選択信号133が供給され
る。

登録時には各連想記憶ユニット1510に登録動作を示す
“1"の動作モード信号103,初期設定信号811,一致列選択
信号133,クロック信号812,入力データ101,登録アドレス
132とを第１図、第８図、第11図、第13図の連想記憶装
置と同様に供給される。登録アドレス132はこの連想記
憶装置の下位アドレスとなり、上位アドレスは上位登録
アドレス1541としてデコード手段1540に供給される。上
位登録アドレス1541は連想記憶ユニット1510を指定し、
登録アドレスは連想記憶ユニット1510内の記憶手段110
の列を指定する。連想記憶装置への書込みを指示する書
込み信号1542はデコード手段1540に供給される。デコー
ド手段1540は書込み信号1542を上位登録アドレス1541で
指定される連想記憶ユニット1510に書込みパルス信号10
4として選択的に供給する。このデコード手段1540によ
り、登録情報は上位登録アドレス1541で選択された連想
記憶ユニット1510に登録される。

探索時にはマスク信号813,クロック信号812,探索条件デ
ータ102,初期設定信号811,入力データ101,動作モード信
号103を各連想記憶ユニット1510に並列に供給する。入
力データ101として与えられた探索情報と探索条件デー
タ102として与えられた探索条件に適合した情報が登録
されている連想記憶ユニット1510からは“1"の整合信号
161と共に探索アドレス162とが出力される。出力手段15
20は複数の連想記憶ユニット1510から“1"の整合信号16
1が発生した場合に左側に位置する連想記憶ユニット151
0の優先順位を高くし、優先順位の高い連想記憶ユニッ
ト1510からの探索アドレス162を下位探索アドレス1521
として出力させる。連想記憶ユニット1510に優先順位を
つけるために、左側から右側の出力手段1520にイネーブ
ル信号1522を供給する。“0"のイネーブル信号1522を供
給された出力手段1520は内部の探索アドレス162の出力
バッファをハイインピーダンス状態にすると共に“0"の
イネーブル信号1522を発生する。“1"のイネーブル信号
と“1"の整合信号161とが供給された出力手段1520は、
探索アドレス162を出力すると共に、“0"のイネーブル
信号1522を発生する。従って、その出力手段1520より右
側に位置する出力手段1520内の出力バッファはハイイン
ピーダンス状態にされる。探索アドレス162を出力した
出力手段1520からは整合信号161を第１の整合信号1523
として出力し、それより右側に位置する出力手段1520は
“0"の第１の整合信号1523を発生する。エンコード手段
1530は第１の整合信号1523を入力とし、“1"の第１の整
合信号1523が入力されたか否かを示す第２の整合信号15
31と“1"の第１の整合信号1523の位置を示す上位探索ア
ドレス1532とを外部機器に出力する。第２の整合信号15
31はこの連想記憶装置内に探索情報と探索条件を満たす
情報が登録されていることを示し、上位探索アドレス15
32は登録されている連想記憶ユニット1510の位置を示
す。また、下位探索アドレス1521はその連想記憶ユニッ
ト1510の探索アドレス162、すなわち、記憶手段110の列
を示す。

外部機器は第２の整合信号1531を監視し、上位探索アド
レス1532と下位探索アドレス1521とを読取り、さらに第
１のリセット信号1524を各出力手段1520に印加する。第
１のリセット信号1524は連想記憶装置内に整合する複数
の情報が登録されている場合に、次に優先順位の高い情
報に対する探索アドレスを求めるために利用される。探
索アドレス162を出力した出力手段1520は第１のリセッ
ト信号1524をリセット信号1111として連想記憶ユニット
1510に供給し、それに次の探索アドレス162を出力させ
る。

このように、この連想記憶装置は第１図、第８図、第11
図、第13図に示した連想記憶装置を用いて構成され、ワ
ード数の拡張が容易に行なえ、大容量の連想記憶装置と
なる。

第16図は第15図の連想記憶装置に用いられた出力手段15
20の一実施例の説明図である。この出力手段は出力バッ
ファ1610と、３個のアンドゲート1620,1630,1640と、イ
ンバータ1650とで構成される。

探索アドレス162は左側の出力手段1520からイネーブル
入力端子1660に入力されたイネーブル信号1522と整合信
号161とが共に“1"の場合に出力バッファ1610を介し
て、下位探索アドレス1521として出力される。この場
合、整合信号161はアンドゲート1630を介して第１の整
合信号1523として出力される。また、イネーブル出力端
子1670からは“0"のイネーブル信号1522が出力される。
従って、このイネーブル出力端子1670につながる右側の
出力手段1520の出力バッファ1610はハイインピーダンス
状態になる。また、第１のリセット信号1524はアンドゲ
ート1620を介してリセット信号1111として連想記憶ユニ
ット1510に供給される。“1"の第１の整合信号1523を発
生する出力手段1520の両側に位置する出力手段1520に与
えられた第１のリセット信号1524はアンドゲート1620を
通過せず、リセット信号1111を出力しない。

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

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

さらに、探索情報の一部をマスクしての探索動作や多重
整合処理も可能である。また、探索条件として一致条件
だけでなく大小関係についての探索も可能である。ま
た、容易にワード数の拡張ができ、より大容量の連想記
憶装置を実現できる。

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

なお、以上の説明において、記憶手段110の偶数列に登
録情報で指定される行のみ“1"を格納させ、奇数列に登
録情報の値以上で指定される行に“1"を格納させてい
た。これは格納方法の一例であり、奇数列に登録情報の
値以下や未満で指定される行に“1"や“0"を格納させる
ことも可能であり、記憶手段110への書込みデータの格
納方法はそれらを組合せた種々の方法を選択できる。し
たがって、書込みデータ発生手段140と探索条件処理手
段150,1310と比較処理手段810と探索処理手段1120は、
記憶手段110への書込みデータの格納方法に伴い容易に
変形できる。

すなわち、以上の説明は本発明の特許請求の範囲を限定
できるものではない。

【図面の簡単な説明】

第１図は第１の発明による連想記憶装置の一実施例の説
明図、第２図は記憶手段110の記憶内容の説明図、第３
図は探索条件と読取り信号との関係を示す説明図、第４
図は行選択手段120の一実施例の説明図、第５図は第１
図の列選択手段130の一実施例の説明図、第６図は第１
図の書込みデータ発生手段140の一実施例の説明図、第
７図は第１図の探索条件処理手段150の一実施例の説明
図、第８図は第２の発明による連想記憶装置の一実施例
の説明図、第９図は第８図の記憶手段110の記憶内容の
説明図、第10図は第８図の比較処理手段810の一実施例
の説明図、第11図は第２の発明による連想記憶装置の一
実施例の説明図、第12図は第11図の探索処理手段1120の
一実施例の説明図、第13図は第２の発明による連想記憶
装置の一実施例の説明図、第14図は第13図の探索条件処
理手段1310の一実施例の説明図、第15図は本発明による
連想記憶装置の一実施例の説明図、第16図は第15図の連
想記憶装置に用いられた出力手段1520の一実施例の説明
図である。110…記憶手段、120…行選択手段、130…列
選択手段、140…書込みデータ発生手段、150,1310…探
索条件処理手段、160,1530…エンコード手段、410,510,
610…デコーダ、810…比較処理手段、1110,1330,1540…
デコード手段、1120…探索処理手段

Claims

【特許請求の範囲】

【請求項１】記憶素子が2^M行2N列（Ｍ、Ｎは正の整数）
の行列状に配置された記憶手段と、入力データを入力と
し、出力が記憶手段の各行選択線につながる行選択手段
と、登録アドレスを入力とし、出力が記憶手段の各列選
択線につながり、登録時に前記登録アドレスで指定され
る特定の列を選択し、探索時に全ての列を選択する列選
択手段と、入力データを入力とし、入力データで指定さ
れる行のみ値が変化する第１のデータと入力データで指
定された行から値が変化する第２のデータとを選択的に
前記記憶手段の各行への書込みデータ線に供給する書込
みデータ発生手段と、前記記憶手段の読取り出力が与え
られた探索条件に適合するか否かを判定する探索条件処
理手段と、該手段の出力につながるエンコード手段とを
備えたことを特徴とする連想記憶装置。
【請求項２】前記行選択手段が登録時に記憶手段の全て
の行選択線を駆動し、探索時に入力データで指定された
行選択線を駆動することを特徴とする特許請求の範囲第
１項に記載の連想記憶装置。
【請求項３】前記列選択手段が登録時に登録アドレスで
指定された記憶手段の２列を１列毎に順次選択し、探索
時に記憶手段の全ての列を選択することを特徴とする特
許請求の範囲第１項に記載の連想記憶装置。
【請求項４】前記書込みデータ発生手段が入力データの
デコード結果と入力データで指定された行位置から値が
変化したデータとを順次に記憶手段の異なる列に供給す
ることを特徴とする特許請求の範囲第１項に記載の連想
記憶装置。
【請求項５】入力データの入力数を計数する計数手段
と、記憶素子が2^M×Ｋ行2N列（Ｍ、Ｎ、Ｋは正の整数）
の行列状に配置された記憶手段と、入力データと計数手
段の出力とを入力とし、出力が記憶手段の各行選択線に
つながる行選択手段と、登録アドレスを入力とし、出力
が記憶手段の各列選択線につながり、登録時に前記登録
アドレスで指定される特定の列を選択し、探索時に全て
の列を選択する列選択手段と、入力データを入力とし、
入力データで指定される行のみ値が変化する第１のデー
タと入力データで指定された行から値が変化する第２の
データとを選択的に前記記憶手段の各行への書込みデー
タ線に供給する書込みデータ発生手段と、前記入力デー
タが与えられる毎に記憶手段の読取り出力を取込む比較
処理手段と、この出力が与えられた探索条件に適合する
か否かを判定する探索条件処理手段と、その出力につな
がるエンコード手段とを備えたことを特徴とする連想記
憶装置。
【請求項６】前記行選択手段が登録時に記憶手段の全て
の行選択線を駆動し、探索時に入力データで指定された
行選択線を駆動することを特徴とする特許請求の範囲第
５項に記載の連想記憶装置。
【請求項７】前記列選択手段が登録時に登録アドレスで
指定された記憶手段の２列を１列毎に順次選択し、探索
時に記憶手段の全ての列を選択することを特徴とする特
許請求の範囲第５項に記載の連想記憶装置。
【請求項８】前記書込みデータ発生手段が入力データの
デコード結果と入力データで指定された行位置から値が
変化したデータとを順次に記憶手段の異なる列に供給す
ることを特徴とする特許請求の範囲第５項に記載の連想
記憶装置。