FFT 推导过程详解：从傅里叶级数到快速傅里叶变换

傅里叶变换 (Fourier Transform) 的推导过程可以分为两个步骤：由时域到频域的傅里叶级数展开，以及由离散时域到频域的离散傅里叶变换 (DFT)。

首先，我们从傅里叶级数展开开始：

傅里叶级数展开 (Fourier Series Expansion)：假设一个周期为 T 的连续函数 f(t)，可以使用正弦和余弦函数的线性组合来表示它： f(t) = a₀ + ∑(aₙcos(2πnt/T) + bₙsin(2πnt/T))

这里，a₀ 是直流分量 (直流成分)，aₙ 和 bₙ 是函数的频率成分的振幅，n 是频率的正整数倍。

傅里叶级数展开将时域的函数表示为不同频率的正弦和余弦函数的叠加，其中的 aₙ 和 bₙ 描述了每个频率分量的振幅。
离散傅里叶变换 (DFT)：离散傅里叶变换是将连续函数的傅里叶级数展开推广到离散的情况。假设我们有一个 N 个离散样本的序列 x[n]，n 表示离散时间点的索引。

离散傅里叶变换定义为： X[k] = ∑(x[n] * exp(-j2πnk/N))

这里，X[k] 是离散傅里叶变换的结果，表示频率为 k 的离散频率成分的振幅和相位，n 是时间的离散索引，j 是虚数单位。

离散傅里叶变换将时域的离散序列 x[n] 转换为频域的离散序列 X[k]，其中的 X[k] 描述了每个离散频率分量的振幅和相位。
快速傅里叶变换 (FFT)：离散傅里叶变换 (DFT) 的计算复杂度为 O(N^2)，而快速傅里叶变换 (FFT) 是一种高效的算法，将 DFT 的计算复杂度降低到 O(NlogN)。

FFT 是通过将 DFT 的计算过程进行递归分解和合并来实现的，其中利用了傅里叶变换的对称性质和特殊的旋转因子。

FFT 算法的核心思想是将长度为 N 的序列分解成两个长度为 N/2 的子序列，并根据对称性质进行合并。通过递归地进行这种分解和合并，最终得到序列的离散傅里叶变换结果。

这就是傅里叶变换 (Fourier Transform) 的推导过程，从傅里叶级数展开到离散傅里叶变换 (DFT)，再到快速傅里叶变换 (FFT)。通过傅里叶变换，我们可以将时域的信号转换到频域，从而分析信号的频率成分和特征。