JPH03100863A - Ｆｆｔ演算方式及び装置 - Google Patents
Ｆｆｔ演算方式及び装置Info
- Publication number
- JPH03100863A JPH03100863A JP1237029A JP23702989A JPH03100863A JP H03100863 A JPH03100863 A JP H03100863A JP 1237029 A JP1237029 A JP 1237029A JP 23702989 A JP23702989 A JP 23702989A JP H03100863 A JPH03100863 A JP H03100863A
- Authority
- JP
- Japan
- Prior art keywords
- fft
- small
- processor
- calculation
- data
- 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.)
- Pending
Links
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
（産業上の利用分野］
本発明は、高速フーリエ変換（ＦＦＴ）の実現手段に関
する。
する。
ＦＦＴの演算は、特開昭５９−３０１６８号公報に記載
のように、互いに独立した複数の小ＦＦＴと呼ばれる処
理単位に分割することにより、並列処理が可能となる。 第１図は、６４点ＦＦＴを、第２図に示す２個×２段の
バタフライ演算から構成される小ＦＦＴにより分割した
ときのデータフロー図である。なお９図面を見易くする
ために、小ＦＦＴ及び小ＦＦＴ間を接続する線の一部を
省略した。第１図より、１０１から１３６の小ＦＦＴ、
すなわち１６個×３段のバタフライ演算に分割できるこ
とが分かる。ところで各車ＦＦＴにおけるバタフライ演
算の回転因子１４１〜１４４の値は、第１図上の小ＦＦ
Ｔの位置に応じて決定される。 第１図において、同−段の１６個の小ＦＦＴｌ０１〜１
１２．１１３〜１２４あるいは１２５〜１３６は、互い
に処理が独立である。そこで、これら同−段の小ＦＦＴ
を複数のプロセッサを用いて同時に処理することにより
、ＦＦＴの並列処理が可能になる。 一方、ＦＦＴの固定小数点演算器での実現上の問題であ
る。オーバフローと内部演算精度の維持を解決する方法
として、中間演算結果全体にある値を乗じ、データの実
質的な有効桁を向上させる方法がある。ここではこの処
理を正規化と呼び。 各段階で乗じた値の累積値を正規化量と呼ぶ。その例と
して、ｒ電子通信学会論文誌５８−Ｄ、９（１９７５年
）第５７８頁から５８５頁」で論じられているような、
オートスケーリングあるいはブロックフローティングと
呼ばれるものがある。 この正規化の手法は９個々の小ＦＦＴの演算に対しても
適用できる。しかしこの場合には９桁合わせと呼ばれる
処理が必要になる。 今、第１図における各車ＦＦＴの演算過程で正規化を行
うとき、第２及び３段の小ＦＦＴｌ１３〜１３６のよう
に、入力データが前段の小ＦＦＴの演算結果である第２
段以降の小ＦＦＴでは、入力データの正規化量が互いに
異なる。これは、入力データの小数点の位置が互いに異
なることを意味する。よってこのような小ＦＦＴでは、
処理に先立ち個々の入力データにその正規化量に応じた
ある値を乗じ、小数点の位置を一致させる必要がある。 この処理を桁合わせと呼ぶ。 このように桁合わせには、入力データ以外にその正規化
量を必要とする。よって、第２段以降の小ＦＦＴの演算
を行うとき、プロセッサは、入力データ以外にその正規
化量をアクセスする必要が生じる。
のように、互いに独立した複数の小ＦＦＴと呼ばれる処
理単位に分割することにより、並列処理が可能となる。 第１図は、６４点ＦＦＴを、第２図に示す２個×２段の
バタフライ演算から構成される小ＦＦＴにより分割した
ときのデータフロー図である。なお９図面を見易くする
ために、小ＦＦＴ及び小ＦＦＴ間を接続する線の一部を
省略した。第１図より、１０１から１３６の小ＦＦＴ、
すなわち１６個×３段のバタフライ演算に分割できるこ
とが分かる。ところで各車ＦＦＴにおけるバタフライ演
算の回転因子１４１〜１４４の値は、第１図上の小ＦＦ
Ｔの位置に応じて決定される。 第１図において、同−段の１６個の小ＦＦＴｌ０１〜１
１２．１１３〜１２４あるいは１２５〜１３６は、互い
に処理が独立である。そこで、これら同−段の小ＦＦＴ
を複数のプロセッサを用いて同時に処理することにより
、ＦＦＴの並列処理が可能になる。 一方、ＦＦＴの固定小数点演算器での実現上の問題であ
る。オーバフローと内部演算精度の維持を解決する方法
として、中間演算結果全体にある値を乗じ、データの実
質的な有効桁を向上させる方法がある。ここではこの処
理を正規化と呼び。 各段階で乗じた値の累積値を正規化量と呼ぶ。その例と
して、ｒ電子通信学会論文誌５８−Ｄ、９（１９７５年
）第５７８頁から５８５頁」で論じられているような、
オートスケーリングあるいはブロックフローティングと
呼ばれるものがある。 この正規化の手法は９個々の小ＦＦＴの演算に対しても
適用できる。しかしこの場合には９桁合わせと呼ばれる
処理が必要になる。 今、第１図における各車ＦＦＴの演算過程で正規化を行
うとき、第２及び３段の小ＦＦＴｌ１３〜１３６のよう
に、入力データが前段の小ＦＦＴの演算結果である第２
段以降の小ＦＦＴでは、入力データの正規化量が互いに
異なる。これは、入力データの小数点の位置が互いに異
なることを意味する。よってこのような小ＦＦＴでは、
処理に先立ち個々の入力データにその正規化量に応じた
ある値を乗じ、小数点の位置を一致させる必要がある。 この処理を桁合わせと呼ぶ。 このように桁合わせには、入力データ以外にその正規化
量を必要とする。よって、第２段以降の小ＦＦＴの演算
を行うとき、プロセッサは、入力データ以外にその正規
化量をアクセスする必要が生じる。
上記従来技術では、ＦＦＴの演算を複数の小ＦＦＴに分
割して段階的に求め、各段階での小ＦＦＴの演算過程で
演算精度を維持するための正規化を１回以上行う演算方
式において９桁合わせを必要とする小ＦＦＴを処理する
プロセッサでは、入力データ以外にその正規化量を必要
とすることについての十分な配慮がなされていない。 このため、プロセッサが小ＦＦＴを処理する上で必要な
データ数が増大するため、より高速なメモリやデータ転
送回路が必要になる。あるいはメモリやデータ転送回路
の能力の制限により、プロセッサが必要とするデータを
転送できないためにオーバヘッドが発生し、並列化の効
果が十分に得られないという問題があった。 本発明の目的は、より高速化が可能なＦＦＴ演算方法を
提供することにある。 本発明の他の目的は、より高速化が可能なＦＦＴ演算装
置を提供することにある。
割して段階的に求め、各段階での小ＦＦＴの演算過程で
演算精度を維持するための正規化を１回以上行う演算方
式において９桁合わせを必要とする小ＦＦＴを処理する
プロセッサでは、入力データ以外にその正規化量を必要
とすることについての十分な配慮がなされていない。 このため、プロセッサが小ＦＦＴを処理する上で必要な
データ数が増大するため、より高速なメモリやデータ転
送回路が必要になる。あるいはメモリやデータ転送回路
の能力の制限により、プロセッサが必要とするデータを
転送できないためにオーバヘッドが発生し、並列化の効
果が十分に得られないという問題があった。 本発明の目的は、より高速化が可能なＦＦＴ演算方法を
提供することにある。 本発明の他の目的は、より高速化が可能なＦＦＴ演算装
置を提供することにある。
上記の目的を達成するために２例えば第１図の第２段の
小ＦＦＴ１１３〜１１６において、各車ＦＦＴの入力デ
ータの正規化量は、これら入力データが全て同じ小ＦＦ
Ｔｌ０Ｉ〜１０４から得られることから、互いに等しい
ことに着目し、このような演算に必要な正規化量が等し
い小ＦＦＴの演算を、同一プロセッサで行うようにした
。 上記他の目的を達成するために、演算過程で正規化を１
回以上行う小ＦＦＴの演算が可能な複数のプロセッサと
、各プロセッサが小ＦＦＴの演算に必要となるデータを
転送するデータ転送手段とを有し、データ転送手段が、
必要な正規化量が等しい小ＦＦＴの演算に用いるデータ
を、同一のプロセッサに逐次供給することにより、当該
小ＦＦＴの演算を行うようにした。 （作用］ プロセッサは、同一の正規化量を用いて複数の小ＦＦＴ
の演算を行うことができるので、プロセッサが必要とす
る正規化量の数を減少できる。あるいは、１つの正規化
量は、ある１つのプロセッサしか必要としなくなるので
、正規化量をプロセッサ間で転送する回数を低減できる
。よって、高速なメモリやデータ転送回路が不要になる
。あるいはメモリやデータ転送回路の・能力の制限から
くるオーバヘッド発生の問題を低減できる。
小ＦＦＴ１１３〜１１６において、各車ＦＦＴの入力デ
ータの正規化量は、これら入力データが全て同じ小ＦＦ
Ｔｌ０Ｉ〜１０４から得られることから、互いに等しい
ことに着目し、このような演算に必要な正規化量が等し
い小ＦＦＴの演算を、同一プロセッサで行うようにした
。 上記他の目的を達成するために、演算過程で正規化を１
回以上行う小ＦＦＴの演算が可能な複数のプロセッサと
、各プロセッサが小ＦＦＴの演算に必要となるデータを
転送するデータ転送手段とを有し、データ転送手段が、
必要な正規化量が等しい小ＦＦＴの演算に用いるデータ
を、同一のプロセッサに逐次供給することにより、当該
小ＦＦＴの演算を行うようにした。 （作用］ プロセッサは、同一の正規化量を用いて複数の小ＦＦＴ
の演算を行うことができるので、プロセッサが必要とす
る正規化量の数を減少できる。あるいは、１つの正規化
量は、ある１つのプロセッサしか必要としなくなるので
、正規化量をプロセッサ間で転送する回数を低減できる
。よって、高速なメモリやデータ転送回路が不要になる
。あるいはメモリやデータ転送回路の・能力の制限から
くるオーバヘッド発生の問題を低減できる。
以下本発明の第１の実施例について述べる。
第３図は、Ｎ点ＦＦＴを構成するバタフライ演算と分割
した小ＦＦＴとの関係の概略を示したものである。ここ
で、１はＮ点ＦＦＴに必要な（Ｎ／２）個×Ｍ段のバタ
フライ演算を表す。但し。 Ｍ ＝ ｌｏｇ、 Ｎである。今、小ＦＦＴ２〜６の大
きさを（Ｑ／２）個×Ｐ段のバタフライ演算であるとす
る。但し、 ｐ＝ｌｏｇ、Ｑである。このときＮ点ＦＦ
Ｔは、Ｒ段×Ｓ個の小ＦＦＴに分割できる。ここで、Ｒ
＝Ｍ／Ｐ且つＳ＝Ｎ／Ｑである。なお。 第３図上で左上を原点とし、そこから右にｒ段。 下にＳ個の位置の小ＦＦＴを、第ｒ段第Ｓ番目の小ＦＦ
Ｔと呼び、Ｈ（ｒ、５）（ｒ＝１，２．−Ｒ；５＝＝１
．２．・・・、Ｓ）と表すことにする。 第４図は、第３図のＲ段×Ｓ個の小ＦＦＴをＵ個のプロ
セッサで処理するときの処理手順を示すものである。ま
ずＮ点ＦＦＴの原始データ（Ｎ個）をビットリバース順
に並び替える処理７を行う９次にＲ段×Ｓ個の小ＦＦＴ
の演算８，９を行う。 最後に全ての演算結果を対象にした桁合わせの処理１０
を行うことにより、Ｎ点ＦＦＴを終了する。 各車ＦＦＴの演算過程でそれぞれ独立した正規化を行う
とき、第２段目以降の小ＦＦＴの演算では９桁合わせの
処理が必要になる。そこで、この桁合わせの処理でのオ
ーバヘッドを減少させるために、Ｒ段×Ｓ個の小ＦＦＴ
の演算８，９のうち。 第１段（ｒ≧２）の小ＦＦＴの演算９を第５図に示す処
理手順により行う。 第５図は、Ｕ番目のプロセッサ（以下プロセッサＵと呼
ぶ：ｕ＝１．２．・・・、Ｕ）における第ｒ段（ｒ≧２
）の小ＦＦＴの処理手順を示すものである。まず、第ｒ
段小ＦＦＴのうち必要な正規化量が等しい小ＦＦＴの番
号（Ｈ（ｒ、ｓ）のＳ）の導出２１を行う。このような
第ｒ段小ＦＦＴはＱ個存在し、その番号を？ （Ｓｉｔ
８２．”’ｊ ５Ｑ）１（ｉ＝１．２．・・・、Ｓ／
Ｑ）と表すことにする。 ここで添字ｉは、このＱ個の第ｒ段小ＦＦＴに対応する
固有の値であり、各々の番号”１１８！Ｉ・・・ｆｉＱ
と１対１に対応する。よって添字ｉが異なると、その番
号＄１１８２１・・・、ｓｅは全て異なる。 次に、処理２１で導出された（Ｓ工、ｓ２．・・・、５
Ｑ）１の中のあるＳｑ （ｑ＝１，２．・・・、Ｑ）
番目の第ｒ段小ＦＦＴＨ（ｒ、Ｓ’ｔ ）の処理２２を
行う。 ２２の処理は、 Ｈ（ｒ、 ｓｑ ）の入力データの桁
合わせを行う処理２３と、（Ｑ／２）個×Ｐ段のバタフ
ライ演算の処理２４からなる。なお２４の処理では、演
算過程で正規化が行われる。この２２の処理は、２５の
条件分岐及び２６の処理する小ＦＦＴの番号の更新の処
理により、処理２１で導出したＱ個の番号の第ｒ段小Ｆ
ＦＴＨ（ｒ、ｓｌ） ｔ Ｈ（ｒｅ ８２） ｇ ・・
・ｇ Ｈ（ｒｅ ｓＱ ）の処理を全て終えるまで繰り
返される。 以上２１〜２６の処理の終了後、２７の条件分岐により
、必要な正規化量が等しいＱ個の第ｒ段小Ｆ ＦＴＨ（
ｒ、 ｓ、） 、 Ｈ（ｒ、 ｓ２） 、 −、Ｈ（ｒ
、ｓＱ）であって、まだ処理を終えておらず且つプロセ
ッサＵで処理すべきものが存在するか否かを判定する。 これは、予めプロセッサＵが処理すべきＱ個の小ＦＦＴ
の番号（ｓｌ、ｓ２．”’、ｓＱ）息の添字ｉを決めて
おき、処理済みの添字との比較から、あるいは、まだど
のプロセッサでも処理されていないＱ個の小ＦＦＴＨ（
ｒ、Ｓｌ）、Ｈ（ｒ ｓ ９ｚ） ＋ ”’＋ Ｈ（ｒ
ｇ ｓＱ）の存在の有無を調べることなどから可能で
ある。その結果、プロセッサＵで処理すべきものが存在
する場合には。 ２１〜２６の処理を再度繰り返す。このとき処理２１は
この新たな添字ｉを有するＱ個の第ｒ段小ＦＦＴの番号
（５１，８２，・・’、５Ｑ）ｔ を導出する。 次に、第５図での２１及び２２の処理について。 詳細に説明する。 ２１の処理で導出される。Ｑ個の第ｒ段小ＦＦＴの番号
Ｓｑ （ｑ＝１，２．・・・、Ｑ）は９次式より導出
する。 ５ｑ＝Ｑ”−”ｘｄｉｖ（（ｉ １）／Ｑ”−”）＋
ｍｏｄ（（ｉ −１）／ Ｑ””） ＋（（１−１）ＸＱ”−”＋１ （１）但しｅ
ｌ ”（Ｓ１ｔｓｌ＋”・ｔｓＱ）ｌ の添字ｅｘ＝Ｌ
２、・・・、（Ｓ／Ｑ）。 ｄｉｖ （ｕ／ｖ）： ｕ／ｖの商。 ｓｏｄ （ｕ／ｖ）： ｕ／ｖの余り。 第６図は、２２の処理すなわちＨ（ｒ、 Ｓｑ ）の処
理の内容をデータフロー図で示したものである。Ｈ（ｒ
、 ｓｑ ）の処理とは、 ｈ （０） 〜ｈ（Ｑ−１
）に対して９桁合わせの処理３１と（Ｑ／２）個ｘｐ段
のバタフライ演算３２を行うことである。それぞれ第５
図における２３の処理及び２４の処理に対応する６ Ｈ（ｒｅｓｑ）の入力データｈ （０） 〜ｈ （Ｑ−
１）とＮ点ＦＦＴの原始データｘ（０）〜ｘ（Ｎ−１）
との関係は、以下のようになる。但しＮ点ＦＦＴの原始
データは、既にビットリバース順に並び変えられている
ものとする。 ｈ （ｋ） ＝ ｘ （Ｑ’Ｘｄｉｖ（（ｓｑ −１）／ Ｑ”−１
））＋ｍｏｄ（（ｓ ｑ −１）／ Ｑ”−１））＋ｋ
ＸＱ”−”） （２）但し、 ｈ （ｋ
） ：小ＦＦＴＨ（ｒ、 ｓｑ ）のに個目の入力デー
タ。ｋ＝０゜ １、・・・ ｘ（ｎ）：Ｎ点ＦＦＴのｎ個目の原始データ。ｎ冨０，
１．・・・ ｄｉｖ （ｕ／ｖ）： ｕ／ｖの商。 ｌ１ｏｄ （ｕ／ｖ） ： ｕ／ｖの余り。 ３１の桁合わせの処理は、Ｈ（ｒ、ｓｑ）の入力データ
ｈ （ｋ）に、それぞれの正規化量に従って、定数Ｄｗ
（Ｗ ＝１ ｅ ２ ｔ −＋ Ｑ）を乗じること
により行われる。（１）式で導出したＱ個の第ｒ段小Ｆ
ＦＴにおけるＤｌは、 Ｈ（ｒ、 Ｓｑ ）での正規化
量をＥ （ｒ、 ｓｑ ）とすると９次式から求められ
る。 Ｄｗ”：５ｉｎ（Ｅ （ｒ−１，ｓ ｚＬ Ｅ （ｒ−
１，Ｓ ｚＬ−・・Ｅ （ｒ−１，ｓ ｅ））／ Ｅ
（ｒ−１，ｓ−） （３）但しｇ Ｉ＠Ｉｎ （ｕ
ｌＩｕｚｇ”’ｇ ｕｖ） ： ｕＬＨＬ１２ｇ°°
。 ｕｖの最小値。 すなわち、Ｑ個の小ＦＦＴの演算に必要な正規化量は、
いずれもＥ（ｒ−１＊ ５１）Ｉ Ｅ （ｒ−１ｓ
ｓｚ） ｅ −Ｅ （ｒ−１） ＳＱ） と等しく
なる。 ３２の（２／Ｑ） 個ｘｐ段のバタフライ演算の処理は
、Ｑ点ＦＦＴの演算とアルゴリズム的に全く同一である
ことから、一般に用いられているＦＦＴの処理アルゴリ
ズムにより実現できる。但し。 各バタフライ演算で乗じる回転因子の値は、Ｑ点ＦＦＴ
の場合と異なる。 今、第６図上で第０段（ｕ ＝ １ 、２ 、− Ｐ
）の（Ｑ／２）個のバタフライ演算の中で、上からＶｆ
ｈＩｌｌｌ（ｖ＝１．２．・・・Ｑ）のバタフライ演算
で用いる回転因子を＠Ｗｕｖと表す。このＷ ｕ ｖは
９次式より導出される。 Ｗｕｖ ＝ｅｘｐ（−ｊ（２π／ Ｎ） Ｘ ｃ ）ｃ
−＝Ｉｌｏｄ（（ｖ −１）／ ２ （ｕ”）） Ｘ
Ｑｃｒ−ｘ＞＋ｍｏｄ（（ｓｑ １）／Ｑ”−”）
（４）すなわち３２の処理は、処理アルゴリズムと
してＦＦＴアルゴリズムを用い２乗じる回転因子は（５
）式より導出することから実現できる。 以上のように、第ｒ段（ｒ≧２）の小ＦＦＴのうち、必
要な正規化量が等しいＱ個の小ＦＦＴの番号ＳＭ （
ｑ ＝ １ ｔ ２１ ・・・＊ Ｑ）を（１）式より
導出し、これらの番号の小ＦＦＴＨ（ｒ、ｓ工）。 Ｈ（ｒ＋ ｓｚ） ｅ ・・・＊ Ｈ（ｒ、 ｓＱ
） を同一プロセッサで処理する。すると、同一プロ
セッサで処理するこれら小ＦＦＴの演算に必要な正規化
量が等しくなるので、プロセッサに転送する正規化量の
数を削減できる。あるいはこれらの正規化量は。 同一プロセッサで処理する小ＦＦＴと１対１に対応する
ことから、１つの正規化量は、ある１つのプロセッサし
か必要としなくなり、正規化量をプロセッサ間で転送す
る回数を低減できる。よって。 高速なメモリやデータ転送回路が不要になる。あるいは
メモリやデータ転送回路の能力の制限からくるオーバヘ
ッド発生の問題を低減できることから、より高速なＦＦ
Ｔの演算が可能になる。 以下本発明の第２の実施例について述べる。 第７図は、第２の実施例の構成図である。第７図におい
て、６０はデータ転送ユニット、４１〜４３はプロセッ
サである。データ転送ユニットは。 共有メモリ４０とバス４４から構成される。共有メモリ
上には、少なくともＦＦＴの原始データ。 中間演算結果、最終演算結果を格納する領域４５と、こ
れらデータの正規化量を格納する領域４６とを有する。 そしてプロセッサが必要とするデータを、共有メモリか
らバスを介して転送する。 各プロセッサは９局所メモリ４７とデータ処理部４８．
アドレス発生部４９．制御部５０から構成される。そし
て、制御部からの指示により、アドレス発生部及びデー
タ処理部が有機的に働き。 共有メモリ上あるいは局所メモリ上のデータに対する処
理を行う。 ところで、共有メモリと各プロセッサ間のデータ転送は
単一のバスにより行うため、複数のプロセッサが同時に
共有メモリをアクセスすると、バス上でデータの衝突が
生じる。この問題は、各プロセッサの制御部により各々
のプロセッサが共有メモリをアクセスするタイミングを
互いに少しずつずらす、あるいはバスアービタを用いる
などの工夫により解決しているものとする。このような
ＦＦＴ演算装置は２例えば市販されている乗算器やメモ
リなどを組み合わせて、あるいはＤＳＰ（ディジタル
シグナル プロセッサ： ｐｉｇｉｔａｌＳｉｇｎａｌ
Ｐｒｏｃｅｓｓｏｒ）を用いることなどにより実現で
きる。 本実施例によるＮ点ＦＦＴの演算は、先の第１の実施例
で述べたＦＦＴ演算方法に基づいて行う。 以下２本実施例によりＮ点ＦＦＴを処理するときのデー
タの流れ及び各部の動作について、第４図及び第５図に
従って述べる。なお、処理開始時点において、ＦＦＴの
原始データ（Ｎ個）は、既に共有メモリ上に格納されて
いるものとする。 まず、第４図の７の処理を行う。これは２例えば各プロ
セッサが共有メモリ上のＮ個のＦＦＴ原Ａとそのビット
リバース位置である範囲Ｂの原始データをそれぞれ局所
メモリ上に転送する。そして、帰所メモリ上の範囲Ａの
データをそのビットリバース位置である共有メモリ上の
範囲Ｂに９局所メモリ上の範囲Ｂのデータをそのビット
リバース位置である共有メモリ上の範ＭＡにそれぞれ転
送することにより実現する。 第２に、第４図の８の処理を行う。これは、各プロセッ
サが共有メモリ上のＮ個のＦＦＴ原始データのうち、プ
ロセッサ毎に異なる小ＦＦＴの入力データ（Ｑ個）を局
所メモリ上に転送した後。 データ処理部でこの局所メモリ上の入力データに対して
、演算過程で正規化を１回以上行う小ＦＦＴの演算を行
い、その結果得られた演算結果（Ｑ個）と正規化量（１
個）を、アドレス発生部を用いて再び共有メモリ上に転
送することにより実現する。演算結果は小ＦＦＴの入力
データが格納されていた同一アドレスに、正規化量は処
理した小ＦＦＴの番号に対応したアドレスに格゛納され
る。 第３に、第４図の９の処理、すなわち第５図の処理を行
う。なお、第２段以降の小ＦＦＴの処理において、各プ
ロセッサで処理すべきＱ個の小ＦＦＴの番号（ｓｘｅ
ｓｚ＋”’ｔ １ｉＱ）１の添字ｉは、予め次のように
決定しておくものとする。すなわち。 プロセッサＵで処理すべきＱ個の小ＦＦＴの番号（５１
１５２１”’ｐｓＱ）、の添字ｉは。 ｕ、ｕ＋Ｕ、ｕ＋２Ｕ、−、ｕ＋ｚＵ 但し、ｚ：＝ｄｉｖ（Ｓ／ （ＱＸＵ））＋ｄｉｖ（ｍ
ａｄ（Ｓ ／ （Ｑ Ｘ Ｕ） ）／ ｕ ）−１とす
る。そしてこれらの値は、プロセッサＵに格納しておく
ものとする。 第５図の２１の処理は、データ処理部において。 予め与えられているプロセッサＵで処理すべきＱ個の小
ＦＦＴの番号（Ｓａｔｓ２＊”’＋ＳＱ）＋の添字ｉよ
り、この（Ｓｚｓ Ｓａｔ”’ｔ ＳＱＩ を（１）式
を用いて導出することにより実現できる。 第５図の２３の処理は、以下の手順で行うことができる
。 手順１： ２１の処理で得られた小ＦＦＴの番号（Ｓ□
、ｓ２．・・・、ｌ！Ｑ）ｌから２桁合わせ、すなわち
（３）式を計算するのに必要なＱ個の正規化量（Ｅ （
ｒ−１，ｓｚ ） ｓ Ｅ （ｒ−１゜ｓｔ） ｌ ・
Ｅ （ｒ−１，ｓＱ） ）を、共有メモリ上から局所メ
モリ上に転送する。 手順２： （３）式より２桁合わせに必要な定数り
、（ｗ＝１．２．−、Ｑ）をデータ処理部で求め、その
結果を局所メモリ上のＥ（ｒ−１，ｓ、） の格納位
置に書き込む。 手順３ ： Ｈ（ｒｅ ｓｑ ）のＱ個の入力データ
を、共有メモリ上から局所メモリ上に転送する。このと
き共有メモリ上の入力データのアドレスは、（２）式を
用いて導出する。 手順４： 局所メモリ上のＨ（ｒ、 Ｓｑ ）の入力デ
ータに、データ処理部を用いて手順２で求めた定数り、
を乗じ、その結果を局所メモリ上の同一アドレスに書き
込む。 また第５図の２４の処理は、引き続き以下の手順により
行う。 手順５： 手順４で求めた局所メモリ上の桁合わせを終
えたＨ （ｒｅ Ｓｑ ）の入力データに対し、データ
処理部を用いて（２／Ｑ）個×Ｐ段のバタフライ演算を
行い、その結果を局所メモリ上の同一アドレスに書き込
む。例えば、処理アルゴリズムとしてＩｎ−Ｐｌａｃｅ
型のＦＦＴアルゴリズムを用いる。但し。 （５）式から決定される回転因子を用いるものとする。 手順６： 手順５の結果、得られたＨ（ｒ、Ｓｑ）の演
算結果（Ｑ個）と正規化量（１個）を共有メモリ上に転
送する。演算結果はＨ（ｒ。 Ｓｑ）の入力データが格納されていた同一アドレスに、
正規化量は処理した小ＦＦＴの番号ｓｑに対応したアド
レスに格納される。 ここで９手順５においてＨ（ｒ、ｓｑ）の第１段のバタ
フライ演算の入力データを対象に正規化を行う場合、正
規化に必要な各入力データに対する乗算と手順４におけ
る定数Ｄｗの乗算を同時に行うことができる。 第５図の２５に条件分岐及び２６の処理は、２３及び２
４の処理をＱ回繰り返すためのものであって、制御部で
のハードウェア的あるいはソフトウェア的なカウンタに
より実現できる。また、Ｑ回繰り返される２３の処理の
うち、前記手順１゜手順２については最初の１回だけ実
行するだけでよい。 第５図の２７の条件分岐は、予め与えられているプロセ
ッサＵで処理すべきＱ個の小ＦＦＴの番号（”１９８２
９・・・、５Ｑ）１の添字ｉと、処理を終えた添字と比
較することにより実現する。 第４に、第４図の１０の処理を行う。これは。 最終段（第ｎ段）の８個の小ＦＦＴで異なった正規化が
行われ、演算結果の正規化量が小ＦＦＴ毎に異なるため
に行う６まず、８個の小ＦＦＴの正規化量の中から、最
小のものを導出する。これは。 あるプロセッサが全正規化量をサーチすることで可能で
ある。次に各車ＦＦＴの演算結果にある一定値を乗じる
。この一定値とは、求めた最小の正規化量を演算結果の
正規化量で除した数である。 これは、各プロセッサが互いに異なる小ＦＦＴの演算結
果に対し、上記一定値を乗じることで可能である。 以上のように、第７図に示す構成を用い、且つ必要な正
規化量が等しい小ＦＦＴの演算に用いるデータを、同一
のプロセッサに逐次転送して、当該小ＦＦＴの演算を行
うことにより、Ｎ点ＦＦＴを行う。すると、プロセッサ
が必要とする正規化量の数が減少する。よって、共有メ
モリ上の正規化量のアクセス頻度が減少でき、メモリや
データ転送回路の能力の制限からくるオーバヘッドの発
生を低減できる。すなわち、より高速なＦＦＴ演算装置
を実現できる。 以下本発明の第３の実施例について述べる。 第８図は、第３の実施例の構成図である。第８図におい
て、７０はデータ転送ユニット、７１〜７３はプロセッ
サである。データ転送ユニットは。 バス７４から構成される。プロセッサが必要とするデー
タは、複数のプロセッサからバスを介して転送する。 各プロセッサは９局所メモリ４７とデータ処理部４８．
アドレス発生部４９．制御部５０から構成される。そし
て、制御部からの指示により、アドレス発生部及びデー
タ処理部が有機的に働き。 局所メモリ上のデータに対する処理を行う。 本実施例では、各プロセッサの局所メモリ上に。 少なくともＦＦＴの原始データ、中間演算結果。 最終演算結果を格納する領域８１と、これらデータの正
規化量を格納する領域８２とを有し、これらのデータを
複数のプロセッサに分散して記憶する。 本実施例によるＮ点ＦＦＴの演算は、前記第２の実施例
の場合と同様の手順により実現できる。 但し本実施例では、各プロセッサが処理を行う上で必要
なデータの授受は、データ転送ユニットのバスを介して
、複数の局所メモリを直接アクセスすることにより行う
、すなわち、プロセッサにおける小ＦＦＴの演算は、以
下に示すような方法により行う。 方法１゜ 複数のプロセッサの局所“メモリ上にある。予め定５ｅ
れた正規化量を・当該ブト９″′局所８モリに転送した
後、複数のプロセッサの局所メモリ上にある。当該正規
化量を有する小ＦＦＴの入力データを、当該プロセッサ
に逐次転送し、前回に、当該プロセッサで行った小ＦＦ
Ｔの演算結果とその正規化量とが参照されたことを検出
した後に、当該小ＦＦＴの演算を行い、得られた演算結
果とその正規化量を、当該プロセッサの局所メモリに格
納することをにより行う。ここで各プロセッサは、入力
データとその正規化量の読み出しに対して主導権を有す
る。 方法２゜ 当該プロセッサの局所メモリに、予め定められた正規化
量と当該正規化量を有する小ＦＦＴの入力データとが格
納されたことを検出し、当該プロセッサがその局所メモ
リの正規化量と入力データを逐次読み出すことにより、
当該小ＦＦＴの演算を行い、得られた演算結果とその正
規化量を、当該演算結果を用いて演算を行うプロセッサ
の局所メモリに転送することにより行う。ここで各プロ
セッサは、演算結果をその正規化量の格納に対して主導
権を有する。 なお、処理開始時点において、ＦＦＴの原始データ（Ｎ
個）は、既に共有メモリ上に分散して格納されているも
のとする。また、前記第２の実施例の場合と同じように
、小ＦＦＴの演算に必要な正規化量は、必要な正規化量
が同じである複数の小ＦＦＴの演算当り、１回転送する
だけでよい。 本実施例では、少なくともＦＦＴの原始データ。 中間演算結果、最終演算結果を格納する領域と。 これらデータの正規化量を格納する領域とを、共に各プ
ロセッサの局所メモリ上に分散配置したが。 少なくともＦＦＴの原始データ、中間演算結果。 最終演算結果を格納する領域のみ、あるいは正規化量を
格納する領域のみを９分散配置することも可能である。 以上のように、第８図に示す構成を用い、且つ必要な正
規化量が等しい小ＦＦＴの演算に用いるデータを、同一
のプロセッサに逐次転送して、当該小ＦＦＴの演算を行
うことにより、Ｎ点ＦＦＴを行う。すると、１つの正規
化量は、ある１つのプロセッサしか必要としなくなるの
で、正規化量をプロセッサ間で転送する回数を低減でき
る。よって、メモリやデータ転送回路の能力の制限から
くるオーバヘッドの発生を低減でき、より高速なＦＦＴ
演算装置を実現できる。
した小ＦＦＴとの関係の概略を示したものである。ここ
で、１はＮ点ＦＦＴに必要な（Ｎ／２）個×Ｍ段のバタ
フライ演算を表す。但し。 Ｍ ＝ ｌｏｇ、 Ｎである。今、小ＦＦＴ２〜６の大
きさを（Ｑ／２）個×Ｐ段のバタフライ演算であるとす
る。但し、 ｐ＝ｌｏｇ、Ｑである。このときＮ点ＦＦ
Ｔは、Ｒ段×Ｓ個の小ＦＦＴに分割できる。ここで、Ｒ
＝Ｍ／Ｐ且つＳ＝Ｎ／Ｑである。なお。 第３図上で左上を原点とし、そこから右にｒ段。 下にＳ個の位置の小ＦＦＴを、第ｒ段第Ｓ番目の小ＦＦ
Ｔと呼び、Ｈ（ｒ、５）（ｒ＝１，２．−Ｒ；５＝＝１
．２．・・・、Ｓ）と表すことにする。 第４図は、第３図のＲ段×Ｓ個の小ＦＦＴをＵ個のプロ
セッサで処理するときの処理手順を示すものである。ま
ずＮ点ＦＦＴの原始データ（Ｎ個）をビットリバース順
に並び替える処理７を行う９次にＲ段×Ｓ個の小ＦＦＴ
の演算８，９を行う。 最後に全ての演算結果を対象にした桁合わせの処理１０
を行うことにより、Ｎ点ＦＦＴを終了する。 各車ＦＦＴの演算過程でそれぞれ独立した正規化を行う
とき、第２段目以降の小ＦＦＴの演算では９桁合わせの
処理が必要になる。そこで、この桁合わせの処理でのオ
ーバヘッドを減少させるために、Ｒ段×Ｓ個の小ＦＦＴ
の演算８，９のうち。 第１段（ｒ≧２）の小ＦＦＴの演算９を第５図に示す処
理手順により行う。 第５図は、Ｕ番目のプロセッサ（以下プロセッサＵと呼
ぶ：ｕ＝１．２．・・・、Ｕ）における第ｒ段（ｒ≧２
）の小ＦＦＴの処理手順を示すものである。まず、第ｒ
段小ＦＦＴのうち必要な正規化量が等しい小ＦＦＴの番
号（Ｈ（ｒ、ｓ）のＳ）の導出２１を行う。このような
第ｒ段小ＦＦＴはＱ個存在し、その番号を？ （Ｓｉｔ
８２．”’ｊ ５Ｑ）１（ｉ＝１．２．・・・、Ｓ／
Ｑ）と表すことにする。 ここで添字ｉは、このＱ個の第ｒ段小ＦＦＴに対応する
固有の値であり、各々の番号”１１８！Ｉ・・・ｆｉＱ
と１対１に対応する。よって添字ｉが異なると、その番
号＄１１８２１・・・、ｓｅは全て異なる。 次に、処理２１で導出された（Ｓ工、ｓ２．・・・、５
Ｑ）１の中のあるＳｑ （ｑ＝１，２．・・・、Ｑ）
番目の第ｒ段小ＦＦＴＨ（ｒ、Ｓ’ｔ ）の処理２２を
行う。 ２２の処理は、 Ｈ（ｒ、 ｓｑ ）の入力データの桁
合わせを行う処理２３と、（Ｑ／２）個×Ｐ段のバタフ
ライ演算の処理２４からなる。なお２４の処理では、演
算過程で正規化が行われる。この２２の処理は、２５の
条件分岐及び２６の処理する小ＦＦＴの番号の更新の処
理により、処理２１で導出したＱ個の番号の第ｒ段小Ｆ
ＦＴＨ（ｒ、ｓｌ） ｔ Ｈ（ｒｅ ８２） ｇ ・・
・ｇ Ｈ（ｒｅ ｓＱ ）の処理を全て終えるまで繰り
返される。 以上２１〜２６の処理の終了後、２７の条件分岐により
、必要な正規化量が等しいＱ個の第ｒ段小Ｆ ＦＴＨ（
ｒ、 ｓ、） 、 Ｈ（ｒ、 ｓ２） 、 −、Ｈ（ｒ
、ｓＱ）であって、まだ処理を終えておらず且つプロセ
ッサＵで処理すべきものが存在するか否かを判定する。 これは、予めプロセッサＵが処理すべきＱ個の小ＦＦＴ
の番号（ｓｌ、ｓ２．”’、ｓＱ）息の添字ｉを決めて
おき、処理済みの添字との比較から、あるいは、まだど
のプロセッサでも処理されていないＱ個の小ＦＦＴＨ（
ｒ、Ｓｌ）、Ｈ（ｒ ｓ ９ｚ） ＋ ”’＋ Ｈ（ｒ
ｇ ｓＱ）の存在の有無を調べることなどから可能で
ある。その結果、プロセッサＵで処理すべきものが存在
する場合には。 ２１〜２６の処理を再度繰り返す。このとき処理２１は
この新たな添字ｉを有するＱ個の第ｒ段小ＦＦＴの番号
（５１，８２，・・’、５Ｑ）ｔ を導出する。 次に、第５図での２１及び２２の処理について。 詳細に説明する。 ２１の処理で導出される。Ｑ個の第ｒ段小ＦＦＴの番号
Ｓｑ （ｑ＝１，２．・・・、Ｑ）は９次式より導出
する。 ５ｑ＝Ｑ”−”ｘｄｉｖ（（ｉ １）／Ｑ”−”）＋
ｍｏｄ（（ｉ −１）／ Ｑ””） ＋（（１−１）ＸＱ”−”＋１ （１）但しｅ
ｌ ”（Ｓ１ｔｓｌ＋”・ｔｓＱ）ｌ の添字ｅｘ＝Ｌ
２、・・・、（Ｓ／Ｑ）。 ｄｉｖ （ｕ／ｖ）： ｕ／ｖの商。 ｓｏｄ （ｕ／ｖ）： ｕ／ｖの余り。 第６図は、２２の処理すなわちＨ（ｒ、 Ｓｑ ）の処
理の内容をデータフロー図で示したものである。Ｈ（ｒ
、 ｓｑ ）の処理とは、 ｈ （０） 〜ｈ（Ｑ−１
）に対して９桁合わせの処理３１と（Ｑ／２）個ｘｐ段
のバタフライ演算３２を行うことである。それぞれ第５
図における２３の処理及び２４の処理に対応する６ Ｈ（ｒｅｓｑ）の入力データｈ （０） 〜ｈ （Ｑ−
１）とＮ点ＦＦＴの原始データｘ（０）〜ｘ（Ｎ−１）
との関係は、以下のようになる。但しＮ点ＦＦＴの原始
データは、既にビットリバース順に並び変えられている
ものとする。 ｈ （ｋ） ＝ ｘ （Ｑ’Ｘｄｉｖ（（ｓｑ −１）／ Ｑ”−１
））＋ｍｏｄ（（ｓ ｑ −１）／ Ｑ”−１））＋ｋ
ＸＱ”−”） （２）但し、 ｈ （ｋ
） ：小ＦＦＴＨ（ｒ、 ｓｑ ）のに個目の入力デー
タ。ｋ＝０゜ １、・・・ ｘ（ｎ）：Ｎ点ＦＦＴのｎ個目の原始データ。ｎ冨０，
１．・・・ ｄｉｖ （ｕ／ｖ）： ｕ／ｖの商。 ｌ１ｏｄ （ｕ／ｖ） ： ｕ／ｖの余り。 ３１の桁合わせの処理は、Ｈ（ｒ、ｓｑ）の入力データ
ｈ （ｋ）に、それぞれの正規化量に従って、定数Ｄｗ
（Ｗ ＝１ ｅ ２ ｔ −＋ Ｑ）を乗じること
により行われる。（１）式で導出したＱ個の第ｒ段小Ｆ
ＦＴにおけるＤｌは、 Ｈ（ｒ、 Ｓｑ ）での正規化
量をＥ （ｒ、 ｓｑ ）とすると９次式から求められ
る。 Ｄｗ”：５ｉｎ（Ｅ （ｒ−１，ｓ ｚＬ Ｅ （ｒ−
１，Ｓ ｚＬ−・・Ｅ （ｒ−１，ｓ ｅ））／ Ｅ
（ｒ−１，ｓ−） （３）但しｇ Ｉ＠Ｉｎ （ｕ
ｌＩｕｚｇ”’ｇ ｕｖ） ： ｕＬＨＬ１２ｇ°°
。 ｕｖの最小値。 すなわち、Ｑ個の小ＦＦＴの演算に必要な正規化量は、
いずれもＥ（ｒ−１＊ ５１）Ｉ Ｅ （ｒ−１ｓ
ｓｚ） ｅ −Ｅ （ｒ−１） ＳＱ） と等しく
なる。 ３２の（２／Ｑ） 個ｘｐ段のバタフライ演算の処理は
、Ｑ点ＦＦＴの演算とアルゴリズム的に全く同一である
ことから、一般に用いられているＦＦＴの処理アルゴリ
ズムにより実現できる。但し。 各バタフライ演算で乗じる回転因子の値は、Ｑ点ＦＦＴ
の場合と異なる。 今、第６図上で第０段（ｕ ＝ １ 、２ 、− Ｐ
）の（Ｑ／２）個のバタフライ演算の中で、上からＶｆ
ｈＩｌｌｌ（ｖ＝１．２．・・・Ｑ）のバタフライ演算
で用いる回転因子を＠Ｗｕｖと表す。このＷ ｕ ｖは
９次式より導出される。 Ｗｕｖ ＝ｅｘｐ（−ｊ（２π／ Ｎ） Ｘ ｃ ）ｃ
−＝Ｉｌｏｄ（（ｖ −１）／ ２ （ｕ”）） Ｘ
Ｑｃｒ−ｘ＞＋ｍｏｄ（（ｓｑ １）／Ｑ”−”）
（４）すなわち３２の処理は、処理アルゴリズムと
してＦＦＴアルゴリズムを用い２乗じる回転因子は（５
）式より導出することから実現できる。 以上のように、第ｒ段（ｒ≧２）の小ＦＦＴのうち、必
要な正規化量が等しいＱ個の小ＦＦＴの番号ＳＭ （
ｑ ＝ １ ｔ ２１ ・・・＊ Ｑ）を（１）式より
導出し、これらの番号の小ＦＦＴＨ（ｒ、ｓ工）。 Ｈ（ｒ＋ ｓｚ） ｅ ・・・＊ Ｈ（ｒ、 ｓＱ
） を同一プロセッサで処理する。すると、同一プロ
セッサで処理するこれら小ＦＦＴの演算に必要な正規化
量が等しくなるので、プロセッサに転送する正規化量の
数を削減できる。あるいはこれらの正規化量は。 同一プロセッサで処理する小ＦＦＴと１対１に対応する
ことから、１つの正規化量は、ある１つのプロセッサし
か必要としなくなり、正規化量をプロセッサ間で転送す
る回数を低減できる。よって。 高速なメモリやデータ転送回路が不要になる。あるいは
メモリやデータ転送回路の能力の制限からくるオーバヘ
ッド発生の問題を低減できることから、より高速なＦＦ
Ｔの演算が可能になる。 以下本発明の第２の実施例について述べる。 第７図は、第２の実施例の構成図である。第７図におい
て、６０はデータ転送ユニット、４１〜４３はプロセッ
サである。データ転送ユニットは。 共有メモリ４０とバス４４から構成される。共有メモリ
上には、少なくともＦＦＴの原始データ。 中間演算結果、最終演算結果を格納する領域４５と、こ
れらデータの正規化量を格納する領域４６とを有する。 そしてプロセッサが必要とするデータを、共有メモリか
らバスを介して転送する。 各プロセッサは９局所メモリ４７とデータ処理部４８．
アドレス発生部４９．制御部５０から構成される。そし
て、制御部からの指示により、アドレス発生部及びデー
タ処理部が有機的に働き。 共有メモリ上あるいは局所メモリ上のデータに対する処
理を行う。 ところで、共有メモリと各プロセッサ間のデータ転送は
単一のバスにより行うため、複数のプロセッサが同時に
共有メモリをアクセスすると、バス上でデータの衝突が
生じる。この問題は、各プロセッサの制御部により各々
のプロセッサが共有メモリをアクセスするタイミングを
互いに少しずつずらす、あるいはバスアービタを用いる
などの工夫により解決しているものとする。このような
ＦＦＴ演算装置は２例えば市販されている乗算器やメモ
リなどを組み合わせて、あるいはＤＳＰ（ディジタル
シグナル プロセッサ： ｐｉｇｉｔａｌＳｉｇｎａｌ
Ｐｒｏｃｅｓｓｏｒ）を用いることなどにより実現で
きる。 本実施例によるＮ点ＦＦＴの演算は、先の第１の実施例
で述べたＦＦＴ演算方法に基づいて行う。 以下２本実施例によりＮ点ＦＦＴを処理するときのデー
タの流れ及び各部の動作について、第４図及び第５図に
従って述べる。なお、処理開始時点において、ＦＦＴの
原始データ（Ｎ個）は、既に共有メモリ上に格納されて
いるものとする。 まず、第４図の７の処理を行う。これは２例えば各プロ
セッサが共有メモリ上のＮ個のＦＦＴ原Ａとそのビット
リバース位置である範囲Ｂの原始データをそれぞれ局所
メモリ上に転送する。そして、帰所メモリ上の範囲Ａの
データをそのビットリバース位置である共有メモリ上の
範囲Ｂに９局所メモリ上の範囲Ｂのデータをそのビット
リバース位置である共有メモリ上の範ＭＡにそれぞれ転
送することにより実現する。 第２に、第４図の８の処理を行う。これは、各プロセッ
サが共有メモリ上のＮ個のＦＦＴ原始データのうち、プ
ロセッサ毎に異なる小ＦＦＴの入力データ（Ｑ個）を局
所メモリ上に転送した後。 データ処理部でこの局所メモリ上の入力データに対して
、演算過程で正規化を１回以上行う小ＦＦＴの演算を行
い、その結果得られた演算結果（Ｑ個）と正規化量（１
個）を、アドレス発生部を用いて再び共有メモリ上に転
送することにより実現する。演算結果は小ＦＦＴの入力
データが格納されていた同一アドレスに、正規化量は処
理した小ＦＦＴの番号に対応したアドレスに格゛納され
る。 第３に、第４図の９の処理、すなわち第５図の処理を行
う。なお、第２段以降の小ＦＦＴの処理において、各プ
ロセッサで処理すべきＱ個の小ＦＦＴの番号（ｓｘｅ
ｓｚ＋”’ｔ １ｉＱ）１の添字ｉは、予め次のように
決定しておくものとする。すなわち。 プロセッサＵで処理すべきＱ個の小ＦＦＴの番号（５１
１５２１”’ｐｓＱ）、の添字ｉは。 ｕ、ｕ＋Ｕ、ｕ＋２Ｕ、−、ｕ＋ｚＵ 但し、ｚ：＝ｄｉｖ（Ｓ／ （ＱＸＵ））＋ｄｉｖ（ｍ
ａｄ（Ｓ ／ （Ｑ Ｘ Ｕ） ）／ ｕ ）−１とす
る。そしてこれらの値は、プロセッサＵに格納しておく
ものとする。 第５図の２１の処理は、データ処理部において。 予め与えられているプロセッサＵで処理すべきＱ個の小
ＦＦＴの番号（Ｓａｔｓ２＊”’＋ＳＱ）＋の添字ｉよ
り、この（Ｓｚｓ Ｓａｔ”’ｔ ＳＱＩ を（１）式
を用いて導出することにより実現できる。 第５図の２３の処理は、以下の手順で行うことができる
。 手順１： ２１の処理で得られた小ＦＦＴの番号（Ｓ□
、ｓ２．・・・、ｌ！Ｑ）ｌから２桁合わせ、すなわち
（３）式を計算するのに必要なＱ個の正規化量（Ｅ （
ｒ−１，ｓｚ ） ｓ Ｅ （ｒ−１゜ｓｔ） ｌ ・
Ｅ （ｒ−１，ｓＱ） ）を、共有メモリ上から局所メ
モリ上に転送する。 手順２： （３）式より２桁合わせに必要な定数り
、（ｗ＝１．２．−、Ｑ）をデータ処理部で求め、その
結果を局所メモリ上のＥ（ｒ−１，ｓ、） の格納位
置に書き込む。 手順３ ： Ｈ（ｒｅ ｓｑ ）のＱ個の入力データ
を、共有メモリ上から局所メモリ上に転送する。このと
き共有メモリ上の入力データのアドレスは、（２）式を
用いて導出する。 手順４： 局所メモリ上のＨ（ｒ、 Ｓｑ ）の入力デ
ータに、データ処理部を用いて手順２で求めた定数り、
を乗じ、その結果を局所メモリ上の同一アドレスに書き
込む。 また第５図の２４の処理は、引き続き以下の手順により
行う。 手順５： 手順４で求めた局所メモリ上の桁合わせを終
えたＨ （ｒｅ Ｓｑ ）の入力データに対し、データ
処理部を用いて（２／Ｑ）個×Ｐ段のバタフライ演算を
行い、その結果を局所メモリ上の同一アドレスに書き込
む。例えば、処理アルゴリズムとしてＩｎ−Ｐｌａｃｅ
型のＦＦＴアルゴリズムを用いる。但し。 （５）式から決定される回転因子を用いるものとする。 手順６： 手順５の結果、得られたＨ（ｒ、Ｓｑ）の演
算結果（Ｑ個）と正規化量（１個）を共有メモリ上に転
送する。演算結果はＨ（ｒ。 Ｓｑ）の入力データが格納されていた同一アドレスに、
正規化量は処理した小ＦＦＴの番号ｓｑに対応したアド
レスに格納される。 ここで９手順５においてＨ（ｒ、ｓｑ）の第１段のバタ
フライ演算の入力データを対象に正規化を行う場合、正
規化に必要な各入力データに対する乗算と手順４におけ
る定数Ｄｗの乗算を同時に行うことができる。 第５図の２５に条件分岐及び２６の処理は、２３及び２
４の処理をＱ回繰り返すためのものであって、制御部で
のハードウェア的あるいはソフトウェア的なカウンタに
より実現できる。また、Ｑ回繰り返される２３の処理の
うち、前記手順１゜手順２については最初の１回だけ実
行するだけでよい。 第５図の２７の条件分岐は、予め与えられているプロセ
ッサＵで処理すべきＱ個の小ＦＦＴの番号（”１９８２
９・・・、５Ｑ）１の添字ｉと、処理を終えた添字と比
較することにより実現する。 第４に、第４図の１０の処理を行う。これは。 最終段（第ｎ段）の８個の小ＦＦＴで異なった正規化が
行われ、演算結果の正規化量が小ＦＦＴ毎に異なるため
に行う６まず、８個の小ＦＦＴの正規化量の中から、最
小のものを導出する。これは。 あるプロセッサが全正規化量をサーチすることで可能で
ある。次に各車ＦＦＴの演算結果にある一定値を乗じる
。この一定値とは、求めた最小の正規化量を演算結果の
正規化量で除した数である。 これは、各プロセッサが互いに異なる小ＦＦＴの演算結
果に対し、上記一定値を乗じることで可能である。 以上のように、第７図に示す構成を用い、且つ必要な正
規化量が等しい小ＦＦＴの演算に用いるデータを、同一
のプロセッサに逐次転送して、当該小ＦＦＴの演算を行
うことにより、Ｎ点ＦＦＴを行う。すると、プロセッサ
が必要とする正規化量の数が減少する。よって、共有メ
モリ上の正規化量のアクセス頻度が減少でき、メモリや
データ転送回路の能力の制限からくるオーバヘッドの発
生を低減できる。すなわち、より高速なＦＦＴ演算装置
を実現できる。 以下本発明の第３の実施例について述べる。 第８図は、第３の実施例の構成図である。第８図におい
て、７０はデータ転送ユニット、７１〜７３はプロセッ
サである。データ転送ユニットは。 バス７４から構成される。プロセッサが必要とするデー
タは、複数のプロセッサからバスを介して転送する。 各プロセッサは９局所メモリ４７とデータ処理部４８．
アドレス発生部４９．制御部５０から構成される。そし
て、制御部からの指示により、アドレス発生部及びデー
タ処理部が有機的に働き。 局所メモリ上のデータに対する処理を行う。 本実施例では、各プロセッサの局所メモリ上に。 少なくともＦＦＴの原始データ、中間演算結果。 最終演算結果を格納する領域８１と、これらデータの正
規化量を格納する領域８２とを有し、これらのデータを
複数のプロセッサに分散して記憶する。 本実施例によるＮ点ＦＦＴの演算は、前記第２の実施例
の場合と同様の手順により実現できる。 但し本実施例では、各プロセッサが処理を行う上で必要
なデータの授受は、データ転送ユニットのバスを介して
、複数の局所メモリを直接アクセスすることにより行う
、すなわち、プロセッサにおける小ＦＦＴの演算は、以
下に示すような方法により行う。 方法１゜ 複数のプロセッサの局所“メモリ上にある。予め定５ｅ
れた正規化量を・当該ブト９″′局所８モリに転送した
後、複数のプロセッサの局所メモリ上にある。当該正規
化量を有する小ＦＦＴの入力データを、当該プロセッサ
に逐次転送し、前回に、当該プロセッサで行った小ＦＦ
Ｔの演算結果とその正規化量とが参照されたことを検出
した後に、当該小ＦＦＴの演算を行い、得られた演算結
果とその正規化量を、当該プロセッサの局所メモリに格
納することをにより行う。ここで各プロセッサは、入力
データとその正規化量の読み出しに対して主導権を有す
る。 方法２゜ 当該プロセッサの局所メモリに、予め定められた正規化
量と当該正規化量を有する小ＦＦＴの入力データとが格
納されたことを検出し、当該プロセッサがその局所メモ
リの正規化量と入力データを逐次読み出すことにより、
当該小ＦＦＴの演算を行い、得られた演算結果とその正
規化量を、当該演算結果を用いて演算を行うプロセッサ
の局所メモリに転送することにより行う。ここで各プロ
セッサは、演算結果をその正規化量の格納に対して主導
権を有する。 なお、処理開始時点において、ＦＦＴの原始データ（Ｎ
個）は、既に共有メモリ上に分散して格納されているも
のとする。また、前記第２の実施例の場合と同じように
、小ＦＦＴの演算に必要な正規化量は、必要な正規化量
が同じである複数の小ＦＦＴの演算当り、１回転送する
だけでよい。 本実施例では、少なくともＦＦＴの原始データ。 中間演算結果、最終演算結果を格納する領域と。 これらデータの正規化量を格納する領域とを、共に各プ
ロセッサの局所メモリ上に分散配置したが。 少なくともＦＦＴの原始データ、中間演算結果。 最終演算結果を格納する領域のみ、あるいは正規化量を
格納する領域のみを９分散配置することも可能である。 以上のように、第８図に示す構成を用い、且つ必要な正
規化量が等しい小ＦＦＴの演算に用いるデータを、同一
のプロセッサに逐次転送して、当該小ＦＦＴの演算を行
うことにより、Ｎ点ＦＦＴを行う。すると、１つの正規
化量は、ある１つのプロセッサしか必要としなくなるの
で、正規化量をプロセッサ間で転送する回数を低減でき
る。よって、メモリやデータ転送回路の能力の制限から
くるオーバヘッドの発生を低減でき、より高速なＦＦＴ
演算装置を実現できる。
本発明によれば、小ＦＦＴの入力データの数をＱ個とす
ると、プロセッサは、各段階で同一の正規化量を用いて
Ｑ個の小ＦＦＴの演算を行うことができるので、プロセ
ッサが必要とする正規化量の数を１／Ｑに削減できる。 あるいは、１つの正規化量は、ある１つのプロセッサし
か必要としなくなるので、正規化量をプロセッサ間で転
送する回数を１／Ｑに低減できる。よって、高速なメモ
リやデータ転送回路が不要になる。あるいはメモリやデ
ータ転送回路の能力の制限からくるオーバヘッド発生の
問題を低減できる。すなわち、より高速なＦＦＴの演算
が可能になる。
ると、プロセッサは、各段階で同一の正規化量を用いて
Ｑ個の小ＦＦＴの演算を行うことができるので、プロセ
ッサが必要とする正規化量の数を１／Ｑに削減できる。 あるいは、１つの正規化量は、ある１つのプロセッサし
か必要としなくなるので、正規化量をプロセッサ間で転
送する回数を１／Ｑに低減できる。よって、高速なメモ
リやデータ転送回路が不要になる。あるいはメモリやデ
ータ転送回路の能力の制限からくるオーバヘッド発生の
問題を低減できる。すなわち、より高速なＦＦＴの演算
が可能になる。
第１図は６４点ＦＦＴを小ＦＦＴに分割して処理すると
きのデータフロー図、第２図は小ＦＦＴのデータフロー
図、第３図はＮ点ＦＦＴと分割した小ＦＦＴの関係の概
略を示す図、第４図は本′発明の一実施例であるＮ点Ｆ
ＦＴの処理手順を示すフローチャート、第５図は本発明
の一実施例であるＵ番目のプロセッサによる第ｒ段小Ｆ
ＦＴの処理手順を示すフローチャート、第６図は小ＦＦ
Ｔのデータフロー図、第７図は本発明の一実施例を示す
構成図、第８図は本発明の一実施例を示す構成図である
。 符号の説明 １０１〜１３６・・・小ＦＦＴ、８・・・第１段小ＦＦ
Ｔの演算、９・・・第ｒ段小ＦＦＴの演算、２１・・・
必要な正規化量が等しい第ｒ段小ＦＦＴの番号（Ｓｌ。 ｓ２．、”’ ５Ｑ）ｔの導出、２２＝−Ｈ（ｒ、Ｓ
ｑ ）の処理、２３・・・Ｈ（ｒ、ｓｑ）の入力データ
の桁合わせ、２４・・・Ｈ（ｒ、ｓ噌）を構成するＱ／
２個×Ｐ段のバタフライ演算の処理、６０．７０・・・
データ転送ユニット、４１，４２，４３．７１，７゛２
，７３・・・プロセッサ、４０・・・共有メモリ、４４
゜７４・・・バス、４７・・・局所メモリ４図 晃２図 ）のイＰ！−嘘バタ２〉イ渭１邊［艮し４■ＶＣ功遍。 第Ｓ図
きのデータフロー図、第２図は小ＦＦＴのデータフロー
図、第３図はＮ点ＦＦＴと分割した小ＦＦＴの関係の概
略を示す図、第４図は本′発明の一実施例であるＮ点Ｆ
ＦＴの処理手順を示すフローチャート、第５図は本発明
の一実施例であるＵ番目のプロセッサによる第ｒ段小Ｆ
ＦＴの処理手順を示すフローチャート、第６図は小ＦＦ
Ｔのデータフロー図、第７図は本発明の一実施例を示す
構成図、第８図は本発明の一実施例を示す構成図である
。 符号の説明 １０１〜１３６・・・小ＦＦＴ、８・・・第１段小ＦＦ
Ｔの演算、９・・・第ｒ段小ＦＦＴの演算、２１・・・
必要な正規化量が等しい第ｒ段小ＦＦＴの番号（Ｓｌ。 ｓ２．、”’ ５Ｑ）ｔの導出、２２＝−Ｈ（ｒ、Ｓ
ｑ ）の処理、２３・・・Ｈ（ｒ、ｓｑ）の入力データ
の桁合わせ、２４・・・Ｈ（ｒ、ｓ噌）を構成するＱ／
２個×Ｐ段のバタフライ演算の処理、６０．７０・・・
データ転送ユニット、４１，４２，４３．７１，７゛２
，７３・・・プロセッサ、４０・・・共有メモリ、４４
゜７４・・・バス、４７・・・局所メモリ４図 晃２図 ）のイＰ！−嘘バタ２〉イ渭１邊［艮し４■ＶＣ功遍。 第Ｓ図
Claims (1)
- 【特許請求の範囲】 １、ＦＦＴの演算を複数の小ＦＦＴに分割して段階的に
求め、各段階での小ＦＦＴの演算過程で演算精度を維持
するための正規化を１回以上行う演算方式において、入
力データの正規化量が等しい小ＦＦＴの演算を、同一プ
ロセッサで行うことを特徴とするＦＦＴ演算方式。 ２、ＦＦＴの一部分である小ＦＦＴの演算が可能で、且
つ演算過程で演算精度を維持するための正規化を１回以
上行うことが可能な複数のプロセッサと、当該各プロセ
ッサと接続され、演算に必要なデータの授受が可能なデ
ータ転送手段とを有することを特徴とするＦＦＴ演算装
置。 ３、各プロセッサは、必要な正規化量が等しい小ＦＦＴ
の入力データとその正規化量を、データ転送手段を介し
て獲得した後、当該小ＦＦＴの演算を逐次行い、得られ
た演算結果とその正規化量を、データ転送手段を介して
転送することを特徴とする請求項２記載のＦＦＴ演算装
置。 ４、プロセッサは、少なくともデータ転送手段とデータ
の授受が可能な局所メモリと、当該局所メモリのデータ
に対して、演算過程で正規化を１回以上行う小ＦＦＴの
演算が可能なデータ処理手段とを有することを特徴とす
る上記第３項記載のＦＦＴ演算装置。 ５、データ転送手段は、少なくともＦＦＴの原始データ
、中間演算結果、最終演算結果と正規化量とを格納可能
な共有メモリと、当該共有メモリと各プロセッサとの間
でデータの授受が可能な手段とを有することを特徴とす
る上記第４項記載のＦＦＴ演算装置。 ６、予め定められた正規化量を、共有メモリから適当な
プロセッサの局所メモリに転送した後、当該正規化量を
有する小ＦＦＴの入力データを、共有メモリから当該プ
ロセッサに逐次転送することにより、当該小ＦＦＴの演
算を行い、得られた演算結果とその正規化量を、当該プ
ロセッサから共有メモリに転送することを特徴とする上
記第５項記載のＦＦＴ演算装置。 ７、データ転送手段は、少なくともプロセッサ相互間で
データの授受が可能な手段を有することを特徴とする請
求項４記載のＦＦＴ演算装置。 ８、各プロセッサの局所メモリ上には、少なくともＦＦ
Ｔの原始データ、中間演算結果、最終演算結果と正規化
量とを分散して格納し、他のプロセッサ上のデータのア
クセスは、データ転送手段を介して行うことを特徴とす
る上記第７項記載のＦＦＴ装置。 ９、複数のプロセッサの局所メモリ上にある、予め定め
られた正規化量を、適当なプロセッサの局所メモリに転
送した後、複数のプロセッサの局所メモリ上にある、当
該正規化量を有する小ＦＦＴの入力データを、当該プロ
セッサに逐次転送し、前回に、当該プロセッサで行った
小ＦＦＴの演算結果とその正規化量とが参照されたこと
を検出した後に、当該小ＦＦＴの演算を行い、得られた
演算結果とその正規化量を、当該プロセッサの局所メモ
リに格納することを特徴とする上記第８項記載のＦＦＴ
演算装置。 １０、個々のプロセッサの局所メモリに、予め定められ
た正規化量と当該正規化量を有する小ＦＦＴの入力デー
タとが格納されたことを検出し、各プロセッサがその局
所メモリの正規化量と入力データを逐次読み出すことに
より、当該小ＦＦＴの演算を行い、得られた演算結果と
その正規化量を、当該演算結果を用いて演算を行うプロ
セッサの局所メモリに転送することを特徴とする上記第
８項記載のＦＦＴ演算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1237029A JPH03100863A (ja) | 1989-09-14 | 1989-09-14 | Ｆｆｔ演算方式及び装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1237029A JPH03100863A (ja) | 1989-09-14 | 1989-09-14 | Ｆｆｔ演算方式及び装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03100863A true JPH03100863A (ja) | 1991-04-25 |
Family
ID=17009339
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1237029A Pending JPH03100863A (ja) | 1989-09-14 | 1989-09-14 | Ｆｆｔ演算方式及び装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH03100863A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008533873A (ja) * | 2005-03-11 | 2008-08-21 | クゥアルコム・インコーポレイテッド | 高速フーリエ変換トゥイドル乗算 |
| US8229014B2 (en) | 2005-03-11 | 2012-07-24 | Qualcomm Incorporated | Fast fourier transform processing in an OFDM system |
-
1989
- 1989-09-14 JP JP1237029A patent/JPH03100863A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008533873A (ja) * | 2005-03-11 | 2008-08-21 | クゥアルコム・インコーポレイテッド | 高速フーリエ変換トゥイドル乗算 |
| US8229014B2 (en) | 2005-03-11 | 2012-07-24 | Qualcomm Incorporated | Fast fourier transform processing in an OFDM system |
| US8266196B2 (en) | 2005-03-11 | 2012-09-11 | Qualcomm Incorporated | Fast Fourier transform twiddle multiplication |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Burrus et al. | An in-place, in-order prime factor FFT algorithm | |
| US5226171A (en) | Parallel vector processing system for individual and broadcast distribution of operands and control information | |
| Silverman | An introduction to programming the Winograd Fourier transform algorithm (WFTA) | |
| EP0240032B1 (en) | Vector processor with vector data compression/expansion capability | |
| US4150434A (en) | Matrix arithmetic apparatus | |
| CN117633418A (zh) | 基于矩阵运算的多维快速傅立叶变换加速方法 | |
| CN108897716A (zh) | 通过存储器读写操作来缩减计算量的数据处理装置及方法 | |
| CN103034621B (zh) | 基2×k并行fft架构的地址映射方法及系统 | |
| US3584781A (en) | Fft method and apparatus for real valued inputs | |
| JPH036546B2 (ja) | ||
| US6704834B1 (en) | Memory with vectorial access | |
| US7870177B2 (en) | Method and system for multi-processor FFT/IFFT with minimum inter-processor data communication | |
| US6728742B1 (en) | Data storage patterns for fast fourier transforms | |
| JPH03100863A (ja) | Ｆｆｔ演算方式及び装置 | |
| US7847349B2 (en) | Single-cycle FFT butterfly calculator | |
| CN119356733B (zh) | 执行fft的方法、处理器和计算设备 | |
| US6023719A (en) | Signal processor and method for fast Fourier transformation | |
| JP3709291B2 (ja) | 高速複素フーリエ変換方法及び装置 | |
| CN114510217A (zh) | 处理数据的方法、装置和设备 | |
| US6438568B1 (en) | Method and apparatus for optimizing conversion of input data to output data | |
| US6772183B1 (en) | Device for converting input data to output data using plural converters | |
| CN118796132B (zh) | 一种数论变换加速方法、装置、介质及芯片 | |
| JP3278441B2 (ja) | ベクトル処理装置 | |
| JP3872724B2 (ja) | 高速フーリエ変換のための回転因子表およびそれを用いた高速フーリエ変換装置 | |
| JP2605792B2 (ja) | 演算処理装置 |