バタフライ図も行列も見たくない人のための高速フーリエ変換 - アジョブジ星通信

高速フーリエ変換（FFT）を実装しようと思って、まず理論を知らねばと調べたところ、まったくチンプンカンプンだったのですが、とりあえず、なんとか証明を追うことができました。というわけで、バタフライ演算の図を見てもなんもわからん人が FFT を実装するための資料として、この記事を書き残したいと思います。 参考にした資料は、富永氏による GNU Scientific Library に関するドキュメントの翻訳の「FFT アルゴリズム」の「基数2の時間空間法」です。周波数空間については追っていません（どっちでやっても計算量は同じなので）。 なぜ離散フーリエ変換（DFT）を高速化できるのか？ この記事内の式で使用する文字を定義しつつ、 FFT の概要を紹介していきます。 とりあえず、 DFT の式を出しておきましょう（フーリエ変換自体を解説できるほどの理解はないので、ごめんなさい）。 記号 意味 入