成果物
今まではFFTの仕組みがよく分かっておらず、見つけたものをそのまま使っていたのですが、WikipediaのCooley-Tukey-algorithmというFFTのアルゴリズムが思いのほか分かりやすかったのでそれをもとに実装してみました。分かりやすさを重視したので速度は遅めですが、工夫すれば軽量化できます。
仕組み
複素数の計算が少々大変ですが、今回のアルゴリズムの中心部はこんなにもシンプルです。偶数部と奇数部に分けて計算し、組み合わせることで求めることができます。
gist.github.com
参考にしたサイト。
Cooley–Tukey FFT algorithm - Wikipedia
Wikipediaの疑似コードは少し癖があるので、こちらのコードを参考に作成しました。
github.com
コード
先ほどのメインのコードに複素数計算やMinimなどを追加したものです。マイク入力に反応して動きます。
Cooley_Tukey_FFTという名前で追加しています。
github.com
