(57)【要約】【課題】ユークリッド距離を用いた場合でも正確に類似検索を行うことが可能な連想メモリを提供すること。【解決手段】連想メモリ１００は、Ｍ×Ｗ（Ｍは１以上の整数、Ｗは２以上の整数）ビットのビット長を有するＲ（Ｒは２以上の整数）個の参照データと、Ｍ×Ｗビットのビット長を有する検索データとのマンハッタン距離を算出する距離演算回路ＤＰ１１〜ＤＰＲＷと、距離／クロック数変換回路ＤＣ１〜ＤＣＲとを備える。距離／クロック数変換回路ＤＣ１〜ＤＣＲの各々は、対応する距離演算回路で算出されるマンハッタン距離を用い、参照データと検索データとのユークリッド距離に一致するクロック数を検出する。距離／クロック数変換回路は、参照データについて、検索データとのユークリッド距離と一致するクロック数を検出したタイミングを示すタイミング信号を出力する。【選択図】図１
2014154196.tif 000002
【特許請求の範囲】
【請求項１】
各々がＭ×Ｗ（Ｍは１以上の整数、Ｗは２以上の整数）ビットのビット長を有するＲ（Ｒは２以上の整数）個の参照データを保存する参照データ保存手段と、
前記Ｒ個の参照データに対応して設けられ、Ｍ×Ｗビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すＲ×Ｗ個の絶対値差を、前記検索データと前記参照データの距離として算出する第１距離算出手段と、
前記参照データごとに、前記第１距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記Ｒ個の参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるＲ個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、ｋ個（ｋは１≦ｋ＜Ｒを満たす整数）の前記タイミング信号を検出し、検出した前記ｋ個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
【請求項２】
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記各参照データにつき、前記Ｗ個の絶対値差の各々に一致する回数だけ、前記絶対値差と一致するクロック数を検出する処理を繰り返すことにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項１に記載の連想メモリ。
【請求項３】
前記各参照データにつき、前記第１距離算出手段で算出された前記Ｗ個の絶対値差の各々の二乗値を算出することにより、前記検索対象の検索データと前記参照データとの距離として、前記Ｗ個の絶対値差の二乗値を算出する第２距離算出手段を更に備え、
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記参照データごとに、前記第２距離算出手段で算出された前記Ｗ個の前記絶対値差の二乗値の和に一致するクロック数を検出することにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項１に記載の連想メモリ。
【請求項４】
マンハッタン距離とユークリッド距離のいずれかの距離を選択する選択手段を備え、
前記タイミング信号出力手段は、前記選択手段によって前記マンハッタン距離が選択された場合には、前記各参照データにつき、前記Ｗ個の絶対値差の和に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力し、前記選択手段によって前記ユークリッド距離が選択された場合には、前記各参照データについて前記タイミング信号出力処理を行う、請求項１から請求項３のいずれか一項に記載の連想メモリ。
【請求項５】
各々がＭ×Ｗ（Ｍは１以上の整数、Ｗは２以上の整数）ビットのビット長を有するＲ（Ｒは２以上の整数）個の参照データを保存する参照データ保存手段と、
前記Ｒ個の参照データに対応して設けられ、Ｍ×Ｗビットのビット長を有する検索対象の検索データと前記参照データとのＲ×Ｗ個の距離を算出する距離算出手段と、
前記参照データごとに、前記距離算出手段で算出された距離を表すビットのうち、設定された対象ビットの値と一致するクロック数を検出したタイミングで一致検出信号を出力する一致検出手段と、
前記各参照データについて算出された前記距離を表す最上位ビットから順に、予め定められたビット単位に前記対象ビットを設定し、いずれかの前記参照データについて、前記対象ビットに対する前記一致検出信号が出力される毎に、前記対象ビットを拡張するビット設定手段と、
前記各参照データについて、前記距離を表す全てのビットに対する前記一致検出信号が出力されたタイミングを示すタイミング信号を出力する処理を、Ｒ個の前記参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるＲ個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、ｋ個（ｋは１≦ｋ＜Ｒを満たす整数）の前記タイミング信号を検出し、検出した前記ｋ個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、連想メモリに関するものである。
【背景技術】
【０００２】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）上で実現することにより、将来、人工知能およびモバイル機器等の高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【０００３】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【０００４】
前者は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）と呼ばれ、ネットワークルータのＩＰアドレステーブルのルーティングおよびプロセッサのキャッシュ等の実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ）と呼ぶ。
【０００５】
連想メモリを実現する手段として（１）ディジタル方式による実現方法（非特許文献１）、（２）アナログ方式による実現方法および（３）ディジタル・アナログ融合方式（非特許文献２）等が提案されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】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.
【非特許文献２】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.
【非特許文献３】Y. Oike et al., “A Word-Parallel Digital Associative Engine with Wide SearchRange Based on Manhattan Distance,”CICC, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に記載の連想メモリは、検索データと参照データとのハミング距離を用いて類似検索を行うものである。そのため、非特許文献１に記載の連想メモリにおいて、ユークリッド距離を用いて類似検索を行うことは困難である。非特許文献２に記載の連想メモリは、検索データと参照データとの類似度を表す距離を電圧に変換するため、誤検索が生じやすい。
【０００８】
そこで、本発明は、かかる問題を解決するためになされたものであり、その目的は、ユークリッド距離を用いた場合でも正確に類似検索を行うことが可能な連想メモリを提供することである。
【課題を解決するための手段】
【０００９】
この発明の実施の形態による連想メモリは、各々がＭ×Ｗ（Ｍは１以上の整数、Ｗは２以上の整数）ビットのビット長を有するＲ（Ｒは２以上の整数）個の参照データを保存する参照データ保存手段と、前記Ｒ個の参照データに対応して設けられ、Ｍ×Ｗビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すＲ×Ｗ個の絶対値差を、前記検索データと前記参照データの距離として算出する第１距離算出手段と、前記参照データごとに、前記第１距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記Ｒ個の参照データについて行うタイミング信号出力手段と、前記タイミング信号出力手段から出力されるＲ個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、ｋ個（ｋは１≦ｋ＜Ｒを満たす整数）の前記タイミング信号を検出し、検出した前記ｋ個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、を備える。
【発明の効果】
【００１０】
この発明の実施の形態による連想メモリにおいては、タイミング信号出力手段は、第１距離算出手段で算出された、各参照データと検索データとの絶対値差を用いて、参照データごとに、検索データとのユークリッド距離に一致するクロック数を検出したタイミングでタイミング信号を出力する。すなわち、タイミング信号出力手段は、各参照データについて算出された絶対値差を、参照データと検索データとのユークリッド距離に相当するクロック数に変換し、変換したクロック数が得られるタイミングでタイミング信号を出力する。その結果、参照データと検索データとのユークリッド距離の大きさに応じて、その参照データのタイミング信号の出力タイミングが決まり、各参照データについて、ユークリッド距離を用いた検索を適切に行うことができる。
【００１１】
従って、本発明の実施の形態によれば、ユークリッド距離を用いた場合でも正確に類似検索を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】第１実施形態に係る連想メモリの構成を示す概略ブロック図である。
【図２Ａ】図２Ａは、図１に示す距離／クロック数変換回路の構成を示す概略図である。
【図２Ｂ】図２Ｂは、図２Ａに示すカウンタ一致検出回路の構成例を示す概略図である。
【図３】図３は、図１に示すＷｉｎｎｅｒ検出器の動作を説明するための図である。
【図４】図４は、第２実施形態における距離／クロック数変換回路の構成を示す概略図である。
【図５Ａ】図５Ａは、第１、第２実施形態の場合の検索時間を表す図である。
【図５Ｂ】図５Ｂは、第３実施形態の場合の検索時間を表す図である。
【図６】図６は、第３実施形態に係る連想メモリの構成を示す概略ブロック図である。
【図７】図７は、図６に示す距離／クロック数変換回路の構成例を示す概略図である。
【図８】図８は、図７に示すカウンタ一致検出回路の構成例を示す概略図である。
【図９Ａ】図９Ａは、図８に示すカウンタと一致検出回路の構成例を示す概略図である。
【図９Ｂ】図９Ｂは、図９Ａに示すカウンタの動作例を示す図である。
【図１０Ａ】図１０Ａは、第３実施形態における距離／クロック数変換回路の動作例を説明する図である。
【図１０Ｂ】図１０Ｂは、図１０Ａに示す例におけるカウンタの動作例を示す図である。
【図１０Ｃ】図１０Ｃは、図１０Ａに示す例におけるカウンタの動作例を示す図である。
【図１０Ｄ】図１０Ｄは、図１０Ａに示す例におけるカウンタの動作例を示す図である。
【図１１】図１１は、第４実施形態における距離演算回路の回路構成例を示す概略図である。
【図１２】図１２は、図１１に示す演算回路の回路構成例を示す概略図である。
【図１３】図１３は、第４実施形態における二乗計算の処理過程を説明する図である。
【図１４】図１４は、第４実施形態におけるカウンタ一致検出回路の構成例を示す概略図である。
【図１５】図１５は、変形例（１）における距離／クロック数変換回路の構成例を示す概略図である。
【発明を実施するための形態】
【００１３】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。
【００１４】
＜第１実施形態＞
図１は、この発明の実施の形態による連想メモリの構成を示す概略ブロック図である。図１を参照して、この発明の第１実施形態による連想メモリ１００は、メモリアレイ部１０と、Ｗｉｎｎｅｒ検出器２０とを備える。
【００１５】
メモリアレイ部１０は、メモリ部１、行デコーダ２、列デコーダ３、読出／書込回路４、及び検索データ保存回路５を含む。
【００１６】
メモリ部１は、参照データ保存回路（Ｓｔｏｒａｇｅ  Ｃｅｌｌ：ＳＣ）ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，・・・，ＳＣＲ１〜ＳＣＲＷと、距離演算回路（絶対値差演算回路）（Ｄｉｓｔａｎｃｅ  Ｐｒｏｃｅｓｓｏｒ：ＤＰ）ＤＰ１１〜ＤＰ１Ｗ，ＤＰ２１〜ＤＰ２Ｗ，・・・，ＤＰＲ１〜ＤＰＲＷと、距離／クロック数変換回路ＤＣ１〜ＤＣＲとを含む。なお、ＷおよびＲの各々は、２以上の整数である。
【００１７】
距離演算回路ＤＰ１１〜ＤＰ１Ｗは、それぞれ、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗに対応して設けられる。また、距離演算回路ＤＰ２１〜ＤＰ２Ｗは、それぞれ、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗに対応して設けられる。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、それぞれ、参照データ保存回路ＳＣＲ１〜ＳＣＲＷに対応して設けられる。
【００１８】
距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１〜ＤＰ１Ｗに対応して設けられる。距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１〜ＤＰ２Ｗに対応して設けられる。以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１〜ＤＰＲＷに対応して設けられる。
【００１９】
参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，・・・，ＳＣＲ１〜ＳＣＲＷは、行デコーダ２、列デコーダ３および読出／書込回路４によって書き込まれた参照データを保存する。この場合、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗは、Ｍ×Ｗ（Ｍは１以上の整数）ビットの参照データ１を保存し、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗは、Ｍ×Ｗビットの参照データ２を保存し、以下、同様にして、参照データ保存回路ＳＣＲ１〜ＳＣＲＷは、Ｍ×Ｗビットの参照データＲを保存する。つまり、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，・・・，ＳＣＲ１〜ＳＣＲＷの各々は、参照データのＭビットを保存する。
【００２０】
距離演算回路ＤＰ１１〜ＤＰ１Ｗは、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗに保存されたＭ×Ｗビットの参照データ１と、検索データ保存回路５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。また、距離演算回路ＤＰ２１〜ＤＰ２Ｗは、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗに保存されたＭ×Ｗビットの参照データ２と、検索データ保存回路５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、参照データ保存回路ＳＣＲ１〜ＳＣＲＷに保存されたＭ×Ｗビットの参照データＲと、検索データ保存回路５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。そして、距離演算回路ＤＰ１１〜ＤＰ１Ｗ、距離演算回路ＤＰ２１〜ＤＰ２Ｗ、・・・、および距離演算回路ＤＰＲ１〜ＤＰＲＷにおける参照データと検索データとの距離の演算は、並列に行なわれる。
【００２１】
そして、距離演算回路ＤＰ１１〜ＤＰ１Ｗは、参照データ１と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ１へ出力する。距離演算回路ＤＰ２１〜ＤＰ２Ｗは、参照データ２と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ２へ出力する。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、参照データＲと検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣＲへ出力する。
【００２２】
距離演算回路ＤＰ１１〜ＤＰ１Ｗの各々は、参照データ１と検索データとの距離を次式を用いて演算する。
【００２３】
【数１】
2014154196.tif 000003
【００２４】
式（１）において、Ｄｒｊ（ｒ＝１〜Ｒ，ｊ＝１〜Ｗ）は、参照データと検索データとの距離（絶対値差）を表す。ｎＭｒは参照データと検索データとのマンハッタン距離を示している。また、式（１）において、Ｉｎｊは、検索データであり、Ｒｅｒｊは、参照データである。各データＩｎｊ，Ｒｅｒｊの各々は、Ｍビットからなる。
【００２５】
このように、距離演算回路ＤＰ１１〜ＤＰ１Ｗは、Ｍ×Ｗビットの参照データ１と、Ｍ×Ｗビットの検索データとの距離をＭビットずつ演算し、各々がＭビットのビット長を有するＷ個の距離信号Ｄ１ｊを距離／クロック数変換回路ＤＣ１へ出力する。
【００２６】
距離演算回路ＤＰ２１〜ＤＰ２Ｗ、・・・および距離演算回路ＤＰＲ１〜ＤＰＲＷも、同様にして、それぞれ、式（１）を用いて参照データ２〜Ｒと検索データとの距離を演算する。そして、距離演算回路ＤＰ２１〜ＤＰ２Ｗ、・・・および距離演算回路ＤＰＲ１〜ＤＰＲＷも、各々がＭビットのビット長を有するＷ個の距離信号Ｄ２ｊ〜ＤＲｊをそれぞれ距離／クロック数変換回路ＤＣ２〜ＤＣＲへ出力する。
【００２７】
距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１〜ＤＰ１ＷからＷ個の距離信号Ｄ１ｊを受け、各距離信号Ｄ１ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ１を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ１をカウントしたタイミングを示すタイミング信号Ｃ１をＷｉｎｎｅｒ検出器２０へ出力する。
【００２８】
距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１〜ＤＰ２ＷからＷ個の距離信号Ｄ２ｊを受け、各距離信号Ｄ２ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ２を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ２をカウントしたタイミングを示すタイミング信号Ｃ２をＷｉｎｎｅｒ検出器２０へ出力する。
【００２９】
以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１〜ＤＰＲＷからＷ個の距離信号ＤＲｊを受け、各距離信号ＤＲｊの二乗値の和に一致するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌＲを後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌＲをカウントしたタイミングを示すタイミング信号ＣＲをＷｉｎｎｅｒ検出器２０へ出力する。
【００３０】
行デコーダ２は、メモリ部１の行方向のアドレスを指定する。列デコーダ３は、メモリ部１の列方向のアドレスを指定する。読出／書込回路４は、参照データを行デコーダ２および列デコーダ３によって指定された参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，・・・，ＳＣＲ１〜ＳＣＲＷに書き込むとともに、検索データを検索データ保存回路５に書き込む。
【００３１】
検索データ保存回路５は、読出／書込回路４によって書き込まれた検索データ（Ｍ×Ｗビットのデータ）を保存する。
【００３２】
Ｗｉｎｎｅｒ検出器２０は、タイミング信号Ｃ１〜ＣＲをそれぞれ距離／クロック数変換回路ＤＣ１〜ＤＣＲから受ける。そして、その受けたタイミング信号Ｃ１〜ＣＲのうち、一致タイミングが早い順にｋ（ｋは１≦ｋ＜Ｒを満たす整数）個のタイミング信号を検出し、その検出したｋ個のタイミング信号を検索データと参照データとの類似度を示すマッチ信号Ｍ１〜Ｍｋとして出力する。
【００３３】
図２Ａは、図１に示す距離／クロック数変換回路ＤＣ１の構成を表す概略構成図である。なお、図１に示す距離／クロック数変換回路ＤＣ２〜距離／クロック数変換回路ＤＣＲの各々も、図２Ａに示す距離／クロック数変換回路ＤＣ１と同様の構成を有する。図２Ａに示すように、距離／クロック数変換回路ＤＣ１は、バッファ２１〜２Ｗと、カウンタ一致検出回路３１〜３Ｗとを含む。
【００３４】
バッファ２１は、連想メモリ１００の制御回路（図示せず）から検索開始信号ＳＢを受け、連想メモリ１００に内蔵されたクロック発生回路（図示せず）からクロック信号ＣＬＫを受ける。そして、バッファ２１は、検索開始信号ＳＢがＬ（Ｌｏｗ）レベルからＨ（Ｈｉｇｈ）レベルに切り替わると、その受けたクロック信号ＣＬＫをバッファ２２およびカウンタ一致検出回路３１へ出力する。バッファ２２は、クロック信号ＣＬＫをバッファ２１から受け、カウンタ一致検出回路３１から、後述するＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けると、クロック信号ＣＬＫをバッファ２３（図示せず）及びカウンタ一致検出回路３２へ出力する。以下、同様にして、バッファ２Ｗは、クロック信号ＣＬＫをバッファ２Ｗ−１（図示せず）から受け、カウンタ一致検出回路３Ｗ−１（図示せず）から、後述するＨレベルの一致信号（ＤＥＴＥＣＴＷ−１）を受けると、クロック信号ＣＬＫをカウンタ一致検出回路３Ｗへ出力する。
【００３５】
カウンタ一致検出回路３１〜３Ｗは、それぞれ、距離演算回路ＤＰ１１〜ＤＰ１Ｗに対応して設けられる。そして、カウンタ一致検出回路３１〜３Ｗは、直列に接続される。ここで、カウンタ一致検出回路３１〜３Ｗの概略構成について説明する。
【００３６】
図２Ｂは、距離／クロック数変換回路ＤＣ１におけるカウンタ一致検出回路３１〜３Ｗの構成例を示す図である。図２Ｂの例では、Ｗ＝２の場合を示している。カウンタ一致検出回路３１は、クロック数変換回路３１ａと、カウンタ３１ｂと、一致検出回路３１ｃとを含む。カウンタ一致検出回路３２は、クロック数変換回路３２ａと、カウンタ３２ｂと、一致検出回路３２ｃとを含む。以下、各構成の機能について説明する。
【００３７】
クロック数変換回路３１ａは、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１と、バッファ２１からのクロック信号ＣＬＫとを受ける。クロック数変換回路３１ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１１が示す距離と一致するクロック数を検出したタイミングで、カウンタ３１ｂにＨレベルの一致検出信号をカウンタ３１ｂへ出力する処理を行う。クロック数変換回路３１ａは、後述の一致検出回路３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）が出力されるまで、この処理を繰り返し行い、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力されると動作を停止する。
【００３８】
カウンタ３１ｂは、クロック数変換回路３１ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウンタ値を一致検出回路３１ｃへ出力する。
【００３９】
一致検出回路３１ｃは、カウンタ３１ｂからカウンタ値を受け、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１を受ける。一致検出回路３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とを比較し、距離信号Ｄ１１が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路３１ａとバッファ２２へ出力する。一致検出回路３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とが一致しないときは、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路３１ａとバッファ２２へ出力する。
【００４０】
クロック数変換回路３２ａは、バッファ２２からクロック信号ＣＬＫを受けると駆動する。クロック数変換回路３２ａは、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。クロック数変換回路３１ａと同様、クロック数変換回路３２ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１２が示す距離と一致するクロック数を検出したタイミングで、カウンタ３２ｂにＨレベルの一致検出信号を出力する処理を行う。クロック数変換回路３２ａは、後述の一致検出回路３２ｃからＨレベルの一致信号（ＤＥＴＥＣＴ２）が出力されるまで、この処理を繰り返し行う。クロック数変換回路３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）が出力されると動作を停止する。
【００４１】
カウンタ３２ｂは、クロック数変換回路３２ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウンタ値を一致検出回路３２ｃへ出力する。
【００４２】
一致検出回路３２ｃは、カウンタ３２ｂからカウンタ値を受け、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。一致検出回路３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とを比較し、距離信号Ｄ１２が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路３２ａに出力するとともに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をタイミング信号Ｃ１としてＷｉｎｎｅｒ検出器２０へ出力する。また、一致検出回路３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とが一致するときに、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路３２ａに出力する。
【００４３】
ここで、例えば、距離演算回路ＤＰ１１から距離「２」を示すＭビットの距離信号Ｄ１１が出力され、距離演算回路ＤＰ１２から距離「３」を示すＭビットの距離信号Ｄ１２が出力された場合の動作例について説明する。
【００４４】
クロック数変換回路３１ａは、距離「２」を示すＭビットの距離信号Ｄ１１を受け、バッファ２１からのクロック信号ＣＬＫのクロックに同期して、距離「２」に一致するクロック数をカウントする。クロック数変換回路３１ａは、カウントしたクロック数と距離とが一致すると、Ｈレベルの一致検出信号を出力する。カウンタ３１ｂは、一致検出信号が立ち上がると、カウンタ値をカウントアップし、「１」を示すカウンタ値を一致検出回路３１ｃに出力する。このとき、距離信号Ｄ１１が示す距離「２」とカウンタ値「１」とが一致しないため、一致検出回路３１ｃからＬレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。
【００４５】
クロック数変換回路３１ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路３１ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「２」と一致すると、カウンタ３１ｂにＨレベルの一致検出信号を出力する。カウンタ３１ｂは、一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路３１ｃに「２」を示すカウンタ値を出力する。一致検出回路３１ｃは、距離信号Ｄ１１が示す距離「２」とカウンタ値「２」とが一致するため、一致信号（ＤＥＴＥＣＴ１）をバッファ２２とクロック数変換回路３１ａに出力する。つまり、検索開始からのクロック数が「４」となるタイミングで、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。そして、クロック数変換回路３１ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）に応じて動作を停止する。
【００４６】
バッファ２２は、一致検出回路３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けて、クロック数変換回路３２ａにクロック信号ＣＬＫを出力する。クロック数変換回路３２ａは、バッファ２２からのクロック信号ＣＬＫのクロックに同期して、クロック信号ＣＬＫのクロック数をカウントする。クロック数変換回路３２ａは、距離「３」を示すＭビットの距離信号Ｄ１２を受け、カウントしたクロック数が距離「３」と一致するタイミングで、Ｈレベルの一致検出信号をカウンタ３２ｂに出力する。カウンタ３２ｂは、クロック数変換回路３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路３２ｃに「１」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「１」とが一致しないため、一致検出回路３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００４７】
クロック数変換回路３２ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路３２ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ３２ｂにＨレベルの一致検出信号を出力する。カウンタ３２ｂは、クロック数変換回路３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路３２ｃに「２」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「２」とが一致しないため、一致検出回路３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００４８】
クロック数変換回路３２ａは、一致検出信号がＬレベルになると、再びカウントしたクロック数をリセットしてクロック信号ＣＬＫをカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ３２ｂにＨレベルの一致検出信号を出力する。そして、クロック数変換回路３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）に応じて動作を停止する。カウンタ３２ｂは、クロック数変換回路３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路３２ｃに「３」を示すカウンタ値を出力する。一致検出回路３２ｃは、距離「３」とカウンタ値「３」とが一致するため、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路３２ａに出力するとともに、タイミング信号Ｃ１としてＷｉｎｎｅｒ検出器２０に出力する。つまり、クロック数変換回路３２ａにおいてカウントされたクロック数は「９（＝３＋３＋３）」であり、検索開始からクロック数「１３（＝４＋９）」のタイミングでタイミング信号Ｃ１が出力される。
【００４９】
カウンタ一致検出回路３１，３２全体でカウントされるクロック数ＣＮ＿ｔｏｔａｌ１「１３」は、カウンタ一致検出回路３１においてカウントするクロック数「４（＝２＋２）」と、カウンタ一致検出回路３２においてカウントするクロック数「９（＝３＋３＋３）」とを加算したものである。つまり、カウンタ一致検出回路３１，３２によって、距離「２」の二乗値と距離「３」の二乗値との和に一致するクロック数をカウントすることに相当する。
【００５０】
距離／クロック数変換回路ＤＣ１は、一般的に、Ｗ個の距離信号Ｄ１１〜Ｄ１Ｗを受ける。そして、Ｗ個の距離信号Ｄ１１〜Ｄ１Ｗの各々は、Ｍビットのビット長を有する。従って、距離／クロック数変換回路ＤＣ１は、Ｍ×Ｗビットのビット長を有する距離信号Ｄ１１Ｄ１２・・・Ｄ１Ｗを受ける。カウンタ一致検出回路３１において、距離信号Ｄ１１が示す距離に一致する回数分だけ、その距離に一致するクロック数を繰り返しカウントする。また、カウンタ一致検出回路３２〜３Ｗは、それぞれ、カウンタ一致検出回路３１〜３Ｗ−１から一致信号を受けた後に、距離信号Ｄ１２〜Ｄ１Ｗにそれぞれ一致するクロック数を、その距離に一致する回数だけ繰り返しカウントする。その結果、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌ１は、カウンタ一致検出回路３１〜３Ｗの各々においてカウントされたクロック数の和に等しい。カウンタ一致検出回路３１〜３Ｗの各々においてカウントされたクロック数は、それぞれ、距離信号Ｄ１１〜Ｄ１Ｗが示す各距離の二乗値に相当するため、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌＲは、各距離信号Ｄ１１〜Ｄ１Ｗの二乗値の和を表している。
【００５１】
ここで、ユークリッド距離ｎＥは、次式によって表わされる。
【００５２】
【数２】
2014154196.tif 000004
【００５３】
式（２）の右辺の｜Ｉｎｊ−Ｒｅｒｊ｜２は、式（１）の右辺の｜Ｉｎｊ−Ｒｅｒｊ｜において、検索データと参照データとの距離の二乗値に一致する。従って、ユークリッド距離ｎＥｒの演算は、上述したように、式（１）によって演算したＷ個の各距離について、距離に一致するクロック数をカウントする処理を距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図２Ｂの例において、カウンタ一致検出回路３２が、カウンタ一致検出回路３１，３２全体でカウントしたクロック数のタイミングを示すタイミング信号Ｃ１を出力することは、ユークリッド距離ｎＥｒによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示すＷｉｎｎｅｒ信号を出力することに相当する。なお、距離／クロック数変換回路ＤＣ２〜ＤＣＲの各々も、距離／クロック数変換回路ＤＣ１の動作と同じ動作によって、それぞれ、タイミング信号Ｃ２〜ＣＲを出力する。
【００５４】
次に、Ｗｉｎｎｅｒ検出器２０の動作について説明する。図３は、図１に示すＷｉｎｎｅｒ検出器２０の動作を説明するための図である。距離／クロック数変換回路ＤＣ１〜ＤＣＲは、図３に示すように、例えばタイミング信号Ｃ１〜ＣＲをそれぞれクロック信号ＣＬＫに同期してＷｉｎｎｅｒ検出器２０へ出力する。
【００５５】
Ｗｉｎｎｅｒ検出器２０は、タイミング信号Ｃ１〜ＣＲを受け、その受けたタイミング信号Ｃ１〜ＣＲの立ち上がりタイミングｔ１〜ｔＲを検出する。そして、Ｗｉｎｎｅｒ検出器２０は、立ち上がりタイミングｔ１〜ｔＲが早い順にｋ個のタイミング信号Ｃ’１〜Ｃ’ｋを検出する。Ｗｉｎｎｅｒ検出器２０は、タイミング信号Ｃ’１〜Ｃ’ｋをマッチ信号Ｍ１〜Ｍｋとして出力する。
【００５６】
例えば、２個（ｋ＝２）のマッチ信号Ｍ１，Ｍ２を検出する場合、Ｗｉｎｎｅｒ検出器２０は、タイミング信号Ｃ１〜ＣＲのうち、立ち上がりタイミングが早い順に２個のタイミング信号Ｃ１，Ｃ３を検出し、その検出したタイミング信号Ｃ１，Ｃ３をマッチ信号Ｍ１，Ｍ２として出力する。ｋ＝２以外のｋ個のタイミング信号Ｃ’１〜Ｃ’ｋを検出する場合も、Ｗｉｎｎｅｒ検出器２０は、同様にして、ｋ個のタイミング信号Ｃ’１〜Ｃ’ｋを検出し、その検出したｋ個のタイミング信号Ｃ’１〜Ｃ’ｋをマッチ信号Ｍ１〜Ｍｋとして出力する。
【００５７】
ｋ＝１である場合、Ｗｉｎｎｅｒ検出器２０は、検索データに最も類似する参照データに対応するタイミング信号（タイミング信号Ｃ１〜ＣＲのいずれか）をマッチ信号Ｍ１として出力する。また、ｋ≠１である場合、Ｗｉｎｎｅｒ検出器２０は、検索データに類似するｋ個の参照データに対応するｋ個のタイミング信号Ｃ’１〜Ｃ’ｋをマッチ信号Ｍ１〜Ｍｋとして出力する。この場合、ｋ個のタイミング信号Ｃ’１〜Ｃ’ｋにおいて、ｋ個の立ち上がりタイミングは、相互に、少なくともクロック信号ＣＬＫの１周期分だけ異なるので、立ち上がりタイミングの早い順にｋ個のタイミング信号Ｃ’１〜Ｃ’ｋが正確に検出される。つまり、連想メモリ１００は、検索データに類似するｋ個の参照データを正確に検出することができる。
【００５８】
距離／クロック数変換回路ＤＣ１〜ＤＣＲの動作は、クロック信号ＣＬＫに同期して実行される。そのため、クロック信号ＣＬＫの周波数を高くすることで、連想メモリ１００の動作を高速化してもよい。本実施形態では、クロック数変換回路３１ａ，３２ａは、一致信号（ＤＥＴＥＣＴ１，ＤＥＴＥＣＴ２）がそれぞれ出力されると動作を停止する。そのため、距離／クロック数変換回路ＤＣｉにおいて、全ての距離が一致するまでクロック数変換回路ＤＣｉ１〜ＤＣｉＲを動作させる場合と比べて消費電力を小さくすることができる。
【００５９】
＜第２実施形態＞
本実施形態では、第１実施形態で説明した距離／クロック数変換回路とは異なる構成によって、ユークリッド距離を用いた検索を行う例について説明する。
【００６０】
図４は、本実施形態における距離／クロック数変換回路ＤＣ１の構成例を示す概略構成図である。図４において、第１実施形態と同様の構成については、第１実施形態と同様の符号を付している。図４の例では、Ｗ＝２の場合の距離／クロック数変換回路ＤＣ１の構成例を示している。なお、距離／クロック数変換回路ＤＣ２〜ＤＣＲについても同様の構成を有する。
【００６１】
図４に示すように、距離／クロック数変換回路ＤＣ１は、バッファ２３、距離／クロック数変換ユニット３１０，３２０、及び、カウンタ一致検出ユニット３００を含む。
【００６２】
バッファ２３は、連想メモリ１００の制御回路（図示せず）から検索開始信号ＳＢを受け、連想メモリ１００に内蔵されたクロック発生回路（図示せず）からクロック信号ＣＬＫを受ける。そして、バッファ２３は、検索開始信号ＳＢがＬレベルからＨレベルに切り替わると、その受けたクロック信号ＣＬＫを距離／クロック数変換ユニット３１０，３２０へ出力する。
【００６３】
距離／クロック数変換ユニット３１０，３２０は、距離演算回路ＤＰ１１，ＤＰ１２にそれぞれ対応して設けられる。距離／クロック数変換ユニット３１０は、クロック数変換回路３１ａ、デマルチプレクサ３１ｄ、ＯＲ回路３１ｅ、及び一致検出回路３１ｃ’を含む。距離／クロック数変換ユニット３２０は、クロック数変換回路３２ａ、デマルチプレクサ３２ｄ、ＯＲ回路３２ｅ、及び一致検出回路３２ｃ’を含む。カウンタ一致検出ユニット３００は、デマルチプレクサ３００ａ、カウンタ３００ｂ、及び、ＡＮＤ回路３００ｃを含む。
【００６４】
デマルチプレクサ３１ｄは、連想メモリ１００の制御回路（図示せず）からイネーブル信号（ＥＮ）を受け、後述の一致検出回路３１ｃ’から一致信号（ＤＥＴＥＣＴ１）を受ける。デマルチプレクサ３１ｄは、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）を受けると、クロック数変換回路３１ａにＨレベル（＝１）のＥＮ信号を出力し、ＯＲ回路３１ｅにＬレベル（＝０）のＥＮ信号を出力する。また、デマルチプレクサ３１ｄは、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）を受けると、クロック数変換回路３１ａにＬレベルのＥＮ信号を出力し、ＯＲ回路３１ｅにＨレベルのＥＮ信号を出力する。
【００６５】
クロック数変換回路３１ａは、距離演算回路ＤＰ１１からＭビットの距離信号Ｄ１１を受け、バッファ２３からクロック信号ＣＬＫを受ける。クロック数変換回路３１ａは、デマルチプレクサ３１ｄからＨレベルのＥＮ信号を受けると、クロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数と距離信号Ｄ１１が示す距離との一致を検出する。クロック数変換回路３１ａは、カウントしたクロック数と距離信号Ｄ１１が示す距離とが一致するタイミングで、ＯＲ回路３１ｅに「１」を示すＨレベルの一致検出信号を出力する。また、クロック数変換回路３１ａは、後述のデマルチプレクサ３００ａから出力される信号を受け、その信号を受けたタイミングでカウントしたクロック数をリセットする。クロック数変換回路３１ａは、デマルチプレクサ３１ｄからＬレベルのＥＮ信号を受けると、「０」を示すＬレベルの一致検出信号をＯＲ回路３１ｅに出力する。
【００６６】
ＯＲ回路３１ｅは、クロック数変換回路３１ａからの一致検出信号（１又は０）と、デマルチプレクサ３１ｄからのＥＮ信号（１又は０）とを受け、一致検出信号とＥＮ信号の論理和を演算し、演算結果からなる駆動信号を距離／クロック数変換回路３２０におけるデマルチプレクサ３２ｄに出力する。
【００６７】
デマルチプレクサ３２ｄは、ＯＲ回路３１ｅからの駆動信号と、後述する一致検出回路３２ｃ’からの一致信号（ＤＥＴＥＣＴ２）とを受ける。デマルチプレクサ３２ｄは、一致検出信号（ＤＥＴＥＣＴ２）がＬレベルの場合、ＯＲ回路３１ｅからの駆動信号をクロック数変換回路３２ａに出力し、ＯＲ回路３１ｅからの駆動信号を反転させた反転信号をＯＲ回路３２ｅに出力する。また、一致信号（ＤＥＴＥＣＴ２）がＨレベルの場合には、ＯＲ回路３１ｅからの駆動信号を反転させた反転信号をクロック数変換回路３２ａに出力し、ＯＲ回路３１ｅからの駆動信号をＯＲ回路３２ｅに出力する。
【００６８】
クロック数変換回路３２ａは、距離演算回路ＤＰ１２からＭビットの距離信号Ｄ１２を受け、バッファ２３からクロック信号ＣＬＫを受ける。クロック数変換回路３２ａは、デマルチプレクサ３２ｄから「１」を示す駆動信号を受けると、クロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数と距離信号Ｄ１２が示す距離との一致を検出する。クロック数変換回路３２ａは、カウントしたクロック数と距離信号Ｄ１２が示す距離とが一致するタイミングで、ＯＲ回路３２ｅに「１」を示す一致検出信号を出力する。また、クロック数変換回路３２ａは、後述のデマルチプレクサ３００ｄから出力される信号を受け、その信号を受けたタイミングでカウントしたクロック数をリセットする。クロック数変換回路３２ａは、デマルチプレクサ３２ｄから「０」を示す駆動信号を受けると、「０」を示す駆動信号をＯＲ回路３２ｅに出力する。
【００６９】
ＯＲ回路３２ｅは、クロック数変換回路３２ａからの一致検出信号（１又は０）と、デマルチプレクサ３２ｄからの駆動信号（１又は０）とを受け、受けた２つの信号の論理和を演算し、演算結果を示す信号をカウンタ一致検出ユニット３００におけるデマルチプレクサ３００ａに出力する。
【００７０】
デマルチプレクサ３００ａは、ＯＲ回路３２ｅからの信号を受け、後述するＡＮＤ回路３００ｃから検索終了か否かを示すＳｅａｒｃｈ−Ｅｎｄ信号を受ける。デマルチプレクサ３００ａは、Ｓｅａｒｃｈ−Ｅｎｄ信号がＬレベルの場合には、ＯＲ回路３２ｅからの信号をカウンタ３００ｂとクロック数変換回路３１ａ，３２ａに出力し、Ｓｅａｒｃｈ−Ｅｎｄ信号がＬレベルからＨレベルに切り替わると、ＯＲ回路３２ｅからの信号をタイミング信号Ｃ１としてＷｉｎｎｅｒ検出器２０へ出力する。
【００７１】
カウンタ３００ｂは、デマルチプレクサ３００ａから信号を受けるごとにカウンタ値を１つだけカウントアップさせ、カウントアップしたＭビットのカウンタ値を一致検出回路３１ｃ’，３２ｃ’へ出力する。なお、カウンタ３００ｂの初期値として、カウンタ値「０」が設定されている。
【００７２】
一致検出回路３１ｃ’は、カウンタ３００ｂからＭビットのカウンタ値を受け、距離演算回路ＤＰ１１から距離信号Ｄ１１を受ける。一致検出回路３１ｃ’は、カウンタ値と距離信号Ｄ１１が示す距離との一致を検出する。一致検出回路３１ｃ’は、カウンタ値≧距離を満たす場合には、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）をデマルチプレクサ３１ｄとＡＮＤ回路３００ｃに出力する。また、カウンタ値と距離とが一致しない場合、つまり、カウンタ値＜距離を満たす場合には、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）をデマルチプレクサ３１ｄとＡＮＤ回路３００ｃに出力する。
【００７３】
一致検出回路３２ｃ’は、カウンタ３００ｂからＭビットのカウンタ値を受け、距離演算回路ＤＰ１２から距離信号Ｄ１２を受ける。一致検出回路３２ｃ’は、カウンタ値と距離信号Ｄ１２が示す距離との一致を検出する。一致検出回路３２ｃ’は、カウンタ値と距離とが、カウンタ値≧距離を満たす場合には、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をデマルチプレクサ３２ｄとＡＮＤ回路３００ｃに出力する。また、カウンタ値と距離とが一致しない場合、つまり、カウンタ値＜距離を満たす場合には、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）をデマルチプレクサ３２ｄとＡＮＤ回路３００ｃに出力する。
【００７４】
ＡＮＤ回路３００ｃは、一致検出回路３１ｃ’からの一致信号（ＤＥＴＥＣＴ１）と、一致検出回路３２ｃ’からの一致信号（ＤＥＴＥＣＴ２）との論理積を演算し、その演算結果を示すＳｅａｒｃｈ−Ｅｎｄ信号をデマルチプレクサ３００ａに出力する。つまり、Ｈレベルの一致信号（ＤＥＴＥＣＴ１，ＤＥＴＥＣＴ２）の場合には、「１」を示すＳｅａｒｃｈ−Ｅｎｄ信号がデマルチプレクサ３００ａに出力され、検索を終了する。また、少なくともいずれか一方の一致信号がＬレベルである場合には、「０」を示すＳｅａｒｃｈ−Ｅｎｄ信号がデマルチプレクサ３００ａに出力され、検索を継続する。
【００７５】
ここで、例えば、距離演算回路ＤＰ１１から距離「２」を示すＭビットの距離信号Ｄ１１が出力され、距離演算回路ＤＰ１２から距離「３」を示すＭビットの距離信号Ｄ１２が出力された場合の動作例について説明する。
【００７６】
ＥＮ信号が入力されると、デマルチプレクサ３１ｄは、一致信号（ＤＥＴＥＣＴ１）が立ち上がっていないため、クロック数変換回路３１ａにＨレベルのＥＮ信号を出力し、ＯＲ回路３１ｅにＬレベルのＥＮ信号を出力する。クロック数変換回路３１ａは、デマルチプレクサ３１ｄからＨレベルのＥＮ信号を受けると、バッファ２３からのクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数と距離演算回路ＤＰ１１からの距離信号Ｄ１１が示す距離「２」と一致するタイミングで一致検出信号（＝１）を出力する。
【００７７】
ＯＲ回路３１ｅは、クロック数変換回路３１ａからの一致検出信号（＝１）とデマルチプレクサ３１ｄからのＥＮ信号（＝０）との論理和の演算結果からなる駆動信号（＝１）をデマルチプレクサ３２ｄに出力する。デマルチプレクサ３２ｄは、ＯＲ回路３１ｅから駆動信号（＝１）を受けると、一致信号（ＤＥＴＥＣＴ２）が立ち上がっていないため、その駆動信号（＝１）をクロック数変換回路３２ａに出力し、その駆動信号の反転信号（＝０）をＯＲ回路３２ｅに出力する。クロック数変換回路３２ａは、デマルチプレクサ３２ｄから駆動信号（＝１）を受けると、バッファ２３からのクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数と、距離演算回路ＤＰ１２からの距離信号Ｄ１２が示す距離「３」とが一致するタイミングで、一致検出信号（＝１）を出力する。
【００７８】
ＯＲ回路３２ｅは、クロック数変換回路３２ａからの一致検出信号（＝１）と、デマルチプレクサ３２ｄからの反転信号（＝０）との論理和の演算結果を表す信号（＝１）をデマルチプレクサ３００ａに出力する。デマルチプレクサ３００ａは、カウンタ３００ｂとクロック数変換回路３１ａ，３２ａとにＯＲ回路３２ｅからの信号（＝１）を出力する。クロック数変換回路３１ａとクロック数変換回路３２ａは、デマルチプレクサ３００ａからの信号（＝１）を受けると、カウントしたクロック数をそれぞれリセットする。カウンタ３００ｂは、デマルチプレクサ３００ａからの信号（＝１）を受けると、カウンタ値をカウントアップし、カウンタ値「１」を一致検出回路３１ｃ’，３２ｃ’へ出力する。なお、検索開始からこのカウンタ値「１」が得られるときのクロック信号ＣＬＫの総クロック数は５（＝２＋３）である。
【００７９】
一致検出回路３１ｃ’は、距離演算回路ＤＰ１１からの距離信号Ｄ１１が示す距離「２」と、カウンタ３００ｂからのカウンタ値「１」とが一致しないため（距離＞カウンタ値）、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）を出力する。また、一致検出回路３２ｃ’は、距離演算回路ＤＰ１２からの距離信号Ｄ１２が示す距離「３」と、カウンタ３００ｂからのカウンタ値「１」とが一致しないため（距離＞カウンタ値）、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）を出力する。
【００８０】
デマルチプレクサ３１ｄは、一致信号（ＤＥＴＥＣＴ１）が立ち上がっていないため、クロック数変換回路３１ａにＨレベルのＥＮ信号を入力し、ＯＲ回路３１ｅにＬレベルのＥＮ信号を出力する。クロック数変換回路３１ａは、クロック信号ＣＬＫのクロック数を再びカウントし、カウントしたクロック信号ＣＬＫのクロック数と距離「２」とが一致するタイミングで、ＯＲ回路３１ｅに「１」を示す一致検出信号を出力する。
【００８１】
クロック数変換回路３１ａからの一致検出信号（＝１）と、ＯＲ回路３１ｅからのＥＮ信号（＝０）との論理和の演算結果を示す駆動信号（＝１）がＯＲ回路３１ｅから出力される。デマルチプレクサ３２ｄは、ＯＲ回路３１ｅから駆動信号（＝１）を受けると、一致信号（ＤＥＴＥＣＴ２）が立ち上がっていないため、クロック数変換回路３２ａに駆動信号（＝１）を出力し、その駆動信号の反転信号（＝０）をＯＲ回路３２ｅに出力する。クロック数変換回路３２ａは、クロック信号ＣＬＫのクロック数を再びカウントし、カウントしたクロック信号ＣＬＫのクロック数と距離「３」とが一致するタイミングで、ＯＲ回路３１ｅに「１」を示す一致検出信号を出力する。
【００８２】
クロック数変換回路３２ａからの一致検出信号（＝１）と、デマルチプレクサ３２ｄからの反転信号（＝０）との論理和の演算結果を示す信号（＝１）がＯＲ回路３２ｅから出力されると、デマルチプレクサ３００ａは、ＯＲ回路３２ｅからの信号（＝１）をカウンタ３００ｂとクロック数変換回路３１ａ，３２ａに出力する。これにより、クロック数変換回路３１ａとクロック数変換回路３２ａは、カウントしたクロック数をそれぞれリセットする。カウンタ３００ｂは、デマルチプレクサ３００ａからの信号（＝１）を受けてカウンタ値をカウントアップさせ、カウンタ値「２」を一致検出回路３１ｃ’，３２ｃ’へ出力する。なお、検索開始からこのカウンタ値「２」が得られるときの総クロック数は１０（＝２＋３＋２＋３）である。
【００８３】
一致検出回路３１ｃ’において、距離信号Ｄ１１が示す距離「２」と、カウンタ３００ｂからのカウンタ値「２」とが一致するため（距離≦カウンタ値）、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。一方、一致検出回路３２ｃ’において、距離信号Ｄ１２が示す距離「３」と、カウンタ３００ｂからのカウンタ値「２」とが一致しないため（距離＞カウンタ値）、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００８４】
デマルチプレクサ３１ｄは、一致信号（ＤＥＴＥＣＴ１）がＬレベルからＨレベルに切り替わると、ＯＲ回路３１ｅにＨレベルのＥＮ信号を出力し、クロック数変換回路３１ａにＬレベルのＥＮ信号を出力する。クロック数変換回路３１ａは、ＬレベルのＥＮ信号を受けると、「０」を示す一致検出信号をＯＲ回路３１ｅに出力する。
【００８５】
クロック数変換回路３１ａからの一致検出信号（＝０）と、デマルチプレクサ３１ｄからのＥＮ信号（＝１）との論理和の演算結果を示す駆動信号（＝１）がＯＲ回路３１ｅから出力されると、デマルチプレクサ３２ｄは、ＯＲ回路３１ｅからの駆動信号（＝１）をクロック数変換回路３２ａに出力し、その駆動信号の反転信号（＝０）をＯＲ回路３２ｅに出力する。
【００８６】
クロック数変換回路３２ａは、ＯＲ回路３２ｅから駆動信号（＝１）を受けると、クロック信号ＣＬＫをカウントし、カウントしたクロック数と距離「３」とが一致するタイミングで、「１」を示す一致検出信号をＯＲ回路３２ｅに出力する。ＯＲ回路３２ｅは、クロック数変換回路３２ａからの一致検出信号（＝１）とデマルチプレクサ３２ｄからの駆動信号（＝０）との論理和の演算結果を示す信号（＝１）をデマルチプレクサ３００ａに出力する。
【００８７】
デマルチプレクサ３００ａは、ＯＲ回路３２ｅから出力される信号（＝１）をカウンタ３００ｂとクロック数変換回路３１ａ，３２ａに出力する。これにより、クロック数変換回路３１ａとクロック数変換回路３２ａは、カウントしたクロック数をそれぞれリセットする。また、カウンタ３００ｂは、デマルチプレクサ３００ａからの信号（＝１）を受けてカウンタ値をカウントアップし、カウンタ値「３」を一致検出回路３１ｃ’，３２ｃ’へ出力する。なお、検索開始からこのカウンタ値「３」が得られるときの総クロック数は１３（＝２＋３＋２＋３＋３）である。
【００８８】
一致検出回路３１ｃ’において、距離演算回路ＤＰ１１からの距離信号Ｄ１１が示す距離「２」と、カウンタ３００ｂからのカウンタ値「３」は、距離≦カウンタ値を満たすため、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。また、一致検出回路３２ｃ’において、距離演算回路ＤＰ１１からの距離信号Ｄ１１が示す距離「３」と、カウンタ３００ｂからのカウンタ値「３」とが一致するため（距離≦カウンタ値）、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００８９】
デマルチプレクサ３１ｄは、一致信号（ＤＥＴＥＣＴ１）がＨレベルであるので、ＯＲ回路３１ｅにＨレベルのＥＮ信号を出力し、クロック数変換回路３１ａにＬレベルのＥＮ信号を出力する。クロック数変換回路３１ａは、ＬレベルのＥＮ信号を受けると、「０」を示す一致検出信号をＯＲ回路３１ｅに出力する。クロック数変換回路３１ａからの一致検出信号（＝０）と、ＯＲ回路３１ｅからのＥＮ信号（＝１）との論理和の演算結果を示す駆動信号（＝１）信号がＯＲ回路３１ｅから出力される。
【００９０】
デマルチプレクサ３２ｄは、一致信号（ＤＥＴＥＣＴ２）がＬレベルからＨレベルに切り替わると、ＯＲ回路３１ｅからの駆動信号（＝１）の反転信号（＝０）をクロック数変換回路３２ａに出力し、その駆動信号（＝１）をＯＲ回路３２ｅに出力する。クロック数変換回路３２ａは、デマルチプレクサ３２ｄから駆動信号（＝０）を受けると、「０」を示す一致検出信号をＯＲ回路３２ｅに出力する。ＯＲ回路３２ｅは、クロック数変換回路３２ａからの一致検出信号（＝０）と、デマルチプレクサ３２ｄからの駆動信号（＝１）との論理和の演算結果を示す信号（＝１）をデマルチプレクサ３００ａに出力する。
【００９１】
ＡＮＤ回路３００ｃは、一致検出回路３１ｃ’，３２ｃ’からのＨレベルの一致信号（ＤＥＴＥＣＴ１）と一致信号（ＤＥＴＥＣＴ２）との論理積を演算し、Ｓｅａｒｃｈ−Ｅｎｄ信号（＝１）をデマルチプレクサ３００ａに出力する。デマルチプレクサ３００ａは、Ｓｅａｒｃｈ−Ｅｎｄ信号（＝１）を受けると検索を終了し、ＯＲ回路３２ｅからの信号を、タイミング信号Ｃ１としてＷｉｎｎｅｒ検出器２０へを出力する。つまり、検索開始からクロック数が「１３」となるタイミングでタイミング信号Ｃ１が出力される。
【００９２】
クロック数「１３」は、距離信号Ｄ１１と距離信号Ｄ１２の各距離（Ｄ１１＝２，Ｄ１２＝３）の二乗値の和（＝４＋９）と等しい。参照データと検索データとのユークリッド距離ｎＥｒの演算は、上述したように、式（１）によって演算したＷ個の各距離について、距離に一致するクロック数をカウントする処理を、距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図４の例において、カウンタ一致検出ユニット３００が、距離／クロック数変換ユニット３１０，３２０全体でクロック数「１３」をカウントしたタイミングを示すタイミング信号Ｃ１を出力することは、ユークリッド距離ｎＥｒによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示すＷｉｎｎｅｒ信号を出力することに相当する。なお、距離／クロック数変換回路ＤＣ２〜ＤＣＲの各々も、距離／クロック数変換回路ＤＣ１の動作と同じ動作によって、それぞれ、タイミング信号Ｃ２〜ＣＲを出力する。
【００９３】
第１実施形態では、距離演算回路ＤＰ１１〜ＤＰＲＷの各々に対してカウンタを設ける例であったが、本実施形態では、距離／クロック数変換回路ＤＣｉごとに１つのカウンタを設ける構成であるため、第１実施形態と比べて回路面積を小さくすることができる。
【００９４】
なお、上述した第２実施形態において、連想メモリ１００の制御回路（図示せず）から、各距離／クロック数変換回路ＤＣｉのデマルチプレクサ３００ａに、マンハッタン距離又はユークリッド距離を示す制御信号を入力し、マンハッタン距離を示す制御信号が入力された場合には、各距離／クロック数変換回路ＤＣｉにおいて１回目の処理が終了するタイミングでタイミング信号Ｃ１を出力するようにしてもよい。つまり、図４の例において、クロック数変換回路３１ａがクロック数「２」をカウントした後、クロック数変換回路３２ａにおいてクロック数「３」をカウントしたタイミングで、デマルチプレクサ３００ａからタイミング信号Ｃ１を出力する。その結果、タイミング信号Ｃ１は、検索開始からクロック数「５」（＝２＋３）のタイミングで出力される。これは、１つの行における参照データと検索データとの各マンハッタン距離の和と一致する。従って、このような構成にすることで、マンハッタン距離とユークリッド距離とを選択的に用いて検索を行うことが可能となる。
【００９５】
＜第３実施形態＞
上述した第１実施形態及び第２実施形態では、各距離／クロック数変換回路において、距離ごとに、距離をクロック数に変換する処理を距離と一致する回数だけ繰り返し行うことによって、ユークリッド距離を用いた検索を行う例について説明した。
【００９６】
例えば、第１実施形態における各距離／クロック数変換回路において、距離をクロック数に変換する処理を各カウンタ一致検出回路において１回だけ行ったタイミングでタイミング信号を出力すると、マンハッタン距離（式（１））の和に一致するクロック数のタイミングでタイミング信号が出力される。また、上述したように、第２実施形態における距離／クロック数変換回路ＤＣ１〜ＤＣＲの距離／クロック数変換ユニット３１０，３２０において、距離をクロック数に変換する処理を１回だけ行ってタイミング信号を出力する場合もマンハッタン距離の和に一致するクロック数のタイミングでタイミング信号を出力することができる。
【００９７】
第１実施形態や第２実施形態において、ユークリッド距離とマンハッタン距離のいずれを用いて検索する場合であっても、各距離／クロック数変換回路において、全ての距離についてクロック数が一致しなければタイミング信号は出力されない。つまり、第１実施形態や第２実施形態の場合、最も早くタイミング信号が出力されるタイミングｔ１（以下、類似パターンｐ１）と、２番目にタイミング信号が出力されるタイミングｔ２（以下、類似パターンｐ２）は、図５Ａに示す関係となる。類似パターンｐ１は、距離がｎＭ１の場合であり、類似パターンｐ２は、距離がｎＭ２（＞ｎＭ１）の場合を示している。また、τCLKは、クロックサイクルを表している。従って、類似パターンｐ１のタイミング信号は、ｔ１＝ｎＭ１・τCLKのタイミングで出力され、類似パターンｐ２のタイミング信号は、ｔ２＝ｎＭ２・τCLKのタイミングで出力される。
【００９８】
第１実施形態や第２実施形態のように、距離ごとに、カウントしたクロック数との一致を厳密に検出すると、検索データやビット長が増加するほど多大な検索時間を要することになる。本実施形態では、図５Ｂに示すように、類似パターンｐ１，ｐ２から同じ値（ｎｘ・τCLK）だけ検索時間を削減することにより、第１実施形態や第２実施形態と比べて検索時間を短縮する検索アルゴリズムについて説明する。なお、以下の説明においては、マンハッタン距離を用いる場合を例に説明する。
【００９９】
図６は、本実施形態に係る連想メモリの構成例を示す概略ブロック図である。図６において、第１実施形態と同様の構成には、第１実施形態と同じ符号を付している。以下、第１実施形態と異なる構成について説明する。図６に示すように、連想メモリ１１０は、距離／クロック数変換回路ＤＣ１〜ＤＣＲに替えて距離／クロック数変換回路ＤＥ１〜ＤＥＲを備え、ＡＮＤ回路６と有効ビット設定部４０とを更に備える。
【０１００】
距離演算回路ＤＰ１１〜ＤＰ１Ｗの各々は、参照データ１と検索データとの距離を上述した式（１）を用いて演算する。また、距離演算回路ＤＰ２１〜ＤＰ２Ｗの各々は、参照データ２と検索データとの距離を上述した式（１）を用いて演算する。以下同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷの各々は、参照データＲと検索データとの距離を上述した式（１）を用いて演算する。
【０１０１】
距離／クロック数変換回路ＤＥ１は、距離演算回路ＤＰ１１〜ＤＰ１ＷからＷ個のＮビット長を有する距離信号Ｄ１ｊを受け、後述する方法で距離信号Ｄ１ｊが示す距離に一致するクロック数を検出したタイミングで、一致検出信号ｍ１Ｗ_ｎを有効ビット設定部４０へ出力する。距離／クロック数変換回路ＤＥ２は、距離演算回路ＤＰ２１〜ＤＰ２ＷからＷ個のＮビット長を有する距離信号Ｄ２ｊを受け、後述する方法で距離信号Ｄ２ｊが示す距離に一致するクロック数を検出したタイミングで、一致検出信号ｍ２Ｗ_ｎを有効ビット設定部４０へ出力する。以下、同様にして、距離／クロック数変換回路ＤＥＲは、距離演算回路ＤＰＲ１〜ＤＰＲＷからＷ個のＮビット長を有する距離信号ＤＲｊを受け、後述する方法で距離信号ＤＲｊが示す距離に一致するクロック数を検出したタイミングで、一致検出信号ｍＲＷ_ｎを有効ビット設定部４０へ出力する。
【０１０２】
図７は、距離／クロック数変換回路ＤＥ１の構成例を示す概略構成図である。図７に示すように、距離／クロック数変換回路ＤＥ１は、距離演算回路ＤＰ１１〜ＤＰ１Ｗにそれぞれ対応するように設けられたカウンタ一致検出回路ＤＥ１１〜ＤＥ１Ｗと、バッファ２１〜２Ｗとを有する。なお、距離／クロック数変換回路ＤＥ２…ＤＥＲについても距離／クロック数変換回路ＤＥ１と同様の構成を有する。
【０１０３】
カウンタ一致検出回路ＤＥ１１〜ＤＥ１Ｗは、それぞれ距離演算回路ＤＰ１１〜ＤＰ１ＷからＮビット長を有する距離信号Ｄ１１〜Ｄ１Ｗを受ける。カウンタ一致検出回路ＤＥ１１は、バッファ２１からクロック信号ＣＬＫが入力される。カウンタ一致検出回路ＤＥ１２〜ＤＥ１Ｗは、それぞれカウンタ一致検出回路ＤＥ１１〜ＤＥ１Ｗ−１から後述するカウンタ一致信号ｍ１１_ｎ〜ｍ１Ｗ−１_ｎがバッファ２２〜２Ｗに入力されると、バッファ２２〜２Ｗからクロック信号ＣＬＫが入力される。
【０１０４】
カウンタ一致検出回路ＤＥ１１〜ＤＥ１Ｗは、後述する有効ビット設定部４０から、検索対象のビットを示す信号（以下、ＢＡＳ信号）を受ける。カウンタ一致検出回路ＤＥ１１は、ＢＡＳ信号が示すビット（ｎ）に対応するカウンタ値と距離信号Ｄ１１が示す距離との一致を検出し、一致を検出したタイミングでバッファ２２とカウンタ一致検出回路ＤＥ１２にＨレベルの一致検出信号ｍ１１＿ｎを出力する。カウンタ一致検出回路ＤＥ１２は、Ｈレベルの一致検出信号ｍ１１＿ｎを受けると、ＢＡＳ信号が示すビットに対応するカウンタ値と距離信号Ｄ２が示す距離との一致を検出し、一致を検出したタイミングで、バッファ２３とカウンタ一致検出回路ＤＥ１３（図示せず）にＨレベルの一致検出信号ｍ１２＿ｎを出力する。以下同様にして、カウンタ一致検出回路ＤＥ１Ｗは、Ｈレベルの一致検出信号ｍ１ｗ−１＿ｎを受けると、ＢＡＳ信号が示すビットに対応するカウンタ値と距離信号Ｄ１Ｗが示す距離との一致を検出し、一致を検出したタイミングで、Ｈレベルの一致検出信号ｍ１ｗ＿ｎを出力する。
【０１０５】
ここで、カウンタ一致検出回路ＤＥ１１の構成例を示す概略構成図を図８に示す。図８に示すように、カウンタ一致検出回路ＤＥ１１は、Ｎビットのカウンタ３１２、一致検出回路３１３、及びマルチプレクサ３１４を有する。なお、カウンタ一致検出回路ＤＥ１２…ＤＥ１ｗについてもカウンタ一致検出回路ＤＥ１１と同様の構成を有する。
【０１０６】
カウンタ３１２は、バッファ２１からクロック信号ＣＬＫを受け、有効ビット設定部４０からＢＡＳ信号を受け、連想メモリ１１０の制御回路（図示せず）からリセット信号（ＲＳＴ）を受ける。カウンタ３１２は、クロック信号ＣＬＫのクロックに同期して、ＢＡＳ信号が示すビットについてカウントアップを行い、カウンタ値を一致検出回路３１３に出力する。
【０１０７】
一致検出回路３１３は、ＢＡＳ信号が示すビットに対応するカウンタ値と距離信号Ｄ１１の値との一致を検出する。一致検出回路３１３は、ＢＡＳ信号が示すビットに対応するカウンタ値と距離信号Ｄ１１の値との一致を検出すると、「１」を示す一検出信号ｍ１１_ｎをマルチプレクサ３１４に出力する。
【０１０８】
図９Ａは、本実施形態におけるカウンタ３１２と一致検出回路３１３の回路構成例を示している。図９Ａの例では、カウンタ３１２は３ビットカウンタで構成される。カウンタ３１２は、３つのセレクタ３１２ａ，３１２ｂ，３１２ｃと、各セレクタと接続された分周器３１２ｄ，３１２ｅ，３１２ｆとを有する。セレクタ３１２ａ，３１２ｂ，３１２ｃは、有効ビット設定部４０からＢＡＳ信号を受け、バッファ２１からクロック信号ＣＬＫを受ける。セレクタ３１２ａは、最上位ビットに対応し、最上位ビットを示すＢＡＳ信号（ＢＡＳ＜１＞）を受ける。セレクタ３１２ｂは、最上位から２番目のビットに対応し、２番目のビットを示すＢＡＳ信号（ＢＡＳ＜２＞）を受ける。セレクタ３１２ｃは、最下位ビットに対応し、最下位ビットを示すＢＡＳ信号（ＢＡＳ＜３＞）を受ける。ＢＡＳ信号は、１又は０を示す信号である。
【０１０９】
一致検出回路３１３は、ＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃと、ＡＮＤ回路３１３ｄ，３１３ｅとを有する。ＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃは、分周器３１２ｄ，３１２ｅ，３１２ｆとそれぞれ接続されている。
【０１１０】
セレクタ３１２ａ，３１２ｂ，３１２ｃのいずれかにＢＡＳ信号（＝１）が入力されると、ＢＡＳ信号（＝１）が入力されたセレクタは、クロック信号ＣＬＫを対応する分周器に入力する。クロック信号ＣＬＫが入力された分周器は、クロック信号ＣＬＫを分周して一致検出回路３１３へ出力する。なお、分周器３１２ｄ，３１２ｅは、下位のビットを示すＢＡＳ信号が入力されている場合であっても、下位のビットに対応する分周器のカウントアップによる桁上げ値が入力されるとカウントアップを行う。
【０１１１】
図９Ｂは、ＢＡＳ信号によって最上位から最下位ビットが指定された場合のカウンタ３１２の動作を示すである。ＢＡＳ信号により最上位ビットが指定されている場合（ＢＡＳ＜１＞＝１，ＢＡＳ＜２＞＝０，ＢＡＳ＜３＞＝０）、セレクタ３１２ｃはグランドに接地されているため、分周器３１２ｆ、３１２ｅからＥＸＮＯＲ回路３１３ｂ，３１３ｃに信号値「０」が出力される。分周器３１２ａには、クロック信号ＣＬＫが入力され、図９Ｂのｉ）に示すように、クロック信号ＣＬＫを２０回分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ａに出力する。つまり、この場合には、カウンタ３１２は、１ビットカウンタとして機能する。
【０１１２】
また、ＢＡＳ信号により最上位から２ビット目が指定されている場合（ＢＡＳ＜１＞＝０，ＢＡＳ＜２＞＝１，ＢＡＳ＜３＞＝０）、分周器３１２ｆからＥＸＮＯＲ回路３１３ｃに信号値「０」が出力される。分周器３１２ｅには、クロック信号ＣＬＫが入力され、図９Ｂのｉｉ）に示すように、クロック信号ＣＬＫを２０回分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ｂに出力する。分周器３１２ｄには、分周器３１２ｅからの桁上げ信号が入力され、図９Ｂのｉｉ）に示すように、クロック信号ＣＬＫを２１分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ａに出力する。つまり、この場合には、カウンタ３１２は、２ビットカウンタとして機能する。
【０１１３】
また、ＢＡＳ信号により最下位ビットが指定されている場合（ＢＡＳ＜１＞＝０，ＢＡＳ＜２＞＝０，ＢＡＳ＜３＞＝１）、分周器３１２ｆには、クロック信号ＣＬＫが入力され、図９Ｂのｉｉｉ）に示すように、クロック信号ＣＬＫを２０回分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ｃに出力する。分周器３１２ｅには、分周器３１２ｆからの桁上げ信号が入力され、図９Ｂのｉｉｉ）に示すように、クロック信号ＣＬＫを２１回分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ｂに出力する。また、分周器３１２ｄには、分周器３１２ｅからの桁上げ信号が入力され、図９Ｂのｉｉｉ）に示すように、クロック信号ＣＬＫを２２回分周した信号で示されるカウンタ値をＥＸＮＯＲ回路３１３ａに出力する。つまり、この場合には、カウンタ３１２は、３ビットカウンタとして機能する。
【０１１４】
図９Ａに戻り、説明を続ける。ＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃは、距離信号Ｄｉｊの各ビットの値Ｄ＜１＞，Ｄ＜２＞，Ｄ＜３＞を受け、分周器３１２ｄ，３１２ｅ，３１２ｆからそれぞれカウンタ値を受ける。
【０１１５】
ＥＸＮＯＲ回路３１３ａは、距離信号Ｄｉｊの最上位ビットの値Ｄ＜１＞と、分周器３１２ｄから出力されるカウンタ値とが一致する場合に、ＡＮＤ回路３１３ｄに「１」を示す検出信号を出力し、その検出信号（＝１）を最上位ビットに対応する一致検出信号ｍｉｊ＿１としてマルチプレクサ３１４に出力する。また、距離信号Ｄｉｊの最上位ビットの値Ｄ＜１＞とカウンタ値とが一致しない場合、ＡＮＤ回路３１３ｄに「０」を示す検出信号を出力し、その検出信号（＝０）を一致検出信号ｍｉｊ＿１としてマルチプレクサ３１４に出力する。
【０１１６】
ＥＸＮＯＲ回路３１３ｂは、距離信号Ｄｉｊの最上位から２番目のビットの値Ｄ＜２＞と、分周器３１２ｅから出力されるカウンタ値とが一致する場合に、ＡＮＤ回路３１３ｄに「１」を示す検出信号を出力し、一致しない場合には「０」を示す検出信号を出力する。
【０１１７】
ＥＸＮＯＲ回路３１３ｃは、距離信号Ｄｉｊの最下位ビットの値Ｄ＜３＞と、分周器３１２ｆから出力されるカウンタ値とが一致する場合に、ＡＮＤ回路３１３ｅに「１」を示す検出信号を出力し、一致しない場合には「０」を示す検出信号を出力する。
【０１１８】
ＡＮＤ回路３１３ｄは、ＥＸＮＯＲ回路３１３ａとＥＸＮＯＲ回路３１３ｂとから入力される検出信号の論理積の値を示す検出信号をＡＮＤ回路３１３ｅに出力し、その検出信号を最上位から２番目のビットに対応する一致検出信号ｍｉｊ＿２としてマルチプレクサ３１４に出力する。例えば、ＥＸＮＯＲ回路３１３ａとＥＸＮＯＲ回路３１３ｂとから検出信号（＝１）が出力された場合、つまり、上位２ビットの距離とカウンタ値とが一致している場合には、「１」を示す検出信号がＡＮＤ回路３１３ｅに出力され、「１」を示す一致検出信号ｍｉｊ＿２がマルチプレクサ３１４に出力される。また、ＥＸＮＯＲ回路３１３ａとＥＸＮＯＲ回路３１３ｂの少なくとも一方から検出信号（＝０）が出力された場合、つまり、上位２ビットの距離とカウンタ値とが一致していない場合には、「０」を示す検出信号がＡＮＤ回路３１３ｅに出力され、「０」を示す一致検出信号ｍｉｊ＿２がマルチプレクサ３１４に出力される。
【０１１９】
ＡＮＤ回路３１３ｅは、ＥＸＮＯＲ回路３１３ｃとＡＮＤ回路３１３ｄとから入力される検出信号の論理積の値を示す検出信号を最下位ビットに対応する一致検出信号ｍｉｊ＿３としてマルチプレクサ３１４に出力する。例えば、ＥＸＮＯＲ回路３１３ｃとＡＮＤ回路３１３ｄとから検出信号（＝１）が出力された場合、つまり、全ビットで表される距離とカウンタ値とが一致している場合には、一致検出信号ｍｉｊ＿３（＝１）が出力される。また、ＥＸＮＯＲ回路３１３ｃとＡＮＤ回路３１３ｄの少なくとも一方から検出信号（＝０）が出力された場合、つまり、全ビットで表される距離とカウンタ値とが一致していない場合には、一致検出信号ｍｉｊ＿３（＝０）がマルチプレクサ３１４に出力される。そして、一致検出回路３１３においては、ＥＸＮＯＲ回路３１３ａが「１」を示す検出信号を出力しない限り、ＡＮＤ回路３１３ｄ，３１３ｅとはそれぞれ「１」を示す一致検出信号ｍｉｊ＿２，ｍｉｊ＿３を出力することはない。
【０１２０】
図８に戻り、カウンタ一致検出回路ＤＥ１１におけるマルチプレクサ３１４は、ＢＡＳ信号で示されるビットに対応する、一致検出回路３１３から出力される一致検出信号ｍ１１＿ｎを、バッファ２２及びカウンタ一致検出回路ＤＥ１２に出力する。なお、カウンタ一致検出回路ＤＥ１Ｗにおけるマルチプレクサ３１４から出力される一致検出信号ｍ１Ｗ＿ｎは、有効ビット設定部４０に出力される。
【０１２１】
次に、図６、７を参照して、有効ビット設定部４０について説明する。有効ビット設定部４０は、クロック信号ＣＬＫと、距離／クロック数変換回路ＤＥ１〜ＤＥＲから出力される一致検出信号ｍｉＷ＿ｎ（１又は０）を受ける。有効ビット設定部４０は、いずれかの距離クロック数変換回路ＤＥ１〜ＤＥＲから一致検出信号ｍｉＷ＿ｎ（＝１）を受けると、クロック信号ＣＬＫに同期して、カウンタ一致検出回路ＤＥｉ１〜ＤＥｉＷにおける各カウンタ３１２及びマルチプレクサ３１４に対してＢＡＳ信号を出力する。
【０１２２】
有効ビット設定部４０からカウンタ一致検出回路ＤＥｉ１〜ＤＥｉＷにＢＡＳ信号を入力するために、１クロックサイクルが必要となる。有効ビット設定部４０は、ＢＡＳ信号を入力する間、ＣＬＫ＿ＡＣＴ信号をＡＮＤ回路６に入力し、クロック信号ＣＬＫが距離／クロック数変換回路ＤＥ１〜ＤＥＲに入力されないようにする。ＣＬＫ＿ＡＣＴ信号は、一致検出信号ｍｉＷ＿ｎを反転させた信号である。
【０１２３】
つまり、一致検出信号ｍｉＷ＿ｎが立ち上がると（一致検出信号ｍｉＷ＿ｎ＝１）、「０」を示すＣＬＫ＿ＡＣＴ信号がＡＮＤ回路６に入力され、一致検出信号ｍｉＷ＿ｎが立ち上がっていなければ（一致検出信号ｍ１Ｗ＿ｎ＝０）、「１」を示すＣＬＫ＿ＡＣＴ信号がＡＮＤ回路６に入力される。有効ビット設定部４０は、距離／クロック数変換回路ＤＥ１〜ＤＥＲから最下位ビットに対応する一致検出信号が立ち上がったタイミングでタイミング信号Ｃ１〜ＣＲをＷｉｎｎｅｒ検出器２０へ出力する。
【０１２４】
ＡＮＤ回路６は、クロック信号ＣＬＫと有効ビット設定部４０からのＣＬＫ＿ＡＣＴ信号（１又は０）とを受ける。ＡＮＤ回路６は、有効ビット設定部４０からのＣＬＫ＿ＡＣＴ信号とクロック信号ＣＬＫとの論理積を演算した結果を距離／クロック数変換回路ＤＥ１〜ＤＥＲに入力する。つまり、有効ビット設定部４０からＣＬＫ＿ＡＣＴ信号（＝０）が入力された場合には、クロック信号ＣＬＫが距離／クロック数変換回路ＤＥ１〜ＤＥＲに入力されず、ＣＬＫ＿ＡＣＴ信号（＝１）が入力された場合には、クロック信号ＣＬＫが距離／クロック数変換回路ＤＥ１〜ＤＥＲに入力される。
【０１２５】
ここで、図６に示す構成において、参照データが参照データ１、２であり、Ｒ＝２、Ｗ＝３である場合の動作例について説明する。図１０Ａは、参照データ１に対する距離／クロック数変換回路ＤＥ１と、参照データ２に対する距離／クロック数変換回路ＤＥ２とにおいて、参照データ１と検索データとの距離と、参照データ２と検索データとの距離とをそれぞれクロック数に変換する処理過程を示す図である。
【０１２６】
図１０Ａの例において、距離／クロック数変換回路ＤＥ１は、カウンタ一致検出回路ＤＥ１１〜ＤＥ１３を有し、距離／クロック数変換回路ＤＥ２は、カウンタ一致検出回路ＤＥ２１〜ＤＥ２３を有する。なお、図１０Ａにおけるカウンタ値と距離の各値の下線は、有効ビット設定部４０によって設定されたビット、つまり、距離とカウンタ値の一致検出対象となるビットであることを示している。
【０１２７】
カウンタ一致検出回路ＤＥ１１，ＤＥ１２，ＤＥ１３には、距離演算回路ＤＰ１１，ＤＰ１２，ＤＰ１３から距離信号Ｄ１１，Ｄ１２，Ｄ１３がそれぞれ入力される。この例において、距離信号Ｄ１１が示す距離は「５１０（＝１０１２）」であり、距離信号Ｄ１２が示す距離は「４１０（＝１００２）」であり、距離信号Ｄ１３が示す距離は「３１０（＝０１０２）」である。また、カウンタ一致検出回路ＤＥ２１，ＤＥ２２，ＤＥ２３には、距離演算回路ＤＰ２１，ＤＰ２２，ＤＰ２３から距離信号Ｄ２１，Ｄ２２，Ｄ２３がそれぞれ入力される。この例において、距離信号Ｄ２１が示す距離は「７１０（＝１１１２）」であり、距離信号Ｄ２２が示す距離は「０１０（＝０００２）」であり、距離信号Ｄ２３が示す距離は「２１０（＝０１０２）」である。なお、距離／クロック数変換回路ＤＥ１とＤＥ２における各カウンタ一致検出回路には、初期値として、最上位ビットを示すＢＡＳ信号（ＢＡＳ＜１＞＝１，ＢＡＳ＜２＞＝０，ＢＡＳ＜３＞＝０）が予め設定されている。
【０１２８】
連想メモリ１１０の制御回路（図示せず）から検索開始を示す信号ＳＢが入力されると、０クロック目において、カウンタ一致検出回路ＤＥ１１，ＤＥ１２は、それぞれ、最上位ビットに対応する分周器３１２ｄのカウンタ値「０」を一致検出回路３１３のＥＸＮＯＲ回路３１３ａに出力する。図１０Ａの例において、ＢＡＳ「１」，クロック「０」のとき、カウンタ一致検出回路ＤＥ１１における、下線で示す最上位ビットのカウンタ値「０００」と距離「１０１」とは一致しない。同様に、カウンタ一致検出回路ＤＥ２１における、下線で示す最上位ビットのカウンタ値「０００」と距離「１１１」とは一致しない。そのため、カウンタ一致検出回路ＤＥ１１とカウンタ一致検出回路ＤＥ２１において、それぞれ、ＥＸＮＯＲ回路３１３ａから「０」を示す検出信号がＡＮＤ回路３１３ｄに出力される。そして、カウンタ一致検出回路ＤＥ１１からカウンタ一致検出回路ＤＥ１２に一致検出信号ｍ１１＿１（＝０）が出力され、カウンタ一致検出回路ＤＥ２１からカウンタ一致検出回路ＤＥ２２に一致検出信号ｍ２１＿１（＝０）が出力される。
【０１２９】
有効ビット設定部４０は、０クロック目において、距離／クロック数変換回路ＤＥ１、ＤＥ２の最上位ビットに対応する一致検出信号がいずれも立ち上がっていないため、ＣＬＫ＿ＡＣＴ信号（＝１）をＡＮＤ回路６に出力する。これにより、カウンタ一致検出回路ＤＥ１１、ＤＥ２１にクロック信号ＣＬＫが入力される。
【０１３０】
カウンタ一致検出回路ＤＥ１１、ＤＥ２１は、それぞれのセレクタ３１２ａにクロック信号ＣＬＫを入力する。カウンタ一致検出回路ＤＥ１１における分周器３１２ｄはクロック信号ＣＬＫを２０回分周し、図１０Ｂに示すｔ１におけるカウンタ値「１」をＥＸＮＯＲ回路３１３ａに出力し、ＥＸＮＯＲ回路３１３ａから「１」を示す検出信号がＡＮＤ回路３１３ｄに出力される。そして、カウンタ一致検出回路ＤＥ１２とバッファ２２とに、一致検出信号ｍ１１＿１（＝１）が出力される。
【０１３１】
カウンタ一致検出回路ＤＥ１２は、一致検出信号ｍ１１_１（＝１）が入力されると、一致検出回路３１３において、最上位ビットに対応する分周器３１２ｄのカウンタ値と距離Ｄ１２との一致の検出を開始する。カウンタ一致検出回路ＤＥ１２における分周器３１２ｄはクロック信号ＣＬＫを２０回分周し、図１０Ｂに示すｔ１におけるカウンタ値「０」をＥＸＮＯＲ回路３１３ａに出力する。最上位ビットに対応するカウンタ値「０」と距離Ｄ１２「１００」とは一致しないため、ＥＸＮＯＲ回路３１３ａから「０」を示す検出信号がＡＮＤ回路３１３ｄに出力され、一致検出信号ｍ１２＿１（＝０）が出力される。従って、検索開始から１クロック目に、参照データ１について一致検出信号ｍ１３＿１（＝１）は出力されない。
【０１３２】
一方、図１０Ｂに示すように、カウンタ一致検出回路ＤＥ２１における分周器３１２ｄはクロック信号ＣＬＫを２０回分周し、図１０Ｂに示すｔ１におけるカウンタ値「１」をＥＸＮＯＲ回路３１３ａに出力し、ＥＸＮＯＲ回路３１３ａから「１」を示す検出信号がＡＮＤ回路３１３ｄに出力される。そして、カウンタ一致検出回路ＤＥ１２とバッファ２２とに、一致検出信号ｍ２１＿１（＝１）が出力される。
【０１３３】
カウンタ一致検出回路ＤＥ２２は、一致検出信号ｍ２１＿１（＝１）が入力されると、一致検出回路３１３において、最上位ビットに対応する分周器３１２ｄのカウンタ値と距離Ｄ２２との一致の検出を開始する。図１０Ｂに示すように、カウンタ一致検出回路ＤＥ２２における分周器３１２ｄはクロック信号ＣＬＫを２０回分周し、図１０Ｂに示すｔ１におけるカウンタ値「０」をＥＸＮＯＲ回路３１３ａに出力する。最上位ビットに対応するカウンタ値「０」と距離「０００」とは一致するため、ＥＸＮＯＲ回路３１３ａから「１」を示す検出信号がＡＮＤ回路３１３ｄに出力され、カウンタ一致検出回路ＤＥ２３とバッファ２３とに、一致検出信号ｍ２２＿１（＝１）が出力される。
【０１３４】
カウンタ一致検出回路ＤＥ２３は、一致検出信号ｍ２２＿１（＝１）が入力されると、一致検出回路３１３において、最上位ビットに対応する分周器３１２ｄのカウンタ値と距離Ｄ２３との一致の検出を開始する。図１０Ｂに示すように、カウンタ一致検出回路ＤＥ２３における分周器３１２ｄはクロック信号ＣＬＫを２０回分周し、一致検出信号ｍ２２＿１（＝１）が入力されたタイミングでカウンタ値「０」をＥＸＮＯＲ回路３１３ａに出力する。最上位ビットに対応するカウンタ値「０」と距離Ｄ２３「０１０」とは一致するため、ＥＸＮＯＲ回路３１３ａから「１」を示す検出信号がＡＮＤ回路３１３ｄに出力され、マルチプレクサ３１４から有効ビット設定部４０に一致検出信号ｍ２３＿１（＝１）が出力される。従って、検索開始から１クロック目で、参照データ２について一致検出信号ｍ２３_１（＝１）が出力される。
【０１３５】
有効ビット設定部４０は、距離／クロック数変換回路ＤＥ２から最上位ビットに対する一致検出信号ｍ２３＿１（＝１）が入力されると、検索開始から２クロック目に、最上位から２番目のビットを示すＢＡＳ信号（ＢＡＳ＜１＞＝０，ＢＡＳ＜２＞＝１，ＢＡＳ＜３＞＝０）を、距離／クロック数変換回路ＤＥ１とＤＥ２における各カウンタ一致検出回路に入力する。これにより、検出対象のビットが上位２ビットまで拡張される。また、有効ビット設定部４０は、ＣＬＫ＿ＡＣＴ信号（＝０）をＡＮＤ回路６に出力し、距離／クロック数変換回路ＤＥ１とＤＥ２にクロック信号ＣＬＫが入力されないようにする。
【０１３６】
カウンタ一致検出回路ＤＥ１１とＤＥ２１は、それぞれのカウンタ３１２において、最上位から２番目のビットに対応するセレクタ３１２ｂにＢＡＳ信号（ＢＡＳ＜２＞＝１）が入力されると、一致検出回路３１３において、上位２ビットのカウンタ値と距離との一致を検出する。
【０１３７】
ＢＡＳ信号（ＢＡＳ＜２＞＝１）が入力されると、図１０Ｃに示すように、カウンタ一致検出回路ＤＥ１１における分周器３１２ｅ，３１２ｄは、クロック信号ＣＬＫを２０，２１回それぞれ分周して２ビットのカウンタ値を出力する。検索開始から１クロック目に、カウンタ一致検出回路ＤＥ１１における分周器３１２ｄのカウンタ値「１」と距離Ｄ１１「１０１」とが一致している。そのため、カウンタ一致検出回路ＤＥ１１の分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ１におけるカウンタ値「１０」のビット値「１」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。つまり、距離「４」の検索が打ち消されたことになる。上位２ビットに対応するカウンタ値「１０」と距離Ｄ１１「１０１」とは一致するため、ＥＸＮＯＲ回路３１３ａ，３１３ｂからＡＮＤ回路３１３ｄ，３１３ｅに「１」を示す検出信号がそれぞれ出力され、ＥＸＮＯＲ回路３１３ａとＡＮＤ回路３１３ｄからマルチプレクサ３１４に、一致検出信号ｍ１１＿１（＝１），ｍ１１＿２（＝１）がそれぞれ出力される。そして、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ１２とバッファ２２に、一致検出信号ｍ１１＿２（＝１）が出力される。
【０１３８】
カウンタ一致検出回路ＤＥ１２は、一致検出信号ｍ１１＿２（＝１）が入力されると、一致検出回路３１３において、上位２ビットのカウンタ値と距離Ｄ１２との一致の検出を開始する。ＢＡＳ信号（ＢＡＳ＜２＞＝１）が入力されると、図１０Ｃに示すように、カウンタ一致検出回路ＤＥ１２における分周器３１２ｅ，３１２ｄは、クロック信号ＣＬＫを２０，２１回それぞれ分周して２ビットのカウンタ値を出力する。図１０Ｃに示すように、ｔ１におけるカウンタ一致検出回路ＤＥ１２の分周器３１２ｄ，３１２ｅのカウンタ値「００」のビット値「０」，「０」がＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力される。上位２ビットに対応するカウンタ値「００」と距離Ｄ１２「１００」とは一致しないため、ＥＸＮＯＲ回路３１３ａ，３１３ｂからＡＮＤ回路３１３ｄにそれぞれ「０」，「１」を示す検出信号が出力され、一致検出信号ｍ１２＿２（＝０）がマルチプレクサ３１４からカウンタ一致検出回路ＤＥ１３とバッファ２３に出力される。
【０１３９】
カウンタ一致検出回路ＤＥ２１における分周器３１２ｅ，３１２ｄは、ＢＡＳ信号（ＢＡＳ＜２＞＝１）が入力されると、図１０Ｃに示すように、クロック信号ＣＬＫをそれぞれ２０，２１回分周して２ビットのカウンタ値を出力する。検索開始から１クロック目に、カウンタ一致検出回路ＤＥ２１における分周器３１２ｄのカウンタ値「１」と距離「１１１」とが一致している。そのため、カウンタ一致検出回路ＤＥ２１の分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ１におけるカウンタ値「１０」のビット値「１」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。つまり、距離「２」の検索が打ち消されたことになる。上位２ビットに対応するカウンタ値「１０」と距離Ｄ２１「１１１」とは一致しないため、ＥＸＮＯＲ回路３１３ａ，３１３ｂからＡＮＤ回路３１３ｄに「１」，「０」を示す検出信号がそれぞれ出力され、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ２２とバッファ２２に、一致検出信号ｍ２１＿２（＝０）が出力される。
【０１４０】
有効ビット設定部４０は、２クロック目において、カウンタ一致検出回路ＤＥ１、ＤＥ２の最上位から２番目のビットに対応する一致検出信号（ｍ１３＿２，ｍ２３＿２）はいずれも立ち上がっていないため、ＡＮＤ回路６にＣＬＫ＿ＡＣＴ信号（＝１）を入力して、距離／クロック数変換回路ＤＥ１とＤＥ２にクロック信号ＣＬＫが入力されるようにする。
【０１４１】
カウンタ一致検出回路ＤＥ１１において、上位２ビットについて一致検出信号ｍ１１＿２（＝１）が検索開始から２クロック目に出力されている。そのため、検索開始から３クロック目では、カウンタ一致検出回路ＤＥ１１において一致検出の動作を停止する。
【０１４２】
カウンタ一致検出回路ＤＥ１２は、検索開始から３クロック目に、セレクタ３１２ｂを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ２におけるカウンタ値「０１」のビット値「０」，「１」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットのカウンタ値「０１」と距離Ｄ１２「１００」とは一致しない。そのため、カウンタ一致検出回路ＤＥ１２において、カウンタ一致検出回路ＤＥ１３とバッファ２３に一致検出信号ｍ１２＿２（＝０）が出力される。
【０１４３】
カウンタ一致検出回路ＤＥ２１も同様に、検索開始から３クロック目に、セレクタ３１２ｂを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ２におけるカウンタ値「１１」のビット値「１」，「１」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットのカウンタ値「１１」と距離Ｄ２１「１１１」とは一致する。そのため、カウンタ一致検出回路ＤＥ２１において、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ２２とバッファ２２に一致検出信号ｍ２１＿２（＝１）が出力される。
【０１４４】
カウンタ一致検出回路ＤＥ２２は、一致検出信号ｍ２１＿２（＝１）が入力されると、一致検出回路３１３において、上位２ビットのカウンタ値と距離Ｄ２２との一致の検出を開始する。図１０Ｃに示すように、カウンタ一致検出回路ＤＥ２２における分周器３１２ｅ，３１２ｄは、ｔ２におけるカウンタ値「００」のビット値「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットに対応するカウンタ値「００」と距離Ｄ２２「０００」とは一致する。そのため、カウンタ一致検出回路ＤＥ２２において、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ２３とバッファ２３に一致検出信号ｍ２２＿２（＝１）が出力される。
【０１４５】
カウンタ一致検出回路ＤＥ２３は、一致検出信号ｍ２２＿２（＝１）が入力されると、上位２ビットのカウンタ値と距離Ｄ２３との一致の検出を開始する。図１０Ｃに示すように、カウンタ一致検出回路ＤＥ２３における分周器３１２ｅ，３１２ｄは、ｔ２におけるカウンタ値「００」のビット値「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットに対応するカウンタ値「００」と距離Ｄ２３「０１０」とは一致しない。そのため、カウンタ一致検出回路ＤＥ２３において、マルチプレクサ３１４から有効ビット設定部４０に一致検出信号ｍ２３＿２（＝０）が出力される。
【０１４６】
３クロック目おいて、距離／クロック数変換回路ＤＥ１とＤＥ２のいずれも最上位から２番目のビットに対応する一致検出信号（ｍ１３＿２，ｍ２３＿２）が立ち上がっていない。そのため、４クロック目においても有効ビット設定部４０からＡＮＤ回路６にＣＬＫ＿ＡＣＴ信号（＝１）が入力される。
【０１４７】
カウンタ一致検出回路ＤＥ１１において、上位２ビットについて一致検出信号ｍ１１＿２（＝１）が検索開始から２クロック目に出力されているため、４クロック目においても一致検出の動作を停止する。
【０１４８】
カウンタ一致検出回路ＤＥ１２は、検索開始から４クロック目に、セレクタ３１２ｂを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ３におけるカウンタ値「１０」のビット値「１」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットのカウンタ値「１０」と距離Ｄ１２「１００」とは一致する。そのため、カウンタ一致検出回路ＤＥ１２において、カウンタ一致検出回路ＤＥ１３とバッファ２３に一致検出信号ｍ１２＿２（＝１）が出力される。
【０１４９】
カウンタ一致検出回路ＤＥ１３は、一致検出信号ｍ１２＿２（＝１）が入力されると、一致検出回路３１３において、上位２ビットのカウンタ値と距離Ｄ１３との一致の検出を開始する。図１０Ｃに示すように、カウンタ一致検出回路ＤＥ１３における分周器３１２ｅ，３１２ｄは、ｔ３におけるカウンタ値「００」のビット値「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットに対応するカウンタ値「００」と距離Ｄ１３「０１１」とは一致しない。そのため、カウンタ一致検出回路ＤＥ１３において、マルチプレクサ３１４から有効ビット設定部４０に一致検出信号ｍ１３_２（＝０）が出力される。
【０１５０】
一方、カウンタ一致検出回路ＤＥ２１，ＤＥ２２において、上位２ビットについての一致検出信号ｍ２１＿２，ｍ２２＿２（＝１）が検索開始から２クロック，３クロック目にそれぞれ出力されているため、４クロック目ではカウンタ一致検出回路ＤＥ２１，ＤＥ２２は一致検出の動作を停止する。
【０１５１】
カウンタ一致検出回路ＤＥ２３は、検索開始から４クロック目に、セレクタ３１２ｂを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅは、図１０Ｃに示すｔ３におけるカウンタ値「０１」のビット値「０」，「１」をＥＸＮＯＲ回路３１３ａ，３１３ｂにそれぞれ出力する。上位２ビットのカウンタ値「０１」と距離Ｄ２３「０１０」とが一致するため、マルチプレクサ３１４から有効ビット設定部４０に一致検出信号ｍ２３＿２（＝１）が出力される。
【０１５２】
有効ビット設定部４０は、４クロック目において、最上位から２番目のビットに対する一致検出信号ｍ２３＿２（＝１）が距離／クロック数変換回路ＤＥ２から入力されると、検索開始から５クロック目に、最下位ビットを示すＢＡＳ信号（ＢＡＳ＜１＞＝０，ＢＡＳ＜２＞＝０，ＢＡＳ＜３＞＝１）を、距離／クロック数変換回路ＤＥ１とＤＥ２における各カウンタ一致検出回路に入力する。これにより、一致検出の対象ビットは、最上位ビットから最下位ビットまで拡張される。また、有効ビット設定部４０は、ＣＬＫ＿ＡＣＴ信号（＝０）をＡＮＤ回路６に入力し、距離／クロック数変換回路ＤＥ１とＤＥ２にクロック信号ＣＬＫが入力されないようにする。
【０１５３】
カウンタ一致検出回路ＤＥ１１とＤＥ２１は、検索開始から５クロック目に、それぞれのカウンタ３１２において、最下位のビットに対応するセレクタ３１２ｃにＢＡＳ信号（ＢＡＳ＜３＞＝１）が入力されると、一致検出回路３１３において、全てのビットのカウンタ値と距離との一致を検出する。
【０１５４】
カウンタ一致検出回路ＤＥ１１における分周器３１２ｆ，３１２ｅ，３１３ｄは、ＢＡＳ信号（ＢＡＳ＜３＞＝１）が入力されると、図１０Ｄに示すように、クロック信号ＣＬＫを２０，２１，２２回それぞれ分周して３ビットのカウンタ値を出力する。検索開始から２クロック目に、カウンタ一致検出回路ＤＥ１１における分周器３１２ｄ，３１２ｅのカウンタ値「１０」と距離Ｄ１１「１０１」とが一致している。そのため、カウンタ一致検出回路ＤＥ１１の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ３におけるカウンタ値「１００」のビット値「１」，「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。つまり、距離「４」の検索が打ち消されたことになる。全ビットに対応するカウンタ値「１００」と距離Ｄ１１「１０１」とは一致しないため、ＥＸＮＯＲ回路３１３ａ，３１３ｂからＡＮＤ回路３１３ｄに「１」，「１」を示す検出信号がそれぞれ出力され、ＥＸＮＯＲ回路３１３ｃからＡＮＤ回路３１３ｅに「０」を示す検出信号が出力される。そして、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ１２とバッファ２２に、一致検出信号ｍ１１＿３（＝０）が出力される。
【０１５５】
カウンタ一致検出回路ＤＥ２１における分周器３１２ｆ，３１２ｅ，３１３ｄは、ＢＡＳ信号（ＢＡＳ＜３＞＝１）が入力されると、図１０Ｄに示すように、クロック信号ＣＬＫを２０，２１，２２回それぞれ分周して３ビットのカウンタ値を出力する。検索開始から３クロック目に、カウンタ一致検出回路ＤＥ２１における分周器３１２ｄ，３１２ｅのカウンタ値「１１」と距離Ｄ２１「１１１」とが一致している。そのため、カウンタ一致検出回路ＤＥ１１の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ５におけるのカウンタ値「１１０」のビット値「１」，「１」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。つまり、距離「６」の検索が打ち消されたことになる。全ビットに対応するカウンタ値「１１０」と距離Ｄ２１「１１１」とは一致しないため、ＥＸＮＯＲ回路３１３ａ，３１３ｂからＡＮＤ回路３１３ｄに「１」，「１」を示す検出信号がそれぞれ出力され、ＥＸＮＯＲ回路３１３ｃからＡＮＤ回路３１３ｅに「０」を示す検出信号が出力される。そして、マルチプレクサ３１４からカウンタ一致検出回路ＤＥ２２とバッファ２２に、一致検出信号ｍ２１＿３（＝０）が出力される。
【０１５６】
検索開始から５クロック目において、カウンタ一致検出回路ＤＥ１１とＤＥ２１のいずれも最下位ビットのカウンタ値と距離とが一致しないため、カウンタ一致検出回路ＤＥ１１とＤＥ２１においてクロック信号ＣＬＫが入力される。
【０１５７】
カウンタ一致検出回路ＤＥ１１は、検索開始から６クロック目に、セレクタ３１２ｂを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ４におけるカウンタ値「１０１」のビット値「１」，「０」，「１」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「１０１」と距離Ｄ１１「１０１」とが一致するため、カウンタ一致検出回路ＤＥ１１において、カウンタ一致検出回路ＤＥ１２とバッファ２２に一致検出信号ｍ１１＿３（＝１）が出力される。
【０１５８】
カウンタ一致検出回路ＤＥ１２は、一致検出信号ｍ１１＿３（＝１）が入力されると、一致検出回路３１３において、全てのビットのカウンタ値と距離との一致を検出する。検索開始から４クロック目に、カウンタ一致検出回路ＤＥ１２における分周器３１２ｄ，３１２ｅ，３１２ｆのカウンタ値「１０」と距離Ｄ１１「１００」とが一致している。そのため、カウンタ一致検出回路ＤＥ１２の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ４におけるカウンタ値「１００」のビット値「１」，「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「１００」と距離Ｄ１２「１００」とが一致するため、カウンタ一致検出回路ＤＥ１２において、カウンタ一致検出回路ＤＥ１３とバッファ２３に一致検出信号ｍ１２＿３（＝１）が出力される。
【０１５９】
カウンタ一致検出回路ＤＥ１３は、一致検出信号ｍ１２＿３（＝１）が入力されると、一致検出回路３１３において、全てのビットのカウンタ値と距離との一致の検出を開始する。カウンタ一致検出回路ＤＥ１３の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ４におけるカウンタ値「０００」のビット値「０」，「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「０００」と距離Ｄ１３「０１１」とは一致しないため、カウンタ一致検出回路ＤＥ１３において、有効ビット設定部４０に一致検出信号ｍ１３＿３（＝０）が出力される。
【０１６０】
一方、カウンタ一致検出回路ＤＥ２１は、検索開始から６クロック目に、セレクタ３１２ｃを介してクロック信号ＣＬＫが入力されると、分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ６におけるカウンタ値「１１１」のビット値「１」，「１」，「１」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「１１１」と距離Ｄ２１「１１１」とは一致するため、カウンタ一致検出回路ＤＥ２１において、カウンタ一致検出回路ＤＥ２２とバッファ２２に一致検出信号ｍ２１＿３（＝１）が出力される。
【０１６１】
カウンタ一致検出回路ＤＥ２２は、一致検出信号ｍ２１＿３（＝１）が入力されると、一致検出回路３１３において、全てのビットのカウンタ値と距離との一致の検出を開始する。検索開始から３クロック目に、カウンタ一致検出回路ＤＥ２２における分周器３１２ｄ，３１２ｅのカウンタ値「００」と距離Ｄ２２「０００」とが一致している。そのため、カウンタ一致検出回路ＤＥ２２の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ６におけるカウンタ値「０００」のビット値「０」，「０」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「０００」と距離Ｄ２２「０００」とが一致するため、カウンタ一致検出回路ＤＥ２２において、カウンタ一致検出回路ＤＥ２３とバッファ２３に一致検出信号ｍ２２＿３（＝１）が出力される。
【０１６２】
カウンタ一致検出回路ＤＥ２３は、一致検出信号ｍ２２＿３（＝１）が入力されると、一致検出回路３１３において、全てのビットのカウンタ値と距離との一致の検出を開始する。検索開始から４クロック目に、カウンタ一致検出回路ＤＥ２３における分周器３１２ｄ，３１２ｅのカウンタ値「０１」と距離Ｄ２３「０１０」とが一致している。そのため、カウンタ一致検出回路ＤＥ２３の分周器３１２ｄ，３１２ｅ，３１２ｆは、図１０Ｄに示すｔ６におけるカウンタ値「０１０」のビット値「０」，「１」，「０」をＥＸＮＯＲ回路３１３ａ，３１３ｂ，３１３ｃにそれぞれ出力する。全ビットのカウンタ値「０１０」と距離Ｄ２３「０１０」とが一致するため、カウンタ一致検出回路ＤＥ２３において、有効ビット設定部４０に一致検出信号ｍ２３＿３（＝１）が出力される。
【０１６３】
有効ビット設定部４０は、距離／クロック数変換回路ＤＥ２から最下位ビットに対する一致検出信号ｍ２３＿３（＝１）を受けると、その一致検出信号を受けたタイミングで、距離／クロック数変換回路ＤＥ２に対するタイミング信号Ｃ２をＷｉｎｎｅｒ検出器２０に出力する。
【０１６４】
このように、図１０Ａの例では、参照データ２について６クロックサイクルでタイミング信号Ｃ２が出力される。第１実施形態の方法を用いた場合には、参照データ２の場合、９クロックサイクル（＝７＋０＋２）必要であったが、本実施形態の方法を用いると３クロックサイクル削減されている。
【０１６５】
一致検出回路３１３は、上位Ｊビット（１≦Ｊ≦Ｎ）について距離とカウンタ値との一致を検出した一致検出信号を出力する。下位からｋビット目が一致検出の対象ビットとして設定されているとき、下位ｋ−１ビットを無視した上位（Ｎ−（ｋ−１））ビットの一致を示す一致検出信号を出力する。そのため、ｋビット目が対象ビットのときに全ての参照データについて一致検出信号が「０」であれば、全ての参照データは、距離２ｋ−１以上の距離を持つことを意味する。この場合には、下位からｋビット目のカウンタにクロック信号が入力されてカウントアップされる。これは、下位からｋビット目が「１」になることを意味しており、１クロックサイクルで、距離２ｋ−１が打ち消されたことに相当する。
【０１６６】
一方、いずれかの参照データについて出力された一致検出信号が「１」であれば、その参照データは、２ｋ−１の距離がないことを意味する。この場合には、対象ビットを下位からｋ−１番目のビットに設定し、全ての参照データについて距離２ｋ−２を順次打ち消す。
【０１６７】
つまり、最上位ビットから任意のビット単位に一致の検出対象となるビットを拡張して、カウンタ値と距離との一致を検出することで、大きい距離を順次打ち消している。これにより、第１、第２実施形態における一つの参照データの最長検索時間が”Ｍ×２Ｎ−１×τＣＬＫ”であるのに対し、本実施形態では、”（Ｍ×Ｎ＋Ｎ−１）×τＣＬＫ”に削減することが可能になる。
【０１６８】
＜第４実施形態＞
第１実施形態及び第２実施形態では、式（１）を用いて算出された検索データと参照データとの各距離をクロック数に変換する処理を、その距離に一致する回数だけ繰り返すことで、各距離の二乗値の和、つまり、ユークリッド距離の和に相当するクロック数に変換する例について説明した。本実施形態では、各距離演算回路（ＤＰ１１，ＤＰ１２，…ＤＰＲＷ）において、各距離の二乗値の演算を行い、演算された各距離の二乗値を、距離／クロック数変換回路（ＤＣ１，ＤＣ２，…ＤＣＲ）においてクロック数に変換する例について説明する。
【０１６９】
図１１は、本実施形態における距離演算回路の構成例を示す概略構成図である。距離演算回路ＤＰｉｊ（１≦ｉ≦Ｒ，１≦ｊ≦Ｗ）は、例えば、距離が４ビットで表される場合、つまり、Ｍ＝４の場合に、演算回路６１〜６４を含む演算回路群６０と、シフトレジスタ６５と、乗数ビットシフト回路６６とを有する。シフトレジスタ６５は、３ビットのシフトレジスタであり、３つのフリップフロップ回路６５ａ〜６５ｃを直列に接続して構成されている。
【０１７０】
図１１の例において、演算回路６１〜６４とフリップフロップ回路６５ａ〜６５ｃは、この順に、最上位ビットから最下位ビット（全７ビット）に対応して並んでいる。演算回路６１〜６４には、それぞれ、参照データ（ＲｅＳ）を反転させた反転参照データ（ＲｅＳＱ）と、検索データ（ＩｎＳ）の各ビットの値が入力される。なお、Ｓは１≦Ｓ≦４を満たす整数である。
【０１７１】
演算回路６１〜６４は、制御回路(図示せず)から入力される二乗計算制御信号ＳＱの信号値が「０」である場合、入力される反転参照データと検索データの絶対値差（ＡＤ１，ＡＤ２，ＡＤ３，ＡＤ４）を算出する。つまり、この場合には、演算回路６１〜６４は減算器として機能する。
【０１７２】
また、制御回路(図示せず)から入力される二乗計算制御信号ＳＱの信号値が「１」である場合、演算回路６１〜６４は、加算器として機能する。つまり、演算回路６１は、入力される後述の被加算値Ｍ１と、シフト演算値ＴＥ０とを加算し、加算結果を、シフト演算値ＴＥ１として演算回路６２に出力する。演算回路６２は、入力される被加算値Ｍ２と、演算回路６１から入力されるシフト演算値ＴＥ１とを加算し、加算結果を、シフト演算値ＴＥ２として演算回路６３に出力する。演算回路６３は、入力される被加算値Ｍ３と、演算回路６２から入力されるシフト演算値ＴＥ２とを加算し、加算結果を、シフト演算値ＴＥ３として演算回路６４に出力する。演算回路６４は、入力される被加算値Ｍ４と、演算回路６３から入力されるシフト演算値ＴＥ３とを加算し、加算結果を、シフト演算値ＴＥ４としてシフトレジスタ６５のフリップフロップ回路６５ａに出力する。
【０１７３】
また、演算回路６１〜６４は、制御回路（図示せず）からマンハッタン距離（ＭＤ）又はユークリッド距離（ＥＤ）を示す制御信号を受ける。本実施形態において、マンハッタン距離（ＭＤ）の場合の信号値を「１」とし、ユークリッド距離（ＥＤ）の場合の信号値を「０」とする。演算回路６１〜６４は、制御信号に応じて上記絶対値差ＡＤＳ又は加算結果を示すＤＯＵＴｋ（０≦ｋ≦４）を距離／クロック数変換回路ＤＣｉに出力する。
【０１７４】
フリップフロップ回路６５ａは、演算回路６４から入力されるシフト演算値ＴＥ４を、クロック信号ＣＬＫに同期して、シフト演算値ＴＥ５としてフリップフロップ回路６５ｂに出力するとともに、シフト演算値ＴＥ５を示す出力値ＤＯＵＴ５を距離／クロック数変換回路ＤＣｉに出力する。
【０１７５】
フリップフロップ回路６５ｂは、フリップフロップ回路６５ａから入力されるシフト演算値ＴＥ５を、クロック信号ＣＬＫに同期して、シフト演算値ＴＥ６としてフリップフロップ回路６５ｃに出力するとともに、そのシフト演算値ＴＥ６を示す出力値ＤＯＵＴ６を距離／クロック数変換回路ＤＣｉに出力する。
【０１７６】
フリップフロップ回路６５ｃは、フリップフロップ回路６５ｂから入力されるシフト演算値ＴＥ６を、クロック信号ＣＬＫに同期して、シフト演算値ＴＥ７を出力値ＤＯＵＴ７として距離／クロック数変換回路ＤＣｉに出力する。
【０１７７】
つまり、二乗計算制御信号ＳＱ（＝１）が入力されると、演算回路６１〜６４においてシフト演算値ＴＥＳを算出し、演算回路６１〜６４及びシフトレジスタ６５において、１クロックごとに、各シフト演算値を下位方向に１ビットシフトさせる処理を行う。この処理は、二乗計算の終了を示す信号が制御回路（図示せず）から入力されるまで行われる。
【０１７８】
ここで、演算回路６１〜６４の回路構成について説明する。図１２は、演算回路６１〜６４の回路構成例を示す図である。図１２の例において、演算回路６１〜６４は、マルチプレクサ７１，７２，７８と、全加算器７３と、Ｄフリップフロップ回路７４と、反転制御回路７５と、ラッチ回路７６と、ＡＮＤ回路７７とを有する。
【０１７９】
マルチプレクサ７１は、検索データＩｎＳ（Ｓは１≦Ｓ≦４を満たす整数）と、シフト演算値ＴＥＳ−１とを受ける。マルチプレクサ７２は、参照データＲＥＳを反転させた反転参照データＲｅＳＱと、ＡＮＤ回路７７から入力される被加算値ＭＳとを受ける。
【０１８０】
マルチプレクサ７１，７２は、制御回路（図示せず）から二乗計算制御信号ＳＱが入力される。本実施形態において、二乗計算制御信号ＳＱの信号値が「１」の場合には、距離演算回路ＤＰｉｊにおいて、距離の二乗計算を行い、信号値が「０」である場合には距離演算回路ＤＰｉｊにおいて、参照データと検索データとの差の絶対値（絶対値差）を算出する。
【０１８１】
マルチプレクサ７１は、二乗計算制御信号ＳＱの信号値が「０」の場合、検索データＩｎＳを全加算器７３に出力し、信号値が「１」の場合には、シフト演算値ＴＥＳ−１を全加算器７３に出力する。マルチプレクサ７２は、二乗計算制御信号ＳＱの信号値が「０」の場合、反転参照データＲｅＳＱを全加算器７３に出力し、信号値が「１」の場合には、被加算値ＭＳを全加算器７３に出力する。
【０１８２】
全加算器７３は、下位ビットからの桁上げ値を受ける端子ＣＢと、上位ビットへ桁上げ値を出力する端子ＣＮ又はＣＡ１を有する。なお、演算回路６４における端子ＣＢは、下位ビットからの桁上げ値ではなく、演算回路６１における桁上げ値が入力される。演算回路６１は最上位ビットに対応するため、演算回路６１における桁上げ値を端子ＣＡ１から演算回路６４へ出力する。
【０１８３】
また、演算回路６４における端子ＣＢは、ＡＮＤ回路６４ａ（図１１参照）と接続されている。ＡＮＤ回路６４ａには、制御回路（図示せず）からの制御信号（ＭＤ又はＥＤ）と、演算回路６１の端子ＣＡ１から出力される桁上げ値とが入力され、制御信号の信号値と桁上げ値の論理積を演算した結果を出力する。
【０１８４】
つまり、演算回路６１〜６４における全加算器７３は、マルチプレクサ７１から出力される検索データＩｎＳ又はシフト演算値ＴＥＳ−１と、マルチプレクサ７２から出力される反転参照データＲｅＳＱ又は被加算値ＭＳと、入力される桁上げ値とを加算する。以下、演算回路６１〜６４における全加算器７３のより具体的な処理について説明する。
【０１８５】
演算回路６１は、最上位ビットに対応するため、上位ビットにおけるシフト演算値がマルチプレクサ７１に入力されない。そのため、演算回路６１では、信号値「１」を示す二乗計算制御信号ＳＱが制御回路（図示せず）から出力されると、シフト演算値ＴＥ０として「０」を入力する。従って、演算回路６１における全加算器７３は、マルチプレクサ７２から出力される被加算値Ｍ１と、端子ＣＢから入力される演算回路６２の桁上げ値と、シフト演算値ＴＥ０（＝０）を加算し、加算結果をＤフリップフロップ回路７４に出力する。
【０１８６】
演算回路６２，６３における各全加算器７３は、信号値「１」を示す二乗計算制御信号ＳＱが制御回路から出力されると、それぞれ、マルチプレクサ７２から出力される被加算値Ｍ２，Ｍ３と、端子ＣＢから入力される演算回路６３，６４の桁上げ値と、演算回路６１，６２から入力されるシフト演算値ＴＥ１，ＴＥ２を加算して、加算結果をＤフリップフロップ回路７４に出力する。
【０１８７】
演算回路６４における全加算器７３は、信号値「１」を示す二乗計算制御信号ＳＱが制御回路から出力されると、マルチプレクサ７２から出力される被加算値Ｍ４と、端子ＣＢを介してＡＮＤ回路６４ａから入力される値と、演算回路６３から入力されるシフト演算値ＴＥ３とを加算して、加算結果をＤフリップフロップ回路７４に出力する。つまり、マンハッタン距離（ＭＤ）を示す制御信号（＝１）がＡＮＤ回路（図示せず）に入力され、演算回路６１の端子ＣＡ１からの桁上げ値「１」がＡＮＤ回路（図示せず）に入力されると、演算回路６４の端子ＣＢに「１」が入力されて加算される。
【０１８８】
次に、演算回路６１〜６４における反転制御回路７５は、演算回路６１からの最上位ビットの桁上げ値を示す信号を受ける端子ＣＡ２を有し、端子ＣＡ２を介して入力される演算回路６１の桁上げ値＝「０」である場合には、全加算器７３から出力された算出結果を反転し、反転した値（絶対値差ＡＤＳ）をラッチ回路７６へ出力する。また、演算回路６１の桁上げ値＝「１」である場合には、全加算器７３から出力された算出結果を反転せずにラッチ回路７６へ出力する。
【０１８９】
演算回路６１〜６４におけるラッチ回路７６は、二乗計算制御信号ＳＱを受ける。ラッチ回路７６は、二乗計算制御信号ＳＱの信号値が「０」から「１」になるタイミングで、反転制御回路７５から出力された絶対値差（ＡＤＳ）を保存する。そして、ＡＮＤ回路７７と乗数ビットシフト回路６６とマルチプレクサ７８にその絶対値差（ＡＤＳ）を出力する。
【０１９０】
演算回路６１〜６４におけるＡＮＤ回路７７は、乗数ビットシフト回路６６から入力される乗数ビットＭＢと、ラッチ回路７６から入力される絶対値差（ＡＤＳ）との論理積の値をマルチプレクサ７２に出力する。
【０１９１】
絶対値差ＡＤＳが算出された後、制御回路（図示せず）により、演算回路６１〜６４におけるＤフリップフロップ回路７４にクロック信号ＣＬＫが入力される。演算回路６１〜６４におけるＤフリップフロップ回路７４は、クロック信号ＣＬＫのクロックが立ち上がるタイミングで、全加算器７３から出力される加算結果を入力する。そして、クロックが立ち下がるタイミングで、その加算結果が、シフト演算値（ＴＥＳ）として、下位ビットの演算回路におけるマルチプレクサ７１又はシフトレジスタ６５に出力される。
【０１９２】
演算回路６１〜６４におけるマルチプレクサ７８は、制御回路（図示せず）からマンハッタン距離（ＭＤ）又はユークリッド距離（ＥＤ）を示す制御信号を受ける。例えば、この例において、マンハッタン距離（ＭＤ）の場合の信号値を「１」とし、ユークリッド距離（ＥＤ）の場合の信号値を「０」とする。マルチプレクサ７８は、マンハッタン距離（ＭＤ）を示す制御信号（＝１）が入力されると、演算回路６１〜６４における各ラッチ回路７６から出力される算出結果（絶対値差ＡＤＳ）を出力する。また、マルチプレクサ７８は、ユークリッド距離（ＥＤ）を示す制御信号（＝０）が入力されると、演算回路６１〜６４における各Ｄフリップフロップ回路７４から出力される算出結果（ＴＥＳ）を出力する。
【０１９３】
乗数ビットシフト回路６６は、クロック信号ＣＬＫに同期して、演算回路６１〜６４におけるラッチ回路７６から出力される絶対値差ＡＤＳの値を受ける。乗数ビットシフト回路６６は、下位ビットから順に、つまり、絶対値差ＡＤ４→ＡＤ３→ＡＤ２→ＡＤ１の順に、その絶対値差を乗数ビットＭＢとしてＡＮＤ回路７７に出力する。乗数ビットシフト回路６６は、最上位ビットの絶対値差（ＡＤ１）の値を出力すると、制御回路（図示せず）に二乗計算の終了を示す信号を出力する。
【０１９４】
ＡＮＤ回路７７は、乗数ビットシフト回路６６から入力される乗数ビットＭＢと、ラッチ回路７６から入力される絶対値差ＡＤＳとの論理積の値を、被加算値ＭＳとしてマルチプレクサ７２に出力する。
【０１９５】
図１３は、距離演算回路ＤＰｉｊにおける二乗計算の処理過程を示す図である。この例では、検索データと参照データとの絶対値差ＡＤＳ＝７１０＝０１１１２である場合を示している。図１３の例では、演算回路６１〜６４の各ＡＮＤ回路７７には、クロック信号ＣＬＫに同期して、絶対値差の下位ビットから「１→１→１→０」の順に、乗数ビットＭＢが乗数ビットシフト回路６６によって入力される。また、演算回路６１〜６４のマルチプレクサ７１には、シフト演算値ＴＥＳ−１として初期値「０」が設定されている。
【０１９６】
距離演算回路ＤＰｉｊは、二乗計算制御信号ＳＱ（＝１）が制御回路から入力されると二乗計算を開始する。演算回路６１〜６４において、各マルチプレクサ７１に設定されているシフト演算値ＴＥＳ−１「００００」が、全加算器７３に入力される（ステップＳ１）。また、演算回路６１〜６４のＡＮＤ回路７７から、乗数ビット”１”と絶対値差ＡＤＳ「０１１１」との論理積を示す被加算値ＭＳ「０１１１」が各マルチプレクサ７２に入力され、各マルチプレクサ７２から全加算器７３に被加算値ＭＳ「０１１１」が入力される（ステップＳ２）。演算回路６１〜６４の全加算器７３において、シフト演算値ＴＥＳ−１「００００」と被加算値ＭＳ「０１１１」が加算されて出力される。加算結果「０１１１」は、１クロック目が立ち上がるタイミングで演算回路６１〜６４のＤフリップフロップ回路７４にそれぞれ入力され、１クロック目が立ち下がるまで保持される（ステップＳ３）。
【０１９７】
１クロック目が立ち下がると、演算回路６１〜６４のＡＮＤ回路７７から、乗数ビット”１”と絶対値差ＡＤＳ「０１１１」の論理積を示す被加算値ＭＳ「０１１１」が各マルチプレクサ７２に入力され、各マルチプレクサ７２から全加算器７３に被加算値ＭＳ「０１１１」が入力される（ステップＳ４）。また、ステップＳ３において、演算回路６１〜６４のＤフリップフロップ回路７４に保持されている加算結果「０１１１」は、シフト演算値ＴＥＳとして、演算回路６２〜６４のマルチプレクサ７１と、シフトレジスタ６５のフリップフロップ回路６５ａとに出力される（ステップＳ５）。
【０１９８】
１クロック目の立ち下がりから２クロック目が立ち上がるまで、演算回路６１〜６４の全加算器７３において、被加算値ＭＳ「０１１１」とシフト演算値ＴＥＳ−１「０１１１」とが加算されて出力される。加算結果「１０１０」は、２クロック目が立ち上がるタイミングで、演算回路６１〜６４のＤフリップフロップ回路７４に入力され、２クロック目が立ち下がるまで保持される。また、シフトレジスタ６５のフリップフロップ回路６５ａに入力されたシフト演算値ＴＥ４「１」は、２クロック目が立ち下がるまで保持される（ステップＳ６）。
【０１９９】
２クロック目が立ち下がると、演算回路６１〜６４のＡＮＤ回路７７から、乗数ビット”１”と絶対値差「０１１１」の論理積を示す被加算値ＭＳ「０１１１」が各マルチプレクサ７２に入力され、各マルチプレクサ７２から各全加算器７３に被加算値ＭＳ「０１１１」が入力される（ステップＳ７）。
【０２００】
また、２クロック目が立ち下がると、ステップＳ６において、演算回路６１〜６４のＤフリップフロップ回路７４に保持されている加算結果「１０１０」は、シフト演算値ＴＥＳとして、演算回路６２〜６４のマルチプレクサ７１とフリップフロップ回路６５ａに出力される。演算回路６１〜６４のマルチプレクサ７１は、シフト演算値ＴＥ０，ＴＥ１，ＴＥ２，ＴＥ３として「０，１，０，１」を全加算器７３に入力する。フリップフロップ回路６５ａは、保持しているシフト演算値ＴＥ４「１」をシフト演算値ＴＥ５（＝ＤＯＵＴ５）としてフリップフロップ回路６５ｂに出力し、演算回路６４から出力されたシフト演算値ＴＥ４「０」を入力する（ステップＳ８）。
【０２０１】
２クロック目の立ち下がりから３クロック目が立ち上がるまで、演算回路６１〜６４の全加算器７３において、被加算値ＭＳ「０１１１」とシフト演算値ＴＥＳ−１「０１０１」とが加算されて出力される。加算結果「１１００」は、３クロック目が立ち上がるタイミングで演算回路６１〜６４のＤフリップフロップ回路７４に入力され、３クロック目が立ち下がるまで保持される。また、フリップフロップ回路６５ａにおいて、演算回路６４からのシフト演算値ＴＥ４「０」は、３クロック目が立ち下がるまで保持される。フリップフロップ回路６５ｂにおいて、フリップフロップ回路６５ａからのシフト演算値ＴＥ５「１」は３クロック目が立ち下がるまで保持される（ステップＳ９）。
【０２０２】
３クロック目が立ち下がると、演算回路６１〜６４のＡＮＤ回路７７から、乗数ビット”０”と絶対値差「０１１１」の論理積を示す被加算値ＭＳ「００００」が各マルチプレクサ７２に入力され、各マルチプレクサ７２から全加算器７３に被加算値ＭＳ「００００」が入力される（ステップＳ１０）。
【０２０３】
また、ステップＳ９において、演算回路６１〜６４のＤフリップフロップ回路７４に保持されている加算結果「１１００」は、３クロック目が立ち下がると、シフト演算値ＴＥＳとして、演算回路６２〜６４のマルチプレクサ７１とフリップフロップ回路６５ａに出力される。演算回路６１〜６４のマルチプレクサ７１は、シフト演算値ＴＥ０，ＴＥ１，ＴＥ２，ＴＥ３として「０，１，１，０」を全加算器７３に入力する。フリップフロップ回路６５ａは、保持しているシフト演算値ＴＥ４「０」をシフト演算値ＴＥ５として出力し、演算回路６４から出力されたシフト演算値ＴＥ４「０」を入力する。フリップフロップ回路６５ｂは、保持しているシフト演算値ＴＥ５「１」をシフト演算値ＴＥ６（＝ＤＯＵＴ６）として出力し、フリップフロップ回路６５ａから出力されたシフト演算値ＴＥ５「０」を入力する。フリップフロップ回路６５ｃは、フリップフロップ回路６５ｂから出力されたシフト演算値ＴＥ６「１」を入力する（ステップＳ１１）。
【０２０４】
３クロック目が立ち下がっている間、乗数ビットシフト回路６６から乗数ビットＭＢ”０”が各演算回路６１〜６４に出力されると、二乗計算の終了を示す信号が制御回路（図示せず）に出力される。３クロック目の立ち下がりから４クロック目が立ち上がるまで、演算回路６１〜６４の全加算器７３において、被加算値ＭＳ「００００」とシフト演算値ＴＥＳ−１「０１１０」とが加算されて出力される。４クロック目が立ち上がると、加算結果「０１１０」は、それぞれシフト演算値ＴＥ１，ＴＥ２，ＴＥ３，ＴＥ４として、Ｄフリップフロップ回路７４に出力される（ステップＳ１２）。シフトレジスタ６５には、ステップＳ１１において入力されたシフト演算値ＴＥ４，ＴＥ５，ＴＥ６の各値（０，０，１）が、シフト演算値ＴＥ５，ＴＥ６，ＴＥ７として保持される。
【０２０５】
４クロック目が立ち下がると、演算回路６１〜６４において、それぞれのＤフリップフロップ回路７４に保持されているシフト演算値ＴＥ１，ＴＥ２，ＴＥ３，ＴＥ４は、それぞれのマルチプレクサ７８に出力され、ＤＯＵＴ０＝０，ＤＯＵＴ１＝０、ＤＯＵＴ２＝１、ＤＯＵＴ３＝１、ＤＯＵＴ４＝０として距離／クロック数変換回路ＤＣｉに出力される。また、シフトレジスタ６５において、フリップフロップ回路６５ａ〜６５ｃに保持されているシフト演算値ＴＥ５「０」，ＴＥ６「０」，ＴＥ７「１」についても、４クロック目が立ち下がると、それぞれ、ＤＯＵＴ５＝０、ＤＯＵＴ６＝０、ＤＯＵＴ７＝１として、距離／クロック数変換回路ＤＣｉに出力される。つまり、ＤＯＵＴ０〜ＤＯＵＴ７は、絶対値差（＝７１０）の二乗値（＝４９１０）を示す距離信号Ｄｉｊとして距離／クロック数変換回路ＤＣｉに出力される。
【０２０６】
距離／クロック数変換回路ＤＣｉは、距離演算回路ＤＰｉｊから出力される絶対値差の二乗値をクロック数に変換する。図１４は、図２Ａに示す距離／クロック数変換回路ＤＣ１におけるカウンタ一致検出回路３１の概略構成を示す図である。図１４に示すように、カウンタ一致検出回路３１は、カウンタ３１１と一致検出回路３１２１とを含む。
【０２０７】
カウンタ３１１は、バッファ２１からクロック信号ＣＬＫを受け、連想メモリ１００の制御回路（図示せず）からリセット信号ＲＳＴを受ける。カウンタ３１１は、リセット信号ＲＳＴを受けると、カウンタ値をリセットし、Ｍビットのビット値をクロック信号ＣＬＫに同期して昇順にカウントアップする。カウンタ３１１は、そのカウンタ値ＣＶ１１をクロック信号ＣＬＫに同期して一致検出回路３１２１へ順次出力する。
【０２０８】
一致検出回路３１２１は、バッファ２１からクロック信号ＣＬＫを受け、制御回路（図示せず）から検索開始信号ＳＢを受ける。また、一致検出回路３１２１は、カウンタ３１１からカウンタ値ＣＶ１１を受け、距離演算回路ＤＰ１１から距離信号Ｄ１１を受ける。一致検出回路３１２１は、検索開始信号ＳＢが立ち上がると、距離信号Ｄ１１に一致するカウンタ値ＣＶ１１が得られるときのクロック信号ＣＬＫのクロック数をカウントする。そして、一致検出回路３１２１は、そのクロック数をカウントしたタイミングを示す一致信号ＭＴＨ１をカウンタ一致検出回路３２へ出力する。一致検出回路３１２１は、一致信号ＭＴＨ１を出力すると動作を停止する。
【０２０９】
なお、図２Ａに示すカウンタ一致検出回路３２〜３Ｗの各々についても、図１４に示すカウンタ一致検出回路３１と同様の構成を有する。カウンタ一致検出回路３２〜３Ｗは、それぞれ、カウンタ一致検出回路３１〜３Ｗ−１の一致検出回路３１２１から一致信号ＭＴＨ１〜ＭＴＨＷ−１を受けるまで動作を停止し、一致信号ＭＴＨ１〜ＭＴＨＷ−１を受けると駆動して動作を開始する。
【０２１０】
カウンタ一致検出回路３Ｗから一致信号ＭＴＨＷが出力されるタイミングで、距離／クロック数変換回路ＤＣｉに対するタイミング信号ＣｉがＷｉｎｎｅｒ検出器２０へ出力される。つまり、タイミング信号Ｃｉは、距離／クロック数変換回路ＤＣｉに入力される距離信号Ｄｉ１〜ＤｉＷが示す各絶対値差の二乗値の和、すなわち、ユークリッド距離値の和に相当するクロック数が得られるタイミングで出力される。
【０２１１】
上記の例では、ユークリッド距離を用いて検索を行う例を説明したが、図１２に示す演算回路６１〜６４のマルチプレクサ７８に、マンハッタン距離を示す制御信号（ＭＤ）が制御回路（図示せず）から入力される場合には、各マルチプレクサ７８から、検索データと参照データの絶対値差（ＡＤ１〜ＡＤ４）で表される距離信号Ｄｉｊが出力される。その場合も、ユークリッド距離と同様、距離／クロック数変換回路ＤＣｉにおいて、距離信号Ｄｉｊに一致するカウンタ値ＣＶｉｊが得られるときのクロック信号ＣＬＫのクロック数をカウントすればよい。
【０２１２】
上述した第４実施形態では、距離演算回路において、検索データと参照データとの絶対値差の演算を行うとともに、絶対値差の二乗演算を行うことができる。そのため、絶対値差の演算と絶対値差の二乗演算とを別個の回路によって実現する場合等と比べて回路面積を小さくすることができる。また、マンハッタン距離とユークリッド距離のいずれを用いた検索にも適用することができる。
【０２１３】
＜変形例＞
【０２１４】
（１）上述した第１実施形態では、ユークリッド距離を用いた検索を行う例について説明したが、マンハッタン距離とユークリッド距離のいずれを用いても検索されるように構成してもよい。図１５は、本変形例におけるカウンタ一致検出回路の構成例を示す概略図である。カウンタ一致検出回路３１は、デマルチプレクサ３１ｘを有し、カウンタ一致検出回路３２は、デマルチプレクサ３２ｘを有する。
【０２１５】
デマルチプレクサ３１ｘ，３２ｘには、マンハッタン距離かユークリッド距離かを示す制御信号ＳＬが制御回路（図示せず）から入力される。クロック数変換回路３１ａにおいて、距離信号Ｄ１１とクロック数とが一致すると、デマルチプレクサ３１ｘにＨレベルの一致検出信号を出力する。デマルチプレクサ３１ｘは、入力された制御信号がマンハッタン距離を示す場合には、クロック数変換回路３１ａから出力される一致検出信号をバッファ２２とクロック数変換回路３１ａに出力して動作を停止する。
【０２１６】
カウンタ一致検出回路３１から一致検出信号が出力されると、バッファ２２からクロック数変換回路３２ａにクロック信号ＣＬＫが入力される。クロック数変換回路３２ａにおいて、距離信号Ｄ１２とクロック数とが一致すると、デマルチプレクサ３２ｘにＨレベルの一致検出信号を出力する。デマルチプレクサ３２ｘは、入力された制御信号がマンハッタン距離を示す場合には、クロック数変換回路３２ａからのＨレベルの一致検出信号が入力されたタイミングでＷｉｎｎｅｒ検出器２０にタイミング信号Ｃ１を出力して動作を停止する。
【０２１７】
なお、ユークリッド距離を示す制御信号がデマルチプレクサ３１ｘ，３２ｘに入力された場合には、マルチプレクサ３１ｘ，３２ｘは、クロック数変換回路３１ａ，３２ａからのＨレベルの一致検出信号をカウンタ３１ｂ，３２ｂにそれぞれ出力し、上述した第１実施形態と同様、カウンタ３１ｂ，３２ｂのカウンタ値と距離信号Ｄ１１，Ｄ１２とが一致するまで動作を繰り返す。
【０２１８】
（２）上述した第３実施形態では、距離とカウンタ値との一致検出の際、最上位ビットから下位方向に１ビットずつ対象ビットを拡張する例について説明したが、複数ビット単位に対象ビットを拡張するようにしてもよい。また、対象ビットを拡張するごとに、拡張するビットの数が異なっていてもよい。例えば、距離とカウンタ値とが６ビット長である場合において、最上位のビットについて一致の検索を行い、いずれかの参照データについての一致検出信号が立ち上がると、２番目と３番目の２つのビットを対象ビットとし、上位３ビットまで拡張する。そして、いずれかの参照データについて、上位３ビットに対する一致検出信号が立ち上がると、４番目〜６番目の３つのビットを次の検索対象のビットとし、全ビットに対象ビットを拡張する。
【産業上の利用可能性】
【０２１９】
この発明は、連想メモリに適用される。
【符号の説明】
【０２２０】
１…メモリ部、２…行デコーダ、３…列デコーダ、４…読出／書込回路、５…検索データ保存回路、６，７７，６４ａ，３００ｃ，３１３ｄ，３１３ｅ…ＡＮＤ回路、１０…メモリアレイ部、２０…Ｗｉｎｎｅｒ検出器、２１〜２Ｗ…バッファ，３１〜３Ｗ，…カウンタ一致検出回路、３１ａ，３２ａ…クロック数変換回路、３１ｂ，３２ｂ，３００ｂ，３１１，３１２…カウンタ、３１ｃ，３１ｃ’，３２ｃ，３２ｃ’，３１３，３１２１…一致検出回路、４０…有効ビット設定部、６１〜６４…演算回路、６５…シフトレジスタ、６５ａ，６５ｂ，６５ｃ…フリップフロップ回路、６６…乗数ビットシフト回路、７１，７２，７８，３１ｄ，３２ｄ，３００ａ，３１４…マルチプレクサ、７３…全加算器、７４…Ｄフリップフロップ回路、７５…反転制御回路、７６…ラッチ回路、３００…カウンタ一致検出ユニット、３１０，３２０…距離／クロック数変換ユニット、３１２ａ〜３１２ｃ…セレクタ、３１２ｄ〜３１２ｆ…分周器、３１３ａ〜３１３ｃ…ＥＸＮＯＲ回路、ＤＣ１〜ＤＣＲ，ＤＥ１〜ＤＥＲ…距離／クロック数変換回路、ＤＥ１１〜ＤＥ１Ｗ…カウンタ一致検出回路、ＤＰ１１〜ＤＰＲＷ…距離演算回路
【図１】
2014154196.tif 000005
【図２Ａ】
2014154196.tif 000006
【図２Ｂ】
2014154196.tif 000007
【図３】
2014154196.tif 000008
【図４】
2014154196.tif 000009
【図５Ａ】
2014154196.tif 000010
【図５Ｂ】
2014154196.tif 000011
【図６】
2014154196.tif 000012
【図７】
2014154196.tif 000013
【図８】
2014154196.tif 000014
【図９Ａ】
2014154196.tif 000015
【図９Ｂ】
2014154196.tif 000016
【図１０Ａ】
2014154196.tif 000017
【図１０Ｂ】
2014154196.tif 000018
【図１０Ｃ】
2014154196.tif 000019
【図１０Ｄ】
2014154196.tif 000020
【図１１】
2014154196.tif 000021
【図１２】
2014154196.tif 000022
【図１３】
2014154196.tif 000023
【図１４】
2014154196.tif 000024
【図１５】
2014154196.tif 000025