(57)【要約】【課題】回路規模の増大を抑制し、かつ、より高速にコンテキスト適応的可変長符号化処理を行うことができるようにする。【解決手段】適応的可変長符号化装置100は、シンタックスエレメントの生成符号化に有意マップを用いることにより、符号化対象のブロックに存在する全係数にアクセスすることなく、容易かつ高速に各シンタックスエレメントを生成することができる。また、適応的可変長符号化装置100は、各シンタックスエレメントの符号化のたびに随時シンタックスエレメントを生成することが可能となるので、各シンタックスエレメントを保持しておくためのバッファが不要になり、回路規模の増大を抑制しながら、シンタックスエレメントの符号化を並列処理することが可能となる。本発明は、符号化装置に適用することができる。【選択図】図3
2008141382.tif 000002
【特許請求の範囲】
【請求項１】
情報を符号化する符号化装置であって、
前記情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップを生成する有意マップ生成手段と、
前記有意マップ生成手段により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化手段と
を備える符号化装置。
【請求項２】
前記係数群を保持する係数保持手段をさらに備え、
前記シンタックスエレメント生成符号化手段は、前記有意マップの情報に基づいて、前記係数保持手段により保持されている前記係数群の中から、前記シンタックスエレメントの生成および可変長符号化に必要な係数のみを取得し、取得した前記係数を用いて前記シンタックスエレメントの生成および可変長符号化を行う
請求項１に記載の符号化装置。
【請求項３】
前記シンタックスエレメント生成符号化手段は、各シンタックスエレメントの生成および可変長符号化を並列的に行う
請求項１に記載の符号化装置。
【請求項４】
前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる符号を保持する符号保持手段と、
前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる各シンタックスエレメントに対応する符号を、予め定められた所定の順序に整列させるために、前記シンタックスエレメント生成符号化手段により可変長符号化されて得られた符号、または、前記符号保持手段により保持されている符号のいずれか一方を選択して出力する符号選択手段と
をさらに備える請求項１に記載の符号化装置。
【請求項５】
前記符号選択手段は、前記符号を、ITU-T（International Telecommunication Union Telecommunication Standardization Sector）により勧告されたH.264方式において規定される順序に整列させるように選択して出力する
請求項４に記載の符号化装置。
【請求項６】
前記有意マップ生成手段は、前記情報の直交変換処理、および、前記直交変換処理により得られる前記直交変換係数の量子化処理をさらに行い、前記有意マップを、前記直交変換係数を用いて前記量子化処理と並行して同時に生成する
請求項１に記載の符号化装置。
【請求項７】
情報を符号化する符号化装置の符号化方法であって、
前記情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップを生成する有意マップ生成ステップと、
前記有意マップ生成ステップの処理により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化ステップと
を備える符号化方法。
【請求項８】
情報を符号化するコンピュータが実行可能なプログラムであって、
前記情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップを生成する有意マップ生成ステップと、
前記有意マップ生成ステップの処理により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化ステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置および方法、並びにプログラムに関し、特に、より高速にコンテキスト適応的可変長符号化処理を行うことができるようにした符号化装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来、MPEG（Moving Picture Experts Group）2やMPEG4では、値が「0」の直交変換係数の長さ（連続数）を示すランと、直交変換係数値を示すレベルの組に対して符号化が行われ、ランとレベルの組を複数並列して生成し、符号化することで高速化が実現されてきた。この場合、ランとレベルの組を符号化する同一の符号化器を複数設けることになるので並列化する分だけ符号化装置の回路規模は増大する。
【０００３】
例えば、画像を複数の領域に分割するようにし、同一の符号化回路を複数設けることで、それぞれの領域を並列に符号化処理する方法がある（例えば、特許文献1参照）。図1は、その画像符号化装置の構成例を示す図である。
【０００４】
図1において、画像符号化装置1は、入力端子10、分割回路11、符号化回路12、符号化回路13、算出回路14、算出回路15、目標符号量制御回路16、出力端子20、および出力端子30を有し、フレーム毎に画像を左右2分割し、左半分を領域［1］、右半分を領域［2］として符号化する。
【０００５】
分割回路11は、入力端子10から入力された画像情報をフレーム毎に領域［1］と領域［2］に分割し、領域［1］の画像情報を符号化回路12に供給し、領域［2］の画像情報を符号化回路13に供給する。符号化回路12は、目標符号量制御回路16より供給された領域［1］の目標符号量TB［1］に応じて領域［1］の画像情報を符号化し、得られたコードストリームを出力端子20より出力させる。また、符号化回路12は、目標符号量制御用情報を算出回路14に供給する。算出回路14は、目標符号量制御用情報を用いて1フレーム中の領域［1］の符号化が終了した時点でパラメータP［1］を算出する。
【０００６】
同様に、符号化回路13は、目標符号量制御回路16より供給された領域［2］の目標符号量TB［2］に応じて領域［2］の画像情報を符号化し、得られたコードストリームを出力端子30より出力させる。また、符号化回路13は、目標符号量制御用情報を算出回路15に供給する。算出回路15は、目標符号量制御用情報を用いて1フレーム中の領域［2］の符号化が終了した時点でパラメータP［2］を算出する。
【０００７】
目標符号量制御回路16は、算出回路14および算出回路15より供給されたパラメータP［1］およびP［2］を用いてフレーム全体の目標符号量TTBを各領域に分配し、各領域の目標符号量TB［1］を符号化回路12に供給し、目標符号量TB［2］を符号化回路13に供給する。
【０００８】
例えば、ITU-T（International Telecommunication Union Telecommunication Standardization Sector）によって勧告されたH.264方式のエントロピー符号化方法の1つであるコンテキスト適応的可変長符号化方式（CAVLC（Context Adaptive Variable Length Coding））においても、回路規模の増大を許せば従来技術のように各シンタックスエレメントについて同一の符号化器を複数持つことで高速化を実現することができる。
【特許文献１】特開平6-113274号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、CAVLCではランとレベルを別々に符号化するため、例えば2並列処理する場合、ラン符号化器とレベル符号化器をそれぞれ2つずつ設ける必要があるため、回路規模の増大はMPEG2やMPEG4の場合と比較してさらに顕著になる恐れがあった。
【００１０】
また、CAVLCは適応的可変長符号化であり、ランおよびレベルのいずれについても、連続するシンタックスエレメントを符号化する場合、後段のシンタックスエレメントの符号化テーブルの選択は前段のシンタックスエレメントの情報を用いて行われるため、レベルを保持する回路を各符号化器に設ける必要があった。
【００１１】
なお、例えば、事前にランとレベルを生成して保持しておき、ランとレベルを同時に符号化するようにすることで高速化を実現する方法があるが、この場合、同一のシンタックス符号化器を複数持つ必要はないが、ランとレベルを保持しておくためのバッファが新たに必要になるため、やはり回路規模の増大を抑制することができない恐れがあった。
【００１２】
このように、従来技術では回路規模の増大を抑制し、かつ、高速化を実現することが困難である恐れがあった。
【００１３】
本発明は、このような状況に鑑みてなされたものであり、回路規模の増大を抑制し、かつ、より高速にコンテキスト適応的可変長符号化処理を行うことができるようにするものである。
【課題を解決するための手段】
【００１４】
本発明の側面は、情報を符号化する符号化装置であって、前記情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップを生成する有意マップ生成手段と、前記有意マップ生成手段により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化手段とを備える符号化装置である。
【００１５】
前記係数群を保持する係数保持手段をさらに備え、前記シンタックスエレメント生成符号化手段は、前記有意マップの情報に基づいて、前記係数保持手段により保持されている前記係数群の中から、前記シンタックスエレメントの生成および可変長符号化に必要な係数のみを取得し、取得した前記係数を用いて前記シンタックスエレメントの生成および可変長符号化を行うことができる。
【００１６】
前記シンタックスエレメント生成符号化手段は、各シンタックスエレメントの生成および可変長符号化を並列的に行うことができる。
【００１７】
前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる符号を保持する符号保持手段と、前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる各シンタックスエレメントに対応する符号を、予め定められた所定の順序に整列させるために、前記シンタックスエレメント生成符号化手段により可変長符号化されて得られた符号、または、前記符号保持手段により保持されている符号のいずれか一方を選択して出力する符号選択手段とをさらに備えるようにすることができる。
【００１８】
前記符号選択手段は、前記符号を、ITU-T（International Telecommunication Union Telecommunication Standardization Sector）により勧告されたH.264方式において規定される順序に整列させるように選択して出力することができる。
【００１９】
前記有意マップ生成手段は、前記情報の直交変換処理、および、前記直交変換処理により得られる前記直交変換係数の量子化処理をさらに行い、前記有意マップを、前記直交変換係数を用いて前記量子化処理と並行して同時に生成することができる。
【００２０】
本発明の側面はまた、情報を符号化する符号化装置の符号化方法またはプログラムであって、前記情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップを生成する有意マップ生成ステップと、前記有意マップ生成ステップの処理により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化ステップとを備える情報処理方法またはプログラムである。
【００２１】
本発明の側面においては、情報が直交変換されて得られた係数群における、値がゼロでない係数の位置を示す有意マップが生成され、その生成された有意マップ、および、有意マップに対応する係数群を用いてシンタックスエレメントが生成され、可変長符号化される。
【発明の効果】
【００２２】
本発明によれば、情報を符号化することができる。特に、回路規模の増大を抑制し、かつ、より高速にコンテキスト適応的可変長符号化処理を行うことができる。
【発明を実施するための最良の形態】
【００２３】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書または図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書または図面に記載されていることを確認するためのものである。従って、明細書または図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００２４】
本発明の側面は、情報を符号化する符号化装置（例えば、図3の適応的可変長符号化装置100）であって、前記情報が直交変換されて得られた係数群（例えば、図2の4×4係数ブロック51）における、値がゼロでない係数の位置を示す有意マップ（例えば、図2の有意マップ53）を生成する有意マップ生成手段（例えば、図3のDCT量子化有意マップ生成部101）と、前記有意マップ生成手段により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化手段（例えば、図3のシンタックス生成符号化部104）とを備える符号化装置である。
【００２５】
前記係数群を保持する係数保持手段（例えば、図3の係数格納部103）をさらに備え、前記シンタックスエレメント生成符号化手段は、前記有意マップの情報に基づいて、前記係数保持手段により保持されている前記係数群の中から、前記シンタックスエレメントの生成および可変長符号化に必要な係数のみを取得し、取得した前記係数を用いて前記シンタックスエレメントの生成および可変長符号化を行うことができる。
【００２６】
前記シンタックスエレメント生成符号化手段は、各シンタックスエレメントの生成および可変長符号化を並列的に行う（例えば、図6のステップS3）ことができる。
【００２７】
前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる符号を保持する符号保持手段（例えば、図3の符号一時格納部106）と、前記シンタックスエレメント生成符号化手段により可変長符号化されて得られる各シンタックスエレメントに対応する符号を、予め定められた所定の順序に整列させるために、前記シンタックスエレメント生成符号化手段により可変長符号化されて得られた符号、または、前記符号保持手段により保持されている符号のいずれか一方を選択して出力する符号選択手段（例えば、図3の選択部107）とをさらに備えるようにすることができる。
【００２８】
前記符号選択手段は、前記符号を、ITU-T（International Telecommunication Union Telecommunication Standardization Sector）により勧告されたH.264方式において規定される順序に整列させるように選択して出力する（例えば、図6のステップS4）ことができる。
【００２９】
前記有意マップ生成手段は、前記情報の直交変換処理、および、前記直交変換処理により得られる前記直交変換係数の量子化処理をさらに行い、前記有意マップを、前記直交変換係数を用いて前記量子化処理と並行して同時に生成する（例えば、図6のステップS1）ことができる。
【００３０】
本発明の側面はまた、情報を符号化する符号化装置（例えば、図3の適応的可変長符号化装置100）の符号化方法またはプログラムであって、前記情報が直交変換されて得られた係数群（例えば、図2の4×4係数ブロック51）における、値がゼロでない係数の位置を示す有意マップ（例えば、図2の有意マップ53）を生成する有意マップ生成ステップ（例えば、図6のステップS1）と、前記有意マップ生成ステップの処理により生成された前記有意マップ、および、前記有意マップに対応する前記係数群を用いてシンタックスエレメントを生成し、可変長符号化するシンタックスエレメント生成符号化ステップ（例えば、図6のステップS3）とを備える情報処理方法またはプログラムである。
【００３１】
以下、本発明の実施の形態について説明する。
【００３２】
本発明の適応的可変長符号化装置の主な特長の1つは、各シンタックスエレメントの生成に有意マップを使用することである。図2は、その有意マップについて説明する図である。図2の上段に示される4×4係数ブロック51は、DCT（Discrete Cosine Transform）直交変換され、量子化が行われて得られた係数の、CAVLCの符号化単位の集合である。この4×4係数ブロック51は、図中左上の係数より所定の方法でジグザグスキャンされ、ジグザグスキャン後の係数列52として、1ビットずつ直列に処理される。
【００３３】
図2の下段に示される有意マップ53は、この4×4係数ブロック51の非ゼロ係数（値が「0」でない係数）を1bitの「1」で表し、ゼロ係数（値が「0」の係数）を1bitの「0」で表したマップであり、16bitで表すことができる。つまり、ジグザグスキャン後の係数列52に対応する有意マップは、ジグザグスキャン後の有意マップ54のように表される。
【００３４】
図3は、本発明を適用した適応的可変長符号化装置の構成例を示すブロック図である。図3において、適応的可変長符号化装置100は、コンテキスト適応的可変長符号化方式（CAVLC（Context Adaptive Variable Length Coding））を用いて符号化を行う装置である。適応的可変長符号化装置100は、DCT量子化有意マップ生成部101、有意マップ格納部102、係数格納部103、シンタックス生成符号化部104、隣接情報格納部105、符号一時格納部106、選択部107、および制御部108を有する。
【００３５】
DCT量子化有意マップ生成部101は、ITU-T（International Telecommunication Union Telecommunication Standardization Sector）によって勧告されたH.264方式のエントロピー符号化方法の1つであるCAVLC符号化処理を実現するために離散コサイン変換処理（直交変換処理）および量子化処理を行い、さらに、その直交変換処理により得られた直交変換係数を用いて、有意マップを、量子化処理と並行して（同時に）生成する。すなわち、有意マップの生成は、DCTや量子化処理と併せて行われるので、有意マップ生成のための係数アクセスを隠蔽することが可能となり、有意マップを生成するためだけにサイクル数を必要とせず、適応的可変長符号化装置100は、高速に処理を行うことができる。
【００３６】
DCT量子化有意マップ生成部101は、その有意マップを有意マップ格納部102に供給し、係数を係数格納部103に供給する。有意マップ格納部102は、供給された有意マップを一時的に格納（保持）し、所定のタイミングでそれをシンタックス生成符号化部104に供給する。係数格納部103は、供給された係数を一時的に格納（保持）し、所定のタイミングでそれをシンタックス生成符号化部104に供給する。
【００３７】
シンタックス生成符号化部104は、各シンタックスエレメントを並列に符号化する。シンタックス生成符号化部104の詳細については後述する。隣接情報格納部105は、シンタックス生成符号化部104での処理の一部であるcoeff_tokenシンタックスエレメントの生成に必要な、隣接ブロックの非ゼロ係数の個数情報を格納（保持）する。
【００３８】
シンタックス生成符号化部104が各シンタックスエレメントを並列に符号化するため、その符号化順序は、必ずしも、H.264において規定された順序とはならない。そこで、符号一時格納部106は、シンタックス生成符号化部104より出力された符号がH.264において規定された順序でビットストリームとして出力されるように、シンタックス生成符号化部104より出力された一部の符号を一時的に保持する。
【００３９】
選択部107は、符号をH.264方式で規定された順序にビットストリームとして出力させるために、符号一時格納部106に格納（保持）されている符号、および、シンタックス生成符号化部104より出力される符号のうちいずれか一方を選択して出力する。
【００４０】
制御部108は、これらのDCT量子化有意マップ生成部101乃至選択部107の各部の動作を制御する。例えば、制御部108は、全体の動作制御として有意マップ格納部102および係数格納部103にあるマクロブロック単位のデータからどの部分を符号化ブロック単位で読み出すかという制御、どのシンタックスエレメントの符号を符号一時格納部106に格納するかの制御や、選択部107の符号選択および出力の制御などを行う。
【００４１】
図4は、図3のシンタックス生成符号化部104の詳細な構成例を示すブロック図である。
【００４２】
図4において、シンタックス生成符号化部104は、例えば、ジグザグスキャン部121、シンタックス生成部122、シンタックス符号化部123、および制御部124を有する。
【００４３】
ジグザグスキャン部121は、有意マップ格納部102に格納されている有意マップを読み出して所定の方法で並び替えを行い（ジグザグスキャンし）、その並び替えた順番で有意マップの各値をシンタックス生成部122に供給する。
【００４４】
シンタックス生成部122は、ジグザグスキャン部121より供給される有意マップを利用して、符号化対象のブロックに存在する全係数にアクセスすることなく（必要な係数のみ係数格納部103より取得し）、各シンタックスエレメントを生成する。シンタックス生成部122は、生成した、各シンタックスエレメントをシンタックス符号化部123に供給する。
【００４５】
シンタックス符号化部123は、シンタックス生成部122において生成された各シンタックスエレメント等を符号化する。シンタックス符号化部123は、非ゼロ係数の総数を示すTotalCoeffシンタックスエレメント（TotalCoeff）と最後に連続する絶対値「1」の係数の個数を示すTrailingOnesシンタックスエレメント（TrailingOnes）の組み合わせであるcoeff_tokenシンタックスエレメントを符号化するcoeff_token符号化部131、最後の非ゼロ係数以前のゼロ係数の個数を示すtotal_zerosシンタックスエレメント（total_zeros）を符号化するtotal_zeros符号化部132、非ゼロ係数値の前の「0」の連続個数を示すrun_beforeシンタックスエレメント（run_before）を符号化するrun_before符号化部133、および、最後に連続する絶対値「1」の係数の符号を示すtrailing_ones_sign_flagシンタックスエレメント（t1_sign）、若しくは、非ゼロ係数値を示すlevelシンタックスエレメント（level）を符号化するnz_coeff符号化部134を有する。
【００４６】
coeff_token符号化部131は、シンタックス生成部122において生成されたTrailingOnesシンタックスエレメント、非ゼロ係数の個数を示すTotalCoeffシンタックスエレメント、および、隣接情報格納部105より読み出した隣接ブロックのTotalCoeffシンタックスエレメントを用いてcoeff_tokenを符号化する。total_zeros符号化部132は、シンタックス生成部122において生成されたTotalCoeffシンタックスエレメント、および、total_zerosシンタックスエレメントを用いてtotal_zerosシンタックスエレメントを符号化する。run_before符号化部133は、シンタックス生成部122において生成されたrun_beforeシンタックスエレメントを符号化する。nz_coeff符号化部134は、シンタックス生成部122において生成された非ゼロ係数（trailing_ones_sign_flagシンタックスエレメント、および、levelシンタックスエレメント）を符号化する。これらのcoeff_token符号化部131乃至nz_coeff符号化部134において生成された、各シンタックスエレメントの符号は、図3の符号一時格納部106および選択部107に供給される。
【００４７】
制御部124は、ジグザグスキャン部121、シンタックス生成部122、およびシンタックス符号化部123をそれぞれ制御する。
【００４８】
図5は、図4のシンタックス生成部122の詳細な構成例を示すブロック図である。
【００４９】
シンタックス生成部122は、16bit加算部151、bit反転部152、16bit加算部153、スイッチ回路154、パターンマッチング部155、減算部156、シフト量カウント部157、アドレス生成部158、可変右ビットシフト部159、および有意マップ一時格納部160を有する。
【００５０】
16bit加算部151は、図4のジグザグスキャン部121より供給される16bitの有意マップの各ビットの値を加算し、加算結果（すなわち非ゼロ係数の数）をTotalCoeffシンタックスエレメントとして、図4のシンタックス符号化部123に供給する。
【００５１】
bit反転部152は、図4のジグザグスキャン部121より供給される16bitの有意マップの各ビットの値を反転させ、「0」のビットを「1」に変換し、「1」のビットを「0」に変換する。16bit加算部153は、その値が反転された各ビットの値を加算し、加算結果（すなわちゼロ係数の数（zeros_all））を減算部156に供給する。
【００５２】
スイッチ回路154は、図4のジグザグスキャン部121より供給された元の有意マップと、有意マップ一時格納部160より供給される、ビットシフトが行われた有意マップのいずれか一方を選択し、それをパターンマッチング部155および可変右ビットシフト部159に供給する。パターンマッチング部155は、スイッチ回路154より供給された有意マップを、所定の有意マップパターンテーブル情報を用いてパターンマッチングを行うことにより、有意マップに含まれる、最後の非ゼロ係数の後（右）に存在するゼロ係数の数を示すzeros_rightを求める。
【００５３】
減算部156は、16bit加算部153より供給されたゼロ係数の数を示すzeros_allより、パターンマッチング部155より供給されたzeros_rightを減算し、total_zerosを求め、それを図4のシンタックス符号化部123に供給する。
【００５４】
また、パターンマッチング部155は、詳細については後述するが、1つの有意マップから、zeros_rightを求めるだけでなく、非ゼロ係数間に存在するゼロの数も求める。そのために、パターンマッチング部155は、有意マップの各ビットを右方向にシフトさせながら、パターンマッチングを繰り返す。パターンマッチング部155は、zeros_rightとともに、この有意マップのビットシフト量も求める。パターンマッチング部155は、このビットシフト量をシフト量カウント部157および可変右ビットシフト部159に供給する。
【００５５】
シフト量カウント部157は、パターンマッチング部155より供給されるビットシフト量を積算し、有意マップ上で右端から何番目に位置するシンボルであるかを示す変数nz_coeff_posをアドレス生成部158に供給する。アドレス生成部158は、そのnz_coeff_posの値に基づいて、非ゼロ係数アドレスを生成し、それを図4の係数格納部103に供給する。この非ゼロ係数アドレスに基づいて、係数格納部103より非ゼロ係数のみが読み出され、trailing_ones_sign_flagシンタックスエレメント若しくはlevelシンタックスエレメントとしてシンタックス符号化部123に供給される（図5においてはlevelシンタックスエレメントについての構成は省略している）。
【００５６】
可変右ビットシフト部159は、パターンマッチング部155において算出されたビットシフト量に基づいて、スイッチ回路154より供給される有意マップを右方向にシフトし、その有意マップを有意マップ一時格納部160に供給する。有意マップ一時格納部160は、供給された有意マップを一時的に格納（保持）し、所定のタイミングで、その有意マップをスイッチ回路154に供給する。
【００５７】
再び非ゼロ係数のアドレスを生成する場合、スイッチ回路154は、有意マップ一時格納部160から読み出された、ビットシフトされた有意マップをパターンマッチング部155に供給するように接続を切り替える。パターンマッチング部155は、このように供給された、ビットシフトされた有意マップに対して再びパターンマッチングを行い、zeros_rightを求める。ただし、ここで求めたzeros_rightは、一度以上ビットシフトされた有意マップを用いて求めたものである。すなわち、このzeros_rightは、非ゼロ係数間に存在するゼロの数、つまり、run_beforeシンタックスエレメントを示すことになる。
【００５８】
パターンマッチング部155は、求めたrun_beforeシンタックスエレメントを図4のシンタックス符号化部123に供給する。
【００５９】
次に、以上のような構成の適応的可変長符号化装置100の動作について説明する。
【００６０】
最初に、適応的可変長符号化装置100により実行されるCAVLC処理の流れの例を、図6のフローチャートを参照して説明する。
【００６１】
CAVLC処理が開始されると、図3のDCT量子化有意マップ生成部101は、ステップS1において、入力された情報に対して、DCT直交変換や量子化を行うとともに、得られたDCT係数の有意マップを生成する。このように、DCT直交変換や量子化を行うとともに有意マップも生成するので、例えば有意マップを生成するために係数格納部103に格納されている係数を読み出す等の、この有意マップを生成するためだけのサイクル数が必要なく、DCT量子化有意マップ生成部101は、高速に係数群（係数ブロック）やその有意マップを求めることができる。
【００６２】
ステップS2において、図4のジグザグスキャン部121は、有意マップ格納部102より、4×4のブロック単位で有意マップを読み出し、ジグザグスキャン順序に並び替える。ステップS3において、図4のシンタックス生成部122は、順番を並び替えられた有意マップを用いて複数種類のシンタックスエレメントを並列に生成する。図4のシンタックス符号化部123は、複数種類のシンタックスエレメントの符号化を並列に行う。すなわち、シンタックス生成符号化部104は、各シンタックスエレメントの生成および符号化の各処理を並列に実行する。
【００６３】
図3の選択部107は、ステップS4において、符号一時格納部106を利用して、符号の並び替えを行い、ビットストリームとして出力する。
【００６４】
以上のように、適応的可変長符号化装置100は、シンタックスエレメントの生成符号化に有意マップを用いることにより、符号化対象のブロックに存在する全係数にアクセスすることなく、容易かつ高速に各シンタックスエレメントを生成することができる。
【００６５】
また、各シンタックスエレメントの符号化のたびに随時シンタックスエレメントを生成することが可能となるので、各シンタックスエレメントを保持しておくためのバッファが不要になる。このため、適応的可変長符号化装置100は、回路規模の増大を抑制しながら、シンタックスエレメントの符号化を並列処理することが可能となる。すなわち、適応的可変長符号化装置100は、回路規模を増大させずに高速に符号化処理を行うことができる。
【００６６】
図4の制御部124は、符号化対象ブロックの有意マップが読み出されジグザグスキャンされたことを受けて、シンタックス生成部122を起動する。起動されたシンタックス生成部122は、まず、TotalCoeffシンタックスエレメントの生成をおこなう。
【００６７】
図7のフローチャートを参照して、シンタックス生成部122によるTotalCoeffシンタックスエレメント生成処理の流れの例を説明する。
【００６８】
TotalCoeffシンタックスエレメント生成処理が開始されると、シンタックス生成部122の16bit加算部151（図5）は、ステップS21において、ジグザグスキャン部121（図4）より供給された16bitの有意マップの各ビットを加算することで、有意マップの「1」の総数を、TotalCoeffシンタックスエレメントとして算出する。有意マップは、図2を参照して説明したように、係数ブロックの非ゼロ係数の位置を「1」で示し、ゼロ係数の位置を「0」で示したものである。従って、有意マップに含まれる「1」のビットの総数は、係数ブロックの非ゼロ係数の総数を示す。
【００６９】
有意マップとシンタックスエレメントの関係を図8に示す。以上の関係から、図8の上段に示されるように、係数ブロックの非ゼロ係数の総数を示すTotalCoeffシンタックスエレメント204は、有意マップ201に含まれる「1」のビットの総数に対応する。すなわち、TotalCoeffシンタックスエレメント204は、全ビットの総和を算出することにより求めることができる。
【００７０】
このように、有意マップを用いてTotalCoeffシンタックスエレメントを生成すると、16bit加算部151は、TotalCoeffシンタックスエレメント生成処理を終了する。
【００７１】
また、制御部124に起動されたシンタックス生成部122は、まず、TotalCoeffシンタックスエレメントの生成とともに、total_zerosシンタックスエレメントを生成し、それらのシンタックスエレメントを用いて、total_zerosシンタックスエレメントの符号化を行う。
【００７２】
図9のフローチャートを参照して、シンタックス生成符号化部104によるtotal_zerosシンタックスエレメント生成符号化処理の流れの例を説明する。
【００７３】
total_zerosシンタックスエレメント生成処理が開始されると、シンタックス生成部122のbit反転部152（図5）は、ステップS61において、ジグザグスキャン部121（図4）より供給された16bitの有意マップの各ビットの値を反転させる。つまり、bit反転部152は、供給された有意マップの各ビットについて、値が「0」のビットを「1」に変換し、値が「1」のビットを「0」に変換する。16bit加算部153は、ステップS62において、値を反転させた有意マップの各ビットの値を加算することで、反転前の有意マップの「0」の総数を、zeros_allとして算出する。
【００７４】
上述したように、有意マップに含まれる「1」のビットの総数は、係数ブロックの非ゼロ係数の総数を示すが、換言すれば、有意マップに含まれる「0」のビットの総数は、係数ブロックのゼロ係数の総数を示す。上述したようにbit反転部152が有意マップの各ビットの値を反転させているので、16bit加算部153は、各ビットの総和を求めることにより、有意マップに含まれる「0」のビットの総数、すなわち、係数ブロックのゼロ係数の総数（zeros_all）を算出することができる。
【００７５】
zeros_allが算出されると、パターンマッチング部155は、ステップS63において、図10に示されるような有意マップのパターンテーブルを用いて、有意マップのパターンマッチングを行い、最後の係数より右側にある「0」の数（zeros_right）を算出する。図8の上段に示されるように、このzeros_right203（非シンタックス）は、有意マップ201の係数列の右端から、最も右側にある「1」のビットまでの間に連続する「0」の総数である。図10に示される有意マップのパターンテーブルは、この有意マップの係数列の右端から連続する「0」のビットのパターン毎に、zeros_right、run_before、およびビットシフト量を割り当てるテーブル情報であり、パターンマッチング部155は、このテーブルを用いて処理対象の有意マップのパターンに応じたzeros_rightを決定する。
【００７６】
以上のようにして、zeros_allおよびzeros_rightが求められると、減算部156は、ステップS64において、zeros_allよりzeros_rightを減算することにより、total_zerosシンタックスエレメントを生成する。total_zerosシンタックスエレメント202は、図8の上段に示されるように、最後の非ゼロ係数以前のゼロ係数の個数であるので、zeros_allよりzeros_rightを減算することにより求めることができる。
【００７７】
total_zerosシンタックスエレメントが生成されると、total_zeros符号化部132（図4）は、ステップS65において、制御部124によって起動され、例えば、図11や図12に示されるような、ブロックサイズ（係数の数）に応じたtotal_zerosシンタックスエレメント適応的可変長符号テーブルを用いて、そのtotal_zerosシンタックスエレメントの符号化を行う。
【００７８】
total_zerosシンタックスエレメントの符号化が終了すると、total_zeros符号化部132は、total_zerosシンタックスエレメント生成符号化処理を終了する。
【００７９】
また、シンタックス生成部122は、制御部124に制御されて、以上の処理と並行して、非ゼロ係数（trailing_ones_sign_flagシンタックスエレメントおよびlevelシンタックスエレメント）を係数格納部103より読み出して符号化する。このとき、シンタックス生成部122（図4）は、有意マップを用いて1つの非ゼロ係数のアドレスを生成し、係数格納部103から非ゼロ係数を1つ読み出し、nz_coeff符号化部134は、バッファリングしたりせずに直ぐにそれを符号化する。
【００８０】
図13のフローチャートを参照して、シンタックス生成符号化部104による非ゼロ係数生成符号化処理の流れの例を説明する。
【００８１】
なお、trailing_ones_sign_flagシンタックスエレメントの符号化は、後述するcoeff_tokenシンタックスエレメントの符号化より前に行われる。適応的可変長符号化装置100は、H.264方式で規定された順序に出力するために最大で3bitのtrailing_ones_sign_flagシンタックスエレメントの符号を、符号一時格納部106（図3）に格納しておき、coeff_tokenシンタックスエレメントの符号化と、最初に符号化するlevelシンタックスエレメントの符号化が終わった時点で、trailing_ones_sign_flagシンタックスエレメント、coeff_tokenシンタックスエレメント、および最初のlevelシンタックスエレメントの符号を一括して、選択部107を通しビットストリームとして出力する。
【００８２】
ステップS81において、シンタックス生成部122は、TrailingOnesシンタックスエレメントの値を初期化して「0」にする。また、シンタックス生成部122は、変数remain_nz_coeffの値を初期化してTotalCoeff（非ゼロ係数の総数）に設定する。ステップS82において、シンタックス生成部122は、その変数remain_nz_coeffの値が「0」より大きいか否かを判定し、値が「0」より大きく、まだ未処理の非ゼロ係数が存在すると判定した場合、処理をステップS83に進め、変数remain_nz_coeffの値を「1」減算し、ステップS84に処理を進める。
【００８３】
ステップS84において、シンタックス生成部122は、パターンマッチング部155、シフト量カウント部157、およびアドレス生成部158等を用いて、有意マップから逆スキャン順序で非ゼロ係数のメモリアドレスを算出する。つまり、パターンマッチング部155は、有意マップパターンテーブルを用いて有意マップのパターンマッチングを行ってビットシフト量を求め、シフト量カウント部157は、そのビットシフト量を積算し、アドレス生成部158は、そのカウント値に基づいて非ゼロ係数のメモリアドレスを生成する。
【００８４】
上述したように、パターンマッチング部155は、パターンテーブルを用いて有意マップのビットパターンよりzeros_rightを求めるが、その際、ビットシフト量も求める。このビットシフト量の値が有意マップ上での最終係数の位置を示す。例えば、図8の下段に示される有意マップ201の場合、右から5番目に位置する1bitシンボルが最終係数に対応する。つまり、図8の下段に示される有意マップ201の例の場合、最終係数のnz_coeff_pos207（level若しくはtrailing_oneの位置）は5となる。アドレス生成部158は、このnz_coeff_posと、符号化対象ブロックがマクロブロックのどの位置にあるかという情報を用いて、非ゼロ係数アドレスを生成する。
【００８５】
メモリアドレスが生成されると、シンタックス生成部122は、ステップS85において、この非ゼロ係数アドレスを用いて係数格納部103にアクセスし、所望の非ゼロ係数を読み出す。シンタックス生成部122は、ステップS86において、読み出された非ゼロ係数の絶対値が「1」であるか否かを判定し、「1」であると判定した場合、処理をステップS87に進める。ステップS87において、nz_coeff符号化部134は、trailing_ones_sign_flagシンタックスエレメントを符号化する。
【００８６】
シンタックス生成部122は、ステップS88においてTrailingOnesシンタックスエレメントの値に「1」を加算し、ステップS89においてTrailingOnesシンタックスエレメントの値が「3」になったか否かを判定する。TrailingOnesシンタックスエレメントの値が「3」でない、つまり「0」以上「2」以下の場合、制御部124は、処理をステップS82に戻し、以上の処理を繰り返し実行させる。
【００８７】
つまり、パターンマッチング部155は、マッチングを行った有意マップを、算出したビットシフト量だけ可変右ビットシフト部159を用いて右にシフトさせ、有意マップ一時格納部160に一時的に格納させ、スイッチ回路154を介して、再度、そのビットシフトさせた有意マップを所定のタイミングで取得し、再度パターンマッチングを行う。
【００８８】
そして、ステップS89において、TrailingOnesシンタックスエレメントの値が「3」になった場合、シンタックス生成部122は、ステップS91に処理を進める。なお、ステップS86において、非ゼロ係数の絶対値が「1」ではないと判定した場合、制御部124は、処理をステップS91に進める。
【００８９】
ステップS91において、nz_coeff符号化部134は、レベル符号化処理を実行し、levelシンタックスエレメントを符号化する。このレベル符号化処理の詳細については、図14のフローチャートを参照して後述する。
【００９０】
ステップS91の処理が終了すると、シンタックス生成部122は、非ゼロ係数生成符号化処理を終了する。なお、ステップS82において、変数remain_nz_coeffの値が「0」以下であると判定した場合、シンタックス生成部122は、非ゼロ係数生成符号化処理を終了する。
【００９１】
次に、図14のフローチャートを参照して、図13のステップS91において実行されるレベル符号化処理の流れの例を説明する。
【００９２】
ステップS111において、シンタックス生成部122は、変数remain_nz_coeffの値が「0」より大きいか否かを判定し、「0」より大きく、まだ未処理の非ゼロ係数が存在すると判定した場合処理をステップS112に進め、変数remain_nz_coeffの値を「1」減算し、ステップS113に処理を進める。
【００９３】
ステップS113において、シンタックス生成部122は、trailing_ones_sign_flagシンタックスエレメントの場合と同様に、有意マップから逆スキャン順序で非ゼロ係数のメモリアドレスを算出し、ステップS114において、算出したアドレスの非ゼロ係数を読み出す。ステップS115において、nz_coeff符号化部134は、levelシンタックスエレメントを符号化し、処理をステップS111に戻す。
【００９４】
以上のようにステップS111乃至ステップS115の処理が繰り返し実行され、ステップS111において、変数remain_nz_coeffの値が「0」以下であると判定した場合、シンタックス生成部122は、レベル符号化処理を終了し、処理を図13のステップS91に戻し、非ゼロ係数生成符号化処理を終了させる。
【００９５】
次に、図15のフローチャートを参照して、シンタックス生成符号化部104により実行されるrun_beforeシンタックスエレメント生成符号化処理の流れの例を説明する。
【００９６】
ステップS131において、シンタックス生成部122の可変右ビットシフト部159（図5）は、有意マップを、パターンマッチング部155により算出されたビットシフト量分、すなわち最後の非ゼロ係数に対応するnz_coeff_pos分右にビットシフトする。
【００９７】
ステップS132において、シンタックス生成部122は、最終係数の左側に存在するゼロ係数の総数を示す変数zeros_leftの値をtotal_zerosシンタックスエレメントの値に設定する。
【００９８】
ステップS133において、シンタックス生成部122は、zeros_leftの値が「0」より大きいか否かを判定し、大きいと判定した場合、処理をステップS134に進める。ステップS134において、パターンマッチング部155は、パターンマッチングを行い、有意マップからrun_beforeシンタックスエレメントを算出する。図8の下段に示されるように、run_beforeシンタックスエレメント206は、有意マップ201に含まれる、値が「1」の各ビットの前の「0」のビットの連続数を示す。従って、有意マップをビットシフト量分右にビットシフトすることで、run_beforeシンタックスエレメント206は、zeros_right203を求める場合と同様にパターンマッチングにより求めることができる。
【００９９】
ステップS135において、run_before符号化部133は、run_beforeシンタックスエレメントが生成される度に、例えば図16に示されるような可変長の符号化テーブルを用いて、そのrun_beforeシンタックスエレメントを随時符号化する。
【０１００】
可変右ビットシフト部159は、ステップS136において、有意マップを、パターンマッチング部155により算出されたビットシフト量分右にビットシフトする。シンタックス生成部122は、ステップS137において、zeros_leftの値よりrun_beforeシンタックスエレメントの値を減算し、処理をステップS133に戻す。
【０１０１】
ステップS133において、zeros_leftの値が「0」以下であると判定した場合、シンタックス生成部122は、run_beforeシンタックスエレメント生成符号化処理を終了する。
【０１０２】
以上のようにして、シンタックス生成部122は、非ゼロ係数アドレスを求めると同期してrun_beforeを求めることができる。このことを図17に示す。図17においては、上から下に進むように処理の進行が表されている。上述したように、最初に、ジグザグスキャン部121（図4）より読み出された有意マップ（一番上の段）を用いてパターンマッチングが行われ、zeros_rightと最初に処理する非ゼロ係数のnz_coeff_posが求められる。図17の例においては、zeros_rightが「4」であり、nz_coeff_posが「5」である。
【０１０３】
次に先ほど読み出した有意マップを、最初の状態（一番上の段）からビットシフト量分右にビットシフトされた有意マップ（上から2段目）に対して最初と同様にパターンマッチングが行われ、最初のrun_beforeシンタックスエレメントと2番目に処理する非ゼロ係数のnz_coeff_posが求められる。図17の例においては、run_beforeシンタックスエレメントが「1」であり、nz_coeff_posが「7」である。
【０１０４】
以上のようなビットシフトを図15のS133の条件が成り立つ、すなわちzeros_leftの値が「0」より大きい間繰り返すことで、シンタックス生成部122は、符号化ブロックを参照することなく、符号化ブロックのすべての非ゼロ係数とrun_beforeシンタックスエレメントを求めることができる。
【０１０５】
なお、適応的可変長符号化装置100は、H.264方式で規定された順序に出力するために、total_zerosシンタックスエレメントおよびrun_beforeシンタックスエレメントの符号を合わせた最大30bitを符号一時格納部106に格納しておき、すべてのlevelシンタックスエレメントの符号化が終わった時点で、total_zerosシンタックスエレメントとすべてのrun_beforeシンタックスエレメントの符号を一括して、選択部107を通しビットストリームとして出力する。符号一時格納部106で格納しておく必要のある符号の最大bit量はtrailing_ones_sign_flagシンタックスエレメント、total_zerosシンタックスエレメント、そして、run_beforeシンタックスエレメントの最大総bit量33bitでよい。すなわち、適応的可変長符号化装置100は、回路規模が大幅に増大することなく処理の高速化を実現することができる。
【０１０６】
非ゼロ係数の生成符号化処理でTrailingOnesシンタックスエレメントが生成された時点で制御部124は、それを受けてcoeff_token符号化部131を起動し、coeff_tokenシンタックスエレメントを符号化する。
【０１０７】
図18のフローチャートを参照して、coeff_token符号化部131により実行されるcoeff_tokenシンタックスエレメント符号化処理の流れの例を説明する。
【０１０８】
最初に、ステップS151において、coeff_token符号化部131は、隣接情報格納部105に格納されている、隣接するブロックのTotalCoeffシンタックスエレメントを取得し、それに基づいて、符号化に利用するVLC（Variable Length Code）テーブルを選択する。coeff_tokenシンタックスエレメントの符号化は、隣接するブロックのTotalCoeffシンタックスエレメントによって参照する可変長符号化テーブルが異なる。図19乃至図22は、その可変長符号化テーブルの例を示す図である。coeff_token符号化部131は、隣接情報格納部105から隣接ブロックのTotalCoeffを読み出し、例えば図19乃至図22のように予め用意された複数の可変長符号化テーブルの中から、参照するテーブルを選択する。
【０１０９】
可変長符号化テーブルを選択すると、coeff_token符号化部131は、ステップS152において、その選択したテーブルを用いて、TotalCoeffシンタックスエレメントおよびTrailingOnesシンタックスエレメントに基づいて、coeff_tokenを符号化する。coeff_tokenを符号化すると、coeff_token符号化部131は、coeff_tokenシンタックスエレメント符号化処理を終了する。
【０１１０】
以上のような有意マップを用いた各シンタックスエレメント符号化処理の並列化について、図23に示されるような係数ブロックを処理対象とする場合について説明する。図23の左側に示される係数ブロック301は、直交変換係数により構成される4×4のブロックであり、図23の右側に示される係数ブロック302は、係数ブロック301に基づいて生成された、シンタックスエレメントにより構成される4×4のブロックである。
【０１１１】
このような係数ブロック301より係数ブロック302の各シンタックスエレメントを生成して符号化する場合、従来の方法においては、図24に示されるように、各シンタックスエレメントを生成するために全係数にアクセスするので、必ず16サイクル必要となり、係数へのアクセス遅延サイクルと符号化処理サイクルと合わせて全体として31サイクル必要となる。
【０１１２】
これに対して、本発明を適用した適応的可変長符号化装置100においては、有意マップを用いることでシンタックスエレメントを生成するために全係数にアクセスする必要がなく、無駄な係数へのアクセスを削減することができる。また、シンタックスエレメントの符号化を並列処理するため、図25に示されるように、10サイクルで処理可能となる。
【０１１３】
図25に示されるように、まずTotalCoeffシンタックスエレメントとtotal_zerosシンタックスエレメントの生成が行われ、次に、total_zerosシンタックスエレメントの符号化が行われる。また、同サイクルにおいて、非ゼロ係数（trailing_ones_sign_flagシンタックスエレメント（t1_sign）とlevelシンタックスエレメント）の読み出し要求（read）が係数格納部103に対して行われる。なお、図25の例においては、非ゼロ係数の読み出し要求があってから2サイクル後にアクセスした係数が読み出せるようになされている。このアクセス遅延サイクル（アクセスlatency）は、実際にはシステムによって異なる。
【０１１４】
また、total_zerosシンタックスエレメントの生成符号化処理が終わると、次サイクルからrun_beforeシンタックスエレメントの生成符号化が開始される。すなわち、図25に示されるように、本発明を適用した適応的可変長符号化装置100は、非ゼロ係数の符号化とrun_beforeシンタックスエレメントの生成符号化を並列的に行うことでサイクル数の削減を実現する。
【０１１５】
従来の場合、仮に、このように非ゼロ係数の符号化とrun_beforeシンタックスエレメントの符号化を並列処理するとしても、そのためには、符号化ブロックに存在し得る最大数の非ゼロ係数とrun_beforeシンタックスエレメントを格納しておくためのバッファが必要であったが、本発明の場合、有意マップを用いて符号化を行うので、非ゼロ係数の符号化のときのみ係数格納部103の係数に直接アクセスすることにより、非ゼロ係数を格納しておくためのバッファが不要となり、かつ、アクセス遅延も最小限に抑制することができる。また、run_beforeシンタックスエレメントは有意マップから生成可能であり、符号化を行うときに随時有意マップから生成することでバッファが不要となり、回路規模の増大を抑制し、かつ、処理の高速化を実現することができる。
【０１１６】
図26乃至図28を参照して、最も多くのシンタックスエレメントが発生する場合の例を説明する。図26の左側に示される係数ブロック401は、最も多くのシンタックスエレメントが発生する場合の、直交変換係数により構成される4×4のブロックであり、図26の右側に示される係数ブロック402は、最も多くのシンタックスエレメントが発生する場合の、係数ブロック401に基づいて生成された、シンタックスエレメントにより構成される4×4のブロックである。
【０１１７】
この場合、従来の方法においては、図27に示されるように、非ゼロ係数の符号化とrun_beforeシンタックスエレメントの符号化を逐次処理するため全体で49サイクル必要となる。これに対して、本発明の方法の場合、非ゼロ係数の符号化とrun_beforeシンタックスエレメントの符号化を並列処理するため18サイクルで処理が終了する。よって、最大31サイクルの削減が可能となる。
【０１１８】
以上のように、本発明を適用した適応的可変長符号化装置100は、各シンタックスエレメント生成符号化処理を並列に行うことができ、処理サイクル数を削減することができる。また、本発明を適用した適応的可変長符号化装置100は、各シンタックスエレメントの生成に有意マップを用いることで非ゼロ係数への随時直接アクセスが可能となること、および非ゼロ係数以外のシンタックスエレメントは有意マップからのみで生成が可能であり符号化のたびに随時生成することができることによりシンタックスエレメントを保持しておくバッファが不要である。つまり、本発明を適用した適応的可変長符号化装置100は、回路規模の増大を抑制し、かつ、処理の高速化が可能となる。
【０１１９】
なお、上述したシンタックスエレメント以外のシンタックスエレメントの生成符号化においても有意マップを用いるようにしてももちろんよい。例えば、coded_block_patternシンタックスエレメントの生成に有意マップを用いるようにしてもよい。この場合、適応的可変長符号化装置100は、各1bitシンボルのビット間でOR演算を行うことでcoded_block_patternシンタックスエレメントの値を判別することが可能となり、係数が格納されているメモリへのアクセス数を減らすことが可能となる。
【０１２０】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。この場合、例えば、図29に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０１２１】
図29において、パーソナルコンピュータ500のCPU（Central Processing Unit）501は、ROM（Read Only Memory）502に記憶されているプログラム、または記憶部513からRAM（Random Access Memory）503にロードされたプログラムに従って各種の処理を実行する。RAM503にはまた、CPU501が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１２２】
CPU501、ROM502、およびRAM503は、バス504を介して相互に接続されている。このバス504にはまた、入出力インタフェース510も接続されている。
【０１２３】
入出力インタフェース510には、キーボード、マウスなどよりなる入力部511、CRTやLCDなどよりなるディスプレイ、並びにスピーカなどよりなる出力部512、ハードディスクなどより構成される記憶部513、モデムなどより構成される通信部514が接続されている。通信部514は、インターネットを含むネットワークを介しての通信処理を行う。
【０１２４】
入出力インタフェース510にはまた、必要に応じてドライブ515が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア521が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部513にインストールされる。
【０１２５】
上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１２６】
この記録媒体は、例えば、図29に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM,DVDを含む）、光磁気ディスク（MDを含む）、もしくは半導体メモリなどよりなるリムーバブルメディア521により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM502や、記憶部513に含まれるハードディスクなどで構成される。
【０１２７】
このように、上述した一連の処理をソフトウェアにより行う場合も、CAVLC符号化処理に有意マップを用いることで、係数が格納されているメモリへのアクセス数を減らすこと、およびシンタックスエレメントの生成符号化のためのループ回数が係数の数で固定ではなく非ゼロ係数の数の最小のループ回数で処理ができ処理サイクル数を削減することが可能となる。
【０１２８】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１２９】
また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。
【０１３０】
なお、以上において、1つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて1つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。
【産業上の利用可能性】
【０１３１】
本発明は、符号化装置に適用することが可能である。
【図面の簡単な説明】
【０１３２】
【図１】従来の画像符号化装置の構成例を示すブロック図である。
【図２】有意マップの構成例を説明する図である。
【図３】本発明を適用した適応的可変長符号化装置の構成例を示すブロック図である。
【図４】図3のシンタックス生成符号化部の構成例を示すブロック図である。
【図５】図4のシンタックス生成部の構成例を示すブロック図である。
【図６】CAVLC処理の流れの例を説明するフローチャートである。
【図７】TotalCoeffシンタックスエレメント生成処理の流れの例を説明するフローチャートである。
【図８】有意マップとシンタックスエレメントの関係を説明する模式図である。
【図９】total_zerosシンタックスエレメント生成符号化処理の流れの例を説明するフローチャートである。
【図１０】有意マップパターンテーブルの構成例を示す模式図である。
【図１１】4×4ブロックtotal_zerosシンタックスエレメント適応的可変長テーブルの構成例を示す模式図である。
【図１２】2×2ブロックtotal_zerosシンタックスエレメント適応的可変長テーブルの構成例を示す模式図である。
【図１３】非ゼロ係数生成符号化処理の流れの例を説明するフローチャートである。
【図１４】レベル符号化処理の流れの例を説明するフローチャートである。
【図１５】run_beforeシンタックスエレメント生成符号化処理の流れの例を説明するフローチャートである。
【図１６】run_beforeシンタックスエレメントの可変長符号化テーブルの構成例を示す模式図である。
【図１７】zeros_right,run_before、および、nz_coeff_posの算出の流れの例を説明する模式図である。
【図１８】coeff_tokenシンタックスエレメント符号化処理の流れの例を説明するフローチャートである。
【図１９】coeff_tokenシンタックスエレメント適応的可変長符号化テーブルの構成例を示す模式図である。
【図２０】coeff_tokenシンタックスエレメント適応的可変長符号化テーブルの構成例を示す模式図である。
【図２１】coeff_tokenシンタックスエレメント適応的可変長符号化テーブルの構成例を示す模式図である。
【図２２】coeff_tokenシンタックスエレメント適応的可変長符号化テーブルの構成例を示す模式図である。
【図２３】係数ブロックの例を示す模式図である。
【図２４】従来のCAVLC処理の流れの例を説明するタイミングチャートである。
【図２５】本発明を適用したCAVLC処理の流れの例を説明するタイミングチャートである。
【図２６】係数ブロックの他の例を示す模式図である。
【図２７】従来のCAVLC処理の流れの、他の例を説明するタイミングチャートである。
【図２８】本発明を適用したCAVLC処理の流れの、他の例を説明するタイミングチャートである。
【図２９】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０１３３】
53  有意マップ，  100  適応的可変長符号化装置，  101  DCT量子化有意マップ生成部，  102  有意マップ格納部，  103  係数格納部103，  104  シンタックス生成符号化部，  105  隣接情報格納部，  106  符号一時格納部，  107  選択部，  108  制御部，  121  ジグザグスキャン部，  122  シンタックス生成部，  123  シンタックス符号化部，  124  制御部，  131  coeff_token符号化部，  132  total_zeros符号化部，  133  run_before符号化部，  134  nz_coeff符号化部，  151  16bit加算部，  152  bit反転部，  153  16bit加算部，  154  スイッチ回路，  155  パターンマッチング部，  156  減算部，  157  シフト量カウント部，  158  アドレス生成部，  159  可変右ビットシフト部，  160  有意マップ一時格納部
【図１】
2008141382.tif 000003
【図２】
2008141382.tif 000004
【図３】
2008141382.tif 000005
【図４】
2008141382.tif 000006
【図５】
2008141382.tif 000007
【図６】
2008141382.tif 000008
【図７】
2008141382.tif 000009
【図８】
2008141382.tif 000010
【図９】
2008141382.tif 000011
【図１０】
2008141382.tif 000012
【図１１】
2008141382.tif 000013
【図１２】
2008141382.tif 000014
【図１３】
2008141382.tif 000015
【図１４】
2008141382.tif 000016
【図１５】
2008141382.tif 000017
【図１６】
2008141382.tif 000018
【図１７】
2008141382.tif 000019
【図１８】
2008141382.tif 000020
【図１９】
2008141382.tif 000021
【図２０】
2008141382.tif 000022
【図２１】
2008141382.tif 000023
【図２２】
2008141382.tif 000024
【図２３】
2008141382.tif 000025
【図２４】
2008141382.tif 000026
【図２５】
2008141382.tif 000027
【図２６】
2008141382.tif 000028
【図２７】
2008141382.tif 000029
【図２８】
2008141382.tif 000030
【図２９】
2008141382.tif 000031