JPH0516618B2 - - Google Patents
Info
- Publication number
- JPH0516618B2 JPH0516618B2 JP58125345A JP12534583A JPH0516618B2 JP H0516618 B2 JPH0516618 B2 JP H0516618B2 JP 58125345 A JP58125345 A JP 58125345A JP 12534583 A JP12534583 A JP 12534583A JP H0516618 B2 JPH0516618 B2 JP H0516618B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- address
- register
- butterfly
- stored
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
- G06F7/5443—Sum of products
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
〔産業上の利用分野〕
本発明は、たとえば高速フーリエ変換等により
デイジタルサンプル値を演算処理する場合に使用
されるバタフライ演算回路に関し、特にバタフラ
イ演算されるデイジタルデータを記憶しているデ
ータメモリのアドレスと、バタフライ演算により
得られるデイジタルデータを記憶する上記データ
メモリのアドレスとが等しいバタフライ演算回路
に関する。 〔背景技術とその問題点〕 デイジタルサンプル値をたとえば高速フーリエ
変換（FFT）により演算処理しようとする場合
に、バタフライ演算回路が使用される。デイジタ
ルデータx1、x2のバタフライ演算は、係数をｋと
し、演算結果をデイジタルデータy1、y2とすれ
ば、 y1＝x1＋kx2 y2＝x1−kx2 ……(1) と表わすことができる。また、上記バタフライ演
算回路において、扱う数値を固定小数点方式で表
わし、また負数を２の補数で表わすようにする
と、該演算回路内の数値Ｎは、−１≦Ｎ＜１の変
域を持つ。このため、バタフライ演算の結果得ら
れるデイジタルデータy1、y2が、オーバーフロー
する場合には、次式に示されるように数値を1/2
倍したのちバタフライ演算が行なわれる。 y1＝１／２x1＋ｋ／２x2 y2＝１／２x1−ｋ／２x2 ……(2) 上記バタフライ演算回路によつて、多数のバタ
フライ演算を高速に実行処理しようとする場合、
いわゆるパイプライン処理が行なわれる。このパ
イプライン処理は、１つのバタフライ演算の演算
終了を待つてつぎのバタフライ演算を開始するの
ではなく、実行されているバタフライ演算の演算
中につぎのバタフライ演算を開始するというよう
に複数の演算を並列的に処理する処理方法であ
る。 上記バタフライ演算回路には、たとえば、乗算
器が２個、加減算器が２個、(1)式の演算について
はｋ、または(2)式の演算については1/2およびk/
２を記憶する係数メモリが１個、またx1、x2およ
びy1、y2を記憶するデータメモリが２個、さらに
係数メモリおよびデータメモリのアドレスを計算
するアドレス生成部が１台設けられている。ここ
で、乗算器、加減算器およびデータメモリが２個
設けられているのは、デイジタルデータx1、x2が
複素数であり、実部および虚部についてそれぞれ
演算が行なわれるためである。 このバタフライ演算回路によつて、(1)式または
(2)式のバタフライ演算をパイプライン処理により
最大限並列的に実行した場合は、メモリへのアク
セス回数を考えないなら、１つのバタフライ演算
が開始されてから４ステツプ後につぎのバタフラ
イ演算を行なうことができる。すなわち、この場
合の信号処理効率は、１つのバタフライ演算を実
質上４ステツプで実行可能なものとなつている。 ところが、１つのバタフライ演算を行なうため
の係数メモリおよびデータメモリへのアクセス回
数を考えると、(1)式または(2)式の演算の場合、ｋ
またはk/2を２度指定するために２回、またx1、
x2、y1、y2の指定に４回、合計で６回アクセスす
る必要がある。ここで、一般に係数ｋはｋ＝cosθ
−isinθが使われ、cosθまたはcosθ／２、sinθまた
は sinθ／２のアクセスに２回、また複素数であるx1、 x2、y1、y2の実部および虚部は異なるメモリの同
じアドレスに記憶されるようになつているため４
回のアクセスが行なわれる。 このように、係数メモリに２回、データメモリ
に４回のアクセスを行なうために、上記アドレス
生成部では、１つのバタフライ演算あたり、６ス
テツプを要してアドレス計算を行なつている。こ
のため、アドレス生成部が１台しか設けられてい
ない上記バタフライ演算回路では、メモリへのア
クセスを考えると、信号処理効率が１つのバタフ
ライ演算あたり６ステツプに落ちてしまい、６ス
テツプ待たなければつぎのバタフライ演算を行な
うことができない。 したがつて、信号処理効率を１つのバタフライ
演算あたり４ステツプに速めるためには、アドレ
ス生成部を２台設ける必要がある。このように、
アドレス生成部を１台増やすことは、必要なIC
（集積回路）数が非常に増加したり、マイクロプ
ログラムのインストラクシヨンが増加するという
欠点がある。 このように、従来のバタフライ演算回路におい
ては、信号処理率が低く、また効率を上げるため
に、素子数を増大させたり、マイクロプログラム
のインストラクシヨンを増大させなければならな
いという難点があつた。 〔発明の目的〕 そこで、本発明はこのような実情に鑑み提案さ
れたものであり、アドレス生成部を１台追加する
ことなく、バタフライ演算を高速に実行可能なバ
タフライ演算回路を提供することを目的とする。 〔発明の概要〕 この目的を達成するために、本発明のバタフラ
イ演算回路は、デイジタルサンプル値に基づくデ
イジタルデータx1、x2等を記憶するデータメモリ
と、係数ｋまたは係数1/2およびk/2を記憶する
係数メモリと、上記データメモリおよび上記係数
メモリのアドレスを示すアドレスデータを演算に
より求めるアドレス生成部と、上記デイジタルデ
ータに対する乗算および加減算を行なう乗算器お
よび加減算器とを有し、上記データメモリに記憶
された少なくとも一対の上記デイジタルデータ
x1、x2をバタフライ演算（y1＝x1＋kx2、y2＝x1
−kx2、またはy1＝x1／２＋kx2／２，y2＝x1／
２−kx2／２）して演算結果であるデイジタルデ
ータy1、y2をそれぞれ求めるバタフライ演算回路
において、上記アドレス生成部にて生成された上
記アドレスデータを記憶し、記憶した上記アドレ
スデータを選択的に上記データメモリにアドレス
データとして供給するアドレスデータ記憶部を備
え、上記アドレスデータ記憶部は、上記データメ
モリから上記デイジタルデータx1、x2が読み出さ
れるときのアドレスデータを記憶保持し、演算結
果である上記デイジタルデータy1、y2が上記デー
タメモリに書き込まれるときに上記記憶保持して
いる上記アドレスデータを上記データメモリに供
給することにより、上記デイジタルデータx1、x2
が読み出されたアドレスと同じアドレスに演算結
果である上記デイジタルデータy1、y2が書き込ま
れるようになされていることを特徴とするもので
ある。 〔実施例〕 以下、本発明の一実施例を図面に基づき説明す
る。 前述したように、デイジタルサンプル値に基づ
く一対のデイジタルデータx1、x2のバタフライ演
算は、係数をｋとし、バタフライ演算して得られ
る一対のデイジタルデータをy1、y2とすれば、 y1＝x1＋kx2 y2＝x1−kx2 ……(1) と表わせる。また、演算結果であるデイジタルデ
ータy1、y2がオーバフローするような場合には、
オーバフローを防止するために、次式によつてバ
タフライ演算が行なわれる。 y1＝１／２x1＋ｋ／２x2 y2＝１／２x1−ｋ／２x2 ……(2) ここで、デイジタルデータx1、ｘを1/2倍する
ようにしてもよいが、バタフライ演算が行なわれ
るバタフライ演算回路の数値Ｎが−１≦Ｎ＜１の
変域をもつような場合には、係数ｋの変域が−１
≦ｋの実部または虚部≦１であると、バタフライ
演算回路内で演算上の不都合が生じる。この不都
合を回避するため、デイジタルデータx2を1/2倍
するのではなく、ｋを1/2倍するようにしている。 変域が、−１≦xiの実部または虚部＜１、ｉ＝
１、２、３、４、……であるデイジタルデータ
x1、x2、x3、x4、…をバタフライ演算回路によつ
てバタフライ演算することによりデイジタルデー
タy1、y2、y3、y4、…を得ることができる。ま
た、さらにこの演算結果であるデイジタルデータ
y1、y2、y3、y4、…をバタフライ演算し、その演
算結果にもバタフライ演算を行なうというよう
に、バタフライ演算を段階的に行なつてゆくと、
バタフライ演算を用いて、デイジタルデータx1、
x2、x3、x4、…についてのたとえば高速フーリエ
変換（FFT）が計算される。 バタフライ演算回路を用いてたとえば高速フー
リエ変換をしようとするとき、演算回路内でオー
バフローする場合には、(2)式のバタフライ演算が
用いられる。ところで、高速フーリエ変換された
データは非常に小さな数値（絶対値）となるた
め、バタフライ演算を用いてフーリエ逆変換を計
算しようとする場合には、バタフライ演算回路内
のオーバーフローが起こらない。このため、フー
リエ逆変換の計算には、(1)式のバタフライ演算が
用いられる。 ところで、上記デイジタルデータx1、x2、x3、
x4、…として、たとえばデイジタルオーデイオサ
ンプル値データα1、α2、α3、α4、…を用いるな
ら、一対のデータα1，α2のバタフライ演算は、係
数ｋをｋ＝e-i〓、バタフライ演算して得られる新
たな一対のデイジタルデータをβ1、β2とすれば、 β1＝α1＋e-i〓・α2 β2＝α1−e-i〓・α2 ……(3) または、 β1＝１／２α1＋e-i〓／２・α2 β2＝１／２α1−e-i〓／２・α2 ……(4) となる。このデイジタルオーデイオサンプル値デ
ータα1、α2、α3、α4、…についてバタフライ演算
を繰り返し、高速フーリエ変換することにより、
最終的な計算結果であるたとえば周波数スペクト
ラムデータを得ることができる。 ここで、上記デイジタルデータα1、α2、β1、β2
の実部をA1、A2、B1、B2で表わし、虚部をa1、
a2、b1、b2で表わせば、データα1、α2、β1、β2
は、 α1＝A1＋ia1 α2＝A2＋ia2 β1＝B1＋ib1 β2＝B2＋ib2 となる。また、e-i〓＝cosθ−isinθであることを利
用すれば、(3)式は、 β1＝（A1＋ia1）＋（cosθ−isinθ）・（A2＋i
a2） β2＝（A1＋ia1）＋（cosθ−isinθ）・（A2＋ia2） となる。この式よりβ1、β2の実部B1、B2および
虚部b1、b2を求めれば次のようになる。 B1＝A1＋（cosθ・A2＋sinθ・a2） b1＝a1＋（cosθ・a2＋sinθ・A2） B2＝A1−（cosθ・A2＋sinθ・a2） b2＝a1−（cosθ・a2＋sinθ・A2） ……(5) また、(4)式について同様に計算し、β1、β2の実部
B1、B2および虚部b1、b2を求めれば次のように
なる。 B1＝A1／２＋（cosθ／２・A2＋sinθ／２・a2） b1＝a1／２＋（cosθ／２・a2−sinθ／２・A2） B2＝A1／２−（cosθ／２・A2＋sinθ／２・a2） b2＝a1／２−（cosθ／２・a2−sinθ／２・A2） ……(6) 第１図および第３図は、本発明に係るバタフラ
イ演算回路のブロツク図である。この第１図に示
すバタフライ演算回路１は、(5)式に示す計算を行
なうようになつており、この計算を行なうことに
より、(3)式のバタフライ演算が実行されるように
つている。また、第３図に示すバタフライ演算回
路２によつて、(6)式に示す計算が行なわれ、1/2
倍を伴う(4)式のバタフライ演算が行なわれるよう
になつている。 上記バタフライ演算回路１，２においては、バ
タフライ演算されるデイジタルデータα1、α2およ
びバタフライ演算を行なうことで得られるデイジ
タルデータβ1、β2はデータメモリDMA、DMBに
記憶されるようになつている。また、データβ1、
β2は、データα1、α2の記憶されていたデータメモ
リDMA、DMBの同一のアドレスに記憶される
ようになつている。上記デイジタルデータα1、
α2、β1、β2の実部A1、A2、B1、B2はデータメモ
リDMAに、また虚部a1、a2、b1、b2はデータメ
モリDMBに記憶されるようになつている。ま
た、バタフライ演算回路１に設けられている係数
メモリCMには、係数ｋの実部、虚部であるcosθ
およびsinθが記憶されている。また、バタフライ
演算回路２の係数メモリCMには、α1を1/2倍す
るための係数1/2、および係数k/2の実部、虚部
であるcosθ／２、sinθ／２が記憶されるようになつて
い る。 つぎに、第１図に示すバタフライ演算回路１の
構成について説明する。バタフライ演算回路１の
上記データメモリDMAはレジスタＲ２Ａとレジ
スタＲ３Ａに接続されており、レジスタＲ２Ａは
レジスタＲ４Ａと乗算器MPYAに接続され、レ
ジスタＲ３Ａは乗算器MPYBに接続されている。
また、データメモリDMBはレジスタＲ２Ｂとレ
ジスタＲ３Ｂに接続されており、レジスタＲ２Ｂ
はレジスタＲ４Ｂと乗算器MPYBに接続され、
レジスタＲ３Ｂは乗算器MPYAに接続されるよ
うになつている。また係数メモリCMは乗算器
MPYAおよび乗算器MPYBに接続されている。
この乗算器MPYAおよび上記レジスタＲ４Ａは
加減算器ALUAに接続され、加減算器ALUAは
レジスタＲ１Ａに接続されるようになつている。
さらにこのレジスタＲ１Ａは、データメモリ
DMAに接続されている。また、上記乗算器
MPYBおよびレジスタＲ４Ｂは加減算器ALUB
に接続され、加減算器ALUBはレジスタＲ１Ｂ
に接続されるようになつている。またこのレジス
タＲ１Ｂは、データメモリDMBに接続されるよ
うになつている。また、上記データメモリ
DMA，DMBおよび係数メモリCMのアドレスを
計算するアドレス生成部AGが１台設けられてい
る。このアドレス生成部AGは、レジスタRCM
１とレジスタ群RDM１に接続されている。この
レジスタRCM１は上記係数メモリCMに接続さ
れ、レジスタ群RDM１は上記データメモリ
DMA，DAMに接続されるようになつている。
ここで、上記レジスタＲ１Ａ，Ｒ１Ｂ，Ｒ２Ａ，
Ｒ２Ｂ，RCM１及びレジスタ群RDM１は、これ
らのレジスタへのデータ取り込み信号をマイクロ
プログラムによりコントロールできるようになつ
ている。 また、第２図は、第１図に示す上記バタフライ
演算回路１の二点鎖線部分の構成を示している。
この第２図において、取り込み信号とクロツク信
号とが入力されるオア回路１０の出力であるコン
トロール信号がレジスタRCM１に入力され、適
切なタイミングにおいて、アドレス生成部AGか
らのアドレス出力がレジスタRCM１を介して、
係数メモリCMに送り出されるようになつてい
る。また、データメモリDMA，DMBに記憶さ
れているデイジタルデータの読み出し時のアドレ
スを一時保存する記憶手段である上記レジスタ群
RDM１は、４段のシフトレジスタを構成する４
個のレジスタ１１，１２，１３，１４とマルチプ
レクサ１５とにより構成されている。各レジスタ
１１，１２，１３，１４には、取り込み信号とク
ロツク信号とが入力されるオア回路１６の出力で
あるコントロール信号が入力されるようになつて
いる。また、各レジスタ１１，１２，１３，１４
はそれぞれマルチプレクサ１５に接続されてい
る。また、マルチプレクサ１５は、データメモリ
DMA，DMBに接続されている。このマルチプ
レクサ１５には、たとえば２ビツトにより構成さ
れる選択信号S1、S2、S3、S4が入力され、それぞ
れレジスタ１１，１２，１３，１４の出力が選択
されるようになつている。そして、アドレス生成
部AGからのアドレス出力が適切なタイミングに
おいて、上記レジスタ１１，１２，１３，１４と
マルチプレクサ１５を介して、データメモリ
DMA，DMBに送り出されるようになつている。 表１および表２は、第１図に示す上記バタフラ
イ演算回路１により(5)式を計算する手段を示して
いる。上記バタフライ演算回路１において、デー
タメモリDMA、DMBのアドレスP1にデータA1、
a1がそれぞれ記憶され、またアドレスP2にデータ
A2、a2がそれぞれ記憶されている。また、係数
メモリCMのアドレスQ1に係数ｋの実部である
cosθが記憶され、アドレスQ2に虚部であるsinθが
記憶されている。また、バタフライ演算を１回行
なうことにより得られる演算結果B1、b1、B2、
b2は、データメモリDMA，DMBの上記データ
A1、a1の記憶されていた上記P1番地にデータB1、
b1がそれぞれ記憶され、上記データA2、a2の記
憶されていた上記P2番地にデータB2、b2がそれ
ぞれ記憶されるようになつている。
デイジタルサンプル値を演算処理する場合に使用
されるバタフライ演算回路に関し、特にバタフラ
イ演算されるデイジタルデータを記憶しているデ
ータメモリのアドレスと、バタフライ演算により
得られるデイジタルデータを記憶する上記データ
メモリのアドレスとが等しいバタフライ演算回路
に関する。 〔背景技術とその問題点〕 デイジタルサンプル値をたとえば高速フーリエ
変換（FFT）により演算処理しようとする場合
に、バタフライ演算回路が使用される。デイジタ
ルデータx1、x2のバタフライ演算は、係数をｋと
し、演算結果をデイジタルデータy1、y2とすれ
ば、 y1＝x1＋kx2 y2＝x1−kx2 ……(1) と表わすことができる。また、上記バタフライ演
算回路において、扱う数値を固定小数点方式で表
わし、また負数を２の補数で表わすようにする
と、該演算回路内の数値Ｎは、−１≦Ｎ＜１の変
域を持つ。このため、バタフライ演算の結果得ら
れるデイジタルデータy1、y2が、オーバーフロー
する場合には、次式に示されるように数値を1/2
倍したのちバタフライ演算が行なわれる。 y1＝１／２x1＋ｋ／２x2 y2＝１／２x1−ｋ／２x2 ……(2) 上記バタフライ演算回路によつて、多数のバタ
フライ演算を高速に実行処理しようとする場合、
いわゆるパイプライン処理が行なわれる。このパ
イプライン処理は、１つのバタフライ演算の演算
終了を待つてつぎのバタフライ演算を開始するの
ではなく、実行されているバタフライ演算の演算
中につぎのバタフライ演算を開始するというよう
に複数の演算を並列的に処理する処理方法であ
る。 上記バタフライ演算回路には、たとえば、乗算
器が２個、加減算器が２個、(1)式の演算について
はｋ、または(2)式の演算については1/2およびk/
２を記憶する係数メモリが１個、またx1、x2およ
びy1、y2を記憶するデータメモリが２個、さらに
係数メモリおよびデータメモリのアドレスを計算
するアドレス生成部が１台設けられている。ここ
で、乗算器、加減算器およびデータメモリが２個
設けられているのは、デイジタルデータx1、x2が
複素数であり、実部および虚部についてそれぞれ
演算が行なわれるためである。 このバタフライ演算回路によつて、(1)式または
(2)式のバタフライ演算をパイプライン処理により
最大限並列的に実行した場合は、メモリへのアク
セス回数を考えないなら、１つのバタフライ演算
が開始されてから４ステツプ後につぎのバタフラ
イ演算を行なうことができる。すなわち、この場
合の信号処理効率は、１つのバタフライ演算を実
質上４ステツプで実行可能なものとなつている。 ところが、１つのバタフライ演算を行なうため
の係数メモリおよびデータメモリへのアクセス回
数を考えると、(1)式または(2)式の演算の場合、ｋ
またはk/2を２度指定するために２回、またx1、
x2、y1、y2の指定に４回、合計で６回アクセスす
る必要がある。ここで、一般に係数ｋはｋ＝cosθ
−isinθが使われ、cosθまたはcosθ／２、sinθまた
は sinθ／２のアクセスに２回、また複素数であるx1、 x2、y1、y2の実部および虚部は異なるメモリの同
じアドレスに記憶されるようになつているため４
回のアクセスが行なわれる。 このように、係数メモリに２回、データメモリ
に４回のアクセスを行なうために、上記アドレス
生成部では、１つのバタフライ演算あたり、６ス
テツプを要してアドレス計算を行なつている。こ
のため、アドレス生成部が１台しか設けられてい
ない上記バタフライ演算回路では、メモリへのア
クセスを考えると、信号処理効率が１つのバタフ
ライ演算あたり６ステツプに落ちてしまい、６ス
テツプ待たなければつぎのバタフライ演算を行な
うことができない。 したがつて、信号処理効率を１つのバタフライ
演算あたり４ステツプに速めるためには、アドレ
ス生成部を２台設ける必要がある。このように、
アドレス生成部を１台増やすことは、必要なIC
（集積回路）数が非常に増加したり、マイクロプ
ログラムのインストラクシヨンが増加するという
欠点がある。 このように、従来のバタフライ演算回路におい
ては、信号処理率が低く、また効率を上げるため
に、素子数を増大させたり、マイクロプログラム
のインストラクシヨンを増大させなければならな
いという難点があつた。 〔発明の目的〕 そこで、本発明はこのような実情に鑑み提案さ
れたものであり、アドレス生成部を１台追加する
ことなく、バタフライ演算を高速に実行可能なバ
タフライ演算回路を提供することを目的とする。 〔発明の概要〕 この目的を達成するために、本発明のバタフラ
イ演算回路は、デイジタルサンプル値に基づくデ
イジタルデータx1、x2等を記憶するデータメモリ
と、係数ｋまたは係数1/2およびk/2を記憶する
係数メモリと、上記データメモリおよび上記係数
メモリのアドレスを示すアドレスデータを演算に
より求めるアドレス生成部と、上記デイジタルデ
ータに対する乗算および加減算を行なう乗算器お
よび加減算器とを有し、上記データメモリに記憶
された少なくとも一対の上記デイジタルデータ
x1、x2をバタフライ演算（y1＝x1＋kx2、y2＝x1
−kx2、またはy1＝x1／２＋kx2／２，y2＝x1／
２−kx2／２）して演算結果であるデイジタルデ
ータy1、y2をそれぞれ求めるバタフライ演算回路
において、上記アドレス生成部にて生成された上
記アドレスデータを記憶し、記憶した上記アドレ
スデータを選択的に上記データメモリにアドレス
データとして供給するアドレスデータ記憶部を備
え、上記アドレスデータ記憶部は、上記データメ
モリから上記デイジタルデータx1、x2が読み出さ
れるときのアドレスデータを記憶保持し、演算結
果である上記デイジタルデータy1、y2が上記デー
タメモリに書き込まれるときに上記記憶保持して
いる上記アドレスデータを上記データメモリに供
給することにより、上記デイジタルデータx1、x2
が読み出されたアドレスと同じアドレスに演算結
果である上記デイジタルデータy1、y2が書き込ま
れるようになされていることを特徴とするもので
ある。 〔実施例〕 以下、本発明の一実施例を図面に基づき説明す
る。 前述したように、デイジタルサンプル値に基づ
く一対のデイジタルデータx1、x2のバタフライ演
算は、係数をｋとし、バタフライ演算して得られ
る一対のデイジタルデータをy1、y2とすれば、 y1＝x1＋kx2 y2＝x1−kx2 ……(1) と表わせる。また、演算結果であるデイジタルデ
ータy1、y2がオーバフローするような場合には、
オーバフローを防止するために、次式によつてバ
タフライ演算が行なわれる。 y1＝１／２x1＋ｋ／２x2 y2＝１／２x1−ｋ／２x2 ……(2) ここで、デイジタルデータx1、ｘを1/2倍する
ようにしてもよいが、バタフライ演算が行なわれ
るバタフライ演算回路の数値Ｎが−１≦Ｎ＜１の
変域をもつような場合には、係数ｋの変域が−１
≦ｋの実部または虚部≦１であると、バタフライ
演算回路内で演算上の不都合が生じる。この不都
合を回避するため、デイジタルデータx2を1/2倍
するのではなく、ｋを1/2倍するようにしている。 変域が、−１≦xiの実部または虚部＜１、ｉ＝
１、２、３、４、……であるデイジタルデータ
x1、x2、x3、x4、…をバタフライ演算回路によつ
てバタフライ演算することによりデイジタルデー
タy1、y2、y3、y4、…を得ることができる。ま
た、さらにこの演算結果であるデイジタルデータ
y1、y2、y3、y4、…をバタフライ演算し、その演
算結果にもバタフライ演算を行なうというよう
に、バタフライ演算を段階的に行なつてゆくと、
バタフライ演算を用いて、デイジタルデータx1、
x2、x3、x4、…についてのたとえば高速フーリエ
変換（FFT）が計算される。 バタフライ演算回路を用いてたとえば高速フー
リエ変換をしようとするとき、演算回路内でオー
バフローする場合には、(2)式のバタフライ演算が
用いられる。ところで、高速フーリエ変換された
データは非常に小さな数値（絶対値）となるた
め、バタフライ演算を用いてフーリエ逆変換を計
算しようとする場合には、バタフライ演算回路内
のオーバーフローが起こらない。このため、フー
リエ逆変換の計算には、(1)式のバタフライ演算が
用いられる。 ところで、上記デイジタルデータx1、x2、x3、
x4、…として、たとえばデイジタルオーデイオサ
ンプル値データα1、α2、α3、α4、…を用いるな
ら、一対のデータα1，α2のバタフライ演算は、係
数ｋをｋ＝e-i〓、バタフライ演算して得られる新
たな一対のデイジタルデータをβ1、β2とすれば、 β1＝α1＋e-i〓・α2 β2＝α1−e-i〓・α2 ……(3) または、 β1＝１／２α1＋e-i〓／２・α2 β2＝１／２α1−e-i〓／２・α2 ……(4) となる。このデイジタルオーデイオサンプル値デ
ータα1、α2、α3、α4、…についてバタフライ演算
を繰り返し、高速フーリエ変換することにより、
最終的な計算結果であるたとえば周波数スペクト
ラムデータを得ることができる。 ここで、上記デイジタルデータα1、α2、β1、β2
の実部をA1、A2、B1、B2で表わし、虚部をa1、
a2、b1、b2で表わせば、データα1、α2、β1、β2
は、 α1＝A1＋ia1 α2＝A2＋ia2 β1＝B1＋ib1 β2＝B2＋ib2 となる。また、e-i〓＝cosθ−isinθであることを利
用すれば、(3)式は、 β1＝（A1＋ia1）＋（cosθ−isinθ）・（A2＋i
a2） β2＝（A1＋ia1）＋（cosθ−isinθ）・（A2＋ia2） となる。この式よりβ1、β2の実部B1、B2および
虚部b1、b2を求めれば次のようになる。 B1＝A1＋（cosθ・A2＋sinθ・a2） b1＝a1＋（cosθ・a2＋sinθ・A2） B2＝A1−（cosθ・A2＋sinθ・a2） b2＝a1−（cosθ・a2＋sinθ・A2） ……(5) また、(4)式について同様に計算し、β1、β2の実部
B1、B2および虚部b1、b2を求めれば次のように
なる。 B1＝A1／２＋（cosθ／２・A2＋sinθ／２・a2） b1＝a1／２＋（cosθ／２・a2−sinθ／２・A2） B2＝A1／２−（cosθ／２・A2＋sinθ／２・a2） b2＝a1／２−（cosθ／２・a2−sinθ／２・A2） ……(6) 第１図および第３図は、本発明に係るバタフラ
イ演算回路のブロツク図である。この第１図に示
すバタフライ演算回路１は、(5)式に示す計算を行
なうようになつており、この計算を行なうことに
より、(3)式のバタフライ演算が実行されるように
つている。また、第３図に示すバタフライ演算回
路２によつて、(6)式に示す計算が行なわれ、1/2
倍を伴う(4)式のバタフライ演算が行なわれるよう
になつている。 上記バタフライ演算回路１，２においては、バ
タフライ演算されるデイジタルデータα1、α2およ
びバタフライ演算を行なうことで得られるデイジ
タルデータβ1、β2はデータメモリDMA、DMBに
記憶されるようになつている。また、データβ1、
β2は、データα1、α2の記憶されていたデータメモ
リDMA、DMBの同一のアドレスに記憶される
ようになつている。上記デイジタルデータα1、
α2、β1、β2の実部A1、A2、B1、B2はデータメモ
リDMAに、また虚部a1、a2、b1、b2はデータメ
モリDMBに記憶されるようになつている。ま
た、バタフライ演算回路１に設けられている係数
メモリCMには、係数ｋの実部、虚部であるcosθ
およびsinθが記憶されている。また、バタフライ
演算回路２の係数メモリCMには、α1を1/2倍す
るための係数1/2、および係数k/2の実部、虚部
であるcosθ／２、sinθ／２が記憶されるようになつて
い る。 つぎに、第１図に示すバタフライ演算回路１の
構成について説明する。バタフライ演算回路１の
上記データメモリDMAはレジスタＲ２Ａとレジ
スタＲ３Ａに接続されており、レジスタＲ２Ａは
レジスタＲ４Ａと乗算器MPYAに接続され、レ
ジスタＲ３Ａは乗算器MPYBに接続されている。
また、データメモリDMBはレジスタＲ２Ｂとレ
ジスタＲ３Ｂに接続されており、レジスタＲ２Ｂ
はレジスタＲ４Ｂと乗算器MPYBに接続され、
レジスタＲ３Ｂは乗算器MPYAに接続されるよ
うになつている。また係数メモリCMは乗算器
MPYAおよび乗算器MPYBに接続されている。
この乗算器MPYAおよび上記レジスタＲ４Ａは
加減算器ALUAに接続され、加減算器ALUAは
レジスタＲ１Ａに接続されるようになつている。
さらにこのレジスタＲ１Ａは、データメモリ
DMAに接続されている。また、上記乗算器
MPYBおよびレジスタＲ４Ｂは加減算器ALUB
に接続され、加減算器ALUBはレジスタＲ１Ｂ
に接続されるようになつている。またこのレジス
タＲ１Ｂは、データメモリDMBに接続されるよ
うになつている。また、上記データメモリ
DMA，DMBおよび係数メモリCMのアドレスを
計算するアドレス生成部AGが１台設けられてい
る。このアドレス生成部AGは、レジスタRCM
１とレジスタ群RDM１に接続されている。この
レジスタRCM１は上記係数メモリCMに接続さ
れ、レジスタ群RDM１は上記データメモリ
DMA，DAMに接続されるようになつている。
ここで、上記レジスタＲ１Ａ，Ｒ１Ｂ，Ｒ２Ａ，
Ｒ２Ｂ，RCM１及びレジスタ群RDM１は、これ
らのレジスタへのデータ取り込み信号をマイクロ
プログラムによりコントロールできるようになつ
ている。 また、第２図は、第１図に示す上記バタフライ
演算回路１の二点鎖線部分の構成を示している。
この第２図において、取り込み信号とクロツク信
号とが入力されるオア回路１０の出力であるコン
トロール信号がレジスタRCM１に入力され、適
切なタイミングにおいて、アドレス生成部AGか
らのアドレス出力がレジスタRCM１を介して、
係数メモリCMに送り出されるようになつてい
る。また、データメモリDMA，DMBに記憶さ
れているデイジタルデータの読み出し時のアドレ
スを一時保存する記憶手段である上記レジスタ群
RDM１は、４段のシフトレジスタを構成する４
個のレジスタ１１，１２，１３，１４とマルチプ
レクサ１５とにより構成されている。各レジスタ
１１，１２，１３，１４には、取り込み信号とク
ロツク信号とが入力されるオア回路１６の出力で
あるコントロール信号が入力されるようになつて
いる。また、各レジスタ１１，１２，１３，１４
はそれぞれマルチプレクサ１５に接続されてい
る。また、マルチプレクサ１５は、データメモリ
DMA，DMBに接続されている。このマルチプ
レクサ１５には、たとえば２ビツトにより構成さ
れる選択信号S1、S2、S3、S4が入力され、それぞ
れレジスタ１１，１２，１３，１４の出力が選択
されるようになつている。そして、アドレス生成
部AGからのアドレス出力が適切なタイミングに
おいて、上記レジスタ１１，１２，１３，１４と
マルチプレクサ１５を介して、データメモリ
DMA，DMBに送り出されるようになつている。 表１および表２は、第１図に示す上記バタフラ
イ演算回路１により(5)式を計算する手段を示して
いる。上記バタフライ演算回路１において、デー
タメモリDMA、DMBのアドレスP1にデータA1、
a1がそれぞれ記憶され、またアドレスP2にデータ
A2、a2がそれぞれ記憶されている。また、係数
メモリCMのアドレスQ1に係数ｋの実部である
cosθが記憶され、アドレスQ2に虚部であるsinθが
記憶されている。また、バタフライ演算を１回行
なうことにより得られる演算結果B1、b1、B2、
b2は、データメモリDMA，DMBの上記データ
A1、a1の記憶されていた上記P1番地にデータB1、
b1がそれぞれ記憶され、上記データA2、a2の記
憶されていた上記P2番地にデータB2、b2がそれ
ぞれ記憶されるようになつている。
【表】
【表】
【表】
表１および第２に基づき、はじめに、バタフラ
イ演算することで得られる演算結果であるデイジ
タルデータβ1、β2の(5)式に示す実部B1、B2を計
算する手順を説明する。 まず、最初の第１ステツプでアドレス生成部
AGで計算された出力P2が、ステツプを順送りす
るクロツク信号と取り込み信号とが同時にオア回
路１６に入力されることによつて、レジスタ群
RDM１のレジスタ１１に送られるようになつて
いる。つぎの第２ステツプでアドレス生成部AG
のアドレス出力Q2が、クロツク信号と取り込み
信号とが同時にオア回路１０に入力されること
で、レジスタRCM１に送られる。また、第３ス
テツプでアドレス生成部AGのアドレス出力P1が
取り込み信号に同期してレジスタ群RDM１のレ
ジスタ１１に送られるが、該取り込み信号よりも
早い時刻にレジスタ群RDM１のマルチプレクサ
１５に入力される選択信号S1によつてレジスタ１
１のアドレス信号P2が選択され、該アドレス信
号P2はデータメモリDMA、DMBに送られるよ
うになつている。このとき、アドレス信号P2は
上記取り込み信号に同期して、レジスタ１２に送
られる。また、この同じステツプで、アドレス信
号P2によつてアドレス指定され読み出されたデ
ータメモリDMAのデータA2は、レジスタＲ２Ａ
に送られる。また、同様にアドレス信号P2によ
つて読み出されたデータメモリDMBのデータa2
は、レジスタＲ３Ｂに送られるようになつてい
る。また、つぎの第４ステツプにおいて、アドレ
ス生成部AGからのアドレス出力Q1がレジスタ
RCM１に送られると同時に、レジスタRCM１内
のアドレス信号Q2は係数メモリCMに送られる。
アドレス信号Q2によつてアドレス指定された係
数メモリCMは、係数ｋの虚部に相当するsinθを
乗算器MPYAに送り出すようになつている。ま
た、同じステツプでレジスタＲ３Ｂにストアされ
ていたデータa2が乗算器MPAYに送られるよう
になつている。ここで、つぎの第５ステツプにス
テツプが進むと同時に、デイジタルデータα1、
α2、α3、α4、…の内のたとえば一対のデータα3、
α4についてのつぎのバタフライ演算が第１ステツ
プから開始されるようになつている。ところで、
第５ステツプでは、レジスタ群RDM１のレジス
タ１１にストアされていたアドレス信号P1がマ
ルチプレクサ１５において選択信号S1によつて選
択され、データメモリDMAに送られる。データ
メモリDMAでは、アドレス信号P1によりアドレ
ス指定されることで、データA1が読み出される。
このデータA1は、レジスタＲ２Ａに送られるよ
うになつている。また、同じステツプでレジスタ
RCM１にストアされていたアドレス信号Q1が係
数メモリCMに送られ、アドレス指定されて読み
出された係数メモリCMからの係数ｋの実部cosθ
は乗算器MPYAに送られる。また、同じステツ
プでレジスタＲ２Ａにストアされていたデータ
A2は、乗算器MPYAに送られる。また、すでに
乗算器MPYA内で乗算されているsinθ・a2の出
力は、同じステツプで乗算器MPYAから加減算
器ALUAに送られるようになつている。さらに
つぎの第６ステツプで、レジスタＲ２Ａにストア
されていたデータA1は、レジスタＲ４Ａに送ら
れる。また、すでに乗算器MPYA内で乗算され
ているcosθ・A2の出力は、この同じステツプで
加減算器ALUAに送られる。また、つぎの第７
ステツプで、レジスタＲ２Ａにストアされていた
データA1がレジスタＲ４Ａに送られるが、第６
ステツプにおいてレジスタＲ４Ａに送られていた
データA1は加減算器ALUAに送られるようにな
つている。また、このデータA1より、加減算器
ALUAにおいてすでに加算されて得られている
Ｗ＝cosθ・A2＋sinθ・a2が減算され、この同じス
テツプで、減算されて得られた演算出力B2＝A1
−ＷがレジスタＲ１Ａに送り出されるようになつ
ている。ここで、上記第５ステツプと第７ステツ
プにおいて、つぎに計算されるデータα3、α4につ
いてのバタフライ演算の第１ステツプと第３ステ
ツプが実行されている。このため第５ステツプと
第７ステツプでは、データα3、α4に関するアドレ
ス信号がレジスタ群RDM１に取り込まれてお
り、第７ステツプにおいて、アドレス信号P1が
レジスタ１３に、アドレス信号P2がレジスタ１
４に送られるようになつている。ところで、つぎ
の第８ステツプでは、レジスタ群RDM１のレジ
スタ１４にストアされているアドレス信号P2が、
選択信号S4によりマルチプレクサ１５で選択さ
れ、データメモリDMAに送られるようになつて
いる。アドレス信号P2によつてアドレス指定さ
れたデータメモリDMAには、レジスタＲ１Ａに
ストアされていた演算出力であるデータB2が、
データA2の記憶されていた同じアドレスに格納
されるようになつている。このデイジタルデータ
B2は、デイジタルデータα1、α2のバタフライ演
算出力であるデータβ2の実部に相当している。ま
た、この同じステツプで、レジスタＲ４Ａにスト
アされていたデータA1が加減算器ALUAに送ら
れる。また、このデータA1には、加減算器
ALUAにストアされているＷが加算され、加算
されて得られた演算出力B1＝A1＋Ｗが同じステ
ツプでレジスタＲ１Ａに送り出されるようになつ
ている。つぎの第９ステツプは、ステツプ数を合
わせるため空ステツプとなつており、何も実行さ
れないようになつている。この第９ステツプから
は、たとえば一対のデイジタルデータα5、α6につ
いてのさらにつぎのバタフライ演算の第１ステツ
プが開始されるようになつている。このため、こ
の第９ステツプにおいて、たとえばデータα6につ
いてのアドレス信号がレジスタ群RDM１に取り
込まれるため、上記アドレス信号P1はレジスタ
１４に移動するようになつている。つぎの第１０
ステツプでは、レジスタ群RDM１のレジスタ１
４にストアされているアドレス信号P1が、選択
信号S4によりマルチプレクサ１５で選択され、デ
ータメモリDMAに送られるようになつている。
アドレス信号P1によつてアドレス指定されたデ
ータメモリDMAには、レジスタＲ１Ａにストア
されていた演算出力であるデータB1が、データ
A1の記憶されていた同じアドレスに格納される
ようになつている。このデイジタルデータB1は、
バタフライ演算出力であるデータβ1の実部に相当
している。つぎの第11ステツプおよび第12ステツ
プは、ステツプ数を合わせるための空ステツプと
なつており、何も実行されないようになつてい
る。このようにして、バタフライ演算出力である
データβ1、β2の実部B1、B2が計算されるように
なつている。なお、最後のバタフライ演算につい
ては、第８ステツプおよび第10ステツプで選択信
号S2等を利用して、アドレス信号を選択するよう
にしてもよい。 ところで、データβ1、β2の虚部b1、b2を求める
ための計算は、乗算器MPYBおよび加減算器
ALUBまたレジスタＲ１Ｂ等を利用して行なわ
れ、上述した実部B1、B2を求める計算手順と同
一の手段で行なわれるようになつている。したが
つて、虚部b1、b2を計算する手順の説明を省略す
る。なお、表２中でＸは Ｘ＝cosθ・a2−sinθ・A2 を表わしている。 このように、上記バタフライ演算回路１では、
第１ステツプおよび第３ステツプで、バタフライ
演算されるデイジタルデータα1、α2の記憶されて
いるデータメモリDMA，DMBのアドレスP1、
P2をアドレス生成部AGで計算している。また、
第２ステツプと第３ステツプとで、係数ｋの記憶
されている係数メモリCMのアドレスQ1、Q2がア
ドレス生成部AGで計算されるようになつてい
る。そして、上記レジスタ群RDM１に上記アド
レスP1、P2がストアされるようになつている。
このため、バタフライ演算結果であるデイジタル
データβ1、β2のデータメモリDMA，DMBに格納
される上記アドレスP1、P2の計算がアドレス生
成部AGでもう一度行なわれることなく、第８ス
テツプおよび第10ステツプにおいて選択信号によ
り選択され再使用されるようになつている。した
がつてデータメモリDMA，DMBおよび係数メ
モリCMへのアクセス回数は１つのバタフライ演
算あたり６回必要であるにもかかわらず、アドレ
ス生成部AGでは４回のアドレス計算を行なうの
みですむようになつている。このため、信号処理
効率を１つのバタフライ演算あたり６ステツプに
落とすことなく、４ステツプに速めることが可能
となつている。このように、レジスタ群RDM１
の設けられた上記バタフライ演算回路１では、始
めの４ステツプの動作が完了した時点で、つぎの
バタフライ演算の第１ステツプを開始できるよう
になつており、上述したように、上記第５ステツ
プから第８ステツプではつぎのバタフライ演算の
第１ステツプから第４ステツプが行なわれ、上記
第９ステツプから第12ステツプではつぎのバタフ
ライ演算の第５ステツプから第８ステツプと、さ
らにそのつぎのバタフライ演算の第１ステツプか
ら第４ステツプがそれぞれ並列的に処理されるよ
うになつている。 つぎに、1/2倍を伴うバタフライ演算を計算す
る第第３図に示すバタフライ演算回路２の構成に
ついて説明する。このバタフライ演算回路２は、
上記バタフライ演算回路１に設けられているレジ
スタＲ４Ａ、Ｒ４Ｂが設けられていないこと、ま
た上記レジスタRCM１がレジスタ群RCM２に置
き換えられていることを除いて、上記バタフライ
演算回路１と同様な構成となつている。 第４図は、第３図に示すバタフライ演算２の一
点鎖線部分の構成を示している。この第４図にお
いて、レジスタ群RCM２は、２段のシフトレジ
スタを構成する２個のレジスタ２０，２１とマル
チプレクサ２２とにより構成され、各レジスタ２
０，２１はそれぞれマルチプレクサ２２に接続さ
れるようになつている。また、取り込み信号とク
ロツク信号とが入力されるオア回路２３の出力で
あるコントロール信号が、各レジスタ２０，２１
に入力されている。上記マルチプレクサ２２に
は、たとえば１ビツトにより構成されている選択
信号t1、t2が入力され、それぞれレジスタ２０，
２１の出力が選択されるようになつている。これ
により、アドレス生成部AGからのアドレス出力
は、適切なタイミングにおいて、レジスタ２０，
２１及びマルチプレクサ２２を介して、係数メモ
リCMに送り出されるようになつている。また、
４段のシフトレジスタを構成する４個のレジスタ
２４，２５，２６，２７とマルチプレクサ２８と
により構成されているレジスタ群RDM２は、上
記バタフライ演算回路１のレジスタ群RDM１と
まつたく同様な構成となつている。これらレジス
タ２４，２５，２６，２７は、オア回路２９から
のコントロール信号が入力されており、マルチプ
レクサ２８を介して、アドレス生成部AGのアド
レス出力が適切なタイミングにおいて、データメ
モリDMA，DMBに送り出されるようになつて
いる。 表３乃至表５は、第３図に示す上記バタフライ
演算回路２により(4)式に示す1/2倍の伴うバタフ
ライ演算を(6)式によつて計算する手順を示してい
る。このバタフライ演算２では、データメモリ
DMA，DMBに記憶されるデイジタルデータα1、
α2、β1、β2は、バタフライ演算回路１と同様にア
ドレスP1、P2によつて指定されるようになつて
いる。また、係数メモリCMのアドレスQ1に係数
k/2の実部cosθ／２が記憶され、アドレスQ2に虚部 sinθ／２が記憶されている。また係数メモリCM内の 別のアドレスに数値1/2が記憶され、レジスタ群
RCM２を使用することなく、いつでも該アドレ
スを指定できるようになつている。
イ演算することで得られる演算結果であるデイジ
タルデータβ1、β2の(5)式に示す実部B1、B2を計
算する手順を説明する。 まず、最初の第１ステツプでアドレス生成部
AGで計算された出力P2が、ステツプを順送りす
るクロツク信号と取り込み信号とが同時にオア回
路１６に入力されることによつて、レジスタ群
RDM１のレジスタ１１に送られるようになつて
いる。つぎの第２ステツプでアドレス生成部AG
のアドレス出力Q2が、クロツク信号と取り込み
信号とが同時にオア回路１０に入力されること
で、レジスタRCM１に送られる。また、第３ス
テツプでアドレス生成部AGのアドレス出力P1が
取り込み信号に同期してレジスタ群RDM１のレ
ジスタ１１に送られるが、該取り込み信号よりも
早い時刻にレジスタ群RDM１のマルチプレクサ
１５に入力される選択信号S1によつてレジスタ１
１のアドレス信号P2が選択され、該アドレス信
号P2はデータメモリDMA、DMBに送られるよ
うになつている。このとき、アドレス信号P2は
上記取り込み信号に同期して、レジスタ１２に送
られる。また、この同じステツプで、アドレス信
号P2によつてアドレス指定され読み出されたデ
ータメモリDMAのデータA2は、レジスタＲ２Ａ
に送られる。また、同様にアドレス信号P2によ
つて読み出されたデータメモリDMBのデータa2
は、レジスタＲ３Ｂに送られるようになつてい
る。また、つぎの第４ステツプにおいて、アドレ
ス生成部AGからのアドレス出力Q1がレジスタ
RCM１に送られると同時に、レジスタRCM１内
のアドレス信号Q2は係数メモリCMに送られる。
アドレス信号Q2によつてアドレス指定された係
数メモリCMは、係数ｋの虚部に相当するsinθを
乗算器MPYAに送り出すようになつている。ま
た、同じステツプでレジスタＲ３Ｂにストアされ
ていたデータa2が乗算器MPAYに送られるよう
になつている。ここで、つぎの第５ステツプにス
テツプが進むと同時に、デイジタルデータα1、
α2、α3、α4、…の内のたとえば一対のデータα3、
α4についてのつぎのバタフライ演算が第１ステツ
プから開始されるようになつている。ところで、
第５ステツプでは、レジスタ群RDM１のレジス
タ１１にストアされていたアドレス信号P1がマ
ルチプレクサ１５において選択信号S1によつて選
択され、データメモリDMAに送られる。データ
メモリDMAでは、アドレス信号P1によりアドレ
ス指定されることで、データA1が読み出される。
このデータA1は、レジスタＲ２Ａに送られるよ
うになつている。また、同じステツプでレジスタ
RCM１にストアされていたアドレス信号Q1が係
数メモリCMに送られ、アドレス指定されて読み
出された係数メモリCMからの係数ｋの実部cosθ
は乗算器MPYAに送られる。また、同じステツ
プでレジスタＲ２Ａにストアされていたデータ
A2は、乗算器MPYAに送られる。また、すでに
乗算器MPYA内で乗算されているsinθ・a2の出
力は、同じステツプで乗算器MPYAから加減算
器ALUAに送られるようになつている。さらに
つぎの第６ステツプで、レジスタＲ２Ａにストア
されていたデータA1は、レジスタＲ４Ａに送ら
れる。また、すでに乗算器MPYA内で乗算され
ているcosθ・A2の出力は、この同じステツプで
加減算器ALUAに送られる。また、つぎの第７
ステツプで、レジスタＲ２Ａにストアされていた
データA1がレジスタＲ４Ａに送られるが、第６
ステツプにおいてレジスタＲ４Ａに送られていた
データA1は加減算器ALUAに送られるようにな
つている。また、このデータA1より、加減算器
ALUAにおいてすでに加算されて得られている
Ｗ＝cosθ・A2＋sinθ・a2が減算され、この同じス
テツプで、減算されて得られた演算出力B2＝A1
−ＷがレジスタＲ１Ａに送り出されるようになつ
ている。ここで、上記第５ステツプと第７ステツ
プにおいて、つぎに計算されるデータα3、α4につ
いてのバタフライ演算の第１ステツプと第３ステ
ツプが実行されている。このため第５ステツプと
第７ステツプでは、データα3、α4に関するアドレ
ス信号がレジスタ群RDM１に取り込まれてお
り、第７ステツプにおいて、アドレス信号P1が
レジスタ１３に、アドレス信号P2がレジスタ１
４に送られるようになつている。ところで、つぎ
の第８ステツプでは、レジスタ群RDM１のレジ
スタ１４にストアされているアドレス信号P2が、
選択信号S4によりマルチプレクサ１５で選択さ
れ、データメモリDMAに送られるようになつて
いる。アドレス信号P2によつてアドレス指定さ
れたデータメモリDMAには、レジスタＲ１Ａに
ストアされていた演算出力であるデータB2が、
データA2の記憶されていた同じアドレスに格納
されるようになつている。このデイジタルデータ
B2は、デイジタルデータα1、α2のバタフライ演
算出力であるデータβ2の実部に相当している。ま
た、この同じステツプで、レジスタＲ４Ａにスト
アされていたデータA1が加減算器ALUAに送ら
れる。また、このデータA1には、加減算器
ALUAにストアされているＷが加算され、加算
されて得られた演算出力B1＝A1＋Ｗが同じステ
ツプでレジスタＲ１Ａに送り出されるようになつ
ている。つぎの第９ステツプは、ステツプ数を合
わせるため空ステツプとなつており、何も実行さ
れないようになつている。この第９ステツプから
は、たとえば一対のデイジタルデータα5、α6につ
いてのさらにつぎのバタフライ演算の第１ステツ
プが開始されるようになつている。このため、こ
の第９ステツプにおいて、たとえばデータα6につ
いてのアドレス信号がレジスタ群RDM１に取り
込まれるため、上記アドレス信号P1はレジスタ
１４に移動するようになつている。つぎの第１０
ステツプでは、レジスタ群RDM１のレジスタ１
４にストアされているアドレス信号P1が、選択
信号S4によりマルチプレクサ１５で選択され、デ
ータメモリDMAに送られるようになつている。
アドレス信号P1によつてアドレス指定されたデ
ータメモリDMAには、レジスタＲ１Ａにストア
されていた演算出力であるデータB1が、データ
A1の記憶されていた同じアドレスに格納される
ようになつている。このデイジタルデータB1は、
バタフライ演算出力であるデータβ1の実部に相当
している。つぎの第11ステツプおよび第12ステツ
プは、ステツプ数を合わせるための空ステツプと
なつており、何も実行されないようになつてい
る。このようにして、バタフライ演算出力である
データβ1、β2の実部B1、B2が計算されるように
なつている。なお、最後のバタフライ演算につい
ては、第８ステツプおよび第10ステツプで選択信
号S2等を利用して、アドレス信号を選択するよう
にしてもよい。 ところで、データβ1、β2の虚部b1、b2を求める
ための計算は、乗算器MPYBおよび加減算器
ALUBまたレジスタＲ１Ｂ等を利用して行なわ
れ、上述した実部B1、B2を求める計算手順と同
一の手段で行なわれるようになつている。したが
つて、虚部b1、b2を計算する手順の説明を省略す
る。なお、表２中でＸは Ｘ＝cosθ・a2−sinθ・A2 を表わしている。 このように、上記バタフライ演算回路１では、
第１ステツプおよび第３ステツプで、バタフライ
演算されるデイジタルデータα1、α2の記憶されて
いるデータメモリDMA，DMBのアドレスP1、
P2をアドレス生成部AGで計算している。また、
第２ステツプと第３ステツプとで、係数ｋの記憶
されている係数メモリCMのアドレスQ1、Q2がア
ドレス生成部AGで計算されるようになつてい
る。そして、上記レジスタ群RDM１に上記アド
レスP1、P2がストアされるようになつている。
このため、バタフライ演算結果であるデイジタル
データβ1、β2のデータメモリDMA，DMBに格納
される上記アドレスP1、P2の計算がアドレス生
成部AGでもう一度行なわれることなく、第８ス
テツプおよび第10ステツプにおいて選択信号によ
り選択され再使用されるようになつている。した
がつてデータメモリDMA，DMBおよび係数メ
モリCMへのアクセス回数は１つのバタフライ演
算あたり６回必要であるにもかかわらず、アドレ
ス生成部AGでは４回のアドレス計算を行なうの
みですむようになつている。このため、信号処理
効率を１つのバタフライ演算あたり６ステツプに
落とすことなく、４ステツプに速めることが可能
となつている。このように、レジスタ群RDM１
の設けられた上記バタフライ演算回路１では、始
めの４ステツプの動作が完了した時点で、つぎの
バタフライ演算の第１ステツプを開始できるよう
になつており、上述したように、上記第５ステツ
プから第８ステツプではつぎのバタフライ演算の
第１ステツプから第４ステツプが行なわれ、上記
第９ステツプから第12ステツプではつぎのバタフ
ライ演算の第５ステツプから第８ステツプと、さ
らにそのつぎのバタフライ演算の第１ステツプか
ら第４ステツプがそれぞれ並列的に処理されるよ
うになつている。 つぎに、1/2倍を伴うバタフライ演算を計算す
る第第３図に示すバタフライ演算回路２の構成に
ついて説明する。このバタフライ演算回路２は、
上記バタフライ演算回路１に設けられているレジ
スタＲ４Ａ、Ｒ４Ｂが設けられていないこと、ま
た上記レジスタRCM１がレジスタ群RCM２に置
き換えられていることを除いて、上記バタフライ
演算回路１と同様な構成となつている。 第４図は、第３図に示すバタフライ演算２の一
点鎖線部分の構成を示している。この第４図にお
いて、レジスタ群RCM２は、２段のシフトレジ
スタを構成する２個のレジスタ２０，２１とマル
チプレクサ２２とにより構成され、各レジスタ２
０，２１はそれぞれマルチプレクサ２２に接続さ
れるようになつている。また、取り込み信号とク
ロツク信号とが入力されるオア回路２３の出力で
あるコントロール信号が、各レジスタ２０，２１
に入力されている。上記マルチプレクサ２２に
は、たとえば１ビツトにより構成されている選択
信号t1、t2が入力され、それぞれレジスタ２０，
２１の出力が選択されるようになつている。これ
により、アドレス生成部AGからのアドレス出力
は、適切なタイミングにおいて、レジスタ２０，
２１及びマルチプレクサ２２を介して、係数メモ
リCMに送り出されるようになつている。また、
４段のシフトレジスタを構成する４個のレジスタ
２４，２５，２６，２７とマルチプレクサ２８と
により構成されているレジスタ群RDM２は、上
記バタフライ演算回路１のレジスタ群RDM１と
まつたく同様な構成となつている。これらレジス
タ２４，２５，２６，２７は、オア回路２９から
のコントロール信号が入力されており、マルチプ
レクサ２８を介して、アドレス生成部AGのアド
レス出力が適切なタイミングにおいて、データメ
モリDMA，DMBに送り出されるようになつて
いる。 表３乃至表５は、第３図に示す上記バタフライ
演算回路２により(4)式に示す1/2倍の伴うバタフ
ライ演算を(6)式によつて計算する手順を示してい
る。このバタフライ演算２では、データメモリ
DMA，DMBに記憶されるデイジタルデータα1、
α2、β1、β2は、バタフライ演算回路１と同様にア
ドレスP1、P2によつて指定されるようになつて
いる。また、係数メモリCMのアドレスQ1に係数
k/2の実部cosθ／２が記憶され、アドレスQ2に虚部 sinθ／２が記憶されている。また係数メモリCM内の 別のアドレスに数値1/2が記憶され、レジスタ群
RCM２を使用することなく、いつでも該アドレ
スを指定できるようになつている。
【表】
【表】
【表】
【表】
以上の説明から明らかなように、本発明によれ
ば、デイジタルサンプル値に基づくデイジタルデ
ータを記憶するデータメモリと、係数を記憶する
係数メモリと、上記データメモリおよび上記係数
メモリのアドレスを示すアドレスデータを演算に
より求めるアドレス生成部と、上記デイジタルデ
ータに対する乗算および加減算を行う乗算器およ
び加減算器とを有し、上記データメモリに記憶さ
れた少なくとも一対のデイジタルデータx1、x2を
バタフライ演算し、その演算結果としてデイジタ
ルデータy1、y2をそれぞれ求めるバタフライ演算
回路において、アドレスデータ記憶部に１台のア
ドレス生成部で計算されるデータメモリのアドレ
ス信号を一時保存する記憶手段であるレジスタ群
（マルチプレクサを含む）と、係数メモリCMの
アドレス信号を一時保存する記憶手段であるレジ
スタ群（マルチプレクサを含む）またはレジスタ
を設けることにより、データメモリの読み出し時
に使用するアドレス信号をしばらくの間上記レジ
スタ群に保存し、同じアドレスを２度計算するこ
となく再び使用することができ、１回のバタフラ
イ演算あたりデータメモリおよび係数メモリへの
アクセス回数が６回必要であるにもかかわらず、
アドレス生成部でのアドレス計算を４回で済ませ
て信号処理効率を４ステツプに速めることが可能
となつている。また、本発明は、アドレス生成部
をさらに一台追加するよりも非常に小さなハード
ウエア規模の追加で実現できるとともに、非常に
小さなマイクロプログラムのインストラクシヨン
の追加によつて実現することができる。
ば、デイジタルサンプル値に基づくデイジタルデ
ータを記憶するデータメモリと、係数を記憶する
係数メモリと、上記データメモリおよび上記係数
メモリのアドレスを示すアドレスデータを演算に
より求めるアドレス生成部と、上記デイジタルデ
ータに対する乗算および加減算を行う乗算器およ
び加減算器とを有し、上記データメモリに記憶さ
れた少なくとも一対のデイジタルデータx1、x2を
バタフライ演算し、その演算結果としてデイジタ
ルデータy1、y2をそれぞれ求めるバタフライ演算
回路において、アドレスデータ記憶部に１台のア
ドレス生成部で計算されるデータメモリのアドレ
ス信号を一時保存する記憶手段であるレジスタ群
（マルチプレクサを含む）と、係数メモリCMの
アドレス信号を一時保存する記憶手段であるレジ
スタ群（マルチプレクサを含む）またはレジスタ
を設けることにより、データメモリの読み出し時
に使用するアドレス信号をしばらくの間上記レジ
スタ群に保存し、同じアドレスを２度計算するこ
となく再び使用することができ、１回のバタフラ
イ演算あたりデータメモリおよび係数メモリへの
アクセス回数が６回必要であるにもかかわらず、
アドレス生成部でのアドレス計算を４回で済ませ
て信号処理効率を４ステツプに速めることが可能
となつている。また、本発明は、アドレス生成部
をさらに一台追加するよりも非常に小さなハード
ウエア規模の追加で実現できるとともに、非常に
小さなマイクロプログラムのインストラクシヨン
の追加によつて実現することができる。
第１図は本発明に係るバタフライ演算回路のブ
ロツク図、第２図は第１図の一点鎖線部分を示す
ブロツク図、第３図は本発明の他の実施例として
の1/2倍を伴うバタフライ演算を行なうバタフラ
イ演算回路のブロツク図、第４図は第３図の一点
鎖線部分を示すブロツク図、第５図は第３図の一
点鎖線部分の他の実施例を示すブロツク図であ
る。 CM……係数メモリ、DMA，DMB……データ
メモリ、MPYA，MPYB……乗算器、ALUA，
ALUB……加減算器、Ｒ１Ａ，Ｒ１Ｂ，Ｒ２Ａ，
Ｒ２Ｂ，Ｒ３Ａ，Ｒ３Ｂ，Ｒ４Ａ，Ｒ４Ｂ……レ
ジスタ、AG……アドレス生成部、RDM１，
RDM２，RDM３……レジスタ群、RCM１，
RCM３……レジスタ、RCM２……レジスタ群、
１０，１６……オア回路、１１，１２，１３，１
４……レジスタ、１５……マルチプレクサ、２
３，２９……オア回路、２０，２１，２４，２
５，２６，２７……レジスタ、２２，２８……マ
ルチプレクサ、３１，３２，３３，３４……レジ
スタ、３６……マルチプレクサ。
ロツク図、第２図は第１図の一点鎖線部分を示す
ブロツク図、第３図は本発明の他の実施例として
の1/2倍を伴うバタフライ演算を行なうバタフラ
イ演算回路のブロツク図、第４図は第３図の一点
鎖線部分を示すブロツク図、第５図は第３図の一
点鎖線部分の他の実施例を示すブロツク図であ
る。 CM……係数メモリ、DMA，DMB……データ
メモリ、MPYA，MPYB……乗算器、ALUA，
ALUB……加減算器、Ｒ１Ａ，Ｒ１Ｂ，Ｒ２Ａ，
Ｒ２Ｂ，Ｒ３Ａ，Ｒ３Ｂ，Ｒ４Ａ，Ｒ４Ｂ……レ
ジスタ、AG……アドレス生成部、RDM１，
RDM２，RDM３……レジスタ群、RCM１，
RCM３……レジスタ、RCM２……レジスタ群、
１０，１６……オア回路、１１，１２，１３，１
４……レジスタ、１５……マルチプレクサ、２
３，２９……オア回路、２０，２１，２４，２
５，２６，２７……レジスタ、２２，２８……マ
ルチプレクサ、３１，３２，３３，３４……レジ
スタ、３６……マルチプレクサ。
Claims (1)
- 【特許請求の範囲】 １ デイジタルサンプル値に基づくデイジタルデ
ータを記憶するデータメモリと、係数を記憶する
係数メモリと、上記データメモリおよび上記係数
メモリのアドレスを示すアドレスデータを演算に
より求めるアドレス生成部と、上記デイジタルデ
ータに対する乗算および加減算を行う乗算器およ
び加減算器とを有し、上記データメモリに記憶さ
れた少なくとも一対のデイジタルデータx1、x2を
バタフライ演算し、その演算結果としてデイジタ
ルデータy1、y2をそれぞれ求めるバタフライ演算
回路において、 上記アドレス生成部にて生成された上記アドレ
スデータを記憶し、記憶した上記アドレスデータ
を選択的に上記データメモリにアドレスデータと
して供給するアドレスデータ記憶部を備え、 上記アドレスデータ記憶部は、上記データメモ
リから上記デイジタルデータx1、x2が読み出され
るときのアドレスデータを記憶保持し、演算結果
である上記デイジタルデータy1、y2が上記データ
メモリに書き込まれるときに上記記憶保持してい
る上記アドレスデータを上記データメモリに供給
することにより、上記デイジタルデータx1、x2が
読み出されたアドレスと同じアドレスに演算結果
である上記デイジタルデータy1、y2が書き込まれ
るようになされていることを特徴とするバタフラ
イ演算回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58125345A JPS6017563A (ja) | 1983-07-09 | 1983-07-09 | バタフライ演算回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58125345A JPS6017563A (ja) | 1983-07-09 | 1983-07-09 | バタフライ演算回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6017563A JPS6017563A (ja) | 1985-01-29 |
| JPH0516618B2 true JPH0516618B2 (ja) | 1993-03-04 |
Family
ID=14907814
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58125345A Granted JPS6017563A (ja) | 1983-07-09 | 1983-07-09 | バタフライ演算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6017563A (ja) |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5378744A (en) * | 1976-12-23 | 1978-07-12 | Fujitsu Ltd | Arithmetic system for complex number |
-
1983
- 1983-07-09 JP JP58125345A patent/JPS6017563A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6017563A (ja) | 1985-01-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP7074363B2 (ja) | 準同型暗号下での安全な計算を加速するための準同型処理ユニット（ｈｐｕ） | |
| US6629117B2 (en) | Method for computing a fast fourier transform and associated circuit for addressing a data memory | |
| US4689762A (en) | Dynamically configurable fast Fourier transform butterfly circuit | |
| US6366936B1 (en) | Pipelined fast fourier transform (FFT) processor having convergent block floating point (CBFP) algorithm | |
| JP2002152014A (ja) | 正規最小平均二乗アルゴリズムに基づいた係数適応用ハードウエアアクセリレータ | |
| US5457805A (en) | Microcomputer enabling high speed execution of product-sum operation | |
| US6463451B2 (en) | High speed digital signal processor | |
| US5629882A (en) | Discrete cosine transformation system and inverse discrete cosine transformation system, having simple structure and operable at high speed | |
| CA1321838C (en) | Apparatus and method for flexible control of digital signal processing devices | |
| US6549925B1 (en) | Circuit for computing a fast fourier transform | |
| JPH0516618B2 (ja) | ||
| KR0147758B1 (ko) | Mpeg-2 오디오 복호화기의 합성 필터 | |
| US5204962A (en) | Processor with preceding operation circuit connected to output of data register | |
| KR19990077845A (ko) | 파이프라인된 고속 푸리에 변환 프로세서 | |
| Bowlyn et al. | A novel distributed arithmetic approach for computing a radix-2 FFT butterfly implementation | |
| JPS61213926A (ja) | Ｄｓｐ演算処理方式 | |
| JP2697619B2 (ja) | Ｎポイントｆｆｔ専用プロセッサ | |
| JPS60129890A (ja) | デイジタル信号処理装置 | |
| JP3654622B2 (ja) | Ｄｃｔ演算装置及びｉｄｃｔ演算装置 | |
| JPS63133268A (ja) | パイプライン式のｆｆｔバタフライ計算装置 | |
| JPH026089B2 (ja) | ||
| KR940007569B1 (ko) | 행렬 곱셈 회로 | |
| JPH0773161A (ja) | 演算装置 | |
| JPH0138697Y2 (ja) | ||
| JPH0721760B2 (ja) | ディジタル演算回路 |