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

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

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成29年3月2日(2017.3.2)
発明の名称または考案の名称 k近傍法連想メモリ
国際特許分類 G11C  15/04        (2006.01)
G06N  99/00        (2010.01)
G06F  17/30        (2006.01)
FI G11C 15/04 631W
G06N 99/00 156
G06F 17/30 210D
G06F 17/30 350C
国際予備審査の請求 未請求
全頁数 26
出願番号 特願2015-528142 (P2015-528142)
国際出願番号 PCT/JP2014/003809
国際公開番号 WO2015/011907
国際出願日 平成26年7月17日(2014.7.17)
国際公開日 平成27年1月29日(2015.1.29)
優先権出願番号 2013154887
優先日 平成25年7月25日(2013.7.25)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JP , KE , KG , KN , KP , KR , KZ , LA , LC , LK , LR , LS , LT , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT , TZ , UA , UG , US
発明者または考案者 【氏名】マタウシュ ハンスユルゲン
【氏名】赤澤 智信
【氏名】山崎 翔悟
出願人 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
個別代理人の代理人 【識別番号】110001427、【氏名又は名称】特許業務法人前田特許事務所
審査請求 未請求
要約 k近傍法連想メモリ(100)は、R個の参照データを保持しており、R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリ(10)と、クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかK個のマッチ信号がアクティブになったことを検出し、そのときのR個のマッチ信号を保持するk近傍検索回路(20)と、R個の参照データのそれぞれのクラスを表すR個のクラスデータからk近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路(30)とを備えている。
特許請求の範囲 【請求項1】
R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになったことを検出し、そのときの前記R個のマッチ信号を保持するk近傍検索回路と、
前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから前記k近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、前記k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている
ことを特徴とするk近傍法連想メモリ。
【請求項2】
前記k近傍検索回路が、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちアクティブになったマッチ信号の数をカウントするマッチ信号カウント回路と、
前記マッチ信号カウント回路のカウント値がkに一致したことを検出するk-マッチ信号数一致検出回路と、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号が入力され、前記k-マッチ信号数一致検出回路によって前記マッチ信号カウント回路のカウント値がkに一致したことが検出されたときの前記R個のマッチ信号を保持するマッチ信号保持回路とを有する、請求項1に記載のk近傍法連想メモリ。
【請求項3】
前記クロックカウント式連想メモリが、前記k-マッチ信号数一致検出回路によって前記マッチ信号カウント回路のカウント値がkに一致したことが検出されたとき、動作を停止するように構成されている、請求項2に記載のk近傍法連想メモリ。
【請求項4】
前記k-マッチ信号数一致検出回路が、前記マッチ信号カウント回路のカウント値がkを超えたことを検出するように構成されている、請求項2および3のいずれか一つに記載のk近傍法連想メモリ。
【請求項5】
前記マッチ信号カウント回路が、複数の加算器がツリー状に接続されてなり、リーフノードの複数の加算器に前記R個のマッチ信号がそれぞれ入力され、ルートノードの加算器からカウント値を出力する加算器ツリー回路である、請求項2から4のいずれか一つに記載のk近傍法連想メモリ。
【請求項6】
前記k近傍クラスタリング回路が、
前記R個のクラスデータを保持するクラスデータメモリと、
X個のクラスのそれぞれに対応するX個のクラスカウンタと、
前記k近傍検索回路が保持するアクティブのk個のマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップするクラス識別回路と、
前記X個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路とを有する、請求項1から5のいずれか一つに記載のk近傍法連想メモリ。
【請求項7】
前記クラス識別回路が、前記k近傍検索回路が保持するR個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力するR個のマッチ信号検出回路を有し、
前記R個のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、
前記R個のマッチ信号検出回路のそれぞれが、前記対応するマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項6に記載のk近傍法連想メモリ。
【請求項8】
前記最大カウンタ検出回路が、
初期値からカウント値をカウントダウンするダウンカウンタと、
前記X個のクラスカウンタのそれぞれに対応して設けられ、対応するクラスカウンタのカウント値と前記ダウンカウンタのカウント値との一致を検出するX個の一致検出回路とを有し、
前記ダウンカウンタのカウント値がカウントダウンされている間に、前記X個の一致検出回路のうちのいずれか一つによって前記ダウンカウンタのカウント値と対応するクラスカウンタのカウント値との一致が検出されたとき、前記ダウンカウンタのカウント動作を停止させる、請求項6および7のいずれか一つに記載のk近傍法連想メモリ。
【請求項9】
前記最大カウンタ検出回路が、2入力1出力の複数の最大値選出回路がツリー状に接続されてなり、リーフノードの複数の最大値選出回路に前記X個のクラスカウンタの各カウント値および各クラスカウンタの識別番号を結合した各信号が入力され、ルートノードの最大値選出回路から前記X個のクラスカウンタの最大カウント値およびそのクラスカウンタの識別番号を結合した信号を出力するトーナメント回路であり、
前記最大値選出回路が、第1のクラスカウンタのカウント値および前記第1のクラスカウンタの識別番号を結合した第1の信号、および第2のクラスカウンタのカウント値および前記第2のクラスカウンタの識別番号を結合した第2の信号を受け、前記第1および第2のクラスカウンタのうちカウント値が大きい方のクラスカウンタのカウント値およびそのクラスカウンタの識別番号を結合した第3の信号を出力する、請求項6および7のいずれか一つに記載の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近傍法連想メモリを提供することを目的とする。
【課題を解決するための手段】
【0009】
本発明の一局面に従ったk近傍法連想メモリは、R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになったことを検出し、そのときの前記R個のマッチ信号を保持するk近傍検索回路と、前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから前記k近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、前記k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている。
【0010】
これによると、クロックカウント式連想メモリによって検索データと各参照データとの距離がクロック数に変換されて、距離に応じたタイミングで各参照データに対応するマッチ信号がアクティブとなり、k近傍検索回路によってより先にアクティブになったk個のマッチ信号が検出および保持され、k近傍クラスタリング回路によって当該k個のマッチ信号に対応するk個のクラスデータをクラス別に分類した場合にデータ数が最大となるクラスが判定される。このようにして、k近傍法に基づいた検索データのクラス分けが実現される。
【発明の効果】
【0011】
本発明によると、LSI上にk近傍法を効果的に実装することができる。
【図面の簡単な説明】
【0012】
【図1】図1は、本発明の一実施形態に係るk近傍法連想メモリの概略構成図である。
【図2】図2は、一例に係るクロックカウント式連想メモリの概略構成図である。
【図3】図3は、一例に係る距離/クロック数変換回路の概略構成図である。
【図4】図4は、一例に係るカウンタ一致検出回路の概略構成図である。
【図5】図5は、一例に係るマッチ信号のタイミングチャートである。
【図6】図6は、一例に係るマッチ信号カウント回路の概略構成図である。
【図7】図7は、一例に係るk-マッチ信号数一致検出回路の概略構成図である。
【図8】図8は、一例に係るマッチ信号保持回路の概略構成図である。
【図9】図9は、一例に係るクラスデータメモリ、クラスカウンタ、およびクラス識別回路の概略構成図である。
【図10】図10は、一例に係るマッチ信号検出回路の概略構成図である。
【図11】図11は、一例に係る最大カウンタ検出回路の概略構成図である。
【図12】図12は、別例に係る最大カウンタ検出回路の概略構成図である。
【図13】図13は、一例に係る最大値選出回路の概略構成図である。
【発明を実施するための形態】
【0013】
以下、図面を参照しながら本発明を実施するための形態について説明する。なお、本発明は、以下の実施形態に限定されるものではない。

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

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

【0016】
k近傍検索回路20は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになったことを検出し、そのときのR個のマッチ信号を保持する回路である。

【0017】
k近傍クラスタリング回路30は、R個の参照データのそれぞれのクラスを表すR個のクラスデータ(クラスデータ1,クラスデータ2,…,クラスデータR)からk近傍検索回路20が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、これらk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定する回路である。

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

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

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

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

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

【0023】
参照データ保存回路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ビットを保存する。

【0024】
距離演算回路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における参照データと検索データとの距離の演算は、並列に行われる。

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

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

【0027】
【数1】
JP2015011907A1_000003t.gif

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

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

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

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

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

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

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

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

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

【0037】
バッファ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へ出力する。

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

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

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

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

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

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

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

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

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

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

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

【0049】
バッファ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)が出力される。

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

【0051】
クロック数変換回路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が出力される。

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

【0053】
距離/クロック数変換回路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の二乗値の和を表している。

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

【0055】
【数2】
JP2015011907A1_000004t.gif

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

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

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

【0059】
≪k近傍検索回路20の構成例≫
図1に戻り、k近傍検索回路20は、マッチ信号カウント回路21と、k-マッチ信号数一致検出回路22と、マッチ信号保持回路23とを含む。

【0060】
マッチ信号カウント回路21は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号のうちアクティブになったマッチ信号の数をカウントする回路である。

【0061】
図6は、一例に係るマッチ信号カウント回路21の概略構成を示す。マッチ信号カウント回路21は、複数の加算器をツリー状に接続した加算器ツリー回路として構成することができる。加算器ツリー回路のリーフノードにはR/2個の半加算器(HA)211が配置される。各加算器211にはR個のマッチ信号のうちの2ビットが入力される。例えば、図6の左端の加算器211には参照データ1に対応するマッチ信号Mと参照データ2に対応するマッチ信号Mが入力され、右端の加算器211には参照データR-1に対応するマッチ信号MR-1と参照データRに対応するマッチ信号Mが入力される。

【0062】
加算器ツリー回路の2段目にはR/2個の2ビットの桁上げ伝播加算器(2bit-RCA)212が配置される。各加算器212には前段(リーフノード)の2個の加算器211からそれぞれ2ビット出力が入力される。

【0063】
加算器ツリー回路の3段目にはR/2個の3ビットの桁上げ伝播加算器(3bit-RCA)213が配置される。各加算器213には前段(第2段目)の2個の加算器212からそれぞれ3ビット出力が入力される。

【0064】
加算器ツリー回路のL段目のルートノードには1個のLビットの桁上げ伝播加算器(Lbit-RCA)21Lが配置される。加算器21Lには前段(L-1段目)の2個の加算器からそれぞれLビット出力が入力される。

【0065】
加算器21LからはL+1ビットのNMS(Number of Match Signals)が出力される。NMSが表す値は、R個のマッチ信号M~Mのうちアクティブになったマッチ信号の数に相当する。

【0066】
上記構成のマッチ信号カウント回路21によると、複数のマッチ信号が同時にアクティブになっても、それらマッチ信号の数を正確にカウントすることができる。

【0067】
また、マッチ信号カウント回路21はk近傍法連想メモリ100の構成要素の中で最長の遅延時間を有する回路であるが、上記のようにマッチ信号カウント回路21を加算器ツリー回路として構成することにより、遅延時間をマッチ信号の総数の対数オーダーに抑えることができる。したがって、マッチ信号カウント回路21の遅延時間は実用上問題とならない程度のものである。

【0068】
図1に戻り、k-マッチ信号数一致検出回路22は、マッチ信号カウント回路21のカウント値がkに一致したことを検出する回路である。なお、マッチ信号カウント回路21のカウント値は上記のNMSによって表され、また、kは外部から与えることができる。

【0069】
図7は、一例に係るk-マッチ信号数一致検出回路22の概略構成を示す。本例において、kは4ビット値として与えられるものとする。k-マッチ信号数一致検出回路22は、kとNMSの対応するビットどうしを比較する4個の1ビット一致検出回路221を含む。

【0070】
各1ビット一致検出回路221は、1ビット入力A,B、および1ビット出力X,Yを有する回路である。AにNMSの対応ビットが、Bにkの対応ビットが、それぞれ入力される。入力A,B、出力X,Yの真理値表は表1に示す通りである。

【0071】
【表1】
JP2015011907A1_000005t.gif

【0072】
すなわち、各1ビット一致検出回路221は、NMSの対応ビットとkの対応ビットが一致すればYに1を出力し、NMSの対応ビットがkの対応ビットよりも大きければXに1を出力する。

【0073】
kの最上位ビット以外の1ビット一致検出回路221において、NMSの対応ビットとそれよりも上位ビットの1ビット一致検出回路221の出力Yとの論理積がAに入力されるようになっている。すなわち、MSNの対応ビットがそれよりも上位ビットの1ビット一致検出回路221の出力Yによってマスクされるようになっている。このため、上位ビットにおいてNMSとkとが一致しない限り、NMSとkの下位ビットどうしの一致検出は行われない。これは、NMSが時間とともに増加することに鑑み、NMSがkよりも小さい間はNMSとkの下位ビットどうしの一致を検出する必要はなく、上位ビットから順に一致を検出すればよいためである。このように、上位ビットの一致を見て下位ビットに進むという方式を採用することにより、1ビット一致検出回路221の不要な動作を抑制して消費電力を低減することができる。

【0074】
各1ビット一致検出回路221の出力YはANDゲート222に入力され、全出力Yの論理積が演算される。kとNMSとが完全一致したとき、ANDゲート222の出力がHレベルに遷移する。ANDゲート222の出力はDフリップフロップ224にクロック入力(CLK)される。Dフリップフロップ224には検索開始信号SBがデータ入力(D)されており、検索開始信号SBがHレベルの場合において、Dフリップフロップ224はクロック入力に応じてHレベルの検索開始信号SBを保持する。Dフリップフロップ224の出力(Q)は停止信号stopとして出力される。

【0075】
後述するように、停止信号stopはマッチ信号保持回路23によるマッチ信号の保持のタイミング信号として利用することができる。また、停止信号stopはクロックカウント式連想メモリ10の動作を停止させる制御信号として利用することができる。アクティブのマッチ信号の数がk個に達した後はクロックカウント式連想メモリ10はもはや動作しなくてもよい。したがって、クロックカウント式連想メモリ10において、例えば、停止信号stopを受けたときにクロック信号CLKの供給を遮断するように構成することで、クロックカウント式連想メモリ10の不要な動作を抑制して消費電力を低減することができる。

【0076】
各1ビット一致検出回路221の出力XはORゲート223aに入力され、全出力Xの論理和が演算される。1ビット一致検出回路221の少なくとも一つにおいてNMSの対応ビットがkの対応ビットよりも大きくなれば、ORゲート223aの出力がHレベルに遷移する。また、NMSの残りの全上位ビットはORゲート223bに入力され、これらビットの論理和が演算される。NMSの残りの全上位ビットにおいて少なくとも1ビットがHレベルとなった場合、ORゲート223bの出力がHレベルに遷移する。ORゲート223cは、ORゲート223aおよびORゲート223bの各出力の論理和を演算する。ORゲート223cの出力は、異常信号abnormalとして出力される。すなわち、NMSがkを超えたとき、異常信号abnormalが出力される。異常信号abnormalは、k近傍検索のやり直し指示などに利用することができる。また、異常信号abnormalはDフリップフロップ224にクロック入力(CLK)される。これにより、異常信号abnormalの出力に合わせて停止信号stopが出力される。

【0077】
異常信号abnormalは、Dフリップフロップ224の出力(Q)の反転論理によってマスクされる。すなわち、異常信号abnormalが出力される前にNMSとKが完全一致して停止信号stopが出力された場合、その後NMSがkを超えても異常信号abnormalが出力されないようになっている。

【0078】
Dフリップフロップ224のリセットを行うために、k近傍法連想メモリ100の共通に使用されるリセット信号RSTが入力される。

【0079】
図1に戻り、マッチ信号保持回路23は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号を受け、k-マッチ信号数一致検出回路22によってマッチ信号カウント回路21のカウント値がkに一致したことが検出されたときのR個のマッチ信号を保持する。

【0080】
図8は、一例に係るマッチ信号保持回路23の構成を示す。マッチ信号保持回路23は、クロックカウント式連想メモリ10から出力されるR個のマッチ信号M~Mのそれぞれを保持するR個のDフリップフロップ231を含む。各Dフリップフロップ231において、マッチ信号がデータ入力(D)されるとともに、停止信号stopがクロック入力(CLK)される。R個のDフリップフロップ231のそれぞれの出力(Q)は、R個のマッチ信号M~Mとしてk近傍クラスタリング回路30に入力される。なお、図示していないが、各Dフリップフロップ231はリセット信号RSTを受けることで初期状態にリセットされる。

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

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

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

【0084】
クラス識別回路33は、k近傍検索回路20(より詳細にはマッチ信号保持回路23)が保持するアクティブのk個のマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータをクラスデータメモリ31から読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタ32をカウントアップする回路である。

【0085】
図9は、一例に係るクラスデータメモリ31、クラスカウンタ32、およびクラス識別回路33の概略構成を示す。

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

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

【0088】
クラスデータ保存回路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ビットを保存する。

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

【0090】
クラス識別回路33は、R個のマッチ信号検出回路331と、デマルチプレクサ332と、バッファ333とを含む。動作開始信号startがHレベルに遷移することで、バッファ333がクラス識別回路33にクロック信号CLKを供給する。これにより、クラス識別回路33は動作を開始する。また、クラス識別回路33によるクラス識別動作が終了すると終了信号endがHレベルに遷移する。

【0091】
R個のマッチ信号検出回路331は、k近傍検索回路20(より詳細にはマッチ信号保持回路23)が保持するR個のマッチ信号のそれぞれに対応して設けられている。各マッチ信号検出回路331は、対応するマッチ信号がアクティブであることを検出してクラスデータメモリ31に当該マッチ信号に対応するクラスデータを選択する選択信号actを出力する回路である。

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

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

【0094】
図10は、一例に係るマッチ信号検出回路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となる。

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

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

【0097】
レジスタ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レベルとなる。

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

【0099】
上記構成のクラスデータメモリ31、クラスカウンタ32、およびクラス識別回路33によると、マッチ信号保持回路23が保持するマッチ信号の総数に拘わらず、kクロック周期で、アクティブのk個のマッチ信号に対応するクラスのカウントが完了する。したがって、k近傍クラスタリング処理を高速に行うことができる。

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

【0101】
図11は、一例に係る最大カウンタ検出回路34の概略構成を示す。最大カウンタ検出回路34は、ダウンカウンタ341と、X個の一致検出回路342とを含む。ダウンカウンタ341は、クロック信号CLKを受けて、初期値からカウント値をカウントダウンする回路である。ダウンカウンタ341へはバッファ343を介してクロック信号CLKが供給される。バッファ343は、クラス識別回路33によるクラス識別動作が終了したときに出力される終了信号endを受けて、ダウンカウンタ341へクロック信号CLKを供給する。

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

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

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

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

【0106】
最大値選出回路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を出力してもよい。

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

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

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

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

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

【0112】
なお、本実施形態では、k近傍検索回路20において、クロックカウント式連想メモリ10から出力されるR個のマッチ信号を各1ビット情報として保存するため、距離情報が欠落してしまう。そこで、例えば、k近傍検索回路20にカウンタを設けて、各マッチ信号がアクティブになるまでの時間情報(すなわち時間換算した距離情報)を保持するようにしてもよい。その場合、時間情報を用いて、検索データにより距離の近い参照データの重みを大きくするようにクラスデータの重み付けを行って、より高度なクラス判別を行うことができる。また、アクティブとなったk個のマッチ信号に対応する参照データのうち、検索データとの距離が閾値以上のものは除外してk個以下でk近傍法を適用することも可能である。
【産業上の利用可能性】
【0113】
本発明に係るk近傍法連想メモリは、LSI上にk近傍法を効果的に実装することができるため、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションに有用である。
【符号の説明】
【0114】
100 k近傍法連想メモリ
10 クロックカウント式連想メモリ
20 k近傍検索回路
31 マッチ信号カウント回路
211,212,213,21L 加算器
22 k-マッチ信号数一致検出回路
23 マッチ信号保持回路
30 k近傍クラスタリング回路
31 クラスデータメモリ
32 クラスカウンタ
33 クラス識別回路
331 マッチ信号検出回路
34 最大カウンタ検出回路
341 ダウンカウンタ
342 一致検出回路
345 最大値選出回路
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12