fast Fourier transform

デジタル大辞泉

エフ‐エフ‐ティー【FFT】

読み方：えふえふてぃー

《fast Fourier transform》⇒高速フーリエ変換

大車林

FFT

英語 fast fourier transform

高速フーリェ変換。非正弦的な周期関数も正弦波の集合(正弦関数の級数)で表すことができ、これをフーリェ変換といい、振動騒音現象の周波数分析などに用いられる。FFTは、演算の手続きを適当に分解し、級数のもつ周期性や対称性を考慮して計算回数を減らす算法により、変換を高速で行うことである。

参照 周波数分析

※「大車林」の内容は、発行日である2004年時点の情報となっております。

透過電子顕微鏡基本用語集

FFT（エフエフティー）

【英】：fast Fourier transform

フーリエ変換を高速に行う計算方法。コンピュータを使うので連続的な積分の代わりに有限の離散的な和で実行される。高分解能像の解析等に使われる。

関連する用語

• ヤング縞

説明に「FFT」が含まれている用語

• ヤング縞

FFT（エフエフティー）

【英】：fast Fourier transform

フーリエ変換を高速に行う計算方法。コンピュータを使うので連続的な積分の代わりに有限の離散的な和で実行される。高分解能像の解析等に使われる。

関連する用語

• ヤング縞

ウィキペディア

高速フーリエ変換

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/08 00:53 UTC 版)

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

概要

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

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

データ数1２の離散フーリエ変換の模式図。時計を模した図形は1の12乗根の一つを表している。時計の針の向きと色は1の12乗根の偏角を表す。この図で表される行列をデータ列にかけることで離散フーリエ変換が得られる。上図で表されるような列の並べ替えを行うことで、元の行列のパターンはデータ数6の離散フーリエ変換のパターンに分解できる。この繰り返しにより最終的にはデータ数３のフーリエ変換に帰着される。

データ数100の離散フーリエ変換の模式図。色は1の100乗根の偏角を表す。バタフライ演算により元の行列のパターンは最終的にデータ数5の離散フーリエ変換のパターンに分解される。

FFTのバタフライ演算

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

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

この節の加筆が望まれています。

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

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

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

• ドイツ