\[
\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}}
\]
圆周卷积与线性卷积
LTI 系统最核心的运算是卷积. 更准确地讲, 是线性卷积.
假设冲激响应 \(\{h(n)\}_{n=0}^{P-1}\), 输入信号 \(\{x(n)\}_{n=0}^{L-1}\), 那么有
\[
\begin{aligned}
y(n)=\sum_{k=-\infty}^{+\infty}h(k)x(n-k)\\
\end{aligned}
\]
这一步, 实际上对 \(h\) 和 \(x\) 作了时间上的扩展 (Time Expansion):
\[
x(n)=0,\ n<0, n\geq L\\
h(n)=0,\ n<0, n\geq P
\]
该卷积输出的长度为 \(P+L-1\). 以及, 卷积计算的复杂度为 \(O(PL)\). 过去哪有你们现在这么好条件呐 (迫真)! 我们希望降低复杂度, 不做这个线性卷积. 怎么办呢? 考虑 DFT, 或者进一步说, 做 FFT, 如果两个长度为 \(L\) 做卷积, 它的 FFT 复杂度就是 \(O(L \log L)\), 相比直接做线性卷积的 \(O(L^2 )\) 降了半阶. 这样, 如果用频域相乘替代频域卷积, 一共只需要做三次 FFT 和一次乘法.
Circular Convolution 圆周卷积
对于有限长度的序列, 圆周卷积可以由周期延拓来定义:
\[
x(n)\circledast h(n)=\sum_{r=-\infty}^{+\infty}h(n)*x(n-rL)
\]
利用周期延拓实现了 "在直线上把尾巴接到另一端".
如果记 \(y(n)=x(n)*h(n)\), 那么类似地, 我们可以记 \(\tilde{y}(n)=x(n)\circledast h(n)\).
对于有限长度的序列, 我们直接对频域上两个 DFT 作乘法, 得到的实际上是圆周卷积, 而非线性卷积. 可以这样理解:
\[
\begin{aligned}
X(k)=\sum_{n=0}^{N-1}x(n)\exp(-j\frac{2\pi}{N}nk)=\sum_{n=0}^{N-1}x(n)w_N^{nk}\\
\end{aligned}
\]
在有限长度的情况下, 将两个多项式相乘
\[
\lr[{x(0)+x(1)w_N^k+\cdots+x(n-1)w_N^{(N-1)k}}] \times
\lr[{h(0)+h(1)w_N^k+\cdots+h(n-1)w_N^{(N-1)k}}]
\]
得到的结果将会是
\[
y(0)+y(1)w_N^k+\cdots+y(n-1)w_N^{(N-1)k}
\]
考察 \(w_N\) 的次数, 为什么在 \(y\) 里没见到理论上存在的高次项 \(w^{(2N-2)k}\) 呢? 这是因为 \(w_N^N=1\), 有很多项都被合并了. 这一合并过程, 就是圆周卷积. 也就是说, DFT 由于指数项中代表离散的 \(N\) 存在, 一定会导致指数项经过 \(N\) 次方后变为 \(1\), 因此得到的是圆周卷积.
接下来, 严谨点说. 毕竟空说无凭. 假设 \(x(n),h(n)\) 的长度都为 \(N\).
\[
\begin{aligned}
X(k)\cdot H(k)&=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x(n)h(l)w_N^{(n+l)k}\\
&=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x(n)h(l)w_N^{((n+l)\ \text{mod}\ N)\cdot k}
\end{aligned}
\]
设
\[
\begin{aligned}
l^\prime&=(n+l)\ \text{mod}\ N\\
\Rightarrow l&\equiv(l^\prime-n)\ \text{mod}\ N
\end{aligned}
\]
由于 \(l,n\) 的取值范围都是 \(0\) 到 \(N-1\), 可以将 \(l\) 直接记为 \(l^\prime-n\)
将 \(l=((l^\prime-n))_N\) 代入换元, 则有:
\[
\begin{aligned}
X(k)\cdot H(k)&=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x(n)h(l)w_N^{l^\prime k}\\
&=\sum_{n=0}^{N-1}\sum_{l^\prime=n\ \text{mod}\ N}^{(n+N-1)\ \text{mod}\ N}x(n)h(((l^\prime-n))_N)w_N^{l^\prime k}\\
&=\sum_{n=0}^{N-1}\left(\sum_{l^\prime=0}^{N-1}x(n)h(((l^\prime-n))_N)\right)w_N^{l^\prime k}\\
&=\sum_{n=0}^{N-1}\left(\sum_{l^\prime=0}^{N-1}\sum_{r^\prime=-\infty}^{+\infty}
x(n)h(l^\prime-(n-rN))\right)w_N^{l^\prime k} \\
&=\sum_{n=0}^{N-1}\left(\sum_{r^\prime=-\infty}^{+\infty}x(n)* h(n-rN)\right)w_N^{l^\prime k} \\
&=\sum_{n=0}^{N-1}(x(n)\circledast h(n)) \\
&=\sum_{n=0}^{N-1}\tilde{y}(n)w_N^{l^\prime k}\\
&=\tilde{Y}(n)
\end{aligned}
\]
圆卷积便体现在其中取 mod 的过程.
利用 DFT 做线性滤波
假如说, 我们要处理一段上无限长的信号 \(x(n)\). 那么, 显然就要分段处理, 否则无法进行 DFT. (首先, 由于计算量, 不可能直接对整段信号做卷积). 假定我们取每一段的长度为 \(L\), 用长度为 \(P\) 的滤波器 \(h\) 处理. 不过根据先前的讨论, 直接做 DFT 出来的是圆周卷积, 如果我们想要线性卷积, 该怎么办呢?
事实上, 我们可以在截取的长度为 \(L\) 的信号 (不妨直接记为 \(x_k\)) 后面补上 \(P\) 个 \(0\). 从周期延拓的角度理解圆卷积, 该操作就保证了延拓时将每个 copy 移得足够开, 从而不会发生混叠.
进行如下定义:
\[
x_k(n)=
\begin{cases}
x(n), & (k-1)L\leq n\leq kL-1\\
0,&others
\end{cases}
\]
就有
\[
x(n)=\sum_{r=-\infty}^{+\infty}x_r(n)
\]
于是
\[
x(n)*h(n)=\sum_{r=-\infty}^{+\infty}x_r(n)*h(n)
\]
在计算每一个具体的 \(x_r(n)*h(n)\) 时, 对 \(x_r(n)\) 补零使得该卷积为线性卷积.
该方法称为 重叠相加, Overlay Add. 切下来, 补零, 卷积, 直接加!
不过捏, 毕竟补上 \(P\) 个 \(0\) 会使得做 DFT 的点位变多, 有些刁钻的人要说了, 这是否有点不环保!
在做卷积的过程中, 当 \(h\) 完全包含在 \(x\) 的区间内时, 圆周卷积的结果就等于线性卷积, 只有在两端 \(h\) 伸出去那两段的结果有偏差. 也就是说, 要掐头去尾留中间. 但这样截取, 岂不是会丢失信息? 不过这一点很容易弥补, 只要在从原信号截取每一段信号时, 人为地提前 \(P\) 个点位. 尽管代价是, 每次信号推进的长度为 \(L-P\), 但每次 DFT 只需要做 \(L\) 点.
该方法称为 重叠保留, Overlay Save
重叠相加和重叠保留就是利用 DFT 做线性滤波的两个主流策略. 方法的选择根据实际情况来. 例如, 假如使用的器件只能做比较低点数的, 那就重叠保留, 也就是做得慢一点嘛.