JPS63314918A - 算術符号化における桁上がり伝搬防止方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （発明の技術分野） 本発明は、画像の符号化やデータ伝送などのデータ圧縮
符号として用いられる算術符号化に係わり、特に圧縮デ
ータのデータ伝送及びメモリ領域への移動をリアルタイ
ムで可能とする算術符号化における桁上がり伝搬防止方
式に関する。

（従来技術とその問題点） 算術符号は、エリアスによる符号化法がリッサネン（Ｒ
ｉｓｓａｎｅｎ）により一般化されたもので、〔０゜１
〕区間をデータシンボルの生起確率に応じて順次分割し
ていき、１つのシンボル列にある部分区間を対応させる
方法である。

従来、高い情報源を圧縮して伝送する符号化方式の代表
例として、出現確率の高い（又は低い）ものに対して短
い（又は長い）ビットを割り当てるハフマン符号がある
。第１図はハフマン符号と算術符号とを用いた場合にお
ける量子化ステップサイズ対符号化効率の特性を示した
ものである。

同図はフィールド内前置予測、線形量子化器を用い、こ
れら符号化データより得られる量子化代表値に対して算
術符号化及びハフマン符号化を行ったものである。同図
から明らかなように、算術符号は量子化ステップサイズ
に関係なくほぼ一定の高符号化率を有している。従って
、近年は算術符号を用いてデータを圧縮する技術が注目
を浴びている。

算術符号として、３値情報源の場合を例に取り説明を行
う。算術符号において、符号化系列は大きさが“′０′
”と“１′の間の２進小数、即ち、最左端に小数点が置
かれた２進数と見なされる。符号化は、以下に示す繰り
返し演算により行われる。

アルファベラ）Ｓ＝　（０，１，２）の各シンボルＫ　
（＝０．１．２）がストリングＳの次のシンボルとなり
、ＳＫを生成するとき、そのＫに対し、オージエント被
加算数と言われるＡ　（ＳＫ）項を、シンボル系列であ
るストリングＳの符号Ｃ（Ｓ）に加えることにより、符
号化が行われる。ここでオージエン）Ａ（ＳＫ）は、（
２）弐のように、シンボルの出現確率に応じてＡ　（Ｓ
）が分割されたものである。符号化は、例えばシンボル
に＝０．１．２なる場合（３）式のように行われる。こ
こでＡ　（Ｓ）とＣ（Ｋ）の初期値をＡ　（ＮＵＬＬ）
　＝　１　　　　　　　−−−−−−−−−−−−−−
−−　（１）Ｃ（ＮＵＬＬ）　＝　０ とするとき、符号化は Ａ（Ｓに）　＝Ａ（Ｓ）　＊　Ｐ（Ｋ）　　　　　Ｋ≠
Ｏ−−−−−−−１２）Ｃ（ＳＫ）　＝Ｃ（Ｓ）　　　
　　　　　Ｋ　＝　０により行われる。

符号化の実現のために、以下の手法が必要になる。

（１）無限精度の乗算を避けるため有効桁数を一定桁数
に制限し、シンボルの出現確率Ｐを近似的に計算する。

そしてこのＰに対し２のべき乗近似を行い、符号化テー
ブル（ＳＫＥＷ）を作成し、乗算をシフト演算に置き換
える。

（２）　Ａ（Ｓ）の領域分割が進むに従って発生する上
位の連続する“０゛ビツトをシフティング法になる左シ
フトにより取り除く。

また、復号化は次のようにして行われる。いま、シンボ
ル系列であるストリングＳまですでに復号されているも
のとする。系列ＳＫのシンボルにはＣ（ＳＫ）　−Ｃ（
Ｓ）　＜Ａ（Ｓｏ）　　　　　　　　Ｋ　＝　Ｏ（４）
Ｃ（ＳＫ）−Ｃ（Ｓ）＜Ａ（Ｓｏ）＋Ａ（ＳＬ）　　Ｋ
＝１Ｃ（ＳＫ）　−Ｃ（Ｓ）　＜Ａ（Ｓｏ）　＋Ａ（Ｓ
ｔ）　＋Ａ（Ｓ２）　　Ｋ　＝　２なる関係で復号され
る。

次に必要なことは、実用上の観点からＡ（Ｓ’の値を制
限することである。このため、（１）式の加算は有限長
のレジスタで行われればならず、例えば高々Ｗ桁の有意
な浮動小数２進デジツトをもつものとなる。ここで、最
初に符号化されたものが、最初に復号されるＦＩＦＯ（
Ｆｉｒｓｔ　ｉｎ　Ｆｉｒｓｔ　ｏｕｔ）型の場合には
、Ａ　（Ｓ）はストリングの右端に加えられるため、多
くの桁を飛び越す桁上がりは正常に復号を行う上で好ま
しくない。算術符号は、符号化された系列の各部が符号
語に分けられるハフマン符号などと異なり、情報源系列
全体を１つの符号語に符号化してしまうため、１変復号
エラーが生ずると、それ以後の復号は完全に不可能とな
る。このため、Ｃ（Ｓ）の−足指以上の桁上がりを完全
に防止することが必要不可欠になる。

第２図に、従来の算術符号化方式を用いた符号　　。

化部のブロックダイヤグラムを示す。符号Ｃ（Ｓ）を、
直接算術演算する最下位Ｗビットの算術演算レジスタ（
以下「Ｗレジスタ」と称する）、それに続くｖビットの
桁上がり監視レジスタ（以下「Ｖレジスタ」と称する）
、Ｗ＋Ｖビットより上位のバッファメモリとなる伝送用
バンファレジスタ（以下「Ｍレジスタ」と称する）の３
つの部分に分けることができる。符号Ｃ（Ｓ）とＡ　（
Ｓ）は、図の様な位置関係になる。演算は、長さＷビッ
トのＷレジスタ上で行い、それ以下の桁は切り捨てるこ
ととする。

また、Ａ　（Ｓ）の分割が進むに従って、上位桁に“０
′°が連続するようになるが、左シフトすることにより
この部分を演算の対象から外す。これを、シフト処理と
呼ぶ。図中、１１はオージェントの累積和を蓄える累積
和蓄積レジスタ（以下、「Ａレジスタ」と称す）　、１
２．１３．１４は符号Ｃのためのレジスタであり、１２
はＡレジスタ１１と加算処理を行うためのＷレジスタ、
１３は連続°°１°′ビットを監視するための桁上がり
監視用レジスタである■レジスタ、１４は伝送用バッフ
ァメモリとなるＭレジスタを示す。又、１５は入力シン
ボルを蓄えるＡＧレジスタで、１６は入力シンボルに対
し符号化テーブル（ＳＫＥＷ）の値のだけビットシフト
されたオージェントを蓄えるＳＦレジスタ、１７はＳＦ
レジスタ１６で作成されたオージェントよりオージエン
トの累積和を作り蓄えられる３Ｍレジスタである。

第２図で、１つの入力シンボルを符号化する為の手順は
、以下のようになる。

（１）人力シンボルごとに、逐次ＡＧレジスタ１５、Ａ
Ｆレジスタ１６及び３Ｍレジスタ１７よりオージェント
の累積和が作られる。

（２）Ａレジスタ１１のオージエントの累積和にＷレジ
スタ１２が加算される。このとき、もし桁上がりがあれ
ば後述する（４）項の処理を行う。

（３）オージエントの正規化を行うため、ＡＧレジスタ
１５のオージェント及びＷレジスタ１２．　　Ｖレジス
タ１３９Ｍレジスタ１４の符号の左へのシフト処理を行
う。

（４）■レジスタ１３のレジスタ内において、連続する
“ビ′ランの桁上がり監視を行い、■レジスタ１３内に
おいて前回にビット・スタッフインク処理により挿入し
た制御信号の位置と異なり、かつ、連続“１”ランが検
出できれば、新たに制御信号を連続“ｌ”ランの後に制
御信号を挿入する。

（５）伝送用バッファであるＭレジスタ１４より、伝送
路又はメモリに符号化データが送られる。

ここで、桁上がりの伝搬を調べるため、■レジスタ１３
に入って（るビットは、 （Ａ）　　レジスタ１１とＷレジスタ１２の内容を加算
することによる桁上がりビット、 （Ｂ）　Ｗレジスタ１２における内容を左シフト処理す
ることによるビット の２種類に分けられる。桁上がり伝搬は、上記（Ａ）と
（Ｂ）の２種類ビットに対し、桁上がり監視レジスタで
ある■レジスタ１３内で必ず抑えられなければならない
。

はじめに、従来の桁上がり防止方式について説明する。

これまで知られている技術として、桁上がり防止方式の
ために、制御信号を符号化系列に挿入するビット・スタ
ッフインク処理方法が知られている。以下に、ビット・
スタッフインクの２つの方法を示す。

（１）■レジスタ１３の全ビットが“１”ビットとなる
ときに限り、レジスタ１３内のビットをシフトアップし
最下位ビット（ＬＳＢ）に制御信号として“０゛°ビツ
トを挿入する方法。

（２）上記（１）項の操作に加え、桁上がりにより■レ
ジスタ１３のＭレジスタ１４にまたがって監視レジスタ
製分の連続“１゛ランが発生した場合に関しても、連続
“１°゛ランの最下位に制御信号として“°０°′ビッ
トを挿入する方法。

しかし、この従来の方法では、前述した桁上がりビット
としてシフト処理されたビットの双方に対して■レジス
タ１３内でかならずしも押さえられるとは限らない。上
述の処理例を方法（１）の場合は表１に、方法（２）の
場合は表に示す。表１及び表２の条件は、Ｖ＝Ｗ＝４ビ
ット、シンボルが、Ｋ＝０．１．２の３値情報源とする
。

表　　　　１ 表　　　　２ 表１は上述（Ａ）なる項の桁上がりにより、■レジスタ
１３とＭレジスタ１４にまたがって監視レジスタ製分の
連続“１゛′ランが発生するとき、制御信号が挿入され
ない例を示したものである。このとき受信側の復号部で
は、ビット・スタ・ンフイング処理により挿入された制
御信号を考慮して処理を行うため、復号エラーが生ずる
。表２を説明する。

復号エラーに陥るときの、復号部における処理手順を、
以下のステップにより示す。

（Ａ）復号部のバッファメモリより読み込まれたビット
が、送信側の符号化部の監視レジスタ（■レジスタ１３
）製分連続して°“１゛ランとなる。

（Ｂ）ビット・スタッフインクにより、制御信号が挿入
されたと検知し、バッファメモリから１ビツトの２進符
号が読み込まれ、復号部の演算レジスタ（以後ｒＷＦレ
ジスタｊと称す）に加算される。

（Ｃ）上記（Ｂ）で読み込んだビットが゛１パならば、
ビットスタッフィングの処理が連続して行われたと判断
し、さらにバッファメモリから１ビツトが読み込まれＷ
Ｆレジスタに加算される。

復号側では、送信側の処理手順に関わらず、常にビット
・スタッフインク処理が行われていると判断する。とこ
ろが送信側では、ビット・スタッフインク処理により挿
入される制御信号が連続する過程において、１回目と２
回目のビット・スタッフインク処理の間にシフト処理が
生ずる場合がある。このとき、受信側でシフト処理が検
出できず、復号エラーが発生することになる。復号部に
おいて、シフト処理がなければ連続ビットスタッフがあ
ったものとして制御信号を取り除く処理のところを、シ
フト処理があるために、桁上がりで変化したビットを読
み込むという復号エラーを発生してしまう。符号部と復
号部において、符号がどの様な処理（シフト処理、ビッ
ト・スタッフインク処理）によって生成されたのかが一
致していなければ、正常な復号は不可能となる。

これらの問題に対し、前述した２種類のビット・スタッ
フインク処理に加え、単純に■レジスタ１３長を長＜シ
゛１′′ランの発生確率を小さくするという手法により
、復号エラーが回避する手法がとられてきた。しかし、
算術符号による符号化データを、リアルタイムで伝送あ
るいはメモリ領域への移動を行う際には、この復号エラ
ー状態が増加するのを回避できず、復号エラーに陥ると
いう問題点があった。

（発明の目的と特徴） 本発明は、上述した従来技術の問題点を解決するために
なされたもので、算術符号の符号化データのリアルタイ
ム伝送やメモリ領域への移動を、復号エラーなく実現さ
せることが可能な算術符号化における桁上がり伝搬防止
方法を提供することを目的とする。

本発明の特徴は、符号化桁上がりレジスタにおいて、桁
上がりが連続して発生した場合、復号エラーを防止する
ための制御信号に加え、挿入制御符号のアドレス情報を
付加して符号化系列を作成すると共にアドレス制御信号
挿入による符号効率劣化を防ぐため、桁上がり緩衝用レ
ジスタを設けた点にある。

（発明の構成と作用） 以下図面を用いて本発明の詳細な説明する。

なお、以下の説明では従来構成と同一構成個所について
は同一番号を付し説明の重複を省く。

第３図は本発明による一実施例であり、符号部の構成図
である。第３図で従来構成と異なる点は、Ｗレジスタ１
２と■レジスタ１３との間に、桁上がりの回数を減らす
ための桁上がり緩衝用レジスタ（以下、「Ｐレジスタ」
と称す）を設けると共に、Ｍレジスタ１４と■レジスタ
１３とを監視して複数のビット・スタッフインク処理が
連続して行われた場合にも付加される制御信号の区別を
行うことができるよう°にアドレス制御信号を発生する
アドレス制御信号挿入用レジスタ（以下「Ｑレジスタ」
と称す）１９をビット・スタッフインク処理部２０とし
て設けた点にある。例えば、Ｐビットから成るＰレジス
タを設けた場合、桁上がりは“１”ビットがＰ個連続す
る場合なので、桁上がり回数は確率的に２−’に減少さ
せることができる。

以下に処理手順について説明する。ビット・スタッフイ
ンク処理部のフローチャートを第４図（ａ）に、又（ａ
）におけるビット・スタッフインク処理の実行部を（ｂ
）に示す。第３図を用いて本発明によるアルゴリズムの
説明をする。

（１）ビット・スタッフインク処理部では、連続する“
１゛がＶビットだけ桁上がり監視レジスタ（■レジスタ
１３）と伝送用バッファ（Ｍレジスタ１４）にまたがっ
て存在するか否かの判定を行う。もし“ｌ”がｖビット
連続する時はビット・スタッフインク処理部２０で同図
（ロ）による処理が行われ、逆にＶビット連続しない時
は終了の工程（後述する（４）項）へ進む。但し、■レ
ジスタ１３にＳビット、Ｍレジスタ１４に（Ｖ−Ｓ）、
併せて合計ｖビットとする。

（２）このステップが、本発明によるアルゴリズムの特
徴となり、同図（ロ）の工程を行う。

（Ａ）　　Ｖレジスタ１３よりＭレジスタ１４へ１ビツ
ト伝送する。

（Ｂ）（＾）項での伝送ビットは、ビット・スタッフイ
ンク処理により発生したもので、かつ、“１”であれば
後述する（３）項の処理を行う。

（Ｃ）　ｌｏｇ、ｖビットのアドレス制御信号（Ｑレジ
スタ１９）をＭレジスタ１４のＬＳＨに挿入する。ここ
でのアドレス制御信号とは、桁上がりにより“１”に変
化したビットと（Ａ）で挿入した“Ｏ”ビットとのビッ
ト単位での距離のことである。

（３）■レジスタ１３の（Ｓ−１）番目までを左ヘシフ
トし、■レジスタ１３のＳ番目のビットに“Ｏ″を挿入
する。

（４）終了。

第５図は、本発明による復号部（受信側）のブロック図
である。図中、３１は伝送路又はメモリから入ってくる
バッファメモリであるＳレジスタ、３２は算術演算レジ
スタであるレジスタ、３３は累積和を蓄える為のＡレジ
スタ、３７．３８．３９はオージエントの累積和を作る
ためのＡＣレジスタ、ＳＦレジスタ、ＳＦレジスタであ
る。又、３４はＳレジスタ３１よりＷレジスタ３２へ読
み出すときに、連続“１”ランをＶビットまでカウント
するカウンタ（以下、ｒ検出カウンタ１と称す）、３５
はＳレジスタ３１の空となった位置を知るためのカウン
タ、３６は連続ビット・スタッフインク処理が発生して
いるときＳレジスタ３１よりｌｏｇ２Ｖビットを読み込
むためのアドレス制御信号カンウタであり、本発明の特
徴であるカウンタ３４．３５及び３６で制御信号処理部
４０を構成している。

第６図は本発明によると、復号部における制御信号処理
部４０の処理手順を示す。

（Ｉ）検出カウンタ３４はＳレジスタ３１から読み込ん
だビットが、符号部の■レジスタ１３長分であるＶビッ
ト連続して“１”ランが続いているか否を判定し、連続
していれば次の工程（ｎ）に進み、逆に連続していない
時はアドレス制御信号カウンタ３６が“０”の状態であ
るかの判定を行う。

カウンタ３６の状態が“０”でないならば次の工程（Ｉ
Ｉ）へ進み、′０”ならば処理部４０の工程を終了する
。

（ｎ）ビット・スタッフインク処理が行われたとして、
Ｓレジスタ３１よりもう１ビット読み込まれ、Ｗレジス
タ３２に伝送される。

（ＩＩ）アドレス制御信号カウンタ３６をデクリメント
する。

（ＩＶ） （Ａ）上述の（ＩＩ）項で読み込まれたビットが“０゛
ならば、後述する（Ｖ）項の処理を行い、°“１°゛な
らば、連続したビット・スタッフインク検出カウンタ３
４をインクリメントする。

（Ｂ）検出カウンタ３４がＶビットと等しいかまたは小
さいとき後述（Ｖ）項の処理を行い、逆に大きい時は次
の（Ｃ）項の処理を行う。

（Ｃ）　　Ｓレジスタ３１よりｌｏｇ２ｖビットだけ、
アドレス制御カウンタ３６へ読み込まれる。

（Ｖ）アドレス制御カウンタ３６が“０゛となったとき
前述の（ｎ）項の処理に戻り、そうでなければ処理部４
０の処理を終了する。

（Ｖｌ）終了。

表　　　　　　３ 表３に、本発明により作成された算術符号化の例を示す
。アドレス制御情報とは、桁上がりにより２度目にビッ
ト・スタッフインク処理が発生する時、桁上がりによっ
て１゛′に変化したビットと、ビット・スタッフインク
により挿入したビット“０″゛に対して挿入するもので
ある。このとき、表３の例では２つのビットの距離が３
であるため、１ｏｇ２２２＝　２ビツトで距離３を表し
、Ｗレジスタ３２に書き込む際に、連続“１”ランのあ
とに“１１”を挿入する。

上述のように、本発明の符号化部ではＷレジスタ１２と
■レジスタ１３との間に桁上がりの回数を低減させるた
めの桁上がり緩衝用レジスタ（Ｐレジスタ）　１８を設
けると共に、桁上がりとシフトとが同時に発生した場合
の如く制御信号が複数連続した時に制御信号を判別する
ためのアドレス制御信号を付加することより、桁上がり
時に生じる復号エラーを防止するようにしたものである
。

第７図は本発明の算術符号化と従来の算術符号化との符
号化効率の比較図である。図中、■の特性は従来の算術
符号化で■レジスタ１３だけでビット・スタッフインク
処理を行った場合、■の特性は従来の算術符号化でＭレ
ジスタ１４と■レジスタ１３とによりビット・スタッフ
インク処理を行った場合、■の特性は本発明による算術
符号化で制御信号にアドレス制御信号（２ビツト）を付
加した場合、■の特性は本発明による算術符号化でＰレ
ジスタ１８とアドレス制御信号とを用いた場合をそれぞ
れ示している。

同図から明らかなように、本発明の特徴のひとつである
アドレス制御信号（２ピント）を単に付加した場合（■
の特性）には伝送すべき情報が増えるために符号化効率
が低下するが、さらに桁上がりの回数を低減させるＰレ
ジスタ１８と組み合われること（■の特性）により、結
果的に従来の算術符号化よりも符号化効率が向上する。

第８図は本発明による算術符号化と従来の算術符号化に
よる量子化ステップサイズと復号エラー発生確率との比
較図であり、本発明の算術符号化では復号エラー発生確
率をほぼ零にすることができる。

このように、本発明は連続符号である算術符号化の桁上
がりによって生じる復号エラー防止をすると共に符号化
効率を改善することができる。

（発明の効果） 以上、詳細に説明したように本発明によれば、算術符号
をＦＩＦＯ型で行う際、桁上がり防止のために、数ビッ
ト長から成るＰレジスタ１８を設けると共に制御信号と
そのアドレス情報を符号化系列に挿入することによって
復号エラーを防止するため、復号化不能状態を完全に回
避することができ、かつ符号化効率も向上させることが
できる。従って、量子化サイズステップに関係な（高符
号化率を有する算術符号化の利点を用いて画像情報や音
声情報等のデータ圧縮技術に適用することが出来、その
効果は大である。

【図面の簡単な説明】

第１図は従来の算術符号化とハフマン符号化との符号化
効率−量子化ステップサイズ特性、第２図は従来の算術
符号化部のブロック図、第３図は本発明による算術符号
化部のブロック図、第４図は本発明によるビットスタッ
フィング処理の流れ図、第５図は本発明による算術符号
を用いた復号部のブロック図、第６図は本発明による制
御信号処理部の流れ図、第７図は本発明による算術符号
化と従来の算術符号化との符号化率の比較図、第８図は
本発明による算術符号化と従来の算術符号化との復号エ
ラー発生確率の比較図である。 １１、３３・・・Ａレジスタ、１２．３２・・・Ｗレジ
スタ、１３・・・■レジスタ、１４・・・Ｍレジスタ、
１５．３７・・・へＧレジスタ、１６．３８・・・ＳＦ
レジスタ、１７．３９・・・３Ｍレジスタ、１８・・・
Ｐレジスタ、１９・・・Ｑレジスタ、２０・・・ビット
・スタッフインク処理部、３１・・・Ｓレジスタ、３４
・・・連続１ビツト検出カウンタ、３５・・・バッファ
制御用カウンタ、３６・・・アドレス制御信号カウンタ
。 特許出願人　　国際電信電話株式会社 ′代理人　弁理士火爆　学 第１図 茅２図 第６図 第７図 ミ≠　　　１ 十 ステ７７＋゛す′イス 第８図 ステ、７８サイス゛

Claims (1)

【特許請求の範囲】
1. オージェントの累積和を蓄積する累積和蓄積レジスタと
   、該蓄積レジスタと加算処理を行う算術演算レジスタと
   、桁上がりを監視する監視用レジスタと符号化されたデ
   ータを格納する伝送用バッファレジスタとを有し、ある
   一定桁内に該桁上がりの伝搬を押さえるためにビット・
   スタッフインク処理を施して制御信号を挿入する算術符
   号化において、該算術演算レジスタと該桁上がり監視用
   レジスタとの間に前記桁上がり回数を低減させるための
   桁上がり緩衝用レジスタを設けると共に、前記桁上がり
   が連続して発生した時に該制御信号を判別するためのア
   ドレス情報を付加するように構成したことを特徴とする
   算術符号化における桁上がり伝搬防止方式。