EE261 Lecture 22

课程主页：https://see.stanford.edu/Course/EE261

这次回顾第二十二讲，这一讲介绍了DFT的性质以及快速傅里叶变换。

DFT的性质

Parseval恒等式

$$\underline{\mathcal{F}} \mathrm{f} \cdot \underline{\mathcal{F}} \mathrm{g}=N(\mathrm{f} \cdot \mathrm{g})$$

证明：

$$\begin{aligned} \underline{\mathcal{F}} \mathrm{f} \cdot \underline{\mathcal{F}} \mathrm{g} &=\left(\sum_{k=0}^{N-1} \mathrm{f}[k] {\omega}^{-k}\right) \cdot\left(\sum_{\ell=0}^{N-1} \mathrm{g}[\ell] \omega^{-\ell}\right)\\ &=\sum_{k=0}^{N-1} \sum_{\ell=0}^{N-1} \mathrm{f}[k] \overline{\mathrm{g}[\ell]}\left(\omega^{-k} \cdot \omega^{-\ell}\right)\\ &=N \sum_{k=0}^{N-1} \mathrm{f}[k] \overline{\mathrm{g}[k]}\\ &=N(\mathrm{f} \cdot \mathrm{g}) \end{aligned}$$

特别的，取$\mathrm{f}=\mathrm{g}$，那么

$$\|\mathcal{F} \mathrm{f}\|^{2}=N\|\mathrm{f}\|^{2}$$

平移和平移定理

定义

$$\tau_{p} \mathrm{f}[n]=\mathrm{f}[n-p]$$

那么

$$\begin{aligned} \underline{\mathcal{F}}\left(\tau_{p} \mathrm{f}\right)[m] &= \sum_{k=0}^{N-1} \tau_{p} \mathrm{f}[k] w^{-k m}\\ &= \sum_{k=0}^{N-1} \mathrm{f}[k-p]w^{-k m}\\ &=w^{-pm} \sum_{k=0}^{N-1} \mathrm{f}[k-p]w^{-(k-p) m}\\ &= w^{-pm} \underline{\mathcal{F}} \mathrm{f}[m] \end{aligned}$$

因此

$$\underline{\mathcal{F}}\left(\tau_{p} \mathrm{f}\right)={\omega}^{-p} \underline{\mathcal{F}} \mathrm{f}$$

modulation定理

考虑

$$\begin{aligned} \omega^{n} \mathrm{f} &=\left(1,w^{n}, w^{2 n}, \ldots,w^{(N-1) n}\right)(\mathrm{f}[0], \mathrm{f}[1], \mathrm{f}[2], \ldots, \mathrm{f}[N-1]) \\ &=\left(\mathrm{f}[0], w^{n} \mathrm{f}[1], w^{2 n} \mathrm{f}[2], \ldots, w^{(N-1) n} \mathrm{f}[N-1]\right) \end{aligned}$$

由定义可得

$$\underline{\mathcal{F}}\left({\omega}^{n} \mathrm{f}\right)=\sum_{k=0}^{N-1} \mathrm{f}[k] w^{k n} {\omega}^{-k}$$

第$m$个分量为

$$\underline{\mathcal{F}}\left({\omega}^{n} \mathrm{f}\right)[m]=\sum_{k=0}^{N-1} \mathrm{f}[k] w^{k n} {w}^{-k m}=\sum_{k=0}^{N-1} \mathrm{f}[k] w^{-k(m-n)}$$

对$\underline{\mathcal{F}}\left({\omega}^{n} \mathrm{f}\right)$平移$n$个单位可得

$$\tau_{n}(\underline{\mathcal{F}} \mathrm{f})=\tau_{n}\left(\sum_{k=0}^{N-1} \mathrm{f}[k] {\omega}^{-k}\right)=\sum_{k=0}^{N-1} \mathrm{f}[k] \tau_{n} {\omega}^{-k}$$

上式右边第$m$个分量为

$$\left(\sum_{k=0}^{N-1} \mathrm{f}[k] \tau_{n} \omega^{-k}\right)[m]=\sum_{k=0}^{N-1} \mathrm{f}[k]\left(\tau_{n} \omega^{-k}\right)[m]=\sum_{k=0}^{N-1} \mathrm{f}[k]w^{-k(m-n)}$$

我们得到

$$\mathcal{F}\left({\omega}^{n} \mathrm{f}\right)=\tau_{n}(\underline{\mathcal{F}} \mathrm{f})$$

卷积

定义

$$(\mathrm{f} * \mathrm{g})[m]=\sum_{k=0}^{N-1} \mathrm{f}[k] \mathrm{g}[m-k]$$

在上述定义下，我们有

$$\underline{\mathcal{F}}(\mathrm{f} * \mathrm{g})=(\underline{\mathcal{F}} \mathrm{f})(\underline{\mathcal{F}} \mathrm{g})$$

利用卷积，我们可得

$$\mathcal{F}(\mathrm{fg})=\frac{1}{N}(\underline{\mathcal{F}} \mathrm{f} * \underline{\mathcal{F}} \mathrm{g})$$

证明：

令

$$\begin{aligned} \mathrm{F}&=\underline{\mathcal{F}}^{-1} \mathrm{f}\\ \mathrm{G}&=\underline{\mathcal{F}}^{-1} \mathrm{g} \end{aligned}$$

那么

$$\mathrm{f}=\underline{\mathcal{F}} \mathrm{F}, \mathrm{g}=\underline{\mathcal{F}} \mathrm{G}$$

所以

$$\mathrm{fg}=(\underline{\mathcal{F}} \mathrm{F})(\underline{\mathcal{F}} \mathrm{G})=\underline{\mathcal{F}}(\mathrm{F} * \mathrm{G})$$

因此

$$\begin{aligned} \underline{\mathcal{F}}(\mathrm{f} \mathrm{g}) &=\underline{\mathcal{F}}\underline{\mathcal{F}}(\mathrm{F} * \mathrm{G})\\ &=N(\mathrm{F} * \mathrm{G})^{-}\\ &=N\left(\frac{1}{N}(\underline{\mathcal{F}} \mathrm{f})^{-} * \frac{1}{N}(\underline{\mathcal{F}} \mathrm{g})^{-}\right)^{-}\\ &=\frac{1}{N}(\underline{\mathcal{F}} \mathrm{f} * \underline{\mathcal{F}} \mathrm{g}) \end{aligned}$$

平移和卷积

类似连续情形，我们有

$$\begin{aligned} \left(\left(\tau_{p} \mathbf{f}\right) * \mathbf{g}\right)[n] &=\sum_{k=0}^{N-1} \tau_{p} \mathbf{f}[n-k] \mathbf{g}[k] \\ &=\sum_{k=0}^{N-1} \mathbf{f}[n-k-p] \mathbf{g}[k] \\ &=(\mathbf{f} * \mathbf{g})[n-p]\\ &=\tau_{p}(\mathbf{f} * \mathbf{g})[n] \end{aligned}$$

所以

$$\left(\tau_{p} \mathbf{f}\right) * \mathbf{g}=\tau_{p}(\mathbf{f} * \mathbf{g})=\mathbf{f} *\left(\tau_{p} \mathbf{g}\right)$$

$\delta $的更多性质

考虑$\delta $的乘法

$$\mathrm{f} \delta_{0}=(\mathrm{f}[0] \cdot 1, \mathrm{f}[1] \cdot 0, \ldots, \mathrm{f}[N-1] \cdot 0)=(\mathrm{f}[0], 0, \ldots, 0)=\mathrm{f}[0] \delta_{0}$$

对于卷积

$$\left(\mathrm{f} * \delta_{0}\right)[m]=\sum_{n=0}^{N-1} \mathrm{f}[m-n] \delta_{0}[n] =\mathrm f[m] \Rightarrow \left(\mathrm{f} * \delta_{0}\right) = \mathrm f$$

类似的，我们有

$$\begin{aligned} \mathrm{f} \delta_{k}&=\mathrm{f}[k] \delta_{k}\\ \mathbf{f} * \delta_{k} &=\mathbf{f} * \tau_{k}\delta_{0}\\ &=\tau_{k}\left(\mathbf{f} * \delta_{0}\right)\\ &=\tau_{k} \mathbf{f} \end{aligned}$$

考虑特殊情形，$f$也为$\delta $函数：

$$\begin{aligned} \delta_{p} \delta_{q}&=\left\{\begin{array}{ll}{\delta_{p}} & {p=q} \\ {0} & {p \neq q}\end{array}\right.\\ \delta_{p} * \delta_{q}&=\delta_{p+q} \end{aligned}$$

FFT算法

我们知道计算DFT需要$O(n^2)$的计算量，当$n$很大时显然不够高效，有没有方法可以减少计算量呢？FFT就是起到这样作用的算法，其计算量为$O(n\log n)$，下面简单介绍该算法的思想。

一些记号

定义

$$\omega[p, q]=\omega_{p}^{q}$$

那么

$$\omega[N / 2,-1]=e^{-2 \pi i /(N / 2)}=e^{-4 \pi i / N}=\omega[N,-2]$$

更一般的，我们有

$$\omega[N,-2 n m]=\omega[N / 2,-n m]$$

对于第二项为奇数的情形，我们有

$$\omega[N,-(2 n+1) m]=\omega[N,-m] \omega[N / 2,-n m]$$

最后考虑一种特殊情形

$$\omega[N,-N/2]=e^{(-2\pi i/N) (N/2)} =e^{-\pi i}= -1$$

划分求和

为了简化讨论，这里假设$N$为偶数，那么

$$\begin{aligned} \mathbf{F}[m] &=\sum_{n=0}^{N-1} \mathbf{f}[n] \omega[N,-n m] \\ &=\sum_{n=0}^{N / 2-1} \mathbf{f}[2 n] \omega[N,-(2 n) m]+\sum_{n=0}^{N / 2-1} \mathrm{f}[2 n+1] \omega[N,-(2 n+1) m] \end{aligned}$$

利用之前的内容对上式分别处理得到

$$\begin{aligned} \mathbf{F}[m] &=\sum_{n=0}^{N / 2-1} \mathbf{f}[2 n] \omega[N / 2,-n m]+\sum_{n=0}^{N / 2-1} \mathbf{f}[2 n+1] \omega[N / 2,-n m] \omega[N,-m] \\ &=\sum_{n=0}^{N / 2-1} \mathbf{f}[2 n] \omega[N / 2,-n m]+\omega[N,-m] \sum_{n=0}^{N / 2-1} \mathbf{f}[2 n+1] \omega[N / 2,-n m] \end{aligned}$$

于是我们得到下式

$$\mathbf{F}[m]=\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { even }}\right)[m]+\omega[N,-m]\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { odd }}\right)[m], \quad m=0,1, \ldots, N / 2-1$$

对于$N-1 \ge m\ge N/2$的情形，我们考虑$m + N/2, m=0,\ldots, N/2-1$即可，注意到

$$\omega[N / 2,-(m+N / 2) n]=\omega[N / 2,-m n] \omega[N / 2,-n(N / 2)]=\omega[N / 2,-m n]$$

对于奇数项，需要处理$\omega[N,-(m+N / 2)]$

$$\omega[N,-(m+N / 2)]=\omega[N,-m] \omega[N,-N / 2]=-\omega[N,-m]$$

所以

$$\mathbf{F}[m+N / 2]=\sum_{n=0}^{N / 2-1} \mathbf{f}[2 n] \omega[N / 2,-n m]-\omega[N,-m] \sum_{n=0}^{N / 2-1} \mathbf{f}[2 n+1] \omega[N / 2,-n m]$$

总结

将上述内容总结，我们得到FFT算法

$$\begin{aligned} \mathbf{F}[m] &=\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { even }}\right)[m]+\omega[N,-m]\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { odd }}\right)[m] \\ \mathbf{F}[m+N / 2] &=\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { even }}\right)[m]-\omega[N,-m]\left(\underline{\mathcal{F}}_{N / 2} \mathbf{f}_{\text { odd }}\right)[m] \end{aligned}$$

其中$m=0,1, \ldots, N / 2$