技術 ２次元逆離散コサイン変換回路

0001

本発明は、２次元逆離散コサイン変換回路に関し、特に画像信号処理等で用いて好適とされる２次元逆離散コサイン変換（Ｉnverse Ｄiscrete ＣonsineＴransform；「ＩＤＣＴ」と略記される）を実現する回路に関する。

0002

近時、マイクロプロセッサやシグナルプロセッサの性能向上により、これらのプロセッサで画像信号処理が実時間で実行可能となるに至っている。

0003

なかでも、乗算器や積和演算器を内蔵したマイクロプロセッサにおいては、積和演算を加減算と同じクロック数で実現できるため、処理の高速化にあたっては乗算の数を減らすだけでなく、加減算と積和演算の数の和を最小化することが望ましい。

0004

マイクロプロセッサやシグナルプロセッサにより２次元（逆）ＤＣＴ（離散コサイン変換；Ｄiscrete Ｃosine Ｔransform）を実現する場合、内部レジスタの本数の制限から、まず行方向の１次元（逆）ＤＣＴを計算して、その計算結果を一旦外部メモリに格納し、次に、行方向処理結果をメモリから列方向に読み出して列方向の１次元（逆）ＤＣＴを実行するという方法が一般的に用いられている。

0005

このとき、演算量やハードウェア量が増大するのを防ぐために、通常、行方向の演算結果は、単精度に打ち切って外部メモリに格納され、このため、演算誤差が生じることになる。このような演算誤差を抑えながら、積和演算と加減算の総数を抑える方法として、例えば文献（「２次元（逆）ＤＣＴ高速化の一検討」、１９９５年電子情報通信学会、基礎・境界ソサイエティ大会予稿集、第１分冊８８頁Ａ−８６）等が参照される。

0006

図３０に、上記文献で提案されている２次元ＩＤＣＴ（Ｉnverse ＤiscreteＣosine Ｔransform）回路のブロック図を示す。

0007

テンソル積演算器１０から１８は、それぞれ図に示すアドレスを持つデータを入力とし、各テンソル積演算を行なう。すなわち、図３０を参照して、添字（インデックス）ｉ、ｊを０から７までの整数として、ｉを垂直方向のアドレス、ｊを水平方向のアドレスとする８点×８点２次元離散コサイン変換（ＤＣＴ）の変換係数を（ｉｊ）で表わすと、第１のテンソル積演算器１０は、（００）、（０４）、（４０）、及び（４４）を入力とし、第２のテンソル積演算器１１は、（０２）、（０６）、（４２）、及び（４６）を入力とし、第３のテンソル積演算器１２は、（２０）、（２４）、（６０）、及び（６４）を入力とし、第４のテンソル積演算器１３は、（２２）、（２６）、（６２）、及び（６６）を入力とし、第５のテンソル積演算器１４は（０１）、（０３）、（０５）、（０７）、（４１）、（４３）、（４５）、及び（４７）を入力とし、第６のテンソル積演算器１５は、（２１）、（２３）、（２５）、（２７）、（６１）、（６３）、（６５）、及び（６７）を入力とし、第７のテンソル積演算器１６は、（１０）、（１４）、（３０）、（３４）、（５０）、（５４）、（７０）、及び（７４）を入力とし、第８のテンソル積演算器１７は、（１２）、（１６）、（３２）、（３６）、（５２）、（５６）、（７２）、及び（７６）を入力とし、第９のテンソル積演算器１８は、（１１）、（１３）、（１５）、（１７）、（３１）、（３３）、（３５）、（３７）、（５１）、（５３）、（５５）、（５７）、（７１）、（７３）、（７５）、及び（７７）を入力とする。

0008

第１の２次元バタフライ演算器１９は、第１から第４のテンソル積演算器１０〜１３の出力を入力として、４点×４点２次元バタフライ演算を行ない、第１の１次元バタフライ演算器２０は、第５及び第６のテンソル積演算器１４、１５の演算結果を入力として１６点１次元バタフライ演算を行ない、第２の１次元バタフライ演算器２１は、第７及び第８のテンソル積演算器１６、１７の演算結果を入力として１６点１次元バタフライ演算を行なう。

0009

第２の２次元バタフライ演算器２２は、第１の２次元バタフライ演算器１９と、第１及び第２の１次元バタフライ演算器２０、２１と、第９のテンソル積演算器１８の演算結果を入力として、８点×８点の２次元バタフライ演算を行なう。

0010

図３０を参照して、第１から第９のテンソル積演算１０〜１８において、その入力が全て零であれば、出力も全て零になる。しかしながら、上記従来方式では、入力データの零／非零に関係なく全てのテンソル積演算が行なわれる構成とされ、零データの場合にも非零データの場合と同等の演算量を要している。

0011

したがって、本発明は、上記事情に鑑みてなされたものであって、その目的は、各テンソル積演算器において、入力データに零が含まれている場合には演算を省略することで演算量を削減し、より一層の高速演算を可能とした２次元逆離散コサイン変換回路を提供することにある。

0012

前記目的を達成するため、本発明の２次元逆離散コサイン変換回路は、ｉ、ｊを０から７までの整数として、ｉを垂直方向のアドレス、ｊを水平方向のアドレスとする８点×８点２次元離散コサイン変換（ＤＣＴ）の変換係数を（ｉｊ）で表わしたとき、（００）、（０４）、（４０）、及び（４４）を入力とする第１のテンソル積演算器と、（０２）、（０６）、（４２）、及び（４６）を入力とする第２のテンソル積演算器と、（２０）、（２４）、（６０）、及び（６４）を入力とする第３のテンソル積演算器と、（２２）、（２６）、（６２）、及び（６６）を入力とする第４のテンソル積演算器と、（０１）、（０３）、（０５）、（０７）、（４１）、（４３）、（４５）、及び（４７）を入力とする第５のテンソル積演算器と、（２１）、（２３）、（２５）、（２７）、（６１）、（６３）、（６５）、及び（６７）を入力とする第６のテンソル積演算器と、（１０）、（１４）、（３０）、（３４）、（５０）、（５４）、（７０）、及び（７４）を入力とする第７のテンソル積演算器と、（１２）、（１６）、（３２）、（３６）、（５２）、（５６）、（７２）、及び（７６）を入力とする第８のテンソル積演算器と、（１１）、（１３）、（１５）、（１７）、（３１）、（３３）、（３５）、（３７）、（５１）、（５３）、（５５）、（５７）、（７１）、（７３）、（７５）、及び（７７）を入力とする第９のテンソル積演算器と、前記第１から第４までのテンソル積演算器の演算結果を入力とする第１の２次元バタフライ演算器と、前記第５及び第６のテンソル積演算器の演算結果を入力とする第１の１次元バタフライ演算器と、前記第７及び第８のテンソル積演算器の演算結果を入力とする第２の１次元バタフライ演算器と、前記第１の２次元バタフライ演算器の演算結果と、前記第１及び第２の１次元バタフライ演算器の演算結果と、前記第９のテンソル積演算器の演算結果とを入力とする第２の２次元バタフライ演算器と、を備えてなる８点×８点２次元逆離散コサイン変換回路において、前記第１から第９までのテンソル積演算器の入力データをそれぞれの入力とする第１から第９の判定器を備え、前記第１から第９の判定器は、それぞれの入力データに非零データがあるか否かを調べ、その判定結果を対応するテンソル積演算器に通知し、前記第１から第９のテンソル積演算器は、それぞれの判定器において入力データが全て零であると判定された場合に、テンソル積演算を行なわない、ことを特徴とする。

0013

請求項２記載の発明に係る２次元逆離散コサイン変換回路は、前記した第１から第９のテンソル積演算器と、第１と第２の１次元バタフライ演算器と、第１と第２の２次元バタフライ演算器から構成される２次元逆離散コサイン変換回路において、前記第１から第９のテンソル積演算器の入力データのうち予め定めた一部のデータだけを入力データとしてテンソル積演算を行なう第１から第９の部分テンソル積演算器と、前記第１から第９のテンソル積演算器の入力データをそれぞれの入力とする第１から第９の選択器を備え、前記第１から第９の選択器はそれぞれの入力データのうち前記第１から第９の部分テンソル積演算器の入力データ以外に非零データがあるかどうかを判定して、対応するテンソル積演算器と部分テンソル積演算器に通知し、部分テンソル積演算器の入力データ以外に非零データがある場合にはテンソル積演算器でテンソル積演算を行ない、部分テンソル積演算器の入力データ以外のデータが全て零である場合には部分テンソル積演算器で部分テンソル積演算を行ない、部分テンソル積演算器の出力をテンソル積演算器の出力とすることを特徴とする。

0014

請求項３記載の発明に係る２次元逆離散コサイン変換回路は、前記した第１から第９のテンソル積演算器と、第１と第２の１次元バタフライ演算器と、第１と第２の２次元バタフライ演算器から構成される２次元逆離散コサイン変換回路において、前記第２から第９のテンソル積演算器に対応する第１から第８の判定器を備え、前記第１から第８の判定器ではエンド・オブ・ブロック（ＥＯＢ）符号の位置情報を入力とし、（００）からＥＯＢ符号までのＤＣＴ係数を全て非零データとみなして、対応するテンソル積演算器の入力データに非零データがあるかどうかを調べて当該テンソル積演算器に通知し、当該テンソル積演算器では入力データが全て零であると判定された場合にはテンソル積演算を行なわないことを特徴とする。

0015

請求項４記載の発明に係る２次元逆離散コサイン変換回路は、上記した請求項２記載の第１から第９のテンソル積演算器と、第１から第９の部分テンソル積演算器と、第１と第２の１次元バタフライ演算器と、第１と第２の２次元バタフライ演算器から構成される２次元逆離散コサイン変換回路において、第１から第９のテンソル積演算器に対応して第１から第９の選択器を備え、前記第１から第９の選択器では入力のＤＣＴ係数におけるエンド・オブ・ブロック（ＥＯＢ）符号の位置情報を入力とし、（００）からＥＯＢ符号までのＤＣＴ係数を全て非零データとみなして、対応するテンソル積演算器の入力データのうち部分テンソル積演算器の入力データ以外に非零データがあるかどうかを調べて、当該テンソル積演算器と部分テンソル積演算器に通知し、非零データがある場合はテンソル積演算器でテンソル積演算を行ない、非零データが無い場合には部分テンソル積演算器で部分テンソル積演算を行ない、部分テンソル積演算器の出力をテンソル積演算器の出力とすることを特徴とする。

0016

本発明の実施の形態について以下に説明する。本発明は、その好ましい実施の形態において、図１を参照すると、第１から第９のテンソル積演算器１０〜１８のそれぞれに対して、第１から第９のテンソル積演算器１０〜１８の入力データをそれぞれの入力とする第１から第９の判定器１〜９を備え、この第１から第９の判定器は、それぞれの入力データに非零データがあるか否かを調べ、その判定結果を対応するテンソル積演算器１０〜１８に通知し、第１から第９のテンソル積演算器１０〜１１は、それぞれ第１から第９の判定器において入力データが全て零であると判定された場合に、テンソル積演算を行なわない。

0017

このように、本発明の実施の形態においては、入力が全て零であるテンソル積演算は行なわないため、判定部の演算が新たに必要となるが、テンソル積演算は削減できる。画像信号の符号化に、この発明を用いる場合には平均的にみて演算量を削減できる。

0018

本発明は、好ましい第２の実施の形態において、図２を参照すると、第１から第９のテンソル積演算器１０〜１８の入力データのうち予め定めた一部のデータだけを入力データとしてテンソル積演算を行なう第１から第９の部分テンソル積演算器３２〜４０と、第１から第９のテンソル積演算器１０〜１８の入力データをそれぞれの入力とする第１から第９の選択器２３〜３１と、を備え、第１から第９の選択器は、それぞれの入力データのうち、第１から第９の部分テンソル積演算器の入力データ以外に非零データがあるか否かを判定し、判定結果を対応するテンソル積演算器と部分テンソル積演算器に通知し、部分テンソル積演算器３２〜４０の入力データ以外に非零データがある場合には、テンソル積演算器１０〜１８でテンソル積演算を行ない、部分テンソル積演算器３２〜４０の入力データ以外のデータが全て零である場合には部分テンソル積演算器で部分テンソル積演算を行ない、部分テンソル積演算器の出力をテンソル積演算結果として出力する。

0019

本発明の第２の実施の形態においては、入力データの零／非零の状態に応じてテンソル積演算を行なうか部分テンソル積演算を行なうかを切替選択するものであり、入力データに非零データがあっても部分テンソル積演算でよい場合が生じるので、上記第１の実施の形態よりも、演算量を削減できる。

0020

次に本発明は、好ましい第３の実施の形態において、図３を参照すると、第２から第９のテンソル積演算器１１〜１８に対応する第１から第８の判定器４１〜４８を備え、第１から第８の判定器４１〜４８では、エンド・オブ・ブロック（ＥＯＢ）符号の位置情報を入力とし、係数（００）からＥＯＢ符号までのＤＣＴ係数を全て非零データとみなして、対応するテンソル積演算器の入力データに非零データがあるか否かを調べて当該テンソル積演算器に通知し、テンソル積演算器では入力データが全て零であると判定された場合にはテンソル積演算を行なわない。

0021

本発明の第３の実施の形態においては、（００）からＥＯＢ符号までの入力データを全て非零データとみなすことで、テンソル積演算を行なうかどうかを判定する。このため、テンソル積演算の全ての入力データに対して零／非零の判定をする必要が無くなり、判定部でかかる演算量を削減することができる。

0022

次に本発明は、好ましい第４の実施の形態において、図４を参照すると、第１から第９のテンソル積演算器１０〜１８に対応して、第１から第８の選択器４９〜５６を備え、第１から第８の選択器は、入力のＤＣＴ係数におけるエンド・オブ・ブロック（ＥＯＢ）符号の位置情報を入力とし、係数（００）からＥＯＢ符号までのＤＣＴ係数を全て非零データとみなして、対応するテンソル積演算器１０〜１８の入力データのうち部分テンソル積演算器３２〜４０の入力データ以外に非零データがあるか否かを調べて当該テンソル積演算器と部分テンソル積演算器に通知し、非零データがある場合にはテンソル積演算器でテンソル積演算を行ない、非零データが無い場合には部分テンソル積演算器で部分テンソル積演算を行ない部分テンソル積演算器の出力をテンソル積演算器の出力とする。

0023

本発明の第４の実施の形態においては、（００）からＥＯＢ符号までの入力データを全て非零データとみなすことで、テンソル積演算を行なうか部分テンソル積演算を行なうかを選択する。このため、部分テンソル積演算の入力データ以外のテンソル積演算の入力データに対して零／非零の判定をする必要が無くなり、選択部でかかる演算量を削減することができる。

0024

上記した本発明の実施の形態について更に詳細に説明すべく、本発明の実施例について図面を参照して以下に説明する。

0025

［実施例１］図１は、本発明の第１の実施例の構成を示す図である。以下本発明の実施例においては、８×８の２次元ＩＤＣＴ回路において、添字ｉ、ｊそれぞれを０から７までの整数として、ｉを垂直方向のアドレス、ｊを水平方向のアドレスとするとき、入力のＤＣＴ係数を（ｉｊ）で表すものとする。

0026

図１を参照すると、本発明の第１の実施例においては、第１から第９のテンソル積演算器１０〜１８に対して、その入力データを入力とし、零／非零を判定する第１から第９の判定器１〜９が備えられている。

0027

第１の判定器１は、入力データ（００）、（０４）、（４０）、及び（４４）が零か否かを調べ、その結果、一つでも非零データが存在していれば第１のテンソル積演算器１０にてテンソル積演算を行ない、一方、全て零であれば第１のテンソル積演算器１０にてテンソル積演算を行なわないように判定制御する。

0028

第２の判定器２は、入力データ（０２）、（０６）、（４２）、及び（４６）が零か否かを調べ、その結果、一つでも非零データが存在していれば第２のテンソル積演算器１１でテンソル積演算を行ない、一方、全て零であれば第２のテンソル積演算器１１にてテンソル積演算を行なわないように判定制御する。

0029

第３の判定器３は、入力データ（２０）、（２４）、（６０）、及び（６４）が零か否かを調べ、その結果、一つでも非零データが存在していれば第３のテンソル積演算器１２でテンソル積演算を行ない、一方、全て零であれば第３のテンソル積演算器１２にてテンソル積演算は行なわないように判定制御する。

0030

第４の判定器４は、入力データ（２２）、（２６）、（６２）、及び（６６）が零か否かを調べ、その結果、一つでも非零データが存在していれば第４のテンソル積演算器１３でテンソル積演算を行ない、一方、全て零であれば第４のテンソル積演算器１３にてテンソル積演算を行なわないように判定制御する。

0031

第５の判定器５は、入力データ（０１）、（０３）、（０５）、（０７）、（４１）、（４３）、（４５）、及び（４７）が零か否かを調べ、その結果、一つでも非零データが存在していれば第５のテンソル積演算器１４でテンソル積演算を行ない、一方、全て零であれば第５のテンソル積演算器１４にてテンソル積演算を行なわないように制御する。

0032

第６の判定器６は、入力データ（２１）、（２３）、（２５）、（２７）、（６１）、（６３）、（６５）、及び（６７）が零か否かを調べ、その結果、一つでも非零データが存在していれば第６のテンソル積演算器１５でテンソル積演算を行ない、一方、全て零であれば第６のテンソル積演算器１５にてテンソル積演算を行なわないように制御する。

0033

第７の判定器７は、入力データ（１０）、（１４）、（３０）、（３４）、（５０）、（５４）、（７０）、及び（７４）が零か否かを調べ、その結果、一つでも非零データが存在していれば第７のテンソル積演算器１６でテンソル積演算を行ない、一方、全て零であれば第７のテンソル積演算器１６にてテンソル積演算を行なわないように制御する。

0034

第８の判定器８は、入力データ（１２）、（１６）、（３２）、（３６）、（５２）、（５６）、（７２）、及び（７６）が零か否かを調べ、その結果、一つでも非零データが存在していれば第８のテンソル積演算器１７でテンソル積演算を行ない、一方、全て零であれば第８のテンソル積演算器１７にてテンソル積演算は行なわないように制御する。

0035

第９の判定器９は、入力データ（１１）、（１３）、（１５）、（１７）、（３１）、（３３）、（３５）、（３７）、（５１）、（５３）、（５５）、（５７）、（７１）、（７３）、（７５）、及び（７７）が零か否かを調べ、その結果、一つでも非零データが存在していれば第９のテンソル積演算器１８でテンソル積演算を行ない、一方、全て零であれば第９のテンソル積演算器１８にてテンソル積演算を行なわないように制御する。

0036

第１〜第９のテンソル積演算器１０〜１８は、対応する第１〜第９の判定器１〜９の判定結果信号を受けて、それぞれの判定器にて、テンソル演算を行なうと判定された場合にのみ、テンソル積演算を行なう。

0037

ここで、Ｃuvを、

0038

0039

とすると、第１のテンソル積演算器１０は、ＤＣＴ係数（００）、（０４）、（４０）、及び（４４）を入力として、次式（１）の４×４行列との行列ベクトル演算を行う。

0040

0041

第２のテンソル積演算器１１は、ＤＣＴ係数（０２）、（０６）、（４２）、及び（４６）を入力として、次式（２）の４×４行列との行列ベクトル演算を行う。

0042

0043

第３のテンソル積演算器１２は、ＤＣＴ係数（２０）、（２４）、（６０）、及び（６４）を入力として、次式（３）の４×４行列との行列ベクトル演算を行う。

0044

0045

第４のテンソル積演算器１３は、ＤＣＴ係数（２２）、（２６）、（６２）、及び（６６）を入力として、次式（４）の４×４行列との行列ベクトル演算を行う。

0046

0047

第５のテンソル積演算器１４は、ＤＣＴ係数（０１）、（０３）、（０５）、（０７）、（４１）、（４３）、（４５）、及び（４７）を入力として、次式（５）の８×８行列との行列ベクトル演算を行う。

0048

0049

第６のテンソル積演算器１５は、ＤＣＴ係数（２１）、（２３）、（２５）、（２７）、（６１）、（６３）、（６５）、及び（６７）を入力として、次式（６）の８×８行列との行列ベクトル演算を行う。

0050

0051

第７のテンソル積演算器１６は、ＤＣＴ係数（１０）、（１４）、（３０）、（３４）、（５０）、（５４）、（７０）、及び（７４）を入力として、次式（７）の８×８行列との行列ベクトル演算を行う。

0052

0053

第８のテンソル積演算器１７は、ＤＣＴ係数（１２）、（１６）、（３２）、（３６）、（５２）、（５６）、（７２）、及び（７６）を入力として、次式（８）の８×８行列との行列ベクトル演算を行う。

0054

0055

第９のテンソル積演算器１８は、ＤＣＴ係数（１１）、（１３）、（１５）、（１７）、（３１）、（３３）、（３５）、（３７）、（５１）、（５３）、（５５）、（５７）、（７１）、（７３）、（７５）、及び（７７）を入力として、次式（９）の１６×１６行列との行列ベクトル演算を行う。

0056

0057

各々の係数Ｃuvは、次式（１０）の三角関数の公式を用いて展開できる。

0058

0059

一例として、図５から図１３に、文献（Ichiro Kuroda，“Processor Architecture Driven Algorithm Optimazation for Fast 2D-DCT”，VLSISignal Processing VIII，pp. 481-490，1995）に記載されている、第１のテンソル積演算器１０から第９のテンソル積演算器１８における、展開例を示す。図中、ｒｎが添字として付されているブランチ（枝）では、その乗算係数を次式（１１）として、乗算を行う。

0060

0061

図５から図１３において、各テンソル積演算器の演算結果は、（ｉｊ）′で表している。

0062

１次元バタフライ演算器（図１の２０、２１）は、第１の入力と第２の入力を加算した結果を第１の出力とし、第１の入力から第２の入力を減算した結果を第２の出力とする１次元バタフライ演算を行なう。

0063

また、２次元バタフライ演算器（図１の１９、２２）は、第１の１次元バタフライ演算器と、第２の１次元バタフライ演算器と、この第１の演算器（１次元バタフライ演算器）の第１の出力を第１の入力とし、第２の演算器の第１の出力を第２の入力とする第３の１次元バタフライ演算器と、第１の演算器の第２の出力を第１の入力とし、第２の演算器の第２の出力を第２の入力とする第４の１次元バタフライ演算器と、からなり、第３の演算器の第１の出力を第１の出力とし、第４の演算器の第１の出力を第２の出力とし、第３の演算器の第２の出力を第３の出力とし、第４の演算器の第２の出力を第４の出力とする２次元バタフライ演算を行なう。

0064

図１を参照して、第１の２次元バタフライ演算器１９は、第１のテンソル積演算器１０から第４のテンソル積演算器１３の演算結果（図５〜図８参照）、（００）′、（０２）′、（２０）′、（２２）′、（０４）′、（０６）′、（２４）′、（２６）′、（４０）′、（４２）′、（６０）′、（６２）′、（４４）′、（４６）′、（６４）′、及び（６６）′を入力として、図１４に示すような４点×４点２次元バタフライ演算を行なう。

0065

図１を参照して、第１の１次元バタフライ演算器２０は、第５、及び第６のテンソル積演算器１４と１５の演算結果（図９、図１０参照）、（０１）′、（２１）′、（０３）′、（２３）′、（０５）′、（２５）′、（０７）′、（２７）′、（４１）′、（６１）′、（４３）′、（６３）′、（４５）′、（６５）′、（４７）′、及び（６７）′を入力として、図１５に示すような１６点１次元バタフライ演算を行なう。

0066

また第２の１次元バタフライ演算器２１は、第７、及び第８のテンソル積演算器１６、１７の演算結果（図１１、図１２参照）、（１０）′、（１２）′、（３０）′、（３２）′、（５０）′、（５２）′、（７０）′、（７２）′、（１４）′、（１６）′、（３４）′、（３６）′、（５４）′、（５６）′、（７４）′、及び（７６）′を入力として、図１６に示すような１６点１次元バタフライ演算を行なう。

0067

第１の２次元バタフライ演算器１９と、第１及び第２の１次元バタフライ演算器２０、２１の演算結果を（ｉｊ）″とすると（図１４、図１５、図１６参照）、第２の２次元バタフライ演算器２２は、２次元バタフライ演算器１９と、第１及び第２の１次元バタフライ演算器２０、２１と、第９のテンソル積演算器１８との演算結果、（００）″、（０１）″、（１０）″、（１１）″、（０４）″、（０３）″、（１４）″、（１３）″、（０６）″、（０５）″、（１６）″、（１５）″、（０２）″、（０７）″、（１３）″、（１７）″、（４０）″、（４１）″、（３０）″、（３１）″、（４４）″、（４３）″、（３４）″、（３３）″、（４６）″、（４５）″、（３６）″、（３５）″、（４２）″、（４７）″、（３２）″、（３７）″、（６０）″、（６１）″、（５０）″、（５１）″、（６４）″、（６３）″、（５４）″、（５３）″、（６６）″、（６５）″、（５６）″、（５５）″、（６２）″、（６７）″、（５２）″、（５７）″、（２０）″、（２１）″、（７０）″、（７１）″、（２４）″、（２３）″、（７４）″、（７３）″、（２６）″、（２５）″、（７６）″、（７５）″、（２２）″、（２７）″、（７２）″、及び（７７）″を入力として、図１７に示すような８点×８点２次元バタフライ演算を行なう。図１７の（ｉｊ）″′で示す演算結果は、８点×８点２次元逆離散コサイン変換回路の出力となる。

0068

第１のテンソル積演算器１０から第９のテンソル積演算器１８において、その演算結果は、第１の判定器１から第９の判定器９によって、テンソル積演算を行なわないと判定されたときには全て零とされる。

0069

［実施例２］図２は、本発明の第２の実施例に係る２次元逆離散コサイン変換（ＩＤＣＴ）回路の回路構成を示す図である。図２を参照すると、本実施例においては、各々のテンソル積演算器１０〜１８に対して部分テンソル積演算器３２〜４０が備えられており、さらに各テンソル積演算出力の入力に対して第１から第９の選択器２３〜３１が備えられている。

0070

図２を参照すると、本実施例において、第１の選択器２３は、入力データ（ＤＣＴ係数）（００）、（０４）、（４０）、及び（４４）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば、第１のテンソル積演算器１０を選択し、予め定めたデータ以外全て零であれば第１の部分テンソル積演算器３２を選択する。

0071

第２の選択器２４は、入力データ（０２）、（０６）、（４２）、及び（４６）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第２のテンソル積演算器１１を選択し、予め定めたデータ以外全て零であれば第２の部分テンソル積演算器３３を選択する。

0072

第３の選択器２５は、入力データ（２０）、（２４）、（６０）、及び（６４）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第３のテンソル積演算器１２を選択し、予め定めたデータ以外全て零であれば第３の部分テンソル積演算器３４を選択する。

0073

第４の選択器２６は、入力データ（２２）、（２６）、（６２）、及び（６６）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第４のテンソル積演算器１３を選択し、予め定めたデータ以外全て零であれば第４の部分テンソル積演算器３５を選択する。

0074

第５の選択器２７は、入力データ（０１）、（０３）、（０５）、（０７）、（４１）、（４３）、（４５）、及び（４７）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第５のテンソル積演算器１４を選択し、予め定めたデータ以外全て零であれば第５の部分テンソル積演算器３６を選択する。

0075

第６の選択器２８は、入力データ（２１）、（２３）、（２５）、（２７）、（６１）、（６３）、（６５）、及び（６７）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第６のテンソル積演算器１５を選択し、予め定めたデータ以外全て零であれば第６の部分テンソル積演算器３７を選択する。

0076

第７の選択器２９は、入力データ（１０）、（１４）、（３０）、（３４）、（５０）、（５４）、（７０）、及び（７４）が零か否かを調べ、その結果、予め選択したデータ以外に一つでも非零データが存在していれば第７のテンソル積演算器１６を選択し、予め定めたデータ以外全て零であれば第７の部分テンソル積演算器３８を選択する。

0077

第８の選択器３０は、入力データ（１２）、（１６）、（３２）、（３６）、（５２）、（５６）、（７２）、及び（７６）が零か否かを調べ、その結果、予め選択したデータ以外に一つでも非零データが存在していれば第８のテンソル積演算器１７を選択し、予め定めたデータ以外全て零であれば第８の部分テンソル積演算器３９を選択する。

0078

第９の選択器３１は、入力データ（１１）、（１３）、（１５）、（１７）、（３１）、（３３）、（３５）、（３７）、（５１）、（５３）、（５５）、（５７）、（７１）、（７３）、（７５）、及び（７７）が零か否かを調べ、その結果、予め定めたデータ以外に一つでも非零データが存在していれば第９のテンソル積演算器１８を選択し、予め定めたデータ以外全て零であれば第９の部分テンソル積演算器４０を選択する。

0079

部分テンソル積演算とは、テンソル積演算の入力データの一部だけを有効な入力とするテンソル積演算である。例えば、係数（００）、（０２）、（２０）、（２２）、（０１）、（０３）、（２１）、（１０）、（３０）、（１２）、（１１）だけを有効な入力とする。

0080

このとき、第１の部分テンソル積演算器３２は、ＤＣＴ係数（００）を入力として、図１８に示すような演算を行ない、演算結果（００）′、（０４）′、（４０）′、（４４）′をテンソル積演算結果として出力する。この場合、（００）′＝（０４）′＝（４０）′＝（４４）′＝ｒ０×（００）＝（１／８（００））とされる。

0081

第２の部分テンソル積演算器３３は、ＤＣＴ係数（０２）を入力として、図１９に示すような演算を行なう。この場合、演算出力は、（０２）′＝（４２）′＝ｒ２×（０２）、（０６）′＝（４６）′＝ｒ６×（０２）とされる。

0082

第３の部分テンソル積演算器３４は、ＤＣＴ係数（２０）を入力として、図２０に示すような演算を行なう。この場合、演算出力は、（２０）′＝（２４）′＝ｒ２×（２０）、（６０）′＝（６４）′＝ｒ６×（２０）とされる。

0083

第４の部分テンソル積演算器３５は、ＤＣＴ係数（２２）を入力として、図２１に示すような演算を行なう。この場合、演算出力は、（２２）′＝（ｒ０＋ｒ４）×（２２）、（６６）′＝（ｒ０−ｒ４）×（２２）、（６２）′＝ｒ４×（２２）、（２６）′＝（−ｒ４）×（２２）とされる。

0084

第５の部分テンソル積演算器３６は、係数（０１）、（０３）を入力として、図２２に示すような演算を行なう。各ブランチ（枝）に付加されたｒｎの演算は図１８から図２１の記法に従う。

0085

第６の部分テンソル積演算器３７は、係数（２１）を入力として、図２３に示すような演算を行なう。

0086

第７の部分テンソル積演算器３８は、係数（１０）、（３０）を入力として、図２４に示すような演算を行なう。

0087

第８の部分テンソル積演算器３９は、係数（１２）を入力として、図２５に示すような演算を行なう。

0088

第９の部分テンソル積演算器４０は、係数（１１）を入力として、図２６に示すような演算を行なう。

0089

本実施例において、第１の部分テンソル積演算器３２から第９の部分テンソル積演算器４０の有効な入力データとしては、上記の係数以外にも考えられる。しかしながら、有効な入力データを増やすと、部分テンソル積演算を選択する確率は増えるが、部分テンソル積演算を行なうことで削減できる演算量は減少する。

0090

第１の２次元バタフライ演算器１９は、第１から第４のテンソル積演算器１０〜１３か、第１から第４の部分テンソル積演算器３２〜３５の演算結果を入力として、図１４に示すような４点×４点２次元バタフライ演算を行なう。

0091

第１の１次元バタフライ演算器２０は、第５、第６のテンソル積演算器１４、１５か、第５、第６部分テンソル積演算器３６、３７の演算結果を入力として、図１５に示すような１６点１次元バタフライ演算を行なう。

0092

第２の１次元バタフライ演算器２１は、第７、第８のテンソル積演算器１６、１７か、部分テンソル積演算器３８、３９の演算結果を入力として、図１６に示すような１６点１次元バタフライ演算を行なう。

0093

第２の２次元バタフライ演算器２２は、第１の２次元バタフライ演算器１９の演算結果と、第１及び第２の１次元バタフライ演算器２０、２１の演算結果と、第９のテンソル積演算器１８又は第９の部分テンソル積演算器４０の演算結果、を入力として、図１７に示すような８点×８点２次元バタフライ演算を行なう。

0094

［実施例３］次に、本発明の第３の実施例に係る２次元逆離散コサイン変換（ＩＤＣＴ）回路について説明する。

0095

入力の各ＤＣＴ係数に、図２７に示すような番号を附与する。例えば動画像通信用の映像符号化方式であるＨ．２６１、蓄積用動画符号化方式であるＭＰＥＧ−１、静止画像符号化方式であるＪＰＥＧ等の画像符号化では、ＤＣＴ係数は、図２７のような順番で符号化され、有意なデータの最後にＥＯＢ符号が付けられ、それ以降のデータは省略される。

0096

図２７に示すＤＣＴ係数において、何番のデータの後にＥＯＢ符号があるかという情報を、「ＥＯＢアドレス」と呼ぶ。また、第１のテンソル積演算器１０から第９のテンソル積演算器１８と、入力係数のアドレスは、図２８に示すような関係にあるため、それぞれのテンソル積演算器は、図２９に示す番号を持つデータを入力とすることになる。

0097

上記第１、第２の実施例に係る２次元ＩＤＣＴ回路では、各テンソル積演算器の入力データが零か否かを実際に調べていたが、図２７における０番からＥＯＢアドレスまでのデータが全て非零であるとみなすことで、ＥＯＢアドレスさえ分かれば、実際のデータを調べる必要がなくなる。

0098

図３に、本発明の第３の実施例に係る２次元ＩＤＣＴ回路の構成を示す。図３を参照すると、第１のテンソル積演算器１０は常にテンソル積演算を行なう。

0099

第１の判定器４１は、ＥＯＢアドレスが「５」以上であるか否かを調べ、「５」以上であれば、第２のテンソル積演算器１１でテンソル積演算を行ない、「５」未満であればテンソル積演算を行なわないと判定する。

0100

第２の判定器４２は、ＥＯＢアドレスが「３」以上であるか否かを調べ、「３」以上であれば、第３のテンソル積演算器１２でテンソル積演算を行ない、３未満であればテンソル積演算を行なわないと判定する。

0101

第３の判定器４３は、ＥＯＢアドレスが「１２」以上であるか否かを調べ、１２以上であれば第４のテンソル積演算器１３でテンソル積演算を行ない、１２未満であればテンソル積演算を行なわないと判定する。

0102

第４の判定器４４は、ＥＯＢアドレスが「１」以上であるか否かを調べ、「１」以上であれば第５のテンソル積演算器１４でテンソル積演算を行ない、「１」未満であればテンソル積演算を行なわないと判定する。

0103

第５の判定器４５は、ＥＯＢアドレスが「８」以上であるか否かを調べ、「８」以上であれば第６のテンソル積演算器１５でテンソル積演算を行ない、「８」未満であればテンソル積演算を行なわないと判定する。

0104

第６の判定器４６は、ＥＯＢアドレスが「２」以上であるか否かを調べ、２以上であれば第７のテンソル積演算器１６でテンソル積演算を行ない、「２」未満であればテンソル積演算を行なわないと判定する。

0105

第７の判定器４７は、ＥＯＢアドレスが「７」以上であるか否かを調べ、「７」以上であれば第８のテンソル積演算器１７でテンソル積演算を行ない、「７」未満であればテンソル積演算を行なわないと判定する。

0106

第８の判定器４８は、ＥＯＢアドレスが「４」以上であるか否かを調べ、「４」以上であれば第９のテンソル積演算器１８でテンソル積演算を行ない、「４」未満であればテンソル積演算を行なわないと判定する。

0107

第２から第９のテンソル積演算器１１〜１８は、それぞれ第１から第８の判定器４１〜４８で演算を行なうものと判定された場合にのみ、テンソル積演算を行なう。

0108

第１のテンソル積演算器１０から第９のテンソル積演算器１８と、第１、及び第２の２次元バタフライ演算器１９、２２と、１次元バタフライ演算器２０と２１については、上記した第１の実施例の２次元逆離散コサイン変換回路と同様とされ、その説明は省略する。

0109

［実施例４］次に本発明の第４の実施例について説明する。図４は、本発明の第４の実施例に係る２次元逆離散コサイン変換回路の構成を示す図である。

0110

図４を参照して、本実施例においては、第１から第９のテンソル積演算器１０〜１８のそれぞれに対して、第１から第９の部分テンソル積演算器３２〜４０を備えるとともに、各テンソル積演算器に対してＥＯＢアドレスを入力とする第１から第９の選択器４９〜５７を備えている。

0111

第１の選択器４９から第９の選択器５７の入力として用いるＥＯＢアドレスは、上記第３の実施例で説明した通りのものであるため、その説明は省略する。

0112

図２９に示す、第１から第９のテンソル積演算器１０〜１８の入力データを持つ番号のうち、第１から第９の部分テンソル積演算器３２〜４０が有効な入力とするデータの番号を除いて一番小さい番号をそれぞれ第１から第９の閾値とする。各選択器は、ＥＯＢアドレスが対応する閾値以上であれば該選択器に対応するテンソル積演算器を選択し、閾値未満であれば、テンソル積演算器の代わりに部分テンソル積演算器を選択する。

0113

第１の選択器４９は、ＥＯＢアドレスが第１の閾値以上であれば第１のテンソル積演算器１０を選択し、第１の閾値未満ならば第１の部分テンソル積演算器３２を選択する。

0114

第２の選択器５０は、ＥＯＢアドレスが第２の閾値以上であれば第２のテンソル積演算器１１を選択し、第２の閾値未満であれば第２の部分テンソル積演算器３３を選択する。

0115

第３の選択器５１は、ＥＯＢアドレスが第３の閾値以上であれば第３のテンソル積演算器１２を選択し、第３の閾値未満であれば第３の部分テンソル積演算器３４を選択する。

0116

第４の選択器５２は、ＥＯＢアドレスが第４の閾値以上であれば第４のテンソル積演算器１３を選択し、第４の閾値未満であれば第４の部分テンソル積演算器３５を選択する。

0117

第５の選択器５３は、ＥＯＢアドレスが第５の閾値以上であれば第５のテンソル積演算器１４を選択し、第５の閾値未満であれば第５の部分テンソル積演算器３６を選択する。

0118

第６の選択器５４は、ＥＯＢアドレスが第６の閾値以上であれば第６のテンソル積演算器１５を選択し、第６の閾値未満であれば第６の部分テンソル積演算器３７を選択する。

0119

第７の選択器５５は、ＥＯＢアドレスが第７の閾値以上であれば第７のテンソル積演算器１６を選択し、第７の閾値未満であれば第７の部分テンソル積演算器３８を選択する。

0120

第８の選択器５６は、ＥＯＢアドレスが第８の閾値以上であれば第８のテンソル積演算器１７を選択し、第８の閾値未満であれば第８の部分テンソル積演算器３９を選択する。

0121

第９の選択器５７は、ＥＯＢアドレスが第９の閾値以上であれば第９のテンソル積演算器１８を選択し、第９の閾値未満であれば第９の部分テンソル積演算器４０を選択する。

0122

第１から第９のテンソル積演算器１０〜１８においては、それぞれ第１から第９の選択器４９〜５７にて、テンソル積演算器が選択された場合にのみ、テンソル積演算を行なう。

0123

第１から第９の部分テンソル積演算器３２〜４０では、それぞれ第１から第９の選択器４９〜５７にて、部分テンソル積演算器が選択された場合にのみ部分テンソル積演算を行なう。

0124

図２９において、０、５、３、１２、１、６、８、２、９、７、４の番号で示すデータを、第１の部分テンソル積演算器３２から第９の部分テンソル積演算器４０において有効な入力とすると、上記第１から第９の閾値は、それぞれ１４、２７、２１、４１、１５、１７、１６、１８、１１となる。

0125

第１から第９のテンソル積演算器１０から１８と、部分テンソル積演算器３２から４０と、第１及び第２の２次元バタフライ演算器１９、２２と、１次元バタフライ演算器２０、２１については、上記第２の実施例と同様である。

0126

上記した本発明の各実施例の作用効果について以下に説明する。

0127

上記実施例においては、９つのテンソル積演算のうち、入力が全て零である場合には、テンソル積演算を行なわない、ように構成したことにより、テンソル積演算量を削減することができる。

0128

例えば図５から図１３に示すような演算に展開したテンソル積演算を、加減算、乗算、積和演算をそれぞれ１命令で実行できるプロセッサを用いて実現する場合、第１から第３のテンソル積演算にそれぞれ１６命令、第４のテンソル積演算に１８命令、第５と第７のテンソル積演算にそれぞれ４８命令、第６と第８のテンソル積演算にそれぞれ５６命令、第９のテンソル積演算に１０８命令必要である。

0129

上記第１の実施例においては、入力が全て零であるテンソル積演算を行なわないので、各テンソル積演算で必要な上記命令数の分だけ演算量を削減できる。なお、演算を行なうものであるか否かを判定する判定器で演算が増えるため、実際に削減できる演算量は、（省略するテンソル積演算の演算量）−（判定器で必要な演算量）となる。

0130

上記第２の実施例も、テンソル積演算にかかる演算量を縮減する。すなわち、第２の実施例においては、テンソル積演算のうちある入力データだけが非零データでその他の入力データは零とした部分テンソル積演算器を用意し、完全なテンソル積演算を行なうか、部分テンソル積演算を行なうかを切替制御するように構成したことによる。

0131

例えば図１８から図２６で示すような部分テンソル積演算を用意し、加減算、乗算、積和演算をそれぞれ１命令で実行できるプロセッサを用いて実現するときには、全て部分テンソル積演算を選択したときに必要な命令数は８３命令で、全てテンソル積演算を行なう場合と比べて２９９命令少なくて済む。

0132

また、第１の実施例においては、演算を行なわずに演算量を削減するためには入力データが全て零でなければならないが、第２の実施例では、例えば入力係数（００）、（０２）、（２０）、（２２）、（０１）、（０３）、（２１）、（１０）、（３０）、（１２）、（１１）に非零係数が存在していても、部分テンソル積演算を選択することによって演算量を削減できる。

0133

さらに、上記第３の実施例では、テンソル積演算で必要な演算量を削減できる上に、テンソル積演算を行なうものであるか否かの判定に必要な演算量も削減できる。その理由は、全ての入力データが零であるか否かを調べるのではなく、ＤＣＴ係数のＥＯＢアドレスを利用し、ＥＯＢアドレスまでのデータは全て非零データとみなすからである。

0134

これによって６４個の入力データ全てを調べる必要がなくなり、各判定器で１回ずつの合計８回のＥＯＢアドレスを用いた条件判定で済む。

0135

そして、上記第４の実施例では、上記第２の実施例と比べて、部分テンソル積演算とテンソル積演算のうちどちらを選択するかを決定する選択器の演算量を削減できる。その理由は、部分テンソル積演算の入力データ以外のテンソル積演算の入力データ全てについて零であるか否かを調べるのではなく、ＤＣＴ係数のＥＯＢアドレスを利用し、ＥＯＢアドレスまでのデータは全て非零データとみなすからである。

0136

これによって６４個の入力データ全てを調べる必要がなくなり、各選択器で１回ずつ合計９回のＥＯＢアドレスを用いた条件判定で済む。

0137

以上、本発明を上記各実施例に即して説明したが、本発明は、上記実施例の構成にのみ限定されるものでなく、本発明の原理に準ずる各種形態及び変形を含むことは勿論である。

0138

以上説明したように、本発明によれば下記記載の効果を奏する。

0139

（１）請求項１記載の発明によれば、テンソル積演算に必要な演算量を縮減することができるという効果を奏する。

0140

その理由は、請求項１記載の発明においては、９つのテンソル積演算のうち、入力が全て零である場合には、テンソル積演算を行なわない、ように構成したことによる。

0141

（２）請求項２記載の発明によっても、テンソル積演算にかかる演算量を減らすことができる。

0142

その理由は、テンソル積演算のうちある入力データだけが非零データでその他の入力データは零とした部分テンソル積演算器を用意し、完全なテンソル積演算を行なうか、部分テンソル積演算を行なうかの選択にした、ことによる。

0143

（３）請求項３記載の発明によれば、テンソル積演算で必要な演算量を削減できる上に、テンソル積演算を行なうものであるか否かの判定に必要な演算量も削減することができる。

0144

その理由は、全ての入力データが零であるか否かを調べるのではなく、ＤＣＴ係数のＥＯＢアドレスを利用し、ＥＯＢアドレスまでのデータは全て非零データとみなすからである。これによって例えば６４個の入力データ全てを調べる必要がなくなり、各判定器で１回ずつの合計８回のＥＯＢアドレスを用いた条件判定で済む。

0145

（４）請求項４記載の発明によれば、請求項２記載の発明と比べて、部分テンソル積演算とテンソル積演算のうちどちらを選択するかを決定する選択器の演算量を削減することができる。

0146

その理由は、部分テンソル積演算の入力データ以外のテンソル積演算の入力データ全てについて零であるか否かを調べるのではなく、ＤＣＴ係数のＥＯＢアドレスを利用し、ＥＯＢアドレスまでのデータは全て非零データとみなすからである。これによって６４個の入力データ全てを調べる必要がなくなり、各選択器で１回ずつ合計９回のＥＯＢアドレスを用いた条件判定で済む。

0147

図１本発明における第１の実施例の構成を示すブロック図である。
図２本発明における第２の実施例の構成を示すブロック図である。
図３本発明における第３の実施例の構成を示すブロック図である。
図４本発明における第４の実施例の構成を示すブロック図である。
図５本発明の実施例におけるテンソル積演算器１０で行なう演算を示す図である。
図６本発明の実施例におけるテンソル積演算器１１で行なう演算を示す図である。
図７本発明の実施例におけるテンソル積演算器１２で行なう演算を示す図である。
図８本発明の実施例におけるテンソル積演算器１３で行なう演算を示す図である。
図９本発明の実施例におけるテンソル積演算器１４で行なう演算を示す図である。
図１０本発明の実施例におけるテンソル積演算器１５で行なう演算を示す図である。
図１１本発明の実施例におけるテンソル積演算器１６で行なう演算を示す図である。
図１２本発明の実施例におけるテンソル積演算器１７で行なう演算を示す図である。
図１３本発明の実施例におけるテンソル積演算器１８で行なう演算を示す図である。
図１４本発明の実施例における２次元バタフライ演算器１９で行なう演算を示す図である。
図１５本発明の実施例における１次元バタフライ演算器２０で行なう演算を示す図である。
図１６本発明の実施例における１次元バタフライ演算器２１で行なう演算を示す図である。
図１７本発明の実施例における２次元バタフライ演算器２２で行なう演算を示す図である。
図１８本発明の実施例における部分テンソル積演算器２３で行なう演算を示す図である。
図１９本発明の実施例における部分テンソル積演算器２４で行なう演算を示す図である。
図２０本発明の実施例における部分テンソル積演算器２５で行なう演算を示す図である。
図２１本発明の実施例における部分テンソル積演算器２６で行なう演算を示す図である。
図２２本発明の実施例における部分テンソル積演算器２７で行なう演算を示す図である。
図２３本発明の実施例における部分テンソル積演算器２８で行なう演算を示す図である。
図２４本発明の実施例における部分テンソル積演算器２９で行なう演算を示す図である。
図２５本発明の実施例における部分テンソル積演算器３０で行なう演算を示す図である。
図２６本発明の実施例における部分テンソル積演算器３１で行なう演算を示す図である。
図２７本発明の一実施例を説明するための図であり、入力のＤＣＴ係数の番号を示す図である。
図２８本発明の一実施例を説明するための図であり、各テンソル積演算と入力データの位置関係を示す図である。
図２９本発明の一実施例を説明するための図であり、各テンソル積演算と入力のＤＣＴ係数の番号を示す図である。
図３０従来の２次元逆離散コサイン変換回路を示すブロック図である。

0148

１〜９判定器
１０〜１８テンソル積演算器
１９、２２ ２次元バタフライ演算器
２０、２１ １次元バタフライ演算器
２３〜３１選択器
３２〜４０ 部分テンソル積演算器
４１〜４８ 判定器
４９〜５７ 選択器