前言

对于学通信的人来说，在学到数字信号处理时都会学到一个东东，叫做快速傅里叶变换(Fast Fourier Transform,简称FFT)。这东西真的挺有用的，但是只要有那么一点用的东西，就是特别难的。(现在也有很多不完整的地方，以后再补充~)

什么是FFT

FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步

FFT是一种用来计算DFT（离散傅里叶变换）和IDFT（离散傅里叶反变换）的一种快速算法。这种算法运用了一种高深的数学方式、把原来复杂度为O(n2)" role="presentation">O(n2)$O(n^2)$
的朴素多项式乘法转化为了O(nlogn)" role="presentation">O(nlogn)$O(nlogn)$的算法。 首先上DFT的公式，下面将由这个公式一步步推出FFT的算法。 X[k]=∑n=0N−1x[n]∗e−i2πkNn" role="presentation">X[k]=∑N−1n=0x[n]∗e−i2πkNn$X[k]=\sum _{n=0}^{N-1}x[n]\ast e^{-i2\pi k{N}_n}$ 它其实就是针对离散的采样点 x[n]的傅里叶变换，其意义还是将信号从时域转换到频域。那么这里的 X[k] 表示的就是频域信号了，下标k表示信号的频率， X[k] 的值就是该频率信号的幅值。这里可以看到，当k固定的时候，对应于频率为k的信号幅值是与 x[n]有关的一个级数的和，因此每一个频域的点实际上包含了所有时域点的信息。 有两点需要注意，一是因为 x[n]的长度为 N ，因此 DFT 后的频域信号 X[k] 的长度也是 N；二是为了进行FFT变换，N的取值一般是2的整数次幂。 将下标n分解为奇偶两部分，然后分别求和 X[k]=∑r=0N2−1x[2r]∗e−i2πkN2r+∑r=0N2−1x[2r+1]∗e−i2πkN(2r+1)" role="presentation">X[k]=∑N2−1r=0x[2r]∗e−i2πkN2r+∑N2−1r=0x[2r+1]∗e−i2πkN(2r+1)$X[k]=\sum _{r=0}^{\frac{N}{2}-1}x[2r]\ast e^{-i2\pi k{N}_{2r}}+\sum _{r=0}^{\frac{N}{2}-1}x[2r+1]\ast e^{-i2\pi k{N}_{(2r+1)}}$ 这里进行一次代换，用 x0[n]" role="presentation">x0[n]$x_0[n]$表示 x[n] 中的偶数项，用 x1[n]" role="presentation">x1[n]$x_1[n]$ 表示 x[n] 中的奇数项 X[k]=∑n=0N2−1x0[n]∗e−i2πkN/2n+∑n=0N2−1x1[n]∗e−i2πkN/2n−i2πkN" role="presentation">X[k]=∑N2−1n=0x0[n]∗e−i2πkN/2n+∑N2−1n=0x1[n]∗e−i2πkN/2n−i2πkN$X[k]=\sum _{n=0}^{\frac{N}{2}-1}{x}_0[n]\ast e^{-i\frac{2\pi k}{N/2}n}+\sum _{n=0}^{\frac{N}{2}-1}{x}_1[n]\ast e^{-i\frac{2\pi k}{N/2}n-i\frac{2\pi k}{N}}$ 第二项求和中，e−i2πkN" role="presentation">e−i2πkN$e^{-i\frac{2\pi k}{N}}$ 与 n 无关，因此可以单独提出 对x0[n]" role="presentation">x0[n]$x0[n]$进行DFT
X[k]=∑n=0N2−1x0[n]e−i2πkN/2n" role="presentation">X[k]=∑N2<