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 會傳回一個合適的填補大小。
參考文獻
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 4. publisher page
- C. E. Shannon, “Communication in the presence of noise,” Proceedings of the IRE, vol. 37, no. 1, pp. 10–21, 1949. doi
- M. Unser, “Sampling—50 years after Shannon,” Proceedings of the IEEE, vol. 88, no. 4, pp. 569–587, 2000. doi
- 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
- 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
- M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proceedings of the IEEE, vol. 93, no. 2, 2005. doi
- A. V. Oppenheim and J. S. Lim, “The importance of phase in signals,” Proceedings of the IEEE, vol. 69, no. 5, 1981. doi
- 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
- M. Mathieu, M. Henaff and Y. LeCun, “Fast training of convolutional networks through FFTs,” arXiv:1312.5851, 2013. arXiv
- L. Chi, B. Jiang and Y. Mu, “Fast Fourier convolution,” Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020. proceedings
- Y. Rao, W. Zhao, Z. Zhu, J. Lu and J. Zhou, “Global filter networks for image classification,” NeurIPS, 2021. arXiv
- 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
- Z.-Q. J. Xu, Y. Zhang and T. Luo, “Overview frequency principle/spectral bias in deep learning,” arXiv:2201.07395, 2022. arXiv
- 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
- 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
- K. Xu, M. Qin, F. Sun, Y. Wang, Y.-K. Chen and F. Ren, “Learning in the frequency domain,” CVPR, 2020. arXiv
- R. Zhang, “Making convolutional networks shift-invariant again,” ICML, 2019. arXiv
- 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
- 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
- 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
- NumPy developers, “numpy.angle,” NumPy reference documentation, accessed 5 November 2026. API 文件.