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

k近傍法連想メモリ

国内特許コード P170013649
整理番号 14073
掲載日 2017年1月25日
出願番号 特願2015-016977
公開番号 特開2016-143430
出願日 平成27年1月30日(2015.1.30)
公開日 平成28年8月8日(2016.8.8)
発明者
  • マタウシュ ハンスユルゲン
  • 山崎 翔悟
出願人
  • 国立大学法人広島大学
発明の名称 k近傍法連想メモリ
発明の概要 【課題】k近傍法を効果的に実現するk近傍法連想メモリを提供する。
【解決手段】k近傍法連想メモリ100は、R個の参照データを保持しており、R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリ10と、クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、R個のマッチ信号の少なくとも一つがアクティブになるごとに、R個の参照データのそれぞれのクラスを表すR個のクラスデータからアクティブになった少なくとも一つの、k個のマッチ信号のそれぞれに対応するクラスデータを選択し、選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路30とを備えている。
【選択図】図1
従来技術、競合技術の概要


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



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



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



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

産業上の利用分野


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

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

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

JP2015016977thum.jpg
出願権利状態 公開


PAGE TOP

close
close
close
close
close
close
close