【数字信号处理】一文讲清FFT(快速傅里叶变换)

本文主要是介绍【数字信号处理】一文讲清FFT(快速傅里叶变换)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速傅里叶变换（Fast Fourier Transform，FFT）

FFT的背景

1、为什么要时域→频域频率？50Hz+频率120Hz正弦波信号叠加，再叠加一些随时间变换的干扰信号（噪声），信号时域上的波形如图2- 1（左）所示。
显然，从图中很难看出真正的有效信息，更无法直接过滤干扰信号。若对叠加信号进行离散傅里叶变换处理，将时域波形→频域图，如图2- 1（右）为变换后的频谱图。此时便很容易分辨出真正有效的频率段是在50Hz和120Hz，而其它频率都是干扰信息。
2、那么问题来了，怎样将时域→频域呢？
于是出现了大神傅里叶。他提出了——离散傅里叶变换（Discrete Fourier Transform，DFT）是一种基础的数字信号处理算法，它将一个离散的信号从时域转换到频域，使得我们可以分析复杂信号中的频率成分。
？？？傅里叶变换是啥玩意？用人话来说，“把信号比喻成一件衣服，任何一块布都可以由不同颜色的线织成，远看这张比布我们不知道是由哪些颜色的线织成的，但如果把布料拆散成一条条线，是不是就可以清晰地分析出所用线的颜色”
同理，傅里叶认为任何一个信号都可以用很多个不同幅度、频率的正弦波/余弦波叠加而成，如果把这些“正弦波/余弦波”分离出来，就可以分析这些波的频率。如果再把这些频率画在如图2- 1（右）的频谱分布图上，就直观地实现了时域→频域

傅里叶变换（法语：Transformation de Fourier，英语：Fourier transform，缩写：FT）是一种线性变换，通常定义为一种积分变换。
其基本思想是一个函数可以用（可数或不可数，可数的情况对应于傅里叶级数）无穷多个周期函数的线性组合来逼近，从而这些组合系数在保有原函数的几乎全部信息的同时，还直接地反映了该函数的“频域特征”。——维基百科

在这里插入图片描述

3、说的简单，那我算起来该怎么算呢？
在现实世界中，一条连续的信号需要经过采样，变成一个个离散的信号后，才能用计算机计算。
用到的算法就是“离散傅里叶变换（Discrete Fourier Transform，DFT）”。
但是离散傅里叶变换的计算量极为庞大，能算，但是太慢！记住就行，因为会用到很多的乘法、加法运算，计算机实现乘法很麻烦！

（有兴趣可以看看为什么计算量大）一个N点复数序列x[n]的离散傅里叶变换定义为公式（3-1）所示，在计算N点序列x[n]的DFT时，每计算一次频率分量应进行N次复数乘法运算以及N-1次复数加法运算，故需要N2次复数乘法运算和(N-1)N次复数加法运算才能获取N个频率分量X[k][28]。由此看来，随着N值增加，信号处理中离散傅里叶变换的运算量会变得极为庞大，从而难以满足实时性的需求。

快速傅里叶变换（Fast Fourier Transform，FFT）

于是便出现了快速傅里叶变换（Fast Fourier Transform，FFT），说白了就是一类快速的计算离散傅里叶变换的方法。代表者是1965年Cooley(库利)和Tukey(图基)提出的FFT，可以将计算N点序列DFT的复乘次数降低到(N/2)log2N。

FFT假设输入信号是周期性的，即它会将一个有限长度的序列视为一个无限长的周期信号。当我们对一个有限长度的信号进行FFT时，实际上是在假设这个信号会无限重复。这个过程称为周期延拓。对于一个正弦波信号，如果你截取了一个完整的周期并进行FFT，得到的频谱将是该正弦波的特征频率。
傅立叶变换（FFT）是一种算法，用于计算离散傅立叶变换（DFT）和其逆变换。
DFT的核心思想是任何时域信号都可以表示为一系列不同频率的正弦波和余弦波的加权和

DFT的数学表达

DFT将一个长度为 (N) 的时域序列 (x(n)) 转换为一个等长的频域序列 (X(k))。每个频域样本 (X(k)) 是通过以下公式计算得到的：

$\sum_{n=0}^{N-1} x(n) e^{-i 2 \pi k n / N}$

其中：
- (x(n)) 是时域信号的第 (n) 个样本。
- (X(k)) 是频域信号的第 (k) 个样本。
- (N) 是总样本数。
- (k) 是频率索引，从 0 到 (N-1)。
- (e^{-i 2 \pi k n / N}) 是一个复数，表示在 (n) 时刻，频率为 (k) 的复指数函数的值。
频域解释

在频域中，(X(k)) 的每个元素代表了信号在对应频率 (k) 处的复数幅度和相位。复数的模（绝对值）给出了该频率成分的强度，而其角度（相位）则表示该频率成分相对于时间原点的相位偏移。

实际计算

FFT算法执行

FFT算法的核心思想是通过分治法将信号分解为更小的部分，以下是具体步骤：

分解信号

分成偶数和奇数部分：将输入信号分为偶数和奇数索引的部分。例如，对于信号 (x[n])，可以分解为：

偶数部分：
$\ldots$
奇数部分：
$\ldots$
递归计算

递归调用FFT：对偶数和奇数部分分别递归调用FFT，直到信号长度为1（基准情况）。

合并结果
合并频谱：使用“蝴蝶运算”将偶数和奇数部分的FFT结果合并。对于每个频率成分 (k)，合并公式为：

$X[k] = E[k] + W_N^k O[k]$

$X[k + N/2] = E[k] - W_N^k O[k]$

其中，

(E[k]) 是偶数部分的FFT结果，
(O[k]) 是奇数部分的FFT结果，
(W_N^k = e^{-2\pi ik/N}) 是旋转因子。
频谱分析

计算幅度和相位：从FFT的输出中提取频率成分，计算幅度和相位。幅度通常为复数结果的模：

$\sqrt{(Re(X[k]))^2 + (Im(X[k]))^2}$

结果后处理
频率分辨率：根据采样频率和信号长度计算频率分辨率。频率分辨率为

$\Delta f = \frac{f_s}{N}$

其中 (f_s) 是采样频率，(N) 是信号长度。

绘制频谱：可以绘制频谱图，展示信号的频率成分。

重要性和应用

例如，在音频处理中，DFT可以帮助识别音乐或语音信号中的不同音调和谐波；
在通信系统中，它用于分析传输信号的频谱，以优化频道使用和减少干扰。

频谱泄露、频谱混叠

特征	频谱泄露	频谱混叠
定义	信号频谱成分扩展到其他频率	高频成分被误认为低频成分
原因	窗口效应或信号截断	采样频率不足
影响	降低频率分辨率和准确性	导致信号失真
解决方法	使用更好的窗函数或增加信号长度	提高采样频率