(57)【要約】【解決手段】範囲マッチングセル（ＲＭＣ）は、ビット線ＢＬ、ワード線ＷＬ、マッチ線ＭＬ、メモリセル１００、前記メモリセルに接続されている第１比較部、前記第１比較器、グランド電圧及び既に決定されている電圧に接続されている第２比較部を備える。前記比較器は演算子データに応答して比較動作を行う。０、１、及びＸ（ｄｏｎ’ｔ ｃａｒｅ）ビットを用いる通常のＴＣＡＭに比べて、ＲＭＣを用いるＣＡＭは演算子データ０及び１を予め格納しておくことにより、更に少ないメモリで比較動作を行うことができる。従って、メモリを効率的に利用できる。メモリを効率的に用いることができるという効果がある。
2009525561.tif 000002
【特許請求の範囲】
【請求項１】
ビット線と反転ビット線の対と、
ワード線と、
前記ワード線及び前記ビット線に接続され、前記ワード線が活性化されると、前記ビット線を介して伝送される前記データを格納するメモリセルと、
マッチ線と、
サーチ線と反転サーチ線の対と、
前記マッチ線に直列に接続されている第１トランジスタと、
前記メモリセル、前記マッチ線及び前記サーチ線に接続され、前記メモリセルに格納された前記データと前記サーチ線を介して伝送されるサーチデータに応答して前記第１トランジスタをオン（ＯＮ）又はオフ（ＯＦＦ）させる第１比較部と、前記第１トランジスタがオフ（ＯＦＦ）されると、前記サーチデータ及び格納された演算子データに基づいて前記マッチ線をグランド電圧又は既に決定されている電圧に接続させる第２比較部と
を備え、前記演算子データは０及び１の論理値を有することを特徴とする範囲マッチングセル。
【請求項２】
前記メモリセルは、
前記データを格納する格納部と、
前記ビット線を前記格納部に接続して前記ビット線を介して受信される前記データを前記格納部に提供する連結手段と
を備えることを特徴とする請求項１に記載の範囲マッチングセル。
【請求項３】
前記格納部は、交差結合されたインバータを備えることを特徴とする請求項２に記載の範囲マッチングセル。
【請求項４】
前記連結手段は、前記ワード線に接続される第１及び第２パスゲートであることを特徴とする請求項２に記載の範囲マッチングセル。
【請求項５】
前記第１比較部は、
前記格納されたデータと前記サーチされたデータとが互いに一致すれば、前記第１トランジスタをオン（ＯＮ）させ、前記格納されたデータと前記サーチされたデータとが互いに一致しなければ、前記第１トランジスタをオフ（ＯＦＦ）させることを特徴とする請求項１に記載の範囲マッチングセル。
【請求項６】
前記第２比較部は、
前記サーチされたデータと前記演算子データとが互いに一致すれば、前記マッチ線をグランド電圧に接続させ、前記サーチされたデータと前記演算子データとが互いに一致しなければ、前記マッチ線を既に決定されている電圧に接続させることを特徴とする請求項１に記載の範囲マッチングセル。
【請求項７】
前記第１比較部は、前記サーチ線を前記第１トランジスタに接続させる第２トランジスタを備え、前記第２トランジスタは、前記格納部に接続されるゲートを備えることを特徴とする請求項２に記載の範囲マッチングセル。
【請求項８】
前記第２比較部は、
前記マッチ線をグランド電圧に直列に接続する第３、第４、及び第５スイッチング素子を備え、
前記第３トランジスタは前記マッチ線と前記第４スイッチング素子を接続し、前記第１比較部に接続されるゲートを備え、
前記第４トランジスタは前記第３トランジスタと前記第５トランジスタを接続し、前記サーチ線に接続されるゲートを備え、
前記第５トランジスタは前記第４トランジスタとグランド電圧を接続し、前記演算子データを受信するゲートを備えることを特徴とする請求項１に記載の範囲マッチングセル。
【請求項９】
前記第２比較部は、
前記既に決定されている電圧とマッチ線を直列に接続する第６及び第７トランジスタと、
第８トランジスタと、
第３パスゲートと、
第４パスゲートと
を有し、
前記第６トランジスタは前記第１比較部に接続されるゲートを備え、
前記第７トランジスタは第１及び第２演算子データのＯＲ演算された結果が入力されるゲートを備え、
前記第８トランジスタは前記マッチ線と、前記第３及び第４パスゲートと接続され、前記第１比較部の反転出力が入力されるゲートを備え、
前記第３パスゲートは前記反転サーチ線と前記第８トランジスタと接続され、前記第１演算子データが入力されるゲートを備え、
前記第４パスゲートは前記サーチ線と前記第８トランジスタと接続され、前記第２演算子データが入力されるゲートを備えることを特徴とする請求項１に記載の範囲マッチングセル。
【請求項１０】
マッチ線と、
ワード線と、
カラム方向に配列されているＮ個のビット線及び反転ビット線の対と、
Ｎ個のサーチ線と反転サーチ線の対と、
前記マッチ線、前記ワード線及びＮ個のビット線の対のそれぞれに接続されるＮ個の範囲マッチングセルと
を有し、
それぞれの前記範囲マッチングセルは、
前記ワード線と前記ビット線の対に接続されて前記ワード線が活性化されると、前記ビット線の対を介して伝送される前記データを格納するメモリセルと、
前記マッチ線に直列に接続されている第１トランジスタと、
前記メモリセル、前記マッチ線及び前記サーチ線の対に接続され、前記メモリセルに格納された前記データと前記サーチ線を介して伝送されるサーチデータに応答して前記第１トランジスタをオン（ＯＮ）又はオフ（ＯＦＦ）制御する第１比較部と、
前記第１トランジスタがオフ（ＯＦＦ）されると、前記サーチデータ及び格納された演算子データに基づいて前記マッチ線をグランド電圧又は既に決定されている電圧に接続させる第２比較部と
を備え、前記演算子データは０及び１の論理値を有することを特徴とするＣＡＭ。
【請求項１１】
前記マッチ線の一端はグランド電圧に接続され、前記マッチ線の他端はマッチ線に接続されることを特徴とする請求項１０に記載のＣＡＭ。
【請求項１２】
前記メモリセルは、
前記データを格納する格納部と、
前記ビット線を前記格納部に接続して前記ビット線を介して入力される前記格納されたデータを前記格納部に提供する連結手段と
を備えることを特徴とする請求項１０に記載のＣＡＭ。
【請求項１３】
前記格納部は、交差結合されたインバータを備えることを特徴とする請求項１２に記載のＣＡＭ。
【請求項１４】
前記連結手段は第１及び第２パスゲートを備え、前記第１及び第２パスゲートは前記ワード線に接続されることを特徴とする請求項１２に記載のＣＡＭ。
【請求項１５】
前記第１比較部は、
前記格納されたデータと前記サーチデータとが互いに一致すれば、前記第１トランジスタをターンオン（ＯＮ）させ、互いに一致しなければ、前記第１トランジスタをターンオフ（ＯＦＦ）させることを特徴とする請求項１０に記載のＣＡＭ。
【請求項１６】
前記第２比較部は、
前記サーチデータと前記演算子データとが互いに一致すれば、前記マッチ線をグランド電圧に接続させ、互いに一致しなければ、前記マッチ線を既に決定されている電圧に接続させることを特徴とする請求項１０に記載のＣＡＭ。
【請求項１７】
前記第１比較部は、
前記サーチ線と前記トランジスタを接続する第２トランジスタを備え、前記第２トランジスタは前記格納部に接続されるゲートを備えることを特徴とする請求項１２に記載のＣＡＭ。
【請求項１８】
前記第２比較部は、
前記マッチ線とグランド電圧を直列に接続する第３、第４、及び第５トランジスタを有し、前記第３トランジスタは前記マッチ線と前記第４トランジスタを接続し、前記第１比較部に接続されるゲートを備え、
前記第４トランジスタは前記第３トランジスタと前記第５トランジスタを接続し、前記サーチ線に接続されるゲートを備え、
前記第５トランジスタは前記第４トランジスタとグランド電圧を接続し、前記演算子データが入力されるゲートを備えることを特徴とする請求項１０に記載のＣＡＭ。
【請求項１９】
前記第２比較部は、
前記既に決定されている電圧とマッチ線を直列に接続する第６素子及び第７トランジスタと、
第８トランジスタと、
第３パスゲートと、
第４パスゲートと
を有し、
前記第６トランジスタは前記第１比較部に接続されるゲートを備え、
前記第７トランジスタは前記第１演算子データと前記第２演算子データのＯＲ演算された結果が入力されるゲートを備え、
前記第８トランジスタは前記マッチ線と、前記第３及び第４パスゲートと接続され、前記第１比較部の反転出力が入力されるゲートを備え、
前記第３パスゲートは前記反転サーチ線と前記第８トランジスタと接続され、前記第１演算子データが入力されるゲートを備え、
前記第４パスゲートは前記サーチ線及び前記第８トランジスタに接続され、前記第２演算子データが入力されるゲートを備えることを特徴とする請求項１０に記載のＣＡＭ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連想メモリ（ＣＡＭ：Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）に関し、更に詳しくは、範囲マッチングセル（ｒａｎｇｅ−ｍａｔｃｈｉｎｇ ｃｅｌｌ）（ＲＭＣ）を用いた範囲検索が可能なＣＡＭに関する。
【背景技術】
【０００２】
通常、ラム（ＲＡＭ）やロム（ＲＯＭ)はアドレスを用いて内部のメモリセルアレイの特定の位置を指示し、指示されたアドレスに対応する格納データを出力する。それに対し、連想メモリ（ＣＡＭ）は外部から受信したデータが内部に格納されたデータと一致（マッチ）するか否かを判断するために比較し、マッチされたアドレスを出力する。
【０００３】
ＣＡＭのそれぞれのメモリセルは、比較ロジックを備える。ＣＡＭに入力されるデータは、ＣＡＭのあらゆるセルに格納されているデータと比較され、マッチされたアドレスを出力する。ＣＡＭは、パターン、リスト、及びイメージデータなどを迅速に検索する必要がある応用分野に広く用いられる。このようなＣＡＭは、バイナリＣＡＭ（ｂｉｎａｒｙ ＣＡＭ）とターナリＣＡＭ（ＴＣＡＭ：Ｔｅｒｎａｒｙ ＣＡＭ）とに区分される。
【０００４】
バイナリＣＡＭは、１と０の２つの論理状態のうちの１つを格納するためのラム（ＲＡＭ）セルを備える。バイナリＣＡＭは、外部から提供されるデータ（以下、「サーチデータ」という）をラム（ＲＡＭ）セルに格納されたデータ（以下、「格納されたデータ」という）と比較し、サーチデータが格納されたいずれかのデータと一致すれば、互いに一致するマッチ線を一定の論理状態に設定する比較回路を備える。バイナリＣＡＭの例は、下記の特許文献1及び特許文献２に開示されている。
【０００５】
一方、ＴＣＡＭは３種類の論理状態、即ち、「１」、「０」、「Ｘ（ｄｏｎ'ｔ ｃａｒｅ）」状態を格納することができる。ＴＣＡＭは、高速のルータにおいてパケット分類を行うための最も効率的な方法の１つである。ＴＣＡＭの例は、特許文献３に開示されている。
【０００６】
従来技術で公知の通り、ＯＳＩ（Ｏｐｅｎ Ｓｙｓｔｅｍｓ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ）７階層（ｌａｙｅｒ)が提案されているが、Ｌａｙｅｒ ３以上をサポートするためのルータでは入力値と、格納された値とが同一であるかを比較すること以外にも、２つの値の大きさを比較する機能が必要である。即ち、イーサネットパケット（Ｅｔｈｅｒｎｅｔ Ｐａｃｋｅｔ）において、サービス（ＴｏＳ）フィールド（ｌａｙｅｒ ３）及び伝送制御プロトコル（ＴＣＰ）ポートフィールド（ｌａｙｅｒ ４）はパケットを分類するために、大きさが比較されなければならない。このために、従来のＴＣＡＭセルは「１」、「０」、「Ｘ（ｄｏｎ’ｔ ｃａｒｅ）」を予め格納して入力値と、格納された値とが同一であるかを比較する役割を果たす。
【０００７】
しかしながら、ＴＣＡＭのこのようなオペレーションはパケットの分類においてＩＰを区分する際には効率的であるが、大きさを比較しなければならないポートナンバーフィールドに対しては脆弱な構造を有する。例えば、１６ビットＴＣＰポートフィールドに対して１０２４より大きい範囲を検索する場合、ＴＣＡＭを用いれば、メモリには以下の６通りの場合が格納されなければならない。
【０００８】
００００_０１ＸＸ_ＸＸＸＸ_ＸＸＸＸ、
００００_１ＸＸＸ_ＸＸＸＸ_ＸＸＸＸ、
０００１_ＸＸＸＸ_ＸＸＸＸ_ＸＸＸＸ、
００１Ｘ_ＸＸＸＸ_ＸＸＸＸ_ＸＸＸＸ、
０１ＸＸ_ＸＸＸＸ_ＸＸＸＸ_ＸＸＸＸ、
１ＸＸＸ_ＸＸＸＸ_ＸＸＸＸ_ＸＸＸＸ
【０００９】
また、最悪の場合、「ソースポートナンバー（Ｓｏｕｒｃｅ ｐｏｒｔ ｎｕｍｂｅｒ）が１より大きく、デスティネーションポートナンバー（ｄｅｓｔｉｎａｔｉｏｎ ｐｏｒｔ ｎｕｍｂｅｒ）が１より大きい」という範囲を検索する場合には９００（３０×３０）個の格納容量が必要になる。そのため、ＴＣＡＭの格納容量を効果的に使用できなくなり、メモリ効率が低下してしまう。また、検索範囲をアップデートする場合にも非常に非効率的であるという問題がある。
【特許文献１】米国特許４,６４６,２７１号公報
【特許文献２】米国特許５,４９０,１０２号公報
【特許文献３】米国特許５,３１９,５９０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は上記事情に鑑みてなされたものであって、その目的は、大きさの比較を通じた範囲検索を行う場合に大きさ比較演算子を提供することで、メモリをより効率的に使用できる範囲マッチングセル及びこれを用いたＣＡＭを提供することにある。
【課題を解決するための手段】
【００１１】
前記目的を達成するために、本発明の一態様によれば、ビット線と、ワード線と、メモリセルと、マッチ線と、サーチ線と、前記メモリセルとに接続させる第１比較部と、前記マッチ線と、前記サーチ線と、グランド電圧と既に決定されている電圧とに接続させる第２比較部とを備えることを特徴とする範囲マッチングセルを提供する。
【００１２】
好ましくは、第１比較部は前記マッチ線に直列に接続されている第１トランジスタと、前記メモリセルと、前記サーチ線と第１トランジスタに接続されている第２トランジスタとを含む。第１トランジスタは第２トランジスタに反応してオン（ＯＮ）又はオフ（ＯＦＦ）となり、第２トランジスタは前記メモリセルに格納されたサーチ線を通じて伝送されたサーチデータに反応して（ＯＮ）又はオフ（ＯＦＦ）となる。
【００１３】
好ましくは、上記第１トランジスタがオフ（ＯＦＦ）になると、第２比較部は前記サーチデータ及び演算子データに反応してグランド電圧又は既に決定されている電圧に前記マッチラインを接続させる。前記演算子データは０または１の論理値を有する第１及び第２演算子データを含む。
【００１４】
好ましくは、上記第１演算子データ（ＯＰ１）と上記第２演算子データ（ＯＰ２）は次のように決定される。
（ａ）サーチデータのサーチ範囲が格納データのサーチ範囲より大きいか同じ場合は、
（ＯＰ１、ＯＰ２）＝（１、０）
（ｂ）サーチデータのサーチ範囲が格納データのサーチ範囲より小さいか同じ場合は、
（ＯＰ１、ＯＰ２）＝（０、１）
（Ｃ）サーチデータのサーチ範囲が格納データのサーチ範囲と同じ場合は、
（ＯＰ１、ＯＰ２）＝（０、０）。
【００１５】
また、本発明の他の態様によれば、マッチ線と、ワード線と、カラム方向に配列されているＮ個のビット線及び反転ビット線の対と、Ｎ個のサーチ線と反転サーチ線の対と、前記マッチ線、前記ワード線及びＮ個のビット線の対のそれぞれに接続されるＮ個の範囲マッチングセルとを有し、それぞれの前記範囲マッチングセルは、前記ワード線と前記ビット線の対に接続されて前記ワード線が活性化されると、前記ビット線の対を介して伝送される前記データを格納するメモリセルと、前記マッチ線に直列に接続されている第１トランジスタと、前記メモリセル、前記マッチ線及び前記サーチ線の対に接続され、前記メモリセルに格納された前記データと前記サーチ線を介して伝送されるサーチデータに応答して前記第１トランジスタをオン（ＯＮ）又はオフ（ＯＦＦ）制御する第１比較部と、前記第１トランジスタがオフ（ＯＦＦ）されると、前記サーチデータ及び格納された演算子データに基づいて前記マッチ線をグランド電圧又は既に決定されている電圧に接続させる第２比較部とを備え、前記演算子データは０及び１の論理値を有するＣＡＭを提供する。
【発明の効果】
【００１６】
本発明に係るＣＡＭによれば、演算子データを予め格納しておくことにより、０、１及びＸ（ｄｏｎ’ｔ ｃａｒｅ）ビットを用いて範囲検索を行う従来のＴＣＡＭに比べて、さらに少ないメモリで比較動作を行えるという効果を奏する。それにより、メモリの利用効率が２.５倍以上増加することができ、更にアップデートもより効率的に行われ得る。
【発明を実施するための最良の形態】
【００１７】
以下、本発明によって範囲マッチングセル（ＲＭＣ）及びこれを用いたＣＡＭについて添付の図面を参照して説明する。全図にわたり、同一又は類似の参照符号は同一又は類似の構成要素を意味する。
【００１８】
図１を参照すれば、本発明の好適な実施形態による範囲マッチングセルの回路図が示されている。図１に示すように、本発明の範囲マッチングセルは、ビット線ＢＬと反転ビット線／ＢＬの対、ワード線ＷＬ、メモリセル１００、マッチ線ＭＬ、サーチ線ＳＬと反転サーチ線／ＳＬの対、第１比較部１１０、及び第２比較部１２０を備える。
【００１９】
メモリセル１００は、パスゲート１０６、１０７と、データ及びその反転データを格納する格納部１０２と、連結手段１０６、１０７とを備える。
【００２０】
パスゲート１０６は、ビット線ＢＬと格納部１０２との間に提供されている。一方、パスゲート１０７は反転ビット線ＢＬと格納部１０２との間に提供されている。パスゲート１０６、１０７は、ビット線の対ＢＬ、／ＢＬを介して入力されるデータを格納部１０２に伝達する。
【００２１】
より詳細に説明すれば、格納部１０２は交差して接続されているインバータ１０３、１０４を備える。パスゲート１０６、１０７は、ＭＯＳ ＦＥＴを有してもよい。
【００２２】
第１比較部１１０は、メモリセル１００、サーチ線の対ＳＬ、／ＳＬ及びマッチ線ＭＬに接続される。第１比較部１１０は、第１トランジスタＴ１と、２つの第２トランジスタＴ２とを備える。第１トランジスタＴ１はマッチ線ＭＬに直列に接続される。そして、第２トランジスタＴ２は第１トランジスタＴ１と格納部１０２との間に配置される。また、第２トランジスタＴ２はサーチ線ＳＬ、／ＳＬにそれぞれ接続され、格納部１０２に接続されているゲートを備える。一方、格納されたデータＳＲＤとサーチデータＳＤとが互いに一致すれば、第１トランジスタＴ１がターンオン（ＯＮ）され、互いに一致しなければ、第１トランジスタＴ１がターンオフ（ＯＦＦ）される。第１及び第２トランジスタＴ１及びＴ２は、いずれもＭＯＳ ＦＥＴであってもよい。第２比較部１２０は、第１トランジスタＴ１がオフ（ＯＦＦ）されると、サーチ線ＳＬを介して伝送されるサーチデータと格納された演算子データＯＰ１、ＯＰ２に応答してマッチ線ＭＬを基準電圧（グランド電圧）に接続させる。更に詳しく説明すれば、第２比較部１２０はサーチデータと演算子データＯＰ１、ＯＰ２とが互いに一致すれば、マッチ線ＭＬを基準電圧に接続させ、互いに一致しなければ、マッチ線を既に設定されている電圧に接続させる。
【００２３】
第２比較部１２０は、第３トランジスタＴ３、２つの第４トランジスタＴ４、２つの第５トランジスタＴ５を有する。トランジスタＴ３、Ｔ４、Ｔ５は、マッチ線を基準電圧に直列に接続させる。また、第３トランジスタＴ３はマッチ線ＭＬと第４トランジスタＴ４を接続し、第１比較部１１０に接続されるゲートを備える。第４トランジスタＴ４は、第３トランジスタＴ３と第５トランジスタＴ５を接続し、サーチ線ＳＬに接続されるゲートを備える。第５トランジスタＴ５は、第４トランジスタＴ４を基準電圧に接続し、演算子データＯＰ１、ＯＰ２に接続されるゲートを備える。
【００２４】
図２を参照すれば、本発明の他の実施形態による範囲マッチングセルの回路図が示されている。本実施形態は、図１でのように、ＮＭＯＳトランジスタとＰＭＯＳトランジスタで実現したダイナミック型の範囲マッチングセルをＮＭＯＳトランジスタのみで実現したものである。ＮＭＯＳトランジスタがＰＭＯＳトランジスタに比べて小さな面積を占めるため、回路を更に集積化、かつ小型化することが可能である。
【００２５】
図２において、参照符号２００〜２２０の機能は図１における参照符号１００〜１２０の機能と実質的に同一である。ただし、図２の第３トランジスタＴ３がＮＭＯＳ型であり、第４及び第５トランジスタＴ４、Ｔ５の下に位置するのに対し、図１の第３トランジスタＴ３はＰＭＯＳ型であり、第４及び第５トランジスタＴ４、Ｔ５の上に位置し、図２の第３トランジスタＴ３は基準電圧に接続され、第４トランジスタＴ４が演算子データＯＰ１、ＯＰ２に接続されるという点で異なる。従って、これについての詳細な説明は簡略化を図るために、省略する。
【００２６】
図３は、本発明のもう１つの実施形態による範囲マッチングセルの回路図を示す。図３において、参照符号３００〜３２０の機能は図２の参照符号２００〜２２０の機能とそれぞれ実質的に同一である。しかしながら、演算子データＯＰ１、ＯＰ２は、Ｎ１及びＮ２で格納されたデータに応答して第１比較器３１０に印加される。従って、図２の回路図と比較して少なくとも１つのトランジスタを低減することが可能になる。
【００２７】
図４は、本発明の更に別の実施形態による範囲マッチングセルの回路図である。図４において、範囲マッチングセルは、ビット線ＢＬと反転ビット線／ＢＬの対、ワード線ＷＬ、メモリセル４００、マッチ線ＭＬ、サーチ線ＳＬと反転サーチ線／ＳＬの対ＳＬ、／ＳＬ、第１比較部４１０、第２比較部４２０を備える。
【００２８】
メモリセル４００は、１対のパスゲート４０６、４０７と、データ及びその反転データを格納する格納部３０４を備える。
【００２９】
パスゲート４０６はビット線ＢＬに接続され、パスゲート４０７はビット線／ＢＬに接続される。また、パスゲート４０６、４０７は格納部４０２に接続され、ビット線の対ＢＬ及び／ＢＬを介して入力されるデータを格納部４０２に伝達する。
【００３０】
更に詳しく説明すれば、格納部４０２は交差接続されたインバータ４０３、４０４を備え、パスゲート４０６を介してビット線ＢＬに接続される。そして、パスゲート４０７は格納部４０２を反転ビット線／ＢＬに接続させる。これらのパスゲートはＭＯＳ ＦＥＴを有する。
【００３１】
第１比較部４１０は、第１トランジスタＴ１と、２つの第２トランジスタＴ２を有する。また、第１トランジスタＴ１は、メモリセル４００、サーチ線の対ＳＬ、／ＳＬ及びマッチ線ＭＬに接続される。
【００３２】
一方、格納されたデータとサーチデータとが互いに一致すれば、第１トランジスタＴ１がターンオン（ＯＮ）され、互いに一致しなければ、第１トランジスタＴ１がターンオフ（ＯＦＦ）される。更に、第１トランジスタＴ１はマッチ線ＭＬに直列に接続される。それぞれの第２トランジスタＴ２はサーチ線の対ＳＬ、／ＳＬをそれぞれ第１トランジスタＴ１に接続させ、格納部３０２に接続されるゲートを備える。第２比較部４２０は、第６トランジスタＴ６、第７トランジスタＴ７、第８トランジスタＴ８、パスゲート４０８及びパスゲート４０９を有する。第２比較部４２０は、マッチ線ＭＬを直列に既に決定されている電圧に接続させる。
【００３３】
第６トランジスタＴ６は、それのゲートを介して第１比較部４１０に接続されて第１比較部４１０から出力された結果を受信する。
【００３４】
第７トランジスタＴ７は、第６トランジスタＴ６とマッチ線ＭＬとの間に配置されて第１演算子データＯＰ１と第２演算子データＯＰ２のＯＲ演算された結果を受信する。
【００３５】
第８トランジスタＴ８は、マッチ線ＭＬとパスゲート４０８、４０９に接続される。第８トランジスタＴ８は、それのゲートを介して第１比較部４１０の反転出力に接続される。
【００３６】
パスゲート４０８は、サーチ線ＢＬ及び第８トランジスタＴ８に接続される。パスゲート４０８のゲートには第２演算子データＯＰ２が接続される。パスゲート４０９は、反転サーチ線／ＳＬ及び第８トランジスタＴ８と接続される。パスゲート４０９のゲートには第１演算子データＯＰ１が接続される。
【００３７】
一方、第１トランジスタＴ１がターンオフされると、第２比較部４２０はサーチ線ＳＬを介して伝達されるサーチデータ及び格納された演算子データＯＰ１、ＯＰ２に応答してマッチ線ＭＬをグランド電圧又は既に設定されている電圧に接続させる。サーチデータと演算子データＯＰ１とが互いに一致すれば、第２比較部４２０はマッチ線ＭＬをグランド電圧に接続させ、互いに一致しなければ、マッチ線ＭＬを既に決定されている電圧に接続させる。
【００３８】
図１〜図３に示す範囲マッチングセルは、ダイナミック型であり、図４に示す範囲マッチングセルは、スタティック型である。ダイナミック型の範囲マッチングセルは、スタティック型の範囲マッチングセルとは異なり、マッチ線がプリチャージされなければならないが、実現したトランジスタの数はスタティック型の範囲マッチセルに比べて更に少ない。即ち、図１及び図２から分かるように、セルの大きさはスタティック型より小さいが、プリチャージによる消費電力がスタティック型より大きい。これと反対に、図４から分かるように、セルの大きさはダイナミック型より大きいが、プリチャージが不要であるため、消費電力を低減できる。
【００３９】
図１〜図４に示すように、参照符号ＯＰ１、ＯＰ２は大きさ演算子を示す。本発明の実施形態において適用される各演算子の論理値は、以下の通りである。即ち、演算子が「大きいか同じである（ＧＥ：Ｇｒｅａｔｅｒ ｔｈａｎ ｏｒ Ｅｑｕａｌ）」の場合は（ＯＰ１、ＯＰ２）＝（１、０）の論理値を有する。演算子が「小さいか同じである（ＬＥ：Ｌｅｓｓ ｔｈａｎ ０ｒ Ｅｑｕａｌ）」場合には（ＯＰ１、ＯＰ２）＝（０、１）の論理値を有する。そして、演算子が「同じである（ＥＱ：Ｅｑｕａｌ）」の場合には（ＯＰ１、ＯＰ２）＝（０、０）の論理値を有する。
【００４０】
以下、図１〜図４を参照して本発明の実施形態による範囲マッチングセルの動作を詳細に説明する。
【００４１】
図５において、ＯＰ１及びＯＰ２はそれぞれ演算子データ１及び２に該当し、ＳＲＤ（Ｓｔｏｒｅｄ ｒｕｌｅ ｄａｔａ）は格納部に格納されたデータを意味し、ＳＤ（Ｓｅａｒｃｈｅｄ ｄａｔａ）はサーチ線ＳＬから伝送されたデータを意味する。
【００４２】
図１に示すように、まず、メモリセル１００に格納されるデータ及びその反転データがビット線の対ＢＬ、／ＢＬを介して伝送される。ワード線ＷＬがハイレべルに活性化されると、パスゲート１０６、１０７がターンオンされる。
【００４３】
前述したように、パスゲート１０６、１０７はワード線ＷＬにゲートが接続されるＮＭＯＳトランジスタである。パスゲート１０６、１０７がターンオンされると、ビット線の対ＢＬ、／ＢＬを介して伝送されたデータ及び反転データが交差接続されたインバータ１０３、１０４から構成された格納部１０２に格納され、ワード線ＷＬが非活性化される。
【００４４】
その後、マッチ線ＭＬがハイレべルにプリチャージされた状態でサーチデータＳＤ及びその反転サーチデータ／ＳＤがそれぞれサーチ線の対ＳＬ、／ＳＬを介して伝送される。
【００４５】
図５に示すように、サーチデータＳＤの検索範囲が格納されたデータＳＲＤの探索範囲より大きいと仮定する。この場合、（ＯＰ１、ＯＰ２）は「大きいか同じである（ＧＥ）」、ＷＭＲ、（１、０）である。（ＳＤ、ＳＲＤ）は（１、１）となる。
【００４６】
このとき、格納部１０２のノード１Ｎ１には論理１値が格納され、格納部１０２のノード２Ｎ２には論理０値が格納される。そして、ノード１Ｎ１で論理１値が第２トランジスタＴ２のうちの左側トランジスタのゲートに入力され、サーチ線ＳＬから伝送されたデータが１であるので、第２トランジスタＴ２のうちの左側トランジスタがターンオンされる。その結果、第１トランジスタＴ１はターンオンされる。この場合、第２比較部１２０の動作と関係なく、マッチ線ＭＬはＰＡＳＳ状態となる。
【００４７】
一方、（ＯＰ１、ＯＰ２）が（１、０）であり、（ＳＤ、ＳＲＤ）は（１、０）であると仮定する。
【００４８】
このとき、ノードＮ１には論理０値が格納され、ノードＮ２には論理１値が格納される。そして、ノードＮ２の論理１値が第２トランジスタＴ２のうちの右側トランジスタのゲートに入力され、反転サーチ線／ＳＬから論理０値が伝送されるので、第２トランジスタＴ２のうちの右側トランジスタがターンオフされる。その結果、第１トランジスタＴ１はターンオフされる。
【００４９】
この場合、第２比較部１２０の第３トランジスタＴ３がターンオンされる。そして、サーチデータＳＤが論理１であり、（ＯＰ１、ＯＰ２）の値が（１、０）であるので、第４及び第５トランジスタＴ４、Ｔ５がターンオンされる。従って、トランジスタＴ３、Ｔ４、Ｔ５がいずれもターンオンされるので、マッチ線ＭＬはこれらを介してグランド電圧に接続される。ここで、グランド電圧は第５トランジスタＴ５に接続される。その結果、マッチ線ＭＬはプルダウンＰＤ状態となる。
【００５０】
また、図５に提示された他の条件に対してもマッチ線ＭＬの状態が同様の方法により導き出され得る。また、図１を基準に範囲マッチングセルの動作を説明したが、図２及び図４の場合にも同一の結果を導き出すことができる。
【００５１】
以下、図５を参照して図２の範囲マッチングセルの動作を説明する。
【００５２】
図５に示す表から明らかなように、（ＯＰ１、ＯＰ２）の値は（１、０）であり、（ＳＤ、ＳＲＤ）の値は（１、１）である。
【００５３】
このとき、ノードＮ１には論理１値が格納され、ノードＮ２には論理０値が格納される。そして、ノードＮ１及びＮ２の論理値に応答して、トランジスタＴ２−１はターンオンされるのに対し、トランジスタＴ２−２はターンオフされる。従って、ノードＮ３はサーチ線ＳＬの論理１値によりハイ状態となり、トランジスタＴ１はターンオンされる。それに対し、トランジスタＴ４−１はノードＮ１の値と演算子データＯＰ２によってターンオフされて、トランジスタＴ６がターンオフされる。その結果、マッチ線ＭＬはＰＡＳＳ状態となる。
【００５４】
そして、（ＯＰ１、ＯＰ２）の値が（１、０）であり、（ＳＤ、ＳＲＤ）の値が（１、０）である場合には論理１値がノードＮ１に格納され、ノードＮ２には論理０値が格納される。サーチ線の値とノードＮ１、Ｎ２の値によって、トランジスタＴ２−１、Ｔ２−２はターンオフされ、トランジスタＴ１はターンオフされる。しかしながら、トランジスタＴ４−２はノードＮ２の値と演算子データＯＰ１の値によってターンオンされて、トランジスタＴ６はターンオンされる。そして、トランジスタＴ２−３はノードＮ２の値とサーチ線ＳＬの値によってターンオンされ、トランジスタＴ５はターンオンされる。その結果、マッチ線ＭＬはプルダウンＰＤ状態となる。
【００５５】
図６は、４−ビットで実現した範囲マッチングセルを用いたＣＡＭの一例を示す。ＣＡＭにおいて、インバータＩは最上位のビットＭＳＢに接続され、グランド電圧Ｇは最下位のビットＬＳＢセルに接続される。このような範囲マッチングセルを用いたＣＡＭの動作について図６〜図９を参照して詳細に説明する。
【００５６】
サーチデータＳＤの探索範囲が格納されたデータＳＲＤの探索範囲より大きいと仮定する。
【００５７】
（ＯＰ１、ＯＰ２）の値が「大きいか同じ（ＧＥ）」である。即ち（１、０）であり、サーチデータＳＤの値は（１、１、０、０）であり、格納されたデータＳＲＤの値は（１、０、１、０）である。図７は、上記条件下でのＣＡＭの動作を示す図である。なお、図７〜図９は、ＳＤ及びＳＲＤの値が左側から順に羅列されたことを示す。
【００５８】
ＭＳＢの場合、即ち、最初のビット（図６及び図７参照）の場合、サーチデータＳＤと格納されたデータＳＲＤが同一の論理１値であるので、マッチ線ＭＬはＰＡＳＳ状態となる（図５参照）。一方、２番目のビットの場合、サーチデータＳＤは論理１であり、格納されたデータＳＲＤは論理０であるので、マッチ線ＭＬはプルアップＰＵ状態となる（図５参照）。
【００５９】
その結果、ＭＳＢに接続されているインバータＩがプルダウンされたマッチ線ＭＬを介して２番目のビットセルのグランド電圧に接続されるので、ＣＡＭは論理ハイ「Ｈ（マッチ）」を出力する。
【００６０】
続いて、サーチデータＳＤの探索範囲が格納されたデータＳＲＤの探索範囲より小さいと仮定する。
【００６１】
（ＯＰ１、ＯＰ２）の値は‘少ないか同じ（ＬＥ）’である。即ち、（１、０、１、０）であり、サーチデータＳＤの値は（１、１、０、０）であり、格納されたデータＳＲＤの値は（１、０、１、０）である。図８は、上記条件下でのＣＡＭの動作を示す図である。
【００６２】
図８に示すＭＳＢの場合、サーチデータＳＤと格納されたデータＳＲＤが論理１値で同一であるので、マッチ線ＭＬはＰＡＳＳ状態となる（図５参照）。一方、２番目のビットの場合、サーチデータＳＤの値が論理１であり、格納されたデータＳＲＤの値が論理０であるので、マッチ線ＭＬはプルアップＰＵ状態となる（図５参照）。
【００６３】
プルアップＰＵ状態で、マッチ線ＭＬは初期のプリチャージされた状態であるので、プリチャージされたマッチ線ＭＬがインバータＩに接続されてＣＡＭの出力は論理ロー「Ｌ（ミスマッチ）」値となる。また、サーチデータＳＤの探索範囲が格納されたデータＳＲＤの探索範囲と同一であると仮定する。（ＯＰ１、ＯＰ２）の値は「同じ（ＥＱ）」である。即ち、（０、０）であり、サーチデータＳＤの値は（１、１、０、０）であり、格納されたデータＳＲＤの値は（１、０、１、０）である。図９は、上記条件下でのＣＡＭの動作を示す。
【００６４】
図９に示すように、ＭＳＢの場合、サーチデータＳＤと格納されたデータＳＲＤの値が同一の論理１値であるので、マッチ線ＭＬはＰＡＳＳ状態となる（図５参照）。一方、２番目のビットの場合、サーチデータＳＤが論理１であり、格納されたデータＳＲＤが論理０であるので、マッチ線ＭＬはプルアップＰＵ状態となる（図５参照）。
【００６５】
ＰＵ状態で、マッチ線ＭＬは初期にプリチャージされる。従って、プリチャージされたマッチ線ＭＬはインバータＩに接続され、ＣＡＭは論理「Ｌ（ミスマッチ）」を出力する。
【００６６】
前述したように、従来のＴＣＡＭにおいて、０、１及びＸ（ｄｏｎ’ｔ ｃａｒｅ）ビットを用いて多くのメモリを使用するのとは異なり、本発明のＣＡＭは、演算子データを事前に格納しておくことにより、少ないメモリを用いて比較演算を処理するため、メモリの利用効率を２.５倍以上も増大させることができることに加え、アップデート動作を更に効率よく行うことができる。
【００６７】
以上、本発明の好ましい実施形態を説明したが、本発明はかかる実施形態に限定されるものではなく、本発明に係る技術的思想の範囲から逸脱しない範囲内で様々な変更が可能であり、それらも本発明の技術的範囲に属する。
【００６８】
本発明の前述した目的並びにその他の目的と特徴については、添付図面及び好適な実施形態の説明から明らかになるであろう。
【図面の簡単な説明】
【００６９】
【図１】本発明の好適な実施形態による範囲マッチングセルの回路図である。
【図２】本発明の他の実施形態による範囲マッチングセルの回路図である。
【図３】本発明のもう１つの実施形態による範囲マッチングセルの回路図である。
【図４】本発明の更に別の実施形態による範囲マッチングセルの回路図である。
【図５】図１〜図４にそれぞれ示した範囲マッチングセルの動作を説明するマッチング表である。
【図６】４−ビットから構成された範囲マッチングセルを用いたＣＡＭの一実施形態である。
【図７】（ＯＰ１、ＯＰ２）が‘大きいか同じで(ＧＥ)’、サーチデータＳＤは（１、１、０、０）、格納データＳＲＤは（１、０、１、０）である場合のＣＡＭの動作を示す図である。
【図８】（ＯＰ１、ＯＰ２）が‘小さいか同じで(ＬＥ)’、ＳＤとＳＲＤは図７と同様である場合のＣＡＭの動作を示す図である。
【図９】（ＯＰ１、ＯＰ２）が‘同じで(ＥＱ)’、ＳＤとＳＲＤは図７と同様である場合のＣＡＭの動作を示す図である。
【図１】
2009525561.tif 000003
【図２】
2009525561.tif 000004
【図３】
2009525561.tif 000005
【図４】
2009525561.tif 000006
【図５】
2009525561.tif 000007
【図６】
2009525561.tif 000008
【図７】
2009525561.tif 000009
【図８】
2009525561.tif 000010
【図９】
2009525561.tif 000011
【国際調査報告】
2009525561.tif 000012
2009525561.tif 000013