JPS60154776A - コード化及び解号方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 次の順序で本発明を説明する。

（ア）　［産業上の利用分野］ （イ）　［開示の概要］ （つ）　［従来技術］ （１）　［発明が解決しようとする問題点コ（オ）　［
問題点を解決するための手段］　（第１図、第３図） （力）　［作用］ （キ）　［実施例］ （キー１）　コード化（第２．１図〜第２．５図）（キ
ー２）　毎号（デコード）（第４．１図〜第４．６図）
（り）　［発明の効果］ （ア）　［産業上の利用分野コ 本発明は例えばファクシミリ等のように、文字像や画像
を走査して得たデータを伝送する際に用いるコード化及
び毎号（復号）方式に関する。

（イ）　［開示の概要コ 修正ＲＥＡＤ方式によるファクシミリ・ビット信号の処
理に例にとり、データ処理のフローを説明する。ラン長
さコードの処理にテーブルを用いる。データのラインは
タテ関連コードとラン長さコードを用いてコード化され
る。

（つ）　［従来技術］ ＣＣＩ　ＴＴ　プロシーディンゲス　オブ　アイイーイ
ーイー、６８巻７号、１９８０−７，８５４〜８６７頁
、Ｒ，ハンター他の論文。

プロシーディンゲス　オブ　アイアールイー、４０巻、
１９５２−９．１０９７〜１１０１頁のり、ハフマンの
論文。

米国特許、３８８３８４７号、４０４４３４７号、３８
３３９００号。

ハフマンは、最少の冗長度の可変長コードを作る方法を
示している。コード・ワードの長さは元のワードの出現
頻度に依り、頻出するワードは短かいコード・ワードに
なる。これはディジタル・イメージ処理に有用だが、パ
ターンがランダムな可変長コードについては欠点があり
、デコード（毎号）を複雑化する。

国際電信電話諮問委員会（ＣＣＩＴＴ）は、標準の１次
元データ圧縮力式（改良ハフマン方式）及び黒白ファク
シミリ像用の２次元データ圧縮力式（修正ＲＥＡＤ方式
）を持っている。ホスト電算機に付けられたファクシミ
リを圧縮された像をホストに送ることができ、又ホスト
は像データの圧縮を高速で行なうことが望ましい。又像
の一部を抽出して、パディング等の処理をして再組立後
、ホストに送ったり、コード化してファクシミリに送っ
たりする必要がある。

高品質のディジタル・ファクシミリでは像のデータ圧縮
が必要である。標準的なファクシミリ文書はタテ方向に
３．８５走査ライン／ｍのラインを持つ。又、細かい像
に対しては７．７本／Ｉｍ＋のラインも使える。標準の
ヨコ（水平）方向解像度は８．０４画素／ｍｕ　（２１
５ｍｎについて１７２８画素）に固定されており、斜線
で大きな段が出ないようになっている・ ２１５ｍ＋ｎＸ２８０画の一部の原稿からの像データを
貯えるのに約２５万バイトが要る。分解能を高くすると
、約５０万バイトにもなる。ＣＣＩＴＴ１次元方式等の
ラン長さコードは代表的な場合で、約５から１５の係数
で、必要なメモリの容量を減らす。２次元方式は、相続
く走査ラインの間での関連をしらべて、更に良い圧縮を
しようとする。

固定したコードは、統計平均が全書類に適用できること
を想定している。しかし平均値に合わない文書もある。

想定が全然使えない時は、圧縮された像区域は逆に圧縮
しない像より更に多くのビットを要する。選択的に非圧
縮モードにするとこのケースを防げる。

一般に、ベル（画素）の白と黒はランダムに分布しては
いなく、互いに高い相関性を持っている。

成るスキャン・ライン上で１つの色（白とか黒とか）の
ベルは列（ランとも呼ぶ）をなしている。

ラン長さコードはこれを利用し、各ベルの色でなく、成
る色の続く数をコードで示す。ラン長さは色毎に変る。

最初の色は大低白だからこの色を示す特定のコードはな
くてもよい。長さゼロで黒が最初から来ることを示して
もよい。

ＣＣＩ　ＴＴ　１次元標準修正ハフマン・コードはラン
長さコード方式であって、白と黒のランが別々のテーブ
ルを持っている。６３以上のランはコード・テーブルの
寸法を１桁小さくするため２部分にわけてコード化され
る。６４の倍数が先ず「メイクアップ」コードとしてコ
ード化され、次に残りが終了コードにされる。短かいラ
ン（０〜６３）は終了コードだけになる。

伝送エラーのあとの再同期のためにライン終り（ＥＯＬ
）コードが標準に入っている。これはゼロ１１個のあと
の１個の１という形である。

ラン長さコードは水平方向における冗長度に関するもの
だが、普通の像ではタテ方向にも強い相関性がみられる
。垂直方向の関連コードは、歴史ライン（前のスキャン
・ライン）でのラン長さと同じ色変化からの距離として
コート化する。

タテ方向では、ライン全体の約半分が同しであり、約２
５％が１ペル位の距離変化しか含んでいない。

ＣＣＩＴＴ２次元修正関連素子アドレス指定（修正ＲＥ
ＡＤ）コード方式はタテ方向関連コードとして＋３又は
−８迄を用いる。成るランがタテ関連コードで終ってい
なければヨコ・モード（ＨＭ）コードが２つのラン長さ
コードに先行する。１対のランを１つの前置コードでコ
ード化するのは、ラン長さコードのあとに又ラン長さコ
ードが来る率が高いことを利用している。

像が前のラインで終ることがある。パス（ＰＡＳＳ）モ
ードは前のライン（参照ライン、歴史ラインともいう）
のラン信号値を下記のようにスキップする。

歴史ライン１１１０００１１０００００１１今ノライン
１０１００００００００００１１パス・モードのコード
はそれに続くタテ関連コードが通常のように歴史ライン
の２番目でなく３番目の黒（１）のランに参照すること
を示す。

これは、若し最初のタテ関連変化の右（ランの終りの前
）に他の変化が見つかった場合に用いられる。この変化
の所で新しいランがスター１〜する。

ＰＡＳＳモードは１本のランの中で何回もコード化でき
る。

変化のエラーの波及を制限するため、少なくともにライ
ン毎に１木が１次元コード化される。Ｋは通常２で、高
解像度の場合４になる。

修正ＲＥＡＤコード・テーブルを下記に示す。

修正ＲＥＡＤコード・テーブル。

ＲＬ前置コード　００１ ＰＡＳＳ　０００１ ＶＯＩ ＶＬＩ　０１０ ＶＲＩ　０１１ ＶＬ２　００００１０ ＶＲ２００００１１ ＶＬ３　０００００１０ ＶＬ３　０００００１１ ＥＯＬ　０ＯＯＯＯＯＯＯＯＯＯＩＴ 拡張 ２次元　００００００１ｘｘｘ １次元　００００００００１．　ｘ　ｘ　ｘＥＯＬのＴ
はタグ・ビットで１次のラインのコード化が１次元（Ｔ
＝）か２次元（Ｔ＝０）力１を示している。

拡張部分は非圧縮モードとして識別される。このモード
ではＸＸＸビットは’１１１’である。

このモードはハーフトーンの走査時や１ペル、２ペルの
ランが多い像で圧縮の改善をする。

非圧縮モード・コード・テーブル。

像パターン　コード・ワード １ ０１　、　０ｆ ００１　００１ ０００１　０００１ ００００１　００００１ ０００００　０００００１ 脱出 ００００００１Ｔ ０　０００００００１Ｔ ００　００００００００１Ｔ ０００　０００００００００　、Ｉ　Ｔｏｏｏｏ　００
００００００００１Ｔ 脱出コードは５通常のコードに戻る時の信号である。Ｔ
はタグ・ビットであり、次のランの色（黒＝１、白＝Ｏ
）を示す。

（１）［発明が解決しようとする問題点〕従来のファク
シミリ等におけるコード化、解帯に用いられていたデコ
ード・テーブルはメモリ内で大きな寸法をとり、それに
もかかわらず解帯の速さが遅かった。その原因はコート
化及び解帯時のデータ処理が能率的でなかったからであ
る。

（オ）［問題点を解決するための手段］本発明は、ファ
クシミリ等に用いるような、互いにビット値の関連性あ
るデータ・ラインの間でのビット値の関連性を検査して
コート化し伝送し復元する際に、効率的なデータ判定及
び処理ステップを用いて、更に又、コード・テーブルを
適当な寸法に作製し、利用することによりメモリ占有寸
法を過大にせず、信号処理速度を向上させたものである
。

（力）［作用コ 使用されるバッファやレジスタの数が最小限で済み、メ
モリ占有量が比較的小さく、又データ処理ステップ数も
少なくて済む。

（キ）［実施例］ 本発明のコード方式は、修正ＲＥＡＤ及び修正ハフマン
ＣＣＩＴＴ標準コード、並びに各ラインの終りにＥＯＬ
コードを要しない上記コードの変形のコード化と解帯を
することができる。

先ず、ディジタル像を本発明によりコード化することを
説明する。コード化処理は２段階で働らく。第１段で、
入力値が入力バッファから色変化位置（変化、ランの終
り）を含むバッファに移される。各エンド・ポイント・
バッファの中の第１の半ワードは用いられるバイトの数
を含む。次の２つの半ワードはゼロにセットされる。ラ
ンの終り（エンド）が、その後の半ワードに貯えられ。

これは白のラン・エンドで始まる（そのラインの最初の
ランが黒なら、これはゼロになる）。最後のラン・エン
ド（即ち、ライン長さ）は少なくとも２つの余分を複製
される。隣接する半ワードの間の相違が黒と白のランの
ラン長さくＲＬ）である。

コード化の第２段は、各ランがタテ関連コードであるか
ＲＬコードであるかを符号化する。タテ関連コードはイ
ンライン・コードと共に発生される。ＲＬコード・ワー
ドはテーブルを引くのに使わオする。

ＲＬコード・テーブルは下記の如く作られている。

コード・ワードの下位８ビツトがバイト・テーブル中に
右を揃えて貯えられる若し８ビット以上が有効値である
なら下位８ビツトのみがゼロでない）。有効なビットの
数は、コード・ビットからの固定オフセットを伴って、
他のハイドに貯えられている。コード化処理時、圧縮さ
れたデータは３２ビツト・レジスタに集められる。この
レジスタに１６ビツト以上有効なビットがあればその時
に、上位１６ビツトが圧縮バッファに出力される。

１３ビツトより長いコード・ワードはないので、この方
法で常に次のコード・ワードの入る空室ができるよう確
保できる。コード・ワードを圧縮されたデータに加える
には、今の圧縮されたデータを有効ビットの数を（右端
ビットにゼロを入れつつ）左にシフトする。次にコード
・ワードの右を揃えたビットがレジスタに加算乃至はオ
アされる（コード・ワードは非ゼロ・ビットのみ有し、
ゼロは前のシフトで入っていた）。

各ラインをコード化した後、エンド・ポイント・バッフ
ァは１次のラインに対する歴史（前の）ラインとするた
めとっておかれる。符号化処理を始動したプログラムは
、データを２つのバッファの間でやりとりしたり、既に
メモリ内にあるラン・エンド・バッファの序列のコード
化を行なわせることもできる。どちらの場合も、前の符
号化されたデータは、２次元コード化演算のため残して
おく必要がある。

本発明で用いる変数や略語の説明をする。

ＦＬＡＧＩＤ・・・これが１ならそのラインは１次元で
コード化７Ｍ号する意味のフラグ。０なら２次元。

ＭＨ・・・修正ハフマン・コード化／毎号を示すフラグ
（１）。修正ハフマン・コードではＥ○Ｌコードのあと
でタグ・ビットは予定されない。

ＲＰ・・・ラン・エンド・ポイントのバッファへのポイ
ンタ。処理中の（半ワード）ラン・エンドを示す。ラン
・エンドは最初がＲＯで、後続するものはＲ２、Ｒ４、
Ｒ６とよばれる。

ＲＩ）　Ｓ　Ｔ・・・今のラン・エンド・ポインタのバ
ッファのアドレス。このアドレスは、次のラン・エンド
・ポイントのバッファを指示するようにセットされる前
に１次のラインの２次元処理のための歴史バッファのア
ドレスとして残される。

ＨＰ・・・歴史ラインについてのラン・エンド。

ポイントのバッファへのポイントタ。ＨＰは、今コード
化しているラン・エンドに関する歴史ポインとして用い
られる（半ワード）ラン・エンドを示す。歴史ラン・エ
ンドはＨＯと示され、これにつづくものはＨＰと呼ばれ
る。

ＨＰ　Ｓ　Ｔ・・・コード処理中のラインに先行するラ
インに関するラン・エンド・ポイントのノベツファのア
ドレス。この歴史バッファは２次元処理にのみ用いられ
、各ラインの終った後ＨＰＳＴにはＲＰＳＴが残される
。

ＲＬ・・・ラン長さ、寸法値。

ＲＯＬＤ・・・コード処理済のラインの位置。

殆んどの時、前のランの位置を含んである。

ＤＩＦ・・・歴史ラインの（ＨＯ）端と今のライン（Ｒ
Ｏ）の端との間のベルの数。

ＴＰ・・・テーブル・ポインタ。ＲＬのコード化時、正
しいＲ，Ｌテーブルの上端を指示する。解帯時は、その
時のテーブル入力値を示す。

ＮＸＴＴＰ・・・次のテーブル・ポインタで。

反対の色のＲＬ子テーブルスタート点を貯えている。

ＴＯ・・・ＴＰで示されたバイト値。

０ＦＦＳＥＴ・・・ＴＰで示されたＲＬ子テーブル始点
と反対色のＲＬ子テーブル始点との間の相対距離。この
値はＴＰに基いて、ＲＬ子テーブル沿って貯えられる。

若し白のＲＬ子テーブル最初にメモリにあれば、ＴＰが
白のテーブルを示した時０ＦＦＳＥＴが正で、黒のテー
ブルなら負である。

ＨＩＣＯＤＥ・・・６４の倍数のＲＬのコード・テーブ
ル。各コード・ワードの低位８ビツトが貯えられる（他
の先行するビットは、若しあれ（よ、ゼロである）。コ
ード・ワードのビットの数ｔｔコード・ワードからの固
定オフセットに貯えら１＋、る。

このテーブルはＴＰによりアドレスされ、黒と白で別の
テーブルがある。

Ｌ　ＯＣＯＤ　Ｅ・・・ＲＬがＯ〜６３のコード・テー
ブル。各コード・ワードの低位８ビツトカ１貯えられ、
これに先行するビットが若しあれｉｆゼロであり、各コ
ート・ワードのビット数がそのコード・ワードの固定オ
フセットに入れられる。ＴＰによりアドレスされる。テ
ーブルは白のＲＬと黒のＲＬで別にある。

ＢＩＴＩＭ・・・次の入力されるラインが、ＲＰＳＴに
より指示されてるノ（ツファに変化位置（ラン・エンド
）のリストとして、既（二乗てしすることを示すフラグ
。従って、デコーダの出力は、ラスター・スキャン・ビ
ット像を作らなし）で、（別のアルゴリズム、オプショ
ンのセット、又番マサブセクションにより）直接、再コ
ード化できる。

ＥＴＯＰＰＡＤ・・・入力ラインを圧縮する前に圧縮さ
れた像にパッドするブランク・ラインの数。

ＥＢＯＴＰＡＤ・・・像の下部で圧縮されるべきブラン
ク・ラインの数。

ＥＹＳＫＩＰ・・・コード化前にスキップする入力ライ
ンの数。

ＰＡＤＣＬＲ・・・ブランク・ライン、及び左と右のパ
ッドで、白（０）でも黒は）でもよし）。

ＥＶＳＣＡＬＥ・・・タテ（垂直）倍率。コード化時、
ラインのスキップをしてタテ方向に解像度の太き（高）
いファクシミリ像を低い像に変換できる。

ＬＬ・・・ライン長さ。圧縮すべきライン当りのベルの
数。

ＣＮＵＭ・・・レジスタＲ内の有効ビットのコード化さ
れたビットの数６ Ｒ・・・圧縮ビットの組立に用いられるレジスタ。

ＲＵＮ２・・・２次元処理時、ランの１番目がなされて
いるか、２番目がなされているかを示すフラグ。

ＲＬＥＮ（ベースＲＰ　Ｓ　Ｔ）　・・・Ｔ＜、　Ｐ　
Ｓ　Ｔ中のアドレスからスタートするバッファで用いら
れるバイト数で、バッファの初めの２バイトに貯えられ
ている。

圧縮データはビットの連続した流れと考えられる。しか
し、実施例のコード化／解帯方式では、この流れをいく
つかのバッファに分ける。例えば、ディスク内の圧縮フ
ァイルの記録、伝送線で送るべきデータのブロックであ
る。演算上の利便のため、実施例ではバッファを半ワー
ド（２バイト単位）に分割する。

コード化処理はビットの流れにビットを追加する。ビッ
トの流れは次のように制御される６最も近い時にコード
化された０〜１５ビツトが３２ビツト・レジスタＲに貯
えられる。カウンタＣＮＵＭが常にＲ中のコード・ビッ
トの数を与える。只の内容を左にシフトし、Ｒの下位ビ
ットに新しいビットを加え又は、ＯＲＬ、て入れられる
ことにより、コードの流れにビットを加えることができ
る。

ＣＮＵＭを加えたビットの数だけ増加させる。若し、こ
のあとで、Ｒ中に１２ピツ１へ以上あれば、上位の１６
コード・ビットがメモリ中のバッファに入れられ、Ｒ中
のビット数のカウンタが１６減らされる。コード化方式
中では長さ］３ピッ１−をこえるコード・ワードはない
から、この方法で、貯蔵前にＲからシフトして出るデー
タのないことが保証される。

実施例では、コードの上位１６ビツトがＲからコード・
バッファに入れられる。これは、Ｒを左に３２・ＣＮＵ
ＭＮ０Ｍピッフトして、Ｒ中で上位ビットが最高位ビッ
ト（ＭＳＢ）から始まるようにしてから、Ｒの３２ビッ
ト全部をバッファに入れ、その後Ｒを３２・ＣＮＵＭビ
ット右に戻して行われる。貯蔵された下位１６ビツトは
次のメモリ動作で書込みをうける。バッファに最後の半
ワードを貯える時、Ｒのコピーが作られ、ＣＮＵＭ１６
でけ右にシフトされ、結果の下位半分が貯えられ、バッ
ファの終端をこえて書込みすることを防ぐ。カウンタが
書込むべきバッファ中の次の半ワードを覚えていて、バ
ッファの終りに来たら。

これを送り出しくディスクに書いたり、伝送線で送った
り）、新しいバッファ（同じものかもしれないが）を得
て、これに圧縮されたデータの追加すべき半ワードを書
込む。

［コード化動作の始業」 始業は下記の如く行なわれ、これはコード化する各像に
ついて１回だけである。

擬似的に全部白のラインと全部黒のラインを作る。

白ブラング・ラインを示すラン・エンド・ポイント・バ
ッファ入力を作り貯える。これは下記の形をしている。

１６　０　０　０　ＬＬ　ＬＬ　ＬＬ　ＬＬＬＬはライ
ン長さ。

黒ブランク・ラインを示す同様入力を作り貯える。下記
の形をとる。

１６　０　０　０　０　ＬＬ　ＬＬ　ＬＬＥＴＯＰＰＡ
ＤとＥＢＯＴＰＡＤが非ゼロの場合に、これらバッファ
がブランク・ライン・エンド・ポイントとして用いられ
る。

最初のラインが２次元でコード化され、そのために白ブ
ラング・ラインを歴史ラインとして必要な際に、）（Ｐ
ＳＴが白ブラング・ライン・ラン・バッファの最初の白
ライン（第１のＬＬ）を指示するよう始動される。

ＣＮＵＭが始動のためゼロにされる。この時、圧縮デー
タを管理する他の始業手順も行われる。

ＭＨ，ＦＬＡＧＩＤ、ＢＩＴＩＭ、ＶＳＣＡＬＥ等の他
の変数が所望のオプションを得るようオペレータにより
制御される。１次元及び２次元のＣＣＩＴＴ標準の両方
が最初のラインを１次元でコード化することを要求して
おり、若しＣＣＩＴＴ標準を選択していたら、ＦＬＡＧ
！Ｄを初めに１にしなければならない。

「バド・ライン」 ＥＴＯＰＰＡＤが正なら、像の上方で余分のブランク・
ラインをコード化する必要がある。先ずＰＡＤＣＬＲに
従って、ＲＰＳＴを黒か白のどちらかのブランク・ライ
ンにセットする。次にこの余分のラインの各々について
、ラン・エンドからラインをコード化するサブルーチン
をコールしなければならない。

「スキップ・ライン」 若しＥＹＳＫＩＰが正なら入力像ラインのうち適当な本
数スキップする。

［１ラインのコード化のループ」 主コード化手順ループは１本のラインを扱う。

先ず、コート化すべき他のラインがあるかどうかを調ら
べ、なければ、ループからの脱出が起る。

他のラインの有無のラストは種々の方法でできる。

その１つは、所要の入力ラインの数をカウンタにプリセ
ットし、処理する毎に減算し、カウンタがゼロになった
時に入力ライン処理を終止するものである。

タテ方向の倍率パラメータＥＶＳＣＡＬＥは、これが１
より大であれば、入力ラインの一部をスキップし、タテ
方向で原画より解像度の落ちたココード化がなされる。

ここではラインを当初からスキップするものとして示し
ているが、こうでなくてもよい。

入力画像はラスター・スキャン像であることが多い。若
しそうであれば、１つのラインがラン・エン、ド表示に
変更される必要がある。ピッ１−・マツプ表示をラン表
示に変換する方法は既に知られている。他方、入力像は
既にラン・エンドポイント形式の多数のラインの形であ
ることもある。デコーダがその一例である。この場合、
］又は２次元の方式と他の方式との間の変換は容易であ
るが、それはラスター像への変換とその戻しが不要だが
らである。

ラン・エンド信号は１ライン毎にそのランの終りにコー
ド化される。

（キー１）　［コード化］ 第２．１図から第２．５図迄にこの処理を記載する。

「パド・ライン」 ＥＢＯＴＰＡＤがオンであれば、入力ラインの所定本数
の処理の後に、余分のラインがバドとして入れられる。

ＥＴＯＰＰＡ、Ｄで用いられた所定の像のブランク・ラ
インを指示する同様の処理が像の終りで用いられる。Ｅ
ＢＯＴＰＡＤは、この点で、計算さオル、固定サイズの
像を維持する。

ライン全部が処理された後、このプロセスから出る前に
６ＥＯＬのＲＥＴＵＲＮ　Ｔｏ　Ｃ０ＮＴＲ０Ｌ順序が
コード化される。

「１ライン・コード化の手順」 第２０．１図から第２．５図は、ラン・エンド・ポイン
ト表示から１ラインをコード化する順序を示す。

第２．１図はデータのコード化の前に要る始業手順を示
す。次のラインを１次元で処理するか、２次元で処理す
るかをきめる、いくつかの選択基準が用いられる。２次
元標準では、少なくともに本のライン毎に１次元のライ
ンを１本コード化する必要があり、このＫは定数であり
、ＣＣＩＴＴ標準では２又は４である。

１次元の場合、ＥＯＬコードが先ずコード化される。修
正ハフマン方式なら、このビット・パターンはｒｏｏｏ
ｏｏｏｏｏｏｏｏｌ」であり、他の方式ならｒｏｏｏｏ
ｏｏｏｏｏｏｏｌｌＪである。コード化されるべき、第
１のラン・エンド（ＲＥ）を指示するＲＰがセットされ
る。ＴＰがセットされ、白のランの対するＲＬコード・
テーブルを指示する。次にコード化するランのＲＬはラ
インの最初のラン・エンド（ＲＥ）の値をとる。

ＦＬＡＧＩＤは１にセットされ、今のラインは１次元で
コード化されるでいることを示す。制御はループに−移
り、ここでＲＬコード化手順によってランの中のコード
化がなされる。

ラインが２次元方式でコード化される際は、ＥＯＬコー
ドはオプションとなる。フラグがテストされ、コード化
すべきか否がを決める。エラーのない状況では、ＥＯＬ
コードを省略するのが望ましい。しかし多くの場合（Ｃ
ＣＩＴＴ標準でのコード化、１次元から２次元への変換
の時、圧縮ライン崩り最ホ限の数のビットが保持される
必要ある時等）ＥＯＬコードが２次元コード化されたう
インに先行する。ＥＯＬをコード化する際には。

ビット・パターンはｒｏｏｏｏｏｏｏｏｏｏｏｉＯｊで
ある。ＲＰはコート化すべき最初のラン・エンド（ＲＥ
）を示すようセットされ、ＨＰは歴史ラインを示すラン
・エンド・バンファ内の最初のラン・エンドを示すよう
セラ１〜される。ＲＯＬＤは０にセットされ、ＦＬＡＧ
ＩＤは０にセットされ、今のラインが２次元処理されて
いることを示す。制御は次に、タテ関連コードがＲＬコ
ードを用いてランをコード化するループに入る。

第２．２図は２次元方式での内部ループを示す。

このループは、コード化中のラン・エンドと歴史バッフ
ァ中のラン・エンドとの差（Ｄ　Ｉ　Ｆ）を算出する。

このＤＩＦがゼロであればタテ関連０（ＶＯに対し２進
コード１）がコード化され、歴史バッファ・ポインタは
増加され、歴史バッファ中の次のラン・エンドを示すよ
うになる。この点で、次のランをコード化するために使
われるＨＰで示されている歴史バッファ中のランは、こ
の時コード化されたランの終りの右に来ているように保
証される。今コード化したラン・エンドがコード化した
ラインの右端にあるか否かテストし、若しそうなら全ラ
インのコート化が済みライン・コード化手順からの脱出
が起る。

他の場合は、今コート化したラン・エンドがＲＯＬＤと
して残され、ラン・エンド・ポインタが更新され、次の
コード化するランを示し、処理の反覆をする。

主ループには３ケ所から入れる。始業直後に点Ａから、
２次元方式で一対のランをＲＬコード化した後、及びＰ
ＡＳＳモードのコード化をした後である。他の入り地点
は非ゼロ・タテ関連がコード化された後である。これら
の場合、ＲＥポインタは未だ最後のコード化されたラン
を指示している。ＤＩＦの計算の前に更新されねばなら
ない。

コード化したランが歴史ランの右で終っていれば、右端
に達したかのテストの前に、点Ｃからループに入る。若
しコード化したランが歴史ランの左で終れば、右端に達
してないことはたしかで（コード化するラインは歴史ラ
インと同長だから）、右端かどうかのテストはスキップ
して、点Ｂでループに入る。

像の右端に達したら、制御がコード化手順（第１図）の
主ループに戻る直前に、今コード化したラインのＲＥバ
ッファの始めを示しているポインタ（ＲＰ　Ｓ　Ｔ）が
ＨＰＳＴにコピーされ、そのため、若し次のラインが２
次元でコード化される際には、歴史ラインとして使える
ようにする。ループから出る他の手順はすべてＨＰＳＴ
を更新する。

若し、主ループで計算されたＤＩＦの値が非ゼロ値であ
れば、他のタテ関連又はＰＡＤＳＳコードが発生される
かをテストする。この手順が第２゜３図に示されている
。

又若し、ＤＩＦがゼロよりも小さい値だったら（即ち、
その時のＲＥが歴史ＲＥの左にある）、タテ左関連をコ
ード化するかをテストする。若し今のランが歴史ライン
の１ベル左で終っていたら。

タテ左関連１（ＶＬＩについてビット・パターン０１０
）をコード化し、ＨＰを加算し、歴史ライン中の次のラ
ンを指示させるが、これはこれが今コード化したＲＥの
右にある、反対側の色の最初の歴史ＲＥの筈だからであ
る。最後のＲＥ　（ライン長）の全文のコピーが各ライ
ンにあることは、右端に達したあとでもＨＰ内に使える
歴史データがあることを保証する。制御は主ループに戻
る。

今のＲＥが歴史ラインの左側２又は３ペルの所で終った
ら、タテ左関連２又は３（ＶＢ２及びＶＢ２について各
々００００１０及び０００００１０のビット・パターン
）をコード化する。前の歴史ランが今のランの終りより
右で終っている場合に備えて、歴史ポインタがバック・
アップされる。

今のランがこの場合に相当するかのテストがされ。

そうでなければ、ＨＰが加算され同色の次のランを指示
する。制御は主ループに戻る。タテ関連コードが発生で
きなかったら、コードのＲＬ部分を入れて１対のランを
コード化する。

若しＤＩＦがゼロより大であれば、そのランはタテ右関
連又はＰ’ＡＳＳを用いてコード化できる。

ランが歴史ランの１ベル右で終ったら、タテ右関連１　
（ＶＲＩに０ＩＩ）をコード化し、ＨＰを加算し次の歴
史ランに合わせる。この歴史ランの終りは今のランの終
りより左にはない。たしかにＲＥの右にあるかのテスト
をする必要がある。若し右でなかったら、ＨＰが再び増
加される。制御は主ループに戻る。

若し、ＶＲＩがコード化されていないと、今のＲＥがＨ
２、の右か調べる。若し、そうなら、ＰＡＳＳ　（ｏｏ
ｏｌ）をコード化しエンド・ポイントＨ２をＲＯＬＤと
して貯え、ＨＰを今のランと同色の次の歴史ランのＲＥ
に合わせ、制御を主ループに戻す。

若し、ＶＲｌかＰＡＳＳのどちらもコード化できなかっ
たら、今のランが歴史ランの２か３ペル右で終るのかテ
ストする。若しそうなら、タテ右関連（ＶＨ２に０００
０１１、又はＶＨ２に０００００１１）をコード化する
と共に、ＨＰを次の歴史ランを示すように進める。これ
が今コード化したＲＥの右にあるかテストする。右でな
いと、ＨＰが加算され、新しいＨＯをテストされる。若
し、まだ右でないと、又ＨＰを加算する。制御は主ルー
プに戻る。

若しタテ関連コードがコード化できないと、ＲＬココ一
部分を用いて、１対のＲＬコード化をする。

第２．４図はＲＬのコード化を示す。この手順には、２
つの入口から入れる。ラインの一次元コード化の始業直
後（点Ｙ）、又は２次元処理の］部でそれがタテ関連コ
ード化を試みそのコード化が適当でない時（点Ｘ）であ
る。

若しＲＬ方式コード化に、２次元処理から入るといくつ
かの始業が必要になる。ＲＬ方式を用いて１対のランを
コード化していることを示す前記号（ＲＬプリフィクス
に２進コード００１）がコード化される。次にＴＰを最
初にコード化するランの色のＲＬ子テーブル示すように
セットする。

この色はＲＰとＲＰＳＴとの差と、それが４の倍数であ
るかによって決められる。ＲＥデータ処理が始まる前に
はＲＥバッファには４つの入力値があるから、そして各
入力は２バイトを要するから、白のＲＥは８．１２．１
６・・・のオフセットでＲＥバッファに貯えられ、黒の
ＲＥは１０．１４１８・・・のオフセットで貯えられる
。そこで、ＲＰ−ＲＰＳＴが４の倍数であれば、ＴＰが
白のテーブルを示すようセットされ、そうでなければ黒
のテーブルを示すようセットされる。ＴＰのセットの後
、フラグ（ＲＵＮ２）がＯにセットされ、１対のランの
第１番目がコード化されていることを示ずようにされ、
このランのＲＬが、今のＲＥとＲＯＬＤ（前のランの終
りか又はＰＡＳＳモードを用いてコード化した位置が入
っている）の値との差から算出される。

始業処理（若しあれば）の後、ＲＬがコード化される。

第２．５図がこれを示す。ＲＬコード化の後更新作業と
、更にＲＬコード化をするかについての判定が必要であ
る。

先ずＦ　ＬＡＧ　Ｉ　Ｄがテストされ、ラインを１次元
でコード化するか見る。そうであれば、コード化された
前のランのＲＥをテストし像ラインの右端に達したか見
る６若しそうなら、全ライン・コード化済みであり、ラ
イン・コード化から脱出する。そうでなければ、ＴＰを
反対色（次にコード化するランの）のＲＬ子テーブルセ
ットし、今コード化したＲＥを貯え、ＲＥポインタを増
加し、次のランのＲＥを示すようにし、ＲＬを新旧ＲＥ
の差として計算する。制御は、新しいＲＬをコード化す
るループの上端に行く。

若し、今のラインが２次元コード化されているなら、フ
ラグＲＵＮ２がテストされ、今コード化したランが１番
目か２番目か見る。第１なら、Ｒしてコード化する別の
ランがある。第２のランの時にＲＵＮ２が１にセットさ
れており、１次元の時と同じセット・アップ手順が遂行
される。ＴＰが反対色のＲＬ子テーブル示すようセット
され、今コード化したＲＥが残され、ＲＥポインタが加
算され次にコード化するランのＲＥを示し、新旧ＲＥの
差から、コード化するＲＬが算出される。

制御は新しいＲＬコード化ループの上端に行く。

若し、今のラインが２次元処理中であって、２番目のラ
ンをコード化したところであれば、ＲＯをテストしライ
ンの右端に来たかをみる。来ていれば、ライン・コード
化手順から出る。そうでなければ、歴史ポインタを更新
する。これは既に正しい色のランを示しているので、こ
れを更新することは、ＨＰが示す歴史ランのＲＥが今コ
ード化したランの終りより右にあるかテストすることに
なる。若しそうでなけｈば、ＨＰが加算され同色の次の
歴史ＲＥを示し、そのＲＥがテストされるこの処理が、
コード化済のＲＥの右に歴史ＲＥが見付かる追及覆さｊ
ｂる。ツー１〜化されるランのＲＥは右端よりは左だし
、結局は右端にある歴史ＲＥに出合う筈だから、上記の
ような歴史ＲＥが存在することは保証されている。次に
２次元コード化主ループに戻る。

第２．５図はＲＥコードを示す。ＲＬはゼロ又はそれ以
上の数の「メイク・アップ」コード（６４の倍数、但し
２５６０以下をコード化）と１個の終了コード（残りビ
ットＯ〜６３の数）からなっている。ＲＬはコード・ワ
ードに対応する値の合計である。そこで、５１５０のラ
ンのＲＬは２５６０＋２５６０＋３０にコード化され、
４００ＯのＲＬは２５６０＋１４０８＋３２で、２００
０のＲＬは１９８４＋１６で、１０のＲＬは１０の終了
コードのみでコード化される。

ＲＬコード化ループは、先ずＲＬが６４より小であるか
を見る。若しそうなら、適正な終了コードＬＯＣＯＤＥ
　（ＲＬ）をコード化して終る。又、そうでなければ、
ＲＬが２５６０より大であるかを見る。若しそうなら、
２５６ｏの「メイク・アップ」コード（０００００００
１１１１１）がコード化され、ＲＬ値から２５６０減算
し、ループの上端に戻る。又、ＲＬが２５６０より大で
なければ、６４で割り（これは右シフトで行なう）、「
メイク・アップ」コードのテーブル（ＨＩＣＯＤＥ）を
見るために使う値を得る。コード化した後、割算の残り
が前のＲＬの値と入れ替る。これはＲＬの値のうち「メ
イク・アップ」コードを指示するために使われた部分を
マスクすることにより行なわれる。制御はループの上端
に戻り、残余のコード化をする。

（キー２）「解読（デコード）」 本発明の方式でコード化された圧縮ディジタル像のデコ
ード手順が第３図、第４．１図から第４゜６図により説
明される。下記のリストが迅速なデコードをする本発明
の特徴を挙げている。

（１）ハフマン可変長コード・ワードの急速直列デコー
ドに簡単なテーブルを用いている。中間節は圧縮データ
流での次の０（１）ビットに関する次の節迄の相対距離
を示している。他の色の感知は、テーブルの次の入口と
して次の節を持っている。負の入力は終了節にフラグし
、見付けたコード・ワードについての情報を有する。修
正ノ）フマン方式のテーブルでは若しＯについてブラン
チが行われれば、テーブル中の次の節迄の相対距離は７
８をこえることはなく、２２１の入力が用いられてもバ
イト・テーブルで十分である。

（２）　同一のレジスタが圧縮されたビットを逐次見る
ことと、すべてのビットが検査された時点の追跡とに用
いられる。データが更に必要かのテストは、（１）の圧
縮ビットが発見された時にのみ必要で、それはこのビッ
トがデータの終りを示すマーカ・ビットでありうるから
である。特別の場合にだけレジスタの残余がゼロになる
。

（３）　タテ関連コードは、インライン・コードにより
デコードされ、そのためプログラムの位置が発見された
コード・ワードを示す。ポインタを歴史データ・バッフ
ァの更新は最小限のテストでなされる。ＲＥバッファは
右左の端で、３つ迄のランを前方又は後方に見る場合で
も正しい情報を与えるよう構成されている。

（４）色変化の位置からビット・マツプを作るのに急速
コードが用いられる。

（５）３つの算法処理をデコードするのに１つのサブル
ーチンが用いられ、余分の負担は殆んどない。これは、
オブジェクト・コードの寸法を小さくする。

（６）内部ループで必要な可変数の殆んどは、レジスタ
に保持できる。

「デコードの全般」 像ラインをデコードする手順は基本的に２ステツプでな
される。

第１に、サブルーチンで各ラインがＲＥ位置のバッファ
内に引伸しされる。２次元デコード時に、歴史ラインを
与える必要があるため、ＲＥバッファは次のラインのデ
コード時迄保持される。ＲＥバッファはコード化器（手
順）の場合と同じ形式である。このため、３つ迄のラン
を前後に見る左右の４″Ｘでも正しい情報が得られる。

これは最初及び最後のランを少なくとも２回余分に複製
することによりなされる。最終ＲＥ値の少なくとも３つ
のコピーがあると、ポインタを２ラン前に進めても有効
なデータをいつでも得られる利点がある。

こうして、デコード時には、相当に少ないテストしか必
要でない。

圧縮データ流は、ＲＥについてデコードする際にのみ、
正しく解読される。そこで、若し像の上端でいくつかの
ラインがスキップされるとすると、これは必要な数のラ
インを無視し終るまでＲＥにデコードするだけで除去で
きる。

第２に、ビット像形式が望まれたら、ＲＥ位置をビット
・マツプに変換できる。

１つのサブルーチンが３つの算法すべてをＲＥバッファ
にデコードするので、オブジェクト・コードの寸法が小
さくなる。これら３つの算法はすべてＥ−ＯＬとそれに
つづく１次元のラインから始まる。そこでデコーダは１
次元ラインを解読できねばならない。ＭＲ算法では、こ
れらラインは各２〜４本毎に起る。２次元コードの時、
００１の水平モード前置コードの後に１次元算法でデコ
ードすべき１対のランが来る。ゼロに対するテストによ
って、１次元コード・ラインを常にＲＬデコード・ルー
プの中に保つように、小数のスイッチがセットされる。

ＭＲＮコードＭＭＲコードとの主な差異は、ＭＲＮコー
ドは各ラインにＥＯＬがあることである。

ＥＯＬは少なくとも１１個のゼロとそのあとの１と、２
次元デコード時にそのあとにつづくタグ・ビットとより
なり、このタグは次のラインの次元を示す。これはグル
ープ■の機械でエラーの伝播を止めるため、各ラインの
終りに必要である。各ランの終りで圧縮像の右端をチェ
ックす九ば、ラインの終りをフラグするのにＥＯＬを必
要とはしない。最初にＥＯＬが検出された時は、同心コ
ードが両方の算法について、ラインのデコードのループ
の再開のため使える。フラグがセットされ、第２のＥＯ
Ｌが次にデコードされる時は、ＲＴＣ手順が認められる
。

［ハフマン可変長コードのデコード・テーブル」ハフマ
ン可変長コード・ワードの直列的デコードのための簡単
なテーブルが容易に作れ、敏速にデコードできる。Ｎコ
ード・ワードについて、Ｎ−１人力が中間節であり、こ
れが０か１の圧縮ビットに関する次の節への相対距離を
示す。他の色の検出は、改めての入力を要しないが、そ
れはその次の節がテーブルへの次の入力だからである。

Ｎ入力は終了節である。これらは、フラグ・ビットによ
り（この実施例では最高位ビット）、中間節と区別でき
る。終了筋入力の残余はコード・ワードに関する情報で
ある。中間節での入力は又、テーブルへの絶対指標にも
なる。

修正ハフマン・テーブルで、若し０でブランチするなら
、２２１の入力があってもバイト・テーブルで十分であ
り、これは８ビツトのマイクロプロセサに適している。

バイト・パターン・テーブル 中間節 ｏｘｘｘｘｘｘｘ　次がＯなら今のポインタにＱＸＸＸ
ＸＸＸＸを加算し次の入力に到達せよ。次が１なら１を
加算し次の入力に到達せよ。

終了節 １０ＸＸＸＸＸＸ　ＲＬ　Ｏ〜６３ １１ＸＸＸ×××　若しＸＸＸＸＸＸ（４１なら、これ
は６３より大なＲＬの高位６ビツトである。

１１１１１１００　１Ｐｋ日宿モード。

１１１１１１０１　不正ビット・パターン１１１１１１
１０　１０個のゼロとこのあとの１じ分ＥＯＬ）１１１
１１１１１　ＥＯＬ（７）１１ゼロ１１ゼロへの入力（
テーブルで２２１番目の入力）は次の節への相対比ｍが
ゼロの中間節に行なわれる。この時、１１個のゼロのあ
とにゼロがいくつあってもこれは新しい入力への移動を
起さない。Ｘ　’ＦＦ’のＥＯＬ終了節が２２２番目の
パイ１〜に移される。不定長で１０個以上のゼロのあと
の最初の１がＥＯＬとして識別される。

これらデコード・テーブルを作製する方法を以下に示す
。

（１）すへてのコード・ワードをこれら終了節に必要な
情報を含むフィールドと共にリストする。

（２）　ヌル（ＮＵＬＬ）コードを含む、これらコード
のすべての前置コードをリストし、中間節であることを
表示する。

（３）増加する２進値順序で揃え、重複を除く。

（４）　中間節テーブル入力を作るため、ブランチする
のに用いられるビットを付加し、長い方のビット・パタ
ーンに合ったものを見付ける。所望のユニットに相対距
離を入れる。

下記の簡単な例では、中間節には１で、終了節にはＴで
フラグする。

元のコード・ワード　節の情報 Ｑ　Ｔ１ １０　Ｔ２ １１１　Ｔ３ １１００　Ｔ４ １１０１　Ｔ５ １でブランチするコードと前置コードとの増加する順で
のテーブル。

コート Ｔ２ ０　Ｔｌ 」−１２ １０ゴ・　２ １１　１４ １１０　工２ １１００　Ｔ４ １１．０１　Ｔ５ １１．１　Ｔ３ 若しＩ／ＴビットがバイトのＭＳＢに変換されたら、最
終のテーブルは２　１２９　２　１．３０　４　２１３
２　１３３　１３１　となる。

バイトは各々、次にデコードするビットが１なら進むへ
き相対距離を示すか、又はデコード結果を与える。ＭＳ
Ｂがデコード手順のかじをとる。

ＭＳＢがゼロなら、デコードをつづけ、次の圧縮ピッ１
〜がゼロの時には次のバイトをスキップし、１ならバイ
ト・テーブル入力に示された数のバイトをスキップする
。デコード完了のフラグはＭＳＢの１へのセットである
。

像をデコードしてメモリに入れる処理を説明する。コー
ド化器での変数に加えて、デコーダは下記の変数を用い
る。

ＤＴＯＰＰＡＤ・・・入力ラインをデコードする前に、
出力像の上端にパドすべきブランク・ラインの数。

ＤＢＯＴＰＡＤ・・・デコード完了後、出力像にパドす
べきブランク・ラインの数。固定寸法の出力像作りに使
える。

ＤＹＳＫＩ　Ｐ・・・出力バッファにラインを出力する
前にスキップすべき入力（圧縮された）ラインの数。

ＤＶＳＣＡＬＥ・・・タテ倍率。低い（タテ方向）解像
度のファクシミリ像を、デコード処理中に複製して高い
（タテ方向）解像度の像にできる。

デコーダで、圧縮データ流について行われる基本動作は
、次のビットが１かゼロか調べることである。実施例で
は、３２ビツトのレジスタＲに０〜１６ビツトの圧縮デ
ータが左側に合わせて入っているように制御している。

これらデータのビットのすぐうしろに１が入っており、
Ｒ中の他のビットはすべてゼロである。次に、Ｒ中の高
位ビット（圧縮された次のビット）をテストする。Ｒを
それ自体と加算する。どれで、Ｒ中の全ビットが１ビツ
ト左にシフトする。

ＩＢＭ（商標）３７０シリーズでは、ＡＤＤ命令により
、Ｒの高位ビット（テスト中のビット）からキャリー／
オーバフローが発生したか及び残りがゼロかを示すコン
ディション・コードがセツトされる。若し、キャリーが
起らなければ、テストされたビットはゼロで、この信号
がデコーダに戻される。オーバフローが発生すれば、圧
縮データの１ビツトか、圧縮データのあとにつけたフラ
グの１ビツトが出て来たことになる。Ｒを調らべれば、
このどちらであるか判る。Ｒが非ゼロであれば、フラグ
はまだＲの中にあり、１は圧縮データだったわけで、こ
の情報がデコーダに戻される。

若しＲがゼロなら、出て来たのはフラグの１ビツトであ
る。この場合、圧縮データの他のバイト即ち半ワードを
更によむ必要がある。Ｒの中に左に寄せて入れる。下位
にはゼロをつめる。データのあとにフラグの１ビツトを
入れる。ビットのテストをして、結果をデコーダに戻す
。次によむべき半ワードについてカウンタが順序を制御
している。

バッファが空になったら、受信機等の信号源にデータを
要求する。

ＩＢＭ３７０シリーズ以外の機械では、レジスタＲが負
であるかどうかを調らべ１次にＲにそれ自体の内容を加
算することによりＭＳＢ（最高位ビット）をテストでき
る。Ｒが０であって、フラグの１ビツトだけの場合をテ
ストするには、負の信号路のみが必要とされる。

修正ハフマンＲＬをデコードする場合に、新しく圧縮ビ
ット（全部ゼロではない）１６個、圧縮データ・レジス
タに入れられると、そのコード・ワードの残りに関して
、有効データの終りのテストは必要がない。最も長いコ
ードは１３ビツトで、但しＥＯＬへのＦＩＬＬ動作でつ
められる余分のゼロは別である。そこで、新しいビット
が全部ゼロでない限り、このコードの終りがマーク・ビ
ットの来る前に来ることが保証される。

更にタテ関連コードをデコードする際、新しいデータが
レジスタに入るとそこに８個の有効ビットがあることが
保証されており、これはＥＯＬの最初の８ゼロを含めて
すべてのタテ関連コードをデコードするのに必要な最大
数である。この場合には有効データのチェックをしない
別の経路を後続させることができる。

第３図に本発明におけるデコード方式を示す。

「デコードの始業」 デコードすべき像毎に始業処理が１回行われる。

これはコード化器の場合の始業に似ている。

人工的に全部内と全部黒のラインを作る。実際のライン
の長さが判っていなければ、ＬＬがＸ’ＦＦＦＦ’　に
セットされ、最初の一次元ラインがデコートさ」ｔた後
にブランク・ラインが再計算され、実際のライン長さを
決める。

白のブランク・ラインを表示するＲＥポイント・バッフ
ァが決められ貯えられる。下記の順序を有する。

１６　０　０　０　ＬＬ　ＬＬ　ＬＬ　ＬＬＬＬはライ
ン長さである。

黒のブランク・ラインを示すＲＥポイント・バッファが
作られ貯えられる。これは下記の順序を有する。

１６　０　０　０　０　ＬＬ　ＬＬ　ＬＬこれらバッフ
ァが、ＤＴＯＰＰＡＤとＤＢＯＴＰＡＤが非ゼロである
時に、ブランク・ライン・エンド・ポイントとして用い
られる。

像の最初のラインが２次元デコードされ、白のブランク
歴史ラインを利用する際には、白ブランク・ライン・ラ
ン・バッファの最初の白ラン（第１のＬＬ）を指示する
ようにＨＰＳＴが始動する。

圧縮データを１ビツトづつ検査するために使うレジスタ
にＸ　’８０００００００’　を入れる。これにより、
最初に読まれる圧縮データについてビットのテストを起
させる。

他のデータ、即ちＭＨ，ＢＩＴＩＭ、ＶＳＣＡＬＥ等が
オペレータにより、所望の値に選定される。Ｆ　ＬＡＧ
　Ｉ　Ｄは普通、圧縮データの先頭のＥＯＬによってセ
ットされる。若しセットされていなければ、セットしな
ければならない。

「スキップ・ライン」 ＤＹＳＫＩＰが正であれば、適当な数の圧縮ラインがＲ
Ｅにデコードされ、その後除去されねばならない。

「パド・ライン」 若しＤＴＯＰＰＡＤが正であれば、像の上方に余分のブ
ランク・ラインを発生する必要がある。

最初のラインは常に１次元デコードされ、これにＥＯＬ
コードがつづくから、ライン当りのビット数は最初のラ
インのデコードの終りに判る。ラインのスキップがなく
、余分のラインのパドが必要なら、出力像の寸法を事前
にセットする必要がある（これは１ラインだけデコード
して元のライン寸法を知ってから、処理を再開すること
によってできる）。

ブランク・ラインを発生させるため、ＲＰ　Ｓ　ＴがＰ
ＡＤＣＬＲに従って、黒か白のブランク・ラインにセッ
トされる。若し像のＲＥ表示が望まれるなら、１６バイ
トが必要な数コピーされ出力バッファに入れられる。そ
うでなければ、ＲＥからビットへの変換手順が、第１の
ブランク・ラインの変換に適用され、結果のビット像ラ
インが必要な数コピーされる。

［１ライン・デコード・ループ」 主デコード・ループが１本のラインをデコードする。先
ず、デコードする追加のラインがあるかテストする。若
しなければ、ループから出る。これは、圧縮データ流が
処理されなくなった時、列（ＲＯＷ）内でのいくつかの
ＥＯＬの制御順序の戻りがあった場合、又は要求された
数の出力ラインがデコード済の時に起る。

１本のラインをＲＥにデコードする手順が第４゜１図か
ら第４．６図を用いて説明される。

ビット表示像が必要な時にはＲＥ表示をビットのラスタ
ー・スキャン形式に変換する。この方法は既知である。

又、出力像をＲＥポイント形式での多数のラインの形の
ままにしておくこともある。

この表示だと容易に再コード化ができる。又、これは１
次元と２次元の算法の間の変換や他のオプションを容易
にするが、それはラスター像形式との間の変換を必要と
しないからである。

ｒＤＢＯＴＰＡＤＪ 所定数の圧縮ラインのデコード後、若しＤＢＯＴＰＡＤ
が正であれば、余白のラインをパドする。

Ｄ　Ｔ　ＯＰ　Ｐ　Ａ　Ｄの時用いた所望の色のブラン
ク・ラインを指示するのと同じ処理が、像のあとで用い
られる。この時点で、一定の像寸法に保持するためにＤ
ＢＯＴＰＡＤの計算がなされる。

「ライン・デコード手順」 第４．１図がデコード時の始業を示す。ＲＰＳＴはＲＥ
バッファが作られる時の場所を示しているものと想定さ
れる。長さを入れる半ワードにつづく３つの半ワードは
ゼロにされる。ＲＰはリセットされ、最初にデコードさ
れたＲＥが貯えられる場所を示す、最後のランＲＯＬＤ
はゼロで始動する。

ＦＬＡＧＩＤがテストされ、次のラインが１次元と２次
元のどちらでコード化されていると予想されるかをみる
。（若し、圧縮コードが次にＥＯＬコードを持っていれ
ば、同じ結果を得るどちらかの経路が選ばれる）若しＦ
ＬＡＧＩＤが（１）で１次元を示したら、ＴＰが白ラン
のＲＬデコード・テーブルを指示するようセットされ、
ＮＸＴＴＰが黒ランのＲＬデコード・テーブルをセット
するようセットされる。制御はループに戻り、ここでＲ
Ｌデコード手順によってランのデコードがなされる。

ラインを２次元デコードする際は、ＨＰが歴史ラインを
持つＲＥバッファの中の最初のＲＥを指示するようにセ
ットされる。次に２次元方式でランをデコードするルー
プに戻る。

第４．２図は２次元方式の内部ループを示す。

このループで次の圧縮データ・ビットを調らべる。

若し、このビットが１なら、タテ関連０　（ＶＯ）がデ
コードされたことになる。歴史ＲＥがＲＯＬＤに貯えら
れ、歴史バッファ・ポインタが増加され、歴史ライン中
の次のＲＥを指示する。デコードしたＲＥがラインの右
端にあったか否かテストされ、若しそうならライン全部
がデコード完了でこの手順からの脱出が起る。そうでな
ければＲＯＬＤを今デコードしたＲＥのまま残し、ＲＥ
ポインタを増加し次にデコードするランに合せ、処理を
反覆する。

主ループには３ケ所から入れる。点Ａからは、始業直後
、２次元デコードで１対のランをＲＬデコードした後、
又はＰＡＳＳモードのデコードの後に入る。他の入口は
、非ゼロのタテ関連がデコ−ドされた際に用いられる。

これらの場合、デコードされた最後のＲＥがＲＯＬＤに
入っている。

これをＲＯに貯えて、ＲＰを次のビットのテスト前に更
新する必要がある。デコードされたランが歴史ランの右
で終っていたら、右端に達したかのテストの前に点Ｃか
らループに入る。デコードしたランが歴史ランの左で終
っていたら（デコード中のラインは歴史ラインと同じ長
さの筈だから）右端に達していないことは明らかで、右
端のテストはスキップしてＢ点からループに入る。

像の右端に達したら、デコーダ（第３図）の主ループに
戻る直前に今デコードしたラインのＲＥバッファの始め
を示すポインタ（ＲＰ　Ｓ　Ｔ）がＨＰＳＴにコピーさ
れ、このラインを若し次のラインが２次元デコードされ
る際に歴史ラインとして使えるようにする。ラインをデ
コードするための他のループ脱出もすべてＨＰＳＴを勇
断する。最ｔ１　（右端）のＲＥの別のコピーがこの時
点でＲＥバッファに入れられる。ＲＥバッファ中の７１
イト数は選択的にＲＬＥＮに貯えられ、半ワードはＲＰ
ＳＴによって指示される。

主ループにおけるビットのテストが非ゼロを示せば、コ
ード・ワードを識別するため他のビットがテストされる
。この手順がタテ関連コードに関して第４．３図、ＰＡ
ＳＳコードに関して第４゜４図に示されている。コード
・ワード全体が見付かる迄ビットは連続して調入られる
。

ＶＬＩがデコードされる時、ＲＯＬＤが歴史ＲＥの１ビ
ツト左にセットされる。歴史ポインタが（ＶＬＩのコー
ド化の時のように）くり上げられ、制御は主ループに戻
る。

ＶＲＩがデコードされる時、ＲＯＬＤは歴史ＲＥの１ピ
ツ１〜右にセットされる。歴史ポインタが次の歴史ラン
を示すようにくり上げられる。この歴史ＲＥは、今デコ
ードしたランの終りの左には来ない。これがＲＥの右に
在るかのテストが必要である。若し右でなかったら、Ｈ
Ｐが再び増加される。制御は主ループに戻る。

ＲＬ前置コードがデコードされる際は、コード化器で説
明したと同様の手順で、正しいカラー・デコード・テー
ブルを示すようにテーブル・ポインタがセットされる。

反対色のために、ＲＬデコード・テーブルにＮＸＴＴＰ
がセットされる。フラグ（ＲＵＮ’″）がゼロにセット
され、１対のランのうちの第１のランがデコードされて
し）ることを示す。制御はＲＬテコ−１手順でランをデ
コードするループに移す。

ＰＡＳＳ　（’０００１’　）をデコードする際には、
エンド・ポイントＦｌ　２をＲＯＬＤとして貯え、歴史
ポインタを今デコードしているランと同色の次の歴史エ
ンド・ポイントを示すようにセットし。

主ループに戻る。

第４．４図はタテ関連デコード手順のつづきを示す。

若し残っている４つのタテ関連コード（ＶＬ２、ＶＬ３
、ＶＲ２、ＶＲ３）＋７１うちの１つがデコードされる
際とは、ＲＯＬＤはＨＯに対し正い１関係になるよう計
算され、ＨＰはコード化の際と同じ方法で更新される。

制御は主ループに戻る。

’００００００１’のビット・パターンは２次元コード
拡張の前置コードである６−次元デコードの際の同じ拡
張のパターンは’ｏｏｏｏｏｏ。

０１′である。’００００００１’の経路のテーブル・
ポインタは、１次元デコーダが拡張前置コードを処理し
終って到達するであろう点にセラ１−され、制御はＲ′
Ｌデコード・ループに移る。

’ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ’のビット・パターンは
ＥＯＬコードを発生ずるものと予期される。０００ｏｏ
ｏｏ’の経路のテーブル・ポインタは、１次元デコーダ
がこれら７つのゼロを処理したら到達したと考えられる
点にセットされ、制御はＲＬデコード・ループに行く。

第４．５図はＲＬデコード手順を示す。この手順には、
ラインの１次元デコードの始業の直後。

ＲＬ前置コードのデコードの後、拡張への前置コードの
デコード後、又はＥＯＬの最初の７個のゼロをデコード
した後に、点Ｙから入る。

このループはＲＬをデコードすることで始まる。

第４．６図に詳細を示す。若しラインの始めにＥＯＬが
デコードされると、始業手順（第４．１図）中に点Ｚに
制御が戻る。又若しラインの終りでＥＯＬがデコードさ
れると、ライン・デコーダからの脱出が起る。そうでな
い場合には、ＲＬがデコードされた後、ＲＯＬＤがＲＬ
によって加算されている筈である。何らかの更新が必要
で、別のＲＬをデコードするか否かの判定がされねばな
らない。

このラインが１次元デコードされているかを知るために
、Ｆ　ＬＡＧ　Ｉ　Ｄがテストされる。若しそうなら、
デコートされた最後のランのＲＥがテストされ像ライン
の右端に来たかをみて、若しそうなら、ラインのデコー
ドは完了で、ライン・デコードから脱出する。若しそう
でなかったら、ＴＰを反対色（次のデコードするラン）
のＲＬ子テーブルセットし、ＲＯＬＤ中のＲＥをＲＯに
貯え、ＲＥポインタを次の（不使用の）ＲＥバッファ位
置を示すよう加算する。制御は新しく、ＲＬをデコード
すべくループの上端に行く。

若し今ラインのデコードが２次元でされていたら、Ｒｔ
ＪＮ２がテストされ、１本目か２本目かをみる。、１本
目だったのなら２本目のランがＲＬでデコードされねば
ならない。２本目であることを示すようＲＵＮ２が１に
セットされ、］次元コード化の時と同じ準備手順が用い
られる。ＴＰが反対色のＲＬテーブルを示すようセット
され、ＲＯＬＤ中のＲＥ′ＩＪ′ＸＲＯに貯えられ、Ｒ
Ｅバッファの次の（不使用の）空間を示すようＲＥポイ
ンタがくり上げられる。新しいＲＬのデコードをするル
ープの上端に制御が移る。

若し今のラインが２次元デコード中で、今終ったランが
２本目だったら、ＲＯＬＤをテストしラインの右端に来
たかをみる。来ていれば、ライン・デコーダから出る。

未だなら、歴史ポインタを更新する。これは既に正しい
色のランを示していたから、更新することはＨＰで示さ
れた歴史ＲＥが今デコードしたランの終りの右にあるか
テストすることになる。若し右でなければ、ＨＰが増さ
れ同色で次の歴史ＲＥを示し、このＲＥがテストされる
。デコードされたランの終りの右に歴史ＲＥが見付かる
までこれがくりかえされる。今デコードの終ったランは
右端の左にあったし、結局は右端にある歴史ＲＥにぶつ
かる筈だから、上記の歴史ＲＥは見（寸かる筈である。

次に、制御は２次元デコードの主ループに戻る。

第４，６図はＲＬデコードの手順を示す。ビットは１つ
毎にテストされる。次のビットが′１′であれば１次の
入力を示すようＴＰが加算される。

次の入力（ＴＯ）がＸ　’８０’　より小さければ、未
だコード全体が見付かってはいなく、制御はループの上
端に戻り、次のビットをテストする。テストしたビット
が１０　Ｔであれば入力値（Ｔｏ）がＴＰに加えられ、
既にデコードされたビットから始まるコードのコード・
テーブルの枝に（サブトリー）移し、ループを反覆する
。

若しどちらかの経路で、入力がＸ　’８０’　より小で
なければ、コード・ワード全体がデコード済である。若
し入力の最高位桁の次の桁のビットがゼロであれば、終
了コードがデコードされた。このコードで示される像ビ
ットの数が、テーブル入力の下位６ビツトから得られＲ
ＯＬＤに加えられる。この点で−ＲＬのデコードが完了
する。ゼロでなければ、ＴＯがＸ’Ｅ８’　より大きい
かテストされる。大きくなければ、「メイク・アップ」
コードがデコードさ九た。このコードで示される像ビッ
トの数がテーブル入力の下位６ビツトに６４をかけて（
これは左シフトできる）得られ、ＲＯＬＤに加算される
。ＴＰは同色ＲＬ子テーブル上端を示すようにセットさ
れねばかｒない。これはＴＰをＮＸＴＴＰにセットし、
オフセットに加算し、元のテーブルに戻ることによって
なされる。

制御はループの上端に戻り、別の「メイク・アップ」又
は終了コード・ワードをデコードする。

若し、テーブル入力がＸ’Ｅ８’　より大きいとＥＯＬ
がデコードされたことになる。修正ハフマン方式が用い
られていないと、タグ・ビットをデコードしＦＬＡＧＩ
Ｄをセットし吹のラインが１次元、２次元のどちらでコ
ード化されているか示さなければならない。次にＲＯＬ
Ｄがテストされ、ラインの始め又は終りにＥＯＬが見付
かったか否かがみられる。終りにあれば、ライン・デコ
ード手順からの脱出が起る。始めなら、制御は第４゜１
図始業手順の点２に戻る。

この説明においては圧縮データには無効なコード・ワー
ドはなく、コード化器では非圧縮モードは使オ〕なかっ
たものとした。Ｘ　’Ｅ８’　より大きいテーブル入力
をすべてＥＯＬに解釈しないで、Ｘ’Ｅｘ’でフラグさ
れた無効コードの検出に適当なテスト及びエラー処理手
順を実行できる。又、若し、非圧縮モード拡張Ｘ’Ｆｘ
’　が発見されたら、非圧縮モートのコード・ワードの
デコードにこの手順を拡張できる。

［発明の効果コ 本発明の方式によりコード化及びデコード処理の速さが
高速化し、データ処理システムや回線の使用時間が減少
するとともにこれら装置の使用能率が向上する。

【図面の簡単な説明】

第」１図は本発明のコード化方式のフロー図、第２．１
図はライン・コード化手順始業フロー図、第２．２図は
ライン・コード化内部ループ・フロー図、第２．３図は
タテ関連コード化フロー図、第２．４図はＲＬコート化
ラフロー図第２．５図は１本のＲＬコード化フロー図、
第３図はデコーダ・フロー図、第４．１図はライン・デ
コーダ始業フロー図、第４．２図はライン・デコーダ内
部ループ・フロー図、第４．３図はタテ関連デコード・
フロー（１）図、第４．４図はタテ関連デコード・フロ
ー（２）図、第４．５図はＲＬデコート・フロー図、第
４．６図は１本のＲＬデコード・フロー図である。 出願人　インターナショナル・ビジネス・マシーンズ・
コーポレーション 代理人　弁理士　山　本　仁　朗 （外１名） ＲＬフード化ラフロー１本） 第２．５図 デコーダ・フロー図 ライン・テパコーダ協業 第４．１図 第１頁の続き ［相］発明者　ジエラルド・ゴーツエ　アメル　ノマロ リカ合衆国ニューヨーク州ホワイト・プレーンズ、スー
・サークル７番地

Claims (1)

1. 【特許請求の範囲】 複数個の信号ディジタル・データ・ビットを含むデータ
   ・ラインを反覆的に多数含むデータ信号であって相続く
   ラインの中のビット値の間に関連性のあるデータ信号を
   コード化及び解号する方式相続く上記ラインに含まれて
   いるビット値を比較し、 関連性を検出した際に関連コード・ワードを発生し、 関連性を検出しなかった際は共通のビット値をもつデー
   タ・ビット列についてテーブル・ルックアップによって
   ラン・コード・ワードを発生し、ラン・コード・ワード
   中のデータ・ビットの数を示すデータを上記ラン・コー
   ド・ワードに対応するテーブル入力値から予定の値オフ
   セットした位置に貯え、 上記発生された関連コード・ワードとラン・コード・ワ
   ードを合計してコード化データ流を作り、上記コード化
   データ流を伝送し、 伝送されて来た上記関連コード・ワードについては上記
   予定の関連性に従って解号し、上記ラン・コード・ワー
   ドについては上記テーブル・ルックアップにより共通の
   ビット値のビット列を解号し上記解号したデータ・ビッ
   トを予定の関係で再配置してデータ信号を復元すること
   、からなるコード化及び解帯方式。