JPH0774985B2 - データ圧縮システム - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は一般に条件付き２進ソースの算術圧縮コーディ
ング、特にスループットを増すための算術圧縮システム
のフォーマット互換性に関する。

B.従来の技術 所要のスループット・データ速度を維持するために、多
くの場合、複数の並列短縮システムを必要とする。短縮
装置の符号器及び複号器の各々はそれに向けられたデー
タを既知の最大時間内に処理せねばならない。短縮は複
数の並列装置により実行されるから、スループット・デ
ータ速度は最も遅い装置により制限される。

それゆえ、本発明の目的は既知の最大時間内にデータを
コード化し複号することができるデータ短縮システムを
提供することである。

各短縮装置は複数のデータ・セットを処理し、各符号器
から得られた修飾子情報はデータ・セットの全域で保持
されねばならない。データ・セットの順序も該処理を通
じて同じに維持されねばならない。修飾子データは算術
コーディング・システムの統計的な表から得られる。複
号の場合、各複号器から得られた修飾子情報もデータ・
セットの全域で保持されねばならない。標準的な方法
は、特定のフォーマットが所与のデータ速度で得られる
ように１つの短縮装置に１つの統計表を包含させること
により、修飾子保持問題を解決することである。そし
て、並列に設置されている圧縮装置の数によりスループ
ット・データ速度が決定される。各圧縮装置はデータの
一部を処理するから、圧縮装置の数が大きければ大きい
ほどデータ速度は早くなる。それゆえ、所要のスループ
ットにより並列短縮装置の数が決まる。各符号器の統計
的な表の学習曲線は後にデータを処理する、即ち圧縮す
るから、短縮装置の数は圧縮されたデータのフォーマッ
トを決定する。以前は、より多くの短縮装置が統計表に
加えられ、その結果、データ・フォーマットが変更され
た。以前にコード化された媒体はもはや確実には複号で
きなかった。もし、後で、より高速のデータ速度が要求
されれば、より多くの短縮装置を用いる新しいフォーマ
ットが設定される。より多くの並列接続短縮装置が供給
する新しいフォーマットは前のフォーマットでコード化
されたデータの複号を妨げる。その逆も成立つ。従っ
て、本発明前は、データ速度の増加により、前のシステ
ムと改良されたシステムの間の上方及び下方の互換性が
なかった。

ゆえに、本発明のもう１つの目的は全システムについて
同じフォーマットを保持しつつ更に高速のデータ速度を
取得できるデータ短縮システムを提供することである。

関連技術の説明 下記の参照文献は異なる状況の２進算術コーディング・
プロセスを示す。

Arithmetic Coding,G.G.Langdon,Jr.,et al.IBM Journa
l Research and Development,Volume 23,Number 2,Marc
h,1979,Page 149−162. Method for Carry−Over Contol in a FIFO Arithmetic
Code String,IBM Technical Disclosure Bulletin,Vol
ume 23,Number 1,June,1980,Pages 310−312. Delocking Method for Use with an Adaptive Arithmet
ic Encoder/Decoder,IBM Technical Disclosure Bullet
in,Volume 23,Number 6,1980,Pages 2528−2529. Unversal Modeling and Coding,J.J.Rissanen,IEEE Tra
nsaction on Information Theory,Volume IT−27,Numbe
r 1,January,1981,Pages 12−23. Statistics Collection for Compression Coding with
Randomizing feature,IBM Technical Disclosure Bulle
tin,Volume 24,Number 10,March,1982,Page 4917. A Simple General Binary Source Code,G.G.Langdon,J
r.,et al.,IEEE Transaction on Information Theory,V
olume IT−28,Number 5,September,1982,Pages 800−80
3. Control Character Insertion into Arithmetcally Enc
oded Strings,IBM Technical Disclosure Bulletin,Vol
ume 25,Number 4,September,1982,Pages 2051−2052. A Double−Adaptive File Compression Algorithm,G.G.
Langdon,Jr.,et al.,IEEE Transactions on Communicat
ions,Volume COM−31,Number 11,November,1983,Pages
1253−5. An Introduction to Arithmetic Coding,G.G.Langdon,J
r.,IBM Journal Research and Development,Volume 28,
Number 2,March,1984,Pages 135−149. Overlapped Statistics Memory Access for Decompress
ion,IBM Technical Disclosure Bulletin,Volume 27,Nu
mber 1B,June,1984,Pages 871−872. United states Patent 4,467,317,High Speed Arithmet
ic Compression Coding,Using Concurrent Value Updat
ing,G.G.Langdon,Jr.,et al. C.発明が解決しようとする課題 異なるスループット速度を持つシステムの間の短縮プロ
セスのフォーマット互換性に関する本発明は前記参照文
献のどれにも開示されていない。

本発明の目的は既知の最大時間内にデータをコード化し
複号することができるデータ短縮システムを提供するこ
とである。

本発明のもう１つの目的は全システムについて同じフォ
ーマットを保持しつつ更に高速のデータ速度を取得でき
るデータ短縮システムを提供することである。

本発明のもう１つの目的は異なるスループット速度を用
いる短縮プロセスでフォーマット互換性が維持される高
機能の２進算術コード化プロセスを提供することであ
る。

本発明のもう１つの目的はコード化及び複号プロセスの
上方及び下方フォーマット互換性を可能にする改良され
た短縮方式を提供することである。

本発明のもう１つの目的は増大したスループット速度及
び標準的なスループット速度のどちらかでコード化され
た媒体も複号できる上方及び下方フォーマット互換性を
提供すると同時に今日のレコード処理システムが要求す
るより高い速度でデータを圧縮し処理するためにデータ
に固有のスループット速度に適応できる短縮プロセッサ
を提供することである。

本発明のもう１つの目的は並列短縮装置の付加により増
大したスループット速度を持つ短縮システムに予測可能
スループット速度及びフォーマット互換性を提供すると
同時に複数の並列短縮システムを利用し且つデータ・ス
トリームに適応可能な圧縮方式を提供することである。

D.課題を解決するための手段 本発明のデータ短縮システムは最初にデータ・ストリー
ムを等しいサイズの管理可能なエンティティ、即ちデー
タ・セットに分割する。次に、これらのデータ・セット
の各々は圧縮するためにデマルチプレクサを介して複数
の符号器に分配される。符号器の各々は複数の統計表を
含み、所要のハードウェアを減らし且つより高いスルー
プット構成に拡張すると同時に、装置の付加によりスル
ープットが増大した２進算術符号器とのフォーマット互
換性を可能にする。短縮されたデータ・セットは再びマ
ルチプレクサで順序付けられる。

該データを複号するため該短縮されたセットはデマルチ
プレクサに送られ、短縮されたデータ・セットの各々を
複数の複号器の１つに分配する。複号器の各々は複数の
統計表も含み、複数の複号器の増大したスループットと
のフォーマット互換性を可能にしつつ、同様に所要のハ
ードウェアを減らし、より高いスループット構成に拡張
するとともに、低いスループット構成に対する下方互換
性を与える。短縮解除されたデータ・セットはマルチプ
レクサにより再び順序付けられ、最初のフォーマットに
なるようにアセンブルし直される。

このように、本発明に従って多重短縮プロセッサを用い
てフォーマット互換性を維持しつつ所望のデータ速度を
保持することができる。各短縮プロセッサにより並列処
理するためにデータは先ず等しいサイズのデータ・セッ
トに分割される。ｎ個の短縮プロセッサの各短縮プロセ
ッサはｍ統計表（ST）を含む。データ・セットの数はｑ
であり、ｉはセットの番号、即ち0,1,2....q−１であ
る。セットｉは統計表ST j kを用いて短縮プロセッサCP
jにより処理される。ｊ及びｋは下式により決定され
る： ｊ＝ｉモジューロｎ ｋ＝（i/n）モジューロｍ 但し（i/n）はi/nの整数部分である。

各CPにＭ個のSTを持つＮ個のCPシステムの場合、Ｎより
も小さい数のCPシステムの可能な構成は： ｍ≦Ｍ ｎ≦Ｎ により規定される。M,N,m及びｎは全て０よりも大きい
整数である。ｎはN CPシステムで最大の中から使用され
るCPの数であり、ｍは各CPで最大Ｍの中から使用される
STの数である。

本発明のもう１つの目的はコード化及び複号プロセスの
上方及び下方フォーマット互換性を可能にする改良され
た短縮方式を提供することである。

本発明はレコードを管理可能なエンティティ即ちセット
に分割し、拡張又は短縮することができる短縮システム
により該データを処理し、該データ・ストリームを所望
の最大可変データ速度で処理する。連続するデータ転送
で用いる符号器及び複号器の数は転送されるデータの速
度によって決まり、連続する符号器及び複号器の各々は
それぞれ短縮及び短縮解除を並列に処理する。使用され
る符号器及び複号器の数は所要の最大データ速度により
増減できる。符号器と複号器の数及びそれぞれが含む統
計表の数を適切に選択することにより、データ・フォー
マットの互換性が維持される。

本発明のもう１つの目的は増大したスループット速度及
び標準的なスループット速度のどちらでコード化された
媒体も複号できる上方及び下方フォーマット互換性を提
供すると同時に今日のレコード処理システムが要求する
より高い速度でデータを圧縮し処理するためにデータに
固有のスループット速度に適応できる短縮プロセッサを
提供することである。

適応圧縮は相互に排他的な２つのモード：少なくとも２
つの同じバイトが現われると必ず同じ文字のランを除去
するラン・モード、及びそれ自身の統計によりデータ・
バイトを直列化し各バイトをコード化するバイト・モー
ドのうちの１つで実行される。両モードの結果は統計表
で統計を集めるために使用される。統計はバイト内のビ
ットのパターンを確立するために集められ、前の経験に
基づいて次のビットを予測する確率として記憶される。
適応圧縮プロセスは、適応データ統計を用いて、コード
・ストリングから最初のデータが回復されるようにデー
タ・ビットのストリングをコード・ストリングに写像す
る。圧縮の量は正確なビット予測に正比例する。

本発明のもう１つの目的は並列短縮装置の付加により増
大したスループット速度を持つ短縮システムに予測可能
スループット速度及びフォーマット互換性を提供すると
同時に複数の並列短縮システムを利用し且つデータ・ス
トリームに適応可能な圧縮方式を提供することである。

本発明のもう１つのアプリケーションは可変長ストリン
グの入力記号を固定長コードに変換するレンペル・ジブ
（Lempel−Ziv）プロセスに関する。このプロセスは圧
縮及び圧縮解除プロセスの間に空の記号ストリングの
表、即ち辞書で開始し、該表を構築する適応圧縮プロセ
スである。このようなシステムのスループットは複数の
符号器及び複号器を用いて高めることができる。レンペ
ル・ジブ・プロセスのより完全な説明は下記の論文を参
照されたい： “A Universal Algorithm for Sequential Data Compre
ssion",J.Ziv,et al.,IEEE Transactions on Informati
on Theory,Vol.IT−3,May 1977,pages 337−343. “Compression of Individual Sequences via Variable
−Rate Coding",J.Ziv,et al.,IEEE Transactions on I
nformation Theory,Vol.IT−24,No.5,September 1978,p
age 5306. 開示の概要 磁気テープ駆動機構で用いる算術２進圧縮コーディング
装置間のフォーマット互換性は、たとえ異なる数の圧縮
装置／圧縮解除装置がシステム・スループットを高める
ために必要とされても保持することができる。装置の各
々はそれに送られるデータを既知の最大時間で処理せね
ばならない。短縮装置の各々は短縮装置毎に選択された
数の統計表を含む。各々が２つの統計表を持つことがで
きる８つの短縮プロセッサが選択される。従って、フォ
ーマット互換性はそれぞれに２つの統計表を持つ４つの
短縮プロセッサを用いて保持することができ、又は符号
器／複号器の各々に１つの統計表を持つ８つの短縮プロ
セッサを用いてスループットを２倍にすることができ
る。各々の速度短縮を用いて磁気テープ上に短縮された
データは各々のテープ駆動機構を用いて複号することが
でき、互換性は保証される。

E.実施例 本発明は磁気テープ・システム、特にIBM 3490磁気テー
プ装置における使用が望ましい。ゆえに、本明細書に記
載された最良のモードは磁気テープ・システムに関する
ものであるが、本発明はどんな記憶装置、通信、即ち伝
送システムにも適応できる、即ちデータ処理システムの
どの部分にも利用される。該データ処理システムにより
データのストリームは例えば記憶のために短縮され、後
にその利用のために検索され短縮解除される。

本発明は情報処理された大抵のタイプのデータを短縮し
て十分に小さいデータ・ブロックにする効率的な方法を
カバーする。本発明により提供される手順はIBM 3480磁
気テープ装置の最新のハードウェアに付加できる。その
結果、システムは本発明による利点を提供すると同時に
必要なときにホスト・データ処理システムのユーザとデ
ータを交換し続けながら本発明による利点を提供する。

第１図の複数の並列に接続された短縮プロセッサ（CP）
１〜４（参照番号17）で示す短縮装置は、拡張フォーマ
ットが選択されている時、チャネル書込み動作中にデー
タを短縮し、チャネル読取り動作中にデータを短縮解除
する。データ短縮は２進算術短縮（BAC）プログラムの
変更版を用いて実行される。該プログラムは論文:An In
troduction to Arithmetic Coding,by Glenn G.Langdo
n,Jr.,IBM Journal of Research and Development,Volu
me 28,Number 2,March 1984に説明されている。各短縮
プロセッサによりデータは1.25Mb/sの速度でコード化さ
れる。並列に付加された各短縮プロセッサは追加の1.25
Mb/sコード化速度を可能にする、従ってデータ処理速度
は増大する。追加の各短縮プロセッサは短縮システム全
体の統計フォーマットに影響する。本発明により、短縮
プロセスのスループットが短縮プロセッサの付加によっ
て増大できると同時に現在の設計が当該増大を受入れる
方法が示される。短縮プロセッサの増加は、例えば本実
施例とのフォーマット互換性を保持しつつ、後で詳細に
説明するように統計的な表を本実施例に付加することに
より適応させることができる。

第１図に示すように、複数のチャネル・アダプタ（CA）
12は、短縮装置16に配置された複数の短縮プロセッサ17
を介して利用装置、例えばテープ記録媒体に接続され
る。短縮プロセッサ17の各々はフォーマット化されてい
ないデータをＡバス20を介してチャネル・アダプタ12か
ら受取る。その詳細は後で説明する。短縮プロセッサ17
は送られたデータのストリームを同一サイズのブロッ
ク、即ちデータのセットに分割する。そして個々のデー
タ・セットは短縮プロセッサ17の各々にある個々の符号
器に送られ、個々のセットは異なる符号器で順次に圧縮
される。そして短縮されたデータ・セットは再びアセン
ブルされフォーマット化されてテープ媒体、即ち第１図
に示す利用装置に書込まれる。

第１図では、複数のチャネル・アダプタ12を相互接続し
て利用装置とインタフェースさせる標準的な読取り及び
書込み、この場合、記録テープ媒体から及び該媒体への
読取り及び書込みフォーマット制御の流れに複数の短縮
プロセッサ17が挿入される。並列接続された短縮プロセ
ッサ17とインタフェースさせるために、ホスト処理装置
からのデータ・ストリームが複数のチャネル・アダプタ
12のなかの１つに送付される。チャネル・アダプタ・コ
マンド・セット、拡張フォーマットはデータ・ストリー
ムをCA 12のインタフェースを介してＡバス20及びライ
ン21に沿って複数の短縮プロセッサ17に転送するように
指図する。Ａバス20からのデータ・ストリームは短縮プ
ロセッサ17の全てに送られ、短縮プロセッサへのデータ
の受取り及び短縮プロセッサからのデータの分配を制御
するのはＡ−mout信号である。その手順は第２図及び第
３図で詳細に説明する。短縮プロセッサ17はフォーマッ
ト化されていないデータを活動状態のCA 12から受取
る。短縮装置16として示されたタンデム装置のような短
縮プロセッサ17はフォーマット化されていないデータを
データ・ストリームから分離して同一サイズのブロック
即ちデータ・セットにする。次に個々のデータ・セット
は各短縮プロセッサ17に送られ、各々のセットは順次に
コード化され短縮される。処理されたデータ・セットは
テープ媒体、利用装置に書込む前にフォーマット化する
ために、それらの最初のシーケンスになるように再アセ
ンブルされ、Ｂバスに送られる。第２図は２つの処理装
置の概要図及びそれらの相互接続を示す。

第２図で、短縮プロセッサ毎にデータストリームがＡバ
ス20から入出力制御部に送られる。第２図には短縮プロ
セッサCP1及びCP2だけが示されている。第２図で、デー
タ・ストリームはI/O制御部Ａ−１及びI/O制御部Ａ−２
に送られる。例えば、I/O制御部Ａ−１はCP1に送られる
データ・セットを決定する。Ａ−mout信号は、ある特定
の期間にどのI/O制御部が活動状態であるかを判定す
る。各処理装置、例えばCP1は回転式デマルチプレクサ
／マルチプレクサ装置25（DMX/MX A−１）のセクション
も含む。回転式デマルチプレクサ／マルチプレクサ装置
25及び処理装置CP2の回転式デマルチプレクサ／マルチ
プレクサ装置処理装置29（DMX/MX A−２）を接続する破
線及び斜線の部分27は、短縮プロセッサの各々への１つ
のデータ・セットの転送を効率的に制御する１つの回転
式デマルチプレクサ及びマルチプレクサ装置を形成する
ために、全ての処理装置のハードウェアが相互接続され
ることを示す。CP1は符号器36及び複号器38も含む。符
号器36の出力及び複号器38の入力はもう１つの回転式マ
ルチプレクサ／デマルチプレクサ37（MX/DMX B−１）、
即ち符号器36の再順序化ハードウェア、及び複号器38の
分離ハードウェアに接続される。CP1の回転式マルチプ
レクサ／デマルチプレクサ37のような、回転式MX/DMX装
置の全ての相互接続は、破線及び斜線部分39で示すよう
に、そのマルチプレクサ／デマルチプレクサ機能を実行
するように作用する。よって、第１図に示すように並列
に動作する短縮プロセッサ17は各処理装置の上部即ちＡ
セクションの入出力制御部、回転式デマルチプレクサ及
びマルチプレクサ、並びに各短縮プロセッサ17の下部即
ちＢセクションの入出力制御部、回転式デマルチプレク
サ及びマルチプレクサを含む。

Ａバスからのデータ・ストリームは各短縮プロセッサ17
の各I/O制御部に送られる。Ａ−mout信号はどの短縮プ
ロセッサがデータ・ストリームからそのデータ・セット
を取得すべきかを指示する。回転式デマルチプレクサ及
びマルチプレクサはその短縮プロセッサ内の符号器及び
複号器に該データ・セットを分配する。例えば、初期設
定では、CP1は第１のデータ・セット（良好な実施例で
は512バイト）を取得し、そしてＡ−mout信号が活動化
されCP2は第２のデータ・セットを取得する。CP3は次の
データ・セットを取得し、次いでCP4はそのデータ・セ
ットを取得する。そして、次のデータ・セットはCP1に
転送されシーケンスを続行する。第１図及び第２図の短
縮プロセッサに含まれた実際のハードウェアは第３図に
示す。

第３図に示すように、各々の短縮プロセッサ17特にCP1
は事象カウンタ132、インタフェース制御部134及び記憶
装置136を含む。これらの装置はCP1の上部即ちＡセクシ
ョンに特有のものである。CP1の下部即ちＢセクション
も事象カウンタ138、記憶装置140及びインタフェース制
御部142を含む。CP1は符号器114、複号器124及び速度整
合バッファ144も含む。事象カウンタ、例えば132および
138は上部及び下部のインタフェースのため処理装置の
各々で使用され、それぞれのデータ・セットの、処理装
置への分割及び処理装置からの合併を制御し検査する。
符号器114は２つの統計表113及び115を含み、複号器124
も２つの統計表123及び125を含む。

第３図では、CP1は初期化プロセス又は前の処理装置、
即ちCP4からの制御の移動により活動化されると仮定す
る。前述のように、Ａ−muut信号は１つのCP装置から次
のCP装置に制御を移動する。書込みサイクルでは、即ち
ホストからのデータ・ストリームが短縮されてテープ媒
体に書込まれるときは、データ・ストリームは短縮プロ
セッサのＡセクションにある全ての記憶装置に送られ
る。記憶装置136は１つのデータ・セット即ち512バイト
を受取ったことを事象カウンタ132に知らせる。そして
事象カウンタ132はCP1がそのデータのセクション即ち１
データ・セットを受取ったので次のデータ・セットはCP
2が受取るべきことをインタフェース制御部134に知らせ
る。書込みサイクルでは、データ・セットは第３図に示
す実線を通じて送られる。第３図に示す種々のラインの
コードには、異なる短縮プロセッサのハードウェアを制
御する制御ラインを示す単線の実線146、書込みデータ
の流れ（WDF）を表わす複線の実線148がある。破線の複
線コード150による信号転送はCP1による読取りデータの
流れ（RDF）を示す。

データ・セットはそれを短縮するために記憶装置136か
ら符号器114に送付される。符号器114は統計表113及び1
15を用いてデータ・セットを短縮する。短縮プロセスの
終了後、符号器114は短縮されたデータ・セットを速度
整合バッファ144及び記憶装置140に送付する。速度整合
バッファ144に送付された、短縮されたデータは符号器1
14の出力と複号器124の出力を整合させるように記憶さ
れる。短縮されたばかりのデータは短縮解除のため速度
整合バッファ144から複号器124に送付される。複号器12
4は短縮解除されたデータを検査のため記憶装置136に返
送する。短縮されたデータは記憶装置140に転送され、
事象カウンタ138及びインタフェース制御部142による制
御を待ち、短縮されたデータ・セットがテープ媒体への
転送のためにＢバスに乗せることができることを知らせ
る。

読取りサイクル、即ちテープ媒体からデータを検索する
データ検索サイクルでは、短縮されたデータ・セットは
テープ媒体から受取り記憶装置140に送付する。短縮さ
れたデータ情報のビットは短縮されたデータ・セット全
体を受取るまで記憶装置140内に記憶される。短縮され
たデータ・セット全体を受取った時点で、短縮されたデ
ータ・セットを分離する区切信号は事象カウンタ138を
活動化し、事象カウンタ138はインタフェース制御部142
を活動化してＢ−mout信号ラインで制御を次の処理装
置、CP2に移動する。CP2はその短縮プロセス内で使用す
るためにそのデータ・セットを受取る。RDF信号経路に
従って、記憶された短縮データ・セットは複号器124に
転送され、複号器124で該データ・セットは短縮解除さ
れ、記憶装置136が512バイトのデータ・セットを受取っ
たことを合図するまでライン141で記憶装置136に送付さ
れ、記憶される。そして制御はインタフェース制御部13
4に移され、記憶装置136が該データ・セットをＡバス20
でチャネル・アダプタ12に転送できるようにする。短縮
解除されたデータが転送された後、事象カウンタ132は
Ａ−mout信号ラインを介して制御をCP2に移すようにイ
ンタフェース制御部134に合図する。この動作により、
次のデータ・セットはCP2の記憶装置ＡからＡバスに、
そして最終的にはチャネル・アダプタに転送できる。短
縮プロセッサ１〜４の制御及びシーケンス動作のより完
全な説明は米国特許出願第441127号（1989年11月22日出
願）明細書を参照されたい。

テープ媒体システムにおけるデータの処理の詳細な説明
は米国特許第4435762号に記載されている。

単一の短縮プロセッサは、データ・ストリームを短縮し
且つ圧縮されていないデータの所与のデータ速度を維持
するには、速さが十分ではない。本発明による速度の増
加はデータ圧縮装置の数の増加とおおよそ比例する。媒
体に書込まれたデータも、圧縮に用いたのと同じ装置数
を用いて同じように高速で短縮解除される。512バイト
・ブロックのデータ・セットの各々は別々の短縮プロセ
ッサで個々に圧縮される。このように、第１のデータ・
セットは短縮プロセッサ１に、第２のデータ・セットは
短縮プロセッサ２に送られ、以下同様に、第４のデータ
・セットが短縮プロセッサ４で圧縮されるまで続く。第
５のデータ・セットはCP1に戻る。

第３図には、２進算術コードにより２進情報を複号する
際に次のビットに関して最後のビット値に基づいた統計
表のアクセスを必要とするタイム・クリティカル帰還経
路がある。もし回避されなければ、この問題は各ビット
の複号に必要なサイクル・タイムを減速させる。隣接す
る位置から１よりも多くの統計を読出し且つ正しい統計
表を選択する先読み手法は、連続するビット毎に異なる
レベルのトリーのアクセス及び同時に２つのレベルの可
能な統計の読出しと組合わされる。後で説明するコード
化方式のプロセス流れ図は第４図に示す。

データを短縮するための２進算術コード・プログラムは
圧縮を成し遂げるために２進統計を必要とする。これは
コード化又は複号されたビット毎に統計を取出すことを
必要とする。統計は線形化されたトリーに記憶される。
ビットのコード化はコード化される８ビット毎に一度だ
け各トリー・レベルのアクセスを必要とする。８ビット
・サイクルでは統計は一度使用されると再び使用される
ことはないから、ビットのコード化又は複号のためのア
クセスをオーバラップさせるための事前取出し即ち先読
みが用いられる。統計表（E1）113は圧縮装置に送られ
たモジューロ８のパケットのうちの第１即ちモジューロ
０のデータ・セットを処理し、他方、統計表（E2）115
はモジューロ４のデータのパケットを処理する。

第３図は複号器124の２つの統計表123及び125も示す。
統計表123及び125は、符号器114に統計表113及び115が
接続されるのと同じように、複号器124に接続される。
符号器及び複号器の全ての統計表のランダム・アクセス
・メモリは、本発明の良好な実施例に符号器及び複号器
が実際に４つずつあるとき、８つの符号器及び複号器が
オンラインであるように見える。符号器及び複号器毎の
統計表の二重化は、各々が１つの統計表を持つ８つの符
号器及び複号器によるフォーマット互換性を成し遂げ
る。８つの符号器及び複号器は、第１図に示す４つの符
号器及び復号器のスループットを２倍にし、他方、符号
器及び復号器毎に１つの統計表の使用は、本発明の実施
例の４つの符号器及び復号器並びにその各々の２つの統
計表を持つシステムとのフォーマット互換性を可能にす
る。

このように、本発明に従って、複数の短縮プロセッサを
用いて所望のデータ速度を保持し、しかもフォーマット
互換性も維持することができる。データは最初、各短縮
プロセッサにより並列処理するために等しいサイズのデ
ータ・セットに分割される。各短縮プロセッサはｎ短縮
プロセッサに対しｍ統計表（ST）を含む。データ・セッ
トの数はｑに等しく、ｉはセット番号、即ち、0,1,
2,....q−１である。セットｉは統計表ST j kを用いて
短縮プロセッサCP jにより処理される。この場合： ｊ＝ｉモジューロｎ ｋ＝（i/n）モジューロｍ である。

各CPでM STを持つN CPについては、データ処理システム
における数Ｎよりも少ないCPの可能な構成は： ｍ＝Ｍ ｎ＝Ｎ により規定される。M,N,m及びｎは全て０よりも大きい
整数である。ｎはN CPシステムにおける最大数の中から
使用されたCPの数であり、ｍは最大数CPの中から使用さ
れたSTの数である。

図示の良好な実施例では、Ｎは8CPに等しく、ＭはCP毎
の2STに等しい。可能な構成はｎが４に等しく、ｍが２
に等しい場合である。スループットの増加は8CPを使用
し、各CPが1STを用いる場合、即ちｎが８に等しくｍが
１に等しい場合に可能である。8CP、即ちＮが８に等し
い場合のもう１つの可能性はＭが８に等しく、可能な構
成は： ｎ＝8,m＝１ ｎ＝4,m＝２ ｎ＝2,m＝４ ｎ＝1,m＝８ である。

8CPの場合で、Ｍが４に等しい時の可能な構成は： ｎ＝8,m＝１ ｎ＝4,m＝２ ｎ＝2,m＝４ である。

従って、全てのスループット速度の増加を通じてフォー
マット互換性を維持しつつ、現在要求されているスルー
プット速度及び後に所望されるスループット速度を選択
することによるデータ・スループットの増加を通じてフ
ォーマット互換性を維持することができる。より高いス
ループット速度、及びより低いスループット速度の短縮
の下方及び上方互換性は保証される。

適応短縮は２つの相互に排他的なモードの１つで符号器
にあるバイト毎に実行される。第１のモードは１以上の
反復が検出されたとき同じ文字の順次反復を圧縮するラ
ン・モードである。これらはラン・モード・シーケンス
をセットすることにより識別される。

第２のモードは集積された統計により個々のバイトをコ
ード化するバイト・モードである。このバイト・モード
は前の２つのバイトが異なる時、即ちバイト・モードが
非反復を表わした後に用いられる。このモードはラン文
字が該文字に等しいときに識別される。両モードの結果
は、どの統計表が当該時点で活動化されるかにより該統
計表からの統計を集積するために使用される。コード化
プログラムはデータ・バイト毎の統計に適応する。ラン
・モード処理では、統計はバイト反復の見込みに基づい
ている。バイト・モード処理では、最初、各バイトの各
ビットは確率が等しいものと仮定する。統計はビット単
位で更新され、統計表の２進トリー構造に記憶される。
統計は入力データ・ストリングの各レコードを受取る前
にリセットされる。従って、各レコードは独立して処理
される。

第４図に関連して後で説明するように、該プログラムは
データ圧縮を最大化するのにどのモードが有効かを動的
に決定する。正確な原データがコード・ストリングから
回復されるように、プログラムは適応データ統計を用い
てデータ・ビットのストリングをコード・ストリングに
写像する。圧縮される量は連続するバイト反復の数及び
或バイト値がどの程度優勢であるかに正比例する。符号
器及び複号器は、該システムの最大データ速度を満たす
のに必要な並列短縮プロセッサの最大数として選択でき
る、同数の統計表を用いる。第４図〜第15図による短縮
処理は前述の論文Arithmetic Coding及びAn Introducti
on to Arithmetic Coding並びに特公昭63−6172号公報
に詳細に記載されている。これらの出版物及び米国特許
明細書は符号器及び復号器毎に１つの統計表が使用され
る本発明によるコード化及び復号プロセスをずっと詳細
に説明している。

第４図の短縮コード化プロセスの流れ図では、２つの前
のバイトが同じ時はラン・モード・シーケンスである。
バイト・モードはラン・モードが見つからない時に使わ
れるモードである。ラン・モードは１以上の反復が検出
されると同じ文字の順次反復を圧縮する。ラン・モード
が見つからない時、即ちバイト・モードが開始される
と、個々のバイトは集積された統計によりコード化さ
れ、前の２バイトが異なる、即ちラン・モードが見つか
らないとき、又はラン・モードが非反復を表示してから
使用される。モードの結果はどちらも統計を集積するた
めに使用される。コード化プロセスはバイト毎の統計に
適応する。ラン・モード処理の場合、統計はバイト反復
の見込みに基づいている。ビット・モード即ち非ラン・
モードの場合、最初に各バイトの各ビットは同じ確率で
あると仮定する。統計はビット単位で更新され且つ２進
トリー・データ構造で記憶される。統計は３ビット・フ
ィールドのフォーマットをとり、１ビットはどのビット
値がより見込みがあるかを表わし、他の２ビットは値１
〜４を持つ数である。前記値は最も見込みのあるビット
値を生じる相対的な確率を示し、値１は同じ見込みの値
を表わし、値４は最も見込みのある値を表わす。ホスト
から受取った各々の論理的なブロックの始まりで統計は
リセットされるので、論理的なブロックはそれぞれ独立
して処理される。該プロセスはデータ圧縮を最大化する
ためにどのモードが有効かを動的に決定する。該プロセ
スは、適応データ統計を用いて、データ・ビットのスト
リングをコード・ストリングに写像し、正確な原データ
がコード・ストリングから回復できるようにする。圧縮
される量は連続するバイト反復の数及び或バイト値がど
の程度優勢であるかに正比例する。

第４図の流れ図はデータ・セットのコード化プロセス全
体を示す。前述のように、データ・セットは最後のセッ
ト（データ・ストリームからデータ・セットに分離され
た後の残りのバイト）以外は512バイトである。データ
・セット毎に、符号器は既知の状態に初期化される。統
計表はデータ・セット毎には初期化されず、むしろチャ
ネル・レコード毎に初期化されるだけである。ラン文字
レジスタは初期化される。ラン・モード・レジスタは各
データ・セットの始まりでリセットされる。該セットの
中から各々のバイトが取出され、文字レジスタにロード
される。もしラン・モードがセットされれば、ラン文字
レジスタと文字レジスタが比較される。もしそれらが等
しければ、第６図に示す反復事象コード化が実行され
る。さもなければ、第７図に示す非反復事象コード化が
実行され且つ第５図に示す文字コード化プロセスが実行
される。もしラン・モードがセットされなかったなら
ば、文字コード化プロセスは直ちに開始される。

該セットのバイトはラン・モードでコード化されている
から、ラン・モードは決定されている。ラン文字レジス
タと文字レジスタが比較され、もしそれらが等しけれ
ば、ラン・モードがセットされる。さもなければ、ラン
・モードはリセットされ、ラン文字レジスタは次のラン
・モード事象の文字・レジスタ情報にセットされる。

該データ・セットの全てのバイトが処理されるまで該プ
ロセスは反復される。非反復事象コード化はラン・モー
ドで処理しているデータ・セットを終了させるために実
行される。ラン・モードがセットされてもリセットされ
ても、符号器内の符号レジスタな内容は符号の一部とし
てシフトアウトされる。

第４図の流れ図はブロック200で初期化、即ち関係する
レジスタをリセットしてプログラムを開始することによ
り始まる。次のブロック204では、データ・セットから
次のバイトを取得し、それを文字レジスタに入れる。判
定ブロック206はラン・モード・シーケンスがセットさ
れているかどうかを判定する。もしセットされていなけ
れば、“ノー”のライン208からブロック210に進み、こ
のバイトをコード化する。次にブロック212で、該文字
は前の文字と同じかどうかを検査する。もし同じでなけ
れば、ブロック214で、ラン・モードをリセットし、且
つラン文字レジスタを文字レジスタに等しくなるように
セットする。プロセスは続行し、次のバイトを取得する
ためにブロック204に戻る。判定ブロック206で、もしラ
ン・モードがセットされていれば、“イエス”のライン
から次の判定ブロック220に進み、ラン文字レジスタの
情報が文字レジスタの情報と同じかどうかを検査する。
もし同じならば、イエス・ライン222からブロック224に
進み、反復された事象をコード化する。そして、ブロッ
ク212に該文字が最後の文字に等しいかどうかを検査す
る。もし等しければ、ブロック218で、ラン・モードが
セットされ、次のデータを取得するためにシーケンスの
始めに戻る。ラン・モード・シーケンスは、前のバイト
が同じであり且つ符号器が２進算術コード化プロセスに
従ってこの類似のデータを短縮する場合に用いられる。
判定ブロック220で、もしこのバイトの文字が同じでな
いならば、ノー・ラインからブロック226に進み、非反
復事象がコード化され、ブロック210で文字がコード化
される。ラン文字レジスタは文字レジスタに等しくない
から、判定ブロック212からノー・ラインを経由してブ
ロック214に進み、ラン・モードをリセットする。ラン
・モード文字はセットされていないから、プロセスは同
じモードのままで各バイトを検査する。この時点では、
それはビット・モードであり、バイトの各ビットは、こ
のバイトの非類似ビットを短縮するように処理される。
プロセスはコード化されるデータ・セットにある全ての
バイトを検査し続ける。コード化されたばかりの情報を
復号する復号プロセスは第11図に示す。第４図の個々の
ブロックの幾つかのプロセスの流れは第５図〜第８図に
示す。

第５図は第４図のブロック210の文字コード化手順を示
す。バイトが反復されない、非ラン・モードのとき、各
バイトは第４図に示すブロックのコード化文字によりコ
ード化される。文字バッファに記憶されているバイトの
８ビットの各々について、統計が取出されてから、第８
図に示すコード化手順によりコード化される。そして、
更新された統計は統計表に再び記憶される。バイトをコ
ード化するために、DBITレジスタは先ずバイトの最上位
ビットにセットされる。ブロック236に示すように、最
初のビットの統計が取出されるアドレス、ADDRが１にセ
ットされる。ブロック238で、ビットはアドレスADDR及
び第８図に示すビット・コード化プロセスを用いてコー
ド化される。最上位の次のビットをコード化するため
に、ブロック240に示すように、ADDRアドレスを１ビッ
ト左シフトしてDBITを書込むことにより新しい統計表ア
ドレスが生成される。ブロック242に示すように、DBIT
は文字レジスタの最上位の次のビットにセットされる。
ブロック244に示すように、前記プロセスは８回反復さ
れ、文字のビットの全てをコード化する。

第６図は第４図に示すブロック224の反復事象コード化
プロセスを示す。統計表のアドレス０はラン・モードと
して使用される。ラン・モードがセットされると、ブロ
ック246に示すように、アドレスADDRは０に、DBITは１
にそれぞれセットされ、反復されたビットがコード化さ
れることを表わす。そして、第８図のビット・コード化
プロセスが実行され、ブロック248に示すように、反復
事象をコード化する。

第７図は第４図のブロック226の非反復事象コード化プ
ロセスを示す。ラン・モードがセットされると、ブロッ
ク250に示す最初のステップで、統計表のアドレスADDR
は０に、DBIT文字は０にそれぞれセットされ、ラン文字
に等しくないビットはコード化されることを表わす。統
計表のアドレス０はラン・モードについて使用される。
そして、ブロック252に示すように第８図のビット・コ
ード化プロセスが実行され、第４図に示すようにラン・
モードの中断が起き且つ文字コード化ブロック210で非
ラン文字がコード化されることを示す。

第８図のビット・コード化プロセスは、第５図のビット
・コード化ブロック238、第６図のビット・コード化ブ
ロック248及び第７図のビット・コード化ブロック252で
使用される。該プロセスの最初のステップ254で、統計
ＭおよびＫはアドレスADDRにより指定されたアドレスで
統計表から取出される。Ｍ統計は推測された値を示す１
ビット値であり、統計Ｋは２ビットの確率値である。Ｋ
は１から４までの数をとることができる。Ｍ、Ｋ及びDB
ITはコード計算ブロック256でのプロセスを使用して該
ビットをコード化するために用いられる。コード計算プ
ロセスは第９図に示す。次にブロック258で、統計を更
新してデータに適応させる。これは第10図に示す統計計
算プロセスで実行される。新しい統計がＭ及びＫで計算
されてから、ブロック260に示すように、統計値はアド
レスADDRにより指定されたアドレスで統計表に記憶され
る。

第９図のコード計算プロセスに示すように、コード化プ
ロセスは確率の合計を生成する。合計はコード、即ち符
号器の出力である。合計は合計レジスタＣで加算及びシ
フト動作を行うことにより生成される。正規化レジスタ
として、レジスタＡも使用される。本発明の良好な実施
例ではＡレジスタ及びＣレジスタはどちらも４ビットで
ある。第４図の初期化ステップで、Ａレジスタ及びＣレ
ジスタはどちらも０に初期化される。第９図のコード計
算プロセスの最初のステップは、ブロック600に示すよ
うに、確率最大の記号MPSをコード化するか、又は確率
最小の記号LPSをコード化するかを決定する。もしDBIT
が推測値Ｍに等しければMPSがコード化され、さもなけ
ればLPSがコード化される。LPSが選択されると、Ａレジ
スタは０にリセットされ（ブロック612）、Ｃレジスタ
はＫ回左シフトされ、０が書込まれる（ブロック61
4）。シフト・プロセスによりＣレジスタから出るビッ
トは連結されてビット・ストリングになる。短縮された
データはＣレジスタから出るこのビット・ストリングで
あり、このストリングに追加の操作が実行される。

最大確率記号（MPS）の場合は、PFと呼ばれる確率係数
がＫから生成される。PFは４ビット値であり、Ａレジス
タ及びＣレジスタで算術演算を実行するために使用され
る。もしＫ＝１ならPFは1000にセットされる。もしＫ＝
２ならPFは0100にセットされる。もしＫ＝３ならPFは00
10にセットされる。もしＫ＝４ならPFの表は0001にセッ
トされる。PF値はＣレジスタの内容に付加される。もし
Ｃレジスタからの桁上げがあれば、該桁上げは前に生成
されたコード・ビットを介して伝達される。新しい４ビ
ット合計は再びＣレジスタに記憶される。更に、Ａレジ
スタの内容からPFが差引かれ、新しい差は再びＡレジス
タに記憶される。減算プロセスでＡレジスタに借りが生
じたなら、Ａレジスタ及びＣレジスタはどちらも１ビッ
トずつ左シフトされ、０が書込まれる。Ｃレジスタから
シフトされたビットは前のコード・ビットと連結され、
短縮されたデータをつくる。

Ｃレジスタからシフトアウトされたビットは確率の合計
であるから、Ｃレジスタからの桁上げは全合計に伝達さ
れねばならない。全合計を符号器に記憶することは実際
的ではないので、符号器から送付済みのコードの桁上げ
は出力を介して伝達しなくてもよいように、桁上げ伝達
が制御されねばならない。これは詰込みビットによって
行われる。Ｃレジスタから出る合計は８ビット・バイト
として連結され、符号器から送出される。８ビットの全
部１の値を持つコード・ビットが検出される毎に、４ビ
ットの０が全１バイトの後に挿入され、Ｃレジスタから
の桁上げが全部１のバイトに伝達されるのを阻止する。
もしＣレジスタからの桁上げがあれば、詰込まれた４ビ
ットの０は１つだけ増加する、従って桁上げが全１コー
ド・バイトに伝達されるのを阻止する。バイト詰込みの
１つの利点は、コード・ストリームへの特別の文字コー
ドの挿入が可能なことである。次の４ビットの２つの組
合せ、即ち0000及び0001の一方だけが全１ビットに続く
ことができるから、コード化プロセスによりこれらの２
つの値以外の値が生成されていないので、２バイトの特
別文字を挿入できる。これらの特別文字は、異なる短縮
データ・セットを分離する、セット区切りの端である。

第10図で、統計表に基づいた確率計算が短縮される（米
国特許第4463342号参照）。モンテカルロ・カウンタ、C
NTは統計表Ｍ及びＫに何が行われるかを決定するために
使用される。モンテカルロ手法は、タスクを実行するか
又は実行しない決定が、決定論的なアプローチではなく
疑似ランダム数から決定された回答に基づく場合に用い
る。CNTカウンタは４ビット２進アップ（UP）・カウン
タである。CNTカウンタは第４図の初期化ステップで０
にリセットされる。第10図のブロック500に示すよう
に、最初のステップは、最大確率記号MPSが処理された
か最小確率記号LPSが処理されたかを判定することであ
る。DBITとＭ統計が等しいときはMPSである。さもなけ
ればLPSである。もしLPSが処理されたなら、間違った推
測であり、該推測値発生の確率値は直ちに減少すべきで
ある。判定ブロック528で、もしＫが既に１ならば、ブ
ロック532で、統計Ｍは逆転され、推測値の反対の値が
保管される。もしMPSが処理されたならば、正しい推測
であり、この推測値発生の確率値は増加すべきである
が、増加は常にＫの最大値に達するのが速すぎ誤り推測
のペナルティがずっと高くなるから、常にそうするとは
限らない。それゆえ、モンテカルロ・カウンタを用いて
Ｋをランダムに増加させる。もし判定ブロック510でＫ
が１に等しく、ブロック516でCNTカウンタの２つの下位
ビットが１であれば、ブロック518で、Ｋは増加され
る。もしＫ統計値が２に等しく（ブロック512）、カウ
ンタCNTの３つの下位ビットが１に等しければ（ブロッ
ク513）、ブロック518でＫは増加される。もし統計Ｋが
３に等しく（ブロック514）、CNTカウンタの４ビット全
てが１に等しければ（ブロック524）、値Ｋは増加され
る。もしＫが４に等しければ、Ｋは既に最大値であるか
ら、そのままである。Ｋの値にかかわらず、MPSの場
合、CNTカウンタはブロック504及び518で増加される。

第11図〜第15図は復号プロセスの処理の流れを示す。第
11図はチャネル・アダプタに送られたデータ・セットの
復号プロセス全体の流れ図を表わす。本発明の良好な実
施例では、データ・セットは最後のセット即ち残りの部
分の外は512バイトである。各データ・セットについ
て、例えば、第３図の復号器124は最初、既知の状態に
なるように初期化される。統計表は各データ・セット毎
には初期化されず、チャネル・ストリームのレコード毎
に初期化されるだけである。各データ・セットの始まり
でラン文字レジスタは初期化され、ラン・モード表示は
リセットされる。復号器のＣレジスタは短縮されたデー
タの最初のバイトの最上位ビットでロードされる。非ラ
ン・モードでは復号プロセスは一度に１ビット復号す
る。８ビット毎に１バイトにアセンブルされ、チャネル
・データのバイトとして送られる。ラン・モードの場
合、反復バイトはチャネル・データのバイトとして送出
され、当該データ・セットの全ての短縮されたデータが
使用され且つデータ・セットの全てのビットが複号され
るまでプロセスは継続する。ブロック308で、もしラン
・モードがセットされていれば、ラン事象を復号するブ
ロック322に進む。ラン事象復号は第13図に示すように
処理され、DBITレジスタに値が戻される。もしDBITが１
なら（ブロック324）、反復されたビットはラン・モー
ドでコード化されており、それゆえラン文字は文字レジ
スタに複写され（ブロック326）、ブロック314で送出さ
れる。もしDBITが０なら、文字復号ブロック310は第12
図に示すように処理される。データ・バイトは復号され
て文字レジスタに送り込まれ、該バイトは文字レジスタ
から送出される。ブロック316で、もしラン文字レジス
タが文字レジスタに等しければ、ブロック238に進み、
ラン・モードをセットする。もしラン文字が文字に等し
くなければ、ラン・モードはリセットされ（ブロック31
8）、文字レジスタはラン文字レジスタに複写される
（ブロック320）。全ての短縮されたデータが使用され
且つチャネル・データのセットの全てのバイトが短縮解
除されるまでプロセスは継続する。

第11図のブロック310の文字復号プロセスは第12図に示
す。例えば、第11図のブロック308で、バイトが反復さ
れないときはラン・モードは継続されないことを示し、
ノー・ラインを経由してブロック310に進む。即ち、第1
2図のブロック330で、最初のビットの統計が取出される
アドレスADDRは１にセットされる。非ラン・モードで
は、各ビットは第12図に示す文字復号プロセスにより複
号される。複号されるバイトの８ビットの各々について
統計が取出され、第14図に示す復号プロセスによりビッ
トが復号される。そして更新された統計は再び統計表に
記憶される。最初のビットの統計が取出されるアドレス
は、前述のようにブロック330で１にセットされる。ブ
ロック332で、復号ビットはDBITレジスタに入力され
る。DBITレジスタで復号された最初のビットは文字レジ
スタの最上位ビットに記憶される。次のビットの復号の
ため、ブロック334で、アドレスADDRを１ビット左シフ
トすることにより新しい統計表アドレスが生成すると同
時に当該ビットにDBITを書込む。復号された次のビット
は文字レジスタの最上位の次のビットに記憶される。こ
れは、ブロック336で、文字レジスタの文字を左シフト
し該レジスタにDBITを書込むことにより行われる。判定
ブロック338に示すように、前記プロセスは８回反復さ
れ、全てのビットを複号して文字レジスタに入れる。

第11図のブロック322のラン事象復号は第13図に示す。
統計表のアドレス０はラン・モードに使用される。それ
ゆえ、第13図のブロック340でアドレスADDRは０にセッ
トされる。そして復号されるビットはブロック342でDBI
Tレジスタに入力され、ラン事象を復号するためにビッ
ト復号が実行される。

第12図のブロック332のビット復号プロセスは第14図に
示す。ブロック350で、ADDR信号により指定されたアド
レスで統計Ｍ及びＫが統計表から取出される。統計Ｍは
推測値を示す１ビット値であり、統計Ｋは２ビットの確
率値である。統計Ｋは１から４までの数を選択できる。
統計Ｍ及びＫは第15図に示すデータ・ビット計算のプロ
セスを用いてビットを復号するのに使用される。ブロッ
ク352のデータ・ビット計算プロセスで、ビットが復号
されDBITレジスタに記憶される。そしてブロック354
で、複号されるデータに統計を適応させるように統計は
更新される。これは第10図に示す統計計算プロセスで行
われる。統計Ｍ及びＫで新しい統計が計算された後、ブ
ロック356で、統計Ｍ及びＫはADDR信号により指定され
たアドレスで再び統計表に記憶される。

第15図は第14図のブロック352のデータ・ビット計算プ
ロセスを示す。復号プロセスはコード化プロセスと同じ
タイプのＡレジスタ及びＣレジスタを使用する。Ａレジ
スタは正規化レジスタでありコード化プロセスと同じよ
うに使用される。本発明の良好な実施例では、Ａレジス
タ及びＣレジスタはどちらも４ビットを有する。復号サ
イクルのための第４図の初期化ステップでは、Ａレジス
タ及びＣレジスタはどちらも０になるように初期化され
る。そして短縮データの最初の４ビットはＣレジスタに
シフトされる。第15図のブロック700の最初のステップ
はデータ・ビットを計算するため最大確率記号（MPS）
がコード化されたか最小確率記号（LPS）がコード化さ
れたかを判定する。Ｃレジスタで減算が試行され、MPS
がコード化されたかLPSがコード化されたかを判定す
る。確率係数PFは統計Ｋから生成される。PFはＡレジス
タ及びＣレジスタで算術演算を実行するために使用され
る４ビット値である。確率係数PFは第９図のコード計算
プロセスの場合と同様に統計Ｋから変換される。

Ｃレジスタの内容からPFを引き、もしＣレジスタに借り
が要求されれば、LPSがコード化されているに相違な
く、さもなければ、MPSがコード化されている。判定ブ
ロック700の結果がLPSなら、ブロック710でＡレジスタ
は０にリセットされ、ブロック712でＣレジスタがＫ回
左シフトされる。Ｃレジスタから出るビットは破棄さ
れ、Ｃレジスタに短縮されたデータが書込まれる。LPS
があることは判定されているから、コード化プロセスで
間違った推測がなされたに相違なく、ブロック714でDBI
TはＭの値の逆数にセットされる。MPSが決定されている
場合は、コード化プロセスで正しい推測がなされている
に相違ないから、ブロック701で、DBITレジスタは値Ｍ
にセットされる。ブロック702でＣレジスタの内容から
確率係数PFを引く。新しい４ビット差は再びＣレジスタ
に記憶される。PFもＡレジスタの内容から引き、新しい
差は再びＡレジスタに記憶される。判定ブロック704
で、もし引算のプロセスでＡレジスタに借りがあれば、
ブロック706及び708で、Ａレジスタ及びＣレジスタはど
ちらも１ビットずつ左シフトされる。Ａレジスタは０を
書込み、Ｃレジスタは短縮されたデータのビットが書込
まれる。Ｃレジスタからシフトされたビットは破棄され
る。

短縮データをＣレジスタにシフトするとき、桁上げを防
ぐための詰込みビットは除去されねばならない（第６図
のコード計算プロセス参照）。詰込みビットは、次のコ
ード・バイトの最上位４ビット−全０又は0001−があと
に続く全１バイトにより識別される。もし全１バイトに
続く４ビットが全０であれば、動作は行われず、４個の
０ビットが破棄されるだけである、即ちＣレジスタへの
シフトは行われない。もし全１バイトに続く４ビットが
0001であれば、Ｃレジスタの内容は１増加され、再びＣ
レジスタに記憶される。この場合、４ビット0001も破棄
され、Ｃレジスタにはシフトされない。もし全１バイト
に続く４ビットが全０でもなく0001でもなければ、全１
バイト及び後続のバイトはコード・ストリームに挿入さ
れた特別の文字である。これらの特別の文字は、セット
の間を区切るか又はレコードの終りを識別する、セット
文字の終り又はレコード文字の終りである。コード・ス
トリームでセット文字又はレコード文字の終りが現われ
ると、全てのデータ・ビットが復号され且つＣレジスタ
の内容が全０になる、即ちコード化プロセスの開始条件
になるまで復号プロセスは継続される。

短縮解除即ち復号シーケンスのチャネル速度は最もタイ
ム・クリティカルである。トリーのＩ番目のレベルのデ
ータ・ビットは、次に最も高いトリー・レベルのビット
を復号するのに必要なトリー・アドレスを計算するため
に復号しなければならない。統計表アクセス時間が復号
サイクル時間に等しい、単なるオーバラップの場合、２
つの隣接する統計位置がＩ番目のレベルのデータ・ビッ
トの可能な結果毎に１つ取出される。下位のアドレス・
ビットが既知であるとき、前記下位のビットは制御信号
になり、所要の統計を選択し短縮装置に送付する。同時
に、統計適応プロセスは該統計を操作し適切なデータ・
レジスタでそれを置換える。そしてデータ・レジスタは
統計表に再書込みされる。２つの独立したデータ・レジ
スタ・メモリ装置の要求は２重ポート・メモリの使用に
より解決することができる。２重ポート・メモリは２つ
の異なるメモリ・アドレスに対し読取り書込みを同時に
行う。１つのトリー・レベルで読取りもう１つのトリー
・レベルで書込むとき、レベルのアドレスは異なること
が保証される。それゆえ、統計表は読取り中は決して更
新されない。

本発明による短縮装置で使用されるプロセスの流れの更
に詳細な説明は特公昭62−28895号公報、米国特許第446
3342号及び特公昭63−6172号公報を参照されたい。本発
明による短縮装置はこれらの３特許の改良である。主た
る改良点として、２つの統計表が符号器及び複号器の各
々に包含され、統計表の２重化は共有のハードウェア、
即ち１つの符号器又は復号器の使用を可能にするととも
に、システムに互換性のあるフォーマットを２倍のスル
ープット・データ速度で可能にする。ハードウェアの数
が少なければ少ないほど費用は安くなる。

第４図のコード化プロセスはたぶん前述の米国特許第44
67317号明細書により最もよく理解される。該特許で使
用されているように、第１のレジスタはレジスタＣであ
り、第２のレジスタはレジスタＡである。良好な実施例
では、レジスタＡ及びＣの各々は４ビットを有し、各々
がシフト・レジスタとして作用するようにプログラムさ
れている。レジスタＣは、コード化サイクルでは圧縮さ
れたデータを含むが、複号サイクルでは圧縮されないデ
ータを含む。

第15図において、ブロック700で最大確率記号（MPS）が
示され、ブロック702で圧縮中に計算された合計からの
差をとり、圧縮されないデータを生成する外は、復号プ
ロセスはコード化プロセスにきわめて類似している。Ａ
レジスタ制御はコード化サイクルの場合と同じである。
Ａレジスタで借りの発生は正規化を生じるが、借りの不
足は制御動作を起こさせない。復号中、判定ブロック70
0からLPSが決定されると、Ａレジスタはブロックでリセ
ットされ、ＣレジスタはＫビット左シフトされ、０より
もむしろ復号される圧縮データが書込まれる。

F.発明の効果 本発明によれば、既知の最大時間内にデータをコード化
し復号することができるデータ短縮システムが提供され
る。

本発明によれば、全システムについて同じフォーマット
を保持しつつ更に高速のデータ速度を取得できるデータ
短縮システムが提供される。

更に本発明によれば、異なるスループット速度を用いる
短縮プロセスでフォーマット互換性を維持される高機能
の２進算術コード化プロセスが提供される。

更に本発明によれば、コード化及び復号プロセスの上方
及び下方フォーマット互換性を可能にする改良された短
縮方式が提供される。

更に本発明によれば、増大したスループット速度及び標
準的なスループット速度のどちらでコード化された媒体
も復号できる上方及び下方フォーマット互換性を提供す
ると同時に今日のレコード処理システムが要求するより
高い速度でデータを圧縮し処理するためにデータに固有
のスループット速度に適応できる短縮プロセッサが提供
される。

最後に本発明によれば、並列短縮装置の付加により増大
したスループット速度を持つ短縮システムに予測可能ス
ループット速度及びフォーマット互換性を提供すると同
時に複数の並列短縮システムを利用し且つデータ・スト
リームに適応可能な圧縮方式が提供される。

【図面の簡単な説明】

第１図は本発明に従って複数の並列接続された短縮プロ
セッサを有する周辺サブシステムの概要ブロック図であ
る。 第２図は第１図の２つの短縮プロセッサの相互接続の概
要図である。 第３図は第１図に示す１つの短縮プロセッサの詳細なブ
ロック図である。 第４図乃至第８図は第３図の符号器により実行される異
なる手順の流れ図である。 第９図は第３図に示す符号器の出力として確率の合計を
生成するコード化プロセスの流れ図である。 第10図は第３図の統計表に基づいた確率計算の流れ図で
ある。 第11図乃至第15図は第３図の符号器の処理の流れ図であ
る。 12……チャネル・アダプタ、16……短縮装置、17……短
縮プロセッサ、20……Ａバス、25、29……デマルチプレ
クサ／マルチプレクサ、36……符号器、38……復号器、
113……統計表、114……符号器、115……統計表、123…
…統計表、124……復号器、125……統計表、132……事
象カウンタ、134……インタフェース制御部、136……記
憶装置、138……事象カウンタ、140……記憶装置、142
……インタフェース制御部、144……速度整合バッフ
ァ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 リチヤード・アンソニー・リバーガー アメリカ合衆国アリゾナ州ツーソン、ノー ス・オカード・プレイス3382番地 (56)参考文献 特開 平１−119119（ＪＰ，Ａ) 特開 昭62−191914（ＪＰ，Ａ) 特公 昭63−6172（ＪＰ，Ｂ２) 特公 昭62−28895（ＪＰ，Ｂ２)

Claims (1)

【特許請求の範囲】
1. 【請求項１】包含する圧縮プロセッサの数がＮであり、
   各圧縮プロセッサは１つの符号器と１つの複号器を有
   し、前記符号器と複号器の各々が保有する統計表の数は
   １より大なるＭである算術２進圧縮システムにおいて、
   ｎ≦Ｎかつｍ≦Ｍとして、ｎ個の圧縮プロセッサの各々
   はｍ個の統計表を使用してコード化するために等しいサ
   イズのデータ・セットを処理する、算術２進圧縮システ
   ムであって、 ｑ＝コード化されるデータ・セットの数 ｉ＝データ・セット番号 ｊ＝ｉモジューロｎ ｋ＝（i/n）モジューロｍ ただし（i/n）はi/nの整数部分、 ｎとｍとの積は一定 であるものとして、 順次のデータ・セットｉを圧縮プロセッサｊに供給する
   よう該圧縮プロセッサｊによるデータ・セットｉの受領
   に応答して次のデータ・セツトｉ＋１を次の圧縮プロセ
   ッサに供給するための各圧縮プロセッサに備えられた手
   段と、 データ・セットｉを処理する圧縮プロセッサｊに統計表
   ｋを使用させるため各圧縮プロセッサの符号器または複
   号器に統計表を関連させるための手段と、 前記符号器または複号器が１つのデータ・セットを処理
   するときの統計集計プロセスを表すステートメントを前
   記符号器または複号器記憶に関連された統計表に記憶
   し、かつ該符号器または複号器が後続のデータ・セット
   を処理するにときに該データ・セットの統計を記憶する
   ように前記符号器または複号器記憶に関連された統計表
   を更新する手段と、 を含み、 これによりｎの値に拘わらず各圧縮プロセッサの１複号
   器に関連した１統計表が１符号器に関連した１統計表の
   統計集計プロセスを通じて圧縮された１データ・セット
   の複号に関する統計を記憶するようにしたことを特徴と
   するデータ圧縮システム。