Top > Search of International Patents > K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY

K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY

Foreign code F150008293
Posted date Apr 3, 2015
Country WIPO
International application number 2014JP003809
International publication number WO 2015011907
Date of international filing Jul 17, 2014
Date of international publication Jan 29, 2015
Priority data
  • P2013-154887 (Jul 25, 2013) JP
Title K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY
Abstract A k-nearest neighbors associative memory (100) is provided with: a clock count type associative memory (10) which retains R pieces of reference data and outputs, for each of the R pieces of reference data, a match signal that becomes active when the clock count corresponding to the distance between that piece of reference data and given search data has been reached; a k-nearest neighbors search circuit (20) which detects when any K match signals among the R match signals output from the clock count type associative memory have become active, and then holds the R match signals; and a k-nearest neighbors clustering circuit (30) which selects k pieces of class data, each of which is among R pieces of class data representing the classes of the R pieces of reference data and is associated with one of the k active match signals held by the k-nearest neighbors search circuit, and determines the class indicated by the largest number of pieces of data when the k pieces of class data are classified by class.
Scope of claims (In Japanese)[請求項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近傍法連想メモリ。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • HIROSHIMA UNIVERSITY
  • Inventor
  • MATTAUSCH HANS JUERGEN
  • AKAZAWA TOSHINOBU
  • YAMASAKI SHOGO
IPC(International Patent Classification)
Specified countries National States: 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 UZ VC VN ZA ZM ZW
ARIPO: BW GH GM KE LR LS MW MZ NA RW SD SL SZ TZ UG ZM ZW
EAPO: AM AZ BY KG KZ RU TJ TM
EPO: 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
OAPI: BF BJ CF CG CI CM GA GN GQ GW KM ML MR NE SN TD TG

PAGE TOP

close
close
close
close
close
close