(57)【要約】【課題】  ハードウェアで全並列最小ユークリッド距離検索メモリを実現する効果的なアーキテクチャを提供する。【解決手段】  Ｗ個の差の絶対値計算回路の出力を全て重み比較回路ＷＣに入力し、重み比較回路ＷＣにおいて差の絶対値の２乗を計算する。これにより、検索データと参照データのユークリッド距離の２乗の計算を実現する。このユークリッド距離の２乗の計算結果から最小距離の参照データを検索する。このように、最も近いユークリッド距離を持つパターンデータを検索するためにユークリッド距離の２乗を用いているため、平方根の計算は必要ではなく、ユークリッド距離計算回路を小面積で実現でき、連想メモリ装置も、低消費電力かつ小面積で実現可能である。【選択図】  図２
2007080375.tif 000002
【特許請求の範囲】
【請求項１】
検索データについて複数の参照データと並列に差の絶対値計算に基づくユークリッド距離の２乗を計算する距離計算回路と、前記ユークリッド距離の２乗の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、
前記検索データおよび参照データがそれぞれｋビット（ｋ＞１）単位でユニット化されている場合に、
前記距離計算回路は、
前記参照データをユニット単位で保存するためのＷ列Ｒ行のユニット保存回路と、
ユニット毎に参照データと検索データの差の絶対値計算を行うＷ列Ｒ行のユニット比較回路と、
行毎に前記Ｗ列のユニット比較回路で計算された差の絶対値の２乗の和に相当する電流または電圧信号を生成するＲ行のワード重み比較回路とを備える、
ことを特徴とする最小ユークリッド距離検索連想メモリ装置。
【請求項２】
請求項１において、
前記Ｒ行のワード重み比較回路の各々は、
対応する行のユニット比較回路の各々に対応させて電流変換回路とアナログ２乗回路とが設けられており、
前記電流変換回路の各々は、
対応するユニット比較回路から出力されるディジタル信号をアナログ電流に変換するものであり、
前記アナログ２乗回路の各々は、
対応する電流変換回路からの出力電流を２乗して対応する行のマッチラインに出力するものである、
ことを特徴とする最小ユークリッド距離検索連想メモリ。
【請求項３】
請求項１において、
前記Ｒ行のワード重み比較回路の各々は、
対応する行のユニット比較回路の各々に対応させてディジタル２乗回路と電流変換回路とが設けれており、
前記ディジタル２乗回路の各々は、
対応するユニット比較回路から出力されるディジタル信号を２乗するものであり、
前記電流変換回路の各々は、
対応するディジタル２乗回路から出力されるディジタル信号をアナログ電流に変換して対応する行のマッチラインに出力するものである、
ことを特徴とする最小ユークリッド距離検索連想メモリ。
【請求項４】
請求項１において、
前記距離計算回路および前記検索回路は半導体集積回路の同一チップ上に形成されている、
ことを特徴とする最小ユークリッド距離検索連想メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラー、グレースケールの画像圧縮、画像認識等の情報処理装置に用いられ、全並列処理による最小ユークリッド距離検索機能を有する連想メモリ装置に関する。
【背景技術】
【０００２】
近年、情報処理技術、特に画像圧縮・画像認識の分野においては、最小距離検索機能を持つ連想メモリが注目されている。連想メモリは、知的情報処理で必要となる物体認識のためのパターンマッチングやコードブックと呼ばれるデータ群を利用したデータ圧縮に非常に有効である。連想メモリは、入力されたデータ列（検索データ）に対して連想メモリ内にある複数の参照データ中から最も類似した（距離の近い）データを検索する機能を持つ機能メモリの代表的なものの一つであり、その優れた検索機能により、先に述べた画像圧縮・画像認識などのパターンマッチング機能を有するアプリケーションにおいて、その性能を飛躍的に向上できるものとして期待されている。
【０００３】
ｋビット×Ｗユニット幅Ｒ個の参照データから、入力データと最も似ているデータを見つけることはパターンマッチングにおいて基本的な処理である（非特許文献１）。ゆえに画像圧縮、画像認識などの情報処理には、最小距離検索連想メモリ（特許文献１）は中核を担う部分であるといえる。既存の全並列最小距離検索連想メモリとしては、単純な距離であるマンハッタン、ハミング距離の検索機能を持つものがそれぞれ提案されている。これらの距離は以下の数１で定義される（非特許文献２）。
【０００４】
【数１】
2007080375.tif 000003
【０００５】
ここで、ＳＷ＝｛ＳＷ1，ＳＷ2，・・・，ＳＷw｝は入力データ、ＲＥＦ＝｛ＲＥＦ1，ＲＥＦ2，・・・，ＲＥＦw｝は参照データを表す。ＳＷiとＲＥＦiが１ビットの２進数である場合、Ｄはハミング距離となる。また、ＳＷiとＲＥＦiがｋビット（ｋ＞１）の２進数であるときに、Ｄはマンハッタン距離となる。これまでに、全並列最小ハミング距離検索アーキテクチャ（非特許文献２）や全並列最小マンハッタン距離検索アーキテクチャ（非特許文献３、特許文献２）が提案されてきている。
【０００６】
しかし、いくつかのアプリケーションで使用されるアルゴリズムにおいては、距離指標としてユークリッド距離を適用することが望まれている。ユークリッド距離は数２で表されるものであり、ベクトル空間における２点間の距離を測定する尺度としてはマンハッタン距離よりも正確である。
【０００７】
【数２】
2007080375.tif 000004
【特許文献１】特開２００２−２８８９８５号公報
【特許文献２】特開２００５−２０９３１７号公報
【特許文献３】特開２００４−５８２５号公報
【非特許文献１】D. R. Tveter, "The Pattern Recognition Basis of Artificial Intelligence," Los Alamitos, CA: IEEE computer society, 1998.
【非特許文献２】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.
【非特許文献３】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.
【非特許文献４】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.
【非特許文献５】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.
【非特許文献６】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.
【非特許文献７】O. Landolt, E. Vittoz and P. Heim, "CMOS Selfbiased Euclidean Distance Computing Circuit with Highdynamic Range," Electron. Lett., vol. 28, pp. 352-354, 1992.
【非特許文献８】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.
【非特許文献９】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.
【非特許文献１０】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.
【非特許文献１１】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.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
これまでに多くのユークリッド距離を計算する回路が提案されている（非特許文献４〜７）。しかし、それらの大部分において計算できる距離の大きさの制限や回路規模が大きいことなどの欠点がある。
【０００９】
これらの問題を解決するために、フローティングゲートを用いたいくつかの回路が開発されている（非特許文献８、９）。しかし、この回路は回路シミュレーションが難しいために、チップ製造前に回路動作を予想して設計することが難しい。
【００１０】
一方、ユークリッド距離を逐次的に計算する回路とそのハードウェア記述言語ＶＨＤＬによる記述が報告されている（非特許文献１０）。この回路は乗算器、加算器、レジスタ、平方根計算回路を用いたディジタル回路であるが、実装トランジスタ数が非常に多いために各参照データと入力データを全並列処理する連想メモリには適していない。
【００１１】
ユークリッド距離を計算するためには二乗と平方根という複雑な計算が必要である。特に平方根は最新のプロセッサを使用しても負荷の大きな計算である。なぜなら平方根は近似を繰り返すこと、つまり値を入れてその値がエラーマージン以内になるまで繰り返し計算をすることにより算出されるからである。ハードウェアとして平方根の計算機能を持っていないような場合に、たとえ小さな値の平方根の計算でさえ不可能である。
【００１２】
以上のように、ハードウェアで全並列最小ユークリッド距離検索メモリを実現する効果的なアーキテクチャはこれまで提案されていない。
【課題を解決するための手段】
【００１３】
最も近いユークリッド距離を持つパターンデータを検索するために平方根の計算は必要ではなく２乗した距離だけを比較することで十分である。なぜならパターンマッチングでは、距離の相対的な大きさの比較だけが必要であり、平方根はこの相対的な大きさを変えないからである。本発明に係る連想メモリ装置は、このような観点に基づいており、以下のように構成される。
【００１４】
検索データについて複数の参照データと並列に差の絶対値計算に基づくユークリッド距離の２乗を計算する距離計算回路と、前記ユークリッド距離の２乗の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、
前記検索データおよび参照データがそれぞれｋビット（ｋ＞１）単位でユニット化されている場合に、
前記距離計算回路は、
前記参照データをユニット単位で保存するためのＷ列Ｒ行のユニット保存回路（ＵＳ）と、
ユニット毎に参照データと検索データの差の絶対値計算を行うＷ列Ｒ行のユニット比較回路（ＵＣ）と、
行毎に前記Ｗ列のユニット比較回路で計算された差の絶対値の２乗の和に相当する電流または電圧信号を生成するＲ行のワード重み比較回路（ＷＣ）とを備えることを特徴とする。
【発明の効果】
【００１５】
本発明による連想メモリ装置では、距離計算回路においてユークリッド距離の２乗を計算し、このユークリッド距離の２乗の計算結果から最小距離の参照データを検索回路において検索するようにしており、平方根計算を行わないため、回路規模の縮小および計算処理の高速化を実現することができる。この結果、連想メモリ装置への適用において、低消費電力で小面積なチップ構成で最小ユークリッド距離検索を実現することができる。
【００１６】
このように、本発明では、全並列連想メモリベースシステムにおいて、カラーやグレースケールの画像圧縮・画像認識などに必要なユークリッド距離計算回路を開発し、低消費電力で小面積な最小ユークリッド距離検索連想メモリ装置を実現する。特にこの回路構成は、パターンマッチングアプリケーション（例えば、ネットワークルータ、コードブックベースデータ圧縮、および、対象認識）に対して従来のＣＭＯＳ技術を用いて高効率な全並列連想メモリ装置のチップ化を可能にする。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照して、本発明を実施するための最良な形態を詳細に説明する。
［全並列型連想メモリアーキテクチャ］
図１は、本発明に係る全並列型連想メモリ装置のアーキテクチャを示すブロック図である。メモリコア部分は、メモリ領域１００、ウィナー・ラインナップ増幅回路（以下、ＷＬＡ回路（Winner Line-Up Amplifier））２００、全ウィナー取得回路（以下、ＷＴＡ回路（Winner Take All Circuit））３００で構成されており、また、周辺回路として列デコーダおよびＲ／Ｗ回路（Column Decoder and Read/Write(k×W Columns)）１１０、行デコーダ（Row Decoder(R Rows)）１２０、検索データ保存回路（Search Data(k×W Bits)）１３０を持つ。この連想メモリ装置は集積回路として１チップ上に実現されており、上記メモリコア部分および周辺回路はこの１チップ上に形成されている。
【００１８】
メモリ領域１００は、参照データをユニット（ｋビット）単位で保存するためのＳＲＡＭセルで形成されるＷ×Ｒ個のユニット保存回路（Unit Storage：ＵＳ）、ユニット毎に参照データと検索データの差の絶対値計算を行うＷ×Ｒ個のユニット比較回路（Unit Comparison：ＵＣ）、計算した絶対差をアナログ電圧（あるいは電流）に変換し変換結果を２乗するＲ個のワード重み比較回路（Word Comparison：ＷＣ）により構成されている。
【００１９】
ワード重み比較回路ＷＣで生成された信号Ｃ（Comparison Signal）はＷＬＡ回路２００に入り、ＷＬＡ回路２００がこの信号Ｃを回路自身のバランスにより制御し、最初の段階で各行の電圧の差を最も大きく増幅する。ＷＬＡ回路２００とＷＴＡ回路３００は、行数Ｒに対する面積増加の割合が行数Ｒに対して線形のＯ(Ｒ)になるという特徴がある。
【００２０】
ＷＴＡ回路３００は、ＷＬＡ回路２００により増幅された各行の電圧出力ＬＡの差を更に増幅する機能を持つ。ＷＴＡ回路３００の出力ＷＴＡにおいては、winner（ウィナー）行が"１"、その他のloser（ルーザ）行が"０"のディジタル信号となる。ＷＬＡ回路２００は、フィードバック信号をワード重み比較回路ＷＣに返す際に、当該ＷＬＡ回路２００に内蔵された電圧フォロワ回路を用いることにより、フィードバックを高速化している。
［ユークリッド距離計算回路］
最も近いユークリッド距離を持つパターンデータを検索するために平方根の計算は必要ではなく２乗した距離だけを比較することで十分である。なぜならパターンマッチングでは、距離の相対的な大きさの比較だけが必要であり、平方根はこの相対的な大きさを変えないからである。本実施形態の連想メモリ装置に用いられるユークリッド距離計算回路は、このような観点に基づいて構成されている。
【００２１】
本実施形態によるユークリッド距離計算回路は、図１に示すように、取り扱うデータを符号化したｋビット（ｋ＞１）相当のユニットをＷ個並べたものとなる。連想メモリ装置の入力となる検索データと連想メモリ装置内に格納されている参照データ（ｉ行）をそれぞれＳＷ、ＲＥＦiとおくとき、ＳＷとＲＥＦiの間のユークリッド距離の２乗は数３のように表される。
【００２２】
【数３】
2007080375.tif 000005
【００２３】
ユークリッド距離は主にカラー画像やグレースケール画像などのｋビット、Ｗ個のデータの比較を必要とする画像データ処理などに用いられる。ユークリッド距離の計算を実現するためには、重み付けされた検索データ（ＳＷ）と参照データ（ＲＥＦi）の比較を行う回路、すなわちＷ個のユニットそれぞれの２つのｋビットデータの差の絶対値（｜ＳＷj−ＲＥＦij｜）を生成する回路と、この絶対差の２乗を計算する回路が必要となる。
【００２４】
図２は、連想メモリ装置内に構築される、行ｉに対するユークリッド距離計算回路の構成を示すブロック図（Ｗユニット分）である。図２において、ＵＳi1〜ＵＳiWはそれぞれ非反転信号ＳＷおよび反転信号〜ＳＷ（〜は反転を意味する。以下同様）のｋビットバイナリコードデータによる検索データユニットを取り込み、予め保存されている参照データユニットと共にビット単位で保存するユニット保存回路、ＵＣi1〜ＵＣiWはそれぞれｋビット減算器および絶対値計算回路を備え、ユニット保存回路ＵＳi1〜ＵＳiWから検索データＳＷと参照データＲＥＦiを受け取り、両者の差の絶対値を計算するユニット比較回路である。各ユニット比較回路ＵＣi1〜ＵＣiWで計算された検索データＳＷと参照データＲＥＦiの差の絶対値のデータは、各ビットの出力ＯＵＴ＝｛０，１｝のディジタル値として、ワード重み比較回路ＷＣiへ送られ、ワード重み比較回路ＷＣiにおいて、全ビットのユークリッド距離の２乗（絶対差の２乗）の総和を計算する。
【００２５】
ワード重み比較回路ＷＣiには、ユニット比較回路ＵＣi1〜ＵＣiWの各々に対して電流変換回路１０およびアナログ２乗回路２０が設けられている。
【００２６】
各ユニット比較回路ＵＣi1〜ＵＣiWから出力されるディジタル信号ＯＵＴ1〜ＯＵＴkは、対応する電流変換回路１０でアナログ電流に変換される。各電流変換回路１０は、対応するユニット比較回路から出力されるディジタル信号ＯＵＴ1〜ＯＵＴk（ディジタルの距離）をアナログ電流に変換するために、それぞれのディジタル信号をゲートに受けるｋ個のＰＭＯＳ（電流変換トランジスタ）が用いられている。ここでは各ビットの出力値ＯＵＴ1，ＯＵＴ2，…，ＯＵＴkを、それぞれビットの位置に応じて、最下位ビットの出力ＯＵＴ1の電流値の２k-1倍になるように調整し重み付けが行われている。調整方法としては、各ビットの出力ＯＵＴkに接続するトランジスタのゲート幅Ｗkを整数（２k-1×Ｗ0）倍（Ｗ0は基準となるトランジスタ幅を示す）して、アナログ２乗回路２０に接続しているトランジスタに流れる電流値を制御することで各ビットの重み付けを行う。
【００２７】
各電流変換回路１０からの出力電流Ｉiは、対応するアナログ２乗回路２０により２乗される。アナログ２乗回路２０の回路構成例を図３に示す。各アナログ２乗回路２０から出力される電流（絶対差の２乗に応じた電流）Ｉoはマッチラインに流れ、これによって各グループの検索データＳＷiと参照データＲＥＦijのユークリッド距離の２乗に対応した電流が流れ、全体の検索データＳＷと参照データＲＥＦiのユークリッド距離ＤEuclid, iの２乗に相当する電流値Ｉが得られる。この電流値Ｉは電圧値に変換されてＷＬＡ回路２００、ＷＴＡ回路３００に送られ、最もユークリッド距離が最小となる行の信号が増幅され、距離が最小の行から"１"が出力される。
【００２８】
なお、図２に示したユニット保存回路（ＵＳ）、ユニット比較回路（ＵＣ）については公知の回路を用いて実現可能であり、たとえば特許文献２に開示されているものを用いて実現することができる。
［最小ユークリッド距離検索連想メモリの性能評価］
本実施形態に基づく最小ユークリッド距離検索連想メモリの性能をＨＳＰＩＣＥによってシミュレーションで確認した。テクノロジは0.35μｍ ＣＭＯＳで１６個の5-bitバイナリ（図２におけるＷ＝１６、ｋ＝５）と１２８個の参照データ（図１におけるＲ＝１２８）を用いた。図３に示したアナログ２乗回路２０のBasic Squarer部についてのシミュレーション結果を図４に、最小ユークリッド距離の参照データを検索するための時間（Winner 検索時間）の結果を図５に、平均消費電力の結果を図６にそれぞれ示す。このように、本実施形態に基づく最小ユークリッド距離検索連想メモリは、ウィナーを参照データとウィナー距離の広い範囲において見つけることができる。
［本実施形態の変形例］
なお、図２に示したユークリッド距離計算回路の代わりに図７に示すユークリッド距離計算回路を用いることも可能である。図７に示すユークリッド距離計算回路のワード重み比較回路ＷＣiには、ユニット比較回路ＵＣi1〜ＵＣiWの各々に対してディジタル２乗回路３０および電流変換回路４０が設けられている。各ユニット比較回路ＵＣi1〜ＵＣiWから出力されるディジタル信号（ｋビット）ＯＵＴ1〜ＯＵＴkは、対応するディジタル２乗回路により２乗される。ディジタル２乗回路３０からの出力（２ｋビット、ｋ＞１）ＯＵＴ1〜ＯＵＴ2kは、対応する電流変換回路４０でアナログ電流に変換される。各電流変換回路４０は、対応するディジタル２乗回路３０から出力されるディジタル信号ＯＵＴ1〜ＯＵＴ2kをアナログ電流に変換するために、それぞれのディジタル信号をゲートに受ける２ｋ個のＰＭＯＳ（電流変換トランジスタ）が用いられている。ここでは各ビットの出力値ＯＵＴ1，ＯＵＴ2，…，ＯＵＴ2kを、それぞれビットの位置に応じて、最下位ビットの出力ＯＵＴ1の電流値の２2kー1倍になるように調整し重み付けが行われている。調整方法としては、各ビットの出力ＯＵＴ2k（ｋ＞１）に接続するトランジスタのゲート幅Ｗ2kを整数（２2kー1×Ｗ0）倍（Ｗ0は基準となるトランジスタ幅を示す）して、電流変換回路４０内のトランジスタに流れる電流値を制御することで各ビットの重み付けを行う。各電流変換回路４０から出力される電流（絶対差の２乗に応じた電流）はマッチラインに流れ、これによって各グループの検索データＳＷiと参照データＲＥＦijのユークリッド距離の２乗に対応した電流が流れ、全体の検索データＳＷと参照データＲＥＦiのユークリッド距離ＤEuclid, iの２乗に相当する電流値Ｉが得られる。
【００２９】
また、本実施形態において示した回路（図２、３、７）の論理は一例であり、論理回路を正または負論理に反転させることも可能である。例えば、メモリ領域のＮ−ＭＯＳをＰ−ＭＯＳ、電流変換回路１０，４０のＰ−ＭＯＳをＮ−ＭＯＳに変更したりしても、その作用効果に変わりはない。
【産業上の利用可能性】
【００３０】
本発明に係る連想メモリ装置は、人工知能システム、データバンクシステム、インターネットルータ、モバイル端末（例えば、モバイルテレビ電話）、コードブックベースデータ圧縮、および、対象認識などの圧縮、認識処理技術全般に利用することができる。
【図面の簡単な説明】
【００３１】
【図１】本発明に係る実施形態として、ユークリッド距離計算回路を用いる全並列型連想メモリ装置のアーキテクチャを示すブロック図。
【図２】図１に示すメモリ内のユークリッド距離計算回路の１行分の構成を示すブロック図。
【図３】図２に示すアナログ２乗回路の内部構成を示す回路図。
【図４】図３に示したアナログ２乗回路２０のBasic Squarer部についてのシミュレーション結果を示す図。
【図５】Winner 検索時間のシミュレーション結果を示す図。
【図６】平均消費電力のシミュレーション結果を示す図。
【図７】図１に示すメモリ内のユークリッド距離計算回路の１行分の構成の変形例を示すブロック図。
【符号の説明】
【００３２】
１００  メモリ領域
２００  ウィナー・ラインナップ増幅回路（ＷＬＡ：Winner Line-Up Amplifier）
３００  全ウィナー取得回路（ＷＴＡ：Winner Take All Circuit）
１１０  行デコーダおよびＲ／Ｗ回路（Column Decoder and Read/Write (k x W Column)）
１２０  列デコーダ（Row Decoder (R Rows)）
１３０  検索データ保存回路（Search Data (k bit x W)）
ＵＳ  ユニット保存回路（Unit Storage）
ＵＣ  ユニット比較回路（Unit Comparison）
ＷＣ  ワード重み比較回路（Word Comparison）
１０  電流変換回路
２０  アナログ２乗回路
３０  ディジタル２乗回路
４０  電流変換回路
【図１】
2007080375.tif 000006
【図２】
2007080375.tif 000007
【図４】
2007080375.tif 000008
【図５】
2007080375.tif 000009
【図６】
2007080375.tif 000010
【図７】
2007080375.tif 000011
【図３】
2007080375.tif 000012