信息处理 - 计算信号的 FFT 需要多少次乘法和加法？ - 吾爱随笔录

计算信号的 FFT 需要多少次乘法和加法？

信息处理 fft

2022-02-22 04:00:39

的长度和 FFT bin 的数量而言，执行 FFT 运算需要多少次乘法/加法？我不想要关于大 O 的答案，而是仅关于和的答案。 $N$ $M$ $N$ $M$

1个回答

如果您对更多涉及的运算感兴趣，您可以查看A modified split-radix FFT with less算术运算，作者 Johnson 和 Frigo，IEEE Transactions on Signal Processing，2007，“Fastest Fourier Transform in the West”的作者（ FFTW）。例如，他们声称经典 radix-2 的复杂性约为：

5 N \log_{2} N

$5N\log_2 N$

而分裂基数产生：

4 N \log_{2} N - 6 N + 8,

$4N \log_2 N − 6N + 8\,,$

他们取得了进步：

\frac{34}{9} N \log_{2} N - \frac{124}{27} N - 2 \log_{2} N - \frac{2}{9} (- 1)^{\log_{2} N} \log_{2} N + \frac{16}{27} (- 1)^{\log_{2} N} + 8 .

$\frac{34}{9} N \log_2 N − \frac{124 }{27 }N − 2 \log_2 N − \frac{2}{9} (−1)^{\log_2 N} \log_2 N + \frac{16}{27} (−1)^{\log_2 N} + 8\,.$

正如其他人所说，您可以看到这个数字取决于实现，并且实际收益是微妙的。

其它你可能感兴趣的问题

上一篇香农定理中的“容量”概念下一篇实时类振荡噪声过滤