第五节 利用圆周卷积求线性卷积
分析时域离散非时变系统以及对序列进行滤波处理时，经常用到求线性卷积。第二章介绍了计算线性卷积的一些方法，其中用计算机求解时，也常常需要用户自己编写合适的函数，使用起来不够灵活。而圆周卷积可以直接使用MATLAB软件中提供的FFT函数，相较线性卷积的计算更加方便。因此，如果能找到线性卷积和圆周卷积之间的联系，借用圆周卷积来求线性卷积是一个不错的方法，本节将讨论这个问题。
假设h（n）和x（n）是长度分别为N和M的有限长序列。
h（n）和x（n）的线性卷积表示为
h（n）和x（n）的圆周卷积表示为
因为
所以
式（3-68）等号右边可写成
将式（3-69）代入（3-68）中，得
式（3-70）表示线性卷积等于圆周卷积以L为周期进行延拓后取其主值区间。因为线性卷积的长度为N+M-1，只有当圆周卷积的长度L≥N+M-1时，yl（n）以L为周期延拓才不会发生混叠现象，此时周期延拓的主值正好等于线性卷积，即yl（n）=yc（n）。下面用一个MATLAB的例子验证它们之间的关系。
例3-13 有两个序列x1（n）和x2（n），其中x1（n）={1，2，3|n=0，1，2}，x2（n）={1，2，3，4|n=0，1，2，3}，计算它们的线性卷积x3（n）以及4点、6点和10点的圆周卷积。
解：MATLAB参考脚本如下：
运行结果如下：
运行结果如图3-8所示。
图3-8 例3-13运行结果
由图3-8可以看出，6点和10点的圆周卷积与线性卷积均相等，但4点的圆周卷积与线性卷积不等。由于线性卷积的长度为6，当圆周卷积的长度大于或等于6时，圆周卷积在主值区间上的样本才与线性卷积相等。
以上研究的都是有限长序列，但在现实中往往需要实现一个有限长序列和一个无限长序列的线性卷积。例如：来自拾音器的语音信号可以认为是一个无限长序列，信号被全部接收后再处理是不现实的，既会产生很大的延时，且系统需要很大的存储空间。通常的操作是边接收边处理，常用的方法有两种：一种称作重叠相加法；另一种称作重叠保留法。
一、重叠相加法
令h（n）是一个长度为M的有限长序列，而x（n）是一个无限长序列（或者是一个长度远远大于M的序列）。目的是生成一种基于DFT的方法来计算h（n）和x（n）的线性卷积，根据线性卷积的公式有
假设x（n）是一个因果序列，将x（n）分割成一组长度为N的连续有限长序列
将式（3-73）代入式（3-71）中，得
式中
上式说明y（n）是由所有ym（n）的和相加得到的，而ym（n）是xm（n）和h（n）的线性卷积。由于xm（n）和h（n）的长度分别为M和N，ym（n）的长度为N+M-1。用计算机实现的步骤是：首先计算xm（n）和h（n）的N点DFT（假设N＞M），然后将其相乘之后的结果进行IDFT，得到所有的ym（n），这些ym（n）的值相加即为y（n）。
在此之前，还要注意一个细节，由于x0（n）和h（n）线性卷积的序列长度为N+M-1，定义区间为0≤n≤N+M-2，x1（n）和h（n）线性卷积的序列长度也为N+M-1，但定义区间为N≤n≤2N+M-2。这表明两个序列之间在N≤n≤N+M-2范围内有M-1个样本是重叠的。同样的道理，x2（n）和h（n）线性卷积的序列与x1（n）和h（n）线性卷积的序列在区间2N≤n≤2N+M-2内发生重叠。可归纳为：xr-1（n）*h（n）与xr（n）*h（n）的样本在区间rN≤n≤rN+M-2内有M-1个样本是重叠的。例3-14说明了这个问题。
例3-14h（n）是一个长度为5的序列h=[1，2，1，2，3]，x（n）是一个长度为21的序列x=[1，2，3，1，2，4，6，7，1，3，5，7，5，3，1，4，5，6，2，6，2]，现在将x（n）分割成一组连续的长度为7的有限长序列，下面分析其重叠相加法的计算过程及MATLAB实现。
解：每一段的x（n）与h（n）线性卷积，长度为11。第一个线性卷积的结果y0（n）的最后M-1=4个点与第二个线性卷积的结果y1（n）的前4个样本发生重叠。同样的道理，y1（n）的后4个样本与y2（n）的前4个样本重叠，由此类推，所求序列y（n）为
y（n）=y0（n），0≤n≤6
y（n）=y0（n）+y1（n-7），7≤n≤10
y（n）=y1（n-7），11≤n≤13
y（n）=y1（n-7）+y2（n-14），14≤n≤17
y（n）=y2（n-14），18≤n≤20
由于每部分线性卷积的结果与相邻的卷积结果之间有重叠，且要把重叠部分都相加才能得到最后的结果，所以将这个过程称为重叠相加法。其MATLAB参考脚本如下：
运行结果如图3-9所示。
图3-9中前三图分段求三个线性卷积，第四图将前三个卷积的结果相加，最后一个图是直接对x（n）与h（n）进行线性卷积。对照最后两个图，发现重叠相加法和直接计算的结果是一样的。
二、重叠保留法
重叠相加法的思路是，对每段xm（n）和序列h（n）进行N+M-1点DFT，结果相乘后再求IDFT，得到的每段ym（n）相加即是x（n）与h（n）的线性卷积y（n）。而重叠保留法将讨论用少于N+M-1点的DFT计算圆周卷积，将x（n）与h（n）的线性卷积和x（n）与h（n）的圆周卷积相等的项保留下来，丢弃两者不等的部分。为了理解线性卷积和圆周卷积之间的对应关系，举一个简单的例子来说明，假设x（n）与h（n）是长度分别为4和3的有限长序列，线性卷积的结果可表示为
图3-9 例3-14运行结果
n=0，yL（0）=x（0）h（0）
n=1，yL（1）=x（1）h（0）+x（0）h（1）
n=2，yL（2）=x（2）h（0）+x（1）h（1）+x（0）h（2）
n=3，yL（3）=x（3）h（0）+x（2）h（1）+x（1）h（2）
n=4，yL（4）=x（3）h（1）+x（2）h（2）
n=5，yL（5）=x（3）h（2）
将它们作4点圆周卷积，结果可用矩阵表示
比较线性卷积和圆周卷积的结果，发现前两个值不相等，但是第3、4个值是相等的。可以归纳证明在长度为M的序列h（n）和长度为N的序列x（n）的N点圆周卷积中（其中N＞M），通常最前面的M-1个样本是不正确的，要丢弃；而余下的N-M+1个样本对应于h（n）和x（n）的线性卷积是正确样本。前面的M-1个正确卷积值如何求解呢？还是用上面的例子，在序列x（n）的前面添加两个0，形成新的序列xb（n）={0，0，x（0），x（1）}，计算xb（n）和h（n）的四点圆周卷积yb（n），保留yb（n）中的yb（2）=yc（0），yb（3）=yc（1）。
对上面的结论进行推广，设h（n）为长度为M的序列，x（n）是一个无限长序列，将x（n）前面添加M-1个零样本，然后分割成一组连续的长度为N的序列xm（n）（0≤m≤∞，N≥M），每组序列的前M-1个样本必须和上一组序列的最后M-1个样本相同。xm（n）和h（n）的N点圆周卷积表示成wm（n）=xm（n）⊗h（n），丢弃wm（n）中的前M-1个样本，保留剩下的N-M+1个样本，保留的样本等于对应的线性卷积的样本值。下面通过例3-15说明这个原理。
例3-15 设x（n）=（n+2），0≤n＜10，h（n）={1，2，1}，当N=6时，用重叠保留法计算x（n）和h（n）的线性卷积y（n）。
解：M=3，所以在序列x（n）的前面必须添加M-1个零样本，将x（n）分割成长度为N的几段，由于每一段必须和前面一段序列重叠M-1=2个样本，因此，分段为
x 1（n）={0，0，2，3，4，5}
x 2（n）={4，5，6，7，8，9}
x 3（n）={8，9，10，11，0，0}
由于分割成三段，因此在最后一段的后面也补充了两个零样本。
对每一段与h（n）作圆周卷积，得到
y 1（n）=x1（n）⊗h（n）={14，5，2，7，12，16}
y 2（n）=x2（n）⊗h（n）={30，22，20，24，28，32}
y 3（n）=x3（n）⊗h（n）={8，25，36，40，32，11}
由于前M-1=2个样本要舍弃，因此，y（n）={2，7，12，16，20，24，28，32，36，40，32，11}，这与线性卷积的结果相同。
可用MATLAB参考脚本如下：
运行结果如图3-10所示。
图3-10 例3-15运行结果