連想メモリ
【課題】誤検索を抑制できる連想メモリを提供する。
【解決手段】
連想メモリ１００内の保存回路Ｓ１は参照データを保存する。比較回路Ｃ１は外部から検索データを受け、参照データと検索データとの距離（たとえばハミング距離）を求める。発振回路ＯＣ１は、比較回路Ｃ１が求めた距離に応じた発振周波数を有するパルス信号Ｐ１を出力する。同様に、発振回路ＯＣ２〜ＯＣＲは、対応する保存回路Ｓ２〜ＳＲ内の参照データと検索データとの距離に応じた発振周波数を有するパルス信号Ｐ２〜ＰＲを出力する。
ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲを受ける。そして、最も発振周波数が高いパルス信号を出力した発振回路に対応する保存回路に保存された参照データを、検索データに最も類似した参照データ（Ｗｉｎｎｅｒ）に決定する。
【解決手段】
連想メモリ１００内の保存回路Ｓ１は参照データを保存する。比較回路Ｃ１は外部から検索データを受け、参照データと検索データとの距離（たとえばハミング距離）を求める。発振回路ＯＣ１は、比較回路Ｃ１が求めた距離に応じた発振周波数を有するパルス信号Ｐ１を出力する。同様に、発振回路ＯＣ２〜ＯＣＲは、対応する保存回路Ｓ２〜ＳＲ内の参照データと検索データとの距離に応じた発振周波数を有するパルス信号Ｐ２〜ＰＲを出力する。
ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲを受ける。そして、最も発振周波数が高いパルス信号を出力した発振回路に対応する保存回路に保存された参照データを、検索データに最も類似した参照データ（Ｗｉｎｎｅｒ）に決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最小距離検索機能を有する連想メモリに関する。
【背景技術】
【０００２】
画像圧縮及び画像認識の分野において、最小距離検索機能を有する連想メモリが注目されている。連想メモリはＷビット幅Ｒ個の参照データを記憶する（Ｗ及びＲは自然数）。データ列（検索データ）が入力されたとき、連想メモリは、複数の参照データの中から最も類似した（距離の近い）データを検索する。
【０００３】
入力されたデータ列と最も類似の参照データを見つけることは、パターンマッチングにおいて基本的な処理である（非特許文献１参照）。したがって、画像圧縮や画像認識等の情報処理において、最小距離検索連想メモリは有用である。最小距離検索連想メモリはたとえば、特許文献１に開示されている。さらに、ハミング距離、マンハッタン距離及びユークリッド距離の検索機能を有する全並列型の連想メモリが特許文献２、非特許文献２及び非特許文献３に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２８８９８５号公報
【特許文献２】特開２００５−２０９３１７号公報
【非特許文献】
【０００５】
【非特許文献１】D. R. Tveter, "The Pattern RecognitionBasis of Artificial Intelligence," Los Alamitos, CA: IEEE computersociety, 1998.
【非特許文献２】H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, "Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance," IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002.
【非特許文献３】H. J. Mattausch, N. Omori, S. Fukae, T.Koide and T. Gyohten, "Fully-Parrallel Pattern-Matching Engine with Dynamic Adaptibility to Hamming or ManhattanDistance," 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002.
【非特許文献４】M. Ikeda, et al., "Time-domain minimum-distance detector and its application to low-power coding schema on chip- interface," Proc. of ESSCIRC '97, pp.464-467, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の連想メモリは、メモリアレイ部と、Ｗｉｎｎｅｒ Ｌｉｎｅ−ｕｐ増幅回路（Winner Line-up Amplifier：以下、ＷＬＡという）と、Ｗｉｎｎｅｒ Ｔａｋｅ Ａｌｌ回路（以下、ＷＴＡという）とを備える。メモリアレイ部は、行列状に配置されたメモリセルを備える。メモリアレイ部の同じ行に配列された複数のメモリセルは、Ｗビット幅の参照データを記憶する。メモリアレイ部はさらに、各々が各行に対応した複数の比較回路を備える。比較回路は、対応する行のメモリセルに記憶された参照データと、外部から入力された検索データとの距離に応じた比較電流信号を生成する。
【０００７】
ＷＬＡ回路は、各々が各比較回路に対応した複数の電流電圧変換回路を備える。各電流電圧変換回路は、対応する比較回路から出力された比較電流信号を電圧に変換する。ＷＬＡ回路は、変換された複数の電圧のうち、電圧レベルが最も低い電圧をＷｉｎｎｅｒとして所定の電圧ＶＷに増幅する。そして、それ以外の電圧をＬｏｓｅｒとして所定の電圧ＶＬに増幅する。ここで、Ｗｉｎｎｅｒは、検索データに最も類似する参照データに対応する。そして、Ｌｏｓｅｒは、検索データに最も類似する参照データ以外の他の参照データに対応する。ＷＴＡ回路は、ＷＬＡ回路から受けた電圧をさらに増幅して出力する。連想メモリでは、電圧ＶＷに増幅された行のメモリセルに記憶された参照データが検索データに最も類似した参照データに決定される。
【０００８】
変換された複数の電圧を電圧ＶＷ及び電圧ＶＬに増幅するために、ＷＬＡ回路は、各行に対応して配置されたトランジスタ素子を用いて、各電圧が所定のしきい値電圧Ｖｒｅｆよりも大きいか否かを判定する。そして、しきい値電圧Ｖｒｅｆよりも小さい電圧を電圧ＶＷに増幅し、しきい値電圧Ｖｒｅｆよりも大きい電圧を電圧ＶＬに増幅する。
【０００９】
上述の電圧判定に用いられるトランジスタ素子の特性は、各行で一致している必要がある。しかしながら、トランジスタ素子の特性はどうしてもばらつく。特性が異なるトランジスタを電圧判定に用いれば、本来電圧ＶＷに増幅されないはずの行で、電圧ＶＷに増幅されてしまう場合が生じる。要するに、各行の比較電流信号を電圧に変換することで参照データを検索する従来の連想メモリでは、誤検索が生じる場合がある。
【００１０】
本発明の目的は、誤検索を抑制できる連想メモリを提供することである。
【課題を解決するための手段及び発明の効果】
【００１１】
本発明による連想メモリは、保存手段と、比較手段と、パルス生成手段と、決定手段とを備える。保存手段は、複数の参照データを保存する。比較手段は、入力された検索データと、複数の参照データの各々とを並列に比較して、検索データと参照データとの距離を、参照データごとに求める。パルス生成手段は、求めた距離に応じた周波数を有するパルス信号を参照データごとに生成する。決定手段は、生成された複数のパルス信号の周波数に基づいて、複数の参照データのうち、検索データに最も近い参照データを決定する。
【００１２】
本発明による連想メモリは、従来のように、参照データと検索データとの距離を電流値や電圧値に変換せず、距離に応じた発振周波数を有するパルス信号を生成する。距離を電流値や電圧値に変換するといったアナログ処理を行わないため、トランジスタ素子特性のばらつきに起因した誤検索が生じにくい。
【００１３】
好ましくは、パルス生成手段は、複数の参照データに対応した複数の発振手段を備える。各発振手段は、検索データと前記対応する参照データとの距離が小さいほど、周波数の高いパルス信号を出力する。決定手段は、発振周波数の最も高いパルス信号を出力した発振手段に対応した参照データを、検索データに最も近い参照データに決定する。
【００１４】
より好ましくは、決定手段はさらに、複数の発振手段に対応した複数の判定手段を備える。決定手段は、複数の判定手段のうち、発振手段からのパルス信号を最も早く受信した判定手段に基づいて、検索データに最も近い参照データを決定する。
【００１５】
この場合、電流電圧差ではなく、パルス信号を受ける時間差に基づいて検索データに最も近い参照データを決定する。そのため、トランジスタ素子特性のばらつきの影響を受けにくい。
【００１６】
好ましくは、連想メモリはさらに、発振回路に対応した複数の分周手段を備える。各分周手段は、対応する発振手段から出力されたパルス信号を所定の分周比で分周して、対応する判定手段に出力する。
【００１７】
この場合、決定手段は、最も早く受信したパルス信号をより精度良く特定できる。
【００１８】
好ましくは、決定手段はさらに、複数の判定手段に接続されたラッチ指示ノードと、ラッチ指示ノードを充電する充電手段とを備える。各判定手段は、放電手段と、ラッチ手段とを備える。放電手段は、対応する発振手段からの出力信号を受け、出力信号がパルス信号であるときラッチ指示ノードを放電する。ラッチ手段は、ラッチ指示ノードが放電されたときに放電手段が受けている出力信号をラッチする。
【００１９】
この場合、最も早くパルス信号を受信した判定手段が出力する出力信号のレベルと、その他の判定手段が出力する出力信号のレベルとを異なるレベルにできる。
【００２０】
好ましくは、決定手段は、トーナメント式に接続された複数の判定手段を備える。第１段目に配置された複数の判定手段の各々は、複数の第１のパルス判定手段と、パルス受付判定ノードと、充電手段とを備える。第１のパルス判定手段は、対応する発振手段の出力信号を受ける。パルス受付判定ノードは、複数の第１のパルス判定手段に接続される。充電手段は、パルス受付判定ノードを充電する。第１のパルス判定手段は、第１の放電手段と、ラッチ手段とを備える。第１の放電手段は、対応する発振手段の出力信号としてパルス信号を受けたとき、パルス受付ノードを放電する。ラッチ手段は、クロック信号を受けたとき第１の放電手段が受けている出力信号をラッチする。第２段目以降に配置されたトーナメント判定手段は、複数の第２のパルス判定手段と、パルス受付判定ノードと、充電手段とを備える。第２のパルス判定手段は、前段の対応するトーナメント判定手段のパルス受付判定ノードに接続される。パルス受付判定ノードは、複数の第２のパルス判定手段が接続される。第２のパルス判定手段は第２の充電手段を備える。第２の充電手段は、前段の対応する判定手段のパルス受付判定ノードが放電されたとき、パルス受付ノードを放電する。最上段の判定手段はさらに、クロック生成手段を備える。クロック生成手段は、パルス受付判定ノードが放電されたとき、クロック信号を出力する。
【００２１】
この場合、各パルス受付判定ノードの負荷容量を小さくすることができる。そのため、パルス信号を受けてからクロック信号が出力されるまでの時間を短縮できる。
【００２２】
好ましくは、発信手段は、直列に接続された複数のインバータと、段数選択手段とを備える。段数選択手段は、検索データと対応する参照データとの距離に応じて、インバータの段数を選択する。
【００２３】
この場合、インバータの段数に応じて発振周波数を調整できる。
【００２４】
好ましくは、決定手段は、複数の発振手段に対応する複数のカウンタ手段を備える。カウント手段は、対応する発振手段からパルス信号を受け、受けたパルスの総数をカウントし、所定数のパルスを受けたとき活性化された出力信号を生成する。
【００２５】
この場合、検索データに類似した参照データを、検索データに類似する順に順次決定することができる。
【００２６】
好ましくは、連想メモリはさらに、パルス無効化手段を備える。パルス無効化手段は、ｊ（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までに決定手段により決定された参照データに対応する発振手段から出力されるパルス信号を無効化する。
【００２７】
この場合、検索データに類似した参照データを、検索データに類似する順に順次決定することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図２】図１中のユニットデータ保存回路とユニットデータ比較回路の回路図である。
【図３】図１中の発振回路の構成を示す機能ブロック図である。
【図４】図３中の遅延回路の回路図である。
【図５】図１中のＷＴＡ回路の回路図である。
【図６】図３に示した発振回路内のインバータの段数と発信周波数のばらつきとの関係を示す図である。
【図７】本発明の第２の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図８】図７中の分周回路を用いた場合のパルス信号の波形の変化を説明するための図である。
【図９】本発明の第３の実施の形態による連想メモリのＷＴＡ回路の回路図である。
【図１０】本発明の第４の実施の形態による連想メモリの発振回路の構成を示す機能ブロック図である。
【図１１】図１０中の遅延回路の回路図である。
【図１２】図１１と異なる他の遅延回路の回路図である。
【図１３】図１１及び図１２と異なる他の遅延回路の回路図である。
【図１４】図１１〜図１３と異なる他の遅延回路の回路図である。
【図１５】本発明の第５の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１６】本発明の第６の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１７】本発明の第７の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１８】図１７中のメモリアレイ部内の第１行目の保存回路、比較回路及び発振回路の構成を示す機能ブロック図である。
【図１９】図１８中の発振回路の構成を示す機能ブロック図である。
【図２０】図１９中の遅延回路の構成を示す機能ブロック図である。
【図２１】本発明の第８の実施の形態による連想メモリのメモリアレイ部内の第１行目の保存回路、比較回路及び発振回路の構成を示す機能ブロック図である。
【図２２】本発明の第９の実施の形態による連想メモリのＷＴＡ回路の構成を示す機能ブロック図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照し、本発明の実施の形態を詳しく説明する。図中同一又は相当部分には同一符号を付してその説明は繰り返さない。
【００３０】
［第１の実施の形態］
［全体構成］
図１を参照して、本発明の実施の形態による連想メモリ１００は、メモリアレイ部１０と、ＷＴＡ（Winner Take All）回路２０とを備える。
【００３１】
メモリアレイ部１０は、メモリ部１と、行デコーダ２と、列デコーダ３と、Ｒｅａｄ／Ｗｒｉｔｅ回路４と、検索データ保存回路５とを備える。
【００３２】
メモリ部１は、ユニットデータ保存回路（Ｕｎｉｔ Ｓｔｒａｇｅ：ＵＳ）ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷを備える。ここで、Ｗは２以上の自然数であり、Ｒは２以上の自然数である。以降の説明では、任意のユニットデータ保存回路をＵＳｉｊ（１≦ｉ≦Ｗ、１≦ｊ≦Ｒ）と記載する。
【００３３】
ユニットデータ保存回路（Ｕｎｉｔ Ｓｔｒａｇｅ：ＵＳ）ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷは、行列状に配置される。同じ行に配列された複数のユニットデータ保存回路ＵＳｉｊは保存回路Ｓｉを構成する。たとえば、第１行に配列されたユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗは、保存回路Ｓ１を構成する。同様に、第２行に配列されたユニットデータ保存回路ＵＳ２１〜ＵＳ２Ｗは、保存回路Ｓ２を構成し、第Ｒ行に配列されたユニットデータ保存回路ＵＳＲ１〜ＵＳＲＷは、保存回路ＳＲを構成する。
【００３４】
各行の保存回路ＳｉはＷビット幅の参照データを記憶する。具体的には、第１行に対応した保存回路Ｓ１は、Ｗビット幅の参照データを記憶する。第２行に対応した保存回路Ｓ２は、保存回路Ｓ１が保存する参照データと異なる他の参照データを記憶する。保存回路Ｓｉ内の複数
のユニットデータ保存回路ＵＳｉｊの各々は、参照データのうちの対応する１ビットデータを記憶する。
【００３５】
メモリ部１はさらに、各保存回路Ｓ１〜ＳＲに対応した複数の比較回路Ｃ１〜ＣＲを備える。
比較回路Ｃ１は、第１行に配置された保存回路Ｓ１に対応する。比較回路Ｃ２は、第２行に配置された保存回路Ｓ２に対応する。同様に、比較回路ＣＲは、第Ｒ行に配置された保存回路ＳＲに対応する。
【００３６】
比較回路Ｃ１は、複数のユニットデータ比較回路（Ｕｎｉｔ Ｃｏｍｐａｒａｔｏｒ：ＵＣ）ＵＣ１１〜ＵＣ１Ｗを備える。同様に、第２行に対応した比較回路Ｃ２は、複数のユニットデータ比較回路ＵＣ２１〜ＵＣ２Ｗを備える。同様に、第３行〜第Ｒ行に対応した比較回路Ｃ３〜ＣＲは、複数のユニットデータ比較回路ＵＣ３１〜ＵＣ３Ｗ、・・・、ＵＣＲ１〜ＵＣＲＷを備える。
【００３７】
ユニットデータ比較回路ＵＣ１１〜ＵＣ１Ｗは、それぞれ、ユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗに対応して配置される。ユニットデータ比較回路ＵＣ２１〜ＵＣ２Ｗは、それぞれ、ユニットデータ保存回路ＵＳ２１〜ＵＳ２Ｗに対応して配置される。以下、同様にして、ユニットデータ比較回路ＵＣ３１〜ＵＣ３Ｗ、・・・、ＵＣＲ１〜ＵＣＲＷは、それぞれ、ユニットデータ保存回路ＵＳ３１〜ＵＳ３Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷに対応して配置される。
【００３８】
以降の説明では、任意の比較回路をＣｉ、任意のユニットデータ比較回路をＵＣｉｊと記載する。
【００３９】
各行の比較回路Ｃｉは、外部からＷビット幅の検索データを受け付ける。そして、検索データと、対応する保存回路Ｓｉに保存されたＷビット幅の参照データとを比較する。より具体的には、比較回路Ｃｉは、検索データと参照データとの距離（本例ではハミング距離）を求める。各行の参照データと検索データとの比較は、並列に実行される。つまり、各比較回路Ｃｉは、対応する第ｉ行の参照データと検索データとの比較を、並列（同時）に実行する。
【００４０】
メモリ部１はさらに、パルス生成回路を備える。パルス生成回路は、複数の発振回路（Ｏｓｃｉｌｌａｔｉｎｇ Ｃｉｒｃｕｉｔ：ＯＣ）ＯＣ１〜ＯＣＲを備える。以降、任意の発振回路をＯＣｉと記載する。
【００４１】
各発振回路ＯＣｉは、各行に配置される。具体的には、発振回路ＯＣ１は、保存回路Ｓ１及び比較回路Ｃ１に対応する。発振回路ＯＣ２は、保存回路Ｓ２及び比較回路Ｃ２に対応する。同様に、発振回路ＯＣＲは、保存回路ＳＲ及び比較回路ＣＲに対応する。
【００４２】
発振回路ＯＣｉは、比較回路Ｃｉにより求められたハミング距離に応じた発振周波数を有するパルス信号Ｐｉを出力する。具体的には、発振回路ＯＣ１は、第１行（保存回路Ｓ１）に保存された参照データと検索データとのハミング距離に応じた発振周波数を有するパルス信号Ｐ１を出力する。発振回路ＯＣ２は、第２行の参照データと検索データとのハミング距離に応じた発信周波数を有するパルス信号Ｐ２を出力する。同様に、発信回路ＯＣＲは、第Ｒ行の参照データと検索データとのハミング距離に応じた発信周波数を有するパルス信号ＰＲを出力する。
【００４３】
要するに、複数の発振回路ＯＣ１〜ＯＣＲを備えたパルス生成回路は、各行の参照データに応じたパルス信号Ｐ１〜ＰＲを生成する。パルス信号Ｐｉの発信周波数は、対応する行（第ｉ行）の参照データと検索データとのハミング距離に対応する。具体的には、ハミング距離が小さい程、発振周波数は高く、ハミング距離が大きい程、発振周波数は低い。
【００４４】
行デコーダ２は、メモリ部１の行方向のアドレスを指定する。列デコーダ３は、メモリ部１の列方向のアドレスを指定する。Ｒｅａｄ／Ｗｒｉｔｅ回路４は、行デコーダ２及び列デコーダ３により指定されたユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷに参照データを書き込む。Ｒｅａｄ／Ｗｒｉｔｅ回路４はさらに、検索データを検索データ保存回路５に書き込む。
【００４５】
検索データ保存回路５は、Ｒｅａｄ／Ｗｒｉｔｅ回路４によって書き込まれた検索データを保存する。
【００４６】
ＷＴＡ回路２０は、パルス生成回路（発信回路ＯＣ１〜ＯＣＲ）で生成された複数のパルス信号Ｐ１〜ＰＲを受ける。ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、検索データに最も類似する参照データを決定する。ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲのうち、発振周波数が最大のパルス信号Ｐｉを特定する。そして、特定されたパルス信号Ｐｉに対応する行（第ｉ行）に記憶された参照データを、検索データに最も類似した参照データに決定する。
【００４７】
ＷＴＡ回路２０は、複数の発振回路ＯＣ１〜ＯＣＲに対応した複数の判定回路（Judgment Circuit）ＪＣ１〜ＪＣＲを備える。以降、任意の判定回路をＪＣｉと記載する。複数の判定回路ＪＣ１〜ＪＣＲは、対応するパルス信号Ｐ１〜ＰＲを受ける。パルス信号Ｐ１〜ＰＲのうち、発振周波数が最大のパルス信号Ｐｉの電圧レベルが最も早く変化する。判定回路ＪＣ１〜ＪＣＲのうち、最も早くレベル変化したパルス信号Ｐｉを受けた判定回路ＪＣｉは、活性化された判定信号(Judgment Signal)ＪＳｉを出力する。２番目以降にレベル変化した信号Ｐｉを受けた残りの判定回路ＪＣｉは、非活性化された判定信号ＪＳｉを出力する。活性化された判定信号ＪＳは「１」を示し、電圧ＶＤＤからなる。非活性化された判定信号ＪＳｉは「０」を示し、電圧Ｖｒｅｆ（Ｖｒｅｆ＜ＶＤＤ）からなる。活性化された判定信号ＪＳｉは、対応する行（第ｉ行）の参照データが検索データに最も類似した参照データ（以降、この参照データをＷｉｎｎｅｒという）であることを示す。また、非活性化された判定信号ＪＳｉは、対応する行の参照データが検索データに最も類似した参照データではない（以降、この参照データをＬｏｓｅｒという）ことを示す。
【００４８】
たとえば、メモリ部１に記憶された複数の参照データのうち、保存回路Ｓ２に記憶された参照データが検索データに最も類似していると仮定する。この場合、パルス信号Ｐ１〜ＰＲのうち、パルス信号Ｐ２の発振周波数が最も高い。そのため、ＷＴＡ回路２０は、判定信号ＪＳ１〜ＪＳＲのうち、判定信号ＪＳ２のみを活性化し、残りの判定信号ＪＳｉを非活性化する。
【００４９】
以上のとおり、連想メモリ１００は、従来の連想メモリのように、参照データと検索データとの距離の違いを電流及び電圧差に置き換えない。代わりに、距離の違いをパルスの発振周波数の違いに置き換える。つまり、距離が異なれば発振周波数も異なる。発振周波数が異なれば、パルスが最初に立ち上がる（又は立ち下がる）時刻が異なるため、距離の違いが時間差に置き換わる。連想メモリ１００は、この時間差に基づいて、検索データに最も類似する参照データを決定する。距離の違いを電流及び電圧差に変換する場合、アナログ処理が実行される。この場合、上述のとおり、ＷｉｎｎｅｒとＬｏｓｅｒを分けるために利用されるトランジスタ素子の特性ばらつきにより誤検索が生じる場合がある。これに対して、連想メモリ１００は、距離の違いを発振周波数の違い（時間差）に置き換えてＷｉｎｎｅｒを決定する。つまり、デジタル処理によりＷｉｎｎｅｒを決定する。そのため、トランジスタ素子の特性のばらつき影響を受けにくく、誤検索が抑制される。
【００５０】
以下、保存回路Ｓｉ内のユニットデータ保存回路ＵＳｉｊと、比較回路Ｃｉ内のユニットデータ比較回路ＵＣｉｊと、パルス生成回路内の発振回路ＯＣｉと、ＷＴＡ回路２０とについて詳述する。以降の説明では、Ｗビット幅の参照データを構成する各ビットデータを参照ビットデータという。また、Ｗビット幅の参照データを構成する各ビットデータを検索ビットデータという。つまり、参照データはＷ個の参照ビットデータを有し、検索データは、参照ビットデータに対応するＷ個の検索ビットデータを有する。
【００５１】
［ユニットデータ保存回路及びユニットデータ比較回路］
図２を参照して、ユニットデータ保存回路ＵＳ１１は、ＳＲＡＭ素子を構成する。ユニットデータ保存回路ＵＳ１１は、データをラッチするラッチ回路２１０と、ｎ型ＭＯＳトランジスタ２０１、２０２とを含む。ｎ型ＭＯＳトランジスタ２０１及び２０２は直列に接続される。そして、ｎ型ＭＯＳトランジスタ２０１と２０２との間には、ラッチ回路２１０が接続される。ｎ型ＭＯＳトランジスタ２０１及び２０２のゲートは、それぞれワード線ＷＬ１に接続される。
【００５２】
ワード線ＷＬ１は行デコーダ２に接続される。行デコーダ２がワード線ＷＬ１を選択したとき、ｎ型ＭＯＳトランジスタ２０１及び２０２はオンになる。このとき、ｎ型ＭＯＳトランジスタ２０１は、外部から入力された参照データを構成する１ビットの参照ビットデータＤをラッチ回路２１０に供給する。ｎ型ＭＯＳトランジスタ２０２は、参照ビットデータＤの反転信号である参照ビットデータＤＱを受け、ラッチ回路２１０に供給する。
【００５３】
ラッチ回路２１０は、２つのインバータＩ１及びＩ２を含む。インバータＩ１の入力端子はインバータＩ２の出力端子と接続される。インバータＩ１の出力端子はインバータＩ２の入力端子と接続される。インバータＩ１はｎ型ＭＯＳトランジスタ２０１から参照ビットデータＤを受ける。インバータＩ２はｎ型ＭＯＳトランジスタ２０２から参照ビットデータＤＱを受ける。そのため、ラッチ回路２１０は１ビットの参照ビットデータＤをラッチする。参照ビットデータＤは「１」又は「０」である。参照ビットデータＤが「１」とは、ｎ型ＭＯＳトランジスタ２０１からラッチ回路２１０に供給される信号がＨレベルである場合を示し、参照ビットデータＤが「０」とは、信号がＬレベルであることを示す。
【００５４】
ユニットデータ比較回路ＵＣ１１には、外部から検索ビットデータＣＡＭが入力される。検索ビットデータＣＡＭは、検索データを構成する１ビットのデータであり、ユニットデータ保存回路ＵＳ１１に対応する。ユニットデータ比較回路ＵＣ１１は、ユニットデータ保存回路ＵＳ１１で保存されている参照ビットデータＤと、検索ビットデータＣＡＭとを比較して、距離（ハミング距離）を求める。そして、求めた距離を対応する発振回路ＯＣ１に出力する。
【００５５】
ユニットデータ比較回路ＵＣ１１は、２つのトランスファゲートＴＧ１、ＴＧ２とインバータＩ３とを含む。
【００５６】
各トランスファゲートＴＧ１、ＴＧ２は、ｎ型ＭＯＳトランジスタと、ｐ型ＭＯＳトランジスタとで構成される。トランスファゲートＴＧ１内のｐ型ＭＯＳトランジスタのゲートは、参照ビットデータＤをラッチ回路２１０から受け、ｎ型ＭＯＳトランジスタのゲートは参照ビットデータＤＱをラッチ回路２１０から受ける。トランスファゲートＴＧ２内のｐ型ＭＯＳトランジスタのゲートは、ラッチ回路２１０から参照ビットデータＤＱをラッチ回路２１０から受け、ｎ型ＭＯＳトランジスタのゲートは参照ビットデータＤをラッチ回路２１０から受ける。
【００５７】
参照ビットデータＤのレベル（「１」又は「０」）に応じて、トランスファゲートＴＧ１及びＴＧ２のいずれか一方がオンになり、他方はオフになる。トランスファゲートＴＧ１は外部から検索ビットデータＣＡＭを受ける。トランスファゲートＴＧ２は、検索ビットデータＣＡＭの反転信号である検索ビットデータＣＡＭＱを外部から受ける。
【００５８】
ノードＮ１はオンされたトランスファゲートＴＧ１又はＴＧ２から出力された信号を、パスイネーブル信号ｐａｔｈ＿ｅｎａとして出力する。インバータＩ３はパスイネーブル信号ｐａｔｈ＿ｅｎａを反転したパスイネーブル信号ｐａｔｈ＿ｅｎａｑを出力する。つまり、ユニットデータ比較回路ＵＣ１１は、２つの信号ｐａｔｈ＿ｅｎａ、ｐａｔｈ＿ｅｎａｑを出力する。２つの信号ｐａｔｈ＿ｅｎａ、ｐａｔｈ＿ｅｎａｑは、参照ビットデータＤと検索ビットデータＣＡＭとの比較結果であり、ハミング距離に相当する。
【００５９】
参照ビットデータＤと検索ビットデータＣＡＭとが一致する場合、信号ｐａｔｈ＿ｅｎａはＬレベルになり、信号ｐａｔｈ＿ｅｎａｑはＨレベルになる。たとえば、参照ビットデータＤ及び検索ビットデータＣＡＭがいずれも「１」である場合、トランスファゲートＴＧ１がオフになり、ＴＧ２がオンになる。また、参照ビットデータＤ及び検索ビットデータＣＡＭがいずでも「０」である場合、トランスファゲートＴＧ１がオンになり、ＴＧ２がオフになる。その結果、信号ｐａｔｈ＿ｅｎａはＬレベルになり、信号ｐａｔｈ＿ｅｎａｑはＨレベルになる。
【００６０】
一方、参照ビットデータＤと検索ビットデータＣＡＭとが一致しない場合、信号ｐａｔｈ＿ｅｎａはＨレベルになり、信号ｐａｔｈ＿ｅｎａｑはＬレベルになる。たとえば、参照ビットデータＤが「１」であり、検索ビットデータＣＡＭが「０」である場合、トランスファゲートＴＧ１がオフになり、ＴＧ２がオンになる。参照ビットデータＤが「０」であり、検索ビットデータＣＡＭが「１」である場合、トランスファゲートＴＧ１がオンになり、ＴＧ２がオフになる。その結果、信号ｐａｔｈ＿ｅｎａはＨレベルになり、信号ｐａｔｈ＿ｅｎａｑはＬレベルになる。
【００６１】
信号ｐａｔｈ＿ｅｎａ及びｐａｔｈ＿ｅｎａｑは、発振回路ＯＣ１生成されるパルス信号Ｐ１の発振周波数を決定する。
【００６２】
ユニットデータ保存回路ＵＳ１２〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・ＵＳＲ１〜ＵＳＲＷは、ユニットデータ保存回路ＵＳ１１と同じ構成からなる。また、ユニットデータ比較回路ＵＣ１２〜ＵＣ１Ｗ、ＵＣ２１〜ＵＣ２Ｗ、・・・ＵＣＲ１〜ＵＣＲＷは、ユニットデータ比較回路ＵＣ１１と同じ構成からなる。
【００６３】
［発振回路］
発振回路ＯＣ１は、保存回路Ｓ１に記憶されたＷビット幅の参照データとＷビット幅の検索データとの距離（ハミング距離）に応じた発振周波数のパルス信号Ｐ１を出力する。具体的には、参照データと検索データとの距離が小さい程、つまり、参照データが検索データに類似する程、発振回路ＯＣ１は、高い発振周波数のパルス信号Ｐ１を出力する。
【００６４】
図３は発振回路ＯＣ１の機能ブロック図である。図３を参照して、発振回路ＯＣ１は、複数の遅延回路(Delay Circuit)ＤＣ１１〜ＤＣ１Ｗを含む。遅延回路ＤＣ１１〜ＤＣ１Ｗはそれぞれ、ユニットデータ比較回路ＵＣ１１〜ＵＣ１Ｗに対応する。
【００６５】
遅延回路ＤＣ１１〜ＤＣ１Ｗは直列に接続される。直列された複数の遅延回路ＤＣ１１〜ＤＣ１Ｗのうち、端に位置する遅延回路ＤＣ１１の出力端子は出力ノードＮ１０に接続される。また、他方の端に位置する遅延回路ＤＣ１Ｗの入力端子は、ＮＡＮＤゲート３００の出力端子と接続される。ＮＡＮＤゲート３００は、発振回路ＯＣ１を起動する役割を有する。ＮＡＮＤゲート３００の一方の入力端子には、発振回路ＯＣ１を起動するためのイネーブル信号ＥＮＡが入力される。また他方の入力端子は出力ノードＮ１０と接続される。
【００６６】
イネーブル信号ＥＮＡが活性化（Ｈレベル）されたとき、ＮＡＮＤゲート３００は、入力信号を反転して出力する反転回路として機能する。一方、各遅延回路ＤＣ１１〜ＤＣ１Ｗは、受けた信号を反転して外部に出力する。つまり、各遅延回路ＤＣ１１〜ＤＣ１Ｗも上述の反転回路として機能する。したがって、発振回路ＯＣ１は、リング状に連結された奇数個の反転回路（起動時のＮＡＮＤゲート３００及び遅延回路ＤＣ１１〜ＤＣ１Ｗ）を備える。
【００６７】
図４に遅延回路ＤＣ１１の回路図を示す。遅延回路ＤＣ１１は、複数のインバータＩ１０〜Ｉ１４と、インバータの段数を選択する段数選択回路ＳＥとを備える。段数選択回路ＳＥは、２つのトランスファゲートＴＧ１０及びＴＧ１１を備える。トランスファゲートＴＧ１０は、Ｈレベルの信号ｐａｔｈ＿ｅｎａとＬレベルの信号ｐａｔｈ＿ｅｎａｑとを受けたときにオンする。つまり、対応するユニットデータ比較回路ＵＣ１１から出力された参照ビットデータＤと検索ビットデータＣＡＭとが一致しないとき、トランスファゲートＴＧ１０はオンする。
【００６８】
トランスファゲートＴＧ１１は、Ｌレベルの信号ｐａｔｈ＿ｅｎａとＨレベルの信号ｐａｔｈ＿ｅｎａｑとを受けたときにオンする。つまり、参照ビットデータＤと検索ビットデータＣＡＭとが一致したとき、スイッチ回路ＴＧ１１はオンになる。
【００６９】
複数のインバータＩ１０〜Ｉ１４は直列に接続される。インバータＩ１３とインバータＩ１４との間にはトランスファゲートＴＧ１０が接続される。そして、スイッチ回路ＴＧ１１は、インバータＩ１０の入力端子とインバータＩ１４の入力端子との間に接続される。
【００７０】
段数選択回路ＳＥは、対応するユニットデータ比較回路ＵＣ１１の比較結果に応じてインバータの段数を選択する。ユニットデータ比較回路ＵＣ１１での比較の結果、参照ビットデータＤと検索ビットデータＣＡＭとが一致する場合、トランスファゲートＴＧ１０がオフになり、ＴＧ１１がオンになる。そのため、遅延回路ＤＣ１１の入力信号は１段のインバータＩ１４を介して外部に出力される。
【００７１】
一方、参照ビットデータＤと検索ビットデータＣＡＭとが異なる場合、トランスファゲートＴＧ１０がオンになり、ＴＧ１１がオフになる。そのため、遅延回路ＤＣ１１の入力信号は、５段のインバータを介して外部に出力される。つまり、参照ビットデータＤと検索ビットデータとが一致しない方が、遅延時間が長くなる。
要するに、遅延回路ＤＣ１１は、インバータ段数が少ないパス（ショートパス）と、インバータ段数が多いパス（ロングパス）と、参照ビットデータと検索ビットデータとのハミング距離に応じてショートパス及びロングパスのいずれかを選択する段数選択回路とを備える。
【００７２】
他の遅延回路ＤＣ１２〜ＤＣ１Ｗも、遅延回路ＤＣ１１と同じ構成を有する。したがって、発振回路ＯＣ１では、保存回路Ｓ１に記憶されたＷビット幅の参照データがＷビット幅の検索データに類似するほど、つまり、参照データと検索データとの距離が小さい程、インバータの段数が少なくなる。なぜなら、Ｌレベルの信号ｐａｔｈ＿ｅｎａとＨレベルの信号ｐａｔｈ＿ｅｎａｑとを出力するデータユニット比較回路ＵＣ１ｊの数が相対的に多くなるからである。インバータの段数が少ないほど、遅延時間は短くなる。したがって、発振回路ＯＣ１は、発振周波数の高いパルス信号Ｐ１を出力する。
【００７３】
一方、保存回路Ｓ１に記憶された参照データと検索データとの距離が遠い程、発振回路ＯＣ１内で利用されるインバータの段数は多くなる。そのため、発振回路ＯＣ１は発振周波数の低いパルス信号Ｐ１を出力する。
【００７４】
以上の構成により、発信回路ＯＣ１は、保存回路Ｓ１の参照データと検索データとの距離に応じた発振周波数のパルス信号Ｐ１を出力する。発振回路ＯＣ１は、参照データと検索データとの距離が小さい程、利用するインバータの段数を減らす。そのため、参照データが検索データに類似する程、高い発振周波数を有するパルス信号Ｐ１を出力する。
【００７５】
発振回路ＯＣ２〜ＯＣＲはそれぞれ、発振回路ＯＣ１と同じ構成を有する。したがって、発振回路ＯＣ１〜ＯＣＲのうち、発振周波数が最大となるパルス信号Ｐｉを出力した発振回路ＯＣｉに対応する保存回路Ｓｉに、検索データに最も類似した参照データが格納されている。
【００７６】
ＮＡＮＤゲート３００は、ノードＮ１０上の信号とイネーブル信号ＥＮＡとを受け、ＮＡＮＤ論理演算結果を遅延回路ＤＣ１Ｗに出力する。上述のとおり、ＮＡＮＤゲート３００は、イネーブル信号ＥＮＡに応じて発振回路ＯＣ１を起動又は停止する。イネーブル信号ＥＮＡが非活性（Ｌレベル）のとき、ＮＡＮＤゲート３００は常にＨレベルの信号を出力する。そのため、発振回路ＯＣ１から出力される信号はＨレベルで一定である。つまり、発振回路ＯＣ１は、パルス信号を出力しない。
【００７７】
［ＷＴＡ回路］
ＷＴＡ回路２０は、発振回路ＯＣ１〜ＯＣＲからパルス信号Ｐ１〜ＰＲを受ける。そして、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、検索データに最も類似した参照データ（Ｗｉｎｎｅｒ）を決定する。
【００７８】
図５を参照して、ＷＴＡ回路２０は、複数の判定回路ＪＣ１〜ＪＣＲと、プリチャージ回路３０と、ラッチ指示ノードＮ４０とを備える。各判定回路ＪＣ１〜ＪＣＲは、ラッチ指示ノードＮ４０に接続される。
【００７９】
プリチャージ回路３０は、イネーブル信号ＥＮＡの反転信号であるイネーブル信号ＥＮＡＱを受けたとき、ラッチ指示ノードＮ４０に電荷を供給し、充電する。これにより、ラッチ指示ノードＮ４０の電圧はＨレベル（ＶＤＤ）に上昇する。
【００８０】
判定回路ＪＣ１は、対応する発振回路ＯＣ１の出力信号を受ける。判定回路ＪＣ２は、発振回路ＯＣ２の出力信号を受ける。同様に、判定回路ＪＣ３〜ＪＣＲは、発振回路ＯＣ３〜ＯＣＲの出力信号をそれぞれ受ける。
【００８１】
判定回路ＪＣ１は、インバータＩ２０と、遅延回路２５１と、ラッチ回路２５２と、放電回路２５０と、クロック生成回路２５３とを備える。
【００８２】
インバータＩ２０は、発信回路ＯＣ１の出力信号を受け、反転してノードＮ３０に出力する。放電回路２５０は、ｎ型ＭＯＳトランジスタからなる。ｎ型ＭＯＳトランジスタは、ラッチ指示ノードＮ４０と接地電圧が供給されるＧＮＤノードとの間に接続され、そのゲートはノードＮ３０に接続される。放電回路２５０は、ｎ型ＭＯＳトランジスタのゲートにＨレベルの信号が入力されたとき、ラッチ指示ノードＮ４０を放電する。つまり、判定回路ＪＣ１は、パルス信号Ｐ１を受けたとき、放電回路２５０によりラッチ指示ノードＮ４０の電圧レベルを接地電圧（Ｌレベル）まで低下する。
【００８３】
クロック生成回路２５３は、ラッチ指示ノードＮ４０がＬレベルとなったときにクロック信号ＣＬＫを出力する。クロック生成回路２５３は、インバータＩ２１からなる。インバータＩ２１の入力端子はラッチ指示ノードＮ４０に接続される。クロック生成回路２５３は、ラッチ指示ノードＮ４０がＬレベルになったとき、Ｈレベルのクロック信号ＣＬＫを出力する。
【００８４】
ラッチ回路２５２は、Ｄフリップフロップで構成される。ラッチ回路２５２は、Ｈレベルのクロック信号ＣＬＫを受けたとき、インバータＩ２０の出力信号をラッチして、判定信号ＪＳ１を外部に出力する。
【００８５】
遅延回路２５１は、発振回路ＯＣ１からパルス信号Ｐ１が出力された場合、クロック生成回路２５３がクロック信号を出力するときにパルス信号Ｐ１の反転信号がラッチ回路２５２に入力されるように調整する。ただし、遅延回路２５１はなくてもよい。
【００８６】
判定回路ＪＣ２〜ＪＣＲは、判定回路ＪＣ１と同じ構成を有する。各判定回路ＪＣ１〜ＪＣＲの放電回路２５０及びクロック生成回路２５３は、いずれもラッチ指示ノードＮ４０と接続されている。したがって、いずれかの判定回路ＪＣの放電回路２５０がラッチ指示ノードＮ４０を放電すれば、全ての判定回路ＪＣ１〜ＪＣＲのクロック生成回路２５３はＨレベルのクロック信号ＣＬＫを出力する。
【００８７】
発振回路ＯＣ１〜ＯＣＲの出力信号にパルスが形成されていないとき、つまり、発振回路ＯＣｉがパルス信号Ｐｉを出力する前、パルス信号Ｐ１〜ＰＲはＨレベルで一定である。ここで、発振回路ＯＣ１〜ＯＣＲのうち、発振回路ＯＣ２が最大の発振周波数のパルス信号Ｐ２を出力したと仮定する。
【００８８】
この場合、発信回路ＯＣ２の出力信号が、他の発振回路ＯＣｉの出力信号よりも早く、電圧レベルがＨレベルからＬレベルに変化する。そのため、各判定回路ＪＣｉ内の放電回路２５０のうち、判定回路ＪＣ２の放電回路２５０が最も早く動作してラッチ指示ノードＮ４０をＬレベルにする。
【００８９】
このとき、判定回路ＪＣ２のラッチ回路２５２はＨレベルの信号を受ける。しかしながら、他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲのラッチ回路２５２はＬレベルの信号を受けている。ラッチ指示ノードＮ４０がＬレベルになると、各判定回路ＪＣｉ内のクロック生成回路２５３が一斉にＨレベルのクロック信号ＣＬＫを出力する。そのため、判定回路ＪＣ２内のラッチ回路２５２のみがＨレベルの信号をラッチし、その他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲ内のラッチ回路２５２はＬレベルの信号をラッチする。
【００９０】
以上の工程により、判定回路ＪＣ２はＷｉｎｎｅｒを示すＨレベルの判定信号ＪＳ２を出力し、他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲはＬｏｓｅｒを示すＬレベルの判定信号ＪＳ１、ＪＳ３〜ＪＳＲを出力する。
【００９１】
以上のとおり、本実施の形態による連想メモリ１００は、参照データと検索データとの距離に応じた発振周波数のパルス信号を生成する。そして、パルス信号の発振周波数に基づいて、Ｗｉｎｎｅｒとなる参照データを決定する。
【００９２】
参照データと検索データとの距離を発振周波数に変換すれば、従来の連想メモリのようにトランジスタ素子の特性のばらつきによる誤検索が発生しにくい。発振回路ＯＣｉは複数段のインバータを備える。インバータを構成するトランジスタ素子の特性にばらつきが生じても、インバータ段数は複数存在するため、特性ばらつきの影響を抑えることができる。つまり、トランジスタ素子の特性にばらつきが生じても、発振周波数のばらつきを抑制することができる。
【００９３】
図６は発振回路ＯＣｉ内のインバータの段数と発振周波数のばらつきとの関係を示すグラフである。図６のグラフは次の方法で求めた。初めに、インバータ段数が１７段、３３段、６５段及び１２９段の発振回路をそれぞれ作製した。使用するＣＭＯＳトランジスタのゲート長は９０ｎｍとした。
【００９４】
作製された各発振回路に種々の電源電圧を用いてパルス信号を生成した。生成されたパルス信号の発振周波数を測定した。測定された発振周波数の平均値を１として正規化し、標準偏差を求めた。図６中の縦軸は、各発振回路の標準偏差（％）を示す。図６を参照して、インバータ段数が多いほど、発振周波数のばらつきが抑えられることが分かる。
【００９５】
［第２の実施の形態］
上述のとおり、第１の実施の形態による連想メモリ１００では、ＷＴＡ回路２０が、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、Ｗｉｎｎｅｒとなる参照データを決定する。したがって、最大の発振周波数を有するパルス信号Ｐｉと、２番目に高い発振周波数を有するパルス信号Ｐｉとの発振周波数の差が大きいほど、Ｗｉｎｎｅｒの誤検出が起こりにくい。
【００９６】
図７を参照して、第２の実施の形態による連想メモリ１１０は、連想メモリ１００と比較して、メモリ部１０とＷＴＡ回路２０との間に、分周部３５を新たに備える。連想メモリ１１０のその他の構成は、連想メモリ１００と同じである。
【００９７】
分周部３５は、複数の分周回路(Frequency Divider)ＦＤ１〜ＦＤＲを備える。連想メモリ１１０のその他の構成は、連想メモリ１００と同じである。
【００９８】
分周回路ＦＤ１は、発振回路ＯＣ１のパルス信号Ｐ１を受ける。そして、パルス信号Ｐ１の周波数を所定の分周比で分周する。本例では、分周回路ＦＤ１は、パルス信号Ｐ１を１．５分周する。ただし、分周比は１．５に限られない。他の分周回路ＦＤ２〜ＦＤＲも分周回路ＦＤ１と同じ分周比でパルス信号Ｐ２〜ＰＲを分周する。
【００９９】
ＷＴＡ回路２０内の各判定回路ＪＣ１〜ＪＣＲは、分周されたパルス信号Ｐ１〜ＰＲを受ける。ＷＴＡ回路２０は、分周されたパルス信号Ｐ１〜ＰＲに基づいて、Ｗｉｎｎｅｒを決定する。
【０１００】
パルス信号Ｐｉを所定の分周比で分周すれば、最も高い発振周波数のパルス信号Ｐｉの波形変化と、次に高い発振周波数のパルス信号Ｐｉの波形変化との差を大きくすることができる。図８を用いてこの点を説明する。
【０１０１】
図８は、各分周回路ＦＤｉが分周比１．５でパルス信号Ｐｉを分周した場合の、パルス信号Ｐ１及びＰ２の波形を示す図である。図中のＰ１（ＦＤ１）は、分周回路ＦＤ１から出力されたパルス信号Ｐ１を示す。図中のＰ２（ＦＤ２）は、分周回路ＦＤ２から出力されたパルス信号Ｐ２を示す。図中のＰ１は、分周回路ＦＤ１に入力されるパルス信号Ｐ１を示し、図中のＰ２は、分周回路ＦＤ２に入力されるパルス信号Ｐ２を示す。
【０１０２】
ここで、パルス信号Ｐ１の周波数が最も高く、Ｐ２の周波数が次に高いと仮定する。図８に示すとおり、分周回路に入力される前のパルス信号Ｐ１とＰ２との最初の波形変化の時間差はＴｄ１である。
【０１０３】
一方、分周されたパルス信号Ｐ１（ＦＤ１）とＰ２（ＦＤ２）との最初の波形変化の時間差はＴｄ２となる。時間差Ｔｄ２は時間差Ｔｄ１よりも大きい。要するに、分周回路ＦＤ１〜ＦＤＲは、Ｗｉｎｎｅｒとなるパルス信号の最初の波形変化と、次に周波数の高いパルス信号の最初の波形変化との時間差を増大する。そのため、ＷＴＡ回路２０はより正確に、Ｗｉｎｎｅｒを決定できる。
【０１０４】
［第３の実施の形態］
連想メモリ１００内のＷＴＡ回路２０では、図５に示すように、全ての判定回路ＪＣ１〜ＪＣＲが１つのラッチ指示ノードＮ４０に接続される。ＷＴＡ回路２０のラッチ指示ノードＮ４０は、全ての判定回路ＪＣ１〜ＪＣＲに接続されるために長い。そのため、ラッチ指示ノードＮ４０の負荷容量は大きい。したがって、放電回路２５０内のｎ型ＭＯＳトランジスタがオンになってから、ラッチ指示ノードＮ４０の電圧レベルが接地電圧に落ちるまでに時間がかかる。ラッチ指示ノードＮ４０の電圧レベルを落とすのに時間がかかれば、Ｗｉｎｎｅｒの決定も時間がかかる。
【０１０５】
そこで、本実施の形態による連想メモリは、ＷＴＡ回路２０の代わりに図９に示す新たなＷＴＡ回路２５を備える。その他の構成は連想メモリ１００と同じである。
【０１０６】
図９を参照して、ＷＴＡ回路２５は、複数の判定ブロックＪＢを備える。複数の判定ブロックＪＢは、トーナメント式に複数段に接続される。図９では、最下段である第１段から、最上段である第ｎ段（ｎは２以上の自然数）まで、ｎ段のトーナメント式となっている。
【０１０７】
最下段に当たる第１段目に配列された複数の判定ブロックＪＢ１は、Ｒ個の第１パルス判定回路ＰＪＣ１〜ＰＪＣＲを含む。換言すれば、Ｒ個の第１パルス判定回路ＰＪＣ１〜ＰＪＣＲは、複数の判定ブロックＪＢ１に分割される。
【０１０８】
各判定回路ＪＢ１は、Ｒ個未満の第１パルス判定回路ＰＪＣｉとパルス受付判定ノードＮ５０とを備える。第１パルス判定回路ＰＪＣ１〜ＰＪＣＲの各々は、図５中の判定回路ＪＣ１〜ＪＣＲと比較して、クロック生成回路２５３を有さない。その他の構成は判定回路ＪＣ１〜ＪＣＲと同じである。各第１パルス判定回路ＰＪＣ１〜ＰＪＣＲは、対応する発振回路ＯＣ１〜ＯＣＲからパルス信号Ｐ１〜ＰＲをそれぞれ受ける。
【０１０９】
各判定ブロックＪＢ１はさらに、パルス受付判定ノードＮ５０と、プリチャージ回路３０とを備える。プリチャージ回路３０は、イネーブル信号ＥＮＡＱを受けたとき、パルス受付判定ノードＮ５０を充電する。
【０１１０】
パルス受付判定ノードＮ５０は、判定ブロックＪＢ１に含まれる複数の第１パルス判定回路ＰＪＣｉ（ただし、Ｒ個未満）に接続される。より具体的には、各第１パルス判定回路ＰＪＣｉ内の放電回路２５０に接続される。
【０１１１】
図５中のラッチ指示ノードＮ４０に接続される判定回路ＪＣｉはＲ個である。これに対して図９中の各パルス受付判定ノードＮ５０に接続される第１パルス判定回路ＰＪＣｉはＲ個未満である。パルス受付判定ノードＮ５０は、ラッチ指示ノードＮ４０と比較して、負荷容量が小さい。
【０１１２】
トーナメント式に接続された判定ブロックのうち、第２段目〜第ｎ−１段目に配列される判定ブロックＪＢ２〜ＪＢｎ−１の構成について説明する。図９を参照して、第２段目に配列される複数の判定ブロックＪＢ２の各々は、プリチャージ回路３０と、パルス受付判定ノードＮ５０と、複数の第２パルス判定回路ＰＪとを含む。
【０１１３】
各第２パルス判定回路ＰＪは、対応する判定ブロックＪＢ１内のパルス受付判定ノードＮ５０に接続される。第２パルス判定回路ＰＪは、インバータＩ２０と、放電回路２５０とを備える。第２パルス判定回路ＰＪは、自身が属する判定ブロックＪＢ２内のパルス受付判定ノードＮ５０に接続される。より具体的には、第２パルス判定回路ＰＪ内の放電回路２５０がパルス受付判定ノードＮ５０と接続される。プリチャージ回路３０は、イネーブル信号ＥＮＡＱを受けたとき、パルス受付判定ノードＮ５０を充電する。
【０１１４】
第３段目〜第ｎ−１段目に配列された各判定ブロックＪＢの構成も同じである。第ｎ−１段目に配列された判定ブロックＪＢ内の第２パルス判定回路ＰＪは、前段、つまり、第ｎ−２段目に配列された複数の判定ブロックＪＢのうち、対応する判定ブロックＪＢ内のパルス受付判定ノードＮ５０に接続される。
【０１１５】
最上段である第ｎ段には、１つの判定ブロックＪＢｎが配置される。判定ブロックＪＢｎは、判定ブロックＪＢ２と比較して、クロック生成回路３１を新たに備える。他の構成は判定ブロックＪＢ２と同じである。
【０１１６】
クロック生成回路３１は、パルス受付判定ノードＮ５０がＬレベルになったとき、クロック信号ＣＬＫを出力する。クロック生成回路３１内の構成は図５中のクロック生成回路２５３と同じである。つまり、クロック生成回路３１はインバータＩ２１を備える。
【０１１７】
以上のとおり、ＷＴＡ回路２５は、第１段〜第ｎ段までの複数段のトーナメント式に接続された判定ブロックＪＢ１〜ＪＢｎを備える。各パルス受付判定ノードＮ５０に接続される第１又は第２パルス判定回路の数は、図５中のラッチ指示ノードＮ４０に接続される判定回路の数よりも少ない。したがって、各パルス受付判定ノードＮ５０の負荷容量は、ラッチ指示ノードＮ４０の負荷容量よりも小さい。そのため、パルス受付判定ノードＮ５０をＨレベルからＬレベルに下げるのにかかる時間は、ラッチ指示ノードＮ４０よりも短くすることができる。
【０１１８】
要するに、トーナメント式に判定ブロックＪＢ１〜ＪＢｎを配置すれば、パルス受付判定ノードＮ５０の負荷容量を小さくできる。そのため、判定ブロックＪＢ１内が最も高い周波数のパルス信号Ｐｉを受けてから、クロック信号ＣＬＫが出力されるまでの時間を短くできる。換言すれば、Ｗｉｎｎｅｒの決定時間を短くできる。
【０１１９】
［第４の実施の形態］
第１の実施の形態では、データユニット保存回路ＵＳｉｊごとに遅延回路ＤＣｉｊを設けた。しかしながら、このような構成では、使用されるトランジスタ素子数が多くなる。そのため、１つの遅延回路を複数のデータユニット保存回路に対応させてもよい。
【０１２０】
本実施の形態による連想メモリは、発振回路ＯＣ１〜ＯＣＲに代えて、新たな発振回路ＯＳＣ１〜ＯＳＣＲを備える。その他の構成は連想メモリ１００と同じである。
【０１２１】
図１０を参照して、発振回路ＯＳＣ１は、発振回路ＯＣ１と比較して、遅延回路ＤＣ１１、ＤＣ１２、・・・ＤＣ１Ｗに代えて、遅延回路ＤＬＣ１１、ＤＬＣ１２、・・・ＤＣＬ１Ｔ（Ｔは１以上の自然数）と、距離判定回路ＤＪ１１〜ＤＪ１Ｔとを備える。距離判定回路ＤＪ１１〜ＤＪ１Ｔは、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔに対応する。その他の構成は発振回路ＯＣ１と同じである。
【０１２２】
活性化されたＮＡＮＤゲート３００は入力信号を反転する。また、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔの各々も、入力信号を反転する。したがって、ＮＡＮＤゲート３００及び遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは、反転回路として機能する。つまり、発振回路ＯＳＣ１は、奇数個の反転回路を備える。したがって、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは偶数個含まれている。奇数個の反転回路（ＮＡＮＤゲート３００及び遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔ）はループ状に直列に連結されている。
【０１２３】
各遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは、２つのデータユニット比較回路ＵＣｉｊの比較結果に基づいて、パルス信号Ｐ１の発振周波数を決定する。
【０１２４】
各距離判定回路ＤＪ１１〜ＤＪ１Ｔは、２つのデータユニット比較回路ＵＣｉｊから比較結果（２つの信号ｐａｔｈ＿ｅｎａ及び信号ｐａｔｈ＿ｅｎａｑ）を受ける。そして、比較結果からハミング距離を求める。そして、求めたハミング距離に応じた信号を、対応する遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔに出力する。
【０１２５】
具体的には、距離判定回路ＤＪ１１は、ユニットデータ比較回路ＵＣ１１及びＵＣ１２から比較結果を受ける。比較の結果、ユニットデータ保存回路ＵＳ１１及びＵＳ１２に格納された参照ビットデータＤの全てが対応する検索ビットデータＣＡＭと一致するとき（つまり、ハミング距離＝０のとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ０を出力する。そして、Ｌレベルの信号Ｓ１及びＳ２を出力する。また、信号Ｓ０、Ｓ１及びＳ２の反転信号／Ｓ０、／Ｓ１及び／Ｓ２を出力する。
【０１２６】
２つの参照ビットデータのうち、いずれか１つが対応する検索ビットデータと一致するとき（つまり、ハミング距離＝１のとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ１を出力し、Ｌレベルの信号Ｓ０及びＳ２を出力する。
【０１２７】
２つの参照ビットデータのいずれも対応する検索ビットデータと一致しないとき（距離＝２であるとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ２を出力し、Ｌレベルの信号Ｓ０及びＳ１を出力する。
【０１２８】
上述のとおり、遅延回路ＤＬＣ１１〜ＤＣＬ１ＴとＮＡＮＤゲート３００は、ループ状に直列に接続される。複数の遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔのうち、端に位置する遅延回路ＤＬＣ１１の出力端子は出力ノードＮ１０に接続される。また、他方の端に位置する遅延回路ＤＬＣ１Ｔの入力端子は、ＮＡＮＤゲート３００の出力端子と接続される。
【０１２９】
遅延回路ＤＬＣ１１の構成を図１１に示す。遅延回路ＤＬＣ１１は、第１の遅延段７０と、第２の遅延段７１と、インバータＩ７１と、段数選択回路７２とを備える。段数選択回路７２は、トランスファゲートＴＧ７１、ＴＧ７２及びＴＧ７３を備える。段数選択回路７２は、距離判定回路ＤＪ１１からの信号Ｓ０〜Ｓ２に応じて、利用するインバータの段数を選択する。換言すれば、段数選択回路７２は、ハミング距離に応じて遅延時間（発振周波数）を選択する。
【０１３０】
第１の遅延段７０及び第２の遅延段７１はそれぞれ、直列に接続された偶数個のインバータを含む。第１の遅延段７０は、前段の遅延回路ＤＬＣ１２の出力を受け、遅延する。第２の遅延段７１は、第１の遅延段７０の出力を受け、遅延する。
【０１３１】
段数選択回路７２内のトランスファゲートＴＧ７１〜ＴＧ７３は並列に接続される。トランスファゲートＴＧ７１〜ＴＧ７３はそれぞれ、ｎ型ＭＯＳトランジスタとｐ型ＭＯＳトランジスタとで構成される。トランスファゲートＴＧ７１は、対応する距離判定回路ＤＪ１１からＨレベルの出力信号Ｓ０とＬレベルの出力信号／Ｓ０を受けるとオンになる。ここで、出力信号／Ｓ０は、信号Ｓ０の反転信号である。要するに、トランスファゲートＴＧ７１は、データユニット保存回路ＵＳ１１及びＵＳ１２に格納された参照データがいずれも検索データと一致したとき（距離＝０のとき）、オンになる。このとき、遅延回路ＤＬＣ１１は、入力信号をトランスファゲートＴＧ７１に通してインバータＩ７１に出力する。
【０１３２】
トランスファゲートＴＧ７２は、Ｈレベルの信号Ｓ１とＬレベルの信号／Ｓ１（信号Ｓ１の反転信号）とを受けるとオンになる。つまり、距離＝１のときにオンになる。このとき、遅延回路ＤＬＣ１１は、入力信号を第１の遅延段７０に供給する。そして、第１の遅延段７０の出力をインバータＩ７１に供給する。
【０１３３】
トランスファゲートＴＧ７３は、Ｈレベルの信号Ｓ２とＬレベルの信号／Ｓ２（信号Ｓ２の反転信号）とを受けるとオンになる。つまり、距離＝２のときにオンになる。このとき、トランスファゲートＴＧ１３は、第２の遅延段７１の出力をインバータＩ７１に供給する。
【０１３４】
要するに、発振回路ＤＬＣ１１は、３つのパス（遅延段のないショートパス、遅延段７１を有するミドルパス、遅延段７１及び７２を有するロングパス）と、３つのパスのうちいずれか１つを選択する段数選択回路７２とを備える。各パスは、それぞれ異なる遅延時間が設定されている。発振回路ＤＬＣ１１は、２つの参照ビットデータと検索ビットデータとの比較結果に応じて、３つのパスの中から１つのパスを選択する。上述の例では、距離＝０のとき、遅延回路ＤＬＣ１１は、ショートパスを選択する。このとき、利用するインバータの段数は１つ（インバータＩ７１のみ）である。距離＝１のとき、遅延回路ＤＬＣ１１は、ミドルパスを選択する。このとき、インバータの段数は５つである（第１の遅延段７０＋インバータＩ７１）。距離＝２のとき、遅延回路ＤＬＣ１１は、ロングパスを選択する。このとき、インバータ段数は９個である（第１の遅延段７０、第２の遅延段７１及びインバータＩ７１）。
【０１３５】
なお、遅延回路ＤＬＣ１２〜ＤＬＣ１Ｔは遅延回路ＤＬＣ１１と同じ構成を有する。
【０１３６】
上述のとおり、遅延回路ＤＬＣは複数の比較結果に応じてインバータの段数を変える。そのため、発振回路ＤＬＣ１１は、発振回路ＤＣ１１と比較して、利用するトランジスタ素子数を減らすことができる。さらに、参照データと検索データが一致した場合（距離＝０の場合）のインバータ段数を減らすことができる。そのため、より高周波のパルス信号を出力できる。その結果、ＷＴＡ回路２０がＷｉｎｎｅｒを決定する時間をより短くできる。
【０１３７】
上述の例では、遅延回路ＤＬＣは、２つの遅延段を含み、利用する遅延段数に応じて３つの遅延時間を設定できる。遅延回路ＤＬＣは、２つの参照ビットデータと２つの検索ビットデータから得られる２つの比較結果に応じて、利用する遅延段数を選択する。その結果、３つの遅延時間の中から１つの遅延時間が選択される。
遅延回路ＤＬＣはＬ（Ｌは２以上の自然数）個の参照ビットデータと検索ビットデータと比較結果に応じて遅延時間を設定することもできる。より具体的には、遅延回路ＤＬＣは、複数の遅延段を含み、利用する遅延段数に応じてＬ＋１個の遅延時間を設定できる。遅延回路ＤＬＣは、Ｌ個の比較結果に応じて、Ｌ＋１個の遅延時間（パス）の中から１つの遅延時間（パス）を選択する。遅延回路ＤＬＣに入力された信号は、選択された遅延時間だけ遅延して次段の遅延回路ＤＬＣに出力される。要するに、Ｌ個の参照ビットデータと検索ビットデータとを比較する場合、遅延回路ＤＬＣは、Ｌ＋１個のパスを備える。各パスは異なる遅延時間が設定される。
【０１３８】
なお、図１２に示すように、第１の遅延段７０及び第２の遅延段７１の初段のインバータをトライステート型のインバータにしてもよい。トライステートインバータＩ７０１は、Ｈレベルの信号Ｓ１又はＳ２を受けると活性化する。また、トライステートインバータＩ７０２は、Ｈレベルの信号Ｓ２を受けると活性化する。距離＝０のとき、第１の遅延段７０及び第２の遅延段７１は動作せず、距離＝１のとき、第２の遅延段７１は動作しない。したがって、消費電力を削減できる。
【０１３９】
トライステートインバータＩ７０１及びＩ７０２が非活性の場合、各遅延段７０及び７１の２段目のインバータの入力ノードは浮遊状態となる。そのため、ノイズ等の影響でノードのレベルが変動し、インバータが動作してしまう場合がある。図１３に示すように、トライステートインバータＩ７０１及びＩ７０２に代えて、ＮＯＲゲート７２１及び７２２を用いれば、２段目のインバータの入力ノードが浮遊状にならない。そのため、ノイズ等の影響で２段目以降のインバータが動作するのを防止できる。
【０１４０】
ＮＯＲゲート７２１は、Ｌレベルの信号／Ｓ１又はＬレベルの信号／Ｓ２を受けると、ＮＯＴゲート（インバータ）として動作する。また、ＮＯＲゲート７２２は、Ｌレベルの信号／Ｓ２を受けると、ＮＯＴゲートとして動作する。
【０１４１】
さらに、図１４に示すように、第２の遅延段７１とトランスファゲートＴＧ７３との間にダミーのＮＯＲゲート７２２を配置してもよい。この場合、各パスの配線に係る容量を同じにできる。そのため、設計時において、各パスの遅延回路の設計を同じにすることができる。
【０１４２】
［第５の実施の形態］
上述の連想メモリ１００は、検索データに最も近い参照データを検索する。しかしながら、検索データに近い参照データを、検索データに近い順に複数検索できる方が好ましい場合がある。
【０１４３】
図１５を参照して、本実施の形態による連想メモリ２００は、連想メモリ１００と比較して、新たにフィードバック回路５０を備える。その他の構成は連想メモリ１００と同じである。
【０１４４】
フィードバック回路５０は、複数のフィードバック回路５１〜５Ｒを備える。各フィードバック回路５１〜５Ｒは、制御信号ＣＯＮを受けて起動する。
【０１４５】
フィードバック回路５１は、Ｈレベルの判定信号ＪＳ１を受けたとき、Ｈレベルのフィードバック信号を出力する。発振回路ＯＣ１の出力ノードは、Ｈレベルのフィードバック信号を受けて、充電される。つまり、フィードバック回路５１は、Ｈレベルの判定信号ＪＳ１を受けると、発振回路ＯＣ１の出力ノードをチャージする。そのため、発振回路ＯＣ１の出力信号はＨレベルで固定される。たとえパルス信号Ｐ１が出力されても、パルス信号Ｐ１が無効化される。
【０１４６】
フィードバック回路５１は、判定信号ＪＳ１がＬレベルのとき、発振回路ＯＣ１の出力ノードをチャージしない。しかし、いったん判定信号ＪＳ１がＨレベルになると、それ以降、Ｈレベルのフィードバック信号を発振回路ＯＣ１の出力ノードに供給し続ける。
【０１４７】
同様に、フィードバック回路５２〜５Ｒはそれぞれ、対応する判定信号ＪＳ２〜ＪＳＲがＨレベルになるまで、発振回路ＯＣ２〜ＯＣＲの出力ノードをチャージしない。しかし、いったん判定信号ＪＳ２〜ＪＳＲがＨレベルになると、それ以降、発振回路ＯＣ２〜ＯＣＲの出力ノードをチャージし続ける。
【０１４８】
以上の構成を有する連想メモリ２００の動作は次のとおりである。
【０１４９】
連想メモリ２００は初めに、１回目の検索を開始する。このとき、連想メモリ２００は検索データに最も類似する参照データを検索する。
【０１５０】
初めに、各比較回路Ｃ１〜ＣＲに検索データが入力される。その後、イネーブル信号ＥＮＡがＨレベルとなり、発振回路ＯＣ１〜ＯＣＲが動作を開始する。ここで、保存回路Ｓ２に記憶された参照データが検索データに最も類似すると仮定する。この場合、判定信号ＪＳ２がＨレベルとなり、その他の判定信号ＪＳ１、ＪＳ３〜ＪＳＲはＬレベルとなる。
【０１５１】
フィードバック回路５１〜５Ｒは、制御信号ＣＯＮを受けて起動する。フィードバック回路５２は、Ｈレベルの判定信号ＪＳ２を受けると、発振回路ＯＣ２の出力ノードをチャージする。その結果、発振回路ＯＣ２の出力ノードの電圧レベルはＨレベルに維持される。そのため、発振回路ＯＣ２から出力されるパルス信号Ｐ２は無効化される。
【０１５２】
第１回目の検索が終了したとき、発振回路ＯＣ１〜ＯＣＲに入力されるイネーブル信号ＥＮＡはいったん非活性（Ｌレベル）となる。
【０１５３】
続いて、連想メモリ２００は、第２回目の検索を実行する。このとき、イネーブル信号ＥＮＡが再びＨレベルになる。そこで、発振回路ＯＣ１〜ＯＣＲは第１回目と同じ比較結果に基づいて、パルス信号Ｐ１〜ＰＲを再び出力する。
【０１５４】
しかしながら、発振回路ＯＣ２の出力ノードは、フィードバック回路５２によりＨレベルに維持されている。したがって、パルス信号Ｐ２は無効化され、発振回路ＯＣ２の出力信号Ｈレベルのままとなる。そのため、ＷＴＡ回回路２０は、パルス信号Ｐ２以外の他の信号Ｐ１、Ｐ３〜ＰＲに基づいて、最も検索データに近い参照データを決定する。ここで、保存回路Ｓ１に記憶された参照データが検索データに最も近いと仮定する。この場合、判定信号ＪＳ１がＨレベルとなり、その他の信号ＪＳ２〜ＪＳＲはＬレベルとなる。
【０１５５】
第２回目の検索によりＨレベルとなった信号ＪＳ１に対応する参照データ（つまり、保存回路Ｓ１に記憶された参照データ）は、検索データに２番目に類似する参照データに相当する。
【０１５６】
判定信号ＪＳ１がＨレベルになると、フィードバック回路５１は発振回路ＯＣ１の出力ノードをチャージする。要するに、フィードバック回路５１は発振回路ＯＣ１のパルス信号Ｐ１を無効化する。第３回目の検索時では、発振回路ＯＣ１及びＯＣ２はパルス信号を出力できない。そのため、既に検索された参照データ（保存回路Ｓ１及びＳ２の参照データ）を除く他の参照データから、検索データに最も類似する参照データが検索される。検索された参照データは検索データに３番目に近いデータに相当する。
【０１５７】
以上のとおり、連想メモリ２００は、ｊ回目（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までにＨレベルの判定信号ＪＳｉを出力した判定回路ＪＣｉに対応する発振回路ＯＣｉの出力を無効化する。これにより、検索処理を実行するごとに、検索データに近い参照データを、検索データに近い順に検索することができる。
【０１５８】
［第６の実施の形態］
第５の実施の形態による連想メモリ２００は、フィードバック回路５０を用いて発振回路ＯＣｉの出力を無効化することにより、検索データに近い参照データを検索データに近い順に複数検索できる。しかしながら、１回の検索処理で１つの参照データしか検索できない。したがって、検索データに近い参照データの複数検索する場合、希望する参照データ数と同じ回数の検索処理を実行しなければならない。
【０１５９】
図１６に本実施の形態による連想メモリ３００の機能ブロック図を示す。図１６を参照して、連想メモリ３００は、連想メモリ１００と比較して、ＷＴＡ回路２０に代えて、カウンタ部４０を備える。
【０１６０】
カウンタ部４０は、複数のカウンタ回路４１〜４Ｒを備える。カウンタ回路４１は、発振回路ＯＣ１のパルス信号Ｐ１を受ける。そして、パルス信号Ｐ１のパルスをカウントする。カウント数が所定数ＣＴ（たとえば１０個）となったとき、カウント回路４１はＨレベルの判定信号ＪＳ１を出力する。
【０１６１】
同様に、カウンタ回路４２〜４Ｒはそれぞれ、発振回路ＯＣ２〜ＯＣＲのパルス信号Ｐ２〜ＰＲを受ける。そして、各パルス信号Ｐ２〜ＰＲのパルスをカウントする。カウント数が所定数ＣＴとなったとき、カウンタ回路４２〜４ＲはＨレベルの判定信号ＪＳ２〜ＪＳＲを順次出力する。
【０１６２】
上述のとおり、発振回路ＯＣ１〜ＯＣＲは、対応する参照データが検索データに類似するほど、パルス信号Ｐ１〜ＰＲの発振周波数を高くする。カウンタ回路４１〜４Ｒは、発振周波数が高いパルス信号Ｐ１〜ＰＲを受けるほど早く、Ｈレベルの判定信号ＪＳ１〜ＪＳＲを出力する。したがって、判定信号ＪＳ１〜ＪＳＲは、対応する参照データが検索データに類似する順に、順次Ｈレベルに立ち上がる。Ｈレベルの判定信号ＪＳ１〜ＪＳＲの出力順に基づいて、カウンタ部４０は、検索データに近い参照データを、検索データに近い順に決定できる。
【０１６３】
以上のとおり、連想メモリ３００は、１回の検索処理で、検索データに近い参照データを複数個検索することができる。
【０１６４】
［第７の実施の形態］
上述の実施の形態では、ハミング距離を適用した場合の連想メモリについて説明した。しかしながら、本発明による連想メモリは、マンハッタン距離にも適用できる。
【０１６５】
図１７を参照して、連想メモリ４００は、連想メモリ１００と同様に、メモリアレイ部１０と、ＷＴＡ回路２０とを備える。
【０１６６】
メモリアレイ部１０は、図１と同様に、メモリ部１と、行デコーダ２と、列デコーダ３と、Ｒｅａｄ／Ｗｒｉｔｅ回路４と、検索データ保存回路５とを備える。
【０１６７】
メモリ部１内のユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷの各々は、参照データをＫビット単位で保存する。
【０１６８】
ここで、第ｉ行（１≦ｉ≦Ｒ）に配置されたユニットデータ保存回路ＵＳｉｊ（１≦ｊ≦ｗ）に注目する。第ｉ行の保存回路Ｓｉに保存された参照データＲＥＦｉのうち、ユニットデータ保存回路ＵＳｉｊに保存されたデータを参照データＲＥＦｉｊとする。つまり、第ｉ行に保存された参照データＲＥＦｉは、ＲＥＦｉ１、ＲＥＦｉ２、・・・ＲＥＦｉｊ、・・・ＲＥＦｉｗで構成される。また、外部から入力される検索データをＳＷとする。検索データＳＷは、ＳＷ１、ＳＷ２、・・・ＳＷｊ、・・・ＳＷｗで構成される。
【０１６９】
検索データＳＷと参照データＲＥＦｉとの間のマンハッタン距離は、次の式（１）で示される。
【数１】
上述のとおり、ユニットデータ保存回路ＵＳｉｊはｋビットの参照データＲＥＦｉｊを保存する。そのため、ユニットデータ保存回路ＵＳｉｊはｋ個の記憶回路（たとえばＳＲＡＭ素子）を備える。各記憶回路は、参照データＲＥＦｉｊの各桁の参照ビットデータ（第１桁の参照ビットデータ〜最上位（第ｋ桁）の参照ビットデータ）をそれぞれ記憶する。
【０１７０】
ユニットデータ比較回路ＵＣｉｊは、対応するユニットデータ保存回路ＵＳｉｊに保存された参照データＲＥＦｉｊ（ｋビット）と、検索データＳＷｊ（ｋビット）とのマンハッタン距離を算出する。
【０１７１】
図１８に、第１行（ｉ＝１）に配置されるユニットデータ保存回路とユニットデータ比較回路と発振回路との機能ブロック図を示す。
【０１７２】
ユニットデータ保存回路ＵＳ１１は、Ｋ個の記憶回路ＳＲＡＭ１１〜ＳＲＡＭ１Ｋを備える。記憶回路ＳＲＡＭ１１には、参照データＲＥＦ１１の第１桁目の参照ビットデータが記憶されている。同様に、記憶回路ＳＲＡＭ１Ｋには、参照データＲＥＦ１１の第Ｋ桁目の参照ビットデータが記憶されている。
【０１７３】
ユニットデータ比較回路ＵＣ１１は、Ｋビット減算器４１０と、絶対値演算回路４２０とを備える。Ｋビット減算器４１０及び絶対値演算回路４２０は、検索データＳＷ１と参照データＲＥＦ１１との差の絶対値を算出する。
【０１７４】
具体的には、Ｋビット減算器４１０は、参照データＲＥＦ１１の第１桁目の参照ビットデータと、検索データＳＷ１の第１桁目の検索ビットデータとを差分する。そして、絶対値演算回路４２０は、その差分値を絶対値に換算し、出力信号ＯＪ１及び／ＯＪ１として出力する。出力信号／ＯＪ１は出力ＯＪ１の反転信号である。
【０１７５】
同様に、Ｋビット減算器４１０は、参照データＲＥＦ１１の第２桁目の参照ビットデータと検索データＳＷ１の第２桁目の検索ビットデータとを差分する。そして、絶対値演算回路４２０は、その差分値を絶対値に換算し、出力信号ＯＪ２及び／ＯＪ２として出力する。Ｋビット減算器４１０及び絶対値演算回路４２０は、参照データＲＥＦ１１の第３桁目以降のビットデータについても同様に算出し、出力信号ＯＪ３〜ＯＪＫ及び／ＯＪ３〜／ＯＪＫを出力する。
【０１７６】
同じ第１行のデータユニット保存回路ＵＳ１１〜ＵＳ１Ｗに格納された参照データＲＥＦ１１〜ＲＥＦ１Ｗと検索データＳＷ１〜ＳＷｗの比較結果（出力信号ＯＪ１〜ＯＪＫ×Ｗ個分）は、全て、同じ発振回路ＯＣＭ１に入力される。
【０１７７】
発振回路ＯＣＭ１は、比較回路Ｃ１の比較結果、つまり、求められた参照データＲＥＦ１と検索データＳＷとのマンハッタン距離に応じて、出力するパルス信号Ｐ１の発振周波数を決定する。
【０１７８】
発振回路ＯＣＭ１の機能ブロック図を図１９に示す。発振回路ＯＣＭ１は偶数個の遅延回路ＤＬ１０１〜ＤＬ１０Ｗと、ＮＡＮＤゲート３００とを備える。偶数個の遅延回路ＤＬ１０１〜ＤＬ１０ＷとＮＡＮＤゲート３００とは、動作時に、入力信号を反転する反転回路として機能する。したがって、発振回路ＯＣＭ１は、ループ状に直列に連結された複数の反転回路を備える。遅延回路ＤＬ１０１の出力は外部に出力されると共に、ＮＡＮＤゲート３００に入力される。つまり、遅延回路ＤＬ１０１〜ＤＬ１０Ｗ及びＮＡＮＤゲート３００はリングオシレータを構成する。
【０１７９】
遅延回路ＤＬ１０１はデータユニット保存回路ＵＳ１１に対応する。遅延回路ＤＬ１０２はデータユニット保存回路ＵＳ１２に対応する。以降、同様に、遅延回路ＤＬ１０３〜ＤＬ１０Ｗは、データユニット保存回路ＵＳ１３〜ＵＳ１Ｗにそれぞれ対応する。
【０１８０】
遅延回路ＤＬ１０１の構成を図２０に示す。遅延回路ＤＬ１０１は、複数の遅延回路ＤＪ１〜ＤＪＫと、インバータＩ５０とを備える。遅延回路ＤＪ１〜ＤＪＫ及びインバータＩ５０は直列に接続される。
【０１８１】
遅延回路ＤＪ１は、遅延段ＤＥＬ１と段数選択回路５５とを備える。遅延段ＤＥＬ１は、直列に接続された複数のインバータで構成される。遅延回路ＤＪ１は、出力信号ＯＪ１に応じて、利用するインバータ段数を選択する。換言すると、遅延回路ＤＪ１は、信号ＯＪ１に応じて遅延段ＤＥＬ１を利用するか否かを選択する。
【０１８２】
距離判定回路ＤＪ１は、遅延回路ＤＬ１０２からの出力を受ける。そして、ユニットデータ比較回路ＵＣ１１から出力された信号ＯＪ１及び／ＯＪ１に基づいて、ユニットデータ保存回路ＵＳ１１に保存された参照データＲＥＦ１１のうち、第１桁目の参照ビットデータの距離を求める。参照データＲＥＦ１１の第１桁目の参照ビットデータが、検索データＳＷ１の第１桁目の検索ビットデータと一致するとき、信号ＯＪ１はＨレベルとなり、信号／ＯＪ１はＬレベルとなる。一方、参照データＲＥＦ１１の第１桁目の参照ビットデータが、検索データＳＷ１の第１桁目の検索ビットデータと一致しないとき、信号ＯＪ１はＬレベルとなり、信号／ＯＪ１はＨレベルとなる。
【０１８３】
段数選択回路５５は、トランスファゲートＧＴ１０とＧＴ１１とを備える。トランスファゲートＴＧ１０及びＴＧ１１は並列に接続される。遅延段ＤＥＬ１は、遅延回路ＤＪ１の入力端子とトランスミッションゲートＧＴ１０との間に接続される。
【０１８４】
参照データＲＥＦ１１の第１桁目の参照ビットデータと検索データＳＷ１の第１桁目の検索ビットデータとが一致するとき、トランスファゲートＴＧ１１がオンになり、ＴＧ１０がオフになる。この場合、入力信号は遅延段ＤＥＬ１を通らずにトランスファゲートＧＴ１１を通過し、外部に出力される。
【０１８５】
一方、参照データＲＥＦ１１の第１桁目の参照ビットデータと検索データＳＷ１の第１桁目の検索ビットデータとが一致しないとき、トランスファゲートＧＴ１０がオンになる。この場合、入力信号は遅延段ＤＥＬ１により設定された遅延時間ΔＴ１だけ遅延して、外部に出力される。
【０１８６】
要するに、遅延回路ＤＪ１は、２通りの遅延時間を設定でき、参照ビットデータと検索ビットデータとが異なる場合に２通りの遅延時間のうち、長い方の遅延時間を選択する。
【０１８７】
遅延回路ＤＪ２〜ＤＪＫも遅延回路ＤＪ１と同様に動作する。各遅延回路ＤＪ２〜ＤＪｋは、２通りの遅延時間を設定でき、参照ビットデータと検索ビットデータとの比較結果に応じて２通りの遅延時間のいずれかを選択する。そのため、遅延回路ＤＬ１０１は、ｋビットの参照ビットデータとｋビットの検索ビットデータとの比較結果に基づいて、２ｋ通りの遅延時間を設定できる。換言すると、遅延回路ＤＬ１０１は、互いに遅延時間の異なる２ｋ通りのパスを備え、ｋ個の参照ビットデータとｋ個の検索ビットデータとのマンハッタン距離に応じてパスを選択する。
遅延回路ＤＪ２内の遅延段の遅延時間は、遅延段ＤＥＬ１の２倍とする。つまり、桁が上がるに従って遅延時間ΔＴを長く設定する。これにより、桁が最上位ビットに近いほど、長い遅延時間が設定される。つまり、マンハッタン距離が大きい程、遅延時間が長くなる。
【０１８８】
各遅延回路ＤＬ１０２〜ＤＬ１０Ｗも、遅延回路ＤＬ１０１と同じ構成を有し、同様の動作をする。そのため、発振回路ＯＣＭ１は、保存回路Ｓ１に保存された参照データと検索データとのマンハッタン距離に応じた発振周波数の信号を出力する。具体的には、参照データと検索データとのマンハッタン距離が近い程、高い発振周波数の信号を出力する。
【０１８９】
上述では第１行の保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＭ１の構成及び動作を説明した。しかしながら、第２行目以降の保存回路Ｓ２〜ＳＲ、比較回路Ｃ２〜ＣＲ及び発振回路ＯＣＭ２〜ＯＣＭＲの構成及び動作も、保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＭ１と同様である。
【０１９０】
したがって、連想メモリ４００は、連想メモリ１００と同様に、距離に応じて発振周波数を変更できる。
【０１９１】
［第８の実施の形態］
本発明による連想メモリは、ハミング距離やマンハッタン距離だけでなく、ユークリッド距離にも適用できる。
【０１９２】
ユークリッド距離に適用される連想メモリの構成は、連想メモリ４００と同様である。メモリ部１内のユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷの各々は、参照データをＫビット単位で保存する。第ｉ行の保存回路Ｓｉに保存された参照データＲＥＦｉのうち、ユニットデータ保存回路ＵＳｉｊに保存されたデータを参照データＲＥＦｉｊとする。つまり、第ｉ行に保存された参照データＲＥＦｉは、ＲＥＦｉ１、ＲＥＦｉ２、・・・ＲＥＦｉｊ、・・・ＲＥＦｉｗで構成される。また、外部から入力される検索データをＳＷとする。検索データＳＷは、ＳＷ１、ＳＷ２、・・・ＳＷｊ、・・・ＳＷｗで構成される。
【０１９３】
検索データＳＷと参照データＲＥＦｉとの間のユークリッド距離は、次の式（２）で示される。
【数２】
ユニットデータ保存回路ＵＳｉｊはＫビットの参照データＲＥＦｉｊを保存する。そのため、ユニットデータ保存回路ＵＳｉｊはＫ個の記憶回路（ＳＲＡＭ素子）を備える。各記憶回路は、参照データＲＥＦｉｊの各桁のビットデータ（第１桁のビットデータ〜最上位（第ｋ桁）ビットデータ）をそれぞれ記憶する。
【０１９４】
ユニットデータ比較回路ＵＣｉｊは、対応するユニットデータ保存回路ＵＳｉｊに保存された参照データＲＥＦｉｊ（ｋビット）と、検索データＳＷｊ（ｋビット）とのユークリッド距離を算出する。
【０１９５】
図２１に、第１行（ｉ＝１）に配置されるユニットデータ保存回路とユニットデータ比較回路と発振回路との機能ブロック図を示す。
【０１９６】
ユニットデータ保存回路ＵＳ１１は、Ｋ個の記憶回路ＳＲＡＭ１１〜ＳＲＡＭ１Ｋを備える。記憶回路ＳＲＡＭ１１には、参照データＲＥＦ１１の第１桁目のビットデータが記憶されている。同様に、記憶回路ＳＲＡＭ１Ｋには、参照データＲＥＦ１１の第Ｋ桁目のビットデータが記憶されている。
【０１９７】
ユニットデータ比較回路ＵＣ１１は、Ｋビット減算器４１０と、絶対値演算回路４２０と、比較電流信号生成回路４３０と、アナログスクエア回路４４０と、Ａ／Ｄコンバータ４５０とを備える。
【０１９８】
Ｋビット減算器４１０及び絶対値演算回路４２０は、検索データＳＷ１と参照データＲＥＦ１１との差の絶対値を算出する。算出結果は、対応する比較電流信号生成回路４３０で絶対値に応じた値のアナログ電流に変換される。
【０１９９】
変換されたアナログ電流はアナログスクエア回路４４０で２乗される。これにより、参照データＲＥＦ１１と、検索データＳＷ１とのユークリッド距離がアナログ電流値で出力される。
【０２００】
Ａ／Ｄコンバータ４５０は、出力されたアナログ電流をデジタル変換する。これにより、ユークリッド距離がｎビットのデジタルデータで出力される。
【０２０１】
発振回路ＯＣＥ１は、発振回路ＯＣ１やＯＣＭ１と同様に、ユークリッド距離に応じた発振周波数のパルス信号Ｐ１を出力する。発振回路ＯＣＥ１は、複数のインバータからなる遅延段と、段数選択回路とを備える。発振回路ＯＣＥ１内の段数選択回路は、ユークリッド距離が小さいほど、使用するインバータ段数を少なく選択する。そのため、ユークリッド距離が小さいほど高い発信周波数のパルス信号Ｐ１が出力される。
【０２０２】
第１行の保存回路Ｓ１内の他のユニットデータ保存回路ＵＳ１２〜ＵＳ１Ｗ、ユニットデータ比較回路ＵＣ１２〜ＵＣ１Ｗの動作も上述の通りである。また、第２行目以降の保存回路Ｓ２〜ＳＲ、比較回路Ｃ２〜ＣＲ及び発振回路ＯＣＥ２〜ＯＣＥＲの構成及び動作も、保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＥ１と同様である。したがって、ユークリッド距離を適用した連想メモリも、連想メモリ１００と同様に、距離に応じて発振周波数を変更できる。
【０２０３】
［第９の実施の形態］
上述の実施の形態において、ＷＴＡ回路２０（図５）やＷＴＡ回路２５（図９）について説明した。しかしながら、ＷＴＡ回路は、図５や図９に限定されない。
図２２は、ＷＴＡ回路の他の例を示す。図２２を参照して、ＷＴＡ回路３５０は、検知回路３５１と、複数の判定回路ＪＣ１１〜ＪＣ１Ｒとを備える。判定回路ＪＣ１１は発振回路ＯＣ１に対応し、発振回路ＯＣ１の出力信号を受ける。同様に、判定回路ＪＣ１２は発振回路ＯＣ２に対応し、発振回路ＪＣ１Ｒは発振回路ＯＣＲに対応する。
判定回路ＪＣ１１は、判定回路ＪＣ１と比較して、放電回路２５０及びクロック生成回路２５３を有さない。他の構成は判定回路ＪＣ１と同じである。判定回路ＪＣ１２〜ＪＣ１Ｒの構成は、判定回路ＪＣ１１と同じである。
検知回路３５１は、発信回路ＯＣ１〜ＯＣＲの出力を受け、最も早く出力されたパルス信号を検知する。検知回路３５１は、最も早く出力されたパルス信号を受けたとき、検知信号を出力する。より具体的には、検知回路３５１は、各判定回路ＪＣ１１〜ＪＣ１Ｒ内のインバータＩ２０の出力を受ける。そして、いずれかのインバータＩ２０から最初にパルス信号を受けたとき、検知信号を出力する。
判定回路ＪＣ１１〜ＪＣ１２内のラッチ回路２５２は、インバータＩ２０の出力を受ける。つまり、対応する発振回路ＯＣ１〜ＯＣＲの出力信号を受ける。そして、検知信号を受けたとき、発信回路ＯＣ１〜ＯＣＲからの出力信号をラッチする。
判定回路ＪＣ１１が、最も早くパルス信号を受けるとき（つまり、発振回路ＯＣ１が最も周波数の高いパルス信号を出力するとき）、判定回路ＪＣ１１内のラッチ回路２５２は、Ｈレベルの信号をラッチする。そして、他の判定回路ＪＣ１２〜ＪＣ１Ｒ内のラッチ回路２５２は、Ｌレベルの信号をラッチする。以上の結果、判定回路ＪＣ１１はＷｉｎｎｅｒを示すＨレベルの判定信号ＪＳ１を出力し、他の判定回路ＪＣ１２〜ＪＣ１Ｒは、Ｌｏｏｓｅｒを示す判定回路ＪＳ２〜ＪＳＲを出力する。
検知回路３５０は、各判定回路ＪＣ１１〜ＪＣ１Ｒ内のインバータＩ２０の出力を受けるワイヤードＯＲ回路であってもよいし、複数段のＯＲ回路で構成されてもよい。
以上、本発明の実施の形態を説明したが、上述した実施の形態は本発明を実施するための例示に過ぎない。よって、本発明は上述した実施の形態に限定されることなく、その趣旨を逸脱しない範囲内で上述した実施の形態を適宜変形して実施することが可能である。
【符号の説明】
【０２０４】
１ メモリ部
２ 行デコーダ
３ 列デコーダ
４ Ｒｅａｄ／Ｗｒｉｔｅ回路
５ 検索データ保存回路
１０ メモリアレイ部
２０ ＷＴＡ回路
３０ プリチャージ回路
３５ 分周部
３１ クロック生成回路
４０ カウンタ部
５０ フィードバック回路
１００，１１０，２００，３００，４００ 連想メモリ
２５０ 放電回路
Ｓ１〜ＳＲ 保存回路
Ｃ１〜ＣＲ 比較回路
【技術分野】
【０００１】
本発明は、最小距離検索機能を有する連想メモリに関する。
【背景技術】
【０００２】
画像圧縮及び画像認識の分野において、最小距離検索機能を有する連想メモリが注目されている。連想メモリはＷビット幅Ｒ個の参照データを記憶する（Ｗ及びＲは自然数）。データ列（検索データ）が入力されたとき、連想メモリは、複数の参照データの中から最も類似した（距離の近い）データを検索する。
【０００３】
入力されたデータ列と最も類似の参照データを見つけることは、パターンマッチングにおいて基本的な処理である（非特許文献１参照）。したがって、画像圧縮や画像認識等の情報処理において、最小距離検索連想メモリは有用である。最小距離検索連想メモリはたとえば、特許文献１に開示されている。さらに、ハミング距離、マンハッタン距離及びユークリッド距離の検索機能を有する全並列型の連想メモリが特許文献２、非特許文献２及び非特許文献３に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２８８９８５号公報
【特許文献２】特開２００５−２０９３１７号公報
【非特許文献】
【０００５】
【非特許文献１】D. R. Tveter, "The Pattern RecognitionBasis of Artificial Intelligence," Los Alamitos, CA: IEEE computersociety, 1998.
【非特許文献２】H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, "Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance," IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002.
【非特許文献３】H. J. Mattausch, N. Omori, S. Fukae, T.Koide and T. Gyohten, "Fully-Parrallel Pattern-Matching Engine with Dynamic Adaptibility to Hamming or ManhattanDistance," 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002.
【非特許文献４】M. Ikeda, et al., "Time-domain minimum-distance detector and its application to low-power coding schema on chip- interface," Proc. of ESSCIRC '97, pp.464-467, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の連想メモリは、メモリアレイ部と、Ｗｉｎｎｅｒ Ｌｉｎｅ−ｕｐ増幅回路（Winner Line-up Amplifier：以下、ＷＬＡという）と、Ｗｉｎｎｅｒ Ｔａｋｅ Ａｌｌ回路（以下、ＷＴＡという）とを備える。メモリアレイ部は、行列状に配置されたメモリセルを備える。メモリアレイ部の同じ行に配列された複数のメモリセルは、Ｗビット幅の参照データを記憶する。メモリアレイ部はさらに、各々が各行に対応した複数の比較回路を備える。比較回路は、対応する行のメモリセルに記憶された参照データと、外部から入力された検索データとの距離に応じた比較電流信号を生成する。
【０００７】
ＷＬＡ回路は、各々が各比較回路に対応した複数の電流電圧変換回路を備える。各電流電圧変換回路は、対応する比較回路から出力された比較電流信号を電圧に変換する。ＷＬＡ回路は、変換された複数の電圧のうち、電圧レベルが最も低い電圧をＷｉｎｎｅｒとして所定の電圧ＶＷに増幅する。そして、それ以外の電圧をＬｏｓｅｒとして所定の電圧ＶＬに増幅する。ここで、Ｗｉｎｎｅｒは、検索データに最も類似する参照データに対応する。そして、Ｌｏｓｅｒは、検索データに最も類似する参照データ以外の他の参照データに対応する。ＷＴＡ回路は、ＷＬＡ回路から受けた電圧をさらに増幅して出力する。連想メモリでは、電圧ＶＷに増幅された行のメモリセルに記憶された参照データが検索データに最も類似した参照データに決定される。
【０００８】
変換された複数の電圧を電圧ＶＷ及び電圧ＶＬに増幅するために、ＷＬＡ回路は、各行に対応して配置されたトランジスタ素子を用いて、各電圧が所定のしきい値電圧Ｖｒｅｆよりも大きいか否かを判定する。そして、しきい値電圧Ｖｒｅｆよりも小さい電圧を電圧ＶＷに増幅し、しきい値電圧Ｖｒｅｆよりも大きい電圧を電圧ＶＬに増幅する。
【０００９】
上述の電圧判定に用いられるトランジスタ素子の特性は、各行で一致している必要がある。しかしながら、トランジスタ素子の特性はどうしてもばらつく。特性が異なるトランジスタを電圧判定に用いれば、本来電圧ＶＷに増幅されないはずの行で、電圧ＶＷに増幅されてしまう場合が生じる。要するに、各行の比較電流信号を電圧に変換することで参照データを検索する従来の連想メモリでは、誤検索が生じる場合がある。
【００１０】
本発明の目的は、誤検索を抑制できる連想メモリを提供することである。
【課題を解決するための手段及び発明の効果】
【００１１】
本発明による連想メモリは、保存手段と、比較手段と、パルス生成手段と、決定手段とを備える。保存手段は、複数の参照データを保存する。比較手段は、入力された検索データと、複数の参照データの各々とを並列に比較して、検索データと参照データとの距離を、参照データごとに求める。パルス生成手段は、求めた距離に応じた周波数を有するパルス信号を参照データごとに生成する。決定手段は、生成された複数のパルス信号の周波数に基づいて、複数の参照データのうち、検索データに最も近い参照データを決定する。
【００１２】
本発明による連想メモリは、従来のように、参照データと検索データとの距離を電流値や電圧値に変換せず、距離に応じた発振周波数を有するパルス信号を生成する。距離を電流値や電圧値に変換するといったアナログ処理を行わないため、トランジスタ素子特性のばらつきに起因した誤検索が生じにくい。
【００１３】
好ましくは、パルス生成手段は、複数の参照データに対応した複数の発振手段を備える。各発振手段は、検索データと前記対応する参照データとの距離が小さいほど、周波数の高いパルス信号を出力する。決定手段は、発振周波数の最も高いパルス信号を出力した発振手段に対応した参照データを、検索データに最も近い参照データに決定する。
【００１４】
より好ましくは、決定手段はさらに、複数の発振手段に対応した複数の判定手段を備える。決定手段は、複数の判定手段のうち、発振手段からのパルス信号を最も早く受信した判定手段に基づいて、検索データに最も近い参照データを決定する。
【００１５】
この場合、電流電圧差ではなく、パルス信号を受ける時間差に基づいて検索データに最も近い参照データを決定する。そのため、トランジスタ素子特性のばらつきの影響を受けにくい。
【００１６】
好ましくは、連想メモリはさらに、発振回路に対応した複数の分周手段を備える。各分周手段は、対応する発振手段から出力されたパルス信号を所定の分周比で分周して、対応する判定手段に出力する。
【００１７】
この場合、決定手段は、最も早く受信したパルス信号をより精度良く特定できる。
【００１８】
好ましくは、決定手段はさらに、複数の判定手段に接続されたラッチ指示ノードと、ラッチ指示ノードを充電する充電手段とを備える。各判定手段は、放電手段と、ラッチ手段とを備える。放電手段は、対応する発振手段からの出力信号を受け、出力信号がパルス信号であるときラッチ指示ノードを放電する。ラッチ手段は、ラッチ指示ノードが放電されたときに放電手段が受けている出力信号をラッチする。
【００１９】
この場合、最も早くパルス信号を受信した判定手段が出力する出力信号のレベルと、その他の判定手段が出力する出力信号のレベルとを異なるレベルにできる。
【００２０】
好ましくは、決定手段は、トーナメント式に接続された複数の判定手段を備える。第１段目に配置された複数の判定手段の各々は、複数の第１のパルス判定手段と、パルス受付判定ノードと、充電手段とを備える。第１のパルス判定手段は、対応する発振手段の出力信号を受ける。パルス受付判定ノードは、複数の第１のパルス判定手段に接続される。充電手段は、パルス受付判定ノードを充電する。第１のパルス判定手段は、第１の放電手段と、ラッチ手段とを備える。第１の放電手段は、対応する発振手段の出力信号としてパルス信号を受けたとき、パルス受付ノードを放電する。ラッチ手段は、クロック信号を受けたとき第１の放電手段が受けている出力信号をラッチする。第２段目以降に配置されたトーナメント判定手段は、複数の第２のパルス判定手段と、パルス受付判定ノードと、充電手段とを備える。第２のパルス判定手段は、前段の対応するトーナメント判定手段のパルス受付判定ノードに接続される。パルス受付判定ノードは、複数の第２のパルス判定手段が接続される。第２のパルス判定手段は第２の充電手段を備える。第２の充電手段は、前段の対応する判定手段のパルス受付判定ノードが放電されたとき、パルス受付ノードを放電する。最上段の判定手段はさらに、クロック生成手段を備える。クロック生成手段は、パルス受付判定ノードが放電されたとき、クロック信号を出力する。
【００２１】
この場合、各パルス受付判定ノードの負荷容量を小さくすることができる。そのため、パルス信号を受けてからクロック信号が出力されるまでの時間を短縮できる。
【００２２】
好ましくは、発信手段は、直列に接続された複数のインバータと、段数選択手段とを備える。段数選択手段は、検索データと対応する参照データとの距離に応じて、インバータの段数を選択する。
【００２３】
この場合、インバータの段数に応じて発振周波数を調整できる。
【００２４】
好ましくは、決定手段は、複数の発振手段に対応する複数のカウンタ手段を備える。カウント手段は、対応する発振手段からパルス信号を受け、受けたパルスの総数をカウントし、所定数のパルスを受けたとき活性化された出力信号を生成する。
【００２５】
この場合、検索データに類似した参照データを、検索データに類似する順に順次決定することができる。
【００２６】
好ましくは、連想メモリはさらに、パルス無効化手段を備える。パルス無効化手段は、ｊ（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までに決定手段により決定された参照データに対応する発振手段から出力されるパルス信号を無効化する。
【００２７】
この場合、検索データに類似した参照データを、検索データに類似する順に順次決定することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図２】図１中のユニットデータ保存回路とユニットデータ比較回路の回路図である。
【図３】図１中の発振回路の構成を示す機能ブロック図である。
【図４】図３中の遅延回路の回路図である。
【図５】図１中のＷＴＡ回路の回路図である。
【図６】図３に示した発振回路内のインバータの段数と発信周波数のばらつきとの関係を示す図である。
【図７】本発明の第２の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図８】図７中の分周回路を用いた場合のパルス信号の波形の変化を説明するための図である。
【図９】本発明の第３の実施の形態による連想メモリのＷＴＡ回路の回路図である。
【図１０】本発明の第４の実施の形態による連想メモリの発振回路の構成を示す機能ブロック図である。
【図１１】図１０中の遅延回路の回路図である。
【図１２】図１１と異なる他の遅延回路の回路図である。
【図１３】図１１及び図１２と異なる他の遅延回路の回路図である。
【図１４】図１１〜図１３と異なる他の遅延回路の回路図である。
【図１５】本発明の第５の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１６】本発明の第６の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１７】本発明の第７の実施の形態による連想メモリの全体構成を示す機能ブロック図である。
【図１８】図１７中のメモリアレイ部内の第１行目の保存回路、比較回路及び発振回路の構成を示す機能ブロック図である。
【図１９】図１８中の発振回路の構成を示す機能ブロック図である。
【図２０】図１９中の遅延回路の構成を示す機能ブロック図である。
【図２１】本発明の第８の実施の形態による連想メモリのメモリアレイ部内の第１行目の保存回路、比較回路及び発振回路の構成を示す機能ブロック図である。
【図２２】本発明の第９の実施の形態による連想メモリのＷＴＡ回路の構成を示す機能ブロック図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照し、本発明の実施の形態を詳しく説明する。図中同一又は相当部分には同一符号を付してその説明は繰り返さない。
【００３０】
［第１の実施の形態］
［全体構成］
図１を参照して、本発明の実施の形態による連想メモリ１００は、メモリアレイ部１０と、ＷＴＡ（Winner Take All）回路２０とを備える。
【００３１】
メモリアレイ部１０は、メモリ部１と、行デコーダ２と、列デコーダ３と、Ｒｅａｄ／Ｗｒｉｔｅ回路４と、検索データ保存回路５とを備える。
【００３２】
メモリ部１は、ユニットデータ保存回路（Ｕｎｉｔ Ｓｔｒａｇｅ：ＵＳ）ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷを備える。ここで、Ｗは２以上の自然数であり、Ｒは２以上の自然数である。以降の説明では、任意のユニットデータ保存回路をＵＳｉｊ（１≦ｉ≦Ｗ、１≦ｊ≦Ｒ）と記載する。
【００３３】
ユニットデータ保存回路（Ｕｎｉｔ Ｓｔｒａｇｅ：ＵＳ）ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷは、行列状に配置される。同じ行に配列された複数のユニットデータ保存回路ＵＳｉｊは保存回路Ｓｉを構成する。たとえば、第１行に配列されたユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗは、保存回路Ｓ１を構成する。同様に、第２行に配列されたユニットデータ保存回路ＵＳ２１〜ＵＳ２Ｗは、保存回路Ｓ２を構成し、第Ｒ行に配列されたユニットデータ保存回路ＵＳＲ１〜ＵＳＲＷは、保存回路ＳＲを構成する。
【００３４】
各行の保存回路ＳｉはＷビット幅の参照データを記憶する。具体的には、第１行に対応した保存回路Ｓ１は、Ｗビット幅の参照データを記憶する。第２行に対応した保存回路Ｓ２は、保存回路Ｓ１が保存する参照データと異なる他の参照データを記憶する。保存回路Ｓｉ内の複数
のユニットデータ保存回路ＵＳｉｊの各々は、参照データのうちの対応する１ビットデータを記憶する。
【００３５】
メモリ部１はさらに、各保存回路Ｓ１〜ＳＲに対応した複数の比較回路Ｃ１〜ＣＲを備える。
比較回路Ｃ１は、第１行に配置された保存回路Ｓ１に対応する。比較回路Ｃ２は、第２行に配置された保存回路Ｓ２に対応する。同様に、比較回路ＣＲは、第Ｒ行に配置された保存回路ＳＲに対応する。
【００３６】
比較回路Ｃ１は、複数のユニットデータ比較回路（Ｕｎｉｔ Ｃｏｍｐａｒａｔｏｒ：ＵＣ）ＵＣ１１〜ＵＣ１Ｗを備える。同様に、第２行に対応した比較回路Ｃ２は、複数のユニットデータ比較回路ＵＣ２１〜ＵＣ２Ｗを備える。同様に、第３行〜第Ｒ行に対応した比較回路Ｃ３〜ＣＲは、複数のユニットデータ比較回路ＵＣ３１〜ＵＣ３Ｗ、・・・、ＵＣＲ１〜ＵＣＲＷを備える。
【００３７】
ユニットデータ比較回路ＵＣ１１〜ＵＣ１Ｗは、それぞれ、ユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗに対応して配置される。ユニットデータ比較回路ＵＣ２１〜ＵＣ２Ｗは、それぞれ、ユニットデータ保存回路ＵＳ２１〜ＵＳ２Ｗに対応して配置される。以下、同様にして、ユニットデータ比較回路ＵＣ３１〜ＵＣ３Ｗ、・・・、ＵＣＲ１〜ＵＣＲＷは、それぞれ、ユニットデータ保存回路ＵＳ３１〜ＵＳ３Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷに対応して配置される。
【００３８】
以降の説明では、任意の比較回路をＣｉ、任意のユニットデータ比較回路をＵＣｉｊと記載する。
【００３９】
各行の比較回路Ｃｉは、外部からＷビット幅の検索データを受け付ける。そして、検索データと、対応する保存回路Ｓｉに保存されたＷビット幅の参照データとを比較する。より具体的には、比較回路Ｃｉは、検索データと参照データとの距離（本例ではハミング距離）を求める。各行の参照データと検索データとの比較は、並列に実行される。つまり、各比較回路Ｃｉは、対応する第ｉ行の参照データと検索データとの比較を、並列（同時）に実行する。
【００４０】
メモリ部１はさらに、パルス生成回路を備える。パルス生成回路は、複数の発振回路（Ｏｓｃｉｌｌａｔｉｎｇ Ｃｉｒｃｕｉｔ：ＯＣ）ＯＣ１〜ＯＣＲを備える。以降、任意の発振回路をＯＣｉと記載する。
【００４１】
各発振回路ＯＣｉは、各行に配置される。具体的には、発振回路ＯＣ１は、保存回路Ｓ１及び比較回路Ｃ１に対応する。発振回路ＯＣ２は、保存回路Ｓ２及び比較回路Ｃ２に対応する。同様に、発振回路ＯＣＲは、保存回路ＳＲ及び比較回路ＣＲに対応する。
【００４２】
発振回路ＯＣｉは、比較回路Ｃｉにより求められたハミング距離に応じた発振周波数を有するパルス信号Ｐｉを出力する。具体的には、発振回路ＯＣ１は、第１行（保存回路Ｓ１）に保存された参照データと検索データとのハミング距離に応じた発振周波数を有するパルス信号Ｐ１を出力する。発振回路ＯＣ２は、第２行の参照データと検索データとのハミング距離に応じた発信周波数を有するパルス信号Ｐ２を出力する。同様に、発信回路ＯＣＲは、第Ｒ行の参照データと検索データとのハミング距離に応じた発信周波数を有するパルス信号ＰＲを出力する。
【００４３】
要するに、複数の発振回路ＯＣ１〜ＯＣＲを備えたパルス生成回路は、各行の参照データに応じたパルス信号Ｐ１〜ＰＲを生成する。パルス信号Ｐｉの発信周波数は、対応する行（第ｉ行）の参照データと検索データとのハミング距離に対応する。具体的には、ハミング距離が小さい程、発振周波数は高く、ハミング距離が大きい程、発振周波数は低い。
【００４４】
行デコーダ２は、メモリ部１の行方向のアドレスを指定する。列デコーダ３は、メモリ部１の列方向のアドレスを指定する。Ｒｅａｄ／Ｗｒｉｔｅ回路４は、行デコーダ２及び列デコーダ３により指定されたユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷに参照データを書き込む。Ｒｅａｄ／Ｗｒｉｔｅ回路４はさらに、検索データを検索データ保存回路５に書き込む。
【００４５】
検索データ保存回路５は、Ｒｅａｄ／Ｗｒｉｔｅ回路４によって書き込まれた検索データを保存する。
【００４６】
ＷＴＡ回路２０は、パルス生成回路（発信回路ＯＣ１〜ＯＣＲ）で生成された複数のパルス信号Ｐ１〜ＰＲを受ける。ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、検索データに最も類似する参照データを決定する。ＷＴＡ回路２０は、パルス信号Ｐ１〜ＰＲのうち、発振周波数が最大のパルス信号Ｐｉを特定する。そして、特定されたパルス信号Ｐｉに対応する行（第ｉ行）に記憶された参照データを、検索データに最も類似した参照データに決定する。
【００４７】
ＷＴＡ回路２０は、複数の発振回路ＯＣ１〜ＯＣＲに対応した複数の判定回路（Judgment Circuit）ＪＣ１〜ＪＣＲを備える。以降、任意の判定回路をＪＣｉと記載する。複数の判定回路ＪＣ１〜ＪＣＲは、対応するパルス信号Ｐ１〜ＰＲを受ける。パルス信号Ｐ１〜ＰＲのうち、発振周波数が最大のパルス信号Ｐｉの電圧レベルが最も早く変化する。判定回路ＪＣ１〜ＪＣＲのうち、最も早くレベル変化したパルス信号Ｐｉを受けた判定回路ＪＣｉは、活性化された判定信号(Judgment Signal)ＪＳｉを出力する。２番目以降にレベル変化した信号Ｐｉを受けた残りの判定回路ＪＣｉは、非活性化された判定信号ＪＳｉを出力する。活性化された判定信号ＪＳは「１」を示し、電圧ＶＤＤからなる。非活性化された判定信号ＪＳｉは「０」を示し、電圧Ｖｒｅｆ（Ｖｒｅｆ＜ＶＤＤ）からなる。活性化された判定信号ＪＳｉは、対応する行（第ｉ行）の参照データが検索データに最も類似した参照データ（以降、この参照データをＷｉｎｎｅｒという）であることを示す。また、非活性化された判定信号ＪＳｉは、対応する行の参照データが検索データに最も類似した参照データではない（以降、この参照データをＬｏｓｅｒという）ことを示す。
【００４８】
たとえば、メモリ部１に記憶された複数の参照データのうち、保存回路Ｓ２に記憶された参照データが検索データに最も類似していると仮定する。この場合、パルス信号Ｐ１〜ＰＲのうち、パルス信号Ｐ２の発振周波数が最も高い。そのため、ＷＴＡ回路２０は、判定信号ＪＳ１〜ＪＳＲのうち、判定信号ＪＳ２のみを活性化し、残りの判定信号ＪＳｉを非活性化する。
【００４９】
以上のとおり、連想メモリ１００は、従来の連想メモリのように、参照データと検索データとの距離の違いを電流及び電圧差に置き換えない。代わりに、距離の違いをパルスの発振周波数の違いに置き換える。つまり、距離が異なれば発振周波数も異なる。発振周波数が異なれば、パルスが最初に立ち上がる（又は立ち下がる）時刻が異なるため、距離の違いが時間差に置き換わる。連想メモリ１００は、この時間差に基づいて、検索データに最も類似する参照データを決定する。距離の違いを電流及び電圧差に変換する場合、アナログ処理が実行される。この場合、上述のとおり、ＷｉｎｎｅｒとＬｏｓｅｒを分けるために利用されるトランジスタ素子の特性ばらつきにより誤検索が生じる場合がある。これに対して、連想メモリ１００は、距離の違いを発振周波数の違い（時間差）に置き換えてＷｉｎｎｅｒを決定する。つまり、デジタル処理によりＷｉｎｎｅｒを決定する。そのため、トランジスタ素子の特性のばらつき影響を受けにくく、誤検索が抑制される。
【００５０】
以下、保存回路Ｓｉ内のユニットデータ保存回路ＵＳｉｊと、比較回路Ｃｉ内のユニットデータ比較回路ＵＣｉｊと、パルス生成回路内の発振回路ＯＣｉと、ＷＴＡ回路２０とについて詳述する。以降の説明では、Ｗビット幅の参照データを構成する各ビットデータを参照ビットデータという。また、Ｗビット幅の参照データを構成する各ビットデータを検索ビットデータという。つまり、参照データはＷ個の参照ビットデータを有し、検索データは、参照ビットデータに対応するＷ個の検索ビットデータを有する。
【００５１】
［ユニットデータ保存回路及びユニットデータ比較回路］
図２を参照して、ユニットデータ保存回路ＵＳ１１は、ＳＲＡＭ素子を構成する。ユニットデータ保存回路ＵＳ１１は、データをラッチするラッチ回路２１０と、ｎ型ＭＯＳトランジスタ２０１、２０２とを含む。ｎ型ＭＯＳトランジスタ２０１及び２０２は直列に接続される。そして、ｎ型ＭＯＳトランジスタ２０１と２０２との間には、ラッチ回路２１０が接続される。ｎ型ＭＯＳトランジスタ２０１及び２０２のゲートは、それぞれワード線ＷＬ１に接続される。
【００５２】
ワード線ＷＬ１は行デコーダ２に接続される。行デコーダ２がワード線ＷＬ１を選択したとき、ｎ型ＭＯＳトランジスタ２０１及び２０２はオンになる。このとき、ｎ型ＭＯＳトランジスタ２０１は、外部から入力された参照データを構成する１ビットの参照ビットデータＤをラッチ回路２１０に供給する。ｎ型ＭＯＳトランジスタ２０２は、参照ビットデータＤの反転信号である参照ビットデータＤＱを受け、ラッチ回路２１０に供給する。
【００５３】
ラッチ回路２１０は、２つのインバータＩ１及びＩ２を含む。インバータＩ１の入力端子はインバータＩ２の出力端子と接続される。インバータＩ１の出力端子はインバータＩ２の入力端子と接続される。インバータＩ１はｎ型ＭＯＳトランジスタ２０１から参照ビットデータＤを受ける。インバータＩ２はｎ型ＭＯＳトランジスタ２０２から参照ビットデータＤＱを受ける。そのため、ラッチ回路２１０は１ビットの参照ビットデータＤをラッチする。参照ビットデータＤは「１」又は「０」である。参照ビットデータＤが「１」とは、ｎ型ＭＯＳトランジスタ２０１からラッチ回路２１０に供給される信号がＨレベルである場合を示し、参照ビットデータＤが「０」とは、信号がＬレベルであることを示す。
【００５４】
ユニットデータ比較回路ＵＣ１１には、外部から検索ビットデータＣＡＭが入力される。検索ビットデータＣＡＭは、検索データを構成する１ビットのデータであり、ユニットデータ保存回路ＵＳ１１に対応する。ユニットデータ比較回路ＵＣ１１は、ユニットデータ保存回路ＵＳ１１で保存されている参照ビットデータＤと、検索ビットデータＣＡＭとを比較して、距離（ハミング距離）を求める。そして、求めた距離を対応する発振回路ＯＣ１に出力する。
【００５５】
ユニットデータ比較回路ＵＣ１１は、２つのトランスファゲートＴＧ１、ＴＧ２とインバータＩ３とを含む。
【００５６】
各トランスファゲートＴＧ１、ＴＧ２は、ｎ型ＭＯＳトランジスタと、ｐ型ＭＯＳトランジスタとで構成される。トランスファゲートＴＧ１内のｐ型ＭＯＳトランジスタのゲートは、参照ビットデータＤをラッチ回路２１０から受け、ｎ型ＭＯＳトランジスタのゲートは参照ビットデータＤＱをラッチ回路２１０から受ける。トランスファゲートＴＧ２内のｐ型ＭＯＳトランジスタのゲートは、ラッチ回路２１０から参照ビットデータＤＱをラッチ回路２１０から受け、ｎ型ＭＯＳトランジスタのゲートは参照ビットデータＤをラッチ回路２１０から受ける。
【００５７】
参照ビットデータＤのレベル（「１」又は「０」）に応じて、トランスファゲートＴＧ１及びＴＧ２のいずれか一方がオンになり、他方はオフになる。トランスファゲートＴＧ１は外部から検索ビットデータＣＡＭを受ける。トランスファゲートＴＧ２は、検索ビットデータＣＡＭの反転信号である検索ビットデータＣＡＭＱを外部から受ける。
【００５８】
ノードＮ１はオンされたトランスファゲートＴＧ１又はＴＧ２から出力された信号を、パスイネーブル信号ｐａｔｈ＿ｅｎａとして出力する。インバータＩ３はパスイネーブル信号ｐａｔｈ＿ｅｎａを反転したパスイネーブル信号ｐａｔｈ＿ｅｎａｑを出力する。つまり、ユニットデータ比較回路ＵＣ１１は、２つの信号ｐａｔｈ＿ｅｎａ、ｐａｔｈ＿ｅｎａｑを出力する。２つの信号ｐａｔｈ＿ｅｎａ、ｐａｔｈ＿ｅｎａｑは、参照ビットデータＤと検索ビットデータＣＡＭとの比較結果であり、ハミング距離に相当する。
【００５９】
参照ビットデータＤと検索ビットデータＣＡＭとが一致する場合、信号ｐａｔｈ＿ｅｎａはＬレベルになり、信号ｐａｔｈ＿ｅｎａｑはＨレベルになる。たとえば、参照ビットデータＤ及び検索ビットデータＣＡＭがいずれも「１」である場合、トランスファゲートＴＧ１がオフになり、ＴＧ２がオンになる。また、参照ビットデータＤ及び検索ビットデータＣＡＭがいずでも「０」である場合、トランスファゲートＴＧ１がオンになり、ＴＧ２がオフになる。その結果、信号ｐａｔｈ＿ｅｎａはＬレベルになり、信号ｐａｔｈ＿ｅｎａｑはＨレベルになる。
【００６０】
一方、参照ビットデータＤと検索ビットデータＣＡＭとが一致しない場合、信号ｐａｔｈ＿ｅｎａはＨレベルになり、信号ｐａｔｈ＿ｅｎａｑはＬレベルになる。たとえば、参照ビットデータＤが「１」であり、検索ビットデータＣＡＭが「０」である場合、トランスファゲートＴＧ１がオフになり、ＴＧ２がオンになる。参照ビットデータＤが「０」であり、検索ビットデータＣＡＭが「１」である場合、トランスファゲートＴＧ１がオンになり、ＴＧ２がオフになる。その結果、信号ｐａｔｈ＿ｅｎａはＨレベルになり、信号ｐａｔｈ＿ｅｎａｑはＬレベルになる。
【００６１】
信号ｐａｔｈ＿ｅｎａ及びｐａｔｈ＿ｅｎａｑは、発振回路ＯＣ１生成されるパルス信号Ｐ１の発振周波数を決定する。
【００６２】
ユニットデータ保存回路ＵＳ１２〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・ＵＳＲ１〜ＵＳＲＷは、ユニットデータ保存回路ＵＳ１１と同じ構成からなる。また、ユニットデータ比較回路ＵＣ１２〜ＵＣ１Ｗ、ＵＣ２１〜ＵＣ２Ｗ、・・・ＵＣＲ１〜ＵＣＲＷは、ユニットデータ比較回路ＵＣ１１と同じ構成からなる。
【００６３】
［発振回路］
発振回路ＯＣ１は、保存回路Ｓ１に記憶されたＷビット幅の参照データとＷビット幅の検索データとの距離（ハミング距離）に応じた発振周波数のパルス信号Ｐ１を出力する。具体的には、参照データと検索データとの距離が小さい程、つまり、参照データが検索データに類似する程、発振回路ＯＣ１は、高い発振周波数のパルス信号Ｐ１を出力する。
【００６４】
図３は発振回路ＯＣ１の機能ブロック図である。図３を参照して、発振回路ＯＣ１は、複数の遅延回路(Delay Circuit)ＤＣ１１〜ＤＣ１Ｗを含む。遅延回路ＤＣ１１〜ＤＣ１Ｗはそれぞれ、ユニットデータ比較回路ＵＣ１１〜ＵＣ１Ｗに対応する。
【００６５】
遅延回路ＤＣ１１〜ＤＣ１Ｗは直列に接続される。直列された複数の遅延回路ＤＣ１１〜ＤＣ１Ｗのうち、端に位置する遅延回路ＤＣ１１の出力端子は出力ノードＮ１０に接続される。また、他方の端に位置する遅延回路ＤＣ１Ｗの入力端子は、ＮＡＮＤゲート３００の出力端子と接続される。ＮＡＮＤゲート３００は、発振回路ＯＣ１を起動する役割を有する。ＮＡＮＤゲート３００の一方の入力端子には、発振回路ＯＣ１を起動するためのイネーブル信号ＥＮＡが入力される。また他方の入力端子は出力ノードＮ１０と接続される。
【００６６】
イネーブル信号ＥＮＡが活性化（Ｈレベル）されたとき、ＮＡＮＤゲート３００は、入力信号を反転して出力する反転回路として機能する。一方、各遅延回路ＤＣ１１〜ＤＣ１Ｗは、受けた信号を反転して外部に出力する。つまり、各遅延回路ＤＣ１１〜ＤＣ１Ｗも上述の反転回路として機能する。したがって、発振回路ＯＣ１は、リング状に連結された奇数個の反転回路（起動時のＮＡＮＤゲート３００及び遅延回路ＤＣ１１〜ＤＣ１Ｗ）を備える。
【００６７】
図４に遅延回路ＤＣ１１の回路図を示す。遅延回路ＤＣ１１は、複数のインバータＩ１０〜Ｉ１４と、インバータの段数を選択する段数選択回路ＳＥとを備える。段数選択回路ＳＥは、２つのトランスファゲートＴＧ１０及びＴＧ１１を備える。トランスファゲートＴＧ１０は、Ｈレベルの信号ｐａｔｈ＿ｅｎａとＬレベルの信号ｐａｔｈ＿ｅｎａｑとを受けたときにオンする。つまり、対応するユニットデータ比較回路ＵＣ１１から出力された参照ビットデータＤと検索ビットデータＣＡＭとが一致しないとき、トランスファゲートＴＧ１０はオンする。
【００６８】
トランスファゲートＴＧ１１は、Ｌレベルの信号ｐａｔｈ＿ｅｎａとＨレベルの信号ｐａｔｈ＿ｅｎａｑとを受けたときにオンする。つまり、参照ビットデータＤと検索ビットデータＣＡＭとが一致したとき、スイッチ回路ＴＧ１１はオンになる。
【００６９】
複数のインバータＩ１０〜Ｉ１４は直列に接続される。インバータＩ１３とインバータＩ１４との間にはトランスファゲートＴＧ１０が接続される。そして、スイッチ回路ＴＧ１１は、インバータＩ１０の入力端子とインバータＩ１４の入力端子との間に接続される。
【００７０】
段数選択回路ＳＥは、対応するユニットデータ比較回路ＵＣ１１の比較結果に応じてインバータの段数を選択する。ユニットデータ比較回路ＵＣ１１での比較の結果、参照ビットデータＤと検索ビットデータＣＡＭとが一致する場合、トランスファゲートＴＧ１０がオフになり、ＴＧ１１がオンになる。そのため、遅延回路ＤＣ１１の入力信号は１段のインバータＩ１４を介して外部に出力される。
【００７１】
一方、参照ビットデータＤと検索ビットデータＣＡＭとが異なる場合、トランスファゲートＴＧ１０がオンになり、ＴＧ１１がオフになる。そのため、遅延回路ＤＣ１１の入力信号は、５段のインバータを介して外部に出力される。つまり、参照ビットデータＤと検索ビットデータとが一致しない方が、遅延時間が長くなる。
要するに、遅延回路ＤＣ１１は、インバータ段数が少ないパス（ショートパス）と、インバータ段数が多いパス（ロングパス）と、参照ビットデータと検索ビットデータとのハミング距離に応じてショートパス及びロングパスのいずれかを選択する段数選択回路とを備える。
【００７２】
他の遅延回路ＤＣ１２〜ＤＣ１Ｗも、遅延回路ＤＣ１１と同じ構成を有する。したがって、発振回路ＯＣ１では、保存回路Ｓ１に記憶されたＷビット幅の参照データがＷビット幅の検索データに類似するほど、つまり、参照データと検索データとの距離が小さい程、インバータの段数が少なくなる。なぜなら、Ｌレベルの信号ｐａｔｈ＿ｅｎａとＨレベルの信号ｐａｔｈ＿ｅｎａｑとを出力するデータユニット比較回路ＵＣ１ｊの数が相対的に多くなるからである。インバータの段数が少ないほど、遅延時間は短くなる。したがって、発振回路ＯＣ１は、発振周波数の高いパルス信号Ｐ１を出力する。
【００７３】
一方、保存回路Ｓ１に記憶された参照データと検索データとの距離が遠い程、発振回路ＯＣ１内で利用されるインバータの段数は多くなる。そのため、発振回路ＯＣ１は発振周波数の低いパルス信号Ｐ１を出力する。
【００７４】
以上の構成により、発信回路ＯＣ１は、保存回路Ｓ１の参照データと検索データとの距離に応じた発振周波数のパルス信号Ｐ１を出力する。発振回路ＯＣ１は、参照データと検索データとの距離が小さい程、利用するインバータの段数を減らす。そのため、参照データが検索データに類似する程、高い発振周波数を有するパルス信号Ｐ１を出力する。
【００７５】
発振回路ＯＣ２〜ＯＣＲはそれぞれ、発振回路ＯＣ１と同じ構成を有する。したがって、発振回路ＯＣ１〜ＯＣＲのうち、発振周波数が最大となるパルス信号Ｐｉを出力した発振回路ＯＣｉに対応する保存回路Ｓｉに、検索データに最も類似した参照データが格納されている。
【００７６】
ＮＡＮＤゲート３００は、ノードＮ１０上の信号とイネーブル信号ＥＮＡとを受け、ＮＡＮＤ論理演算結果を遅延回路ＤＣ１Ｗに出力する。上述のとおり、ＮＡＮＤゲート３００は、イネーブル信号ＥＮＡに応じて発振回路ＯＣ１を起動又は停止する。イネーブル信号ＥＮＡが非活性（Ｌレベル）のとき、ＮＡＮＤゲート３００は常にＨレベルの信号を出力する。そのため、発振回路ＯＣ１から出力される信号はＨレベルで一定である。つまり、発振回路ＯＣ１は、パルス信号を出力しない。
【００７７】
［ＷＴＡ回路］
ＷＴＡ回路２０は、発振回路ＯＣ１〜ＯＣＲからパルス信号Ｐ１〜ＰＲを受ける。そして、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、検索データに最も類似した参照データ（Ｗｉｎｎｅｒ）を決定する。
【００７８】
図５を参照して、ＷＴＡ回路２０は、複数の判定回路ＪＣ１〜ＪＣＲと、プリチャージ回路３０と、ラッチ指示ノードＮ４０とを備える。各判定回路ＪＣ１〜ＪＣＲは、ラッチ指示ノードＮ４０に接続される。
【００７９】
プリチャージ回路３０は、イネーブル信号ＥＮＡの反転信号であるイネーブル信号ＥＮＡＱを受けたとき、ラッチ指示ノードＮ４０に電荷を供給し、充電する。これにより、ラッチ指示ノードＮ４０の電圧はＨレベル（ＶＤＤ）に上昇する。
【００８０】
判定回路ＪＣ１は、対応する発振回路ＯＣ１の出力信号を受ける。判定回路ＪＣ２は、発振回路ＯＣ２の出力信号を受ける。同様に、判定回路ＪＣ３〜ＪＣＲは、発振回路ＯＣ３〜ＯＣＲの出力信号をそれぞれ受ける。
【００８１】
判定回路ＪＣ１は、インバータＩ２０と、遅延回路２５１と、ラッチ回路２５２と、放電回路２５０と、クロック生成回路２５３とを備える。
【００８２】
インバータＩ２０は、発信回路ＯＣ１の出力信号を受け、反転してノードＮ３０に出力する。放電回路２５０は、ｎ型ＭＯＳトランジスタからなる。ｎ型ＭＯＳトランジスタは、ラッチ指示ノードＮ４０と接地電圧が供給されるＧＮＤノードとの間に接続され、そのゲートはノードＮ３０に接続される。放電回路２５０は、ｎ型ＭＯＳトランジスタのゲートにＨレベルの信号が入力されたとき、ラッチ指示ノードＮ４０を放電する。つまり、判定回路ＪＣ１は、パルス信号Ｐ１を受けたとき、放電回路２５０によりラッチ指示ノードＮ４０の電圧レベルを接地電圧（Ｌレベル）まで低下する。
【００８３】
クロック生成回路２５３は、ラッチ指示ノードＮ４０がＬレベルとなったときにクロック信号ＣＬＫを出力する。クロック生成回路２５３は、インバータＩ２１からなる。インバータＩ２１の入力端子はラッチ指示ノードＮ４０に接続される。クロック生成回路２５３は、ラッチ指示ノードＮ４０がＬレベルになったとき、Ｈレベルのクロック信号ＣＬＫを出力する。
【００８４】
ラッチ回路２５２は、Ｄフリップフロップで構成される。ラッチ回路２５２は、Ｈレベルのクロック信号ＣＬＫを受けたとき、インバータＩ２０の出力信号をラッチして、判定信号ＪＳ１を外部に出力する。
【００８５】
遅延回路２５１は、発振回路ＯＣ１からパルス信号Ｐ１が出力された場合、クロック生成回路２５３がクロック信号を出力するときにパルス信号Ｐ１の反転信号がラッチ回路２５２に入力されるように調整する。ただし、遅延回路２５１はなくてもよい。
【００８６】
判定回路ＪＣ２〜ＪＣＲは、判定回路ＪＣ１と同じ構成を有する。各判定回路ＪＣ１〜ＪＣＲの放電回路２５０及びクロック生成回路２５３は、いずれもラッチ指示ノードＮ４０と接続されている。したがって、いずれかの判定回路ＪＣの放電回路２５０がラッチ指示ノードＮ４０を放電すれば、全ての判定回路ＪＣ１〜ＪＣＲのクロック生成回路２５３はＨレベルのクロック信号ＣＬＫを出力する。
【００８７】
発振回路ＯＣ１〜ＯＣＲの出力信号にパルスが形成されていないとき、つまり、発振回路ＯＣｉがパルス信号Ｐｉを出力する前、パルス信号Ｐ１〜ＰＲはＨレベルで一定である。ここで、発振回路ＯＣ１〜ＯＣＲのうち、発振回路ＯＣ２が最大の発振周波数のパルス信号Ｐ２を出力したと仮定する。
【００８８】
この場合、発信回路ＯＣ２の出力信号が、他の発振回路ＯＣｉの出力信号よりも早く、電圧レベルがＨレベルからＬレベルに変化する。そのため、各判定回路ＪＣｉ内の放電回路２５０のうち、判定回路ＪＣ２の放電回路２５０が最も早く動作してラッチ指示ノードＮ４０をＬレベルにする。
【００８９】
このとき、判定回路ＪＣ２のラッチ回路２５２はＨレベルの信号を受ける。しかしながら、他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲのラッチ回路２５２はＬレベルの信号を受けている。ラッチ指示ノードＮ４０がＬレベルになると、各判定回路ＪＣｉ内のクロック生成回路２５３が一斉にＨレベルのクロック信号ＣＬＫを出力する。そのため、判定回路ＪＣ２内のラッチ回路２５２のみがＨレベルの信号をラッチし、その他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲ内のラッチ回路２５２はＬレベルの信号をラッチする。
【００９０】
以上の工程により、判定回路ＪＣ２はＷｉｎｎｅｒを示すＨレベルの判定信号ＪＳ２を出力し、他の判定回路ＪＣ１、ＪＣ３〜ＪＣＲはＬｏｓｅｒを示すＬレベルの判定信号ＪＳ１、ＪＳ３〜ＪＳＲを出力する。
【００９１】
以上のとおり、本実施の形態による連想メモリ１００は、参照データと検索データとの距離に応じた発振周波数のパルス信号を生成する。そして、パルス信号の発振周波数に基づいて、Ｗｉｎｎｅｒとなる参照データを決定する。
【００９２】
参照データと検索データとの距離を発振周波数に変換すれば、従来の連想メモリのようにトランジスタ素子の特性のばらつきによる誤検索が発生しにくい。発振回路ＯＣｉは複数段のインバータを備える。インバータを構成するトランジスタ素子の特性にばらつきが生じても、インバータ段数は複数存在するため、特性ばらつきの影響を抑えることができる。つまり、トランジスタ素子の特性にばらつきが生じても、発振周波数のばらつきを抑制することができる。
【００９３】
図６は発振回路ＯＣｉ内のインバータの段数と発振周波数のばらつきとの関係を示すグラフである。図６のグラフは次の方法で求めた。初めに、インバータ段数が１７段、３３段、６５段及び１２９段の発振回路をそれぞれ作製した。使用するＣＭＯＳトランジスタのゲート長は９０ｎｍとした。
【００９４】
作製された各発振回路に種々の電源電圧を用いてパルス信号を生成した。生成されたパルス信号の発振周波数を測定した。測定された発振周波数の平均値を１として正規化し、標準偏差を求めた。図６中の縦軸は、各発振回路の標準偏差（％）を示す。図６を参照して、インバータ段数が多いほど、発振周波数のばらつきが抑えられることが分かる。
【００９５】
［第２の実施の形態］
上述のとおり、第１の実施の形態による連想メモリ１００では、ＷＴＡ回路２０が、パルス信号Ｐ１〜ＰＲの発振周波数に基づいて、Ｗｉｎｎｅｒとなる参照データを決定する。したがって、最大の発振周波数を有するパルス信号Ｐｉと、２番目に高い発振周波数を有するパルス信号Ｐｉとの発振周波数の差が大きいほど、Ｗｉｎｎｅｒの誤検出が起こりにくい。
【００９６】
図７を参照して、第２の実施の形態による連想メモリ１１０は、連想メモリ１００と比較して、メモリ部１０とＷＴＡ回路２０との間に、分周部３５を新たに備える。連想メモリ１１０のその他の構成は、連想メモリ１００と同じである。
【００９７】
分周部３５は、複数の分周回路(Frequency Divider)ＦＤ１〜ＦＤＲを備える。連想メモリ１１０のその他の構成は、連想メモリ１００と同じである。
【００９８】
分周回路ＦＤ１は、発振回路ＯＣ１のパルス信号Ｐ１を受ける。そして、パルス信号Ｐ１の周波数を所定の分周比で分周する。本例では、分周回路ＦＤ１は、パルス信号Ｐ１を１．５分周する。ただし、分周比は１．５に限られない。他の分周回路ＦＤ２〜ＦＤＲも分周回路ＦＤ１と同じ分周比でパルス信号Ｐ２〜ＰＲを分周する。
【００９９】
ＷＴＡ回路２０内の各判定回路ＪＣ１〜ＪＣＲは、分周されたパルス信号Ｐ１〜ＰＲを受ける。ＷＴＡ回路２０は、分周されたパルス信号Ｐ１〜ＰＲに基づいて、Ｗｉｎｎｅｒを決定する。
【０１００】
パルス信号Ｐｉを所定の分周比で分周すれば、最も高い発振周波数のパルス信号Ｐｉの波形変化と、次に高い発振周波数のパルス信号Ｐｉの波形変化との差を大きくすることができる。図８を用いてこの点を説明する。
【０１０１】
図８は、各分周回路ＦＤｉが分周比１．５でパルス信号Ｐｉを分周した場合の、パルス信号Ｐ１及びＰ２の波形を示す図である。図中のＰ１（ＦＤ１）は、分周回路ＦＤ１から出力されたパルス信号Ｐ１を示す。図中のＰ２（ＦＤ２）は、分周回路ＦＤ２から出力されたパルス信号Ｐ２を示す。図中のＰ１は、分周回路ＦＤ１に入力されるパルス信号Ｐ１を示し、図中のＰ２は、分周回路ＦＤ２に入力されるパルス信号Ｐ２を示す。
【０１０２】
ここで、パルス信号Ｐ１の周波数が最も高く、Ｐ２の周波数が次に高いと仮定する。図８に示すとおり、分周回路に入力される前のパルス信号Ｐ１とＰ２との最初の波形変化の時間差はＴｄ１である。
【０１０３】
一方、分周されたパルス信号Ｐ１（ＦＤ１）とＰ２（ＦＤ２）との最初の波形変化の時間差はＴｄ２となる。時間差Ｔｄ２は時間差Ｔｄ１よりも大きい。要するに、分周回路ＦＤ１〜ＦＤＲは、Ｗｉｎｎｅｒとなるパルス信号の最初の波形変化と、次に周波数の高いパルス信号の最初の波形変化との時間差を増大する。そのため、ＷＴＡ回路２０はより正確に、Ｗｉｎｎｅｒを決定できる。
【０１０４】
［第３の実施の形態］
連想メモリ１００内のＷＴＡ回路２０では、図５に示すように、全ての判定回路ＪＣ１〜ＪＣＲが１つのラッチ指示ノードＮ４０に接続される。ＷＴＡ回路２０のラッチ指示ノードＮ４０は、全ての判定回路ＪＣ１〜ＪＣＲに接続されるために長い。そのため、ラッチ指示ノードＮ４０の負荷容量は大きい。したがって、放電回路２５０内のｎ型ＭＯＳトランジスタがオンになってから、ラッチ指示ノードＮ４０の電圧レベルが接地電圧に落ちるまでに時間がかかる。ラッチ指示ノードＮ４０の電圧レベルを落とすのに時間がかかれば、Ｗｉｎｎｅｒの決定も時間がかかる。
【０１０５】
そこで、本実施の形態による連想メモリは、ＷＴＡ回路２０の代わりに図９に示す新たなＷＴＡ回路２５を備える。その他の構成は連想メモリ１００と同じである。
【０１０６】
図９を参照して、ＷＴＡ回路２５は、複数の判定ブロックＪＢを備える。複数の判定ブロックＪＢは、トーナメント式に複数段に接続される。図９では、最下段である第１段から、最上段である第ｎ段（ｎは２以上の自然数）まで、ｎ段のトーナメント式となっている。
【０１０７】
最下段に当たる第１段目に配列された複数の判定ブロックＪＢ１は、Ｒ個の第１パルス判定回路ＰＪＣ１〜ＰＪＣＲを含む。換言すれば、Ｒ個の第１パルス判定回路ＰＪＣ１〜ＰＪＣＲは、複数の判定ブロックＪＢ１に分割される。
【０１０８】
各判定回路ＪＢ１は、Ｒ個未満の第１パルス判定回路ＰＪＣｉとパルス受付判定ノードＮ５０とを備える。第１パルス判定回路ＰＪＣ１〜ＰＪＣＲの各々は、図５中の判定回路ＪＣ１〜ＪＣＲと比較して、クロック生成回路２５３を有さない。その他の構成は判定回路ＪＣ１〜ＪＣＲと同じである。各第１パルス判定回路ＰＪＣ１〜ＰＪＣＲは、対応する発振回路ＯＣ１〜ＯＣＲからパルス信号Ｐ１〜ＰＲをそれぞれ受ける。
【０１０９】
各判定ブロックＪＢ１はさらに、パルス受付判定ノードＮ５０と、プリチャージ回路３０とを備える。プリチャージ回路３０は、イネーブル信号ＥＮＡＱを受けたとき、パルス受付判定ノードＮ５０を充電する。
【０１１０】
パルス受付判定ノードＮ５０は、判定ブロックＪＢ１に含まれる複数の第１パルス判定回路ＰＪＣｉ（ただし、Ｒ個未満）に接続される。より具体的には、各第１パルス判定回路ＰＪＣｉ内の放電回路２５０に接続される。
【０１１１】
図５中のラッチ指示ノードＮ４０に接続される判定回路ＪＣｉはＲ個である。これに対して図９中の各パルス受付判定ノードＮ５０に接続される第１パルス判定回路ＰＪＣｉはＲ個未満である。パルス受付判定ノードＮ５０は、ラッチ指示ノードＮ４０と比較して、負荷容量が小さい。
【０１１２】
トーナメント式に接続された判定ブロックのうち、第２段目〜第ｎ−１段目に配列される判定ブロックＪＢ２〜ＪＢｎ−１の構成について説明する。図９を参照して、第２段目に配列される複数の判定ブロックＪＢ２の各々は、プリチャージ回路３０と、パルス受付判定ノードＮ５０と、複数の第２パルス判定回路ＰＪとを含む。
【０１１３】
各第２パルス判定回路ＰＪは、対応する判定ブロックＪＢ１内のパルス受付判定ノードＮ５０に接続される。第２パルス判定回路ＰＪは、インバータＩ２０と、放電回路２５０とを備える。第２パルス判定回路ＰＪは、自身が属する判定ブロックＪＢ２内のパルス受付判定ノードＮ５０に接続される。より具体的には、第２パルス判定回路ＰＪ内の放電回路２５０がパルス受付判定ノードＮ５０と接続される。プリチャージ回路３０は、イネーブル信号ＥＮＡＱを受けたとき、パルス受付判定ノードＮ５０を充電する。
【０１１４】
第３段目〜第ｎ−１段目に配列された各判定ブロックＪＢの構成も同じである。第ｎ−１段目に配列された判定ブロックＪＢ内の第２パルス判定回路ＰＪは、前段、つまり、第ｎ−２段目に配列された複数の判定ブロックＪＢのうち、対応する判定ブロックＪＢ内のパルス受付判定ノードＮ５０に接続される。
【０１１５】
最上段である第ｎ段には、１つの判定ブロックＪＢｎが配置される。判定ブロックＪＢｎは、判定ブロックＪＢ２と比較して、クロック生成回路３１を新たに備える。他の構成は判定ブロックＪＢ２と同じである。
【０１１６】
クロック生成回路３１は、パルス受付判定ノードＮ５０がＬレベルになったとき、クロック信号ＣＬＫを出力する。クロック生成回路３１内の構成は図５中のクロック生成回路２５３と同じである。つまり、クロック生成回路３１はインバータＩ２１を備える。
【０１１７】
以上のとおり、ＷＴＡ回路２５は、第１段〜第ｎ段までの複数段のトーナメント式に接続された判定ブロックＪＢ１〜ＪＢｎを備える。各パルス受付判定ノードＮ５０に接続される第１又は第２パルス判定回路の数は、図５中のラッチ指示ノードＮ４０に接続される判定回路の数よりも少ない。したがって、各パルス受付判定ノードＮ５０の負荷容量は、ラッチ指示ノードＮ４０の負荷容量よりも小さい。そのため、パルス受付判定ノードＮ５０をＨレベルからＬレベルに下げるのにかかる時間は、ラッチ指示ノードＮ４０よりも短くすることができる。
【０１１８】
要するに、トーナメント式に判定ブロックＪＢ１〜ＪＢｎを配置すれば、パルス受付判定ノードＮ５０の負荷容量を小さくできる。そのため、判定ブロックＪＢ１内が最も高い周波数のパルス信号Ｐｉを受けてから、クロック信号ＣＬＫが出力されるまでの時間を短くできる。換言すれば、Ｗｉｎｎｅｒの決定時間を短くできる。
【０１１９】
［第４の実施の形態］
第１の実施の形態では、データユニット保存回路ＵＳｉｊごとに遅延回路ＤＣｉｊを設けた。しかしながら、このような構成では、使用されるトランジスタ素子数が多くなる。そのため、１つの遅延回路を複数のデータユニット保存回路に対応させてもよい。
【０１２０】
本実施の形態による連想メモリは、発振回路ＯＣ１〜ＯＣＲに代えて、新たな発振回路ＯＳＣ１〜ＯＳＣＲを備える。その他の構成は連想メモリ１００と同じである。
【０１２１】
図１０を参照して、発振回路ＯＳＣ１は、発振回路ＯＣ１と比較して、遅延回路ＤＣ１１、ＤＣ１２、・・・ＤＣ１Ｗに代えて、遅延回路ＤＬＣ１１、ＤＬＣ１２、・・・ＤＣＬ１Ｔ（Ｔは１以上の自然数）と、距離判定回路ＤＪ１１〜ＤＪ１Ｔとを備える。距離判定回路ＤＪ１１〜ＤＪ１Ｔは、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔに対応する。その他の構成は発振回路ＯＣ１と同じである。
【０１２２】
活性化されたＮＡＮＤゲート３００は入力信号を反転する。また、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔの各々も、入力信号を反転する。したがって、ＮＡＮＤゲート３００及び遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは、反転回路として機能する。つまり、発振回路ＯＳＣ１は、奇数個の反転回路を備える。したがって、遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは偶数個含まれている。奇数個の反転回路（ＮＡＮＤゲート３００及び遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔ）はループ状に直列に連結されている。
【０１２３】
各遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔは、２つのデータユニット比較回路ＵＣｉｊの比較結果に基づいて、パルス信号Ｐ１の発振周波数を決定する。
【０１２４】
各距離判定回路ＤＪ１１〜ＤＪ１Ｔは、２つのデータユニット比較回路ＵＣｉｊから比較結果（２つの信号ｐａｔｈ＿ｅｎａ及び信号ｐａｔｈ＿ｅｎａｑ）を受ける。そして、比較結果からハミング距離を求める。そして、求めたハミング距離に応じた信号を、対応する遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔに出力する。
【０１２５】
具体的には、距離判定回路ＤＪ１１は、ユニットデータ比較回路ＵＣ１１及びＵＣ１２から比較結果を受ける。比較の結果、ユニットデータ保存回路ＵＳ１１及びＵＳ１２に格納された参照ビットデータＤの全てが対応する検索ビットデータＣＡＭと一致するとき（つまり、ハミング距離＝０のとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ０を出力する。そして、Ｌレベルの信号Ｓ１及びＳ２を出力する。また、信号Ｓ０、Ｓ１及びＳ２の反転信号／Ｓ０、／Ｓ１及び／Ｓ２を出力する。
【０１２６】
２つの参照ビットデータのうち、いずれか１つが対応する検索ビットデータと一致するとき（つまり、ハミング距離＝１のとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ１を出力し、Ｌレベルの信号Ｓ０及びＳ２を出力する。
【０１２７】
２つの参照ビットデータのいずれも対応する検索ビットデータと一致しないとき（距離＝２であるとき）、距離判定回路ＤＪ１１は、Ｈレベルの信号Ｓ２を出力し、Ｌレベルの信号Ｓ０及びＳ１を出力する。
【０１２８】
上述のとおり、遅延回路ＤＬＣ１１〜ＤＣＬ１ＴとＮＡＮＤゲート３００は、ループ状に直列に接続される。複数の遅延回路ＤＬＣ１１〜ＤＬＣ１Ｔのうち、端に位置する遅延回路ＤＬＣ１１の出力端子は出力ノードＮ１０に接続される。また、他方の端に位置する遅延回路ＤＬＣ１Ｔの入力端子は、ＮＡＮＤゲート３００の出力端子と接続される。
【０１２９】
遅延回路ＤＬＣ１１の構成を図１１に示す。遅延回路ＤＬＣ１１は、第１の遅延段７０と、第２の遅延段７１と、インバータＩ７１と、段数選択回路７２とを備える。段数選択回路７２は、トランスファゲートＴＧ７１、ＴＧ７２及びＴＧ７３を備える。段数選択回路７２は、距離判定回路ＤＪ１１からの信号Ｓ０〜Ｓ２に応じて、利用するインバータの段数を選択する。換言すれば、段数選択回路７２は、ハミング距離に応じて遅延時間（発振周波数）を選択する。
【０１３０】
第１の遅延段７０及び第２の遅延段７１はそれぞれ、直列に接続された偶数個のインバータを含む。第１の遅延段７０は、前段の遅延回路ＤＬＣ１２の出力を受け、遅延する。第２の遅延段７１は、第１の遅延段７０の出力を受け、遅延する。
【０１３１】
段数選択回路７２内のトランスファゲートＴＧ７１〜ＴＧ７３は並列に接続される。トランスファゲートＴＧ７１〜ＴＧ７３はそれぞれ、ｎ型ＭＯＳトランジスタとｐ型ＭＯＳトランジスタとで構成される。トランスファゲートＴＧ７１は、対応する距離判定回路ＤＪ１１からＨレベルの出力信号Ｓ０とＬレベルの出力信号／Ｓ０を受けるとオンになる。ここで、出力信号／Ｓ０は、信号Ｓ０の反転信号である。要するに、トランスファゲートＴＧ７１は、データユニット保存回路ＵＳ１１及びＵＳ１２に格納された参照データがいずれも検索データと一致したとき（距離＝０のとき）、オンになる。このとき、遅延回路ＤＬＣ１１は、入力信号をトランスファゲートＴＧ７１に通してインバータＩ７１に出力する。
【０１３２】
トランスファゲートＴＧ７２は、Ｈレベルの信号Ｓ１とＬレベルの信号／Ｓ１（信号Ｓ１の反転信号）とを受けるとオンになる。つまり、距離＝１のときにオンになる。このとき、遅延回路ＤＬＣ１１は、入力信号を第１の遅延段７０に供給する。そして、第１の遅延段７０の出力をインバータＩ７１に供給する。
【０１３３】
トランスファゲートＴＧ７３は、Ｈレベルの信号Ｓ２とＬレベルの信号／Ｓ２（信号Ｓ２の反転信号）とを受けるとオンになる。つまり、距離＝２のときにオンになる。このとき、トランスファゲートＴＧ１３は、第２の遅延段７１の出力をインバータＩ７１に供給する。
【０１３４】
要するに、発振回路ＤＬＣ１１は、３つのパス（遅延段のないショートパス、遅延段７１を有するミドルパス、遅延段７１及び７２を有するロングパス）と、３つのパスのうちいずれか１つを選択する段数選択回路７２とを備える。各パスは、それぞれ異なる遅延時間が設定されている。発振回路ＤＬＣ１１は、２つの参照ビットデータと検索ビットデータとの比較結果に応じて、３つのパスの中から１つのパスを選択する。上述の例では、距離＝０のとき、遅延回路ＤＬＣ１１は、ショートパスを選択する。このとき、利用するインバータの段数は１つ（インバータＩ７１のみ）である。距離＝１のとき、遅延回路ＤＬＣ１１は、ミドルパスを選択する。このとき、インバータの段数は５つである（第１の遅延段７０＋インバータＩ７１）。距離＝２のとき、遅延回路ＤＬＣ１１は、ロングパスを選択する。このとき、インバータ段数は９個である（第１の遅延段７０、第２の遅延段７１及びインバータＩ７１）。
【０１３５】
なお、遅延回路ＤＬＣ１２〜ＤＬＣ１Ｔは遅延回路ＤＬＣ１１と同じ構成を有する。
【０１３６】
上述のとおり、遅延回路ＤＬＣは複数の比較結果に応じてインバータの段数を変える。そのため、発振回路ＤＬＣ１１は、発振回路ＤＣ１１と比較して、利用するトランジスタ素子数を減らすことができる。さらに、参照データと検索データが一致した場合（距離＝０の場合）のインバータ段数を減らすことができる。そのため、より高周波のパルス信号を出力できる。その結果、ＷＴＡ回路２０がＷｉｎｎｅｒを決定する時間をより短くできる。
【０１３７】
上述の例では、遅延回路ＤＬＣは、２つの遅延段を含み、利用する遅延段数に応じて３つの遅延時間を設定できる。遅延回路ＤＬＣは、２つの参照ビットデータと２つの検索ビットデータから得られる２つの比較結果に応じて、利用する遅延段数を選択する。その結果、３つの遅延時間の中から１つの遅延時間が選択される。
遅延回路ＤＬＣはＬ（Ｌは２以上の自然数）個の参照ビットデータと検索ビットデータと比較結果に応じて遅延時間を設定することもできる。より具体的には、遅延回路ＤＬＣは、複数の遅延段を含み、利用する遅延段数に応じてＬ＋１個の遅延時間を設定できる。遅延回路ＤＬＣは、Ｌ個の比較結果に応じて、Ｌ＋１個の遅延時間（パス）の中から１つの遅延時間（パス）を選択する。遅延回路ＤＬＣに入力された信号は、選択された遅延時間だけ遅延して次段の遅延回路ＤＬＣに出力される。要するに、Ｌ個の参照ビットデータと検索ビットデータとを比較する場合、遅延回路ＤＬＣは、Ｌ＋１個のパスを備える。各パスは異なる遅延時間が設定される。
【０１３８】
なお、図１２に示すように、第１の遅延段７０及び第２の遅延段７１の初段のインバータをトライステート型のインバータにしてもよい。トライステートインバータＩ７０１は、Ｈレベルの信号Ｓ１又はＳ２を受けると活性化する。また、トライステートインバータＩ７０２は、Ｈレベルの信号Ｓ２を受けると活性化する。距離＝０のとき、第１の遅延段７０及び第２の遅延段７１は動作せず、距離＝１のとき、第２の遅延段７１は動作しない。したがって、消費電力を削減できる。
【０１３９】
トライステートインバータＩ７０１及びＩ７０２が非活性の場合、各遅延段７０及び７１の２段目のインバータの入力ノードは浮遊状態となる。そのため、ノイズ等の影響でノードのレベルが変動し、インバータが動作してしまう場合がある。図１３に示すように、トライステートインバータＩ７０１及びＩ７０２に代えて、ＮＯＲゲート７２１及び７２２を用いれば、２段目のインバータの入力ノードが浮遊状にならない。そのため、ノイズ等の影響で２段目以降のインバータが動作するのを防止できる。
【０１４０】
ＮＯＲゲート７２１は、Ｌレベルの信号／Ｓ１又はＬレベルの信号／Ｓ２を受けると、ＮＯＴゲート（インバータ）として動作する。また、ＮＯＲゲート７２２は、Ｌレベルの信号／Ｓ２を受けると、ＮＯＴゲートとして動作する。
【０１４１】
さらに、図１４に示すように、第２の遅延段７１とトランスファゲートＴＧ７３との間にダミーのＮＯＲゲート７２２を配置してもよい。この場合、各パスの配線に係る容量を同じにできる。そのため、設計時において、各パスの遅延回路の設計を同じにすることができる。
【０１４２】
［第５の実施の形態］
上述の連想メモリ１００は、検索データに最も近い参照データを検索する。しかしながら、検索データに近い参照データを、検索データに近い順に複数検索できる方が好ましい場合がある。
【０１４３】
図１５を参照して、本実施の形態による連想メモリ２００は、連想メモリ１００と比較して、新たにフィードバック回路５０を備える。その他の構成は連想メモリ１００と同じである。
【０１４４】
フィードバック回路５０は、複数のフィードバック回路５１〜５Ｒを備える。各フィードバック回路５１〜５Ｒは、制御信号ＣＯＮを受けて起動する。
【０１４５】
フィードバック回路５１は、Ｈレベルの判定信号ＪＳ１を受けたとき、Ｈレベルのフィードバック信号を出力する。発振回路ＯＣ１の出力ノードは、Ｈレベルのフィードバック信号を受けて、充電される。つまり、フィードバック回路５１は、Ｈレベルの判定信号ＪＳ１を受けると、発振回路ＯＣ１の出力ノードをチャージする。そのため、発振回路ＯＣ１の出力信号はＨレベルで固定される。たとえパルス信号Ｐ１が出力されても、パルス信号Ｐ１が無効化される。
【０１４６】
フィードバック回路５１は、判定信号ＪＳ１がＬレベルのとき、発振回路ＯＣ１の出力ノードをチャージしない。しかし、いったん判定信号ＪＳ１がＨレベルになると、それ以降、Ｈレベルのフィードバック信号を発振回路ＯＣ１の出力ノードに供給し続ける。
【０１４７】
同様に、フィードバック回路５２〜５Ｒはそれぞれ、対応する判定信号ＪＳ２〜ＪＳＲがＨレベルになるまで、発振回路ＯＣ２〜ＯＣＲの出力ノードをチャージしない。しかし、いったん判定信号ＪＳ２〜ＪＳＲがＨレベルになると、それ以降、発振回路ＯＣ２〜ＯＣＲの出力ノードをチャージし続ける。
【０１４８】
以上の構成を有する連想メモリ２００の動作は次のとおりである。
【０１４９】
連想メモリ２００は初めに、１回目の検索を開始する。このとき、連想メモリ２００は検索データに最も類似する参照データを検索する。
【０１５０】
初めに、各比較回路Ｃ１〜ＣＲに検索データが入力される。その後、イネーブル信号ＥＮＡがＨレベルとなり、発振回路ＯＣ１〜ＯＣＲが動作を開始する。ここで、保存回路Ｓ２に記憶された参照データが検索データに最も類似すると仮定する。この場合、判定信号ＪＳ２がＨレベルとなり、その他の判定信号ＪＳ１、ＪＳ３〜ＪＳＲはＬレベルとなる。
【０１５１】
フィードバック回路５１〜５Ｒは、制御信号ＣＯＮを受けて起動する。フィードバック回路５２は、Ｈレベルの判定信号ＪＳ２を受けると、発振回路ＯＣ２の出力ノードをチャージする。その結果、発振回路ＯＣ２の出力ノードの電圧レベルはＨレベルに維持される。そのため、発振回路ＯＣ２から出力されるパルス信号Ｐ２は無効化される。
【０１５２】
第１回目の検索が終了したとき、発振回路ＯＣ１〜ＯＣＲに入力されるイネーブル信号ＥＮＡはいったん非活性（Ｌレベル）となる。
【０１５３】
続いて、連想メモリ２００は、第２回目の検索を実行する。このとき、イネーブル信号ＥＮＡが再びＨレベルになる。そこで、発振回路ＯＣ１〜ＯＣＲは第１回目と同じ比較結果に基づいて、パルス信号Ｐ１〜ＰＲを再び出力する。
【０１５４】
しかしながら、発振回路ＯＣ２の出力ノードは、フィードバック回路５２によりＨレベルに維持されている。したがって、パルス信号Ｐ２は無効化され、発振回路ＯＣ２の出力信号Ｈレベルのままとなる。そのため、ＷＴＡ回回路２０は、パルス信号Ｐ２以外の他の信号Ｐ１、Ｐ３〜ＰＲに基づいて、最も検索データに近い参照データを決定する。ここで、保存回路Ｓ１に記憶された参照データが検索データに最も近いと仮定する。この場合、判定信号ＪＳ１がＨレベルとなり、その他の信号ＪＳ２〜ＪＳＲはＬレベルとなる。
【０１５５】
第２回目の検索によりＨレベルとなった信号ＪＳ１に対応する参照データ（つまり、保存回路Ｓ１に記憶された参照データ）は、検索データに２番目に類似する参照データに相当する。
【０１５６】
判定信号ＪＳ１がＨレベルになると、フィードバック回路５１は発振回路ＯＣ１の出力ノードをチャージする。要するに、フィードバック回路５１は発振回路ＯＣ１のパルス信号Ｐ１を無効化する。第３回目の検索時では、発振回路ＯＣ１及びＯＣ２はパルス信号を出力できない。そのため、既に検索された参照データ（保存回路Ｓ１及びＳ２の参照データ）を除く他の参照データから、検索データに最も類似する参照データが検索される。検索された参照データは検索データに３番目に近いデータに相当する。
【０１５７】
以上のとおり、連想メモリ２００は、ｊ回目（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までにＨレベルの判定信号ＪＳｉを出力した判定回路ＪＣｉに対応する発振回路ＯＣｉの出力を無効化する。これにより、検索処理を実行するごとに、検索データに近い参照データを、検索データに近い順に検索することができる。
【０１５８】
［第６の実施の形態］
第５の実施の形態による連想メモリ２００は、フィードバック回路５０を用いて発振回路ＯＣｉの出力を無効化することにより、検索データに近い参照データを検索データに近い順に複数検索できる。しかしながら、１回の検索処理で１つの参照データしか検索できない。したがって、検索データに近い参照データの複数検索する場合、希望する参照データ数と同じ回数の検索処理を実行しなければならない。
【０１５９】
図１６に本実施の形態による連想メモリ３００の機能ブロック図を示す。図１６を参照して、連想メモリ３００は、連想メモリ１００と比較して、ＷＴＡ回路２０に代えて、カウンタ部４０を備える。
【０１６０】
カウンタ部４０は、複数のカウンタ回路４１〜４Ｒを備える。カウンタ回路４１は、発振回路ＯＣ１のパルス信号Ｐ１を受ける。そして、パルス信号Ｐ１のパルスをカウントする。カウント数が所定数ＣＴ（たとえば１０個）となったとき、カウント回路４１はＨレベルの判定信号ＪＳ１を出力する。
【０１６１】
同様に、カウンタ回路４２〜４Ｒはそれぞれ、発振回路ＯＣ２〜ＯＣＲのパルス信号Ｐ２〜ＰＲを受ける。そして、各パルス信号Ｐ２〜ＰＲのパルスをカウントする。カウント数が所定数ＣＴとなったとき、カウンタ回路４２〜４ＲはＨレベルの判定信号ＪＳ２〜ＪＳＲを順次出力する。
【０１６２】
上述のとおり、発振回路ＯＣ１〜ＯＣＲは、対応する参照データが検索データに類似するほど、パルス信号Ｐ１〜ＰＲの発振周波数を高くする。カウンタ回路４１〜４Ｒは、発振周波数が高いパルス信号Ｐ１〜ＰＲを受けるほど早く、Ｈレベルの判定信号ＪＳ１〜ＪＳＲを出力する。したがって、判定信号ＪＳ１〜ＪＳＲは、対応する参照データが検索データに類似する順に、順次Ｈレベルに立ち上がる。Ｈレベルの判定信号ＪＳ１〜ＪＳＲの出力順に基づいて、カウンタ部４０は、検索データに近い参照データを、検索データに近い順に決定できる。
【０１６３】
以上のとおり、連想メモリ３００は、１回の検索処理で、検索データに近い参照データを複数個検索することができる。
【０１６４】
［第７の実施の形態］
上述の実施の形態では、ハミング距離を適用した場合の連想メモリについて説明した。しかしながら、本発明による連想メモリは、マンハッタン距離にも適用できる。
【０１６５】
図１７を参照して、連想メモリ４００は、連想メモリ１００と同様に、メモリアレイ部１０と、ＷＴＡ回路２０とを備える。
【０１６６】
メモリアレイ部１０は、図１と同様に、メモリ部１と、行デコーダ２と、列デコーダ３と、Ｒｅａｄ／Ｗｒｉｔｅ回路４と、検索データ保存回路５とを備える。
【０１６７】
メモリ部１内のユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷの各々は、参照データをＫビット単位で保存する。
【０１６８】
ここで、第ｉ行（１≦ｉ≦Ｒ）に配置されたユニットデータ保存回路ＵＳｉｊ（１≦ｊ≦ｗ）に注目する。第ｉ行の保存回路Ｓｉに保存された参照データＲＥＦｉのうち、ユニットデータ保存回路ＵＳｉｊに保存されたデータを参照データＲＥＦｉｊとする。つまり、第ｉ行に保存された参照データＲＥＦｉは、ＲＥＦｉ１、ＲＥＦｉ２、・・・ＲＥＦｉｊ、・・・ＲＥＦｉｗで構成される。また、外部から入力される検索データをＳＷとする。検索データＳＷは、ＳＷ１、ＳＷ２、・・・ＳＷｊ、・・・ＳＷｗで構成される。
【０１６９】
検索データＳＷと参照データＲＥＦｉとの間のマンハッタン距離は、次の式（１）で示される。
【数１】
上述のとおり、ユニットデータ保存回路ＵＳｉｊはｋビットの参照データＲＥＦｉｊを保存する。そのため、ユニットデータ保存回路ＵＳｉｊはｋ個の記憶回路（たとえばＳＲＡＭ素子）を備える。各記憶回路は、参照データＲＥＦｉｊの各桁の参照ビットデータ（第１桁の参照ビットデータ〜最上位（第ｋ桁）の参照ビットデータ）をそれぞれ記憶する。
【０１７０】
ユニットデータ比較回路ＵＣｉｊは、対応するユニットデータ保存回路ＵＳｉｊに保存された参照データＲＥＦｉｊ（ｋビット）と、検索データＳＷｊ（ｋビット）とのマンハッタン距離を算出する。
【０１７１】
図１８に、第１行（ｉ＝１）に配置されるユニットデータ保存回路とユニットデータ比較回路と発振回路との機能ブロック図を示す。
【０１７２】
ユニットデータ保存回路ＵＳ１１は、Ｋ個の記憶回路ＳＲＡＭ１１〜ＳＲＡＭ１Ｋを備える。記憶回路ＳＲＡＭ１１には、参照データＲＥＦ１１の第１桁目の参照ビットデータが記憶されている。同様に、記憶回路ＳＲＡＭ１Ｋには、参照データＲＥＦ１１の第Ｋ桁目の参照ビットデータが記憶されている。
【０１７３】
ユニットデータ比較回路ＵＣ１１は、Ｋビット減算器４１０と、絶対値演算回路４２０とを備える。Ｋビット減算器４１０及び絶対値演算回路４２０は、検索データＳＷ１と参照データＲＥＦ１１との差の絶対値を算出する。
【０１７４】
具体的には、Ｋビット減算器４１０は、参照データＲＥＦ１１の第１桁目の参照ビットデータと、検索データＳＷ１の第１桁目の検索ビットデータとを差分する。そして、絶対値演算回路４２０は、その差分値を絶対値に換算し、出力信号ＯＪ１及び／ＯＪ１として出力する。出力信号／ＯＪ１は出力ＯＪ１の反転信号である。
【０１７５】
同様に、Ｋビット減算器４１０は、参照データＲＥＦ１１の第２桁目の参照ビットデータと検索データＳＷ１の第２桁目の検索ビットデータとを差分する。そして、絶対値演算回路４２０は、その差分値を絶対値に換算し、出力信号ＯＪ２及び／ＯＪ２として出力する。Ｋビット減算器４１０及び絶対値演算回路４２０は、参照データＲＥＦ１１の第３桁目以降のビットデータについても同様に算出し、出力信号ＯＪ３〜ＯＪＫ及び／ＯＪ３〜／ＯＪＫを出力する。
【０１７６】
同じ第１行のデータユニット保存回路ＵＳ１１〜ＵＳ１Ｗに格納された参照データＲＥＦ１１〜ＲＥＦ１Ｗと検索データＳＷ１〜ＳＷｗの比較結果（出力信号ＯＪ１〜ＯＪＫ×Ｗ個分）は、全て、同じ発振回路ＯＣＭ１に入力される。
【０１７７】
発振回路ＯＣＭ１は、比較回路Ｃ１の比較結果、つまり、求められた参照データＲＥＦ１と検索データＳＷとのマンハッタン距離に応じて、出力するパルス信号Ｐ１の発振周波数を決定する。
【０１７８】
発振回路ＯＣＭ１の機能ブロック図を図１９に示す。発振回路ＯＣＭ１は偶数個の遅延回路ＤＬ１０１〜ＤＬ１０Ｗと、ＮＡＮＤゲート３００とを備える。偶数個の遅延回路ＤＬ１０１〜ＤＬ１０ＷとＮＡＮＤゲート３００とは、動作時に、入力信号を反転する反転回路として機能する。したがって、発振回路ＯＣＭ１は、ループ状に直列に連結された複数の反転回路を備える。遅延回路ＤＬ１０１の出力は外部に出力されると共に、ＮＡＮＤゲート３００に入力される。つまり、遅延回路ＤＬ１０１〜ＤＬ１０Ｗ及びＮＡＮＤゲート３００はリングオシレータを構成する。
【０１７９】
遅延回路ＤＬ１０１はデータユニット保存回路ＵＳ１１に対応する。遅延回路ＤＬ１０２はデータユニット保存回路ＵＳ１２に対応する。以降、同様に、遅延回路ＤＬ１０３〜ＤＬ１０Ｗは、データユニット保存回路ＵＳ１３〜ＵＳ１Ｗにそれぞれ対応する。
【０１８０】
遅延回路ＤＬ１０１の構成を図２０に示す。遅延回路ＤＬ１０１は、複数の遅延回路ＤＪ１〜ＤＪＫと、インバータＩ５０とを備える。遅延回路ＤＪ１〜ＤＪＫ及びインバータＩ５０は直列に接続される。
【０１８１】
遅延回路ＤＪ１は、遅延段ＤＥＬ１と段数選択回路５５とを備える。遅延段ＤＥＬ１は、直列に接続された複数のインバータで構成される。遅延回路ＤＪ１は、出力信号ＯＪ１に応じて、利用するインバータ段数を選択する。換言すると、遅延回路ＤＪ１は、信号ＯＪ１に応じて遅延段ＤＥＬ１を利用するか否かを選択する。
【０１８２】
距離判定回路ＤＪ１は、遅延回路ＤＬ１０２からの出力を受ける。そして、ユニットデータ比較回路ＵＣ１１から出力された信号ＯＪ１及び／ＯＪ１に基づいて、ユニットデータ保存回路ＵＳ１１に保存された参照データＲＥＦ１１のうち、第１桁目の参照ビットデータの距離を求める。参照データＲＥＦ１１の第１桁目の参照ビットデータが、検索データＳＷ１の第１桁目の検索ビットデータと一致するとき、信号ＯＪ１はＨレベルとなり、信号／ＯＪ１はＬレベルとなる。一方、参照データＲＥＦ１１の第１桁目の参照ビットデータが、検索データＳＷ１の第１桁目の検索ビットデータと一致しないとき、信号ＯＪ１はＬレベルとなり、信号／ＯＪ１はＨレベルとなる。
【０１８３】
段数選択回路５５は、トランスファゲートＧＴ１０とＧＴ１１とを備える。トランスファゲートＴＧ１０及びＴＧ１１は並列に接続される。遅延段ＤＥＬ１は、遅延回路ＤＪ１の入力端子とトランスミッションゲートＧＴ１０との間に接続される。
【０１８４】
参照データＲＥＦ１１の第１桁目の参照ビットデータと検索データＳＷ１の第１桁目の検索ビットデータとが一致するとき、トランスファゲートＴＧ１１がオンになり、ＴＧ１０がオフになる。この場合、入力信号は遅延段ＤＥＬ１を通らずにトランスファゲートＧＴ１１を通過し、外部に出力される。
【０１８５】
一方、参照データＲＥＦ１１の第１桁目の参照ビットデータと検索データＳＷ１の第１桁目の検索ビットデータとが一致しないとき、トランスファゲートＧＴ１０がオンになる。この場合、入力信号は遅延段ＤＥＬ１により設定された遅延時間ΔＴ１だけ遅延して、外部に出力される。
【０１８６】
要するに、遅延回路ＤＪ１は、２通りの遅延時間を設定でき、参照ビットデータと検索ビットデータとが異なる場合に２通りの遅延時間のうち、長い方の遅延時間を選択する。
【０１８７】
遅延回路ＤＪ２〜ＤＪＫも遅延回路ＤＪ１と同様に動作する。各遅延回路ＤＪ２〜ＤＪｋは、２通りの遅延時間を設定でき、参照ビットデータと検索ビットデータとの比較結果に応じて２通りの遅延時間のいずれかを選択する。そのため、遅延回路ＤＬ１０１は、ｋビットの参照ビットデータとｋビットの検索ビットデータとの比較結果に基づいて、２ｋ通りの遅延時間を設定できる。換言すると、遅延回路ＤＬ１０１は、互いに遅延時間の異なる２ｋ通りのパスを備え、ｋ個の参照ビットデータとｋ個の検索ビットデータとのマンハッタン距離に応じてパスを選択する。
遅延回路ＤＪ２内の遅延段の遅延時間は、遅延段ＤＥＬ１の２倍とする。つまり、桁が上がるに従って遅延時間ΔＴを長く設定する。これにより、桁が最上位ビットに近いほど、長い遅延時間が設定される。つまり、マンハッタン距離が大きい程、遅延時間が長くなる。
【０１８８】
各遅延回路ＤＬ１０２〜ＤＬ１０Ｗも、遅延回路ＤＬ１０１と同じ構成を有し、同様の動作をする。そのため、発振回路ＯＣＭ１は、保存回路Ｓ１に保存された参照データと検索データとのマンハッタン距離に応じた発振周波数の信号を出力する。具体的には、参照データと検索データとのマンハッタン距離が近い程、高い発振周波数の信号を出力する。
【０１８９】
上述では第１行の保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＭ１の構成及び動作を説明した。しかしながら、第２行目以降の保存回路Ｓ２〜ＳＲ、比較回路Ｃ２〜ＣＲ及び発振回路ＯＣＭ２〜ＯＣＭＲの構成及び動作も、保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＭ１と同様である。
【０１９０】
したがって、連想メモリ４００は、連想メモリ１００と同様に、距離に応じて発振周波数を変更できる。
【０１９１】
［第８の実施の形態］
本発明による連想メモリは、ハミング距離やマンハッタン距離だけでなく、ユークリッド距離にも適用できる。
【０１９２】
ユークリッド距離に適用される連想メモリの構成は、連想メモリ４００と同様である。メモリ部１内のユニットデータ保存回路ＵＳ１１〜ＵＳ１Ｗ、ＵＳ２１〜ＵＳ２Ｗ、・・・、ＵＳＲ１〜ＵＳＲＷの各々は、参照データをＫビット単位で保存する。第ｉ行の保存回路Ｓｉに保存された参照データＲＥＦｉのうち、ユニットデータ保存回路ＵＳｉｊに保存されたデータを参照データＲＥＦｉｊとする。つまり、第ｉ行に保存された参照データＲＥＦｉは、ＲＥＦｉ１、ＲＥＦｉ２、・・・ＲＥＦｉｊ、・・・ＲＥＦｉｗで構成される。また、外部から入力される検索データをＳＷとする。検索データＳＷは、ＳＷ１、ＳＷ２、・・・ＳＷｊ、・・・ＳＷｗで構成される。
【０１９３】
検索データＳＷと参照データＲＥＦｉとの間のユークリッド距離は、次の式（２）で示される。
【数２】
ユニットデータ保存回路ＵＳｉｊはＫビットの参照データＲＥＦｉｊを保存する。そのため、ユニットデータ保存回路ＵＳｉｊはＫ個の記憶回路（ＳＲＡＭ素子）を備える。各記憶回路は、参照データＲＥＦｉｊの各桁のビットデータ（第１桁のビットデータ〜最上位（第ｋ桁）ビットデータ）をそれぞれ記憶する。
【０１９４】
ユニットデータ比較回路ＵＣｉｊは、対応するユニットデータ保存回路ＵＳｉｊに保存された参照データＲＥＦｉｊ（ｋビット）と、検索データＳＷｊ（ｋビット）とのユークリッド距離を算出する。
【０１９５】
図２１に、第１行（ｉ＝１）に配置されるユニットデータ保存回路とユニットデータ比較回路と発振回路との機能ブロック図を示す。
【０１９６】
ユニットデータ保存回路ＵＳ１１は、Ｋ個の記憶回路ＳＲＡＭ１１〜ＳＲＡＭ１Ｋを備える。記憶回路ＳＲＡＭ１１には、参照データＲＥＦ１１の第１桁目のビットデータが記憶されている。同様に、記憶回路ＳＲＡＭ１Ｋには、参照データＲＥＦ１１の第Ｋ桁目のビットデータが記憶されている。
【０１９７】
ユニットデータ比較回路ＵＣ１１は、Ｋビット減算器４１０と、絶対値演算回路４２０と、比較電流信号生成回路４３０と、アナログスクエア回路４４０と、Ａ／Ｄコンバータ４５０とを備える。
【０１９８】
Ｋビット減算器４１０及び絶対値演算回路４２０は、検索データＳＷ１と参照データＲＥＦ１１との差の絶対値を算出する。算出結果は、対応する比較電流信号生成回路４３０で絶対値に応じた値のアナログ電流に変換される。
【０１９９】
変換されたアナログ電流はアナログスクエア回路４４０で２乗される。これにより、参照データＲＥＦ１１と、検索データＳＷ１とのユークリッド距離がアナログ電流値で出力される。
【０２００】
Ａ／Ｄコンバータ４５０は、出力されたアナログ電流をデジタル変換する。これにより、ユークリッド距離がｎビットのデジタルデータで出力される。
【０２０１】
発振回路ＯＣＥ１は、発振回路ＯＣ１やＯＣＭ１と同様に、ユークリッド距離に応じた発振周波数のパルス信号Ｐ１を出力する。発振回路ＯＣＥ１は、複数のインバータからなる遅延段と、段数選択回路とを備える。発振回路ＯＣＥ１内の段数選択回路は、ユークリッド距離が小さいほど、使用するインバータ段数を少なく選択する。そのため、ユークリッド距離が小さいほど高い発信周波数のパルス信号Ｐ１が出力される。
【０２０２】
第１行の保存回路Ｓ１内の他のユニットデータ保存回路ＵＳ１２〜ＵＳ１Ｗ、ユニットデータ比較回路ＵＣ１２〜ＵＣ１Ｗの動作も上述の通りである。また、第２行目以降の保存回路Ｓ２〜ＳＲ、比較回路Ｃ２〜ＣＲ及び発振回路ＯＣＥ２〜ＯＣＥＲの構成及び動作も、保存回路Ｓ１、比較回路Ｃ１及び発振回路ＯＣＥ１と同様である。したがって、ユークリッド距離を適用した連想メモリも、連想メモリ１００と同様に、距離に応じて発振周波数を変更できる。
【０２０３】
［第９の実施の形態］
上述の実施の形態において、ＷＴＡ回路２０（図５）やＷＴＡ回路２５（図９）について説明した。しかしながら、ＷＴＡ回路は、図５や図９に限定されない。
図２２は、ＷＴＡ回路の他の例を示す。図２２を参照して、ＷＴＡ回路３５０は、検知回路３５１と、複数の判定回路ＪＣ１１〜ＪＣ１Ｒとを備える。判定回路ＪＣ１１は発振回路ＯＣ１に対応し、発振回路ＯＣ１の出力信号を受ける。同様に、判定回路ＪＣ１２は発振回路ＯＣ２に対応し、発振回路ＪＣ１Ｒは発振回路ＯＣＲに対応する。
判定回路ＪＣ１１は、判定回路ＪＣ１と比較して、放電回路２５０及びクロック生成回路２５３を有さない。他の構成は判定回路ＪＣ１と同じである。判定回路ＪＣ１２〜ＪＣ１Ｒの構成は、判定回路ＪＣ１１と同じである。
検知回路３５１は、発信回路ＯＣ１〜ＯＣＲの出力を受け、最も早く出力されたパルス信号を検知する。検知回路３５１は、最も早く出力されたパルス信号を受けたとき、検知信号を出力する。より具体的には、検知回路３５１は、各判定回路ＪＣ１１〜ＪＣ１Ｒ内のインバータＩ２０の出力を受ける。そして、いずれかのインバータＩ２０から最初にパルス信号を受けたとき、検知信号を出力する。
判定回路ＪＣ１１〜ＪＣ１２内のラッチ回路２５２は、インバータＩ２０の出力を受ける。つまり、対応する発振回路ＯＣ１〜ＯＣＲの出力信号を受ける。そして、検知信号を受けたとき、発信回路ＯＣ１〜ＯＣＲからの出力信号をラッチする。
判定回路ＪＣ１１が、最も早くパルス信号を受けるとき（つまり、発振回路ＯＣ１が最も周波数の高いパルス信号を出力するとき）、判定回路ＪＣ１１内のラッチ回路２５２は、Ｈレベルの信号をラッチする。そして、他の判定回路ＪＣ１２〜ＪＣ１Ｒ内のラッチ回路２５２は、Ｌレベルの信号をラッチする。以上の結果、判定回路ＪＣ１１はＷｉｎｎｅｒを示すＨレベルの判定信号ＪＳ１を出力し、他の判定回路ＪＣ１２〜ＪＣ１Ｒは、Ｌｏｏｓｅｒを示す判定回路ＪＳ２〜ＪＳＲを出力する。
検知回路３５０は、各判定回路ＪＣ１１〜ＪＣ１Ｒ内のインバータＩ２０の出力を受けるワイヤードＯＲ回路であってもよいし、複数段のＯＲ回路で構成されてもよい。
以上、本発明の実施の形態を説明したが、上述した実施の形態は本発明を実施するための例示に過ぎない。よって、本発明は上述した実施の形態に限定されることなく、その趣旨を逸脱しない範囲内で上述した実施の形態を適宜変形して実施することが可能である。
【符号の説明】
【０２０４】
１ メモリ部
２ 行デコーダ
３ 列デコーダ
４ Ｒｅａｄ／Ｗｒｉｔｅ回路
５ 検索データ保存回路
１０ メモリアレイ部
２０ ＷＴＡ回路
３０ プリチャージ回路
３５ 分周部
３１ クロック生成回路
４０ カウンタ部
５０ フィードバック回路
１００，１１０，２００，３００，４００ 連想メモリ
２５０ 放電回路
Ｓ１〜ＳＲ 保存回路
Ｃ１〜ＣＲ 比較回路
【特許請求の範囲】
【請求項１】
複数の参照データを保存する保存手段と、
入力された検索データと、前記複数の参照データの各々とを並列に比較して、前記検索データと前記参照データとの距離を、前記参照データごとに求める比較手段と、
前記求めた距離に応じた周波数を有するパルス信号を前記参照データごとに生成するパルス生成手段と、
前記生成された複数のパルス信号の周波数に基づいて、前記複数の参照データのうち、前記検索データに最も近い参照データを決定する決定手段とを備える連想メモリ。
【請求項２】
請求項１に記載の連想メモリであって、
前記パルス生成手段は、
前記複数の参照データに対応した複数の発振手段を備え、
前記各発振手段は、前記検索データと前記対応する参照データとの距離が小さいほど、周波数の高い前記パルス信号を出力し、
前記決定手段は、発振周波数の最も高いパルス信号を出力した発振手段に対応した参照データを、前記検索データに最も近い参照データに決定する連想メモリ。
【請求項３】
請求項２に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発振手段に対応した複数の判定手段を備え、
前記決定手段は、前記複数の判定手段のうち、前記発振手段からのパルス信号を最も早く受信した判定手段に基づいて、前記検索データに最も近い参照データを決定する連想メモリ。
【請求項４】
請求項２又は請求項３に記載の連想メモリであってさらに、
前記発振回路に対応した複数の分周手段を備え、
各分周手段は、対応する発振手段から出力されたパルス信号を所定の分周比で分周して、対応する判定手段に出力する連想メモリ。
【請求項５】
請求項３に記載の連想メモリであって、
前記決定手段は、
前記複数の判定手段に接続されたラッチ指示ノードと、
前記ラッチ指示ノードを充電する充電手段とを備え、
前記各判定手段は、
対応する前記発振手段からの出力信号を受け、前記出力信号が前記パルス信号であるとき前記ラッチ指示ノードを放電する放電手段と、
前記ラッチ指示ノードが放電されたときに前記放電手段が受けている前記出力信号をラッチするラッチ手段とを備える連想メモリ。
【請求項６】
請求項２に記載の連想メモリであって、
前記決定手段は、
複数段のトーナメント式に接続された複数の判定手段を備え、
第１段目に配置された複数の判定手段の各々は、
各々が対応する発振手段の出力信号を受ける複数の第１のパルス判定手段と、
前記複数の第１のパルス判定手段に接続されたパルス受付判定ノードと、
前記パルス受付判定ノードを充電する充電手段とを備え、
前記第１のパルス判定手段は、
前記対応する発振手段の出力信号としてパルス信号を受けたとき、前記パルス受付ノードを放電する第１の放電手段と、
クロック信号を受けたとき前記第１の放電手段が受けている出力信号をラッチするラッチ手段とを備え、
第２段目以降に配置された判定手段は、
各々が、前段の対応する判定手段のパルス受付判定ノードに接続された、複数の第２のパルス判定手段と、
前記複数の第２のパルス判定手段が接続されたパルス受付判定ノードと、
前記充電手段とを備え、
前記第２のパルス判定手段は、
前段の対応するトーナメント判定手段のパルス受付判定ノードが放電されたとき、前記パルス受付ノードを放電する第２の放電手段を備え、
最上段の判定手段はさらに、
前記パルス受付判定ノードが放電されたとき、クロック信号を出力するクロック信号生成手段を備える連想メモリ。
【請求項７】
請求項２又は請求項３に記載の連想メモリであって、
前記発信手段は、直列に接続された複数のインバータと、
前記検索データと前記対応する参照データとの距離に応じて、前記インバータの段数を選択する段数選択手段とを備える連想メモリ。
【請求項８】
請求項２に記載の連想メモリであって、
前記決定手段は、
複数の前記発振手段に対応する複数のカウンタ手段を備え、
前記カウンタ手段は、対応する発振手段からパルス信号を受け、所定数のパルスを受けたとき活性化された出力信号を生成する連想メモリ。
【請求項９】
請求項２に記載の連想メモリであってさらに、
ｊ（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までに決定手段により決定された参照データに対応する発振手段から出力されたパルス信号を無効化するパルス無効化手段を備えることを特徴とする連想メモリ。
【請求項１０】
請求項２に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記各参照ビットデータと前記各検索ビットデータとをハミング距離に基づいて比較し、
前記発信手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、Ｌ＋１個（Ｌは自然数）通りの遅延時間を設定可能であり、Ｌ個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。
【請求項１１】
請求項２に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記参照ビットデータと前記検索ビットデータとをマンハッタン距離に基づいて比較し、
前記発信手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、２ｋ（ｋは自然数）通りの遅延時間を設定可能であり、ｋ個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。
【請求項１２】
請求項３に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発信手段から出力されるパルス信号のうち、最も早く出力されたパルス信号を検知する検知手段を備え、
前記各判定手段は、
対応する前記発信手段から出力信号を受け、前記検知手段が最も早く出力されたパルス信号を検知したとき、前記出力信号をラッチする、連想メモリ。
【請求項１】
複数の参照データを保存する保存手段と、
入力された検索データと、前記複数の参照データの各々とを並列に比較して、前記検索データと前記参照データとの距離を、前記参照データごとに求める比較手段と、
前記求めた距離に応じた周波数を有するパルス信号を前記参照データごとに生成するパルス生成手段と、
前記生成された複数のパルス信号の周波数に基づいて、前記複数の参照データのうち、前記検索データに最も近い参照データを決定する決定手段とを備える連想メモリ。
【請求項２】
請求項１に記載の連想メモリであって、
前記パルス生成手段は、
前記複数の参照データに対応した複数の発振手段を備え、
前記各発振手段は、前記検索データと前記対応する参照データとの距離が小さいほど、周波数の高い前記パルス信号を出力し、
前記決定手段は、発振周波数の最も高いパルス信号を出力した発振手段に対応した参照データを、前記検索データに最も近い参照データに決定する連想メモリ。
【請求項３】
請求項２に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発振手段に対応した複数の判定手段を備え、
前記決定手段は、前記複数の判定手段のうち、前記発振手段からのパルス信号を最も早く受信した判定手段に基づいて、前記検索データに最も近い参照データを決定する連想メモリ。
【請求項４】
請求項２又は請求項３に記載の連想メモリであってさらに、
前記発振回路に対応した複数の分周手段を備え、
各分周手段は、対応する発振手段から出力されたパルス信号を所定の分周比で分周して、対応する判定手段に出力する連想メモリ。
【請求項５】
請求項３に記載の連想メモリであって、
前記決定手段は、
前記複数の判定手段に接続されたラッチ指示ノードと、
前記ラッチ指示ノードを充電する充電手段とを備え、
前記各判定手段は、
対応する前記発振手段からの出力信号を受け、前記出力信号が前記パルス信号であるとき前記ラッチ指示ノードを放電する放電手段と、
前記ラッチ指示ノードが放電されたときに前記放電手段が受けている前記出力信号をラッチするラッチ手段とを備える連想メモリ。
【請求項６】
請求項２に記載の連想メモリであって、
前記決定手段は、
複数段のトーナメント式に接続された複数の判定手段を備え、
第１段目に配置された複数の判定手段の各々は、
各々が対応する発振手段の出力信号を受ける複数の第１のパルス判定手段と、
前記複数の第１のパルス判定手段に接続されたパルス受付判定ノードと、
前記パルス受付判定ノードを充電する充電手段とを備え、
前記第１のパルス判定手段は、
前記対応する発振手段の出力信号としてパルス信号を受けたとき、前記パルス受付ノードを放電する第１の放電手段と、
クロック信号を受けたとき前記第１の放電手段が受けている出力信号をラッチするラッチ手段とを備え、
第２段目以降に配置された判定手段は、
各々が、前段の対応する判定手段のパルス受付判定ノードに接続された、複数の第２のパルス判定手段と、
前記複数の第２のパルス判定手段が接続されたパルス受付判定ノードと、
前記充電手段とを備え、
前記第２のパルス判定手段は、
前段の対応するトーナメント判定手段のパルス受付判定ノードが放電されたとき、前記パルス受付ノードを放電する第２の放電手段を備え、
最上段の判定手段はさらに、
前記パルス受付判定ノードが放電されたとき、クロック信号を出力するクロック信号生成手段を備える連想メモリ。
【請求項７】
請求項２又は請求項３に記載の連想メモリであって、
前記発信手段は、直列に接続された複数のインバータと、
前記検索データと前記対応する参照データとの距離に応じて、前記インバータの段数を選択する段数選択手段とを備える連想メモリ。
【請求項８】
請求項２に記載の連想メモリであって、
前記決定手段は、
複数の前記発振手段に対応する複数のカウンタ手段を備え、
前記カウンタ手段は、対応する発振手段からパルス信号を受け、所定数のパルスを受けたとき活性化された出力信号を生成する連想メモリ。
【請求項９】
請求項２に記載の連想メモリであってさらに、
ｊ（ｊは、１＜ｊ≦ｋを満たす整数、ｋは、２以上の整数）回目の検索において、ｊ−１回目までに決定手段により決定された参照データに対応する発振手段から出力されたパルス信号を無効化するパルス無効化手段を備えることを特徴とする連想メモリ。
【請求項１０】
請求項２に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記各参照ビットデータと前記各検索ビットデータとをハミング距離に基づいて比較し、
前記発信手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、Ｌ＋１個（Ｌは自然数）通りの遅延時間を設定可能であり、Ｌ個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。
【請求項１１】
請求項２に記載の連想メモリであって、
前記参照データは、複数の参照ビットデータを含み、
前記検索データは、前記参照ビットデータに対応する複数の検索ビットデータを含み、
前記比較手段は、前記参照ビットデータと前記検索ビットデータとをマンハッタン距離に基づいて比較し、
前記発信手段は、
直列に接続される複数の遅延手段を備え、
前記各遅延手段は、２ｋ（ｋは自然数）通りの遅延時間を設定可能であり、ｋ個の参照ビットデータ及び検索ビットデータの比較結果に応じて、前記遅延時間を選択する連想メモリ。
【請求項１２】
請求項３に記載の連想メモリであって、
前記決定手段はさらに、
前記複数の発信手段から出力されるパルス信号のうち、最も早く出力されたパルス信号を検知する検知手段を備え、
前記各判定手段は、
対応する前記発信手段から出力信号を受け、前記検知手段が最も早く出力されたパルス信号を検知したとき、前記出力信号をラッチする、連想メモリ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１１−７６６８８（Ｐ２０１１−７６６８８Ａ）
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２００９−２２９６０１（Ｐ２００９−２２９６０１）
【出願日】平成２１年１０月１日（２００９．１０．１）
【出願人】（５０４１３６５６８）国立大学法人広島大学 (924)
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年１０月１日（２００９．１０．１）
【出願人】（５０４１３６５６８）国立大学法人広島大学 (924)
[ Back to top ]