離散フーリエ変換(DFT)の計算オーダーと高速フーリエ変換(FFT)【理工数学】
離散フーリエ変換の計算効率 DFTを定義に基づいて計算した場合、どれくらいの計算ステップが必要なのかを調べてみる。 まず、DFTの定義から出発する。 $$G_n=\sum_{k=0}^{N-1}g_ke^{-\frac{2\pi ink}{N}}$$ いま、式を見やすくするために $$W^k=e^{ […]
TAG
離散フーリエ変換
離散フーリエ変換の理論と計算【理工数学】
離散フーリエ変換 これまで、離散的な時刻tk=kΔt (k=0, ±1, ±2, …, ±∞) でサンプリングされた無限個のデータに対するフーリエ変換Gs(f)を考え、その性質について論じてきた。 しかし、実際にコンピュータ上で数値計算を行う場合、データは有限個である。このとき、フーリエ変換は連続関 […]
離散データのフーリエ変換とサンプリング定理(標本化定理)の導出【理工数学】
周期デルタ関数列とそのフーリエ変換 時刻tk=kΔt (k=0, ±1, ±2, …)にデルタ関数をもつ、周期デルタ関数列を次式で定義する。 $$\delta_{\Delta t}(t)=\sum_{k=-\infty}^{\infty}\delta(t-k\Delta t)$$ この […]
離散フーリエ変換(DFT)とサンプリング定理の概要
離散フーリエ変換 ここまで、フーリエ変換の数学的な理論について学んできた。 実際にフーリエ変換を応用する場合には、現実の信号を有限の時間で測定し、離散的なデータを元にコンピュータを用いて計算しなくてはならない。 これから、そのための手法である「離散フーリエ変換」について学んでいく。 サ […]