説明

連想メモリ

【課題】誤検索を抑制可能な連想メモリを提供する。
【解決手段】連想メモリは、R個の距離/時間変換回路DT〜DTを備える。R個の距離/時間変換回路DT〜DTの各々は、NAND回路40と、Nビットステージ41〜4kとを含む。Nビットステージ41〜4kは、それぞれ、参照データと検索データとの間の距離が大きいほど、より長い遅延時間によってNAND回路40からの信号を遅延して発振信号を発振し、参照データと検索データとの間の距離が小さいほど、より短い遅延時間によってNAND回路40からの信号を遅延して発振信号を発振する。そして、距離/時間変換回路DT〜DTから出力されたR個の発振信号のうち、最も早く変化する発振信号がWinner行の発振信号として検出される。


Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298

【特許請求の範囲】
【請求項1】
各々がW(Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存回路と、
Wビットのビット長を有し、かつ、検索対象である検索データを前記R個の参照データの各々とビット毎に比較し、各々が前記検索データと前記参照データとの間の距離を表し、かつ、Wビットのビット値からなるR個の距離信号を前記検索データと前記R個の参照データとの比較結果として出力する比較回路と、
前記R個の距離信号に対応して設けられ、各々がk(kは、W/Nまたは(W/N)+1を満たす整数、Nは、3以上の整数)個の遅延回路をリング状に接続した発振回路を含むR個の変換回路と、
前記R個の距離信号および前記R個の変換回路に対応して設けられ、各々がk個の経路選択回路を含むR個の選択回路と、
前記R個の変換回路から出力されたR個の出力信号のうち、最も早く変化する出力信号を検出し、その検出した出力信号を前記検索データに最も類似した参照データを示す信号として出力する検出回路とを備え、
前記R個の選択回路の各々は、対応するWビットの距離信号によって表される距離が小さいほど前記k個の遅延回路における遅延時間が短くなり、かつ、前記対応するWビットの距離信号によって表される距離が大きいほど前記k個の遅延回路における遅延時間が長くなるように前記k個の遅延回路の各々におけるN+1個の遅延経路から1つの遅延経路を選択するためのk個の選択信号を前記対応するWビットの距離信号に基づいて生成し、その生成したk個の選択信号を前記対応する変換回路へ出力し、
前記R個の変換回路の各々は、前記対応する選択回路から前記k個の選択信号を受けると、その受けたk個の選択信号によって選択されたk個の遅延経路を介して発振し、その発振した発振信号を出力信号として前記検出回路へ出力する、連想メモリ。
【請求項2】
前記R個の変換回路から出力されたR個の出力信号を分周し、その分周したR個の出力信号を前記検出回路へ出力する分周器をさらに備える、請求項1に記載の連想メモリ。
【請求項3】
前記k個の経路選択回路は、前記k個の遅延回路に対応して設けられ、
前記k個の経路選択回路の各々は、前記k個の経路選択回路が含まれる選択回路へ出力されるWビットの距離信号のうち、Nビットの距離信号を受け、その受けたNビットの距離信号によって表される距離が小さいほど遅延時間が短くなり、かつ、前記受けたNビットの距離信号によって表される距離が大きいほど遅延時間が長くなるように前記N+1個の遅延経路から1つの遅延経路を選択するための選択信号を生成し、その生成した選択信号を前記対応する遅延回路へ出力し、
前記k個の遅延回路の各々は、前記N+1個の遅延経路を含み、前記対応する経路選択回路から前記選択信号を受けると、その受けた選択信号によって選択された前記1つの遅延経路によって信号を遅延して出力する、請求項1または請求項2に記載の連想メモリ。
【請求項4】
前記k個の遅延回路の各々は、
入力ノードと、
出力ノードと、
前記入力ノードと前記出力ノードとの間に接続された第1のゲートからなる第1の遅延経路と、
各々が、前記入力ノード側に配置された第2のゲートと、前記出力ノードに接続された第3のゲートと、前記第2のゲートと前記第3のゲートとの間に接続された遅延器とからなるN個の遅延経路とを含み、
前記N個の遅延経路のうち、前記第1の遅延経路に隣接する第2の遅延経路の前記第2のゲートは、前記入力ノードに接続され、
前記N個の遅延経路のうち、前記第2の遅延経路以外のN−1個の遅延経路に含まれるN−1個の前記第2のゲートは、それぞれ、前記第1の遅延経路側で隣接する遅延経路に含まれる前記遅延器の出力側に接続され、
前記第1のゲート、前記N個の第2のゲートおよび前記N個の第3のゲートは、前記Nビットの距離信号によって表される距離がd(d=0,1,2,・・・,N)であるとき前記入力ノードからi個の前記遅延器を介して前記出力ノードへ信号が出力されるように前記選択信号によって開閉される、請求項3に記載の連想メモリ。
【請求項5】
前記k個の経路選択回路の各々は、
直列に接続されたN−1個の第1の選択信号生成回路と、
前記N−1個の第1の選択信号生成回路のうち、入力側からN−1番目の第1の選択信号生成回路から出力されたN個の出力信号に基づいて、前記第1の遅延経路から最も離れた位置に配置された第N+1番目の遅延経路に含まれる前記第3のゲートと前記第1のゲートとを除いたN−2個の前記第3のゲートを開閉するN−2個の第1の選択信号と、前記N個の第2のゲートを開閉するN個の第2の選択信号とを生成する第2の選択信号生成回路とを含み、
前記N−1個の第1の選択信号生成回路は、
前記Wビットの距離信号のうちの第1および第2番目のビット値に基づいて2個の選択信号を生成する第1の信号生成回路と、
各々が、m(mは2≦m≦N−1を満たす整数)個の選択信号と、前記Wビットの距離信号のうちの第n(nは3≦n≦Nを満たす整数)番目のビット値とに基づいてm+1個の選択信号を生成するN−2個の第2の信号生成回路とを含み、
前記N−2個の第2の信号生成回路の各々は、前記第1の信号生成回路、または前記第1の信号生成回路側の第2の信号生成回路から前記m個の選択信号を受け、
前記第2の選択信号生成回路は、前記N−2個の第1の選択信号を前記N−2個の第3のゲートへ出力し、前記N個の第2の選択信号を前記N個の第2のゲートへ出力し、前記第2の遅延経路に含まれる前記第2のゲートへ出力する前記第2の選択信号の反転信号を前記第1のゲートへ出力し、前記第N+1番目の遅延経路に含まれる前記第2のゲートへ出力する前記第2の選択信号と同じ選択信号を前記第N+1番目の遅延経路に含まれる前記第3のゲートへ出力する、請求項4に記載の連想メモリ。
【請求項6】
K(Kは2以上の整数)ビットのビット長を有する参照データを列方向にW(Wは2以上の整数)個配列し、かつ、行方向にR(Rは2以上の整数)個配列してW×R個の参照データを保存する参照データ保存回路と、
Kビットのビット長を有し、かつ、検索対象である検索データを前記W×R個の参照データの各々とビット毎に比較し、各々が前記検索データと前記参照データとの間の距離を表し、かつ、各々がKビットのビット値からなるW×R個の距離信号を前記検索データと前記W×R個の参照データとの比較結果として出力する比較回路と、
各々が前記列方向に配列されたW個の参照データと前記検索データとの比較結果を示すR個の距離信号に対応して設けられたR個の変換回路と、
前記R個の距離信号および前記R個の変換回路に対応して設けられたR個の選択回路と、
前記R個の変換回路から出力されたR個の出力信号のうち、最も早く変化する出力信号を検出し、その検出した出力信号を前記検索データに最も類似した参照データを示す信号として出力する検出回路とを備え、
前記R個の選択回路の各々は、前記R個の距離信号のうち、対応する距離信号のW×K個のビット値に基づいて、前記参照データと前記検索データとの同位ビット同士が異なるとき第1の遅延時間を有する第1の遅延経路を選択し、前記同位ビット同士が一致するとき前記第1の遅延時間よりも短い第2の遅延時間を有する第2の遅延経路を選択するための選択信号を生成し、
前記R個の変換回路の各々は、前記対応する選択回路から受けた選択信号によって選択された前記第1の遅延経路または前記第2の遅延経路を用いて、前記参照データと前記検索データとの最上位ビット同士の距離を示す第1の距離信号から前記参照データと前記検索データとの最下位ビット同士の距離を示す第2の距離信号に向かって遅延時間が順次短くなり、かつ、周波数が順次高くなるように前記第1の距離信号から前記第2の距離信号に向かって前記距離信号を発振信号に順次変換し、その変換した発振信号を出力信号として前記検出回路へ出力する、連想メモリ。
【請求項7】
前記R個の変換回路の各々は、
各々がリング状に接続されたW個の遅延回路を含み、前記参照データおよび前記検索データのK個のビット位に対応して配置されたK個の発振回路と、
各々が隣接する2つの発振回路間に配置され、前記K個の発振回路を直列に接続するK−1個の選択器と、
前記直列に接続されたK個の発振回路のうちの一方端の発振回路と他方端の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記一方端の発振回路へ出力する活性化回路とを含み、
前記K−1の選択器の各々は、前記2つの発振回路のうちの一方の発振回路の出力信号を入力信号として前記一方の発振回路へ出力するとともに、前記一方の発振回路への出力回数が所望回数に達すると、前記一方の発振回路の出力信号を前記2つの発振回路のうちの他方の発振回路へ出力し、
前記W個の遅延回路の各々は、前記第1および第2の遅延経路を有し、前記選択信号によって選択された前記第1または第2の遅延経路を用いて入力信号を遅延して隣接する遅延回路へ出力し、
前記K個の発振回路は、前記一方端の発振回路から前記他方端の発振回路へ向かうに従って前記第1の遅延経路における前記第1の遅延時間が順次短くなっており、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、各選択信号が各ビット位に対応して配置された発振回路へ出力されるように前記生成したK個の選択信号をそれぞれ前記K個の発振回路へ出力する、請求項6に記載の連想メモリ。
【請求項8】
前記R個の変換回路の各々は、
各々がリング状に接続されたW個の遅延回路を含み、前記参照データおよび前記検索データのK個のビット位に対応して配置されたK個の発振回路と、
各々が隣接する2つの発振回路間に配置され、前記K個の発振回路を直列に接続するK−1個の分周器と、
前記直列に接続されたK個の発振回路のうちの一方端の発振回路と他方端の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記一方端の発振回路へ出力する活性化回路とを含み、
前記K−1の分周器の各々は、前記2つの発振回路のうちの一方の発振回路の出力信号を分周して前記一方の発振回路へ出力するとともに、分周回数が所望回数に達すると、分周後の信号を前記2つの発振回路のうちの他方の発振回路へ出力し、
前記W個の遅延回路の各々は、前記第1および第2の遅延経路を有し、前記選択信号によって選択された前記第1または第2の遅延経路を用いて入力信号を遅延して隣接する遅延回路へ出力し、
前記W個の遅延回路に含まれるW個の前記第1の遅延経路におけるW個の前記第1の遅延時間は、相互に同じであり、
前記K−1個の分周器は、前記一方端の発振回路の出力信号を受ける分周器から前記他方端の発振回路へ信号を出力する分周器に向かうに従って分周回数が減少し、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、各選択信号が各ビット位に対応して配置された発振回路へ出力されるように前記生成したK個の選択信号をそれぞれ前記K個の発振回路へ出力する、請求項6に記載の連想メモリ。
【請求項9】
前記R個の変換回路の各々は、
各々が前記第1および第2の遅延経路を有し、リング状に接続されたW個の遅延回路を含む第1の発振回路と、
各々が前記第1および第2の遅延経路を有し、リング状に接続されたW個の遅延回路を含む第2の発振回路と、
前記第1の発振回路の出力信号を所望回数だけ分周し、その分周した信号を前記第2の発振回路へ出力する第1の分周器と、
前記第2の発振回路の出力信号を所望回数だけ分周し、その分周した信号を前記第1の発振回路へ出力する第2の分周器と、
前記第2の分周器と前記第1の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記第1の発振回路へ出力する活性化回路とを含み、
前記第1の分周器は、前記参照データと前記検索データとの最上位ビットから奇数番目のビット同士の比較結果を示す第1の距離信号を変換した発振信号を前記第1の発振回路から受け、前記第1の距離信号がより下位のビット同士の比較結果を示すほど少ない回数だけ前記受けた発振信号を分周して前記第2の発振回路へ出力し、
前記第2の分周器は、前記参照データと前記検索データとの最上位ビットから偶数番目のビット同士の比較結果を示す第2の距離信号を変換した発振信号を前記第2の発振回路から受け、前記第2の距離信号がより下位のビット同士の比較結果を示すほど少ない回数だけ前記受けた発振信号を分周して前記第1の発振回路へ出力し、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、前記第1の距離信号に基づいて生成された選択信号が前記第1の発振回路へ出力され、前記第2の距離信号に基づいて生成された選択信号が前記第2の発振回路へ出力されるように前記K個の選択信号を交互に前記第1および第2の発振回路へ出力する、請求項6に記載の連想メモリ。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate

【図44】
image rotate

【図45】
image rotate


【公開番号】特開2013−101729(P2013−101729A)
【公開日】平成25年5月23日(2013.5.23)
【国際特許分類】
【出願番号】特願2011−243733(P2011−243733)
【出願日】平成23年11月7日(2011.11.7)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 1.発行者名 社団法人 電子情報通信学会 2.刊行物名、巻数、号数 電子情報通信学会技術研究報告 信学技報 Vol.111 No.40 3.発行日 平成23年 5月11日
【国等の委託研究の成果に係る記載事項】(出願人による申告)平成22年度、独立行政法人科学技術振興機構 科学技術コモンズ 産業技術力強化法第19条の適用を受ける特許出願
【出願人】(504136568)国立大学法人広島大学 (924)