DTFT、DFT、循环卷积与线性卷积

最近在助教DSP这门课时候，对循环卷积理解不够，特此重新学习一下。

---

在计算机上实现信号的频谱分析及其它方面的处理工作时，对信号的要求是：在时域和频域都应当是离散的，且都应是有限长！

首先对于任意的连续非周期信号，通过傅立叶变换FT(Fourier Transform)得到频域，频域信号也是连续的。

由于计算机只能处理离散信号，将原来时域模拟信号离散化，引入时域采样信号，其频谱也是一系列的冲激串。时域相乘，对应频域卷积。

这里$\omega_0$和$T_0$的乘积为$2\pi$,也就是说采样间隔越频繁，$\omega_0$间隔越大，因此频谱重叠的可能就越小。
通过时域采样，频域频谱镜像会呈周期性出现在各个脉冲点处。接着我们对频域进行采样。频域相乘，对应时域卷积。也就是对时域采样信号的周期延拓。
因此可以说：DTFT是数学家的杰作，DFT是工程师的杰作。

接着分析线性卷积与循环卷积

卷积是信号处理领域跟线性时不变系统有关的一种运算，关于卷积的理解，知乎有很多精彩的阐述，其中我认为最精彩的表述是：瞬时行为的持续性后果，你细品。

循环卷积是使用DFT(FFT)计算线性卷积时的衍生品。

对于离散信号，卷积通常计算比较复杂，可能的简化思路是放到频域计算。我们知道

$$DTFT[y(n)]=DTFT[x(n)]DTFT[h(n)]$$

其中

$$\begin{aligned}&DTFT[x(n)]=\sum_{n=-\infty}^\infty x(n)e^{-jwn}=\sum_{n=0}^{L-1}x(n)e^{-jwn}=X(e^{jw})\end{aligned}$$

但是由于DTFT频域连续计算机不容易处理，因此使用DFT，但是DFT卷积存在个问题，时域线性卷积DFT转化为相乘不一定成立，这是因为DFT/IDFT都隐含了一个相同的参数，就是DFT的点数，也就是说下面式子不一定成立。

$$IDFT[DFT[x(n)]DFT[h(n)]]\stackrel{?}{=}IDFT[DFT[x(n)*h(n)]]$$

然后把频域相乘后转化到时域的结果定义为循环卷积，这是因为求解后发现表达式中有循环的过程。

$$IDFT[DFT[x(n)]\bullet DFT[h(n)]]=x(n)\otimes h(n)$$

发现了循环卷积和线性卷积的关系，进而定义了具体的循环卷积。

$$\begin{aligned} &x(n)\otimes h(n):=\left[\sum_{m=0}^{N-1}x(m)h((n-m))_N\right]R_N(n)=\left[\sum_{m=0}^{N-1}h(m)x((n-m))_{N}\right]R_{N}(n) \end{aligned}$$

循环卷积要求两个卷积的信号的DFT点数相同。
现在讨论上面式子成立的条件，这是与DFT的点数有关的，注意DFT点数和信号长度这是两个概念。
假设两卷积信号长度分别为$L$与$M$，DFT点数为$N$。
当信号为因果信号时，线性卷积为

$$y_L[n]=\sum h[k]x[n-k]$$ $$\begin{aligned}&\begin{bmatrix}y[0]\\y[1]\\\vdots\\y[L+M-2]\\y[L+M-1]\end{bmatrix}_{(L+M-1)\times1}=\begin{bmatrix}h[0]&0&\cdots&0&0&0\\h[1]&h[0]&\cdots&0&0&0\\\vdots&&&&&\vdots\\0&0&\cdots&h[M]&h[M-1]&h[M-2]\\0&0&\cdots&0&h[M]&h[M-1]\\0&0&\cdots&0&0&h[M]\end{bmatrix}_{(L+M-1)\times N}\cdot\begin{bmatrix}x[0]\\x[1]\\\vdots\\x[L-2]\\x[L-1]\end{bmatrix}_{N\times1}\end{aligned}$$

循环卷积为

$$y_C[n]=\sum h[k]x[\langle n-k\rangle_N]$$

当卷积点数小于$L$与$M$时，显然有部分数据被丢弃了，结果必然是不正确的。
当卷积点数大于$L$与$M$，也大于$L+M-1$时，循环卷积即为线性卷积，结果必然正确。
当卷积点数大于$L$与$M$，却小于$L+M-1$时，左边时域将按N点进行周期延拓产生混叠。

$$(x\otimes h)(n)=\sum_{r=-\infty}^{+\infty}(x*h)(n+rN),n=0,\ldots,N-1$$

在学习循环卷积时，往往是直接给出了循环卷积的定义，然后让我们去求循环卷积与线性卷积的关系，因此显得循环卷积的由来很突兀。其实在历史发展过程中，是先发现$IDFT[DFT[x(n)]\bullet DFT[h(n)]]$与线性卷积的关系（是线性卷积的以N为周期移位叠加），进而定义了循环卷积。
有时候总是过度去思考因果来由让自己难以自洽。