快速傅里叶变换（FFT）

快速傅里叶变换是计算离散傅里叶变换的高效算法！理解FFT，能帮助我们快速处理数字信号。

什么是快速傅里叶变换？

快速傅里叶变换（Fast Fourier Transform，FFT）是计算离散傅里叶变换（DFT）的高效算法。

简单理解

FFT就像"快速计算DFT的算法"：

• DFT的计算复杂度是 $O(N^2)$
• FFT的计算复杂度是 $O(N \log N)$
• 当 $N$ 很大时，FFT比DFT快得多

历史背景

FFT算法由库利（Cooley）和图基（Tukey）在1965年提出，但早在1805年高斯就已经使用了类似的算法。

离散傅里叶变换（DFT）

定义

对于长度为 $N$ 的序列 $x[n]$，离散傅里叶变换：

$X[k] = \sum_{n=0}^{N-1} x[n] e^{-i 2\pi kn/N} \quad (k = 0, 1, 2, \ldots, N-1)$

逆变换

$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i 2\pi kn/N} \quad (n = 0, 1, 2, \ldots, N-1)$

计算复杂度

直接计算DFT需要 $N^2$ 次复数乘法和 $N(N-1)$ 次复数加法，复杂度为 $O(N^2)$。

FFT算法

基本思想

FFT利用分治法（Divide and Conquer）的思想：

1. 将长度为 $N$ 的序列分成两个长度为 $N/2$ 的子序列
2. 递归计算两个子序列的DFT
3. 合并结果得到原序列的DFT

时间抽取FFT（DIT-FFT）

时间抽取FFT（Decimation in Time FFT）将序列按时间（索引）分为奇偶两部分。

设 $N = 2^m$，将 $x[n]$ 分为：

• 偶数索引：$x[2r] = x_0[r]$（$r = 0, 1, \ldots, N/2 - 1$）
• 奇数索引：$x[2r + 1] = x_1[r]$（$r = 0, 1, \ldots, N/2 - 1$）

则：

$X[k] = \sum_{r=0}^{N/2-1} x[2r] W_N^{2rk} + \sum_{r=0}^{N/2-1} x[2r+1] W_N^{(2r+1)k}$

其中 $W_N = e^{-i 2\pi/N}$ 是旋转因子。

可以写成：

$X[k] = X_0[k] + W_N^k X_1[k]$

其中 $X_0[k]$ 和 $X_1[k]$ 分别是 $x_0[n]$ 和 $x_1[n]$ 的DFT。

频率抽取FFT（DIF-FFT）

频率抽取FFT（Decimation in Frequency FFT）将DFT结果按频率（索引）分为前后两部分。

蝶形运算

FFT的核心是蝶形运算（Butterfly Operation）：

X[k] = X_0[k] + W_N^k X_1[k] \\ X[k + N/2] = X_0[k] - W_N^k X_1[k] \end{cases}$$ 这个运算的形状像蝴蝶，因此称为蝶形运算。 ## FFT的计算复杂度 ### 复杂度分析 对于长度为 $N = 2^m$ 的序列： - 第1层：$N/2$ 个蝶形运算 - 第2层：$N/4$ 个蝶形运算 - ... - 第 $m$ 层：$N/2^m = 1$ 个蝶形运算 总共有 $m = \log_2 N$ 层，每层有 $N/2$ 个蝶形运算。 每个蝶形运算需要1次复数乘法和2次复数加法。 所以总计算量： - 复数乘法：$\frac{N}{2} \log_2 N$ - 复数加法：$N \log_2 N$ 复杂度为 $O(N \log N)$。 ### 与DFT的比较 | 算法 | 复杂度 | $N = 1024$ 时的计算量 | |------|--------|----------------------| | DFT | $O(N^2)$ | 约 $10^6$ 次运算 | | FFT | $O(N \log N)$ | 约 $10^4$ 次运算 | 当 $N$ 很大时，FFT比DFT快得多！ ## FFT的实现 ### 递归实现 ```python def fft_recursive(x): N = len(x) if N <= 1: return x even = fft_recursive(x[0::2]) odd = fft_recursive(x[1::2]) T = [exp(-2j*pi*k/N) * odd[k] for k in range(N//2)] return [even[k] + T[k] for k in range(N//2)] + \ [even[k] - T[k] for k in range(N//2)] ``` ### 迭代实现 迭代实现通常比递归实现更高效，使用位反转和蝶形运算。 ## FFT的应用 ### 信号处理 - 📡 **频谱分析**：快速计算信号的频谱 - 🔊 **滤波**：在频域进行滤波 - 📺 **压缩**：快速压缩信号 ### 图像处理 - 🖼️ **图像变换**：快速计算图像的傅里叶变换 - 🎨 **图像滤波**：在频域进行图像滤波 - 🔍 **图像压缩**：快速压缩图像 ### 通信工程 - 📻 **信号分析**：快速分析通信信号 - 📡 **调制解调**：快速处理调制信号 ### 科学计算 - 🔬 **数值计算**：快速计算卷积、相关等 - 📊 **数据分析**：快速分析实验数据 ## 生活中的应用 ### 音频处理 - 🎵 **音乐分析**：快速分析音乐的频谱 - 🔊 **音频滤波**：快速滤波音频信号 - 🎤 **语音识别**：快速处理语音信号 ### 医学 - 🏥 **医学成像**：快速处理医学图像 - 💊 **信号分析**：快速分析生理信号 ### 科学 - 🔬 **光谱分析**：快速分析光谱 - 📊 **数据分析**：快速分析实验数据 ## FFT的变种 ### 基-2 FFT **基-2 FFT**要求序列长度为2的幂次（$N = 2^m$）。 ### 基-4 FFT **基-4 FFT**要求序列长度为4的幂次（$N = 4^m$），通常比基-2 FFT更快。 ### 混合基FFT **混合基FFT**可以处理任意长度的序列，通过分解为小质数的乘积。 ### 快速数论变换（NTT） **快速数论变换**（Number Theoretic Transform）是FFT在有限域上的推广。 ## 常见错误 ### 错误 1：序列长度不是2的幂次 基-2 FFT要求序列长度为2的幂次，否则需要补零或使用其他方法。 ### 错误 2：旋转因子计算错误 要正确计算旋转因子 $W_N^k = e^{-i 2\pi k/N}$。 ### 错误 3：索引错误 要注意数组索引，特别是位反转操作。 ## 小练习 1. 说明FFT和DFT的区别 2. 解释蝶形运算的作用 3. 分析FFT的计算复杂度 4. 应用题：在音频处理中，为什么使用FFT而不是DFT？ --- > 💡 **小贴士**：快速傅里叶变换是计算离散傅里叶变换的高效算法。记住：FFT的计算复杂度是 $O(N \log N)$，比DFT的 $O(N^2)$ 快得多。掌握FFT，你就能快速处理数字信号！