(57)【要約】【課題】入力バッファ（１４０）に保持されたバイトをヒストリ・バッファ（１１０、１２０）に保持されたバイトと比較する、データ文字列のＬＺ１圧縮用の比較マトリックス（１７０）の比較ユニット（４００）で使用される回路（６４０）および方法を提供すること。【解決手段】この方法は、直列に結合された複数の論理ゲート段（７２０、７３０、７４０、７５０）を提供するステップを含み、複数の論理ゲート段の各々は、ユニットの出力の１つおよび複数の論理ゲート段のうちの別の段に受け渡されるキャリ値を生成し、複数の論理ゲート段に含まれる論理ゲート段の数と複数の論理ゲート段の各々に含まれる論理ゲートの数の積は、論理ゲート段を１つだけ有する等価な回路で必要とされる論理ゲートの数よりも少ない。複数の論理ゲート段を使用した結果生じる遅延は、キャリ・ルック・アヘッド値（７７０）を使用することによって減少させることができる。圧縮効率は、ユニットの出力で生成されるキャリ値をそれより前に生成されたキャリ・ルック・アヘッド値と比較して、キャリ値を改善できるかどうか決定することによって、改善することができる。
2006515121.tif 000002
【特許請求の範囲】
【請求項１】
入力バッファ（１４０）に保持されたバイトをヒストリ・バッファ（１１０、１２０）に保持されたバイトと比較する、データ文字列のＬＺ１圧縮用の比較マトリックス（１７０）で使用される回路（６４０）であって、
直列に結合された複数の論理ゲート段（７２０、７３０、７４０、７５０）であって、前記複数の論理ゲート段の各々は、ユニットの出力の１つおよび前記複数の論理ゲート段のうちの別の段に受け渡すためのキャリ値を生成するように配置され、前記複数の論理ゲート段に含まれる段の数と前記複数の論理ゲート段の各々に含まれる論理ゲートの数の積は、論理回路段を１つだけ有する等価な回路で必要とされる論理ゲートの数よりも少ない、複数の論理ゲート段を含む回路。
【請求項２】
別のキャリ値生成回路からキャリ値を受信するため、前記回路の入力に結合された入力ラッチ（７１０）をさらに含む、請求項１に記載の回路。
【請求項３】
所定の数の前記複数の論理ゲート段に結合された、ルック・アヘッド・キャリ値を生成する手段（７７０）をさらに含む、請求項１または２のいずれかに記載の回路。
【請求項４】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段からキャリ値を受信するように結合された中間ラッチ（７６０）をさらに含む、請求項３に記載の回路。
【請求項５】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）が、論理ゲート（８００）を介して比較器の出力に結合され、前記比較マトリックスの他の列の比較ユニットに結合されるように配置された論理手段（８１０）を含む、請求項３または４のいずれかに記載の回路。
【請求項６】
前記回路の出力で生成されるキャリ値をそれより前に生成されたキャリ・ルック・アヘッド値と比較して、前記キャリ値を改善できるかどうか決定する手段を含む、請求項３、４または５のいずれかに記載の回路。
【請求項７】
データ文字列のＬＺ１圧縮用の機構（１００）であって、
前記データ文字列の第１のバイト列を保持するための入力バッファ（１４０）と、
前記データ文字列の第２のバイト列を保持するためのヒストリ・バッファ（１１０、１２０）と、
前記入力バッファおよび前記ヒストリ・バッファに結合され、前記入力バッファに保持されたバイトと前記ヒストリ・バッファに保持されたバイトを比較するための比較ユニット（４００）を並べた複数の行および列を有する比較マトリックス（１７０）であって、前記ヒストリ・バッファの各バイトが、前記比較マトリックス内の斜めにずれた位置の比較ユニットに結合される、比較マトリックスと、
前記行の各々で、同じ列の先行する比較ユニットからその行の比較ユニットにかけて生じた連続するバイト・マッチの最大数を発生させた列を検出する検出手段（１５０）と、
前記検出手段によって検出されたマッチ・バイト列をトークンとして符号化する手段（１６０）と、
請求項１ないし６のいずれか一項に記載の回路（６４０）を含む比較ユニットとを含む機構。
【請求項８】
入力バッファ（１４０）に保持されたバイトをヒストリ・バッファ（１１０、１２０）に保持されたバイトと比較する、データ文字列のＬＺ１圧縮用の比較マトリックス（１７０）で使用される方法であって、
直列に結合された複数の論理ゲート段（７２０、７３０、７４０、７５０）を提供するステップであって、前記複数の論理ゲート段の各々は、ユニットの出力の１つおよび前記複数の論理ゲート段のうちの別の段に受け渡されるキャリ値を生成するように配置され、前記複数の論理ゲート段に含まれる段の数と前記複数の論理ゲート段の各々に含まれる論理ゲートの数の積は、論理回路段を１つだけ有する等価な回路で必要とされる論理ゲートの数よりも少ない、ステップを含む方法。
【請求項９】
前記ユニットの入力に結合された入力ラッチ（７１０）を提供するステップと、別のキャリ値生成ユニットからキャリ値を受信するステップをさらに含む、請求項８に記載の方法。
【請求項１０】
所定の数の前記複数の論理ゲート段に結合された、ルック・アヘッド・キャリ値を生成する手段（７７０）を提供するステップをさらに含む、請求項８または９のいずれかに記載の方法。
【請求項１１】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段に結合された中間ラッチ（７６０）を提供するステップと、ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段からキャリ値を受信するステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
ルック・アヘッド・キャリ値を生成する前記ステップ（７７０）が、所定の数の前記複数の論理ゲート段の比較器の出力に結合され、かつ前記比較マトリックスの他の列の比較ユニットに結合された論理手段（８１０）を提供するステップを含む、請求項１０または１１のいずれかに記載の方法。
【請求項１３】
前記ユニットの出力で生成されるキャリ値をそれより前に生成されたキャリ・ルック・アヘッド値と比較して、前記キャリ値を改善できるかどうか決定するステップを含む、請求項１０、１１または１２のいずれかに記載の方法。
【請求項１４】
データ文字列のＬＺ１圧縮用の方法（３００）であって、
前記データ文字列の第１のバイト列を入力バッファ（１４０）に保持するステップと、
前記データ文字列の第２のバイト列をヒストリ・バッファ（１１０、１２０）に保持するステップと、
前記入力バッファおよび前記ヒストリ・バッファに結合される、比較ユニット（４００）を並べた複数の行および列を有する比較マトリックスで、前記入力バッファに保持されたバイトと前記ヒストリ・バッファに保持されたバイトを比較するステップ（１７０）であって、前記ヒストリ・バッファの各バイトが、前記比較マトリックス内の斜めにずれた位置の比較ユニットに結合されるステップと、
前記行の各々で、同じ列の先行する比較ユニットからその行の比較ユニットにかけて生じた連続するバイト・マッチの最大数を発生させた列を検出するステップ（１５０）と、
前記検出ステップ（１５０）で検出されたマッチ・バイト列をトークンとして符号化するステップ（１６０）とを含み、
前記比較ステップ（１７０）が、請求項８ないし１３のいずれか一項に記載の方法を実行するステップを含む方法。
【請求項１５】
請求項１ないし６のいずれか一項に記載の回路、または請求項７に記載の機構を含む集積回路。
【請求項１６】
前記集積回路が、特定用途向け集積回路（ＡＳＩＣ）である、請求項１５に記載の集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮に関し、詳細には「ＬＺ１」データ圧縮に関する。
【背景技術】
【０００２】
レンペル−ジフ・アルゴリズム（Lempel-Ziv algorithm）は、データ圧縮の分野でよく知られている。特に、ＬＺ１として知られる「ヒストリ・バッファ（historybuffer）」バージョンは、必要なバッファが比較的少量で、性能も予測可能であることから、大部分の技術によく適合し、そのため、符号化データの可逆圧縮（losslesscompression）が必要とされるハードウェア実装において広く普及している。
【０００３】
ＬＺ１アルゴリズムは、入力文字列を検査し、出現した文字の記録を保持することによって機能する。最近のヒストリ中に発生したことのある文字列が出現した場合、その文字列は出力文字列の中では、その文字列が以前発生した場所とその長さを示すコードである「トークン」によって置き換えられる。圧縮器および伸張器は共に、定められた長さの「ヒストリ・バッファ」を使用しなければならないが、その他には、圧縮器と伸張器の間で受け渡す必要のある情報はない。
【０００４】
対照される文字列の中に出現したことのない文字は、「直定数（literal）」として符号化される。このような符号化は、必要となるビット数を増やすことになるが、大部分のタイプのデータでは、トークンによる置き換えが発生する（したがって、圧縮される）場合のほうが、データが圧縮できない場合より多く、そのため、全体的に見れば、圧縮が達成される。標準的な圧縮率は、２：１から約１０：１の間である。
【０００５】
長年にわたって、基本ＬＺ１アルゴリズムの変種がいくつか現れたが、改善は漸進的であった。
【０００６】
ＬＺ１アルゴリズムは、バイト単位で機能するので、従来のハードウェア実装では、入力ストリームを圧縮する際、一度に１バイトだけしか考慮されない。バイトが入力されるたび、例えば、連想メモリ（ＣＡＭ:Content-Addressable-Memory）を用いて、すべてのバイトの発生について「ヒストリ・バッファ」がスキャンされる。単一バイトは文字列の置き換えの有効な候補とは見なされないので、トークンによる置き換えを行うには、見つかったマッチに引き続いてマッチが見つからなければならない。
【０００７】
後続の各入力バイトもヒストリ・バッファ内で探索されるが、報告されるマッチは、既存のマッチに続くマッチだけである。最後に、（既知のマッチに接するマッチがもう見つからない場合に）文字列マッチは終り、残存「文字列マッチ」（surviving “string match”）が置換のために符号化される。マッチが長くなるほど、より多くのビットを節約できる。
【０００８】
クロック・サイクル当り１バイトを処理するＬＺ１アルゴリズムの簡単な実装では、現在のＡＳＩＣ（特定用途向け集積回路）技術で標準的なクロック速度で、約１００〜２００ＭＢ／秒が限界である。しかし、単一データ・ストリーム用に高帯域を必要とする、（例えば、メモリ圧縮、光ネットワーク、ＲＡＩＤディスク・アレイなどの）ある種のアプリケーションにとっては、この圧縮性能では不十分な場合がある。性能を向上させるには、すなわち、１秒当りに圧縮可能なバイト数を増やすには、「サイクル・タイム」（バイトを入力し、すべてのマッチを見つけるのに要する時間）を短縮するか、または一度に１バイトより多く探索できるようにＣＡＭを変更しなければならない。マルチ入力ＣＡＭを設計するのが困難なことから、性能改善を図る際には、ＣＡＭのアクセス時間、したがって、サイクル・タイムを短縮することに通常は努力が注がれる。しかし、もちろん、２つの改善策は互いに排他的ではなく、サイクル・タイムの短縮に加えて、マルチバイトＣＡＭを用いても、性能は向上する。
【０００９】
本出願と同時に同じ出願者によって出願された、「データ圧縮用の方法および機構（METHODAND ARRANGEMENT FOR DATA COMPRESSION）」と題する国際出願（国際出願番号ＰＣＴ／ＧＢ０３／００３８４）に、データ文字列の第１のバイト列を入力バッファに保持し、データ文字列の第２のバイト列をヒストリ・バッファに保持し、入力バッファおよびヒストリ・バッファに結合され、比較ユニットを複数の行および列に並べた比較マトリックスで、入力バッファに保持されたバイトとヒストリ・バッファに保持されたバイトを比較し、その際、ヒストリ・バッファの各バイトは比較マトリックス内の斜めにずれた位置の比較ユニットに結合されており、各行において、同じ列の先行する比較ユニットからその行の比較ユニットにかけて生じた連続するバイト・マッチの最大数を発生させた列を検出し、前記検出ステップで検出されたマッチ・バイト列をトークンとして符号化することによって、データ文字列のＬＺ１圧縮を行うための方法および機構が記載されている。
【００１０】
しかし、この技法は、サイクル当りのバイト数は何バイトにでも拡張できるものの、それを実装するのに消費される論理ゲートの数は、バイト数の２乗に比例して増加し、そのため、サイクル当り約４バイトを超える設計はコストが高くなる。
【特許文献１】国際出願番号ＰＣＴ／ＧＢ０３／００３８４
【発明の開示】
【発明が解決しようとする課題】
【００１１】
したがって、上記の不都合を緩和し得るデータ圧縮のための方法および機構が必要とされている。
【課題を解決するための手段】
【００１２】
本発明の第１の態様によれば、請求項１に記載の、データ列のＬＺ１圧縮用の比較マトリックスで使用される回路が提供される。
【００１３】
本発明の第２の態様によれば、請求項７に記載の、データ列のＬＺ１圧縮用の機構が提供される。
【００１４】
本発明の第３の態様によれば、請求項８に記載の、データ列のＬＺ１圧縮用の比較マトリックスで使用される方法が提供される。
【００１５】
本発明の第４の態様によれば、請求項１４に記載の、データ列のＬＺ１圧縮用の方法が提供される。
【００１６】
本発明を具現したデータ圧縮用の一方法および機構を、添付の図面を参照しながら、例としてのみ説明する。
【発明を実施するための最良の形態】
【００１７】
以下に示す本発明の好ましい実施形態は、「ＩＢＭＬＺ１」として知られるＩＢＭが開発したＬＺ１の変種を前提として説明されるが、提示される技法がＬＺ１アルゴリズムのすべてのバージョンに適用可能であることは理解されよう。この技法は、任意のサイクル当りバイト数、または任意のヒストリ・バッファ長に拡張可能だが、５１２バイトのヒストリ・バッファを備え、サイクル当りのバイト数を１２バイトとする設計によって説明を行う。
【００１８】
ここで図１を参照すると、圧縮機構１００は、２グループ（Ｌ１およびＬ２）の５１２バイトのラッチ１１０、１２０と、１グループの５１２個のキャリ・ラッチ（carry latch）１３０と、１２バイトの入力バッファ１４０と、ＭＡＸ関数（ＭＦ:Max function）／優先エンコーダ（ＰＥ:PriorityEncoding）１５０と、トークン・エンコーダ１６０と、（以下でより詳細に説明する）比較ユニット２００を並べた５１２×１２のマトリックス・アレイ１７０とを含む。
【００１９】
Ｌ２ラッチ１２０は、マトリックス１７０の第１行の５１２個の比較ユニットとそれぞれ結合され、マトリックスのより下の行では、以下でより詳細に説明するように、１行下がるごとに１ユニット右斜め下の比較ユニットと次々に結合される。Ｌ１ラッチ１１０とそれに関連付けられたキャリ・ラッチ１３０は、マトリックス１７０の最終行の５１２個の比較ユニットとそれぞれ結合される。入力バッファ１４０の１２個のバイトは、マトリックス１７０の最も左の列で１２行の比較ユニットとそれぞれ結合される。ＭＡＸ関数／優先エンコーダ１５０とトークン・エンコーダ１６０は、マトリックス１７０の１２行の比較ユニットと結合される。
【００２０】
１２個の入力バイトは、ヒストリ・バッファ全体と比較して、マッチを探索しなければならない。しかし、入力バイト自体の一部も、「ヒストリ」の一部を構成する。１２バイトの入力バッファは、実際には全バイトが１サイクル中に入力されるが、各バイトは時系列的に並んでいると仮定しなければならない。したがって、入力バッファの一方の端は「最新度が最高」で、もう一方の端は「最新度が最低」であると見なされ、あたかも「最新度が最低」のバイトから最初に処理に入ったかのようである。各バイトは、入力バッファ内の「最新度がより低い」バイトもヒストリの一部であると見なして、しかるべく比較されなければならない。
【００２１】
入力バイトをヒストリ・バッファ内のバイトおよび入力バッファ内の最新度がより低いバイトと比較する方法が、図１に示されている。図の左側の入力バッファ１４０について考える。この実装では、すべてのバイトが同時に入力されるのだが、１バイトずつ処理を行う従来タイプの処理が行われるとすると、最上位バイトが最初に処理に入り、最下位バイトが最後に処理に入ることになる。図から分かるように、入力バッファの出力は、１２個の入力バイトのすべてについて、マトリックス１７０の各行のすべての比較ユニット２００の入力に接続される。各クロック・サイクルで、ヒストリ・バッファの内容が、その５１２個のバイトのすべてについて、フィードダウンされて、入力バッファの先頭の（最新度が最低の）バイトと比較され、さらに右斜め下方向にフィードダウンを繰り返し、最後は入力バッファの最新度が最高のバイトと比較される。
【００２２】
ヒストリ・バッファのすべてのバイトは同時に利用可能でなければならないので、従来のＲＡＭはヒストリ・バッファに使用できないことは理解されよう。この実装では、ヒストリ・バッファは、level sensitive scan design（ＬＳＳＤ）のＬ１−Ｌ２としてペアで配置されるレジスタを用いて構成される。各クロック・サイクルの最後で、１２個の入力バイトは、ヒストリ・バッファの中にシフトし、ヒストリ・バッファの古い内容は、（図１に示すように右に）１２バイトだけシフトし、最も古い１２バイトは廃棄される。
【００２３】
図１に左上隅を切り落とした正方形によって表される比較ユニット２００は、この設計の基本的要素である。比較ユニットの拡大図が、図２に示されている。各ブロックの仕事は、２つの入力バイトの値を比較し、マッチ・バイトの数を集計し、制御ロジックにウィニング・マッチ（winning match）を報告することである。
【００２４】
マトリックス１７０内の比較ユニット２００は、その行に対応する入力バッファのバイト位置のバイト値と左斜め上のユニットから渡されたヒストリ・バッファのバイト値を比較のために受信するように構成された、バイト比較器２１０を含む。増加器２２０は、マトリックスの同じ列の真上のユニットから「カウント・イン」値を受信し、それを「１」だけ増やすように構成される。選択器２３０は、増やされたカウント値と「０」値を受信し、それらの一方を比較器２１０の出力に基づき選択するように構成される。比較器２１０がマッチを示している場合は、選択器２３０は、増やされたカウント値を出力し、そうでない場合は、「０」値を出力する。選択器の出力は、「カウント・アウト」値として、同じ列の真下のユニットに渡されるとともに、マトリックスの同じ行のＭＡＸ関数／優先エンコーダにも渡される。太い破線で示されるように、選択器２１０に入力されるバイト値は、同じ行の右隣のユニットと右斜め下のユニットに渡される。
【００２５】
図２には、ユニット２００が、比較されるバイトに加えて、それまでに見つかった文字列の長さを示す「カウント」を上のユニットから入力として取り込み、また入力バッファ１４０の同じ行のバイトも取り込むことが示されている。２つの入力バイトがマッチした場合、比較ユニットはカウントを増やし、新しいカウントを下のユニットに渡す。２つの入力バイトがマッチしなかった場合、出力カウントは、入力カウントの値にかかわらず、０に設定される。
【００２６】
このカウントの値はまた、各比較ユニットの右側から出力され、行の終端の「ＭＡＸ関数／優先エンコーダ」（ＭＦ／ＰＥ）ロジック１５０に供給される。こうしたＭＦ／ＰＥユニットは、圧縮器１００の１２の行それぞれに１つ存在する。ＭＦ／ＰＥの機能は、その行の５１２個の比較ユニット２００のうちのどの比較ユニットが最長の文字列（すなわち、最大カウント−ＭＡＸ関数）を報告したかを決定し、行内のその位置を符号化することである。複数の列が同じ大きさのカウントを生成した場合、ＭＦ／ＰＥは、（恣意的に）最も左側の値を符号化する（優先符号化機能（priority encoding function））。しかし、文字列はその行を超えて継続することもあるので、ＭＦ／ＰＥによって生成される値は、符号化される文字列であるとは限らない点に留意されたい。
【００２７】
第１２行（マトリックス１７０の最終行）でまだ有効な文字列マッチは、次のサイクルに持ち越すことができる。図１の最下部のキャリ・ラッチ１３０は、この行から残存文字列（surviving string）がある位置を保存する（その文字列の長さ、すなわち、「カウント」は、図示されていない別個の単一レジスタに保存される）。キャリは、次のサイクルで、比較ユニットの第１行に「カウント入力」として供給される。ＬＺ１アルゴリズムによって符号化できる文字列長には、トークンのビット数によって課された限界があることに留意されたい（ＩＢＭＬＺ１では、この限界は２７１文字である）。最大数に達した場合、トークンは初期化され（atoken is emitted）、文字列は０から開始しなければならない。トークン・エンコーダ１６０は、従来技術において周知な方法と同じ方法で動作すること、したがって、その構造および機能についてこれ以上詳細に説明する必要がないことを理解されたい。
【００２８】
（ＭＦ／ＰＥ１５０によって報告された）各行の最大文字列値とその符号化された位置は、トークン・エンコーダ（ＴＥ）１６０に供給される。ＴＥは、各行ごとに報告された長さを検査し、この１２個の入力バイトの束について、どこで文字列を符号化できるかを決定する。文字列を符号化する場合、ＴＥは、文字列長に加えて、ＭＦ／ＰＥ１５０によって報告された位置も、トークンの一部として使用する。長い文字列が複数のサイクルにまたがる場合、長さが１２を超える場合があることに留意されたい。このようなことが起った場合、文字列が終了した際に行われる符号化に備えて、カウントはＴＥ内に蓄積される。
【００２９】
文字列が見つからない場合（１バイトだけのマッチは符号化には無意味であることに留意されたい）、すなわち、１２バイトのどの部分もマッチさせられない場合、ＴＥは直定数を出力しなければならい。これを行うため、ＴＥは、データを入力バッファ１４０から直接取得する。
【００３０】
図３には、圧縮操作３００のスナップショットが示されている。直前の文「asnapshot of a compression operation」が入力に用いられており、例を簡単にするため、５バイトの入力バイトと２７バイトのヒストリ・バッファ・バイトだけが示されている。（列３１０、３２０、３３０、３４０、３５０の）黒丸は、マッチが検出された場所を示しており、現在の入力バイト「ion」とマッチする有用な文字列マッチを、列３２０に発見することができる。この行内の列３２０の位置が、符号化のために転送される。
【００３１】
図４には、比較ユニット用の可能な実装が示されている。（図示のようにマトリックス１７０の第３行のユニットである）比較ユニット４００は、上で説明したように比較される２つのバイト値を受信する比較器４１０を有する。３個のＡＮＤゲート４２２、４２４、４２６は各々、比較器４１０の出力を受信するように接続された一方の入力をもち、同一列の真上のユニットからの（３ビットの「入力カウント」値を伝送する）３本のビット線のうちの１本をそれぞれ受け入れるように接続されたもう一方の入力をもつ。ＡＮＤゲート４２２、４２４、４２６の出力は、比較器４１０の出力と共に、（４ビットの「出力カウント」値を伝送し）同一列の真下の比較ユニットに接続される。左側の３つの「出力カウント」ビット線は、３個のＡＮＤゲート４３２、４３４、４３６の入力にそれぞれ接続される。ＡＮＤゲート４３２、４３４、４３６の出力は、ＡＮＤゲート４２６の出力と共に、４入力ＯＲゲート４４０の入力に接続される。
【００３２】
ＯＲゲート４４０の出力は（マトリックス１７０の第３行の他の比較ユニット４００の出力と共に）、ＭＦ／ＰＥ５００内で、５１２入力の優先エンコーダ５１０の入力に接続される。ＭＦ／ＰＥ５００内ではまた、ＡＮＤゲート４２２、４２４、４２６の出力も（マトリックス１７０の第３行の他の比較ユニット４００のＡＮＤゲートの出力と共に）、５１２入力のＯＲゲート５２２、５２４、５２６の入力にそれぞれ接続される。ＯＲゲート５２２、５２４、５２６の出力は、マトリックス１７０の第３行の各比較ユニット４００内のＡＮＤゲート４３２、４３４、４３６の入力に反転して接続される。
【００３３】
比較器４１０は、上で説明した比較ユニット２００内の比較器２１０と同じであるが、比較ユニット４００では、「カウント」は、Ｎビット・ベクトルによって維持される。このベクトルのビットは、１からＮまで番号が振られ、カウント「ｎ」は、１からｎビットまでを「１」にすることによって表される。ベクトル内の他のすべてのビットは「０」である。したがって、カウント０は、すべてのビットを０にすることによって示される。これは、以下の理由から、この設計においてカウントを行う際の有用な方法となる。
【００３４】
１．必要とされるビット数Ｎは、行番号と同じ大きさがありさえすればよい（第１行は１ビットしか必要とせず、第１２行は１２ビットを必要とする）。
【００３５】
２．「カウント」は、右にシフトさせ「１」を補充するだけで、容易に増やすことができる。
【００３６】
３．ＭＡＸ関数は、すべてのベクトルどうしで対応するビットの論理和をとることによって、容易に実装することができる。
【００３７】
比較ユニット内に（ＡＮＤゲート４３２、４３４、４３６およびＯＲゲート４４０の形態をした）小規模の追加ロジックをもたせることで、優先エンコーダも簡単になる。
【００３８】
図４の比較ユニット４００は、動作する際、次のように機能する。入力カウントは、３ビット・ベクトルによって表され、４種類の値を示すことができる。
【００３９】
【表１】
2006515121.tif 000003
【００４０】
比較器４１０は、この行（第３行）のこの列でマッチを検出した場合、カウントを増やし、ユニットの下部から４ビット・ベクトルの「出力カウント」を生成する。カウント増加は、入力ベクトルを１ビット右にシフトさせ、左側に「１」を付け加えることによって効果的に達成される。ここでマッチを検出しなかった場合、ＡＮＤゲート４２２、４２４、４２６はすべて０を出力し、「出力カウント」は０に戻される。
【００４１】
変更を施された４ビット・カウントは、やはり図４に示すように、行の終端でＭＦ／ＰＥ５００内の論理回路５１０、５２２、５２４、５２６に出力される。３個の５１２入力のＯＲゲート５２２、５２４、５２６が、この行の最大カウントを決定する（低位ビットは、１バイトのカウントを表すだけなので使用されない）。この最大値は、この最大カウントに寄与していない列の比較ユニット４００のＡＮＤゲート４３２、４３４、４３６を用いて、ウィニング・カウントよりも小さなすべてのカウントを失格させるのに使用される。最大カウントを示す比較ユニットは、エンコーダ入力上で立候補を宣言し、優先エンコーダは、それらの最も左側のものの位置を符号化する。最下行の比較ユニット内のＯＲゲート４４０の「ウィン（win）」出力は、次のサイクルのために保存される５１２個の「キャリ」ビットを構成する。
【００４２】
上記の説明では、すべての動作は単一サイクル内で発生するものとされたが、この設計は、一部の要素のパイプライン化を排除するものではない。クリティカルな要因は、各行についてのキャリを、次のサイクルの計算への算入に備えて、１サイクル内でうまく保存しなければならないことである。
【００４３】
クリティカルなタイミング・パスは、次のサイクルのための有効キャリを生成するパスであり、この例では、最大１２個（１２文字がマッチした文字列の場合）のＡＮＤゲート、（おそらく複数のカスケード・ゲートを有する）５１２入力のＯＲゲート、キャリ用のさらに２個のＡＮＤゲートを通過するパスとして構成される。
【００４４】
したがって、２０ほどのゲート遅延の総和が、この設計の最大動作周波数を決定する。１２のＡＮＤゲート遅延は、ルックアヘッド技法を用いて減らすことができるが、それによって、ゲート数は増える。
【００４５】
比較ユニット４００は、マトリックス１７０の下の行に行くほどそれに比例して多くのゲートを有すること、そのため、ゲートの総数は、サイクル当りに処理されるバイト数の２乗に比例して増加することが理解できよう。
【００４６】
ゲート数の削減
ゲートの総数は、サイクル当りに処理されるバイト数（Ｎ）の２乗に比例して（公式Ｎ（Ｎ＋１）／２に従って）増加するため、サイクル当りに処理されるバイト数が大きくなると（例えば、４より大きくなると）、実行不能になる場合がある。この実行不能性を低下させるため、さらなる技法を使用して、ゲートの総数を削減することができる。
【００４７】
次に図５を参照すると、比較マトリックス１７０の各列は、ゲートから成る「三角形」（６００）と考えることができ、三角形の上に行くほどゲート数は少なくなる。三角形の底部における出力は、最長の残存文字列を示す「キャリ」であり、次のサイクルのために保存される。三角形の面積は、使用されるゲートの数に比例する。
【００４８】
次に図６を参照すると、各三角形をより小さな三角形（６１０、６２０、６３０）に分割し、配置６４０における対応する総面積を小さくすることによって、より高い効率性を達成することができる。図５の単一の三角形を図６の３つの三角形６１０、６２０、６３０に分割することによって、ゲート数は７３から３０に削減される。
【００４９】
より小さな各三角形は、下方の次の三角形に入力される独自の「キャリ」を生成しなければならない。このキャリは、最長の現在文字列を通知するすべての列で真となり、そのため、ＭＡＸ関数／優先エンコーダ（ＭＦ／ＰＥロジック）からのフィードバックを必要とする。したがって、各キャリ生成は、追加の遅延を招き、これらの遅延すべての総和は、設計において分割可能な三角形の数、ひいてはなし得る削減に制限を設ける。
【００５０】
より詳細な例が、図７および図８に示されている。図７として左側および下側の図に示された（図５に示された三角形のゲート配置に対応する）元の設計は、１２バイト毎サイクルの設計であり、文字列蓄積ロジックのために、１２×（１２＋１）／２、すなわち７８個のゲートを使用する。キャリ出力に要するスルー・タイムは、約（１２＋３）＝１５ゲート分の遅延である。（右上の破線の枠内に図８として設計全体の４分の１に相当する部分が示された）ゲートを削減した設計は、元の設計を（３つの反復部分をもつ図６の配置の代わりに）、４×３×（３＋１）／２、すなわち２４個のゲートを費やして、４×（３＋３）＝２４ゲート遅延のスルー・タイムを有する、３バイト毎サイクルの比較器から成る４つの反復部分に分割する。
【００５１】
遅延の削減
図８の配置では、ゲート数は著しく削減されるが、その結果増加する遅延が、必要なサイクル・タイムにとって大き過ぎるものとなる場合がある。これを抑えるため、ある種のパイプライン化を利用することができる。
【００５２】
図９には、ラッチ７１０と、４つの段、すなわち、ゲートの三角形７２０、７３０、７４０、７５０が描かれた、図８を略書きした図が示されている。図１０には、どのように図８の設計をさらに改良して、サイクル当りの遅延を削減するかが示されている。図１０の配置では、図９のキャリ・チェーン（carry chain）が２つに分割され、段７３０からの前半のキャリ（Ｂ）の結果は、第２のサイクル（Ｄ）に備えて（ラッチ７６０に）ラッチされる。ラッチされたキャリは、第２のサイクルでチェーンの残りを伝播されるが、チェーンの前半では、次のサイクルのキャリが処理される。したがって、必要なサイクル・タイムは半分に削減される。
【００５３】
しかし、キャリ・チェーンの前半で、直前のサイクルについての完全なキャリを入力（Ａ）として必要とする点が、ことを複雑にする。キャリ・チェーンの前半は、図９の配置から生成されるのと同じ値を必要とする。しかし、直前のサイクルは、全体的なキャリを生成するには短すぎ、チェーンの前半からのキャリしか生成しない。
【００５４】
これを解決するには、キャリ・チェーンの前半で、フル・チェーンについてのキャリを生成するキャリ・ルック・アヘッド（carry look-ahead）（Ｃ）を作り出さなければならない。列のデータを完全に処理する必要がないことに留意されたい（これは、ラッチ７６０の右側のロジックによって第２のサイクルで達成される）。キャリ（最長の残存文字列をもつ１つまたは複数の列）の提供が必要なだけである。このキャリは、第２の組のゲートによって提供されるフル処理の場合よりも少ないゲートで生成することができる。このキャリ・ルック・アヘッド（Ｃ）は、段７７０で作り出される。
【００５５】
キャリ・ルック・アヘッド
図１１には、このルック・アヘッド・キャリをどのように生成するかが示されている。下側の６個の比較器（段７４０から３個、段７５０から３個）の出力が、上側ブロックからのキャリ出力（図１０の信号「Ｂ」）と共に使用される。図７の下側の図に示されたキャリ生成器と類似するロジック８１０が、第１２行における最善の残存文字列を決定する。これが次のサイクルで使用するのに適したキャリである。
【００５６】
キャリ・ルック・アヘッド・ペシミスム
しかし、図１１のルック・アヘッド・ロジックによって生成されたキャリは、有効なキャリではあるが、最適な圧縮を提供するとは限らない。このロジックは、第１２行を専ら対象とするので（タイミング制約を満たすため、こうする必要がある）、その他の文字列候補を見落とすことがあり得る。
【００５７】
図１２には、このようなことがどのようにして起こるか、その一例が示されている。図には、下側６行で発生した３つの文字列（９１０、９２０、９３０）が示されている。長さが４の最も左の文字列（９１０）は、長さが３の最も右の文字列（９３０）よりも長いので、ルック・アヘッド・コンテストに勝利する。しかし、（ルック・アヘッドの対象から外れた）長さが３の真中の文字列（９２０）は、上側３個のブロックからのキャリを生成し、この時点で最も左の文字列（９１０）よりも優勢となる。最も左の文字列（９１０）は、上側ブロックからのキャリを持たずに次の行から開始し、その長さは３に減少する。したがって、最終行で残存している２つの文字列（９１０および９３０）がキャリを生成し、結局、おそらく最も右の文字列（９３０）が、より長いマッチを提供するであろう。
【００５８】
（最も右の文字列９３０は最終勝利者でないと仮定する）この「ペシミスム」の結果、より少ないキャリしか保存されず、このことは、次のサイクルで有効長を引き継ぐことのできる文字列が見つからないことを意味する。このことによってエラーが生じることはないが、エンコーダの圧縮効率を僅かに低下させることがあり得る。
【００５９】
しかし、パフォーマンスの一部を犠牲にすることによって、圧縮効率を回復することができる。ルック・アヘッド・キャリ生成器は常に、フル・デコードの場合と同じかまたはより少ない数のキャリを生成する。フル・デコードの結果は、第２サイクルで分かるが、フル・スピード動作にとっては通常は遅すぎる。ラッチされたルック・アヘッド・キャリの値を第２サイクルからのフル・キャリ出力と比較することによって、第１サイクルのキャリが非効率なものかどうかを決定することができる。非効率なものである場合、サイクルを繰り返して、新しいキャリを設定することができる。
【００６０】
図１３には、これがどのように動作するか、その一例が示されている。この図には、図１０の５箇所Ａ、Ｂ、Ｃ、Ｄ、Ｅにおける信号が示されており、それらは様々な段で生成されるキャリである。信号上の数字は、特定のキャリが生成される入力サイクルを示す。クエスチョン・マークは、生成されるキャリが正しくないかもしれないこと、すなわち、ペシミスティックであり得ることを示す。
【００６１】
第１サイクルでは、入力番号１の間に、ラッチされたルック・アヘッドが生成される。このサイクルの間に、上位ブロックが、（Ｂで２の）キャリを生成し、その後、（Ｃで２？の）ルック・アヘッド・キャリが生成される。ルック・アヘッドの質は、この時点では、確かではなく、したがって、「？」が付けられている。やがて、（Ｄ）は入力番号１からラッチされたキャリをもち、（Ｅ）ではデータの下半分についてのキャリが生成される。
【００６２】
第２サイクルでは、（Ａ）はラッチされた不確かなルック・アヘッド・キャリをもつ。（Ｂ）および（Ｃ）で生成されたキャリは、共に（Ａ）に依存しているため、（３？で示すように）不確かである。しかし、（Ｄ）および（Ｅ）は正しいキャリを示す。これは、それらのキャリは、１サイクル遅延しているものの、フル・チェーンから導き出されたからである。
【００６３】
（１０００’で示される）第２サイクルの終りで、（Ａ）でラッチされたルック・アヘッド・キャリは、（Ｅ）からの正しいキャリと比較される。この例では、それらは同じであると仮定されるので、ラッチされたルック・アヘッド・キャリ（Ａにおける２）は正しく、それから導き出されたキャリ（Ｂにおける３）も正しい。このサイクルでは、ルック・アヘッド（Ｃにおける３？）は、まだ信用することができず（キャリ値は改善されることもあり得る）、次のサイクルでのラッチされたキャリ（Ａ）には、まだ「？」が付けられている。
【００６４】
第３サイクルも、（１０００”で示される）サイクルの終りでの（Ａ）と（Ｅ）の比較が失敗する点を除いて同様である。ラッチされたルック・アヘッド・キャリ（３？）は、ペシミスティックである。そのため、それから導き出された結果（２つの４？）は廃棄され、（Ａ）は（Ｃ）からではなく（Ｅ）からラッチされる。サイクルは、今では正しいことが判明したキャリを用いて繰り返され、新しいキャリが生成される。
【００６５】
（図１２の場合のように）ルック・アヘッド・キャリがペシミスティックなときだけ稀に加えられる追加のサイクルによって、完全な効率が回復されることが理解できよう。このチェックを行わなくても圧縮動作は正しいが（正確にデータを伸張するが）、高い圧縮率を示さない場合があることを思い出されたい。したがって、上記の技法の使用は、スピードまたは高い圧縮率が求められているかどうかに応じて、選択可能であるべきである。
【００６６】
要約
要約すれば、本発明は、サイクル当り所定のバイト数を処理するのに必要とされるゲートの数を劇的に削減する、初期のＬＺ１マルチバイト圧縮エンジンに対する改良を提供するものであることが理解されよう。追加の遅延を補償するのに、ルック・アヘッド・キャリ生成器を必要とする、パイプライン処理を利用することができる。ルック・アヘッド・キャリの短所は、パフォーマンスを僅かに低下させるだけで補正することができる。
【００６７】
上で説明した機構および方法は一般に、例えば、ＡＳＩＣ（特定用途向け集積回路）などの集積回路（図示せず）の形態をとる、ハードウェアで実施することができることも理解されよう。
【００６８】
上で説明したデータ圧縮技法が、ストレージおよび通信アプリケーションの広い範囲で利用できることは理解されよう。
【図面の簡単な説明】
【００６９】
【図１】本発明を利用する圧縮機構内で使用される比較マトリックスの概略ブロック図である。
【図２】図１の圧縮機構の比較ユニットを詳細に示した概略ブロック図である。
【図３】図１の圧縮機構で行われる圧縮操作の概略図である。
【図４】図１の圧縮機構で使用される比較ユニット・マトリックスの具体的な実装を詳細に示した概略ブロック図である。
【図５】本発明を利用することで達成されるゲート数の削減を示した概略図である。
【図６】本発明を利用することで達成されるゲート数の削減を示した概略図である。
【図７】本発明で使用し得る４ウェイ・ブレークダウン（4-way break down）の一例を示した概略ブロック図である。
【図８】本発明で使用し得る４ウェイ・ブレークダウンの一例を示した概略ブロック図である。
【図９】本発明で使用し得る遅延削減を示した概略ブロック図である。
【図１０】本発明で使用し得る遅延削減を示した概略ブロック図である。
【図１１】本発明で使用し得るルック・アヘッド・キャリ（look-ahead carry）の生成を示した概略ブロック図である。
【図１２】本発明で生じ得る「キャリ・ルック・アヘッド・ペシミスム（carrylook-ahead pessimism）」問題の一例を示した概略ブロック図である。
【図１３】本発明で達成し得る圧縮効率の回復を示した信号タイミングのブロック図である。
【図１】
2006515121.tif 000004
【図２】
2006515121.tif 000005
【図３】
2006515121.tif 000006
【図４】
2006515121.tif 000007
【図５】
2006515121.tif 000008
【図６】
2006515121.tif 000009
【図７】
2006515121.tif 000010
【図８】
2006515121.tif 000011
【図９】
2006515121.tif 000012
【図１０】
2006515121.tif 000013
【図１１】
2006515121.tif 000014
【図１２】
2006515121.tif 000015
【図１３】
2006515121.tif 000016
【手続補正書】
【提出日】平成16年9月15日(2004.9.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力バッファ（１４０）に保持されたバイトをヒストリ・バッファ（１１０、１２０）に保持されたバイトと比較する、データ文字列のＬＺ１圧縮用の比較マトリックス（１７０）で使用される回路（６４０）であって、
直列に結合された複数の論理ゲート段（７２０、７３０、７４０、７５０）を含み、前記複数の論理ゲート段の各々は、ゲートから成る三角形を含み、
前記複数の論理ゲート段の各々は、前記比較マトリックスの出力に受け渡すための、または前記複数の論理ゲート段のうちの別の段に受け渡すためのキャリ値を生成するように配置される回路。
【請求項２】
前記複数の論理ゲート段に含まれる論理ゲート段の数と前記複数の論理ゲート段の各々に含まれる論理ゲートの数の積が、論理ゲート段を１つだけ有する等価な回路で必要とされる論理ゲートの数よりも少ない、請求項１に記載の回路。
【請求項３】
別のキャリ値生成回路からキャリ値を受信するため、前記回路の入力に結合された入力ラッチ（７１０）をさらに含む、請求項１または２に記載の回路。
【請求項４】
所定の数の前記複数の論理ゲート段に結合された、ルック・アヘッド・キャリ値を生成する手段（７７０）をさらに含む、請求項１、２または３のいずれかに記載の回路。
【請求項５】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段からキャリ値を受信するように結合された中間ラッチ（７６０）をさらに含む、請求項４に記載の回路。
【請求項６】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）が、論理ゲート（８００）を介して比較器の出力に結合され、前記比較マトリックスの他の列の比較ユニットに結合されるように配置された論理手段（８１０）を含む、請求項４または５のいずれかに記載の回路。
【請求項７】
前記回路の出力で生成されるキャリ値をそれより前に生成されたキャリ・ルック・アヘッド値と比較して、前記キャリ値を改善できるかどうか決定する手段を含む、請求項４、５または６のいずれかに記載の回路。
【請求項８】
データ文字列のＬＺ１圧縮用の機構（１００）であって、
前記データ文字列の第１のバイト列を保持するための入力バッファ（１４０）と、
前記データ文字列の第２のバイト列を保持するためのヒストリ・バッファ（１１０、１２０）と、
前記入力バッファおよび前記ヒストリ・バッファに結合され、前記入力バッファに保持されたバイトと前記ヒストリ・バッファに保持されたバイトを比較するための比較ユニット（４００）を並べた複数の行および列を有する比較マトリックス（１７０）であって、前記ヒストリ・バッファの各バイトが、前記比較マトリックス内の斜めにずれた位置の比較ユニットに結合される、比較マトリックスと、
前記行の各々で、同じ列の先行する比較ユニットからその行の比較ユニットにかけて生じた連続するバイト・マッチの最大数を発生させた列を検出する検出手段（１５０）と、
前記検出手段によって検出されたマッチ・バイト列をトークンとして符号化する手段（１６０）と、
請求項１ないし６のいずれか一項に記載の回路（６４０）を含む比較ユニットとを含む機構。
【請求項９】
入力バッファ（１４０）に保持されたバイトをヒストリ・バッファ（１１０、１２０）に保持されたバイトと比較する、データ文字列のＬＺ１圧縮用の比較マトリックス（１７０）で使用される方法であって、
直列に結合された複数の論理ゲート段（７２０、７３０、７４０、７５０）を提供するステップを含み、前記複数の論理ゲート段の各々は、ゲートから成る三角形を含み、
前記複数の論理ゲート段の各々は、前記比較マトリックスの出力に受け渡すための、または前記複数の論理ゲート段のうちの別の段に受け渡すためのキャリ値を生成するように配置される方法。
【請求項１０】
前記複数の論理ゲート段に含まれる論理ゲート段の数と前記複数の論理ゲート段の各々に含まれる論理ゲートの数の積が、論理ゲート段を１つだけ有する等価な回路で必要とされる論理ゲートの数よりも少ない、請求項９に記載の方法。
【請求項１１】
前記ユニットの入力に結合された入力ラッチ（７１０）を提供するステップと、別のキャリ値生成ユニットからキャリ値を受信するステップをさらに含む、請求項９または１０に記載の方法。
【請求項１２】
所定の数の前記複数の論理ゲート段に結合された、ルック・アヘッド・キャリ値を生成する手段（７７０）を提供するステップをさらに含む、請求項１０または１１のいずれかに記載の方法。
【請求項１３】
ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段に結合された中間ラッチ（７６０）を提供するステップと、ルック・アヘッド・キャリ値を生成する前記手段（７７０）に結合された論理ゲート段からキャリ値を受信するステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
ルック・アヘッド・キャリ値を生成する前記ステップ（７７０）が、所定の数の前記複数の論理ゲート段の比較器の出力に結合され、かつ前記比較マトリックスの他の列の比較ユニットに結合された論理手段（８１０）を提供するステップを含む、請求項１２または１３のいずれかに記載の方法。
【請求項１５】
前記ユニットの出力で生成されるキャリ値をそれより前に生成されたキャリ・ルック・アヘッド値と比較して、前記キャリ値を改善できるかどうか決定するステップを含む、請求項１２、１３または１４のいずれかに記載の方法。
【請求項１６】
データ文字列のＬＺ１圧縮用の方法（３００）であって、
前記データ文字列の第１のバイト列を入力バッファ（１４０）に保持するステップと、
前記データ文字列の第２のバイト列をヒストリ・バッファ（１１０、１２０）に保持するステップと、
前記入力バッファおよび前記ヒストリ・バッファに結合される、比較ユニット（４００）を並べた複数の行および列を有する比較マトリックスで、前記入力バッファに保持されたバイトと前記ヒストリ・バッファに保持されたバイトを比較するステップ（１７０）であって、前記ヒストリ・バッファの各バイトが、前記比較マトリックス内の斜めにずれた位置の比較ユニットに結合されるステップと、
前記行の各々で、同じ列の先行する比較ユニットからその行の比較ユニットにかけて生じた連続するバイト・マッチの最大数を発生させた列を検出するステップ（１５０）と、
前記検出ステップ（１５０）で検出されたマッチ・バイト列をトークンとして符号化するステップ（１６０）とを含み、
前記比較ステップ（１７０）が、請求項９ないし１５のいずれか一項に記載の方法を実行するステップを含む方法。
【請求項１７】
請求項１ないし７のいずれか一項に記載の回路、または請求項８に記載の機構を含む集積回路。
【請求項１８】
前記集積回路が、特定用途向け集積回路（ＡＳＩＣ）である、請求項１７に記載の集積回路。
【国際調査報告】
2006515121.tif 000017
2006515121.tif 000018
2006515121.tif 000019