快速傅里叶变换（FFT）基础（附python实现）

对于非专业人士，傅里叶变换一直是一个神秘的武器，它可以分析出不同频域的信息，从时域转换到频域，揭示了信号的频率成分，对于数字信号处理（DSP）、图像、语音等数据来说，傅里叶变换是最为基础，同时非常重要的分析工具。在处理真实世界的问题中，快速傅里叶变换（Fast Fourier Transform，FFT）是一种高效的算法，用于计算离散傅里叶变换（Discrete Fourier Transform，DFT）及其逆变换。DFT是傅里叶变换在离散数据上的版本，FFT算法的出现极大地减少了DFT的计算复杂度，使得在实际应用中变得可行。本文介绍一些基础概念，最后使用一个python小例子来展示FFT的效果。

傅里叶变换的基本概念

傅里叶变换是一种数学工具，它表明任何周期函数都可以表示为正弦和余弦函数的和。在信号处理中，傅里叶变换用于分析信号的频率成分，即信号中包含的所有不同频率的正弦波。

离散傅里叶变换（DFT）

DFT是傅里叶变换的离散版本，它将有限长度的时域信号转换为有限长度的频域信号。对于一个长度为N的序列x[n]，其DFT定义为：

$\sum_{n=0}{N-1} x[n] \cdot e{-j \frac{2\pi}{N} kn} ]$
其中，X[k]是序列x[n]的DFT，k是频率索引，j是虚数单位。

快速傅里叶变换（FFT）

FFT是DFT的一种高效算法实现，它利用了DFT的对称性和周期性等数学性质，将复杂度从 $O(N^2)$ 降低到 $O (Nl o g N)$ 。这意味着对于长度为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()