JPH0248941B2 - Tajigenrisangatafuuriehenkankeisanhoshiki - Google Patents
TajigenrisangatafuuriehenkankeisanhoshikiInfo
- Publication number
- JPH0248941B2 JPH0248941B2 JP57031328A JP3132882A JPH0248941B2 JP H0248941 B2 JPH0248941 B2 JP H0248941B2 JP 57031328 A JP57031328 A JP 57031328A JP 3132882 A JP3132882 A JP 3132882A JP H0248941 B2 JPH0248941 B2 JP H0248941B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- vector
- twiddle factor
- processing
- factor table
- 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
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Theoretical Computer Science (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
【発明の詳細な説明】
(1) 発明の技術分野
本発明は、スペクトル解析や数値解法の有効な
手段である多数元離散型フーリエ変換（以下、
MDFTと表記する）を並列処理計算機上で効率
よく処理する多次元離散型フーリエ変換計算方式
に関するものである。
手段である多数元離散型フーリエ変換（以下、
MDFTと表記する）を並列処理計算機上で効率
よく処理する多次元離散型フーリエ変換計算方式
に関するものである。
(2) 従来技術と問題点
第１図は並列処理計算機の概要を示すものであ
つて、１はパイプライン方式の並列処理計算機、
２は一元化メモリ、３は制御部、４は並列処理装
置、５は加算パイプライン、６は乗算パイプライ
ンをそれぞれ示している。一元化メモリ２の中に
はベクトル・データが格納されている。制御部は
ベクトル命令をデコードして加算パイプライン５
や乗算パイプライン６などの各種の演算パイプラ
インを制御するものである。加算パイプライン５
は２個のベクトル・データをパイプライン的に加
算処理し、乗算パイプライン６は２個のベクト
ル・データをパイプライン的に乗算処理する。第
２図はパラレル方式の並列処理計算機の概要を示
すものであつて、１′はパラレル方式の並列処理
計算機、２′は一元化メモリ、３′は制御部、４′
は並列処理装置、５′−０ないし５′−ｎは同種の
演算器である。第２図の並列処理計算機において
は、一次元メモリ２′から読出された被演算ベク
トルの要素aiと演算ベクトルの要素biが演算部
５′−ｊに入力され、次の要素ai+1およびbi+1が演
算部５′−＋１に入力される。
つて、１はパイプライン方式の並列処理計算機、
２は一元化メモリ、３は制御部、４は並列処理装
置、５は加算パイプライン、６は乗算パイプライ
ンをそれぞれ示している。一元化メモリ２の中に
はベクトル・データが格納されている。制御部は
ベクトル命令をデコードして加算パイプライン５
や乗算パイプライン６などの各種の演算パイプラ
インを制御するものである。加算パイプライン５
は２個のベクトル・データをパイプライン的に加
算処理し、乗算パイプライン６は２個のベクト
ル・データをパイプライン的に乗算処理する。第
２図はパラレル方式の並列処理計算機の概要を示
すものであつて、１′はパラレル方式の並列処理
計算機、２′は一元化メモリ、３′は制御部、４′
は並列処理装置、５′−０ないし５′−ｎは同種の
演算器である。第２図の並列処理計算機において
は、一次元メモリ２′から読出された被演算ベク
トルの要素aiと演算ベクトルの要素biが演算部
５′−ｊに入力され、次の要素ai+1およびbi+1が演
算部５′−＋１に入力される。
第１図および第２図に示した並列処理計算機
は、メモリ上に規則的に並んだデータを並列処理
装置を用いて規則的に並列処理することにより計
算効率の向上をねらつたものであり、具体的に
は、例えば二個のベクトルａ→，ｂ→の加算 ci＝ai＋bi（ｉ＝１，２，………ｎ） ここで、ａ→＝（a1，a2，………ao） ｂ→＝（b1，b2，………bo） ｃ→＝（c1，c2，………co） ｎはベクトル長 を行う場合、並列処理機能をもたない計算機にお
いてはｎ個の加算命令により実行するに対して、
並列処理計算機においては一個又はｎ個より少な
い個数のベクトル加算命令により実行される。
は、メモリ上に規則的に並んだデータを並列処理
装置を用いて規則的に並列処理することにより計
算効率の向上をねらつたものであり、具体的に
は、例えば二個のベクトルａ→，ｂ→の加算 ci＝ai＋bi（ｉ＝１，２，………ｎ） ここで、ａ→＝（a1，a2，………ao） ｂ→＝（b1，b2，………bo） ｃ→＝（c1，c2，………co） ｎはベクトル長 を行う場合、並列処理機能をもたない計算機にお
いてはｎ個の加算命令により実行するに対して、
並列処理計算機においては一個又はｎ個より少な
い個数のベクトル加算命令により実行される。
さて、これら方式の計算機における処理効率
（一定時間内での命令件数又は処理データ件数）
は、計算機のもつハードウエア特性に依存する
が、更にはその計算機の具体的なアーキテクチヤ
ーおよびデータの処理内容と手順を示すソフトウ
エアに大きく依存する。しかしながら ○イ 並列処理するデータの長さ（ベクトル長）を
可能な限り長くとる。
（一定時間内での命令件数又は処理データ件数）
は、計算機のもつハードウエア特性に依存する
が、更にはその計算機の具体的なアーキテクチヤ
ーおよびデータの処理内容と手順を示すソフトウ
エアに大きく依存する。しかしながら ○イ 並列処理するデータの長さ（ベクトル長）を
可能な限り長くとる。
○ロ 並列処理するデータのメモリ上での間隔は可
能な限り短かくする。即ち、データをメモリ上
で連続的に配置する。
能な限り短かくする。即ち、データをメモリ上
で連続的に配置する。
ことが、最大効率をひき出すための基本的な要件
である。これを並列処理要件という。本発明は、
第１図や第２図に示されるような並列処理計算機
において、MDFTを上記○イ，○ロの要件を満すべ
く処理するものである。
である。これを並列処理要件という。本発明は、
第１図や第２図に示されるような並列処理計算機
において、MDFTを上記○イ，○ロの要件を満すべ
く処理するものである。
本発明を説明する前にMDFTを計算する場合
の基本となる一次元の離散型フーリエ変換（以
下、DFTという）について述べる。第３図イは
DFTを計算するための手順とデータの流れを示
すものであり、第３図ロは第３図イの表記法を説
明するものである。図にそつて説明すると、各ス
テージの両端の〇印はメモリ上のデータとその順
位（並び順位）を示し、各ステージの左端の〇印
は入力データ、右端の〇印は出力データを示して
いる。最初のステージ（Stage）の処理では位置
１ないし４のデータで構成されるベクトルV1と、
位置５ないし８までのデータで構成されるベクト
ルV2に対して、ベクトル加算V1＋V2を計算し、
その結果を位置１から一つおきに位置７までに格
納する（図の実線部分）。また、ベクトル減算V1
−V2を計算し、その結果の各要素に対して回転
因子を乗じその結果を位置２から一つおきに位置
８までに格納する。ステージ２およびステージ３
においても、同様にベクトルV1とV2に基づいて
処理を行うが、ステージが進むごとに回転因子を
更新する。
の基本となる一次元の離散型フーリエ変換（以
下、DFTという）について述べる。第３図イは
DFTを計算するための手順とデータの流れを示
すものであり、第３図ロは第３図イの表記法を説
明するものである。図にそつて説明すると、各ス
テージの両端の〇印はメモリ上のデータとその順
位（並び順位）を示し、各ステージの左端の〇印
は入力データ、右端の〇印は出力データを示して
いる。最初のステージ（Stage）の処理では位置
１ないし４のデータで構成されるベクトルV1と、
位置５ないし８までのデータで構成されるベクト
ルV2に対して、ベクトル加算V1＋V2を計算し、
その結果を位置１から一つおきに位置７までに格
納する（図の実線部分）。また、ベクトル減算V1
−V2を計算し、その結果の各要素に対して回転
因子を乗じその結果を位置２から一つおきに位置
８までに格納する。ステージ２およびステージ３
においても、同様にベクトルV1とV2に基づいて
処理を行うが、ステージが進むごとに回転因子を
更新する。
データの個数を一般化しｎとした場合の処理手
順は第４図に示される。こゝでは、ｎは簡単のた
めに２の巾乗（ｎ＝2l，ｌは正の整数）で表現で
きるものとし、また、データは｛ai｝と表わして
いる。回転因子テーブルの内容は、 ω＝exp（−2πi／ｎ） として、 である。この一般化した手順は、ｎが２の巾乗で
表現できない場合にも容易に拡張できる。
順は第４図に示される。こゝでは、ｎは簡単のた
めに２の巾乗（ｎ＝2l，ｌは正の整数）で表現で
きるものとし、また、データは｛ai｝と表わして
いる。回転因子テーブルの内容は、 ω＝exp（−2πi／ｎ） として、 である。この一般化した手順は、ｎが２の巾乗で
表現できない場合にも容易に拡張できる。
さて、MDFTについて説明するが、簡単なた
めに二次元の場合を考える。変換対象とするデー
タをai,jと表わす。ここで、 ｉ＝１，２，………，n1 ｊ＝１，２，………，n2 とする。このデータai,jを第５図イのように二次
元配列で表わす。第５図イでｉ方向を列方向、ｊ
の方向を行方向と呼ぶものとする。二次元
MDFTは原理的に次のように定式化される。
めに二次元の場合を考える。変換対象とするデー
タをai,jと表わす。ここで、 ｉ＝１，２，………，n1 ｊ＝１，２，………，n2 とする。このデータai,jを第５図イのように二次
元配列で表わす。第５図イでｉ方向を列方向、ｊ
の方向を行方向と呼ぶものとする。二次元
MDFTは原理的に次のように定式化される。
DO 20 Ｉ＝１，２
DO 10 Ｊ＝１，n1・n2／nI
大きさnIのDFT（一次元）
10 CONTINUE
20 CONTINUE
これを具体的に述べると、
Ｉ＝１のとき
第５図ロに示すような列方向の大きさn1のベ
クトル（列ベクトル）に対して、DFT（一次
元）を適用する。このDFT（一次元）は、ｊに
関するn2組の列ベクトルに対して適用する。
クトル（列ベクトル）に対して、DFT（一次
元）を適用する。このDFT（一次元）は、ｊに
関するn2組の列ベクトルに対して適用する。
Ｉ＝２のとき
第５図ハに示すような行方向の大きさn2のベ
クトル（行ベクトル）に対してDFT（一次元）
を適用する。このDFT（一次元）は、ｉに関す
るn1組の行ベクトルに対して適用する。ここ
で、はの処理によりａが変換されているこ
とを意味している。
クトル（行ベクトル）に対してDFT（一次元）
を適用する。このDFT（一次元）は、ｉに関す
るn1組の行ベクトルに対して適用する。ここ
で、はの処理によりａが変換されているこ
とを意味している。
上記のような，の処理を逐次に行うことに
より、二次元MDFTが実現される。ここで，
の処理順序は可換である。このように、
MDFTは入力データの部分ベクトルに対して
DFTを複数回適用することにより計算できる。
より、二次元MDFTが実現される。ここで，
の処理順序は可換である。このように、
MDFTは入力データの部分ベクトルに対して
DFTを複数回適用することにより計算できる。
次に、このMDFTを並列処理することを考え
る。この二次元MDFTの大きさは、説明の簡単
のためにn1＝４，n2＝８とする。また、データ
ai,jは、ｉに関して連続したメモリ上にあるもの
とする。即ち、データai,jのメモリ上での順番は、
a1，1，a2，1，………，a4，1，a1，2，a2，2，………
，
a4，2，a1，3，………，a1，4，………a1，8，a2，8，
………a4，8のように第一添字から変化する順番に
格納されているものとする。従来技術における処
理手順およびデータの流れは第６図に示される。
第６図の表記法は第３図と同様である。第６図に
従つて説明すると、ステージ（Stage）１および
２においては、大きさ４の一次元DFTを逐次処
理することを想定し、８組の同一の一次元DFT
を並列処理する。また、ステージ３，４および５
においては、大きさ８の一次元DFTを第３図に
従つて並列処理し、逐次にそれを４組行う。
る。この二次元MDFTの大きさは、説明の簡単
のためにn1＝４，n2＝８とする。また、データ
ai,jは、ｉに関して連続したメモリ上にあるもの
とする。即ち、データai,jのメモリ上での順番は、
a1，1，a2，1，………，a4，1，a1，2，a2，2，………
，
a4，2，a1，3，………，a1，4，………a1，8，a2，8，
………a4，8のように第一添字から変化する順番に
格納されているものとする。従来技術における処
理手順およびデータの流れは第６図に示される。
第６図の表記法は第３図と同様である。第６図に
従つて説明すると、ステージ（Stage）１および
２においては、大きさ４の一次元DFTを逐次処
理することを想定し、８組の同一の一次元DFT
を並列処理する。また、ステージ３，４および５
においては、大きさ８の一次元DFTを第３図に
従つて並列処理し、逐次にそれを４組行う。
この二次元MDFTの大きさを一般化してn1，
n2とすると、各ステージでは次の二つの何れかの
方法がとられる。すなわち、 大きさn1（又はn2）の一次元DFTを逐次処理
することを想定し、n2組（又はn1組）並列処理
する。
n2とすると、各ステージでは次の二つの何れかの
方法がとられる。すなわち、 大きさn1（又はn2）の一次元DFTを逐次処理
することを想定し、n2組（又はn1組）並列処理
する。
大きさn2（又はn1）の一次元DFTを並列処理
し、これをn1回（又はn2回）繰返す。
し、これをn1回（又はn2回）繰返す。
この二つの方法は、n1，n2の値に応じて並列処
理する際のベクトル長が可能な限り長くなるよう
に、いずれかが選択される。しかしながら、この
ような従来技術では ベクトルの長さは高さmax（n1，n2） 変換の対象となるデータのメモリ上の配置は
連続ではなくその間隔は最低min（n1，n2）と
なるため、さきに述べた並列処理条件が満され
ず、並列処理効率が充分に向上しない。
理する際のベクトル長が可能な限り長くなるよう
に、いずれかが選択される。しかしながら、この
ような従来技術では ベクトルの長さは高さmax（n1，n2） 変換の対象となるデータのメモリ上の配置は
連続ではなくその間隔は最低min（n1，n2）と
なるため、さきに述べた並列処理条件が満され
ず、並列処理効率が充分に向上しない。
(3) 発明の目的
本発明は、上記の考察に基づくものであつて、
MDFTを並列処理計算機上で実行する場合、先
に述べた並列処理要件を満足するようにして
MDFTを実行できるようにした多次元離散型フ
ーリエ変換計算方式を提供することを目的として
いる。
MDFTを並列処理計算機上で実行する場合、先
に述べた並列処理要件を満足するようにして
MDFTを実行できるようにした多次元離散型フ
ーリエ変換計算方式を提供することを目的として
いる。
(4) 発明の構成
そしてそのため、本発明の多次元離散型フーリ
エ変換計算方式は、メモリ、並列処理装置および
制御部を有する並列処理計算機を用いてＭ次元
（Ｍは１より大なる整数）の離散型フーリエ変換
を行う多次元離散型フーリエ変換計算方式におい
て、Ｍ次元配列のデータ群に属する2N個のデー
タai1,i2,………iMのそれぞれを第一添字から変化す
る順番に上記メモリの所定のデータ域に予め格納
すると共に、制御変数Ｌを初期値とし、しかる後
に、 (イ) 数値Ｎ、制御変数Ｌで示される次元の大きさ
nLに基づいて回転因子テーブルを作成する処理
と、 (ロ) 制御変数Ｉを数値“１”にする処理と、 (ハ) 上記メモリに格納されている2N個のデータ
のうちの先頭からＮ番目までのデータ列をベク
トルＶ，Ｎ＋１番目から2N番目のデータ列を
ベクトルV2としてベクトルV1とV2の加算を行
う処理と、 (ニ) ベクトルV1とV2の加算結果ベクトルの各デ
ータを上記データ域の先頭のデータ格納位置か
ら一つおきに格納する処理と、 (ホ) 上記のように定められたベクトルV1とV2の
減算を行う処理と、 (ヘ) 減算結果ベクトルに回転因子ベクトルを乗算
する処理と、 (ト) 乗算結果ベクトルの各データを上記データ域
の２番目のデータ格納位置から一つおきに順番
に格納する処理と、 (チ) 制御変数Ｉがlog2nLより小さいか否かを調べ
る処理と、 (リ) 上記(チ)でYesとされた場合には、数値Ｎ、数
値nLおよび制御変数Ｉの値に基づいて回転因子
テーブルを改訂し、しかる後に制御変数Ｉを単
位量だけ増加し、上記(ハ)の処理に戻る処理と、 (ヌ) 上記(チ)の処理でNoとされたときには制御変
数Ｌを単位量だけ更新し、制御変数Ｌが所定の
条件を満しているか否かを調べ、満している場
合には上記(イ)の処理に戻る処理と、 を行うことを特徴とするものである。
エ変換計算方式は、メモリ、並列処理装置および
制御部を有する並列処理計算機を用いてＭ次元
（Ｍは１より大なる整数）の離散型フーリエ変換
を行う多次元離散型フーリエ変換計算方式におい
て、Ｍ次元配列のデータ群に属する2N個のデー
タai1,i2,………iMのそれぞれを第一添字から変化す
る順番に上記メモリの所定のデータ域に予め格納
すると共に、制御変数Ｌを初期値とし、しかる後
に、 (イ) 数値Ｎ、制御変数Ｌで示される次元の大きさ
nLに基づいて回転因子テーブルを作成する処理
と、 (ロ) 制御変数Ｉを数値“１”にする処理と、 (ハ) 上記メモリに格納されている2N個のデータ
のうちの先頭からＮ番目までのデータ列をベク
トルＶ，Ｎ＋１番目から2N番目のデータ列を
ベクトルV2としてベクトルV1とV2の加算を行
う処理と、 (ニ) ベクトルV1とV2の加算結果ベクトルの各デ
ータを上記データ域の先頭のデータ格納位置か
ら一つおきに格納する処理と、 (ホ) 上記のように定められたベクトルV1とV2の
減算を行う処理と、 (ヘ) 減算結果ベクトルに回転因子ベクトルを乗算
する処理と、 (ト) 乗算結果ベクトルの各データを上記データ域
の２番目のデータ格納位置から一つおきに順番
に格納する処理と、 (チ) 制御変数Ｉがlog2nLより小さいか否かを調べ
る処理と、 (リ) 上記(チ)でYesとされた場合には、数値Ｎ、数
値nLおよび制御変数Ｉの値に基づいて回転因子
テーブルを改訂し、しかる後に制御変数Ｉを単
位量だけ増加し、上記(ハ)の処理に戻る処理と、 (ヌ) 上記(チ)の処理でNoとされたときには制御変
数Ｌを単位量だけ更新し、制御変数Ｌが所定の
条件を満しているか否かを調べ、満している場
合には上記(イ)の処理に戻る処理と、 を行うことを特徴とするものである。
(5) 発明の実施例
以下、本発明を図面を参照しつつ説明する。
第５図イに示すような二次元DFTに対する本
発明の並列処理手順は、第７図に示される。第７
図の表記法は第３図の場合と同様である。第７図
に沿つて説明すると、ステージ１，２および３に
おいては、大きさ８の一次元DFTを並列処理す
ることを４組同時に行う。また、ステージ４およ
び５においては、大きさ４の一次元DFTを並列
処理することを８組同時に行う。本発明の特色
は、回転因子の作成方法と改訂方法にあり、本発
明によれば、データの大きさn1，n2に関係なく ベクトルの長さは、常にn1・n2／２（これは
限界値の値である） 変換対象となるデータのメモリ上での配置
（データ間隔）は常に連続（間隔は常に１） となり、先に述べた並列処理条件は完全に満たさ
れ、並列処理効果は最大限発揮される。
発明の並列処理手順は、第７図に示される。第７
図の表記法は第３図の場合と同様である。第７図
に沿つて説明すると、ステージ１，２および３に
おいては、大きさ８の一次元DFTを並列処理す
ることを４組同時に行う。また、ステージ４およ
び５においては、大きさ４の一次元DFTを並列
処理することを８組同時に行う。本発明の特色
は、回転因子の作成方法と改訂方法にあり、本発
明によれば、データの大きさn1，n2に関係なく ベクトルの長さは、常にn1・n2／２（これは
限界値の値である） 変換対象となるデータのメモリ上での配置
（データ間隔）は常に連続（間隔は常に１） となり、先に述べた並列処理条件は完全に満たさ
れ、並列処理効果は最大限発揮される。
本発明を一般化し、Ｍ次元の場合について説明
する。各元の大きさをそれぞれn1，n2，………nM
とし、データai1，ai2，………，aiM（i1＝１，２…
……i1，i2＝１，２………n2，………，iM＝１，
２………nM） は、第一添字から変化する順番にメモリ上に格納
されているものとする。このＭ次元MDFTの処
理手順は第８図に示される。
する。各元の大きさをそれぞれn1，n2，………nM
とし、データai1，ai2，………，aiM（i1＝１，２…
……i1，i2＝１，２………n2，………，iM＝１，
２………nM） は、第一添字から変化する順番にメモリ上に格納
されているものとする。このＭ次元MDFTの処
理手順は第８図に示される。
回転因子テーブルの作成方法を更に詳しく説明
する。或るレベルＬ（Ｌ＝Ｍ，Ｍ−１，………又
は１）に対して先ず大きくnL／２のDFT用回転
因子テーブルを作成する。即ち ω＝exp（2πi／nL） として なる回転因子テーブルを作成する。簡単なために
このテーブルをξと表わし ξ＝｛ξ1，ξ2，………，ξoL／２｝ とする。
する。或るレベルＬ（Ｌ＝Ｍ，Ｍ−１，………又
は１）に対して先ず大きくnL／２のDFT用回転
因子テーブルを作成する。即ち ω＝exp（2πi／nL） として なる回転因子テーブルを作成する。簡単なために
このテーブルをξと表わし ξ＝｛ξ1，ξ2，………，ξoL／２｝ とする。
次に、ξを拡張し、大きさＮのMDFT用回転
因子テーブル（ξ〓と表わす）を作成する。この方
法は、ξの各要素を2N／nL個ずつ連続するよう
に拡張する。即ち、 ξ〓＝｛ξ1，ξ1，………ξ1，ξ2，ξ2，………，
ξ2，
………ξoL/2，ξoL/2，………，ξoL/2｝ なるテーブルを作成する。ただし、ξ1，ξ2，……
…ξoL/2の個数はそれぞれ2N／nL個である。
因子テーブル（ξ〓と表わす）を作成する。この方
法は、ξの各要素を2N／nL個ずつ連続するよう
に拡張する。即ち、 ξ〓＝｛ξ1，ξ1，………ξ1，ξ2，ξ2，………，
ξ2，
………ξoL/2，ξoL/2，………，ξoL/2｝ なるテーブルを作成する。ただし、ξ1，ξ2，……
…ξoL/2の個数はそれぞれ2N／nL個である。
回転因子テーブルの改訂方法を更に詳しく説明
する。改訂は、或るレベルＬ（Ｌ＝Ｍ，Ｍ−１，
………，１）に対して、（log2nL）−１回行う。い
ま、第Ｐ回の改訂を行う場合について述べると、
Ｓ回（Ｓ＝１，２，………，nL／4P）だけ次の
手順を繰り返す。即ち、回転因子テーブルの
（4PN／nL）＊（Ｓ−１）＋１番目から連続した
2PN／nL個の要素を回転因子テーブルの
（4PN／nL）＊（Ｓ−１）＋2PN／nL＋１番目から
連続して複写する。
する。改訂は、或るレベルＬ（Ｌ＝Ｍ，Ｍ−１，
………，１）に対して、（log2nL）−１回行う。い
ま、第Ｐ回の改訂を行う場合について述べると、
Ｓ回（Ｓ＝１，２，………，nL／4P）だけ次の
手順を繰り返す。即ち、回転因子テーブルの
（4PN／nL）＊（Ｓ−１）＋１番目から連続した
2PN／nL個の要素を回転因子テーブルの
（4PN／nL）＊（Ｓ−１）＋2PN／nL＋１番目から
連続して複写する。
具体例として第７図に示される二次元MDFT
の場合の回転因子テーブルの作成と改訂の実際を
第９図に示す。ここでは、Ｎ＝16（ｎ＝n1・n2／
２）である。第９図に沿つて説明すると、先ずＬ
＝２として、大きさを４（＝n2／２）のDFT用回
転因子テーブル ξ＝｛０，１，２，３｝ を作成する。なお、テーブルの各数値はωに対す
るべき数を示す。次に、ξを拡張した大きさ16
（＝Ｎ）のMDFT用回転因子テーブルξ〓を作成す
る。即ち、 ξ〓＝｛０，０，０，０，１，１，１，１，２，２，
２，２，３，３，３，３｝ を作成する。これがステージ１の回転因子テーブ
ルである。
の場合の回転因子テーブルの作成と改訂の実際を
第９図に示す。ここでは、Ｎ＝16（ｎ＝n1・n2／
２）である。第９図に沿つて説明すると、先ずＬ
＝２として、大きさを４（＝n2／２）のDFT用回
転因子テーブル ξ＝｛０，１，２，３｝ を作成する。なお、テーブルの各数値はωに対す
るべき数を示す。次に、ξを拡張した大きさ16
（＝Ｎ）のMDFT用回転因子テーブルξ〓を作成す
る。即ち、 ξ〓＝｛０，０，０，０，１，１，１，１，２，２，
２，２，３，３，３，３｝ を作成する。これがステージ１の回転因子テーブ
ルである。
次に改訂を行うか、その回数はＬ＝２では２
（＝log2n2−１）回である。その１回目（Ｐ＝１）
の改訂では次のように計２回の複写を行う。すな
わち、先ずＳ＝１として回転因子テーブルの１番
目から連続４（＝2PN／n2）個の要素を回転因子
テーブルの５（＝4PN／n2＊（Ｓ−１）＋2PN／n2
＋１）番目から連続して複写する。次にＳ＝２と
して、回転因子テーブルの９番目から連続４個の
要素を回転因子テーブルの第13番から連続して複
写する。この結果は、ステージ２の回転因子テー
ブルである。同様に２回目（Ｐ＝２）の改訂で
は、次のように１回の複写を行う。即ち、Ｓ＝１
として回転因子テーブルの１番目から連続８（＝
2PN／n2）個の要素を回転因子テーブルの９（＝
4PN／n2＊（Ｓ−１）＋2PN／n2＋１）番目から
連続して複写する。この結果がステージ３の回転
因子テーブルである。
（＝log2n2−１）回である。その１回目（Ｐ＝１）
の改訂では次のように計２回の複写を行う。すな
わち、先ずＳ＝１として回転因子テーブルの１番
目から連続４（＝2PN／n2）個の要素を回転因子
テーブルの５（＝4PN／n2＊（Ｓ−１）＋2PN／n2
＋１）番目から連続して複写する。次にＳ＝２と
して、回転因子テーブルの９番目から連続４個の
要素を回転因子テーブルの第13番から連続して複
写する。この結果は、ステージ２の回転因子テー
ブルである。同様に２回目（Ｐ＝２）の改訂で
は、次のように１回の複写を行う。即ち、Ｓ＝１
として回転因子テーブルの１番目から連続８（＝
2PN／n2）個の要素を回転因子テーブルの９（＝
4PN／n2＊（Ｓ−１）＋2PN／n2＋１）番目から
連続して複写する。この結果がステージ３の回転
因子テーブルである。
次にＬ＝１として、大きさ２（＝n1／２）の
DFT用回転因子テーブル ξ＝｛０，１｝ を作成する。次にξを拡張して大きさ16（＝Ｎ）
のMDFT用回転因子テーブルξを作成する。即
ち、 ξ〜＝｛０，０，０，０，０，０，０，０，１，１，１
，１，１，１，１，１｝ を作成する。これはステージ４の回転因子テーブ
ルである。次に改訂を行うが、その回数はレベル
Ｌ＝１では１（log2n1−１）回である。この改訂
はＰ＝１とし、次のように１回の複写を行う。即
ち、Ｓ＝１として回転因子テーブルの１番目から
連続８（＝2PN／n1）個の要素を回転因子テーブ
ルの９（4PN／n1＊（Ｓ−１）＋2PN／n1＋１）番
目から連続して複写する。この結果は、ステージ
５の回転因子テーブルである。
DFT用回転因子テーブル ξ＝｛０，１｝ を作成する。次にξを拡張して大きさ16（＝Ｎ）
のMDFT用回転因子テーブルξを作成する。即
ち、 ξ〜＝｛０，０，０，０，０，０，０，０，１，１，１
，１，１，１，１，１｝ を作成する。これはステージ４の回転因子テーブ
ルである。次に改訂を行うが、その回数はレベル
Ｌ＝１では１（log2n1−１）回である。この改訂
はＰ＝１とし、次のように１回の複写を行う。即
ち、Ｓ＝１として回転因子テーブルの１番目から
連続８（＝2PN／n1）個の要素を回転因子テーブ
ルの９（4PN／n1＊（Ｓ−１）＋2PN／n1＋１）番
目から連続して複写する。この結果は、ステージ
５の回転因子テーブルである。
第１０図は本発明を実施するためのハードウエ
ア構成の一実施例を示すものである。第１０図に
おいて、１２はメモリ装置、１３は制御装置、１
４はベクトル演算装置、１５はデータ転送装置、
１６はMDFT用回転因子テーブル発生・改訂装
置をそれぞれ示している。メモリ装置１２には、
演算対象となるベクトル・データや回転因子テー
ブルが格納される。制御装置１３は第８図に示さ
れるMDFTの処理手順に従つて各装置を制御す
るものである。データ転送装置１５は、メモリ装
置１２とベクトル演算装置１４との間のデータ転
送、およびメモリ装置１２とMDFT用回転因子
テーブル発生・改訂装置１６との間のデータ転送
を行うものである。ベクトル演算装置１４は、送
られて来たベクトル・データや回転因子テーブル
に対して各種の演算を並列処理する機能を有して
いる。MDFT用回転因子テーブル発生・改訂装
置１６は、先に述べたようにDFT用回転因子テ
ーブルに基づきMDFT用回転因子テーブルを作
成し、また、メモリ装置から送られて来た
MDFT用回転因子テーブルを改訂する機能を有
している。
ア構成の一実施例を示すものである。第１０図に
おいて、１２はメモリ装置、１３は制御装置、１
４はベクトル演算装置、１５はデータ転送装置、
１６はMDFT用回転因子テーブル発生・改訂装
置をそれぞれ示している。メモリ装置１２には、
演算対象となるベクトル・データや回転因子テー
ブルが格納される。制御装置１３は第８図に示さ
れるMDFTの処理手順に従つて各装置を制御す
るものである。データ転送装置１５は、メモリ装
置１２とベクトル演算装置１４との間のデータ転
送、およびメモリ装置１２とMDFT用回転因子
テーブル発生・改訂装置１６との間のデータ転送
を行うものである。ベクトル演算装置１４は、送
られて来たベクトル・データや回転因子テーブル
に対して各種の演算を並列処理する機能を有して
いる。MDFT用回転因子テーブル発生・改訂装
置１６は、先に述べたようにDFT用回転因子テ
ーブルに基づきMDFT用回転因子テーブルを作
成し、また、メモリ装置から送られて来た
MDFT用回転因子テーブルを改訂する機能を有
している。
(6) 発明の効果
以上の説明から明らかなように、本発明の多次
元離散型フーリエ変換計算方式によれば、並列処
理するデータの長さ（ベクトル長）を可能な限り
長くとる、並列処理するデータのメモリ上での間
隔（データ間隔）を可能な限り短くする、という
並列処理要件を完全に満しているので、処理効率
を大幅に向上することが可能である。
元離散型フーリエ変換計算方式によれば、並列処
理するデータの長さ（ベクトル長）を可能な限り
長くとる、並列処理するデータのメモリ上での間
隔（データ間隔）を可能な限り短くする、という
並列処理要件を完全に満しているので、処理効率
を大幅に向上することが可能である。
第１図および第２図は並列処理計算機の概要を
示す図、第３図はDFTの計算法を説明するため
の図、第４図は並列処理DFTの処理手順を示す
図、第５図は二次元配列、列ベクトルおよび行ベ
クトルの一例を示す図、第６図は従来技術による
MDFTの計算法を説明する図、第７図は本発明
による二次元DFTを行うための処理を説明する
図、第８図は本発明によるＭ次元MDFTの処理
手順を示す図、第９図は本発明による二次元
MDFTの回転因子テーブルの作成と改訂を説明
するための図、第１０図は本発明を実施するため
ハードウエア構成の一実施例を示す図である。 １２……メモリ装置、１３……制御装置、１４
……ベクトル演算装置、１５……データ転送装
置、１６……MDFT用回転因子テーブル発生、
改訂装置。
示す図、第３図はDFTの計算法を説明するため
の図、第４図は並列処理DFTの処理手順を示す
図、第５図は二次元配列、列ベクトルおよび行ベ
クトルの一例を示す図、第６図は従来技術による
MDFTの計算法を説明する図、第７図は本発明
による二次元DFTを行うための処理を説明する
図、第８図は本発明によるＭ次元MDFTの処理
手順を示す図、第９図は本発明による二次元
MDFTの回転因子テーブルの作成と改訂を説明
するための図、第１０図は本発明を実施するため
ハードウエア構成の一実施例を示す図である。 １２……メモリ装置、１３……制御装置、１４
……ベクトル演算装置、１５……データ転送装
置、１６……MDFT用回転因子テーブル発生、
改訂装置。
Claims (1)
- 【特許請求の範囲】 １ メモリ、並列処理装置および制御部を有する
並列処理計算機を用いてＭ次元（Ｍは１より大な
る整数）の離散型フーリエ変換を行う多次元離散
型フーリエ変換計算方式において、Ｍ次元配列の
データ群に属する2N個のデータai1,i2,……iMのそ
れぞれを第一添字から変化する順番に上記メモリ
の所定のデータ域に予め格納すると共に、制御変
数Ｌを初期値とし、しかる後に (イ) 数値Ｎ、制御変数Ｌで示される次元の大きさ
nLに基づいて回転因子テーブルを作成する処理
と、 (ロ) 制御変数Ｉを数値“１”にする処理と、 (ハ) 上記メモリに格納されている2N個のデータ
のうちの先頭からＮ番目までのデータ列をベク
トルV1，Ｎ＋１番目から2N番目のデータ列を
ベクトルV2としてベクトルV1とV2の加算を行
う処理と、 (ニ) ベクトルV1とV2の加算結果ベクトルの各デ
ータを上記データ域の先頭のデータ格納位置か
ら一つおきに格納する処理と、 (ホ) 上記のように定められたベクトルV1とV2の
減算を行う処理と、 (ヘ) 減算結果ベクトルに回転因子ベクトルを乗算
する処理と、 (ト) 乗算結果ベクトルの各データを上記データ域
の２番目のデータ格納位置から一つおきに順番
に格納する処理と、 (チ) 制御変数Ｉがlog2nLより小さいか否かを調べ
る処理と、 (リ) 上記(チ)でYesとされた場合には、数値Ｎ、数
値nLおよび制御変数Ｉの値に基づいて回転因子
テーブルを改訂し、しかる後に制御変数Ｉを単
位量だけ増加し、上記(ハ)の処理に戻る処理と、 (ヌ) 上記(チ)の処理でNoとされたときには制御変
数Ｌを単位量だけ更新し、制御変数Ｌが所定の
条件を満しているか否かを調べ、満している場
合には上記(イ)の処理に戻る処理と、 を行うことを特徴とする多次元離散型フーリエ変
換計算方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57031328A JPH0248941B2 (ja) | 1982-02-27 | 1982-02-27 | Tajigenrisangatafuuriehenkankeisanhoshiki |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57031328A JPH0248941B2 (ja) | 1982-02-27 | 1982-02-27 | Tajigenrisangatafuuriehenkankeisanhoshiki |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS58149564A JPS58149564A (ja) | 1983-09-05 |
| JPH0248941B2 true JPH0248941B2 (ja) | 1990-10-26 |
Family
ID=12328191
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57031328A Expired - Lifetime JPH0248941B2 (ja) | 1982-02-27 | 1982-02-27 | Tajigenrisangatafuuriehenkankeisanhoshiki |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0248941B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2560432B2 (ja) * | 1988-07-07 | 1996-12-04 | 日本電気株式会社 | ２次元フーリエ変換装置 |
| CN104883238B (zh) * | 2015-03-31 | 2018-05-01 | 重庆邮电大学 | 一种多载波时分复用调制/解调方法及系统 |
-
1982
- 1982-02-27 JP JP57031328A patent/JPH0248941B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS58149564A (ja) | 1983-09-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6839728B2 (en) | Efficient complex multiplication and fast fourier transform (FFT) implementation on the manarray architecture | |
| Alvarado | Parallel solution of transient problems by trapezoidal integration | |
| Wang | A parallel method for tridiagonal equations | |
| Lusk | Controlling redundancy in large search spaces: Argonne-style theorem proving through the years | |
| JPH0248941B2 (ja) | Tajigenrisangatafuuriehenkankeisanhoshiki | |
| JPS6314378B2 (ja) | ||
| Miranker et al. | Accurate Scientific Computations: Symposium, Bad Neuenahr, Federal Republic of Germany March 12-14, 1985. Proceedings | |
| JP3887097B2 (ja) | コンパイル方法，コンパイル装置および、コンパイル用プログラムを記憶したコンピュータ読み取り可能な記憶媒体 | |
| CN110008436A (zh) | 基于数据流架构的快速傅里叶变换方法、系统和存储介质 | |
| Sorensen et al. | Efficient FFT algorithms for DSP processors using tensor product decompositions | |
| CN113626760A (zh) | 用于对矩阵值灵活求和的设备和方法 | |
| JP2837547B2 (ja) | ベクトル計算機による行列積計算方法 | |
| Cooley | Rectangular transforms for digital convolution on the research signal processor | |
| JP2549838B2 (ja) | デ−タ制御装置 | |
| Stotts | OPTIMAL DISTRIBUTED MICROPROCESSOR ARCHITECTURE USING MULTI-PHASE PROCESSING TO PERFORM A VECTOR, MATRIX MULTIPLICATION | |
| JPH0644270B2 (ja) | ベクトルプロセッサの制御処理方式 | |
| JPS5846439A (ja) | 計算機のプログラム編集方法 | |
| Bywater | Second-order-difference integrator. Design base for realising high-resolution digital differential analysers | |
| CN119025805A (zh) | 基于数据流芯片进行批量矩阵乘计算的方法和装置 | |
| JPH0267602A (ja) | 数値演算装置 | |
| Duff et al. | Performance Issues for Frontal Schemes on High Performance Computer | |
| Hopper | Investigations of primal techniques for integer linear programs. | |
| Yeh | A task scheduling algorithm for the parallel expression evaluation in a reconfigurable fully digit on-line network | |
| JPS6252899B2 (ja) | ||
| Stephens | Fast Fourier Transforms on Transputers |