JPH05174046A

JPH05174046A - 演算回路

Info

Publication number: JPH05174046A
Application number: JP3337343A
Authority: JP
Inventors: Hirofumi Sakagami; 弘文阪上
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1991-12-20
Filing date: 1991-12-20
Publication date: 1993-07-13

Abstract

(57)【要約】【目的】小規模なハードウエア構成で効率のよいフー
リエ演算を可能にすること。【構成】第１，２の複素数の実数部Ｂr，Ｃrと虚数部
Ｂi，Ｃiとが切換え手段Ｓ₁，Ｓ₂により選択切換えされ
て入力される１つの乗算器４１を設け、この乗算器４１
出力を累積加算又は減算する第１の加減算器４３と、乗
算結果中の実数部を保持する第１のレジスタ４５と虚数
部を保持する第２のレジスタ４６とを別個に設け、第３
の複素数の実数部Ａr とレジスタ４５に保持された実数
部出力（Ｂ・Ｃ)rとの加減算処理を行なう第２の加減算
器４７を設け、この第３の複素数の虚数部Ａi とレジス
タ４６に保持された虚数部出力(Ｂ・Ｃ)r との加減算処
理を行なう第３の加減算器４８とを設けて、高速フーリ
エ変換のバタフライ演算を行なうようにした。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、高速フーリエ変換、さ
らには、ＦＩＲフィルタの演算も可能な演算回路に関す
る。

【０００２】

【従来の技術】一般に、高速フーリエ変換（ＦＦＴ演
算）は、データ列をビット逆順の並べ換えと称される方
法に従い並べ換えを行ない、並べ換えられたデータ列を
バタフライ演算と称される２点フーリエ変換を繰返すこ
とにより、２のｎ乗で示されるデータ列のフーリエ変換
を行なうものである。このようなＦＦＴ演算は、デジタ
ル信号処理全般、ファクシミリのモデム、音声信号処理
等の分野において、周波数特性を調べる場合や相関演算
を高速に計算する場合などに広く利用される。

【０００３】ここに、ＦＦＴ演算を繰返し高速に実行し
たい場合にはプロセッサをパイプライン的に結合するこ
とになる。このような構成を持たせたものとして、例え
ば特開昭６０−７５７５号公報中に示されるような固定
小数点高速フーリエ変換方式がある。図９は固定小数点
演算で高速フーリエ変換のバタフライ演算をパイプライ
ン形式で実行するようにしたシステム構成を示すもの
で、複数のデータバッファ１とＦＦＴ演算器２とを順次
パイプライン形式で接続したものである。

【０００４】各ＦＦＴ演算器２は図１０に示すように構
成されている。即ち、入力データバッファ３の出力がデ
ータの流れを切換えるスイッチ４により直接、又は、信
号ビットに従ってデータの１ビット右シフトを行なうシ
フタ５を介して間接的に、一方の入力に与えられる乗算
器６が設けられている。この乗算器６の他方の入力とし
てはＲＯＭ７に格納された定数が与えられる。この乗算
器６の出力側には乗算結果を保持するデータレジスタ８
が設けられ、このデータレジスタ８には加算器９が接続
されている。この加算器９中には加算結果の桁あふれフ
ラグ１０が設けられている。また、加算器９の出力側に
は加算結果をデータレジスタ８側にフィードバックさせ
るかレジスタ１１側に出力させるかを切換えるスイッチ
１２が設けられている。このレジスタ１１の出力が出力
データバッファ１３を介して出力される。バッファ３，
１３間には制御情報を格納したレジスタ１４が設けられ
ている。また、各部を制御するコントローラ１５が設け
られている。

【０００５】このような構成により、固定小数点演算時
にオーバフロー（桁あふれ）が発生した場合に、オーバ
フローが発生したことを示す情報をフラグ１０により次
段側に出力し、演算結果を１ビットシフトして出力させ
ることで、フーリエ変換の最終結果の出力時に、行なわ
れたビットシフトの回数を同時に知ることができる。こ
の結果、固定小数点演算時のデータ長を最も有効に活用
して演算精度を上げることができるようにしたものであ
る。また、異なる入力データに対するフーリエ変換結果
の間の相対的なスケールの違いも補正し得るものとな
る。

【０００６】また、特開昭６１−１０１８７２号公報に
示されるようなＦＦＴ演算回路もある。これは、高速フ
ーリエ変換のバタフライ演算を実行する時の複素数の演
算について、実数部の演算と虚数部の演算とを独立して
実行できるように、例えば、図１１に示すように、係数
メモリ１６，１７、乗算器１８，１９、加減算器２０，
２１及びデータメモリ２２，２３等による演算回路を２
系統設けたものである。ここに、各系統毎に３つずつの
レジスタ２４〜２９が設けられている。

【０００７】

【発明が解決しようとする課題】ところが、前者の特開
昭６０−７５７５号公報方式の場合、基本的に固定小数
点演算方式であるため、演算精度に限界がある。また、
パイプライン形式であるため、ハードウエア規模が大き
くなってしまう。

【０００８】また、後者の特開昭６１−１０１８７２号
公報方式の場合、乗算器１８，１９を２個必要とするた
め、ハードウエア規模が大きくなってしまう。また、実
数部用と虚数部用との２系統の演算回路間で交互にデー
タの入出力を行なう必要があり、制御が複雑となってし
まう。

【０００９】

【課題を解決するための手段】請求項１記載の発明で
は、第１ないし第３の３つの複素数の内、第１及び第２
の複素数の実数部と虚数部とが切換え手段により選択切
換えされて入力される乗算器と、この乗算器出力を累積
加算又は減算する第１の加減算器と、前記乗算器による
第１及び第２の複素数の乗算結果中の実数部を保持する
第１のレジスタと、この乗算結果中の虚数部を保持する
第２のレジスタと、第３の複素数の実数部と前記第１の
レジスタに保持された実数部出力との加減算処理を行な
う第２の加減算器と、第３の複素数の虚数部と前記第２
のレジスタに保持された虚数部出力との加減算処理を行
なう第３の加減算器とよりなり、高速フーリエ変換のバ
タフライ演算を行なうようにした。

【００１０】この際、請求項２記載の発明では、乗算器
及び第１ないし第３の各加減算器を浮動小数点演算を行
なうものとした。

【００１１】また、請求項３記載の発明では、これらの
発明において、第１のレジスタの出力値を選択的に外部
に出力するためのＦＩＲ用出力端子を設けて、第１及び
第２の複素数の実数部が乗算器に対する入力となるよう
に切換え手段を固定するとともに、第１の加減算器を加
算モードに設定し、前記乗算器による乗算結果について
この第１の加減算器により累積加算した値を前記第１の
レジスタに一旦保持させた後、前記ＦＩＲ用出力端子か
ら出力させるようにした。

【００１２】請求項４記載の発明では、このような請求
項３記載の発明に加え、第２の加減算器に対して外部か
らの入力値を選択的に入力させるための入力端子とこの
第２の加減算器の出力値を選択的に外部に出力するため
の出力端子とを設けるとともに、この第２の加減算器を
加算モードに設定し、前記入力端子からの入力値と第１
のレジスタからの出力値とをこの第２の加減算器により
累積加算し、その結果を前記出力端子から外部に出力さ
せるようにした。

【００１３】また、請求項５記載の発明では、請求項１
記載の発明に加えて、複素数中の実数部のデータを記憶
するＮワードの第１及び第２のメモリと、複素数中の虚
数部のデータを記憶するＮワードの第３のメモリと、デ
ータの正負を反転させる符号反転回路とを設け、実数部
のデータを前記第１のメモリと前記第２のメモリとの内
の一方のメモリに入力させて所定データ量に達した後
は、他方のメモリに切換えて入力させ、この他方のメモ
リに所定データ量のデータを入力し終わるまでの期間中
に、データ入力済みの前記一方のメモリ中のデータと前
記第３のメモリ中のデータとを用いてフーリエ変換又は
逆フーリエ変換の演算を行ない、フーリエ変換時にはフ
ーリエ変換後の（Ｎ／２−１）ワードの虚数部のデータ
を前記一方のメモリに記憶させる一方、逆フーリエ変換
時には前記一方のメモリ中に記憶された（Ｎ／２−１）
ワード分の虚数部のデータを必要に応じて符号反転回路
により符号反転させて乗算器に入力させて演算を行な
い、前記第３のメモリを虚数部用作業領域として用い前
記第１，２のメモリに交互にデータを入力させながらバ
タフライ演算を繰返すようにした。

【００１４】また、請求項６記載の発明では、請求項３
又は４記載の発明に加えて、時系列データによる複素数
中の実数部のデータを記憶するＮワードの第１及び第２
のメモリと、ＦＩＲフィルタの各タップ係数のデータを
記憶するＮワードの第３及び第４のメモリとを設けて、
ＦＩＲフィルタ演算を行なうようにした。

【００１５】さらに、請求項７記載の発明では、乗算器
の出力を入力側に選択的にフィードバックさせる切換え
回路と、窓関数を記憶したメモリとを設け、前記乗算器
により時系列データに前記メモリに記憶された窓関数を
乗算した後で高速フーリエ変換のバタフライ演算を行な
うようにした。

【００１６】

【作用】請求項１記載の発明によれば、１個の乗算器を
使用し、複素数の乗算結果の実数部と虚数部とを各々独
立して保持する第１，２のレジスタを有し、各々の加減
算を同時に並行して行なうため、小さなハードウエア規
模にして、複素数演算の効率のよいものとなる。

【００１７】また、請求項２記載の発明によれば、乗算
器や加減算器として浮動小数点演算によるものを用いて
いるため、固定小数点演算方式によるものに比して演算
精度の高いものとなる。

【００１８】さらに、請求項３記載の発明によれば、乗
算し加算した結果をＦＩＲ用出力端子により外部に出力
し得るので、フーリエ変換だけでなく、ＦＩＲ（有限イ
ンパルス応答）フィルタ演算を行なうことも可能とな
る。

【００１９】この際、請求項４記載の発明によれば、外
部からの入力値と内部での乗算及び加算結果とを加算
し、この加算結果を外部に出力し得るので、複数の演算
回路を縦列接続して使用できるものとなり、より多くの
タップを持つＦＩＲフィルタを実現できることになる。

【００２０】また、請求項５記載の発明によれば、フー
リエ変換後の最初の（Ｎ／２−１）個の実数部のデータ
と、最初の（Ｎ／２−１）個の虚数部のデータとを入出
力するようにしたので、データ転送量が減少するものと
なり、Ｎワードの実数部用のメモリのみを２個使用し、
虚数部用のメモリとしては１個使用するだけで、リアル
タイム処理が可能となる。

【００２１】さらに、請求項６記載の発明では、フーリ
エ変換用にはＮワードのメモリを３個使用するが、ＦＩ
Ｒフィルタ用として使用する時には、Ｎワードのメモリ
を１個追加しているので、４個のメモリの内、２個を時
系列データ用として用い、残りの２個をＦＩＲフィルタ
係数用に使用すればよく、フーリエ変換とＦＩＲフィル
タ演算とを共用する際に、メモリの使用効率のよいもの
となる。

【００２２】また、請求項７記載の発明によれば、乗算
結果をその乗算器の入力側にフィードバックさせるもの
とし、かつ、窓関数用のメモリを有しているので、容易
に窓関数と時系列データとの乗算、即ち、周波数分析時
に必要な窓関数の演算も可能となる。

【００２３】

【実施例】本発明の一実施例を図１ないし図８に基づい
て説明する。本実施例は、高速フーリエ変換を実行する
時に必要なバタフライ演算を行なう演算回路であり、Ｆ
ＩＲフィルタ演算をも可能としたものである。

【００２４】まず、図２によりバタフライ演算方法の基
本を説明する。図中、Ａ，Ｂはバタフライ演算の入力
値、Ｃはフーリエ変換係数、Ｐ，Ｑはバタフライ演算の
出力値である。ここに、ＢとＣとを乗算する乗算器３１
と、この乗算結果とＡとを加算する加減算器３２と、加
算結果とＡとを減算する加減算器３３とが設けられてい
る。これらのＡ，Ｂ，Ｃ，Ｐ，Ｑは全て複素数であり、
各値の関係は、Ｐ＝Ａ＋Ｂ・Ｃ ………………………(１) Ｑ＝Ａ−Ｂ・Ｃ ………………………(２) のようになる。

【００２５】ここに、各複素数を実数部と虚数部とに分
けると、Ａ＝Ａr ＋ｉ・Ａi …………………(３) B=Br ＋ｉ・Ｂi …………………(４) Ｃ＝Ｃr ＋ｉ・Ｃi …………………(５) Ｐ＝Ｐr ＋ｉ・Ｐi …………………(６) Ｑ＝Ｑr ＋ｉ・Ｑi …………………(７) のように示すことができる。ただし、ｉは「−１」の平
方根を示すものする。

【００２６】従って、出力値Ｐ，Ｑの実数部、虚数部
は、各々Ｐr ＝Ａr ＋（Ｂr・Ｃr−Ｂi・Ｃi） ………(８) Ｐi ＝Ａi ＋（Ｂi・Ｃr＋Ｂr・Ｃi） ………(９) Ｑr ＝Ａr −（Ｂr・Ｃr−Ｂi・Ｃi） ………(10) Ｑi ＝Ａi −（Ｂi・Ｃr−Ｂr・Ｃi） ………(11) のように表される。

【００２７】このように、バタフライ演算は、複素数の
積和演算であるため、各複素数の実数部と虚数部とを別
々に計算する必要がある。

【００２８】このため、本実施例では、図１に示すよう
な構成でバタフライ演算を行なうための演算ユニット３
４が設けられている。まず、複素数Ａ，Ｂ中の実数部Ａ
r，Ｂrを入力するための第１入力端子Ｉ₁と、複素数
Ａ，Ｂ中の虚数部Ａi，Ｂiを入力するための第２入力端
子Ｉ₂と、複素数（フーリエ変換係数）の実数部Ｃr及び
虚数部Ｃiを入力するための第３入力端子Ｉ₃とが設けら
れている。また、バタフライ演算には関係しないが、Ｆ
ＩＲフィルタ用の第４入力端子Ｉ₄ も設けられている。

【００２９】また、複素数Ｐ，Ｑ中の実数部Ｐr，Ｑrを
出力するための第１出力端子Ｏ₁ と、複素数Ｐ，Ｑ中の
虚数部Ｐi，Ｑiを出力するための第２出力端子Ｏ₂ とが
設けられている。また、バタフライ演算には関係しない
が、窓関数の乗算結果を出力するための第３出力端子Ｏ
₃と、ＦＩＲフィルタ用の第４出力端子Ｏ₄ も設けられ
ている。

【００３０】さらに、入力側には６個のレジスタ３５〜
４０が設けられている。レジスタ３５は第１入力端子Ｉ
₁から入力される実数部Ｂrのデータを保持するものであ
る。レジスタ３６は第２入力端子Ｉ₂から入力される虚
数部Ｂiのデータを保持するものである。レジスタ３７
は第３入力端子Ｉ₃から入力される実数部Ｃrのデータを
保持するものである。レジスタ３８は第３入力端子Ｉ₃
から入力される虚数部Ｃiのデータを保持するものであ
る。レジスタ３９は第１入力端子Ｉ₁ から入力される実
数部Ａrのデータを保持するものである。レジスタ４０
は第２入力端子Ｉ₂から入力される虚数部Ａi のデータ
を保持するものである。

【００３１】レジスタ３５，３６の読出し出力側には切
換え手段となるスイッチＳ₁ が設けられ、同様に、レジ
スタ３７，３８の読出し出力側にも切換え手段となるス
イッチＳ₂ が設けられ、これらのスイッチＳ₁，Ｓ₂を介
して乗算器４１（乗算器３１に相当する）に接続されて
いる。よって、この乗算器４１はＢr，Ｂi側のデータと
Ｃr，Ｃi側のデータとの間で乗算を行なうものである。
乗算器４１の出力側には乗算結果（Ｂr・Ｃr，Ｂi・Ｃ
i，Ｂi・Ｃr，Ｂr・Ｃi）を一時保存するためのレジス
タ４２が設けられている。このレジスタ４２の読出し出
力側には前記第３出力端子Ｏ₃ が接続されている他、第
１の加減算器４３の±入力端子に接続されている。この
加減算器４３の＋入力端子には自己の出力がこれを一時
保持するためのレジスタ４４を介して入力されている。
この加減算器４３は加算モード又は減算モードに設定自
在なものであり、（Ｂr・Ｃr−Ｂi・Ｃi）なる減算処
理、又は、（Ｂi・Ｃr＋Ｂr・Ｃi）なる加算処理を行な
うものである。

【００３２】この加減算器４３の出力側には第１，２の
レジスタとなる２つのレジスタ４５，４６が接続されて
いる。Ｂ・Ｃなる演算結果について、レジスタ４５側は
その実数部（Ｂr・Ｃr−Ｂi・Ｃi）のデータを保持し、
レジスタ４６側はその虚数部（Ｂi・Ｃr＋Ｂr・Ｃi）の
データを保持するものである。

【００３３】さらに、レジスタ４５の出力側は前記第４
出力端子Ｏ₄ に接続されているとともに、第２の加減算
器４７の±入力端子に入力されている。この加減算器４
７の＋入力端子には前記レジスタ３９の出力（Ａr ）が
入力されている（より具体的には、第４入力端子Ｉ₄も
接続自在であり、スイッチＳ₃が介在されている）。ま
た、レジスタ４６の出力側は第３の加減算器４８の±入
力端子に入力されている。この加減算器４８の＋入力端
子には前記レジスタ４０の出力（Ａi ）が入力されてい
る。

【００３４】ここに、加減算器４７，４８は何れも加算
モード、減算モードの設定が自在なものであり、 (Ｂ・Ｃ)ｒ＝Ｂr・Ｃr−Ｂi・Ｃi (Ｂ・Ｃ)ｉ＝Ｂi・Ｃr＋Ｂr・Ｃr とすると、加減算器４７では、Ａr＋(Ｂ・Ｃ)ｒなる加
算処理、又は、Ａr−(Ｂ・Ｃ)rなる減算処理を行ない、
加減算器４８では、Ａi＋(Ｂ・Ｃ)iなる加算処理、又
は、Ａi−(Ｂ・Ｃ)iなる減算処理を行なうものである。
即ち、加減算器４７が実数部用で加減算器３２に相当
し、加減算器４８が虚数部用で加減算器３３に相当す
る。

【００３５】加減算器４７の出力側にはＰr又はＱrのデ
ータを保持するレジスタ４９が接続され、第１出力端子
Ｏ₁として引出されている。加減算器４８の出力側には
Ｐi又はＱiのデータを保持するレジスタ５０が接続さ
れ、第２出力端子Ｏ₂として引出されている。また、前
記レジスタ４９の出力はスイッチＳ₄ を介して第４出力
端子Ｏ₄ にも接続可能とされている。

【００３６】なお、乗算器４１及び加減算器４３，４
５，４６は何れも浮動小数点演算を行なうものが用いら
れている。

【００３７】このような構成の演算ユニット３４の動作
について説明する。まず、最初に各レジスタ３５〜４０
には上述したような各データ（Ｂr，Ｂi，Ｃr，Ｃi，Ａ
r，Ａi）を保持させる一方、レジスタ４４の内容はクリ
アし、その出力値を０とする。また、加減算器４３は減
算モードとして動作するように設定する。そして、スイ
ッチＳ₁，Ｓ₂により、レジスタ３６，３８からＢiとＣi
とを乗算器４１に入力し、Ｂi・Ｃiなる乗算処理を行な
う。この乗算結果Ｂi・Ｃiをレジスタ４２に保持する。
そこで、加減算器４３で（０−Ｂi・Ｃi）なる減算処理
を行ない、この減算結果をレジスタ４４に保持する。

【００３８】つぎに、スイッチＳ₁，Ｓ₂を切換え、レジ
スタ３５，３７からＢrとＣrとを乗算器４１に入力し、
Ｂr・Ｃrなる乗算処理を行なう。この乗算結果Ｂr・Ｃr
をレジスタ４２に保持するとともに、加減算器４３を加
算モードとして動作するように切換え、（Ｂr・Ｃr−Ｂ
i・Ｃｉ）なる加算処理を行ない、レジスタ４５に保持
する。

【００３９】さらに、スイッチＳ₁，Ｓ₂によりレジスタ
３６，３７からＢiとＣrとを乗算器４１に入力し、その
乗算結果Ｂi・Ｃrをレジスタ４２に保持する。また、レ
ジスタ４４をクリアしその出力値を０とする。この結
果、加減算器４３は（０＋Ｂi・Ｃr）なる加算結果を出
力し、レジスタ４４に保持する。同様に、スイッチ
Ｓ₁，Ｓ₂ により、レジスタ３５，３８からＢrとＣiと
を乗算器４１に入力し、その乗算結果Ｂr・Ｃiをレジス
タ４２に保持する。この結果、加減算器４３は（Ｂi・
Ｃr＋Ｂr・Ｃi）なる加算結果を出力し、レジスタ４６
に保持する。

【００４０】その後、加減算器４７，４８をともに加算
モードに設定すると、加減算器４７は｛Ａr＋（Ｂr・Ｃ
r−Ｂi・Ｃi）｝なる加算結果を出力し、一旦、レジス
タ４９に保持した後、第１出力端子Ｏ₁ からＰr として
出力する。加減算器４８側では、｛Ａi＋（Ｂi・Ｃr＋
Ｂr・Ｃi）｝なる加算結果を出力し、一旦、レジスタ
５０に保持した後、第２出力端子Ｏ₂ からＰi として出
力する。

【００４１】一方、加減算器４７，４８をともに減算モ
ードに設定すると、加減算器４７は｛Ａr−（Ｂr・Ｃr
−Ｂi・Ｃi）｝なる減算結果を出力し、一旦、レジス
タ４９に保持した後、第１出力端子Ｏ₁からＱrとして出
力する。加減算器４８側では、｛Ａi−（Ｂi・Ｃr＋Ｂr
・Ｃi）｝なる減算結果を出力し、一旦、レジスタ５０
に保持した後、第２出力端子Ｏ₂からＱiとして出力す
る。

【００４２】このようにして、本実施例の演算ユニット
３４によれば、入力レジスタ３５〜４０に３つの複素数
Ａ，Ｂ，Ｃを設定し、１個の乗算器４１で４回乗算処理
を行なうことで、Ｂ・Ｃの演算を行ない、その実数部と
虚数部とについてレジスタ４５，４６により各々独立し
て保持した後、２個の加減算器４７，４８により、１つ
のバタフライ演算結果の実数部と虚数部とを同時に出力
することになり、請求項１，２記載の発明が構成される
ことになる。

【００４３】ところで、図１に示した構成の演算ユニッ
ト３４が、ＦＩＲフィルタ機能を持つ点について説明す
る。まず、ＦＩＲフィルタはデジタルフィルタを構成す
るための一つの手段であり、基本的には、図３に示すよ
うに、時系列データｘ_n と各定数ａ_mとの乗算器５１_nに
よる乗算結果を加算器５２により加算するといった、積
和演算で実現できるものである。時系列データｘ_n のラ
インにはＤで示す遅延素子５３が設けられている。

【００４４】これを図１で考える。まず、初期設定とし
てレジスタ４４をクリアしその出力を０とする。また、
スイッチＳ₁，Ｓ₂はレジスタ３５，３７からのＢr，Ｃr
が乗算器４１に入力されるように設定する。スイッチＳ
₄ はレジスタ４５の内容が第４出力端子Ｏ₄ から出力さ
れるように切換え設定する。加減算器４３は加算モード
に設定する。

【００４５】このような初期設定において、第１入力端
子Ｉ₁から時系列データｘ_n-mを入力し、第３入力端子Ｉ
₃ からは対応する定数（以下、ＦＩＲフィルタ係数とい
う）ａ_mを入力し、乗算器４１で乗算を行なう。その乗
算結果をレジスタ４２により保持することにより、加減
算器４３の出力にはａ_m・ｘ_n-mが得られる。この加減算
器４３の出力をレジスタ４４により保持する。次に、時
系列データｘ_n-(m-1)及びＦＩＲフィルタ係数ａ_m-1を
入力し、同様にして、乗算・加算処理を行なった結果で
あるａ_m・ｘ_n-m＋ａ_m-1・ｘ_n-(m-1)を加減算器４３より
得てレジスタ４４に保持する。このような処理を後続の
時系列データ、ＦＩＲフィルタ係数についても同様に繰
返し、ｘ_n・ａ₀までの演算が終了した時点で、全ての積
和演算結果をレジスタ４５により保持した後、スイッチ
Ｓ₄を介して第４出力端子Ｏ₄からＦＩＲフィルタ出力ｙ
_nを出力する。このようにして、請求項３記載の発明に
いうＦＩＲフィルタ演算機能を併せ持つものとなる。

【００４６】ところで、図１に示したような演算ユニッ
ト３４は図４に示すように複数のメモリ等と組合せられ
て１つの論理回路５４として構成される。このような論
理回路５４構成により、高速フーリエ変換回路として機
能させ得るが、具体的な構成・動作に先立ち、フーリエ
変換の性質として、フーリエ変換後の各値に対称性があ
る点について説明する。

【００４７】まず、フーリエ変換の定義式は(12)式のよ
うに示される。ただし、同式中のＷは(13)式のようなも
のとする。

【００４８】

【数１】

【００４９】ここに、ｋ＝０，１，…，N-1 であり、ｘ
_mとｘ_N-mとの場合について考えると、各々(14)(15)式の
ように表される。

【００５０】

【数２】

【００５１】ここで、(15)式中のＷ項は各々(16)(17)式
で示されるので、(15)式のｘ_N-m としては(18)式が導か
れる。

【００５２】

【数３】

【００５３】従って、(14)式と(18)式よりｘ_mの実数部
(ｘ_m)r、虚数部(ｘ_m)iと、ｘ_N-mの実数部(ｘ_N-m)r、虚
数部(ｘ_N-m)iとの間には、(19)(20)式に示すような関係
が成立する。

【００５４】 (ｘ_m)r ＝ (ｘ_N-m)r ………………(19) (ｘ_m)i ＝ −(ｘ_N-m)i ………………（２０）また、ｘ_Ｎ／２については、(21)式が成立し、その虚数
部は０となる。ｘ₀についても同様である。

【００５５】

【数５】

【００５６】従って、例えばＮ＝８の場合のフーリエ変
換結果では、実数部・虚数部間には(22)(23)式に示すよ
うな関係 (ｘ₁)r＝ (ｘ₇)r，(ｘ₂)r＝ (ｘ₆)r，(ｘ₃)r＝ (ｘ₅)r， ……(22) (ｘ₁)i＝−(ｘ₇)i，(ｘ₂)i＝−(ｘ₆)i，(ｘ₃)i＝−(ｘ₅)i， ……(23) が成立する。

【００５７】図５はこの様子を模式的に図示したもので
ある。片矢印は、符号が反転することを示し、両矢印は
同じ値であることを示す。従って、実質的には、ｘ₀〜
ｘ₄の実数部及びｘ₁〜ｘ₃の虚数部のデータがあれば十
分といえる。

【００５８】しかして、図４に示す演算回路５４ではこ
のような性質に着目し、フーリエ変換の入力データ及び
出力データを記憶するメモリをＮワードとし、バタフラ
イ演算を実行する時は、虚数部のデータ領域としてさら
にＮワードの１個のメモリを使用し、フーリエ変換の最
終出力結果を演算する時点で、（Ｎ／２−１）ワードの
虚数部データを実数部データ領域へ入力させ、フーリエ
変換後のデータ量を半減させるようにしたものである。
さらには、データ入出力用のＮワードのメモリのみを２
個使用する一方、虚数部用のメモリは１個使用し、２個
のメモリに交互にデータを入力し、データが一杯になっ
たメモリと虚数部用のメモリとでフーリエ変換を行な
い、リアルタイムでの処理も可能である。

【００５９】図４において、まず、フーリエ変換後のデ
ータを出力するための第５出力端子Ｏ₅と、フーリエ変
換する時系列データを入力するための第５入力端子Ｉ₅
とが設けられている。また、フーリエ変換には関係しな
いが、ＦＩＲフィルタ係数を入力するための第６入力端
子Ｉ₆ も設けられている。さらに、２ポートメモリ構成
のＲＡＭによる２つのデータ入出力用バッファメモリ
（第１，２のメモリ）５５，５６が設けられ、連動する
スイッチＳ₆，Ｓ₇を介して端子Ｏ₅，Ｉ₅に選択自在に接
続されている。また、フーリエ変換演算時に虚数部デー
タ用の作業領域となる２ポートメモリ構成のＲＡＭによ
るメモリ（第３のメモリ）５７が設けられ、さらには、
フーリエ変換時には不使用となる２ポートメモリ構成の
ＲＡＭによるメモリ（第４のメモリ）５８も設けられ、
スイッチＳ₈を介して第６入力端子Ｉ₆に接続されてい
る。ここに、メモリ５８はＦＩＲフィルタ演算時にはメ
モリ５７とともにＦＩＲフィルタ係数を記憶するための
メモリとして使用されるものである。また、メモリ５
５，５６の他方には一方を選択するためのスイッチＳ₉
が設けられ、メモリ５７，５８の他方に対しても一方を
選択するためのスイッチＳ₁₀が設けられている。

【００６０】さらに、ＦＦＴ係数（Ｗの実数部及び虚数
部）を記憶するＲＯＭ構成のメモリ５９と周波数分析用
の窓関数を記憶するＲＯＭ構成のメモリ６０とが設けら
れている。これらのメモリ５９，６０はスイッチＳ₁₁を
介して何れか一方が演算ユニット３４の第３入力端子Ｉ
₃ に入力可能とされている。また、入力データの符号を
反転、即ち、正の値は負に、負の値は正に変換するため
の符号反転回路６１も設けられている。

【００６１】また、前記メモリ５５，５６はスイッチＳ
₉ を始めとする複数のスイッチを介して演算ユニット３
４の入出力端子や符号反転回路６１に接続可能とされて
いる。まず、スイッチＳ₉ に接続されたスイッチＳ₁₂が
設けられ、そのａ端子にはスイッチＳ₁₃が接続されてい
る。このスイッチＳ₁₃のａ端子側が第１出力端子Ｏ_１に
接続され、ｂ端子側が第２出力端子Ｏ_２側に接続され
ている。また、前記スイッチＳ₁₂のｂ端子側にはスイッ
チＳ₁₄のａ端子側が接続されている。このスイッチＳ₁₄
は第１入力端子Ｉ₁ 及び符号反転回路６１に接続された
ものである。また、スイッチＳ₁₄のｂ端子側が第３出力
端子Ｏ₃ に接続されている。

【００６２】また、メモリ５７，５８もスイッチＳ₁₀を
始めとする複数のスイッチを介して演算ユニット３４の
入出力端子に接続可能とされている。まず、スイッチＳ
₁₀に接続されたスイッチＳ₁₅が設けられ、そのａ端子は
第２出力端子Ｏ₂ に接続されている。また、ｂ端子には
第２入力端子Ｉ₂ に接続されたスイッチＳ₁₆のａ端子が
接続されている。このスイッチＳ₁₆のｂ端子はスイッチ
Ｓ₁₇に接続され、符号反転回路６１の出力とこの符号反
転回路６１を経ない出力とを選択切換えし得るように構
成されている。

【００６３】このような構成において、Ｎ＝８のフーリ
エ変換をする場合を例にとり、図４の動作を説明する。
まず、スイッチＳ₆，Ｓ₇をｂ端子側に切換え、メモリ５
５に８個の時系列データを入力する。８個のデータ入力
が終了したら、スイッチＳ₆，Ｓ₇ をａ端子側に切換
え、今度はメモリ５６に時系列データを入力する。この
メモリ５６に時系列データを格納している間に、メモリ
５５に入力された時系列データについてフーリエ変換す
る。

【００６４】図６はＮ＝８の場合の高速フーリエ変換の
演算手順を模式的に示すもので、処理は、図中、左側か
ら右側に向い、合計１２回のバタフライ演算を演算ユニ
ット３４で実行することになる。まず、スイッチＳ₉ を
ａ端子、スイッチＳ₁₂をｂ端子、スイッチＳ₁₄をａ端子
側として、メモリ５５に既に格納されたデータを演算ユ
ニット３４の第１入力端子Ｉ₁ から入力させる。また、
スイッチＳ₁₀，Ｓ₁₅，Ｓ₁₆を何れもａ端子側とする。ス
イッチＳ₁₁はａ端子側とし、ＦＦＴ係数を第３入力端子
Ｉ₃ から入力させる。

【００６５】ここに、図６中に示す左側のバタフライ演
算においては、虚数部を０として入力する必要があるた
め、図１に示した演算ユニット３４内のレジスタ３６，
４０をクリアして０をセットしてバタフライ演算を実行
する。

【００６６】次に、スイッチＳ₁₆，Ｓ₁₂をａ端子側に切
換え、バタフライ演算結果の実数部をメモリ５５へ格納
し、虚数部をメモリ５７へ格納し、時系列データを書換
える。このようにして、メモリ５５，５７を使用してバ
タフライ演算を実行していく。

【００６７】そして、図６中の右側に示す最終段のバタ
フライ演算を実行する時には、まず、ｘ₀とｘ₄が出力さ
れる。この時、虚数部のデータはメモリ５７へ入力しな
くてもよいが、実数部のデータ(ｘ₀)r，(ｘ₄)rはメモリ
５５へ格納する。次に、ｘ₁とｘ₅ が出力されるが、(ｘ
₁)rをメモリ５５へ格納した後、(ｘ₁)iを(ｘ₅)rを入力
すべきアドレスに格納する。この時、スイッチＳ₁₆をｂ
端子側に切換え、スイッチＳ₁₂をａ端子側に切換える。
つづいて、ｘ₂とｘ₆とが出力される場合も同様であり、
(ｘ₂)rをメモリ５５へ格納するとともに、(ｘ₂)iを
(ｘ₆)rのアドレスに格納する。このようなフーリエ変換
の結果、メモリ５５に格納されたデータの様子を示す
と、図７のようになる。

【００６８】フーリエ変換が終了したら、メモリ５５の
データを出力する。一方、メモリ５６に８個の時系列デ
ータが入力されたら、スイッチＳ₆，Ｓ₇，Ｓ₉ を逆端子
側に切換え、上記と逆の処理、即ち、メモリ５５に対し
て時系列データの入力を行なうとともに、メモリ５６の
データを用いてフーリエ変換を行なう。

【００６９】このように、メモリ５５，５６に交互に入
力される時系列データを用い、奇数部データ領域として
は１つのメモリ５７のみを使用することで、リアルタイ
ムでフーリエ変換できるものとなり、請求項５記載の発
明にいうバタフライ演算機能を持つものとなる。

【００７０】なお、フーリエ逆変換も同様にして行なえ
るが、図７に示した形式で入力されたＮ個のデータを、
図５中の右側に示した２Ｎ個のデータに変換して演算ユ
ニット３４に入力するために、メモリ５５，５６から出
力したデータの符号を反転する必要がある場合には、符
号反転回路６１を経由するようにスイッチが切換えられ
る。

【００７１】ところで、図４に示したような構成の演算
回路５４を複数個用意し、図８に示すようにこれらの演
算回路５４を縦列接続することにより、ＦＩＲフィルタ
のタップ数を増加させることができる。この場合、演算
回路５４中のスイッチＳ₁₄，Ｓ₁₆はａ端子側とし、スイ
ッチＳ₁₂，Ｓ₁₅はｂ端子側としておく。また、演算ユニ
ット３４については、この演算ユニット３４をＦＩＲフ
ィルタ演算に使用するモードに設定しておく。さらに、
スイッチＳ₃ を第４入力端子Ｉ₄ 側に切換え、スイッチ
Ｓ₄ をレジスタ４９の出力側に切換えておき、加減算器
４７を加算モードに設定しておく。これが、請求項４記
載の発明の構成に相当する。

【００７２】このような構成とすることにより、メモリ
５５，５６に入力された時系列データと、メモリ５７，
５８に入力されたＦＩＲフィルタ係数との積和演算が行
なわれ、かつ、加減算器４７によってその前段側の演算
回路５４（図８中、自己より左側のもの）での積和演算
の結果が加算され、さらに、その結果が、後段側の演算
回路５４に入力されて同様の加算に供され、次々と加算
が行なわれることになる。そして、最終段の演算回路５
４からＦＩＲフィルタ出力が得られることになる。

【００７３】さらに、本実施例の演算回路５４が周波数
分析等でよく用いられる窓関数の乗算が可能な点につい
て説明する。まず、フーリエ変換を行なう時の図６中の
左側に示す１段目のバタフライ演算を行なう際に、ＦＦ
Ｔ係数を入力データに乗算する前に窓関数データをメモ
リ６０から出力し、スイッチＳ₁₁を経て、演算ユニット
３４の第３入力端子Ｉ₃ に入力させる。そして、乗算結
果が保持されたレジスタ４２の出力値を第３出力端子Ｏ
₃ より出力し、図４におけるスイッチＳ₁₄を介して再び
乗算器４１の入力値としてレジスタ３５で保持する。そ
の後、ＦＦＴ係数を入力してバタフライ演算を行なうこ
とで、窓関数の乗算が可能となる。このようにして、請
求項７記載の発明にいう窓関数の乗算処理が可能とな
る。

【００７４】

【発明の効果】本発明は、上述したように構成し、請求
項１記載の発明では、第１ないし第３の３つの複素数の
内、第１及び第２の複素数の実数部と虚数部とが切換え
手段により選択切換えされて入力される乗算器と、この
乗算器出力を累積加算又は減算する第１の加減算器と、
前記乗算器による第１及び第２の複素数の乗算結果中の
実数部を保持する第１のレジスタと、この乗算結果中の
虚数部を保持する第２のレジスタと、第３の複素数の実
数部と前記第１のレジスタに保持された実数部出力との
加減算処理を行なう第２の加減算器と、第３の複素数の
虚数部と前記第２のレジスタに保持された虚数部出力と
の加減算処理を行なう第３の加減算器とを設けて、高速
フーリエ変換のバタフライ演算を行なうようにしたの
で、１個の乗算器を使用し、複素数の乗算結果の実数部
と虚数部とを各々独立して保持する第１，２のレジスタ
を有する小さなハードウエア規模にして、各々の加減算
を同時に並行して行なうことができ、効率のよい複素数
演算が可能となる。

【００７５】この際、請求項２記載の発明では、乗算器
及び第１ないし第３の各加減算器を浮動小数点演算を行
なうものとしたので、従来の固定小数点演算方式による
ものに比して演算精度の高いものとすることができる。

【００７６】また、請求項３記載の発明では、これらの
発明において、第１のレジスタの出力値を選択的に外部
に出力するためのＦＩＲ用出力端子を設けて、第１及び
第２の複素数の実数部が乗算器に対する入力となるよう
に切換え手段を固定するとともに、第１の加減算器を加
算モードに設定し、前記乗算器による乗算結果について
この第１の加減算器により累積加算した値を前記第１の
レジスタに一旦保持させた後、前記ＦＩＲ用出力端子か
ら出力させるようにしたので、乗算し加算した結果をＦ
ＩＲ用出力端子により外部に出力し得るものとなり、フ
ーリエ変換機能だけでなく、ＦＩＲフィルタ演算を行な
わせることも可能となる。

【００７７】請求項４記載の発明では、このような請求
項３記載の発明に加え、第２の加減算器に対して外部か
らの入力値を選択的に入力させるための入力端子とこの
第２の加減算器の出力値を選択的に外部に出力するため
の出力端子とを設けて、この第２の加減算器を加算モー
ドに設定し、前記入力端子からの入力値と第１のレジス
タからの出力値とをこの第２の加減算器により累積加算
し、その結果を前記出力端子から外部に出力させるよう
にしたので、外部からの入力値と内部での乗算及び加算
結果とを加算し、この加算結果を外部に出力し得るもの
となり、よって、複数の演算回路を縦列接続して使用す
ることで、より多くのタップ数を持つＦＩＲフィルタを
実現できるものとなる。

【００７８】また、請求項５記載の発明では、請求項１
記載の発明に加えて、複素数中の実数部のデータを記憶
するＮワードの第１及び第２のメモリと、複素数中の虚
数部のデータを記憶するＮワードの第３のメモリと、デ
ータの正負を反転させる符号反転回路とを設けて、実数
部のデータを前記第１のメモリと前記第２のメモリとの
内の一方のメモリに入力させて所定データ量に達した後
は、他方のメモリに切換えて入力させ、この他方のメモ
リに所定データ量のデータを入力し終わるまでの期間中
に、データ入力済みの前記一方のメモリ中のデータと前
記第３のメモリ中のデータとを用いてフーリエ変換又は
逆フーリエ変換の演算を行ない、フーリエ変換時にはフ
ーリエ変換後の（Ｎ／２−１）ワードの虚数部のデータ
を前記一方のメモリに記憶させる一方、逆フーリエ変換
時には前記一方のメモリ中に記憶された（Ｎ／２−１）
ワード分の虚数部のデータを必要に応じて符号反転回路
により符号反転させて乗算器に入力させて演算を行な
い、前記第３のメモリを虚数部用作業領域として用い前
記第１，２のメモリに交互にデータを入力させながらバ
タフライ演算を繰返すようにしたので、フーリエ変換後
の最初の（Ｎ／２−１）個の実数部のデータと、最初の
（Ｎ／２−１）個の虚数部のデータとを入出力すればよ
いものとなり、データ転送量を減少させることができ、
Ｎワードの実数部用のメモリのみを２個使用し、虚数部
用のメモリとしては１個使用するだけで、リアルタイム
処理を可能とすることができる。

【００７９】また、請求項６記載の発明では、請求項３
又は４記載の発明に加えて、時系列データによる複素数
中の実数部のデータを記憶するＮワードの第１及び第２
のメモリと、ＦＩＲフィルタの各タップ係数のデータを
記憶するＮワードの第３及び第４のメモリとを設けて、
ＦＩＲフィルタ演算を行なうようにしたので、フーリエ
変換用にはＮワードのメモリを３個使用するが、ＦＩＲ
フィルタ用として使用する時には、Ｎワードのメモリを
１個追加しているので、４個のメモリの内、２個を時系
列データ用として用い、残りの２個をＦＩＲフィルタ係
数用に使用すればよいものとなり、フーリエ変換とＦＩ
Ｒフィルタ演算とを共用する際に、メモリの使用効率の
よいものとなる。

【００８０】さらに、請求項７記載の発明では、乗算器
の出力を入力側に選択的にフィードバックさせる切換え
回路と、窓関数を記憶したメモリとを設けて、前記乗算
器により時系列データに前記メモリに記憶された窓関数
を乗算した後で高速フーリエ変換のバタフライ演算を行
なうようにしたので、容易に窓関数と時系列データとの
乗算、即ち、周波数分析時に必要な窓関数の演算も可能
とするとができる。

【図面の簡単な説明】

【図１】本発明の一実施例を示す演算ユニット構成のブ
ロック図である。

【図２】バタフライ演算方法を示す模式図である。

【図３】ＦＩＲフィルタ構成の原理を示す模式図であ
る。

【図４】論理回路全体構成を示すブロック図である。

【図５】フーリエ変換の対称性特性を示すための説明図
である。

【図６】ＦＦＴ演算の一例を示す模式図である。

【図７】フーリエ変換結果の格納状態を示すメモリ模式
図である。

【図８】縦列接続例を示すブロック図である。

【図９】パイプライン結合方式の従来例を示すブロック
図である。

【図１０】そのＦＦＴ回路構成を示すブロック図であ
る。

【図１１】異なる従来例を示すブロック図である。

【符号の説明】

４１乗算器４３第１の加減算器４５第１のレジスタ４６第２のレジスタ４７第２の加減算器４８第３の加減算器５５第１のメモリ５６第２のメモリ５７第３のメモリ５８第４のメモリ６０窓関数用のメモリ６１符号反転回路Ｓ₁，Ｓ₂ 切換え手段Ｓ₁₁ 切換え回路Ｉ₄ 入力端子Ｏ₄ 出力端子Ａ第３の複素数Ｂ第１の複素数Ｃ第２の複素数

Claims

【特許請求の範囲】

【請求項１】第１ないし第３の３つの複素数の内、第
１及び第２の複素数の実数部と虚数部とが切換え手段に
より選択切換えされて入力される乗算器と、この乗算器
出力を累積加算又は減算する第１の加減算器と、前記乗
算器による第１及び第２の複素数の乗算結果中の実数部
を保持する第１のレジスタと、この乗算結果中の虚数部
を保持する第２のレジスタと、第３の複素数の実数部と
前記第１のレジスタに保持された実数部出力との加減算
処理を行なう第２の加減算器と、第３の複素数の虚数部
と前記第２のレジスタに保持された虚数部出力との加減
算処理を行なう第３の加減算器とよりなることを特徴と
する演算回路。
【請求項２】乗算器及び第１ないし第３の各加減算器
を浮動小数点演算を行なうものとしたことを特徴とする
請求項１記載の演算回路。
【請求項３】第１のレジスタの出力値を選択的に外部
に出力するためのＦＩＲ用出力端子を設けたことを特徴
とする請求項１又は２記載の演算回路。
【請求項４】第２の加減算器に対して外部からの入力
値を選択的に入力させるための入力端子とこの第２の加
減算器の出力値を選択的に外部に出力するための出力端
子とを設けたことを特徴とする請求項３記載の演算回
路。
【請求項５】複素数中の実数部のデータを記憶するＮ
ワードの第１及び第２のメモリと、複素数中の虚数部の
データを記憶するＮワードの第３のメモリと、データの
正負を反転させる符号反転回路とを設け、実数部のデー
タを前記第１のメモリと前記第２のメモリとの内の一方
のメモリに入力させて所定データ量に達した後は、他方
のメモリに切換えて入力させ、この他方のメモリに所定
データ量のデータを入力し終わるまでの期間中に、デー
タ入力済みの前記一方のメモリ中のデータと前記第３の
メモリ中のデータとを用いてフーリエ変換又は逆フーリ
エ変換の演算を行ない、フーリエ変換時にはフーリエ変
換後の（Ｎ／２−１）ワードの虚数部のデータを前記一
方のメモリに記憶させる一方、逆フーリエ変換時には前
記一方のメモリ中に記憶された（Ｎ／２−１）ワード分
の虚数部のデータを必要に応じて符号反転回路により符
号反転させて乗算器に入力させて演算を行ない、前記第
３のメモリを虚数部用作業領域として用い前記第１，２
のメモリに交互にデータを入力させながらバタフライ演
算を繰返すようにしたことを特徴とする請求項１記載の
演算回路。
【請求項６】時系列データによる複素数中の実数部の
データを記憶するＮワードの第１及び第２のメモリと、
ＦＩＲフィルタの各タップ係数のデータを記憶するＮワ
ードの第３及び第４のメモリとを設けたことを特徴とす
る請求項３又は４記載の演算回路。
【請求項７】乗算器の出力を入力側に選択的にフィー
ドバックさせる切換え回路と、窓関数を記憶したメモリ
とを設けたことを特徴とする請求項１記載の演算回路。