JP3327869B2 - 最小マッチ長が3のプリマッチストリングマッチアレイ - Google Patents
最小マッチ長が3のプリマッチストリングマッチアレイInfo
- Publication number
- JP3327869B2 JP3327869B2 JP20682399A JP20682399A JP3327869B2 JP 3327869 B2 JP3327869 B2 JP 3327869B2 JP 20682399 A JP20682399 A JP 20682399A JP 20682399 A JP20682399 A JP 20682399A JP 3327869 B2 JP3327869 B2 JP 3327869B2
- Authority
- JP
- Japan
- Prior art keywords
- match
- byte
- output
- string
- signal
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Description
【0001】
【発明の属する技術分野】最小マッチ長が3である、G
ZIPとして産業界において知られているタイプのスト
リングマッチングを使用してデータを圧縮するための回
路であって、その回路は、セル当たり一つの比較器しか
有していない。
ZIPとして産業界において知られているタイプのスト
リングマッチングを使用してデータを圧縮するための回
路であって、その回路は、セル当たり一つの比較器しか
有していない。
【0002】
【従来の技術】圧縮の一般的な形態は、各々の現在の入
力バイトを前に受信されたバイトのストリングと比較
し、一つまたはそれ以上のマッチがあったときに信号を
出力する。前のバイトを保持するレジスタが十分に大き
いとき、たとえば、4Kであるときには、マッチの数が
判る。次いで、このプロセスは次のバイトに進み、最初
のマッチを示すいずれかのセルが次のバイトともマッチ
するかどうかを調べる。多分、幾つかのものがマッチを
示す。このプロセスは、最も大きなストリングのマッチ
するバイトが組み立てられるまで続く。次いで、このス
トリングは、ストリング内のバイトの数と、変位、すな
わち、現在のストリングの最初のバイトとレジスタ内の
最長のマッチするストリングの最初のバイトの間にある
バイトの数として記述される。殆どの場合において、ス
トリング内のバイトの数と変位は、元のデータより少な
いビットで記述することができ、圧縮される結果とな
る。
力バイトを前に受信されたバイトのストリングと比較
し、一つまたはそれ以上のマッチがあったときに信号を
出力する。前のバイトを保持するレジスタが十分に大き
いとき、たとえば、4Kであるときには、マッチの数が
判る。次いで、このプロセスは次のバイトに進み、最初
のマッチを示すいずれかのセルが次のバイトともマッチ
するかどうかを調べる。多分、幾つかのものがマッチを
示す。このプロセスは、最も大きなストリングのマッチ
するバイトが組み立てられるまで続く。次いで、このス
トリングは、ストリング内のバイトの数と、変位、すな
わち、現在のストリングの最初のバイトとレジスタ内の
最長のマッチするストリングの最初のバイトの間にある
バイトの数として記述される。殆どの場合において、ス
トリング内のバイトの数と変位は、元のデータより少な
いビットで記述することができ、圧縮される結果とな
る。
【0003】このバイトはどのようなサイズでもよく、
また、どのような種類のデータを表すものであってもよ
い。この説明の残りの部分では、バイト当たり8ビット
であり、バイトはビデオの画素であると仮定している
が、バイト当たりのビットは任意の他の数でよく、ま
た、キャラクタコード化されたデータのような任意の他
の種類のデータを表すものであってもよい。
また、どのような種類のデータを表すものであってもよ
い。この説明の残りの部分では、バイト当たり8ビット
であり、バイトはビデオの画素であると仮定している
が、バイト当たりのビットは任意の他の数でよく、ま
た、キャラクタコード化されたデータのような任意の他
の種類のデータを表すものであってもよい。
【0004】ここに参考として組み入れられた先の共通
に譲渡された米国特許出願第08/937,554号に
おいては、そのような方法およびこの方法を実行するた
めの回路が説明されている。この場合では、最小マッチ
長は2であった。すなわち、列の中の二つのみの画素が
レジスタ内の前の画素とマッチした場合に圧縮が適用さ
れることになる。各ステージの比較器回路は、画素を比
較して、一つまたはそれ以上のマッチがあった場合には
最初のマッチを登録することになる。次いで2番目のバ
イトが比較されることになる。同じセルの中でマッチが
なかった場合には、最初のバイトが圧縮なしで送り出さ
れることになる。2番目のマッチがあった場合には、最
初の信号は圧縮されるべきストリングの最初のバイトと
して使用されることになる。
に譲渡された米国特許出願第08/937,554号に
おいては、そのような方法およびこの方法を実行するた
めの回路が説明されている。この場合では、最小マッチ
長は2であった。すなわち、列の中の二つのみの画素が
レジスタ内の前の画素とマッチした場合に圧縮が適用さ
れることになる。各ステージの比較器回路は、画素を比
較して、一つまたはそれ以上のマッチがあった場合には
最初のマッチを登録することになる。次いで2番目のバ
イトが比較されることになる。同じセルの中でマッチが
なかった場合には、最初のバイトが圧縮なしで送り出さ
れることになる。2番目のマッチがあった場合には、最
初の信号は圧縮されるべきストリングの最初のバイトと
して使用されることになる。
【0005】
【発明が解決しようとする課題】3の最小ストリング長
で動作するように回路が修正されるときに複雑化した問
題が生じる。最初のマッチが見つかったときに、全ての
非マッチセルがオフにされる。2番目のマッチがあった
場合には、画素は送り出されないままであり、3番目の
マッチがない場合には、最小マッチ長は達成されていな
い。ここでプロセスは、2番目のバイトに戻ってそれを
最初のバイトとして処理しなければならない。なぜなら
ば、2番目のバイトは、オフされたセル内の新しいスト
リングの最初のバイトであるかもしれないからである。
無論、バイトのストリングを戻すことは、性能を大幅に
劣化させる。
で動作するように回路が修正されるときに複雑化した問
題が生じる。最初のマッチが見つかったときに、全ての
非マッチセルがオフにされる。2番目のマッチがあった
場合には、画素は送り出されないままであり、3番目の
マッチがない場合には、最小マッチ長は達成されていな
い。ここでプロセスは、2番目のバイトに戻ってそれを
最初のバイトとして処理しなければならない。なぜなら
ば、2番目のバイトは、オフされたセル内の新しいスト
リングの最初のバイトであるかもしれないからである。
無論、バイトのストリングを戻すことは、性能を大幅に
劣化させる。
【0006】他の可能性がある実施形態は、現在のバイ
トをパイプライン化して、最初のバイトが見つかった後
に、マッチについて2番目と3番目のバイトの両方を検
査することである。これは、セル当たり二つの比較器を
必要とする。3の最小マッチ長についての一層効率的な
回路が必要である。
トをパイプライン化して、最初のバイトが見つかった後
に、マッチについて2番目と3番目のバイトの両方を検
査することである。これは、セル当たり二つの比較器を
必要とする。3の最小マッチ長についての一層効率的な
回路が必要である。
【0007】
【課題を解決するための手段】この回路は、前と現在の
バイト(AとB)がマッチした場合にのみ真である一つ
の信号と、現在(B)と次のバイト(C)が一致した場
合にのみ真である別の信号を発生させることにより、セ
ル当たり1個の比較器を使用する。三つ全てがマッチし
た場合には、回路は、ストリングの終わりまでマッチの
検査を続けてその結果を圧縮する。三つ全てがマッチし
ない場合には、プロセスは前のバイトAを生データとし
て送り出し、現在のBバイトにおいてプロセスを再開始
する。
バイト(AとB)がマッチした場合にのみ真である一つ
の信号と、現在(B)と次のバイト(C)が一致した場
合にのみ真である別の信号を発生させることにより、セ
ル当たり1個の比較器を使用する。三つ全てがマッチし
た場合には、回路は、ストリングの終わりまでマッチの
検査を続けてその結果を圧縮する。三つ全てがマッチし
ない場合には、プロセスは前のバイトAを生データとし
て送り出し、現在のBバイトにおいてプロセスを再開始
する。
【0008】二つのバイトがマッチした場合に真である
信号は、一つの比較器によって生成される。Bバイトに
ついての最初の比較は、1個の比較器によって生成さ
れ、フリップフロップの入力に印加される。次のクロッ
クサイクルで、ここではフリップフロップによって出力
されている、信号Bについての比較信号がC出力にAN
Dされ、ANDゲートの出力におけるハイ出力は、Bと
Cの両方の比較の結果マッチしたことを示す。同様に、
別のフリップフロップは、前のサイクルでA+Bのマッ
チがあったかどうかを示す1サイクル遅延した出力を有
する。
信号は、一つの比較器によって生成される。Bバイトに
ついての最初の比較は、1個の比較器によって生成さ
れ、フリップフロップの入力に印加される。次のクロッ
クサイクルで、ここではフリップフロップによって出力
されている、信号Bについての比較信号がC出力にAN
Dされ、ANDゲートの出力におけるハイ出力は、Bと
Cの両方の比較の結果マッチしたことを示す。同様に、
別のフリップフロップは、前のサイクルでA+Bのマッ
チがあったかどうかを示す1サイクル遅延した出力を有
する。
【0009】A+BとB+Cの両方の信号が真である場
合に、新しいストリングの最初のバイトとしてバイトA
を使用するために論理回路が設けられる。A+Bはマッ
チを示すが、B+Cはそうでない場合には、全てのセル
がリセットされ、Bは新しいストリングの可能性のある
最初のバイトとしてセーブされる。A+BとB+Cの両
方の信号が偽である場合には、全てのセルがリセットさ
れ、プロセスはバイトCで最初から開始される。結果
は、ストリングを開始するためには、同じセルにおける
列の中の三つのマッチが必要であり、セル当たり一つの
比較器しか必要でないと云うことである。
合に、新しいストリングの最初のバイトとしてバイトA
を使用するために論理回路が設けられる。A+Bはマッ
チを示すが、B+Cはそうでない場合には、全てのセル
がリセットされ、Bは新しいストリングの可能性のある
最初のバイトとしてセーブされる。A+BとB+Cの両
方の信号が偽である場合には、全てのセルがリセットさ
れ、プロセスはバイトCで最初から開始される。結果
は、ストリングを開始するためには、同じセルにおける
列の中の三つのマッチが必要であり、セル当たり一つの
比較器しか必要でないと云うことである。
【0010】
【発明の実施の形態】3の最小マッチ長で動作させるた
めに、セルが2のマッチ長の存在を判別しているとき
に、回路は、同じサイクルで、3のマッチ長が次のサイ
クルで発生するかどうかも判別出来なければならない。
図1のストリングマッチアレイは、そう行うように設計
される。
めに、セルが2のマッチ長の存在を判別しているとき
に、回路は、同じサイクルで、3のマッチ長が次のサイ
クルで発生するかどうかも判別出来なければならない。
図1のストリングマッチアレイは、そう行うように設計
される。
【0011】図1の順番に番号が付けられたレジスタ1
1を通って右に進むバイトストリング〔x,c’,
b’,a’,d,c,b,a〕を仮定する。a’=a,
b’=b,等と仮定する。最初のパスでは、aからdが
生ビデオとして送り出されるが、ストリングc’,
b’,a’はマッチする3バイトストリングになり、ス
トリングが3バイト長で、4バイト前に出力されたスト
リングにマッチすることを示す「3,4」に圧縮され
る。
1を通って右に進むバイトストリング〔x,c’,
b’,a’,d,c,b,a〕を仮定する。a’=a,
b’=b,等と仮定する。最初のパスでは、aからdが
生ビデオとして送り出されるが、ストリングc’,
b’,a’はマッチする3バイトストリングになり、ス
トリングが3バイト長で、4バイト前に出力されたスト
リングにマッチすることを示す「3,4」に圧縮され
る。
【0012】b’が現在のビットであり、c’がセル3
の比較器12を含む全ての比較器に印加される次のビッ
トであると仮定する。比較器12への他の入力は、バイ
トcを含み、それ故にバイトcを出力するセルレジスタ
11の内容である。二つは比較器12でマッチし、c=
c’であること示す出力Cがある。同様な理由で、前の
サイクルでb=b’であり、セル#4のクロック駆動さ
れるFF13の出力はBである。BとCの両方がAND
ゲート14に印加され、出力はB+Cであり、セル#3
における”現在のマッチ”がb’とc’バイトの両方で
見つかったことを示す。同様なプロセスによって、前の
サイクルでFF13の出力はA+Bであった。
の比較器12を含む全ての比較器に印加される次のビッ
トであると仮定する。比較器12への他の入力は、バイ
トcを含み、それ故にバイトcを出力するセルレジスタ
11の内容である。二つは比較器12でマッチし、c=
c’であること示す出力Cがある。同様な理由で、前の
サイクルでb=b’であり、セル#4のクロック駆動さ
れるFF13の出力はBである。BとCの両方がAND
ゲート14に印加され、出力はB+Cであり、セル#3
における”現在のマッチ”がb’とc’バイトの両方で
見つかったことを示す。同様なプロセスによって、前の
サイクルでFF13の出力はA+Bであった。
【0013】図2にも示されるセル#4の残りへの他の
信号入力は、初期化信号(Init)である。いずれか
のセルからエンコーダ15への変位信号(Disp1_
x)がハイになってマッチを示す限りは、Init信号
はローのままである。次いで、回路の残りは、これらの
二つの信号、Init信号およびANDゲート14の出
力を使用して、セルの出力である変位ラインを制御す
る。五つの可能性がある結果がある。
信号入力は、初期化信号(Init)である。いずれか
のセルからエンコーダ15への変位信号(Disp1_
x)がハイになってマッチを示す限りは、Init信号
はローのままである。次いで、回路の残りは、これらの
二つの信号、Init信号およびANDゲート14の出
力を使用して、セルの出力である変位ラインを制御す
る。五つの可能性がある結果がある。
【0014】現在のマッチ(B+C)がない場合には、
両方のゲート20,21への一方の入力はローであり、
マルチプレクサへの1あるいは0の入力がロー出力を生
じさせ、クロックされた後に、FF22出力はローにな
り、マッチしなかったことを示す。現在のマッチがない
場合には、他の信号とは無関係に変位出力は常にローに
なる。
両方のゲート20,21への一方の入力はローであり、
マルチプレクサへの1あるいは0の入力がロー出力を生
じさせ、クロックされた後に、FF22出力はローにな
り、マッチしなかったことを示す。現在のマッチがない
場合には、他の信号とは無関係に変位出力は常にローに
なる。
【0015】現在のマッチがあり、また、前のセル出力
(前のクロック期間の間の出力)がハイであった場合に
は、少なくとも一つのセルはハイ出力を有していたので
Init信号は0になり、mux16の0入力が選択さ
れ、ハイ状態がmuxを通してFF22に印加され、次
のクロックで出力変位信号はハイになる。これは、既に
セル内で開始されたマッチしたストリングの継続とな
る。
(前のクロック期間の間の出力)がハイであった場合に
は、少なくとも一つのセルはハイ出力を有していたので
Init信号は0になり、mux16の0入力が選択さ
れ、ハイ状態がmuxを通してFF22に印加され、次
のクロックで出力変位信号はハイになる。これは、既に
セル内で開始されたマッチしたストリングの継続とな
る。
【0016】前のマッチおよび現在のマッチがなく、前
のセル出力がローであった場合には、いずれかのゲート
がローを出力し、次のセル出力はローになる。これは、
少なくとも一つの他のセルがストリングを開始し、この
セルが無効にされた状況である。
のセル出力がローであった場合には、いずれかのゲート
がローを出力し、次のセル出力はローになる。これは、
少なくとも一つの他のセルがストリングを開始し、この
セルが無効にされた状況である。
【0017】前のセル出力はないが、現在のマッチと前
のマッチがあり、Initラインが1でどのセルにもマ
ッチがないことを示す場合には、ゲート21が選択さ
れ、出力はハイである。これは、このセルが新しいスト
リングを開始している場合になる。
のマッチがあり、Initラインが1でどのセルにもマ
ッチがないことを示す場合には、ゲート21が選択さ
れ、出力はハイである。これは、このセルが新しいスト
リングを開始している場合になる。
【0018】最後に、前および現在のマッチがあり、前
のセル出力はローであり、少なくとも一つの他のセル出
力があった場合には、Initは0になり、ゲート20
が選択され、出力がローになってこのセルが無効にされ
たことを示す。
のセル出力はローであり、少なくとも一つの他のセル出
力があった場合には、Initは0になり、ゲート20
が選択され、出力がローになってこのセルが無効にされ
たことを示す。
【図1】 全体のアレイの回路である。
【図2】 一つの論理セクションの回路である。
11 レジスタ 12 比較器 13 FF 14 ANDゲート 15 エンコーダ 16 mux 20,21 ゲート 22,23 FF
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平7−95093(JP,A) 特開 平7−297728(JP,A) 特開 平8−51371(JP,A) 特開 平8−79092(JP,A) 特開 平8−234959(JP,A) 特開 平8−242178(JP,A) 特開 平8−274649(JP,A) 特開 平11−145848(JP,A) (58)調査した分野(Int.Cl.7,DB名) H03M 7/30 H03M 7/40
Claims (1)
- 【請求項1】 アレイが、いずれのセルも変位信号を生
成しない場合には初期化信号を生成して全てのセルに印
加するエンコーダを含んでおり、各セルが、前、現在、
および次のバイトの入力バイトストリングの一つのバイ
トを記憶するためのレジスタを含んでいる、セルのスト
リングマッチアレイにおいて、変位信号を生成するため
の各セルにおける回路が、 次のバイトとレジスタの内容が等しいかどうかを判別し
て出力を生成するための比較器と、 前の比較器出力を遅延させるための手段と、 比較器出力と遅延された比較器出力に応答して、現在の
バイトと遅延された前のバイトの両方がマッチした場合
には現在のマッチ信号を生成するための手段と、 現在のマッチ信号を遅延させて前のマッチ信号を作り出
すための手段とを含んでおり、 初期化信号が存在するときに、変位信号として前のマッ
チと現在のマッチを出力し、 初期化信号が存在しないときに、現在のマッチと前の変
位信号を出力するストリングマッチアレイ。
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US12377698A | 1998-07-28 | 1998-07-28 | |
US123776 | 1998-07-28 |
Publications (2)
Publication Number | Publication Date |
---|---|
JP2000059226A JP2000059226A (ja) | 2000-02-25 |
JP3327869B2 true JP3327869B2 (ja) | 2002-09-24 |
Family
ID=22410821
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP20682399A Expired - Fee Related JP3327869B2 (ja) | 1998-07-28 | 1999-07-21 | 最小マッチ長が3のプリマッチストリングマッチアレイ |
Country Status (3)
Country | Link |
---|---|
EP (1) | EP0977152A3 (ja) |
JP (1) | JP3327869B2 (ja) |
BR (1) | BR9902900A (ja) |
Families Citing this family (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US8400335B2 (en) | 2011-07-21 | 2013-03-19 | International Business Machines Corporation | Using variable length code tables to compress an input data stream to a compressed output data stream |
US8669889B2 (en) | 2011-07-21 | 2014-03-11 | International Business Machines Corporation | Using variable length code tables to compress an input data stream to a compressed output data stream |
US8692696B2 (en) | 2012-01-03 | 2014-04-08 | International Business Machines Corporation | Generating a code alphabet of symbols to generate codewords for words used with a program |
KR102072412B1 (ko) * | 2013-01-07 | 2020-02-04 | 삼성전자주식회사 | 데이터 압축 회로의 동작 방법과 상기 방법을 수행할 수 있는 장치들 |
Family Cites Families (10)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5003307A (en) * | 1989-01-13 | 1991-03-26 | Stac, Inc. | Data compression apparatus with shift register search means |
US5384567A (en) * | 1993-07-08 | 1995-01-24 | International Business Machines Corporation | Combination parallel/serial execution of sequential algorithm for data compression/decompression |
JPH07114577A (ja) * | 1993-07-16 | 1995-05-02 | Internatl Business Mach Corp <Ibm> | データ検索装置、データ圧縮装置及び方法 |
US5525982A (en) * | 1994-04-15 | 1996-06-11 | International Business Machines Corporation | Method and means for character string pattern matching for compression and the like using minimal cycles per character |
JP3210183B2 (ja) * | 1994-08-08 | 2001-09-17 | 富士通株式会社 | データ圧縮方法及び装置 |
US5572209A (en) * | 1994-08-16 | 1996-11-05 | International Business Machines Corporation | Method and apparatus for compressing and decompressing data |
US5612693A (en) * | 1994-12-14 | 1997-03-18 | International Business Machines Corporation | Sliding window data compression using a toroidal bit shift register |
US5771010A (en) * | 1995-03-22 | 1998-06-23 | Ibm Corporation | Apparatus for compressing data using a Lempel-Ziv-type algorithm |
JPH08242178A (ja) * | 1995-11-02 | 1996-09-17 | Mitsubishi Electric Corp | 誤り訂正方法 |
US5874907A (en) * | 1997-09-19 | 1999-02-23 | International Business Machines Corporation | Method and apparatus for providing improved data compression efficiency for an adaptive data compressor |
-
1999
- 1999-07-21 EP EP99305784A patent/EP0977152A3/en not_active Withdrawn
- 1999-07-21 JP JP20682399A patent/JP3327869B2/ja not_active Expired - Fee Related
- 1999-07-27 BR BR9902900-6A patent/BR9902900A/pt not_active Application Discontinuation
Also Published As
Publication number | Publication date |
---|---|
BR9902900A (pt) | 2000-01-04 |
EP0977152A3 (en) | 2000-12-27 |
JP2000059226A (ja) | 2000-02-25 |
EP0977152A2 (en) | 2000-02-02 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US5771010A (en) | Apparatus for compressing data using a Lempel-Ziv-type algorithm | |
EP0803091B1 (en) | Computer system | |
US5572209A (en) | Method and apparatus for compressing and decompressing data | |
EP0568305A2 (en) | Data compression | |
US5778255A (en) | Method and system in a data processing system for decompressing multiple compressed bytes in a single machine cycle | |
US5805086A (en) | Method and system for compressing data that facilitates high-speed data decompression | |
US6348881B1 (en) | Efficient hardware implementation of a compression algorithm | |
US20020026466A1 (en) | Arithmetic unit and data processing unit | |
JP3327869B2 (ja) | 最小マッチ長が3のプリマッチストリングマッチアレイ | |
US5463760A (en) | Break function in-circuit emulator for a microprocessor with a cache memory | |
US20090037800A1 (en) | Data parallelizing receiver | |
US7668381B2 (en) | Decoding apparatus and encoding apparatus with specific bit sequence deletion and insertion | |
US6674373B1 (en) | System and method for data decompression | |
US6429794B1 (en) | Format converter | |
US7539258B2 (en) | Audio data sync format detecting circuit | |
US7426187B2 (en) | False sync code protection (FSP) decoding by software | |
JPH05189360A (ja) | データ転送および記憶方式 | |
KR100268125B1 (ko) | 병렬 순환 여유도 검사(crc) 회로 | |
JPH10154065A (ja) | バス制御装置 | |
JPH1098458A (ja) | シンクワード検出回路 | |
KR0184780B1 (ko) | 메모리 인터페이스방법 및 장치 | |
JPH11242651A (ja) | インターフェース | |
JP3293382B2 (ja) | データ圧縮装置及びデータ伸長装置 | |
JP2005202628A (ja) | メモリ制御装置、メモリ制御方法およびメモリ制御プログラム | |
JP2010233235A (ja) | エンコード装置 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20020531 |
|
LAPS | Cancellation because of no payment of annual fees |