JPH0253329A - 圧縮符号化方法及び復号方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、ソース・データ・ストリングの圧縮表現の生
成方法に関する。本発明は、特に、高能率の乗算なしの
算術符号化に関する。算術符号化は、データ処理システ
ムでデータを圧縮するのによく用いられる技術である。

Ｂ、従来技術及びその問題点 かかる圧縮は、普通、大規模データ・ベースを特徴づけ
るシンボルに関連する、高度の相関関係を持ち非一様で
ある統計分布によって可能とされる。ソース・データが
デジタル形式で表現されるとき、圧縮の目的は、２オリ
ジナルのソース・データ・ストリングよりもデータ、ビ
ット数の少ないデータ・ストリングを出力することにあ
る。統計的に有意なソース・データ・ストリングのサン
プルが圧縮されるとき、圧縮出力データ・ストリングの
予想長さは、ソース・データ・ストリングの°“エント
ロピー°゛に対応する。

ソース・データの圧縮方法の１例として、算術符号器が
Ｒ１５ｓａｎｅｎによって開発され、それはまず下記の
論文で発表された。

”Ｇｅｎｅｒａｌｉｚｅｄ　Ｋｒａｆｔ　Ｉｎｅｑｕａ
ｌｉｔｙ　ＡｒｉｔｈｍｅｔｉｃＣｏｄｉｎｇ　、　Ｉ
ＢＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈ　ａｎ
ｄＤｅｖｅｌｏｐｍｅｎｔ、　Ｖｏｌｕｍｅ　２０＋　
Ｎａ３　、１９７６年５月Ｒ１５ｓａｎｅｎ？こよって
紹介された算術符号化法によれば、マルチ・アルファベ
ット・データ、つまり各シンボルがマルチ・シンボル・
アルファベットの中で見い出せるようなデータの圧縮が
可能となる。

算術符号化法を採用するためには、まずソース・アルフ
ァベットの中の各シンボルの発生確率を決定することが
必要である。普通、ソース・データ・ストリング毎に確
率は変化する。したがって、テレビ・イメージに相当す
るデータを圧縮するのに算術符号化法が用いられる場合
、まず各画素の発生確率が決定されねばならない。この
決定はリアル・タイムで行われることもあるし、統計的
に予定されることもある。しかしながら、確率の決定法
は本発明の特徴とは関係ない。本発明は、確率の決定法
に関係なく、等しく適用可能である。

ソース・アルファベット内の各シンボルの発生確率を決
定した後、各シンボルの累積確率が決定されよう。した
がって、データ・ストリングの第１番目のシンボルにつ
いての累積゛確率５（１）は−ｉにゼロに等しい。また
、第１１番目のシンボルについての累積確率は、先行す
る（ｎ−１）個のシンボルの各々の発生確率の和に等し
くなる。

算術符号化法では、普通、出力データ・ストリングは、
単位区間（０，１）の中の２進少数として表現される。

Ｌａｎｇｄｏｎ　Ｊｒ、が”Ａｎ　Ｉｎｔｒｏｄｕｃｔ
ｉｏｎｔｏ　Ａｒｉｔｈｍｅｔｉｃ　Ｃｏｄｉｎｇ　、
　ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆＲｅｓｅａｒｃｈ　ａ
ｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ、　Ｖｏｌｕｍｅ　２Ｂ
、Ｎ０、２　、　１９８４年３月、で説明しているよう
に、算術符号化は該単位区間の細分割に関係している。

この細分割は、ソース・アルファベット内のシンボルご
とに、単位区間中にコード・ポイントＣ，，をマークす
ることによって達成される。コード・ポイントの各々は
、先行シンボルの発生確率の和に等しい。各コード・ポ
イントの右側の小区間Ａｎの巾の大きさは、対応するシ
ンボルまでのソース・データ・ストリングの発生確率を
表現する（第３図参照）。

例えば、そのアルファベットがａｉからａｆｆｉまでの
シンボルからなり、シンボルの発生確率がそれぞれｐ　
（０）、・・・、ｐ　（ｍ）に等しいソース・データ・
ストリングを考えてみよう。ソース・データ・ストリン
グがａｉａＳ　ａｉ・・・・・・であるなら、第１シン
ボルａ０は部分区間〔０、ｐ（０））の範囲内で符号化
される。これは、巾Ａ１がシンボルａ０の発生確率に単
純に相当するｐ（０）に等しい、元の単位区間内の第１
小区間を表現している。ソース・データ・ストリングの
第２シンボルを符号化するためには、シンボルａ０の発
生確率を条件とするａｉの発生確率が決定されねばなら
ない。さらに、第２シンボルａｉに関連する累積確率を
計算しなければならない。かくして、第２シンボルａｉ
に対応する小区間は、ａｏに対応する第１部分区間内に
ある第２小区間となる。数学的には、第２部分区間の巾
Ａ２はｐ　（０）　＊ｐ（５）つまり、２つのシンボル
ａ０、ａｓの発生確率の積に等しい。単位区間内にある
第２小区間の出発点は、第１小区間の巾ＡＩと第２シン
ボルａｉに関連する累積確率５（５）に依存する。つま
り、それらの積Ａ、＊Ｓ　（５）に等しい。このように
、ソース・データ・ストリングの各シンボルが単位区間
の中で相次いで符号化されていくにつれて、部分区間も
相次いで生成され、その各々が特定のコード・ポイント
と幅によって特定され得る。現在の部分区間についての
コード・ポイントは、従前の区間又は部分区間の範囲内
の、現在の部分区間に対応する。上述のように、これは
現在シンボルに関連する累積確率に等しい。したがって
、第ｎ番目の部分区間に関連するコード・ポイントは、
第（ｎ−１）番目の部分区間の幅に先行する（ｎ−１）
個のシンボルの累積確率を掛けたもの、つまりＡ、Ｓ　
（ｎ）に等しい。新しい部分区間の幅は、ソース・デー
タ・ストリングについてそれまで符号化されたすべての
シンボルの確率の積、つまりｐ　（０）　＊ｐ　（５）
　＊ｐ　（３）に等しい。幅Ａ７と第ｎ部分区間のコー
ド・ポイントＣ７に対応するデータによって、ソース・
データ・ストリング中の最初から（ｎ＋１）個目までの
シンボルが符号化される。したがって、算術符号器はこ
れらのデータを記憶するのに２つのメモリ・レジスタを
必要とし、それらは通常それぞれＡレジスタ、Ｃレジス
タと呼ばれる。

部分区間の幅は確率の積に等しいのであるから、２つの
ファクタが浮かび上がってくる。まず、符号化されるソ
ース・データ・ストリングのシンボル数が多くなればな
るほど、算術符号表現を規定する部分区間の幅は減少す
る。（というのは、個々の確率は必ず１より小さくなけ
ればならないからである）。さらに、算術符号化を効率
よくインプリメントするには、そのプロセスにおいて乗
算を繰り返さなければならない。

データ・ストリングを構成するシンボルの正確な発生確
率に基づくとき、算術符号器はソース・データ・ストリ
ングのエントロピーに相等する最適な圧縮結果を生成す
る。しかし、従来の実際のインプリメンテーションでは
、確率を正確に決定することの困難さ故に、近似を導入
しがちであった。その結果、算術符号演算の効率が低下
し、出力データ・ストリングに含まれるシンボル数が理
論的な最低限（エントロピー）を上回ってしまう。

さらに、部分区間の幅を決める度に必要とされる乗算を
なくするために、さらなる近似が導入されてきている。

算術符号器は、メモリ・レジスタのビット数が有限であ
るようなコンピュータでインプリメントされる。乗算に
関連する問題の１つは、確率の乗算を続けていけばいく
ほどより小さな区間が生成されるので、そのような乗算
をわずか数回やった後には、その結果体じた部分区間が
小さすぎてコンピュータ・レジスタに満足にストアでき
ない、という事実に起因する。例えば、各レジスタが１
６ビツトであるときに、、確率の乗算を繰り返した結果
、積が１−１′より小さくなったならば、積はレジスタ
をアンダーフローしてしまう。言い換えると、レジスタ
はゼロで満たされ、確率積の有意なビットは失われてし
まう。一連の乗算に伴う別の問題は、実行に要する時間
である。

上記第１の問題点は、正規化（ｎｏｒｍａｌｉｚａｉｉ
ｏｎ）と呼ばれる技術によって解決された。この技術で
は、確率積は浮動小数点表記でストアされる。これを実
行するべ（、別のビット・レジスタが用いられ、部分区
間の幅に対応する（２を基数とする）指数をストアする
。そのとき、２進小数の最も桁の高い１は最も左の位置
ヘシフトされる。したがって、明らかに１６ビツト・レ
ジスタにストアできない１．０１０１　Ｘ２−”°なる
２進小数であっても、１゜０ＬＯＬＥ−２０として満足
にストアできる。ここで仮数と指数は別個のレジスタに
ストアされる。仮数のＭＳＢはこのように常に１となる
ように配置されるので、仮数レジスタにストアされる実
際の数は常に１．０より大きい。

上記第２の問題点（乗算実行時間）は、いわゆる「乗算
なし」の算術符号器によっである程度解決された。２進
算法を用いるコンピュータでは、乗算はシフトと加算オ
ペレーションの繰り返しとしてインプリメントされる。

「乗算なし」という言葉は、従来、様々に用いられてお
り、各符号化ステップについてのシングル・シフト、ま
たはシングル・シフト・アンド・アト・オペレーション
のどちらかを意味してきた。厳密に言うと、数学的には
シングル・シフト演算も乗算をしたことに変わりはない
。しかしながら、多数のシフトと加算演算を伴う厳密な
算術符号器のインプリメンテーションに関連する乗算に
比べて、このやり方では費す時間がはるかに少なくなる
。したがって、「乗算なし」なる語は、しばしば乗算が
大幅に簡素化された、あるいは減少した、という意味に
用いられる。従来技術、及び本発明において「乗算なし
」なる語が用いられるのは、このような文脈においてで
ある。

米国特許第４２８６２５６号明細書では、演算の数を減
らした算術符号化の方法及び装置が開示されている。そ
の特許発明によれば、現在のコード・ポイントを符号化
するのに先立って、部分区間の幅に対応する内部積の１
つを切捨てることによって乗算を簡略化している。しか
しながら、この方法は２進ソース（つまり、シンボルを
２つだけ持つアルファベット）にしか適さない。つまり
、この方法は、ソース・データ・ストリングの各シンボ
ルを、確率の高い事象または低い事象のどちらかとして
符号化することはできるけれども、マルチ・アルファベ
ット・コードには適さない。

米国特許４６５２８５６号明細書では、乗算なしのマル
チ・アルファベット算術符号が開示されている。そこで
は、部分区間の各々が上述のような浮動小数点形式でス
トアされる。そして、Ａレジスタに収められる仮数は、
０．１より大きな２進小数とされる。該明細書で提唱さ
れる近似方法によれば、可変の基準を採用して、部分区
画の仮数を（２進の）０．１に正確に切り捨てるか、も
しくは１に切り上げる（ｒｏｕｎｄ　ｕｐ）かのどちら
かを行わせる。

このような近似を使ってもなお所望の圧縮を達成できる
けれども、効率の点ではロスがある。換言すると、圧縮
データ・ストリングを表現するために、最低限のビット
数より多くのビット数が必要とされる。このような非能
率は、圧縮対象のソース・データの性質に依存する。

上記米国特許４６５２８５６号の発明の大きな問題点は
、Ａレジスタの内容を切り上げることによって該当する
シンボルの確率が現実の値よりも大きな値に近似される
ことに起因する。アルファベットのすべてのシンボルに
ついての確率の和が１．０を越えられないことを確実に
するために、上記特許発明では、最後の部分区間を次の
ように近似する。

この近似（概算）によれば、アルファベットのすべての
シンボルの確率の和が１に等しいことが保証されるけれ
ども、これは、最後の部分区間を非常に小さなものとし
てしまい、符号化の能率が非常に悪くなるという犠牲を
伴う。

Ｃ９問題点を解決するための手段 本発明の目的は、上記従来技術に関連する問題点を大幅
に減少させ、あるいは除去する、高効率で乗算なしの算
術符号化法を提供することにある。

本発明によれば、ソース・データ・ストリングの圧縮表
現Ｒ（ｃｏｍｐ）を生成する方法が提供される。

該方法の内容は以下に示すとおりである。

各シンボルは、（ｍ＋１）個のシンボルａＯＳ・・・、
ａｉからなる有限のセットから取り出される。

上記圧縮表現は所定の範囲の数値であり、ストリング中
の相次ぐシンボルに対応する相次ぐサイクルにおいて帰
納的に生成される。

各シンボルａｉについて、確率値ｐ（１）と累積確率値
Ｓ　（１）がアベイラブルである。

ここで、上記累積確率値は、 Ｓ　　（１）　　＝ｐ　　（０）　　＋ｐ　　（１）　
　＋・・・・・・＋ｐ　（ｉ−１）　　（ｉ＝１、・・
・、ｍ）Ｓ（０）＝０ である。

一対のシフト・レジスタＡ及びＣが用いられる。

それぞれ、２進デイジット６個分の位置を有している。

特に、本発明の特徴は、以下の点にある。

（ａ）まず、Ｃレジスタの内容をすべてゼロにセットす
るとともに、Ａレジスタの内容を所定の値にセットする
。

次に、ストリングの相次ぐシンボルａｉごとに、（ｂ）
Ａレジスタの内容を取り出し、所定の基準に照らして該
基準を下回る下位の゛１°゛ビットを削除する（切り捨
てる）ことによって、スケーリング・ファクタにを決定
し、 （ｃ）Ｋ＊５（１）の値をＣレジスタの内容に加算し、 （ｄ）　（ｄ１）シンボルａｉがシンボルａｉでないな
らば、値に＊ｐ　（１）をＡレジスタに挿入し、（ｄ２
）シンボルａｉがシンボルａｌｌならば、値に＋３　（
１）をＡレジスタから引き算することにより、Ａレジス
タの内容を決定し、（ｅ）Ａレジスタの内容が所定の範
囲内に来るまで、ＡレジスタとＣレジスタを両方とも所
定の向きにシフトし、空いた位置にはゼロを充填し、（
ｆ）シンボルａｉがストリングＳＴＲの最終シンボルで
ないならば、ステップ（ｂ）ないし（ｅ）を繰り返し、
シンボルａｉがストリングＳＴＲの最終シンボルならば
、Ｃレジスタの内容を上記所定の向きにＷ位置だけシフ
トする。

以上のステップを経てＣレジスタから外ヘシフトされた
一連の２進デイジツトは、シンボル・ストリングＳＴＲ
の圧縮表現Ｒ（ｃｏｍｐ）を構成する。

したがって、本発明によれば、ソース・データ・ストリ
ングＳＴＲ内の各シンボルが相次いで符号化されると、
その代表圧縮符号がＣレジスタから外ヘシフトされ、必
要に応じて後処理に供される。普通は、圧縮されたデー
タが相次いでＣレジスタから読み取られ、その後適当な
復号装置に送られる。そこで圧縮済ストリングは復号さ
れ、オリジナルのソース・データ・ストリングＳＴＲが
再構成される。上記従来の算術符号化と同じく、本発明
法もファースト・イン・ファースト・アラ）（ＦＩＦＯ
）ルーチンであり、ソース・データ・ストリングＳＴＲ
中の最初のシンボルが最初に符号化される。

好適な実施例では、Ａレジスタは値ｉ、　ｏ　ｏ　ｏに
初期設定されるとともに、圧縮後の算術符号は０と１の
間の（直をとる。

ソース・データ・ストリングＳＴＲ内のシンボルの符号
化が次々に行われるので、ＳＴＲ中の後続シンボルにつ
いて展開された符号が、“キャリー・オーバー゛効果ゆ
えに先行シンボルについて既に生成された符号に影響を
及ぼすことがある。

このキャリー・オーバー効果は文献等で十分に知られた
ことであり、いくつかの解決策が発表されている。その
うちの何れを本発明とともに用いても差し支えない。

Ｄ、実施例 第３図は、確率ｐ　（１）のテーブルと、５つのシンボ
ルａ０〜ａ４からなるシンボル・セットについての累積
確率Ｓ　（１）を、単位区間〔０、ｌ）上にプロットし
たコード・ポイントとともに示したものである。既に説
明したように、符号化対象のシンボルａｉについての確
率ｐ　（１）と累積確率Ｓ　（１）に基づいて、シンボ
ル・セットに由来する相次ぐシンボルを帰納的に単位区
間内の部分区間として符号化するプロセスは、算術符号
化それ自身の特徴である。第１図は、本発明による符号
化法の流れ図である。４つの主要なステップには１から
４までの番号が付されている。その理由は、第２図を参
照することにより、後で明らかになる。

スタート時点では、Ｃレジスタは０、　ｏ　ｏ　ｏに、
Ａレジスタは１．０００、にそれぞれセットされる。

ステップ（１）では、ソース・データ・ストリングＳＴ
Ｒ中の各シンボルについて、確率ｐ　（１）及び累積確
率Ｓ　（１）が決定される。これは既知のいくつかの方
法の何れかを用いて実行できる。

あるいは、固定かつ予定された確率値セットを用いるこ
ともできる。次に、ステップ（２）で示されるように、
Ａレジスタの内容を取出し、２進の“′１°゛のデイジ
ットのうち上位２つまでを残して残りを切り捨てること
により、スケーリング・ファクタＫが決定される。Ａレ
ジスタが現在部分区間の幅を表現する一方、スケーリン
グ・ファクタには事実上現在部分区間の幅の近似である
。この幅は（２進数の）１．００００と１．１１１１・
・・の間に正規化される一方、スケーリング・ファクタ
には上位２つまでの“°１′″を残し他を削除して得ら
れるＡレジスタの内容の近似値である。

以下の記載においては、（ｍ＋１）個のシンボルからな
る有限セットのシンボルを、ａ０、ａｌ・・・、ａｉと
表記する。シンボルａｌについての確率と累積確率は、
それぞれ、ｐ　（１）及び５（１）と表記する。したが
って、例えば、マルチ・アルファベット・シンボルの８
番目のシンボルが“ｈｌｌならば、ａｓ　＝）１であり
、その確率はｐ（８）及び５（８）ということになる。

ステップ（３）は、ソース・データ・ストリングＳＴＲ
の各シンボルについて、ＫとＳ　（１）の積がＣレジス
タに加算されるとともに、ｉ＜ｍならば、Ａレジスタは
に＊ｐ　（１）にセットされ、ｉ＝ｍならば、Ａレジス
タの内容からに＊Ｓ（ｍ）が引き算されることを示して
いる。したがって、符号化対象のシンボルがマルチ・ア
ルファベット・シンボル中の最終シンボルに該当しない
とき、Ａレジスタは単純に現在シンボルの確率とＫの積
にセットされる。ここで、Ｋは現在部分区間の幅の近似
である。一方、符号化対象のシンボルが該アルファベッ
トの最終シンボルに該当するとき、Ａレジスタの値は、
Ｋと該最終シンボルの累積確率との積の分だけ減らされ
る。これは、確率ｐ　（１）は近似にすぎないという事
実を埋め合わセスる。実際、マルチ・アルファベットの
すべてのシンボルについての確率の和が１に等しいこと
を保証する。このことは、以下のことから導かれる。

アルファベットの第ｍ番目のシンボルについて、Ａ　−
Ａ　−Ｋ　＊　Ｓ　（ｍ） となる。そして、ＫはＡの近似であるから、Ａ　−Ａ　
−Ａ　＊　Ｓ　（ｍ） したがって、Ａ　−Ａ　（１−Ｓ　（ｍ）　）つまり、
　　　Ａ＝Ａ　（１−ｐ　（０）　−ｐ　（１）・・・
・・・・・・−ｐ（ｍ−１）） すなわち、Ａ＝Ａ＊ｐ（ｍ） これはまさに要求されるところである。

アルゴリズムの次のステップ（４）では、Ａレジスタの
内容が所定の範囲に収まるように、Ａレジスタが正規化
される。Ａレジスタの内容には、適当な２の倍数が掛は
合わされる。これは、簡単なシフト・オペレーションで
もって、Ａレジスタの現在の内容に応じて定まる回数分
Ａレジスタを左ヘシフトすることによって達成される。

Ｃレジスタも同じビット数分だけ左ヘシフトされる。そ
の結果、Ｃレジスタの上位のビットが読み取られ、それ
はＳＴＲについての算術符号の一部を構成することにな
る。このような手順はＳＴＲ中のすべてのシンボルにつ
いて繰り返され、それが完了したなら、その時点のＣレ
ジスタの全内容が外にシフトされ、先に生成されていた
コード・ストリングと連結される。その結果できたコー
ド・ストリングは、圧縮済であるところの出力データ・
ストリングを表現している。

本発明に従う方法によれば、ＳＴＲ内のシンボル毎に、
圧縮出力データ・ストリングが帰納的に生成されること
がわかろう。コードが生成されると、Ｃレジスタの左へ
のシフト、及びＡレジスタの正規化が行われる。

本発明の方法は、以下の具体例を参照することによって
、最もよく理解されよう。

例 ソース・データ・ストリングは、５シンボル・アルファ
ベットから導かれるものとする。この５シンボル・アル
ファベットは、シンボルａ０・・・・・・ａ４から成り
、それぞれａｉｂ、ｃ、ｄ、ｅに合致するものとする。

各々の確率（２進数）は、以下の通りである。

ｐ　　（０）＝０．０００００１ ｐ　（１）＝０．００００１　１ ｐ　　（２）＝Ｏ，０ＯＯ１１０ Ｐ　　（３）＝Ｏ，０Ｏ１０１０ ｐ　　（４）＝０．１０１１００ このように、マルチ・システム・アルファベット中のシ
ンボルの数（ｍ＋１）は５に等しい。確率の合計が１に
等しい、つまり であることも確認されよう。

各シンボルについての累積確率は以下の通りである。

Ｓ　（０）＝Ｏ，０ＯＯＯ００ Ｓ　（１）＝Ｏ，０Ｏ０００１ Ｓ　（２）　＝０．０００１００ Ｓ　（３）＝０．０Ｏ１０１０ Ｓ　（４）＝０．０ＩＱ１００ 上述の好ましい実施例に従って、６ビツトのＡレジスタ
、Ｃレジスタを使って、５ＴＲ＝ｂ、ｃ、ｅ、ｄＳ　ａ
ｉｃ、ｂなるソース・データ・ストリングを符号化する
ものとしよう。

次のような処理が行われる。

まず、Ａレジスタが１．０００００に、Ｃレジスタが、
ｏ　ｏ　ｏ　ｏ　ｏ　ｏに、それぞれ初期化される。

小数点はわかっているものとするので、Ａレジスタ、Ｃ
レジスタの内容は、それぞれ １０００００．００００００になる。

第１シンボルｂ（−ａｌ）の符号化： に＝１．　　　　　　　　　ｉ＝１≠ｍｐ　（１）　＝
　００００１１　　　３（１）　＝　０００００ＩＣ＝
　０．０＋１．ＯｘＯ，０００００１＝　０．００００
０１結果： 但 、０００００１ 卜する： ０００００、１０００００ Ｃレジスタの境界を意味し 小数点の左の５つの２進ビ 八 、００００１１ Ａを正規化し、Ｃをシフ ｉ、１ｏｏｏ。

ここで、小数点は、 ている。このように、 ット０ＯＯＯＯは、結果め算術符号のうちの最初の５ビ
ツトがＣレジスタから外ヘシフトしたことを示す一方、
小数点の右側の６個の２進ビツト１０００００は、Ｃレ
ジスタの新たな内容を意味している。ここで、Ａ、Ｃ両
しジスタの内容については、左へのシフトに対応してゼ
ロが左詰めされる。８亥シンボルはストリングＳＴＲの
終りではないので、処理は継続する。

第２シンボルＣ（＝ａ＝）の符号化： に＝１．１　　　　　　　　　　ｉ＝２≠ｍｐ　（２）
　＝　０００１１ＯＳ　（２）　＝　０００１００Ｃ＝
　０．１０００００　＋１．Ｉ　Ｘ０、０００１＝０．
１００１１結果： Ａ　　　　　　　　　　　　Ｃ ，００１００１０００００，１００１１０Ａを正規化し
、Ｃをシフトする： 八　　　　　　旦 １．００１００　　０００００１００．１１００００こ
のシンボルはストリングＳＴＲの終りではないので、処
理は継続する。

第３シンボルｅ（＝ａｓ Ｋ＝１．００１ ｐ−（４）　＝　１１０１１０ ０ｉ＝なので、 Ａ＝１．００１００−１．００１ Ｃ士０．１１００００＋１．００１ Ｃ＞１なので、先頭の１ を生じさせる。

結果： ）の符号化 ｉ＝４＝ｍ Ｓ（４）　＝　０１０１００ ｘＯ，０１０１０＝０．１１００１０ ｘ０．０１０１０　　＝１．０００１１０はキャリー・
オーバー 人　　　　　　旦 、１１００１０　　０００００１０１．０００１１０Ａ
を正規化し、Ｃをシフトする： 人　　　　　　ρ １．１００１０　　０００００１０１０．００１１００
このシンボルはストリングＳＴＲの終りではないので、
処理は継続する。

第４シンボルｄ（＝ａｉ、）の符号化：Ｋ　　＝１．１
　　　　　　　　　ｉ＝３≠ｍｐ（３）　＝　００１０
１Ｏ５（３）　＝　００１０１０Ｃ＝Ｏ，０Ｏ１１００
＋１．Ｉ　Ｘ０、００１０１　＝０．０１１０１１結果
二 人　　　　　　旦 、００１１１１　　０００００１０１０．０１１０１１
Ａを正規化し、Ｃをシフトする： Ａ　　　　　　　　　旦 １．１１１００　　０００００１０１００１１．０１１
０００このシンボルはストリングＳＴＲの終りではない
ので、処理は継続する。

第５シンボルａ　（＝ａ０）の符号化：Ｋ　　−１，１
ｊ＝０≠ｍ ｐ　（０）　＝　０００００１　　　３　（０）　＝　
００００００Ｃ＝０．０１１０００　　＋　　０．０　
　＝０．０１１０００結果： Ａ　　　　　　　　　　旦 、００ＱＯＯ１０００００１Ｑ１００１１．０１１（１
００Ａを正規化し、Ｃをシフトする： 八　　　　　　　　　　　　〇 １．０００００　　０００００１０１００１１０１１０
００．００００００このシンボルはストリングＳＴＲの
終りではないので、処理は継続する。

第６シンボルｃ　（＝ａ２）の符号化二Ｋ　　＝１．Ｏ
ｉ　＝　２≠ｍ ｐ　（２）　＝　０００１１ＯＳ　（２）　＝　０００
１００Ｃ＝　Ｏ，Ｏ＋１．ＯＸ０、０００１００＝　０
．０００１００結果： Ａ　　　　　　　　　　　　　　Ｃ− ，０００１１００００００１０１００１１０１１０００
，０００１０ＯＡを正規化し、Ｃをシフトする： Ａ　　　　　　　　　　　　　　Ｃ １，１０００００００００１０１００１１０１１０００
０００１，００００００このシンボルはストリングＳＴ
Ｒの終りではないので、処理は継続する。

第７シンボルｂ（＝ａｉ）の符号化： Ｋ　　−１，１ｉ＝１≠ｍ ｐ　（１）　＝　００００１１　　　　Ｓ　（１）　＝
　０００００１Ｃ＝　０．０＋　１．ＩＸ０、００００
０１＝　０．０００００１結果： Ｃ ，０００１０００００００１０１００１１０１１０００
０００１，０００００１Ａを正規化し、Ｃをシフトする
： Ａ　　　　　　　　　　　　　　　　　　　　　Ｃ−１
，００００００００００１０１００１１０１１００００
００１００００，０１００００これはストリングＳＴＲ
の最後のシンボルなので、Ｃレジスタの内容を６位置分
シフトし、下に示す完全な出力ストリングを出力する。

Ｃ＝ＯＯ０００１０１００１１０１１００００００１０
００００１００００第２図は、第１図を参照して説明し
た方法のステップ（１）〜（４）の各々について、レジ
スタ間のデータの流れを示す。符号化法のステップ（１
）では、各シンボルａｉが人力ストリングから順に抽出
されるとともに、シンボルａｉが入力ストリングの最終
ストリングか否かを表示すべく、フラグ′エンド′°が
生成される。シンボルａｉは確率テーブルに入力される
。−二のテーブルは、そこから確率ｐ　（１）とＳ　（
１）を導くために、コンスタントに更新されてよい。フ
ラグ”ｉ＝ｍも生成されて、シンボルａｉがソース・ア
ルファベットの最終シンボルか否かを表示する。

ステップ（２）では、スケーリング・ファクタにを与え
るべく、Ａレジスタの内容が切り捨てられる。

ステップ（３）では、ｐ　（１）とＳ　（１）の値が、
それぞれ、ステップ（２）で求められた値にと掛は合わ
され、値に＊ｐ　（１）とに＊Ｓ　（１）が生成される
。この乗算では、単一のシフト・アンド・アト（シフト
及び加算）・オペレーションが用いられる。Ｋ＊ｐ　（
１）とに＊Ｓ　（１）は上述のように一次バッファにス
トアされる。値Ａとに＊Ｓ　（１）は減算器に送られ、
Ａ−に＊ｐ　（１）なる値が出力される。同様に、値Ｃ
とに＊５（１）は加算器に送られ、Ｃ＋に＊Ｓ　（１）
なる値が出力される。減算器の出力Ａ−に＊Ｓ　（１）
と値に＊ｐ　（１）は、フラグ’ｉ＝ｍ”とともに、選
択ロジック・ユニットに送られる。選択ユニットからの
出力は、ｉ＋ｍのとき、Ｋ＊ｐ　（１）に等しく、ｉ＝
ｍのとき、Ａ−に＊Ｓ　（１）に等しい。

最後に、ステップ（４）では、シフト・コントロール・
ユニットがＡレジスタの内容が指定された範囲内に収ま
るまで、ＡとＣのレジスタをシフトする。ストップ・フ
ラグが生成されると、それによってシフト・オペレーシ
ョンがストップする。。

ステップ（１）で導かれた“エンド”′フラグはシフト
・コントロール・ユニットへ渡されるので、入力ストリ
ングの最後では、シフト・コントロール・ユニットがＣ
レジスタを６位置分シフトさせ（なぜなら、６ビツトの
Ａレジスタ、Ｃレジスタを使っているから）、Ｃレジス
タを空にする。ストップまたはエンド・フラグに応答し
てシフト・コントロール・ユニットがＣレジスタをシフ
トさせるのにつれて、Ｃレジスタから外ヘシフトされた
データが連結され、出力ストリングを形成する。

必要ならば、第１図及び上述の例を参照して説明したよ
うに、キャリー・ビットが出力ストリングに連結される
。

上述した例では、常にＡレジスタの内容が１．０から２
．０の範囲に収まるように、つまりＡε〔１，２〕とな
るように、Ａレジスタの正規化が行われている。しかし
、Ａレジスタの正規化は、０．１と１．０（２進値）の
範囲で行われてもよいし、あるいはその範囲を適宜２の
倍数を掛けて変更できることもすぐに理解できよう。こ
のような範囲が変わっても、同じアルゴリズムを使える
。しかし、確率を適宜２の倍数で割ったり、あるいは掛
けたりすることが必要になる。さらに、上述した特定の
例では、ソース・データ・ストリングＳＴＲの第３シン
ボルを符号化するときにキャリー・オーバーが生じる。

上記の例では、結果のコードがデコーダに送られるのは
、ソース・データ・ストリングＳＴＲのすべてのシンボ
ルが符号化されてからである。明らかに、Ｃレジスタか
ら外ヘシフトされ内容を連結してストリングを形成して
ストアしておき、ＳＴＲ全部が符号されてから圧縮デー
タが生成されるや否やそれをリアル・タイムで転送する
ことが現実には望ましい。

本発明の別の実施例としては、にを生じさせる近似を改
良した修正方法がある。前記実施例のようにＡレジスタ
の１のうち上位３番目以後を切り捨てる代りに、上位４
番目以後の１を切り捨てても本発明の実施は可能である
。もつとも、前記実流側の場合に比べて、シフト・アン
ド・アト・オペレーションがもう１回必要になるという
代償を伴うことになる。明らかに、このような改良は、
さらに押し進めて行くことができ、その極限ではスケー
リング・ファクタＫがＡレジスタの内容と全く等しくな
る。これは、近似を用いない算術符号化ということにな
る。しかしながら、上記図面を参照して説明した方゛法
によれば、Ａレジスタの内容を近似しつつも、９８％を
越える効率を達成できる。

本発明の原理に従って導かれた圧縮出力データ・ストリ
ングの復号は、実質的に符号化の逆である。したがって
、まず、Ａレジスタが１（１，０００・・・・・・）で
満たされ、Ｃレジスタは圧縮済ストリングＲ（ｃｏｍｐ
）の最初の６個のシンボルで満たされる。

次に、ソース・データ・ストリングＳＴＲが相次いで復
号されていくわけだが、その際、Ｃ≧に＊５（ｊ）とな
るｊのうち、最大のものが決定される。ここで、Ｋ及び
Ｓ　（ｊ）は、符号器に関して説明したものと同じであ
る。Ｃは、Ｃレジスタの外でＭＳＢの隣りに２進小数点
を持つ２進小数として解釈される。このようにしてｊが
決定されたなら、現在シンボル、つまり現段階で出力さ
れるシンボルはａｊである。ここで、ａｏ・・・ａｉｌ
は、上述の定義どおりのマルチ・アルファベットである
。

続いて、Ｃレジスタの内容から、Ｋ＊Ｓ　（ｊ）の値が
引き算される一方、Ａレジスタの内容は、ｊ＝ｍか否か
に従って修正される。ｊ≠ｍならば、Ｋ＊ｐ　（ｊ）の
値がＡレジスタに挿入される。他方、ｊ−ｍならば、Ａ
レジスタの内容からに＊５（ｊ）が引き算される。

最後に、Ａレジスタの内容が、所定の範囲に収まるまで
、つまりＡＥ　（１，２）となるまで、Ａレジスタ及び
Ｃレジスタが所定の向きにシフトされる。Ａレジスタの
中の空いた位置（ビット）は、圧縮済データ・ストリン
グＲ（ｃｏｍｐ）の中の残りのデジットのう５ち、最上
位から数えて、空いた位置の数に該当するデジットでも
って充填される。

Ｒ（ｃｏｍｐ）が空になるまでプロセスは繰り返され、
そして完結する。

Ｅ、効果 本発明の圧縮符号化方法及び復号方法は、効率及び時間
の両方の点で優れている。

【図面の簡単な説明】

第１図は、本発明による符号化法のフロー・チャートで
ある。 第２図は、第２図の方法が実行される際の、レジスタ間
でのデータの流れの説明図である。 第３図は、５つのシンボルについての確率及び累積確率
の例を示す説明図である。 出願人　　インターナシヨナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　頓　　宮　　孝　　−（外１名） 第６図

Claims (2)

【特許請求の範囲】
1. （１）（ｍ＋１）個のシンボル（ｍは自然数）があり、
   各シンボルａ＿ｉ（ｉ＝０、・・・、ｍ）について、そ
   の発生確率ｐ（ｉ）が与えられるとともに、Ｓ（ｉ）＝
   ｐ（０）＋ｐ（１）＋・・・ ・・・＋ｐ（ｉ−１）（ｉ＝１、・・・、ｍ）Ｓ（０）
   ＝０ なる式によつて累積確率Ｓ（ｉ）が与えられているとき
   に、一対の夫々Ｗビット分の位置を有するＡレジスタ及
   びＣレジスタを用いて、含まれる各シンボルが上記（ｍ
   ＋１）個のシンボルの何れかであるソース・データ・ス
   トリングを圧縮し、その際、圧縮表現は所定の範囲の数
   値として生成され、かつ圧縮表現の生成は該ソース・デ
   ータ・ストリングの相次ぐシンボルに対応する相次ぐサ
   イクルの中で帰納的に行われる圧縮符号化方法において
   、 （ａ）Ａレジスタ及びＣレジスタ中に夫々の初期内容を
   与え、 ソース・データ・ストリング中のシンボルａ＿ｉについ
   て （ｂ）Ａレジスタの内容を取り出し、所定の基準に照ら
   して、Ａレジスタに含まれる１のビットのうち該基準を
   下回る下位のものを切り捨てることによつて、スケーリ
   ング・ファクタＫを決定し、 （ｃ）ＫとＳ（ｉ）の積を求めてこれをＣレジスタの内
   容に加算し、 （ｄ）（ｄ１）シンボルａ＿ｉがシンボルａ＿ｍでない
   ならば、Ｋとｐ（ｉ）の積を求めてこれをＡレジスタの
   新たな内容とし、または、 （ｄ２）シンボルａ＿ｉがシンボルａ＿ｍであるならば
   、ＫとＳ（ｉ）の積を求めてこれをＡレジスタの内容か
   ら引き算することによつて、 Ａレジスタの内容を決定し、 （ｅ）Ａレジスタの内容が所定の範囲内に収まるまで、
   ＡレジスタとＣレジスタを両方とも所定の向きにシフト
   し、空いた位置にはゼロを充填し、 （ｆ）シンボルａ＿ｉがソース・データ・ストリングの
   最終シンボルでなければ、上記ステップ（ｂ）ないし（
   ｅ）を繰り返し、シンボルａ＿ｉがソース・データ・ス
   トリングの最終シンボルならば、Ｃレジスタの内容を上
   記所定の向きにＷ位置だけシフトする ステップを有する圧縮符号化方法。
2. （２）上記特許請求の範囲第１項の方法におけるものと
   同様に定義されたシンボルａ（ｉ）、確率ｐ（ｉ）、累
   積確率Ｓ（ｉ）（何れもｉ＝０、・・・、ｍ）並びにＡ
   レジスタ及びＣレジスタがあるときに、上記特許請求の
   範囲第１項記載の方法により生成されたソース・データ
   ・ストリングの圧縮表現を複号する方法であつて、 （ａ）Ｃレジスタの内容を上記圧縮表現の最上位から数
   えてＷ桁までの内容に初期設定するとともに、Ａレジス
   タに所定の初期内容を与え、 ソース・データ・ストリング中のシンボルａ＿ｉを順次
   複号すべく、 （ｂ）Ａレジスタの内容を取り出し、所定の基準に照ら
   して、Ａレジスタに含まれる１のビットのうち該基準を
   下回る下位のものを切り捨てることによつて、スケーリ
   ング・ファクタにを決定し、 （ｃ）Ｃ≧Ｋ＊Ｓ（ｊ）となるようなｊのうちの最大の
   ものを求め、ａ＿ｊをもつて現段階で出力されるシンボ
   ルとなし、 （ｄ）（ｄ１）シンボルａ＿ｊがシンボルａ＿ｍでない
   ならば、Ｋとｐ（ｊ）の積を求めてこれをＡレジスタの
   新たな内容とし、または、 （ｄ２）シンボルａ＿ｊがシンボルａ＿ｍであるならば
   、ＫとＳ（ｊ）の積を求めてこれをＡレジスタの内容か
   ら引き算することによつて、 Ａレジスタの内容を決定し、 （ｅ）ＫとＳ（ｊ）の積を求めてこれをＣレジスタの内
   容から引き算し、 （ｆ）Ａレジスタの内容が所定の範囲に収まるまで、Ａ
   レジスタとＣレジスタを両方とも所定の向きにシフトし
   、Ａレジスタの空いた位置にはゼロを充填するとともに
   、Ｃレジスタの空いた位置には、上記圧縮表現の未処理
   部分の内容を、その最上位の桁から空いた位置の数と同
   じ桁数だけ取り出して充填し、上記圧縮表現の未処理部
   分がなくなるまで、上記ステップ（ｂ）ないし（ｆ）を
   繰り返す ステップを有する、復号方法。