(57)【特許請求の範囲】
【請求項１】
Ｎ個（Ｎは正の整数）の符号ストリームを記憶するバッファと、
前記Ｎ個の符号ストリームの夫々に一対一対応し、夫々、対応する符号ストリームを復号化してＭビット幅（Ｍは正の整数）の部分シンボルを単位サイクル毎に逐次生成する、直列に多段接続されるＮ個のデコーダと、
を備え、
前記Ｎ個のデコーダのうちのｉ（２≦ｉ≦Ｎ、ｉは正の整数）段目のデコーダは、複数の確率モデルを記憶し、各単位サイクルにおいて、直前の単位サイクルにおいてｉ−１段目のデコーダによって生成された部分シンボルを含むｉ−１個の部分シンボルの入力を受け付けて、前記入力されたｉ−１個の部分シンボルに基づいて前記複数の確率モデルのうちの１つを選択し、前記選択した確率モデルを用いて１個の部分シンボルを生成し、前記生成した１個の部分シンボルを前記入力されたｉ−１個の部分シンボルとともに出力し、
前記Ｎ個の符号ストリームは、Ｎ個の部分シンボルからなる単位シンボルが複数配列されて構成される原データが部分シンボル毎に符号化されて生成されたデータであって、
前記単位シンボルの先頭からｉ番目の部分シンボルにかかる符号ストリームは、前記Ｎ個のデコーダのうちのｉ段目のデコーダに対応し、前記ｉ段目のデコーダが備える複数の確率モデルのうちの前記単位シンボルの先頭からｉ−１番目までの部分シンボルに基づいて定まる確率モデルを用いて符号化されたデータである、
ことを特徴とする復号化装置。 
【請求項２】
前記ｉ段目のデコーダは、前記自デコーダが生成した１個の部分シンボルを前記入力されたｉ−１個の部分シンボルの末尾に結合して出力する、
ことを特徴とする請求項１に記載の復号化装置。 
【請求項３】
前記ｉ段目のデコーダは、単位サイクル毎に、前記選択した確率モデルを自デコーダが生成した１個の部分シンボルに基づいて更新する、
ことを特徴とする請求項１に記載の復号化装置。 
【請求項４】
前記Ｎ個のデコーダのうちの１段目のデコーダは、２段目以降のデコーダが記憶する確率モデルとは異なる予め定められた確率モデルを用いて部分シンボルを生成して、当該生成した部分シンボルを出力する、
ことを特徴とする請求項１から請求項３の何れか一項に記載の復号化装置。 
【請求項５】
夫々Ｎ×Ｍビット幅（Ｎ、Ｍはともに正の整数）を有する複数の単位シンボルを、単位シンボルの先頭からｉ（１≦ｉ≦Ｎ）番目の部分シンボルはｉ番目の符号ストリームに属するように符号化して、Ｎ個の符号ストリームを生成する符号化ステップを備え、
前記符号化ステップは、
１つの部分シンボルを符号化する際、複数の確率モデルを相互に関連付けるＮ階層の階層構造であって、当該階層構造の各階層はＮ個の符号ストリームの夫々と一対一で対応付けられ、当該階層構造の葉側の階層に属する確率モデルは根側の階層に属する確率モデルと当該根側に属する確率モデルを用いて符号化される前記１つの部分シンボルと同一の単位シンボルに属する対応する他の部分シンボルの値とに基づいて特定されるように関連付けられる階層構造に基づいて、前記複数の確率モデルのうちの１つを特定する特定ステップと、
前記特定した確率モデルを用いて前記１つの部分シンボルを符号化する個別符号化ステップと、
を備えることを特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、復号化装置および符号化方法に関する。
【背景技術】
【０００２】
データを圧縮する手法として、算出符号を用いた符号化（算術符号化）が挙げられる。算術符号化は、０と１の間の区間を入力シンボルの出現確率に比例した小区間に分割していくことで入力シンボルの符号化を行う手法である。算術符号化によれば、着目している入力シンボルの直前に入力された入力シンボルにより指定された小区間を、着目している入力シンボルの出現確率に比例した小区間にさらに分割する工程が順次実行され、結果的に複数の入力シンボルがひとつの実数に符号化される。
【０００３】
また、算術符号の一つに、Range  Coderがある。Range  Coderによれば、１より大きな区間を用いることによって、整数に符号化することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第５５８３５００号明細書
【特許文献２】特開２００８−２８９１２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の一つの実施形態は、可及的に高速に符号の復号化を行うことができる復号化装置および当該復号化装置で復号化することができる符号を生成する符号化方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一つの実施形態によれば、復号化装置は、Ｎ個の符号ストリームを記憶するバッファと、直列に多段接続されているＮ個のデコーダを備えている。Ｎ個のデコーダは、夫々、前記Ｎ個の符号ストリームの夫々に一対一対応し、対応する符号ストリームを復号化してＭビット幅の部分シンボルを単位サイクル毎に逐次生成する。前記Ｎ個のデコーダのうちのｉ（ｉ≧２）段目のデコーダは、複数の確率モデルを記憶し、各単位サイクルにおいて、直前の単位サイクルにおいてｉ−１段目のデコーダによって生成された部分シンボルを含むｉ−１個の部分シンボルの入力を受け付けて、前記入力されたｉ−１個の部分シンボルに基づいて前記複数の確率モデルのうちの１つを選択し、前記選択した確率モデルを用いて１個の部分シンボルを生成し、前記生成した１個の部分シンボルを前記入力されたｉ−１個の部分シンボルとともに出力する。前記Ｎ個の符号ストリームは、Ｎ個の部分シンボルからなる単位シンボルが複数配列されて構成される原データが部分シンボル毎に符号化されて生成されたデータである。前記単位シンボルの先頭からｉ番目の部分シンボルにかかる符号ストリームは、前記Ｎ個のデコーダのうちのｉ段目のデコーダに対応し、前記ｉ段目のデコーダが備える複数の確率モデルのうちの前記単位シンボルの先頭からｉ−１番目までの部分シンボルに基づいて定まる確率モデルを用いて符号化されたデータである。
【図面の簡単な説明】
【０００７】
【図１】図１は、本発明の実施形態の復号化装置を備える画像再生装置の構成を示す図である。
【図２】図２は、元のデータから圧縮データが生成される様子を概要的に説明する図である。
【図３】図３は、元のデータから圧縮データが生成される様子を概要的に説明する図である。
【図４】図４は、デコンプレッション回路の構成を説明する図である。
【図５】図５は、Ｎ個のデコーダが原データを生成するタイミングを説明する図である。
【図６】図６は、デコーダの構成を説明する図である。
【図７】図７は、符号化装置をコンピュータを用いて実現する場合のハードウェア構成例を示す図である。
【図８】図８は、本発明の実施形態の符号化方法を説明するフローチャートである。
【図９】図９は、符号化装置にて実行される出現確率p0の更新処理を説明するフローチャートである。
【図１０】図１０は、画像再生装置の動作を説明するフローチャートである。
【図１１】図１１は、１つのデコーダが１つの符号データを復号化する動作を説明するフローチャートである。
【図１２】図１２は、デコーダコアにて実行される出現確率p0の更新処理を説明するフローチャートである。
【図１３】図１３は、本発明の実施形態のコンテキストアーキテクチャの別の例を示す図である。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態にかかる復号化装置および符号化方法を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。ここでは、一例として、本発明の実施形態の復号化装置をゲーム機などの画像再生装置に組み込まれて構成される場合について説明するが、本発明の実施形態の復号化装置の適用範囲は画像再生装置だけに限定されない。本発明の実施形態の復号化装置は、符号化されたデータを復号化する装置であればどのような装置にも適用することができる。
【０００９】
（第１の実施形態）
図１は、本発明の実施形態の復号化装置を備える画像再生装置の構成を示す図である。図示するように、画像再生装置１は、制御チップ２０、ＤＲＡＭ（Dynamic  Random  Access  Memory）３０、ＲＯＭ（Read  Only  Memory）４０、およびＬＣＤ（Liquid  Crystal  Monitor）パネル５０を備えている。ＲＯＭ４０は、画像データ（原データ１０）が符号化（圧縮）されて生成された圧縮データ１４を記憶している。制御チップ２０は、ＲＯＭ４０に格納されている圧縮データ１４を復号化して、復号化されて生成された原データ１０を元に画像フレームを生成し、生成した画像フレームをＬＣＤパネル５０に出力する。ＤＲＡＭ３０を、制御チップ２０により生成された画像フレームを蓄積するフレームバッファや、制御チップ２０が画像フレームを生成するためのワークメモリとして機能する。
【００１０】
制御チップ２０は、ＣＰＵ（Central  Processing  Unit）２１、ＧＰＵ（Graphics  Processing  Unit）２２、ＤＲＡＭコントローラ２３、ディスプレイコントローラ２４、ＤＭＡＣ（Direct  Memory  Access  Controller）２５、ＲＯＭコントローラ２６および本発明の実施形態の復号化装置としてのデコンプレッション回路１００を備えている。ＣＰＵ２１、ＧＰＵ２２、ＤＲＡＭコントローラ２３、制御バス２７およびサブバス２８は、夫々メインバス２９に接続されている。ＤＭＡＣ２５およびＲＯＭコントローラ２６は、制御バス２７およびサブバス２８の両方に接続されている。デコンプレッション回路１００は、制御バス２７およびＤＭＡＣ２５の両方に接続されている。
【００１１】
ＲＯＭコントローラ２６は、制御チップ２０がＲＯＭ４０にアクセスを行うためのインタフェース回路である。また、ＤＲＡＭコントローラ２３は、制御チップ２０がＤＲＡＭ３０にアクセスを行うためのインタフェース回路である。また、ディスプレイコントローラ２４は、制御チップ２０がＬＣＤパネル５０に画像フレームを表示するためのインタフェース回路である。
【００１２】
デコンプレッション回路１００は、圧縮データ１４を復号化して原データ１０を生成する。デコンプレッション回路１００の詳細な構成は後述する。
【００１３】
ＣＰＵ２１は画像再生装置１の全体の制御を行う。ＤＭＡＣ２５は、ＣＰＵ２１による制御の下で、ＲＯＭ４０に格納されている圧縮データ１４をＲＯＭコントローラ２６およびサブバス２８を介してデコンプレッション回路１００に転送したり、圧縮データ１４がデコンプレッション回路１００により復号化されて生成された原データ１０をサブバス２８、メインバス２９、およびＤＲＡＭコントローラ２３を介してＤＲＡＭ３０に転送したりする。
【００１４】
ＧＰＵ２２は、ＣＰＵ２１による制御の下で、ＤＲＡＭ３０に格納された原データ１０から画像フレームを生成し、生成した画像フレームをＤＲＡＭ３０に確保されたフレームバッファに格納する。ディスプレイコントローラ２４は、フレームバッファに格納された画像フレームをＬＣＤパネル５０に出力する。
【００１５】
ここで、圧縮データ１４は、本発明の実施形態の符号化方法によって原データ１０が符号化されて生成されるものである。具体的な符号化方法について後述する図７乃至図９において説明を行う。ここでは原データ１０から圧縮データ１４が生成される様子を概要的に説明するために図２および図３を用いる。なお、ここでは、一例として、圧縮データ１４は、Binary  Range  Coderによって生成されるものとする。
【００１６】
図２に示すように、圧縮データ１４が生成される元となるデータ（原データ１０）は、固定長ビットのシンボルＤを複数備えて構成される。ここでは、シンボルＤのビット長をＮとし、原データ１０はｎ＋１個のシンボルＤ０、Ｄ１、Ｄ２、〜、Ｄｎがこの順番で配列されて構成されるものとしている。ただし、Ｎ、ｎはともに正の整数である。
【００１７】
原データ１０は、シンボルＤを構成する夫々のビットが夫々異なるストリームデータに属するようにＮ個のストリームデータ（ストリームデータ１１１〜１１Ｎ）に分割される。個々のストリームデータは、シンボルＤに含まれる対応するビットが原データ１０におけるシンボルＤの配列順に配列されて構成されている。即ち、例えば、ストリームデータ１１ｉは、シンボルＤ０、Ｄ１、Ｄ２、〜、Ｄｎの夫々のｉ番目のビットがこの順番で配列されて構成される。なお、以降、ストリームデータ１１１〜１１Ｎをストリームデータ１１と総称することがある。また、ストリームデータを単にストリームということがある。
【００１８】
図３に示すように、分割されて生成された夫々のストリーム１１は、夫々異なるコンテキストを用いて符号化される。コンテキストとは、入力されたビットの出現確率を規定する確率モデルのことである。
【００１９】
図３の１３は、コンテキストアーキテクチャの一例を示している。この例によれば、コンテキストアーキテクチャ１３は、ストリーム１１１の符号化に用いられるコンテキストＡをルートとした二分木構造を有している。そして、ｉ番目のストリーム１１（ストリーム１１ｉ）は、ｉ階層目のコンテキストを用いて符号化される。ｉ階層目のコンテキストが複数存在する場合（この場合にはｉが２以上の値である場合）には、ｉ−１階層目で用いられたコンテキストに実線または一点鎖線で接続されたコンテキストが用いられる。ｉ−１階層目で符号化対象となったビットが「０」である場合には、実線で接続されたコンテキストが用いられ、ｉ−１階層目で符号化対象となったビットが「１」である場合には、一点鎖線で接続されたコンテキストが用いられる。このように、コンテキストアーキテクチャ１３は、複数の確率モデルを相互に関連付けるＮ階層の階層構造を備え、当該階層構造の各階層はＮ個のストリーム１１の夫々と一対一で対応付けられ、当該階層構造の葉側の階層（即ちコンテキストグループ１３Ｎ側のコンテキストグループ１３）に属する確率モデルは根側の階層（即ちコンテキストグループ１３１側のコンテキストグループ１３）に属する確率モデルと当該根側に属する確率モデルを用いて符号化される１つのビットと同一のシンボルＤに属する対応する他のビットの値とに基づいて特定されるように関連付けられている。
【００２０】
一つのシンボルＤｉに着目して説明する。シンボルＤｉの１番目のビットは、ストリーム１１１に含まれており、このビットの符号化にはコンテキストＡが用いられる。当該ビットが「０」である場合、ストリーム１１２に含まれる同一のシンボルＤｉにかかるビット（即ちシンボルＤｉの２番目のビット）は、コンテキストＢを用いて符号化される。シンボルＤｉの２番目のビットが「１」である場合、ストリーム１１３に含まれる同一のシンボルＤｉにかかるビット（即ちシンボルＤｉの３番目のビット）は、コンテキストＥを用いて符号化される。
【００２１】
このように、同一のシンボルＤに関し、ストリーム１１ｉの符号化に用いられるコンテキストは、ストリーム１１１〜ストリーム１１ｉ−１の夫々において入力された符号化対象のビットに応じて定められる。言い換えると、シンボルＤのｉ番目のビットを符号化する際に使用されるコンテキストは、当該シンボルＤの１番目からｉ−１番目の値、即ち符号化対象のビットよりも上位側のビットにより決定される。
【００２２】
なお、同一の階層に属する１以上のコンテキストをコンテキストグループと称する。即ち、ストリーム１１ｉがコンテキストグループ１３ｉに属するコンテキストを用いて符号化されることによって、符号データ（符号ストリーム）１２ｉが生成される。Ｎ個のストリーム１１から生成されたＮ個の符号データ１２１〜１２Ｎは、圧縮データ１４を構成する。なお、符号データ１２１〜１２Ｎを符号データ１２と総称することがある。
【００２３】
次に、本発明の実施形態の復号化装置について説明する。
本発明の実施形態によれば、デコンプレッション回路１００は、上記のように構成される圧縮データ１４を高速に復号化することができる。図４は、デコンプレッション回路１００の構成を説明する図である。
【００２４】
図４に示すように、デコンプレッション回路１００は、ＲＯＭ４０から読み出され、送られてきた圧縮データ１４をバッファリングするストリームバッファ１０１と、Ｎ個のデコーダ（デコーダ１０２１〜１０２Ｎ）とを備えている。以降、デコーダ１０２１〜１０２Ｎをデコーダ１０２と総称することがある。
【００２５】
デコーダ１０２１〜１０２Ｎは、コンテキストアーキテクチャ１３の階層構造に対応する順番で直列に多段接続されている。ｉ段目のデコーダ１０２ｉは、コンテキストグループ１３ｉに属するコンテキストを用いて復号化を行うことができるようになっている。ストリームバッファ１０１には、圧縮データ１４を構成するＮ個の符号データ１２１〜１２Ｎが並列にバッファリングされる。Ｎ個のデコーダ１０２１〜１０２Ｎは、ストリームバッファ１０１にバッファリングされているＮ個の符号データ１２１〜１２Ｎのうちの対応する符号データ１２を復号化して、対応するストリーム１１を構成するビットを単位サイクル毎に逐次生成する。デコーダ１０２の夫々は、自デコーダ１０２が復号化により生成した１ビットを前段のデコーダ１０２から送られてきた同一のシンボルＤにかかる復号化済みの値の最下位ビットに結合して後段のデコーダ１０２に送る。Ｎ段目のデコーダ１０２Ｎは、自デコーダ１０２Ｎが復号化して得たビットをＮ−１段目のデコーダ１０２Ｎ−１から送られてきたＮ−１ビットの値の最下位ビットに結合して、得られたＮビットの値を、復号化済みのシンボルＤとして出力する。
【００２６】
なお、１階層目のコンテキストグループ１３１を除き、コンテキストグループ１３は、複数のコンテキストを含んでいる。２段目以降のデコーダ１０２は、前段のデコーダ１０２から送られてきた同一のシンボルＤにかかる復号化済みの値に基づいて、複数のコンテキストのうちから使用するコンテキストを選択する。
【００２７】
ここで、デコーダ１０２１〜１０２Ｎは、夫々、対応する符号データ１２をパイプライン処理的に復号化することによって、１つのデコーダがＮビットのシンボルＤの列を順次復号化する場合に比べて高速に復号化することができる。図５は、Ｎ個のデコーダ１０２が原データ１０を生成するタイミングを説明する図である。
【００２８】
図５に示すように、デコーダ１０２１は、符号データ１２１を復号化することによって、ストリーム１１１を１ビットずつ出力する。デコーダ１０２２は、デコーダ１０２１が最初の１ビット（即ちシンボルＤ０の先頭の１ビット）を出力すると、当該出力された結果に基づいて、符号データ１２２からストリーム１１２の最初の１ビット（即ちシンボルＤ０の２番目のビット）を出力する。デコーダ１０２１は、デコーダ１０２２がシンボルＤ０の２番目のビットを出力するサイクルと同じサイクルにおいてシンボルＤ１の最初のビットを出力する。
【００２９】
このように、２段目以降のデコーダ１０２ｉは、各単位サイクルにおいて、１ビットの値を生成するとともに、直前の単位サイクルにおいてｉ−１段目のデコーダによって生成された値を含むシンボルＤの先頭のｉ−１ビット幅の値に、前記生成した１ビットの値を結合し、結合により生成されたシンボルＤの先頭のｉビット幅の値を出力するので、デコーダ１０２１〜１０２Ｎは、協働して、Ｎビット幅のシンボルＤを単位サイクル毎に一つずつ出力できる。即ち、１個のデコーダがＮビット幅のシンボルＤを１つずつシリアルに生成する場合に比べ、高速に復号化することができるようになる。
【００３０】
図６は、デコーダ１０２の構成を説明する図である。なお、ここでは、一例として、３段目のデコーダ１０２３の構成を説明する。
【００３１】
図示するように、デコーダ１０２３は、４つの確率テーブル記憶部１０３ａ〜１０３ｄと、選択回路１０４と、デコーダコア１０５と、コード／レンジ記憶部１０６と、フリップフロップ１０７とを備えている。
【００３２】
コード／レンジ記憶部１０６は、ストリームバッファ（バッファ）１０１から取り出した符号データ１２３のうちの処理対象データと、レンジとを一時記憶する。確率テーブル記憶部１０３ａ〜１０３ｄは、夫々異なるコンテキストにかかる出現確率を記憶する。選択回路１０４は、前段のデコーダ１０２２から送られてきた２ビットの復号化結果を選択信号として４つの確率テーブル記憶部１０３ａ〜１０３ｄのうちの一つを選択する。例えば、図３のコンテキストアーキテクチャ１３に則して説明すると、確率テーブル記憶部１０３ａ〜１０３ｄは、コンテキストＤにかかる出現確率、コンテキストＥにかかる出現確率、コンテキストＦにかかる出現確率、コンテキストＧにかかる確率を夫々記憶する。そして、例えば前段のデコーダ１０２２から送られてきた２ビットの復号化結果が「１０」であれば、選択回路１０４は、コンテキストＦの出現確率を記憶する確率テーブル記憶部１０３ｃを選択する。
【００３３】
なお、確率テーブル記憶部１０３の数は、デコーダ１０２が何番目の符号データ１２を復号化するものであるかによって変化する。例えば２番目の符号データ１２２を復号化するデコーダ１０２２は、確率テーブルＢおよびＣの２個を使用するので、２個の確率テーブル記憶部１０３を具備する。
【００３４】
デコーダコア１０５は、選択回路１０４が選択した確率テーブル記憶部１０３に格納されている出現確率と、コード／レンジ記憶部１０６に格納されているレンジとに基づいて、コード／レンジ記憶部１０６に格納されている符号データ１２３のうちの処理対象データを復号化する。復号化により得られた１ビットの値は、前段のデコーダ１０２２から送られてきた２ビットの復号化結果の末尾に結合されて後段のデコーダ１０２４に送られる。フリップフロップ１０７は、前段のデコーダ１０２２から送られてきた２ビットの復号化結果の出力タイミングとデコーダ１０２３が生成した１ビットの復号化結果の出力タイミングを合わせるために、前記２ビットの復号化結果を暫くの間だけ保持する。
【００３５】
次に、本発明の実施形態の符号化装置および符号化方法について説明する。
なお、圧縮データ１４は、例えばコンピュータ上で専用のプログラムを実行することによって生成される。図７は、圧縮データ１４を生成する符号化装置をコンピュータを用いて実現する場合のハードウェア構成例を示す図である。
【００３６】
図７に示すように、符号化装置２００は、ＣＰＵ２０１、ＲＡＭ２０２、ＲＯＭ３、入力装置２０４、表示装置２０５を備える。ＣＰＵ２０１、ＲＡＭ２０２、ＲＯＭ２０３、入力装置２０４、表示装置２０５は、バスラインを介して夫々接続されている。
【００３７】
表示装置２０５は、例えば液晶モニタなどの情報を表示可能な装置である。表示装置２０５は、ユーザに対する出力情報を表示する。入力装置２０４は、例えばマウスやキーボードを備えて構成され、ユーザからの符号化装置２００に対する操作情報が入力される。入力された操作情報は、ＣＰＵ２０１へ送られる。
【００３８】
ＲＯＭ２０３は、本発明の実施形態の符号化方法を実行するためのコンピュータプログラムである符号化プログラム２０６を記録する記録媒体である。ＣＰＵ２０１は、ＲＯＭ２０３から符号化プログラム２０６をバスラインを介して読み出して、ＲＡＭ２０２へロードし、ＲＡＭ２０２内にロードされた符号化プログラム２０６を実行する。原データ１０は、ＲＯＭ２０３や、図示しない外部記憶装置を介して入力される。ＣＰＵ２０１は、入力された原データ１０に対し、ＲＡＭ２０２にロードされた符号化プログラム２０６に基づいて後述する処理ステップを実行することによって、圧縮データ１４を生成する。ＣＰＵ２０１は生成した圧縮データ１４を、ＲＡＭ２０２や外部記憶装置に出力する。
【００３９】
なお、符号化プログラム２０６をインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、ＲＯＭ２０３の代わりに、外部記憶装置、着脱可能なメモリデバイス、光ディスク装置など、一時的でない有形の媒体を、符号化プログラム２０６のロード元となる記録媒体として適用することが可能である。
【００４０】
次に、本発明の実施形態の符号化方法を、図８および図９を用いて説明する。なお、当該符号化方法は、符号化装置２００が具備するＣＰＵ２０１が符号化プログラム２０６による制御の下で動作することによって実行される。以下、ＣＰＵ２０１を当該符号化方法の動作主体として説明する。
【００４１】
図８は、符号化装置２００を用いて実行される本発明の実施形態の符号化方法を説明するフローチャートである。まず、ＣＰＵ２０１は、原データ１０を分割して、Ｎ個のストリーム１１１〜１１Ｎを生成する（ステップＳ１）。そして、ＣＰＵ２０１は、ストリーム１１１〜１１Ｎを符号化するための下限値（low）およびレンジ（range）を初期化する（ステップＳ２）。ここでは、ＣＰＵ２０１は、次の式のように初期化する。
low=0x00000000      式（１）
range=0xffffffff      式（２）
【００４２】
なお、lowおよびrangeは、ストリーム１１毎に用意される。ストリーム１１毎のこれらの値は、例えばＲＡＭ２０２内に格納される。
【００４３】
ＣＰＵ２０１は、ストリーム１１ｉに含まれるビット列のうちのシンボルＤｊに属するビットを着目ビット（indt）とし、ｉ、ｊをループインデックスとして用いてステップＳ４〜ステップＳ１０の処理を行う。その為に、ＣＰＵ２０１は、まず、ループインデックスｉ、ｊを、次のように初期化する（ステップＳ３）。
i=1      式（３）
j=0      式（４）
【００４４】
続いて、ＣＰＵ２０１は、コンテキストグループ１３ｉから、コンテキストを１つ選択する（ステップＳ４）。ステップＳ４において、ｉ＝１が満たされる場合には、ＣＰＵ２０１は、コンテキストＡを選択する。ｉ≧２が満たされる場合には、ＣＰＵ２０１は、シンボルＤｊの１番目からｉ−１番目までの値に基づいて、複数存在するコンテキストから１つのコンテキストを選択する。ステップＳ４において選択されたコンテキストには、値「０」の出現確率p0が対応付けられており、当該コンテキストに対応付けられている出現確率p0は、ステップＳ５〜ステップＳ８の処理にて使用される。なお、出現確率p0は、予め決められたビット数（pwdth）により表現されるものとする。pwdthは、コンテキスト間で共通する。
【００４５】
続いて、ＣＰＵ２０１は、indt=0が満たされるか否かを判定する（ステップＳ５）。indt=0が満たされる場合には（ステップＳ５、Ｙｅｓ）、ＣＰＵ２０１は、インデックスｉにかかるrangeをp0の表現ビット数（pwdth）だけ右にシフトし、シフト後のrangeにp0を乗算して得られる値でrangeを更新する（ステップＳ６）。一方、indt=1が満たされる場合には（ステップＳ５、Ｎｏ）、ＣＰＵ２０１は、インデックスｉにかかるrangeをpwdthだけ右にシフトし、シフト後のrangeにp0を乗算して得られる値でrangeを更新し、インデックスｉにかかるlowに更新後のrangeを加算して得られる値でlowを更新する（ステップＳ７）。
【００４６】
ステップＳ６またはステップＳ７の処理の後、ＣＰＵ２０１は、p0の更新処理を実行する（ステップＳ８）。ステップＳ８の処理にて更新されるp0は、ステップＳ４にて選択されたコンテキストにかかる出現確率p0である。
【００４７】
図９は、ステップＳ８において実行される出現確率p0の更新処理を説明するフローチャートである。まず、ＣＰＵ２０１は、indt=0が満たされるか否かを判定する（ステップＳ２１）。indt=0が満たされる場合には（ステップＳ２１、Ｙｅｓ）、ＣＰＵ２０１は、p0を値「３２」で除算した値をp0に加算し、得られた値でp0を更新する（ステップＳ２２）。一方、indt=1が満たされる場合には（ステップＳ２１、Ｎｏ）、ＣＰＵ２０１は、値「１」からp0を減算して得られる値を値「３２」で除算し、p0から前記除算により得られた値を減算し、得られた値でp0を更新する（ステップＳ２３）。ＣＰＵ２０１は、ステップＳ２２またはステップ２３の処理により、p0の更新処理を終了する。
【００４８】
ＣＰＵ２０１は、ステップＳ８の処理の後、range＜0x1000000が満たされるか否かを判定する（ステップＳ９）。range＜0x1000000が満たされる場合には（ステップＳ９、Ｙｅｓ）、ＣＰＵ２０１は、lowを左に８ビットだけシフトして得られる値でlowを更新し、rangeを左に８ビットだけシフトして得られる値でrangeを更新し、更新後のlowを右に２４ビットだけシフトして得られる値を符号データ１２ｉの一部（code）として出力する（ステップＳ１０）。range＜0x1000000が満たされない場合には（ステップＳ９、Ｎｏ）、ステップＳ１０の処理がスキップされる。
【００４９】
続いて、ＣＰＵ２０１は、ｉ=Nが満たされるか否かを判定する（ステップＳ１１）。ｉ=Nが満たされない場合には（ステップＳ１１、Ｎｏ）、ＣＰＵ２０１は、ｉを「１」だけインクリメントして（ステップＳ１２）、ステップＳ４の処理を実行する。
【００５０】
ｉ=Nが満たされる場合には（ステップＳ１１、Ｙｅｓ）、ＣＰＵ２０１は、j=nが満たされるか否かを判定する（ステップＳ１３）。j=nが満たされない場合には（ステップＳ１３、Ｎｏ）、ＣＰＵ２０１は、jを「１」だけインクリメントするとともにiを「１」に初期化して（ステップＳ１４）、ステップＳ４の処理を実行する。
【００５１】
j=nが満たされる場合には（ステップＳ１３、Ｙｅｓ）、ＣＰＵ２０１は、全ストリーム１１１〜１１Ｎについてlowを符号データ１２１〜１２Ｎの残りの部分として出力する（ステップＳ１５）。そして、ＣＰＵ２０１は、ステップＳ１０において出力した１つ以上のcodeとステップＳ１５において出力したcodeとをループインデックス別に接続して、符号データ１２１〜１２Ｎの夫々を生成し（ステップＳ１６）、動作を終了する。
【００５２】
次に、図１０〜１２を参照して、本発明の実施形態の復号化方法を説明する。図１０は、図１に示す画像再生装置１の動作を説明するフローチャートである。
【００５３】
図１０に示すように、まず、ＣＰＵ２１は、制御バス２７を介してデコンプレッション回路１００およびＲＯＭコントローラ２６の初期設定を実行する（ステップＳ３１）。そして、ＣＰＵ２１は、制御バス２７を介してＤＭＡＣ２５を起動する（ステップＳ３２）。ＤＭＡＣ２５は、サブバス２８を介してＲＯＭコントローラ２６に圧縮データ１４の読み出し要求を発行する（ステップＳ３３）。読み出し要求を受信したＲＯＭコントローラ２６は、ＲＯＭ４０から圧縮データ１４を読み出して、読み出した圧縮データ１４をＤＭＡＣ２５に返す（ステップＳ３４）。ＤＭＡＣ２５は、受け取った圧縮データ１４をデコンプレッション回路１００に渡す（ステップＳ３５）。デコンプレッション回路１００は、受け取った圧縮データ１４の復号化を行い、復号化して得られた原データ１０をＤＭＡＣ２５に返す（ステップＳ３６）。ＤＭＡＣ２５は、受け取った復号化後の原データ１０をサブバス２８、メインバス２９、およびＤＲＡＭコントローラ２３を介してＤＲＡＭ３０に書き込む（ステップＳ３７）。ＣＰＵ２１およびＧＰＵ２２は、協働して、ＤＲＡＭ３０に書き込まれた原データ１０から画像フレームを生成し、生成した画像フレームをＤＲＡＭ３０に確保されているフレームバッファに格納する（ステップＳ３８）。ディスプレイコントローラ２４は、フレームバッファから画像フレームを読み出して、読み出した画像フレームをＬＣＤパネル５０に出力し（ステップＳ３９）、画像再生装置１は動作を終了する。
【００５４】
ステップＳ３６の処理においてデコンプレッション回路１００が圧縮データ１４を復号化する際には、デコーダ１０２１〜１０２Ｎは、夫々、対応する符号データ１２をパイプライン処理的に復号化する。図１１は、図６に示す１つのデコーダ１０２が１つの符号データ１２を復号化する動作を説明するフローチャートである。
【００５５】
図１１に示すように、まず、デコーダコア１０５は、自デコンプレッション回路１００が初期状態であるか否かを判定する（ステップＳ４１）。初期状態とは、ステップＳ３１の処理によりＣＰＵ２１によって初期設定された後で、復号化を開始する前の状態を指す。なお、初期状態においては、コード／レンジ記憶部１０６には、式（１）および式（２）を用いて初期化されたrangeおよびlowが格納されている。
【００５６】
デコンプレッション回路１００が初期状態である場合には（ステップＳ４１、Ｙｅｓ）、デコーダコア１０５は、ストリームバッファ１０１に送られてきた圧縮データ１４に含まれる符号データ１２１〜１２Ｎのうちの、自デコーダ１０２に対応する符号データの先頭の４バイトを取り出して、取り出した４バイトのデータをコード／レンジ記憶部１０６にセットする（ステップＳ４２）。デコーダコア１０５は、ステップＳ４２の処理によりコード／レンジ記憶部１０６にセットしたデータを、後の処理において、変数「code」として使用する。デコンプレッション回路１００が初期状態ではない場合には（ステップＳ４１、Ｎｏ）、デコーダコア１０５は、ストリームバッファ１０１に格納されている対応する符号データから１バイトのデータを取り出して、取り出した１バイトのデータを、既にコード／レンジ記憶部１０６に格納されているcodeを構成する値の最も下位側の１バイトにセットする（ステップＳ４３）。
【００５７】
ステップＳ４２またはステップＳ４３の処理の後、デコーダ１０２は、前段のデコーダ１０２から復号結果を受信し（ステップＳ４４）、選択回路１０４は、受信した復号結果を選択信号として用いて、複数の確率テーブル記憶部１０３のうちの１つを選択する（ステップＳ４５）。複数の確率テーブル記憶部１０３は、「０」の出現確率p0を夫々記憶しており、ステップＳ４５により選択された確率テーブル記憶部１０３は、自記憶部１０３が記憶するp0を選択回路１０４を介してデコーダコア１０５に入力する。なお、前段のデコーダ１０２から送られてきた復号結果は、フリップフロップ１０７にラッチされる。
【００５８】
続いて、デコーダコア１０５は、rangeを右にpwdthだけシフトするとともに、シフト後のrangeにp0を乗算した値でrangeを更新する（ステップＳ４６）。
【００５９】
そして、デコーダコア１０５は、code-low＜rangeが満たされるか否かを判定する（ステップＳ４７）。code-low＜rangeが満たされる場合には（ステップＳ４７、Ｙｅｓ）、デコーダコア１０５は、自デコーダ１０２にかかる復号化結果（decoded  data）を「０」とし、rangeにp0を乗算した値でrangeを更新する（ステップＳ４８）。デコーダ１０２は、フリップフロップ１０７にラッチしておいた復号化結果の最下位ビット側に、decoded  dataを結合して、結合して得られる複数ビットの復号化結果を出力する（ステップＳ５０）。
【００６０】
code-low＜rangeが満たされない場合には（ステップＳ４７、Ｎｏ）、デコーダコア１０５は、decoded  data=1とし、rangeにp0を乗算した値でrangeを更新するとともに、lowに更新後のrangeを加算して得られる値でlowを更新する（ステップＳ４９）。ステップＳ４９の処理の後、デコーダ１０２は、ステップＳ５０の処理を実行する。
【００６１】
ステップＳ５０の処理の後、デコーダコア１０５は、ステップＳ４５により選択された確率テーブル記憶部１０３に格納されているp0の更新処理を実行する（ステップＳ５１）。
【００６２】
図１２は、ステップＳ５１において実行される出現確率p0の更新処理を説明するフローチャートである。まず、デコーダコア１０５は、decoded  data=0が満たされるか否かを判定する（ステップＳ６１）。decoded  data=0が満たされる場合には（ステップＳ６１、Ｙｅｓ）、デコーダコア１０５は、p0を値「３２」で除算した値をp0に加算し、得られた値でp0を更新する（ステップＳ６２）。一方、decoded  data=1が満たされる場合には（ステップＳ６１、Ｎｏ）、デコーダコア１０５は、値「１」からp0を減算して得られる値を値「３２」で除算し、p0から前記除算により得られた値を減算し、得られた値でp0を更新する（ステップＳ６３）。デコーダコア１０５は、ステップＳ６２またはステップ６３の処理により、p0の更新処理を終了する。
【００６３】
ステップＳ５１の処理の後、デコーダコア１０５は、range＜0x1000000が満たされるか否かを判定する（ステップＳ５２）。range＜0x1000000が満たされる場合には（ステップＳ５２、Ｙｅｓ）、デコーダコア１０５は、codeを左に８ビットだけシフトして得られる値でcodeを更新し、lowを左に８ビットだけシフトして得られる値でlowを更新し、rangeを左に８ビットだけシフトして得られる値でrangeを更新する（ステップＳ５３）。ステップＳ５３の処理の後、デコーダコア１０５は、ステップＳ４１の処理を実行する。range＜0x1000000が満たされない場合には（ステップＳ５２、Ｎｏ）、ステップＳ４４の処理が実行される。
【００６４】
このように、１つのデコーダ１０２は、自デコーダ１０２が復号化して得た１ビットのdecoded  dataを、前段のデコーダ１０２から入力されたシンボルＤの一部を構成するビット列の末尾に結合する。これによって、Ｎ個のデコーダ１０２１〜１０２Ｎは、協働して、Ｎ個の符号データ１２１〜１２Ｎをパイプライン処理的に復号化して、原データ１０を構成するシンボルＤを連続的に生成することができる。生成されたシンボルＤは、ステップＳ３６〜ステップＳ３７の処理により逐次ＤＲＡＭ３０に格納され、ＤＲＡＭ３０上で原データ１０が復元される。
【００６５】
なお、以上の説明においては、本発明の実施形態の符号化／復号化に用いられるコンテキストアーキテクチャ１３は二分木構造を有するとして説明したが、本発明の実施形態に適用できるコンテキストアーキテクチャ１３はこれに限定されない。以下の２つの条件を満たすコンテキストアーキテクチャであれば適用可能である。
（１）コンテキストアーキテクチャは、複数のコンテキスト間の対応関係がＮ個のストリーム１１１〜１１Ｎに一対一で対応するＮ個の階層の階層構造で記述されること。
（２）階層ｉ（ｉは１〜Ｎ）のコンテキストの選択に、階層ｊ(ただしｊ>ｉ)のストリーム１１ｊの値が影響しないこと。
【００６６】
図１３は、本発明の実施形態のコンテキストアーキテクチャの別の例を示す図である。この例によれば、コンテキストアーキテクチャ１３は、１段目のコンテキストグループ１３１から３段目のコンテキストグループ１３３に属する複数のコンテキストは、二分岐構造を形成している。しかしながら、４段目のコンテキストグループ１３４は、２つのコンテキスト（コンテキストＨおよびコンテキストＩ）を有している。そして、コンテキストＨは、３段目のコンテキストＤ〜Ｇの夫々から実線で共通接続され、コンテキストＩは、コンテキストＤ〜Ｇの夫々から一点鎖線で共通接続されている。５段目のコンテキストグループ１３５は、４つのコンテキスト（コンテキストＪ〜Ｍ）を有している。そして、コンテキストＪはコンテキストＨに実線で接続され、コンテキストＫはコンテキストＨに一点鎖線で接続されている。コンテキストＬはコンテキストＩに実線で接続され、コンテキストＭはコンテキストＩに一点鎖線で接続されている。
【００６７】
なお、図３に示したコンテキストアーキテクチャ１３の例のように二分木構造を有するコンテキストアーキテクチャを採用した場合には、デコンプレッション回路１００に具備せしめる確率テーブル記憶部１０３の数がＮの数に応じて増加する。図１３に示したコンテキストアーキテクチャ１３のように、二分木構造を採用した場合に比べてコンテキストの数を減少させることによって、必要となる確率テーブル記憶部１０３の数を減少せしめることができる。
【００６８】
なお、条件（１）は、階層の順番は必ずしもシンボルＤを構成する各ビットの並び順に一致していなくてもよいということを示している。例えば、シンボルＤの３番目のビットが最上段のコンテキストグループ１３１を用いて符号化されるようにしてもよい。
【００６９】
また、本発明の実施形態においては、符号化／復号化のための符号としてbinary  Range  Coderが採用される例を説明したが、符号化／復号化の手法には、binary  Range  Coder以外の算術符号など、他の符号を採用することが可能である。
【００７０】
また、シンボルＤを構成する各ビットからストリーム１１の夫々が生成されるものとして説明したが、シンボルＤをＮ×Ｍビットの固定長で構成し、Ｍビット幅のデータ（部分シンボル）毎に夫々ストリーム１１を生成するようにしてもよい。その場合には、デコーダ１０２の夫々は、単位サイクル当たりにＭビット幅の部分シンボルを生成するようにするとよい。
【００７１】
以上述べたように、本発明の実施形態によれば、デコンプレッション回路１００は、Ｎ個の符号データ１２１〜１２Ｎを記憶するストリームバッファ１０１と、Ｎ個の符号データ１２１〜１２Ｎの夫々に一対一対応し、夫々、対応する符号データ１２を復号化してＭビット幅の部分シンボルを単位サイクル毎に逐次生成する、直列に多段接続されるＮ個のデコーダ１０２１〜１０２Ｎと、を備え、Ｎ個のデコーダ１０２１〜１０２Ｎのうちのｉ（ｉ≧２）段目のデコーダ１２ｉは、複数の確率モデルを記憶し、各単位サイクルにおいて、直前の単位サイクルにおいてｉ−１段目のデコーダ１０２ｉ−１によって生成された部分シンボルを含むｉ−１個の部分シンボルの入力を受け付けて、入力されたｉ−１個の部分シンボルに基づいて複数の確率モデルのうちの１つを選択し、選択した確率モデルを用いて１個の部分シンボルを生成し、生成した１個の部分シンボルを前記入力されたｉ−１個の部分シンボルとともに出力する、ように構成したので、Ｎ個のデコーダ１０２１〜１０２Ｎは協働して単位シンボルを単位サイクル毎に生成することができるので、１個のデコーダが１個の単位シンボルを逐次生成する場合に比べて高速に復号化することができる。即ち、デコンプレッション回路１００は、可及的に高速に符号の復号化を行うことができる。
【００７２】
また、ｉ段目のデコーダ１２iは、自デコーダ１２iが生成した１個の部分シンボルを前記入力されたｉ−１個の部分シンボルの末尾に結合して出力する、ように構成したので、Ｎ個のデコーダ１０２１〜１０２Ｎは、協働して、シンボルＤの先頭から部分シンボルを順次復号化することができる。
【００７３】
また、Ｎ個のデコーダ１０２１〜１０２Ｎの夫々は、単位サイクル毎に、前記選択した確率モデルを自デコーダ１０２が生成した１個の部分シンボルに基づいて更新する、ように構成したので、確率モデルが固定されている場合に比べて高圧縮率の圧縮データ１４を扱うことができるようになる。
【００７４】
また、Ｎ個の符号データ１２は、Ｎ個の部分シンボルからなるシンボルＤ（単位シンボル）が複数配列されて構成される原データ１０が部分シンボル毎に符号化されて生成されたデータであって、シンボルＤの先頭からｉ番目の部分シンボルにかかる符号データ１２ｉは、前記Ｎ個のデコーダのうちのｉ段目のデコーダに対応し、前記ｉ段目のデコーダ１０２ｉが備える複数の確率モデルのうちのシンボルＤの先頭からｉ−１番目までの部分シンボルに基づいて定まる確率モデルを用いて符号化されたデータであるので、Ｎ個のデコーダ１０２１〜１０２Ｎは、協働して、シンボルＤの先頭から部分シンボルを順次復号化することができる。
【００７５】
以上、本発明の実施形態を説明したが、この実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。この新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。この実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７６】
１０  原データ、１１１〜１１Ｎ  ストリームデータ、１２１〜１２Ｎ  符号データ、１３  コンテキストアーキテクチャ、１３１〜１３Ｎ  コンテキストグループ、１４  圧縮データ、２０  制御チップ、２４  ディスプレイコントローラ、２５  ＤＭＡＣ、３０  ＤＲＡＭ、４０  ＲＯＭ、５０  ＬＣＤパネル、１００  デコンプレッション回路、１０１  ストリームバッファ、１０２１〜１０２Ｎ  デコーダ、１０３ａ〜１０３ｄ  確率テーブル記憶部、１０４  選択回路、１０５  デコーダコア、１０６  コード／レンジ記憶部、１０７  フリップフロップ、２００  符号化装置、２０１  ＣＰＵ、２０６  符号化プログラム、１０２１〜１０２Ｎ  デコーダ。
【図１】
0005703204.tif 000002
【図２】
0005703204.tif 000003
【図３】
0005703204.tif 000004
【図４】
0005703204.tif 000005
【図５】
0005703204.tif 000006
【図６】
0005703204.tif 000007
【図７】
0005703204.tif 000008
【図８】
0005703204.tif 000009
【図９】
0005703204.tif 000010
【図１０】
0005703204.tif 000011
【図１１】
0005703204.tif 000012
【図１２】
0005703204.tif 000013
【図１３】
0005703204.tif 000014