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

k近傍法連想メモリ UPDATE 外国出願あり

国内特許コード P170013665
整理番号 F13011-JP
掲載日 2017年1月25日
出願番号 特願2015-528142
出願日 平成26年7月17日(2014.7.17)
国際出願番号 JP2014003809
国際公開番号 WO2015011907
国際出願日 平成26年7月17日(2014.7.17)
国際公開日 平成27年1月29日(2015.1.29)
優先権データ
  • 特願2013-154887 (2013.7.25) JP
発明者
  • マタウシュ ハンスユルゲン
  • 赤澤 智信
  • 山崎 翔悟
出願人
  • 国立大学法人広島大学
発明の名称 k近傍法連想メモリ UPDATE 外国出願あり
発明の概要 k近傍法連想メモリ(100)は、R個の参照データを保持しており、R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリ(10)と、クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかK個のマッチ信号がアクティブになったことを検出し、そのときのR個のマッチ信号を保持するk近傍検索回路(20)と、R個の参照データのそれぞれのクラスを表すR個のクラスデータからk近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路(30)とを備えている。
従来技術、競合技術の概要


近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated circuit)上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。



パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。



前者は、CAM(Content Addressable Memory)と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ(Associative Memory)と呼ぶ。



連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている(非特許文献1参照)。また、連想メモリにk近傍探索を取り入れたものが知られている(非特許文献2参照)。

産業上の利用分野


本発明は、連想メモリに関し、特に、k近傍法を効果的に実現する連想メモリに関する。

特許請求の範囲 【請求項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近傍法連想メモリ。
国際特許分類(IPC)
画像

※ 画像をクリックすると拡大します。

JP2015528142thum.jpg
出願権利状態 公開


PAGE TOP

close
close
close
close
close
close
close