JPS6045501B2 - 連想メモリ装置 - Google Patents
連想メモリ装置Info
- Publication number
- JPS6045501B2 JPS6045501B2 JP54095298A JP9529879A JPS6045501B2 JP S6045501 B2 JPS6045501 B2 JP S6045501B2 JP 54095298 A JP54095298 A JP 54095298A JP 9529879 A JP9529879 A JP 9529879A JP S6045501 B2 JPS6045501 B2 JP S6045501B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- hamming distance
- memory device
- associative memory
- unit cell
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Landscapes
- Image Analysis (AREA)
Description
【発明の詳細な説明】
本発明は連想メモリ装置、詳しくは、パターン酬−Ｌ
ｐｌＴＥＬ１−セをＬｎ威ｎ↓↓゛拙一唸佃桧“七ナ４
゛本フ メモリ装置に関するものである。
ｐｌＴＥＬ１−セをＬｎ威ｎ↓↓゛拙一唸佃桧“七ナ４
゛本フ メモリ装置に関するものである。
従来の連想メモリ装置は、外部から入力した検索デー
タと完全に一致している記憶データのみを選択して出力
するというもので、曖昧さを持つて記憶データを選択す
るということは考慮されていない。
タと完全に一致している記憶データのみを選択して出力
するというもので、曖昧さを持つて記憶データを選択す
るということは考慮されていない。
従つて、このような曖昧さを持たない連想メモリをパタ
ーン認識処理へ応用しようとする場合、認識しようとす
るパターンと連想メモリ中に記憶されている標準パター
ンとは完全に一致していなければならないという制約が
ある。しかし、一般に認識しようとするパターンと標準
パターンとは雑音、位置ずれ等のため、完全に一致して
いることは少なく、従来の曖昧さを持たない連想メモリ
を用いてパターン認識処理を行うには、特殊な誤りを訂
正符号とその復号化過程を用いて、連想動作に曖昧さを
導入しなければならない。すなわち、誤りを訂正完全符
号となるように符号化した原理パタン・データに誤り訂
正の復号化操作を行い、該原データに対して曖昧さをも
つ縮退デー・夕をつくり、該縮退データ空間で従来の曖
昧さをもたない連想動作を行いという構成をとらなけれ
ばならない。この従来の連想メモリを用いた構成では、
曖昧さを導入する復号化のための動作時間、金物量が増
大するとう欠点がある。 本発明の叙上の事情に鑑みな
されたもので連想メモリにハミング距離を利用した曖昧
さをもつ連想機能を付与して、検索データと完全に一致
している記憶データ以外の、検索データとハミング距離
によつて関係づけられた記憶データをも選択できるよう
にした連想メモリ装置を提供することにある。
ーン認識処理へ応用しようとする場合、認識しようとす
るパターンと連想メモリ中に記憶されている標準パター
ンとは完全に一致していなければならないという制約が
ある。しかし、一般に認識しようとするパターンと標準
パターンとは雑音、位置ずれ等のため、完全に一致して
いることは少なく、従来の曖昧さを持たない連想メモリ
を用いてパターン認識処理を行うには、特殊な誤りを訂
正符号とその復号化過程を用いて、連想動作に曖昧さを
導入しなければならない。すなわち、誤りを訂正完全符
号となるように符号化した原理パタン・データに誤り訂
正の復号化操作を行い、該原データに対して曖昧さをも
つ縮退デー・夕をつくり、該縮退データ空間で従来の曖
昧さをもたない連想動作を行いという構成をとらなけれ
ばならない。この従来の連想メモリを用いた構成では、
曖昧さを導入する復号化のための動作時間、金物量が増
大するとう欠点がある。 本発明の叙上の事情に鑑みな
されたもので連想メモリにハミング距離を利用した曖昧
さをもつ連想機能を付与して、検索データと完全に一致
している記憶データ以外の、検索データとハミング距離
によつて関係づけられた記憶データをも選択できるよう
にした連想メモリ装置を提供することにある。
今、２つのデータＡ＝〔Ａｌａ２ａ３ａ４〕、Ｂ＝〔ｂ
１■Ｂ３ｂ４〕をモデユロ２で加算して、を得たとする
。
１■Ｂ３ｂ４〕をモデユロ２で加算して、を得たとする
。
こ）で、ｄｌ＝Ａ，＋Ｂｉ（１＝１、２、３、４）であ
る。この時、Ｄｉぱ゜０゛か“゜１゛かのいずれかであ
り、その１の総和をハミング距離という。すなわち、ハ
ミング距離ｄは、で表わされる。当然のことながらｄ＝
０の場合、２つのデータＡ．．Ｂは完全に一致しており
、ｄの値が大きくなるに従い類似しなくなる。第１図お
よび第２図は本発明の一実施例であつて、ハミング距離
ｄが０、２未満、２以上という３種類の関係を利用した
最も単純な曖昧さをもつ連想機能を有した連想メモリで
ある。
る。この時、Ｄｉぱ゜０゛か“゜１゛かのいずれかであ
り、その１の総和をハミング距離という。すなわち、ハ
ミング距離ｄは、で表わされる。当然のことながらｄ＝
０の場合、２つのデータＡ．．Ｂは完全に一致しており
、ｄの値が大きくなるに従い類似しなくなる。第１図お
よび第２図は本発明の一実施例であつて、ハミング距離
ｄが０、２未満、２以上という３種類の関係を利用した
最も単純な曖昧さをもつ連想機能を有した連想メモリで
ある。
第１図は必要な論理を分散的にもつた単位セルに示し、
第２図は第１図の単位セルに托個用いた４ワード×４ビ
ット構成のセルアレイを示す。本発明で対象とするメモ
リは半導体メモリであつても、その他のメモリであつて
もよい。第１図において、１は情報Ｍｊを記憶する記憶
素子、２は検索データＳｉの入力端、３は下位の単位セ
ルからの伝搬情報Ｅｉ−１の入力端、４は下位．の単位
セルからの伝搬情報Ｆ，−１の入力端である。
第２図は第１図の単位セルに托個用いた４ワード×４ビ
ット構成のセルアレイを示す。本発明で対象とするメモ
リは半導体メモリであつても、その他のメモリであつて
もよい。第１図において、１は情報Ｍｊを記憶する記憶
素子、２は検索データＳｉの入力端、３は下位の単位セ
ルからの伝搬情報Ｅｉ−１の入力端、４は下位．の単位
セルからの伝搬情報Ｆ，−１の入力端である。
５は排他的論理和ゲート、６，７は入力端子の一部にイ
ンバータを含む論理積ゲート、８は論理和ゲートである
。
ンバータを含む論理積ゲート、８は論理和ゲートである
。
９は上位の単位セルへの伝搬情報Ｅ，の出力端、１０は
上位の単位セルへの伝！搬情報Ｆｉの出力端である。
上位の単位セルへの伝！搬情報Ｆｉの出力端である。
第２図の１１〜２６は第１図に示した単位セルで、例え
ば単位セル１２に注目するに、その端子２，３，４，９
，１０が第１図に同じ記号の所に対応する。他の単位セ
ルについても同様である。２７〜３０は検索デー・夕の
供給源、３１は論理゜゜１゛に相当する電位供給端、３
２は論理“０゛に相当する電位供給端である。
ば単位セル１２に注目するに、その端子２，３，４，９
，１０が第１図に同じ記号の所に対応する。他の単位セ
ルについても同様である。２７〜３０は検索デー・夕の
供給源、３１は論理゜゜１゛に相当する電位供給端、３
２は論理“０゛に相当する電位供給端である。
３３〜４０は連想結果の出力端子で、このうち、３３〜
３６は各ワードの最上位の単位セル１４，１８，２２，
２６からの出力信号Ｅ，であり、３７〜４０は同じく各
ワードの最上位の単位セル１４，１８，２２，２６から
の出力信号Ｆ，である。
３６は各ワードの最上位の単位セル１４，１８，２２，
２６からの出力信号Ｅ，であり、３７〜４０は同じく各
ワードの最上位の単位セル１４，１８，２２，２６から
の出力信号Ｆ，である。
さて、第１図の単位セルは、下位からの伝搬情報Ｅｉ−
１，Ｆ，−１、及び、記憶情報Ｍｉｌ検索データＳｉか
ら、次の論理式ノで表わされる伝搬情報ＥＩ，Ｆｌを出
力する。
１，Ｆ，−１、及び、記憶情報Ｍｉｌ検索データＳｉか
ら、次の論理式ノで表わされる伝搬情報ＥＩ，Ｆｌを出
力する。
たＳ゛し、４はモデユロ２の加算すなわち排他的論理和
を表わす。上記（３）式により、伝搬情報Ｅ，は下位の
すべての単位セルでＭｉ（５Ｓ，とが一致しているとき
論理１をとる。換言すれば、各ワードにおい・て、Ｍｉ
（５Ｓ，とが不一致の単位セルが１つでもあると、最上
位の単位セルの出力Ｅｉは論理“゜０゛となる。一方、
伝搬情報Ｆ，がワードを構成する単位セルのうち、Ｍｉ
とＳ，とが不一致である単位セルの数が１以下のとき理
“０゛をとり、不一致”である単位セルの数が２以上の
とき論理゜゜１゛をとる。すなわち、各ワードの最上位
の単位セルの出力Ｅ１＝Ｅ．．Ｆｉ＝Ｆの組み合せによ
り、３種類の関係が識別できる。つまり、Ｅ＝１、Ｆ＝
０のとき、不一致である単位セルの数は零、すなわち記
憶データと検索データとのハミング距離はＯであり、Ｅ
＝０、Ｆ＝０のとき、不一致である単位セルの数は１、
すなわち記憶データと検索データとのハミング距離は１
であり、Ｅ＝０、Ｆ＝１のとき不一致である単位セルの
数は２以上、すなわち記憶データと検索データとのハミ
ング距離は２以上である。このように、第１図の単位セ
ルにより第２図に示すセルアレイを構成し、供給線２７
〜３０に検索データを入力して連想動作を行つた際、各
ワードの最上位の単位セル１４，１８，２２，２６から
出力される伝搬情報Ｅ，Ｆにもとづき、Ｅ＝１、Ｆ＝０
であるワードの記憶データを選択すると、検索データと
一致した記憶データが出力されることにより、又、Ｅ＝
０、Ｆ＝０であるワードの記憶データを選択すると、検
索データとのハミング距離が１の記憶データが出力され
ることになる。
を表わす。上記（３）式により、伝搬情報Ｅ，は下位の
すべての単位セルでＭｉ（５Ｓ，とが一致しているとき
論理１をとる。換言すれば、各ワードにおい・て、Ｍｉ
（５Ｓ，とが不一致の単位セルが１つでもあると、最上
位の単位セルの出力Ｅｉは論理“゜０゛となる。一方、
伝搬情報Ｆ，がワードを構成する単位セルのうち、Ｍｉ
とＳ，とが不一致である単位セルの数が１以下のとき理
“０゛をとり、不一致”である単位セルの数が２以上の
とき論理゜゜１゛をとる。すなわち、各ワードの最上位
の単位セルの出力Ｅ１＝Ｅ．．Ｆｉ＝Ｆの組み合せによ
り、３種類の関係が識別できる。つまり、Ｅ＝１、Ｆ＝
０のとき、不一致である単位セルの数は零、すなわち記
憶データと検索データとのハミング距離はＯであり、Ｅ
＝０、Ｆ＝０のとき、不一致である単位セルの数は１、
すなわち記憶データと検索データとのハミング距離は１
であり、Ｅ＝０、Ｆ＝１のとき不一致である単位セルの
数は２以上、すなわち記憶データと検索データとのハミ
ング距離は２以上である。このように、第１図の単位セ
ルにより第２図に示すセルアレイを構成し、供給線２７
〜３０に検索データを入力して連想動作を行つた際、各
ワードの最上位の単位セル１４，１８，２２，２６から
出力される伝搬情報Ｅ，Ｆにもとづき、Ｅ＝１、Ｆ＝０
であるワードの記憶データを選択すると、検索データと
一致した記憶データが出力されることにより、又、Ｅ＝
０、Ｆ＝０であるワードの記憶データを選択すると、検
索データとのハミング距離が１の記憶データが出力され
ることになる。
更に、各ワードの最上位の単位セルから出力される伝搬
情報Ｆのみり着目し、Ｆ＝０であるワードの記憶データ
を選択すると、検索データとのハミング距離が２未満の
記憶データが出力れることにより、又、Ｆ＝１であるワ
ードの記憶データを選択すると、検索データとのハミン
グ距離が２以上の記憶データが出力されることになる。
先の論理式（１）で示した論理機能を満たす構成は、第
１図以外にも考えられているが、いずれの場合も、一つ
の単位セルにあたり記憶素子と４ゲート程度の論理ゲー
トを用いて、きわめて簡単にハミング距離を利用した曖
昧さをもつ連想機能を有する連想メモリが構成できるた
め、高速なパターン認識処理の実現が可能になる。なお
、実施例では、ハミング距離が０１２未満、２以上の関
係を用いた曖昧さをもつ連想機能を有する連想メモリの
構成を示したが、さらに論理を付加することによつて、
３以上の任意の自然数をｎとしたとき、ハミング距離が
０．．ｎ未満の任意距離、ｎ未満の任意距離以下、一定
値以上の関係を用いた曖昧さをもつ連想メモリも、同様
な考え方に基づいて構成できる。
情報Ｆのみり着目し、Ｆ＝０であるワードの記憶データ
を選択すると、検索データとのハミング距離が２未満の
記憶データが出力れることにより、又、Ｆ＝１であるワ
ードの記憶データを選択すると、検索データとのハミン
グ距離が２以上の記憶データが出力されることになる。
先の論理式（１）で示した論理機能を満たす構成は、第
１図以外にも考えられているが、いずれの場合も、一つ
の単位セルにあたり記憶素子と４ゲート程度の論理ゲー
トを用いて、きわめて簡単にハミング距離を利用した曖
昧さをもつ連想機能を有する連想メモリが構成できるた
め、高速なパターン認識処理の実現が可能になる。なお
、実施例では、ハミング距離が０１２未満、２以上の関
係を用いた曖昧さをもつ連想機能を有する連想メモリの
構成を示したが、さらに論理を付加することによつて、
３以上の任意の自然数をｎとしたとき、ハミング距離が
０．．ｎ未満の任意距離、ｎ未満の任意距離以下、一定
値以上の関係を用いた曖昧さをもつ連想メモリも、同様
な考え方に基づいて構成できる。
例としてｎ＝３、４の場合に必要とする伝搬情報の論理
式を以下に示す。以上説明したように、本発明によれば
、従来きわめて複雑な手法を用いて実現したいた曖昧さ
をもつ連想機能を、ハミング距離の利用という全く新し
い視点に立つて、きわめて小規模な単位セルの繰り返し
構造でハード的に実現することが出来るので次のような
利点が生ずる。（１）従来の複雑な手法を用いる場合と
異なり、メモリ装置自体が曖昧さをもつ連想機能を有し
ており、メモリ装置以外の論理装置を必要としない。
式を以下に示す。以上説明したように、本発明によれば
、従来きわめて複雑な手法を用いて実現したいた曖昧さ
をもつ連想機能を、ハミング距離の利用という全く新し
い視点に立つて、きわめて小規模な単位セルの繰り返し
構造でハード的に実現することが出来るので次のような
利点が生ずる。（１）従来の複雑な手法を用いる場合と
異なり、メモリ装置自体が曖昧さをもつ連想機能を有し
ており、メモリ装置以外の論理装置を必要としない。
（２）このため、本連想メモリ装置をパターン認識処理
装置へ応用すると、高速化、処理装置の小形化、低価格
化がはかれる。
装置へ応用すると、高速化、処理装置の小形化、低価格
化がはかれる。
（３）本連想メモリ装置の単位セルは、記憶素子と数個
の論理ゲートで構成でき、設計は容易である。
の論理ゲートで構成でき、設計は容易である。
（４）本連想メモリ装置は、単位セルをアレイ状に配置
することによつて設計できるため、従来のメモリ装置の
設計に要した手間と同程度の手間で、本連想メモリ装置
を設計することができる。
することによつて設計できるため、従来のメモリ装置の
設計に要した手間と同程度の手間で、本連想メモリ装置
を設計することができる。
（５）ハミング距離の算出に必要な論理演算機能を各単
位セルに分散的に配置しているため、単位セル以外にハ
ミング距離算出用回路を設ける必要がない。
位セルに分散的に配置しているため、単位セル以外にハ
ミング距離算出用回路を設ける必要がない。
第１図は本発明による連想メモリ装置の一実施例の単位
セルを示す図、第２図は第１図の単位セルを用いたメモ
リセル・アレイを示す図である。 １・・・・・記憶素子、２・・・・・・検索データ入力
端、ノ３，４・・・・・・伝搬情報入力端、５・・・・
・・排他的論理和ゲート、６・・・・・・論理積ゲート
、７・・・・・・論理和ゲート、９，１０・・・・・・
伝搬情報出力端、１１〜２６・・・・・単位セル、２７
〜３０・・・・・・検索データ供給線。
セルを示す図、第２図は第１図の単位セルを用いたメモ
リセル・アレイを示す図である。 １・・・・・記憶素子、２・・・・・・検索データ入力
端、ノ３，４・・・・・・伝搬情報入力端、５・・・・
・・排他的論理和ゲート、６・・・・・・論理積ゲート
、７・・・・・・論理和ゲート、９，１０・・・・・・
伝搬情報出力端、１１〜２６・・・・・単位セル、２７
〜３０・・・・・・検索データ供給線。
Claims (1)
- 【特許請求の範囲】 １ 各記憶データと検索データとのハミング距離を算出
し、前記検索データと完全に一致している記憶データ以
外の、前記検索データとハミング距離によつて関係づけ
られた記憶データをも選択して出力する機能を有してい
ることを特徴とする連想メモリ装置。 ２ 前記ハミング距離の算出にあたつて、必要な論理演
算機能を記憶データの各ビットに対応するメモリ・セル
内に分散的に配置して単位セルを構成し、かつ、該単位
セルをアレイ状に配置することにより、前記ハミング距
離の算出を行うことを特徴とする特許請求の範囲第１項
記載の連想メモリ装置。 ３ 前記検索データとハミング距離によつて関係づけら
れた記憶データを選択して出力するにあたつて、ハミン
グ距離が零、一定値未満の任意距離、一定値未満の任意
距離以下、一定値以上という関係を識別し、これらの関
係のうち、検索データと所望の関係にある記憶データを
出力することを特徴とする特許請求の範囲第１項記載の
連想メモリ装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP54095298A JPS6045501B2 (ja) | 1979-07-26 | 1979-07-26 | 連想メモリ装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP54095298A JPS6045501B2 (ja) | 1979-07-26 | 1979-07-26 | 連想メモリ装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5619182A JPS5619182A (en) | 1981-02-23 |
| JPS6045501B2 true JPS6045501B2 (ja) | 1985-10-09 |
Family
ID=14133858
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP54095298A Expired JPS6045501B2 (ja) | 1979-07-26 | 1979-07-26 | 連想メモリ装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6045501B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6219726A (ja) * | 1985-07-18 | 1987-01-28 | Ascii Corp | 色コ−ド検出回路 |
| JPH0460782A (ja) * | 1990-06-28 | 1992-02-26 | Tsubakimoto Chain Co | パターン処理装置 |
| JP6085187B2 (ja) * | 2013-02-13 | 2017-02-22 | 国立大学法人広島大学 | 連想メモリ |
-
1979
- 1979-07-26 JP JP54095298A patent/JPS6045501B2/ja not_active Expired
Also Published As
| Publication number | Publication date |
|---|---|
| JPS5619182A (en) | 1981-02-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6353910B1 (en) | Method and apparatus for implementing error correction coding (ECC) in a dynamic random access memory utilizing vertical ECC storage | |
| US9240237B2 (en) | Semiconductor device and method of writing/reading entry address into/from semiconductor device | |
| JPS61107596A (ja) | 連想記憶装置 | |
| JPS6116351A (ja) | システムメモリ用単一誤り訂正回路 | |
| JPH0248931B2 (ja) | ||
| US4833602A (en) | Signal generator using modulo means | |
| US4016409A (en) | Longitudinal parity generator for use with a memory | |
| JPS6045501B2 (ja) | 連想メモリ装置 | |
| US4519079A (en) | Error correction method and apparatus | |
| JPH0413735B2 (ja) | ||
| JPH0421997A (ja) | 連想記憶回路 | |
| KR100517765B1 (ko) | 캐시 메모리 및 그 제어 방법 | |
| JPS58211392A (ja) | 半導体記憶装置 | |
| US5603023A (en) | Processor circuit for heapsorting | |
| WO2000010089A1 (en) | Content addressable memory addressable by redundant form input data | |
| US4890255A (en) | Data processing device for simultaneously activating and applying paraller trains of commands to memories for storing matrices | |
| JPH0370416B2 (ja) | ||
| JPH10334697A (ja) | 半導体記憶装置およびその誤り訂正方法 | |
| Thornton | A signed binary addition circuit based on an alternative class of addition tables | |
| JPH02126321A (ja) | 命令コードのデコード装置 | |
| SU409221A1 (ru) | Вероятностный сумматор параллельного типа | |
| JPS6261120A (ja) | けた上げ選択加算器 | |
| JPH0550078B2 (ja) | ||
| US3154676A (en) | Change adder | |
| JPS60129853A (ja) | アドレス発生装置 |