JP2003067360A - 積和演算方法および積和演算装置 - Google Patents

Abstract

(57)【要約】 【課題】直交変換処理において演算量の多い積和演算を
簡素化する。 【解決手段】データ記憶手段１から積和演算単位として
８個のデータを切り出すデータ選択手段２と、切り出さ
れた８個のデータのそれぞれが零か非零かを判断する零
・非零判定手段３と、その８個のデータの非零要素の存
在する位置に基づき、ＣＰＵ６で生成されるデータアド
レスに対し、前記非零要素のみを連続的に読み出し可能
となるようなアドレス変換を行うアドレス変換手段４ａ
と、同じく、ＣＰＵ６で生成される変換係数アドレスに
対し、前記非零要素に対応する変換係数の読み出しを可
能とするようなアドレス変換を行うアドレス変換手段４
ｂとを有する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、音情報、画像情報、映
像情報などの情報圧縮、また符号化などの信号処理に用
いられる直交変換処理を高速に行うための積和演算方法
および積和演算装置に関する。

【０００２】

【従来の技術】情報機器の高機能化により、情報の符号
化、圧縮に欠かせない直交変換処理は、より重要度を増
している。また、情報機器の汎用性の面から、また技術
革新の速さへの対応のために、より汎用的なハードウェ
ア、また、より一般的なデータ構造に対応できる直交変
換処理方法が求められている。

【０００３】以下は具体的な説明のために、広く用いら
れている静止画符号化技術であるＪＰＥＧ処理を例にと
る。ＪＰＥＧは、離散コサイン変換（ＤＣＴ）、量子
化、ランレングス符号化、ハフマン符号化などを技術要
素として含む画像圧縮、符号化方法である。図６から図
８はこれらを簡単に説明するためのものである。

【０００４】図６は、画像データＤ１からＪＰＥＧ処理
の単位となるデータブロックＡ１，Ａ２，Ａ３，…の切
り出しを模式的に示すものである。ＪＰＥＧ処理は、Ｎ
とＭを自然数とし、８Ｎ×８Ｍのサイズのデータブロッ
クに対して行われる。８Ｎ×８Ｍのデータブロックは、
データを間引かれて、最終的に８×８のサイズとなり、
ＪＰＥＧ処理そのものは、全て８×８のデータブロック
に対して行われる。そのため、以降は８×８のデータブ
ロックを例にして説明する。

【０００５】具体的な例として、あるデータブロックの
データが図７（ａ）のようなものであるとする。ＪＰＥ
Ｇ処理の第１ステップは、これにＤＣＴ処理を行うもの
である。ＤＣＴ処理は直交変換の一種であり、画像デー
タを周波数領域に変換するものである。ＤＣＴ処理は数
式で表現すると、

【０００６】

【数１】

【０００７】のように表される。この（１）式におい
て、Ｐは画像データであり、Ｃは変換係数、ｉ、ｊはそ
れぞれ横方向、縦方向の画素の位置を示す。また、ｍ，
ｎはそれぞれ横方向、縦方向の周波数成分を示す。ま
た、Ｂは本来、符号無しデータである画素データを計算
の都合上、符号有りデータへ変換するためのバイアス値
である。上記の演算によって得られるＳが、元画像を周
波数領域へ変換したものである。

【０００８】この処理により、図７（ａ）のデータは、
図７（ｂ）のデータへ変換される。画像の復号時には、
このデータに対し、以下に示す（２）式のような逆ＤＣ
Ｔ処理を行うことにより、元のデータが復元される。

【０００９】

【数２】

【００１０】ＪＰＥＧ処理における次のステップは、量
子化である。人間の視覚特性は周波数の低いデータに対
して敏感であり、逆に周波数の高いデータに対して鈍感
である。この特性を利用し、周波数の低い領域のデータ
をより細かなスケールで表現し、逆に周波数の高い領域
のデータをより粗いスケールで表現することにより、全
体としてのデータ量を削減することができる。このよう
な操作をスカラー量子化と呼ぶ。

【００１１】仮に図７（ｄ）のような量子化スケールを
用いた場合、図７（ｂ）のデータは、図７（ｃ）のデー
タに量子化される。この図７（ｃ）より明らかなよう
に、零となる要素の数が増えている。

【００１２】ＪＰＥＧ処理における次のステップは、ラ
ンレングス符号化である。図８および図９はこれを説明
するためのものである。まず最初に８×８の６４個の要
素は、図８（ａ）に示すようなジグザグスキャン順序
で、図８（ｂ）に示すような１列のデータへ並べ替えら
れる。これは、より最初の方に次元的な意味での低周波
側のデータがあり、後に行くほど高周波側のデータが並
べられることになる。

【００１３】図９は、図７（ｃ）のデータを並べ替えた
例であり、図９（ａ）のデータは、図９（ｂ）のように
並べ替えられる。実際のランレングス符号化では、この
並びの中の零の連鎖をさらに符号化する。たとえば、図
９（ｃ）に示すように、ある位置以降のデータが全て零
である場合、その零の連鎖の全てを、一つのデータ終端
記号（Ｅｎｄ Ｏｆ Ｂｌｏｃｋ、略してＥＯＢ）で置
き換える。さらに、それ以外の零もそれぞれ記号に置き
換えられるのであるが、本発明の要点からは離れるので
省略する。

【００１４】ＪＰＥＧにおける次のステップはハフマン
符号化であるが、これも本発明の要点から離れるので省
略する。

【００１５】ところで、ＪＰＥＧ全体の処理の中で、特
にＤＣＴ処理は非常に大量の演算を必要とする。つま
り、この部分を高速化することが、ＪＰＥＧ処理全体の
高速化につながる。以下、ＤＣＴ演算を例にとり、その
高速化について説明する。

【００１６】ＤＣＴ演算は前述の（１）式に示したよう
なものであるが、これは以下に示すような２段階の１次
元処理として実行される。

【００１７】

【数３】

【００１８】

【数４】

【００１９】この計算を、より分かりやすくするため
に、変換係数を

【００２０】

【数５】

【００２１】とし、行列演算の形で書くと以下のような
形となる。

【００２２】

【数６】

【００２３】

【数７】

【００２４】これは模式的に書くと、図１０（ａ），
（ｂ）のように、行方向の演算処理と列方向の演算処理
（処理方向それぞれ矢印で示す）を、行または列のいず
れかから順次実行すると言うことである。ここで重要で
あるのは、（３）式と（４）式の実行順序についての自
由度があると言うことである。原理的に言えば、演算が
有限精度で行われることによる誤差を除き、最終的な結
果は、この実行順序に依存しない。

【００２５】ＤＣＴ演算の高速化は、このような行列演
算を高速化することと同等になる。このような高速化に
おいて、従来例において用いられる方法は以下のような
ものがある。

【００２６】特開平４−７００６０において用いられて
いる手法は、データブロック内の全てのデータが零の
時、そのＤＣＴ演算をスキップするというものである。

【００２７】上の式から明らかであるように、このよう
な条件では、演算結果は全て零になるので、演算を省略
することが可能である。このような条件は、特にプログ
レッシブ型と呼ばれる時に成立する可能性が高い。

【００２８】特開平４−１３７９７５において用いられ
ている手法は、４並列演算が可能なハードウェアにおい
て、その４要素が零の時に演算をスキップすると言うよ
うなものである。

【００２９】ＤＣＴ演算で用いられるデータの精度は１
６ビットであることが多く、６４ビットの演算レジスタ
をもつハードウェアにおいては、４つのデータを同時に
処理することができる。この並列演算により処理を高速
化し、さらに、結果が自明であるデータが全て零の時に
演算を省略することにより、より高速化を行うものであ
る。この手法は特開平４−２０００７９においても述べ
られている。

【００３０】また、特開平４−２２００８１において用
いられている手法は、上述の特開平４−７００６０と類
似した手法であるが、データブロック内のデータが直流
成分、つまり、（０、０）要素のみの場合に対応したも
のである。このとき、ＤＣＴ演算結果は、全てのデータ
が同じ値となり、１つのデータの演算を行うだけで、演
算結果を得ることができる。

【００３１】また、特開平１０−６３６４６で用いられ
ている手法は、データの状態に対応した複数の演算手段
を持ち、ＥＯＢの位置により、それらの演算手段の内か
ら最適なものを選択することにより演算を高速化するも
のである。

【００３２】図１１はこれを簡単に説明するものであ
る。図１１（ａ）に示す位置にＥＯＢが現れたと仮定す
ると、先に説明したように、それ以降のデータは全て零
である。逆に、それ以前のデータは零ではない可能性が
高い。つまり、零ではないデータの位置を塗りつぶし、
零であるデータの位置を塗りつぶさないで表示すると、
ある点にＥＯＢが現れた場合の零、非零のデータの分布
は、図１１（ｂ）のようなものである可能性が高い。こ
のデータの偏りに対応する演算手段を複数用意し、最も
適切な演算手段を選択することにより、ＤＣＴ演算を高
速化することができる。

【００３３】特開平１０−３２２６９９は、上述の例と
類似した考え方であるが、予めデータ領域を２つの領域
に分割し、データが零ではない可能性が高い低周波領域
においては常に高速ＤＣＴアルゴリズムを用いた演算を
行い、それ以外の領域では通常のＤＣＴを行うものであ
る。これは図１２（ａ）に示すように、たとえば、デー
タ領域を４つに分割し、左上の領域Ｚ１は常にデータが
あると仮定し、図１２（ｂ）に示すように、その左上の
領域はすべて処理対象とし、それ以外の領域は、個別に
零、非零の判断と処理を行うものである。

【００３４】これは、処理をある程度固定することによ
り、先の従来例で必要であった条件判断のための負荷を
軽減するものである。

【００３５】特開平１１−４１６０１は、以上で説明し
た４並列演算、複数の演算手段、またＥＯＢの位置によ
る条件判断の全てを用いるものである。

【００３６】

【発明が解決しようとする課題】先に述べたような従来
例は、それぞれ有効なものであるが、以下に述べるよう
な課題は残る。

【００３７】特開平４−７００６０および特開平４−２
２００８１に述べられているのは、データが特殊な状態
である場合のみの高速化であり、より一般的な条件での
有効性は劣る。

【００３８】特開平４−１３７９７５および特開平４−
２０００７９に述べられているような４並列演算ハード
ウェアを基本とするものは、４個のデータの整列、分解
の負荷、また、４個のデータが零か非零かの判断の負荷
が大きい。また、４並列演算処理の効果は非常に大きな
ものであるが、このような機能を持つハードウェア以外
においては有効なものではない。

【００３９】具体的な例として、図１３（ａ）のような
データを仮定する。図中の塗りつぶした部分が非零要素
であるとする。この場合、４並列演算を用いると、図１
３（ｂ）の塗りつぶした位置の要素につき演算を行う必
要がある。勿論、並列演算の効果により、演算処理時間
の増大は少ないと考えられるが、同時に、単純な処理に
比較した処理の高速化の効果もない。また、データの
零、非零の判断、及び、データの整列、分解の処理が付
加的に必要となる。

【００４０】特開平１０−６３６４６、および、特開平
１０−３２２６９９は複数の演算手段を持つものであ
り、処理の複雑さが増す。またＥＯＢによる条件判断
は、必ずしも有効なものではない。たとえば、上と同じ
図１４（ａ）のようなデータを仮定する。そうすると、
ＥＯＢによる判断は、図１４（ｂ）のようなデータを仮
定することになり、非常に冗長な演算を行う必要がでて
くる。特開平１１−４１６０１も以上と同様である。

【００４１】以上のように従来例における直交変換処理
の高速化手法は、特殊なデータの場合のみへ対応したも
のであり、また、特定のハードウェア構造を仮定したも
のである。また、一部は非常に複雑な構造を必要とする
ものである。

【００４２】本発明は、以上の課題を解決し、音情報、
画像情報、映像情報などの情報圧縮、また符号化などの
信号処理に用いられる直交変換処理を高速に行うための
積和演算方法および積和演算装置を提供することを目的
としている。

【００４３】

【課題を解決するための手段】上述した目的を達成する
ため、本発明の積和演算方法は、積和演算単位を構成す
るＮ個のデータを所定のアドレス順で順次読み出して積
和演算を行う積和演算方法において、前記Ｎ個のデータ
のそれぞれについて零か非零かを判断し、そのＮ個のデ
ータにおける非零要素の存在する位置を示す情報に基づ
いて、前記アドレスに対し、前記非零要素のみを連続的
に読み出し可能となるようなアドレス変換を行い、その
変換後のアドレスによって読み出されたデータに対して
順次積和演算を行うようにしている。

【００４４】この積和演算方法において、前記Ｎ個のデ
ータにおける非零要素の存在する位置に基づくアドレス
変換は、積和演算を行うに必要な変換係数を読み出すた
めのアドレスに対しても行い、その変換後のアドレスに
よって前記非零要素に対応する変換係数の読み出しを行
うようにしている。

【００４５】また、本発明の積和演算装置は、積和演算
単位を構成するＮ個のデータを所定のアドレス順で順次
読み出して積和演算を行う積和演算装置において、処理
対処となるデータが記憶されるデータ記憶手段と、この
データ記憶手段に記憶された処理対象となるデータか
ら、積和演算単位となるＮ個のデータを切り出すデータ
選択手段と、このデータ選択手段で切り出されたＮ個の
データのそれぞれが零か非零かを判断する零・非零判定
手段と、この零・非零判定結果において非零要素の存在
する位置を示す情報に基づいて、前記アドレスに対し、
前記非零要素のみを連続的に読み出し可能となるような
アドレス変換を行うアドレス変換手段とを有し、このア
ドレス変換手段によるアドレス変換後のアドレスによっ
て読み出されたデータに対して前記積和演算手段により
積和演算を行うようにしている。

【００４６】このような積和演算装置において、前記Ｎ
個のデータにおける非零要素の存在する位置に基づいた
アドレス変換を行うアドレス変換手段は、前記Ｎ個のデ
ータを順次読み出すためのアドレスに対してアドレス変
換を行うデータアドレス変換手段と、前記変換係数を読
み出すためのアドレスに対してアドレス変換を行う変換
係数アドレス変換手段を設け、前記データを読み出すた
めのアドレスに対しては、前記データアドレス変換手段
により前記非零要素のみを連続的に読み出し可能となる
ようなアドレス変換を行い、前記変換係数を読み出すた
めのアドレスに対しては、前記変換係数アドレス変換手
段により前記非零要素に対応する変換係数の読み出しが
可能となるようなアドレス変換を行うようにしている。

【００４７】このように本発明は、積和演算単位を構成
するＮ個のデータのそれぞれについて零か非零かを判断
し、そのＮ個のデータにおける非零要素の存在する位置
を示す情報に基づき、たとえば、ＣＰＵやＤＳＰ（Digi
tal Signal Processor）などの積和演算処理手段で生成
されるアドレスに対し、前記非零要素のみを連続的に読
み出し可能となるようなアドレス変換を行い、そのアド
レス変換後のアドレス順で読み出されたデータに対して
順次積和演算を行うようにしている。

【００４８】このように、ＣＰＵやＤＳＰなどが生成す
る連続的なアドレス（積和演算単位として切り出された
Ｎ個のデータを、たとえば、データ位置０から順に１，
２，３，…とアクセスするためのアドレス）を、非零要
素のデータのみを順次アクセス可能なアドレスに変換し
て、その変換後のアドレス順でデータを読み出して積和
演算を行うようにしている。

【００４９】これにより、ＣＰＵやＤＳＰなどは単に連
続したアドレスによって演算すべきデータを読み出して
積和演算する動作を行うだけで、実際には、疎な状態で
飛び飛びにしか存在しない非零要素のみを次々と連続し
て読み出す動作を行うことになる。したがって、たと
え、積和演算すべき非零要素のデータが疎な状態で散ら
ばって存在していたとしても、その疎な状態の非零要素
を次々と連続的に読み出すことができ、これによって、
直交変換処理に伴う積和演算量を効率よく行うことがで
き、その演算量を大幅に削減することができる。

【００５０】また、そのアドレス変換は、積和演算を行
うに必要な変換係数を読み出すためのアドレスに対して
も行うようにしているので、疎な状態で存在する非零要
素のデータに対応する変換係数のみを順次アクセスする
ことができる。

【００５１】

【発明の実施の形態】以下、本発明の実施の形態につい
て説明する。なお、この実施の形態で説明する内容は、
本発明の積和演算方法および積和演算装置についての説
明である。

【００５２】また、本発明の積和演算方法および積和演
算装置は特定の直交変換に適用されるものではないが、
この実施の形態では具体的な説明のために、広く用いら
れている静止画符号化技術であるＪＰＥＧ処理に適用す
る場合を例にとる。

【００５３】本発明の基本的な考え方は、一般的なＣＰ
ＵやＤＳＰにおいては、積和演算すべきデータが疎な状
態で並んで存在する場合の積和演算効率は悪いが、密な
状態に並んで存在するデータについては効率良く積和演
算を行うことができることを利用したものである。

【００５４】このため、本発明では、疎な状態で並んだ
データ位置に依存したアドレス変換処理を行うことによ
り、ＣＰＵやＤＳＰなどの積和演算処理手段におけるソ
フトウエア側からは、あたかも密にデータが分布してい
るかのようにみせるようにしたものである。

【００５５】本発明は大別して2つの処理（これを第1の
処理と第2の処理という）に分けて考えることできる。

【００５６】第1の処理は、処理対象データが記憶され
ているデータ記憶手段から、１つの積和演算単位を構成
するＮ個（ここではＪＰＥＧを例にとっているのでＮ＝
８）データを切り出し、その積和演算単位の中に非零要
素がどのような位置に存在ししているかを判断する非零
要素位置の判断処理である。

【００５７】また、第2の処理は、第1の処理で判断され
た非零要素位置の判断処理に基づき、ＣＰＵやＤＳＰで
生成されるアドレスを変換するアドレス変換処理であ
る。

【００５８】なお、このＣＰＵやＤＳＰで生成されるア
ドレスは、この場合、８個のデータを順次読み出すため
のアドレス（データアドレスという）と、それぞれのデ
ータに対応した変換係数を読み出すためのアドレス（変
換係数アドレスという）が存在し、これらデータアドレ
スと変換係数アドレスをともにアドレス変換する必要が
あるが、これらのアドレス変換処理は同様に考えること
ができるので、まずは、データアドレスについての処理
を説明する。

【００５９】図1は第1の処理を説明するもので、図2は
第2の処理を説明する図である。図1において、データ記
憶手段１に記憶されているデータの中から積和演算単位
として切り出された８個のデータ（上述したように、こ
こではＪＰＥＧを例にしているので１つの積和演算単位
を８個のデータとし、そのデータ位置を「０」〜「７」
で表す）をデータ選択手段２が切り出し、その切り出し
た8個のデータの零・非零判定を零・非零判定手段３に
より行う。

【００６０】ここでは、黒く塗りつぶした部分を非零要
素とし、その非零要素のデータを“１”で表し、また、
零要素のデータを“０”で表すと、この切り出された8
個のデータの零・非零判定結果は、“１００１０１１
０”となる。これを10進数で表すと、「１５０」とな
り、この零・非零判定手段による零・非零判定結果であ
る非零要素の位置を示す情報に基づいてアドレス変換処
理を行なう。

【００６１】まず、この非零要素の位置を示す情報を用
いて、アドレス変換手段がアドレッシングモード設定処
理を行う。このアドレッシングモード設定処理は、アド
レッシングモード選択手段４１における「０」〜「２５
５」の「１５０」の位置をkeyとして、アドレッシング
データ記憶手段４２内のアドレッシングデータを取得す
る処理である。

【００６２】このアドレッシングデータ記憶手段４２に
は、アドレッシングモード選択手段４１の「０」〜「２
５５」のそれぞれに対応したデータ長とそのデータ位置
が記述されていて、たとえば、アドレッシングモード選
択手段４１の「１５０」はデータ長が「４」でそのデー
タ位置が「１，２，４，７」であることを示している。
つまり、アドレッシングモード選択手段４１の「１５
０」は、８個のデータのうち非零要素のデータが４個存
在し、その４個は「０」〜「７」のデータ位置のうち、
「１」，「２」，「４」，「７」の位置に存在している
ことを示している。

【００６３】ちなみに、アドレッシングモード選択手段
４１の「０」は、非零要素が０個であるので、そのデー
タ位置は無いことを意味している。また、アドレッシン
グモード選択手段４１の「２５５」は、８個のデータ全
てが非零要素であって、その８個のデータは「０」，
「１」，「２」，「３」，「４」，「５」，「６」，
「７」のデータ位置に存在していることを示している。

【００６４】このようにして、1つの積和演算単位とし
て切り出された８個のデータに対し、非零要素の数とそ
のデータ位置が設定される。そして、このように設定さ
れた内容に基づいたアドレス変換処理がなされる。この
アドレス変換処理は図２に示すようにして行われる。

【００６５】まず、ベースアドレス記憶手段４３に記憶
されているベースアドレス（積和演算単位として切り出
された８個のデータに対し、最初のアドレスとして設定
されるアドレス）を読み出して、読み出されたベースア
ドレス（０ｘ１０００とする）を、積和演算処理手段と
してのＣＰＵやＤＳＰが、積和演算単位として切り出さ
れた８個のデータを順に読み出すように生成した連続的
なアドレス（これをここでは仮想アドレスと呼び、０ｘ
１０００，０ｘ１００１，０ｘ１００２，…で表す）か
ら引き算する。なお、このＣＰＵやＤＳＰから出力され
る仮想アドレスは仮想アドレス入力手段４４に入力され
ている。

【００６６】たとえば、ベースアドレス０ｘ１０００を
仮想アドレス０ｘ１０００から引き算すると「０」であ
り、その「０」をkeyとして、図1で設定されたアドレッ
シングデータ記憶手段４２のアドレッシングデータ（こ
の場合、データ長が「４」でそのデータ位置が「１，
２，４，７」）を見ると、データ位置として「１」が書
き込まれていて、この「１」をベースアドレス０ｘ１０
００に加算して、物理アドレスとして０ｘ１００１を得
る。この物理アドレス０ｘ１００１は物理アドレス記憶
手段４５に記憶される。

【００６７】同様に、ベースアドレス０ｘ１０００を仮
想アドレス０ｘ１００１から引き算すると「１」であ
り、その「１」をkeyとして、図１で設定されたアドレ
ッシングデータ記憶手段４２のアドレッシングデータ
（同じく、データ長が「４」でそのデータ位置が「１，
２，４，７」）を見ると、この場合、データ位置として
「２」が書き込まれていて、この「２」をベースアドレ
ス０ｘ１０００に加算して、物理アドレスとして０ｘ１
００２を得る。この物理アドレス０ｘ１００２は物理ア
ドレス記憶手段４５に記憶される。

【００６８】また、ベースアドレス０ｘ１０００を仮想
アドレス０ｘ１００２から引き算すると「２」であり、
その「２」をkeyとして、図1で設定されたアドレッシン
グデータ記憶手段４２のアドレッシングデータ（同じ
く、データ長が「４」でそのデータ位置が「１，２，
４，７」）を見ると、この場合、データ位置として
「４」が書き込まれていて、この「４」をベースアドレ
ス０ｘ１０００に加算して、物理アドレスとして０ｘ１
００４を得る。この物理アドレス０ｘ１００４は物理ア
ドレス記憶手段４５に記憶される。

【００６９】さらに、ベースアドレス０ｘ１０００を仮
想アドレス０ｘ１００３から引き算すると「３」であ
り、その「３」をkeyとして、図1で設定されたアドレッ
シングデータ記憶手段４２のアドレッシングデータ（同
じく、データ長が「４」でそのデータ位置が「１，２，
４，７」）を見ると、この場合、データ位置として
「７」が書き込まれていて、この「７」をベースアドレ
ス０ｘ１０００に加算して、物理アドレスとして０ｘ１
００７を得る。この物理アドレス０ｘ１００７は物理ア
ドレス記憶手段４５に記憶される。

【００７０】このような処理によって、ＣＰＵやＤＳＰ
が生成した仮想アドレス０ｘ１０００，０ｘ１００１，
０ｘ１００２，０ｘ１００３に対する物理アドレス０ｘ
１００１，０ｘ１００２，０ｘ１００４，０ｘ１００７
が得られる。

【００７１】この物理アドレス０ｘ１００１，０ｘ１０
０２，０ｘ１００４，０ｘ１００７は、図１に示すデー
タ選択手段２によって切り出された積和演算単位の８個
のデータに対し、それぞれ非零要素に対応する位置を指
し示すアドレスとなる。

【００７２】このように、本発明によれば、積和演算す
べき非零要素のデータが疎な状態で散らばって並んでい
るような場合、上述したようなアドレス変換を行うこと
によって、ＣＰＵやＤＳＰ側からみたとき、疎な状態で
散らばっている非零要素のデータがあたかも密な状態で
連続して並んでいるかのように見えることになる。

【００７３】これは、前述したように、一般的なＣＰＵ
やＤＳＰにおいては、積和演算すべきデータが疎な状態
で並んで存在する場合の積和演算効率は悪いが、密な状
態に並んで存在するデータについては効率よく積和演算
を行うことができることを利用したものであり、このよ
うな連続したデータについて積和演算を行うようなプロ
グラムの設定されたＣＰＵやＤＳＰにとっては極めて都
合のよいものとなる。

【００７４】すなわち、積和演算単位として切り出され
た８個のデータのうち、積和演算すべき非零要素のデー
タが疎な状態でしか存在しない場合でも、上述したアド
レス変換処理を行うことによって、ＣＰＵやＤＳＰは連
続したアドレスによって演算すべきデータを読み出して
積和演算する動作を行うだけで、実際には、疎な状態で
しか存在しない非零要素のみを次々と連続して読み出す
動作を行うことになる。それによって、効率よく積和演
算が行え、その演算量を大幅に削減することができ、高
速な積和演算が可能となる。

【００７５】図3は以上説明した処理の手順を示すフロ
ーチャートである。これまでの説明と重複するが、この
図3を用いてその処理手順を再度説明すると、まず、積
和演算単位として切り出されたＮ個のデータ（この実施
の形態では、ＪＰＥＧを例にしているので8個のデー
タ）を切り出し（ステップｓ１）、切り出された８個の
データの個々のデータが零であるかどうかの判定を行う
（ステップｓ２）。

【００７６】そして、その零・非零判定処理による零・
非零判定結果によって、アドレッシングモード選択手段
４１とアドレッシングデータ記憶手段４２を用いて、ア
ドレッシングモード設定を行う（ステップｓ３）。

【００７７】これは、零・非零判定結果によって得られ
る非零要素の位置を示す情報に依存したアドレッシング
データをアドレッシングデータ記憶手段４２から取得す
ることであり、上述した図１の例においては、切り出さ
れた８個のデータの零・非零判定結果は、“１００１０
１１０”であって、これを10進数で表した「１５０」を
keyとして、アドレッシングモード選択手段４１がアド
レッシングデータ記憶手段４２からデータ長が「４」で
そのデータ位置が「１，２，４，７」のアドレッシング
データを取得してそれを設定する。

【００７８】そして、このアドレッシングモード設定と
ともに、ベースアドレスの設定を行う（ステップｓ
４）。このベースアドレスは、前述したように、ここで
は０ｘ１０００としている。そして、残データ数をデー
タ長に設定する（ステップｓ５）。この残データ数をデ
ータ長に設定というのは、アドレッシングデータ記憶手
段４２により得られたデータ長を設定することであり、
上述の例では、アドレッシングデータ記憶手段４２によ
り得られたデータ長は「４」であるので、その「４」が
設定されることになる。

【００７９】そして、その残データ数が零か否かを判断
し（ステップｓ６）、零であれば処理を終了し、零でな
ければ、物理アドレスで指定されるアドレスのデータに
対して積和演算を行う（ステップｓ７）。

【００８０】次に、仮想アドレスに1を加えて（ステッ
プｓ８）、残データ数から１を減じて（ステップｓ
９）、ステップｓ６の処理に戻る。これは、たとえば、
仮想アドレス０ｘ１０００に対する積和演算処理が終了
したら、それに１を加えて０ｘ１００１とし、そのとき
の残データ数（この場合４）から「１」を減算して残デ
ータ数を「３」としてステップｓ６を行い、この場合、
残データ数が零でないので、仮想アドレス０ｘ１００１
に対する物理アドレス０ｘ１００２による積和演算を行
う。

【００８１】そして、この仮想アドレス０ｘ１００１に
対する積和演算処理が終了したら、それに１を加えて０
ｘ１００２とし、そのときの残データ数（この場合３）
から「１」を減算して残データ数を「２」としてステッ
プｓ６を行い、この場合、残データ数が零でないので、
仮想アドレス０ｘ１００２に対する物理アドレス０ｘ１
００４による積和演算を行う。

【００８２】この仮想アドレス０ｘ１００２に対する積
和演算処理が終了したら、それに１を加えて０ｘ１００
３とし、そのときの残データ数（この場合２）から
「１」を減算して残データ数を「１」としてステップｓ
６を行い、この場合、残データ数が零でないので、仮想
アドレス０ｘ１００３に対する物理アドレス０ｘ１００
７による積和演算を行う。

【００８３】この仮想アドレス０ｘ１００３に対する積
和演算処理が終了したら、それに１を加えて０ｘ１００
４とし、そのときの残データ数（この場合１）から
「１」を減算して残データ数を「０」としてステップｓ
６を行うと、この場合、残データ数が零であるので、処
理を終了する。

【００８４】このように、ＣＰＵやＤＳＰは連続的なデ
ータアドレスを生成し、その連続的なデータアドレスに
従って演算処理を行なうが、実際には、その連続的なア
ドレスが疎の状態で存在する積和演算すべきデータを次
々と指し示す物理アドレスとして変換する処理が行わ
れ、それによって、疎な状態でしか存在しない非零要素
のみを次々と連続して読み出す動作を行うことになる。

【００８５】なお、積和演算を行う際は、（６）式や
（７）式で示した変換係数を用いて行うが、この変換係
数に対しても、疎の状態で存在する非零要素のデータに
対応し読み出す必要があり、変換係数を読み出すための
変換係数アドレスも上述同様のアドレス変換を行う必要
がある。

【００８６】図４は本発明の積和演算装置の全体的な構
成図であり、処理対象となるデータを記憶するデータ記
憶手段１、このデータ記憶手段１から1つの積和演算単
位を構成するデータ（ここでは8個のデータ）を切り出
すデータ選択手段２、このデータ選択手段２で切り出さ
れた積和演算単位の8個のデータに対し、零か非零かの
判定を行う零・非零判定手段３、上述したアドレス変換
処理を行なうアドレス変換手段（このアドレス変換手段
はデータアドレスに対するアドレス変換手段４ａと変換
係数アドレスに対するアドレス変換手段４ｂが存在す
る）、積和演算を行うに必要な変換係数を記憶する変換
係数記憶手段５、積和演算処理を行うＣＰＵあるいはＤ
ＳＰ（ここではＣＰＵとする）６から構成されている。
なお、この図4の構成要素のうち、図1および図２で示し
た構成要素と同じものには同一符号が付されている。

【００８７】アドレス変換手段４ａ，４ｂは、それぞれ
アドレッシングモード選択手段４１、アドレッシングデ
ータ記憶手段４２、ベースアドレス記憶手段４３を有し
た構成となっており、図１および図２で説明したような
動作を行う。

【００８８】図５はこの図2をブロック図として表した
ものであり、ベースアドレス記憶手段４３、アドレッシ
ングモード選択手段４１、アドレッシングデータ記憶手
段４２の他に、ＣＰＵ６で生成されるデータアドレスあ
るいは変換係数アドレスを仮想アドレスとして入力する
仮想アドレス入力手段４４と、その仮想アドレスをアド
レス変換処理することによって生成された物理アドレス
を記憶する物理アドレス記憶手段４５を有した構成とな
っている。

【００８９】ＣＰＵ６はデータアドレス生成手段６１、
変換係数アドレス生成手段６２、積和演算手段６３を有
した構成となっており、データアドレスや変換係数アド
レスの生成、積和演算処理を行なうとともに、この図４
に示す各構成要素全体の動作を制御する機能をも有して
いる。

【００９０】データアドレス生成手段６１で生成される
アドレスは、積和演算単位として切り出された８個のデ
ータを順に読み出すためのアドレス（データアドレス）
であり、このデータアドレスはアドレス変換手段４ａに
与えられ、このアドレス変換手段４ａに含まれる仮想ア
ドレス入力手段４４（図５参照）に仮想アドレスとして
入力される。

【００９１】また、変換係数アドレス生成手段６２で生
成されるアドレスは、変換係数を読み出すためのアドレ
ス（変換係数アドレス）であり、この変換係数アドレス
は、アドレス変換手段４ｂに与えられ、このアドレス変
換手段４ｂに含まれる仮想アドレス入力手段４４（図５
参照）に仮想アドレスとして入力される。

【００９２】このような構成の積和演算装置におけるア
ドレス変換手段４ａ，４ｂのアドレス変換処理などにつ
いてはすでに詳細に説明したので、このアドレス変換処
理についての説明は省略して、全体的な処理について説
明する。

【００９３】まず、図1で説明したように、積和演算単
位として切り出された8個のデータにおける非零要素の
位置を示す情報に基づいて、アドレッシングモード選択
手段４１がアドレッシングデータ記憶手段４２から或る
データ長とデータ位置を示す情報を指示し、そのデータ
長とデータ位置を示す情報がアドレッシングデータとし
て設定される。その後、図2で説明したように、ＣＰＵ
６のデータアドレス生成手段６１で生成される連続的な
データアドレス（仮想アドレス０ｘ１０００，０ｘ１０
０１，０ｘ１００２，…）をアドレス変換手段４ａでア
ドレス変換処理することで、非零要素のみを連続的に指
し示す物理アドレス（上述の例では、０ｘ１００１，０
ｘ１００２，０ｘ１００４，０ｘ１００７）を生成し、
データ記憶手段１からその物理アドレスで示されるデー
タを読み出して、その読み出されたデータが積和演算手
段６３に与えられる。

【００９４】一方、同じく、ＣＰＵ６の変換係数アドレ
ス生成手段６２で生成される変換係数アドレスをアドレ
ス変換手段４ｂでデータアドレスと同様にアドレス変換
処理することで、非零要素に対応する変換係数を連続的
に指し示す物理アドレスを生成し、変換係数記憶手段５
からその物理アドレスによって示される変換係数を読み
出して、その読み出された変換係数が積和演算手段６３
に与えられる。

【００９５】このように、アドレス変換手段４ａ，４ｂ
によって生成された物理アドレスによって非零要素のデ
ータが順次読み出されるとともに、その非零要素に対応
する変換係数が順次読み出され、それらが積和演算手段
６３に与えられることで積和演算が行われる。

【００９６】このとき、ＣＰＵ６からは連続的なデータ
アドレスと変換係数アドレスが生成されるだけである
が、その連続的なデータアドレスと変換係数アドレス
は、疎な状態で存在する非零要素とそれに対応する変換
係数を次々と連続的に指し示す物理アドレスとして変換
され、それによって、たとえ、積和演算すべき非零要素
のデータが疎な状態で散らばって存在していても、ＣＰ
Ｕ６は単に連続的なデータアドレスおよび変換係数アド
レスを生成し、それに従ったデータの読み出しを行って
積和演算する動作を行うだけで、実際には、疎に存在す
る非零要素のデータとそれに対応する変換係数のみを順
次読み出して積和演算する動作を行うことになり、効率
のよい積和演算が行え、その演算量を大幅に削減するこ
とができる。

【００９７】なお、本発明は以上説明した実施の形態に
限定されるものではなく、本発明の要旨を逸脱しない範
囲で種々変形実施可能となるものである。

【００９８】また、本発明は、以上説明した本発明を実
現するための処理手順が記述された処理プログラムを作
成し、その処理プログラムをフロッピィディスク、光デ
ィスク、ハードディスクなどの記録媒体に記録させてお
くことができ、本発明はその処理プログラムが記録され
た記録媒体をも含むものである。また、ネットワークか
ら当該処理プログラムを得るようにしてもよい。

【００９９】

【発明の効果】以上で説明したように本発明によれば、
積和演算単位を構成するＮ個のデータのそれぞれについ
て零か非零かを判断し、そのＮ個のデータにおける非零
要素の存在する位置を示す情報に基づき、ＣＰＵやＤＳ
Ｐなどの積和演算処理手段で生成されるアドレスに対
し、非零要素のみを連続的に読み出し可能となるような
アドレス変換を行い、そのアドレス変換後のアドレス順
で読み出されたデータに対して順次積和演算を行うよう
にしている。

【０１００】このように、ＣＰＵやＤＳＰなどが生成す
る連続的なアドレスを、非零要素のみを順次アクセス可
能なアドレスに変換して、その変換後のアドレス順でデ
ータを読み出して積和演算を行うようにしている。

【０１０１】これにより、ＣＰＵやＤＳＰなどは単に連
続したアドレスによって演算すべきデータを読み出して
積和演算する動作を行うだけで、実際には、疎な状態で
しか存在しない非零要素のみを次々と連続して読み出す
動作を行うことになる。したがって、たとえ、積和演算
すべき非零要素のデータが疎な状態で散らばって存在し
ていたとしても、その疎な状態の非零要素とそれに対応
する変換係数を次々と連続的に読み出すことができ、こ
れによって、直交変換処理に伴う積和演算を効率よく行
うことができ、その演算量を大幅に削減することができ
る。

【図面の簡単な説明】

【図１】本発明の積和演算処理を説明する図であり、処
理対象となるデータから積和演算単位となる8個のデー
タを切り出し、その8個のデータ中に非零要素がどのよ
うな位置に存在しているかを判断し、それに基づいてデ
ータ長とデータ位置を示す情報を取得する処理を説明す
る図である。

【図２】本発明の積和演算処理を説明する図であり、図
1で示した処理に基づいて、ＣＰＵやＤＳＰで生成され
るアドレスを変換するアドレス変換処理を説明する図で
ある。

【図３】本発明の積和演算処理の全体的な処理手順を説
明するフローチャートである。

【図４】本発明の積和演算装置の全体的な構成図であ
る。

【図５】図２で示したアドレス変換動作をブロック図と
して表した図である。

【図６】画像データから処理単位となるＮ×Ｎ（８×
８）のデータブロックの切り出しを模式的に説明する図
である。

【図７】処理単位となるＮ×Ｎ（８×８）のデータブロ
ックのデータ例と、そのデータを周波数領域に変換した
のち量子化する処理例を説明する図である。

【図８】ランレングス符号化処理について説明する図で
ある。

【図９】図７（ｃ）のデータを並べ替え、さらに、零の
連鎖をＥＯＢに置き換えた場合を示す図である。

【図１０】処理単位となるＮ×Ｎ（８×８）のデータブ
ロックに対する処理を行方向または列方向のいずれから
行うかを説明する図である。

【図１１】従来技術において、ＥＯＢの位置により最適
な演算手段を選択して直交変換演算の簡略化を図る例を
説明する図である。

【図１２】 従来技術において、処理単位となるＮ×Ｎ
（８×８）のデータブロックをいくつかの領域に分割し
て演算を行うことで直交演算の簡略化を図る例を説明す
る図である。

【図１３】処理単位となるＮ×Ｎ（８×８）のデータブ
ロックにおけるデータにおいて、従来技術の１つである
４並列演算（行方向の４並列演算）により積和演算を行
なう場合の問題点を説明する図である。

【図１４】処理単位となるＮ×Ｎ（８×８）のデータブ
ロックにおけるデータにおいて、従来技術の１つである
ＥＯＢの判断を用いて積和演算を行なう場合の問題点を
説明する図である。

【符号の説明】

１ データ記憶手段 ２ データ選択手段 ３ 零・非零判定手段 ４ａ アドレス変換手段（データアドレスに対するアド
レス変換手段） ４ｂ アドレス変換手段（変換係数アドレスに対するア
ドレス変換手段） ５ 変換係数記憶手段 ６ ＣＰＵ ４１ アドレッシングモード選択手段 ４２ アドレッシングデータ記憶手段 ４３ ベースアドレス記憶手段 ６１ データアドレス生成手段 ６２ 変換係数アドレス生成手段 ６３ 積和演算手段

Claims (4)

【特許請求の範囲】
1. 【請求項１】 積和演算単位を構成するＮ個のデータを
   所定のアドレス順で順次読み出して積和演算を行う積和
   演算方法において、 前記Ｎ個のデータのそれぞれについて零か非零かを判断
   し、そのＮ個のデータにおける非零要素の存在する位置
   を示す情報に基づいて、前記アドレスに対し、前記非零
   要素のみを連続的に読み出し可能となるようなアドレス
   変換を行い、 その変換後のアドレスによって読み出されたデータに対
   して順次積和演算を行うことを特徴とする積和演算方
   法。
2. 【請求項２】 前記Ｎ個のデータにおける非零要素の存
   在する位置に基づくアドレス変換は、積和演算を行うに
   必要な変換係数を読み出すためのアドレスに対しても行
   い、その変換後のアドレスによって前記非零要素に対応
   する変換係数の読み出しを行うことを特徴とする請求項
   １記載の積和演算方法。
3. 【請求項３】 積和演算単位を構成するＮ個のデータを
   所定のアドレス順で順次読み出して積和演算を行う積和
   演算装置において、 処理対処となるデータが記憶されるデータ記憶手段と、 このデータ記憶手段に記憶された処理対象となるデータ
   から、積和演算単位となるＮ個のデータを切り出すデー
   タ選択手段と、 このデータ選択手段で切り出されたＮ個のデータのそれ
   ぞれが零か非零かを判断する零・非零判定手段と、 その零・非零判定結果において非零要素の存在する位置
   を示す情報に基づいて、前記アドレスに対し、前記非零
   要素のみを連続的に読み出し可能となるようなアドレス
   変換を行うアドレス変換手段と、 を有し、このアドレス変換手段によるアドレス変換後の
   アドレスによって読み出されたデータに対して積和演算
   を行うことを特徴とする積和演算装置。
4. 【請求項４】 前記Ｎ個のデータにおける非零要素の存
   在する位置に基づいたアドレス変換を行うアドレス変換
   手段は、前記Ｎ個のデータを順次読み出すためのアドレ
   スに対してアドレス変換を行うデータアドレス変換手段
   と、前記変換係数を読み出すためのアドレスに対してア
   ドレス変換を行う変換係数アドレス変換手段を設け、前
   記データを読み出すためのアドレスに対しては、前記デ
   ータアドレス変換手段により前記非零要素のみを連続的
   に読み出し可能となるようなアドレス変換を行い、前記
   変換係数を読み出すためのアドレスに対しては、前記変
   換係数アドレス変換手段により前記非零要素に対応する
   変換係数の読み出しが可能となるようなアドレス変換を
   行うことを特徴とする請求項３記載の積和演算装置。