高速フーリエ変換

高速フーリエ変換（こうそくフーリエへんかん、英: fast Fourier transform, FFT）は、離散フーリエ変換（英: discrete Fourier transform, DFT）を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換（英: inverse fast Fourier transform, IFFT）と呼ぶ。

概要

複素関数 $f (x)$ の離散フーリエ変換である複素関数 $F (t)$ は以下で定義される。

F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right).

このとき、 ${x = 0, 1, 2, ..., N - 1}$ を標本点と言う。

これを直接計算したときの時間計算量は、ランダウの記号を用いて表現すると $O (N 2)$ である。

高速フーリエ変換は、この結果を、次数 $N$ が2の累乗のときに $O (N log N)$ の計算量で得るアルゴリズムである。より一般的には、次数が $N = \prod n i$ と素因数分解できるとき、 $O (N \sum n i)$ の計算量となる。次数が $2$ の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、 $0$ 詰めで次数を調整することもある。

高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量を $O (N 2)$ から $O (N log N)$ まで落とせる。

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

逆変換

逆変換は正変換と同じと考えて良いが、指数の符号が逆であり、係数 $1/ N$ が掛かる。

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

離散フーリエ変換を

F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)

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

f(x)={\frac {1}{N}}\sum _{t=0}^{N-1}F(t)\exp \left(i{\frac {2\pi {tx}}{N}}\right)={\frac {1}{N}}{\overline {\sum _{t=0}^{N-1}{\overline {F(t)}}\exp \left(-i{\frac {2\pi tx}{N}}\right)}}

となる。

このため、 $F (t)$ の離散フーリエ逆変換を求めるには、

(1) 複素共役を取り、

F (t)

を求める、

(2)

F (t)

の正変換の離散フーリエ変換を高速フーリエ変換で行う、

(3) その結果の複素共役を取り、

N

で割る

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

アルゴリズム

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

→詳細は「クーリー–テューキー型FFTアルゴリズム（英語版）」を参照

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

分割統治法を使ったアルゴリズムで、 $N = N 1 N 2$ のサイズの変換を、より小さいサイズである $N 1$ , $N 2$ のサイズの変換に分割していくことで高速化を図っている。

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

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

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

原理の簡単な説明

離散フーリエ係数は、 $1$ の原始 $N$ 乗根の1つ $W N = e -2 πi / N$ を使うと、次のように表せる。

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

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

{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}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{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{bmatrix}}

となる。入力列 $x k$ を添字の偶奇で分けて、以下のように変形する。

{\begin{aligned}{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}&={\begin{bmatrix}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{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\\&={\begin{bmatrix}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{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\end{aligned}}

( $\because W^{k+N}=W^{k}$ )

すると、サイズ $2$ のFFTの演算結果を用いて表現でき、サイズの分割ができる。

{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}1&0&W^{0}&0\\0&1&0&W^{1}\\1&0&W^{2}&0\\0&1&0&W^{3}\end{bmatrix}}\,{\begin{bmatrix}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{bmatrix}}\,{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}

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

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

原理の説明

FFTの原理は、 $N = PQ$ として、 $N$ 次離散フーリエ変換を、 $P$ 次離散フーリエ変換と $Q$ 次離散フーリエ変換に分解することである^[2]。

$N$ 次離散フーリエ変換：

F(n)=\sum _{k=0}^{N-1}f(k)\exp \left(-2\pi i{\frac {nk}{N}}\right)

を、 $n = 0, 1, ..., N - 1$ について計算することを考える。 $n$ , $k$ を次のように書き換える。ただし $0 \leq n \leq N - 1$ また $0 \leq k \leq N - 1$ である。

{\begin{aligned}n&=sQ+r\qquad 0\leq s\leq P-1,\,0\leq r\leq Q-1\\k&=qP+p\qquad 0\leq p\leq P-1,\;0\leq q\leq Q-1\end{aligned}}

すると

{\begin{aligned}F(n)&=F(sQ+r)=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {(qP+p)(sQ+r)}{PQ}}\right)\\&=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i\left({\frac {rq}{Q}}+{\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\\&=\sum _{p=0}^{P-1}\left[\exp \left(-2\pi i\left({\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)\right]\end{aligned}}

ここで、

f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)

と置くと、

F(n)=F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)

となる。即ち、 $F (n) = F (sQ + r)$ の計算は、次の2ステップになる。

ステップ1

p = 0, 1, ..., P - 1

と

r = 0, 1, ..., Q - 1

について

f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)

を計算する。これは、

Q

次の離散フーリエ変換

\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)

の実行と、回転因子

exp(-2 πipr / PQ)

の掛け算を、全ての

p

,

r

の組（

PQ = N

通り）に対して行うことと見ることができる。

ステップ2

s = 0, 1, ..., P - 1

と

r = 0, 1, ..., Q - 1

について

F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)

を計算する。ここで、右辺は

r

を固定すれば、

P

次の離散フーリエ変換である。

ステップ1、2は、 $N = PQ$ 次の離散フーリエ変換を、 $Q$ 次の離散フーリエ変換と回転因子の掛け算の実行により、 $Q$ 組 ( $r = 0, 1, ..., Q - 1$ ) の $P$ 次離散フーリエ変換に分解したと見ることができる。

N

次離散フーリエ変換の問題　⇒　

Q

次離散フーリエ変換の実施　⇒　

N / Q

次離散フーリエ変換の問題に帰着

特に、 $Q$ が $2$ または $4$ の場合は、 $Q$ 次離散フーリエ変換は非常に簡単な計算になる。

$Q = 2$ の場合は、 $exp(-2 πirq / Q)$ は $1$ か $-1$ なので、 $Q$ 次離散フーリエ変換は符号の逆転と足し算だけで計算できる。
$Q = 4$ の場合は、 $exp(-2 πirq / Q)$ は $1$ , $-1$ , $i$ , $- i$ のいずれかなので、 $Q$ 次離散フーリエ変換の計算は、符号の逆転、実部虚部の交換と足し算だけで計算できる。

$Q = 2$ か $Q = 4$ の場合のこの部分の $Q$ 次離散フーリエ変換のことを、バタフライ演算と言う。

また､ $N = Q k$ ( $P = Q k - 1$ ) の場合には、上を繰り返すことができ、 $Q$ 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げられ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、 $F (t)$ を求めることができる。
このため、 $2$ の累乗あるいは $4$ の累乗次の離散フーリエ変換は、両方の性質を利用でき、非常に簡単に計算できる。

また、 $Q = 2$ か $Q = 4$ の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。 $N = Q k$ の次数を1落とすために $N$ 回の「掛け算」が必要であり、次数を $k$ から $0$ に落とすにはそれを $k$ 回繰り返す必要があるため、「掛け算」の数は $Nk = N log Q N$ となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は $O (N log N)$ になる」ことの根拠になっている。

ビットの反転

上記の説明で、 $N=Q^{k}(P=Q^{k-1})$ の場合、 $N = Q k$ 個のデータ $f(qQ^{k-1}+p)$ から、 $N = Q k$ 個の計算結果

f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{Q^{k}}}\right)\sum _{q=0}^{Q-1}f(qQ^{k-1}+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)

を計算する場合に、メモリの節約のため、 $0 \leq q \leq Q - 1$ と $0 \leq r \leq Q - 1$ を利用し、計算結果 $f_{1}(p,r)$ を元データ $f(rQ^{k-1}+p)$ のあった場所に格納することが多い。これが次の次数 $Q k - 1$ でも繰り返されるため、 $p=q_{2}Q^{k-2}+p_{2}$ とすると、次の次数の計算結果 $f_{2}(p_{2},q_{2},q)$ は $f(qQ^{k-1}+q_{2}Q^{k-2}+p_{2})$ のあった場所に格納される。繰り返せば、 $t=q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +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}+\cdots +q_{k-1}Q+p_{k})$ のあった場所に格納される。

一方、

F(sQ+r)=\sum _{p=0}^{Q^{k-1}-1}\exp \left(-2\pi i{\frac {sp}{Q^{k-1}}}\right)f_{1}(p,r)

を、 $r$ を固定し $s$ を変数とした $Q k - 1$ 次離散フーリエ変換と見なして、 $s=s_{2}Q+r_{2}$ とすると、

F(s_{2}Q^{2}+r_{2}Q+r)=\sum _{p_{2}=0}^{Q^{k-2}-1}\exp \left(-2\pi i{\frac {s_{2}p_{2}}{Q^{k-2}}}\right)f_{2}(p_{2},r_{2},r)

となる。繰り替えせば、

F(s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=\sum _{p_{k}=0}^{Q^{k-k}-1}\exp \left(-2\pi i{\frac {s_{k}p_{k}}{Q^{k-k}}}\right)f_{k}(p_{k},r_{k},r_{k-1},\dots ,r_{2},r_{1})

となるが、左辺について

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

より $s k = 0$ , また右辺について

Q^{k-k}-1=0

より $p k = 0$ 。このため、

F(r_{k}Q^{k-1}+\cdots +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}+\cdots +r_{k-1}Q+r_{k})$ のあった場所に格納されている。

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

プログラムの例

以下は、高速フーリエ変換のプログラムを $Q = 4$ の場合に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 $log 4$ Ndeg となっている。

その他のアルゴリズム

Prime Factor Algorithm（英語版） (PFA)
Bruun's FFT algorithm（英語版）
レーダーのFFTアルゴリズム
Bluestein's FFT algorithm（英語版） (see "Chirp Z-transform")　任意長のデータ列に対する変換が高速に可能である。
オドリツコ・ショーンハーゲ法（英語版） - アンドリュー・オドリツコ（英語版）、アーノルド・ショーンハーゲ（英語版）。
Fast Walsh–Hadamard transform（英語版）

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

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

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

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

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

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

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

また、偶奇の対称性を持つ実入力の場合には、DFTはDCTやDST（英語版）となるので、演算と記憶に関してほぼ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] とされているクーリー–テューキー型FFTアルゴリズム（英語版）を呼ぶ^[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]

参考文献

[脚注の使い方]

^ ^a ^b J. W. Cooley and J. W. Tukey: Math. of Comput. 19 (1965) 297.
^ 高橋秀俊「高速フーリエ変換（FFT）について」『情報処理』第14巻第8号、情報処理学会、1973年8月、CRID 1050564287833399424。
^ 例えば、（Sorensen, H V and Jones, D and Heideman, Michael and Burrus, C (1987). “Real-valued fast Fourier transform algorithms”. IEEE Transactions on acoustics, speech, and signal processing (IEEE) 35 (6): 849-863. doi:10.1109/TASSP.1987.1165220. ）
^ FFT spectrum analyzer
^ 惑星大気の観測「SPART」
^ 空間FFT電波干渉計による電波天体の高速撮像
^ IEEE Archives: History of FFT with Cooley and Tukey.
^ 『東京大学大型計算機センターニュース』第2巻Supplement 2、1970年。
^ 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).
^ “vDSP - Accelerate - Apple Developer Documentation”. May 25, 2024閲覧。
^ “AOCL-FFTW (Fastest Fourier Transform in the West)”. AMD. 25 May 2024閲覧。
^ “Arm Performance Libraries”. May 25, 2024閲覧。
^ “cuFFT”. NVIDIA Developer. 25 May 2024閲覧。
^ “NEC Corporation of America”. mathkeisan.com. 25 May 2024閲覧。
^ AMD. “rocFFT documentation — rocFFT Documentation”. rocm.docs.amd.com. 25 May 2024閲覧。

学習用図書

今後記述を追加の予定

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-4876530069 （1989年）．
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-0849302701 (1999).
Gerlind Plonka, Daniel Potts, Gabriele Steidl and Manfred Tasche: Numerical Fourier Analysis, Birkhaeuser, ISBN 978-3030043056 (2019年2月）.
谷萩隆嗣：「高速アルゴリズムと並列信号処理」、コロナ社、ISBN 4-339-01124-X（2000年7月26日）．
Daisuke Takahashi: Fast Fourier Transform Algorithms for Parallel Computers, Springer, ISBN 978-9811399671 (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. ※ 群上の調和解析

外部リンク

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

[2] 高橋秀俊「高速フーリエ変換（FFT）について」『情報処理』第14巻第8号、情報処理学会、1973年8月、CRID 1050564287833399424。

[3] 例えば、（Sorensen, H V and Jones, D and Heideman, Michael and Burrus, C (1987). “Real-valued fast Fourier transform algorithms”. IEEE Transactions on acoustics, speech, and signal processing (IEEE) 35 (6): 849-863. doi:10.1109/TASSP.1987.1165220. ）

[4] FFT spectrum analyzer

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

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

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

[8] 『東京大学大型計算機センターニュース』第2巻Supplement 2、1970年。

[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] “vDSP - Accelerate - Apple Developer Documentation”. May 25, 2024閲覧。

[11] “AOCL-FFTW (Fastest Fourier Transform in the West)”. AMD. 25 May 2024閲覧。

[12] “Arm Performance Libraries”. May 25, 2024閲覧。

[13] “cuFFT”. NVIDIA Developer. 25 May 2024閲覧。

[14] “NEC Corporation of America”. mathkeisan.com. 25 May 2024閲覧。

[15] AMD. “rocFFT documentation — rocFFT Documentation”. rocm.docs.amd.com. 25 May 2024閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

概要

逆変換