JPH0218668A - ２次元フーリエ変換装置 - Google Patents
２次元フーリエ変換装置Info
- Publication number
- JPH0218668A JPH0218668A JP63167774A JP16777488A JPH0218668A JP H0218668 A JPH0218668 A JP H0218668A JP 63167774 A JP63167774 A JP 63167774A JP 16777488 A JP16777488 A JP 16777488A JP H0218668 A JPH0218668 A JP H0218668A
- Authority
- JP
- Japan
- Prior art keywords
- data
- vector
- transformation
- dimensional
- parallel
- 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.)
- Granted
Links
- 230000009466 transformation Effects 0.000 title abstract description 19
- 239000013598 vector Substances 0.000 claims abstract description 48
- 238000006243 chemical reaction Methods 0.000 claims abstract description 31
- 238000000034 method Methods 0.000 claims abstract description 13
- 230000006866 deterioration Effects 0.000 abstract 1
- 238000011426 transformation method Methods 0.000 abstract 1
- 238000004364 calculation method Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 5
- 230000000694 effects Effects 0.000 description 3
- 238000007796 conventional method Methods 0.000 description 2
- 238000013500 data storage Methods 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はベクトルプロセッサを用いた２次元高速フーリ
エ変換装置に関し、特に各次元方向のデり長の差が大き
い時に、ベクトル長が短くなることに起因してベクトル
プロセッサの演算速度か低下することを防止しつつ変換
を行うことを可能とした２次元フーリエ変換装置に関す
る。
エ変換装置に関し、特に各次元方向のデり長の差が大き
い時に、ベクトル長が短くなることに起因してベクトル
プロセッサの演算速度か低下することを防止しつつ変換
を行うことを可能とした２次元フーリエ変換装置に関す
る。
従来、ベクトルプロセッサを用いた２次元フリエ変換で
は２例えば列方向の変換では各列を構成している１次元
データは互いに独立性をもつことに注目し、各列におい
て同一要素番号をもつものをベクトルデータとしてベク
トルプロセッサを行方向に動作させ２行方向のデータ数
をベクトル長としてベクトル処理していた。一方２行方
向の変換では、逆に列方向にベクトルプロセッサを動作
させる処理を行なっていた。
は２例えば列方向の変換では各列を構成している１次元
データは互いに独立性をもつことに注目し、各列におい
て同一要素番号をもつものをベクトルデータとしてベク
トルプロセッサを行方向に動作させ２行方向のデータ数
をベクトル長としてベクトル処理していた。一方２行方
向の変換では、逆に列方向にベクトルプロセッサを動作
させる処理を行なっていた。
第６図（ａ）は従来の手法による２次元フーリエ変換装
置の列方向変換を示す。なお、２次元フーリエ変換の列
方向２行方向のデータ数はそれぞれＮｘ 、 Ｎｙとす
る。同図において、２次元データが格納されているメモ
リ２」から各列データの同一行番号をもつ要素を長さＮ
ｙのベクトルとしてとり出し、ベクトルプロセノザで構
成された並列ノーリ工変換装置２２で演算を行う。
置の列方向変換を示す。なお、２次元フーリエ変換の列
方向２行方向のデータ数はそれぞれＮｘ 、 Ｎｙとす
る。同図において、２次元データが格納されているメモ
リ２」から各列データの同一行番号をもつ要素を長さＮ
ｙのベクトルとしてとり出し、ベクトルプロセノザで構
成された並列ノーリ工変換装置２２で演算を行う。
第６図（ｂ）の行方向変換では、各行データの同列番号
をもつ要素を長さＮｘのベクトルデータとしてとり出し
、同様に並列フーリエ変換装置２２で演算を行う。
をもつ要素を長さＮｘのベクトルデータとしてとり出し
、同様に並列フーリエ変換装置２２で演算を行う。
この方法では、各々のデータ数Ｎｘ、Ｎｙが近い値をと
るときは効率よく処理できる。しかしＮｘ、ＮｙＯ値が
大きく離れている場合１例えばＮｘ−＝ １．０２４
。
るときは効率よく処理できる。しかしＮｘ、ＮｙＯ値が
大きく離れている場合１例えばＮｘ−＝ １．０２４
。
Ｎｙ＝１６の場合２行方向変換のベクトル長は１０２４
と長いため効率がよいが２列方向変換のベク）−ル長は
１６と短い値をとるため、ベク）・ルプロセノザの効率
が低下するという欠点がある。
と長いため効率がよいが２列方向変換のベク）−ル長は
１６と短い値をとるため、ベク）・ルプロセノザの効率
が低下するという欠点がある。
本発明の２次元フーリエ変換装置は、単一の１次元デー
タに対し、そのデータ内の要素をとり出して作ったベク
トル要素に対してベクトル演算によってフーリエ変換を
馴算する単一データ列変換部と、同一の長さの複数個の
データに対し、同一の要素番号をもつものをとり出して
作成したベクトル要素に対して並列にベクトル演算によ
ってフリエ変換を計算する複数データ列並列変換部と入
力データの各次元の長さの関係により、ベク）・ル演算
の処理効率が最適となるように前記単一ブタ列変換部、
複数データ列並列変換部のどちらかを選択する変換方法
選択部を有している。
タに対し、そのデータ内の要素をとり出して作ったベク
トル要素に対してベクトル演算によってフーリエ変換を
馴算する単一データ列変換部と、同一の長さの複数個の
データに対し、同一の要素番号をもつものをとり出して
作成したベクトル要素に対して並列にベクトル演算によ
ってフリエ変換を計算する複数データ列並列変換部と入
力データの各次元の長さの関係により、ベク）・ル演算
の処理効率が最適となるように前記単一ブタ列変換部、
複数データ列並列変換部のどちらかを選択する変換方法
選択部を有している。
次に本発明について図面を用いて説明する。
第１図は１本発明の一実施例を示したブロック図である
。同図において、２は入力される２次元データの各方向
のサイズＮｘ 、Ｎｙの大きさ、および列方向のデータ
の格納間隔ｔの値によって行方向変換５列方向変換をそ
れぞれ、単一データ列変換部３．複数データ列並列変換
部４のどちらを用いてフーリエ変換を計算するのかの選
択を行う変換方法選択部、３は、２次元データのある行
、まだはある列をとりだした単一の１次元データに対し
。
。同図において、２は入力される２次元データの各方向
のサイズＮｘ 、Ｎｙの大きさ、および列方向のデータ
の格納間隔ｔの値によって行方向変換５列方向変換をそ
れぞれ、単一データ列変換部３．複数データ列並列変換
部４のどちらを用いてフーリエ変換を計算するのかの選
択を行う変換方法選択部、３は、２次元データのある行
、まだはある列をとりだした単一の１次元データに対し
。
ベクトル演算でフーリエ変換を計算する単一ブタ列変換
部、４は２次元データの全行、あるいは全列を同一の長
さから々る複数の１次元データとみなして、どれらを並
列にベクトル処理を行なってフーリエ変換を計算する複
数データ列並列変換部である。
部、４は２次元データの全行、あるいは全列を同一の長
さから々る複数の１次元データとみなして、どれらを並
列にベクトル処理を行なってフーリエ変換を計算する複
数データ列並列変換部である。
以下に動作を説明する。
第２図は、単一データ列変換部におけるデータ長ｎ ＝
８の時のデータの流れと演算・ぐターンを示した例で
ある。この図では、 ｐｅａｓｅの方法による変換例を
示しており、ベクトル長は記号Ｖの添字で同一のものを
もつものの個数で昔となる。
８の時のデータの流れと演算・ぐターンを示した例で
ある。この図では、 ｐｅａｓｅの方法による変換例を
示しており、ベクトル長は記号Ｖの添字で同一のものを
もつものの個数で昔となる。
第３図は複数データ列並列変換部による処理を示す。こ
の例では、長さｎ ＝ ８の１６組のデータｄ１．ｄ２
２．ｄ１６を変換する場合を示す。各データの同一要素
番号をもつデータから８個の長さ１６のベクトルデータ
Ｖｌ＋ Ｖ２＋ Ｖ３ ＋ ”” Ｂを構成し、フーリ
エ変換演算部では、これらのデータをベクトル長１６で
計算を行う。以上よりデータサイズがＮｘ 、 Ｎｙの
２次元データの場合２行方向変換では単一データ列変換
部を用いるとベクトル長はＮｙ／２ 、複数データ列並
列変換部を用いるとベク（５〕 トル長はＮｘである。
の例では、長さｎ ＝ ８の１６組のデータｄ１．ｄ２
２．ｄ１６を変換する場合を示す。各データの同一要素
番号をもつデータから８個の長さ１６のベクトルデータ
Ｖｌ＋ Ｖ２＋ Ｖ３ ＋ ”” Ｂを構成し、フーリ
エ変換演算部では、これらのデータをベクトル長１６で
計算を行う。以上よりデータサイズがＮｘ 、 Ｎｙの
２次元データの場合２行方向変換では単一データ列変換
部を用いるとベクトル長はＮｙ／２ 、複数データ列並
列変換部を用いるとベク（５〕 トル長はＮｘである。
変換方法選択部ではベクトル演算の効率が良くなるよう
次のように選択を行う。行方向変換では。
次のように選択を行う。行方向変換では。
第４図（ａ）のように１行方向のデータサイズＮｘとそ
のＮｘＯ値において、単一データ列変換部を用いた方が
処理効率が高く々るような最小の列方向ブタサイズＮｙ
の関係を示すテーブルを作成しておき、これらのテーブ
ルにより変換方法を選択する。
のＮｘＯ値において、単一データ列変換部を用いた方が
処理効率が高く々るような最小の列方向ブタサイズＮｙ
の関係を示すテーブルを作成しておき、これらのテーブ
ルにより変換方法を選択する。
このテーブルでは、たとえばＮｘ＝６４の時ＮＹの値が
５１２以上なら単一データ列変換部が選択され、５１２
より小さい場合は複数データ列並列変換部が選択される
。
５１２以上なら単一データ列変換部が選択され、５１２
より小さい場合は複数データ列並列変換部が選択される
。
実際にＮｘ＝ ６４ 、 Ｎｙ＝ １０２４の場合の処
理時間の短縮効果は以下のようになる。
理時間の短縮効果は以下のようになる。
第５図は２本フーリエ変換装置を構成しているベクトル
グロセノサのベクトル長と処理速度（単位時間内に処理
可能な演算数、即ちこの値が太きいほど処理効率が高い
）の−例を示しだものである。行方向変換においては、
演算数はＮｘ ×１０ ×ｕｙＸ４ｏｙ２ Ｎｙ ＝
３，２７６，８００である。従来の複数データ列並列変
換を用いると、ベクトル長は６４なので第５図より一秒
あたり２００ｘ１．０６演算が処理可能である。従って
、処理時間は３，２７６．８００÷（２００×］Ｏ）二
０．０１６４秒となる。
グロセノサのベクトル長と処理速度（単位時間内に処理
可能な演算数、即ちこの値が太きいほど処理効率が高い
）の−例を示しだものである。行方向変換においては、
演算数はＮｘ ×１０ ×ｕｙＸ４ｏｙ２ Ｎｙ ＝
３，２７６，８００である。従来の複数データ列並列変
換を用いると、ベクトル長は６４なので第５図より一秒
あたり２００ｘ１．０６演算が処理可能である。従って
、処理時間は３，２７６．８００÷（２００×］Ｏ）二
０．０１６４秒となる。
本発明の場合は、第４図（ａ）で示したように、単デー
タ列変換部が選択され、この場合のベクトル長はＮｙ／
２＝ ５１−２ 、すなわち第５図より処理速度は５０
５Ｘ１０６（演算７秒）であるから、処理時間は３，２
７６．８００＋（５０５Ｘ１０６）＝０００６４９秒と
ナルので、約６０％の処理時間が短縮されることと々る
。
タ列変換部が選択され、この場合のベクトル長はＮｙ／
２＝ ５１−２ 、すなわち第５図より処理速度は５０
５Ｘ１０６（演算７秒）であるから、処理時間は３，２
７６．８００＋（５０５Ｘ１０６）＝０００６４９秒と
ナルので、約６０％の処理時間が短縮されることと々る
。
以」−説明したように本発明は、ベクトルプロセッサで
構成した２次元フーリエ変換装置において。
構成した２次元フーリエ変換装置において。
単一データ列変換部、複数データ列並列変換部を備え、
さらに入力データサイズＮｘ 、Ｎｙの関係により、上
記２つの変換部のうち最適たものを選択する変換方法選
択部をもつことによって、常に最適な効率でベクトルプ
ロセッサで変換処理を行うことができる効果がある。
さらに入力データサイズＮｘ 、Ｎｙの関係により、上
記２つの変換部のうち最適たものを選択する変換方法選
択部をもつことによって、常に最適な効率でベクトルプ
ロセッサで変換処理を行うことができる効果がある。
第１図は本発明の２次元フーリエ変換装置の構成図で、
第２図は、単一データ列変換部のベクトル演算を説明す
るだめの図、第３図は複数データ列並列変換部のベクト
ル演算を説明するだめの図。 第４図は本発明による変換方法選択テーブルを示した図
、第５図はベクトル長と処理速度の関係を示すテーブル
を示した図、第６図は従来の方式による２次元フーリエ
変換手順を説明するだめの図である。 １は入力の２次元データ、２は変換方法選択部。 ３は単一データ列変換部、４は複数データ列並列変換部
。 第６図 （（１，） 長さＮｙのベクトル処理
第２図は、単一データ列変換部のベクトル演算を説明す
るだめの図、第３図は複数データ列並列変換部のベクト
ル演算を説明するだめの図。 第４図は本発明による変換方法選択テーブルを示した図
、第５図はベクトル長と処理速度の関係を示すテーブル
を示した図、第６図は従来の方式による２次元フーリエ
変換手順を説明するだめの図である。 １は入力の２次元データ、２は変換方法選択部。 ３は単一データ列変換部、４は複数データ列並列変換部
。 第６図 （（１，） 長さＮｙのベクトル処理
Claims (1)
- １、ベクトルプロセッサを用いた２次元フーリエ変換装
置において、単一の１次元データをベクトル処理する単
一データ列変換部と、複数組の１次元データを並列にベ
クトル処理する並列変換部と、変換すべき２次元データ
の各方向のサイズの関係より、ベクトル長が長い演算を
行なって、ベクトルプロセッサの動作効率が高くなるよ
うに前記単一データ列変換部、並列変換部の選択を行う
変換方法選択部とを有する２次元フーリエ変換装置。
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 true JPH0218668A (ja) | 1990-01-22 |
| JP2560432B2 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) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58149564A (ja) * | 1982-02-27 | 1983-09-05 | Fujitsu Ltd | 多次元離散型フ−リエ変換計算方式 |
-
1988
- 1988-07-07 JP JP63167774A patent/JP2560432B2/ja not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58149564A (ja) * | 1982-02-27 | 1983-09-05 | Fujitsu Ltd | 多次元離散型フ−リエ変換計算方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2560432B2 (ja) | 1996-12-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP7793585B2 (ja) | ハードウェアにおけるスパース行列乗算 | |
| US6029185A (en) | Discrete cosine high-speed arithmetic unit and related arithmetic unit | |
| JPS6053349B2 (ja) | 画像処理プロセツサ | |
| CN112784973A (zh) | 卷积运算电路、装置以及方法 | |
| CN109726822B (zh) | 运算方法、装置及相关产品 | |
| JP3852895B2 (ja) | 乗法演算節減可能な二次元離散コサイン変換及びその逆変換の実行方法 | |
| US9002919B2 (en) | Data rearranging circuit, variable delay circuit, fast fourier transform circuit, and data rearranging method | |
| WO2007099950A1 (ja) | 高速ｐｅ間データ再配置機能を有するプロセッサアレイシステム | |
| JPH02273867A (ja) | 行列演算装置 | |
| CN116542294A (zh) | 一种适用于大卷积核的三维Winograd嵌套方法 | |
| CN106454382B (zh) | 一种量子图像制备方法 | |
| JPS6310263A (ja) | ベクトル処理装置 | |
| Hsiao et al. | A cost-efficient and fully-pipelinable architecture for DCT/IDCT | |
| JP2560432B2 (ja) | ２次元フーリエ変換装置 | |
| JP7513316B1 (ja) | ベクトルプロセッサ、ベクトルプロセッサの制御方法、及び、プログラム | |
| Liu et al. | On general factorizations for n-D polynomial matrices | |
| WO2020039522A1 (ja) | 情報処理装置、情報処理方法及びプログラム | |
| KR19990017608A (ko) | 신호 처리 프로세서의 연산 유닛 및 입출력 장치 | |
| JPH047668A (ja) | 半導体集積回路 | |
| JPH0484218A (ja) | 可変長多バイトデータ変換装置 | |
| KR970025177A (ko) | 단일화된 시스톨릭어레이 구조에 의한 dct/dst/dht의 수행 방법 및 그 장치 | |
| JP2895892B2 (ja) | データ処理装置 | |
| CN119155037A (zh) | 基于avx512ifma的椭圆曲线的并行点加方法 | |
| JPS62295174A (ja) | 並列デ−タ処理装置 | |
| Saeki et al. | An application of interior point method to 0-1 mixed integer programing problems |
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 |