JP2560432B2 - ２次元フーリエ変換装置 - Google Patents
２次元フーリエ変換装置Info
- Publication number
- JP2560432B2 JP2560432B2 JP63167774A JP16777488A JP2560432B2 JP 2560432 B2 JP2560432 B2 JP 2560432B2 JP 63167774 A JP63167774 A JP 63167774A JP 16777488 A JP16777488 A JP 16777488A JP 2560432 B2 JP2560432 B2 JP 2560432B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- vector
- fourier transform
- dimensional
- data size
- 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
- 238000006243 chemical reaction Methods 0.000 claims description 45
- 238000000034 method Methods 0.000 claims description 13
- 238000010586 diagram Methods 0.000 description 7
- 238000007796 conventional method Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000003247 decreasing effect Effects 0.000 description 1
- 238000004904 shortening Methods 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明はベクトルプロセッサを用いた２次元高速フー
リエ変換装置に関し，特に各次元方向のデータ長の差が
大きい時に，ベクトル長が短くなることに起因してベク
トルプロセッサの演算速度が低下することを防止しつつ
変換を行うことを可能とした２次元フーリエ変換装置に
関する。
リエ変換装置に関し，特に各次元方向のデータ長の差が
大きい時に，ベクトル長が短くなることに起因してベク
トルプロセッサの演算速度が低下することを防止しつつ
変換を行うことを可能とした２次元フーリエ変換装置に
関する。
従来，ベクトルプロセッサを用いた２次元フーリエ変
換では，例えば列方向の変換では各列を構成している１
次元データは互いに独立性をもつことに注目し，各列に
おいて同一要素番号をもつものをベクトルデータとして
ベクトルプロセッサを行方向に動作させ，行方向のデー
タ数をベクトル長としてベクトル処理していた。一方，
行方向の変換では，逆に列方向にベクトルプロセッサを
動作させる処理を行なっていた。
換では，例えば列方向の変換では各列を構成している１
次元データは互いに独立性をもつことに注目し，各列に
おいて同一要素番号をもつものをベクトルデータとして
ベクトルプロセッサを行方向に動作させ，行方向のデー
タ数をベクトル長としてベクトル処理していた。一方，
行方向の変換では，逆に列方向にベクトルプロセッサを
動作させる処理を行なっていた。
第６図（ａ）は従来の手法による２次元フーリエ変換
装置の列方向変換を示す。なお,2次元フーリエ変換の列
方向，行方向のデータ数はそれぞれNx,Nyとする。同図
において,2次元データが格納されているメモリ21から各
列データの同一行番号をもつ要素を長さNyのベクトルと
してとり出し，ベクトルプロセッサで構成された並列フ
ーリエ変換装置22で演算を行う。
装置の列方向変換を示す。なお,2次元フーリエ変換の列
方向，行方向のデータ数はそれぞれNx,Nyとする。同図
において,2次元データが格納されているメモリ21から各
列データの同一行番号をもつ要素を長さNyのベクトルと
してとり出し，ベクトルプロセッサで構成された並列フ
ーリエ変換装置22で演算を行う。
第６図（ｂ）の行方向変換では，各行データの同一列
番号をもつ要素を長さNxのベクトルデータとしてとり出
し，同様に並列フーリエ変換装置22で演算を行う。
番号をもつ要素を長さNxのベクトルデータとしてとり出
し，同様に並列フーリエ変換装置22で演算を行う。
この方法では，各々のデータ数Nx,Nyが近い値をとる
ときは効率よく処理できる。しかしNx,Nyの値が大きく
離れている場合，例えばNx＝1024,Ny＝16の場合，行方
向変換のベクトル長は1024と長いため効率がよいが，列
方向変換のベクトル長は16と短い値をとるため，ベクト
ルプロセッサの効率が低下するという欠点がある。
ときは効率よく処理できる。しかしNx,Nyの値が大きく
離れている場合，例えばNx＝1024,Ny＝16の場合，行方
向変換のベクトル長は1024と長いため効率がよいが，列
方向変換のベクトル長は16と短い値をとるため，ベクト
ルプロセッサの効率が低下するという欠点がある。
本発明の２次元フーリエ変換装置は，単一の１次元デ
ータに対し，そのデータ内の要素をとり出して作ったベ
クトル要素に対してベクトル演算によってフーリエ変換
を計算する単一データ列変換部と，同一の長さの複数個
のデータに対し，同一の要素番号をもつものをとり出し
て作成したベクトル要素に対して並列にベクトル演算に
よってフーリエ変換を計算する複数データ列並列変換部
と，変換すべき２次元データの行方向のデータサイズNx
と列方向のデータサイズNyに関してあらかじめ定められ
たテーブルを参照して、ベクトルプロセッサの処理効率
が高くなるように前記単一データ列変換部、前記並列変
換部のいずれかの選択を行う変換方法選択部とを有し、
前記あらかじめ定められたテーブルは、前記データサイ
ズNxと該データサイズNxの値において前記単一データ列
変換部を用いた方が前記処理効率が高くなるような最小
のデータサイズNyとの関係、及び前記データサイズNyと
該データサイズNyの値において前記単一データ列変換部
を用いた方が前記処理効率が高くなるような最小のデー
タサイズNxとの関係を示すものであることを特徴とす
る。
ータに対し，そのデータ内の要素をとり出して作ったベ
クトル要素に対してベクトル演算によってフーリエ変換
を計算する単一データ列変換部と，同一の長さの複数個
のデータに対し，同一の要素番号をもつものをとり出し
て作成したベクトル要素に対して並列にベクトル演算に
よってフーリエ変換を計算する複数データ列並列変換部
と，変換すべき２次元データの行方向のデータサイズNx
と列方向のデータサイズNyに関してあらかじめ定められ
たテーブルを参照して、ベクトルプロセッサの処理効率
が高くなるように前記単一データ列変換部、前記並列変
換部のいずれかの選択を行う変換方法選択部とを有し、
前記あらかじめ定められたテーブルは、前記データサイ
ズNxと該データサイズNxの値において前記単一データ列
変換部を用いた方が前記処理効率が高くなるような最小
のデータサイズNyとの関係、及び前記データサイズNyと
該データサイズNyの値において前記単一データ列変換部
を用いた方が前記処理効率が高くなるような最小のデー
タサイズNxとの関係を示すものであることを特徴とす
る。
次に本発明について図面を用いて説明する。
第１図は，本発明の一実施例を示したブロック図であ
る。同図において,2は入力される２次元データの各方向
のサイズNx,Nyの大きさ，および列方向のデータの格納
間隔ｌの値によって行方向変換，列方向変換をそれぞ
れ，単一データ列変換部3,複数データ列並列変換部４の
どちらを用いてフーリエ変換を計算するのかの選択を行
う変換方法選択部,3は,2次元データのある行，またはあ
る列をとりだした単一の１次元データに対し，ベクトル
演算でフーリエ変換を計算する単一データ列変換部,4は
２次元データの全行，あるいは全列を同一の長さからな
る複数の１次元データとみなして，これらを並列にベク
トル処理を行なってフーリエ変換を計算する複数データ
列並列変換部である。
る。同図において,2は入力される２次元データの各方向
のサイズNx,Nyの大きさ，および列方向のデータの格納
間隔ｌの値によって行方向変換，列方向変換をそれぞ
れ，単一データ列変換部3,複数データ列並列変換部４の
どちらを用いてフーリエ変換を計算するのかの選択を行
う変換方法選択部,3は,2次元データのある行，またはあ
る列をとりだした単一の１次元データに対し，ベクトル
演算でフーリエ変換を計算する単一データ列変換部,4は
２次元データの全行，あるいは全列を同一の長さからな
る複数の１次元データとみなして，これらを並列にベク
トル処理を行なってフーリエ変換を計算する複数データ
列並列変換部である。
以下に動作を説明する。
第２図は，単一データ列変換部におけるデータ長ｎ＝
８の時のデータの流れと演算パターンを示した例であ
る。この図では,Peaseの方法による変換列を示してお
り，ベクトル長は記号ｖの添字で同一のものをもつもの
の個数でn/2となる。
８の時のデータの流れと演算パターンを示した例であ
る。この図では,Peaseの方法による変換列を示してお
り，ベクトル長は記号ｖの添字で同一のものをもつもの
の個数でn/2となる。
第３図は複数データ列並列変換部による処理を示す。
この例では，長さｎ＝８の16組のデータd1,d2,…,d16を
変換する場合を示す。各データの同一要素番号をもつデ
ータから８個の長さ16のベクトルデータv1,v2,v3,…v8
を構成し，フーリエ変換演算部では，これらのデータを
ベクトル長16で計算を行う。以上よりデータサイズがN
x,Nyの２次元データの場合，行方向変換では単一データ
列変換部を用いるとベクトル長はNy/2,複数データ列並
列変換部を用いるとベクトル長はNxである。
この例では，長さｎ＝８の16組のデータd1,d2,…,d16を
変換する場合を示す。各データの同一要素番号をもつデ
ータから８個の長さ16のベクトルデータv1,v2,v3,…v8
を構成し，フーリエ変換演算部では，これらのデータを
ベクトル長16で計算を行う。以上よりデータサイズがN
x,Nyの２次元データの場合，行方向変換では単一データ
列変換部を用いるとベクトル長はNy/2,複数データ列並
列変換部を用いるとベクトル長はNxである。
変換方法選択部ではベクトル演算の効率が良くなるよ
う次のように選択を行う。行方向変換では，第４図
（ａ）のように，行方向のデータサイズNxとそのNxの値
において，単一データ列変換部を用いた方が処理効率が
高くなるような最小の列方向データサイズNyの関係を示
すテーブルを作成しておき，これらのテーブルにより変
換方法を選択する。このテーブルでは，たとえばNx＝64
の時Nyの値が512以上なら単一データ列変換部が選択さ
れ,512より小さい場合は複数データ列並列変換部が選択
される。
う次のように選択を行う。行方向変換では，第４図
（ａ）のように，行方向のデータサイズNxとそのNxの値
において，単一データ列変換部を用いた方が処理効率が
高くなるような最小の列方向データサイズNyの関係を示
すテーブルを作成しておき，これらのテーブルにより変
換方法を選択する。このテーブルでは，たとえばNx＝64
の時Nyの値が512以上なら単一データ列変換部が選択さ
れ,512より小さい場合は複数データ列並列変換部が選択
される。
実際にNx＝64,Ny＝1024の場合の処理時間の短縮効果
は以下のようになる。
は以下のようになる。
第５図は，本フーリエ変換装置を構成しているベクト
ルプロセッサのベクトル長と処理速度（単位時間内に処
理可能な演算数，即ちこの値が大きいほど処理効率が高
い）の一例を示したものである。行方向変換において
は，演算数は である。従来の複数データ列並列変換を用いると，ベク
トル長は64なので第５図より一秒あたり200×106演算が
処理可能である。従って，処理時間は3,276,800÷（200
×106）＝0.0164秒となる。
ルプロセッサのベクトル長と処理速度（単位時間内に処
理可能な演算数，即ちこの値が大きいほど処理効率が高
い）の一例を示したものである。行方向変換において
は，演算数は である。従来の複数データ列並列変換を用いると，ベク
トル長は64なので第５図より一秒あたり200×106演算が
処理可能である。従って，処理時間は3,276,800÷（200
×106）＝0.0164秒となる。
本発明の場合は，第４図（ａ）で示したように，単一
データ列変換部が選択され，この場合のベクトル長はNy
/2＝512,すなわち第５図より処理速度は505×106（演算
／秒）であるから，処理時間は3,276,800÷（505×1
06）＝0.00649秒となるので，約60％の処理時間が短縮
されることとなる。
データ列変換部が選択され，この場合のベクトル長はNy
/2＝512,すなわち第５図より処理速度は505×106（演算
／秒）であるから，処理時間は3,276,800÷（505×1
06）＝0.00649秒となるので，約60％の処理時間が短縮
されることとなる。
以上説明したように本発明は，ベクトルプロセッサで
構成した２次元フーリエ変換装置において，単一データ
列変換部，複数データ列並列変換部を備え，さらに入力
データサイズNx,Nyの関係により，上記２つの変換部の
うち最適なものを選択する変換方法選択部をもつことに
よって，常に最適な効率でベクトルプロセッサで変換処
理を行うことができる効果がある。
構成した２次元フーリエ変換装置において，単一データ
列変換部，複数データ列並列変換部を備え，さらに入力
データサイズNx,Nyの関係により，上記２つの変換部の
うち最適なものを選択する変換方法選択部をもつことに
よって，常に最適な効率でベクトルプロセッサで変換処
理を行うことができる効果がある。
第１図は本発明の２次元フーリエ変換装置の構成図で，
第２図は，単一データ列変換部のベクトル演算を説明す
るための図，第３図は複数データ列並列変換部のベクト
ル演算を説明するための図，第４図は本発明による変換
方法選択テーブルを示した図，第５図はベクトル長と処
理速度の関係を示すテーブルを示した図，第６図は従来
の方式による２次元フーリエ変換手順を説明するための
図である。 １は入力の２次元データ,2は変換方法選択部,3は単一デ
ータ列変換部,4は複数データ列並列変換部。
第２図は，単一データ列変換部のベクトル演算を説明す
るための図，第３図は複数データ列並列変換部のベクト
ル演算を説明するための図，第４図は本発明による変換
方法選択テーブルを示した図，第５図はベクトル長と処
理速度の関係を示すテーブルを示した図，第６図は従来
の方式による２次元フーリエ変換手順を説明するための
図である。 １は入力の２次元データ,2は変換方法選択部,3は単一デ
ータ列変換部,4は複数データ列並列変換部。
Claims (1)
- 【請求項１】ベクトルプロセッサを用いた２次元フーリ
エ変換装置において、単一の１次元データをベクトル処
理する単一データ列変換部と、複数組の１次元データを
並列にベクトル処理する並列変換部と、変換すべき２次
元データの行方向のデータサイズNxと列方向のデータサ
イズNyに関してあらかじめ定められたテーブルを参照し
て、ベクトルプロセッサの処理効率が高くなるように前
記単一データ列変換部、前記並列変換部のいずれかの選
択を行う変換方法選択部とを有し、前記あらかじめ定め
られたテーブルは、前記データサイズNxと該データサイ
ズNxの値において前記単一データ列変換部を用いた方が
前記処理効率が高くなるような最小のデータサイズNyと
の関係、及び前記データサイズNyと該データサイズNyの
値において前記単一データ列変換部を用いた方が前記処
理効率が高くなるような最小のデータサイズNxとの関係
を示すものであることを特徴とする２次元フーリエ変換
装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63167774A JP2560432B2 (ja) | 1988-07-07 | 1988-07-07 | ２次元フーリエ変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63167774A JP2560432B2 (ja) | 1988-07-07 | 1988-07-07 | ２次元フーリエ変換装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0218668A JPH0218668A (ja) | 1990-01-22 |
| JP2560432B2 true JP2560432B2 (ja) | 1996-12-04 |
Family
ID=15855860
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63167774A Expired - Lifetime JP2560432B2 (ja) | 1988-07-07 | 1988-07-07 | ２次元フーリエ変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2560432B2 (ja) |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0248941B2 (ja) * | 1982-02-27 | 1990-10-26 | Fujitsu Ltd | Tajigenrisangatafuuriehenkankeisanhoshiki |
-
1988
- 1988-07-07 JP JP63167774A patent/JP2560432B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0218668A (ja) | 1990-01-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4965762A (en) | Mixed size radix recoded multiplier | |
| JP2002351858A (ja) | 処理装置 | |
| JP2560432B2 (ja) | ２次元フーリエ変換装置 | |
| JPH04280368A (ja) | Ｄｃｔマトリクス演算回路 | |
| JP3668356B2 (ja) | 高速フーリエ変換演算回路 | |
| JPH07234864A (ja) | 直交変換装置 | |
| US4325056A (en) | BCD To binary converter | |
| JPH10340340A (ja) | 画像処理装置 | |
| JPS6226723B2 (ja) | ||
| JP3223530B2 (ja) | データ転送命令生成処理方法 | |
| JP2002504250A (ja) | データ要素の系列を変換する装置 | |
| JPH05189554A (ja) | ２次元配列データ回転装置 | |
| JP3525960B2 (ja) | 並列ソート方式 | |
| CN120335870A (zh) | 一种基于向量处理器的混合基fft的数据混洗方法 | |
| JP2580501B2 (ja) | 並列デ−タ処理装置 | |
| GAUDIOT | ON PROGRAM DECOMPOSITION AND PARTITIONING IN DATA-FLOW SYSTEMS. | |
| JP2004258842A (ja) | 遺伝的アルゴリズムを用いた並列処理装置 | |
| JPH0524552B2 (ja) | ||
| CN120104188A (zh) | 一种基于向量处理器的基4-fft的数据混洗方法 | |
| JP2835366B2 (ja) | 高速フーリエ変換用アドレス情報発生装置 | |
| Lun et al. | Extended diagonal structure for address generation of the prime factor algorithm | |
| JP3320767B2 (ja) | データ処理装置及びその制御方法 | |
| JP2845428B2 (ja) | 巾乗器 | |
| JPS6361710B2 (ja) | ||
| JPS63262760A (ja) | 高速フ−リエ変換装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080919 Year of fee payment: 12 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080919 Year of fee payment: 12 |