DFT計(jì)算卷積學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1DFT計(jì)算卷積計(jì)算卷積第1頁(yè)/共25頁(yè)第2頁(yè)/共25頁(yè)問(wèn)題提出：實(shí)際需要： LTI系統(tǒng)響應(yīng) yk=x khk第3頁(yè)/共25頁(yè)設(shè) x k 的非零范圍是 0 k N-1gk 的非零范圍是 0 k M-1yk=x khk非零范圍序列yk的長(zhǎng)度為0 k N+M- 2L=N+M-1至少要做 L=N+M-1點(diǎn)的循環(huán)卷積第4頁(yè)/共25頁(yè)補(bǔ)L-N零補(bǔ)L-M零L點(diǎn)DFTL點(diǎn)DFTL點(diǎn)IDFTkxkhkyx1kh1k第5頁(yè)/共25頁(yè)利用MATLAB由DFT計(jì)算xk* hk。 xk=1, 2, 0, 1, hk=2, 2, 1, 1% Calculate Linear Convolution by DFTx

2、 = 1 2 0 1;h = 2 2 1 1;% determine the length for zero paddingL = length(x)+length(h)-1;% Compute the DFTs by zero-paddingXE = fft(x,L);HE = fft(h,L);% Determine the IDFT of the producty1 = ifft(XE.*HE);第6頁(yè)/共25頁(yè)01234560246Result of Linear ConvolutionTime index kAmplitude01234560123x 10-15Time index

3、kAmplitudeError Magnitude第7頁(yè)/共25頁(yè)(1) 信號(hào)要全部輸入后才能進(jìn)行計(jì)算，延遲太多(2) 內(nèi)存要求大(3) 算法效率不高分段卷積可采用和第8頁(yè)/共25頁(yè)將長(zhǎng)序列xk 分為若干段長(zhǎng)度為L(zhǎng)的序列kx- 010 其他LknLkxkxn定義0nLkxnn-(短序列hk 的長(zhǎng)度為M)第9頁(yè)/共25頁(yè)0khnLkxkhkxnn-0nLkynn-y0k的非零范圍20-MLky1k-L的非零范圍 22-MLkL序列 y0k, y1k的重疊部分2-MLkL重疊的點(diǎn)數(shù)L+M-2-L+1=M-1:khkxkynn 計(jì)計(jì)算算第10頁(yè)/共25頁(yè)第11頁(yè)/共25頁(yè)第12頁(yè)/共25頁(yè) 重疊相加

4、法 (M=3)yk=xk*hk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14x1k=2, 3, 4, 5, 6x2k=7, 8, 9 ,10, 11x3k=12, 13, 14, 0, 0y1k= x1k*hk= 2,7,12,16,20,17,6y2k= x2k*hk= 7,22,32,36,40,32,11y3k= x3k*hk= 12,37,52,41,14,0,0 已知序列xk=k+2,0k12, hk=1,2,1試?yán)弥丿B相加法計(jì)算線性卷積, 取L=5 。第13頁(yè)/共25頁(yè): FIR filter : input s

5、equence 為DFT點(diǎn)數(shù)，一般取2的整數(shù)次冪第14頁(yè)/共25頁(yè)% Generate the noise sequenceN = 64; d = rand(1,N)-0.5;% Generate the uncorrupted sequence and add noisen = 0:N-1;s= 2*n.*(0.9).n);x= s+ d;% the length of moving average filterM = 4;% Generate the moving average filter coefficientsh = ones(1,M)/M; % Perform the overl

6、ap-add filtering operationy = fftfilt(h,x,8);第15頁(yè)/共25頁(yè)第16頁(yè)/共25頁(yè)k1kxM-1第17頁(yè)/共25頁(yè)n1nxM-1n2nxL-1)1(1nRnMxLL-)(1nRnxLL-)1(1nRnxLL-第18頁(yè)/共25頁(yè)1111111111111111111101012011021012301210 xxxx Mx Mxx Mxxxxxx Mx Mx Mxx Mx Mxx-22222011102xxxMxLxLM-111111111111111111111111100001211000012120000011002100123401230 xx

7、 Mx Mxxxx Mxx Mx Mxx Mxxxxxx Mx Mx Mx Mx Mx Mx Mx-2222222011121xxxMxMxMxLxL-1111111111111111111101012011021012301210 xxxx Mx Mxx Mxxxxxx Mx Mx Mxx Mx Mxx-22222011102xxxMxLxLM-第19頁(yè)/共25頁(yè) x1k L x2k則L點(diǎn)循環(huán)卷積若x1k為 M 點(diǎn)序列, x2k為L(zhǎng) 點(diǎn)序列 ， LM第20頁(yè)/共25頁(yè)2. 重疊保留法（overlap save） 方法： (1) 將xk長(zhǎng)序列分段，每段長(zhǎng)度為L(zhǎng)。 (2) 各段序列xnk與 M點(diǎn)

8、短序列hk循環(huán)卷積。 (3) 從各段循環(huán)卷積中提取線性卷積結(jié)果。前M-1個(gè)點(diǎn)不是線性卷積的點(diǎn)，因ynk=xn k L hk故分段時(shí)，每段與其前一段有M-1個(gè)點(diǎn)重疊。第21頁(yè)/共25頁(yè)-x k(M1)M-1-L (M 1)L-1x 0kx 1k2L-Mk第一段前需補(bǔ)M-1個(gè)零第22頁(yè)/共25頁(yè)2. 重疊保留法（overlap save）記：ynk =xn k L hk第23頁(yè)/共25頁(yè) yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14x1k=0, 0, 2, 3, 4x2k=3, 4, 5, 6 ,7x3k=6 ,7 , 8, 9, 10y1k= x1k hk= 11, 4, 2, 7, 12x4k=9, 10 , 11, 12,13y2k= x2k hk= 23, 17, 16, 20, 24y3k= x3k hk= 35, 29, 28, 32, 36y4k= x