❶ 快速卷積在什麼情況下效率最高呢
一、實驗目的
1、學會FFT演算法程序(或函數）的使用方法;
2、了解序列的線性卷積和圓周卷積之間的關系;
3、驗證有限長FFT演算法實現線性相關運算的快速計算方法;
4、解FFT的點數對快速卷積與快速相關運算結果所產生的影響;
5、了學會利用FFT演算法進行有限長序列的線性卷積的快速計算;
6、掌握基-2快速傅立葉變換（Fast FourierTransform,FFT)的演算法原理及其程序實現方法.
二、實驗原理
1、有限長序列的線性卷積和圓周卷積線性卷積和圓周卷對於有限長序列，存在兩種形式的卷積,即積。設x(n)是長度光JM的有限長序列，y(n)是長度為N的有限長序列,則二者的線性卷積可表示為:
M-1
線性卷積的結果序列f(n)是一個長度為L=N +M -1的有限有限長序列，且長序列。將x(n)及y(n)均補零增長為L點的二者的L點的圓周卷積可表示為:
圓周卷積的結果序列f(n)是一個長度為L的有限長序列，由圓周卷積的點數所決定。有限長序列的線性卷積和圓周卷積之間的關系可用公式表示如下:
即:圓周卷積是線性卷積以圓周卷積的點數幾為周期進行周期延拓後所取的主值序列。因而,在圓周卷積的點數大於或等於線性卷積的長度時、圓周卷積結果和線性卷積結果相等，這也是快速卷積演算法的理論基礎之一。
2、離散傅里葉變換的卷積性質
離散傅里葉變換的卷積性質也是快速卷積演算法的另一理論基礎。若f(n)是有限長序列x(n)和有限長序列y(n)的L點圓周卷積,即公式（5-2），則 f(n)的L點離散傅里葉變換為: F_c (k)=X(k)Y(k)
3、Matlab中FFT與IFFT的實現
離散傅立葉變換（Discrete Fourier Transform, DFT)實現了頻域的離散化,方便了計算機處理,在數字信號處理中有著非常重要的作用。但直接計算DFT的運算量與變換長度N的平方成正比,計算量太大。而快速傅立葉變換FFT則是快速計算DFT的有效演算法，大大提高了DFT的運算效率，在信號頻譜的分析、濾波器頻率響應的計算，以及線性卷積的快速計算等方面起著非常重要的作用。FFT 採用分組計算的方式進行DFT的快速計算,具體演算法原理參看教材，在附錄B中也給出了常用的基-2時間抽取FFT演算法和分裂基FFT 演算法的C語言程序。相應的,IFFT 則為離散傅里葉反變換，即 IDFT 的快速計算方法。在Matlab中，提供了f(t)和 ifi(t)兩個函數來分別實現快速傅立葉變換的正變換和反變換。Ft(t)和if(t)兩個函數是用機器語言而不是Matlab 指令寫成的，執行速度很快。除了輸入、輸出參數的含義不同之外，這兩個函數的調用方法完全相同，因此以ff()函數為例說明二者的使用方法。ff()函數常用調用格式有兩種:
(1）Xk=fft(xn)
其中，xn為輸入時域序列x(n)，返回結果xk為x(n)的離散傅里葉變換X(k)。當xn是矩陣時（對應於多通道信號)，計算xn中每一列信號的離散傅里葉變換。當xn的長度是2的整數冪,采
用基2快速演算法計算,否則採用較慢的混合基演算法進行計算。
（2）Xk=fft(xn，NFFT)
這種調用格式相比較於上一種調用格式,多了一個輸入參數NFFT,用於指定FFT的點數。當NFFT的值是2的整數冪,採用基-2快速演算法計算，否則採用較慢的混合基演算法進行計算。當xn的長度大於NFFT時,對 xn進行自動截斷;當xn的長度小於NFFT時,在xn後自動進行補零。
4、快速卷積基本演算法的原理
利用FFT進行有限長序列的線性卷積的快速計算即為快速卷積演算法。按照上述相關原理,利用FFT計算線性卷積,即計算公式中的f(n)的演算法步驟可用下圖來表示:
其中，FFT運算的點數L應滿足L≥N+ M-1。為了採用基-2的演算法，常常需要L還應滿足L=2M
5、快速相關演算法原理
利用 FFT 講行有限長序列相關運算的快速實現則稱為快速相關演算法。若(n)是長度頭M的有限長序列，y(n)是長度為N的有限長序列，則一者的線性百相關序列R(m)與二者的線性卷積運算之間的關系可表示
由於線性卷積可以用FFT講行快速計算，則按公式，相關運算也可以利用fft進行快速計算，在此不再贅述其原理。需要時,根據傅立葉變換的反折和共軛特性可以減少一次FFT的使用提高計算效率。
三、實驗步驟、數據記錄及處理
本實驗利用Matlab中提供的fft()和 ifft()函數進行快速卷積演算法和快速相關演算法性卷積和圓周卷積之間的關系進行驗證。具體的實驗內容和實驗的實現，並對有限長序列線
步驟如下所示:
其中:
1、用 Matlab生成兩個有限長序列x(n) y(n)
(1）基於fft()和 ifft()函數，編程利用4點快速卷積演算法計算有限長序列x(n)與y(n)的卷積,結果令為c1(n)。
(2）基於fft()和 ifft()函數,編程利用速卷積演算法計算有限長序列x(n)與y(n)的卷積，結果令為c2(n)
(3）調用conv()函數計算有限長序列x(n)與y(n)的卷積,結果令為c3(n)。分別繪制序列x(n)、y(n)、c1(n)、c2(n)和c3(n)的圖形。對結果進行分析，並通過實驗結果驗證有限長序列線生卷積和圓周卷積之間的關系。
2、設兩個有限長序列x(n)和h(n)分別為:
(1）x(n)=(sin 0.4n)·R,(n+1);
(2）h(n)=(0.9)"R,o(n+1)
按圖所示的快速卷積演算法原理編寫完整的快速卷積演算法程序計算y(n)=x(n)*h(n)，繪制序列圖形，並通過 conv()函數對結果進行驗證。
3、將實驗1中實驗內容4所給定的信號利用快速相關演算法進行自相關序列的計算,並將結果與實驗1中的結果進行對比驗證。
實驗程序：
clc;clear all;close all;
nx=0:1:2;x=[1,1,1];%確定x(n)與y(n)的自變數取值范圍
ny=0:1:2;y=[2,2,2];%生成x(n)與h(n)
L=pow2(nextpow2(length(x)+length(y)-1));%確定FFT快速卷積的點數
xk=fft(x,L);%計算x的L點FFT,結果為x(k)
yk=fft(y,L);%計算y的L點FFT,結果為y(k)
YK=xk.*yk;%計算y(k)
c1n=ifft(YK,4);%四點
c2n=ifft(YK,L);%八點
c3n=conv(x,y);%線性卷積
n1=0:1:3;%確定n1的取值范圍
n2=0:1:7;%確定n2的取值范圍
n3=0:1:4;%確定n3的取值范圍
%繪制x(n)與y(n)波形
figure('name','x(n)與y(n)序列');
subplot(2,1,1);stem(nx,x);grid on;xlabel('n');ylabel('x(n)');title('序列x(n)');
subplot(2,1,2);stem(ny,y);grid on;xlabel('n');ylabel('y(n)');title('序列y(n)');
%繪制x(n)與y(n)序列卷積波形
figure('name','x(n)與y(n)序列卷積');
subplot(3,1,1);stem(n1,c1n);grid on;xlabel('n');ylabel('c1(n)');title('x(n)與y(n)的4點fft');
subplot(3,1,2);stem(n2,c2n);grid on;xlabel('n');ylabel('c2(n)');title('x(n)與y(n)的8點fft');
subplot(3,1,3);stem(n3,c3n);grid on;xlabel('n');ylabel('c3(n)');title('x(n)與y(n)的線性卷積');
登錄後復制
clc;clear all;close all;
nxn=1:15;nhn=1:20;%確定x(n)與y(n)的自變數取值范圍
xn=sin(0.4*nxn);hn=0.9.^nhn;%生成x(n)與h(n)
L=pow2(nextpow2(length(xn)+length(hn)-1));%確定FFT快速卷積的點數
Xk=fft(xn,L);%計算x的L點FFT,結果為x(k)
Hk=fft(hn,L);%計算y的L點FFT,結果為y(k)
Yk=Xk.*Hk;%計算YK
y1n=ifft(Yk,L);%對YK調用IFFT，求得y1(n)
y2n=conv(xn,hn);%計算y2(n)的卷積
n1=(nxn(1)+nhn(1)):1:(L+nxn(1)+nhn(1)-1);%確定n1的自變數取值范圍
n2=(nxn(1)+nhn(1)):1:(nxn(15)+nhn(20));%確定n2的自變數取值范圍
%繪制有限長序列想x(n)與h(n)
figure('name','x(n)與h(n)序列');
subplot(2,2,1);stem(nxn,xn);grid on;xlabel('n');ylabel('x(n)');title('x(n)=(sin0.4n)*R15（n+1）');
subplot(2,2,2);stem(nhn,hn);grid on;xlabel('n');ylabel('h(n)');title('h(n)=(（0.9)^n)R20(n+1)');
subplot(2,2,3);stem(n1,y1n);grid on;xlabel('n');ylabel('y(n)');title('快速卷積法計算y(n)');
subplot(2,2,4);stem(n2,y2n);grid on;xlabel('n');ylabel('y(n)');title('conv()函數計算y(n)');
登錄後復制
clc;clear all;close all;
n1=1:100;n2=1:100;%確定n1,n2取值范圍
x=[101,82,66,35,31,7,20,92,154,125,85,68,38,23,10,24,83,132,131,118,90,67,60,47,41,21,16,6,4,7,14,34,45,43,48,42,28,10,8,2,0,1,5,12,14,35,46,41,30,24,16,7,4,2,8,17,36,50,62,67,71,48,28,8,13,57,122,138,103,86,63,37,24,11,15,40,62,98,124,96,66,64,54,39,21,7,4,23,55,94,96,77,59,44,47,30,16,7,37,74];
mean(x(:))
x=x-mean(x);
Rx=xcorr(x);
y=x(end:-1:1);
subplot(2,1,1);stem(Rx);grid on;xlabel('t');ylabel('Rx');title('xcorr()函數計算的自相關序列');
L=pow2(nextpow2(length(n1)+length(n2)-1));%確定FFT快速卷積的點數
Xk=fft(x,L);%計算x的L點FFT,結果為x(k)
Yk=fft(y,L);%計算y的L點FFT,結果為y(k)
Rk=Xk.*Yk;%計算YK
Rn=ifft(Rk,L);%對RK調用IFFT，求得y1(n)
n=(n1(1)+n2(1)):(L+n1(1)+n2(1)-1);%確定n的自變數取值范圍
subplot(2,1,2);stem(1:200,Rn(1:200));grid on;xlabel('t');ylabel('R(n)');title('fft計算的自相關序列');
登錄後復制
四、思考題
（1）對實驗內容2中快速卷積基本演算法的運算量進行分析,即乘法和加法運算次數。
（2）利用實例說明快速卷積基本演算法的適用條件，即在什麼情況下效率最高。
（3）實驗內容3中,如何通過DFT的性質，減少一次ftt（）函數的調用,提高計算效率?
五、總結
通過此次實驗的練習，加深理解FFT 在實現數字濾波（或快速卷積）中的重要作用，更好的利用FFT進行數字信號處理，並且掌握了循環卷積和線性卷積兩者之間的關系