デジタル信号処理の基礎
N点のDFTを定義どおりに計算すると約 N² 回、FFT(高速フーリエ変換)では約 N log₂N 回の演算で済むとする。N = 1024 のとき、FFTによる演算回数の削減の度合いとして最も近いものはどれか。
- A約10分の1
- B約100分の1
- C約1000分の1
答えと解説を見る
正解：B. 約100分の1
N² = 1024² ≈ 105万、N log₂N = 1024 × 10 = 10240 で、比は N/log₂N = 1024 ÷ 10 = 102.4、つまり約100分の1です。N が大きいほど差は広がり、例えば N = 65536 では約4096分の1になります。FFTは、DFTを半分の大きさのDFTに次々に分けて、共通の計算をまとめることで演算を減らします。
- A. log₂N = 10 の値です。比は N²/(N log₂N) = N/log₂N です。
- B. 正しい。1024 ÷ 10 = 102.4 で、約100分の1です。
- C. FFTの演算回数を N 回とした場合の比(N²/N = 1024)です。