Qian's Blog HOME CATEGORY REFERENCE ABOUT

信号处理之浅见（三）：快速傅里叶变换

离散傅里叶变换(DFT, Discrete Fourier Transform)

至今，我们已经讨论了四种形式的傅里叶变换，但是如果在计算机上进行信号处理的时候会发现，这四种形式都难以操作。计算机只能处理离散且有限长的信号，因此信号的时域和频域必须是离散的、而且个数有限。

观察四种傅里叶变换发现，只有DFS的时域和频域是离散的，但是却是无限长的。所幸，DFS的时域和频域都是以N为周期的。若对DFS的时域和频域信号只取其中一个周期，就成为了离散傅里叶变换对，也就是DFT和iDFT。

$\ X(k)=\sum_{n=0}^{N-1} x(n)e^{-jk\omega_0n},k=0,1,2,...,N-1$

$\ x(n)=\frac{1}{N}\sum_{k=0}^{N-1} X(k) e^{jk\omega_0n},n=0,1,2,...,N-1$

显然，现实中遇到的信号有可能是非周期的，既有可能是有限长也可能是无限长序列。对于有限长非周期信号，只需要进行延拓即可；对于无限长非周期信号，只需要截取一定长度在进行延拓即可。

但是有一个问题摆在眼前，根据上述公式，计算一个X(k)就需要N次复数乘法，求N个点就需要N*N次复数乘法，当N很大的时候，这种计算了基本上是不可实现的，好在有一种算法把如此复杂度的计算量降为(Nlog2N)/2次，从而使DFT在信号处理中成为最重要也最方便的运算，这就是接下来要讲的FFT算法。

快速傅里叶变换(FFT, Fast Fourier Transformation)

改写如上两式：

$\ X(k)=\sum_{n=0}^{N-1} x(n)W^{nk}_N,k=0,1,2,...,N-1$

$\ x(n)=\frac{1}{N}\sum_{k=0}^{N-1} X(k)W^{-nk}_N,n=0,1,2,...,N-1$

其中

$\ W^{nk}_N=e^{-jk\omega_0n}=e^{-jk\frac{2\pi}{N}n}$

将DFT写成矩阵形式有：

$\ \begin{bmatrix} X(0)\\X(1)\\...\\X(N) \end{bmatrix}=\begin{bmatrix} W^{00}&W^{10}&...&W^{N0}\\W^{01}&W^{11}&...&W^{N1}\\...&...&...&...\\W^{0N}&W^{1N}&...&W^{NN} \end{bmatrix} \begin{bmatrix} x(0)\\x(1)\\...\\x(N) \end{bmatrix}$

不难发现，W的取值有一些特点：

W^(0) = 1
W^(N/2) = -1
W^(N+r) = W^r
W^(N/2+r) = -W^r

利用W因子的周期性和对称性以及如上的性质，可以导出一个高效的快速算法。事实上早在1965年，J.W.Cooley和J.W.Tukey就提出了这一算法，从那时起，新的算法层出不穷，一种是针对N等于2的整数次幂的算法，如基2、基4、实因子、分裂基等算法，另一种是针对N不等于2的整数次幂的算法，如素因子、Winograd等算法。