重叠保留法教学探索与案例设计

基金项目：2023年国家自然科学基金面上项目“微尺度功能表面上气液相变的介微观建模与直接模拟研究”（52376086）；2021国家自然科学基金青年项目“非一致标准具效应下微量气体原位检测方法研究”（62103448）；2022年湖南省科技创新计划项目“青年科技人才项目”（2022RC1090）

第一作者简介：黄荣宗（1988-），男，汉族，湖北咸宁人，工学博士，特聘副教授。研究方向为多相流介微观数值方法及应用、固液相变传热与储能等。

*通信作者：蓝丽娟（1987-），女，畲族，福建漳州人，工学博士，讲师。研究方向为工业自动化检测、工业过程碳排放智能感知等。

DOI：10.19980/j.CN23-1593/G4.2024.12.031

摘  要：分段卷积是DFT/FFT实现线性卷积的重要途径，主要有重叠保留法和重叠相加法，教学过程中发现，学生对于重叠保留法的学习往往忽略对算法原理的真正理解，导致计算结果不准确。该文基于圆周卷积与线性卷积的数学关系，推导重叠保留法计算误差出现的原因，得到重叠保留法的计算步骤；结合计算流程和具体实例，分析造成计算数据缺失的原因，并创新提出解决方法；随后分析基2-FFT算法下补零处理对重叠保留法的影响，得出采用重叠保留法和FFT算法计算线性卷积的优化步骤；最后，以调制光谱分析为例进行教学案例设计，并对重叠保留法给出相应的教学建议。

关键词：分段卷积；重叠保留法；线性卷积；圆周卷积；案例设计

中图分类号：G642      文献标志码：A          文章编号：2096-000X（2024）12-0130-04

Abstract： Piecewise convolution is an important way for DFT/FFT algorithm to calculate linear convolution. It mainly includes overlapping reservation and overlap-add methods. During the teaching process， students often ignore the principle of the algorithm when learning the overlapping reservation method， resulting in calculation errors. Based on the mathematical relationship between circular convolution and linear convolution， this article deduces the reasons for the calculation error of the overlapping reservation method， and obtains the calculation process of the overlapping reservation method. Combining the calculation process and specific examples， it analyzes the reasons for the missing calculation data， and innovatively proposes the solution. Then， it analyzes the impact of zero-padding processing on the overlapping preservation method under the base 2-FFT algorithm， and optimizes the steps for calculating linear convolution using the overlapping reservation and FFT algorithms. Finally， a teaching case is designed using the modulation spectrum analysis， and corresponding teaching suggestions are given for the overlapping reservation method.

Keywords： piecewise convolution; overlapping reservation method; linear convolution; circular convolution; case design

线性卷积反映系统对于输入信号的作用结果，即线性卷积当前时刻的输出是当前及其之前时刻系统对输入信号响应的叠加，线性卷积是连接信号与系统的桥梁。利用圆周卷积计算线性卷积是离散傅里叶变换（DFT）的典型应用，具有现实的工程意义，也是数字信号处理课程的重要知识点[1-4]。由于DFT可以采用快速傅里叶变换（FFT）算法实现，因此可以利用FFT快速计算两个序列的线性卷积。但现实应用中往往面临两个计算序列的长度严重不匹配的情况，直接计算圆周卷积需要对其中较短序列大量补零，严重增加了计算量，降低了数据处理效率，因此引入分段卷积对较长的序列进行分段，提高数据处理效率，分段方法主要有重叠保留法和重叠相加法[5-10]。

在课程教学过程中，我们发现学生对圆周卷积与线性卷积的关系理解不足，特别是在运用重叠保留法计算时，学生对分段过程中的补零理解不够深刻，往往认为长序列分段结束即计算结束，没有真正了解最后一段数据是否已被“用完”，从而导致计算的结果存在缺漏的现象时有发生，而现有教材、课程教学方法等对这一情况尚未进行详细研究和阐述[1-3]。为此，我们根据圆周卷积和FFT算法的计算原理，结合具体案例，创新讲解重叠保留法的计算方法和实现步骤，提出教学方法探索，以使学生加深对分段卷积的理解，达到较好的教学效果。

一  重叠保留法的计算原理

重叠保留法的计算源于圆周卷积与线性卷积的数学关系，假设参与线性卷积的两个序列x（n）和h（n），其序列长度分别为N1和N2，线性卷积y（n）长度N=N1+N2-1，圆周卷积yc（n）可用下列表达式表示为

式中：L为圆周卷积的长度。即，圆周卷积是线性卷积以L长度进行周期延拓后，取主值周期的结果。

当圆周卷积长度大于等于线性卷积的长度（L≥N）时，圆周卷积的结果正好与线性卷积相同；当L<N时，线性卷积的周期延拓导致超过圆周卷积长度的数值叠加到了序列的前端，使得圆周卷积的结果存在混叠，前N-L点与线性卷积不同，只有在N-L≤n≤L-1的范围内，圆周卷积结果与线性卷积结果一致（图1）。因此，圆周卷积的计算误差e（n）仅存在于前N-L点，且与超过圆周卷积长度部分的线性卷积数值相等，具体地，可以用数学表达式表示为

e（n）=y（n+L）。         （2）

图1  圆周卷积长度小于线性卷积的结果

二  教学方法探索

（一）  算法步骤

基于上述的数学关系，重叠保留法的实现方法如图2所示。假设两个序列x（n）和h（n）的长度分别为N和M，且满足N？垌M。计算步骤如下。

图2  重叠保留法计算流程图

1）将序列x（n）以前后重叠的方式进行分段，分段长度为L，重叠部分的长度为M-1，其中第1段的前面M-1个点为0。

2）将每个分段与h（n）作长度为L的圆周卷积。

3）每段圆周卷积的前M-1个点数值因发生混叠而舍弃（图中每段yi（n）的打“×”部分），余下的L-M+1个数值是每段卷积的正确结果。

4）将这些结果按顺序连接起来，即可得到x（n）和h（n）的线性卷积的结果。

（二）  案例分析

上节算法步骤是多数教材呈现的重叠保留法的实现步骤。然而在教学过程中，我们发现学生对分段卷积的原理理解不到位，如果仅依靠这些步骤，学生在解题过程中对于分段、补零、计算和保留等过程的处理总出现失误，导致计算线性卷积存在数据缺失的情况时有发生。以一个实例进行讲解。

假设参与线性卷积的两个序列分别为x（n）={1，2， 3，4，5，6，7，8，9，10}，h（n）={1，2，-1}。若采用L=7进行对x（n）分段，不少学生认为最后一个数据出现在分段中即可停止分段，即得到下述分段

根据这个分段计算得到的结果为y（n）={1，4，6，8，10，12， 14，16，18，20}，y（n）的长度为10，显然与正确的长度12不符，也就是说上述的计算还没有结束，分段仍需继续。那么，问题在于重叠保留法为什么会出现上述的问题？分段结束的依据是什么？如何保证重叠保留法采用最少的分段得到完整的线性卷积结果？

（三）  改进方法

针对上述的问题，我们从圆周卷积与线性卷积的数学关系探讨如何保证重叠保留法把数据“用完”。由于圆周卷积是线性卷积周期延拓后进行累加取主值周期得到的结果，当圆周卷积的长度小于线性卷积时，将会发生混叠现象。为避免混叠带来的影响，重叠保留法以前后重叠的方式对长序列进行分段，计算结果将重叠的部分舍弃，未重叠的部分即构成了正确的线性卷积的分段。而重叠部分实际上是每个分段中超过圆周卷积长度的部分叠加到了序列的前端，即圆周卷积相对于线性卷积的误差实际上是超过圆周卷积长度的线性卷积的序列值（见公式（2））。

因此，当我们对长序列进行分段并作圆周卷积时，最后一个分段的部分线性卷积的结果总会因为混叠而被叠加到该段的前端，并被舍弃；被叠加部分如果包含有效的卷积结果，就会造成计算结果的缺失。为避免这种现象，保证最后一个分段的有效线性卷积结果不被混叠，就需要在输入序列的末端做补零处理。

针对重叠保留法的处理步骤，与第一个分段序列的补零处理相同，我们不难发现，对于最后一个分段，我们仍然需要与第一个分段相同的补零个数（M-1个0，M为短序列的长度），才能避免最后一个分段的有用线性卷积结果被混叠至前端而丢失。如图3所示，考虑到分段长度的灵活性，对于重叠保留法，不仅要在第一个分段序列的最前端补M-1个0，最后一个分段序列也要保证在有效数据的末端补至少M-1个0。所得圆周卷积结果除了要剔除前M-1个值，末端如有0值，也需要舍弃，所得结果按顺序连接，即为所求线性卷积的结果。

图3  重叠保留法最后一个分段至少要有M-1个补零

如上例题，增加第3个分段x2（n）={9，10，0，0，0，0，

0}8，圆周卷积结果为y2（n）={9，28，11，-10，0，0，0}，去掉前2个值，保留非0序列为{11，-10}，正是缺失的最后两个数值。

（四）  FFT快速实现

利用FFT进行计算线性卷积，通常要求参与计算序列的长度为2的整数次幂（基2-FFT算法），如果序列长度未满足2的整数次幂的要求，则需将每个序列长度补零至相应长度，利用FFT计算线性卷积的流程图如图4所示，其中L'为2的整数次幂，L'≥L。下面讨论FFT补零对重叠保留法的影响。

图4  利用FFT计算线性卷积的流程图

仍以上述例题为例。显然L=7不满足FFT的要求，因此需对每个分段进行补零，按照L'=23，即

， （4）

将式（4）中的每个分段xi（n）与h（n）分别计算8点FFT，相乘后计算8点IFFT即可得到每个分段的圆周卷积的结果