FFT｜離散信号を高速周波数スペクトル化

FFT

FFTは、離散フーリエ変換（DFT）の計算量を劇的に削減するアルゴリズム群の総称である。ナイーブなDFTがO(N2)であるのに対し、FFTは典型的にO(N log N)で計算できるため、信号処理、画像処理、通信、制御、振動解析など広範な分野で事実上の標準となっている。FFTは特定の一手法ではなく、データ長や構造に応じた多様な分割統治法のファミリーであり、実装ではバタフライ演算、ツイドル因子、インデックスのビット反転並べ替えなどの要素が組み合わさる。

Table Of Contents

定義と背景

FFTはDFTの計算を再帰的な分割と再結合で効率化する方法である。複素指数関数の周期性と対称性を利用し、部分問題へと分解して再利用することで、冗長な乗算・加算を避ける。これにより、リアルタイム処理や大規模データの周波数解析が現実的となる。

DFTと計算量の要点

DFTは時系列x[n]（n=0..N−1）を周波数領域X[k]へ写像する離散変換である。ナイーブ実装は各kに対しN項を総なめするためO(N2)となるが、FFTはNを部分系列へ分割し、再帰合成してO(N log N)を実現する。Nが2の冪であると特に効率がよい。

代表的アルゴリズム

  • Cooley–Tukey法：最も広く使われる分割統治型FFT。基数2（radix-2）、基数4、混合基数などの派生がある。

  • 分割方向：時間分割（DIT）と周波数分割（DIF）があり、バタフライの順序や並べ替えの位置が異なる。

  • Bluestein（Chirp-Z）：任意長Nに対し畳み込みへ帰着させてFFTを適用する手法で、素数長に有効。

  • Rader：素数長DFTを巡回畳み込みに変換する。

実装上の論点

  • 窓関数：有限長切り出しによる漏れを抑えるため、HannやHamming等を適用してからFFTを取る。

  • ゼロ詰め：周波数軸の補間表示を滑らかにし、ピーク位置の推定を容易にするが、分解能自体を上げるわけではない。

  • 正規化：実装によりスケーリングの位置が異なるため、逆変換（IFFT）と組で振幅が整合するよう係数を明示する。

  • 実数FFT：実信号の共役対称性を利用して演算量とメモリを半減するテクニックがある。

スペクトル解釈の基礎

  • 複素スペクトル：X[k]の大きさが振幅、偏角が位相を与える。位相は遅延や開始位相に敏感で、システム同定や干渉解析で重要となる。

  • 片側スペクトル：実信号では正負周波数が対称となるため、エネルギ保存を踏まえた倍率で片側表示を行う。

  • 周波数ビン：サンプリング周波数fs、長さNのFFTではビン間隔Δf＝fs/Nである。

周波数分解能と時間分解能

分解能Δfは観測窓長T（＝N/fs）に反比例し、より細かい周波数分解には長い窓が必要となる。一方で時間変動の追従性は低下する。短時間フーリエ変換（STFT）は固定窓で時間と周波数の局在性を折衷する枠組みであり、非定常信号の分析に用いられる。

漏れと窓関数の実務

矩形窓は主ローブが狭いがサイドローブが高く、弱い成分が強い成分の近傍で埋もれやすい。Hann等はサイドローブを低減する代わりに主ローブが広がる。測定目的（ピークの分離、振幅精度、雑音耐性）に応じて窓を選択し、FFT結果の解釈に反映させるべきである。

畳み込み定理と高速畳み込み

畳み込み定理により、時間領域の畳み込みは周波数領域の積に対応する。長いFIRフィルタや画像の相関計算は、ゼロ詰めとFFT・IFFTを用いた高速畳み込みで計算量を削減できる。オーバーラップセーブ／アド法は長系列処理の定番である。

数値安定性と誤差

  • 丸め誤差：バタフライでの累積に注意し、倍精度やスケーリングでS/Nを確保する。

  • ツイドル因子表：前計算と再利用で高速化するが、テーブルの精度とキャッシュ局在性のバランスが重要である。

  • ビット反転並べ替え：メモリアクセスの局所性が性能を左右するため、配列レイアウトを最適化する。

実務のチェックリスト

  1. サンプリング条件：fsとアンチエイリアスの仕様を明確化し、Nyquistを超える成分の折返しを防ぐ。

  2. 前処理：直流オフセット除去、窓関数の選択、必要に応じたデトレンドを施す。

  3. スケーリング：直交規約（1/N、1/√Nなど）を決め、振幅・エネルギの解釈を一貫させる。

  4. 可視化：片側表示、対数軸、平均化（Welch法等）で見やすくし、ピークとノイズ床を分離する。

応用例

  • 機械振動：共振周波数の抽出、アンバランス診断、軸受故障の高調波解析にFFTが有効である。

  • 電力品質：高調波歪み、フリッカ、インバータスイッチング成分の評価に活用する。

  • 通信・レーダ：スペクトル占有、同期、OFDM符号化の基盤としてFFTが機能する。

  • 画像処理：周波数フィルタリング、周期ノイズ除去、相関法によるサブピクセル位置合わせ。

STFT・ウェーブレットとの位置づけ

非定常解析ではSTFTやウェーブレット変換が時間局在性で優れるが、固定窓のSTFTも本質はFFTの反復適用であり、実装効率の観点からFFTは依然中核にある。周波数解像度と時間解像度の折衷を理解して適切に使い分けることが重要である。

実装最適化の勘所

  • キャッシュ最適化：配列を連続アクセスし、バタフライのループ順序を調整する。

  • SIMD/マルチスレッド：データ並列とスレッド並列でFFTのコア演算を高速化する。

  • 実数・多次元FFT：R2C/C2Rや2D/3D拡張で画像・体積データを効率処理する。