(57)【要約】論理回路は、マッチングアルゴリズムファンクションを実行する。メモリは、どのメモリセルが、入力アドレスデータをメモリにマッチするデータを含むかを示す、マッチ信号を形成する。第一論理積ファンクションは、入力アドレスデータに対してメモリにより現在形成されるマッチ信号の現在値と、直前入力アドレスデータにより形成されるマッチ信号の前値との、論理積をとる。バッファは、インデックスデータを保持する。第二論理積ファンクションは、第一論理積ファンクションの出力をインデックスデータと比較する。第二論理積ファンクションの出力は、バッファに新しいインデックスデータとして戻される。インデックス論理は、オフセットを、バッファに記憶されるインデックスデータとして生成する。送信バイトファンクションは、送信バイト信号を、マッチ信号が、ゼロの時と、第二論理積ファンクションの出力が、ゼロの時にアサートする。レングスカウンタは、送信バイト信号が、アサートされないサイクル毎にインクリメントされる。
2004507858.tif 000002
【特許請求の範囲】
【請求項１】
先入れ先出し（ＦＩＦＯ）連想記憶装置（ＣＡＭ）であって、
ＣＡＭアドレス信号を受信するためのアドレス入力と、
タイル状に集結された複数のＣＡＭセルと、
を備え、
前記各ＣＡＭセルは、
前記アドレス入力に接続され、ＣＡＭアドレス信号を受信するためのセルアドレス入力と、
前記ＣＡＭセルに記憶されるデータを受信するためのデータ入力と、
データ入力にて受信されるデータを記憶するための記憶論理と、
出力として記憶論理に記憶されるデータを提供するためのデータ出力と、
前記ＣＡＭセルに記憶されるデータをＣＡＭアドレス信号と比較するためのマッチ論理であって、前記ＣＡＭセルに記憶されるデータが、ＣＡＭアドレス信号とマッチする時を示すマッチ信号を形成するマッチ論理と、
を備え、
前記ＣＡＭセルは、一のＣＡＭセルに対するデータ出力を他のＣＡＭセルに対するデータ入力に結合することにより、タイル状に集結されることを特徴とする連想記憶装置。
【請求項２】
請求項１に記載のＦＩＦＯ　ＣＡＭにおいて、前記記憶論理は、複数のフリップフロップを用いて実現されることを特徴とする連想記憶装置。
【請求項３】
請求項１に記載のＦＩＦＯ　ＣＡＭにおいて、前記マッチ論理は、
複数のＸＮＯＲゲートであって、それぞれが、入力として、ＣＡＭセルに記憶されるデータビットとＣＡＭアドレス信号のビットを受信する複数のＸＮＯＲゲートと、
否定論理積ファンクションを全複数ＸＮＯＲゲートからの出力に対して行うためのＮＡＮＤゲートと、
を含むことを特徴とする連想記憶装置。
【請求項４】
請求項１に記載のＦＩＦＯ　ＣＡＭにおいて、前記各ＣＡＭセルは、
ＣＡＭセルに記憶されるデータが、有効かどうかを示す有効ビットを受信するための有効入力と、
有効ビットを記憶するための有効記憶装置と、
出力として有効記憶装置に記憶される有効ビットを提供するための有効出力と、
をさらに備えることを特徴とする連想記憶装置。
【請求項５】
マッチングアルゴリズムファンクションを実行する論理回路であって、
どのメモリセルが、入力アドレスデータをメモリにマッチするデータを含むかを示す、マッチ信号を形成するメモリと、
入力アドレスデータに対してメモリにより現在形成されるマッチ信号の現在値と、直前の入力アドレスデータにより形成されるマッチ信号の前値との、論理積をとる第一論理積ファンクションと、
インデックスデータを保持するためのバッファと、
第一論理積ファンクションの出力とインデックスデータを比較する第二論理積ファンクションであって、当該第二論理積ファンクションの出力は、バッファに新しいインデックスデータとして戻される、第二論理積ファンクションと、
オフセットを、バッファに記憶されるインデックスデータに基づいて、生成するためのインデックスと、
マッチ信号が、ゼロの時と、第二論理積ファンクションの出力が、ゼロの時に、送信バイト信号をアサートするための送信バイトファンクションと、
送信バイト信号が、アサートされないサイクル毎に、インクリメントされるレングスカウンタと、
を備えることを特徴とする論理回路。
【請求項６】
請求項５に記載の論理回路において、前記メモリは、先入れ先出し連想記憶装置であることを特徴とする論理回路。
【請求項７】
請求項５に記載の論理回路において、
第二論理積ファンクションの出力が、論理１にセットされた１ビットのみを有する時に、オフセットレディ信号を生成するためのオフセットレディ論理を、
さらに備えることを特徴とする論理回路。
【請求項８】
請求項５に記載の論理回路において、
前値を第一論理積ファンクションにより受信する前に、前値を１ビットシフトするための第一シフトファンクションと、
インデックスデータを第二論理積ファンクションにより受信する前に、インデックスデータを１ビットシフトするための第二シフトファンクションと、
をさらに備えることを特徴とする論理回路。
【請求項９】
請求項５に記載の論理回路において、
送信バイト信号が、アサートされた直後のサイクルにおいて、第二論理積ファンクションへの入力として、インデックス論理をすべて論理１に置換するための置換論理を、
さらに備えることを特徴とする論理回路。
【請求項１０】
先入れ先出し（ＦＩＦＯ）連想記憶装置（ＣＡＭ）を提供するための方法であって、
（ａ）ＣＡＭアドレス信号を複数の各ＣＡＭセルに与える工程であって、ＣＡＭセルは、一のＣＡＭセルに対するデータ出力を他のＣＡＭセルに対するデータ入力に結合することにより、タイル状に集結されている工程と、
（ｂ）複数のＣＡＭセルの各ＣＡＭセルに対して、以下のサブ工程を行う工程と、
を備え、そのサブ工程は、
（ｂ．１）ＣＡＭアドレス信号を受信する工程と、
（ｂ．２）ＣＡＭセルに記憶されるデータをＣＡＭアドレス信号と比較し、ＣＡＭセルに記憶されるデータが、ＣＡＭアドレス信号とマッチしたことを示すマッチ信号を形成する工程と、
（ｂ．３）出力としてＣＡＭセルに記憶されるデータを提供する工程と、
（ｂ．４）ＣＡＭセルに記憶される新しいデータを受信する工程と、
を備えることを特徴とする方法。
【請求項１１】
請求項１０に記載の方法において、サブ工程（ｂ．２）では、ＣＡＭセルに記憶されるデータは、複数のフリップフロップに記憶されることを特徴とする方法。
【請求項１２】
請求項１０に記載の方法において、サブ工程（ｂ．２）は、
ＣＡＭセルに記憶されるデータの各ビットと、ＣＡＭアドレス信号の対応ビットとの、ＸＮＯＲをとる工程と、
ＸＮＯＲをとることにより形成されたすべての結果からの出力に対して否定論理積ファンクションを実行する工程と、
を含むことを特徴とする方法。
【請求項１３】
請求項１０に記載の方法において、
サブ工程（ｂ．３）は、出力データが、有効かどうかを示す有効ビットを提供する工程を含み、
サブ工程（ｂ．４）は、新しい有効ビットを新しいデータと共に受信する工程を含む、
ことを特徴とする方法。
【請求項１４】
マッチングアルゴリズムファンクションを実行する方法であって、
（ａ）複数のデータ値をメモリに記憶する工程と、
（ｂ）メモリにアドレスするのに使用される入力アドレスデータに応じて、どのメモリセルが、入力アドレスデータとマッチするデータを含むかを示す、マッチ信号を形成する工程と、
（ｃ）マッチ信号の現在値と、直前の入力アドレスデータにより形成されるマッチ信号の前値との、論理積をとる工程と、
（ｄ）論理積ファンクションを実行して、工程（ｃ）で実行された論理積の結果をインデックスデータと比較する工程と、
（ｅ）工程（ｃ）で実行された論理積の結果を新しいインデックスデータとして記憶する工程と、
（ｆ）工程（ｅ）において記憶されたインデックスデータに基づき、オフセットを生成する工程と、
（ｇ）工程（ｂ）で形成されたマッチ信号が、ゼロの時と、工程（ｃ）で実行された論理積の結果が、ゼロの時に、送信バイト信号をアサートする工程と、
（ｈ）送信バイト信号がアサートされないサイクル毎に、レングスをインクリメントする工程と、
を備えることを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、工程（ａ）では、メモリが、先入れ先出し連想記憶装置であることを特徴とする方法。
【請求項１６】
請求項１４に記載の方法において、
（ｉ）工程（ｅ）において論理積の実行により、論理１にセットされた１ビットのみとなる時に、オフセットレディ信号を生成する工程を、
さらに含むことを特徴とする方法。
【請求項１７】
請求項１４に記載の方法において、
工程（ｃ）は、論理積ファンクションを実行する前に、前値を１ビットシフトする工程を含み、
工程（ｄ）は、論理積ファンクションを実行する前に、インデックスデータを１ビットシフトする工程を含む、
ことを特徴とする方法。
【請求項１８】
請求項１４に記載の方法において、
工程（ｄ）は、送信バイト信号がアサートされた直後のサイクルにおいて、論理積ファンクションを実行する前に、インデックス論理をすべて論理１に置換する工程を、
含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
（背景）
本発明は、データの圧縮および解凍に関する。特に、本発明は、効率的な圧縮アルゴリズムのハードウエアにおける実現に関する。
【０００２】
データ圧縮は、データを記憶または転送する時、冗長性がある場合に、使用できる。このような圧縮により、有効データサイズを、情報を損失することなく、減じることができる。情報密度は、増加して、より速い送信時間を可能にし、より少ない記憶装置資源を必要とする。
【０００３】
データコンプレッサの速度は、重要である。従って、データ圧縮アルゴリズムは、しばしば、データの圧縮および解凍に必要な時間を減らすために、ハードウエアにおてい実施される。
【０００４】
ＪａｃｏｂＺｉｖとＡｂｒａｈａｍＬｅｍｐｅｌは、２つの適応性のあるデータ圧縮機構を提案しており、それらは、前のデータ記号の特有ストリングを表すコードディクショナリを構成する。これらのアルゴリズムは、多くの変形を伴って実施されてきた。例えば、米国特許番号５、３３９、０７６、米国特許番号５、４５５、５７６、米国特許番号５、４６９、１６１、米国特許番号５３２、６９３、米国特許番号５、５３２、６９４、米国特許番号６４２、１１２、米国特許番号５、７７１、０１０、米国特許番号５、８１８、８７３、米国特許番号５、８２８、３２４、米国特許番号５、８７７、７１４、および、米国特許番号５、９３６、５６０における実施を参照できる。
【０００５】
（発明の要約）
本発明の実施形態に従い、論理回路は、マッチングアルゴリズムファンクションを実行する。メモリは、どのメモリセルが、入力アドレスデータをメモリにマッチするデータを含むかを示すマッチ信号を形成する。第一論理積ファンクションは、入力アドレスデータに対してメモリにより現在形成されるマッチ信号の現在値と、直前入力アドレスデータにより形成されるマッチ信号の前値との、論理積をとる。バッファは、インデックスデータを保持する。第二論理積ファンクションは、第一論理積ファンクションの出力をインデックスデータと比較する。第二論理積ファンクションの出力は、バッファに新しいインデックスデータとして戻される。インデックス論理は、オフセットを、バッファに記憶されるインデックスデータとして生成する。送信バイトファンクションは、送信バイト信号を、マッチ信号が、ゼロの時と第二論理積ファンクションの出力が、ゼロの時にアサートする。レングスカウンタは、送信バイト信号が、アサートされないサイクル毎にインクリメントされる。
【０００６】
本発明の実施形態において、オフセットレディ論理は、第二論理積ファンクションの出力が、論理１にセットされた１ビットのみを有している時に、オフセットレディ信号を生成する。また、置換論理は、送信バイト信号が、アサートされる直後のサイクルにおいて、全論理１にインデックス論理を第二論理積ファンクションへの入力として置換する。
【０００７】
また、本発明の一実施形態では、メモリは、データをシフトしない連想記憶装置（ＣＡＭ）として実施される。この場合、第一シフトファンクションは、前値が、第一論理積ファンクションに受信される前に、前値を１ビットシフトする。また、第二シフトファンクションは、インデックスデータが、第二論理積ファンクションに受信される前に、インデックスデータを１ビットシフトする。これらの２つのファンクションは、メモリが、先入れ先出し（ＦＩＦＯ）ＣＡＭを用いて実施される時には、必要ない。
【０００８】
メモリは、ＦＩＦＯ　ＣＡＭを用いて実施できる。例えば、ＣＡＭは、ＣＡＭアドレス信号を受信するためのアドレス入力を含む。ＦＩＦＯ　ＣＡＭは、タイル状集結にされた複数のＣＡＭセルをも含む。
【０００９】
各ＣＡＭセルは、ＣＡＭアドレス信号を受信するためのセルアドレス入力を含む。データ入力は、ＣＡＭセルに記憶されるデータを受信する。記憶論理は、データ入力にて受信されるデータを記憶する。データ出力は、出力として、記憶論理に記憶されるデータを提供する。マッチ論理は、ＣＡＭセルに記憶されるデータをＣＡＭアドレス信号と比較する。マッチ論理は、ＣＡＭセルに記憶されるデータが、ＣＡＭアドレス信号とマッチングする時を示す、マッチ信号を形成する。ＣＡＭセルは、１ＣＡＭセルに対するデータ出力を他のＣＡＭセルに対するデータ入力に結合することにより、タイル状に集結される。
【００１０】
一実施形態において、記憶装置ユニットは、複数のフリップフロップを用いて実施される。マッチ論理は、複数のＸＮＯＲゲートとＮＡＮＤゲートを含む。各ＸＮＯＲゲートは、入力として、ＣＡＭセルに記憶されるデータのビットと、ＣＡＭアドレス信号のビットを受信する。ＮＡＮＤゲートは、全複数ＸＮＯＲゲートからの出力に対して、否定論理積ファンクションを実行する。また、ＣＡＭセルは、ＣＡＭセルに記憶されるデータが、有効かどうかを示す有効ビットを受信するための有効入力をもさらに含むことができる。有効ビットは、ＣＡＭセルに記憶され、出力として対応データと共に提供される。
【００１１】
本発明により、損失の少ない圧縮アルゴリズムを効率的にハードウエアにおいて実施することができ、それは、ＡＮＳＩＸ３．２４１−１９９４仕様（ＳｔａｃｋｅｒＬＺＳ．ＴＭ．として既知）と互換性がある。
【００１２】
（実施形態の説明）
図１は、圧縮エンジン１０のブロックインターフェースである。インターフェースは、１ビットクロック（ＣＬＫ）入力１１と、１ビットリセット（ＲＳＴ＿Ｎ）入力１２と、１ビット圧縮入力１３と、１ビット書き込み入力１４と、４ビット最終（ＬＡＳＴ［３：０］）入力１５と、３２ビットデータ入力（ＤＩ）１６と、１ビット読み取り入力１７と、１０ビットアドレス（Ａ）入力１８と、１ビットマッチセレクト（ＭＳＥＬ）入力１０と、１ビット入力レディ（ＩＲＤＹ）出力２１と、１ビット出力レディ（ＯＲＤＹ）出力２２と、４ビット（ＢＥ）出力２３と、３２ビットデータ出力（ＤＯ）２４と、１ビットビジー出力２５とを含む。
【００１３】
圧縮エンジン１０は、リセット（ＲＳＴ＿Ｎ）入力１２を介してリセットされ、履歴情報をフレームごと全てクリアする。データの最終ワードは、コントロール信号４ビット最終（ＬＡＳＴ［３：０］）入力１５を介して、（バイト毎に）信号通知される。圧縮エンジン１０からの出力は、１ビットビジー出力２５におけるビジー信号が、取り消されるまで、データ処理およびデータ引渡しを継続する。
【００１４】
圧縮エンジン１０は、セルフスロットル型圧縮エンジンであり、クロックサイクル毎に１バイトのデータ（８ビット）を圧縮または解凍できる。
【００１５】
実施形態において、圧縮エンジン１０は、バス３１へのシンプル同期インターフェース３０を、圧縮および解凍データの入出力に対して用いている。これを図２に示す。圧縮エンジン１０は、データの入力３５およびデータの出力３４を、コントロール信号３３を介して絞り込む。圧縮エンジン１０は、クロック信号３２あたり１バイトずつデータを処理する。クロック信号３２を用いて、バスインターフェース３０と圧縮エンジン１０のタイミングを同期する。
【００１６】
圧縮エンジン１０は、損失の少ない圧縮アルゴリズムを実現しており、それは、２０４８バイト以下のフレームに対しては、ＡＮＳＩＸ３．２４１−１９９４仕様（ＳｔａｃｋｅｒＬＺＳ．ＴＭ．として既知）と互換性がある。バイナリデータストリームの圧縮は、データ中に繰り返しパターンを見つけることにより、達成される。パケット全体が、履歴テーブルに含まれるため、圧縮エンジン１０では、データ用スライディングウィンドウを用いていない、という点において、圧縮エンジン１０は、改善された実施となっている。
【００１７】
他の実施形態において、圧縮エンジン１０は、スライディングウィンドウをＡＮＳＩＸ３．２４１−１９９４の実施のために用いる。しかし、本実施形態は、圧縮アルゴリズムの実施のために異なるアーキテクチャを必要とする。圧縮エンジン１０の構成要素である連想記憶装置（ＣＡＭ）は、先入れ先出しメモリ（ＦＩＦＯ）として動作しなければならず、ＣＡＭにおける各バイトは、ＣＡＭブロックにロードされる時に、シフトダウンされる。
【００１８】
圧縮データは、データトークンとストリングトークンで表される。データトークンは、実際のデータバイト値を表すために用いられる。ストリングトークンは、パケット中の繰返しパターンを示すために用いられる。データトークンは、実際のデータの８ビットに続く「０」としてコード化される。
【００１９】
ストリングトークンは、履歴バッファ（データの最終２０４８バイト）への７ビットオフセットに続く「１１」と、ストリングパターンのレングスとから成る。また、ストリングトークンは、履歴バッファ（データの最終２０４８バイト）への１１ビットオフセットに続く「１０」と、ストリングパターンのレングスとから成る。ストリングパターンのレングスは、１５バイトのブロックにて実行され、それにより、ストリングレングス「１１１１」は、１５バイトのデータ長を有するストリングパターンを示し、ストリングレングス「１１１１１１１１」は、３０バイトのデータ長を有するストリングパターンを示し、そして、ストリングレングス「１１１１１１１１０１１１」は、３７バイトのデータ長を有するストリングパターンを示す。
【００２０】
ストリングトークンは、オフセットサイズとレングスフィールドサイズに基づいて成る。各データトークンは、１ビット余分に必要とするため、データは、圧縮アルゴリズムにより処理されると、拡張する可能性がある。最大拡張率は、９／８、または、１２．５％の拡張である。最大圧縮率は、少なくとも４ビットを１５バイトのデータ毎に出力するという制約により制限される（同文字の無限長パターンに対して３０／１）。エンドマーカが、０×０オフセットを有する特別ストリングトークンとして構成される。（エクストラゼロをエンドマーカの後に付加して、データのバイト調整を行う）。
【００２１】
本発明の一実施形態では、パイプラインによる実施を用いて、ＡＮＳＩＸ３．２４１−１９９４仕様を満たしている。パイプラインによる実施により、データの最小記憶を可能にし、最高スループット性能を維持する。アルゴリズムが、履歴バッファより大きくパケットを圧縮するために、スライディングウィンドウを履歴バッファに用いる。この実施形態では、２キロバイトのスライディングウィンドウを用いる。
【００２２】
現在のバイトを履歴情報のスライディングウィンドウと比較することにより、冗長ストリングが、見られる。履歴バッファは、処理情報の最終２０４８バイトを含む（処理される全てのバイトは、マッチした時でも、比較後に履歴バッファに見られる）。バイトが、履歴バッファのどの位置ともマッチしない場合は、バイトは、出力にデータトークンとして渡される。マッチする場合は、バイトは、出力に渡されず、マッチが、見られなくなるまで、次のバイトが、処理される（マッチは、隣接していなければならない）。もはや、マッチが、見られなくなると、データパターン内のマッチのオフセットとマッチングストリングのレングスが、出力にストリングトークンとして渡される。
【００２３】
連想記憶装置（ＣＡＭ）は、履歴バッファデータの記憶のための理想的なデバイスである。スライディングウィンドウアーキテクチャを実施する際に最適性能を得るためには、ＣＡＭは、ＦＩＦＯ特性を有していなければならず、それにより、各バイトをロードする時、ＣＡＭ全体を、１クロック期間の間にシフトダウンする。
【００２４】
図３は、ＣＡＭセル５１の構造を示す。ＣＡＭセル５１は、フリップフロップ（ＦＦ）５２により実施される、８ビットのレジスタ記憶装置を含む。レジスタ記憶装置は、入力Ｄ［７：０］を受信し、Ｑ［７：０］を出力する。ＸＮＯＲゲート５３とＡＮＡＤゲート５４を用いて実施されるコンパレータは、Ｑ［７：０］とＣＡＭアドレスＣＡ［７：０］とのマッチがあるかを示す。有効入力ビット（ＶＩ）は、フリップフロップ５５に記憶され、有効出力ビット（ＶＯ）を形成し、その有効出力ビット（ＶＯ）は、Ｄ［７：０］により特定された位置が、有効情報を含む時を示す。ＮＯＲゲート５６は、出力（ＭＡＴＣＨ）信号を形成しており、その信号は、フリップフロップ５７を介してレジストされ、ＣＡＭセル５１の処理可能速度を高める。
【００２５】
図４に示す通り、ＣＡＭセルは、タイル状に集結されて、履歴バッファとして機能するＣＡＭ全体ブロックを構成する。これを、図のようにタイル状に集結されたＣＡＭセル６１とＣＡＭセル６２とＣＡＭセル６３により、図４に示す。ＬＯＡＤおよびＣＡＭアドレスＣＡ［７：０］信号は、タイル状ＣＡＭセルのアレイ全体を通じて共通である。リセット（ＲＳＴ＿Ｎ）信号を用いて、１クロック内のアレイ全体（有効ビット）を、履歴バッファをフラッシュすることによりクリアする。履歴バッファは、２０４８バイトレングスのため、２０４８のＣＡＭセルが存在する。
【００２６】
図４に見られる通り、データＤＩ［７：０］のバイトは、ＣＡＭセル６１に（ＶＩ）信号における有効性と共に入り、その有効性は、データのバイトが、有効であるかを示す。連続するクロックサイクルにて、そのデータバイトは、全２０４８ＣＡＭセルを通してクロックする。
【００２７】
図５は、ＣＡＭ７１への入力／出力インターフェースを示す構成図である。ＣＡＭ７１への入力は、ＬＯＡＤ信号と、ＷＲＩＴＥ信号と、バイト内のデータＤＩ［７：０］と、ＣＡＭアドレスＣＡ［７：０］と、１１ビットアドレスＡ［１０：０］である。ＣＡＭ７１は、１バイトデータアウトＤＯ［７：０］と、２０４８のＣＡＭの各セルに対するマッチ表示（ＭＡＴＣＨ［２０４７：０］）を形成する。
【００２８】
１１ビットアドレスＡ［１０：０］は、ダイレクト読み取り／書き込みアクセスを各ＣＡＭレジスタ（セル）に提供する。これは、テストするために提供されるものであり、これにより、同じ記憶要素が、データ解凍に使用できるようになる。
【００２９】
比較論理と続くストリングマッチング理論が、パイプラインされているため、マッチが、認識されない時に提供される出力データは、パイプラインに従う必要がある。ＣＡＭへのダイレクトメモリアクセスを用いて、データストリーム中の正しいバイトを、余分なバッファリングを必要とすることなく、パイプラインの深度に読み取りアドレスをセットすることにより、読み取ることができる。
【００３０】
ＣＡＭ７１のサイズは、かなりのものである。図３、４、および、５に示す通り実施すると、ＣＡＭ７１をなすゲートは、およそ２１２、０００ゲートである。サイズは、標準レイアウトセルを構成することにより相当減じて、（コンパイル済みのメモリのような）ＣＡＭ７１を実施することができる。これは、また、ＣＡＭ７１の処理可能速度を高める。
【００３１】
レジストされたマッチ値（図３のフリップフロップ５７により示す）は、パイプライン内で出力データを１クロック期間だけ遅延させる。より遅い速度のアプリケーションでは、これを除いて、実施ゲート総数を減らすことができる。
【００３２】
図６は、圧縮マッチングアルゴリズムのハードウエアにおける実施を示す。１バイトラッチ（ＢＹＴＥ）８２は、ＣＡＭ７１に挿入される入データを保持する。ＯＲゲート８７は、２０４８のＭＡＴＣＨビットに対して論理和ファンクションを実行し、マッチしたかを示すシングルビットを形成する。「１」という値を、入力８１としてＣＡＭ７１のアドレスＡ［１０：０］に配置する。
【００３３】
レジスタ８３は、前のクロックサイクルに対する２０４８ビットのマッチ値を保持する。ＡＮＤゲート８４は、前のクロックサイクルに対する２０４８ビットのマッチ値と、現在のクロックサイクルに対する２０４８ビットのマッチ値との、ビット毎の論理積をとり、２０４８ビット出力を形成する。ＡＮＤゲート８５は、ＡＮＤゲート８４からの２０４８ビットの出力値と、ＯＲゲート８６からの２０４８ビットのアウトとの、ビット毎の論理積をとる。ＡＮＤゲート８５の出力は、レジスタ８８に記憶される。ＯＲゲート８６は、レジスタ８８に記憶される値と、フリップフロップ８９に記憶される１ビット値との、論理和をとり、２０４８ビット出力を形成する。フリップフロップ８９に記憶される１ビット値が、論理「１」である場合、ＯＲゲート８６は、２０４８の論理１の出力信号を形成する。
【００３４】
ＯＲゲート９１は、ＡＮＤゲート８５の２０４８ビット出力に対する論理和をとる。ＮＡＮＤゲート９５は、ＯＲゲート８７の１ビット出力と、ＯＲゲート９１の１ビット出力との、否定論理積ファンクションを実行して、ＳＥＮＤ　ＢＹＴＥ信号を形成する。
【００３５】
マッチングアルゴリズムは、「隣接」マッチを探し、冗長ストリングを決定する。ストリングの構成は、それ自体は、ストリングとして保存されない。隣接マッチのみが、履歴バッファにて認識されたストリングとしてトラックされる。隣接マッチは、前のマッチングベクトルから現在のマッチングベクトル状態への変移を探すことにより構成される。
【００３６】
データが、ＦＩＦＯ型ＣＡＭ７１を通じて移動するため、インデックスブロック９６により出力されるオフセットを、最後に認識された最終隣接マッチから直接決定することができる。従って、ほんの１つの隣接マッチのみが検出されるとすぐに、オフセットを認知できる。ワンファンクション９０は、ほんの１つの隣接マッチが検出される時を検出し、表示をフリップフロップ９２に記憶する。フリップフロップ９２は、オフセットレディ（ＯＦＦＲＤＹ）信号９３を生成する。
【００３７】
このように、インデックス９６からのオフセットを、データストリームに、ストリングマッチ全体が認識される前に、引渡すことができる。オフセットは、レジスタ（ＲＥＧ）８８に記憶される。オフセットの引渡しは、ブロック全体性能を初めに高めており、それは、オフセットが、通常（特に短いストリングの場合には）、ストリングマッチ完了前に、決定されるからである。
【００３８】
オフセットは、特定ストリングトークン（履歴バッファ内の２つのマッチングストリング）に対して、解決しなくてもよい。解凍は、どのパターンを参照したかに関係ないため、ストリングトークンは、どちらのオフセットを出力してもよい。オフセットトークンの値は、優先エンコーダとして動作するインデックスファンクション９６により決定される。インデックス９６は、１１ビットオフセット（［１０：０］）と、１１ビットオフセットの７ビットのみ（すなわち、７ビットオフセット）が、使用されるべき時を示すＯＦＦ７ＢＩＴ信号を生成する。
【００３９】
レングスカウンタ９４は、ＮＡＮＤゲート９５からの信号に基づいてインクリメントを実行する。レングスカウンタ９４による８ビットレングス（ＬＥＮ［７：０］）出力は、認識された連続マッチングバイト数により決定される。ストリングのレングスは、通常、４ビットのインクリメントの間に、出力バッファに引渡される。一時に４ビットずつのコード化レングスの引渡しにより、レングスを、無限サイズにすることができる。性能も上がり、それは、ストリングマッチが、インクリメントする時に、ストリングのレングス（最後の４ビットを除く全て）を出力バッファに引渡しできるからである。レングスレディ（ＬＥＮＲＤＹ）信号は、レングスが、レディの時を示す。ＬＥＮ８ＢＩＴ出力は、レングスが、８ビットレングスであることを示す。ＬＥＮ２ＢＩＴ出力は、レングスが２ビットであることを示す。デフォルトは、４ビットである。８ビットレングスを用いる理由を以下に記す。
【００４０】
オフセットは、ＣＡＭ７１への半分（１０２４バイト）までに、ほんの１つのストリングマッチングを解決することを保証されていない。レングスカウンタ９４は、従って、オフセットが、解決される（ＯＦＦＲＤＹが、アサートされる）まで、カウントを１０２４まで続けなければなければならない。オフセットが、一旦、解決されると、レングスファンクションは、記憶レングスを１６カウントより小さくディクリメントするまで、一時に８ビットずつ出力する。一旦、レングスが、１６より小さくなり、オフセットが、解決されると、レングスファンクションは、ストリングマッチの終わりまで、一時に４ビットずつ出力する。
【００４１】
図７は、マッチングアルゴリズム１０１（その詳細を図６に記載）を通じる圧縮データフローを示す。３２ビットデータ入力ＤＩ［３１：０］が、入力バッファ１００によりバッファされる。入力バッファ１００は、一回に８ビットずつ、バイトラッチ８２（図６に図示）にデータを転送する。個々のバイトは、入力バッファ１００から引き出され、マッチングアルゴリズム１０１のデータパスにパイプラインされる。
【００４２】
３２ビットデータ出力は、出力バッファ１０２によりバッファされる。出力バッファ１０２を用いて、圧縮データストリーム情報（データトークンとストリングトークン）を集め、それを語境界に配列する。
【００４３】
出力ＯＦＦＲＤＹは、（未アクティブの場合）ストリングの終わりでアクティブに駆動され、レングスを出力させる。ＬＥＮＲＤＹ出力は、また、ストリングの終わりでアサートされて、コード化レングスの最終ビットが、確実に読み取られるようにする。
【００４４】
レングスは、出力バッファ１０２に転送するのに、多くのクロックを必要としてもよく、それは、オフセットが、マッチングストリングの終わりまで解決されない可能性があるためである。効果は、出力バッファへのレングス出力のビット幅を増やすことにより、小さくなる。（４ビット幅ではなく）８ビット幅では、最悪の場合は、データの１０２４バイトが、集められ、ストリングが、その点で決定される。オフセットを転送するのには、１クロックを必要とし、完全にコード化レングスをマッチングアルゴリズム１０１から出力バッファ１０２に転送するのには、３５クロック（（１０２４／１５）＊４／８）を必要とする。
【００４５】
各ストリングの最初の２バイトは、出力バッファ１０２にＣＡＭ７１を通じてパイプランされており、それは、ソースパターンが、少なくとも２バイトをストリングマッチのために必要とするからである。バイトは、ＳＥＮＤ　ＢＹＴＥ信号が、アクティブになる度に、ＳＥＮＤ　ＢＹＴＥの０から１への変移における最初のバイトを除いて、出力バッファにＣＡＭ７１のＤＯ［７：０］ラインから送信される。これは、ストリングの終わりに到達し、ストリングトークンが、終了したことを示す。
【００４６】
入力バッファ１００は、データを一時に８ビットずつバイトラッチ８２（図６に図示）に転送する。個々のバイトは、入力バッファ１００から引き出され、マッチングアルゴリズム１０１のデータパスにパイプラインされる。出力バッファ（これも３２ビット）を用いて、圧縮データストリーム情報（データトークンとストリングトークン）を集め、それを語境界に配列する。
【００４７】
圧縮データの解凍は、圧縮よりもずっとシンプルなタスクである。ＣＡＭ７１は、データ解凍に再度用いられる。入力バッファ１００を用いて、バイト配列データストリームを保持し、一方、データトークンとストリングトークンをストリップする。
【００４８】
図８は、解凍データフローを示す。ストリングトークンは、オフセットフィールド１１７とレングスフィールドを引き出すために解析される。
【００４９】
オフセットフィールド１１７は、フィールド全体として引き出され、レングス１１４は一時に４ビットずつ引き出される。各レングスフィールドは、デコード１１３によりデコードされ、結果は、レングスカウンタ１１４にロードされており、そのレングスカウンタ１１４を用いて、複数の４ビットにおけるストリングスレングスを決定する。オフセット値（マイナス１）を用いて、ＣＡＭにアドレスし、適正バイトを引き出す。各解凍バイト（ＤＯ［７：０］）は、出力バッファ１０２（図７に図示）に引渡され、続いて履歴情報として使用するためにＣＡＭ７１に配置される。マルチプレクサ（ＭＵＸ）１１２は、バイト１１１、または、ＤＯ［７：０］のいずれかを、レングスカウンタ１１４が、レングスが、ゼロである（すなわち、データバイトが、処理されている）と示すか、あるいは、レングスが、ゼロより大きい（すなわち、ストリングトークンが、処理されている）と示すかに基づき、選択する。
【００５０】
レングスカウンタ１１４におけるレングスは、その後、ストリングの一部として処理される各バイトを、ゼロになるまで、ディクリメントする。レングスカウンタ１１４は、レングスが、０より大きい時を示す１ビット出力値を有する。ＯＲゲート１１５は、この値とＷＲＩＴＥ信号とに対して、それをＣＡＭ７１のＬＯＡＤ入力に転送する前に、論理和をとる。
【００５１】
例えば、圧縮前は、データストリングは、ＡＮＳＩＸ３．２４１−１９９４により、以下の１６バイト文字ストリング「ＡＢＡＡＡＡＡＡＣＡＢＡＢＡＢＡ」として、定義される。１６進数ストリングでは、「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２　４１　４２　４１」となる。
【００５２】
結果の圧縮ストリングは、２サイクルのパイプライン遅延と共に、「２０　９０　８８　３８　１Ｃ　２１　Ｅ２　５Ｃ　１５　８０」として生成される。
【００５３】
図９は、圧縮値を示す。最上行４１は、１６進数値を示す。行４２は、１６進数値のコード化バイナリビットを示す。
【００５４】
圧縮データを解凍する際、入力ストリームは、バイトとストリングトークンをストリームからストリップするように解析される。各データトークンは、先頭のゼロを除くことにより、バイトに変換される。バイトは、それから、出力に直接供給され、ＣＡＭにロードされる。ストリングトークンは、デコードされ、データを履歴バッファ（ＣＡＭの内容）から復元するために用いられる。
【００５５】
データ復元は、オフセット（マイナス１）をアドレス（Ａ）としてＣＡＭブロックに適用することにより達成される。結果データアウト（ＤＯ）は、その後、ＣＡＭ７１にロードされ、出力バイトとして提供される。このプロセスは、ストリングトークンのレングスが、ゼロにディクリメントされるまで続く。
【００５６】
オフセットは、履歴バッファ（ＣＡＭ）７１からストリングを引き出す時に、レングスをディクリメントする際には、変化しない。圧縮データから解析された各ストリングトークンは、エンドマーカに達するまで処理される。
【００５７】
例えば、図９に説明する値を解凍する場合、ビット１４１は、「０」であり、それは、次の８ビットが、解凍データであることを示す。次の８ビット１４２は、データ値「４１」であり、それは、ＣＡＭ７１に配置され、データアウトの１バイトとして使用される。結果として、ＣＡＭ７１は、以下の１６進数値「４１」（ＣＡＭ７１内の位置０から始まる）を記憶している。
【００５８】
ビット１４３は、「０」であり、それは、次の８ビットが、解凍データであることを示す。次の８ビット１４４は、データ値「４２」であり、それは、ＣＡＭ７１内に配置され、データアウトの１バイトとして使用される。結果として、ＣＡＭ７１は、以下の１６進数値「４２　４１」（ＣＡＭ７１内の位置０から始まる）を記憶している。
【００５９】
ビット１４５は、「０」であり、それは、次の８ビットが、解凍データであることを示す。ビット１４６は、データ値「４１」であり、それは、ＣＡＭ７１内に配置され、データアウトの１バイトとして使用される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１」（ＣＡＭ７１内の位置０から始まる）を記憶している。
【００６０】
２つのビットストリング１４７は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」であるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。もし、オフセットが、１２７よりも大きかったら、１１ビットが、用いられ、２つのビットストリング１４７の値は、「１０」であったであろう。
【００６１】
７ビットオフセット１４８は、オフセットが、「１」に等しいことを示す。このオフセットレス１（オフセット−１）は、ＣＡＭ７１のアドレス（Ａ［１０：０］）入力に配置される。４ビットレングス１４９は、２つの２ビットセクションに分けられる。第一の２ビットセクションは、「１１」のビット値を有し、それは、３に等しい。第二の２ビットセクションは、「００」のビット値を有し、それは、０に等しい。ストリングの全レングスは、従って、２＋３＋０＝５となる。
【００６２】
第一クロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４１　４２　４１」を記憶している。レングスは、４にまでディクリメントされる。
【００６３】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１内に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４１　４１　４２　４１」を記憶している。レングスは、３までディクリメントされる。
【００６４】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４１　４１　４１　４２　４１」を記憶している。レングスは、２までにディクリメントされる。
【００６５】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、１にまでディクリメントされる。
【００６６】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、０にまでディクリメントされる。
【００６７】
ビット１５０は、「０」であり、次の８ビットが、解凍データであることを示す。次の８ビット１５１は、データ値「４３」であり、それは、ＣＡＭ７１に配置され、データアウトの１バイトとして用いられる。結果として、ＣＡＭ７１は、以下の１６進数値「４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。
【００６８】
２つのビットストリング１５２は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」あるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。
【００６９】
７ビットオフセット１５３は、オフセットが、「９」に等しいことを示す。このオフセットレス１（オフセット−１）は、ＣＡＭ７１のアドレス（Ａ［１０：０］）入力に配置される。２ビットレングス１５４は、「０１」のビット値を有し、それは、１に等しい。ストリングの全レングスは、従って、２＋１＝３となる。
【００７０】
第一クロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、２にまでディクリメントされる。
【００７１】
次のクロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１内に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、１にまでディクリメントされる。
【００７２】
次のクロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、０にまでにディクリメントされる。
【００７３】
２つのビットストリング１５５は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」あるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。
【００７４】
７ビットオフセット１５６は、オフセットが、「２」に等しいことを示す。このオフセットレス１（オフセット−１）は、ＣＡＭ７１のアドレス（Ａ［１０：０］）入力に配置される。２ビットレングス１５７は、「１０」のビット値を有し、それは、２に等しい。ストリングの全レングスは、従って、２＋２＝４となる。
【００７５】
第一クロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４２　４１　４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、３にまでディクリメントされる。
【００７６】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１内に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、２にまでディクリメントされる。
【００７７】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４２　４１　４２　４１　４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、１にまでにディクリメントされる。
【００７８】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１に戻って配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４２　４１　４２　４１　４３　４１　４１　４１　４１　４１　４１　４２　４１」を記憶している。レングスは、０にまでにディクリメントされる。
【００７９】
８ビットストリング１５８は、エンドマーカであり、データストリームの終わりを示している。
【００８０】
圧縮アルゴリズムは、パケットサイズを履歴バッファ（２０４８バイト）よりも小さく限定することにより、ウィンドウなしのアルゴリズムに簡略化できる。パケットサイズを限定することにより、履歴バッファは、パケットデータと共に「スライド」して、情報の最終２０４８バイトを含む必要がなくなる。
【００８１】
データが、履歴バッファをラップしないため、標準ＣＡＭ構成を用いて、アルゴリズムを実施する。データが、履歴バッファ（ＣＡＭ）をラップしないので、履歴テーブルに対する開始及び終了ポインタのトラックを保持する必要がない。また、マッチ出力結合をシフトし続けて、ストリングマッチングにおける文字比較が、隣接するようにする必要もない。
【００８２】
標準ＣＡＭ構成をウィンドウなしの環境下においても使用することには、まだ、短所がある。オフセットを、ＣＡＭに保持されるバイト数（または、バイトでの現在の蓄積ストリングレングス）、および、ＣＨＡＲベクトルの最終インデックスに基づき、計算しなければならない。計算式は、ＯＦＦＳＥＴ＝ＳＴＲＩＮＧ　ＬＥＮＧＴＨ−ＩＮＤＥＸ＋１である。
【００８３】
ストリングマッチ（ＣＨＡＲ）の計算に対するビットシフトは、ここで、ＣＡＭの外部にて行われなければならない。アーキテクチャワンにおいて、ビットシフトは、非明示であり、それは、ＣＡＭは、各バイトを、ロードする度に、データをシフトするからである。
【００８４】
図１０は、本発明のかかる他の実施形態に対するＣＡＭセル５１の構成例を示す。８ビットメモリアレイ１２１は、メモリセルの値を記憶する。コンパレータ１２１は、これをＣＡＭアドレスＣＡ［７：０］と比較する。ＮＡＮＤゲートは、コンパレータ１２１の出力と有効ビットとの論理積をとる。この結果は、フリップフロップ１２１に記憶される。フリップフロップ１２１の出力は、１ビットマッチ信号であり、それは、有効データのマッチが、ＣＡ［７：０］から８ビットメモリアレイ１２１に記憶されるデータに、存在したかを示す。
【００８５】
図１０に示す標準ＣＡＭセルは、データを共に連鎖しない。それは、単にメモリアレイであり、各要素は、ＣＡＭアドレス（ＣＡ）と比較されている。セルは、タイル状に集結されており、標準メモリ読み取り／書き込みアクセスを、使用可能である。該して、ＣＡＭ比較は、読み取りまたはＣＡＭメモリアレイと有効ビットへの書き込みに対する排他アクセスである。ＭＡＴＣＨ出力は、ＣＡＭ内にレジストされても、されなくてもよい。ＭＡＴＣＨ出力をレジストすることにより、単にパイプラインは、遅延し、タイミングが、向上する。
【００８６】
図１１は、他の実施形態に対する、圧縮マッチングアルゴリズムのハードウエアにおける実施を示す。１バイトラッチ（ＢＹＴＥ）１８２は、ＣＡＭ１７１に挿入される入データを保持する。ＯＲゲート１８７は、２０４８のＭＡＴＣＨビットに対して論理和ファンクションを実行し、マッチしたかを示すシングルビットを形成する。
【００８７】
レジスタ１８３は、前のクロックサイクルに対する２０４８ビットのマッチ値を保持する。ＡＮＤゲート１８４は、前のクロックサイクルに対する２０４８ビットのマッチ値と、現在のクロックサイクルに対する２０４８ビットのマッチ値との、ビット毎の論理積をとり、２０４８ビット出力を形成する。「Ｉ−１」ファンクション２０１は、レジスタ１８３に記憶されるマッチ値の１ビットシフト（ゲートは必要なく、単にワイヤリングシフトである）を実行する。ＡＮＤゲート１８５は、ＡＮＤゲート１８４からの２０４８ビットの出力値と、ＯＲゲート１８６からの２０４８ビットのアウトとの、ビット毎の論理積をとる。ＡＮＤゲート１８５の出力は、レジスタ１８８に記憶される。ＯＲゲート１８６は、レジスタ１８８に記憶される値とフリップフロップ１８９に記憶される１ビット値の論理和をとり、２０４８ビット出力を形成する。「Ｉ−１」ファンクション２０２は、レジスタ１８８に記憶されるマッチ値の１ビットシフトを、それが、ＯＲゲート１８６に転送される前に、実行する。
【００８８】
ＯＲゲート１９１は、ＡＮＤゲート１８５の２０４８ビット出力の論理和をとる。ＮＡＮＤゲート１９５は、ＯＲゲート１８７の１ビット出力と、ＯＲゲート１９１の１ビット出力とに、否定論理積ファンクションを実行し、ＳＥＮＤ　ＢＹＴＥ信号を形成する。
【００８９】
マッチングアルゴリズムは、「隣接」マッチを探し、冗長ストリングを決定する。ストリングの構成は、それ自体は、ストリングとして保存されない。隣接マッチのみが、履歴バッファに認識されたストリングとしてトラックされる。隣接マッチは、前のマッチベクトルから現在のマッチベクトル状態への変移を探すことにより構成される。
【００９０】
ワンファンクション１９０は、ほんの１つの隣接マッチが、検出される時を検出し、フリップフロップ１９２における表示を記憶する。フリップフロップ１９２は、ＯＦＦＲＤＹ信号１９３を生成する。
【００９１】
このように、インデックス１９６からのオフセットを、データストリームに、ストリングマッチ全体が認識される前に、引渡すことができる。オフセットの引渡しは、ブロック全体性能を初めに高めており、それは、オフセットが、通常（特に短いストリングの場合には）、ストリングマッチ完了前に、決定されるからである。
【００９２】
レングスカウンタ１９４は、ＮＡＮＤゲート１９５からの信号に基づいてインクリメントを実行する。レングスカウンタ１９４による８ビットレングス（ＬＥＮ［７：０］）出力は、認識された連続マッチングバイト数により決定される。ストリングのレングスは、４ビットのインクリメントの間に、出力バッファに引渡すことができる。一時に４ビットずつコード化レングスを引渡すことにより、レングスを無限サイズにすることができる。性能も上がり、それは、ストリングマッチが、インクリメントする時に、ストリングのレングス（最後の４ビットを除く全て）を出力バッファに引渡すことができるからである。
【００９３】
ＬＥＮＲＤＹは、レングスが、レディの時を示す。ＬＥＮ８ＢＩＴ出力は、レングスが、８ビットレングスであることを示す。ＬＥＮ２ＢＩＴ出力は、レングスが、２ビットであることを示す。
【００９４】
オフセットは、ほんの１つのストリングマッチを、ＣＡＭ１７１への半分（１０２４バイト）までに、解決することを保証されていない。レングスカウンタ１９４は、従って、オフセットが、解決される（ＯＦＦＲＤＹが、アサートされる）まで、カウントを１０２４まで続けなければなければならない。一旦、オフセットが、決定されると、レングスファンクションは、記憶レングスを１６カウントより小さくディクリメントするまで、一時に８ビットずつを出力する。一旦、レングスが、１６より小さくなり、オフセットが、解決されると、レングスファンクションは、ストリングマッチの終わりまで、一時に４ビットずつ出力する。
【００９５】
ストリングレングスブロック２０３は、入力データストリームの全レングスをバイトで含んでいる。ストリングレングスブロック２０３を用いて、データのバイトをＣＡＭ１７１に書き込むために、次のＣＡＭ位置にアドレスする。また、ストリングレングスブロック２０３を用いて、オフセット値を生成しており、それは、ＣＡＭデータが、このアーキテクチャではシフトしないからである。サブブロック１９９は、インデックス１９６からの出力とストリングレングス２０３の出力を受信し、１１ビットオフセット（［１０：０］）を形成する。コンパレータ２００は、この値を「１２８」とを比較し、７ビットオフセットのみが、使われていることを示すＯＦＦ７ＢＩＴ信号を形成する。出力データバイトを、レジストして、データ出力パイプラインが、マッチングパイプラインと並ぶようにしなければならない。
【００９６】
この実施においては、ＣＡＭ１７１に組み込まれたどの優先エンコーダファンクションも使用できず、それは、全マッチのトラックをマッチングアルゴリズムパイプラインの間ずっと、保たなければならないからである。
【００９７】
解凍データフローは、概ね、図８の説明と同じである。しかし、オフセットは、現在のストリングレングスから差引かれて、ＣＡＭ１７１内の位置を計算しなければならない。
【００９８】
例えば、圧縮前は、データストリングは、ＡＮＳＩＸ３．２４１−１９９４により、以下の１６バイトの文字ストリング「ＡＢＡＡＡＡＡＡＣＡＢＡＢＡＢＡ」として、定義される。１６進数ストリングでは、「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２　４１　４２　４１」となる。
【００９９】
結果の圧縮ストリングは、２サイクルのパイプライン遅延と共に、「２０　９０　８８　３８　１Ｃ　２１　Ｅ２　５Ｃ　１５　８０」として生成される。
【０１００】
圧縮データを解凍する際、入力ストリームは、バイトとストリングトークンをストリームからストリップするよう解析される。各データトークンは、先頭のゼロを除くことにより、バイトに変換される。バイトは、それから、出力に直接供給され、ＣＡＭにロードされる。ストリングトークンは、デコードされ、データを履歴バッファ（ＣＡＭの内容）から復元するために用いられる。
【０１０１】
データの復元は、オフセット（マイナス１）をアドレス（Ａ）としてＣＡＭブロックに適用することにより達成される。結果データアウト（ＤＯ）は、その後、ＣＡＭ１７１にロードされ、出力バイトとして提供される。このプロセスは、ストリングトークンのレングスが、ゼロにディクリメントされるまで続く。
【０１０２】
ストリングを履歴バッファから引き出す時に、レングスが、ディクリメントされても、オフセットは、一定のままである。アドレス方程式を、各復元ステップに対して更新して、新しいストリングレングスが、アドレス（Ａ）は、バイト毎にインクリメントされることを、考慮するようにしなければならない。
【０１０３】
例えば、図９に説明する値を解凍する場合、ビット１４１は、「０」であり、それは、次の８ビットが、解凍データであることを示す。次の８ビット１４２は、データ値「４１」であり、それは、ＣＡＭ１７１に配置され、データアウトの１バイトとして使用される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝０（Ａ＝ストリングレングス−（オフセット−１）＝０−（１−１））で配置される。ＣＡＭ１７１は、以下の１６進数値「４１」（ＣＡＭ１７１内の位置０から始まる）を記憶している。ストリングレングスは、１に等しくなるまでインクリメントされる。
【０１０４】
ビット１４３は、「０」であり、それは、次の８ビットが、解凍データであることを示す。次の８ビット１４４は、データ値「４２」であり、それは、ＣＡＭ１７１内に配置され、データアウトの１バイトとして使用される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１（Ａ＝ストリングレングス−（オフセット−１）＝１−（１−１））で配置される。結果としてＣＡＭ１７１は、以下の１６進数値「４１　４２」（ＣＡＭ１７１内の位置０から始まる）を記憶している。ストリングレングスは、２に等しくなるまでインクリメントされる。
【０１０５】
ビット１４５は、「０」であり、それは、次の８ビットが、解凍データであることを示す。次の８ビット１４６は、データ値「４１」であり、それは、ＣＡＭ１７１内に配置され、データアウトの１バイトとして使用される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝２（Ａ＝ストリングレングス−（オフセット−１）＝２−０）で配置される。結果としてＣＡＭ１７１は、以下の１６進数値「４１　４２　４１」（ＣＡＭ１７１内の位置０から始まる）を記憶している。ストリングレングスは、３に等しくなるまでインクリメントされる。
【０１０６】
２つのビットストリング１４７は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」であるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。もし、オフセットが１２７より大きかったら、１１ビットが、用いられ、２つのビットストリング１４７の値は、「１０」であったであろう。
【０１０７】
７ビットオフセット１４８は、オフセットが、「１」に等しいことを示す。ストリングレングス、マイナスオフセットマイナス１（オフセット−１）は、ＣＡＭ１７１のアドレス（Ａ［１０：０］）入力に配置される。４ビットレングス１４９は、２つの２ビットセクションに分けられる。第一の２ビットセクションは、「１１」のビット値を有し、それは、３に等しい。第二の２ビットセクション、「００」のビット値を有し、それは、０に等しい。ストリングの全レングスは、従って、２＋３＋０＝５となる。
【０１０８】
第一クロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝３（Ａ＝ストリングレングス−（オフセット−１）＝３−０）で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１」（ＣＡＭ１７１内の位置０から始まる）を記憶している。レングスは、４までディクリメントされる。ストリングレングスは、４に等しくなるまでインクリメントされる。
【０１０９】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１内に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝４で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１」を記憶している。レングスは、３までディクリメントされる。ストリングレングスは、５に等しくなるまでインクリメントされる。
【０１１０】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝５で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１」を記憶している。レングスは、２までにディクリメントされる。ストリングレングスは、６に等しくなるまでインクリメントされる。
【０１１１】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝６で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１」を記憶している。レングスは、１にまでディクリメントされる。ストリングレングスは、７に等しくなるまでインクリメントされる。
【０１１２】
次のクロックサイクルにおいて、０のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝７で配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１」を記憶している。レングスは、０にまでディクリメントされる。ストリングレングスは、８に等しくなるまでインクリメントされる。
【０１１３】
ビット１５０は、「０」であり、次の８ビットが、解凍データであることを示す。次の８ビット１５１は、データ値「４３」であり、ＣＡＭ１７１に配置され、データアウトの１バイトとして用いられる。新しい値は、ＣＡＭ１７１内にアドレスＡ＝８で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３」を記憶している。ストリングレングスは、９に等しくなるまでインクリメントされる。
【０１１４】
２つのビットストリング１５２は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」あるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。
【０１１５】
７ビットオフセット１５３は、オフセットが、「９」に等しいことを示す。このオフセットレス１（オフセット−１）は、ＣＡＭ１７１のアドレス（Ａ［１０：０］）入力に配置される。２ビットレングス１５４は、「０１」のビット値を有し、それは、１に等しい。ストリングの全レングスは、従って、２＋１＝３となる。
【０１１６】
第一クロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝９で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１」を記憶している。レングスは、２にまでディクリメントされる。ストリングレングスは、１０に等しくなるまでインクリメントされる。
【０１１７】
次のクロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１内に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１０で配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２」を記憶している。レングスは、１にまでディクリメントされる。ストリングレングスは、１１に等しくなるまでインクリメントされる。
【０１１８】
次のクロックサイクルにおいて、８のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１１で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１」を記憶している。レングスは、０にまでにディクリメントされる。ストリングレングスは、１２に等しくなるまでインクリメントされる。
【０１１９】
２つのビットストリング１５５は、ストリングオフセットとストリングレングスが、続くことを示す。２つのビット値が、「１１」あるため、これは、オフセットが、７ビット以内に書かれている（すなわち、１２７以下の値を有する）ことを示す。
【０１２０】
７ビットオフセット１５６は、オフセットが、「２」に等しいことを示す。このオフセットレス１（オフセット−１）は、ＣＡＭ１７１のアドレス（Ａ［１０：０］）入力に配置される。２ビットレングス１５７は、「１０」のビット値を有し、それは、２に等しい。ストリングの全レングスは、従って、２＋２＝４となる。
【０１２１】
第一クロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１２で配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２」を記憶している。レングスは、３にまでディクリメントされる。ストリングレングスは、１３に等しくなるまでインクリメントされる。
【０１２２】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ７１内に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１３で配置される。結果として、ＣＡＭ７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２　４１」を記憶している。レングスは、２にまでディクリメントされる。ストリングレングスは、１４に等しくなるまでインクリメントされる。
【０１２３】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４２」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１４で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２　４１　４２」を記憶している。レングスは、１にまでにディクリメントされる。ストリングレングスは、１５に等しくなるまでインクリメントされる。
【０１２４】
次のクロックサイクルにおいて、１のアドレス（オフセット−１）は、ＣＡＭ１７１から出力される値「４１」となる。この値は、データアウトの１バイト（ＤＯ［７：０］）として用いられ、ＣＡＭ１７１に戻って配置される。新しい値は、ＣＡＭ１７１内にアドレスＡ＝１５で配置される。結果として、ＣＡＭ１７１は、以下の１６進数値「４１　４２　４１　４１　４１　４１　４１　４１　４３　４１　４２　４１　４２　４１　４２　４１」を記憶している。レングスは、０にまでにディクリメントされる。ストリングレングスは、１６に等しくなるまでインクリメントされる。
【０１２５】
８ビットストリング１５８は、エンドマーカであり、データストリームの終わりを示している。
【０１２６】
図１０および１１のウィンドウのないアーキテクチャは、解凍データに対して、ＣＡＭ１７１以外のメモリを必要としないという長所を有する。従って、図１０および１１に示すアーキテクチャの変形において、データを、圧縮前に完全にＣＡＭ１７１にロードすることができる。データを、データストリームの圧縮前に、（バスバンド幅を解放して）ＣＡＭ１７１にバースト可能である。データが圧縮されると、出力ストリームは、正規のスロットル仕様に戻る。
【０１２７】
解凍は、圧縮と逆のファンクションである。入力ストリームは、スロットル仕様でブロックへ送りこまれ、出力は、ＣＡＭ１７１に集められる。解凍データは、その後、ＣＡＭ１７１からバースト可能となる。
【０１２８】
両方の場合、より大量の（解凍）データは、バーストパケットとして転送される。両方の場合の圧縮ストリームは、入力へ絞られる。このように、必要な全バスバンド幅とデマンドは、減じられる。
【０１２９】
データ構造とマッチングアルゴリズムは、配置済み圧縮に対しても図１０および１１を用いた説明の通り、同様である。データが、完全にＣＡＭ１７１にロードされた後、各バイトは、有効フラグを更新することにより、比較に対し有効として、１時に１つずつ、タグ付けされる。このメカニズムでは、有効フラグが、別々に入力データからアクセス可能であることを必要とする（そうでなければ、読み取り／変更／書き込み処理を必要とする）。簡易深度（ストリングレングス）カウンタを用いて、有効ビットが、アクセス不可能の場合、まだ履歴バッファの一部とみなされないバイトに対して、比較をマスクする。
【０１３０】
上述の図１０および１１に示すアーキテクチャへの変形は、図３から６について図示説明したアーキテクチャの変形よりも、有利ではなく、それは、アーキテクチャは、ＣＡＭ７１とスライディングウィンドウを通して移動するデータを利用しているからである。
【０１３１】
上記の連想記憶装置は、高性能／密度な実施のためにカスタマイズされたブロックを必要とする。スタティックＲＡＭを履歴バッファに対し外部比較と組合せて用いることにより、さらに、満足のいく性能を、コンパクトなノンカスタムソリューションの長所と共に、生ずることができる。この種の「ＣＡＭ」の実施は、特に小さいパケットに対して、大変有効となり得る。
【０１３２】
圧縮のための配置済みアルゴリズムは、非常に簡単に、ストリングレングスカウンタにおいて有効なバイト数をトラックすることにより、実施できる。ストリングレングスカウンタを使用すると、有効ビットをメモリ（サイズ縮小）に記憶する必要性を排除できるが、それは、各バイトの有効性が、ストリングレングスの深度により決定されるからである。また、レングスカウンタを用いて、いかに深くメモリ内に、アルゴリズムの各パスに対して、アクセスされなければならないかを決定する（パス毎に１バイトを処理する）。
【０１３３】
小さいパケットは、小数の必要アクセスから開始し、パケットの終わりに向けて指数的に構成するため、この方法は、ウィンドウのない実施に対してよく作用する。性能を、よりワイドなメモリ（例えば、６４ビット）を用いて向上し、バイトあたりのメモリアクセス（または、クロック）数を減らすことができる。
【０１３４】
解凍は、上記の通り扱われる。必要な比較演算は、存在しない（メモリ空間のみ）。
【０１３５】
スタティックＲＡＭを用いて履歴バッファを実施することの問題点の１つのは、性能が、パケットサイズが、増加するとすぐに、悪くなることである。主な長所は、標準メモリを使用することと、ゲートを効率的に実施することである。
【０１３６】
スタティックＲＡＭ実施の性能は、１時に１バイトずつよりも多く（セレクションあたり複数バイト）を比較の間に処理することにより、かなり改善される。並列コンパレータを追加することにより、メモリは、複数マッチベクトル（および連続バイト）を同時に処理することにより、前に進めることができる。実施は、もっと複雑になり、メモリに他の読み取りポートを追加することにより、あるいは、メモリのビット幅を拡張することにより、同じ効果を得ることができる。
【０１３７】
上記のアーキテクチャは、各圧縮アルゴリズムの問題を解くために、交換して用いることができる。しかし、ウィンドウのある環境の標準ＣＡＭには、データが、ラップされた時に、ＣＡＭ内の履歴バッファ開始をトラックするために、（ＦＩＦＯのようにみせるために）循環待ち行列バッファを使用する必要がある。循環待ち行列バッファにより、隣接した計算が、きわめて困難になる（すなわち、マッチラインを多重化して、隣接マッチを決定する必要がある）。ウィンドウなしのアーキテクチャにおいて、データは、ＣＡＭをラップすることはなく、このアーキテクチャをより効率的にしている。
【０１３８】
ストリングマッチをトラックする基本式は、常に同じである。
【０１３９】
ＣＨＡＲ（ｉ）＝ＭＡＴＣＨ（ｉ）　ａｎｄ　Ｐｒｅｖ（ＭＡＴＣＨ（ｉ−１））　ａｎｄ　（Ｐｒｅｖ（ＣＨＡＲ（ｉ−１））　ｏｒ　Ｐｒｅｖ（ＳＥＮＤ　ＢＹＴＥ））
ＳＥＮＤ　ＢＹＴＥ＝ＮＯＴ（ＡＮＹ（ＣＨＡＲ）　ａｎｄ　ＡＮＹ（ＭＡＴＣＨ））
ここで、Ｐｒｅｖ（）は、レジスタ（フリップフロップ出力）直後の値である。
【０１４０】
前述の説明は、単に本発明の模範的な方法と実施形態を開示し、述べたものである。当業者に自明の通り、本発明は、その要旨と本質的な特徴を逸脱することなく、他の特別な形態において実施することができる。従って、本発明の開示は、例示的であって、発明の範囲を制限するものではなく、その発明の範囲を、付属のクレームに述べる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態による、圧縮エンジンのブロックインターフェースである。
【図２】図２は、本発明の実施形態による、図１の圧縮エンジンに対するブロックインターフェースの実施を示す。
【図３】図３は、本発明の実施形態による、ＣＡＭセルの構造を示す。
【図４】図４は、本発明の実施形態による、タイル状に集結されたＣＡＭセルを示す。
【図５】図５は、本発明の実施形態による、ＣＡＭへの入力／出力インターフェースを示す構成図である。
【図６】図６は、本発明の実施形態による、圧縮マッチングアルゴリズムのハードウエアにおける実施を示す。
【図７】図７は、本発明の実施形態による、図６の圧縮マッチングアルゴリズムを通した圧縮データフローを示す。
【図８】図８は、本発明の実施形態による、解凍データフローを示す。
【図９】図９は、本発明の実施形態による、圧縮データの例を示す。
【図１０】図１０は、本発明の他の実施形態による、ＣＡＭセルの構造を示す。
【図１１】図１１は、本発明の他の実施形態による、圧縮マッチングアルゴリズムのハードウエアにおける実施を示す。
【図１】
2004507858.tif 000003
【図２】
2004507858.tif 000004
【図４】
2004507858.tif 000005
【図６】
2004507858.tif 000006
【図７】
2004507858.tif 000007
【図８】
2004507858.tif 000008
【図１０】
2004507858.tif 000009
【図１１】
2004507858.tif 000010
【国際公開パンフレット】
2004507858.tif 000011
2004507858.tif 000012
2004507858.tif 000013
2004507858.tif 000014
2004507858.tif 000015
2004507858.tif 000016
2004507858.tif 000017
2004507858.tif 000018
2004507858.tif 000019
2004507858.tif 000020
2004507858.tif 000021
2004507858.tif 000022
2004507858.tif 000023
2004507858.tif 000024
2004507858.tif 000025
2004507858.tif 000026
2004507858.tif 000027
2004507858.tif 000028
2004507858.tif 000029
2004507858.tif 000030
2004507858.tif 000031
2004507858.tif 000032
2004507858.tif 000033
2004507858.tif 000034
2004507858.tif 000035
2004507858.tif 000036
2004507858.tif 000037
2004507858.tif 000038
2004507858.tif 000039
2004507858.tif 000040
2004507858.tif 000041
2004507858.tif 000042
2004507858.tif 000043
2004507858.tif 000044
2004507858.tif 000045
2004507858.tif 000046
2004507858.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2004507858.tif 000048
2004507858.tif 000049
2004507858.tif 000050
2004507858.tif 000051
2004507858.tif 000052
2004507858.tif 000053
2004507858.tif 000054
2004507858.tif 000055
2004507858.tif 000056
2004507858.tif 000057
2004507858.tif 000058
2004507858.tif 000059
2004507858.tif 000060
2004507858.tif 000061
2004507858.tif 000062
2004507858.tif 000063
2004507858.tif 000064
2004507858.tif 000065
2004507858.tif 000066
2004507858.tif 000067
2004507858.tif 000068
2004507858.tif 000069
2004507858.tif 000070
2004507858.tif 000071
2004507858.tif 000072
2004507858.tif 000073
2004507858.tif 000074
2004507858.tif 000075
2004507858.tif 000076
2004507858.tif 000077
2004507858.tif 000078
2004507858.tif 000079
2004507858.tif 000080
2004507858.tif 000081
2004507858.tif 000082
2004507858.tif 000083
2004507858.tif 000084
2004507858.tif 000085
【国際調査報告】
2004507858.tif 000086
2004507858.tif 000087
2004507858.tif 000088