字数

1277 字

阅读时间

6 分钟

快速傅里叶变换（Fast Fourier Transform, FFT）是一种高效的算法，用于计算离散傅里叶变换（Discrete Fourier Transform, DFT）及其逆变换。 DFT 可以将时域信号转换为频域表示，而 FFT 通过利用 DFT 中的对称性和周期性来减少计算量，从而大大提高了计算速度。

原理

FFT 的核心思想是“分而治之”，即将一个问题分解成多个更小的子问题，这些子问题是原问题的简化版本。对于一个 N 点的 DFT，如果 N 是一个 2 的幂次方，那么 FFT 算法会递归地将这个 DFT 分解为两个 N/2 点的 DFT，然后继续分解直到达到最小单元。这一过程显著减少了所需的乘法和加法次数。

具体来说，FFT 通常使用蝶形运算结构，它把输入序列按照偶数和奇数索引分为两部分，并分别对这两部分进行较小规模的 DFT 计算。之后，再结合这两个结果得到完整的 DFT 输出。这种递归分解的方法使得原本需要 $O(N^2)$ 次操作的 DFT 可以在 $O(N\log N$) 时间内完成。

与傅里叶变换的区别

1. 定义与适用范围：
   • 傅里叶变换（Fourier Transform, FT）适用于连续时间或空间上的函数。
   • 离散傅里叶变换（DFT）是 FT 在离散情况下的对应物，主要用于==处理数字信号==。
   • 快速傅里叶变换（FFT）是 DFT 的一种高效实现方式，专门设计==用来加速大规模数据集的 DFT 计算==。
2. 计算复杂度：
   • 对于长度为 N 的数据序列，标准 DFT 的计算复杂度为(O (N^2))，这在大数据集上会导致极高的计算成本。
   • FFT 则能够将复杂度降低到(O (N \log N))，极大地提升了计算效率，尤其当 N 很大时效果明显。 综上所述，虽然 FFT 和 FT 都是用于将信号从时域转换到频域的工具，但是 FFT 作为一种优化算法，在面对大型数据集时提供了==更快的速度==和==更低的计算资源需求==。

示例代码

% 参数设定
Fs = 1000; % 采样频率 (Hz)
T = 1/Fs; % 采样周期 (s)
L = 1000; % 信号长度 (采样点数)
t = (0:L-1)*T; % 时间向量

% 创建一个包含两个频率成分的合成信号
f1 = 100; % 第一个正弦波频率 (Hz)
f2 = 600; % 第二个正弦波频率 (Hz)
x = 0.7*sin(2*pi*f1*t) + sin(2*pi*f2*t); % 合成信号

% 执行快速傅里叶变换
X = fft(x);

% 计算双边频谱P2
P2 = abs(X/L);

% 单边频谱P1
P1 = P2(1:L/2+1);
P1(2:end-1) = 2*P1(2:end-1); % 只加倍中间部分，不包括DC和Nyquist分量

% 频率轴
f = Fs*(0:(L/2))/L;

% 绘制单边幅度谱
plot(f, P1)
title('单边幅度谱')
xlabel('f (Hz)')
ylabel('|P1(f)|')
grid on;

代码解读

[! tip]+ 代码解读单边频谱的绘制 X 是通过快速傅里叶变换（FFT）得到的结果，它是一个复数数组，代表了信号在频域中的表示 abs(X) 函数计算的是这些复数值的绝对值，即它们的模长，这给出了各频率分量的幅度。 X/L 的操作是为了对结果进行归一化处理，使得频谱的幅度反映了真实的物理意义。这里的 L 是原始时间序列的长度（采样点数），除以 L==使频谱的幅度与输入信号的平均功率相对应==。 P 1 = P 2 (1: L/2+1); 我们选择了从第一个元素到中间位置（包括奈奎斯特频率）的频谱值来构建单边频谱。 P 1 (2: end-1) = 2*P 1 (2: end-1); % 只加倍中间部分，不包括 DC 和 Nyquist 分量调整幅度：由于只保留了一半的频谱，为了==保持总能量不变==，除了直流分量（DC，即频率为0的部分）和奈奎斯特频率外，所有其他频率分量的幅度都要乘以2。

结果

![[Pasted image 20250116154011.png|400]] 可以观察到上面的信号明明是 100 Hz 和 600 Hz 但是为什么快速傅里叶变换后得到的是 100 和 400 Hz 呢，原因是出现了频率混叠。任何高于500Hz（$F_s/2$）的频率都会出现混叠现象，并表现为较低的频率。

更改一下绘图的逻辑，得到双边幅度谱

figure;
subplot(1, 2, 1);
% 绘制单边幅度谱
plot(f, P1)
title('单边幅度谱')
xlabel('f (Hz)')
ylabel('|P1(f)|')
grid on;
subplot(1,2,2)
% 频率轴
f = Fs*(0:L-1)/L;
%绘制双边幅度谱
plot(f,P2)
title('双边幅度谱')
xlabel('f (Hz)')
ylabel('|P2(f)|')
grid on;

![[Pasted image 20250116155720.png]]

贡献者

OveDuke

文件历史

最后编辑于 大约 2 小时前查看完整历史

623e9-update_ai