JPH0366227A - 圧縮符号化方法及びシステム並びに復号方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、算術符号化の改善方法及びその方法の実行シ
ステムに関する。

Ｂ、従来技術 算術符号化器（エン”コーグ）は、Ｒ１５ｓａｎｅｎに
よって開発され、１９７６年５月に刊行された“Ｇｅｎ
ｅｒａｌｉｚｅｄ　Ｋｒａｆｔ　Ｉｎｅｑｕａｌｉｔｙ
　Ａｒｊ、ｔｈｍｅｔｉｃＣｏｄｉｎｇ”、ＩＢＭ　Ｊ
ｏｕｒｎａｌ　ｏｆ　Ｒｅ６ｅａｒｃｈ　ａｎｄＤｅｖ
ｅｌｏｐｍｅｎｔ、　Ｖｏｌｕｍｅ２０．　Ｎｏ、　３
においてはしめて発表された。この算術符号化によれば
、マルチ・アルファベット・データの圧縮が可能になる
。マルチ・アルファベラ１〜・データとは、そのシンボ
ルの各々がマルチ・シンボル・アルファベラ１〜の１つ
であるようなデータを言う。ソース・データ・ストリン
グの圧縮とは、その情報内容を減じることなしに、ソー
ス・データ・ストリングに関連するデータの量を減らす
ことを言う。したがって、ソース・データ・ストリング
を圧縮すると、出力データはオリジナル・ソース・デー
タよりも少ない７− データ量で構成されるけれども、ソース・データ全体を
再構成することは依然として可能である。

算術符号化プロシージャでは、通常、出力データ・スト
リングは単位区間（０，１）内の２進少数として表わさ
れる。工９８４年３月に刊行されたＬａｎｇｄｏｒ　Ｊ
ｒ、著の“Ａｎ　Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔ。

Ａｒｉｔｈｍｅｔｉｃ　Ｃｏｄｉｎｇ”　、　ＩＢＭ　
Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈａｎｄ　Ｄｅ
ｖｅｌｏｋｍｅｎｔ、　Ｖｏｌｕｍｅ２８．　Ｎａ　２
で説明されているように、算術符号化は単位区間（ｕｎ
ｉｔｉｎｔｅｒｖａｌ）を細分化するプロセスに関連す
る。この細分化は、単位区間に沿ってソース・アルファ
ベット中のシンボルごとにコード・ポイントＣｎを決め
ていくことによって遠戚される。ここで、各コード・ポ
イントは、先行するシンボルの発生確率の総和に等しい
。各コード・ポイントの右側の部分区間（ｓｕｂ−ｉｎ
ｔｅｒｖａｌ）の幅あるいはサイズと言うべきＡｎは、
対応するシンボルまでのソース・データ・ストリングの
発生確率を表わす。

例えば、アルファベットがシンボルａ。−ａｍから構成
され、その発生確率がそれぞれｐ　（０）８− 〜ｐ　（ｍ）であるとしよう。ソース・データ・ス１−
リングがａ。第５ａ３・・・・・であるならば、最初の
シンボルａ。は、部分区間〔○、　ｐ　（０）　）の中
で符号化される。これは、元の単位区間内にあって、そ
の幅Ａ１がｐ　（０）に等しくてシンボルａ。

の発生確率に単純に対応する第１の部分区間を表わす。

ソース・データ・ストリングの第２のシンボル第５を符
号化するためには、シンボルａ。の発生確率を条件とす
る第５の発生確率を決定しなければならない。さらに、
第２シンボルａ５に関連する累積確率も計算しなければ
ならない。その結果、第２シンボルａ５に対応する部分
区間は、ａｌｌに対応する第１部分区間内の第２の部分
区間になる。数学的には、第２部分区間の＠Ａ２はｐ　
（０）・ｐ　（５）　、すなわちシンボルａ。、第５の
各発生確率の積に等しい。単位区間内で第２部分区間の
開始点は、第１部分区間の＠Ａ□と第２シンボルａ５に
関連する累積確率５（５）とに依存する。

すなわち、それらの積Ａ１・５（５）に等しい。

このようにしてソース・データ・ストリングの各シンボ
ルが単位区間内で相次いで符号化されていくと、それぞ
れを特定のコード・ポイントと幅でもって特定すること
が可能である部分区間が相次いで生成される。現在の部
分区間についてのコード・ポイントは、先行する区間又
は部分区間の中での現在部分区間の始まりに対応する。

上述のように、これは現在シンボルに関連する累積確率
に等しい。したがって、第ｎ部分区間に関連するコード
・ポイントは、第（ｎ−１）部分区間に関連するコード
・ポイントに第（ｎ−１）部分区間の幅と現在シンボル
の累積確率の積を足したものに等しい。すなわち、Ｃｎ
　”　Ｃ＋　Ａ　ｎ　Ｓ−１ （ｉ）となる。新しい小区間の幅は、（現在シンボルを
含めて）それまで符号化されたすべてのシンボルの確率
の積に等しい。すなわち、上述のソース・データ・スト
リングについてならｐ　（ｏ）Ｐ（５）・Ｐ（３）・・
・・・・ということになる。このようにして、幅Ａｎと
第ｎ小区間のコード・ポイントＣｎに対応するデータに
よって、ソース・データ・ストリング中の先頭の（ｎ＋
１）個のシンボルが符号化される。したがって、算術コ
ーグには、これらのデータを記憶するために、通常Ａレ
ジスタ、Ｃレジスタと呼ばれる２つのメモリ・レジスタ
が必要となる。

データ・ストリングを構成するシンボルの正確な発生確
率に依拠するとき、算術コーグは、ソース・データ・ス
トリングのエントロピーに対応する最適の圧縮を行う。

しかしながら、実際には、従来の算術符号化プロシージ
ャーのインプリメンテーションは、正確な確率を決定す
ることの困難さゆえに、近似を導入する傾向があった。

そのような近似によれば、算術符号化オペレーションの
効率が低下し、出力データ・ストリングが理論的最小値
、つまりエントロピーよりも多くのシンボルをもって生
成されることになる。さらに、一連の小区間の各々の幅
を決定するのに必要とされている乗算をなくすために、
−層の近似が導入されている。

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

米国特許第４６５２８５６号明細書では、乗算なしのマ
ルチ・アルファベット算術符号が開示されている。そこ
では、部分区間の各々が上述のような浮動少数魚形式で
ストアされる６そして、Ａレジスタに収められる仮数は
、０．１より大きな２進小数とされる。該明細書で提唱
される近似方法によれば、可変の基準を採用して、部分
区画の仮数を（２進の）０．１に正確に切り捨てるか、
もしくは１に切り上げる（ｒｏｕｎｄ　ｕｐ）かのどち
らかを行わせる。このような近似を使ってもなお所２− 望の圧縮を達成できるけれども、効率の点ではロスがあ
る。換言すると、圧縮データ・ストリングを表現するた
めに、最低限のビット数より多くのビット数が必要とさ
れる。このような非能率は、圧縮対象のソース・データ
の性質に依存する６特開平２−５３３２９号公報には、
各シンボルが（ｍ＋１）個のシンボルａ。、・・・、ａ
　からなる有限のセットから取り出されるソース・デー
タ・ストリングの圧縮表現を生成する改善された方法が
開示される。この方法は算術符号化プロシージャに依拠
しており、ソース・データ・ストリングが所定区間内の
相次ぐ部分区間として帰納的に生成される。各部分区間
の幅は、理論的には先行部分区間の幅に現在シンボルの
確率を掛けた積に等しい。改良点は、適当なシフト・レ
ジスタを用いる１回のシフト・アンド・アト・オペレー
ションによって近似を達成できるように、先行部分区間
の幅を近似することから得られる。

この公報では、発明の詳細な実行例として、５シンボル
・アルファベットから取り出された７個のシンボルから
なるソース・データ・ストリングの符号化法が説明され
ている。そして、説明の便宜のために、各シンボルの発
生確率は既知であり不変であると仮定されていた。実際
には、この方法１よ、同一のシンボルであってもソース
・データストリング中での発生のし方によって発生確率
が変わるような、より一般的な状況にも、よく適してい
る。それにもかかわらず、上記公報は、改良算術コーグ
の特定のインプリメンテーションにのみ関与しており、
確率のデリベーション（ｄｅｒｉｖａｔｉｏｎ）には関
与していない。

実際、ソース・データ・ストリング中のシンボルの確率
が当該シンボルの現れる文脈（ｃｏｎｔｅｘｔ）に依存
することはよく知られている。「文脈」とは、注目して
いるシンボルの直近のシンボル・パターンを意味する。

したがって、１次元ストリング中のある特定シンボルの
文脈には、当該シンボルの一方又は両方の側の工以上の
シンボルが含まれることになる、したがって、例えば、
ソース・データ・ストリングが、色が黒か白に応じて各
画素がＯか１になり得るような、イメージ処理システム
における画素情報を現わす場合、イメージの暗い部分で
はすべての画素はＯであり、イメージの明るい部分では
すべての画素は１である。その結果、明るい部分の中の
ある特定の画素は、その四方を値１の画素でもって囲ま
れることになるであろう。ある特定画素の確率を決定す
るに際し、先行する２画素からなる文脈を考えるなら、
イメージの明るい部分の中央にある画素の文脈は、１Ｌ
Ｘ（Ｘは当該特定画素）に等しいことになるのは明らか
である。

上述の事項を言い換えると、ある特定のシンボルの確率
は、その文脈に依存する。したがって、上記の例におい
て、あるシンボルの文脈が１１Ｘであることがわかって
いるなら１問題のシンボルが王である蓋然性は、文脈が
Ｏ○である場合よりもずっと高い。さらに、シンボルの
文脈の中のシンボル数が２個に限らずそれより多い数で
あるならば、ある特定のシンボルの確率をその文脈の関
数としてさらに一層正確に決定することが可能に５− なる。したがって、文脈が１０個のシンボルを含み、か
つそのすべてが工である場合において、問題のシンボル
がＯに等しい確率は、文脈を構成するシンボルの数が２
個で、かつ両方がともに１である場合よりも、はるかに
小さい。

シンボルの確率をその文脈の関数として決定することは
周知であり、上述の特許明細書の何れにおいても使用す
ることが可能である。あるシンボルの情報量（ｉｎｆｏ
ｒｍａｔｉｏｎ　ｃｏｎｔｅｎｔ）が式（１）によって
与えられることも知られている。

ｉ＝−１ｏｇ２ｐ　（１） ここでｐは、当該シンボルの発生確率に等しい。

したがって、各シンボルがＯか１であるような２進デー
タを送信する場合、ソース・データ・ストリングに登場
するシンボルの各々につき、圧縮（された）データ・ス
トリング中に登場する平均ビット数は、ｉの期待値に等
しいことが示され得る。すなわち、下記式（２）のよう
になる。

平均ビット数＝−（ｐ１ｏｇ２ｐ（１−ｐ）ｌｏｇ２（
１−ｐ））　（２）上記式から容易にわかることだが、
２進アルフ１６− アベツトの場合において、あるシンボルの発生確率が０
．５であるならば、当該シンボルを圧縮するのに要する
平均ピッ１〜数は１に等しい。すなわち、圧縮は不可能
である。ｎ個のシンボルを有するアルファベラ１への場
合、シンボルの確率が１／ｎに等しいならば、圧縮は不
可能である。

イメージ・データの圧縮に関して上述の例を再び考えて
みる。イメージの暗と明の領域に対応する単純な２値の
ケースにおいて、文脈が・・ＯＯＯ・・・または・・・
１１１　・であるような画素を圧縮するのに要する平均
ビット数は、１よりもかなり少ない。したがって、ソー
ス・データを効率よく圧縮することができる。しかしな
がら、イメージの暗と明の領域の境にある画素の確率は
０．５に等しい。なぜなら、現在シンボルと暗領域の所
定数の画素を含む文脈に基づくなら、現在画素は○であ
ると推測されるだろうけれども、現在シンボルと明領域
の同数の画素を含む文脈に基づくなら、現在シンボルは
ｌであると同程度に期待されるであろうだからである。

その結果、イメージ・データを送信するに際し、イメー
ジの実質的に暗の領域と実質的に明の領域の境に位置す
る画素に対応するデータを明瞭に送信するためには、情
報当りの支出が高価なものでならざるを得ない。

Ｃ０発明が解決しようとする課題 本発明の目的は、シンボルの確率が該シンボルの文脈に
応じて決定され、かつ従来の算術符号器に付随した欠点
が実質的に減少しあるいは除かれた算術符号器を提供す
ることにある。

００課題を解決するための手段 本発明の広い局面によれば、シンボルのパターンに算術
符号化を施して、圧縮された出力コード・ストリングを
生成する方法であって、上記シンボルは有限のシンボル
のセットから取られ、各シンボルは上記パターン中のあ
る位置に出現し、上記コード・ストリングは上記シンボ
ルの上記位置に出現する確率に依拠するある数であるよ
うな圧縮符号化方法において、以下のステップを含むこ
とを特徴とする方法が提供される。

（ａ）各位置の近傍の位置の所与の第１のサブ・パター
ンを評価することによって、該パターン中の予測可能位
置ＰＰと予測不能位置ＵＰを決定する。

ここで、該位置サブパターンが所与のシンボル・サブパ
ターン・セットのうちの何れか１つを含むときにＵＰは
定義され、その他のすべての場合にＰＰが定義される。

（ｂ）ＰＰ中の各シンボルについて、各自の位置におけ
る各自のシンボルの確率を用いて、通常の算術符号化を
適用する。

（ｃ）ＵＰ中の各シンボルについて、各自の位置に出現
し得るシンボルの所与のセットの組合せ確率を用いて、
通常の算術符号化を適用する。

本発明の第２の局面によれば、シンボルのパターンに無
損失算術符号化を施して、圧縮された出力コード・スト
リングを生成する方法であって、上記シンボルは有限の
シンボルのセットから取られ、各シンボルは上記パター
ン中のある位置に出現し、上記コード・ストリングは上
記シンボルの上記位置に出現する確率に依拠するある数
であるような圧縮符号化方法において、以下のステップ
９− を含むことを特徴とする方法が提供される。

（ａ）各位置の近傍の、文脈を表わす位置の所与の第１
のサブ・パターンを評価することによって、該パターン
中の予測可能位置ＰＰと予測不能位置ＵＰを決定する。

ここで、該位置サブパターンが選択されたシンボル・サ
ブパターン・セットのうちの何れか１つを含むときにＵ
Ｐは定義され、その他のすべての場合にＰＰが定義され
る。

（ｂ）ＰＰ中の各シンボルについて、各自の文脈におけ
る各自のシンボルの確率を用いて、通常の算術符号化を
適用する。

（ｃ）ＵＰ中の各シンボルについて、上記ＵＰが予測可
能となるように、上記所与の第１のサブパターンよりも
大きな第２の位置のサブパターンを評価する。

（ｄ）上記第２のサブパターンから導かれた各シンボル
の更新された確率によって、算術符号化を実行する。

本発明の第３の局面によれば、上述の方法を実行するた
めのシステムであって、 ２０ 各シンボルについて、上記第１のサブパターンを記憶す
るための第１のメモリと、 可能性のあるサブパターンの所定のセットを記憶するた
めの第２のメモリと、 各シンボルについて、第１メモリ中の第１のサブパター
ンを第２メモリ中のサブパターン・セットのサブパター
ンと比較し、上記第１のサブパターンと第■の信号を生
成し、そうでない場合には第２の信号を生成する比較手
段と、 可能性のあるサブパターンの完全セットの各々に応じた
シンボル・セラ１へ中の各シンボルの確率を保持する第
１のルックアップ・テーブルを記憶するための第３のメ
モリと、 上記所定のサブパターン・セットに応じた可能性のある
シンボルの所定のセットの組合せ確率を保持する第２の
ルックアップ・テーブルを記憶するための第４のメモリ
と、 比較手段と結合され、上記第１の信号に応答して、上記
第３メモリを読み取る一方、上記第２の信号に応答して
上記第４メモリを読み取り、上記第１のサブパターンに
対応する記憶されている確率を決定する読取手段と、 読取手段と結合され、決定された確率に応答して各シン
ボルを符号化する算術符号手段を具備する°、圧縮符号
化システムが提供される。

このように、本発明によれば、データは予測可能ポイン
トと予測不能ポイントに対応するクラスに分けられ、別
々に取り扱われる。予測可能ポイントは算術符号器を使
って通常のやり方で符号化される。予測不能ポイントの
符号化を望むときは、有損失（ｌｏｓｓｙ）又は無損失
（ｌｏｓｓｌｅｓｓ）符号器のどちらがインプリメント
されているかによって、数通りのオプションが存在する
。どちらの場合も、通常の算術符号器をインプリメント
することによって、予測不能シンボルを含むシンボルの
完全クラスが送信される。しかし、現在シンボルの確率
を利用するのではなくて、予測不能ポイントを含むシン
ボルの完全クラスの組合せ確率が利用される。

有損失符号化については、これで十分であり、適当なデ
コーダが、どのシンボルクラスが予測不能ポイントによ
って表わされているかを決定することが可能である。予
測不能ポイント自身は、符号化されることなしに、それ
が属する一般クラスを表示する。このようにして、情報
量当りの支出は、シンボル自身が符号化される場合より
も低価になる。

無損失符号化については、予測不能ポイントの文脈が、
当該ポイントにおけるシンボルの確率がｎシンボル・ア
ルファベットの場合に１　／　ｎとは異なる値になるよ
うに、増大されてよい。

復号時には、相次いでシンボルが復合される際の、各シ
ンボルの各自の文脈が、符号器のものと全く同一のルー
ルに従って、該シンボルが予測可能又は予測不能ポイン
トのどちらを表わしているかを決定するのに使われる。

予測可能ポイントの場合、シンボルは算術符号化の通常
のルールを使って復合される。一方、予測不能ポイント
の場合には、有損失又は無損失複合のどちらかが要求さ
れているかに応じて、数通りのオプションが存在３− する。

有損失復号の場合、予測不能ポイントは、予測不能ポイ
ントがそのメンバーである完全クラスを示す補助シンボ
ルによって単に置換されるだけである。この場合、生成
される復号出力ストリングは、ユニークなストリングで
はなく、可能性のあるストリングのセットである。

無損失復号の場合、予測不能ポイントに関しｌ／ｎとは
異なる確率を獲得し、それによって予測を可能にするた
めに、符号化についてなされたとの全く同様にして、予
測不能ポイントの文脈が増大されてよい。本発明による
エパス・デコーダでは、予測不能ポイントの近傍におい
て、該ポイントの前に出現するシンボルの数を増やすこ
とによって、文脈が増大される。本発明による２パス・
デコーダでは、予測不能ポイントの後に出現するポイン
トも考慮することによって、文脈が増大される。

有損失デコーダでは、ストリング・セットを表わす補助
シンボルでもって予測不能ポイントを置−２４＝ 換するかわりに、予測不能ポイントの近傍において復号
されたストリングを内挿又は外挿することによって予測
不能ポイントを推測することも可能である。

Ｅ、実施例 第１図は、本発明による、一般化された符号化プロシー
ジャの流れ図である。このプロシージャの主要ステップ
には、１．３．４、及び５の番号が付されているけれど
も、その理由は後で第７図を参照するとこで明らかにな
るであろう。

ソース・データ・ストリング中の各シンボルについて、
文脈は、当該シンボルの近傍の、所与のサブ・パターン
の位置を評価することによって決定される。ソース・デ
ータ・ストリングが１次であるなら、文脈は、現在シン
ボルの一方の側のシンボルだけあるいは両方の側のシン
ボルを名慮することによって、評価され得る。例えばイ
メージ処理で発生するような２次元データの場合には、
現在シンボルの四方のシンボルの何れかあるいはすべて
を考慮することになる。明らかに、リアル・タイムでの
文脈の評価において、現在シンボルの後に発生するシン
ボルを考慮することが必要とされる場合には、ソース・
データ・ストリングを一旦記憶して後処理をすることが
必要になるので、データ捕捉とデータ圧縮の間に短い遅
延が存在することになる。現実には、遅延は極めて短い
ので、無視することができる。

現在のシンボルの文脈が評価されたなら、該現在文脈に
依拠する条件付き確率が決定される。これによって、現
在シンボルを、（ｎシンボル・アルファベットの場合に
は）確率が１　／　ｎに等しい予測不能ポイント（ｕｎ
ｐｒｅｄｉｃｔａｂｌｅ　ｐｏｉｎｔ、以下ＵＰと略す
ることもある）又は他のすべての確率に対応する予測可
能ポイント（ｐｒｅｄｉｃｔａｂｌｅｐｏｉｎｔ、以上
ＰＰと略することもある）に分類することが可能になる
。予測可能ポイントＰＰの符号化は、現在シンボルの確
率に依拠する標準算術符号化法によって行われる。

第１図に示されるように、予測不能ポイントＵＰを処理
するためには、有損失（ファジィ）符号化又は無損失符
号化のどちらが要求されるかに応じて、２つの方法のう
ちの工つをとることができる。有損失（１ｏｓｓｙ）符
号化の場合には、現在シンボルに対応するファジー・セ
ット（現在シンボルを含む異なるシンボルのセット）の
確率が決定され、その後、この組合せ（ｃｏｍｂｉｎｅ
ｄ）確率を使って算術符号化が実行されるので、現在シ
ンボルの属す、るクラス全部のポイントが効率よく送信
される。無損失（１ｏｓｓｌｅｓｓ）符号化を行うため
には、確率が１　／　ｎとは異なるものになるように、
したがって、ポイントが予測可能になるように、現在シ
ンボルの文脈が増大する。算術符号化は、この大きくな
った文脈に依拠して、新たに決定された確率を使って実
行されるので、現在シンボルを損失なしに符号化するこ
とができる。

第２図には、無損失符号化を行う他の方法が示される。

予測可能ポイントは第１図に関して述べたのと全く同様
にして処理される。予測不能ポイントＵＰに遭遇すると
、まず現在シンボルの属するファジー・セットの確率が
決定され、次いでこ２７− の組合せ確率を使って算術符号化が実行されて、現在シ
ンボルの属するクラス全部のポイントが効率よく送信さ
れる。これは第１図に示されたプロシージャと同一であ
る。しかしながら、ここで、現在シンボルが予測可能と
なるようにその文脈が増大され、次いでこの拡大された
新しい文脈を使って現在シンボルの確率が決定される。

新しい確率は（ｎシンボル・アルファベットの場合）も
はや１　／　ｎではなく、したがって現在シンボルは拡
大された文脈を使って予測可能であり、算術符号化を普
通のやり方で適用することができる。

上記説明より、２つの重要な点が浮かび上がる。

まず、すべてのケースにおいて、予測可能ポイントは、
標準的な算術符号化技法を用いて従来通りに処理される
。しかしながら、予測不能ポイントは、同様に処理する
とデータ圧縮効率を低下させるので、２段階又は３段階
で処理されることになるが、その理由は後で明らかにす
る。第１段階では、当該予測不能ポイントの属するシン
ボルの完全クラスに関する情報が獲得される。オプショ
ン２８ として、現在シンボルの属するファジー・セットを転送
するために算術符号化をここで実行しても差し支えない
（第２図）。最終段階では、予測不能ポイントを予測可
能にするために、拡大された文脈が評価され、算術符号
化が再度実行される。

したがって、第１図を参照して述べた２段階方法では、
各予測不能ポイントＵＰについて、算術符号化のステッ
プは、拡大された文脈を使って、１度だけ実行される。

第２図を参照して述べた３段階法では、算術符号化のス
テップは、２度、つまり完全ファジー・セットの符号化
について１度と現在シンボルの符号化について１度実行
される。

しかしながら、このケースでは、追加的な算術符号化ス
テップが必要であるけれども、現在シンボルが属するフ
ァジー・セットの知識は決定されており、したがって、
デゴーダには知られていることを理解しなければならな
い。その結果、新しい拡大された文脈の中で、現在シン
ボルの確率は、２段階方法のそれとは同じにならず、し
たがってソース・データ・ストリングをより効率的に圧
縮することができる。さらに、文脈の拡大量をファジー
・セットに応じて換えることもできる。これに対し、フ
ァジー・セットの知識をまず符号化することを行わない
ならば、文脈の拡大量は常に同じでなければならない。

第３図には、有損失（ファジー）符号化を行う他の方法
が示される。その主要なステップには１０から１５まで
の番号が付されているけれども、その理由は後で第８図
を参照することで明らかになるであろう。第３図に示さ
れるファジー符号化法において、予測可能ポイントＰＰ
は、第１図に関して述べたのと全く同様に、通常の算術
符号化法にしたがって処理される。しかしながら、この
ケースでは、予測不能ポイントＵＰは違って処理される
。ｔＪＰｋこ対応する現在ポイントは補助（ａｕｘｉｌ
ｉａｒｙ）シンボルにセットされ、現在シンボルの属す
るファジー・セットの確率が決定される。この１１組合
せ（ｃｏｍｂｉｎｅｄ　）”確率の知識に基づいて算術
符号化が適用され、ＵＰの属するシンボルの完全クラス
に対応する情報が効率よく送信される。

上記ファジー符号化の説明の中で、２点に注意しなけれ
ばならない。第１に補助シンボルはデコーダに送信され
ない、補助シンボルは、後続の文脈を正確に評価できる
ように、エンコーダの中の一時バッファにストアされる
。上述のことかられかるように、文脈はソース・データ
・ストリング中のシンボルの条件付きに確率を決定する
。したがって、ある特定シンボルの文脈がＵＰを含んで
いる場合、現在シンボルの確率を正確に決定するために
は、現在文脈の中でのＵＰの存在及び位置を知る必要が
る。実際、補助シンボルは、個々の位置の元の（初期の
）シンボルがＵＰであったことを示すフラグにすぎない
。

第２に、第３図を参照して説明した算術符号化法では、
レシーバ側でユニークなストリング中デコードすること
ができない。その代り、予測不能ポイントＵＰがその属
する完全クラスの形で明記されたストリング・セラ１〜
が送信される。その結果、デコードされたストリングの
情報量はオリジ−３１− ナル・ソース・ストリングよりもいくらか少ない。

それゆえ、かかるエンコーダは“ファジー”エンコーダ
と呼ばれる。ファジー算術符号器をイメージ処理で用い
ると、圧縮率は改善されるけれども、イメージの品質は
多少低下する。イメージの品質が低下する場合、本発明
によるファジー算術符号化は、そのようなエラーが目立
たないような領域に限定されなければならないことは明
らかであろう。

第１〜３図を参照して述べた本発明法及び従来の算術符
号器に比してのパフォーマンスの向上を明示するために
、詳細な具体例を以下に揚げる。

２進アルフアベツトから取られたシンボルを含む、次の
ようなソース・データ・ストリングについて考える。

Ｓ　ＲＴ　＝　１１１１０００００１１１１１００１０
０１０１００１１１１０００００００上述のように、算
術符号器は、Ａ、Ｃと称される２つのシフト・レジスタ
を用いる。Ａレジスタはコード区間の長さを表わす一方
、Ｃレジスタはコードの実際の値を持つ。Ａレジスタの
内容は、３２ それまでに符号化された全シンボルの確率の積に等しい
。即ち、以下の式によって与えられる。

Ａ＝　ｐ（ａｌ）ｐ（ａ２）ｐ（ａ３）・・・−ｐ（ａ
ｎ−ｔ）ｐ（ａｎ）したがって、 ｌｏｇ２Ａ　＝　ｌｏｇ、　ｐ　（ａｘ　）＋１ｏｇ２
ｐ　（ａ２）３１０ｇ２ｐ　（ａ３）＋−１ｏｇ２ｐ（
ａｎ−、）＋１ｏｇ２ｐ（ａｎ）となる。

１ｏｇ２Ａは、Ａレジスタを正規化するのに必要なシフ
ト数を表わし、さらにはＣレジスタから抽出されるコー
ドの長さを決定する。結果として、算術符号器から導入
されるコードの長さは、ソース・データ・ストリング中
の２を底とする符号化された各シンボルの確率の対数を
加算することによって計算することができる。

以下の実行例では、Ａ及びＣレジスタの具体的な数値は
考慮しない。なぜなら、２つの方法を比較する上で関心
をひくのは、圧縮済コード中のビット数だけであって、
コード自体の具体的な数値ではないからである。

例１：従来の算術符号器 ソース・ストリングＳＴＲ中でＯ又は１を発見する確率
が、以下のような文脈に依存すると仮定する。

文脈＝１１Ｘ　：　ｐ（１）＝０．７　　ｐ（０）＝０
．３１を符号化するのに要するビット数＝−１ｏｇ２０
．７＝０．５１０を符号化するのに要するビット数＝−
１ｏｇ２０．３＝１．７４文脈＝ＯＯＸ　：　ｐ（１）
＝０．３３　　ｐ（０）＝０．６７１を符号化するのに
要するビット数＝−１ｏｇ２０．３３＝１．６００を符
号化するのに要するビット数＝−１ｏｇ２０．６７＝０
．５８文脈＝０１Ｘ　：　ｐ（１）＝０．５　　ｐ（ｏ
）＝ｏ、ｓ１を符号化するのに要するビット数＝−１ｏ
ｇ２０．５＝１．０００を符号化するのに要するビット
数”−１ｏｇ２０．５”１．ＯＯ文脈、１０Ｘ　：　ｐ
（１）、０．１７　　ｐ（０）＝０．８３１を符号化す
るのに要するビット数ニーｌｏｇ２０．１７＝２．５６
０を符号化するのに要するビット数＝−１ｏｇ２０．８
３＝０．２７Ｓ　Ｔ　Ｒ＝　１１１１０００００１１１
１１００１００１０１００１１１１０００００００ステ
ツプＯ：初期設定： ｃ＝ｏ、ｂｂｂ ステップ１：文脈＝１１Ｘ　　５ＴＲ（１）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ Ｒｅｍ、＝０．５１ビツト ステップ２；文脈＝１１Ｘ　　５ＴＲ（２）＝１１を符
号化するのに要するビット数＝０．５］ｃ＝ｏ、ｂｂｂ
ｂ Ｒｅｍ、＝０．０２ビツト ステップ３：文脈＝１１Ｘ　　５ＴＲ（３）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ
ｂ Ｒｅｆｆ１．＝０．５３ビツト ステップ４：文脈＝１１Ｘ　　５ＴＲ（４）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ
ｂｂ Ｒｅｍ、＝０．０４ビツト ５ ステップ５：文脈＝ＩＩＸ　　５ＴＲ（５）＝００を符
号化するのに要するビット数＝１．７４ｃ＝ｏ、ｂｂｂ
ｂｂｂ Ｒｅｍ、＝０．７８ビツト ステップ６：文脈＝１０Ｘ　　５ＴＲ（６）＝００を符
号化するのに要するビット数＝０．２７ｃ　＝ｏ、ｂｂ
ｂｂｂｂｂ Ｒｅｍ、＝０．０５ビツト ステップ７：文脈＝００Ｘ　　５ＴＲ（７）＝００を符
号化するのに要するビット数＝０．５８ｃ：ｏ、ｂｂｂ
ｂｂｂｂ Ｒｅｍ、＝０．６３ビツト ステップ８：文脈＝＝ＯＯＸ　　５ＴＲ（８）＝００を
符号化するのに要するビット数＝０．５８ｃ＝ｏ、ｂｂ
ｂｂｂｂｂｂ Ｒｅｍ、＝０．２１ピツト スフ−７プ９：文脈＝ＯＯＸ　　５ＴＲ（９）＝００を
符号化するのに要するビット数：０．５８ｃ　＝ｏ、ｂ
ｂｂｂｂｂｂｂ Ｒｅｍ、＝０．７９ビツト ３６ ステツプ１０：文脈＝００Ｘ　　５ＴＲ（１０）＝１１
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．３９ビツト ステップ１１：文脈＝０１Ｘ　　５ＴＲ（１１）＝１１
を符号化するのに要するビット数＝１．０Ｏｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂ Ｒｅｉ、＝０．３９ビツト ステップ１２：文脈＝１１Ｘ　　５ＴＲ（１２）＝１１
を符号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．９０ビツト ステップ１３：文脈＝１１Ｘ　　５ＴＲ（１３）＝１１
を符号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．４１ビツト ステップ１４：文脈＝１１Ｘ　　５ＴＲ（１４）＝１王
を符号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．９２ビット ステップ１５：文脈＝１１Ｘ　　５ＴＲ（１５）＝００
を符号化するのに要するビット数＝１．７４ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．６６ビツト ステツプ１６：文脈＝１０Ｘ　　５ＴＲ（１６）＝００
を符号化するのに要するビット数＝０．２７ｃ＝ｏ、　
ｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．９３ビツト ステップ１７：文脈＝００Ｘ　　５ＴＲ（１７）＝１１
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．５３ビツ
ト ステップ１８：文脈＝ＯＩＸ　　５ＴＲ（１８）＝００
を符号化するのに要するビット数＝１．０Ｏｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．５３ビ
ツト ステップ１９：文脈＝１０Ｘ　　５ＴＲ（１９）＝００
を符号化するのに要するビット数＝０．２７ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．８０ビ
ツト ３９− ステップ２５：文脈＝ＯＯＸ　　５ＴＲ（２５）＝１１
を符号化するのに要するビット数＝１．６０ｃ　＝ｏ、
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ
、＝０．８３ビツト ステップ２６：文脈＝ＯＩＸ　　５ＴＲ（２６）＝１１
を符号化するのに要するビット数＝１．ＯＯｃ　＝ｏ、
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅ
ｍ、＝０．８３ビツト ステップ２７：文脈＝１１Ｘ　　５ＴＲ（２７）＝１１
を符号化するのに要するビット数＝０．５１０＝０゜ Ｒｅｍ、＝０．３４ビツト ステップ２８：文脈＝１１Ｘ　　５ＴＲ（２８）＝１１
を符号化するのに要するビット数＝０．５１０＝０゜ Ｒｅｍ、＝０．８５ビツト ステップ２９：文脈＝１１Ｘ　　５ＴＲ（２９）＝００
を符号化するのに要するビット数＝１．７４０＝０゜ Ｒｅｍ、＝０．５９ビツト ステップ２０：文脈＝００Ｘ　　ＳＴＲ，（２０）＝１
１を符号化するのに要するビット数＝１．６０Ｃ＝Ｏ，
ｂｂｂｂｂｂｂｂｂｂｂｂｔ＋ｂｂｂｂｂＲｅｍ、＝０
．４０ビツト ステップ２１：文脈＝ＯＩＸ　　５ＴＲ（２１）＝００
を符号化するのに要するビット数＝ｉ、、ｏ。

ｃ＝ｏ、ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅ
ｍ、＝０．４０ビツト ステップ２２：文脈＝１０Ｘ　　５ＴＲ（２２）＝１１
を符号化するのに要するビット数＝２．５６ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０
．９６ビツト ステツプ２３：文脈＝０１Ｘ　　５ＴＲ（２３）＝００
を符号化するのに要するピッｌ−数＝ｉ、ｏ。

ｃ＝ｏ、ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲ
ｅｍ、＝０．９６ビツト ステツプ２４：文脈＝１０Ｘ　　５ＴＲ（２４）＝００
を符号化するのに要するビット数＝０．２７Ｃ＝０．ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝
０．２３ビツト ４０− ステップ３０：文脈＝１０Ｘ　　５ＴＲ（３０）＝００
を符号化するのに要するビット数＝０．２７Ｃ＝０゜ Ｒｅｍ、＝０．８６ビツト ステツプ３１：文脈＝００Ｘ　　５ＴＲ（３１）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ Ｒｅｍ、＝０．４４ビツト ステップ３２：文脈＝ＯＯＸ　　５ＴＲ（３２）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ Ｒｅｍ、＝０．０２ビツト ステップ３３：文脈＝ＯＯＸ　　５ＴＲ（３３）＝００
を符号化するのに要するビット数＝０．５８Ｃ：０゜ Ｒｅｍ、＝０．６０ビツト ステップ３４：文脈＝００Ｘ　　５ＴＲ（３４）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝Ｏ。

Ｒｅｍ、＝０．１８ピツ１、 ステップ３５：文脈＝ＯＯＸ　　５ＴＲ（３５）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ 上記のステップの内容のうち、ステップ２．３．４につ
いてだけ簡単に説明しておく。ステップ２では、文脈１
１Ｘの下で、１が符号化される。そのために要するビッ
ト数は０．５１である。よって、ステップ１と２を合わ
せて、０．５１＋０゜５１＝１．０２ビツトが符号化に
必要になる。よってＣがｌビット増化する。そして、１
．０２の少数部分０．０２ビツトが残る。このことをＲ
ｅｍ、＝０．０２ビツトと表わしている。

ステップ３では０．５１ビツトが符号化に必要とされる
。よって、Ｒｅｍ、＝０．０２＋０．５１＝０．５３ビ
ツトとなる。

ステップ４では０．５１ビツトが符号化に必要とされる
。よって、ステップ３のＲｅｍ、に０゜５１を足すと、
１．０４ビツトとなり、ｌを越えた。よって、Ｃが１ビ
ツト増加する。そして、１゜０４の小数部分０．０４ビ
ツトが残る。即ち、Ｒｅｍ、＝０．０４ビツトである。

このようにして、最終的には、圧縮コードの長さは３２
ビツトとなる。そのコード・ストリングをデコードすれ
ば、オリジナル・ソース・データ・ストリングＳＴＲが
複製される。

例２：ファジー論論理算術量器（ＦＬＡＣ）ソース・デ
ータ・ストリングＳＴＲ中でＯ又は１を発見する確率が
、以下のような文脈に依存すると仮定する。

文脈＝１１Ｘ　：　ｐ（１）＝０．７　　ｐ（０）＝０
．３１を符号化するのに要するビット数＝−１ｏｇ２０
．７−０．５１０を符号化するのに要するビット数＝−
１ｏｇ２０．３＝１．７４文脈＝ＯＯＸ　：　ｐ（１）
＝０．３３　　ｐ（０）＝０．６７１を符号化するのに
要するビット数＝−１ｏｇ２０，３３４．６００を符号
化するのに要するビット数＝−１ｏｇ２０．６７二〇、
５８文文脈上０Ｘ　：　ｐ（１）＝０．１７　　ｐ（０
）＝０．８３１を符号化するのに要するビット数＝−１
０ｇ２Ｑ、　１７＝２．５６０を符号化するのに要する
ビット数＝−１ｏｇ２０．８３−０．２７文脈＝０１Ｘ
　：“ＤＯＮ’Ｔ　ＣＡＲＥ””＝（１，０）を符号化
するのに要するビット数＝０４３− 文脈＝Ｉ　Ｘ　：　ｐ（１）＝０．７５　　ｐ（０）−
０，８３１を符号化するのに要するビット数＝−１ｏｇ
、０．７５＝０．４２０を符号化するのに要するビット
数ニー１０ｇ２０．２５＝２．００＊ 文脈＝　ＬＸ　：　ｐ（１）＝０．６７　　ｐ（０）＝
０．３３１を符号化するのに要するビット数＝−１ｏｇ
２０．６７”０．５８０を符号化するのに要するビット
数＝−１ｏｇ２０．３３＝１．６０ネ 文脈二〇ｘ：ｐ（１）＝０．８５ｐ（０）＝０．１５１
を符号化するのに要するビット数＝−１ｏｇ２０．８５
＝０．２３０を符号化するのに要するビット数ニーｌｏ
ｇ、０．１５＝２．７４Ｓ　Ｔ　Ｒ＝　１１１１０００
００１１１１１００１００１０１００１１１１００００
０００４４− ステップ○：初期設定： ｃ＝ｏ、ｂｂｂ ステップ１：文脈＝１１Ｘ　　５ＴＲ（１）＝１１を符
号化するのに要するビット数＝０．５］ｃ＝ｏ、ｂｂｂ Ｒｅｍ、＝０．５１ビツト ステップ２：文脈＝１１Ｘ　　５ＴＲ（２）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ
ｂ Ｒｅｍ、＝０．０２ビツト ステップ３：文脈＝１１Ｘ　　５ＴＲ（３）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ
ｂ ＲｅＩｌｌ、＝０．５３ピツ１、 ステップ４：文脈＝１１Ｘ　　５ＴＲ（４）＝１１を符
号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂｂｂ
ｂｂ Ｒｅ１１．＝０．０４ビット ステップ５：文脈＝１１Ｘ　　５ＴＲ（５）＝００を符
号化するのに要するビット数＝１．７４ｃ＝ｏ、ｂｂｂ
ｂｂｂ Ｒｅｍ、＝０．７８ビツト ステップ６：文脈＝１０Ｘ　　５ＴＲ（６）＝００を符
号化するのに要するビット数＝０．２７ｃ＝ｏ、ｂｂｂ
ｂｂｂｂ Ｒｅｍ、＝０．０５ビツト ステップ７：文脈＝００Ｘ　　５ＴＲ（７）＝００を符
号化するのに要するビット数＝０．５８ｃ＝ｏ、ｂｂｂ
ｂｂｂｂ Ｒｅｍ、＝０．６３ビット ステップ８：文脈＝ＯＯＸ　　５ＴＲ（８）＝００を符
号化するのに要するビット数＝０．５８ｃ、ｏ、ｂｂｂ
ｂｂｂｂｂ Ｒｅｌｕ、＝０．２１ビツト ステップ９：文脈＝ＯＯＸ　　５ＴＲ（９）＝００を符
号化するのに要するビット数＝０．５８ｃ＝ｏ、ｂｂｂ
ｂｂｂｂｂ Ｒｅｍ、＝０．７９ビツト ４７− ステップ１４：文脈＝１１Ｘ　　５ＴＲ（１４）＝１１
を符号化するのに要するビット数＝０．５１ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．ＯＯビット ステップ１５：文脈＝１１Ｘ　　５ＴＲ（１５）＝００
を符号化するのに要するビット数＝１．７４ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．７４ビツト ステップ１６：文脈＝１０Ｘ　　５ＴＲ（１６）＝００
を符号化するのに要するビット数＝０．２７ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｎ＋、＝０．０１ビツ
ト ステップ１７：文脈＝ＯＯＸ　　５ＴＲ（１７）＝１１
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．６１ビツ
ト ステップ１８：文脈＝０１Ｘ　　５ＴＲ（１８）＝”＊
を符号化するのに要するビット数：＝Ｏ，ＯＯｃ　＝ｏ
、ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．６１
ビツト ステップ１０：文脈＝ＯＯＸ　　５ＴＲ（１０）＝１１
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．３９ピツ１、 Ｘ−７−ツフｌｌ：文脈＝ＯＩＸ　　５ＴＲ（１１）＝
”＊を符号化するのに要するビット数＝０．００ｃ＝ｏ
、ｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．３９ビツト ステップ１２：文脈＝Ｉ　Ｘ　　５ＴＲ（１２）＝１１
を符号化するのに要する゛ビット数＝０．４２ｃ＝ｏ、
ｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．８１ビツト ステップ１３：文脈＝　ＬＸ　　５ＴＲ（１３）＝１王
を符号化するのに要するビット数＝０．５８ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂ Ｒｅｍ、＝０．４９ビツト ４８ ステップ１９：文脈＝Ｉ　Ｘ　　５ＴＲ（１９）＝００
を符号化するのに要するビット数＝２．０Ｏｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．６１
ビツト ステップ２０：文脈＝　ＯＸ　　５ＴＲ（２０）＝１１
を符号化するのに要するビット数＝０．２３ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ　、＝０．８
４ビツト ステップ２１：文脈＝ＯＩＸ　　５ＴＲ（２１）＝”＊
を符号化するのに要するビット数＝０．００ｃ　＝ｏ、
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．３
４ビツト ステップ２２：文脈＝ＩＸ　　５ＴＲ（２２）＝１１を
符号化するのに要するビット数＝０゜４２ｃ＝ｏ、ｂｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．２６
ビット ステップ２３：文脈＝　ＩＸ　　５ＴＲ（２３）＝００
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０．
８６ビツト ステツプ２４：文脈＝１０Ｘ　　５ＴＲ（２４）＝００
を符号化するのに要するビット数＝０．２７ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝０
．１３ビツト ステップ２５：文脈＝ＯＯＸ　　５ＴＲ（２５）＝１１
を符号化するのに要するビット数＝１．６０ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝
０．７３ビツト ステラフ２６：文脈＝ＯＩＸ　　５ＴＲ（２６）＝’＊
を符号化するのに要するビット数＝０．００ｃ＝ｏ、ｂ
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ、＝
０．７３ビツト ステップ２７：文脈＝Ｉ　Ｘ　　５ＴＲ（２７）＝１１
を符号化するのに要するビット数＝０．４２ｃ　＝ｏ、
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ
、＝０．１５ビツト ステップ２８二文脈＝　ＬＸ　　５ＴＲ（２８）＝１１
を符号化するのに要するビット数＝０．５８ｃ　＝ｏ、
ｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂｂＲｅｍ
、＝０．７３ビツト ステップ２９：文脈＝１１Ｘ　　５ＴＲ（２９）＝００
を符号化するのに要するビット数＝１．７４Ｃ＝Ｏ。

Ｒｅｍ、＝０．４７ビツト ステツプ３０：文脈＝１０Ｘ　　５ＴＲ（３０）＝００
を符号化するのに要するピッ１〜数＝０．２７０＝０゜ Ｒｅｍ、＝０．７４ビツト ５１− ステップ３１：文脈＝ＯＯＸ　　５ＴＲ（３１）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ Ｒｅｍ、＝０．３２ビツト ステップ３２：文脈＝ＯＯＸ　　５ＴＲ（３２）＝００
を符号化するのに要するビット数＝０．５８０二〇。

Ｒｅ１１．＝０．９０ビツト ステップ３３：文脈＝ＯＯＸ　　５ＴＲ（３３）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ Ｒｅｍ、＝０．４８ビツト ステップ３４：文脈＝００Ｘ　　５ＴＲ（３４）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ Ｒｅｍ、＝０．０６ビツト ステツプ３５：文脈＝００Ｘ　　５ＴＲ（３５）＝００
を符号化するのに要するビット数＝０．５８Ｃ＝０゜ このようにして得られた圧縮コードの長さは２５２− ９ビツトにすぎない。このコードのデコードは従来の算
術復号器と同様のやり方で行われ、次のようなストリン
グ・セットが得られる Ｓ　Ｓ　＝１１１１０００００１１１１００１０１１０
０１１１０００００００最後に、ＦＬＡＣデコーダが、
ストリングＳＳ水 中の　に対応する予測不能ポイントＵＰを、次のような
補間によって評価するようにプログラムされていると仮
定する。即ち、　の右のシンボルが１であるならば、　
は１に置き換えられる。そうでないならば、０に置き換
えられる。これによって、ソース・ストリングＳＴＲに
ついての、次のような最終評価ＳＴＲ’　が得られる。

Ｓ　Ｔ　Ｒ’　＝１１１１０００００１１１１１００１
００１１１００１１１１０００００００一方、ＳＴＲは
次の通りであった。

Ｓ　Ｔ　Ｒ＝１１１１０００００１１１１１００１００
１０１００１１１１０００００００このように、評価さ
れたコード・ストリングＳＴＲ′とオリジナルのコード
・ストリングＳＴＲとは、長さにおいて等しく、第２１
番目のシンボルが違うだけである。

上述の例に関して、デコードは従来の算術復号方法によ
ると説明した。これは正しく、上述の例において３５コ
ード・ポイント中の３１コード・ポイントを構成する予
測可能ポイントＰＰについて、５デコードは標準的な算
術復号方法を用いて行われる。しかしながら、この方法
は、上記被評価コード・ストリングＳＴＲ’　において
　で示された予測不能ポイントＵＰを解釈するために、
若干修正する必要がある。

第４図乃至第６図には、予測不能ポイントを処理するた
めに、標準算術復号器に加えるべき若干の修正を説明す
る流れ図が示されている。

第４図は、第１図を参照して説明した方法に従って符号
化された予測不能ポイントをデコードするための、関連
ある追加的なステップを示す。被復号ストリングが補助
シンボルを含む場合、現在ポイントがデフォルトの文脈
の中で予測不能であることが示される。もしそれ以上に
何のアクションもとられず、補助シンボルがオリジナル
・シンボル・アルファベットの１つのシンボルと置き換
えられない場合、復号出カストリングは、上記の例２で
説明したように、可能性のあるストリングのセットを表
わす。そうでない場合には、第１図に示された符号器が
使用したのと同じルールに従って、補助シンボルの文脈
が拡大され、これによって予測不能ポイントは予測可能
になり、復号が可能となる。

上記の例２では、被評価出カストリングＳＴＲ’中の補
助シンボル　については、文脈を増大させることによる
復号は行われなくて、補間が行われた。第５図は、補助
シンボルの値を、先に復号されたシンボルと後に復号さ
れたシンボルを両方含む当該シンボルの文脈の知識に基
づいて補間する２パス・デコード・オペレーションの一
部を示す。

換言すると、補助シンボルの前後でリアル・タイムでデ
コードされたシンボルが、これらのシンボルの間での内
挿による現在シンボルの値の評価に用いられる。このよ
うなデコード方法を″２パス″′と呼ぶのは、補助シン
ボルを評価するために、被復号シンボル・ストリングに
沿った２つのパスが必要とされるからである。第１のパ
スでは、予測５５ 可能ポイントがデコードされるとともに、予測不能ポイ
ントの値ではなく場所が決定される。そのようにして生
成されたストリングは、第２のパスにおいて、各予測不
能ポイントの前後の予測可能ポイントを含む文脈から当
該予測不能のポイントの値を内挿すべく、スキャンされ
る。

第６図は、１パス・デコーディングによって予測不能ポ
イントを評価するという、別のやり方を示す。ここでは
、被復号ストリングに沿った１回のパスが用いられ、各
補助シンボルは、その先行文脈からの外挿によって評価
される。このケースでは予測不能ポイントの後に現れる
シンボルは考慮されないので、補助シンボルのデコード
は、ストリングのデコードと同時に“ｉｎ　ｆｌｉｇｈ
ｔ”で実行され得るのである。

第７図は、第１図に示された方法を用いる算術符号器内
のユニット間のデータの流れを示す。入力ストリング中
の新シンボルａｉごとに１、それの文脈Ｃ１が所定のル
ールに従って決定される。

ルックアップ・テーブル（３）は、予測可能ボイ５６− ントと予測不能ポイントに夫々対応するシンボルとファ
ジー・セットのすべての、文脈Ｃ１に応した確率を収容
している。予測可能ポインｌ−Ｐ　Ｐについては、ルッ
クアップ・テーブル（３）からの出力は、現在シンボル
ａｉ又はこのシンボルを含むファジー・セットの確率ｐ
　（ｉ）と、それの累積確率Ｓ　（ｉ）である。ｐ　（
ｉ）とＳ　（ｉ）の値はセレクタ（６）に入力され、そ
の出力であるｐとＳは算術符号器（５）に入力される。

算術符号器（５）は、セレクタ（６）から夫々導かれた
確率ｐと累積確率Ｓに従って、現在シンボル又は現在フ
ァジー・セットを符号化する。

第２のルックアップ・テーブル（４）は、増大した文脈
Ｃ２に対応した確率ｐ’　　（ｉ）と累積確率Ｓ’　　
（ｉ）を収容する。ｐ″　（ｉ）とＳ″　（ｉ）の値は
セレクータ（６）に入力され、第１文脈Ｃ１が予測不能
ポイントＵＰを示す場合に選択される。

セレクタ（６）からの出力であるｐとＳは算術符号器（
５）に供給され、当該シンボルが通）ｉｉ゛のやり方で
符号化されるのを可能にする。

次に、第８図を参照すると、そこには第３図に基づいて
説明した方法を用いるファジー算術符号器における種々
のシフト・レジスタ間の関係が示されている。入力スト
リング中の各シンボルａｉについて、文脈が決定される
（１１）。この文脈は、予測可能ポイントＰＰと予測不
能ポイントＵＰを分けることを可能にする標準文脈テー
ブルと照合される。予測可能ポイントについての確率ｐ
（ｉ）と累積確率Ｓ　（ｉ）を収容するルックアップ・
テーブル（１２）によって夫々の確率が決定され、それ
らは算術符号器（１５）に入力されて、通常のやり方で
処理される。予測不能ポイントＵＰについては、現在シ
ンボルａｉが上記例２では１によって示された補助シン
ボルにセットされ、しかる後、現在シンボルａｉを含む
ファジー・セットについての確率を収めている第２のル
ックアップ・テーブル（１４）がアクセスされる。ｐ′
（ｉ）とＳ’　　（ｉ）によって表示され、夫々現在フ
ァジー・セットの確率と累積確率に対応する、第２ルツ
クアツプ・テーブル（１４）からの出力は、算術符号器
（１５）に入力され、通常のやり方で処理される。

第９図には、第５図を参照して説明した２パス・デコー
ディング方法を用いる２パス・デコーダの１部が示され
ている。第１パスの後、再構成されたストリングはレジ
スタ（２０）に入力され、再構成されたストリングの１
ポイントずつのスキャンを可能にする。現在シンボルａ
ｉが所定の補助シンボル・セットの中の１つであるとき
には、文脈と現在補助シンボルａｉがインターポレータ
（内挿器）　　（２１）に供給され、そこで予め定義さ
れたルールに従って補助シンボルがシンボル・アルファ
ベットの中の対応するシンボルに置き換えられる。イン
ターポレータ（２１）からの出力は、現在シンボルａｉ
とともにセレクタ（２２）に入力される。セレクタ２２
の出力は、現在シンボルａｉが補助シンボルか否かに応
じて、現在シンボルａｉ又はインターポレータ（２１）
からの出力のどちらかになる。

一般的なケースでは、ファジー・セットの数は９− １より多いことがあり得ることが理解されよう。

そのようなケースでは、現在の補助シンボルは、現在文
脈と現在シンボルａｉの属する特定のファジー・セット
とに従って再構成される。例えば、コード・ストリング
が子音字、母音字、数字、及び句読点（つまり４つの異
なったデータ・クラス）から成り、ある特定の予測不能
ポイントは母音字であることがわかっているならば、２
パス・デコーダの第１パスの際に、現在シンボルは母音
字クラスに対応するある特定の補助シンボルに置換され
る。そして、第２パスの際に、該シンボルは現在文脈か
ら補間され、これによって、該補助シンボルはある特定
の母音字と置き換えられる。

このように、本発明によれば、必要に応じて、有損失又
は無損失符号化に適合し得る算術符号化の改善された方
法が提供される。本発明の有損失符号化によれば、従来
の算術符号器に比べて、１６％も圧縮率が向上し得るこ
とが発見された。予測不能ポイントＵＰの数は比較的少
ないので、これらの問題のポイントにもっと多くのコン
ピユー６０− ティング・リソースを割り当てることも可能である。例
えば、ある所与のアプリケーションに関して、アベイラ
ブルなＣＰＵパワーをもってしては文脈の決定に４ビツ
トしか割り当てられないということもある。かかる状況
の下では、ソース・データ・ストリング中の各ポイント
について１６通りの文脈しか考慮することができない。

しかしながら、１％の予測不能ポイントＵＰについて１
０ビツトを割り当て、１０２４通りの文脈を作り出すこ
とも十分可能である。その結果、予測不能ポイントのエ
ントロピーが減少し、全体的な圧縮率が向上する。

Ｆ、効果 本発明によれば、シンボルの確率が該シンボルの文脈に
応じて決定される算術符号化において、圧縮の効率を従
来よりも向上させることができる。

【図面の簡単な説明】

第１図は、本発明による、一般化された無損失又はファ
ジー算術符号化方法の主要なステップを示す流れ図であ
る。 第２図は、本発明による無損失算術符号化方法の主要な
ステップを示す流れ図である。 第３図は、本発明によるファジー算術符号化方法の主要
なステップを示す流れ図である。 第４図は第１図に示した符号化法とともに用いるのに適
した復号方法の主要なステップを示す流れ図である。 第５図は、第３図に示した符号化法とともに用いるのに
適した２パス復号方法の追加的なステップを示す流れ図
である。 第６図は第３図に示した符号化法とともに用いられる１
パス復号方法を示す流れ図である。 第７図は、第１図の符号化プロシージャを実行する際の
レジスタ間でのデータの流れを示す図である。 第８図は、第３図の符号化プロシージャを実行する際の
レジスタ間でのデータの流れを示す図である。 第９図は、第８図の符号化プロシージャ実行の際の、２
パス・デコーダにおけるレジスタ間でのデータの流れを
示す図である。

Claims (9)

【特許請求の範囲】
1. （１）シンボルのパターンに算術符号化を施して、圧縮
   された出力コード・ストリングを生成する方法であって
   、上記シンボルは有限のシンボルのセットから取られ、
   各シンボルは上記パターン中のある位置に出現し、上記
   コード・ストリングは上記シンボルの上記位置に出現す
   る確率に依拠するある数であるような圧縮符号化方法に
   おいて、以下のステップを含むことを特徴とする方法。 （ａ）各位置の近傍の、文脈を表わす位置の所与の第１
   のサブ・パターンを評価することによって、該パターン
   中の予測可能位置ＰＰと予測不能位置ＵＰを決定する。 ここで、該位置サブパターンが選択されたシンボル・サ
   ブパターン・セットのうちの何れか１つを含むときにＵ
   Ｐは定義され、その他のすべての場合にＰＰが定義され
   る。 （ｂ）ＰＰ中の各シンボルについて、各自の文脈におけ
   る各自のシンボルの確率を用いて、通常の算術符号化を
   適用する。 （ｃ）ＵＰ中の各シンボルについて、各自の位置に出現
   し得るシンボルの所定のセットの組合せ確立を用いて、
   通常の算術符号化を適用する。
2. （２）シンボルのパターンに無損失算術符号化を施して
   、圧縮された出力コード・ストリングを生成する方法で
   あって、上記シンボルは有限のシンボルのセットから取
   られ、各シンボルは上記パターン中のある位置に出現し
   、上記コード・ストリングは上記シンボルの上記位置に
   出現する確率に依拠するある数であるような圧縮符号化
   方法において、以下のステップを含むことを特徴とする
   方法。 （ａ）各位置の近傍の、文脈を表わす位置の所与の第１
   のサブ・パターンを評価することによって、該パターン
   中の予測可能位置ＰＰと予測不能位置ＵＰを決定する。 ここで、該位置サブパターンが選択されたシンボル・サ
   ブパターン・セットのうちの何れか１つを含むときにＵ
   Ｐは定義され、その他のすべての場合にＰＰが定義され
   る。 （ｂ）ＰＰ中の各シンボルについて、各自の文脈におけ
   る各自のシンボルの確率を用いて、通常の算術符号化を
   適用する。 （ｃ）ＵＰ中の各シンボルについて、上記ＵＰが予測可
   能となるように、上記所与の第１のサブパターンよりも
   大きな第２の位置のサブパターンを評価する。 （ｄ）上記第２のサブパターンから導かれた各シンボル
   の更新された確率によって、算術符号化を実行する。
3. （３）ＵＰ中の各シンボルについて、さらに、上記ＵＰ
   が予測可能となるように、上記所与の第１のサブパター
   ンよりも大きな第２の位置のサブパターンを評価し、 上記第２のサブパターンから導かれた各シンボルの更新
   された確率によって、算術符号化を実行する ことを特徴とする、請求項１記載の方法。
4. （４）有損失符号化を行うために、ＵＰ中の各シンボル
   について、第１の位置のサブパターン中の対応するシン
   ボルが補助シンボルに置き換えられることを特徴とする
   、請求項１記載の方法。
5. （５）請求項１乃至４の何れかに記載の方法を実行する
   ためのシステムであって、 各シンボルについて、文脈を表わす上記第１の位置のサ
   ブパターンを記憶するための第１のメモリと、 可能性のあるサブパターンの所定のセットを記憶するた
   めの第２のメモリと、 各シンボルについて、第１メモリ中の第１のサブパター
   ンを第２メモリ中のサブパターン・セットのサブパター
   ンと比較し、上記第１のサブパターンとマッチする上記
   サブパターン・セット中のサブパターンがある場合には
   第１の信号を生成し、そうでない場合には第２の信号を
   生成する比較手段と、 可能性のあるサブパターンの完全セットの各々の文脈中
   でのシンボル・セット中の各シンボルの確率を保持する
   第１のルックアップ・テーブルを記憶するための第３の
   メモリと、上記所定のサブパターン・セットの各々の文
   脈での可能性のあるシンボルの所定のセットの組合せ確
   率を保持する第２のルックアップ・テーブルを記憶する
   ための第４のメモリと、 比較手段と結合され、上記第１の信号に応答して上記第
   ３メモリを読み取る一方、上記第２の信号に応答して上
   記第４メモリを読み取り、上記サブパターンに対応する
   記憶されている確率を決定する読取手段と、 読取手段と結合され、決定された確率に応答して各シン
   ボルを符号化する算術符号化手段を具備する、圧縮符号
   化システム。
6. （６）請求項１記載の方法に従って符号化されたシンボ
   ル・パターンを表わすコード・ストリングを復号する方
   法であって、 出力コード・ストリング中の各位置について、その近傍
   の、符号化の際に用いた位置の所与の第１のサブパター
   ンに対応する位置のサブパターンを評価し、該サブパタ
   ーンが所与のシンボル・サブパターン・セットのうちの
   １つ又は１以上のシンボルが補助シンボルと置換された
   これら所与のシンボル・サブパターンの何れかを含むか
   否かを決定し、 テスト結果が肯定的であって予測不能ポイントＵＰを示
   す場合には、出力シンボル・パターン中の各自の位置に
   補助シンボルを挿入し、 テスト結果が否定的であって予測可能ポイントＰＰを示
   す場合には、コード・ストリングの頭部（リーディング
   ）デジットを評価することによって、オリジナル・シン
   ボル・パターンの１シンボルを再構成すべく通常の算術
   符号化を適用し、コード・ストリングから、復号され再
   構成されたシンボルに対応する数を引くことによって、
   コード・ストリングの頭部デジットを変更し、出力スト
   リング中の各補助シンボルについて、最終出力シンボル
   ・パターン中の各自の位置に実際に挿入されるべきシン
   ボルを、各補助シンボルの近傍の復号・再構成されたシ
   ンボルの文脈に基づいて決定する ステップを含むことを特徴とする方法。
7. （７）各補助シンボルが、当該補助シンボルに先行する
   先行して復号されたシンボルのパターンから外挿するこ
   とによって、上記シンボル・セット中の１つのシンボル
   と置換される、請求項６記載の方法。
8. （８）各補助シンボルが、当該補助シンボルの前と後の
   、当該補助シンボルに先行して復号されたシンボルのパ
   ターンの間で内挿することによって、上記シンボル・セ
   ット中の１つのシンボルと置換される、請求項６記載の
   方法。
9. （９）出力シンボル・パターン中に出現する各補助シン
   ボルについて、各補助シンボルに対応するオリジナル・
   シンボルの決定が可能になるように、各補助シンボルの
   近傍の位置のサブパターンが拡大される、請求項６記載
   の方法。