快速傅里叶算法（FFT）快在哪里？_民生

快速傅里叶算法（FFT）快在哪里？

创始人

2024-05-26 12:26:15

0次

前言

1、DFT算法

2、FFT算法

2.1 分类

2.2 以基2 DIT（时间抽取） FFT 算法为例

2.2.1 一次分解

2.2.2 多次分解

参考

前言

对信号分析的过程中，为了能换一个角度观察问题，很多时候需要把时域信号波形变换到频域进行分析，这涉及到对信号求傅里叶变换，在计算机中便于处理的是离散信号，因此需要求信号的离散傅里叶变换，但是离散傅里叶变换（DFT--Discrete Fourier transform）的算法时间复杂度O(n2)，为了能提高计算的速度，很多时候我们进行的变换为快速傅里叶变换（FFT--Fast Fourier Transform），其算法时间复杂度O(nlogn)，大大提高了计算的速度，那么该快速傅里叶变换算法的快在哪里？中间进行了什么操作，我们下面具体分析。

在之前的一篇文章中我们提到了DFT和FFT的关系

频谱、功率谱、倒频谱_heda3的博客-CSDN博客_倒频谱

1、DFT算法

DFT的数学计算表达式为：

长度为N的离散时间信号x(n),做N点离散傅里叶变换如下：

$X(k)=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}kn}=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}$

其中k=0,1,2,...N-1

其中 $W_{N}=e^{-j2\frac{ \pi }{N}}$

运算量表述为：

依据上述公式可知，做1点DFT，需要N次复数乘法、N-1次复数加法

做N点DFT，则需要N*N次复数乘法、N*（N-1）次复数加法

当N为256点时，所需运算量65536次复数乘法、65280次复数加法

N=512点时，所需运算量262144次复数乘法、261632次复数加法

N=1024点时，所需运算量1048576次复数乘法、1047552次复数加法

可见当N点从256到1024点变化时，DFT算法的计算量从万级到百万级。

2、FFT算法

2.1 分类

分为按照时间抽取（在时间上将信号长度逐步减少）和按照频率抽取

依据抽取长度分为基2、基4

基2 DIT（时间抽取） FFT 也称为Cooley-Tukey algorithm 库利图基算法

基2 DIF（频率抽取） FFT

基4 FFT

分裂基FFT（包含两种不同基的混合计算）

2.2 以基2 DIT（时间抽取） FFT 算法为例

基于基2时间抽取将信号划分为两部分分别计算FFT（信号长度N要求为N=2的整数倍）：

$X(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}=\sum_{n=0}^{N/2-1}x(2n)W_{N}^{k2n}+\sum_{n=0}^{N/2-1}x(2n+1)W_{N}^{k(2n+1)}$ 1）

其中k=0,1,2,...N-1

复数运算的特性

$W_{N}^{kn}=e^{-j2\frac{ \pi }{N}kn}$

对称性：

$W_{N}^{nk}=W_{N}^{-nk}=W_{N}^{(N-n)k}$

周期性：

$W_{N}^{nk}=W_{N}^{(n+N)k}$

可约性：

$W_{N}^{nk}=W_{mN}^{mnk} =W_{N/m}^{nk/m}$

常见的计算

$W_{N}^{0}=1$

$W_{N}^{N/2}=-1$

$W_{N}^{N/4}=-j$