(57)【特許請求の範囲】
【請求項１】
内部に格納されたｍビット×ｎワードのデータ群の中から、外部から入力されたｍビットの検索データに一致するデータを検出する連想メモリにおいて、
各ワード毎の格納データと検索データとをビット毎に照合し、このビット毎の照合結果を入力するｍ個のＭＯＳトランジスタを直列接続し、この直列接続回路のうち、ＭＳＢ側から連続して一致しているビットの範囲とそれ以外の範囲とを異なる電位として、且つＬＳＢ側回路の電位を出力する各ワード毎の論理演算回路と、
最初の照合動作の実行後に、同じビットを構成するｎ個の連想メモリセルから、それぞれ前記各ワード毎の論理演算回路を構成するＭＯＳトランジスタの出力側の電位を各ビット毎の論理和演算回路に入力し、ＭＳＢ側から連続して最も多数のビットが一致しているワードの一致しているビットの出力情報を得る前記各ビット毎の論理和演算回路とを設けて、
完全に一致するデータが無い場合には、前記各ビット毎の論理和演算回路の出力情報により一致しているビット以外をマスクビットとして再度照合動作を行い、前記各ワード毎の論理演算回路の出力によりＭＳＢ側から連続して最も多くのビットが一致しているデータを検出することができることを特徴とする連想メモリ。
【請求項２】
内部に格納されたｍビット×ｎワードのデータ群の中から、外部から入力されたｍビットの検索データに一致するデータを検出する連想メモリにおいて、
各ワード毎の格納データと検索データとをビット毎に照合し、このビット毎の照合結果を入力するｍ個のＮＭＯＳトランジスタを直列接続して構成したダイナミックＮＡＮＤ回路により、前記直列接続回路のうち、ＭＳＢ側から連続して一致しているビットの範囲とそれ以外の範囲とを異なる電位として、且つＬＳＢ側回路の電位を出力する各ワード毎の論理演算回路と、
連想メモリの各連想メモリセルに、前記ダイナミックＮＡＮＤ回路を構成するＮＭＯＳトランジスタのドイレン側のノードがゲートに接続され、正電源がソースに接続されたＰＭＯＳトランジスタをそれぞれ設け、同じビットを構成するｎ個の連想メモリセル内の前記ＰＭＯＳトランジスタのドレインを共通に接続し、前記の共通接続端子と接地電位との間にＮＭＯＳトランジスタを設け、前記ＮＭＯＳトランジスタのオン及びオフ後の最初の照合動作の実行後に、前記各ビット毎の共通接続端子の電位から、ＭＳＢ側から連続して最も多数のビットが一致しているワードの一致しているビットの出力情報を得る各ビット毎の論理演算回路とを設けて、
完全に一致するデータが無い場合には、前記各ビット毎の論理演算回路の出力情報により一致しているビット以外をマスクビットとして再度照合動作を行い、前記各ワード毎の論理演算回路の出力によりＭＳＢ側から連続して最も多くのビットが一致しているデータを検出することができることを特徴とする連想メモリ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力された検索データに対して、内部に格納されたデータ群のうちから完全に一致するデータの検出と、完全に一致するデータが無い場合には、内部に格納されたデータ群のうちＭＳＢ側から連続して最も多くのビットが連続して一致するデータの検出（最長一致の検出）が可能な連想メモリに関するものである。
【０００２】
【従来の技術】
連想メモリは、内部に格納されたデータ群と、検索データとして入力されたビット列とを照合して一致するデータを検出し、そのデータが格納されているアドレスを外部に出力するものであり、ネットワークシステム内におけるルーティング情報の検索等に適用される。
なお、以降の説明では、連想メモリをＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）と略記する。
【０００３】
ＣＡＭには、一般的に、検索データとして入力したビット列のうち、照合対象から除外するビットを１ビットずつ設定する手段が備えられている。照合対象から除外することをマスクと称し、照合対象から除外されたビットをマスクビットと称する。
最長一致の検出とは、完全に一致するデータが無い場合に、ＭＳＢ（最大有効ビット）側から連続して最も多くのビットが一致するデータを検出することである。
最長一致の検出は、例えば特開平１１−７７８２号公報（最長一致検出装置）等に示されているように、カウンタ等の手段によりマスクビットをＬＳＢ（最小有効ビット）側から１ビットずつ増やしながら照合動作を繰り返し、最初に一致するデータを調べることにより実現できる。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来の最長一致検出方法では、マスクビットを１ビットずつシフトして照合を行うため、一致の検出までに時間を要するという欠点がある。
例えばネットワークシステムで一般的な３２ビットのアドレス値を検索データとした場合、最大で３２回の照合動作が必要となる。前記の特許公報に記載のようにＣＡＭを分割した場合、例えば４個に分割し、８ビット（１バイト）長の連想メモリを４個設けるようにした場合でも、照合動作は８回必要となる。
ＣＡＭをネットワークシステム内でルーティング情報の検索に適用した場合、一致の検出までに時間を要することはスループットの低下に繋がり、ネットワークの使用効率の低下を招くので好ましくない。
また、ＣＡＭの照合動作には、多数の長い配線に対する容量の充放電が伴うため、複数回の照合動作の連続実行が必要な従来の検出方法には、消費電流が大きいという欠点もある。
【０００５】
【課題を解決するための手段】
本発明に係る連想メモリは、内部に格納されたｍビット×ｎワードのデータ群の中から、外部から入力されたｍビットの検索データに一致するデータを検出する連想メモリにおいて、各ワード毎の格納データと検索データとをビット毎に照合し、このビット毎の照合結果を入力するｍ個のＭＯＳトランジスタを直列接続し、この直列接続回路のうち、ＭＳＢ側から連続して一致しているビットの範囲とそれ以外の範囲とを異なる電位として、且つＬＳＢ側回路の電位を出力する各ワード毎の論理演算回路と、最初の照合動作の実行後に、同じビットを構成するｎ個の連想メモリセルから、それぞれ前記各ワード毎の論理演算回路を構成するＭＯＳトランジスタの出力側の電位を各ビット毎の論理和演算回路に入力し、ＭＳＢ側から連続して最も多数のビットが一致しているワードの一致しているビットの出力情報を得る前記各ビット毎の論理和演算回路とを設けて、完全に一致するデータが無い場合には、前記各ビット毎の論理和演算回路の出力情報により一致しているビット以外をマスクビットとして再度照合動作を行い、前記各ワード毎の論理演算回路の出力によりＭＳＢ側から連続して最も多くのビットが一致しているデータを検出することができるものである。
【０００６】
【発明の実施の形態】
実施形態１
図２は本発明の実施形態１に係る１ビット分のＣＡＭセルの回路図である。
図２の回路のうち、ワード線２０と、相補のビット線２１ａ及び２１ｂと、インバータＮＶ２１およびＮＶ２２と、ＮＭＯＳトランジスタＮＭ２１及びＮＭ２２とにより、一般的な１ビット分のＳＲＡＭ回路を構成している。
また、照合用のＮＭＯＳトランジスタＮＭ２３，ＮＭ２４，ＮＭ２５と、マッチ線２２は、上記のＳＲＡＭ回路に対して図示のように接続される。
【０００７】
図１は本発明の実施形態１に係るＣＡＭの回路図である。
図１においては、図２に示したＣＡＭセルが縦・横のアレイ状に配置され、横方向の１行が同じワード線に接続され１ワードを構成し、縦方向の１列が同じビット線対に接続され１ビットを構成している。
ここでは、説明を簡単にするために３ビット×３ワード構成のＣＡＭとしているが、通常はビット数及びワード数は、これより大きい値となる。
なお、図１の接続の場合、１ビット目がＭＳＢ、３ビット目がＬＳＢとなる。
【０００８】
図１のワード１の回路によって、１ワード分の回路の接続について説明する。図２のＮＭ２５に相当する３ビット分のＮＭＯＳトランジスタＮＭ１５１１，ＮＭ１５１２，ＮＭ１５１３が直列に接続され、この直列接続の３個のトランジスタＮＭ１５１１〜１５１３と、これらの両端に接続されたプリチャージ用のＰＭＯＳトランジスタＰＭ１１１及びＮＭＯＳトランジスタＮＭ１１１とで一般的なダイナミックＮＡＮＤ回路が構成され、この直列接続回路のＬＳＢ側の電位をインバータＮＶ１１１で反転させて取り出している。
上記トランジスタＰＭ１１１及びＮＭ１１１のゲートには、プリチャージ用の制御信号１４が接続され、この制御信号１４は全ワードに対して同様に接続される。
なお、ここではワード線の駆動回路は省略している。
【０００９】
次に、図１のビット１の回路によって、１ビット分の回路の接続について説明する。
図２のＮＭ２５に相当するＮＭＯＳトランジスタＮＭ１５１１，ＮＭ１５２１，ＮＭ１５３１のドレイン側の各信号がＮＡＮＤ回路ＮＤ１６１に入力され、このＮＤ１６１のＮＡＮＤ演算結果がビット線駆動回路１３１に入力される。このＮＡＮＤ演算はスタティック（ＣＭＯＳ）ＮＡＮＤ回路で行なってもよく、またダイナミックＮＡＮＤ回路で行なってもよい。
ビット線駆動回路１３１には、上記ＮＡＮＤ演算結果信号のほかに、各ビット毎の、書き込み／照合データ信号と、マスク設定信号と、ビット線駆動用制御信号１６が入力される。またビット線対（図２の２１ａ，２１ｂに相当）もビット線駆動回路１３１に接続される。
【００１０】
図５は本発明におけるＣＡＭの動作概要の説明図であり、同図により本発明の動作の概要を述べる。
まず、ＣＡＭ内に格納されたワード１、ワード２、…、ワードｎの各データと、ＣＡＭに入力されたデータとの照合を行い、ＭＳＢ側から連続して最も多数のビットが一致しているワード（図５ではワード４）の、連続して一致している領域Ａと、それ以外の領域Ｂを検出する。
次に、領域Ｂをマスクビットとして再度照合を行なうことにより、ワード４が「一致」として検出される。
【００１１】
図６は本発明のワード毎の論理演算処理とビット毎の論理和演算処理の説明図であり、図６は図５の格納データと入力データとの一致、不一致に対応した処理を示している。
本発明のワード毎の論理演算処理は、ＣＡＭ内に格納されたワード１，ワード２，…ワードｎの各データと、ＣＡＭに入力されたデータとの各ビット毎の一致（図５の黒地部）、不一致（図５の白地部）を調べ、各ワード毎に、ＭＳＢ側から連続して一致しているビットの範囲（図６のハッチングで囲まれているＬの範囲）はＬｏｗ電位に、それ以外のＬＳＢまでの範囲（図６の白地のＨの範囲）はＨｉｇｈ電圧として、且つＬＳＢ側の電位を出力（実施形態では反転出力）するものである。
また本発明のビット毎の論理和演算処理は、上記各ワード毎の論理演算処理の出力信号である各ワード毎のＭＳＢ側から連続して一致しているビット範囲を示すＬｏｗ電位の各ビット毎の論理和演算を行うことにより、ＭＳＢ側から連続して最も多数のビットが一致しているワード（図６のワード４）の一致しているビットの出力情報（本実施形態ではワード４のＬｏｗ電位とＨｉｇｈ電位の反転出力）を得るものである。
【００１２】
以下に、具体的な動作について説明する。
図２により、１ビット分のＣＡＭセルの動作について説明する。
データの書き込み動作は、通常のＳＲＡＭと同様に行なう。いま相補のビット線２１ａ，２１ｂのうち２１ａを正相とすると、ＣＡＭセルへ“１”を書き込むには、ビット線２１ａ，２１ｂをそれぞれＨｉｇｈ、Ｌｏｗ電位にし、ワード線２０をＨｉｇｈ電位にし、トランジスタＮＭ２１，ＮＭ２２をＯＮにする。逆に“０”を書き込むには、ビット線２１ａ，２１ｂをそれぞれＬｏｗ、Ｈｉｇｈ電位にする。
【００１３】
照合動作は、ワード線２０をＬｏｗ電位にし、トランジスタＮＭ２１，ＮＭ２２をＯＦＦにした状態で相補のビット線２１ａ，２１ｂに照合値を印加する。
いまＣＡＭセル内の値が“１”のとき、トランジスタＮＭ２３がＯＮしているので、照合値が“１”（ビット線２１ａの電位がＨｉｇｈ）であれば、トランジスタＮＭ２５がＯＮし、逆に照合値が“０”（ビット線２１ａの電位がＬｏｗ）の場合、トランジスタＮＭ２５はＯＦＦとなる。
また、ＣＡＭセル内の値が“０”のとき、トランジスタＮＭ２４がＯＮしているので、照合値が“０”（ビット線２１ｂの電位がＨｉｇｈ）であれば、トランジスタＮＭ２５がＯＮし、逆に照合値が“１”（ビット線２１ｂの電位がＬｏｗ）の場合、トランジスタＮＭ２５はＯＦＦとなる。
【００１４】
このように、ＣＡＭセル内の値とビット線に印加された値が一致すると、トランジスタＮＭ２５はＯＮとなり、一致しない場合ＯＦＦとなる。
あるビットをマスクする場合は、照合時にビット線２１ａ，２１ｂの電位を共にＨｉｇｈにする。このとき、ＣＡＭセル内の値が“１”、“０”のどちらでも（トランジスタＮＭ２３，ＮＭ２４のいずれがＯＮしていても）、トランジスタＮＭ２５がＯＮするので、このビットは常に一致とみなされる。その結果、このビットは照合対象から除外される。
【００１５】
図１により、本発明の実施形態１のＣＡＭの動作について説明する。
検索動作は、一般的なＣＡＭと同様である。
まず、ビット線駆動用制御信号１６によりビット線駆動回路１３１〜１３３を制御し、ビット毎に設けられたビット線対の電位を共にＨｉｇｈにし、ＮＭＯＳトランジスタＮＭ１５１１〜ＮＭ１５１３、ＮＭ１５２１〜ＮＭ１５２３、ＮＭ１５３１〜ＮＭ１５３３を全てＯＮにした状態で、プリチャージ信号１４をＬｏｗ電位にし、ＰＭＯＳトランジスタＰＭ１１１〜ＰＭ１１３をＯＮに、ＮＭＯＳトランジスタＮＭ１１１〜ＮＭ１１３をＯＦＦにすることにより、各ワードのダイナミックＮＡＮＤ回路内のノード１２１０〜１２１３、１２２０〜１２２３、１２３０〜１２３３をＨｉｇｈ電位にする。
【００１６】
次に、制御信号１６によりビット線駆動回路１３１〜１３３を制御し、各ビット毎に照合値を印加してから、プリチャージ信号１４をＨｉｇｈ電位に戻しＰＭＯＳトランジスタＰＭ１１１〜ＰＭ１１３をＯＦＦに、ＮＭＯＳトランジスタＮＭ１１１〜ＮＭ１１３をＯＮにする。
なお、検索データを印加する際、マスク設定信号によりマスクビットとされているビットについては、ビット線対には共にＨｉｇｈ電位が印加され、ＣＡＭセル内の値と照合値が一致したのと等価になる。
【００１７】
前述のように各ＣＡＭセル内のＮＭＯＳトランジスタＮＭ１５１１〜ＮＭ１５１３、ＮＭ１５２１〜ＮＭ１５２３、ＮＭ１５３１〜ＮＭ１５３３はＣＡＭセル内の値と照合値が一致するとＯＮとなるから、例えばワード１の全てのビットが一致するとノード１２１３（ＬＳＢ側）の電位はＬｏｗに、インバータＮＶ１１１の出力はＨｉｇｈになる。
このように、インバータＮＶ１１１〜ＮＶ１１３出力がＨｉｇｈであることにより、そのワードには検索データに一致するデータが格納されていることが示されている。
【００１８】
検索データを印加した際に、例えば
ワード１の１ビット目と２ビット目、
ワード２の１ビット目、
ワード３の２ビット目と３ビット目、
が検索データに一致し、残りのビットが不一致であれば、どのワードのデータも検索データと完全には一致しないため、インバータＮＶ１１１〜ＮＶ１１３の出力は全てＬｏｗである。
【００１９】
このとき、ダイナミックＮＡＮＤ回路内のノードの電位に着目すると、
ワード１では、トランジスタのＮＭ１５１１とＮＭ１５１２がＯＮ、ＮＭ１５１３はＯＦＦとなるので、ノードの１２１１，１２１２（ＭＳＢと次のビットの範囲）の電位がＬｏｗ、１２１３（その他のビットの範囲）の電位はＨｉｇｈとなる。
ワード２では、トランジスタのＮＭ１５２１がＯＮ、ＮＭ１５２２とＮＭ１５２３はＯＦＦとなるので、ノードの１２２１（ＭＳＢの範囲）の電位がＬｏｗ、１２１２と１２１３（その他のビットの範囲）の電位はＨｉｇｈとなる。
ワード３では、トランジスタのＮＭ１５３２とＮＭ１５３３がＯＮするが、ＮＭ１５３１がＯＦＦとなるので、ノード１２３１〜１２３３（ＭＳＢからＬＳＢまでの全範囲）の電位はＨｉｇｈのままである。
このように、各ワード毎の論理演算回路は、直列接続されたダイナミックＮＡＮＤ回路のノードのうち、ＭＳＢ側から連続して一致しているビットの範囲はＬｏｗ電位に、それ以外のＬＳＢまでの範囲はＨｉｇｈ電位として、且つＬＳＢ側の電位を出力（この場合反転出力）するものである（図６の各ワード電位を参照）。
【００２０】
前記各ワード毎の論理演算回路の同じビットを構成する３つのノード１２１１〜１２３１、１２１２〜１２３２、１２１３〜１２３３の電位はそれぞれＮＡＮＤ回路１６１，１６２，１６３に入力される。
その結果、１ビット目のＮＡＮＤ回路ＮＤ１６１の出力はＨｉｇｈ、
２ビット目のＮＡＮＤ回路ＮＤ１６２の出力はＨｉｇｈ、
３ビット目のＮＡＮＤ回路ＮＤ１６３の出力はＬｏｗとなる。
上記各ワード毎の論理演算回路のうちで重要な信号は、前記ＭＳＢ側から連続しているビットの範囲を示すＬｏｗ電位であり、このＬｏｗ電位の信号に対しては、ＮＡＮＤ回路は論理和演算をしたことになる（但し出力は反転してＨｉｇｈ電位となる）。
つまり、ＮＡＮＤ回路ＮＤ１６１〜ＮＤ１６３の出力値により、ＭＳＢ（ビット１）側からみて最も多くのビットが連続して一致しているワード（この場合はワード１）の、一致しているビット（この場合はビット１，２）が、ＮＤ１６１とＮＤ１６２の出力のＨｉｇｈにより示される（図６の論理和反転出力を参照）。
ここでは、ＮＡＮＤ回路ＮＤ１６１〜ＮＤ１６３の出力値を「最長一致信号」と称する。
【００２１】
次に、ビット線駆動回路の制御信号１６により、ＮＡＮＤ回路ＮＤ１６１〜ＮＤ１６３の出力値がＬｏｗのビット（この場合はビット３）はマスクビットとし、ビット線対の双方にＨｉｇｈの電位を印加する。
このとき、ビット３では、既にＯＮとなっていたトランジスタのＮＭ１５３３に加え、ＮＭ１５１３、ＮＭ１５２３がＯＮとなる。
ワード１では既にトランジスタのＮＭ１１１，ＮＭ１５１１，ＮＭ１５１２がＯＮとなっているので、ノード１２１３の電位がＬｏｗになり、インバータＮＶ１１１の出力はＨｉｇｈ、すなわち「一致」となる。
ワード２ではトランジスタＮＭ１５２２がＯＦＦで、ワード３ではトランジスタＮＭ１５３１がＯＦＦとなっているので、ノード１２２３及び１２３３の電位はＨｉｇｈのままであり、インバータＮＶ１１２及びＮＶ１１３の出力はＬｏｗ、すなわち「不一致」となる。
以上の動作により、最長一致の検出が行われる。
【００２２】
以上のように本実施形態１によれば、
最初の、最長一致信号によりマスクビットを設定せずに行なう照合動作と、
次の、最長一致信号によりマスクビットを設定して行なう照合動作と、
計２度の照合動作により最長一致の検出が可能となる。
従って従来のように、照合データのビット数の増加によって照合回数が増加することはない。
【００２３】
実施形態２
図３は本発明の実施形態２に係る１ビット分のＣＡＭセルの回路図である。
図３の構成は、図２に示した１ビット分のＣＡＭセルに、ＰＭＯＳトランジスタＰＭ３１と最長一致線３３が付加され、マッチ線２２に対して図示のように接続される。
【００２４】
図４は本発明の実施形態２に係るＣＡＭの回路図である。
図４においては、図３に示したＣＡＭセルが縦・横のアレイ状に配置され、横方向の１行が同じワード線に接続され１ワードを構成し、縦方向の１列が同じビット線対に接続され１ビットを構成している。
そして１ワード分の回路の接続は、図１に示した実施形態１の場合と同様である。
【００２５】
次に、図４のビット１の回路で、１ビット分の回路の接続について説明する。図３の最長一致線３３に相当する最長一致線４７１に、図３のＰＭＯＳトランジスタＰＭ３１に相当する３ワード分の同一ビットのＰＭＯＳトランジスタＰＭ４１１１〜ＰＭ４１３１の各ドレインを共通に接続し、この共通接続された最長一致線４７１と接地電位との間に、最長一致線４７１のディスチャージ用のＮＭＯＳトランジスタＮＭ４６１が接続され、前記ＮＭＯＳトランジスタＮＭ４６１のゲートに供給されるディスチャージ信号１５によってこのトランジスタＮＭ４６１のＯＮ／ＯＦＦが制御される。そしてこの最長一致線４７１は、ビット線駆動回路１３１に入力される。
ビット線駆動回路１３１には、上記最長一致線４７１のほかに、各ビット毎の、書き込み／照合データ信号と、マスク設定信号と、ビット線駆動用制御信号１６が入力される。またビット線対（図３の２１ａ，２１ｂに相当）も、ビット線駆動回路１３１に接続される。
【００２６】
図３の構成は、図２のＣＡＭセルにＰＭＯＳトランジスタＰＭ３１と最長一致線３３が付加されたものであり、図３のＣＡＭセルの書き込み及び照合動作は図２のＣＡＭセルと同様である。
【００２７】
図４により、本実施形態２のＣＡＭの動作について説明する。
まず、ビット線駆動用制御信号１６によりビット線駆動回路を制御し、ビット毎に設けられたビット線対の電位を共にＨｉｇｈにし、ＮＭＯＳトランジスタＮＭ１５１１〜ＮＭ１５１３、ＮＭ１５２１〜ＮＭ１５２３、ＮＭ１５３１〜ＮＭ１５３３を全てＯＮにした状態で、プリチャージ信号１４をＬｏｗ電位にし、ＰＭＯＳトランジスタＰＭ１１１〜ＰＭ１１３をＯＮに、ＮＭＯＳトランジスタＮＭ１１１〜ＮＭ１１３をＯＦＦにすることにより、各ワードのダイナミックＮＡＮＤ回路内のノード１２１０〜１２１３、１２２０〜１２２３、１２３０〜１２３３をＨｉｇｈ電位にするまでは、前記実施形態１の場合と同様である。
このとき、各ビット毎の最長一致線４７１，４７２，４７３にドレインが接続されるＰＭＯＳトランジスタＰＭ４１１１〜ＰＭ４１１３、ＰＭ４１２１〜ＰＭ４１２３、ＰＭ４１３１〜ＰＭ４１３３はＯＦＦとなる。
【００２８】
次に、ディスチャージ信号１５をＨｉｇｈ電位にしディスチャージ用のＮＭＯＳトランジスタＮＭ４６１〜ＮＭ４６３をＯＮにすることにより、最長一致線４７１〜４７３の電位をＬｏｗにする。
次に、ディスチャージ信号１５をＨｉｇｈ電位に戻し、ＮＭＯＳトランジスタＮＭ４６１〜ＮＭ４６３をＯＦＦにする。
次に、制御信号１６によりビット線駆動回路を制御し、各ビット毎に照合値を印加してから、プリチャージ信号１４をＨｉｇｈ電位に戻しＰＭＯＳトランジスタＰＭ１１１〜ＰＭ１１３をＯＦＦに、ＮＭＯＳトランジスタＮＭ１１１〜ＮＭ１１３をＯＮにする。
【００２９】
検索データを印加した際に、例えば
ワード１の１ビット目と２ビット目、
ワード２の１ビット目、
ワード３の２ビット目と３ビット目、
が検索データに一致し、残りのビットが不一致であれば、どのワードのデータも検索データと完全には一致しないため、インバータＮＶ１１１〜ＮＶ１１３の出力は全てＬｏｗである。
【００３０】
このとき、ダイナミックＮＡＮＤ回路内のノードの電位に着目すると、
ワード１では、トランジスタのＮＭ１５１１とＮＭ１５１２がＯＮ、ＮＭ１５１３はＯＦＦとなるので、ノードの１２１１，１２１２の電位がＬｏｗ、１２１３の電位はＨｉｇｈとなる。
ワード２では、トランジスタのＮＭ１５２１がＯＮ、ＮＭ１５２２とＮＭ１５２３はＯＦＦとなるので、ノードの１２２１の電位がＬｏｗ、１２１２と１２１３の電位はＨｉｇｈとなる。
ワード３では、トランジスタのＮＭ１５３２とＮＭ１５３３がＯＮするが、ＮＭ１５３１がＯＦＦとなるので、ノード１２３１〜１２３３の電位はＨｉｇｈのままである。
【００３１】
従って、１ビット目の最長一致線４７１の電位は、ＰＭＯＳトランジスタＰＭ４１１１とＰＭ４１２１がＯＮとなることによりＨｉｇｈになり、
２ビット目の最長一致線４７２の電位は、ＰＭＯＳトランジスタＰＭ４１１２がＯＮとなることによりＨｉｇｈになり、
３ビット目の最長一致線４７３の電位は、ＰＭＯＳトランジスタＰＭ４１１３とＰＭ４１２３とＰＭ４２３３が共にＯＦＦのままなのでＬｏｗを保つ。
すなわち、最長一致線４７１〜４７３の値により、ＭＳＢ（ビット１）側からみて最も多くのビットが連続して一致しているワード（この場合はワード１）の、一致しているビット（この場合はビット１，２）が示され、前記実施形態１における「最長一致信号」と同じ機能を有する。
【００３２】
次に、ビット線駆動回路の制御信号１６により、最長一致線４７１〜４７３の値がＬｏｗのビット（この場合はビット３）はマスクビットとし、ビット線対の双方にＨｉｇｈの電位を印加する。このとき、ビット３では、既にＯＮとなっていたトランジスタのＮＭ１５３３に加え、ＮＭ１５１３、ＮＭ１５２３がＯＮとなる。
ワード１では既にトランジスタのＮＭ１１１，ＮＭ１５１１，ＮＭ１５１２がＯＮとなっているので、ノード１２１３の電位がＬｏｗになり、インバータＮＶ１１１の出力はＨｉｇｈ、すなわち「一致」となる。
ワード２ではトランジスタＮＭ１５２２がＯＦＦで、ワード３ではトランジスタＮＭ１５３１がＯＦＦとなっているので、ノード１２２３及び１２３３の電位はＨｉｇｈのままであり、インバータＮＶ１１２及びＮＶ１１３の出力はＬｏｗ、すなわち「不一致」となる。
以上の動作により、最長一致の検出が行われる。
【００３３】
以上のように本実施形態２によれば、前記実施形態１と同様に、
最初の、最長一致信号によりマスクビットを設定せずに行なう照合動作と、
次の、最長一致信号によりマスクビットを設定して行なう照合動作と、
計２度の照合動作により最長一致の検出が可能となる。
さらに本実施形態２によれば、前記実施形態１では最長一致信号を形成するのに各ビット毎の個別配線路を必要とするスタティック（ＣＭＯＳ）ＮＡＮＤ回路またはダイナミックＮＡＮＤ回路ＮＤ１６１〜ＮＤ１６３と比較して、共通配線路である最長一致線４７１〜４７３を用いて、より小面積、かつ高速動作が可能な回路で最長一致信号を出力しているため、結果として実施形態１の場合よりも、より小面積、かつ高速動作が可能なＣＡＭが実現できる。
なお、実施形態１に対する実施形態２の優位性は、ワード数が多いＣＡＭを構成した場合ほど大きくなる。
【００３４】
前記実施形態１、２における説明では、常に２度の照合動作を行なうものとしているが、２度目の照合動作を行なうか否かを選択する手段を設けることにより、検索データに完全に一致するデータのみを検出することが必要な用途にも適用が可能となる。
【００３５】
【発明の効果】
以上のように本発明によれば、内部に格納されたｍビット×ｎワードのデータ群の中から、外部から入力されたｍビットの検索データに一致するデータを検出する連想メモリにおいて、各ワード毎の格納データと検索データとをビット毎に照合し、このビット毎の照合結果を入力するｍ個のＭＯＳトランジスタを直列接続し、この直列接続回路のうち、ＭＳＢ側から連続して一致しているビットの範囲とそれ以外の範囲とを異なる電位として、且つＬＳＢ側回路の電位を出力する各ワード毎の論理演算回路と、最初の照合動作の実行後に、同じビットを構成するｎ個の連想メモリセルから、それぞれ前記各ワード毎の論理演算回路を構成するＭＯＳトランジスタの出力側の電位を各ビット毎の論理和演算回路に入力し、ＭＳＢ側から連続して最も多数のビットが一致しているワードの一致しているビットの出力情報を得る前記各ビット毎の論理和演算回路とを設けて、完全に一致するデータが無い場合には、前記各ビット毎の論理和演算回路の出力情報により一致しているビット以外をマスクビットとして再度照合動作を行い、前記各ワード毎の論理演算回路の出力によりＭＳＢ側から連続して最も多くのビットが一致しているデータを検出することができるようにしたので、最初の各ビット毎の論理和演算回路の出力情報を得るマスクビットを設定しないで行なう照合動作と、次の各ワード毎の論理演算回路の出力情報を得るマスクビットを設定して行なう照合動作の２回の照合動作により最長一致の検出が可能となる。
【図面の簡単な説明】
【図１】本発明の実施形態１に係るＣＡＭの回路図である。
【図２】本発明の実施形態１に係る１ビット分のＣＡＭセルの回路図である。
【図３】本発明の実施形態２に係る１ビット分のＣＡＭセルの回路図である。
【図４】本発明の実施形態２に係るＣＡＭの回路図である。
【図５】本発明におけるＣＡＭの動作概要の説明図である。
【図６】本発明のワード毎の論理演算処理とビット毎の論理和演算処理の説明図である。
【符号の説明】
１４  プリチャージ用制御信号
１５  ディスチャージ信号
１６  ビット線駆動用制御信号
２０  ワード線
２１ａ，２１ｂ  ビット線
２２  マッチ線
３３  最長一致線
【図１】
0004298104.tif 000002
【図２】
0004298104.tif 000003
【図３】
0004298104.tif 000004
【図４】
0004298104.tif 000005
【図５】
0004298104.tif 000006
【図６】
0004298104.tif 000007