完整搜尋頁面 →

FFT 的歷史與函式庫

選讀・IP 04・頻域濾波 的補充資料(第 2/2 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

FFT 比電腦還古老,而現代函式庫又遠遠超越教科書上的演算法。

Heideman、Johnson 與 Burrus,〈Gauss and the history of the fast Fourier transform〉[5]。 一篇歷史回顧,把類 FFT 演算法追溯到高斯約 1805 年未發表的手稿,以及 1965 年前的多次重新發現。重點:這個演算法的想法很簡單,被發現過很多次;1965 年真正改變的是數位電腦讓它變得重要。

現代函式庫遠遠超越教科書上的基數 2(radix-2)演算法。Frigo 與 Johnson 介紹的 FFTW [6] 能處理任意長度,在執行時實際量測哪個演算法在這台機器上最快再做選擇,並自動產生小型的「codelet」核心程式。實務上,質因數都很小(2、3、5、7)的長度很快,大質數則較慢。scipy.fft.next_fast_len 會傳回一個合適的填補大小。

參考文獻

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 4. publisher page
  2. C. E. Shannon, “Communication in the presence of noise,” Proceedings of the IRE, vol. 37, no. 1, pp. 10–21, 1949. doi
  3. M. Unser, “Sampling—50 years after Shannon,” Proceedings of the IEEE, vol. 88, no. 4, pp. 569–587, 2000. doi
  4. J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Mathematics of Computation, vol. 19, no. 90, 1965. doi
  5. M. T. Heideman, D. H. Johnson and C. S. Burrus, “Gauss and the history of the fast Fourier transform,” IEEE ASSP Magazine, vol. 1, no. 4, pp. 14–21, 1984. doi
  6. M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proceedings of the IEEE, vol. 93, no. 2, 2005. doi
  7. A. V. Oppenheim and J. S. Lim, “The importance of phase in signals,” Proceedings of the IEEE, vol. 69, no. 5, 1981. doi
  8. A. V. Oppenheim, R. W. Schafer and T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proceedings of the IEEE, vol. 56, no. 8, pp. 1264–1291, 1968. doi
  9. M. Mathieu, M. Henaff and Y. LeCun, “Fast training of convolutional networks through FFTs,” arXiv:1312.5851, 2013. arXiv
  10. L. Chi, B. Jiang and Y. Mu, “Fast Fourier convolution,” Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020. proceedings
  11. Y. Rao, W. Zhao, Z. Zhu, J. Lu and J. Zhou, “Global filter networks for image classification,” NeurIPS, 2021. arXiv
  12. N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. A. Hamprecht, Y. Bengio and A. Courville, “On the spectral bias of neural networks,” ICML, 2019. arXiv
  13. Z.-Q. J. Xu, Y. Zhang and T. Luo, “Overview frequency principle/spectral bias in deep learning,” arXiv:2201.07395, 2022. arXiv
  14. Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart and A. Anandkumar, “Fourier neural operator for parametric partial differential equations,” arXiv:2010.08895, 2020. arXiv
  15. N. Kovachki, Z. Li, B. Liu, K. Azizzadenesheli, K. Bhattacharya, A. Stuart and A. Anandkumar, “Neural operator: Learning maps between function spaces,” Journal of Machine Learning Research, vol. 24, 2023. arXiv
  16. K. Xu, M. Qin, F. Sun, Y. Wang, Y.-K. Chen and F. Ren, “Learning in the frequency domain,” CVPR, 2020. arXiv
  17. R. Zhang, “Making convolutional networks shift-invariant again,” ICML, 2019. arXiv
  18. T. Karras, M. Aittala, S. Laine, E. Härkönen, J. Hellsten, J. Lehtinen and T. Aila, “Alias-free generative adversarial networks,” arXiv:2106.12423, 2021. arXiv
  19. J. Frank, T. Eisenhofer, L. Schönherr, A. Fischer, D. Kolossa and T. Holz, “Leveraging frequency analysis for deep fake image recognition,” ICML, 2020. arXiv
  20. M. Tancik, P. P. Srinivasan, B. Mildenhall, S. Fridovich-Keil, N. Raghavan, U. Singhal, R. Ramamoorthi, J. T. Barron and R. Ng, “Fourier features let networks learn high frequency functions in low dimensional domains,” arXiv:2006.10739, 2020. arXiv
  21. NumPy developers, “numpy.angle,” NumPy reference documentation, accessed 5 November 2026. API 文件.