快速傅里叶变换（FFT）：重塑数字信号处理时代的算法基石

本文深入剖析快速傅里叶变换（FFT）的历史渊源、数学原理及其在现代工程中的核心应用，揭示这一20世纪最伟大算法如何重塑数字世界。文章追溯了从高斯1805年手稿到Cooley-Tukey 1965年论文的完整历史脉络，详细解释了分治法、蝶形运算和位反转等核心原理，并列举了OFDM（5G/Wi-Fi）、DCT（JPEG/MP3）、Schönhage-Strassen算法（大整数乘法）、地震波反演（核爆监测/石油勘探）等多个领域的深度应用。文章还介绍了FFTW、cuFFT等现代软件实现以及FPGA、ASIC等硬件加速方案。