JP2010258927A - 符号データ処理装置、方法及びプログラム - Google Patents

Abstract

【課題】エントロピー符号に基づく符号データ列を効率的に復号すること。
【解決手段】本発明にかかる符号データ処理装置は、複数のＰＥ（Processor Elements）を有し、エントロピー符号に基づく符号データ列を復号するものであり、符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを複数のＰＥへ分配して入力する分配入力手段と、分配入力手段により入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号手段と、並列復号手段により特定された復号データ及び符号長を用いて、符号データ列に対応する復号データ列を生成する生成手段と、を備える。
【選択図】図１

Description

本発明は、符号データ処理装置、方法及びプログラムに関し、特に、エントロピー符号に基づく符号データ列を復号する符号データ処理装置、方法及びプログラムに関する。

近年、自動車等の組み込み分野においても車載カメラを用いて運転者に注意を促すシステム等が実用化されている。このようなマルチメディアの処理は大量のデータを扱うため、組み込み用途のプロセッサでは時間がかかる事が多い。

一般に、マルチメディアの処理は、大量のデータに似たような処理を行う場面が多く、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｌｔｉｐｌｅ Ｄａｔａ）プロセッサ等の並列処理が可能なプロセッサを用いると効率良く処理が可能であることが知られている。

一方、組み込み分野ではメモリ等の資源が限られているため、データの圧縮及び伸張が必要な場面も多い。静止画像の圧縮で有名なＪＰＥＧ（Joint Photographic Experts Group）にもエントロピー符号の一種であるハフマン符号が利用されており、これらの処理の高速化が望まれている。

特許文献１には、ハフマン符号化されたデータを復号化する際のハフマン符号のサーチを高速かつ少ないサーチテーブルで行う復号化方法に関する技術が開示されている。特許文献１では、ハフマン符号を、符号長が８ビットまでの第１のグループと、９ビットから１２ビットまでの第２のグループと、１３ビット以上の第３のグループに分け、第１乃至第３のグループのハフマン符号をアドレスとし、そのアドレスに、対応する符号長、有効係数を示したデータを書き込む事により、第１乃至第３のサーチテーブルを予め展開しておき、ハフマン符号化されたデータの符号長及び有効係数を、第１乃至第３のサーチテーブルを参照して確定する事により、目的のハフマン符号をサーチし、復号化する。

図７は、特許文献１にかかるハフマン符号の復号方法の流れを示すフローチャート図である。まず、変数ＶＤにハフマンデータを代入（Ｓ７１）し、第１のサーチテーブルについて参照する（Ｓ７２及びＳ７３）。これにより、符号長が導き出される。

ここで、符号長が８ビット以下であれば（Ｓ７４のＮＯ）、第１のサーチテーブルにより正しい符号長が導き出されたこととなる。その後、符号長、グループ番号分だけ、左シフトして次のテーブルをサーチする（Ｓ８０）。また、符号長が９ビット以上であれば（Ｓ７４のＹＥＳ）、第２のサーチテーブルについて参照する（Ｓ７５及びＳ７６）。この時点では、符号長が９ビット以上である事しか分からないためである。これにより、符号長が導き出される。

ここで、符号長が９ビット以上１２ビット以下であれば（Ｓ７７のＮＯ）、第２のサーチテーブルにより正しい符号長が導き出されたこととなる。その後、符号長、グループ番号分だけ、左シフトして次のテーブルをサーチする（Ｓ８０）。また、符号長が１３ビット以上であれば（Ｓ７７のＹＥＳ）、第３のサーチテーブルについて参照（Ｓ７８及びＳ７９）し、１３ビット以上のコードを確定する。これにより、符号長が導き出される。このように、特許文献１では、最大でもテーブルを３回参照する事で、目的のハフマンテーブルを見つけることができる。

特開平７−１０７３０３号公報

しかしながら、特許文献１には、複数のプロセッサを用いて並列処理する場合に、効率よく復号化を行うことができないという問題点がある。ここで、エントロピー符号は、出現確率が高いシンボルには短い符号語長を、出現確率が低いシンボルには長い符号語長を割り当てるという性質がある。そのため、復号を行う場合は現在先頭にある符号語が可変長であるという理由から、先頭のデータを一度復号し、それと同時に対応する符号長（ビット長）を確定しないと、次のデータの先頭位置の特定ができない。

本発明の第１の態様にかかる符号データ処理装置は、複数のＰＥ（Processor Elements）を有し、エントロピー符号に基づく符号データ列を復号する符号データ処理装置であって、前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを前記複数のＰＥへ分配して入力する分配入力手段と、前記分配入力手段により入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号手段と、前記並列復号手段により特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成手段と、を備える。

本発明の第２の態様にかかる符号データ処理方法は、複数のＰＥ（Processor Elements）を有する符号データ処理装置を用いて、エントロピー符号に基づく符号データ列を復号する符号データ処理方法であって、前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを前記複数のＰＥへ分配して入力する分配入力ステップと、前記分配入力ステップにより入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号ステップと、前記並列復号ステップにより特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成ステップと、を含む。

本発明の第３の態様にかかる符号データ処理プログラムは、エントロピー符号に基づく符号データ列を復号する符号データ処理を、複数のＰＥ（Processor Elements）を備えるコンピュータに実行させる符号データ処理プログラムであって、前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを複数のＰＥへ分配して入力する分配入力ステップと、前記分配入力ステップにより入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号ステップと、前記並列復号ステップにより特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成ステップと、を備える。

上述した本発明の第１、第２及び第３の態様にかかるにかかる符号データ処理装置、方法及びプログラムによれば、エントロピー符号に基づく符号データ列の全てのビットを復号処理における先頭位置とみなして固定長の符号データを抽出し、抽出した各符号データを複数のＰＥに入力することで、複数のＰＥ毎に復号処理を並列に行わせるものである。そして、復号処理により特定された復号データ及び符号長を用いることにより、入力された符号データ列に対応する復号データ列を生成するものである。これにより、符号データ列の先頭のデータの復号結果を待つことなく、全ての復号結果を得ることができる。そのため、得られた復号結果の中から、符号長を用いて先頭から復号データを結合することにより、入力された符号データ列に対応する復号データ列を生成することができる。

本発明により、エントロピー符号に基づく符号データ列を効率的に復号する符号データ処理装置、方法及びプログラムを提供することができる

本発明の実施の形態１にかかる符号データ処理装置の構成を示すブロック図である。 本発明の実施の形態１にかかる符号データ列の復号処理の流れを示すフローチャート図である。 本発明の実施の形態１にかかる各ＰＥが一定ビット列を読み込む処理の概念を説明するための図である。 本発明の実施の形態１にかかる各ＰＥがルックアップテーブルを参照する処理の概念を説明するための図である。 本発明の実施の形態１にかかる各ＰＥの復号処理結果を用いて復号データ列を生成する処理の概念を説明するための図である。 本発明の実施の形態２にかかる符号データ処理装置の構成を示すブロック図である。 関連技術にかかるハフマン符号の復号方法の流れを示すフローチャート図である。

以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。

＜発明の実施の形態１＞
図１は、本発明の実施の形態１にかかる符号データ処理装置１００の構成を示すブロック図である。符号データ処理装置１００は、エントロピー符号に基づく符号データ列を復号する並列処理プロセッサである。符号データ処理装置１００は、符号データ処理装置１００は、コントロールユニット１と、バス２と、ＰＥ（Processor Elements）群３とを備えるＳＩＭＤ（Single Instruction Multiple Data）型プロセッサである。ここでは、ＰＥ群３は、ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎという１２８個のＰＥを含むものとする。

コントロールユニット１は、バス２を介してＰＥ群３を制御する制御装置である。コントロールユニット１は、分配入力手段と、並列復号手段と、生成手段として機能する。分配入力手段は、符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、符号データ列の全てのビットを基準位置として行う。そして、分配入力手段は、抽出された複数の符号データをＰＥ群３へ分配して入力する。並列復号手段は、入力された符号データについての復号処理を、ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎ毎に並列して実行させる。生成手段は、ＰＥ群３により出力された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する。

具体的には、まず、分配入力手段は、ＰＥ群３の個数であるＰＥ数の基準位置について抽出処理を行う。次に、分配入力手段は、抽出されたＰＥ数の符号データをＰＥ群３のそれぞれへ均等に分配して入力しる。そして、分配入力手段は、入力した符号データについての並列復号手段における復号処理が終了した後に、未抽出の基準位置について抽出処理を行う。このようにして、符号データ処理装置１００は、分配入力手段及び並列復号手段を繰り返すとよい。これにより、入力された符号データ列を効率よく、ＰＥ群３に分配することができる。

さらに次のようにすることが望ましい。まず、分配入力手段は、符号データ列から１ビットずつＰＥ数回シフトした符号データ列の各先頭位置を基準位置として、当該基準位置から固定長を符号データとして抽出して抽出処理を行う。次に、分配入力手段は、抽出されたＰＥ数の符号データをＰＥ群３へ一つずつ分配して入力する。そして、分配入力手段は、入力した符号データについての並列復号手段における復号処理が終了した後に、基準位置をＰＥ数のビット分シフトした符号データ列の各先頭位置を基準位置として、抽出処理を行う。このようにして、符号データ処理装置１００は、分配入力手段及び並列復号手段を繰り返すとさらによい。これにより、入力された符号データ列をビット単位で漏れなく、ＰＥ群３に分配することができる。

また、生成手段は、符号データ列の先頭位置を含む第１の符号データに対応する復号データに、当該第１の符号データに対応する符号長分のビットを当該先頭位置からシフトした基準位置における第２の符号データに対応する第２の復号データを連結することにより、復号データ列を生成することが望ましい。これにより、同時に特定された複数の復号データの中から効率よく、必要な復号データを選択して、結合することができる。

ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎは、バス２を介して、コントロールユニット１からの指示に応じて動作する。ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎは、入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を行う。また、ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎは、それぞれに復号処理に用いるルックアップテーブル４及びバッファを備える。

ルックアップテーブル４は、符号値と、復号データと、符号長とを対応付けて格納する記憶領域である。ルックアップテーブル４は、符号値により一意に復号データ及び符号長を特定できるようにデータが格納されている。ここで、エントロピー符号は、符号化前の元データ列について、出現確率が高いシンボルにはより短い符号長、出現確率が低いシンボルにはより長い符号長を割り当てるものである。して、エントロピー符号は、先頭のビットからのビットの組み合わせが一意となるものである。そこで、符号値は、エントロピー符号に基づき符号化された符号を先頭から一部分又は全ての桁に含む符号データである。また、符号値の長さは、当該符号化された符号の最大長以上である。ここでは、符号値の長さを８ビットとする。つまり、符号値は、８ビットの固定長の符号データである。復号データは、符号値に対応する復号値である。符号長は、符号値の内、有効なデータの長さである。つまり、符号値は、８ビットの内、先頭から符号長の分が実際の符号である。

ここで、図４は、本発明の実施の形態１にかかるルックアップテーブル４の例である。例えば、符号値"０１１００１１１"において、復号データ"ａ"、符号長"３"である。そのため、符号値"０１１００１１１"の内、実際に有効なデータは、先頭の３桁である"０１１"となる。そして、"０１１"に対応する復号データが"ａ"である。

また、バッファは、ＰＥ群３において実行される復号処理の結果を格納する記憶領域である。具体的には、復号データ及び符号長を対応付けて格納する。そのため、ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎは、入力された符号データに対応する復号データ及び符号長をルックアップテーブル４から取得し、取得した復号データ及び符号長を対応付けてバッファに格納する。

バス２は、コントロールユニット１並びにＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎを接続し、データをやり取りするための伝送路である。

図２は、本発明の実施の形態１にかかる符号データ列の復号処理の流れを示すフローチャート図である。まず、コントロールユニット１は、カウンタｉに０を格納し、入力データ変数ｉｎに入力された符号データ列を格納する（Ｓ１１）。次に、コントロールユニット１は、入力データ変数ｉｎを１ビットずつシフトしたビットを基準位置として、入力データ変数ｉｎから固定長の符号データを抽出し、抽出した符号データを各ＰＥに入力する（Ｓ１２）。具体的には、入力データ変数ｉｎの中から、ＰＥ３ａは１ビット目から、ＰＥ３ｂは２ビット目から、ＰＥ３ｎは１２８ビット目からというように、夫々１ビットずつシフトしたビットを基準位置として符号データ列から一定ビット数分、ここでは、８ビット分を読み込む。

図３は、本発明の実施の形態１にかかる各ＰＥが一定ビット列を読み込む処理の概念を説明するための図である。符号データ列Ｄは、"０１１００１１１００・・・"から始まる符号データ列である。このとき、ＰＥ３ａは、先頭から８ビットである符号データＤ１を読み込む。また、ＰＥ３ｂは、２ビット目から８ビットである符号データＤ２を読み込む。さらに、ＰＥ３ｃは、３ビット目から８ビットである符号データＤ３を読み込む。

図２に戻り、ＰＥ群３は、それぞれルックアップテーブル４を参照し、入力された符号データに対応する復号データ及び符号長を取得し、それぞれが有するバッファへ格納する（Ｓ１３）。ここでは、ＰＥ群３に属するＰＥ毎に、復号データを格納するバッファとして配列word[ｉ]、符号長を格納するバッファとして配列next[ｉ]を有するものとする。また、このとき、ＰＥ群３は、コントロールユニット１により並列実行される。

図４は、本発明の実施の形態１にかかる各ＰＥがルックアップテーブルを参照する処理の概念を説明するための図である。このとき、ＰＥ３ａは、ルックアップテーブル４を参照し、符号データＤ１"０１１００１１１"に対応する復号データ"ａ"及び符号長"３"を取得する。そして、ＰＥ３ａは、自己の配列word[ｉ]に復号データ"ａ"を格納し、自己の配列next[ｉ]に符号長"３"を格納する。同様に、ＰＥ３ｂ及び３ｃについても、ルックアップテーブル４を参照し、それぞれ符号データＤ２及びＤ３に対応する復号データ及び符号長を取得し、自己の配列に格納する。

図２に戻り、ＰＥ群３においてステップＳ１３が終了した後に、コントロールユニット１は、カウンタｉを１加算し、入力データ変数ｉｎをＰＥ数ビット分左シフトする（Ｓ１４）。ここでは、コントロールユニット１は、入力データ変数ｉｎに格納された符号データ列を１２８ビット左シフトする。そして、コントロールユニット１は、入力データ変数ｉｎが空であるか否かを判定する（Ｓ１５）。入力データ変数ｉｎが空でないと判定された場合、コントロールユニット１は、ステップＳ１２へ進み、入力データ変数ｉｎが空となるまでの間、ステップＳ１２乃至Ｓ１６を繰り返す。

ステップＳ１５において、入力データ変数ｉｎが空と判定された場合、コントロールユニット１は、生成処理を行う。すなわち、コントロールユニット１は、ＰＥ群３の各ＰＥが有する配列word[ｉ]及びnext[ｉ]を参照し、入力された符号データ列の先頭に対応する復号データから符号長に基づいて連結を行い、復号データ列を生成する。

具体的には、まず、コントロールユニット１は、符号位置ｎ及びカウンタｊに０を格納する（Ｓ１６）。そして、コントロールユニット１は、以下の式（１）及び式（２）を実行する（Ｓ１７）。
out[ｊ]＝ＰＥ（ｎ％ＰＥ数）のword[ｎ／ＰＥ数] ・・・（１）
ｎ＝ｎ＋ＰＥ（ｎ％ＰＥ数）のnext[ｎ／ＰＥ数] ・・・（２）
ここで、out[ｊ]は、復号データ列を格納する配列である。また、ＰＥ３ａ、３ｂ、３ｃ、・・・及び３ｎを１、２、３、・・・、１２８の位置に対応付けるものとする。

そのため、ＰＥ（ｎ％ＰＥ数）は、符号位置ｎをＰＥ群３に属するＰＥの個数であるＰＥ数による除算し、余りをＰＥ群３に属するＰＥの先頭からの位置となる。そして、word[ｎ／ＰＥ数]は、ＰＥ（ｎ％ＰＥ数）が有する復号データの配列word[]において、符号位置ｎをＰＥ数による除算の商の位置に格納された復号データである。よって、式（１）は、ｊ番目のシンボルの復号データが復号データ列out[ｊ]に格納されることを示す。また、式（２）は、次の符号位置ｎが格納されることを示す。

図２に戻り、コントロールユニット１は、復号データ列out[ｊ]が空であるか否かを判定する（Ｓ１８）。復号データ列out[ｊ]が空でないと判定された場合、コントロールユニット１は、カウンタｊを１加算（Ｓ１９）し、ステップＳ１７へ進む。以降、コントロールユニット１は、復号データ列out[ｊ]が空であると判定されるまでの間、ステップＳ１７乃至Ｓ１９を繰り返す。

ステップＳ１８において、復号データ列out[ｊ]が空であると判定された場合、コントロールユニット１は、符号データ列の復号処理を終了する。

図５は、本発明の実施の形態１にかかる各ＰＥの復号処理結果を用いて復号データ列を生成する処理の概念を説明するための図である。初期状態として、符号位置ｎ及びカウンタｊは０であり、復号データ列out[]は空である。まず、コントロールユニット１は、ＰＥ３ａが有する配列word[０]から復号データ"ａ"を取得し、復号データ列out[０]に格納する。併せて、コントロールユニット１は、ＰＥ３ａが有する配列next[０]から符号長"３"を取得し、符号位置ｎに格納する。そして、コントロールユニット１は、ＰＥ３ａから３つ隣りのＰＥ３ｄが有する配列word[０]から復号データ"ｂ"を取得し、復号データ列out[１]に格納する。併せて、コントロールユニット１は、ＰＥ３ｄが有する配列next[０]から符号長"２"を取得し、符号位置ｎに格納する。そして、コントロールユニット１は、ＰＥ３ｄから２つ隣りのＰＥ３ｆが有する配列word[０]から復号データ"ｃ"を取得し、復号データ列out[２]に格納する。併せて、コントロールユニット１は、ＰＥ３ｆが有する配列next[０]から符号長"４"を取得し、符号位置ｎに格納する。以下、説明を省略する。このようにして、コントロールユニット１は、ＰＥ群３に属するＰＥが有する全ての復号結果の内、符号長に基づいて適切な復号データを選択し、結合することで、復号データ列を生成することができる。

上述したように本発明の実施の形態１では、符号データ列のビット列を並列に処理することにより、復号化の効率を上げることができる。その理由は、関連技術での処理時間をＰとすると、ＳＩＭＤの例において、ＰＥ数をＮ、エントロピー符号の平均符号長（１語当たり）をＬとし、復号データの生成処理時間をＴとした場合、本発明での処理時間はおよそＰ×（Ｌ／Ｎ）＋Ｔと表すことができるためである。例えば、Ｌ＝８、Ｎ＝１２８とした場合、関連技術に対して数倍〜１６倍の効率化が期待できると言える。つまり、本発明の実施の形態１により、エントロピー符号に基づく符号データ列を効率的に復号することができる。

＜発明の実施の形態２＞
本発明の実施の形態２は、本発明の実施の形態１の変形例である。本発明の実施の形態１では、ＳＩＭＤを例に説明したが、並列動作が可能なシステムであれば同様な事が実現できる。本発明の実施の形態２では、複数のＰＵ（Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔｓ）が並列に動作でき、全てのＰＵが一つのバスで接続されているシステムを例示する。尚、以下では、本発明の実施の形態１との違いを中心に説明し、同等の構成又は処理については、説明を省略する。

図６は、本発明の実施の形態２にかかる符号データ処理装置２００の構成を示すブロック図である。符号データ処理装置２００は、バス２と、ＰＵ５ａ、ＰＵ５ｂ、ＰＵ５ｃ、・・・及びＰＵ５ｎとを備える。符号データ処理装置２００は、制御プログラム（不図示）により、ＰＵ５ａに、コントロールユニット１と同等の処理を実行させる。つまり、ＰＵ５ａは、分配入力手段と、並列復号手段と、生成手段として機能する。また、ＰＵ５ａは、図２のステップＳ１３を除く処理を実行する。

また、符号データ処理装置２００は、当該制御プログラムにより、ＰＵ５ｂ、ＰＵ５ｃ、・・・及びＰＵ５ｎをＰＥ群５として、ＰＥ群３と同等の処理を実行させる。つまり、ＰＥ群５は、ＰＵ５ａの指示に基づき、図２のステップＳ１３の復号処理を並列実行する。

また、ＰＵ５ａ、ＰＵ５ｂ、ＰＵ５ｃ、・・・及びＰＵ５ｎのいずれが、コントロールユニット１の処理を実行するかは、上述した制御プログラムにより、任意に変更可能である。そのため、複数のＣＰＵが並列に動作するようなシステムにおいても、エントロピー符号の効率的な復号化が可能であり、組み込みソフトにおいても本発明の実施の形態１で示した構成をとることができ、同等の効果を奏することができる。そのため、本発明の実施の形態２により、エントロピー符号に基づく符号データ列を効率的に復号することができる

＜その他の実施の形態＞
本発明は、エントロピー符号の復号化に関し、特に組み込みソフトウェアにおけるエントロピー符号の復号方法に適用可能である。

尚、上述の実施の形態では、本発明をハードウェアの構成として説明したが、本発明は、これに限定されるものではない。本発明は、任意の処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、記録媒体に記録して提供することも可能であり、また、インターネットその他の通信媒体を介して伝送することにより提供することも可能である。また、記憶媒体には、例えば、フレキシブルディスク、ハードディスク、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ、ＲＯＭカートリッジ、バッテリバックアップ付きＲＡＭメモリカートリッジ、フラッシュメモリカートリッジ、不揮発性ＲＡＭカートリッジ等が含まれる。また、通信媒体には、電話回線等の有線通信媒体、マイクロ波回線等の無線通信媒体等が含まれる。

さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。

１００ 符号データ処理装置
２００ 符号データ処理装置
１ コントロールユニット
２ バス
３ ＰＥ群
３ａ ＰＥ
３ｂ ＰＥ
３ｃ ＰＥ
３ｎ ＰＥ
４ ルックアップテーブル
５ ＰＥ群
５ａ ＰＵ
５ｂ ＰＵ
５ｃ ＰＵ
５ｎ ＰＵ
Ｄ 符号データ列
Ｄ１ 符号データ
Ｄ２ 符号データ
Ｄ３ 符号データ

Claims (17)

1. 複数のＰＥ（Processor Elements）を有し、エントロピー符号に基づく符号データ列を復号する符号データ処理装置であって、
   前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを前記複数のＰＥへ分配して入力する分配入力手段と、
   前記分配入力手段により入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号手段と、
   前記並列復号手段により特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成手段と、
   を備える符号データ処理装置。
2. 前記分配入力手段は、前記複数のＰＥの個数であるＰＥ数の前記基準位置について前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ均等に分配して入力し、入力した符号データについての前記並列復号手段における復号処理が終了した後に、未抽出の基準位置について前記抽出処理を行うことを特徴とする請求項１に記載の符号データ処理装置。
3. 前記分配入力手段は、前記符号データ列から１ビットずつ前記ＰＥ数回シフトした符号データ列の各先頭位置を前記基準位置として、当該基準位置から固定長を符号データとして抽出して前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ一つずつ分配して入力し、入力した符号データについての前記並列復号手段における復号処理が終了した後に、前記基準位置を前記ＰＥ数のビット分シフトした符号データ列の各先頭位置を前記基準位置として、前記抽出処理を行うことを特徴とする請求項２に記載の符号データ処理装置。
4. 前記固定長の符号データに対応する復号データと、当該固定長の符号データの内、有効なデータの長さである符号長とを格納するルックアップテーブルをさらに備え、
   前記並列復号手段は、入力された符号データに対応する復号データ及び符号長を前記ルックアップテーブルから取得することにより前記復号処理を、前記複数のＰＥ毎に並列して実行させることを特徴とする請求項１乃至３のいずれか１項に記載の符号データ処理装置。
5. 前記生成手段は、前記符号データ列の先頭位置を含む第１の符号データに対応する復号データに、当該第１の符号データに対応する符号長分のビットを当該先頭位置からシフトした基準位置における第２の符号データに対応する第２の復号データを連結することにより、前記復号データ列を生成することを特徴とする請求項１乃至４のいずれか１項に記載の符号データ処理装置。
6. 前記符号データ処理装置は、前記複数のＰＥを制御するコントロールユニットをさらに有するＳＩＭＤ（Single Instruction Multiple Data）型プロセッサであることを特徴とする請求項１乃至５のいずれか１項に記載の符号データ処理装置。
7. 前記符号データ処理装置は、複数のプロセッサユニットを備え、
   前記複数のプロセッサユニットは、前記複数のＰＥと、当該複数のＰＥを制御する制御用プロセッサとを含むことを特徴とする請求項１乃至５のいずれか１項に記載の符号データ処理装置。
8. 複数のＰＥ（Processor Elements）を有する符号データ処理装置を用いて、エントロピー符号に基づく符号データ列を復号する符号データ処理方法であって、
   前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを前記複数のＰＥへ分配して入力する分配入力ステップと、
   前記分配入力ステップにより入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号ステップと、
   前記並列復号ステップにより特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成ステップと、
   を含む符号データ処理方法。
9. 前記分配入力ステップは、前記複数のＰＥの個数であるＰＥ数の前記基準位置について前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ均等に分配して入力し、入力した符号データについての前記並列復号ステップにおける復号処理が終了した後に、未抽出の基準位置について前記抽出処理を行うことを特徴とする請求項８に記載の符号データ処理方法。
10. 前記分配入力ステップは、前記符号データ列から１ビットずつ前記ＰＥ数回シフトした符号データ列の各先頭位置を前記基準位置として、当該基準位置から固定長を符号データとして抽出して前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ一つずつ分配して入力し、入力した符号データについての前記並列復号ステップにおける復号処理が終了した後に、前記基準位置を前記ＰＥ数のビット分シフトした符号データ列の各先頭位置を前記基準位置として、前記抽出処理を行うことを特徴とする請求項９に記載の符号データ処理方法。
11. 前記符号データ処理装置は、
    前記固定長の符号データに対応する復号データと、当該固定長の符号データの内、有効なデータの長さである符号長とを格納するルックアップテーブルをさらに備え、
    前記並列復号ステップは、入力された符号データに対応する復号データ及び符号長を前記ルックアップテーブルから取得することにより前記復号処理を、前記複数のＰＥ毎に並列して実行させることを特徴とする請求項８乃至１０のいずれか１項に記載の符号データ処理方法。
12. 前記生成ステップは、前記符号データ列の先頭位置を含む第１の符号データに対応する復号データに、当該第１の符号データに対応する符号長分のビットを当該先頭位置からシフトした基準位置における第２の符号データに対応する第２の復号データを連結することにより、前記復号データ列を生成することを特徴とする請求項８乃至１１のいずれか１項に記載の符号データ処理方法。
13. エントロピー符号に基づく符号データ列を復号する符号データ処理を、複数のＰＥ（Processor Elements）を備えるコンピュータに実行させる符号データ処理プログラムであって、
    前記符号データ列から基準位置に基づく固定長の符号データを抽出する抽出処理を、前記符号データ列の全てのビットを基準位置として行い、抽出された複数の符号データを複数のＰＥへ分配して入力する分配入力ステップと、
    前記分配入力ステップにより入力された符号データに対応する復号データと、当該符号データの内、有効なデータの長さである符号長とを特定する復号処理を、当該複数のＰＥ毎に並列して実行させる並列復号ステップと、
    前記並列復号ステップにより特定された復号データ及び符号長を用いて、前記符号データ列に対応する復号データ列を生成する生成ステップと、
    を備える符号データ処理プログラム。
14. 前記分配入力ステップは、前記複数のＰＥの個数であるＰＥ数の前記基準位置について前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ均等に分配して入力し、入力した符号データについての前記並列復号ステップにおける復号処理が終了した後に、未抽出の基準位置について前記抽出処理を行うことを特徴とする請求項１３に記載の符号データ処理プログラム。
15. 前記分配入力ステップは、前記符号データ列から１ビットずつ前記ＰＥ数回シフトした符号データ列の各先頭位置を前記基準位置として、当該基準位置から固定長を符号データとして抽出して前記抽出処理を行い、抽出されたＰＥ数の符号データを前記複数のＰＥへ一つずつ分配して入力し、入力した符号データについての前記並列復号ステップにおける復号処理が終了した後に、前記基準位置を前記ＰＥ数のビット分シフトした符号データ列の各先頭位置を前記基準位置として、前記抽出処理を行うことを特徴とする請求項１４に記載の符号データ処理プログラム。
16. 前記コンピュータは、
    前記固定長の符号データに対応する復号データと、当該固定長の符号データの内、有効なデータの長さである符号長とを格納するルックアップテーブルをさらに備え、
    前記並列復号ステップは、入力された符号データに対応する復号データ及び符号長を前記ルックアップテーブルから取得することにより前記復号処理を、前記複数のＰＥ毎に並列して実行させることを特徴とする請求項１３乃至１５のいずれか１項に記載の符号データ処理プログラム。
17. 前記生成ステップは、前記符号データ列の先頭位置を含む第１の符号データに対応する復号データに、当該第１の符号データに対応する符号長分のビットを当該先頭位置からシフトした基準位置における第２の符号データに対応する第２の復号データを連結することにより、前記復号データ列を生成することを特徴とする請求項１３乃至１６のいずれか１項に記載の符号データ処理プログラム。

Images