離散序列線性卷積和循環(huán)卷積的關(guān)系

離散序列線性卷積和循環(huán)卷積的關(guān)系

王益艷

(四川文理學院物理與機電工程學院,四川達州635000)

摘要：針對時域離散序列，探討了線性卷積和循環(huán)卷積之間的關(guān)系.分析了兩者等價的條件，并研究了其不等價情形下的誤差范圍，最后通過仿真實驗證明了理論結(jié)果的正確性.

關(guān)鍵詞：線性卷積；循環(huán)卷積；混疊誤差

收稿日期：2015-08-06

基金項目：四川文理學院2013年度重點教改項目“電子學專業(yè)信號處理系列課程教學模式改革與實踐”(2013JZ12)

作者簡介：王益艷(1982—)，男，湖北咸寧人.講師，碩士，主要從事圖像與信號處理研究.

中圖分類號：O411.1文獻標志碼：A

0引 言

線性卷積是時域離散線性時不變(LTI)系統(tǒng)中最重要的運算之一，通過卷積可以有效建立系統(tǒng)輸入和輸出之間的關(guān)系.[1]另外，F(xiàn)IR濾波器在實際中一般都是通過線性卷積實現(xiàn)的.[2]而離散傅里葉變換(DFT)又是在頻域?qū)崿F(xiàn)線性系統(tǒng)運算的一條有效途徑，通過循環(huán)卷積定理可知，[3]DFT可用來計算循環(huán)卷積.若序列x(n)的長度(即非零點的個數(shù))為M，h(n)的長度為N，則計算兩者L點(L≥max[M,N])的循環(huán)卷積yL(n)=x(n)?h(n)的方法如下：[4]

(1)在x(n)的尾部補L-M個零點，在h(n)的尾部補L-N個零點；

(2)分別計算L點的X(k)=DFT[x(n)]和L點的H(k)=DFT[h(n)]，其中k=0,1,2,…,L-1.

(3)計算YL(k)=X(k)H(k)，k=0,1,2,…,L-1.

(4)計算L點的yL(n)=IDFT[YL(k)]，n=0,1,2,…,L-1.

因此，循環(huán)卷積既可以在時域直接計算，也可以在頻域計算.同時，上述計算過程中的DFT和IDFT均可采用快速傅里葉FFT算法實現(xiàn).[5]當L很大時，在頻域計算循環(huán)卷積的速度要快得多.

與計算循環(huán)卷積一樣，為了提高運算速度，人們也希望用FFT計算線性卷積.然而FFT只能直接用來計算循環(huán)卷積.因此，研究線性卷積和循環(huán)卷積的關(guān)系以及兩者等價的條件具有重要的意義.[6]

1線性卷積和循環(huán)卷積等價的條件

不失一般性，假定x(n)和h(n)都是有限長序列，其長度分別為M和N.則它們的線性卷積和循環(huán)卷積可分別表示如下：[4]

(1)

(2)

(3)

對比式(1)和式(3)，可得

(4)

將式(4)代入式(3)，得

(5)

式(5)表明，yL(n)等于yc(n)以L為周期的周期延拓序列的主值區(qū)間.眾所周知，線性卷積yc(n)的長度為M+N-1.因此，只有當循環(huán)卷積的長度L≥M+N-1時，yc(n)以L為周期進行周期延拓時序列才沒有混疊現(xiàn)象.此時其主值區(qū)間必定滿足yL(n)=yc(n).由此證明了循環(huán)卷積和線性卷積等價的條件為L≥M+N-1.下圖1給出了其Matlab實驗結(jié)果.實驗參數(shù)取M=8，N=5，循環(huán)卷積的點數(shù)L分別取10，12，15.

圖1　線性卷積與循環(huán)卷積對比實驗結(jié)果

由上述實驗結(jié)果可知，線性卷積的長度為M+N-1=12(圖(1-c)).因此，只有當L≥12時，循環(huán)卷積的波形才與線性卷積結(jié)果相同(即圖(1-e)、圖(1-f)和圖(1-c)結(jié)果一樣)，而當L<12時，循環(huán)卷積的波形出現(xiàn)了一定程度的混疊失真(即圖(1-d)和圖(1-c)結(jié)果不一樣).

2線性卷積和循環(huán)卷積不相等的誤差分析

為了用DFT快速求解線性卷積，必須適當選取長度L.然而，在實際中，經(jīng)常遇到兩個序列的長度相差很大的情況，例如M?N.若仍選取L≥M+N-1，以L為循環(huán)卷積的長度，并采用DFT快速計算線性卷積.則要求對較短的序列補很多零點，而且長序列必須全部輸入后才能進行快速計算.這必然導致存儲容量大，運算時間長，無法滿足實時性的要求.而且在一些特殊的應用場合，序列長度不定或者認為是無限長，如醫(yī)學超聲信號和遙感信號等.[7-10]因此，在要求實時處理時，直接采用上述方法是行不通的.解決這個問題的方法一般是將長序列分段處理，具體包括重疊相加法和重疊保留法.[11]另一方面，當L取為小于M+N-1的值來做循環(huán)卷積，則必然會引起混疊，導致計算結(jié)果出現(xiàn)誤差.下面對其誤差進行分析和討論.首先，假設(shè)L滿足：

max(M,N)L

(6)

根據(jù)式(5)，令誤差e(n)為

(7)

因為L≥max(M,N)，僅有對應于m=±1的兩項保留在式(7)的求和運算中，所以

e(n)=[yc(n+L)+

yc(n-L)]RL(n)

(8)

一般來說，x(n)和h(n)都是因果序列，因此兩者的線性卷積yc(n)也是因果的，則

yc(n-L)=0;0nL-1

(9)

所以，

e(n)=yc(n+L);0nL-1

(10)

式(10)表明，當max(M,N)L

圖2　線性卷積與循環(huán)卷積混疊誤差實驗結(jié)果

測試指標長度有效范圍序列x(n)M=200,1,2….19序列h(n)N=90,1,2,….8線性卷積M+N-1=280,1,2,….2720點循環(huán)卷積誤差Δ1=(M+N-1)-L1=28-20=80,1,2,….720點循環(huán)卷積正確值L1-Δ1=20-8=128,9,10,….1924點循環(huán)卷積誤差Δ2=(M+N-1)-L2=28-24=40,1,2,324點循環(huán)卷積正確值L2-Δ2=24-4=204,5,….2326點循環(huán)卷積誤差Δ3=(M+N-1)-L3=28-26=20,126點循環(huán)卷積正確值L3-Δ3=26-2=242,3,4,….25

由上述實驗結(jié)果可知，當max(M,N)L

3結(jié)語

本文從理論分析的角度研究了離散序列兩種卷積的關(guān)系，發(fā)現(xiàn)循環(huán)卷積本質(zhì)上可以看成線性卷積以其長度為周期的周期延拓序列的主值序列，從而得出兩者相等應滿足的條件.同時還對兩者不相等情形下的誤差進行了探討，得出了相應誤差點的個數(shù)和范圍.最后，通過Matlab仿真實驗，驗證了該結(jié)論的正確性.

參考文獻:

[1] Won Y. Yang.SignalsandSystemswithMATLAB：影印版[M]. 北京: 電子工業(yè)出版社, 2012:13-20.

[2] Philips L, Parr M, Riskin E A.Signals,Systems,ansTransforms[M]. Fourth Edition, NJ, Pearson Education Inc, 2008: 213-227.

[3] Vinary K. Ingle.DigitalsignalprocessingusingMatlab：影印版[M]. 北京: 科學出版社, 2003:125-131.

[4] 程佩青. 數(shù)字信號處理教程[M]. 北京: 清華大學出版社, 2007:103-110.

[5] Vinay K. Ingle, John G. Proakis.數(shù)字信號處理：MATLAB版[M].劉樹棠,譯. 西安：西安交通大學出版社, 2008:134-140.

[6] 伍世云, 王益艷. Matlab在DSP課程教學中的幾個典型應用[J]. 計算機與現(xiàn)代化, 2011(8):185-189.

[7] 宋壽鵬, 李萍萍. 基于卷積模型的超聲回波分離技術(shù)及其應用[J]. 儀器儀表學報, 2009(6)：1175-1179.

[8] 朱莉莉, 李暉, 謝樹森. 用去卷積法提高超聲調(diào)制光學成像的空間分辨率[J]. 激光生物學報, 2008(1): 110-114.

[9] 許姜嚴, 王衛(wèi)星. 基于平均加權(quán)四元數(shù)卷積的巖石節(jié)理裂隙檢測[J]. 光電工程, 2009(10): 76-80.

[10]陳奮, 趙忠明. 遙感影像反卷積復原處理[J]. 數(shù)據(jù)采集與處理, 2008(2): 168-175.

[11]高西全, 丁玉美. 數(shù)字信號處理教程：第三版[M]. 西安: 西安電子科技大學出版社, 2008:90-93.

[責任編輯范藻]

Relationship Between Linear Convolution and

Circular Convolution of Discrete Sequence

WANG Yiyan

(Physics and Mechanical-Electrical Engineering School of Sichuan University of Arts and Sciences, Dazhou Sichuan 635000,China)

Abstract:The relationship between linear convolution and circular convolution is discussed for time-domain discrete sequence in this paper. It not only analyzes the equivalent condition of two convolutions, but also studies the range of error under in-equivalent situations. Finally, the theoretical results are proved by simulation.

Key words:linear convolution; circular convolution; aliasing errors