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{array}{rl}& DTFT[x(n)]=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}x(n)e^{-jwn}=\sum _{n=0}^{L-1}x(n)e^{-jwn}=X(e^{jw})\end{array}$$

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

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

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

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

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

$$\begin{array}{rl}& x(n)\otimes h(n):=[\sum _{m=0}^{N-1}x(m)h((n-m){)}_N]R_N(n)=[\sum _{m=0}^{N-1}h(m)x((n-m){)}_N]R_N(n)\end{array}$$

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

$$y_L[n]=\sum h[k]x[n-k]$$$$\begin{array}{rl}& {\left[\begin{array}{c}y[0]\\ y[1]\\ ⋮\\ y[L+M-2]\\ y[L+M-1]\end{array}\right]}_{(L+M-1)\times 1}={\left[\begin{array}{cccccc}h[0]& 0& \cdots & 0& 0& 0\\ h[1]& h[0]& \cdots & 0& 0& 0\\ ⋮& & & & & ⋮\\ 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{array}\right]}_{(L+M-1)\times N}\cdot {\left[\begin{array}{c}x[0]\\ x[1]\\ ⋮\\ x[L-2]\\ x[L-1]\end{array}\right]}_{N\times 1}\end{array}$$

循环卷积为

$$y_C[n]=\sum h[k]x[⟨n-k{⟩}_N]$$

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

$$(x\otimes h)(n)=\sum _{r=-\mathrm{\infty }}^{+\mathrm{\infty }}(x\ast h)(n+rN),n=0,\dots ,N-1$$

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