快速傅里叶变换（FFT）基础（附python实现）
对于非专业人士，傅里叶变换一直是一个神秘的武器，它可以分析出不同频域的信息，从时域转换到频域，揭示了信号的频率成分，对于数字信号处理（DSP）、图像、语音等数据来说，傅里叶变换是最为基础，同时非常重要的分析工具。在处理真实世界的问题中，快速傅里叶变换（Fast Fourier Transform，FFT）是一种高效的算法，用于计算离散傅里叶变换（Discrete Fourier Transform，DFT）及其逆变换。DFT是傅里叶变换在离散数据上的版本，FFT算法的出现极大地减少了DFT的计算复杂度，使得在实际应用中变得可行。本文介绍一些基础概念，最后使用一个python小例子来展示FFT的效果。
傅里叶变换的基本概念
傅里叶变换是一种数学工具，它表明任何周期函数都可以表示为正弦和余弦函数的和。在信号处理中，傅里叶变换用于分析信号的频率成分，即信号中包含的所有不同频率的正弦波。
离散傅里叶变换（DFT）
DFT是傅里叶变换的离散版本，它将有限长度的时域信号转换为有限长度的频域信号。对于一个长度为N的序列x[n]，其DFT定义为：
[
X
[
k
]
=
∑
n
=
0
N
−
1
x
[
n
]
⋅
e
−
j
2
π
N
k
n
]
[ X[k] = \sum_{n=0}{N-1} x[n] \cdot e{-j \frac{2\pi}{N} kn} ]
[X[k]=∑n=0N−1x[n]⋅e−jN2πkn]
其中，X[k]是序列x[n]的DFT，k是频率索引，j是虚数单位。
快速傅里叶变换（FFT）
FFT是DFT的一种高效算法实现，它利用了DFT的对称性和周期性等数学性质，将复杂度从 O ( N 2 ) O(N^2) O(N2)降低到 O ( N l o g N ) O(N log N) O(NlogN)。这意味着对于长度为N的序列，FFT算法可以在对数时间内完成DFT的计算。
FFT的关键性质
FFT是一种强大的工具，它使得在各种科学和工程领域中分析和处理信号成为可能。通过将信号分解为不同频率的组成部分，FFT揭示了信号的内在结构，为信号处理提供了一个强大的分析框架。所有这些，其实都利益于它具备如下的特点：
- 线性：FFT保持了傅里叶变换的线性性质。
- 时域和频域的局部性：FFT算法利用了“蝶形操作”来减少复数乘法的数量。
- 并行性：FFT可以并行执行，进一步提高计算效率。
因此，FFT在很有领域有广泛的应用：
- 信号处理：音频和图像的压缩、滤波和分析。
- 图像处理：边缘检测、图像增强和图像压缩。
- 通信系统：在无线通信中，FFT用于信道均衡和信号调制。
- 数据分析：频谱分析和周期性检测。
代码
下面给出一个例子，使用pytorch，分析两个不同频率合成后的信号，使用FFT识别出两个频率，最后使用matplotlib来进行可视化：
import torch
import numpy as np
import matplotlib.pyplot as plt
# 设置参数
sample_rate = 1000 # 采样率 (Hz)
T = 1 / sample_rate # 采样间隔
t = np.linspace(0, 1, sample_rate, endpoint=False) # 时间向量
# 生成信号
freq1, freq2 = 50, 120 # 两正弦波的频率
amplitude1, amplitude2 = 0.7, 0.5 # 振幅
signal = amplitude1 * np.sin(2 * np.pi * freq1 * t) + amplitude2 * np.sin(2 * np.pi * freq2 * t)
# 将信号转换为 Torch 张量
signal_tensor = torch.tensor(signal, dtype=torch.float32)
# 执行 RFFT
rfft_result = torch.fft.rfft(signal_tensor)
# 获取幅度谱
magnitude = torch.abs(rfft_result)
# 频率轴
frequencies = torch.fft.rfftfreq(signal.size, d=T)
plt.figure(figsize=(12, 6))
# 原始信号
plt.subplot(2, 1, 1)
plt.plot(t, signal)
plt.title('Original Signal')
plt.xlabel('Time [s]')
plt.ylabel('Amplitude')
# 频谱
plt.subplot(2, 1, 2)
plt.plot(frequencies.numpy(), magnitude.numpy())
plt.title('Magnitude Spectrum')
plt.xlabel('Frequency [Hz]')
plt.ylabel('Magnitude')
plt.tight_layout()
plt.show()
效果
上图为原始信息，由两个信息合成；下图为解析出来的光谱图，可以看到，分析得到两个脉冲，分别对应两个正弦波的频率：50与120，可以看到FFT的神奇之处了吧：）
