(57)【特許請求の範囲】
【請求項１】
半導体記憶装置であって、
行列上に配置された複数のメモリセルを含むメモリセルアレイと、
ワード線を活性化することによって、前記メモリセルからビット線に出力されるデータと、第１の検索データとを比較する第１の比較器と、
前記ワード線を活性化することによって、前記メモリセルから前記ビット線に出力されるデータと、第２の検索データとを比較する第２の比較器とを備え、
１つのワード線の活性化によってビット線に出力されるデータが前記第１の比較器および第２の比較器の両方に入力され、
前記半導体記憶装置は、さらに、
ロウアドレスを順次生成するアドレス生成器と、
前記生成されたロウアドレスに従って、前記メモリセルアレイ内のいずれかのワード線を活性化するロウデコーダと、
前記アドレス生成器と接続され、前記第１の比較器で一致すると判定されたときに、ロウアドレスをラッチする第１のプライオリティエンコーダと、
前記アドレス生成器と接続され、前記第２の比較器で一致すると判定されたときのロウアドレスをラッチする第２のプライオリティエンコーダとを備え、
前記第１および第２のプライオリティエンコーダは、一致すると判定されたときのロウアドレスが複数個ある場合に、優先度の高い方のロウアドレスをラッチし、
前記アドレス生成器は、小さな方から順番にロウアドレスを循環的に生成し、
前記第１および第２のプライオリティエンコーダは、一致すると判定されたときのロウアドレスが複数個ある場合に、値の小さなロウアドレスをラッチし、
前記第２のプライオリティエンコーダは、前記第２の比較器から出力される判定信号に応じてラッチ信号を生成し、先頭のアドレスが入力されたときに前記ラッチ信号をリセットする第１のラッチ回路と、前記アドレス生成器によって生成されたロウアドレスを受け、クロック端子に供給される前記ラッチ信号に応じて前記ロウアドレスをラッチし一致アドレスとして出力する第２のラッチ回路とを備える半導体記憶装置。
【請求項２】
前記半導体記憶装置は、さらに、
最初にサーチコマンドの入力に応じて、前記アドレス生成器に、小さな方から順番に順次ロウアドレスを生成させ、最大のロウアドレスが生成される前に、次のサーチコマンドが入力された場合には、前記アドレス生成器に、次に第Ｋ行を生成させるときには、前記
アドレス生成器に、最大のロウアドレスが生成された後、さらに、先頭のロウアドレスから第（Ｋ−１）番目のロウアドレスまでの１または複数のロウアドレスを順次生成させる、請求項１記載の半導体記憶装置。
【請求項３】
行列状に配置された複数のメモリセルを含むメモリセルアレイと、
小さな方から順番にロウアドレスを循環的に順次生成するアドレス生成器と、
前記生成されたロウアドレスにしたがって、前記メモリセルアレイ内のいずれかのワード線を活性化するロウデコーダと、
前記ワード線を活性化することによって、前記メモリセルからビット線に出力されるデータと、第１の検索データとを比較する第１の比較器と、
前記ワード線を活性化することによって、前記メモリセルから前記ビット線に出力されるデータと、第２の検索データとを比較する第２の比較器と、
前記アドレス生成器と接続され、前記第１の比較器で一致すると判定されたときに、ロウアドレスをラッチする第１のプライオリティエンコーダと、
前記アドレス生成器と接続され、前記第２の比較器で一致すると判定されたときに、ロウアドレスをラッチする第２のプライオリティエンコーダと、を備え、
前記第１および第２のプライオリティエンコーダは、一致すると判定されたときのロウアドレスが複数個ある場合に、値の小さなロウアドレスをラッチするものであって、
前記第２のプライオリティエンコーダは、
前記第２の比較器から出力される判定信号を受けラッチ信号を生成するとともに先頭のアドレスが入力されたときにリセットされる第１のラッチ回路と、
前記アドレス生成器によって生成されたロウアドレスを受け、クロック端子に供給された前記ラッチ信号に応じて前記ロウアドレスをラッチし一致アドレスとして出力する第２のラッチ回路と、
を有する半導体記憶装置。
【請求項４】
前記第２のプライオリティエンコーダは、サーチを開始するためのサーチ制御信号を受け、前記サーチ制御信号が活性化されたときに前記第１のラッチ回路をリセットする、請求項３記載の半導体記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体記憶装置に関し、特にサーチ機能を有する半導体記憶装置に関する。
【背景技術】
【０００２】
従来から、サーチ機能を有する半導体記憶装置が知られている。たとえば、特許文献１に記載されている半導体記憶装置では、データ検索が実行される場合は、ＣＰＵ等から入力された検索キー・データが検索キー・データ保持レジスタに保持され、データ一致検出部において、検索キー・データ保持レジスタに保持された検索キー・データと連想メモリに格納されているデータとが照合され、一致する全アドレスが検出される。次に、プライオリティエンコーダにおいて、データ一致検出部にて検出された全アドレスから最も優先度の高いアドレスが選択され、アドレス・セレクタ及びアドレス・エンコーダに対して出力される（段落［００２６］、［００２７］を参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−４８５７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１記載の装置では、あるデータの検索を実行中に、次のデータの検索が指示された場合には、実行中の検索が終了してからでないと、次のデータの検索が実行できない。
【０００５】
それゆえに、本発明の目的は、あるデータの検索を実行中に、次のデータの検索が実行できる半導体記憶装置を提供することである。
【課題を解決するための手段】
【０００６】
本発明の一実施形態の半導体記憶装置は、行列上に配置された複数のメモリセルを含むメモリセルアレイと、ワード線を活性化することによって、メモリセルからビット線に出力されるデータと、第１の検索データとを比較する第１の比較器と、ワード線を活性化することによって、メモリセルからビット線に出力されるデータと、第２の検索データとを比較する第２の比較器と、１つのワード線の活性化によってビット線に出力されるデータが第１の比較器および第２の比較器の両方に同時に入力される。
【発明の効果】
【０００７】
本発明の一実施形態の半導体記憶装置によれば、データの検索を実行中に、次のデータの検索が実行できる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態の半導体装置の構成を表わす図である。
【図２】第１の実施形態のメモリセルアレイの構成を表わす図である。
【図３】（ａ）は、図１の第１のサーチデータレジスタに格納されるサーチデータの例を表わす図である。（ｂ）は、図１の第２のサーチデータレジスタに格納されるサーチデータの例を表わす図である。
【図４】図１の第１の比較器の構成を表わす図である。
【図５】図１の第２の比較器の構成を表わす図である。
【図６】図１の第１のプライオリティエンコーダの構成を表わす図である。
【図７】図１の第２のプライオリティエンコーダの構成を表わす図である。
【図８】第１の実施形態の半導体装置の動作を表わすためのタイミング図である。
【図９】第２の実施形態におけるメモリセルアレイに格納されるデータと、そのアドレスを説明するための図である。
【図１０】第２の実施形態におけるメモリセルアレイに格納されるデータと、そのアドレスを説明するための図である。
【図１１】第２の実施形態の半導体装置の構成を表わす図である。
【図１２】図１１の多ビット論理積回路の構成を表わす図である。
【図１３】第３の実施形態の階層化された分割逆テーブルを説明するための図である。
【図１４】第３の実施形態の半導体装置の構成を表わす図である。
【図１５】第４の実施形態の階層化された分割逆テーブルを説明するための図である。
【図１６】第４の実施形態の半導体装置の構成を表わす図である。
【図１７】オリジナルの検索方式と、第２〜第４の検索方式でのテーブルを記憶する容量について説明するための図である。
【図１８】オリジナルの検索方式と、第２〜第４の実施形態の検索方式でのテーブルを記憶する容量について説明するための図である。
【図１９】第５の実施形態の半導体装置の構成を表わす図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面を参照して説明する。
［第１の実施形態］
図１は、第１の実施形態の半導体装置の構成を表わす図である。
【００１０】
図１を参照して、この半導体装置１は、半導体記憶装置２と、ＣＰＵ１５とからなる。半導体記憶装置２は、メモリセルアレイ３と、ロウデコーダ４と、センスアンプ群５と、第１のサーチデータレジスタ６と、第２のサーチデータレジスタ１３と、サーチ制御部７と、アドレス生成器８と、第１の比較器９と、第２の比較器１０と、第１のプライオリティエンコーダ１１と、第２のプライオリティエンコーダ１２とを備える。
【００１１】
ＣＰＵ１５は、半導体記憶装置２に対して、サーチコマンドＳＣ、サーチデータＳＤＡ，ＳＤＢを与える。また、ＣＰＵ１５は、半導体記憶装置２から、サーチデータＳＤＡ，ＳＤＢが格納される行を表わすアドレスＨＡＤＡ，ＨＡＤＢを受ける。
【００１２】
メモリセルアレイ３は、行列状に配置された複数個のＳＲＡＭセルを含む。
（メモリセルアレイ３）
図２は、第１の実施形態のメモリセルアレイ３の構成を表わす図である。
【００１３】
このメモリセルアレイ３は、行方向にＭ個、列方向にＮ個の行列状に配置されたメモリセルＭＣ（ｉ，ｊ）（ｉ＝１〜Ｍ、ｊ＝１〜Ｎ）を備える。
【００１４】
第ｊ列（ｊ＝１〜Ｎ）のＭ個のメモリセルＭＣ（ｉ，ｊ）（ｉ＝１〜Ｍ）は、ビット線対ＢＬ［ｊ］，／ＢＬ［ｊ］と接続する。第ｉ行（ｉ＝１〜Ｍ）のＮ個のメモリセルＭＣ（ｉ，ｊ）（ｊ＝１〜Ｎ）は、ワード線ＷＬ［ｉ］と接続する。
【００１５】
ロウデコーダ４によって、ワード線ＷＬ［ｉ］が活性化されると、第ｉ行のＮ個のメモリセルＭＣ（ｉ，ｊ）（ｊ＝１〜Ｎ）の格納値がビット線ＢＬ［ｊ］に出力され、第ｉ行のＮ個のメモリセルＭＣ（ｉ，ｊ）（ｊ＝１〜Ｎ）の格納値の相補値がビット線／ＢＬ［ｊ］に出力される。
【００１６】
センスアンプ群５は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、対応の列のビット線対の電圧を増幅して、第１の比較器９および第２の比較器１０へ出力する。
【００１７】
第１のサーチデータレジスタ６および第２のサーチデータレジスタ１３はそれぞれ、外部から入力されるＮビットのサーチデータＳＤＡ、ＳＤＢを蓄積する。
【００１８】
図３（ａ）は、図１の第１のサーチデータレジスタ６に格納されるサーチデータの例を表わす図である。
【００１９】
図３（ａ）を参照して、第１のサーチデータレジスタ６に格納される第１のＮビットのサーチデータ（ａ１，ａ２，・・・，ａＮ）は、Ｎ本の第１のサーチデータ線対ＳＬＡ［１］，／ＳＬＡ［１］〜ＳＬＡ［Ｎ］，／ＳＬＡ［Ｎ］を通じて、第１の比較器９へ出力される。ここで、第１のサーチデータの第ｉビット目の値がＳＬＡ［ｉ］に与えられ、第１のサーチデータの第ｉビット目の値の相補値が／ＳＬＡ［ｉ］に与えられる。
【００２０】
図３（ｂ）は、図１の第２のサーチデータレジスタ１３に格納されるサーチデータの例を表わす図である。
【００２１】
第２のサーチデータレジスタ１３に格納される第２のＮビットのサーチデータ（ｂ１，ｂ２，・・・，ｂＮ）は、Ｎ本の第２のサーチデータ線対ＳＬＢ［１］，／ＳＬＢ［１］〜ＳＬＢ［Ｎ］，／ＳＬＢ［Ｎ］を通じて、第２の比較器１０へ出力される。ここで、第２のサーチデータの第ｉビット目の値がＳＬＢ［ｉ］に与えられ、第２のサーチデータの第ｉビット目の値の相補値が／ＳＬＢ［ｉ］に与えられる。
【００２２】
サーチ制御部７は、外部からサーチコマンドＳＣが入力されると、第１のサーチまたは第２のサーチを開始する。すなわち、サーチ制御部７は、最初のサーチコマンドＳＣの入力に応じて、第１のサーチ制御信号ＳＲＡを「Ｈ」レベルに活性化して第１のサーチを開始する。サーチ制御部７は、第１のサーチ制御信号ＳＲＡを第１のプライオリティエンコーダ１１へ出力する。サーチ制御部７は、第１のサーチ制御信号ＳＲＡを活性化した後、アドレス生成器８に対して、第１のサーチのために第１行〜第Ｍ行を１行ずつ順番に指定する。また、サーチ制御部７は、第１行〜第Ｍ行の各行の指定と同期して、センスアンプ制御信号ＳＡを「Ｈ」レベルに活性化させる。サーチ制御部７は、第Ｍ行の指定の後、第１のプライオリティエンコーダ１１から出力される一致アドレスＨＡＤＢを外部に出力する。
【００２３】
サーチ制御部７は、２番目のサーチコマンドＳＣの入力に応じて、第２のサーチ制御信号ＳＲＢを「Ｈ」レベルに活性化して第２のサーチを開始する。サーチ制御部７は、第２のサーチ制御信号ＳＲＢを第２のプライオリティエンコーダ１２へ出力する。また、サーチ制御部７は、第２のサーチ制御信号ＳＲＢを活性化したときに、アドレス生成器８に対して、次に第１のサーチおよび第２のサーチのために第Ｋ行を指定するときには、第Ｍ行の指定の後、さらに、第２のサーチのために第１行〜第（Ｋ−１）行を１行ずつ順番に指定する。これによって、第２のサーチのために、メモリセルからデータを読出す範囲を必要十分な範囲に限定することができ、無用な電力消費を回避することができる。サーチ制御部７は、第１行〜第（Ｋ−１）行の各行の指定と同期して、センスアンプ制御信号ＳＡを「Ｈ」レベルに活性化させる。サーチ制御部７は、第（Ｋ−１）行の指定の後、第２のプライオリティエンコーダ１２から出力される一致アドレスＨＡＤＢを外部に出力する。
【００２４】
アドレス生成器８は、サーチ制御部７から指定された行のロウアドレスＲＡを生成して、ロウデコーダ４、第１のプライオリティエンコーダ１１および第２のプライオリティエンコーダ１２へ出力する。アドレス生成器８は、第１ロウ信号ＡＤＤ１を第１のプライオリティエンコーダ１１および第２のプライオリティエンコーダ１２へ出力する。アドレス生成器８は、生成したロウアドレスＲＡが第１行のロウアドレスの場合には、第１のプライオリティエンコーダ１１および第２のプライオリティエンコーダ１２へ出力する第１ロウ信号ＡＤＤ１を「Ｈ」レベルに活性化する。
【００２５】
ロウデコーダ４は、アドレス生成器８から送られるロウアドレスＲＡに応じたワード線ＷＬを活性化する。
【００２６】
（比較器）
図４は、図１の第１の比較器９の構成を表わす図である。
【００２７】
図４を参照して、第１の比較器９は、２Ｎ個の反一致回路２０Ａ＿ｉ（１），２０Ａ＿ｉ（２）（ｉ＝１〜Ｎ）と、１個の論理和回路２１Ａとを備える。
【００２８】
反一致回路２０Ａ＿ｉ（１）は、ビット線ＢＬ［ｉ］と、第１のサーチデータ線ＳＬＡ［ｉ］の値が一致するときには、「Ｌ」レベルを出力し、不一致のときには、「Ｈ」レベルを出力する。
【００２９】
反一致回路２０Ａ＿ｉ（２）は、ビット線／ＢＬ［ｉ］と、第１のサーチデータ線／ＳＬＡ［ｉ］の値が一致するときには、「Ｌ」レベルを出力し、不一致のときには、「Ｈ」レベルを出力する。
【００３０】
論理和回路２１Ａは、２Ｎ個の反一致回路２０Ａ＿ｉ（１），２０Ａ＿ｉ（２）（ｉ＝１〜Ｎ）の出力の論理和を検索判定信号ＭＡＴＡとして出力する。すなわち、検索判定信号ＭＡＴＡは、Ｎビットのメモリセルの格納値とＮビットの第１のサーチデータが一致している場合に、「Ｌ」レベルとなり、いずれかのビットで不一致がある場合には、「Ｈ」レベルとなる。
【００３１】
図５は、図１の第２の比較器１０の構成を表わす図である。
図５を参照して、第２の比較器１０は、２Ｎ個の反一致回路２０Ｂ＿ｉ（１），２０Ｂ＿ｉ（２）（ｉ＝１〜Ｎ）と、１個の論理和回路２１Ｂとを備える。
【００３２】
反一致回路２０Ｂ＿ｉ（１）は、ビット線ＢＬ［ｉ］と、第２のサーチデータ線ＳＬＢ［ｉ］の値が一致するときには、「Ｌ」レベルを出力し、不一致のときには、「Ｈ」レベルを出力する。
【００３３】
反一致回路２０Ｂ＿ｉ（２）は、ビット線／ＢＬ［ｉ］と、第２のサーチデータ線／ＳＬＢ［ｉ］の値が一致するときには、「Ｌ」レベルを出力し、不一致のときには、「Ｈ」レベルを出力する。
【００３４】
論理和回路２１Ｂは、２Ｎ個の反一致回路２０Ｂ＿ｉ（１），２０Ｂ＿ｉ（２）（ｉ＝１〜Ｎ）の出力の論理和を検索判定信号ＭＡＴＢとして出力する。すなわち、検索判定信号ＭＡＴＢは、Ｎビットのメモリセルの格納値とＮビットの第２のサーチデータが一致している場合に、「Ｌ」レベルとなり、いずれかのビットで不一致がある場合には、「Ｈ」レベルとなる。
【００３５】
（プライオリティエンコーダ）
図６は、図１の第１のプライオリティエンコーダ１１の構成を表わす図である。
【００３６】
図６を参照して、第１のプライオリティエンコーダ１１は、論理和回路２２と、第１のラッチ回路２３と、第２のラッチ回路２４とを備える。
【００３７】
論理和回路２２は、第１のサーチ制御信号ＳＲＡと、第１ロウ信号ＡＤＤ１とを受ける。論理和回路２２は、第１のサーチ制御信号ＳＲＡが「Ｈ」レベルに活性化されるか、または第１ロウ信号ＡＤＤ１が「Ｈ」レベルに活性化したときに、「Ｈ」レベルの信号を出力して、第１のラッチ回路２３をリセットする。
【００３８】
第１のラッチ回路２３は、セット端子Ｓに「Ｈ」レベルを受け、クロック端子Ｃに検索判定信号ＭＡＴＡを受けて、リセット端子Ｒに論理和回路２２の出力を受けて、出力端子Ｏからラッチ信号ＬＴ１を出力する。
【００３９】
第２のラッチ回路２４は、セット端子ＳにロウアドレスＲＡを受けて、クロック端子Ｃに第１のラッチ回路２３の出力を受けて、出力端子Ｏから一致アドレスＨＡＤＡを出力する。
【００４０】
第１のラッチ回路２３および第２のラッチ回路２４は、最初にヒットしたときのロウアドレスＲＡをラッチして一致アドレスＨＡＤＡとして出力する。ただし、第１のサーチ制御信号ＳＲＡが「Ｈ」レベルに活性化されるか、または、第１ロウ信号ＡＤＤ１が「Ｈ」レベルに活性化したときに、ラッチしたロウアドレスをリセットして、次にヒットしたときのロウアドレスＲＡをラッチして一致アドレスＨＡＤＡとして出力する。
【００４１】
図７は、図１の第２のプライオリティエンコーダ１２の構成を表わす図である。
図７を参照して、第２のプライオリティエンコーダ１２は、論理和回路２５と、第１のラッチ回路２６と、第２のラッチ回路２７とを備える。
【００４２】
論理和回路２５は、第２のサーチ制御信号ＳＲＢと、第１ロウ信号ＡＤＤ１とを受ける。論理和回路２５は、第２のサーチ制御信号ＳＲＢが「Ｈ」レベルに活性化されるか、または、第１ロウ信号ＡＤＤ１が「Ｈ」レベルに活性化したときに、「Ｈ」レベルの信号を出力して、第１のラッチ回路２６をリセットする。
【００４３】
第１のラッチ回路２６は、セット端子Ｓに「Ｈ」レベルを受け、クロック端子Ｃに検索判定信号ＭＡＴＢを受けて、リセット端子Ｒに論理和回路２５の出力を受けて、出力端子Ｏからラッチ信号ＬＴ２を出力する。
【００４４】
第２のラッチ回路２７は、セット端子ＳにロウアドレスＲＡを受けて、クロック端子Ｃに第１のラッチ回路２６の出力を受けて、出力端子Ｏから一致アドレスＨＡＤＢを出力する。
【００４５】
第１のラッチ回路２６および第２のラッチ回路２７は、最初にヒットしたときのロウアドレスＲＡをラッチして一致アドレスＨＡＤＢとして出力する。ただし、第２のサーチ制御信号ＳＲＢが「Ｈ」レベルに活性化されるか、または、第１ロウ信号ＡＤＤ１が「Ｈ」レベルに活性化したときに、ラッチしたロウアドレスをリセットして、次にヒットしたときのロウアドレスＲＡをラッチして一致アドレスＨＡＤＢとして出力する。
【００４６】
以上のような、第１のプライオリティエンコーダ１１および第２のプライオリティエンコーダ１２を備えることによって、複数のロウアドレスにおいて、ヒットしたときに、優先度の高いロウアドレス（小さな値のロウアドレス）をヒットしたアドレスとして出力することができる。また、第１のプライオリティエンコーダ１１および第２のプライオリティエンコーダ１２内に、ヒットによってラッチしたロウアドレスを先頭のアドレスに戻ったときに、リセットする機能を持たせることによって、第２のサーチおよび第１のサーチをロウアドレスの先頭から実行しなくてもよいようにできる。
【００４７】
なお、第１のサーチを必ず先頭のロウアドレスから実行する場合には、第１のプライオリティエンコーダ１１は、このようなリセット機能を有さないものであってもよい。
【００４８】
（動作）
図８は、第１の実施形態の半導体装置の動作を表わすためのタイミング図である。
【００４９】
図８を参照して、サーチ制御部７は、最初のサーチコマンドＳＣの入力（（１）に示す）に応じて、第１のサーチ制御信号ＳＲＡを「Ｈ」レベルに活性化して第１のサーチを開始する。また、第１のサーチデータレジスタ６には、第１のＮビットのサーチデータ（ａ１，ａ２，・・・，ａＮ）が格納される。
【００５０】
サーチ制御部７は、アドレス生成器８に対して、第１行〜第Ｍ行を１行ずつ順番に指定する。アドレス生成器８は、指定されたロウアドレスを順次生成し、ロウデコーダ４は、ワード線ＷＬ［１］〜ＷＬ［Ｍ］を順次活性化する。また、サーチ制御部７は、第１行〜第Ｍ行の各行の指定と同期して、センスアンプ制御信号ＳＡを「Ｈ」レベルに活性化させる。
【００５１】
一方、サーチ制御部７は、２番目のサーチコマンドＳＣの入力（（２）に示す）に応じて、第２のサーチ制御信号ＳＲＢを「Ｈ」レベルに活性化して第２のサーチを開始する。また、第２のサーチデータレジスタ１３には、第２のＮビットのサーチデータ（ｂ１，ｂ２，・・・，ｂＮ）が格納される。
【００５２】
また、サーチ制御部７は、第２のサーチ制御信号ＳＲＢを活性化したときに、次に、アドレス生成器８に対して、第１のサーチおよび第２のサーチのために、たとえば第１５行を指定するときには（（３）に示す）、第Ｍ行の指定の後、さらに、第２のサーチのために、第１行〜第１４行を１行ずつ順番に指定する。アドレス生成器８は、指定されたロウアドレスを順次生成し、ロウデコーダ４は、ワード線ＷＬ［１］〜ＷＬ［１４］を活性化する。また、サーチ制御部７は、第１行〜第１４行の各行の指定と同期して、センスアンプ制御信号ＳＡを「Ｈ」レベルに活性化させる。
【００５３】
ワード線ＷＬ［ｉ］（ｉ＝１〜Ｍ、１〜１４）の活性化に応じて、第ｉ行のメモリセルＭＣ（ｉ，ｊ）（ｊ＝１〜Ｎ）からデータがビット線対ＢＬ［ｊ］，／ＢＬ［ｊ］にデータが読み出される。センスアンプ群５の各センスアンプは、センスアンプ制御信号ＳＥによって活性化されて、接続されるビット線対のデータを増幅する。
【００５４】
ワード線ＷＬ［ｉ］（ｉ＝１〜Ｍ）の活性化に応じて、第１の比較器９は、Ｎ個のセンスアンプから出力されるビット線対ＢＬ［１］，／ＢＬ［１]〜ＢＬ［Ｎ］，／ＢＬ［Ｎ］のデータと第１のサーチデータ線対ＳＬＡ［１］，ＳＬＡ［１］〜ＳＬＡ［Ｎ］，／ＳＬＡ［Ｎ］のデータとを比較する。同様に、ワード線ＷＬ［ｉ］（ｉ＝１５〜Ｍ、１〜１４）の活性化に応じて、第２の比較器１０は、Ｎ個のセンスアンプから出力されるビット線対ＢＬ［１］，／ＢＬ［１]〜ＢＬ［Ｎ］，／ＢＬ［Ｎ］のデータと第２のサーチデータ線対ＳＬＢ［１］，ＳＬＢ［１］〜ＳＬＢ［Ｎ］，／ＳＬＢ［Ｎ］のデータとを比較する。
【００５５】
たとえば、第１０行のメモリセルＭＣ（１０，ｊ）（ｊ＝１〜Ｎ）のデータと第１のＮビットのサーチデータ（ａ１，ａ２，・・・，ａＮ）の値が一致し（（４）に示す）、かつ第２０行のメモリセルＭＣ（２０，ｊ）（ｊ＝１〜Ｎ）のデータと第１のＮビットのサーチデータ（ａ１，ａ２，・・・，ａＮ）の値が一致する（（５）に示す）ときには、第１のプライオリティエンコーダ１１は、最初の第１０行のロウアドレスＲＡをラッチし続ける（第２０行のロウアドレスはラッチしない）。
【００５６】
第Ｍ行の指定の後において、第１のプライオリティエンコーダ１１からは、ラッチしている第１０行のロウアドレスＲＡを示す一致アドレスＨＡＤＡが出力される。サーチ制御部７は、第Ｍ行の指定の後、第１のプライオリティエンコーダ１１から出力されている第１０行のロウアドレスＲＡを示す一致アドレスＨＡＤＡを外部に出力する。
【００５７】
たとえば、第３０行のメモリセルＭＣ（３０，ｊ）（ｊ＝１〜Ｎ）のデータと第２のＮビットのサーチデータ（ｂ１，ｂ２，・・・，ｂＮ）の値が一致し（（６）に示す）、かつ第２行のメモリセルＭＣ（２，ｊ）（ｊ＝１〜Ｎ）のデータと第２のＮビットのサーチデータ（ｂ１，ｂ２，・・・，ｂＮ）の値が一致する（（７）に示す）ときには、第２のプライオリティエンコーダ１２は、最初の第３０行のロウアドレスＲＡをラッチする。その後、ロウアドレスＲＡが第１行に戻ったときに、第２のプライオリティエンコーダ１２は、第１ロウ信号ＡＤＤ１によってラッチしたアドレスをリセットして、第２行のロウアドレスＲＡをラッチする。第１４行の指定の後において、第２のプライオリティエンコーダ１２からは、ラッチしている第２行のロウアドレスＲＡを示す一致アドレスＨＡＤＢが出力される。サーチ制御部７は、第１４行の指定の後、第２のプライオリティエンコーダ１２から出力されている第２行のロウアドレスＲＡを示す一致アドレスＨＡＤＢを外部に出力する。
【００５８】
（まとめ）
以上のように、第１の実施形態の半導体装置によれば、あるデータの検索を実行中に、次のデータの検索が実行できるので、あるデータの検索の終了後に、次のデータの検索を実行するよりも、メモリセルからデータを読出す回数を少なくできるので、低消費電力化を実現できる。
【００５９】
［第１の実施形態の変形例］
本発明は、２個の比較器および２個のプライオリティエンコーダを備えることとし、一部の期間、第１のサーチと第２のサーチを同時に実行することとしたが、Ｎ個の比較器およびＮ個のプライオリティエンコーダを備えることとして、一部の期間において、Ｎ個のサーチを同時に実行することとしてもよい。この場合、サーチ制御部は、第ｉ番目のサーチコマンドに応じて、第ｉ番目の検索データをｉ番目の比較器に与え、第Ｋ番目のロウアドレスが生成されたときに、Ｎ番目のサーチコマンドに応じて、Ｎ番目の検索データをＮ番目の比較器に与えたときには、最大のロウアドレスが生成された後、さらにアドレス生成器に、先頭のロウアドレスから第（Ｋ−１）番目のロウアドレスまでの１または複数のロウアドレスを順次生成させることにすればよい。
【００６０】
［第２の実施形態］
第１の実施形態では、外部からサーチデータが与えられ、メモリセルアレイ内に格納されたデータのうち外部から与えられたサーチデータと一致するアドレスを出力した。
【００６１】
これに対して、第２の実施形態では、第１の実施形態におけるメモリセルアレイのアドレスをメモリセルアレイのデータとして格納し、第１の実施形態におけるメモリセルアレイに格納されたデータを外部からアドレスとして与える。外部から与えられたアドレスは分割され、分割されたアドレスに対応するメモリセルアレイのデータを読出し、読出した結果を合成することによって、第１の実施形態と同様の検索が実行できる。第２の実施形態の検索方式を分割逆引き検索方式と呼ぶことにする。
【００６２】
（メモリセルアレイの構成と、記憶されるデータの例１）
図９は、第２の実施形態におけるメモリセルアレイに格納されるデータと、そのアドレスを説明するための図である。図９は、説明の便宜上、メモリセルアレイのサイズを実際よりも小さくして説明したものである。
【００６３】
図９（ａ）および（ｂ）は、第１の実施形態で示した方式で格納されるデータと、そのアドレスを説明するための図である。
【００６４】
図９（ａ）に示すように、このメモリセルアレイ４１は、（８）行×（４）列で構成されるオリジナルの検索テーブルを記憶する。つまり、このメモリセルアレイは、８エントリを含み、各エントリには、４ビットの値が格納される。
【００６５】
図９（ｂ）は、このメモリセルアレイ４１の各エントリに格納される４ビットの値の例を表わす。たとえば、エントリ番号（アドレス）が「００１」（＝１）のエントリには、データ「００１１」が格納される。
【００６６】
図９（ｃ）および（ｄ）は、図９（ａ）および（ｃ）を逆引き方式に変換したものである。
【００６７】
図９（ｃ）に示すように、このメモリセルアレイ４２は、（２4）行×（Ｌｏｇ2８）列で構成される。つまり、このメモリセルアレイ４２は、２4エントリを含み、各エントリには、Ｌｏｇ2８ビットの値が格納される。
【００６８】
図９（ｂ）では、アドレス「００１」にデータ「００１１」が格納されていたのに対して、図９（ｄ）では、この関係が逆転し、アドレス「００１１」にデータ「００１」が格納される。
【００６９】
図９（ｅ）および（ｆ）は、図９（ｃ）および（ｄ）のメモリセルアレイに格納されるデータの形式を変換したものである。
【００７０】
図９（ｅ）に示すように、このメモリセルアレイ４３は、（２4）行×（８）列で構成される逆テーブルを記憶する。つまり、このメモリセルアレイ４３は、２4エントリを含み、各エントリには、８ビットの値が格納される。
【００７１】
図９（ｄ）のデータの値「ｎ」は、図９（ｆ）では、最下位ビットから（ｎ＋１）ビットが「１」となり、その他のビットが「０」となる値に変換される。
【００７２】
たとえば、図９（ｄ）では、アドレス「００１１」にデータ「００１」が格納されていたのに対して、図９（ｆ）では、アドレス「００１１」にデータ「００００００１０」が格納される。
【００７３】
図９（ｇ）、（ｈ）、（ｉ）は、図９（ｅ）および（ｆ）をアドレス分割によって変換したものである。
【００７４】
図９（ｇ）に示すように、メモリセルアレイは、上位ビット用メモリセルアレイ４４と下位ビット用メモリセルアレイ４５に分割される。各メモリセルアレイは、（２2）行×（８）列で構成される分割逆引きテーブル（ＤＲＴ:Divisional Reverse Table）を記憶する。上位ビット用メモリセルアレイ４４は、逆テーブルを２個にアドレス分割したときの上位から第１番目のブロックに対応する上位ビット用の分割逆引きテーブルを記憶する。下位ビット用メモリセルアレイ４５は、逆テーブルを２個にアドレス分割したときの上位から第２番目のブロックに対応する下位ビット用の分割逆引きテーブルを記憶する。
【００７５】
図９（ｇ）の上位ビット用メモリセルアレイ４４には、図９（ｅ）の逆テーブルの上位２ビットで指定される複数のエントリのデータの論理和が格納される。
【００７６】
図９（ｇ）の下位ビット用メモリセルアレイ４５には、図９（ｅ）の逆テーブルの下位２ビットで指定される複数のエントリのデータの論理和が格納される。
【００７７】
外部から指定されたアドレスは、上位２ビットと下位２ビットに分割される。上位ビット用メモリセルアレイ４４からは、分割された上位２ビットで指定されるエントリのデータが読み出される。下位ビット用メモリセルアレイ４５からは、分割された下位２ビットで指定されるエントリのデータが読み出される。そして、２つのメモリセルアレイ４４，４５から読み出されたデータの論理積がとられる。この論理積の「１」の値が最下位ビットからｎ番目のときに、（ｎ−１）が外部指定されたアドレスに対応するデータとして出力される。
【００７８】
図９（ｈ）は、上位ビット用メモリセルアレイに格納されるデータを表わす。
たとえば、図９（ｈ）のアドレス「００」には、図９（ｆ）において、上位２ビットのアドレスが「００」であるアドレス「００００」と「００１０」と「００１１」に格納されるデータの論理和が格納される。すなわち、図９（ｆ）では、アドレス「００００」、「００１０」、「００１１」にはそれぞれ「０００１００００」、「０００００１００」、「００００００１０」が格納されるので、図９（ｈ）では、アドレス「００」に、これらの論理和の「０００１０１１０」が格納される。
【００７９】
図９（ｉ）は、下位ビット用メモリセルアレイに格納されるデータを表わす。
たとえば、図９（ｉ）のアドレス「１１」には、図９（ｆ）において、下位２ビットのアドレスが「１１」であるアドレス「００１１」と「０１１１」と「１０１１」と「１１１１に格納されるデータの論理和が格納される。すなわち、図９（ｆ）では、アドレス「００１１」と「０１１１」と「１０１１」と「１１１１」には、それぞれ、「００００００１０」、「０１００００００」、「００１０００００」、「００００１０００」が格納されるので、図９（ｉ）では、アドレス「１１」に、これらの論理和の「０１１０１０１０」が格納される。
【００８０】
外部からアドレス「０００１」が指定された場合に、上位ビット用メモリセルアレイ４４から上位２ビット「００」で指定されるエントリのデータ「０００１０１１０」が読み出され、下位ビット用メモリセルアレイ４５から下位２ビット「１１」で指定されるエントリのデータ「０１１０１０１０」が読み出される。そして、２つの読み出されたデータの論理積が「００００００１０」であり、「１」の位置が最下位ビットが２番目なので、「１」（＝「００１」）が出力される。
【００８１】
以上の説明を総括すると、図９（ａ）および（ｂ）の第１の実施形態の方式では、外部からサーチデータ「００１１」が与えられ、メモリセルアレイ内に格納されたデータのうち外部から与えられたサーチデータと一致するアドレス「００１」が出力された。これに対して、図９（ｇ）、（ｈ）および（ｉ）の第２の実施形態の方式では、外部からアドレス「００１１」が与えられ、このアドレスに対応するデータ「１」（＝「００１」）が出力される。これによって、第２の実施形態でも、第１の実施形態と同様の検索が実行できる。
【００８２】
（メモリセルアレイの構成と、記憶されるデータの例２）
図１０は、第２の実施形態におけるメモリセルアレイに格納されるデータと、そのアドレスを説明するための図である。
【００８３】
図１０（ａ）および（ｂ）は、第１の実施形態で示した方式で格納されるデータと、そのアドレスを表わす。図１０は、図９をより一般化したものである。
【００８４】
図１０（ａ）に示すように、このメモリセルアレイ４６は、（Ｌ）行×（Ｎ）列で構成されるオリジナルの検索テーブルを記憶する。つまり、このメモリセルアレイは、Ｌエントリを含み、各エントリには、Ｎビットの値が格納される。図１０（ｂ）は、このメモリセルアレイの各エントリに格納されるＮビットの値の例を表わす。
【００８５】
図１０（ｃ）および（ｄ）は、図１０（ａ）および（ｃ）を逆引き方式に変換したものである。
【００８６】
図１０（ｃ）に示すように、このメモリセルアレイ４７は、（２N）行×（Ｌｏｇ2Ｌ）列で構成される。
【００８７】
図１０（ｅ）および（ｆ）は、図１０（ｃ）および（ｄ）のメモリセルアレイに格納されるデータの形式を変換したものである。
【００８８】
図１０（ｅ）に示すように、このメモリセルアレイ４８は、（２4）行×（８）列で構成される逆テーブルを記憶する。図１０（ｄ）のデータの値「ｎ」は、図１０（ｆ）では、最下位ビットから（ｎ＋１）ビットが「１」となり、その他のビットが「０」となる値に変換される。
【００８９】
図１０（ｇ）、（ｈ）、（ｉ）、（ｊ）は、図１０（ｅ）および（ｆ）をアドレス分割によって変換したものである。
【００９０】
図１０（ｇ）に示すように、メモリセルアレイは、第１メモリセルアレイ４９＿１、第２メモリセルアレイ４９＿２、・・・、第Ｍメモリセルアレイ４９＿Ｎに分割される。各メモリセルアレイは、（２s）行×（Ｌ）列で構成される分割逆引きテーブルを記憶する。ここで、Ｓ×Ｍ＝Ｎである。第１メモリセルアレイ４９＿１は、逆テーブルをＭ個にアドレス分割したときの上位から第１番目のブロックに対応する分割逆引きテーブルを記憶する。第２メモリセルアレイ４９＿２は、逆テーブルをＭ個にアドレス分割したときの上位から第２番目のブロックに対応する分割逆引きテーブルを記憶する。第Ｍメモリセルアレイ４９＿Ｍは、逆テーブルをＭ個にアドレス分割したときの上位から第Ｍ番目のブロックに対応する分割逆引きテーブルを記憶する。
【００９１】
図１０（ｇ）の第１メモリセルアレイ４９＿１には、図１０（ｅ）の逆テーブルの最上位からＳ個のビットで指定されるＳ個のエントリのデータの論理和が格納される。図１０（ｇ）の第２メモリセルアレイ４９＿２には、図１０（ｅ）の逆テーブルの最上位から（Ｓ＋１）番目のビット〜最上位から２Ｓ番目のビットで指定されるＳ個のエントリのデータの論理和が格納される。図１０（ｇ）の第Ｍメモリセルアレイ４９＿Ｎには、図１０（ｅ）の逆テーブルの最下位からＳ個のビットで指定されるＳ個のエントリのデータの論理和が格納される。ここで、論理和をとる対象のエントリにデータがない場合はそのエントリの全ビットが０とみなすことによって、論理和が得られる。
【００９２】
外部から指定されたアドレスは、Ｓ個のビットずつに分割される。第１メモリセルアレイ４９＿１からは、分割された最上位からＳ個のビットで指定されるエントリのデータが読み出される。第２メモリセルアレイ４９＿２からは、分割された最上位から（Ｓ＋１）番目のビット〜最上位から２Ｓ番目のビットで指定されるエントリのデータが読み出される。第Ｍメモリセルアレイ４９＿Ｍからは、分割された最下位からＳ個のビットで指定されるエントリのデータが読み出される。そして、第１〜第Ｍメモリセルアレイから読み出されたデータの論理積がとられる。この論理積の「１」の最下位ビットからｎ番目のときに、（ｎ−１）が外部から指定されたアドレスに対応するデータとして出力される。
【００９３】
（構成）
図１１は、第２の実施形態の半導体装置の構成を表わす図である。
【００９４】
図１１を参照して、この半導体装置６２は、半導体記憶装置６１と、ＣＰＵ５７とからなる。
【００９５】
ＣＰＵ５７は、半導体記憶装置６１に対して、サーチコマンドＳＣとアドレスＡＤＤを与える。また、ＣＰＵ５７は、半導体記憶装置６１から、ＡＤＤに対応する記憶されているデータＲＤを受ける。
【００９６】
半導体記憶装置６１は、それぞれが、メモリセルアレイと、ロウデコーダと、センスアンプ群を有するＭ個のブロックを有する。つまり、半導体記憶装置６１は、第１メモリセルアレイ４９＿１、第２メモリセルアレイ４９＿２、・・・、第Ｍメモリセルアレイ４９＿Ｍと、第１ロウデコーダ５１＿１、第２ロウデコーダ５１＿２、・・・、第Ｍロウデコーダ５１＿Ｍと、第１センスアンプ群５２＿１、第２センスアンプ群５２＿２、・・・、第Ｍセンスアンプ群５２＿Ｍとを有する。
【００９７】
さらに、この半導体記憶装置６１は、アドレス分割器５３と、多ビット論理積回路５４と、ビット位置判定部５５と、サーチ制御部５６とを備える。
【００９８】
第１メモリセルアレイ４９＿１は、図１０（ｇ）に示したものと同様であり、行列上に配置された複数個のＳＲＡＭセルを有する。第１メモリセルアレイ４９＿１は、逆テーブルをＭ個にアドレス分割したときの第１番目のブロックに対応する分割逆引きテーブルを記憶する。第１メモリセルアレイ４９＿１は、たとえば、図１０（ｈ）に示すようなデータを記憶する。
【００９９】
第２メモリセルアレイ４９＿２は、図１０（ｇ）に示したものと同様であり、行列上に配置された複数個のＳＲＡＭセルを有する。第２メモリセルアレイ４９＿２は、逆テーブルをＭ個にアドレス分割したときの第２番目のブロックに対応する分割逆引きテーブルを記憶する。第２メモリセルアレイ４９＿２は、たとえば、図１０（ｉ）に示すようなデータを記憶する。
【０１００】
第Ｍメモリセルアレイ４９＿Ｍは、図１０（ｇ）に示したものと同様であり、行列上に配置された複数個のＳＲＡＭセルを有する。第Ｍメモリセルアレイ４９＿Ｍは、逆テーブルをＭ個にアドレス分割したときの第Ｍ番目のブロックに対応する分割逆引きテーブルを記憶する。
【０１０１】
アドレス分割器５３は、外部から指定されたＮビットのアドレスＡＤＤを、Ｓ個のビットずつに分割する。アドレス分割器５３は、分割された最上位からＳ個のビットからなるアドレスＡＤＤ（１）を第１ロウデコーダ５１＿１に出力する。アドレス分割器５３は、分割された最上位から（Ｓ＋１）番目のビット〜最上位から２Ｓ番目のビットからなるアドレスＡＤＤ（２）を第２ロウデコーダ５１＿２に出力する。アドレス分割器５３は、分割された最下位からＳ個のビットからなるアドレスＡＤＤ（Ｍ）を第Ｍロウデコーダ５１＿Ｍに出力する。
【０１０２】
第１ロウデコーダ５１＿１は、アドレス分割器５３から出力されるＡＤＤ（１）に応じた第１メモリセルアレイ４９＿１内のワード線ＷＬを活性化する。第２ロウデコーダ５１＿２は、アドレス分割器５３から出力されるＡＤＤ（２）に応じた第２メモリセルアレイ４９＿２内のワード線ＷＬを活性化する。第Ｍロウデコーダ５１＿Ｍは、アドレス分割器５３から出力されるＡＤＤ（Ｍ）に応じた第Ｍメモリセルアレイ４９＿Ｍ内のワード線ＷＬを活性化する。
【０１０３】
第１センスアンプ群５２＿１は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、第１メモリセルアレイ４９＿１の対応の列のビット線対の電圧を増幅して出力する。第２センスアンプ群５２＿２は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、第２メモリセルアレイ４９＿２の対応の列のビット線対の電圧を増幅して出力する。第Ｍセンスアンプ群５２＿Ｍは、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、第Ｍメモリセルアレイ４９＿Ｎの対応の列のビット線対の電圧を増幅して出力する。
【０１０４】
図１２は、図１１の多ビット論理積回路の構成を表わす図である。
図１２を参照して、多ビット論理積回路５４は、Ｌ個の論理積回路６０＿１〜６０＿Ｌとビット結合器７１を備える。
【０１０５】
論理積回路６０＿ｉは、第１メモリセルアレイ４９＿１の第ｉ列のビット線ＢＬ［ｉ］（１）のデータ、第２メモリセルアレイ４９＿２の第ｉ列のビット線ＢＬ［ｉ］（２）のデータ、・・・、第Ｍメモリセルアレイ４９＿Ｍの第ｉ列のビット線ＢＬ［ｉ］（Ｍ）のデータの論理積ｃ（ｉ）を出力する。
【０１０６】
ビット位置判定部５５は、多ビット論理積回路５４から出力されるＬ個のデータＣ（１）〜Ｃ（Ｌ）のうち、値が「１」となるものがｃ（ｎ）のときに、（ｎ−１）を外部から指定されたアドレスＡＤＤに対応するデータＲＤとして出力する。
【０１０７】
サーチ制御部５６は、外部からサーチコマンドＳＣが実行されると、外部からのアドレスＡＤＤに対応するデータのサーチを開始する。また、サーチ制御部５６は、ビット位置判定部５５から出力されるデータＲＤを外部に出力する。
【０１０８】
（まとめ）
以上のように、第２の実施形態によれば、第１の実施形態のようにすべてのデータを読み出して比較する必要がなく、アドレスに相当するデータを読み出すことによって、読み出されたデータを検索結果とすることができるので、低消費電力化を図ることができる。
【０１０９】
［第３の実施形態］
第２の実施形態では、検索性能とテーブル容量の間にトレード・オフの関係があり、高い検索性能を実現するためには従来の検索テーブルと比べて、何十倍〜何百倍という大きなメモリ容量を必要とする。
【０１１０】
第３の実施形態は、第２の実施形態の方法を改良し、ポインタを使って間接的に分割具逆引きテーブルを参照する。間接的に分割逆引きテーブルを参照することによって、メモリの使用効率を上げることができるので、メモリ容量を節約することができる。
【０１１１】
第３の実施形態では、第２の実施形態の分割逆引きテーブルのエントリを必要なエントリのみに絞ったものを用いる。そして、この新たな分割逆引きテーブルを下位階層とし、上位階層のアドレステーブル（ＡＴ:Address Table）が下位階層の分割逆引きテーブルへのエントリへのポインタ（アドレス）を格納する。
【０１１２】
（メモリセルアレイの構成と、記憶されるデータの例）
図１３は、第３の実施形態の階層化された分割逆テーブルを説明するための図である。図１３は、説明の便宜上、メモリセルアレイのサイズを実際よりも小さくして説明したものである。
【０１１３】
図１３（ａ）は、オリジナルの検索テーブルを示す図である。すなわち、図１３（ａ）は、第１の実施形態で示した方式で格納されるデータと、そのアドレスを表わす。これは、第２の実施形態の例では、図９（ｂ）に対応する。
【０１１４】
図１３（ａ）に示すように、このメモリセルアレイは、（４）行×（８）列で構成される。つまり、このメモリセルアレイは、４エントリを含み、各エントリには、８ビットの値が格納される。たとえば、エントリ番号（アドレス）が「０ｘ０」（＝１）のエントリには、データ「２５５」が格納される。
【０１１５】
図１３（ｂ）は、第２の実施形態による分割逆引きテーブルを表わす図である。すなわち、図１３（ｂ）は、図１３（ａ）を逆引き方式に変換したものである。これは、第２の実施形態の例では、図９（ｈ）および（ｉ）に相当する。
【０１１６】
図１３（ｂ）に示すように、メモリセルアレイは、上位ビット用メモリセルアレイ（上位ビット用の分割逆引きテーブル）と下位ビット用メモリセルアレイ（下位ビット用の分割逆引きテーブル）に分割され、各メモリセルアレイは、（１６）行×（４）列、すなわち１６ビット×４（＝６４ビット）で構成される。したがって、図１３（ｂ）では、メモリセルアレイの容量は、６４ビット×２＝１２８ビットとなる。
【０１１７】
ところで、（１）に示すように、各６４ビットの分割逆引きテーブルに着目すると、オリジナルの検索テーブルが４エントリであるから、「１」が立つビットは、高々４ビットであり、残りの６０ビットは「０」のままである。これを分割逆引きテーブルのエントリで考えると、以下のようになる。すなわち、各分割逆引きテーブルは１６エントリを有するが、有効なエントリは高々４エントリであり、残りの１２エントリはオール「０」の無効なデータを保持している。
【０１１８】
第３の実施形態では、ポインタを使った間接参照を導入することによって、上記のような無駄なエントリを削除する。
【０１１９】
図１３（ｃ）は、第３の実施形態による階層的分割逆引きを説明するための図である。
図１３（ｃ）に示すように、上位階層のアドレステーブルによって、下位階層の分割逆引きテーブルが参照される。
【０１２０】
各分割逆引きテーブルのエントリは、「１」を含む有効なエントリの最大数である４個のみである。アドレステーブルには、外部から与えられるアドレス（サーチキー）から、分割逆引きテーブルのエントリを参照するためのポインタが格納される。このアドレステーブルは、さらに、各アドレスに分割逆引きテーブルのエントリへのポインタが格納されているかどうかを表わす有効フラグを格納する。有効フラグＶａｌｉｄが「１」のときには、分割逆引きテーブルのエントリへのポインタが格納されていることを示し、有効フラグＶａｌｉｄが「１」のときには、無効なデータが格納されていることを示す。
【０１２１】
このようにして、分割逆引きテーブルに無効なデータを格納しないようにすることによって、メモリ容量を大幅に圧縮することができる。
【０１２２】
たとえば、サーチキーとして「００００００００」が与えられた場合の検索手順について以下に説明する。
【０１２３】
上位ビット用のアドレステーブルにおいて、サーチキーの上位ビット「００００」のアドレス位置の有効フラグが「１」（有効）であるので、そのアドレス位置のデータ「０ｘ０」がセレクタ（判定部）ＳＬＡを介して上位ビット用の分割逆引きテーブルへのポインタとして読出される。
【０１２４】
上位ビット用の分割逆引きテーブルにおいて、「０ｘ０」のアドレス位置のデータ「１０」が読み出される。
【０１２５】
また、下位ビット用のアドレステーブルにおいて、サーチキーの下位ビット「００００」のアドレス位置の有効フラグが「１」（有効）であるので、そのアドレス位置のデータ「０ｘ１」がセレクタ（判定部）ＳＬＢを介して分割逆引きテーブルへのポインタとして読出される。
【０１２６】
下位ビット用の分割逆引きテーブルにおいて、「０ｘ１」のアドレス位置のデータ「１０１０」が読み出される。
【０１２７】
上位ビット用の分割逆引きテーブルから読み出された「１０００」と下位ビット用の分割逆引きテーブルから読み出された「１０１０」の論理積が「１０００」であるので、ビット位置判定部５５から「３」が外部指定されたアドレス（サーチキー「００００００００）」に対応するデータとして出力される。
【０１２８】
（構成）
図１４は、第３の実施形態の半導体装置の構成を表わす図である。
【０１２９】
図１４を参照して、この半導体装置１６２は、半導体記憶装置１６１と、ＣＰＵ５７とからなる。
【０１３０】
ＣＰＵ５７は、半導体記憶装置１６１に対して、サーチコマンドＳＣとアドレスＡＤＤを与える。また、ＣＰＵ５７は、半導体記憶装置１６１から、ＡＤＤに対応する記憶されているデータＲＤを受ける。
【０１３１】
半導体記憶装置１６１は、第１〜第ＭのＭ個のアドレスブロック１５０を備える。Ｍ個のアドレスブロック１５０のそれぞれは、メモリセルアレイ１４９と、ロウデコーダ１５１と、センスアンプ群１５２とを有する。
【０１３２】
半導体記憶装置１６１は、第１〜第ＭのＭ個の分割逆引きブロック１５６を備える。Ｍ個の分割逆引きブロック１５６のそれぞれは、判定部ＳＬと、メモリセルアレイ１５７と、ロウデコーダ１５８と、センスアンプ群１５９とを有する。
【０１３３】
各メモリセルアレイは、行列上に配置された複数個のＳＲＡＭセルを有する。
第ｋ（ｋ＝１〜Ｍ）分割逆引きブロックのメモリセルアレイは、第２の実施形態の第ｋメモリセルアレイ４９−ｋに格納された分割逆引きテーブルから、必要なエントリのみを残し、残りを削除した分割逆引きテーブルを格納する。ここで、必要なエントリとは、「１」を含むエントリである。
【０１３４】
第ｋ（ｋ＝１〜Ｍ）アドレスブロックのメモリセルアレイは、第ｋ分割逆引きブロックのメモリセルアレイに格納された分割逆引きテーブルのエントリへのポインタと有効フラグＶａｌｉｄを格納する。有効フラグＶａｌｉｄが「１」のときには、分割逆引きテーブルのエントリへのポインタが格納されていることを示し、有効フラグＶａｌｉｄが「１」のときには、無効なデータが格納されていることを示す。
【０１３５】
たとえば、Ｍ＝２の場合には、第１アドレスブロックのメモリセルアレイは、図１３（ｃ）に示すような上位ビット用のアドレステーブルを記憶し、第２アドレスブロックのメモリセルアレイは、図１３（ｃ）に示すような下位ビット用のアドレステーブルを記憶し、第１分割逆引きブロックのメモリセルアレイは、図１３（ｃ）に示すような上位ビット用の分割逆引きテーブルを記憶し、第２分割逆引きブロックのメモリセルアレイは、図１３（ｃ）に示すような下位ビット用の分割逆引きテーブルを記憶する。
【０１３６】
さらに、この半導体記憶装置１６１は、第２の実施形態と同様のアドレス分割器５３と、多ビット論理積回路５４と、ビット位置判定部５５と、サーチ制御部５６とを備える。
【０１３７】
アドレス分割器５３は、外部から指定されたＮビットのアドレスＡＤＤを、Ｓ個のビットずつに分割する。アドレス分割器５３は、分割された最上位からＳ個のビットからなるアドレスＡＤＤ（１）を第１アドレスブロックのロウデコーダに出力する。アドレス分割器５３は、分割された最上位から（Ｓ＋１）番目のビット〜最上位から２Ｓ番目のビットからなるアドレスＡＤＤ（２）を第２アドレスブロックのロウデコーダに出力する。アドレス分割器５３は、分割された最下位からＳ個のビットからなるアドレスＡＤＤ（Ｍ）を第Ｍアドレスブロックのロウデコーダに出力する。
【０１３８】
第１アドレスブロックのロウデコーダ１５１は、アドレス分割器５３から出力されるＡＤＤ（１）に応じたメモリセルアレイ１４９内のワード線ＷＬを活性化する。第２アドレスブロックのロウデコーダ１５１は、アドレス分割器５３から出力されるＡＤＤ（２）に応じたメモリセルアレイ１４９内のワード線ＷＬを活性化する。第Ｍアドレスブロックのロウデコーダ１５１は、アドレス分割器５３から出力されるＡＤＤ（Ｍ）に応じたメモリセルアレイ１４９内のワード線ＷＬを活性化する。
【０１３９】
第１〜第Ｍアドレスブロックのセンスアンプ群１５２は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、メモリセルアレイの対応の列のビット線対の電圧を増幅して出力する。
【０１４０】
第ｋ（ｋ＝１〜Ｍ）分割逆引きブロックの判定部ＳＬは、第ｋアドレスブロックのセンスアンプ群１５２から出力されたデータの中の有効フラグＶａｌｉｄの値が「１」の場合には、この出力されたデータをアドレスとして、ロウデコーダ１５８に与える。
【０１４１】
第ｋ（ｋ＝１〜Ｍ）分割逆引きブロックのロウデコーダ１５８は、判定部ＳＬから受けたアドレスに応じたメモリセルアレイ１５７内のワード線ＷＬを活性化する。
【０１４２】
第ｋ（ｋ＝１〜Ｍ）分割逆引きブロックの判定部ＳＬは、第ｋアドレスブロックのセンスアンプ群１５２から出力されたデータの中の有効フラグＶａｌｉｄの値が「０」の場合には、オール０のＳビットのデータを多ビット論理積回路５４へ出力する。
【０１４３】
第ｋ（ｋ＝１〜Ｍ）分割逆引きブロックのセンスアンプ群１５９は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、メモリセルアレイ１５７の対応の列のビット線対の電圧を増幅して多ビット論理積回路５４へ出力する。
【０１４４】
（まとめ）
以上のように、第３の実施形態の半導体装置によれば、第２の実施形態の分割逆引きテーブルのエントリのうち、「１」を含むエントリのみを記憶するので、メモリ容量を削減できる。
【０１４５】
［第４の実施形態］
第４の実施形態では、第３の実施形態よりもさらなるメモリ容量節約のために、オリジナル検索テーブルのエントリを分割したシステムを考える。オリジナルの検索テーブルのエントリを分割することは、分割逆引きテーブルにおいてビット方向にテーブルを分割することと同じ意味を持つ。
【０１４６】
第４の実施形態は、第３の実施形態をさらに改良し、分割逆引きテーブルの１エントリを構成する複数ビットを分割した上で、第３の実施形態と同様に、ポインタによる間接参照により検索を実現する。冗長なテーブルのエントリが削除されるので、第３の実施形態よりもさらなるメモリ容量を節約できる。
【０１４７】
（メモリセルアレイの構成と、記憶されるデータの例）
図１５は、第４の実施形態の階層化された分割逆テーブルを説明するための図である。
【０１４８】
図１５（ａ）は、第２の実施形態による分割逆引きテーブルを表わす図であり、図１３（ｂ）に示したものと同様のテーブルである。
【０１４９】
図１５（ａ）に示すように、上位ビット用の分割逆引きテーブルおよび下位ビット用の分割逆引きテーブルは、それぞれ４ビット×１６エントリの６４ビットのテーブルである。上位ビット用の分割逆引きテーブルおよび下位ビット用の分割逆引きテーブルのそれぞれについて、（２）に示すように、１エントリを構成する４ビットを２ビットずつにビット分割することによって、２つの３２ビットのテーブルに分割する。
【０１５０】
これによって、各分割逆引きテーブルのビット分割された右側の３２ビットのテーブルで高々２ビットが「１」となり、ビット分割された左側の３２ビットで高々２ビットが「１」となる。したがって、第３の実施形態と同様に、エントリで考えると、以下のようになる。すなわち、各分割逆引きテーブルの右側および左側のテーブルは、１６エントリを有するが、有効なエントリは高々２エントリであり、残りの１４エントリはオール「０」の無効なデータを保持している。したがって、第４の実施形態では、第３の実施形態と同様に、ポインタを使った間接参照を導入することによって、ビット分割された右側および左側の３２ビットテーブルの無駄なエントリを削除する。
【０１５１】
図１５（ｂ）は、第４の実施形態による階層的分割逆引きを説明するための図である。
図１５（ｂ）に示すように、上位階層のアドレステーブルによって、下位階層のビット分割された分割逆引きテーブルが参照される。
【０１５２】
各分割逆引きテーブルのエントリは、「１」を含む有効なエントリの最大数である２個のみである。アドレステーブルには、外部から与えられるアドレス（サーチキー）から、分割逆引きテーブルのエントリを参照するためのポインタが格納される。このアドレステーブルは、さらに、各アドレスに分割逆引きテーブルのエントリへのポインタが格納されているかどうかを表わす有効フラグを格納する。有効フラグＶａｌｉｄが「１」のときには、分割逆引きテーブルのエントリへのポインタが格納されていることを示し、有効フラグＶａｌｉｄが「１」のときには、無効なデータが格納されていることを示す。
【０１５３】
このようにして、分割逆引きテーブルに無効なデータを格納しないようにすることによって、メモリ容量を大幅に圧縮することができる。
【０１５４】
たとえば、サーチキーとして「００００００００」が与えられた場合の検索手順について以下に説明する。
【０１５５】
上位ビット用の左側アドレステーブルにおいて、サーチキーの上位ビット「００００」のアドレス位置の有効フラグが「１」（有効）であるので、そのアドレス位置のデータ「０ｘ０」がセレクタ（判定部）ＳＬ１を介して上位ビット用の左側分割逆引きテーブルへのポインタとして読出される。
【０１５６】
上位ビット用の左側分割逆引きテーブルにおいて、「０ｘ０」のアドレス位置のデータ「１０」が読み出される。
【０１５７】
上位ビット用の右側アドレステーブルにおいて、サーチキーの上位ビット「００００」のアドレス位置の有効フラグが「０」（無効）であるので、上位ビット用の右側分割逆引きテーブルが参照されず、セレクタ（判定部）ＳＬ２を介して固定データ「００」が読み出される。
【０１５８】
以上より、左側分割逆引きテーブルから読出されたデータと右側分割逆引きテーブルから読出されたデータとを合成すると、上位ビットのテーブルから「１０００」が読出されることになる。
【０１５９】
下位ビット用の左側アドレステーブルにおいて、サーチキーの上位ビット「００００」のアドレス位置の有効フラグが「１」（有効）であるので、そのアドレス位置のデータ「０ｘ０」がセレクタ（判定部）ＳＬ３を介して下位ビット用の左側分割逆引きテーブルへのポインタとして読出される。
【０１６０】
下位ビット用の左側分割逆引きテーブルにおいて、「０ｘ０」のアドレス位置のデータ「１０」が読み出される。
【０１６１】
下位ビット用の右側アドレステーブルにおいて、サーチキーの上位ビット「００００」のアドレス位置の有効フラグが「１」（有効）であるので、そのアドレス位置のデータ「０ｘ１」がセレクタ（判定部）ＳＬ４を介して下位ビット用の右側分割逆引きテーブルへのポインタとして読出される。
【０１６２】
下位ビット用の右側分割逆引きテーブルにおいて、「０ｘ１」のアドレス位置のデータ「１０」が読み出される。
【０１６３】
以上より、左側分割逆引きテーブルから読出されたデータと右側分割逆引きテーブルから読出されたデータとを合成すると、下位ビットのテーブルから「１０１０」が読出されることになる。
【０１６４】
上位ビットのテーブルから読み出された「１０００」と下位ビットのテーブルから読み出された「１０１０」の論理積が「１０００」であるので、ビット位置判定部５５から「３」が外部指定されたアドレス（サーチキー「００００００００）」に対応するデータとして出力される。
【０１６５】
（構成）
図１６は、第４の実施形態の半導体装置の構成を表わす図である。
【０１６６】
図１６を参照して、この半導体装置１９２は、半導体記憶装置１９１と、ＣＰＵ５７とからなる。
【０１６７】
ＣＰＵ５７は、半導体記憶装置１９１に対して、サーチコマンドＳＣとアドレスＡＤＤを与える。また、ＣＰＵ５７は、半導体記憶装置１９１から、ＡＤＤに対応する記憶されているデータＲＤを受ける。
【０１６８】
半導体記憶装置１９１は、第ｉ−ｊアドレスブロック（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）２６１を備える。ＭＱ個のアドレスブロック２６１のそれぞれは、図示は省略するが、第３の実施形態と同様に、メモリセルアレイと、ロウデコーダと、センスアンプ群とを有する。
【０１６９】
半導体記憶装置１９１は、第ｉ−ｊ分割逆引きブロック（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ２７１）を備える。ＭＱ個の分割逆引きブロックのそれぞれは、図示は省略するが、第３の実施形態と同様に、判定部と、メモリセルアレイと、ロウデコーダと、センスアンプ群とを有する。
【０１７０】
各メモリセルアレイは、行列上に配置された複数個のＳＲＡＭセルを有する。
第ｉ−ｊ分割逆引きブロックのメモリセルアレイは、第３の実施形態の分割逆引きテーブルをＱ個にビット分割した分割逆引きテーブルを格納する。
【０１７１】
第ｉ−ｊ分割逆引きブロックに格納される分割逆引きテーブルは、逆テーブルをＭ個にアドレス分割したときの最上位から第ｉ番目の分割逆引きテーブルのＳビットのエントリをさらにＱ個にビット分割したときの最上位から第ｊ番目の分割逆引きテーブルである。この分割逆引きテーブルのエントリのビット数は、Ｓ／Ｑである。
【０１７２】
第ｉ−ｊアドレスブロックのメモリセルアレイは、第ｉ−ｊ分割逆引きブロックのメモリセルアレイに格納された分割逆引きテーブルのエントリへのポインタと有効フラグＶａｌｉｄを格納する。有効フラグＶａｌｉｄが「１」のときには、分割逆引きテーブルのエントリへのポインタが格納されていることを示し、有効フラグＶａｌｉｄが「１」のときには、無効なデータが格納されていることを示す。
【０１７３】
たとえば、Ｍ＝２、Ｑ＝２の場合には、第１−１アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような上位ビット用の左側アドレステーブルを記憶し、第１−２アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような上位ビット用の右側アドレステーブルを記憶し、第２−１アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような下位ビット用の左側アドレステーブルを記憶し、第２−２アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような下位ビット用の右側アドレステーブルを記憶する。第１−１分割逆引きブロックのメモリセルアレイは、図１５（ｂ）に示すような上位ビット用の左側分割逆引きテーブルを記憶し、第１−２アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような上位ビット用の右側分割逆引きテーブルを記憶し、第２−１アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような下位ビット用の左側分割逆引きテーブルを記憶し、第２−２アドレスブロックのメモリセルアレイは、図１５（ｂ）に示すような下位ビット用の右側分割逆引きテーブルを記憶する。
【０１７４】
さらに、この半導体記憶装置１９１は、第２の実施形態と同様の、アドレス分割器５３と、多ビット論理積回路５４−１〜Ｑと、ビット位置判定部５５と、サーチ制御部５６とを備える。
【０１７５】
アドレス分割器５３は、外部から指定されたＮビットのアドレスＡＤＤを、Ｓ個のビットずつに分割する。アドレス分割器５３は、分割された最上位からＳ個のビットからなるアドレスＡＤＤ（１）を第１アドレスブロックのロウデコーダに出力する。アドレス分割器５３は、分割された最上位から（Ｓ＋１）番目のビット〜最上位から２Ｓ番目のビットからなるアドレスＡＤＤ（２）を第２アドレスブロックのロウデコーダに出力する。アドレス分割器５３は、分割された最下位からＳ個のビットからなるアドレスＡＤＤ（Ｍ）を第Ｍアドレスブロックのロウデコーダに出力する。
【０１７６】
第１−ｊ（ｊ＝１〜Ｑ）アドレスブロックのロウデコーダは、アドレス分割器５３から出力されるＡＤＤ（１）に応じたメモリセルアレイ内のワード線ＷＬを活性化する。第２−ｊ（ｊ＝１〜Ｑ）アドレスブロックのロウデコーダは、アドレス分割器５３から出力されるＡＤＤ（２）に応じたメモリセルアレイ内のワード線ＷＬを活性化する。第Ｍ−ｊ（ｊ＝１〜Ｑ）アドレスブロックのロウデコーダは、アドレス分割器５３から出力されるＡＤＤ（Ｍ）に応じたメモリセルアレイ内のワード線ＷＬを活性化する。
【０１７７】
第ｉ―ｊ（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）アドレスブロックのセンスアンプ群は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、メモリセルアレイの対応の列のビット線対の電圧を増幅して出力する。
【０１７８】
第ｉ―ｊ（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）分割逆引きブロックの判定部は、第i―ｊアドレスブロックのセンスアンプ群から出力されたデータの中の有効フラグＶａｌｉｄの値が「１」の場合には、この出力されたデータをアドレスとして、第ｉ―ｊ分割逆引きブロックのロウデコーダに与える。
【０１７９】
第ｉ―ｊ（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）分割逆引きブロックのロウデコーダは、判定部から受けたアドレスに応じたメモリセルアレイ内のワード線ＷＬを活性化する。
【０１８０】
第ｉ―ｊ（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）分割逆引きブロックの判定部は、第ｉ―ｊアドレスブロックのセンスアンプ群から出力されたデータの中の有効フラグＶａｌｉｄの値が「０」の場合には、オール０の（Ｓ／Ｑ個のビット）のデータを多ビット論理積回路へ出力する。
【０１８１】
第ｉ―ｊ（ｉ＝１〜Ｍ、ｊ＝１〜Ｑ）分割逆引きブロックのセンスアンプ群は、列ごとに設けられたセンスアンプを備える。各センスアンプは、センスアンプ制御信号ＳＡが「Ｈ」レベルに活性化されると、メモリセルアレイの対応の列のビット線対の電圧を増幅して多ビット論理積回路５４−ｊへ出力する。
【０１８２】
（まとめ）
以上のように、第４の実施形態の半導体装置によれば、分割逆引きテーブルの１エントリを構成する複数ビットをビット分割した上で、第３の実施形態と同様に、ポインタによる間接参照を用いることによって、第３の実施形態よりもさらなるメモリ容量を節約できる。
【０１８３】
（第２〜第４の実施形態のテーブル容量の比較例１）
図１７は、オリジナルの検索方式と、第２〜第４の検索方式でのテーブルを記憶する容量について説明するための図である。
【０１８４】
図１７（ａ）は、オリジナルの検索テーブルを表わす。
オリジナルの検索テーブルのエントリ数が２５６であり、各エントリのビット数は４１である。したがって、オリジナルの検索方式でのテーブルの容量は、１０．２５Ｋｂである。
【０１８５】
図１７（ｂ）は、第２の実施形態の分割逆引きテーブルを表わす。
図１７（ｂ）に示すように、各分割逆引きテーブル（ＤＲＴ）は、１０ビット単位で４ブロックにアドレス分割したテーブルである。各分割逆引きテーブルのエントリ数が１Ｋであり、各エントリのビット数は２５６である。したがって、第２の実施形態の検索方式でのテーブルの容量は、１Ｍｂである。
【０１８６】
図１７（ｃ）は、第３の実施形態のアドレステーブルおよび分割逆引きテーブルを表わす。
【０１８７】
図１７（ｃ）に示すように、各分割逆引きテーブル（ＤＲＴ）は、図１７（ｂ）の分割逆引きテーブルについて、「１」を含むエントリを残し、その他のエントリを削除したものであり、エントリ数は、２５６である。また、各アドレステーブル（ＡＴ）のエントリ数は１Ｋであり、各エントリのビット数は９である。したがって、第３の実施形態の検索方式でのテーブルの容量は、２９２ｋｂである。
【０１８８】
図１７（ｄ）は、第４の実施形態のアドレステーブルおよび分割逆引きテーブルを表わす。
【０１８９】
図１７（ｄ）に示すように、各分割逆引きテーブル（ＤＲＴ）は、図１７（ｃ）の分割逆引きテーブルを６４ビット単位で４ブロックに分割したものである。各分割逆引きテーブルのエントリ数は６４であり、各エントリのビット数は６４である。また、各アドレステーブル（ＡＴ）のエントリ数は１Ｋであり、各エントリのビット数は７である。したがって、第４の実施形態でのテーブルの容量は１７６Ｋｂである。
【０１９０】
（第２〜第４の実施形態のテーブル容量の比較例２）
図１８は、オリジナルの検索方式と、第２〜第４の実施形態の検索方式でのテーブルを記憶する容量について説明するための図である。第２〜第４の実施形態の検索方式でのアドレス分割の数をＭとする。第４の実施形態の検索方式でのビット分割の数をＴとする。
【０１９１】
図１８（ａ）は、オリジナルの検索テーブルを表わす。
オリジナルの検索テーブルのエントリ数がＬであり、各エントリのビット数は（Ｎ＋１）である。したがって、オリジナルの検索方式でのテーブルの容量は、Ｌ×（Ｎ＋１）である。
【０１９２】
図１８（ｂ）は、第２の実施形態の分割逆引きテーブルを表わす。
図１８（ｂ）に示すように、各分割逆引きテーブル（ＤＲＴ）は、Ｓビット単位でＭブロックにアドレス分割したテーブルである。各分割逆引きテーブルのエントリ数が２Sであり、各エントリのビット数はＬである。したがって、第２の実施形態の検索方式でのテーブルの容量は、Ｌ×２S×Ｍである。
【０１９３】
図１８（ｃ）は、第３の実施形態のアドレステーブルおよび分割逆引きテーブルを表わす。
【０１９４】
図１８（ｃ）に示すように、各分割逆引きテーブル（ＤＲＴ）のエントリ数はＬである。また、各アドレステーブル（ＡＴ）のエントリ数は２Sであり、各エントリのビット数は（１＋Ｌｏｇ2Ｌ）である。したがって、第３の実施形態の検索方式でのテーブルの容量は、（（１＋Ｌｏｇ2Ｌ）×２S＋Ｌ2）×Ｍである。
【０１９５】
図１８（ｄ）は、第４の実施形態のアドレステーブルおよび分割逆引きテーブルを表わす。
【０１９６】
図１８（ｄ）に示すように、各分割逆引きテーブル（ＤＲＴ）のエントリ数はＴであり、各エントリのビット数はＴである。また、各アドレステーブル（ＡＴ）のエントリ数は２Sであり、各エントリのビット数は（１＋Ｌｏｇ2Ｔ）である。したがって、第４の実施形態でのテーブルの容量は（（１＋Ｌｏｇ2Ｔ）×２S＋Ｔ2）×Ｗ×Ｍである。
【０１９７】
たとえば、Ｎ＝１２８、Ｌ＝８１９２、Ｓ＝１６、Ｍ＝８の場合について、上記の検索方式でのテーブルの容量は、以下のようになる。
【０１９８】
図１８（ａ）に示すオリジナルの検索方式でのテーブルの容量は、１０３２Ｋｂである。図１８（ｂ）に示す第２の実施形態の検索方式でのテーブルの容量は、４Ｇｂである。
図１８（ｃ）に示す第３の実施形態の検索方式でのテーブルの容量は、５１０Ｍｂである。図１８（ｄ）に示す第４の実施形態の検索方式でのテーブルの容量は、１０８ＭＢである。
【０１９９】
（第３の実施形態が第２の実施形態よりもテーブル容量が小さくなる条件）
第３の実施形態の検索方式の方が、第２の実施形態の検索方式よりもテーブルの容量が小さくなるのは、以下の式（Ａ１）が成立するときである。
【０２００】
L * 2S > (1 + log2L) * 2S + L2  ・・・・（Ａ１）
式（Ａ）を変形すると以下のようになる。
【０２０１】
(L - 1 - log2L) * 2S> L2
(1 / L - 1 / L2 - log2L / L2) * 2S > 1
ここで、L >> 1と仮定すると、以下のように式が変形される。
【０２０２】
(1 / L - log2L / L2) * 2S > 1
2S > L2 / (L - log2L)
ここで、L >> 1のときには、以下のように式が変形される。
【０２０３】
S > 2 * log2L - log2(L - log2L)
さらに、L >> log2Lが成り立つ場合において、L >> 1かつL >> log2Lのときには、以下のように変形される。
【０２０４】
S > log2L
たとえば、L=8192の場合には、S > log28192＝13となる。
【０２０５】
（第４の実施形態が第３の実施形態よりもテーブル容量が小さくなる条件）
第４の実施形態の検索方式の方が、第３の実施形態の検索方式よりもテーブルの容量が小さくなるのは、以下の式（Ａ２）が成立するときである。
【０２０６】
(1 + log2L) * 2S + L2> ((1 + log2T) * 2S + T2) * W  ・・・  （Ａ２）
式（Ａ２）を変形すると、以下のようになる。
【０２０７】
T * W = Lなので
(1 + log2L) * 2S + L2> ((1 + log2T) * 2S + T2) * L / T
(1 / L2 + log2L / L2) * 2S + 1 > (1 / (L * T) + log2T / (L * T)) * 2S+ T / L
1 - T / L > (1 / (L * T) + log2T / (L * T) - 1 / L2 - log2L / L2) * 2S
ここで、L >> 1，T >> 1と仮定すると、以下のように変形される。
【０２０８】
1 - T / L > (log2T / (L * T) - log2L / L2) * 2S
2S < (1 - T / L) / (log2T / (L * T) - log2L / L2)
2S < L * T / log2T * (1 - T / L) / (1 - T / L * log2L / log2T)
さらに、L>>1かつT>>1のときには、以下のように変形される。
【０２０９】
S < log2L + log2T - log2(log2T) + log2(1 - T / L) - log2(1 - T / L * log2L / log2T)
さらに、log2L / log2T ~ 1が成り立つ場合は、以下のように変形される。
【０２１０】
2S < L * T / log2T * (1 - T / L) / (1 - T / L) 
2S < L * T / log2T
さらに、L >> 1かつT >> 1かつlog2L / log2T ~ 1のときには、以下のように変形される。
【０２１１】
S < log2L + log2T - log2(log2T)，
たとえば、L=8192で、T=1024の場合には、S < log2(8192) + log2(1024) - log2(log2(1024)) = 13 + 10 - 3.3 = 19.7となる。
【０２１２】
［第５の実施形態］
図１９は、第５の実施形態の半導体装置の構成を表わす図である。
【０２１３】
図１９を参照して、この半導体装置８１は、ＣＰＵ８３と、メモリセルアレイ８２と、第２の実施形態の半導体記憶装置６１と、メンテナンス部８４とを備える。
【０２１４】
メモリセルアレイ８２は、行列状に配置された複数のメモリセルを有し、半導体記憶装置６１に記憶されている分割逆引き方式のデータの元となるデータを記憶する。
【０２１５】
ＣＰＵ８３は、第２の実施形態と同様に、サーチ時に、アドレスＡＤＤ＿Ｓを半導体記憶装置６１に与え、アドレスＡＤＤ＿Ｓに対応するデータＲＤを半導体記憶装置６１から受ける。ＣＰＵ８３は、メンテナンス時に、アドレスＡＤＤ＿Ｍに対応する新たなデータＮ＿ＤＡをメンテナンス部８４に与える。
【０２１６】
（メンテナンス処理）
次に、メンテナンス部８４による、メンテナンス処理について説明する。
【０２１７】
メモリセルアレイ８２には、図９（ｂ）に示すデータが格納されるものとする。半導体記憶装置６１は、上位ビット用の第１メモリセルアレイと、下位ビット用の第２のメモリセルアレイとを備え、上位ビット用の第１メモリセルアレイと、下位ビット用の第２のメモリセルアレイには、それぞれ図９（ｈ）、（ｉ）に示すデータが格納されているものとする。
【０２１８】
ここで、メモリセルアレイ８２のエントリ番号「１」に格納されているデータ「００１１」を「０１１０」に変更するようにメンテナンスするものとする。
【０２１９】
ＡＤＤ＿Ｍとして「１」が入力され、メモリセルアレイ８２のＡＤＤ＿Ｍで指定される行からリードデータＯ＿ＤＡ（＝「００１１」）が出力される。
【０２２０】
メンテナンス部８４は、ＡＤＤ＿Ｍ（＝「１」）に対応するリードデータＯ＿ＤＡ（「００１１」）の関係から、第１メモリセルアレイのアドレス「００」に対応するエントリの下位２ビット目の「１」を「０」に変更し、第２メモリセルアレイのアドレス「１１」に対応するエントリの下位２ビット目の「１」を「０」に変更する。
【０２２１】
次に、メンテナンス部８４は、ＡＤＤ＿Ｍ（＝「１」）に対する新規データＮ＿ＤＡＴＡ（＝「０１１０」）の関係から、第１メモリセルアレイのアドレス「０１」に対応するエントリの下位２ビット目の「０」を「１」に変更し、第２メモリセルアレイのアドレス「１０」に対応するエントリの下位２ビット目の「０」を「１」に変更する。また、メンテナンス部は、メモリセルアレイ８２のＡＤＤ＿Ｍで指定される行に新規データＮ＿ＤＡを書込む。
【０２２２】
以上のように、第５の実施形態の半導体装置によれば、第２の実施形態のメモリセルに格納した分割逆引き方式のもととなるデータを格納するメモリセルアレイを備えることによって、第２の実施形態でメモリセルに格納されるデータの修正、変更が可能となる。
【０２２３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０２２４】
１，６２，１６２，１９２  半導体装置、２，６１，１６１，１９２  半導体記憶装置、３，４１〜４８，４９＿１〜４９＿Ｍ，８２，１４９，１５７  メモリセルアレイ、４，５１＿１〜５１＿Ｍ，１５１，１５８  ロウデコーダ、５，５２＿１〜５２＿Ｍ，１５２，１５９  センスアンプ群、６  第１のサーチデータレジスタ、７，５６  サーチ制御部、８  アドレス生成器、９  第１の比較器、１０  第２の比較器、１１  第１のプライオリティエンコーダ、１２  第２のプライオリティエンコーダ、１３  第２のサーチデータレジスタ、１５，５７，８３  ＣＰＵ、２０Ａ＿１（１）〜２０Ａ＿Ｎ（１），２０Ａ＿１（２）〜２０Ａ＿Ｎ（２），２０Ｂ＿１（１）〜２０Ｂ＿Ｎ（１），２０Ｂ＿１（２）〜２０Ｂ＿Ｎ（２）  反一致回路、２１Ａ，２１Ｂ，２２，２５  論理和回路、２３，２４，２６，２７  ラッチ回路、５３  アドレス分割器、５４  多ビット論理積回路、５５  ビット位置判定部、６０＿１〜６０＿Ｌ  論理積回路、８４  メンテナンス部、ＩＶＡ＿１〜ＩＶＡ＿Ｎ，ＩＶＢ＿１〜ＩＶＢ＿Ｎ  インバータ、１５０，２６１  アドレスブロック、１５６，２７１  分割逆引きブロック。
【図１】
0005731179.tif 000002
【図２】
0005731179.tif 000003
【図３】
0005731179.tif 000004
【図４】
0005731179.tif 000005
【図５】
0005731179.tif 000006
【図６】
0005731179.tif 000007
【図７】
0005731179.tif 000008
【図８】
0005731179.tif 000009
【図９】
0005731179.tif 000010
【図１０】
0005731179.tif 000011
【図１１】
0005731179.tif 000012
【図１２】
0005731179.tif 000013
【図１３】
0005731179.tif 000014
【図１４】
0005731179.tif 000015
【図１５】
0005731179.tif 000016
【図１６】
0005731179.tif 000017
【図１７】
0005731179.tif 000018
【図１８】
0005731179.tif 000019
【図１９】
0005731179.tif 000020