重疊保留法教學探索與案例設計

黃榮宗 藍麗娟 陳志文 蔣朝輝 許可

基金項目：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

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即可得到每個分段的圓周卷積的結果

舍棄劃“-”和“×”的數據，剩余數據順序排列即為線性卷積的結果。從式（5）可以看出，每段計算結果中只有M至L-1點保留了與線性卷積相同的結果，超過補零前序列長度L的數據出現了無效的非零值。因此，采用FFT計算線性卷積時，如需補零，則重疊保留法分段計算得到的圓周卷積結果中，超過補零前原有分段長度的數據需舍棄，再根據重疊保留法的步驟，舍棄前M-1個點，保留下來的結果按順序連接，得到線性卷積的結果。上節中討論的最后一個分段的補零不受此影響。

（五）? 教學案例設計

線性卷積是連接信號與系統的橋梁，分段卷積使得利用計算機加快計算線性卷積成為可能，因此分段卷積具有實際工程應用價值。上述內容雖具體探討了重疊保留法如何將分段數據“用完”的處理方法，討論了FFT算法補零對重疊保留法實現線性卷積的影響，但所述理論和方法對于初學者仍具挑戰。為了達到較好的教學效果，在教學實踐環節，可以引入具體工程案例對分段中的補零和數據保留等步驟進行講解和拓展。例如以調制光譜分析[11]和PD雷達測距[5]等設計教學案例，引導學生思考重疊保留法計算結束的判斷標準，討論當分段長度為非2的整數次冪時，FFT算法補零與末段補零的區別和聯系，從而達到讓學生掌握重疊保留法計算原理和步驟的目的。

下面以調制光譜分析為例對重疊保留法進行案例設計。光譜分析因高選擇性和高靈敏度等特性，使其在能源、環保等領域具有廣泛應用。對光譜信號進行調制可有效提高抗噪聲能力，因而使其能適用于惡劣的工業生產環境。案例中，輸入信號x（n）是采樣長度N=300 000的信號（其中包含頻率為6 kHz的正弦調制信號），系統的單位脈沖響應h（n）是頻率為6 kHz的單周期正弦信號（即信號長度為M=50），滿足N？垌M。實驗中采用兩種方法計算輸入信號x（n）與單位脈沖響應h（n）線性卷積的結果，即不分段直接利用FFT計算x（n）×h（n）（未分段FFT）、結合重疊保留法和FFT算法進行計算（重疊保留法）；實驗計算時，設置重疊保留法分段長度不滿足2的整數次冪，讓學生處理FFT的補零操作、重疊保留法的數據舍棄和保留、計算結束節點的判斷、計算結果異同的分析和兩種方法計算速度的比較等，并進行相關總結。

例如，針對上述實驗數據，在重疊保留法計算中，采用L=200個點進行分段和圓周卷積，則由于重疊保留法每一分段的前M-1=49個值是前一分段的最后M-1個值，因此實際每個分段中只保留151個有效的卷積結果；同時采用FFT計算時需將每個分段的xi（n）和h（n）補零至L'=28=256。在經過1 986次分段后，余下的數據包含重疊部分的長度為163，該段數據須首先補37個0使序列長度達到200個點，繼而進行FFT計算。此時與學生討論計算是否可以結束，讓學生掌握重疊保留法末段補零的原則，并結合FFT計算中補零的操作，分析并理解兩種補零處理的目的和作用，進而達到讓學生掌握知識的目的。

利用上述兩種方法計算得到的調制光譜信號的諧波曲線如圖5所示。計算結果顯示采用未分段FFT和采用重疊保留法計算線性卷積得到的結果是也必然是一致的，說明了重疊保留法的正確性和可操作性。同時，從數據的處理效率可以發現，未分段FFT計算速度極慢，這是由于當數據長度N很大時，讓計算機處理N點長度的數據需要耗費大量內存，嚴重影響數據的處理效率，而采用重疊保留法的計算速度非常快，二者形成鮮明對比，實驗表明重疊保留法可有效加快數據的處理速度，具有現實的工程應用價值。

圖5? 調制光譜案例中采用未分段FFT和重疊保留法計算線性卷積得到的諧波信號幅值對比

三? 結束語

分段卷積是數字信號處理課程的一個重要知識點，同時具備重要的工程實踐價值，重疊保留法是實現方法之一。現有教材和課堂教學均闡述了重疊保留法如何開始進行分段，未就結束段的數據處理進行詳細說明。我們針對教學環節中學生對重疊保留法存在的疑問，從圓周卷積與線性卷積的數學關系入手，深入淺出分析方法出現數據缺失的根本原因，創新提出解決方案；結合基2-FFT算法的實現步驟，進一步討論補零操作對計算的影響；最后通過調制光譜分析的案例設計，讓學生充分理解并掌握重疊保留法的具體實施步驟，并討論其工程應用價值。教學過程中，可以通過“發現問題—理論分析—方案探索—解決問題”[12]引導學生對相關知識點進行梳理學習，使學生加深對DFT/FFT、圓周卷積、分段卷積等知識點的理解，“從工程實踐中來，回到工程實踐中去”，鼓勵學生聯系工程實踐，敢于質疑、勇于探索，提升其從數理理論出發解決實際工程問題的能力，預期可以取得較好的教學效果。

參考文獻：

[1] 許可，萬建偉.數字信號處理[M].北京：清華大學出版社，2020.

[2] 王艷芬，王剛，張曉光，等.數字信號處理原理及實現[M].北京：清華大學出版社，2017.

[3] 程佩青.數字信號處理教程（第五版）[M].北京：清華大學出版社，2017.

[4] 張海劍，余磊，肖進勝，等.數字信號處理課程體系分析與教學實踐[J].高教學刊，2022，8（35）：124-127.

[5] 許可，辛勤，李雙勛，等.利用PD雷達脈沖壓縮實例講解分段卷積[J].電氣電子教學學報，2022，44（3）：127-129.

[6] 沈希忠.數字信號處理課程的應用型教學模式探索[J].高教學刊，2016（22）：98-99.

[7] 楊忠林，侯新國，劉建寶.“數字信號處理”中重疊保留法的教學探討[J].課程教育研究，2013（1）：54-55.

[8] 江漢，徐以濤，沈良.線性卷積與循環卷積的教學研究[J].電氣電子教學學報，2016，38（4）：72-74.

[9] 王倩雯，毛衛寧.數字信號處理中分段濾波的教學探討[J].電氣電子教學學報，2021，43（4）：78-80.

[10] 李昌利，霍冠英.“數字信號處理”中重疊保留法的證明[J].電氣電子教學學報，2011，33（6）：31-32，35.

[11] LAN L J. Development of a CO2 sensor using TDLAS-WMS and its application for emission analysis in Munich[D]. Germany： Technical University of Munich， 2020.

[12] 李敏通，趙繼政，遲茜，等.問題教學法在“數字信號處理”課程教學中的應用[J].高教學刊，2015（21）：70-71.