(57)【特許請求の範囲】
【請求項１】
保持データをそれぞれ有し、保持データと検索データとが一致したときに検索一致信号をそれぞれ出力する複数の連想メモリ素子を具備した連想メモリ装置において、
入力側に前記検索一致信号をそれぞれ伝送する複数の検索一致線を有し、出力側に前記検索一致線にそれぞれ対応した同じ本数の一致検出線を有し、１つの検索一致信号が何れかの検索一致線を介して入力されたときは、その検索一致線に対応した一致検出線を除く他の一致検出線上をLow レベルにし、２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されたときは、全ての一致検出線上をLow レベルにする２つの一致検出回路と、
一方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第１の検索一致検出回路と、
他方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第２の検索一致検出回路と、
一方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと前記第２の検索一致検出回路の出力レベルとの論理積をとる複数の第１のＡＮＤ回路と、
他方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと前記第１の検索一致検出回路の出力レベルとの論理積をとる複数の第２のＡＮＤ回路と、
前記第１及び第２のＡＮＤ回路の出力側に設けられたＮＯＲ回路とを備え、
前記２つの一致検出回路のうち何れか一方の一致検出回路に２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されたとき、又は前記２つの一致検出回路にそれぞれ１つの検索一致信号が何れかの検索一致線を介して入力されたとき、前記第１及び第２のＡＮＤ回路のそれぞれの出力がLow レベルになって前記ＮＯＲ回路から多重検出信号が出力されることを特徴とする連想メモリ装置の多重一致検出回路。
【請求項２】
請求項１記載の多重一致検出回路を基本回路とし、連想メモリ素子の数に応じてその基本回路を組み合わせてなる連想メモリ装置の多重一致検出回路。
【請求項３】
保持データをそれぞれ有し、保持データと検索データとが一致したときにそれぞれ検索一致信号を出力する複数の連想メモリ素子を具備した連想メモリ装置において、
所定数の連想メモリ素子からの検索一致信号が入力され、少なくとも１つ（但し、所定数未満）の検索一致信号の入力を検出したとき検索一致検出信号を出力し、前記所定数の連想メモリ素子からの検索一致信号の入力を検出したときは検索一致検出信号及び検索一致多重検出信号をそれぞれ出力する複数の多重検出入力回路と、
複数の多重検出入力回路と接続され、１つの検索一致検出信号の入力を検出したときその検索一致検出信号を出力し、複数の検索一致検出信号の入力を検出したときは検索一致検出信号及び検索一致多重検出信号をそれぞれ出力し、また、検索一致検出信号及び検索一致多重検出信号の入力を検出したときは検索一致検出信号及び多重検出信号をそれぞれ出力する多重検出出力回路とを備え、
前記複数の多重検出入力回路及び前記多重検出出力回路を基本回路とし、前記基本回路及びその基本回路の多重検出出力回路を連想メモリ素子の数に応じて組み合わせてなる連想メモリ装置の多重一致検出回路。
【請求項４】
保持データをそれぞれ有し、保持データと検索データとが一致したときにそれぞれ検索一致信号を出力する複数の連想メモリ素子を具備した連想メモリ装置において、
それぞれの連想メモリ素子による保持データと検索データの比較結果の信号が入力されると、その入力信号のＬＳＢ側から最初の検索一致信号を検索し、この検索により最初の検索一致信号を検出したときはその検索一致信号までを有効データ領域として有効領域信号を生成する有効データ領域検出回路と、
前記入力信号に対しその有効領域信号を用いて有効データ領域側の信号をマスクする有効データ領域マスク回路と、
マスクされていない領域の入力信号に検索一致信号が存在するかどうかを検索し、検索一致信号を検出したときは前記入力信号に２以上の検索一致信号が存在するとして多重検出信号を出力する有効データ検出回路と
を備えたことを特徴とする連想メモリ装置の多重一致検出回路。
【請求項５】
保持データをそれぞれ有し、保持データと検索データとが一致したときにそれぞれ検索一致信号を出力する複数の連想メモリ素子を具備した連想メモリ装置において、
選択回路と、
それぞれの連想メモリ素子による保持データと検索データの比較結果の信号が前記選択回路を介して入力されると、その入力信号のＬＳＢ側から最初の検索一致信号を検索し、この検索により最初の検索一致信号を検出したときはその検索一致信号までを有効データ領域として有効領域信号を生成する有効データ領域検出回路と、
前記選択回路からの入力信号に対し前記有効領域信号を用いて有効データ領域外の信号をマスクする無効データ領域マスク回路と、
該無効データ領域マスク回路のマスクにより抽出された有効データ領域側の信号から検索一致信号を判別して出力する検索一致信号判別回路と、
前記選択回路からの入力信号に対し前記有効領域信号を用いて有効データ領域側の信号をマスクする有効データ領域マスク回路と、
該有効データ領域マスク回路によってマスクされた信号を一時的に保持する保持回路とを備え、
前記選択回路は前記保持回路に信号が保持されるとその信号を入力信号として前記有効データ領域検出回路及び無効データ領域マスク回路並びに有効データ領域マスク回路にそれぞれ出力し、前記有効データ領域検出回路は、入力信号に検索一致信号を検出し終えるまで有効領域信号の生成を繰り返し行うことを特徴とする連想メモリ装置の多重一致検出回路。
【請求項６】
前記有効データ領域検出回路は、
直列接続された複数のNMOSトランジスタを有するダイナミックNAND回路と、
前記ダイナミックNAND回路の各NMOSトランジスタの全てのソース端子に電源電圧をチャージする電荷チャージ手段とを備え、
前記ダイナミックNAND回路にグランド側をＬＳＢとしてそれぞれの連想メモリ素子からの信号が入力されると、各NMOSトランジスタは、入力信号に基づいてソース端子に蓄積された電荷を放出して最初の検索一致信号を検出することを特徴とする請求項４又は５記載の連想メモリ装置の多重一致検出回路。
【請求項７】
前記電荷チャージ手段は、検索一致信号に対応して設けられ、ソース側が電源に接続され、ゲート側がプリチャージ端子に接続され、ドレイン側が前記ダイナミックNAND回路の各NMOSトランジスタのそれぞれのソース側に接続され、前記プリチャージ端子にLow レベルのプリチャージ信号が入力されたときに前記NMOSトランジスタの各ソース側に電源電圧をチャージするPMOSトランジスタからなることを特徴とする請求項６記載の連想メモリ装置の多重一致検出回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連想メモリ装置に係わり、特に多重検出信号を高速に発生する多重一致検出回路に関するものである。
【０００２】
【従来の技術】
図１１は従来の連想メモリ装置の多重一致検出回路の構成を示す論理回路図である。この図に示す連想メモリ装置は、例えば２５６エントリに対応して設けられた２５６個の連想メモリ素子を有する連想メモリ素子群５０と、各連想メモリ素子の出力側にそれぞれ配置された２５６個のＡＮＤ回路５１と、８ビットカウンタ５２と、カウンタ出力を２５６ビットにデコードした各信号を順次にHighレベルにするデコーダ５３と、それぞれのＡＮＤ回路５１のHighレベルの出力を論理和とするＯＲ回路５４と、ＯＲ回路５４の出力がHighレベルのときにカウントする２ビットカウンタ５５とを備えている。なお、連想メモリ素子群５０を除く他の回路によって従来の多重一致検出回路が構成されている。
【０００３】
前記のように構成された従来の連想メモリ装置においては、連想メモリ素子群５０に検索データが与えられると、各連想メモリ素子は、保持データと検索データとを比較し、この２つのデータが一致しているときはHighレベルの検索一致信号M0,M1…を出力し、データが不一致のときはLow レベルにする。一方、８ビットカウンタ５２（２５６＝２8 ）、２ビットカウンタ５５は初期化される。
【０００４】
８ビットカウンタ５２にクロックが供給されると、デコーダ５３は、カウンタ出力を２５６ビットにデコードした各信号を順次にHighレベルにし、それぞれのＡＮＤ回路５１に出力する。各ＡＮＤ回路５１は、Highレベルのデコード信号と検索一致信号とが入力されたとき出力をHighレベルにし、ＯＲ回路５４は、ＡＮＤ回路５１からの信号を２ビットカウンタ５５に出力する。この２ビットカウンタ５５は、ＯＲ回路５４の出力がHighレベルのときにカウントし、このカウントを２カウントすると出力をHighレベルにする。即ち、２以上の検索一致信号が入力された場合に２ビットカウンタ５５の上位ビットがHighレベルとなるため、この信号を多重検出信号として出力する。
【０００５】
【発明が解決しようとする課題】
前述した従来の多重一致検出回路は、複数のエントリに対する検索一致信号を順次に検索して、２以上の検索一致信号を確認したとき多重検出信号を出力するようになっているため、多重検出信号の有無を判定するまでに時間がかかり、また、エントリ数により８ビットカウンタ５２やデコーダ５３の構成が異なるため、あるエントリ数の連想メモリ装置を基に他のエントリ数の連想メモリ装置への開発が難しく再利用性が低いという課題があった。
【０００６】
【課題を解決するための手段】
本発明に係る連想メモリ装置の多重一致検出回路は、保持データをそれぞれ有し、保持データと検索データとが一致したときに検索一致信号をそれぞれ出力する複数の連想メモリ素子を具備した連想メモリ装置において、入力側に検索一致信号をそれぞれ伝送する複数の検索一致線を有し、出力側に検索一致線にそれぞれ対応した同じ本数の一致検出線を有し、１つの検索一致信号が何れかの検索一致線を介して入力されたときは、その検索一致線に対応した一致検出線を除く他の一致検出線上をLow レベルにし、２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されたときは、全ての一致検出線上をLow レベルにする２つの一致検出回路と、一方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第１の検索一致検出回路と、他方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第２の検索一致検出回路と、一方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと第２の検索一致検出回路の出力レベルとの論理積をとる複数の第１のＡＮＤ回路と、他方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと第１の検索一致検出回路の出力レベルとの論理積をとる複数の第２のＡＮＤ回路と、第１及び第２のＡＮＤ回路の出力側に設けられたＮＯＲ回路とを備え、２つの一致検出回路のうち何れか一方の一致検出回路に２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されたとき、又は２つの一致検出回路にそれぞれ１つの検索一致信号が何れかの検索一致線を介して入力されたとき、第１及び第２のＡＮＤ回路のそれぞれの出力がLow レベルになってＮＯＲ回路から多重検出信号が出力される。
【０００７】
本発明においては、例えば、一方の一致検出回路に２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されると、一方の一致検出回路の出力側の全ての一致検出線上がLow レベルとなって、第１のＡＮＤ回路の出力をLow レベルにする。一方、第１の検索一致検出回路の出力レベルも前記の検索一致信号の入力によりHighレベルからLow レベルに反転し、第２のＡＮＤ回路の出力をLow レベルにする。この時、第１及び第２のＡＮＤ回路の各出力がLow レベルであるため、ＮＯＲ回路から多重検出信号が出力される。また、２つの一致検出回路にそれぞれ１つの検索一致信号が何れかの検索一致線を介して入力された場合も、第１及び第２のＡＮＤ回路のそれぞれの出力がLow レベルになって、ＮＯＲ回路から多重検出信号が出力される。
【０００８】
【発明の実施の形態】
実施の形態１．
図１は本発明の実施の形態１に係る連想メモリ装置の多重一致検出回路の構成を示す回路図である。なお、説明を簡素化するためにエントリ数４の連想メモリ装置にて説明する。
図１に示す実施の形態１の多重一致検出回路は、連想メモリ素子群１を構成する４つの連想メモリ素子C0〜C3にそれぞれ検索一致線M0〜M3を介して接続された一致検出回路２と、この一致検出回路２に一致検出線A0〜A3を介して接続されたＮＯＲ回路３とからなっている。
【０００９】
一致検出回路２は、検索一致線M0〜M3と一致検出線A0〜A3との交点に配置されたスイッチング用のＮ型トランジスタQ01 …と、それぞれの一致検出線A0〜A3にプルアップ接続されたダイオード接続のＰ型トランジスタ（●）とを備えている。前述した連想メモリ素子C0〜C3は、それぞれ保持データを有し、検索データと一致したときにHighレベルの検索一致信号を検索一致線M0〜M3を介して一致検出回路２に出力する。
【００１０】
Ｎ型トランジスタQ01 …は、図中に示すように、ゲート側が検索一致線M0〜M3に、ドレイン側が一致検出線A0〜A3に、ソース側がグランドにそれぞれ接続されている。また、このＮ型トランジスタQ01 …は、全ての検索一致線M0〜M3と一致検出線A0〜A3との交点に配置されているわけではなく、一定の規則に基づき配置されており、以下、その規則について説明する。
【００１１】
１本の一致検出線には４本の検索一致線との交点があるが、Ｎ型トランジスタQ01 …は、４つの交点のうち１つを除いて配置されている。除かれる検索一致線との交点は、全ての一致検出線で異なるようにする。例えば、一致検出線A0では、検索一致線M0を除く他の検索一致線M1, M2, M3との交点に配置され、一致検出線A1では、検索一致線M1を除く検索一致線M0, M2, M3との交点に配置され、また、一致検出線A2では、検索一致線M2を除く検索一致線M0, M1, M3との交点に配置され、さらに、一致検出線A3では、検索一致線M3を除く検索一致線M0, M1, M2との交点に配置されている。
【００１２】
前記のように構成された実施の形態１の多重一致検出回路の動作を説明する。なお、まず最初に連想メモリ素子C0が保持しているデータのみが検索データと一致しているときの動作を説明し、次に連想メモリ素子C0, C1の保持データが検索データと一致しているときの動作を説明する。
【００１３】
検索動作前では、検索一致線M0〜M3がLow レベルに、一致検出線A0〜A3がプルアップによりHighレベルになっており、ＮＯＲ回路３の出力がLow レベルとなっている。ここで、検索データが入力されて検索動作が完了すると、前述したように連想メモリ素子C0の保持データと検索データとが一致しているため、検索一致線M0のみがHighレベルとなり、残りの検索一致線M1〜M3がLow レベルのままになっている。
【００１４】
この時、検索一致線M0がHighレベルになったことでＮ型トランジスタQ10, Q20, Q30 がオンし、残りのＮ型トランジスタQ01 〜QO3, Q12, Q13, Q21, Q23, Q31, Q32 はオフのままになっている。これにより、Ｎ型トランジスタQ10, Q20, Q30 に接続された一致検出線A1〜A3はLow レベルとなり、残りの一致検出線A0はHighレベルのままであるため、ＮＯＲ回路３の出力はLow レベルのままとなっている。また、他の１本の検索一致線がHighレベルとなっても、同様に１本の一致検出線のみがHighレベルとなるため、ＮＯＲ回路３の出力はLow レベルとなる。
【００１５】
次に、連想メモリ素子C0，C1の保持データと検索データとが一致している場合は、検索一致線M2, M3がLow レベルのままで、検索一致線M0, M1がHighレベルになる。この時、Ｎ型トランジスタQ10, Q20, Q30とQ01, Q21, Q31がオンし、それらに接続された一致検出線A0〜A3の全てがLow レベルとなる。このため、ＮＯＲ回路３の出力はHighレベルに反転し多重検出信号として出力される。また、検索一致線M0〜M3が２つ以上Highレベルとなる他の組み合わせでも、一致検出線A0〜A3の全てがLow レベルとなるため、前記と同様にＮＯＲ回路３の出力がHighレベルとなり多重検出信号が出力される。
【００１６】
よって、多重一致検出回路の一致検出回路２は、連想メモリ素子C0〜C3のいづれか１つが一致しているときのみ、一致した一致検出線がHighレベルになり、不一致の一致検出線がLow レベルとなり、２以上が一致している場合は、全ての一致検出線A0〜A3がLow レベルとなる。これは、検索一致線M0〜M3の多重一致フィルタ機能を有する回路であって、多重一致フィルタの結果である全値Low レベルをもって多重を検出することができる。
【００１７】
以上のように実施に形態１によれば、連想メモリ素子C0〜C3のエントリ数に依らず、全エントリの検索一致信号を同時に検出することが可能になり、このため、多重検索処理の高速化を図れ、特にエントリ数が多い程に効果は顕著となる。
また、一致検出回路２の構成は規則性が極めて高く、異なるエントリ数に対する回路は、既設計回路、既設計レイアウトからの流用、即ち、図２に示すようにエントリ数４の連想メモリ装置からエントリ数８の連想メモリ装置への流用や再利用が容易となり、特定の用途向けに異なるエントリ数の連想メモリ装置を開発する場合の開発期間を短縮できるという効果がある。
【００１８】
実施の形態２．
実施の形態２は、図１に示す一致検出回路を２個用いてエントリ数４からエントリ数８に拡張した連想メモリ装置であり、以下、図３に基づいて説明する。この図３は本発明の実施の形態２に係る連想メモリ装置の多重一致検出回路の構成を示す回路図である。なお、図１で説明した実施の形態１と同一又は相当部分には同じ符号を付し説明を省略する。
【００１９】
図３に示す多重一致検出回路は、４個の連想メモリ素子C0〜C3にそれぞれ検索一致線M0〜M3を介して接続された一方の一致検出回路H1と、残りの４個の連想メモリ素子C4〜C7にそれぞれ検索一致線M4〜M7を介して接続された他方の一致検出回路H2と、一方の一致検出回路H1に一致検出線A0〜A3を介して接続されたＡＮＤ回路４〜７（第１のＡＮＤ回路）と、他方の一致検出回路H2に一致検出線A4〜A7を介して接続されたＡＮＤ回路８〜１１（第２のＡＮＤ回路）と、ＡＮＤ回路４〜７にそれぞれ接続された一致検出線A4_7と検索一致線M4〜M7との交点に配置されたスイッチング用のＮ型トランジスタQ101〜Q104（第２の検索一致検出回路）と、ＡＮＤ回路８〜１１にそれぞれ接続された一致検出線A0_3と検索一致線M0〜M3との交点に配置されたスイッチング用のＮ型トランジスタQ201〜Q204（第１の検索一致検出回路）と、ＡＮＤ回路４〜１１の出力A01〜A31とA41〜A71が接続されたＮＯＲ回路３と、一致検出線A4_7、A0_3にそれぞれプルアップ接続されたダイオード接続のＰ型トランジスタ（●）とから構成されている。
【００２０】
なお、一致検出回路H1，H2にそれぞれ設けられたＮ型トランジスタQ01 …の位置は図１に示す一致検出回路２と同じである。前述したＮ型トランジスタQ101〜Q104及びQ201〜Q204は、それぞれのゲート側が検索一致線M0〜M7に、ドレイン側が一致検出線A0〜A7に、ソース側がグランドにそれぞれ接続されている。
【００２１】
前記のように構成された実施の形態２の多重一致検出回路の動作を説明する。なお、まず最初に連想メモリ素子C0の保持データのみが検索データと一致したときの動作を説明し、次に連想メモリ素子C0，C1の保持データと検索データとが一致したときの動作を説明し、さらに、連想メモリ素子C0，C4の保持データと検索データとが一致したときの動作を説明する。
【００２２】
連想メモリ素子C0の保持データと検索データとが一致している場合、一致検出回路H1側の一致検出線A0〜A3は、実施の形態１と同様に一致検出線A0のみがHighレベルで、他の一致検出線A1〜A3はLow レベルとなり、追加された一致検出線A4_7は、Highレベルのままになっている。また、一致検出回路H2側の一致検出線A4〜A7はHighレベルのままであり、追加された一致検出線A0_3は、検索一致線M0のHighレベルによりＮ型トランジスタQ201がオンしてLow レベルとなる。ここで、それぞれのＡＮＤ回路４〜１１の出力A01〜A31とA41〜A71を見ると、ＡＮＤ回路４では、入力側が共にHighレベルであるため、その出力A01 がHighレベルとなり、他のＡＮＤ回路５〜１１では、入力側の何れか一方がLow レベルであるため、それぞれの出力A11 〜A31とA41〜A71 がLow レベルとなり、このため、ＮＯＲ回路３の出力はLow レベルのままとなり、多重検出信号が出力されない状態となっている。
【００２３】
次に、連想メモリ素子C0，C1の保持データと検索データとが一致した場合は、一致検出回路H1側の一致検出線A0〜A3が実施の形態１と同様に全てLow レベルとなり、追加された一致検出線A4_7は、Highレベルのままになっている。一致検出回路H2側の一致検出線A4〜A7はHighレベルのままであり、追加された一致検出線A0_3は、検索一致線M0，M1のHighレベルによりＮ型トランジスタQ201，Q202がオンしてLow レベルとなる。ここで、それぞれのＡＮＤ回路４〜１１の出力を見ると、全てのＡＮＤ回路４〜１１の入力側は、何れか一方がLow レベルであるため、それぞれの出力A01〜A31とA41〜A71がLow レベルとなり、このため、ＮＯＲ回路３の出力はLow レベルからHighレベルに反転して、多重検出信号として出力される。
【００２４】
さらに、連想メモリ素子C0，C4の保持データと検索データとが一致した場合は、一致検出回路H1側の一致検出線A0〜A3は、前記と同様に一致検出線A0のみがHighレベルとなり、他の一致検出線A1〜A3はLow レベルとなり、追加された一致検出線A4_7は、検索一致線M4のHighレベルによりＮ型トランジスタQ101がオンしてLow レベルとなる。また、一致検出回路H2側の一致検出線A4〜A7は、一致検出線A4のみがHighレベルとなり、他の一致検出線A5〜A7はLow レベルとなり、追加された一致検出線A0_3は、前記と同様に検索一致線M0のHighレベルによりＮ型トランジスタQ201がオンしてLow レベルとなる。それぞれのＡＮＤ回路４〜１１の出力を見ると、全てのＡＮＤ回路４〜１１の入力側は、何れか一方がLow レベルであるため、全ての出力A01〜A31とA41〜A71がLow レベルとなり、よってＮＯＲ回路３の出力はHighレベルとなり、多重検出信号として出力される。
【００２５】
以上のように実施の形態２においては、実施の形態１に示す連想メモリ装置からエントリ数を拡張する場合、図２に示す拡張方法に比べ、使用する回路素子を約１／２に削減することができる。また、拡張に対する規則性は実施の形態１と同様に高いため、既設計回路、レイアウトからの流用、再利用が容易になり、特定の用途向けに異なるエントリ数の連想メモリ装置を開発する場合の開発期間を短縮できるという効果がある。
【００２６】
なお、前記の実施の形態２では、エントリ数８の連想メモリ装置に適用して説明したが、図３に示す本実施の形態２の多重一致検出回路を一組の基本回路とし、この基本回路をエントリ数に応じて組み合わせるようにしてもよい。例えば、エントリ数１６の連想メモリ装置に適用する場合は二組の基本回路で多重一致検出回路を構成し、また、エントリ数２４の連想メモリ装置に適用する場合は三組の基本回路で多重一致検出回路を構成する。この場合、ＡＮＤ回路の出力が増加するので、それに対応したＮＯＲ回路を用意する。
【００２７】
実施の形態３．
実施の形態３は、連想メモリ装置の多重一致検出回路を論理回路で構成したものであり、以下、図４に基づいて説明する。図４は本発明の実施の形態３に係る連想メモリ装置の４ビット用の多重一致検出回路の構成を示す論理回路図である。
【００２８】
図４に示す４ビット用の多重一致検出回路は、例えば２つの多重検出入力回路２１、２２と、これら多重検出入力回路２１，２２の出力側に設けられた多重検出出力回路２３とから構成されている。多重検出入力回路２１は、ＡＮＤ回路２１ａとＯＲ回路２１ｂとからなり、連想メモリ素子（図示せず）からHighレベルの検索一致信号Y1,Y2 が出力されると、ＡＮＤ回路２１ａが出力Y5をHighレベルにし、検索一致多重検出信号として出力し、一方、ＯＲ回路２１ｂは出力Y6をHighレベルにし、検索一致検出信号として出力する。また、検索一致信号Y1,Y2 の何れか一方がHighレベルのときは、ＯＲ回路２１ｂが出力Y6をHighレベルにし、検索一致検出信号として出力する。
【００２９】
また、もう一方の多重検出入力回路２２は、前記と同様にＡＮＤ回路２２ａとＯＲ回路２２ｂとからなり、２入力の検索一致信号Y3,Y4 が共にHighレベルのときは、ＡＮＤ回路２２ａが出力Y7をHighレベルにし、検索一致多重検出信号として出力し、一方、ＯＲ回路２２ｂは出力Y8をHighレベルにし、検索一致検出信号Y8として出力する。また、検索一致信号Y3,Y4 の何れか一方がHighレベルのときは、ＯＲ回路２２ｂが出力Y8をHighレベルにし、検索一致検出信号として出力する。
【００３０】
多重検出出力回路２３は、入力端に多重検出入力回路２１，２２側の出力Y6,Y8 がそれぞれ接続されたＡＮＤ回路２３ａ及びＯＲ回路２３ｂと、そのＡＮＤ回路２３ａの出力と多重検出入力回路２１側の出力Y5とが接続されたＯＲ回路２３ｃと、このＯＲ回路２３ｃの出力と多重検出入力回路２２側の出力Y7とが接続されたＯＲ回路２３ｄとから構成されている。多重検出入力回路２１側の出力Y5と多重検出入力回路２２側の出力Y7 の何れか一方がHighレベル（検索一致多重検出信号）のとき、また、多重検出入力回路２１側の出力Y6と多重検出入力回路２２側の出力Y8とが共にHighレベル（検索一致検出信号）のときは、ＯＲ回路２３ｄが出力Y9をHighレベルにし、多重検出信号として出力する。また、多重検出入力回路２１側の出力Y6又は多重検出入力回路２２側の出力Y8の何れか一方がHighレベル（検索一致検出信号）のときは、ＯＲ回路２３ｂが出力Y10 をHighレベルにし、検索一致検出信号として出力する。
【００３１】
前記のように構成された４ビットの多重一致検出回路の動作を図５に示す真理値表を参照しながら説明する。
まず、入力の４ビット（検索一致信号Y1〜Y4）全てがLow レベル（検索不一致）の場合を説明する。この場合は、多重検出入力回路２１、２２が共にＡＮＤ回路２１ａ、２２ａとＯＲ回路２１ｂ、２２ｂとで構成されているので、多重検出出力回路２３は、Low レベルの多重検出信号Y9を出力すると共に、Low レベルの検索一致検出信号Y10 を出力する。
【００３２】
次に、入力の４ビットのうち１ビットのみがHighレベル（検索一致）のときを説明する。即ち、４本の検索一致信号Y1〜Y4のうち例えば検索一致信号Y1のみがHighレベルの場合、多重検出入力回路２１は、出力Y5をLow レベルにすると共に、出力Y6をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。もう一方の多重検出入力回路２２は、検索一致信号Y3,Y4 が共にLow レベルであるため、出力Y7,Y8 を共にLow レベルにする。多重検出出力回路２３は、多重検出入力回路２１側の出力Y6のみがHighレベルであるため、出力Y10 のみをHighレベルにし検索一致検出信号として出力する。
【００３３】
検索一致信号Y2のみがHighレベルのときは、前記と同様に、多重検出入力回路２１は、出力Y5をLow レベルにし、出力Y6をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。もう一方の多重検出入力回路２２は、出力Y7,Y8 を共にLow レベルにする。この時、多重検出出力回路２３は、多重検出入力回路２１側の出力Y6がHighレベルであるため、出力Y10 のみをHighレベルにし検索一致検出信号として出力する。
【００３４】
検索一致信号Y3のみがHighレベルのときは、多重検出入力回路２１は出力Y5,Y6 を共にLow レベルにし、もう一方の多重検出入力回路２２は、出力Y7をLow レベルにし、出力Y8をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。この時、多重検出出力回路２３は、多重検出入力回路２２側の出力Y8がHighレベルであるため、出力Y10 のみをHighレベルにし検索一致検出信号として出力する。
【００３５】
検索一致信号Y4のみがHighレベルのときは、前記と同様に、多重検出入力回路２１は出力Y5,Y6 を共にLow レベルにし、もう一方の多重検出入力回路２２は、出力Y7をLow レベルにし、出力Y8をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。この時、多重検出出力回路２３は、多重検出入力回路２２側の出力Y8がHighレベルであるため、出力Y10 のみをHighレベルにし検索一致検出信号として出力する。
【００３６】
以上のように入力の４ビットのうち１ビットのみがHighレベル（一致検出）の場合は、多重検出出力回路２３の出力Y9がLow レベルになって多重検出なしの状態となり、一方、出力Y10 はHighレベルとなって検索一致の検出状態となる。
【００３７】
次に、入力の４ビットのうち２ビットがHighレベル（検索一致）の場合を説明する。
検索一致信号Y1,Y2 がHighレベルのときは、多重検出入力回路２１は、出力Y5をHighレベルにし検索一致多重検出信号として多重検出出力回路２３に出力すると共に、出力Y6をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。もう一方の多重検出入力回路２２は、検索一致信号Y3,Y4 が共にLow レベルであるため、出力Y7,Y8 を共にLow レベルにする。多重検出出力回路２３は、多重検出入力回路２１側の出力Y5,Y6 が共にHighレベルであるため、出力Y9をHighレベルにし多重検出信号として出力すると共に、出力Y10 をHighレベルにし検索一致検出信号として出力する。
【００３８】
検索一致信号Y1,Y3 がHighレベルのときは、多重検出入力回路２１は、出力Y5をLow レベルにし、出力Y6をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。もう一方の多重検出入力回路２２は、出力Y7をLow レベルにし、出力Y8をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。多重検出出力回路２３は、多重検出入力回路２１側の出力Y6と多重検出入力回路２２側の出力Y8とが共にHighレベルであるため、出力Y9をHighレベルにし多重検出信号として出力し、また、出力Y10 をHighレベルにし検索一致検出信号として出力する。
【００３９】
検索一致信号Y1,Y4 がHighレベルのときは、多重検出入力回路２１は、出力Y5をLow レベルにし、出力Y6をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。もう一方の多重検出入力回路２２は、出力Y7をLow レベルにし、出力Y8をHighレベルにし検索一致検出信号として多重検出出力回路２３に出力する。多重検出出力回路２３は、多重検出入力回路２１側の出力Y6と多重検出入力回路２２側の出力Y8とが共にHighレベルであるため、出力Y9をHighレベルにし多重検出信号として出力し、また、出力Y10 をHighレベルにし検索一致検出信号として出力する。
【００４０】
以上３つのパターンを示したが、その他の場合も入力の４ビットのうち２ビットがHighレベル（検索一致）の場合、多重検出出力回路２３の出力Y9,Y10が共にHighレベルとなり、検索一致の検出と多重の検出となる。また、入力の４ビットのうち３ビットがHighレベルの場合は、図５の真理値表に示すように多重検出出力回路２３の出力Y9,Y10が共にHighレベルとなり、検索一致の検出と多重の検出となる。
【００４１】
以上のように実施の形態３においては、２以上の検索一致信号が入力されたとき検索一致多重検出信号及び検索一致検出信号を出力し、１つの検索一致信号が入力されたときは検索一致検出信号を出力する多重検出入力回路２１，２２と、この多重検出入力回路２１，２２からの検索一致多重検出信号又は２以上の検索一致検出信号が入力されたとき多重検出信号を出力し、１つの検索一致検出信号が入力されたときはその検索一致検出信号を出力する多重検出出力回路２３とで多重一致検出回路を構成したので、論理回路の段数を少ない状態で検索一致信号の多重を高速で検出できるという効果がある。
【００４２】
実施の形態４．
実施の形態４は、実施の形態３の４ビット用の多重一致検出回路を用いて１６ビット用の多重一致検出回路を構成したものである。図６は本発明の実施の形態４に係る連想メモリ装置の１６ビット用の多重一致検出回路の構成を示す論理回路図である。
この図に示す１６ビット用の多重一致検出回路は、図４に示す多重検出入力回路２１，２２と多重検出出力回路２３とを組み合わせたものを基本回路３０とし、この基本回路３０を連想メモリ素子（図示せず）の数（１６ビット分）に応じて４個配列し、２個づつの基本回路３０の出力側に基本回路３０に用いられている多重検出出力回路２３（以下、符号を「３１」、「３２」とする）を配置し、さらに、この２個の多重検出出力回路３１、３２の出力側に同じ多重検出出力回路３３を設けてなっている。
【００４３】
１個の多重検出出力回路３１に接続されている２個の基本回路３０のうち、一方の基本回路３０の出力Y9は多重検出出力回路３１のＯＲ回路３１ｃに接続され、出力Y10 はＡＮＤ回路３１ａ及びＯＲ回路３１ｂに接続され、また、他方の基本回路３０の出力Y9は多重検出出力回路３１のＯＲ回路３１ｄに接続され、出力Y10 はＡＮＤ回路３１ａ及びＯＲ回路３１ｂに接続されている。
【００４４】
また、出力端側に設けられた１個の多重検出出力回路３３に接続されている２個の多重検出出力回路３１，３２のうち、一方の多重検出出力回路３１の出力Y91 は出力端側の多重検出出力回路３３のＯＲ回路３３ｃに接続され、出力Y101はＡＮＤ回路３３ａ及びＯＲ回路３３ｂに接続され、また、他方の多重検出出力回路３２の出力Y91 は出力端側の多重検出出力回路３３のＯＲ回路３３ｄに接続され、出力Y10 はＡＮＤ回路３３ａ及びＯＲ回路３３ｂに接続されている。
【００４５】
前記のように構成された１６ビット用の多重一致検出回路においては、実施の形態３と同様に、１６本の検索一致信号のうち何れか１本の検索一致信号が入力されたときは、出力端側の多重検出出力回路３３の出力Y102のみがHighレベルとなり検索一致検出信号として出力される。また、２本以上の検索一致信号が入力されたときは、その多重検出出力回路３３の出力Y92 がHighレベルとなり多重検出信号として出力されると共に、出力Y102がHighレベルとなり検索一致検出信号として出力される。
【００４６】
以上のように、極めて簡単にビット数拡張の多重一致検出回路を構成でき、しかも、ビット数の拡張に関わりなく高速で検索一致信号の多重を検出できる。
【００４７】
実施の形態５．
図７は本発明の実施の形態５に係る連想メモリ装置の多重一致検出回路の構成を示すブロック図である。
実施の形態５における多重一致検出回路は、有効データ領域検出回路４０と、有効データ領域マスク回路４１と、有効データ検出回路４２とからなっている。前述の有効データ領域検出回路４０は、ｎビットの信号幅をもつ信号in[n-1:0] が入力されると、その入力信号のＬＳＢ側から最初の有効を示すビット「１」（検索一致信号）を検索し、この検索により最初の「１」を検出したときはそのビットまでを有効データ領域として有効領域信号m1[n-1:0] を生成する。有効データ領域マスク回路４１は、ｎビットの信号幅をもつ入力信号in[n-1:0] に対し、有効データ領域検出回路４０の有効領域信号m1[n-1:0] の反転の論理積をとって有効データ領域の信号をマスクし、信号m2[n-1:0] として出力する。有効データ検出回路４２は、有効データ領域マスク回路４１によりマスクされた信号m2[n-1:0] に有効データが含まれているかどうかを検出し、その結果を出力する。
【００４８】
次に、ｎ＝８の場合について本実施の形態５の多重一致検出回路の動作を説明する。なお、正論理を用い、ビット上の「１」を有効データ、「０」を無効データとする。
例えば、８ビットの信号幅をもつ信号in[7:0]=0010_0010 が入力されると、有効データ領域検出回路４０は、ＬＳＢ側から最初の有効データ、この場合では、１ビット目が有効データであるため、入力信号in[7:0]=0010_0010 から有効領域信号m1=0000_0011を生成し、有効データ領域マスク回路４１に出力する。この有効データ領域マスク回路４１は、入力信号in[7:0]=0010_0010 の個々のビットに対して有効領域信号m1=0000_0011の反転（1111_1100 ）との論理積をとって有効データ領域の信号をマスクし、信号m2[7:0]=0010_0000 を出力する。即ち、この出力信号m2[7:0] は以下の式にて表される。
m2[7:0]=in[7:0] ＆ ￣ m1[7:0] （＆：論理積、￣：反転）
一方、有効データ検出回路４２は、入力された信号m2[7:0] に「１」が含まれているかどうかを検索し、この場合は、２つ以上の有効データが入力信号in[7:0] に含まれているので、出力信号out を「１」にして２つ以上の有効データが含まれていた旨を通知する。本論理は、入力される信号の個々のビットの論理和をとることを意味するものである。即ち、出力信号out は以下の式にて表される。
out=（m2[7]｜m2[6]｜m2[5]｜m2[4]｜m2[3]｜m2[2]｜m2[1]｜m2[0]）（｜：論理和）
【００４９】
次に、入力信号がin[7:0]=0000_1000 の場合について説明する。この場合は、ＬＳＢ側から３ビット目が有効データであるため、有効データ領域検出回路４０の出力はm1[7:0]=0000_1111 となり、有効データ領域マスク回路４１の出力はm2=0000_0000となる。従って、有効データ検出回路４２は、出力信号out を「０」にし、２つ以上の有効データが入力信号in[7:0] に含まれていなかった旨を通知する。
【００５０】
実施の形態５における多重一致検出回路は、ｎビットの信号幅をもつ入力信号in[n-1:0] のＬＳＢ側から最初の有効データ「１」までの領域幅を検出して有効領域信号m1[n-1:0] を生成し、前記入力信号in[n-1:0] に対してその有効領域信号m1[n-1:0] の反転の論理積をとって有効データ領域の信号をマスクして信号m2[n-1:0] を生成し、このマスクした信号m2[n-1:0] に有効データが含まれているかどうかを検出してその結果を出力するものであるため、連想メモリ装置のエントリ数に応じた多重一致検出回路を容易に提供できる。
【００５１】
（実施例１）
ここで、前述した有効データ領域検出回路４０の構成を具体的に説明する。図８は多重一致検出回路の有効データ領域検出回路の一例を示す回路構成図である。
図において、INV1_0〜INV1_7は信号in[0] 〜in[7] がそれぞれ入力されるインバータである。N1_0〜N1_7はNMOSトランジスタで、そのうち、NMOSトランジスタN1_0は、ソース側が内部ノードnet_0 に接続され、ゲート側がインバータINV1_0 の出力端に接続され、ドレイン側が内部ノードnet_1 に接続されている。NMOSトランジスタN1_1は、ソース側が内部ノードnet_1 に接続され、ゲート側がインバータINV1_1の出力端に接続され、ドレイン側が内部ノードnet_2 に接続されている。
【００５２】
NMOSトランジスタN1_2は、ソース側が内部ノードnet_2 に接続され、ゲート側がインバータINV1_2の出力端と接続され、ドレイン側が内部ノードnet_3 に接続されている。NMOSトランジスタN1_3は、ソース側が内部ノードnet_3 に接続され、ゲート側がインバータINV1_3の出力端と接続され、ドレイン側が内部ノードnet_4 に接続されている。NMOSトランジスタN1_4は、ソース側が内部ノードnet_4 に接続され、ゲート側がインバータINV1_4の出力端と接続され、ドレイン側が内部ノードnet_5 に接続されている。NMOSトランジスタN1_5は、ソース側が内部ノードnet_5 に接続され、ゲート側がインバータINV1_5の出力端と接続され、ドレイン側が内部ノードnet_6 に接続されている。NMOSトランジスタN1_6は、ソース側が内部ノードnet_6 に接続され、ゲート側がインバータINV1_6の出力端と接続され、ドレイン側が内部ノードnet_7 に接続されている。NMOSトランジスタN1_7は、ソース側が内部ノードnet_7 に接続され、ゲート側がインバータINV1_7の出力端と接続され、ドレイン側がPMOSトランジスタP0のドレインと接続されている。
【００５３】
NOはNMOSトランジスタで、ソース側がグランドに接続され、ゲート側がプリチャージ端子pcに接続され、ドレイン側が内部ノードnet_0 に接続されている。P0は前述したPMOSトランジスタで、ソースがエアが電源VDD に接続され、ゲート側がプリチャージ端子pcに接続され、ドレイン側がNMOSトランジスタN1_7のドレインに接続されている。P1_0〜P1_7はPMOSトランジスタで、それぞれのソース側が電源VDD に接続され、それぞれのゲート側がプリチャージ端子pcに接続され、各ドレイン側はそれぞれ内部ノードnet_0〜net_7に接続されている。INV2_0〜INV2_7は出力側に設けられたインバータで、入力側がそれぞれ内部ノードnet_0 〜net_7 と接続されている。
【００５４】
次に、前述した有効データ領域検出回路の動作を説明する。
まず、プリチャージ信号線pcがLow レベルになると、NMOSトランジスタNOがオフ状態に、PMOSトランジスタP0及び８個のPMOSトランジスタP1_0〜P1_7がオン状態となる。この時、入力信号in[7] 〜in[0] の値に関係なく、内部ノードnet_0 〜net_7 がHighレベルとなり、各インバータINV2_0〜INV2_7の出力信号out[7]〜out[0]がそれぞれLow レベルとなる。
【００５５】
本回路４０では、プリチャージ端子pcがプリチャージ状態（Low レベル）の間に入力信号in[7] 〜in[0] の値を確定し、その後、プリチャージ端子pcをHighレベルにすることにより、内部ノードnet_0 〜net_7 に蓄積された電荷を、NMOSトランジスタNO及び８個のNMOSトランジスタN1_0 〜N1_7 を介して放出することにより論理演算を実行するダイナミック論理回路を構成する。
【００５６】
この場合、NMOSトランジスタNOはオン状態に、PMOSトランジスタP0及び８個のPMOSトランジスタP1_0〜P1_7がオフ状態となり、入力信号in[7] 〜in[0] が入力されるインバータINV1_0〜INV1_7の出力の値に応じてオンしているNMOSトランジスタN1_0〜N1_7により、インバータINV2_0〜INV2_7の出力信号out[7]〜out[0]が決定される。
【００５７】
例えば、図７で述べた入力信号in[7:0]=0010_0010 が入力されたときは、インバータINV1_7〜INV1_0の出力信号がINV1[7:0]=1101_1101 となる。この時、NMOSトランジスタN1_0，N1_2〜N1_4，N1_6及N1_7はオン状態に、その他のNMOSトランジスタN1_1，N1_5はオフ状態となる。一方、内部ノードnet_0 は、入力端子pcのHighレベルによりNMOSトランジスタNOがオン状態となっているため、その内部ノードnet_0 に蓄積された電荷は放出され、Low レベルに遷移する。
【００５８】
内部ノードnet_1 は、NMOSトランジスタN1_0がオン状態にあるため、その内部ノードnet_1 に蓄積された電荷はNMOSトランジスタN1_0及びNMOSトランジスタNOを介して放出され、Low レベルに遷移する。また、内部ノードnet_2 は、NMOSトランジスタN1_1がオフ状態にあるため、その内部ノードnet_2 に蓄積された電荷は放出されず、Highレベルのままとなる。さらに、内部ノードnet_3 〜net_7 は、NMOSトランジスタN1_1がオフ状態にあるため、内部ノードnet_2 と同様に蓄積された電荷は放出されず、Highレベルのままとなる。
【００５９】
前述したように内部ノードnet_0 及びnet_1 はLow レベルに遷移し、その他の内部ノードnet_2 〜net_7 はHighレベルを保ちつづけるため、インバータINV2_7〜INV2_0を介した出力信号out は[0000_0011] となり、前述した有効領域信号m1と同じ結果の[0000_0011] が出力される。
【００６０】
次に、入力信号がin[7:0]=0000_1000 の場合について説明する。
この場合は、インバータINV1_7〜INV1_0の出力信号はINV1[7:0]=1111_0111 となる。この時、NMOSトランジスタN1_3のみがオフ状態となり、その他のNMOSトランジスタはオン状態となる。この時、内部ノードnet_0 〜net_3 に蓄積された電荷はNMOSトランジスタジスタN1_0〜N1_2及びNMOSトランジスタNOを介して放出されてLow レベルに遷移し、その他の内部ノードnet_4 〜net_7 はNMOSトランジスタN1_3がオフ状態にあるため、電荷は放出されず、Highレベルのままとなる。従って、インバータINV2_7〜INV2_0を介して出力される出力信号out は[0000_1111] となり、前述した有効領域信号m1と同じ結果の[0000_1111] が出力される。
【００６１】
前記のように構成された有効データ領域検出回路４０を多重一致検出回路の一部材として用いたので、容易にビット幅を拡張することが可能になり、連想メモリ装置に組み込むに際して高集積な多重一致検出回路を構成することが可能になる。
【００６２】
（実施例２）
本実施例２は図８に示す実施例１の有効データ領域検出回路を複数に分割したものであり、以下、図９に基づいて説明する。図９は実施例２の有効データ領域検出回路を示す回路構成図である。なお、説明を簡略化するために、信号in[0] 〜in[3] が入力される回路をＬＳＢ側回路、信号in[4] 〜in[7] が入力される回路をＭＳＢ側回路と称する。また、PMOSトランジスタP0，P1_0〜P1_7、NMOSトランジスタN0，N1_0〜N1_7並びに８個のインバータINV1_0〜INV1_7、８個のインバータINV2_0〜INV2_7は実施例１と同じであるため、詳細な説明は割愛する。
【００６３】
ＬＳＢ側回路のPMOSトランジスタP2は、ソース側が電源VDD に接続され、ゲート側がプリチャージ端子pcに接続され、ドレイン側がＭＳＢ側のNMOSトランジスタN1_3のドレイン（net_c ）に接続されている。内部ノードnet_c はインバータINV3の入力側に接続されている。
ＭＳＢ側回路のNMOSトランジスタN2は、ゲート側がＬＳＢ側回路に設けられたインバータINV3の出力側に接続され、ソース側がNMOSトランジスタN0のドレインに接続され、ドレイン側がNMOSトランジスタN1_4のソース（net_4 ）に接続されている。
【００６４】
次に、実施例２の有効データ領域検出回路の動作を説明する。
まず、プリチャージ端子pcがLow レベルになると、NMOSトランジスタN0がオフ状態、PMOSトランジスタP0及び８個のPMOSトランジスタP1_0〜P1_7がオン状態となり、入力信号in[7]〜in[0]の値に関係なく内部ノードnet_0 〜net_7 がHighレベルとなり、出力信号out[7]〜out[0]がLow レベルとなる。この時、ＬＳＢ側回路の内部ノードnet_c もHighレベルにチャージされ、インバータINV3の出力端子ＣはLow レベルとなり、また、ＭＳＢ側回路においては、前記のインバータINV3の出力信号ＣがLow レベルであるため、NMOSトランジスタN2はオフ状態となる。
【００６５】
ここで、入力信号in[7:0]＝0010_0010が入力されたときは、実施例１と同様にNMOSトランジスタN1_0，N1_2〜N1_4，N1_6及びN1_7がオン状態となり、残り２つのNMOSトランジスタN1_1，N1_5がオフ状態となる。この時、ＬＳＢ側回路においては、実施例１と同様に内部ノードnet_0 及びnet_1 はLow レベルに遷移し、その他の内部ノードnet_2 ，net_3 ，net_c はHighレベルを保ちつづける。このため、インバータINV3はLow レベルの出力信号Ｃを保持し、これに伴ってNMOSトランジスタN2もオフ状態を保持する。また、ＭＳＢ側回路においては、NMOSトランジスタN2がオフ状態であるため、全ての内部ノードnet_4 〜net_7 の電荷がHighレベルのまま保たれる。従って、インバータINV2_1〜INV2_7を介した出力信号out は0000_0011 となり、実施例５に示す有効領域信号m1=0000_0011と同じ結果が出力される。
【００６６】
次に、入力信号in[7:0]=0000_1000 の場合について説明する。この場合には、インバータINV1_7〜INV1_0の出力信号はINV1[7:0]=1111_0111 となる。この時、ＬＳＢ側回路においては、NMOSトランジスタN1_3のみがオフ状態となり、その他のNMOSトランジスタN1_0〜N1_2はオン状態となる。また、内部ノードnet_0 〜net_3 に蓄積された電荷は、NMOSトランジスタN0及びNMOSトランジスタN1_0〜N1_2を介して放出され、Low レベルに遷移する。内部ノードnet_c は、NMOSトランジスタN1_3がオフ状態にあるため、電荷の放出が行われず、Highレベルのまま保たれる。従って、前記と同様にインバータINV3の出力信号ＣはLow レベルとなり、ＭＳＢ側の回路においては、NMOSトランジスタN2がオフ状態を保ちつづけるため、インバータINV2_0〜INV2_7を介して出力される出力信号out は0000_1111 となり、実施例５に示す有効領域信号m1=0000_1111と同じ結果が出力される。
【００６７】
次に、インバータINV3の出力信号Ｃが有効になる場合に付いて説明する。
入力信号in[7:0]=0001_0000 の場合、インバータINV1_7〜INV1_0の出力信号は、INV1=1110_1111となり、ＬＳＢ側回路においては、全てのNMOSトランジスタN1_0〜N1_3がオン状態になり、内部ノードnet_0 〜net_3及びnet_cはNMOSトランジスタN0及びN1_0〜N1_3を介して電荷を放出し、Low レベルとなる。インバータINV3の出力信号ＣはHighレベルとなり、また、ＭＳＢ側回路においては、NMOSトランジスタN2はオン状態となり、内部ノードnet_4 に蓄積されていた電荷は、ＭＳＢ側回路のNMOSトランジスタN0及びN1_4を介して放出され、Low レベルに遷移する。NMOSトランジスタN1_4はオフ状態にあるため、その他の内部ノードnet_5〜net_7の電荷は保持されつづける。従って、８個のインバータINV2_7〜INV2_0を介した出力信号out は0001_1111 となる。
【００６８】
以上のように実施例２によれば、ビット幅が広くなり、動作速度が劣化してきた場合においても、本回路を分割することにより、高速処理が可能な多重一致検出回路を提供することができる。
【００６９】
以上のように実施の形態５における多重一致検出回路は、ｎビットの信号幅をもつ入力信号in[n-1:0] に対しＬＳＢ側から最初の有効データ「１」までの領域幅を検出して有効領域信号m1[n-1:0] を生成し、前記入力信号in[n-1:0] とその有効領域信号m1[n-1:0] の各ビットの論理積をとって無効領域外の信号をマスクした信号m3[n-1:0] を生成し、このマスクした入力信号m3[n-1:0] に対し、バイナリ・エンコードを実行して mビットの信号幅をもつ信号out[m-1:0]を出力するので、連想メモリ装置のエントリ数に応じた多重一致検出回路を容易に提供できる。
【００７０】
また、実施例１（図８）及び実施例２（図９）に示された有効データ領域検出回路４０を利用しても、多重一致が発生した場合にＬＳＢ側の一致結果のみを抽出するので、正確なアドレス値のエンコード結果を出力することが可能となる。
【００７１】
実施の形態６．
図１０は本発明の実施の形態６に係る連想メモリ装置の多重一致検出回路の構成を示すブロック図である。なお、図７で説明した実施の形態５と同一又は相当部分には同じ符号を付し説明を省略する。
【００７２】
実施の形態６の多重一致検出回路は、選択回路４５と、選択回路４５の出力信号が入力される有効データ領域検出回路４０と、選択回路４５の出力信号及び有効データ領域検出回路４０の有効領域信号m1[n-1:0] が入力される無効データ領域マスク回路４３と、無効データ領域マスク回路４３の信号m3[n-1:0] に対してバイナリ・エンコードを実行して mビットの信号幅をもつ信号out[m-1:0]を出力するエンコーダ回路４４と、選択回路４５の出力信号及び有効データ領域検出回路４０の有効領域信号m1[n-1:0] が入力される有効データ領域マスク回路４１と、有効データ領域マスク回路４１の出力信号m2[n-1:0] を保持するデータ保持回路４６とからなっている。
【００７３】
前述した無効データ領域マスク回路４３は、入力信号in[n-1:0] と有効領域信号m1[n-1:0] の各ビットをそれぞれ論理積をとって無効領域の信号をマスクし、それを信号m3[n-1:0] として出力する。エンコーダ回路４４は、無効データ領域マスク回路４３によりマスクされた信号m3[n-1:0] に対し、バイナリ・エンコードを実行して mビットの信号幅をもつ信号out[m-1:0]を出力する。
【００７４】
選択回路４５は、ｎビットの信号幅をもつ入力信号in[n-1:0] を出力し、データ保持回路４６に保持された信号m2[n-1:0] の中に有効データ「１」が含まれているときに選択して信号m4[n-1:0] として出力する。データ保持回路４６は、フリップ・フロップ等で構成される記憶素子からなり、入力信号m2[n-1:0] を一定期間保持する機能を有している。
【００７５】
次に、ｎ＝８の場合について本実施の形態６の多重一致検出回路の動作を説明する。なお、正論理を用い、正論理を用い、ビット上の「１」を有効データ、「０」を無効データとする。
例えば、８ビットの信号幅をもつ信号in[7:0]=0010_0010 が入力されると、選択回路７がその入力信号in[7:0] を選択し、有効データ領域検出回路４０、有効データ領域マスク回路４３及び無効データ領域マスク回路４１にそれぞれ出力する。
【００７６】
この時、有効データ領域検出回路４０は、ＬＳＢ側から最初の有効データ、この場合では、１ビット目が有効データであるため、入力信号in[7:0]=0010_0010 から有効領域信号m1=0000_0011を生成し、無効データ領域マスク回路４３に出力する。この無効データ領域マスク回路４３は、入力信号in[7:0]=0010_0010 の個々のビットと有効領域信号m1=0000_0011の個々のビットをそれぞれ論理積をとって無効データ領域の信号をマスクし、エンコーダ回路４４に信号m3[7:0]=0000_0010 を出力する。エンコーダ回路４４は、入力された信号m3[7:0] のバイナリ・エンコードを実行し、信号out[2:0]=001を出力する。この「001」 は、入力信号in[7:0] の１ビット目に有効データ（検索一致信号）があった旨を知らせている。
【００７７】
一方、有効データ領域マスク回路４１は、入力信号in[7:0]=0010_0010 の個々のビットに対して有効領域信号m1=0000_0011の反転（1111_1100)との論理積をとって有効データ領域の信号をマスクし、出力信号m2[7:0]=0010_0000 をデータ保持回路４６に保持させる。選択回路４５は、データ保持回路６に保持された信号m4[7:0]=0010_0000 が入力されたときに選択し、有効データ領域検出回路４０、有効データ領域マスク回路４１及び無効データ領域マスク回路４３にそれぞれ出力する。
【００７８】
信号m4[7:0]=0010_0000 が入力された有効データ領域検出回路４０は、有効領域信号m1=0011_1111を生成して（５ビット目がＬＳＢ側の最初の有効データ）、無効データ領域マスク回路４３に出力し、無効データ領域マスク回路４３は、入力信号m4[7:0]=0010_0000 の個々のビットと有効領域信号m1=0011_1111の個々のビットをそれぞれ論理積をとって無効データ領域の信号をマスクし、エンコーダ回路４４に信号m3[7:0]=0000_0010 を出力する。エンコーダ回路４４は、入力された信号m3[7:0] のバイナリ・エンコードを実行し、信号out[2:0]=101を出力する。この場合は、入力信号in[7:0] の５ビット目に有効データ（検索一致信号）があった旨を知らせている。
【００７９】
一方、有効データ領域マスク回路４１は、選択回路４５の出力信号m4[7:0]=0010_0000 の個々のビットに対して有効領域信号m1=0011_1111の反転（1100_0000）との論理積をとって有効データ領域の信号をマスクし、出力信号m2[7:0]=0000_0000 をデータ保持回路４６出力する。本実施の形態では、入力信号in[7:0]=0010_0010 に含まれる有効表示のビット数が２であったため、有効データ領域マスク回路４１の出力信号m2[7:0]が「0000_0000」となった時点で演算を終了する。入力信号in[7:0] に含まれる有効表示のビット数がＮ個ある場合には、Ｎ回、前述の演算を繰り返すことにより、ＬＳＢ側からのアドレスのエンコード値を逐次、正確に出力することが可能になる。
【００８０】
以上のように実施の形態６によれば、実施例１、２に示した有効データ領域検出回路４０を利用し、かつ、小規模な回路の増加のみで、多重一致が発生した場合にもＬＳＢ側の一致結果のみを抽出し、正確なアドレス値のエンコード結果を逐次、全て出力することが可能となる。
【００８１】
【発明の効果】
以上のように本発明によれば、入力側に検索一致信号をそれぞれ伝送する複数の検索一致線を有し、出力側に検索一致線にそれぞれ対応した同じ本数の一致検出線を有し、１つの検索一致信号が何れかの検索一致線を介して入力されたときは、その検索一致線に対応した一致検出線を除く他の一致検出線上をLow レベルにし、２以上の検索一致信号が何れかの検索一致線を介してそれぞれ入力されたときは、全ての一致検出線上をLow レベルにする２つの一致検出回路と、一方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第１の検索一致検出回路と、他方の一致検出回路の各検索一致線に挿入され、この検索一致線の何れかに検索一致信号が流れたとき出力側をHighレベルからLow レベルに反転する第２の検索一致検出回路と、一方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと第２の検索一致検出回路の出力レベルとの論理積をとる複数の第１のＡＮＤ回路と、他方の一致検出回路の各一致検出線にそれぞれ挿入され、それぞれの一致検出線上のレベルと第１の検索一致検出回路の出力レベルとの論理積をとる複数の第２のＡＮＤ回路と、第１及び第２のＡＮＤ回路の出力側に設けられたＮＯＲ回路とからなる多重一致検出回路を用いているので、連想メモリ素子のエントリ数に依らずに全エントリの検索一致信号を同時に検出することが可能になり、このため、多重検索処理の高速化を図れ、特にエントリ数が多い程に効果は顕著となる。一致検出回路の構成は規則性が極めて高く、異なるエントリ数に対する回路では、既設計回路、既設計レイアウトからの流用や再利用が容易となり、特定の用途向けに異なるエントリ数の連想メモリ装置を開発する場合の開発期間を短縮できるという効果がある。
【図面の簡単な説明】
【図１】本発明の実施の形態１に係る連想メモリ装置の多重一致検出回路の構成を示す回路図である。
【図２】エントリ数４を８に変更したときの連想メモリ装置の多重一致検出回路の構成を示す回路図である。
【図３】本発明の実施の形態２に係る連想メモリ装置の多重一致検出回路の構成を示す回路図である。
【図４】本発明の実施の形態３に係る連想メモリ装置の４ビット用の多重一致検出回路の構成を示す論理回路図である。
【図５】実施の形態３における多重一致検出回路の真理値表を示す図である。
【図６】本発明の実施の形態４に係る連想メモリ装置の１６ビット用の多重一致検出回路の構成を示す論理回路図である。
【図７】本発明の実施の形態５に係る連想メモリ装置の多重一致検出回路の構成を示すブロック図である。
【図８】実施の形態５における有効データ領域検出回路の実施例を示す回路構成図である。
【図９】有効データ領域検出回路の他の実施例を示す回路構成図である。
【図１０】本発明の実施の形態６に係る連想メモリ装置の多重一致検出回路の構成を示すブロック図である。
【図１１】従来の連想メモリ装置の多重一致検出回路の構成を示す論理回路図である。
【符号の説明】
１  連想メモリ素子群、２，Ｈ１，Ｈ２  一致検出回路、３  ＮＯＲ回路、
２１，２２  多重検出入力回路、２３，３１〜３３  多重検出出力回路、
３０  基本回路、４０  有効データ領域検出回路、４１  有効データ領域マスク回路、４２  有効データ検出回路、４３  無効データ領域マスク回路、
４４  エンコーダ回路、４５  選択回路、４６  データ保持回路。
【図１】
0003861236.tif 000002
【図２】
0003861236.tif 000003
【図３】
0003861236.tif 000004
【図４】
0003861236.tif 000005
【図５】
0003861236.tif 000006
【図６】
0003861236.tif 000007
【図７】
0003861236.tif 000008
【図８】
0003861236.tif 000009
【図９】
0003861236.tif 000010
【図１０】
0003861236.tif 000011
【図１１】
0003861236.tif 000012