FFT快速傅里叶变换

FFT提出的意义

FFT（Fast Fourier Transform）是DFT的高效算法，大幅减少了计算量。

直接计算 $N$ 点DFT需要 $N^{2}$ 次复数乘法和 $N (N - 1)$ 次复数加法。
FFT利用旋转因子 $W_{N}^{kn}$ 的对称性和周期性，将运算量降至 $O (N lo g_{2} N)$ 。
以 $N = 1024$ 为例：DFT需约 $1 0^{6}$ 次乘法，FFT仅需约 $5000$ 次，速度提升200倍。

基2时间抽取FFT（DIT-FFT）

基本思想

将 $N$ 点序列按奇偶分解为两个 $N /2$ 点子序列，递归进行直到2点DFT。
利用旋转因子的性质合并子问题结果。

分解过程

$x [n]$ 按 $n$ 的奇偶分为 $x [2 r]$ 和 $x [2 r + 1]$ 。
$N$ 点DFT表示为两个 $N /2$ 点DFT的组合： $X [k] = G [k] + W_{N}^{k} H [k], k = 0, \dots, N /2 - 1$ $X [k + N /2] = G [k] - W_{N}^{k} H [k], k = 0, \dots, N /2 - 1$ 其中 $G [k] = DFT {x [2 r]}$ ， $H [k] = DFT {x [2 r + 1]}$ 。

蝶形运算

每个蝶形单元完成一次复数乘法和两次复数加法： $X_{a} = A + W_{N}^{k} B$ $X_{b} = A - W_{N}^{k} B$
蝶形单元的图形表示形似蝴蝶，故得名。
$N = 2^{M}$ 时，FFT共有 $M = lo g_{2} N$ 级，每级 $N /2$ 个蝶形运算。

运算量分析

算法	复数乘法次数	复数加法次数
DFT	$N^{2}$	$N (N - 1)$
FFT（基2）	$(N /2) lo g_{2} N$	$N lo g_{2} N$

$N = 1024$ ：DFT需1,048,576次乘法；FFT仅需5,120次。
运算效率比： $N^{2} / (N /2) lo g_{2} N = 2 N / lo g_{2} N$ ，随 $N$ 增大而显著提升。

频率抽取FFT（DIF-FFT）

与DIT-FFT对称：按频率的奇偶分解，而非按时间。
将序列 $x [n]$ 分为前后两半，而不是按奇偶索引。
蝶形结构不同：DIF使用 $W_{N}^{k}$ 在蝶形之后，而DIT在之前。
两者的运算量和复杂度相同，只是流图结构略有差异。

IFFT（快速傅里叶逆变换）

IFFT的计算结构与FFT完全相同。
利用DFT性质：将 $X [k]$ 取共轭，做FFT后再取共轭并除以 $N$ ： $x [n] = \frac{1}{N} [FFT {X^{*} [k]}]^{*}$
因此可用同一套硬件/软件实现FFT和IFFT。

链接到

上一个知识点：8.1 DFT离散傅里叶变换
下一个知识点：8.3 信号流图