FFT

虽说 DFT 不需要像 DTFT 那样算无穷多项了,但要算的东西也是挺多的,我们来分析一下复杂度:

要计算出 $N$ 个 $X[k]$,必须进行 $N^2$ 次复数乘法和 $N(N-1)$ 次复数加法,时间复杂度为 $O(N^2)$。

假如有一个 44.1 kHz 采样率的 1s 音频,那么乘法的运算量大约是 1.94G,而现在的计算机处理速度也就 3~5GHz,也就是说 1s 也就算个几次 DFT,要是换以前的 CPU,估计得算一个星期😓。

但我们可以利用 DFT 中 $W_N^{kn}$ 的一些特殊性质来简化计算。比如说:$W_N^{k+\frac{N}{2}}=-W_N^k$,这样的话就可以减少一半的运算量,但时间复杂度还是 $O(N^2)$。如果用上其他性质,就能在 $O(n\log n)$ 时间内求出来,就得到我们的 FFT 算法。

基-2 FFT

DIT-FFT 算法

按时间抽取 FFT 算法(DIT-FFT,Decimation In Time FFT),也叫 Cooley-Tukey Fast Fourier Transform,是 1965 年由 Cooley 和 Tukey 提出,现在使用的大部分 FFT 都是在这个算法的基础上进行改进的。这个算法的步骤如下:

设序列 $x[n]$ 的长度 $N$ 是 $2$ 的幂,我们将 $x[n]$ 分解为偶数点和奇数点:

从而 $X[k]$ 可以分解为:

由于 $W_N^2=W_{N/2}$,所以(注意 $k$ 的取值范围):

根据 $W_N^{k+\frac{N}{2}}=-W_N^k$,如果要算 $X[k+\frac{N}{2}]$,易得:

总的来说,这是一次蝶形运算,运算量是 1 乘 2 加。

fft-butterfly

利用这个思想,我们可以进行递归:

每级的蝶形运算有 $N/2$ 个,每个蝶形运算包括一个复数乘法和两个加法,一共有 $\log_2 N$ 级,所以复杂度为 $O(N\log N)$

以 $N=8$ 为例:

计算流图 树形图
FFT-N=8-递归

我们来看看一个比较有趣的东西。将树形图中的编号写成二进制的形式:

$X_0=00\red0$ $X_1=00\red1$ $X_2=01\red0$ $X_3=01\red1$ $X_4=10\red0$ $X_5=10\red1$ $X_6=11\red0$ $X_7=11\red1$
$00\red0$
$01\red0$
$10\red0$
$11\red0$
$00\red1$
$01\red1$
$10\red1$
$11\red1$
$0\red00$
$1\red00$
$0\red10$
$1\red10$
$0\red01$
$1\red01$
$0\red11$
$1\red11$
$x_0=\red000$ $x_4=\red100$ $x_2=\red010$ $x_6=\red110$ $x_1=\red001$ $x_5=\red101$ $x_3=\red011$ $x_7=\red111$

注意到,从上往下先是按二进制的第1位分奇偶,然后再按第2位、第三位……,最终,使得最下面与最上面的二进制恰好“对称”,这称为 比特逆序

如果我们定义第 $r$ 级蝶形运算的输入是 $\Psi_r[\alpha]$ 和 $\Psi_r[\beta]$,并且特殊的,对于第一级,$\Psi_r[k]$ 对应的是比特逆序的 $k$,对于最后一级则是正常的 $k$。则每个蝶形运算可以表示为:

$\alpha$,$\beta$,$r$,$\ell$ 之间满足一些关系:

  1. $\alpha=a\cdot 2^r+b$,其中,$a=0,1,\cdots,N/2^r-1$,而 $b=0,1,\cdots,2^{r-1}-1$
  2. $\beta$ 与 $\alpha$ 一一对应,$\beta=\alpha+2^{r-1}$
  3. $\ell=b\cdot N/2^r$

我推导上面的式子只是为了好玩而已,课本中有库利-图基FFT算法的一般形式。考试中最好还是列计算流图。

DIF-FFT

按频率抽取(Decimation In Frequency)FFT 算法可以简单理解为 DIT-FFT 的翻转版。我们不将 $x[n]$ 进行奇偶分解,而是对 $X[k]$ 进行奇偶分解:

DIF-FFT 与 DIT-FFT 蝶形运算的对比如下:

8 点 FFT 的计算流图如下:

8-point-Radix-2-FFT-Decimation-in-frequency-form

注意到 $x[n]$ 是比特顺序,$X[k]$ 是比特逆序,这恰好与 DIT-FFT 相反。

算法实现

FFTW 是一个用于计算 DFT 的 C 语言库,它是开源的~

参考