关于FFT (Fast - Fourier Transformation) 快速傅里叶变换

FunnyWii
FunnyWii
发布于 2022-07-28 / 22 阅读
0
0

关于FFT (Fast - Fourier Transformation) 快速傅里叶变换

傅里叶变换

傅里叶的原理说明:任何连续测量的时序或信号,都可以用不同频率的正弦波信号的无限叠加来表示。
在数学的角度来看,傅里叶变换算法利用直接测量得到的初始信号,用累加的方式来计算该初始信号中不同正弦波信号的频率,幅值和相位。
而从物理学的角度来看,傅里叶变换可以帮助我们将时域的信号转为频域来分析。有些在时域上很难分析的一些信号,在被转换到频域后,更容易找到其特征。此外,频谱也可以通过傅里叶变换得出。下图可以更好理解时域到频域的转换:

FFT.png

Figure1 从时域到频域的变化

傅里叶变换的4种类型

  1. 非周期性连续信号傅立叶变换(Fourier Transform)
  2. 周期性连续信号傅立叶级数 (Fourier Series)
  3. 非周期性离散信号离散时域傅立叶变换(Discrete Time Fourier Transform)
  4. 周期性离散信号离散傅立叶变换 (Discrete Fourier Transform, DFT)

FFT4.png

Figure2 四种变换类型

快速傅里叶变换

因为计算机只能处理离散数值信号,因此只有周期性离散信号离散傅立叶变换 (Discrete Fourier Transform, DFT) 适用。FFT也是DFT的一种快速算法。DFT运算过程如下:

X(k)=\frac 1N\sum_{n=0}^{N-1} x(n)e^{-j2\pi nk/N}

其中,
X(k) - 频域的值
x(n) -时域的采样点
n - 时域采样点的序列索引
k - 频域值的索引
N - 采样点数量

对于在毕设中出现的平面曲线的descriptor, X(k)Y(k) 分别代表 x 轴和 y 轴的坐标。

S(k) = X(k) + jY(k)
a(u)=\sum_{k=0}^{K-1} s(k)e^{-juk2\pi/K}

其中,
a(u) - 频域的值
s(k) - 复数表示的平面坐标点k
k - 点的索引
u - 频域值的索引
K - 曲线中的总点数

快在哪?

由公式可以看出,DFT后的输出包含与输入数量相同的采样点,但是有一半是冗余的,实际上只有 \frac N2 +1个点包含有用信息。
FFT相比DFT,原本时间复杂度为N^2的运算,变成了N\lg{N}

快速算法实现举例

以下式为例

X(k) = \frac14 \sum^{3}_{n=0} x(n) e^{-j2\pi nk/4}
X(0) = \textcolor{#FF0000}{x(0)e^{-j0} + x(1)e^{-j0} +x(2)e^{-j0} + x(3)e^{-j0}}
X(1) = x(0)e^{-j0} + \textcolor{#FF0000}{x(1)e^{-j\pi /2} + x(2)e^{-j\pi} +x(3)e^{-j3\pi /2}}
X(2) = x(0)e^{-j0} + x(1)e^{-j\pi} + x(2)e^{-j2\pi} +x(3)e^{-j3\pi}
X(3) = x(0)e^{-j0} + x(1)e^{-j3\pi / 2} + x(2)e^{-j3\pi} +x(3)e^{-j9\pi /2}

红色部分是在FFT中需要计算的分量,其他部分不需要计算 (简单的弧度关系 - e^{i\theta}),可以由红色部分推导得出:

x(1)e^{-j0} = -x(1)e^{-j\pi}
x(2)e^{-j0} = x(2) e^{-j2\pi}

变换前后信号的对应关系

原始信号幅值A,FFT结果的每个点(除第一个直流分量外),幅值就是 A\frac N2 倍。直流(DC)分量,也就是第一个点 (0Hz),他的幅值是直流分量的 N 倍。
每个点的相位,就是该频率下的信号的相位。
从第一个点(直流分量)到最后一个点N表示采样频率,这个区间被 N-1 个点分成 N 等份,每个点的频率以此增加。F_n = (n-1) \times \frac {F_s}N。在某个点 n 处所能分辨的频率\frac {Fs}NF_s 为采样频率, N 为采样点数。

FFT3.png

Figure3 FFT变换后信号的变化

参考文献

[1] FFT的物理意义 avaliable @7/28/2022
[2] 数字图像处理中的傅里叶(DFT/FFT) avaliable @7/28/2022


评论