JP3119025B2

JP3119025B2 - 符号化装置及び復号化装置

Info

Publication number: JP3119025B2
Application number: JP05094278A
Authority: JP
Inventors: 孝義瀬政
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1993-04-21
Filing date: 1993-04-21
Publication date: 2000-12-18
Anticipated expiration: 2015-12-18
Also published as: JPH06311045A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、符号化・復号化装置、
特に画像情報などの符号化・復号化装置に関する。

【０００２】

【従来の技術】マルコフ情報源の符号化においては、情
報源の出力シンボル系列に対し、既に符号化済みのシン
ボルである参照シンボルにより符号化対象シンボルを予
測し、その予測誤差信号を参照シンボルパターンにより
予測的中率に応じて各予測誤差信号をいくつかの群に分
類し、それぞれに適した符号を用いて符号化が行われて
いる。ここで、以下この予測誤差信号の作成のことを、
予測変換、群に分類することを統合、群の識別子のこと
を次数と呼ぶ。また、符号化されるべき予測誤差信号の
ことを予測誤差シンボルと呼ぶことにする。

【０００３】この予測変換及び次数選択方法としては、
情報源の統計的性質の局所的変化に対応するため、適応
処理を行う技術が特開平２−３０５２２５号公報に開示
されている。予測誤差シンボルの符号化手法について
は、減算型算術符号化法が、ＩＢＭ研究開発情報１９８
８年１１月、第３２巻第６号（ＩＢＭＪｏｕｒｎａｌ
ｏｆＲｅｓｅｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎ
ｔ，Ｖｏｌ．３２，Ｎｏ．６，Ｎｏｖ，１９８８）の
「Ｑ−コーダ対応２元演算符号器の基礎的原理の外観」
（Ａｎｏｖｅｒｖｉｅｗｏｆｔｈｅｂａｓｉｃ
ｐｒｉｎｃｉｐｌｅｏｆｔｈｅＱ−Ｃｏｄｅｒ
ａｄａｐｔｉｖｅ−ｂｉｎａｒｙａｒｉｔｈ−ｍｅ
ｔｉｃｃｏｄｅｒ）や特公平２−５８８１１号公報な
どに開示されている。これらはシンボル系列を数直線上
で０．０から１．０までの間に写像し、その座標を符号
語として符号化する数直線表示符号化方式の一種で、生
起したシンボルに応じて数直線を分割する際に、加減算
のみで行うものである。

【０００４】以下、図に従って従来の技術による予測変
換、統合及び符号化の過程を説明する。図１４は従来の
技術による符号化装置のブロック図であり、図１５はこ
の内の算術符号器の内部構成図である。簡単のため、情
報源は２値画像信号とし、参照シンボルは図１６の１２
画素、統合数は１６とする。

【０００５】図１４で、１は情報源シンボル１０１の系
列から参照シンボルを選択出力する参照シンボル作成
器、２はこの出力である参照シンボルパターン１０２よ
り対象シンボルの次数１０３と予測値１０４を出力する
次数・予測値メモリ、３は後述の次数・予測値レジスタ
８で選択・記憶された予測値１１２をもとに予測誤差シ
ンボル１０５を作成する予測変換器、４は後述の次数・
予測値レジスタ８で選択・記憶された次数１１１をもと
に算術符号の領域幅１０６を出力する領域幅テーブル、
５は算術符号器、６は次数・予測値メモリの読み出しと
更新を制御する次数・予測値制御回路、７は参照シンボ
ルパターン１０２から直前の符号化対象シンボルに対す
る参照シンボルパターンと符号化対象シンボルに対する
参照シンボルパターンが一致しているか否かを検出する
検出器、８は次数・予測値メモリ２からの次数１０３及
び予測値出力１０４ないしは、次数・予測値制御回路６
からの更新信号１０８を一時記憶する次数・予測値レジ
スタである。ここで、参照シンボル数を１２としたこと
より、次数・予測値テーブル（次数・予測値メモリの内
容）は図１７に示す様に２¹²種必要となる。次数値につ
いては統合を１６の群としたことからこれを識別するも
のとなる。ここでは予測的中率の高い程次数が高いもの
とする。

【０００６】図１５は、算術符号器５の内部構成を示す
ブロック構成図である。図において、５ａは数直線上の
有効領域Ａi を記憶するＡレジスタ、５ｂはＭＰＳ領域
幅１１４を計算する減算器、５ｃはＬＰＳの領域幅とＭ
ＰＳの領域幅を選択してＡレジスタ５ａの入力とする選
択器、５ｄは下界値座標１１６を記憶するＣレジスタ、
５ｅはＬＰＳの場合のＣレジスタ値１１７を計算する加
算器、５ｆはＣレジスタのオーバーフロー（シフトアウ
ト）信号であるキャリー出力１１８を一時記憶し、Ｃレ
ジスタ５ｄ更新時に桁上がりの処理を行い最終的な符号
系列を作成するための符号レジスタ、５ｇはこの算術符
号器５の動きを制御するタイミング制御回路である。

【０００７】次に図１４についてその動作を説明する。
情報源から発生したシンボル１０１（画像信号）は参照
シンボル作成器１でその系列が記憶されると共に、図１
６に示す１２画素の信号が選択されて参照シンボルパタ
ーン１０２として出力される。次数・予測値メモリ２で
はこれを基に図１７に示すテーブル内容から、対象シン
ボルの予測値１０４と次数１０３が出力され、次数１０
３情報は図１８に示す領域幅テーブル４で領域幅１０６
として変換出力される。一方、発生シンボル１０１は予
測変換器３で予測値１１２と排他的論理和がとられ予測
誤差シンボル１０５が作成される。この予測誤差シンボ
ルは符号化対象が２値画像信号であるため、予測一致の
場合に０（ＭＰＳ：ＭｏｒｅＰｒｏｂａｂｌｅＳｙ
ｍｂｏｌ）、不一致の場合に１（ＬＰＳ：ＬｅｓｓＰ
ｒｏｂａｂｌｅＳｙｍｂｏｌ）となる。

【０００８】算術符号器５では領域幅１０６信号を基
に、予測誤差シンボル１０５を数直線上に写像してゆき
符号化が実行される。すなわち、予測誤差シンボル系列
において第ｉ番目のシンボルをａ_i 、第ｉ時点でのＬＰ
Ｓの写像範囲（割当領域）をＳとすると、ＭＰＳ領域を
有効領域の下側に取るとすれば、第ｉ時点でのシンボル
系列の写像範囲（有効領域）Ａi とその下界値座標Ｃi
は、シンボルａ_i がＭＰＳのとき、Ａi ＝Ａi-1 − ＳＣi ＝Ｃi-1 シンボルａ_i がＬＰＳのときＡi ＝ＳＣi ＝Ｃi-1 ＋（Ａi-1 − Ｓ）とする。

【０００９】ここで有効領域Ａi が１／２以下になった
場合には、演算制度を上げるため２のべき乗倍する。こ
のとき座標Ｃi のオーバーフロー（小数点以上の部分）
分が符号ビット系列として出力される。以下このべき乗
処理を正規化と呼ぶ。Ａi 更新値＝Ａi ＊２^m （１／２＜
Ａi 更新値≦１）Ｃi 更新値＝Ｃi ＊２^m

【００１０】算術符号に於いては，ＳをＬＰＳの出現確
率（＝予測誤り確率）とすることで、情報源エントロピ
に極めて近い高効率の符号化ができることが知られてい
る。よって、次数に対応した予測的中率に適したＳ値を
選択することで上記処理により算術符号化を行うことが
できる。図１８は次数と領域幅Ｓとの対応表の一例であ
る。表中の値は、上記式中の数値を２¹⁶倍したものを記
してある。この例では、数直線上の領域計算は１６ビッ
ト精度で行うものであり、Ａレジスタ、Ｃレジスタはそ
れぞれ小数以下１６ビットの構成となる。

【００１１】次に予測及び統合の適応処理について説明
する。この適応処理方法としては、出力シンボル系列か
ら連続するＭＰＳとＬＰＳの数を計数して制御する方式
と、上記正規化が生起したときのシンボルがＭＰＳかＬ
ＰＳによって制御する方式がある。ここでは後者の方式
を例にとって説明する。次数・予測値制御回路６は正規
化時に予測変換器３の出力シンボルがＭＰＳあるいはＬ
ＰＳであるかを判定する。

【００１２】ＬＰＳの場合次数・予測値メモリ２において、その時の参照シンボル
パターンに対応する次数の値を１だけ減算する。たとえ
ば、図１７（ａ）に示すように符号化対象シンボルＸの
参照シンボルパターンＡ〜Ｌに対する次数が４、予測値
が１であった場合、図１７（ｂ）に示すように、次数を
３にする。これは、当該参照シンボル状態に於ける予測
が外れたため、予測の的中度を示す次数を下げることに
よって、現在の符号化対象となっている情報源に対し、
次数・予測値を適応させる動作である。次数が最低次数
に達しそれ以上次数を減じることが出来なくなると、予
測値を反転させる。この動作により的中率が極端に悪い
予測値は書き換えられる。

【００１３】ＭＰＳの場合次数・予測値メモリ２において、その時の参照シンボル
パターンに対応する次数の値を１だけ加算する。たとえ
ば、図１７（ａ）に示すように符号化対象シンボルＸの
参照シンボルパターンＡ〜Ｌに対する次数が４であった
場合、図１７（ｃ）に示すように、次数を５にする。こ
れは、当該参照シンボル状態に於ける予測が的中したた
め、予測の的中度を示す次数を上げることによって、現
在の符号化対象となっている情報源に対し、次数・予測
値を適応させる動作である。次数がすでに最高次数に達
している場合には加算は実行されない。この動作により
予測が極めてよく的中する場合には、次数を上げること
によりＳ値が小さくなり、算術符号器５から出力される
符号量を抑えることができる。

【００１４】以上の適応処理の動作により次数・予測値
制御回路６は、情報源の性質に追従して次数・予測値テ
ーブルを書き換えてゆき、高い符号化効率による算術符
号化が実現できる。

【００１５】ここでこの符号化装置の１シンボル毎の処
理動作を図１９を用いて詳述する。図１９においてＣ
１、Ｃ２、Ｃ３、・・・はシステムクロック１周期を示
している。また、図において＃１、＃２、＃３・・・は
符号化する対象シンボルを示している。ただし、図１９
の中の＃１、＃２、＃３は対象シンボルそのものを意味
するのではなく、図中左側に記載された各種パターンや
出力が対象シンボルに対応するものであることを示して
いる。例えば、対象シンボルパターン１０２において＃
１、＃２、＃３・・・とあるのは対象シンボル＃１に対
応する参照シンボルパターンの出力を示しており、同様
に＃２は対象シンボル＃２に対応する参照シンボルパタ
ーンの出力を示している。

【００１６】図１９に示すように、システムクロックＣ
１において情報源シンボル１０１を入力し、参照シンボ
ル作成器１から参照シンボルパターン１０２を出力す
る。同時にシステムクロックＣ１において、次数・予測
値メモリ２から次数１０３及び予測値１０４を出力す
る。また、システムクロックＣ２において、次数・予測
値レジスタ８から当該符号化対象シンボルの次数信号１
１１及び予測値信号１１２が出力され、次数・予測値メ
モリ２において次の符号化対象シンボルに対する次数１
０３及び予測値１０４をシステムクロック１周期を用い
て読み出す。また、システムクロックＣ３においては、
算術符号器５により当該シンボル符号化の為の出力が行
われ、ＡレジスタとＣレジスタからの符号の出力が行わ
れるのと平行して、次の符号化対象シンボルの次数信号
１１１及び予測値信号１１２が次数・予測値レジスタ８
から出力され、また、更に次の符号化対象シンボルに対
する次数１０３及び予測値１０４を、次数・予測値メモ
リ２から読み出す。このように符号化装置は、処理をパ
イプライン的に行うように構成されている。

【００１７】次に、対象シンボルを符号化した場合に正
規化及び次数・予測値の更新が無い場合と、有る場合に
ついて説明する。（１）正規化及び次数・予測値の更新がない場合例えば、図１９の＃１、＃３、＃４、＃６の場合のよう
に、上記領域と座標の演算後、次符号化対象シンボルの
領域・座標演算に移る。（２）正規化及び次数・予測値の更新がある場合例えば、図１９の＃２、＃５の場合のように、上記領域
と座標の演算を１クロックで行った後、以下の更新・正
規化を行う。

【００１８】次数・予測値メモリ２の内容の更新は、検
出器７から出力される当該シンボルに対する参照パター
ン１０９（参照シンボルパターン１０２を１シンボル分
遅らせたもの）、次数・予測値制御回路６からの更新信
号１０８をもとに行う。この時、参照シンボルパターン
１０２（次の符号化対象シンボルに対する信号）と当該
符号化対象シンボルに対する参照パターン１０９が一致
する場合は、次数・予測値レジスタの内容についても更
新を行う。これら内容更新はシステムクロック１周期で
処理する。

【００１９】正規化についてはこの更新動作と並行して
左シフトにより１ビット当たり１システムクロック周期
で行う。この正規化及び次数・予測値の更新がある場合
の具体例について説明する。システムクロックＣ３にお
いて、符号化対象シンボル＃２に対する領域・座標演算
が行われる。演算の結果有効領域が１／２以下なった場
合には正規化処理が行われる。同様に、前述した適応処
理が行われる。即ち、正規化処理を行う為にシステムク
ロックＣ４においてＡレジスタとＣレジスタを１ビット
シフトし、符号が出力される。また、適応処理について
は、図１７（ｂ）、（ｃ）に示したように、符号化対象
シンボル＃２が参照した参照シンボルパターンに対応す
る次数が変更される。あるいは予測値が変更される。こ
のようにして次数・予測値メモリ２の符号化対象シンボ
ル＃２が参照した次数及び予測値が更新されたものを図
１９においては＃２´として示している。

【００２０】そしてこの両動作の完了を待って、次の符
号化対象シンボルの領域・座標演算に移る。システムク
ロックＣ５においては、次の符号化対象シンボルの演算
が行われることになるが、次の符号化対象シンボル＃３
に用いられる次数及び予測値は、符号化対象シンボル＃
２と符号化対象シンボル＃３の参照シンボルパターンが
不一致の場合には、符号化対象シンボル＃３の参照シン
ボルパターンから求められた次数と予測値を用いる。一
方符号化対象シンボル＃２と符号化対象シンボル＃３の
参照シンボルパターンが一致した場合には、前述した適
応処理により更新された次数及び予測値（図中、次数・
予測値メモリ出力の＃２´で示す）を用いる。

【００２１】また、符号化対象シンボル＃５の場合には
システムクロックＣ７の演算の結果、正規化処理の為に
２ビットシフトが行われる為、システムクロックＣ８と
Ｃ９において、２ビットシフトの正規化処理が行われ
る。また、次に符号化される符号化対象シンボル＃６の
次数及び予測値についても、符号化対象シンボル＃５と
符号化対象シンボル＃６の参照シンボルパターンが不一
致の場合には、そのままシステムクロックＣ７で得られ
た次数と予測値をシステムクロックＣ１０において用い
ることになるが、符号化対象シンボル＃５と符号化対象
シンボル＃６の参照シンボルパターンが一致する場合に
は、符号化対象シンボル＃５の適応処理により、次数・
予測値メモリ２の内容の更新が行われているため、更新
後の次数及び予測値（図中、次数・予測値メモリ出力の
＃５´で示す）をシステムクロックＣ１０において用い
る。以上のように正規化処理を行い、１ビットの符号が
出力される度に追加のシステムクロック１周期を用いる
ことになる。この追加のシステムクロックの数は符号ビ
ット数と等しくなる。

【００２２】以上の説明より明らかなようにこの符号化
装置の符号化処理時間Ｔは、全シンボル数をＮａ、符号
ビット数をＮｃとすると、システムクロックが１０ＭＨ
Ｚの場合、Ｔ＝１００＋１００＊Ｎａ＋１００＊Ｎｃ（ｎｓｅ
ｃ）となる。上の式の第１項目の１００は図１９のシステム
クロックＣ１の時間を示している。また、第２項目の１
００×Ｎａは１シンボル当たり１００ｎｓｅｃかかるた
め全シンボルを処理する時間を示している。また、第３
項目の１００×Ｎｃは図１９中の正規化処理、即ち符号
ビットを出力する処理に要する追加の時間を示してい
る。例えば、図１９においてはシステムクロックＣ４と
Ｃ８とＣ９の３回のシフト処理が行われている為、３つ
の符号ビットが出力されており、この例では１００×３
＝３００ｎｓｅｃとなる。そこで、標準的な解像度水平
８画素／ｍｍ、垂直７．７ライン／ｍｍのＡ４判原稿と
して、圧縮率を３０と仮定するとＮａ＝１７２８＊２３７６Ｎｃ＝１７２８＊２３７６＊（１／３０）となり、符号化処理時間Ｔは約０．４秒となる。

【００２３】

【発明が解決しようとする課題】以上のように、従来の
装置に於いては、全シンボルにおいて参照シンボルパタ
ーンの作成と、次数・予測値テーブルの検索、数直線の
領域計算を行うが、条件により更に、次数・予測値テー
ブルの更新、正規化を行うこととなり、画像信号の性質
により符号化・復号処理が遅くなるという問題点があっ
た。特に組織的ディザ画像や誤差拡散法により２値化さ
れた疑似中間調画像などではＡ４判原稿を水平８画素／
ｍｍ、垂直７．７ライン／ｍｍの解像度で符号化する場
合０．７〜１秒程度と、通常の文字画像などに比べ処理
時間が２倍程度となっている。

【００２４】この発明は上記のような問題点を解消する
ためになされたもので、大幅な処理高速化が可能な符号
化・復号化装置を得ることを目的にしている。

【００２５】

【課題を解決するための手段】この第１の発明に係わる
符号化装置は、情報源の出力シンボル系列からそのシン
ボル出現確率を推定して、それに応じた有効領域分割を
行ってこのシンボル系列を算術符号化する際に、数直線
上の有効領域を記憶する第１のレジスタと、ＭＰＳの領
域幅を計算する第１の演算手段と、数直線上の有効領域
の境界値を記憶する第２のレジスタと、ＬＰＳに対応す
る領域とＭＰＳの領域の境界値を計算する第２の演算手
段と、発生シンボルがＭＰＳかＬＰＳかによって新たな
有効領域幅を選択する第１の選択手段と、同じく新たな
有効領域の境界値を選択する第２の選択手段と、第１の
選択手段出力を受けて最上位の“１”あるいは“０”の
位置を検出するビット位置検出手段と、この検出手段出
力に応じて第１の選択手段出力をシフトして第１のレジ
スタ入力値を出力する第１のシフタと、同じく第２の選
択手段出力を受けて第２のレジスタ入力値及び第２のレ
ジスタからのオーバーフローしたデータを出力する第２
のシフタと、この第２のシフタからの第２のレジスタか
らオーバーフローしたデータ出力を受けて符号出力を生
成する符号生成手段を備えたものである。

【００２６】この第２の発明に係わる符号化装置は、Ｆ
ＩＦＯメモリを有する符号生成手段を備えたものであ
る。

【００２７】この第３の発明に係わる復号化装置は、情
報源の出力シンボル系列からそのシンボル出現確率を推
定して、それに応じた有効領域分割を行ってこのシンボ
ル系列を算術符号化した符号ビット系列を復号する際
に、数直線上の有効領域を記憶する第１のレジスタと、
発生頻度が大きいと想定されるシンボル（優性シンボ
ル：ＭＰＳ）の領域幅を計算する第１の演算手段と、数
直線上の有効領域の境界値を記憶する第２のレジスタ
と、第２のレジスタ出力から発生頻度が小さいと想定さ
れるシンボル（劣性シンボル：ＬＰＳ）の領域とＭＰＳ
領域との境界値を減算して当該シンボルがＭＰＳかＬＰ
Ｓかを判定する第２の演算手段と、当該シンボルがＭＰ
ＳかＬＰＳかによって新たな有効領域幅を選択する第１
の選択手段と、同じく新たな有効領域の境界値を選択す
る第２の選択手段と、第１の選択手段出力を受けて最上
位の“１”あるいは“０”の位置を検出するビット位置
検出手段と、この検出手段出力に応じて第１の選択手段
出力をシフトして第１のレジスタ入力値として出力する
第１のシフタと、同じく第２の選択手段出力及び後述の
符号読み出し手段出力を受けて第２のレジスタ入力値を
出力する第２のシフタと、入力した符号データ系列を受
けて、必要なビット数の符号系列を第２のレジスタの下
位ビット信号として第２のシフタに出力する符号読み出
し手段を備えたものである。

【００２８】この第４の発明に係わる復号化装置は、Ｆ
ＩＦＯメモリを有する符号読み出し手段を備えたもので
ある。

【００２９】この第５の発明に係わる符号化装置は、情
報源の出力シンボル系列の予め定めておいた位置の複数
の参照シンボルの状態から符号化対象シンボルの予測を
行ってその予測誤差信号を符号化する際に、参照シンボ
ルの各状態における上記符号化対象シンボルの予測値と
予測一致率によって分類される群の識別子である次数と
を記憶する読みだし書き込み同時動作可能なメモリと、
符号化対象シンボルが予測一致しているか否かを検査し
その結果に応じて該参照シンボル状態における予測値及
び次数を書き換える次数・予測値制御回路と、このメモ
リから読み出された当該符号化対象シンボルの予測値及
び次数信号、ないしは、直前の符号化対象シンボルに対
する、書き換え処理後の予測値及び次数を記憶する次数
・予測値レジスタと、符号化対象シンボルに対する参照
シンボル状態と直前のシンボルに対する参照シンボル状
態とが一致しているか否かを検出する検出器と、上記次
数・予測値レジスタより出力された予測値・次数情報を
もとに予測誤差信号を符号化する算術符号器とを備えた
ものである。

【００３０】この第６の発明に係わる復号化装置は、情
報源の出力シンボル系列の予め定めておいた位置の複数
の参照シンボルの状態から復号化対象シンボルの予測を
行ってその予測誤差信号を符号化した符号ビット系列を
復号化する際に、参照シンボルの状態から復号化対象シ
ンボルの予測値と予測一致率によって分類される群の識
別子である次数とを記憶する同時書き込み読みだし可能
なメモリと、上記復号化対象シンボルが予測一致してい
るか否かを検査しその結果に応じて該参照シンボル状態
における予測値及び次数を書き換える次数・予測値制御
回路と、先行する復号化対象シンボルの再生信号値によ
って、複数個の状態に対するメモリ出力のうちの１組の
予測値及び次数を選択出力する選択器と、このメモリか
らの予測値及び次数、ないしは、直前の復号化対象シン
ボルに対する更新後の予測値及び次数を記憶するレジス
タと、復号化対象シンボルに対する参照シンボル状態と
直前のシンボルに対する参照シンボル状態とが一致して
いるか否かを検出する検出器と、選択された予測値・次
数情報をもとに符号ビット系列を復号化する算術復号器
とを備えたものである。

【００３１】

【作用】この第１の発明に係わる符号化装置は、第１及
び第２のシフタを用いて正規化動作を高速化することに
より、符号化速度を向上させるものである。

【００３２】この第２の発明に係わる符号化装置は、符
号生成手段にＦＩＦＯを用いて符号出力時の緩衝を行っ
て符号出力に関わる符号化動作の中断を減少させること
により、符号化速度を向上させるものである。

【００３３】この第３の発明に係わる復号化装置は、第
１及び第２のシフタを用いて正規化動作を高速化するこ
とにより、復号化速度を向上させるものである。

【００３４】この第４の発明に係わる復号化装置は、符
号読み出し手段にＦＩＦＯを用いて符号入力時の緩衝を
行って符号入力に関わる復号化動作の中断を減少させる
ことにより、復号化速度を向上させるものである。

【００３５】この第５の発明に係わる符号化装置は、次
数・予測値格納用のメモリを複数ポートの構成とし、読
みだし書き込み動作を同時に行わせることにより、符号
化速度を向上させるものである。

【００３６】この第６の発明に係わる復号化装置は、次
数・予測値格納用のメモリを複数ポートの構成とし、読
みだし書き込み動作を同時に行わせることにより、復号
化速度を向上させるものである。

【００３７】

【実施例】実施例１．以下、本発明を図示実施例の基づ
いて説明する。本実施例の符号化装置ブロック構成は、
図１４の従来の装置と同様であるが、相違点としては、
次数・予測値メモリ２が高速なものとなり、システムク
ロックの前半の周期で書き込み動作が可能であり、後半
の周期で読み出しが可能なものとなっている点及び算術
符号器５の内部構成が異なっている点である。

【００３８】図１は本実施例に於ける算術符号器５の内
部構成を示すブロック構成図で、図１５の従来の符号化
装置の算術符号器との相違点は、ＬＰＳ領域幅とＭＰＳ
領域幅の選択器５ｃの出力を受けて最上位の１の位置を
検出するビット位置検出器５ｈと、この出力である正規
化ビット数信号１２０に応じたビット数だけ選択器５ｃ
の出力を左シフトしてＡレジスタ５ａに入力１２１する
第１のバレルシフタ５ｉと、Ｃレジスタ５ｄ出力１１６
とＬＰＳの場合のＣレジスタ値１１７を切り替える選択
器５ｊと、正規化ビット数信号１２０に応じたビット数
だけ選択器５ｊの出力１２２を左シフトしてオーバーフ
ロー分１２４を符号レジスタ５ｆに出力するとともに下
位ビット１２３をＣレジスタ５ｄに入力する第２のバレ
ルシフタ５ｋが付加されたこと、及び、符号レジスタ５
ｆの入力として従来の１ビットのキャリ出力に替えて、
第２のバレルシフタ５ｋからのオーバーフロー信号１２
４及びビット位置検出器５ｈからの正規化ビット数信号
１２０が入力されていることである。

【００３９】図２は符号レジスタ５ｆの内部構成を示す
図で、５ｆ１はオーバーフロー信号を所定ビット数だけ
シフトするためのバレルシフタ、５ｆ２は正規化ビット
数信号１２０を受け、オーバーフロ信号をシフト加算す
るビット数１２６を制御する桁制御回路、５ｆ３はオー
バーフロ信号を先行したビット系列の下位に付加・加算
するための加算器、５ｆ４はオーバーフロー信号系列を
バイトに詰めるためのバイトパック用レジスタ、５ｆ５
はバイトパック用レジスタ５ｆ４からの桁上がり１３０
を検出するオーバーフロー検出器、５ｆ６はバイトパッ
ク用レジスタ５ｆ４の出力１２９から１６進数で“０ｘ
ｆｆ”を検出・計数するｆｆパターン検出・計数器、５
ｆ７はバイトパック用レジスタ５ｆ４からの出力１２９
を一時記憶するとともに、オーバーフロー検出器５ｆ５
からのオーバーフローがあった場合には記憶しているデ
ータに１を加算するバッファレジスタ、５ｆ８は１６進
数で“０ｘｆｆ”を出力するｆｆデータ発生器、５ｆ９
は同じく“０ｘ００”を出力する００データ発生器、５
ｆ１０はバッファレジスタ５ｆ７とｆｆデータ発生器５
ｆ８、００データ発生器５ｆ９からのデータを選択して
符号データ系列をつくるための選択器である。

【００４０】次に、本実施例の動作について図３を用い
て説明する。図３において従来と大きく異なる点は、次
数・予測値メモリ２が高速になっているため次数・予測
値メモリからの読みだしがシステムクロックの後半で可
能な点である。例えば、符号化対象シンボル＃１を次数
・予測値メモリ２から読み出す場合には、システムクロ
ックＣ１の後半を用いて読み出す。同様に符号化対象シ
ンボル＃２を読み出す場合も、システムクロックＣ２の
後半部分を用いて読み出す。もし、演算の結果、正規化
処理と次数・予測値の変更処理が生じた場合にはシステ
ムクロックの前半部分を用いて次数・予測値メモリへの
更新処理を行うことが可能である。例えば、システムク
ロックＣ３において符号化対象シンボル＃２の演算処理
を行った結果、１ビットシフトの正規化処理が生じ、次
数・予測値の更新が生じた場合には、システムクロック
Ｃ４の前半部分を用いて次数・予測値メモリ２に対して
更新処理を行うことが可能である。また同様にシステム
クロックＣ６において、符号化対象シンボル＃５の演算
処理の結果２ビットシフトの正規化処理及び次数・予測
値の更新処理が発生した場合にはシステムクロックＣ７
の前半部分において次数・予測値メモリ２に対する更新
処理を行うことが可能である。今、次数・予測値レジス
タ８から当該符号化対象シンボルの次数信号１１１及び
予測値信号１１２が出力されたとすると、以下に示す当
該シンボル符号化のための処理を行うのと並行して、次
数・予測値メモリ２において次の符号化対象シンボルに
対する次数及び予測値をシステムクロックの後半の周期
を用いて読み出す。（１）正規化及び次数・予測値の更新がない場合例えば図３の＃１、＃３、＃４、＃６の場合のように、
上記領域と座標の演算後、次符号化対象シンボルの領域
・座標演算に移る。（２）正規化と次数・予測値の更新がある場合例えば図３の＃２、＃５の場合ように、上記領域及び座
標の演算及び正規化までの処理を１クロックで行った
後、次のシンボルの処理の移る。

【００４１】バレルシフタは複数ビットのシフト処理を
１クロックで行うことが可能なため、複数ビットのシフ
ト処理を行う正規化処理の場合でも１クロックで正規化
処理を終了することができる。この正規化処理の動作に
ついては後述する。次数・予測値メモリ２の内容の更新
は、次数・予測値制御回路６及び検出器７により、次の
シンボルの領域と座標計算を行っているサイクルのシス
テムクロック前半の周期で行われる。

【００４２】次に図３を用いて具体的動作について説明
する。システムクロックＣ３において、符号化対象シン
ボル＃２の演算処理が行われた結果、正規化処理及び次
数・予測値更新処理（適応処理）が有りと判断された場
合には、システムクロックＣ４の前半部分を用いて次数
・予測値メモリへの更新処理が行われる。システムクロ
ックＣ４においては符号化対象シンボル＃３の次数及び
予測値を決定するに当たり、符号化対象シンボル＃２と
符号化対象シンボル＃３の参照シンボルパターンが一致
する場合としない場合が考えられる。符号化対象シンボ
ル＃２と符号化対象シンボル＃３の参照シンボルパター
ンが不一致の場合には、システムクロックＣ３の時点で
次数・予測値メモリ２から読み出された符号化対象シン
ボル＃３の次数及び予測値を、システムクロックＣ４に
おいて、符号化対象シンボル＃３の次数及び予測値とし
て出力する。一方、符号化対象シンボル＃２と符号化対
象シンボル＃３の参照シンボルパターンが一致した場合
には、符号化対象シンボル＃２の演算処理後に正規化処
理及び次数・予測値の更新処理が発生しているため、更
新後の次数及び予測値を用いなければならない。此の次
数及び予測値の更新処理はシステムクロックＣ４の前半
部分で行われている。従って次数・予測値レジスタ８か
らの次数及び予測値は、システムクロックＣ４の前半部
分で更新された次数及び予測値を符号化対象シンボルの
次数及び予測値として用いる。システムクロックＣ４の
前半部分における次数・予測値メモリ２への更新と同時
に次数・予測値レジスタ８の更新も並行して行うことに
より、システムクロックＣ４の前半部分で次数・予測値
レジスタ８の符号化対象シンボル＃２の次数及び予測値
も同時に更新することができる。システムクロックＣ４
においては、次数・予測値レジスタ８の更新された次数
及び予測値を符号化対象シンボル＃３の次数及び予測値
として用いる事により、新たに更新された次数及び予測
値を正しく用いることが出来る。

【００４３】また、符号化対象シンボル＃５において、
２ビットの正規化処理及び次数・予測値の変更処理が生
じた場合にも前述した符号化対象シンボル＃２と同様な
正規化処理及び次数・予測値の更新処理が行われる。さ
らに符号化対象シンボル＃６に対する次数及び予測値を
決定する場合にも前述したように符号化対象シンボル＃
２と＃３の参照シンボルパターンの一致または不一致に
より、一致する場合には更新された新たな次数及び予測
値を用い、不一致の場合には符号化対象シンボル＃６の
ために読み出された次数及び予測値がそのまま用いられ
る。

【００４４】以上のように、この実施例においては次数
・予測値メモリ２が従来に比べて高速なものになったお
かげで、システムクロックの前半と後半を用いて書き込
み及び読みだしが行うことが出来ることが大きな特徴で
ある。また、正規化時のシフト処理においてバレルシフ
タを用いて複数ビットの処理が有る場合でも１クロック
で行えることが大きな特徴である。このように従来の装
置においてはシフト処理を行うためにシステムクロック
を必要としていたのに対して、この実施例ではシフトビ
ット数が複数の場合でも１クロックで終了することが可
能であり、正規化処理の為に他のパイプライン的に構成
された処理を遅延させる必要が無くなる。また正規化処
理及び次数・予測値の更新処理がパイプライン的に構成
された装置の算術符号器という後段の部分においてなさ
れるため、次数及び予測値が更新されるかどうかが判断
され、その更新された新たな次数及び予測値を次に符号
化する符号化対象シンボルに反映させるために次数・予
測値メモリ２を高速にアクセス可能にしたものである。

【００４５】次に図１に基づいて算術符号器５の動作に
ついて説明する。算術符号器５は領域幅１０６と予測誤
差シンボル１０５を入力して符号１０７を出力する。予
測誤差シンボル１０５はＬＰＳ（１）／ＭＰＳ（０）の
いずれかであり、ＬＰＳの場合に選択器５ｃはＳ１とＳ
３を接続する。及び選択器５ｊはＳ６とＳ４を選択す
る。一方、予測誤差シンボル１０５がＭＰＳの場合には
選択器５ｃはＳ２とＳ３を接続する。また選択器５ｊは
Ｓ５とＳ６を接続する。選択器５ｃがＳ１とＳ３を接続
した場合には領域幅１０６を入力し、第１のバレルシフ
タ５ｉへ出力する。一方Ｓ２とＳ３が接続された場合に
はＡレジスタ５ａにある領域幅から領域幅１０６を減算
した残りのＭＰＳ領域幅１１４を第１のバレルシフタ５
ｉへ出力する。

【００４６】ビット位置検出器５ｈは選択器からの出力
１１５を監視し、出力１１５の最上位ビット位置を検出
する。例えば、ビット“１”が２桁目に検出された場合
には正規化ビット数信号として１を出力する。またビッ
ト１が３桁目に検出された場合には正規化ビット数信号
として２を出力する。正規化ビット数信号が１を表わす
場合にはシフト数が１であることを示し、正規化ビット
数信号が２である場合にはシフト数が２であることを示
している。この正規化ビット数信号１２０は第１のバレ
ルシフタ５ｉと第２のバレルシフタ５ｋに入力され、選
択器５ｃ及び選択器５ｊから出力される信号をシフトす
る。このようにして正規化処理が１クロックで終了す
る。選択器５ｊにおいてＳ４とＳ６が接続された場合に
は、Ｃレジスタ５ｄにある値にＭＰＳ領域幅１１４を加
算して新たなＬＰＳＣレジスタ値を計算し、これを第２
のバレルシフタ５ｋに出力する。一方選択器５ｊがＳ５
とＳ６を接続した場合にはＣレジスタ５ｄから出力され
るＣレジスタ出力１１６を選択して、第２のバレルシフ
タ５ｋに出力する。

【００４７】次に図２を用いて符号レジスタ５ｆの動作
について説明する。符号レジスタ５ｆは第２のバレルシ
フタ５ｋからのオーバーフロー信号１２４を入力し、符
号１０７を出力する。このオーバーフロー信号１２４か
ら符号１０７を出力するにあたっては正規化ビット信号
１２０を入力すると共に、符号化停止信号１２５を出力
し、符号化のタイミングを調整する。前述したように、
オーバーフロー信号１２４が２ビット入力される場合に
は正規化ビット数信号１２０はシフトすべきビット数と
して２を入力する。桁制御回路５ｆ２は正規化ビット数
信号１２０の値に基づいてバレルシフタ５ｆ１をシフト
させオーバーフロー信号１２４を取り込む。もしバレル
シフタ５ｆ１が正規化ビット数信号１２０に基づくビッ
ト数だけシフトすることができない場合には、桁制御回
路５ｆ２は符号化停止信号１２５を出力する。符号化停
止信号１２５は図１に示すタイミング制御回路５ｇに入
力される。タイミング制御回路５ｇは符号化停止信号１
２５が入力されると算術符号器５の符号化動作を一時停
止させる。符号化停止信号１２５を出力した桁制御回路
は、算術符号器５が次の動作を停止している間にバレル
シフタ５ｆ１の残りのシフト動作を行う事により、符号
レジスタ５ｆ内において次のオーバーフロー信号１２４
を入力することが可能になるまで符号レジスタ５ｆの動
作を続行する。

【００４８】正規化時の符号レジスタ５ｆの動作は、以
下の通りである。（ａ）Ｃレジスタ５ｄからのオーバーフロ信号１２４
は、既に処理済みの直前のオーバーフロー信号の直下の
位置に加算する。ただしオーバーフロ信号が正規化ビッ
ト数より大きい場合（最大１ビットのみ）には、最上位
のビットは直前のオーバーフロー信号の最下位のビット
に加算されることとなる。（ｂ）オーバーフロー信号がバイトパック用レジスタに
一度に加算できないときは下記（ｃ）のバイトパック用
レジスタからの出力を行って、最下位ビットまでバイト
パック用レジスタに格納されるまで同様の加算動作を繰
り返す。（ｃ）バイトパック用レジスタ５ｆ４にバイト境界まで
データが格納されると、ｆｆパターン検出・計数器５ｆ
６により以下の処理を行う。（ｃ−１）バイトパック用レジスタ５ｆ４のデータが
“０ｘｆｆ”を越える場合（オーバーフロー検出器により検出される）すでに格納
済みのバッファレジスタ５ｆ７の内容に１を加算し、そ
れを選択器５ｆ１０を介して符号出力としたのち、“０
ｘｆｆ”の計数値の数分だけ００データ発生器５ｆ９に
より“０ｘ００”を符号出力する。その後バイトパック
用レジスタ５ｆ４の下位８ビットを読み出し、バッファ
レジスタ５ｆ７に出力する。（ｃ−２）バイトパック用レジスタ５ｆ４のデータが
“０ｘｆｆ”の場合 “０ｘｆｆ”の計数値を１加算する。（ｃ−３）バイトパック用レジスタ５ｆ４のデータが
“０ｘｆｆ”未満の場合すでに格納済みのバッファレジ
スタ５ｆ７の内容を選択器５ｆ１０を介して符号出力と
したのち、“０ｘｆｆ”の計数値の数分だけｆｆデータ
発生器５ｆ８により“０ｘｆｆ”を符号出力する。その
後バイトパック用レジスタ５ｆ４を読み出し、バッファ
レジスタ５ｆ７に出力する。これらの処理により、いわゆるｐｕｒｅｏｕｔｐｕｔ
の符号生成処理が行われることになる。

【００４９】以上の説明より明らかなようにこの符号化
装置の符号化処理時間Ｔは、全シンボル数をＮａ、符号
ビット数をＮｃとすると、システムクロックが１０ＭＨ
Ｚの場合、Ｔ＝１００＋１００＊Ｎａ＋α （ｎｓｅ
ｃ）となる。ここでαはＣレジスタ５ｄから送られてくる複
数ビットのオーバーフロー信号１２４を符号レジスタ５
ｆにおいて、８ビットに詰めて出力する間に次のオーバ
ーフロー信号が生成されたためつぎの符号化シンボルの
領域計算が待たされたことによる時間である。オーバフ
ロー信号１２４が８ビットを越えた場合に発生すること
となる。そこで標準的な解像度水平８画素／ｍｍ、垂直
７．７ライン／ｍｍのＡ４判原稿として、圧縮率を３０
と仮定すると、符号化処理時間Ｔは約０．４秒、誤差拡
散画像のような極めて複雑な画像で圧縮率が１．５でも
同じく約０．４秒となる。ここでαは α＝１００＊Ｎｃ＊（１／１６）とした。

【００５０】これに対し、図１４の従来の装置では、圧
縮率が１．５とすると約０．７秒となる。

【００５１】実施例２．次に、図４は本発明の他の実施
例である符号化装置の算術符号器のブロック構成を示し
ている。本実施例と図１の実施例との違いは、符号レジ
スタ５ｆの初段にオーバーフロー信号１２４及び正規化
ビット数信号１２０を記憶するＦＩＦＯが付加されてい
る点である。

【００５２】算術符号化によれば、情報源の性質に合わ
せた符号化が行われるため、過渡的な部分をのぞき圧縮
率が１を越えること、及び、符号レジスタ５ｆの処理は
（時間遅れを除けば）１クロックで８ビット分の処理が
できることから１６段程度のＦＩＦＯにより、領域計算
の停止は不要になり（すなわちα＝０となり）ディジタ
ル複写機などで必要となる超高速・一定速度の符号器が
実現できる。

【００５３】実施例３．次に、図５は本発明の他の実施
例である符号化装置のブロック構成を示している。図
で、上記した実施例でのブロック図との違いは、次数・
予測値メモリ２が２ポート構成になったこと、及び検出
器７の替わりに参照シンボルパターン１０２と更新用参
照シンボルパターン信号１０９とを監視し、更新信号１
０８が発生した時に、両パターンが一致した場合は次の
シンボルに対する次数・予測値メモリのアクセスを中止
するための２ポート制御部９、アクセス禁止回路１０が
付加されたことである。

【００５４】図６に本実施例での符号化動作例を示す。
ここで算術符号器は図１のものを用いるものとした。ア
クセス速度の１／２の２ポートメモリにより上記同様の
処理が可能となる。

【００５５】次にこの具体例について図６を用いて説明
する。システムクロックＣ３において符号化対象シンボ
ル＃２の演算処理の結果、正規化処理及び次数・予測値
更新処理（適応処理）が行われる。システムクロックＣ
４においては次数・予測値の更新の為に符号化対象シン
ボル＃２に用いた次数及び予測値を更新しようとする。
次数・予測値メモリ２への書き込み動作は、同じくシス
テムクロックＣ４における次数・予測値メモリの符号化
対象シンボル＃４の為の読みだしと並行して行われる。
ただし、符号化対象シンボル＃２と符号化対象シンボル
＃４の参照シンボルパターンが同一の場合には、次数・
予測値メモリ２への書き込みと読み込みが競合するた
め、次数・予測値メモリ２が２ポートメモリである場合
でもいずれか一方のアクセスを禁止しなければならな
い。２ポート制御部９は符号化対象シンボル＃２と符号
化対象シンボル＃４の参照シンボルパターンが同一の場
合には、アクセス禁止回路１０に対してアクセス禁止を
命令する。アクセス禁止回路１０は符号化対象シンボル
＃４に対する次数・予測値メモリの読みだしを禁止す
る。符号化対象シンボル＃４に対する次数及び予測値メ
モリの読みだしが禁止された場合であっても、符号化対
象シンボル＃２による次数及び予測値の更新が行われる
ため次数・予測値メモリ２と次数・予測値レジスタ８の
符号化対象シンボル＃２（即ち符号化対象シンボル＃
４）の参照シンボルパターンは更新された新たな値とし
て使用することが可能になる。

【００５６】システムクロックＣ４において符号化対象
シンボル＃２と符号化対象シンボル＃４の参照シンボル
パターンが不一致の場合には、次数・予測値メモリへの
書き込み処理と読みだし処理が異なるアドレスで行われ
るため同時に並行して読みだしと書き込みが行われる。
システムクロックＣ５においては符号化対象シンボル＃
４の次数及び予測値としてシステムクロックＣ４におい
て、次数・予測値レジスタ８に設定された次数及び予測
値を用いる。即ち、符号化対象シンボル＃２と符号化対
象シンボル＃４が不一致の場合には、次数・予測値メモ
リ２から読み出された次数及び予測値が符号化対象シン
ボル＃４の次数及び予測値として用いられる。一方、符
号化対象シンボル＃２と符号化対象シンボル＃４の参照
シンボルパターンが一致した場合にはアクセス禁止回路
１０によりアクセスが禁止されたため、次数及び予測値
メモリからの読みだしは行われず、次数・予測値制御回
路６により更新された新たな次数及び予測値が符号化対
象シンボル＃４の次数及び予測値として用いられる。

【００５７】また、符号化対象シンボル＃５において正
規化処理及び次数・予測値への更新処理が発生した場合
にも前述したような処理により符号化対象シンボル＃７
の次数及び予測値が決定される。

【００５８】実施例４．次に、図７は本発明の他の実施
例である復号化装置のブロック構成を示している。図
で、１１は符号ビット系列１０７より領域幅信号１０６
を基に予測誤差シンボル１０５を再生する算術復号器、
１２はこの予測誤差シンボル１０５と予測値１１２との
排他的論理和演算を行って情報源シンボル１０１を再生
する予測逆変換器である。また２は図１６の参照画素の
うちＡを除いた１１画素の参照シンボルパターンを入力
しＡが１及び０の２種類の状態に対する次数及び予測値
信号（それぞれ１０３ａ、１０４ａと１０３ｂ、１０４
ｂの２種類）を出力する次数・予測値メモリであり、８
もこの出力を受け、同じく２種類の次数・予測値を記憶
するレジスタである。また１３は予測逆変換器１２で再
生された直前の情報源シンボル１０１に応じて２種類の
次数及び予測値のいずれかを選択する選択器であり、ま
た次数・予測値制御回路６からの更新信号１０８を受
け、再生された情報源シンボルに応じて図１６の参照画
素Ａが１あるいは０のいずれかの次数・予測値メモリ２
の内容及び次数・予測値レジスタ８の内容を更新するた
めの第１選択更新信号１０８ａ及び第２選択更新信号１
０８ｂを作成する機能を有している。

【００５９】図８はこの算術復号器１１の内部構成を示
すブロック構成図で、１１ａは数直線上の有効領域Ａｉ
を記憶するＡレジスタ、１１ｂはＭＰＳ領域幅１１４を
計算する減算器、１１ｃはＬＰＳ領域幅１０６とＭＰＳ
領域幅１１４を選択する選択器、１１ｄはこの選択器出
力１１５を受けて最上位の１の位置を検出するビット位
置検出器、１１ｅはこの出力１２０に応じたビット数だ
け選択器１１ｃ出力１１５を左シフトする第１のバレル
シフタ、１１ｆは下界値座標を記憶するＣレジスタ、１
１ｇはＬＰＳの場合のＣレジスタ値１１７を計算する減
算器、１１ｈはＬＰＳの場合のＣレジスタ値１１７とＣ
レジスタ出力１１６を選択する選択器、１１ｉはこの切
り替え器出力１２２の下位に後述の符号レジスタ１１ｊ
からの下位ビット入力１４０を付加する第２のバレルシ
フタ、１１ｊはバイト単位に送られてくる符号データ１
０７を所定ビットずつ第２のバレルシフタ１１ｉを介し
てＣレジスタ１１ｆに入力するための符号レジスタ、１
１ｋはこの算術復号器１１の動きを制御するタイミング
制御回路である。

【００６０】図９はこの符号レジスタ１１ｊの内部構成
を示す構成図で、１１ｊ１〜１１ｊ３は符号データを一
時記憶するバッファレジスタで、１１ｊ４はこれら符号
レジスタ出力からＣレジスタのに入力する下位ビット１
４０を作成するためのバレルシフタ、１１ｊ５このバレ
ルシフタでシフトするビット数１２６を制御する桁制御
回路である。

【００６１】次に本実施例の動作について説明する。算
術符号の復号化においては、Ｃレジスタの内容である相
対座標をＣｉ、第ｉ番目の予測誤差シンボルａ_i 時点で
のＬＰＳの領域幅をＳとすると、Ｃi-1 ＜（Ａi-1 − Ｓ）ならばａ_i はＭＰＳＡi ＝Ａi-1 − ＳＣi ＝Ｃi-1 Ｃi-1 ≧ （Ａi-1 − Ｓ）ならばａ_i はＬＰＳＡi ＝ＳＣi ＝Ｃi-1 − （Ａi-1 − Ｓ）とする。

【００６２】ここで有効領域Ａｉが１／２以下になった
場合には、演算精度を上げるために正規化処理として２
のべき乗倍する。このときＣｉの最下位にｎビットの符
号データを符号レジスタ１１ｊから入力する。Ａｉ更新値＝Ａｉ＊２^m （１／２＜Ａ
ｉ更新値≦１）Ｃｉ更新値＝Ｃｉ＊２^m

【００６３】図１０は本実施例の動作例を示すタイミン
グ図である。まず各システムクロックにおいて、復号化
対象シンボルに対し、図１６の参照画素のうちＡを除い
た１１画素の参照シンボルパターンを基に、Ａが１及び
０の２種類の状態に対する次数１０３ａ、１０３ｂ及び
予測値１０４ａ、１０４ｂをメモリ２から読み出しレジ
スタ８に記憶する。これらの処理はシステムクロック１
周期の時間に行う。その後、直前に再生された情報源シ
ンボルであるＡの値によりこの２種類の次数及び予測値
の一方を選択して当該情報源シンボルの再生及び次数・
予測値の更新を行う。

【００６４】予測誤差シンボルａ_i の再生及び有効領域
Ａｉ、相対座標Ｃｉの演算及び次数・予測値の更新は以
下の動作で行われる。（１）まず算術復号器１１内部のタイミング制御回路１
１ｋにおいてＬＰＳＣレジスタ値信号１１７の極性によ
り、上記の様にＣｉ−１と（Ａi −１−Ｓ）の比較を行
ってシンボルａ_i を（ＭＰＳあるいはＬＰＳ）決定す
る。（２）正規化及び次数・予測値の更新がない場合図１０の復号化対象シンボル＃１、＃３、＃４、＃６の
場合のように、ＡｉとＣｉを計算してＡレジスタ１１ａ
及びＣレジスタ１１ｆに設定する。（１）と（２）の一
連の処理はシステムクロック１周期で行う。（３）正規化及び次数・予測値の更新がある場合図１０に示すように復号化対象シンボル＃２、＃５、＃
７の場合のように、ＡｉとＣｉの演算の結果、有効領域
Ａｉが１／２未満になる場合、ビット位置検出器１１ｄ
で示されるビット数分に対応した正規化の処理を行う。
ここで、バレルシフタ１１ｅ、１１ｉによるビットシフ
ト・正規化動作は（１）の処理と同一のクロック周期内
で行い、次のシンボルの処理に移る。尚、この実施例においても次数・予測値メモリ２は従来
のものに比べて高速な処理が可能であるものを使用して
いるものとする。

【００６５】次数・予測値メモリの更新は、図１０のシ
ステムクロックＣ３、Ｃ６、Ｃ８に示すように、次数・
予測値制御回路６及び検出器７によりシステムクロック
の前半の周期で行う。このように、この復号装置は、バ
レルシフタを用いることにより正規化処理を１システム
クロック内で行えることが大きな特徴である。またバレ
ルシフタを用いる事により正規化動作が１クロック周期
内で実行出来るため、次数・予測値メモリへの更新も高
速に行うようにしたことが大きな特徴である。この例で
は、システムクロックの前半部分で次数・予測値メモリ
２への書き込みを行い、システムクロックの後半部分
で、次数・予測値メモリ２からの読みだしを行う例を示
している。

【００６６】次数・予測値の更新時は、次数・予測値制
御回路６より更新信号が出され、選択器１３で直前に再
生された情報源シンボルの値に基づき参照画素Ａが１な
いし０に対応する選択更新信号（１０８ａ、１０８ｂ）
を生成し、次数・予測値メモリ２の内容を更新する。ま
た、このとき直前に読み出された次数・予測値メモリ２
の参照パターン１０２が更新用参照シンボルパターン１
０９と一致する場合は、次数・予測値レジスタ８の内容
も同時に更新する。

【００６７】正規化時の符号レジスタ１１ｊの動作は、
以下の通りである。（ａ）既にバレルシフタ１１ｊ４の最上位からの位置に
示されている未処理の符号ビット系列から、正規化ビッ
ト数分だけ読み出されバレルシフタ１１ｉを介してＣレ
ジスタ１１ｆの下位にデータをセットする。（ｂ）この読み出しの結果第３のバッファレジスタ１１
ｊ３に未処理の符号ビットがなくなれば新たな符号デー
タを入力し、第１のバッファレジスタ１１ｊ１に格納す
るとともに、第１、第２のバッファレジスタ１１ｊ２、
１１ｊ３の内容をそれぞれ第２、第３のバッファレジス
タ１１ｊ３、１１ｊ４に転送する。（ｃ）第２、第３のバッファレジスタ１１ｊ２、１１ｊ
３共に未処理の符号ビットがなくなれば、同様にさらに
もう１バイトの符号データを入力することとなる。

【００６８】そこで、復号化処理時間Ｔは符号化時同様Ｔ＝１００＋１００＊Ｎａ＋α （ｎｓｅ
ｃ）となり、本実施例においても、従来技術による復号化装
置に比べ大幅な向上が実現できる。

【００６９】実施例５．また、図１１は他の実施例であ
る算術復号器の符号レジスタ１１ｊのブロック構成を示
している。本実施例では図９の実施例との違いは、バイ
ト単位で入力される符号データを２バイト毎まとめてワ
ード構成にするワード変換器１１ｊ６、及びこれを一時
記憶するＦＩＦＯメモリ１１ｊ７が追加されたこと及び
第１第２のバッファレジスタが削除されて第３のバッフ
ァレジスタ１１ｊ３がワード構成となったことである。

【００７０】このように構成することにより、正規化に
必要な符号ビット（最大１６ビット）をバッファレジス
タ１１ｊ３から読み出した時点で次の１６ビットのデー
タを用意できるため、超高速・一定速の復号器が実現で
きる。

【００７１】実施例６．次に、図１２は本発明の他の実
施例である復号化装置のブロック構成を示している。図
で、図７の実施例との違いは、次数・予測値メモリ２が
２ポート構成になったこと、及び検出器７の替わりに参
照シンボルパターン１０２と更新用の同信号１０９を監
視し、更新信号１０８が発生したときに参照シンボルパ
ターン１０２が（図１６のＡを除き）一致する場合は、
並列でアクセスしている参照シンボルパターン１０２に
対応するアクセスの内更新用のシンボルパターンと一致
するもののアクセスを中止するための２ポート制御部１
４、アクセス禁止回路１５が付加されている点である。

【００７２】図１３に本実施例での復号化動作例を示
す。ここで算術復号器は図８のものを用いた。アクセス
時間１００ｎｓｅｃの２ポートメモリにより上記同様の
処理が可能になる。

【００７３】上記実施例では算術符号化としてＬＰＳと
ＭＰＳ算定方法は有効領域幅によらず単一の方法とした
が、特開平３−２４７１２３号のようにＭＰＳのＬＰＳ
の有効範囲の大小関係が逆転するときは、ＭＰＳとＬＰ
Ｓの割当を逆転する方式や、特開平２−２０２２６７号
のように、ＭＰＳ領域幅が１／２を下回る場合にＬＰＳ
の領域の一部をＭＰＳに振り分ける方式などでも同様の
効果を奏す。また、ＭＰＳの領域を数直線上の上位に位
置させる方法でも同様である。

【００７４】

【発明の効果】以上のように、この発明によれば、情報
源シンボルの算術符号化あるいは復号化の際に、ＬＰＳ
あるいはＭＰＳに応じた新たな有効領域幅及び領域の境
界値を所定ビット数シフトすることにより、符号化ある
いは復号化速度を大幅に向上できる符号化装置あるいは
復号化装置を実現することができる。

【図面の簡単な説明】

【図１】本発明の一実施例による符号化装置の算術符号
器のブロック構成図である。

【図２】図１の実施例おける符号レジスタの内部構成を
示すブロック構成図である。

【図３】本実施例による動作例を示すタイミング図であ
る。

【図４】本発明の他の実施例による符号化装置の算術符
号器の符号レジスタのブロック構成図である。

【図５】本発明の他の実施例を示す符号化装置のブロッ
ク構成図である。

【図６】図５の実施例による動作例を示すタイミング図
である。

【図７】本発明の他の実施例を示す復号化装置のブロッ
ク構成図である。

【図８】図７の実施例における算術復号器の内部構成を
示すブロック構成図である。

【図９】図８の算術復号器の符号レジスタの内部構成を
示すブロック構成図である。

【図１０】図７の実施例による動作例を示すタイミング
図である。

【図１１】本発明の他の実施例を示す算術復号器の符号
レジスタのブロック構成図である。

【図１２】本発明の他の実施例を示す算術復号器のブロ
ック構成図である。

【図１３】図１２の実施例による動作例を示すタイミン
グ図である。

【図１４】従来の技術による符号化装置のブロック構成
図である。

【図１５】図１４の符号化装置における算術符号器の内
部構成を示すブロック構成図である。

【図１６】符号化に利用される参照シンボルの位置を示
す図である。

【図１７】次数・予測値テーブルの内容を示す図であ
る。

【図１８】領域幅テーブルの内容を示す図である。

【図１９】図１４の符号化装置における動作例を示すタ
イミング図である。

【符号の説明】

２次数・予測値メモリ５算術符号器６次数・予測値制御回路７検出器８次数・予測値レジスタ１１算術復号器１３選択器５ａ第１のレジスタ５ｂ第１の演算手段５ｄ第２のレジスタ５ｅ第２の演算手段５ｃ第１の選択手段５ｊ第２の選択手段５ｈビット位置検出手段５ｉ第１のバレルシフタ５ｋ第２のバレルシフタ５ｆ符号生成手段５ｆ１１ＦＩＦＯ１１ａ第１のレジスタ１１ｂ第１の演算手段１１ｆ第２のレジスタ１１ｇ第２の演算手段１１ｃ第１の選択手段１１ｈ第２の選択手段１１ｄビット位置検出手段１１ｅ第１のバレルシフタ１１ｉ第２のバレルシフタ１１ｊ符号読みだし手段１１ｊ４ＦＩＦＯ

フロントページの続き (56)参考文献特開昭56−79333（ＪＰ，Ａ) 特開昭60−196014（ＪＰ，Ａ) 特開昭62−43222（ＪＰ，Ａ) 特開平１−286526（ＪＰ，Ａ) 特開平３−247123（ＪＰ，Ａ) 特開平５−64007（ＪＰ，Ａ) 特開平５−298063（ＪＰ，Ａ) 特開平２−305225（ＪＰ，Ａ) 特開平５−67978（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/40

Claims

(57)【特許請求の範囲】

【請求項１】情報源の出力シンボル系列からそのシン
ボル出現確率を推定して、数直線上でそれに応じた有効
領域分割を行ってこのシンボル系列を算術符号化する符
号化装置において、数直線上の有効領域幅を記憶する第１のレジスタと、発生頻度が大きいと想定されるシンボル（優性シンボ
ル：ＭＰＳ）の領域幅を計算する第１の演算手段と、数直線上の有効領域の境界値を記憶する第２のレジスタ
と、発生頻度が小さいと想定されるシンボル（劣性シンボ
ル：ＬＰＳ）に対応する領域とＭＰＳの領域の境界値を
計算する第２の演算手段と、発生シンボルがＭＰＳかＬＰＳかによって新たな有効領
域幅を選択する第１の選択手段と、発生シンボルがＭＰＳかＬＰＳかによって新たな有効領
域の境界値を選択する第２の選択手段と、第１の選択手段からの新たな有効領域幅を受けて最上位
の“１”あるいは“０”の位置を検出するビット位置検
出手段と、ビット位置検出手段からの出力に応じて第１の選択手段
からの新たな有効領域幅をシフトして第１のレジスタへ
出力する第１のシフタと、ビット位置検出手段からの出力に応じて第２の選択手段
からの新たな有効領域の境界値をシフトして第２のレジ
スタに出力するとともにオーバーフローしたデータを出
力する第２のシフタと、この第２のシフタからのオーバーフローしたデータ出力
を受けて符号出力を生成する符号生成手段を備えたこと
を特徴とする符号化装置。
【請求項２】符号生成手段は、ＦＩＦＯメモリを備え
たことを特徴とする特許請求の範囲第１項記載の符号化
装置。
【請求項３】情報源の出力シンボル系列からそのシン
ボル出現確率を推定して、数直線上でそれに応じた有効
領域分割を行ってこのシンボル系列を算術符号化した符
号ビット系列を復号する復号化装置において、数直線上の有効領域幅を記憶する第１のレジスタと、発生頻度が大きいと想定されるシンボル（優性シンボ
ル：ＭＰＳ）の領域幅を計算する第１の演算手段と、数直線上の有効領域の境界値を記憶する第２のレジスタ
と、第２のレジスタ出力から発生頻度が小さいと想定される
シンボル（劣性シンボル：ＬＰＳ）の領域とＭＰＳ領域
との境界値を演算して当該シンボルがＭＰＳかＬＰＳか
を判定する第２の演算手段と、当該シンボルがＭＰＳかＬＰＳかによって新たな有効領
域幅を選択する第１の選択手段と、当該シンボルがＭＰＳかＬＰＳかによって新たな有効領
域の境界値を選択する第２の選択手段と、第１の選択手段からの新たな有効領域幅を受けて最上位
の“１”あるいは“０”の位置を検出するビット位置検
出手段と、符号データ系列を入力して、ビット位置検出手段からの
出力に応じて必要なビット数の符号データ系列を出力す
る符号読み出し手段と、ビット位置検出手段からの出力に応じて第１の選択手段
からの新たな有効領域幅をシフトして第１のレジスタへ
出力する第１のシフタと、ビット位置検出手段からの出力に応じて第２の選択手段
からの新たな有効領域の境界値及び符号読み出し手段か
らの出力をシフトして第２のレジスタへ出力する第２の
シフタを備えたことを特徴とする復号化装置。
【請求項４】符号読み出し手段はＦＩＦＯメモリを備
えたことを特徴とする特許請求の範囲第３項記載の復号
化装置。
【請求項５】情報源の出力シンボル系列の予め定めて
おいた位置の複数の参照シンボルの状態から符号化対象
シンボルの予測を行ってその予測誤差信号を符号化する
符号化装置において、参照シンボルの各状態における上記符号化対象シンボル
の予測値と予測一致率によって分類される群の識別子で
ある次数とを記憶する読みだし書き込み同時動作可能な
メモリと、符号化対象シンボルが予測一致しているか否かを検査し
その結果に応じて該参照シンボル状態における予測値及
び次数を書き換える次数・予測値制御回路と、メモリから読み出された当該符号化対象シンボルの予測
値及び次数、ないしは、直前の符号化対象シンボルに対
する、書き換え処理後の予測値及び次数を記憶する次数
・予測値レジスタと、符号化対象シンボルに対する参照シンボル状態と直前の
シンボルに対する参照シンボル状態とが一致しているか
否かを検出する検出器と、上記次数・予測値レジスタより出力された予測値・次数
をもとに予測誤差信号を符号化する算術符号器とを備
え、直前のシンボルに対する予測値あるいは次数の更新があ
る場合、直前のシンボルに対する予測値・次数の書換処
理と符号化対象シンボルに対する予測値・次数の読みだ
し処理を並行して行わせるとともに、符号化に用いる予
測値及び次数として、符号化対象シンボルに対する参照
シンボル状態と直前の符号化対象シンボルに対する参照
シンボル状態とが一致しているか否かにより、書き換え
処理後の予測値及び次数、または、メモリに格納された
次数・予測値を選択して用いることを特徴とする符号化
装置。
【請求項６】情報源の出力シンボル系列の予め定めて
おいた位置の複数の参照シンボルの状態から復号化対象
シンボルの予測を行ってその予測誤差信号を符号化した
符号ビット系列を復号化する復号化装置において、参照シンボルの状態から復号化対象シンボルの予測値と
予測一致率によって分類される群の識別子である次数と
を記憶するとともに、復号される可能性のある複数のシ
ンボルに対応する次数及び予測値を組として複数出力す
る同時書き込み読みだし可能なメモリと、上記復号化対象シンボルが予測一致しているか否かを検
査しその結果に応じて該参照シンボル状態における予測
値及び次数を書き換える次数・予測値制御回路と、先行する復号化対象シンボルの再生信号値によって、メ
モリから出力される複数組の予測値及び次数のうちの１
組の予測値及び次数を選択出力する選択器と、メモリからの予測値及び次数、ないしは、直前の復号化
対象シンボルに対する更新後の予測値及び次数を記憶す
るレジスタと、復号化対象シンボルに対する参照シンボル状態と直前の
シンボルに対する参照シンボル状態とが一致しているか
否かを検出する検出器と、選択された予測値・次数をもとに符号ビット系列を復号
化する算術復号器とを備え、直前のシンボルに対する予測値あるいは次数の更新があ
る場合、直前のシンボルに対する予測値・次数の書換処
理と復号化対象シンボルに対する予測値あるいは次数の
読みだし処理を並行して行わせるとともに、復号化に用
いる予測値及び次数として、復号化対象シンボルに対す
る参照シンボル状態と直前のシンボルに対する参照シン
ボル状態とが一致しているか否かにより、直前の復号化
対象シンボルの書き換え後の予測値及び次数、または、
メモリに格納された予測値及び次数を選択して用いるこ
とを特徴とする復号化装置。