(57)【要約】【課題】データ文字列のＬＺ１圧縮のための方法および配置構成を提供する。【解決手段】データ文字列の第１のバイト系列を入力バッファ（１４０）内に保持するステップと、データ文字列の第２のバイト系列を履歴バッファ（１１０、１２０）内に保持すること、入力バッファおよび履歴バッファに結合され複数の行および列の比較ユニット（２００）を有するマトリックス比較手段内で、入力バッファ内に保持されたバイトと、前記マトリックス比較手段内で斜めにずれた位置にある比較ユニットに結合された履歴バッファ内に保持されたバイトとを比較するステップ（１７０）と、各行で、その行内の比較ユニットと同じ列内の先行の比較ユニットとにおいて最大数の連続するバイト一致が発生した列、を検出するステップ（１５０）と、前記検出ステップ（１５０）によって検出された一致バイト系列をトークンとして符号化するステップ（１６０）とによる、データ文字列のＬＺ１圧縮のための方法（３００）および配置構成。
2005525039.tif 000002
【特許請求の範囲】
【請求項１】
データ文字列のＬＺ１圧縮のための配置構成（１００）であって、
前記データ文字列の第１のバイト系列を保持するための入力バッファ手段（１４０）と、
前記データ文字列の第２のバイト系列を保持するための履歴バッファ手段（１１０、１２０）と、
前記入力バッファ手段および前記履歴バッファ手段に結合され、前記入力バッファ手段内に保持されているバイトと前記履歴バッファ手段内に保持されているバイトとを比較するための比較ユニット（２００）の複数の行および列を有するマトリックス比較手段（１７０）であって、前記履歴バッファ手段のバイトが、前記マトリックス比較手段内で斜めにずれていく比較ユニットに結合される、マトリックス比較手段（１７０）と、
前記各行で、その行内の比較ユニットと、同じ列内の先行する比較ユニットとにおいて、最大数の連続するバイト一致が発生した列、を検出するための検出手段（１５０）と、
前記検出手段によって検出された一致バイト系列をトークンとして符号化するための手段（１６０）と、
を有する配置構成。
【請求項２】
前記マトリックス比較手段（１７０）が、各比較ユニット（２００）において、前記比較ユニットと、同じ列内の先行する比較ユニットとにおいて、発生した連続するバイト一致の数をカウントするための、カウント手段（２２０、２３０）を有し、
前記検出手段（１５０）が、各行において、最大カウントが発生した列を検出するための手段を有する、
請求項１に記載の配置構成。
【請求項３】
各比較ユニットが、
前記入力バッファ手段からのバイトと前記履歴バッファ手段からのバイトとを比較するためのコンパレータ手段（２１０）と、
同じ列内の他の比較ユニットからのカウント値を受け取って増分するためのインクリメンタ手段（２２０）と、
前記コンパレータ手段の前記出力を受け取るための、およびそれに依存して、同じ列内の他の比較ユニットに渡すために前記インクリメンタ手段の前記出力かまたはゼロ値かを選択するための、セレクタ手段（２３０）と、
を有する、請求項２に記載の配置構成。
【請求項４】
各比較ユニット（４００）が、
前記入力バッファ手段からのバイトと前記履歴バッファ手段からのバイトとを比較するためのコンパレータ手段（４１０）と、
カウント値を表すいくつかのビットからなる値を同じ列内の他の比較ユニットから受け取るための、ならびに、前記コンパレータ手段の出力を受け取り、それに依存して、前記値をゼロにするか、またはシフトして前記値に更なるビットを追加することにより前記値を増分するかするための、論理手段（４２２、４２４、４２６）と、
を有する、請求項２に記載の配置構成。
【請求項５】
前記検出手段（５００）が、前記値の前記ビットを入力として受け取るための、および、それらの論理ＯＲ演算を実行して前記値の最大値を生成するための、論理手段（５２２、５２４、５２６）を有する、請求項４に記載の配置構成。
【請求項６】
前記履歴バッファ手段が、
前記マトリックス比較手段の第１の側にある行内の比較ユニットに結合された、第１のシフト・レジスタ手段と、
前記マトリックス比較手段の前記第１の側とは反対の第２の側にある行内の比較ユニットに結合された、第２のシフト・レジスタ手段と、
を有する、前記請求項のいずれか一項に記載の配置構成。
【請求項７】
前記第１のシフト・レジスタ手段および前記第２のシフト・レジスタ手段が、同一のシフト・レジスタ内のレベル・センシティブ・スキャン・デザイン（ＬＳＳＤ）の対を有する、請求項６に記載の配置構成。
【請求項８】
前記第１のバイト系列および前記第２のバイト系列が前記データ文字列内で連続する、前記請求項のいずれか一項に記載の配置構成。
【請求項９】
前記入力バッファ手段と前記履歴バッファ手段とにおけるデータの、第１の構成での比較から得られる列のキャリー情報を、前記入力バッファ手段と前記履歴バッファ手段とにおけるデータの、第２のデータ構成での比較において使用するために格納するための、キャリー手段（１３０）をさらに有する、前記請求項のいずれか一項に記載の配置構成。
【請求項１０】
データ文字列のＬＺ１圧縮のための方法（３００）であって、前記配置構成が
前記データ文字列の第１のバイト系列を入力バッファ（１４０）内に保持するステップと、
前記データ文字列の第２のバイト系列を履歴バッファ（１１０、１２０）内に保持するステップと、
前記入力バッファおよび前記履歴バッファに結合され、複数の行および列の比較ユニット（２００）を有する、マトリックス比較手段内で、前記入力バッファ内に保持されているバイトと前記履歴バッファ内に保持されているバイトとを比較するステップ（１７０）であって、前記履歴バッファのバイトは前記マトリックス比較手段内で斜めにずれていく比較ユニットに結合される、比較ステップと、
前記各行で、その行内の比較ユニットと同じ列内の先行する比較ユニットとにおいて、最大数の連続するバイト一致が発生した列、を検出するステップ（１５０）と、
前記検出ステップ（１５０）で検出された一致バイト系列をトークンとして符号化するステップ（１６０）と、
を有する方法。
【請求項１１】
前記比較ステップ（１７０）が、各比較ユニット（２００）において、前記比較ユニットと、同じ列内の先行する比較ユニットとで発生する、連続するバイト一致の数をカウントするステップ（２２０、２３０）を有し、
前記検出ステップ（１５０）が、各行で、最大カウントが発生した列を検出するステップを有する、
請求項１０に記載の方法。
【請求項１２】
前記比較ステップが、各比較ユニットにおいて、
前記入力バッファ手段からのバイトと前記履歴バッファ手段からのバイトとをコンパレータ手段内で比較するステップ（２１０）と、
同じ列内の他の比較ユニットから受け取ったカウント値をインクリメンタ手段内で増分するステップ（２２０）と、
前記コンパレータ手段の前記出力に依存して、同じ列内の他の比較ユニットに渡すために前記インクリメンタ手段の前記出力かまたはゼロ値かを選択するステップ（２３０）と、
を有する、請求項１１に記載の方法。
【請求項１３】
前記比較ステップが、各比較ユニット（４００）において、
前記入力バッファからのバイトと前記履歴バッファからのバイトとをコンパレータ手段（４１０）内で比較するステップと、
カウント値を表すいくつかのビットからなる値を同じ列内の他の比較ユニットから受け取るステップ（４２２、４２４、４２６）、ならびに前記コンパレータ手段の出力を受け取り、それに依存して、前記値をゼロにするか、またはシフトして前記値に更なるビットを追加することにより前記値を増分するかするステップと、
を有する、請求項１１に記載の方法。
【請求項１４】
前記検出手段（５００）のステップが、前記値の前記ビットを受け取るステップ（５２２、５２４、５２６）、およびそれらの論理ＯＲ演算を実行して前記値の最大値を生成するステップを有する、請求項１３に記載の方法。
【請求項１５】
前記履歴バッファ手段が、
前記マトリックス比較手段の第１の側にある行内の比較ユニットに結合された、第１のシフト・レジスタ手段と、
前記マトリックス比較手段の前記第１の側とは反対の第２の側にある行内の比較ユニットに結合された、第２のシフト・レジスタ手段と、
を有する、請求項１０乃至１４のいずれか一項に記載の方法。
【請求項１６】
前記第１のシフト・レジスタ手段および前記第２のシフト・レジスタ手段が、同一のシフト・レジスタ内のレベル・センシティブ・スキャン・デザイン（ＬＳＳＤ）の対を有する、請求項１５に記載の方法。
【請求項１７】
前記第１のバイト系列および前記第２のバイト系列が前記データ文字列内で連続する、請求項１０乃至１６のいずれか一項に記載の方法。
【請求項１８】
前記入力バッファと前記履歴バッファとにおけるデータの、第１の構成での比較から得られる列のキャリー情報を、前記入力バッファと前記履歴バッファとにおけるデータの、第２の構成での比較において使用するために格納するステップをさらに有する、請求項１０乃至１７のいずれか一項に記載の方法。
【請求項１９】
請求項１乃至９のいずれか一項に記載の配置構成を有する集積回路。
【請求項２０】
前記集積回路が特定用途向け集積回路（ＡＳＩＣ）である、請求項１９に記載の集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ圧縮に関し、具体的には「ＬＺ１」データ圧縮に関する。
【背景技術】
【０００２】
Ｌｅｍｐｅｌ−Ｚｉｖアルゴリズムは、データ圧縮の分野でよく知られている。具体的に言えば、ＬＺ１として知られる「履歴バッファ」バージョンが、その比較的少ないバッファ要件および予測可能な性能によってほとんどの技術にうまく適合するため、符号化データの損失のない圧縮が必要な場合には必ず、特にハードウェアの実装において、普及している。
【０００３】
ＬＺ１アルゴリズムは、入力文字列を検査すること、および見てきた文字の記録を維持することによって機能する。その後、文字列が最新履歴の中の以前に発生したものであることがわかった場合、その文字列は出力文字列内で、過去にその文字列が発生した場所および期間を示す符号である「トークン」によって置き換えられる。圧縮プログラムおよび圧縮解除プログラムのどちらも、規定の長さの「履歴バッファ」を使用しなければならないが、その他の点では双方の間でそれ以上情報を渡す必要はない。
【０００４】
意味のある文字列内で以前に見られたことのない文字は、「リテラル（そのままの文字）」として符号化される。その量は必要なビット数の拡張になるが、ほとんどのタイプのデータではトークン置換（したがって圧縮）の機会が圧縮できないデータよりも多いため、全体の圧縮が達成される。典型的な圧縮比率は２：１からおよそ１０：１の範囲である。
【０００５】
基本的なＬＺ１アルゴリズムのいくつかの変形が長年にわたって出現してきたが、少しずつ改善されてきている。
【０００６】
ＬＺ１アルゴリズムはバイト単位で働くため、従来のハードウェア実装では、入力ストリームを圧縮する際に１回に１バイトしか考慮の対象としない。各バイトが入力されるときに、たとえばコンテント・アドレッサブル・メモリ（ＣＡＭ）を使用して、すべての発生バイトについて「履歴バッファ」がスキャンされる。単一バイトは文字列置換のための有効な候補とはみなされないため、いずれかの一致が見つかれば、トークン置換が実施される前に引き続いての一致によって補足されなければならない。
【０００７】
入力される後続の各バイトも履歴バッファ内でシークされるが、報告される一致は既存の一致に従うもののみである。最終的に、（既知の一致に隣接する一致がそれ以上見つけられない場合）文字列の一致は終了し、存続した「文字列一致」が置換のために符号化される。一致が長いほどビットの節約も大きい。
【０００８】
クロック・サイクル当たり１バイトを処理するＬＺ１アルゴリズムの単なる実施は、現在のＡＳＩＣ（特定用途向け集積回路）技術に関する典型的なクロック・レートでおよそ１００〜２００ＭＢ／秒に限られる。しかしながらこれでは、単一のデータ・ストリームに高帯域幅を必要とするいくつかのアプリケーション（たとえばメモリ圧縮、光ネットワーク、およびＲＡＩＤディスク・アレイなど）には不十分な場合がある。性能、すなわち１秒当たりの圧縮可能バイト数を上げるためには、「サイクル時間」（バイトを入力してすべての一致を見つけるための所用時間）を減らすか、または１回に１バイトより多く検索するようにＣＡＭを修正しなければならない。多重入力ＣＡＭの設計は困難であるため、性能の向上はこれまで通常、ＣＡＭのアクセス時間、すなわちサイクル時間を短くすることに絞られてきた。しかしもちろんこの２つの改善策は相互に排他的ではなく、サイクル時間の削減に加えてマルチバイトＣＡＭを使用すれば、性能を上げることにつながる。
【０００９】
サイクル当たり複数バイトの圧縮に関する以前の試みは、米国特許第５７７１０１１号および第５９２９７９１号（後者は前者の分割出願）に見られるが、これらはサイクル当たり２バイトに匹敵する。これらの特許は、彼らの技法を２バイトより多くにまで拡張するのに必要な工程を示すことを意図するものであるが、その教示は実行方法に関して不完全かつ実現不可能であり、サイクル当たりＮバイトの圧縮について彼らの技法に必要な数の式に対してある公式を与えているが、式自体が導出される方法は示されていない。さらに、使用される「循環バッファ」をどのように適合させれば、サイクル当たりさらに多数の入力バイトを処理できるのかも明らかにされていない。
【００１０】
さらに以前の米国特許第５１７９３７８号では、入力バイトと履歴バッファとを比較するための異なる技法を使用している。上記の従来技術の特許に示されたように、各クロック・サイクルで、１回に１バイトを入力し、全並列比較（そのバイトと履歴バッファの内容全体とを比較すること）を採用するのではなく、米国特許第５１７９３７８号は、当該比較を「シストリック・アレイ」パイプライン方式を使用する段階まで細分化する。しかしながら、この特許の技法では、サイクル当たり複数入力バイトの処理レートは達成されず、サイクル当たり１バイトの完全な処理さえも達成されない場合がある。
【特許文献１】米国特許第５７７１０１１号
【特許文献２】米国特許第５９２９７９１号
【特許文献３】米国特許第５１７９３７８号
【発明の開示】
【発明が解決しようとする課題】
【００１１】
したがって、上記の欠点を軽減することのできるデータ圧縮のための方法および配置構成が求められている。
【課題を解決するための手段】
【００１２】
本発明の第１の態様に従い、特許請求の範囲の請求項１で請求されているような、データ文字列のＬＺ１圧縮のための配置構成が提供される。
【００１３】
本発明の第２の態様に従い、特許請求の範囲の請求項１０で請求されているような、データ文字列のＬＺ１圧縮のための方法が提供される。
【００１４】
次に、本発明を組み込んだデータ圧縮のための１つの方法および配置構成について、添付の図面を参照しながら説明するが、これは単に例を挙げて示すものに過ぎない。
【発明を実施するための最良の形態】
【００１５】
以下の好ましい実施形態は、ＩＢＭに属し「ＩＢＭＬＺ１」と呼ばれるＬＺ１変形との関連において説明するが、提示された技法はＬＺ１アルゴリズムのすべてのバージョンに適用可能であることを理解されよう。この技法は、サイクル当たり任意のバイト数または任意長の履歴バッファに拡張可能であるが、５１２バイトの履歴バッファを使用したサイクル当たり１２バイトの設計を使用して説明する。
【００１６】
次に図１を参照すると、圧縮配置構成１００には、２つのグループ（Ｌ１およびＬ２）の５１２バイト・ラッチ１１０および１２０、１つのグループの５１２キャリー・ラッチ１３０、１２バイト入力バッファ１４０、最大値関数／優先度エンコーダ１５０、トークン・エンコーダ１６０、および５１２×１２マトリックス・アレイ１７０の比較ユニット２００（以下でより詳細に説明する）が含まれる。
【００１７】
Ｌ２ラッチ１２０は、マトリックス１７０の最初の行にある５１２の比較ユニットと、マトリックスの１行下へ行くごとに連続して右へ１ユニットずつ斜めにずれていく比較ユニットとに、それぞれ結合されるが、これについては以下でより詳細に説明する。Ｌ１ラッチ１１０および関連付けられたキャリー・ラッチ１３０は、マトリックス１７０の最後の行にある５１２の比較ユニットにそれぞれ結合される。入力バッファ１４０の１２バイトは、マトリックス１７０の一番左の列にある１２行の比較ユニットにそれぞれ結合される。ＭＡＸ関数／優先エンコーダ１５０およびトークン・エンコーダ１６０は、マトリックス１７０の１２行の比較ユニットに結合される。
【００１８】
１２の入力バイトは、一致の検索において履歴バッファ全体と比較されなければならない。しかしながら、入力バイトの一部は、それ自体が「履歴」の一部を構成するものである。１２バイトの入力バッファは、たとえ全バイトが１サイクルで入っている場合でも、発生順に並んでいると想定しなければならない。したがって、入力バッファの一方の端は「最も近来度の高い」ものであり、他方は「最も近来度の低い」ものであって、あたかも「最も近来度の高い」バイトがそのプロセスに最初に入ったかのように考えられる。各バイトは、入力バッファ内で自分自身より「近来度の低い」バイトが履歴の一部となるものであり、したがって比較されるものであるということを考慮に入れなければならない。
【００１９】
入力バイトが、履歴バッファ内のバイト及び入力バッファ内で自分自身より近来度の低いバイトの両方と比較される方法が、図１に示されている。図の左側にある入力バッファ１４０を考えてみると、処理が従来のタイプ、すなわち１回に１バイトである場合、一番上のバイトが最初、一番下のバイトが最後に入ることになるが、この実施ではバイトはすべて同時に入力される。図を見るとわかるように、入力バッファの出力、すなわち１２の入力バイトはすべて、マトリックス１７０の各行にある各比較ユニット２００の入力に接続されている。各クロック・サイクルで、履歴バッファのコンテンツ、すなわちその５１２バイトすべては、入力バッファの最初の（最も近来度の低い）バイトとの比較のために下方向へ送られ、次に入力バッファの最も近来度の高いバイトとの比較のために、斜め下方向へ送られる。
【００２０】
履歴バッファのあらゆるバイトが一度に使用可能でなければならないため、従来のＲＡＭを履歴バッファに使用することはできない。この実施では、履歴バッファは、レベル・センシティブ・スキャン・デザイン（ＬＳＳＤ：Ｌｅｖｅｌ  Ｓｅｎｓｉｔｉｖｅ  Ｓｃａｎ  Ｄｅｓｉｇｎ）のＬ１−Ｌ２対として配置されたレジスタを使用して構築される。各クロック・サイクルの終わりに１２の入力バイトは履歴バッファにシフトされ、履歴バッファの古いコンテンツは１２バイトずつ長手方向に（図１に示されるように右へ）シフトされて、最も古い１２バイトが廃棄される。
【００２１】
図１で端折れ型の四角形で表された比較ユニット２００は、この設計の基本要素である。比較ユニットの拡大図が図２に示されている。各ブロックのジョブは、２つの入力バイトの値を比較して、一致したバイトを計数し、比較結果を制御ロジックに報告することである。
【００２２】
マトリックス１７０の比較ユニット２００には、比較のためにその行の入力バッファのバイト位置からのバイト値と、斜め左上のユニットから渡された履歴バッファのバイト値とを受け取るように配置構成された、バイト・コンパレータ（比較器）２１０が含まれる。インクリメンタ（増分器）２２０は、マトリックスの同じ列の真上にあるユニットから「カウント・イン」値を受け取り、「１」ずつ増分するように配置構成される。セレクタ２３０は、増分されたカウント値および「０」値を受け取り、コンパレータ２１０の出力に依存してこれらのいずれかから選択するように配置構成される。コンパレータ２１０が一致を示した場合、セレクタ２３０は増分されたカウント値を出力し、そうでない場合は「０」値を出力する。セレクタの出力は、「カウント・アウト」値として同じ列の真下にあるユニットに渡され、当該セレクタの出力はマトリックスの同じ行にあるＭＦＰＥにも渡される。太い破線で示されるように、セレクタ２１０に入力されたバイト値は、同じ行の右隣のユニットおよび斜め右下のユニットに渡される。
【００２３】
図２では、バイトが比較されることに加えて、ユニット２００が上のユニットから「カウント」を入力として受け取ることが示されており、これは、これまでに見てきた文字列の長さを示し、入力バッファ１４０の同じ行のバイトを示すものである。２つの入力バイトが一致した場合、その後比較ユニットはそのカウントを増分し、新しいカウントを下のユニットに渡すことになる。２つのバイトが一致しない場合、その後出力カウントは、入力カウント値に関係なくゼロに設定されることになる。
【００２４】
このカウントの値は、各比較ユニットの右側からも出力され、行の端部にある「最大値関数／優先エンコーダ」（ＭＦＰＥ）ロジック１５０に送り込まれる。圧縮プログラム１００の１２行それぞれについて、これらＭＦＰＥの１つがある。ＭＦＰＥの機能は、その行の５１２のうちのどの比較ユニット２００が最も長い文字列（すなわち、最も大きなカウント、最大値関数）を報告したかを判別すること、および、その行内の位置を符号化することである。複数の列が同じ大きさのカウントを生成した場合、ＭＦＰＥは（自由裁量で）一番左の値を符号化する（優先エンコード機能）。しかしながら、文字列はその行を超えて続く可能性があるため、ＭＦＰＥによって生成される値が必ずしも符号化されることになる文字列ではないことに留意されたい。
【００２５】
行１２（マトリックス１７０の最後の行）でまだ存続している文字列の一致は、次のサイクルまで継続することができる。図１の一番下にあるキャリー・ラッチ１３０は、任意の残存する文字列の位置をこの行から格納する。（その文字列の長さ、すなわち「カウント」は、図示されていない別の単一レジスタに格納される。）キャリーは、次のサイクルで比較ユニットの最初の行の「カウント入力」へ送り込まれる。ＬＺ１アルゴリズムによって符号化できる文字列の長さには、トークン内のビット数によって課される制限があることに留意されたい。（ＩＢＭＬＺ１では、この制限は２７１文字である。）最大数に達すると、トークンが放出され、文字列はゼロから開始しなければならない。トークン・エンコーダ１６０は従来技術で知られた方法と同じ方法で動作するため、その構造および機能についてはこれ以上詳細に説明する必要がないことを理解されよう。
【００２６】
各行の（ＭＦＰＥ１５０によって報告される）最大の文字列値およびその符号化された位置が、トークン・エンコーダ（ＴＥ）１６０に送り込まれる。ＴＥは各行について報告された長さを検査して、この一群の１２バイトの入力について文字列が符号化できるかどうかを判別する。文字列が符号化される場合、ＴＥは、文字列長と共に、ＭＦＰＥによってトークンの一部として報告された位置を使用する。長い文字列が１サイクル以上にまたがる場合、この長さは１２を超える可能性があることに留意されたい。このような場合、カウントは文字列が終了したときに符号化するようにＴＥ内で累算される。
【００２７】
文字列が見つからない場合（１バイトだけの一致は符号化する価値がないことに留意）、または１２バイトの一部が一致不可能な場合、ＴＥはリテラル（そのままの文字）を出力しなければならない。その場合、ＴＥは入力バッファ１４０から直接データを取得する。
【００２８】
図３は、圧縮動作を示すスナップショット３００である。「ｓｈｏｔ  ｏｆ  ａ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｐｅｒａｔｉｏｎ」というセンテンスが入力として使用され、説明を簡単にするために、５つの入力バイトおよび２７の履歴バッファ・バイトのみが示されている。黒丸（列３１０，３２０、３３０、３４０、および３５０）は、一致が検出された場所を示し、現在の入力バイト「ｉｏｎ」の列３２０で有用な文字列一致が見られる。これは、符号化のために転送されることになる、行内の列３２０の位置である。
【００２９】
比較ユニットに関する可能な実施４００が図４に示されている。比較ユニット４００（図に示されるように、マトリックス１７０の行３のユニットである）はコンパレータ４１０を有し、これが前述のように比較される２つのバイト値を受け取る。３つのＡＮＤゲート４２２、４２４、および４２６があり、それぞれ、コンパレータ４１０の出力を受け取るように各々の入力のうちの１つが接続され、同じ列の真上にある比較ユニットから（３ビットの「入力カウント」値を搬送する）３ビットの並びのうちのそれぞれ１つを受け取るように各々のもう１つの入力が接続されている。ＡＮＤゲート４２２、４２４、および４２６の出力は、コンパレータ４１０の出力と共に、（４ビットの「出力カウント」値をキャリーして）、同じ列の真下にある比較ユニットに接続される。「出力カウント」ビットの並びのうちの左３つは、それぞれ３つのＡＮＤゲート４３２、４３４、および４３６に接続される。ＡＮＤゲート４３２、４３４、および４３６の出力は、ＡＮＤゲート４２６の出力と共に、４入力ＯＲゲート４４０の入力に接続される。
【００３０】
ＯＲゲート４４０の出力は（マトリックス１７０の行３にある他の比較ユニットの出力と共に）、ＭＦＰＥ５００内にある５１２入力優先エンコーダ５１０の入力に接続される。ＭＦＰＥ５００内でも、ＡＮＤゲート４２２、４２４、および４２６の出力は、（マトリックス１７０の行３にある他の比較ユニット４００のＡＮＤゲートの出力と共に）５１２入力ＯＲゲート５２２、５２４、および５２６のそれぞれの入力に接続される。ＯＲゲート５２２、５２４、および５２６の出力は、マトリックス１７０の行３にあるそれぞれの比較ユニット４００の、ＡＮＤゲート４３２、４３４、および４３６の入力に論理反転して接続される。
【００３１】
コンパレータ４１０は、前述の比較ユニット２００内のコンパレータ２１０と同じであるが、比較ユニット４００では「カウント」がＮビット・ベクトルによって維持される。このベクトルのビットには１からＮまでの番号が付けられ、「ｎ」のカウントはビット１からｎが「１」とすることによって表される。ベクトル内の他のすべてのビットは「０」である。したがって、ゼロのカウントはすべてのビットがゼロとすることで示される。これは、以下の理由から、この設計における有用なカウント方法である。
１．必要なビット数Ｎは、行番号と同じ数だけが必要である（行１は１ビットだけ、行１２は１２ビットが必要である）。
２．「カウント」は、単に「１」を充てんして右にシフトするだけで容易に増分される。
３．最大値関数は、すべてのベクトルのそれぞれのビットのＯＲをとることによって、容易に実施される。
【００３２】
比較ユニット内には（ＡＮＤゲート４３２、４３４、および４３６ならびにＯＲゲート４４０の形の）少数の追加ロジックを伴うだけで、優先エンコーダも単純に構成される。
【００３３】
図４の比較ユニット４００の動作では、以下のように機能する。入力カウントは３ビット・ベクトルで表され、以下の４つの値を示すことができる。
【表１】
2005525039.tif 000003
【００３４】
コンパレータ４１０がこの行（行３）のこの列における一致を検出すると、カウントを増分し、ユニットの下から４ビット・ベクトルの「出力カウント」を生成する。増分は、入力ベクトルを右へ１ビットずつ効果的にシフトし、左側に「１」を追加することによって達成される。ここで一致がない場合、ＡＮＤゲート４２２、４２４、および４２６はすべてオフになり、「出力カウント」はゼロになる。
【００３５】
さらに図４に示されるように、４ビット・カウントの修正バージョンが、行の終わりにＭＦＰＥ５００の論理回路５１０、５２２、５２４、および５２６に出力される。３つの５１２入力ＯＲゲート５２２、５２４、および５２６は、この行の最大カウントを決定する（最低位ビットは１バイトのみのカウントを表すので使用されない）。この最大値は、この最大カウントに寄与しない列の比較ユニット４００にあるＡＮＤゲート４３２、４３４、および４３６を介して、勝者のカウントよりも小さいすべてのカウントを不適格とするために使用される。最大カウントを示す比較ユニットは、エンコーダ入力上で自らの立候補資格を宣言し、優先エンコーダはそれらのうちの一番左の位置を符号化する。一番下の行の比較ユニットにあるＯＲゲート４４０の「勝者」出力は、次のサイクル用に格納される５１２の「キャリー」ビットを有する。
【００３６】
上記の説明では、単一のサイクルで発生するすべての動作について示してきたが、当該設計はパイプライン方式の要因を排除するものではない。重要な要素は、次のサイクルの計算に含める準備のために、各行のキャリーを１サイクルで首尾よく格納しなければならないということである。
【００３７】
次のサイクル用に有効なキャリーを生成する重要なタイミング・パスは、この場合は、５１２入力ＯＲゲート（おそらくいくつかの直列接続のゲートを有する）を介し、次にキャリー用にさらに２つのＡＮＤゲートを介する、１２個までのＡＮＤゲートからなる。
【００３８】
したがって、およそ２０のゲート遅延の合計が、この設計の最大動作周波数を決定する。１２のＡＮＤゲート遅延は、ルックアヘッド（先見）技法を使用することによって減じることができるが、これはゲート・カウントに追加される。
【００３９】
マトリックス１７０の下の行にある比較ユニット４００ほど、比例的に多くのゲートを有することがわかり、その結果、ゲートの合計数は、サイクル当たりで処理されるバイト数の２乗で増加していくことが理解されよう。
【００４０】
さらに、前述の配置構成および方法は、典型的には、たとえばＡＳＩＣ（特定用途向け集積回路）などの集積回路（図示せず）の形のハードウェアで実行されるものであることも理解されよう。
【００４１】
結論として、前述の説明は、ゲート・カウントおよびタイミング上の問題によって制限される、サイクル当たり任意のバイト数を処理することのできるＬＺ１圧縮プログラムの構築方法を示したものであることを理解されよう。
【００４２】
前述のデータ圧縮技法は、広範囲に渡るストレージおよび通信の適用分野で使用可能であることを理解されよう。
【００４３】
前述のデータ圧縮技法は、サイクル当たり任意数のバイトまたは任意長の履歴バッファに拡張可能であるため、（前述のようにゲート・カウントおよびタイミング上の問題によってのみ制限される）任意の所望の帯域幅での動作を提供できるという利点を有することを理解されよう。
【００４４】
当業者であれば、前述の発明の実施形態に対する他の代替形態が明らかであることを理解されよう。
【図面の簡単な説明】
【００４５】
【図１】本発明を使用する圧縮配置構成で使用される比較マトリックスを示すブロック略図である。
【図２】図１の圧縮配置構成の比較ユニットを詳細に示すブロック略図である。
【図３】図１の比較配置構成における比較動作を示す概略図である。
【図４】図１の比較配置構成で使用される比較ユニット・マトリックスの特定の実施を詳細に示すブロック略図である。
【図１】
2005525039.tif 000004
【図２】
2005525039.tif 000005
【図３】
2005525039.tif 000006
【図４】
2005525039.tif 000007
【国際調査報告】
2005525039.tif 000008
2005525039.tif 000009
2005525039.tif 000010