高速フーリエ変換

高速フーリエ変換（こうそくフーリエへんかん、テンプレート:Lang-en-short）は、離散フーリエ変換（テンプレート:Lang-en-short）を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換（テンプレート:Lang-en-short）と呼ぶ。

概要

複素関数テンプレート:Math の離散フーリエ変換である複素関数テンプレート:Math は以下で定義される。

F (t) = \sum_{x = 0}^{N - 1} f (x) \exp (- i \frac{2 π t x}{N}) .

このとき、テンプレート:Math を標本点と言う。

これを直接計算したときの時間計算量は、ランダウの記号を用いて表現するとテンプレート:Math である。

高速フーリエ変換は、この結果を、次数テンプレート:Mvarが2の累乗のときにテンプレート:Math の計算量で得るアルゴリズムである。より一般的には、次数がテンプレート:Math と素因数分解できるとき、テンプレート:Math の計算量となる。次数がテンプレート:Math の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、テンプレート:Math 詰めで次数を調整することもある。

高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量をテンプレート:Math からテンプレート:Math まで落とせる。

現在は、初期の手法^[1] をより高速化したアルゴリズムが使用されている。

逆変換

逆変換は正変換と同じと考えて良いが、指数の符号が逆であり、係数テンプレート:Math が掛かる。

高速フーリエ変換のプログラム中、どの符号が逆転するかを一々分岐させると、分岐の判定に時間がかかり、パフォーマンスが落ちる。一方、正変換のプログラムと、逆変換のプログラムを両方用意しておくことも考えられるが、共通部分が多いため、無駄が多くなる。このため、複素共役を使った次のような方法が考えられる。

離散フーリエ変換を

F (t) = \sum_{x = 0}^{N - 1} f (x) \exp (- i \frac{2 π t x}{N})

で定義したとき、逆変換は

f (x) = \frac{1}{N} \sum_{t = 0}^{N - 1} F (t) \exp (i \frac{2 π t x}{N}) = \frac{1}{N} \overline{\sum_{t = 0}^{N - 1} \overline{F (t)} \exp (- i \frac{2 π t x}{N})}

となる。

このため、テンプレート:Math の離散フーリエ逆変換を求めるには、

(1) 複素共役を取り、テンプレート:Math を求める、

(2) テンプレート:Math の正変換の離散フーリエ変換を高速フーリエ変換で行う、

(3) その結果の複素共役を取り、テンプレート:Mvar で割る

とすれば良く、正変換の高速フーリエ変換のプログラムがあれば、逆変換は容易に作ることができる。

アルゴリズム

クーリー–テューキー型FFTアルゴリズム

テンプレート:Main クーリー–テューキー型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。

分割統治法を使ったアルゴリズムで、テンプレート:Math のサイズの変換を、より小さいサイズであるテンプレート:Math, テンプレート:Math のサイズの変換に分割していくことで高速化を図っている。

最もよく知られたクーリー–テューキー型アルゴリズムは、ステップごとに変換のサイズをサイズテンプレート:Math の2つの変換に分割するので、テンプレート:Math の累乗次数に限定される。しかし、一般的には次数はテンプレート:Math の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。

伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。

クーリー–テューキー型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、テンプレート:Math あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。

原理の簡単な説明

離散フーリエ係数は、[[1の冪根|テンプレート:Mathの原始テンプレート:Mvar 乗根]]の1つテンプレート:Math を使うと、次のように表せる。

F (t) = \sum_{x = 0}^{N - 1} f (x) W_{N}^{t x} .

例えば、テンプレート:Math のとき、 $F (t) = X_{t}$ 、 $f (k) = x_{k}$ とすれば、離散フーリエ係数は行列を用いて表現すると（テンプレート:Math と略記）

[\begin{matrix} X_{0} \\ X_{1} \\ X_{2} \\ X_{3} \end{matrix}] = [\begin{matrix} W^{0} & W^{0} & W^{0} & W^{0} \\ W^{0} & W^{1} & W^{2} & W^{3} \\ W^{0} & W^{2} & W^{4} & W^{6} \\ W^{0} & W^{3} & W^{6} & W^{9} \end{matrix}] [\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \end{matrix}]

となる。入力列テンプレート:Mvar を添字の偶奇で分けて、以下のように変形する。

\begin{matrix} [\begin{matrix} X_{0} \\ X_{1} \\ X_{2} \\ X_{3} \end{matrix}] & = [\begin{matrix} W^{0} & W^{0} & W^{0} & W^{0} \\ W^{0} & W^{2} & W^{1} & W^{3} \\ W^{0} & W^{4} & W^{2} & W^{6} \\ W^{0} & W^{6} & W^{3} & W^{9} \end{matrix}] [\begin{matrix} x_{0} \\ x_{2} \\ x_{1} \\ x_{3} \end{matrix}] \\ = [\begin{matrix} W^{0} & W^{0} & W^{0} W^{0} & W^{0} W^{0} \\ W^{0} & W^{2} & W^{1} W^{0} & W^{1} W^{2} \\ W^{0} & W^{0} & W^{2} W^{0} & W^{2} W^{0} \\ W^{0} & W^{2} & W^{3} W^{0} & W^{3} W^{2} \end{matrix}] [\begin{matrix} x_{0} \\ x_{2} \\ x_{1} \\ x_{3} \end{matrix}] \end{matrix}

( $∵ W^{k + N} = W^{k}$ )

すると、サイズテンプレート:Math のFFTの演算結果を用いて表現でき、サイズの分割ができる。

[\begin{matrix} X_{0} \\ X_{1} \\ X_{2} \\ X_{3} \end{matrix}] = [\begin{matrix} 1 & 0 & W^{0} & 0 \\ 0 & 1 & 0 & W^{1} \\ 1 & 0 & W^{2} & 0 \\ 0 & 1 & 0 & W^{3} \end{matrix}] [\begin{matrix} W_{2}^{0} & W_{2}^{0} & 0 & 0 \\ W_{2}^{0} & W_{2}^{1} & 0 & 0 \\ 0 & 0 & W_{2}^{0} & W_{2}^{0} \\ 0 & 0 & W_{2}^{0} & W_{2}^{1} \end{matrix}] [\begin{matrix} x_{0} \\ x_{2} \\ x_{1} \\ x_{3} \end{matrix}]

また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。

バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。

原理の説明

FFTの原理は、テンプレート:Math として、テンプレート:Mvar 次離散フーリエ変換を、テンプレート:Mvar 次離散フーリエ変換とテンプレート:Mvar 次離散フーリエ変換に分解することである^[2]。

テンプレート:Mvar 次離散フーリエ変換：

F (n) = \sum_{k = 0}^{N - 1} f (k) \exp (- 2 π i \frac{n k}{N})

を、テンプレート:Math について計算することを考える。テンプレート:Mvar, テンプレート:Mvar を次のように書き換える。ただしテンプレート:Math またテンプレート:Math である。

\begin{matrix} n & = s Q + r 0 \leq s \leq P - 1, 0 \leq r \leq Q - 1 \\ k & = q P + p 0 \leq p \leq P - 1, 0 \leq q \leq Q - 1 \end{matrix}

すると

\begin{matrix} F (n) & = F (s Q + r) = \sum_{p = 0}^{P - 1} \sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i \frac{(q P + p) (s Q + r)}{P Q}) \\ = \sum_{p = 0}^{P - 1} \sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i (\frac{r q}{Q} + \frac{s p}{P} + \frac{p r}{P Q})) \\ = \sum_{p = 0}^{P - 1} [\exp (- 2 π i (\frac{s p}{P} + \frac{p r}{P Q})) \sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i \frac{r q}{Q})] \end{matrix}

ここで、

f_{1} (p, r) = \exp (- 2 π i \frac{p r}{P Q}) \sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i \frac{r q}{Q})

と置くと、

F (n) = F (s Q + r) = \sum_{p = 0}^{P - 1} \exp (- 2 π i \frac{s p}{P}) f_{1} (p, r)

となる。即ち、テンプレート:Math の計算は、次の2ステップになる。

ステップ1

テンプレート:Math とテンプレート:Math について

f_{1} (p, r) = \exp (- 2 π i \frac{p r}{P Q}) \sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i \frac{r q}{Q})

を計算する。これは、テンプレート:Mvar次の離散フーリエ変換

\sum_{q = 0}^{Q - 1} f (q P + p) \exp (- 2 π i \frac{r q}{Q})

の実行と、回転因子テンプレート:Math の掛け算を、全てのテンプレート:Mvar, テンプレート:Mvar の組（テンプレート:Math 通り）に対して行うことと見ることができる。

ステップ2

テンプレート:Math とテンプレート:Math について

F (s Q + r) = \sum_{p = 0}^{P - 1} \exp (- 2 π i \frac{s p}{P}) f_{1} (p, r)

を計算する。ここで、右辺はテンプレート:Mvar を固定すれば、テンプレート:Mvar 次の離散フーリエ変換である。

ステップ1、2は、テンプレート:Math 次の離散フーリエ変換を、テンプレート:Mvar 次の離散フーリエ変換と回転因子の掛け算の実行により、テンプレート:Mvar 組 (テンプレート:Math) のテンプレート:Mvar 次離散フーリエ変換に分解したと見ることができる。

テンプレート:Math 次離散フーリエ変換の問題　⇒　テンプレート:Mvar 次離散フーリエ変換の実施　⇒　テンプレート:Math 次離散フーリエ変換の問題に帰着

特に、テンプレート:Mvar がテンプレート:Mathまたはテンプレート:Mathの場合は、テンプレート:Mvar次離散フーリエ変換は非常に簡単な計算になる。

テンプレート:Math の場合は、テンプレート:Math はテンプレート:Math かテンプレート:Math なので、テンプレート:Mvar 次離散フーリエ変換は符号の逆転と足し算だけで計算できる。
テンプレート:Math の場合は、テンプレート:Math はテンプレート:Math, テンプレート:Math, テンプレート:Mvar, テンプレート:Math のいずれかなので、テンプレート:Mvar 次離散フーリエ変換の計算は、符号の逆転、実部虚部の交換と足し算だけで計算できる。

テンプレート:Math かテンプレート:Math の場合のこの部分のテンプレート:Mvar次離散フーリエ変換のことを、バタフライ演算と言う。

また､テンプレート:Math (テンプレート:Math) の場合には、上を繰り返すことができ、テンプレート:Mvar 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げられ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、テンプレート:Mathを求めることができる。
このため、テンプレート:Mathの累乗あるいはテンプレート:Mathの累乗次の離散フーリエ変換は、両方の性質を利用でき、非常に簡単に計算できる。

また、テンプレート:Mathかテンプレート:Mathの場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。テンプレート:Mathの次数を1落とすためにテンプレート:Mvar回の「掛け算」が必要であり、次数をテンプレート:Mvarからテンプレート:Mathに落とすにはそれをテンプレート:Mvar回繰り返す必要があるため、「掛け算」の数はテンプレート:Math となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度はテンプレート:Math になる」ことの根拠になっている。

ビットの反転

上記の説明で、 $N = Q^{k} (P = Q^{k - 1})$ の場合、テンプレート:Math 個のデータ $f (q Q^{k - 1} + p)$ から、テンプレート:Math 個の計算結果

f_{1} (p, r) = \exp (- 2 π i \frac{p r}{Q^{k}}) \sum_{q = 0}^{Q - 1} f (q Q^{k - 1} + p) \exp (- 2 π i \frac{r q}{Q})

を計算する場合に、メモリの節約のため、テンプレート:Math とテンプレート:Math を利用し、計算結果 $f_{1} (p, r)$ を元データ $f (r Q^{k - 1} + p)$ のあった場所に格納することが多い。これが次の次数テンプレート:Math でも繰り返されるため、 $p = q_{2} Q^{k - 2} + p_{2}$ とすると、次の次数の計算結果 $f_{2} (p_{2}, q_{2}, q)$ は $f (q Q^{k - 1} + q_{2} Q^{k - 2} + p_{2})$ のあった場所に格納される。繰り返せば、 $t = q_{1} Q^{k - 1} + q_{2} Q^{k - 2} + \dots + q_{k}$ とすると、計算結果 $f_{k} (p_{k}, q_{k}, q_{k - 1}, \dots, q_{2}, q_{1})$ は $f (q_{1} Q^{k - 1} + q_{2} Q^{k - 2} + \dots + q_{k - 1} Q + p_{k})$ のあった場所に格納される。

一方、

F (s Q + r) = \sum_{p = 0}^{Q^{k - 1} - 1} \exp (- 2 π i \frac{s p}{Q^{k - 1}}) f_{1} (p, r)

を、テンプレート:Mvar を固定しテンプレート:Mvar を変数としたテンプレート:Math 次離散フーリエ変換と見なして、 $s = s_{2} Q + r_{2}$ とすると、

F (s_{2} Q^{2} + r_{2} Q + r) = \sum_{p_{2} = 0}^{Q^{k - 2} - 1} \exp (- 2 π i \frac{s_{2} p_{2}}{Q^{k - 2}}) f_{2} (p_{2}, r_{2}, r)

となる。繰り替えせば、

F (s_{k} Q^{k} + r_{k} Q^{k - 1} + \dots + r_{2} Q + r_{1}) = \sum_{p_{k} = 0}^{Q^{k - k} - 1} \exp (- 2 π i \frac{s_{k} p_{k}}{Q^{k - k}}) f_{k} (p_{k}, r_{k}, r_{k - 1}, \dots, r_{2}, r_{1})

となるが、左辺について

s_{k} Q^{k} + r_{k} Q^{k - 1} + \dots + r_{2} Q + r_{1} < Q^{k}

よりテンプレート:Math, また右辺について

Q^{k - k} - 1 = 0

よりテンプレート:Math。このため、

F (r_{k} Q^{k - 1} + \dots + r_{2} Q + r_{1}) = f_{k} (0, r_{k}, r_{k - 1}, \dots, r_{2}, r_{1}) .

これは $f (r_{1} Q^{k - 1} + r_{2} Q^{k - 2} + \dots + r_{k - 1} Q + r_{k})$ のあった場所に格納されている。

このように、求める解 $F (r_{k} Q^{k - 1} + \dots + r_{2} Q + r_{1})$ が $f (r_{1} Q^{k - 1} + r_{2} Q^{k - 2} + \dots + r_{k - 1} Q + r_{k})$ のあった場所に格納されていることを、ビット反転と言う。これは、テンプレート:Mvar 進法で表示した場合、 $r_{k} Q^{k - 1} + \dots + r_{2} Q + r_{1}$ は $(r_{k} r_{k - 1} \dots r_{2} r_{1})_{Q}$ となるのに対し、 $r_{1} Q^{k - 1} + r_{2} Q^{k - 2} + \dots + r_{k - 1} + r_{k}$ は逆から読んだ $(r_{1} r_{2} \dots r_{k - 1} r_{k})_{Q}$ となるためである。

プログラムの例

以下は、高速フーリエ変換のプログラムをテンプレート:Math の場合にMicrosoft Visual Basicの文法を用いて書いた例である。

Const pi As Double = 3.14159265358979   '円周率
Dim Ndeg As Long '4^deg
Dim Pdeg As Long '4^(deg-i)
Dim CR() As Double   '入力実数部
Dim CI() As Double   '入力虚数部
Dim FR() As Double   '出力実数部
Dim FI() As Double   '出力虚数部

deg=5 '任意に設定。5ならN=4^5=1024で計算
Ndeg=4^deg
ReDim CR(Ndeg - 1) As Double '入力実数部
ReDim CI(Ndeg - 1) As Double '入力虚数部
ReDim FR(Ndeg - 1) As Double '出力実数部
ReDim FI(Ndeg - 1) As Double '出力虚数部
'ここで、変換される関数の実部をCR(0)からCR(Ndeg-1)に、虚部をCI(0)からCI(Ndeg-1)に入力しておくこと

'フーリエ変換
For i = 1 To deg
 Pdeg = 4 ^ (deg - i)
 For j0 = 0 To 4 ^ (i - 1) - 1
  For j1 = 0 To Pdeg - 1
   j = j1 + j0 * Pdeg * 4
   'バタフライ演算(Q=4)
   w1 = CR(j) + CR(j + Pdeg) + CR(j + 2 * Pdeg) + CR(j + 3 * Pdeg)
   w2 = CI(j) + CI(j + Pdeg) + CI(j + 2 * Pdeg) + CI(j + 3 * Pdeg)
   w3 = CR(j) + CI(j + Pdeg) - CR(j + 2 * Pdeg) - CI(j + 3 * Pdeg)
   w4 = CI(j) - CR(j + Pdeg) - CI(j + 2 * Pdeg) + CR(j + 3 * Pdeg)
   w5 = CR(j) - CR(j + Pdeg) + CR(j + 2 * Pdeg) - CR(j + 3 * Pdeg)
   w6 = CI(j) - CI(j + Pdeg) + CI(j + 2 * Pdeg) - CI(j + 3 * Pdeg)
   w7 = CR(j) - CI(j + Pdeg) - CR(j + 2 * Pdeg) + CI(j + 3 * Pdeg)
   w8 = CI(j) + CR(j + Pdeg) - CI(j + 2 * Pdeg) - CR(j + 3 * Pdeg)
   CR(j) = w1
   CI(j) = w2
   CR(j + Pdeg) = w3
   CI(j + Pdeg) = w4
   CR(j + 2 * Pdeg) = w5
   CI(j + 2 * Pdeg) = w6
   CR(j + 3 * Pdeg) = w7
   CI(j + 3 * Pdeg) = w8
   '回転因子
   For k = 0 To 3
    w1 = Cos(2 * pi * j * k / Pdeg / 4)
    w2 = -Sin(2 * pi * j * k / Pdeg / 4)
    w3 = CR(j + k * Pdeg) * w1 - CI(j + k * Pdeg) * w2
    w4 = CR(j + k * Pdeg) * w2 + CI(j + k * Pdeg) * w1
    CR(j + k * Pdeg) = w3
    CI(j + k * Pdeg) = w4
   Next k
  Next j1
 Next j0
Next i
'ビット反転
For i = 0 To Ndeg - 1
 k = i
 k1 = 0
 For j = 1 To deg
  k1 = k1 + (k - Int(k / 4) * 4) * 4 ^ (deg - j)
  k = Int(k / 4)
 Next j
 FR(i) = CR(k1)
 FI(i)=CI(k1)
Next i

この例では、最深部 (For k、Next k の間の部分)の繰り返し回数が Ndeg テンプレート:Math Ndeg となっている。

その他のアルゴリズム

テンプレート:仮リンク (PFA)
テンプレート:仮リンク
レーダーのFFTアルゴリズム
テンプレート:仮リンク (see "Chirp Z-transform")　任意長のデータ列に対する変換が高速に可能である。
テンプレート:仮リンク - テンプレート:仮リンク、テンプレート:仮リンク。
テンプレート:仮リンク

テンプレート:節スタブ

実数および対称的な入力への最適化

多くの応用において、FFTに対する入力データは実数の列(実入力)であり、このとき変換された出力の列は次の対称性を満たす（テンプレート:Math は複素共役）：

F (- t) = \overline{F (t)} .

そこで、多くの効率的なFFTアルゴリズム^[3] は入力データが実数であることを前提に設計されている。

入力データが実数の場合の効率化の手段としては、次のようなものがある。

クーリー-テューキー型アルゴリズムなど典型的なアルゴリズムを利用して、時間とメモリーの両方のコストを低減する。
入力データが偶数の長さのフーリエ係数はその半分の長さの複素フーリエ係数として表現できる（出力の実数/虚数成分は、それぞれ入力の偶関数/奇関数成分に対応する）ことを利用する。

かつては実数の入力データに対するフーリエ係数を求めるのには、実数計算だけで行えるテンプレート:仮リンク (discrete Hartley transform, DHT)を用いると効率的であろうと思われていた。しかしその後に、最適化された離散フーリエ変換 (discrete Fourier transform, DFT) アルゴリズムの方が、離散ハートリー変換アルゴリズムに比べて必要な演算回数が少ないということが判明した。また当初は、実数入力に対してブルーン (Bruun) FFT アルゴリズムは有利であると云われていたが、その後そうではないことが判った。

また、偶奇の対称性を持つ実入力の場合には、DFTはDCTやテンプレート:仮リンクとなるので、演算と記憶に関してほぼ2倍の効率化が得られる。よって、そのような場合にはDFTのアルゴリズムをそのまま適用するよりも、DCTやDSTを適用してフーリエ係数を求める方が効率的である。

応用

スペクトラムアナライザ
OFDM変復調器
OFDM（日本および欧州で地上デジタルテレビジョン放送やADSL等に用いられる変調方式）の実装は、LSI化されたFFTおよびIFFT（逆変換）をそれぞれ復調器および変調器を用いて行われている。
フーリエ変換NMR
核磁気共鳴 (NMR) スペクトルを得るために使用される。
コンピュータ断層撮影 (CT)、核磁気共鳴画像法 (MRI) 等
受像素子を360度回転させながら連続撮影した映像をフーリエ変換する事により、回転面の透過画像を合成する。
多倍精度の乗除算
自動列車停止装置 (例: JR西日本の最新型車両。地上子が発振する周波数の検出に、高速フーリエ変換が用いられている)
FFTアナライザ
周波数の分布を調べるために使用される。以前はハードウェアで信号を処理していたが、近年はCPUの性能が向上した為ソフトウェアで処理される。ノートパソコンとUSBで接続して使用するもの^[4] や、近年はデジタルオシロスコープにFFTの機能を内蔵している物もある。
電波天文学
FX型デジタル分光相関器等を使用して星間分子のスペクトルを解析する^[5]^[6]。

歴史

高速フーリエ変換といえば一般的には1965年、テンプレート:仮リンク (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見した^[1] とされているテンプレート:仮リンクのことをさす^[7]。同時期に高橋秀俊がクーリーとテューキーとは全く独立にフーリエ変換を高速で行うためのアルゴリズムを考案していた^[8]。しかし、1805年頃に既にガウスが同様のアルゴリズムを独自に発見していた。それは彼の没後に刊行された全集に収録されている^[9]（本ページの外部リンク先に同じ文章PDFへのリンクがある）。ガウスの論文以降、地球物理学や気候や潮位解析などの分野などで測定値に対する調和解析は行われていたので、計算上の工夫を必要とする応用分野で受け継がれていたようである（たとえば、Robart L. Nowack: "Development of the FFT and Applications in Geophysics", in Proceedings of the Cornelius Lanczos International Centenary Conference,SIAM, ISBN 978-0898713398 (1994), pp.395-397、の中では Danielson and Lanczos（1942年）などの先行例をあげている。和書でも沼倉三郎：「測定値計算法」、森北出版、（1956年）には，一般の合成数Nに対してではないが、人が計算を行う場合にある程度の大きさまでの合成数Nについてどのように計算すればよいかについての説明をみることができる）。以下の書籍にも、天体観測の軌道の補間のためにガウスが高速フーリエ変換を利用したことが書かれている。

Elena Prestini:"The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004)のSec.3.10 'Gauss and the asteroids: history of the FFT'.

ライブラリ

特定のデバイスに限定していない汎用の実装

FFTPACK
FFTW

ハードウェアベンダーによる、特定のデバイス向けの実装

Accelerate vDSP - Apple のデバイス用^[10]
AOCL-FFTW - AMD CPU 用^[11]
Arm Performance Libraries - Arm64 用^[12]
cuFFT - NVIDIA GPU 用^[13]
Intel oneAPI Math Kernel Library - Intel CPU, GPU 用
MathKeisan - NEC SX 用^[14]
rocFFT - AMD GPU 用^[15]

参考文献

テンプレート:脚注ヘルプテンプレート:Reflist

学習用図書

今後記述を追加の予定

Henri J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms, 2nd Ed., Springer-Verlag, ISBN 978-3-540-11825-1, (1982年).
E.Oran Brigham：「高速フーリエ変換」、科学技術出版社 (1985年).
Rafael G. Campos: The XFT Quadrature in Discrete Fourier Analysis, Birkhäuser, ISBN 978-3-030-13422-8, (2019年). ※離散フーリエ変換の拡張
Douglas F. Elliott and K.Ramamohan Rao: Fast Transforms: Algorithms, Analyses, Applications, Academic Press, ISBN 0-12-237080-5, (1982).
Henri J. Nussbaumer:「高速フーリエ変換のアルゴリズム」、科学技術出版社、ISBN 978-4-87653006-9,（1989年）．
Charles Van Loan: Computational Frameworks for the Fast Fourier Transform, SIAM, ISBN 978-0-89871-285-8, (1992年).
William L. Briggs and Van Emden Henson: The DFT: An Owners' Manual for the Discrete Fourier Transform, SIAM, ISBN 978-0-898713-42-8, (1995年).
Eleanor Chu and Alan George: Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms, CRC Press, ISBN 978-0-84930270-1, (1999).
Audrey Terras: Fourier Analysis on Finite Groups and Applications, London Mathematical Society, Cambridge Univ. Press, ISBN 978-0-521-45718-7 (1999). ※ 群上の調和解析
Gerlind Plonka, Daniel Potts, Gabriele Steidl and Manfred Tasche: Numerical Fourier Analysis, Birkhaeuser, ISBN 978-3-03004305-6, (2019年2月）.
谷萩隆嗣：「高速アルゴリズムと並列信号処理」、コロナ社、ISBN 4-339-01124-X,（2000年7月26日）．
Daisuke Takahashi: Fast Fourier Transform Algorithms for Parallel Computers, Springer, ISBN 978-981139967-1, (2020).
David K. Maslen and Daniel N. Rockmore: The Cooley-Tukey FFT and Group Theory, Notices of the AMS, (Nov, 2001), Vol.48, No.10, pp.1151-1161. ※ 群上の調和解析
David K. Maslen and Daniel N. Rockmore: The Cooley-Tukey FFT and Group Theory, Modern Signal Processing, MSRI Publications, Vol.46,(2003), pp.281-300. ※ 群上の調和解析
Rockmore, D.N. (2004). Recent Progress and Applications in Group FFTs. In: Byrnes, J. (eds) Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry, Vol.136, Springer, ISBN 978-1-4020-1982-1. ※ 群上の調和解析

外部リンク

テンプレート:Normdaten

↑ ^1.0 ^1.1 J. W. Cooley and J. W. Tukey: Math. of Comput. 19 (1965) 297.
↑ テンプレート:Cite journal
↑ 例えば、（テンプレート:Cite journal）
↑ FFT spectrum analyzer
↑ 惑星大気の観測「SPART」
↑ 空間FFT電波干渉計による電波天体の高速撮像
↑ IEEE Archives: History of FFT with Cooley and Tukey.
↑ テンプレート:Cite journal
↑ Carl Friedrich Gauss, "Nachlass: Theoria interpolationis methodo nova tractata", Werke band 3, 265–327 (Konigliche Gesellschaft der Wissenschaften, Gottingen, 1866). See also　M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine 1 (4), 14–21 (1984).
↑ テンプレート:Cite web
↑ テンプレート:Cite web
↑ テンプレート:Cite web
↑ テンプレート:Cite web
↑ テンプレート:Cite web
↑ テンプレート:Cite web

[Math-1] 1.0 ^1.1 J. W. Cooley and J. W. Tukey: Math. of Comput. 19 (1965) 297.

[2] テンプレート:Cite journal

[3] 例えば、（テンプレート:Cite journal）

[4] FFT spectrum analyzer

[5] 惑星大気の観測「SPART」

[6] 空間FFT電波干渉計による電波天体の高速撮像

[7] IEEE Archives: History of FFT with Cooley and Tukey.

[8] テンプレート:Cite journal

[9] Carl Friedrich Gauss, "Nachlass: Theoria interpolationis methodo nova tractata", Werke band 3, 265–327 (Konigliche Gesellschaft der Wissenschaften, Gottingen, 1866). See also　M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine 1 (4), 14–21 (1984).

[10] テンプレート:Cite web

[11] テンプレート:Cite web

[12] テンプレート:Cite web

[13] テンプレート:Cite web

[14] テンプレート:Cite web

[15] テンプレート:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

高速フーリエ変換

目次

概要

逆変換