JPH06110917A - ベクトル計算機 - Google Patents

Abstract

(57)【要約】 【目的】 高速でフーリエ変換を行なうことのできるベ
クトル計算機を提供することを目的とする。 【構成】 多次元データを１次元的に並べる配列手段
と、前記配列においてバタフライ演算を行うバタフライ
演算部と、バタフライ演算終了後のデータを並べ換える
並べ換え手段とを有し、前記バタフライ演算及びデータ
の並べ換えを１回以上繰り返してフーリエ変換を行な
う。 【効果】 フーリエ変換の演算が高速化される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はフーリエ変換を行なうベ
クトル計算機に係り、特に高速に演算を行なう技術に関
する。

【０００２】

【従来の技術】従来より、画像処理や物性計算の分野に
おいて、フーリエ変換が多く使用されており、高速にフ
ーリエ変換を行なうことのできるベクトル計算機の出現
が望まれている。

【０００３】一般に、多次元離散フーリエ変換は次式に
よって定義される。

【０００４】

【数１】 ここでｎは次元数、Ｎ_i （ｉ＝１，…，ｎ）は各次元に
対するデータ数である。（１）式は次のように変形され
る。

【０００５】

【数２】 （２）式より多次元離散フーリエ変換は、ｊ₁ ，……，
ｊ_n-1 を固定しｊ_n に関してフーリエ変換を行ない、次
にｊ₁ ，…，ｊ_n-2 ，ｊ_n を固定しｊ_n-1 に関して変換
する、というように１次元離散フーリエ変換を次元数回
繰り返せばよいことがわかる。ＦＦＴ（高速フーリエ変
換）の場合も同様で、多次元ＦＦＴは１次元ＦＦＴを次
元数回繰り返すことにより計算できる。

【０００６】また、繰り返し数Ｎ_i （ｉ＝１，…，ｎ）
の外側ループとＦＦＴのアルゴリズム内のループを交換
して実行する方法もある。ここで、１次元ＦＦＴの仕組
みを簡単のためにＮ＝８の場合について述べる。１次元
離散フーリエ変換は次の（３）式によって定義される。

【０００７】

【数３】 （３）式の定義通り計算を行なえば、８個のデータを変
換するのに８×８＝６４回の演算が必要である。しかし
ＦＦＴでは８×３＝２４回の演算で済ませられる。
（３）式において

【数４】 とし、その変換の様子を図１８に示す。８個のデータｆ
（ｊ）｛ｊ＝０，…，７｝は図１８のように３段階で変
換される。図１８からわかるように、ｆ（０）とｆ
（４）からｇ（０）とｇ（４）が生成される。ｆ（０）
とｆ（４）はｇ（０）とｇ（４）以外の値を求めるのに
必要ないのでｇ（０）とｇ（４）はｆ（０）とｆ（４）
の上に重ね書き出来る。このデータの流れを図で表すと
交差した形が得られるので、この演算はバタフライ演算
と呼ばれている。また、ｇ（０）とｇ（２）からｈ
（０）とｈ（４）が生成されるが、ｇ（０）とｇ（２）
はｈ（０）とｈ（４）以外の計算には必要ないので同様
に重ね書き出来る。

【０００８】この重ね書きによるデータの変換の様子を
図１９に示す。この方法は余分な記憶容量を取らないと
いう利点があるが、最後に得られるｃ（ｋ）は正しい順
序に並んでいない。そこで、通常は最後にデータの入れ
換えを行なっている。

【０００９】図１８の変換の様子を見るとｃ（ｋ）は正
しい順に並んでいる。そこで重ね書きをせずに作業用配
列を使用し、最後の並べ換えを必要としないスーパーコ
ンピュータ向けのＳｔｏｃｋｈａｍのアルゴリズムにつ
いて述べる。

【００１０】ＦＦＴの中間段階第ｌ段におけるＮ（＝２
^p ）個のデータは次の（５）式のように定義される。

【００１１】

【数５】 となり、これは初期データである。また、ｌ＝ｐのとき
ｊ＝０で

【数６】 となり、これは求めるフーリエ変換そのものである。さ
らにＸ_l とＸ_l+1 の間には次の漸化式が成り立ってい
る。

【００１２】

【数７】 この変換を図示すると図２０のようになる。この操作を
１列の縦ベクトルから始め、１行の横ベクトルになるま
で繰り返せばフーリエ変換出来たことになる。Ｎ＝８の
場合のＦＦＴの流れを図２１に示す。図２１より初期デ
ータはｆ（０），ｆ（１），…，ｆ（Ｎ−１）の順に、
結果はｃ（０），ｃ（１），…，ｃ（Ｎ−１）の順に格
納されているので最後のデータの入れ換えは必要ないこ
とがわかる。

【００１３】この方法はベクトル化可能であり、データ
数Ｎを大きくとればベクトル長が大きくなるのでスーパ
ーコンピュータで実行するのに有効である。前述したよ
うに多次元ＦＦＴは１次元ＦＦＴを次元数回繰り返すこ
とによって計算できる。従って多次元ＦＦＴの場合は各
次元のデータ数Ｎ_i を大きくとればベクトル長が大きく
なり有効である。

【００１４】

【発明が解決しようとする課題】このように従来におけ
るベクトル計算機ではフーリエ変換を行う際のベクトル
長が短いので計算に時間がかかるという問題点があっ
た。

【００１５】この発明はこのような従来の課題を解決す
るためになされたもので、その目的とするところは、ベ
クトル長を長くしてフーリエ変換を行なうことのできる
ベクトル計算機を提供することにある。

【００１６】

【課題を解決するための手段】上記目的を達成するた
め、本発明は、多次元フーリエ変換を演算するベクルト
計算機において、多次元データを１次元的に並べる配列
手段と、前記配列においてバタフライ演算を行うバタフ
ライ演算手段と、バタフライ演算終了後のデータを並べ
換える並べ換え手段とを有し、前記バタフライ演算及び
データの並べ換えを１回以上繰り返してフーリエ変換を
行なうことが特徴である。

【００１７】

【作用】上述の如く構成された本発明では、入力データ
をデータ配列手段によって１次元的に並べ換え、更にバ
タフライ演算後のデータを並べ換え手段によって並べ換
えている。従って、ベクトル長を長くすることが可能と
なり、これによってフーリエ変換を高速で行なうことが
できるようになる。

【００１８】

【実施例】以下、本発明の実施例を図面に基づいて説明
する。図１は本発明が適用されたベクトル計算機におけ
るフーリエ変換演算に係る部分の構成を示す概略的なブ
ロック図である。図示のように、このベクトル計算機
は、入力データを後述する如くの順序に配列するデータ
配列手段１と、バタフライ演算を行なうバタフライ演算
手段２と、バタフライ演算後のデータを並べ換える並べ
換え手段３を有している。

【００１９】次に、このように構成されたベクトル計算
機を用いてフーリエ変換を行なう手順について図２に示
すフローチャートを参照しながら説明する。多次元デー
タが入力されると、データ配列手段１ではこの多次元デ
ータを１次元的に並べる（ステップＳＴ１）。例えば、
入力データが次の３次元データ

【数８】 ｆ（ｊ₁ ，ｊ₂ ，ｊ₃ ，）｛ｊ₁ ＝０，…，Ｎ₁ −１，ｊ₂ ＝０， …，Ｎ₂ −１，ｊ₃ ＝０，…，Ｎ₃ −１｝ …（１０） の場合には、

【数９】 ｆ（０，０，０），ｆ（１，０，０）， …ｆ（Ｎ₁ −１，０，０），ｆ（０，１，０），ｆ（１，１，０）， …，ｆ（Ｎ₁ −１，１，０）， …，ｆ（Ｎ₁ −１，Ｎ₂ −１，Ｎ₃ −１） …（１１） の順に１次元の配列に格納する。但しＮ₁ ＝２^p1，Ｎ₂
＝２^p2，Ｎ₃ ＝２^p3とする。そして、格納の様子は図３
に示す如くである。

【００２０】次いで、１次元ＦＦＴと同様の処理を第Ｐ
_n 段階まで行なう（ステップＳＴ２）。そして、この処
理の終了時のデータの様子は図４に示す如くである。そ
して、変換後のデータを並べ換える（ステップＳＴ
３）。ここでの処理では図５に示すように、列順に並ん
でいるデータを行順に並べる。その後、１次元ＦＦＴと
同様の処理をＰ_n-1 段階まで行なう（ステップＳＴ
４）。このときのデータの様子は図６に示す通りであ
る。上記の処理をｎ回行い最後は１次元ＦＦＴと同様の
処理をＰ₁ 段階まで繰り返す。

【００２１】また、（１０）式に示した３次元データの
場合には、長さＮ₁ ×Ｎ₂ ×Ｎ₃ のデータに対して１次
元ＦＦＴと同様のバタフライ演算を第Ｐ₃ 段階まで行
う。そして、その結果をｆ′とする。Ｎ₁ ＝Ｎ₂ ＝Ｎ₃
＝４の場合についての変換の様子を図８に示す。図８に
おいて第１段階と第２段階の変換の様子を見てみる。第
２段階変換後のデータ、Ｘ₂ （０，０），Ｘ₂ （０，
１），Ｘ₂ （０，２），Ｘ₂ （０，３）がどのように生
成されているか流れを見てみる。Ｘ₂ （０，０）とＸ₂
（０，２）はＸ₁ （０，０）とＸ₁ （１６，０）から、
Ｘ₂ （０，１）とＸ₂ （０，３）はＸ₁ （０，１）とＸ
₁ （１６，１）から生成されている。そしてＸ₁ （０，
０）とＸ₁ （０，１）はＸ₀ （０，０）とＸ₀ （３２，
０）から、Ｘ₁ （１６，０）とＸ₁ （１６，１）はＸ₀
（１６，０）とＸ₀ （４８，０）からそれぞれ生成され
ている。ここで ｆ（０，０，０）＝Ｘ₀ （０，０） ｆ（０，０，１）＝Ｘ₀ （１６，０） ｆ（０，０，２）＝Ｘ₀ （３２，０） ｆ（０，０，３）＝Ｘ₀ （４８，０） であり、第２段階までの変換のこの部分だけを見るとｊ
₁ ＝ｊ₂ ＝０の場合についてｊ₃ 方向のフーリエ変換を
行なったのと同じである。同様にしてＸ₂ （１，０）、
Ｘ₂ （１，１）、Ｘ₂ （１，２）、Ｘ₂ （１，３）は初
期データｆ（１，０，０）、ｆ（１，０，１）、ｆ
（１，０，２）、ｆ（１，０，３）をｊ₁ ＝１，ｊ₂ ＝
０の場合についてｊ₃ 方向のフーリエ変換を行なったも
のである。従って第２段階までの変換は、全てのｊ₁ と
ｊ₂ についてｊ₃ 方向のフーリエ変換を行なったのと同
じであることがわかる。この時点でのデータの状態を図
９に示す。

【００２２】第２段階変換後のデータは図１０の矢印の
順に配列に格納されているので、これを次に図１１の矢
印の順に並べ換える。すると今度はデータの並びが

【数１０】 ｆ′（０，０，０），ｆ′（０，０，１）， …，ｆ′（０，０，Ｎ₃ −１），ｆ′（１，０，０）， ｆ′（１，０，１），…，ｆ′（１，０，Ｎ₃ −１）， …，ｆ′（Ｎ₁ −１，Ｎ₂ −１，Ｎ₃ −１） …（１２） の順になる。そして前回と同様、第２段階まで１次元Ｆ
ＦＴを行なう（結果をｆ”とする）と今度は全てのｊ₁
とｊ₃ についてｊ₂ 方向のフーリエ変換をしたことと同
じになる。

【００２３】最後に再び並べ換えを行ない、今度は、

【数１１】 ｆ”（０，０，０），ｆ”（０，１，０）， …，ｆ”（０，Ｎ₂ −１，０，）ｆ”（０，０，１）， ｆ”（０，１，１），…，ｆ”（０，Ｎ₂ −１，１）， …，ｆ”（Ｎ₁ −１，Ｎ₂ −１，Ｎ₃ −１） …（１３） の順に配列に格納し同様の処理を行なう。するとｊ₁ 方
向のフーリエ変換をしたことになり、これで３次元ＦＦ
Ｔが終了する。

【００２４】なお、図７に従来の多次元ＦＦＴの手順が
示されており、本実施例によればループ長が長くなり演
算が高速化されることが理解できる。

【００２５】一般にｎ次元ＦＦＴの場合も３次元の場合
と同様で、データを１次元的に並べて１次元ＦＦＴと同
様のバタフライ演算を途中まで行なう。そしてＦＦＴの
途中のデータの並べ換えをｎ回行なえばｎ次元ＦＦＴが
終了する。この時にデータを不連続にアクセスするので
バンクコンフリクトの発生する可能性があるが、ここで
は超平面法と類似のデータアクセス法を用いて、バンク
コンフリクトの発生を防いでいる。

【００２６】以上述べてきたアルゴリズムにしたがって
３次元ＦＦＴのルーチンを作成し、幾つかのテストデー
タについて実行時間を従来の方法と比較した。それを表
１に示す。

【００２７】

【表１】 ここでは今回検討したアルゴリズムで処理したときの時
間を１として示してある。データ数が多くなると両者の
差は小さくなるが、高速化が実現されている。また、図
１２には入力データ数と、従来と本発明との処理時間の
比率との特性曲線が示されており、従来の３０％以下の
処理時間でフーリエ変換が行なえることがわかる。

【００２８】次に、本発明によるベクトル計算機を用い
て、Ｘ線ＣＴスキャナの再構成演算を高速化する例を説
明する。図１３はＸ線ＣＴスキャナの概略的な構成を示
すブロック図であり、被検体にＸ線を照射するＸ線発生
器１１と、Ｘ線管に高電圧を供給する高電圧発生部１２
と、被検体を載置してガントリ内へ侵入させる寝台１３
と、Ｘ線を走査する走査システム１４と、被検体透過後
のＸ線を検出する検出器１５と、前記高電圧発生部１
２、寝台１３、走査システム１４を総括的に制御すると
ともに検出器で収集された信号を再構成してＣＴ画像を
モニタ１７に表示するコンピュータシステム１６と、Ｍ
Ｔ１８、ディスク１９から構成されている。

【００２９】このような構成において、画像を再構成す
る手順を図１６に示すフローチャートを参照しながら説
明する。まず、図１４に示すようにＸ線２０を被検体２
２に向けて照射すると、検出器２１では例えば曲線Ｓ１
に示す如くのＸ線検出データが収集される。そして、こ
の操作を図１５に示すように回転させながら繰り返すこ
とによって、さまざまな角度からのＸ線データを得る
（図１６、ステップＳＴ１１）。

【００３０】その後、このデータをディジタル化し（ス
テップＳＴ１２）、一旦メモリに格納する（ステップＳ
Ｔ１３）。そして、高速フーリエ変換を本発明の方法を
用いて実施し（ステップＳＴ１４）、補間処理後（ステ
ップＳＴ１５）、逆フーリエ変換する（ステップＳＴ１
６）。その後、Ｄ／Ａ変換器にてアナログ化し、ＣＴ画
像を得る（ステップＳＴ１７）。そして、これをモニタ
表示する（ステップＳＴ１８）。

【００３１】こうして、ＣＴ画像の再構成が高速に行な
われるのである。

【００３２】また、図１７は本発明のベクトル計算機を
用いて偏微分方程式を解く際のフローチャートである。
処理の手順としては、まず境界条件を関数化し（ステッ
プＳＴ２１）、高速フーリエ変換して波動空間での境界
条件を求める（ステップＳＴ２２，ＳＴ２３）。

【００３３】また、偏微分方程式を波動空間での代数方
程式に変換し（ステップＳＴ２４）、ステップ２３で求
められた境界条件にて代数方程式を解く（ステップＳＴ
２５）。その後、この結果を逆ＦＦＴして（ステップＳ
Ｔ２６）、偏微分方程式の解を得る。

【００３４】こうして、偏微分方程式を高速で解くこと
ができるのである。

【００３５】また、最近R.Car,M.Parrinello等によって
行われるようになったＤＳＡ（Dyanamic Simulated Ann
ealing）法（Phys.Rev.Lett.55(1985) p2471）などの物
性計算にも本発明を適用することができる。例えばＤＳ
Ａ法では物質の結晶格子が規則的に配列されているとい
う特徴を利用して、物質内の電子状態はｋ−空間（逆格
子ベクトル空間、波動ベクトル空間）に展開して計算し
ている。したがってイオンに加わる力を電子状態から計
算する場合、ｋ−空間に展開された、電子状態を表わす
関数を３次元逆フーリエ変換して実空間上の関数に変換
する必要がある。このようにＤＳＡをはじめとする物性
計算にはｋ−空間上の関数を実空間の関数に直したり、
実空間上の関数をｋ−空間上の関数に直したりする多次
元ＦＦＴ処理を多く用いるため、本発明を適用すること
により高速度に物性の計算を行うことができる。

【００３６】このようにして、本発明のベクトル計算機
を用いれば、画像の再構成や偏微分方程式の解法等ＦＦ
Ｔを用いる種々の分野でその演算速度を速めることがで
きるようになる。

【００３７】

【発明の効果】以上説明したように、本発明のベクトル
計算機では、ベクトル長を長くするために多次元のデー
タを１次元的に並べてループ長を長くし、１次元ＦＦＴ
と同様の処理を１回行なうことにより多次元ＦＦＴを計
算しているので、演算の速度を著しく速くすることがで
きる。これによって、フーリエ変換を用いる各分野でそ
の演算速度を速めることができ極めて有用である。

【図面の簡単な説明】

【図１】本発明が適用されたベクトル計算機の一実施例
に係る概略的な構成を示すブロック図である。

【図２】本実施例のベクトル計算機を用いたＦＦＴ処理
の動作を示すフローチャートである。

【図３】多次元データの配列を示す説明図である。

【図４】バタフライ演算の第Ｐ_n 段階終了時の様子を示
す説明図である。

【図５】データの並べ換えを示す説明図である。

【図６】バタフライ演算の第Ｐ_n-1 段階終了時の様子を
示す説明図である。

【図７】従来の多次元ＦＦＴの手順を示すフローチャー
トである。

【図８】バタフライ演算の流れを示す説明図である。

【図９】第２段階終了時のデータの状態を示す説明図で
ある。

【図１０】第２段階変換後のデータが配列に格納されて
いる順序を示す説明図である。

【図１１】第２段階変換後のデータを１次元配列に格納
する順序を示す説明図である。

【図１２】入力データ数と、従来及び本発明の処理時間
の比率との関係を示す特性図である。

【図１３】Ｘ線ＣＴスキャナの概略的な構成を示すブロ
ック図である。

【図１４】Ｘ線を照射して検出データを収集する例を示
す説明図である。

【図１５】Ｘ線データの収集角度を変更した例を示す説
明図である。

【図１６】Ｘ線ＣＴ画像を再構成する手順を示すフロー
チャートである。

【図１７】偏微分方程式の計算手順を示すフローチャー
トである。

【図１８】Ｎ＝８の場合の１次元ＦＦＴの変換の様子を
示す説明図である。

【図１９】Ｎ＝８の場合の重ね書きによる１次元ＦＦＴ
の流れ図である。

【図２０】ベクトル計算機向けＦＦＴの変換図である。

【図２１】Ｎ＝８の場合のベクトル計算機向け１次元Ｆ
ＦＴの流れ図である。

【符号の説明】

１ データ配列手段 ２ バタフライ演算手段 ３
並べ換え手段 １１ Ｘ線発生器 １５ 検出器 １６ コンピュ
ータシステム

Claims (1)

【特許請求の範囲】
1. 【請求項１】 多次元フーリエ変換を演算するベクルト
   計算機において、 多次元データを１次元的に並べる配列手段と、前記配列
   においてバタフライ演算を行うバタフライ演算手段と、
   バタフライ演算終了後のデータを並べ換える並べ換え手
   段とを有し、前記バタフライ演算及びデータの並べ換え
   を１回以上繰り返してフーリエ変換を行なうことを特徴
   とするベクトル計算機。