TOP > 国内特許検索 > 連想メモリ

連想メモリ

国内特許コード P130008705
整理番号 S2012-1038-N0,12070
掲載日 2013年3月18日
出願番号 特願2013-025465
公開番号 特開2014-154196
登録番号 特許第6085187号
出願日 平成25年2月13日(2013.2.13)
公開日 平成26年8月25日(2014.8.25)
登録日 平成29年2月3日(2017.2.3)
発明者
  • マタウシュ ハンスユルゲン
  • 佐々木 静龍
  • 赤澤 智信
出願人
  • 国立大学法人広島大学
発明の名称 連想メモリ
発明の概要 【課題】ユークリッド距離を用いた場合でも正確に類似検索を行うことが可能な連想メモリを提供すること。
【解決手段】連想メモリ100は、M×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データと、M×Wビットのビット長を有する検索データとのマンハッタン距離を算出する距離演算回路DP11~DPRWと、距離/クロック数変換回路DC~DCとを備える。距離/クロック数変換回路DC~DCの各々は、対応する距離演算回路で算出されるマンハッタン距離を用い、参照データと検索データとのユークリッド距離に一致するクロック数を検出する。距離/クロック数変換回路は、参照データについて、検索データとのユークリッド距離と一致するクロック数を検出したタイミングを示すタイミング信号を出力する。
【選択図】図1
従来技術、競合技術の概要



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





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





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





連想メモリを実現する手段として(1)ディジタル方式による実現方法(非特許文献1)、(2)アナログ方式による実現方法および(3)ディジタル・アナログ融合方式(非特許文献2)等が提案されている。

産業上の利用分野



この発明は、連想メモリに関するものである。

特許請求の範囲 【請求項1】
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すR×W個の絶対値差を、前記検索データと前記参照データの距離として算出する第1距離算出手段と、
前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記R個の参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。

【請求項2】
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記各参照データにつき、前記W個の絶対値差の各々に一致する回数だけ、前記絶対値差と一致するクロック数を検出する処理を繰り返すことにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。

【請求項3】
前記各参照データにつき、前記第1距離算出手段で算出された前記W個の絶対値差の各々の二乗値を算出することにより、前記検索対象の検索データと前記参照データとの距離として、前記W個の絶対値差の二乗値を算出する第2距離算出手段を更に備え、
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記参照データごとに、前記第2距離算出手段で算出された前記W個の前記絶対値差の二乗値の和に一致するクロック数を検出することにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。

【請求項4】
マンハッタン距離とユークリッド距離のいずれかの距離を選択する選択手段を備え、
前記タイミング信号出力手段は、
(1)前記選択手段によって前記マンハッタン距離が選択された場合、前記各参照データにつき、前記W個の絶対値差の和に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力し、
(2)前記選択手段によって前記ユークリッド距離が選択された場合、前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力する
請求項1から請求項3のいずれか一項に記載の連想メモリ。



【請求項5】
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとのR×W個の距離を算出する距離算出手段と、
前記参照データごとに、前記距離算出手段で算出された距離を表すビットのうち、設定された対象ビットの値と一致するクロック数を検出したタイミングで一致検出信号を出力する一致検出手段と、
前記各参照データについて算出された前記距離を表す最上位ビットから順に、予め定められたビット単位に前記対象ビットを設定し、いずれかの前記参照データについて、前記対象ビットに対する前記一致検出信号が出力される毎に、前記対象ビットを拡張するビット設定手段と、
前記各参照データについて、前記距離を表す全てのビットに対する前記一致検出信号が出力されたタイミングを示すタイミング信号を出力する処理を、R個の前記参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
国際特許分類(IPC)
画像

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

JP2013025465thum.jpg
出願権利状態 登録


PAGE TOP

close
close
close
close
close
close
close