JPH06149861A

JPH06149861A - Ｄｃｔ及び逆ｄｃｔ演算装置並びにその演算方法

Info

Publication number: JPH06149861A
Application number: JP30207192A
Authority: JP
Inventors: Masato Motomura; 真人本村
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1992-11-12
Filing date: 1992-11-12
Publication date: 1994-05-31
Anticipated expiration: 2013-03-11
Also published as: US5477469A; JP2725544B2

Abstract

(57)【要約】【目的】画像データの高能率符号化の中心的処理である
ＤＣＴ，逆ＤＣＴ演算を高速に実行し、かつ高能率符号
化の他の処理にも使用できる、高性能かつ柔軟なＤＣ
Ｔ，逆ＤＣＴ演算装置並びにその演算方法を提供する。【構成】データメモリ１１０と、アドレス発生手段１２
０と、加算器１４０と、積和演算器１５０とを有するＤ
ＣＴ，逆ＤＣＴ演算装置であって、加算器１４０で加減
算手続きを実行し、その結果に対して積和演算器１５０
で積和演算手続きを実行することにより一次元Ｎ次ＤＣ
Ｔを実行し、また積和演算器１５０で積和演算手続きを
実行し、その結果に対して加算器１４０で加減算手続き
を実行することにより、一次元Ｎ次逆ＤＣＴを実行す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はテレビ電話システム，テ
レビ会議システム，ディジタルＶＴＲ等において用いら
れる画像データの高能率符号化処理の構成要素に係り、
より具体的には高能率符号化処理の中核を成す離散コサ
イン変換（ディスクリート・コサイン・トランスフォー
ム：ＤｉｓｃｒｅｔｅＣｏｓｉｎｅＴｒａｎｓｆｏ
ｒｍ：以後ＤＣＴと呼ぶ），逆離散コサイン変換（イン
バース・コサイン・トランスフォーム：Ｉｎｖｅｒｓｅ
ＣｏｓｉｎｅＴｒａｎｓｆｏｒｍ：以後逆ＤＣＴあ
るいはＤＣＴ^-1と呼ぶ）を高速に処理する、ＤＣＴ，逆
ＤＣＴ演算装置とその演算方法に関する。

【０００２】

【従来の技術】ＤＣＴとは、画像情報等の離散データ
（以下原画像データと呼ぶ）をコサイン関数を用いて周
波数空間の離散データ（以下ＤＣＴ変換結果と呼ぶ）に
変換するものであり、原画像データとＤＣＴ変換係数の
積和演算を行うことにより実行され、演算の結果、ＤＣ
Ｔ変換結果を得る。逆ＤＣＴはこのＤＣＴの逆変換であ
り、ＤＣＴ変換結果と逆ＤＣＴ変換係数の積和演算を行
うことで実行され、演算の結果、原画像データを得る。
１次元の場合のＤＣＴ及び逆ＤＣＴは、データ数をＮと
したとき、Ｎ次の１次元ＤＣＴ及び逆ＤＣＴ、あるいは
１次元Ｎ次ＤＣＴ及び、１次元Ｎ次逆ＤＣＴと呼ぶ。そ
して、Ｎ次の１次元ＤＣＴ及び逆ＤＣＴにおける原画像
データをｘ（ｉ；Ｎ），ＤＣＴ変換結果をｙ（ｋ；Ｎ）
とすると、０≦ｉ，ｋ＜Ｎとして、ｙ（ｋ；Ｎ）及びｘ
（ｉ；Ｎ）はそれぞれ、ｙ（ｋ；Ｎ）＝ｘ（ｉ；Ｎ）ｄ（ｉ，ｋ；Ｎ）｜ｉ …（１）ｘ（ｉ；Ｎ）＝ｆ（ｉ，ｋ；Ｎ）ｙ（ｋ；Ｎ）｜ｋ …（２）と表される。ただし、ｄ（ｉ，ｋ；Ｎ）＝（２／Ｎ）（１／２）^1/2 ：ｋ＝０のとき＝（２／Ｎ）ｃｏｓ｛π（２ｉ＋１）ｋ／２ｎ｝：ｋ＝０のときｆ（ｉ，ｋ；Ｎ）＝（１／２）^1/2 ＝ｃｏｓ｛π（２ｉ＋１）ｋ／２Ｎ｝：ｋ＝０以外のときなお、上式では変数ｉに対する累算を“｜ｉ”のように
記述した。またｄ（ｉ，ｋ；Ｎ）をＤＣＴ変換係数、ｆ
（ｉ，ｋ；Ｎ）を逆ＤＣＴ変換係数と呼ぶ。上記（１）
式がＤＣＴで、（２）式がＤＣＴ^-1である。

【０００３】次に、Ｎ次の２次元ＤＣＴ，逆ＤＣＴは、
原画像データをｘ（ｉ，ｊ；Ｎ）、ＤＣＴ変換結果をｙ
（ｋ，ｌ；Ｎ）とすると、０≦ｉ，ｊ，ｋ，ｌ＜Ｎとし
て、ｙ（ｋ，ｌ；Ｎ）＝ｄ（ｊ，ｌ；Ｎ）ｘ（ｉ，ｊ；Ｎ）ｄ（ｉ，ｋ；Ｎ）｜ｉ，ｊ…（３）ｘ（ｉ，ｊ；Ｎ）＝ｆ（ｉ，ｋ；Ｎ）ｙ（ｋ，ｌ；Ｎ）ｆ（ｉ，ｊ；Ｎ）｜ｋ，ｌ…（４）と表すことが出来る。上記（３）式及び（４）式からわ
かるように、Ｎ次の２次元ＤＣＴ，逆ＤＣＴは、それぞ
れＮ次の１次元ＤＣＴ，逆ＤＣＴと同じ形の積和演算を
２Ｎ回繰り返すことで実行できる。

【０００４】原画像データのデータ量を大幅に削減する
ことを目的とした高能率符号化処理では、この２次元Ｄ
ＣＴ，２次元逆ＤＣＴと動きベクトル検出，ＦＩＲフィ
ルタ，量子化等の処理を用いてデータの圧縮を行う。Ｍ
ＰＥＧ、ＣＣＩＴＴ−Ｈ．２６１等の高能率符号化の標
準化方式勧告案では、変換の対象となる画像データは８
×８画素とされている。つまり、これらの標準化方式を
実現するためには２次元８次ＤＣＴ，逆ＤＣＴを実行す
る必要がある。

【０００５】以上のようなＤＣＴの変換式を直接計算す
る方法がある。以下、この方法の従来技術その１と呼
ぶ。従来技術その１での演算量は、１次元Ｎ次ＤＣＴ，
逆ＤＣＴに対してＮ²回の積和演算、２次元Ｎ次ＤＣ
Ｔ，逆ＤＣＴに対して２Ｎ³の積和演算となる。よっ
て、従来技術その１の演算装置では、２次元８次ＤＣ
Ｔ，逆ＤＣＴを実行するのに、１サイクルで積和演算１
回を実行できるとしても、１０２４サイクルかかること
になる。このように、従来技術その１ではＮの３乗のオ
ーダーで処理サイクルが増大し、２次元８次ＤＣＴ，逆
ＤＣＴを実現するために、高能率符号化処理時間の約半
分という長い処理時間を必要とするという問題があっ
た。

【０００６】このような問題を解決するため、１９７０
年代からＤＣＴ，逆ＤＣＴの演算量を減らす高速アルゴ
リズムが開発されると共に、このような高速アルゴリズ
ムを実行する専用のＤＣＴ，逆ＤＣＴ演算装置が開発さ
れてきている。これらの高速アルゴリズムは、コサイン
関数の対称性，反対称性を利用して、ＤＣＴ，逆ＤＣＴ
の演算量を減らすのが特徴である。これらの高速アルゴ
リズムに基づくＤＣＴ，逆ＤＣＴ演算装置を従来技術そ
の２と呼ぶ。従来技術その２の例として、Ｂｙｅｏｎｇ
ＧｉＬｅｅ氏により、１９８４年１１月にＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｏｎＡｃｃｏｕｓｔｉｃ
ｓ，ＳｐｅｅｃｈａｎｄＳｉｇｎａｌＰｒｅｃｅｓ
ｓｉｎｇ，Ｖｏｌ．３２，Ｎｏ．６，ｐｐ．１２４３に
発表された高速アルゴリズムＦＣＴ法に基づくＤＣＴ，
逆ＤＣＴ演算装置を簡単に紹介する。

【０００７】図７に従来技術その２のＤＣＴ，逆ＤＣＴ
演算装置の構成例を示す。図７はＦＣＴ法に基づき、８
次のＤＣＴ，逆ＤＣＴの専用演算装置を構成した場合の
ブロック図である。図７において、従来技術その２のＤ
ＣＴ，逆ＤＣＴ装置は、加算装置７１０、７２０、７３
０、７４０、乗算装置７６０、７７０、７８０を交互に
並べた構成をしている。このような構成で、ＦＣＴ法の
アルゴリズムに基づく演算手順を実行することにより、
高速なＤＣＴ，逆ＤＣＴ演算を実現することが出来る。
このような基本概念に基づいたＤＣＴ，逆ＤＣＴ演算装
置の例としては、上谷氏等により東芝レビュー、ＶＯ
Ｌ．４５，ＮＯ．８，ＰＰ．６２３に発表された「高精
度・高速ＤＣＴ用ＬＳＩ」等がある。

【０００８】

【発明が解決しようとする課題】以上のように、従来技
術その２のＤＣＴ，逆ＤＣＴ演算装置により、ＤＣＴ，
逆ＤＣＴ演算を大幅に高速化することが出来る。しか
し、この従来技術その２の演算装置は下記の欠点を有し
ている。（１）演算装置のハードウェア量が非常に大きい。（２）特殊な構成をしているためＤＣＴ，逆ＤＣＴ以外
の他の高能率符号化処理には使えない。（３）ＤＣＴ，逆ＤＣＴの変換の次数に応じて必要とさ
れている乗算装置，加算装置の数および構成が変化する
ので、柔軟性に欠ける。

【０００９】このため、テレビ会議システム、テレビ電
話システム等で用いられる高能率符号化処理値の小型化
・低価格化が困難だという問題が生じる。

【００１０】このような問題を解決するためには、動き
ベクトル検出，ＦＩＲフィルタ，量子化等の高能率符号
化のその他の主要な処理と共用化できるような汎用的な
構成を持ち、しかも従来技術その１よりも大幅に処理を
高速化することが出来る、ＤＣＴ，逆ＤＣＴ演算装置が
必要である。

【００１１】本発明の目的はこのような問題を解決し、
高性能でかつ柔軟なＤＣＴ，逆ＤＣＴ演算装置、並びに
その演算方法を提供することにある。

【００１２】

【課題を解決するための手段】第１の発明のＤＣＴ，逆
ＤＣＴ演算装置は、（Ａ）原画像データ，演算途中結
果，ＤＣＴ変換結果，ＤＣＴ変換係数，逆ＤＣＴ変換係
数を記憶するデータメモリ、（Ｂ）前記データメモリの
読みだし及び書き込みアドレスを指定するアドレス発生
手段、（Ｃ）前記アドレス発生手段の指定する前記デー
タメモリの複数のアドレスから読み出されたデータ間の
加算または減算を行い、前記加算結果を前記アドレス発
生手段の指定する前記データメモリのアドレスに書き込
む加算器、（Ｄ）前記アドレス発生手段の指定する前記
データメモリの複数のアドレスから読み出されたデータ
間の積和演算を行い、前記積和演算結果を前記アドレス
発生手段の指定する前記データメモリのアドレスに書き
込む積和演算器、を有して構成されている。

【００１３】また、第２の発明のＤＣＴ演算方法は第１
の発明のＤＣＴ及び逆ＤＣＴ演算装置におけるＮ次（Ｎ
は２の正のべき乗で表される任意の正整数）の１次元Ｄ
ＣＴの演算方法であって、（Ａ）０から（Ｍ−１）まで
の引数を持つＭ個（Ｍは２からＮまでの２の正のべき乗
で表される任意の正整数）のデータを入力として持ち、
前記アドレス発生手段の指定により、前記入力データの
うち引数の和がＭである二つの前記入力データの組を順
次前記データメモリから読みだし、読み出された二つの
前記入力データ間の加算を前記加算器で行い、１から
（Ｍ／２−１）までの引数を持つＭ／２個の加算結果を
前記データメモリに書き込む加算ステップ、（Ｂ）０か
ら（Ｍ−１）までの引数を持つＭ個のデータを入力とし
て持ち、前記アドレス発生手段の指定により、前記入力
データのうち引数の和がＭである二つの前記入力データ
の組を順次前記データメモリから読み出し、読み出され
た二つの前記入力データ間の減算を前記加算器で行い、
１から（Ｍ／２−１）までの引数を持つＭ／２個の減算
結果を前記データメモリに書き込む減算ステップ、
（Ｃ）０から（Ｌ−１）までの引数を持つＬ個（Ｌは２
からＮ／２までの２の正のべき乗で表される任意の正整
数）のデータと、Ｌ²個のＤＣＴ変換係数とを入力とし
て持ち、前記アドレス発生手段の指定により、前記入力
データと前記入力ＤＣＴ変換係数を順次前記データメモ
リから読みだし、読み出された前記入力データと前記入
力ＤＣＴ変換係数間の積和演算を前記積和演算器で行
い、Ｌ個のＤＣＴ変換結果を出力する第１の積和演算ス
テップ、（Ｄ）０から１までの引数を持つ２個のデータ
と、４個のＤＣＴ変換係数とを入力として持ち、前記ア
ドレス発生手段の指定により、前記入力データと前記入
力ＤＣＴ変換係数を順次前記データメモリから読みだ
し、読み出された前記入力データと前記入力ＤＣＴ変換
係数間の積和演算を前記積和演算器で行い、２個のＤＣ
Ｔ変換結果を出力する第２の積和演算ステップ、を有
し、（ｌｏｇ₂Ｎ−１）回の前記加算ステップと（ｌｏ
ｇ₂Ｎ−１）回の前記減算ステップを行う加減算手続き
と、（ｌｏｇ₂Ｎ−１）回の前記第１の積和演算ステッ
プと１回の前記第２の積和演算ステップを行う積和演算
手続とにより１次元Ｎ次ＤＣＴ演算を実行し、前記加減
算手続器においては、第１回目の前記加算ステップおよ
び第１回目の前記減算ステップの前記入力データとし
て、０から（Ｎ−１）までの引数を持つＮ個の前記原画
像データを用い、第ｍ回目（ｍは２から（ｌｏｇ₂Ｎ−
１）までの任意の正整数）の前記加算ステップおよび第
ｍ回目の前記減算ステップの前記入力データとして第
（ｍ−１）回目の前記加算ステップの前記加算結果を用
い、前記積和演算手続においては、第ｎ回目（ｎは１か
ら（ｌｏｇ₂Ｎ−１）までの任意の正整数）の前記第１
の積和演算ステップの前記入力データとして、第ｎ回目
の前記減算ステップの前記減算結果を用い、前記第２の
積和演算ステップの入力データとして第（ｌｏｇ₂Ｎ−
１）回目の前記加算ステップの加算結果を用い、第１か
ら第（ｌｏｇ₂Ｎ−１）までの前記第１の積和演算ステ
ップと前記第２の積和演算ステップの積和演算の結果と
して、合計でＮ個の前記ＤＣＴ変換経過を得るように構
成されている。

【００１４】また、第３の発明の逆ＤＣＴ演算方法は、
第１の発明のＤＣＴ及び逆ＤＣＴ演算装置におけるＮ次
の１次元ＤＣＴの演算方法であって、（Ａ）０からＮ−
１までの引数を持つＮ個の前記ＤＣＴ変換結果のうち
で、引数Ｎ／２ⁿで割った余りがＮ／２ⁿ⁺¹である引数
を持つ２ⁿ個の前記ＤＣＴ変換結果と、２²ⁿ個の前記逆
ＤＣＴ変換係数とを入力として持ち、前記アドレス発生
手段の指定により、前記入力ＤＣＴ変換経過と、前記入
力逆ＤＣＴ変換係数を順次データメモリから読み出し、
読み出された前記入力ＤＣＴ変換結果と前記入力逆ＤＣ
Ｔ変換係数間の積和演算を前記第１の積和演算器で行
い、０から（２ⁿ−１）までの引数を持つ２ⁿ個の積和
演算結果を出力する第１の積和演算ステップ、（Ｂ）前
記ＤＣＴ変換結果のうちで、引数が０とＮ／２である２
個の前記ＤＣＴ変換結果と、４個の前記逆ＤＣＴ変換係
数とを入力として持ち、前記アドレス発生手段の指定に
より、前記入力データと前記入力逆ＤＣＴ変換係数を順
次データメモリから読み出し、読み出された前記入力デ
ータと前記入力逆ＤＣＴ変換係数間の積和演算を前記第
２の積和演算器で行い、０から１までの引数を持つ２個
の積和演算結果を出力する第２の積和演算ステップ、
（Ｃ）０から（Ｌ−１）までの引数を持つＬ個のデータ
二組を入力として持ち、前記アドレス発生手段の指定に
より、二組の前記入力データのうち、引数が同じである
二つの前記入力データの組を順次前記データメモリから
読みだし、読み出された二つの前記入力データ間の加算
を前記加算器で行い、Ｌ個の加算結果を前記データメモ
リに書き込む加算ステップ、（Ｄ）０から（Ｌ−１）ま
での引数を持つＬ個のデータ二組を入力として持ち、前
記アドレス発生手段により、二組の前記入力データのう
ち、引数が同じである二つの前記入力データの組を順次
前記データメモリから読み出し、読み出された二つの前
記入力データ間の減算を前記加算器で行い、Ｌ個の減算
結果を前記データメモリに書き込む減算ステップ、を有
し、（ｌｏｇ₂Ｎ−１）回の第１の積和演算ステップと
１回の第２の積和演算ステップを行う積和演算手続と、
（ｌｏｇ₂Ｎ−１）回の加算ステップと（ｌｏｇ₂Ｎ−
１）回の減算ステップを行う加減算手続きとにより１次
元Ｎ次逆ＤＣＴを実行し、前記積和演算手続きにおいて
は、第ｎ回目の第１の積和演算ステップで、前記２ⁿ個
の逆ＤＣＴ変換結果を入力として用い、前記加減手続き
においては、第１回目の前記加算ステップおよび第１回
目の前記減算ステップの二組の前記入力データとして、
前記第２の積和演算ステップの前記積和演算結果と第１
回目の前記第１の積和演算ステップの前記積和演算結果
とを用い、第ｍ回目の前記加算ステップおよび第ｍ回目
の前記減算ステップのそれぞれの二組の前記入力データ
として第（ｍ−１）回目の前記加算ステップの前記加算
結果及び第（ｍ−１）回目の前記減算ステップの前記減
算結果と、第ｍ回目の前記第１の積和演算ステップの前
記積和演算結果とを用い、第（ｌｏｇ₂Ｎ−１）回目の
前記加算ステップの前記加算結果および第（ｌｏｇ₂Ｎ
−１）回目の前記減算ステップの前記減算結果として、
Ｎ個の原画像データを得るように構成されている。

【００１５】また、第４の発明のＤＣＴ演算方法は、第
１の発明のＤＣＴ及び逆ＤＣＴ演算装置におけるＮ次の
２次元ＤＣＴ演算方法であって、第２の発明の１次元Ｎ
次ＤＣＴ演算方法を２Ｎ回繰り返すことにより２次元Ｎ
次ＤＣＴ演算を行い、前記加算器と前記積和演算器を並
列動作させることにより、ある前記１次元Ｎ次ＤＣＴ演
算の前記積和演算手続きと、その次の繰り返しの前記１
次元Ｎ次ＤＣＴ演算の加減算手続きとを並列に処理する
ように構成されている。

【００１６】また、第５の発明の逆ＤＣＴ演算方法は、
第１の発明のＤＣＴ及び逆ＤＣＴ演算装置におけるＮ次
の２次元逆ＤＣＴ演算方法であって、第３の発明の１次
元Ｎ次逆ＤＣＴ演算方法を２Ｎ回繰り返すことにより２
次元Ｎ次逆ＤＣＴ演算を行い、前記加算器と前記積和演
算器を並列動作させることにより、ある前記１次元Ｎ次
逆ＤＣＴ演算の前記加減算手続きと、その次の繰り返し
の前記１次元Ｎ次逆ＤＣＴ演算の前記積和演算手続きと
を並列に処理するように構成されている。

【００１７】

【実施例】次に、本発明の実施例について図面を参照し
て説明する。

【００１８】図１は本発明のＤＣＴ，逆ＤＣＴ演算装置
の一実施例を示すブロック図である。図１において、本
実施例のＤＣＴ，逆ＤＣＴ演算装置は、原画像データ，
ＤＣＴ変換結果，演算途中結果，ＤＣＴ変換係数，逆Ｄ
ＣＴ変換係数を記憶するデータメモリ１１０と、データ
メモリ１１０に外部からデータを与える入力端子１０１
と、データメモリ１１０の読み出し及び書き込みアドレ
スを指定するアドレス発生手段１２０と、データメモリ
から読み出されたデータを受け取る入力バス１３０と、
入力バス１３０から２つの入力データを受け取り加算ま
たは減算を行う加算器１４０と、入力バス１３０から２
つの入力データを受け取り積和演算を行う積和演算器１
５０と、加算器１４０の出力もしくは積和演算器１５０
の出力を受け取り、データメモリ１１０への書き込みを
行う出力バス１６０と、ＤＣＴ変換結果あるいはＤＣＴ
逆変換の結果復元された原画像データを外部へ出力する
外部出力端子１０２とからなっている。

【００１９】図２は図１のＤＣＴ，逆ＤＣＴ演算装置に
おける本発明の１次元Ｎ次（Ｎは２の正のべき乗で表さ
れる正整数）ＤＣＴの演算方法を示す流れ図である。

【００２０】図２において、本発明のＤＣＴ演算方法
は、加算ステップ２１０，演算ステップ２２０，積和演
算ステップ２３０−１、積和演算ステップ２３０−２の
各演算ステップを、図２に示された処理の手順に従って
順次Ｎ個の原画像データｘ（ｉ；Ｎ）２４０に対して施
すことにより実行されている。まず、これらの各演算ス
テップの動作を図１を引用して説明する。

【００２１】図２の加算ステップ２１０は、Ｎ／２^p個
（ｐは０から（ｌｏｇ₂Ｎ−２）までの正整数）の加減
算入力データｘ^P（ｑ；Ｎ／２^p）２５０から、Ｎ／２
^(p+1) 個の加算結果ｘ^p+1 （ｕ；Ｎ／２^p+1 ）２６０を
次の（５）式に従って算出するステップである。ただ
し、ｑ及びｕの範囲は０≦ｑ＜Ｎ／２^P，０≦ｕ＜Ｎ／
２^p+1である。

【００２２】ｘ^P+1 （ｕ；Ｎ／２^p+1 ）＝ｘ^P（ｕ；Ｎ／２^p）＋ｘ^p（Ｎ／２^p−１−ｕ；Ｎ／２^p） …（５）図１のＤＣＴ，逆ＤＣＴ演算装置においてこの加算ステ
ップ２１０は以下のようにして実行される。加減算入力
データｘ^p（ｑ；Ｎ／２^p) ２５０はデータメモリ１１
０に記憶されている。アドレス発生手段１２０の指定に
従って、上式の右辺の二つの項のように、引数の和がＮ
／２^pになる二つの加減算入力データ２５０が入力バス
１３０に読み出され、加算器１４０に与えられる。加算
器１４０で上式の計算が行われ、加算結果ｘ^p+1 （ｕ；
Ｎ／２^p+1 ）２６０がデータメモリ１１０に書き込まれ
る。

【００２３】図２の減算ステップ２２０は、Ｎ／２^p個
（ｐは０から（ｌｏｇ₂Ｎ−２）までの正整数）の加減
算入力データｘ^p（ｑ；Ｎ／２^p）２５０から、Ｎ／２
^(p+1) 個の減算結果ｇ^p+1 （ｕ；Ｎ／２^p+1 ）２７０を
次の（６）式に従って算出するステップである。

【００２４】ｇ^p+1 （ｕ；Ｎ／２^p+1 ）＝ｘ^p（ｕ；Ｎ／２^p）−ｘ^p（Ｎ／２^p−１−ｕ；Ｎ／２^p） …（６）図１のＤＣＴ、逆ＤＣＴ演算装置においてこの減算ステ
ップ２２０は以下のようにして実行される。加減算入力
データｘ^p（ｑ；Ｎ／２^p）２５０はデータメモリ１１
０に記憶されている。アドレス発生手段１２０の指定に
従って、上式の右辺の二つの項のように、引数の和がＮ
／２^pになる二つの加減算入力データ２５０が入力バス
１３０に読み出され、加算器１４０に与えられる。加算
器１４０で上式の計算が行われ、減算結果ｇ^p+1 （ｕ；
Ｎ／２^p+1）２７０がデータメモリ１１０に書き込まれ
る。

【００２５】図２の積和演算ステップ２３０−１は、Ｎ
／２^r個（ｒは１から（ｌｏｇ₂Ｎ−１）までの正整
数）の減算結果ｇ^r（ｓ；Ｎ／２^r）２７０と、（Ｎ／
２^r）²個のＤＣＴ変換係数２９０−１から、Ｎ／２^r
個のＤＣＴ変換結果２８０を次の（７）式に従って算出
するステップである。ただし、０≦ｓ、ｔ＜Ｎ／２^rで
ある。

【００２６】ｙ（２^rｔ＋２^r-1；Ｎ）＝ｇ^r(s；Ｎ／２^r）ｄ（ｓ，２^rｔ＋２^r-1 ；Ｎ）｜ｓ …（７）図１のＤＣＴ，逆ＤＣＴ演算装置においてこの積和ステ
ップ２３０−１は以下のようにして実行される。演算結
果ｇ^r（ｓ；Ｎ／２^r）２７０とＤＣＴ変換係数２９０
−１はデータメモリ１１０に記憶されている。アドレス
発生手段１２０の指定に従って、減算結果とＤＣＴ変換
係数がそれぞれ入力バス１３０に順次読み出され、積和
演算器１４０に与えられる。積和器１４０で上式の計算
が行われ、ＤＣＴ変換結果ｙ（２^rｔ＋２^r-1;Ｎ）２８
０が外部出力端子１０２から外部へ出力される。

【００２７】図２の積和演算ステップ２３０−２は、２
個の加算結果ｘ^α （Ｗ；２）２６０と、４個のＤＣＴ
変換係数２９０−２から２個のＤＣＴ変換結果２８０を
次の（８）式に従って算出するステップである。ただ
し、０≦ｖ，ｗ＜２である。また、^α＝ｌｏｇ₂Ｎ−
１としている。

【００２８】ｙ（Ｎｖ／２；Ｎ）＝ｘ^α （ｗ；２）ｄ（ｗ，Ｎｖ／２；Ｎ）｜ｗ…（８）図１のＤＣＴ，逆ＤＣＴ演算装置においてこの積和ステ
ップ２３０−２は以下のようにして実行される。加算結
果ｘ^α （ｗ；２）２６０どＤＣＴ変換係数２９０−２
はデータメモリ１１０に記憶されている。アドレス発生
手段１２０の指定に従って、加算結果２６０とＤＣＴ変
換係数２９０−２がそれぞれ入力バス１３０に順次読み
出され、積和演算器１４０に与えられる。積和演算器１
４０で上式の計算が行われ、ＤＣＴ変換結果ｙ（Ｎｖ／
２；Ｎ）２８０が外部出力端子１０２から外部へ出力さ
れる。

【００２９】次に、図２の全体のＤＣＴ演算の手順を図
１を参照しながら説明する。図２において、本実施例の
１次元Ｎ次ＤＣＴの演算方法は、加減算手続き２９２と
積和演算手続き２９４とから構成されている。

【００３０】加減算手続き２９２においては、まず始め
に、入力端子１０１より外部から与えられ、データメモ
リ１１０に記憶された原画像データｘ（ｉ；Ｎ）２４０
を入力データとして用いる。スイッチ２０１は第１回目
の加算ステップ２１０と第１回目の減算ステップ２２０
の加減算入力データ２５０として原画像データｘ（ｉ；
Ｎ）２４０を与え、２回目から（ｌｏｇ₂Ｎ−１）回目
までの加算ステップ２１０と減算ステップ２２０の加減
算入力データ２５０として、それぞれ一回前の加算ステ
ップ２１０の加算結果２６０を用いることを示してい
る。それぞれの、加算ステップ２１０、減算ステップ２
２０は、上記の説明に従って、図１のＤＣＴ，逆ＤＣＴ
演算装置で実行される。ここで、上記の加算ステップ２
１０、減算ステップ２２０の説明における入力データｘ
^p（ｑ；Ｎ／２^p）２５０で、ｐ＝０の場合が原画像デ
ータｘ（ｉ；Ｎ）２４０に対応することになる。また、
スイッチ２０２は、第（ｌｏｇ₂Ｎ−１）回目の加算ス
テップ２１０の加算結果２６０については、再度加算ス
テップ２１０、減算ステップ２２０の入力とすることを
せずに、積和演算ステップ２３０−２へ入力することを
示している。このような手順で再帰的に加算ステップ２
１０、減算ステップ２２０を行うことにより、加算結果
ｘ^p+1（ｕ；Ｎ／２^p+1）２６０、減算結果ｇ
^p+1（ｕ；Ｎ／２^p+1）２７０が得られる。

【００３１】次に、積和演算手続き２９４を加減算手続
き２９２の演算結果を用いて実行する。ｇ¹からｇ^α
までの減算結果ｇ^p+1（ｕ；Ｎ／２^p+1）２７０を入力
として用い、上記の説明に従って、積和演算ステップ２
３０−１を（ｌｏｇ₂Ｎ−１）回行うことにより、それ
ぞれＮ／２^p+1個のＤＣＴ変換結果を算出する。また加
算結果ｘ^α（ｗ；２）２６０を入力として用い、積和
演算ステップ２３０−２を行うことにより２個のＤＣＴ
変換結果を算出する。

【００３２】以上の処理手順により、合計でＮ個の、１
次元Ｎ次ＤＣＴ演算の演算結果が得られることになる。

【００３３】図３は図１のＤＣＴ，逆ＤＣＴ演算装置に
おける１次元Ｎ次逆ＤＣＴの演算方法の実施例を示す流
れ図である。

【００３４】図３において、本発明の逆ＤＣＴ演算方法
は、積和演算ステップ３１０−１，積和演算ステップ３
１０−２，加算ステップ３２０，減算ステップ３３０の
各演算ステップを、図３に示された処理の手順に従っ
て、順次Ｎ個のＤＣＴ変換結果ｙ（ｋ；Ｎ）３４０に対
して施すことにより実行されている。まず、これらの各
演算ステップの動作を図１を引用して説明する。

【００３５】図３の積和演算ステップ３１０−１は、２
^r個（ｒは１から（ｌｏｇ₂Ｎ−１）までの正整数）の
ＤＣＴ変換結果ｙ（Ｎｔ／２^r＋Ｎ／２^r+1；Ｎ）３４
０と、２^2r個のＤＣＴ逆変換係数３９０−１から、２^r
個の加減算入力データｈ₁ ^r（ｓ；２^r）３６０−１を
次の（９）式に従って算出するステップである。ただ
し、０≦ｓ、ｔ＜２^rである。

【００３６】ｈ₁ ^r（ｓ；２^r）＝ｆ（ｓ，Ｎｔ／２^r＋Ｎ／２^r+1；Ｎ）ｙ（Ｎｔ／２^r＋Ｎ／２^r+1；Ｎ）｜ｔ …（９）図１のＤＣＴ、逆ＤＣＴ演算装置においてこの積和ステ
ップ３１０−１は以下のようにして実行される。ＤＣＴ
変換結果ｙ（Ｎｔ／２^r ＋Ｎ／２^r+1 ；Ｎ）３４０と逆
ＤＣＴ変換係数３９０−１はデータメモリ１１０に記憶
されている。アドレス発生手段１２０の指定に従って、
ＤＣＴ変換結果３４０と逆ＤＣＴ変換係数３９０−１が
それぞれ入力バス１３０に順次読み出され、積和演算器
１５０に与えられる。積和演算器１５０で上式の計算が
行われ、加減算入力データｈ₁ ^r（ｓ；２^r ）３６０−１
がデータメモリ１１０に書き込まれる。

【００３７】図３の積和演算ステップ３１０−２は、２
個のＤＣＴ変換結果ｙ（Ｎｖ／２；Ｎ）３４０と、４個
の逆ＤＣＴ変換係数３９０−２から、２個の積和演算結
果ｈ₀ ¹（ｗ；２）３５０を次の（１０）式に従って算出
するステップである。ただし、０≦ｖ，ｗ〈２である。

【００３８】ｈ₀ ¹（ｗ；２）＝ｆ（ｗ，Ｎｖ／２；Ｎ）ｙ（Ｎｖ／２；Ｎ）｜ｖ …（１０）図１のＤＣＴ、逆ＤＣＴ演算装置においてこの積和演算
ステップ３１０−２は以下のようにして実行される。Ｄ
ＣＴ変換結果ｙ（Ｎｖ／２；Ｎ）３４０と逆ＤＣＴ変換
係数３９０−２はデータメモリ１１０に記憶されてい
る。アドレス発生手段１２０の指定に従って、ＤＣＴ変
換結果３４０と逆ＤＣＴ変換係数３９０−２がそれぞれ
入力バス１３０に順次読み出され、積和演算器１５０に
与えられる。積和器１５０で上式の計算が行われ、積和
演算結果ｈ₀ ¹（ｗ；２）３５０がデータメモリ１１０に
書き込まれる。

【００３９】図３の加算ステップ３２０は、２^r 個の加
減算入力データｈ₁ ^r（ｓ；２^r ）３６０−１と２^r 個の
加減算入力データｈ₀ ^r（ｓ；２^r ）３６０−２から、２
^r 個の加算結果ｈ₀ ^r+1（ｓ；２^r+1 ）３７０−１を次の
（１１）式に従って算出するステップである。

【００４０】ｈ₀ ^r+1（ｓ；２^r+1)＝ｈ₀ ^r（ｓ；２^r）＋ｈ₁ ^r（ｓ；２^r） …（１１）図１のＤＣＴ、逆ＤＣＴ演算装置においてこの加算ステ
ップ３２０は以下のようにして実行される。加減算入力
データｈ₁ ^r（ｓ；２^r ）３６０−１と加減算入力データ
ｈ₀ ^r（ｓ；２^r ）３６０−２はデータメモリ１１０に記
憶されている。アドレス発生手段１２０の指定に従っ
て、上式の右辺の二つの頃のように、引数が等しい二つ
の入力データが入力バス１３０に読み出され、加算器１
４０に与えられる。加算器１４０で上式の計算が行わ
れ、加算結果ｈ₀ ^r+1（ｓ；２^r+1 ）３７０−１がデータ
メモリ１１０に書き込まれる。

【００４１】図３の減算ステップ３３０は、２r 個の加
減算入力データｈ₁ ^r（ｓ；２^r ）３６０−１と２^r 個の
加減算入力データｈ₀ ^r（ｓ；２^r ）３６０−２から、２
^r 個の減算結果ｈ₀ ^r+1（２^r+1 −１−ｓ；２^r+1 ）３７
０−２を次の（１２）式に従って算出するステップであ
る。

【００４２】ｈ₀ ^r+1（２^{r +1}−１−ｓ；２^r+1)＝ｈ₀ ^r（ｓ；２^r ）−ｈ₁ ^r（ｓ；２^r） …（１２）図１のＤＣＴ，逆ＤＣＴ演算装置においてこの減算ステ
ップ３３０は以下のようにして実行される。加減算入力
データｈ₁ ^r（ｓ；２^r ）３６０−１と加減算入力データ
ｈ₀ ^r（ｓ；２^r ）３６０−２はデータメモリ１１０に記
憶されている。アドレス発生手段１２０の指定に従っ
て、上式の右辺の二つの頃のように、引数が等しい二つ
の入力データが入力バス１３０に読み出され、加算器１
４０に与えられる。加算器１４０で上式の計算が行わ
れ、減算結果ｈ₀ ^r+1（２^r+1 −１−ｓ；２^r+1 ）３７０
−２がデータメモリ１１０に書き込まれる。

【００４３】次に、図３の全体の逆ＤＣＴ演算の手順を
図１を参照しながら説明する。図３において本実施例の
１次元Ｎ次逆ＤＣＴ変換の演算方法は積和演算手続き３
９２と加減算手続き３９４とから構成されている。

【００４４】積和演算手続き３９２においては、まず始
めに、入力端子１０１より外部から与えられたＤＣＴ変
換結果ｙ（ｋ；Ｎ）３４０を入力データとして用いる。
上記の説明に従って、第１回目から第（ｌｏｇ2 Ｎ−
１）回までの第ｒ回目の積和演算ステップ３１０−１
が、それぞれＤＣＴ変換結果ｙ（Ｎｔ／２^r ＋Ｎ／２
^r+1；Ｎ）３４０に対して実行され、加減算入力データ
ｈ₁ ^r（ｓ；２^r ）３６０−１がデータメモリ１１０に書
き込まれる。また積和演算ステップ３１０−２がＤＣＴ
変換結果ｙ（Ｎｖ／２；Ｎ）３４０に対して実行され、
積和演算結果ｈ₀ ¹（ｗ；２）３５０がデータメモリ１１
０に書き込まれる。

【００４５】次に、加減算手続き３９４を積和演算手続
き３９２の演算結果を用いて実行する。スイッチ３０１
は加減算入力データｈ₀ ^r（ｓ；２^r ）３６０−２とし
て、ｒ＝１のときは積和演算ステップの積和演算結果３
５０を用い、それ以外は加算ステップ３２０、減算ステ
ップ３３０の出力結果３７０−１及び３７０−２を用い
ることを示している。第１回目から第（ｌｏｇ₂Ｎ−
１）回目までの第ｒ回の加算ステップ３２０と減算ステ
ップ３３０は、一方の入力として加減算入力データｈ₁ ^r
（ｓ；２^r ）３６０−１を用い、もう一方の入力として
加減算入力データｈ₀ ^r（ｓ；２^r ）３６０−２を用い
て、それぞれの演算を行い、加減算結果ｈ₀ ^r+1（ｓ；２
^r+1 ）３７０−１、減算結果ｈ₀ ^r+1（２^r+1 −１−ｓ；
２^r+1 ）３７０−２をデータメモリ１１０に書き込む。
スイッチ３０２は第（ｌｏｇ2 Ｎ−１）回目の加算結果
３７０−１、減算結果３７０−２のみは、逆ＤＣＴ変換
の結果である原画像データ３８０として、出力端子１０
２から外部に出力することを示している。

【００４６】以上の処理手順により、合計でＮ個の、１
次元Ｎ次逆ＤＣＴ演算結果が得られることになる。

【００４７】図４は本発明によるＤＣＴ、逆ＤＣＴ演算
装置の第２の実施例を示すブロック図である。図４にお
いて、本実施例のＤＣＴ、逆ＤＣＴ演算装置は、原画像
データ，ＤＣＴ変換結果，演算途中結果，ＤＣＴ変換係
数，逆ＤＣＴ変換係数を記憶するデータメモリ４１０−
１、データメモリ４１０−２と、データメモリ４１０−
１、データメモリ４１０−２に外部からデータを与える
入力端子４０１と、データメモリ４１０−１の読みだし
及び書き込みアドレスを指定するアドレス発生手段４２
０−１と、データメモリ４１０−２の読みだし及び書き
込みアドレスを指定するアドレス発生手段４２０−２
と、データメモリ４１０−１、データメモリ４１０−２
から読み出されたデータを受け取る加算器入力バス４３
０−１及び積和演算器入力バス４３０−２と、加算器入
力バス４３０−１から２つの入力データを受け取り加算
または減算を行う加算器４４０と、積和演算器入力バス
４３０−２から２つの入力データを受け取り積和演算を
行う積和演算器４５０と、加算器４４０の出力もしくは
積和演算器４５０の出力を受け取り、データメモリ４１
０−１またはデータメモリ４１０−２への書き込みを行
う出力バス４６０−１及び４６０−２と、ＤＣＴ変換結
果、あるいはＤＣＴ逆変換の結果の原画像データを外部
へ出力する外部出力端子４０２からなっている。図４の
ＤＣＴ，逆ＤＣＴ演算装置においては、データメモリ，
アドレス発生回路，入力バス，出力バスを全て２重化す
ることで、加算器４４０と積和演算器４５０が並列に動
作できるようにしている。

【００４８】この実施例のＤＣＴ，逆ＤＣＴ演算装置を
用いて、本発明の２次元Ｎ次ＤＣＴ演算を次のようにし
て行う。２次元Ｎ次ＤＣＴは１次元Ｎ次ＤＣＴを２回介
繰り返すことにより実行することが出来る。従って、ま
ず１次元Ｎ次ＤＣＴの演算方法を説明する。

【００４９】１次元Ｎ次ＤＣＴは、図４のＤＣＴ，逆Ｄ
ＣＴ演算装置においても、図２の演算方法に従って加減
算手続き２９２と積和演算手続き２９４を用いて行う。
以下図２と図４を用いて説明する。外部入力端子４０１
より与えられた原画像データ２４０は、データメモリ４
１０−１に記憶される。この原画像データ２４０に対
し、加減算手続き２９２における、加算ステップ２２０
を、上記の図２の説明のように実行する。ただし、デー
タメモリ１１０のかわりにデータメモリ４１０−１、ア
ドレス発生手段１２０のかわりにアドレス発生手段４２
０−１、入力バス１３０のかわりに加算器入力バス４３
０−１、加算器１４０のかわりに加算器４４０を用い
る。また、全ての減算結果２６０と、最後の加算結果２
５０はデータメモリ４１０−２へ記憶させるものとす
る。データメモリ４１０−２に記憶された減算結果２６
０、加算結果２５０に対して、積和演算手続き２９４に
より積和演算ステップ２３０−１、積和演算ステップ２
３０−２を上記の図２の説明のように実行する。ただ
し、データメモリ１１０のかわりにデータメモリ４１０
−２、アドレス発生手段１２０のかわりにアドレス発生
手段４２０−２、入力バス１３０のかわりに積和演算器
入力バス４３０−２、積和演算器１５０のかわりに積和
４５０を用いる。また、ＤＣＴ変換結果は、最初のＮ回
の１次元Ｎ次ＤＣＴ演算の場合は、外部出力端子４０２
から外部へ出力するかわりにもう一度データメモリ４１
０−１に記憶される。

【００５０】図５は、図４のＤＣＴ，逆ＤＣＴ演算装置
での２次元Ｎ次ＤＣＴの演算方法におけるタイミングを
示すタイミング図である。図５において、２次元Ｎ次Ｄ
ＣＴは１次元Ｎ次ＤＣＴ５１０を２Ｎ回繰り返すことで
実行されている。１次元Ｎ次ＤＣＴは、図２の説明で述
べたように加減算手続き２９２，積和演算手続き２９４
から構成されている。図４のＤＣＴ、逆ＤＣＴ演算装置
において、加算器４４０、積和演算器４５０が並列に動
作できるので、図５に示したように、ある１次元Ｎ次Ｄ
ＣＴの積和演算手続き２９４とその次の繰り返しの１次
元Ｎ次ＤＣＴの加減算手続き２９２とは並列に実行する
ことができる。このように、本発明の２次元Ｎ次ＤＣＴ
の演算方法では、各１次元Ｎ次ＤＣＴの演算処理をオー
バーラップさせて、加算器４４０と積和演算器４５０で
並列処理を行っている。

【００５１】次に、図４のＤＣＴ，逆ＤＣＴ演算装置を
用いて、本発明の２次元Ｎ次逆ＤＣＴの演算を次のよう
にして行う。２次元Ｎ次逆ＤＣＴは１次元Ｎ次逆ＤＣＴ
を２Ｎ回繰り返すことにより実行することが出来る。１
次元Ｎ次逆ＤＣＴは、図４のＤＣＴ，逆ＤＣＴ演算装置
においても、図３の演算方法に従って積和演算手続き３
９２と加減算手続き３９４により行う。２次元Ｎ次ＤＣ
Ｔの場合と同様に、ある１次元Ｎ次逆ＤＣＴの加減算手
続き３９４とその次の繰り返しの１次元Ｎ次逆ＤＣＴの
積和演算手続き３９２とは並列に実行することが出来
る。このように、本発明の２次元Ｎ次逆ＤＣＴの演算方
法では、各１次元Ｎ次逆ＤＣＴの演算処理をオーバーラ
ップさせて、加算器４４０と積和演算器４５０で並列処
理を行っている。

【００５２】図６は本発明のＤＣＴ並びに逆ＤＣＴ演算
装置における１次元Ｎ次ＤＣＴ、逆ＤＣＴの演算方法の
効果を示すため、本発明による１次元８次ＤＣＴ、逆Ｄ
ＣＴの演算手順と演算量、及び１次元Ｎ次ＤＣＴ，逆Ｄ
ＣＴの演算量を、従来技術その１，従来技術その２の例
であるＦＣＴ法と比較したものである。同図において、
従来技術その２、及び本発明においては、１次元８次Ｄ
ＣＴの演算手順は同図に記載された手順を上から下に行
い、１次元８次逆ＤＣＴの演算手順は同図に記載された
手順を下から上に行うものとする。また、演算量は積和
演算、加減算、乗算を単位演算として、これらの単位演
算の実行回数で数えている。これから、以下のことが分
かる。（１）演算量は、従来技術その１が６４回、従来技術そ
の２が４２回、本発明が３６回であり、本発明が最も少
ない。（２）従来技術その２では、演算手順が加減算手続き、
乗算手続きの繰り返しになっているが、本発明の演算方
法では、積和演算手続きと加減算手続きを実行するだけ
でよく、演算手順が簡単である。（３）従来技術その２では、乗算が一つのデータに繰り
返し３回実行されるのに対し、本発明の演算方法では一
つのデータに１度しか積和演算が行われないので、乗算
実行時の丸め誤差の影響が本発明の演算方法の方が少な
くて済む。

【００５３】このように、本発明のＤＣＴ，逆ＤＣＴ演
算方法は１次元８次ＤＣＴ，逆ＤＣＴに対して、従来技
術その１、従来技術その２に比べてすぐれた性能を有す
る。また、一般のＮ次の１次元ＤＣＴ，逆ＤＣＴについ
ては図６から分かるように、、Ｎが１６以上では、本発
明による演算方法より従来技術２の方が演算量が少な
く、上記（１）は成り立たないことが分かる。しかし、
上記（２），（３）については、Ｎが増えるほど本発明
による演算方法の方が有利になる。

【００５４】更に、本発明によるＤＣＴ，逆ＤＣＴ演算
装置は、加算器の積和演算器が並列動作できるようにす
ることにより、２次元Ｎ次ＤＣＴまたは２次元Ｎ次逆Ｄ
ＣＴを実行するさい、１次元Ｎ次ＤＣＴまたは逆ＤＣＴ
の加減算手続きと積和演算手続きを並列に処理できると
いう優れた性質を有しており、これにより更に高速なＤ
ＣＴ，逆ＤＣＴ演算を実現することが出来る。

【００５５】

【発明の効果】以上のように、本発明のＤＣＴ及び逆Ｄ
ＣＴ演算装置は以下のような効果を有する。（１）データメモリ，アドレス発生手段，加算器，積和
演算器をバスで接続した柔軟な構成をしているため、高
能率符号化の他の処理も行うことができる。（２）同一の演算器構成で、任意の次数のＤＣＴ及び逆
ＤＣＴを実行できる。（３）従来技術その２と比べると、少ないハードウェア
量で、より高性能なＤＣＴ及び逆ＤＣＴ演算装置を構成
できる。（４）以下に述べるように、本演算装置上のＤＣＴ，逆
ＤＣＴ演算方法は、演算量が少なく、演算手順が簡単な
ため、高速にＤＣＴ，逆ＤＣＴを実行できる。

【図面の簡単な説明】

【図１】本発明のＤＣＴ，逆ＤＣＴ演算装置の一実施例
を示すブロック図である。

【図２】図１のＤＣＴ，逆ＤＣＴ演算装置における１次
元Ｎ次ＤＣＴの演算方法を示す流れ図である。

【図３】図１のＤＣＴ，逆ＤＣＴ演算装置における１次
元Ｎ次逆ＤＣＴの演算方法を示す流れ図である。

【図４】本発明のＤＣＴ，逆ＤＣＴの演算装置の第２の
実施例を示すブロック図である。

【図５】図４のＤＣＴ，逆ＤＣＴ演算装置での２次元Ｎ
次ＤＣＴの演算方法におけるタイミングを示すタイミン
グ図である。

【図６】本発明の効果を示す従来技術との比較図であ
る。

【図７】図７は従来技術その２におけるＤＣＴ，逆ＤＣ
Ｔ演算装置の構成を示すブロック図である。

【符号の説明】

１０１入力端子１０２出力端子１１０データメモリ１２０アドレス発生回路１３０入力バス１４０加算器１５０積和演算器１６０出力バス２０１スイッチ２０２スイッチ２１０加算ステップ２２０減算ステップ２３０−１積和演算ステップ２３０−２積和演算ステップ２４０原画像データ２５０加減算入力データ２６０加算結果２７０減算結果２８０ＤＣＴ変換結果２９０−１ＤＣＴ変換係数２９０−２ＤＣＴ変換係数２９２加減算手続き２９４積和演算手続き３０１スイッチ３０２スイッチ３１０−１積和演算ステップ３１０−２積和演算ステップ３２０加算ステップ３３０減算ステップ３４０ＤＣＴ演算結果３５０積和演算結果３６０−１加減算入力データ３６０−２加減算入力データ３７０−１加算結果３７０−２減算結果３８０原画像データ３９０−１逆ＤＣＴ変換係数３９０−２逆ＤＣＴ変換係数３９２積和演算手続き４０１外部入力端子４０２外部出力端子４１０−１データメモリ４１０−２データメモリ４２０−１アドレス発生手段４２０−２アドレス発生手段４３０−１加算器入力バス４３０−２積和演算器入力バス４４０加算器４５０積和演算器４６０−１出力バス４６０−２出力バス５１０１次元Ｎ次ＤＣＴ７１０〜７４０加算装置７６０〜７８０乗算装置

Claims

【特許請求の範囲】

【請求項１】（Ａ）原画像データ，演算途中結果，ＤＣ
Ｔ変換結果，ＤＣＴ変換係数，逆ＤＣＴ変換係数を記憶
するデータメモリ、（Ｂ）前記データメモリの読みだし
及び書き込みアドレスを指定するアドレス発生手段、
（Ｃ）前記アドレス発生手段の指定する前記データメモ
リの複数のアドレスから読み出されたデータ間の加算ま
たは減算を行い、前記加算結果を前記アドレス発生手段
の指定する前記データメモリのアドレスに書き込む加算
器、（Ｄ）前記アドレス発生手段の指定する前記データ
メモリの複数のアドレスから読み出されたデータ間の積
和演算を行い、前記積和演算結果を前記アドレス発生手
段の指定する前記データメモリのアドレスに書き込む積
和演算器、を有することを特徴とするＤＣＴ及び逆ＤＣ
Ｔ演算装置。
【請求項２】請求項１記載のＤＣＴ及び逆ＤＣＴ演算
装置におけるＮ次（Ｎは２の正のべき乗で表される任意
の正整数）の１次元ＤＣＴの演算方法であって、（Ａ）
０から（Ｍ−１）までの引数を持つＭ個（Ｍは２からＮ
までの２の正のべき乗で表される任意の正整数）のデー
タを入力として持ち、前記アドレス発生手段の指定によ
り、前記入力データのうち引数の和がＭである二つの前
記入力データの組を順次前記データメモリから読みだ
し、読み出された二つの前記入力データ間の加算を前記
加算器で行い、１から（Ｍ／２−１）までの引数を持つ
Ｍ／２個の加算結果を前記データメモリに書き込む加算
ステップ、（Ｂ）０から（Ｍ−１）までの引数を持つＭ
個のデータを入力として持ち、前記アドレス発生手段の
指定により、前記入力データのうち引数の和がＭである
二つの前記入力データの組を順次前記データメモリから
読み出し、読み出された二つの前記入力データ間の減算
を前記加算器で行い、１から（Ｍ／２−１）までの引数
を持つＭ／２個の減算結果を前記データメモリに書き込
む減算ステップ、（Ｃ）０から（Ｌ−１）までの引数を
持つＬ個（Ｌは２からＮ／２までの２の正のべき乗で表
される任意の正整数）のデータと、Ｌ²個のＤＣＴ変換
係数とを入力として持ち、前記アドレス発生手段の指定
により、前記入力データと前記入力ＤＣＴ変換係数を順
次前記データメモリから読みだし、読み出された前記入
力データと前記入力ＤＣＴ変換係数間の積和演算を前記
積和演算器で行い、Ｌ個のＤＣＴ変換結果を出力する第
１の積和演算ステップ、（Ｄ）０から１までの引数を持
つ２個のデータと、４個のＤＣＴ変換係数とを入力とし
て持ち、前記アドレス発生手段の指定により、前記入力
データと前記入力ＤＣＴ変換係数を順次前記データメモ
リから読みだし、読み出された前記入力データと前記入
力ＤＣＴ変換係数間の積和演算を前記積和演算器で行
い、２個のＤＣＴ変換結果を出力する第２の積和演算ス
テップ、を有し、（ｌｏｇ₂Ｎ−１）回の前記加算ステップと（ｌｏｇ₂
Ｎ−１）回の前記減算ステップを行う加減算手続きと、
（ｌｏｇ₂Ｎ−１）回の前記第１の積和演算ステップと
１回の前記第２の積和演算ステップを行う積和演算手続
とにより１次元Ｎ次ＤＣＴ演算を実行し、前記加減算手続器においては、第１回目の前記加算ステップおよび第１回目の前記減算
ステップの前記入力データとして、０から（Ｎ−１）ま
での引数を持つＮ個の前記原画像データを用い、第ｍ回目（ｍは２から（ｌｏｇ₂Ｎ−１）までの任意の
正整数）の前記加算ステップおよび第ｍ回目の前記減算
ステップの前記入力データとして第（ｍ−１）回目の前
記加算ステップの前記加算結果を用い、前記積和演算手続においては、第ｎ回目（ｎは１から（ｌｏｇ₂Ｎ−１）までの任意の
正整数）の前記第１の積和演算ステップの前記入力デー
タとして、第ｎ回目の前記減算ステップの前記減算結果
を用い、前記第２の積和演算ステップの入力データとして第（ｌ
ｏｇ₂Ｎ−１）回目の前記加算ステップの加算結果を用
い、第１から第（ｌｏｇ₂Ｎ−１）までの前記第１の積和演
算ステップと前記第２の積和演算ステップの積和演算の
結果として、合計でＮ個の前記ＤＣＴ変換経過を得るこ
とを特徴とする１次元Ｎ次ＤＣＴの演算方法。
【請求項３】請求項１記載のＤＣＴ及び逆ＤＣＴ演算
装置におけるＮ次の１次元ＤＣＴの演算方法であって、
（Ａ）０からＮ−１までの引数を持つＮ個の前記ＤＣＴ
変換結果のうちで、引数Ｎ／２ⁿで割った余りがＮ／２
ⁿ⁺¹である引数を持つ２ⁿ個の前記ＤＣＴ変換結果と、
２²ⁿ個の前記逆ＤＣＴ変換係数とを入力として持ち、前
記アドレス発生手段の指定により、前記入力ＤＣＴ変換
経過と、前記入力逆ＤＣＴ変換係数を順次データメモリ
から読み出し、読み出された前記入力ＤＣＴ変換結果と
前記入力逆ＤＣＴ変換係数間の積和演算を前記第１の積
和演算器で行い、０から（２ⁿ−１）までの引数を持つ
２ⁿ個の積和演算結果を出力する第１の積和演算ステッ
プ、（Ｂ）前記ＤＣＴ変換結果のうちで、引数が０とＮ
／２である２個の前記ＤＣＴ変換結果と、４個の前記逆
ＤＣＴ変換係数とを入力として持ち、前記アドレス発生
手段の指定により、前記入力データと前記入力逆ＤＣＴ
変換係数を順次データメモリから読み出し、読み出され
た前記入力データと前記入力逆ＤＣＴ変換係数間の積和
演算を前記積和演算器で行い、０から１までの引数を持
つ２個の積和演算結果を出力する第２の積和演算ステッ
プ、（Ｃ）０から（Ｌ−１）までの引数を持つＬ個のデ
ータ二組を入力として持ち、前記アドレス発生手段の指
定により、二組の前記入力データのうち、引数が同じで
ある二つの前記入力データの組を順次前記データメモリ
から読みだし、読み出された二つの前記入力データ間の
加算を前記加算器で行い、Ｌ個の加算結果を前記データ
メモリに書き込む加算ステップ、（Ｄ）０から（Ｌ−
１）までの引数を持つＬ個のデータ二組を入力として持
ち、前記アドレス発生手段により、二組の前記入力デー
タのうち、引数が同じである二つの前記入力データの組
を順次前記データメモリから読み出し、読み出された二
つの前記入力データ間の減算を前記加算器で行い、Ｌ個
の減算結果を前記データメモリに書き込む減算ステッ
プ、を有し、（ｌｏｇ₂Ｎ−１）回の第１の積和演算ステップと１回
の第２の積和演算ステップを行う積和演算手続と、（ｌ
ｏｇ₂Ｎ−１）回の加算ステップと（ｌｏｇ₂Ｎ−１）
回の減算ステップを行う加減算手続きとにより１次元Ｎ
次逆ＤＣＴを実行し、前記積和演算手続きにおいては、第ｎ回目の第１の積和演算ステップで、前記２ⁿ個の逆
ＤＣＴ変換結果を入力として用い、前記加減手続きにおいては、第１回目の前記加算ステップおよび第１回目の前記減算
ステップの二組の前記入力データとして、前記第２の積
和演算ステップの前記積和演算結果と第１回目の前記第
１の積和演算ステップの前記積和演算結果とを用い、第ｍ回目の前記加算ステップおよび第ｍ回目の前記減算
ステップのそれぞれの二組の前記入力データとして第
（ｍ−１）回目の前記加算ステップの前記加算結果及び
第（ｍ−１）回目の前記減算ステップの前記減算結果
と、第ｍ回目の前記第１の積和演算ステップの前記積和
演算結果とを用い、第（ｌｏｇ₂Ｎ−１）回目の前記加算ステップの前記加
算結果および第（ｌｏｇ₂Ｎ−１）回目の前記減算ステ
ップの前記減算結果として、Ｎ個の原画像データを得る
ことを特徴とする１次元Ｎ次逆ＤＣＴの演算方法。
【請求項４】請求項１記載のＤＣＴ及び逆ＤＣＴ演算
装置におけるＮ次の２次元ＤＣＴ演算方法であって、請求項２記載の１次元Ｎ次ＤＣＴ演算方法を２Ｎ回繰り
返すことにより２次元Ｎ次ＤＣＴ演算を行い、前記加算
器と前記積和演算器を並列動作させることにより、ある前記１次元Ｎ次ＤＣＴ演算の前記積和演算手続き
と、その次の繰り返しの前記１次元Ｎ次ＤＣＴ演算の加
減算手続きとを並列に処理することを特徴とする２次元
Ｎ次ＤＣＴ演算方法。
【請求項５】請求項１記載のＤＣＴ及び逆ＤＣＴ演算
装置におけるＮ次の２次元逆ＤＣＴ演算方法であって、
請求項３記載の１次元Ｎ次逆ＤＣＴ演算方法を２Ｎ回繰
り返すことにより２次元Ｎ次逆ＤＣＴ演算を行い、前記
加算器と前記積和演算器を並列動作させることにより、ある前記１次元Ｎ次逆ＤＣＴ演算の前記加減算手続き
と、その次の繰り返しの前記１次元Ｎ次逆ＤＣＴ演算の
前記積和演算手続きとを並列に処理することを特徴とす
る２次元Ｎ次逆ＤＣＴ演算方法。