\[
\newcommand{\bs}{\boldsymbol}
\newcommand{\bsX}{\boldsymbol{X}}
\newcommand{\bf}{\mathbf}
\newcommand{\msc}{\mathscr}
\newcommand{\mca}{\mathcal}
\newcommand{\T}{\text{T}}
\newcommand{\rme}{\mathrm{e}}
\newcommand{\rmi}{\mathrm{i}}
\newcommand{\rmj}{\mathrm{j}}
\newcommand{\rmd}{\mathrm{d}}
\newcommand{\rmm}{\mathrm{m}}
\newcommand{\rmb}{\mathrm{b}}
\newcommand{\and}{\land}
\newcommand{\or}{\lor}
\newcommand{\exist}{\exists}
\newcommand{\sube}{\subseteq}
\newcommand{\lr}[3]{\left#1 #2 \right#3}
\newcommand{\intfy}{\int_{-\infty}^{+\infty}}
\newcommand{\sumfy}[1]{\sum_{#1=-\infty}^{+\infty}}
\newcommand{\vt}{\vartheta}
\newcommand{\ve}{\varepsilon}
\newcommand{\vp}{\varphi}
\newcommand{\Var}{\text{Var}}
\newcommand{\Cov}{\text{Cov}}
\newcommand{\edef}{\xlongequal{def}}
\newcommand{\prob}{\text{P}}
\newcommand{\Exp}{\text{E}}
\newcommand{\t}[1]{\text#1}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\versionofnewcommand}{\text{260125}}
\]
Discrete Time Fourier Transform (DFT)
假如存在一个 \(x(n)\), 当对它进行 LTI 系统 \(L\) 处理后, 满足不变性
\[
L(x(n))=\alpha_L\cdot x(n)
\]
那这样的 \(x(n)\) 对我们来说显然是极其方便的. 可以联想到矩阵的特征值与特征向量:
\[
A\boldsymbol x=\lambda\boldsymbol x
\]
事实上, \(x(n)=a^n\) 足矣.
\[
y(n)=\sum_{k=-\infty}^{+\infty} h(k)x(n-k)=\sum_{k=-\infty}^{+\infty} h(k)\cdot a^{n-k}
=\left(\sum_{k=-\infty}^{+\infty}h(k)\cdot a^{-k}\right)a^n=\alpha_h\cdot x(n)
\]
进一步地, 如果所有的 input \(x(n)\) 都能够写成如下形式:
\[
x(n)=\sum_{k=-\infty}^{+\infty}\alpha_k\cdot a_k^n
\]
那么, 经过 LTI 系统处理:
\[
L(x(n))=L(\sum_{k=-\infty}^{+\infty}\alpha_k\cdot a_k^n)=\sum_{k=-\infty}^{+\infty}\alpha_k\cdot L(a_k^n)=\sum_{k=-\infty}^{+\infty}\alpha_k\cdot\beta_h(k) \cdot a_k^n
\]
这意味着, 省去了许多麻烦的卷积步骤.
Discrete Time Fourier Transform (DFT)
将 \(x(t)\) 进行 Fourier 变换
\[
\begin{aligned}
x(t) &=\sum_{k=-\infty}^{+\infty}\alpha_k\exp(j\omega_kt)\\
\alpha_k &=\frac{1}{2\pi}\int_{-\pi}^\pi x(t)\exp(-jw_kt)\ dt
\end{aligned}
\]
由于复指数也是指数, 因此它就是 LTI 中的一种特殊的不变输入.
这里 \(x(t)\) 是连续函数. 现实中我们一般面对的是离散型式的 input.
首先, 通过 Discrete Time Fourier Transform 把输入变到频域上:
\[
\sum_{k=-\infty}^{+\infty} x(k)\exp(-j\omega k)= X(e^{j\omega})
\]
相应的逆变换:
\[
x(t)=\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{jw})\exp(j\omega k)\ d\omega
\]
这样就有:
\[
\begin{aligned}
L(x(n))&=L\left(\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\omega})\exp(j\omega n)\ d\omega\right)\\
&=\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\omega})\cdot L\left(\exp(j\omega n)\right)\ d\omega\\
&=\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\omega})\cdot \beta_h(j\omega)\cdot\exp(j\omega n)\ d\omega
\end{aligned}
\]
从最后的结果来看, 整个过程可以这样理解:
- 先把信号从时域转到频域上分析:
\[
x(t)\to X(e^{j\omega})
\]
- 接着, 直接在频域上用 LTI 处理, 具体形式不是卷积了! 而是直接乘上一个与系统有关的 Transformation Function (传递函数) . Thanks to 复指数!
\[
X(e^{j\omega})\cdot\beta_h(\omega)
\]
- 最后, 把这个结果用傅里叶逆变换倒腾回时域, 就大功告成了.
整理一下结果, 假设 \(x(t),\ y(t),\ h(t)\) 经过傅里叶变换后分别是 \(X(e^{j\omega}),\ Y(e^{j\omega}),\ H(e^{j\omega})\), 那么,
\[
\begin{cases}
y(t)=x(t)* h(t)\\
y(t)=\mathcal{F^{-1}}(X(e^{j\omega})\cdot H(e^{j\omega}))
\end{cases}
\]
从而
\[
\begin{aligned}
x(t)* h(t) & =\mathcal{F^{-1}}(X(e^{j\omega})\cdot H(e^{j\omega}))\\
\mathcal{F}(x(t)* h(t)) & =X(e^{j\omega})\cdot H(e^{j\omega})
\end{aligned}
\]
时域卷积定理：如果有两个函数在时域进行卷积，即 \(f(t)* g(t)\)，那么这个卷积的傅立叶变换等于这两个函数各自傅立叶变换的乘积
频域卷积定理：反之，如果在频域对两个函数的傅立叶变换进行乘积，其逆傅立叶变换得到的结果是这两个原时域函数卷积的结果
计算举例
对于
\[
x(n)=a^nu(n). |a|<1
\]
通过 DFT 变到频域
\[
X(e^{jw})=\sum_{k=-\infty}^{+\infty}x(k)\exp(-j\omega k)=\sum_{k=0}^{+\infty}a^k\exp(-j\omega k)=\sum_{k=0}^{+\infty}(a\exp({-j\omega}))^k=\frac{1}{1-a\exp(-j\omega)}
\]
低通滤波器与高通滤波器
看这个例子:
\[
y(n)=L(x(n))=\sum_{k=n-N+1}^nx(k)=x(n-N+1)+\cdots+x(n)
\]
容易看出满足 LTI.
接下来计算传递函数, 即系统在频域上的表达:
\[
H(e^{jw})=\sum_{k=-\infty}^{+\infty}h(k)\exp(-j\omega k)
\]
这样看来, 就不得不根据卷积计算 \(h\) 了:
\[
\sum_{k=-\infty}^{+\infty}h(n-k)x(k)=\sum_{k=n-N+1}^n x(k)
\]
那么就有:
\[
\begin{cases}
h(n-k)=1, &k=n-N+1,\cdots,n\\
h(n-k)=0, &others\\
\end{cases}
\Rightarrow
\begin{cases}
h(k)=1, &k=0,\cdots,N-1\\
h(k)=0, &others\\
\end{cases}
\]
于是
\[
H(e^{j\omega})=\sum_{k=0}^{N-1}\exp(-j\omega k)=\frac{1-\exp(j\omega N)}{1-\exp(j\omega)}
\]
我们将 \(H(e^{j\omega})\) 记成这样的形式:
\[
\begin{aligned}
H(e^{j\omega})&=\frac{\exp(j\omega\frac{N}{2})-\exp(-j\omega\frac{N}{2})}{\exp(j\frac{\omega}{2})-\exp(-j\frac{\omega}{2})}\cdot\frac{\exp(-j\omega\frac{N}{2})}{\exp(-j\frac{\omega}{2})}\\
&=\frac{\sin(\frac{N\omega}{2})}{\sin(\frac{\omega}{2})}\cdot\exp(-j\omega\frac{N-1}{2})
\end{aligned}
\]
其中, \({\sin(\frac{N\omega}{2})}/{\sin(\frac{\omega}{2})}\) 可看作是振幅, \(\exp(-j\omega\frac{N-1}{2})\) 可看作是相位.
由于 \(\omega\) 在复指数中具有周期 \(2\pi\), 因此只关注 \((-\pi,\pi)\) 就好. 来看一下这个区间内, 当 N=10 时的图像
明显地, 在低频段振幅高, 高频段振幅低. 因此该系统可以作为 低通滤波器.
同时, 还可以通过差分搞出 高通滤波器.
\[
\begin{aligned}
y(n) &=x(n)-x(n-1)\\
\Rightarrow\quad Y(e^{j\omega}) &=X(e^{j\omega})-X(e^{j\omega})\cdot\exp(-j\omega)\\
&=(1-\exp(-j\omega))\cdot X(e^{j\omega})
\end{aligned}
\]
其中, 用到了这一结论: 当对具有时延的信号作傅里叶变换时:
\[
\begin{aligned}
X_{n_0}(e^{j\omega})&=\sum_{k=-\infty}^{+\infty}x(k-n_0)\exp(-j\omega k)\\
&=\sum_{k^\prime=-\infty}^{+\infty}x(k^\prime)\exp(-j\omega k^\prime)\exp(-j\omega n_0)\\
&=X(e^{j\omega})\cdot\exp(-j\omega n_0)
\end{aligned}
\]
这样,
\[
H(e^{j\omega})=Y(e^{j\omega})/X(e^{j\omega})=1-\exp(-j\omega)
\]
其实我们可以直接算出它的幅度:
\[
|1-\exp(-j\omega)|=\sqrt{(1-\cos\omega)^2+\sin\omega^2}=\sqrt{2-2\cos\omega^2}=2\sin{\frac{\omega}{2}}
\]
看得出来, 低频振幅小, 高频振幅小.
卷积定理的证明 (一个域上相乘 \(\Leftrightarrow\) 另一个域上卷积)
\[
\begin{aligned}
Y(n)&=\sum_{k=-\infty}^{+\infty}y(k)\exp(-j\omega k)\\
&=\sum_{k=-\infty}^{+\infty}\left(\sum_{m=-\infty}^{+\infty}x(m)h(k-m)\right)\exp(-j\omega k)\\
&=\sum_{m=-\infty}^{+\infty}\left(\sum_{k=-\infty}^{+\infty}x(m)h(k-m)\right)\exp(-j\omega k),\ 交换次序\\
&=\sum_{m=-\infty}^{+\infty}x(m)\cdot\sum_{k=-\infty}^{+\infty}h(k-m)\exp(-j\omega (k-m+m))\\
&=\sum_{m=-\infty}x(m)\exp(-j\omega m)\cdot\sum_{k=-\infty}^{+\infty}h(k-m)\exp(-j\omega (k-m))\\
&=X(e^{j\omega})\cdot H(e^{j\omega})
\end{aligned}
\]
另外, 时域上两者相乘, 则频域上两者卷积.
\[
\begin{aligned}
y(n) &=x(n)h(n)\\
\Leftrightarrow\quad Y(e^{j\omega}) &=\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\theta})H(e^{j(\omega-\theta)})\ d\theta
\end{aligned}
\]
Proof:
\[
\begin{aligned}
y(n)=&\mathcal{F}^{-1}(Y(e^{j\omega}))\\
=&\frac{1}{2\pi}\int_{-\pi}^{\pi}\left(\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\theta})H(e^{j(\omega-\theta)})\ d\theta\right)\exp(j\omega n)\ d\omega\\
=&\frac{1}{4\pi^2}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi} X(e^{j\theta})H(e^{j(\omega-\theta)})\exp(j\omega n)\ d\theta\ d\omega\\
=&\frac{1}{4\pi^2} \int_{-\pi}^{\pi}X(e^{j\theta})\int_{-\pi}^{\pi}H(e^{j(\omega-\theta)})\exp(j\omega n)\ d\omega\ d\theta\\
=&\frac{1}{4\pi^2} \int_{-\pi}^{\pi}X(e^{j\theta})\int_{-\pi-\theta}^{\pi-\theta}H(e^{j\omega^\prime})\exp(j(\omega ^\prime+\theta)n)\ d\omega^\prime\ d\theta\\
=&\frac{1}{4\pi^2}\int_{-\pi}^{\pi}X(e^{j\theta})\exp(j\theta n)\int_{-\pi-\theta}^{\pi-\theta}H(e^{j\omega^\prime})\exp(j\omega^\prime n)\ d\omega^\prime\ d\theta
\end{aligned}
\]
吔? 积分限出现 \(\theta\) 以后, \(\omega^\prime\) 和 \(\theta\) 好像分不开了? 实际并非如此. 这是个以 \(2\pi\) 为周期的函数, 在整周期上做积分的值都一样. 于是:
\[
\begin{aligned}
y(n)=&\frac{1}{4\pi^2}\int_{-\pi}^{\pi}X(e^{j\theta})\exp(j\theta n)\int_{-\pi}^{\pi}H(e^{j\omega^\prime})\exp(j\omega^\prime n)\ d\omega^\prime\ d\theta\\
=&\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\theta})\exp(j\theta n)\ d\theta\cdot\frac{1}{2\pi}\int_{-\pi}^{\pi}H(e^{j\omega^\prime})\exp(j\omega^\prime n)\ d\omega\\
=&x(n)\cdot h(n)
\end{aligned}
\]
Parseval 恒等式
我们冥冥之中有种感觉, 一个信号在时域和频域上应该有种等量关系. 因为实际上, 这两者只是从不同的"基" 看待. 时域上的基是 \(\delta(n)\), 频域上的基则是 \(\exp(j\omega n)\)
Parseval (帕塞瓦尔) 恒等式告诉我们: 信号在时域的总能量等于信号在频域的总能量.
\[
\sum_{k=-\infty}^{+\infty}|x(k)|^2=\frac{1}{2\pi}\int_{-\infty}^{+\infty}|X(e^{j\omega})|^2\ d\omega
\]
更一般地:
\[
\sum_{k=-\infty}^{+\infty}x(k)\cdot y^*(k)=\frac{1}{2\pi}\int_{-\infty}^{+\infty}X(e^{j\omega})\cdot Y^*(e^{j\omega})\ d\omega
\]
证明也是简单的. 由刚才的结论, 时域上相乘则频域上卷积:
\[
\begin{aligned}
\mathcal{F}(x(n)\cdot y(n))
=& \sum_{k=-\infty}^{+\infty}x(k)\cdot y(k)\cdot e^{-j\theta k}\ d\theta\\
=& \frac{1}{2\pi}\int_{-\infty}^{+\infty} X(e^{j\omega})\cdot Y(e^{j(\theta-\omega)})\ d\omega\\
\end{aligned}
\]
令 \(\theta=0\) 即证.
习题例:
对于这样一个 LTI 系统:
\[
y(n)-\frac{1}{2}y(n-1)=x(n)-\frac{1}{4}x(n-1)
\]
在时域上算要算死了. 在频域看看:
先看这个情况: \(x(n)=\delta(n)\) 时:
\[
\begin{aligned}
&&Y(e^{j\omega})(1-\frac{1}{2}\exp({-j\omega})) &=1-\frac{1}{4}\exp(-j\omega)\\
\Rightarrow && Y(e^{j\omega}) &=\frac{1-\frac{1}{4}\exp(-j\omega)}{1-\frac{1}{2}\exp({-j\omega})}
\end{aligned}
\]
可是这一坨积分仍然不好做. 而且也没必要轻易地做积分.
\[
\begin{aligned}
Y(e^{j\omega})=&\ \frac{1-\frac{1}{4}\exp(-j\omega)}{1-\frac{1}{2}\exp({-j\omega})}\\
=&\ \frac{1}{1-\frac{1}{2}\exp({-j\omega})}-\frac{1}{4}\cdot\frac{\exp(-j\omega)}{1-\frac{1}{2}\exp({-j\omega})}\\
=&\ \mathcal{F}\left(\left(\frac{1}{2}\right)^n u(n)\right)-\mathcal{F}\left(\frac{1}{4}\left(\frac{1}{2}\right)^{n-1} u(n-1)\right)
\end{aligned}
\]