(57)【要約】【課題】検索処理の信頼性を向上することができるようにする。【解決手段】記憶部の各エントリは、メンテナンスポートより検索装置に入力され、エラー検出処理部により登録される７２ビットの検索対象データ、エラー検出処理部により検索対象データに付加される８ビットのＥＣＣ（冗長ビット）からなるエントリデータ、および、エントリに有効なエントリデータが登録されているか否かを示す１ビットのエンプティビットにより構成される。エラー検出処理部は、エントリデータを読み出し、エントリデータの冗長ビットに基づいて、エントリデータの検索対象データの誤りの検出訂正処理を実行する。本発明は、ネットワークの中継を行うルータに適用できる。【選択図】      図５
2004362315.tif 000002
【特許請求の範囲】
【請求項１】
入力されたデータを、登録されているエントリデータの中から検索する連想メモリであって、
前記エントリデータは、前記入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出訂正符号が付加されて構成されている
ことを特徴とする連想メモリ。
【請求項２】
入力されたデータを、登録されているエントリデータの中から検索する連想メモリであって、
前記エントリデータは、前記入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出符号が付加されて構成されている
ことを特徴とする連想メモリ。
【請求項３】
入力されたデータを、登録されているエントリデータの中から検索する検索装置において、
前記入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加手段と、
前記付加手段により前記誤り検出訂正符号が付加された前記検索対象データを前記エントリデータとして登録する登録手段と、
前記入力されたデータを前記登録手段により登録された前記エントリデータの中から検索する検索手段と
を備えることを特徴とする検索装置。
【請求項４】
前記エントリデータの前記誤り検出訂正符号を検索対象から外すマスクパターンを設定するマスク設定手段をさらに備え、
前記検索手段は、前記マスク設定手段により設定されたマスクパターンに基づいて、前記入力されたデータを前記登録手段により登録された前記エントリデータの中から検索する
ことを特徴とする請求項３に記載の検索装置。
【請求項５】
前記登録手段により登録された前記エントリデータを読み出す読み出し手段と、
前記読み出し手段により読み出された前記エントリデータの前記誤り検出訂正符号に基づいて、前記エントリデータの誤りを検出し、訂正する誤り訂正処理を行う誤り検出訂正手段と、
前記誤り検出訂正手段により誤りが訂正された前記エントリデータを再登録する再登録手段と
をさらに備えることを特徴とする請求項３に記載の検索装置。
【請求項６】
前記誤り検出訂正手段による前記誤り検出訂正処理を、前記登録手段により登録されたすべてのエントリデータに施すための所定のコマンドを発生させるコマンド発生手段をさらに備え、
前記読み出し手段は、前記コマンド発生手段により前記コマンドが発生された場合に、前記すべてのエントリデータを順に読み出す
ことを特徴とする請求項５に記載の検索装置。
【請求項７】
所定の時間が経過したか否かを判断する時間判断手段をさらに備え、
前記読み出し手段は、前記時間判断手段により所定の時間が経過したと判断された場合に、前記登録手段により登録されたすべてのエントリデータを順に読み出す
ことを特徴とする請求項５に記載の検索装置。
【請求項８】
前記誤り検出訂正手段により前記エントリデータの前記誤りが訂正されなかった場合、前記エントリデータの誤りが訂正されなかったことを示す情報と、前記エントリデータのアドレスを通知する通知手段を
さらに備えることを特徴とする請求項５に記載の検索装置。
【請求項９】
前記エントリデータが前記検索対象として有効であるか否かを示す検索対象情報を設定する検索対象情報設定手段をさらに備え、
前記検索対象情報設定手段は、前記誤り検出訂正手段により前記エントリデータの誤りが訂正されなかった場合、前記エントリデータの前記検索対象情報を無効に設定する
ことを特徴とする請求項５に記載の検索装置。
【請求項１０】
入力されたデータを、登録されているエントリデータの中から検索する検索方法において、
前記入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、
前記付加ステップの処理により前記誤り検出訂正符号が付加された前記検索対象データを前記エントリデータとして登録する登録ステップと、
前記入力されたデータを前記登録ステップの処理により登録された前記エントリデータの中から検索する検索ステップと
を含むことを特徴とする検索方法。
【請求項１１】
入力されたデータを、登録されているエントリデータの中から検索する検索処理を行うプログラムであって
前記入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、
前記付加ステップの処理により前記誤り検出訂正符号が付加された前記検索対象データを前記エントリデータとして登録する登録ステップと、
前記入力されたデータを前記登録ステップの処理により登録された前記エントリデータの中から検索する検索ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１２】
入力されたデータを、登録されているエントリデータの中から検索する検索処理をコンピュータに実行させるプログラムであって、
前記入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、
前記付加ステップの処理により前記誤り検出訂正符号が付加された前記検索対象データを前記エントリデータとして登録する登録ステップと、
前記入力されたデータを前記登録ステップの処理により登録された前記エントリデータの中から検索する検索ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連想メモリ、検索装置および方法、記録媒体、並びにプログラムに関し、特に、検索処理の信頼性を向上することができるようにした連想メモリ、検索装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
ネットワークの高速スイッチングを行うためのスイッチングＨＵＢやルータなどのネットワーク装置は、頻繁にはリセットされることなく、２４時間稼動することが多く、高度な信頼性が要求される。そこで、このようなネットワーク装置に、近年、連想メモリ（ＣＡＭ：Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）が多く用いられるようになってきている。
【０００３】
図１は、ＣＡＭ１のセルの構成例を示している。図１においては、ＣＡＭ１は、６つのトランジスタと、書き込み、読み出し２組のワード線およびビット線からなるＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１１、並びに、４つのトランジスタ、書き込み、読み出し２組の検索ビット線、およびマッチ線からなる検索回路（Ｍａｔｃｈ  Ｄｅｔｅｃｔｏｒ）１２により構成される。なお、ＳＲＡＭ１１は、検索対象となるデータを保持するメモリセルであり、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）で構成される場合もある。
【０００４】
ＣＡＭ１が、ネットワーク中継装置に使用された場合、ＣＡＭ１のＳＲＡＭ１１には、ＩＰアドレスおよびＴＣＰポート番号などがエントリデータとして登録される。ＣＡＭ１にデータが入力されると、検索回路１２は、ＳＲＡＭ１１に登録されているエントリデータの中からそのデータに、マッチング（一致）するものを検索し、検索結果として、マッチングしたエントリデータのアドレスなどを出力する。
【０００５】
一方、昨今のインターネットの普及拡大や高速化により、必要とされるＣＡＭの容量（例えば、１８．８Ｍビット以上）は、年々大きくなってきている。このため、ＣＡＭを構成するＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）を製造するプロセスは、ゲートサイズが０．１３μｍ以下のものが必要とされる。
【０００６】
しかしながら、上述したプロセスを用いてトランジスタが微細化されることにより、微細化されたトランジスタにおいては、アルファ線などによるソフトエラーが生じてしまう恐れがある。例えば、ＳＲＡＭにおいて、ソフトエラーが生じた場合、ＳＲＡＭに記憶されているデータが書き換わってしまう。
【０００７】
このような場合、従来のメモリ装置においては、特許文献１に示されるように、入力されるデータに、ＥＣＣ（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）に代表される誤り検出訂正符号、またはパリティ符号に代表される誤り検出符号を付加することにより対応していた。
【０００８】
図２は、ＥＣＣ処理を行う従来のメモリ装置の構成例を示している。図２の例においては、メモリ２２に書き込まれるデータのビット列がｍビットで、誤り検出訂正符号がｋビットであるので、メモリ１２内のワード長は、ｍ＋ｋビットとされている。
【０００９】
ＥＣＣエンコーダ２１は、ｍビットのデータが入力されると、ｋビットの誤り検出訂正符号を付加（ＥＣＣエンコード）し、ｋビットの誤り検出訂正符号が付加されたｍ＋ｋビット幅のデータをメモリ２２に書き込む。デコーダ２３は、メモリ２２に書き込まれたｍ＋ｋビット幅のデータを読み出し、ｋビットの誤り検出訂正符号を誤り検出訂正（ＥＣＣデコード）し、訂正された訂正後データ（ｍビット）を図示せぬ後段に出力する。
【００１０】
このようにすることで、従来のメモリ装置においては、ＥＣＣエンコーダ２１によりメモリ２２に書き込まれたデータが、ソフトエラーなどにより書き換えられてしまったとしても、ＥＣＣデコーダ２３において、誤り検出訂正符号を用いて、誤ったデータが訂正されるので、訂正された正しいデータを出力することができた。
【００１１】
【特許文献１】
特開平６−２５０９３５号公報
【００１２】
【発明が解決しようとする課題】
上述したようなソフトエラーが生じた場合、図１のＣＡＭ１において、ＳＲＡＭ１１に記憶されているデータの多くは、エージングなどの処理により一定の時間間隔で書き換わっていくために、ソフトエラーが生じたとしても、回復できる可能性がある。しかしながら、すべてがそのように書き換わるデータばかりではなく、特にルータなどのネットワーク装置の場合、上述したように、電源をほとんど切ることなく使用されるために、長時間にわたり記憶されたデータが維持される場合がある。したがって、ＣＡＭ１においても、ＳＲＡＭ１１に記憶されたデータ（エントリデータを含む）がソフトエラーによって書き換わってしまう課題があった。
【００１３】
さらに、ＣＡＭ１において出力されるものは、入力されるデータと一致するエントリデータのアドレスなどの検索結果であるため、上述したような従来のメモリ装置におけるＥＣＣの処理をただ単に適用するだけでは、結局、間違った検索結果が出力されてしまう。したがって、ＣＡＭ１の信頼性が悪くなってしまう課題があった。
【００１４】
本発明は、このような状況に鑑みてなされたものであり、検索処理の信頼性を向上することができるようにするものである。
【００１５】
【課題を解決するための手段】
本発明の第１の連想メモリは、エントリデータは、入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出訂正符号が付加されて構成されていることを特徴とする。
【００１６】
本発明の第２の連想メモリは、エントリデータは、入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出符号が付加されて構成されていることを特徴とする。
【００１７】
本発明の検索装置は、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加手段と、付加手段により誤り検出訂正符号が付加された検索対象データをエントリデータとして登録する登録手段と、入力されたデータを登録手段により登録されたエントリデータの中から検索する検索手段とを備えることを特徴とする。
【００１８】
エントリデータの誤り検出訂正符号を検索対象から外すマスクパターンを設定するマスク設定手段をさらに備え、検索手段は、マスク設定手段により設定されたマスクパターンに基づいて、入力されたデータを登録手段により登録されたエントリデータの中から検索するようにすることができる。
【００１９】
登録手段により登録されたエントリデータを読み出す読み出し手段と、読み出し手段により読み出されたエントリデータの誤り検出訂正符号に基づいて、エントリデータの誤りを検出し、訂正する誤り訂正処理を行う誤り検出訂正手段と、誤り検出訂正手段により誤りが訂正されたエントリデータを再登録する再登録手段とをさらに備えるようにすることができる。
【００２０】
誤り検出訂正手段による誤り検出訂正処理を、登録手段により登録されたすべてのエントリデータに施すための所定のコマンドを発生させるコマンド発生手段をさらに備え、読み出し手段は、コマンド発生手段によりコマンドが発生された場合に、すべてのエントリデータを順に読み出すようにすることができる。
【００２１】
所定の時間が経過したか否かを判断する時間判断手段をさらに備え、読み出し手段は、時間判断手段により所定の時間が経過したと判断された場合に、登録手段により登録されたすべてのエントリデータを順に読み出すようにすることができる。
【００２２】
誤り検出訂正手段によりエントリデータの誤りが訂正されなかった場合、エントリデータの誤りが訂正されなかったことを示す情報と、エントリデータのアドレスを通知する通知手段をさらに備えるようにすることができる。
【００２３】
エントリデータが検索対象として有効であるか否かを示す検索対象情報を設定する検索対象情報設定手段をさらに備え、検索対象情報設定手段は、誤り検出訂正手段によりエントリデータの誤りが訂正されなかった場合、エントリデータの検索対象情報を無効に設定するようにすることができる。
【００２４】
本発明の検索方法は、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、付加ステップの処理により誤り検出訂正符号が付加された検索対象データをエントリデータとして登録する登録ステップと、入力されたデータを登録ステップの処理により登録されたエントリデータの中から検索する検索ステップとを含むことを特徴とする。
【００２５】
本発明の記録媒体に記録されるプログラムは、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、付加ステップの処理により誤り検出訂正符号が付加された検索対象データをエントリデータとして登録する登録ステップと、入力されたデータを登録ステップの処理により登録されたエントリデータの中から検索する検索ステップとを含むことを特徴とする。
【００２６】
本発明のプログラムは、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップと、付加ステップの処理により誤り検出訂正符号が付加された検索対象データをエントリデータとして登録する登録ステップと、入力されたデータを登録ステップの処理により登録されたエントリデータの中から検索する検索ステップとを含むことを特徴とする。
【００２７】
第１の本発明においては、エントリデータが、入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出訂正符号が付加されて構成される。
【００２８】
第２の本発明においては、エントリデータが、入力されたデータを検索する検索対象となる検索対象データに、所定のビット長の誤り検出符号が付加されて構成される。
【００２９】
第３の本発明においては、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号が付加され、誤り検出訂正符号が付加された検索対象データがエントリデータとして登録される。そして、入力されたデータが登録されたエントリデータの中から検索される。
【００３０】
【発明の実施の形態】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００３１】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００３２】
請求項１に記載の連想メモリ（例えば、図３のＣＡＭブロック６６）は、エントリデータ（例えば、図５のエントリデータ）は、入力されたデータ（例えば、検索キーデータ）を検索する検索対象となる検索対象データ（例えば、図５の検索対象データ）に、所定のビット長の誤り検出訂正符号（例えば、図５のＥＣＣ（冗長ビット））が付加されて構成されていることを特徴とする。
【００３３】
請求項２に記載の連想メモリ（例えば、図３のＣＡＭブロック６６）は、エントリデータ（例えば、図１１のエントリデータ）は、入力されたデータ（例えば、検索キーデータ）を検索する検索対象となる検索対象データ（例えば、図１１の検索対象データ）に、所定のビット長の誤り検出符号（例えば、図１１のパリティ符号）が付加されて構成されていることを特徴とする。
【００３４】
請求項３に記載の検索装置（例えば、図３の検索装置５１）は、入力されたデータを検索する検索対象となる検索対象データ（例えば、図５の検索対象データ）に、誤り検出訂正符号（例えば、図５のＥＣＣ（冗長ビット））を付加する付加手段（例えば、図７のステップＳ３の処理を実行する図６のＥＣＣエンコーダ８１）と、付加手段により誤り検出訂正符号が付加された検索対象データをエントリデータ（例えば、図５のエントリデータ）として登録する登録手段（例えば、図７のステップＳ４の処理を実行する図６のＥＣＣエンコーダ８１）と、入力されたデータ（例えば、検索キーデータ）を登録手段により登録されたエントリデータの中から検索する検索手段（例えば、図３の検索部７２）とを備えることを特徴とする。
【００３５】
請求項４に記載の検索装置は、エントリデータの誤り検出訂正符号を検索対象から外すマスクパターンを設定するマスク設定手段（例えば、図３のマスク発生部６５）をさらに備え、検索手段は、マスク設定手段により設定されたマスクパターンに基づいて、入力されたデータを登録手段により登録されたエントリデータの中から検索することを特徴とする。
【００３６】
請求項５に記載の検索装置は、登録手段により登録されたエントリデータを読み出す読み出し手段（例えば、図８のステップＳ２２の処理を実行する図６のＥＣＣデコーダ８２）と、読み出し手段により読み出されたエントリデータの誤り検出訂正符号に基づいて、エントリデータの誤りを検出し、訂正する誤り訂正検出処理を行う誤り検出訂正手段（例えば、図８のステップＳ２３の処理を実行する図６のＥＣＣデコーダ８２）と、誤り検出訂正手段により誤りが訂正されたエントリデータを再登録する再登録手段（例えば、図８のステップＳ２５の処理を実行する図６のＥＣＣエンコーダ８１）とをさらに備えることを特徴とする。
【００３７】
請求項６に記載の検索装置は、誤り検出訂正手段による誤り検出訂正処理を、登録手段により登録されたすべてのエントリデータに施すための所定のコマンドを発生させるコマンド発生手段（例えば、図３のリフレッシュ要求部６８）をさらに備え、読み出し手段は、前記コマンド発生手段により前記コマンドが発生された場合に、すべての前記エントリデータを順に読み出すことを特徴とする。
【００３８】
請求項８に記載の検索装置は、誤り検出訂正手段によりエントリデータの誤りが訂正されなかった場合、エントリデータの誤りが訂正されなかったことを示す情報と、エントリデータのアドレスを通知する通知手段（例えば、図６のエラー通知部８３）をさらに備えることを特徴とする。
【００３９】
請求項９に記載の検索装置は、エントリデータが検索対象として有効であるか否かを示す検索対象情報（例えば、図５のエンプティビット）を設定する検索対象情報設定手段（例えば、図８のステップＳ２７の処理を実行する図６のＥＣＣエンコーダ８１）をさらに備え、検索対象情報設定手段は、誤り検出訂正手段によりエントリデータの誤りが訂正されなかった場合、エントリデータの検索対象情報を無効に設定することを特徴とする。
【００４０】
本発明の検索方法、記録媒体およびプログラムは、入力されたデータを検索する検索対象となる検索対象データに、誤り検出訂正符号を付加する付加ステップ（例えば、図７のステップＳ３）と、付加ステップの処理により誤り検出訂正符号が付加された検索対象データをエントリデータとして登録する登録ステップ（例えば、図７のステップＳ４）と、入力されたデータを登録ステップの処理により登録されたエントリデータの中から検索する検索ステップ（例えば、図９のステップＳ４４）とを含むことを特徴とする。
【００４１】
以下、図を参照して本発明の実施の形態について説明する。
【００４２】
図３は、本発明を適用した検索装置５１の構成例を表している。図３の例の場合、検索装置５１は、コマンド制御部６１、キーデータ生成部６２、データ入出力制御部６３、エラー検出処理部６４、マスク発生部６５、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ：連想メモリ）ブロック６６、検索結果出力部６７およびリフレッシュ要求部６８により構成される。なお、図３の例においては、図示されないが、検索装置５１の外部には、検索装置５１とのデータの入出力を行う外部の制御装置または外部の装置が設置されている。
【００４３】
検索装置５１は、外部の装置などから検索キーデータを入力するための入力データポートａ、外部の制御装置などから各種コマンドを入力するためのコマンドポートｂ、クロックを入力するためのクロックポートｃ、およびメンテナンス用の各種データを入出力するためのメンテナンスポートｄ、外部の制御装置などにエラー通知を出力するためのエラー通知ポートｅ、並びに、外部の装置などに検索結果データを出力するための出力ポートｆを有している。
【００４４】
コマンド制御部６１は、クロックポートｃから供給されるクロックに同期して、外部の制御装置から、コマンドポートｂを介して各種コマンドを入力し、入力された各種コマンドに基づいて、キーデータ生成部６２、データ入出力制御部６３、エラー検出処理部６４およびマスク発生部６５を制御する。また、コマンド制御部６１は、リフレッシュ要求部６８からのリフレッシュコマンドに応じて、データ入出力制御部６３およびエラー検出処理部６４を制御する。したがって、任意のコマンドが入力された場合、コマンド制御部６１は、それ以外のコマンドに対する処理に対する制御を行わない。すなわち、入力されたコマンド以外の処理は、排他制御される。
【００４５】
キーデータ生成部６２は、コマンド制御部６１からの制御に基づいて、入力データポートａから入力された検索キーデータをＣＡＭブロック６６に供給する。
【００４６】
データ入出力制御部６３には、メンテナンスポートｂを介して、外部の制御装置から、ＣＡＭブロック６６に登録する検索対象データが入力される。データ入出力制御部６３は、コマンド制御部６１からの制御に基づいて、メンテナンスポートｄから入力された検索対象データを、エラー検出処理部６４に出力したり、エラー検出処理部６４から入力された検索対象データをメンテナンスポートｄを介して外部の制御装置に出力する。また、データ入出力制御部６３は、コマンド制御部６１からの制御に基づいて、メンテナンスポートｄから入力されるマスクパターン情報を、マスク発生部６５に出力したり、マスク発生部６５から入力されたマスクパターンを、メンテナンスポートｄを介して外部の制御装置に出力する。
【００４７】
エラー検出処理部６４は、コマンド制御部６１からの制御に基づいて、データ入出力制御部６３から入力された検索対象データに、誤り検出訂正符号として、図５を参照して後述するＥＣＣ（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）方式の冗長ビットを付加する。そして、エラー検出処理部６４は、冗長ビットが付加された検索対象データを、エントリデータとしてＣＡＭブロック６６に登録する。なお、このようなエラー検出処理部６４の処理は、ＥＣＣエンコードとも称されている。
【００４８】
また、エラー検出処理部６４は、コマンド制御部６１からの制御に基づいて、ＣＡＭブロック６６に登録されているエントリデータを読み出し、エントリデータの冗長ビットを用いて、エントリデータの検索対象データの誤り検出訂正処理を実行する。なお、このようなエラー検出処理部６４の処理は、ＥＣＣデコードとも称されている。そして、エラー検出処理部６４は、誤りが訂正された検索対象データに、再度、冗長ビットを付加して、エントリデータとしてＣＡＭブロック６６に書き戻すとともに、誤りが訂正された検索対象データを、データ入出力制御部６３を介して、メンテナンスポートｄに出力する。
【００４９】
エラー検出処理部６４は、ＣＡＭブロック６６から読み出したエントリデータの誤りが訂正できなかった場合、エントリデータに誤りがあることを示す通知とともに、そのエントリデータのＣＡＭブロック６６におけるアドレスを、エラー通知ポートｅから外部の制御装置などに通知する。また、このとき、エラー検出処理部６４は、エントリデータのＣＡＭブロック６６におけるアドレスを内部レジスタ（図示せず）に保持するようにしてもよい。
【００５０】
マスク発生部６５は、データ入出力制御部６３より入力されたマスクパターン情報に基づいて、ＣＡＭブロック６６へのエントリデータの書き込みの１ビットごとのマスクをしたり、検索する際に、ＣＡＭブロック６６に登録されているエントリデータのうちのマスクする（検索対象から外す）部分を指示するマスクパターンを発生させ、発生させたマスクパターンを、コマンド制御部６１からの制御に基づいて、ＣＡＭブロック６６に供給する。また、マスク発生部６５は、発生させたマスクパターンを、データ入出力制御部６３を介して、メンテナンスポートｄに出力する。
【００５１】
ＣＡＭブロック６６は、１または複数のＣＡＭにより構成されている。なお、いまの場合、説明の便宜上、ＣＡＭブロック６６を１つのＣＡＭとして説明する。ＣＡＭブロック６６は、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などからなる記憶部７１と、Ｍａｔｃｈ  Ｄｅｔｅｃｔｏｒなどからなる検索部７２により構成される。記憶部７１には、エラー検出処理部６４より検索対象データに冗長ビットが付加されて構成されるエントリデータが登録される。
【００５２】
図４は、ＣＡＭブロック６６の記憶部７１の構成例を示している。なお、図４の例の場合、記憶部７１は、エントリ１、エントリ２、…、エントリ２５６ｋの２５６ｋエントリと、各エントリに対応する１８ビットのアドレスにより構成される。各エントリには、所定のワード長のエントリデータが登録される。
【００５３】
図５は、記憶部７１に登録されているエントリの構成例を示す。図５の例の場合、エントリは、メンテナンスポートｄより検索装置５１に入力され、エラー検出処理部６４により登録される検索対象データと、エラー検出処理部６４により検索対象データに付加されるＥＣＣ（冗長ビット）からなるエントリデータ、およびエンプティビットにより構成される。検索対象データは、例えば、検索装置５１がルータなどのネットワーク装置に内蔵される場合には、ＭＡＣアドレスやＩＰアドレスなどにより構成される。
【００５４】
検索装置５１においては、誤り検出訂正符号には、ＥＣＣ（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）方式のＳＥＣ／ＤＥＤ（Ｓｉｎｇｌｅ  ｂｌｏｃｋ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  ／  Ｄｏｕｂｌｅ  ｂｌｏｃｋ  Ｅｒｒｏｒ  Ｄｅｔｅｃｔｉｏｎ）コードが用いられる。ＳＥＣ／ＤＥＤコードの場合、冗長ビット長（ｋ）は、検索対象データのデータ長をｍとすると、式（１）で求められる。
【００５５】
２ｋ−１−１≧ｍ＋ｋ                                    ・・・（１）
【００５６】
したがって、図５の例の場合、検索対象データビットは、７２ビット（正確には、後述するエンプティビットがあるため７３ビット）のため、冗長ビットは、８ビットとなり、ＣＡＭブロック６６の記憶部７１のワード長は、８０ビット（エンプティビットを含めると８１ビット）とされる。
【００５７】
エンプティビットは、エントリに、検索時に有効なエントリデータが書き込まれているか否か、すなわち、このエントリデータが検索時に検索対象とされるか否かを示すデータである。検索装置５１の電源投入時やリセット時、エラー検出処理部６４は、すべてのエントリのエンプティビットを「１」に設定し、検索対象として無効状態にさせる。エラー検出処理部６４は、ＣＡＭブロック６６に、冗長ビットが付加された検索対象データを、エントリデータとして書き込むと、そのエントリのエンプティビットを「０」に設定し、エントリデータの登録されたエントリを、検索対象として有効状態にさせる。
【００５８】
これにより、ＣＡＭブロック６６の検索部７２は、記憶部７１のエントリのエンプティビットおよびマスク発生部６５より供給されたマスクパターンに基づいて、キーデータ生成部６２より入力された検索キーデータ（７２ビット）を、記憶部７１に登録されているエントリデータの中から検索する。すなわち、検索部７２は、エンプティビットに基づいて、記憶部７１に登録されているエントリデータの中から、有効状態である（検索対象となる）エントリデータを求める。そして、検索部７２は、マスク発生部６５より供給されたマスクパターンに基づいて、有効状態であるエントリデータのうちの冗長ビット（８ビット）をマスク部分とし、エントリデータ（８０ビット）のうちの検索対象データ（７２ビット）の中から、検索キーデータ（７２ビット）に一致するエントリデータを検索する。
【００５９】
検索部７２は、入力された検索キーデータに一致するエントリデータが、記憶部７１にあった場合、検索結果データ（２０ビット）を、検索結果出力部６７に出力する。検索結果データは、検索キーデータに一致するエントリデータがあったことを示すヒット（ＨＯＮ）信号（１ビット）、検索キーデータに一致するエントリデータが複数あったことを示すマルチヒット（ＭＨＯＮ）信号（１ビット）、および、検索キーデータに一致するエントリデータのアドレスのうち最も小さい（優先度が高い）アドレスを示すヒットアドレス（ＨＨＡ（Ｈｉｇｈｅｓｔ  Ｈｉｔ  Ａｄｄｒｅｓｓ））信号（１８ビット）により構成される。
【００６０】
検索結果出力部６７は、ＣＡＭブロック６６からの検索結果データを、出力ポートｆを介して、外部の装置へ出力する。リフレッシュ要求部６８は、エラー検出処理部６４によるエントリデータの誤り検出訂正処理を、ＣＡＭブロック６６に登録されているすべてのエントリのエントリデータに対して実行するときに、リフレッシュコマンドをコマンド制御部６１に出力する。
【００６１】
図６は、図３のエラー検出処理部６４の構成例を示す。図６の例においては、エラー検出処理部６４は、ＥＣＣエンコーダ８１、ＥＣＣデコーダ８２およびエラー通知部８３により構成される。
【００６２】
ＥＣＣエンコーダ８１は、コマンド制御部６１からの制御に基づいて、データ入出力制御部６３から供給された検索対象データをＥＣＣエンコードすることにより、検索対象データに８ビットの冗長ビットを付加する。そして、ＥＣＣエンコーダ８１は、冗長ビットが付加された検索対象データを、エントリデータとしてＣＡＭブロック６６の記憶部７１に登録する。また、ＥＣＣエンコーダ８１は、ＥＣＣデコーダ８２により誤りが訂正された検索対象データを再度ＥＣＣエンコードし、エントリデータとしてＣＡＭブロック６６の記憶部７１の対応するエントリに登録する。さらに、ＥＣＣエンコーダ８１は、ＥＣＣデコーダ８２により検索対象データの誤りが訂正されなかった場合、そのエントリデータが登録される記憶部７１のエントリのエンプティビット「１」に設定し、無効状態にする。
【００６３】
ＥＣＣデコーダ８２は、コマンド制御部６１からの制御に基づいて、ＣＡＭブロック６６の記憶部７１に登録されているエントリデータを読み出し、エントリデータをＥＣＣデコードする。すなわち、ＥＣＣデコーダ８２は、エントリデータの冗長ビットを用いて、エントリデータの検索対象データの誤り検出訂正処理を実行する。ＥＣＣ方式のＳＥＣ／ＤＥＤコードの場合、冗長ビットが用いられることにより、エントリデータの１ビットの誤りの訂正および２ビットエラーの検出が行われる。
【００６４】
したがって、ＥＣＣデコーダ８２は、冗長ビットを用いて、検索対象データにおいて、１ビットの誤りを検出した場合、冗長ビットを用いて、検索対象データの１ビットの誤りを訂正し、訂正された検索対象データを、データ入出力制御部６３およびＥＣＣエンコーダ８１に出力する。また、ＥＣＣデコーダ８２は、検索対象データにおいて、冗長ビットを用いて、２ビットの誤りを検出した場合、ＥＣＣデコーダ８２は、２ビットの誤りを訂正することができないので、そのエントリデータに誤りがあるという通知とともに、エントリデータが登録されている記憶部７１のエントリのアドレスを、エラー通知部８３に出力する。また、このとき、ＥＣＣデコーダ８２は、エントリデータが登録されている記憶部７１のエントリのアドレスを内部レジスタに保持するようにしてもよい。
【００６５】
エラー通知部８３は、コマンド制御部６１からの制御に基づいて、ＥＣＣデコーダ８２からの、エントリデータに誤りがあるという通知とともに、エントリデータが登録されている記憶部７１のエントリのアドレスを、エラー通知ポートｅから外部の制御装置などに通知する。
【００６６】
次に、図７のフローチャートを参照して、検索装置５１の書き込み処理を説明する。
【００６７】
検索装置５１において検索処理を行うためには、ＣＡＭブロック６６の記憶部７１の各エントリに検索対象データを登録する必要がある。外部の制御装置は、検索対象データを登録する場合、コマンドポートｂを介してコマンド制御部６１に書き込みコマンドを入力し、同時に、メンテナンスポートｄを介してデータ入出力制御部６３に検索対象データを入力する。
【００６８】
コマンド制御部６１は、ステップＳ１において、コマンドポートｂを介して書き込みコマンドを受けたと判断するまで待機しており、コマンドポートｂを介して書き込みコマンドが入力されると、コマンドポートｂを介して書き込みコマンドを受けたと判断し、ステップＳ２に進み、データ入出力制御部６３を制御し、メンテナンスポートｄを介して入力された検索対象データ（７２ビット）を、エラー検出処理部６４のＥＣＣエンコーダ８１に出力させ、ステップＳ３に進む。
【００６９】
ステップＳ３において、ＥＣＣエンコーダ８１は、コマンド制御部６１の制御に基づいて、データ入出力制御部６３からの検索対象データをＥＣＣエンコードすることにより、８ビットの冗長ビットを付加し、ステップＳ４に進む。ステップＳ４において、ＥＣＣエンコーダ８１は、冗長ビットが付加された検索対象データを、エントリデータ（８０ビット）として、記憶部７１の所定のエントリに書き込み、検索装置５１の書き込み処理を終了する。なお、このとき、ＥＣＣエンコーダ８１は、登録されたエントリのエンプティビットを「０」に設定し、有効状態にさせる。
【００７０】
以上のようにして、ＣＡＭブロック６６の記憶部７１のエントリに、冗長ビットが付加された検索対象データ（エントリデータ）が登録される。
【００７１】
次に、図８のフローチャートを参照して、検索装置５１における登録されたエントリデータの読み出し処理について説明する。
【００７２】
検索装置５１においては、ＣＡＭブロック６６の記憶部７１の任意のエントリのエントリデータを読み出してメンテナンスを行う場合がある。図示せぬ外部の制御装置は、エントリデータを読み出す場合、コマンドポートｂを介してコマンド制御部６１に読み出しコマンドを入力する。
【００７３】
コマンド制御部６１は、ステップＳ２１において、コマンドポートｂを介して読み出しコマンドを受けたと判断するまで待機しており、コマンドポートｂを介して読み出しコマンドが入力されると、コマンドポートｂを介して読み出しコマンドを受けたと判断し、ステップＳ２２に進み、エラー検出処理部６４のＥＣＣデコーダ８２を制御し、ＣＡＭブロック６６の記憶部７１に登録されている、冗長データが付加されたエントリデータ（８０ビット）を読み出させ、ステップＳ２３に進む。
【００７４】
ＥＣＣデコーダ８２は、ステップＳ２３において、コマンド制御部６１の制御に基づいて、読み出したエントリデータをＥＣＣデコードする。すなわち、エントリデータの冗長データに基づいて、エントリデータの検索対象データの誤り検出訂正処理を実行し、ステップＳ２４に進む。いまの場合、ＥＣＣ機能のＳＥＣ／ＤＥＤコードの冗長ビットが用いられているので、エントリデータの１ビットの誤りの訂正および２ビットエラーの検出が行われる。
【００７５】
ＥＣＣデコーダ８２は、ステップＳ２４において、検索対象データから１ビット誤りが検出されたか、または、検索対象データから誤りが検出されなかったか否かを判断し、検索対象データから１ビット誤りが検出された、または、検索対象データから誤りが検出されなかったと判断した場合、誤り検出訂正処理により１ビットの誤りが訂正されているので、１ビットの誤りが訂正された検索対象データ（または、誤りがなかった検索対象データ）をＥＣＣエンコーダ８１に出力し、ステップＳ２５に進む。ステップＳ２５において、ＥＣＣエンコーダ８１は、ＥＣＣデコーダ８２から入力される検索対象データを再度ＥＣＣエンコードすることにより、冗長データを付加し、冗長データが付加されたエントリデータを、ＣＡＭブロック６６の記憶部７１の対応するエントリに書き戻し、ステップＳ２８に進む。
【００７６】
一方、ステップＳ２４において、検索対象データから１ビット誤りが検出されず、および、検索対象データから誤りが検出されたと判断された場合、すなわち、検索対象データに、２ビットの誤りが検出されたと判断された場合、ＥＣＣデコーダ８２は、２ビットの誤りを訂正することができないので、ステップＳ２６に進み、エラー通知部８３およびエラー通知ポートｅを介して、このエントリデータに誤りがあるという通知とともに、エントリデータが登録されている記憶部７１のエントリのアドレスを、外部の制御装置などに通知し、ステップＳ２７に進む。なお、このとき、ＥＣＣデコーダ８２は、エントリデータが登録されている記憶部７１のエントリのアドレスを内部レジスタ（図示せず）に保持する。ステップＳ２７において、ＥＣＣエンコーダ８１は、エントリデータが登録されている記憶部７１のエントリのアドレスのエンプティビットを「１」に書き換え、このエントリを検索対象として無効状態にさせ、ステップＳ２８に進む。
【００７７】
ステップＳ２８において、ＥＣＣデコーダ８２は、訂正された検索対象データ、誤りが検出されなかった検索対象データ、または、２つの誤りが検出された検索対象データを、データ入出力制御部６３およびメンテナンスポートｄを介して外部の制御装置などに出力し、検索装置５１の読み出し処理を終了する。
【００７８】
以上のように、登録されているエントリデータを読み出し、エントリデータの冗長ビットを用いて、検索対象データの誤り検出訂正処理を行い、誤りが訂正された検索対象データをエントリデータとして、記憶部７１に書き戻すようにしたので、アルファ線によるソフトエラーが生じたとしても、正しいエントリデータを記憶部７１に保持することができる。これにより、アルファ線によるソフトエラーが生じたとしても、検索装置５１の図９を参照して後述する検索処理において、誤った検索結果を得ることが抑制される。
【００７９】
また、検索対象データから２ビットの誤りを検出した場合、検索対象データ（エントリデータ）に誤りがあるという通知とともに、エントリデータが登録されている記憶部７１のエントリのアドレスを外部に通知するようにしたので、外部の制御装置において、誤りを訂正し、訂正された検索対象データをメンテナンスポートｄより再び記憶部７１に書き戻すことができる。
【００８０】
さらに、検索対象データから２ビットの誤りを検出した場合、エントリデータが登録されている記憶部７１のエントリのエンプティビットを無効状態「１」に設定するようにしたので、アルファ線によるソフトエラーが生じたとしても、検索装置５１の検索処理において、間違った検索結果を得ることが抑制される。
【００８１】
次に、図９のフローチャートを参照して、検索装置５１における検索処理を説明する。
【００８２】
検索装置５１において、検索処理を実行する場合、コマンドポートｂを介してコマンド制御部６１に検索コマンドが入力されるので、コマンド制御部６１は、検索コマンドに従って、検索装置５１の各部を制御する。また、検索コマンドが入力されるのと同時に、入力ポートａから検索キーデータ（７２ビット）がキーデータ生成部６２に入力されている。
【００８３】
コマンド制御部６１は、ステップＳ４１において、コマンドポートｂを介して検索コマンドを受けたと判断するまで待機しており、コマンドポートｂを介して検索コマンドが入力されると、コマンドポートｂを介して検索コマンドを受けたと判断し、ステップＳ４２に進み、キーデータ生成部６２を制御し、検索キーデータを、ＣＡＭブロック６６の検索部７２に入力させ、ステップＳ４３に進む。
【００８４】
コマンド制御部６１は、ステップＳ４３において、マスク発生部６５を制御し、予めメンテナンスポートｄおよび入出力制御部６３を介して入力されているマスクパターン情報に基づいて発生されたマスクパターンを、ＣＡＭブロック６６の検索部７２に入力させ、ステップＳ４４に進む。
【００８５】
検索部７２は、キーデータ生成部６２より検索キーデータが入力され、マスク発生部６５よりマスクパターンが入力されると、ステップＳ４４において、マスクパターンに基づいて、記憶部７１に登録されているエントリデータの中から検索キーデータを検索する。具体的には、検索部７２は、記憶部７１のエントリのエンプティビットに基づいて、検索対象となるエントリデータを求め、マスク発生部６５より供給されたマスクパターンに基づいて、エントリデータのうちの冗長ビット（８ビット）をマスク部分とし、エントリデータ（８０ビット）のうちの検索対象データ（７２ビット）の中から、検索キーデータ（７２ビット）に一致する検索対象データを検索し、ステップＳ４５に進む。
【００８６】
検索部７２は、入力された検索キーデータに一致する検索対象データのエントリが、記憶部７１にあった場合、ステップＳ４５において、検索結果データ（２０ビット）を、検索結果出力部６７および出力ポートｆを介して、図示せぬ外部の装置へ出力し、検索装置５１の検索処理を終了する。出力された検索結果データは、外部装置など後段の処理に用いられる。
【００８７】
以上のように、マスクパターンを用いることによりエントリデータに付加された冗長ビットを検索対象から外すことができ、冗長ビットが付加されていても、冗長ビットが付加されていない場合と同様の検索処理を実行することができる。さらに、冗長ビットが付加されることにより、エントリデータの誤り検出訂正がされるので、外部装置など後段においては、アルファ線などのソフトエラーの影響による誤った検索結果データが入力されることが抑制される。
【００８８】
次に、図１０のフローチャートを参照して、検索装置５１のリフレッシュ処理について説明する。なお、図１０のステップＳ６５乃至Ｓ６９の処理は、図８のステップＳ２３乃至Ｓ２７の処理と基本的に同様であり繰り返しになるので、その説明の詳細は省略する。
【００８９】
記憶部７１に登録されているエントリデータの誤り検出訂正処理は、図８を参照して上述した読み出し処理において実行されたが、この場合、すべてのエントリデータが読み出されて誤り検出訂正されるとは限らないので、記憶部７１の中に全くアクセスされないエントリデータが生じる恐れがある。したがって、通常のＤＲＡＭのリフレッシュ処理と同様に、一定時間内に、すべての対象となるエントリデータを読み出して、冗長ビットを用いて、検索対象データの誤り検出訂正を実行する場合に、リフレッシュ要求部６８は、リフレッシュコマンドを発生し、コマンド制御部６１に出力する。
【００９０】
そこで、コマンド制御部６１は、図１０のステップＳ６１において、リフレッシュ要求部６８からリフレッシュコマンドを受けたと判断するまで待機しており、リフレッシュ要求部６８からリフレッシュコマンドを受けたと判断した場合、ステップＳ６２に進む。
【００９１】
コマンド制御部６１は、ステップＳ６２において、ＥＣＣデコーダ８２を制御し、リフレッシュ対象アドレスのエントリのエントリデータを読み出させ、ステップＳ６３に進み、ＥＣＣデコーダ８２は、読み出されたエントリのエンプティビットが１（無効状態）であるか否かを判断し、読み出されたエントリのエンプティビットが１ではない（すなわち、エンプティビットが０（有効）である）と判断した場合、ステップＳ６４に進む。
【００９２】
ＥＣＣデコーダ８２は、ステップＳ６４において、コマンド制御部６１の制御に基づいて、読み出したエントリデータをＥＣＣデコードする。すなわち、ＥＣＣデコーダ８２は、冗長データに基づいて、検索対象データの誤り検出訂正処理を実行し、ステップＳ６５に進む。
【００９３】
ＥＣＣデコーダ８２は、ステップＳ６５において、検索対象データから１ビット誤りが検出されたか、または、検索対象データから誤りが検出されなかったか否かを判断し、検索対象データから１ビット誤りが検出された、または、検索対象データから誤りが検出されなかったと判断した場合、誤り検出訂正処理により１ビットの誤りが訂正されているので、１ビットの誤りが訂正された検索対象データ、または誤りがなかった検索対象データをＥＣＣエンコーダ８１に出力し、ステップＳ６６に進み、ＥＣＣエンコーダ８１は、ＥＣＣデコーダ８２からのエントリデータを再度ＥＣＣエンコードすることにより、冗長データを付加し、冗長データが付加されたエントリデータを、ＣＡＭブロック６６の記憶部７１に書き戻し、ステップＳ６９に進む。
【００９４】
一方、ステップＳ６５において、検索対象データから１ビット誤りが検出されず、および、検索対象データから誤りが検出されたと判断された場合、すなわち、検索対象データに、２ビットの誤りが検出されたと判断された場合、ＥＣＣデコーダ８２は、２ビットの誤りを訂正することができないので、ステップＳ６７に進み、エラー通知部８３およびエラー通知ポートｅを介して、検索対象データの誤りが訂正できないという通知とともに、検索対象データが対応するエントリのアドレスを、外部の制御装置などに通知し、ステップＳ６８に進む。なお、このとき、ＥＣＣデコーダ８２は、検索対象データが対応するエントリのアドレスを内部レジスタに保持する。ステップＳ６８において、ＥＣＣエンコーダ８１は、検索対象データが対応するエントリのアドレスのエンプティビットを「１」に書き換え、ステップＳ６９に進む。
【００９５】
一方、ステップＳ６３において、読み出されたエントリデータのエンプティビットが１（無効）であると判断された場合、コマンド制御部６１は、ステップＳ６４乃至Ｓ６８の処理をスキップし、ステップＳ６９に進む。すなわち、エントリデータが登録されていないエントリは、冗長ビットが書き込まれていないため、誤り検出訂正処理は行われない。
【００９６】
コマンド制御部６１は、ステップＳ６９において、リフレッシュ対象アドレスを１つインクリメントさせ、リフレッシュ処理を終了する。そして、次回、また、ステップＳ６１において、リフレッシュコマンドを受けたと判断された場合、コマンド制御部６１は、１つインクリメントされたリフレッシュ対象アドレスのエントリのエントリデータに対して、図１０のリフレッシュ処理を実行する。すなわち、結果的に、リフレッシュコマンドにより記憶部７１に登録されているすべてのエントリデータに対して、リフレッシュ処理（誤り検出訂正処理）が実行される。
【００９７】
以上のように、エントリデータが登録され、冗長ビットの書き込まれているエントリデータに対して、誤り検出訂正処理を実行するようにしたので、アルファ線によるソフトエラーが発生したとしても、誤った検出結果が出力されることが抑制される。
【００９８】
なお、上記説明においては、エンプティビットが「１」であるエントリデータに対しては、冗長ビットが書き込まれていないため、誤り検出訂正処理を実行しないようにしたが、ソフトエラーによりエンプティデータそのものが書き換わってしまっている恐れがあるため、エンプティデータが「１」のエントリのエントリデータも誤り検出訂正処理を行うようにしてもよい。なお、その場合には、図１０のステップＳ６３の処理は実行されない。
【００９９】
また、上記説明においては、リフレッシュ要求部６８からコマンド制御部６１に対してリフレッシュコマンドを出力し、コマンド制御部６１によりＣＡＭブロック６６の検索、書き込み、および読み出し処理の排他制御を行っているが、検索装置５１の内部にタイマ機能を設け、タイマが所定の期間が経過したと判断した場合に、図１０のリフレッシュ処理を実行させるようにしてもよい。なお、この場合には、リフレッシュ処理と、検索、書き込みおよび読み出し処理との競合を避けるために、キーデータ生成部６２およびデータ入出力制御部６３などの内部にバッファを設け、入力される検索キーデータやエントリデータを一時的に蓄積し、検索、書き込みおよび読み出し処理を一時的に待機させるようにする。
【０１００】
さらに、上述した説明においては、冗長ビットとして、誤り検出訂正符号のＥＣＣ機能のＳＥＣ／ＤＥＤコードが用いられているが、１ビットの誤り訂正のみの符号や、拡張ＥＣＣ機能のＳ４ＥＣ−Ｄ４ＥＤ（Ｓｉｎｇｌｅ  ４ｂｉｔ  ｂｌｏｃｋ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  −  Ｄｏｕｂｌｅ  ４ｂｉｔ  ｂｌｏｃｋ  Ｅｒｒｏｒ  Ｄｅｔｅｃｔｉｏｎ）の誤り訂正符号を用いるようにしてもよい。また、誤り検出訂正符号ではなく、図１１に示されるように、誤り検出符号であるパリティ符号を用いるようにしてもよい。
【０１０１】
図１１は、記憶部７１に登録されるエントリの構成例を示す。図１１のエントリにおいては、検索対象データに付加される冗長ビットとして、図５のＥＣＣの代わりに、パリティ符号が用いられている。したがって、図１１の例の場合、エントリは、検索対象データとパリティ符号からなるエントリデータおよびエンプティビットにより構成される。
【０１０２】
このように、検索対象データに付加される冗長ビットとして、パリティ符号が付加されることにより、検索対象データの誤りを訂正することはできないが、検索対象データの誤りを検出することができるため、エラー通知部８３により誤りのある検索対象データが対応するエントリのアドレスを外部の制御装置に通知することができる。
【０１０３】
これにより、外部の制御装置において訂正された検索対象データを、再度エントリデータとして書き戻すことができるので、ソフトエラーにより記憶部７１に登録されているエントリデータが書き換わることにより、誤った検索結果データが出力されることが抑制される。
【０１０４】
以上のように、ＣＡＭに登録される検索対象データに誤り検出訂正符号を付加し、誤り検出訂正符号を用いて、自己回復させるようにしたので、アルファ線などによるソフトエラーが生じたとしても、ＣＡＭにおいて、誤った検索結果が出力されることが抑制される。なお、ソフトエラーを気にしない場合には、エントリデータにおける誤り訂正符号分（８ビット）の分も、検索対象データ（８０ビット）として設定するようにしてもよい。この場合には、８０ビットを用いた検索処理が実行できる。
【０１０５】
なお、本発明の検索装置５１は、ルータなどのネットワーク装置にも適用することもできる。
【０１０６】
上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。この場合、例えば、図３の検索装置５１は、図１２に示されるような検索装置１０１により構成される。
【０１０７】
図１２において、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）  １１２に記憶されているプログラム、または、記憶部１１９からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１１３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ１１３にはまた、ＣＰＵ１１１が各種の処理を実行する上において必要なデータなどが適宜記憶される。
【０１０８】
ＣＰＵ１１１、ＲＯＭ１１２、およびＲＡＭ１１３は、バス１１４を介して相互に接続されている。このバス１１４にはまた、ＣＡＭ１１５および入出力インタフェース１１６も接続されている。
【０１０９】
ＣＡＭ１１５には、各種データが登録されている。ＣＡＭ１１５は、入力部１１７または通信部１２０などから入力されたデータを、登録されているデータの中から検索し、検索結果データとして、登録されているデータのアドレスを出力する。
【０１１０】
入出力インタフェース１１６には、キーボード、マウスなどよりなる入力部１１７、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ），ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）などよりなるディスプレイ、並びにスピーカなどよりなる出力部１１８、ハードディスクなどより構成される記憶部１１９、モデム、ターミナルアダプタなどより構成される通信部１２０が接続されている。通信部１２０は、図示せぬネットワークを介しての通信処理を行う。
【０１１１】
入出力インタフェース１１６にはまた、必要に応じてドライブ１３０が接続され、磁気ディスク１３１、光ディスク１３２、光磁気ディスク１３３、或いは半導体メモリ１３４などが適宜装着され、それから読み出されたコンピュータプログラムが、必要に応じて記憶部１１９にインストールされる。
【０１１２】
一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば、汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１１３】
この記録媒体は、図１２に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク１３１（フレキシブルディスクを含む）、光ディスク１３２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）を含む）、光磁気ディスク１３３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）（商標）を含む）、もしくは半導体メモリ１３４などよりなるパッケージメディアにより構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ１１２や、記憶部１１９に含まれるハードディスクなどで構成される。
【０１１４】
なお、本明細書において、フローチャートに示されるステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１１５】
【発明の効果】
以上の如く、本発明によれば検索処理の信頼性を向上することができる。
【図面の簡単な説明】
【図１】ＣＡＭのセルの構成例を示す図である。
【図２】従来のメモリ装置の構成例を示すブロック図である。
【図３】本発明を適用した検索装置の構成例を示すブロック図である。
【図４】図３の記憶部の構成例を示す図である。
【図５】図４のエントリの構成例を示す図である。
【図６】図３のエラー検出処理部の構成例を示す図である。
【図７】図３の検索装置の書き込み処理を説明するフローチャートである。
【図８】図３の検索装置の読み出し処理を説明するフローチャートである。
【図９】図３の検索装置の検索処理を説明するフローチャートである。
【図１０】図３の検索装置のリフレッシュ処理を説明するフローチャートである。
【図１１】図４のエントリの他の構成例を示す図である。
【図１２】本発明を適用した検索装置の他の構成例を示すブロック図である。
【符号の説明】
５１  検索装置，６１  コマンド制御部，６２  キーデータ生成部，６３  データ入出力制御部，６４  エラー検出処理部，６５  マスク発生部，６６  ＣＡＭブロック，６７  検索結果出力部，６８  リフレッシュ要求部，７１  記憶部，７２  検索部，８１  ＥＣＣエンコーダ，８２  ＥＣＣデコーダ，８３  エラー通知部
【図１】
2004362315.tif 000003
【図２】
2004362315.tif 000004
【図３】
2004362315.tif 000005
【図４】
2004362315.tif 000006
【図５】
2004362315.tif 000007
【図６】
2004362315.tif 000008
【図７】
2004362315.tif 000009
【図８】
2004362315.tif 000010
【図９】
2004362315.tif 000011
【図１０】
2004362315.tif 000012
【図１１】
2004362315.tif 000013
【図１２】
2004362315.tif 000014