お薦めの本 トピックス プログラム、シミュレーション 数学 物理 科学・技術・数学

似たパターンに変形して、計算を効率化

投稿日:

フーリエの冒険」も最終章になりました。 資料作成に手間取って昨日投稿できませんでした。 FFTのアルゴリズムを説明します。 離散的なデータを用いてフーリエ変換をします。cossinを掛けて面積を算出するフーリエ展開指数を用いたフーリエ展開を説明してきました。いずれも、計算処理にはコンピュータを使いますが、高速に処理するためのアルゴリズムが必要です。

資料を参照ください → FFT

p.1 f(t)という波から一定の時間(τ)毎にサンプリングしたデータを用いてフーリエ変換をします。

p.2 「e^(-i2π/N)=W」とおいて、見やすくします。この式は「回転子」といって、Wを掛けると半径1の円周上で回転させることができます。p.1の波からN=8のデータを得たとして説明していきます。 N=8の時、フーリエ変換の式は、G(0/8)~G(7/8)の8つの式で計算します。

p.3 上述の8つの式をマトリックスで表したものが、上の表です。Wは回転を意味しますので、1周以上すると、同じWが出現します。例えば、W0=W8、W1=W9・・となります。これを使って書き換えたマトリックスが下の表です。

p.4 f(t)をtの偶数奇数に分けて集めます。偶数のマトリックス表(左図)を見てください。上の4行(赤枠)と下の4行のWの値が同じであることがわかります。奇数の方は、Wnの列を外に出して掛ける形にすると、緑枠のように偶数と同じになります。 これより赤枠の計算をすれば他のマトリックスの計算はそれを利用すればよいことになります。

p.5 同様に、右と左のマトリックスを偶数列奇数列に分けると、W0、W2、W及びW2のマトリックスに置き換えることができます。

p.6 解析したい波の8つのポイントがf(0)~f(7)ですが、各々の列に各々のWを掛けて行方向に加算すると、p.2の計算が可能になります。これにより、64回を24回まで計算を短縮可能です。8ポイントですので削減効果は低いですが、1024点のデータを解析する時は、1,048,576→10,240回にまで削減可能だそうです。データを解析する際は、のサンプリング数にすると、今回のように半分、そのまた半分と数を削減可能です。

p.7 アルゴリズムはいろいろあるようです。 Wikipediaから引用しました。 → 高速フーリエ変換

ようやく「フーリエの冒険」の説明終了です。 いかがでしたか? 何度も言っていますが、この本、本当に理解し易いよい本です。 フーリエ逆変換は、以前説明したようにカーブフィッティングにも使えます。

-お薦めの本, トピックス, プログラム、シミュレーション, 数学, 物理, 科学・技術・数学

Copyright© 進化するガラクタ , 2019 All Rights Reserved Powered by STINGER.