EE261 Lecture 20 and Lecture 21

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

这次回顾第二十，二十一讲，这一讲介绍离散傅里叶变换的一些性质。

周期性

回顾DFT

$$\mathbf{F}[m]=\sum_{k=0}^{N-1} \mathbf{f}[k] \omega^{-k m}$$

注意到我们有

$$\omega^{-k(m+N)}=\omega^{-k m}$$

所以

$$\sum_{k=0}^{N-1} \mathrm{f}[k] \omega^{-k(m+nN)}=\sum_{k=0}^{N-1} \mathrm{f}[k] \omega^{-k m}=\mathbf{F}[m]$$

即

$$\mathbf{F}[m+n N]=\mathbf{F}[m]$$

所以$\mathbf F$可以延拓为周期为$N$的函数，从而我们有如下假设：

• 我们总是假设$\mathbf F$为周期为$N$的函数

类似的，我们还做出如下假设：

• 我们总是假设$\mathbf f$为周期为$N$的函数

利用周期性，我们不难得到

$$\underline{\mathcal{F} } \mathrm{f}=\sum_{k=p}^{p+N-1} \mathrm{f}[k] \omega^{-k}$$

常见函数的DFT

离散$\delta$

定义

$$\delta_{k}=(0, \ldots, 0,1,0, \ldots, 0)$$

其中第$k$个元素为$1$，那么我们有

$$\mathbf{f}=\sum_{k=0}^{N-1} \mathbf{f}[k] {\delta}_{k}$$

周期化$\delta_k $得到

$$\delta_{k}[m]= \left\{\begin{array}{ll}{1} & {m \equiv k \quad \bmod N} \\ {0} & {\text { otherwise } }\end{array}\right.$$

对$\delta_k $取离散傅里叶变换可得

$$\underline{\mathcal{F} } \delta_{k}=\sum_{n=0}^{N-1} \delta_{k}[n] \omega^{-n}=\omega^{-k}$$

特别的

$$\underline{\mathcal{F} } \delta_{0}=\omega^{0}=1$$

利用上述事实，我们得到

$$\mathbf{f}=\sum_{k=0}^{N-1} \mathbf{f}[k] \delta_{k} \Rightarrow \mathcal{F} \mathbf{f}=\sum_{k=0}^{N-1} \mathbf{f}[k] \underline{\mathcal{F} } \delta_{k}=\sum_{k=0}^{N-1} \mathbf{f}[k] {\omega}^{-k}$$

复指数的正交性

考虑

$${\omega}^{k}=\left(1, w^{k}, w^{2 k}, \ldots, w^{(N-1) k}\right)$$

我们有

$$\omega^{k} \cdot \omega^{\ell}=\left\{\begin{array}{ll}{0} & {k \not\equiv \ell \bmod N} \\ {N} & {k \equiv \ell \bmod N}\end{array}\right.$$

原因如下：

$$\begin{aligned} {\omega}^{k} \cdot {\omega}^{\ell} &=\sum_{n=0}^{N-1} {\omega}^{k}[n] \overline{ {\omega}^{\ell}[n]} \\ &=\sum_{n=0}^{N-1} {\omega}^{k}[n] {\omega}^{-\ell}[n] \\ &=\sum_{n=0}^{N-1} \omega^{k-\ell}[n] \quad \text { (ditto) } \\ &=\sum_{n=0}^{N-1} w^{(k-\ell) n}\\ &= \begin{cases} 0& k-\ell \not \equiv 0 \bmod N \\ {N} & {k-\ell \equiv 0 \bmod N} \end{cases}\\ &= \begin{cases} 0& k \not \equiv \ell \bmod N \\ {N} & {k \equiv \ell \bmod N} \end{cases}\\ \end{aligned}$$

其中倒数第二个等式是因为当$k\neq 0$时，

$$1+\omega^{k}+\omega^{2 k}+\ldots \omega^{(N-1) k}=\frac{1-\omega^{k N} }{1-\omega^{k} }=0$$

当$k=0$时，

$$1+\omega^{k}+\omega^{2 k}+\ldots \omega^{(N-1) k}=1+1+\ldots+1=N$$

复指数的DFT

考虑$\omega^k$的DFT

$$\underline{\mathcal{F} } {\omega}^{k}=\sum_{n=0}^{N-1} \omega^{k}[n] \omega^{-n}$$

第$\ell$个元素为

$$\begin{aligned} \mathcal{F} {\omega}^{k}[\ell] &=\sum_{n=0}^{N-1} \omega^{k}[n] {\omega}^{-n}[\ell] \\ &=\sum_{n=0}^{N-1} w^{k n} w^{-n \ell}\\ &=\omega^{k} \cdot \omega^{\ell}\\ &=\begin{cases} 0& k \not \equiv \ell \bmod N \\ {N} & {k \equiv \ell \bmod N} \end{cases}\\ &= N\delta_k \end{aligned}$$

反向信号和其DFT

定义

$$\mathrm{f}^{-}[m]=\mathrm{f}[-m]$$

利用$\mathbf f$周期为$N$，我们有

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

即

$$\mathbf{f}^{-}[n]=\mathbf{f}[N-n]$$

不难验证反向运算有如下性质

$$\begin{aligned} (\mathrm{f}+\mathrm{g})^{-}&=\mathrm{f}^{-}+\mathrm{g}^{-}\\ (\alpha \mathbf{f})^{-}&=\alpha \mathbf{f}^{-}\\ (\mathrm{fg})^{-}&=\left(\mathrm{f}^{-}\right)\left(\mathrm{g}^{-}\right) \end{aligned}$$

对于$\delta_k $，我们有

$$\begin{aligned} \delta_{k}^{-}[n] &= \delta_{k}[N-n]\\ &= \delta_{k}[-n]\\ &=\delta_{-k}[n] \end{aligned}$$

即

$$\delta_{k}^{-}=\delta_{-k}$$

特别的

$$\delta_{0}^{-}=\delta_{0}$$

利用上式记号，我们可得

$$\mathbf{f}^{-}=\left(\sum_{k=0}^{N-1} \mathbf{f}[k] \delta_{k}\right)^{-}=\sum_{k=0}^{N-1} \mathbf{f}[k] \delta_{-k}$$

接着讨论$\omega^{-}$，首先我们有

$${\omega}^{-}=({\omega}[N], {\omega}[N-1], {\omega}[N-2], \ldots, {\omega}[1])=\left(1, w^{N-1}, w^{N-1}, w^{N-2}, \ldots, w\right)$$

利用

$$w^{N-k} w^k =1 \Rightarrow w^{N-k} =w^{-k}$$

因此

$$\omega^{-}=\left(1,w^{-1}, w^{-2}, \ldots, w^{-(N-1)}\right)=\omega^{-1}$$

同理可得

$$\begin{aligned} \left(\omega^{k}\right)^{-}&=\omega^{-k} \\ \left(\omega^{-k}\right)^{-}&=\omega^{k} \end{aligned}$$

现在利用上式事实计算$\mathcal{F} \mathrm{f}^{-}$，实际上我们有

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

利用上述事实，我们有

$$\underline{\mathcal{F} } \omega^{-k}=\left(\underline{\mathcal{F} } \omega^{k}\right)^{-}=\left(N \delta_{k}\right)^{-}=N \delta_{-k}$$

现在对

$$\underline{\mathcal{F} } \mathrm{f}=\sum_{k=0}^{N-1} \mathrm{f}[k] \omega^{-k}$$

作用快速傅里叶变换，我们有

$$\mathcal{F} \underline{\mathcal{F} } \mathbf{f}=\sum_{k=0}^{N-1} \mathbf{f}[k] \underline{\mathcal{F} } {\omega}^{-k}=N \sum_{k=0} \mathbf{f}[k] {\delta}_{-k}=N \mathbf{f}^{-}$$

将上式性质总结如下：

• $\underline{\mathcal{F} } \mathrm{f}^{-}=(\underline{\mathcal{F} } \mathrm{f})^{-}$
• $\underline{\mathcal{F} } \mathcal{F} \mathrm{f}=N \mathrm{f}^{-}$

逆DFT

定义逆DFT为

$$\begin{aligned} \underline{\mathcal{F} }^{-1} \mathbf{f}&=\frac{1}{N} \mathcal{F} \mathrm{f}^{-}=\frac{1}{N} (\underline{\mathcal{F} } \mathbf{f})^{-}\\ \underline{\mathcal{F} }^{-1} \mathrm{f}&=\frac{1}{N} \sum_{n=0}^{N-1} \mathrm{f}[n] \omega^{n} \end{aligned}$$

我们来验证其合理性。

首先有

$$\begin{aligned} \underline {\mathcal{F} }^{-1} \omega^{-k} &=\frac{1}{N} \underline {\mathcal{F} }\left(\omega^{-k}\right)^{-} \\ &=\frac{1}{N} \underline {\mathcal{F} } \omega^{k} \\ &=\frac{1}{N} N \delta_{k}\\ &=\delta_{k} \end{aligned}$$

利用上式，我们可得

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

将逆变换写成分量形式得到

$$\underline{\mathcal{F} }^{-1} \mathbf{f}[n]=\frac{1}{N} \sum_{k=0}^{N-1} \mathrm{f}[k] \omega^{k n}$$

矩阵形式的逆DFT

利用复指数的正交性，不难得到

$$\underline{\mathcal{F} }^{*} \underline{\mathcal{F} }=\underline{\mathcal{F} }^T\underline{\mathcal{F} }=N I$$

所以

$$\underline{\mathcal{F} }^{-1}=\frac{1}{N} \mathcal{F}^{*} = \frac 1 N \underline{\mathcal{F} }^T =\frac 1 N \underline{\mathcal{F} }$$

即

$$\frac{1}{N} \underline{\mathcal{F} }^{*} =\frac{1}{N}\left(\begin{array}{ccccc}{1} & {1} & {1} & {\cdots} & {1} \\ {1} & {\omega^{1} } & {\omega^{2} } & {\cdots} & {\omega^{(N-1)} } \\ {1} & {\omega^{2} } & {\omega^{4} } & {\cdots} & {\omega^{2(N-1)} } \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {1} & {\omega^{(N-1)} } & {\omega^{2(N-1)} } & {\dots} & {\omega^{(N-1)^{2} }}\end{array}\right)$$

傅里叶逆变换的矩阵形式即为

$$\frac{1}{N}\left(\begin{array}{ccccc}{1} & {1} & {1} & {\cdots} & {1} \\ {1} & {\omega^{1} } & {\omega^{2} } & {\cdots} & {\omega^{(N-1)} } \\ {1} & {\omega^{2} } & {\omega^{4} } & {\cdots} & {\omega^{2(N-1)} } \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {1} & {\omega^{(N-1)} } & {\omega^{2(N-1)} } & {\dots} & {\omega^{(N-1)^{2} }}\end{array}\right)\left(\begin{array}{c}{F[0]} \\ {F[1]} \\ {F[2]} \\ {\vdots} \\ {f[N-1]}\end{array}\right)=\left(\begin{array}{c}{f[0]} \\ {f[1]} \\ {f[2]} \\ {\vdots} \\ {f[N-1]}\end{array}\right)$$