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

王益艷

(四川文理學(xué)院物理與機(jī)電工程學(xué)院,四川達(dá)州635000)

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

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

收稿日期：2015-08-06

基金項(xiàng)目：四川文理學(xué)院2013年度重點(diǎn)教改項(xiàng)目“電子學(xué)專(zhuān)業(yè)信號(hào)處理系列課程教學(xué)模式改革與實(shí)踐”(2013JZ12)

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

中圖分類(lèi)號(hào)：O411.1文獻(xiàn)標(biāo)志碼：A

0引 言

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

(1)在x(n)的尾部補(bǔ)L-M個(gè)零點(diǎn)，在h(n)的尾部補(bǔ)L-N個(gè)零點(diǎn)；

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

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

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

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

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

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

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

(1)

(2)

(3)

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

(4)

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

(5)

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

圖1　線性卷積與循環(huán)卷積對(duì)比實(shí)驗(yàn)結(jié)果

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

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

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

max(M,N)L

(6)

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

(7)

因?yàn)長(zhǎng)≥max(M,N)，僅有對(duì)應(yīng)于m=±1的兩項(xiàng)保留在式(7)的求和運(yùn)算中，所以

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

yc(n-L)]RL(n)

(8)

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

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

(9)

所以，

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

(10)

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

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

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

由上述實(shí)驗(yàn)結(jié)果可知，當(dāng)max(M,N)L

3結(jié)語(yǔ)

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

參考文獻(xiàn):

[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]. 北京: 科學(xué)出版社, 2003:125-131.

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

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

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

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

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

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

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

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

[責(zé)任編輯范藻]

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