傅里叶变换

傅里叶变换是将信号从时域变换为频域的工具。直观来说，傅里叶变换可以提取一段音频的频率信息。

定义

傅里叶变换一般定义如下，设有模拟信号 $f(t)f(t)$，则其傅里叶变换为：

$$\mathcal{F}\{f\}(\omega )=F(\omega )={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}f(t)e^{-i\omega t}\mathrm{d}t\backslash mathcal\{F\}\backslash \{f\backslash \}(\backslash omega)\; =\; F(\backslash omega)\; =\; \backslash int\_\{-\backslash infty\}^\{+\backslash infty\}f(t)e^\{-i\; \backslash omega\; t\}\; \backslash mathrm\{d\}t$$

这一过程看作 $L^{2}L^2$ 空间上将 $f(t)f(t)$ 投影到正交基底 $e^{-i\omega t}e^\{-i\; \backslash omega\; t\}$ 上的过程。而因为 $e^{-i\omega t}=\cos \omega t-i\sin \omega te^\{-i\backslash omega\; t\}\; =\; \backslash cos\; \backslash omega\; t\; -\; i\; \backslash sin\; \backslash omega\; t$，从而我们可以认为傅里叶变换提取了频率为 $f=\frac{\omega }{2\pi }f\; =\; \backslash frac\{\backslash omega\}\{2\backslash pi\}$ 的频率分量. $\mathrm{\mid }\mathcal{F}\{f\}(\omega )\mathrm{\mid }|\backslash mathcal\{F\}\backslash \{f\backslash \}(\backslash omega)|$ 表示频率为 $ff$ 的分量的“音量”大小，$\arg \mathcal{F}\{f\}(\omega )\backslash arg\; \backslash mathcal\{F\}\backslash \{f\backslash \}(\backslash omega)$ 则表示频率为 $ff$ 的分量的相位。

这一过程因为基函数正交且完备，故可逆。其逆变换为：

$${\mathcal{F}}^{-1}\{F\}(t)=\frac{1}{2\pi }{\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}F(\omega )e^{-i\omega t}\mathrm{d}\omega \backslash mathcal\{F\}^\{-1\}\backslash \{F\backslash \}(t)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash infty\}^\{+\backslash infty\}F(\backslash omega)e^\{-i\; \backslash omega\; t\}\; \backslash mathrm\{d\}\backslash omega$$

这一过程可以理解为从正交基底重建原函数的过程。

离散傅里叶变换

在实践过程中，因为数字音频流是离散的，一般使用傅里叶变换的离散版替代 (Discrete Fourier Transform, 简称 DFT)，即离散傅里叶变换。假设原始信号是 $x[n]x[n]$，则定义其离散傅里叶变换为

$$\mathrm{DFT}(x)[k]=X[k]=\sum _{n=0}^{N-1}x[n]e^{-i\frac{2\pi }{N}kn}\backslash operatorname\{DFT\}(x)[k]\; =\; X[k]\; =\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{N\; -\; 1\}\; x[n]\; e^\{-i\backslash frac\{2\backslash pi\}\{N\}\; kn\}$$

其中 $NN$ 为原始信号的采样点个数，其具体意义与连续傅里叶变换一致。但因为信号离散的缘故，频率计算与采样率 $f_{s}f\_s$ 与指标 $kk$ 有关，具体计算方式为 $k\frac{f_s}{N}k\backslash frac\{f\_s\}\{N\}$。

同理，这一过程同样可逆，其逆变换即为离散傅里叶变换逆变换 (Inverse Discrete Fourier Transform, 简称 IDFT)

$$\mathrm{IDFT}(X)[n]=x[n]=\frac{1}{N}\sum _{k=0}^{N-1}X[k]e^{-i\frac{2\pi }{N}kn}\backslash operatorname\{IDFT\}(X)[n]\; =x[n]\; =\; \backslash frac\{1\}\{N\}\backslash sum\backslash limits\_\{k=0\}\; ^\; \{N\; -\; 1\}\; X[k]\; e^\{-i\backslash frac\{2\backslash pi\}\{N\}\; kn\}$$

快速傅里叶变换

在实践中，不难发现按照原定义计算 DFT 的时间复杂度为 $o(N^2)o(N^2)$，这在实时计算中显然效率偏低，因此实践中一般使用分治方式进行优化，即为快速傅里叶变换 (Fast Fourier Transform, 简称 FFT)。以正向傅里叶变换为例（反向同理），其过程如下

首先写出离散傅里叶变换定义式

$$X[k]=\sum _{n=0}^{N-1}x[n]e^{-i\frac{2\pi }{N}kn}X[k]\; =\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{N\; -\; 1\}\; x[n]\; e^\{-i\backslash frac\{2\backslash pi\}\{N\}\; kn\}$$

将其按照奇偶项分离有

$$X[k]=\sum _{n=0}^{\frac{N}{2}-1}{x}_{2n}{e}^{-\frac{2k(2n)\pi }{N}i}+\sum _{n=0}^{\frac{N}{2}-1}{x}_{2n+1}{e}^{-\frac{2k(2n+1)\pi }{N}i}X[k]\; =\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\}\; e^\{-\backslash frac\{2k(2n)\backslash pi\}\{N\}i\}\; +\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\; +\; 1\}\; e^\{-\backslash frac\{2k(2n+\; 1)\backslash pi\}\{N\}i\}$$

即

$$X[k]=\sum _{n=0}^{\frac{N}{2}-1}{x}_{2n}{e}^{-\frac{2kn\pi }{N\mathrm{/}2}i}+e^{\frac{-2k\pi }{N}i}\sum _{n=0}^{\frac{N}{2}-1}{x}_{2n+1}{e}^{-\frac{2kn\pi }{N\mathrm{/}2}i}X[k]\; =\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\}\; e^\{-\backslash frac\{2kn\backslash pi\}\{N/2\}i\}\; +\; e^\{\backslash frac\{-2k\backslash pi\}\{N\}i\}\; \backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\; +\; 1\}\; e^\{-\backslash frac\{2kn\backslash pi\}\{N/2\}i\}$$

而 ${\sum }_{n=0}^{\frac{N}{2}-1}{x}_{2n}{e}^{-\frac{2kn\pi }{N\mathrm{/}2}i}\backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\}\; e^\{-\backslash frac\{2kn\backslash pi\}\{N/2\}i\}$ 和 ${\sum }_{n=0}^{\frac{N}{2}-1}{x}_{2n+1}{e}^{-\frac{2kn\pi }{N\mathrm{/}2}i}\backslash sum\backslash limits\_\{n=0\}\; ^\; \{\backslash frac\{N\}\{2\}\; -\; 1\}\; x\_\{2n\; +\; 1\}\; e^\{-\backslash frac\{2kn\backslash pi\}\{N/2\}i\}$ 是采样点为 $\frac{N}{2}\backslash frac\{N\}\{2\}$ 的傅里叶变换。从而当 $NN$ 为 $22$ 的幂次时，可以对原问题进行分治，其时间复杂度为 $o(N\log N)o(N\backslash log\; N)$.