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

明細書 :k近傍法連想メモリ

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2016-143430 (P2016-143430A)
公開日 平成28年8月8日(2016.8.8)
発明の名称または考案の名称 k近傍法連想メモリ
国際特許分類 G11C  15/04        (2006.01)
G06F  17/30        (2006.01)
FI G11C 15/04 631M
G06F 17/30 210D
G06F 17/30 350D
請求項の数または発明の数 6
出願形態 OL
全頁数 19
出願番号 特願2015-016977 (P2015-016977)
出願日 平成27年1月30日(2015.1.30)
発明者または考案者 【氏名】マタウシュ ハンスユルゲン
【氏名】山崎 翔悟
出願人 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
個別代理人の代理人 【識別番号】110001427、【氏名又は名称】特許業務法人前田特許事務所
審査請求 未請求
要約 【課題】k近傍法を効果的に実現するk近傍法連想メモリを提供する。
【解決手段】k近傍法連想メモリ100は、R個の参照データを保持しており、R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリ10と、クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、R個のマッチ信号の少なくとも一つがアクティブになるごとに、R個の参照データのそれぞれのクラスを表すR個のクラスデータからアクティブになった少なくとも一つの、k個のマッチ信号のそれぞれに対応するクラスデータを選択し、選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路30とを備えている。
【選択図】図1
特許請求の範囲 【請求項1】
R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、前記R個のマッチ信号の少なくとも一つがアクティブになるごとに、前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている
ことを特徴とするk近傍法連想メモリ。
【請求項2】
前記k近傍クラスタリング回路が、
前記R個のクラスデータを保持するクラスデータメモリと、
X個のクラスのそれぞれに対応するX個のクラスカウンタと、
前記アクティブになった少なくとも一つのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップし、前記アクティブになった少なくとも一つのマッチ信号をすべて選択し終わると終了信号を出力するクラス識別回路と、
前記X個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路と、
前記クラス識別回路がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がkに一致したことを検出するk-マッチ信号数一致検出回路とを有するものであり、
前記k近傍法連想メモリが、前記R個のマッチ信号の少なくとも一つがアクティブになると前記クロックカウント式連想メモリの動作を停止させて前記クラス識別回路を動作させ、前記クラス識別回路から前記終了信号が出力されると前記クラス識別回路の動作を停止させて前記クロックカウント式連想メモリを動作させる制御回路を備え、
前記クロックカウント式連想メモリが、前記k-マッチ信号数一致検出回路によって前記カウント値がkに一致したことが検出されたとき、動作を停止するように構成されている、請求項1に記載のk近傍法連想メモリ。
【請求項3】
前記制御回路が、
前記R個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブになってから前記クラス識別回路から前記終了信号が出力されるまでの間だけアクティブになる検出信号を出力するR個のマッチ信号アクティブ検出回路と、
前記R個のマッチ信号アクティブ検知回路から出力されるR個の検出信号の論理和を演算するORゲートとを有し、
前記ORゲートの出力信号で前記クラス識別回路および前記クロックカウント式連想メモリの動作を制御する、請求項2に記載のk近傍法連想メモリ。
【請求項4】
前記クラス識別回路が、前記R個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力するR個のマッチ信号検出回路を有し、
前記R個のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、
前記R個のマッチ信号検出回路のそれぞれが、前記対応するマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項2および3のいずれか一つに記載のk近傍法連想メモリ。
【請求項5】
前記最大カウンタ検出回路が、
初期値からカウント値をカウントダウンするダウンカウンタと、
前記X個のクラスカウンタのそれぞれに対応して設けられ、対応するクラスカウンタのカウント値と前記ダウンカウンタのカウント値との一致を検出するX個の一致検出回路とを有し、
前記ダウンカウンタのカウント値がカウントダウンされている間に、前記X個の一致検出回路のうちのいずれか一つによって前記ダウンカウンタのカウント値と対応するクラスカウンタのカウント値との一致が検出されたとき、前記ダウンカウンタのカウント動作を停止させる、請求項2ないし4のいずれか一つに記載のk近傍法連想メモリ。
【請求項6】
前記最大カウンタ検出回路が、2入力1出力の複数の最大値選出回路がツリー状に接続されてなり、リーフノードの複数の最大値選出回路に前記X個のクラスカウンタの各カウント値および各クラスカウンタの識別番号を結合した各信号が入力され、ルートノードの最大値選出回路から前記X個のクラスカウンタの最大カウント値およびそのクラスカウンタの識別番号を結合した信号を出力するトーナメント回路であり、
前記最大値選出回路が、第1のクラスカウンタのカウント値および前記第1のクラスカウンタの識別番号を結合した第1の信号、および第2のクラスカウンタのカウント値および前記第2のクラスカウンタの識別番号を結合した第2の信号を受け、前記第1および第2のクラスカウンタのうちカウント値が大きい方のクラスカウンタのカウント値およびそのクラスカウンタの識別番号を結合した第3の信号を出力する、請求項2ないし4のいずれか一つに記載のk近傍法連想メモリ。
発明の詳細な説明 【技術分野】
【0001】
本発明は、連想メモリに関し、特に、k近傍法を効果的に実現する連想メモリに関する。
【背景技術】
【0002】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated circuit)上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【0003】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【0004】
前者は、CAM(Content Addressable Memory)と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ(Associative Memory)と呼ぶ。
【0005】
連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている(非特許文献1参照)。また、連想メモリにk近傍探索を取り入れたものが知られている(非特許文献2参照)。
【先行技術文献】
【0006】
<nplcit num="1"> <text>S.Sasaki et al., "Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization," ESSCIRC'2012, 2012, pp.185-188</text></nplcit><nplcit num="2"> <text>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</text></nplcit>
【発明の概要】
【発明が解決しようとする課題】
【0007】
パターン認識の分野において機械学習アルゴリズムとしてk近傍法がよく用いられる。k近傍法は、パターン認識において高い信頼性を持つ。従来技術では、連想メモリにおいてk近傍探索を取り入れているものの、k近傍法が実効的に実現されておらず、特にk近傍法に基づいたパターンのクラス分けまでは実現できていない。
【0008】
この問題に関して、本願発明者は、k近傍法を効果的に実現することができるk近傍法連想メモリを発明し、国際出願PCT/JP2014/003809(以下、先願という)に当該発明を開示した。
【0009】
本発明も先願発明と同様に、k近傍法を効果的に実現することができるk近傍法連想メモリを提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明の一局面に従ったk近傍法連想メモリは、R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、前記R個のマッチ信号の少なくとも一つがアクティブになるごとに、前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている。
【0011】
これによると、クロックカウント式連想メモリによって検索データと各参照データとの距離がクロック数に変換されて、距離に応じたタイミングで各参照データに対応するマッチ信号がアクティブとなり、k近傍クラスタリング回路によって、より先にアクティブになったk個のマッチ信号に対応するk個のクラスデータをクラス別に分類した場合にデータ数が最大となるクラスが判定される。このようにして、k近傍法に基づいた検索データのクラス分けが実現される。
【発明の効果】
【0012】
本発明によると、LSI上にk近傍法を効果的に実装することができる。
【図面の簡単な説明】
【0013】
【図1】本発明の一実施形態に係るk近傍法連想メモリの概略構成図
【図2】一例に係るクロックカウント式連想メモリの概略構成図
【図3】一例に係る距離/クロック数変換回路の概略構成図
【図4】一例に係るカウンタ一致検出回路の概略構成図
【図5】一例に係るマッチ信号のタイミングチャート
【図6】一例に係る制御回路の概略構成図
【図7】一例に係るクラスデータメモリ、クラスカウンタ、クラス識別回路、およびk-マッチ信号数一致検出回路の概略構成図
【図8】一例に係るマッチ信号検出回路の概略構成図
【図9】一例に係る最大カウンタ検出回路の概略構成図
【図10】別例に係る最大カウンタ検出回路の概略構成図
【図11】一例に係る最大値選出回路の概略構成図
【発明を実施するための形態】
【0014】
以下、図面を参照しながら本発明を実施するための形態について説明する。なお、本発明は、以下の実施形態に限定されるものではない。

【0015】
図1は、本発明の一実施形態に係るk近傍法連想メモリ100の概略構成を示す。本実施形態に係るk近傍法連想メモリ100は、クロックカウント式連想メモリ10と、制御回路20と、k近傍クラスタリング回路30とを備えている。

【0016】
クロックカウント式連想メモリ10は、R個の参照データ(参照データ1,参照データ2,…,参照データR)を保持しており、これらR個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力する回路である。なお、「距離」とはマンハッタン距離、ユークリッド距離などを含む。また、「アクティブ」とは、正論理では信号がLレベルからHレベルへと遷移することをいい、負論理では信号がHレベルからLレベルへと遷移することをいう。便宜のため、以下では正論理を前提に説明する。

【0017】
制御回路20は、クロックカウント式連想メモリ10およびk近傍クラスタリング回路30の動作を制御する回路である。

【0018】
k近傍クラスタリング回路30は、R個の参照データのそれぞれのクラスを表すR個のクラスデータ(クラスデータ1,クラスデータ2,…,クラスデータR)から、クロックカウント式連想メモリ10から出力されるアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、これらk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定する回路である。

【0019】
k近傍法連想メモリ100は、上記3つの回路を備えることで、k近傍法に基づいて、与えられた検索データがいずれのクラスに分類されるかを判定することができる。以下、各回路の構成例について説明する。

【0020】
≪クロックカウント式連想メモリ10の構成例≫
図2は、一例に係るクロックカウント式連想メモリ10の概略構成を示す。クロックカウント式連想メモリ10は、メモリ部11、行デコーダ12、列デコーダ13、読出/書込回路14、および検索データ保存回路15を含む。

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

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

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

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

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

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

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

【0028】
【数1】
JP2016143430A_000003t.gif

【0029】
式(1)において、Drj(r=1~R,j=1~W)は、参照データと検索データとの距離(絶対値差)を表す。nMrは、参照データと検索データとのマンハッタン距離を示している。また、式(1)において、Injは、検索データであり、Rerjは、参照データである。各データInj、Rerjは、それぞれ、Mビットからなる。

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

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

【0032】
距離/クロック数変換回路DCは、距離演算回路DP11~DP1WからW個の距離信号D1jを受け、各距離信号D1jの二乗値の和に相当するクロック信号CLKのクロック数CN_total1を後述する方法によってカウントする。そして、そのクロック数CN_total1をカウントしたタイミングを示すマッチ信号Mを出力する。

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

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

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

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

【0037】
図3は、一例に係る距離/クロック数変換回路DCの概略構成を示す。なお、距離/クロック数変換回路DC~DCのそれぞれも、図3に示す距離/クロック数変換回路DCと同様の構成を有する。距離/クロック数変換回路DCは、バッファ121~12Wと、カウンタ一致検出回路131~13Wとを含む。

【0038】
バッファ121は、k近傍法連想メモリ100の制御回路(図示せず)から検索開始信号SBを受け、k近傍法連想メモリ100に内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受ける。そして、バッファ121は、検索開始信号SBがLレベルからHレベルに遷移すると、その受けたクロック信号CLKをバッファ122およびカウンタ一致検出回路131へ出力する。バッファ122は、クロック信号CLKをバッファ121から受け、カウンタ一致検出回路131から、後述するHレベルの一致信号(DETECT1)を受けると、クロック信号CLKをバッファ123(図示せず)およびカウンタ一致検出回路132へ出力する。以下、同様にして、バッファ12Wは、クロック信号CLKをバッファ12W-1(図示せず)から受け、カウンタ一致検出回路13W-1(図示せず)から、後述するHレベルの一致信号(DETECTW-1)を受けると、クロック信号CLKをカウンタ一致検出回路13Wへ出力する。

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

【0040】
図4は、一例に係るカウンタ一致検出回路131~13Wの概略構成を示す。本例は、W=2の場合を示している。カウンタ一致検出回路131は、クロック数変換回路131aと、カウンタ131bと、一致検出回路131cとを含む。カウンタ一致検出回路132は、クロック数変換回路132aと、カウンタ132bと、一致検出回路132cとを含む。以下、各構成の機能について説明する。

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

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

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

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

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

【0046】
一致検出回路132cは、カウンタ132bからカウンタ値を受け、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。一致検出回路132cは、距離信号D12が示す距離とカウンタ値とを比較し、距離信号D12が示す距離とカウンタ値とが一致するときに、Hレベルの一致信号(DETECT2)をクロック数変換回路132aとバッファ122へ出力するとともに、Hレベルの一致信号(DETECT2)をマッチ信号Mとして出力する。また、一致検出回路132cは、距離信号D12が示す距離とカウンタ値とが一致しないときは、Lレベルの一致信号(DETECT2)をクロック数変換回路132aに出力する。

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

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

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

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

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

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

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

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

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

【0056】
【数2】
JP2016143430A_000004t.gif

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

【0058】
図5は、一例に係るマッチ信号のタイミングチャートである。距離/クロック数変換回路DC~DCは、図5に示すように、例えばマッチ信号M~Mをそれぞれクロック信号CLKに同期して出力する。

【0059】
なお、上記構成のクロックカウント式連想メモリ10は一例に過ぎず、図5に示したような出力が可能なクロックカウント式連想メモリであればよい。

【0060】
≪制御回路20の構成例≫
図6は、一例に係る制御回路20の概略構成を示す。制御回路20は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号M~Mのそれぞれに対応するR個のマッチ信号アクティブ検出回路21と、R個のマッチ信号アクティブ検出回路21から出力される検出信号MD~MDの論理和を演算してマッチ信号アクティブ検出信号MDを出力するORゲート22とを含む。マッチ信号アクティブ検出回路21は、対応するマッチ信号M(iは1からRまでの整数)と後述するクラス識別回路33によるクラス識別動作の終了を表す終了信号endとの論理積を演算するANDゲート211と、Hレベル信号がデータ入力(D)されるとともにANDゲート211の出力信号がクロック入力(CLK)されるDフリップフロップ212と、マッチ信号MとDフリップフロップの反転出力との論理積を演算して検出信号MDiを出力するANDゲート213とを含む。なお、図示していないが、各Dフリップフロップ212はリセット信号を受けることで初期状態にリセットされる。

【0061】
このような回路構成によれば、マッチ信号アクティブ検出回路21から出力される検出信号MDは、マッチ信号Mがアクティブ(Hレベル)になるとアクティブ(Hレベル)になり、その後、終了信号endが立ち上がってDフリップフロップ211がデータ入力(D)を取り込んで反転出力(Qバー)がLレベルに変化することで非アクティブ(Lレベル)になる。ここで、Dフリップフロップ211のデータ入力(D)はHレベル信号の固定値であるため、Dフリップフロップ211が一度データ入力(D)を取り込んだ後は、Dフリップフロップ211がリセットされるまで、Dフリップフロップ211の反転出力(Qバー)はLレベルに維持される。このため、ANDゲート213においてマッチ信号Mがマスクされ、検出信号MDは非アクティブ(Lレベル)を維持する。すなわち、マッチ信号アクティブ検出回路21から出力される検出信号MDは、マッチ信号Mがアクティブになってから終了信号endが出力されるまでの間だけアクティブになり、それ以外の期間は非アクティブになる。したがって、マッチ信号アクティブ検出信号MDの出力に寄与したマッチ信号は、その後のマッチ信号アクティブ検出信号MDの出力に影響を及ぼさずに、別のマッチ信号がアクティブになることでマッチ信号アクティブ検出信号MDが再び出力される。このように、制御回路20は、任意のマッチ信号がアクティブになるごとにそれを検出してマッチ信号アクティブ検出信号MDを出力する。

【0062】
マッチ信号アクティブ検出信号MDは、クロックカウント式連想メモリ10およびクラス識別回路33の動作制御に使用される。より詳細には、制御回路20は、マッチ信号アクティブ検出信号MDを用いてクロックカウント式連想メモリ10およびクラス識別回路33を排他的に動作させる。例えば、クロックカウント式連想メモリ10において、マッチ信号アクティブ検出信号MDが非アクティブのときにクロック信号CLKが供給されるように構成するとよい。クラス識別回路33の構成例については後述する。

【0063】
≪k近傍クラスタリング回路30の構成例≫
図1に戻り、k近傍クラスタリング回路30は、クラスデータメモリ31と、X個のクラスカウンタ32と、クラス識別回路33と、最大カウンタ検出回路34と、k-マッチ信号数一致検出回路35とを含む。

【0064】
クラスデータメモリ31は、R個の参照データのそれぞれのクラスを表すR個のクラスデータ(クラスデータ1,クラスデータ2,…,クラスデータR)を保持する回路である。

【0065】
各クラスカウンタ32は、対応するクラスのデータ数をカウントするための回路である。クラス数は、全部でX個(Xは2以上の整数)である。

【0066】
クラス識別回路33は、クロックカウント式連想メモリ10から出力されるアクティブのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータをクラスデータメモリ31から読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタ32をカウントアップする回路である。

【0067】
k-マッチ信号数一致検出回路35は、クラス識別回路33がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がkに一致したことを検出する回路である。

【0068】
図7は、一例に係るクラスデータメモリ31、クラスカウンタ32、クラス識別回路33、およびk-マッチ信号数一致検出回路35の概略構成を示す。

【0069】
クラスデータメモリ31は、メモリ部311、行選択回路312、列デコーダ313、および読出/書込回路314を含む。

【0070】
メモリ部311は、SRAMなどで構成されるクラスデータ保存回路S11~S1Q,S21~S2Q,…,SR1~SRQを含む。なお、Qは、2以上の整数である。

【0071】
クラスデータ保存回路S11~S1Q,S21~S2Q,…,SR1~SRQは、行選択回路312、列デコーダ313、および読出/書込回路314によって書き込まれたクラスデータを保存する。この場合、クラスデータ保存回路S11~S1Qは、N×Q(Nは1以上の整数)ビットのクラスデータ1を保存し、クラスデータ保存回路S21~S2Qは、N×Qビットのクラスデータ2を保存し、以下、同様にして、クラスデータ保存回路SR1~SRQは、N×QビットのクラスデータRを保存する。つまり、クラスデータ保存回路S11~S1Q,S21~S2Q,…,SR1~SRQのそれぞれは、クラスデータのNビットを保存する。

【0072】
行選択回路312は、メモリ部311の行方向のアドレスを指定する。列デコーダ313は、メモリ部311の列方向のアドレスを指定する。読出/書込回路314は、行選択回路312および列デコーダ313によって指定されたクラスデータ保存回路S11~S1Q,S21~S2Q,…,SR1~SRQに対してクラスデータを読み書きする。

【0073】
クラス識別回路33は、R個のマッチ信号検出回路331と、デマルチプレクサ332と、二つのバッファ333,334とを含む。クラス識別回路33には、直列に接続されたバッファ3315とバッファ3316を介してクロック信号CLKが接続されている。制御回路20から出力されるマッチ信号アクティブ検出信号MDがHレベルに遷移することで、バッファ333およびバッファ334を介してクラス識別回路33にクロック信号CLKが供給される。これにより、クラス識別回路33は動作を開始する。また、クラス識別回路33によるクラス識別動作が終了すると終了信号endがHレベルに遷移する。終了信号endがHレベルに遷移することで、バッファ334がクラス識別回路33へのクロック信号CLKの供給を遮断する。これにより、クラス識別回路33は動作を停止する。

【0074】
R個のマッチ信号検出回路331は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号のそれぞれに対応して設けられている。各マッチ信号検出回路331は、対応するマッチ信号がアクティブであることを検出してクラスデータメモリ31に当該マッチ信号に対応するクラスデータを選択する選択信号actを出力する回路である。

【0075】
R個のマッチ信号検出回路331は、動作開始信号を伝搬するように直列に接続されている。すなわち、マッチ信号検出回路331は動作開始信号を次々に受けて順次動作するようになっている。初段のマッチ信号検出回路331は、マッチ信号アクティブ検出信号MDを動作開始信号nextとして受けて動作を開始し、動作が終了すると次段(2段目)のマッチ信号検出回路331へ動作開始信号nextを出力する。2段目のマッチ信号検出回路331は、動作開始信号nextを受けて動作を開始し、動作が終了すると次段(3段目)のマッチ信号検出回路331へ動作開始信号nextを出力する。以下、同様にして、最終段(R段目)のマッチ信号検出回路331は、動作開始信号nextR-1を受けて動作を開始し、動作が終了すると動作開始信号nextを出力する。動作開始信号nextは終了信号endに相当する。

【0076】
マッチ信号Mが入力されるマッチ信号検出回路331から出力される選択信号actによって、クラスデータメモリ31においてクラスデータ1が選択され、出力される。マッチ信号Mが入力されるマッチ信号検出回路331から出力される選択信号actによって、クラスデータメモリ31においてクラスデータ2が選択され、出力される。以下、同様にして、マッチ信号Mが入力されるマッチ信号検出回路331から出力される選択信号actによって、クラスデータメモリ31においてクラスデータRが選択され、出力される。

【0077】
図8は、一例に係るマッチ信号検出回路331の概略構成を示す。マッチ信号検出回路331は、一致検出回路3311と、レジスタ3312とを含む。一致検出回路3311は、レジスタ3312が保持する1ビット値とマッチ信号Mとの一致を検出して一致信号matchを出力する回路である。両者が一致する場合、一致信号matchはHレベルとなり、両者が一致しない場合、一致信号matchはLレベルとなる。一致信号matchおよびマッチ信号検出回路331に入力される動作開始信号nexti-1はANDゲート3313に入力されて論理積が演算される。ANDゲート3313の出力が、次段のマッチ信号検出回路331に供給される動作開始信号nextとなる。また、一致信号matchの論理反転および動作開始信号nexti-1はANDゲート3314に入力されて論理積が演算される。ANDゲート3314の出力が、クラスデータの選択信号actとなる。

【0078】
レジスタ3312には初期値として0が保持されている。したがって、マッチ信号Mが非アクティブのとき、両者は一致して一致信号matchがHレベルとなる。このとき、ANDゲート3313の出力がHレベルとなり、次段のマッチ信号検出回路331に動作開始信号nexti-1が供給される。また、ANDゲート3314の出力はLレベルとなる。すなわち、クラスデータの選択信号actは出力されない。このように、マッチ信号Mが非アクティブのとき、マッチ信号検出回路331は、クラスデータの選択信号を出力せずに、入力された動作開始信号をすぐさま次段のマッチ信号検出回路331に伝達する。

【0079】
一方、マッチ信号Mがアクティブのとき、両者が一致しないため一致信号matchがLレベルとなる。このとき、ANDゲート3313の出力がLレベルとなり、Hレベルの動作開始信号nexti-1が入力されることで、ANDゲート3314からHレベルの選択信号actが出力される。

【0080】
レジスタ3312には、直列に接続されたバッファ3315とバッファ3316を介してクロック信号CLKが接続されている。動作開始信号nexti-1がHレベルになると、バッファ3315はクロック信号CLKをバッファ3316へ供給する。さらに、一致信号matchの反転がHレベルになるとバッファ3316はクロック信号CLKをレジスタ3312へ供給する。レジスタ3312はクロック信号CLKを受けると保持値を1に変更する。これにより、アクティブのマッチ信号Mとレジスタ3312の保持値とが一致して一致信号matchがLレベルとなる。このとき、ANDゲート3313の出力がHレベルとなり、次段のマッチ信号検出回路331に動作開始信号nexti-1が供給される。また、ANDゲート3314の出力はLレベルとなる。すなわち、クラスデータの選択信号actがLレベルに遷移する。このように、マッチ信号Mがアクティブのとき、マッチ信号検出回路331は、クラスデータの選択信号を出力してから1クロック周期後に、入力された動作開始信号を次段のマッチ信号検出回路331に伝達する。このとき出力されるクラスデータの選択信号は1クロック周期だけHレベルとなる。

【0081】
図7に戻り、デマルチプレクサ332にはバッファ333およびバッファ334を介して供給されるクロック信号CLKが入力され、出力先はクラスデータメモリ31から出力されたQビットのクラスデータclsによって決定される。すなわち、クラスデータclsはX個のクラスカウンタ32の中のいずれか一つを選択する信号として用いられる。そして、1クロック周期ごとにクラスデータが選択され、当該選択されたクラスデータに対応するクラスカウンタ32にクロック信号CLKが入力されることで、当該クラスカウンタ32のカウント値がカウントアップされる。

【0082】
k-マッチ信号数一致検出回路35は、カウンタ351および比較器352を含む。カウンタ351には、クラス識別回路33へのクロック信号CLKの供給と同じ条件でクロック信号CLKが入力されてパルス数をカウントアップする。すなわち、カウンタ351は、クラス識別回路33がアクティブになったマッチ信号を一つ選択するごとにカウントアップする。比較器352は、外部から与えられる数値kとカウンタ351のカウント値とを比較する回路である。両者が一致すると比較器352から停止信号stopが出力される。なお、図示していないが、カウント回路351はリセット信号を受けることで初期状態にリセットされる。

【0083】
停止信号stopはクロックカウント式連想メモリ10の動作を停止させる制御信号として利用することができる。例えば、クロックカウント式連想メモリ10において、停止信号stopを受けたときにクロック信号CLKの供給を遮断するように構成するとよい。これにより、クロックカウント式連想メモリ10から出力されるR個のマッチ信号M~Mのいずれかk個がアクティブになったとき、クロックカウント式連想メモリ10の動作が停止してそれ以上マッチ信号がアクティブになるのが抑制される。すなわち、アクティブになるマッチ信号の数をk個に制限することができる。

【0084】
X個のクラスカウンタ32のカウント値Cn~Cnは、各クラスの近傍の数を示している。すなわち、カウント値Cn~Cnを参照することで各クラスの票数(データ数)がわかる。最大カウンタ検出回路34は、X個のクラスカウンタ32の中からカウント値が最大のクラスカウンタを見つける回路である。

【0085】
図9は、一例に係る最大カウンタ検出回路34の概略構成を示す。最大カウンタ検出回路34は、ダウンカウンタ341と、X個の一致検出回路342とを含む。ダウンカウンタ341は、クロック信号CLKを受けて、初期値からカウント値をカウントダウンする回路である。ダウンカウンタ341へはバッファ343を介してクロック信号CLKが供給される。バッファ343は、k-マッチ信号数一致検出回路35から出力される停止信号stopを受けて、ダウンカウンタ341へクロック信号CLKを供給する。

【0086】
X個の一致検出回路342は、X個のクラスカウンタ32のそれぞれに対応して設けられている。各一致検出回路342は、対応するクラスカウンタ32のカウント値とダウンカウンタ341のカウント値との一致を検出して、一致信号C~Cを出力する回路である。各一致検出回路342は、一致を検出すると、一致信号C~CをHレベルに遷移させる。

【0087】
X個の一致検出回路342の出力信号はORゲート344に入力され、これらの論理和が演算される。ダウンカウンタ341に入力されるクロック信号CLKは、ORゲート344の出力の論理反転によってマスクされるようになっている。すなわち、ダウンカウンタ341のカウント値がカウントダウンされている間に、X個の一致検出回路342のうちのいずれか一つによってダウンカウンタ341のカウント値と対応するクラスカウンタ32のカウント値との一致が検出されたとき、ダウンカウンタ341のカウント動作を停止させるようになっている。これにより、最大のカウント値を保持するクラスカウンタ32のみを検出することができる。一致信号C~CのうちHレベルになっているものが、k近傍法に基づいて決定された検索データのクラスを表している。

【0088】
図10は、別例に係る最大カウンタ検出回路34の概略構成を示す。最大カウンタ検出回路34は、複数の最大値選出回路345をツリー状に接続したトーナメント回路として構成することもできる。

【0089】
図11は、一例に係る最大値選出回路345の概略構成を示す。最大値選出回路345は、比較回路346と、マルチプレクサ347とを含む。

【0090】
最大値選出回路345には、あるクラスカウンタ32のカウント値Aとそのクラスカウンタ32の識別番号iを結合した信号A&iと、別のクラスカウンタ32のカウンタ値Bとそのクラスカウンタ32の識別番号jを結合した信号B&jが入力される。比較回路346は、カウンタ値Aおよびカウンタ値Bの大小を比較する。マルチプレクサ347は、信号A&iおよび信号B&jを受け、比較回路346の出力信号に応じて信号Cとして信号A&iおよび信号B&jのいずれか一方を出力する。具体的には、マルチプレクサ347は、A≧Bの場合、信号A&iを出力し、A<Bの場合、信号B&jを出力する。すなわち、信号Cとして、カウンタ値が大きい方のクラスカウンタ32のカウント値max(A,B)とそのクラスカウンタの識別番号index(i or j)を結合した信号が出力される。なお、マルチプレクサ347は、A>Bの場合、信号A&iを出力し、A≦Bの場合、信号B&jを出力してもよい。

【0091】
図10に戻り、トーナメント回路のリーフノードにはX/2個の最大値選出回路345が配置される。リーフノードの各最大値選出回路345にはX個のクラスカウンタ32のうち隣り合う2個のクラスカウンタ32の各カウンタ値とそれら2個のクラスカウンタ32の各識別番号を結合した信号が入力される。

【0092】
トーナメント回路の2段目にはX/2個の最大値選出回路345が配置される。2段目の各最大値選出回路345にはリーフノードの隣り合う2個の最大値選出回路345から出力される信号が入力される。

【0093】
トーナメント回路のルートノードには1個の最大値選出回路345が配置される。そして、ルートノードの最大値選出回路345から、X個のクラスカウンタ32の最大カウント値max(Cn,…,Cn)およびそのクラスカウンタ32の識別番号であるclass indexを結合した信号が出力される。

【0094】
上記構成の最大カウンタ検出回路34によると、X個のクラスカウンタ32の最大値を1クロックサイクルで決定することができるため、特に高速処理に適している。

【0095】
以上のように、本実施形態によると、クロックカウント式連想メモリ10によって検索データと各参照データとの距離がクロック数に変換されて、距離に応じたタイミングで各参照データに対応するマッチ信号がアクティブとなる。そして、k近傍クラスタリング回路30によって、より先にアクティブになったk個のマッチ信号に対応するk個のクラスデータをクラス別に分類した場合にデータ数が最大となるクラスが判定される。このようにして、k近傍法に基づいた検索データのクラス分けが実現される。

【0096】
なお、本実施形態では、クロックカウント式連想メモリ10から出力されるR個のマッチ信号のいずれかがアクティブになるごとにクラス識別が行われるため、距離情報が欠落してしまう。そこで、例えば、クラス識別回路33にカウンタを設けて、各マッチ信号がアクティブになるまでの時間情報(すなわち時間換算した距離情報)を保持するようにしてもよい。その場合、時間情報を用いて、検索データにより距離の近い参照データの重みを大きくするようにクラスデータの重み付けを行って、より高度なクラス判別を行うことができる。また、アクティブとなったk個のマッチ信号に対応する参照データのうち、検索データとの距離が閾値以上のものは除外してk個以下でk近傍法を適用することも可能である。

【0097】
また、先願発明に係るk近傍法連想メモリでは、複数の加算器をツリー状に接続してマッチ信号カウント回路を構成し、クロックカウント式連想メモリ10から出力されるR個のマッチ信号を当該マッチ信号カウント回路に接続して、より先にアクティブになったk個のマッチ信号をカウントしていた。これに対して、本実施形態に係るk近傍法連想メモリ100では、そのような加算器ツリーを使用せずにより先にアクティブになったk個のマッチ信号をカウントすることができるため、回路規模、消費電力、および遅延時間をより小さくすることができる。
【符号の説明】
【0098】
100 k近傍法連想メモリ
10 クロックカウント式連想メモリ
20 制御回路
31 マッチ信号カウント回路
30 k近傍クラスタリング回路
31 クラスデータメモリ
32 クラスカウンタ
33 クラス識別回路
331 マッチ信号検出回路
34 最大カウンタ検出回路
341 ダウンカウンタ
342 一致検出回路
345 最大値選出回路
35 k-マッチ信号数一致検出回路
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10