波形測定器に戻る

FFTアナライザ

0件の登録があります。

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

概要

複素関数 f(x) の離散フーリエ変換である複素関数 F(t) は以下で定義される。
F ( t ) = ∑ x = 0 N − 1 f ( x ) exp ⁡ ( − i 2 π t x N ) . {\displaystyle 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(N2) である。高速フーリエ変換は、この結果を、次数Nが2の累乗のときに O(N log N) の計算量で得るアルゴリズムである。より一般的には、次数が N = ∏ ni と素因数分解できるとき、O(N∑ni) の計算量となる。次数が 2 の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、0 詰めで次数を調整することもある。高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量を O(N2) から O(N log N) まで落とせる。現在は、初期の手法 をより高速化したアルゴリズムが使用されている。

逆変換

逆変換は正変換と同じと考えて良いが、指数の符号が逆であり、係数 1/N が掛かる。高速フーリエ変換のプログラム中、どの符号が逆転するかを一々分岐させると、分岐の判定に時間がかかり、パフォーマンスが落ちる。一方、正変換のプログラムと、逆変換のプログラムを両方用意しておくことも考えられるが、共通部分が多いため、無駄が多くなる。このため、複素共役を使った次のような方法が考えられる。離散フーリエ変換を
F ( t ) = ∑ x = 0 N − 1 f ( x ) exp ⁡ ( − i 2 π t x N ) {\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)}
で定義したとき、逆変換は
f ( x ) = 1 N ∑ t = 0 N − 1 F ( t ) exp ⁡ ( i 2 π t x N ) = 1 N ∑ t = 0 N − 1 F ( t ) ¯ exp ⁡ ( − i 2 π t x N ) ¯ {\displaystyle 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) アルゴリズムである。分割統治法を使ったアルゴリズムで、N = N1 N2 のサイズの変換を、より小さいサイズである N1, N2 のサイズの変換に分割していくことで高速化を図っている。最もよく知られたクーリー–テューキー型アルゴリズムは、ステップごとに変換のサイズをサイズ N/2 の2つの変換に分割するので、2 の累乗次数に限定される。しかし、一般的には次数は 2 の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。クーリー–テューキー型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、N ≤ 8 あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。

原理の簡単な説明

離散フーリエ係数は、1の原始 N 乗根の1つ WN = e−2πi/N を使うと、次のように表せる。
F ( t ) = ∑ x = 0 N − 1 f ( x ) W N t x . {\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)W_{N}^{tx}.}
例えば、N = 4 のとき、 F ( t ) = X t {\displaystyle F(t)=X_{t}} 、 f ( k ) = x k {\displaystyle f(k)=x_{k}} とすれば、離散フーリエ係数は行列を用いて表現すると（W = W4 と略記）
[ X 0 X 1 X 2 X 3 ] = [ 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 ] [ x 0 x 1 x 2 x 3 ] {\displaystyle {\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}}}
となる。入力列 xk を添字の偶奇で分けて、以下のように変形する。
[ X 0 X 1 X 2 X 3 ] = [ 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 ] [ x 0 x 2 x 1 x 3 ] = [ 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 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\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}}}
( ∵ W k + N = W k {\displaystyle \because W^{k+N}=W^{k}} )すると、サイズ 2 のFFTの演算結果を用いて表現でき、サイズの分割ができる。
[ X 0 X 1 X 2 X 3 ] = [ 1 0 W 0 0 0 1 0 W 1 1 0 W 2 0 0 1 0 W 3 ] [ 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 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\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 次離散フーリエ変換に分解することである。N 次離散フーリエ変換：
F ( n ) = ∑ k = 0 N − 1 f ( k ) exp ⁡ ( − 2 π i n k N ) {\displaystyle 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 ≤ n ≤ N − 1 また 0 ≤ k ≤ N − 1 である。
n = s Q + r 0 ≤ s ≤ P − 1 , 0 ≤ r ≤ Q − 1 k = q P + p 0 ≤ p ≤ P − 1 , 0 ≤ q ≤ Q − 1 {\displaystyle {\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}}}
すると
F ( n ) = F ( s Q + r ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i ( q P + p ) ( s Q + r ) P Q ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i ( r q Q + s p P + p r P Q ) ) = ∑ p = 0 P − 1 [ exp ⁡ ( − 2 π i ( s p P + p r P Q ) ) ∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i r q Q ) ] {\displaystyle {\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 ⁡ ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i r q Q ) {\displaystyle 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 ( s Q + r ) = ∑ p = 0 P − 1 exp ⁡ ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle 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 ⁡ ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i r q Q ) {\displaystyle 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次の離散フーリエ変換
∑ q = 0 Q − 1 f ( q P + p ) exp ⁡ ( − 2 π i r q Q ) {\displaystyle \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 ( s Q + r ) = ∑ p = 0 P − 1 exp ⁡ ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle 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 = Qk (P = Qk − 1) の場合には、上を繰り返すことができ、Q 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げられ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、F(t)を求めることができる。
このため、2の累乗あるいは4の累乗次の離散フーリエ変換は、両方の性質を利用でき、非常に簡単に計算できる。また、Q = 2かQ = 4の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。N = Qkの次数を1落とすためにN回の「掛け算」が必要であり、次数をkから0に落とすにはそれをk回繰り返す必要があるため、「掛け算」の数は Nk = N logQ N となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は O(N log N) になる」ことの根拠になっている。

ビットの反転

上記の説明で、 N = Q k ( P = Q k − 1 ) {\displaystyle N=Q^{k}(P=Q^{k-1})} の場合、N = Qk 個のデータ f ( q Q k − 1 + p ) {\displaystyle f(qQ^{k-1}+p)} から、N = Qk 個の計算結果
f 1 ( p , r ) = exp ⁡ ( − 2 π i p r Q k ) ∑ q = 0 Q − 1 f ( q Q k − 1 + p ) exp ⁡ ( − 2 π i r q Q ) {\displaystyle 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 ≤ q ≤ Q − 1 と 0 ≤ r ≤ Q − 1 を利用し、計算結果 f 1 ( p , r ) {\displaystyle f_{1}(p,r)} を元データ f ( r Q k − 1 + p ) {\displaystyle f(rQ^{k-1}+p)} のあった場所に格納することが多い。これが次の次数 Qk − 1 でも繰り返されるため、 p = q 2 Q k − 2 + p 2 {\displaystyle p=q_{2}Q^{k-2}+p_{2}} とすると、次の次数の計算結果 f 2 ( p 2 , q 2 , q ) {\displaystyle f_{2}(p_{2},q_{2},q)} は f ( q Q k − 1 + q 2 Q k − 2 + p 2 ) {\displaystyle f(qQ^{k-1}+q_{2}Q^{k-2}+p_{2})} のあった場所に格納される。繰り返せば、 t = q 1 Q k − 1 + q 2 Q k − 2 + ⋯ + q k {\displaystyle t=q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k}} とすると、計算結果 f k ( p k , q k , q k − 1 , … , q 2 , q 1 ) {\displaystyle 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 + ⋯ + q k − 1 Q + p k ) {\displaystyle f(q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k-1}Q+p_{k})} のあった場所に格納される。一方、
F ( s Q + r ) = ∑ p = 0 Q k − 1 − 1 exp ⁡ ( − 2 π i s p Q k − 1 ) f 1 ( p , r ) {\displaystyle 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 を変数とした Qk − 1 次離散フーリエ変換と見なして、 s = s 2 Q + r 2 {\displaystyle s=s_{2}Q+r_{2}} とすると、
F ( s 2 Q 2 + r 2 Q + r ) = ∑ p 2 = 0 Q k − 2 − 1 exp ⁡ ( − 2 π i s 2 p 2 Q k − 2 ) f 2 ( p 2 , r 2 , r ) {\displaystyle 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 + ⋯ + r 2 Q + r 1 ) = ∑ p k = 0 Q k − k − 1 exp ⁡ ( − 2 π i s k p k Q k − k ) f k ( p k , r k , r k − 1 , … , r 2 , r 1 ) {\displaystyle 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 + ⋯ + r 2 Q + r 1 < Q k {\displaystyle s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}<Q^{k}}
より sk = 0, また右辺について
Q k − k − 1 = 0 {\displaystyle Q^{k-k}-1=0}
より pk = 0。このため、
F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) = f k ( 0 , r k , r k − 1 , … , r 2 , r 1 ) . {\displaystyle 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 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されている。このように、求める解 F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) {\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})} が f ( r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されていることを、ビット反転と言う。これは、Q 進法で表示した場合、 r k Q k − 1 + ⋯ + r 2 Q + r 1 {\displaystyle r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}} は ( r k r k − 1 … r 2 r 1 ) Q {\displaystyle (r_{k}r_{k-1}\dots r_{2}r_{1})_{Q}} となるのに対し、 r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 + r k {\displaystyle r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}+r_{k}} は逆から読んだ ( r 1 r 2 … r k − 1 r k ) Q {\displaystyle (r_{1}r_{2}\dots r_{k-1}r_{k})_{Q}} となるためである。

プログラムの例

以下は、高速フーリエ変換のプログラムを Q = 4 の場合にMicrosoft Visual Basicの文法を用いて書いた例である。この例では、最深部 (For k、Next k の間の部分)の繰り返し回数が Ndeg log4 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 ) = F ( t ) ¯ . {\displaystyle F(-t)={\overline {F(t)}}.}
そこで、多くの効率的なFFTアルゴリズム は入力データが実数であることを前提に設計されている。入力データが実数の場合の効率化の手段としては、次のようなものがある。クーリー-テューキー型アルゴリズムなど典型的なアルゴリズムを利用して、時間とメモリーの両方のコストを低減する。入力データが偶数の長さのフーリエ係数はその半分の長さの複素フーリエ係数として表現できる（出力の実数/虚数成分は、それぞれ入力の偶関数/奇関数成分に対応する）ことを利用する。かつては実数の入力データに対するフーリエ係数を求めるのには、実数計算だけで行える離散ハートリー変換 (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で接続して使用するもの や、近年はデジタルオシロスコープにFFTの機能を内蔵している物もある。
電波天文学
FX型デジタル分光相関器等を使用して星間分子のスペクトルを解析する。

歴史

高速フーリエ変換といえば一般的には1965年、ジェイムズ・クーリー (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見した とされているクーリー–テューキー型FFTアルゴリズムを呼ぶ。同時期に高橋秀俊がクーリーとテューキーとは全く独立にフーリエ変換を高速で行うためのアルゴリズムを考案していた。しかし、1805年頃に既にガウスが同様のアルゴリズムを独自に発見していた（本ページの外部リンク先に同じ文章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'.

ライブラリ

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

FFTPACKFFTW

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

Accelerate vDSP - Apple のデバイス用AOCL-FFTW - AMD CPU 用Arm Performance Libraries - Arm64 用cuFFT - NVIDIA GPU 用Intel oneAPI Math Kernel Library - Intel CPU, GPU 用MathKeisan - NEC SX 用rocFFT - AMD GPU 用

参考文献

関連記事

フーリエ変換離散フーリエ変換 (DFT)Butterfly diagramOverlap–add method / Overlap–save methodSpectral musicスペクトラムアナライザ時系列ショーンハーゲ・ストラッセン法（乗算アルゴリズム）Sparse Fourier transform ※ （高速）スパース・フーリエ変換(SFT)

学習用図書

今後記述を追加の予定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. ※ 群上の調和解析

外部リンク

fast Fourier transform (Mathematics) - ブリタニカ百科事典世界大百科事典 第２版『高速フーリエ変換』 - コトバンクMichael T. Heideman, Don H. Johnson, and C. Sidney Burrus: "Gauss and the History of the Fast Fourier Transform", IEEE ASSP Magazine, Vol.1,pp.14-21(1984). (PDF File)Alex H. Barnett, Jeremy F. Magland, Ludvig af Klinteberg:A parallel non-uniform fast Fourier transform library based on an "exponential of semicircle" kernel高橋大介：「高速フーリエ変換におけるキャッシュ最適化」、RISTニュース、No.57,pp.24-31 (2014).「2の累乗専用のFFTを用いて任意長FFTを実装：チャープZ変換」(Qiita記事，2018年11月13日）WEB SITE "FFT Report"山本有作:「高速フーリエ変換とその並列化 (I)」(2003年6月6日)

もっと見る 閉じる

高速フーリエ変換 （http://ja.wikipedia.org/）より引用

誠に申し訳ございません。


該当分類に登録されている製品が見つかりませんでした。