離散フーリエ変換(DFT)の計算オーダーと高速フーリエ変換(FFT)【理工数学】
離散フーリエ変換の計算効率 DFTを定義に基づいて計算した場合、どれくらいの計算ステップが必要なのかを調べてみる。 まず、DFTの定義から出発する。 $$G_n=\sum_{k=0}^{N-1}g_ke^{-\frac{2\pi ink}{N}}$$ いま、式を見やすくするために $$W^k=e^{ […]
TAG
離散フーリエ変換の計算効率 DFTを定義に基づいて計算した場合、どれくらいの計算ステップが必要なのかを調べてみる。 まず、DFTの定義から出発する。 $$G_n=\sum_{k=0}^{N-1}g_ke^{-\frac{2\pi ink}{N}}$$ いま、式を見やすくするために $$W^k=e^{ […]