JP3652717B2

JP3652717B2 - 離散コサイン高速演算器

Info

Publication number: JP3652717B2
Application number: JP11492494A
Authority: JP
Inventors: 元伸外村
Original assignee: Renesas Technology Corp
Current assignee: Renesas Technology Corp
Priority date: 1994-05-27
Filing date: 1994-05-27
Publication date: 2005-05-25
Anticipated expiration: 2020-05-25
Also published as: JPH07319849A

Description

【０００１】
【産業上の利用分野】
本発明は、計算機システムの演算器に係り、特にマルチメディア処理分野において、複数個の定数関数値を利用した積和計算をし、データの圧縮／伸長を高速処理するのに好適な離散コサイン高速演算器に関する。
【０００２】
【従来の技術】
音声・画像処理などによく使われている離散フーリエ変換（ＤＦＴ）およびその各種変形である離散コサイン変換（ＤＣＴ）などは、複数個の三角関数値を利用しており、それらとデータとの積和計算が主体である。一般に、乗算の方が加減算に比べて計算コストが高いために、複数個の三角関数値間の関係（倍／半角公式など）を巧みに利用して乗算回数を少なくした高速計算アルゴリズムが従来いくつか考案されている。これらについては、日経エレクトロニクス１９９０．１０．１５，Ｎｏ．５１１，１１５〜１４２ページにおいてまとめられている。複数個の三角関数値は定数としてメモリに格納して利用している場合が多い。特に、桁数が比較的少ないので、データと三角関数値の積の全結果をメモリに格納しておく方法も使われている。また、座標回転の原理を利用したＣＯＲＤＩＣ法や関数近似式で計算する方法で、直接、各三角関数値を計算する方法も知られているので利用することができる。
【０００３】
【発明が解決しようとする課題】
複数個の三角関数値を定数としてメモリに格納しておいて利用する、あるいはＣＯＲＤＩＣ法などで直接計算する従来方法は、乗算回数を巧妙なアルゴリズムで削減しても、ある一定のかなりの乗算を必要とする。しかも、それらの乗算に対して各乗算器を設けることは現実的ではなく、逐次的に利用することになる。これが高速演算を妨げる原因になっている。また、乗算器は任意の値の入力を仮定しているので、２進入力データのある桁の値がゼロであってもその桁に関する部分積が無駄に計算されてしまっている。データと三角関数値の積の全結果をメモリに格納して利用する方法も、設計が容易であるが、メモリ容量が大きく、チップサイズが大きくなる。
【０００４】
【課題を解決するための手段】
本発明では、各三角関数値が定数であることから、それらの２進数展開した数の非ゼロ係数の個数が最少に近くなるように、あらかじめ｛−１，０，＋１｝の冗長２進数表現にリコードおよびシフトし、各桁ごとに非ゼロ係数値の対を最適グループ化し、対応するデータ対を係数の符号に応じて加減算し、さらにそれらの結果を定められた位置に桁合わせシフトして加算器群に入力することによって部分積を求め、各部分積を総和することで無駄なく構成し、コンパクトかつ高速に動作する離散コサイン高速演算器を提供することにある。
【０００５】
【作用】
定数の非ゼロ係数の個数を少なくして、また各桁ごとに非ゼロ係数値の対をグループ化して加算を最適共通化するため、加算器の総個数が減少するとともに、総ゲート段数も減少する。
【０００６】
【実施例】
８点の離散コサイン変換（以下ＤＣＴと略称）について説明する。ＤＣＴの式は、入力データをｘ_k、計算データをＸ_nとすると、
【０００７】
【数１】

【０００８】
によって表される。また、逆ＤＣＴ（以下ＩＤＣＴと略称）の式は、
【０００９】
【数２】

【００１０】
によって表される。ただし、
【００１１】
【数３】

【００１２】
である。g(i)=cos(πi/16)とおけば、数式（１）は図２に示すように行列表現できる。また、数式（２）は図２の行と列を転置したもので表現できる。
【００１３】
今、ＤＣＴの計算を実現する前に、まず次のような積和式
【００１４】
【数４】

【００１５】
を考える。ここで、
【００１６】
【数５】

【００１７】
とすると、
【００１８】
【数６】

【００１９】
である。ただし、ａ_k,i∈｛−１，０，１｝とする。もし、相異なるｋとｊについて、ａ_k,i＝｜ａ_j,i｜＝１なる係数の対ａ_k,iとａ_j,iが存在するならば、
【００２０】
【数７】

【００２１】
となる。さらに、相異なるｉとｍについて、ａ_k,i＝｜ａ_j,m｜＝１なる係数の対ａ_k,iとａ_j,mが存在するならば、
【００２２】
【数８】

【００２３】
となる。ｘ_k・ａ_k＋ｘ_j・ａ_jの積和について、もし、数式（７）または（８）を満たす係数の対が復数個存在するならば、数式（７）によって示される原理に従って、あらかじめｘ_kとｘ_jの和と差、あるいは数式（８）によって示される原理に従って、一方を２のｎ乗（ｎ＝ｍ−ｉ桁シフト）したものとの和と差を計算し、これらを上記条件を満たす桁位置まで各々シフトして互いに加算することによって部分積和の計算回数を削減することができる。
【００２４】
さらに、ｉ個の非ゼロ係数を２個にまで削減することができる正準リコードと呼ばれている
【００２５】
【数９】

【００２６】
なる関係を適当に使用することによって数のシフト操作を行い、数式（７）または（８）を満たす係数の対を増加させることができる。
【００２７】
これら原理を適用して、ＤＣＴの部分積和計算量を削減する方法を以下に説明する。まず、７個のコサイン定数ｇ（ｉ）の１６桁までの２進数展開値を図３に示す。あわせて正準リコード値も示しておく（リコードによって非ゼロ係数の個数は５９から４２になる）。ただし、−１は１の上に横棒をつけて表現する。さらに、ｇ（４）は２の平方根倍すれば１と簡単になるので、ｇ（ｉ）の２の平方根倍の値も示しておく（非ゼロ係数の個数は４６から４３になる）。このように、もとのコサイン定数に適当な定数を掛けることによって、リコード後の非ゼロ係数の個数が増減することから、どこかに最適解が存在することが予想できる。もちろん、仮定する桁数にも依存する。ここでは、シフト操作によって容易に桁合わせできることから逆ＤＣＴの計算も考えると（逆ＤＣＴでは、掛けた定数で逆に割ることになる）、ｇ（ｉ）とその２の平方根倍のどちらかしか意味がないことを指摘しておくが、もし、ＤＣＴあるいは逆ＤＣＴのどちらか一方の計算しか利用しない場合はこのかぎりではない。本実施例では、主として２の平方根倍をした場合を仮定して説明する。
【００２８】
ＤＣＴの計算では、図２に示すように、ｇ（２ｋ＋１）が奇数行に出現し、ｇ（２ｋ）が偶数行に出現し、グループ化されている。また、各ｇ（ｋ）について互いに異符号で２つの列ｉとｊに出現しているので、ｘ_iとｘ_jの差、ｕ_k＝ｘ_i−ｘ_jをあらかじめ計算しておく。そして、例えば、１行目について、ｕ₁＝ｘ₀−ｘ₇、ｕ₃＝ｘ₁−ｘ₆、ｕ₅＝ｘ₂−ｘ₅、ｕ₇＝ｘ₃−ｘ₄とすると、総和：ｕ₁・ｇ（１）＋ｕ₃・ｇ（３）＋ｕ₅・ｇ（５）＋ｕ₇・ｇ（７）＝１．０１１０００１１０００１ｕ₁＋１．００１０１１０１００００ｕ₃＋０．１１００１００１００１０ｕ₅＋０．０１０００１１０１０１０ｕ₇（小数点以下１２桁目までで丸めた）の計算は、図４に示すように、まず、ｕ₁＋ｕ₃、ｕ₁−ｕ₃、ｕ₅＋ｕ₇を前加算し、続いて、それら結果およびｕ₁、ｕ₃、ｕ₅、ｕ₇が単独出現する桁位置へシフト入力し、一括して後加算する。次に、２行目について、ｕ₂＝（ｘ₀＋ｘ₇）−（ｘ₃＋ｘ₄）、ｕ₆＝（ｘ₁＋ｘ₆）−（ｘ₂＋ｘ₅）とすると、総和：ｕ₂・ｇ（２）＋ｕ₆・ｇ（６）＝１．０１００１１１０１０００ｕ₂＋０．１０００１０１０１００１ｕ₆の計算は、図４に示すように、まず、ｕ₂とｕ₆を計算し、ｕ₂＋ｕ₆を前加算し、続いて、それら結果およびｕ₂、ｕ₆が単独出現する桁位置へシフト入力し、一括して後加算する。さらに、０行目または４行目について、ｕ₄＝（ｘ₀＋ｘ₇）＋（ｘ₃＋ｘ₄）、ｕ₄’＝−（ｘ₁＋ｘ₆）−（ｘ₂＋ｘ₅）とすると、まず、ｕ₄とｕ₄’を計算し、総和：（ｕ₄＋ｕ₄’）・ｇ（４）＝ｕ₄＋ｕ₄’の計算をすればよい。残りの、３、６と５、７行目についても、それぞれ１行目と２行目とほぼ同じ構成で加算できる。そこで、図５に示すように、セレクタｓ１、ｓ３、ｓ５、ｓ７、ｓ２、ｓ３、ｓ４、ｓ４’を設ければ、加算部のハードウェアは共通化でき、奇数行と偶数行について各行が逐一計算される。もちろん加算部のハードウェアを共通化しないでこれらを並列化することもできる。すなわち、図２に示す行列表現の各行の総和を並列に計算するために、各々の加算ハードウェアを独立に設ける。
【００２９】
図５において、加算器１２０〜１２６，２２０〜２４１の種類については全加算器、桁上げ伝播のない加算器など適当に選べばよいが、特に、高速化を狙うならば、桁上げ伝播のない加算器を選ぶべきである。その場合には、総和した結果を通常の２進数表現に変換する部分２１０，２１１が必要である。また、桁上げ伝播のない加算器についても、桁上げ保存型と冗長２進型があるが、どちらを選択してもかまわない。本実施例では、冗長２進加算器特有の性質を利用した回路構成法について説明する。桁上げ伝播のない加算器は各桁が同じ回路で構成されていることから、任意の１桁分について考えればよい。まず、ｕ_k＝ｘ_i−ｘ_j１００〜１０３の各桁の計算回路は、０−０＝０、０−１＝−１、１−０＝＋１、１−１＝０であるから、加算回路を使わなくても、図６に示す簡単なゲート回路によって構成できる。ｕ_k＝ｘ_i＋ｘ_j１０４〜１０７の各桁の計算回路も、ｕ_k＝ｘ_i＋ｘ_j＝ｘ_i−（−ｘ_j）と考えればよい。−ｘ_jは２の補数表現によって、ｘ_jの反転＋１によって得られる。ｘ_jの反転はｘ_jの上に横棒をつけて示す。そして、２段目以降の加算は、｛＋１，０，−１｝の冗長２進数表現であるから、各桁の冗長２進加算回路には、図７に示す回路を使用する。冗長２進数表現で得られる総和結果は通常の２進数に変換される。この変換回路２１０，２１１は、冗長２進数が、正と負の２進数に分解できることから、減算器で容易に構成できる。この減算器には、加算器における桁上げ先見回路に相当する桁借りを先見する専用回路を付加してもよい。
【００３０】
次に、ＩＤＣＴの計算について説明する。ＩＤＣＴは図２に示すように、ＤＣＴの行列表現の行と列を転置したものである。ＩＤＣＴとＤＣＴとの相違は、ＤＣＴではｇ（ｋ）の出現が奇数と偶数のｋについて分かれたが、ＩＤＣＴではすべてのｋについてｇ（ｋ）が現れることである。しかし、ｇ（１），ｇ（３），ｇ（５），ｇ（７）が０列目に出現するが、７列目にこれらとは異符号のものが出現する。ｇ（４），ｇ（２），ｇ（４），ｇ（６）は０列目と７列目に同符号で出現する。また、ｇ（３），−ｇ（７），−ｇ（１），−ｇ（５）が１列目に出現し、６列目にこれらとは異符号のものが出現する。ｇ（４），ｇ（６），−ｇ（４），−ｇ（２）が１列目と６列目に同符号で出現する。ｇ（５），−ｇ（１），ｇ（７），ｇ（３）が２列目に出現し、５列目にこれらとは異符号のものが出現する。ｇ（４），−ｇ（６），−ｇ（４），ｇ（２）が２列目と５列目に同符号で出現する。そして、ｇ（７），−ｇ（５），ｇ（３），−ｇ（１）が３列目に出現し、４列目にこれらとは異符号のものが出現する。ｇ（４），−ｇ（２），ｇ（４），−ｇ（６）が３列目と４列目に同符号で出現する。従って、奇数ｋのｇ（ｋ）に関してグループ化した総和について、前列目と後列目とでは異符号のかたちで加算することで、同時に２列分のＩＤＣＴ結果を得ることができる。これら回路２４０，２４１とそれらのセレクタおよび入力データ１１０〜１１７のセレクタを図５に追加することでＤＣＴ／ＩＤＣＴ回路のハードウェアを共通化することができる。
【００３１】
以上説明してきた図５のＤＣＴ／ＩＤＣＴブロック図を図２の各行についての計算ごとに並列化してまとめると、図１に示す本発明の離散コサイン高速演算器の構成図が得られる。すなわち、８個の元データ／計算データが同時に入力され、まず前加算部１０において、入力データそれ自体の和および／あるいは差（コサイン定数値のリコードによって求められる），それら入力データの定数倍の和および／または差（コサイン定数値の桁シフトによって求められる）を予め計算する。次に、後加算部２０において、前加算部１０の結果を定められた位置に桁合わせシフトして加算器群に入力することによって部分積を計算し、各部分積を総和することで８個の出力データ（計算データ／元データ）が同時に得られる。従来の乗算器ベースのものでは、１２回の乗算（１１×１２＝１３２回の加算）と２９回の加算が必要だったので、合計１６１個の加算器が必要であった。また、加算１回を１段と数える段数では、加算１４段であった。本発明方式によれば、合計１１６（＝２９×４）個の加算器が必要で、加算５段である。したがって、従来の約２／３の加算器で約３倍の速度が達成できるという効果がある。
【００３２】
今まで説明してきたＤＣＴ／ＩＤＣＴは、１次元のものでこれらは主として音声などの圧縮／伸長に利用される。（ｘ，ｙ）座標をもつ２次元の画像などの圧縮／伸長に利用するためには、図８の上部に示すように２つの１次元の要素ｘ方向走査とｙ方向走査に分解する。すなわち、まずｘ方向に走査する第１の１次元要素の結果をＲＡＭ（ランダム・アクセス・メモリ）に一旦格納し、これらの行と列の役割を転置し、ｙ方向に走査する第２の１次元要素に入力して計算する。結果として２次元のものが得られる。従来のこのような方式に対して、以下では１次元の要素に分解することなく、直接２次元で計算する本発明方式を説明する。ここでは、説明が複雑になるのを避けるため、２次元の４×４点で説明する。８×８点には容易に拡張できる。２次元では、ｃｏｓα・ｃｏｓβの定数計算が必要で、もし、ｃｏｓαとｃｏｓβの定数値を別々に求めておいたものを利用するならば、乗算が必要になるが、４×４点では図９に示すように、あらかじめ６個の組み合せについて掛け合わされた定数値を求めておけばこれら定数同士の乗算が不要になる。さらに、２つの１次元の要素に分解する従来方式で必要なＲＡＭへの格納動作も不要になり高速化が実現できる。ｆ（ｉ）＝ｃｏｓ（πｉ／８）とおく。２次元４×４点のＤＣＴ／ＩＤＣＴの行列は、図１０／１１に示すようになる。ただし、ここではシフトできる係数項は説明上本質的でないので省略した。
【００３３】
図１０の２次元ＤＣＴの式から、図１２に示すように（浮動小数点以下１６桁）、加算の対を（ｆ（１）ｆ（２），ｆ（２）ｆ（３））と（ｆ（１）ｆ（１），ｆ（３）ｆ（３）），そして単独加算をｆ（１）ｆ（３）とｆ（２）ｆ（２）とすればよいことがわかり、１次元のときと同様に前加算１０の対が選ばれ、対応する桁位置へシフト入力され、後加算２０で一括計算される。２次元の４×４点ＤＣＴのブロック図をまとめると、図１３に示すようになる。ここでは、すべてのデータが並列に計算されることを想定している。したがって、４×４＝１６個のデータｘ_ijはすでにバッファ・メモリまたはレジスタに格納されている。ｘ_ij−ｘ_kl６０の計算は、回路６００のゲート（１桁分）によって加算器なしに行われる。ｘ_ij＋ｘ_kl６１の計算は、回路６１０のゲート（１桁分）によって加算器なしに行われる。ただし、ｘ_ij−（−ｘ_kl）によって求める。それ以降の加算に使う加算器５０，５１などは冗長２進加算器で、その１桁分の回路は図７に示すものである。加算器群の加算タイプは３種類７０，７１，７２に分かれていて、合計１６ブロックある。２次元の４×４点ＩＤＣＴの式は図１１に示すとおりなので、１次元のときと類似の方法でＤＣＴのハードウェアと共有できる。本発明方式によれば、２次元を２つの１次元に分解する必要がないので、転置用ＲＡＭに一旦格納する必要がなくなり計算が一気に行われ高速化されるという効果がある。ただし、必要な加算器の数は１次元に分解する場合に比べて３倍程度になる。
【００３４】
図１４に本発明のＤＣＴ／ＩＤＣＴ高速演算器を使ったチップ・システム３００の例を示す。画像はフレーム・メモリ、レジスタなどの並列アクセス可能なバッファ・メモリ部３２０に格納される。ＤＣＴ／ＩＤＣＴ部３１０は、バッファ・メモリ部３２０より、演算に必要な８×８＝６４個のすべてのデータを同時に取りだし、演算結果を量子化部３３０に出力し、可変長符号部３４０で圧縮され、伝送路に送られるかあるいは記憶媒体に格納される（３５０）。逆に、伝送路／記憶媒体からシステム３００に入力された圧縮データは可変長復号部３４０で伸長され、逆量子化部３３０で元の計算データに復元され、ＩＤＣＴ３１０で逆変換計算され、元の画像データに復元され、バッファ・メモリ３２０を介して、画像表示される。
【００３５】
本発明は、離散コサイン変換ばかりでなく、三角関数一般に拡張することができるので、離散フーリエ変換およびその系統（ハートレイ変換、ウェーブレット変換など）にも応用することができる。また、三角関数を使った一般の変換、例えば、ハフ変換、ラドン変換などにも応用できる。さらに、三角関数を一般の周期関数にも拡張することができる。そして、一方が定数の積和演算にも拡張することができる。次元を２次元から３次元以上に、離散化点数を８点から増加させることもできる。本発明のシフト操作はあらかじめ定められたものとして固定化しているが、これらをシフタで構成すれば、可変構造になり、応用範囲が拡大される。加算器が大量に使用されるが、これらの任意の１桁分は基本回路として規則的な繰返し構造を有するので設計規模の拡大は容易である。
【００３６】
【発明の効果】
本発明によれば、ゲート段数が大幅に削減され、ＤＣＴ／ＩＤＣＴの計算が高速化されるという効果がある。また、ＤＣＴ／ＩＤＣＴのハードウェアをほぼ共通化していることと、この高速化を（速度）×（面積）＝（一定）になるように基本部分を繰返して使用すれば、チップ面積小を実現できる。
【図面の簡単な説明】
【図１】本発明の離散コサイン高速演算器の構成図。
【図２】ＤＣＴ／ＩＤＣＴ計算の行列表現。
【図３】７個のコサイン定数の２進数数展開値とその値を正準リコードしたもの、およびそれらを２の平方根倍したもの。
【図４】前加算のために、あらかじめ加減算する変数対の組み合せおよび後加算のために、シフト入力する位置を示す図。
【図５】本発明の１次元ＤＣＴ／ＩＤＣＴを計算する回路。
【図６】ｘ_i−ｘ_jを加算器でなく簡単なゲートで実現する１桁分の回路。
【図７】本発明で使用する冗長２進加算器の１桁分の回路。
【図８】２次元ＤＣＴ／ＩＤＣＴを１次元に分解して実現する方法および直接２次元で実現する方法の説明図。
【図９】２次元４×４点のｃｏｓα×ｃｏｓβ値の２進数展開値とそれらのリコード値の表。
【図１０】２次元４×４点ＤＣＴの行列表現。
【図１１】２次元４×４点ＩＤＣＴの行列表現。
【図１２】２次元４×４点ＤＣＴ／ＩＤＣＴを１次元分解なしに直接計算する方法：前加算のために、あらかじめ加減算する変数対の組み合せおよび後加算のために、シフト入力する位置を示す図。
【図１３】２次元４×４点ＤＣＴを１次元分解なしに直接計算する本発明の回路構成図。
【図１４】本発明のＤＣＴ／ＩＤＣＴ高速演算器を組み込んだチップ構成図。
【符号の説明】
１０…前加算ブロック，２０…後加算ブロック，１００〜１０７…ＤＣＴ入力直後の単純加算ゲート回路，１１０〜１１７…ＩＤＣＴ入力部，１２０〜１２６，２２０〜２４１…冗長２進加算器，２１０，２１１…冗長２進から通常の２進へ変換する回路。

Claims

複数の入力変数の和又は差の一方若しくは両方、又は、前記複数の入力変数の定数倍の値の和又は差の一方若しくは両方を並列に計算する複数の第１の計算手段と前記複数の第１計算手段の結果のうち二つの結果を和又は差の一方又は両方を計算する複数の第２の計算手段を有し、複数の計算結果を出力する第１の手段と、
前記第１の手段の複数の出力を同時に加算処理する複数の第２の手段とを有する処理手段とを有し、
前記第１の手段の複数の出力の夫々は、前記複数の第２の手段のうち前記第 2 の計算手段の結果及び前記第 1 の計算手段の結果が単独出現する桁位置にシフトして入力されることを特徴とする離散コサイン変換の部分積和演算を行う離散コサイン高速演算器。
複数の入力変数の和又は差の一方若しくは両方、又は、前記複数の入力変数の定数倍の値の和又は差の一方若しくは両方を並列に計算する複数の第１の計算手段と前記複数の第１計算手段の結果のうち二つの結果を和又は差の一方又は両方を計算する複数の第２の計算手段を有し、複数の計算結果を出力する第１の手段と、
前記第１の手段の複数の出力を同時に後加算処理する複数の第２の手段とを有する処理手段とを有し、
前記第１の手段の複数の出力の夫々は、前記複数の第２の手段のうち前記第 2 の計算手段の結果及び前記第 1 の計算手段の結果が単独出現する桁位置にシフトして入力されることをことを特徴とする離散コサイン変換の部分積和演算を行う離散コサイン高速演算器。
前記第１の手段は、ｎ点離散コサイン変換の式において、順変換の場合にはｎ−１＝ｉ＋ｊとなるようなｉとｊとについてｉ列及びｊ列のデータの和と差を前記データ入力直後に計算したものを、逆変換の場合には入力されたｉ列とｊ列のデータそのものを選択する手段を有しており、
順変換と逆変換のハードウェアを共通化したことを特徴とする請求項１または２記載の離散コサイン高速演算器。
前記第１の手段は、１−１＝０，１−０＝１，０−１＝−１，０−０＝０となる回路である複数のゲート回路を有し、
前記処理手段は、冗長２進加算器を有し、
前記複数のゲート回路には、それぞれが入力初段の加算が減算となるように変換した値を入力する請求項１または２記載の離散コサイン高速演算器。
前記離散コサイン高速演算器は、適当な定数に予めコサイン係数を掛けてリコード後の非ゼロ係数の数をもとの係数よりも少なくなるように決定して回路を構成したことを特徴とする請求項１または２記載の離散コサイン高速演算器。