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

明細書 :連想メモリ

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第6085187号 (P6085187)
公開番号 特開2014-154196 (P2014-154196A)
登録日 平成29年2月3日(2017.2.3)
発行日 平成29年2月22日(2017.2.22)
公開日 平成26年8月25日(2014.8.25)
発明の名称または考案の名称 連想メモリ
国際特許分類 G11C  15/04        (2006.01)
FI G11C 15/04 631F
請求項の数または発明の数 5
全頁数 41
出願番号 特願2013-025465 (P2013-025465)
出願日 平成25年2月13日(2013.2.13)
新規性喪失の例外の表示 特許法第30条第2項適用 1.研究集会名 VDECデザイナーズフォーラム2012 2.開催日(発明を発表した日) 平成24年 8月26日
審査請求日 平成27年10月6日(2015.10.6)
特許権者または実用新案権者 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
発明者または考案者 【氏名】マタウシュ ハンスユルゲン
【氏名】佐々木 静龍
【氏名】赤澤 智信
個別代理人の代理人 【識別番号】100104444、【弁理士】、【氏名又は名称】上羽 秀敏
【識別番号】100112715、【弁理士】、【氏名又は名称】松山 隆夫
【識別番号】100125704、【弁理士】、【氏名又は名称】坂根 剛
【識別番号】100120662、【弁理士】、【氏名又は名称】川上 桂子
【識別番号】100140327、【弁理士】、【氏名又は名称】大塚 千秋
審査官 【審査官】滝谷 亮一
参考文献・文献 特開2011-076688(JP,A)
特開2007-080375(JP,A)
特開昭56-019182(JP,A)
調査した分野 G11C 15/04
特許請求の範囲 【請求項1】
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すR×W個の絶対値差を、前記検索データと前記参照データの距離として算出する第1距離算出手段と、
前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記R個の参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
【請求項2】
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記各参照データにつき、前記W個の絶対値差の各々に一致する回数だけ、前記絶対値差と一致するクロック数を検出する処理を繰り返すことにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。
【請求項3】
前記各参照データにつき、前記第1距離算出手段で算出された前記W個の絶対値差の各々の二乗値を算出することにより、前記検索対象の検索データと前記参照データとの距離として、前記W個の絶対値差の二乗値を算出する第2距離算出手段を更に備え、
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記参照データごとに、前記第2距離算出手段で算出された前記W個の前記絶対値差の二乗値の和に一致するクロック数を検出することにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。
【請求項4】
マンハッタン距離とユークリッド距離のいずれかの距離を選択する選択手段を備え、
前記タイミング信号出力手段は、
(1)前記選択手段によって前記マンハッタン距離が選択された場合、前記各参照データにつき、前記W個の絶対値差の和に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力し、
(2)前記選択手段によって前記ユークリッド距離が選択された場合、前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力する
請求項1から請求項3のいずれか一項に記載の連想メモリ。


【請求項5】
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとのR×W個の距離を算出する距離算出手段と、
前記参照データごとに、前記距離算出手段で算出された距離を表すビットのうち、設定された対象ビットの値と一致するクロック数を検出したタイミングで一致検出信号を出力する一致検出手段と、
前記各参照データについて算出された前記距離を表す最上位ビットから順に、予め定められたビット単位に前記対象ビットを設定し、いずれかの前記参照データについて、前記対象ビットに対する前記一致検出信号が出力される毎に、前記対象ビットを拡張するビット設定手段と、
前記各参照データについて、前記距離を表す全てのビットに対する前記一致検出信号が出力されたタイミングを示すタイミング信号を出力する処理を、R個の前記参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
発明の詳細な説明 【技術分野】
【0001】
この発明は、連想メモリに関するものである。
【背景技術】
【0002】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated circuit)上で実現することにより、将来、人工知能およびモバイル機器等の高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【0003】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【0004】
前者は、CAM(Content 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 SearchRange Based on Manhattan Distance,”CICC, 2004.
【発明の概要】
【発明が解決しようとする課題】
【0007】
非特許文献1に記載の連想メモリは、検索データと参照データとのハミング距離を用いて類似検索を行うものである。そのため、非特許文献1に記載の連想メモリにおいて、ユークリッド距離を用いて類似検索を行うことは困難である。非特許文献2に記載の連想メモリは、検索データと参照データとの類似度を表す距離を電圧に変換するため、誤検索が生じやすい。
【0008】
そこで、本発明は、かかる問題を解決するためになされたものであり、その目的は、ユークリッド距離を用いた場合でも正確に類似検索を行うことが可能な連想メモリを提供することである。
【課題を解決するための手段】
【0009】
この発明の実施の形態による連想メモリは、各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すR×W個の絶対値差を、前記検索データと前記参照データの距離として算出する第1距離算出手段と、前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記R個の参照データについて行うタイミング信号出力手段と、前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、を備える。
【発明の効果】
【0010】
この発明の実施の形態による連想メモリにおいては、タイミング信号出力手段は、第1距離算出手段で算出された、各参照データと検索データとの絶対値差を用いて、参照データごとに、検索データとのユークリッド距離に一致するクロック数を検出したタイミングでタイミング信号を出力する。すなわち、タイミング信号出力手段は、各参照データについて算出された絶対値差を、参照データと検索データとのユークリッド距離に相当するクロック数に変換し、変換したクロック数が得られるタイミングでタイミング信号を出力する。その結果、参照データと検索データとのユークリッド距離の大きさに応じて、その参照データのタイミング信号の出力タイミングが決まり、各参照データについて、ユークリッド距離を用いた検索を適切に行うことができる。
【0011】
従って、本発明の実施の形態によれば、ユークリッド距離を用いた場合でも正確に類似検索を行うことができる。
【図面の簡単な説明】
【0012】
【図1】第1実施形態に係る連想メモリの構成を示す概略ブロック図である。
【図2A】図2Aは、図1に示す距離/クロック数変換回路の構成を示す概略図である。
【図2B】図2Bは、図2Aに示すカウンタ一致検出回路の構成例を示す概略図である。
【図3】図3は、図1に示すWinner検出器の動作を説明するための図である。
【図4】図4は、第2実施形態における距離/クロック数変換回路の構成を示す概略図である。
【図5A】図5Aは、第1、第2実施形態の場合の検索時間を表す図である。
【図5B】図5Bは、第3実施形態の場合の検索時間を表す図である。
【図6】図6は、第3実施形態に係る連想メモリの構成を示す概略ブロック図である。
【図7】図7は、図6に示す距離/クロック数変換回路の構成例を示す概略図である。
【図8】図8は、図7に示すカウンタ一致検出回路の構成例を示す概略図である。
【図9A】図9Aは、図8に示すカウンタと一致検出回路の構成例を示す概略図である。
【図9B】図9Bは、図9Aに示すカウンタの動作例を示す図である。
【図10A】図10Aは、第3実施形態における距離/クロック数変換回路の動作例を説明する図である。
【図10B】図10Bは、図10Aに示す例におけるカウンタの動作例を示す図である。
【図10C】図10Cは、図10Aに示す例におけるカウンタの動作例を示す図である。
【図10D】図10Dは、図10Aに示す例におけるカウンタの動作例を示す図である。
【図11】図11は、第4実施形態における距離演算回路の回路構成例を示す概略図である。
【図12】図12は、図11に示す演算回路の回路構成例を示す概略図である。
【図13】図13は、第4実施形態における二乗計算の処理過程を説明する図である。
【図14】図14は、第4実施形態におけるカウンタ一致検出回路の構成例を示す概略図である。
【図15】図15は、変形例(1)における距離/クロック数変換回路の構成例を示す概略図である。
【発明を実施するための形態】
【0013】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。

【0014】
<第1実施形態>
図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】
JP0006085187B2_000002t.gif

【0024】
式(1)において、Drj(r=1~R,j=1~W)は、参照データと検索データとの距離(絶対値差)を表す。nMrは参照データと検索データとのマンハッタン距離を示している。また、式(1)において、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を受け、各距離信号D1jの二乗値の和に相当するクロック信号CLKのクロック数CN_total1を後述する方法によってカウントする。そして、そのクロック数CN_total1をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。

【0028】
距離/クロック数変換回路DCは、距離演算回路DP21~DP2WからW個の距離信号D2jを受け、各距離信号D2jの二乗値の和に相当するクロック信号CLKのクロック数CN_total2を後述する方法によってカウントする。そして、そのクロック数CN_total2をカウントしたタイミングを示すタイミング信号CをWinner検出器20へ出力する。

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

【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】
図2Aは、図1に示す距離/クロック数変換回路DCの構成を表す概略構成図である。なお、図1に示す距離/クロック数変換回路DC~距離/クロック数変換回路DCの各々も、図2Aに示す距離/クロック数変換回路DCと同様の構成を有する。図2Aに示すように、距離/クロック数変換回路DCは、バッファ21~2Wと、カウンタ一致検出回路31~3Wとを含む。

【0034】
バッファ21は、連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、連想メモリ100に内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受ける。そして、バッファ21は、検索開始信号SBがL(Low)レベルからH(High)レベルに切り替わると、その受けたクロック信号CLKをバッファ22およびカウンタ一致検出回路31へ出力する。バッファ22は、クロック信号CLKをバッファ21から受け、カウンタ一致検出回路31から、後述するHレベルの一致信号(DETECT1)を受けると、クロック信号CLKをバッファ23(図示せず)及びカウンタ一致検出回路32へ出力する。以下、同様にして、バッファ2Wは、クロック信号CLKをバッファ2W-1(図示せず)から受け、カウンタ一致検出回路3W-1(図示せず)から、後述するHレベルの一致信号(DETECTW-1)を受けると、クロック信号CLKをカウンタ一致検出回路3Wへ出力する。

【0035】
カウンタ一致検出回路31~3Wは、それぞれ、距離演算回路DP11~DP1Wに対応して設けられる。そして、カウンタ一致検出回路31~3Wは、直列に接続される。ここで、カウンタ一致検出回路31~3Wの概略構成について説明する。

【0036】
図2Bは、距離/クロック数変換回路DCにおけるカウンタ一致検出回路31~3Wの構成例を示す図である。図2Bの例では、W=2の場合を示している。カウンタ一致検出回路31は、クロック数変換回路31aと、カウンタ31bと、一致検出回路31cとを含む。カウンタ一致検出回路32は、クロック数変換回路32aと、カウンタ32bと、一致検出回路32cとを含む。以下、各構成の機能について説明する。

【0037】
クロック数変換回路31aは、距離演算回路DP11からMビットのビット長を有する距離信号D11と、バッファ21からのクロック信号CLKとを受ける。クロック数変換回路31aは、クロック信号CLKのクロック数をカウントし、距離信号D11が示す距離と一致するクロック数を検出したタイミングで、カウンタ31bにHレベルの一致検出信号をカウンタ31bへ出力する処理を行う。クロック数変換回路31aは、後述の一致検出回路31cからHレベルの一致信号(DETECT1)が出力されるまで、この処理を繰り返し行い、Hレベルの一致信号(DETECT1)が出力されると動作を停止する。

【0038】
カウンタ31bは、クロック数変換回路31aからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウンタ値を一致検出回路31cへ出力する。

【0039】
一致検出回路31cは、カウンタ31bからカウンタ値を受け、距離演算回路DP11からMビットのビット長を有する距離信号D11を受ける。一致検出回路31cは、距離信号D11が示す距離とカウンタ値とを比較し、距離信号D11が示す距離とカウンタ値とが一致するときに、Hレベルの一致信号(DETECT1)をクロック数変換回路31aとバッファ22へ出力する。一致検出回路31cは、距離信号D11が示す距離とカウンタ値とが一致しないときは、Lレベルの一致信号(DETECT1)をクロック数変換回路31aとバッファ22へ出力する。

【0040】
クロック数変換回路32aは、バッファ22からクロック信号CLKを受けると駆動する。クロック数変換回路32aは、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。クロック数変換回路31aと同様、クロック数変換回路32aは、クロック信号CLKのクロック数をカウントし、距離信号D12が示す距離と一致するクロック数を検出したタイミングで、カウンタ32bにHレベルの一致検出信号を出力する処理を行う。クロック数変換回路32aは、後述の一致検出回路32cからHレベルの一致信号(DETECT2)が出力されるまで、この処理を繰り返し行う。クロック数変換回路32aは、Hレベルの一致信号(DETECT2)が出力されると動作を停止する。

【0041】
カウンタ32bは、クロック数変換回路32aからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウンタ値を一致検出回路32cへ出力する。

【0042】
一致検出回路32cは、カウンタ32bからカウンタ値を受け、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。一致検出回路32cは、距離信号D12が示す距離とカウンタ値とを比較し、距離信号D12が示す距離とカウンタ値とが一致するときに、Hレベルの一致信号(DETECT2)をクロック数変換回路32aに出力するとともに、Hレベルの一致信号(DETECT2)をタイミング信号CとしてWinner検出器20へ出力する。また、一致検出回路32cは、距離信号D12が示す距離とカウンタ値とが一致するときに、Lレベルの一致信号(DETECT2)をクロック数変換回路32aに出力する。

【0043】
ここで、例えば、距離演算回路DP11から距離「2」を示すMビットの距離信号D11が出力され、距離演算回路DP12から距離「3」を示すMビットの距離信号D12が出力された場合の動作例について説明する。

【0044】
クロック数変換回路31aは、距離「2」を示すMビットの距離信号D11を受け、バッファ21からのクロック信号CLKのクロックに同期して、距離「2」に一致するクロック数をカウントする。クロック数変換回路31aは、カウントしたクロック数と距離とが一致すると、Hレベルの一致検出信号を出力する。カウンタ31bは、一致検出信号が立ち上がると、カウンタ値をカウントアップし、「1」を示すカウンタ値を一致検出回路31cに出力する。このとき、距離信号D11が示す距離「2」とカウンタ値「1」とが一致しないため、一致検出回路31cからLレベルの一致信号(DETECT1)が出力される。

【0045】
クロック数変換回路31aは、出力した一致検出信号がLレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路31aは、再びクロック信号CLKのクロック数をカウントし、カウントしたクロック数が距離「2」と一致すると、カウンタ31bにHレベルの一致検出信号を出力する。カウンタ31bは、一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路31cに「2」を示すカウンタ値を出力する。一致検出回路31cは、距離信号D11が示す距離「2」とカウンタ値「2」とが一致するため、一致信号(DETECT1)をバッファ22とクロック数変換回路31aに出力する。つまり、検索開始からのクロック数が「4」となるタイミングで、Hレベルの一致信号(DETECT1)が出力される。そして、クロック数変換回路31aは、Hレベルの一致信号(DETECT1)に応じて動作を停止する。

【0046】
バッファ22は、一致検出回路31cからHレベルの一致信号(DETECT1)を受けて、クロック数変換回路32aにクロック信号CLKを出力する。クロック数変換回路32aは、バッファ22からのクロック信号CLKのクロックに同期して、クロック信号CLKのクロック数をカウントする。クロック数変換回路32aは、距離「3」を示すMビットの距離信号D12を受け、カウントしたクロック数が距離「3」と一致するタイミングで、Hレベルの一致検出信号をカウンタ32bに出力する。カウンタ32bは、クロック数変換回路32aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路32cに「1」を示すカウンタ値を出力する。このとき、距離「3」とカウンタ値「1」とが一致しないため、一致検出回路32cからLレベルの一致信号(DETECT2)が出力される。

【0047】
クロック数変換回路32aは、出力した一致検出信号がLレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路32aは、再びクロック信号CLKのクロック数をカウントし、カウントしたクロック数が距離「3」と一致すると、カウンタ32bにHレベルの一致検出信号を出力する。カウンタ32bは、クロック数変換回路32aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路32cに「2」を示すカウンタ値を出力する。このとき、距離「3」とカウンタ値「2」とが一致しないため、一致検出回路32cからLレベルの一致信号(DETECT2)が出力される。

【0048】
クロック数変換回路32aは、一致検出信号がLレベルになると、再びカウントしたクロック数をリセットしてクロック信号CLKをカウントし、カウントしたクロック数が距離「3」と一致すると、カウンタ32bにHレベルの一致検出信号を出力する。そして、クロック数変換回路32aは、Hレベルの一致信号(DETECT2)に応じて動作を停止する。カウンタ32bは、クロック数変換回路32aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路32cに「3」を示すカウンタ値を出力する。一致検出回路32cは、距離「3」とカウンタ値「3」とが一致するため、Hレベルの一致信号(DETECT2)をクロック数変換回路32aに出力するとともに、タイミング信号CとしてWinner検出器20に出力する。つまり、クロック数変換回路32aにおいてカウントされたクロック数は「9(=3+3+3)」であり、検索開始からクロック数「13(=4+9)」のタイミングでタイミング信号Cが出力される。

【0049】
カウンタ一致検出回路31,32全体でカウントされるクロック数CN_total1「13」は、カウンタ一致検出回路31においてカウントするクロック数「4(=2+2)」と、カウンタ一致検出回路32においてカウントするクロック数「9(=3+3+3)」とを加算したものである。つまり、カウンタ一致検出回路31,32によって、距離「2」の二乗値と距離「3」の二乗値との和に一致するクロック数をカウントすることに相当する。

【0050】
距離/クロック数変換回路DCは、一般的に、W個の距離信号D11~D1Wを受ける。そして、W個の距離信号D11~D1Wの各々は、Mビットのビット長を有する。従って、距離/クロック数変換回路DCは、M×Wビットのビット長を有する距離信号D1112・・・D1Wを受ける。カウンタ一致検出回路31において、距離信号D11が示す距離に一致する回数分だけ、その距離に一致するクロック数を繰り返しカウントする。また、カウンタ一致検出回路32~3Wは、それぞれ、カウンタ一致検出回路31~3W-1から一致信号を受けた後に、距離信号D12~D1Wにそれぞれ一致するクロック数を、その距離に一致する回数だけ繰り返しカウントする。その結果、距離/クロック数変換回路DCにおいてカウントされる全体のクロック数CN_total1は、カウンタ一致検出回路31~3Wの各々においてカウントされたクロック数の和に等しい。カウンタ一致検出回路31~3Wの各々においてカウントされたクロック数は、それぞれ、距離信号D11~D1Wが示す各距離の二乗値に相当するため、距離/クロック数変換回路DCにおいてカウントされる全体のクロック数CN_totalRは、各距離信号D11~D1Wの二乗値の和を表している。

【0051】
ここで、ユークリッド距離nは、次式によって表わされる。

【0052】
【数2】
JP0006085187B2_000003t.gif

【0053】
式(2)の右辺の|In-Rerjは、式(1)の右辺の|In-Rerj|において、検索データと参照データとの距離の二乗値に一致する。従って、ユークリッド距離nErの演算は、上述したように、式(1)によって演算したW個の各距離について、距離に一致するクロック数をカウントする処理を距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図2Bの例において、カウンタ一致検出回路32が、カウンタ一致検出回路31,32全体でカウントしたクロック数のタイミングを示すタイミング信号Cを出力することは、ユークリッド距離nErによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示すWinner信号を出力することに相当する。なお、距離/クロック数変換回路DC~DCの各々も、距離/クロック数変換回路DCの動作と同じ動作によって、それぞれ、タイミング信号C~Cを出力する。

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

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

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

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

【0058】
距離/クロック数変換回路DC~DCの動作は、クロック信号CLKに同期して実行される。そのため、クロック信号CLKの周波数を高くすることで、連想メモリ100の動作を高速化してもよい。本実施形態では、クロック数変換回路31a,32aは、一致信号(DETECT1,DETECT2)がそれぞれ出力されると動作を停止する。そのため、距離/クロック数変換回路DCにおいて、全ての距離が一致するまでクロック数変換回路DCi1~DCiRを動作させる場合と比べて消費電力を小さくすることができる。

【0059】
<第2実施形態>
本実施形態では、第1実施形態で説明した距離/クロック数変換回路とは異なる構成によって、ユークリッド距離を用いた検索を行う例について説明する。

【0060】
図4は、本実施形態における距離/クロック数変換回路DCの構成例を示す概略構成図である。図4において、第1実施形態と同様の構成については、第1実施形態と同様の符号を付している。図4の例では、W=2の場合の距離/クロック数変換回路DCの構成例を示している。なお、距離/クロック数変換回路DC~DCについても同様の構成を有する。

【0061】
図4に示すように、距離/クロック数変換回路DCは、バッファ23、距離/クロック数変換ユニット310,320、及び、カウンタ一致検出ユニット300を含む。

【0062】
バッファ23は、連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、連想メモリ100に内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受ける。そして、バッファ23は、検索開始信号SBがLレベルからHレベルに切り替わると、その受けたクロック信号CLKを距離/クロック数変換ユニット310,320へ出力する。

【0063】
距離/クロック数変換ユニット310,320は、距離演算回路DP11,DP12にそれぞれ対応して設けられる。距離/クロック数変換ユニット310は、クロック数変換回路31a、デマルチプレクサ31d、OR回路31e、及び一致検出回路31c’を含む。距離/クロック数変換ユニット320は、クロック数変換回路32a、デマルチプレクサ32d、OR回路32e、及び一致検出回路32c’を含む。カウンタ一致検出ユニット300は、デマルチプレクサ300a、カウンタ300b、及び、AND回路300cを含む。

【0064】
デマルチプレクサ31dは、連想メモリ100の制御回路(図示せず)からイネーブル信号(EN)を受け、後述の一致検出回路31c’から一致信号(DETECT1)を受ける。デマルチプレクサ31dは、Lレベルの一致信号(DETECT1)を受けると、クロック数変換回路31aにHレベル(=1)のEN信号を出力し、OR回路31eにLレベル(=0)のEN信号を出力する。また、デマルチプレクサ31dは、Hレベルの一致信号(DETECT1)を受けると、クロック数変換回路31aにLレベルのEN信号を出力し、OR回路31eにHレベルのEN信号を出力する。

【0065】
クロック数変換回路31aは、距離演算回路DP11からMビットの距離信号D11を受け、バッファ23からクロック信号CLKを受ける。クロック数変換回路31aは、デマルチプレクサ31dからHレベルのEN信号を受けると、クロック信号CLKのクロック数をカウントし、カウントしたクロック数と距離信号D11が示す距離との一致を検出する。クロック数変換回路31aは、カウントしたクロック数と距離信号D11が示す距離とが一致するタイミングで、OR回路31eに「1」を示すHレベルの一致検出信号を出力する。また、クロック数変換回路31aは、後述のデマルチプレクサ300aから出力される信号を受け、その信号を受けたタイミングでカウントしたクロック数をリセットする。クロック数変換回路31aは、デマルチプレクサ31dからLレベルのEN信号を受けると、「0」を示すLレベルの一致検出信号をOR回路31eに出力する。

【0066】
OR回路31eは、クロック数変換回路31aからの一致検出信号(1又は0)と、デマルチプレクサ31dからのEN信号(1又は0)とを受け、一致検出信号とEN信号の論理和を演算し、演算結果からなる駆動信号を距離/クロック数変換回路320におけるデマルチプレクサ32dに出力する。

【0067】
デマルチプレクサ32dは、OR回路31eからの駆動信号と、後述する一致検出回路32c’からの一致信号(DETECT2)とを受ける。デマルチプレクサ32dは、一致検出信号(DETECT2)がLレベルの場合、OR回路31eからの駆動信号をクロック数変換回路32aに出力し、OR回路31eからの駆動信号を反転させた反転信号をOR回路32eに出力する。また、一致信号(DETECT2)がHレベルの場合には、OR回路31eからの駆動信号を反転させた反転信号をクロック数変換回路32aに出力し、OR回路31eからの駆動信号をOR回路32eに出力する。

【0068】
クロック数変換回路32aは、距離演算回路DP12からMビットの距離信号D12を受け、バッファ23からクロック信号CLKを受ける。クロック数変換回路32aは、デマルチプレクサ32dから「1」を示す駆動信号を受けると、クロック信号CLKのクロック数をカウントし、カウントしたクロック数と距離信号D12が示す距離との一致を検出する。クロック数変換回路32aは、カウントしたクロック数と距離信号D12が示す距離とが一致するタイミングで、OR回路32eに「1」を示す一致検出信号を出力する。また、クロック数変換回路32aは、後述のデマルチプレクサ300dから出力される信号を受け、その信号を受けたタイミングでカウントしたクロック数をリセットする。クロック数変換回路32aは、デマルチプレクサ32dから「0」を示す駆動信号を受けると、「0」を示す駆動信号をOR回路32eに出力する。

【0069】
OR回路32eは、クロック数変換回路32aからの一致検出信号(1又は0)と、デマルチプレクサ32dからの駆動信号(1又は0)とを受け、受けた2つの信号の論理和を演算し、演算結果を示す信号をカウンタ一致検出ユニット300におけるデマルチプレクサ300aに出力する。

【0070】
デマルチプレクサ300aは、OR回路32eからの信号を受け、後述するAND回路300cから検索終了か否かを示すSearch-End信号を受ける。デマルチプレクサ300aは、Search-End信号がLレベルの場合には、OR回路32eからの信号をカウンタ300bとクロック数変換回路31a,32aに出力し、Search-End信号がLレベルからHレベルに切り替わると、OR回路32eからの信号をタイミング信号CとしてWinner検出器20へ出力する。

【0071】
カウンタ300bは、デマルチプレクサ300aから信号を受けるごとにカウンタ値を1つだけカウントアップさせ、カウントアップしたMビットのカウンタ値を一致検出回路31c’,32c’へ出力する。なお、カウンタ300bの初期値として、カウンタ値「0」が設定されている。

【0072】
一致検出回路31c’は、カウンタ300bからMビットのカウンタ値を受け、距離演算回路DP11から距離信号D11を受ける。一致検出回路31c’は、カウンタ値と距離信号D11が示す距離との一致を検出する。一致検出回路31c’は、カウンタ値≧距離を満たす場合には、Hレベルの一致信号(DETECT1)をデマルチプレクサ31dとAND回路300cに出力する。また、カウンタ値と距離とが一致しない場合、つまり、カウンタ値<距離を満たす場合には、Lレベルの一致信号(DETECT1)をデマルチプレクサ31dとAND回路300cに出力する。

【0073】
一致検出回路32c’は、カウンタ300bからMビットのカウンタ値を受け、距離演算回路DP12から距離信号D12を受ける。一致検出回路32c’は、カウンタ値と距離信号D12が示す距離との一致を検出する。一致検出回路32c’は、カウンタ値と距離とが、カウンタ値≧距離を満たす場合には、Hレベルの一致信号(DETECT2)をデマルチプレクサ32dとAND回路300cに出力する。また、カウンタ値と距離とが一致しない場合、つまり、カウンタ値<距離を満たす場合には、Lレベルの一致信号(DETECT2)をデマルチプレクサ32dとAND回路300cに出力する。

【0074】
AND回路300cは、一致検出回路31c’からの一致信号(DETECT1)と、一致検出回路32c’からの一致信号(DETECT2)との論理積を演算し、その演算結果を示すSearch-End信号をデマルチプレクサ300aに出力する。つまり、Hレベルの一致信号(DETECT1,DETECT2)の場合には、「1」を示すSearch-End信号がデマルチプレクサ300aに出力され、検索を終了する。また、少なくともいずれか一方の一致信号がLレベルである場合には、「0」を示すSearch-End信号がデマルチプレクサ300aに出力され、検索を継続する。

【0075】
ここで、例えば、距離演算回路DP11から距離「2」を示すMビットの距離信号D11が出力され、距離演算回路DP12から距離「3」を示すMビットの距離信号D12が出力された場合の動作例について説明する。

【0076】
EN信号が入力されると、デマルチプレクサ31dは、一致信号(DETECT1)が立ち上がっていないため、クロック数変換回路31aにHレベルのEN信号を出力し、OR回路31eにLレベルのEN信号を出力する。クロック数変換回路31aは、デマルチプレクサ31dからHレベルのEN信号を受けると、バッファ23からのクロック信号CLKのクロック数をカウントし、カウントしたクロック数と距離演算回路DP11からの距離信号D11が示す距離「2」と一致するタイミングで一致検出信号(=1)を出力する。

【0077】
OR回路31eは、クロック数変換回路31aからの一致検出信号(=1)とデマルチプレクサ31dからのEN信号(=0)との論理和の演算結果からなる駆動信号(=1)をデマルチプレクサ32dに出力する。デマルチプレクサ32dは、OR回路31eから駆動信号(=1)を受けると、一致信号(DETECT2)が立ち上がっていないため、その駆動信号(=1)をクロック数変換回路32aに出力し、その駆動信号の反転信号(=0)をOR回路32eに出力する。クロック数変換回路32aは、デマルチプレクサ32dから駆動信号(=1)を受けると、バッファ23からのクロック信号CLKのクロック数をカウントし、カウントしたクロック数と、距離演算回路DP12からの距離信号D12が示す距離「3」とが一致するタイミングで、一致検出信号(=1)を出力する。

【0078】
OR回路32eは、クロック数変換回路32aからの一致検出信号(=1)と、デマルチプレクサ32dからの反転信号(=0)との論理和の演算結果を表す信号(=1)をデマルチプレクサ300aに出力する。デマルチプレクサ300aは、カウンタ300bとクロック数変換回路31a,32aとにOR回路32eからの信号(=1)を出力する。クロック数変換回路31aとクロック数変換回路32aは、デマルチプレクサ300aからの信号(=1)を受けると、カウントしたクロック数をそれぞれリセットする。カウンタ300bは、デマルチプレクサ300aからの信号(=1)を受けると、カウンタ値をカウントアップし、カウンタ値「1」を一致検出回路31c’,32c’へ出力する。なお、検索開始からこのカウンタ値「1」が得られるときのクロック信号CLKの総クロック数は5(=2+3)である。

【0079】
一致検出回路31c’は、距離演算回路DP11からの距離信号D11が示す距離「2」と、カウンタ300bからのカウンタ値「1」とが一致しないため(距離>カウンタ値)、Lレベルの一致信号(DETECT1)を出力する。また、一致検出回路32c’は、距離演算回路DP12からの距離信号D12が示す距離「3」と、カウンタ300bからのカウンタ値「1」とが一致しないため(距離>カウンタ値)、Lレベルの一致信号(DETECT2)を出力する。

【0080】
デマルチプレクサ31dは、一致信号(DETECT1)が立ち上がっていないため、クロック数変換回路31aにHレベルのEN信号を入力し、OR回路31eにLレベルのEN信号を出力する。クロック数変換回路31aは、クロック信号CLKのクロック数を再びカウントし、カウントしたクロック信号CLKのクロック数と距離「2」とが一致するタイミングで、OR回路31eに「1」を示す一致検出信号を出力する。

【0081】
クロック数変換回路31aからの一致検出信号(=1)と、OR回路31eからのEN信号(=0)との論理和の演算結果を示す駆動信号(=1)がOR回路31eから出力される。デマルチプレクサ32dは、OR回路31eから駆動信号(=1)を受けると、一致信号(DETECT2)が立ち上がっていないため、クロック数変換回路32aに駆動信号(=1)を出力し、その駆動信号の反転信号(=0)をOR回路32eに出力する。クロック数変換回路32aは、クロック信号CLKのクロック数を再びカウントし、カウントしたクロック信号CLKのクロック数と距離「3」とが一致するタイミングで、OR回路31eに「1」を示す一致検出信号を出力する。

【0082】
クロック数変換回路32aからの一致検出信号(=1)と、デマルチプレクサ32dからの反転信号(=0)との論理和の演算結果を示す信号(=1)がOR回路32eから出力されると、デマルチプレクサ300aは、OR回路32eからの信号(=1)をカウンタ300bとクロック数変換回路31a,32aに出力する。これにより、クロック数変換回路31aとクロック数変換回路32aは、カウントしたクロック数をそれぞれリセットする。カウンタ300bは、デマルチプレクサ300aからの信号(=1)を受けてカウンタ値をカウントアップさせ、カウンタ値「2」を一致検出回路31c’,32c’へ出力する。なお、検索開始からこのカウンタ値「2」が得られるときの総クロック数は10(=2+3+2+3)である。

【0083】
一致検出回路31c’において、距離信号D11が示す距離「2」と、カウンタ300bからのカウンタ値「2」とが一致するため(距離≦カウンタ値)、Hレベルの一致信号(DETECT1)が出力される。一方、一致検出回路32c’において、距離信号D12が示す距離「3」と、カウンタ300bからのカウンタ値「2」とが一致しないため(距離>カウンタ値)、Lレベルの一致信号(DETECT2)が出力される。

【0084】
デマルチプレクサ31dは、一致信号(DETECT1)がLレベルからHレベルに切り替わると、OR回路31eにHレベルのEN信号を出力し、クロック数変換回路31aにLレベルのEN信号を出力する。クロック数変換回路31aは、LレベルのEN信号を受けると、「0」を示す一致検出信号をOR回路31eに出力する。

【0085】
クロック数変換回路31aからの一致検出信号(=0)と、デマルチプレクサ31dからのEN信号(=1)との論理和の演算結果を示す駆動信号(=1)がOR回路31eから出力されると、デマルチプレクサ32dは、OR回路31eからの駆動信号(=1)をクロック数変換回路32aに出力し、その駆動信号の反転信号(=0)をOR回路32eに出力する。

【0086】
クロック数変換回路32aは、OR回路32eから駆動信号(=1)を受けると、クロック信号CLKをカウントし、カウントしたクロック数と距離「3」とが一致するタイミングで、「1」を示す一致検出信号をOR回路32eに出力する。OR回路32eは、クロック数変換回路32aからの一致検出信号(=1)とデマルチプレクサ32dからの駆動信号(=0)との論理和の演算結果を示す信号(=1)をデマルチプレクサ300aに出力する。

【0087】
デマルチプレクサ300aは、OR回路32eから出力される信号(=1)をカウンタ300bとクロック数変換回路31a,32aに出力する。これにより、クロック数変換回路31aとクロック数変換回路32aは、カウントしたクロック数をそれぞれリセットする。また、カウンタ300bは、デマルチプレクサ300aからの信号(=1)を受けてカウンタ値をカウントアップし、カウンタ値「3」を一致検出回路31c’,32c’へ出力する。なお、検索開始からこのカウンタ値「3」が得られるときの総クロック数は13(=2+3+2+3+3)である。

【0088】
一致検出回路31c’において、距離演算回路DP11からの距離信号D11が示す距離「2」と、カウンタ300bからのカウンタ値「3」は、距離≦カウンタ値を満たすため、Hレベルの一致信号(DETECT1)が出力される。また、一致検出回路32c’において、距離演算回路DP11からの距離信号D11が示す距離「3」と、カウンタ300bからのカウンタ値「3」とが一致するため(距離≦カウンタ値)、Hレベルの一致信号(DETECT2)が出力される。

【0089】
デマルチプレクサ31dは、一致信号(DETECT1)がHレベルであるので、OR回路31eにHレベルのEN信号を出力し、クロック数変換回路31aにLレベルのEN信号を出力する。クロック数変換回路31aは、LレベルのEN信号を受けると、「0」を示す一致検出信号をOR回路31eに出力する。クロック数変換回路31aからの一致検出信号(=0)と、OR回路31eからのEN信号(=1)との論理和の演算結果を示す駆動信号(=1)信号がOR回路31eから出力される。

【0090】
デマルチプレクサ32dは、一致信号(DETECT2)がLレベルからHレベルに切り替わると、OR回路31eからの駆動信号(=1)の反転信号(=0)をクロック数変換回路32aに出力し、その駆動信号(=1)をOR回路32eに出力する。クロック数変換回路32aは、デマルチプレクサ32dから駆動信号(=0)を受けると、「0」を示す一致検出信号をOR回路32eに出力する。OR回路32eは、クロック数変換回路32aからの一致検出信号(=0)と、デマルチプレクサ32dからの駆動信号(=1)との論理和の演算結果を示す信号(=1)をデマルチプレクサ300aに出力する。

【0091】
AND回路300cは、一致検出回路31c’,32c’からのHレベルの一致信号(DETECT1)と一致信号(DETECT2)との論理積を演算し、Search-End信号(=1)をデマルチプレクサ300aに出力する。デマルチプレクサ300aは、Search-End信号(=1)を受けると検索を終了し、OR回路32eからの信号を、タイミング信号CとしてWinner検出器20へを出力する。つまり、検索開始からクロック数が「13」となるタイミングでタイミング信号Cが出力される。

【0092】
クロック数「13」は、距離信号D11と距離信号D12の各距離(D11=2,D12=3)の二乗値の和(=4+9)と等しい。参照データと検索データとのユークリッド距離nErの演算は、上述したように、式(1)によって演算したW個の各距離について、距離に一致するクロック数をカウントする処理を、距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図4の例において、カウンタ一致検出ユニット300が、距離/クロック数変換ユニット310,320全体でクロック数「13」をカウントしたタイミングを示すタイミング信号Cを出力することは、ユークリッド距離nErによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示すWinner信号を出力することに相当する。なお、距離/クロック数変換回路DC~DCの各々も、距離/クロック数変換回路DCの動作と同じ動作によって、それぞれ、タイミング信号C~Cを出力する。

【0093】
第1実施形態では、距離演算回路DP11~DPRWの各々に対してカウンタを設ける例であったが、本実施形態では、距離/クロック数変換回路DCごとに1つのカウンタを設ける構成であるため、第1実施形態と比べて回路面積を小さくすることができる。

【0094】
なお、上述した第2実施形態において、連想メモリ100の制御回路(図示せず)から、各距離/クロック数変換回路DCのデマルチプレクサ300aに、マンハッタン距離又はユークリッド距離を示す制御信号を入力し、マンハッタン距離を示す制御信号が入力された場合には、各距離/クロック数変換回路DCにおいて1回目の処理が終了するタイミングでタイミング信号Cを出力するようにしてもよい。つまり、図4の例において、クロック数変換回路31aがクロック数「2」をカウントした後、クロック数変換回路32aにおいてクロック数「3」をカウントしたタイミングで、デマルチプレクサ300aからタイミング信号Cを出力する。その結果、タイミング信号Cは、検索開始からクロック数「5」(=2+3)のタイミングで出力される。これは、1つの行における参照データと検索データとの各マンハッタン距離の和と一致する。従って、このような構成にすることで、マンハッタン距離とユークリッド距離とを選択的に用いて検索を行うことが可能となる。

【0095】
<第3実施形態>
上述した第1実施形態及び第2実施形態では、各距離/クロック数変換回路において、距離ごとに、距離をクロック数に変換する処理を距離と一致する回数だけ繰り返し行うことによって、ユークリッド距離を用いた検索を行う例について説明した。

【0096】
例えば、第1実施形態における各距離/クロック数変換回路において、距離をクロック数に変換する処理を各カウンタ一致検出回路において1回だけ行ったタイミングでタイミング信号を出力すると、マンハッタン距離(式(1))の和に一致するクロック数のタイミングでタイミング信号が出力される。また、上述したように、第2実施形態における距離/クロック数変換回路DC~DCの距離/クロック数変換ユニット310,320において、距離をクロック数に変換する処理を1回だけ行ってタイミング信号を出力する場合もマンハッタン距離の和に一致するクロック数のタイミングでタイミング信号を出力することができる。

【0097】
第1実施形態や第2実施形態において、ユークリッド距離とマンハッタン距離のいずれを用いて検索する場合であっても、各距離/クロック数変換回路において、全ての距離についてクロック数が一致しなければタイミング信号は出力されない。つまり、第1実施形態や第2実施形態の場合、最も早くタイミング信号が出力されるタイミングt1(以下、類似パターンp1)と、2番目にタイミング信号が出力されるタイミングt2(以下、類似パターンp2)は、図5Aに示す関係となる。類似パターンp1は、距離がnM1の場合であり、類似パターンp2は、距離がnM2(>nM1)の場合を示している。また、τCLKは、クロックサイクルを表している。従って、類似パターンp1のタイミング信号は、t1=nM1・τCLKのタイミングで出力され、類似パターンp2のタイミング信号は、t2=nM2・τCLKのタイミングで出力される。

【0098】
第1実施形態や第2実施形態のように、距離ごとに、カウントしたクロック数との一致を厳密に検出すると、検索データやビット長が増加するほど多大な検索時間を要することになる。本実施形態では、図5Bに示すように、類似パターンp1,p2から同じ値(n・τCLK)だけ検索時間を削減することにより、第1実施形態や第2実施形態と比べて検索時間を短縮する検索アルゴリズムについて説明する。なお、以下の説明においては、マンハッタン距離を用いる場合を例に説明する。

【0099】
図6は、本実施形態に係る連想メモリの構成例を示す概略ブロック図である。図6において、第1実施形態と同様の構成には、第1実施形態と同じ符号を付している。以下、第1実施形態と異なる構成について説明する。図6に示すように、連想メモリ110は、距離/クロック数変換回路DC~DCに替えて距離/クロック数変換回路DE~DEを備え、AND回路6と有効ビット設定部40とを更に備える。

【0100】
距離演算回路DP11~DP1Wの各々は、参照データ1と検索データとの距離を上述した式(1)を用いて演算する。また、距離演算回路DP21~DP2Wの各々は、参照データ2と検索データとの距離を上述した式(1)を用いて演算する。以下同様にして、距離演算回路DPR1~DPRWの各々は、参照データRと検索データとの距離を上述した式(1)を用いて演算する。

【0101】
距離/クロック数変換回路DEは、距離演算回路DP11~DP1WからW個のNビット長を有する距離信号D1jを受け、後述する方法で距離信号D1jが示す距離に一致するクロック数を検出したタイミングで、一致検出信号m1W_nを有効ビット設定部40へ出力する。距離/クロック数変換回路DEは、距離演算回路DP21~DP2WからW個のNビット長を有する距離信号D2jを受け、後述する方法で距離信号D2jが示す距離に一致するクロック数を検出したタイミングで、一致検出信号m2W_nを有効ビット設定部40へ出力する。以下、同様にして、距離/クロック数変換回路DEは、距離演算回路DPR1~DPRWからW個のNビット長を有する距離信号DRjを受け、後述する方法で距離信号DRjが示す距離に一致するクロック数を検出したタイミングで、一致検出信号mRW_nを有効ビット設定部40へ出力する。

【0102】
図7は、距離/クロック数変換回路DEの構成例を示す概略構成図である。図7に示すように、距離/クロック数変換回路DEは、距離演算回路DP11~DP1Wにそれぞれ対応するように設けられたカウンタ一致検出回路DE11~DE1Wと、バッファ21~2Wとを有する。なお、距離/クロック数変換回路DE…DEについても距離/クロック数変換回路DEと同様の構成を有する。

【0103】
カウンタ一致検出回路DE11~DE1Wは、それぞれ距離演算回路DP11~DP1WからNビット長を有する距離信号D11~D1Wを受ける。カウンタ一致検出回路DE11は、バッファ21からクロック信号CLKが入力される。カウンタ一致検出回路DE12~DE1Wは、それぞれカウンタ一致検出回路DE11~DE1W-1から後述するカウンタ一致信号m11_n~m1W-1_nがバッファ22~2Wに入力されると、バッファ22~2Wからクロック信号CLKが入力される。

【0104】
カウンタ一致検出回路DE11~DE1Wは、後述する有効ビット設定部40から、検索対象のビットを示す信号(以下、BAS信号)を受ける。カウンタ一致検出回路DE11は、BAS信号が示すビット(n)に対応するカウンタ値と距離信号D11が示す距離との一致を検出し、一致を検出したタイミングでバッファ22とカウンタ一致検出回路DE12にHレベルの一致検出信号m11_nを出力する。カウンタ一致検出回路DE12は、Hレベルの一致検出信号m11_nを受けると、BAS信号が示すビットに対応するカウンタ値と距離信号Dが示す距離との一致を検出し、一致を検出したタイミングで、バッファ23とカウンタ一致検出回路DE13(図示せず)にHレベルの一致検出信号m12_nを出力する。以下同様にして、カウンタ一致検出回路DE1Wは、Hレベルの一致検出信号m1w-1_nを受けると、BAS信号が示すビットに対応するカウンタ値と距離信号D1Wが示す距離との一致を検出し、一致を検出したタイミングで、Hレベルの一致検出信号m1w_nを出力する。

【0105】
ここで、カウンタ一致検出回路DE11の構成例を示す概略構成図を図8に示す。図8に示すように、カウンタ一致検出回路DE11は、Nビットのカウンタ312、一致検出回路313、及びマルチプレクサ314を有する。なお、カウンタ一致検出回路DE12…DE1wについてもカウンタ一致検出回路DE11と同様の構成を有する。

【0106】
カウンタ312は、バッファ21からクロック信号CLKを受け、有効ビット設定部40からBAS信号を受け、連想メモリ110の制御回路(図示せず)からリセット信号(RST)を受ける。カウンタ312は、クロック信号CLKのクロックに同期して、BAS信号が示すビットについてカウントアップを行い、カウンタ値を一致検出回路313に出力する。

【0107】
一致検出回路313は、BAS信号が示すビットに対応するカウンタ値と距離信号D11の値との一致を検出する。一致検出回路313は、BAS信号が示すビットに対応するカウンタ値と距離信号D11の値との一致を検出すると、「1」を示す一検出信号m11_nをマルチプレクサ314に出力する。

【0108】
図9Aは、本実施形態におけるカウンタ312と一致検出回路313の回路構成例を示している。図9Aの例では、カウンタ312は3ビットカウンタで構成される。カウンタ312は、3つのセレクタ312a,312b,312cと、各セレクタと接続された分周器312d,312e,312fとを有する。セレクタ312a,312b,312cは、有効ビット設定部40からBAS信号を受け、バッファ21からクロック信号CLKを受ける。セレクタ312aは、最上位ビットに対応し、最上位ビットを示すBAS信号(BAS<1>)を受ける。セレクタ312bは、最上位から2番目のビットに対応し、2番目のビットを示すBAS信号(BAS<2>)を受ける。セレクタ312cは、最下位ビットに対応し、最下位ビットを示すBAS信号(BAS<3>)を受ける。BAS信号は、1又は0を示す信号である。

【0109】
一致検出回路313は、EXNOR回路313a,313b,313cと、AND回路313d,313eとを有する。EXNOR回路313a,313b,313cは、分周器312d,312e,312fとそれぞれ接続されている。

【0110】
セレクタ312a,312b,312cのいずれかにBAS信号(=1)が入力されると、BAS信号(=1)が入力されたセレクタは、クロック信号CLKを対応する分周器に入力する。クロック信号CLKが入力された分周器は、クロック信号CLKを分周して一致検出回路313へ出力する。なお、分周器312d,312eは、下位のビットを示すBAS信号が入力されている場合であっても、下位のビットに対応する分周器のカウントアップによる桁上げ値が入力されるとカウントアップを行う。

【0111】
図9Bは、BAS信号によって最上位から最下位ビットが指定された場合のカウンタ312の動作を示すである。BAS信号により最上位ビットが指定されている場合(BAS<1>=1,BAS<2>=0,BAS<3>=0)、セレクタ312cはグランドに接地されているため、分周器312f、312eからEXNOR回路313b,313cに信号値「0」が出力される。分周器312aには、クロック信号CLKが入力され、図9Bのi)に示すように、クロック信号CLKを2回分周した信号で示されるカウンタ値をEXNOR回路313aに出力する。つまり、この場合には、カウンタ312は、1ビットカウンタとして機能する。

【0112】
また、BAS信号により最上位から2ビット目が指定されている場合(BAS<1>=0,BAS<2>=1,BAS<3>=0)、分周器312fからEXNOR回路313cに信号値「0」が出力される。分周器312eには、クロック信号CLKが入力され、図9Bのii)に示すように、クロック信号CLKを2回分周した信号で示されるカウンタ値をEXNOR回路313bに出力する。分周器312dには、分周器312eからの桁上げ信号が入力され、図9Bのii)に示すように、クロック信号CLKを2分周した信号で示されるカウンタ値をEXNOR回路313aに出力する。つまり、この場合には、カウンタ312は、2ビットカウンタとして機能する。

【0113】
また、BAS信号により最下位ビットが指定されている場合(BAS<1>=0,BAS<2>=0,BAS<3>=1)、分周器312fには、クロック信号CLKが入力され、図9Bのiii)に示すように、クロック信号CLKを2回分周した信号で示されるカウンタ値をEXNOR回路313cに出力する。分周器312eには、分周器312fからの桁上げ信号が入力され、図9Bのiii)に示すように、クロック信号CLKを2回分周した信号で示されるカウンタ値をEXNOR回路313bに出力する。また、分周器312dには、分周器312eからの桁上げ信号が入力され、図9Bのiii)に示すように、クロック信号CLKを2回分周した信号で示されるカウンタ値をEXNOR回路313aに出力する。つまり、この場合には、カウンタ312は、3ビットカウンタとして機能する。

【0114】
図9Aに戻り、説明を続ける。EXNOR回路313a,313b,313cは、距離信号Dijの各ビットの値D<1>,D<2>,D<3>を受け、分周器312d,312e,312fからそれぞれカウンタ値を受ける。

【0115】
EXNOR回路313aは、距離信号Dijの最上位ビットの値D<1>と、分周器312dから出力されるカウンタ値とが一致する場合に、AND回路313dに「1」を示す検出信号を出力し、その検出信号(=1)を最上位ビットに対応する一致検出信号mij_1としてマルチプレクサ314に出力する。また、距離信号Dijの最上位ビットの値D<1>とカウンタ値とが一致しない場合、AND回路313dに「0」を示す検出信号を出力し、その検出信号(=0)を一致検出信号mij_1としてマルチプレクサ314に出力する。

【0116】
EXNOR回路313bは、距離信号Dijの最上位から2番目のビットの値D<2>と、分周器312eから出力されるカウンタ値とが一致する場合に、AND回路313dに「1」を示す検出信号を出力し、一致しない場合には「0」を示す検出信号を出力する。

【0117】
EXNOR回路313cは、距離信号Dijの最下位ビットの値D<3>と、分周器312fから出力されるカウンタ値とが一致する場合に、AND回路313eに「1」を示す検出信号を出力し、一致しない場合には「0」を示す検出信号を出力する。

【0118】
AND回路313dは、EXNOR回路313aとEXNOR回路313bとから入力される検出信号の論理積の値を示す検出信号をAND回路313eに出力し、その検出信号を最上位から2番目のビットに対応する一致検出信号mij_2としてマルチプレクサ314に出力する。例えば、EXNOR回路313aとEXNOR回路313bとから検出信号(=1)が出力された場合、つまり、上位2ビットの距離とカウンタ値とが一致している場合には、「1」を示す検出信号がAND回路313eに出力され、「1」を示す一致検出信号mij_2がマルチプレクサ314に出力される。また、EXNOR回路313aとEXNOR回路313bの少なくとも一方から検出信号(=0)が出力された場合、つまり、上位2ビットの距離とカウンタ値とが一致していない場合には、「0」を示す検出信号がAND回路313eに出力され、「0」を示す一致検出信号mij_2がマルチプレクサ314に出力される。

【0119】
AND回路313eは、EXNOR回路313cとAND回路313dとから入力される検出信号の論理積の値を示す検出信号を最下位ビットに対応する一致検出信号mij_3としてマルチプレクサ314に出力する。例えば、EXNOR回路313cとAND回路313dとから検出信号(=1)が出力された場合、つまり、全ビットで表される距離とカウンタ値とが一致している場合には、一致検出信号mij_3(=1)が出力される。また、EXNOR回路313cとAND回路313dの少なくとも一方から検出信号(=0)が出力された場合、つまり、全ビットで表される距離とカウンタ値とが一致していない場合には、一致検出信号mij_3(=0)がマルチプレクサ314に出力される。そして、一致検出回路313においては、EXNOR回路313aが「1」を示す検出信号を出力しない限り、AND回路313d,313eとはそれぞれ「1」を示す一致検出信号mij_2,mij_3を出力することはない。

【0120】
図8に戻り、カウンタ一致検出回路DE11におけるマルチプレクサ314は、BAS信号で示されるビットに対応する、一致検出回路313から出力される一致検出信号m11_nを、バッファ22及びカウンタ一致検出回路DE12に出力する。なお、カウンタ一致検出回路DE1Wにおけるマルチプレクサ314から出力される一致検出信号m1W_nは、有効ビット設定部40に出力される。

【0121】
次に、図6、7を参照して、有効ビット設定部40について説明する。有効ビット設定部40は、クロック信号CLKと、距離/クロック数変換回路DE~DEから出力される一致検出信号miW_n(1又は0)を受ける。有効ビット設定部40は、いずれかの距離クロック数変換回路DE~DEから一致検出信号miW_n(=1)を受けると、クロック信号CLKに同期して、カウンタ一致検出回路DEi1~DEiWにおける各カウンタ312及びマルチプレクサ314に対してBAS信号を出力する。

【0122】
有効ビット設定部40からカウンタ一致検出回路DEi1~DEiWにBAS信号を入力するために、1クロックサイクルが必要となる。有効ビット設定部40は、BAS信号を入力する間、CLK_ACT信号をAND回路6に入力し、クロック信号CLKが距離/クロック数変換回路DE~DEに入力されないようにする。CLK_ACT信号は、一致検出信号miW_nを反転させた信号である。

【0123】
つまり、一致検出信号miW_nが立ち上がると(一致検出信号miW_n=1)、「0」を示すCLK_ACT信号がAND回路6に入力され、一致検出信号miW_nが立ち上がっていなければ(一致検出信号m1W_n=0)、「1」を示すCLK_ACT信号がAND回路6に入力される。有効ビット設定部40は、距離/クロック数変換回路DE~DEから最下位ビットに対応する一致検出信号が立ち上がったタイミングでタイミング信号C~CをWinner検出器20へ出力する。

【0124】
AND回路6は、クロック信号CLKと有効ビット設定部40からのCLK_ACT信号(1又は0)とを受ける。AND回路6は、有効ビット設定部40からのCLK_ACT信号とクロック信号CLKとの論理積を演算した結果を距離/クロック数変換回路DE~DEに入力する。つまり、有効ビット設定部40からCLK_ACT信号(=0)が入力された場合には、クロック信号CLKが距離/クロック数変換回路DE~DEに入力されず、CLK_ACT信号(=1)が入力された場合には、クロック信号CLKが距離/クロック数変換回路DE~DEに入力される。

【0125】
ここで、図6に示す構成において、参照データが参照データ1、2であり、R=2、W=3である場合の動作例について説明する。図10Aは、参照データ1に対する距離/クロック数変換回路DEと、参照データ2に対する距離/クロック数変換回路DEとにおいて、参照データ1と検索データとの距離と、参照データ2と検索データとの距離とをそれぞれクロック数に変換する処理過程を示す図である。

【0126】
図10Aの例において、距離/クロック数変換回路DEは、カウンタ一致検出回路DE11~DE13を有し、距離/クロック数変換回路DEは、カウンタ一致検出回路DE21~DE23を有する。なお、図10Aにおけるカウンタ値と距離の各値の下線は、有効ビット設定部40によって設定されたビット、つまり、距離とカウンタ値の一致検出対象となるビットであることを示している。

【0127】
カウンタ一致検出回路DE11,DE12,DE13には、距離演算回路DP11,DP12,DP13から距離信号D11,12,D13がそれぞれ入力される。この例において、距離信号D11が示す距離は「510(=101)」であり、距離信号D12が示す距離は「410(=100)」であり、距離信号D13が示す距離は「310(=010)」である。また、カウンタ一致検出回路DE21,DE22,DE23には、距離演算回路DP21,DP22,DP23から距離信号D21,22,D23がそれぞれ入力される。この例において、距離信号D21が示す距離は「710(=111)」であり、距離信号D22が示す距離は「010(=000)」であり、距離信号D23が示す距離は「210(=010)」である。なお、距離/クロック数変換回路DEとDEにおける各カウンタ一致検出回路には、初期値として、最上位ビットを示すBAS信号(BAS<1>=1,BAS<2>=0,BAS<3>=0)が予め設定されている。

【0128】
連想メモリ110の制御回路(図示せず)から検索開始を示す信号SBが入力されると、0クロック目において、カウンタ一致検出回路DE11,DE12は、それぞれ、最上位ビットに対応する分周器312dのカウンタ値「0」を一致検出回路313のEXNOR回路313aに出力する。図10Aの例において、BAS「1」,クロック「0」のとき、カウンタ一致検出回路DE11における、下線で示す最上位ビットのカウンタ値「00」と距離「01」とは一致しない。同様に、カウンタ一致検出回路DE21における、下線で示す最上位ビットのカウンタ値「00」と距離「11」とは一致しない。そのため、カウンタ一致検出回路DE11とカウンタ一致検出回路DE21において、それぞれ、EXNOR回路313aから「0」を示す検出信号がAND回路313dに出力される。そして、カウンタ一致検出回路DE11からカウンタ一致検出回路DE12に一致検出信号m11_1(=0)が出力され、カウンタ一致検出回路DE21からカウンタ一致検出回路DE22に一致検出信号m21_1(=0)が出力される。

【0129】
有効ビット設定部40は、0クロック目において、距離/クロック数変換回路DE、DEの最上位ビットに対応する一致検出信号がいずれも立ち上がっていないため、CLK_ACT信号(=1)をAND回路6に出力する。これにより、カウンタ一致検出回路DE11、DE21にクロック信号CLKが入力される。

【0130】
カウンタ一致検出回路DE11、DE21は、それぞれのセレクタ312aにクロック信号CLKを入力する。カウンタ一致検出回路DE11における分周器312dはクロック信号CLKを2回分周し、図10Bに示すt1におけるカウンタ値「1」をEXNOR回路313aに出力し、EXNOR回路313aから「1」を示す検出信号がAND回路313dに出力される。そして、カウンタ一致検出回路DE12とバッファ22とに、一致検出信号m11_1(=1)が出力される。

【0131】
カウンタ一致検出回路DE12は、一致検出信号m11_1(=1)が入力されると、一致検出回路313において、最上位ビットに対応する分周器312dのカウンタ値と距離D12との一致の検出を開始する。カウンタ一致検出回路DE12における分周器312dはクロック信号CLKを2回分周し、図10Bに示すt1におけるカウンタ値「0」をEXNOR回路313aに出力する。最上位ビットに対応するカウンタ値「0」と距離D1200」とは一致しないため、EXNOR回路313aから「0」を示す検出信号がAND回路313dに出力され、一致検出信号m12_1(=0)が出力される。従って、検索開始から1クロック目に、参照データ1について一致検出信号m13_1(=1)は出力されない。

【0132】
一方、図10Bに示すように、カウンタ一致検出回路DE21における分周器312dはクロック信号CLKを2回分周し、図10Bに示すt1におけるカウンタ値「1」をEXNOR回路313aに出力し、EXNOR回路313aから「1」を示す検出信号がAND回路313dに出力される。そして、カウンタ一致検出回路DE12とバッファ22とに、一致検出信号m21_1(=1)が出力される。

【0133】
カウンタ一致検出回路DE22は、一致検出信号m21_1(=1)が入力されると、一致検出回路313において、最上位ビットに対応する分周器312dのカウンタ値と距離D22との一致の検出を開始する。図10Bに示すように、カウンタ一致検出回路DE22における分周器312dはクロック信号CLKを2回分周し、図10Bに示すt1におけるカウンタ値「0」をEXNOR回路313aに出力する。最上位ビットに対応するカウンタ値「0」と距離「00」とは一致するため、EXNOR回路313aから「1」を示す検出信号がAND回路313dに出力され、カウンタ一致検出回路DE23とバッファ23とに、一致検出信号m22_1(=1)が出力される。

【0134】
カウンタ一致検出回路DE23は、一致検出信号m22_1(=1)が入力されると、一致検出回路313において、最上位ビットに対応する分周器312dのカウンタ値と距離D23との一致の検出を開始する。図10Bに示すように、カウンタ一致検出回路DE23における分周器312dはクロック信号CLKを2回分周し、一致検出信号m22_1(=1)が入力されたタイミングでカウンタ値「0」をEXNOR回路313aに出力する。最上位ビットに対応するカウンタ値「0」と距離D2310」とは一致するため、EXNOR回路313aから「1」を示す検出信号がAND回路313dに出力され、マルチプレクサ314から有効ビット設定部40に一致検出信号m23_1(=1)が出力される。従って、検索開始から1クロック目で、参照データ2について一致検出信号m23_1(=1)が出力される。

【0135】
有効ビット設定部40は、距離/クロック数変換回路DEから最上位ビットに対する一致検出信号m23_1(=1)が入力されると、検索開始から2クロック目に、最上位から2番目のビットを示すBAS信号(BAS<1>=0,BAS<2>=1,BAS<3>=0)を、距離/クロック数変換回路DEとDEにおける各カウンタ一致検出回路に入力する。これにより、検出対象のビットが上位2ビットまで拡張される。また、有効ビット設定部40は、CLK_ACT信号(=0)をAND回路6に出力し、距離/クロック数変換回路DEとDEにクロック信号CLKが入力されないようにする。

【0136】
カウンタ一致検出回路DE11とDE21は、それぞれのカウンタ312において、最上位から2番目のビットに対応するセレクタ312bにBAS信号(BAS<2>=1)が入力されると、一致検出回路313において、上位2ビットのカウンタ値と距離との一致を検出する。

【0137】
BAS信号(BAS<2>=1)が入力されると、図10Cに示すように、カウンタ一致検出回路DE11における分周器312e,312dは、クロック信号CLKを2,2回それぞれ分周して2ビットのカウンタ値を出力する。検索開始から1クロック目に、カウンタ一致検出回路DE11における分周器312dのカウンタ値「1」と距離D1101」とが一致している。そのため、カウンタ一致検出回路DE11の分周器312d,312eは、図10Cに示すt1におけるカウンタ値「10」のビット値「1」,「0」をEXNOR回路313a,313bにそれぞれ出力する。つまり、距離「4」の検索が打ち消されたことになる。上位2ビットに対応するカウンタ値「10」と距離D11101」とは一致するため、EXNOR回路313a,313bからAND回路313d,313eに「1」を示す検出信号がそれぞれ出力され、EXNOR回路313aとAND回路313dからマルチプレクサ314に、一致検出信号m11_1(=1),m11_2(=1)がそれぞれ出力される。そして、マルチプレクサ314からカウンタ一致検出回路DE12とバッファ22に、一致検出信号m11_2(=1)が出力される。

【0138】
カウンタ一致検出回路DE12は、一致検出信号m11_2(=1)が入力されると、一致検出回路313において、上位2ビットのカウンタ値と距離D12との一致の検出を開始する。BAS信号(BAS<2>=1)が入力されると、図10Cに示すように、カウンタ一致検出回路DE12における分周器312e,312dは、クロック信号CLKを2,2回それぞれ分周して2ビットのカウンタ値を出力する。図10Cに示すように、t1におけるカウンタ一致検出回路DE12の分周器312d,312eのカウンタ値「00」のビット値「0」,「0」がEXNOR回路313a,313bにそれぞれ出力される。上位2ビットに対応するカウンタ値「00」と距離D12100」とは一致しないため、EXNOR回路313a,313bからAND回路313dにそれぞれ「0」,「1」を示す検出信号が出力され、一致検出信号m12_2(=0)がマルチプレクサ314からカウンタ一致検出回路DE13とバッファ23に出力される。

【0139】
カウンタ一致検出回路DE21における分周器312e,312dは、BAS信号(BAS<2>=1)が入力されると、図10Cに示すように、クロック信号CLKをそれぞれ2,2回分周して2ビットのカウンタ値を出力する。検索開始から1クロック目に、カウンタ一致検出回路DE21における分周器312dのカウンタ値「1」と距離「11」とが一致している。そのため、カウンタ一致検出回路DE21の分周器312d,312eは、図10Cに示すt1におけるカウンタ値「10」のビット値「1」,「0」をEXNOR回路313a,313bにそれぞれ出力する。つまり、距離「2」の検索が打ち消されたことになる。上位2ビットに対応するカウンタ値「10」と距離D21111」とは一致しないため、EXNOR回路313a,313bからAND回路313dに「1」,「0」を示す検出信号がそれぞれ出力され、マルチプレクサ314からカウンタ一致検出回路DE22とバッファ22に、一致検出信号m21_2(=0)が出力される。

【0140】
有効ビット設定部40は、2クロック目において、カウンタ一致検出回路DE、DEの最上位から2番目のビットに対応する一致検出信号(m13_2,m23_2)はいずれも立ち上がっていないため、AND回路6にCLK_ACT信号(=1)を入力して、距離/クロック数変換回路DEとDEにクロック信号CLKが入力されるようにする。

【0141】
カウンタ一致検出回路DE11において、上位2ビットについて一致検出信号m11_2(=1)が検索開始から2クロック目に出力されている。そのため、検索開始から3クロック目では、カウンタ一致検出回路DE11において一致検出の動作を停止する。

【0142】
カウンタ一致検出回路DE12は、検索開始から3クロック目に、セレクタ312bを介してクロック信号CLKが入力されると、分周器312d,312eは、図10Cに示すt2におけるカウンタ値「01」のビット値「0」,「1」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットのカウンタ値「01」と距離D12100」とは一致しない。そのため、カウンタ一致検出回路DE12において、カウンタ一致検出回路DE13とバッファ23に一致検出信号m12_2(=0)が出力される。

【0143】
カウンタ一致検出回路DE21も同様に、検索開始から3クロック目に、セレクタ312bを介してクロック信号CLKが入力されると、分周器312d,312eは、図10Cに示すt2におけるカウンタ値「11」のビット値「1」,「1」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットのカウンタ値「11」と距離D21111」とは一致する。そのため、カウンタ一致検出回路DE21において、マルチプレクサ314からカウンタ一致検出回路DE22とバッファ22に一致検出信号m21_2(=1)が出力される。

【0144】
カウンタ一致検出回路DE22は、一致検出信号m21_2(=1)が入力されると、一致検出回路313において、上位2ビットのカウンタ値と距離D22との一致の検出を開始する。図10Cに示すように、カウンタ一致検出回路DE22における分周器312e,312dは、t2におけるカウンタ値「00」のビット値「0」,「0」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットに対応するカウンタ値「00」と距離D22000」とは一致する。そのため、カウンタ一致検出回路DE22において、マルチプレクサ314からカウンタ一致検出回路DE23とバッファ23に一致検出信号m22_2(=1)が出力される。

【0145】
カウンタ一致検出回路DE23は、一致検出信号m22_2(=1)が入力されると、上位2ビットのカウンタ値と距離D23との一致の検出を開始する。図10Cに示すように、カウンタ一致検出回路DE23における分周器312e,312dは、t2におけるカウンタ値「00」のビット値「0」,「0」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットに対応するカウンタ値「00」と距離D23010」とは一致しない。そのため、カウンタ一致検出回路DE23において、マルチプレクサ314から有効ビット設定部40に一致検出信号m23_2(=0)が出力される。

【0146】
3クロック目おいて、距離/クロック数変換回路DEとDEのいずれも最上位から2番目のビットに対応する一致検出信号(m13_2,m23_2)が立ち上がっていない。そのため、4クロック目においても有効ビット設定部40からAND回路6にCLK_ACT信号(=1)が入力される。

【0147】
カウンタ一致検出回路DE11において、上位2ビットについて一致検出信号m11_2(=1)が検索開始から2クロック目に出力されているため、4クロック目においても一致検出の動作を停止する。

【0148】
カウンタ一致検出回路DE12は、検索開始から4クロック目に、セレクタ312bを介してクロック信号CLKが入力されると、分周器312d,312eは、図10Cに示すt3におけるカウンタ値「10」のビット値「1」,「0」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットのカウンタ値「10」と距離D12100」とは一致する。そのため、カウンタ一致検出回路DE12において、カウンタ一致検出回路DE13とバッファ23に一致検出信号m12_2(=1)が出力される。

【0149】
カウンタ一致検出回路DE13は、一致検出信号m12_2(=1)が入力されると、一致検出回路313において、上位2ビットのカウンタ値と距離D13との一致の検出を開始する。図10Cに示すように、カウンタ一致検出回路DE13における分周器312e,312dは、t3におけるカウンタ値「00」のビット値「0」,「0」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットに対応するカウンタ値「00」と距離D13011」とは一致しない。そのため、カウンタ一致検出回路DE13において、マルチプレクサ314から有効ビット設定部40に一致検出信号m13_2(=0)が出力される。

【0150】
一方、カウンタ一致検出回路DE21,DE22において、上位2ビットについての一致検出信号m21_2,m22_2(=1)が検索開始から2クロック,3クロック目にそれぞれ出力されているため、4クロック目ではカウンタ一致検出回路DE21,DE22は一致検出の動作を停止する。

【0151】
カウンタ一致検出回路DE23は、検索開始から4クロック目に、セレクタ312bを介してクロック信号CLKが入力されると、分周器312d,312eは、図10Cに示すt3におけるカウンタ値「01」のビット値「0」,「1」をEXNOR回路313a,313bにそれぞれ出力する。上位2ビットのカウンタ値「01」と距離D23010」とが一致するため、マルチプレクサ314から有効ビット設定部40に一致検出信号m23_2(=1)が出力される。

【0152】
有効ビット設定部40は、4クロック目において、最上位から2番目のビットに対する一致検出信号m23_2(=1)が距離/クロック数変換回路DEから入力されると、検索開始から5クロック目に、最下位ビットを示すBAS信号(BAS<1>=0,BAS<2>=0,BAS<3>=1)を、距離/クロック数変換回路DEとDEにおける各カウンタ一致検出回路に入力する。これにより、一致検出の対象ビットは、最上位ビットから最下位ビットまで拡張される。また、有効ビット設定部40は、CLK_ACT信号(=0)をAND回路6に入力し、距離/クロック数変換回路DEとDEにクロック信号CLKが入力されないようにする。

【0153】
カウンタ一致検出回路DE11とDE21は、検索開始から5クロック目に、それぞれのカウンタ312において、最下位のビットに対応するセレクタ312cにBAS信号(BAS<3>=1)が入力されると、一致検出回路313において、全てのビットのカウンタ値と距離との一致を検出する。

【0154】
カウンタ一致検出回路DE11における分周器312f,312e,313dは、BAS信号(BAS<3>=1)が入力されると、図10Dに示すように、クロック信号CLKを2,2,2回それぞれ分周して3ビットのカウンタ値を出力する。検索開始から2クロック目に、カウンタ一致検出回路DE11における分周器312d,312eのカウンタ値「10」と距離D11101」とが一致している。そのため、カウンタ一致検出回路DE11の分周器312d,312e,312fは、図10Dに示すt3におけるカウンタ値「100」のビット値「1」,「0」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。つまり、距離「4」の検索が打ち消されたことになる。全ビットに対応するカウンタ値「100」と距離D11101」とは一致しないため、EXNOR回路313a,313bからAND回路313dに「1」,「1」を示す検出信号がそれぞれ出力され、EXNOR回路313cからAND回路313eに「0」を示す検出信号が出力される。そして、マルチプレクサ314からカウンタ一致検出回路DE12とバッファ22に、一致検出信号m11_3(=0)が出力される。

【0155】
カウンタ一致検出回路DE21における分周器312f,312e,313dは、BAS信号(BAS<3>=1)が入力されると、図10Dに示すように、クロック信号CLKを2,2,2回それぞれ分周して3ビットのカウンタ値を出力する。検索開始から3クロック目に、カウンタ一致検出回路DE21における分周器312d,312eのカウンタ値「11」と距離D21111」とが一致している。そのため、カウンタ一致検出回路DE11の分周器312d,312e,312fは、図10Dに示すt5におけるのカウンタ値「110」のビット値「1」,「1」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。つまり、距離「6」の検索が打ち消されたことになる。全ビットに対応するカウンタ値「110」と距離D21111」とは一致しないため、EXNOR回路313a,313bからAND回路313dに「1」,「1」を示す検出信号がそれぞれ出力され、EXNOR回路313cからAND回路313eに「0」を示す検出信号が出力される。そして、マルチプレクサ314からカウンタ一致検出回路DE22とバッファ22に、一致検出信号m21_3(=0)が出力される。

【0156】
検索開始から5クロック目において、カウンタ一致検出回路DE11とDE21のいずれも最下位ビットのカウンタ値と距離とが一致しないため、カウンタ一致検出回路DE11とDE21においてクロック信号CLKが入力される。

【0157】
カウンタ一致検出回路DE11は、検索開始から6クロック目に、セレクタ312bを介してクロック信号CLKが入力されると、分周器312d,312e,312fは、図10Dに示すt4におけるカウンタ値「101」のビット値「1」,「0」,「1」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「101」と距離D11101」とが一致するため、カウンタ一致検出回路DE11において、カウンタ一致検出回路DE12とバッファ22に一致検出信号m11_3(=1)が出力される。

【0158】
カウンタ一致検出回路DE12は、一致検出信号m11_3(=1)が入力されると、一致検出回路313において、全てのビットのカウンタ値と距離との一致を検出する。検索開始から4クロック目に、カウンタ一致検出回路DE12における分周器312d,312e,312fのカウンタ値「10」と距離D11100」とが一致している。そのため、カウンタ一致検出回路DE12の分周器312d,312e,312fは、図10Dに示すt4におけるカウンタ値「100」のビット値「1」,「0」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「100」と距離D12100」とが一致するため、カウンタ一致検出回路DE12において、カウンタ一致検出回路DE13とバッファ23に一致検出信号m12_3(=1)が出力される。

【0159】
カウンタ一致検出回路DE13は、一致検出信号m12_3(=1)が入力されると、一致検出回路313において、全てのビットのカウンタ値と距離との一致の検出を開始する。カウンタ一致検出回路DE13の分周器312d,312e,312fは、図10Dに示すt4におけるカウンタ値「000」のビット値「0」,「0」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「000」と距離D13011」とは一致しないため、カウンタ一致検出回路DE13において、有効ビット設定部40に一致検出信号m13_3(=0)が出力される。

【0160】
一方、カウンタ一致検出回路DE21は、検索開始から6クロック目に、セレクタ312cを介してクロック信号CLKが入力されると、分周器312d,312e,312fは、図10Dに示すt6におけるカウンタ値「111」のビット値「1」,「1」,「1」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「111」と距離D21111」とは一致するため、カウンタ一致検出回路DE21において、カウンタ一致検出回路DE22とバッファ22に一致検出信号m21_3(=1)が出力される。

【0161】
カウンタ一致検出回路DE22は、一致検出信号m21_3(=1)が入力されると、一致検出回路313において、全てのビットのカウンタ値と距離との一致の検出を開始する。検索開始から3クロック目に、カウンタ一致検出回路DE22における分周器312d,312eのカウンタ値「00」と距離D22000」とが一致している。そのため、カウンタ一致検出回路DE22の分周器312d,312e,312fは、図10Dに示すt6におけるカウンタ値「000」のビット値「0」,「0」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「000」と距離D22000」とが一致するため、カウンタ一致検出回路DE22において、カウンタ一致検出回路DE23とバッファ23に一致検出信号m22_3(=1)が出力される。

【0162】
カウンタ一致検出回路DE23は、一致検出信号m22_3(=1)が入力されると、一致検出回路313において、全てのビットのカウンタ値と距離との一致の検出を開始する。検索開始から4クロック目に、カウンタ一致検出回路DE23における分周器312d,312eのカウンタ値「01」と距離D23010」とが一致している。そのため、カウンタ一致検出回路DE23の分周器312d,312e,312fは、図10Dに示すt6におけるカウンタ値「010」のビット値「0」,「1」,「0」をEXNOR回路313a,313b,313cにそれぞれ出力する。全ビットのカウンタ値「010」と距離D23010」とが一致するため、カウンタ一致検出回路DE23において、有効ビット設定部40に一致検出信号m23_3(=1)が出力される。

【0163】
有効ビット設定部40は、距離/クロック数変換回路DEから最下位ビットに対する一致検出信号m23_3(=1)を受けると、その一致検出信号を受けたタイミングで、距離/クロック数変換回路DEに対するタイミング信号CをWinner検出器20に出力する。

【0164】
このように、図10Aの例では、参照データ2について6クロックサイクルでタイミング信号Cが出力される。第1実施形態の方法を用いた場合には、参照データ2の場合、9クロックサイクル(=7+0+2)必要であったが、本実施形態の方法を用いると3クロックサイクル削減されている。

【0165】
一致検出回路313は、上位Jビット(1≦J≦N)について距離とカウンタ値との一致を検出した一致検出信号を出力する。下位からkビット目が一致検出の対象ビットとして設定されているとき、下位k-1ビットを無視した上位(N-(k-1))ビットの一致を示す一致検出信号を出力する。そのため、kビット目が対象ビットのときに全ての参照データについて一致検出信号が「0」であれば、全ての参照データは、距離2k-1以上の距離を持つことを意味する。この場合には、下位からkビット目のカウンタにクロック信号が入力されてカウントアップされる。これは、下位からkビット目が「1」になることを意味しており、1クロックサイクルで、距離2k-1が打ち消されたことに相当する。

【0166】
一方、いずれかの参照データについて出力された一致検出信号が「1」であれば、その参照データは、2k-1の距離がないことを意味する。この場合には、対象ビットを下位からk-1番目のビットに設定し、全ての参照データについて距離2k-2を順次打ち消す。

【0167】
つまり、最上位ビットから任意のビット単位に一致の検出対象となるビットを拡張して、カウンタ値と距離との一致を検出することで、大きい距離を順次打ち消している。これにより、第1、第2実施形態における一つの参照データの最長検索時間が”M×2N-1×τCLK”であるのに対し、本実施形態では、”(M×N+N-1)×τCLK”に削減することが可能になる。

【0168】
<第4実施形態>
第1実施形態及び第2実施形態では、式(1)を用いて算出された検索データと参照データとの各距離をクロック数に変換する処理を、その距離に一致する回数だけ繰り返すことで、各距離の二乗値の和、つまり、ユークリッド距離の和に相当するクロック数に変換する例について説明した。本実施形態では、各距離演算回路(DP11,DP12,…DPRW)において、各距離の二乗値の演算を行い、演算された各距離の二乗値を、距離/クロック数変換回路(DC,DC,…DC)においてクロック数に変換する例について説明する。

【0169】
図11は、本実施形態における距離演算回路の構成例を示す概略構成図である。距離演算回路DPij(1≦i≦R,1≦j≦W)は、例えば、距離が4ビットで表される場合、つまり、M=4の場合に、演算回路61~64を含む演算回路群60と、シフトレジスタ65と、乗数ビットシフト回路66とを有する。シフトレジスタ65は、3ビットのシフトレジスタであり、3つのフリップフロップ回路65a~65cを直列に接続して構成されている。

【0170】
図11の例において、演算回路61~64とフリップフロップ回路65a~65cは、この順に、最上位ビットから最下位ビット(全7ビット)に対応して並んでいる。演算回路61~64には、それぞれ、参照データ(Re)を反転させた反転参照データ(ReSQ)と、検索データ(In)の各ビットの値が入力される。なお、Sは1≦S≦4を満たす整数である。

【0171】
演算回路61~64は、制御回路(図示せず)から入力される二乗計算制御信号SQの信号値が「0」である場合、入力される反転参照データと検索データの絶対値差(AD,AD,AD,AD)を算出する。つまり、この場合には、演算回路61~64は減算器として機能する。

【0172】
また、制御回路(図示せず)から入力される二乗計算制御信号SQの信号値が「1」である場合、演算回路61~64は、加算器として機能する。つまり、演算回路61は、入力される後述の被加算値M1と、シフト演算値TEとを加算し、加算結果を、シフト演算値TEとして演算回路62に出力する。演算回路62は、入力される被加算値M2と、演算回路61から入力されるシフト演算値TEとを加算し、加算結果を、シフト演算値TEとして演算回路63に出力する。演算回路63は、入力される被加算値M3と、演算回路62から入力されるシフト演算値TEとを加算し、加算結果を、シフト演算値TEとして演算回路64に出力する。演算回路64は、入力される被加算値M4と、演算回路63から入力されるシフト演算値TEとを加算し、加算結果を、シフト演算値TEとしてシフトレジスタ65のフリップフロップ回路65aに出力する。

【0173】
また、演算回路61~64は、制御回路(図示せず)からマンハッタン距離(MD)又はユークリッド距離(ED)を示す制御信号を受ける。本実施形態において、マンハッタン距離(MD)の場合の信号値を「1」とし、ユークリッド距離(ED)の場合の信号値を「0」とする。演算回路61~64は、制御信号に応じて上記絶対値差AD又は加算結果を示すDOUT(0≦k≦4)を距離/クロック数変換回路DCに出力する。

【0174】
フリップフロップ回路65aは、演算回路64から入力されるシフト演算値TEを、クロック信号CLKに同期して、シフト演算値TEとしてフリップフロップ回路65bに出力するとともに、シフト演算値TEを示す出力値DOUTを距離/クロック数変換回路DCに出力する。

【0175】
フリップフロップ回路65bは、フリップフロップ回路65aから入力されるシフト演算値TEを、クロック信号CLKに同期して、シフト演算値TEとしてフリップフロップ回路65cに出力するとともに、そのシフト演算値TEを示す出力値DOUTを距離/クロック数変換回路DCに出力する。

【0176】
フリップフロップ回路65cは、フリップフロップ回路65bから入力されるシフト演算値TEを、クロック信号CLKに同期して、シフト演算値TEを出力値DOUTとして距離/クロック数変換回路DCに出力する。

【0177】
つまり、二乗計算制御信号SQ(=1)が入力されると、演算回路61~64においてシフト演算値TEを算出し、演算回路61~64及びシフトレジスタ65において、1クロックごとに、各シフト演算値を下位方向に1ビットシフトさせる処理を行う。この処理は、二乗計算の終了を示す信号が制御回路(図示せず)から入力されるまで行われる。

【0178】
ここで、演算回路61~64の回路構成について説明する。図12は、演算回路61~64の回路構成例を示す図である。図12の例において、演算回路61~64は、マルチプレクサ71,72,78と、全加算器73と、Dフリップフロップ回路74と、反転制御回路75と、ラッチ回路76と、AND回路77とを有する。

【0179】
マルチプレクサ71は、検索データIn(Sは1≦S≦4を満たす整数)と、シフト演算値TES-1とを受ける。マルチプレクサ72は、参照データREを反転させた反転参照データReSQと、AND回路77から入力される被加算値Mとを受ける。

【0180】
マルチプレクサ71,72は、制御回路(図示せず)から二乗計算制御信号SQが入力される。本実施形態において、二乗計算制御信号SQの信号値が「1」の場合には、距離演算回路DPijにおいて、距離の二乗計算を行い、信号値が「0」である場合には距離演算回路DPijにおいて、参照データと検索データとの差の絶対値(絶対値差)を算出する。

【0181】
マルチプレクサ71は、二乗計算制御信号SQの信号値が「0」の場合、検索データInを全加算器73に出力し、信号値が「1」の場合には、シフト演算値TES-1を全加算器73に出力する。マルチプレクサ72は、二乗計算制御信号SQの信号値が「0」の場合、反転参照データReSQを全加算器73に出力し、信号値が「1」の場合には、被加算値Mを全加算器73に出力する。

【0182】
全加算器73は、下位ビットからの桁上げ値を受ける端子CBと、上位ビットへ桁上げ値を出力する端子CN又はCAを有する。なお、演算回路64における端子CBは、下位ビットからの桁上げ値ではなく、演算回路61における桁上げ値が入力される。演算回路61は最上位ビットに対応するため、演算回路61における桁上げ値を端子CAから演算回路64へ出力する。

【0183】
また、演算回路64における端子CBは、AND回路64a(図11参照)と接続されている。AND回路64aには、制御回路(図示せず)からの制御信号(MD又はED)と、演算回路61の端子CAから出力される桁上げ値とが入力され、制御信号の信号値と桁上げ値の論理積を演算した結果を出力する。

【0184】
つまり、演算回路61~64における全加算器73は、マルチプレクサ71から出力される検索データIn又はシフト演算値TES-1と、マルチプレクサ72から出力される反転参照データReSQ又は被加算値Mと、入力される桁上げ値とを加算する。以下、演算回路61~64における全加算器73のより具体的な処理について説明する。

【0185】
演算回路61は、最上位ビットに対応するため、上位ビットにおけるシフト演算値がマルチプレクサ71に入力されない。そのため、演算回路61では、信号値「1」を示す二乗計算制御信号SQが制御回路(図示せず)から出力されると、シフト演算値TEとして「0」を入力する。従って、演算回路61における全加算器73は、マルチプレクサ72から出力される被加算値Mと、端子CBから入力される演算回路62の桁上げ値と、シフト演算値TE(=0)を加算し、加算結果をDフリップフロップ回路74に出力する。

【0186】
演算回路62,63における各全加算器73は、信号値「1」を示す二乗計算制御信号SQが制御回路から出力されると、それぞれ、マルチプレクサ72から出力される被加算値M,Mと、端子CBから入力される演算回路63,64の桁上げ値と、演算回路61,62から入力されるシフト演算値TE,TEを加算して、加算結果をDフリップフロップ回路74に出力する。

【0187】
演算回路64における全加算器73は、信号値「1」を示す二乗計算制御信号SQが制御回路から出力されると、マルチプレクサ72から出力される被加算値Mと、端子CBを介してAND回路64aから入力される値と、演算回路63から入力されるシフト演算値TEとを加算して、加算結果をDフリップフロップ回路74に出力する。つまり、マンハッタン距離(MD)を示す制御信号(=1)がAND回路(図示せず)に入力され、演算回路61の端子CAからの桁上げ値「1」がAND回路(図示せず)に入力されると、演算回路64の端子CBに「1」が入力されて加算される。

【0188】
次に、演算回路61~64における反転制御回路75は、演算回路61からの最上位ビットの桁上げ値を示す信号を受ける端子CAを有し、端子CAを介して入力される演算回路61の桁上げ値=「0」である場合には、全加算器73から出力された算出結果を反転し、反転した値(絶対値差AD)をラッチ回路76へ出力する。また、演算回路61の桁上げ値=「1」である場合には、全加算器73から出力された算出結果を反転せずにラッチ回路76へ出力する。

【0189】
演算回路61~64におけるラッチ回路76は、二乗計算制御信号SQを受ける。ラッチ回路76は、二乗計算制御信号SQの信号値が「0」から「1」になるタイミングで、反転制御回路75から出力された絶対値差(AD)を保存する。そして、AND回路77と乗数ビットシフト回路66とマルチプレクサ78にその絶対値差(AD)を出力する。

【0190】
演算回路61~64におけるAND回路77は、乗数ビットシフト回路66から入力される乗数ビットMBと、ラッチ回路76から入力される絶対値差(AD)との論理積の値をマルチプレクサ72に出力する。

【0191】
絶対値差ADが算出された後、制御回路(図示せず)により、演算回路61~64におけるDフリップフロップ回路74にクロック信号CLKが入力される。演算回路61~64におけるDフリップフロップ回路74は、クロック信号CLKのクロックが立ち上がるタイミングで、全加算器73から出力される加算結果を入力する。そして、クロックが立ち下がるタイミングで、その加算結果が、シフト演算値(TE)として、下位ビットの演算回路におけるマルチプレクサ71又はシフトレジスタ65に出力される。

【0192】
演算回路61~64におけるマルチプレクサ78は、制御回路(図示せず)からマンハッタン距離(MD)又はユークリッド距離(ED)を示す制御信号を受ける。例えば、この例において、マンハッタン距離(MD)の場合の信号値を「1」とし、ユークリッド距離(ED)の場合の信号値を「0」とする。マルチプレクサ78は、マンハッタン距離(MD)を示す制御信号(=1)が入力されると、演算回路61~64における各ラッチ回路76から出力される算出結果(絶対値差AD)を出力する。また、マルチプレクサ78は、ユークリッド距離(ED)を示す制御信号(=0)が入力されると、演算回路61~64における各Dフリップフロップ回路74から出力される算出結果(TE)を出力する。

【0193】
乗数ビットシフト回路66は、クロック信号CLKに同期して、演算回路61~64におけるラッチ回路76から出力される絶対値差ADの値を受ける。乗数ビットシフト回路66は、下位ビットから順に、つまり、絶対値差AD→AD→AD→ADの順に、その絶対値差を乗数ビットMBとしてAND回路77に出力する。乗数ビットシフト回路66は、最上位ビットの絶対値差(AD)の値を出力すると、制御回路(図示せず)に二乗計算の終了を示す信号を出力する。

【0194】
AND回路77は、乗数ビットシフト回路66から入力される乗数ビットMBと、ラッチ回路76から入力される絶対値差ADとの論理積の値を、被加算値Mとしてマルチプレクサ72に出力する。

【0195】
図13は、距離演算回路DPijにおける二乗計算の処理過程を示す図である。この例では、検索データと参照データとの絶対値差AD=710=0111である場合を示している。図13の例では、演算回路61~64の各AND回路77には、クロック信号CLKに同期して、絶対値差の下位ビットから「1→1→1→0」の順に、乗数ビットMBが乗数ビットシフト回路66によって入力される。また、演算回路61~64のマルチプレクサ71には、シフト演算値TES-1として初期値「0」が設定されている。

【0196】
距離演算回路DPijは、二乗計算制御信号SQ(=1)が制御回路から入力されると二乗計算を開始する。演算回路61~64において、各マルチプレクサ71に設定されているシフト演算値TES-1「0000」が、全加算器73に入力される(ステップS1)。また、演算回路61~64のAND回路77から、乗数ビット”1”と絶対値差AD「0111」との論理積を示す被加算値M「0111」が各マルチプレクサ72に入力され、各マルチプレクサ72から全加算器73に被加算値M「0111」が入力される(ステップS2)。演算回路61~64の全加算器73において、シフト演算値TES-1「0000」と被加算値M「0111」が加算されて出力される。加算結果「0111」は、1クロック目が立ち上がるタイミングで演算回路61~64のDフリップフロップ回路74にそれぞれ入力され、1クロック目が立ち下がるまで保持される(ステップS3)。

【0197】
1クロック目が立ち下がると、演算回路61~64のAND回路77から、乗数ビット”1”と絶対値差AD「0111」の論理積を示す被加算値M「0111」が各マルチプレクサ72に入力され、各マルチプレクサ72から全加算器73に被加算値M「0111」が入力される(ステップS4)。また、ステップS3において、演算回路61~64のDフリップフロップ回路74に保持されている加算結果「0111」は、シフト演算値TEとして、演算回路62~64のマルチプレクサ71と、シフトレジスタ65のフリップフロップ回路65aとに出力される(ステップS5)。

【0198】
1クロック目の立ち下がりから2クロック目が立ち上がるまで、演算回路61~64の全加算器73において、被加算値M「0111」とシフト演算値TES-1「0111」とが加算されて出力される。加算結果「1010」は、2クロック目が立ち上がるタイミングで、演算回路61~64のDフリップフロップ回路74に入力され、2クロック目が立ち下がるまで保持される。また、シフトレジスタ65のフリップフロップ回路65aに入力されたシフト演算値TE「1」は、2クロック目が立ち下がるまで保持される(ステップS6)。

【0199】
2クロック目が立ち下がると、演算回路61~64のAND回路77から、乗数ビット”1”と絶対値差「0111」の論理積を示す被加算値M「0111」が各マルチプレクサ72に入力され、各マルチプレクサ72から各全加算器73に被加算値M「0111」が入力される(ステップS7)。

【0200】
また、2クロック目が立ち下がると、ステップS6において、演算回路61~64のDフリップフロップ回路74に保持されている加算結果「1010」は、シフト演算値TEとして、演算回路62~64のマルチプレクサ71とフリップフロップ回路65aに出力される。演算回路61~64のマルチプレクサ71は、シフト演算値TE,TE,TE,TEとして「0,1,0,1」を全加算器73に入力する。フリップフロップ回路65aは、保持しているシフト演算値TE「1」をシフト演算値TE(=DOUT)としてフリップフロップ回路65bに出力し、演算回路64から出力されたシフト演算値TE「0」を入力する(ステップS8)。

【0201】
2クロック目の立ち下がりから3クロック目が立ち上がるまで、演算回路61~64の全加算器73において、被加算値M「0111」とシフト演算値TES-1「0101」とが加算されて出力される。加算結果「1100」は、3クロック目が立ち上がるタイミングで演算回路61~64のDフリップフロップ回路74に入力され、3クロック目が立ち下がるまで保持される。また、フリップフロップ回路65aにおいて、演算回路64からのシフト演算値TE「0」は、3クロック目が立ち下がるまで保持される。フリップフロップ回路65bにおいて、フリップフロップ回路65aからのシフト演算値TE「1」は3クロック目が立ち下がるまで保持される(ステップS9)。

【0202】
3クロック目が立ち下がると、演算回路61~64のAND回路77から、乗数ビット”0”と絶対値差「0111」の論理積を示す被加算値M「0000」が各マルチプレクサ72に入力され、各マルチプレクサ72から全加算器73に被加算値M「0000」が入力される(ステップS10)。

【0203】
また、ステップS9において、演算回路61~64のDフリップフロップ回路74に保持されている加算結果「1100」は、3クロック目が立ち下がると、シフト演算値TEとして、演算回路62~64のマルチプレクサ71とフリップフロップ回路65aに出力される。演算回路61~64のマルチプレクサ71は、シフト演算値TE,TE,TE,TEとして「0,1,1,0」を全加算器73に入力する。フリップフロップ回路65aは、保持しているシフト演算値TE「0」をシフト演算値TEとして出力し、演算回路64から出力されたシフト演算値TE「0」を入力する。フリップフロップ回路65bは、保持しているシフト演算値TE「1」をシフト演算値TE(=DOUT)として出力し、フリップフロップ回路65aから出力されたシフト演算値TE「0」を入力する。フリップフロップ回路65cは、フリップフロップ回路65bから出力されたシフト演算値TE「1」を入力する(ステップS11)。

【0204】
3クロック目が立ち下がっている間、乗数ビットシフト回路66から乗数ビットMB”0”が各演算回路61~64に出力されると、二乗計算の終了を示す信号が制御回路(図示せず)に出力される。3クロック目の立ち下がりから4クロック目が立ち上がるまで、演算回路61~64の全加算器73において、被加算値M「0000」とシフト演算値TES-1「0110」とが加算されて出力される。4クロック目が立ち上がると、加算結果「0110」は、それぞれシフト演算値TE,TE,TE,TEとして、Dフリップフロップ回路74に出力される(ステップS12)。シフトレジスタ65には、ステップS11において入力されたシフト演算値TE,TE,TEの各値(0,0,1)が、シフト演算値TE,TE,TEとして保持される。

【0205】
4クロック目が立ち下がると、演算回路61~64において、それぞれのDフリップフロップ回路74に保持されているシフト演算値TE,TE,TE,TEは、それぞれのマルチプレクサ78に出力され、DOUT=0,DOUT=0、DOUT=1、DOUT=1、DOUT=0として距離/クロック数変換回路DCに出力される。また、シフトレジスタ65において、フリップフロップ回路65a~65cに保持されているシフト演算値TE「0」,TE「0」,TE「1」についても、4クロック目が立ち下がると、それぞれ、DOUT=0、DOUT=0、DOUT=1として、距離/クロック数変換回路DCに出力される。つまり、DOUT~DOUTは、絶対値差(=710)の二乗値(=4910)を示す距離信号Dijとして距離/クロック数変換回路DCに出力される。

【0206】
距離/クロック数変換回路DCは、距離演算回路DPijから出力される絶対値差の二乗値をクロック数に変換する。図14は、図2Aに示す距離/クロック数変換回路DCにおけるカウンタ一致検出回路31の概略構成を示す図である。図14に示すように、カウンタ一致検出回路31は、カウンタ311と一致検出回路3121とを含む。

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

【0208】
一致検出回路3121は、バッファ21からクロック信号CLKを受け、制御回路(図示せず)から検索開始信号SBを受ける。また、一致検出回路3121は、カウンタ311からカウンタ値CV11を受け、距離演算回路DP11から距離信号D11を受ける。一致検出回路3121は、検索開始信号SBが立ち上がると、距離信号D11に一致するカウンタ値CV11が得られるときのクロック信号CLKのクロック数をカウントする。そして、一致検出回路3121は、そのクロック数をカウントしたタイミングを示す一致信号MTH1をカウンタ一致検出回路32へ出力する。一致検出回路3121は、一致信号MTH1を出力すると動作を停止する。

【0209】
なお、図2Aに示すカウンタ一致検出回路32~3Wの各々についても、図14に示すカウンタ一致検出回路31と同様の構成を有する。カウンタ一致検出回路32~3Wは、それぞれ、カウンタ一致検出回路31~3W-1の一致検出回路3121から一致信号MTH1~MTHW-1を受けるまで動作を停止し、一致信号MTH1~MTHW-1を受けると駆動して動作を開始する。

【0210】
カウンタ一致検出回路3Wから一致信号MTHWが出力されるタイミングで、距離/クロック数変換回路DCに対するタイミング信号CがWinner検出器20へ出力される。つまり、タイミング信号Cは、距離/クロック数変換回路DCに入力される距離信号Di1~DiWが示す各絶対値差の二乗値の和、すなわち、ユークリッド距離値の和に相当するクロック数が得られるタイミングで出力される。

【0211】
上記の例では、ユークリッド距離を用いて検索を行う例を説明したが、図12に示す演算回路61~64のマルチプレクサ78に、マンハッタン距離を示す制御信号(MD)が制御回路(図示せず)から入力される場合には、各マルチプレクサ78から、検索データと参照データの絶対値差(AD~AD)で表される距離信号Dijが出力される。その場合も、ユークリッド距離と同様、距離/クロック数変換回路DCにおいて、距離信号Dijに一致するカウンタ値CVijが得られるときのクロック信号CLKのクロック数をカウントすればよい。

【0212】
上述した第4実施形態では、距離演算回路において、検索データと参照データとの絶対値差の演算を行うとともに、絶対値差の二乗演算を行うことができる。そのため、絶対値差の演算と絶対値差の二乗演算とを別個の回路によって実現する場合等と比べて回路面積を小さくすることができる。また、マンハッタン距離とユークリッド距離のいずれを用いた検索にも適用することができる。

【0213】
<変形例>

【0214】
(1)上述した第1実施形態では、ユークリッド距離を用いた検索を行う例について説明したが、マンハッタン距離とユークリッド距離のいずれを用いても検索されるように構成してもよい。図15は、本変形例におけるカウンタ一致検出回路の構成例を示す概略図である。カウンタ一致検出回路31は、デマルチプレクサ31xを有し、カウンタ一致検出回路32は、デマルチプレクサ32xを有する。

【0215】
デマルチプレクサ31x,32xには、マンハッタン距離かユークリッド距離かを示す制御信号SLが制御回路(図示せず)から入力される。クロック数変換回路31aにおいて、距離信号D11とクロック数とが一致すると、デマルチプレクサ31xにHレベルの一致検出信号を出力する。デマルチプレクサ31xは、入力された制御信号がマンハッタン距離を示す場合には、クロック数変換回路31aから出力される一致検出信号をバッファ22とクロック数変換回路31aに出力して動作を停止する。

【0216】
カウンタ一致検出回路31から一致検出信号が出力されると、バッファ22からクロック数変換回路32aにクロック信号CLKが入力される。クロック数変換回路32aにおいて、距離信号D12とクロック数とが一致すると、デマルチプレクサ32xにHレベルの一致検出信号を出力する。デマルチプレクサ32xは、入力された制御信号がマンハッタン距離を示す場合には、クロック数変換回路32aからのHレベルの一致検出信号が入力されたタイミングでWinner検出器20にタイミング信号Cを出力して動作を停止する。

【0217】
なお、ユークリッド距離を示す制御信号がデマルチプレクサ31x,32xに入力された場合には、マルチプレクサ31x,32xは、クロック数変換回路31a,32aからのHレベルの一致検出信号をカウンタ31b,32bにそれぞれ出力し、上述した第1実施形態と同様、カウンタ31b,32bのカウンタ値と距離信号D11,D12とが一致するまで動作を繰り返す。

【0218】
(2)上述した第3実施形態では、距離とカウンタ値との一致検出の際、最上位ビットから下位方向に1ビットずつ対象ビットを拡張する例について説明したが、複数ビット単位に対象ビットを拡張するようにしてもよい。また、対象ビットを拡張するごとに、拡張するビットの数が異なっていてもよい。例えば、距離とカウンタ値とが6ビット長である場合において、最上位のビットについて一致の検索を行い、いずれかの参照データについての一致検出信号が立ち上がると、2番目と3番目の2つのビットを対象ビットとし、上位3ビットまで拡張する。そして、いずれかの参照データについて、上位3ビットに対する一致検出信号が立ち上がると、4番目~6番目の3つのビットを次の検索対象のビットとし、全ビットに対象ビットを拡張する。
【産業上の利用可能性】
【0219】
この発明は、連想メモリに適用される。
【符号の説明】
【0220】
1…メモリ部、2…行デコーダ、3…列デコーダ、4…読出/書込回路、5…検索データ保存回路、6,77,64a,300c,313d,313e…AND回路、10…メモリアレイ部、20…Winner検出器、21~2W…バッファ,31~3W,…カウンタ一致検出回路、31a,32a…クロック数変換回路、31b,32b,300b,311,312…カウンタ、31c,31c’,32c,32c’,313,3121…一致検出回路、40…有効ビット設定部、61~64…演算回路、65…シフトレジスタ、65a,65b,65c…フリップフロップ回路、66…乗数ビットシフト回路、71,72,78,31d,32d,300a,314…マルチプレクサ、73…全加算器、74…Dフリップフロップ回路、75…反転制御回路、76…ラッチ回路、300…カウンタ一致検出ユニット、310,320…距離/クロック数変換ユニット、312a~312c…セレクタ、312d~312f…分周器、313a~313c…EXNOR回路、DC~DC,DE~DE…距離/クロック数変換回路、DE11~DE1W…カウンタ一致検出回路、DP11~DPRW…距離演算回路
図面
【図1】
0
【図2A】
1
【図2B】
2
【図3】
3
【図4】
4
【図5A】
5
【図5B】
6
【図6】
7
【図7】
8
【図8】
9
【図9A】
10
【図9B】
11
【図10A】
12
【図10B】
13
【図10C】
14
【図10D】
15
【図11】
16
【図12】
17
【図13】
18
【図14】
19
【図15】
20