「フーリエの冒険」も最終章になりました。 資料作成に手間取って昨日投稿できませんでした。 ＦＦＴのアルゴリズムを説明します。 離散的なデータを用いてフーリエ変換をします。cosやsinを掛けて面積を算出するフーリエ展開や指数を用いたフーリエ展開を説明してきました。いずれも、計算処理にはコンピュータを使いますが、高速に処理するためのアルゴリズムが必要です。
資料を参照ください → FFT
p.1 f(t)という波から一定の時間（τ）毎にサンプリングしたデータを用いてフーリエ変換をします。
p.2 「e^(-i2π/N)=W」とおいて、見やすくします。この式は「回転子」といって、Wを掛けると半径１の円周上で回転させることができます。p.1の波からN=8のデータを得たとして説明していきます。 N=8の時、フーリエ変換の式は、G(0/8）～G(7/8）の８つの式で計算します。
p.3 上述の８つの式をマトリックスで表したものが、上の表です。Wは回転を意味しますので、1周以上すると、同じWが出現します。例えば、W0＝W8、W1=W9・・となります。これを使って書き換えたマトリックスが下の表です。
p.4 f(t)をｔの偶数と奇数に分けて集めます。偶数のマトリックス表（左図）を見てください。上の４行（赤枠）と下の４行のWの値が同じであることがわかります。奇数の方は、Wnの列を外に出して掛ける形にすると、緑枠のように偶数と同じになります。 これより赤枠の計算をすれば他のマトリックスの計算はそれを利用すればよいことになります。
p.5 同様に、右と左のマトリックスを偶数列と奇数列に分けると、W0、W2、W０及びW2のマトリックスに置き換えることができます。
p.6 解析したい波の８つのポイントがf(0)～f(7)ですが、各々の列に各々のWｎを掛けて行方向に加算すると、p.2の計算が可能になります。これにより、64回を24回まで計算を短縮可能です。８ポイントですので削減効果は低いですが、1024点のデータを解析する時は、1,048,576→10,240回にまで削減可能だそうです。データを解析する際は、２ｎのサンプリング数にすると、今回のように半分、そのまた半分と数を削減可能です。
p.7 アルゴリズムはいろいろあるようです。 Wikipediaから引用しました。 → 高速フーリエ変換
ようやく「フーリエの冒険」の説明終了です。 いかがでしたか？ 何度も言っていますが、この本、本当に理解し易いよい本です。 フーリエ逆変換は、以前説明したようにカーブフィッティングにも使えます。