EE261 Lecture 19

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

这次回顾第十九讲，这一讲引入离散傅里叶变换。

引入

离散傅里叶变换的想法如下：

• 找到离散版本的$f(t)$作为$f(t)$的合理近似
• 找到离散版本的$\mathcal F f(s)$作为$\mathcal F f(s)$的合理近似

假设$f(t)$在$[0, L]$以外为$0$，$\mathcal F f(s)$在$[0, 2B]$以外为$0$，根据采样定理，我们需要在时域按照$1/ 2B$间隔采样，总共的点数为

$$N=\frac{L}{1 / 2 B}=2 B L$$

采样点为

$$t_{0}=0, t_{1}=\frac{1}{2 B}, t_{2}=\frac{2}{2 B}, \ldots, t_{N-1}=\frac{N-1}{2 B}$$

根据采样定理，知道上述点即可知道$f(t)$，所以我们可以说

• $f(t)$的离散版本为采样点$f\left(t_{0}\right), f\left(t_{1}\right), \ldots, f\left(t_{N-1}\right)$

现在借助$\text{III}$函数：

$$\sum_{n=0}^{N-1} \delta\left(t-t_{n}\right)$$

我们得到

$$f_{\text {discrete}}(t)=f(t) \sum_{n=0}^{N-1} \delta\left(t-t_{n}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) \delta\left(t-t_{n}\right)$$

取傅里叶变换可得

$$\mathcal{F} f_{\text {discrete}}(s)=\sum_{n=0}^{N-1} f\left(t_{n}\right) \mathcal{F} \delta\left(t-t_{n}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s t_{n}}$$

接着从频域角度考虑，根据采样定理，我们需要在时域按照$1/ L$间隔采样，总共的点数为

$$\frac{2 B}{1 / L}=2 B L=N$$

采样点为

$$s_{0}=0, s_{1}=\frac{1}{L}, \ldots, s_{N-1}=\frac{N-1}{L}$$

注意离散版本的$\mathcal F f(s)$不是$\mathcal F f(s)$在采样点$s_m$的值，而是$\mathcal{F} f_{\text {discrete}}(s)$在$s_m$的值：

$$F\left(s_{0}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{0} t_{n}}, F\left(s_{1}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{1} t_{n}}, \ldots, F\left(s_{N-1}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{N-1} t_{n}}$$

即

$$F\left(s_{m}\right)=\sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{m} t_{n}}$$

为什么上式可以看出傅里叶变换的近似呢？考虑定义

$$\mathcal{F} f\left(s_{m}\right)=\int_{0}^{L} e^{-2 \pi i s_{m} t} f(t) d t$$

利用积分的定义，我们有

$$\mathcal{F} f\left(s_{m}\right)=\int_{0}^{L} f(t) e^{-2 \pi i s_{n} t} d t \approx \sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{m} t_{n}} \Delta t=\frac{1}{2 B} \sum_{n=0}^{N-1} f\left(t_{n}\right) e^{-2 \pi i s_{m} t_{n}}=\frac{1}{2 B} F\left(s_{m}\right)$$

所以在不考虑常数因子的条件下，上式为傅里叶变换的近似。

离散傅里叶变换（DFT）

现在将上述讨论总结，首先假设给定$N$元组

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

那么如下$N$元组为其离散傅里叶变换

$$\mathbf{F}=(\mathbf{F}[0], \mathbf{F}[1], \ldots, \mathbf{F}[N-1])$$

其中

$$\mathbf{F}[m]=\sum_{n=0}^{N-1} \mathbf{f}[n] e^{-2 \pi i m n / N}, \quad m=0,1, \ldots, N-1$$

一些记号

为了后续讨论，这里引入一些记号，考虑

$$\mathrm{x}=(\mathrm{x}[0], \mathrm{x}[1], \ldots, \mathrm{x}[N-1]),\mathrm{y}=(\mathrm{y}[0], \mathrm{y}[1], \ldots, \mathrm{y}[N-1])$$

定义

$$\begin{aligned} \mathbf{x} \mathbf{y}&=\left(\mathbf{x}[0] \mathbf{y}[0], \mathbf{x}[1] \mathbf{y}[1], \ldots, \mathbf{x}[N-1] \mathbf{y}[N-1] \right) \\ \frac{\mathbf{x}}{\mathbf{y}}&=\left(\frac{\mathbf{x}[0]}{\mathbf{y}[0]}, \frac{\mathbf{x}[1]}{\mathbf{y}[1]}, \dots, \frac{\mathbf{x}[N-1]}{\mathbf{y}[N-1]}\right)\\ \mathbf{x}^{p}&=\left(\mathbf{x}[0]^{p}, \mathbf{x}[1]^{p}, \ldots, \mathbf{x}[N-1]^{p}\right) \\ f((\mathrm{x}[0], \mathrm{x}[1], \ldots, \mathrm{x}[N-1]))&=(f(\mathrm{x}[0]), f(\mathrm{x}[1]), \ldots, f(\mathrm{x}[N-1]))\\ [r:s] &=(r, r+1, r+2, \dots, s)\\ 0&=(0,0, \ldots, 0) \end{aligned}$$

定义

$$\begin{aligned} w&=e^{2 \pi i / N}\\ \omega&=\left(1, w, w^{2}, \ldots, w^{N-1}\right) \end{aligned}$$

不难看出

$$\begin{aligned} w^{kN} &= w^{2k \pi i} =1\\ \omega^{kN} & =(1,\ldots, 1) \\ \omega^{-k(m+N)}&=\omega^{-k m} \end{aligned}$$

DFT的向量形式

在上述记号下，不难得到

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

这是因为

$$\underline{\mathcal{F}} \mathbf{f}[m]=\sum_{k=0}^{N-1} \mathrm{f}[k] \omega^{-k}[m]=\sum_{k=0}^{N-1} \mathrm{f}[k]w^{-k m}=\sum_{k=0}^{N-1} \mathrm{f}[k] e^{-2 \pi i k m / N}$$

特别的，取$m=0$得到

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

DFT的矩阵形式

DFT可以理解为向量到向量的映射，不难看出该映射是线性的：

$$\begin{aligned} \underline{\mathcal{F}}\left(\mathbf{f}_{1}+\mathbf{f}_{2}\right)&=\underline{\mathcal{F}} \mathbf{f}_{1}+\underline{\mathcal{F}} \mathbf{f}_{2}\\\underline{\mathcal{F}}(\alpha \mathbf{f})&=\alpha \mathcal{F} \mathbf{f} \end{aligned}$$

记$\mathbf{F}=\underline{\mathcal{F}} f$，则矩阵形式为

$$\left(\begin{array}{c}{F[0]} \\ {F[1]} \\ {F[2]} \\ {\vdots} \\ {F[N-1]}\end{array}\right)=\left(\begin{array}{ccccc}{1} & {1} & {1} & {\cdots} & {1} \\ {1} & {\omega^{-1 \cdot 1}} & {\omega^{-1 \cdot 2}} & {\dots} & {\omega^{-(N-1)}} \\ {1} & {\omega^{-2 \cdot 1}} & {\omega^{-2 \cdot 2}} & {\cdots} & {\omega^{-2(N-1)}} \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {1} & {\omega^{-(N-1) \cdot 1}} & {\omega^{-(N-1) \cdot 2}} & {\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)$$

即

$$\underline{\mathcal{F}}=\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)$$