高速フーリエ変換（FFT)
高速フーリエ変換（FFT) 信州大学工学部 井澤裕司 １． 高速フーリエ変換とは ここでは、高速フーリエ変換について解説します。 高速フーリエ変換（Fast Fourier Transform; FFT）は、離散フーリエ変換の対称性に着目して、 その演算量を減らし高速に変換を行う手法であり、1965年、CooleyとTukeyにより発表されました。 周期 N の離散フーリエ変換（DFT)では、複素数の乗算を N2 回行う必要があります。 高速フーリエ変換では、その乗算回数を N・log2N /2 回に減らすことができます。 なお、乗算では加算を複数回行うので、加算より複雑な処理になります。 例えばNが2のべき乗、すなわち N=2m のとき、その比率を求めると、 ［FFT] / [DFT] = m・2m-1/22m = m/2m+1 となり、ｍ（すなわちN）が大きいほど、その効果がはっきり現
高速フーリエ変換 - [物理のかぎしっぽ]
ここで上の行列の真ん中で左右に分けて考えると，添字が偶数の行については左と右の部分が同じで，添字が奇数の行については左と右の部分が半周期ずれたものになっているのがわかります．そのため上の式は以下と等価です． 図1 図1を見てもわかる通りxの並びが変わっています．このように並び替えることで計算がしやすくなります．それではソースコードを見てみます． dfttimes = num; power = power_two(num); //２の何乗かを返す for(i=0; i<power-1; i++){ indexto = offset = 0; while(indexto < num){ indexfrom = 0; while(indexfrom < dfttimes){ rbuf[indexto] = re[indexfrom + offset]; ibuf[indexto] = im[in
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
