(57)【要約】  入力信号（４１６）の離散コサイン変換（ＤＣＴ）を実行するための回路は、直列に結合される、順方向加算器ツリー・モジュール（４０２）、マルチプレクサの第１のセット（４０４）、共用フローグラフ・モジュール（４０６）、逆方向加算器ツリー・モジュール（４０８）、及びマルチプレクサの第２のセット（４１０）を含む。演算において、マルチプレクサ（４０４）は、順方向加算器ツリー・モジュール（４０２）及び共用フローグラフ・モジュール（４０６）を介して入力信号を処理して、入力信号（４１６）の順方向ＤＣＴを実行する、又は、共用フローグラフ・モジュール（４０６）及び逆方向加算器ツリー・モジュール（４０８）を介して入力信号（４１６）の逆ＤＣＴを実行するように構成される。
2013513866.tif 000002
【特許請求の範囲】
【請求項１】
入力信号の離散コサイン変換を実行するための装置であって、
加算器及び乗算器の第１のセットを含む順方向加算器ツリー・モジュールであって、前記順方向加算器ツリー・モジュールの入力ノードが入力信号を受信するように構成される、前記順方向加算器ツリー・モジュール、
マルチプレクサの第１のセットであって、前記マルチプレクサの第１のセットの入力ノードが、前記順方向加算器ツリー・モジュールの出力ノードに接続され、且つ前記入力信号を受信するように構成される、前記マルチプレクサの第１のセット、
加算器及び乗算器の第２のセットを含む共用フローグラフ・モジュールであって、前記共用フローグラフ・モジュールの入力ノードが、前記マルチプレクサの第１のセットの出力ノードに接続される、前記共用フローグラフ・モジュール、
加算器及び乗算器の第３のセットを含む逆方向加算器ツリー・モジュールであって、前記逆方向加算器ツリー・モジュールの入力ノードが前記共用フローグラフ・モジュールの出力ノードに接続される、前記逆方向加算器ツリー・モジュール、及び、
マルチプレクサの第２のセットであって、前記マルチプレクサの第２のセットの入力ノードが、前記共用フローグラフ・モジュールの出力ノード及び前記逆方向加算器ツリー・モジュールの出力ノードに接続される、前記マルチプレクサの第２のセット、
を含む、装置。
【請求項２】
請求項１に記載の装置であって、前記マルチプレクサの第１のセット及び前記マルチプレクサの第２のセットが、前記順方向加算器ツリー・モジュール及び前記共用フローグラフ・モジュールを介して前記入力信号を処理して、前記入力信号の順方向離散コサイン変換を実行するように構成される、装置。
【請求項３】
請求項２に記載の装置であって、前記入力信号の前記順方向離散コサイン変換の間、前記マルチプレクサの第１のセットが、前記順方向加算器ツリー・モジュールの前記出力ノードから各々の信号を選択するように構成され、前記マルチプレクサの第２のセットが、前記共用フローグラフ・モジュールの前記出力ノードから各々の信号を選択するように構成される、装置。
【請求項４】
請求項１に記載の装置であって、前記マルチプレクサの第１のセット及び前記マルチプレクサの第２のセットが、前記共用フローグラフ・モジュール及び前記逆方向加算器ツリー・モジュールを介して前記入力信号を処理して、前記入力信号の逆離散コサイン変換を実行するように構成される、装置。
【請求項５】
請求項４に記載の装置であって、前記入力信号の前記逆離散コサイン変換の間、前記マルチプレクサの第１のセットが前記入力信号を選択するように構成され、前記マルチプレクサの第２のセットが、前記逆加算器モジュールの前記出力ノードから各々の信号を選択するように構成される、装置。
【請求項６】
請求項１に記載の装置であって、前記入力信号が、並列の８個のデジタル入力データを含む、装置。
【請求項７】
請求項６に記載の装置であって、前記加算器及び乗算器の第１のセットが、１２個の加算器及び６個の負の単位元乗算器を含み、前記加算器及び乗算器の第２のセットが、１４個の加算器及び２０個の乗算器を含む、装置。
【請求項８】
請求項７に記載の装置であって、前記加算器及び乗算器の第３のセットが１２個の加算器及び６個の負の単位元乗算器を含む、装置。
【請求項９】
請求項８に記載の装置であって、前記２０個の乗算器が、それらの入力値を一定の係数で乗算するように構成され、前記一定の係数が、−π／１６、π／１６、−π／８、π／８、３π／１６、π／４、−５π／１６、５π／１６、６π／１６、７π／１６、及び−１を含む、装置。
【請求項１０】
請求項１に記載の装置であって、前記マルチプレクサの第１のセットが８個の２：１マルチプレクサを含み、前記マルチプレクサの第２のセットが８個の２：１マルチプレクサを含む、装置。
【請求項１１】
請求項１０に記載の装置であって、前記８個のマルチプレクサの第１のセット及び前記８個のマルチプレクサの第２のセットが、それらの制御信号として「０」を受信すると、それぞれ、前記順方向加算器ツリー・モジュールの前記出力ノードから各々の信号を、及び前記共用フローグラフ・モジュールの前記出力ノードから各々の信号を選択するように構成される、装置。
【請求項１２】
請求項１０に記載の装置であって、前記８個のマルチプレクサの第２のセットが、前記８個のデジタル入力データの順方向離散コサイン変換を表す、８個のデジタル出力データを並列に生成するように構成される、装置。
【請求項１３】
請求項１２に記載の装置であって、前記８個のマルチプレクサの第１のセット及び前記８個のマルチプレクサの第２のセットが、それらの制御信号として「１」を受信すると、それぞれ、前記８個のデジタル入力データを、及び前記逆加算器モジュールの前記出力ノードから各々の信号を選択するように構成される、装置。
【請求項１４】
請求項１３に記載の装置、前記８個のマルチプレクサの第２のセットが、前記８個のデジタル入力データの逆離散コサイン変換を表す、８個のデジタル出力データを並列に生成するように構成される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、エレクトロニクスの分野に関連し、更に特定して言えば、離散コサイン変換（ＤＣＴ）装置及び回路に関連する。
【背景技術】
【０００２】
離散コサイン変換（ＤＣＴ）は、波形データを、重み付けされたコサインの和として表すための手法である。ＤＣＴは、ＪＰＥＧ（Joint Photographic Experts Group）のような、音声又は画像のデータ圧縮に一般に用いられている。ＤＣＴのこの用途は、損失のある圧縮をもたらす。ＤＣＴ自体がデータを失うのではなく、より正確に言えば、ＤＣＴに依存するデータ圧縮技術は、データ量を減らすためにＤＣＴの幾つかの係数の近似値を求めるのである。時間ドメインのデジタル入力データが周波数ドメインのデジタル出力データに変換される場合のＤＣＴは、順方向離散コサイン変換（ＦＤＣＴ）と呼ばれる。反対に、周波数ドメインのデジタル入力データが時間ドメインのデジタル出力データに変換される場合のＤＣＴは、逆離散コサイン変換（ＩＤＣＴ）と呼ばれる。種々の応用例において、デジタル入力データを圧縮する際にＦＤＣＴが用いられ、一方、このデジタル入力データを復元する際にＩＤＣＴが用いられる。
【０００３】
８ポイント（例えば、８個のパラレル・デジタル入力及び出力）ＦＤＣＴは、下記の数式によって表すことができる。
【数１】
2013513866.tif 000003
ここで、F（k）は周波数ドメインのデジタル出力データを表し、c（k）は定数（例えば、k=０の場合、c（k）=１／（２）1/2、k=１から７の場合、c（k）=１）を表し、ｆ（ｊ）は時間ドメインのデジタル入力データを表し、ｋは０から７の範囲の整数を表す。更に、下記は、このＦＤＣＴ計算式の行列乗算を表す。
【数２】
2013513866.tif 000004
ここで、
【数３】
2013513866.tif 000005
であり、このＦＤＣＴ計算式の係数、即ち、１／４、は１に正規化される。図１は、チェン（Ｃｈｅｎ）、スミス（Ｓｍｉｔｈ）、及びフラリック（Ｆｒａｌｉｃｋ）のアルゴリズムに従った８ポイントＦＤＣＴフローグラフ１００を示し、この８ポイントＦＤＣＴフローグラフ１００はハードウェアを用いて実装され得る。図１において、８ポイントＦＤＣＴフローグラフ１００は、円で表す２６個の加算器１０２〜１５２、及び矩形で表す２８個の乗算器１５４〜１９５を含む。演算において、８ポイントＦＤＣＴフローグラフ１００は、入力信号１９６、即ち、f（０）〜f（７）、を処理することによって、出力信号１９８（例えば、F（０）〜F（７））を生成する。例えば、F（０）は、図１において強調表示した信号経路で示すように、下記の数式：F(0)=C4×((f(0)+f(7))+(f(3)+f(4)))+C4×((f(1)+f(6))+(f(2)+f(5)))=C4×(f(0)+f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7))を用いて求めることができる。同様に、F（１）〜F（７）も求めることができる。
【０００４】
８ポイントＩＤＣＴは、下記の数式によって表すことができる。
【数４】
2013513866.tif 000006
ここで、ｆ（ｊ）は時間ドメインのデジタル出力データを表し、ｃ（ｋ）は定数（例えば、ｋ＝０の場合、ｃ（ｋ）＝１／（２）1/2であり、ｋ＝１から７の場合、ｃ（ｋ）＝１）を表し、Ｆ（ｋ）は周波数ドメインのデジタル入力データを表し、ｊは０から７の範囲の整数を表す。更に、下記はこのＩＤＣＴ計算式の行列乗算を表す。
【数５】
2013513866.tif 000007
ここで、
【数６】
2013513866.tif 000008
である。図２は、チェン、スミス、及びフラリックのアルゴリズムに従った８ポイントＩＤＣＴフローグラフ２００を示し、この８ポイントＩＤＣＴフローグラフ２００はハードウェアを用いて実装され得る。図２において、８ポイントＩＤＣＴフローグラフ２００は、２６個の加算器２０２〜２５２及び２６個の乗算器２５４〜２９５を含む。演算において、８ポイントＩＤＣＴフローグラフ２００は、入力信号２９６、即ち、F（０）〜F（７）、を処理することによって、出力信号２９８、即ち、f（０）〜f（７）、を生成する。例えば、f（０）は、図２において強調表示した信号経路で示すように、下記の数式：f(0)=(C4×F(0)+C4×F(4))+(C2×F(2)+C6×F(6))+(C5×F(5)+C3×F(3))+(C1×F(1)+C7×F(7))=C4×F(0)+C1×F(1)+C2×F(2)+C3×F(3)+C4×F(4)+C5×F(5)+C6×F(6)+C7×F(7)を用いて求めることができる。同様に、f（１）〜f（７）も求めることができる。
【０００５】
ＦＤＣＴ及びＩＤＣＴのいずれも、符号化器／復号化器などの応用例において並列に用いることがある。つまり、図１及び図２のものなど２つの個別の回路が、それぞれＦＤＣＴ及びＩＤＣＴ用に実装され得る。この方法は、ＦＤＣＴ又はＩＤＣＴのいずれか用に指定された加算器及びマルチプレクサを用いるため、回路を構築するために一層多くのスペース及び構成要素を必要とする可能性がある。
【０００６】
代替として、図３に図示するように、ＦＤＣＴ及びＩＤＣＴの両方のための回路が単一の回路を用いて構築されてもよい。図３は、チェン、スミス、及びフラリックのアルゴリズムに従った８ポイントＦＤＣＴ／ＩＤＣＴフローグラフ３００を示し、この８ポイントＦＤＣＴ／ＩＤＣＴフローグラフ３００はハードウェアを用いて実装され得る。図３において、８ポイントＦＤＣＴ／ＩＤＣＴフローグラフ３００は、３６個の加算器３０２〜３３７、及び矩形で表す２８個の乗算器３５０〜３７７を含む。演算において、８ポイントＦＤＣＴ／ＩＤＣＴフローグラフ３００は、ＦＤＣＴ演算の間、時間ドメイン信号３９８に基づいて周波数ドメイン信号３９６を生成し、一方、ＩＤＣＴ演算の間、周波数ドメイン信号３９６に基づいて時間ドメイン信号３９８を生成する。図３に示すように、ＦＤＣＴ及びＩＤＣＴを単一の回路に組み合わせることで、回路の寸法だけでなく回路の構成要素の数も低減されるように思われるが、これらの２種類の離散コサイン変換（ＤＣＴ）に関して２つの反対方向に流れる信号を処理するため、その回路にかなりの数のマルチプレクサを付加する必要が生じ得る。つまり、回路３００内の各加算器に１個のマルチプレクサ（例えば、又は少なくとも計２８個のマルチプレクサ）が割り当てられ、ＤＣＴの種類に基づいてそのマルチプレクサに関連する各加算器を選択するまたはその選択を解除する必要があり得る。例えば、ＦＤＣＴのＦ（０）を得るため、信号経路内の加算器のうち、加算器３０６、３１４、３１５、３２２、３２３、３２４及び３２５が含まれる必要があり、一方、加算器３３０〜３３７は、各々のマルチプレクサ（図３には図示せず）を用いて排除される必要がある。別の例では、ＩＤＣＴでf（０）を得るため、信号経路内の加算器のうち、加算器３１２、３１３、３１４、３１７、３２１、３２２及び３３０が含まれる必要があり、一方、加算器３０２〜３０９及び３２９は、各々のマルチプレクサ（図３には図示せず）を用いて排除される必要がある。更に、ＦＤＣＴ又はＩＤＣＴ演算に基づいて回路３００内のマルチプレクサを制御するため、１つ又は複数の論理回路が実装される必要があり得る。このため、回路３００内に実装される必要のあるこれらの付加的なマルチプレクサ及び論理回路が、同一回路にＦＤＣＴ／ＩＤＣＴの両方の特徴を実装することによってもたらされるスケーリング効果を相殺してしまう可能性がある。
【発明の概要】
【０００７】
フローグラフの共用に基づく離散コサイン変換のための装置及び回路が開示される。
【０００８】
１つの側面において、入力信号の離散コサイン変換を実行するための装置が、加算器及び乗算器の第１のセットを有する順方向加算器ツリー・モジュールを含み、この順方向加算器ツリー・モジュールの入力ノードは、入力信号を受信するように構成される。この装置は、入力ノードが前記順方向加算器ツリー・モジュールの出力ノードに接続され、前記入力信号を受信するように構成される、マルチプレクサの第１のセットを更に含む。この装置は、加算器及び乗算器の第２のセットを有する共用フローグラフ・モジュールを更に含み、この共用フローグラフ・モジュールの入力ノードは、前記マルチプレクサの第１のセットの出力ノードに接続される。また、この装置は、加算器及び乗算器の第３のセットを有する逆方向加算器ツリー・モジュールを含み、この逆方向加算器ツリー・モジュールの入力ノードは、前記共用フローグラフ・モジュールの出力ノードに接続される。また、この装置は、入力ノードが前記共用フローグラフ・モジュールの出力ノードに及び前記逆方向加算器ツリー・モジュールの出力ノードに接続される、マルチプレクサの第２のセットを含む。
【０００９】
別の側面において、入力信号の離散コサイン変換を実行するための回路が、１２個の加算器及び６個の乗算器を有する順方向加算器ツリー・モジュールを含み、この順方向加算器ツリー・モジュールの入力ノードは、８個のデジタル入力データを並列に受信するように構成される。この回路は、入力ノードが前記順方向加算器ツリー・モジュールの出力ノードに接続され、前記８個のデジタル入力データを受信するように構成される、８個のマルチプレクサの第１のセットを更に含む。この回路は、１４個の加算器及び２０個の乗算器を有する共用フローグラフ・モジュールを更に含み、この共用フローグラフ・モジュールの入力ノードは、前記８個のマルチプレクサの第１のセットの出力ノードに接続される。また、この回路は、１２個の加算器及び６個の乗算器を有する逆方向加算器ツリー・モジュールを含み、この逆方向加算器ツリー・モジュールの入力ノードは、前記共用フローグラフ・モジュールの出力ノードに接続される。また、この回路は、入力ノードが前記共用フローグラフ・モジュールの出力ノードに及び前記逆方向加算器ツリー・モジュールの出力ノードに接続される、８個のマルチプレクサの第２のセットを含む。
【００１０】
これらの実施例の他の特徴は、添付の図面から、また以下に続く詳細な説明から明らかとなろう。
【図面の簡単な説明】
【００１１】
【図１】図１は、チェン、スミス、及びフラリックのアルゴリズムに従った８ポイントＦＤＣＴフローグラフを示す。
【００１２】
【図２】図２は、チェン、スミス、及びフラリックのアルゴリズムに従った８ポイントＩＤＣＴフローグラフを示す。
【００１３】
【図３】図３は、チェン、スミス、及びフラリックのアルゴリズムに従った８ポイントＦＤＣＴ／ＩＤＣＴフローグラフを示す。
【００１４】
【図４】図４は、一実施例に従った例示のＤＣＴ装置のブロック図を示す。
【００１５】
【図５】図５は、一実施例に従った、例示の共用フローグラフ・モジュール及び例示の逆方向加算器ツリー・モジュールを含む、８ポイントＩＤＣＴフローグラフを示す。
【００１６】
【図６】図６は、図１の８ポイントＦＤＣＴフローグラフの簡略化したバージョンを示す。
【００１７】
【図７】図７は、一実施例に従った、例示の順方向加算器ツリー・モジュール及び図５の共用フローグラフ・モジュールを含む、８ポイントＦＤＣＴフローグラフを示す。
【００１８】
【図８】図８は、一実施例に従った例示のＤＣＴ回路の概略図を示す。
【発明を実施するための形態】
【００１９】
本明細書に記載の図面は、単なる例示のためであって、いかなる方式においても本開示の範囲を制限することを意図しているものではない。
【００２０】
フローグラフの共用に基づく離散コサイン変換のための装置及び回路の例が開示される。下記の詳細な説明は、単なる例示であり、本開示、応用例、又は用途を制限することを意図しているものではない。複数の図面にわたって、対応する参照符号は、同様の又は対応する部分及び特徴を示すことを理解されたい。
【００２１】
図４は、一実施例に従った、例示のＤＣＴ装置４００のブロック図を示す。ＤＣＴ装置４００は、順方向加算器ツリー・モジュール４０２、マルチプレクサ４０４、共用フローグラフ・モジュール４０６、逆方向加算器ツリー・モジュール４０８、及びマルチプレクサ４１０を含む。順方向加算器ツリー・モジュール４０２は、加算器及び乗算器４１２を含み、順方向加算器ツリー・モジュール４０２の入力ノード４１４は、入力信号４１６を受信するように構成される。マルチプレクサ４０４は、順方向加算器ツリー・モジュール４０２の出力ノード４２０に接続される入力ノード４１８を有し、マルチプレクサ４０４の入力ノード４１８も入力信号４１６を受信するように構成される。共用フローグラフ・モジュール４０６は、加算器及び乗算器４２２を含み、共用フローグラフ・モジュール４０６の入力ノード４２４は、マルチプレクサ４０４の第１のセットの出力ノード４２６に接続される。逆方向加算器ツリー・モジュール４０８は、加算器及び乗算器４２８を含み、逆方向加算器ツリー・モジュール４０８の入力ノード４３０は、共用フローグラフ・モジュール４０６の出力ノード４３２に接続される。マルチプレクサ４１０は、共用フローグラフ・モジュール４０６の出力ノード４３２に及び逆方向加算器ツリー・モジュール４０８の出力ノード４３６に接続される入力ノード４３４を有する。
【００２２】
一例の演算において、受信した制御信号４３８に基づいて、マルチプレクサ４０４及びマルチプレクサ４１０は、順方向加算器ツリー・モジュール４０２及び共用フローグラフ・モジュール４０６を介して入力信号４１６を処理して、入力信号４１６のＦＤＣＴ演算を実行するように構成される。つまり、入力信号４１６のＦＤＣＴ演算の間、マルチプレクサ４０４が、順方向加算器ツリー・モジュール４０２の出力ノード４２０から各々の信号を選択するように構成され、マルチプレクサ４１０が、共用フローグラフ・モジュール４０６の出力ノード４３２から各々の信号を選択するように構成される。従って、マルチプレクサ４１０は、その出力ノードを介して、入力信号４１６のＦＤＣＴ演算から出力信号４４０を生成する。
【００２３】
別の演算例では、マルチプレクサ４０４及びマルチプレクサ４１０は、共用フローグラフ・モジュール４０６及び逆方向加算器ツリー・モジュール４０８を介して入力信号４１６を処理して、入力信号４１６のＩＤＣＴ演算を実行するように構成される。つまり、入力信号４１６のＩＤＣＴ演算の間、受信した制御信号４３８に基づいて、マルチプレクサ４０４が入力信号４１６を選択するように構成され、マルチプレクサ４１０が、逆方向加算器ツリー・モジュール４０８の出力ノード４３６から各々の信号を選択するように構成される。従って、マルチプレクサ４１０は、入力信号４１６のＩＤＣＴ演算から出力信号４４０を生成する。
【００２４】
共用フローグラフ・モジュール４０６はＦＤＣＴ及びＩＤＣＴ演算の両方に用いられ、それにより、使用する加算器及び乗算器などの構成要素の数が低減されたＤＣＴ装置４００を構築することが可能となることを理解されたい。ＤＣＴ装置４００の共用フローグラフ・モジュール４０６は、ＦＤＣＴ及びＩＤＣＴ演算の両方に対し単一方向の信号を処理し、一方、図３に示したものなどの従来のＤＣＴ装置は、ＦＤＣＴ及びＩＤＣＴ演算の間逆方向に流れる信号を扱うため、マルチプレクサなどの付加的な電子的構成要素を必要とし得ることも理解されたい。
【００２５】
図５は、一実施例に従った、例示の共用フローグラフ・モジュール５０２及び例示の逆方向加算器ツリー・モジュール５０３を含む８ポイントＩＤＣＴフローグラフ５００を示す。共用フローグラフ・モジュール５０２は、図４の共用フローグラフ・モジュール４０６の一例の実施例であることを理解されたい。逆方向加算器ツリー・モジュール５０３は、逆方向加算器ツリー・モジュール４０８の一例の実施例であることも理解されたい。８ポイントＩＤＣＴフローグラフ５００は、構成要素（例えば、加算器５０６〜５１９及び５５０〜５６１、及び乗算器５２０〜５３９及び５６２〜５６７）を用いて実装される場合、周波数ドメインのデジタル入力データ５０４（例えば、並列の８個のデジタル入力データF（０）〜F（７））のＩＤＣＴ演算を実行して、時間ドメインのデジタル出力データ５０５（例えば、並列の８個のデジタル出力データf（０）〜f（７））を生成する。
【００２６】
図５に図示するように、共用フローグラフ・モジュール５０２は、１４個の加算器（例えば、加算器５０６〜５１９）及び２０個の乗算器（例えば、乗算器５２０〜５３９）を含む。各加算器は、２個の入力を受け単一の出力を生成する。各乗算器は、その入力値を一定の係数で乗算するように構成され、この係数は、−Ｃ１又は−π／１６、Ｃ１又はπ／１６、−Ｃ２又は−π／８、Ｃ２又はπ／８、Ｃ３又は３π／１６、Ｃ４又はπ／４、−Ｃ５又は−５π／１６、Ｃ５又は５π／１６、Ｃ６又は６π／１６、Ｃ７又は７π／１６、及び−１を含む。逆方向加算器ツリー・モジュール５０３は、１２個の加算器（例えば、加算器５５０〜５６１）及び６個の負の単位元（unity）乗算器（例えば、乗算器５６２〜５６７）を含む。各加算器は、２個の入力を受け単一の出力を生成する。各乗算器はその入力値を−１で乗算するように構成される。
【００２７】
また、共用フローグラフ・モジュール５０２から、ノードＢ０〜Ｂ７の信号、即ち、Ｓ（Ｂ０）〜Ｓ（Ｂ７）、を下記のようにノードＡ０〜Ａ７の信号、即ち、Ｓ（Ａ０）〜Ｓ（Ａ７）、に関して求めることができる。
S(B0)=C4×S(A0)+C4×S(A1)，
S(B1)=C4×S(A0)-C4×S(A1) ，
S(B2)=C6×S(A2)-C2×S(A3) ，
S(B3)=C2×S(A2)+C6×S(A3) ，
S(B4)=C7×S(A4)+C3×S(A5)-C5×S(A6)-C1×S(A7) ，
S(B7)=C1×S(A4)+C5×S(A5)+C3×S(A6)+C7×S(A7) ，
cos(x+y)=cosx×cosy-sinx×siny、cos(x-y)=cosx×cosy+sinx×siny、sinx=cos(π/2-x)及びcos(π/4)=sin(π/4)というコサイン及びサインの特性を用い、
S(B5)=C4×[-C5×S(A5)-C3×S(A6)+C1×S(A4)+C7×S(A7)]
-C4×[C7×S(A4)-C1×S(A7)-C3×S(A5)+C5×S(A6)]
=C4×(C1-C7)×S(A4)-C4×(C5-C3)×S(A5)-C4×(C3+C5)×S(A6)
+C4×(C7+C1)×S(A7)
=C5×S(A4)+C7×S(A5)-C1×S(A6)+C3×S(A7)であり、
S(B6)=C4×[C7×S(A4)-C1×S(A7)-(C3×S(A5)-C5×S(A6))]
+C4×[-(C5×S(A5)+C3×S(A6))+C1×S(A4)+C7×S(A7)]
=C4×(C7+C1)×S(A4)-C4×(C3+C5)×S(A5)+C4×(C5-C3)×S(A6)
+C4×(C7-C1)×S(A7)
=C3×S(A4)-C1×S(A5)-C7×S(A6)-C5×S(A7)であり、
ここで、C4×(C1-C7)=C4×C1-C4×C7=cos(4π/16)×cos(π/16)-cos(4π/16)×cos(7π/16)
=cos(4π/16)×cos(π/16)-sin(4π/16)×sin(π/16)=cos(4π/16+π/16)=cos(5π/16)=C5，
-C4×(C5-C3)=C4×C3-C4×C5=cos(4π/16)×cos(3π/16)-cos(4π/16)×cos(5π/16)
=cos(4π/16)×cos(3π/16)-sin(4π/16)×sin(3π/16)=cos(4π/16+3π/16)=cos(7π/16)=C7，
C4×(C3+C5)=C4×C3+C4×C5=cos(4π/16)×cos(3π/16)+cos(4π/16)×cos(5π/16)
=cos(4π/16)×cos(3π/16)+sin(4π/16)×sin(3π/16)=cos(4π/16-3π/16)=cos(π/16)=C1，
及びC4×(C7+C1)=C4×C7+C4×C1=cos(4π/16)×cos(7π/16)+cos(4π/16)×cos(π/16)
=cos(4π/16)×cos(π/16)+sin(4π/16)×sin(π/16)=cos(4π/16-π/16)=cos(3π/16)=C3である。
【００２８】
図６は、図１の８ポイントＦＤＣＴフローグラフ１００の簡略化したバージョンを示す。図１において、出力信号１９８、即ち、F（０）〜F（７）、は下記のようにノードＡ０〜Ａ７の信号、即ち、Ｓ（Ａ０）〜Ｓ（Ａ７）、に関して求めることができる。
F(0)=C4×S(A0)+C4×S(A1)，
F(4)=C4×S(A0)-C4×S(A1)，
F(2)=C6×S(A2)+C2×S(A3)，
F(6)=C6×S(A3)-C2×S(A2)，
cos（x+y）=cosx×cosy-sinx×siny、cos（x-y）=cosx×cosy+sinx×siny、sinx=cos（π/2-x）、及びcos(π/4)=sin(π/4)というコサイン及びサインの特性を用いて、
F(1)=C7×[S(A4)+C4×(S(A6)-S(A5))]+C1×[S(A7)+C4×S(A5)+C4×S(A6)]
=C7×S(A4)+C4×(C1-C7)×S(A5)+C4×(C1+C7)×S(A6)+C1×S(7)
=C7×S(A4)+C5×S(A5)+C3×S(A6)+C1×S(A7)，
F(3)=-C5×[S(A4)+-(C4×S(A6)-C4×S(A5))]+C3×[S(A7)-(C4×S(A5)
+C4×S(A6))]=-C5×S(A4)-C4×(C3+C5)×S(A5)+C4×(C5-C3)×S(A6)
+C3×S(A7)
=-C5×S(A4)-C1×S(A5)-C7×S(A6)+C3×S(A7)
F(5)=C3×[S(A4)-C4×S(A6)+C4×S(A5)]+C5×[S(A7)-C4×(S(A5)+S(A6))]
=C3×S(A4)+C4×(C3-C5)×S(A5)-C4×(C3+C5)×S(A6)+C5×S(A7)
=C3×S(A4)+C7×S(A5)-C1×S(A6)+C5×S(A7)であり、
F(7)=-C1×[S(A4)+C4×(S(A6)-S(A5))]+C7×[C4×(S(A5)+S(A6))+S(A7))]
=-C1×S(A4)+C4×(C7+C1)×S(A5)+C4×(C7-C1)×S(A6)+C7×S(A7)
=-C1×S(A4)+C3×S(A5)-C5×S(A6)+C7×S(A7)であり、
ここで、C4×(C1-C7)=C4×C1-C4×C7=cos(4π/16)×cos(π/16)-cos(4π/16)×cos(7π/16)
=cos(4π/16)×cos(π/16)-sin(4π/16)×sin(π/16)=cos(4π/16+π/16)=cos(5π/16)=C5，
-C4×(C5-C3)=C4×C3-C4×C5=cos(4π/16)×cos(3π/16)-cos(4π/16)×cos(5π/16)
=cos(4π/16)×cos(3π/16)-sin(4π/16)×sin(3π/16)=cos(4π/16+3π/16)=cos(7π/16)=C7，
C4×(C3+C5)=C4×C3+C4×C5=cos(4π/16)×cos(3π/16)+cos(4π/16)×cos(5π/16)=
cos(4π/16)×cos(3π/16)+sin(4π/16)×sin(3π/16)=cos(4π/16-3π/16)=cos(π/16)=C1，
及びC4×(C7+C1)=C4×C7+C4×C1=cos(4π/16)×cos(7π/16)+cos(4π/16)×cos(π/16)
=cos(4π/16)×cos(π/16)+sin(4π/16)×sin(π/16)=cos(4π/16-π/16)=cos(3π/16)=C3である。
【００２９】
図６は、ＦＤＣＴフローグラフ１００の簡略化したバージョンを表し、ここで、出力信号６０３、即ち、Ｆ（０）〜Ｆ（７）、は−Ｃ１、Ｃ１、−Ｃ２、Ｃ２、Ｃ３、Ｃ４、−Ｃ５、Ｃ５、Ｃ６、−Ｃ７、Ｃ７、及び−１など、上述で計算した係数に基づいて、ノードＡ０〜Ａ７の信号に関して表される。図５のＳ（Ｂ０）〜Ｓ（Ｂ７）と前で計算したF（０）〜F（７）とを比較すると、下記のことが分かる。
（１）  Ｆ（０）とＳ（Ｂ０）が等価である。
（２）  Ｆ（４）とＳ（Ｂ１）が等価である。
（３）  Ｓ（Ａ２）とＳ（Ａ３）が交差する場合、Ｆ（２）はＳ（Ｂ３）と等価となる。
（４）  Ｓ（Ａ２）とＳ（Ａ３）交差する場合、Ｆ（６）はＳ（Ｂ２）と等価となる。
（５）  Ｓ（Ａ４）とＳ（Ａ７）交差する場合、Ｆ（１）はＳ（Ｂ７）と等価となる。
（６）  Ｓ（Ａ４）とＳ（Ａ７）交差する場合、Ｆ（３）はＳ（Ｂ６）と等価となる。
（７）  Ｓ（Ａ４）とＳ（Ａ７）交差する場合、Ｆ（５）はＳ（Ｂ５）と等価となる。
（８）  Ｓ（Ａ４）とＳ（Ａ７）交差する場合、Ｆ（７）はＳ（Ｂ４）と等価となる。
これらの関係を用いて、後に図７に図示するように、共用フローグラフ５０２が８ポイントＦＤＣＴフローグラフ１００内に形成され得る。つまり、ノードＡ２及びＡ３だけでなくノードＡ４及びＡ７が交差することにより、共用フローグラフ５０２が８ポイントＦＤＣＴフローグラフ１００内に形成され得る。
【００３０】
図７は、一実施例に従って、例示の順方向加算器ツリー・モジュール７０２及び図５の共用フローグラフ・モジュール５０２を含む８ポイントＦＤＣＴフローグラフ７００を示す。順方向加算器ツリー・モジュール７０２は、図４の順方向加算器ツリー・モジュール４０２の一例の実施例であることを理解されたい。８ポイントＦＤＣＴフローグラフ７００は、構成要素（例えば、加算器７０６〜７１７及び５０６〜５１９、及び乗算器７１８〜７２３及び５２０〜５３９）を用いて実装される場合、時間ドメインのデジタル入力データ７０４（例えば、並列の８個のデジタル入力データf（０）〜f（７））のＦＤＣＴ演算を実行して、周波数ドメインのデジタル出力データ７０５（例えば、並列の８個のデジタル出力データF（０）〜F（７））を生成する。
【００３１】
図７に図示するように、順方向加算器ツリー・モジュール７０２は、１２個の加算器（例えば、加算器７０６〜７１７）、及び６個の負の単位元乗算器（例えば、乗算器７１８〜７２３）を含む。各加算器は、２個の入力を受け単一の出力を生成する。各乗算器は、その入力値を−１で乗算するように構成される。共用フローグラフ・モジュール５０２は、１４個の加算器（例えば、加算器５０６〜５１９）、及び２０個の乗算器（例えば、乗算器５２０〜５３９）を含む。各加算器は２個の入力を受け単一の出力を生成する。各乗算器は、その入力値を一定の係数で乗算するように構成され、この係数は、−Ｃ１又は−π／１６、Ｃ１又はπ／１６、−Ｃ２又は−π／８、Ｃ２又はπ／８、Ｃ３又は３π／１６、Ｃ４又はπ／４、−Ｃ５又は−５π／１６、Ｃ５又は５π／１６、Ｃ６又は６π／１６、Ｃ７又は７π／１６、及び−１を含む。
【００３２】
図８は、一実施例に従った例示のＤＣＴ回路８００の概略図を示す。ＤＣＴ回路８００は、図７の順方向加算器ツリー・モジュール７０２、８個のマルチプレクサ８０２〜８１６、図５の共用フローグラフ・モジュール５０２、逆方向加算器ツリー・モジュール５０３、及び８個のマルチプレクサ８１８〜８３２を含む。順方向加算器ツリー・モジュール７０２の入力ノードＥ０〜Ｅ７は、デジタル入力データ７０４を受信するように構成される。８個のマルチプレクサ８０２〜８１６の入力ノードは、順方向加算器ツリー・モジュール７０２の出力ノードＦ０〜Ｆ７に接続され、デジタル入力データ７０４を受信するように構成される。共用フローグラフ・モジュール５０２の入力ノードＡ０〜Ａ７は、８個のマルチプレクサ８０２〜８１６の出力ノードに接続される。逆方向加算器ツリー・モジュール５０３の入力ノードＣ０〜Ｃ７は、共用フローグラフ・モジュール５０２の出力ノードＢ０〜Ｂ７に接続される。８個のマルチプレクサ８１８〜８３２の入力ノードは、共用フローグラフ・モジュール５０２の出力ノードＢ０〜Ｂ７、及び逆方向加算器ツリー・モジュール５０３の出力ノードＤ０〜Ｄ７に接続される。
【００３３】
図８に図示するように、８個のマルチプレクサ８０２〜８３２の各々は２：１マルチプレクサである。ＤＣＴ回路８００の一例の演算において、それらの制御信号８３４として「０」を受信すると、８個のマルチプレクサ８０２〜８１６が、順方向加算器ツリー・モジュール７０２の出力ノードＦ０〜Ｆ７から各々の信号を選択するように構成され、８個のマルチプレクサ８１８〜８３２が、共用フローグラフ・モジュール５０２の出力ノードＢ０〜Ｂ７から各々の信号を選択するように構成される。更に、８個のマルチプレクサ８１８〜８３２は、デジタル入力データ７０４のＦＤＣＴ演算を表す、デジタル出力データ７０５、即ち、F（０）〜F（７）、を並列に生成するように構成される。
【００３４】
ＤＣＴ回路８００の別の演算例では、それらの制御信号８３４として「１」を受信すると、８個のマルチプレクサ８０２〜８１６がデジタル入力データ７０４を選択するように構成され、８個のマルチプレクサ８１８〜８３２が、逆方向加算器ツリー・モジュール５０３の出力ノードＤ０〜Ｄ７から各々の信号を選択するように構成される。８個のマルチプレクサ８１８〜８３２は、デジタル入力データ５０４のＩＤＣＴ演算を表す、デジタル出力データ５０５、即ち、f（０）〜f（７）、を並列に生成するように構成される。
【００３５】
本明細書に記載の種々のデバイス、モジュール、アナライザ、生成器などは、ハードウェア回路（例えば、論理回路に基づく相補型金属酸化膜半導体（ＣＭＯＳ））、ファームウェア、ソフトウェア、及び／又はハードウェア、ファームウェア及び／又はソフトウェアの任意の組み合わせ（例えば、機械により解読可能な媒体に組み込まれる）を用いて作動し及び操作され得る。また、種々の電気的構造及び方法は、トランジスタ、論理ゲート、及び／又は電気的回路（例えば、特定用途向け集積回路（ＡＳＩＣ））を用いて組み込まれ得る。本願実施例を特定の例示の実施例に関連して説明してきたが、これらの種々の実施例の範囲及び趣旨から逸脱することなく、これらの実施例に種々の変形及び変更が成され得ることは明らかであろう。例えば、本願実施例は一次元ＤＣＴに関して説明している。しかし、これらの実施例は、転置された出力を有するマルチ・パスＤＣＴと同じように、多次元ＤＣＴに適用され得る。例えば、ＪＰＥＧ及びビデオ符号化／復号化技術のベースとなっている二次元ＤＣＴは、単に、画像又はマトリックスの一次元ＤＣＴを、行に沿って及びその後列に沿って、又はその逆に実行したものである。
【図１】
2013513866.tif 000009
【図２】
2013513866.tif 000010
【図３】
2013513866.tif 000011
【図４】
2013513866.tif 000012
【図５】
2013513866.tif 000013
【図６】
2013513866.tif 000014
【図７】
2013513866.tif 000015
【図８】
2013513866.tif 000016
【国際調査報告】
2013513866.tif 000017
2013513866.tif 000018