利用FFT计算线性卷积

北京理工大学,实验报告,利用FFT计算线性卷积

实验三 利用FFT计算线性卷积

实验记录

1. 比较当序列长度分别为8,16,32,64,256,512,1024时两种方法计算的时间

一、直接线性卷积

程序代码

for n1=3:10;

L=2^n1;

x=ones(1,L);

h=cos(0.2*pi.*x);

tic

y=conv(x,h);

toc

end

程序结果：

Elapsed time is 0.000104 seconds.

Elapsed time is 0.000022 seconds.

Elapsed time is 0.000018 seconds.

Elapsed time is 0.000021 seconds.

Elapsed time is 0.000031 seconds.

Elapsed time is 0.000059 seconds.

Elapsed time is 0.000152 seconds.

Elapsed time is 0.000508 seconds.

二、快速卷积

程序代码

for n0=3:10;

L=2^n0;

n=0:L;

x=heaviside(n)-heaviside(n-L);

h=cos(0.2*pi.*n);

X=fft(x);

H=fft(h);

Y=X.*H;

tic

y=ifft(Y);

toc

end

北京理工大学,实验报告,利用FFT计算线性卷积

程序结果

Elapsed time is 0.000041 seconds.

Elapsed time is 0.000441 seconds.

Elapsed time is 0.000075 seconds.

Elapsed time is 0.000070 seconds.

Elapsed time is 0.001507 seconds.

Elapsed time is 0.000544 seconds.

Elapsed time is 0.005577 seconds.

Elapsed time is 0.002435 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

2.考察当L=2048和4096，M=256时两种方法计算时间

1）N=2048时

一、直接线性卷积

程序代码

L=2048;

M=256;

n0=0:L;

x=heaviside(n0)-heaviside(n0-L);

n1=0:M;

h=cos(0.2*pi.*n1);

tic

y=conv(x,h);

toc

程序结果

Elapsed time is 0.011091 seconds

二、 快速卷积

程序代码

L=2048;

M=256;

n0=0:L;

x=heaviside(n0)-heaviside(n0-L);

n1=0:M;

h=cos(0.2*pi.*n1);

tic

X=fft(x,2048);

H=fft(h,2048);

Y=X.*H;

y=ifft(Y);

toc

程序结果

Elapsed time is 0.005779 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

2）N=4096时

一、直接线性卷积

程序代码

L=4096;

M=256;

n0=0:L;

x=heaviside(n0)-heaviside(n0-L);

n1=0:M;

h=cos(0.2*pi.*n1);

tic

y=conv(x,h);

toc

程序结果

Elapsed time is 0.002153 seconds.

二、快速卷积

程序代码

L=4096;

M=256;

n0=0:L;

x=heaviside(n0)-heaviside(n0-L);

n1=0:M;

h=cos(0.2*pi.*n1);

tic

X=fft(x,2048);

H=fft(h,2048);

Y=X.*H;

y=ifft(Y);

toc

程序结果

Elapsed time is 0.005149 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

3.利用重叠相加法计算线性卷积，考察L=2048和4096时的计算时间

1）L=2048

程序代码

L=2048;

M=256;

x=ones(1,L);

n=0:M-1;

h=cos(0.2*pi*n);

N=L+M-1;

y=zeros(1,N);

subLen=M;

subNum=L/M;

subLenY=2*M-1;

tic

H=fft(h,2*M-1);

for count=1:subNum

x_temp=x(((count-1)*subLen+1):(count*subLen));

X=fft(x_temp,2*M-1);

Y=X.*H;

y_temp=ifft(Y,2*M-1);

y(((count-1)*subLen+1):(count*subLen+M-1))=y(((count-1)*subLen+1):(count*subLen+M-1))+y_temp;

end

toc

程序结果

Elapsed time is 0.003825 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

2）L=4096

程序代码

L=4096;

M=256;

x=ones(1,L);

n=0:M-1;

h=cos(0.2*pi*n);

N=L+M-1;

y=zeros(1,N);

subLen=M;

subNum=L/M;

subLenY=2*M-1;

tic

H=fft(h,2*M-1);

for count=1:subNum

x_temp=x(((count-1)*subLen+1):(count*subLen));

X=fft(x_temp,2*M-1);

Y=X.*H;

y_temp=ifft(Y,2*M-1);

y(((count-1)*subLen+1):(count*subLen+M-1))=y(((count-1)*subLen+1):(count*subLen+M-1))+y_temp;

end

toc

程序结果

Elapsed time is 0.006678 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

4.利用重叠保留法计算两个序列的线性卷积。考察L=2048和4096时的计算时间

1）L=2048

程序代码

L=2048;

M=256;

x=ones(1,L);

n=0:M-1;

h=cos(0.2*pi*n);

N=L+M-1;

useLen=M;

subLen=useLen+M-1;

subNum=round(L/useLen);

x_bar=[zeros(1,M-1),x];

tic

H=fft(h,subLen);

for count=1:subNum

x_temp=x_bar(((count-1)*useLen+1):(count-1)*useLen+subLen);

X=fft(x_temp,subLen);

Y=X.*H;

y_temp=ifft(Y,subLen);

y(((count-1)*useLen+1):(count*useLen))=y_temp(M:subLen);

end

x_temp=x_bar((count*useLen+1):N);

X=fft(x_temp,subLen);

Y=X.*H;

y_temp=ifft(Y,subLen);

y((count*useLen+1):N)=y_temp(M:2*M-2);

toc

程序结果

Elapsed time is 0.008932 seconds.

北京理工大学,实验报告,利用FFT计算线性卷积

2）L=4096

程序代码

L=4096;

M=256;

x=ones(1,L);

n=0:M-1;

h=cos(0.2*pi*n);

N=L+M-1;

useLen=M;

subLen=useLen+M-1;

subNum=round(L/useLen);

x_bar=[zeros(1,M-1),x];

tic

H=fft(h,subLen);

for count=1:subNum

x_temp=x_bar(((count-1)*useLen+1):(count-1)*useLen+subLen); X=fft(x_temp,subLen);

Y=X.*H;

y_temp=ifft(Y,subLen);

y(((count-1)*useLen+1):(count*useLen))=y_temp(M:subLen); end

x_temp=x_bar((count*useLen+1):N);

X=fft(x_temp,subLen);

Y=X.*H;

y_temp=ifft(Y,subLen);

y((count*useLen+1):N)=y_temp(M:2*M-2);

toc

程序结果

Elapsed time is 0.009648 seconds.

本文来源：https://www.bwwdw.com/article/z9mj.html