高速フーリエ変換

ウィキペディア

高速フーリエ変換

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

高速フーリエ変換（こうそくフーリエへんかん、英: 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).$

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

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

FFTのバタフライ演算

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

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

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

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

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

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

• ドイツ