(57)【要約】【課題】  マンハッタン距離計算回路を小面積で実現し、低消費電力で小面積・高速な最小マンハッタン距離検索連想メモリ装置を提供する。【解決手段】  連想メモリ用に差の絶対値計算を行う回路を実現した。この回路は、加算回路とビット反転回路の２つから構成され、トランジスタ数が従来の１／３程度の極めて少ないという利点を有する。そこで、この差の絶対値計算回路をユニット比較回路ＵＣとして全並列型連想メモリに組み込み、Ｗ個の差の絶対値計算回路の出力を全て重み比較回路ＷＣに入力し処理する。これにより、検索データと参照データのマンハッタン距離の計算を実現する。マンハッタン距離計算回路が小面積で実現されたため、連想メモリ装置も、低消費電力かつ小面積で実現可能である。【選択図】      図７
2005209317.tif 000002
【特許請求の範囲】
【請求項１】
検索データについて複数の参照データと並列に差の絶対値計算に基づくマンハッタン距離を計算する距離計算回路と、前記マンハッタン距離の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、
前記検索データ及び参照データがそれぞれｋビット（ｋ＞１）単位でユニット化されている場合に、
前記距離計算回路は、前記参照データをユニット単位で保存するためのＷ列Ｒ行のユニット保存回路、ユニット毎に参照データと検索データの差の絶対値を求めるマンハッタン距離計算を行うＷ列Ｒ行のユニット比較回路、行毎に前記Ｗ列のユニット比較回路で計算されたマンハッタン距離に相当する電流または電圧信号を生成するＲ行のワード重み比較回路を備え、
前記ユニット比較回路は、
前記マンハッタン距離計算が、それぞれｋビット（ｋ＞１）単位でユニット化された参照データＲＥＦと検索データＳＷとの不一致の度合いＤを、差の絶対値計算Ｄ＝｜ＳＷ−ＲＥＦ｜で計算する方式であるとき、
前記参照データＲＥＦと検索データＳＷの大小を比較し、その比較結果がＳＷ＞ＲＥＦのときは（ＳＷ＋（〜ＲＥＦ））＋１（〜は反転（１の補数）を意味する。以下同様）を計算し、ＳＷ＜＝ＲＥＦのときは〜（ＳＷ＋（〜ＲＥＦ））を計算することを特徴とする最小マンハッタン距離検索連想メモリ装置。
【請求項２】
前記ユニット比較回路は、
前記差の絶対値計算で使用する減算処理を加算処理で表現してＳＷ＋（〜ＲＥＦ）を計算する加算回路と、
前記加算回路の計算結果について、ＭＳＢ（最上位ビット）の桁上げの有無を判断する桁上げ判断回路と、
前記桁上げが「無し」ならば前記加算回路の計算結果を反転出力し、「有り」ならば前記加算回路の計算結果に１を加算して出力する出力処理回路とを具備したことを特徴とする請求項１記載の最小マンハッタン距離検索連想メモリ装置。
【請求項３】
前記加算回路は、前記検索データの各ビットを非反転信号と反転信号の双対信号で取り込んで前記参照データのビット出力との排他的論理和を演算する第１の演算回路と、前記第１の演算回路の出力データと下位ビットからの桁上げデータとの排他的論理和を演算する第２の演算回路とを備え、
前記桁上げ判断回路は、前記第１の演算回路の出力データに基づいて上記検索データのビットデータと下位ビットからの桁上げデータのうちの一方を選択して桁上げデータを生成する選択回路を備え、
前記出力処理回路は、前記桁上げ判断回路で最上位ビットの桁上げがないと判断された場合に前記第２の演算回路それぞれのビット出力を反転する反転回路と、前記桁上げ判断回路で最上位ビットの桁上げがあると判断された場合に前記第２の演算回路それぞれのビット出力の総和に１を加算する加算回路とを備えることを特徴とする請求項２記載の最小マンハッタン距離検索連想メモリ装置。
【請求項４】
前記加算回路は、最下位ビットについては前記第１の演算回路の出力を直接出力することを特徴とする請求項３記載の最小マンハッタン距離検索連想メモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラー、グレースケールの画像圧縮、画像認識等の情報処理装置に用いられ、全並列処理による最小マンハッタン距離検索機能を有する連想メモリ装置に関する。
【背景技術】
【０００２】
近年、情報処理技術、特に画像圧縮・画像認識の分野においては、最小距離検索機能を持つ連想メモリ装置が注目されている。この連想メモリ装置は、入力されたデータ列（検索データ）に対して連想メモリ内にある複数の参照データ中から最も類似した（距離の近い）データを検索する機能を持つ機能メモリの代表的なものの一つであり、その優れた検索機能により、先に述べた画像圧縮・画像認識などのパターンマッチング機能を有するアプリケーションにおいて、その性能を飛躍的に向上できるものとして期待されている。
【０００３】
ここで、距離とは、検索データと参照データとを比較したときの不一致の度合いを意味しており、主にハミング距離とマンハッタン距離があることが知られている。検索データをＳＷ ＝｛ＳＷ1 ，ＳＷ2 ，…，ＳＷW ｝、メモリのｉ行に格納されている参照データをＲＥＦi ＝｛ＲＥＦi1，ＲＥＦi2，…，ＲＥＦiW ｝とすると、ｉ行目の参照データと検索データの間のハミング距離は、  
【数１】
2005209317.tif 000003
【０００４】
と表される。マンハッタン距離は、  
【数２】
2005209317.tif 000004
【０００５】
となる。
【０００６】
ハミング距離ＤHamm は主にデータ列や音声、文字などの認識に用いられ、マンハッタン距離ＤManh は主にカラーやグレースケールの画像圧縮・画像認識に用いられる。これまでに開発されている全並列型連想メモリでは、ハミング距離検索用の距離計算回路が実現されている（非特許文献１参照）が、カラーやグレースケールの画像圧縮・画像認識などに必要なマンハッタン距離の検索機能を連想メモリのメモリ領域に直接実現したものはない。
【０００７】
一方、ハミング距離検索用の連想メモリを用いて、マンハッタン距離をエンコード（符号化）する方式が提案されている（非特許文献２参照）。しかしながら、この方式では、各パターンのビット数が３ビット以上になると急激に回路面積が大きくなり、それに伴って消費電力も増大するという問題点がある。また、マンハッタン距離計算回路を実現するためには、検索データと参照データの差の絶対値を計算する回路を実現すればよいが、従来から知られている減算器（加算器）や絶対値計算回路をそのまま用いた場合には、回路規模（トランジスタ数）が大きくなるという欠点がある。
【非特許文献１】H．J．Mattausch et al., “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 et al．， “Fully-parallel pattern-matching engine with dynamic adaptability to Hamming or Manhattan distance”, 2002 Symposium on VLSI Circuit Dig. of Tech. Papers, pp.252-255，2002．
【非特許文献３】H．J．Mattausch et al．， “An architechture for compact associative memories with deca-ns nearest-match capability up to large distance”, ISSCC Dig. of Tech. Papers, pp.170-171.
【特許文献１】特開２００２−２８８９８５号
【特許文献２】特願２００２−１５９４３６号
【特許文献３】特願２００２−１６５７５９号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
以上述べたように、従来の連想メモリ装置では、データ列や音声、文字などの認識に用いられるハミング距離検索機能を搭載した、低消費電力で小面積のものが実現されているが、カラーやグレースケールの画像圧縮・画像認識等に必要なマンハッタン距離の検索機能をメモリ領域内部に搭載したものは未だ実現されていない。
【０００９】
本発明は、上記の状況に鑑みてなされたもので、全並列処理によってカラーやグレースケールの画像圧縮・画像認識などに必要な最小マンハッタン距離検索を高速に、低消費電力でかつ小面積な回路で実現可能な最小マンハッタン距離検索連想メモリ装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために本発明に係る連想メモリ装置は、以下のように構成される。
【００１１】
（１）検索データについて複数の参照データと並列に差の絶対値計算に基づくマンハッタン距離を計算する距離計算回路と、前記マンハッタン距離の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、  
前記検索データ及び参照データがそれぞれｋビット（ｋ＞１）単位でユニット化されている場合に、  
前記距離計算回路は、前記参照データをユニット単位で保存するためのＷ列Ｒ行のユニット保存回路、ユニット毎に参照データと検索データの差の絶対値を求めるマンハッタン距離計算を行うＷ列Ｒ行のユニット比較回路、行毎に前記Ｗ列のユニット比較回路で計算されたマンハッタン距離に相当する電流または電圧信号を生成するＲ行のワード重み比較回路を備え、  
前記ユニット比較回路は、  
前記マンハッタン距離計算が、それぞれｋビット（ｋ＞１）単位でユニット化された参照データＲＥＦと検索データＳＷとの不一致の度合いＤを、差の絶対値計算Ｄ＝｜ＳＷ−ＲＥＦ｜で計算する方式であるとき、  
前記参照データＲＥＦと検索データＳＷの大小を比較し、その比較結果がＳＷ＞ＲＥＦのときは（ＳＷ＋（〜ＲＥＦ））＋１（〜は反転（１の補数）を意味する。以下、同様）を計算し、ＳＷ＜＝ＲＥＦのときは〜（ＳＷ＋（〜ＲＥＦ））を計算することを特徴とする。
【００１２】
（２）（１）の構成において、前記ユニット比較回路は、  
前記差の絶対値計算で使用する減算処理を加算処理で表現してＳＷ＋（〜ＲＥＦ）を計算する加算回路と、  
前記加算回路の計算結果について、ＭＳＢ（最上位ビット）の桁上げの有無を判断する桁上げ判断回路と、  
前記桁上げが「無し」ならば前記加算回路の計算結果を反転出力し、「有り」ならば前記加算回路の計算結果に１を加算して出力する出力処理回路とを具備したことを特徴とする。
【００１３】
（３）（２）の構成において、  
前記加算回路は、前記検索データの各ビットを非反転信号と反転信号の双対信号で取り込んで前記参照データのビット出力との排他的論理和を演算する第１の演算回路と、前記第１の演算回路の出力データと下位ビットからの桁上げデータとの排他的論理和を演算する第２の演算回路とを備え、  
前記桁上げ判断回路は、前記第１の演算回路の出力データに基づいて上記検索データのビットデータと下位ビットからの桁上げデータのうちの一方を選択して桁上げデータを生成する選択回路を備え、  
前記出力処理回路は、前記桁上げ判断回路で最上位ビットの桁上げがないと判断された場合に前記第２の演算回路それぞれのビット出力を反転する反転回路と、前記桁上げ判断回路で最上位ビットの桁上げがあると判断された場合に前記第２の演算回路それぞれのビット出力の総和に１を加算する加算回路とを備えることを特徴とする。
【００１４】
（４）（３）の構成において、前記加算回路は、最下位ビットについては前記第１の演算回路の出力を直接出力することを特徴とする。すなわち、最下位ビットについては、下からの桁上げがないため、第２の演算回路は省略することができる。
【発明の効果】
【００１５】
本発明によれば、マンハッタン距離計算における差の絶対値計算を２の補数に基づき全て加算処理で実現し、ユニット保存回路に存在する検索データのビットラインの双対信号（非反転信号及び反転信号）を用い、最下位ビットの桁上げ信号により出力信号を反転するか、出力の総和に１を加えるかを判断することにより、回路構成を削減するようにしているので、回路規模の縮小及び計算処理の高速化を実現することができる。この結果、連想メモリ装置への適用において、低消費電力で小面積なチップ構成で最小マンハッタン距離検索を実現することができる。
【００１６】
このように、本発明では、全並列連想メモリベースシステムにおいて、カラーやグレースケールの画像圧縮・画像認識などに必要なマンハッタン距離計算回路を開発し、低消費電力で小面積な最小マンハッタン距離検索連想メモリ装置を実現する。特にこの回路構成は、パターンマッチングアプリケーション（例えば、ネットワークルータ、コードブックベースデータ圧縮、及び、対象認識）に対して従来のＣＭＯＳ技術を用いて高効率な全並列連想メモリ装置のチップ化を可能にする。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照して、本発明を実施するための最良な形態を詳細に説明する。
【００１８】
［全並列型連想メモリアーキテクチャ］
図１は、本発明に係るマンハッタン距離計算回路を使用する全並列型連想メモリ装置のアーキテクチャを示すブロック図である（非特許文献１または特許文献１参照）。メモリコア部分は、メモリ領域（左部分）１００、ウィナー・ラインナップ増幅回路（以下、ＷＬＡ回路（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：ＷＣ）により構成されている。
【００２０】
ワード重み比較回路ＷＣで生成された信号Ｃ（Comparison Signal）はＷＬＡ回路２００に入り、ＷＬＡ回路２００がこの信号Ｃを回路自身のバランスにより制御し、最初の段階で各行の電圧の差を最も大きく増幅する。ＷＬＡ回路２００とＷＴＡ回路３００は、行数Ｒに対する面積増加の割合が行数Ｒに対して線形のＯ(R)になるという特徴がある。
【００２１】
ＷＴＡ回路３００はＷＬＡ回路２００により増幅された各行の電圧出力ＬＡの差を更に増幅する機能を持つ。ＷＴＡ回路３００の出力Ｍにおいては、winner （ウィナー）行が“１”、その他のloser （ルーザ）行が“０”のディジタル信号となる。ＷＬＡ回路２００は、フィードバック信号Ｆ（Feedback Signal）をワード重み比較回路ＷＣに返す際に、当該ＷＬＡ回路２００に内蔵された電圧フォロワ（Voltage Follower）回路を用いることにより、フィードバックを高速化している。
【００２２】
［マンハッタン距離計算回路］
本発明の連想メモリ装置に用いられるマンハッタン距離計算回路は、図１に示すように、取り扱うデータを符号化したｋビット（ｋ＞１）相当のユニットをＷ個並べたものとなる。連想メモリ装置の入力となる検索データと連想メモリ装置内に格納されている参照データ（ｉ行）をそれぞれＳＷ、ＲＥＦi とおくとき、ＳＷとＲＥＦi の間のマンハッタン距離は次式のように表される。
【数３】
2005209317.tif 000005
【００２３】
マンハッタン距離は主にカラー画像やグレースケール画像などのｋビット、Ｗ個のデータの比較を必要とする画像データ処理などに用いられる。マンハッタン距離の計算を実現するためには、重み付けされた検索データ（ＳＷ）と参照データ（ＲＥＦi ）の比較を行う回路、すなわちＷ個のユニットそれぞれの２つのｋビットデータの差の絶対値を生成する回路（差の絶対値計算回路｜ＳＷi −ＲＥＦij ｜）が必要となる。
【００２４】
図２は連想メモリ装置内に構築される、行ｉに対するマンハッタン距離計算回路の構成を示すブロック図（Ｗユニット分）である。図２において、ＵＳi1〜ＵＳiWはそれぞれ非反転信号ＳＷ及び反転信号〜ＳＷ（〜は反転を意味する。以下同様）のｋビットバイナリコードデータによる検索データユニットを取り込み、予め保存されている参照データユニットと共にビット単位で保存するユニット保存回路、ＵＣi1〜ＵＣiWはそれぞれｋビット減算器（k-Bit Subtractor）１１及び絶対値計算回路（Absolute Value）１２を備え、ユニット保存回路ＵＳi1〜ＵＳiWから検索データＳＷと参照データＲＥＦを受け取り、両者の差の絶対値を計算するユニット比較回路である。各ユニット比較回路ＵＣi1〜ＵＣiWで計算された検索データＳＷと参照データＲＥＦの差の絶対値のデータは、各ビットの出力ＯＵＴ＝｛０,１｝のディジタル値として、ワード重み比較回路ＷＣi へ送られ、ワード重み比較回路ＷＣi において、全ビットのマンハッタン距離の総和を計算する。
【００２５】
図３は、図２に示す１グループ（図３では第ｊグループ）を取り出し、ワード重み比較回路ＷＣi において、各ビットの重みを考慮して、マンハッタン距離計算結果を電流値に変換する回路の例を示している。この例では、各ビットの出力値ＯＵＴ1 ，ＯＵＴ2 ，…，ＯＵＴk を、それぞれビットの位置に応じて、最下位ビットの出力ＯＵＴ1 の電流値の２k-1 倍になるように調整し重み付けを行っている。調整方法としては、各ビットの出力ＯＵＴk に接続するトランジスタのゲート幅Ｗk を整数（２k-1×Ｗ0 ）倍（Ｗ0 は基準となるトランジスタ幅を示す）して、マッチライン（Match Line）に接続しているトランジスタに流れる電流値を制御することで各ビットの重み付けを行う。全ユニット比較回路ＵＣi1〜ＵＣiWから出力される差の絶対値に応じた電流はマッチラインに流れ、これによって各グループの検索データＳＷi と参照データＲＥＦijのマンハッタン距離に対応した電流が流れ、全体の検索データＳＷと参照データＲＥＦのマンハッタン距離Ｄmanhに相当する電流値ｉが得られる。この電流値ｉは電圧値に変換されてＷＬＡ回路２００、ＷＴＡ回路３００に送られ、最もマンハッタン距離が最小となる行の信号が増幅され、距離が最小の行から“１”が出力される。
【００２６】
一般に、図２に示すｋビットの減算器１１と絶対値計算回路１２は、従来から知られている加算器（Adder）、セレクタ（Selector）、反転器（Inverter）を用いて構成することが可能である。例えば、図４（ａ）に示す減算及び絶対値による計算式に対し、加算器、セレクタ及び反転器を用いたユニット比較回路ＵＣの全体の構成は図４（ｂ）に示すようになり、ｋビットそれぞれの回路構成は図４（ｃ）に示すようになる。しかし、この場合には、セレクタＳＥＬ（Selector）が図５（ａ）に示すように６トランジスタ程度必要となり、半加算器ＨＡ（Half Adder）が図５（ｂ）に示すように１２トランジスタ程度必要となり、全加算器ＦＡ（Full Adder）が図５（ｃ）に示すように３０トランジスタ程度必要となる。このため、差の絶対値計算回路ＵＣ全体のトランジスタ数は、  
３０×（ｋ−１）＋１２×（ｋ＋１）＋２×ｋ＋６×ｋ
＝５０ｋ−１８（トランジスタ数）                          （４）
となり、トランジスタ数が多く、また、符号ビットの計算が必要となる。
【００２７】
そこで本発明では、連想メモリ用に、トランジスタ数が少ない差の絶対値計算（マンハッタン距離計算）を行う回路を提供する。そして、この差の絶対値計算回路をユニット比較回路ＵＣとして全並列型連想メモリに組み込み、Ｗ個の差の絶対値計算回路の出力を全て重み比較回路ＷＣに入力し処理することで、検索データと参照データのマンハッタン距離の計算を実現する。
【００２８】
本発明の差の絶対値計算回路は、基本的に加算回路とビット反転回路の２つから構成される。図６は本発明における差の絶対値の計算方式を示したものである。一般に２つのデータＳＷ、ＲＥＦの差の絶対値Ｙを求めるためには、２の補数を用いることによって減算を加算で処理することができる。図６（ａ）に示すように、ＳＷ＞ＲＥＦとＳＷ≦ＲＥＦの２つのケースについて計算すると、最終的にＳＷ＋〜ＲＥＦ（〜は反転（１の補数）を意味する。以下同様）の計算結果の最上位ビット（ＭＳＢ）の桁上げ（Carry）が０の場合には、ＳＷ＋〜ＲＥＦの計算結果を反転すればよく、１の場合には、ＳＷ＋ＲＥＦの計算結果に１を足せばよい。
【００２９】
表１に、差の絶対値計算回路の中で用いる減算回路（加算回路）の真理値表を示す。  
【表１】
2005209317.tif 000006
【００３０】
一方、連想メモリ装置において、ユニット保存回路ＵＳのＳＲＡＭセルは、ビットラインの双対信号（非反転信号ＳＷ、反転信号〜ＳＷ）によって動作する。そこで、本発明では、図６の計算方式と表１に基づいて、ユニット保存回路ＵＳのＳＲＡＭセルに存在するビットラインの双対信号（非反転信号ＳＷ、反転信号〜ＳＷ）を用い、最上位ビットの桁上げ信号により出力信号を反転するか、出力の総和に１を加えるかを判断することにより回路構成を削減するようにした。
【００３１】
図７は上記概要に基づく本発明による１つのグループのマンハッタン距離計算回路の構成を示す回路図である。図７において、ユニット保存回路ＵＳijは、ＳＲＡＭセルＳ1 ，Ｓ2 ，…，Ｓkに、１ユニット分のｋビット参照データの各ビットデータＲＥＦ1 ，ＲＥＦ2 ，…，ＲＥＦk を保存する。各セル出力データはユニット比較回路ＵＣijに送られる。
【００３２】
ユニット比較回路ＵＣijにおいて、各セル出力データＲＥＦ1 ，ＲＥＦ2 ，…，ＲＥＦkは、排他的論理和を演算するＸＯＲ回路Ａ1 ，Ａ2 ，…，Ａkに送られ、ｋビット検索データの各ビットデータＳＷi,j1，ＳＷi,j2，…，ＳＷi,jk（非反転信号及び反転信号）の対応ビットデータに応じて反転／非反転出力される。これにより、検索データと参照データとのビット間の減算が加算処理によって実現される。
【００３３】
各ビットにおける計算回路は、ユニット保存回路ＵＳijの対応するビット出力と下位ビットからの桁上げデータＣ1 ，Ｃ2 ，…，Ｃk-1との排他的論理和による加算処理（Addition）を行うＸＯＲ回路Ｂ2 ，…，Ｂk、上記ＸＯＲ回路Ａ1 ，Ａ2 ，…，Ａkの演算結果に応じて上記検索データの反転ビット入力と下位ビットからの桁上げデータのいずれかを選択出力することで上位ビットへの桁上げデータＣk （＝Ｃmax ）を生成するセレクタ構成の桁上げ生成回路（Carry Generation）Ｄ1 ，Ｄ2 ，…，Ｄk、及び、最上位ビットの桁上げデータが０のときに各ビットの加算処理結果を反転（Inversion）するためのＸＯＲ回路Ｅ1 ，Ｅ2 ，…，Ｅkの４つの部分から構成される。最下位ビット（ＬＳＢ）のみは、下の桁からの桁上げがないため、加算出力用（Addition）のＸＯＲ回路Ｂが不要である。また、最上位ビットの桁上げ生成回路Ｄk の桁上げ出力Ｃmax が１のときには、計算結果に１を加えるため信号がワード重み比較回路ＷＣi のマッチラインに加えられる。これにより、＋１による桁上げ処理を簡単な回路構成で実現することができる。また、以上の構成により、図６で説明した２の補数の加算処理による差の絶対値計算を実現することができる。
【００３４】
本発明のマンハッタン距離計算回路のトランジスタ数は、メモリ内の反転信号を効率よく利用することにより回路規模を縮小することができる。また、ＳＷ＞ＲＥＦのときの１加算処理を簡単な構造で実現することができる。例えば、図７の回路構成では、  
１６×（ｋ−１）＋１２＋２＝１６ｋ−２（トランジスタ数）  （５）  
となり、従来の方法によるトランジスタ数５０ｋ−１８に比べて約１／３程度の大幅な削減ができる。
【００３５】
表２はハミング距離方式でマンハッタン距離を実現した場合（非特許文献２参照）と本発明による直接マンハッタン距離を実現した場合の回路規模の比較を表したものである。
【表２】
2005209317.tif 000007
【００３６】
表２において、（ａ）はハミング距離によるマンハッタン距離の符号化の例を示し、（ｂ）は距離指標と回路規模との関係を示している。特に（ｂ）では、マンハッタン距離検索を直接回路により実現する方法（方式１）とハミング距離による符号化により実現する方法（方式２）による場合において、それぞれ必要となるトランジスタ数とビット数ｋとの関係を示している。
【００３７】
このマッピング（符号化）のコストはビット数ｋに対して２k −１となる。そのため、遅延時間には削減が影響を受けないが、面積の利点の大きさに関してトレードオフが生じる。ビット当たりの減算と絶対値計算回路の現実的なトランジスタ数は１６であるので、マッピングにより連想メモリコアのメモリ領域で削減されるトランジスタ数は条件式（１）により得ることができる。  
９（２k −１）＝トランジスタ数(方式２)  
＜２４ｋ＋２k トランジスタ数(方式２)      （６）
（６）式をｋに対して解くことにより、マンハッタン距離検索をハミング距離連想メモリ上にマッピング（符号化）する場合には、ｋ≦３ビットの２進数までは、最小距離検索時間を増やすことなく、連想メモリコアの小面積化が可能となるが、ｋ＞３ビットの場合にはマンハッタン距離計算回路を連想メモリ内部に直接実現することにより大幅な回路面積の削減ができる。
【００３８】
［最小マンハッタン距離検索連想メモリＬＳＩの設計］
本発明に基づく５ビットの最小マンハッタン距離検索連想メモリを、３層配線０．３５μｍＣＭＯＳ技術を用いて設計し、チップ試作を行い、性能を評価した。図８に設計した１２８行８０列（ｋ＝５ビット×Ｗ＝１６ユニット）の連想メモリのレイアウトを示す。試作チップは全ての回路を７．４９平方ミリメートル（1.990mm×3.765mm）の面積で実現し、その内winner検索回路（ＷＬＡ回路、ＷＴＡ回路）が全体のわずか１３．６％（１．０２平方ミリメートル）で実現することができた。図９に試作した最小マンハッタン距離検索連想メモリの顕微鏡写真を示す。
【００３９】
設計・試作した最小マンハッタン距離検索連想メモリの性能を評価するために、ＨＳＰＩＣＥを用いた回路シミュレーションを行った。図１０にＨＳＰＩＣＥシミュレーションによる最小マンハッタン距離の参照データを検索するための時間（Winner 検索時間）の結果を示す。
【００４０】
図１０では、横軸は検索データ（Input）と最も近い参照データ（Winner）との距離（Winner-Input Distance (Bit)）を表し、縦軸は参照データの検索時間（Winner-Search Time (ns)）す。また、グラフ中のWinner-Loser Distance は、最も近い参照データ以外の参照データ（Loser）とWinnerとの距離を１、２、５、１０ビットと変化させた場合のWinner 検索時間を示している。このシミュレーションは、１２８個の参照データのうちのひとつをwinner、その他の１２７個を同一内容のloser と仮定して実行した。シミュレーションのパラメータとしてWinner-Loser 間距離を１、２、５、１０ビットという検索が難しいケースに設定した。このシミュレーション結果は、最大距離４９６（5-bit × 16 units）に対して、検索時間は２４０nsec 以下であった。
【００４１】
図１１に、試作したチップの測定結果を示す。測定結果よりWinner-Input Distance （参照データ・検索データ間距離）が最大２１９まで測定することができた。また、Winner 検索時間は１８０nsec 以下であった。実際の応用（例えば、コードブックを用いるベクトル量子化による画像圧縮）ではWinner-Input Distanceの距離差が５０ビット以下がほとんどであることを考慮すると、１８０nsec 以下の高速な検索が可能である。消費電力は最大２００mW＠５MHz であり、１参照パターン当たり約１．５６mW＠５MHz 程度と非常に低消費電力であった。表３に試作した最小マンハッタン距離検索連想メモリの性能一覧を示す。
【表３】
2005209317.tif 000008
【００４２】
尚、図７に示した回路の論理は一例であり、論理回路を正または負論理に反転させることも可能である。例えば、メモリ領域のＮ−ＭＯＳをＰ−ＭＯＳに変更したり、マッチラインのＰ−ＭＯＳをＮ−ＭＯＳに変更したりしても、その作用効果に変わりはない。
【産業上の利用可能性】
【００４３】
本発明に係る連想メモリ装置は、人工知能システム、データバンクシステム、インターネットルータ、モバイル端末（例えば、モバイルビデオ電話）、コードブックベースデータ圧縮、及び、対象認識などの圧縮、認識処理技術全般に利用することができる。
【図面の簡単な説明】
【００４４】
【図１】本発明に係る実施形態として、マンハッタン距離計算回路を用いる全並列型連想メモリ装置のアーキテクチャを示すブロック図。
【図２】図１に示すメモリ内のマンハッタン距離計算回路の１行分の構成を示すブロック図。
【図３】図２に示すマンハッタン距離計算回路の１ブロックの構成を示すブロック図。
【図４】加算器とセレクタを用いた従来型マンハッタン距離計算回路を示すブロック図。
【図５】加算器とセレクタを用いた従来型マンハッタン距離計算回路の各構成要素を示す図。
【図６】本発明に係る差の絶対値の計算方法を説明するための図。
【図７】本発明によるマンハッタン距離計算回路（ユニット比較回路）の構成を示すロジック回路図。
【図８】本発明の実施例として、０．３５μｍＣＭＯＳ技術により設計した最小マンハッタン距離検索連想メモリのレイアウトを示す図。
【図９】本発明の実施例として、０．３５μｍＣＭＯＳ技術により設計した最小マンハッタン距離検索連想メモリのチップ写真を示す図。
【図１０】本発明の実施例として、設計したテストチップのWinner 検索時間のシミュレーションによる評価を示す図。
【図１１】本発明の実施例として、設計したテストチップの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）、
１１…ｋビット減算器、
１２…絶対値計算回路。
【図１】
2005209317.tif 000009
【図２】
2005209317.tif 000010
【図３】
2005209317.tif 000011
【図４】
2005209317.tif 000012
【図５】
2005209317.tif 000013
【図６】
2005209317.tif 000014
【図７】
2005209317.tif 000015
【図８】
2005209317.tif 000016
【図９】
2005209317.tif 000017
【図１０】
2005209317.tif 000018
【図１１】
2005209317.tif 000019
【手続補正書】
【提出日】平成16年3月2日(2004.3.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
本発明のマンハッタン距離計算回路のトランジスタ数は、メモリ内の反転信号を効率よく利用することにより回路規模を縮小することができる。また、ＳＷ＞ＲＥＦのときの１加算処理を簡単な構造で実現することができる。例えば、図７の回路構成では、  
２０×（ｋ−１）＋１６＋２＝２０ｋ−２（トランジスタ数）  （５）  
となり、従来の方法によるトランジスタ数５０ｋ−１８に比べて約２／５程度の大幅な削減ができる。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
表２はハミング距離方式でマンハッタン距離を実現した場合（非特許文献２参照）と本発明による直接マンハッタン距離を実現した場合の回路規模の比較を表したものである。
【表２】
2005209317.tif 000020