(57)【特許請求の範囲】
【請求項１】
それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離／クロック数変換回路とを有する、複数のエレメント回路と、
前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路と、
ｋ近傍法に従って前記検索データのクラスを判定するｋ近傍クラスタリング回路とを備え、
前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する複数の参照データ検索回路からなる再構成可能なクロックカウント式連想メモリが構成され、
前記ｋ近傍クラスタリング回路は、前記再構成可能なクロックカウント式連想メモリから出力される複数のマッチ信号のうちいずれかｋ個のマッチ信号がアクティブになるまでの間、前記複数のマッチ信号の少なくとも一つがアクティブになるごとに、前記複数の参照データ検索回路のそれぞれが保存する参照データのクラスを表す複数のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でｋ個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するように構成されている
ことを特徴とする再構成可能なｋ近傍法連想メモリ。
【請求項２】
前記ｋ近傍クラスタリング回路が、
前記複数のクラスデータを保持するクラスデータメモリと、
Ｘ個のクラスのそれぞれに対応するＸ個のクラスカウンタと、
前記アクティブになった少なくとも一つのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップし、前記アクティブになった少なくとも一つのマッチ信号をすべて選択し終わると終了信号を出力するクラス識別回路と、
前記Ｘ個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路と、
前記クラス識別回路がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がｋに一致したことを検出するｋ−マッチ信号数一致検出回路とを有するものであり、
前記再構成可能なｋ近傍法連想メモリが、前記複数のマッチ信号の少なくとも一つがアクティブになると前記再構成可能なクロックカウント式連想メモリの動作を停止させて前記クラス識別回路を動作させ、前記クラス識別回路から前記終了信号が出力されると前記クラス識別回路の動作を停止させて前記再構成可能なクロックカウント式連想メモリを動作させる制御回路を備え、
前記再構成可能なクロックカウント式連想メモリが、前記ｋ−マッチ信号数一致検出回路によって前記カウント値がｋに一致したことが検出されたとき、動作を停止するように構成されている、請求項１に記載の再構成可能なｋ近傍法連想メモリ。
【請求項３】
前記制御回路が、
前記複数のスイッチ回路のそれぞれに対応して設けられ、対応するスイッチ回路が前記回路構成信号に応じて選択的に出力する前段のエレメント回路のマッチ信号がアクティブになってから前記クラス識別回路から前記終了信号が出力されるまでの間だけアクティブになる検出信号を出力する複数のマッチ信号アクティブ検出回路と、
前記複数のマッチ信号アクティブ検知回路から出力される複数の検出信号の論理和を演算するＯＲゲートとを有し、
前記ＯＲゲートの出力信号で前記クラス識別回路および前記再構成可能なクロックカウント式連想メモリの動作を制御する、請求項２に記載の再構成可能なｋ近傍法連想メモリ。
【請求項４】
前記クラス識別回路が、前記複数のスイッチ回路のそれぞれに対応して設けられ、対応するスイッチ回路が前記回路構成信号に応じて選択的に出力する前段のエレメント回路のマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力する複数のマッチ信号検出回路を有し、
前記複数のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、
前記複数のマッチ信号検出回路のそれぞれが、前記対応するスイッチ回路から出力されるマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するスイッチ回路から出力されるマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項２および３いずれか一つに記載の再構成可能なｋ近傍法連想メモリ。
【請求項５】
前記最大カウンタ検出回路が、
初期値からカウント値をカウントダウンするダウンカウンタと、
前記Ｘ個のクラスカウンタのそれぞれに対応して設けられ、対応するクラスカウンタのカウント値と前記ダウンカウンタのカウント値との一致を検出するＸ個の一致検出回路とを有し、
前記ダウンカウンタのカウント値がカウントダウンされている間に、前記Ｘ個の一致検出回路のうちのいずれか一つによって前記ダウンカウンタのカウント値と対応するクラスカウンタのカウント値との一致が検出されたとき、前記ダウンカウンタのカウント動作を停止させる、請求項２ないし４のいずれか一つに記載の再構成可能なｋ近傍法連想メモリ。
【請求項６】
前記最大カウンタ検出回路が、２入力１出力の複数の最大値選出回路がツリー状に接続されてなり、リーフノードの複数の最大値選出回路に前記Ｘ個のクラスカウンタの各カウント値および各クラスカウンタの識別番号を結合した各信号が入力され、ルートノードの最大値選出回路から前記Ｘ個のクラスカウンタの最大カウント値およびそのクラスカウンタの識別番号を結合した信号を出力するトーナメント回路であり、
前記最大値選出回路が、第１のクラスカウンタのカウント値および前記第１のクラスカウンタの識別番号を結合した第１の信号、および第２のクラスカウンタのカウント値および前記第２のクラスカウンタの識別番号を結合した第２の信号を受け、前記第１および第２のクラスカウンタのうちカウント値が大きい方のクラスカウンタのカウント値およびそのクラスカウンタの識別番号を結合した第３の信号を出力する、請求項２ないし４のいずれか一つに記載の再構成可能なｋ近傍法連想メモリ。
【請求項７】
回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えている
ことを特徴とする請求項１ないし請求項３のいずれかに記載の再構成可能なｋ近傍法連想メモリ。
【請求項８】
前記回路構成情報記憶回路が不揮発性メモリで構成されている
ことを特徴とする請求項７に記載の再構成可能なｋ近傍法連想メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連想メモリに関し、特に、ｋ近傍法を効果的に実現する連想メモリに保存される参照データの次元数および個数を拡縮する技術に関する。
【背景技術】
【０００２】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをＬＳＩ（Large Scale Integrated Circuit）上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【０００３】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【０００４】
前者は、ＣＡＭ（Content Addressable Memory）と呼ばれ、ネットワークルータのＩＰアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ（Associative Memory）と呼ぶ。
【０００５】
連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている（非特許文献１参照）。また、連想メモリにｋ近傍探索を取り入れたものが知られている（非特許文献２参照）。
【０００６】
また、本願発明者は、検索に係るクロックカウント数を削減する機構（有効ビット設定部）とユークリッド距離検索のための二乗計算回路（距離演算回路）とを備えたクロックカウント式の連想メモリを発明している（特許文献１参照）。当該発明によれば、データ規模が増大しても高速な検索が可能なユークリッド／マンハッタン距離検索連想メモリをエラーフリー、高電力効率に実現することができる。
【０００７】
一方、パターン認識の分野において機械学習アルゴリズムとしてｋ近傍法がよく用いられる。本願発明者は、連想メモリを用いてｋ近傍法を効果的に実現することができるｋ近傍法連想メモリを発明している（特許文献２参照）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１４−１５４１９６号公報
【特許文献２】国際公開第２０１５／０１１９０７号
【非特許文献】
【０００９】
【非特許文献１】S.Sasaki et al., "Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization," ESSCIRC'2012, 2012, pp.185-188
【非特許文献２】M.A.Abedin et al., "Realization of K-Nearest-Matches Search Capability in Fully-Parallel Associative Memories," IEICE Trans. on Fundamentals, vol. E90-A, No.6, 2007, pp.1240-1243
【発明の概要】
【発明が解決しようとする課題】
【００１０】
連想メモリが利用される分野として、コードブックベース画像圧縮のデータ検索やＢｏＷ（Bag of Words）などが挙げられる。前者では比較的少ない次元数の大量の参照データの検索が行われ、後者では膨大な次元数の少量の参照データの検索が行われる。しかし、従来の連想メモリでは回路構成が固定されているため、アプリケーションに応じて参照データの次元数および個数を拡縮することが困難である。
【００１１】
この問題に関して、本願発明者は、参照データの次元数および個数の拡縮が可能な連想メモリを発明し、特願２０１４−３６６９８（以下、先願という）に当該発明を開示した。
【００１２】
一方、先行文献２に開示されたｋ近傍法連想メモリでは参照データの次元数および個数が固定されているが、ｋ近傍法連想メモリについても先願の連想メモリと同様に参照データの次元数および個数の拡縮を可能にすることが求められる。
【００１３】
上記問題に鑑み、本発明は、参照データの次元数および個数の拡縮が可能なｋ近傍法連想メモリを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一局面に従った再構成可能なｋ近傍法連想メモリは、それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離／クロック数変換回路とを有する、複数のエレメント回路と、前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路と、ｋ近傍法に従って前記検索データのクラスを判定するｋ近傍クラスタリング回路とを備え、前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する複数の参照データ検索回路からなる再構成可能なクロックカウント式連想メモリが構成され、前記ｋ近傍クラスタリング回路は、前記再構成可能なクロックカウント式連想メモリから出力される複数のマッチ信号のうちいずれかｋ個のマッチ信号がアクティブになるまでの間、前記複数のマッチ信号の少なくとも一つがアクティブになるごとに、前記複数の参照データ検索回路のそれぞれが保存する参照データのクラスを表す複数のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でｋ個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するように構成されているものである。
【００１５】
これによると、再構成可能なクロックカウント式連想メモリによって検索データと各参照データとの距離がクロック数に変換されて、距離に応じたタイミングで各参照データに対応するマッチ信号がアクティブとなり、ｋ近傍クラスタリング回路によって、より先にアクティブになったｋ個のマッチ信号に対応するｋ個のクラスデータをクラス別に分類した場合にデータ数が最大となるクラスが判定される。このようにして、ｋ近傍法に基づいた検索データのクラス分けが実現される。また、複数のスイッチ回路のそれぞれを適宜制御することにより、エレメント回路の接続形態を任意に変更して、任意の次元数の参照データを保存する任意の個数の参照データ検索回路を構成することができる。
【発明の効果】
【００１６】
本発明によると、ｋ近傍法連想メモリにおいて参照データの次元数および個数を拡縮することができる。これにより、アプリケーションに応じてｋ近傍法連想メモリを最適に再構成して、ｋ近傍法連想メモリに割り当てられたリソースを最大限利用することができる。
【図面の簡単な説明】
【００１７】
【図１】一例に係るクロックカウント式連想メモリの概略構成図
【図２】一例に係る距離／クロック数変換回路の概略構成図
【図３】一例に係るカウンタ一致検出回路の概略構成図
【図４】一例に係るマッチ信号のタイミングチャート
【図５】再構成可能なクロックカウント式連想メモリのある再構成例を示す図
【図６】再構成可能なクロックカウント式連想メモリの別の再構成例を示す図
【図７】再構成可能なクロックカウント式連想メモリのさらに別の再構成例を示す図
【図８】本発明の一実施形態に係る再構成可能なｋ近傍法連想メモリの概略構成図
【図９】一例に係る再構成可能なクロックカウント式連想メモリの概略構成図
【図１０】一例に係るスイッチ回路の回路構成図
【図１１】別例に係るスイッチ回路の回路構成図
【図１２】一例に係る制御回路の概略構成図
【図１３】一例に係るクラスデータメモリ、クラスカウンタ、クラス識別回路、およびｋ−マッチ信号数一致検出回路の概略構成図
【図１４】一例に係るマッチ信号検出回路の概略構成図
【図１５】一例に係る最大カウンタ検出回路の概略構成図
【図１６】別例に係る最大カウンタ検出回路の概略構成図
【図１７】一例に係る最大値選出回路の概略構成図
【発明を実施するための形態】
【００１８】
以下、図面を参照しながら本発明を実施するための形態について説明する。なお、本発明は、以下の実施形態に限定されるものではない。
【００１９】
≪クロックカウント式連想メモリの基本構成例≫
まず、本発明に係る再構成可能なｋ近傍法連想メモリの前提となるクロックカウント式連想メモリの基本構成について説明する。
【００２０】
図１は、一例に係るクロックカウント式連想メモリの概略構成を示す。一例に係るクロックカウント式連想メモリ１０’は、メモリ部１１、行デコーダ１２、列デコーダ１３、読出／書込回路１４、および検索データ保存回路１５を含む。
【００２１】
メモリ部１１は、参照データ保存回路（Storage Cell：ＳＣ）ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，…，ＳＣＲ１〜ＳＣＲＷと、距離演算回路（絶対値差演算回路）（Distance Processor：ＤＰ）ＤＰ１１〜ＤＰ１Ｗ，ＤＰ２１〜ＤＰ２Ｗ，…，ＤＰＲ１〜ＤＰＲＷと、距離／クロック数変換回路ＤＣ１〜ＤＣＲとを含む。なお、ＷおよびＲは、それぞれ、２以上の整数である。
【００２２】
距離演算回路ＤＰ１１〜ＤＰ１Ｗは、それぞれ、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗに対応して設けられる。また、距離演算回路ＤＰ２１〜ＤＰ２Ｗは、それぞれ、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗに対応して設けられる。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、それぞれ、参照データ保存回路ＳＣＲ１〜ＳＣＲＷに対応して設けられる。
【００２３】
距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１〜ＤＰ１Ｗに対応して設けられる。距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１〜ＤＰ２Ｗに対応して設けられる。以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１〜ＤＰＲＷに対応して設けられる。
【００２４】
参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，…，ＳＣＲ１〜ＳＣＲＷは、行デコーダ１２、列デコーダ１３、および読出／書込回路１４によって書き込まれた参照データを保存する。この場合、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗは、Ｍ×Ｗ（Ｍは１以上の整数）ビットの参照データ１を保存し、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗは、Ｍ×Ｗビットの参照データ２を保存し、以下、同様にして、参照データ保存回路ＳＣＲ１〜ＳＣＲＷは、Ｍ×Ｗビットの参照データＲを保存する。つまり、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，…，ＳＣＲ１〜ＳＣＲＷのそれぞれは、参照データのＭ×Ｗビットを保存する。
【００２５】
距離演算回路ＤＰ１１〜ＤＰ１Ｗは、参照データ保存回路ＳＣ１１〜ＳＣ１Ｗに保存されたＭ×Ｗビットの参照データ１と、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。また、距離演算回路ＤＰ２１〜ＤＰ２Ｗは、参照データ保存回路ＳＣ２１〜ＳＣ２Ｗに保存されたＭ×Ｗビットの参照データ２と、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、参照データ保存回路ＳＣＲ１〜ＳＣＲＷに保存されたＭ×Ｗビットの参照データＲと、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。そして、距離演算回路ＤＰ１１〜ＤＰ１Ｗ、距離演算回路ＤＰ２１〜ＤＰ２Ｗ、…、距離演算回路ＤＰＲ１〜ＤＰＲＷにおける参照データと検索データとの距離の演算は、並列に行われる。
【００２６】
そして、距離演算回路ＤＰ１１〜ＤＰ１Ｗは、参照データ１と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ１へ出力する。距離演算回路ＤＰ２１〜ＤＰ２Ｗは、参照データ２と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ２へ出力する。以下、同様にして、距離演算回路ＤＰＲ１〜ＤＰＲＷは、参照データＲと検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣＲへ出力する。
【００２７】
距離演算回路ＤＰ１１〜ＤＰ１Ｗのそれぞれは、参照データ１と検索データとの距離を次式を用いて演算する。
【００２８】
【数１】
0006411914.tif 000002
【００２９】
式（１）において、Ｄｒｊ（ｒ＝１〜Ｒ，ｊ＝１〜Ｗ）は、参照データと検索データとの距離（絶対値差）を表す。ｎＭｒは、参照データと検索データとのマンハッタン距離を示している。また、式(１)において、Ｉｎｊは、検索データであり、Ｒｅｒｊは、参照データである。各データＩｎｊ、Ｒｅｒｊは、それぞれ、Ｍビットからなる。
【００３０】
このように、距離演算回路ＤＰ１１〜ＤＰ１Ｗは、Ｍ×Ｗビットの参照データ１と、Ｍ×Ｗビットの検索データとの距離をＭビットずつ演算し、それぞれがＭビットのビット長を有するＷ個の距離信号Ｄ１ｊを距離／クロック数変換回路ＤＣ１へ出力する。
【００３１】
距離演算回路ＤＰ２１〜ＤＰ２Ｗ、…および距離演算回路ＤＰＲ１〜ＤＰＲＷも、同様にして、それぞれ、式（１）を用いて参照データ２〜Ｒと検索データとの距離を演算する。そして、距離演算回路ＤＰ２１〜ＤＰ２Ｗ、…および距離演算回路ＤＰＲ１〜ＤＰＲＷも、それぞれがＭビットのビット長を有するＷ個の距離信号Ｄ２ｊ〜ＤＲｊをそれぞれ距離／クロック数変換回路ＤＣ２〜ＤＣＲへ出力する。
【００３２】
距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１〜ＤＰ１ＷからＷ個の距離信号Ｄ１ｊを受け、各距離信号Ｄ１ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ１を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ１をカウントしたタイミングを示すマッチ信号Ｍ１を出力する。
【００３３】
距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１〜ＤＰ２ＷからＷ個の距離信号Ｄ２ｊを受け、各距離信号Ｄ２ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ２を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ２をカウントしたタイミングを示すマッチ信号Ｍ２を出力する。
【００３４】
以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１〜ＤＰＲＷからＷ個の距離信号ＤＲｊを受け、各距離信号ＤＲｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌＲを後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌＲをカウントしたタイミングを示すマッチ信号ＭＲを出力する。
【００３５】
行デコーダ１２は、メモリ部１１の行方向のアドレスを指定する。列デコーダ１３は、メモリ部１１の列方向のアドレスを指定する。読出／書込回路１４は、参照データを行デコーダ１２および列デコーダ１３によって指定された参照データ保存回路ＳＣ１１〜ＳＣ１Ｗ，ＳＣ２１〜ＳＣ２Ｗ，…，ＳＣＲ１〜ＳＣＲＷに書き込むとともに、検索データを検索データ保存回路１５に書き込む。
【００３６】
検索データ保存回路１５は、読出／書込回路１４によって書き込まれた検索データ（Ｍ×Ｗビットのデータ）を保存する。
【００３７】
図２は、一例に係る距離／クロック数変換回路ＤＣ１の概略構成を示す。なお、距離／クロック数変換回路ＤＣ２〜ＤＣＲのそれぞれも、図２に示す距離／クロック数変換回路ＤＣ１と同様の構成を有する。距離／クロック数変換回路ＤＣ１は、バッファ１２１〜１２Ｗと、カウンタ一致検出回路１３１〜１３Ｗとを含む。
【００３８】
バッファ１２１は、クロックカウント式連想メモリの制御回路（図示せず）から検索開始信号ＳＢを受け、クロックカウント式連想メモリに内蔵されたクロック発生回路（図示せず）からクロック信号ＣＬＫを受ける。そして、バッファ１２１は、検索開始信号ＳＢがＬレベルからＨレベルに遷移すると、その受けたクロック信号ＣＬＫをバッファ１２２およびカウンタ一致検出回路１３１へ出力する。バッファ１２２は、クロック信号ＣＬＫをバッファ１２１から受け、カウンタ一致検出回路１３１から、後述するＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けると、クロック信号ＣＬＫをバッファ１２３（図示せず）およびカウンタ一致検出回路１３２へ出力する。以下、同様にして、バッファ１２Ｗは、クロック信号ＣＬＫをバッファ１２Ｗ−１（図示せず）から受け、カウンタ一致検出回路１３Ｗ−１（図示せず）から、後述するＨレベルの一致信号（ＤＥＴＥＣＴＷ−１）を受けると、クロック信号ＣＬＫをカウンタ一致検出回路１３Ｗへ出力する。
【００３９】
カウンタ一致検出回路１３１〜１３Ｗは、それぞれ、距離演算回路ＤＰ１１〜ＤＰ１Ｗに対応して設けられる。そして、カウンタ一致検出回路１３１〜１３Ｗは、直列に接続される。ここで、カウンタ一致検出回路１３１〜１３Ｗの概略構成について説明する。
【００４０】
図３は、一例に係るカウンタ一致検出回路１３１〜１３Ｗの概略構成を示す。本例は、Ｗ＝２の場合を示している。カウンタ一致検出回路１３１は、クロック数変換回路１３１ａと、カウンタ１３１ｂと、一致検出回路１３１ｃとを含む。カウンタ一致検出回路１３２は、クロック数変換回路１３２ａと、カウンタ１３２ｂと、一致検出回路１３２ｃとを含む。以下、各構成の機能について説明する。
【００４１】
クロック数変換回路１３１ａは、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１と、バッファ１２１からのクロック信号ＣＬＫとを受ける。クロック数変換回路１３１ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１１が示す距離と一致するクロック数を検出したタイミングで、カウンタ１３１ｂにＨレベルの一致検出信号を出力する処理を行う。クロック数変換回路１３１ａは、後述の一致検出回路１３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）が出力されるまで、この処理を繰り返し行い、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力されると動作を停止する。
【００４２】
カウンタ１３１ｂは、クロック数変換回路１３１ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路１３１ｃへ出力する。
【００４３】
一致検出回路１３１ｃは、カウンタ１３１ｂからカウンタ値を受け、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１を受ける。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とを比較し、距離信号Ｄ１１が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路１３１ａとバッファ１２２へ出力する。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とが一致しないときは、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路１３１ａとバッファ１２２へ出力する。
【００４４】
クロック数変換回路１３２ａは、バッファ１２２からクロック信号ＣＬＫを受けると駆動する。クロック数変換回路１３２ａは、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。クロック数変換回路１３１ａと同様、クロック数変換回路１３２ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１２が示す距離と一致するクロック数を検出したタイミングで、カウンタ１３２ｂにＨレベルの一致検出信号を出力する処理を行う。クロック数変換回路１３２ａは、後述の一致検出回路１３２ｃからＨレベルの一致信号（ＤＥＴＥＣＴ２）が出力されるまで、この処理を繰り返し行う。クロック数変換回路１３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）が出力されると動作を停止する。
【００４５】
カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路１３２ｃへ出力する。
【００４６】
一致検出回路１３２ｃは、カウンタ１３２ｂからカウンタ値を受け、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。一致検出回路１３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とを比較し、距離信号Ｄ１２が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａとバッファ１２２へ出力するとともに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をマッチ信号Ｍ１として出力する。また、一致検出回路１３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とが一致しないときは、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａに出力する。
【００４７】
ここで、例えば、距離演算回路ＤＰ１１から距離「２」を示すＭビットの距離信号Ｄ１１が出力され、距離演算回路ＤＰ１２から距離「３」を示すＭビットの距離信号Ｄ１２が出力された場合の動作例について説明する。
【００４８】
クロック数変換回路１３１ａは、距離「２」を示すＭビットの距離信号Ｄ１１を受け、バッファ１２１からのクロック信号ＣＬＫのクロックに同期して、距離「２」に一致するクロック数をカウントする。クロック数変換回路１３１ａは、カウントしたクロック数と距離とが一致すると、Ｈレベルの一致検出信号を出力する。カウンタ１３１ｂは、一致検出信号が立ち上がると、カウント値をカウントアップし、「１」を示すカウンタ値を一致検出回路１３１ｃに出力する。このとき、距離信号Ｄ１１が示す距離「２」とカウント値「１」とが一致しないため、一致検出回路１３１ｃからＬレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。
【００４９】
クロック数変換回路１３１ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路１３１ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「２」と一致すると、カウンタ１３１ｂにＨレベルの一致検出信号を出力する。カウンタ１３１ｂは、一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３１ｃに「２」を示すカウンタ値を出力する。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離「２」とカウンタ値「２」とが一致するため、一致信号（ＤＥＴＥＣＴ１）をバッファ１２２とクロック数変換回路１３１ａに出力する。つまり、検索開始からのクロック数が「４」となるタイミングで、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。そして、クロック数変換回路１３１ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）に応じて動作を停止する。
【００５０】
バッファ１２２は、一致検出回路１３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けて、クロック数変換回路１３２ａにクロック信号ＣＬＫを出力する。クロック数変換回路１３２ａは、バッファ１２２からのクロック信号ＣＬＫのクロックに同期して、クロック信号ＣＬＫのクロック数をカウントする。クロック数変換回路１３２ａは、距離「３」を示すＭビットの距離信号Ｄ１２を受け、カウントしたクロック数が距離「３」と一致するタイミングで、Ｈレベルの一致検出信号をカウンタ１３２ｂに出力する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「１」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「１」とが一致しないため、一致検出回路１３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００５１】
クロック数変換回路１３２ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路１３２ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ１３２ｂにＨレベルの一致検出信号を出力する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「２」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「２」とが一致しないため、一致検出回路１３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。
【００５２】
クロック数変換回路１３２ａは、一致検出信号がＬレベルになると、再びカウントしたクロック数をリセットしてクロック信号ＣＬＫをカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ１３２ｂにＨレベルの一致検出信号を出力する。そして、クロック数変換回路１３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）に応じて動作を停止する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「３」を示すカウンタ値を出力する。一致検出回路１３２ｃは、距離「３」とカウント値「３」とが一致するため、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａに出力するとともに、マッチ信号Ｍ１を出力する。つまり、クロック数変換回路１３２ａにおいてカウントされたクロック数は「９（＝３＋３＋３）」であり、検索開始からクロック数「１３（＝４＋９）」のタイミングでマッチ信号Ｍ１が出力される。
【００５３】
カウンタ一致検出回路１３１，１３２全体でカウントされるクロック数ＣＮ＿ｔｏｔａｌ１「１３」は、カウンタ一致検出回路１３１においてカウントするクロック数「４（＝２＋２）」と、カウンタ一致検出回路１３２においてカウントするクロック数「９（＝３＋３＋３）」とを加算したものである。つまり、カウンタ一致検出回路１３１，１３２によって、距離「２」の二乗値と距離「３」の二乗値との和に一致するクロック数をカウントすることに相当する。
【００５４】
距離／クロック数変換回路ＤＣ１は、一般的に、Ｗ個の距離信号Ｄ１１〜Ｄ１Ｗを受ける。そして、Ｗ個の距離信号Ｄ１１〜Ｄ１Ｗのそれぞれは、Ｍビットのビット長を有する。したがって、距離／クロック数変換回路ＤＣ１は、Ｍ×Ｗビットのビット長を有する距離信号Ｄ１１Ｄ１２…Ｄ１Ｗを受ける。カウンタ一致検出回路１３１において、距離信号Ｄ１１が示す距離に一致する回数分だけ、その距離に一致するクロック数を繰り返しカウントする。また、カウンタ一致検出回路１３２〜１３Ｗは、それぞれ、カウンタ一致検出回路１３１〜１３Ｗ−１から一致信号を受けた後に、距離信号Ｄ１２〜Ｄ１Ｗにそれぞれ一致するクロック数を、その距離に一致する回数だけ繰り返しカウントする。その結果、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌ１は、カウンタ一致検出回路１３１〜１３Ｗのそれぞれにおいてカウントされたクロック数の和に等しい。カウンタ一致検出回路１３１〜１３Ｗのそれぞれにおいてカウントされたクロック数は、それぞれ、距離信号Ｄ１１〜Ｄ１Ｗが示す各距離の二乗値に相当するため、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌＲは、各距離信号Ｄ１１〜Ｄ１Ｗの二乗値の和を表している。
【００５５】
ここで、ユークリッド距離ｎＥｒは、次式によって表される。
【００５６】
【数２】
0006411914.tif 000003
【００５７】
式（２）の右辺の｜Ｉｎｊ−Ｒｅｒｊ｜２は、式（１）の右辺の｜Ｉｎｊ−Ｒｅｒｊ｜において、検索データと参照データとの距離の二乗値に一致する。したがって、ユークリッド距離ｎＥｒの演算は、上述したように、式（１）によって演算したＷ個の各距離について、距離に一致するクロック数をカウントする処理を距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図３の例において、カウンタ一致検出回路１３２が、カウンタ一致検出回路１３１，１３２全体でカウントしたクロック数のタイミングを示すマッチ信号Ｍ１を出力することは、ユークリッド距離ｎＥｒによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示す信号を出力することに相当する。なお、距離／クロック数変換回路ＤＣ２〜ＤＣＲのそれぞれも、距離／クロック数変換回路ＤＣ１の動作と同じ動作によって、それぞれ、マッチ信号Ｍ２〜ＭＲを出力する。
【００５８】
図４は、一例に係るマッチ信号のタイミングチャートである。距離／クロック数変換回路ＤＣ１〜ＤＣＲは、図４に示すように、例えばマッチ信号Ｍ１〜ＭＲをそれぞれクロック信号ＣＬＫに同期して出力する。
【００５９】
≪再構成可能なクロックカウント式連想メモリの再構成例≫
次に、本発明に係る再構成可能なｋ近傍法連想メモリの前提となる再構成可能なクロックカウント式連想メモリについて説明する。再構成可能なクロックカウント式連想メモリは、例えば上記構成のクロックカウント式連想メモリ１０’において参照データの次元数および個数を任意に拡縮できるように構成したものである。図５、図６、および図７は、再構成可能なクロックカウント式連想メモリのさまざまな再構成例を示す。
【００６０】
再構成可能なクロックカウント式連想メモリ１０において、複数のエレメント回路７０がＲ行×Ｃ列（ただし、Ｒ，Ｃはいずれも２以上の整数である。）のマトリクス状に配置されている。なお、便宜のため、以下では、再構成可能なクロックカウント式連想メモリ１０において４行×４列の計１６個のエレメント回路７０がマトリクス状に配置されているものとして説明する。また、行デコーダ２、列デコーダ３、読出／書込回路４、検索データ保存回路５などの周辺回路の図示は省略する。
【００６１】
各エレメント回路７０は、１組以上の上記の参照データ保存回路ＳＣおよび距離計算回路ＤＰの対応するペア、ならびにそれら距離計算回路ＤＣから出力される距離信号が入力される上記の距離／クロック数変換回路ＤＣを含む。各エレメント回路７０から出力されるＭＮ（Match Next）信号は、各エレメント回路７０における距離／クロック数変換回路ＤＣから出力されるマッチ信号に相当する。すなわち、各エレメント回路７０は、Ｑ次元（Ｑは２以上の整数）の参照データを保存し、当該Ｑ次元の参照データとＱ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）を出力する。
【００６２】
後述する図示しないスイッチ回路によってエレメント回路７０どうしが任意に接続および切断可能となっている。エレメント回路７０どうしが接続された場合、前段のエレメント回路７０から出力されるＭＮ信号は、次段のエレメント回路７０における距離／クロック数変換回路ＤＣのトリガー信号として次段のエレメント回路７０に供給される。
【００６３】
図５の再構成例では、図示しないスイッチ回路によって４個のエレメント回路７０がカスケード接続されて４個の参照データ検索回路４０が構成されている。図５の再構成例において、４個の参照データ検索回路４０は、それぞれ、４Ｑ（＝４×Ｑ）次元の参照データを保存し、当該４Ｑ次元の参照データと４Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）を出力する。
【００６４】
図６の再構成例では、図示しないスイッチ回路によって２個のエレメント回路７０がカスケード接続されて８個の参照データ検索回路４０が構成されている。図６の再構成例において、８個の参照データ検索回路４０は、それぞれ、２Ｑ（＝２×Ｑ）次元の参照データを保存し、当該２Ｑ次元の参照データと２Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）を出力する。すなわち、図６の再構成例は、図５の再構成例に対して、参照データの次元数を半分にする代わりに個数を倍にしたものである。
【００６５】
図７の再構成例では、図示しないスイッチ回路によって８個のエレメント回路７０がカスケード接続されて２個の参照データ検索回路４０が構成されている。図７の再構成例において、２個の参照データ検索回路４０は、それぞれ、８Ｑ（＝８×Ｑ）次元の参照データを保存し、当該８Ｑ次元の参照データと８Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）を出力する。すなわち、図７の再構成例は、図５の再構成例に対して、参照データの個数を半分にする代わりに次元数を倍にしたものである。
【００６６】
≪再構成可能なｋ近傍法連想メモリの実施形態≫
次に、本発明の一実施形態に係る再構成可能なｋ近傍法連想メモリについて説明する。図８は、本発明の一実施形態に係る再構成可能なｋ近傍法連想メモリ１００の概略構成を示す。本実施形態に係る再構成可能なｋ近傍法連想メモリ１００は、上記の再構成可能なクロックカウント式連想メモリ１０と、制御回路２０と、ｋ近傍クラスタリング回路３０とを備えている。
【００６７】
再構成可能なクロックカウント式連想メモリ１０は、複数の参照データ（例えば、参照データ１，参照データ２，…，参照データＲ）を保持しており、これら複数の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力する回路である。なお、上述したように、再構成可能なクロックカウント式連想メモリ１０は、再構成することで、保持する参照データの個数と次元数を任意に変更することができる。なお、「距離」とはマンハッタン距離、ユークリッド距離などを含む。また、「アクティブ」とは、正論理では信号がＬレベルからＨレベルへと遷移することをいい、負論理では信号がＨレベルからＬレベルへと遷移することをいう。便宜のため、以下では正論理を前提に説明する。
【００６８】
制御回路２０は、再構成可能なクロックカウント式連想メモリ１０およびｋ近傍クラスタリング回路３０の動作を制御する回路である。
【００６９】
ｋ近傍クラスタリング回路３０は、エレメント回路７０の総数（例えば、ｎ個）に等しい複数の参照データのそれぞれのクラスを表す複数のクラスデータ（例えば、クラスデータ１，クラスデータ２，…，クラスデータｎ）から、クロックカウント式連想メモリ１０から出力されるアクティブのｋ個のマッチ信号のそれぞれに対応するｋ個のクラスデータを選択し、これらｋ個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定する回路である。
【００７０】
再構成可能なｋ近傍法連想メモリ１００は、上記３つの回路を備えることで、ｋ近傍法に基づいて、与えられた検索データがいずれのクラスに分類されるかを判定することができる。以下、各回路の構成例について説明する。
【００７１】
≪再構成可能なクロックカウント式連想メモリ１０の構成例≫
図９は、一例に係る再構成可能なクロックカウント式連想メモリ１０の概略構成を示す。各エレメント回路７０に対応してスイッチ回路５０が設けられており、上述したように、スイッチ回路５０によってエレメント回路７０どうしが任意に接続および切断可能となっている。各スイッチ回路５０がエレメント回路７０どうしを接続するか否かは、各スイッチ回路５０に入力される回路構成信号ＳＲによって決まる。
【００７２】
また、各スイッチ回路５０に対応してｋ近傍法（ｋ−ＮＮ）ユニット８０が設けられている。各ｋ−ＮＮユニット８０は、制御回路２０の構成要素であるマッチ信号アクティブ検出回路（不図示）ならびにｋ近傍クラスタリング回路３０の構成要素であるマッチ信号検出回路（不図示）およびクラスデータ保存回路（不図示）を有している。各ｋ−ＮＮユニット８０には対応するスイッチ回路５０が回路構成信号ＳＲに応じて選択的に出力するマッチ信号が入力される。すべてのｋ−ＮＮユニット８０はカスケード接続されており、初段のｋ−ＮＮユニット８０にはマッチ信号アクティブ検出信号ＭＤが入力され、最終段のｋ近傍法ｋ−ＮＮユニット８０から終了信号ｅｎｄが出力される。これら信号については後述する。
【００７３】
各スイッチ回路５０に入力される回路構成信号ＳＲは、メモリ（回路構成情報記憶回路）６０に記憶されている。メモリ６０は、ＳＲＡＭ（Static Random Access Memory）、フラッシュメモリ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）などの不揮発性メモリやシフトレジスタなどで構成することができる。メモリ６０の記憶内容を書き換えるだけで、再構成可能なｋ近傍法連想メモリ１００を任意に再構成することができる。
【００７４】
図１０は、一例に係るスイッチ回路５０の回路構成を示す。スイッチ回路５０は、例えば、二つのマルチプレクサ（ＭＵＸ）５１および５２を備えている。
【００７５】
マルチプレクサ５１は、検索開始信号ＳＢが入力ｉｎ０として、前段のエレメント回路７０から出力されるＭＮ信号（ＭＮｉｎ）が入力ｉｎ１としてそれぞれ与えられ、回路構成信号ＳＲによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。ＭＵＸ５１から出力されるＭＮ信号（ＭＮｏｕｔ）は、次段のエレメント回路７０における距離／クロック数変換回路ＤＣのトリガー信号となる。具体的には、ＭＵＸ５１は、回路構成信号ＳＲがＨレベル（ＳＲ＝１）のとき、ｉｎ１を出力する。この場合、前段のエレメント回路７０における距離／クロック数変換回路ＤＣから出力されるマッチ信号（ＭＮ信号）が次段のエレメント回路７０における距離／クロック数変換回路ＤＣのトリガー信号として供給される。一方、ＭＵＸ５１は、回路構成信号ＳＲがＬレベル（ＳＲ＝０）のとき、ｉｎ０を出力する。この場合、次段のエレメント回路７０における距離／クロック数変換回路ＤＣに検索開始信号ＳＢが供給される。すなわち、この場合の次段のエレメント回路７０は、参照データ検索回路４０における初段のエレメント回路７０に相当する。
【００７６】
ＭＵＸ５２は、前段のエレメント回路７０から出力されるＭＮ信号（ＭＮｉｎ）が入力ｉｎ０として、固定値“０”が入力ｉｎ１としてそれぞれ与えられ、回路構成信号ＳＲによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。ＭＵＸ５２から出力されるマッチ信号Ｍは、対応するｋ−ＮＮユニット８０に入力される。
【００７７】
例えば、回路構成信号ＳＲがＨレベルのとき、ＭＵＸ５２はｉｎ１を出力する。この場合、対応するｋ−ＮＮユニット８０にはマッチ信号Ｍとして固定値“０”が入力される。したがって、当該ｋ−ＮＮユニット８０に入力されるマッチ信号Ｍはアクティブになることはなく、当該ｋ−ＮＮユニット８０に含まれるマッチ信号アクティブ検出回路およびマッチ信号検出回路は動作しない。一方、回路構成信号ＳＲがＬレベルのとき、ＭＵＸ５２はｉｎ０を出力する。回路構成信号ＳＲがＬレベルということは、上述したように、次段のエレメント回路７０が参照データ検索回路４０における初段のエレメント回路７０に相当し、当該スイッチ回路５０に対応するエレメント回路７０は参照データ検索回路４０における最終段のエレメント回路７０に相当する。この場合、対応するｋ−ＮＮユニット８０にはマッチ信号ＭとしてＭＵＸ５１から出力されるＭＮ信号、すなわち、参照データ検索回路４０における最終段のエレメント回路７０における距離／クロック数変換回路ＤＣから出力されるマッチ信号（ＭＮ信号）が入力される。したがって、当該ｋ−ＮＮユニット８０に入力されるマッチ信号Ｍは、参照データ検索回路４０において検索データと参照データとの距離が計算され、その距離に応じたクロック数がカウントされたタイミングでアクティブになり、当該ｋ−ＮＮユニット８０に含まれるマッチ信号アクティブ検出回路およびマッチ信号検出回路は当該マッチ信号Ｍがアクティブになることで所期の動作を行う。この動作については後述する。
【００７８】
図１１は、別例に係るスイッチ回路５０の回路構成を示す。当該構成は、図１０の構成と異なり、ＭＵＸ５２の入力ｉｎ０として、前段のエレメント回路７０から出力されるＭＮ信号（ＭＮｉｎ）ではなくＭＵＸ５１の出力信号が与えられる。なお、このような構成の場合、ＭＵＸ５２には次段のスイッチ回路５０に入力される回路構成信号ＳＲを与える必要がある。このような構成のスイッチ回路５０でも、図１０の構成と同様の動作をすることができる。
【００７９】
≪制御回路２０の構成例≫
図１２は、一例に係る制御回路２０の概略構成を示す。制御回路２０は、複数の（具体的にはエレメント回路７０の総数であり、例えば、ｎ個とする）マッチ信号アクティブ検出回路２１と、ｎ個のマッチ信号アクティブ検出回路２１から出力される検出信号ＭＤ１〜ＭＤｎの論理和を演算してマッチ信号アクティブ検出信号ＭＤを出力するＯＲゲート２２とを含む。なお、上述したように、各マッチ信号アクティブ検出回路２１は各ｋ−ＮＮユニット８０内に配置されている。マッチ信号アクティブ検出回路２１は、対応するマッチ信号Ｍｉ（ｉは１からｎまでの整数）と後述するクラス識別回路３３によるクラス識別動作の終了を表す終了信号ｅｎｄとの論理積を演算するＡＮＤゲート２１１と、Ｈレベル信号がデータ入力（Ｄ）されるとともにＡＮＤゲート２１１の出力信号がクロック入力（ＣＬＫ）されるＤフリップフロップ２１２と、マッチ信号ＭｉとＤフリップフロップの反転出力との論理積を演算して検出信号ＭＤiを出力するＡＮＤゲート２１３とを含む。なお、図示していないが、各Ｄフリップフロップ２１２はリセット信号を受けることで初期状態にリセットされる。
【００８０】
このような回路構成によれば、マッチ信号アクティブ検出回路２１から出力される検出信号ＭＤｉは、マッチ信号Ｍｉがアクティブ（Ｈレベル）になるとアクティブ（Ｈレベル）になり、その後、終了信号ｅｎｄが立ち上がってＤフリップフロップ２１１がデータ入力（Ｄ）を取り込んで反転出力（Ｑバー）がＬレベルに変化することで非アクティブ（Ｌレベル）になる。ここで、Ｄフリップフロップ２１１のデータ入力（Ｄ）はＨレベル信号の固定値であるため、Ｄフリップフロップ２１１が一度データ入力（Ｄ）を取り込んだ後は、Ｄフリップフロップ２１１がリセットされるまで、Ｄフリップフロップ２１１の反転出力（Ｑバー）はＬレベルに維持される。このため、ＡＮＤゲート２１３においてマッチ信号Ｍｉがマスクされ、検出信号ＭＤｉは非アクティブ（Ｌレベル）を維持する。すなわち、マッチ信号アクティブ検出回路２１から出力される検出信号ＭＤｉは、マッチ信号Ｍｉがアクティブになってから終了信号ｅｎｄが出力されるまでの間だけアクティブになり、それ以外の期間は非アクティブになる。したがって、マッチ信号アクティブ検出信号ＭＤの出力に寄与したマッチ信号は、その後のマッチ信号アクティブ検出信号ＭＤの出力に影響を及ぼさずに、別のマッチ信号がアクティブになることでマッチ信号アクティブ検出信号ＭＤが再び出力される。このように、制御回路２０は、任意のマッチ信号がアクティブになるごとにそれを検出してマッチ信号アクティブ検出信号ＭＤを出力する。
【００８１】
マッチ信号アクティブ検出信号ＭＤは、再構成可能なクロックカウント式連想メモリ１０およびクラス識別回路３３の動作制御に使用される。より詳細には、制御回路２０は、マッチ信号アクティブ検出信号ＭＤを用いて再構成可能なクロックカウント式連想メモリ１０およびクラス識別回路３３を排他的に動作させる。例えば、再構成可能なクロックカウント式連想メモリ１０において、マッチ信号アクティブ検出信号ＭＤが非アクティブのときにクロック信号ＣＬＫが供給されるように構成するとよい。クラス識別回路３３の構成例については後述する。
【００８２】
≪ｋ近傍クラスタリング回路３０の構成例≫
図８に戻り、ｋ近傍クラスタリング回路３０は、クラスデータメモリ３１と、Ｘ個のクラスカウンタ３２と、クラス識別回路３３と、最大カウンタ検出回路３４と、ｋ−マッチ信号数一致検出回路３５とを含む。
【００８３】
クラスデータメモリ３１は、エレメント回路７０の総数に等しいｎ個の参照データのそれぞれのクラスを表すｎ個のクラスデータ（クラスデータ１，クラスデータ２，…，クラスデータｎ）を保持する回路である。
【００８４】
各クラスカウンタ３２は、対応するクラスのデータ数をカウントするための回路である。クラス数は、全部でＸ個（Ｘは２以上の整数）である。
【００８５】
クラス識別回路３３は、再構成可能なクロックカウント式連想メモリ１０から出力されるアクティブのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータをクラスデータメモリ３１から読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタ３２をカウントアップする回路である。
【００８６】
ｋ−マッチ信号数一致検出回路３５は、クラス識別回路３３がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がｋに一致したことを検出する回路である。
【００８７】
図１３は、一例に係るクラスデータメモリ３１、クラスカウンタ３２、クラス識別回路３３、およびｋ−マッチ信号数一致検出回路３５の概略構成を示す。
【００８８】
クラスデータメモリ３１は、メモリ部３１１、行選択回路３１２、列デコーダ３１３、および読出／書込回路３１４を含む。
【００８９】
メモリ部３１１は、ＳＲＡＭなどで構成されるクラスデータ保存回路Ｓ１１〜Ｓ１Ｑ，Ｓ２１〜Ｓ２Ｑ，…，Ｓｎ１〜ＳｎＱを含む。なお、Ｑは、２以上の整数である。
【００９０】
クラスデータ保存回路Ｓ１１〜Ｓ１Ｑ，Ｓ２１〜Ｓ２Ｑ，…，Ｓｎ１〜ＳｎＱは、行選択回路３１２、列デコーダ３１３、および読出／書込回路３１４によって書き込まれたクラスデータを保存する。この場合、クラスデータ保存回路Ｓ１１〜Ｓ１Ｑは、Ｎ×Ｑ（Ｎは１以上の整数）ビットのクラスデータ１を保存し、クラスデータ保存回路Ｓ２１〜Ｓ２Ｑは、Ｎ×Ｑビットのクラスデータ２を保存し、以下、同様にして、クラスデータ保存回路Ｓｎ１〜ＳｎＱは、Ｎ×ＱビットのクラスデータＲを保存する。つまり、クラスデータ保存回路Ｓ１１〜Ｓ１Ｑ，Ｓ２１〜Ｓ２Ｑ，…，Ｓｎ１〜ＳｎＱのそれぞれは、クラスデータのＮビットを保存する。なお、上述したように、各クラスデータ保存回路は各ｋ−ＮＮユニット８０内に配置されている。
【００９１】
行選択回路３１２は、メモリ部３１１の行方向のアドレスを指定する。列デコーダ３１３は、メモリ部３１１の列方向のアドレスを指定する。読出／書込回路３１４は、行選択回路３１２および列デコーダ３１３によって指定されたクラスデータ保存回路Ｓ１１〜Ｓ１Ｑ，Ｓ２１〜Ｓ２Ｑ，…，Ｓｎ１〜ＳｎＱに対してクラスデータを読み書きする。
【００９２】
クラス識別回路３３は、ｎ個のマッチ信号検出回路３３１と、デマルチプレクサ３３２と、二つのバッファ３３３，３３４とを含む。クラス識別回路３３には、直列に接続されたバッファ３３１５とバッファ３３１６を介してクロック信号ＣＬＫが接続されている。制御回路２０から出力されるマッチ信号アクティブ検出信号ＭＤがＨレベルに遷移することで、バッファ３３３およびバッファ３３４を介してクラス識別回路３３にクロック信号ＣＬＫが供給される。これにより、クラス識別回路３３は動作を開始する。また、クラス識別回路３３によるクラス識別動作が終了すると終了信号ｅｎｄがＨレベルに遷移する。終了信号ｅｎｄがＨレベルに遷移することで、バッファ３３４がクラス識別回路３３へのクロック信号ＣＬＫの供給を遮断する。これにより、クラス識別回路３３は動作を停止する。
【００９３】
ｎ個のマッチ信号検出回路３３１は、ｎ個のスイッチ回路５０から出力されるｎ個のマッチ信号のそれぞれに対応して設けられている。各マッチ信号検出回路３３１は、対応するマッチ信号がアクティブであることを検出してクラスデータメモリ３１に当該マッチ信号に対応するクラスデータを選択する選択信号ａｃｔを出力する回路である。なお、上述したように、各マッチ信号検出回路３３１は各ｋ−ＮＮユニット８０内に配置されている。
【００９４】
図９に示したように、すべてのｋ−ＮＮユニット８０はカスケード接続されている。すなわち、ｎ個のマッチ信号検出回路３３１は、動作開始信号を伝搬するように直列に接続されている。すなわち、マッチ信号検出回路３３１は動作開始信号を次々に受けて順次動作するようになっている。初段のマッチ信号検出回路３３１は、マッチ信号アクティブ検出信号ＭＤを動作開始信号ｎｅｘｔ０として受けて動作を開始し、動作が終了すると次段（２段目）のマッチ信号検出回路３３１へ動作開始信号ｎｅｘｔ１を出力する。２段目のマッチ信号検出回路３３１は、動作開始信号ｎｅｘｔ１を受けて動作を開始し、動作が終了すると次段（３段目）のマッチ信号検出回路３３１へ動作開始信号ｎｅｘｔ２を出力する。以下、同様にして、最終段（ｎ段目）のマッチ信号検出回路３３１は、動作開始信号ｎｅｘｔｎ−１を受けて動作を開始し、動作が終了すると動作開始信号ｎｅｘｔｎを出力する。動作開始信号ｎｅｘｔｎは終了信号ｅｎｄに相当する。
【００９５】
マッチ信号Ｍ１が入力されるマッチ信号検出回路３３１から出力される選択信号ａｃｔ１によって、クラスデータメモリ３１においてクラスデータ１が選択され、出力される。マッチ信号Ｍ２が入力されるマッチ信号検出回路３３１から出力される選択信号ａｃｔ２によって、クラスデータメモリ３１においてクラスデータ２が選択され、出力される。以下、同様にして、マッチ信号Ｍｎが入力されるマッチ信号検出回路３３１から出力される選択信号ａｃｔｎによって、クラスデータメモリ３１においてクラスデータＲが選択され、出力される。
【００９６】
図１４は、一例に係るマッチ信号検出回路３３１の概略構成を示す。マッチ信号検出回路３３１は、一致検出回路３３１１と、レジスタ３３１２とを含む。一致検出回路３３１１は、レジスタ３３１２が保持する１ビット値とマッチ信号Ｍｉとの一致を検出して一致信号ｍａｔｃｈを出力する回路である。両者が一致する場合、一致信号ｍａｔｃｈはＨレベルとなり、両者が一致しない場合、一致信号ｍａｔｃｈはＬレベルとなる。一致信号ｍａｔｃｈおよびマッチ信号検出回路３３１に入力される動作開始信号ｎｅｘｔｉ−１はＡＮＤゲート３３１３に入力されて論理積が演算される。ＡＮＤゲート３３１３の出力が、次段のマッチ信号検出回路３３１に供給される動作開始信号ｎｅｘｔｉとなる。また、一致信号ｍａｔｃｈの論理反転および動作開始信号ｎｅｘｔｉ−１はＡＮＤゲート３３１４に入力されて論理積が演算される。ＡＮＤゲート３３１４の出力が、クラスデータの選択信号ａｃｔｉとなる。
【００９７】
レジスタ３３１２には初期値として“０”が保持されている。したがって、マッチ信号Ｍｉが非アクティブのとき、両者は一致して一致信号ｍａｔｃｈがＨレベルとなる。このとき、ＡＮＤゲート３３１３の出力がＨレベルとなり、次段のマッチ信号検出回路３３１に動作開始信号ｎｅｘｔｉ−１が供給される。また、ＡＮＤゲート３３１４の出力はＬレベルとなる。すなわち、クラスデータの選択信号ａｃｔｉは出力されない。このように、マッチ信号Ｍｉが非アクティブのとき、マッチ信号検出回路３３１は、クラスデータの選択信号を出力せずに、入力された動作開始信号をすぐさま次段のマッチ信号検出回路３３１に伝達する。
【００９８】
一方、マッチ信号Ｍｉがアクティブのとき、両者が一致しないため一致信号ｍａｔｃｈがＬレベルとなる。このとき、ＡＮＤゲート３３１３の出力がＬレベルとなり、Ｈレベルの動作開始信号ｎｅｘｔｉ−１が入力されることで、ＡＮＤゲート３３１４からＨレベルの選択信号ａｃｔｉが出力される。
【００９９】
レジスタ３３１２には、直列に接続されたバッファ３３１５とバッファ３３１６を介してクロック信号ＣＬＫが接続されている。動作開始信号ｎｅｘｔｉ−１がＨレベルになると、バッファ３３１５はクロック信号ＣＬＫをバッファ３３１６へ供給する。さらに、一致信号ｍａｔｃｈの反転がＨレベルになるとバッファ３３１６はクロック信号ＣＬＫをレジスタ３３１２へ供給する。レジスタ３３１２はクロック信号ＣＬＫを受けると保持値を１に変更する。これにより、アクティブのマッチ信号Ｍｉとレジスタ３３１２の保持値とが一致して一致信号ｍａｔｃｈがＬレベルとなる。このとき、ＡＮＤゲート３３１３の出力がＨレベルとなり、次段のマッチ信号検出回路３３１に動作開始信号ｎｅｘｔｉ−１が供給される。また、ＡＮＤゲート３３１４の出力はＬレベルとなる。すなわち、クラスデータの選択信号ａｃｔｉがＬレベルに遷移する。このように、マッチ信号Ｍｉがアクティブのとき、マッチ信号検出回路３３１は、クラスデータの選択信号を出力してから１クロック周期後に、入力された動作開始信号を次段のマッチ信号検出回路３３１に伝達する。このとき出力されるクラスデータの選択信号は１クロック周期だけＨレベルとなる。
【０１００】
図１３に戻り、デマルチプレクサ３３２にはバッファ３３３およびバッファ３３４を介して供給されるクロック信号ＣＬＫが入力され、出力先はクラスデータメモリ３１から出力されたＱビットのクラスデータｃｌｓによって決定される。すなわち、クラスデータｃｌｓはＸ個のクラスカウンタ３２の中のいずれか一つを選択する信号として用いられる。そして、１クロック周期ごとにクラスデータが選択され、当該選択されたクラスデータに対応するクラスカウンタ３２にクロック信号ＣＬＫが入力されることで、当該クラスカウンタ３２のカウント値がカウントアップされる。
【０１０１】
ｋ−マッチ信号数一致検出回路３５は、カウンタ３５１および比較器３５２を含む。カウンタ３５１には、クラス識別回路３３へのクロック信号ＣＬＫの供給と同じ条件でクロック信号ＣＬＫが入力されてパルス数をカウントアップする。すなわち、カウンタ３５１は、クラス識別回路３３がアクティブになったマッチ信号を一つ選択するごとにカウントアップする。比較器３５２は、外部から与えられる数値ｋとカウンタ３５１のカウント値とを比較する回路である。両者が一致すると比較器３５２から停止信号ｓｔｏｐが出力される。なお、図示していないが、カウント回路３５１はリセット信号を受けることで初期状態にリセットされる。
【０１０２】
停止信号ｓｔｏｐは再構成可能なクロックカウント式連想メモリ１０の動作を停止させる制御信号として利用することができる。例えば、再構成可能なクロックカウント式連想メモリ１０において、停止信号ｓｔｏｐを受けたときにクロック信号ＣＬＫの供給を遮断するように構成するとよい。これにより、再構成可能なクロックカウント式連想メモリ１０から出力される複数のマッチ信号のいずれかｋ個がアクティブになったとき、再構成可能なクロックカウント式連想メモリ１０の動作が停止してそれ以上マッチ信号がアクティブになるのが抑制される。すなわち、アクティブになるマッチ信号の数をｋ個に制限することができる。
【０１０３】
Ｘ個のクラスカウンタ３２のカウント値Ｃｎ１〜ＣｎＸは、各クラスの近傍の数を示している。すなわち、カウント値Ｃｎ１〜ＣｎＸを参照することで各クラスの票数（データ数）がわかる。最大カウンタ検出回路３４は、Ｘ個のクラスカウンタ３２の中からカウント値が最大のクラスカウンタを見つける回路である。
【０１０４】
図１５は、一例に係る最大カウンタ検出回路３４の概略構成を示す。最大カウンタ検出回路３４は、ダウンカウンタ３４１と、Ｘ個の一致検出回路３４２とを含む。ダウンカウンタ３４１は、クロック信号ＣＬＫを受けて、初期値からカウント値をカウントダウンする回路である。ダウンカウンタ３４１へはバッファ３４３を介してクロック信号ＣＬＫが供給される。バッファ３４３は、ｋ−マッチ信号数一致検出回路３５から出力される停止信号ｓｔｏｐを受けて、ダウンカウンタ３４１へクロック信号ＣＬＫを供給する。
【０１０５】
Ｘ個の一致検出回路３４２は、Ｘ個のクラスカウンタ３２のそれぞれに対応して設けられている。各一致検出回路３４２は、対応するクラスカウンタ３２のカウント値とダウンカウンタ３４１のカウント値との一致を検出して、一致信号Ｃ１〜ＣＸを出力する回路である。各一致検出回路３４２は、一致を検出すると、一致信号Ｃ１〜ＣＸをＨレベルに遷移させる。
【０１０６】
Ｘ個の一致検出回路３４２の出力信号はＯＲゲート３４４に入力され、これらの論理和が演算される。ダウンカウンタ３４１に入力されるクロック信号ＣＬＫは、ＯＲゲート３４４の出力の論理反転によってマスクされるようになっている。すなわち、ダウンカウンタ３４１のカウント値がカウントダウンされている間に、Ｘ個の一致検出回路３４２のうちのいずれか一つによってダウンカウンタ３４１のカウント値と対応するクラスカウンタ３２のカウント値との一致が検出されたとき、ダウンカウンタ３４１のカウント動作を停止させるようになっている。これにより、最大のカウント値を保持するクラスカウンタ３２のみを検出することができる。一致信号Ｃ１〜ＣＸのうちＨレベルになっているものが、ｋ近傍法に基づいて決定された検索データのクラスを表している。
【０１０７】
図１６は、別例に係る最大カウンタ検出回路３４の概略構成を示す。最大カウンタ検出回路３４は、複数の最大値選出回路３４５をツリー状に接続したトーナメント回路として構成することもできる。
【０１０８】
図１７は、一例に係る最大値選出回路３４５の概略構成を示す。最大値選出回路３４５は、比較回路３４６と、マルチプレクサ３４７とを含む。
【０１０９】
最大値選出回路３４５には、あるクラスカウンタ３２のカウント値Ａとそのクラスカウンタ３２の識別番号ｉを結合した信号Ａ＆ｉと、別のクラスカウンタ３２のカウンタ値Ｂとそのクラスカウンタ３２の識別番号ｊを結合した信号Ｂ＆ｊが入力される。比較回路３４６は、カウンタ値Ａおよびカウンタ値Ｂの大小を比較する。マルチプレクサ３４７は、信号Ａ＆ｉおよび信号Ｂ＆ｊを受け、比較回路３４６の出力信号に応じて信号Ｃとして信号Ａ＆ｉおよび信号Ｂ＆ｊのいずれか一方を出力する。具体的には、マルチプレクサ３４７は、Ａ≧Ｂの場合、信号Ａ＆ｉを出力し、Ａ＜Ｂの場合、信号Ｂ＆ｊを出力する。すなわち、信号Ｃとして、カウンタ値が大きい方のクラスカウンタ３２のカウント値ｍａｘ（Ａ，Ｂ）とそのクラスカウンタの識別番号ｉｎｄｅｘ（ｉ  ｏｒ  ｊ）を結合した信号が出力される。なお、マルチプレクサ３４７は、Ａ＞Ｂの場合、信号Ａ＆ｉを出力し、Ａ≦Ｂの場合、信号Ｂ＆ｊを出力してもよい。
【０１１０】
図１６に戻り、トーナメント回路のリーフノードにはＸ／２個の最大値選出回路３４５が配置される。リーフノードの各最大値選出回路３４５にはＸ個のクラスカウンタ３２のうち隣り合う２個のクラスカウンタ３２の各カウンタ値とそれら２個のクラスカウンタ３２の各識別番号を結合した信号が入力される。
【０１１１】
トーナメント回路の２段目にはＸ／２２個の最大値選出回路３４５が配置される。２段目の各最大値選出回路３４５にはリーフノードの隣り合う２個の最大値選出回路３４５から出力される信号が入力される。
【０１１２】
トーナメント回路のルートノードには１個の最大値選出回路３４５が配置される。そして、ルートノードの最大値選出回路３４５から、Ｘ個のクラスカウンタ３２の最大カウント値ｍａｘ（Ｃｎ１，…，ＣｎＸ）およびそのクラスカウンタ３２の識別番号であるｃｌａｓｓ  ｉｎｄｅｘを結合した信号が出力される。
【０１１３】
上記構成の最大カウンタ検出回路３４によると、Ｘ個のクラスカウンタ３２の最大値を１クロックサイクルで決定することができるため、特に高速処理に適している。
【０１１４】
以上のように、本実施形態によると、再構成可能なクロックカウント式連想メモリ１０によって検索データと各参照データとの距離がクロック数に変換されて、距離に応じたタイミングで各参照データに対応するマッチ信号がアクティブとなる。そして、ｋ近傍クラスタリング回路３０によって、より先にアクティブになったｋ個のマッチ信号に対応するｋ個のクラスデータをクラス別に分類した場合にデータ数が最大となるクラスが判定される。このようにして、ｋ近傍法に基づいた検索データのクラス分けが実現される。また、複数のエレメント回路７０をさまざまにつなぎ替えて参照データの次元数および個数を任意に拡縮することができる。これにより、アプリケーションに応じて再構成可能なｋ近傍法連想メモリ１００を最適に再構成して、再構成可能なｋ近傍法連想メモリ１００に割り当てられたリソースを最大限利用することができる。
【０１１５】
なお、本実施形態では、再構成可能なクロックカウント式連想メモリ１０から出力される複数のマッチ信号のいずれかがアクティブになるごとにクラス識別が行われるため、距離情報が欠落してしまう。そこで、例えば、クラス識別回路３３にカウンタを設けて、各マッチ信号がアクティブになるまでの時間情報（すなわち時間換算した距離情報）を保持するようにしてもよい。その場合、時間情報を用いて、検索データにより距離の近い参照データの重みを大きくするようにクラスデータの重み付けを行って、より高度なクラス判別を行うことができる。また、アクティブとなったｋ個のマッチ信号に対応する参照データのうち、検索データとの距離が閾値以上のものは除外してｋ個以下でｋ近傍法を適用することも可能である。
【０１１６】
また、先行文献２の発明に係るｋ近傍法連想メモリでは、複数の加算器をツリー状に接続してマッチ信号カウント回路を構成し、クロックカウント式連想メモリから出力されるＲ個のマッチ信号を当該マッチ信号カウント回路に接続して、より先にアクティブになったｋ個のマッチ信号をカウントしていた。これに対して、本実施形態に係る再構成可能なｋ近傍法連想メモリ１００では、そのような加算器ツリーを使用せずにより先にアクティブになったｋ個のマッチ信号をカウントすることができるため、回路規模、消費電力、および遅延時間をより小さくすることができる。
【符号の説明】
【０１１７】
１００  再構成可能なｋ近傍法連想メモリ
１０    再構成可能なクロックカウント式連想メモリ
２０    制御回路
２１    マッチ信号アクティブ検出回路
２２    ＯＲゲート
３０    ｋ近傍クラスタリング回路
３１    クラスデータメモリ
３２    クラスカウンタ
３３    クラス識別回路
３３１  マッチ信号検出回路
３４    最大カウンタ検出回路
３４１  ダウンカウンタ
３４２  一致検出回路
３４５  最大値選出回路
３５    ｋ−マッチ信号数一致検出回路
４０    参照データ検索回路
５０    スイッチ回路
６０    メモリ（回路構成情報記憶回路）
７０    エレメント回路
ＳＣ    参照データ保存回路
ＤＰ    距離計算回路
ＤＣ    距離／クロック数変換回路
【図１】
0006411914.tif 000004
【図２】
0006411914.tif 000005
【図３】
0006411914.tif 000006
【図４】
0006411914.tif 000007
【図５】
0006411914.tif 000008
【図６】
0006411914.tif 000009
【図７】
0006411914.tif 000010
【図８】
0006411914.tif 000011
【図９】
0006411914.tif 000012
【図１０】
0006411914.tif 000013
【図１１】
0006411914.tif 000014
【図１２】
0006411914.tif 000015
【図１３】
0006411914.tif 000016
【図１４】
0006411914.tif 000017
【図１５】
0006411914.tif 000018
【図１６】
0006411914.tif 000019
【図１７】
0006411914.tif 000020