Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
5
Help us understand the problem. What is going on with this article?
@kob58im

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

経緯

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

バタフライ演算の経路と重みを可視化してみた

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

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

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

高速フーリエ変換を実装してみた (JavaScript)

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

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

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

高速フーリエ変換をC#で実装してみた(ライブラリレス)

C# - Win32API(WinMM)でマイク入力を拾う(32bit) / 高速フーリエ変換を手実装してみた

参考サイト

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

  1. 高速フーリエ変換 (FFT) - ゆるふわブログ
  2. 高速フーリエ変換#アルゴリズム - Wikipedia
  3. 高速フーリエ変換(千葉大学 講義資料 PDF)
  4. https://www.onosokki.co.jp/HP-WK/eMM_back/emm140.pdf
  5. https://qiita.com/kob58im/items/bc5dc3f6114778adc141

  1. +180度($e^{-i\pi}$相当)など 

  2. N=8の場合 

5
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
5
Help us understand the problem. What is going on with this article?