TOP > 国内特許検索 > 最小ユークリッド距離検索連想メモリ装置

最小ユークリッド距離検索連想メモリ装置 コモンズ 新技術説明会

国内特許コード P07P005167
掲載日 2007年4月13日
出願番号 特願2005-266250
公開番号 特開2007-080375
登録番号 特許第4892720号
出願日 平成17年9月14日(2005.9.14)
公開日 平成19年3月29日(2007.3.29)
登録日 平成24年1月6日(2012.1.6)
発明者
  • マタウシュ ハンスユルゲン
  • 小出 哲士
  • アベディン モハマド アノワルル
出願人
  • 学校法人広島大学
発明の名称 最小ユークリッド距離検索連想メモリ装置 コモンズ 新技術説明会
発明の概要

【課題】 ハードウェアで全並列最小ユークリッド距離検索メモリを実現する効果的なアーキテクチャを提供する。
【解決手段】 W個の差の絶対値計算回路の出力を全て重み比較回路WCに入力し、重み比較回路WCにおいて差の絶対値の2乗を計算する。これにより、検索データと参照データのユークリッド距離の2乗の計算を実現する。このユークリッド距離の2乗の計算結果から最小距離の参照データを検索する。このように、最も近いユークリッド距離を持つパターンデータを検索するためにユークリッド距離の2乗を用いているため、平方根の計算は必要ではなく、ユークリッド距離計算回路を小面積で実現でき、連想メモリ装置も、低消費電力かつ小面積で実現可能である。
【選択図】 図2

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


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



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.

産業上の利用分野


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

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

産業区分
  • 記憶装置
国際特許分類(IPC)
画像

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

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


PAGE TOP

close
close
close
close
close
close
close