JPH03247123A - 符号化装置及び符号化方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は画像情報などの符号化方式に関するものであ
る。

［従来の技術］ マルコフ情報源の符号化についてはシンボル系列を数直
線上で０．０から１．０までの間に写像しその座標を例
えば２進表示したものを符号語として符号化する数直線
表示符号化方式が知られている。

第４図はその概念図であり、簡単のため２値情報源とし
、シンボル“１”の出現確率をｒｌ　“０”の出現確率
を１−ｒとした無記憶情報源を示している。無記憶情報
源の出力系列長を３とすると、右端のＣ（０００）＝Ｃ
（１１１）のそれぞれの座標を２進表示し、区別のつく
桁までで打ち切ってそれぞれの符号語とすれば受信側で
は送信側と同様の過程を経ることにより復号が可能であ
る。

このような系列では第１時点でのシンボル系列の数直線
上へのマツピング範囲のＡ８、その範囲の最小の座標Ｃ
１は 出力シンボルａ１が０のとき Ａ、＝（１−ｒ）Ａ Ｃ：　＝Ｃ＋ｒＡ 出力シンボルａｌが１のとき Ａ　　＝ｒＡ −Ｃ となる。

さて、Ａｎ　ｏｖｅｒｖｉｅｗ　ｏｆ　ｔｈｅ　ｂａｓ
ｉｃ　ｐｒｉｎｃｉｐｌｅｓｏｆ　ｔｈｅ　Ｑ−ｃｏｒ
ｄｅｒ−Ａｄａｐｔｉｖｅ　ｂｉｎａｒｙ　ａｒｉｔｈ
ｍｅｔｉｃｃｏｒｄｅｒ（ＩＢｉｌ　Ｊｏｕｒｎａｌ　
ｏｆ　Ｒｅ５ｅａｒｃｈ　＆ＤｅｖｅｌｏｐｍｅｎｔＶ
ｏ１．３２　Ｎｏ、６　Ｎｏｖ、ｆ９８ｇ）に記載され
ているように掛は算等の演算回数を減らすためにはｒＡ
ｌ−、＋を必ずしも演算せず、複数の固定値をテーブル
に用意しその中からマルコフ状態に対応しである値を選
択する方法が採られている。

したがって、シンボルが順次繰り返されると範囲Ａ１．
は次第に小さくなっていくので演算の精度を保つため正
規化（Ａ、、を２のべき乗倍すること）が必要であり実
際の符号語では上記固定値は常に同じものとし、演算時
に２のべき乗置の１すなわち２進数のシフトを行うこと
で処理される。

ここで、ｒＡｌ−１をＳとおくと、前述した式は、それ
ぞれ次のようになる。

ａ、が０のとき Ａ、＝Ａ＝、−３ Ｃ＝Ｃ、＋Ｓ ａｌが１のとき Ａ　　＝Ｓ Ｃ，＝Ｃ となる。

ここで、前シンボルの範囲Ａ１−１はシンボルが増える
にしたがって、逐次小さくなっていくのでＳも逐次小さ
くしていく必要がある。Ｓを小さくすることは具体的に
はシフト動作で２のべき乗置の１とすることで実現され
る。あるいは、逆に数直線上でＡ　＋−＋を２のべき乗
倍し一定値のＳを用いると考えることができる。これを
正規化と呼ぶ。

なお、以下ではシンボルａ、が０の場合をＭＰＳ（優勢
シンボル：より出現確率の高いシンボル）１の場合をＬ
ＰＳ　（劣勢シンボル二より出現確率の低いシンボル）
と呼ぶ。すなわち、事前に予測変換処理が行われており
出現確率の高いと想定されるＭＰＳか低いと想定される
ＬＰＳかで表現されているものとする。

また、上述したシンボルａ１が“０“のときの範囲Ａ：
　＝　ｒＡｌ　ｌ　”Ｓは劣勢シンボルの範囲といえる
。

また、第５図は従来の符号化装置を示すブロック図であ
り、図において、（１）は前シンボルに割り当てられた
範囲の値を一時記憶するレジスタ、（２）は減算器、（
３）は範囲の切替器、（４）は座標の切替器、（５）は
正規化処理によるシフト量を決定するシフト器、（７）
は符号化出力を演算する演算部である。

つぎに、動作を図に基づいて説明する。

図示していない予測見積部でマルコフ情報源の状態から
複数の値を持つテーブルより選択されたＳ（劣勢シンボ
ル範囲）が入力されると減算器（２）でレジスタ（１）
に記憶されている前シンボルの範囲Ａ１−１との差Ａ、
、−３を求め出力する。

優勢シンボルに割当てる範囲Ａ、、−３と優勢シンボル
に割当てる範囲Ｓが切替器（３）に人力され、シンボル
が優勢シンボルか劣勢シンボルかにより切替えられる。

すなわち、シンボルが優勢シンボルであればシンボルに
割当てる範囲Ａ、＝Ａ、、−３として出力し、劣勢シン
ボルであればシンボルに割当てる範囲Ａ、＝Ｓとして出
力する。

また、切替器（４）では優勢シンボルか劣勢シンボルか
により入力される劣勢シンボル範囲Ｓまたは固定値“０
“のどちらかを前シンボルに割当てた範囲Ａ１．の最小
座標Ｃｔ−ｔに対する差分座標へ〇として出力する。す
なわち、優勢シンボルであれば差分座標ΔＣ−８として
出力し、劣勢シンボルであれば差分座標ΔＣ−〇として
出力する。

切替器（３）の出力Ａ１はレジスタ（１）、シフト器（
５）および演算部（６）に送られる。

シンボルａ、に対する割り当て範囲Ａ１はレジスタ（１
）に記憶され次のシンボルの範囲算出のデータとなる。

シフト器（５）では入力される範囲Ａ、を１／２と比較
し、１／２より小さい場合には範囲Ａ、を２倍した後再
度１／２と比較して、範囲Ａ、が１／２を越えるまで繰
り返す。そして範囲Ａ、が１／２を越えたときのべき乗
数ｌを求め、座標のシフト量ｌとして演算部（６）へ出
力する。そして、演算部（６）は切替器（３）、切替器
（４）およびシフト器（５）の出力を入力として符号語
の演算を行い出力する。演算部（６）には過去からの差
分座標が累積加算され記憶されている。すなわち、この
累積加算された値は前シンボルに割り当てられた範囲の
最小座標Ｃ１１に等しい。入力差分座標ΔＣは前シンボ
ルの最小座標Ｃ７−１に加算され現シンボルの割り当て
範囲の最小座標Ｃ１を得る。この最小座標ＣＩをシフト
量Ｉ　（ビット）だけシフトさせ範囲Ａ１との一致する
部分があるかを調べ、もし一致する部分があればその部
分を確定座標ビットすなわち符号語として出力する。

［発明が解決しようとする課題］ さて、上述したようにＳとして一定値を用いると特に劣
勢シンボル範囲Ｓが大きく、正規化表現された前シンボ
ルの範囲Ａ、−１が相対的に小さいときには問題があっ
た。

以下にその例を示す。今、前シンボルａｌ−１に割り当
てた範囲Ａ＋−１が０，５を若干越えていたとすると、
シンボルａ１がＭＰＳのときのシンボル範囲Ａ１は極め
て小さくなりシンボルａ　がＬＰＳのときの範囲Ａ２よ
りはるかに小さくなる。

すなわち、本来ＭＰＳの方の出現確率の方が高いにも拘
らずＭＰＳに割り当てられる範囲がＬＰＳに割り当てら
れる範囲より小さくなるわけであり、これは長い符号語
となるため符号化効率の低下につながることになる。仮
にＭＰＳに割り当てられる範囲がＬＰＳに割り当てられ
る範囲より必ず大であるようにすると、Ａ＋−＋　＞０
．５よりＳは０゜２５以下とする必要が生じる。

したがって、前シンボルの範囲Ａ　＋−＋が１．０のと
きはｒ＝０．２５となり、また前シンボルの範囲Ａ１−
１が０．５に近いときはｒ＝０．５となるため、結局符
号化の上ではＬＰＳの出現比率が１／４から１／２の間
で変動していることになる。

この変動幅を少なくできれば出現比率に応じた範囲割り
当てができ符号化効率の向上が期待できる。

この発明は上記のような問題点を解消するためになされ
たもので、特にＬＰＳ　（劣勢シンボル）の出現比率が
１／２に近い場合に効率向上が著しい。

［課題を解決するための手段］ この発明に係わる符号化方式は、マルコフ情報源の出力
シンボル系列を数直線上のある範囲に対応させ、その数
直線上の位置情報を２進表現した値を用いて送信するこ
とにより符号化圧縮を行う符号化方式において、 劣勢シンボルにはその出現確率に対応して選ばれて入力
される一定範囲Ｓを与え優勢シンボル（出現頻度の高い
シンボル）には前記所定範囲から一定範囲Ｓを差引いた
範囲を与える減算手段と、前記一定値Ｓと前記減算手段
の出力との大小を比較する手段とを備え、 優勢シンボルに与えられた範囲のほうが劣勢シンボルに
与えられた範囲よりも小さくなるときには優勢シンボル
と劣勢シンボルの解釈を送受信側で一時的に入れ替えて
数直線上への範囲割当てを行うことを特徴とする。

［作用］ この発明における符号化方式は、優勢シンボルに割当て
る数直線上の範囲と劣勢シンボルに割当てる数直線上の
範囲の大小を比較手段で比較し、優勢シンボルへの割当
て範囲が劣勢シンボルへの割当て範囲より小であるとき
は、優勢シンボルには劣勢シンボルに割当てる範囲を与
え劣勢シンボルには優勢シンボルに割当てる範囲を与え
る。

［実施例］ 以下、この発明の一実施例を図について説明する。第１
図において、（１）は前シンボルの範囲値Ａ１を保持す
るレジスタ、（２）は減算器、（３）は切替器、（４）
は切替器、（５）はシフト器、（６）は演算部、（７）
は比較器である。

つぎに、第１図をもとに動作を説明する。

図示していない予測見積部でマルコフ情報源の状態から
複数の値を持つテーブルより選択されたＳ（劣勢シンボ
ル領域）が入力されると減算器（２）でレジスタ（１）
に記憶されている前シンボルの範囲Ａ１１　との差Ａ、
、−３を求め出力する。比較器（７）では、このＡ、、
−８と直接入力される劣勢シンボル範囲Ｓとの大小を比
較し、その結果をＥとして出力する。

一方、切替器（７）では入力されるＡ、、、−３とＳか
ら比較器（７）の出力Ｅと図示していない予測見積部で
マルコフ情報源が優勢シンボルか劣勢シンボルかを判定
した出力であるＭＰＳ／ＬＰＳとにもとづいて、入力さ
れるＡ、、−３とＳのどちらかに切替えて現在のシンボ
ルに対する範囲の値として出力する。

すなわち、比較器（７）で１．−＋−３＞Ｓであるとき
、出力Ｅを”１　“とじ、Ａ、、−３≦Ｓのとき、出力
Ｅを”０“とすれば、 （イ）Ｅ＝１、シンボルａｔ　−ｏ　（ＭＰＳ）のとき 切替器（８）は入力Ａ、、−８に切替えて、シンボルａ
１に対する割り当ての範囲Ａ、　−８として出力する。

（ロ）Ｅ＝１、シンボルａ、＝１　（ＬＰＳ）のとき 切替器（８）は入力Ｓに切替えて、シンボルａ、に対す
る割り当ての範囲Ａ Ｓとして出力する。

（ハ）Ｅ＝０、シンボルａ、＝Ｏ（ＭＰＳ）のとき 切替器（８）は入力Ｓに切替えて、シンボルａ１に対す
る割り当ての範囲Ａ、＝Ｓとして出力する。

（＝）Ｅ＝Ｏ、シンボルａｔ　＝ｌ　（ＬＰＳ）のとき 切替器（８）は入力Ａ１−１−８に切替えて、シンボル
ａｉに対する割り当ての範囲Ａ、＝Ａ、、、、　−８と
して出力する。

また、切替器（９）では比較器（７）の出力Ｅとシンボ
ルａ１にもとづいて、入力Ｓまたは固定入力“０”のど
ちらかに切替えて前シンボルａに割り当てた範囲の最小
座標との差分の座標へＣとして出力する。すなわち、 （イ）Ｅ−１、シンボルａ：　＝ｏ　（ＭＰＳ）のとき 切替器（９）は固定人力０に切替えて前シンボルａｌｌ
の範囲の最小座標Ｃ とシンボルａ１の範囲の最小座標Ｃ１との差分の座標Δ
Ｃ−０として出力する。

（ｏ）Ｅ＝１、シンボルａ、　−１（ＬＰＳ）のとき 切替器（９）は入力Ｓに切替えて前シンボルａｌｔの範
囲の最小座標Ｃ１１とシンボルａ１の範囲の最小座標Ｃ
Ｉとの差分の座標ΔＣ＝Ｓとして出力する。

（ハ）Ｅ−０、シンボルａ、＝ｏ（ＭＰＳ）のとき 切替器（９）は固定人力Ｏに切替えて差分の座標へ〇−
０として出力する。

（：）Ｅ＝Ｏ、シンボルａｔ　＝ｌ　（ＬＰＳ）のとき 切替器（９）は入力Ｓに切替えて差分の座標ΔＣ−８と
して出力する。

切替器（８）の出力Ａ、はレジスタ（１）、シフト器（
５）および演算部（６）に送られる。

シフト器（５）および演算部（６）の動作は従来技術と
同様である。

また、第２図は第１図で示したこの発明の実施例におけ
る手順を示すフローチャート図である。

まずステップ１では、入力されるシンボルが優勢シンボ
ル（ＭＰＳ）か劣勢シンボル（Ｌ　Ｐ　Ｓ）かを判定す
る。ステップ２、ステップ３では判定結果にもとづいて
入力シンボルに割り当てる範囲Ａ、−、−３が劣勢シン
ボルに割り当てられる範囲Ｓより大であるかを判定する
。

即ち、ステップ２ではステップ１で劣勢シンボルと判定
された場合にその劣勢シンボルに割り当てられた範囲Ｓ
が優勢シンボルに割り当てられる範囲Ａ、、−３より小
であるか判定し、小であればステップ５に進む。また、
そうでなければステップ４に進む。ステップ３ではステ
ップ１で優勢シンボルと判定された場合にその優勢シン
ボルに割り当てられた範囲Ａ、、−８が劣勢シンボルに
割り当てられる範囲Ｓより大であるかを判定し、大であ
ればステップ４に進み、もしそうでなければステップ５
に進む。

ステップ４では入力シンボルが優勢シンボルであって割
り当てられた範囲が劣勢シンボルの範囲より大のときお
よび入力シンボルが劣勢シンボルであって割り当てられ
た範囲が優勢シンボルの範囲より大であるときのそれぞ
れの入力に対する範囲Ａ１と範囲Ａ１の最小座標Ｃ１を
決定する。

ステップ５では入力シンボルが優勢シンボルであって割
り当てられた範囲が劣勢シンボルの範囲より小であると
きおよび入力シンボルが劣勢シンボルであって割り当て
られた範囲が優勢シンボルの範囲より小であるときのそ
れぞれの入力シンボルに対する範囲Ａ１と範囲Ａ、の最
小座標Ｃ１を決定する。

ステップ６はシフト量ｌを計算するために初期値として
０とする。

ステップ７ではステップ４またはステップ５で決定され
た範囲Ａ１が０．５より小であるかを判定し、小である
場合にはステップ８に移る。大である場合にはステップ
９へ進む。

ステップ８では範囲Ａ、を２倍しシフト量！を！＝１と
し、再度ステップ７の判定を行ない範囲Ａ、が０．５を
越えるまでこのルーチンを繰り返す。

ステップ９で符号語を演算するために、累積加算されて
いる前シンボルの範囲の最小座標Ｃに入力される差分座
標ΔＣを加算し現シンボルに対する最小座標Ｃ２を求め
てシフト量ｌビットのシフトを行う。そしてｌビットの
シフトを行った最小座標Ｃ１に入力される範囲Ａｉを加
算して範囲Ａｉの最大座標を求めて、最小座標のｌビッ
トのシフトを行った部分と最大座標の上位とが一致する
ときは最小座標の！ビット分を符号語として出力する。

一致しないときは出力はしない。

つぎにステップ１０に進み、つぎのシンボルの処理のた
めｉをｉ＋１に更新してステップ１に戻る。

なお、受信側で復号する場合には、Ａ１．ｔ　　ＳとＳ
を比較することで送信側でＭＰ　Ｓ／Ｌ　Ｐ　Ｓの一時
的入替えが行われたかどうかを知ることができ、正しく
復号することが可能である。

つぎに、この発明による効果を定量的に説明する。いま
、ＬＰＳの発生確率をｒとし、固定割当て値をＳとした
ときのＬＰＳへの割り当て比ｒｓはＡ＝０．５のとき最
大となりｒＳ＝Ｓ、Ａ＝１のときに最小となりｒｓ　＝
Ｓとなる。

ｒ　、、＝　２３のときの１シンボルあたりの平均符号
長Ｌ　２ｓは Ｌ　２．＝　−（１−ｒ）ｌｏｇ（１−２Ｓ）　−ｒｌ
ｏｇ２ｓｒ　ｓ　＝Ｓのときの１シンボルあたりの平均
符号長Ｌ８は Ｌ　ｓ＝　−（１−ｒ）ｌｏｇ（１−３）−ｒｌｏｇｓ
与えられたｒに対する最適なＳは最悪の符号化効率を最
小にするという観点からＬ　２ｓ＝　Ｌ　ｓを満足する
Ｓの値で与えられる。

つぎに、この発明を適用したときの１シンボルあたりの
平均符号長の範囲はＳ＜１／４では上記と同様であるが
、１／４≦Ｓ＜１／３ではＬ８と１の間に限定される。

第３図は本実施例による符号化効率をｅとしたときの１
　／　ｅ　−１のグラフで示したものであり、最大５％
程度の符号化効率の改善がされていることが分かる。

なお、上記実施例では通常ＭＰＳを数直線上で上側にと
りＬＰＳを下側にとる例を示したが、ＭＰＳを下側にと
りＬＰＳを上側にとるのを原則としても全く同様の効果
を有する。

し発明の効果］ 以上のようにこの発明によれば優勢シンボルＭＰＳと劣
勢シンボルＬＰＳの割当て領域との大きさの関係が、常
に優勢シンボルＭＰＳの割当て領域の方が大きいように
構成したので高い符号化効率が得られるという効果があ
る。

【図面の簡単な説明】

第１図はこの発明の一実施例による符号化装置を示すブ
ロック図、第２図は符号化処理を示すフローチャート図
、第３図はこの発明の実施例による符号化効率を示す図
、第４図は符号化の概念を示す図、第５図は従来の符号
化装置を示すブロック図である。 （１）・・・レジスタ、（２）・・・減算器、（３）、
（４）、（８）、（９）・・・切替器、（５）・・・シ
フト器、（６）・・・演算器、（７）・・・比較器なお
、図中、同一符号は同一　または相当部分を示す。

Claims (1)

1. 【特許請求の範囲】 ２値マルコフ情報源の符号化にあたり情報源の出力シン
   ボル系列を優勢シンボル（出現頻度の高いシンボル）と
   劣勢シンボル（出現頻度の低いシンボル）とに判定しそ
   の出現確率に対応して複数の一定値を記憶したテーブル
   から一つを選びその一定値にもとづいて入力シンボルを
   数直線上の所定の範囲に対応させ、その対応させた範囲
   が所定範囲の１／２以下になるたびに当該範囲を１／２
   を越えるまで２のべき乗倍に拡大し、その数直線上の位
   置情報を２進表現した値と前記２のべき乗数をもとに符
   号化圧縮を行う符号化方式において、劣勢シンボルには
   その出現確率に対応して選ばれて入力される一定範囲Ｓ
   を与え優勢シンボル（出現頻度の高いシンボル）には前
   記所定範囲から一定範囲Ｓを差引いた範囲を与える減算
   手段と、前記一定値Ｓと前記減算手段の出力との大小を
   比較する手段とを備え、 優勢シンボルに与えられた範囲のほうが劣勢シンボルに
   与えられた範囲よりも小さくなるときには優勢シンボル
   と劣勢シンボルの解釈を送受信側で一時的に入れ替えて
   数直線上への範囲割当てを行うことを特徴とする符号化
   方式。