FFT 与 DFT 相关知识全总结

本文系统整理 DFT、FFT 的定义、性质、频率轴、分辨率、窗函数、快速算法、循环卷积，以及在雷达信号处理中的典型应用。

结合前文 PRF、频率分辨率、中频/射频/零频、IQ、欧拉公式等知识点。

1. DFT 定义
2. IDFT 与对称形式
3. DFT 的物理意义
4. DFT 与 DTFT、DFS、CTFT 的关系
5. 频率轴与频率分辨率
6. DFT 的性质
7. 循环卷积与线性卷积
8. 窗函数、泄漏与栅栏效应
9. 补零与频谱插值
10. FFT 快速算法
11. 基 2 FFT：DIT 与 DIF
12. 其他 FFT 算法
13. 实序列 FFT 优化
14. 雷达中的 FFT 应用
15. Python 示例
16. 常见误区
17. 公式速查
18. 一句话总结

1. DFT 定义

离散傅里叶变换 DFT 将长度为 N 的离散序列 x[n] 变换为长度为 N 的离散频谱 X[k]。

正变换：

X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}, \quad k = 0, 1, \ldots, N-1

其中旋转因子：

W_N = e^{-j2\pi/N}

所以：

W_N^{kn} = e^{-j2\pi kn/N}

W_N 就是欧拉公式的直接应用。

逆变换 IDFT：

x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn}, \quad n = 0, 1, \ldots, N-1

2. IDFT 与对称形式

IDFT 另一种写法：

x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j2\pi kn/N}

对比 DFT：

\mathrm{DFT}: e^{-j2\pi kn/N}, \qquad \mathrm{IDFT}: e^{+j2\pi kn/N}

区别：

DFT 使用负指数；
IDFT 使用正指数；
IDFT 需要除以 N。

若把 DFT 写成矩阵形式：

X = W x, \qquad x = \frac{1}{N} W^* X

其中 W 是 DFT 矩阵，元素为 $W_N^{kn}$ 。

3. DFT 的物理意义

DFT 可以理解为：

对有限长序列进行周期延拓；
取周期序列的一个周期；
求离散傅里叶级数 DFS；
得到频域离散采样。

因此 DFT 隐含了以下假设：

时域序列是周期的，周期为 N；
频域也是周期的，周期为 N；
时域和频域都是离散的。

DFT 的频率 bin 对应：

f_k = k \frac{f_s}{N}, \quad k = 0, 1, \ldots, N-1

其中 fs 是采样率。

4. DFT 与 DTFT、DFS、CTFT 的关系

变换	时域	频域	特点
CTFT	连续、非周期	连续、非周期	模拟信号频谱
DTFT	离散、非周期	连续、周期	离散时间傅里叶变换
DFS	离散、周期	离散、周期	离散傅里叶级数
DFT	离散、有限长	离散、有限长	对 DTFT 频域采样

关系：

DFT 是对 DTFT 在 $[0, 2\pi)$ 上的 N 点等间隔采样；
DFT 是对 DFS 取一个周期；
DFT 是对 CTFT 经过采样、截断、周期延拓后的近似。

5. 频率轴与频率分辨率

5.1 频率 bin

DFT 输出 X[k] 对应的频率：

f_k = k \frac{f_s}{N}, \quad k = 0, 1, \ldots, N-1

频率范围：

0 \le f_k \lt f_s

如果使用 fftshift，频率范围变为：

-\frac{f_s}{2} \le f_k \lt \frac{f_s}{2}

对应索引：

k = -\frac{N}{2}, \ldots, -1, 0, 1, \ldots, \frac{N}{2} - 1

5.2 DFT bin 间隔

\Delta f_{bin} = \frac{f_s}{N}

如果采样时间：

T = \frac{N}{f_s}

则：

\Delta f_{bin} = \frac{1}{T}

5.3 真实频率分辨率

DFT bin 间隔是频域采样间隔，不等于真实频率分辨率。

真实频率分辨率主要取决于观测时间：

\Delta f_{real} \approx \frac{1}{T}

其中 T 是有效观测时间。补零可以让 $\Delta f_{bin}$ 变小，但不会提高 $\Delta f_{real}$ 。

5.4 与 PRF 的关系

在雷达慢时间维：

f_{s,\mathrm{slow}} = PRF, \quad T_{CPI} = \frac{N}{PRF}

\Delta f_{bin} = \frac{PRF}{N} = \frac{1}{T_{CPI}}, \quad \Delta f_d \approx \frac{1}{T_{CPI}} = \frac{PRF}{N}

所以：

\Delta f_d = \frac{PRF}{N}

固定 N 时，PRF 越高， $\Delta f_d$ 越大，频率分辨率越差。

6. DFT 的性质

6.1 线性

\mathrm{DFT}\{a x_1[n] + b x_2[n]\} = a X_1[k] + b X_2[k]

6.2 循环移位

时域循环移位：

x[(n - m) \bmod N] \leftrightarrow X[k] e^{-j2\pi km/N}

频域循环移位：

x[n] e^{j2\pi mn/N} \leftrightarrow X[(k - m) \bmod N]

6.3 循环卷积

时域循环卷积对应频域乘积：

x[n] \circledast h[n] \leftrightarrow X[k] H[k]

频域循环卷积对应时域乘积：

x[n] h[n] \leftrightarrow \frac{1}{N} X[k] \circledast H[k]

6.4 共轭对称

若 x[n] 是实序列：

X[k] = X^*[(N - k) \bmod N]

即实部偶对称，虚部奇对称。

若 x[n] 是实偶序列，则 $X[k]$ 为实偶序列。

若 x[n] 是实奇序列，则 $X[k]$ 为虚奇序列。

6.5 帕塞瓦尔定理

\sum_{n=0}^{N-1} \lvert x[n] \rvert^2 = \frac{1}{N} \sum_{k=0}^{N-1} \lvert X[k] \rvert^2

能量守恒。

6.6 对偶性

\mathrm{DFT}\{x[n]\} = X[k], \qquad \mathrm{DFT}\{X[n]\} = N x[(-k) \bmod N]

6.7 调制

x[n] \cos(2\pi mn/N) \leftrightarrow \frac{1}{2}\left(X[(k-m) \bmod N] + X[(k+m) \bmod N]\right)

6.8 实序列频谱对称

实序列的 DFT 幅度谱关于 $N/2$ 对称，相位谱奇对称。因此只需要计算前 $N/2 + 1$ 个点。

7. 循环卷积与线性卷积

7.1 循环卷积定义

y[n] = x[n] \circledast h[n] = \sum_{m=0}^{N-1} x[m] h[(n - m) \bmod N]

7.2 线性卷积定义

y[n] = x[n] * h[n] = \sum_{m} x[m] h[n - m]

长度为：

L = L_x + L_h - 1

7.3 用 FFT 计算线性卷积

步骤：

将 x[n] 和 h[n] 补零到长度 $N \ge L_x + L_h - 1$ ；
计算 X[k] = FFT{x[n]}；
计算 H[k] = FFT{h[n]}；
计算 Y[k] = X[k] H[k]；
计算 y[n] = IFFT{Y[k]}。

这样得到的 y[n] 就是线性卷积，而不是循环卷积。

7.4 分段卷积

当信号很长时，使用：

Overlap-Add 法；
Overlap-Save 法。

用于实时滤波、脉冲压缩等。

8. 窗函数、泄漏与栅栏效应

8.1 频谱泄漏

DFT 假设信号是周期为 N 的周期信号。如果信号频率不是 $\Delta f_{bin}$ 的整数倍，会产生频谱泄漏。

泄漏原因：

时域截断；
非整周期采样；
矩形窗旁瓣较高。

8.2 栅栏效应

DFT 只在离散频点 $f_k = k f_s / N$ 上采样频谱。如果真实频率位于两个 bin 之间，峰值可能落在两个 bin 上，称为栅栏效应。

补零可以减小栅栏效应，但不能提高真实分辨率。

8.3 常见窗函数

窗函数	主瓣宽度	旁瓣衰减	特点
矩形窗	最窄	-13 dB	分辨率最好，泄漏大
汉宁窗	较宽	-31 dB	通用
汉明窗	较宽	-41 dB	旁瓣低
布莱克曼窗	更宽	-57 dB	旁瓣很低
凯泽窗	可调	可调	参数可调

8.4 加窗影响

降低旁瓣，抑制泄漏；
展宽主瓣，降低频率分辨率；
需要根据应用折衷。

9. 补零与频谱插值

9.1 补零的作用

使 N 增大， $\Delta f_{bin} = f_s / N$ 变小；
频谱看起来更密；
减小栅栏效应；
便于观察峰值位置。

9.2 补零不能做什么

不能增加信息量；
不能提高真实频率分辨率；
不能分辨原本无法分辨的两个频率分量。

9.3 真实分辨率

真实分辨率由观测时间 T 决定：

\Delta f_{real} \approx \frac{1}{T}

如果两个频率间隔小于 1/T，即使补零也无法分辨。

10. FFT 快速算法

FFT 是 DFT 的快速算法。

10.1 直接 DFT 复杂度

直接计算 N 点 DFT：

O(N^2)

10.2 FFT 复杂度

基 2 FFT：

O(N \log_2 N)

当 N 很大时，FFT 比 DFT 快几个数量级。

10.3 基本思想

利用旋转因子的周期性和对称性：

W_N^{k+N/2} = -W_N^k, \qquad W_N^{k+N} = W_N^k

将 N 点 DFT 分解为两个 N/2 点 DFT，递归计算。

11. 基 2 FFT：DIT 与 DIF

11.1 按时间抽取 DIT

将输入序列按奇偶分组：

x[2r]：偶序列；
x[2r+1]：奇序列。

得到：

X[k] = E[k] + W_N^k O[k], \qquad X[k + N/2] = E[k] - W_N^k O[k]

其中 $E[k]$ 和 $O[k]$ 分别是偶序列和奇序列的 N/2 点 DFT， $k = 0, 1, \ldots, N/2 - 1$ 。

11.2 按频率抽取 DIF

将输出序列按前后分组：

X[2r]：偶频率；
X[2r+1]：奇频率。

得到类似蝶形结构。

11.3 蝶形运算

基本蝶形：

A' = A + W \cdot B, \qquad B' = A - W \cdot B

其中 W 是旋转因子。

11.4 位反转

DIT 输入需要位反转排序。例如 N = 8：

自然顺序：0 1 2 3 4 5 6 7
位反转：  0 4 2 6 1 5 3 7

11.5 蝶形图

x[0] ──┬──●─── X[0]
       │
x[4] ──┴──●─── X[1]
...

具体结构可参考标准 FFT 蝶形图。

12. 其他 FFT 算法

12.1 混合基 FFT

当 N 不是 2 的幂时，可以分解为多个因子：

N = N_1 \cdot N_2 \cdot \ldots \cdot N_m

适用于 N 可分解的情况。

12.2 分裂基 FFT

结合基 2 和基 4，减少运算量。

12.3 Bluestein 算法

适用于任意 N，将 DFT 转化为卷积，用 FFT 计算。

12.4 Goertzel 算法

用于计算单个频率点的 DFT：

O(N)

适合检测少数频点，如 DTMF 解码。

12.5 Rader 算法

适用于 N 为素数，将 DFT 转化为循环卷积。

12.6 素因子算法 PFA

适用于 N 分解为互素因子。

13. 实序列 FFT 优化

实序列 x[n] 的 DFT 具有共轭对称性：

X[k] = X^*[N - k]

因此：

只需计算前 $N/2 + 1$ 个点；
可以用一个 N/2 点复 FFT 计算两个实序列的 FFT；
常用 rfft 函数。

例如 NumPy：

X = np.fft.rfft(x)

输出长度为 $N/2 + 1$ 。

14. 雷达中的 FFT 应用

14.1 快时间 FFT：距离维

对每个脉冲的回波采样做 FFT，得到距离信息。距离分辨率：

\Delta R = \frac{c}{2B}

其中 B 是带宽。

14.2 慢时间 FFT：多普勒维

对同一距离单元、不同脉冲的采样做 FFT，得到多普勒频率。

f_d = \frac{2v}{\lambda}

多普勒分辨率：

\Delta f_d \approx \frac{1}{T_{CPI}} = \frac{PRF}{N}

速度分辨率：

\Delta v = \frac{\lambda PRF}{2N}

14.3 距离-多普勒图

二维处理：

快时间维 FFT / 脉冲压缩：测距；
慢时间维 FFT：测速；
形成距离-多普勒二维图。

14.4 脉冲压缩

LFM 信号通过匹配滤波实现脉冲压缩。可用 FFT 实现快速卷积：

y = \mathrm{IFFT}\left(\mathrm{FFT}(x) \cdot \mathrm{FFT}(h)\right)

14.5 CFAR

在距离-多普勒图上进行恒虚警检测。

14.6 加窗

在慢时间维加窗，抑制多普勒旁瓣。但会展宽主瓣，降低多普勒分辨率。

15. Python 示例

15.1 基本 DFT / FFT

import numpy as np
import matplotlib.pyplot as plt

fs = 1000
N = 1024
t = np.arange(N) / fs

f0 = 100
x = np.cos(2 * np.pi * f0 * t)

X = np.fft.fft(x)
f = np.fft.fftfreq(N, d=1/fs)

plt.plot(f, np.abs(X))
plt.xlabel('Frequency (Hz)')
plt.ylabel('Magnitude')
plt.show()

15.2 使用 fftshift

X_shifted = np.fft.fftshift(X)
f_shifted = np.fft.fftshift(f)

plt.plot(f_shifted, np.abs(X_shifted))
plt.show()

15.3 补零

N_fft = 4096
X_zero = np.fft.fft(x, n=N_fft)
f_zero = np.fft.fftfreq(N_fft, d=1/fs)

15.4 加窗

window = np.hanning(N)
x_win = x * window
X_win = np.fft.fft(x_win)

15.5 线性卷积

h = np.ones(10)
N_conv = len(x) + len(h) - 1
X = np.fft.fft(x, n=N_conv)
H = np.fft.fft(h, n=N_conv)
y = np.fft.ifft(X * H).real

16. 常见误区

误区一：FFT 就是 DFT

正确：FFT 是 DFT 的快速算法，结果与 DFT 相同，但计算量更小。

误区二：补零可以提高频率分辨率

正确：补零只减小 bin 间隔，不提高真实分辨率。真实分辨率由观测时间 T 决定。

误区三：DFT bin 间隔就是频率分辨率

正确：bin 间隔是频域采样间隔，真实分辨率还受窗函数、信噪比、观测时间影响。

误区四：加窗一定能提高分辨率

正确：加窗通常降低频率分辨率，但抑制旁瓣和泄漏。

误区五：FFT 只能处理 2 的幂长度

正确：FFT 可以处理任意长度，只是基 2 算法要求 N 为 2 的幂。其他长度可用混合基、Bluestein 等算法。

误区六：实信号 FFT 需要全部 N 点

正确：实信号频谱共轭对称，只需前 $N/2 + 1$ 点。

误区七：循环卷积就是线性卷积

正确：循环卷积是周期延拓后的卷积。要得到线性卷积，需要补零到 $N \ge L_x + L_h - 1$ 。

17. 公式速查

名称	公式
DFT	$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N}$
IDFT	$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j2\pi kn/N}$
旋转因子	$W_N = e^{-j2\pi/N}$
频率 bin	$f_k = k f_s / N$
bin 间隔	$\Delta f_{bin} = f_s / N = 1 / T$
真实分辨率	$\Delta f_{real} \approx 1 / T$
循环卷积	$x[n] \circledast h[n] \leftrightarrow X[k] H[k]$
线性卷积长度	$L = L_x + L_h - 1$
帕塞瓦尔	$\sum_{n=0}^{N-1} \lvert x[n] \rvert^2 = \frac{1}{N} \sum_{k=0}^{N-1} \lvert X[k] \rvert^2$
实序列对称	$X[k] = X^*[N-k]$
基 2 FFT 复杂度	$O(N \log_2 N)$
直接 DFT 复杂度	$O(N^2)$
慢时间多普勒分辨率	$\Delta f_d = PRF / N = 1 / T_{CPI}$
速度分辨率	$\Delta v = \lambda PRF / (2N)$

18. 一句话总结

DFT 是有限长离散序列的傅里叶变换，FFT 是 DFT 的快速算法；DFT 的频率 bin 间隔为 $f_s/N$ ，真实频率分辨率由观测时间 T 决定，补零只能插值不能提高分辨率；在雷达中，快时间 FFT 用于测距，慢时间 FFT 用于测速，多普勒分辨率满足 $\Delta f_d = PRF/N = 1/T_{CPI}$ 。

结束