Top > Search of Japanese Patents > ASSOCIATIVE MEMORY DEVICE FOR RETRIEVING MINIMUM EUCLIDEAN DISTANCE

ASSOCIATIVE MEMORY DEVICE FOR RETRIEVING MINIMUM EUCLIDEAN DISTANCE meetings

Patent code P07P005167
Posted date Apr 13, 2007
Application number P2005-266250
Publication number P2007-080375A
Patent number P4892720
Date of filing Sep 14, 2005
Date of publication of application Mar 29, 2007
Date of registration Jan 6, 2012
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)小出 哲士
  • (In Japanese)アベディン モハマド アノワルル
Applicant
  • (In Japanese)学校法人広島大学
Title ASSOCIATIVE MEMORY DEVICE FOR RETRIEVING MINIMUM EUCLIDEAN DISTANCE meetings
Abstract

PROBLEM TO BE SOLVED: To provide an effective architecture for obtaining a memory for retrieving fully parallel minimum Euclidean distance by hardware.

SOLUTION: All outputs of circuits for calculating absolute values of W pieces of differences are input to a weight comparator circuit WC to calculate square of absolute values of the differences in the weight comparator circuit WC. By this procedure, the calculation of square of Euclidean distances of retrieval data and reference data is achieved. The reference data of minimum distance are retrieved from a calculation result of square of this Euclidean distance. Thus, since square of Euclidean distance is used for retrieving pattern data having nearest Euclidean distance, a calculation of square root is not required, and a Euclidean distance calculating circuit is obtained by a small area, and the associative memory device is also obtainable by low power consumption and small area.

Outline of related art and contending technology (In Japanese)


近年、情報処理技術、特に画像圧縮・画像認識の分野においては、最小距離検索機能を持つ連想メモリが注目されている。連想メモリは、知的情報処理で必要となる物体認識のためのパターンマッチングやコードブックと呼ばれるデータ群を利用したデータ圧縮に非常に有効である。連想メモリは、入力されたデータ列(検索データ)に対して連想メモリ内にある複数の参照データ中から最も類似した(距離の近い)データを検索する機能を持つ機能メモリの代表的なものの一つであり、その優れた検索機能により、先に述べた画像圧縮・画像認識などのパターンマッチング機能を有するアプリケーションにおいて、その性能を飛躍的に向上できるものとして期待されている。



kビット×Wユニット幅R個の参照データから、入力データと最も似ているデータを見つけることはパターンマッチングにおいて基本的な処理である(非特許文献1)。ゆえに画像圧縮、画像認識などの情報処理には、最小距離検索連想メモリ(特許文献1)は中核を担う部分であるといえる。既存の全並列最小距離検索連想メモリとしては、単純な距離であるマンハッタン、ハミング距離の検索機能を持つものがそれぞれ提案されている。これらの距離は以下の数1で定義される(非特許文献2)。



【数式1】




ここで、SW={SW1,SW2,・・・,SWw}は入力データ、REF={REF1,REF2,・・・,REFw}は参照データを表す。SWiとREFiが1ビットの2進数である場合、Dはハミング距離となる。また、SWiとREFiがkビット(k>1)の2進数であるときに、Dはマンハッタン距離となる。これまでに、全並列最小ハミング距離検索アーキテクチャ(非特許文献2)や全並列最小マンハッタン距離検索アーキテクチャ(非特許文献3、特許文献2)が提案されてきている。



しかし、いくつかのアプリケーションで使用されるアルゴリズムにおいては、距離指標としてユークリッド距離を適用することが望まれている。ユークリッド距離は数2で表されるものであり、ベクトル空間における2点間の距離を測定する尺度としてはマンハッタン距離よりも正確である。



【数式2】



【特許文献1】特開2002-288985号公報

【特許文献2】特開2005-209317号公報

【特許文献3】特開2004-5825号公報

【非特許文献1】D. R. Tveter, "The Pattern Recognition Basis of Artificial Intelligence," Los Alamitos, CA: IEEE computer society, 1998.

【非特許文献2】H.J.Mattausch,T.Gyohten, Y. Soda, and T. Koide, "Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance," IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002.

【非特許文献3】H. J. Mattausch, N. Omori, S. Fukae, T. Koide and T. Gyohten, "Fully-Parrallel Pattern-Matching Engine with Dynamic Adaptibility to Hamming or Manhattan Distance," 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002.

【非特許文献4】P. Heim, F. Krummenacher and E. A. Vittoz, "CMOS Full-wave Operational Transconductance Rectifier with Improved DC Transfer Characteristic," Electron. Lett., vol. 28, pp. 333-334, 1992.

【非特許文献5】Y. Tulay and J. S. Marsland, "A Conic Section Function Network Synapse and Neuron Implementation in VLSI Hardware," IEEE Conf. Neural Networks, pp. 974-979, 1996.

【非特許文献6】S. Churcher, A. F. Murray and H. M. Reekie, "Programmable Analogue VLSI for Radial Basis Function Networks," Electron. Lett., vol. 29, pp.1603-1605, 1993.

【非特許文献7】O. Landolt, E. Vittoz and P. Heim, "CMOS Selfbiased Euclidean Distance Computing Circuit with Highdynamic Range," Electron. Lett., vol. 28, pp. 352-354, 1992.

【非特許文献8】S. Collins, G. F. Marshall and D. R. Brown, "An Analogue Radial Basis Function Circuit Using a Compact Euclidean Distance Calculator," IEEE Int. Symp. Circuits Systems, pp. 233-236, 1994.

【非特許文献9】P. Hasler, B. A. Minch, J. Dugger, and C. Dorio, "Adaptive Circuits and Synapses using Floating Gate Devices," in Learning on Silicon: Adaptive VLSI Neural Systems, G. Cauwenberghs and M. A. Bayoumi, Eds. Boston, MA: Kluwer, pp. 33-65, 1999.

【非特許文献10】M. Freeman, M. Weeks and J. Austin, "Hardware Implementation of Similarity Functions," IADIS International Conference on Applied Computing, Algarve, Portugal, vol. 2, pp. 329-332, 2005.

【非特許文献11】Y. Yano, T. Koide and H. J. Mattausch, "Fully Parallel Nearest Manhattan-distance Search Memory with Large Reference-pattern Number," Extend. Abst. of the Int. Conf. on Solid State Devices and Materials (SSDM'2002), pp. 254-255, 2002.

Field of industrial application (In Japanese)


本発明は、カラー、グレースケールの画像圧縮、画像認識等の情報処理装置に用いられ、全並列処理による最小ユークリッド距離検索機能を有する連想メモリ装置に関する。

Scope of claims (In Japanese)
【請求項1】
 
検索データについて複数の参照データと並列に差の絶対値計算に基づくユークリッド距離の2乗を計算する距離計算回路と、前記ユークリッド距離の2乗の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、
前記検索データおよび参照データがそれぞれkビット(k>1)単位でユニット化されている場合に、
前記距離計算回路は、
前記参照データをユニット単位で保存するためのW列R行のユニット保存回路と、
ユニット毎に参照データと検索データの差の絶対値計算を行うW列R行のユニット比較回路と、
行毎に前記W列のユニット比較回路で計算された差の絶対値の2乗の和に相当する電流または電圧信号を生成するR行のワード重み比較回路とを備える、
ことを特徴とする最小ユークリッド距離検索連想メモリ装置。

【請求項2】
 
請求項1において、
前記R行のワード重み比較回路の各々は、
対応する行のユニット比較回路の各々に対応させて電流変換回路とアナログ2乗回路とが設けられており、
前記電流変換回路の各々は、
対応するユニット比較回路から出力されるディジタル信号をアナログ電流に変換するものであり、
前記アナログ2乗回路の各々は、
対応する電流変換回路からの出力電流を2乗して対応する行のマッチラインに出力するものである、
ことを特徴とする最小ユークリッド距離検索連想メモリ。

【請求項3】
 
請求項1において、
前記R行のワード重み比較回路の各々は、
対応する行のユニット比較回路の各々に対応させてディジタル2乗回路と電流変換回路とが設けれており、
前記ディジタル2乗回路の各々は、
対応するユニット比較回路から出力されるディジタル信号を2乗するものであり、
前記電流変換回路の各々は、
対応するディジタル2乗回路から出力されるディジタル信号をアナログ電流に変換して対応する行のマッチラインに出力するものである、
ことを特徴とする最小ユークリッド距離検索連想メモリ。

【請求項4】
 
請求項1において、
前記距離計算回路および前記検索回路は半導体集積回路の同一チップ上に形成されている、
ことを特徴とする最小ユークリッド距離検索連想メモリ。

Industrial division
  • Storage device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2005266250thum.jpg
State of application right Right is in force
Reference ( R and D project ) (In Japanese)小出哲士のホームページ


PAGE TOP

close
close
close
close
close
close
close