JPH04277933A - データ圧縮および復元方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は，文字コード，画像デー
タ等のデータを算術符号化するデータ圧縮方式に関する
。文字コード，画像データ等の様々な種類のデータがコ
ンピュータで扱われるようになるのにともない，取り扱
われるデータ量も増大している。そのような大量のデー
タの処理においては，記憶容量を減らしたり，遠隔地へ
の伝送を可能とするため，データ中の冗長な部分を省い
て圧縮したデータとして記憶したり，データ転送を行う
ようにすることが望まれる。

【０００２】様々な種類のデータ（文字コード，画像デ
ータ等）のデータに適用できるデータ圧縮方式として，
ユニバーサル符号による方式がある。ユニバーサル符号
化方式には，様々な方法があるが，代表的な方法として
，算術符号化方式がある。本発明は，算術符号化方式に
よる圧縮符号の最終バイトに付加する制御符号の構成を
改良することを目的とする。

【０００３】

【従来の技術】算出符号化方式は，情報源の文字の出現
頻度が分かっている場合に，最大の効率で圧縮できるも
のである。

【０００４】図４により，二値データを算術符号化する
場合の原理を説明する。出難いシンボルの出現確率をｐ
，出易いシンボルの出現確率を１−ｐとし，出難いシン
ボルが出現したときをＦａｌｓｅ　（Ｆ）出易いシンボ
ルが出現したときをＴｒｕｅ（Ｔ）とする。

【０００５】そして，出現確率ｐを次のように２の負の
巾乗で近似する。 ｐ＝２−ＳＫ　（ＳＫ：ＳＫｅｗ　　ｎｕｍｂｅｒであ
って整数）そして，入力のＴ，Ｆにより数直線上で次式
によって符号化区間の幅と符号区間の下端の値により符
号語を求める。 　　区間幅：Ａ（ｓ，Ｆ）＝Ｗ（Ｆ）＝Ａ（ｓ）×２−
ＳＫ　・・・・・（１）　　　　　　　　　　Ａ（ｓ，
Ｔ）＝Ｗ（Ｔ）＝Ａ（ｓ）−Ｗ（Ｆ）・・・・（２）　
　符号語：Ｃ（ｓ，Ｆ）＝Ｃ（ｓ）・・・・・・・・・
・・・・・（３）　　　　　　　　　　Ｃ（ｓ，Ｔ）＝
Ｗ（Ｔ）＝Ｃ（ｓ）＋Ｗ（Ｆ）・・・・（４）

【０００
６】図は区間幅の初期値を１として，入力データが，「
ＴＴＦＴＦＴＴ」の順に出現する場合を示す。 入力データの最初のシンボルに対しては，Ｔであるから
，上記式（２），（４）により Ａ（１，Ｔ）＝１−２−ＳＫ　（＝Ａ１　）Ｃ（１，Ｔ
）＝２−ＳＫ　　　　　（＝Ｃ１　）が得られる。第２
番目に入力されるシンボルに対しては，Ｔであるから，
上記式（２），（４）より，　　　　Ａ（２，Ｔ）＝Ａ
１　−Ａ１　×２−ＳＫ　＝Ａ１　×（１−２−ＳＫ　
）（＝Ａ２　）　　　　Ｃ（２，Ｔ）＝Ｃ１　＋Ａ１　
×２−ＳＫ　＝Ａ１　×（１＋２−ＳＫ　）（＝Ｃ２　
）第３番目のシンボルに対しては，Ｆであるから，上記
式（２），（３）により， Ａ（３，Ｆ）＝Ａ２　×２−ＳＫ　 Ｃ（３，Ｆ）＝Ｃ２　 以下，同様に演算を進め，求められた最後区間の下端の
値に基づいて符号が定められる。

【０００７】図５に算術符号の符号化のアルゴリズムの
フローを示す。図において，Ｃは符号レジスタ，Ｑは出
力バッファレジスタ，Ａは区間幅レジスタ，ＭＩＮは入
力データビット，ＳＫはＳｋｅｗ　Ｎｕｍｂｅｒ　（１
，２，３，４）である。ＳＫの値は，入力データと予測
値を比較し，一致した回数に応じて更新される。ｓｈ１
　は１　ビットシフト，ｓｈ１ＳＫはＳＫビットシフト
，ｓｈ１４は４ビットシフトを示す。なお，Ｑレジスタ
とＣレジスタ（５ビット）は同一レジスタ上に構成され
，Ｑレジスタの最下位ビットにつづいて，Ｃレジスタの
最上位ビットである。

【０００８】図示の番号に従って説明する。■　　Ｑ，
ＣおよびＡを初期化する。■　　入力データの１ビット
を取り込む。ＳＫをセットする（ＳＫの初期値は１）。 ■　　入力データビット（ＭＩＮ）のＴ，Ｆを判定する
。■　　Ｆであれば，Ｑレジスタ，ＣレジスタをＳＫビ
ットシフトし，Ｃレジスタに格納された符号を，Ｑレジ
スタに移す。そして，Ｃレジスタの空いた部分に０を詰
める（Ｃ（ｓ）＝Ｃ（ｓ），区間幅Ａ＝Ａ（ｓ）×２−
ＳＫ　を１に規格するため）。区間幅Ａを１に規格化す
る。■　　■において，ＭＩＮがＴのときは，Ｃレジス
タの値をＣ＋２−ＳＫ　，Ａレジスタの値をＡ−２−Ｓ
Ｋ　とする（Ｃ（Ｔ）＝Ｃ（ｓ）＋Ｗ（Ｆ），Ａ（Ｔ）
＝Ａ（ｓ）−Ｗ（Ｆ））。

【０００９】■　　２進演算の論理上，Ａが１を越える
場合があるので，Ａ＜１．０でないなら，■に進み，Ａ
＜１．０なら■に進む。■　　Ｑレジスタ，Ｃレジスタ
を１ビットシフトし，Ｃレジスタに格納した符号を，１
ビットだけＱレジスタに移し，Ｃレジスタの空いた部分
に０を詰める。Ａレジスタも１ビットシフトしてＣレジ
スタと桁合わせする。■　　すべての入力データについ
て処理したか判断し，終了していなけれは，■以降の処
理を繰り返す。■　　■において，全ての入力データビ
ットの処理を終了したら，Ｑレジスタ，Ｃレジスタを４
ビットシフトして出力符号を得る。

【００１０】図６に，算術符号の復号化のアルゴリズム
のフローを示す。図において，Ｃは符号レジスタ，Ｑは
出力バッファレジスタ，Ａは区間幅レジスタ，ＭＯＵＴ
は入力符号ビット，ＳＫはＳｋｅｗ　Ｎｕｍｂｅｒ，ｓ
ｈ１　は１ビットシフト，ｓｈ１ＳＫはＳＫビットシフ
ト，ｓｈ１４は４ビットシフトを示す。　　なお，Ｑレ
ジスタとＣレジスタを同一レジスタ上に構成され，Ｃレ
ジスタ（５ビット）の最下位ビットにつづいて，Ｑレジ
スタの最上位ビットである。

【００１１】図示の番号の順にフローの説明をする。■
　　Ｃレジスタに，Ｑレジスタを４ビットシフトして，
データを格納する。Ａレジスタの値を１．０に規格化す
る。■　　ＳＫの値を取り込む。■　　Ｃ−２−ＳＫ　
の正負を判定する。■　　■において，Ｃ−２−ＳＫ　
が負であれば，入力符号ビットＭＯＵＴとしてＦを出力
する。■　　Ｃレジスタ，ＱレジスタをＳＫビットシフ
トし，ＣレジスタにＱレジスタの符号を移す。そして，
Ｑレジスタの空いた桁に０を詰める。Ａの値を１．０に
規格化する。■　　■において，Ｃ−２−ＳＫ　が正で
あれば入力符号ビットＭＯＵＴとしてＴを出力する。■
　　ＣレジスタをＣ−２−ＳＫ　とする，Ａレジスタを
Ａ−２−ＳＫ　とする。■　　Ａ＜１．０であるか判定
する。Ａ＜１．０でなければ，■’に進む。■　　■に
おいて，Ａ＜１．０を満たしていれば，Ｃレジスタ，Ｑ
レジスタを１ビットシフトし，ＣレジスタにＱレジスタ
の符号を移す。そして，空いた桁に０を詰める。■’全
ての符号について復号化が終了したか判断し，終了して
いなければ■以降の処理を繰り返す。

【００１２】図７，図８により，ＡＮＳＩ提案方式にお
ける従来の算術符号化の装置構成を示す。図７は通常モ
ード（Ｎｏｒｍａｌ　ｍｏｄｅ　）における構成を示す
。図において，６０はモデリング変換器であって，入力
データから，二値データの出現頻度を予測し，符号化対
象の入力ビットと比較して，Ｔ，Ｆを判定するもの，６
１は算術符号化符号器，６２は８ビットの入力データ（
文字コード）を格納するものであって，ＭＳＢからＬＳ
Ｂの順で順次に格納した二値データを１ビットずつ出力
するもの，６３はレジスタ６２の出力を，出現確率の高
い値（ＭＰＳ（　ｍｏｒｅ　ｐｒｏｂａｂｌｅ　ｓｙｍ
ｂｏｌ　））と比較し，入力データビットについてＴ，
Ｆを判定するもの，６４はテーブルペア（ｔａｂｌｅ　
ｐａｉｒ）であって，入力データにおける二値データの
並びのパターンに続く二値データを予測するためのテー
ブルであって，出現確率の高い二値データ（ＭＰＳ）と
ＳＫについての組をテーブルペアとして，二値データの
パターン毎に持つものである。６５はテーブルペアアド
レス作成部であって，入力された二値データについての
並び方のパターンと同じパターンを持つテーブルペア６
４のアドレスを生成するもの，６６は実際にＭＰＳとの
照合部６３における照合結果に基づいて，ＳＫの値を更
新するＴａｂｌｅ　　ｐａｉｒ更新部，６７はテーブル
ペアアドレス作成部６５のアドレスに従って，テーブル
ペアを選択するテーブルペア選択部，６８は符号化ビッ
ト制御部であって，入力データ格納部６２の入力データ
についてＭＳＢからＬＳＢに順次取り出すように制御す
るとともに，テーブルペアアドレス作成部を制御するも
のである。

【００１３】図の構成の動作を説明する。入力データ格
納部６２に格納された文字コード等の８ビットの並列デ
ータは符号化ビット制御部６８に制御されて，ＭＳＢか
ら順次ＬＳＢの順に１ビットづつ出力する。そして，テ
ーブルペアアドレス作成部６５は，順次に取り出された
ビットの並び方のパターンと同一のパターンを取り出す
ためのテーブルペアに対するアドレスを作成する。テー
ブルペア選択部６７はテーブルペアアドレス作成部６５
の作成したアドレスに基づいて，テーブルペア６４より
テーブルペアを取り出し，ＭＰＳとの照合部６３に格納
する。ＭＰＳとの照合部６３は，入力データ格納部６２
から出力されたデータと格納されたＭＰＳを比較する。

【００１４】その結果，一致すれば，Ｔを出力し，一致
しなければＦを出力する。算術符号化符号器６１は，テ
ーブルペア選択部６７が選択したテーブルペア６４のＳ
Ｋ，およびＭＰＳとの照合部６３の照合結果に基づいて
，算術符号を求める。テーブルペア更新部６６は，Ｔの
回数をカウントし，一定値に達すると，ＳＫの値を更新
する。

【００１５】図８は，ランモード（Ｒｕｎ　ｍｏｄｅ）
における装置構成を示す。図において，７０はモデリン
グ変換器，７１は算術符号化符号器，７２はレジスタで
あって，符号化対象の１バイトデータに先行する１バイ
トデータを格納するもの，７３は８ビット照合部であっ
て，符号化対象の入力データと後続の１バイトデータを
比較し，同一の時はランモードをオンとするものである
。７４はランモード専用のテーブルペアであって，ＭＰ
Ｓの初期値として１を持ち，ＭＰＳとＳＫの組よりなる
ものである。７５はテーブルペア更新部であって，ＭＰ
Ｓとの照合部７６（後述）の出力におけるＴをカウント
し，一定値に達するとテーブルペアにおけるＳＫの値を
更新する。７６はＭＰＳとの照合器であって，入力デー
タをビット毎に，テーブルペア７４のＭＰＳと比較する
ものである。

【００１６】図の構成の動作を説明する。レジスタ７２
には，先行する１バイトデータが残されている。そこで
，８ビット照合部７３は，１バイトの入力データとレジ
スタ７２に残されている１バイトデータを比較し，一致
したときはランモードをオンにして，ランモードを設定
する。そして，ランモードにおいては，以降のデータが
ランモードに入ったときのデータと同じときは，ＭＰＳ
との照合部７６への入力データは１とする。テーブルペ
ア７４は，ランモード専用（ＭＰＳ＝１）のテーブルペ
アがあり，ＭＰＳとの照合部７６は，入力データ１とＭ
ＰＳ（＝１）を比較する。従って，ランモードが続く場
合には論理Ｔが出力される。

【００１７】図９は従来の算術符号のデータフォーマッ
トを示す。図において，９０は入力データ，９１は圧縮
データ，９２，９２’は終端符号であって，ブロック毎
の圧縮データの終端に付加するデータである。９３，９
３’は入力データの１ブロック（例えば，５１２バイト
）の圧縮符号の終了を示す全ビット１の終了符号である
。９４は制御符号であって，符号化した圧縮データにお
ける制御符号を表す（先頭は必ず１とされる），９４’
は最終ブロック制御信号を示す。９５，９５’は圧縮デ
ータにおける全ビット数がバイト単位で割り切れないよ
うな場合に，バイト単位の整数倍になるように付加した
ビット数を表すもので，例えば，３ビット付加したので
あれば「０１１」とする。従来のデータフォーマットは
，図示のように，例えば，５１２バイト単位の入力デー
タ９０について，算術符号化し，ブロック毎に圧縮デー
タ９１を得る。

【００１８】そして，１ブロックの入力データの符号化
が終了すると，符号化の終了を示す終了信号「１１１１
　　１１１１」を圧縮データに付加する。さらに，付加
したビット数を示す制御符号９４，９４’を付加する。 算術符号では，符号「１１１１１１１１」が生成された
場合には，桁上がりを抑止するため，続く符号として「
００００」を挿入するように規定されているので，終了
信号と全ビット１の符号を識別するために制御符号の先
頭は必ず１とされる。

【００１９】圧縮データは，常にバイト単位で割り切れ
るビット数で構成されるとは限らないので，圧縮データ
をバイト単位に分けた場合，最後のバイトにおける１バ
イトに満たない部分が１バイトになるようにビットを付
加して，バイトの整数倍の長さのデータとなるようにす
る。そして，制御符号における下位３ビットの部分に付
加したビット数示す符号付加する。例えば，３ビット付
加したのであれば，付加ビット数９５は「０１１」とす
る。

【００２０】

【発明が解決しようとする課題】従来の算術符号化方式
におけるデータフォーマットからは，符号語全体のビッ
ト数は分かるが，符号語から元データとして，何バイト
が復元されるかは分からない欠点があった。本発明は，
算術符号においては符号化したデータ数が分かれば，符
号語から元データを正確に復元できることに着目し，デ
ータフォーマットの終端符号の部分に元データ数を付加
するようにした。そして，簡単な構成で元データ数が分
かるようなデータフォーマットを作成する算術符号化方
式を提供することを目的とする。

【００２１】

【課題を解決するための手段】図１に本発明の基本構成
を示す。図において，１は入力データであって，ｍバイ
ト（ｍは整数）よりなるもの，２は圧縮データであって
，ｍバイトの入力データ１を算術符号化したもの，３は
終端符号であって，終了符号と制御信号よりなるもので
ある。４は全ビット１の終了符号であって圧縮符号の終
了を示すもの，５は制御符号であって，先頭１であるも
ので，例えば，第２ビット以降の７ビットの部分に，元
データのデータ数（ｍバイト）もしくは，元データ数を
整数αで割った余り等により元データ数がわかるような
数値を表したものである。

【００２２】データ数の表し方としては，直接実際の元
データ数で表すか，データ数を任意の数αで割った余り
で表すようにする。例えば，データ数を表すのに使用で
きるビット数は最大７ビット（最大１２８）までである
ので，α＝１２８として元データ数を１２８で割った余
りを７ビットで表す（ｍｏｄ（ｍ，１２８））ようにす
る（この場合，元データ数が１２８以下の場合には，１
２８で割った余りは，そのまま，元データ数を表す）。

【００２３】

【作用】図１の基本構成の作用について説明する。符号
化においては，予め定めた元データ数ｍバイトに対して
，データ数ｍもしくはｍをαで割った余りを，圧縮デー
タの終了符号の次に付加する。復号側では，復元データ
数をカウントしながら，復元してゆく，一方，復元側に
おいて，終端符号を検出したら，そこに記されているデ
ータ数ｍもしくは，余りαを検出し，カンウト値もしく
はカウント値をαで割った値と比較する。そして，復元
したデータ数と終端符号で検出した値が一致した所で復
号を終了する。実際には，終了符号を検出した時点にお
いて，検出値と復元されたデータ数とで，大きな違いは
ないので，両者の下位数ビット（４ビット程度）を比較
するだけでよい。また，αで割った場合にも，αが２の
指数乗であれば，制御符号における余りの数値と復元デ
ータ数を下位数ビットで比較することにより正確に符号
化を終了させることができる。

【００２４】

【実施例】図２に，本発明の符号化における装置構成実
施例を示す。図において，２０はモデリング変換器，２
１は算術符号化符号器，２２は入力データの終了検出器
，２３はマルチプレクサであって，算術符号化符号器２
１の出力と，カウンタ２４（後述）の出力と，終了符号
発生部２５（後述）の出力を選択するもの，２４は入力
データ数をカウントするカウンタ，２５は全ビット１の
終了符号を発生する終了符号発生器，２６は８ビットの
文字コード等の入力データ，２７は圧縮データ（符号）
である。

【００２５】図の構成の動作を説明する。入力データは
，モデリング変換器２０に入力され，モデリング変換器
からＴ／Ｆの出力に基づいて，算術符号化符号器２１は
算術符号を作成する。一方，終了検出器２２は，予め定
められた一定のバイト数の入力データの処理が終了した
ことを検出すると，算術符号化符号器２１およびマルチ
プレクサ２３に終了検出信号を与える。

【００２６】カウンタ２４は，例えば８ビットのカウン
タで構成し，入力データの１データ毎にパルスを計数す
る。ところで，復号においては，元データ数と復元デー
タ数を全ビットで比較して復号化の終了時点を判定する
必要はなく，下位７ビットの比較で正確に終了を判定で
きるので，符号化においても，カウンタ２４のカウント
値のうち下位７ビットを出力する。終了検出器２２の終
了検出に基づいて，マルチプレクサ２３は，終了符号発
生器２５の全ビット１の出力「ＦＦ」を選択する。次い
で，カウンタ２４の出力により制御符号を作成し，出力
する。

【００２７】図３に復号側における装置構成実施例を示
す。図において，３０は算術符号化復号器，３１はモデ
リング逆変換器であって，算術符号化復号器の出力に基
づいて，復元データを作成するもの，３２は終端検出器
であって，圧縮データにおける全ビット１の終了符号を
検出するもの，３３はレジスタであって，終端符号にお
ける制御符号のデータ数を表すデータを格納するもの，
３４は復元データ数をカウントするカウンタ，３５はレ
ジスタ３３に格納された値とカウンタ３４のカウント値
を比較するものである。３７は入力される圧縮データ（
符号），３８は復元データである。

【００２８】図の構成の動作を説明する。圧縮データ（
符号）３７は，算術符号化復号器３０に入力され復号さ
れる。復号された出力はモデリング逆変換器３１に入力
され，復元データ３８を得る。一方，カウンタ３４は復
元したデータ数をカウントする。そして，終端検出器３
２は，圧縮符号において，全ビット１の終了符号を検出
すると，それに続く制御符号のデータ数を示す下位ビッ
トの値をレジスタ３３にセットする。比較器３５はカウ
ンタ３４のカウント値とレジスタにセットされた値を比
較し，一致すると，算術符号化復号器３０およびモデリ
ング逆変換器３１に終了指令を示す信号を出力する。 そして，復元動作を終了する。

【００２９】

【発明の効果】本発明によれば，算術符号化において，
簡単な構成で圧縮した元データ数を圧縮データに付加す
ることができ，復元においても，簡単な構成で復元の終
了処理を行うことが可能になる。

【図面の簡単な説明】

【図１】本発明の基本構成を示す図である。

【図２】本発明の符号化における装置構成を示す図であ
る。

【図３】本発明の復号側における装置構成を示す図であ
る。

【図４】算術符号の説明図である。

【図５】算術符号の符号化のフローを示す図である。

【図６】算術符号の復号化のフローを示す図である。

【図７】従来の算術符号化（Ｎｏｒｍａｌ　　ｍｏｄｅ
）の装置構成を示す図である。

【図８】従来の算術符号化（Ｒｕｎ　　ｍｏｄｅ）の装
置構成を示す図である。

【図９】従来の算術符号のデータフォーマットを示す図
である。

【符号の説明】

１　　入力データ ２　　圧縮データ ３　　終端符号 ４　　終了符号 ５　　制御符号 ６　　元データ数

Claims (3)

【特許請求の範囲】
1. 【請求項１】　　複数バイトのデータを，算術符号化す
   るデータ圧縮方式において，入力される元データ（１）
   　を算術符号化する算術符号化手段と，元データ（１）
   　のバイト数を計数する手段と，圧縮データの終端を示
   す終端符号（３）　を付加する手段とを備え，圧縮デー
   タに付加される終端符号（３）　は，圧縮データ（２）
   　の終了を示す符号と元データ（１）　のバイト数もし
   くは元データのバイト数を整数で割った余りの数を含む
   制御符号により構成することを特徴とするデータ圧縮方
   式。
2. 【請求項２】　　請求項１において，制御符号（５）　
   に含める元データ数を示す数値は，元データ数の下位数
   ビットの数値，もしくは元データ数を整数で割った余り
   の下位数ビットで表される数値であることを特徴とする
   データ圧縮方式。
3. 【請求項３】　　算術符号化された圧縮データを入力し
   て復号する算術符号復号部と，復号したデータ数をカウ
   ントするカウンタと，圧縮データの終端符号における元
   データ数を検出する終端符号検出部と，復元データ数と
   元データ数を比較する比較部を備え，復元データ数もし
   くは復元データ数の下位数ビットの数値と，終端符号検
   出部の検出した数値が一致するまで，圧縮データを復号
   することを特徴とする請求項１に記載の圧縮データの復
   元方式。