JPH114170A

JPH114170A - ２進データのダブル・ランレングス符号化の方法および装置

Info

Publication number: JPH114170A
Application number: JP9010086A
Authority: JP
Inventors: Ken Schmidt; ケン・シュミット; Jeff Horowitz; ジェフ・ホロウィッツ
Original assignee: Peerless Systems Corp
Current assignee: Peerless Systems Corp
Priority date: 1996-01-02
Filing date: 1997-01-06
Publication date: 1999-01-06
Anticipated expiration: 2017-01-06
Also published as: EP0783208B1; DE69624670D1; EP0783208A2; EP0783208A3; JP4094081B2; DE69624670T2; US5710561A

Abstract

(57)【要約】【課題】ダブル・ランレングス符号化（ＤＲＬＥ）と
呼ぶ技法を使用して２進データを無損失圧縮する方法お
よび装置。【解決手段】ＤＲＬＥは、レーザ・プリンタまたはそ
の他の連続ラスタ走査装置による印刷のために処理する
際のグレースケール・データの圧縮に特に適用される。
ＤＲＬＥによって、計算の複雑さがほとんどなしに１と
０の反復パターンを記録する。従来のランレングス符号
化（ＲＬＥ）ではうまく圧縮することができないデータ
についてしばしば１桁以上高い圧縮比が得られる。ＤＲ
ＬＥは、ゼロと１の可変長パターンを示す順序対の順次
履歴を使用し、それらのパターンが繰り返されるに従っ
てそれらのパターンを符号化する。

Description

【発明の詳細な説明】

【０００１】

【発明が属する技術分野】本発明は、レーザ・プリンタ
またはその他の連続ラスタ走査装置による印刷のために
処理する際にグレースケール・データの圧縮に特に適用
される本明細書でダブル・ランレングス符号化（ＤＲＬ
Ｅ）と呼ぶ２進データの無損失圧縮の方法に関する。

【０００２】

【従来の技術】従来知られている圧縮技術にランレング
ス符号化（ＲＬＥ）がある。これはランを＜パターン、
反復回数＞の形式の順序対として表す無損失圧縮方法で
あり、反復回数によってパターンの連続するオカレンス
数が決まる。ランを適切な回数だけ繰り返されるパター
ンに伸長すると元の２進形式が再生されるため、ＲＬＥ
が実際に無損失変換であり、適合する大きさの反復パタ
ーンをきわめてよく圧縮する変換であることは容易に判
断される。ここに、ランとは０又は１の連続した繰り返
し生起するパターンである。

【０００３】反復数の値は、それを表すために使用され
るビット数によって制限される。Ｗビットを使用して反
復数を表した場合、１つのＲＬＥ順序対の長さはＬ（＜パターン、反復数＞）＝（Ｌ（パターン）＋Ｗ）となる。（反復数＊Ｌ（パターン））＞＞（Ｌ（パターン）＋
Ｗ）または１＞＞（（１／反復数）＋（Ｗ／（反復数＊Ｌ（パター
ン））））の場合、明らかにＲＬＥは有効な無損失圧縮方式であ
る。したがって、ＲＬＥは反復回数の多いパターンを持
つデータには最適である。

【０００４】

【発明が解決しようとする課題】本発明は、これを改良
して更に効率のよい無損失圧縮技法を提供しようとする
ものである。

【０００５】

【課題を解決するための手段】レーザ・プリンタまたは
その他の連続ラスタ走査装置による印刷のために処理す
る際にグレースケール・データの圧縮に特に適用され
る、本明細書でダブル・ランレングス符号化（ＤＲＬ
Ｅ）と呼ぶ２進データの無損失圧縮の方法を開示する。
ＤＲＬＥ方法は、計算の複雑さがほとんどなしに１と０
の反復パターンを効率的に記録する。従来のランレング
ス符号化（ＲＬＥ）ではうまく圧縮することができない
データについて１桁以上高い圧縮比が得られる場合が多
い。ＤＲＬＥは０と１の可変長パターンを示す順序対の
順次履歴を使用し、次にそれらのパターンを、反復され
るに従って効率的かつ適応的に符号化する。

【０００６】ＤＲＬＥは、ディジタル・プリンタで印刷
するページの２進イメージに特有のグレースケール・デ
ータの場合に高い圧縮比を実現する。ＤＲＬＥによっ
て、従来のランレングス符号化（ＲＬＥ）では通常はう
まく圧縮されない多くのページを、計算効率のよい方法
で表すことができると同時に、それらのページを保持す
るのに必要な記憶量を大幅に低減することができる。こ
の計算効率はリアルタイム制約のあるソフトウェアとハ
ードウェアの両方の実施にきわめて有用であると同時
に、高圧縮比は一般に、今日の低コスト高解像度モノク
ロームおよびカラーのインクジェットおよびレーザ・プ
リンタにとって理想的である。

【０００７】ＤＲＬＥの理論的基礎とグレースケールへ
のその応用に関する説明とを示す。グレースケール画像
処理は一般に、１カラー・プレーン当たり１ビット／画
素のディジタル・モノクロームまたはプレーナ・カラー
・プリンタに適用される。

【０００８】

【発明の実施の形態】本発明によるダブル・ランレング
ス符号化（ＤＲＬＥ）には以下の３つの基本要素があ
る。１．ダブル・ラン。要素が、圧縮するデータ内の０のランと１のランとの連
結を表す順序対。２．リテラルおよびリピータの符号化。ＤＲＬＥの出力形式は、ダブル・ランを表すリテラル
と、ダブル・ランの循環インスタンスのリピータを含
む。３．パターン・マッチング。ダブル・ランの循環可変長パターンを検出する適応型の
方法。

【０００９】上記の各要素について以下に詳述する。最
初の２つの要素は、圧縮データを表すために使用するデ
ータ構造体であり、ＤＲＬＥの主要構成要素である。圧
縮程度は、パターン・マッチング・アルゴリズムによっ
て異なる。グレースケール・データの場合、ＤＲＬＥは
最新（ＭＲ）ダブル・ラン方式を採用する。その他の方
式としては最新パターン変化（ＭＲＰＣ）と事前定義固
定パターン（ＰＦＰ）があり、パターン内に埋め込まれ
たパターンを含むデータ、またはＤＲＬＥを適用する前
に特定のパターンが存在することがわかっているデータ
にそれぞれ適用可能である。これらのパターン・マッチ
ング方式のそれぞれについては以下で説明する。

【００１０】以下では、無損失圧縮およびＤＲＬＥの形
式モデルについて説明し、次にＤＲＬＥの例を示す。そ
れによって、ＤＲＬＥがアルゴリズム的にどのように機
能するかを例示し、特定の条件で圧縮比が数学的にどの
ように変化するかを例示する。その後でグレースケール
・データへのＤＲＬＥの応用について説明する。

【００１１】理論モデル任意の２進データは、ゼロと１のランダムな順序とみな
すことができる（図１の最上部を参照）。この説明で
は、ＲＬＥとＤＲＬＥを使用した無損失圧縮の形式を説
明することが可能な表記と用語を採用する。

【００１２】２進データの最小要素はビット（すなわち
ゼロまたは１）である。合計ビット数をデータの長さと
呼ぶ。２進データの無損失圧縮とは、変換が可逆的（す
なわち無損失）であるように当該データに適用される変
換であり、より長さの短いデータを生成する（すなわち
圧縮する）。

【００１３】無損失圧縮Ｔ（ｘ）＝ｙは２進データｘの変換Ｔを行って２進データｙを生成す
ることを表すものとする。

【００１４】変換Ｔ（ｘ）は、すべてのｘについてＴ^-1（Ｔ（ｘ））＝ｘになるＴ^-1（ｙ）が存在する場合のみ無損失である。Ｔ
^-1（ｙ）をＴ（ｘ）の逆変換と呼ぶ。無損失圧縮の用語
では、Ｔ^-1（ｙ）を圧縮解除または伸長変換と呼ぶ。２
進データｘの長さはｘを構成するビットの数（またはカ
ウント）である。Ｌ（ｘ）はｘの長さを示すものとする。ｘの無損失変換Ｔ（ｘ）
は、Ｌ（Ｔ（ｘ））＜Ｌ（ｘ）の場合にのみ圧縮される。Ｔ（ｘ）の圧縮比Ｒ（Ｔ
（ｘ））は、Ｒ（Ｔ（ｘ））＝Ｌ（ｘ）／Ｌ（Ｔ（ｘ））のように定義される。Ｔ（ｘ）の基本目標は、Ｒ（Ｔ（ｘ））＞＞１となる場
合である。

【００１５】ランレングス符号化ランとは介在データなしに繰り返し生起するパターンで
ある。たとえば、「５個のゼロのラン」とは５個の連続
したゼロのことを言う。

【００１６】ランレングス符号化（ＲＬＥ）は、ランを
＜パターン、反復回数＞の形式の順序対として表す公知
の無損失圧縮方法であり、反復回数によってパターンの
連続するオカレンス数が決まる。ランを適切な回数だけ
繰り返されるパターンに伸長すると元の２進形式が再生
されるため、ＲＬＥが実際に無損失変換であり、適合す
る大きさの反復パターンをきわめてよく圧縮する変換で
あることは容易に判断される。

【００１７】反復数の値は、それを表すために使用され
るビット数によって制限される。Ｗビットを使用して反
復数を表した場合、１つのＲＬＥ順序対の長さはＬ（＜パターン、反復数＞）＝（Ｌ（パターン）＋Ｗ）となる。（反復数＊Ｌ（パターン））＞＞（Ｌ（パターン）＋
Ｗ）または１＞＞（（１／反復数）＋（Ｗ／（反復数＊Ｌ（パター
ン））））の場合、明らかにＲＬＥは有効な無損失圧縮方式であ
る。したがって、ＲＬＥは反復回数の多いパターンを持
つデータには最適である。

【００１８】図１の中央に、図１の最上部にある２進デ
ータのＲＬＥの例を示す。この例では、パターンの長さ
は１ビットであり、それによってゼロまたは１の２つの
可能なパターンを示す。図１のランレングス符号化例の
各順序対は、パターンの後にパターンの連続インスタン
ス数が付いたものを示している。図１に示す７６ビット
の２進データの特定のビット・パターンの場合、各順序
対に４ビット（パターン０または１に１ビットと、０〜
７の連続インスタンス数に３ビット）を要し、合計８０
ビットに２０個の順序対を要するため、ＲＬＥ圧縮では
利点がない。また、符号化形式で現れたときパターンが
少なくとも１回生起するため、ＲＬＥのソフトウェアま
たはハードウェア実施態様は、反復カウントに使用され
るビット数にもう１回の反復を計算に入れることができ
るように、オカレンス数ではなく隣接反復数を記録する
ことができることに留意されたい。この例では１ビット
幅のパターンのみを符号化するが、ＲＬＥの応用例では
一般にバイトまたはバイトのシーケンスなどより大きな
パターンが可能であり、可変長パターンさえも可能な場
合があるが、これは計算上かなり難しく、より多くのコ
ストがかかる。ＤＲＬＥは基本的に可変長パターンを扱
い、それを計算効率のよい方法で行うことに留意された
い。

【００１９】ダブル・ランレングス符号化ダブル・ランレングス符号化（ＤＲＬＥ）は、グレース
ケール・データについて高い圧縮比を実現する無損失圧
縮変換である。グレースケール・データは、１とゼロの
反復パターンの反復によってグレーの様々な陰影が表さ
れる２進データである。１が多くゼロがあまり多くない
パターンは一般に濃いグレーを表し、１が少なくゼロが
多いパターンは一般に明るいグレーを表す。

【００２０】ＤＲＬＥのソフトウェアまたはハードウェ
ア実施態様は、グレースケール・パターンを検出し、そ
れらのパターンを圧縮形式で固有かつ効率的に符号化す
る。これは、ダブル・ランと呼ぶ、ゼロと１（グレース
ケールではそれぞれ白と黒の画素）の隣接ランを示す順
序対の一時的履歴を記録し、それらのダブル・ランをリ
テラルとして符号化し、次にそれらのダブル・ランの隣
接オカレンスをリピータとして符号化することによって
行う。最もコンパクトな符号化を実現するように、リピ
ータは最小のビット数を使用する。圧縮形式の長さは元
の２進データよりも大幅に短くなる場合が多い。

【００２１】ダブル・ラン、リテラル、およびリピータ
の概念に加えて、ＤＲＬＥは、小さなランを効率的に符
号化することができるようにし、いくつかのパターンを
同時に符号化できるようにすることによって、ＲＬＥを
特有に拡張する。各ダブル・ランはゼロのランの後に１
のランが続いたものを表し、履歴はダブル・ランの一時
的シーケンスを表す。リピータによって、わずか２ビッ
トで履歴の最新のサブシーケンスを効率的に符号化する
ことができる。

【００２２】図１ないし図５の例で、ＤＲＬＥのために
以下の表記を使用したダブル・ランを示す。｛Ｌ₀，Ｌ₁｝上記で、Ｌ₀はダブル・ラン内のゼロの数であり、Ｌ₁は
ダブル・ラン内の１の数である。

【００２３】符号化形式ＤＲＬＥを使用して生成された２進データは、リテラル
とリピータの２つの基本データ項目を使用する。以下は
これらのデータ項目の物理形式の説明である。リテラル
またはリピータの先頭ビットは、データ項目のタイプを
決定するタグであり、リテラルの場合はゼロ、リピータ
の場合は１である。形式の残りの部分は、要素がリテラ
ルであるかリピータであるかによって決まる。

【００２４】リテラルの形式は、以下の形式の三つ組で
ある。｛０，Ｌ₀，Ｌ₁｝最初の要素はタグ・ビットであり、０の場合はそのデー
タ項目がリテラルであることを示す。２番目の要素であ
るＬ₀はパターン内の連続するゼロの数である。３番目
の要素はゼロの直後の連続する１の数である。たとえ
ば、「｛０，４，３｝」というリテラルは、「００００
１１１」というパターンを表す。

【００２５】リピータの形式は次の通りである。｛１，ｎ｝最初の要素はタグ・ビットであり、１の場合はデータ項
目がリピータであることを示す。２番目の要素であるｎ
はパターン内のダブル・ランの数を示す。

【００２６】リピータの２番目の要素は、ダブル・ラン
の一時履歴に関係する。ＤＲＬＥの一実施態様は、ダブ
ル・ランのシーケンスを順序付けされた先入れ先出しリ
ストの形で維持してパターン・マッチングに使用する。
このシーケンスを維持する方法は様々あり、このような
３通りの方法について以下に説明する。このリスト内の
ダブル・ランの実際の数は、後述するようにＤＲＬＥの
サイジング・パラメータであり、圧縮比に影響を与える
可能性がある。リピータの値ｎはこのリストへの相対オ
フセットである。パターンはその相対オフセットから始
まる現行リスト内のダブル・ランの最新のサブシーケン
スである。たとえば、最新ダブル・ランのリピータは
「｛１，０｝」であるのに対して、２つの最新ダブル・
ランのリピータは「｛１，１｝」である。一般には、ｎ
個の最新ダブル・ランのリピータは「｛１，ｎ−１｝」
である。

【００２７】サイジング・パラメータリテラルとリピータのサイジング（すなわち、そのそれ
ぞれが必要とするビット数）を制御するパラメータは以
下の２つである。Ｗ：ゼロのランまたは１のランの長さを表すために使用
するビット数。Ｎ：履歴内のダブル・ランの最大数。

【００２８】値Ｗは、リテラル内のゼロのランと１のラ
ンの長さがそれぞれゼロから２^W−１までの範囲である
ことが可能であることを意味する。Ｗによってランのサ
イズが決まるため、リテラルのサイズもＷによって制御
される。

【００２９】値Ｎは、リピータの２番目の要素（リテラ
ル・オフセット）に必要なビット数を決定する。言い換
えると、これによって履歴内で維持されるダブル・ラン
の数が決まる。これらのパラメータを使用すると、リテ
ラルおよびリピータの固定長はそれぞれ、Ｌ（リテラル）＝１＋（２＊Ｗ）およびＬ（リピータ）＝１＋最高限界（ｌｏｇ２（Ｎ））となり、上式で関数最高限界（ｒ）によって実数ｒ以上
の最小整数が得られる。

【００３０】これらのパラメータの効果を図２に示す。
この図は、図１に示す例の要素の一部を強調したもので
あり、以下で「例１」として詳述する。

【００３１】ＤＲＬＥ圧縮方法概念的には、ＤＲＬＥの実施態様は一般に２進データを
左から右に走査して、一度に１つのダブル・ランを引き
出す。記録機構を使用してダブル・ランの履歴を維持す
る。この履歴内の要素数は最大Ｎ個である。

【００３２】ダブル・ランの履歴を維持する機構は様々
ある。たとえば、次の３つの方法を使用することができ
る。１．最新（most recent, ＭＲ）２．最新パターン変化（most recent pattern change,
ＭＲＰＣ）３．事前定義固定パターン（predefined fixed patter
n, ＰＦＰ）

【００３３】ＭＲ機構は２進データ内で遭遇したサイズ
Ｎのダブル・ランの現行リストを維持する。新しいラン
を入手するとそれがリストの前または先頭に追加され
る。これは図２に示す手法であり、グレースケール・デ
ータに最も適した手法である。

【００３４】ＭＲＰＣ機構は、ＭＲ機構の変更版であ
り、パターン不一致が生起した場合のみ履歴を変更す
る。図３に、Ｎ＝２の場合のこの手法を示す。この手法
は、パターンがより大きなパターン内に埋め込まれてい
るデータに適している。

【００３５】ＰＦＰ機構は、サイズＮの事前定義ダブル
・ラン・パターンを使用し、このパターンのインスタン
スまたはそのサブパターンのインスタンスのみを探す。
履歴は変化しない。この例を図４に示す。この方式は、
当該データについて事前の知識がある場合に適切であ
る。一般には、ＰＦＰは、ＮおよびＷが良好な圧縮を実
現するのに十分な大きさの有限のシーケンスが、完全な
形または部分的な形で生起することがわかっているデー
タに適する。

【００３６】ＤＲＬＥの結果は、ダブル・ランの履歴を
維持するために使用した機構によって異なる場合がある
ため、この方法は圧縮解除方法への入力でもなければな
らない。したがって、理論的には変換ＤＲＬＥ（ｘ）お
よびＤＲＬＥ^-1（ｙ）があるが、アルゴリズム的にはこ
れらのそれぞれが追加パラメータを有する。

【００３７】履歴に加えて、ＤＲＬＥ実施態様は、リテ
ラルもリピータも出されていない最新ダブル・ランの先
読みバッファを維持する。最新履歴のサブシーケンスの
完全一致がある場合、リピータが出される。そうでない
場合は先読みバッファ内のダブル・ランのリテラルが最
初の不一致まで出される。いずれの場合も、作用を受け
たダブル・ランは先読みバッファから廃棄される。

【００３８】初期状態ダブル・ラン履歴の初期状態の適切な選定によって、圧
縮比を向上させることができる。ＰＦＰの場合は間違い
なく初期状態は事前定義固定パターンである。グレース
ケール・データの場合は、印刷するページは通常白い空
間から始まり、大部分白い空間から成るため、履歴内の
各リテラルについて「すべて白、黒なし」の初期状態が
推奨される。より形式的には、グレースケール・データ
の場合、履歴内の各ダブル・ランの初期値は以下の通り
でなければならない。｛２Ｗ^-1，０｝

【００３９】例最初の例では図２について説明する。図２および図３
に、ＤＲＬＥのいくつかの境界条件、すなわちゼロのみ
の２進データ（空白ページ）と、１つの反復パターンか
ら成る２進データを示す。

【００４０】例１図２に、ＭＲを使用したＷ＝５およびＮ＝２の場合のＤ
ＲＬＥを例示する。この場合、リテラルの長さは１１ビ
ットで、リピータの長さは２である。この例の結果は、
４個のリテラルと４個のリピータで合計５２ビットの長
さになり、圧縮比は７６／５２である。

【００４１】Ｗの効果を示すために、リテラルの長さ要
素の値を２進形式で示す。たとえば、「００１１１」お
よび「００１１０」がそれぞれ７および６に相当する５
ビットの２進数であるため、最初のダブル・ラン｛７，
６｝の結果はリテラル｛０，００１１１，００１１０｝
になる。

【００４２】左から右に進むと、｛４，３｝の最初のイ
ンスタンスの結果はリテラルになる。しかし、｛４，
３｝の２番目のインスタンスは２要素から成る履歴の先
頭と一致し、したがって、値｛１，０｝のリピータにな
る。

【００４３】続けて、｛４，３｝の３番目のインスタン
スの結果はリピータになり、｛２，５｝の最初のインス
タンスの結果はリテラルになる。

【００４４】この時点で、次の２つのダブル・ランであ
る｛４，３｝と｛２，５｝は一時履歴の最初の２つ（し
かもただ２つ）の要素と一致する。したがって、結果は
値｛１，１｝のリピータになる。これと同じパターンが
もう１回繰り返され、したがって再び値｛１，１｝のリ
ピータになる。

【００４５】最後は、ダブル・ラン｛５，２｝のリテラ
ルの結果になる。

【００４６】例２「すべて白、黒なし」のダブル・ラン（たとえば｛２^W
−１，０｝）が入っている履歴の初期状態を有する、ま
ったくゼロだけから成る長さＬ（Ｓ）の２進データＳを
考えてみる。このＳの形は完全レンダリングされた黒ペ
ージと似ている。

【００４７】この場合、連続した「すべて白、黒なし」
ダブル・ランの各Ｎ個のオカレンスは、｛１，Ｎ−１｝
の形のリピータに置き換えられる。

【００４８】Ｓ内の「すべて白、黒なし」ダブル・ラン
の数をＭとする。ＭはＮで割り切れない場合がある。言
い換えると、次のようになる場合がある。（ＭｍｏｄＮ）＞０上記で、「ＭｍｏｄＮ」は整数Ｎで割った場合の整
数Ｍの整数剰余を示す。Ｋ＝（ＭｍｏｄＮ）とす
る。ＤＲＬＥ（Ｓ）は｛１，Ｎ−１｝の形式のいくつか
の数のリピータ、すなわち（Ｍ−Ｋ）／Ｎから成る。Ｋがゼロでない場合、これらのリピータの後
には｛１，Ｋ−１｝の形のリピータが続く。さらに、Ｓ
は長さがＲ＝Ｌ（Ｓ）ｍｏｄ（２^W−１）のいくつかの残余ビットを有する場合があり、したがっ
てＲがゼロでない場合、ＤＲＬＥ（Ｓ）は｛１，Ｒ，
０｝の形のリテラルで終わることになる。これらを使用
すると、Ｌ（ＤＲＬＥ（Ｓ））＝（（Ｍ−Ｋ）／Ｎ＊Ｌ（リピー
タ）＋残余＋Ｒとなり、上式でＫがゼロの場合、残余は０であり、ゼロ
でない場合はＬ（リピータ）である。

【００４９】典型的なディジタル印刷の場合、Ｌ（Ｓ）
は大きいためＬ（ＤＲＬＥ（Ｓ））に対する影響は以下
によって十分に概算される。（Ｍ／Ｎ）＊Ｌ（リピータ）Ｎ＝２の場合、上式は以下のようになり、（Ｍ／２）＊２＝Ｍ圧縮比は以下のようになる。Ｒ（ＤＲＬＥ（Ｓ））＝Ｌ（Ｓ）／ＭＬ（Ｓ）はＭ＊（２^W−１）であり、したがってＮ＝２の場合はＲ（ＤＲＬＥ（Ｓ））＝Ｍ＊（２^W−１）／Ｍ＝２^W−１となることに留意されたい。Ｗ＝５の場合、Ｒ（ＤＲＬ
Ｅ（Ｓ））は３１である。

【００５０】この計算は、Ｓがすべてゼロの２進値であ
ることに基づいていることに留意されたい。また、長さ
が２^W−１のダブル・ランの反復パターンの総合的結果
によって、同じ圧縮比２^W−１が得られることにも留意
されたい。したがって、Ｗの選定はきわめて重要であ
る。

【００５１】例３例２を概括すると、Ｎ＝２が２^W−１の場合の長さ２^W−
１ビットの単一の反復ダブル・ランの可能な最善の圧縮
比がわかる。この例では、Ｎ個のダブル・ランを有する
反復パターンの最高の圧縮比を計算する。この場合も、
Ｌ（Ｓ）は２進データのシーケンスＳの長さを示すもの
とし、Ｓは、Ｓ全体を通じてパターンとしてＭ回繰り返
されるｎ個のダブル・ランＬ１、Ｌ２、．．．、Ｌｎを
含むようになっているものとする。言い換えると、Ｓ＝Ｌ１Ｌ２．．．ＬｎＬ１Ｌ２．．．Ｌｎ
．．．Ｌ１Ｌ２．．．Ｌｎ剰余となる。例として、図２に３回生起する反復パターン
｛４，３｝｛２，５｝を示す。

【００５２】Ｌ（ＤＲＬＥ（Ｓ））は、リテラル、リピ
ータ、および剰余のパターンの１つのインスタンスの累
積長である。Ｌ（Ｓ）が大きい場合は重要ではないため
説明を簡単にするために剰余はないものとする。

【００５３】パターンの１インスタンスのリテラルの長
さは、パターン内の各リテラルの長さの合計である。こ
れは、Ｌ（すべてのリテラル）＝ｎ＊（１＋２＊Ｗ）となる。

【００５４】パターンの残り（Ｍ−１）個のインスタン
スはリピータによって表される。リピータの長さは以下
のようになる。Ｌ（すべてのリピータ）＝（Ｍ−１）＊（１＋最高限度
（ｌｏｇ２Ｎ））したがって、以下のようになる。Ｌ（ＤＲＬＥ（Ｓ））＝ｎ＊（１＋２＊Ｗ）＋（（Ｍ−
１）＊（１＋最高限度（ｌｏｇ２Ｎ））Ｗ＝５およびＮ＝２の場合、上式は以下のようになる。Ｌ（ＤＲＬＥ（Ｓ））＝１１＊ｎ＋２＊（Ｍ−１）

【００５５】Ｍが大きくｎが小さい（たとえば２）の場
合、これは２＊（Ｍ−１）に収束する。この結果は、ダ
ブル・ランの長さに対して変化しないことに留意された
い。したがって、圧縮比は反復パターン内のダブル・ラ
ンが最大長の場合に最大化され、その逆の場合（すなわ
ち各ダブル・ランが「０１」というパターンを表す場
合）は最小化される。

【００５６】任意のＷおよびＮのダブル・ランの最大長
反復パターンは以下の形になる。｛２^W−１，２^W−１｝｛２^W−１，２^W−１｝．．．．．
｛２^W−１，２^W−１｝上記で、このパターン内のダブル・ランの数は合計Ｎ個
になる。

【００５７】このパターンの長さはＮ＊２＊（２^W−１）である。これを大きなＭとＮ＝２に当てはめると、以下
の圧縮比が得られる。Ｒ（ＤＲＬＥ（Ｓ））＝（Ｍ＊４＊（２^W−１））／
（２＊（Ｍ−１））Ｍが大きい場合、（Ｍ−１）をＭに置き換えることがで
き、以下の概算結果が得られる。２＊（２^W−１）＝２^W+1−２これは、予測通り例２の結果の正確に２倍である。

【００５８】したがって、Ｗ＝５の場合、Ｎ＝２につい
て得られる最高の圧縮比は約６２である。

【００５９】グレースケール・データへの適用以下の説明では、以上の説明の結果をグレースケール・
データに適用する。グレースケール・データは、一般に
はインク・ジェット・プリンタまたはレーザ・プリンタ
で印刷される、モノクローム・ディジタル・イメージ、
または１プレーン当たり１ビット／画素の複数プレーナ
・ディジタル・カラー・イメージの単一プレーンを表す
２進データである。

【００６０】ディジタル・イメージでは、データの各ビ
ットを画素と呼ぶ。画素の値１は一般にその画素が（た
とえば黒色のインクまたはトナーで）「印刷」されるこ
とを意味し、値ゼロはその画素が印刷されない（すなわ
ち白または印刷媒体の色）であることを意味する。

【００６１】テキストとグラフィックスを混在させる典
型的なソフトウェア・システムでは、ユーザはグレーの
様々な陰影を使用することができる。たとえば、図の一
部に２５％のグレーを使用し、別の部分に５０％のグレ
ーを使用することができる。その他の部分にはグレーが
なく、ある部分は完全に黒とすることができる（それぞ
れ０％および１００％のグレー）。

【００６２】グレーの陰影が最終的に２進データにされ
ると、グレーのパーセンテージはグレー領域上の印刷画
素の割合によって概算され、その領域の上にそれらの印
刷画素が分散される。分散プロセスでは一般にグレーを
概算すると同時に、不快な可視パターン（すなわちモア
レ・パターン）が生じる可能性を最小限にするように試
みる。

【００６３】分散は通常、ハーフトーンと呼ばれるパタ
ーンで表される。ハーフトーンは一般に、グレーの値を
表し、ハーフトーン・セルと呼ばれる画素から成る小さ
い矩形である。セル内の合計画素数に対する印刷画素数
によって、セルが表すグレーのパーセンテージが決ま
る。たとえば、４×４セルによって最大１７のグレーの
陰影を表すことができる。

【００６４】ハーフトーン・セルのサイズが通常小さい
ことは価値がない。１６×１６セルが一般的であり、そ
れによって最大２５７個のグレー値を表すことができ、
これはほとんどの用途で必要な数より多い。

【００６５】図５（ａ）に、ディジタル・イメージの一
部にあるハーフトーンの例を示す。このカットには１２
本の走査線がある。走査線とはディジタル・イメージ内
の画素から成る１本の線である。データのこの部分内に
は２５％のグレーを表すハーフトーン・パターンがあ
る。この例では、最長のランでも７画素しかなく、最小
は１画素である。１ビット・パターンの場合、ＲＬＥで
はこれを十分に扱えないことは明らかである。

【００６６】図５（ｂ）に、各走査線にＭＲを個別に適
用したＤＲＬＥを示す。全体的な圧縮に関して最大の柔
軟性をもたせるように、一般には一度に１本の走査線に
圧縮が適用される（グレースケール・データと写真画像
が含まれているページを考えてみると、イメージ・デー
タを有する走査線はＤＲＬＥではそれほど良好に圧縮す
ることができず、他の何らかの形の圧縮を必要とするこ
とがある）。この結果、合計長が以下の通りの３２個の
リテラルと４８個のリピータになる。（３２＊１１）＋（４８＊２）＝４４８ビット

【００６７】この例では、走査線カットの幅は８３画素
に過ぎず、そのような線が１２本ある。したがって、行
イメージ・サイズは（１２＊８３）＝９９６ビットとなる。

【００６８】したがって、この例の圧縮比は９９６／４４８＝２．２２となる。

【００６９】３００ドット／インチ（ｄｐｉ）のイメー
ジでは、８３ビットの走査線は０．２８インチ（０．７
１ｃｍ）に過ぎず、６００ｄｐｉでは０．１４（０．３
６ｃｍ）インチに過ぎない。これらのｄｐｉレベルは今
日のディジタル・プリンタに典型的なものである。した
がって、現実には典型的な８１／２×１１インチの用
紙上の走査線は一般に３００ｄｐｉで２５５０画素、６
００ｄｐｉで５１００画素である。反復パターンを含む
グレースケール・データの典型的なカットは、０．２８
インチ（０．７１ｃｍ）または０．１４インチ（０．３
６ｃｍ）を超えつつある。したがって現実の例では、リ
ピータの圧縮比に与える効果はこの例よりも大きな影響
を持ち、圧縮比はこれより高くなる。

【００７０】ハーフトーン・セルのサイズが小さいた
め、ハーフトーンのグレースケール・データは従来のＲ
ＬＥでは十分に役立たない。これは、ランのサイズが小
さく、ランの長さフィールドの長さがラン自体の長さと
それほど違わないため、圧縮比が小さくなるためであ
る。または、ＲＬＥではそのデータをまったく圧縮する
ことができず、実際にはそれを伸張する可能性がある。

【００７１】ＤＲＬＥは、各パターンが小さい、１とゼ
ロの可変長パターンを含むデータのクラスの場合、きわ
めて良好な圧縮を実現する適応型無損失圧縮方式であ
る。ＤＲＬＥは、コンピュータで作成され、１プレーン
当たり１ビット／画素のカラー・プリンタまたはモノク
ローム・プリンタを対象とする、テキストとグラフィッ
クスを含む文書のディジタル表現では典型的なタイプの
データである、ハーフトーン化されたグレースケール・
データに特に適切である。したがって、このタイプの文
書を保持するのに必要な記憶容量が大幅に低減される。

【００７２】圧縮による記憶量低減は、低コストの高解
像度ディジタル画像処理システム、すなわち、インク・
ジェット・プリンタおよびレーザ・プリンタの必須要素
である。これは記憶装置が高価な機構であるために必要
である。記憶量をなくしたり減らしたりすることは、コ
スト競争力のある製品を開発する有効な方法である。

【００７３】レーザ・プリンタ内で、所与のページの用
紙がプリンタを通過して移動し始めた後は、その用紙は
連続的に移動する。この期間中、ソフトウェアとハード
ウェアはリアルタイム制約の下でレーザに走査線を送る
必要がある。したがって、圧縮解除方式の計算効率が高
いことが重要である。ＤＲＬＥの圧縮解除方式はきわめ
て単純であることは明白であろう。さらに、Ｎ＝２およ
び最新履歴（ＭＲ）の場合、ＤＲＬＥの圧縮圧縮アルゴ
リズムも簡単である。したがって、ＤＲＬＥは、高い圧
縮比を実現するだけでなく、実施がきわめて容易であ
り、リアルタイム環境におけるソフトウェアとハードウ
ェアの両方の実施態様にとって効率上有用である。

【００７４】ソフトウェア実施態様ＤＲＬＥのソフトウェア実施態様の例を、本明細書に付
属文書Ｉとして添付されており、これはＣ言語ソース・
コードである。このプログラムの動作は以下のハードウ
ェア実施態様の説明を読めば容易に明らかになろう。

【００７５】ハードウェア実施態様図６に、２進データのストリームを圧縮するのに必要な
データ経路と処理段階に焦点を絞ったＤＲＬＥのハード
ウェア実施態様を図示する。データの流れは左から右の
方向である。システム・メモリ（たとえばＤＲＡＭ）か
ら非圧縮ソース・データが読み取られ、入力ＦＩＦＯ
１０１を経由して圧縮器に入る。入力ＦＩＦＯは任意選
択であるが、これによってメモリからソース・データを
バーストで読み取ることができ、全体的なシステム・パ
フォーマンスを最適化することができる。後述するいく
つかの処理段階１０３の後、圧縮されたデータ・ワード
が出力ＦＩＦＯ１０５に書き込まれる。出力ＦＩＦＯ
も任意選択であるが、この場合もこれによって圧縮デー
タをメモリにバーストで書き込むことができる。

【００７６】入力ＦＩＦＯ１０１入力ＦＩＦＯはＤＭＡ読取りＦＩＦＯとして実施するこ
とができる。このＦＩＦＯはシステム・メモリから読み
取る要求と、システム・メモリから読み取ったデータを
ＦＩＦＯバッファに格納する要求を生成する論理回路を
含む。

【００７７】ダブル・ラン・エンコーダ１０９ダブル・ラン・エンコーダは、入力ＦＩＦＯからワード
をアンロードする要求を出すエンコーダである。本明細
書に記載の実施例では、データ・ワードのサイズは３２
ビットである。しかし、異なるサイズのバッファとカウ
ンタを使用してその他のサイズのデータ・ワードも扱う
ことができ、その特定の詳細は当業者なら容易にわかる
であろう。ダブル・ラン・エンコーダの処理によって、
３２ビットのデータ・ワードが５ビットのランレングス
符号化に変換される。データは、ダブル・ラン・エンコ
ーダに３２ビット・ワードとして入るかその他のサイズ
のワードとして入るかに関係なく、２進データの直列ス
トリームとみなされる。従来技術のランレングス・エン
コーダ１０９ａを使用してこの直列ストリームを読み取
り、５ビット・カウンタで連続ビットの数をカウントす
る。内部状態機械１０９ｂが、ランレングス・エンコー
ダの動作を制御し、最初にゼロ・ビットをカウントする
ように指示する。１に到達すると、ランレングス・エン
コーダのゼロのカウントが、ダブル・ランＦＩＦＯ１
１１内のレジスタＨ２の上位半分にロードされる。ただ
し、Ｈ２は後述するように１０ビットのレジスタであ
る。内部状態機械１０９ｂは次にランレングス・エンコ
ーダ１０９ａに対して連続する１のビットをカウントす
るように指示する。ゼロに到達すると、ランレングス・
エンコーダの１のカウントがレジスタＨ２の下位半分に
ロードされる。この時点で、レジスタＨ２には有効なダ
ブル・ラン符号化が入れられ、ダブル・ラン・エンコー
ダの状態機械はこの事象を後述するＤＲＬＥ状態機械に
通知する。

【００７８】ダブル・ラン・エンコーダはこのストリー
ムの処理中に２つの問題を処理しなければならない。第
１に、ゼロのランまたは１のランがワード境界を越すこ
とがある。ランレングス・エンコーダがワード内の最後
のビットに到達すると、ダブル・ラン・エンコーダは入
力ＦＩＦＯから別のワードを要求しなければならない。
入力ＦＩＦＯが次のワードを供給すると、ランレングス
・エンコーダ１０９ａは現行ランのカウントを再開す
る。

【００７９】第２に、ソース・ストリームに、ランレン
グス・エンコーダの５ビット・カウンタが保持すること
ができる最大値である３１ビットより大きいゼロのラン
または１のランが入っている場合がある。これが発生し
た場合、ダブル・ラン・エンコーダはそのランを２つ以
上のダブル・ラン符号化に分割しなければならない。こ
の特殊な事態はＲＬＥ状態機械１０９ｂが処理する。ラ
ンレングス・エンコーダは、１つのラン内の３２番目の
ビットに到達するとその事象をＲＬＥ状態機械に通知
し、ＲＬＥ状態機械はＤＲＬＥ状態機械１１５に対して
レジスタＨ２内の値が完結していることを通知する。レ
ジスタＨ２内の値は、ゼロのランのカウント中に最大カ
ウントに達した場合は｛３１，０｝であり、１のランの
カウント中に最大カウントに達した場合は｛ｎ，３１｝
である。ただし、ｎは直前のランでカウントされたゼロ
の数である。Ｈ２内の値が受け入れられると、ＲＬＥ状
態機械１０９ｂはランレングス・エンコーダを再始動さ
せ、ランレングス・エンコーダは前に中断したところか
らビットのカウントを再開する。

【００８０】ＲＬＥ状態機械は、当業者に周知の技法に
よる順序論理回路を使用して実施することができる。状
態機械の機能も、論理ゲートを使用して個別論理回路と
して実施することができる。その具体的な詳細は本発明
を理解するのに重要ではなく、当業者には周知である。

【００８１】ダブル・ランＦＩＦＯ１１１ダブル・ランＦＩＦＯは、ダブル・ラン・エンコーダ１
０９によって生成された最後の３つの結果を保持するＦ
ＩＦＯとして構成された３個の１０ビット・レジスタに
過ぎない。図７で、この３個のレジスタにはＨ２、Ｈ
１、およびＨ０と符号が付けられている。圧縮開始時に
は、Ｈ２がゼロ・クリアされ、Ｈ１とＨ０はそれぞれ
｛３１，０｝に初期設定される。この初期設定値によっ
て、ゼロ・ランで始まるデータ・ストリームの圧縮度が
向上する。ダブル・ラン・エンコーダがその最初の結果
を生成すると、それらがＨ２にロードされる。Ｈ２、Ｈ
１、およびＨ０内の値は履歴比較器１１３によって検査
され、履歴比較器は後述するようにＤＲＬＥ状態機械に
データを供給する。ＤＲＬＥ状態機械が履歴比較器の結
果に基づいて動作すると、レジスタＨ２およびＨ１内の
値がそれぞれレジスタＨ１およびＨ０にシフト・ダウン
され、レジスタＨ２は再びゼロ・クリアされる。その
後、レジスタＨ２を使用して次のダブル・ラン値を形成
することができる。

【００８２】履歴比較器１１３履歴比較器は、２つの比較を行い、その結果はＤＲＬＥ
状態機械が圧縮コードの生成を制御するために使用す
る。履歴比較器は、２つの１０ビット等価比較器を含
む。第１の等価比較器はレジスタＨ２をレジスタＨ１と
比較し、第２の等価比較器はレジスタＨ２とレジスタＨ
０を比較する。これらの比較結果は、ＤＲＬＥ状態機械
に供給され、コード・エミッタ１１７を制御する。

【００８３】ＤＲＬＥ状態機械１１５ＤＲＬＥ状態機械は、履歴比較器から結果を受け取り、
その結果に基づいてコード・エミッタが生成するコード
のタイプ、すなわち後述のようにＹかＺかを選択する。

【００８４】ＤＲＬＥ状態機械は、３ステート有限状態
機械（ＦＳＭ）として実施することができる。初期状態
は、状態０であり、現行ダブル・ランについて検討中の
前のダブル・ランがない状態である（前にＡ≠Ｃ、Ａ≠
Ｂ）。この場合、現行ダブル・ランは、リテラルとして
出されるか（履歴内のいずれとも一致しない場合、Ａ≠
Ｃ、Ａ≠Ｂ）、履歴内の最新項目とのみ一致する場合
（Ａ≠Ｃ、Ａ＝Ｂ）はリピータとして出され、現行ダブ
ル・ランが最も古いものと一致する場合（Ａ＝Ｃ、Ａ≠
Ｂ）（状態１）または履歴内の両方のダブル・ランと一
致する場合（Ａ＝Ｃ、Ａ＝Ｂ）（状態２）は、状態を変
化させる。

【００８５】状態１は、前のダブル・ランが現行ランだ
ったときに履歴比較機内の最も古いものと一致したが、
最も新しいものとは一致しなかった場合（前にＡ＝Ｃ、
Ａ≠Ｂ）に発生する。この場合、現行ダブル・ランが現
行の最も古いものと一致する場合（Ａ＝Ｃ）、２要素リ
ピータを出すことができる。そうでない場合は、前のリ
テラルを出さなければならず、現行のものはリテラル
（Ａ≠Ｂ）または単一要素リピータ（Ａ＝Ｂ）として出
される。

【００８６】状態２は、前のダブル・ランが現行ダブル
・ランだったときに履歴比較器内の両方の要素と一致し
た場合（前にＡ＝Ｃ、Ａ＝Ｂ）に発生する。この場合、
現行ダブル・ランが現行の最も古いものと一致しする場
合（Ａ＝Ｃ）、２要素リピータを出すことができる。そ
うでない場合（Ａ≠Ｃ）、前の単一リピータを出さなけ
ればならず、現行のものはリテラルとして出される。

【００８７】ＤＲＬＥ状態機械は、付属文書１のソース
・コードで表されるものとして前述したソフトウェア実
施態様で説明している状態機械のコードを実施する状態
機械である。

【００８８】コード・エミッタ１１７コード・エミッタはＹとＺの２つの出力を発生する。Ｙ
には、完全な１１ビットのリテラル・コードか、２ビッ
トの単一反復コードか、または２ビットのダブル反復コ
ードが入る。Ｚには、Ｙのコードのサイズ、すなわち２
または１１が入る。コード・エミッタは、履歴比較器の
結果に基づいてＤＲＬＥ状態機械１１５によって制御さ
れる。Ｈ２から１０ビットの値を取り出し、ＡＤＤ０論
理回路１１４によって最上位ビットとして０を前に付加
し、１１ビットの結果をＹ上に駆動することによって、
リテラル・コードが生成される。それと並行して、値１
１（２進数１０１１）がＺに駆動される。２進数１０を
Ｙの最下位ビットに駆動し、値２（２進００１０）をＺ
に駆動するだけで単一反復コードが生成される。同様
に、２進数１１をＹの最下位ビットに駆動し、Ｚに値２
（２進００１０）を駆動することによって、ダブル反復
コードが生成される。ＤＲＬＥ状態機械１１５からの出
力信号は、コード・エミッタ１１７への３つの入力のう
ちの１つを選択し、前述のようにコード・エミッタはそ
れをＺ上の１１または２と共にＹに入れる。

【００８９】ワード・パッカ１１９ワード・パッカは、コード・エミッタ１１７からｎビッ
トのコードを受け取り、それらを３２ビット・ワードに
パックする。ワード・パッカはコード・エミッタから、
コードすなわちＹからの値と、コードのサイズすなわち
Ｚからの値の２つの値を受け取る。コード・エミッタは
２ビットと１１ビットの２つのコード・サイズしか出力
しない。コード・サイズに応じて、ワード・パッカは現
行２ビット・コード値または１１ビット・コード値を、
前に受け取った値と結合し、３２ビット・ワードを形成
する。ワード・パッカは、ワード境界を越えるコードを
適切に扱わなければならない。完全な３２ビット・ワー
ドを形成するのに十分なコードが結合されると、ワード
・パッカはその結果を出力ＦＩＦＯに渡す。ワード・パ
ッカ１１９の機能を実施する回路は当業者なら容易にわ
かるであろう。図７は、ワード・パッカ・ブロック１１
９のデータ経路の作用を示す、適合する一実施態様のブ
ロック図である。ワード・パッカはコード・エミッタ１
１７から一続きのｎビット・コードを受け取り、それら
を一緒にパックして３２ビット・ワードにする。ワード
・パッカはコード・エミッタから、コードすなわちＹか
らの値と、コードのサイズすなわちＺからの値の２つの
値を受け取る。

【００９０】図７のワード・パッカは、そのコアにある
３２ビットのバレル・シフタ１３１を使用する。３２ビ
ット・バレル・シフタは、Ｙで送られたコード値を回転
させて適切な位置に入れ、３２ビット・レジスタ１３５
に連結された前のコード値と結合することができるよう
にする。３２ビット幅の２：１マルチプレクサ１３７
が、現行コード値を、前の連結コード・データのストリ
ングと結合し、新しい連結を３２ビット・レジスタ１３
５に保管する。３２ビット・レジスタが一杯になるかオ
ーバーフローすると、ワード・パッカはその結果を出力
ＦＩＦＯ１０５に渡す。

【００９１】Ｚ上の４ビット値は、Ｙ上のコードのサイ
ズを示す。Ｚの値は５ビットのレジスタ１４１に累積さ
れ、このレジスタのＰａｋＳｈという符号が付けてある
出力がバレル・シフタの動作を直接制御し、３２個の個
別に制御可能な２：１マルチプレクサを含む３２ビット
幅の２：１マルチプレクサ１３７の動作を間接的に制御
する。ＰａｋＳｈ値は、マスク生成器１４５によって単
純な５ビットの２進値から３２ビットのマスクに変換さ
れる。ＰａｋＳｈ値０ｘ００、０ｘ０１、０ｘ０
２、．．．、０ｘ１Ｆによって、それぞれ３２ビットの
マスク値０ｘ００００００００、０ｘ８００００００
０、０ｘＣ０００００００、．．．、０ｘＦＦＦＦＦＦ
ＦＦが生成される。次にこの３２ビット・マスクからの
ビット値によって、３２個の２：１マルチプレクサのそ
れぞれが直接、個別に制御されて、現行コード・データ
または前のコード・データが選択される。このようにし
て、３２ビット幅の２：１マルチプレクサ１３７は現行
コード値をその直前のコード値のストリングと結合し、
その新しい結合を３２ビット・レジスタ１３５にロード
することができるようにする。

【００９２】上記で示していない小さい状態機械が、５
ビットおよび３２ビットのレジスタ１４１および１３５
のロードと、マスク生成器１４５のイネーブルとを制御
する。また、これはＡＬＵ１３１からの合計および桁
上げ出力（図示せず）のモニタも行い、現行コードによ
って３２ビットが一杯になるかまたはオーバーフローす
るかどうかを判断する。この２つのいずれの場合も、３
２ビット・レジスタ１３５にロードされた後、その結果
を出力ＦＩＦＯ１０５に渡さなければならない。後者
の場合、次のコード値を結合する前に、現行回転コード
のオーバーフロー部分を３２ビット・レジスタの開始ビ
ット部分にロードしなければならない。この状態機械は
この順序付けを扱う。

【００９３】出力ＦＩＦＯ１０５出力ＦＩＦＯはＤＭＡ書込みＦＩＦＯとして実施するこ
とができる。このＦＩＦＯは、ワード・パッカ１１７か
ら受け取った３２ビット・ワードを格納し、そのワード
をメモリに書き戻す。メモリに格納されている圧縮デー
タはデコーダに渡され、デコーダの出力は元の入力ファ
イルと同じである。

【００９４】デコーダは上述の処理を逆にたどる。適合
するデコーダの実施態様の詳細は、当業者なら容易にわ
かるであろう。

【００９５】以上、ダブル・ランレングス・エンコーダ
の特定の実施態様について説明したが、異なるワード・
サイズを使用したり、３個のレジスタＨ１〜Ｈ２より多
くのレジスタを設けたり、履歴比較による比較を３つよ
り多くしたり、ＤＲＬＥ状態機械の状態を３つより多く
したり、０と１の代わりに１と０の対にして、リテラル
を示す接頭コードとして０の代わりに１を使用し、１の
代わりに０を使用してリピータを示したりするなど、特
許請求の範囲に記載の本発明の精神および範囲から逸脱
することなく多くの変更を加えることができる。

【図面の簡単な説明】

【図１】２進データの様々な表現を示す図である。

【図２】最新（ＭＲ）履歴を使用したダブル・ランレ
ングス符号化の例を示す図である。

【図３】最新パターン変化（ＭＲＰＣ）を使用したダ
ブル・ランレングス符号化の例を示す図である。

【図４】事前定義固定パターン（ＰＦＰ）を使用した
ＤＲＬＥの例を示す図である。

【図５】グレースケール・データのダブル・ランレン
グス符号化を示す図である。

【図６】本発明のダブル・ランレングス符号化技法の
ハードウェア実施態様を示すブロック図である。

【図７】本発明と共に使用するのに適したワード・パ
ッカを示すブロック図である。

【符号の説明】

１０１入力ＦＩＦＯ１０３処理段階１０５出力ＦＩＦＯ１０９ダブル・ラン・エンコーダ１０９ａランレングス・エンコーダ１０９ｂ内部状態機械１１１ダブル・ランＦＩＦＯ１１３履歴比較器１１５ＤＲＬＥ状態機械１１７コード・エミッタ１１９ワード・パッカ１３１バレル・シフタ１３７マルチプレクサ１４５マスク生成器

Claims

【特許請求の範囲】

【請求項１】２進データの無損失圧縮を行うシステム
であって、ａ）各符号化対が０のランと１のランを表す、２進デー
タのストリームを前記符号化対としてランレングス符号
化する手段と、ｂ）前記符号化対の履歴を記憶する手段と、ｃ）現行符号化対を前記履歴内の少なくとも第１および
第２の前の符号化対と比較する手段と、ｄ）ｉ）第１のコードが前記現行符号化対が前記第２の
前の符号化対と一致し、前記第１の前の符号化対と一致
しなかったことを示し、第２のコードが前記現行符号化
対が前記第２の前の符号化対および前記第１の前の符号
化対と一致したことを示す、接頭コードを有する前記現
行符号化対の一方を選択し、ｉｉ）前記選択された一方
と前記選択された一方の長さとを出力として生成する手
段と、ｅ）前記出力を所定の長さを有するワードにパックする
手段とを備えるシステム。
【請求項２】前記ランレングス符号化手段が、ランレ
ングス・エンコーダに入力源からデータを要求させて前
記データを対に変換させるように動作するランレングス
状態機械に結合されたランレングス・エンコーダを備
え、各対の第１の要素が入力源から受け取った連続する
０の数を示す数値であり、各対の第２の要素が入力源か
ら受け取った連続する１の数を示す数値であり、前記ラ
ンレングス状態機械が各連続する０と連続する１との対
の組合せの終わりを示す信号を発生するようにさらに動
作することを特徴とする請求項１に記載のシステム。
【請求項３】前記履歴格納手段が、第２のレジスタに
結合された第１のレジスタと第２のレジスタに結合され
た第３のレジスタとを有するＦＩＦＯを備え、前記レジ
スタのそれぞれが２つの半分を有し、その一方に前記ラ
ンレングス・エンコーダ手段によって生成された連続す
る０が格納されその他方に前記ランレングス・エンコー
ダ手段によって生成された連続する１が格納されること
を特徴とする請求項１に記載のシステム。
【請求項４】前記比較器手段が、前記第１のレジスタ
の内容を前記第２のレジスタおよび前記第３のレジスタ
と比較し、前記比較の結果を示す対応する第１おび第２
の比較信号を発生する比較器を備えることを特徴とする
請求項３に記載のシステム。
【請求項５】ａ）前記接頭コードを前記現行符号化対
の前に付加する付加接頭コード手段と、ｂ）前記第１および第２のコードを生成する反復コード
手段とをさらに備える、請求項１に記載のシステム。
【請求項６】前記選択手段が、ａ）前記比較器手段と前記履歴手段と前記ランレングス
符号化手段とに結合されたダブル・ランレングス状態機
械と、ｂ）前記付加接頭コード手段と前記反復コード手段と前
記ダブル・ランレングス状態機械とに結合され、前記ダ
ブル・ランレングス状態機械から受け取った信号に基づ
いて、接頭コードを有する前記現行符号化対と、前記第
１のコードと、前記第２のコードとのうちの１つをその
出力として選択するコード・エミッタ・マルチプレクサ
と、ｃ）前記マルチプレクサに結合され、前記選択された１
つの出力の長さを生成する論理回路とを備えることを特
徴とする請求項５に記載のシステム。
【請求項７】前記パッキング手段が、ａ）前記論理回路に結合され、前記選択された１つの出
力の長さを１つの入力として受け取り、合計および桁上
げ出力を生成するアキュムレータと、ｂ）前記アキュムレータに結合され、前記アキュムレー
タの合計出力をその入力として受け取り、その内容を前
記アキュムレータに第２の入力として供給するレジスタ
と、ｃ）前記コード・エミッタ・マルチプレクサに結合さ
れ、前記コード・エミッタ・マルチプレクサからの選択
された出力をそのデータ入力として受け取るバレル・シ
フタと、ｄ）前記レジスタに結合され、前記レジスタの内容に基
づいてマスク出力を生成するマスク生成器と、ｅ）前記バレル・シフタと前記マスク生成期手段とに結
合され、それぞれが前記バレル・シフタの出力のうちの
対応する１つを１つの入力として有する１組の２：１マ
ルチプレクサと、ｆ）前記１組の２：１マルチプレクサに結合され、前記
１組の２：１マルチプレクサへの対応する第２の入力と
して結合された出力を有する第２のレジスタとを備える
ことを特徴とする請求項６に記載のシステム。
【請求項８】２進データの無損失圧縮を行う方法であ
って、ａ）各符号化対が０のランと１のランを表す２進データ
のストリームを符号化対としてランレングス符号化する
ステップと、ｂ）前記符号化対の履歴を記憶するステップと、ｃ）現行符号化対を前記履歴内の少なくとも第１および
第２の前の符号化対と比較するステップと、ｄ）第１のコードが前記現行符号化対が前記第２の前の
符号化対と一致し、前記第１の前の符号化対と一致しな
かったことを示し、第２のコードが前記現行符号化対が
前記題２の前の符号化対および前記第１の前の符号化対
と一致したことを示す接頭コード付きの前記現行符号化
対のうちの１つを選択するステップと、ｅ）前記選択された１つと前記選択された１つの長さと
を出力として生成するステップと、ｆ）前記出力を所定の長さを有するワードにパックする
ステップとを含む方法。
【請求項９】前記ランレングス符号化ステップが、入
力源からデータを要求して前記データを、各対の第１の
要素が入力源から受信した連続する０の数を示す数値で
あり、各対の第２の要素が入力源から受け取った連続す
る１の数を示す数値である対に変換し、各連続する０と
連続する１との対の組合せの終わりを示す信号を発生す
るステップを含むことを特徴とする請求項８に記載の方
法。
【請求項１０】前記履歴記憶ステップが、前記ランレ
ングス・エンコーダ・ステップによって生成された前記
連続する０および１を、第２のレジスタに結合された第
１のレジスタと、前記第２のレジスタに結合された第３
のレジスタとを有するＦＩＦＯに格納するステップを含
み、前記レジスタのそれぞれが２つの半分を有し、その
うちの一方に連続する０が格納され、他方に連続する１
が格納されることを特徴とする請求項９に記載の方法。
【請求項１１】前記比較ステップが、前記第１のレジ
スタの内容を前記第２のレジスタおよび前記第３のレジ
スタと比較し、前記比較の結果を示す対応する第１およ
び第２の比較信号を発生するステップを含むことを特徴
とする請求項１０に記載のシステム。
【請求項１２】ａ）前記接頭コードを前記現行符号化
対の前に付加するステップと、ｂ）前記第１および第２のコードを生成するステップと
をさらに含む、請求項８に記載の方法。