TOP > 国内特許検索 > 連想メモリ

連想メモリ

国内特許コード P100001371
掲載日 2010年12月22日
出願番号 特願2009-229601
公開番号 特開2011-076688
登録番号 特許第5224601号
出願日 平成21年10月1日(2009.10.1)
公開日 平成23年4月14日(2011.4.14)
登録日 平成25年3月22日(2013.3.22)
発明者
  • マタウシュ ハンスユルゲン
  • 小出 哲士
  • アンサリ タニア
  • 今福 渉
  • 賀谷 彰大
出願人
  • 国立大学法人広島大学
発明の名称 連想メモリ
発明の概要

【課題】誤検索を抑制できる連想メモリを提供する。
【解決手段】
連想メモリ100内の保存回路Sは参照データを保存する。比較回路Cは外部から検索データを受け、参照データと検索データとの距離(たとえばハミング距離)を求める。発振回路OCは、比較回路Cが求めた距離に応じた発振周波数を有するパルス信号Pを出力する。同様に、発振回路OC~OCは、対応する保存回路S~S内の参照データと検索データとの距離に応じた発振周波数を有するパルス信号P~Pを出力する。
WTA回路20は、パルス信号P~Pを受ける。そして、最も発振周波数が高いパルス信号を出力した発振回路に対応する保存回路に保存された参照データを、検索データに最も類似した参照データ(Winner)に決定する。
【選択図】図1

従来技術、競合技術の概要


画像圧縮及び画像認識の分野において、最小距離検索機能を有する連想メモリが注目されている。連想メモリはWビット幅R個の参照データを記憶する(W及びRは自然数)。データ列(検索データ)が入力されたとき、連想メモリは、複数の参照データの中から最も類似した(距離の近い)データを検索する。



入力されたデータ列と最も類似の参照データを見つけることは、パターンマッチングにおいて基本的な処理である(非特許文献1参照)。したがって、画像圧縮や画像認識等の情報処理において、最小距離検索連想メモリは有用である。最小距離検索連想メモリはたとえば、特許文献1に開示されている。さらに、ハミング距離、マンハッタン距離及びユークリッド距離の検索機能を有する全並列型の連想メモリが特許文献2、非特許文献2及び非特許文献3に開示されている。

産業上の利用分野


本発明は、最小距離検索機能を有する連想メモリに関する。

特許請求の範囲 【請求項1】
複数の参照データを保存する保存手段と、
入力された検索データと、前記複数の参照データの各々とを並列に比較して、前記検索データと前記参照データとの距離を、前記参照データごとに求める比較手段と、
前記求めた距離に応じた周波数を有するパルス信号を前記参照データごとに生成するパルス生成手段と、
前記生成された複数のパルス信号の周波数に基づいて、前記複数の参照データのうち、前記検索データに最も近い参照データを決定する決定手段とを備える連想メモリ。

【請求項2】
請求項1に記載の連想メモリであって、
前記パルス生成手段は、
前記複数の参照データに対応した複数の発振手段を備え、
前記各発振手段は、前記検索データと前記対応する参照データとの距離が小さいほど、周波数の高い前記パルス信号を出力し、
前記決定手段は、発振周波数の最も高いパルス信号を出力した発振手段に対応した参照データを、前記検索データに最も近い参照データに決定する連想メモリ。

【請求項3】
請求項2に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発振手段に対応した複数の判定手段を備え、
前記決定手段は、前記複数の判定手段のうち、前記発振手段からのパルス信号を最も早く受信した判定手段に基づいて、前記検索データに最も近い参照データを決定する連想メモリ。

【請求項4】
求項3に記載の連想メモリであってさらに、
前記発振手段に対応した複数の分周手段を備え、
各分周手段は、対応する発振手段から出力されたパルス信号を所定の分周比で分周して、対応する判定手段に出力する連想メモリ。

【請求項5】
請求項3に記載の連想メモリであって、
前記決定手段は、
前記複数の判定手段に接続されたラッチ指示ノードと、
前記ラッチ指示ノードを充電する充電手段とを備え、
前記各判定手段は、
対応する前記発振手段からの出力信号を受け、前記出力信号が前記パルス信号であるとき前記ラッチ指示ノードを放電する放電手段と、
前記ラッチ指示ノードが放電されたときに前記放電手段が受けている前記出力信号をラッチするラッチ手段とを備える連想メモリ。

【請求項6】
請求項2に記載の連想メモリであって、
前記決定手段は、
複数段のトーナメント式に接続された複数の判定手段を備え、
第1段目に配置された複数の判定手段の各々は、
各々が対応する発振手段の出力信号を受ける複数の第1のパルス判定手段と、
前記複数の第1のパルス判定手段に接続されたパルス受付判定ノードと、
前記パルス受付判定ノードを充電する充電手段とを備え、
前記第1のパルス判定手段は、
前記対応する発振手段の出力信号としてパルス信号を受けたとき、前記パルス受付判定ノードを放電する第1の放電手段と、
クロック信号を受けたとき前記第1の放電手段が受けている出力信号をラッチするラッチ手段とを備え、
第2段目以降に配置された判定手段は、
各々が、前段の対応する判定手段のパルス受付判定ノードに接続された、複数の第2のパルス判定手段と、
前記複数の第2のパルス判定手段が接続されたパルス受付判定ノードと、
前記充電手段とを備え、
前記第2のパルス判定手段は、
前記前段の対応する判定手段のパルス受付判定ノードが放電されたとき、前記パルス受付判定ノードを放電する第2の放電手段を備え、
最上段の判定手段はさらに、
前記パルス受付判定ノードが放電されたとき、クロック信号を出力するクロック信号生成手段を備える連想メモリ。

【請求項7】
請求項2又は請求項3に記載の連想メモリであって、
前記発手段は、直列に接続された複数のインバータと、
前記検索データと前記対応する参照データとの距離に応じて、前記インバータの段数を選択する段数選択手段とを備える連想メモリ。

【請求項8】
請求項2に記載の連想メモリであって、
前記決定手段は、
複数の前記発振手段に対応する複数のカウンタ手段を備え、
前記カウンタ手段は、対応する発振手段からパルス信号を受け、所定数のパルスを受けたとき活性化された出力信号を生成する連想メモリ。

【請求項9】
請求項2に記載の連想メモリであってさらに、
j(jは、1<j≦kを満たす整数、kは、2以上の整数)回目の検索において、j-1回目までに決定手段により決定された参照データに対応する発振手段から出力されたパルス信号を無効化するパルス無効化手段を備えることを特徴とする連想メモリ。

【請求項10】
請求項2に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記各参照ビットデータと前記各検索ビットデータとをハミング距離に基づいて比較し、
前記発手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、L+1個(Lは自然数)通りの遅延時間を設定可能であり、L個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。

【請求項11】
請求項2に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記参照ビットデータと前記検索ビットデータとをマンハッタン距離に基づいて比較し、
前記発振手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、2(kは自然数)通りの遅延時間を設定可能であり、k個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。

【請求項12】
請求項3に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発手段から出力されるパルス信号のうち、最も早く出力されたパルス信号を検知する検知手段を備え、
前記各判定手段は、
対応する前記発手段から出力信号を受け、前記検知手段が最も早く出力されたパルス信号を検知したとき、前記出力信号をラッチする、連想メモリ。
産業区分
  • 記憶装置
国際特許分類(IPC)
画像

※ 画像をクリックすると拡大します。

JP2009229601thum.jpg
出願権利状態 権利存続中
参考情報 (研究プロジェクト等) 小出哲士のホームページ


PAGE TOP

close
close
close
close
close
close
close