JPH08195680A

JPH08195680A - 算術符号復号化装置

Info

Publication number: JPH08195680A
Application number: JP377295A
Authority: JP
Inventors: Tomoo Tsuda; 智夫津田
Original assignee: Kawasaki Steel Corp
Current assignee: JFE Steel Corp
Priority date: 1995-01-13
Filing date: 1995-01-13
Publication date: 1996-07-30

Abstract

(57)【要約】【目的】算術符号の復号化を高速で行えるようにす
る。【構成】処理手順を変更し、レジスタの更新回数を減
らす。コードレジスタのスタッフィングビットの幅を増
やし、符号入力に伴うループを完全に無くす。データを
先読みし、先行する未確定の画素に依存した２つの文脈
を用意して処理を行い、先行する画素が確定した段階で
１つを選択するようにし、処理の二重化を行って、先行
する画素が確定するまでの待ち時間を減らす。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、算術符号復号化装置に
係り、特に、算術符号化された２値画像を復号化する際
に用いるのに好適な、高速で復号化を行うことが可能な
算術符号復号化装置に関するものである。

【０００２】

【従来の技術】伝送路を用いた情報伝達や、データベー
スへの情報の保存に際しては、伝送あるいは保存される
情報のデータ量が少ない方が望ましい。例えば、画像情
報は一般に膨大な情報量となるものであるため、その情
報の伝達や保存に際して、様々な手法によるデータ圧縮
がなされている。

【０００３】データ圧縮には、非可逆符号化によるもの
と、可逆符号化によるものがあり、可逆符号化のうち、
エントロピ符号化と呼ばれるものは、有限個のシンボル
を持つ情報源出力に対し、出現確率の偏り利用してデー
タ圧縮している。即ち、出現確率の高いシンボルには、
より短い符号を割り当てることによって、生成される符
号の平均符号長を短くするようにし、純数な統計的性質
によって情報圧縮を図っている。

【０００４】このエントロピ符号化のうち、算術符号化
は、エライアス符号化として知られている無記憶情報源
に対する理想的符号化方式を、実用可能な形に再編成し
たものと言える。この算術符号化では、符号化すべきシ
ンボル系列を、劣勢シンボル及び優勢シンボルの出現確
率に応じて分割した確率数直線上にマッピングし、その
位置に従って符号化することによって、算術符号を作成
している（「インターフェース′９１．１２月号」１５
４頁〜１５７頁参照）。

【０００５】例えば、図１の算術符号の概念図では、
“１”のシンボルが、出現確率がＰの劣勢シンボルとさ
れ、一方、“０”のシンボルは、出現確率が（１−Ｐ）
の優勢シンボルとされている。例えば、“０，１，０，
０，１”のシンボル系列を符号化する際には、まず、第
１番目のシンボル“０”に対応して、（１−Ｐ）の優勢
シンボルの幅（オージェンド値と称する）Ａ0 が得られ
る。第２番目のシンボル“１”に対応して、（１−Ｐ）
Ｐのオージェンド値Ａ01が得られる。第３番目のシンボ
ル“０”に対応して、（１−Ｐ）²Ｐのオージェンド値
Ａ010 が得られる。第４番目のシンボル“０”に対応し
て、（１−Ｐ）³Ｐのオージェンド値Ａ0100が得られ
る。第５番目のシンボル“１”に対応して、（１−Ｐ）
³Ｐ²のオージェンド値Ａ01001 が得られる。第６番目
のシンボル“１”に対応して、“（１−Ｐ）³Ｐ³”の
オージェンド値Ａ010011が得られる。

【０００６】これらのオージェンド値は、図１に示され
るような確率数直線上での符号の範囲に対応しており、
図１の一点鎖線Ｃで示されるものは、その確率数直線上
での符号の位置（コードと称する）である。このコード
に応じて、一般に２進小数値で表現されるものが、算術
符号の符号化された結果となる。

【０００７】このような算術符号化を行う符号化処理、
あるいは、算術符号化されたものを復号する復号化処理
に際しては、一般に、前記のような確率数直線上での符
号の範囲を示すオージェンド値を記憶するオージェンド
レジスタと、同じく確率数直線上での符号の位置を示す
コード値を記憶するコードレジスタを用いた処理を繰り
返す、ループ処理となっている。

【０００８】更に、算術符号では、符号を数値と見做
し、加算によって逐次的に符号を作成していくため、桁
上がりが生じて、既に決定した上位ビットに影響を及ぼ
す場合がある。この桁上がりによるビット反転波及の範
囲を所定範囲内に抑えるために、ビット・スタッフィン
グ法が用いられている。

【０００９】これは、図２に示すように、例えばＶビッ
トのコードレジスタＣの上位にＷビットの監視レジスタ
Ｐを用意しておき、この監視レジスタＰの内容が全て１
になったら、監視レジスタＰとコードレジスタＣの間に
１ビットの“０”を挿入するというものである。このよ
うにして、例えば監視レジスタＰが全て“１”のとき
に、コードレジスタＣで桁上がりが起こっても、挿入ビ
ットが反転して“１”になるだけであり、それより上位
のビットは影響を受けることなく、出力される。

【００１０】算術符号の復号化は、具体的には、次のよ
うにして行われる。（１）直前の画素を含む復号済みの何画素かを、任意の
形に並べて、ビットレスと見做して整数化し、現在の文
脈ＣＸを得る。（２）この文脈ＣＸから状態ＳＴを得る。（３）この状態ＳＴから確率（劣勢分割幅ＬＳＺ）等を
求める。（４）確率に従って、オージェンドを分割し、コード値
と比較して復号する。（５）必要に応じて、文脈ＣＸに対応する状態ＳＴを更
新する。（６）以上を繰り返す。

【００１１】以下、図３に示されるようなレジスタ構造
を有する例について、上記手順を実施するための、ＩＳ
Ｏ／ＩＥＣＤＩＳ１１５４４（ＣＣＩＴＴＲｅ
ｃ，Ｔ．８２（１９９３Ｅ）Ｐ４１〜Ｐ４６参照）によ
る復号化処理の具体的なアルゴリズムを説明する。ここ
で、コードレジスタの例えば上位１６ビットを保持する
Ｃｈｉｇｈレジスタと、コードレジスタの例えば下位１
６ビットを保持するＣｌｏｗレジスタは、１つの３２ビ
ットのコードレジスタと考えることができ、コード値Ｃ
の正規化（リノーマライズ）によって、Ｃｌｏｗレジス
タの第１５ビット（図の左端）からの新データのビット
が、Ｃｈｉｇｈレジスタの第０ビット（右端）にシフト
される。しかしながら、復号化のための比較は、Ｃｈｉ
ｇｈレジスタのみを用いて行われる。Ｃｌｏｗレジスタ
は、“ｂ”が記入された上位８ビットのみが使用され
る、繰り上がり対処用のレジスタであり、新しいデータ
は、Ｃｌｏｗレジスタの“ｂ”ビットに同時に１バイト
ずつ格納される。“ａ”が記入されたビットは、現在の
オージェンド値を示すビットであり、“ｘ”が記入され
たビットは、コード値を表わすビットである。オージェ
ンドレジスタＡの１７番目のビットは、概念的に存在し
ているが、１６ビットの処理が必要な場合には、取り除
くことができる。

【００１２】復号化処理に際しては、図４に示す流れ図
のように、まず、初期化ルーチンを呼び出し（ステップ
１００）、初期化を行う。

【００１３】この初期化ルーチンのアルゴリズムは、例
えば図５に示す如くである。この初期化ルーチンにおい
ては、まず、画像の最初のストライプ又は強制リセット
であるか否かが判定され（ステップ２００）、画像の最
初のストライプ又は強制リセットである場合には、全て
の可能な文脈ＣＸの値（例えば１２ビット）に対応する
確率評価状態ＳＴの値（例えば７ビット）及び現在の優
勢シンボルＭＰＳの値（例えば１ビット）を“０”にセ
ットする（ステップ２０２）。一方、画像の最初のスト
ライプ又は強制リセットでない場合には、全ての可能な
ＣＸの値に対して、ＳＴとＭＰＸの値を、先行ストライ
プの終わりの値にセットする（ステップ２０４）。

【００１４】ステップ２０２又は２０４終了後、まず、
コードレジスタＣの値を“０”として、後出の符号バイ
ト入力（ＢＹＴＥＩＮ）ルーチン（図６参照）を呼び
出し、符号入力処理を行う。次いで、コードレジスタＣ
の値を、最下位ビットＬＳＢ側から最上位ビットＭＳＢ
側へ左に８ビットシフトし、再び符号バイト入力ルーチ
ンを呼び出して、次のバイトの符号入力処理を行う。更
に、コードレジスタＣの値を左に８ビットシフトし、再
び符号バイト入力ルーチンを呼び出して、更に次のバイ
トの符号入力処理を行う。これにより、３バイトがコー
ドレジスタＣに読み込まれる。更にオージェンドレジス
タＡに“０ｘ１００００”（１６進数）をセットして、
この初期化ルーチンを抜ける。

【００１５】前記初期化ルーチンのステップ２０６等で
実行される符号バイト入力ルーチンのアルゴリズムは、
例えば図６に示す如くである。この符号バイト入力ルー
チンにおいては、まず、符号化ビットストリームデータ
ＳＣＤ（例えば１６ビット）から、全てのデータがバイ
ト単位で読み出されるまで（ステップ３００）、ＳＣＤ
から１バイトずつ読み出し、最新のバイトデータを一時
的に保持するためのバッファレジスタＢＵＦＦＥＲをこ
れと同じ値にセットする（ステップ３０２）。ＳＣＤか
ら全データを読み出した後は、バッファレジスタＢＵＦ
ＦＥＲを“０”にセットする（ステップ３０４）。ステ
ップ３０２又は３０４終了後、バッファレジスタＢＵＦ
ＦＥＲを８ビット左へシフトして、コードレジスタＣに
加えることにより、読み出されたバイトが、コードレジ
スタの下位ビットＣｌｏｗの上位８ビットに挿入され、
カウンタＣＴが８にリセットされる（ステップ３０
６）。

【００１６】ここで、ＣＴは、コードレジスタＣの下位
ビットＣｌｏｗ中の圧縮ビット数の経過（１ビット毎の
シフト回数）を保持しているカウンタであり、ＣＴが
“０”になると、新しいバイトがＣｌｏｗに挿入され
る。

【００１７】初期化ルーチンを抜けた後、図４のステッ
プ１０２に戻り、符号化ビットストリームデータＳＣＤ
を読み出す。次いで、文脈（ｃｏｎｔｅｘ）ＣＸを読み
出し（ステップ１０４）、該文脈ＣＸに応じた状態ＳＴ
の値ＳＴ［ＣＸ］に基づいて、予め準備された、例えば
図７に示すような、各状態ＳＴの値に対応する、劣勢分
割幅ＬＳＺの値、次の確率評価状態をそれぞれ与える劣
勢アレイＮＬＰＳ、優勢アレイＮＭＰＳの値、及び優勢
と劣勢を入れ換えるための入換フラグＳＷＴＣＨの値が
記載された確率評価テーブル（ＩＳＯ／ＩＥＣ１１５
４４：１９９３（Ｅ）のＴａｂｌｅ２４；ＣＣＩＴＴ
Ｒｅｃ，Ｔ．８２（１９９３Ｅ）のＰ３３参照）から、
状態ＳＴ［ＣＸ］を指標として読み出された劣勢分割幅
ＬＳＺの値を、そのときのオージェンドレジスタＡの値
から引くことによって、オージェンドを分割する（ステ
ップ１０６）。次いで、分割されたオージェンド値Ａ
と、コード値が格納されたコードレジスタの上位ビット
Ｃｈｉｇｈを比較し（ステップ１０８）、図８に実線で
示す如く、オージェンド値Ａの方がコード値Ｃを含んで
いる場合には、オージェンド値Ａが“０ｘ８０００”未
満であるか否かを判定する（ステップ１１０）。オージ
ェンドレジスタＡのＭＳＢが“１”であり、ステップ１
１０の判定結果が否である場合には、その時の優勢シン
ボルＭＰＳ（１ビット値）を画素Ｐｉｘに入れる（ステ
ップ１１２）。一方、オージェンドレジスタＡのＭＳＢ
が“０”であり、ステップ１１０の判定結果が正である
場合には、後出ＭＰＳ入換ルーチン（図９参照）及び正
規化ルーチン（図１１参照）を呼び出す（ステップ１１
４）。

【００１８】一方、前出ステップ１０８の判定結果が否
であり、図８に破線で示す如く、オージェンド値Ａの範
囲にコード値Ｃが存在しない場合には、後出ＬＰＳ（劣
勢シンボル）入換ルーチン（図１０参照）及び正規化ル
ーチンを呼び出す（ステップ１１６）。

【００１９】即ち、次の復号化の時に行われるオージェ
ンドレジスタとコードレジスタの桁位置を揃える必要が
あるため、コードレジスタＣも、オージェンドレジスタ
Ａをシフトしたビット数と同じビット数だけ左側にシフ
トして、正規化（リノーマライズ）を行う。

【００２０】前記ステップ１０４乃至１１６の処理を、
全画素について終了するまで行う（ステップ１１８）。

【００２１】前記復号化処理のステップ１１４で呼び出
されるＭＰＳ入換ルーチンの具体的なアルゴリズムは、
図９に示す如くである。即ち、オージェンド値Ａと劣勢
分割幅ＬＳＺを比較し、判定結果が否であれば、優勢シ
ンボルＭＰＳの値を画素Ｐｉｘに入れ、ＭＰＳに対応す
る、次の確率評価状態を与える優勢アレイＮＭＰＳの値
（例えば７ビット）を状態ＳＴに入れて、状態ＳＴを更
新する（ステップ４０２）。一方、ステップ４００の判
定結果が正である場合には、優勢シンボルＭＰＳを反転
して、劣勢シンボルＬＰＳ（＝１−ＭＰＳ）を画素Ｐｉ
ｘに入れ（ステップ４０４）、入換フラグＳＷＴＣＨが
１であるか否か判定する（ステップ４０６）。ステップ
４０６の判定結果が正である場合には、優勢シンボルＭ
ＰＳを反転し（ステップ４０８）、ＬＰＳに対応する、
次の確率評価状態を与える劣勢アレイＮＬＰＳの値（例
えば７ビット）を状態ＳＴに入れて、状態ＳＴを更新す
る（ステップ４１０）。

【００２２】又、前記復号化処理のステップ１１６で呼
び出されるＬＰＳ入換ルーチンの具体的なアルゴリズム
は図８に示す如くである。即ち、オージェンド値Ａと劣
勢分割幅ＬＳＺが比較され（ステップ５００）、判定結
果が正である場合には、そのときのコードレジスタ上位
ビット値Ｃｈｉｇｈからオージェンド値Ａを引いたもの
を新たなコードレジスタの上位ビット値Ｃｈｉｇｈとし
てコード値を変えると共に、劣勢分割幅ＬＳＺをオージ
ェンド値Ａとし（ステップ５０２）、そのときの優勢シ
ンボルＭＰＳを画素Ｐｉｘに入れると共に、優勢アレイ
ＮＭＰＳの値を状態ＳＴに入れて状態ＳＴを更新する
（ステップ５０４）。

【００２３】一方、ステップ５００の判定結果が否であ
る場合には、ステップ５０２と同様の処理（ステップ５
０６）を行った後、優勢シンボルＭＰＳを反転した値
（１−ＭＰＳ）を画素Ｐｉｘに入れ（ステップ５０
８）、入換フラグＳＷＴＣＨが“１”であるかどうか判
定する（ステップ５１０）。ステップ５１０の判定結果
が正である場合には、優勢シンボルＭＰＳの反転を行い
（ステップ５１２）、劣勢アレイＮＬＰＳの値を状態Ｓ
Ｔに入れて状態ＳＴを更新する（ステップ５１４）。

【００２４】前記復号化処理のステップ１１４及び１１
６で呼び出される正規化ルーチンの具体的アルゴリズム
は図１１に示す如くである。即ち、コードレジスタＣの
下位ビットＣｌｏｗ中の圧縮ビット数の経過（１ビット
毎のシフト回数）を保持するためのカウンタＣＴが
“０”であるか否か判定し（ステップ６００）、カウン
タＣＴの値が“０”である場合には、前記符号バイト入
力ルーチン（図６）を呼び出して、新しいバイトを下位
ビットＣｌｏｗに挿入する（ステップ６０２）。次い
で、レジスタＡ及びＣの値を１ビットずつ左にシフトす
ると共に、カウンタＣＴの値を１だけデクリメントし
（ステップ６０４）、オージェンド値Ａが“０ｘ０８０
００”となるまで、即ち、オージェンドレジスタＡのＭ
ＳＢが“１”となるまで、オージェンドレジスタＡの値
とコードレジスタＣの値を１ビットずつシフトする（ス
テップ６０６）。ステップ６０６の判定結果が否であっ
ても、カウンタＣＴの値が０でない場合には（ステップ
６０８）、再び符号バイト入力ルーチンを呼び出す（ス
テップ６１０）。

【００２５】

【発明が解決しようとする課題】しかしながら従来は、
中間値ＢＵＦＦＥＲ等もレジスタに入れていたため、レ
ジスタの更新回数が多く、処理速度が低下してしまう。
又、図１１に示した如く、正規化ルーチンに、ステップ
６０６から６００に戻る、符号入力に併うループが存在
し、オージェンド値Ａ及びコード値Ｃを１ビットずつシ
フトしていたため、やはり処理速度が低下する。更に、
文脈ＣＸが、直前に復号化した画素Ｐｉｘの値に依存す
るため、直前の画素の復号化が終了しないと、次の画素
の復号化を始めることができない等の問題点を有してい
た。

【００２６】本発明は、前記従来の問題点を解消するべ
くなされたもので、処理速度を速めて、高速で復号する
ことが可能な算術符号復号化装置を提供することを目的
とする。

【００２７】

【問題点を解決するための手段】本発明は、符号化すべ
きシンボル系列を、劣勢シンボル及び優勢シンボルの出
現確率に応じて分割した確率数直線上にマッピングし、
その位置に従って符号化することによって作成された算
術符号を、前記確率数直線上での符号の範囲を示すオー
ジェンド値を記憶するオージェンドレジスタ、及び、同
じく確率数直線上での符号の位置を示すコード値を記憶
するコードレジスタを用いて復号化するための算術符号
復号化装置において、先行するデータから、現在の文脈
を生成する手段と、該文脈を指標として、状態及び現在
の優勢シンボルを決定する手段と、前記状態を指標とし
て、リード・オンリー・メモリに記憶された確率評価テ
ーブルの値を読み出す手段と、該確率評価テーブルから
読み出された確率に従ってオージェンドを分割し、正規
化する場合のシフト量、及び、コード値の更新される可
能性のある値を計算する手段と、分割の結果、コード値
が優劣どちらの領域に含まれ、どちらの領域が大きいか
を判別し、処理を振り分けて、データを生成する手段
と、振り分けられた結果に応じて、予め計算しておいた
前記シフト量を用いてシフトを行い、オージェンドレジ
スタ及びコードレジスタを更新する手段と、必要に応じ
て、ランダム・アクセス・メモリに記憶された状態や現
在の優勢シンボルを更新する手段とを備えることによ
り、前記目的を達成したものである。

【００２８】更に、実際にシフトした量を、コードレジ
スタの隙間の大きさに加算する手段と、該コードレジス
タの隙間に次の符号を入れてビットスタッフィングを行
う手段とを備え、前記コードレジスタが、コード値に対
応するビット長の上位ビットと、シフト量に対応する有
効ビット長に加えて、前記隙間の最大量を収容可能なビ
ット長の、拡張された下位ビットを含み、該下位ビット
がスタッフィングビットとして使われるようにして、同
じく前記目的を達成したものである。

【００２９】又、同様の算術符号復号化装置において、
先行するデータの内、未確定のデータに依存した、複数
の文脈を生成する手段と、該複数の文脈のそれぞれを指
標として、それぞれに対応する状態及び現在の優勢シン
ボルの候補を生成する手段と、先行するデータが確定し
た段階で、前記候補中から、実際に用いる状態及び現在
の優勢シンボルを決定する手段とを備えることにより、
同じく前記目的を達成したものである。

【００３０】

【作用】本発明は、処理手順を変更し、レジスタの更新
回数を減らすことにより、処理速度を高速化したもので
ある。

【００３１】これに加えて、コードレジスタの幅を拡大
することにより、符号入力に伴なうループを完全になく
して、処理速度を高速化したものである。

【００３２】又、先行する未確定のデータに依存した２
つの文脈を用意して、先読みによる処理の二重化を行
い、先行するデータが確定した段階で１つを選択するよ
うにして、処理速度を高速化したものである。

【００３３】

【実施例】以下図面を参照して、本発明の実施例を詳細
に説明する。

【００３４】本実施例における復号化処理は、図１２乃
至図１４に示す手順に従って実行される。この図１２乃
至図１４は、図４に示した従来例のステップ１０２以降
に対応するもので、まず、図１２のステップ７００乃至
７０４で、文脈ＣＸを指標としてランダムアクセスメモ
リ（ＲＡＭ）を参照することにより、状態ＳＴ及び優勢
シンボルＭＰＳを生成する。具体的には、文脈ＣＸは直
前の画素の復号値に依存するので、直前の画素が“０”
の場合と“１”の場合を考えて、ＲＡＭを２つ使用し、
それぞれの場合の文脈ＣＸを、ＣＸ０、ＣＸ１（例えば
１２ビット）とする（ステップ７００）。次いで、文脈
ＣＸ０、ＣＸ１を用いて、それぞれに対応する状態ＳＴ
０、ＳＴ１（例えば７ビット）を生成し、ＳＴの候補と
する。又、直前のデコードで用いた劣勢アレイＮＬＰＳ
及び優勢アレイＮＭＰＳ（例えば７ビット）も状態ＳＴ
の候補とする（ステップ７０２）。更に、状態ＳＴと同
様に、文脈ＣＸ０、ＣＸ１から、それぞれに対応する優
勢シンボルＭＰＳ０、ＭＰＳ１（例えば１ビット）を生
成し、優勢シンボルＭＰＳの候補とする。又、直前のデ
コードに用いた優勢シンボルＭＰＳと、その反転も、Ｍ
ＰＳの候補とする（ステップ７０４）。上記のステップ
７００乃至７０４が、ＲＡＭから読み出す手順である。

【００３５】次いで、ステップ７０６に進み、後述する
「判別」により、直前の画素値等から、実際に用いる状
態ＳＴ及び優勢シンボルＭＰＳを決定する（選択）。

【００３６】次いでステップ７０８に進み、決定された
状態ＳＴを指標として、リードオンリーメモリ（ＲＯ
Ｍ）に予め記憶されている、図７に示したような確率評
価テーブルを参照することにより、劣勢分割幅ＬＳＺ、
劣勢アレイＮＬＰＳ、優勢アレイＮＭＰＳ、入換フラグ
ＳＷＴＣＨを決定する（ＲＯＭの読み出し）。

【００３７】次いで図１３のステップ７１０に進み、劣
勢分割幅ＬＳＺをレジスタｐ（例えば１５ビット）に入
れ、そのときのオージェンド値Ａから劣勢分割幅ＬＳＺ
を引いた値をレジスタｑ（例えば１６ビット）に入れる
ことにより、オージェンドを分割する。次いでステップ
７１２に進み、レジスタｐを正規化するべく、ｐを“０
ｘ８０００”以上とするためのシフト量ｐｓ（例えば４
ビット）と、レジスタｑを正規化するべく、ｑを“０ｘ
８０００”以上とするためのシフト量ｑｓ（例えば４ビ
ット）を求めると共に、コード値Ｃからｑを引くことに
よって、スタッフィングビットが３０ビットに拡張され
たコードレジスタＣ（例えば４６ビット）の更新される
可能性のある値Ｃ′（例えば４６ビット）を計算する
（分割など）。

【００３８】次いでステップ７１４乃至７１８で、コー
ド値Ｃｈｉｇｈが、劣勢領域ｐと優勢領域ｑのどちらの
領域に含まれるのか、更に、劣勢領域ｐと優勢領域ｑの
どちらが大きいのかに応じて、４通りの処理に振り分け
られる。

【００３９】又、この時点で、例えば図１５及び図１６
に示すような関係を用いて、次の画素を復号化するとき
に用いる選択信号を生成する。図１３及び図１４におい
て、Ｘは、“０”、“１”のどちらでもかまわないドン
ト・ケア（Ｄon´t care ）状態である。

【００４０】ステップ７１４及び７１６の判定結果がい
ずれも正であるとき、即ち、図１７に実線で示す如く、
Ｃｈｉｇｈ（＝Ｃ）が優勢領域ｑに含まれ、且つ、優勢
領域ｑが劣勢領域ｐより小さいときには、ステップ７２
０に進み、そのときの劣勢シンボルＬＰＳを画素Ｐｉｘ
とする。次いでステップ７２２で、レジスタｑを予め計
算しておいたシフト量ｑｓだけまとめて左にシフトし
て、オージェンド値Ａとし、コード値Ｃ（＝Ｃｈｉｇ
ｈ）をシフト量ｑｓだけまとめて左にシフトして、新し
いコード値Ｃとする（シフト及びレジスタの更新）。

【００４１】次いでステップ７２４に進み、入換フラグ
ＳＷＴＣＨがセットされていれば、ステップ７２６で優
勢シンボルＭＰＳを反転し、ステップ７２８で劣勢アレ
イＮＬＰＳを状態ＳＴとする（ＲＡＭの更新）。

【００４２】一方、ステップ７１４の判定結果が正で、
ステップ７１６の判定結果が否である場合、即ち、図１
８に実線で示す如く、コード値Ｃが優勢領域ｑに含ま
れ、優勢領域ｑが劣勢領域ｐより小さくないときには、
ステップ７３０に進み、そのときの優勢シンボルＭＰＳ
の値を画素Ｐｉｘに入れる。次いでステップ７３２に進
み、ステップ７２２と同様にシフト量ｑｓだけまとめた
シフトを行って、オージェンドレジスタ及びコードレジ
スタを更新する（シフト及びレジスタの更新）。

【００４３】次いでステップ７３４に進み、ｑを正規化
するためのシフト量ｑｓが“０”でない場合には、ステ
ップ７３６で優勢アレイＮＭＰＳを状態ＳＴに入れる
（ＲＡＭの更新）。

【００４４】又、前述ステップ７１４の判定結果が否
で、ステップ７１８の判定結果が正である場合、即ち、
図１７に破線で示す如く、コード値Ｃが優勢領域ｑに含
まれず、且つ、優勢領域ｑが劣勢領域ｐより小さいとき
には、ステップ７４０に進み、ステップ７３０と同様
に、そのときの優勢シンボルＭＰＳの値を画素Ｐｉｘに
入れ、ステップ７４２で、レジスタｐを予め計算してお
いたシフト量ｐｓだけまとめて左にシフトしたものを新
しいオージェンド値Ａとし、ステップ７１２で求めてお
いたコード値の候補Ｃ′を、シフト量ｑｓだけまとめて
左にシフトしたものを新しいコード値Ｃとして、レジス
タを更新する（シフト及びレジスタの更新）。

【００４５】次いでステップ７４４に進み、そのときの
優勢アレイＮＭＰＳの値を状態ＳＴに入れる（ＲＡＭの
更新）。

【００４６】又、前記ステップ７１４及び７１８の判定
結果がいずれも否である場合、即ち、図１８に破線で示
す如く、コード値Ｃが優勢領域ｑに含まれず、且つ、優
勢領域ｑが劣勢領域ｐより小さくないときには、ステッ
プ７５０に進み、そのときの劣勢シンボルＬＰＳを画素
Ｐｉｘに入れ、ステップ７５２で、レジスタｐをシフト
量ｐｓだけまとめて左にシフトしたものを新しいオージ
ェンド値Ａとし、コード値の候補Ｃ′をシフト量ｑｓだ
けまとめて左にシフトしたものを新しいコード値Ｃとし
て、レジスタを更新する（シフト及びレジスタの更
新）。

【００４７】次いでステップ７５４に進み、入換フラグ
ＳＷＴＣＨが“１”であれば、ステップ７５６で、優勢
シンボルＭＰＳを反転し、ステップ７５８で、そのとき
の劣勢アレイＮＬＰＳの値を状態ＳＴに入れる（ＲＡＭ
の更新）。

【００４８】次いで図１４のステップ７６０乃至７６８
で、符号のバイト単位での入力及び正規化を行う（符号
バイト入力：ＢＹＴＥＩＮ）。具体的には、ステップ
７６０で、シフト量ｐｓ及びｑｓのうち、実際にシフト
に用いた量をＳ（例えば４ビット）とし、ステップ７６
２で、シフトによってコードレジスタに生じた隙間の大
きさを保持しているカウンタＣＳ（例えば５ビット）を
Ｓだけ加算する。このカウンタＣＳは、従来のカウンタ
ＣＴに相当する。

【００４９】次いでステップ７６４に進み、この隙間の
大きさＣＳが１６以上になったときは、ステップ７６６
で、コード値Ｃに、次の符号化データＳＣＤ（例えば１
６ビット）を（ＣＳ−１６）だけ左にまとめてシフトし
たものを加えると共に、入力分に対応させてカウンタＣ
Ｓを“１６”だけ減算したものを新しいＣＳとして、ス
テップ７６８で、新しい符号化データＳＣＤを読み込ん
で、次のデータの処理に移行する。

【００５０】本実施例におけるコードレジスタＣは、図
１９に示す如く、従来と同様の、コード値を格納する上
位１６ビットＣｈｉｇｈと、図３に示したような従来例
においては１６ビットにすぎなかったスタッフィングビ
ットを３０ビットに拡張したＣｌｏｗの合計４６ビット
とされている。このようにスタッフィングビットを１５
ビット×２＝３０ビットとすることにより、上記処理手
順と合せて、処理の簡略化を図ることができる。

【００５１】即ち、正規化に従って、コードレジスタ
が、例えば実際のシフト量Ｓ＝５、Ｓ＝６、Ｓ＝７の順
で、シフトしたとすると、図１９中にＶで示した有効な
ビットの隙間に“０”が入っていく。今、初期値とし
て、隙間カウンタＣＳ＝０、即ち隙間がないとすると、
まず５ビットシフトするので、隙間が５ビットになり、
次に６ビットシフトするので、隙間が５＋６＝１１ビッ
トになり、更に、７ビットシフトするので、隙間が１１
＋７＝１８ビットとなる。この３回目のシフトによっ
て、隙間が１６ビット以上になるので、ここに次の符号
データＳＣＤを入れ、ビットスタッフィングを行う。

【００５２】ここで、Ｃｌｏｗを３０ビットとしている
のは、次の理由による。即ち、Ｃｌｏｗのビット長を
Ｗ、隙間をＣＳとすると、Ｃｌｏｗ中の有効ビット長Ｌ
は、Ｌ＝Ｗ−ＣＳで表わされる。

【００５３】一方、シフト量Ｓは最大１５なので、有効
ビット長Ｌは１５以上でなければならない。又、隙間Ｃ
Ｓは最大１５なので、Ｌが１５以上という条件を満足す
るためには、図２０に示す如く、Ｗ（＝Ｌ＋ＣＳ）が３
０以上でなければならない。図２０は、ＣＳ＝１５、即
ち隙間が最大で、有効ビットが最小となった状態を示し
たものである。

【００５４】本実施例における処理のタイムチャートを
図２１に示す。画素ｎを復号する場合、まずＲＡＭの読
み出し（図１２のステップ７００〜７０４に相当）を行
う。この時点では、直前の画素ｎ−１の復号は終了して
いないので、文脈ＣＸは一意に決まらない。そこで、Ｒ
ＡＭを２つ用いて、画素ｎ−１が０の場合と、１の場合
のどちらにも対応できるようにする。

【００５５】画素ｎのＲＡＭの読み出しが終了した時点
では、直前の画素ｎ−１の判別（図１３のステップ７１
４〜７１８に相当）が終わっており、画素ｎ−１が０か
１に決まっている。そこで、画素ｎ−１の値に従って、
ＲＡＭの読み出し結果から、適当な状態を選択（図１２
のステップ７０６に相当）する。この選択結果に従っ
て、ＲＯＭの読み出し（図１２のステップ７０８に相
当）を行う。このＲＯＭの読み出しには２クロックかか
り、確率（劣勢分割幅ＬＳＺ）等が得られる。得られた
確率やレジスタ値を基に、画素ｎの分割（図１３のステ
ップ７１０〜７１２に相当）等を行う。分割結果を基に
判別（画素生成を含む）を行う（図１３のステップ７１
４〜７２０、７３０、７４０、７５０に相当）。

【００５６】次いで、レジスタ更新のため、シフト処理
（図１３のステップ７２２、７３２、７４２、７５２に
相当）を行い、必要であれば、ＲＡＭの更新（図１３の
ステップ７２４〜７２８、７３４〜７３６、７４４、７
５４〜７５８）を行い、レジスタを更新する。

【００５７】更に、必要であれば符号バイト入力（ＢＹ
ＴＥＩＮ：図１４のステップ７６０〜７６８に相当）
を行う。

【００５８】本実施例では、コードレジスタの下位ビッ
ト（スタッフィングビット）が３０ビットに拡張されて
いるので、１６ビット単位で迅速に処理を行うことがで
きる。これに対して従来は８ビット単位で時間がかかっ
ていた。

【００５９】本実施例においては、図２１に示す如く、
直前の画素ｎ−１の判別が終了して画素が生成される前
にＲＡＭの読み出しを先行して行っているので、処理速
度を高速化することができる。これに対して従来は、直
前の画素の符号バイト入力（コードレジスタＣへの書き
込み）が終了した時点で、初めて次の画素のＲＡＭの読
み出しを開始していたため、図２１の例では５クロック
分、余計に時間がかかっていたものである。

【００６０】図２２は、本発明を用いた装置の実施例の
構成を示す。

【００６１】本実施例は、減算、比較、シフト、レジス
タ処理等を行う演算処理部１０と、２つのＲＡＭを持
ち、先行する画素値が“０”又は“１”のいずれの場合
にも対応できるように、２つの状態ＳＴ０、ＳＴ１及び
優勢シンボルＭＰＳ０、ＭＰＳ１を生成する状態発生部
６０と、先行する画素に従って生成される選択信号に応
じて、正しい状態ＳＴ及び優勢シンボルＭＰＳを選択す
るマルチプレクサ７０と、確率評価テーブルが収納され
たＲＯＭを用いて、確率等を生成する確率推定部８０と
から構成されている。

【００６２】前記演算処理部１０は、具体的には、図２
３に示す如く、オージェンド値Ａ及び劣勢分割幅ＬＳＺ
を一時的に保持するラッチ１２、１４と、該ラッチ１
２、１４を介して入力されるＡからＬＳＺを引くことに
よって、図１３のステップ７１０に相当する分割処理を
行い、ｐ及びｑを出力する減算回路１６と、該減算回路
１６から出力されるｐ及びｑの値をそれぞれ一時的に保
持するラッチ１８、２０と、該ラッチ１８、２０から出
力されるｐ、ｑの値に応じて、シフト量ｐｓ、ｑｓを計
算するシフト量計算回路２２と、コードレジスタの上位
１６ビットに格納されたコード値Ｃからｑの値を引くこ
とによって、コード値の候補Ｃ′を計算する減算回路２
４と、前記コード値Ｃ及びラッチ１８、２０に保持され
たｐ、ｑの値に応じて、図１３のステップ７１４〜７１
８に相当する判別処理を行い、画素や選択信号等を生成
する判別回路２６と、該判別回路２６の判別結果に従っ
て、前記シフト量計算回路２２、ラッチ１８、２０、減
算回路２４の出力をそれぞれ選択するマルチプレクサ２
８、３０、３２と、該マルチプレクサ２８、３０、３
２、前記判別回路２６の出力を一時的に保持するラッチ
３４、３６、３８、４０と、前記ラッチ３６から入力さ
れるｐ又はｑの値に対して、ラッチ３４から入力される
シフト量ｐｓ又はｑｓだけシフトするためのシフト回路
４２と、前記ラッチ３８から入力されるコード値Ｃ又は
その候補Ｃ′に対してｑｓのシフトを行うシフト回路４
４と、前記ラッチ３４から入力されるシフト量に応じ
て、図１９の隙間カウンタＣＳの処理を行い、符号をバ
イト入力するか否か判定するコードレジスタ制御回路４
６と、前記シフト回路４２、４４の出力をそれぞれラッ
チするラッチ４８、５０と、該ラッチ４８の出力により
内容が更新されるオージェンドレジスタ５２と、前記コ
ードレジスタ制御回路４６の出力に応じて、符号化デー
タＳＣＤを入力し、ファーストイン・ファーストアウト
（ＦＩＦＯ）メモリに保存するメモリ５４と、前記コー
ドレジスタ制御回路４６からの制御信号により、必要に
応じて、前記メモリ５４の出力により内容が更新される
コードレジスタ５６とから構成されている。

【００６３】前記シフト量計算回路２２としては、例え
ばプライオリティエンコーダを有効に用いることができ
る。即ち、シフト量は、「何ビット左（ＭＳＢの方向）
にシフトすれば“０ｘ８０００”以上になるか？」を意
味する。又、“０ｘ８０００”以上とは、ＭＳＢが
“１”であることを意味する。従って、シフト量の計算
は、「ＭＳＢから数えて、何ビット目に“１”があるの
か？」という問題に帰着する。この問題は、図２４に示
すような論理を持つプライオリティエンコーダで解決で
きる。例えば、入力の第１５ビットが“１”であれば、
他の入力にかかわらず、“０”が出力される。又、例え
ば、第１５ビット〜第１３ビットが“０”で、第１２ビ
ットが“１”であれば、同様に“３”が出力され、どち
らの場合も、シフト量を得ることができる。

【００６４】本実施例においては、レジスタの更新回数
が少ない処理手順、スタッフィングビットが拡張された
コードレジスタ、及び未確定画素の先読みによる処理の
二重化を行っているので、処理速度が非常に高速化する
ことができる。なお、これらの処理を組合せることな
く、単独で用いることも可能である。

【００６５】

【発明の効果】以上説明したとおり、本発明によれば、
処理速度を高速化して高速で復号することができ、従来
に比べて、数倍から数十倍の高速化を達成することがで
きる。

【図面の簡単な説明】

【図１】算術符号における確率数直線の例を示す線図

【図２】ビットスタッフィングの原理を説明する線図

【図３】従来の復号用レジスタの構成の例を示す線図

【図４】従来の復号化処理の基本的な手順を示す流れ図

【図５】同じく初期化ルーチンの例を示す流れ図

【図６】同じく符号バイト入力ルーチンの例を示す流れ
図

【図７】同じく確率評価テーブルの例を示す線図

【図８】同じくオージェンドとコード値の関係の例を示
す線図

【図９】同じく優勢シンボル（ＭＰＳ）入換ルーチンの
例を示す流れ図

【図１０】同じく劣勢シンボル（ＬＰＳ）入換ルーチン
の例を示す流れ図

【図１１】同じく正規化（リノーマライズ）ルーチンの
例を示す流れ図

【図１２】本発明に係る算術復号化処理装置の実施例の
処理手順の一部を示す流れ図

【図１３】図１２に続く処理手順の一部を示す流れ図

【図１４】図１３に続く処理手順の残りを示す流れ図

【図１５】前記処理手順における状態ＳＴの選択基準の
例を示す線図

【図１６】同じく優勢シンボルＭＰＳの選択基準の例を
示す線図

【図１７】同じく、分割されたオージェンドとコード値
の関係の一例を示す線図

【図１８】同じく、分割されたオージェンドとコード値
の関係の他の例を示す線図

【図１９】前記実施例で用いられているコードレジスタ
の構成、及び、そのシフト状態の例を示す線図

【図２０】同じく、隙間が最大で有効ビットが最小の場
合のコードレジスタの状態の例を示す線図

【図２１】前記実施例における各画素毎の処理手順の時
間的な関係の例を示すタイムチャート

【図２２】前記実施例の全体構成を示すブロック線図

【図２３】前記実施例の演算処理部の具体的な構成例を
示すブロック線図

【図２４】前記演算処理部のシフト量計算回路として用
いられるプライオリティエンコーダの論理を示す線図

【符号の説明】

Ａ…オージェンド値Ｃ…コード値ＳＣＤ…符号化ビットストリームデータＣＸ…文脈ＳＴ…状態Ｐｉｘ…画素ＬＳＺ…劣勢分割幅ＭＰＳ…優勢シンボルＬＰＳ…劣勢シンボルｐ、ｑ…レジスタｐｓ、ｑｓ…シフト量１０…演算処理部１６、２４…減算回路２２…シフト量計算回路２６…判別回路２８、３０、３２…マルチプレクサ４２…シフト回路４６…コードレジスタ制御回路５２…オージェンドレジスタ５４…メモリ５６…コードレジスタ６０…状態発生部７０…マルチプレクサ８０…確率推定部

Claims

【特許請求の範囲】

【請求項１】符号化すべきシンボル系列を、劣勢シンボ
ル及び優勢シンボルの出現確率に応じて分割した確率数
直線上にマッピングし、その位置に従って符号化するこ
とによって作成された算術符号を、前記確率数直線上で
の符号の範囲を示すオージェンド値を記憶するオージェ
ンドレジスタ、及び、同じく確率数直線上での符号の位
置を示すコード値を記憶するコードレジスタを用いて復
号化するための算術符号復号化装置において、先行するデータから、現在の文脈を生成する手段と、該文脈を指標として、状態及び現在の優勢シンボルを決
定する手段と、前記状態を指標として、リード・オンリー・メモリに記
憶された確率評価テーブルの値を読み出す手段と、該確率評価テーブルから読み出された確率に従ってオー
ジェンドを分割し、正規化する場合のシフト量、及び、
コード値の更新される可能性のある値を計算する手段
と、分割の結果、コード値が優劣どちらの領域に含まれ、ど
ちらの領域が大きいかを判別し、処理を振り分けて、デ
ータを生成する手段と、振り分けられた結果に応じて、予め計算しておいた前記
シフト量を用いてシフトを行い、オージェンドレジスタ
及びコードレジスタを更新する手段と、必要に応じて、ランダム・アクセス・メモリに記憶され
た状態や現在の優勢シンボルを更新する手段と、を備えたことを特徴とする算術符号復号化装置。
【請求項２】請求項１において、更に、実際にシフトした量を、コードレジスタの隙間の大きさ
に加算する手段と、該コードレジスタの隙間に次の符号を入れてビットスタ
ッフィングを行う手段とを備え、前記コードレジスタが、コード値に対応するビット長の
上位ビットと、シフト量に対応する有効ビット長に加え
て、前記隙間の最大量を収容可能なビット長の、拡張さ
れた下位ビットを含み、該下位ビットがスタッフィングビットとして使われるこ
とを特徴とする算術符号復号化装置。
【請求項３】符号化すべきシンボル系列を、劣勢シンボ
ル及び優勢シンボルの出現確率に応じて分割した確率数
直線上にマッピングし、その位置に従って符号化するこ
とによって作成された算術符号を、前記確率数直線上で
の符号の範囲を示すオージェンド値を記憶するオージェ
ンドレジスタ、及び、同じく確率数直線上での符号の位
置を示すコード値を記憶するコードレジスタを用いて復
号化するための算術符号復号化装置において、先行するデータの内、未確定のデータに依存した、複数
の文脈を生成する手段と、該複数の文脈のそれぞれを指標として、それぞれに対応
する状態及び現在の優勢シンボルの候補を生成する手段
と、先行するデータが確定した段階で、前記候補中から、実
際に用いる状態及び現在の優勢シンボルを決定する手段
と、を備えたことを特徴とする算術符号復号化装置。