简明FFT公式

1. 傅里叶变换

$$F(\omega )={\int }_{?\infty }^{\infty }f(x)e^{?i\omega x}dx$$

2. 逆傅里叶变换

$$f(x)=\frac{1}{2\pi }{\int }_{?\infty }^{\infty }F(\omega )e^{i\omega x}d\omega$$

f(x)是一个关于时间t的函数，信号处理中代表信号值
F(ω)为信号在频域中的表示，描述原始函数f(t)在各个频率ω上的成分或强度
e^iωx/e^-iωx是旋转因子

3. 离散傅里叶变换（DFT）

$$A_k=\sum _{n=0}^{N?1}{e}^{?i\frac{2\pi }{N}kn}{a}_n$$

傅里叶变换针对连续信号，离散傅里叶DFT针对采样得到的离散信号
a_n表示第n个采样点处（或者说在时间n）信号的强度
A_k表示该信号在频率k上的强度或振幅
总的来说，a_n是输入信号的离散时间域表示，经过DFT后，将这个时域的表示转换为频域的表示A_k

DFT通常写作：
$$A_k=\sum _{n=0}^{N?1}{W}_N^{kn}{a}_n$$
其中，$W_N=e^{?i\frac{2\pi }{N}}$

$W_N^k$ ($k=0\dots N?1$) 通常被称为N次单位根。因为在复数运算中，${\left(W_N^k\right)}^N=1$. 复平面上绘制的$N=2,N=4$, $N=8$的单位根分别如下所示：

4. 逆离散傅里叶变换（IDFT）

$$a_n=\frac{1}{N}\sum _{k=0}^{N?1}{W}_N^{?kn}{A}_k$$

其实就是换了个旋转因子

5. 快速傅里叶变换FFT

Cooley-Turkey算法是应用最广泛的FFT算法，采用分而治之的方法，将大DFT分解为小DFT，公式如下：

$$\begin{array}{rl}{A}_k& =\sum _{n=0}^{N?1}{a}_n{W}_N^{nk},k=0,1,?,N?1\\ & =\sum _{n=0}^{N/2?1}{a}_{2n}{W}_N^{2nk}+\sum _{n=0}^{N/2?1}{a}_{2n+1}{W}_N^{(2n+1)k}\\ & =\sum _{n=0}^{N/2?1}{a}_{2n}{W}_N^{2nk}+W_N^k\sum _{n=0}^{N/2?1}{a}_{2n+1}{W}_N^{2nk}\\ & =\sum _{n=0}^{N/2?1}{a}_{2n}{W}_{N/2}^{nk}+W_N^k\sum _{n=0}^{N/2?1}{a}_{2n+1}{W}_{N/2}^{nk}\\ & =F_k+W_N^k{G}_k,\\ F_k& =\sum _{n=0}^{N/2?1}{a}_{2n}{W}_{N/2}^{nk},G_k=\sum _{n=0}^{N/2?1}{a}_{2n+1}{W}_{N/2}^{nk},k=0,1,?,\frac{N}{2}?1\end{array}$$

由此将长度为N的DFT分解为两个长度为N/2的DFT，但是仅能得到前一半频率对应的结果
而由$W_{N/2}^{nk}=W_{N/2}^{n(k+N/2)},W_N^{nk}=?W_N^{n(k+N/2)}$，可得$F_{k+\frac{N}{2}}=F_k,G_{k+\frac{N}{2}}=G_k$，即：

$$\begin{array}{rl}{A}_{k+\frac{N}{2}}& =F_{k+\frac{N}{2}}+W_N^{k+\frac{N}{2}}{G}_{k+\frac{N}{2}},k=0,1,?,\frac{N}{2}?1\\ & =F_k?W_N^k{G}_k\end{array}$$

DFT时间复杂度为$O(N^2)$，FFT时间复杂度为$O(Nlo{g}_{2}N)$

当FFT处理的离散序列长度为1，可以发现如下蝶形运算

蝶形运算组合成蝶形网络，以N=8的FFT为例：

IFFT同理，换个旋转因子即可

$$————————————————————————————————$$

参考： Fourier transforms and the fast Fourier transform (FFT) algorithm