1. 快速傅立叶变换 （Fast Fourier Transform, FFT）

傅里叶变换

首先，什么是傅里叶变换，复变中都会讲到，先来复习一下。 [^2] [1]

傅立叶变换，表示 将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。

(1) 定义

$f(t)$是周期函数，而且满足狄利赫里条件(Dirichlet conditions) ,那么可以函数的 $f(t)$ 的傅里叶变换F(w)存在。

狄利赫里条件  
(1) 函数在任意有限区间内连续，或只有有限个第一类间断点
(2) 在一个周期内，函数有有限个极大值或极小值
(3) $$f(t)$$ 在单个周期内绝对可积,即 $$ \int_{0}^{T} f(t) dt $$
  • 许多情况下，傅里叶变换是可逆变换
  • f 是实数函数，而 $\hat f$ 则是复函数，用一个复数来表示振幅和相位
  • 一般情况下，若“傅里叶变换”一词不加任何限定语，则指的是“连续傅里叶变换”

最近看到一篇讲解傅立叶变换的知乎回答，讲的深入浅出，值得一看，原文如何理解傅里叶变换公式？，回答离线 备份

快速傅里叶变换

快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

FFT（Fast Fourier Transformation） 是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

$$A(x)*B(x)\
A(x)=a_0+a_1x+a_2x2+\cdots+a_{n-1}x{n-1}\
B(x)=b_0+b_1x+b_22+\cdots+b_{n-1}x{n-1}
$$

通常对A和B做卷积运算需要将A的每一系数和B的每一个系数进行一次相乘，通常需要$o(mn)$的复杂度，这样比较耗时。

这里讲一下卷积的定义,设:$f(x)$,$g(x)$是$R1$上的两个可积函数，作积分

参考文献：

  1. 傅里叶变换. wikipedia ↩︎