算術符号化方法及び算術符号化装置
【課題】パイプライン構成を可能とし、スループットを向上させる。
【解決手段】算術符号化装置１は、複数に分割されたパイプライン構造を有し、このステージは、入力されたコンテキストに基づき、コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージ２と、Ａレジスタ２１に格納された値を更新し、状態遷移テーブルに基づき出現確率情報を更新し、Ａレジスタ２１に格納された値を正規化するＡレジスタ更新ステージ３と、Ｃレジスタ４１に格納された値を更新し、Ｃレジスタ４１に格納された値及びＢレジスタ４５に格納された値に基づき、コンテキストに対する符号化データを生成するＣレジスタ更新ステージ４とからなる。算術符号化装置１は、このように分割されたステージ毎に順次処理を行い、入力されたコンテキストを符号化する。
【解決手段】算術符号化装置１は、複数に分割されたパイプライン構造を有し、このステージは、入力されたコンテキストに基づき、コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージ２と、Ａレジスタ２１に格納された値を更新し、状態遷移テーブルに基づき出現確率情報を更新し、Ａレジスタ２１に格納された値を正規化するＡレジスタ更新ステージ３と、Ｃレジスタ４１に格納された値を更新し、Ｃレジスタ４１に格納された値及びＢレジスタ４５に格納された値に基づき、コンテキストに対する符号化データを生成するＣレジスタ更新ステージ４とからなる。算術符号化装置１は、このように分割されたステージ毎に順次処理を行い、入力されたコンテキストを符号化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号化方法及び算術符号化装置に関し、特に、パイプライン処理により符号化処理を行う方法及び装置に関する。
【背景技術】
【０００２】
従来、算術符号化は、画像処理装置等に用いられ、画像データを構成する画素の符号化処理の際に適用される（例えば、特許文献１）。算術符号化処理では、８ビットの符号化されたデータを生成する際に、キャリーが発生する場合がある。
【０００３】
そこで、通常は、このようなキャリーを既に値が確定した符号化データに伝搬させないようにするため、ビット・スタフィングと呼ばれる処理が行われる。このとき、ビット・スタフィング処理を実行するか否かに応じて、正規化処理を実行した後のＣＴレジスタの更新値が変化する。従って、Ｃレジスタの値により、ＣＴレジスタの更新値が決定される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３１８５７６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、従来の算術符号化処理では、Ａレジスタ、Ｃレジスタ及びＣＴレジスタの値を更新する際に、各々のレジスタの値を更新条件として用いるため、パイプライン構成とすることが困難であるという問題があった。パイプライン構成とすることができない場合、算術符号化処理では、１つの入力処理がすべて終了するまで次の入力を受け付けることができないため、処理を実行するために要する時間（実行スループット）が大幅に低下する。
【０００６】
また、算術符号化処理をパイプライン構成とした場合には、演算量の多いＡレジスタ及びＣレジスタの更新タイミングを、異なるパイプラインステージに分割することができないという問題があった。Ｃレジスタの更新値は、Ａレジスタの更新値を使用するため、Ａレジスタ及びＣレジスタが同一のパイプラインステージに存在すると、演算による遅延が積み重なり、パイプライン全体のスループットが低下する。これは、Ａレジスタ及びＣレジスタが共にＣＴレジスタを更新するアルゴリズムであり、かつ、正規化処理の実施を示すＣＴレジスタの値が「０」となった後のＣＴレジスタの更新値が、Ｃレジスタの更新後に決定されるためである。
【０００７】
そこで、本発明は、上記従来の技術における問題点に鑑みてなされたものであって、パイプライン構成を可能とし、スループットを向上させることが可能な算術符号化方法及び算術符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明は、入力されたコンテキストを符号化する算術符号化方法であって、複数のステージに分割され、パイプライン処理によって前記ステージ毎に順次処理を行い、前記ステージは、入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステップによる処理を行う出現確率情報確定ステージと、Ａレジスタに格納された値を更新するＡレジスタ更新ステップ、状態遷移テーブルに基づき前記出現確率情報を更新する出現確率情報更新ステップ、及び前記Ａレジスタに格納された値を正規化する正規化ステップによる処理を行うＡレジスタ更新ステージと、Ｃレジスタに格納された値を更新するＣレジスタ更新ステップ、及び前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成する符号化データ出力ステップによる処理を行うＣレジスタ更新ステージとからなることを特徴とする。
【０００９】
そして、本発明によれば、算術符号化処理を複数のステージに分割してパイプライン処理を行うと共に、Ａレジスタ及びＣレジスタを異なるステージに分割するため、１パイプラインステージ毎の演算量を低減させることができ、スループットを向上させることができる。
【００１０】
上記算術符号化方法において、前記出現確率情報確定ステージは、前記入力されたコンテキストに基づき、出現確率情報保持レジスタに保持された複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択し、前記Ａレジスタ更新ステージは、前記出現確率情報の値Ｑｅと、前記Ａレジスタに格納された値Ａから前記値Ｑｅを減算して得られる値Ａ−ＱｅとのうちいずれかをＡレジスタ更新値として選択し、前記Ａレジスタ更新値と、前記正規化ステップにより正規化されたＡレジスタ更新値のうちいずれかを選択して前記Ａレジスタに格納し、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタに格納された値Ｃと、該値Ｃに前記値Ｑｅを加算して得られる値Ｃ＋Ｑｅとのうちいずれかを選択するためのＣ判定情報を生成し、前記Ｃレジスタ更新ステージは、前記Ａレジスタ更新ステージで生成された前記Ｃ判定情報に基づき、前記値Ｃ及び前記値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して前記Ｃレジスタに格納し、前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記符号化データ出力ステップで前記コンテキストに対する符号化データを生成することができる。
【００１１】
上記算術符号化方法において、前記Ｃレジスタ更新ステージは、前記符号化データ出力ステップにより、ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を出力し、前記Ａレジスタ更新ステージは、前記ＣＴレジスタに格納された値から、前記正規化による前記Ａレジスタ更新値のシフト数を示す正規化シフト数を減算して得られる値と、前記Ｃレジスタ更新ステージから出力される前記ＣＴレジスタ更新値とを加算し、前記ＣＴレジスタに格納することができる。
【００１２】
上記算術符号化方法において、前記ＣＴレジスタは、負の値を格納可能とすることができる。これにより、Ａレジスタ及びＣレジスタを異なるステージに分割することができる。
【００１３】
また、本発明は、入力されたコンテキストを符号化する算術符号化装置であって、複数に分割されたステージ毎に順次処理を行うパイプライン構造を有し、前記ステージは、入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージと、Ａレジスタに格納された値を更新し、状態遷移テーブルに基づき前記出現確率情報を更新し、前記Ａレジスタに格納された値を正規化するＡレジスタ更新ステージと、Ｃレジスタに格納された値を更新し、前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成するＣレジスタ更新ステージとからなることを特徴とする。本発明によれば、前記発明と同様に、Ａレジスタ及びＣレジスタを異なるステージに分割することにより、スループットを向上させることができる。
【００１４】
上記算術符号化装置において、前記出現確率情報確定ステージは、複数のコンテキストに対応する出現確率情報を格納する出現確率情報保持レジスタと、前記入力されたコンテキストに基づき、前記複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択して出力する出現確率情報セレクタとを備え、前記Ａレジスタ更新ステージは、前記Ａレジスタと、前記Ａレジスタに格納された値Ａから前記出現確率情報の値Ｑｅを減算する第１の減算器と、前記値Ｑｅ及び前記第１の減算器により得られる値Ａ−Ｑｅのうちいずれかを第１のＡレジスタ更新値として選択して出力する第１のＡレジスタ更新値セレクタと、前記第１のＡレジスタ更新値を正規化する正規化処理部と、前記第１のＡレジスタ更新値、及び前記正規化された第１のＡレジスタ更新値のうちいずれかを第２のＡレジスタ更新値として選択して出力する第２のＡレジスタ更新値セレクタと、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記第１のＡレジスタ更新値セレクタによる選択を制御するＡ判定情報を生成すると共に、前記正規化処理部による前記第１のＡレジスタ更新値に対する正規化を実施するか否かを判定する正規化判定情報を生成する第１の演算部とを備え、前記第２のＡレジスタ更新値を前記Ａレジスタに格納し、前記Ｃレジスタ更新ステージは、前記Ｃレジスタと、前記Ｃレジスタに格納された値Ｃに前記値Ｑｅを加算する第１の加算器と、前記値Ｃ及び前記第１の加算器により得られる値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して出力するＣレジスタ更新値セレクタと、前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記コンテキストに対する符号化データを生成する第２の演算部とを備え、前記Ｃレジスタ更新値を前記Ｃレジスタに格納することができる。
【００１５】
上記算術符号化装置において、前記第１の演算部は、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタ更新値セレクタによる選択を制御するＣ判定情報を生成することができる。
【００１６】
上記算術符号化装置において、前記正規化処理部は、前記正規化による前記第１のＡレジスタ更新値のシフト数を示す正規化シフト数を生成し、前記Ａレジスタ更新ステージは、ＣＴレジスタと、前記ＣＴレジスタに格納された値から前記正規化シフト数を減算する第２の減算器と、前記第２の減算器により得られる値と、ＣＴレジスタ更新値とを加算する第２の加算器とをさらに備え、前記第２の加算器から出力された値を前記ＣＴレジスタに格納し、前記第２の演算部は、前記ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を生成することができる。
【００１７】
上記算術符号化装置において、前記ＣＴレジスタは、負の値を格納可能とすることができる。これにより、Ａレジスタ及びＣレジスタを異なるステージに分割することができる。
【発明の効果】
【００１８】
以上のように、本発明によれば、パイプライン構成を可能とし、スループットを向上させることが可能になる。
【図面の簡単な説明】
【００１９】
【図１】本発明にかかる算術符号化装置の第１の実施形態における出現確率情報確定ステージ及びＡレジスタ更新ステージの一例を示すブロック図である。
【図２】本発明にかかる算術符号化装置の第１の実施形態におけるＣレジスタ更新ステージの一例を示すブロック図である。
【図３】算術符号化装置における処理の流れの一例を示すフローチャートである。
【図４】図３のステップＳ１及びＳ２における処理について説明するためのブロック図である。
【図５】図３のステップＳ３における処理の流れの一例を示すフローチャートである。
【図６】図３のステップＳ５−３における符号化データ出力処理の流れの一例を示すフローチャートである。
【図７】算術符号化装置の動作について説明するためのタイミングチャートである。
【図８】ＣＴレジスタ値の更新について説明するための略線図である
【図９】本発明にかかる算術符号化装置の第２の実施形態における出現確率情報確定ステージ及び出現確率情報確定第２ステージの一例を示すブロック図である。
【発明を実施するための形態】
【００２０】
次に、本発明を実施するための形態について、図面を参照しながら詳細に説明する。
【００２１】
図１及び図２は、本発明にかかる算術符号化装置の第１の実施形態を示し、この算術符号化装置１は、出現確率情報確定ステージ２、Ａレジスタ更新ステージ３及びＣレジスタ更新ステージ４からなる複数のステージに分割され、これらのステージにおける処理をパイプライン処理によりステージ毎に順次行う。尚、図１及び図２に示すブロック図おいて、記号Ａ〜Ｅは、それぞれ対応する記号へとデータが供給されることを示す。
【００２２】
図１に示すように、出現確率情報確定ステージ２は、コンテキスト保持レジスタ１１、出現確率情報保持レジスタ１２及び出現確率情報セレクタ１３で構成され、算術符号化装置１に入力された算術符号化処理の対象データを示すコンテキストＣＸと、このコンテキストＣＸの出現確率を示す出現確率情報Ｑｅとを対として、次のＡレジスタ更新ステージ３に対して出力する。
【００２３】
コンテキスト保持レジスタ１１は、入力されたコンテキストＣＸを格納するレジスタであり、算術符号化装置１の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力すると共に、このクロックのタイミングで入力される次のコンテキストＣＸを格納する。コンテキスト保持レジスタ１１から出力されたコンテキストＣＸは、出現確率情報セレクタ１３及び後述するＡレジスタ更新ステージ３に供給される。
【００２４】
出現確率情報保持レジスタ１２は、複数のコンテキストＣＸに対応する各々の出現確率情報Ｑｅを保持する複数のレジスタで構成されたレジスタ群であり、Ａレジスタ更新ステージ３から供給される、更新された出現確率情報Ｑｅをレジスタ群の対応するレジスタに保持する。
【００２５】
出現確率情報セレクタ１３は、コンテキスト保持レジスタ１１から供給されたコンテキストＣＸに基づき、出現確率情報保持レジスタ１２に格納された複数の出現確率情報Ｑｅから、このコンテキストＣＸに対応する出現確率情報Ｑｅを選択し、Ａレジスタ更新ステージ３に対して出力する。
【００２６】
Ａレジスタ更新ステージ３は、Ａレジスタ２１、減算器２２、演算部２３、第１のＡレジスタ値セレクタ２４、正規化処理部２５、第２のＡレジスタ値セレクタ２６、正規化シフト数セレクタ２７、ＣＴレジスタ２８、減算器２９、加算器３０及び出現確率情報保持レジスタ３１で構成され、Ａレジスタ２１及びＣＴレジスタ２８の値を更新すると共に、出現確率情報Ｑｅ、正規化シフト数、ＣＴレジスタ値及び後述するＣレジスタの判定結果を、次のＣレジスタ更新ステージ４に対して出力する。
【００２７】
Ａレジスタ２１は、格納されたデータ（以下、「データＡ」とする）を減算器２２及び演算部２３に対して出力する。また、Ａレジスタ２１は、後述する第２のＡレジスタ値セレクタ２６から供給されたデータＡを格納する。
【００２８】
減算器２２は、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅと、Ａレジスタ２１から供給されたデータＡとを減算し、減算結果を示す減算データＡ−Ｑｅを取得する。減算器２２で得られた減算データＡ−Ｑｅは、演算部２３及び第１のＡレジスタ値セレクタ２４に対して出力される。
【００２９】
演算部２３は、出現確率情報確定ステージ２のコンテキスト保持レジスタ１１から供給されたコンテキストＣＸ、出現確率情報セレクタ１３から供給された出現確率情報Ｑｅ、Ａレジスタ２１から供給されたデータＡ、及び減算器２２から供給された減算データＡ−Ｑｅに基づき、Ａレジスタ値及びＣレジスタ値の判定、出現確率情報Ｑｅの更新、正規化を実施するか否かの判定等の処理を行う。
【００３０】
Ａレジスタ値の判定結果を示すＡ判定情報は、第１のＡレジスタ値セレクタ２４に供給され、Ｃレジスタ値の判定結果を示すＣ判定情報は、Ｃレジスタ更新ステージ４に供給される。また、更新された出現確率情報Ｑｅは、出現確率情報確定ステージ２の出現確率情報保持レジスタ１２に供給され、正規化実施の判定結果を示す正規化判定情報は、第２のＡレジスタ値セレクタ２６及び正規化シフト数セレクタ２７に供給される。
【００３１】
第１のＡレジスタ値セレクタ２４は、演算部２３から供給されたＡ判定情報に基づき、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅと、減算器２２から供給された減算データＡ−Ｑｅとのうちいずれかを選択し、正規化処理部２５及び第２のＡレジスタ値セレクタ２６に対して出力する。
【００３２】
正規化処理部２５は、第１のＡレジスタ値セレクタ２４から供給されたデータ（データＡ又は減算データＡ−Ｑｅ）に対して正規化処理を行い、正規化されたデータと正規化シフト数を示す正規化シフト数データとを取得し、正規化データを第２のＡレジスタ値セレクタ２６に供給すると共に、正規化シフト数データを正規化シフト数セレクタ２７に供給する。
【００３３】
第２のＡレジスタ値セレクタ２６は、演算部２３から供給された正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から供給されたデータ（データＡ又は減算データＡ−Ｑｅ）と、正規化処理部２５から供給された正規化データとのうちいずれかを選択し、データＡとしてＡレジスタ２１に供給する。
【００３４】
正規化シフト数セレクタ２７は、演算部２３から供給された正規化判定情報に基づき、正規化処理部２５から供給された正規化シフト数データと、値が「０」であるデータとのうちいずれかを選択し、減算器２９及びＣレジスタ更新ステージ４に対して出力する。
【００３５】
ＣＴレジスタ２８は、格納されたデータ（以下、「データＣＴ」とする）を減算器２９に対して出力する。また、ＣＴレジスタ２８は、後述する加算器３０から供給されたデータＣＴを格納する。
【００３６】
減算器２９は、正規化シフト数セレクタ２７から供給されたデータ（正規化シフト数データ又は「０」データ）と、ＣＴレジスタ２８から供給されたデータＣＴとを減算し、減算結果を示す減算データを取得する。すなわち、減算データは、データＣＴから、正規化シフト数セレクタ２７から供給されたデータを減算したデータとなる。
【００３７】
減算器２９は、正規化処理部２５における正規化処理と同等の処理を行うものであり、５ビットで値「−１６」から値「１５」までを計算することが可能である。減算器２９で得られた減算データは、加算器３０に対して出力される。
【００３８】
加算器３０は、減算器２９から供給された減算データと、後述するＣレジスタ更新ステージ４から供給されたＣＴレジスタの更新値を示すＣＴ更新値データとを加算し、加算結果を示す加算データを取得する。すなわち、加算データは、減算データとＣＴ更新値データとを加算したデータとなる。
【００３９】
加算器３０は、Ｃレジスタ更新ステージ４で行われる符号化データ出力処理と同等の処理を行うものである。加算器３０で得られた加算データは、ＣＴレジスタ値を示すデータＣＴとしてＣＴレジスタ２８及びＣレジスタ更新ステージ４に対して出力される。このデータＣＴの値が「０」以下である場合に、次のＣレジスタ更新ステージ４において符号化データ出力処理が行われることを示す。
【００４０】
出現確率情報保持レジスタ３１は、出現確率情報Ｑｅを保持するレジスタであり、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを格納し、パイプライン処理の動作に応じた所定のタイミングでＣレジスタ更新ステージ４に対して出力する。
【００４１】
図２に示すように、Ｃレジスタ更新ステージ４は、Ｃレジスタ４１、加算器４２、Ｃレジスタ値セレクタ４３、演算部４４、Ｂレジスタ４５、キャリー加算部４６及び符号値セレクタ４７で構成され、Ｃレジスタ４１及びＢレジスタ４５の値を更新すると共に、ＣＴレジスタの更新値、算術符号化結果を示す符号出力値及び符号出力タイミングを示す符号タイミング情報を出力する。尚、ＣＴレジスタの更新値を示すＣＴ更新値データは、前のステージであるＡレジスタ更新ステージ３に対して出力される。
【００４２】
Ｃレジスタ４１は、後述する演算部４４から供給されたＣレジスタ値の計算結果を示すデータＣを格納すると共に、格納されたデータＣを加算器４２及びＣレジスタ値セレクタ４３に対して出力する。
【００４３】
加算器４２は、Ａレジスタ更新ステージ３の出現確率情報保持レジスタ３１から供給された出現確率情報Ｑｅと、Ｃレジスタ４１から供給されたデータＣとを加算し、加算結果を示す加算データＣ＋Ｑｅを取得する。得られた加算データＣ＋Ｑｅは、Ｃレジスタ値セレクタ４３に対して出力される。
【００４４】
Ｃレジスタ値セレクタ４３は、Ａレジスタ更新ステージ３の演算部２３から供給されたＣレジスタ値の判定結果を示すＣ判定情報に基づき、Ｃレジスタ４１から供給されたデータＣと、加算器４２から供給された加算データＣ＋Ｑｅとのうちいずれかを選択し、演算部４４に対して出力する。
【００４５】
演算部４４は、Ａレジスタ更新ステージ３の正規化シフト数セレクタ２７から供給された正規化シフト数データと、加算器３０から供給されたデータＣＴと、Ｃレジスタ値セレクタ４３から供給されたデータ（データＣ又は加算データＣ＋Ｑｅ）と、後述するＢレジスタ４５から供給された符号出力値とに基づき、Ｃレジスタ値の計算、符号出力値の生成、ＣＴレジスタの更新値（ＣＴ更新値データ）の生成、符号キャリーの判定、符号出力のタイミングを示す符号タイミング情報の生成等の処理を行う。
【００４６】
Ｃレジスタ値の計算結果を示すデータＣは、Ｃレジスタ４１に供給され、符号出力値は、Ｂレジスタ４５に供給される。また、ＣＴレジスタの更新値を示すＣＴ更新値データは、Ａレジスタ更新ステージ３の加算器３０に供給され、符号キャリーの判定結果を示す符号キャリー情報は、符号値セレクタ４７に供給される。さらに、符号タイミング情報は、Ｂレジスタ４５に供給されると共に、外部に出力される。
【００４７】
Ｂレジスタ４５は、演算部４４から供給された符号タイミング情報に基づき、演算部４４から供給された符号出力値（確定前符号出力値）を格納すると共に、格納された確定前符号出力値を演算部４４、キャリー加算部４６及び符号値セレクタ４７に対して出力する。
【００４８】
キャリー加算部４６は、Ｂレジスタ４５から供給された確定前符号出力値にキャリーを示す値「１」を加算し、符号値セレクタ４７に対して出力する。
【００４９】
符号値セレクタ４７は、演算部４４から供給された符号キャリー情報に基づき、キャリー加算部４６から供給されたキャリーが加算された符号出力値と、Ｂレジスタ４５から供給された符号出力値（確定前符号出力値）とのうちいずれかを選択し、符号出力値として出力する。
【００５０】
次に、上記構成を有する算術符号化装置１の動作について、図１〜図６を参照して説明する。
【００５１】
まず、算術符号化装置１における処理の流れについて、図３に示すフローチャートを参照して説明する。ステップＳ１において、算術符号化装置１にコンテキストＣＸが入力されると、入力されたコンテキストＣＸに対応する出現確率情報Ｑｅが確定される（ステップＳ２）。
【００５２】
例えば、図４に示すように、複数のコンテキストＣＸ1〜ＣＸnに対応する出現確率情報Ｑｅ1〜Ｑｅnが格納された出現確率情報保持レジスタ１２から、算術符号化装置１に入力されたコンテキストＣＸに対応する出現確率情報Ｑｅが出現確率情報セレクタ１３によって選択される。これにより、ステップＳ１で入力されたコンテキストＣＸに対応する出現確率情報ＱｅがステップＳ２において確定される。
【００５３】
説明は図３に戻り、次に、入力されたコンテキストＣＸと、ステップＳ２で確定された出現確率情報Ｑｅとに基づき、図１に示すＡレジスタ２１及びＣレジスタ４１の値（データＡ及びデータＣ）を更新する処理が行われると共に、出現確率情報Ｑｅを更新する処理が行われる（ステップＳ３）。尚、ステップＳ３における処理の詳細については、後述する。
【００５４】
次に、ステップＳ３による処理の結果に基づき、正規化処理を実施するか否かが判断される（ステップＳ４）。正規化処理を実施すると判断された場合には、正規化処理が行われる（ステップＳ５）。尚、ステップＳ５における正規化処理の詳細については、後述する。一方、正規化処理を実施しないと判断された場合には、処理がステップＳ１に戻り、次のコンテキストＣＸの入力が受け付けられる。以下、上述したステップＳ１〜ステップＳ５の処理が巡回的に行われる。
【００５５】
次に、図３のステップＳ３における処理の流れについて、図５に示すフローチャートを参照して説明する。まず、算術符号化装置１に入力されたコンテキストＣＸがＭＰＳ（More Probable Symbol；優勢確率シンボル）であるか、又はＬＰＳ（Less Probable Symbol；劣勢確率シンボル）であるかが判断される（ステップＳ１１）。
【００５６】
ステップＳ１１において、コンテキストＣＸがＭＰＳであると判断された場合には、Ａレジスタ２１に格納された値（データＡ）から出現確率情報Ｑｅを減算した値（減算データＡ−Ｑｅ）をＡレジスタ２１の値とする（ステップＳ１２）。
【００５７】
次に、Ａレジスタ２１の値（減算データＡ−Ｑｅ）と値「０ｘ８０００」とが比較される（ステップＳ１３）。ここで、値の前に示された「０ｘ」は、その値が１６進数で表記されていることを示す。Ａレジスタ２１の値が値「０ｘ８０００」以上であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とし（ステップＳ１４）、一連の処理が終了される。
【００５８】
一方、Ａレジスタ２１の値が値「０ｘ８０００」未満であると判断された場合には、Ａレジスタ２１の値と出現確率情報Ｑｅとが比較される（ステップＳ１５）。Ａレジスタ２１の値が出現確率情報Ｑｅ以上であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とする（ステップＳ１６）。また、Ａレジスタ２１の値が出現確率情報Ｑｅ未満であると判断された場合には、Ａレジスタ２１に格納された値（データＡ）を出現確率情報Ｑｅとする（ステップＳ１７）。
【００５９】
次に、状態遷移テーブルに基づき出現確率情報Ｑｅが更新される（ステップＳ１８）。ここで、状態遷移テーブルは、インデックス値、出現確率情報Ｑｅ、コンテキストＣＸがＭＰＳである場合の次のインデックス値を示すＮＭＰＳ、コンテキストＣＸがＬＰＳである場合の次のインデックス値を示すＮＬＰＳ等が互いに関連付けられて記述される。
【００６０】
ステップＳ１８では、状態遷移テーブルが参照され、コンテキストＣＸのインデックス値に対応するＮＭＰＳが読み出される。そして、出現確率情報ＱｅがＮＭＰＳに記述されたインデックス値に対応する出現確率情報Ｑｅに更新される。
【００６１】
一方、ステップＳ１１において、コンテキストＣＸがＬＰＳであると判断された場合、Ａレジスタ２１に格納された値（データＡ）から出現確率情報Ｑｅを減算した値（減算データＡ−Ｑｅ）をＡレジスタ２１の値とする（ステップＳ１９）。
【００６２】
次に、Ａレジスタ２１の値（減算データＡ−Ｑｅ）と出現確率情報Ｑｅとが比較される（ステップＳ２０）。Ａレジスタ２１の値が出現確率情報Ｑｅ以上であると判断された場合には、Ａレジスタ２１に格納された値（データＡ）を出現確率情報Ｑｅとする（ステップＳ２１）。また、Ａレジスタ２１の値が出現確率情報Ｑｅ未満であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とする（ステップＳ２２）。
【００６３】
次に、状態遷移テーブルが参照され、コンテキストＣＸのインデックス値に対応するＮＬＰＳが読み出される。そして、出現確率情報ＱｅがＮＬＰＳに記述されたインデックス値に対応する出現確率情報Ｑｅに更新される（ステップＳ２３）。
【００６４】
次に、ステップＳ１８及びステップＳ２３において、出現確率情報Ｑｅが更新された場合に、図３のステップＳ５に示す正規化処理を実施することが確定され（ステップＳ２４）、一連の処理が終了される。
【００６５】
このような処理を行うことにより、図１の演算部２３は、「算術符号化装置１に入力されたコンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値未満」（ステップＳ１５−Ｙｅｓ）である場合と、「コンテキストＣＸがＬＰＳであり（ステップＳ１１−ＬＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値以上」（ステップＳ２０−Ｎｏ）である場合とにおいて、第１のＡレジスタ値セレクタ２４で出現確率情報Ｑｅを選択するためのＡ判定情報を出力する。第１のＡレジスタ値セレクタ２４は、このＡ判定情報に基づき出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを選択して出力する。
【００６６】
それ以外の場合、演算部２３は、第１のＡレジスタ値セレクタ２４で減算データＡ−Ｑｅを選択するためのＡ判定情報を出力する。第１のＡレジスタ値セレクタ２４は、このＡ判定情報に基づき減算器２２から供給された減算データＡ−Ｑｅを選択して出力する。
【００６７】
その後、第２のＡレジスタ値セレクタ２６は、演算部２３から供給された正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から出力されたデータ（出現確率情報Ｑｅ又は減算データＡ−Ｑｅ）又は正規化データのいずれかを選択し、Ａレジスタ２１に供給する。これにより、Ａレジスタ２１に格納されるデータＡの値が更新される。
【００６８】
また、演算部２３は、「コンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が値「０ｘ８０００」以上」（ステップＳ１３−Ｙｅｓ）である場合と、「コンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値以上」（ステップＳ１５−Ｎｏ）である場合と、「コンテキストＣＸがＬＰＳであり（ステップＳ１１−ＬＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値未満」（ステップＳ２０−Ｙｅｓ）である場合とにおいて、図２のＣレジスタ値セレクタ４３で加算データＣ＋Ｑｅを選択するためのＣ判定情報を出力する。Ｃレジスタ値セレクタ４３は、このＣ判定情報に基づき加算器４２から供給された加算データＣ＋Ｑｅを選択して出力する。
【００６９】
それ以外の場合、演算部２３は、Ｃレジスタ値セレクタ４３でデータＣを選択するためのＣ判定情報を出力する。Ｃレジスタ値セレクタ４３は、このＣ判定情報に基づきＣレジスタ４１から供給されたデータＣを選択し、演算部４４に出力する。
【００７０】
その後、演算部４４は、Ｃレジスタ値セレクタ４３から供給されたデータＣに基づき、Ｃレジスタ４１の値を計算する。これにより、Ｃレジスタ４１に格納されるデータＣの値が更新される。
【００７１】
さらに、演算部２３は、ステップＳ１８又はステップＳ２３の処理を行った場合に、状態遷移テーブルに基づき出現確率情報Ｑｅの更新値を決定する。決定された出現確率情報Ｑｅは、出現確率情報保持レジスタ１２に供給されて格納される。これにより、出現確率情報Ｑｅが更新される。
【００７２】
次に、図３のステップＳ５における正規化処理の流れについて説明する。図３のステップＳ４において、正規化処理を実施すると判断された場合には、ステップＳ５−１において、Ａレジスタ２１に格納されたデータＡの値を左に１ビットだけシフトさせると共に、Ｃレジスタ４１に格納されたデータＣの値を左に１ビットだけシフトさせる。また、ＣＴレジスタ２８に格納されたデータＣＴの値を「１」だけ減算する。
【００７３】
次に、データＣＴの値が「０」であるか否かが判断される（ステップＳ５−２）。データＣＴの値が０であると判断された場合には、符号化データ出力処理が行われる（ステップＳ５−３）。尚、符号化データ出力処理の詳細については、後述する。
【００７４】
次に、Ａレジスタ２１の値（データＡ）と値「０ｘ８０００」とが比較される（ステップＳ５−４）。比較の結果、Ａレジスタ２１の値が値「０ｘ８０００」以上であると判断された場合には、処理がステップＳ１に戻り、次のコンテキストＣＸに対する処理が行われる。一方、Ａレジスタ２１の値が値「０ｘ８０００」未満であると判断された場合には、処理がステップＳ５−１に戻り、データＣＴの値が「０」となるまで、ステップＳ５−１〜Ｓ５−４の処理が巡回的に行われる。
【００７５】
尚、ステップＳ４における正規化処理の実施判定は、上述した図５のステップＳ２４における処理を行うか否かで判断することができ、ステップＳ２４の処理を行う場合に、ステップＳ５の正規化処理が行われる。このとき、演算部２３は、「算術符号化装置１に入力されたコンテキストＣＸがＭＰＳであり（図５のステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が値「０ｘ８０００」以上（ステップＳ１３−Ｙｅｓ）である場合」以外の場合において、第２のＡレジスタ値セレクタ２６で正規化データを選択するための正規化判定情報を出力する。第２のＡレジスタ値セレクタ２６は、この正規化判定情報に基づき、正規化処理部２５から供給された正規化データを選択して出力する。
【００７６】
それ以外の場合は、ステップＳ２４の処理を行わないため、ステップＳ５の正規化処理が行われない。そのため、演算部２３は、第２のＡレジスタ値セレクタ２６で第１のＡレジスタ値セレクタ２４から出力されたデータ（出現確率情報Ｑｅ又は減算データＡ−Ｑｅ）を選択するための正規化判定情報を出力する。第２のＡレジスタ値セレクタ２６は、この正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から出力されたデータを選択して出力する。
【００７７】
次に、図３のステップＳ５−３における符号化データ出力処理の流れについて、図６に示すフローチャートを参照して説明する。図３のステップＳ５−２において、データＣＴの値が０であると判断された場合には、図６のステップＳ３１において、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが比較される。比較の結果、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが一致する場合には、ビット・スタフィング処理を行うと判断され、処理がステップＳ３７に移行し、ビット・スタフィング処理が行われる。
【００７８】
一方、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが一致しないと判断された場合には、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ８００００００」とが比較される（ステップＳ３２）。この処理は、図２の演算部４４（符号キャリー判定）で行われる。比較の結果、データＣの値が値「０ｘ８００００００」以上であると判断された場合には、Ｂレジスタ４５の符号出力値にキャリーを示す値「１」が加算される（ステップＳ３３）。また、データＣの値が値「０ｘ８００００００」未満であると判断された場合には、処理がステップＳ３６に移行する。
【００７９】
次に、Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが比較される（ステップＳ３４）。Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが一致すると判断された場合には、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ７ＦＦＦＦＦＦ」との論理積値がデータＣとされ（ステップＳ３５）、処理がステップＳ３７に移行する。一方、Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが一致しないと判断された場合には、処理がステップＳ３６に移行する。
【００８０】
ステップＳ３６では、Ｂレジスタ４５に格納された符号出力値が符号化データとして出力された後、データＣを右に１９ビットだけシフトした値がＢレジスタ４５に格納される。そして、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ００７ＦＦＦＦ」との論理積値がデータＣとされると共に、ＣＴレジスタ２８のデータＣＴの値が「８」とされる。
【００８１】
ステップＳ３７では、ビット・スタフィング処理が行われ、Ｂレジスタ４５に格納された符号出力値が符号化データとして出力された後、データＣを右に２０ビットだけシフトした値がＢレジスタ４５に格納される。そして、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ００ＦＦＦＦＦ」との論理積値がデータＣとされると共に、ＣＴレジスタ２８のデータＣＴの値が「７」とされる。
【００８２】
次に、算術符号化装置１の動作について、図７のタイミングチャートを参照して説明する。図７は、算術符号化装置１の動作を制御するクロックの周期によって決定されるサイクルにおいて、各部に対して入出力される各種データのタイミングの一例を示す。
【００８３】
「クロック」１１１は、算術符号化装置１の動作を制御するクロックを示す。この例では、クロック周期によって決定されたサイクル＃１〜サイクル＃６までが示されている。「コンテキスト」１１２は、サイクル＃１〜サイクル＃６において算術符号化装置１に入力されるコンテキスト（Ａ−０１〜Ｆ−０１）を示す。
【００８４】
出現確率情報確定ステージ２において、「コンテキスト保持レジスタ」１２１は、図１のコンテキスト保持レジスタ１１に保持されたコンテキスト（Ａ−０２〜Ｅ−０２）を示す。また、「出現確率情報保持レジスタ」１２２は、出現確率情報保持レジスタ１２に保持された出現確率情報（Ａ−０３〜Ｅ−０３）を示し、「出現確率情報」１２３は、出現確率情報セレクタ１３で選択された出現確率情報（Ａ−０４〜Ｅ−０４）を示す。
【００８５】
出現確率情報確定ステージ２には、コンテキスト保持レジスタ１１が設けられているため、算術符号化装置１に入力されたコンテキストは、コンテキスト保持レジスタ１１に保持された後、１サイクル後に値が確定して出現確率情報確定ステージ２から出力される。また、出現確率情報保持レジスタ１２に保持された出現確率情報Ｑｅについても、１サイクル後に値が確定し、出現確率情報確定ステージ２から出力される。
【００８６】
すなわち、サイクル＃１で算術符号化装置１に入力されたコンテキスト（Ａ−０１）、及びコンテキスト（Ａ−０１）に対応する出現確率情報は、次のサイクル＃２で値が確定し、コンテキスト（Ａ−０２）及び出現確率情報（Ａ−０４）が出現確率情報確定ステージ２から出力される。
【００８７】
以下、同様にして、サイクル＃２〜サイクル＃５で算術符号化装置１に入力されたコンテキスト（Ｂ−０１〜Ｅ−０１）、及び各々コンテキストに対応する出現確率情報は、サイクル＃３〜サイクル＃６で値が確定し、コンテキスト（Ｂ−０２〜Ｅ−０２）及び出現確率情報（Ｂ−０４〜Ｅ−０４）が出現確率情報確定ステージ２から出力される。
【００８８】
Ａレジスタ更新ステージ３において、「Ａレジスタ」１３１は、Ａレジスタ２１に保持されたデータＡ（Ａ−０５〜Ｄ−０５）を示す。また、「ＣＴレジスタ」１３２は、ＣＴレジスタ２８に保持されたデータＣＴ（Ａ−０６〜Ｄ−０６）を示す。
【００８９】
Ａレジスタ更新ステージ３では、出現確率情報確定ステージ２で確定した値を用いて計算したデータＡ及びデータＣＴをＡレジスタ２１及びＣＴレジスタ２８に格納するため、出現確率情報確定ステージ２の１サイクル後に値が確定し、Ａレジスタ更新ステージ３から出力される。すなわち、サイクル＃２で出現確率情報確定ステージ２から出力された出現確率情報Ａ−０４に基づくデータＡ及びデータＣＴは、サイクル＃３で確定し、データＡ（Ａ−０５）及びデータＣＴ（Ａ−０６）がＡレジスタ更新ステージ３から出力される。
【００９０】
以下、同様にして、サイクル＃３〜サイクル＃５で出現確率情報確定ステージ２から出力された出現確率情報Ｂ−０４〜Ｄ−０４に基づくデータＡ及びデータＣＴは、サイクル＃４〜サイクル＃６で確定し、データＡ（Ｂ−０５〜Ｄ−０５）及びデータＣＴ（Ｂ−０６〜Ｄ−０６）がＡレジスタ更新ステージ３から出力される。
【００９１】
Ｃレジスタ更新ステージ４において、「Ｃレジスタ」１４１は、図２のＣレジスタ４１に保持されたデータＣ（Ａ−０７〜Ｃ−０７）を示し、「ＣＴレジスタ更新値」１４２は、演算部４４から出力されるＣＴ更新値データ（Ａ−０８〜Ｄ−０８）を示す。また、「Ｂレジスタ」１４３は、Ｂレジスタ４５に保持された符号出力値（Ａ−０９〜Ｃ−０９）を示し、「符号出力タイミング」１４４は、演算部４４から出力される符号タイミング情報を示す。
【００９２】
Ｃレジスタ更新ステージ４では、Ａレジスタ更新ステージ３から出力された値を使用して計算したデータＣ及び符号出力値をＣレジスタ４１及びＢレジスタ４５に格納するため、Ａレジスタ更新ステージ３の１サイクル後に値が確定し、Ｃレジスタ更新ステージ４から出力される。ただし、Ｂレジスタ４５は、「符号出力タイミング」１４４をイネーブルとして使用するため、演算部４４から符号タイミング情報が出力された場合にのみ値が更新される。また、ＣＴ更新値データ及び符号タイミング情報は、レジスタへの更新を行わないため、Ａレジスタ更新ステージ３と同じサイクルに値が確定する。
【００９３】
すなわち、サイクル＃３でＡレジスタ更新ステージ３から出力されたデータＡ（Ａ−０５）及びデータＣＴ（Ａ−０６）に基づくデータＣ及び符号出力値は、サイクル＃４で確定し、データＣ（Ａ−０７）及び符号出力値（Ａ−０９）が出力される。一方、ＣＴ更新値データは、Ａレジスタ更新ステージ３と同じサイクルであるサイクル＃３で確定し、ＣＴ更新値データ（Ａ−０８）が出力される。
【００９４】
以下、同様にして、サイクル＃４及び＃５でＡレジスタ更新ステージ３から出力されたデータＡ（Ｂ−０５、Ｃ−０５）及びデータＣＴ（Ｂ−０６、Ｃ−０６）に基づくデータＣ及び符号出力値は、サイクル＃５及び＃６で確定し、データＣ（Ｂ−０７、Ｃ−０７）及び符号出力値（Ｂ−０９、Ｃ−０９）が出力される。また、ＣＴ更新値データは、Ａレジスタ更新ステージ３と同じサイクルであるサイクル＃４及び＃５で確定し、ＣＴ更新値データ（Ｂ−０８、Ｃ−０８）が出力される。
【００９５】
このようにして、サイクル＃１で入力されたコンテキストは、サイクル＃４でＢレジスタ４５に格納され、符号出力タイミングがアサートしたタイミングであるサイクル＃５で符号キャリーの判定を行い、出力される。
【００９６】
尚、符号出力タイミングがアサートされる条件は、ＣＴレジスタ値を示すデータＣＴの値が「０」以下の場合であるため、データＣＴ（Ａ−０６及びＣ−０６）の値が「０」以下である。また、符号出力タイミングがアサートされるのは、符号化データ出力処理が行われるタイミングであるため、ＣＴ更新値データ（Ａ−０８及びＣ−０８）の値が「７」もしくは「８」となり、それ以外のデータＣＴの値は「０」となる。
【００９７】
ここで、正規化処理直前のＡレジスタ２１の値を「０ｘ０１００」とし、ＣＴレジスタ２８の値を「３」とした場合のＣＴレジスタ値の更新について考える。
【００９８】
従来の算術符号化では、図８（ａ）に示すように、正規化完了後のＡレジスタ２１は、７回の左シフトを実行することにより、Ａレジスタ２１の値が「０ｘ８０００」となる。
【００９９】
この間、ＣＴレジスタ２８は、３回の左シフトを実行することにより、ＣＴレジスタ２８の値が「０」となり、符号化データ出力処理が開始される。これにより、ＣＴレジスタ２８には、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値が設定される。さらに、ＣＴレジスタ２８は、残りの４回の左シフトを実行する。
【０１００】
このとき、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割すると、ＣＴレジスタ２８は、符号化データ出力処理によって設定される値を即座に入手できないため、１クロックサイクルで演算を実行することができない。従って、従来は、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割してスループットを向上させることができない。
【０１０１】
これに対して、本実施の形態による算術符号化では、図８（ｂ）に示すように、正規化完了後のＡレジスタ２１は、７回の左シフトを実行することにより、Ａレジスタ２１の値が「０ｘ８０００」となる。
【０１０２】
本実施の形態におけるＣＴレジスタ２８は、負の値を許容する構成であるため、ＣＴレジスタ２８は、７回の左シフトをそのまま実行することにより、ＣＴレジスタ２８の値が「−４」となり、符号化データ出力処理が開始される。これにより、ＣＴレジスタ２８には、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値が設定される。
【０１０３】
このとき、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値は、次のクロックサイクルにおいて、後段のパイプラインステージで確定した値をフィードバックして加算することにより、演算を実行することができる。また、同時に、次のクロックサイクルのＡレジスタ２１のシフト回数だけ左シフトを実行することにより、パイプラインの流れが停止するパイプラインストールのが発生を防ぐことができる。
【０１０４】
従って、本実施の形態においては、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割し、スループットを向上させることが可能になる。
【０１０５】
以上のように、本実施の形態によれば、算術符号化処理を、複数のパイプラインステージからなるパイプライン構成とし、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割すると共に、ＣＴレジスタ２８の値に対して負の値を許容することにより、スループットを向上させることができる。
【０１０６】
次に、第２の実施形態について説明する。第２の実施形態では、算術符号化装置１’において、上述したパイプラインステージをさらに分割し、出現確率情報確定ステージ２及びＡレジスタ更新ステージ３の間に、出現確率情報確定第２ステージ２’を設ける。図９は、本発明にかかる算術符号化装置の第２の実施形態における出現確率情報確定ステージ及び出現確率情報確定第２ステージの一例を示す。尚、上述した第１の実施形態と共通する部分については、同一の符号を付し、詳細な説明を省略する。
【０１０７】
出現確率情報確定第２ステージ２’は、コンテキスト保持レジスタ５１及び５２、比較部５３、出現確率情報保持レジスタ５４及び５５、出現確率情報セレクタ５６で構成される。コンテキスト保持レジスタ５１は、出現確率情報確定ステージ２から出力されたコンテキストＣＸを格納し、算術符号化装置１’の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力する。コンテキスト保持レジスタ５１から出力されたコンテキストＣＸは、コンテキスト保持レジスタ５２及び比較部５３に供給されると共に、Ａレジスタ更新ステージ３に供給される。
【０１０８】
コンテキスト保持レジスタ５２は、コンテキスト保持レジスタ５１から供給されたコンテキストＣＸを格納し、算術符号化装置１’の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力する。コンテキスト保持レジスタ５２に格納されたコンテキストＣＸは、比較部５３に供給される。
【０１０９】
比較部５３は、コンテキスト保持レジスタ５１から供給されたコンテキストＣＸと、コンテキスト保持レジスタ５２から供給されたコンテキストＣＸとを比較し、２つのコンテキストＣＸが同一であるか否かを判断する。ここで、コンテキスト保持レジスタ５２から供給されるコンテキストＣＸは、コンテキスト保持レジスタ５１から供給されるコンテキストＣＸに対して１クロック前、すなわち１サイクル前のコンテキストである。従って、比較部５３は、同一のコンテキストＣＸが１サイクル毎に連続して供給されるか否かを判断する処理を行う。比較部５３は、比較結果を示す比較情報を生成し、出現確率情報セレクタ５６に供給する。
【０１１０】
出現確率情報保持レジスタ５４は、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを格納し、出現確率情報セレクタ５６に供給する。出現確率情報保持レジスタ５５は、Ａレジスタ更新ステージ３から供給される、更新された出現確率情報Ｑｅを格納する。
【０１１１】
出現確率情報セレクタ５６は、比較部５３から供給された比較情報に基づき、出現確率情報保持レジスタ５４から供給された出現確率情報Ｑｅと、出現確率情報保持レジスタ５５から供給された出現確率情報Ｑｅとのうちいずれかを選択する。具体的には、出現確率情報セレクタ５６は、比較情報が同一のコンテキストＣＸが連続すると判断したことを示す場合に、出現確率情報保持レジスタ５５に格納された出現確率情報Ｑｅを選択し、比較情報が同一のコンテキストＣＸが連続しないと判断したことを示す場合に、出現確率情報保持レジスタ５４に格納された出現確率情報Ｑｅを選択する。選択された出現確率情報Ｑｅは、Ａレジスタ更新ステージ３に対して出力される。
【０１１２】
出現確率情報確定第２ステージ２’では、出現確率情報確定ステージ２の出現確率情報セレクタ１３から出力された出現確率情報Ｑｅを出現確率情報保持レジスタ５４に保持するため、出現確率情報セレクタ１３で発生する遅延をＡレジスタ更新ステージ３に持ち越さず、出現確率情報確定第２ステージ２’から出力される出現確率情報Ｑｅの遅延を低減させることができる。これは、コンテキストＣＸの種類が多く、出現確率情報セレクタ１３の動作が複雑となる場合に、特に有効である。
【０１１３】
また、出現確率情報確定第２ステージ２’では、入力されたコンテキストＣＸをコンテキスト保持レジスタ５１に保持するため、コンテキストＣＸのタイミングを調整することができると共に、出現確率情報確定ステージ２の出現確率情報保持レジスタ１２の更新の際のタイムラグを調整することができる。
【０１１４】
さらに、同一のコンテキストＣＸが連続して入力された場合、通常は、２回目のコンテキストＣＸにおける、１回目のコンテキストＣＸに基づきＡレジスタ更新ステージ３からフィードバックされる出現確率情報Ｑｅの更新値の反映が間に合わない。
【０１１５】
そこで、出現確率情報確定第２ステージ２’では、現在のコンテキストＣＸと１サイクル前のコンテキストＣＸとを比較し、これらのコンテキストＣＸが同一である場合には、出現確率情報保持レジスタ５５に保持される、Ａレジスタ更新ステージ３からフィードバックされた出現確率情報Ｑｅの更新値を、現在のコンテキストＣＸに対応する出現確率情報Ｑｅとして使用する。これにより、出現確率情報Ｑｅを更新すると共に、出現確率情報Ｑｅの遅延を低減させてＡレジスタ更新ステージ３に出力することができる。
【符号の説明】
【０１１６】
１ 、１’ 算術符号化装置
２ 出現確率情報確定ステージ
２’ 出現確率情報確定第２ステージ
３ Ａレジスタ更新ステージ
４ Ｃレジスタ更新ステージ
１１ コンテキスト保持レジスタ
１２ 出現確率情報保持レジスタ
１３ 出現確率情報セレクタ
２１ Ａレジスタ
２２ 減算器
２３ 演算部
２４ 第１のＡレジスタ値セレクタ
２５ 正規化処理部
２６ 第２のＡレジスタ値セレクタ
２７ 正規化シフト数セレクタ
２８ ＣＴレジスタ
２９ 減算器
３０ 加算器
３１ 出現確率情報保持レジスタ
４１ Ｃレジスタ
４２ 加算器
４３ Ｃレジスタ値セレクタ
４４ 演算部
４５ Ｂレジスタ
４６ キャリー加算部
４７ 符号値セレクタ
５１、５２ コンテキスト保持レジスタ
５３ 比較部
５４、５５ 出現確率情報保持レジスタ
５６ 出現確率情報セレクタ
１１１ クロック
１１２ コンテキスト
１２１ コンテキスト保持レジスタ
１２２ 出現確率情報保持レジスタ
１２３ 出現確率情報
１３１ Ａレジスタ（データＡ）
１３２ ＣＴレジスタ（データＣＴ）
１４１ Ｃレジスタ（データＣ）
１４２ ＣＴレジスタ更新値（ＣＴ更新値データ）
１４３ Ｂレジスタ（確定前符号出力値）
１４４ 符号出力タイミング（符号タイミング情報）
【技術分野】
【０００１】
本発明は、算術符号化方法及び算術符号化装置に関し、特に、パイプライン処理により符号化処理を行う方法及び装置に関する。
【背景技術】
【０００２】
従来、算術符号化は、画像処理装置等に用いられ、画像データを構成する画素の符号化処理の際に適用される（例えば、特許文献１）。算術符号化処理では、８ビットの符号化されたデータを生成する際に、キャリーが発生する場合がある。
【０００３】
そこで、通常は、このようなキャリーを既に値が確定した符号化データに伝搬させないようにするため、ビット・スタフィングと呼ばれる処理が行われる。このとき、ビット・スタフィング処理を実行するか否かに応じて、正規化処理を実行した後のＣＴレジスタの更新値が変化する。従って、Ｃレジスタの値により、ＣＴレジスタの更新値が決定される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３１８５７６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、従来の算術符号化処理では、Ａレジスタ、Ｃレジスタ及びＣＴレジスタの値を更新する際に、各々のレジスタの値を更新条件として用いるため、パイプライン構成とすることが困難であるという問題があった。パイプライン構成とすることができない場合、算術符号化処理では、１つの入力処理がすべて終了するまで次の入力を受け付けることができないため、処理を実行するために要する時間（実行スループット）が大幅に低下する。
【０００６】
また、算術符号化処理をパイプライン構成とした場合には、演算量の多いＡレジスタ及びＣレジスタの更新タイミングを、異なるパイプラインステージに分割することができないという問題があった。Ｃレジスタの更新値は、Ａレジスタの更新値を使用するため、Ａレジスタ及びＣレジスタが同一のパイプラインステージに存在すると、演算による遅延が積み重なり、パイプライン全体のスループットが低下する。これは、Ａレジスタ及びＣレジスタが共にＣＴレジスタを更新するアルゴリズムであり、かつ、正規化処理の実施を示すＣＴレジスタの値が「０」となった後のＣＴレジスタの更新値が、Ｃレジスタの更新後に決定されるためである。
【０００７】
そこで、本発明は、上記従来の技術における問題点に鑑みてなされたものであって、パイプライン構成を可能とし、スループットを向上させることが可能な算術符号化方法及び算術符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明は、入力されたコンテキストを符号化する算術符号化方法であって、複数のステージに分割され、パイプライン処理によって前記ステージ毎に順次処理を行い、前記ステージは、入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステップによる処理を行う出現確率情報確定ステージと、Ａレジスタに格納された値を更新するＡレジスタ更新ステップ、状態遷移テーブルに基づき前記出現確率情報を更新する出現確率情報更新ステップ、及び前記Ａレジスタに格納された値を正規化する正規化ステップによる処理を行うＡレジスタ更新ステージと、Ｃレジスタに格納された値を更新するＣレジスタ更新ステップ、及び前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成する符号化データ出力ステップによる処理を行うＣレジスタ更新ステージとからなることを特徴とする。
【０００９】
そして、本発明によれば、算術符号化処理を複数のステージに分割してパイプライン処理を行うと共に、Ａレジスタ及びＣレジスタを異なるステージに分割するため、１パイプラインステージ毎の演算量を低減させることができ、スループットを向上させることができる。
【００１０】
上記算術符号化方法において、前記出現確率情報確定ステージは、前記入力されたコンテキストに基づき、出現確率情報保持レジスタに保持された複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択し、前記Ａレジスタ更新ステージは、前記出現確率情報の値Ｑｅと、前記Ａレジスタに格納された値Ａから前記値Ｑｅを減算して得られる値Ａ−ＱｅとのうちいずれかをＡレジスタ更新値として選択し、前記Ａレジスタ更新値と、前記正規化ステップにより正規化されたＡレジスタ更新値のうちいずれかを選択して前記Ａレジスタに格納し、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタに格納された値Ｃと、該値Ｃに前記値Ｑｅを加算して得られる値Ｃ＋Ｑｅとのうちいずれかを選択するためのＣ判定情報を生成し、前記Ｃレジスタ更新ステージは、前記Ａレジスタ更新ステージで生成された前記Ｃ判定情報に基づき、前記値Ｃ及び前記値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して前記Ｃレジスタに格納し、前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記符号化データ出力ステップで前記コンテキストに対する符号化データを生成することができる。
【００１１】
上記算術符号化方法において、前記Ｃレジスタ更新ステージは、前記符号化データ出力ステップにより、ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を出力し、前記Ａレジスタ更新ステージは、前記ＣＴレジスタに格納された値から、前記正規化による前記Ａレジスタ更新値のシフト数を示す正規化シフト数を減算して得られる値と、前記Ｃレジスタ更新ステージから出力される前記ＣＴレジスタ更新値とを加算し、前記ＣＴレジスタに格納することができる。
【００１２】
上記算術符号化方法において、前記ＣＴレジスタは、負の値を格納可能とすることができる。これにより、Ａレジスタ及びＣレジスタを異なるステージに分割することができる。
【００１３】
また、本発明は、入力されたコンテキストを符号化する算術符号化装置であって、複数に分割されたステージ毎に順次処理を行うパイプライン構造を有し、前記ステージは、入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージと、Ａレジスタに格納された値を更新し、状態遷移テーブルに基づき前記出現確率情報を更新し、前記Ａレジスタに格納された値を正規化するＡレジスタ更新ステージと、Ｃレジスタに格納された値を更新し、前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成するＣレジスタ更新ステージとからなることを特徴とする。本発明によれば、前記発明と同様に、Ａレジスタ及びＣレジスタを異なるステージに分割することにより、スループットを向上させることができる。
【００１４】
上記算術符号化装置において、前記出現確率情報確定ステージは、複数のコンテキストに対応する出現確率情報を格納する出現確率情報保持レジスタと、前記入力されたコンテキストに基づき、前記複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択して出力する出現確率情報セレクタとを備え、前記Ａレジスタ更新ステージは、前記Ａレジスタと、前記Ａレジスタに格納された値Ａから前記出現確率情報の値Ｑｅを減算する第１の減算器と、前記値Ｑｅ及び前記第１の減算器により得られる値Ａ−Ｑｅのうちいずれかを第１のＡレジスタ更新値として選択して出力する第１のＡレジスタ更新値セレクタと、前記第１のＡレジスタ更新値を正規化する正規化処理部と、前記第１のＡレジスタ更新値、及び前記正規化された第１のＡレジスタ更新値のうちいずれかを第２のＡレジスタ更新値として選択して出力する第２のＡレジスタ更新値セレクタと、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記第１のＡレジスタ更新値セレクタによる選択を制御するＡ判定情報を生成すると共に、前記正規化処理部による前記第１のＡレジスタ更新値に対する正規化を実施するか否かを判定する正規化判定情報を生成する第１の演算部とを備え、前記第２のＡレジスタ更新値を前記Ａレジスタに格納し、前記Ｃレジスタ更新ステージは、前記Ｃレジスタと、前記Ｃレジスタに格納された値Ｃに前記値Ｑｅを加算する第１の加算器と、前記値Ｃ及び前記第１の加算器により得られる値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して出力するＣレジスタ更新値セレクタと、前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記コンテキストに対する符号化データを生成する第２の演算部とを備え、前記Ｃレジスタ更新値を前記Ｃレジスタに格納することができる。
【００１５】
上記算術符号化装置において、前記第１の演算部は、前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタ更新値セレクタによる選択を制御するＣ判定情報を生成することができる。
【００１６】
上記算術符号化装置において、前記正規化処理部は、前記正規化による前記第１のＡレジスタ更新値のシフト数を示す正規化シフト数を生成し、前記Ａレジスタ更新ステージは、ＣＴレジスタと、前記ＣＴレジスタに格納された値から前記正規化シフト数を減算する第２の減算器と、前記第２の減算器により得られる値と、ＣＴレジスタ更新値とを加算する第２の加算器とをさらに備え、前記第２の加算器から出力された値を前記ＣＴレジスタに格納し、前記第２の演算部は、前記ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を生成することができる。
【００１７】
上記算術符号化装置において、前記ＣＴレジスタは、負の値を格納可能とすることができる。これにより、Ａレジスタ及びＣレジスタを異なるステージに分割することができる。
【発明の効果】
【００１８】
以上のように、本発明によれば、パイプライン構成を可能とし、スループットを向上させることが可能になる。
【図面の簡単な説明】
【００１９】
【図１】本発明にかかる算術符号化装置の第１の実施形態における出現確率情報確定ステージ及びＡレジスタ更新ステージの一例を示すブロック図である。
【図２】本発明にかかる算術符号化装置の第１の実施形態におけるＣレジスタ更新ステージの一例を示すブロック図である。
【図３】算術符号化装置における処理の流れの一例を示すフローチャートである。
【図４】図３のステップＳ１及びＳ２における処理について説明するためのブロック図である。
【図５】図３のステップＳ３における処理の流れの一例を示すフローチャートである。
【図６】図３のステップＳ５−３における符号化データ出力処理の流れの一例を示すフローチャートである。
【図７】算術符号化装置の動作について説明するためのタイミングチャートである。
【図８】ＣＴレジスタ値の更新について説明するための略線図である
【図９】本発明にかかる算術符号化装置の第２の実施形態における出現確率情報確定ステージ及び出現確率情報確定第２ステージの一例を示すブロック図である。
【発明を実施するための形態】
【００２０】
次に、本発明を実施するための形態について、図面を参照しながら詳細に説明する。
【００２１】
図１及び図２は、本発明にかかる算術符号化装置の第１の実施形態を示し、この算術符号化装置１は、出現確率情報確定ステージ２、Ａレジスタ更新ステージ３及びＣレジスタ更新ステージ４からなる複数のステージに分割され、これらのステージにおける処理をパイプライン処理によりステージ毎に順次行う。尚、図１及び図２に示すブロック図おいて、記号Ａ〜Ｅは、それぞれ対応する記号へとデータが供給されることを示す。
【００２２】
図１に示すように、出現確率情報確定ステージ２は、コンテキスト保持レジスタ１１、出現確率情報保持レジスタ１２及び出現確率情報セレクタ１３で構成され、算術符号化装置１に入力された算術符号化処理の対象データを示すコンテキストＣＸと、このコンテキストＣＸの出現確率を示す出現確率情報Ｑｅとを対として、次のＡレジスタ更新ステージ３に対して出力する。
【００２３】
コンテキスト保持レジスタ１１は、入力されたコンテキストＣＸを格納するレジスタであり、算術符号化装置１の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力すると共に、このクロックのタイミングで入力される次のコンテキストＣＸを格納する。コンテキスト保持レジスタ１１から出力されたコンテキストＣＸは、出現確率情報セレクタ１３及び後述するＡレジスタ更新ステージ３に供給される。
【００２４】
出現確率情報保持レジスタ１２は、複数のコンテキストＣＸに対応する各々の出現確率情報Ｑｅを保持する複数のレジスタで構成されたレジスタ群であり、Ａレジスタ更新ステージ３から供給される、更新された出現確率情報Ｑｅをレジスタ群の対応するレジスタに保持する。
【００２５】
出現確率情報セレクタ１３は、コンテキスト保持レジスタ１１から供給されたコンテキストＣＸに基づき、出現確率情報保持レジスタ１２に格納された複数の出現確率情報Ｑｅから、このコンテキストＣＸに対応する出現確率情報Ｑｅを選択し、Ａレジスタ更新ステージ３に対して出力する。
【００２６】
Ａレジスタ更新ステージ３は、Ａレジスタ２１、減算器２２、演算部２３、第１のＡレジスタ値セレクタ２４、正規化処理部２５、第２のＡレジスタ値セレクタ２６、正規化シフト数セレクタ２７、ＣＴレジスタ２８、減算器２９、加算器３０及び出現確率情報保持レジスタ３１で構成され、Ａレジスタ２１及びＣＴレジスタ２８の値を更新すると共に、出現確率情報Ｑｅ、正規化シフト数、ＣＴレジスタ値及び後述するＣレジスタの判定結果を、次のＣレジスタ更新ステージ４に対して出力する。
【００２７】
Ａレジスタ２１は、格納されたデータ（以下、「データＡ」とする）を減算器２２及び演算部２３に対して出力する。また、Ａレジスタ２１は、後述する第２のＡレジスタ値セレクタ２６から供給されたデータＡを格納する。
【００２８】
減算器２２は、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅと、Ａレジスタ２１から供給されたデータＡとを減算し、減算結果を示す減算データＡ−Ｑｅを取得する。減算器２２で得られた減算データＡ−Ｑｅは、演算部２３及び第１のＡレジスタ値セレクタ２４に対して出力される。
【００２９】
演算部２３は、出現確率情報確定ステージ２のコンテキスト保持レジスタ１１から供給されたコンテキストＣＸ、出現確率情報セレクタ１３から供給された出現確率情報Ｑｅ、Ａレジスタ２１から供給されたデータＡ、及び減算器２２から供給された減算データＡ−Ｑｅに基づき、Ａレジスタ値及びＣレジスタ値の判定、出現確率情報Ｑｅの更新、正規化を実施するか否かの判定等の処理を行う。
【００３０】
Ａレジスタ値の判定結果を示すＡ判定情報は、第１のＡレジスタ値セレクタ２４に供給され、Ｃレジスタ値の判定結果を示すＣ判定情報は、Ｃレジスタ更新ステージ４に供給される。また、更新された出現確率情報Ｑｅは、出現確率情報確定ステージ２の出現確率情報保持レジスタ１２に供給され、正規化実施の判定結果を示す正規化判定情報は、第２のＡレジスタ値セレクタ２６及び正規化シフト数セレクタ２７に供給される。
【００３１】
第１のＡレジスタ値セレクタ２４は、演算部２３から供給されたＡ判定情報に基づき、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅと、減算器２２から供給された減算データＡ−Ｑｅとのうちいずれかを選択し、正規化処理部２５及び第２のＡレジスタ値セレクタ２６に対して出力する。
【００３２】
正規化処理部２５は、第１のＡレジスタ値セレクタ２４から供給されたデータ（データＡ又は減算データＡ−Ｑｅ）に対して正規化処理を行い、正規化されたデータと正規化シフト数を示す正規化シフト数データとを取得し、正規化データを第２のＡレジスタ値セレクタ２６に供給すると共に、正規化シフト数データを正規化シフト数セレクタ２７に供給する。
【００３３】
第２のＡレジスタ値セレクタ２６は、演算部２３から供給された正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から供給されたデータ（データＡ又は減算データＡ−Ｑｅ）と、正規化処理部２５から供給された正規化データとのうちいずれかを選択し、データＡとしてＡレジスタ２１に供給する。
【００３４】
正規化シフト数セレクタ２７は、演算部２３から供給された正規化判定情報に基づき、正規化処理部２５から供給された正規化シフト数データと、値が「０」であるデータとのうちいずれかを選択し、減算器２９及びＣレジスタ更新ステージ４に対して出力する。
【００３５】
ＣＴレジスタ２８は、格納されたデータ（以下、「データＣＴ」とする）を減算器２９に対して出力する。また、ＣＴレジスタ２８は、後述する加算器３０から供給されたデータＣＴを格納する。
【００３６】
減算器２９は、正規化シフト数セレクタ２７から供給されたデータ（正規化シフト数データ又は「０」データ）と、ＣＴレジスタ２８から供給されたデータＣＴとを減算し、減算結果を示す減算データを取得する。すなわち、減算データは、データＣＴから、正規化シフト数セレクタ２７から供給されたデータを減算したデータとなる。
【００３７】
減算器２９は、正規化処理部２５における正規化処理と同等の処理を行うものであり、５ビットで値「−１６」から値「１５」までを計算することが可能である。減算器２９で得られた減算データは、加算器３０に対して出力される。
【００３８】
加算器３０は、減算器２９から供給された減算データと、後述するＣレジスタ更新ステージ４から供給されたＣＴレジスタの更新値を示すＣＴ更新値データとを加算し、加算結果を示す加算データを取得する。すなわち、加算データは、減算データとＣＴ更新値データとを加算したデータとなる。
【００３９】
加算器３０は、Ｃレジスタ更新ステージ４で行われる符号化データ出力処理と同等の処理を行うものである。加算器３０で得られた加算データは、ＣＴレジスタ値を示すデータＣＴとしてＣＴレジスタ２８及びＣレジスタ更新ステージ４に対して出力される。このデータＣＴの値が「０」以下である場合に、次のＣレジスタ更新ステージ４において符号化データ出力処理が行われることを示す。
【００４０】
出現確率情報保持レジスタ３１は、出現確率情報Ｑｅを保持するレジスタであり、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを格納し、パイプライン処理の動作に応じた所定のタイミングでＣレジスタ更新ステージ４に対して出力する。
【００４１】
図２に示すように、Ｃレジスタ更新ステージ４は、Ｃレジスタ４１、加算器４２、Ｃレジスタ値セレクタ４３、演算部４４、Ｂレジスタ４５、キャリー加算部４６及び符号値セレクタ４７で構成され、Ｃレジスタ４１及びＢレジスタ４５の値を更新すると共に、ＣＴレジスタの更新値、算術符号化結果を示す符号出力値及び符号出力タイミングを示す符号タイミング情報を出力する。尚、ＣＴレジスタの更新値を示すＣＴ更新値データは、前のステージであるＡレジスタ更新ステージ３に対して出力される。
【００４２】
Ｃレジスタ４１は、後述する演算部４４から供給されたＣレジスタ値の計算結果を示すデータＣを格納すると共に、格納されたデータＣを加算器４２及びＣレジスタ値セレクタ４３に対して出力する。
【００４３】
加算器４２は、Ａレジスタ更新ステージ３の出現確率情報保持レジスタ３１から供給された出現確率情報Ｑｅと、Ｃレジスタ４１から供給されたデータＣとを加算し、加算結果を示す加算データＣ＋Ｑｅを取得する。得られた加算データＣ＋Ｑｅは、Ｃレジスタ値セレクタ４３に対して出力される。
【００４４】
Ｃレジスタ値セレクタ４３は、Ａレジスタ更新ステージ３の演算部２３から供給されたＣレジスタ値の判定結果を示すＣ判定情報に基づき、Ｃレジスタ４１から供給されたデータＣと、加算器４２から供給された加算データＣ＋Ｑｅとのうちいずれかを選択し、演算部４４に対して出力する。
【００４５】
演算部４４は、Ａレジスタ更新ステージ３の正規化シフト数セレクタ２７から供給された正規化シフト数データと、加算器３０から供給されたデータＣＴと、Ｃレジスタ値セレクタ４３から供給されたデータ（データＣ又は加算データＣ＋Ｑｅ）と、後述するＢレジスタ４５から供給された符号出力値とに基づき、Ｃレジスタ値の計算、符号出力値の生成、ＣＴレジスタの更新値（ＣＴ更新値データ）の生成、符号キャリーの判定、符号出力のタイミングを示す符号タイミング情報の生成等の処理を行う。
【００４６】
Ｃレジスタ値の計算結果を示すデータＣは、Ｃレジスタ４１に供給され、符号出力値は、Ｂレジスタ４５に供給される。また、ＣＴレジスタの更新値を示すＣＴ更新値データは、Ａレジスタ更新ステージ３の加算器３０に供給され、符号キャリーの判定結果を示す符号キャリー情報は、符号値セレクタ４７に供給される。さらに、符号タイミング情報は、Ｂレジスタ４５に供給されると共に、外部に出力される。
【００４７】
Ｂレジスタ４５は、演算部４４から供給された符号タイミング情報に基づき、演算部４４から供給された符号出力値（確定前符号出力値）を格納すると共に、格納された確定前符号出力値を演算部４４、キャリー加算部４６及び符号値セレクタ４７に対して出力する。
【００４８】
キャリー加算部４６は、Ｂレジスタ４５から供給された確定前符号出力値にキャリーを示す値「１」を加算し、符号値セレクタ４７に対して出力する。
【００４９】
符号値セレクタ４７は、演算部４４から供給された符号キャリー情報に基づき、キャリー加算部４６から供給されたキャリーが加算された符号出力値と、Ｂレジスタ４５から供給された符号出力値（確定前符号出力値）とのうちいずれかを選択し、符号出力値として出力する。
【００５０】
次に、上記構成を有する算術符号化装置１の動作について、図１〜図６を参照して説明する。
【００５１】
まず、算術符号化装置１における処理の流れについて、図３に示すフローチャートを参照して説明する。ステップＳ１において、算術符号化装置１にコンテキストＣＸが入力されると、入力されたコンテキストＣＸに対応する出現確率情報Ｑｅが確定される（ステップＳ２）。
【００５２】
例えば、図４に示すように、複数のコンテキストＣＸ1〜ＣＸnに対応する出現確率情報Ｑｅ1〜Ｑｅnが格納された出現確率情報保持レジスタ１２から、算術符号化装置１に入力されたコンテキストＣＸに対応する出現確率情報Ｑｅが出現確率情報セレクタ１３によって選択される。これにより、ステップＳ１で入力されたコンテキストＣＸに対応する出現確率情報ＱｅがステップＳ２において確定される。
【００５３】
説明は図３に戻り、次に、入力されたコンテキストＣＸと、ステップＳ２で確定された出現確率情報Ｑｅとに基づき、図１に示すＡレジスタ２１及びＣレジスタ４１の値（データＡ及びデータＣ）を更新する処理が行われると共に、出現確率情報Ｑｅを更新する処理が行われる（ステップＳ３）。尚、ステップＳ３における処理の詳細については、後述する。
【００５４】
次に、ステップＳ３による処理の結果に基づき、正規化処理を実施するか否かが判断される（ステップＳ４）。正規化処理を実施すると判断された場合には、正規化処理が行われる（ステップＳ５）。尚、ステップＳ５における正規化処理の詳細については、後述する。一方、正規化処理を実施しないと判断された場合には、処理がステップＳ１に戻り、次のコンテキストＣＸの入力が受け付けられる。以下、上述したステップＳ１〜ステップＳ５の処理が巡回的に行われる。
【００５５】
次に、図３のステップＳ３における処理の流れについて、図５に示すフローチャートを参照して説明する。まず、算術符号化装置１に入力されたコンテキストＣＸがＭＰＳ（More Probable Symbol；優勢確率シンボル）であるか、又はＬＰＳ（Less Probable Symbol；劣勢確率シンボル）であるかが判断される（ステップＳ１１）。
【００５６】
ステップＳ１１において、コンテキストＣＸがＭＰＳであると判断された場合には、Ａレジスタ２１に格納された値（データＡ）から出現確率情報Ｑｅを減算した値（減算データＡ−Ｑｅ）をＡレジスタ２１の値とする（ステップＳ１２）。
【００５７】
次に、Ａレジスタ２１の値（減算データＡ−Ｑｅ）と値「０ｘ８０００」とが比較される（ステップＳ１３）。ここで、値の前に示された「０ｘ」は、その値が１６進数で表記されていることを示す。Ａレジスタ２１の値が値「０ｘ８０００」以上であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とし（ステップＳ１４）、一連の処理が終了される。
【００５８】
一方、Ａレジスタ２１の値が値「０ｘ８０００」未満であると判断された場合には、Ａレジスタ２１の値と出現確率情報Ｑｅとが比較される（ステップＳ１５）。Ａレジスタ２１の値が出現確率情報Ｑｅ以上であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とする（ステップＳ１６）。また、Ａレジスタ２１の値が出現確率情報Ｑｅ未満であると判断された場合には、Ａレジスタ２１に格納された値（データＡ）を出現確率情報Ｑｅとする（ステップＳ１７）。
【００５９】
次に、状態遷移テーブルに基づき出現確率情報Ｑｅが更新される（ステップＳ１８）。ここで、状態遷移テーブルは、インデックス値、出現確率情報Ｑｅ、コンテキストＣＸがＭＰＳである場合の次のインデックス値を示すＮＭＰＳ、コンテキストＣＸがＬＰＳである場合の次のインデックス値を示すＮＬＰＳ等が互いに関連付けられて記述される。
【００６０】
ステップＳ１８では、状態遷移テーブルが参照され、コンテキストＣＸのインデックス値に対応するＮＭＰＳが読み出される。そして、出現確率情報ＱｅがＮＭＰＳに記述されたインデックス値に対応する出現確率情報Ｑｅに更新される。
【００６１】
一方、ステップＳ１１において、コンテキストＣＸがＬＰＳであると判断された場合、Ａレジスタ２１に格納された値（データＡ）から出現確率情報Ｑｅを減算した値（減算データＡ−Ｑｅ）をＡレジスタ２１の値とする（ステップＳ１９）。
【００６２】
次に、Ａレジスタ２１の値（減算データＡ−Ｑｅ）と出現確率情報Ｑｅとが比較される（ステップＳ２０）。Ａレジスタ２１の値が出現確率情報Ｑｅ以上であると判断された場合には、Ａレジスタ２１に格納された値（データＡ）を出現確率情報Ｑｅとする（ステップＳ２１）。また、Ａレジスタ２１の値が出現確率情報Ｑｅ未満であると判断された場合には、Ｃレジスタ４１に格納された値（データＣ）に出現確率情報Ｑｅを加算した値（加算データＣ＋Ｑｅ）をＣレジスタ４１の値とする（ステップＳ２２）。
【００６３】
次に、状態遷移テーブルが参照され、コンテキストＣＸのインデックス値に対応するＮＬＰＳが読み出される。そして、出現確率情報ＱｅがＮＬＰＳに記述されたインデックス値に対応する出現確率情報Ｑｅに更新される（ステップＳ２３）。
【００６４】
次に、ステップＳ１８及びステップＳ２３において、出現確率情報Ｑｅが更新された場合に、図３のステップＳ５に示す正規化処理を実施することが確定され（ステップＳ２４）、一連の処理が終了される。
【００６５】
このような処理を行うことにより、図１の演算部２３は、「算術符号化装置１に入力されたコンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値未満」（ステップＳ１５−Ｙｅｓ）である場合と、「コンテキストＣＸがＬＰＳであり（ステップＳ１１−ＬＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値以上」（ステップＳ２０−Ｎｏ）である場合とにおいて、第１のＡレジスタ値セレクタ２４で出現確率情報Ｑｅを選択するためのＡ判定情報を出力する。第１のＡレジスタ値セレクタ２４は、このＡ判定情報に基づき出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを選択して出力する。
【００６６】
それ以外の場合、演算部２３は、第１のＡレジスタ値セレクタ２４で減算データＡ−Ｑｅを選択するためのＡ判定情報を出力する。第１のＡレジスタ値セレクタ２４は、このＡ判定情報に基づき減算器２２から供給された減算データＡ−Ｑｅを選択して出力する。
【００６７】
その後、第２のＡレジスタ値セレクタ２６は、演算部２３から供給された正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から出力されたデータ（出現確率情報Ｑｅ又は減算データＡ−Ｑｅ）又は正規化データのいずれかを選択し、Ａレジスタ２１に供給する。これにより、Ａレジスタ２１に格納されるデータＡの値が更新される。
【００６８】
また、演算部２３は、「コンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が値「０ｘ８０００」以上」（ステップＳ１３−Ｙｅｓ）である場合と、「コンテキストＣＸがＭＰＳであり（ステップＳ１１−ＭＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値以上」（ステップＳ１５−Ｎｏ）である場合と、「コンテキストＣＸがＬＰＳであり（ステップＳ１１−ＬＰＳ）、かつ減算データＡ−Ｑｅの値が出現確率情報Ｑｅの値未満」（ステップＳ２０−Ｙｅｓ）である場合とにおいて、図２のＣレジスタ値セレクタ４３で加算データＣ＋Ｑｅを選択するためのＣ判定情報を出力する。Ｃレジスタ値セレクタ４３は、このＣ判定情報に基づき加算器４２から供給された加算データＣ＋Ｑｅを選択して出力する。
【００６９】
それ以外の場合、演算部２３は、Ｃレジスタ値セレクタ４３でデータＣを選択するためのＣ判定情報を出力する。Ｃレジスタ値セレクタ４３は、このＣ判定情報に基づきＣレジスタ４１から供給されたデータＣを選択し、演算部４４に出力する。
【００７０】
その後、演算部４４は、Ｃレジスタ値セレクタ４３から供給されたデータＣに基づき、Ｃレジスタ４１の値を計算する。これにより、Ｃレジスタ４１に格納されるデータＣの値が更新される。
【００７１】
さらに、演算部２３は、ステップＳ１８又はステップＳ２３の処理を行った場合に、状態遷移テーブルに基づき出現確率情報Ｑｅの更新値を決定する。決定された出現確率情報Ｑｅは、出現確率情報保持レジスタ１２に供給されて格納される。これにより、出現確率情報Ｑｅが更新される。
【００７２】
次に、図３のステップＳ５における正規化処理の流れについて説明する。図３のステップＳ４において、正規化処理を実施すると判断された場合には、ステップＳ５−１において、Ａレジスタ２１に格納されたデータＡの値を左に１ビットだけシフトさせると共に、Ｃレジスタ４１に格納されたデータＣの値を左に１ビットだけシフトさせる。また、ＣＴレジスタ２８に格納されたデータＣＴの値を「１」だけ減算する。
【００７３】
次に、データＣＴの値が「０」であるか否かが判断される（ステップＳ５−２）。データＣＴの値が０であると判断された場合には、符号化データ出力処理が行われる（ステップＳ５−３）。尚、符号化データ出力処理の詳細については、後述する。
【００７４】
次に、Ａレジスタ２１の値（データＡ）と値「０ｘ８０００」とが比較される（ステップＳ５−４）。比較の結果、Ａレジスタ２１の値が値「０ｘ８０００」以上であると判断された場合には、処理がステップＳ１に戻り、次のコンテキストＣＸに対する処理が行われる。一方、Ａレジスタ２１の値が値「０ｘ８０００」未満であると判断された場合には、処理がステップＳ５−１に戻り、データＣＴの値が「０」となるまで、ステップＳ５−１〜Ｓ５−４の処理が巡回的に行われる。
【００７５】
尚、ステップＳ４における正規化処理の実施判定は、上述した図５のステップＳ２４における処理を行うか否かで判断することができ、ステップＳ２４の処理を行う場合に、ステップＳ５の正規化処理が行われる。このとき、演算部２３は、「算術符号化装置１に入力されたコンテキストＣＸがＭＰＳであり（図５のステップＳ１１−ＭＰＳ）、かつ減算器２２から出力される減算データＡ−Ｑｅの値が値「０ｘ８０００」以上（ステップＳ１３−Ｙｅｓ）である場合」以外の場合において、第２のＡレジスタ値セレクタ２６で正規化データを選択するための正規化判定情報を出力する。第２のＡレジスタ値セレクタ２６は、この正規化判定情報に基づき、正規化処理部２５から供給された正規化データを選択して出力する。
【００７６】
それ以外の場合は、ステップＳ２４の処理を行わないため、ステップＳ５の正規化処理が行われない。そのため、演算部２３は、第２のＡレジスタ値セレクタ２６で第１のＡレジスタ値セレクタ２４から出力されたデータ（出現確率情報Ｑｅ又は減算データＡ−Ｑｅ）を選択するための正規化判定情報を出力する。第２のＡレジスタ値セレクタ２６は、この正規化判定情報に基づき、第１のＡレジスタ値セレクタ２４から出力されたデータを選択して出力する。
【００７７】
次に、図３のステップＳ５−３における符号化データ出力処理の流れについて、図６に示すフローチャートを参照して説明する。図３のステップＳ５−２において、データＣＴの値が０であると判断された場合には、図６のステップＳ３１において、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが比較される。比較の結果、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが一致する場合には、ビット・スタフィング処理を行うと判断され、処理がステップＳ３７に移行し、ビット・スタフィング処理が行われる。
【００７８】
一方、Ｂレジスタ４５の符号出力値と値「０ｘＦＦ」とが一致しないと判断された場合には、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ８００００００」とが比較される（ステップＳ３２）。この処理は、図２の演算部４４（符号キャリー判定）で行われる。比較の結果、データＣの値が値「０ｘ８００００００」以上であると判断された場合には、Ｂレジスタ４５の符号出力値にキャリーを示す値「１」が加算される（ステップＳ３３）。また、データＣの値が値「０ｘ８００００００」未満であると判断された場合には、処理がステップＳ３６に移行する。
【００７９】
次に、Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが比較される（ステップＳ３４）。Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが一致すると判断された場合には、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ７ＦＦＦＦＦＦ」との論理積値がデータＣとされ（ステップＳ３５）、処理がステップＳ３７に移行する。一方、Ｂレジスタ４５の符号出力値に値「１」を加算した値と値「０ｘＦＦ」とが一致しないと判断された場合には、処理がステップＳ３６に移行する。
【００８０】
ステップＳ３６では、Ｂレジスタ４５に格納された符号出力値が符号化データとして出力された後、データＣを右に１９ビットだけシフトした値がＢレジスタ４５に格納される。そして、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ００７ＦＦＦＦ」との論理積値がデータＣとされると共に、ＣＴレジスタ２８のデータＣＴの値が「８」とされる。
【００８１】
ステップＳ３７では、ビット・スタフィング処理が行われ、Ｂレジスタ４５に格納された符号出力値が符号化データとして出力された後、データＣを右に２０ビットだけシフトした値がＢレジスタ４５に格納される。そして、Ｃレジスタ４１に格納されたデータＣの値と値「０ｘ００ＦＦＦＦＦ」との論理積値がデータＣとされると共に、ＣＴレジスタ２８のデータＣＴの値が「７」とされる。
【００８２】
次に、算術符号化装置１の動作について、図７のタイミングチャートを参照して説明する。図７は、算術符号化装置１の動作を制御するクロックの周期によって決定されるサイクルにおいて、各部に対して入出力される各種データのタイミングの一例を示す。
【００８３】
「クロック」１１１は、算術符号化装置１の動作を制御するクロックを示す。この例では、クロック周期によって決定されたサイクル＃１〜サイクル＃６までが示されている。「コンテキスト」１１２は、サイクル＃１〜サイクル＃６において算術符号化装置１に入力されるコンテキスト（Ａ−０１〜Ｆ−０１）を示す。
【００８４】
出現確率情報確定ステージ２において、「コンテキスト保持レジスタ」１２１は、図１のコンテキスト保持レジスタ１１に保持されたコンテキスト（Ａ−０２〜Ｅ−０２）を示す。また、「出現確率情報保持レジスタ」１２２は、出現確率情報保持レジスタ１２に保持された出現確率情報（Ａ−０３〜Ｅ−０３）を示し、「出現確率情報」１２３は、出現確率情報セレクタ１３で選択された出現確率情報（Ａ−０４〜Ｅ−０４）を示す。
【００８５】
出現確率情報確定ステージ２には、コンテキスト保持レジスタ１１が設けられているため、算術符号化装置１に入力されたコンテキストは、コンテキスト保持レジスタ１１に保持された後、１サイクル後に値が確定して出現確率情報確定ステージ２から出力される。また、出現確率情報保持レジスタ１２に保持された出現確率情報Ｑｅについても、１サイクル後に値が確定し、出現確率情報確定ステージ２から出力される。
【００８６】
すなわち、サイクル＃１で算術符号化装置１に入力されたコンテキスト（Ａ−０１）、及びコンテキスト（Ａ−０１）に対応する出現確率情報は、次のサイクル＃２で値が確定し、コンテキスト（Ａ−０２）及び出現確率情報（Ａ−０４）が出現確率情報確定ステージ２から出力される。
【００８７】
以下、同様にして、サイクル＃２〜サイクル＃５で算術符号化装置１に入力されたコンテキスト（Ｂ−０１〜Ｅ−０１）、及び各々コンテキストに対応する出現確率情報は、サイクル＃３〜サイクル＃６で値が確定し、コンテキスト（Ｂ−０２〜Ｅ−０２）及び出現確率情報（Ｂ−０４〜Ｅ−０４）が出現確率情報確定ステージ２から出力される。
【００８８】
Ａレジスタ更新ステージ３において、「Ａレジスタ」１３１は、Ａレジスタ２１に保持されたデータＡ（Ａ−０５〜Ｄ−０５）を示す。また、「ＣＴレジスタ」１３２は、ＣＴレジスタ２８に保持されたデータＣＴ（Ａ−０６〜Ｄ−０６）を示す。
【００８９】
Ａレジスタ更新ステージ３では、出現確率情報確定ステージ２で確定した値を用いて計算したデータＡ及びデータＣＴをＡレジスタ２１及びＣＴレジスタ２８に格納するため、出現確率情報確定ステージ２の１サイクル後に値が確定し、Ａレジスタ更新ステージ３から出力される。すなわち、サイクル＃２で出現確率情報確定ステージ２から出力された出現確率情報Ａ−０４に基づくデータＡ及びデータＣＴは、サイクル＃３で確定し、データＡ（Ａ−０５）及びデータＣＴ（Ａ−０６）がＡレジスタ更新ステージ３から出力される。
【００９０】
以下、同様にして、サイクル＃３〜サイクル＃５で出現確率情報確定ステージ２から出力された出現確率情報Ｂ−０４〜Ｄ−０４に基づくデータＡ及びデータＣＴは、サイクル＃４〜サイクル＃６で確定し、データＡ（Ｂ−０５〜Ｄ−０５）及びデータＣＴ（Ｂ−０６〜Ｄ−０６）がＡレジスタ更新ステージ３から出力される。
【００９１】
Ｃレジスタ更新ステージ４において、「Ｃレジスタ」１４１は、図２のＣレジスタ４１に保持されたデータＣ（Ａ−０７〜Ｃ−０７）を示し、「ＣＴレジスタ更新値」１４２は、演算部４４から出力されるＣＴ更新値データ（Ａ−０８〜Ｄ−０８）を示す。また、「Ｂレジスタ」１４３は、Ｂレジスタ４５に保持された符号出力値（Ａ−０９〜Ｃ−０９）を示し、「符号出力タイミング」１４４は、演算部４４から出力される符号タイミング情報を示す。
【００９２】
Ｃレジスタ更新ステージ４では、Ａレジスタ更新ステージ３から出力された値を使用して計算したデータＣ及び符号出力値をＣレジスタ４１及びＢレジスタ４５に格納するため、Ａレジスタ更新ステージ３の１サイクル後に値が確定し、Ｃレジスタ更新ステージ４から出力される。ただし、Ｂレジスタ４５は、「符号出力タイミング」１４４をイネーブルとして使用するため、演算部４４から符号タイミング情報が出力された場合にのみ値が更新される。また、ＣＴ更新値データ及び符号タイミング情報は、レジスタへの更新を行わないため、Ａレジスタ更新ステージ３と同じサイクルに値が確定する。
【００９３】
すなわち、サイクル＃３でＡレジスタ更新ステージ３から出力されたデータＡ（Ａ−０５）及びデータＣＴ（Ａ−０６）に基づくデータＣ及び符号出力値は、サイクル＃４で確定し、データＣ（Ａ−０７）及び符号出力値（Ａ−０９）が出力される。一方、ＣＴ更新値データは、Ａレジスタ更新ステージ３と同じサイクルであるサイクル＃３で確定し、ＣＴ更新値データ（Ａ−０８）が出力される。
【００９４】
以下、同様にして、サイクル＃４及び＃５でＡレジスタ更新ステージ３から出力されたデータＡ（Ｂ−０５、Ｃ−０５）及びデータＣＴ（Ｂ−０６、Ｃ−０６）に基づくデータＣ及び符号出力値は、サイクル＃５及び＃６で確定し、データＣ（Ｂ−０７、Ｃ−０７）及び符号出力値（Ｂ−０９、Ｃ−０９）が出力される。また、ＣＴ更新値データは、Ａレジスタ更新ステージ３と同じサイクルであるサイクル＃４及び＃５で確定し、ＣＴ更新値データ（Ｂ−０８、Ｃ−０８）が出力される。
【００９５】
このようにして、サイクル＃１で入力されたコンテキストは、サイクル＃４でＢレジスタ４５に格納され、符号出力タイミングがアサートしたタイミングであるサイクル＃５で符号キャリーの判定を行い、出力される。
【００９６】
尚、符号出力タイミングがアサートされる条件は、ＣＴレジスタ値を示すデータＣＴの値が「０」以下の場合であるため、データＣＴ（Ａ−０６及びＣ−０６）の値が「０」以下である。また、符号出力タイミングがアサートされるのは、符号化データ出力処理が行われるタイミングであるため、ＣＴ更新値データ（Ａ−０８及びＣ−０８）の値が「７」もしくは「８」となり、それ以外のデータＣＴの値は「０」となる。
【００９７】
ここで、正規化処理直前のＡレジスタ２１の値を「０ｘ０１００」とし、ＣＴレジスタ２８の値を「３」とした場合のＣＴレジスタ値の更新について考える。
【００９８】
従来の算術符号化では、図８（ａ）に示すように、正規化完了後のＡレジスタ２１は、７回の左シフトを実行することにより、Ａレジスタ２１の値が「０ｘ８０００」となる。
【００９９】
この間、ＣＴレジスタ２８は、３回の左シフトを実行することにより、ＣＴレジスタ２８の値が「０」となり、符号化データ出力処理が開始される。これにより、ＣＴレジスタ２８には、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値が設定される。さらに、ＣＴレジスタ２８は、残りの４回の左シフトを実行する。
【０１００】
このとき、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割すると、ＣＴレジスタ２８は、符号化データ出力処理によって設定される値を即座に入手できないため、１クロックサイクルで演算を実行することができない。従って、従来は、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割してスループットを向上させることができない。
【０１０１】
これに対して、本実施の形態による算術符号化では、図８（ｂ）に示すように、正規化完了後のＡレジスタ２１は、７回の左シフトを実行することにより、Ａレジスタ２１の値が「０ｘ８０００」となる。
【０１０２】
本実施の形態におけるＣＴレジスタ２８は、負の値を許容する構成であるため、ＣＴレジスタ２８は、７回の左シフトをそのまま実行することにより、ＣＴレジスタ２８の値が「−４」となり、符号化データ出力処理が開始される。これにより、ＣＴレジスタ２８には、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値が設定される。
【０１０３】
このとき、符号化データ出力処理を実行した際のＣレジスタ４１の値に依存した値は、次のクロックサイクルにおいて、後段のパイプラインステージで確定した値をフィードバックして加算することにより、演算を実行することができる。また、同時に、次のクロックサイクルのＡレジスタ２１のシフト回数だけ左シフトを実行することにより、パイプラインの流れが停止するパイプラインストールのが発生を防ぐことができる。
【０１０４】
従って、本実施の形態においては、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割し、スループットを向上させることが可能になる。
【０１０５】
以上のように、本実施の形態によれば、算術符号化処理を、複数のパイプラインステージからなるパイプライン構成とし、Ａレジスタ２１及びＣレジスタ４１を異なるパイプラインステージに分割すると共に、ＣＴレジスタ２８の値に対して負の値を許容することにより、スループットを向上させることができる。
【０１０６】
次に、第２の実施形態について説明する。第２の実施形態では、算術符号化装置１’において、上述したパイプラインステージをさらに分割し、出現確率情報確定ステージ２及びＡレジスタ更新ステージ３の間に、出現確率情報確定第２ステージ２’を設ける。図９は、本発明にかかる算術符号化装置の第２の実施形態における出現確率情報確定ステージ及び出現確率情報確定第２ステージの一例を示す。尚、上述した第１の実施形態と共通する部分については、同一の符号を付し、詳細な説明を省略する。
【０１０７】
出現確率情報確定第２ステージ２’は、コンテキスト保持レジスタ５１及び５２、比較部５３、出現確率情報保持レジスタ５４及び５５、出現確率情報セレクタ５６で構成される。コンテキスト保持レジスタ５１は、出現確率情報確定ステージ２から出力されたコンテキストＣＸを格納し、算術符号化装置１’の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力する。コンテキスト保持レジスタ５１から出力されたコンテキストＣＸは、コンテキスト保持レジスタ５２及び比較部５３に供給されると共に、Ａレジスタ更新ステージ３に供給される。
【０１０８】
コンテキスト保持レジスタ５２は、コンテキスト保持レジスタ５１から供給されたコンテキストＣＸを格納し、算術符号化装置１’の動作を制御するクロックのタイミングで、格納されたコンテキストＣＸを出力する。コンテキスト保持レジスタ５２に格納されたコンテキストＣＸは、比較部５３に供給される。
【０１０９】
比較部５３は、コンテキスト保持レジスタ５１から供給されたコンテキストＣＸと、コンテキスト保持レジスタ５２から供給されたコンテキストＣＸとを比較し、２つのコンテキストＣＸが同一であるか否かを判断する。ここで、コンテキスト保持レジスタ５２から供給されるコンテキストＣＸは、コンテキスト保持レジスタ５１から供給されるコンテキストＣＸに対して１クロック前、すなわち１サイクル前のコンテキストである。従って、比較部５３は、同一のコンテキストＣＸが１サイクル毎に連続して供給されるか否かを判断する処理を行う。比較部５３は、比較結果を示す比較情報を生成し、出現確率情報セレクタ５６に供給する。
【０１１０】
出現確率情報保持レジスタ５４は、出現確率情報確定ステージ２の出現確率情報セレクタ１３から供給された出現確率情報Ｑｅを格納し、出現確率情報セレクタ５６に供給する。出現確率情報保持レジスタ５５は、Ａレジスタ更新ステージ３から供給される、更新された出現確率情報Ｑｅを格納する。
【０１１１】
出現確率情報セレクタ５６は、比較部５３から供給された比較情報に基づき、出現確率情報保持レジスタ５４から供給された出現確率情報Ｑｅと、出現確率情報保持レジスタ５５から供給された出現確率情報Ｑｅとのうちいずれかを選択する。具体的には、出現確率情報セレクタ５６は、比較情報が同一のコンテキストＣＸが連続すると判断したことを示す場合に、出現確率情報保持レジスタ５５に格納された出現確率情報Ｑｅを選択し、比較情報が同一のコンテキストＣＸが連続しないと判断したことを示す場合に、出現確率情報保持レジスタ５４に格納された出現確率情報Ｑｅを選択する。選択された出現確率情報Ｑｅは、Ａレジスタ更新ステージ３に対して出力される。
【０１１２】
出現確率情報確定第２ステージ２’では、出現確率情報確定ステージ２の出現確率情報セレクタ１３から出力された出現確率情報Ｑｅを出現確率情報保持レジスタ５４に保持するため、出現確率情報セレクタ１３で発生する遅延をＡレジスタ更新ステージ３に持ち越さず、出現確率情報確定第２ステージ２’から出力される出現確率情報Ｑｅの遅延を低減させることができる。これは、コンテキストＣＸの種類が多く、出現確率情報セレクタ１３の動作が複雑となる場合に、特に有効である。
【０１１３】
また、出現確率情報確定第２ステージ２’では、入力されたコンテキストＣＸをコンテキスト保持レジスタ５１に保持するため、コンテキストＣＸのタイミングを調整することができると共に、出現確率情報確定ステージ２の出現確率情報保持レジスタ１２の更新の際のタイムラグを調整することができる。
【０１１４】
さらに、同一のコンテキストＣＸが連続して入力された場合、通常は、２回目のコンテキストＣＸにおける、１回目のコンテキストＣＸに基づきＡレジスタ更新ステージ３からフィードバックされる出現確率情報Ｑｅの更新値の反映が間に合わない。
【０１１５】
そこで、出現確率情報確定第２ステージ２’では、現在のコンテキストＣＸと１サイクル前のコンテキストＣＸとを比較し、これらのコンテキストＣＸが同一である場合には、出現確率情報保持レジスタ５５に保持される、Ａレジスタ更新ステージ３からフィードバックされた出現確率情報Ｑｅの更新値を、現在のコンテキストＣＸに対応する出現確率情報Ｑｅとして使用する。これにより、出現確率情報Ｑｅを更新すると共に、出現確率情報Ｑｅの遅延を低減させてＡレジスタ更新ステージ３に出力することができる。
【符号の説明】
【０１１６】
１ 、１’ 算術符号化装置
２ 出現確率情報確定ステージ
２’ 出現確率情報確定第２ステージ
３ Ａレジスタ更新ステージ
４ Ｃレジスタ更新ステージ
１１ コンテキスト保持レジスタ
１２ 出現確率情報保持レジスタ
１３ 出現確率情報セレクタ
２１ Ａレジスタ
２２ 減算器
２３ 演算部
２４ 第１のＡレジスタ値セレクタ
２５ 正規化処理部
２６ 第２のＡレジスタ値セレクタ
２７ 正規化シフト数セレクタ
２８ ＣＴレジスタ
２９ 減算器
３０ 加算器
３１ 出現確率情報保持レジスタ
４１ Ｃレジスタ
４２ 加算器
４３ Ｃレジスタ値セレクタ
４４ 演算部
４５ Ｂレジスタ
４６ キャリー加算部
４７ 符号値セレクタ
５１、５２ コンテキスト保持レジスタ
５３ 比較部
５４、５５ 出現確率情報保持レジスタ
５６ 出現確率情報セレクタ
１１１ クロック
１１２ コンテキスト
１２１ コンテキスト保持レジスタ
１２２ 出現確率情報保持レジスタ
１２３ 出現確率情報
１３１ Ａレジスタ（データＡ）
１３２ ＣＴレジスタ（データＣＴ）
１４１ Ｃレジスタ（データＣ）
１４２ ＣＴレジスタ更新値（ＣＴ更新値データ）
１４３ Ｂレジスタ（確定前符号出力値）
１４４ 符号出力タイミング（符号タイミング情報）
【特許請求の範囲】
【請求項１】
入力されたコンテキストを符号化する算術符号化方法であって、
複数のステージに分割され、パイプライン処理によって前記ステージ毎に順次処理を行い、
前記ステージは、
入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステップによる処理を行う出現確率情報確定ステージと、
Ａレジスタに格納された値を更新するＡレジスタ更新ステップ、状態遷移テーブルに基づき前記出現確率情報を更新する出現確率情報更新ステップ、及び前記Ａレジスタに格納された値を正規化する正規化ステップによる処理を行うＡレジスタ更新ステージと、
Ｃレジスタに格納された値を更新するＣレジスタ更新ステップ、及び前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成する符号化データ出力ステップによる処理を行うＣレジスタ更新ステージとからなることを特徴とする算術符号化方法。
【請求項２】
前記出現確率情報確定ステージは、
前記入力されたコンテキストに基づき、出現確率情報保持レジスタに保持された複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択し、
前記Ａレジスタ更新ステージは、
前記出現確率情報の値Ｑｅと、前記Ａレジスタに格納された値Ａから前記値Ｑｅを減算して得られる値Ａ−ＱｅとのうちいずれかをＡレジスタ更新値として選択し、
前記Ａレジスタ更新値と、前記正規化ステップにより正規化されたＡレジスタ更新値のうちいずれかを選択して前記Ａレジスタに格納し、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタに格納された値Ｃと、該値Ｃに前記値Ｑｅを加算して得られる値Ｃ＋Ｑｅとのうちいずれかを選択するためのＣ判定情報を生成し、
前記Ｃレジスタ更新ステージは、
前記Ａレジスタ更新ステージで生成された前記Ｃ判定情報に基づき、前記値Ｃ及び前記値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して前記Ｃレジスタに格納し、
前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記符号化データ出力ステップで前記コンテキストに対する符号化データを生成することを特徴とする請求項１に記載の算術符号化方法。
【請求項３】
前記Ｃレジスタ更新ステージは、前記符号化データ出力ステップにより、ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を出力し、
前記Ａレジスタ更新ステージは、前記ＣＴレジスタに格納された値から、前記正規化による前記Ａレジスタ更新値のシフト数を示す正規化シフト数を減算して得られる値と、前記Ｃレジスタ更新ステージから出力される前記ＣＴレジスタ更新値とを加算し、前記ＣＴレジスタに格納することを特徴とする請求項２に記載の算術符号化方法。
【請求項４】
前記ＣＴレジスタは、負の値を格納可能とすることを特徴とする請求項３に記載の算術符号化方法。
【請求項５】
入力されたコンテキストを符号化する算術符号化装置であって、
複数に分割されたステージ毎に順次処理を行うパイプライン構造を有し、
前記ステージは、
入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージと、
Ａレジスタに格納された値を更新し、状態遷移テーブルに基づき前記出現確率情報を更新し、前記Ａレジスタに格納された値を正規化するＡレジスタ更新ステージと、
Ｃレジスタに格納された値を更新し、前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成するＣレジスタ更新ステージとからなることを特徴とする算術符号化装置。
【請求項６】
前記出現確率情報確定ステージは、
複数のコンテキストに対応する出現確率情報を格納する出現確率情報保持レジスタと、
前記入力されたコンテキストに基づき、前記複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択して出力する出現確率情報セレクタと
を備え、
前記Ａレジスタ更新ステージは、
前記Ａレジスタと、
前記Ａレジスタに格納された値Ａから前記出現確率情報の値Ｑｅを減算する第１の減算器と、
前記値Ｑｅ及び前記第１の減算器により得られる値Ａ−Ｑｅのうちいずれかを第１のＡレジスタ更新値として選択して出力する第１のＡレジスタ更新値セレクタと、
前記第１のＡレジスタ更新値を正規化する正規化処理部と、
前記第１のＡレジスタ更新値、及び前記正規化された第１のＡレジスタ更新値のうちいずれかを第２のＡレジスタ更新値として選択して出力する第２のＡレジスタ更新値セレクタと、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記第１のＡレジスタ更新値セレクタによる選択を制御するＡ判定情報を生成すると共に、前記正規化処理部による前記第１のＡレジスタ更新値に対する正規化を実施するか否かを判定する正規化判定情報を生成する第１の演算部とを備え、
前記第２のＡレジスタ更新値を前記Ａレジスタに格納し、
前記Ｃレジスタ更新ステージは、
前記Ｃレジスタと、
前記Ｃレジスタに格納された値Ｃに前記値Ｑｅを加算する第１の加算器と、
前記値Ｃ及び前記第１の加算器により得られる値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して出力するＣレジスタ更新値セレクタと、
前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記コンテキストに対する符号化データを生成する第２の演算部とを備え、
前記Ｃレジスタ更新値を前記Ｃレジスタに格納することを特徴とする請求項５に記載の算術符号化装置。
【請求項７】
前記第１の演算部は、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタ更新値セレクタによる選択を制御するＣ判定情報を生成することを特徴とする請求項６に記載の算術符号化装置。
【請求項８】
前記正規化処理部は、
前記正規化による前記第１のＡレジスタ更新値のシフト数を示す正規化シフト数を生成し、
前記Ａレジスタ更新ステージは、
ＣＴレジスタと、
前記ＣＴレジスタに格納された値から前記正規化シフト数を減算する第２の減算器と、
前記第２の減算器により得られる値と、ＣＴレジスタ更新値とを加算する第２の加算器とをさらに備え、
前記第２の加算器から出力された値を前記ＣＴレジスタに格納し、
前記第２の演算部は、前記ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を生成することを特徴とする請求項７に記載の算術符号化装置。
【請求項９】
前記ＣＴレジスタは、負の値を格納可能とすることを特徴とする請求項８に記載の算術符号化装置。
【請求項１】
入力されたコンテキストを符号化する算術符号化方法であって、
複数のステージに分割され、パイプライン処理によって前記ステージ毎に順次処理を行い、
前記ステージは、
入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステップによる処理を行う出現確率情報確定ステージと、
Ａレジスタに格納された値を更新するＡレジスタ更新ステップ、状態遷移テーブルに基づき前記出現確率情報を更新する出現確率情報更新ステップ、及び前記Ａレジスタに格納された値を正規化する正規化ステップによる処理を行うＡレジスタ更新ステージと、
Ｃレジスタに格納された値を更新するＣレジスタ更新ステップ、及び前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成する符号化データ出力ステップによる処理を行うＣレジスタ更新ステージとからなることを特徴とする算術符号化方法。
【請求項２】
前記出現確率情報確定ステージは、
前記入力されたコンテキストに基づき、出現確率情報保持レジスタに保持された複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択し、
前記Ａレジスタ更新ステージは、
前記出現確率情報の値Ｑｅと、前記Ａレジスタに格納された値Ａから前記値Ｑｅを減算して得られる値Ａ−ＱｅとのうちいずれかをＡレジスタ更新値として選択し、
前記Ａレジスタ更新値と、前記正規化ステップにより正規化されたＡレジスタ更新値のうちいずれかを選択して前記Ａレジスタに格納し、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタに格納された値Ｃと、該値Ｃに前記値Ｑｅを加算して得られる値Ｃ＋Ｑｅとのうちいずれかを選択するためのＣ判定情報を生成し、
前記Ｃレジスタ更新ステージは、
前記Ａレジスタ更新ステージで生成された前記Ｃ判定情報に基づき、前記値Ｃ及び前記値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して前記Ｃレジスタに格納し、
前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記符号化データ出力ステップで前記コンテキストに対する符号化データを生成することを特徴とする請求項１に記載の算術符号化方法。
【請求項３】
前記Ｃレジスタ更新ステージは、前記符号化データ出力ステップにより、ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を出力し、
前記Ａレジスタ更新ステージは、前記ＣＴレジスタに格納された値から、前記正規化による前記Ａレジスタ更新値のシフト数を示す正規化シフト数を減算して得られる値と、前記Ｃレジスタ更新ステージから出力される前記ＣＴレジスタ更新値とを加算し、前記ＣＴレジスタに格納することを特徴とする請求項２に記載の算術符号化方法。
【請求項４】
前記ＣＴレジスタは、負の値を格納可能とすることを特徴とする請求項３に記載の算術符号化方法。
【請求項５】
入力されたコンテキストを符号化する算術符号化装置であって、
複数に分割されたステージ毎に順次処理を行うパイプライン構造を有し、
前記ステージは、
入力されたコンテキストに基づき、該コンテキストの出現確率を示す出現確率情報を確定する出現確率情報確定ステージと、
Ａレジスタに格納された値を更新し、状態遷移テーブルに基づき前記出現確率情報を更新し、前記Ａレジスタに格納された値を正規化するＡレジスタ更新ステージと、
Ｃレジスタに格納された値を更新し、前記Ｃレジスタに格納された値及びＢレジスタに格納された値に基づき、前記コンテキストに対する符号化データを生成するＣレジスタ更新ステージとからなることを特徴とする算術符号化装置。
【請求項６】
前記出現確率情報確定ステージは、
複数のコンテキストに対応する出現確率情報を格納する出現確率情報保持レジスタと、
前記入力されたコンテキストに基づき、前記複数の出現確率情報から、前記コンテキストに対応する出現確率情報を選択して出力する出現確率情報セレクタと
を備え、
前記Ａレジスタ更新ステージは、
前記Ａレジスタと、
前記Ａレジスタに格納された値Ａから前記出現確率情報の値Ｑｅを減算する第１の減算器と、
前記値Ｑｅ及び前記第１の減算器により得られる値Ａ−Ｑｅのうちいずれかを第１のＡレジスタ更新値として選択して出力する第１のＡレジスタ更新値セレクタと、
前記第１のＡレジスタ更新値を正規化する正規化処理部と、
前記第１のＡレジスタ更新値、及び前記正規化された第１のＡレジスタ更新値のうちいずれかを第２のＡレジスタ更新値として選択して出力する第２のＡレジスタ更新値セレクタと、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記第１のＡレジスタ更新値セレクタによる選択を制御するＡ判定情報を生成すると共に、前記正規化処理部による前記第１のＡレジスタ更新値に対する正規化を実施するか否かを判定する正規化判定情報を生成する第１の演算部とを備え、
前記第２のＡレジスタ更新値を前記Ａレジスタに格納し、
前記Ｃレジスタ更新ステージは、
前記Ｃレジスタと、
前記Ｃレジスタに格納された値Ｃに前記値Ｑｅを加算する第１の加算器と、
前記値Ｃ及び前記第１の加算器により得られる値Ｃ＋ＱｅのうちいずれかをＣレジスタ更新値として選択して出力するＣレジスタ更新値セレクタと、
前記Ｃレジスタに格納された値及び前記Ｂレジスタに格納された値とに基づき、前記コンテキストに対する符号化データを生成する第２の演算部とを備え、
前記Ｃレジスタ更新値を前記Ｃレジスタに格納することを特徴とする請求項５に記載の算術符号化装置。
【請求項７】
前記第１の演算部は、
前記値Ｑｅ及び前記値Ａ−Ｑｅに基づき、前記Ｃレジスタ更新値セレクタによる選択を制御するＣ判定情報を生成することを特徴とする請求項６に記載の算術符号化装置。
【請求項８】
前記正規化処理部は、
前記正規化による前記第１のＡレジスタ更新値のシフト数を示す正規化シフト数を生成し、
前記Ａレジスタ更新ステージは、
ＣＴレジスタと、
前記ＣＴレジスタに格納された値から前記正規化シフト数を減算する第２の減算器と、
前記第２の減算器により得られる値と、ＣＴレジスタ更新値とを加算する第２の加算器とをさらに備え、
前記第２の加算器から出力された値を前記ＣＴレジスタに格納し、
前記第２の演算部は、前記ＣＴレジスタに格納された値の更新値であるＣＴレジスタ更新値を生成することを特徴とする請求項７に記載の算術符号化装置。
【請求項９】
前記ＣＴレジスタは、負の値を格納可能とすることを特徴とする請求項８に記載の算術符号化装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−１６９５４（Ｐ２０１３−１６９５４Ａ）
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願番号】特願２０１１−１４７０６４（Ｐ２０１１−１４７０６４）
【出願日】平成２３年７月１日（２０１１．７．１）
【出願人】（３０３０１３７６３）ＮＥＣエンジニアリング株式会社 (651)
【Ｆターム（参考）】
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願日】平成２３年７月１日（２０１１．７．１）
【出願人】（３０３０１３７６３）ＮＥＣエンジニアリング株式会社 (651)
【Ｆターム（参考）】
[ Back to top ]