JPS60196014A - データ圧縮・転送・圧縮解除装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、特にデータの圧縮または圧縮解除を行うだ
めの装置に関し、データの送信側と受信側とがともに次
の動作を動的に且つ同時に行なうような装置に関する。

：　、 （１）適応予測計算の制御、 （１１）データソースとデータの宛先とで同時に与見ら
れたデータストリームをあられす予測の、２進的に決定
された対称的な列を用意すること、０ｉｌ）　決定０・
・・・ｎ−１のそれぞれに対して最適化された累積予測
経過に基づき２進的な決定１・・・・ｎに対して、デー
タソースとデータの宛先とて個別に且つ対称的に圧縮及
び圧縮解除の予測を計算すること。

この発明は、ビットを送ることを強制されるよシもむし
ろ２進的な決定を適応的にコーディングすることによシ
実施される。ｎ番目の決定のコーディングに使用される
統計はｎ−１番目の決定寸でに更新されたソースモデル
及び宛先モデルによって対称的に実行される適応処理の
一部であるので、転送されるデータのタイプに拘束され
ることなく最適なコーディングが達成される。

この発明に基づき転送されるすべての情報は、転送のた
めに圧縮さ力、る。この際、何らかの確率情報を送ると
いうオーバーヘッドを必要としない。何となれば、予測
される確率は、適応技術を用いることにより、ソースと
宛先とで対称的に削算されるからである。

速度上の理由により、ある環境においては確率情報の更
新を遅らせることが有利である。この遅延は続けて何度
も起こる事象の処理に有用である。そして、カウンタを
更新することは確率を更新することよりも何倍も安価で
済むので、コーダーがより高速で作動することになる。

圧縮された全データストｌ）−人の長さは、１６ビノト
精度で作動するような比較的小型のデータプロセッサに
おいてすら、エントロピー予測に近づく。

〔従来技術〕

従来、データ圧縮に関しては数多くの知識が開示されて
いる。それは、有史以前のコード化されたうなり声に始
壕シ、単一ドツトのモールスコードを経て現代のデータ
伝達技術における、精密化された予測に基づく走行長（
ｒｕｎ−１ｅｎｇｔｈ）コードに至るものである。例え
ば英語におけるモールスコードなどのように、データス
トリームの統計が周知である場合に、良好にはたらく実
際的なシステムを含む、データ圧縮の重要な知識ベース
が存在する。

あるモデルに従うデータ圧縮及び圧縮解除のシステムは
周知である。このモデルは現在のチータグループに対す
る予測モードを規定する。

そして、予６１１］による非常に大きなデータ圧縮を行
うことができる。例えば、メツセージの第１ビツトを、
標準コートで継続すべきかあるいけ暗号に変換すべきか
という承認された問い合わせに対する応答とするこ七が
できる。そのような環境においては単一のビットに含丑
れる情報量は膨大である。壕だ、類似データの継続が生
じる確率に基づく複雑な予惣モデルも周知である。例え
ば、影像においては、白スペースの予測さｉた継続の一
致及びその一致回数を定めることにより白スペースの広
い一様な領域をわずか数ビットで識別できる。しかし、
白スペースが黒スペースと出会う端部を検知するとすぐ
に、起こり得るべき情況を予測するための多数のビット
と、個別の予測を受け入れるための多数のビットか必要
となる。この予測モードではソースと宛先どで一致が必
要であり、それにょシ圧縮されたノーステータが宛先で
正常に圧縮解除さ、ｆｌ、ることが可能となる。

ソースと宛先とでのコード選択モデルが正しく一致して
いる限り、ソースでのデータ圧縮とダ［ｉ先でのデータ
圧縮解除を継続することができる。ｆｌｌ　エバモール
スコードのノースとモールスコードの宛先ではドツトが
文字パｅ＃である点で一致している。しかし、多様な特
性を有する大量のデータに対しては、コード選択を不変
にしておくことは最適ではない。むしろ、今寸での経鍋
の知識に基づいて次のチータグループを予測し時々刻々
とコードを変更することが、コード選択を最適化する上
できわめて有用である。

そのようなコード選択は転送されるデータグループ毎に
動的に変更されるが、しかし、頻繁にコード選択を変更
するために如］、ソースがコードを変更しつつあること
を宛先に知らせる必要があることから、相当に多用のデ
ータ転送を行う必要がある。例えば、いくつかの予測コ
ードでは、予測精度（予測された値から選択するために
必要なビット数）が周期的に転送される。

ＩＥＥＥトランスインフォセオリ（’Ｆｒ　ａ　ｎ　５
Ｉｎｆｏ　Ｔｈｅｏｒｙ）丁Ｔ−２５、Ｎｌ’１．６．
６７２（１９７９）に掲載の、Ｆ　、　ルピン（Ｆ、Ｒ
ｕｂｉｎ）の論文には固定精度レジスタを用いた算術ス
トリームコーディング処理が記載されている。この論文
に記載の構成によれば、有限精度レジスタ中の複数の重
要ビットが一度に１ビツトずつ調整される。これによれ
ば最大精度を保つことができるけれども、コンピュータ
中で時間を浪費してし捷う。

〔発明が解決しようとする問題点〕

この発明の目的は、データストリーム中のデータの動的
な経過に対して圧縮及び拡張アルゴリズムを継続的に適
用することにより最適なデータ圧縮を行うとともに、こ
の継続的に適用された圧縮及び拡張アルゴリズムを対称
的な適応圧縮捷たは適応拡張により実行することにある
。

この発明のさらに固有の目的は、予測計算というオーバ
ーヘッドを伴うことなく圧縮データを転送することによ
シ、時間または距離に亘る転送データを圧縮し、またけ
圧縮解除することにある。

〔問題点を解決するだめの手段〕

この発明によれば、ソースと宛先とで対称的に、適応的
に且つ同時的に予測＝−ｔ　Ｘが行なわれる。この結果
として、データグループｎ　−１までで正確な圧縮モデ
ルの更新に基づき、転送されたすべての情報が圧縮きれ
る。

この発明の１つの特徴−ば、（例えば文字の余白におけ
る連続する白スペースのような）予測の均一性によシ予
測モードの干渉を行うことが許容され、動的なベース上
で実際のデータ転送を要求するよシもむしろ、圧縮の大
＋１＠な増加によシ反復カウントとして転送されるよう
なデータ列の間は予測情報を別個に処理することにある
。

この発明の他の特徴は、予測列を（２を乗じるか２で割
るかして）シフトすることにより簡単に処理することに
ある。この簡単な処理によシ、時間のかかる掛は算や、
さらに一層時間のかかる割シ算を行わなくともよくなる
。

この発明の利点は、エントロピーの限界に達するような
比較的小さいデータプロセッサに対しても、データ圧縮
能力を与えることができることにある。このことにより
、膨大な量のデータを、かなりのレベルの精度で回復で
きるように転送することができる。１だ、それよりも少
ない量のデータについては完壁な精度で転送することが
できる。

〔実施例〕

この発明は、モード変更ビットのオーバーヘッドが比較
的小さいようなシステムに特に適用される。

データソースとデータの宛先での対称的なモデル予測発
生装置は同一のデータストリーム、すなわちデータグル
ープ（１・ｎ−１、ｎ）のうち１つの夕１月二で同時に
作動する。その際に転送データはチータグループ１　・
ｎ−１に適応的に７ｆＭ　ｉｊ化された確率に基づき圧
縮さね、る。現在のチータグループ１１はソースから宛
先へ転送を行うために圧縮されるのである。データグル
ープの同一の列（１・・・・ｎ−１、ｎ）はソースと宛
先とに同時に与えられる（宛先ではデータグループが圧
縮されている）。ソースと宛先はともに、それらのモデ
ルに基づき、与えられた列に対して最適化された確率モ
ードに対称的に適合する。

このときモード変更ビットを転送するというオーバーヘ
ッドは必要でない。実際のモード変更はソースと宛先と
で個別に計算さ７またモードの定義により定められる。

この、個別の月つ対称的な適応モード割算能力における
投資Ｑま、データ転送の膨大なコスト、殊にメガバイト
を要するような影像データについて考えあわせたとき、
その大きなデータ圧縮能力の供力ゆえに十分利得の大き
い投資であると言うことができる。また、転送能力が速
度または容＃において制限さｔｌ、でいるような状況に
おいては転送コストが用務的なコストを上廻ることもあ
ろう。しかしながら、この分散した対称的な適応モード
ｇ１貌能力に投資することにより、従来転送／ステムの
能力を超乏−でいたようなある種のデータ転送が６丁能
、となるのである。

この発明は、例えばＩＢＭＳ／１またはＰＣ１あるいは
そね−らの機能的に同一な１６ビツト（２バイト）の並
列データ上で作動するような小型機上で実行されるよう
に役割された実用的なコーディング及びデコーディング
アルゴリズムとして実施される。そして前述した関連文
献→ユ→のものよけ異なり、コードストリームピットの
シフトは一度に１個ずつ行なわれるのではなくで、算術
処理の１バイトに等しい８ビット単位として行なわれる
。このことによりソフトウェア中できわめて高速の実行
が可能となる。丑だ、有限精度算術処理から生じてくる
キャリー及びオーバフロー処理の問題はバイトがンフト
アウトシたときのみ必要となるにすきない。さらに確率
割算の詳細が含−ｆ；７１でいる。というのは、それら
のフォーマットがコーダー及びデコーダーの統合的な部
分であり、そｔゆえに注意深く処理されなくてｄ、なら
ないからである。このアルゴリズムはグレースケールデ
ータ圧縮に有用である。このアルゴリズムはまた遠隔会
議システムにも有用である。この有用性とけすなわち、
データ圧縮がなされないかあるいは従来の技術を用いて
データ圧縮したまうな」５．合にグロセソザやコミュニ
ケーションンステムの容量を飽和させてし脣うようなデ
ータの転送能力を高めることにある。

ここではコーディングスキームは１６ビツト精度で記述
されている。寸だ、６２ビット精度への拡張も示されて
いる。

そのアルゴリズムは第１〜１６図中に記載されている。

第１図に、圧縮及び圧縮解除システムの機能的なブロッ
ク図である。第１図において、入力ＤＡＴＡＩＮはユー
ザーによって供鳥されたモデルに基づく状態発生装置１
によって（ＢＩＴであられされる）２進決定の列に変換
される。

個別の２進決定に対して状態発生装置１は丑／こ、適用
確率発生装置２とコーダー６とに固有の状態信号を供給
する。適応確率発生装置２は、状態信号がもつ状態デー
タを、ＢＩＴがゼロになる確率Ｐをもとめるために使用
する。一方、コーダーはＢＩＴの値と状態信号の情報を
用いて、ｌよパ 圧縮データストリームを発生する。例えが第１図ではこ
のデータストｌ）−ムは８ビット単位で送出される。尚
、概念的にはそのビット単位はコーディング動作の精度
とコンパチブルな任意のサイズでさってもよい。しかし
、１６ピツトマシン」−で実現されるコープインゲンス
テムには特に８ビツトが好適である。同様に、３２ビツ
トマ／ンでｄ、１６ビツト単位の圧縮データが適肖であ
る。

圧縮されたデータス）　ｌ）−ムはもとのデータよりも
低コストで記憶または伝達されるように最適に符号化さ
れる。ＤＡＴＡＯＵＴ側には上記状態発生装置１及び適
応確率発生装置２・に対応しそれらと等しい構成をもつ
状態発生装置７゛及び適応確率発生装置６と、上記コー
ダーとは対称的なデコーダー５が設けられている。８ビ
ツトの単位（あるいはコーダー６で使用されたのと同一
のデータグループ）でデコーダー５に入力された圧縮デ
ータから、ＢＩＴの値が決定され、それはＤＡＴＡＯＵ
Ｔを発生するために使用される。

確率Ｐが発生された後は、Ｐの値を更新するためにＢＩ
Ｔの値が使用される。この更新されたＰの値は次回の転
送の際に供給される。２つの適応確率発生装置２．６で
発生され−だ確率は、一つのステップ中では保持される
４、というのは、確率はコーダー３またはデコーダー５
に供給される後までは更新が行なわれることＩｒｉ、ｉ
いからである。

コードストリームは、大きさがコード化されたすべての
ＢＩＴの確率の積であるような数直線上の区間内にある
実数をあられずものと考えることができる。コードスト
リームの長さはＢＩＴの列を個別に識別するのに十分で
ある。

第２図は単一のＢＩＴのコーディングを］ン１示するも
のである。ｎ番目のＢＩＴがコード化される前に、コー
ドストリーム（４，それ以前にコード化きれた事象を記
述する実数Ｆ　（ｎ−１）　を識別する。Ｆ（ｎ−１）
は既に実行されたコードストリームによってあられされ
る数が存在する区間の下限である。この区間の大きさは
それ以前にコード化された事象の確率の積であり、Ｒ（
ｎ−１）と称することにする。ｎ番目のＢＩＴをコード
化するだめにはＲ（ｎ−１）の幅が２つの部分に分割さ
れる。その２つの部分の幅は、それぞれｎ番目のＢＩＴ
がゼロである場合と１″である場合との確率に比例する
。もしＢＩＴがゼロであるなら、新しい幅Ｒ（ｎ）はＲ
（ｎ−１）ＸＰ（古い幅と、ＢＩＴがゼロである確率と
の積）となり、区間の下限は不変である。また、ＢＩＴ
が°゛１″であるなら、新たな区間Ｆ（ｎ）の下限はＦ
（ｎ−１）＋Ｒ（ｎ−１）ｘｐにセットされ、従ってそ
の下限はＢＩＴがゼロである場合に割あ　。

てられた区間よシも上方にあり、新たな幅Ｒ（ｎ）はＲ
（ｎ−１）ｘ（１−Ｐ）　（古い幅と、ＢＩＴがパ１″
である確率との積）である。

第６図は１つのＢＩＴのコーディング及びデコーディン
グをあられす図である。尚、この第６図及び第５．６図
では次の変数が使用される：Ｒ：　許容された幅 Ｆ　：　（第２．３図のみ）−圧縮されたすべてのデー
タ （他のすべての図）−圧縮されたデ ータ上の有限精度の窓 Ｐ　：　１３ＩＴがゼロである確率 Ｔ　：　５ＲＬ（ＲＸＰ）１５の計算結果を保持するた
めの仮変数 ｐ、＋：５ＲＬｐ’ｉの計算結果を保持するための仮変
数 コーディング処理は先ずＲＸＰＯ値（ＢＩＴがゼロであ
る場合の区間の大きさ）を計算し、Ｔとして保持してお
くことから始まる。次にＢＩＴが判断され、ＢＩＴがゼ
ロであれば、保持されだ値Ｔが新しい幅となり、区間の
下限は変化しない。まだＢＩＴが°゛１″であれば、区
間の下限が保持されだ値Ｔだけ増加されて、幅は保持さ
れた値Ｔの分だけ減少される（すなわち、Ｒ（ｎ）はＲ
（ｎ−１）−Ｒ（ｎ−１）ＸＰにセットされるが、それ
はＲ（ｎ−１）Ｘ（Ｉ　Ｐ）に等しい）。

一方デコーディング処理もＲＸＰを計算し、それをＴと
して保持しておくことから始まる。

次に、コード化された値Ｆ（それは、コード化された実
数から現在の幅の下限を引いものである）が、Ｔよりも
小さいかどうかが判断される。

そしてＦ（Ｔであれば、ＢＩＴコードがゼロになり、幅
ＲはＴで置きかえられる。′−！、−たＦ≧Ｔであれば
、コードストリームによってあられされた数はＢＩＴの
値がパ１″である区間に収まらなければならない。それ
ゆえ幅ＲはＴだけ引か、れる。Ｆの値も放棄された区間
の大きさだけ減少されなくてはならず、こうしてコーダ
ー中で行なわれたのとは逆の演算が行なわれる。

適応確率発生装置 第４図は第１図中で２個図示した適応確率発生装置２．
６を記述するだめのフローチャートである。適応確率発
生装置２、乙の機能は状態信号とＢＩＴからＢＩＴがゼ
ロである確率をめ、そのあとＢＩＴの値を判断し、゛そ
の判断した値を用いて以下の計算の基礎情報（統計）を
適応的に更新することにある。コーダー６中には、状態
信号とＢＩＴとが同時に到着する。デコーダー５中では
、状態信号は確率Ｐを発生するために使用され、このＰ
はＢＩＴをデコードするために使用され、そして次にＢ
ＩＴは統計を更新する際に使用するために適応確率発生
装置に送られＺ。

適応確率発生装置は状態情報により６つのモードのうち
の任意のモードで作動することができる。このとき状態
信号がゼロであることは、ＢＩＴのゼロ値が発生する回
数につき計数値が保たれているような特殊な場合として
認識される。その際、統計は、ＢＩＴの°“１″値が生
じるまで更新されない（従ってＢＩＴがゼロであ′る確
率は変化しない、）。その時点で実行される更新動作は
第７図に関連してより詳細に説明される。このゼロ状態
は続々と多数回発生する事象を処理するために有用であ
る。そして、カウンタを更新することは、確率゛を更新
するために必要な掛算処理よりも安価であるので、コー
ダー６はより高速に作動することになる。

別の特殊な場合はＢＩＴがゼロである確率が０５に固定
されている状態である。この状態では、卸持する必要の
ある統計がないので、何の処理も行う必要がない。

第ろのモードでは、各確率計算の後に更新される統計か
ら確率が発生される。このとき統計と確率Ｐとを更新す
るために使用される処理は第８．９図のフローチャート
に関連して詳細に説明さｔする。１ コーダー 第５図はコーダー６の動作のフローチャートである。こ
のユニットは状態イ菖号と、ＢＩＴと、ＩＩ　Ｉ　Ｔが
セロである確率Ｐとを人力して、ＢＩＴのコート化を１
−■う。第５図において、Ｒ（１２８がどうかが先ず判
断される。もしそうであ７１−ば、積ＲＸ　Ｐを正確に
コード化するに十分な有効ビットがないかもしれない、
ということであり、従ってＦから圧縮されたデータスト
リームへ１単位の出力を移動させる。この機能を行うた
めのバイトアウト処理は、より多くのデータのコーディ
ングを行なうことができるように幅を拡げる（バイトア
ウトは第１０図のフローチャートに関連してより詳細に
記述される）。

次にＢＩＴがコード化される。もし状態信号が、確率Ｐ
が０５に固定されていないことを示すなら、第６図に示
したコーター６中で記述された計算が実行される。この
とき、積ＲＸＰの最も上位の部分として仮の値Ｔが割算
される。

この値は、もしＢＩＴがゼロであれば新しい幅となる。

捷だ、ＢＩＴが゛置″であれは、幅ＲばＴたけ減少され
て、ＦにはＴが加えられる。

もし状態が、確率が０５に固定されていることを示すな
ら、掛は算処理はソフト処理で置きかえられ、新しいＲ
がＢＩＴの各値につき同一となる。このときＢＩＴが１
″であれば、ＦをＲだけ増加しさえすればよい。

デコーダー 第６図はデコーダー５の動作を示すフローチャートＣあ
る。このユニットは状態信号と、ＢＩＴがセロである確
率Ｐとを入力して、ＢＴＴのデコードを行う。第６図に
おいて、先ずＲ〈１２８が判断される。そして、Ｒ＜１
２８であれば積Ｒ×Ｐ中には正確にデコードするために
十分な有効ビットがないということだから、圧縮された
データストｌ）−ムからデータの一単位を取り出してそ
れをＦに加える必要がある。この機能を行うバイトイン
処理は、より多くのデータのテコ−ティングを行うこと
ができるように、幅を増加させる。（）＜イトイン処理
は第１１図のフローチャートに関連してより詳細に記述
される。） 次にＢＩＴがデコードされる。もし状態が、僅率Ｐが０
５に固定されていないことを示すならば、第ろ図のデコ
ーダー５中に記述された割算が行なわれる。仮の値Ｔは
積ＲＸ　Ｔ−）の最上位部分としてδ−１算される。こ
のときＦの下位ビットはコーダーろと対称的であるため
に計勢に用いられてはならない。従って、下位１ビツト
をシフトアウトさせた仮の値Ｆ１が使用さｆ］る３゜次
に、ＢＩＴがゼロが１”かを判断するためにＦｌがＴに
比較される。そしてＩ’ＭＴがゼロであるならＴが新し
７い幅となる。寸だ、ＢＩＴが°１〃であるなら、幅Ｒ
はＴたけ減少されてＦは、１ビツトだけ左方にシフトさ
れたＴの値の分だけ減少される。

もし状態が、確率Ｐが０５に固定されていることを示す
ならば、掛は算がシフトによって首き換えられ、新しい
幅ＲはＢＩＴの各値につき同一となる。このときにも仮
の値Ｆ１が計算されて、ＢＩＴの値を判断するためにそ
のＦｌがＴと比較される。そして、もしＢＩＴが°゛１
″であれば、もとの区間の下位部分を放棄するためにＦ
が減少される。

統計の更新処理 第７〜９図は、適応確率発生装置中で統計を更新するだ
めに第４図中で使用されている手続を記述するフローチ
ャートである。これらの計α中で使用されているいくつ
かの変数についてはこれから説明する。

確率は、現在の状態においてＢＩＴ＝０が生じた回数を
、現在の状態が生じた全回数で割った商の値を計算する
ことにより得られる。しかし、割り算はコストがかかる
ので、割シ算を行うかわりに、状態が生じた回数の逆数
を与える索引テーブルを用いることで置きかえる。との
パ逆数″テーブルは１２８ノ・−７ワード（２バイト）
エントリからなる。その各エントリはＸ′７ＦＦＰ′／
Ｍであられされ、Ｍはエントリの数である。もし状態が
１２５回以上発生するならば、索引テーブルが使用でき
るように状態の発生回数を十分小さい値に保つために統
計が再規格化される。索引テーブルの第１のテーブルエ
ントリはＭ＝１に対応するものであり、これは決して使
用されることがない。

゛逆数″テーブルのエントリ全体は次の表Ｉのとおりで
ある： 表 Ｄ　３２７６７　１６３８ろ　１０９二５４６１　４６
８１　４０９３　３６ノ７７３０　２５２０　２３４０
　２１）１８２０　１７２４　１６３８　１５〈１３６
５　１３１０　１２６０　１２’１０９２　１０５７　
１０２３　９！ ９１０　８８５　８６２　Ｆｉノ ア８０　７６’）　７４４　７： ６Ｂ２　６６８　．６５５　６゜ ６０６　５９５　５８５　５． ５４６　３５７　５２８　５： ４９６　４８９　４８１　４． ４５５　４、’１８　４４２　４ｉ ４２０　４１４　４０９　４＋ ３９０　３８５　３８１　、　３． ３６４　３６０　３５６　３！ ３４１　３３７　３３４　３． ３２１　３１８　３１５　３ ３０３　’３００　２９７　２’ ２８７　２８４　２８２　２１ ２７３　２１’［Ｉ　２６８　２＋ ２６０　２５８ ’２　８１９１　６５５３ １０　３２７６　２９７Ｆ１ １４　２０４７　１９２７ ｉ０　１４８９　１４２４ ３　１１７０　１１２９ ＋２　９／＋３　９ろ６ １０　８１９　７９９ ンＦｌ　７１２　６９７ １２　６６０　６１８ ’４　５６４　５５５ ’０　５１１　５０４ ’４　４６８　４６１ ｉ６　４３１　４２５ １４　３９９　３９４ ’６　３７２　６６８ ｉ２　３４８　３４４ ｉ０　６２７　３２４ １２　３０９、　３０６ １５　２９２　２８９ １０　２７７　２７５ ：６　２６４　２６２ 確率を」豹［７＃計を更新するための仙の少数としては
次の本のがある： Ｄ　：　確率Ｐの計算の際に分母として使用さｈる全計
数値。

Ｎ　：　６１を生Ｐの計算の際に分子として使用される
ＢＩＴ＝ｌ’ｌの回数。

Ｉｐ：Ｔ、Ｊｌ在のＤの幼をあられす、”逆数″テーブ
ル中の伜に対するポインタ。“ 逆数８テーブルはハーフワードテーブ ルであるから、Ｄが”１″たけ増加す る毎にＩＰけ２だけ増加する。

ＩＤ：　ＩＰによって指定される２バイトの値。それは
Ｘ′７ＦＦＦ′／２×Ｄと あられさ第１る。

ＩＰＳＴ：　”逆数′テーブルのアドレス。

ＩＥ：　”逆数８テーブル中の＃後の（Ｄ＝１２８）エ
ントリ。

ＣＴ：　Ｎ及びＤ　Ｋ−）だ含まれていないＢＩＴ＝０
０回初。

第７図ｕ、ＣＡＬＣＰＯ処岬をあられすものである。す
なわち、ＣＡＬＣＰＯ処理では、ＢＩＴがゼロのときに
単一コーディングステップに対する統計が更新される。

現在の状態の発生回数はＩＰを”２′だけ増加させるこ
とによって、先ず１″だけ増加される。次に、”逆数″
テーブルの最終点に達したかどうかが判断され−る。そ
して、もしそうであれば統計を再規格化する必要がある
。この再規格化は、テーブルポインタＩＰを“逆数″テ
ーブルの中点にセットし、ＢＩＴ＝００発生回数（Ｎ）
を右に”１″だけシフトさせることによシ行なわれる。

この再規格化の結果Ｎの値が６３になった々らげ、増加
したＮの値はＮ＝Ｄをみたすことになろう、するとＢＩ
Ｔがゼロである確率は“１″と計算されてしまう。そこ
で、これを避けるため、Ｄを増加させるべ（ＩＰに”２
″だけ加算する。

これで再規格化処理は終了となる。そして、新しい確率
Ｐを計算するためには、Ｂ　Ｉ　Ｔ＝Ｏの一回の発生の
たびにＮを“１″だけ加算する。

こうして、新しい確率ＰはＮｘｒＤ（Ｎ／Ｄに等しい）
として計算される。

第８図は、ＢＩＴ＝１のときに単一コーディングステッ
プに対する統計を更新するためのＣＡＬＣＰ１処理を記
述するフローチャートである。現在の状態の発生回数は
ＩＰを”２＃だけ増加させることによって、先ず”１″
だけ増加される。次に、”逆数８テーブルの最終点に達
したかどうかが判断さｔする。そして、もしそうであれ
ば統計を再規格化する必要がある。この再却格化は、テ
ーブルポインタＩＰを”逆数″テーブルの中点にセット
し、ＢＩＴ＝０の発生回数（Ｎ）を右に“１″だけシフ
トさせることにより行なわれる。この再知格化の結果Ｎ
の備が０になったならは、ＢＩＴ＝０の確率はゼロと計
博されてし凍う。そこで、これを避けるため、ＮとＤと
をともに“１″だけ増加させる（Ｄに関しては、ＩＰを
２だけ増加させることによって行なわれる）。これで再
規格化処理は終了となる。こうして、新しい確率ＰはＮ
ＸＩＤ（Ｎ／ｎに等しい）として計算される。

第９図は、ＢＩＴ＝１の場合の多重コーディングステッ
プに対する統計を更新するためのＣＡＬＣＰＣＴ処理を
記述するフローチャートである。先ず、現在の状態の発
生回数がＣＴ＋１だけ増加される。このＣＴ＋１は、コ
ード化されるべきＢＩＴ＝１の場合のゼロビットの数に
“１″を加えたものである。現在の状態におけるＢＩＴ
＝０の発生回数はＣＴだけ増加され、次にＣＴはゼロに
リセットされる。次に、再規格化が必要かどうかが判断
される。すなわちＤが１２５よシも大きければ、ＤとＮ
とがともに右に１ピットたけシフトされる。この処理は
、Ｄが最早１２５よシも太きくなくなる１で繰り返され
る。次に、ＮとＤとの薗から計ｑされる確率Ｐがゼロで
も１″でもないことを保証することが必要である。もし
ＤとＮとが等しければ、Ｐ＝１となるのを避けるためＤ
が１だけ増加される。そうではなくてＮがゼロであれば
、ｐ＝ｏと計算されてしまうことを避けるためにＤとＮ
とを”１″だけ増加させる。これで再規格化処理は終了
となる。次にＩＰが、“逆数″テーブルの開始アドレス
上の２ＸＤバイ）Ｋセットされ、新しい確率ＰＪＩ′ｉ
ＮＸ　Ｉ　Ｄ　（Ｎ／Ｄに等しい）として計算される。

第１０図と第１１図とは、圧縮されたデータストリーム
を処理するだめの手続のフローチャートである。この手
続では、次に示す変数が使用される： ＢＰ：　コーディングの間に記憶され、あるいはデコー
ディングの間に使用される 圧縮されたデータの最終バイトへのポ インタ Ｂ　：　ＨＰによって指定されたバイトＢＰＳＴ：圧縮
データバッファ中の最初のノくイトへのポインタ ＢＥ：　圧縮データバッファ中の最終ノくイトへのポイ
ンタ ＩＪＮ：　圧縮データバッファのバイト中の長さ 注）　Ｂ１１ｍ＝ＢＰＳＴ＋ＬＥＮ−１第１０図は、第
５図に示したバイトアウト手続を記述するフローチャー
トである。この手続は、Ｆから圧縮されたデータストリ
ームに１単位のデータをつけ加えて、ＦとＲとを適宜調
整するためにコールされる。

第１０図の手続の第１のステップはＦの高位ピットにキ
ャリーが生じているかどうか（す々わち、１６ピツト精
度ではＦ＞Ｘ’　７ＦＦＦ’であるかでうか）を判断す
ることである。そして、もしそうであれば、圧縮された
データストリーム中に以前に配置されたデータ単位がそ
のキャリーに対して１だけ増加される。また、そのバイ
トがＸ’　ＦＦ’まで増加されていれば、次に示す追加
的な処理が心安である。

キャリーピット（もし存在すれば）が用意された徐に、
データの次のバイトに対する記憶位置にアドレスするた
めにＢＰが増加される。もし、圧縮データバッファの最
終位置に達したならば、そのバッファは”ラインアウト
”と表示した手続によって適宜処理（伝達、記憶など）
さね、ＢＰはそのバッファの開始地点にリセットさね、
これによりそのバッファにはさらに多くのデータを収め
ることが可能となる。次に、１５ビツトの値Ｆの上位８
ビツトが出力用バッファに格納されるとともに、その記
憶されたバイトが値Ｘ’　ＦＦ’をもつならば追加的な
処理が行なわわる。そして、そのキャリーピットと先程
記憶されたピットとは、Ｆからはマスクされ、ＦとＲの
値は、より多くのデータをコード化すべてスペースをあ
けておくためにそれぞれ８ビツトだけ左にシフトされる
。

圧縮されたデータストリーム中のいかなるバイトもＦの
最上以ビット中へのキャリーによってＸ’ＦＦ―からｘ
＋ｏｏ’へ１増分”されないことを保証することが必要
である。というのは、増分されたバイトからのキャリー
は伝播することができないからである。このことを防止
するために１記憶された各バイトについてはその値がＸ
　Ｉ　ＦＦ　＋であるかどうかが判断さｈる。

そして、もしそう表らその圧縮さねたデータストリーム
中には値Ｘ’ＯＯ’をもつ追加的なバイトが配置される
。このバイトは、必要ならば安全に増分することができ
る。圧縮されたデータストリームをそのゼロバイト中に
配置するために、そのバイトが記憶されるべきバイトの
スペースにアドレスするべ（ＢＰが増分される。

もし圧縮データバッファの彫°終点に達したならば、そ
の完了したバッファを送出するためにラインアウトが使
用され、ＢＰがバッファの開始点にリセットされる。次
にＢＰで示される箇所にゼロバイトが記憶きねる。

第１１図は第６図中に示したバイトイン手続のフローチ
ャートである。この手続は、データの一単位を圧縮され
たデータストリームがらＦへ移動させ、ＦとＲとを適宜
調整するためにコールされる。

第１１図において先ず、圧縮されたデータストリーム中
の次のバイトが、キャリー用のスペースを４．ｆるよう
にＸ　Ｉ　ＦＦ　’バイトの次に挿入されたものである
かどうかが判断される。そして、もしそうであれば（す
々わち、もしその前に読み増られたバイトＢがＸｌＦＦ
’であれば）、圧縮きれたデータストリーム中の新しい
バイトにアドレスするためにＢＰが１″だけ増分される
。もし圧縮データノぐツファの最終位置に達したなら、
より多くの圧縮データを得るためにラインイン手続が使
用され、ＢＰが補充されたバッファの開始点にリセット
される。次にキャリーがＦに加えられる。

キャリービット（もし存在するなら）が加入された存・
に、圧縮されたデータの次のノ；イトにアドレスするた
めにＢＰが増分される。もし圧縮データバッファの最終
位１＃−１に達したなら、より多くのデータを得るため
にラインインが使用さｆ＋、ＢＰがバッファの開始点に
リセットされる。次にＦが左に８ビツトシフトされ、圧
縮されたデータの新しいバイトかＦの下位８ビツトとし
て挿入される。Ｒもまた８ピツトだけ左にシフトされる
。

次に示す表■は、コーダー３及びデコーダー５に必要な
初期化について示すものである。

表　■ ＣＴ←Ｏ Ｎ←７ Ｄ　４−Ｎ＋１ １Ｐ←Ｉ　Ｐ　Ｓ　Ｔ十り＋Ｄ Ｐ　４−ＮＸＩＤ Ｎ１３ Ｐ　４−Ｘ１３ＦＦＦＩ ＩＰ←ＩＰＳＴ＋４ 初期化変数 ＩＰＳＴ←゛逆数″テーブルのアドレスＩＥ４−ＩＰＳ
Ｔ＋２５４ Ｂ　Ｐ４−Ｂ　Ｐ　Ｓ　Ｔ Ｂ　Ｐ４−Ｂ　Ｐ　−１ Ｂ　Ｅ　＋−Ｂ　Ｐ　＋　Ｌ　Ｅ　Ｎ コーダーのみ Ｆ　←Ｏ Ｒ＋Ｘ’７ＦＦＦｌ バイトイン バイトイン Ｒ４−Ｘ’７１”ＦＦ’ 状態０統剖に対しては、ＢＩＴ＝Ｏに遭遇した回数がゼ
ロにセットされ、Ｂ　Ｉ　Ｔ＝ＤＣある確率Ｐが７７８
（Ｎ＝７、Ｄ−８）に初期化され、Ｄに対応してＩＰか
セットされる。

頷ヰｒか０５に固定さねていない状態ノンゼロ統削に対
し′Ｃは、ＢＩＴ＝Ｄでを）る確率が初期状態で１／２
（Ｎ＝１、ＩＰ＝ＩＰＳＴ＋４、効率的にはＤ−２）に
セットされる。

セットアツプする必要のあるその他の変数には次のもの
がある： ＋）　゛逆数″テーブルの開始点と終点のアドレス、１
１）圧縮データバッファの開始点と終点のアドレス、１
ｉｉ）　＃初の読み取りバイトより前のバイトを指定す
るＢＰの＃＋。コーダー３の中では、最初のバイトには
キャリーが生じない。イがって、このデータは変更を受
けガい。デコーダーの中では、実のバッファの前のバイ
トが何かのはずみにＸ　Ｉ　ＦＦ　ｌとなってしまわな
いように注意がなされなければならない。コーダーにお
いては、Ｆがゼロにセットされる。デコーダー５におい
ては、初期値の状態のＦ中に２バイトをロードするため
に、バイトインが２回コールされる。どちらの場合にも
幅ＲはＸ“７ＦＦＦ”に初期化され、それば°゛１″を
あられす。

第１２図は、圧縮されたデータストリームに最終バイト
を追加するだめに、コーダー６中で使用される手続をあ
られすものである。この手続はデコーダー５が十分なデ
ータを持つことを保証するために有用である。第１２図
において先ずＳＲＬ　Ｒ１としてＲ／２が計算さね、Ｆ
を現在の幅の中央に耐１置するためにＦがそのＲ／２だ
けｉ？ｆ分される。そして、バイトアウト（第１０図）
が行々われる。次に、次のバイトのためのスペースにア
ドレスすべ（ＢＰが１＃だけ増分される。次にもし圧縮
データバッファの最終点に達すると、そのバッファの処
理を行うためにラインアウトがコールされ、ＢＰがリセ
ットされる。次に値Ｘ’ＦＥＩをもつバイトが出力バッ
ファに格納される。（このとき、Ｘ’ＦＥ’の値は、Ｘ
ＩＦＦＩ以外ならどのような値でも任意に選ぶことがで
きる）。次にＢＰが再び“１″だけ増分され、圧縮デー
タバッファの最終アドレスと比較される。またラインア
ウトがコールされ、必要ならばＢＰがリセットされる。

次に飴Ｘ’ＦＥ’をもつ別のバイトが圧縮されたデータ
ストリーム中に配置される。この圧縮されたデータスト
リームはここで完成され、最終のバッファを処理するた
ｄ）にラインアウトがコールされる。

次に示す表■け、初期化調整のいくつかの値を示す簡単
な表である。尚、この初期化潤整け１６ビツ）Ｍ度のか
わりに３２ビット精度で行うようにしてもよい。

表　■ 理　論　１６ビツト　６２ビツト ＦＤ　’Ｏ Ｒ１＝１００％２　−１＝Ｘ・７ＦＦＦ’・２”１−１
＝Ｘ・７Ｆ’ＦＦＦＦＦＦ・５ 逆数（Ｉ）１／Ｉ　Ｘ’７ＦＦＦ’／Ｉ　Ｘ１７ＦＦＦ
ＦＦＦ’ＦＩ／Ｉ尚、上述の実施例ではチータグループ
としてバイト毎に処理されているが、より大きなシステ
ムでは；それに対応してより大きなデータグープを処理
するのが好適であることを理解されたい。

〔発明の効架］ Ｊ、Ｊ上のように、この発明によねげ、データのソース
と卵先々で対称的に、月つ同時的に予測網銹を行うよう
にしたので、確率データを送る必臂がなくなり、データ
の圧縮、転送、圧縮解除に吸する時間を知縮できる、と
いう効果がある。

４図面の節即々欣明 舶：１図は圧縮及び圧縮解除システムの機能的なブロッ
ク図、 第２図は本発明に係るデータ圧縮及び圧縮解除システム
の理論を曲間するための図、第６図は１つのＢＩＴをコ
ーディング及びコーディングするための手続のフローチ
ャート、第４図は適応確率発生装置６における手続をあ
られすフローチャート、 第５図に”コーダーにおける手続をあられすフローチャ
ート、 第６図はデコーダーにおける手わ「をあられす７０チヤ
ート、 第７図けＦＩＩＴがゼロのときに単一コーディングステ
ップに対ｊ７て統計の更新処理を行うためのフローチャ
ート、 第８図はＢＩＴがパ１″のときに単一コーディングステ
ップに対して統計の更新処理を行うためのフローチャー
ト、 第９図はＢＩＴが“１″のときは多ｌ゛コーディングス
テップに対して統計の更新処理を行うためのフローチャ
ート、 第１０図はバイトアウト手続のフローチャート、 第１１図はバイトイン手続のフロチャート、第１２図は
圧縮されたデータストリームに最終バイトを追加するた
めに、コーダー中で使用される手続のフローチャートで
ある。１．２．６・・・・データ圧縮手段、５．６．７
・・・・データ圧粋解除手段。

才　２　図 オ　４　図 矛　１０　図 オ　１１　ロ オ　１２　目

Claims (1)

1. 【特許請求の範囲】 各々複数のビットからなるｎ−１個（ｎＦｉ正の整数）
   のデータグループから、適応予想モデルを用いてｎ番目
   のデータグループの発生確率を計算し、該確率に適合す
   る圧縮コードを用いて上記ｎ番目のデータグループを圧
   縮するためのデータ圧縮手段と、 上記データ圧縮手段から圧縮されたデータを順次骨は取
   り、各々複数のビットからなるｎ　−１個（ｎは正の整
   数）の圧縮されたデータグループから、上記データ圧縮
   手段と同じ適応予想モデルをｎ番目の圧縮されたデータ
   グループの発生確率を計算し、該確率に適合する圧縮解
   除コードを用いて上記ｎ番目の圧縮されたデータグルー
   プを圧縮解除するためのデータ圧縮解除手段とを具備す
   るデータ圧縮装置。