TOP > 国内特許検索 > 連想メモリ > 明細書

明細書 :連想メモリ

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5916563号 (P5916563)
公開番号 特開2014-041676 (P2014-041676A)
登録日 平成28年4月15日(2016.4.15)
発行日 平成28年5月11日(2016.5.11)
公開日 平成26年3月6日(2014.3.6)
発明の名称または考案の名称 連想メモリ
国際特許分類 G11C  15/04        (2006.01)
FI G11C 15/04 631F
請求項の数または発明の数 9
全頁数 44
出願番号 特願2012-183975 (P2012-183975)
出願日 平成24年8月23日(2012.8.23)
審査請求日 平成27年4月30日(2015.4.30)
特許権者または実用新案権者 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
発明者または考案者 【氏名】マタウシュ ハンスユルゲン
【氏名】小出 哲士
【氏名】佐々木 静龍
【氏名】赤澤 智信
個別代理人の代理人 【識別番号】100104444、【弁理士】、【氏名又は名称】上羽 秀敏
【識別番号】100112715、【弁理士】、【氏名又は名称】松山 隆夫
【識別番号】100125704、【弁理士】、【氏名又は名称】坂根 剛
【識別番号】100120662、【弁理士】、【氏名又は名称】川上 桂子
審査官 【審査官】塚田 肇
参考文献・文献 特開2002-288985(JP,A)
国際公開第2004/077669(WO,A1)
調査した分野 G11C 15/04
特許請求の範囲 【請求項1】
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存回路と、
前記R個の参照データに対応して設けられ、各々がM×Wビットのビット長を有し、かつ、検索対象である検索データと前記参照データとの距離を表わすR個の距離信号を出力するR個の距離演算回路と、
前記R個の距離演算回路に対応して設けられ、各々が対応する距離演算回路から各々がMビットのビット長を有するW個の距離信号を受け、その受けたW個の距離信号の和に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントし、前記クロック数をカウントしたタイミングである一致タイミングを示すタイミング信号を出力するR個の距離/クロック数変換回路と、
前記R個の距離/クロック数変換回路から受けたR個のタイミング信号に基づいて、前記一致タイミングが早い順にk(kは1≦k<Rを満たす整数)個のタイミング信号を検出し、その検出したk個のタイミング信号を前記検索データと前記参照データとの類似度を示すマッチ信号として出力するWinner検出器とを備える連想メモリ。
【請求項2】
前記R個の距離/クロック数変換回路の各々は、各々がMビットのビット長を有するW個の距離信号に対応して設けられ、かつ、直列に接続されたW個のカウンタ一致検出回路を含み、
前記W個のカウンタ一致検出回路は、W=2である場合、
前記W個の距離信号を一列に配列したときの一方端の距離信号である1番目の距離信号に対応して設けられ、前記1番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けた1番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第1のクロック数をカウントし、前記第1のクロック数をカウントしたタイミングを示す第1の一致信号を出力する第1のカウンタ一致検出回路と、
前記一方端からW番目の距離信号に対応して設けられ、前記第1のカウンタ一致検出回路から前記第1の一致信号を受けると駆動されるとともに前記W番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第2のクロック数をカウントし、前記第2のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第2のカウンタ一致検出回路とを含み、
前記W個のカウンタ一致検出回路は、Wが3以上である場合、
前記第1のカウンタ一致検出回路と、
2番目の距離信号からW-1番目の距離信号までのW-2個の距離信号に対応して設けられ、各々が、前記第1のカウンタ一致検出回路またはw-1(wは2≦w≦W-1を満たす整数)番目の距離信号に対応して設けられたカウンタ一致検出回路から前記1番目または前記w番目の距離信号に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントしたタイミングを示す第2の一致信号を受けると駆動されるとともに前記w番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたw番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第3のクロック数をカウントし、前記第3のクロック数をカウントしたタイミングを示す第3の一致信号を出力するW-2個の第3のカウンタ一致検出回路と、
W番目の距離信号に対応して設けられ、W-1番目の距離信号に対応して設けられたカウンタ一致検出回路から前記第3の一致信号を受けると駆動されるとともに前記W番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第4のクロック数をカウントし、前記第4のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第4のカウンタ一致検出回路とを含む、請求項1に記載の連想メモリ。
【請求項3】
前記第1のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第1のカウンタと、
前記第1のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記1番目の距離信号を受け、前記受けたカウンタ値が前記1番目の距離信号に一致するときの前記第1のクロック数をカウントし、前記第1のクロック数が得られると、前記第1の一致信号を出力する第1の一致検出回路とを含み、
前記第2のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第2のカウンタと、
前記第2のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記W番目の距離信号を受け、前記第1のカウンタ一致検出回路から前記第1の一致信号を受けると駆動され、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第2のクロック数をカウントし、前記第2のクロック数が得られると、前記タイミング信号を前記Winner検出器へ出力する第2の一致検出回路とを含み、
前記W-2個の第3のカウンタ一致検出回路の各々は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第3のカウンタと、
前記第3のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記w番目の距離信号を受け、前記第2の一致信号を受けると駆動され、前記受けたカウンタ値が前記w番目の距離信号に一致するときの前記第3のクロック数をカウントし、前記第3のクロック数が得られると、前記第3の一致信号を出力する第3の一致検出回路とを含み、
前記第4のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第4のカウンタと、
前記第4のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記W番目の距離信号を受け、前記第3の一致信号を受けると駆動され、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第4のクロック数をカウントし、前記第4のクロック数が得られると、前記タイミング信号を前記Winner検出器へ出力する第4の一致検出回路とを含む、請求項2に記載の連想メモリ。
【請求項4】
前記Wは、2(iは2以上の整数)からなり、
前記R個の距離/クロック数変換回路の各々は、W/s(sはW以下である2に等しい。xは正の整数)個の距離信号に対応して設けられ、各々がMビットのビット長を有するW個の距離信号に基づいて、前記タイミング信号を出力するW/s個のカウンタ一致検出回路を含み、
前記W/s個のカウンタ一致検出回路は、各々が前記W/s個の距離信号からなるs組の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたs組の距離信号に含まれるW個の距離信号の和に一致するカウンタ値が得られるときの前記クロック数をカウントし、前記クロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する、請求項1に記載の連想メモリ。
【請求項5】
前記W/s個のカウンタ一致検出回路は、前記W/s個の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW/s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号の第1のクロック数をカウントし、前記第1のクロック数をカウントしたタイミングを示す第1の一致信号を出力する処理をs-1回繰り返し実行し、前記第1の一致信号を前記s-1回出力し、かつ、s回目に前記W/s個の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW/s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号の第2のクロック数をカウントし、前記第2のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する、請求項4に記載の連想メモリ。
【請求項6】
前記W/s個のカウンタ一致検出回路は、
前記W個の距離信号を一列に配列したときの一方端からp(pは1≦p<Wを満たす奇数)番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記p番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第3のクロック数をカウントし、前記第3のクロック数をカウントしたタイミングを示す第2の一致信号を出力する第1の一致処理をW/2回繰り返し実行する第1のカウンタ一致検出回路と、
前記一方端からq(qは1<q≦Wを満たす偶数)番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記q番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第4のクロック数をカウントし、前記第4のクロック数をカウントしたタイミングを示す第3の一致信号を出力する第2の一致処理を((W/2)-1)回繰り返し実行し、前記第2の一致信号を前記W/2回受け、かつ、W番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記W番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第5のクロック数をカウントし、前記第5のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第2のカウンタ一致検出回路とを含む、請求項4に記載の連想メモリ。
【請求項7】
前記R個の距離/クロック数変換回路の各々は、
前記第1のカウンタ一致検出回路から前記第2の一致信号を受けると、その受けた第2の一致信号を前記第2のカウンタ一致検出回路へ出力し、前記第2のカウンタ一致検出回路から前記第3の一致信号を受けると、その受けた第3の一致信号を前記第1のカウンタ一致検出回路へ出力するスイッチング制御回路を更に含み、
前記第1のカウンタ一致検出回路は、前記スイッチング制御回路から前記第3の一致信号を受ける毎に前記第1の一致処理を1回実行し、
前記第2のカウンタ一致検出回路は、前記スイッチング制御回路から前記第2の一致信号を受ける毎に前記第2の一致処理を1回実行するとともに、前記第2の一致信号を前記W/2回受けると、前記第5のクロック数をカウントし、前記タイミング信号を前記Winner検出器へ出力する、請求項6に記載の連想メモリ。
【請求項8】
前記第1のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第1の出力処理を前記W/2回繰り返し実行する第1のカウンタと、
前記第1のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記p番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたカウンタ値が前記p番目の距離信号に一致するときの前記第3のクロック数をカウントし、前記第2の一致信号を出力する第2の出力処理を前記W/2回繰り返し実行する第1の一致検出回路とを含み、
前記第2のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第3の出力処理を前記W/2回繰り返し実行する第2のカウンタと、
前記第2のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記q番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたカウンタ値が前記q番目の距離信号に一致するときの前記第4のクロック数をカウントし、前記第3の一致信号を出力する第2の出力処理を前記((W/2)-1)回繰り返し実行し、前記第2の一致信号を前記W/2回受けると、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第5のクロック数をカウントし、前記タイミング信号を前記Winner検出器へ出力する第2の一致検出回路とを含む、請求項6または請求項7に記載の連想メモリ。
【請求項9】
前記第1から第4のカウンタの各々は、Mビットのカウンタ値を昇順に出力するM個の分周器からなり、
前記Mビットのカウンタ値の最下位ビットから最上位ビットへ向かう方向において第m(mは1≦m≦Mを満たす整数)位のビット値を出力する分周器は、クロック信号を2m-1回に分周した信号を出力する、請求項3または請求項8に記載の連想メモリ。
発明の詳細な説明 【技術分野】
【0001】
この発明は、連想メモリに関するものである。
【背景技術】
【0002】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated circuit)上で実現することにより、将来、人工知能およびモバイル機器等の高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【0003】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【0004】
前者は、CAM(Contents Addressable Memory)と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュ等の実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ(Associative Memory)と呼ぶ。
【0005】
連想メモリを実現する手段として(1)ディジタル方式による実現方法(非特許文献1)、(2)アナログ方式による実現方法および(3)ディジタル・アナログ融合方式(非特許文献2)等が提案されている。
【先行技術文献】
【0006】

【非特許文献1】Y. Oike, et al., “A High-Speed and Low-Voltage Associative Co-Processor with Hamming Distance Ordering Using Word-Parallel and Hierarchical Search Architecture,” CICC, 2004.
【非特許文献2】M. A. Abedin, et al., “Nearest-euclidean-distance search associative memory with fully parallel mixed digital-analog match circuitry,” Proc. of SSDM2006, pp. 282-283, 2006.
【非特許文献3】Y. Oike et al., “A Word-Parallel Digital Associative Engine with Wide Search Range Based on Manhattan Distance,” CICC, 2004.
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかし、非特許文献1に記載の連想メモリは、検索データと参照データとのハミング距離を用いて類似検索を行うため、マンハッタン距離を用いて類似検索を行うことが困難であるという問題がある。また、非特許文献2に記載の連想メモリにおいては、検索データと参照データとの類似度を表す距離を電圧に変換するので、誤検索が生じるという問題がある。
【0008】
そこで、この発明は、かかる問題を解決するためになされたものであり、その目的は、マンハッタン距離を用いた場合にも、正確、かつ、高速に類似検索を行うことが可能な連想メモリを提供することである。
【課題を解決するための手段】
【0009】
この発明の実施の形態による連想メモリは、参照データ保存回路と、R個の距離演算回路と、R個の距離/クロック数変換回路と、Winner検出器とを備える。参照データ保存回路は、各々がM×Wビットのビット長を有するR個の参照データを保存する。R個の距離演算回路は、R個の参照データに対応して設けられ、各々がM×Wビットのビット長を有し、かつ、検索対象である検索データと参照データとの距離を表わすR個の距離信号を出力する。R個の距離/クロック数変換回路は、R個の距離演算回路に対応して設けられ、各々が対応する距離演算回路から各々がMビットのビット長を有するW個の距離信号を受け、その受けたW個の距離信号の和に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントし、そのクロック数をカウントしたタイミングである一致タイミングを示すタイミング信号を出力する。Winner検出器は、R個の距離/クロック数変換回路から受けたR個のタイミング信号に基づいて、一致タイミングが早い順にk個のタイミング信号を検出し、その検出したk個のタイミング信号を検索データと参照データとの類似度を示すマッチ信号として出力する。
【発明の効果】
【0010】
この発明の実施の形態による連想メモリにおいては、R個の距離/クロック数変換回路の各々は、対応する距離演算回路から受けたW個の距離信号の和に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントし、そのクロック数をカウントしたタイミングである一致タイミングを示すタイミング信号を出力する。即ち、R個の距離/クロック数変換回路の各々は、W個の距離信号の和をクロック信号のクロック数に変換し、その変換したクロック数が得られるタイミングを示すタイミング信号を出力する。その結果、W個の距離信号の和によって表わされる距離が小さければ、タイミング信号は、より早い一致タイミングを示し、W個の距離信号の和によって表わされる距離が大きければ、タイミング信号は、より遅い一致タイミングを示す。また、W個の距離信号の和に一致するカウンタ値が得られるときのクロック信号のクロック数は、W個の距離信号のそれぞれに一致するW個のカウンタ値が得られるときのクロック信号のW個のクロック数を加算した値からなるので、検索データと参照データとの距離をマンハッタン距離によって表わしたときの検索データと参照データとの距離信号に一致するカウンタ値が得られるときのクロック信号のクロック数になる。更に、2つのタイミング信号によって示される2つのタイミングは、クロック信号の少なくとも1周期以上の時間差を有する。更に、クロック信号の周波数を高くすることによって検索時間が短くなる。
【0011】
従って、この発明の実施の形態によれば、マンハッタン距離を用いた場合にも、正確、かつ、高速に類似検索を行うことができる。
【図面の簡単な説明】
【0012】
【図1】この発明の実施の形態による連想メモリの構成を示す概略ブロック図である。
【図2】図1に示す距離/クロック数変換回路の構成を示す概略図である。
【図3】図2に示すカウンタ一致検出回路の構成を示す概略図である。
【図4】図3に示すカウンタ一致検出回路の動作を説明するための図である。
【図5】図1に示す距離/クロック数変換回路の動作を説明するための図である。
【図6】図1に示すWinner検出器の動作を説明するための図である。
【図7】図3に示すカウンタの好ましい構成を示す概略図である。
【図8】図7に示すカウンタの動作を説明するための図である。
【図9】図1に示す距離/クロック数変換回路の別の構成を示す概略図である。
【図10】図1に示す距離/クロック数変換回路の更に別の構成を示す概略図である。
【図11】図9に示す距離/クロック数変換回路の具体的な構成を示す概略図である。
【図12】図11に示す距離/クロック数変換回路の動作を説明するための図である。
【図13】図9に示す距離/クロック数変換回路の別の具体的な構成を示す概略図である。
【図14】図13に示す距離/クロック数変換回路の動作を説明するための図である。
【図15】図10に示す距離/クロック数変換回路の具体的な構成を示す概略図である。
【図16】図15に示す距離/クロック数変換回路の動作を説明するための図である。
【図17】図10に示す距離/クロック数変換回路の更に別の具体的な構成を示す概略図である。
【図18】図17に示す距離/クロック数変換回路の動作を説明するための図である。
【図19】最短検索時間の比較を示す図である。
【図20】消費電力の比較を示す図である。
【発明を実施するための形態】
【0013】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。

【0014】
図1は、この発明の実施の形態による連想メモリの構成を示す概略ブロック図である。図1を参照して、この発明の実施の形態1による連想メモリ100は、メモリアレイ部10と、Winner検出器20とを備える。

【0015】
メモリアレイ部10は、メモリ部1と、行デコーダ2と、列デコーダ3と、読出/書込回路4と、検索データ保存回路5とを含む。

【0016】
メモリ部1は、参照データ保存回路(Storage Cell:SC)SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRWと、距離演算回路(Distance Processor:DP)DP11~DP1W,DP21~DP2W,・・・,DPR1~DPRWと、距離/クロック数変換回路DC~DCとを含む。なお、WおよびRの各々は、2以上の整数である。

【0017】
距離演算回路DP11~DP1Wは、それぞれ、参照データ保存回路SC11~SC1Wに対応して設けられる。また、距離演算回路DP21~DP2Wは、それぞれ、参照データ保存回路SC21~SC2Wに対応して設けられる。以下、同様にして、距離演算回路DPR1~DPRWは、それぞれ、参照データ保存回路SCR1~SCRWに対応して設けられる。

【0018】
距離/クロック数変換回路DCは、距離演算回路DP11~DP1Wに対応して設けられる。距離/クロック数変換回路DCは、距離演算回路DP21~DP2Wに対応して設けられる。以下、同様にして、距離/クロック数変換回路DCは、距離演算回路DPR1~DPRWに対応して設けられる。

【0019】
参照データ保存回路SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRWは、行デコーダ2、列デコーダ3および読出/書込回路4によって書き込まれた参照データを保存する。この場合、参照データ保存回路SC11~SC1Wは、M×W(Mは1以上の整数)ビットの参照データ1を保存し、参照データ保存回路SC21~SC2Wは、M×Wビットの参照データ2を保存し、以下、同様にして、参照データ保存回路SCR1~SCRWは、M×Wビットの参照データRを保存する。つまり、参照データ保存回路SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRWの各々は、参照データのMビットを保存する。

【0020】
距離演算回路DP11~DP1Wは、参照データ保存回路SC11~SC1Wに保存されたM×Wビットの参照データ1と、検索データ保存回路5に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。また、距離演算回路DP21~DP2Wは、参照データ保存回路SC21~SC2Wに保存されたM×Wビットの参照データ2と、検索データ保存回路5に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。以下、同様にして、距離演算回路DPR1~DPRWは、参照データ保存回路SCR1~SCRWに保存されたM×Wビットの参照データRと、検索データ保存回路5に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。そして、距離演算回路DP11~DP1W、距離演算回路DP21~DP2W、・・・、および距離演算回路DPR1~DPRWにおける参照データと検索データとの距離の演算は、並列に行なわれる。

【0021】
そして、距離演算回路DP11~DP1Wは、参照データ1と検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力し、距離演算回路DP21~DP2Wは、参照データ2と検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力し、以下、同様にして、距離演算回路DPR1~DPRWは、参照データRと検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力する。

【0022】
距離演算回路DP11~DP1Wの各々は、参照データ1と検索データとの距離を次式を用いて演算する。

【0023】
【数1】
JP0005916563B2_000002t.gif

【0024】
式(1)において、Drj(r=1~R,j=1~W)は、参照データと検索データとの距離であり、Inは、検索データであり、Rerjは、参照データである。そして、各データIn,Rerjの各々は、Mビットからなる。

【0025】
このように、距離演算回路DP11~DP1Wは、M×Wビットの参照データ1と、M×Wビットの検索データとの距離をMビットづつ演算し、各々がMビットのビット長を有するW個の距離信号D1jを距離/クロック数変換回路DCへ出力する。

【0026】
距離演算回路DP21~DP2W、・・・および距離演算回路DPR1~DPRWも、それぞれ、式(1)を用いて参照データ2~Rと検索データとの距離を演算する。そして、距離演算回路DP21~DP2W、・・・および距離演算回路DPR1~DPRWも、各々がMビットのビット長を有するW個の距離信号D2j~DRjをそれぞれ距離/クロック数変換回路DC~DCへ出力する。

【0027】
距離/クロック数変換回路DCは、距離演算回路DP11~DP1WからW個の距離信号D1jを受け、その受けたW個の距離信号D1jの和に一致するクロック信号CLKのクロック数CN_total1を後述する方法によってカウントし、そのクロック数CN_total1をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。そして、このクロック数CN_total1をカウントしたタイミングは、検索データと参照データ1との距離に一致する一致タイミングである。

【0028】
また、距離/クロック数変換回路DCは、距離演算回路DP21~DP2WからW個の距離信号D2jを受け、その受けたW個の距離信号D2jの和に一致するクロック信号CLKのクロック数CN_total2を後述する方法によってカウントし、そのクロック数CN_total2をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。このクロック数CN_total2をカウントしたタイミングは、検索データと参照データ2とが一致する一致タイミングである。

【0029】
以下、同様にして、距離/クロック数変換回路DCは、距離演算回路DPR1~DPRWからW個の距離信号DRjを受け、その受けたW個の距離信号DRjの和に一致するクロック信号CLKのクロック数CN_totalRを後述する方法によってカウントし、そのクロック数CN_totalRをカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。このクロック数CN_totalRをカウントしたタイミングは、検索データと参照データRとが一致する一致タイミングである。

【0030】
行デコーダ2は、メモリ部1の行方向のアドレスを指定する。列デコーダ3は、メモリ部1の列方向のアドレスを指定する。読出/書込回路4は、参照データを行デコーダ2および列デコーダ3によって指定された参照データ保存回路SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRWに書き込むとともに、検索データを検索データ保存回路5に書き込む。

【0031】
検索データ保存回路5は、読出/書込回路4によって書き込まれた検索データ(M×Wビットのデータ)を保存する。

【0032】
Winner検出器20は、タイミング信号C~Cをそれぞれ距離/クロック数変換回路DC~DCから受け、その受けたタイミング信号C~Cのうち、一致タイミングが早い順にk(kは1≦k<Rを満たす整数)個のタイミング信号を検出し、その検出したk個のタイミング信号を検索データと参照データとの類似度を示すマッチ信号M~Mとして出力する。

【0033】
図2は、図1に示す距離/クロック数変換回路DCの構成を示す概略図である。図2を参照して、距離/クロック数変換回路DCは、増幅器21~2Wと、カウンタ一致検出回路31~3Wとを含む。

【0034】
増幅器21は、連想メモリ100に内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受け、その受けたクロック信号CLKを増幅して増幅器22およびカウンタ一致検出回路31へ出力する。

【0035】
増幅器22は、クロック信号CLKを増幅器21から受け、その受けたクロック信号CLKを増幅器23(図示せず)およびカウンタ一致検出回路32へ出力する。

【0036】
以下、同様にして、増幅器2Wは、クロック信号CLKを増幅器2W-1(図示せず)から受け、その受けたクロック信号CLKをカウンタ一致検出回路3Wへ出力する。

【0037】
カウンタ一致検出回路31~3Wは、それぞれ、距離演算回路DP11~DP1Wに対応して設けられる。そして、カウンタ一致検出回路31~3Wは、直列に接続される。

【0038】
カウンタ一致検出回路31は、増幅器21からクロック信号CLKを受け、連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、距離演算回路DP11からMビットのビット長を有する距離信号D11を受ける。カウンタ一致検出回路31は、検索開始信号SBがL(論理ロー)レベルからH(論理ハイ)レベルに切り替わると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントする。そして、カウンタ一致検出回路31は、そのクロック数をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してカウンタ一致検出回路32へ出力する。カウンタ一致検出回路31は、一致信号MTH1を出力すると、動作を停止する。

【0039】
カウンタ一致検出回路32は、増幅器22からクロック信号CLKを受け、カウンタ一致検出回路31から一致信号MTH1を受け、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。カウンタ一致検出回路32は、カウンタ一致検出回路31から一致信号MTH1を受けるまで動作を停止している。カウンタ一致検出回路32は、カウンタ一致検出回路31から一致信号MTH1を受けると駆動され、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントする。そして、カウンタ一致検出回路32は、そのクロック数をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してカウンタ一致検出回路33(図示せず)へ出力する。カウンタ一致検出回路32は、一致信号MTH2を出力すると、動作を停止する。

【0040】
以下、同様にして、カウンタ一致検出回路3Wは、増幅器2Wからクロック信号CLKを受け、カウンタ一致検出回路3W-1から一致信号MTHW-1を受け、距離演算回路DP1WからMビットのビット長を有する距離信号D1Wを受ける。カウンタ一致検出回路3Wは、カウンタ一致検出回路3W-1から一致信号MTHW-1を受けるまで動作を停止している。カウンタ一致検出回路3Wは、カウンタ一致検出回路3W-1から一致信号MTHW-1を受けると駆動され、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D1Wに一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントする。そして、カウンタ一致検出回路3Wは、そのクロック数をカウントしたタイミングを示す一致信号MTHWをタイミング信号Cとしてクロック信号CLKに同期してWinner検出器20へ出力する。カウンタ一致検出回路3Wは、タイミング信号Cを出力すると、動作を停止する。

【0041】
なお、図1に示す距離/クロック数変換回路DC~距離/クロック数変換回路DCの各々も、図2に示す距離/クロック数変換回路DCと同じ構成からなる。

【0042】
図3は、図2に示すカウンタ一致検出回路31の構成を示す概略図である。図3を参照して、カウンタ一致検出回路31は、カウンタ311と、一致検出回路312とを含む。

【0043】
カウンタ311は、増幅器21からクロック信号CLKを受け、連想メモリ100の制御回路(図示せず)からリセット信号RSTを受ける。カウンタ311は、リセット信号RSTを受けると、カウンタ値をリセットし、Mビットのビット値をクロック信号CLKに同期して昇順にカウントする。そして、カウンタ311は、そのカウントしたカウンタ値CV11をクロック信号CLKに同期して一致検出回路312へ順次出力する。

【0044】
一致検出回路312は、増幅器21からクロック信号CLKを受け、連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、カウンタ311からカウンタ値CV11を順次受け、距離演算回路DP11から距離信号D11を受ける。

【0045】
一致検出回路312は、検索開始信号SBがLレベルからHレベルに切り替わると、距離信号D11に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数をカウントする。そして、一致検出回路312は、そのクロック数をカウントしたタイミングを示す一致信号MTH1をカウンタ一致検出回路32へ出力する。

【0046】
一致検出回路312は、一致信号MTH1を出力すると、動作を停止する。

【0047】
なお、図2に示すカウンタ一致検出回路32~3Wの各々も、図3に示すカウンタ一致検出回路31と同じ構成からなる。この場合、カウンタ一致検出回路32~3Wの一致検出回路312は、それぞれ、カウンタ一致検出回路31~3W-1の一致検出回路312から一致信号MTH1~MTHW-1を受けるまで動作を停止し、一致信号MTH1~MTHW-1を受けると駆動され、動作を開始する。

【0048】
図4は、図3に示すカウンタ一致検出回路31の動作を説明するための図である。なお、図4においては、カウンタ値CV11および距離信号D11の各々が3ビットである場合を例にしてカウンタ一致検出回路31の動作を説明する。また、距離信号D11は、“011”からなるものとする。

【0049】
図4を参照して、カウンタ一致検出回路31のカウンタ311は、連想メモリ100の制御回路からリセット信号RSTを受けると、カウント数をリセットし、クロック信号CLKの連続する周期T1,T2,T3,T4に同期して、それぞれ、“000”,“001”,“010”,“011”のビット値を順次カウントし、そのカウントした“000”,“001”,“010”,“011”のカウンタ値CV11を一致検出回路312へ順次出力する。

【0050】
そして、一致検出回路312は、距離演算回路DP11から“011”の距離信号D11を受け、クロック信号CLKの周期T1に同期して“000”のカウンタ値CV11をカウンタ311から受けると、タイミングt1において“0”のクロック数をカウントし、“0”のクロック数において、“000”のカウンタ値CV11が“011”の距離信号D11に一致しないことを検出する。

【0051】
そして、一致検出回路312は、クロック信号CLKの周期T1の次の周期T2に同期して“001”のカウンタ値CV11をカウンタ311から受けると、タイミングt2において“1”のクロック数をカウントし、“1”のクロック数において、“001”のカウンタ値CV11が“011”の距離信号D11に一致しないことを検出する。

【0052】
また、一致検出回路312は、クロック信号CLKの周期T2の次の周期T3に同期して“010”のカウンタ値CV11をカウンタ311から受けると、タイミングt3において“2”のクロック数をカウントし、“2”のクロック数において、“010”のカウンタ値CV11が“011”の距離信号D11に一致しないことを検出する。

【0053】
更に、一致検出回路312は、クロック信号CLKの周期T3の次の周期T4に同期して“011”のカウンタ値CV11をカウンタ311から受けると、タイミングt4において“3”のクロック数をカウントし、“3”のクロック数において、“011”のカウンタ値CV11が“011”の距離信号D11に一致することを検出する。そして、一致検出回路312は、“011”の距離信号D11に一致する“011”のカウンタ値CV11が得られるときのクロック信号CLKのクロック数(=“3”)をカウントしたタイミングt4を示す一致信号MTH1をカウンタ一致検出回路32および連想メモリ100の制御回路へ出力する。その後、一致検出回路312は、図4において、“4”,“5”のクロック数において、“011”のカウンタ値が保持されているように、動作を停止する。

【0054】
この場合、カウンタ一致検出回路31は、タイミングt1において“0”のクロック数をカウントしてからタイミングt4において“3”のクロック数をカウントして一致信号MTH1を出力するまでに、タイミングt1からタイミングt4までの時間(=t4-t1)を要する。

【0055】
なお、図2に示すカウンタ一致検出回路32~3W-1の各々において、カウンタ311は、連想メモリ100の制御回路からリセット信号RSTを受けるまで動作を停止し、連想メモリ100の制御回路からリセット信号RSTを受けると、“000”,“001”,“010”,“011”,・・・のビット値を順次カウントし、そのカウントした“000”,“001”,“010”,“011”,・・・のカウンタ値(=各カウンタ値CV12~CV1W-1)を一致検出回路312へ順次出力する。

【0056】
カウンタ一致検出回路32~3W-1の一致検出回路312は、それぞれ、カウンタ一致検出回路31~3W-2の一致検出回路312から一致信号MTH1~MTHW-2を受けるまで動作を停止し、一致信号MTH1~MTHW-2を受けると、カウンタ値CV12~CV1W-1がそれぞれ距離信号D12~D1W-1に一致するときのクロック信号CLKのクロック数をカウントし、そのクロック数をカウントしたタイミングを示す一致信号MTH2~MTHW-1をそれぞれカウンタ一致検出回路33~3Wおよび連想メモリ100の制御回路へ出力する。そして、カウンタ一致検出回路32~3W-1の一致検出回路312は、動作を停止する。

【0057】
また、カウンタ一致検出回路3Wのカウンタ311は、連想メモリ100の制御回路からリセット信号RSTを受けるまで動作を停止し、連想メモリ100の制御回路からリセット信号RSTを受けると、“000”,“001”,“010”,“011”,・・・のビット値を順次カウントし、そのカウントした“000”,“001”,“010”,“011”,・・・のカウンタ値CV1Wを一致検出回路312へ順次出力する。

【0058】
カウンタ一致検出回路3Wの一致検出回路312は、カウンタ一致検出回路3W-1の一致検出回路312から一致信号MTHW-1を受けるまで動作を停止し、一致信号MTHW-1を受けると、カウンタ値CV1Wが距離信号D1Wに一致するときのクロック信号CLKのクロック数をカウントし、そのクロック数をカウントしたタイミングを示すタイミング信号(各タイミング信号C~C)をWinner検出器20および連想メモリ100の制御回路へ出力する。そして、カウンタ一致検出回路3Wの一致検出回路312は、動作を停止する。

【0059】
連想メモリ100の制御回路は、カウンタ一致検出回路31~3W-1からそれぞれ一致信号MTH1~MTHW-1を受けると、リセット信号RSTをそれぞれカウンタ一致検出回路32~3Wへ出力する。また、連想メモリ100の制御回路は、カウンタ一致検出回路3Wからタイミング信号Cを受けると、リセット信号RSTをカウンタ一致検出回路31~3Wへ出力する。

【0060】
図5は、図1に示す距離/クロック数変換回路DCの動作を説明するための図である。なお、図5においては、距離/クロック数変換回路DCが2つのカウンタ一致検出回路31,32からなる場合を例にして距離/クロック数変換回路DCの動作を説明する。また、距離信号D11が“3”からなり、距離信号D12が“5”からなることを前提とする。

【0061】
図5を参照して、距離演算回路DP11は、検索データと参照データSC11との距離を式(1)に従って演算し、距離信号D11(=“011”)をカウンタ一致検出回路31へ出力する。また、距離演算回路DP12は、検索データと参照データSC12との距離を式(1)に従って演算し、距離信号D12(=“101”)をカウンタ一致検出回路32へ出力する。

【0062】
カウンタ一致検出回路31は、距離演算回路DP11から距離信号D11(=“011”)を受け、連想メモリ100の制御回路からリセット信号RSTおよび検索開始信号SBを受けると、上述した方法によって、カウンタ値CV11が距離信号D11(=“011”)に一致するときのクロック信号CLKのクロック数(=“3”)をカウントし、“3”のクロック数をカウントしたタイミングを示す一致信号MTH1をカウンタ一致検出回路32および連想メモリ100の制御回路へ出力する。そして、カウンタ一致検出回路31は、動作を停止する。

【0063】
カウンタ一致検出回路32は、距離演算回路DP12から距離信号D12(=“101”)を受け、連想メモリ100の制御回路からリセット信号RSTを受ける。そして、カウンタ一致検出回路32は、“3”のクロック数が得られたタイミングでカウンタ一致検出回路31から一致信号MTH1を受けると、動作を開始し、距離信号D12(=“101”)に一致するカウンタ値CV12(=“101”)が得られるときのクロック信号CLKのクロック数(=“5”)をカウントし、“5”のクロック数をカウントしたタイミングでカウンタ値CV12(=“101”)が距離信号D12(=“101”)に一致することを検出する。

【0064】
そうすると、カウンタ一致検出回路32は、“5”のクロック数をカウントしたタイミングを示すタイミング信号CをWinner検出器20および連想メモリ100の制御回路へ出力する。そして、カウンタ一致検出回路32は、動作を停止する。

【0065】
このように、カウンタ一致検出回路32は、カウンタ一致検出回路31による“3”のクロック数のカウントが完了した後に、“5”のクロック数をカウントしたタイミングで“5”のクロック数をカウントしたタイミングを示すタイミング信号Cを出力する。従って、カウンタ一致検出回路32は、カウンタ一致検出回路31によるクロック数のカウント開始から“3”+“5”=“8”のクロック数をカウントするまでの時間が経過したタイミングで“5”のクロック数をカウントしたタイミングを示すタイミング信号Cを出力する。即ち、カウンタ一致検出回路32は、“3”の距離信号と“5”の距離信号との和である“8”の距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントし、そのクロック数をカウントしたタイミングを示すタイミング信号Cを出力する。

【0066】
2つのカウンタ一致検出回路31,32が全体でカウントする“8”のクロック数は、カウンタ一致検出回路31がカウントする“3”のクロック数と、カウンタ一致検出回路32がカウントする“5”のクロック数とを加算したものである。このことは、カウンタ一致検出回路32が、カウンタ一致検出回路31において“3”のクロック数がカウントされたタイミングでカウンタ一致検出回路31から一致信号MTH1を受けると、距離信号D12に一致するカウンタ値CV12が得られるときのクロック数をカウントする動作を開始することからも明らかである(図5参照)。

【0067】
その結果、2つのカウンタ一致検出回路31,32が全体で“8”のクロック数をカウントすることは、距離“3”と距離“5”との和(=“8”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントすることに相当する。

【0068】
距離/クロック数変換回路DCは、一般的に、W個の距離信号D11~D1Wを受ける。そして、W個の距離信号D11~D1Wの各々は、Mビットのビット長を有する。従って、距離/クロック数変換回路DCは、M×Wビットのビット長を有する距離信号D1112・・・D1Wを受ける。

【0069】
そして、距離/クロック数変換回路DCにおいて、カウンタ一致検出回路31~3Wは、それぞれ、距離信号D11~D1Wにそれぞれ一致するカウンタ値CV11~CV1Wが得られるときのクロック信号CLKのクロック数CN1~CNWをカウントする。また、カウンタ一致検出回路32~3Wは、それぞれ、カウンタ一致検出回路31~3W-1から一致信号MTH2~MTHW-1を受けた後に、距離信号D12~D1Wにそれぞれ一致するカウンタ値CV12~CV1Wが得られるときのクロック信号CLKのクロック数CN2~CNWのカウントを開始する。

【0070】
その結果、距離/クロック数変換回路DCがカウントするクロック数CN_totalは、クロック数CN1~CNWの和に等しい。そうすると、クロック数CN1~CNWは、それぞれ、距離信号D11~D1Wを表わすので、クロック数CN_totalは、距離信号D11~D1Wの和を表わす。

【0071】
一方、マンハッタン距離nは、次式によって表わされる。

【0072】
【数2】
JP0005916563B2_000003t.gif

【0073】
式(2)の右辺の|In-Re|は、式(1)の右辺の|In-Rerj|において、1つの行(rによって表わされる)における検索データと参照データとの距離|In-Re|に一致する。

【0074】
従って、マンハッタン距離nは、式(1)によって演算した距離をW個の距離について加算したものに等しい。

【0075】
そうすると、距離/クロック数変換回路DCがクロック数CN_totalをカウントしたタイミングを示すタイミング信号Cを出力することは、マンハッタン距離nによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示すWinner信号を出力することに相当する。

【0076】
なお、距離/クロック数変換回路DC~DCの各々も、図5において説明した距離/クロック数変換回路DCの動作と同じ動作によって、それぞれ、タイミング信号C~Cを出力する。

【0077】
図6は、図1に示すWinner検出器20の動作を説明するための図である。図6を参照して、距離/クロック数変換回路DC~DCは、それぞれ、タイミング信号C~Cをクロック信号CLKに同期してWinner検出器20へ出力する。

【0078】
Winner検出器20は、タイミング信号C~Cを受け、その受けたタイミング信号C~Cの立ち上がりタイミングt~tを検出する。そして、Winner検出器20は、立ち上がりタイミングt~tが早い順にk個のタイミング信号C’~C’を検出する。そうすると、Winner検出器20は、タイミング信号C’~C’をマッチ信号M~Mとして出力する。

【0079】
例えば、2個のマッチ信号M,Mを検出する場合、Winner検出器20は、タイミング信号C~Cのうち、立ち上がりタイミングが早い順に2個のタイミング信号C,Cを検出し、その検出したタイミング信号C,Cをマッチ信号M,Mとして出力する。

【0080】
なお、k=2以外のk個のタイミング信号C’~C’を検出する場合も、Winner検出器20は、同様にして、k個のタイミング信号C’~C’を検出し、その検出したk個のタイミング信号C’~C’をマッチ信号M~Mとして出力する。

【0081】
k=1である場合、Winner検出器20は、検索データに最も類似する参照データに対応するタイミング信号(タイミング信号C~Cのいずれか)をマッチ信号Mとして出力する。

【0082】
また、k≠1である場合、Winner検出器20は、検索データに類似するk個の参照データに対応するk個のタイミング信号C’~C’をマッチ信号M~Mとして出力する。この場合、k個のタイミング信号C’~C’において、k個の立ち上がりタイミングは、相互に、少なくともクロック信号CLKの1周期分だけ異なるので、立ち上がりタイミングの早い順にk個のタイミング信号C’~C’を正確に検出できる。つまり、連想メモリ100は、検索データに類似するk個の参照データを正確に検索できる。

【0083】
また、距離/クロック数変換回路DC~DCの動作は、クロック信号CLKに同期して実行されるので、クロック信号CLKの周波数を高くすることによって、連想メモリ100の動作を高速にできる。

【0084】
従って、連想メモリ100は、マンハッタン距離を用いた場合にも、正確、かつ、高速に類似検索を行うことができる。

【0085】
図7は、図3に示すカウンタ311の好ましい構成を示す概略図である。この発明の実施の形態においては、カウンタ311は、好ましくは、図7に示すカウンタ311Aからなる。

【0086】
図7を参照して、カウンタ311Aは、分周器311-1~311-Mを含む。分周器311-1は、Mビットの距離信号(=距離信号D11~D1W,D21~D2W,・・,DR1~DRWの各々)の最下位ビットに対応して設けられる。分周器311-2は、Mビットの距離信号(=距離信号D11~D1W,D21~D2W,・・,DR1~DRWの各々)の第2位ビットに対応して設けられる。以下、同様にして、分周器311-Mは、Mビットの距離信号(=距離信号D11~D1W,D21~D2W,・・,DR1~DRWの各々)の最上位ビットに対応して設けられる。

【0087】
分周器311-1は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。分周器311-2は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。以下、同様にして、分周器311-Mは、クロック信号CLKを2M-1回分周し、その分周した分周信号DVを一致検出回路312へ出力する。

【0088】
図8は、図7に示すカウンタ311Aの動作を説明するための図である。なお、図8においては、カウンタ311Aが4個の分周器311-1~311-4からなる場合を例にしてカウンタ311Aの動作を説明する。

【0089】
図8を参照して、分周器311-1は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。分周器311-2は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。分周器311-3は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。分周器311-4は、クロック信号CLKを2回分周し、その分周した分周信号DVを一致検出回路312へ出力する。

【0090】
その結果、4個の分周器311-1~311-4は、最初に、“0000”のカウンタ値を出力し、2番目に、“0001”のカウンタ値を出力し、3番目に、“0010”のカウンタ値を出力し、以下、同様にして、15番目に、“1110”のカウンタ値を出力し、最後に、“1111”のカウンタ値を出力する。

【0091】
カウンタ311Aは、4ビット以外のカウンタ値を出力する場合も、M個の分周器311-1~311-Mによって構成され、M個の分周器311-1~311-Mは、図8に示す態様と同じ態様で、それぞれ、クロック信号CLKを2回、2回、2回、・・・、2M-1回分周し、その分周した分周信号DV~DVを出力する。その結果、カウンタ311Aは、Mビットのカウンタ値を“0・・・0”,“0・・・1”,・・・,“1・・・1”の順で出力する。

【0092】
従って、分周器311-1~311-Mのうち、Mビットのカウンタ値の最下位ビットから最上位ビットへ向かう方向において第m(mは1≦m≦Mを満たす整数)位のビット値を出力する分周器は、クロック信号CLKを2m-1回に分周した信号を出力する。

【0093】
このように、カウンタ311Aを分周器311-1~311-Mによって構成することによって、通常のカウンタに比べて、回路サイズを小さくでき、消費電力を低減できる。

【0094】
カウンタ一致検出回路31~3Wのカウンタ311が図7に示すカウンタ311Aからなっている場合も、距離/クロック数変換回路DC~DCは、上述した方法によって、それぞれ、M×Wビットのビット長を有する距離信号D11~D1W,D21~D2W,・・・,DR1~DRWの和にそれぞれ一致するクロック数CN_total1~CN_totalRをカウントしたタイミングを示すタイミング信号C~CをWinner検出器20へ出力する。

【0095】
上述したように、距離/クロック数変換回路DC~DCの各々は、図2に示すように、直列に接続されたW個のカウンタ一致検出回路31~3Wからなる。

【0096】
W=2である場合、距離/クロック数変換回路DC~DCの各々は、カウンタ一致検出回路31,32からなる。この場合、距離演算回路DP11~DP1Wは、距離演算回路DP11,DP12からなり、距離信号D11~D1Wは、距離信号D11,D12からなる。

【0097】
そして、カウンタ一致検出回路31は、距離信号D11,D12を一列に配列したときの一方端の距離信号である1番目の距離信号D11に対応して設けられ、1番目の距離信号D11を距離演算回路DP11から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けた1番目の距離信号D11に一致するカウンタ値が得られるときのクロック数CN1をカウントし、クロック数CN1をカウントしたタイミングを示す一致信号MTH1を出力する。

【0098】
また、カウンタ一致検出回路32は、距離信号D11,D12を一列に配列したときの一方端からW番目(=2番目)の距離信号であるW番目(=2番目)の距離信号D12に対応して設けられ、カウンタ一致検出回路31から一致信号MTH1を受けると駆動されるとともにW番目(=2番目)の距離信号D12を距離演算回路DP12から受け、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けたW番目(=2番目)の距離信号D12に一致するカウンタ値が得られるときのクロック数CN2をカウントし、クロック数CN2をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。

【0099】
この場合、カウンタ一致検出回路31は、「第1のカウンタ一致検出回路」を構成し、カウンタ一致検出回路32は、「第2のカウンタ一致検出回路」を構成する。

【0100】
また、W=3以上である場合、距離/クロック数変換回路DC~DCの各々は、カウンタ一致検出回路31~3Wからなる。

【0101】
そして、カウンタ一致検出回路31は、距離信号D11~D1Wを一列に配列したときの一方端の距離信号である1番目の距離信号D11に対応して設けられ、1番目の距離信号D11を距離演算回路DP11から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けた1番目の距離信号D11に一致するカウンタ値が得られるときのクロック数CN1をカウントし、クロック数CN1をカウントしたタイミングを示す一致信号MTH1を出力する。

【0102】
また、カウンタ一致検出回路32~3W-1は、2番目の距離信号D12からW-1番目の距離信号D1W-1までのW-2個の距離信号D12~D1W-1に対応して設けられる。そして、カウンタ一致検出回路32~3W-1の各々は、カウンタ一致検出回路31またはw-1(wは2≦w≦W-1を満たす整数)番目の距離信号に対応して設けられたカウンタ一致検出回路32~3W-2から1番目またはw-1番目の距離信号に対応して設けられたカウンタ一致検出回路31~3W-2から1番目またはw番目の距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントしたタイミングを示す一致信号MTH1~MTH3W-2を受けると駆動されるとともにw番目の距離信号(=距離信号D12~D1W-1のいずれか)を受け、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、w番目の距離信号(=距離信号D12~D1W-1のいずれか)に一致するカウンタ値が得られるときのクロック数CN3をカウントし、クロック数CN3をカウントしたタイミングを示す一致信号(=一致信号MTH2~MTHW-1のいずれか)を出力する。

【0103】
更に、カウンタ一致検出回路3Wは、W番目の距離信号D1Wに対応して設けられ、W-1番目の距離信号に対応して設けられたカウンタ一致検出回路3W-1から一致信号MTHW-1を受けると駆動されるとともにW番目の距離信号D1Wを受け、カウンタ一致検出回路3W-1から一致信号MTH3W-1を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、W番目の距離信号D1Wに一致するカウンタ値が得られるときのクロック数CN4をカウントし、クロック数CN4をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。

【0104】
この場合、カウンタ一致検出回路31は、「第1のカウンタ一致検出回路」を構成し、カウンタ一致検出回路32~3W-1は、「W-2個の第3のカウンタ一致検出回路」を構成し、カウンタ一致検出回路3Wは、「第4のカウンタ一致検出回路」を構成する。

【0105】
図9は、図1に示す距離/クロック数変換回路DC~DCの別の構成を示す概略図である。

【0106】
この発明の実施の形態においては、距離/クロック数変換回路DC~DCの各々は、図9に示す距離/クロック数変換回路DC’からなっていてもよい。この場合、W=2(iは2以上の整数)である。

【0107】
図9を参照して、距離/クロック数変換回路DC’は、増幅器41~4Lと、カウンタ一致検出回路51~5Lとを含む。ここで、L=W/s(sは、W以下の2を満たす整数、xは、正の整数)である。

【0108】
増幅器41は、連想メモリ100に内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受け、その受けたクロック信号CLKを増幅して増幅器42およびカウンタ一致検出回路51へ出力する。

【0109】
増幅器42は、クロック信号CLKを増幅器41から受け、その受けたクロック信号CLKを増幅して増幅器43(図示せず)およびカウンタ一致検出回路52へ出力する。

【0110】
以下、同様にして、増幅器4Lは、クロック信号CLKを増幅器4L-1(図示せず)から受け、その受けたクロック信号CLKを増幅してカウンタ一致検出回路5Lへ出力する。

【0111】
カウンタ一致検出回路51,52,・・・,5Lは、それぞれ、s個の距離演算回路DP11,DP1(1+L),・・・,DP1(1+(u-1)L)、s個の距離演算回路DP12,DP1(2+L),・・・,DP1(2+(u-1)L)、・・・、s個の距離演算回路DP1L,DP1(L+L),・・・,DP1(L+(u-1)L)に対応して設けられる。なお、uは、1,2,3,・・・,sである。

【0112】
そして、カウンタ一致検出回路51~5Lは、直列に接続される。また、カウンタ一致検出回路51~5Lの各々は、図3に示すカウンタ一致検出回路31と同じ構成からなる。この場合、カウンタ一致検出回路51~5Lの各々は、図3に示すカウンタ311または図7に示すカウンタ311Aを含む。

【0113】
カウンタ一致検出回路51は、増幅器41からクロック信号CLKを受け、連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、距離演算回路DP11,DP1(1+L),・・・,DP1(1+(u-1)L)からそれぞれ距離信号D11,D1(1+L),・・・,D1(1+(u-1)L)を受ける。

【0114】
カウンタ一致検出回路51は、距離信号D11,D1(1+L),・・・,D1(1+(u-1)L)を受け、検索開始信号SBがLレベルからHレベルに切り替わると、上述した方法によって、距離信号D11,D1(1+L),・・・,D1(1+(u-1)L)の和に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントする。そして、カウンタ一致検出回路51は、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してカウンタ一致検出回路52へ出力する。その後、カウンタ一致検出回路51は、動作を停止する。

【0115】
また、カウンタ一致検出回路52は、増幅器42からクロック信号CLKを受け、カウンタ一致検出回路51から一致信号MTH1を受け、距離演算回路DP12,DP1(2+L),・・・,DP1(2+(u-1)L)からそれぞれ距離信号D12,D1(2+L),・・・,D1(2+(u-1)L)を受ける。

【0116】
カウンタ一致検出回路52は、距離信号D12,D1(2+L),・・・,D1(2+(u-1)L)を受け、一致信号MTH1を受けると、上述した方法によって、距離信号D12,D1(2+L),・・・,D1(2+(u-1)L)の和に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントする。そして、カウンタ一致検出回路52は、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してカウンタ一致検出回路53へ出力する。その後、カウンタ一致検出回路52は、動作を停止する。

【0117】
以下、同様にして、カウンタ一致検出回路5Lは、増幅器4Lからクロック信号CLKを受け、カウンタ一致検出回路5L-1から一致信号MTHL-1を受け、距離演算回路DP1L,DP1(L+L),・・・,DP1(L+(u-1)L)からそれぞれ距離信号D1L,D1(L+L),・・・,D1(L+(u-1)L)を受ける。

【0118】
カウンタ一致検出回路5Lは、距離信号D1L,D1(L+L),・・・,D1(L+(u-1)L)を受け、一致信号MTHL-1を受けると、上述した方法によって、距離信号D1L,D1(L+L),・・・,D1(L+(u-1)L)の和に一致するカウンタ値CV1Lが得られるときのクロック信号CLKのクロック数CN_Lをカウントする。そして、カウンタ一致検出回路5Lは、クロック数CN_Lをカウントしたタイミングを示すタイミング信号Cをクロック信号CLKに同期してWinner検出器20へ出力する。その後、カウンタ一致検出回路5Lは、動作を停止する。

【0119】
なお、距離信号D11,D1(1+L),・・・,D1(1+(u-1)L),D12,D1(2+L),・・・,D1(2+(u-1)L),・・・,D1L,D1(L+L),・・・,D1(L+(u-1)L)の各々は、Mビットのビット値からなる。

【0120】
従って、距離/クロック数変換回路DC~DC(=距離/クロック数変換回路DC’)の各々は、L(=W/s)個の距離信号に対応して設けられ、各々がMビットのビット長を有するW個の距離信号に基づいて、タイミング信号(タイミング信号C~Cのいずれか)を出力するL(=W/s)個のカウンタ一致検出回路を含み、L(=W/s)個のカウンタ一致検出回路は、各々がL(=W/s)個の距離信号からなるs組の距離信号を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けたs組の距離信号に含まれるW個の距離信号の和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントし、そのクロック数をカウントしたタイミングを示すタイミング信号(タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0121】
カウンタ一致検出回路51~5L-1の各々は、s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(=クロック数CN_1~CN_L-1のいずれか)をカウントしたタイミングを示す一致信号(=一致信号MTH1~MTHL-1のいずれか)を出力し、カウンタ一致検出回路5Lは、s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_Lをカウントしたタイミングを示すタイミング信号(タイミング信号C~Cのいずれか)を出力し、L=W/sであるので、L(=W/s)個のカウンタ一致検出回路51~5Lは、結局、(W/s)×s=W個の距離信号の和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントしたタイミングを示すタイミング信号(タイミング信号C~Cのいずれか)を出力することになる。

【0122】
図10は、図1に示す距離/クロック数変換回路DC~DCの更に別の構成を示す概略図である。

【0123】
この発明の実施の形態においては、距離/クロック数変換回路DC~DCの各々は、図10に示す距離/クロック数変換回路DC”からなっていてもよい。この場合も、W=2(iは2以上の整数)である。

【0124】
図10を参照して、距離/クロック数変換回路DC”は、図9に示す距離/クロック数変換回路DC’にスイッチング制御回路60およびマルチプレクサ61~6Lを追加したものであり、その他は、距離/クロック数変換回路DC’と同じである。

【0125】
距離/クロック数変換回路DC”においては、増幅器41~4Lは、クロック信号CLKを増幅し、その増幅したクロック信号CLKをそれぞれカウンタ一致検出回路51~5Lへ出力するとともに、その増幅したクロック信号CLKをスイッチング制御回路60へ出力する。

【0126】
また、距離/クロック数変換回路DC”においては、マルチプレクサ61,62,・・・,6Lは、それぞれ、s個の距離演算回路DP11,DP1(1+L),・・・,DP1(1+(u-1)L)、s個の距離演算回路DP12,DP1(2+L),・・・,DP1(2+(u-1)L)、・・・、s個の距離演算回路DP1L,DP1(L+L),・・・,DP1(L+(u-1)L)に対応して設けられる。そして、カウンタ一致検出回路51~5Lは、それぞれ、マルチプレクサ61~6Lに対応して設けられる。

【0127】
スイッチング制御回路60は、連想メモリ100の制御回路から検索開始信号SBおよびリセット信号RSTを受け、カウンタ一致検出回路51~5Lからそれぞれ一致信号MTH1~MTHLを受ける。

【0128】
そして、スイッチング制御回路60は、検索開始信号SBおよびリセット信号RSTを受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0129】
また、スイッチング制御回路60は、一致信号MTHLをカウンタ一致検出回路5Lから受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。スイッチング制御回路60は、この処理をs-1回実行する。

【0130】
更に、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。スイッチング制御回路60は、この処理をs回実行する。

【0131】
更に、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路53へ出力するとともに出力信号OUT3をマルチプレクサ63へ出力する。スイッチング制御回路60は、この処理をs回実行する。

【0132】
以下、同様にして、スイッチング制御回路60は、一致信号MTHL-1をカウンタ一致検出回路5L-1から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路5Lへ出力するとともに出力信号OUTLをマルチプレクサ6Lへ出力する。スイッチング制御回路60は、この処理をs回実行する。

【0133】
マルチプレクサ61は、s個の距離信号D11,D1(1+L),・・・,D1(1+(u-1)L)を受ける。そして、マルチプレクサ61は、1回目の出力信号OUT1をスイッチング制御回路60から受けると、距離信号D11をカウンタ一致検出回路51へ出力し、2回目の出力信号OUT1をスイッチング制御回路60から受けると、距離信号D1(1+L)をカウンタ一致検出回路51へ出力し、以下、同様にして、s回目の出力信号OUT1をスイッチング制御回路60から受けると、距離信号D1(1+(u-1)L)をカウンタ一致検出回路51へ出力する。

【0134】
マルチプレクサ62は、s個の距離信号D12,D1(2+L),・・・,D1(2+(u-1)L)を受ける。そして、マルチプレクサ62は、1回目の出力信号OUT2をスイッチング制御回路60から受けると、距離信号D12をカウンタ一致検出回路52へ出力し、2回目の出力信号OUT2をスイッチング制御回路60から受けると、距離信号D1(2+L)をカウンタ一致検出回路52へ出力し、以下、同様にして、s回目の出力信号OUT2をスイッチング制御回路60から受けると、距離信号D1(2+(u-1)L)をカウンタ一致検出回路52へ出力する。

【0135】
以下、同様にして、マルチプレクサ6Lは、s個の距離信号D1L,D1(L+L),・・・,D1(L+(u-1)L)を受ける。そして、マルチプレクサ6Lは、1回目の出力信号OUTLをスイッチング制御回路60から受けると、距離信号D1Lをカウンタ一致検出回路5Lへ出力し、2回目の出力信号OUTLをスイッチング制御回路60から受けると、距離信号D1(L+L)をカウンタ一致検出回路5Lへ出力し、以下、同様にして、s回目の出力信号OUTLをスイッチング制御回路60から受けると、距離信号D1(L+(u-1)L)をカウンタ一致検出回路5Lへ出力する。

【0136】
カウンタ一致検出回路51は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路51は、距離信号D11をマルチプレクサ61から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。カウンタ一致検出回路51は、この処理をs個の距離信号D11,D1(1+L),・・・,D1(1+(u-1)L)の全てについて実行する。

【0137】
また、カウンタ一致検出回路52は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路52は、距離信号D12をマルチプレクサ62から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。カウンタ一致検出回路52は、この処理をs個の距離信号D12,D1(2+L),・・・,D1(2+(u-1)L)の全てについて実行する。

【0138】
以下、同様にして、カウンタ一致検出回路5Lは、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路5Lは、距離信号D1Lをマルチプレクサ6Lから受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D1Lに一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_Lをカウントし、クロック数CN_Lをカウントしたタイミングを示す一致信号MTHLをスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路5Lは、動作を停止する。カウンタ一致検出回路5Lは、この処理をs-1個の距離信号D12,D1(2+L),・・・,D1(2+(u-1)L-1)の全てについて実行する。

【0139】
そして、カウンタ一致検出回路5Lは、s回目のリセット信号RSTをスイッチング制御回路60から受けると駆動されるとともに距離信号D1(L+(u-1)L)をマルチプレクサ6Lから受け、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D1(L+(u-1)L)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_Lをカウントし、クロック数CN_Lをカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。

【0140】
距離/クロック数変換回路DC~DC(=距離/クロック数変換回路DC”)の各々においては、検索データに類似する参照データの検索が開始されると、スイッチング制御回路60は、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0141】
そして、マルチプレクサ61は、スイッチング制御回路60からの1回目の出力信号OUT1に応じて、距離信号D11をカウンタ一致検出回路51へ出力する。

【0142】
カウンタ一致検出回路51は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路51は、距離信号D11をマルチプレクサ61から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0143】
その後、スイッチング制御回路60は、カウンタ一致検出回路51からの一致信号MTH1に応じて、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。

【0144】
マルチプレクサ62は、スイッチング制御回路60からの1回目の出力信号OUT2に応じて、距離信号D12をカウンタ一致検出回路52へ出力する。

【0145】
カウンタ一致検出回路52は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路52は、距離信号D12をマルチプレクサ62から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0146】
以下、同様にして、スイッチング制御回路60は、カウンタ一致検出回路5L-1からの一致信号MTHL-1に応じて、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路5Lへ出力するとともに出力信号OUTLをマルチプレクサ6Lへ出力する。

【0147】
そして、マルチプレクサ6Lは、スイッチング制御回路60からの1回目の出力信号OUTLに応じて、距離信号D1Lをカウンタ一致検出回路5Lへ出力する。

【0148】
カウンタ一致検出回路5Lは、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路5Lは、距離信号D1Lをマルチプレクサ6Lから受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D1Lに一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_Lをカウントし、クロック数CN_Lをカウントしたタイミングを示す一致信号MTHLをスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路5Lは、動作を停止する。

【0149】
その後、スイッチング制御回路60は、カウンタ一致検出回路5Lからの一致信号MTHLに応じて、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0150】
その後、カウンタ一致検出回路51~5L-1、スイッチング制御回路60およびマルチプレクサ61~6L-1は、上述した動作をs-1回繰り返し実行し、カウンタ一致検出回路5Lおよびマルチプレクサ6Lは、上述した動作をs-2回繰り返し実行する。

【0151】
そして、カウンタ一致検出回路5Lは、s回目のリセット信号RSTをスイッチング制御回路60から受け、距離信号D1(L+(u-1)L)をマルチプレクサ6Lから受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D1(L+(u-1)L)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_Lをカウントし、クロック数CN_Lをカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。そして、カウンタ一致検出回路5Lは、動作を停止する。

【0152】
L(=W/s)個のカウンタ一致検出回路51~5Lを1個のカウンタ一致検出回路MDCと考えた場合、カウンタ一致検出回路MDCは、1回目、L(=W/s)個の距離信号D11~D1Lを受ける。そして、カウンタ一致検出回路51~5Lがそれぞれ距離信号D11~D1Lに一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1~CN_Lをカウントし、クロック数CN_1~CN_Lをカウントしたタイミングを示す一致信号MTH1~MTHLを出力することは、カウンタ一致検出回路MDCが距離信号D11~D1Lの和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(CN_1+CN_2+・・・+CN_L)をカウントし、そのクロック数(CN_1+CN_2+・・・+CN_L)をカウントしたタイミングを示す一致信号を出力することに相当する。また、カウンタ一致検出回路MDCは、この処理をs-1回繰り返し実行する。そして、カウンタ一致検出回路MDCは、s-1回目の一致信号を出力すると、L(=W/s)個の距離信号D1(1+(u-1)L),D1(2+(u-1)L),・・・,D1(L+(u-1)L)の和に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(CN_1+CN_2+・・・+CN_L)をカウントし、そのクロック数(CN_1+CN_2+・・・+CN_L)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0153】
従って、距離/クロック数変換回路DC”においては、L(=W/s)個のカウンタ一致検出回路51~5Lは、L(=W/s)個の距離信号D11~D1Lを受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けたL(=W/s)個の距離信号D11~D1Lの和に一致するカウンタ値が得られるときのクロック信号CLKの第1のクロック数をカウントし、第1のクロック数をカウントしたタイミングを示す第1の一致信号を出力する処理をs-1回繰り返し実行し、前記第1の一致信号をs-1回出力し、かつ、s回目にL(=W/s)個の距離信号を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、その受けたL(=W/s)個の距離信号に一致するカウンタ値が得られるときのクロック信号CLKの第2のクロック数をカウントし、前記第2のクロック数をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0154】
図11は、図9に示す距離/クロック数変換回路DC’の具体的な構成を示す概略図である。

【0155】
図11を参照して、W=2=2=8からなり、s=2=2=2からなる場合、L=W/s=8/2=4であり、距離/クロック数変換回路DC’-1は、増幅器41~44と、カウンタ一致検出回路51~54とを含む。

【0156】
また、W個の距離信号D11~D1Wは、8個の距離信号D11~D18からなり、W個の距離演算回路DP11~DP1Wは、8個の距離演算回路DP11~DP18からなる。ここで、距離信号D11~D18は、それぞれ、D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”であるものとする。

【0157】
そして、カウンタ一致検出回路51は、2個の距離演算回路DP11,DP15に対応して設けられ、カウンタ一致検出回路52は、2個の距離演算回路DP12,DP16に対応して設けられ、カウンタ一致検出回路53は、2個の距離演算回路DP13,DP17に対応して設けられ、カウンタ一致検出回路54は、2個の距離演算回路DP14,DP18に対応して設けられる。

【0158】
図12は、図11に示す距離/クロック数変換回路DC’-1の動作を説明するための図である。

【0159】
距離/クロック数変換回路DC~DCの各々は、図11に示す距離/クロック数変換回路DC’-1からなる。そして、距離/クロック数変換回路DC~DCの各々(=距離/クロック数変換回路DC’-1)において、検索データに類似する参照データの検索が開始されると、カウンタ一致検出回路51は、距離演算回路DP11,DP15からそれぞれ距離信号D11(=“3”),D15(=“2”)を受け、カウンタ一致検出回路52は、距離演算回路DP12,DP16からそれぞれ距離信号D12(=“2”),D16(=“4”)を受け、カウンタ一致検出回路53は、距離演算回路DP13,DP17からそれぞれ距離信号D13(=“5”),D17(=“2”)を受け、カウンタ一致検出回路54は、距離演算回路DP14,DP18からそれぞれ距離信号D14(=“1”),D18(=“3”)を受ける。

【0160】
そうすると、カウンタ一致検出回路51は、距離信号D11(=“3”),D15(=“2”)の和(=“5”=“101”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN1(=“5”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN1(=“5”)をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してカウンタ一致検出回路52へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0161】
カウンタ一致検出回路52は、一致信号MTH1をカウンタ一致検出回路51から受けると、距離信号D12(=“2”),D16(=“4”)の和(=“6”=“110”)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN2(=“6”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN2(=“6”)をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してカウンタ一致検出回路53へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0162】
カウンタ一致検出回路53は、一致信号MTH2をカウンタ一致検出回路52から受けると、距離信号D13(=“5”),D17(=“2”)の和(=“7”=“111”)に一致するカウンタ値CV13が得られるときのクロック信号CLKのクロック数CN4(=“7”)をカウントする。そして、カウンタ一致検出回路53は、クロック数CN4(=“7”)をカウントしたタイミングを示す一致信号MTH3をクロック信号CLKに同期してカウンタ一致検出回路54へ出力する。そして、カウンタ一致検出回路53は、動作を停止する。

【0163】
カウンタ一致検出回路54は、一致信号MTH3をカウンタ一致検出回路53から受けると、距離信号D14(=“1”),D18(=“3”)の和(=“4”=“100”)に一致するカウンタ値CV14が得られるときのクロック数CN4(=“4”)をカウントする。そして、カウンタ一致検出回路54は、クロック数CN4(=“4”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をクロック信号CLKに同期してWinner検出器20へ出力する。そして、カウンタ一致検出回路54は、動作を停止する。

【0164】
このように、カウンタ一致検出回路51~54の各々は、2つの距離信号の和に一致するカウンタ値が得られるときのクロック数をカウントし、2つの距離信号の和に一致するカウンタ値が得られるときのクロック数をカウントすると、それぞれ、一致信号MTH1~MTH3およびタイミング信号(=タイミング信号C~Cのいずれか)を出力する。

【0165】
距離/クロック数変換回路DC~DCの各々が距離/クロック数変換回路DC’-1からなる場合、距離/クロック数変換回路DC~DCの各々は、距離信号D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”の和(=“22”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(=“22”)をカウントし、クロック数(=“22”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0166】
図13は、図9に示す距離/クロック数変換回路DC’の別の具体的な構成を示す概略図である。

【0167】
図13を参照して、W=2=2=8からなり、s=2=2=4からなる場合、L=W/s=8/4=2であり、距離/クロック数変換回路DC’-2は、増幅器41,42と、カウンタ一致検出回路51,52とを含む。

【0168】
また、W個の距離信号D11~D1Wは、8個の距離信号D11~D18からなり、W個の距離演算回路DP11~DP1Wは、8個の距離演算回路DP11~DP18からなる。また、距離信号D11~D18の各々は、4ビットのビット値からなる。ここで、距離信号D11~D18は、それぞれ、D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”であるものとする。

【0169】
そして、カウンタ一致検出回路51は、4個の距離演算回路DP11,DP13,DP15,DP17に対応して設けられ、カウンタ一致検出回路52は、4個の距離演算回路DP12,DP14,DP16,DP18に対応して設けられる。

【0170】
なお、カウンタ一致検出回路51,52の各々において、カウンタ311または311Aは、4ビットのカウンタ値を一致検出回路312へ出力する。

【0171】
図14は、図13に示す距離/クロック数変換回路DC’-2の動作を説明するための図である。

【0172】
距離/クロック数変換回路DC~DCの各々は、図13に示す距離/クロック数変換回路DC’-2からなる。そして、距離/クロック数変換回路DC~DCの各々(=距離/クロック数変換回路DC’-2)において、検索データに類似する参照データの検索が開始されると、カウンタ一致検出回路51は、距離演算回路DP11,DP13,DP15,DP17からそれぞれ距離信号D11(=“3”),D13(=“5”),D15(=“2”),D17(=“2”)を受け、カウンタ一致検出回路52は、距離演算回路DP12,DP14,DP16,DP18からそれぞれ距離信号D12(=“2”),D14(=“1”),D16(=“4”),D18(=“3”)を受ける。

【0173】
そうすると、カウンタ一致検出回路51は、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11(=“3”),D13(=“5”),D15(=“2”),D17(=“2”)の和(=“12”=“1100”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN1(=“12”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN1をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してカウンタ一致検出回路52へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0174】
カウンタ一致検出回路52は、一致信号MTH1をカウンタ一致検出回路51から受けると駆動され、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12(=“2”),D14(=“1”),D16(=“4”),D18(=“3”)の和(=“10”=“1010”)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN2(=“10”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN2(=“10”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をクロック信号CLKに同期してWinner検出器20へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0175】
このように、カウンタ一致検出回路51,52の各々は、4つの距離信号の和に一致するカウンタ値が得られるときのクロック数をカウントし、4つの距離信号の和に一致するカウンタ値が得られるときのクロック数をカウントすると、それぞれ、一致信号MTH1およびタイミング信号(=タイミング信号C~Cのいずれか)を出力する。

【0176】
距離/クロック数変換回路DC~DCの各々が距離/クロック数変換回路DC’-2からなる場合も、距離/クロック数変換回路DC~DCの各々は、距離信号D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”の和(=“22”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(=“22”)をカウントし、クロック数(=“22”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0177】
図15は、図10に示す距離/クロック数変換回路DC”の具体的な構成を示す概略図である。

【0178】
図15を参照して、W=2=2=8からなり、s=2=2=2からなる場合、L=W/s=8/2=4であり、距離/クロック数変換回路DC”-1は、増幅器41~44と、カウンタ一致検出回路51~54と、スイッチング制御回路60と、マルチプレクサ61~64とを含む。

【0179】
また、W個の距離信号D11~D1Wは、8個の距離信号D11~D18からなり、W個の距離演算回路DP11~DP1Wは、8個の距離演算回路DP11~DP18からなる。ここで、距離信号D11~D18は、それぞれ、D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”であるものとする。

【0180】
距離/クロック数変換回路DC”-1においては、マルチプレクサ61は、2個の距離演算回路DP11,DP15に対応して設けられ、マルチプレクサ62は、2個の距離演算回路DP12,DP16に対応して設けられ、マルチプレクサ63は、2個の距離演算回路DP13,DP17に対応して設けられ、マルチプレクサ64は、2個の距離演算回路DP14,DP18に対応して設けられる。

【0181】
カウンタ一致検出回路51~54は、それぞれ、マルチプレクサ61~64に対応して設けられる。

【0182】
距離/クロック数変換回路DC”-1においては、増幅器41~44は、クロック信号CLKを増幅し、その増幅したクロック信号CLKをそれぞれカウンタ一致検出回路51~54へ出力するとともに、その増幅したクロック信号CLKをスイッチング制御回路60へ出力する。

【0183】
スイッチング制御回路60は、連想メモリ100の制御回路から検索開始信号SBおよびリセット信号RSTを受け、カウンタ一致検出回路51~54からそれぞれ一致信号MTH1~MTH4を受ける。

【0184】
そして、スイッチング制御回路60は、検索開始信号SBおよびリセット信号RSTを受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0185】
また、スイッチング制御回路60は、一致信号MTH4をカウンタ一致検出回路54から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。スイッチング制御回路60は、この処理を1(=s-1=2-1)回実行する。

【0186】
更に、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。スイッチング制御回路60は、この処理を2(=s=2)回実行する。

【0187】
更に、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路53へ出力するとともに出力信号OUT3をマルチプレクサ63へ出力する。スイッチング制御回路60は、この処理を2(=s=2)回実行する。

【0188】
更に、スイッチング制御回路60は、一致信号MTH3をカウンタ一致検出回路53から受けると、クロック信号CLKに同期して、リセット信号RSTをカウント一致検出回路54へ出力するとともに出力信号OUT4をマルチプレクサ64へ出力する。スイッチング制御回路60は、この処理を2(=s=2)回実行する。

【0189】
マルチプレクサ61は、2個の距離信号D11,D15を受ける。そして、マルチプレクサ61は、1回目の出力信号OUT1をスイッチング制御回路60から受けると、距離信号D11をカウンタ一致検出回路51へ出力し、2回目の出力信号OUT1をスイッチング制御回路60から受けると、距離信号D15をカウンタ一致検出回路51へ出力する。

【0190】
マルチプレクサ62は、2個の距離信号D12,D16を受ける。そして、マルチプレクサ62は、1回目の出力信号OUT2をスイッチング制御回路60から受けると、距離信号D12をカウンタ一致検出回路52へ出力し、2回目の出力信号OUT2をスイッチング制御回路60から受けると、距離信号D16をカウンタ一致検出回路52へ出力する。

【0191】
マルチプレクサ63は、2個の距離信号D13,D17を受ける。そして、マルチプレクサ63は、1回目の出力信号OUT3をスイッチング制御回路60から受けると、距離信号D13をカウンタ一致検出回路53へ出力し、2回目の出力信号OUT3をスイッチング制御回路60から受けると、距離信号D17をカウンタ一致検出回路53へ出力する。

【0192】
マルチプレクサ64は、2個の距離信号D14,D18を受ける。そして、マルチプレクサ64は、1回目の出力信号OUT4をスイッチング制御回路60から受けると、距離信号D14をカウンタ一致検出回路54へ出力し、2回目の出力信号OUT4をスイッチング制御回路60から受けると、距離信号D18をカウンタ一致検出回路54へ出力する。

【0193】
カウンタ一致検出回路51は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路51は、距離信号D11をマルチプレクサ61から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。カウンタ一致検出回路51は、この処理を2個の距離信号D11,D15の全てについて実行する。

【0194】
また、カウンタ一致検出回路52は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路52は、距離信号D12をマルチプレクサ62から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。カウンタ一致検出回路52は、この処理を2個の距離信号D12,D16の全てについて実行する。

【0195】
更に、カウンタ一致検出回路53は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路53は、距離信号D13をマルチプレクサ63から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D13に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_3をカウントし、クロック数CN_3をカウントしたタイミングを示す一致信号MTH3をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路53は、動作を停止する。カウンタ一致検出回路53は、この処理を2個の距離信号D13,D17の全てについて実行する。

【0196】
更に、カウンタ一致検出回路54は、リセット信号RSTをスイッチング制御回路60から受けると駆動される。そして、カウンタ一致検出回路54は、距離信号D14をマルチプレクサ64から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D14に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_4をカウントし、クロック数CN_4をカウントしたタイミングを示す一致信号MTH4をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路54は、動作を停止する。

【0197】
そして、カウンタ一致検出回路54は、2回目のリセット信号RSTをスイッチング制御回路60から受け、距離信号D18をマルチプレクサ64から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D18に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_4をカウントし、クロック数CN_4をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。そして、カウンタ一致検出回路54は、動作を停止する。

【0198】
図16は、図15に示す距離/クロック数変換回路DC”-1の動作を説明するための図である。

【0199】
距離/クロック数変換回路DC~DC(=距離/クロック数変換回路DC”-1)の各々において、検索データに類似する参照データの検索が開始されると、スイッチング制御回路60は、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0200】
そして、マルチプレクサ61は、スイッチング制御回路60からの1回目の出力信号OUT1に応じて、距離信号D11(=“3”)をカウンタ一致検出回路51へ出力する。

【0201】
カウンタ一致検出回路51は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路51は、距離信号D11(=“3”)をマルチプレクサ61から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D11(=“3”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1(=“3”)をカウントし、クロック数CN_1(=“3”)をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0202】
その後、スイッチング制御回路60は、カウンタ一致検出回路51から一致信号MTH1を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。

【0203】
マルチプレクサ62は、スイッチング制御回路60からの1回目の出力信号OUT2に応じて、距離信号D12(=“2”)をカウンタ一致検出回路52へ出力する。

【0204】
カウンタ一致検出回路52は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路52は、距離信号D12(=“2”)をマルチプレクサ62から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D12(=“2”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2(=“2”)をカウントし、クロック数CN_2(=“2”)をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0205】
その後、スイッチング制御回路60は、カウンタ一致検出回路52から一致信号MTH2を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路53へ出力するとともに出力信号OUT3をマルチプレクサ63へ出力する。

【0206】
マルチプレクサ63は、スイッチング制御回路60からの1回目の出力信号OUT3に応じて、距離信号D13(=“5”)をカウンタ一致検出回路53へ出力する。

【0207】
カウンタ一致検出回路53は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路53は、距離信号D13(=“5”)をマルチプレクサ63から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D13(=“5”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_3(=“5”)をカウントし、クロック数CN_3(=“5”)をカウントしたタイミングを示す一致信号MTH3をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路53は、動作を停止する。

【0208】
その後、スイッチング制御回路60は、カウンタ一致検出回路53から一致信号MTH3を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路54へ出力するとともに出力信号OUT4をマルチプレクサ64へ出力する。

【0209】
マルチプレクサ64は、スイッチング制御回路60からの1回目の出力信号OUT4に応じて、距離信号D14(=“1”)をカウンタ一致検出回路54へ出力する。

【0210】
カウンタ一致検出回路54は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路54は、距離信号D14(=“1”)をマルチプレクサ64から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D14(=“1”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_4(=“1”)をカウントし、クロック数CN_4(=“1”)をカウントしたタイミングを示す一致信号MTH4をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路54は、動作を停止する。

【0211】
その後、スイッチング制御回路60は、カウンタ一致検出回路54から一致信号MTH4を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0212】
マルチプレクサ61は、スイッチング制御回路60からの2回目の出力信号OUT1に応じて、距離信号D15(=“2”)をカウンタ一致検出回路51へ出力する。

【0213】
カウンタ一致検出回路51は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路51は、距離信号D15(=“2”)をマルチプレクサ61から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D15(=“2”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1(=“2”)をカウントし、クロック数CN_1(=“2”)をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0214】
その後、スイッチング制御回路60は、カウンタ一致検出回路51から一致信号MTH1を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。

【0215】
マルチプレクサ62は、スイッチング制御回路60からの2回目の出力信号OUT2に応じて、距離信号D16(=“4”)をカウンタ一致検出回路52へ出力する。

【0216】
カウンタ一致検出回路52は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路52は、距離信号D16(=“4”)をマルチプレクサ62から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D16(=“4”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2(=“4”)をカウントし、クロック数CN_2(=“4”)をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0217】
その後、スイッチング制御回路60は、カウンタ一致検出回路52から一致信号MTH2を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路53へ出力するとともに出力信号OUT3をマルチプレクサ63へ出力する。

【0218】
マルチプレクサ63は、スイッチング制御回路60からの2回目の出力信号OUT3に応じて、距離信号D17(=“2”)をカウンタ一致検出回路53へ出力する。

【0219】
カウンタ一致検出回路53は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路53は、距離信号D17(=“2”)をマルチプレクサ63から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D17(=“2”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_3(=“2”)をカウントし、クロック数CN_3(=“2”)をカウントしたタイミングを示す一致信号MTH3をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路53は、動作を停止する。

【0220】
その後、スイッチング制御回路60は、カウンタ一致検出回路53から一致信号MTH3を受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路54へ出力するとともに出力信号OUT4をマルチプレクサ64へ出力する。

【0221】
マルチプレクサ64は、スイッチング制御回路60からの2回目の出力信号OUT4に応じて、距離信号D18(=“3”)をカウンタ一致検出回路54へ出力する。

【0222】
カウンタ一致検出回路54は、スイッチング制御回路60からのリセット信号RSTに応じて駆動される。そして、カウンタ一致検出回路54は、距離信号D18(=“3”)をマルチプレクサ64から受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、距離信号D18(=“3”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_4(=“3”)をカウントし、クロック数CN_4(=“3”)をカウントしたタイミングを示す一致信号MTH4をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路54は、動作を停止する。

【0223】
そうすると、スイッチング制御回路60は、カウンタ一致検出回路54からの2回目の一致信号MTH4に応じて、2回目の一致信号MTH4によって示されるタイミングと同じタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0224】
このように、カウンタ一致検出回路51~54は、それぞれ、距離信号D11~D14に一致するカウンタ値が得られたときのクロック信号CLKのクロック数CN_1~CN_4をカウントし、クロック数CN_1~CN_4をカウントしたタイミングを示す一致信号MTH1~MTH4を出力した後に、それぞれ、距離信号D15~D18に一致するカウンタ値が得られたときのクロック信号CLKのクロック数CN_1~CN_4をカウントし、クロック数CN_1~CN_4をカウントしたタイミングを示す一致信号MTH1~MTH4を出力する。

【0225】
つまり、カウンタ一致検出回路51~54の各々は、距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数をカウントし、そのクロック数をカウントしたタイミングを示す一致信号を出力する処理を2回繰り返し実行する。

【0226】
距離/クロック数変換回路DC~DCの各々が距離/クロック数変換回路DC”-1からなる場合も、距離/クロック数変換回路DC~DCの各々は、距離信号D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”の和(=“22”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(=“22”)をカウントし、クロック数(=“22”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0227】
図17は、図10に示す距離/クロック数変換回路DC”の更に別の具体的な構成を示す概略図である。

【0228】
図17を参照して、W=2=2=8からなり、s=2=2=4からなる場合、L=W/s=8/4=2であり、距離/クロック数変換回路DC”-2は、増幅器41,42と、カウンタ一致検出回路51,52と、スイッチ制御回路60と、マルチプレクサ61,62とを含む。

【0229】
マルチプレクサ61は、4個の距離演算回路DP11,DP13,DP15,DP17に対応して設けられ、マルチプレクサ62は、4個の距離演算回路DP12,DP14,DP16,DP18に対応して設けられる。

【0230】
カウンタ一致検出回路51は、マルチプレクサ61に対応して設けられ、カウンタ一致検出回路52は、マルチプレクサ62に対応して設けられる。

【0231】
スイッチング制御回路60は、連想メモリ100の制御回路から検索開始信号SBおよびリセット信号RSTを受ける。また、スイッチング制御回路60は、増幅器41,42からクロック信号CLKを受ける。更に、スイッチング制御回路60は、カウンタ一致検出回路51から一致信号MTH1を受け、カウンタ一致検出回路52から一致信号MTH2を受ける。

【0232】
そして、スイッチング制御回路60は、検索開始信号SBおよびリセット信号RSTを受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0233】
また、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0234】
更に、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに出力信号OUT2をマルチプレクサ62へ出力する。

【0235】
そして、スイッチング制御回路60は、s回目の一致信号MTH2をカウンタ一致検出回路52から受けると、s回目の一致信号MTH2によって示されるタイミングと同じタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0236】
マルチプレクサ61は、距離演算回路DP11,DP13,DP15,DP17からそれぞれ距離信号D11,D13,D15,D17を受け、出力信号OUT1をスイッチング制御回路60から受ける。

【0237】
そして、マルチプレクサ61は、1回目の出力信号OUT1を受けると、距離信号D11をカウンタ一致検出回路51へ出力し、2回目の出力信号OUT1を受けると、距離信号D13をカウンタ一致検出回路51へ出力し、3回目の出力信号OUT1を受けると、距離信号D15をカウンタ一致検出回路51へ出力し、4回目の出力信号OUT1を受けると、距離信号D17をカウンタ一致検出回路51へ出力する。

【0238】
また、マルチプレクサ62は、距離演算回路DP12,DP14,DP16,DP18からそれぞれ距離信号D12,D14,D16,D18を受け、出力信号OUT2をスイッチング制御回路60から受ける。

【0239】
そして、マルチプレクサ62は、1回目の出力信号OUT2を受けると、距離信号D12をカウンタ一致検出回路52へ出力し、2回目の出力信号OUT2を受けると、距離信号D14をカウンタ一致検出回路52へ出力し、3回目の出力信号OUT2を受けると、距離信号D16をカウンタ一致検出回路52へ出力し、4回目の出力信号OUT2を受けると、距離信号D18をカウンタ一致検出回路52へ出力する。

【0240】
カウンタ一致検出回路51は、マルチプレクサ61から距離信号D11を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D11に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0241】
また、カウンタ一致検出回路51は、マルチプレクサ61から距離信号D13を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D13に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0242】
更に、カウンタ一致検出回路51は、マルチプレクサ61から距離信号D15を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D15に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0243】
更に、カウンタ一致検出回路51は、マルチプレクサ61から距離信号D17を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D17に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0244】
このように、カウンタ一致検出回路51は、距離信号とリセット信号とを受けるごとに、距離信号(=距離信号D11から奇数番目の距離信号D11,D13,D15,D17のいずれか)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1をスイッチング制御回路60へ出力し、その後、動作を停止する。

【0245】
カウンタ一致検出回路52は、マルチプレクサ62から距離信号D12を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D12に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0246】
また、カウンタ一致検出回路52は、マルチプレクサ62から距離信号D14を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D14に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0247】
更に、カウンタ一致検出回路52は、マルチプレクサ62から距離信号D16を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D16に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0248】
更に、カウンタ一致検出回路52は、マルチプレクサ62から距離信号D18を受け、リセット信号RSTをスイッチング制御回路60から受けると、上述した方法によって、距離信号D18に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0249】
このように、カウンタ一致検出回路52は、距離信号とリセット信号とを受けるごとに、距離信号(=距離信号D11から偶数番目の距離信号D12,D14,D16,D18のいずれか)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2をスイッチング制御回路60へ出力し、その後、動作を停止する。

【0250】
図18は、図17に示す距離/クロック数変換回路DC”-2の動作を説明するための図である。

【0251】
図18を参照して、スイッチング制御回路60は、連想メモリ100の制御回路からの検索開始信号SBおよびリセット信号RSTに応じて、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに出力信号OUT1をマルチプレクサ61へ出力する。

【0252】
マルチプレクサ61は、距離演算回路DP11,DP13,DP15,DP17からそれぞれ距離信号D11,D13,D15,D17を受ける。そして、マルチプレクサ61は、1回目の出力信号OUT1に応じて、距離信号D11をカウンタ一致検出回路51へ出力する。

【0253】
そうすると、カウンタ一致検出回路51は、距離信号D11(=“3”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1(=“3”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN_1(=“3”)をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0254】
その後、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに、出力信号OUT2をマルチプレクサ62へ出力する。

【0255】
マルチプレクサ62は、距離演算回路DP12,DP14,DP16,DP18からそれぞれ距離信号D12,D14,D16,D18を受ける。そして、マルチプレクサ62は、1回目の出力信号OUT2に応じて、距離信号D12(=“2”)をカウンタ一致検出回路52へ出力する。

【0256】
そうすると、カウンタ一致検出回路52は、距離信号D12(=“2”)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2(=“2”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN_2(=“2”)をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0257】
引き続いて、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに、出力信号OUT1をマルチプレクサ61へ出力する。

【0258】
マルチプレクサ61は、2回目の出力信号OUT1に応じて、距離信号D13(=“5”)をカウンタ一致検出回路51へ出力する。

【0259】
そうすると、カウンタ一致検出回路51は、距離信号D13(=“5”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1(=“5”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN_1(=“5”)をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0260】
スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに、出力信号OUT2をマルチプレクサ62へ出力する。

【0261】
マルチプレクサ62は、2回目の出力信号OUT2に応じて、距離信号D14(=“1”)をカウンタ一致検出回路52へ出力する。

【0262】
そうすると、カウンタ一致検出回路52は、距離信号D14(=“1”)に一致するカウンタ値CV12が得られるときのクロック数CN_2(=“1”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN_2(=“1”)をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0263】
そして、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに、出力信号OUT1をマルチプレクサ61へ出力する。

【0264】
マルチプレクサ61は、3回目の出力信号OUT1に応じて、距離信号D15(=“2”)をカウンタ一致検出回路51へ出力する。

【0265】
そうすると、カウンタ一致検出回路51は、距離信号D15(=“2”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1(=“2”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN_1(=“2”)をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0266】
そして、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに、出力信号OUT2をマルチプレクサ62へ出力する。

【0267】
マルチプレクサ62は、3回目の出力信号OUT2に応じて、距離信号D16(=“4”)をカウンタ一致検出回路52へ出力する。

【0268】
そうすると、カウンタ一致検出回路52は、距離信号D16(=“4”)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2(=“4”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN_2(=“4”)をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0269】
そして、スイッチング制御回路60は、一致信号MTH2をカウンタ一致検出回路52から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路51へ出力するとともに、出力信号OUT1をマルチプレクサ61へ出力する。

【0270】
マルチプレクサ61は、4回目の出力信号OUT1に応じて、距離信号D17(=“2”)をカウンタ一致検出回路51へ出力する。

【0271】
そうすると、カウンタ一致検出回路51は、距離信号D17(=“2”)に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数CN_1(=“2”)をカウントする。そして、カウンタ一致検出回路51は、クロック数CN_1(=“2”)をカウントしたタイミングを示す一致信号MTH1をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51は、動作を停止する。

【0272】
その後、スイッチング制御回路60は、一致信号MTH1をカウンタ一致検出回路51から受けると、クロック信号CLKに同期して、リセット信号RSTをカウンタ一致検出回路52へ出力するとともに、出力信号OUT2をマルチプレクサ62へ出力する。

【0273】
マルチプレクサ62は、4回目の出力信号OUT2に応じて、距離信号D18(=“3”)をカウンタ一致検出回路52へ出力する。

【0274】
そうすると、カウンタ一致検出回路52は、距離信号D18(=“3”)に一致するカウンタ値CV12が得られるときのクロック信号CLKのクロック数CN_2(=“3”)をカウントする。そして、カウンタ一致検出回路52は、クロック数CN_2(=“3”)をカウントしたタイミングを示す一致信号MTH2をクロック信号CLKに同期してスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路52は、動作を停止する。

【0275】
そうすると、スイッチング制御回路60は、カウンタ一致検出回路52からの4回目の一致信号MTH2に応じて、4回目の一致信号MTH2によって示されるタイミングと同じタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0276】
このように、カウンタ一致検出回路51,52は、交互に、それぞれ、距離信号(=距離信号D11から奇数番目の距離信号D11,D13,D15,D17のいずれか)および距離信号(=距離信号D11から偶数番目の距離信号D12,D14,D16,D18のいずれか)に一致するカウンタ値CV11,CV12が得られるときのクロック信号CLKのクロック数CN_1,CN_2をカウントし、クロック数CN_1,CN_2をカウントしたタイミングを示す一致信号MTH1,MTH2をスイッチング制御回路60へ出力する。そして、カウンタ一致検出回路51,52は、この処理を4(=s)回繰り返し実行する。

【0277】
距離/クロック数変換回路DC~DCの各々が距離/クロック数変換回路DC”-2からなる場合も、距離/クロック数変換回路DC~DCの各々は、距離信号D11=“3”,D12=“2”,D13=“5”,D14=“1”,D15=“2”,D16=“4”,D17=“2”,D18=“3”の和(=“22”)に一致するカウンタ値が得られるときのクロック信号CLKのクロック数(=“22”)をカウントし、クロック数(=“22”)をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0278】
上記においては、W=8である場合について説明したが、Wは、2を満たせば、8以外の値であってもよい。

【0279】
そして、Wが2を満たす8以外の値であるときも、距離/クロック数変換回路DC~DCは、それぞれ、上述した動作と同じ動作によってタイミング信号C~CをWinner検出器20へ出力する。

【0280】
また、上記においては、s=2,4の場合について説明したが、sは、W以下の2を満たす整数であれば、2,4以外の値からなっていてもよく、その場合も、距離/クロック数変換回路DC~DCは、それぞれ、上述した動作と同じ動作によってタイミング信号C~CをWinner検出器20へ出力する。

【0281】
上述したように、図13および図17においては、距離/クロック数変換回路DC~DC(=距離/クロック数変換回路DC’-2,DC”-2)の各々が2つのカウンタ一致検出回路51,52からなる場合について説明した。

【0282】
そして、距離/クロック数変換回路DC~DCの各々が図13に示す距離/クロック数変換回路DC’-2または図17に示す距離/クロック数変換回路DC”-2からなる場合、カウンタ一致検出回路51は、W個の距離信号(=距離信号D11~D1W等)を一列に配列したときの一方端からp(pは1≦p<Wを満たす奇数)番目の距離信号を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、p番目の距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_1をカウントし、クロック数CN_1をカウントしたタイミングを示す一致信号MTH1を出力する一致処理をW/2回繰り返し実行する。

【0283】
また、カウンタ一致検出回路52は、W個の距離信号(=距離信号D11~D1W等)を一列に配列したときの一方端からq(qは1<q≦Wを満たす偶数)番目の距離信号を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、q番目の距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示す一致信号MTH2を出力する一致処理を((W/2)-1)回繰り返し実行し、一致信号MTH1をW/2回受け、かつ、W番目の距離信号を受けると、カウンタ値をクロック信号CLKに同期して昇順にカウントしたときに、W番目の距離信号に一致するカウンタ値が得られるときのクロック信号CLKのクロック数CN_2をカウントし、クロック数CN_2をカウントしたタイミングを示すタイミング信号(=タイミング信号C~Cのいずれか)をWinner検出器20へ出力する。

【0284】
この場合、カウンタ一致検出回路51は、「第1のカウンタ一致検出回路」を構成し、カウンタ一致検出回路52は、「第2のカウンタ一致検出回路」を構成する。

【0285】
また、カウンタ一致検出回路51のカウンタ311(またはカウンタ311A)は、「第1のカウンタ」を構成し、カウンタ一致検出回路51の一致検出回路312は、「第1の一致検出回路」を構成する。

【0286】
更に、カウンタ一致検出回路52のカウンタ311(またはカウンタ311A)は、「第2のカウンタ」を構成し、カウンタ一致検出回路52の一致検出回路312は、「第2の一致検出回路」を構成する。

【0287】
図13および図17に示すように、距離/クロック数変換回路DC~DC(=距離/クロック数変換回路DC’-2,DC”-2)の各々を2個のカウンタ一致検出回路51,52によって構成することによって、距離/クロック数変換回路DC~DCの回路面積を削減でき、消費電力を低減できる。

【0288】
図19は、最短検索時間の比較を示す図である。図19における周波数マッピング型とは、検索データと参照データとの距離を周波数に変換して検索データに類似する参照データを検索する連想メモリを意味する。

【0289】
また、図19の(a)は、M×W=16ビット×8ユニット=128ビットの参照データを64個用いた場合の最短検索時間の比較を示す。更に、図19の(b)は、M×W=16ビット×16ユニット=256ビットの参照データを64個用いた場合の最短検索時間の比較を示す。

【0290】
図19の(a)を参照して、M×W=16ビット×8ユニット=128ビットの参照データを64個用いた場合、周波数マッピング型の連想メモリにおいては、最短検索時間が1280(ns)であるのに対し、本発明の連想メモリ100においては、最短検索時間が20(ns)である。

【0291】
図19の(b)を参照して、M×W=16ビット×16ユニット=256ビットの参照データを64個用いた場合、周波数マッピング型の連想メモリにおいては、最短検索時間が210000(ns)であるのに対し、本発明の連想メモリ100においては、最短検索時間が40(ns)である。

【0292】
このように、この発明の実施の形態による連想メモリ100は、従来の周波数マッピング型の連想メモリよりも2桁以上短い時間で検索データに類似する参照データを検索できることが実験的に実証された。

【0293】
また、この発明の実施の形態による連想メモリ100は、参照データのビット数が多くなるに従って、検索時間を飛躍的に短くできることが実験的に実証された。

【0294】
図20は、消費電力の比較を示す図である。図20において、従来例の連想メモリは、非特許文献3に記載された連想メモリである。

【0295】
図20を参照して、従来例の連想メモリにおいては、64個の参照データが用いられ、本発明の連想メモリ100においては、128個の参照データが用いられた。

【0296】
そして、従来例の連想メモリにおいては、消費電力は、321(mW)であるのに対し、本発明の連想メモリ100においては、消費電力は、2.13(mW)である。

【0297】
このように、この発明の実施の形態による連想メモリ100は、参照データ数が2倍多いにも拘わらず、従来例の連想メモリよりも2桁以上消費電力を低減できることが実験的に実証された。

【0298】
従って、この発明の実施の形態による連想メモリ100を用いれば、低消費電力で高速に検索データに類似する参照データを検索できることが明らかである。

【0299】
なお、上記においては、マンハッタン距離を用いて検索データに類似するk個の参照データを検索すると説明したが、この発明の実施の形態においては、これに限らず、ハミング距離を用いて検索データに類似するk個の参照データを検索してもよい。

【0300】
この場合、Mビットは、1ビットからなり、参照データ保存回路SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRWの各々は、1ビットの参照データを保存する。また、距離演算回路DP11~DP1W,DP21~DP2W,・・・,DPR1~DPRWの各々は、検索データの1ビットと参照データの1ビットとの距離を式(1)に従って演算する。

【0301】
そして、連想メモリ100は、上述した動作に従って、ハミング距離を用いて検索データに類似するk個の参照データを検索する。

【0302】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【0303】
この発明は、連想メモリに適用される。
【符号の説明】
【0304】
1 メモリ部、2 行デコーダ、3 列デコーダ、4 読出/書込回路、5 検索データ保存回路、10 メモリアレイ部、20 Winner検出器、21~2W,41~4L 増幅器、31~3W,51~5L カウンタ一致検出回路、60 スイッチング制御回路、61~6L マルチプレクサ、100 連想メモリ、311,311A カウンタ、312 一致検出回路、311-1~311-M 分周器、SC11~SC1W,SC21~SC2W,・・・,SCR1~SCRW 参照データ保存回路、DP11~DP1W,DP21~DP2W,・・・,DPR1~DPRW 距離演算回路、DC~DC 距離/クロック数変換回路。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19