JPH1032496A

JPH1032496A - 算術符号化装置

Info

Publication number: JPH1032496A
Application number: JP18794896A
Authority: JP
Inventors: Toshihiko Okamura; 利彦岡村
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1996-07-18
Filing date: 1996-07-18
Publication date: 1998-02-03
Anticipated expiration: 2016-07-18
Also published as: JP3018990B2

Abstract

(57)【要約】【課題】適応的多値算術符号化において処理速度の高
速化を可能にする。【解決手段】累積頻度格納手段２は累積頻度の最大値
を２の整数巾でとる。この巾数を用いて、符号化手段５
は算術符号化で必要な除算をシフトに置き換える。出現
頻度格納手段２は入力データ中の各シンボルの頻度を計
測し、記録する。カウンタ３は入力データ中のシンボル
の数を計測し、累積頻度更新のタイミングを累積頻度更
新手段４に知らせる。累積頻度更新手段４は累積頻度格
納手段２と出現頻度格納手段１に格納されている情報か
ら新たな累積頻度を計算し、累積頻度格納手段２を更新
する。このとき、累積頻度更新手段４は累積頻度の最大
値を２の整数巾で保った形で更新処理を行う。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は算術符号化装置に関
し、特に適応的かつ多値の算術符号化装置に関する。

【０００２】

【従来の技術】データ圧縮技術はデータの伝送、蓄積の
効率化のために不可欠の技術である。基本的には、よく
現れるシンボルには短い符号語を割り当て稀にしか現れ
ないシンボルには長い符号語を割り当てることで圧縮は
達成される。このような符号化方式として、ハフマン符
号、算術符号などが知られているが、算術符号は特に圧
縮率に優れた方式である。

【０００３】データ中のシンボルを｛０，１，２，…，
Ａ−１｝とし、シンボルｋの現れる確率をｐ（ｋ）とす
る。算術符号化はデータに対して［０，１）内の区間を
対応させることで符号化を行う。符号化処理は１シンボ
ルずつ逐次的に行うことができる。具体的にはデータａ
（０）ａ（１）ａ（２）・・・ａ（ｎ−１）に対して次
の手順で符号化を行う。１．初期状態Ｉ（０）＝［０，１）（０から１までの区
間）２．ｊ＝０，１，…，ｎ−１に対して次の手順を繰り返
す：Ｉ（ｊ）をｐ（０）：ｐ（１）：・・・：ｐ（Ａ−
１）の比に分割し、ａ（ｊ）に対応する区間（ｐ（ａ
（ｊ））の比率に対応する区間）を新たにＩ（ｊ＋１）
とする。３．最終的に得られた区間Ｉ（ｎ）の１点を二進列で表
し、符号語として出力する。

【０００４】区間Ｉ（ｎ）の大きさはｐ（ａ（０）） ^*
ｐ（ａ（１））^*・・・ ^*ｐ（ａ（ｎ−１））であり、
この区間の１点を他の区間と識別できるようにするため
には、ほぼ−ｌｏｇ（ｐ（ａ（０）） ^*ｐ（ａ（１））
^*・・・ ^*ｐ（ａ（ｎ−１）））ビットで表せばよい。
‘^*’は乗算を表す。データの各文字が独立に生起して
いるならばｐ（ａ（０） ^*ａ（１）^*・・・ ^*ａ（ｎ−
１））＝ｐ（ａ（０）） ^*ｐ（ａ（１））^*・・・ ^*ｐ
（ａ（ｎ−１））となり、−ｌｏｇ（ｐ（ａ（０） ^*ｐ
（ａ（１））^*・・・ ^*（ａ（ｎ−１））ビットは情報
理論的には最良の符号長である。よって算術符号は原理
的には最良の符号化方式となる。

【０００５】以上に述べた方法はインプリメント上二つ
の問題がある。第１に、一般にシンボルの現れる確率は
事前には分からないということである。第２に区間を順
次分割していくときの計算精度の問題である。高い計算
精度で符号化を行おうとすると、非常に高い計算コスト
となり、圧縮速度が大きく劣化する。

【０００６】まず、第１の問題に対しては、図８に示す
ように予測手段５１を設けることにより、今までのデー
タの統計から動的に確率を求める方法が考案されてき
た。符号化手段５０は予測手段から得られる確率に基づ
いて符号化処理（区間の算出）を行う。復号手段５２は
復元データに基づいて予測手段５３が供給する確率に基
づいて復元を行うことによって、正しい処理を行うこと
ができる。基本的には予測手段５１はデータの過去の頻
度に基づいて累積頻度を計算し、符号化手段５０に供給
する。

【０００７】一方、第２の問題に対しては、区間の計算
の精度を劣化させることで解決を試みる努力がなされて
きた。

【０００８】二値の場合にはこれらの問題は単純化さ
れ、Ｑコーダーと呼ばれる有効な方式が提案されてい
る。これは「１９８８年１１月、アイ・ビー・エム・ジ
ャーナル・オブ・リサーチ・アンド・デヴェロップメン
ト、第３２巻、第６号、７１７〜７２６頁（ＩＢＭＪ
ＯＵＲＮＡＬＯＦＲＥＳＥＡＲＣＨＡＮＤＤＥ
ＶＥＬＯＰＭＥＮＴ，ＶＯＬ．３２，ＮＯ．６，ＮＯＶ
ＥＭＢＥＲ１９８８，ＰＰ．７１７−７２６）に詳述
されている。この方式は二値画像圧縮のＩＴＵ勧告であ
るＪＢＩＧなどで利用されている。

【０００９】しかし、多値データは多値のまま符号化し
た方が効率良く処理が行える。計算機上のデータはバイ
ト（８ビット）単位で扱うことが多く、バイト単位で圧
縮を行うことはごく自然な処理であり、特にソフトウェ
アでのインプリメントでは二値の場合よりも高速化が可
能となる。多値算術符号は「１９８７年７月、コミュニ
ケーションズ・オブ・エー・シー・エム、第３０巻、第
６号、５２０〜５４０頁（ＣＯＭＭＵＮＩＣＡＴＩＯＮ
ＳＯＦＡＣＭ，ＶＯＬ．３０，ＮＯ．６，ＰＰ．５
２０−５４０）」に述べられている方法が最も洗練され
た方式の一つである（以下、“ＣＡＣＭ”と呼ぶことに
する）。ＣＡＣＭは区間計算を固定桁数の整数演算で行
えるようにした。以下、ＣＡＣＭについて説明を行う。

【００１０】シンボル｛０，１，・・，Ａ−１｝に対し
て、頻度の配列Ｆを用意する。Ｆ（ｋ）はｋに対する頻
度を表す。頻度は全て整数値でとる。また、累積頻度の
配列Ｃを用意する。Ｃ（０）＝０として、ａ＝１，・
・，Ａ−１，Ａに対する累積頻度は次の式で定義され
る。

【００１１】Ｃ（ａ）＝Ｆ（０）＋Ｆ（１）＋・・・Ｆ（ａ−１）．Ｍ＝Ｃ（Ａ）とする。Ｍはシンボルの頻度の総計に対応
する。Ｎを正の整数とする。算術符号は原理的には区間
は［０，１）を分割していくが、ＣＡＣＭでは［０，
Ｎ）内の区間を分割する処理を行うことで符号化が進
む。これは［０，１）を有効桁ｌｏｇ（Ｎ）ビット（ｌ
ｏｇの底は２）で見ていることと同一にもなる。Ｎは通
常２の巾でとる。符号化区間は、その上端を表すｕｐｐ
ｅｒ、その下端を表すｌｏｗｅｒ、その幅を表すｒａｎ
ｇｅを用いて表される。この三つの値は整数値で単純に
次の関係を満たす。

【００１２】ｒａｎｇｅ＝ｕｐｐｅｒ−ｌｏｗｅｒ＋１．ＣＡＣＭでも、通常の算術符号と同様に現在の区間をＦ
（０），Ｆ（１），・・・，Ｆ（ａ−１）の比に分割
し、符号化しているシンボルに対応している区間を新た
な区間とすることを処理の基本とする。実際には符号化
しているシンボルに対応する区間さえ求めればよい。こ
れは累積頻度Ｃを用いて計算できる。図８の５１，５３
に示されている予測手段はこの累積頻度を符号化手段、
復号手段に供給する装置であると考えて良い。

【００１３】図９はＣＡＣＭにおける処理の流れを示す
フローチャートである。図９は１シンボルに対する処理
の流れを示したのみで、実際には入力データが終わるま
でこの処理が繰り返される。

【００１４】入力データを読み込む（ステップ６０）。
これをａとする。

【００１５】ａに対応する区間を求める（ステップ６
１）。

【００１６】ｕｐｐｅｒ←ｌｏｗｅｒ＋［ｒａｎｇｅ＊
Ｃ（ａ＋１）／Ｍ］−１，ｌｏｗｅｒ←ｌｏｗｅｒ＋［ｒａｎｇｅ＊Ｃ（ａ）／
Ｍ］．ここで［Ｘ］はｘを越えない最大の整数を表す。図示す
ると、図１０のように区間が縮小される。新たなｒａｎ
ｇｅの大きさは、ｒａｎｇｅ＊（Ｃ（ａ＋１）−Ｃ（ａ））／Ｍ＝ｒａｎ
ｇｅ＊Ｆ（ａ）／Ｍ，にほぼ等しく、現在のｒａｎｇｅのＦ（ａ）／Ｍ倍の区
間を新たな区間としている。

【００１７】新しい区間が確定したら、必要に応じてビ
ット出力と区間の正規化処理を行う（ステップ６２）。
ｌｏｗｅｒとｕｐｐｅｒがともにＮ／２より大である場
合は、その区間を縮小してもＮ／２より上にある。よっ
て符号語の次のビットは１と確定される。逆に、ｌｏｗ
ｅｒ，ｕｐｐｅｒともにＮ／２より小である場合、その
区間を縮小してもＮ／２より下になり、符号語の次のビ
ットは０と確定される。このようにしてビット出力（符
号語出力）が逐次行われる。新しい区間のｒａｎｇｅ
は、次のシンボルに対してステップ６１の処理を行った
ときに、シンボルに対応する区間の大きさがすべて１以
上になるようにしなければならない。そうでない場合に
は一つの区間に複数のシンボルが対応し、正しく復元で
きなくなる。よってｒａｎｇｅは十分な大きさを保たな
ければならない。この処理が正規化の処理である。ビッ
ト出力と正規化は次の三つの処理に分類される。（ａ）ｕｐｐｅｒ，ｌｏｗｅｒともにＮ／２より大きいｕｐｐｅｒ←（ｕｐｐｅｒ−Ｎ／２）＊２＋１，ｌｏｗｅｒ←（ｌｏｗｅｒ−Ｎ／２）＊２．（ｂ）ｕｐｐｅｒ，ｌｏｗｅｒはともにＮ／２より小さ
いｕｐｐｅｒ←ｕｐｐｅｒ＊２，ｌｏｗｅｒ←ｌｏｗｅｒ＊２．（ｃ）それ以外の場合ｕｐｐｅｒ←（ｕｐｐｅｒ−Ｎ／４）＊２＋１，ｌｏｗｅｒ←（ｌｏｗｅｒ−Ｎ／４）＊２＋１．最後に頻度の配列Ｆ、累積頻度の配列Ｃの更新を行う
（ステップ６３）。これは図８では予測手段５１の範疇
に入る処理である。ＣＡＣＭではシンボルａの符号化が
終了した後、次のシンボルの符号化に備えてＦ（ａ）←Ｆ（ａ）＋ｖ，と頻度を更新する。ｖの値は１〜３２がとられる。Ｆの
値の変化に応じてＣも変更する。

【００１８】

【発明が解決しようとする課題】ＣＡＣＭでは図９のス
テップ６１に示したように、１シンボル処理する毎に乗
算と除算を行う必要がある。このことは算術符号の圧縮
速度がハフマン符号に比べて劣ることの要因の一つとな
っている。その中でも特に除算の影響は大きい。

【００１９】また、多値算術符号化では予測手段５１に
おける処理である、図９のステップ６３の累積頻度更新
にかかる時間も問題になる。図１１は累積頻度格納手段
の変遷を例示する。この図を用いて累積頻度の更新にか
かるコストを説明する。

【００２０】図１１はシンボルが｛０，１，２，３，
４｝からなる場合の例である。累積頻度配列７０は各シ
ンボルに対する累積頻度が０、２、６、８、９、１６の
状況である。‘（５）’に対応する要素‘１６’は各シ
ンボルの頻度の総計である。この時、各シンボルに対す
る頻度は２、４、２、１、７となる。

【００２１】ここで、ＣＡＣＭでは入力０の符号化処理
を終えるとＦ（０）←Ｆ（０）＋１（ｖ＝１とする）と
なり、それにつれて累積頻度の更新が行われ、７１のよ
うになる。つまり、シンボル１、２、３、４、（５）に
対する累積頻度（図１０の７１で網かけの部分）を１ず
つインクリメントしなければならない。以下同様に、入
力シンボルを処理する度に７２，７３のように累積頻度
配列を更新しなければならない。つまり、最悪の場合で
入力データの１シンボルにつきＡ個のシンボル（Ａはシ
ンボルの総数）に対する累積頻度を更新しなければなら
ない。これは１シンボル＝１バイトの場合（シンボル数
２５６）でも非常に大きな時間となる。

【００２２】これに対し、累積頻度の配列に構造を持た
せることで、更新処理にかかる時間を削減する研究が行
われてきた。その中でも最も有力なのが、「１９９４年
３月、ソフトウェア−プラクティス・アンド・エクスペ
リエンス、第２４巻、第３号、３２７〜３３６頁（ＳＯ
ＦＴＷＡＲＥ−ＰＲＡＣＴＩＣＥＡＮＤＥＸＰＥＲ
ＩＥＮＣＥ，ＶＯＬ．３２，ＮＯ．３，ＰＰ．３２７−
３３６．）」に示されている方法（ＢＩＴ法と呼ばれ
る）である。ＢＩＴ法を用いても、シンボル数をＡとす
ると符号化と累積頻度更新のため、１シンボル当りｌｏ
ｇ（Ａ）回程度の累積頻度格納手段の要素にアクセスす
る必要がある（ｌｏｇの底は２）。

【００２３】一方、乗算・除算不要の多値算術符号は
「１９８８年１月、アイ・イー・イー・トランザクショ
ン・オブ・コミュニケーション、第３７巻、第１号、９
３〜９８頁（ＩＥＥＥＴＲＡＮＳＡＣＴＩＯＮＳＯ
ＦＣＯＭＭＵＮＩＣＡＴＩＯＮＳ，ＶＯＬ．３７，Ｎ
Ｏ．１，ＪＡＮＵＡＲＹ，１９８８，ＰＰ．９３−９
８．）」に提案されてはいる。しかし、算術符号化は動
的に頻度を更新しながら圧縮を行うことによって初めて
その真価が発揮されるが、この文献では累積頻度更新手
法に関しては全く触れていない。上記のＢＩＴ法を累積
頻度更新手法に用いた場合には、符号化におけるロスが
大きく、圧縮率の劣化が大きいものとなる。この文献に
示されている方式と相性のよい累積頻度更新手法は上記
のＣＡＣＭの文献で述べられているが、この方式は最悪
の場合には１シンボル当りＡ回累積頻度格納手段の要素
にアクセスする必要がある。

【００２４】本発明は、適応的多値算術符号化方式に対
して、除算の回避により高速化を図るとともに、その際
の有効な累積頻度更新方式を与えることを目的とする。

【００２５】

【課題を解決するための手段】本発明の累積頻度格納手
段（図１の２）は常にその要素の最大値を２の整数巾で
とる。累積頻度更新手段（図１の４）は累積頻度格納手
段の最大値を２の整数巾に保つ形で更新処理を行う。

【００２６】累積頻度の最大値を一定に保ったまま更新
処理を行う場合には、１シンボル処理する度に更新処理
を行うのではなく、出現頻度格納手段（図１の１）を設
け、入力データのブロック単位での頻度を計測して、そ
の頻度を元に累積頻度を更新する。

【００２７】累積頻度更新のタイミングを図るために、
カウンタ（図１の３）を用意し、所定の数（ブロックの
大きさ）のシンボルの符号化処理を終えたかどうかを判
定する。

【００２８】累積頻度の最大値を２の整数巾に保つこと
により、従来の算術符号化で必要になっていた除算をビ
ットシフトに置き換えることができる。

【００２９】１シンボルずつ累積頻度を更新する方法で
は累積頻度の最大値を一定に保つことは困難であるが、
入力データのブロック単位での頻度を計測して、その頻
度を元に累積頻度を更新することにより容易に行うこと
ができる。ブロックの大きさをある程度大きくすれば、
従来に比べて入力データ１シンボル当りの更新にかかる
時間を短縮することも可能となる。また、この際、従来
の累積頻度格納手段で用いられていた、木構造等による
複雑なデータ構造は不要となる。

【００３０】

【発明の実施の形態】本発明の実施の形態について図面
を参照して詳細に説明する。

【００３１】図１は本発明の実施の形態の一例を示すブ
ロック図で、出現頻度格納手段１、累積頻度格納手段
２、カウンタ３、累積頻度更新手段４、符号化手段５か
ら成る。符号化手段を除いた部分は図８の予測手段５１
に相当する。

【００３２】出現頻度格納手段１は、入力データ中に各
シンボルが現れた回数を記録する。各シンボルに対応す
るエントリを持つ配列などで構成され、各エントリは対
応する頻度を計測し、記録する。

【００３３】累積頻度格納手段２は、符号化に必要な各
シンボルの累積頻度を記録する。各シンボルに対応する
エントリを持つ配列などで構成され、各エントリは対応
する累積頻度を保持する。累積頻度の最大値は２の整数
巾の値になるようにしてある。

【００３４】カウンタ３は、入力データ中のシンボル数
をカウントする。

【００３５】累積頻度更新手段４はカウンタ３の状況に
基づいて、出現頻度格納手段１と累積頻度格納手段２に
記録されている値から新たな累積頻度を作成して、累積
頻度格納手段２の内容を更新する。このとき、累積頻度
の最大値は２の整数巾になるように更新処理を行う。

【００３６】符号化手段５は符号化するシンボルに対応
する累積頻度情報に基づいて、現在の区間の縮小とそれ
に伴う区間の正規化処理や圧縮データ出力を行い、実際
に圧縮データを生成する。累積頻度の配列をＣとしたと
き、シンボルａを符号化するときに累積頻度格納手段２
から符号化手段５に与えられる累積頻度情報はＣ
（ａ）、Ｃ（ａ＋１）とシンボルの頻度の合計に対する
ビット数（従来方式ではシンボルの頻度の合計の値その
もの）となる。

【００３７】次に、図１、図２および図３を参照して本
発明の動作について説明する。図２は本発明の動作を示
すフローチャートであり、図３は本発明の符号化による
区間の縮小の様子を示した図である。図１の出現頻度格
納手段１に対応する配列をＦ、累積頻度格納手段２に対
応する配列をＣとする。シンボル数をＡとし、Ｍ＝Ｃ
（Ａ）を２のｍ乗（ｍ：整数）とする。算術符号化に使
用する区間［０，Ｎ）とする。また、図１のカウンタ３
のカウント値を格納するレジスタをＳとする。図２は１
シンボルの処理の流れを示すもので、実際の圧縮処理に
おいてはこの操作を繰り返す。

【００３８】入力データを読み込む（ステップ１０）。
これをａとする。入力データは一度バッファに格納され
ることもある。

【００３９】ａに対応する区間を求める（ステップ１
１）。これは次の操作で行われる：ｕｐｐｅｒ←ｌｏｗｅｒ＋［ｒａｎｇｅ＊Ｃ（ａ＋１）
＞＞ｍ］−１，ｌｏｗｅｒ←ｌｏｗｅｒ＋［ｒａｎｇｅ＊Ｃ（ａ）＞＞
ｍ］．ここで［Ｘ］はｘを越えない最大の整数を表し、ｘ＊ｙ
はｘとｙの乗算を表す。また、ｘ＞＞ｍはｘをｍビット
右へ（小さい方へ）シフトすることを示す。図３はこの
処理によりどのように区間が縮小されるのかを示してい
る。

【００４０】新しい区間が確定したら、必要に応じてビ
ット出力と区間の正規化処理を行う（ステップ１２）。
これは従来の算術符号化における処理と同様に行うこと
ができる。

【００４１】ａの出現頻度Ｆ（ａ）とカウンタＳを更新
する（ステップ１３）；Ｆ（ａ）←Ｆ（ａ）＋１，Ｓ←Ｓ＋１．Ｓが予め定められた閾値Ｔに達したかどうかを判別する
（ステップ１４）。Ｔは累積頻度更新処理の間隔を決め
るパラメータである。

【００４２】Ｓが閾値Ｔに達したら、累積頻度更新処理
を行う（ステップ１５）。ＣとＦから計算できる関数Ｇ
を用いて、配列Ｃの値を書き直す。Ｓと配列Ｆのすべて
の要素を０にリセットする。本発明では、累積頻度が更
新されるまでの間は、同一の累積頻度を用いて符号化が
行われる。

【００４３】全体の処理の流れと累積頻度更新の関係に
ついて図４に示す例を用いて詳細に説明する。図４は累
積頻度更新の過程を示すブロック図で、入力データ２
０、累積頻度格納手段２１、２２、出現頻度格納手段２
３、累積頻度更新手段２４から成る。

【００４４】入力データ２０は｛０，１，２，３，４｝
の４つのシンボルから成り、左から右の順序で並んでい
る。入力データは幾つかのブロックに分けられ、ブロッ
クの大きさ（シンボル数）はステップ１４の閾値Ｔの大
きさに相当する。

【００４５】累積頻度格納手段２１は入力データ２０の
ブロック（ｎ）の先頭における累積頻度の状態を表す配
列である。ブロック（ｎ−１）までのデータを符号化し
た時点で、累積頻度が２１のような状態になったとして
いる。ブロック（ｎ）のデータはこの累積頻度を用いて
符号化する。累積頻度の最大値を１６（２の整数巾）に
設定しているため、符号化における除算はビットシフト
に置き換えることができる。

【００４６】出現頻度格納手段は、ブロック（ｎ）の先
頭では各要素ともに０にリセットされており、ブロック
（ｎ）のシンボルを符号化する度に対応する要素が１イ
ンクリメントされる（図２のステップ１３に相当）。図
５の出現頻度格納手段２３はブロック（ｎ）の符号化終
了時の出現頻度を示している。つまり、２３の各要素は
ブロック（ｎ）において各シンボルが現れた回数を示し
ている。

【００４７】ブロック（ｎ）の符号化を終了した時点
（ステップ１４に相当）で、出現頻度格納手段２３と累
積頻度格納手段２１に格納されている値を用いて累積頻
度更新手段２４は累積頻度を更新する（ステップ１５に
相当）。図５では、累積頻度格納手段２１から計算され
る頻度（ｆ（ａ）＝Ｃ（ａ＋１）−Ｃ（ａ））と出現頻
度格納手段２３の値との平均値をシンボルの頻度とし、
その頻度に基づいて累積頻度を計算している。

【００４８】累積頻度格納手段２２は更新された累積頻
度を示している。このとき、累積頻度の最大値は１６に
保たれていることに注意する。ブロック（ｎ＋１）は累
積頻度格納手段２２を用いて符号化を行う。

【００４９】図５は累積頻度更新手段４の動作例（図２
のステップ１５の例）を具体的に示すフローチャートで
ある。出現頻度格納手段１、累積頻度格納手段２から得
られる頻度に対して重みづけ和をとり、累積頻度の最大
値はそのままになるようにしている。この処理において
も、整数値演算のみで行い、重みづけに必要な除算も重
みの和を２の整数巾でとることによりシフトに回避する
ことを可能にしている。

【００５０】シンボルを０，１，・・・，Ａ−１とす
る。Ｆは出現頻度格納手段１で、Ｆ（ｉ）はシンボルｉ
に対する出現頻度とする。Ｃは累積頻度格納手段２で、
Ｃ（ｉ）はシンボルｉに対する累積頻度とする。Ｃ
（ｉ）はｉ＝Ａに対しても（便宜上）定義され、Ｃ
（Ａ）＝Ｍ（２の整数巾）とする。実際にはＣはＡに対
するエントリを持つ必要はない。何故ならばＭは固定さ
れているからである。図６の動作はカウンタの値Ｓ（＝
Ｆ（０）＋Ｆ（１）＋・・・＋Ｆ（Ａ−１））が閾値Ｔ
に達したら行われる。Ｔは予め決められた整数値ｓに対
して、Ｔ＝（Ｍ−Ａ）＞＞ｓ，となるように設定される。“ｘ＞＞ｙ”はｘをｙビット
分だけ右へ（小さい方へ）シフトすることを意味する。
ｓはＡのビット数以下の値でなければならない。また整
数値ｄを任意に設定する。ｄに対してＤを、Ｄ＝（１＜＜ｄ），となるように定める。“ｘ＜＜ｙ”はｘをｙビット分だ
け左へ（大きい方へ）シフトすることを意味する。Ｄは
２の整数巾である。Ｒは切捨てにより生じた端数を保持
する変数である。ｆ，ｇ，ｒは計算上必要な変数であ
る。

【００５１】まず第１に初期化を行う（ステップ３
０）。カウンタの値Ｓを０にリセットする。ｇの値は０
（＝Ｃ（０））に設定し、Ｒの値は０に設定する。Ｒの
値は０以外でも、Ｄより小さい値であったらよい。シン
ボルｉ＝０に設定する。

【００５２】シンボルｉの新たな頻度を計算する（ステ
ップ３１）。

【００５３】ｆ←Ｃ（ｉ＋１）−ｇ，とすることで、ｆは現在の累積頻度で表されるシンボル
ｉの頻度を表す。続いてｇは次のシンボルの頻度を計算
するのに備えてＣ（ｉ＋１）に設定される。ｆとＦ
（ｉ）から次の式（１）の右辺の値を求めて、改めてｆ
とする。

【００５４】ｆ←ｆ＊（Ｄ−１）＋Ｆ（ｉ）＜＜ｓ＋１．（１）これは、累積頻度格納手段から得られる頻度ｆと出現頻
度格納手段から得られる頻度をほぼ（Ｄ−１）：（１＜
＜ｓ）の比で加算していることに相当する。Ｔとｓの値
の決め方から、すべてのシンボルに対して（１）の右辺
のｆの値は加算したものはＭのＤ倍になっている。累積
頻度の最大値をＭにするためには、（１）で得られたｆ
をＤで割る必要がある。まず、ｆをＤで割った時の余り
（０からＤ−１までの値）をＲに加算する。Ｄは２の巾
であるため、この余りは（Ｄ−１）とｆのビット毎の排
他的論理和をとれば得られるので、実際には除算を行う
必要がない。こうして得られたｆをｄビット右へシフト
する。これはＤで割って、小数点以下を切り捨てた値と
等しい。累積頻度格納手段から計算されるシンボルｉの
頻度（ステップ４１の（Ｃ（ｉ＋１）−ｇ）で計算され
る値）が０でないのなら、Ｆ（ｉ）が０であっても式
（１）で計算されるｆの値は０でないことに注意する。
このことは、算術符号化が正しく動作するために必須の
条件である。

【００５５】ＲがＤより大きいか判別する（ステップ３
２）。

【００５６】ＲがＤより大きい場合はｆの値を１増加さ
せる（ステップ３３）。ＲをＤで割った時の余りを改め
てＲとおく。こうして本来なら小数点以下で切り捨てら
れてしまう値を有効に頻度に反映させることができる。

【００５７】シンボル（ｉ＋１）に対する累積頻度Ｃ
（ｉ＋１）の計算を行う（ステップ３４）。これは既に
得られているＣ（ｉ）にステップ３１または３３までで
得られているｆを加算することで行われる。Ｆ（ｉ）は
０にリセットされ、ｉはｉ＋１に設定される。

【００５８】ｉ＝Ａ−１となったら累積頻度更新処理を
終了する（ステップ３５）。Ｃ（Ａ）はＭで固定されて
いるために計算する必要はない。

【００５９】次に、累積頻度格納手段２の初期状態につ
いて説明する。

【００６０】初期状態は各シンボルの出現頻度を一定の
値として設定することが通常行われる。最初から累積頻
度の最大値Ｍを固定しておく場合には、各シンボルの出
現頻度をＭ／Ａとして累積頻度を計算し、累積頻度格納
手段２の初期値とする。また、最初はＭを小さく設定し
ておいて、符号化が進むにつれて順に大きくしていく方
法も考えられる。その際、Ｍは常に２の整数巾に保った
まま大きくしていくことが必要となる。特定のクラスの
データの符号化に使用する際には出現頻度を一定とする
のではなく、そのクラスの統計的性質に合わせた初期状
態とすることも可能である。

【００６１】次に本発明の別の実施の形態について述べ
る。

【００６２】算術符号化は予測手段を工夫することによ
って圧縮率の向上をみることができる。このとき、予測
手段はある状態の下でのシンボルの累積頻度を符号化手
段へ供給する。例えば、ｎ次マルコフモデルと呼ばれる
予測手段では、直前のｎシンボルを状態とし、各状態の
下での頻度、累積頻度を計算する。図６は二つの状態に
基づいて符号化を行う場合の本発明の構成を示し、状態
判別手段４０、出現頻度テーブル４１、累積頻度テーブ
ル４２、カウンタテーブル４３、累積頻度更新手段４
４、符号化手段４５から成る。もちろん状態数は２に限
らず、任意の数にすることができる。

【００６３】状態判別手段４０は、シンボルをどの状態
に基づいて符号化するかを決定する。１次マルコフモデ
ルであったら直前の１文字を記憶しておくことにより、
状態が決定される。

【００６４】出現頻度テーブル４１は複数の出現頻度格
納手段から成る。状態一つに対して、一つの出現頻度格
納手段が対応する。それぞれの出現頻度格納手段は図１
の出現頻度格納手段１と同一の構造を持つ。ただし、状
態によってシンボル数が変わってもよい。

【００６５】累積頻度テーブル４２は複数の累積頻度格
納手段から成る。状態一つに対して、一つの累積頻度格
納手段が対応する。それぞれの累積頻度格納手段は図１
の累積頻度格納手段２と同一の構造を持つ。ただし、状
態によってシンボル数が変わってもよい。

【００６６】カウンタテーブル４３は複数のカウンタか
ら成る。状態一つに対して、一つのカウンタが対応す
る。それぞれのカウンタは図１のカウンタ３と同一の構
造を持つ。

【００６７】累積頻度更新手段４４は、図１の累積頻度
更新手段４と同様の働きをする。状態に応じて累積頻度
更新間隔や累積頻度更新方法を選択することもできる。
例えば予めデータの統計的性質の変化が激しいとわかっ
ている状態に関しては累積頻度更新間隔を小さく設定し
ておいたり、累積頻度更新手段４は出現頻度格納手段１
から得られる頻度に大きな重みをつけて累積頻度更新を
行うよう設定しておくなどの処置を施すことが可能であ
る。

【００６８】符号化手段４５は、図１の符号化手段５と
同一である。

【００６９】図６の構成に示した本発明の動作は、図２
を用いて表した動作とほぼ同一である。状態を｛ａ，
ｂ｝の２種類とする。図６で、入力シンボルを状態ａで
符号化するときには、出現頻度テーブル４１では出現頻
度格納手段ａ，カウンタテーブル４３ではカウンタａが
更新される。このとき、カウンタａが一定値に達した場
合には、累積頻度更新手段４４は出現頻度テーブル４１
の出現頻度格納手段ａと累積頻度テーブル４２の累積頻
度格納手段ａを用いて、累積頻度格納手段ａのみを更新
する。状態ｂで符号化するときには、各手段でｂの方を
用いて処理すればよい。

【００７０】このように、複数の状態に基づいて算術符
号化を行うときも、本発明は自然に適用が可能となり、
従来の圧縮率の向上という利点に加えて高速化が可能と
なる。

【００７１】図２では、累積頻度更新処理間隔を決定す
るパラメータＴを固定としていたが、これをデータの状
態または符号化の状況に合わせて可変とする方式も考え
られる。図７はＴを可変にするときに必要な更新間隔決
定手段と図１のブロック図とのつながりを示すブロック
図である。更新間隔決定手段は累積頻度更新手段と情報
の交換を行えれば十分である。

【００７２】データの状態に応じてＴを変更する場合に
は、図７に示すように更新間隔決定手段は累積頻度更新
手段から得られる情報に基づいてＴの変更を決定する。
更新間隔決定手段は、図１の出現頻度格納手段１に格納
されている頻度と累積頻度更新手段２から得られる頻度
との差異の情報を累積頻度更新手段４から得て、この情
報を元にＴの変更を決定する。差異が大きい場合には、
データの統計的性質の変化が激しいので、Ｔを小さくす
ることで圧縮率の向上を図ることができる。差異が小さ
い場合にはＴを大きくすることで不要な累積頻度更新を
行わずに済み、さらなる高速化を図ることができる。差
異の図り方には様々な方法があるが、計算量の小さい方
法である必要がある。例えば、累積頻度格納手段２から
得られる頻度が１であるシンボルに対応する、出現頻度
格納手段１に格納されている頻度の最大値等である。更
新間隔の変更があった場合には、累積頻度更新手段の更
新処理におけるパラメータ（図５におけるｓ，ｄなど）
も必要に応じて変更する。

【００７３】このように、本発明は累積頻度の更新間隔
を動的に変更できるという高い自由度を持つ符号化装置
である。

【００７４】以上、本発明の符号化装置について述べた
が、復号時にも符号化時と同一の累積頻度更新を行うこ
とにより正しく復号を行うことができる。累積頻度の最
大値を２の巾に設定することにより、従来１シンボルを
復号するのに必要であった３回の除算を、２回のビット
シフトと１回の除算に置き換えることができ、本発明は
復号時も高速化を図ることができる。

【００７５】

【発明の効果】本発明の効果は、算術符号化（区間縮
小）で必要な乗算をビットシフトに置き換えることによ
り高速な処理が可能となることである。区間縮小にかか
る時間は本発明によって従来方式の１／２程度に削減で
きる。

【００７６】その理由は、乗算に比べてビットシフトの
方がはるかに少ない実行量で行うことができるためであ
る。除算をビットシフトに置き換えることができるのは
累積頻度の最大値を２の巾に保つことによる。また、ブ
ロック単位で累積頻度更新処理を行うことで、累積頻度
の最大値を一定値に保ったままでも容易に累積頻度更新
処理を行うことができる。このとき、従来方式よりも一
つの累積頻度更新にかかる時間は大きくなるが、その回
数は減少するため、本発明に示した累積頻度更新方式を
用いて入力データの１シンボル当りの累積頻度更新にか
かる時間を従来方式の最良のもの（ＢＩＴ法）よりも短
縮することが可能となる。シンボルの数が２５６（１バ
イト）のとき累積頻度の更新間隔を６４シンボルにすれ
ば、入力データ１シンボル当りの累積頻度の更新要素の
数は２５６／６４＝４となる。このとき、本発明により
累積頻度更新にかかる時間はＢＩＴ法と同程度以下にな
る。また、本発明では累積頻度更新手段としては単なる
一つの配列構造で十分であり、特別なデータ構造も不要
となる利点もある。結果、図１に示した算術符号化処理
全体でみても、累積頻度の更新間隔が６４程度で本発明
を用いて２０〜２５％の高速化をみることができる。累
積頻度の更新間隔を１２８程度にすると３０％程度の高
速化が可能となる。累積頻度の更新間隔を６４程度に設
定し、適切な累積頻度更新手段を用いれば、従来方式と
比べて圧縮率の劣化はほとんどのデータに対し１ポイン
ト以内となる。累積頻度の更新間隔を１２８程度に設定
しても、圧縮率の劣化は１．５ポイント以内となること
が多い。

【図面の簡単な説明】

【図１】本発明の構成を示すブロック図である。

【図２】本発明の動作の流れを示すフローチャートであ
る。

【図３】本発明による、算術符号化における区間縮小処
理を図示したものである。

【図４】全体の処理と累積頻度更新処理との関係を示す
図である。

【図５】累積頻度更新処理の具体例の動作を示すフロー
チャートである。

【図６】二つの状態を用いて算術符号化を行うときの本
発明の構成を示すブロック図である。

【図７】累積頻度更新間隔を動的に変更するときの、更
新間隔決定手段と図１の構成との関係を示すブロック図
である。

【図８】算術符号化方式の大きな構成を示すブロック図
である。

【図９】従来の算術符号化方式の動作の流れを示すフロ
ーチャートである。

【図１０】従来の算術符号化方式における区間縮小処理
を図示したものである。

【図１１】従来方式における累積頻度更新処理の具体例
を示す。

【符号の説明】

１出現頻度格納手段２累積頻度格納手段３カウンタ４累積頻度更新手段５符号化手段４０状態判別手段４１出現頻度テーブル４２累積頻度テーブル４３カウンタテーブル４４累積頻度更新手段４５符号化手段５０符号化手段５１予測手段５２復号手段５３予測手段

Claims

【特許請求の範囲】

【請求項１】入力データを圧縮データに変換する算術符
号化装置において、入力データ中の各シンボルの出現頻度を計測し、記録す
る出現頻度格納手段と、算術符号化に必要な各シンボルの累積頻度を記録する累
積頻度格納手段と、累積頻度更新のタイミングを計るためにに、符号化され
たシンボルの数を計測するカウンタと、前記出現頻度格納手段と前記累積頻度格納手段に記録さ
れた情報に基づいて新たな累積頻度情報を生成し、前記
累積頻度格納手段の内容を更新する累積頻度更新手段
と、前記累積頻度格納手段に記録された情報を元に圧縮デー
タを生成する符号化手段とを有し、前記累積頻度格納手段に蓄積されている累積頻度の最大
値は２の整数巾であり、前記累積頻度更新手段は累積頻
度の最大値を２の整数巾に保ったまま更新処理を行うこ
とを特徴とする算術符号化装置。
【請求項２】前記累積頻度更新手段は、前記出現頻度格
納手段に記録されている頻度と前記累積頻度格納手段に
記録されている情報から得られる頻度の重みづけ和を用
いて新たな累積頻度を生成することを特徴とする請求項
１に記載の算術符号化装置。
【請求項３】前記重みづけ和における重みの分母を２の
整数巾でとることを特徴とする請求項２に記載の算術符
号化装置。
【請求項４】前記出現頻度格納手段、前記累積頻度格納
手段及び前記カウンタの組を複数装備することを特徴と
する請求項１に記載の算術符号化装置。
【請求項５】前記累積頻度更新手段は、前記出現頻度格
納手段、前記累積頻度格納手段及び前記カウンタの組に
よって、累積頻度の更新間隔、累積頻度の更新方法を変
更することを特徴とする請求項４に記載の算術符号化装
置。
【請求項６】前記カウンタの値から決定される累積頻度
更新の間隔を可変とする請求項１に記載の算術符号化装
置。