高速フーリエ変換

デジタル大辞泉

こうそく‐フーリエへんかん〔カウソク‐ヘンクワン〕【高速フーリエ変換】

読み方：こうそくふーりえへんかん

コンピューターなどで、離散化されたフーリエ変換を高速で行うためのアルゴリズム。デジタル信号の周波数解析をはじめ、通信・画像処理などに広く用いられ、計算回数を減らして効率よく計算できる種々のアルゴリズムが考案されている。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) は以下で定義される。

$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)}}.$

• ドイツ