More than 3 years have passed since last update.

高速フーリエ変換(FFT)のバタフライ演算を可視化してみた

Last updated at 2020-09-19Posted at 2020-09-13

経緯

バタフライ演算の図は数あれど、どの線上で何が重みづけ計算されているのかサッパリわからなかったので色々調べてみたところ、参考サイト1とそのCodePenを見て理解ができたので、インスパイヤされてつくってみた。

バタフライ演算図の読み方・・・線が合流している箇所で加算が行われます。矢印が描画されている箇所では重みづけ計算がされます。

Inputの横のスライダの値を変化させると、選択した経路（白線）に応じて、重み¹が角度単位で表示されます。経路中（白線上）の合計角度が45度刻み²に増えるのが見て取れるかと思います。

上側の波形を入力としてフーリエ変換結果を下側に描画します。
スライダで指定した繰り返し数のsin波で、入力側の波形を初期化します。

See the Pen FFT by kob58im (@kob58im) on CodePen.

※JavaScriptの場合は、手実装するより、ありものを使ったほうがよさそう。
getUserMediaで音声を拾いリアルタイムで波形を出力する - Qiita

下記１つ目のサイトのButterfly Diagram Maker - CodePenのおかげでバタフライ演算の図の読み方が理解できました。感謝！