(57)【要約】【課題】復号処理の際の処理速度を向上させることが可能なデータ処理装置を提供する。【解決手段】入力ビットストリームを復号処理する際に、入力ビットストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番にそのビットデータが所定値「０」と一致するか否かの判断分岐がなされるように構築されたツリー構造を用いる。また、入力ビットストリームにおいて１ビットずつ順番に、そのような判断分岐の判定を行う。これにより、必要最小限の判断分岐によって、判定対象のビットパターンに対応するシンボルデータの出力が可能となる。【選択図】図２
2010021620.tif 000002
【特許請求の範囲】
【請求項１】
符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番に、そのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されたツリー構造を構成する構成部と、
前記符号化ストリームを復号処理する際に、前記構成部により構成されたツリー構造を用いて、前記符号化ストリームにおいて１ビットずつ順番に前記判断分岐の判定を行うことにより、その判定対象のビットパターンに対応するシンボルデータを出力する判定部と
を備えたデータ処理装置。
【請求項２】
前記ツリー構造は、Ｎビット（Ｎ；１以上の整数）のビットパターンに対応するシンボルデータの出力の際に、Ｎ回の判断分岐がなされるように構築されている
請求項１に記載のデータ処理装置。
【請求項３】
前記判定部による判断分岐の度に、前記符号化ストリームから１ビットずつ順番にビットデータを読み込み、そのビットデータを前記判定部へ供給する読み込み部を備えた
請求項１に記載のデータ処理装置。
【請求項４】
前記符号化ストリームが、可変長符号により符号化されたものである
請求項１に記載のデータ処理装置。
【請求項５】
符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番に、そのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されたツリー構造を構成する構成ステップと、
前記符号化ストリームを復号処理する際に、前記構成ステップにおいて構成されたツリー構造を用いて、前記符号化ストリームにおいて１ビットずつ順番に前記判断分岐の判定を行うことにより、その判定対象のビットパターンに対応するシンボルデータを出力する判定ステップと
を含むデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化されたビットストリームに対して復号処理を行うデータ処理装置およびデータ処理方法に関する。
【背景技術】
【０００２】
可変長符号は、情報圧縮を実現する際の基本的な技術のひとつであり、その原理は、「出現頻度の高いシンボルには短い符号を割り当て、逆に出願頻度の低いシンボルには長い符号を割り当てる」ことにある。例えば、英語の文章をコンピュータが扱うデータとして表す場合、通常、１シンボル（１文字）を８ビットで表すが、これはどの文字も同じビット数で表す固定長符号である。これに対して、可変長符号を用いて情報圧縮を行う場合、出現頻度の高い文字（例えば「ｅ」）には短い符号（例えば２ビット）が割り当てられ、逆に出現頻度の低い文字（例えば「ｑ」）には長い符号（例えば１４ビット）が割り当てられる。仮に元の文章が完全にランダムな文字の羅列であるならば圧縮の効果は得られないが、通常、英語の文章には文字の出現確率に偏りがあり、「ｅ」が出現する確率は高く、「ｑ」が出現する確率は低い。したがって、このような可変長符号を用いることによって、文章全体を表すビット量を削減することができる。このようにして可変長符号は、音声や画像のデータ圧縮など、様々な分野で利用されている。
【０００３】
可変長符号を利用した技術の典型例が、ＭＰＥＧ（Moving Picture Experts Group）に代表されるデジタル画像符号化技術である。ＭＰＥＧ復号器では、ＭＰＥＧ符号化された入力ビットストリームから可変長符号により圧縮された符号が取り出され、それが復号されることにより、画像を構成するための各種情報が得られるようになっている。
【０００４】
このようなＭＰＥＧ復号器に関して、例えばＭＰＥＧ−４の規格書（非特許文献１参照）によれば、各種情報を表す可変長符号の一覧を記述した可変長符号テーブルを用意し、入力ビットストリームから読み出した符号と一致する符号（ビットパターン）を探すという手法が考えられる。
【０００５】
【非特許文献１】ＩＳＯ／ＩＥＣ  １４４９６−２：２００４  Ｉｎｆｏｒｍａｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ  ―  Ｃｏｄｉｎｇ  ｏｆ  ａｕｄｉｏ−ｖｉｓｕａｌ  ｏｂｊｅｃｔｓ  ―  Ｐａｒｔ  ２：  Ｖｉｓｕａｌ、２００４年６月１日発行
【発明の開示】
【発明が解決しようとする課題】
【０００６】
この手法では、上記したように、使用される可変長符号を全て記述した可変長符号テーブルが用意される。これには、「可変長符号が表すシンボル」、「可変長符号のビットパターン」および「可変長符号の長さ」の一覧が含まれる。そして、入力ビットストリームから１ビットずつ読み込み、読み込んだビットパターンとその長さとが共に一致する符号を、可変長符号テーブル上で探すようになっている。見つかった場合には、その符号が表すシンボルが復号結果として出力される。一方、見つからなかった場合には、次の１ビットを読み込んでビットパターンに追加すると共にビットパターンの長さに１を加え、同様の処理（比較処理）が再度行われる。このようにして、符号が見つかるまで同様の比較処理が繰り返されるようになっている。
【０００７】
ところが、この手法では、入力ビットストリームから１ビット読み出す度に、可変長符号テーブルに記述されている全ての符号（ビットパターン）との比較処理を行う必要がある。そのため、比較結果の一致しない無駄な処理が多くなるという問題があった。
【０００８】
なお、このような問題点は、これまで説明したような可変長符号の場合だけでなく、固定長符号の場合にも同様に生じうるものである。
【０００９】
本発明はかかる問題点に鑑みてなされたもので、その目的は、復号処理の際の処理速度を向上させることが可能なデータ処理装置およびデータ処理方法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明のデータ処理装置は、符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番に、そのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されたツリー構造を構成する構成部と、符号化ストリームを復号処理する際に、構成部により構成されたツリー構造を用いて、符号化ストリームにおいて１ビットずつ順番に上記判断分岐の判定を行うことにより、その判定対象のビットパターンに対応するシンボルデータを出力する判定部とを備えたものである。
【００１１】
本発明のデータ処理方法は、符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番に、そのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されたツリー構造を構成する構成ステップと、符号化ストリームを復号処理する際に、構成ステップにおいて構成されたツリー構造を用いて、符号化ストリームにおいて１ビットずつ順番に上記判断分岐の判定を行うことにより、その判定対象のビットパターンに対応するシンボルデータを出力する判定ステップとを含むようにしたものである。
【００１２】
本発明のデータ処理装置およびデータ処理方法では、符号化ストリームを復号処理する際に、所定のツリー構造を用いることにより、判定対象のビットパターンに対応するシンボルデータが出力される。ここで、このツリー構造では、符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番にそのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されていると共に、符号化ストリームにおいて１ビットずつ順番にそのような判断分岐の判定が行われることにより、従来のような無駄な繰り返し処理（比較処理）がなくなり、必要最小限の判断分岐によって対応するシンボルデータの出力が可能となる。
【発明の効果】
【００１３】
本発明のデータ処理装置またはデータ処理方法によれば、符号化ストリームを復号処理する際に、符号化ストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番にそのビットデータが所定値と一致するか否かの判断分岐がなされるように構築されたツリー構造を用いると共に、符号化ストリームにおいて１ビットずつ順番にそのような判断分岐の判定を行うようにしたので、必要最小限の判断分岐によって、判定対象のビットパターンに対応するシンボルデータの出力が可能となる。よって、無駄な繰り返し処理が必要な従来と比べ、復号処理の際の処理速度を向上させることが可能となる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１５】
図１は、本発明の一実施の形態に係るデータ処理装置（後述する可変長符号復号部１１）を備えたＭＰＥＧ復号器（ＭＰＥＧ復号器１）の概略構成を表すものである。このＭＰＥＧ復号器１は、可変長符号方式により符号化された入力ビットストリームに対して復号処理を行い、出力画像を生成および出力するものである。ＭＰＥＧ復号器１は、本実施の形態に係る可変長符号復号部１１と、逆スキャン部１２と、逆量子化部１３と、逆離散コサイン変換部１４と、動き補償部１５と、画像メモリ１６とから構成されている。なお、本発明の一実施の形態に係るデータ処理方法は、本実施の形態の可変長符号復号部１１によって具現化されるので、以下併せて説明する。
【００１６】
（ＭＰＥＧ復号器１の構成）
可変長符号復号部１１は、入力ビットストリーム（符号化ストリーム）から可変長符号により圧縮された符号（ビットパターン）を取り出すと共に、取り出した符号に対して復号処理を行うことにより、その符号に対応するシンボル（出力シンボル）を出力するものである。なお、この可変等符号復号部１１の詳細構成については、後述する（図２）。
【００１７】
逆スキャン部１２は、可変長符号復号部１１からの出力シンボルに基づいて、ブロックごとの情報を逆スキャンによって整列する処理を行うものである。
【００１８】
逆量子化部１３は、逆スキャン部１２から出力されたデータに対して逆量子化処理を行うことにより、離散コサイン（ＤＣＴ；Discrete Cosine Transformation）変換の係数情報を得るものである。
【００１９】
逆離散コサイン変換部１４は、逆量子化部１３により得られた係数情報に対して逆離散コサイン（逆ＤＣＴ）変換を行うことにより、係数情報を画像情報に変換するものである。
【００２０】
動き補償部１５および画像メモリ１６は、入力ビットストリームにおいてフレーム間予測が使用されている場合に、用いられるものである。具体的には、逆離散コサイン変換部１４により得られた画像情報において、動きベクトルと、過去に復号された参照画像とを基にして予測画像を構成すると共に、ここまでの処理で得られた画像と合成する動き補償処理が行われることにより、最終的な出力画像が得られるようになっている。
【００２１】
（可変長符号復号部１１の構成）
次に、図２を参照して、可変長符号復号部１１の詳細構成について説明する。
【００２２】
この可変長符号復号部１１は、ビット読み込み部１１１と、ツリー構成部１１２と、１ビット判定部１１３と、シンボル出力部１１４と、制御部１１５とから構成されている。
【００２３】
ビット読み込み部１１１は、後述する１ビット判定部１１３による判断分岐の度に、入力ビットストリームから１ビットずつ順番にビットデータを読み込み、そのビットデータを１ビット判定部１１３へ供給するものである。
【００２４】
ツリー構成部１１２は、例えば図３（Ａ）や図３（Ｂ）に示したような可変長符号テーブル２１，２２に対応して個別に構築された所定のツリー構造を構成するものである。ここで、これら可変長テーブル２１，２２では、入力ビットストリームにおいて出現し得る全ての符号（ビットパターン）と、符号長さ（ビット数）と、その符号に対応する復号結果であるシンボル（出力シンボル）とが、それぞれ対応づけて構成されている。
【００２５】
これに対し、本実施の形態のツリー構造は、詳細は後述（図４、図９および図１０）するが、入力ビットストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番に、そのビットデータが所定値（ここでは、「０」）と一致するか否かの判断分岐がなされるように、構築されている。また、このツリー構造は、Ｎビット（Ｎ；１以上の整数）のビットパターンに対応するシンボルデータ（出力シンボル）の出力の際に、（Ｎ−１）回またはＮ回の判断分岐がなされるように構築されている
【００２６】
１ビット判定部１１３は、入力ビットストリームを復号処理する際に、ツリー構成部１１２により構成された上記ツリー構造を用いて、ビット読み込み部１１１から供給されるビットデータを基に、１ビットずつ順番に上記判断分岐（各ビットデータが「０」であるか否かの判断分岐）の判定を行うものである。なお、この１ビット判定部１１３による判定動作の詳細については、後述する（図４、図９および図１０）。
【００２７】
シンボル出力部１１４は、１ビット判定部１１３による判断分岐の判定結果に応じて、その判定対象のビットパターンに対応するシンボルデータ（出力シンボル）を出力するものである。
【００２８】
制御部１１５は、ビット読み込み部１１１による読み込み動作、１ビット判定部１１３による判定動作、およびシンボル出力部１１４による出力動作をそれぞれ、適宜制御するものである。
【００２９】
ここで、ビット読み込み部１１１が、本発明における「読み込み部」の一具体例に対応する。また、ツリー構成部１１２が、本発明における「構成部」の一具体例に対応する。また、１ビット判定部１１３およびシンボル出力部１１４が、本発明における「判定部」の一具体例に対応する。
【００３０】
次に、本実施の形態のＭＰＥＧ復号器１の動作について説明する。
【００３１】
（ＭＰＥＧ復号器１の基本動作）
まず、図１を参照して、ＭＰＥＧ復号器１の基本動作について説明する。このＭＰＥＧ復号器１では、まず、可変長符号復号部１１において、入力ビットストリームから可変長符号により圧縮された符号が取り出されて復号処理が行われ、その符号に対応するシンボル（出力シンボル）が出力される。次に、逆スキャン部１２では、その出力シンボルに基づいて、ブロックごとの情報を逆スキャンによって整列する処理が行われる。次に、逆量子化部１３では、逆スキャン部１２からの出力データに対して逆量子化処理が行われ、離散コサイン変換の係数情報が得られる。次に、逆離散コサイン変換部１４では、得られた係数情報に対して逆離散コサイン変換が行われることにより、係数情報が画像情報に変換される。そして、動き補償部１５および画像メモリ１６では、入力ビットストリームにおいてフレーム間予測が使用されている場合に、逆離散コサイン変換部１４により得られた画像情報によって予測画像が構成されると共に動き補償処理が行われることにより、最終的な出力画像が得られる。
【００３２】
（可変長符号復号部１１の動作）
次に、図２〜図４を参照して、本発明の特徴的部分の１つである、可変長符号復号部１１による復号処理の概要について説明する。図４は、可変長符号復号部１１による復号処理の一例を流れ図で表したものであり、図３（Ａ）に示した可変長符号テーブル２１による復号処理に対応するものである。
【００３３】
図４に示した復号処理の際、可変長符号復号部１１では、まず、ビット読み込み部１１１が、入力ビットストリームから１ビットのビットデータを読み込み、１ビット判定部１１３へ供給する（ステップＳ１０１）。次に、１ビット判定部１１３は、そのビットデータが「０」であるか否かを判定する（ステップＳ１０２）。ここで、そのビットデータが「０」ではない（「１」である）と判定された場合（ステップＳ１０２：Ｎ（Ｎｏ））、その判定結果に応じて、シンボル出力部１１４によって、符号「１」に対応するシンボル「Ａ」が出力シンボルとして出力される（ステップＳ１０３、図３（Ａ）参照）。これにより、現在の判定対象の符号に対する復号処理が終了となる。
【００３４】
一方、ステップＳ１０２において、そのビットデータが「０」であると判定された場合（ステップＳ１０２：Ｙ（Ｙｅｓ））、次に、ビット読み込み部１１１から１ビット判定部１１３へ、次の１ビットのビットデータが供給される（ステップＳ１０４）。次に、１ビット判定部１１３は、再び、そのビットデータが「０」であるか否かを判定する（ステップＳ１０５）。ここで、そのビットデータが「０」ではない（「１」である）と判定された場合（ステップＳ１０５：Ｎ）、その判定結果に応じて、シンボル出力部１１４によって、符号「０１」に対応するシンボル「Ｂ」が出力シンボルとして出力される（ステップＳ１０６、図３（Ａ）参照）。これにより、現在の判定対象の符号に対する復号処理が終了となる。
【００３５】
一方、ステップＳ１０５において、そのビットデータが「０」であると判定された場合（ステップＳ１０５：Ｙ）、その判定結果に応じて、シンボル出力部１１４によって、符号「００１」に対応するシンボル「Ｃ」が出力シンボルとして出力される（ステップＳ１０７、図３（Ａ）参照）。これにより、現在の判定対象の符号に対する復号処理が終了となる。
【００３６】
このようにして、本実施の形態の可変長符号復号部１１では、入力ビットストリームの復号処理の際に、例えば図４に示したような、ツリー構成部１１２により予め構成された所定のツリー構造が用いられ、これにより、判定対象の符号に対応するシンボルデータ（出力シンボル）が出力される。具体的には、このツリー構造では、入力ビットストリームにおいて出現し得る全てのビットパターンを網羅しつつ（図４に対応する図３（Ａ）参照）、１ビットずつ順番に、そのビットデータが所定値「０」と一致するか否かの判断分岐がなされるように構築されている。また、このようなツリー構造を用いて、入力ビットストリームにおいて１ビットずつ順番に、そのような判断分岐の判定が行われる。
【００３７】
さらに、このツリー構造は、Ｎビット（Ｎ；１以上の整数）の符号に対応するシンボルデータ（出力シンボル）の出力の際に、Ｎ回の判断分岐がなされる。具体的には、図４に示した符号処理の例では、１ビットの符号に対応するシンボル「Ａ」を出力する際に、１回の判断分岐（ステップＳ１０２）が行われるようになっている。また、２ビットの符号に対応するシンボル「Ｂ」、および３ビットの符号に対応するシンボル「Ｃ」を出力する際に、２回の判断分岐（ステップＳ１０２，Ｓ１０５）が行われるようになっている。ただし、可変長符号テーブルに記載された符号のうち最大の長さをもつ符号が１種類のみで、かつビットストリームにエラーが存在しないことを前提としている場合には、Ｎ回目の判断分岐を省略して、（Ｎ−１）回の判断分岐で処理することができる。通常は、ビットストリームにエラーが存在する可能性を考慮し、Ｎ回目の判断分岐において対応する符号が存在しない場合には、エラーとして扱う。
【００３８】
なお、図４に示した流れ図は、図３（Ａ）に示した可変長符号テーブル２１による復号処理に対応する例であり、可変長符号表のパターンに応じて、流れ図における判断分岐のツリー形状は異なるようになっている。
【００３９】
次に、図５〜図１１を参照して、可変長符号復号部１１による復号処理について、比較例と比較しつつ詳細に説明する。ここで、図５は、比較説明に用いる入力ビットストリームの一例（入力ビットストリームＢＳin）を表したものである。また、図６〜図８は、比較例に係る従来の可変長符号復号部（可変長符号復号部１００）を表したものである。具体的には、図６は、可変長符号復号部１００のブロック構成を表したものである。また、図７は、この可変長符号復号部１００による復号処理を流れ図で表したものである。また、図８は、可変長符号復号部１００による入力ビットストリームＢＳinに対する復号処理（図３（Ｂ）に示した可変長符号テーブル２２を用いた復号処理に対応）の態様を、タイミング図で模式的に表したものである。また、図９および図１０は、本実施の形態の可変長符号復号部１１による入力ビットストリームＢＳinに対する復号処理（図３（Ｂ）に示した可変長符号テーブル２２による復号処理に対応）を、流れ図で表したものである。
【００４０】
（比較例の構成および動作）
まず、図６に示したように、比較例に係る可変長符号復号部１００は、ビット読み込み部１０１と、読み込み符号レジスタ１０５と、読み込み符号長さレジスタ１０６と、可変長符号テーブル保持メモリ１０７と、可変長符号テーブルインデックス１０８と、一致判定部１０３と、シンボル出力部１０４とから構成されている。ビット読み込み部１０１は、入力ビットストリームから１ビットずつ順番にビットデータを読み込み、そのビットデータを読み込み符号レジスタ１０５へ供給すると共に、そのビットデータの長さを読み込み符号長さレジスタ１０６へ供給するものである。また、読み込み符号レジスタ１０５は、読み込まれた符号のビットパターンを保持するものである。また、読み込み符号長さレジスタ１０６は、読み込まれた符号の長さ（ビット数）を保持するものである。また、可変長符号テーブル保持メモリ１０７は、例えば図３（Ａ），図３（Ｂ）に示したような可変長符号テーブル２１，２２などを保持するものである。また、可変長符号テーブルインデックス１０８は、可変長符号テーブルの中の特定の符号を指し示すためのものである。また、一致判定部１０３は、読み込み符号レジスタ１０５に保持されている符号のビットパターンと、読み込み符号長さレジスタ１０６に保持されている符号の長さとがそれぞれ一致する符号が、可変長符号レーブル保持メモリ１０７に保持されている可変長符号テーブルの中に存在するか否かを判定するものである。また、シンボル出力部１０４は、一致判定部１０３において一致する符号が見つかったときに、その符号に対応するシンボルを出力するものである。
【００４１】
この可変長符号復号部１００では、例えば図７中のステップＳ９０１〜Ｓ９０９に示したようにして、復号処理が行われる。すなわち、まず、読み込み符号レジスタ１０５および読み込み符号長さレジスタ１０６がそれぞれ、初期値「０」で初期化される（ステップＳ９０１）。次に、入力ビットストリームから１ビットのビットデータが読み込まれ、読み込み符号レジスタ１０５に追加される（ステップＳ９０２）と同時に、読み込み符号長さレジスタ１０６に「１」が加えられる（ステップＳ９０３）。次に、可変長符号テーブルインデックス１０８に「０」が設定され（ステップＳ９０４）、その可変長符号テーブルインデックス１０８の指す符号および符号長さが、可変長符号テーブル１０７から取り出される（ステップＳ９０５）。次に、一致判定部１０３によって、取り出された符号および符号長さが、読み込み符号レジスタ１０５の符号および読み込み符号長さレジスタ１０６の値と一致するか否かが判定される（ステップＳ９０６）。一致すると判定された場合には（ステップＳ９０６：Ｙ）、その可変長符号が表すシンボル（出力シンボル）が復号結果として出力され（ステップＳ９０９）、復号処理が終了となる。一方、ステップＳ９０６において一致しないと判定された場合には（ステップＳ９０６：Ｎ）、可変長符号テーブルインデックス１０８に「１」が加えられる（ステップＳ９０７）と共に、その可変長符号テーブルインデックス１０８の値がテーブルのサイズ以内であるか否かが判断される（ステップＳ９０８）。テーブルのサイズ以内であると判断された場合には（ステップＳ９０８：Ｙ）、ステップＳ９０５に戻ると共に、ステップＳ９０６において一致すると判定されるまで同様の処理が繰り返される。一方、ステップＳ９０８においてテーブルのサイズ以内ではないと判断された場合には（ステップＳ９０８：Ｎ）、ステップＳ９０２に戻って次の１ビットを読み込むと共に、ステップＳ９０６において一致すると判定されるまで同様の処理が繰り返される。
【００４２】
具体的には、例えば図５に示した入力ビットストリームＢＳin（＝「０１１００１１１０…」）に対する復号処理の際には、可変長符号復号部１００では、例えば図８に示したようにして復号処理が行われる。すなわち、まず、図５中の矢印Ｐ１および図８（Ａ）に示したように、読み込み符号レジスタ１０５にビットデータ「０」が読み込まれると共に、読み込み符号長さレジスタ１０６に読み込んだ符号の長さ「１」が保持される。この場合、これらの符号および符号長さに対応する符号は、図３（Ｂ）に示した可変長符号テーブルには存在しないため、全てのシンボル「０」〜「１８」に対応する符号に対して比較処理が繰り返されるものの、一致ものは存在しないことになる。次に、図５中の矢印Ｐ１および図８（Ｂ）に示したように、読み込み符号レジスタ１０５に次のビットデータ「１」が読み込まれて「０１」が保持されると共に、読み込み符号長さレジスタ１０６に読み込んだ符号の長さ「２」が保持される。この場合も、これらの符号および符号長さに対応する符号は、図３（Ｂ）に示した可変長符号テーブルには存在しないため、全てのシンボル「０」〜「１８」に対応する符号に対して比較処理が繰り返されるものの、一致ものは存在しないことになる。そして、次に、図５中の矢印Ｐ１および図８（Ｃ）に示したように、読み込み符号レジスタ１０５に次のビットデータ「１」が読み込まれて「０１１」が保持されると共に、読み込み符号長さレジスタ１０６に読み込んだ符号の長さ「３」が保持される。この場合には、これらの符号および符号長さに対応する符号が、図３（Ｂ）に示した可変長符号テーブルに存在する（シンボル「６」）ため、対応するこのシンボル「６」が復号結果として出力される。ただし、この場合も、シンボル「０」〜「５」に対応する符号に対しては、結果的に一致しない比較処理が繰り返されることになる。
【００４３】
このようにして、可変長符号復号部１００では、一致する符号が見つかるまで、同様の比較処理が繰り返される。ところがこの手法では、上記したように、入力ビットストリームから１ビット読み出す度に、可変長符号テーブルに記述されている全ての符号（ビットパターン）との比較処理を行う必要がある。そのため、比較結果の一致しない無駄な処理が多くなり、復号処理の際の処理速度が低いものとなってしまうことになる。
【００４４】
（本実施の形態の可変長符号復号部１１の動作）
これに対して、本実施の形態の可変長符号復号部１１では、入力ビットストリームの復号処理の際に、前述した図４と同様に、例えば図９および図１０中のステップＳ２０１〜Ｓ２５５に示したような、ツリー構成部１１２により予め構成された所定のツリー構造を用いられることにより、判定対象の符号に対応するシンボルが出力される。
【００４５】
具体的には、このツリー構造では、入力ビットストリームにおいて出現し得る全てのビットパターンを網羅しつつ（図９および図１０に対応する図３（Ｂ）参照）、１ビットずつ順番に、そのビットデータが所定値「０」と一致するか否かの判断分岐がなされるように構築されている。また、１ビット判定部１１３では、このようなツリー構造を用いて、入力ビットストリームにおいて１ビットずつ順番に、そのような判断分岐の判定が行われる。
【００４６】
これにより、上記した可変長符号復号部１００のような無駄な繰り返し処理（比較処理）がなくなるため、必要最小限の判断分岐によって、対応するシンボルデータの出力が可能となる。具体的には、このツリー構造では、Ｎビット（Ｎ；１以上の整数）の符号に対応するシンボルデータ（出力シンボル）の出力の際に、（Ｎ−１）回またはＮ回の判断分岐がなされる。
【００４７】
ここで、図１１に示した実施例（可変長符号復号部１１による実施例）および比較例（可変長符号復号部１００による比較例）のデータは、６種類の異なる入力ビットストリームに対する復号処理の際の、復号処理の処理時間（デコード時間）を含む全体の処理時間と、高速化倍率（＝比較例の処理時間／実施例の処理時間）を表したものである。これらのデータによれば、比較例と比べて実施例では、２．２００倍〜３．２２５倍程度、デコード時間を含む全体の処理時間が高速化されていることが分かる。
【００４８】
以上のように本実施の形態では、入力ビットストリームを復号処理する際に、入力ビットストリームにおいて出現し得る全てのビットパターンを網羅しつつ、１ビットずつ順番にそのビットデータが所定値「０」と一致するか否かの判断分岐がなされるように構築されたツリー構造を用いると共に、入力ビットストリームにおいて１ビットずつ順番にそのような判断分岐の判定を行うようにしたので、必要最小限の判断分岐によって、判定対象のビットパターンに対応するシンボルデータの出力が可能となる。よって、無駄な繰り返し処理が必要な従来と比べ、復号処理の際の処理速度を向上させることが可能となる。
【００４９】
また、短い符号ほど少ないステップ数で復号処理が完了する一方、長い符号ほど多いステップ数で復号処理が完了することになるが、一般に、情報圧縮のために使われる可変長符号では、短い符号のほうがその出現確率が高いため、全体としての処理時間を短くすることができる。一方、比較例に係る従来の可変長符号復号部１００では、符号の出現確率に関係なく、可変長符号テーブル２１，２２等の最初の符号から順番に比較を行っているため、結果的に一致する符号を見つけるまでに、無駄な比較処理を行ってしまう可能性が高くなってしまうことになる。
【００５０】
さらに、出現する可能性のあるすべての符号のビットパターンおよびその長さを記述する可変長符号テーブル２１，２２等を保持するメモリが不要となるため、必要なメモリ量を削減することも可能となる。一方、比較例に係る従来の可変長符号復号部１００では、そのような可変長符号テーブル２１，２２等を保持する必要があるため、必要なメモリ量が多くなってしまうことになる。
【００５１】
以上、実施の形態を挙げて本発明を説明したが、本発明はこの実施の形態に限定されるものではなく、種々の変形が可能である。
【００５２】
例えば、上記実施の形態では、入力ビットストリーム（符号化ストリーム）が可変長符号により符号化されたものである場合について説明したが、本発明は、固定長符号により符号化された符号化ストリームに対しても適用することが可能である。
【００５３】
また、上記実施の形態では、各ビットデータが所定値「０」と一致するか否かの判断分岐を行う場合について説明したが、逆に、各ビットデータが所定値「１」と一致するか否かの判断分岐を行うようにしてもよい。
【００５４】
また、上記実施の形態では、ＭＰＥＧによる圧縮方式の際の復号処理を例として挙げて説明したが、本発明は、他の圧縮方式の際の復号処理にも適用することが可能である。
【００５５】
さらに、上記実施の形態において説明した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされるようになっている。図１２は、これら一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。このようなプログラムは、コンピュータ２００に内蔵されている記録媒体としてのハードディスク２０５やＲＯＭ２０３に予め記録しておくことができる。あるいはまた、プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory），ＭＯ（Magneto Optical）ディスク，ＤＶＤ（Digital Versatile Disc）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体２１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体２１１は、いわゆるパッケージソフトウエアとして提供することができる。なお、プログラムは、上述したようなリムーバブル記録媒体２１１からコンピュータにインストールする他、ダウンロードサイトから、デジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、ＬＡＮ（Local Area Network）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部２０８で受信し、内蔵するハードディスク２０５にインストールすることができる。
【００５６】
また、このコンピュータ２００は、ＣＰＵ２０２を内蔵している。このＣＰＵ２０２には、バス２０１を介して、入出力インタフェース２１０が接続されている。ＣＰＵ２０２は、入出力インタフェース２１０を介して、ユーザによって、キーボードや、マウス、マイク等で構成される入力部２０７が操作等されることにより指令が入力されると、それにしたがって、ＲＯＭ（Read Only Memory）２０３に格納されているプログラムを実行する。あるいは、また、ＣＰＵ２０２は、ハードディスク２０５に格納されているプログラム、衛星もしくはネットワークから転送され、通信部２０８で受信されてハードディスク２０５にインストールされたプログラム、またはドライブ２０９に装着されたリムーバブル記録媒体２１１から読み出されてハードディスク２０５にインストールされたプログラムを、ＲＡＭ（Random Access Memory）２０４にロードして実行する。これにより、ＣＰＵ２０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、ＣＰＵ２０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース２１０を介して、ＬＣＤ（Liquid Crystal Display）やスピーカ等で構成される出力部２０６から出力、あるいは、通信部２０８から送信、さらには、ハードディスク２０５に記録等させるようになっている。
【００５７】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。また、プログラムは、１のコンピュータにより処理されるものであってもよいし、複数のコンピュータによって分散処理されるものであってもよい。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであってもよい。
【図面の簡単な説明】
【００５８】
【図１】本発明の一実施の形態に係るデータ処理装置を備えたＭＰＥＧ符号器の概略構成を表すブロック図である。
【図２】図１に示した可変長符号復号部の詳細構成を表すブロック図である。
【図３】可変長符号復号部による復号処理に適用される可変長符号テーブルの一例を表す図である。
【図４】実施の形態に係る復号処理の一例を表す流れ図である。
【図５】入力ビットストリームの一例を表す図である。
【図６】比較例に係る従来の可変長符号復号部の構成を表すブロック図である。
【図７】比較例に係る従来の復号処理について説明するための流れ図である。
【図８】比較例に係る従来の復号処理について説明するためのタイミング図である。
【図９】実施の形態に係る復号処理の他の例を表す流れ図である。
【図１０】図９に続く実施の形態に係る復号処理の他の例を表す流れ図である。
【図１１】実施例および比較例に係る処理時間の一例を表す図である。
【図１２】本発明を適用したコンピュータの構成例を表すブロック図である。
【符号の説明】
【００５９】
１…ＭＰＥＧ復号器、１１…可変長符号復号部、１１１…ビット読み込み部、１１２…ツリー構成部、１１３…１ビット判定部、１１４…シンボル出力部、１１５…制御部、１２…逆スキャン部、１３…逆量子化部、１４…逆離散コサイン変換部、１４…動き補償部、１６…画像メモリ、２１，２２…可変長符号テーブル、ＢＳin…入力ビットストリーム。
【図１】
2010021620.tif 000003
【図２】
2010021620.tif 000004
【図３】
2010021620.tif 000005
【図４】
2010021620.tif 000006
【図５】
2010021620.tif 000007
【図６】
2010021620.tif 000008
【図７】
2010021620.tif 000009
【図８】
2010021620.tif 000010
【図９】
2010021620.tif 000011
【図１０】
2010021620.tif 000012
【図１１】
2010021620.tif 000013
【図１２】
2010021620.tif 000014