Top > Search of Japanese Patents > ASSOCIATIVE MEMORY

ASSOCIATIVE MEMORY

Patent code P100001371
Posted date Dec 22, 2010
Application number P2009-229601
Publication number P2011-076688A
Patent number P5224601
Date of filing Oct 1, 2009
Date of publication of application Apr 14, 2011
Date of registration Mar 22, 2013
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)小出 哲士
  • (In Japanese)アンサリ タニア
  • (In Japanese)今福 渉
  • (In Japanese)賀谷 彰大
Applicant
  • (In Japanese)国立大学法人広島大学
Title ASSOCIATIVE MEMORY
Abstract PROBLEM TO BE SOLVED: To provide an associative memory that reduces false searches.
SOLUTION: A storage circuit S1 in the associative memory 100 stores reference data. A comparison circuit C1 receives retrieval data from the outside and obtains a distance (e.g. hamming distance) between the reference data and retrieval data. An oscillating circuit OC1 outputs a pulse signal P1 having an oscillation frequency corresponding to the distance obtained by the comparison circuit C1. Oscillating circuits OC2 to OCR output pulse signals P2 to PR having oscillation frequencies according to the distance between reference data and retrieval data in corresponding storage circuits S2 to SR. A WTA circuit 20 receives the pulse signals P1 to PR. Reference data stored in a storage circuit corresponding to an oscillating circuit having output a pulse signal having highest oscillation frequency, are decided as reference data (Winner) most similar to the retrieval data.
Outline of related art and contending technology (In Japanese)

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

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

Field of industrial application (In Japanese)

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

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

【請求項12】
 
請求項3に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発手段から出力されるパルス信号のうち、最も早く出力されたパルス信号を検知する検知手段を備え、
前記各判定手段は、
対応する前記発手段から出力信号を受け、前記検知手段が最も早く出力されたパルス信号を検知したとき、前記出力信号をラッチする、連想メモリ。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2009229601thum.jpg
State of application right Registered
Reference ( R and D project ) (In Japanese)小出哲士のホームページ


PAGE TOP

close
close
close
close
close
close
close